People sent me lots of submissions! Some are great, some are a bit of a stretch.

• Overpriced by an order of magnitude.
• The letters of “art” are found embedded, in order, in “pharmaceuticals”.
• Search keywords that cost the most to advertise on?
• “Wyeth”: I think this means this, and this.
• “Romeo and Juliet” famously includes both “art” (wherefore art thou) and pharmaceuticals (poison!)
• Some art has been created out of pharmaceuticals.
• Some art has been created under the influence of pharmaceuticals.

I was asking because I was playing around with a dataset of 100,000 noun phrases’ appearances on the web, from the Reading the Web project at CMU. That is, for a noun like “art”, this data has a large list of phrases in which the word “art” is used, across some 200 million web pages. For two noun concepts, we can see what they have in common and what’s different by looking at examples of how people use them when writing. So, for “art” versus “pharmaceuticals”:

The middle column, showing ways in which people talk about both “art” and “pharmaceuticals”, makes it pretty clear. What they have in common is that they’re both products: you can buy, sell, produce, and store them. (There’s also an intellectual goods aspect: they both can be stolen.) This really didn’t occur to me at first; silly me, I thought art was a thing of beauty removed from such mundane considerations. A number of the submitted answers, though, center around the theme of them both being expensive — so we have positive agreement between corpus statistics and human judgments!

Examining massive numbers of contexts like this follows what the infinitely wise Dinosaur Comics calls “a statistically-based descriptivist approach to semantics.” Or as linguist J.R. Firth put it, “You shall know a word by the company it keeps.” Many subtleties of the two concepts can be seen just in their context lists. For example, in the left column, we see that only art “is a commodity”. Well, certainly pharmaceuticals are a commodity too. But that’s so obvious it’s not worth saying. Proclaiming that “art is a commodity”, however, is interesting. Maybe we think about this (possible) fact more.

As for the data: it comes from 200 million web pages (500 million sentences), and is filtered to contexts that appear more than five hundred times in the data. It was collected as part of a research project that seeks to extract a database of knowledge from this information — “reading the web”. (Yes, Hadoop was involved.) To make the table, I took the contexts’ set differences and intersection and showed a random subsample from each.

A final note. Will pointed out that in Alice in Wonderland, the Mad Hatter asks, “Why is a raven like a writing desk?” I tried that query on this data, but unfortunately, it didn’t contain many instances of “raven”. However, it does include a proper name “Raven” — which turns out to be an anime character. Not the first time I’ve seen the Internet’s massive amount of anime knowledge get in the way of a very serious semantic extraction system!

Many thanks to Adam, Joanna, Will, Vikas, and Michael for the submitted answers.

I have a data-driven answer, but am curious how easy it is to guess it, and in what sense it’s valid. I’ll post my answer and supporting evidence on Tuesday.

For one recent ad-hoc task I had — reformatting 1GB of textual feature data into a form Matlab and R can read — I tried writing implementations in several languages, with help from my classmate Elijah. The results really surprised us:

To be clear, the problem is to take several files of (item name, feature name, value) triples, like:

000794107-10-K-19960401 limited 1
000794107-10-K-19960401 colleges 1
000794107-10-K-19960401 code 2
...
004334108-10-K-19961230 recognition 1
004334108-10-K-19961230 gross 8
...

And then rename items and features into sequential numbers as a sparse matrix: (i, j, value) triples. Items should count up from inside each file; but features should be shared across files, so they need a shared counter. Finally, we need to write a mapping of feature IDs back to their names for later inspection; this can just be a list.

This task is simple, but it’s representative of many data munging tasks out there. It inputs and outputs textual data. It’s probably one-off. The algorithm is easy — especially since it’s a subtask of something larger — but still complex enough you’ll need a debug cycle or two. You want to get it done fast so you can get on to the real work. Complex programming tools, like debuggers, are of little use — you figure out what’s going on by inspecting the output. Complex data processing environments, like Hadoop or an RDBMS, are also of little use — you have to munge in the first place to load data into them.

It turns out, this is a task AWK was made for. It’s a language dating from the original Bell Labs Unix era — circa 1977 — and it’s extremely specialized for processing delimited text files in a single pass. Perl was created in part to supersede it, but for this core use case, Awk is much more elegant and clearer. The implementation here is only 8 lines of code, expanded from merely 3 when I first wrote it.

Since it’s a standardized language, many implementations exist. One of them, MAWK, is incredibly efficient. It outperforms all other languages, including statically typed compiled ones like Java and C++! It wins on both LOC and performance criteria — a rare feat indeed, transcending the usual competition of slow-but-easy scripting languages versus fast-but-hard compiled languages.

[There's another big pro-VM story here: Java beat C++, both in LOC/ease-of-programming as well as performance. C++ was, as usual, a total nightmare to write. What you don't see in the LOC numbers is the sheer amount of time spent googling through every weird issue. For example, apparently g++ requires you to define the hash function in order to use a hash_map of string keys. Or, there are a zillion different ways to split a string, none of them standard. Then there are 2 different I/O and 2 different string libraries given its C heritage, and if you make the wrong choices, performance is terrible. I'm totally sure that given some more rewriting, the C++ implementation can be made the fastest. It's just a question of how much pain you go through to find the right rewrites. All the other implementations were written in the most straightforward, simplest way possible. C++ abjectly fails the "get it done quick" criterion.]

My most pleasant surprise learning Awk was its shortcuts for reading and writing files. Like shell, there is no concept of a file handle — you don’t open and close files, you just specify the filename and the VM figures it out. Even Perl, king of syntactic shorthand, doesn’t have this useful feature; and even Ruby, with its elegant open()-block-cleanup construct, is clunkier. It sounds minor, but this eliminates a number of bugs you can make in scripts.

But what I most appreciate about Awk is the discourse structure of its programs: every clause is a potentially conditional action to be performed with the current record. If you want actions to be taken upon program start or exit, you declare special clauses for that. Awk manages all these features while being staying incredibly small and simple — the advantages of being a domain-specific language. I think it feels a little more like a super-flexible, index-challenged version of SQL than it does a standard scripting language. I suspect Awk’s simplicity and specialization is part of why Mike Brennan was able to make Mawk so insanely fast. If your only datatypes are strings and hashes, then compile-time type inference is pretty easy.

Awk is also well-suited to the “Disk is the New Tape” era. That is, right now, hard drive sizes are rapidly growing — allowing very large datasets — but random access seek times aren’t catching up. In this setting, the only way to process data will be via linear scans, accessing one item of data at a time. (E.g. running variance, online learning, column stores, etc.) This is the core philosophy behind Hadoop’s computation model — and Awk’s. If hard drives are like tape drives, then it’s worth looking in to other blast-from-the-past technologies! (Similar point about SAS, in fact.)

There are many Awk tutorials on the web. This one is decent, though I strongly recommend Ken Church’s classic tutorial Unix for Poets. It shows how to do all sorts of great things with Unix text processing tools, including Awk.

All the code, results, and data can be obtained at github.com/brendano/awkspeed. I’d love to see results for more languages. And I hope someday someone tries writing an LLVM Awk — will it be even faster?

However, as far as I can tell, it might still be the easiest-to-use text classifier package out there. You don’t have to program — just invoke commandline arguments — and it can accommodate reasonably sized datasets, does tokenization, stopword filtering, etc. for you, and has some useful feature selection and other options. Based on my limited usage, it seems well-implemented. If anyone knows of a better one I’d love to hear it. I once looked at, among other things, GATE and UIMA, and they seemed too hard to use if you wanted to download something that did simple text classification; or else, maybe they didn’t have documentation on how to use them in that manner. Rainbow does. If I had to recommend a text classifier to a social scientist today, I might say they should Rainbow.

(GATE and UIMA call themsleves “architectures”. I usually don’t want an architecture, I want a program that does stuff. LingPipe was the only other system I found that had good web documentation saying how to use it to do text classification. It looks like a good option, if you’re willing to write some code. There are numerous academic efforts to make automated content analysis systems that at a high level sound like the right sort of thing, but nearly all of them have poor web docs so it’s hard to tell whether they do what you want.)

In the meantime, the current Rainbow download has issues compiling on modern GCC and Mac OSX — some issues documented here. I worked through them put my patched version (only tested on GCC 4.0, OSX 10.5) up here: github.com/brendano/bow

Here’s our final figure, a k-means clustering of face photos via perceived social attributes (social concepts/types? with exemplars?):

I just started reading the rest of the book and it’s very fun.  Peter Norvig’s chapter on language models is gripping.  (It does word segmentation, ciphers, and more, in that lovely python-centric tutorial style extending his previous spell correction article.)  There are also chapters by many other great researchers and practitioners (some of whom you may have seen around this blog or its neighborhood) like Andrew Gelman, Hadley Wickham, Michal Migurski, Jeffrey Heer, and still more… I’m impressed just by the talent-gathering-and-organizing operation. Big kudos to editors Toby Segaran and Jeff Hammerbacher, and O’Reilly’s Julie Steele.

I also have an apparently secret code that gets you a discount, so email me if you want it.  I wonder if I’m not supposed to give out many of them.  Hm.

Coreference resolution is an interesting NLP problem.  (Examples.)  It involves honest-to-goodness syntactic, semantic, and discourse phenomena, but still seems like a real cognitive task that humans have to solve when reading text [1].  I haven’t read the whole literature, but I’ve always been puzzled by the crop of papers on it I’ve seen in the last year or two.  There’s a big focus on fancy graph/probabilistic/constrained optimization algorithms, but often these papers gloss over the linguistic features — the core information they actually make their decisions with [2].  I never understood why the latter isn’t the most important issue.  Therefore, it was a joy to read

• Aria Haghighi and Dan Klein, EMNLP-2009.  “Simple Coreference Resolution with Rich Syntactic and Semantic Features.”

They describe a simple, essentially non-statistical system that outperforms previous unsupervised systems, and compares favorably to supervised ones, by using smart features.  It has two-ish modular components:

• Syntactic constraints: entity type agreement, appositives, and a few other things that get at syntactic salience.
• Semantic filter:  non-pronoun mentions must be corpus-pattern-compatible with their antecedents; described below.

For each mention, these constraints filter previous mentions to several possible antecedents.  If there’s more than one, the system picks the closest.  Entity clusters are formed in the simplest (dumbest) way possible, by taking the transitive closure of these pairwise mention-antecedent decisions.

The lexical semantic filter is interesting.  They found that syntactic cues have recall issues for non-pronoun references, e.g. the company referring to AOL.  You need to know that these two words tend to be compatible with each other.  They create a very specific lexical resource — of word pairs compatible to be coreferent — by finding coreferent expressions via bootstrapping in a large unlabelled text corpus (Wikipedia abstracts and newswire articles.  But they say only 25k Wiki abstracts?  There are >10 million total; how were they selected?).

Using a parsed corpus, they seeded with appositive and predicate-nominative patterns: I’m guessing, something like ”Al Gore, vice-president…” and “Al Gore was vice-president”.  Then they extracted connecting paths on those pairs.  E.g., the text “Al Gore served as the vice-president” then yields the path-pattern “X served as Y”.  Then there’s one more iteration to extract more word pairs — pairs that appear a large number of times.

They cite Hearst 1992, Snow et al 2005, and Phillips and Riloff 2007.  But note, they don’t describe their technique as trying to be a general hypernym finder; rather, its only goal is to find pairs of words (noun phrase heads) that might corefer in text that the final system encounters.  In fact, they describe the bootstrapping system as merely trying to find instances of noun phrase pairs that exhibit coreference.  I wonder if it’s fair to think of the bootstrapping system as a miniature coreference detector itself, but tuned for high-precision, by only considering very short syntactic paths (no longer than 1 sentence).  I also wonder if there are instances of non-pronoun coreference that aren’t hyponym-hypernym pairs; if not, my analysis here is silly.

Coverage seems to be good, or at least useful: many non-pronoun coreference recall errors are solved by using this data.  (I can’t tell whether it’s two-thirds of all recall errors after the syntactic system, or two-thirds of the errors in Table 1.)  And they claim word pairs are usually correct, with a few interesting types of errors (that look quite solvable).  As for coverage, I wonder if they tried WordNet hypernym/synonym information, and whether it was useful.  My bet is that WordNet’s coverage here would be significantly poorer than a bootstrapped system.

This paper was fun to read because it’s written very differently than the usual NLP paper.  Instead of presenting a slew of modelling, it cuts to the chase, using very simple algorithms and clear argumentation to illustrate why a particular set of approaches is effective.  There’s lots of error analysis motivating design decisions, as well as suggesting concusions for future work.  In particular, they think discourse, pragmatics, and salience aren’t the most important issues; instead, better syntactic and semantic modelling would give the biggest gains.

There’s also something very nice about reading a paper that doesn’t have a single equation yet makes a point, and is easy to implement yourself to boot.  I think the machine learning approach to NLP research can really hurt insight.  Every paper is obsessed with held-out predictive accuracy.  If you’re lucky, a paper will list out all the features they used, then (only sometimes!) they make a cursory attempt at finding which features were important.  A simple hand-coded system lends itself to easily describing and motivating every feature by itself — better narrative explanations and insight.  Which type of research is more useful as science?

Final note: it’s not totally fair to consider this system a non-statistical one, because its syntactic and semantic subsystems rest on complicated statistical components that required boatloads of labelled training data — the Stanford parser, Stanford NER, and the Charniak parser.  (I wonder how sensitive performance is relative to these components.  Could rule-based parsing and NER work as well?)  Further, as they point out, more complicated structured approaches to the problem of forming entity partitions from features should improve performance.  (But how much?)

[1] As opposed to, say, the rarified activity of treebanking, a 318-page-complex linguistic behavior that maybe several dozen people on Earth are capable of executing.  There’s a whole other rant here, on the topic of the behavioral reality of various linguistic constructs.  (Treebank parsers were extensively used in this paper, so maybe I shouldn’t hate too much…)

[2] There are certainly exceptions to this like Bengston and Roth, or maybe Denis and Baldridge (both EMNLP-2008).  I should emphasize my impression of the literature is from a small subsample.

Amusingly, one of the most useful intro questions is: How to search for “R” materials?

Mike Driscoll (who organized an in-person conference event to get this bootstrapped) pointed out that in many ways StackOverflow is a nicer forum for help than a mailing list.  (i.e. the impressive but hard-to-approach R-help.)  It’s more organized, easier to browse, and repetition and wrong answers can get downvoted.  (And more thoughts from John Cook.)

This comes from a slide explaining the impressive speed results for their glmnet regression package.  Substantively, I’m interested in their observation that coordinate descent works well for sparse data — if you’re optimizing one feature at a time, and that feature is used in only a small percentage of instances, there are some neat optimizations!

But mostly, I had a fun time skimming the glmnet code.  It’s written in 2008, but, yes, the core algorithm is written entirely in Fortran, complete with punchcard-style, fixed-width formatting!  (This seems gratuitous to me — I thought the modern Fortran-90 had done away with such things?)  I’ve felt clever enough making 10x-100x performance gains by switching from R or Python down to C++, but I’m told that this is nothing compared to Fortran with the proprietary Intel compiler — still the fastest language in the world for numeric computing.

(Hat tip: Revolution Computing pointed out the useR-2009 presentations.)