refex generation

It often happens for me that trying to implement something subtle/tricky is way more effective a learning process than going cross-eyed over a paper

refexes:
  within rx:
    b1 (a box): [OK]
    b1 a1 (a box and an ant): [OK]
    b1 b2 (two boxes): [OK]
    b1 a1 b2 (two boxes and an ant): [OK]
    a1 b1 b2 (an ant and two boxes): [OK]
  across rx:
    a1|a1 (an ant|the same ant): [OK]
    a1|a2 (an ant|another ant): [OK]
    a1 a2|a1 (two ants|one of the ants): [OK]
    a1 a2|a2 (two ants|one of the ants): [OK]
    a1 a2|a2 a1 (two ants|the same ants): [OK]
    a1 a2|a2|a1 (two ants|one of the ants|the other ant): [OK]

morph testing

Hello from beyond the academic grave! Just reporting that morphological realisation (and some simple aggregation) seem to lend themselves quite nicely to unit testing, at least for spotting simple blunders.

(My bug was just a flipped bit, meant "Plural" when I typed "Singular")

verbs:
  inflection:
    walk (walks, walked): [OK]
    push (pushes, pushed): [OK]
    pass (passes, passed): [OK]
    abuse (abuses, abused): [OK]
    banjo (banjoes, banjoed): [OK]
    play (plays, played): [OK]
    cry (cries, cried): [OK]
  expansion:
    walk:
      walks: [OK]
      walk: [OK]
      walked: [OK]
    call_in:
      calls in: [OK]
      call in: [OK]
      called in: [OK]
    take_in (cooperation w lexicon):
      takes in: [OK]
      take in: [OK]
      taken in: [OK]
concepts:
  star (stars): [OK]
  egg (eggs): [OK]
  patch (patches): [OK]
  boy (boys): [OK]
  spy (spies): [OK]
  thesis (theses): [OK]
  elf (elves): [OK]
  ace (aces): [OK]
refexes:
  box (a box): [OK]
  box ant (a box and an ant): [OK]
  box box (two boxes): [Failed]
Failed: expected: ["two boxes"]
 but got: ["two box"]
  box ant box (two boxes and an ant): [Failed]
Failed: expected: ["two boxes and an ant"]
 but got: ["two box and an ant"]
  ant box box (an ant and two boxes): [Failed]
Failed: expected: ["an ant and two boxes"]
 but got: ["an ant and two box"]

GenI parser cleanups and error handling

I have a piece of code which gives me a nagging feeling of wrongness.   There aren't going to be any answers in this blog post, just an exploration of the problem space.

GenI uses a handful of different input files, a tree schemata file, a lexicon and a test suite.

There are others, but we can focus on that for a moment.  I have this common pattern which I use to work with such files:

1. read configuration setting from program state (IORef): this corresponds to flags passed in from the command line
2. read the file
3. parse the file with Parsec
4. post-process the parsed entries (for example, if it's a list of items, weed out the duplicates)
5. update the program state with the post-processed entries

This is neither rocket science, nor computational linguistics, just your basic IO and dance.  Here is the code that handles this bureaucracy.  The type signatures may be a bit confusing, what with the use of existential types to try to support an heterogeneous flag set (probably severely misguided, and now potentially obsoleted by the really nice magical libraries like cmdargs and cmdlib), but I think you can see the common pattern lurking through this.

Some some reason I've spent the whole time working on GenI walking around with this nagging feeling of Wrong-Wrong-Wrong, the feeling that this should be a lot simpler and tidier than it is; but also that I had far more important things to be doing that worrying about a minor itch.  Unfortunately, the itch has just turned into a rash.  The issue is that the error handling is not useful outside the context of an academic software prototype, a prototype which can afford to crash autistically because its programmer has high priority items to hack on.  If you want to use GenI as a library, crashing on bad input is not going to fly.

Notice that the problem is not the code isn't factored.  In fact, it's probably excessively factored, but just somehow wrongly factored, like I've started barking up the wrong tree. I kind of feel like I need to redistribute the pieces and try again.  Part of this is the natural, organic growth of an academic software prototype.  You just sort of glom on features as your needs change.   The problem now is how to tease apart the necessary and unnecessary bits of complexity:

• error class: missing command line arguments -- notice I have a loadFileOrIgnore for some reason, looks like there are cases where you do want to support a command line argument being missing, but not always
• error class: bad file
• error class: missing file, etc [not really handled]
• use cases: reading from GUI support (if the user supplies bad input from the GUI, pop a dialog box instead of just crashing -- this isn't visible in the snippet but it does do that for some inputs), reading from command line and reading via a library call
• status messages (printing "now loading foo..." to stdout
• wanting to avoid code duplication
• binary file detection - in the case of macros files, we have two file formats, a fast-loading binary file format (probably a bad idea?) and slow-loading text file format.  We want to support the behaviour where we first try to read the file as binary, and if that fails, read it as text.  It's worth thinking about dropping this future, but we don't want to break compatibility with old grammars in the process

There are basically a couple of other issues I'm trying to wrap my head around

1. Can we eliminate the use of a global program state to pass things around in?  It feels so horrible, but every time I make a stab at it I somehow burn my fingers and give up
2. What kind of error handling do I want?  We have a lot of tools at our disposal in Haskell.  For example, parse errors can be differentiated from successful parses in the type system.  Unfortunately, one tool I've been using a lot (for convenience) is fail, a function whose presence in the Monad type class is commonly held to be a mistake in Haskell.
3. From the maintenance perspective, how do I divide the code?  What lines do you factor it along?  This is probably one of those tricky questions it would take years of maturation to answer properly.  What do you make easier at the expense of others?
4. From the usability/API perspective, how I divide the interface?  What should I provide as discrete functions, and what should I ball up into do-everything functions?  

Error handling is a subtle topic with tradeoffs, and I think it is very very easy to get the wrong idea about what to do with errors. For example, Freshman Eric tried to take to heart the idea that code should be defensive and robust with respect to errors but ended up writing a lot of code which just "gracefully" caught errors only to hide them (and yes, before you weigh in, I know that you can catch exceptions selectively).  I'm just saying it's more subtle than one may think... Maybe a more mature Haskeller or a LISPer can come in and smack my head around a bit.  For now, I'm working on this sort of rough basis:

1. expected unusual cases - not actually errors (for example, find me the first entry in the list which satisfies condition foo should return Nothing or Just the item)
2. my errors as a programmer - this-should-be-impossible style error should either be cunningly made inexpressible with the type system (this is the sort of thing I admire in clever Haskellers), or greeted with a CRASH.  The crash is something Freshman Eric would not have understood, "wouldn't you want to be robust?"
3. bad input from other programmers using my code - ??? if I'm division, what do I do if the programmer fails to heed the API  and passes me a zero denominator?  If I'm the head function, what should I do if the programmer gives me an empty list?  The Haskell stdlib crashes in these cases (you should know better), but an alternative option would be to be express the errors with something like Maybe.  But does the Maybe really make sense here?  I can see how you would want to express the idea "this dictionary does not have the entry you're looking for", but saying that 4 / 0 is Nothing where as 4 / 2 is Just 2 seems to imply that 4 / 0 is legitimate.
4. user errors - be as graceful as humanly possible, detect errors at the earliest possible stage
5. completely unanticapted errors - ??? nobody is perfect... you can't predict everything that could possibly go wrong (perhaps unless you're one of these Formal Methods types?)

I don't want to get too general about this, not trying to write a programming book here.  Just saying, this sort of thing can be a bit subtle.  In my case, I have a user error (trying to parse a file that's not in the expected format), and I think actually my code does recognise it as such.  The Parsec library recognises it as an expected usual case (which makes sense), and my code simply takes it out with pattern matching (Left/Right) and blithely exits on parse error.  In a sense I'm doing the right class of things (knowing it's a user error), but I'm doing it in the worst possible way; exiting when I should be giving the user some recourse to action.

That should be a straightforward fix to make... just throw an exception, but I still think this code needs a lot of cleaning.

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.

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"

been a genchal week (+132h)

Kinda boring, but also very good practice for teaching myself to shut up, stop complaining and just do what needs doing. If that means writing unit tests and documentation, go write unit tests and documentation. Get it right. Sigh :-)

Time bank holding steady (was +131h last week). The model for Balance that I would like to experiment with is

• try to meet your daily quota every day
• do minimal darcs stuff every day
  
• if you have exceeded your weekly quota (even by 15 minutes), you can take the rest of Friday afternoon off to go do more substantial darcs stuff once you've met your daily quota
  
• if you have exceeded your weekly quota by a lot (say 2 hours), don't worry about making Friday's quota, just go do darcs stuff when you feel like it

So basically, darcs being the Friday afternoon treat for a week's work.

another genchal day

I now have a reusable module for doing web-based, latin square, human intrinsic evaluations. It's mostly just refactoring previous work, cutting into pieces and learning how to do object oriented programming in Perl (it's easy: objects are just packages).

Working on some baselines next.

I have been reading The Pragmatic Programmer lately. Very easy to understand. Good advice... has clarified some of my inner debates, like what to do about errors and exceptions. Do not repeat yourself. Dead programs don't lie.

mostly genchal

I've been spending the whole week working on genchal stuff (cleaning up last year's work: short cuts make long delays... JSON was quite helpful for this... if there is a next year, hopefully reuse and extension will be easier).

chartparser and packing

Just snuck in a few minutes of chartparser work. I've figured out my CKY problem. I'm not sure I can explain this right. So the point of the chartparser library is to make it ridiculously easy to write parsers, right? Not necessarily fast parsers, just parsers that are correct. It's a prototyping library. So to do this, I try to supply as many of the basic features in a generic, hopefully orthogonal, format. Part of this is for me to figure out what the heart of the chart parser is. Okay, so I've got a bit that removes items of an agenda (any data structure), combines them with the chart (any data structure), but is this logic part of the core chart parser?

• if an agenda item already exists in the chart, remove it
• if a chart item already exists, do not add it to the chart

It seems like a simple question, but then what happens when you add a generic backpointer mechanism? I like the generic backpointer mechanism because it means you can generate a derivation tree for any parsing algorithm. But then what makes an item unique? Should it just be the "essence" of the item that we compare, or should we compare the full item, including backpointer?

Let's see how this interacts: given the sentence "somebody hacks something somewhere", I ought to be getting 2 derivations. My "minimal" chart data structure was only paying attention to the essence of a chart item (in the CKY case, left, right and symbol). As a result, it was filtering out one of the two ways for generating the VP (hacks something somewhere). Now, at this time, I didn't realise that was the cause of the error, so what I did was to disable the uniqueness criterion... and by doing that, I got 4 derivations and not two. Until I discovered the bug, I was flipping back and forth between too many derivations and too few.

So now I have the two derivations I want, but I have a sneaking suspicion that I'm not really allowed to call the resulting algorithm CKY because now I have two VP chart items, when I should really have one. This leads me to wonder if I need to revise my backpointer mechanism so that the generic chart parser can merge two items which belong to an equivalence class (i.e. that have the same essence)... But this makes me a little nervous because I want to preserve a sort of orthogonality. I don't want to force people to use packing, if for whatever their reasons, their algorithms do not support it.

But I dunno. Maybe this generic packing mechanism is harmless. And people could also rig things so that the essence of a chart item is the chart item itself (define essence as id)... which would mean no packing.

Hmm... well, thanks, rubber duckie. I think I've just talked myself into a solution.

I need to be more patient, though. I'm being a bit too eager to release this library and get the Haskell NLP community started. Slowly and surely.

genchal half-day

Been doing genchal stuff all week.

Seem to have come down with a cold, so I'm heading home early to de-headache myself. I suppose it's mild enough that I can just hack my way through it (as I have been this morning), but eh.

haskell nlp sneak preview

The Haskell NLP project on the {code,projects}.haskell.org has been created! So far, we have two darcs repositories (chartparser and hs-giza-pp), a mailing list and a trac instance, but no static webpage, nor wiki content nor users.

The goal of Haskell-NLP is to make Haskell a more attractive language for natural language processing (research and teaching) by putting together tools and libraries for general use.

The mailing list and wiki will be used to build up an eventually community of Haskell-using NLP folks. The directory http://code.haskell.org/nlp will serve as an incubator for any small projects or libraries that are too small to stand on their own. The issue tracker will for proposing new haskell-nlp projects, and also to serve as a tracker for any projects hosted under the incubator.

genchal JSON

The Pragmatic Programmer book reminds us that "short cuts lead to long delays"... something I'm experiencing now adapting some work from last year's genchal stuff to this year. So instead of carrying on business as usual (prolonging the pain and ugliness), I'm going to be experimenting with JSON as an intermediary format between various bits of my evaluation toolchain. No more making stuff up quick and dirty... let's aim for something slightly more extensible.

full day

Managed to get in early today. I think it helped.

profiling

I'm getting a little bit more comfortable with the GHC profiler, actually managing to use it somewhat successfully to track down a stack overflow in my code (also learned a little bit more about laziness, thunks, tail recursion on the Haskell wiki).

The 6 columns of numbers you see can be a bit overwhelming at first, but there's really nothing to it... just think of it as pairs: (no, entries) (raw time, raw mem) (total time, total mem). The manual calls it "inherited" which can be a bit confusing, because what it really means is the time including your kids... backwards inheritence.

Haskell NLP releases in the pipeline

I have received authorisation to release my Haskell stuff. So I hope to have three packages out soonish:

• hs-gizapp - a Haskell wrapper around GIZA++ (now released)
  
• chartparser - generic chart parsing library with debugger and parse tree generation
  
• scfgtools - decoder, parser and rule extractor (no stats yet, sorry... also, parser still broken)

I have also requested a project called "nlp" on code.haskell.org as an umbrella for the Haskell NLP community, which I intend to start at some point if nobody else does... because dangit, Haskell is useful and stuff.

packing and debugging

I've extended NLP.ChartParser with (a) some notion of packing and (b) some notion of unpacking :-)... well rather I've made it so that every chart item must have a list of backpointers. The library provides a generic parse tree extractor. Here is the fragment of a derivation tree using dotted CKY:

[complete] VP -> V NP ⦁ (1,3)
|
+- [complete] VP -> V ⦁ NP (1,2)
|  |
|  +- [axiom] VP -> ⦁ V NP (1,1)
|  |
|  `- [scan] V -> hacks ⦁ (1,2)
|     |
|     `- [axiom] V -> ⦁ hacks (1,1)
|
`- [scan] NP -> something ⦁ (2,3)
 |
 `- [axiom] NP -> ⦁ something (2,2)

The idea is that if you want to produce a derived tree, maybe having the derivation tree will be useful (I'm using derivation tree here not necessarily in the TAG sense, but to mean the relationship between chart items via their backpointers).

Heh... one trick I want to add to the debugger is a command that prints out the derivation tree for a given chart item. Should be easy. Just need to assign an id to each chart item and let the user type in something like "tree 43"

I have to be careful not to get too deep into extend NLP.ChartParser (patches welcome! especially now I think the debugger is usable enough for people to get the idea and start extending it). I'm just trying to make it useful enough for me to do my SCFG stuff, and also something that I can release. I do hope that I manage to pull this off... and that it actually turns out to be useful for somebody.

pretty brain-dead

I've gone stupid(er) today.

earley-ish algorithm

I'm pretty sure my algorithm from yesterday is wrong (plus it has lots of typos, below is a slightly more typo-free version, plus a little extra work with indices to try to minimise the wrong-ness).


The parser can be wrong for two reasons: it accepts too few things and/or it accepts too many. I think the latter is true. I suspect you can fool my algorithm into accepting pairs of strings where one side of the grammar accepts the left string, and one side of the grammar accepts the right string, but the pair of strings should not be accepted together. There are some choices I need to make here:

• pore over the WASP and Joshua source code - look for references to algorithm used
• ask on the Joshua mailing list
• ask a local grown-up - this may be a great option since there are some local grown-ups who are sure to be able to give me good advice, but I'm... err... feeling shy
  
• decide that I don't care if my parser is too liberal (and just be sure not to advertise this as a working SCFG parser, but something works enough for me).

fancier debugger

Following the theme of doing stupid but useful things, I seem to be re-inventing the GenI debugger (because I'm trying to figure some stuff out about SCFG parsing). Rather, I've taken my SCFG-specific debugger from a couple of days ago, and moved some code around so that it's generic to anything that uses NLP.ChartParser. (By the way, If you want to teach a parsing course, I think my debugger could be useful for you (although at this stage, you're probably better off with NLTK).

The new debugger is text mode for now. You type in commands to it.

example step

--- chart 5 --- (9 items)
ChartItem {symbol = "VP", beforeDot1 = fromList ["x2"], afterDot1 = [], indices1 = (1,2), beforeDot2 = fromList [], afterDot2 = ["y2"], mIndices2 = Just (0,0)}
ChartItem {symbol = "S", beforeDot1 = fromList ["NP","VP"], afterDot1 = [], indices1 = (0,2), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Just (0,0)}
ChartItem {symbol = "S", beforeDot1 = fromList ["NP","VP"], afterDot1 = [], indices1 = (0,2), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Nothing}
...

--- agenda 5 --- (1 items)
ChartItem {symbol = "VP", beforeDot1 = fromList ["x2"], afterDot1 = [], indices1 = (1,2), beforeDot2 = fromList ["y2"], afterDot2 = [], mIndices2 = Just (0,1)}


Hit enter for next step or type 'help'

the command set so far

help
Display commands
----------------
help            : print this help
agenda          : show the full agenda
chart           : show the full chart
filter P T value : P = {agenda,chart}, T={symbol}

Navigation commands
-------------------
last            : jump to the very last step
quit            : (self explanatory)
next INT        : (self explanatory)
start over      : (self explanatory)

Hit enter for next step or type 'help'

trying out a filter

filter chart symbol S
--- requested filter --- (4 items)
ChartItem {symbol = "S", beforeDot1 = fromList ["NP","VP"], afterDot1 = [], indices1 = (0,2), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Just (0,0)}
ChartItem {symbol = "S", beforeDot1 = fromList ["NP","VP"], afterDot1 = [], indices1 = (0,2), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Nothing}
ChartItem {symbol = "S", beforeDot1 = fromList ["NP"], afterDot1 = ["VP"], indices1 = (0,1), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Nothing}
ChartItem {symbol = "S", beforeDot1 = fromList [], afterDot1 = ["NP","VP"], indices1 = (0,0), beforeDot2 = fromList [], afterDot2 = ["VP","NP"], mIndices2 = Nothing}
Hit enter for next step or type 'help'

I could go crazy with the filter and write a fancy parser for things so that you can say things like "show me the chart items with symbol S and whose left indices are between, etc etc"... which I may end up deciding I need to do.

code more?

Maybe the key for me is to understand that I understand things through the process of coding. So if I want to do or to wrap my head around anything, I should try to frame it in terms of "what code can I write?"... I dunno if that's going to send me on a lot of wild goose chases, though, the kind of thing where I think I'm productive because I'm doing lots of stuff, but in reality, not actually accomplishing anything.

scfg parser, lazy evaluation

wanted: scfg parser

Ok, parsers exist (there's Joshua and WASP to choose from, both in Java), but what I want is a parser recipe, i.e. an general algorithm for parsing SCFGs (none of this normal form crap) as a deductive proof system. And yes, on further thought, of course my proposed algorithm from yesterday was wrong (what else would it be).

my second attempt

Here's my second attempt at making a straightforward adaptation of the Earley algorithm from CFGs. It's probably wrong, this being something that's best left to the experts, but I guess it was fun to try. It seems to be working on some examples I have, for example, of a backwards grammar ("one two three" vs "trois deux un"). Note that dash means 'unset' and question mark means 'don't care':



It doesn't exactly match my implementation (which is why it was useful to specify the thing twice, once in Haskell and once in LaTeX). I've highlighted the bits where I think something special happens, i.e. not just business as usual.

why lazy evaluation rocks

It helps you write simpler, more orthogonal code, i.e. keeping unrelated bits of logic separate from each other.

Here's the (text) debugger for my chart parser:

debugger :: Scfg -> String -> String -> IO ()
debugger gram s1 s2 =
 forM_ steps $ \s -> do
   putStr . unlines . map show . chart $ s
   putStrLn "Hit Ctrl-C or press enter for next step"
   getLine
 where
  steps = iterate (chartStep config) initSt
  (config, initSt) = initStuff gram (s1,s2)

Get it? The key is the iterate function. steps is an infinite list of chart steps... it's what you get if you keep applying the chartStep function to the previous element in the list (getting a new chart step). Once you have an infinite list (lazily generate), you can generate bits and pieces of it as you go, for example, on each "press enter to continue".

And here are the interactions:

Hit Ctrl-C or press enter for next step

Followed by:

ChartItem {symbol = "S", beforeDot = fromList [], afterDot = ["NP","VP"], bSide = False, left = 0, right = 0}
Hit Ctrl-C or press enter for next step

And then...

ChartItem {symbol = "NP", beforeDot = fromList [], afterDot = ["Det","N"], bSide = False, left = 0, right = 0}
ChartItem {symbol = "S", beforeDot = fromList [], afterDot = ["NP","VP"], bSide = False, left = 0, right = 0}
Hit Ctrl-C or press enter for next step

Etc...

three minor ah-hahs

chart parser

Rather than asking each chart parser to supply separate rules which make a chart item interact with an agenda item, (and then a separate set of rules to extend agenda items by themselves, e.g. Earley predict or scan rules), we should just ask them to supply rules which take a chart and an agenda item, and then select whatever items it wants from the chart. This also makes it possible to generalise CKY to non-binary rules (which yes is very inefficient if you don't have dots... but useful for reducing code footprint)

scfg parsing

I need not only to have an SCFG decoder (from source language string to target language string), but a bona fide parser (parses string pairs). I guess you can implement one with a modest extension to Earley's algorithm. Just add an extra boolean field to the chart item denoting which side of the SCFG rule you are processing. The idea is that once you complete the rule on the left side, you push the dot over to the beginning of the target side (and flip your bside bit). Only when you have completed both sides do you consider the rule complete. So it's exactly Earley's algorithm except (a) your scan rules need to distinguish between scanning the source side and scanning the target side (b) you need to introduce a "hop" rule which flips the bside bit when you have half-completed. Surely somebody else has this written up somewhere. Or maybe my proposed algorithm is dead-wrong for some reason.

applicative functors ftw?

I've been wishing for a while that I had a better way to do something like concatMap (\x -> map (f x) ys) xs (i.e. I want crossProductMap).

Then I realised that this was the same thing as

do x <- xs
   y <- ys
   return $ f x y

Then I realised that this was the same as liftM2 f xs ys

... which is the same as f `liftM` xs `ap` ys (I guess)

... which is the same as f <$> xs <*> ys

I'm guessing about the second-to-last one (I've only glanced at uses of ap without understanding them fully.). Anyway, I still don't know what all the applicative functors fuss is all about, but at least now I have a small inkling about how it could be relevant to my life as a programmer (so I'll see how far I go with the f <$> xs <*> ys version. The second-to-last version (with ap, which I figured out after the last version) uses monads, not applicative functors, so I don't really see what the big deal is except for maybe a nicer operator. I'm sure I'll work it out sometime in the far future. Yay, abstractions! in any case.

SCFG decoder

Once I had a toy implementation of dotted CKY, making a toy implementation of Earley was easy (just add a predict rule, and change the axioms to be a bit more conservative). And once I had a toy implementation of Earley, implementing an SCFG decoder was... well not quite so easy, but doable.

*NLP.ScfgEarley> putStrLn $ go toyGram "the boy hacks some ugly code"
S(NP(Det(the) N(boy)) VP(V(hacks) NP(Det(some) Adj(ugly) N(code))))
S(NP(Det(le) N(garcon)) VP(V(hacke) NP(Det(du) N(code) Adj(moche))))

I'm doing things in the most naive possible way, which is to apply CFG Earley to the source rhs of the SCFG to obtain a derivation and then re-run the derivation on the other side. It's the re-running bit that gets a bit tricky for me, because the target rhs isn't in the same order as the source rhs (that's the whole point of an SCFG after all) and it may have different set of terminal symbols.

Here's the core of my ugly-ass solution:

type ForestPair a = ([Tree a],[Tree a])

nodesFor :: ForestPair String -> String -> [ForestPair String]
nodesFor (gs, ns) s =
do let matches = filter (match s) ns
-- no matches means terminal symbol, which is fine
g <- if null matches then return (Node s []) else matches
return (g:gs, delete g ns)
match x1 (Node x2 _) = x1 == x2

I'm probably not going to succeed in explaining this, but that's ok. The tree unpacking algorithm does recursion twice, once to obtain the list of kids, and once to obtain the list of siblings. (Keep in mind that the chart only stores a single CFG derivation). The whole idea is that you recursively obtain the list of kids for both the source and target side (rhs1 and rhs2). The list of kids for the target side will be in the incorrect order, that of the source side, but it will contain the correct subtrees. How do you re-arrange these trees in the target order? By selecting a rule from the SCFG whose source rhs corresponds to the right hand side of the current chart item. Rather, you use the nodesFor function defined above to traverse the target rhs (rhs2) of the rule. At each non-terminal symbol you select the appropriate sub-tree from the list of incorrectly ordered nodes. At each terminal symbol, you generate a leaf.

helper :: String -> [String] -> Int -> Int -> [ForestPair String]
helper c1 cs1 l r =
do -- boring details elided...
(kids1,kids2u) <- case tiKids1 of
          []       -> return ([],[])
          (kc:kcs) -> helper kc kcs l rti
-- boring details elided...
rule <- if null tiKids1
    then return $ ScfgRule c1 [] [] -- terminal only
    else filter (\x -> scfgRhs1 x == tiKids1) rulez
kids2  <- (reverse . fst) `fmap` foldM nodesFor ([],kids2u) rKids2
-- boring details elided...
(sibs1,sibs2) <- case cs1 of
         []         -> return ([],[])
         (c1b:cs1b) -> helper c1b cs1b rti r
let node1 = Node c1 kids1
node2 = Node c1 kids2
return (node1:sibs1, node2:sibs2)

Sorry if that didn't make any sense. It probably won't make much sense to me next month, and the complicatedness of it probably means that I haven't deeply understood things yet.

Thankfully, I now know about useful tricks like (a) using the list monad to handle non-determinism Prolog-style and (b) using fmap to promote functions into a monad (which avoids a lot of boilterplate let x = ). Tricks like this make the code a bit cleaner, with fewer moving parts. (I like to use the idea of moving parts, because lines of code is not always relevant, a moving part is an ill-defined "conceptual" line of code, some "thing" happening... there must be an official word for this).

An interesting thing I notice about my lack of Haskell-fu is that whenever I have trouble understanding how to do something, I will tend to use a lot of explicit recursion. I need to grasp the moving parts as a sort of handrail. Once I've got things down as a solution, or have had some time to get a bit of recul wrt the problem, I may eventually realise that actually these 12 lines of code (or whatever) can be replaced by a single higher order function and a little bit of business logic. But to begin with, at least, I'll code like a newbie.

NLP.ChartParser - generic chart parsing library

I've mentioned before that I've grown scared of programming lately. Somehow this week, I managed to convince myself that it was probably a good idea for me to implement my own SCFG parser and that there wasn't really any way around it.

My first attempt (months ago) was a failure because I kept trying to cut the code out of GenI and make it generic. Too much stuff going on there. So yesterday, I decided that the best thing for me to do was to start from scratch. Even if the result ends up just as complicated as GenI, it's worth trying the new path, in the hope that a fresh perspective may lead to something cleaner.

The new NLP.ChartParser purports to be a generic chart parsing library. You feed it axioms, inference rules and goals, and it does the chart+agenda manipulation for you. In its primitive stage, there is no parameterisation of the data structures (chart and agenda are lists), only of the core parsing algorithm.

The core of this library is:

chartStep :: Eq a => Config a -> Status a -> Status a
chartStep config st =
 case getAgendaItem (agenda st) of
   Nothing -> st
   Just (aItem,agenda2) ->
    let oldChart = chart st
        cItems = compatibleItems config aItem oldChart
        nItems = scan config aItem ++ concatMap (combine config aItem) cItems
    in st { agenda = nub . notAlreadyInChart oldChart
                   $ addToAgenda nItems agenda2
          , chart  = assert (not $ aItem `elem` oldChart)
                   $ addToChart aItem oldChart }

-- | If you wanted to implement some kind of fancy graphical interface
--   you could consider using iterate chartStep
chartParse :: Eq a => Config a -> Status a -> Status a
chartParse config = helper . filterAgenda
 where
  filterAgenda st =
    st { agenda = notAlreadyInChart (chart st) (agenda st) }
  helper st
   | isAgendaEmpty st = st
   | otherwise        = helper (chartStep config st)

I would love to make a BSD-licensed copy of this available on Hackage (provided it is compatible with University policy for me to do so... although if I was really being disciplined about policy, I wouldn't be pasting code on the blog... I seriously doubt UoB would care about me dumping some decades old stuff online though). If this is possible, I'll also throw in my implementation of CKY and dotted CKY (note: with chart sharing only and no equivalence-class based packing, so not proper CKY).

All together, it took a day of hacking, 80 lines of code for NLP.ChartParser, 130 lines for toy CKY and 200 lines for dotted CKY, including toy grammars). So for crying out loud, Eric, stop being so scared of everything.

Note that NLP.ChartParser might never evolve into something suitable for production use (I hope it does), but I don't really care, because it may turn out to be useful for prototyping chart parsers or for teaching.

*NLP.ToyDottedCky> putStr $ go toyGram "the boy hacks some code on a machine"
S
|
+- NP
|  |
|  +- Det
|  |  |
|  |  `- the
|  |
|  `- N
|     |
|     `- boy
|
`- VP
   |
   +- V
   |  |
   |  `- hacks
   |
   `- NP
      |
      +- NP
      |  |
      |  +- Det
      |  |  |
      |  |  `- some
      |  |
      |  `- N
      |     |
      |     `- code
      |
      `- PP
         |
         +- P
         |  |
         |  `- on
         |
         `- NP
            |
            +- Det
            |  |
            |  `- a
            |
            `- N
               |
               `- machine


S
|
+- NP
|  |
|  +- Det
|  |  |
|  |  `- the
|  |
|  `- N
|     |
|     `- boy
|
`- VP
   |
   +- VP
   |  |
   |  +- V
   |  |  |
   |  |  `- hacks
   |  |
   |  `- NP
   |     |
   |     +- Det
   |     |  |
   |     |  `- some
   |     |
   |     `- N
   |        |
   |        `- code
   |
   `- PP
      |
      +- P
      |  |
      |  `- on
      |
      `- NP
         |
         +- Det
         |  |
         |  `- a
         |
         `- N
            |
            `- machine

various notes

implementation progress

I now have a small Haskell wrapper around GIZA++. It only outputs word alignments. I've also extended my Chiang 2005 implementation with one constraint, that

If there are multiple initial phrase pairs containing the same set of alignments, only the smallest is kept.

This is one of those devil-in-detail moments: define small? define same set of alignments? I went with size of source phrase + size of target phrase, and went with considering the powerset of alignments for a given pp.

I'd be happy to release it (provided that University policy allows me to do so) soonish in the hopes that other people can improve it.

lambda SCFG

Ok, now I think I understand this better. Djame, you're right. C'est pas complique. I just like to confuse myself for nothing.

Structured questions to help me understand Wong and Mooney's λ-SCFGs:

1. Where do functions and their arguments come from?
   
   • functions come from the expansion of a non-terminal symbol. The RHS2 of each SCFG rule is a lambda expression (λx₁..λx_n.β). (note that n can be zero, I think)
   • the arguments come from a requirement in the formalism that "Each non-terminal A_j in β is followed by a list of k_j arguments (k_j can be 0)." In other words, the arguments come from the top down
2. When does function application take place?
   • at the end of SCFG derivation (nothing special). Presumably the lambda expression associated with the start symbol of your grammar must not have any lambda operators
   • there is no "outermost" lambda term and therefore no "outermost" argument (i.e. corresponding to the start symbol)... You traverse the expression produced by derivation and reduce any lambda terms you see inside of that expression:
     

     whatisthe(x1,
     (λa1.smallest(x2,(
     (λb1.state(b1))(a1),
     (λb1.λb2.area(b1,b2))(a1,x2)
     )))(x1)
     )
     

   • My first instinct reacting to the above is "can you do that?"... but then I guess, "why not?"
     
3. Why is it possible to have free variables in λ-SCFG lambda terms?
   • I'm still a bit shaky on this one.
     
   • Consider the use of smallest below. How do we guarantee that if we try to parse a sentence like "which state has either the smallest river or the smallest mountain" that we generate a new instance of the size variable (x₂) for each one?
   • Perhaps one answer seems to be that λ-SCFG requires that you systematically rename all the free variables in a lambda term before doing function application. (Well, I guess in case the name conflicts with a variable name either free or bound in the argument is enough). Yeah... I guess that's enough to guarantee that we're generating a new instance of each free variable per use. I think this is why I was confusedly trying to say that they were like let..in.
     
   • Hah, I had circled x₂ but of course x₁ is also free above

limits 1 (inversion and rotation)

I like to map myself out, try to understand my shortcomings (and should I be so lucky, strengths). Here are two related thing I've noticed about myself:

1. I have a very hard time with things that have polarity, for lack of better term. True vs False, Plus vs Minus, Source vs Target, Then vs Else, Left vs Right. I cannot cope well with inversions or inversions of inversions. I'm always getting things backwards. This is why things like subsumption are a nightmare for me (X subsumes Y, or X is subsumed by Y). I get the idea, (I think), but putting potentially inversible things together and I'm bound to screw something up. Unfortunately, you can't type-check your way around a boolean-inversion problem.
2. I have a hard time dealing with rotation. I think this actually the same problem as #1. I cannot mentally rotate things (or ideas!) and reason about the results. When I look at a map, it takes me hours to reason my way through things. I have to physically turn the map around and still it takes me a long time to work out where I am and where to go.

If I have a clear picture of this, then I can hopefully use my strengths (few as they may be) to offset my shortcomings. The danger of course is that I attach myself to a potentially incorrect picture of myself, or one which is no longer true with the present circumstances. The other danger is taking universal things (maybe everybody sucks at inversion and rotation) and thinking them to be specifically true of myself. But I think for the case of #1 and #2, I am probably worse at it than my peers.

P.S. none of this explains my confusion of the lambda SCFGs, probably another kettle o poisson.

initial phrase pairs (Chiang 2005)

Chiang says his initial phrase pair criteria are the same as Och and Ney 2004. Beware of bugs in my very naive implementation below:

import Control.Monad (guard)

data WordPos = WordPos String Int deriving Show
data Align   = Align WordPos WordPos deriving Show
data PhrasePair  = PhrasePair (Int,Int) (Int,Int) deriving Show

phrasePairs aligns fs es =
do fp1 <- [ 0 .. fmax ]; fp2 <- [ fp1 .. fmax ]
   ep1 <- [ 0 .. emax ]; ep2 <- [ ep1 .. emax ]
   let f_range = (fp1,fp2)
       e_range = (ep1,ep2)
   guard (  any  (inRange     f_range e_range) aligns
         && none (eOutOfRange f_range e_range) aligns
         && none (fOutOfRange f_range e_range) aligns
         )
   return $ PhrasePair f_range e_range
where
 inRange (fp1,fp2) (ep1,ep2) a =
   let Align (WordPos _ fp) (WordPos _ ep) = a
   in  fp >= fp1 && fp <= fp2 && ep >= ep1 && ep <= ep2
 eOutOfRange (fp1,fp2) (ep1,ep2) a =
   let Align (WordPos _ fp) (WordPos _ ep) = a
   in  (fp >= fp1 && fp <= fp2) && (ep < ep1 || ep > ep2)
 fOutOfRange (fp1,fp2) (ep1,ep2) a =
   let Align (WordPos _ fp) (WordPos _ ep) = a
   in  (ep >= ep1 && ep <= ep2) && (fp < fp1 || fp > fp2)
 fmax = length fs - 1
 emax = length es - 1

none :: (a -> Bool) -> [a] -> Bool
none f = not . any f

Note: it's not obligatory to use a (list) monad here; I just thought it was clearer to do so. My first implementation was just using a list comprehension, which Pythonistas should be comfortable with. (The trick, for non-Haskellers is to read the "guard" as "such that")

Edit 18:30I also have a toy implementation of rule extraction (without the filters), I think.

giza giza giza

There is a chance I'm going to have to teach myself how to use GIZA++, a prospect by which I am absolutely thrilled.

It's one of the most disheartening aspects of this statistical stuff, the "turning knobs" bit. I don't know what all these parameters are, nor why I should care about them nor do I feel able to learn. I imagine that part of what makes the statistical stuff smart is that they have developed self-turning knobs (for example, the minimum error rate training used by WASP).

But that doesn't answer my questions for what to do with this GIZA stuff. I see a sea of parameters. Now what? Now perhaps we see what we can do with the defaults. Or we copy the defaults from somebody else. Or we focus on more down to earth problems like what formats GIZA likes things in.

Meh

day of refactoring

Been cutting my way through the Reg08 summary code from last year. Got rid of a bunch of explicit HTML table generation in favour of my tabular library. The library is really not sophisticated enough. It doesn't handle cell merging, for example, or decorations on cells. I've also had to extend some of it so that it no longer assumes that cell and row headers are strings (the result is more complicated -- you have to supply rendering functions for headers -- but flexible).

End result is much cleaner though... Now we're just generating slightly more abstract tables and we have the rendering of those tables as an orthogonal layer. This means we could go render them in LaTeX if we wanted, for example. I'm not really sure why I did this refactor though.

Part of it is just the standard fussy coder personality... can't stand to leave a mess behind. Part of it is also because I know that I'll be extending this code for the genchal stuff this year. Refactoring this code lets me refamilarise myself with it and also simplifies my job for this year and perhaps subsequent ones.

The code is still pretty smelly, just less so this year.

Anyway, that's 3 uses for the tabular library so far: eval stuff for generation, eval stuff for genchal and darcs benchmarking. I'm glad I spent the time making this library.