stupid NLP tricks: haikubot!

At Indiana, we have an IRC server where many of the CS students hang out. I keep myself logged in all the time, in a screen session that I'm usually not looking at. But even while I'm not watching, the chat logs just pile up. So I have megabytes of text from the conversations with my friends and colleagues. The clear use for this resource is, of course, generating haiku [0].

So I built a bot that does this! Here is my friend Eric Holk requesting a poem generated from snippets of text that he actually said.

< eholk> haikubot: eholk
< haikubot> do you have enough / memory to cause that was / stored unless it knew

Alright, how does this work?

I use the IRC logs to train a language model from things that each user said [1], on demand. They're cached in case somebody asks for another haiku from that same user's model again, because it can take a few seconds to train the model. The language model is something one could easily implement (although smoothing can get a little tricky), but I just used the default bigram models from NLTK.

We also need to be able to count syllables: this is pretty straightforward using the CMU Pronouncing Dictionary, which also comes with NLTK. If we don't have a stored pronunciation for a word, we back off to some heuristics about English that try to count the number of vowels (with some special rules for English spelling particularities); this comes from nltk_contrib.

To actually generate a line of the haiku, we just sample words from the language model until we have the desired number of syllables. If that fails for some reason, we try again (up to 100 times), and eventually just back off to picking a word from a list of known 5-syllable or 7-syllable words.

The IRC libraries and basic IRC bot structure are adapted from ircbot-collection by Ben Collins-Sussman et al [2].

Here's the code for haikubot! Hopefully this will be fun for somebody else too. If nothing else, it's a pretty good demonstration of some NLTK features working just fine on Python 3. It requires, at the moment, the tip of the NLTK trunk.

---

[0] These are of course not proper haiku as such. Just 5-7-5 syllables.
[1] There is some filtering to try to ignore, for example, code samples, and usernames at the start of lines.
[2] Related! Ben Collins-Sussman's talk: "How to Replace Yourself with an IRC Bot"

reading: Computer Power and Human Reason

Not long ago, I got a copy of Jospeh Weizenbaum's Computer Power and Human Reason from a pile of free books -- there's so much great stuff on the free books table when a professor retires!

I’d recommend reading it if you’re into the ethical issues surrounding computing or the history of AI. The book was published in 1976; our relationship with computing has changed a lot since then, and that was probably the most striking thing about reading the book now.

Weizenbaum was worried about trust that society placed in the computer systems of the time. He describes situations in which people felt they were slaves to systems too complex for people to understand and too far removed from human judgement to be humane; examples include planning systems that told pilots where to bomb during the Vietnam War. But the systems had computers involved, and they were made by experts, so they must be right! "Garbage in; gospel out". And down came the bombs.

I'd argue that we've become less dazzled by computers as such, that we no longer think of them as infallible. But perhaps we're less likely to think about the computers themselves at all. They've become ubiquitous, just the infrastructure that makes society work. My mother (a keen observer of technology) recently remarked that it's strange that we still call them "computers" when the point is to use them for communication. We may still have problems of blind obedience, but perhaps it's better understood as blind obedience to people.

Similarly, Weizenbaum was concerned about the social power wielded by scientists, engineers, and other experts. To me, in the fair-and-balanced political climate, this sounds like a good problem to have: people used to listen to experts? Did they listen to experts when they said things that were politically inconvenient for those with money? Perhaps not...

Computer Power and Human Reason also spends some time with the exuberant claims about AI from before the AI Winter. Herbert Simon said, "... in a visible future – the range of problems they [machines] can handle will be coextensive with the range to which the human mind has been applied", which was clearly somewhat premature. But we have made progress on a lot of fronts! Weizenbaum was quite skeptical that machine translation would be any good, despite claims (which he relates in the book) that MT really just needed more processing power and more data. A few decades later, MT is often pretty good! All it took was more processing power and more data.

There's also some beautifully strange writing. Towards the beginning, he spends a few chapters explaining how computers work, in a formal, abstract way. And then we get this:

Suppose there were an enormous telephone network in which each telephone is permanently connected to a number of other telephones; there are no sets with dials. All subscribers constantly watch the same channel on television, and whenever a commercial, i.e., an active interval, begins, they all rush to their telephones and shout either "one" or "zero," depending on what is written on a notepad attached to their apparatus. ...

I have trouble imagining that this metaphor has helped many people understand digital logic circuits; but I enjoyed reading the book! Perhaps you'd enjoy it as well.

cross-lingual word sense disambiguation

Have I mentioned what I've been working on recently? Maybe I haven't.

In general, I'm working on cross-lingual word- and phrase-sense disambiguation. WSD/PSD is the problem of deciding, for a given word or phrase, which meaning was intended, for some pre-defined sets of meanings. You might get the possible senses out of a dictionary, where they're nicely enumerated, or perhaps from WordNet. The stock example is "bank" -- is it the side of a river, or is it a building where they do financial services? Or, is it the abstract financial institution?

There's a brilliant bit from the prescient Warren Weaver, from 1955 (via):

If one examines the words in a book, one at a time as through an opaque mask with a hole in it one word wide, then it is obviously impossible to determine, one at a time, the meaning of the words . . . . But if one lengthens the slit in the opaque mask, until one can see not only the central word in question but also say N words on either side, then if N is large enough one can unambiguously decide the meaning of the central word . . . . The practical question is: "What minimum value of N will, at least in a tolerable fraction of cases, lead to the correct choice of meaning for the central word?

The "cross-lingual" kind of WSD means that we care about exactly the distinctions that cause you to pick a different word in a given target language, typically because the CLWSD system is meant to be integrated into an MT system; that's becoming fashionable (Carpuat and Wu, 2007). So in this setting, say if you're translating "bank" from English into Spanish, your system doesn't have to decide if it's the building or the institution that owns it -- it's still "banco". Now a riverbank is an "orilla".

In the general case, your system might end up learning how to make distinctions that you as a human didn't know you had to make -- for example, I'm given to understand that Japanese doesn't have just one word for "brother", but "older brother" and "younger brother", which are different enough concepts that they get totally separate words.

Making these choices is typically treated as a classification problem: you get some features for a bunch of instances of usage of a source word, and do supervised learning to get a classifier with (hopefully) good accuracy on the problem of predicting whether this is a "banco" usage or an "orilla" usage. The features are typically things like "which words are in the surrounding context?", or perhaps something fancier based on a parse of the sentence or knowledge about the document as a whole -- whatever you think will be predictive of what the target-language word should be. Hopefully your learning algorithm has some good way of filtering out irrelevant features.

And then, once that's all put together, hopefully you have some extra signal to feed into your translation system, and it makes better word choices, and everybody's happy.

And that's cross-lingual word/phrase-sense disambiguation!

here come some explanatory examples

Having recovered from all that fruitcake and holiday cheer, I've started digging through the code I wrote over the past semester, looking for things that could be straightforward examples.

So far, I've got:

• calculating the entropy of a discrete random variable
• a cute implementation of finite-state automata with matrix multiplication
• calculating the probability of a Markov process going to a particular state, again with matrix multiplication
• a simple CYK-style chart parser for probabilistic grammars (computing inside probabilities, outside probabilities, and the most probable parse)
• a parse evaluator that gives precision and recall for parse trees
• probabilistic part-of-speech taggers that take into account bigrams, both by trying all combinations of tags for the words and using the Viterbi algorithm
• Some pretty clean code for hidden Markov models in general

I've already checked these in over on narorumo. They're all in Python, but some depend on nltk or numpy.

They'll be increasingly clean and documented over the next week or so. I hope these are helpful to somebody!

today's reading: Neighbourhood Components Analysis

Goldberger, Roweis, Hinton, and Salakhutdinov: Neighbourhood Components Analysis. The punchline: ... learning a linear transformation of the input space such that in the transformed space, KNN performs well.

I've been making an effort to read more academic papers. This one came up for one of the many reading groups at the Goog, and I picked it out of my stack a few days ago. Here's the abstract.

In this paper we propose a novel method for learning a Mahalanobis distance measure to be used in the KNN classification algorithm. The algorithm directly maximizes a stochastic variant of the leave-one-out KNN score on the training set. It can also learn a low-dimensional lin- ear embedding of labeled data that can be used for data visualization and fast classification. Unlike other methods, our classification model is non-parametric, making no assumptions about the shape of the class distributions or the boundaries between them. The performance of the method is demonstrated on several data sets, both for metric learning and linear dimensionality reduction.

This is a very common, general problem for machine learning -- you want to build a classifier, and you think you might like to use K Nearest Neighbors; it's dead simple, and a lot of the time, it gets the job done. No complicated models to train up -- if you want to classify an instance (ooh, here's an animal -- is it a kitty?), you just find the k most similar instances in your bank of examples and let them vote it out. Four of the five most-similar things in your example set are kitties? Alright, we'll call the new one a kitty. You have to tune k as a parameter to work well with your dataset, of course, and you can get slightly more sophisticated by introducing weighted voting -- things that are less similar to the instance you're trying to classify are considered less important.

The remaining question, though -- how do you decide what counts as "similar"? Typically, you use some sort of distance metric (Euclidean or Manhattan, for example) -- plot all of your instances in some high-dimensional space and see what's close. What if some of your features are noisy or irrelevant, though? Well, you could do some feature selection and prune those features out. Worse! What if you have several informative features, but they happen to be on very different scales, such that distances in one overwhelm distances in another? Well, you could manually scale them until you get some good results...

This is starting to sound like maybe K-Nearest Neighbors isn't all that easy to use, out of the box.

This paper actually solves both of those cases. Goldberger et al harness the power of linear algebra and come up with a way to learn a projection -- just a matrix -- from the original feature space, where distance metrics might not be very useful for KNN, into a new feature space, where your distance metric does the right thing. In effect, this is the feature selection and the scaling, all in one go, and they do it in such a way as to minimize the Leave-One-Out error, all tuned for your particular data set.

That's kind of cool.

As an added bonus, if you restrict the transform to project into three or fewer dimensions (just make sure the matrix is the right shape, and you're good!), then the same algorithm produces what sounds like a very nice visualization of your data. Features that are informative in discriminating your classes will be stretched out, and instances in the same class will tend to clump -- otherwise, KNN wouldn't work very well.

Lovely paper, guys! Very well-written, clearly explained, and addresses a problem probably a lot of people have had. The only issue I can raise so far -- it's not clear how long it takes to learn the transformation. This might be a very slow process, and all we're given in the paper is something to the effect of "oh, just optimize this function and you're good..." ... the machine learning pros among us can probably just look at the formula and knock it out in a few lines of Matlab (or supposedly Lisp, if you're Charles Isbell), but I would've liked a little more discussion on the implementation side... maybe they posted some code somewhere.

Happy hacking :) alexr out!

brains 'n' balancing training data

- Martin points us to a nice article over on Developing Intelligence: 10 Important Differences Between Brains and Computers. Your computational metaphor just breaks down eventually, y'know? The brain is not very much like a Von Neumann computer. It's a lot squishier.

If building classifiers is your thing, you may be interested to take a look at these articles:

- Gustavo E. A. P. A. Batista , Ana L. C. Bazzan, and Maria Carolina Monard: Balancing Training Data for Automated Annotation of Keywords: a Case Study.
Three researchers, seven middle names, one novel technique for building balanced data sets out of unbalanced ones for training classifiers: generate new instances of your minority class by interpolating between examples actually in your dataset. I'm still trying to decide whether this approach should work for the general case -- does it make too many assumptions about the shape of the space? Particularly: can you arbitrarily draw lines (in higher-dimensional space) between positive instances? What if there are negative instances between those two? Which dimensions do you look at first, and how is this better than just adding some noise or weighting positive examples higher? (is that last option the same as simply counting them several times?)

- Foster Provost: Machine Learning from Imbalanced Data Sets 101.
A basic overview of the problem, examining the motivation for building classifiers at all and some different approaches to sampling. The award for Best Name Ever goes to Dr. Foster Provost.

Programmatic poetry: oh noetry!

Automatic generation of texts has been on my mind for rather a while. Particularly, I've been thinking about poetry and the what characterizes it, in contrast to, say, technical manuals or want ads. Some (five?) years ago, my cohort Esther and I had set at the generation problem from an ontology standpoint, trying to figure out what it would take to get thematic relationships into an automatic poem. We didn't get very far, probably because at that point my first instinct was to code everything from scratch in C!

Anyway, it turns out that there are non-me people interested in this sort of thing, and the ever-helpful Graham has pointed out a bunch of interesting things happening in the field!

- The prosthetic imagination is a blog by a one Jim Carpenter, who's been working on Erica T. Carter (aka "the electronic text composition project", mentioned on GrandTextAuto here), which uses probabilistic grammars to generate free verse poems. I think the output is pretty convincing ("convincingly what?"); according to Mr. Carpenter, it's rather unnerving to readers who've been informed that they were composed by machine.

It's interesting how people react, when confronted with "creativity" from a non-human source; one is reminded of Douglas Hofstadter's surprising reaction to David Cope's lovely work with algorithmic music composition, which makes music, in a sense, in the style of other composers.

I'll have to read more, but I'm not entirely sure, if it's just using hierarchical grammars, how Erica is different from The Postmodernism Generator (the best-known use of the world-famous dada engine)... but I'll report back on this later.

- There is an Electronic Poetry Center at Buffalo. Interesting!

- Gnoetry is another system out there, and a very prolific one at that, apparently connected to this super-fascinating Beard of Bees publishing group. Language is a prosthesis of an ancient neuro-chemical regime; but now the chemical author is dead. Gnoetry places language at a remove from its typical sources: pre-conscious governance, psycho-historical flux, conscious-mind narration. YES. I will be getting in contact with these guys.

- At upenn, they have a series of readings, M^<4|\3, with all sorts of "literary uses of technology" things going on, including, next week, Flarf poetry (!) .

- Speaking of literary uses of technology, the GTR Language Workbench looks like something between Eclipse and a word processor... I'm not quite sure what to make of it yet.

I'm all excited. Let's get hacking.

Mapping and reducing is like popping and locking for programmers

If you don't read Lambda the Ultimate, that's quite alright. But fairly often over there, you find a link to Why Functional Programming Matters, by John Hughes. Recently, I decided to sit down and actually read it. It's mind-expanding!

Previously, I'd thought about mapping functions onto lists as an operational thing, a set of steps to complete, but that's not the cleanest way to think about it. Mapping is actually a special case of "reduce", an operation where you just go through and replace the all the "cons" functions in a list expression with something else, then evaluate the expression again. "map" functions have a cons in the function they're reducing with, so the end result is another list.

For example: you might write, in lisp: "(mapcar #'(lambda(x) (* x 2)) '(1 2 3 4))", yielding (2 4 6 8).. and you might think of that procedurally... but a map is just a reduce where "cons composed with the mapped function" replaces every "cons". Append can be written similarly; it's all essentially just replacement, function composition and evaluation. The paper also goes into beautiful issues like lazy evaluation (the author says that if he wrote the paper now, the examples would be in Haskell!) and continues to do some lovely examples, some numerical and one very close to our heart: a bot that plays tic-tac-toe, optimally, with pruned game trees.

Years ago, Kurt Eiselt told me that the future of computing was going to be functional languages on very-parallel hardware; functional languages, at least in principle, make synchronization easier by limiting or removing-altogether side effects. (although reconciling this idea with stateful, event-driven end-user applications is another issue!) To an extent, it looks like he was right, and the future is here! MapReduce is the method Google is using to crunch super-giant datasets with enormously parallel clusters. It's not just for functional languages, of course, but the idea is there.

rapid-feedback poetry and lisp environments

I think, ultimately, TEB is going to want to be less of a fully automated thing and more of a computer-aided composition tool for poetry. Or maybe it'd be better to think of it as a generator, with a human in the loop. Something that would let you get really rapid feedback and come up with suggestions. It would let you build poetry by search, recognizing what you like and what you don't like. And it'll keep versioning information...

Hey, speaking of development environments! On Lemonodor, I just found out that there's an Eclipse plugin for writing Lisp called Cusp. It uses SBCL and swank, like all right-thinking lispers, letting you do SLIME-like things without Emacs -- SLIME being the currently en-vogue common lisp development environment, and swank being the backend. There's a similar project out there that I've been watching too -- Slim-Vim, which is an attempt to make that same swank code work with vim. (the mailing list has been a little quiet, but it might pick up steam again)

Genetic algorithms for Dr. Mario Strategy!

It turns out that one Paul Kuliniewicz has decided to build an AI to play Dr. Mario -- or more accurately, to learn to play Dr. Mario and then play it, using, ironically, genetic algorithms. It's called Wallace, and it builds up and breeds different strategies for pushing pills around. This seems like a pretty good domain -- and I suppose puzzle games of this sort are in general... I wonder if anybody's done something like this for Tetris? Other real-time puzzle games?

The interesting thing about this -- he's hooked his evaluation function for evolutionary candidates into the NES emulator. Pretty clever stuff!

"Here, lemme take a Pikachu..."

So say that you want to pepper your speech with non-sequitur references to some particular topic -- like whenever you use a string of words that rhymes with the name of a Pokémon name, replace that string with the name of said Pokémon.

That wouldn't be that hard -- there's a pretty happenin' metric for finding rhymes, ready to go.

So you'd just have to have a list of the words for the domain you want to substitute in, make sure that you have phonetic descriptions of each of them (Bradley Buda's rhyme metric uses the CMU Pronouncing Dictionary's format)... then run through your input text searching for substrings that rhyme with words in your list with a score over some particular threshold. And hilarity ensues.

A similar technique could be used for generating phrases like "my feet are staying!" for "auf wiedersehen!" -- you could something hill-climbing-like (with a parser in the loop, so as to try to maintain grammaticality) to substitute out common phrases...

The only problem is -- what rhymes with "Psyduck"?

More on the horoscope remix project...

So my plan so far for remixing horoscopes doesn't seem to be going so well. It went like this:

- Take in the text or texts to be mixed and tag them, so you know what every word's part of speech is.
- Shuffle all the words together randomly.
- Do something like simulated annealing to hillclimb towards a more sensible output text: at every step, swap two words somewhere in the shuffled text, and keep the swap if we think the series of words that it would produce is more likely (as determined by looking at our transition-probability model) than the previous series of three words in that area -- and sometimes make bad choices, probabilistically, to avoid getting stuck in local maxima. Now our transition-probability model works in terms of parts of speech ("tags", to those hip to the NLP lingo), and we learned those tables from tagging a previous corpus...

I'm not quite sure why this isn't working. It might be that using trigram transition probabilities (on the tags) doesn't capture enough structure to get coherent sentences? Because this method doesn't produce coherent sentences very well.

I'm thinking about what else I could do. Perhaps I could use longer n-grams in the model -- or maybe I should look to use a parser, and reward the hill-climbing when it produces longer and longer parsable sentence chunks. The other possibility is that maybe my tagger isn't as accurate as I think it is... it could be mislabeling more words than expected (and it's expected to mislabel a bunch of them.)

The problem is totally not that I'm training my models on James Joyce.

NLTK and generating horoscopes

Have I mentioned that NLTK is the hotness? NLTK is the hotness, particularly if you want to do your language-y things in Python.

It's intended for educational use, but it has what you need, and it lets you compare different algorithms for tokenizing, tagging, and parsing chunks of text, very pluggably. The API is nice too -- you can very easily tell taggers (the parts of your program that decide which part-of-speech a given word is) to make calls to one another in case they can't figure out the right tag independently.

There's of course the OpenNLP tools in Java, but they don't seem near as quick or awesome.

Soon: using transition probabilities on parts-of-speech to shuffle chunks of text and generate new moderately-sensible horoscopes? Yes! (also: this should be helpful in the long term for my automatic poetry project, which will eventually be more Python-and-ML than Lisp-and-formal-rules)

What I've been working on: fixing your tiny keyboard typos!

Alex Rudnick and Sunyoung Kim: Towards automatic error correction for mini-QWERTY input. October 2006, for Thad Starner's CS 7470.

Presentation slides here: (as a PDF)

Lisp is still really pretty.

So I'm building some decision trees for a project I've been working on -- this automatic typo correction for tiny blackberry-style keyboards. The motivation for this is pretty obvious -- we have to decide when to do the correction and when to let the user type what they're typing!

I'm going through some code I'd had for an earlier project, this one done in Common Lisp. And I've been really excited about Python recently -- but man, Lisp is so nice for data structures. There's so little punctuation for building things. I mean, goodness -- it's as if the language was made for dealing with recursively nested things. I'm a little reluctant to translate this stuff -- why am I not just using CL, again? ...

Oh yeah, because I need to make it talk to other programs.

Also! Roughly the hippest thing ever is the __call__ construct on Python classes. If an object has a __call__() method defined on it, then for object foo, you just go foo(arg), and it does its Pre-Defined Thing. Check it out! ("emulating callable objects")