state of the thesis 2006-10-31

Not much to report for this month. I spent the whole time reading intensively (by my standards) about search strategies and chart parsing, most of it motivated by trying to understand something solidly enough that I could write about it without this nagging self doubt in the back of my mind (wait... do I really believe that?). The month has been a long struggle to convince myself of some very basic things. I have produced a total of 10 pages (that's 11 minus bibliography), which is rather pathethic, especially considering that I'll probably have to toss in all in trash when it's been looked over by somebody else. Next month, I'll be back home... hoping desperately that I can be productive without being in an office.

agenda stuff written (words: 8772, pages: 11)

Ok, I think I have a more solid grasp of the agenda based control in shieber1988uap. Embarrasingly enough, part of my problem was that I was confusing my search tree with my syntactic tree. (Stuuuuuuupiiiiid), so of course breadth first and depth first didn't quite mean what I thought they meant. I was having trouble seeing where the non-determinism comes from because all I could see was that the order of edge availability was pretty fixed (i.e. you have to predict foo before you even have the choice to complete it). But now I see more clearly that all this just refers to syntactic ambiguity. If you FIFO, you explore the ambiguity first (breadth-first); if you LIFO, you explore the current tree first (depth-first); if you go prediction-lex-etc-rightmost, you get shift reduce (note that the shift reduce thing, the prediction rules first thing is kinda important for seeing it work).

working algorithms out by hand

Working this out has made me rediscover by old bag-of-tricks of working out algorithms from when I was still taking classes. I like this kind of stuff, algorithms for human beings. Basic point is, don't waste your time; just focus on the interesting bits.

Trick #1: Use the simplest phrases you need to illustrate the point:
Bad : The man saw the boy with the telescope
Good: Bob saw the boy with the telescope

Trick #2: Compress your phrases unless they really illustrate a point.
Bad : 0 Bob 1 saw 2 the 3 boy 4 with 5 the 6 telescope 7
Good: 0 Bob 1 saw 2 the 3 boy 4 with-the-telescope 5

Trick #3: Use first letters; choose your words so that they unambiguously correspond to a first letter (seen in neumman1994ucm)
Bad : Bob saw the boy with-the-telescope (b s t b w)
Good: John saw the boy with-the-telescope (j s t b w)

Trick #4: Pare your grammar down to the minimum possible. Refactor mercilessly?
Bad:

NP -> PN
PN -> j

Good:

NP -> j

Here's what I use for John saw the boy with-the-telescope:

S  -> NP VP
NP -> j
NP -> t b
NP -> NP w
VP -> s NP
VP -> VP w

Trick #5: Assume an oracle that can tell you if an edge is going to lead you to a dead end. If the oracle (i.e. a human being, i.e. you) tells you the edge is useless, dump it toot sweet.

Trick #6: Don't worry about order. Use order to represent things going into the chart. Use check marks to represent the order that they get removed from the agenda. No need to write things down twice, what.

unproductive afternoon

Was pretty good this morning, painstakingly working out the differences between the three variants shown in shieber1988uap. Now need to write about indexing and packing, although have some ideas still mixed up in my head. I was really hoping to make 10 kilowords by the time I headed to the states. Oh well. Guess it's not very likely.

short day, cabalised

Very short day. Was helping a friend move from 09:00 to 15:00. Spent some time chez moi lazy as hell even though I didn't actually do very much (tidy up a desk, etc). Spent about 2 or 3 hours at work, mostly goofing off - realised that while I get the rough idea of parameterising your algorithms by changing the data structure of your agenda, I don't see the concrete mapping between the structures and the algorithm behaviour. Another one of those moments where you think you understand something, and then when you sit down and you actually try to write it up... HUH?

Other than that, at home, I noticed on the tutorial How to write a Haskell program that Cabalising your software is VERY VERY easy. It took me less than ten minutes. So you have no excuse. If dumb eric can do it, so can you. Just copy the templates from the wiki, open up the cabal docs when stuck. I'll post a link to my Cabal file when I have pushed the patches in.

lazy eric (words: 8564, pages: 11)

Got in late, and sort of bummed around today. But I think I understand the agenda-based control stuff better.

progress in the morning (words: 8198, pages: 11)

Had a little bit of clarity this morning and was able to move forward a little bit on the chart parsing stuff. Managed to think myself out of a little bit of confusion about subsumption based checking and restrictors. Part of me was thinking "gee: wouldn't subsumption based checking make restrictors sort of unnecessary? Because you can block an infinite looping prediction just the same way you avoid left-recursion for context free grammars". Then I sat down and thought about it for a while, and noticed that people who talk about subsumption based checking also talk about restrictors, so that can't be it [He's a slow one, the eric], and then though about it somewhere and realised that (A) i'm an idiot (B) you still need restrictors, because with unification grammars, it's always possible to make infinite looping predictions which don't have a subsumption thingy. Take your basic subcategorisation list for example. It's sooooo simple: X does not subsume Cons foo X. End of discussion. So hey, at least we got that cleared up. I get the impression that for anybody else, this kind of thing would have been like "no duh, obvious!". In fact that's all I've been doing the whole month. Getting stuck on some stupid question that I don't even know how to formulate, and when I finally get around to putting my question into words, thinking about it really hard (sifting through papers very inefficiently, trying in vain to find a response), finding finding the answer, and then saying "golly! that should have been self-evident". Yeah, that's the issue, see? I spend a lot of time worrying about the self-evident.

Now the thing I'm cracking my head over is agenda based control. I've grown up with agenda based control, and it's very hard for me to imagine a world without it. Sure, I could talk about using the agenda to make your control more explicit and easier to parameterise, but what I have a hard time doing is wrapping my head around what exactly an agenda buys you besides this. Like, really, what's the alternative? The Prolog NLP course has been helpful for this once more, in that here I see an agenda-less parser. But the thing is that I don't want to mix up the notion of passive/active items with the agenda or no agenda. It's really a matter of dissecting everything, making sure I understand really what all the pieces of the puzzle are, and precisely what happens when you do away with them. What worries me is that all this stuff is just simple undergrad to first year Master's stuff. As D once said "it took you two days to figure out left corner parsing?"

So I'm slow. Very slow. I do eventually get things and understand them well (I hope), but it takes me next to forever.

feeling better (words: 7520, pages: 10)

Feeling slightly better about the whole thing. Not making real progress yet, but (1) I actually got enough sleep last night, which is new for the past couple of weeks [been bad and not forcing myself to bed despite tiredness] (2) I think I can finally move on to talk about chart stuff instead of just search strategies. Wrote the first paragraph of the chart stuff. Mapped out the rest of it, plopped down the ideas on paper. Didn't get much else done today. Short day, off to get my carte de séjour.

recul (words: 6722, pages: 10)

Not really getting anywhere today. Going backwards even! This morning, I commented out all the stuff I felt I haven't really written, you know, the big gob of drool falling on your keyboard thing. So that lost me about a good kiloword. Been slow going today. I have once again rearranged the bu/shdga stuff, realising how silly it was of me to want to elaborate on all this bu stuff in shdga land. Excellent strategy for confusing the reader, good job! Took me a while to understand the empty head problem well enough to write about it. Just going with vanilla shieber1990shd. Am going to need some hand-holding on the German or Dutch grammar though, cuz I want to use a smaller example that they gave, really just nothing more the mininum you need to show the verb movement stuff.

Speaking of shieber1990shd, I just realised that what I've been calling shieber1990shd is in fact shieber1989shd, a similar but ever so slightly different article. Oh it's more or less the same thing, though everybody seems to refer to the former and it has a little bit more stuff, e.g. a discussion on the empty head stuff. It was funny, yesterday I was so confused because gerdemann1995sop talks about some example in shieber1990shd, and I'm like "what? where?" Oooooohhhh, now I get it...

This is quite discouraging. I've been en rédaction since forever, which btw translates to 2006-10-03. This puts me at a rate of 420 words (or 0.6 pages) a workday. I hope the only reason I'm going so slow is because that's the price of actually trying to understand things well and not just me being stupid or something. I hope it's just a small hurdle to slog through, that the rest of it will go faster, that everything will just suddenly make sense, like that one day that everything clicks and you suddenly know how to ride a bike. Cuz otherwise, this sucks. Well no, it's kinda nice when stuff that you've been hazy on for so long starts to clear up... yeah that's not so bad... but it's the excrutiating slowness of it all, that huge chunk of "huh?" that hurts so much.

crawling out? (words: 7226, pages: 11)

Spent this morning rearranging the bottom-up stuff, moving a good chunk of the discussion to the end of the SHD stuff. It feels a little bit more solid, both sections. What I'm stuck now on is a little discussion on the drawbacks of SHD. I'm not sure I really want to be digging out examples in German, or if I completely understand the gap/filler stuff, much less to say the movement stuff. Haven't really sat down and tried hard to understand the type raised functors. Maybe now is a good time to set this aside and move on to chart generation... I guess I sorta have some sense of closure now that the bu stuff is in a semi-stable state.

Anyway. I'm going to head home early. I think one of my problems is just being tired in general, so perhaps a good dose of doing nothing every night and then going to bed early might make me more productive. Think I've been sticking around just to go the canteen because I'm too lazy to cook, which is kinda stupid. Should probably get into the habit of making huge amount of food over the weekend and then just heating it up over the week. I'd get to have my rest and my laziness too.

not very productive (words: 6174, pages: 10)

Nah... I spent most of today goofing off. Redid my "discovering a syntactic tree" diagrams so that they are clearer and quieter (and added a bottom-up tree). Tried to rearrange things so that the bottom-up stuff was clearer and had a more cohesive narrative structure. The problem with trying to jump down to the chart stuff is that I don't have much of a sense of closure on the search strategies stuff, don't feel like it's in a state where I can leave it alone. Don't be fooled by the high word count - a lot of it is just random gibberish at the end, just me jotting down some things I might like to say about the chart processing.

Not very disciplined. Blew a good chunk of time just watching TED talks online and staring out into space.

it's just not working today

Nope.

I think I want to give up on writing the td, bu, shdga stuff for now, move on to chart parsing and go backwards. Part of me wants to scrap the whole lot and just start over, whole new approach. Problem is that I'm trying to build this up chronologically, which maybe made sense 10 years ago when all of this stuff was still fresh and in context. But now, 2006 I should maybe step back and lay it out differently. Here are the basic points: (1) you want an approach that combines goal-directedness from top-down processing [i.e. get your logical form as instantiated as you can] with immediate exploitation of lexical information from bottom-up processing. I can't quite argue the goal directedness stuff because I just don't have the practical experience and can't poke at the algorithms in my head to see how they would behave in real life (2) you want a head-driven approach for generation instead of left-to-right ordering. LR sort of works for parsing because you're constrained against your input string, but in generation, you don't have an input string, so you're just going to sit around generating stuff you don't even know if you can use. A head-driven approach makes more sense because the semantic heads have their semantics already instantiated, meaning more stuff to constrain against. More variables given nice constant values. I can sort of see this intuitively, but I can't argue it convincingly either (3) you want memoisation (chart) instead of backtracking -- or maybe not, some people have complained that charts are useless for generation. I need to find these arguments and understand them, and then see how they fit in the other research.

There is so much going on in the chart stuff

• Storing of intermediate results - that's the big thing, forget indices, agendas, passive and active edges, whatever. The one big thing is that you've got your intermediate results stored somewhere and you're not recomputing them
• Indices as comparison constraints -- this is only a big deal if comparing items is expensive (which it might be, say unification). The whole point about indices is that they give you an instant answer, yes or no, I can try combining these two items together. You don't have to actually try it to find out. An NLP newbie [wait... I'm an NLP newbie...] might look at this stuff and think "oh, ok, array lookup is O(1) instead of list lookup O(n)", but that's just not all that important.
• Equivalence classes - packing. These two items can merge. The consequences of packing can be sloppy - you could use it to combine two items that really DON'T have any business going together, but that's ok, because you can always verify it during the unpacking phase (analogy: prediction over-predicts and is cleaned up after by completion)
• Subsumption based blocking -- I had written this down, but it sort of seems the same as packing
• Active vs. passive edges -- I had written this down, but it sort of seems the same as indices as comparison constraints
• Agenda based approach - the ability to adjust search strategy just by changing the way you put things into the agenda and take them out

I really do not understand this stuff as well as I should, i.e. know it cold. For example, I'm still not sure I understand the relationship between chart and search. I understand that you can layer a chart onto any search strategy and make it better, but I also get the impression that somehow this matters more for some strategies than others. Like for a top-down approach on CFG: using a chart is the difference between life (bad) and death (termination, that's good). As for GenI, we combine all items together anyway, so unless you do something clever which involves NOT allowing all comparisons (substitution before adjunction, eh?), it really doesn't seem like your search strategy matters all that much. Keep in mind, we're just pacmaning our way through the items. No crazy recursion thingies going on here (unless you have empty sem), just "destructively" combining our way down. But there must be some link. Maybe I can see it making sense if you only want one response, because then you try to order things so that you get a response early and stop (hopefully the best response). But if you care about paraphrases, it seems you're exploring stuck with exploring the whole search tree/graph anyway.

I feel like such a fraud. It's so different writing for a blog, than say, your PhD thesis. You can just randomly assert stuff because you feel like it and nobody even notices. Trying to write something serious, something that you yourself are convinced by, wow that's hard... that's where you learn that you're an idiot and you really don't just don't get it. They say that perfectionists are the worst procrasinators... yeah fine I believe in "shitty first draft" theory too. But this isn't creative writing. This isn't about getting the words to fit together right. It's about not getting the basic facts down and that's the stuff I'm mired in. I can't shitty first draft my way out of that!

Haven't fit all of the pieces together in my head yet. Only thing to do is keep reading and talking to people. Find the right stuff to read, the right questions to ask.

going home early (words: 5532, pages: 9)

Wrote a basic description of SHDGA, and some discussion regarding why we see the shieber1988uap algorithm as primarily bottom-up. It's not all very solid, but in any case, moving on past the Earley stuff and straight into SHDGA was a useful way to make a little progress. You write some head-driven stuff, think about it some more and then go back and add more stuff to the bottom-up section. This goes so slowly for me (I know, I keep bitching about this) because everytime I write a sentence I worry to myself, "does that even make sense? Do I actually understand what I'm saying? Do I believe it?". Anyway, I feel like going home early today.

Oh yeah, btw, I hacked my thloria so that it doesn't do the even-page thing. For writing drafts, at the snail's pace that I go, it's really discouraging to see your page count go up in 2 page increments.... I would much rather have "1...2...3...4...5...6....7..." than "1.......3......5......7........". Of course, counting pages is kinda stupid if in the back of your mind you're also wondering - what if I'm writing the wrong thing? I don't just mean what if I'm writing it wrong, but hey, did you really need that paragraph about Earley deduction, or about restrictors? Just what is it do you think you're doing, eric?

shdga - kowthese.tex (words: 4514, pages: 7)

Sigh... well ok, I've sort of jotted down some more stuff about the bottom-up stuff... I'm still not sure I understand all the arguments about non-determinism. My main issue is that I really don't see why prediction as used in shieber1988uap fails to constrain the derivation of items. Is it as gerdemann1995sop says, that it's just because of not quite using the right restrictors, or is there something more subtle going on here? I feel soooo stupid. I feel like a third grader, I do, in that I can see procedurally how things work - I can see dots moving around in different orders, but I don't understand them deeply enough for arguments about their behaviour to actually be meaningful to me. I don't want to just rehash what all the other papers are saying and then call that an état de l'art; I want to actually be convinced by what I'm writing. When I'm writing something, it has to be because I actually believe it, not because some guy smarter than me wrote it in the past, and it kinda sounds like it makes sense, so I'll just say what he said. But then I just get stuck because justement, the problem is that I don't understand. I sorta see it for parsing ok, top-down not exploiting lexical information, bottom-up not sufficiently goal directed (i.e. given s(np(a plant), vp(iv(died)), you might waste a lot of time trying things that involve tv(plant) (instead of n(plant)), can see how the interleaved top-down/bottom-up works in parsing, yet for some reason I can't quite make the leap. Can't quite see why shieber1988uap isn't Earley enough, can't see if it's really just a problem with left-right vs. head-first scheduling or if there really is a bottom-down vs. top-down issue going on.

Anyway, I have decided to put a todo in there and just move on and talk about shdga which I understand procedurally, but don't completely see yet. I have the feeling that maybe writing about this will really help me to come to grips with the bottom-up stuff. Yeck. Moving ever so slowly.

Approach has been all wrong. Trying to brute force, frontal assault my non-comprehension, keep staring at something until you get it, when I should really be stepping aside, off the line of attack, understand something which is easier to 'get' and is sort of related to what I'm really stuck on, and then use that as sideways scaffolding to clear up the issue at hand. I spend all this time just feeling so dumb.

eric so slow (words: 3916, pages: 7)

Talked with Bertrand about Earley behaviour - he showed me a way to look at it, rewriting CKY using Earley-style syntax. In any case, we're talking about bottom-up here (Earley says top-down, but is that because he's talking exclusively about CFG? because it's not exactly the right way to look at it). Earley is just CKY with a better prediction rule, one that makes fewer predictions (but of course, the complete set).

That helped a bit. Spent some time making a little graphic for this, don't know why, just being empty-headed:



Anyway, I guess that wasn't really what I was looking for, although it did help a lot to look at things this way. I was already comfortable with the relationship between CKY and Earley because of the time I spent implementing the stuff. I guess what I'm really looking for now is what's missing in that predictor step for the uniform architecture... is generation with the shieber1988uap stuff purely bottom-up or is that actually some goal-directedness offered by that prediction step. What does SHGDA really add besides head-first-ness? Is SHGDA really just head-corner whereas the uniform architecture is left-corner-esque or does it somehow succeed in using more "top-down" information? I think I'm just looking at this in a very stupid and rigid pigeonholey way. But slowly starting to get a clearer picture.

Sigh. I'll never finish this état de l'art. I'm also worried that I'm doing a lot of writing, which is in the end going to be "too far back" and not really worth my time.

just Prolog hacking

Uhh... oops. No, I didn't get any writing done today. But I did suggest to Claire that instead of hacking on GenI this November, I would spend my time writing up instead (still the state of the art). That sort of buys me time... which I hope I won't need. Work harder, eric! Creeeeack! Aieee!

I was sort of bad today. I had walked into Claire's office, discovered and fixed a couple of minor UI bugs, namely with the input semantic box and calling ViewTAG.

We were sort of chatting about the semconst stuff, and me being meddlesome and curious, offered to have a look. So spent the morning debugging the Prolog. Turns out it was a problem in the grammar. The np nodes had only one index (idx), instead of two (idx, label) and that was causing a unification mismatch. Now we can parse "jean rêve de paul". Unfortunately, we can't seem to parse more complicated stuff. Useful exercise. Now I know how to debug Prolog better, i.e. how to use the trace information (having multi-coloured pen is useful here, red X for failures, green for depth level, etc).

Also seems like one of the problems is knowing which version of the grammar we've got. Kinda useful being able to selectively obliterate patches. One thing which seemed to be problematic was that Claire was running on a recent generation grammar, which could explain the parse failures. Spent the early part of the afternoon trying to put together a parsing grammar by obliterating some generation specific patches and seeing what happened. We believe that somewhere out there is a working copy of the grammar for parsing. But we'll need to sit down and ferret it out.

Along the way, I noticed that with one version of the grammar, we could parse the simple sentences again but not the slightly more complicated ones. (Actually, C says she has the same result with her copy...). We're back to the point where we do get a parse forest, and semantic construction mostly fails (except for Jean rêve de Paul type sentences). But I guess it's better than nothing.

Spent the rest of my afternoon looking at some more Prolog... but no luck. Probably some weird grammar problem. Anyway, that's what I get for sticking my nose where it don't belong. But I felt sort of responsible see, what with the whole darcs stuff.

new earley diagram

Tightened it up a little bit.

earley drawings (words: 3394, pages: 7)

Oops! I just managed to blow a whole afternoon playing with Omnigraffle. I was reading pereira1983pd (Parsing as Deduction) this morning, when I suddenly found myself trying to replicate the parsing process on paper. I don't know why; I see myself as pretty comfortable with the idea of Earley parsing, but I guess I wanted to make sure I really got what it is that's supposed to make it efficient. Here's what I ended up making. I was experimenting with ways to make the diagram a more effective way to communicate what's going on. Note that I have s/hit/punched/ so that I can use first-letter abbreviations everywhere (a-s-h-p-u: Agatha's husband punched Ulrich)

The first diagram (click to enlarge):


The second diagram separates the deduction steps from the picture:


I'm not sure if I was succesful or not. Maybe the original diagram in the paper is better.

restrictors

Wrote the bit about restrictors. Didn't get much done. Spent my time trying to deeply understand Earley and goal directedness in generation. I hate how slow I am. I guess I should be glad though. At least now I think I understand restrictors.

GenI

I have this really bad programmer habit, the "yep, looks like it works". Need to be more rigourous in testing stuff out, not just try an easy case, but something non-trivial. Showed Claire the lemanchor mechanism, but turns out it wasn't completely. It was only doing the first lemanchor in the tree... mostly because I didn't think things through and make sure it worked on n > 1. Took like 2 minutes to fix, but gah! Way to waste people's time, eric.

clickity click (words: 3096, pages: 7)

Some things are starting to become clearer in my head. Read blackburn2003cs, which is a very nice introduction to computational semantics and a good refresher to the fundamentals.

flat sem and the whole lfe thing

Reading it, I realised that the whole flat semantics thing, at least what we're using, is actually extremely weak as far as logics go - we've got first order terms, i.e. constants and variables, formulas, and conjunction. No negation or disjunction. I had a few words to say about this, something along the lines of "that's ok", but I'm feeling too shy and clueless, so I'll save it for another day.

earley and shieber1998uap

This is kind of obvious, but it really things go "click". Earley scanning is just initialisation in a parsing-as-deduction framework. You do not "scan", you just initialise with all the words you've already seen. I'm starting to get a clearer picture on the notion of goal-directedness now wrt to generation algorithms. I'm still not sure I understand why we see this as bottom-up, but I think I'm close to getting it.

restrictors

After reading neumann1994ucm, I have a better grasp of the whole restrictors idea. One thing which was confusing me is that (1) we use restrictors to prevent our parsers from over-predicting (i.e. predicting things that would send us into an infinite loop (2) in a seeming contradiction, using restrictors now causes you to... over-predict... wait wasn't that the whole point, to prevent over-prediction? Now I think I understand this.

Using a restrictor, you still over-predict; you just do it in a controlled fashion. You still effectively predict all the nasty stuff that would cause an infinite loop, but not explicitly... the nasty stuff is collapsed into one of a finite number of equivalence classes. I guess, instead of equivalence classes, we could just think of it as there being one little feature structure that subsumes an infinite number (of course) of feature structures, including ones that you "want" and ones that you don't want. That's why we say it over-predicts. You need your completion step to fail those guys out.

hacking away

Most of the day spent hacking on GenI. Added a lemanchor feature and discovered a bug in the lexical selection step (merging synonyms causes two lexical items with different path equations to be treated as the same... bad eric!). Everything fixed.

not much progress (words: 2945, pages: 5)

Making slow progress. Have wrapped up the top-down stuff. Now time to explain bottom up. Attended a PhD defense. Helped a friend with some Prolog. Helped Claire prepare some demo stuff. Discovered some potential last minute features to implement or bugs to fix. Tomorrow morning, I get to write code again. It's funny. I'm actually at the point where my desire to write English is (almost) greater than my desire to write Haskell.

oh... (words: 2595, pages: 5)

[Backdating]

Ok, now after reading a bunch of BUG-related articles, I think I'm finally getting the point - yes the problem is undecidable in general, no semantic monotonicity is not a sufficient restriction on grammars to ensure termination (completeness just means IF it terminates, it gets all the relevant yes'es). Things now starting to fit together. Spent a bit of time rewriting the top down stuff. I hope this doesn't suck too much. I'm rehashing a lot of stuff that a bunch of people smarter than me have explained before... but maybe my way of explaining it will be just a little different and be useful to the "I can program a computer but I'm a worthless computer scientist and don't know anything about linguistics crowd". Boy, I am glad surface realisation for TAG and a flat semantics is only NP-complete.

c'mon eric, try to keep up

Was really tired yesterday, whole day just going "ugh". Feeling slightly better.

cl crash course - unification grammars

Alright, time to crawl out of my ignorance. I spent all this time trying to learn about semantic formalisms, then parsing algorithms... now I need to buff up on my unification grammar and computational linguistics culture. Like, I don't mean to be an HPSG or LFG expert or nothing. Just need to get enough of my shit together. This is kinda fun in a painful way, lots of "oh!"s and "ah!"s to be expected, but a lot of embarassing "ooh! I should have known that, or taken the trouble to go find out!"

So here's the result of reading Unification Grammars, the ESSLLI 2003 reader:

• subcategorisation - I've asked a million times what this was, and gotten the answer, sometimes remembering it, sometimes not. Don't get me wrong, each time I understood that it was a really easy concept, but I must have a learning disability or something because N months later, I'll go back to a paper and see "subcategorisation list" and go huh? But now that I've seen the "source code" for subcategorisation - showing one approach using atomic values and then showing a better one encoding it in lists - this time it should stick. "Subcategorisation list" should no longer make me go "huh?"
• long distance dependencies - handling via (1) slash introduction [and propagation] (2) gap filler [plugging the 'whom' in]. Learned this 5 years ago, but never saw it again, so it's nice to have a refresher. This and subcategorisation aren't very useful to me by themselves. Their real utility is for making the examples that people put in articles about generation easier to understand. When somebody says "yeah, so you can see that this won't terminate with a simple subcategorisation list thing", the example actually evokes a mental image of the appropriate grammatical machinery. No more taking people's word for things.
• reentrancy - coreference, nothing to it
• LFG arrows - I've sort of figured this out for myself, but I wanted somebody to tell me for sure (UP = mother, DOWN = me). Nothing serious, but having to think about it reduces fluency

It's not so much about concepts being easy to understand, or important, or particularly pertinent. A lot of this is a question of fluency. Being able to read stuff without having to deal with friction from stupid little details like what the arrows mean.

A lot of this I can just apply my programmer's brain to. Like the reason why you want subcategorisation lists (as opposed to the atomic value approach). It just makes for redundant code. It's just a matter of refactoring your code. Oh. Refactoring. I understanding refactoring.

bug, shdg

Head swimming after reading vannoord1989, vannoord1994 and chunks of gerdemann1994sop. I feel like I'm getting to close to wrapping my head around the state of the art, but so many things I just don't get yet and need to get. Like the semantic monotonicity thing - that's enough to make shieber1988uap terminate right? Complete means that if the answer is yes, your program says "yes" too. And it can't be complete if it don't terminate, right? Can we prove it? In other words, it is necessary for completeness, but is it sufficient? What's this problem with BUG and non-head daughters that have exactly the same semantics as the mother? Why is that a problem? I need to run through the algorithm in order to really understand this better. Is this enough to guarantee that BUG would terminate, or are we just plugging our finger in a hole only to find water spurting out somewhere else later on? Gerdemann1994sop shows where shieber1990shd would fail to terminate. Are these two places related?

Note to self - vannoord1989 shows very simply a kind of rule that shows generation is undecidable in general (essentially VP -> foo VP). Not the same problem for parsing, because in parsing, at some point you'd have to eat that foo, so if you bottom-up, you're ok. Just not clear on the restrictions we apply to grammars to make it so we come up with algorithms that terminate under those conditions.

solving two different problems

Seems like there's really two different generation problems - generation from Prolog-style logical forms and shake-and-bakey generation (two, instead of "everybody's solving a different problem"... this makes it easier; really two families of literature so far). Difference is that the second one, you can spell out from the beginning all the bits and pieces you are going to use, and then "destroy" them as you use them. No non-termination problems there. But what's the trade-off solving this problem, instead of the more general (undecidable) problem? Is this really related to the semantic formalism (seems doubtful), or is this something related to the grammar formalism (which lets you use a certain semantic formalism)? Lexicalist? All our information is in the lexicon - you don't need to look things up from the grammar, no rules like VP -> VP ADV, every bit and piece associated to a single lexical item.

oh... yeah...

So today I just learned something I should have known from the very beginning, something that should have been no-shit-Sherlock obvious: generation on unconstrained unification grammars is undedicable. Well, I guess that sort of makes sense if unification grammars are... you know... turing complete? "[D]etermining whether a given string is generated by a unification grammar is as hard as deciding whether Turing machine halts on the empty input". What I would like to see is a minimal encoding of the lambda calculus or something like that, something to just drive the point home.

Have much more reading to do if I want to talk about the search algorithm stuff better. Hope not lost of course, you just have to restrict your grammar formalism. We know that shake and bake on CFG is NP-complete; shake and bake is just surface realisation with flat semantics, right? We also know that it is NP-complete on LTAGs (no feature structures). Now just need to read a bunch of stuff and see whether arguments about termination and stuff still actually make sense. Getting there.

Otherwise, have been practically useless today. Got in late. Didn't do much. Series of distractions, but that's really no excuse.

Plodding along (words: 1633, pages 5)

Not a very productive day. Made some diagrams for the top-down and bottom-up realisation stuff. I hope using Omnigraffle isn't the wrong approach to this - I dunno, maybe I should generate these programmatically using some nice latex package. Got stuck for a while on the bottom-up stuff, kind of a sudden realisation that I didn't know what the heck I was talking about.

A stupid roadblock was that (in the Masters) I had talked about selecting all items whose semantics subsumes some part of the input semantics... but then I got to thinking "Is that actually easy?". For a while, I was stuck because I simply didn't know how one would express that in Prolog (silly way of thinking, not really even giving code). I eventually thought to ask Sébastien, and he told me about the =.. operator. So the subsumption check is really just four lines of Prolog; here's my implementation to convince myself that it really is something easy that we can just gloss over:

subsumePartOf(X,X).
subsumePartOf(X,T) :- T =.. [_|Args], subsumePartOfArgs(X,Args).

subsumePartOfArgs(X,[Y|_]) :- subsumePartOf(X,Y).
subsumePartOfArgs(X,[_|Args]) :- subsumePartOfArgs(X, Args).

Apparantly the subsumePartOf(X,X) is wrong, but it works well enough to convince me. Anyway, it's a really stupid reason to get stuck. I guess I just watned to make sure I wasn't completely talking out of my butt or something.

Anyway, today I actually managed to get in before 08:00 like back in the overdrive days. Maybe we're back in business. Wasn't very productive in the morning, though. Heck, wasn't very productive in the afternoon either. I spent about 3 or 4 hours hacking on my BibTeX citekey script, improving the family name logic so that I could handle 'von' particles, like the "van" in "van Noord" (citekey vannoord, not noord). Silly eric. Stop procrastinating.

Arrrrrgh... 2 pages, mostly diagrams. This is REALLY crappy progress, especially considering that this is stuff I have written about before! Two years later, I guess all I want is to get it right this time, really explain it well, because I [think] I understand it a lot better. But for the time being, it might actually be going in the wrong direction. Maybe I'm muddying things up even more.

eric begins writing (923 words, 3 pages)

Didn't come in to work yesterday. Spent the morning doing admin stuff and the afternoon waiting around for the locksmith to come replace my lock (which was stupid, one, he didn't make it, two it turns out I didn't need to be there in the first place).

Am currently reading wedekind1988gsd and gerdemann1994sop.

Most importantly, I have started to write. Explained the top-down realisation stuff. Doing it a little bit differently, a little bit more concretely than in the Masters. I hope it's better.

~/custom/scripts/wctex kowthese.tex mainIssues.tex 
kowthese.tex (words: 923, pages 3)