equivalence-class based packing for GenI - node counting idea

Here's an idea that came to me when I was quite literally sitting around doing nothing.  Ah yes, the whole business of getting ideas for things you are not working on.

GenI is a chart generator.  It has a notion of agenda/chart-based control to order operations and sub-tree sharing (basically for free by using Haskell), but what it lacks, crucially is a notion of equivalence-class based packing.  Packing is extremely important because it's what allows you to control the combinatorial explosion of intermediary chart items as you explore the search space.  In particular, in GenI, we're interested in exploring the whole space (enumerating all possible parses), so we're not particularly after any sort of pruning.  Really, the chart is all about making sure we don't do a lot of stupid redundant work.

What you want your equivalence classes to do is partition your set of possible chart items in such a way that lets you compare the subsets with each other rather than the individual items within.  So to illustrate example, imagine you're starting out with 8 items (in classes A, B, C) :

• A: 2 items
• B: 3 items
• C: 2 items

If you were just doing straight parsing without any sort of equivalence classes, you're going to be deriving 2x3x2=12 items.  But if you use the equivalence classes, you only need to do 1x1x1=1.  At the end of the day, you're still going to have 12 items when you expand the set, so what have you gained?  Well, I'm still a bit fuzzy on that to be honest.

Part of my answer is that it saves you work when you have chart items that don't lead to any derivations. If you have say another 4 items that can combine with these 12, that gives something like 48 items to sift through (before you work out that you can only keep 12 of them).  With equivalence-class packing at least, you avoid this sort of explosion.

I'm not sure if that's the whole story.

Anyhow...

There's one way I knew to get equivalence-class based packing for GenI, and that would be to implement a CKY/Earley parser for TAGs.  I tried that during my 2nd year of the PhD, but the whole thing sort of fell apart because my coding sucked (I think now that I know about the Zipper, I can have a much better chance).  Nevermind, it gave me a chance to refactor the hell out of the code.  I still think it'd be good to get back to it... but what if there was a simpler way?

the plan

First, let's make some simplifying assumptions:

• no substitution - we're in an adjuction only grammar (which is easy because GenI does 2-phase generation only)
• auxiliary trees all have the same root node category (we can relax this later on)

The problem I was struggling which trying to work out how packing would work is that it's not just good enough to partition your set of chart items.  What you to do is to partition them in such a way that the result of combining two equivalence classes can be derived from the classes themselves and not the items within them.  Coming up with any old scheme for putting your chart items into bins is the easy part.  Now what happens when you plug two of those bins into each other?  And if you do come up with such a scheme, is it going to chunk your inputs so that you get that factorisation thing going on, or are you just going to partition into a bunch of singleton sets?

And here's the scheme I just thought of:

Two items are in the same equivalence class if they have the same semantics, and the same number of nodes  (of a given category X) which can receive adjunction

If you do adjunction with this scheme, all you have to do is take the union of the semantics (à la Martin Kay) and the sum of the numbers of the nodes (minus 1 or something like that).  And if you want to deal with more than one category, just do it in phases.  First focus on one category, derive everything you have.  Then pick a new category and re-pack everything into a different chart.

I hope that this scheme is broad enough that it actually divides our chart into non-singleton sets. 

Will it work? Will it work? Will it work?

I can't wait to find out.

Too bad I don't actually have time for GenI hacking.

folds and subsamples

Ah, one bit of clumsy language (I always get terminology subtly wrong like this).  I noted that it's a good idea to store your folds as text files and not as a directory tree of copies of files.  Actually what I really meant is that it's a good idea to store the subsamples, ie. the subsets of your partition.  You could also store the folds, but duplication root of all evil.

ABC subdirectory permutation

This is the sort of problem I find myself frequently confronted with, stuck on and bored by.  I feel like I've seen this enough times that I should have knocked out a set of standard tools to just get it right so I can move on with the interesting bits of the research, yet despite the handful of variations I've experienced, it always feels like a new problem wanting its own ad-hoc solution.

It's a simple permutation thing, a question of best-practice in laying out your directory.  You have a set of texts which can be characterised by N dimensions:

1. primary method (the thing I'm evaluating, eg. corpus-acquisition technique)
2. secondary method (some other source of variation, eg. generation system)
3. fold
4. evaluation set (training, development, test)
5. subcorpus

The first time I saw this problem, I only had #1, #3 and #4.  Then one day I was introduced to an evaluation which cared about #1, #4 and #5 (intersection between #4 and #5, it's important when dividing your corpus into subsets that you preserve the distribution of files in subcorpus, so if your corpus has 10 As, 40 Bs, and 30 Cs, and you're splitting into tenths, you need to make sure you still have 1 A, 4 Bs, and 3 Cs).  Now I think I'm dealing with most of these (except #4).

My failure to generalise over this problem, the sense that I'm continuously reinventing wheels that I'd previous reinvented, makes me feel stupid.

Some tricks I've learned along the way:

• Store your folds as a list of filenames, not the files themselves (obvious in hindsight!).  
  1. If you're doing repeated random sub-sampling, you save the space wasted by having more than one copy of the same file.  OK maybe you could also have avoided this by using hard-linking, but then what happens when you copy your stuff to another filesystem?  Do the hard-links get preserved? (Maybe, I dunno.  To be clear, I don't mean from filesystem A to filesystem B, but do the links between A/X and A/Y get preserved when in B/{X,Y}?  A simple ls -i can tell).
  2. It reduces the risk of human error that redundancy introduces.  Duplication is the root of all evil.  These arguments don't apply maybe if you're partitioning your data for cross-fold validation (no duplication), but there's still
  3. It makes it easier to communicate your folds.  For example, you do sanity checks like "does my partitioning of the fold into a further training and development set reproduce the original fold" with simple cat and diff.
• Handy tools that somebody else has written. You don't need to knock out your own 5-minute script:
  • split - split a file equal-sized chunks (useful for partitioning)
  • unsort - randomise lines in a file (randomisation)
• Version control randomisation. This goes back to the third argument for why you should store your folds as a list of filenames. You want to make sure you can reproduce every single step of what you do. So if you randomly partition your data for cross-fold validation, save the files containing your list of filenames
• Build systems can be abused as test harnesses.  I've been experimenting with an implementation of DJB redo and am loving it!  

Right now, I'm staring at my monitor dithering over various subdirectory layouts for my test bench.  Do I want my data divided into

• Primary-method/Secondary-method/Fold/Subset (tech-A/gen-I/fold-1/training)
• Fold/Subset/Primary-method/Secondary-method (fold-1/training/tech-A/gen-I)
• Fold/Primary-method/Secondary-method/Subset (fold-1/tech-A/gen-I/training)

Only 24 permutations to consider, I guess.  Which layout is going to maximise sanity-preservation?  The endless struggle.  Go on, you do the science.  I'm still trying to work out how to arrange my lab bench.  I wonder if I'm the only one that has issues with this.  It's just so embarrassingly inconsequential yet it feels like one of my main pre-occupations.

Edit Stepping away from the problem I realised that actually, I once inherited a solution to the first version of the problem using Fold/EvaluationSet/Text.Primary-Method (slightly outside the box -- who says it all has to be subdirectories)?  Still doesn't solve the Secondary method.  In a previous blog post, I wanted to compress the dimensions by merging the Fold and Primary method, but in hindsight, that doesn't make things any easier.

double/parallel symlinking

Here's a little pattern that some people might find useful.

Scenario

You are primarily working on a shared file system plus a personal hard drive.  You have source code and data/crunchy-chrunchy-work.

• The shared file system is backed up and also makes for easy accessibility for colleagues. 
• The disk drive is way faster (lower latency), which makes a difference if you're going crunchy-crunchy over a lot of files.  It also has more space (in 9 years working in some lab/university or another, we've never had enough space on the file server)

Basic setup

So how you do you store things?  The pattern I'm starting to take is: 

• /shared-space/my-project-dir (on shared)
  • src
  • etc
  • README
  • ...
  • symlinks to /hardisk/my-project-dir/{data,tmp}
• /harddisk/my-project-dir
• data
• tmp
• symlinks to /shared-space/my-project-dir/{src,etc,README}

I wouldn't go so far as to call this a best practice.  The key here is for both directories to mirror each other  (which is an important detail that I key forgetting) in terms of tree depth.  The reason for this is to allow you to preserve the illusion (for your own sanity) that this is all one tree.  For example, you want to be able to be in the src directory and access the tmp directory using a relative path like "../tmp/foo/bar".  Likewise, you also want to be able to do the reverse from the tmp directory.

If I'm not thinking carefully about it, my links will tend to be assymetrical.  Rather than creating a parallel my-project-dir under /harddisk, I'll just like /shared-space/my-project-dir/tmp to something like /harddisk/tmp-for-my-project-dir... which breaks the minute I try to round-trip from src to tmp and back with relative paths.

prone to confusion - filename extensions

One of the tensions I face in building up NLP pipelines is extensions for filenames.  Should extensions reflect a sort of format, or a stage of processing?

My code uses the latter, so I get something like:

• en
• en-selected
• en-fragments

And I can tell them apart.  They all start with "en" because they are compatible with each other in a sense.

stage of processing

• can tell the different stages of processing apart at a glance
• can dump all the files into one directory

format

The problem with the stage-of-processing approach, however is that one can get easily confused with the proliferation of extensions (wait, was that .data or .data-subset I wanted), and also it makes it impossible to use directory-wide graphical diff without writing some sort of wrapper process.

It also brings up sorts of side questions like "what if you want to skip stage 2 and pretend the output of stage 1 is the input to stage 3".  This sort of thing makes it much more natural to use format extensions.

Right now the compromise solution is to go with stage-of-processing extensions, and make copies reflecting snapshots of processing using format extensions for easier diffability, but meh

multi-annotation

For the corpus construction work, I'm finding myself in a position where I want to combine different kinds of annotation, say from a

1. domain-specific tokeniser
2. transliteration tool (iconv to strip accents)
3. lemmatiser/pos-tagger
4. named entity recogniser

For the moment, I'm keeping things real simple by just assuming a dumb pipeline (and ignoring NER).  That means making compromises like forcing ASCII text on all components, even those which are sophisticated enough to deal with Unicode, and also working with funny tokens, treating lemmatiser/pos-tagger as input to the corpus construction stuff, giving it tokens like "be_VBZ" instead of "was".

But over time I may find myself needing some sort of multi-track annotation approach because different components require different stages of input.

So I'm guessing here that I should use some sort of standoff-annotation scheme even though my needs don't really have any crossing/overlapping boundaries.  Everything is based on tokens.  I'm mainly attracted to a standoff annotation scheme because

• I want multiple layers of annotation.
• I don't want to decide in advance how many layers of processing I add (a simple column-based text format like tab-delimited would get unwieldy fast)

I'm a bit resistant to just using GATE for this (sorry, Java allergy plus a lot of my components are written in Haskell; and writing little Java stub wrapper programs is boring).  Turns out from a quick Google search that other generic tools exist (Amy Isard's slides [PPT]).  GATE is really neat and all (being able to cook up complex processing pipelines with arbitrary components is great, and I'll admit that having a GUI makes it a whole lot more discoverable), but really I just wanted to know about things like standard formats for standoff style markup.

Having glanced at Amy Isard's slides, I think I'll be trying the LT XML library next, hey maybe even make a Haskell binding to the library if the Unixy command line tools don't do what I want.

Going with the stupid pipeline first, though.

summing logs

Got a bit of hacking to do today for the corpus acquisition stuff.  Trying to work out why our sentence extraction (or deletion) depending on your POV works so badly.

Trying to evaluate results (informally) is a bit of a tricky enterprise for me.  I tend to just rely on your basic Unix text processing tools and graphical diff.  So if example, I want to see what our tool, which is supposed to delete boring sentences from a text actually does, what I'll do is to run cd before; wc -l -w *.txt and the same with cd after.  This gives me the number of lines and tokens in each set of texts.  Assuming we're working on the same files, I can then view the two word count files, finding out for example that there are no differences (which means we haven't been deleting anything), or that there are systematically zero tokens/lines in the after end... which means something has gone wrong.  In my case, both are true...

I think I've worked out what it is.  Either I was using some kind of crude method before (deliberately), or I just misunderstood some idea somewhere (likely), but in any case I've got some logarithms to sum.  Sure wish I had maths more firmly anchored in my brain.  I can think thoughts like "oh, summing logs of probabilities is like multiplying them, which makes sense if you've got a reasonable independence assumption and you want to see the joint probabilites"... but then if you push my brain just a little further "so what does it mean when take the mean of these sums" it explodes.  Puny Erician brain...