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"

quals writeup: Tree Transducers, Machine Translation, and Cross-Language Divergences

I hope it's not too pretentious to put things I'm writing for my phd qualifiers on arXiv. I think arXiv is really exciting, by the way. Leak your preprints there! Also pretty exciting: tree transducers for machine translation.

Abstract:

Tree transducers are formal automata that transform trees into other trees. Many varieties of tree transducers have been explored in the automata theory literature, and more recently, in the machine translation literature. In this paper I review T and xT transducers, situate them among related formalisms, and show how they can be used to implement rules for machine translation systems that cover all of the cross-language structural divergences described in Bonnie Dorr's influential article on the topic. I also present an implementation of xT transduction, suitable and convenient for experimenting with translation rules.

Paper! http://arxiv.org/abs/1203.6136

Software! http://github.com/alexrudnick/kurt

securing your MoinMoin wiki

I really like MoinMoin; it's straightforward, it's Pythonic, it's got WikiWords. Great! I've been keeping a bunch of notes on one.

The IU Computational Linguistics group had an aging MoinMoin too, but most of the edits and new accounts were spam. I suspect the edits were being done by humans too, because they were pretty good at fitting into the markup of existing pages.

We replaced it with a new install (here it is) and make it a bit more secure. We disallowed anonymous edits, and made it so that you can't just arbitrarily create accounts, which took a code change. I added the "if not request.user.isSuperUser() ..." block (suggested here) to MoinMoin/action/newaccount.py. The rest of the changes described on that page aren't necessary -- just make it refuse new account requests.

Then it occurred to me: spammers have probably been trying to spam my personal wiki too! I checked: there were about a hundred spam accounts; a new one every day or two. My Moin was allowing arbitrary account creation, but they were all useless because only I could edit pages!

So in the interest of discouraging future webcrap, let me issue a warning: CyrilleVincent, SabaFaulkner, CasinoBonus, life insurance quotes, and ChickyBowen -- I'm coming for you. And you'd best sleep with one eye open, paydayloansuk214. If that's your real name.

Python tip: 3.2 adds a memoization decorator

This is a really handy thing to have around, in case you've got expensive computations that you want done more than once. I've written a clumsier version of this myself, once or twice -- but it makes sense to have in the standard library!

http://docs.python.org/py3k/library/functools.html#functools.lru_cache

There's some other neat stuff in the functools package too: currying and reducing. Pretty slick!

Python tip: dir() with no arguments

If you do Python, you probably knew that you can ask an object what it has on it by saying dir(theobject).

I just found this out, though: you can also say dir() with no arguments to find out everything that's in your current namespace. No more losing temporary variables that you forgot about earlier in the repl. It works for finding out which modules you have loaded, too. Holy cow.

>>> dir()
['__builtins__', '__doc__', '__name__', '__package__']
>>> x = "this string is amazing"
>>> dir()
['__builtins__', '__doc__', '__name__', '__package__', 'x']

May I present: kompressr

kompressr: make text shorter harnessing the power of acronyms (MTSHTPOA)

Try it out, let me know what you think and if it breaks :) Should be useful for making long papers shorter, by automatically extracting acronyms and using them wherever possible.

Public beta!^tm

(running on App Engine, with NLTK!)

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!

Python generator expressions

I just found out about this: Python has a really concise way to make new generators.

It looks like a list comprehension, just without the brackets. Before I knew about this feature, the code I was reading looked pretty mysterious.

There are some nice examples of cases where you might want to use this sort of thing in the relevant PEP. Especially pleasant uses from the PEP include passing a generator to the dictionary constructor, like so:
d = dict( (k, func(k)) for k in keylist)

... and, useful for me personally, getting the set of words in a file, all in one go:
s = set(word for line in f for word in line.split())

Good to know!

constraint programming in Python

You may be familiar with constraint programming, an approach where, instead of describing how to solve a problem, you describe what a possible solution looks like, and let a generalized solver find possible solutions. This is the sort of thing you might do with Prolog, Oz, or any number of libraries for your favorite programming language.

If your favorite programming language is Python, there are at least two different libraries for this approach! Unfortunately, they're both called "python-constraint"; this led to some confusion on my part. Here they are:

logilab-constraint. This is packaged in Debian/Ubuntu as "python-constraint". It's put out by the French company LogiLab, who contribute a bunch of Free Software useful for doing AI-flavored things. Their HMM library is pretty slick too.

python-constraint is a package by Gustavo Niemeyer, and it's got this really nice tutorial.

I mention these because my new research group is using this latter one to build a dependency grammar system based on Ralph Debusmann's XDG.

And more about that, as we get to it :)

HOWTO not get "/usr/bin/env: bad interpreter"

If you get this:

bash: ./my-script.py: /usr/bin/env: bad interpreter: Permission denied

The partition your script lives on may be mounted with the "user" option set. "user" implies "noexec" (see the manpage for "mount"), which is going to keep you from running executables. And while running a binary executable from this kind of partition fails more clearly, trying to run a script with a shebang gives you this more confusing error message.

To fix! Add "exec" after your "user" flag in /etc/fstab. (again, see "man mount").

Lisp insights from learning Logo

So I was just writing a simple recursive procedure in Logo. I wanted to go down a list, cons up a new list, and return the empty list when I get to the end.

My first pass, once I found out how to return something from a function (Logo procedures aren't expressions -- you have to explicitly return) had a line like this:

if (stacks = []) (output [])

Running the procedure gave me the helpful error message:
output didn't output to if in astep
[if (stacks = [] ) (output [] )]

Pardon?

When I remembered that Logo's "if" wants a list of instructions, it clicked with my new nugget of knowledge that literal lists are quoted in Logo. Then I understood what was going on: this "if" is neither a macro (like in Scheme, or most languages) nor lazily evaluated (like Haskell). It's a regular function, but one that expects quoted code to evaluate on demand at runtime. Rubyists and Smalltalkers: this is something like how an if block works for you, yes?

Here's an analogy into Python, for the non-Lispers out there:

def myIf(tf, truecode, falsecode):
  code = {True : truecode, False : falsecode}
  return eval(code[tf])

>>> myIf(0 == 1, "'it was ' + 'true'", "'it was not true'.upper()")
'IT WAS NOT TRUE'

>>> myIf(0 == 0, "'it was ' + 'true'", "'it was not true'.upper()")
'it was true'

Also, apparently Logo in general has dynamic scope -- which shouldn't surprise me, since lexical scope is relatively new in Lisp. And Berkeley Logo in particular has macros. Maybe my little compiler project is going to be harder than I expected. Honestly, I was imagining I'd be done if I could just parse it, do some simple transformations on the tree and spit JavaScript.

sudokudlx: Automatic Sudoku Solving with Dancing Links

In case I hadn't shown you yet, here's my Python implementation of a Dancing Links sudoku solver, on appengine!

http://sudokudlx.appspot.com/

Also, I've written a bit about how to use Dancing Links (DLX) to solve sudoku puzzles. Soon, I'll write up how to implement DLX.

plats is Swedish for "locale".

My first pass for solving the problem from a few days ago is now live on appengine.

Check it out: http://plats.appspot.com

Just include a script in your page and you get a variable or a meta tag (for GWT apps) to tell you which locale you should be in. Details here.

reconsidering applets

Applets are a really tempting idea. The JVM is a serious piece of machinery; despite its startup time, once it gets rolling, Java can go fast indeed. And although it hasn't been very widely used, applets and javascript have had a means of calling back and forth for quite a while. It's called LiveConnect. (although LiveConnect may be replaced at some point...)

So, a beefy, fast VM that runs inside the browser, coupled with a nice web UI, and no manual installs for your users -- big win? Maybe! On considering this, one of my first thoughts was to put Jython into an applet and build something akin to JES -- a little Jython IDE in the browser! The kids would love it! So I set out to make this happen, or at least build a proof-of-concept.

I ran into a serious snag, though -- the Jython interpreter works by compiling to bytecode and bringing it up with the class loader, the latter of which applets aren't typically allowed to do. Special permission can be granted with a Java policy file, but that's a very high barrier to entry. It's certainly not the sort of thing a person might do on a public terminal. Signing the applets may also be an option -- but that's also a pain, and anecdotally, I think signed applets may not always get the same rights, cross-platform.

Once I understood the permissions issue, I did get a little Jython repl going -- it just hooks "eval" up to some javascript for output. Nothing fancy, but kind of satisfying. For now, though, it doesn't look like Jython IDEs are coming to the browser. Until we rewrite it to not use of the class loader. Or just use some more modern approach.

Some other people have had similar thoughts!

• Interactive Jython Console: this one, for the exact same reasons that mine does, requires a java policy file.
• the ruby-in-browser project. It does exactly pretty much what it sounds like it does, also by means of an applet and LiveConnect. Interestingly, JRuby doesn't seem to use the class loader, it just works! Check out the demo! [thanks for the heads-up, Lindsey Kuper!]

Penguin Parens: referenced by NLTK!

A while ago, I was working on remixing horoscopes and I gushed quite a bit about the lovely free Python NLP toolkit NLTK. And I was honored to get a comment from Steven Bird, one of the NLTK developers and an eminent natural language researcher.

It turns out that they quoted my blog post for the "Quotes" page. Aw :)

I'm checking out their circumstance again, so to speak -- and it's grown so much. They've got most of a textbook (free online!) put together. And the API is gigantic, so much code! Amazing. I'm going to have to dig back into it.

You get spoiled by languages with first-class functions

Earlier today, I needed to take a list of strings and grab all of them that end with ".html". Very simple task. My first thought is of course something like:

[fn for fn in fns if fn.endswith(".html")]

Or even:
filter( lambda x: x.endsWith(".html"), fns)

Or the equivalent Lisp. Y'know, with "loop" and "collect". (Common Lisp has, as they say, the Cadillac of loop syntax)

Or something to that extent. But then I remembered that I was writing in Java, and I ended up writing a for-loop. There's no clean, idiomatic way to say that in Java, is there? Do you have to build up the list procedurally? ...

java 6: apparently even less of a loss than java 5!

Java 6. It's so hot right now. Java 6.

Well, I'm excited anyway. The new Scripting API provides a standard interface for embedding other languages in Java and making calls between the two. See if there's already a project to handle your favorite language here -- there probably is, unless you like Common Lisp. There's even a mechanism for manipulating namespaces in the embedded language, pretty snappy.

Apparently recent releases of Jython already have hooks to support the new API. Maybe the next version of JES should be rewritten with that in mind, say once Jython 2.2 is stable. And perhaps we'll see ABCL ported to the new standard...

Also in Java 6, the built-in support for splash screens is kinda cute. And they're saying that the whole shebang is faster and prettier. Good job, guys!

tools for blogging and reading

I had an idea for a tool today, one to keep track of links that you want to blog about, assuming you keep a buffer of a few links hanging around like I do. Usually, I have a bookmark folder set aside for the next batch of links, but it might be nice to have a special command that would let you right-click on a link and save it to somewhere. Later on, you'll be able to paste back your links (maybe with HTML link code) into arbitrary text boxes using another context-menu command. This probably wants to be a Firefox extension.

Graham suggests that this would be better with online storage -- it could sync up with your del.icio.us bookmarks and keep track of what you've already blogged about. Perhaps someday soon I'll be cool enough to use del.icio.us.

Speaking of reading things on the web and managing one's reading -- please allow me to direct your attention to BibDesk and Skim, a pair of apps for the Mac designed with your reading pleasure in mind. The first is a bibliography manager that works with BibTeX format and has a lovely UI and lets you drag references around and whatnot, and the latter is for reading, highlighting, and annotating your papers, which is traditionally pretty difficult with a PDF.

The downside of these is that they're Cocoa apps and Mac-only, but they're pretty much what I'll want to build when I get around to putting together that cross-platform Python paper manager thing I've been thinking about...

list comprehensions!

List comprehensions. I've been a fan of these for a while, but I'd like to share:

tenpercent = len(lines) / 10
testset = random.sample(lines, tenpercent)
trainingset = [line for line in lines if line not in testset]

Python makes me warm and fuzzy on the inside. Also, random.sample() is pretty sexy!

python generators and more live coding music!

I just found out about the yield python keyword, which lets you produce generator functions. This came up, in a practical context, because I wanted a clean way to get n items at a time out of a list, and the Python Cookbook approach uses generator functions. They let you build an object that essentially contains a closure of the current environment, which can be iterated on. Sort of like lazy lists! Of course, the same behavior could be done with C-style static variables, but this is really pretty.

- yield keyword from the Python docs
- a discussion of generator functions over at IBM Developerworks.

Also! Brett alerts us to Impromptu, another live coding environment for making music and stuff! From their site:

Impromptu is an OSX programming environment for composers, sound artists, VJ's and graphic artists with an interest in live or interactive programming. Impromptu is a Scheme language environment, a member of the Lisp family of languages.