Information search method and apparatus using Inverse Hidden Markov Model

• US 20020065959A1
• Filed: 05/14/2001
• Published: 05/30/2002
• Est. Priority Date: 10/13/2000
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd., SungKyunKwan University (SKKU)
• Original Assignee: Samsung Electronics Co. Ltd., SungKyunKwan University (SKKU)
• Inventors: Kim, Bo-Sung, Cho, Jun-dong, Chang, Young-hoon, Park, Sun-hee
• Granted Patent: US 6,735,588 B2
• Time in Patent Office: Days
• US Class Current: 710/1
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G10L 15/142 Hidden Markov Models [HMMs]
• CPC Class Codes: G10L 15/144 Training of HMMs
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

An information search method and apparatus using an Inverse Hidden Markov Model (IHMM) are provided. The information search method involves the steps of: (a) obtaining a minimum state probability φ′_i(t) for a particular state searched at a current time t in a HMM state lattice of a reference information model by using minimum state probabilities of effective states, each of which is a probability accumulated along a search path up to a previous time t−1, and then updating the obtained minimum state probability φ′_i(t) with a predetermined value if the minimum state probability φ′_i(t) is greater than a minimum unlikelihood score; (b) obtaining an optimal path value corresponding to the lowest of a plurality of minimum state probabilities obtained after step (a) is performed for a period of time T which is greater than t, and updating the minimum unlikelihood score with the optimal path value if the minimum unlikelihood score is greater than the optimal path value; (c) determining whether or not the optimal path value has been obtained for each of the predetermined reference information models, and if not, iterating steps (a) and (b) for another reference information model for which the optimal path value has not been obtained; and (d) if the optimal path value has been obtained for each of the reference information models, determining that the reference information model yielding the optimal path value with which the minimum unlikelihood score was last updated best matches the unknown information, wherein for the period of time T, step (a) is performed for each of one or more states searched at every current time t=1, 2, . . . T, the effective states are states searched at previous time t−1 which have minimum state probabilities less than the minimum unlikelihood score, and from which a transition can be made to the particular state searched at time t, and the minimum state probability of the particular state corresponds to the lowest among state probabilities of the particular state for making a transition to the particular state from the effective states.

Claims

1. An information search method using an Inverse Hidden Markov Model (IHMM),for stochastically searching for a reference information model among a plurality of predetermined reference information models obtained by training that best matches unknown information which is expressed by a HMM chain, the information search method comprising the steps of:

(a) obtaining a minimum state probability φ

′

_i(t) for a particular state searched at a current time t in a HMM state lattice of a reference information model by using minimum state probabilities of effective states, each of which is a probability accumulated along a search path up to a previous time t−

1, and then updating the obtained minimum state probability φ

′

_i(t) with a predetermined value if the minimum state probability φ

′

_i(t) is greater than a minimum unlikelihood score;

(b) obtaining an optimal path value corresponding to the lowest of a plurality of minimum state probabilities obtained after step (a) is performed for a period of time T which is greater than t, and updating the minimum unlikelihood score with the optimal path value if the minimum unlikelihood score is greater than the optimal path value;

(c) determining whether or not the optimal path value is obtained for each of the predetermined reference information models, and if not, iterating steps (a) and (b) for another reference information model for which the optimal path value has not been obtained; and

(d) if the optimal path value has been obtained for each of the reference information models, determining that the reference information model yielding the optimal path value with which the minimum unlikelihood score was last updated best matches the unknown information,

wherein for the period of time T, step (a) is performed for each of one or more states searched at every current time t=1, 2, . . . T, the effective states are states searched at previous time t−

1 which have minimum state probabilities less than the minimum unlikelihood score, and from which a transition can be made to the particular state searched at time t, and the minimum state probability of the particular state corresponds to the lowest among state probabilities of the particular state for making a transition to the particular state from the effective states.

2. The information search method of claim 1, wherein the minimum state probability of the particular state corresponds to the lowest probability among the state probabilities obtained, equal in number to the effective states, by using the minimum state probabilities of the effective states, transition probabilities from the effective states to the particular state, and observation probabilities of the particular state, and the predetermined value is greater than the minimum unlikelihood score.

3. The information search method of claim 2, wherein step (a) comprises the steps of:

(a1) obtaining the minimum state probability φ

′

_i(t) for the particular state searched at current time t;

(a2) updating the minimum state probability φ

′

_i(t) of the particular state with the predetermined value if the minimum state probability obtained in step (a1) is greater than the minimum unlikelihood score;

(a3) determining whether or not the minimum state probability φ

′

_i(t) has been obtained for each of the one or more states searched at current time t, and if not, iterating steps (a1) and (a2) for each of the remaining states for which the minimum state probability φ

′

_i(t) has not been obtained; and

(a4) determining whether or not the period of time T has passed if the minimum state probability φ

′

_i(t) has been obtained for each of the particular states, and if so, proceeding to step (b), and if not, performing steps (a1) through (a3) at a next time t+1.

4. The information search method of claim 3, wherein the minimum state probability φ

′

_i(t) of the particular state searched at current time t is obtained by the following formula;

φ

′

_i(t)=min[φ

′

_ij(t−

1)+log(1−

a_ij)+log(1−

b_ij(W(t)))]

where a_ij is the transition probability;

b_ijW(t) is state observation probability for the particular state searched at time t;

W(t) is a symbol sequence which indicates utterance at time t, b_ij indicates the probability for the symbol sequence;

φ

′

_ij(t−

1) indicates the minimum state probability of the j-th state searched at time t−

1 which is a probability accumulated along a search path up to previous time t−

1;

i is a variable indicating states searched at time t and 1≦

i≦

N;

j is a variable indicating states searched at time t−

1 and 1≦

j≦

N;

N is the number of information states forming the unknown information; and

[ ] means the state probability.

5. An information search apparatus using an Inverse Hidden Markov Model (IHMM), for performing the information search method of any one of claims 1 through 4, the information search apparatus comprising:

a storage unit for storing the minimum unlikelihood score, a first value related to the transition probability, and a second value related to the state observation probability;

first through N-th processing units;

first through N-th comparing &

selecting units;

a control unit for outputting a control signal in response to a comparison flag output from each of the first through the N-th comparing &

selecting units, controlling reading of data stored in the storage unit, and passing values output from the first through the N-th comparing &

selecting units; and

a buffer for receiving and buffering values passed by the control unit and outputting each of the buffered values to a corresponding processing unit among the first through the N-the processing units, in response to the control signal,

wherein an i-th processing unit processes a value output from the buffer, and the first value and the second value provided from the storage unit, compares the processed results, selects and outputs the smallest processed result in response to the control signal, and an i-th comparing &

selecting unit compares the smallest processed result output from the i-th processing unit with the minimum unlikelihood score provided from the storage unit, selects one of the predetermined value and the smallest processed result in response to the result of the comparison, and outputs the selected value and a comparison flag having a level corresponding to the result of the comparison to the control unit.

6. The information search apparatus of claim 5, wherein the i-th processing unit comprises:

first through N-th adding portions; and

a minimum value selector,

wherein an i-th adding portion adds a value output from the buffer, the first value, and the second value, and the minimum value selector selects the smallest added result among the added results output from the first through N-th adding portions, in response to the control signal, and outputs the selected smallest result as the smallest processed value to the i-th comparing &

selecting unit.