Natural join is a useful special case of the relational join operation (and is extremely common when denormalizing data pulled in from a relational database). Spark’s DataFrame API provides an expressive way to specify arbitrary joins, but it would be nice to have some machinery to make the simple case of natural join as easy as possible. Here’s what a natural join needs to do:
- For relations R and S, identify the columns they have in common, say c1 and c2;
- join R and S on the condition that R.c1 == S.c1 and R.c2 == S.c2; and
- project away the duplicated columns.
so, in Spark, a natural join would look like this:
We can generalize this as follows (note that joining two frames with no columns in common will produce an empty frame):
Furthermore, we can make this operation available to any
DataFrame via implicit conversions:
One of the great things about Apache Spark is that you can experiment with new analyses interactively. In the past, I’ve used the
sbt console to try out new data transformations and models; the console is especially convenient since you can set it up as a custom Scala REPL with your libraries loaded and some test fixtures already created.
However, some of Spark’s coolest new functionality depends on some aspects of Scala reflection that aren’t compatible with how
sbt uses classloaders for tasks, so you’re liable to see
MissingRequirementError exceptions when you try and run code that exercises parts of Spark SQL or the DataFrame API from the
You can certainly run a regular Scala REPL or the
spark-shell, but doing so sacrifices a lot of the flexibility of running from
sbt: every time your code or dependencies change, you’ll need to package your application and set your classpath, ensuring that all of your application classes and dependencies are available to the REPL application.
Fortunately, there’s an easier way: you can make a small application that runs a Scala REPL set up the way you like and ask
sbt how to set its classpath. First, write up a simple custom Scala REPL, like this one:
ReplApp application sets up a Scala REPL with imports for some common Spark classes and bindings to a
ConsoleApp object is just a simple wrapper for Spark context and configuration; see the Silex project, where my team is collecting and generalizing infrastructure code from Spark applications, for more details – or just change this code to set up a
SparkContext as you see fit.)
In order to run this application, you’ll need to set its classpath, and
sbt gives you a way to do find out exactly what environment it would be using so you can run the application manually.2 First, make sure you have a copy of
sbt-extras either in your repository or somewhere pointed to by
SBT in your environment. Then, create a shell script that looks like this:
You can then run
repl.sh and get a Scala REPL that has all of your app’s dependencies and classes loaded and will let you experiment with structured data manipulation in Spark.
Frustratingly, apps that use these features will work, since the classes Scala reflection depends on will be loaded by the bootstrap classloader, and test cases will work as long as you have
sbtfork a new JVM to execute them! Unfortunately,
sbtcannot currently fork a new JVM to run a console. ↩
run-maintask is the right way to run most applications from
sbt, but it seems to be somewhat flaky when launching interactive console applications. ↩
Last night I had a crazy realization: I could probably replace the majority of what my team hopes to accomplish with standup meetings, design documents, project management apps, and social code sharing features with a single tool.
Before I reveal what this tool is, let’s consider why most team collaboration is suboptimal. Everyone who has been in standup meetings or read groupwide status reports has probably seen the following status-update antipatterns; in fact, unless you’re a better teammate than I, you’ve probably been guilty of each of these yourself:
- “This week I read 253 emails in my inbox, 1478 emails from mailing list folders, and sampled 75 messages from my spam folder to make sure none of them were spuriously filed. I also wrote a net 498 lines of code, brewed eight pots of coffee and five shots of espresso, spent 246 minutes in meetings, and urinated twenty-one times.”
- “I’m still working on the same thing I was working on last week. None of you are close enough to this problem to know why it is so tough and I’m too defeated to explain it to you, so feel free to assume that I am either heroically deep in the weeds or have gotten totally ratholed on something irrelevant.”
- “I discovered that this graph search problem could be better modeled as a language-recognition query, and spent some time investigating efficient representations before coming up with a really clever approach involving boolean satisfiability – there was a paper in the SIGYAWN ‘75 proceedings that used a similar technique; maybe you read it too – … [fifteen minutes pass] … and improved performance by 0.57%.”
It doesn’t seem like it should be, but getting the level of detail right in status updates is hard, and it’s hard for stupid reasons. Your big accomplishments for the week are easy to explain and you don’t want to make it seem like you did nothing, so you start accounting for every second since last Monday. It’s too depressing to consider that the bug that’s been keeping you awake for the last few weeks still isn’t solved and you don’t want to spend time talking about all of the dim trails you investigated, so you’ll Eeyore it up to get out of the meeting and back to work. You’re so deep in a problem that you think everyone else needs to know about a bunch of tiny details and can’t tell that they’ve all fallen asleep.
To some extent, all of these seemingly-different problems stem from too much status and not enough context. But even if we recast status reports as context updates, we’ve traded the problem of finding an appropriate level of status detail for finding an appropriate amount of context. How do we decide what an appropriate amount of context is?
Think of the best and worst talks you’ve ever seen. A good talk doesn’t exhaustively describe the work the author did, but it places it in enough context so that the audience has some way to evaluate the claims, get interested, and decide if the work is worth investigating further. A bad talk is vague, disorganized, gets bogged down in irrelevant details, or only makes sense to people who already know everything about its subject.
Now think about the best talks you’ve ever given. Giving a good talk – even more so than writing a good article or essay – hones and clarifies your argument. You have to step out of your bubble and see your work from the perspective of your audience, because you have just a few minutes to catch their attention before they tune out and start checking their email while waiting for the next speaker. Now, I’ve given a lot of lectures, academic talks, and conference presentations, but I’ve found that giving informal, internal tech talks on some interesting aspect of something I’ve been working on has paid off disproportionately.
So I don’t want my team to give each other status updates. Instead, I want us to give regular short talks. And the medium that I want us to use as we develop these talks is a shared slide deck, updated throughout the week.1 In spite of the amazingly persistent ubiquity of speakers reading through their wall-of-text decks like apparatchiks in dystopian fiction, slides aren’t a substitute for talks. However, a good slide deck supports a good talk, and designing a slide deck helps to make sure that you have the right amount of context in your talk, because the wrong amount of context in a talk leaves some obvious odors in the deck:
- Oh, you need to drop down to 18 point type to cover everything you wanted here? That’s probably a clue that you’re covering something that would be better addressed in further discussion or a subsequent deep dive.
- Does this slide feel totally bare? Maybe you need more background here.
- Could you draw a picture and replace this paragraph? Could you write a sentence and replace this code excerpt?
- If you had to explain this to a customer or an executive – really, to anyone who’s sharp and engaged but not a domain expert – right now, where would you start? How would you keep them interested?
My team is doing data science, so a lot of what we wind up delivering turns out to be presentations and visual explanations. As a result, this practice could be even more beneficial for us than it might be for other groups. Rigorously working out explanations among ourselves is certain to pay off in the future, when we have to present results internally or externally. By using a shared deck, we can annotate with questions, link to more detail elsewhere, and rapidly iterate on our presentations as we have improved results or come up with clearer explanations.
(Thanks to RJ Nowling, who suggested the idea of a regular “analytics review,” like a code review, and got me thinking along these lines.)
Over eight years ago, Richard WM Jones wrote a great but disheartening article about his experience serving as a technical reviewer for an infamous book about OCaml. The post made quite an impression on me at the time and I’ve often recalled it over the years whenever opportunities to do prepress reviews have landed in my inbox. Briefly, Jones was asked to use terrible tools (Microsoft Word) to deal with stilted, error-ridden prose surrounding unidiomatic and broken code. For his trouble, he got an hourly wage that would have represented a slight raise over what I made mowing my neighbors’ lawns in high school.
Recently, I was invited to review a book under even more outrageous terms. The project in question was the second edition of a book on a subject I understand pretty well.1 I didn’t respond to their first invitation to review because:
- I assumed they’d cast a fairly wide net;
- my spare time is pretty well saturated these days and reviewing technical prose is a lot of slow, precise work;
- in my opinion, this publisher releases a lot of subpar products and I don’t want my name and reputation associated with a mediocre book;
- the earlier edition of this book had received extremely poor reviews; and
- the compensation offered was simply risible: credit in the frontmatter of the finished book, a paper or ebook copy of the finished book, and an additional ebook of my choice.
Now, there are always tradeoffs involved in choosing contract work: one can weigh compensation against loving one’s work, having pride in products, having a prestigious position, or enjoying a low-stress work environment. But I’m pretty sure I know what the skill set that would enable someone to be a competent reviewer of a book like this one is worth, and the people who have it aren’t likely to be motivated to volunteer for a for-profit corporation in exchange for credit and free ebooks. Personally, a demand on my spare time that depends on my professional expertise (and takes away from time I might spend with my family, bicycling, catching up on sleep, or learning something new) but offers no compensation is not particularly compelling, and it becomes far less compelling when it seems like an opportunity to be involved with a product that I’m not likely to believe in and that I probably wouldn’t be proud to put my name on. So when the publisher sent me a rather snippy message following up, I wrote back, gently indicating that I would not be able to do the review and that they’d likely have trouble finding a qualified reviewer who was willing to work for free.
One wonders what publishers expect to accomplish with prepress technical reviews. In Jones’s case, he provided a lot of feedback and suggested that Apress not proceed with publishing Practical OCaml without major revisions; they ignored his objections but used his name in the final text. (At least he was paid something, I guess.) Not every publisher works this way, but the ones that do seem more interested in shifting the blame for bogus content to an external contractor than in releasing a thoroughly vetted product.
Requests to do specialized work for free are almost always insulting. However, the apparent value that some publishers ascribe to prepress review is even more insulting if you consider it from the perspective of the technical-book consumer!
In fact, this publisher had invited me to write a book for them on this topic earlier this year, apparently before deciding to revise their existing offering instead. ↩
I’ll be speaking later this afternoon at ApacheCon EU. The title of my talk is “Iteratively Improving Spark Application Performance.” The great thing about Apache Spark is that simple prototype applications are very easy to develop, and even a first attempt at realizing a new analysis will usually work well enough so that it’s not frustrating to evaluate it on real data. However, simple prototypes can often exhibit performance problems that aren’t obvious until you know where to look.
In this talk, we’ll introduce Spark’s execution model and discuss how to use Spark effectively. I’ll use a prototype implementation of my bike data analytics application as a running example and will present four general principles to keep in mind when writing efficient Spark applications, complete with detailed code explanations. My slides are available here as a PDF.
If you’re interested in more detail about the bike data analytics application, you can watch a brief video demo or watch a video of my talk about this application from Spark Summit earlier this year. Finally, I’ve published a blog post covering similar principles for improving Spark applications, which will be a useful reference whether or not you’re able to attend the talk.1
If you’re also at ApacheCon today, I hope to see you at 15:50 CET!
The talk will feature visual explanations and other material that are not in that post, but the post has links to full code examples suitable for off-line experimentation. ↩
My last post covered some considerations for using Spark SQL on a real-world JSON dataset. In particular, schema inference can suffer when you’re ingesting a dataset of heterogeneous objects. In this post, I’d like to sketch out some ways to connect schema inference to type inference, in order to point to automated solutions to some of the problems we’ve seen.
We’ll start out by reviewing some definitions from the world of type systems:
- a type is a range of values.
- a product type is a compound type that describes structures with multiple values of (possibly) different types (e.g., tuples or records). You can think of a product type as being like the Cartesian product of several other types: if we have types A and B, the type A × B (i.e., the type of pairs of one value in A and one value in B) can represent the Cartesian product of A and B.
- a sum type is a compound type that represents the disjoint union of several other types. Given types A and B, the type A + B represents the sum of A and B (i.e., any value in A or any value in B).
In Scala terms, a simple example of a product type is a tuple:
and a simple example of a sum type is a basic linked list:
Note that, in the case of the linked list (as with other standard recursive data structures), we’re actually looking at a sum type in which one of the summed types is a product type: an
IntList can either be an
EmptyList or a cons cell, consisting of a pair of an
Int value (the head of the list) and an
IntList (the tail of the list).
Also note that, in Scala, sum types are tagged. You can statically distinguish between cons cells and the empty list in a case match.1 C programmers are familiar with a related kind of sum type: the untagged union, which describes a structure that can hold one value that can be of several different types. If you have a C
union, you’ll need to explicitly track what kind of value it’s holding since you won’t be able to tell what kind of value it contains statically.
Given a collection of JSON objects,2 a schema inference algorithm produces a type that is the supertype of every object in the collection. (This is an interesting problem only if the collection contains objects of different types.) As an example, consider the following two objects:
The first models some characteristics of a bicycle and the second models some characteristics of a car. Both have
gears, but bicycles have data about what kind of
handlebars they include; cars have data about whether or not they include anti-lock brakes (
abs) and specify what kind of
fuel they expect. If we ask Spark SQL to infer a schema for a collection including these two objects, we’ll get something like this:
root |-- abs: boolean (nullable = true) |-- fuel: string (nullable = true) |-- gears: integer (nullable = true) |-- handlebars: string (nullable = true) |-- pedals: string (nullable = true)
Given a collection of objects with types T₁, T₂, ⋯, Tₓ, what we’re trying to get is the sum type T₁ + T₂ + ⋯ + Tₓ . The way we get this type is as an untagged union: we get an object that has the union of all of the fields of T₁, all of the fields of T₂, and so on. (Put another way, we’re really treating a heterogeneous collection as a union of homogeneous collections and identifying its schema as the union of the schemas for each included homogeneous collection.) Just as if we were using a C
union, we’d have to figure out whether or not each object was a bicycle or a car. Fortunately, since we’re be in a safe-language context, we’d know that an object with a value in the
pedals field wouldn’t have a value in the
It should be clear that this is a totally reasonable approach, since it combines a straightforward implementation with a pleasant and unsurprising user experience: by adding a simple filter to my queries, I can select only objects of a given type from a heterogeneous collection. For example, if I want to find the mean number of gears for every bicycle with drop handlebars, I could write the following query (assuming I’d registered my
SchemaRDD as a table called
handlebars will be
NULL for every car, this query will only consider bicycles. Other collections may not admit such straightforward differentiation between object kinds, of course.
Problems and possible solutions
Tagging diverging types
As I mentioned last week, things begin to break down when we attempt to construct the sum of types that have the same field names but diverging types for those fields, as in the following example:
A few days ago, Spark would have failed to infer a schema for this collection of objects, but open-source development moves quickly and now it will handle the conflicting types by giving users a schema in which the
branches field contains an array of strings (and in which every object in the collection has its
branches field cast to an array of strings).
In general, it seems like whatever technique we might adopt schema inference should prefer imprecise results to a crash. But are there ways Spark could do a better job of inferring schemas for heterogeneous collections with diverging field types? I believe there might be, and part of the answer is going from untagged unions to tagged unions.
The fedmsg data set is a heterogeneous collection of objects; in some of these objects, the
branches field models one concept as an array of strings, and in others, it models a different concept as an array of objects. I solved this problem by preprocessing the JSON to rename the different
branches fields – in effect, dividing the
branches fields into two tagged possibilities, like this. We could imagine that Spark could handle schema divergence by automatically identifying equivalence classes of field types, perhaps naming them with an integer subscript (e.g.,
branches_2) or with some abbreviated identifier for the value type, as follows:
Here’s an alternative way we could make the tagging explicit, by wrapping the diverging field’s values in an object:
The advantage to this tagged-union approach is that it makes it possible to write queries that handle heterogeneous collections. The disadvantage is that the path from the schema root to the tagged value will be different from the path to that value in the schemas of any of the objects in the original heterogeneous collection. The schema change may be surprising to the user, but – by definition – any approach to derive a fixed schema for a collection of objects with diverging schemas will not result in a schema that is totally compatible with the objects in the original collection.
The other problem I observed related to encoding maps as JSON objects, as in the following example where we have a map from bicycle names to vehicle objects:
The inferred schema for a collection including an object like this will have a distinct field for every key in every map. In this case, we don’t have an immediately great solution from the broader world of type systems. However, it seems that some heuristic – for example, “if an object has more than n fields and each has a value of the same type, it is a map” – might be able to do a good job of identifying objects that model maps.
In any case, it is possible for the user to preprocess their objects in order to encode maps in a different way if that will make it easier to query the data after ingest.
Spark SQL’s support for schema inference is an extremely cool feature, although it obviously isn’t able to work magic by ascribing rigid structure to heterogeneous collections of ad hoc objects. Some minor improvements could make inferred schemas more useful for these kinds of collections, though.
Scala doesn’t support untagged union types directly – although there are clever ways to encode them in the type system – and Scala won’t actually be able to infer sum types from collections of untagged values: the inferred type of
Array[String + Int]. ↩
(Slightly) more precisely: objects are defined recursively as unordered collections of key-value pairs, where keys are strings and values can be numbers, booleans, strings, objects, or arrays of values. ↩
In this post, I’ll briefly introduce fedmsg, the federated message bus developed as part of the Fedora project’s infrastructure, and discuss how to ingest fedmsg data for processing with Spark SQL. While I hope you’ll find the analytic possibilities of fedmsg data as interesting as I do, this post will also cover some possible pitfalls you might run into while ingesting complex JSON data or the contents of large SQL databases into Spark SQL more generally.
fedmsg is one of the coolest things about Fedora’s infrastructure.1 Because nearly everything that happens in Fedora is logged to a messaging bus, there is a vast amount of public data about the daily operation of a large and thriving open-source community, all in one place.2 The whole list of message topics published on the Fedora project’s fedmsg bus are documented here, but these examples should give you a taste of the kinds of messages available for inspection:
- when a Fedora contributor updates the package build metadata (including RPM specfile, patches, source tarball list. etc.) in
- when a package build is started (and then again when the package build succeeds or fails, and when the package build is pushed out to the distribution),
- when a Fedora community member tags a package with keywords,
- when a blog post is syndicated to Fedora Planet,
- when a wiki page is created or updated,
- when an IRC meeting starts or ends,
and so on. Furthermore, these data are accessible either as a stream of messages (as they are generated), as JSON-encoded historical data via a REST interface, or as a PostgreSQL dump of all historical fedmsg activity.
An exhaustive treatment of fedmsg is outside the scope of this post,4 but I wanted to make it clear that
- open infrastructure for a very large open-source project is an extremely cool thing,
- there is a lot of interesting data available in fedmsg,
- there have been some cool applications built atop fedmsg already (see Fedora Badges for an Xbox-like “achievements” system or Ralph Bean’s animated visualization for a couple of fun examples), and
- there are a lot of possibilities for making sense of this data using Spark, Spark SQL, and Spark Streaming.
Getting the historical data
I wanted to look at a large amount of data to start with, so I began by grabbing a dump of the datanommer database. (Datanommer is a service that records each message on the fedmsg bus in a SQL database.) The nightly dump I got was about 3 gb compressed and expanded to about 40 gb – certainly not “big data,” but too big to fit in main memory on my workstation. I loaded the dump into a new Postgres database and started inspecting it.
The largest table by far is
messages,5 which has the following schema:
There are a couple of things to note here:
signaturefields account for the bulk of the raw data, and
_msgfield actually contains the string representation of a topic-specific JSON object.
As we’ll see, each of these can lead to some pitfalls when attempting to ingest the data into Spark.
Pitfall 1: Single-node memory limits and Slick projections
Here’s the core of a very simple program that ingests fedmsg records from a local PostgreSQL database, using Slick, and outputs these to JSON files,6 one for each record,7 in a local directory (I’m not reproducing the generated code that models datanommer tables and rows here):
Note that the
message2json implicit conversion doesn’t do anything with the
These fields are necessary for critical production applications because anyone can write to the fedmsg bus. However, I’m not planning to make any irreversible decisions based on my analyses of fedmsg data and am thus not currently interested in actually verifying message contents or provenance. Since I’m also not currently interested in wasting memory or performance, I’m going to strip these out of the generated JSON.
Unfortunately, even shipping these fields from the database to the JVM only to ignore them dramatically impacts the performance and memory footprint of our importer, so we’ll want to project these away sooner. The best solution I found for efficiently projecting away nullable fields from a SQL database accessed via Slick involved modifying the generated code to control how case classes were instantiated from the database. The generated code includes definitions of case classes for rows in each table, like this:
The generated code also contains classes describing each table; these include a
* method defining the default projection from a tuple to a row-specific case class. In our case, the default projection for the
messages table looks like this:
If we modify it, we can ignore
signature (essentially returning SQL
NULL values instead of enormous encoded objects for these fields):
Now we can fire up a REPL and produce JSON documents from the datanommer data; the following example will take the first 100 rows PostgreSQL gives us and generate documents for them in
Pitfall 2: The Lost Caverns (of type inference)
Spark SQL supports Hive-style records and arrays within relational data. An especially cool feature of Spark SQL, though, is that it can infer a HiveQL schema from a collection of JSON documents with complex nested structure (see the
jsonFile method of
SQLContext, which will operate on a single JSON document or a directory of JSON documents).
If you have a clone of the Spark repository on your machine, the easiest way to try this out is to launch
sbt hive/console from within your local clone. You’ll then be able to build a schema from some JSON documents:
JSON is convenient for users because it lets us specify untyped objects with no fixed schema. Unfortunately, JSON lets us specify untyped objects with no fixed schema. This means that Spark might have trouble inferring a fixed schema for our data. Consider how type inference works in real programming languages: if a variable can take one of two possible values, its type must be the unification on their types. Sometimes, this means we get a trivial typing (in Scala terms,
Any), but in other cases, it means we get a contradiction (in Scala terms,
Nothing). When Spark is inferring types for our documents, it will simply raise an exception if it tries to unify two objects with diverging types, as you can see in the following example:
The two JSON objects each contain a field called
branches, but in the former it is an array of strings, while in the latter it is an object. In the case of fedmsg data, this problem came up because different message topics used
branches to correspond to different (but related) concepts. If we could rename these different cases, we could avoid the diverging types. Since the JSON library we’re using has a facility to transform JSON values based on partial functions, we can do this easily:
renameBranches method above will simply translate fields named
branches with array-of-strings values to fields named
pkg_branches with the same values and translate fields named
branches with array-of-objects values to fields named
git_branches with the same values. Other fields are ignored by this code.
Pitfall 3: Too many columns
A related problem comes up when we have JSON objects who use field names as entity names, like in the following example (taken from a message describing a
files is essentially a collection of objects describing different changed files in the commit (
sources), but it is represented as an object with a field for each changed file. Because of this, the inferred schema will have a field in the
stats.files object for every single filename that has ever been committed to Fedora’s
git repository! (That’s a lot of
NULL values in a typical row.)
There are other similar cases in the fedmsg data as well where entity names become field names; these can all be handled by transformation rules in fairly straightforward fashion.
This post should have enough background to help you get started looking at fedmsg data with Spark SQL. In future posts, I’ll discuss some additional correctness and efficiency considerations; demonstrate how to unify warehoused, batched, and streaming data; and introduce some analytic applications involving fedmsg data.
I’ve recently been reading Jay Kreps’ I ♥ Logs, in which Kreps argues (from principle and from experience) for the centrality of the log abstraction in distributed systems. I may write a longer review later, but the argument is sound (and consonant with some of the arguments initially made for basing Fedora’s infrastructure around a messaging bus) and the book is definitely worth checking out! ↩
There are also tables to store the names of users, the names of packages, and to model the relationships between users or packages and fedmsg messages involving those users or packages. ↩
I’m using JSON here because of the rich structure of the topic-specific messages. If you were ingesting flat relational data, it would almost certainly make more sense to use JdbcRDD and do the ingest within Spark. ↩
Please don’t use the above code in production; it’s intended to be simple, not efficient. Producing one file per record makes it easy to see where things are going wrong, but it’s very slow both for this program and for the Spark jobs that you’ll want to write to read these data. Your local filesystem probably won’t be too happy with you, either. ↩
I went to Strata + Hadoop World last week. This event targets a pretty broad audience and is an interesting mix of trade show, data science conference, and software conference. However, I’ve been impressed by the quality and relevance of the technical program both of the years that I’ve gone. The key to finding good talks at this kind of event is to target talks focusing on applications, visualization, and fundamental techniques, rather than ostensibly technical talks.1 In the rest of this post, I’ll share some of my notes from the talks and tutorials I enjoyed the most.
This was a great tutorial: the pace, scope, content, and presentation were all really excellent. It provided enough context to make sense of D3’s substantial capabilities and left me feeling like I could dive in to using D3 for some interesting projects. Finally, Gutierrez provided lots of links to other resources to learn more and experiment, both things I’d seen, like bl.ocks.org, and things that were new to me, like tributary.io and JSFiddle.
The standalone D3 tutorial on DashingD3JS.com seems like an excellent way to play along at home.
Engineering Pipelines for Learning at Scale
I attended the “Hardcore Data Science” track in the afternoon of the tutorial day; there were several interesting talks but I wanted to call out in particular Ben Recht’s talk, which mentioned BDAS in the title but was really about generic problems in developing large-scale systems that use machine learning.
Recht’s talk began with the well-known but oft-ignored maxim that machine learning is easy once you’ve turned your analysis problem into an optimization problem. I say “oft-ignored” here not because I believe practitioners are getting hung up on the easy part of the problem, but because it seems like raw modeling performance is often the focus of marketing for open-source and commercial projects alike.2 The interesting engineering challenges are typically in the processing pipeline from raw data to an optimizable model: acquiring data, normalizing and pruning values, and selecting features all must take place before modeling and classification. Learning problems often have this basic structure; Recht provided examples of these pipeline stages in object recognition and text processing domains.
The main motivating example was Recht’s attempt to replicate the Oregon State Digital Scout project, which analyzed video footage of American football, and answered questions including what plays were likely from given offensive formations. So Recht’s team set out to stich together video footage into a panorama, translate from video coordinates to inferred field coordinates, and track player positions and movements. This preprocessing code, which they had implemented with standard C++ and the OpenCV library, took ten hours to analyze video of a four-second NFL play. Expert programmers could surely have improved the runtime of this code substantially, but it seems like we should be able to support software engineering of machine-learning applications without having teams of experts working on each stage of the learning pipeline.
The talk concluded by presenting some ideas for work that would support software engineering for learning pipelines. These were more speculative but generally focused on using programming language technology to make it easier to develop, compose, and reason about learning pipelines.
Since the talks from the plenary sessions are all fairly brief (and freely available as videos), I’ll simply call out a couple that were especially enjoyable.
- John Rauser from Pinterest gave a great talk on using simulation techniques (in particular random permutation) to identify statistical significance in a way that’s more intuitive for many of us than the well-known (but poorly-understood) a priori methods for doing the same.
- Bob Mankoff’s talk about the New Yorker Caption Contest was enormously entertaining and had some really interesting insights about how people receive, analyze, and rank humor.
Domain-Specific Languages for Data Transformation
Joe Hellerstein and Sean Kandel of Trifacta gave a talk on domain-specific languages for data transformation in general and on their Wrangle system in particular. (Trifacta is also responsible for the extremely cool Vega project.) The talk led with three rules for successful data wrangling, which I’ll paraphrase here:
- your processes, not your data, are most important;
- reusable scripts to process data are more valuable than postprocessed and cleaned data; and
- “agile” models in which preprocessing is refined iteratively in conjunction with downstream analysis of the processed data are preferable to having preprocessing take place as an isolated phase.3
The first act of the talk also referenced this quotation from Alfred North Whitehead, which set the tone for a survey of DSLs for data transformation and query construction:
By relieving the brain of all unnecessary work, a good notation sets it free to concentrate on more advanced problems…
In the 1990s, several data processing DSLs emerged that were based on second-order logic, proximity joins, and composable transformations.4 Hellerstein argued that, since these underlying formalisms weren’t any simpler to understand than the relational model, the DSLs weren’t particularly successful at simplifying data transformation for end-users.
Raman and Hellerstein’s Potter’s Wheel system presented a visual interface to SQL for data cleaning; it could automatically detect bad data and infer structure domains but wasn’t particularly easier to use than SQL: putting a visual, menu-driven interface over a language doesn’t generally lower the cognitive load of using that language.5
The Wrangler system (which forms the basis for the Wrangle DSL in Trifacta’s product) attacks the problem from a different angle: data cleaning operations are suggested based on explicit user guidance, semantic information about types and domains, and inferences of user intent based on prior actions. The entire problem of suggesting queries and transformations is thus expressible as an optimization problem over the space of DSL clauses. With the interface to the Wrangle DSL, the user highlights features in individual rows of the data to appear in the transformed data or in a visualization, and the system presents several suggested queries that it had inferred. The Wrangle system also infers regular expressions for highlighted text transformations, but since regular expressions – and especially machine-generated ones – are often painful to read, it translates these to a more readable (but less expressive) representation before presenting them to the user.
Kandel gave a very impressive live demo of Wrangle on a couple of data sets, including techniques for sensibly treating dirty or apparently-nonsensical rows (in this example, the confounding data included negative contribution amounts from election finance data, which represented refunds or revised accounting). This is excellent work at the intersection of databases, programming languages, machine learning, and human-computer interaction – which is a space that I suspect a lot of future contributions to data processing will occupy.
Clustering for Anomaly Detection
Sean Owen’s talk on using Spark and k-means clustering for anomaly detection was absolutely packed. Whether this was more due to the overwhelming popularity of talks with “Spark” in the title or because Sean is widely known as a sharp guy and great presenter, I’m not sure, but it was an excellent talk and was about more than just introducing clustering in Spark. It was really a general discussion of how to go from raw data to a clustering problem in a way that would give you the most useful results – Spark was essential to make the presentation of ETL and clustering code simple enough to fit on a slide, but the techniques were generally applicable.
The running example in this talk involved system log data from a supervised learning competition. Some of the log data was generated by normal activity and some of it was generated by activity associated with various security exploits. The original data were labeled (whether as “normal” or by the name of the associated exploit), since they were intended to evaluate supervised learning techniques. However, Owen pointed out that we could identify anomalies by clustering points and looking at ones that were far away from any cluster center. Since k-means clustering is unsupervised, one of Owen’s first steps was to remove the labels.
With code to generate an RDD of unlabeled records, Owen then walked through the steps he might use if he were using clustering to characterize these data:
- The first question involves choosing a suitable k. Since Owen knew that there were 23 different kinds of records (those generated by normal traffic as well as by 22 attack types), it seems likely that there would be at least 23 clusters. A naïve approach to choosing a cluster count (viz., choosing a number that minimizes the distance from each point to its nearest centroid) falls short in a couple of ways. First, since cluster centers are originally picked randomly, the results of finding k clusters may not be deterministic. (This is easy to solve by ensuring that the algorithm runs for a large number of iterations and has a small distance threshold for convergence.) More importantly, though, finding n clusters, where n is the size of the population, would be optimal under this metric, but it would tell us nothing.
- The vectors in the raw data describe 42 features but the distance between them is dominated by two values: bytes read and bytes written, which are relatively large integer values (as opposed to many of the features, which are booleans encoded as 0 or 1). Normalizing each feature by its z-score made each feature contribute equally to distance.
- Another useful trick is encoding features whose space is a finite domain of n elements as n boolean features (where only one of them will be true). So if your feature could be either
durianin the raw data, you could encode it as four boolean-valued features, one of which is true if and only if the feature is
apple, one of which is true if and only if the feature is
banana, and so on.
- Using entropy (or normalized mutual information) to evaluate the clustering can be a better bet since fitness by entropy won’t increase until k = n as fitness by Euclidean distance will. Another option is restoring the labels from the original data and verifying that clusters typically have homogeneous labels.
Many of the talks I found interesting featured at least some of the following common themes: using programming-language technology, improving programmer productivity, or focusing on the pipeline from raw data to clean feature vectors. I especially appreciated Sean Owen’s talk for showing how to refine clustering over real data and demonstrating substantial improvements by a series of simple changes. As Recht reminds us, the optimization problems are easy to solve; it’s great to see more explicit focus on making the process that turns analysis problems into optimization problems as easy as possible.
Alas, talks with technical-sounding abstracts often wind up having a nontrivial marketing component! ↩
This is related to the reason why “data lakes” have turned out to be not quite as useful as we might have hoped: a place to store vast amounts of sparse, noisy, and irregular data and an efficient way to train models from these data are necessary but not sufficient conditions for actually answering questions! ↩
Hellerstein pointed out that the alternative to his recommendation is really the waterfall model (seriously, click that link), which makes it all the more incredible that anyone follows it for data processing. Who would willingly admit to using a practice initially defined as a strawman? ↩
I was first confronted with the false promise of visual languages in the 1980s. I had saved my meager kid earnings for weeks and gone to HT Electronics in Sunnyvale to purchase the AiRT system for the Amiga. AiRT was a visual programming language that turned out to be neither more expressive nor easier to use than any of the text-based languages I was already familiar with. With the exception of this transcript of a scathing review in Amazing Computing magazine (“…most of [its] potential is not realized in the current implementation of AiRT, and I cannot recommend it for any serious work.”), it is now apparently lost to history. ↩
leitmotif is a very simple templating tool that generates directories from prototypes stored in git repositories. Its design prioritizes simplicity and a minimal set of external dependencies.
leitmotif tool is still under development and some interesting features are planned for future work, it is already useful for many project-templating tasks. This post will show you how to get started.
To install the RubyGem, simply run
gem install leitmotif.
To install the standalone script, run the following commands:
In the future, I expect that
leitmotif packages will be available for CentOS and Fedora.
leitmotif tool is self-documenting. Run
leitmotif help to see options.
Copying a prototype from a remote repository
leitmotif clone URL to make a local copy of the remote prototype repository at
URL in your local Leitmotif prototype store (under your home directory).
Listing locally-installed prototypes
leitmotif list to see the prototypes you have installed in your local store.
leitmotif generate PROTOTYPE OUTPUT_DIR to instantiate
OUTPUT_DIR. In this form,
PROTOTYPE must be the path to a git repository containing a Leitmotif prototype. This command supports the following options:
PROTOTYPEas the name of a prototype repository in the local store rather than as a path
OUTPUT_DIRbefore processing the prototype, if it exists
gittag, branch, or SHA to use from the prototype repository (defaults to
--bindings KEY:VALUE ...: a list of variable bindings to use while instantiating the prototype
--verbose: provide additional output as
Creating Leitmotif prototypes
A Leitmotif prototype is just a git repository with a particular structure. Specifically, a prototype must have two entries in the repository root directory:
- a YAML file named
.leitmotifthat contains metadata about the prototype, and
- a directory named
proto, which contains the prototype itself.
.leitmotif file is just a YAML representation of a hash of metadata options. The following keys can appear in a
:name: the name of the prototype (used for documentation)
:version: the version of the prototype (used for documentation)
:required: a list of variables that must have user-provided values when the prototype is instantiated
:ignore: a list of files to copy to the instantiated prototype without processing by the templating engine
:defaults: a hash consisting of default values for prototype variables
Here’s an example
.leitmotif file, from a prototype for Spark application development:
Prototypes and templating
With the exception of the files in the
:ignore list, all of the files in a prototype repository are processed by ERB after they’re copied to the output directory. For more details on eRuby, see elsewhere, but here are a few basics to get you started:
- If a template file contains Ruby code surrounded by
%>, that code is evaluated at prototype instantiation time with user-supplied variable bindings.
- If a template file contains Ruby code surrounded by
%>, that code is evaluated at prototype instantiation time with user-supplied variable bindings and the result of evaluating that code is substituted into the document at that point.
Combining these two, we can see how to use loops in a file:
The above will generate a Markdown file containing a bulleted list that will strike terror into the heart of any adult who has ever been on a bus full of middle-schoolers.
I wrote this tool to solve an immediate need1 and will be updating it as new requirements become apparent. However, there are a few things that are already on my roadmap:
- automated test coverage (currently – and shamefully! – there is none)2
- additional commands, e.g., to inspect installed prototypes
- post-instantiation actions, e.g., to rename a file or create a directory based on the result of a variable expansion
I’ve written in the past about what a mistake it is to add behavioral incentives or morality clauses to the licenses for open-source projects. Briefly, these clauses are bad:
- philosophically because they infringe the on basic software freedom to use a freely-available project for any purpose1;
- legally because they generally rely on vague and subjective terms and (paradoxically) thus rendering your license both radioactive and unenforceable; and
- practically because instead of preventing people from doing things that you don’t like, they just prevent people – even those who wouldn’t be inclined to do things you don’t like! – from using your work.
One software domain in which licenses with usage restrictions are commonplace (and, unfortunately, widely accepted) is digital fonts. This has historically been a problem for Fedora, since many “free” fonts are not open-source (in that they do not permit modification) or have usage restrictions (in particular, against “commercial” use). Furthermore, much like novel one-off open-source software licenses, most partially-free licenses authored by font creators are unlikely to be unambiguous or legally sensical.2
The problem gets far worse when we look at commercial fonts, for which the type of application and type of output are often incorporated in usage restrictions. Last year, I licensed a font whose EULA was self-contradictory; you can click the link for the whole story, but the main problem was that it claimed to broadly allow rasterization, including use to “create images on computer screens, paper, web pages, photographs, movie credits, printed material, T-shirts, and other applications,” but that I couldn’t use the font “as part of broadcasting video or film […] the use of the font software in titling, credits or other text for any onscreen broadcast via television, video, or motion picture.”
Since one of my creative endeavors is editing home and bicycling videos, the combination of being allowed to “create … movie credits” but not to “use the font software in titling, credits or other text for … motion picture” was pretty frustrating, especially since the EULA hadn’t been obviously available for review until after I licensed the face. (There were numerous other problems, ambiguities, and contradictions with the license, and when I asked the foundry for for a clarification, they curtly denied that there was anything to be confused about.)
For more than a year and a half, this inconsistent license has been my benchmark to evaluate whether or not a font is more trouble than it’s worth, and I’ve at least learned to be more careful reading font EULAs.3 However, I recently came across an example4 that so completely outclasses the contradictory license that I can’t imagine it will be replaced as the new standard for terrible usage clauses in licenses. Here’s an excerpt; the author’s name is redacted:
Fonts by [redacted] may NOT be used for pornographic, derogatory, defamatory or racist material (in any form, printed or virtual); fonts by [redacted] may NOT be used by individuals or companies involved in child abuse, child pornography or child labour; fonts by [redacted] may NOT be used by individuals or companies involved in destruction of natural resources and/or habitat, logging (even legal), palm oil exploitation/harvesting, tuna fishing, whaling, animal trafficking, oil and/or gas drilling or transporting and mining. Fonts by [redacted] may NOT be used by individuals or companies promoting an unhealthy lifestyle (fast food, energy drinks, foods containing GM ingredients). Fonts by [redacted] may NOT be used by companies or individuals involved in Genetic Modification / Genetic Alteration of organisms. Fonts by [redacted] may NOT be used by individuals or companies involved in fur trade, or making use of fur. Fonts by [redacted] may NOT be used by missionaries, individuals or institutions of any creed or faith for the purpose of converting others to their creed or faith. Fonts by [redacted] may NOT be used to instigate terror, hate, intolerance, fear or racism.
I almost don’t know where to begin with this one, since it raises so many questions for the licensor:
- When do we cross the line from light-hearted ribbing to “derogatory material”? Are satire and parody proscribed?
- Say I use this font to title a bicycling video; would the licensor need to see what sort of chain lubricant I used or whether or not I was a regular inner-tube recycler before determining that I wasn’t involved in “destruction of natural resources”? (What about people who eat animal protein? Or plants?)
- Are we mostly worried about the Indonesian orangutan, or is (relatively-low-impact) West African palm oil OK? Is the palm oil industry full of typophiles? How many jars of palm oil bore the licensor’s glyphs before he added this clause?
- How are we defining “unhealthy” or “genetic modification”? It seems like consensus regularly changes on the former and the latter is – like much of the language in this clause – actually kind of vague despite being deployed in an absolute manner. Can I replant seeds from my best tomatoes or must I toss them? (In a related question, since I have the suspicion that it might come up in a future revision of this license: is it OK to use this font to promote vaccination?)
- What about people of faith whose creed includes a concept of vocation, or the notion that they serve God through their creative and professional work?
Hopefully, these kinds of questions – along with many more like them that you may be asking yourself – underscore why this kind of license is a problem: the licensor probably hoped to make a clear statement of principles, condemn what he saw as social ills, and avoid assisting people and groups he’d find objectionable. Instead, the license restrictions are so broad as to exclude use by anyone except the font’s creator (who is unlikely to sue himself for breach of contract). No matter who you are or what you do, if the licensor wanted to sue you, he probably could.
I’m inclined to excuse that last sentence, though, since the licensor seems to know a thing or two about instigating “hate, intolerance, [and] fear.”
The GNU Project calls this “Freedom 0.” ↩
If you’re releasing open-source software, you should use a well-known license. If you want to release a font freely, you should have a very good reason for using anything except the Open Font License or the LPPL. ↩
This may be surprising to people used to regular software licensing, but I’ve seen fonts for sale in different places with different licenses! It seems like some sellers have standard EULAs and require font creators to allow distribution under these, while others maintain the creators’ EULAs. ↩
Alas, I came across this example after paying for a license. ↩