Method for improving results in an HMM-based segmentation system by incorporating external knowledge

1. A method for improving a Hidden Markov model (HMM) based mark-up system, the method including the steps of:

a. constructing a HMM defining a plurality of states;

b. modifying a Viterbi algorithm, related to the HMM, in order to apply a multiplicative factor if a particular state is re-entered; and

c. executing the modified Viterbi algorithm against at least one information source.

2. The method according to claim 1 further comprises the steps of:

d. identifying a number of times each state is re-entered; and

e. applying the multiplicative factor based on the identified number of times the state has been re-entered.

3. The method according to claim 2 , wherein different multiplicative factors are applied for different numbers of re-entry times.

4. The method according to claim 1 , further comprising the steps of:

d. marking-up the at least one information source, wherein the source is a resume.

5. The method according to claim 1 , further comprising the steps of:

d. determining an optimal multiplicative factor for each particular state independent of the other states.

6. The method according to claim 1 , further comprising the steps of:

d. separating the particular state into a plurality of sub-states; and

e. modifying the Viterbi algorithm in order to apply a sub-state multiplicative factor if a particular sub-state is re-entered.

7. The method according to claim 1 , wherein re-entry is constrained on local fragments of the at least one information source, rather than the whole at least one information source.

8. The method according to claim 1 , wherein the multiplicative factor is a reward factor to increase the likelihood that the particular state is re-entered.

9. The method according to claim 1 , wherein the multiplicative factor is a reward factor to require that the particular state is re-entered.

10. The method according to claim 1 , wherein the multiplicative factor is a penalty factor to decrease the likelihood that the particular state is re-entered.

11. The method according to claim 1 , wherein the multiplicative factor is a penalty factor to prohibit that the particular state is re-entered.

12. A method of improving a Hidden Markov model (HMM) segmentation system comprising the steps of:

a. receiving a data sequence to be segmented;

b. invoking a Viterbi algorithm to label the received data sequence into a plurality of segment types;

c. if a segment type is identified more than once during labeling, verifying which identification is correct;

d. anchoring, within the data sequence, labels verified as being correct; and

e. invoking the Viterbi algorithm to label the data sequence, including the anchored labels, into the plurality of segment types.

13. A multi-pass method for improving results of a Hidden Markov model (HMM) based segmentation system, comprising the steps of:

a. receiving a data sequence to be segmented;

b. invoking a Viterbi algorithm to label the received data sequence into a plurality of segment types; and

c. if a segment type is identified more than once during labeling, invoking a modified Viterbi algorithm to label the received data sequence into the plurality of segment types; wherein the modified Viterbi algorithm imposes a constraint regarding re-entry into a particular state of the HMM.

14. The method according to claim 13 , wherein the step of invoking the modified Viterbi Algorithm further includes the steps of;

d. determining which respective state of the HMM corresponds to each of the segment types identified more than once during labeling; and

e. invoking the modified Viterbi algorithm with respect to only the determined states of the HMM.

15. The method according to claim 13 , wherein the constraint penalizes entry into a particular state.

16. The method according to claim 13 , wherein the constraint encourages entry into a particular state.

17. A method for improving a Hidden Markov model (HMM) based mark-up system, the method including the steps of:

a. constructing an HMM defining a plurality of hierarchically arranged states;

b. modifying a Viterbi algorithm, related to the HMM, in order to apply a first multiplicative factor if a first state of the HMM is re-entered and to apply a second multiplicative factor if a second state of the HMM is re-entered, wherein the second state is at a second hierarchical level under the first hierarchical level of the first state; and

c. invoking the modified Viterbi algorithm against at least one information source.

18. A method for improving a conventional Viterbi algorithm, the method comprising the step of modifying the determination of δ and φ of the conventional Viterbi algorithm such that:

a. for each state i ε{1, . . . ,N},

i. if state i is in re-entry group k,

a) δ 1 (i,G k )=π l ×b i (O 1 ); for all G≠G k , δ 1 (i,G)=0, and

b) For all G, φ i (i,G)=0;

ii. otherwise, if state i is not in any re-entry group k,

a) δ 1 (i,G 0 )=π i ×b i (O 1 ); for all G≠G 0 , δ 1 (i,G)=0, and

b) For all G, φ 1 (i,G)=0; and

b. for time t=2 to T,

iii. for each state i ε {1, . . . ,N},

a) for each re-entry state G,

1) δ 1 (i,G)=max 1≦j≦N{δ t-1 (j,G′)×a ji ×d(G′,i,j)}×b i (O t ), and

2) φ t (i,G)=argmax 1≦j≦N{δ t-1 (j)×a ji ×d(G′,i,j)},

C. wherein G k , for each re-entry group k, denotes the current number of entries into that particular re-entry group; G denotes a re-entry state comprising a set of values for all G k ; G k denotes the re-entry state consisting of zeroes for all re-entry groups except k and a one for group k; and G′ denotes the re-entry state j that would have led to re-entry state G when moving from state j to state i.