[Ligncse256] HW2: buildTrellis method

[Ben Cipollini]

Hey all,

I'm trying to debug some issues with my HMM scorer.  In doing so, the buildTrellis method of the POSTagger doesn't make sense to me.  I was wondering if anybody's taken a look.

Here's some basics:
* I'm using a subset of the training data for debugging purposes.
* There are 48 unique tags in the training dataset that I'm using
* There are 1201 unique combinations of tags

What I expect to do in building a trellis is:
* T0: start at the "START" state, and calculate the probability of transitioning to each of the 48 unique tags
* T1: for each of the 48 tags, determine the probability of transitioning to each of the 48 unique tags.
* T2: ...
*T{end}: for each of the 48 tags, determine the probability of transitioning to the end state.

However, this is what I see buildTrellis doing:
* T0: same
* T1: same
* T2: for each of the 48*48 possibilities of previous transitions COMBINATIONS, calculate the transition to each of the 48 states.

I think this is happening because states are unique based not on the previous state, but on the previous state and previous-previous state.  

I was expecting, however, that this shouldn't be--the probability of transition depends on the previous-previous and previous tag, but does the trellis need an extra edges or something?  I figured the trellis would have the same exact architecture as the HMM trellis we discussed in class, and thus always compute transitions from 48 states to 48 other states (48^2 such computations).  

In addition, the State class encodes sentence position.  For the HMM model, this is never used.  This winds up completely exploding caching of states to try and save memory, leading to maybe 20x extra memory used on State objects that is completely unnecessary in the HMM case, if I understand properly.

Has anybody sifted through this code or can provide feedback about my expectations?  I'm not sure if I'm conceptually missing something.  This whole State-Trellis object system seems unnecessarily complex and weighty for what I'm trying to do, and it's really making debugging a big chore for me.

Lastly, is there any principled reason that the State object uses names previousTag and previousPreviousTag instead of curTag and previousTag?  Even the startState has prevprev as START and prev as START (no current).  The semantics seem strange, and a function getNextState combines a passed-in curTag with previousTag instead of combining a nextTag with a curTag.   I can't help but feeling I'm missing some semantics in what's intended.

Please anybody respond to any part of this mail.  Just throwing some thoughts out there.  And my apologies if I'm so far off that I'm not even making sense.

Thanks in advance,
Ben
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://pidgin.ucsd.edu/pipermail/ligncse256/attachments/20080221/98a94900/attachment.htm