[Ligncse256] Iterating through states in the trellis

[Ben Cipollini]

Hey Dan,

I hit that issue as well.  I guess the solutions would be:
1. In your trellis builder, make sure all edges exist by inserting edges 
with 0 probability where they don't exist now.  You could probably 
initialize each word position by adding all possible transitions, setting 
probability to 0, and then loop over transitions based on your 
tag-transition model, changing the probability of the ones you think have 
non-zero probability.

In my implementation, that would be really inefficient, so I didn't do that. 
In fact, in my final implementation my trellis was pretty sparsely connected 
(but I'm not sure that's a "good" thing, I just know it was the case for 
what I did).

2. In the trellis decoder, only consider/traverse the existing 
forward/backward transitions.  0-probability transitions are implicit.  It 
probably takes more programming logic, but that turned out to be more 
efficient (runtime-wise) for me.

Hope that addresses your question...

Ben

----- Original Message ----- 
From: "Dan Kleinman" <dkleinman at ucsd.edu>
To: <ligncse256 at ling.ucsd.edu>
Sent: Wednesday, February 27, 2008 8:51 AM
Subject: [Ligncse256] Iterating through states in the trellis


> Hi Everyone,
>
> In building the decoder, I'm having trouble trying to figure out a
> not-terribly-inefficient way to iterate through all of the states in the
> trellis, which is necessary to calculate state weights and add
> backpointers. I can see that the states in the trellis are related
> through forwardTransitions/backwardTransitions, which, if we assume that
> every state in a given position is connected to every state in the next
> position, makes this process relatively easy - the model could access
> all of the forward transitions from states in a given position by
> looking at the backward transitions from all states forward of any node
> in that position. The problem is, after sprinkling some Print statements
> throughout my code, I'm not convinced that that assumption - that
> everything is connected - is valid: the number of backwardTransitions my
> trellis uses is different from how many I would expect there to be if
> that were the case (i.e., the sum of the products of the number of
> states at every two consecutive positions). Is my math screwy, or is
> there a better way to implement the iteration?
>
> Thanks,
> Dan Kleinman
>
> _______________________________________________
> Ligncse256 mailing list
> Ligncse256 at ling.ucsd.edu
> http://pidgin.ucsd.edu/mailman/listinfo/ligncse256