corpus sifter - tool for building paired data/text corpora

Here's a small webapp I wrote yesterday. Since the app (as I envisoned it) was fairly simple, I figured I would invest some time to learn how to write web stuff in Haskell. I went with the Happstack framework just because it's the most well known.

Sales pitch

I call the app "corpus sifter". It could use a nicer name. The code is BSD licensed and I'm willing to stick the Darcs repository up somewhere, maybe even upload it to hackage if anybody is interested, but I doubt it's useful enough to justify such actions.

The scenario behind this application is as follows:

• You have some pieces of structured data
• Using a search engine, you have retrieved a text file for each piece of the data
• You don't know if the data you retrieved really corresponds to the data; there may be some automatic ways of finding out, but you need to spend a little time scrutinising the data to find out

Solution? Well, you're stuck with manually sifting through the data, so you might as well make this manual process as quick and painless as possible. To this end, we present the data and text file side-by-side, and three buttons "good", "bad" and "unsure". Clicking on one of these buttons moves the pair to the corresponding "good/bad/unsure" bin from the new bin; it also presents you with another item to classify.

Two features of this approach is that is (a) fairly general and (b) simple/robust (hopefully).

generality

There is nothing in corpus sifter that is specific to the corpus in question. The data must be represented as a JSON object (which corpus sifter will render as an HTML table), and the text will just be systematically dumped out as raw text (these are wikipedia entries that I'm using, but you may have other things in mind).

simplicity/robustness?

Part of corpus sifter's design is to account for incremental corpus construction. When you begin building the corpus, you may not exactly know all the best ways of (i) sifting through it or (ii) searching for texts. So over time, you may want to revise your data. Corpus sifter supports this by adopting a very simple and stupid model of processing: the bins are represented as directories, and moving items from one bin to another consists of literally moving them on the file system.

If you change your mind about a bin (say, you hit a back button), corpus sifter will notice and move the data pair from the corresponding bin.

If over time you add more data to the corpus that you want to sift through, just dump it in the "new" directory.

In a future version of corpus sifter (maybe tomorrow?), I plan to add a feature that lets it notice that you have put something in the "new" bin which already has been classified. This would account for cases where you have new, hopefully better search results. What the tool would hypothetically do is to create some sort of backup directory and move the old data from its bin to this directory. This will be handy for cases where you incrementally refine your search methodology, leading to different results for files that you have already seen. For example, working with Wikipedia entries, I've discovered better and better ways of coping with disambiguation pages, but I need to find some graceful solution for merging these new results in with my old sifted corpus. I certainly wouldn't want to have two copies of my data lying around!

Implementation notes

You can count on me to extol the virtues of Haskell programming at any slightest opportunity. Today, the features I'm going to gush about are common among many functional programming languages (Haskell, ML-ish languages and Scala). These features are algebraic data types and pattern matching.

How Haskell helped me here is to develop a simple and generic solution for rendering any JSON object as HTML. The code is as follows (renderer in 25 lines of Haskell, entire app in about 200 lines):

jsonToHtml JSNull = noHtml
jsonToHtml (JSBool b) = stringToHtml (show b)
jsonToHtml (JSRational float r) =
  stringToHtml $ if denominator r == 1 then show (numerator r)
                                       else show (fromRational r :: Float)
jsonToHtml (JSString js) =
 case fromJSString js of
   u@('h':'t':'t':'p':':':'/':'/':u') -> anchor (abbreviate u') ! [ href u ]
   s -> stringToHtml s
 where
   abbreviate = stringToHtml . (++ "...") . take 13
jsonToHtml (JSArray xs) = unordList (map jsonToHtml xs)
jsonToHtml (JSObject o) = jTable . concatHtml . altMap dark light . map mkRow $ fromJSObject o
 where
  mkRow  (k,v) = tr $ concatHtml [ td (stringToHtml k), td (jsonToHtml v) ]
  dark  = (! [ theclass "dark" ])
  light = (! [ theclass "light" ])
  jTable x = table x ! [ theclass "json" ]

-- | map on every other element
altMap _ _ []  = []
altMap f1 f2 [x] = [ f1 x ]
altMap f1 f2 (x1:x2:xs) = f1 x1 : f2 x2 : altMap f1 f2 xs

The basic idea is that JSON strings are escaped and turned into straight HTML, numbers are represented in decimal notation (where appropriate), lists are rendered as bullets (ul tag) and here's where it gets fun, objects (key-value pairs) as tables. The nice thing here for me is that I didn't have to go read a bunch of specs to know what I had to do. Since the author of the json library chose a nice simple sum type representation for JSON objects, I could simply write a function to pattern-match on each one of the cases individually...

These key is that algebraic types helped me to think about the problem because they (i) divided the problem into cases which (ii) they made very readily apparent and (iii) which the compiler could then check that I have exhaustively explored all the cases [eg, did you consider boolean values in JSON? what about the null case?]. Furthermore, the recursion on the the types (JSON objects contain JSON objects) was very simple to deal with as just a straightforward recursive function.

Pattern matching and algebraic data types... this kind of stuff makes me really reluctant to give up statically-typed functional programming languages. Of course, there must be other ways to solve this with other languages' tools; if this would have been easier in some other language, give me a shout in the comments.

incremental development + resource constraints = messiness

Say you've got a pipeline that searches for Wikipedia articles, retrieves them and maybe does some post-processing on them.

You later on decide that you need to do some extra work on the results, say parse the disambiguation pages, retrieve the disambiguation results and then do some post-processing on them.

Now, the pipeline takes a long time or a lot of resources to run, so you definitely do not want to run it again. You've already got your WP articles; no point fetching them again. If you had had the foresight to plan for the disambiguation stuff from the beginning, then it would all be part of one nice happy pipeline, but you didn't, tough luck.

So what do you do? You develop a separate post-processing script that operates over the results of your first processing step.

... and?

You've just created a mess. Now you've got yet another script in your pipeline that you need to tell somebody to run (editing your README file), or that you need to augment your pipeline with for future use (which you are not motivated to do because it does not solve any immediate problems). Not only that, you're faced with the dilemma of whether or not you should keep both the original data fetched from the pipeline, plus the additional disambiguation results [for future tracking/reproducibility]; or if you should just mash them all together [for simplicity].

This is the kind of organic incremental growth that leads to a general feeling of sprawl and out of controlness. I don't foresee any solutions.

• One could plan better and try to get things right the first time, but that's mostly like saying one should just be more intelligent, and capable of anticipating changes down the road... "Be more clever" is just not acceptable answer.
• One could use more pilot studies to flesh out as much of the toolchain as possible on small amounts of data (which eliminates the resource constraint problem). This is probably a good idea, but it only goes so far, in the sense that you sometimes need to work with large amounts of data before you can become aware of the problems that lead you to augment your pipeline.
  
• Or maybe one could design processes to easily accommodate these kinds of incremental changes in a tidy manner.

I haven't figured out the latter bit yet, and so I've got yet another Perl script in my burgeoning toolchain that I won't know what to do with three months from now.

subsumption

I mentioned that I tend to have a lot of difficulty with polarities. By this I mean, I tend to get left and right confused, along with true/false, plus/minus, subsumes/is subsumed by.

The good news is that I think I have finally figured out why I keep tripping over subsumption, as I have done ever since I encountered the concept in a beginner's Description Logic course.

In short, we say G ⊑ S (G subsumes S) more or less if G is a subset of S, right?

The reason I think this gives me difficulty is that there's a kind of subtle "contradiction" that my very sloppy and stupid brain simply cannot handle. It goes like this:

• G is a subset of S, so G is SMALLER than S, gotcha
• G is more general than S, so G is BIGGER than S, wait, WTF?

So the problem is that "G subsumes S" conjures up a mental image of a massive blob-like G swallowing up a helpless little S. I know the mental image isn't appropriate here, but I can't help it! You say the word, and I get the blob.

Of course, if I can keep my thinking cap on for long enough, I realise that the way out of this is that to remember that G is more general than S only by virtue of containing less stuff than it. Smaller, so more general.

But I think I'm the kind of guy that does NOT reason about things so much as trying to bash them into primitive mental constructs like "smaller" and "bigger". Hence the repeated run-ins with confusion about subsumption. How did I fool these people into giving me a fancy degree?

fractional B3

I think the PyCoLi B3 scorer would be better using the Python fractions module. No point messing around with floating point when we don't actually need it. If this works, I may send a patch.

more pipeline hacking

There's a constant tension between wanting to make everything work as a single "go" operation and having things be broken down into nice interchangeable modules that you can later isolate. When building the "go" button, you don't always have a good idea what the modules are (well maybe you do; I certainly don't) and you only discover them after the fact. So say your big go button does jobs A B C and D. And later on, you discover that you need to factor out components B and C into a separate standalone utility.

Now what?

Now you're stuck: you need to get the job done NOW so you probably create the module by doing some copy+paste programming. No time to think and do the job right, just get in done, go. But of course you're just creating more misery for down the road because in doing copy+paste programming you've created duplication and we know the lesson from being bitten over and over and over by it:

duplication is the root of all evil
But what else are you going do? Well you could take your time to do things right, but that's not necessarily the right answer either. First, there's always deadlines looming. Second, sometimes the only way to discover what the "doing things right" means involves doing them wrong a few zillion times until your brain gets the idea.

Right, let's get to it...

Then later on we're going to have to address this most heinous duplication between the B+C mini-go operation and the big go operation. I'm sorry I keep writing about the same thing over and over again; it's just that I haven't found the words to say this concisely and precisely yet. I haven't figured out how to drive straight to the heart of the matter.

tidy tidy tidy

Now that I've wasted a good two weeks trying to reproduce something that should have taken me less than half an hour, I feel that the general attitude of fanatical tidiness is not wholly stupid.

Don't rush about; you'll just waste more time that way.

I'm taking a week out to sit down and re-arrange this ENLG stuff and package it up nice with an installer, sensible directories, etc. Just using the latest accumulated experience from the genchal work and the trip to Nancy.

I figure that SOMEDAY in the future, future-us will be grateful.

reproduced results!

Hurrah! I've been able to reproduce the results from our paper last year. That's a good TWO WEEKS of work lost to poor methodology.

OK, so what do we learn from this?

Lay directories out sensibly

I should do the things I mentioned in my series of posts about toolchains, particularly the one about directories. Part of the mess was due to the fact that the paper last year was before I wrote that toolchains post, and I was still doing things in a pretty random way.

Embrace change

This is actually me attempting to defend something which made my life more difficult these two weeks. Part of the difficulty in reproducing things is that I had started shifting to a less random way of doing things, rationalising the names I gave to systems and directories, rearranging tree structures. This made life pretty awful because I couldn't just whip out a graphical diff and say "ah, that bit is different with that other bit"; I had to write a bunch of stupid scripts to rename things from the old way to the new way. So that cost me a lot of time and grief, but then what can you do?

In my opinion, the wrong answer is to say "don't change, because stability is at a premium." The problem with that answer is that when you fail to change things, you propagate unsustainable practices that just cause you increasing amounts of pain down the road. If you're balancing on a slippery rock standing on your big left toe and sticking your other leg in the air, staying vewy still isn't actually going to give you any stability. The way to get the stability is to step off the stupid rock and put both feet on the ground. So if you're doing things a stupid way, you HAVE to change them or suffer the consequences. Change to gain stability. Of course, change has a cost which I've definitely been paying a lot of; but the cost of changing must also be put into perspective against the cost of NOT changing.

Archive and date

I was lucky because I found somewhere a directory labeled delete-after-2009-11/eacl-2008-09-29 that basically contained everything I needed to contain the old stuff.

As I mentioned in my last post: two digits for the conference, four digits for the archival date. It matters.

Use stow; use /usr/local

This is just expanding on sensible directory layout. If you're going to be working with a bunch of third party tools like GIZA++, SRILM, and moses; make sure you install them with stow (whenever possible). The idea is that you can install them into directories like:

• /usr/local/stow/gizapp-1.0.3
• /usr/local/stow/gizapp-1.0.4
• /usr/local/stow/moses-2008-07-11
• /usr/local/stow/moses-2009-02-04

What this lets you do is selectively activate and deactivate different versions of packages. If you do cd /usr/local/stow; stow gizapp-1.0.4, this will dumbly create symbolic links from everything in /usr/local/stow/gizapp-1.0.4 to the equivalent location in /usr/local. If you do then do cd /usr/local/stow; stow -D gizapp-1.0.4, this will delete the symbolic links, making it possible for you to swap a different version in.

Now some tools will not have an installation method, for example, SRILM. I would not bother trying to shoehorn one into them. Just stick them under (for example). /usr/local/SRILM-1.5.5.

This sounds like a stupid detail, but hey, I just wasted two weeks, partly because I didn't have any idea what all the versions of all the crap I was using because I didn't have a consistent methodology for installing such unpackaged dependencies. They were either going in my home directory, in some local space on the hard drive, in /opt. Huge mess. Attention to detail matters.

archiving and dates

I'm finding it increasingly necessary to build up a repertoire of tips and tricks solely to cope with the fact that I get confused easily.

Here's the latest addition.

Background: I have an archiving strategy which is based on calendar years. So, I have this huge directory called ARCHIVE which is further broken down into directories by homebase/year. So these four directories track the transition from 2007 to 2009 and from my LORIA life to my Brighton life:

• 2007-loria
• 2007-brighton
• 2008-brighton
• 2009-brighton

This all works very well except for one detail : I always trip over the fact that work for conferences that take place one year often happens the year before. Either I can't find something because my expectations about where they should be are incorrect, or if they are correct because past-me had misfiled it. A paper for ACL 2009 should really be archived in the 2008 directory because that's when you did the work (this stupid-looking detail really matters if you EVER need to reproduce things, which you do).

So how do you avoid accidentally misfiling a conference-related project in the wrong directory? Two digit years.

Instead of calling the data eacl2009-stuff, I now call it eacl09-stuff, and if I want to back it up and pin it down to a specific date, I can use an ISO style date: eacl09-stuff-2008-07-04. The two digit year is for the conference, whereas the 4 digit one is for the actual work year.

(Note that this is orthogonal to the revision control issue. Of course you should be using revision control, but [a] sometimes your data are just fricking huge and you don't want to revision control them (no revisions) [b] you don't always remember to track all the right files and [c] it's super convenient to have snapshots, eg. from when you submitted the paper).

So that's the big discovery du jour: two digits for labelling conferences, four digits for labeling dates.

And people wonder why I never get any real work done...

fiddly nonsense

An example of the sort of stuff I hate dealing with:

Here is the training data. Except no, you shouldn't use all of them because the past experiment in 2002 (for whatever reason) only made use of a certain subset. So you'll have to remember to partition your data into the 2002 stuff and the rest of it. And of course, you only discover it after the fact, so you'll have to write some post-processing scripts for your evaluation procedure to separate the two.

And of course, nobody really remembers what happens. The data is organised into directories X Y Z,, and you'll have to merge it with this other variant of the data which is in one flat space with file names f.x, f.y, f.z. And then you want 5 fold cross validation, and you also want to remember that your training set must be subdivided into into a training and development set.

Oh now it's 2009 and for whatever reason, you're not getting identical output to 2008. What happened? What did you [Eric] change between 2008 and 2009 (you and your attempt to tidy things up once and for all)? Why do you have 16 different variants of the data (all various attempts at picking out the right subset of the data to match the 2002 conditions).

And of course for all my griping, I just make matters worse because I don't follow good methodology either, don't sit down and figure out how to avoid making a mess out if. If I have 16 folders, it's because 9 of them are ones I created in the process of trying to wade my way through the mess. Fiddly nonsense just grows.

Here's my directory:

• Data
• data-bob
• data-intersect-BobHybrid-NoEmpties
• data-intersect-BobHybrid-NoEmpties-split-train-dev
• data-segments
  

Oh, and did I mention that there's also a variant of this tree on the fast machine? The WTF is entirely of my own devising. What was I thinking?! [I was thinking "nevermind about trying to figure out how to do this cleanly; just get the job done because the deadline is looming"].

I guess there's a certain quality to the nature of work. If I'm just turning arbitrary knobs on a black box without any real rhyme or reason (what happens if I enable factoring, what happens if I twiddle my lambdas, etc)... but it's sort of inevitable, this endless meaningless self-inflicted variation. Just variation and more variation, knobs to turn, variables to twiddle. I need to work out how to stop this madness, how to arrest this spiral of silly variants.

Never taking shortcuts would be nice. Having a strict separation between raw source data and automatically compiled data would be another. Sunsetting things so that you know to get rid of them later on would be good. Must find a way out.

mediawiki parsing

It's taken me a week or so to settle in, but here I am back in Brighton.

I've mostly been working personal stuff: thinking about the future, clearing out my Inbox-es, investigating new ways of keeping myself organised (xmonad + mutt + hsgtd + iFolder, yeah!). Small differences like having your mailer (mutt) talk directly to your list of next actions (hsgtd) with a keystroke and have that list be automagically be synchronised in the background (iFolder) so that you're always viewing the same list wherever you are, with a tiling manager to keep mailer and todo lists in the same view (xmonad). When you get a sufficient number of little details right, magic happens. In any case, I feel a little better.

That's one of the reason why I still use all these old-fashioned command line tools. I can get really really picky about how things work. I want to use my favourite editor, Vim; want to use my favourite organisation methodology, GTD; etc. A fancy graphical tool may be good enough for most people, but if you find yourself in a niche (use vertical keyboard => vim for easier navigation), the Unix-y philosophy of small tools that do one job well and plug into other small tools is easiest.

mediawiki stuff (actual work)

Otherwise, I've also done a little work on improving the situation with the wikipedia mini-corpus. One discovery is that instead of talking to Mediawiki's api.php, I could instead talk to index.php and pass in a special parameter to expand all the templates. I'm not sure this is a good idea. On the one hand, it avoids me having to process all those stupid little templates. On the other hand, it turns a lot of nice high-level input into something rather gunkier. I'm going with the gunk for now as a matter of keeping it simple, but I could be well mistaken.

I've also hacked a little bit on the Mediawiki parser for Pandoc. Adding support for tables. I think the right approach to take to this Mediawiki parsing is to work on it in tiny little spurts lest I get bored and frustrated. The work is well worth it. Imagine having Mediawiki, the Wikipedia format in the quiver of formats supported by the Universal Converter Pandoc... it's like iconv for markup formats.

GenI 0.20 released

Here's the official announcement. Heading in the right direction. Not completely there yet, but APIs are getting simpler, documentation is getting written, things are getting clearer. GenI 0.20 is a nice little hop in the right direction... at least, I hope.

Gave my ENLG talk again.

Talked with one of my GenI users, which turned into a great rambling chat about everything and anything.

Nice way to end the trip. Goodbye, Nancy, merci and hello Brighton on Thursday.

fixed the unification bug!

Woo! That was making me pretty unhappy.

It wasn't the core unification algorithm that was at fault (phew!). It was just a simple matter of "oops, I forgot to propagate these replacement values" when doing successive unifications during adjunction. Of course the real problem is that we're doing unification in an overly manual and error-prone fashion. We need to stop doing that. The Prolog hackers are watching and laughing.

I don't think I really need to go as far as having a unification monad (or whatever). Simply replacing all my unify :: a -> a -> (Subst a , a) (yes, I'm fibbing with the types a bit) with unifyWith :: Subst a -> a -> a -> (Subst a, a) would be a step in the right direction. We'd still have to keep track of the new substitutions that pop out of it but at least this fixes the core stupid.

the wrap up that never wraps

Argh, mind spinning with things I want to do in my last few hours of GenI hacking time. Not really being very effective about this, just sort of darting around randomly.

morph progress

In a frenzy of refactoring last night, I've finally kicked the morphological realiser out of GenI and rejiggled the interactions between the two to be completely JSONified.

I still need to:

• print uninflected forms in the enriched output and for each form all the morphological realisations for it (this takes a bit of work actually, lots of cleaning up to do)
  
• output this stuff in geniserver

The pieces are all there, but I can't really work on it right now because there's not much time left and I still haven't looked at the unification bug

genimanual

For no good reason (probably because I was tired), I started trying to sweep up bits and pieces of the wiki into the LaTeX/Literate Haskell manual. I think I want there to be 4 kinds of documentation:

1. Wiki: walkthrough, FAQ, little user-driven notes
2. Manual: reference manual; not meant to be friendly, just complete
3. Literate GenI: still not sure how to do this right, but something that shows you the underlying implementation details but still on a somewhat high level
4. API

The situation is not less bad than it was before this month. For example, I've consolidated the description of the GenI formats (EBNF, etc) into the manual and really tidied the heck out of that module. So at least that bit looks somewhat reasonable. The main thrust of this work has been to clarify the distinctions between the four kinds of documentation, which means I now have a clearer idea of how to write for each context.

Remaining shortcomings:

• Basic flags not documented: http://trac.haskell.org/GenI/ticket/36
• Manual is in PDF only. Need something like Hevea or Latex2html to convert it
• Ugh, lots more...

the unification bug

I ought to spend the rest of this afternoon just looking at the unification bug. Fixing the morphology stuff would be great, but it's not a release blocker...

wrap-up 2

Spent this morning dithering over the future of GenI's relationship with lex2all. I think the right thing to do is just to merge parsing of CGM lexicons into geniconvert. There may be some code-duplication but the way I figure, one way or another *some* code is going to be duplicated and it's unlikely lex2all is going to use the GenI library to inherent its model of lexicons. So this is the simplemest way forward.

all done?

Otherwise, I think I'm done with all the items on my official TODO list, rah! This means I get to go play :-)

• decided we're dropping the random formula thing: it should just work once it's in the right format, so I'm ignoring it
  
• demo'ed the results of the OT-GenI integration and also the latest state of the Forge
• presented the idea of using virtual machine and a disk image so that future installation procedures can be tested on a clean machine
• advocated geni-users passing to moderate for unsubscribers only (that was easy :-))

Go play...

• Clean up interaction with the morphological realiser - I've now got GenI spitting out lemmata and features in JSON (got JSON-fever, sorry!) and expecting lists of lists of input back. There's still going to be some GenI-specific formats around, but basically anything that can't be expressed purely in idiomatic GenI is going to be JSON with some GenI thrown in (eg. for features). No more making up crappy Erician formats, but no need to subject myself to XML either. My hatred for XML is probably irrational, especially since I seem to be hitting the same kinds of nails with the same kind of hammer. Sue me.
• Fix the darn unification bug! Wah
• Release GenI (but only if I can either fix the unification bug or prove that it already existed in the last release)

GenI wrap-up mode

Pretty satisfying day. Just lots of stuff coming to completion at once:

• INRIA-Gforge stuff is out of the way. I'm using Git-SVN to make Subversion bearable. Once you go decentralised you can't go back. Micro-commiting forever.
• I've completed the integration of the OT ranking code into mainline GenI. If you run it in batchdir mode, you get the rankings and violations in JSON. If you run it just on plain console, you get them pretty-printed. If you run it in a GUI you see them in a separate tab
• I now require UTF-8 input files. I don't have the resources to deal with locales, but I want Unicode support so you're stuck with it. I didn't touch the output, however because I figured I might as well just wait for GHC 6.12 with its locale stuff.

Todo todo:

• Integrate GenI into random formula generator (that's the last of what I'm brought here to do)
  
• Investigate that pesky unification bug. Does it happen with GenI 0.17.4?
• (maybe) look into morphology stuff
  

cluster progress

cluster stuff

Last night and this morning, I polished off the GenI work needed to make it run on the cluster. I also have ppss another look.

One thing that PPSS assumes is that the nodes of the cluster can ssh to the master to ask it things. I wonder how that would work with all these crazy oarsh-or-whatever scripts. Apparantly oarsh is just a super-layer on top of ssh, so maybe there is a way to get at the underlying ssh keys so that PPSS can work.

Working with the local engineer we've now got GenI running on a cluster node. Progress!

unification bug

The universe makes sense after all, but I still have a unification bug. The trick is that I have to turn off optimisations to reveal it. Now I need to check if the bug still exists in GenI 0.17.4

stupid GUI bug fixed!

The week so far:

• Monday: worked on Darcs and a tiny tiny bit on cluster
  
• Tuesday: worked on Darcs in morning, worked on cluster stuff
  
• Wednesday: stymied by unification bug in GenI 0.18; worked on cluster stuff; worked on bug with debugger GUI; implemented geni --version
  
• Thursday: Fixed the GUI bug! This has been going on for maybe a couple years now. It was making the debugger seem totally random (because for some reason junk was being prepended to the list of items in the chart; just the display, not the internal representation)

Basically I was trying to suss out this weird unification bug (why does it only happen on Linux?!). Naturally, I used my debugger to step through the thing so I could work out what was happening... only the debugger was next to useless because of the weird GUI bug. So slight detour as I hack my way through the graphical interface with slightly cleaner code as a result.

Of course, on the way home last night, I realised I don't need to solve the unification bug right now (for purposes of this testing stuff). I could just disable the test case that was triggering it for now so that I could move on to the my task list... but unification bugs are scary! And this being a regression...

guilt

Anyway, I don't intend on feeling too guilty about the Monday/Tuesday bout of Darcs hacking. Just a giant pile of mail in my box and a sort of budding anxiety. Had to polish that stuff all off, get it off my mind. Besides, I have done at least a couple weekends of GenI hacking before coming to Nancy so it /sorta/ evens out. And I'm planning to stay late to catch up a bit today...

So the dream here would be to find a job where you never have to feel guilty about doing any sort of work. Where the job description is just to be productive; doesn't matter who you're being productive for, just go be productive... that's the kind of job I need to land :-P because I know I have the capacity to work on stuff (and more stuff, and more other stuff), and I have a rough idea that said work is more or less net-beneficial to society. Controlling what exactly I'm working on, on the other hand, is not so easy...

unification

HUH? Now that I've fixed my weird GUI bug, the unification bug no longer manifests... also the unification bug never manifested on MacOS.

SIGH

I guess I really should go back to an older GenI and see if I can reproduce the bug there. It was pretty darned systematic.

GenI warnings, gui and morphology

warnings

Before leaving work last night, I polished off the outputting of warnings in batch mode. This also gave me a chance to refactor the GUI code so that it was no longer looking for warning conditions by itself but simply picking up the warning strings from the program state. That made me happy. Nothing pleases me more than getting rid of code.

I still have some warnings that I'm outputting via unsafePerformIO. I need to look into them probably changing the return type of my functions to make everything nice and pure.

Let that be a lesson: kludges hurt. You can do them for expediency, but never delude yourself into thinking that you won't find yourself having to clean up after them in the future.

MacOS X installation

One of my personal priorities is to make GenI easier to install on MacOS X. Ultimately, I want cabal install -fgui GenI to just work. It's not currently the case; there are still a couple of post-install hoops you have to jump through, which are all the more agacant because you have to do them each time you reinstall GenI. The desiderata are:

1. Ability to call GenI from the command line the same way you would under Linux
   
2. No adding junk to paths.
3. No manual intervention after cabal install (right now, need to call macosx-app on the binary)
   
4. No need to be super-user.
5. Possibility of installing in --global
6. Fancy custom app bundles (in the future)

After chatting on #haskell and doing a bit of Setup.hs hacking in the afternoon, I have finally, finally -- argh I'd been itching to fix this for years and now it's done -- worked out a solution to the problem. Thanks to advice from the #haskell IRC channel (it takes a village to write a script), the next release of GenI will be as easy to install on MacOS X as it is on Linux.

Now, if we could get the wxHaskell installation problem solved (and it's well on its way to being so), installing graphical GenI will no longer be painful!

morphology

Spent the early afternoon talking with another GenI user and got some nice tickets out of the process:

• #28 - output to 3rd party morph generator should include variables
  
• #29 - genisrever should output morph features and lemmas
  
• #30 - break morphological realiser out of geni executable
  

How silly of me not to have been using a proper bug tracker for GenI from the very beginning.

GenI batch processing update

It's nice to have customers that know what are the right things to ask for.

I've enhanced the basic batch processing mode in GenI so that it dumps a 'derivations' file with for each sentence

• the sentence generated
• the derivation steps as a list of (operation, child, parent, site)
• the lexically selected items as a list (item name, traces)

Instead of making up my own format, I just used JSON. Great stuff, I finally have something I can tolerate (ie. not XML), something which is vaguely human-readable but still easy to process via third party libraries. In principle, we can now get a stagiere to run over this with a little Python script or something.

Have also converted the chart statistics (don't get excited; by this I mean "number of iterations", "number of lexically selected items", etc) to JSON.

Next up: modify GenI so that warnings are stored in the program state instead of being printed to screen and also dump them in a file.

darcs stuff

Spent the whole morning in a big meeting with collaborative editing folks here in the lab, showing darcs and talking about possible links between darcs theory and operational transforms. Only I don't really understand darcs theory well enough. But hopefully we can invite more of an expert to Nancy.

XMG GenI demonstrator progress

chat

Not such a productive day. Spent first part of the morning settling in with the new machine, a few creature comforts like xmonad and my vim configuration files. Also spent the afternoon chatting with folks I haven't seen in a while. It was good :-)

demonstrator

I've got the demonstrator pretty much squared away. Have done an about-face re: installing software in a private package DB. Now the install script simply does the installation for you. The way I figure:

• If you're using the demonstrator, it's because you likely want to have the software on your system anyway for your own work
• If you're afraid of clobbering your version of the software, don't run the install script.

I'm still bundling things that I don't yet know how to automate fetching, namely XMG and associated tools.

Anyway, I've spent a little bit more time making the documentation more helpful. I hope it really does help. Will have to test it on some users.

forge

One of the questions on my mind is how to distribute the demonstrator. Here are the features some sort of forge type site could offer:

• Homepage: We want a nice (simple) homepage with information and links
  
• Package hosting: We need a place where people can download our stuff and also where we can upload our stuff.
  
• Release management : Slick interface for downloading latest version, but also for going back and picking older releases
• Version control integration : My ranking is darcs > git > SVN (given SVN, I would just roll up my sleeves and deal with git-svn). I don't care all too much because I don't think this is the sort of thing where the choice of version control system has a big impact on developer convenience. Take darcs away from me and I would be crippled for GenI, but for the demonstrator, eh.
  
• Issue tracker: trac is a natural choice for this, but I don't think we have the human resources to manage a trac instance. It'd have to be ready made.
  

What I think we all agree is that it would be silly to migrate XMG and GenI, attempting to centralise them on the one true forge. We're just going to have to accept that we're working in a heterogenous environment, combining tools from several outsiders. The fact that the outsiders happen to be former insiders is irrelevant. Someday in the future, the demonstrator may have to point to Somebody Else's really cool NLP tool, so we're going to have to accomodate outside forges one way or the other.

For now I guess the best candidates are the INRIA GForge instance and Sourcesup.

documentation migration

I'm now looking to see if my Pandoc Mediawiki work can be used to help migrate documentation from the LORIA wiki to the new trac-based on projects.haskell.org. I'll bet I can get away with just converting to MoinMoin syntax instead of writing a Trac writer. My first job is to see if I can first retrieve a list of pages that start with "GenI".

Edit Oh wait: I don't think LORIA wiki is a late enough version to support the mediawiki API.

documentation problem

I need a good policy on documentation. Right now we have (i) literateGenI - which isn't all that useful except for deep technical questions (ii) no manual (iii) sort of a wiki walkthrough that needs migration. I think I intend to flesh (ii) out using literate Haskell (where the documentation is the manual) because I think that's easier to maintain. Will have to look into something like latex2html to put it on the web. I wish I had a gitit instance to play with. That would make wikis more convenient.

loria day 1

First day back at the LORIA.

wxHaskell

Last night, I tried again to install wxHaskell using the new recabalised wxcore. This time for no apparent reason, it all magically worked! I can even run sample applications with it. Very encouraging. This means that we are one step closer to cabal install GenI just working with graphical interface and all.

admin

Today I've been doing paperwork and very shyly saying hello to people from the lab... or sometimes not and just hiding behind my screen instead.

integration

I've started rebuilding XMG-GenI integration (the Makefile of Doom) from first principles. I've learned a few things about integrating lots of software components from my Brightonian hacking so I'm hoping that these experiences will make things a lot smoother and more reproducible. I'm pleased to say that I now have an install.sh script which appears to work.

The thing I'm aiming for most is stability: this means that everything is set to a fixed known last-working version which I bundle with the tool chain or constrain with an installer version. With the exception of Mozart and the Haskell platform, I am only installing software in the toolchain's dist directory and not on the machine. We want things to be reproducible and self-contained. I tried hard to make them so in the PhD years, but I failed, partly because I was also trying to do disparate tasks ("experiments"). Now that the experiments pressure is off, I can focus on just a simple task of making the damned thing run. Hopefully with the whole thing rebuilt from scratch we can go back to thinking about how to do "experiments" from there. The integration problem isn't easy. The whole thing is about tradeoffs that you don't know you're making. It takes a lot of experience and burning of fingers to realise what those trade-offs are.

Tradeoff: The experiments tried to be varied + self-contained but at the price of duplication. Duplication is the root of all evil. Because of duplication, my users had the experience of 10 million Makefiles (all self-contained) none of which worked very well. I started trying to explain why things were so bad, but I don't think I was very successful; it sounded more like I was trying to make excuses, which you never want to be doing. Now I'm going for the other side of the trade-off. I want things to be self-contained with minimal duplication, but this means there's going to be less variety. We'll figure the variety out later.

Tradeoff: To save time, the toolchain did all sorts of fancy things like cutting down the metagrammar to just the pieces that we want to recompile. But these fancy things create complexity and a maintenance hassle. Things break because of it. You can't win. Either you have something fast and ugly or you have something slow and nice. Hrmph. Getting grumpy.

installing stuff

I'm squatting a desk with Ubuntu Jaunty. Installing the Haskell Platform on it is no walk in the park sadly. It's super easy on Windows (I believe) and on MacOS X, but on Ubuntu you have to:

• install GHC binary
• install OpenGL stuff (libglu-dev, I think)
• install editline (libedit-dev, I think)
• patch the installer because of bug #84
• and finally install the platform

I'll still require the platform. It's just easier in the long run, when that beautiful future arrives where HP is available on your favourite distribution. We're getting closer and closer. Haskell with batteries included.

off to France! (for a month)

It will be good to do some legitimate GenI hacking for a change.

I'd better make the most of it. I'm a bit anxious that I won't deliver the goods.

more real work, but very slowly

I'm half-heartedly working on a Pandoc parser for MediaWiki formatted files. The good news is that I can build off another intrepid soul's first attempt. He did all the hard work of figuring out how to deal with this insane idea of using 2 apostrophes to mean italics and 3 to mean bold.

So far I've added in:

• dots and dashes (without them necessarily being hyphens or ellipsis)
  
• paragraphs
• local links
• miscellaneous corrections
• simple test suite
  

I say half-heartedly because MediaWiki is one of those formats that's hard to formalise. Still it seems like using something which parses into a tree is much better than throwing a million regular expressions at the problem (even if the million-regexps solution is easiest to start with).

If I do succeed at making something that's halfway usable, then interesting possibilities open up. Pandoc is a universal translator for formats that uses an intermediate abstract representation of markup. Processing the intermediate abstract representation is just way easier to think about than dealing with markup itself. It also means that we can envisage converting MediaWiki data into other formats.

Hey maybe this can even double as GenI work then: I need to convert from MediaWiki to trac format to migrate my content to the new wiki.

real work

Making some progress on the Wikipedia retrieval stuff. Basically, I now have a thousand articles about British hills downloaded from Wikipedia (in the mediawiki format). It took me a while because I had to

• Extend the Haskell HTTP library with proxy settings detection (copy and pasted over from the cabal-install code). This extension has been accepted, so I guess we've got a little cross-package refactoring action going on here, bacterial DNA exchange.
• Tweak the Haskell mediawiki package to use said proxy detection (trivial)
• Learn how to use the Mediawiki API (and the corresponding Haskell package)
• Write a parser for hill names as they appear in the database (sigh)
  
• Decide what to search for (I just went with the simplest component of all names)
• Decide how to filter the results
• Parse mediawiki API output (I went with the XML output, lightweight parser)
  

The latest development was to just try and see what happens if I look for exact matches. Out of 5000 hills, this gives us 1000 articles... Not too bad, I guess. It really pays to start with the simplest stupidest thing you can possibly think of.

So we got a little bit of Haskell infrastructure out of this. There may be more to come. Now I want to look into the package for parsing Mediawiki syntax. I was initially tempted to work on merging this into Pandoc, but I guess on further reflection that would be very much Not My Problem (for now). All I want to do is parse this goop and extract the most interesting bits from it.

I'll also need to remember that I've also retrived timestamps and revision IDs along with the articles.

darcs for better NLG-human collaboration

It makes me think that there may be some sort of project out there on facilitating cooperation between human and machine editors of collaborative texts, through the use of fine-grained revision control (darcs with character patches).

The idea is that you want your machine to NLG-out some Wikipedia entries, and then have humans edit it, and have the machine make more modifications to the entries without clobbering the human changes unless absolutely necessary. Right now, this may be tricky because darcs and other revision control systems are line based (or maybe KISS, it doesn't actually matter in practice), but because darcs has the ability to deal with different patch types, you could imagine a future version of darcs which isn't line-based, but character based.... this gives you a much more fine-grained notion of merging.

There actually is a git/darcs-based wiki out there (it's called gitit), so you could imagine first an importer from mediawiki history into a darcs history and then a prototype based on this.

unification bug

I just discovered/fixed this bug in a fit of insomnia-based hacking. My unit tests need to be extended accordingly. Should probably send a small advisory to the mailing list:

Basically the question is what happens when you unify [?1, ?2, ?3] with [?2,?3,X].

module Main (main) where

import NLP.GenI.Btypes

main =
 do print $ head $ unify left right
    print $ head $ unify right left
 where
  left  = map (GVar . show) [1..3]
  right = drop 1 left ++ [GConst ["X"]]

Output

([?1,?1,X],fromList [("1",X),("2",X),("3",X)])
([?2,?3,X],fromList [("1",X),("2",X),("3",X)])

What's wrong with that? First, unification should be symmetrical. Second, we should be retroactively propagating results.

Should be

([X,X,X],fromList [("1",X),("2",X),("3",X)])
([X,X,X],fromList [("1",X),("2",X),("3",X)])

I realise I ought to be treating unification bugs more seriously than this, but I don't think this is a big deal in practice. The fix was fairly simple: just rerun replace after unification (which is what the code tends to do in practice anyway, just not on the low level). I'll bet the bug is my fault. Will have to dig up and study some 2004 code, hopefully with the old unification still intact. But stuff like this is why I want an abstraction over unification (eg. Prolog).

Think I need to look into my tests also, maybe try SmallCheck out.

GenI unification

These thoughts should probably go on the bug-tracker somewhere. Probably weekend relaxation hacking or more likely September work. Anyway, I was thinking this morning before getting out of bed that there could be some ways to make the unification stuff in GenI cheaper.

Reductionist performance tester

Too much of GenI performance hacking is done by trial and error. One of the reasons is that GenI is a complex piece of software (for me anyway); many things going on and interacting, so it's not always clear how to boil things down in chunks. This doesn't mean the chunks/units aren't there, just that I need to get better at recognising them. I want to move more in the direction of studying individual bits of GenI without all the intervening junk. For example, I ought to have a performance tester that lets me do unification on two GeniVal lists with (say) a 1000 unique variables each. How much does that cost? Once I figure out how to make such a list (ie. what elements to populate it with), I can start experimenting with some other ideas.

Just in time substitution - Avoid repeated replacement traversals

I suspect this is making unification very expensive. You unify two GeniVal, and whatever variable substitutions come out of them, you need to propagate throughout any structure that may contain said GeniVal. And these are complex structures: chart items (a) which contain lists (b) of nodes (c) which contain feature structures (d) which consist of attribute-value pairs (e) where the values are (f) the GeniVal we're looking for.

Incidentally is why for my Haskell 2006 paper, I was so happy to have type classes; they do a really great job of capturing this idea of "all these different things have something in common". After getting some advice from Neil, I'll be using these type classes in a more generic way (half the code!) and when Uniplate affords the performance I need, just switching to that altogether. Attending Your Favourite Language User Groups meetings is a good idea. If I hadn't been to that LondonHUG talk, "find out what generic programming is" would have been stuck on my list forever.

Anyway: one thing I was thinking is that what ends up happening is that I am doing a lot of traversal. Because I do a lot of unification, I end up building up a lot of "replace X with Y on structure A", followed by "replace Y with Z on structure A"... Unless I misunderstand the fusion/deforestation stuff (which is very likely), these can't be detected on compile-time [because it's replace; do something else; replace] so aren't going to be magically smooshed down into "replace X with Y then Y with Z on structure A"

So instead I need to explore an idea of just in time replacement. In a sense, I already do this by hand. When I have to adjoin two TAG trees for example, and I do feature structure unification on the adjunction site top feature, I only propagate the variables to the foot and adjunction site bottom because I'm going to unify them. I don't waste my time propagating them throughout the whole tree. Of course, I'm going to have to have to propagate them sometime just not right now. Not until I've had a chance to coalesce my replacements (X with Y, Y with Z becomes X with Z, Y still with Z). I want to generalise this idea somehow and make it automatic.

unifyPending

First I want to replace my unify :: [GeniVal] -> [GeniVal] -> Maybe ([GeniVal], Subst) with some sort of unifyPending :: Subst -> [GeniVal] -> GeniVal -> Maybe ([GeniVal],Subst) function. The difference between these two functions is that whereas unify applies substitutions on the future elements of the list as soon as it gets them, unifyPending will instead build up a list of pending substitutions and only apply them as it visits the next item. The crucial difference here is that this affords us the chance to coalesce transitive substitutions (X directly Z). See what I mean? Anyway, the reason why I want to have unifyPending is so that I can generalise to unification within a larger structure

pending substitutions in chart item

Perhaps the chart items need to keep track of the pending substitutions so that we can do the unifyPending trick across chart generation steps.

Unification monad transformer

It's been a couple years now that I've been wanting some sort of unification monad. The problem with unification and my hand-written-just-in-time stuff is that it's very error prone. It's far too easy to perform a unification and then forget to propagate the variable substitutions onto other parts of your structure. And that's silly. We're Haskellers; and Haskellers don't expose themselves to making silly mistakes that could be easily be caught by a computer on compile-time.

In this case, we don't even want to catch the mistake; we just want to rearrange the universe so that mistake isn't even possible in the first place. So yeah, I keep thinking that the pending substitutions should be stored in something like the state transformer monad and that I should supply a unification function within the unification monad, one that applies the pending substitution on the next unification. You want a transformer because you need another monad to capture the idea of failure (Maybe if you just want to know the answer, Either String if you also want to know why you couldn't get an answer).

If I do things right, the unification monad will not only keep my code clean and less error-prone, but also give me just-in-time substitutions for free.

Conclusion

So I don't know if any of this will actually work or if I'm just rambling incoherently. But perhaps one day when I have some GenI time, I can explore this better.

That's the problem with working on stuff. You spend 4 years where you're supposed to do stuff, but you're not able to because you just haven't absorbed enough stuff yet, not enough Haskell, not enough GenI , not enough generation, not enough chart parsing, not enough breadth/depth, your head spins with all the things you don't have a clue about. Now 4 years later, your head hasn't stopped spinning but at least you have a somewhat better idea about Haskell and about GenI and you still want certain things done (particularly, getting to the bottom of this performance stuff)... just that you're not supposed to anymore. Argh! :-)

I guess none of this GenI-hacking counts as really researchy either. Well too bad. It needs doing and if I do it right, then other people can do researchy things with it... which is about the best I can hope for.

See you in September.

the na "phase" - slight dissapointment

So, I was pretty excited about the new intermediate null-adjunction phase I was going to add to GenI because I could see in my mind's eye how this would cut down on a lot of work for the surface realiser.

I did manage to implement this (along with a GUI refactor and a tweak to have the debugger status bar tell you what generation phase it was). I didn't use a separate chart generation phase at the end of the day. Instead what I had a simple filter that gets applied during the switch from the Substitution to the Adjunction one. It appears to work, although I'll still need to hack on it some more so that it propagates info to the GUI and also so that you can tick a box to disable/enable the optimisation at will.

The results aren't all that great. There does appear to be a bit of an improvement
Here's two heap profiles, one using the plain old algorithm (smaller example):
And using the improved algorithm:

On the other hand, things look a bit better on a somewhat larger example. Here's with the old algorithm:
We manage to save about 5 MB of max heap usage with the new algorithm:
Hope not entirely lost yet. Perhaps the effect is more pronounced with bigger auxiliary trees and with more adjunctions (ambiguity?). I'll still need to add the GUI code so that I can see what this thing is actually doing (I make the graphical debugger for me not my users; I wouldn't be able to get a feel for GenI without stepping through that and studying the trees).

Or maybe somehow this optimisation is pointless because blah-blah handwave Haskell laziness gesticulate wildly. I do wish I had a better idea on how to write good fast Haskell software. Slowly learning things. It's interesting to look at these heap profiles. It's like there's three phases: substitution, adjunction and then what? Printing out the results? Is that what that spike is, as all the accumulated work from adjunction/substitution actually has to be performed? What's the effect of this optimisation? It looks like we're forced to pay a lot of the substitution costs up front instead of at the very end. But where?

That's one of the reasons why I've been obsessively working on this lately. Like the ugly unification code, my persistent inability to understand what makes GenI tick (performance wise) just gets under my skin. I HAVE to know why it's slow. Maybe I'll never be able to make GenI faster, but I just hate the uncertainty. Is it supposed to be like this? Probably not. 50% of time spent doing garbage collection can't be good.

Anyway, I guess I'd better put GenI away and start doing some real work over the week. I've just been a bit performance-obsessed lately. I bet we can do better than this.

GenI hacking - unification refactor

Oh, this feels good. This scratches an itch. I've been pretty embarrassed about the state of GenI's unification code for a long time. The new code does the same thing, and while it may not exactly be something to be proud of, I reckon that it's got about 64% less Suck.

We should play "spot the difference" in the comments:

Eric thinks this code sucks less for 5 reasons. What are they?
I'll note that the only reason I have been able to reduce the Suck in this code comes from my participation in open source projects. I may still be a crap programmer, but imagine how much worse the situation could be if I wasn't osmosing all those ideas by reading other people's code. If you want to code better, you have to watch how other people do it. I don't think I can recommend this enough if you have to code on the job. If your job does not already involve a lot of hacking with people who are way better at it than you are, then you absolutely have to join an open source project.

the new code

unify :: Monad m => [GeniVal] -> [GeniVal] -> m ([GeniVal], Subst)
unify [] l2 = return (l2, Map.empty)
unify l1 [] = return (l1, Map.empty)
unify (h1:t1) (h2:t2) =
case unifyOne h1 h2 of
Failure -> fail $ "unification failure between " ++ show h1 ++ " and " ++ show h2
SuccessRep v g -> prepend `liftM` unify t1b t2b
                 where
                  s   = (v,g)
                  t1b = replaceOne s t1
                  t2b = replaceOne s t2
                  prepend = (g:) *** prependToSubst s
SuccessSans g  ->  first (g:) `liftM` unify t1 t2

data UnificationResult = SuccessSans GeniVal
                    | SuccessRep  String GeniVal
                    | Failure

unifyOne :: GeniVal -> GeniVal -> UnificationResult
unifyOne g GAnon = SuccessSans g
unifyOne GAnon g = SuccessSans g
unifyOne (GVar v) gc@(GConst _) = SuccessRep v gc
unifyOne gc@(GConst _) (GVar v) = SuccessRep v gc
unifyOne (GConst v1) (GConst v2) =
case v1 `intersect` v2 of
 []   -> Failure
 newV -> SuccessSans (GConst newV)
unifyOne x1@(GVar v1) (GVar v2) =
if v1 == v2
  then SuccessSans x1
  else SuccessRep  v2  x1

the old high-suckage code

unify (h1:t1) (h2:t2) | h1 == h2 = unifySansRep h1 t1 t2
unify (GAnon:t1) (h2:t2) = unifySansRep h2 t1 t2
unify (h1:t1) (GAnon:t2) = unifySansRep h1 t1 t2
unify (h1@(GVar _):t1) (h2:t2) = unifyWithRep h1 h2 t1 t2
unify (h1:t1) (h2@(GVar _):t2) = unifyWithRep h2 h1 t1 t2
 -- special cases for efficiency only
 unify ((GConst [_]):_) ((GConst [_]):_) =
 fail "unification failure"
 -- end special efficiency-only cases
unify ((GConst h1v):t1) ((GConst h2v):t2) =
 case h1v `intersect` h2v of
 []   -> fail "unification failure"
 newH -> unifySansRep (GConst newH) t1 t2

{-# INLINE unifySansRep #-}
unifySansRep :: (Monad m) => GeniVal -> [GeniVal] -> [GeniVal] -> m ([GeniVal], Subst)
unifySansRep x2 t1 t2 =
 do (res,subst) <- unify t1 t2    
    return (x2:res, subst) 

{-# INLINE unifyWithRep #-}
unifyWithRep :: (Monad m) =>  GeniVal ->  GeniVal -> [GeniVal] -> [GeniVal] -> m ([GeniVal], Subst) unifyWithRep (GVar h1) x2 t1 t2 =  let s = (h1,x2)      t1_ = replaceOne s t1      t2_ = replaceOne s t2      ustep = unify t1_ t2_  in s `seq` t1_ `seq` t2_ `seq` ustep `seq`     (ustep >> = \(res,subst) -> return (x2:res, prependToSubst s subst))
unifyWithRep _ _ _ _ = geniBug "unification error"

more GenI optimisation - the No Adjunction phase

Just had a small idea on how to make GenI faster without having to be a clever Haskeller. You'll want to be careful here. I think what I'm proposing is safe and correct, but I may be missing something.

an older idea: top/bottom unification on the fly

To give some background to this idea, I want to talk about another similarly small idea I had/implemented when I was desperate to optimise GenI and was still actually supposed to work on it. This older idea consisted of doing top/bottom unification on the fly instead of at the very end of derivation. It's safe to do it if you're doing 2-phase chart generation and if you only do it on nodes which you have ruled out for adjunction (reasoning: you are never gonna touch those nodes again).

So why am I talking about this? The reason is that both that older idea and the one I'm thinking about now fit into the basic theme of cutting down your search space by using domain-specific knowledge to choose an optimal traversal, ie. one that promotes failure and pruning. If you are careful about what order you do operations in, you can walk the space in such a way that (A) you identify the failing regions of the space as early as possible and (B) reduce the amount of work you actually have to do in the parts you still need to explore.

Concretely, the on-the-fly tb unification means that (a) you induce any unification failures which may occur as soon as possible thus pruning out any chart items which you would otherwise generate for no good reason and (b) that you reduce the size of the chart items because you've mooshed together the top/bottom feature structures, which means you get much quicker traversals whenever you do unification and need to propagate some variable substitutions on your structure.

the No Adjunction phase

OK, so what's the new Small Idea? Right now GenI has a two-phase chart generation algorithm, substitution before adjunction (in a way this is also another variant on the order-of-traversal to maximise pruning; but I think it's more than that, i.e. avoiding redundant traversals that lead to the same space so I didn't want to mention it). My thinking is that we should introduce an intermediary phase for non-adjunction.

In this phase, your job is hunt down all the potential adjunction sites to which no auxiliary tree may adjoin. So basically, you TRY to perform adjunction (with every auxiliary tree in your chart). The trick here is that you don't bother saving the results if you succeed because you don't care about adjunction yet. All you want to do is rule out as many nodes for adjunction as possible, just mark them as ^na constraints ASAP.

The benefit of this is that (a) you later combine these auxiliary trees with other initial trees, you don't have to faff around with trying these potential adjunction sites again. They're gone. This could actually have a pretty wide impact if you consider that an auxiliary tree could potentially combine with more than one chart item. Also (b) closing off the adjunction sites as soon as possible means that you're also doing your top-bottom unification sooner, which means that whenever you do variable substitution, you're working with much smaller structures - fewer things to traverse.

Oh some details: first, this phase requires a temporary holding area. I think you can recycle the auxiliary agenda for that. Once you're done with the intermediary phase, you ditch your chart and partition the holding area into initial and auxiliary trees, moving your new smaller auxiliary trees (fewer adjunction sites) into the chart and your initial trees into the agenda for the usual adjunction phase. Second: the adjunction phase has to be left intact. In other words, just because we've performed a no-adjunction phase doesn't mean we can omit the no-adjunction inference rule from the adjunction phase. We still got to try it out it account for the possibility that you don't want to adjoin something to node Foo even though it's possible, but to node Bar. The only thing the intermediary phase does is to minimise the number of possible adjunction sites that you have to explore.

GenI performance and wikipedia

not work

I've been pretty obsessive about improving GenI performance for the past few days. It's not work (so I'm plunging deeper into time debt), but I guess it's not so bad since I'm learning stuff that will make me better at work in the future: more about laziness vs strictness, simple things like tail recursion, getting the hang of the profiler, continuation passing style, generic programming. The best thing here is if I can make GenI faster by making the code cleaner.

My main toy right now is the Uniplate library, so easy that even an Eric can use it. I'm hoping that if I use this, I can get rid of a good chunk of boring repetitive code (the bit that performs substitutions on variables after unification). Only problem is that it makes my memory usage explode. I've asked Neil about it and he has very kindly offered to have a look at the code.

I've had a couple of minor wins: killed the heap growth in a pathological adjunction example (I've got to build up a library of minimal, artificial performance examples), more than halved the memory usage on some adjunction, but nothing to big O about.

Bleh. I need to stop doing this and start doing Work though.

wikipedia retrieval

A kind soul on the #wikipedia channel told me I was going about this entirely the wrong way. Instead of looking up articles by title, I should just use the search engine (because predicting article names is going to be hard). That's when I remembered that there's now a mediawiki library on Hackage (this sounds like the kind of thing Haskell NLP people need to know about).

I think I'm mainly procrastinating on learning on to use this thing.

I still bet that because the things I'm trying to look up are sort of obscure and well behaved, it'd be a useful feasibility study to search for titles and see what comes up. I'll have to give up on my read everything into a giant trie idea and probably just double-loop.

sloppier

This is too much, but I am going to let myself be more relaxed about how I spend my time (20% deal notwithstanding). My current approach of counting every 15 minutes and never going to work is making me miserable :-).

Yes, there was a necessity for it (and there still is) because I was spending all my time doing darcs stuff (like I'm spending all my time doing GenI stuff right now), but the sort of ugh-work depression that's resulting from this is making me unproductive.

So I'll just have to accept that I'll probably have zero holiday budget for next year and let myself work in a more natural way: by periodically latching on to obsessions, by time into learning new skills instead of doing things, and by taking the weekend off even if I'm behind budget and getting further and further away from it. We'll see how this goes.

My justification is the dual use nature of things. So I'm doing this thing because I'm interested in it and not because it needs doing. But then it pays off later when I need to do something else that Is work and actually makes use of what I've learned. Of course, you have to do real research at some point, can't spend all your time learning R or trying to CPS-style your monads. But that's what ya get. Maybe I'm not a researcher. I just like to make things and to learn things so that I can make things better.

The counter-argument, of course, is that I'm already spending a good chunk of my time on not-work (i.e darcs) and spending more than that time is starting to be, shall we say, taking the piss?

Sigh.

wikipedia retrieval

Here's one problem I'm working on now: given 5000 or so names and 6.5 million Wikipedia entries, retrieve all the articles that correspond to those names (if any).

Maybe this is the kind of thing where I have to stop hacking and start doing some computer science (or not). Lots of little things to work on. I confess that I tend to just sort of get bored and wander off when I should be thinking of solutions to things.

Rough thoughts:

• I'm not really expecting a large majority of those names to actually exist on Wikipedia
• There may be cases where the name is ambiguous (think Jacksonville, North Carolina vs Jacksonville, Florida; Fargo (film) vs Fargo, North Dakota)
• I may run to into redirects
• I may run into disambiguation pages
• It may be wise to make it so that I can repeat this procedure as Wikipedia evolves
• Need to deal with encoding of characters for URLs and also for Wikipedia. We don't really want to %-encode everything because it would look needlessly ugly.
• Ideally, you want to have one name = one article. How do you choose?
  

Things I'm considering:

• Do most of your work by talking to Wikipedia.
• Download a database dump and then poke at it offline (only 5G bzip2ed if you don't care about history).
  

My current thinking is that as a first step, I need to do some offline work. I've retrieved a list of wikipedia titles (6.5M lines, 126Mb) which I could just grep through 5000 times. This would give me a list of potential matches which I would have to navigate. But then what? I still haven't dealt with all the boring nonsense like the redirects and what not, but it's a first step. Feasibility study. Figure out how many matches you get through this simple process first, before trying to do all the hard stuff.

Instead of grepping 5000 times, I thought what I would do is store this the set of titles as a trie (there's those DEA courses being put to use). In case I have more than one match, the submatches would just be a subtrie. I figure that if I'm going to be doing this 5000 times, it would pay off if I read things in once into some efficient data structure. I also figure that because my script is going to have to do some arbitrary nonsense (for example look for things that start with parentheses after the matches, eg. Jacksonville (city)), and that I would be happier with code that did everything in-house instead of having to make a call to grep each time. But maybe I'm just being stupid by trying to be clever. After all, in computer terms, 5000 is nothing, right?

We'll see how this goes. I'm really not very good at making things scale, so this ought to be funny.

Edit an hour later OK. First, grep is really really really fast :-). Second, building the trie took forever. Perhaps there's some kind of performance stuff I just need to play with.

toolchain/pipeline - coping with slowness

One aspect of evaluation toolchains/pipelines is that they can often take a long time to run. I suspect this will be true for as long as we'll be writing these things: the faster our computers and algorithms get, the more ambitious we become.

So we need to make sure we get better at managing time. How do we go about doing that?

Option A: One thing we could do is to become better programmers and computer scientists, i.e. write code more intelligently. Right, step 1, become better computer scientist. Check. But then what if you're as dumb as an Eric and pretty much never going to become a better computer scientist?

Option B: learn a bunch of stupid tricks.

set aside the slow stuff

Thanks to my time in Nancy, I've grown to appreciate having one single go.sh script that I can run that does EVERYTHING... except the slow stuff. The slow stuff I set aside in a different fire-and-forget script, for example resolvers-go.sh, because running the resolvers takes a long time.

This can be beneficial because you'll often find yourself with fast little tools that you modify frequently... so what you want to be able to do is just to tweak the tool (say you modified it to print the rows of your table in order of the best score) and just mindlessly rerun go.sh. If you separate out the slow stuff (that doesn't need to be re-run), you are then free to re-run your go script as often as you want.

It's probably also a good idea for your go.sh to detect if you have forgotten to run your slow-thing.sh

Mindlessness is good. The cognitive friction involved in "wait, which script do I need to run again, and which parameters do I need to pass to it" is costly. I don't know why really. Just having to think about that stuff makes you stupider. So make things mindless so you can go spend your time being clever instead of scratching your head at scripts.

use your number cruncher

Somewhere in your lab, somebody ordered a REALLY REALLY fast machine. Don't forget to use it! It sounds obvious, but I didn't think to do it until I was three-quarters through this evaluation exercise. Would have saved me a lot of grief.

That you often need to be running things on more than one machine is why it's a very good idea to make sure your toolchain is as portable and EZ-install as possible (e.g. following the tips in my last post and more). You want to be able to just rsync that crap over and hit go.sh. No sitting around trying to figure out what extra junk to stick into your .bashrc

use screen

The great thing about screen is that it allows you to run something, log out, go home so you can have dinner [leaving the thing crunching away in the background], log back in when you're done with dinner and resume staring at progress bars. Screen effectively removes the requirement to be physically present at our machines all the time from our natural compulsion to stare at progress bars.

Screen is particularly useful in conjunction with your fast machine. You can ssh in from work, detach your screen, log-out, ssh-in from home, reattach your screen.

use rsync

Don't forget that you'll be modifying your toolchain (fixing bugs) and re-running it a whole bunch of times. I guarantee it. You will be running this thing many many times before this evaluation is over.

I have this script I call copy-to-fast-machine.sh in my toolchain directory.

#!/bin/bash
rsync -av `dirname $0` --exclude='*/dist/*' fast-machine:my-toolchain

So I just do

eval `ssh-agent`
ssh-add
cd my-toolchain
./copy-to-fast-machine.sh

Then every time I fix something in the toolchain, I just sigh once, hit the up arrow in bash, and rsync everything over again. Notice in particular that this script tells rsync to exclude the dist directories. This is useful to avoid having the fast machine get confused because you compiled something on your home machine, and then recompile everything out of that confusion.

Pay attention to detail so that you can maximise the mindlessness.

parallelise the heck out of things

Today's happy discovery is a shell script called PPSS. I've always been meaning to figure out how to do clever things like running stuff in parallel (and on multiple machines). Turns out, I don't actually have to be all that clever. The above is a simple shell script that figures everything out for you. You just feed it a list of files, and a command to execute on any one file (e.g. "${SCRIPT_DIR}/opennlp-wrapper/run-opennlp.sh ${INDIR} ${OUTDIR}/openNLP \$ITEM" ($ITEM is a placeholder for the file in question) and BANG, instant maximum resource consumption, all N processors happily crunching away.

conclusion

There's nothing here that counts as rocket science, just stuff that I typically forget to do before it's too late. If you just put these tricks together in your toolchain, you can save yourself a lot of time and open the door to re-running things over and over and over again (which is good if you are like me and prone to screwing things up).

So hopefully, if I ever find myself writing another one of these toolchains, I'll actually remember to do these things from the get go.

fetching opennlp models

This will be a stupid post with potentially bad advice.

Context:I want to to try the latest version of OpenNLP and see if it still has a NullPointerException on one of my texts.

Problem:I have to download a bunch of models (49 files) from their homepage. They're probably making me do this by hand for a good reason, but I'm going to have to rebel against that, sorry. I'm not going to sit there scratching my head to figure out which subset of the 49 I'm going grab, nor am I going to click into each directory and download them one by one, clickity, clickity, clickity.

I tried wget -r http://opennlp.sourceforge.net/models/english, but that only fetches the index.html file and returns a binary at that. Note that visiting just the page gives you a directory listing, but visiting index.html gives some sort of PHP diagnostic thingy.

Solution:Recursive scp.

I don't know if you need a sourceforge account for this, but I did:

scp -r kowey@web.sourceforge.net:/home/groups/o/op/opennlp/htdocs/models/english .

toolchain/pipeline scripting

More thoughts on the construction of toolchains. Actually, I'm wondering if "toolchains" is the wrong word for this and if maybe I want to say rather is "pipelines". So maybe I'll call them pipelines in the near future, but for now, "toolchains" will do.

In the last post I discussed t some useful distinctions to maintain in the kinds of directories that your toolchain used. Today I want to look deeper into the question of scripting. Keep in mind that I may not know what I'm talking about. Pass the salt.

sh vs bash

I used to think that for portability's sake, you should write scripts using #!/bin/sh as the shebang. But now I realise that this is likely a mistake, a sort of false advertising.

As I currently understand it, the problem is that it is far too easy to write shell scripts that say they are simple Bourne shell scripts when they in fact use features (or make assumptions) that pertain only fancier shells such as the Bourne again Shell (bash). The reason this happens is that (a) on your system, is it very likely for /bin/sh to just be /bin/bash which is fine, except that (b) as far as I can tell, bash is tolerant about interpreting scripts with a /bin/sh shebang but bash-specific features. So while your "portable" script appears to work on your system, it blows up when your Ubuntu using friend runs it because his /bin/sh is not bash but the lighter weight dash. Oops.

For what it's worth, this is why I'm actually not a big fan of the "be strict in what you emit and generous in what you accept" principle. Maybe it was relevant in the past. But I think now a better policy in the long run is "be strict in what you emit and it what you accept". A little autism goes a long way.

Anyway that's why I advocate using #!/bin/bash instead. It increases the probability that if it works for you then it'll also work for somebody else. No more false advertising (which always leads to misery). And besides, who doesn't have bash these days? We'll see what Eric ≥ 2015 thinks of this advice.

cwd tolerance

I like it when my scripts can be run from any directory and not specifically the one where the script lives. For this to work, however, my script needs to know where it lives. How? Use the $0 variable. My current implementation of current-working-dir tolerance involves a bit of bash. I don't know if this is the best approach, but it works for now:

pushd `dirname $0` > /dev/null
SCRIPT_DIR=`pwd`
popd > /dev/null

This SCRIPT_DIR variable can then be used to reference anything which is relative to the script path, for example, CORPUS=${SCRIPT_DIR}/../data.

Now why is this important to me? First, there's a simple question of convenience. Sometimes, I want to pass in paths to my script which are relative to my current location, which isn't possible if I have to cd to the script directory to run it.

Second, I want to make it easier for other scripts (and other people!) to interact with my script. There is no reason that they should have accommodate me by juggling their paths. Put another way: adjusting paths to deal with working directories is a pain. Somebody is going to have to suffer this pain: either me as the producer of the script, or you as its consumer. Since there is a many-to-one relationship between consumers and producer, the producer should take care to pay the price so that the consumer doesn't have to. It's like paying careful attention to how you write your mails on a mailing list. There's one of you writing, and there's tons of people doing the reading, so write carefully. Build cwd-tolerance into your scripts.

(NB: I used to merely use SCRIPT_DIR=`dirname $0`, but this is a little fragile, because it can return a relative path and lead to all sorts of trouble if you have other scripts (in other paths) calling this script. The pwd approach returns an absolute path, which is uglier but more robust)

the user environment

This part of the post is slightly related to the discussion on external vs internal software in my entry on toolchain directories. Consider this scenario: you have some internal code that is shared across different components in your toolchain. How are you going to get at this shared code?

Now we know that duplication is the root of all evil, so having one copy of this shared code per component is out of the question. What happens every time I'm tempted to do this is that at some point I have to modify the shared code, but I forget to replicate this modification across all components and all sort of crazy, hard to track down bugs result (not to mention the confusion: which is the official version again?).

Another option, one which I was using until only yesterday, is to have the user install the shared component. OK, this works if you're willing to package up your component and put it in an official repository like CPAN or Hackage. But what if it's really not for public consumption? It's really just so specific to your toolchain that it just wouldn't be right to stick it in a repository, and besides you can't be bothered to do all the packaging work. In this case, what you might be tempted to do (at least, I certainly was tempted!) is to put these components in the user's HOME directory and have them add something to their shell init file. I'm talking about things like setting the CLASSPATH variable, or PERL5LIB, or PYTHONPATH.

STOP THAT
One: You're polluting the user's home directory with random crap that she's not going to know what to do with three years from now.

Two: You're giving the user one more hoop to jump through to get started (and you're giving yourself one more line of README to write and verify). Basically, doing this amounts to taking short-cuts now and off-loading the pain to other people (including future versions of yourself, who acquire shiny new laptops at some instance in their life and have to get started again).

Three: What will likely happen to you is that you will forget that you have done this. So sometime in the future, you ship your toolchain to somebody else, and when they try to run it, it no workee. Why? Oh yeah, the PERL5LIB kajoogle. No. No kajoogle. Kajoogle Bad.

There is an alternative to this. Since you've written your scripts to have current-working-directory tolerance, you know where your shared code lives. So instead of making the user jump through these arbitrary and fragile hoops, what you should do is just provisionally augment the environment within your script. It's not hard. My scripts have little lines like

export PERL5LIB=${SCRIPT_DIR}/../shared-code/common:${PERL5LIB}

or

export PYTHONPATH=${SCRIPT_DIR}/bundled/PyCoLi/python/coref\
:${SCRIPT_DIR}/bundled\
:${PYTHONPATH}

Just a little bit of code like that in your scripts makes a big difference. Now you can just rsync your toolchain over to the fast machine and run it, instead of having go through all sorts of crazy installation procedures.

But I understand it isn't always easy. Me, for instance, I haven't figured out how to have a temporary Haskell package database, so I make my users cabal install my shared code. That's in flagrant violation of this section (but at least it's documented and versioned).

conclusion

Whenever possible it's a good idea to keep your toolchain self-contained and free from assumptions and hoops to jump. I certainly was never very good at it (to think of all the horrors and broken toolchains I left behind in France), but I hope that one of these days I'll work it out and write an "it just works" toolchain. It sounds like a lot of effort, but it really pays off. Just tell yourself that the only reason you don't have time to things the right way is because a past version of yourself made the same excuse, which you are now paying the price for. So break the cycle. Be kind to Future You. (again, not always easy, I'm definitely a hypocrite here).

coreference with a passion

I'm not going anywhere with this, just horsing around.

attempt one

John hates Sally with a passion. But he can't resist talking to her.

********Anaphor-antecedent pairs*****
(1,7) her <-- (1,1) he, 
(0,0) John <-- (1,7) her

********Text with substitution*****
John hates Sally with a passion. 
But [John] can n't resist talking to [John].

attempt two

John hates Mary with a passion, but he cannot resist talking to her.

********Anaphor-antecedent pairs*****
(0,5) passion <-- (0,8) he, 
(0,0) John <-- (0,13) her

********Text with substitution*****
John hates Mary with a passion, but [passion] cannot resist talking to [John].

attempt three

John hates Mary, but he cannot resist talking to her.

********Anaphor-antecedent pairs*****
(0,10) her <-- (0,5) he, 
(0,0) John <-- (0,10) her

********Text with substitution*****
John hates Mary, but [John] cannot resist talking to [John].

attempt four

John hates Mary. He talks to her.

********Anaphor-antecedent pairs*****
(1,3) her <-- (1,0) He, 
(0,0) John <-- (1,3) her

********Text with substitution*****
John hates Mary. 
[John] talks to [John].

attempt five

John hates Mary. John talks to her.

********Anaphor-antecedent pairs*****
(1,0) John <-- (1,3) her

********Text with substitution*****
John hates Mary. 
John talks to [John]. 

attempt six (ah-hah!)

John hates Bob. John talks to him.

********Anaphor-antecedent pairs*****
(0,2) Bob <-- (1,3) him

********Text with substitution*****
John hates Bob. 
John talks to [Bob]

attempt seven

John hates Bob. He talks to him.

********Anaphor-antecedent pairs*****
(0,2) Bob <-- (1,0) He, 
(0,2) Bob <-- (1,3) him

********Text with substitution*****
John hates Bob. 
[Bob] talks to [Bob].

Now back out and try plugging Bob into the rest of these...