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

• US 6,965,861 B1
• Filed: 11/20/2001
• Issued: 11/15/2005
• Est. Priority Date: 11/20/2001
• Status: Expired due to Fees

• Current Assignee: Predictive Intelligence, LLC
• Original Assignee: Burning Bush Technologies LLC
• Inventors: Dailey, Matthew N., Hathaidharm, Chalaporn, Pathria, Anu K., Freitag, Dayne B.
• Primary Examiner(s): {hacek over (S)}mits, Talivaldis Ivars
• Assistant Examiner(s): Rivero, Minerva
• Application Number:
  US09/988,601
• Time in Patent Office: 1,456 Days
• Field of Search: 704/1, 704/9, 704/242, 715/500, 715/530, 715/531
• US Class Current: 704/242
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A Hidden Markov model is used to segment a data sequence. To reduce the potential for error that may result from the Markov assumption, the Viterbi dynamic programming algorithm is modified to apply a multiplicative factor if a particular set of states is re-entered. As a result, structural domain knowledge is incorporated into the algorithm by expanding the state space in the dynamic programming recurrence. In a specific example of segmenting resumes, the factor is used to reward or penalize (even require or prohibit) a segmentation of the resume that results in the re-entry into a section such as Experience or Contact Information. The method may be used to impose global constraints in the processing of an input sequence or to impose constraints to local sub-sequences.

Claims

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) δ

₁(i,G^k)=π

_l×

b_i(O₁);

for all G≠

G^k, δ

₁(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) δ

₁(i,G⁰)=π

_i×

b_i(O₁);

for all G≠

G⁰, δ

₁(i,G)=0, and

b) For all G, φ

₁(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) δ

₁(i,G)=max<sub>1≦

j≦

N{δ

t-1</sub>(j,G′

)×

a_ji×

d(G′

,i,j)}×

b_i(O_t), and

2) φ

_t(i,G)=argmax<sub>1≦

j≦

N{δ

t-1</sub>(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.