Name entity extraction using language models

[0001] 1. Technical Field

[0002] The present invention relates to natural language understanding and, in particular, to name entity extraction. Still more particularly, the present invention provides a method, apparatus, and program for name entity extraction using language models (N-gram and/or finite-state language model).

[0003] 2. Description of Related Art

[0004] The task of name entity extraction is to retrieve name entities from text documents or natural language utterances. Much research has been done in this area. Existing techniques for name entity extraction include, for example, rule based methods, decision tree approach, Hidden Markov model (HMM) technique, Maximum Entropy approach, and Finite-state transducer.

[0005] Most of the currently existing name entity extraction methods rely on a model that is trained or developed based on a large amount of manually annotated text data. These techniques have several problems. A sufficient amount of text data needs to be collected, which is expensive in both time and money. Also, data annotation requires substantial amount of time and human effort. Usually, a good model requires the training data to be consistently annotated, which in practice is a luxury requirement, especially when multiple persons participate in the annotation simultaneously and when the annotation process spans over a long period of time. Furthermore, the collected text data is usually domain-dependent and so is the trained model, which could not be reused or easily applied to other domains of applications. These problems make the development work very expansive and the development process very long even for a simple natural language application, such as a mutual fund trading system or air travel system.

[0006] Therefore, it would be advantageous to provide an improved name entity extraction technique that provides accurate results without excessive language model training efforts.

[0007] The present invention provides a name entity extraction technique using language models. A general language model is provided for the natural language understanding domain. A language model is also provided for each name entity. The name entity language models are added to the general language model. Each language model is considered a state. Probabilities are applied for each transition within a state and between each state. For each word in an utterance, the name extraction process determines a best current state and a best previous state. When the end of the utterance is reached, the process traces back to find the best path. Each series of words in a state other than the general language model state is identified as a name entity. The present invention also provides a technique for iteratively retraining the general language model. The name entity extraction technique is used to extract name entities from a corpus of training sentences. The name entities are replaced with name entity labels in the training sentences and the general language model is retrained using these sentences. The process iteratively extracts names and retrains the general language model until the probabilities do not change. The name entity extraction technique of the present invention may also use a general language model with uniform probabilities to save the time and expense of training the general language model.

[0008] The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objectives and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

[0009] FIG. 1 is a pictorial representation of a data processing system in which the present invention may be implemented in accordance with a preferred embodiment of the present invention;

[0010] FIG. 2 is a block diagram of a data processing system in which the present invention may be implemented;

[0011] FIG. 3 depicts a natural language understanding application in accordance with a preferred embodiment of the present invention;

[0012] FIG. 4 illustrates an example of a finite-state language model for the integer numbers between twenty-eight and thirty-two in accordance with a preferred embodiment of the present invention;

[0013] FIG. 5 illustrates an example of a finite-state language model equivalent to a bigram language model with the vocabulary of two words in accordance with a preferred embodiment of the present invention;

[0014] FIGS. 6A and 6B illustrate a general language model and two name entity language models in accordance with a preferred embodiment of the present invention;

[0015] FIGS. 7A and 7B depict a decoding for an example sentence in accordance with a preferred embodiment of the present invention;

[0016] FIG. 8 is a flowchart illustrating the operation of a natural language extraction mechanism in accordance with a preferred embodiment of the present invention; and

[0017] FIG. 9 is a flowchart illustrating the operation of an iterative decoding and retraining process in accordance with a preferred embodiment of the present invention.

[0018] With reference now to the figures and in particular with reference to FIG. 1, a pictorial representation of a data processing system in which the present invention may be implemented is depicted in accordance with a preferred embodiment of the present invention. A computer 100 is depicted which includes system unit 102, video display terminal 104, keyboard 106, storage devices 108, which may include floppy drives and other types of permanent and removable storage media, and mouse 110. Additional input devices may be included with personal computer 100, such as, for example, a joystick, touchpad, touch screen, trackball, microphone, and the like. Computer 100 can be implemented using any suitable computer, such as an IBM eServer computer or IntelliStation computer, which are products of International Business Machines Corporation, located in Armonk, N.Y. Although the depicted representation shows a computer, other embodiments of the present invention may be implemented in other types of data processing systems, such as a network computer. Computer 100 also preferably includes a graphical user interface (GUI) that may be implemented by means of systems software residing in computer readable media in operation within computer 100.

[0019] With reference now to FIG. 2, a block diagram of a data processing system is shown in which the present invention may be implemented. Data processing system 200 is an example of a computer, such as computer 100 in FIG. 1, in which code or instructions implementing the processes of the present invention may be located. Data processing system 200 employs a peripheral component interconnect (PCI) local bus architecture. Although the depicted example employs a PCI bus, other bus architectures such as Accelerated Graphics Port (AGP) and Industry Standard Architecture (ISA) may be used. Processor 202 and main memory 204 are connected to PCI local bus 206 through PCI bridge 208. PCI bridge 208 also may include an integrated memory controller and cache memory for processor 202. Additional connections to PCI local bus 206 may be made through direct component interconnection or through add-in boards.

[0020] In the depicted example, local area network (LAN) adapter 210, small computer system interface SCSI host bus adapter 212, and expansion bus interface 214 are connected to PCI local bus 206 by direct component connection. In contrast, audio adapter 216, graphics adapter 218, and audio/video adapter 219 are connected to PCI local bus 206 by add-in boards inserted into expansion slots. Expansion bus interface 214 provides a connection for a keyboard and mouse adapter 220, modem 222, and additional memory 224. SCSI host bus adapter 212 provides a connection for hard disk drive 226, tape drive 228, and CD-ROM drive 230. Typical PCI local bus implementations will support three or four PCI expansion slots or add-in connectors.

[0021] An operating system runs on processor 202 and is used to coordinate and provide control of various components within data processing system 200 in FIG. 2. The operating system may be a commercially available operating system such as Windows XP, which is available from Microsoft Corporation. An object oriented programming system such as Java may run in conjunction with the operating system and provides calls to the operating system from Java programs or applications executing on data processing system 200. Java is a trademark of Sun Microsystems, Inc. Instructions for the operating system, the object-oriented programming system, and applications or programs are located on storage devices, such as hard disk drive 226, and may be loaded into main memory 204 for execution by processor 202.

[0022] Those of ordinary skill in the art will appreciate that the hardware in FIG. 2 may vary depending on the implementation. Other internal hardware or peripheral devices, such as flash read-only memory (ROM), equivalent nonvolatile memory, or optical disk drives and the like, may be used in addition to or in place of the hardware depicted in FIG. 2. Also, the processes of the present invention may be applied to a multiprocessor data processing system.

[0023] For example, data processing system 200, if optionally configured as a network computer, may not include SCSI host bus adapter 212, hard disk drive 226, tape drive 228, and CD-ROM 230. In that case, the computer, to be properly called a client computer, includes some type of network communication interface, such as LAN adapter 210, modem 222, or the like. As another example, data processing system 200 may be a stand-alone system configured to be bootable without relying on some type of network communication interface, whether or not data processing system 200 comprises some type of network communication interface. As a further example, data processing system 200 may be a personal digital assistant (PDA), which is configured with ROM and/or flash ROM to provide non-volatile memory for storing operating system files and/or user-generated data.

[0024] The depicted example in FIG. 2 and above-described examples are not meant to imply architectural limitations. For example, data processing system 200 also may be a notebook computer or hand held computer in addition to taking the form of a PDA. Data processing system 200 also may be a kiosk or a Web appliance.

[0025] The processes of the present invention are performed by processor 202 using computer implemented instructions, which may be located in a memory such as, for example, main memory 204, memory 224, or in one or more peripheral devices 226-230.

[0026] With reference to FIG. 3, a natural language understanding application is shown in accordance with a preferred embodiment of the present invention. Speech recognition unit 302 receives a spoken utterance. The speech recognition unit converts the spoken utterance into a natural language text. Name entity extraction mechanism 304 receives the natural language text and extracts name entities. A name entity is a recognizable, meaningful entity in the text, such as a dollar amount, a city, or a date. Name entity extraction mechanism 304 may insert labels in place of or in association with the words that make up the name entity. Parser 306 receives the natural language text with name entity labels and parses the utterance to perform a natural language understanding operation. The natural language understanding application or, more particularly, the name entity extraction mechanism may be implemented on a computer, such as computer 100 in FIG. 1.

[0027] The present invention provides a name entity extraction technique using language models. Each kind of name entity is represented by a language model such as an N-gram language model or a finite-state language model. Another language model, called general language model, is introduced to represent the patterns of natural language utterances. The general language model encodes the linguistic information among the name entities and other words in the vocabulary. Consequently, if there are K types of name entities, then there are (K1) language models in total. During decoding, each language model is regarded as one state. Given an utterance, a word in the utterance could be aligned with any state. The Viterbi algorithm is applied to find out the most probable state sequence aligning with the word sequence. Any contiguous words aligned with a state other than the state of the general language model are tagged and labeled as the corresponding name entity.

[0028] In accordance with a preferred embodiment of the present invention, the language model for a name entity is either a finite-state or an N-gram language model. The latter is trained using the text data of that specific name entity. Therefore, the model for the name entity is domain-independent. However, the general language model is trained using a set of domain-dependent natural language utterances. Therefore, it is domain-dependent. In an alternate embodiment, a uniform bigram language model is used as the general language model, where the probability between any pair of words is equal to a preset constant value. This uniform bigram language model is not only domain-independent, but also it does not require any data to train a weighted general language model, and the vocabulary size is unlimited. However, if some domain specific data is available, this algorithm could be applied to iteratively decode the raw sentences and refine the models, and thereby to improve the performance of the name entity recognition system.

[0029] In accordance with a preferred embodiment of the present invention, the back-off bigram language model or finite-state language model is used to capture the local context information of a name entity. The generalization from bigram to N-gram (N3) language models and other smoothing techniques is straightforward. In order to present the algorithm, one must introduce some basic concepts and some convections used in the present invention.

[0030] The pattern of a natural language utterance is defined as the corresponding utterance with the interested name entities represented by the corresponding labels. In the examples shown below, normal words in a natural language utterance are written in lower case, while the labels are written in upper case. The following are example natural language utterances and their corresponding patterns, where AMOUNT, SHARES, and FUND are the labels for the name entities of the types of dollar amount, share amount, and fund names, respectively:

[0031] Original utterance: i want to buy two hundred dollars of fidelity magellan

[0032] Pattern: i want to buy AMOUNT of FUND

[0033] Original utterance: transfer twenty shares from my magellan account to vanguard account

[0034] Pattern: transfer SHARES from my FUND account to FUND account

[0035] The pattern of a natural language utterance is the one with all the interested name entities represented by the corresponding labels. Fidelity magellan and magellan are labeled as FUND names, twenty shares is labeled as SHARES names and two hundred dollars is labeled as AMOUNT names.

[0036] A bigram language model is defined by a vocabulary and probabilities for any pair of words. In the back-off bigram language model, if a word pair appears too infrequent in the training data, its bigram probability will be backed-off to the unigram probability. Similarly, if a word appears too infrequent, its unigram probability will be backed-off to the uniform distribution. Mathematically, the unigram probability for a word w_i could be defined as: $\begin{array}{cc}P\left(w_i\right)=\{\begin{array}{cc}N\left(w_i\right)/N& \mathrm{if}N\left(w_i\right)>u,\\ u/N& \mathrm{otherwise},\end{array}& \left(1\right)\end{array}$

[0037] where u is a constant; N(w_i) is the number of times the word w_i appears in the training corpus; N_jAN(w_j)_{j{overscore (A)}}u, where A is the set of words w_j that satisfy N(w_j)>u and {overscore (A)} is the set of words not belonging to A in the pre-defined vocabulary.

[0038] The bigram probability for each word-pair (w_i, w_j) is defined as: $\begin{array}{cc}P(w_j{w}_i)=\{\begin{array}{cc}N\left(w_i,w_j\right)/N\left(w_i\right)& \mathrm{if}N\left(w_i,w_j\right)>t,\\ b\left(w_i\right)p\left(w_j\right)& \mathrm{if}N\left(w_i,w_j\right)t\mathrm{and}N\left(w_i\right)>0,\end{array}& \left(2\right)\end{array}$

[0039] where t is a constant, N (w_i, w_j) is the number of occurrences w_j follows w_i in the training corpus; b (w_i) is the back-off weight which is calculated to ensure _j1^VP (w_jw_i)1. Therefore, $b\left(w_i\right)=\frac{1-\underset{j{B}_i}{}P\left(w_j{w}_i)\right)}{1-\underset{j{B}_i}{}P\left(w_j\right)}$

[0040] where B_i is the set of all words w_j for which N (w_i, w_j)>t, and where both u and t are set to 1.

[0041] A finite-state language model is a finite-state automata defined by a sextuple (Q, , I, T, , Z) where Q(q₁, . . . ,q_N) is a finite set of states, is the vocabulary, I is the initial state, T is the terminal state, is the transition function, and Z is the probability function. There are arcs transiting from one state to other states. An arc originating from a state q is associated with one symbol w, the associated probability Z(wq). Each continuous path across the finite-state automata originating from the initial state and ending at the final state is called a complete path, and all the other paths are called partial paths. The word sequence corresponding to a complete path represents a legal utterance defined by this finite-state language model.

[0042] FIG. 4 illustrates an example of a finite-state language model for the integer numbers between twenty-eight and thirty-two in accordance with a preferred embodiment of the present invention. Dotted lines represent a transition without emitting any word. Each word represents an arc emitting the specified word with the probability being equal to the number. In a back-off N-gram language model, any sequence of words in the vocabulary are legal utterances. However, in a finite-state language model, only those word sequences corresponding to a complete path are legal utterances.

[0043] On the other hand, a bigram language model with vocabulary size N may be represented by a finite-state language model with N states together with an initial state and a terminal state. Any transition from the initial state to the i-th (1iN) state generates word w_i with probability P(w_iUTT_START), where UTT_START represents the starting symbol of an utterance, P is the bigram probability. A transition from the i-th state to the terminal state leads to the end of the utterance with the probability of P(UTT_ENDw_i), where UTT_END represents the ending symbol of an utterance. A transition from i-th state to j-th state (1i,jN) generates w_j with probability P(w_jw_i. FIG. 5 illustrates an example of a finite-state language model equivalent to a bigram language model with the vocabulary of two words in accordance with a preferred embodiment of the present invention.

[0044] Given K kinds of interested name entities, each type of name entity is represented by a bigram or a finite-state language model. Together with the general language model, there are (K1) language models in total. During decoding, each language model is regarded as one state. Therefore, there are (K1) states, denoted as s₀, s₁, . . . , s_K with s₀ denoting the state for the general language model and s_i (i1) the state for the language model of the i-th name entity. Each language model has its specific starting and ending words of an utterance, denoted as ENT_i-START and ENT_iEND for the i-th (1iN) name entity, and GENERAL_START and GENERAL_END for the general language model.

[0045] Given the assumption that a sufficient amount of natural language utterances is annotated and replacing the name entities by the corresponding labels, denoted as ENT_i(1iK), one gets the patterns of the natural language utterances which can be used to train a bigram language model for the general language model where ENT_i are words of the vocabulary. Denoting a natural language utterance as a sequence of words Ww₁, w₂, . . . , w_n which may or may not contain any name entities, then at any time t(1tn), the word w_t is assumed to be aligned with the state S_t(S_ts₀, . . . , s_K).

[0046] With reference now to FIG. 6A, a general language model and two name entity language models are shown in accordance with a preferred embodiment of the present invention. A transition from w_t1 to w_t involves the state transition from S_t1 to S_t. Suppose the probability transiting to w_t at state S_t only depends on the previous word w₁ and the corresponding state S_t1, the transition probability can be written as P(w_t,S_tw_t1, S_t1). From FIG. 6A, one sees that a transition from s₀ to s_i(i0) at time t means that w_t is the first word of the i-th name entity, a transition from s₁(i0) to s₀ at time t means that w_i is the last word of the i-th name entity, a transition from s_i to s_j(ij, i0,j0) at time t means that w_t1 is the last word of the i-th name entity and w_t is the first word of the j-th name entity.

[0047] The probability P(w_t,S_tw_t1,S_t1) may be rewritten as

[0048] where P(w_tw_t1,S_t,S_t1) is the probability transiting from w_t1 to w_t conditioned on states S_t1 and S_t, while P(S_tw_t1,S_t1) is the probability transiting from state S_t1 to S_t conditioned on w_t1. The probabilities should satisfy the unitary conditions: $\begin{array}{cc}\underset{w_t}{}P(w_t{w}_{t-1},S_t,S_{t-1})=1,\underset{S_t}{}P(S_t{w}_{t-1},S_{t-1})=1.& \left(4\right)\end{array}$

[0049] Depending on S_t1 and S_t, P(w_tw_t1,S_t,S_t1) may be defined using the probability of the general language model, denoted by G, and those for the name entities, denoted by E_i(1iK): $\begin{array}{cc}P(w_t{w}_{t-1},S_t,S_{t-1})=\{\begin{array}{cc}G(w_t{w}_{t-1}),& \mathrm{if}{S}_{t-1}=S_t=s_0,\\ E_i(w_t{\mathrm{ENT}}_i\mathrm{\_START}),& \mathrm{if}{S}_{t-1}=s_0,S_t=s_i{s}_0,\\ G(w_t{\mathrm{ENT}}_i\mathrm{\_END}),& \mathrm{if}{S}_{t-1}=s_i{s}_0,S_t=s_0,\\ E_j(w_t{\mathrm{ENT}}_j\mathrm{\_START}),& \mathrm{if}{S}_{t-1}=s_i{s}_0,S_t=s_j{s}_0,s_i{s}_j,\\ E_i(w_t{w}_{t-1}),& \mathrm{if}{S}_{t-1}=S_t=s_i{s}_0.\end{array}& \left(5\right)\end{array}$

[0050] where G(w_iENT_iEND)G(w_iENT_i). If the i-th name entity is represented by a finite-state language model (Q_i, _i, I_i, T_i,_i, Z_i), the corresponding language model i probabilities are express as:

[0051] In this case, one must keep track of the internal state of the language model at each time t when calculating the trellis scores.

[0052] Similarly, P(S_tS_t1, w_t1) may be defined as: $\begin{array}{cc}P(S_t{S}_{t-1},w_{t-1})=\{\begin{array}{cc}\begin{array}{c}1-\underset{i=1}{\overset{K}{}}{}_{i}G({\mathrm{ENT}}_i\mathrm{\_START}{w}_{t-1}),\mathrm{if}{S}_{t-1}=S_t=s_0,\\ {}_{i}G({\mathrm{ENT}}_i\mathrm{\_START}{w}_{t-1}),\mathrm{if}{S}_{t-1}=s_0,S_t=s_i{s}_0,\\ {}_i{E}_i({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1}),\mathrm{if}{S}_{t-1}=s_i{s}_0,S_t=s_0,\\ {}_{\mathrm{ij}}G({\mathrm{ENT}}_j\mathrm{\_START}{\mathrm{ENT}}_i\mathrm{\_END})E_i({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1}),\mathrm{if}{S}_{t-1}=s_i{s}_0,S_t=s_j{s}_0,s_i{s}_j,\\ 1-{}_i{E}_i({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1})-\underset{ji,j0}{}{}_{\mathrm{ij}}\\ G({\mathrm{ENT}}_j\mathrm{\_START}{\mathrm{ENT}}_i\mathrm{\_END})E_i({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1}),\mathrm{if}{S}_{t-1}=S_t=s_i{s}_0,\end{array}& \end{array}& \left(7\right)\end{array}$

[0053] where G(ENT_jSTARTENT_iEND)G(ENT_jENT_i), G(ENT_iSTARTw_t1)G(ENT_iw_t1), E_is are represented in equation (6), _i, _i and _ij (1iK) are redundant constant parameters constrained by equation (4) and

[0054] These parameters may be used to control state transitions. Usually, _is are set to some large values so that transition from the state of the general language model to the state of name entities are encouraged, _is and _is are set to some small values so that a transition away from the state for a name entity is discouraged, and staying in the state for a name entity is encouraged. Because of this, the decoder prefers longer names than shorter names.

[0055] Substituting Equation (5) and (7) into (3), we get the state transition probability $\begin{array}{cc}P\left(w_t,S_t{S}_{t-1},w_{t-1})=P(w_t{w}_{t-1},S_t,S_{t-1})P(S_t{S}_{t-1},w_{t-1}\right)=\begin{array}{cc}\{\begin{array}{cc}\left[1-\underset{i=1}{\overset{K}{}}{}_{i}G\left({\mathrm{ENT}}_i\mathrm{\_START}{w}_{t-1}\right)\right]G(w_t{w}_{t-1}),& \mathrm{if}{S}_{t-1}=S_t=s_0,\\ {}_{i}G\left({\mathrm{ENT}}_i\mathrm{\_START}{w}_{t-1})E_i(w_t{\mathrm{ENT}}_i\mathrm{\_START}\right),& \mathrm{if}{S}_{t-1}=s_0,S_t=s_i{s}_0,\\ {}_i{E}_i\left({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1})G(w_t{\mathrm{ENT}}_i\mathrm{\_START}\right),& \mathrm{if}{S}_{t-1}=s_i{s}_0,S_t=s_0,\\ {}_{\mathrm{ij}}G\left({\mathrm{ENT}}_j\mathrm{\_START}{\mathrm{ENT}}_i\mathrm{\_END})E_i({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1}\right),& \mathrm{if}{S}_{t-1}=s_i{s}_0,S_t=s_j{s}_0,s_i{s}_j,\\ [1-{}_i{E}_i({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1})-\underset{ji,j0}{}{}_{\mathrm{ij}}& \mathrm{if}{S}_{t-1}=S_t=s_t{s}_0,\\ G\left({\mathrm{ENT}}_j\mathrm{\_START}{\mathrm{ENT}}_i\mathrm{\_END})E_i({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1}\right)]E_i(w_t{w}_{t-1}),& \\ & \end{array}& \end{array}& \left(8\right)\end{array}$

[0056] If a pair formed by a language model state and a word identity is regarded as one state, the finite-state machine with probability defined by equation (8) represents an ergodic Markov chain.

[0057] Given a word sequence Ww₁, w₂, . . . , w_n, and a set of name entities each of which is associated with a language model, the task of name entity extraction is to discover a state sequence SS₁, S₂, . . . , S_n, which maximizes the conditional probability P(SW)P(S₁, S₂, . . . , S_nw₁, w₂, . . . , w_n) with the word w_i aligning with state S_i(1in).

[0058] According to Bayes's rule, the result is

[0059] where the last equal relation comes from the fact that P(W) is independent of the state sequence S. Based on the ergodic Markov chain model defined in equation (8), the joint probability could be rewritten as: $P\left(W,S\right)=\underset{i=0}{\overset{n+1}{}}P(w_{i+1},S_{i+1}{w}_i,S_i)$

[0060] with w₀GENERAL_START, w_n1GENERAL_END, S₀S_n1s₀. Therefore, the task of name entity extraction is to find the optimal state sequence S that maximinzes the joint probability P(W,S). This may be performed efficiently using the Viterbi algorithm. Denoting Q(w_t,S_t) as the accumulated score at t (1tn) with the word w_t aligned with the state S{dot over (_t)}_tS_t) is the state at t1 from which the accumulated probability at (w_t, S_t) is the highest among all transitions from (w_t1, s_i) with 0in, the Viterbi algorithm is stated as follows:

[0061] (1) Initialization: I(GENERAL_START, s₀)1.

[0062] (2) When t1,

[0063] for (i0; iK; i)

[0064] Q(w₁, s_t)I(GENERAL_START, s₀)*P(w₁, s_iGENERAL_START, s₀),

[0065] ₁(s_i)s₀.

[0066] (3) Recursion: when 2tn,

[0067] for (t2;tn;t)

[0068] for (i0;iK;i)

[0069] Q(w_t, s_i)max_j(Q(w_t1, s_j)P(w_t, s_iw_t1, s_j)),

[0070] _t(s_t)arg max_jQ(w_t1, s_j)P(w_t, s_iw_t1, s_j))

[0071] (4) Termination: when tn1,

[0072] Q(GENERAL_END, s₀)max_j(Q(w_n, s_j)P(GENERAL_END, s₀w_t1, s_j),

[0073] _n1 (s₀)arg max_jQ(w_n, s_j)P(GENERAL_END, s₀w_t1, s_j)).

[0074] (5) Trace back to get the optimal state sequence S₀, S₁, . . . , S_n.

[0075] S_n1s₀

[0076] for (tn;t0;t) S_tt1(S_t1).

[0077] In this optimal state sequence, any contiguous words aligned with a state other than the one of the general language model is tagged and labeled as the corresponding name entity.

[0078] With reference now to FIG. 7A, a decoding for an example sentence is illustrated in accordance with a preferred embodiment of the present invention. The name extraction mechanism of the present invention is used to decode the following sentence:

[0079] i want to buy 200 dollars of fidelity magellan please

[0080] If the interested name entities are FUND and AMOUNT, there are three states in total. One corresponds to the general language model, denoted by s₀; the second corresponds the bigram language model of FUND, denoted by s₁; the third corresponds to the finite-state language model of AMOUNT, denoted by s₂. As shown in FIG. 6A, at t0 (the first step of the Viterbi algorithm), the word GENERAL_START is aligned with state s₀. At t1 (the second step of the Viterbi Algorithm), the accumulated probabilities of the word w₁, i aligned with S₁s₀, s₁ and s₂ are calculated and denoted as Q(w₁,s₀), Q(w₁, s₁) and Q(w₁, s₂) respectively. The best previous state at time t1 for each of these states are so (the state aligned with GENERAL_START). At t2 (step 3 of the Viterbi algorithm), the score of Q(w₂, S₂), where w₂want and S₂s₀, s₁ and s₂, are calculated as follows:

[0081] FIG. 6B shows how the score Q(w₂, s₁) is calculated. There are transitions to (w₂, s₁) from (w₁, s₀), (w₁, s₁), and (w₁, s₂) respectively. The solid arrow line in FIG. 6B (from (w₁, s₀) to (w₂, s₁)) has the best accumulated score among all these three transitions. Therefore, the best previous state of s₁ at t2 is ₂(S₁)s₀. Similarly, we can calculate the best accumulate score for Q(w₂, s₀) and Q(w₂, s₂) and their best previous states ₂(s₀) and ₂(s₂) respectively. At the end (step 4 of the Viterbi algorithm), we calculate the best accumulated score of Q(w₁₁, s₀) where w₁₁GENERAL_END and found its best previous state to be ₁₁ (s₀)s₀. By tracing back, the best previous state of s₀(₁₁ (s₀)) at t10 is ₁₀ (s₀)s₁, and the best previous state of s₁ (₁₀(s₀)) at t9 is s₁, and so on. Finally, we get the best state sequence:

[0082] The words aligned with the above state sequence are:

[0083] GNEERAL_START i want to buy 200 dollars of fidelity magellan please (w₀GNEERAL_START, w₁i, . . . w₁₀please. w_t aligns with _t1, because _t1, is the best previous state). The best state sequence aligning with the above word sequence is depicted in FIG. 7A.

[0084] With reference to FIG. 8, a flowchart is shown illustrating the operation of a natural language extraction mechanism in accordance with a preferred embodiment of the present invention. The process begins and initializes the probability that the start node is in the general language model state to 1 (step 802). For the first word in the utterance, the process determines the accumulated scores of the first word aligning with each language model state (step 804). Then, the next word is considered (step 806) and a determination is made as to whether the end node is reached (step 808). If the end node is not reached, the process determines the best accumulated scores of the current word aligning with each language model state (step 810), determines the best previous state (step 812), and returns to step 806 to consider the next word.

[0085] If, however, the end node is reached in step 808, the process determines the best previous state (step 814). Thereafter, the process traces back to find the best path (step 816) and identifies any series of words aligned with a state other than the general language state as name entities (step 818). Then, the process extracts the identified name entities (step 820) and ends.

[0086] In the above algorithm, it is assumed that a sufficient amount of annotated utterances is used to train the general language model. More particularly, the probabilities G(ENT_iw_t) and G(w_tENT_i) can be calculated only when there is boundary information of name entities in the utterances. In practice, this is very expensive. In accordance with a preferred embodiment of the present invention, a technique is provided to iteratively decode the natural language utterances and update the general language model.

[0087] First, all the natural language utterances are decoded using the probability distribution defined in equation (9). $\begin{array}{cc}P(w_t,S_t{S}_{t-1},w_{t-1})=\{\begin{array}{cc}\left(1-\right)G(w_t{w}_{t-1})/\left(K+1\right),& \mathrm{if}{S}_{t-1}=S_t=s_0,\\ E_i(w_t{\mathrm{ENT}}_i\mathrm{\_START})/\left(K+1\right),& \mathrm{if}{S}_{t-1}=s_0,S_t=s_i{s}_0,\\ E_i^{}({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1})/(V\left(K+1\right)),& \mathrm{if}{S}_{t-1}=s_i{s}_0,S_t=s_0,\\ E_i\left({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1})E_j(w_t{\mathrm{ENT}}_j\mathrm{\_START}\right)/\left(K+1\right),& \mathrm{if}{S}_{t-1}=s_i{s}_0,S_t=s_j{s}_0,s_i{s}_j,\\ \left[1-\left(+\right)E_i\left({\mathrm{ENT}}_i\mathrm{\_END}{w}_{t-1})\right]E_i(w_t{w}_{t-1}\right)/\left(K+1\right),& \mathrm{if}{S}_{t-1}=S_t=s_i{s}_0,\end{array}& \left(9\right)\end{array}$

[0088] where V is the vocabulary size, is a large value such as 0.999, and are small values such as 0.001.

[0089] Equation (9) is derived from (8) by assuming a flat probability distribution of G(ENT_iw_t), G(w_tENT_i) as well as G(ENT_j_STARTENT_iEND), and properly adjusting the parameters _i, _i, _ij (1iK). Apparently, P(w_t,S_tS_t1, w_t1) satisfies the unitary condition: $\underset{w_t,S_t}{}P(w_t,S_t{S}_{t-1},w_{t-1})=1.$

[0090] After the initial decoding of all the raw natural language utterances using the probability distribution of (9), an iterative retraining technique is used to calculate the probabilities G(ENT_iw_t), G(w_tENT_i) and G(ENT_jSTARTENT_iEND) as well as other bigram probabilities in the general language model. Then, the probabilities defined in equation (8) are used to re-decode the raw utterance and update the general language model with which we can decode the raw data again. This process may repeat until the decoded result, and therefore the general language model, does not change. In this way, a name entity extractor may be achieved without manually annotating a large amount of text data.

[0091] Turning now to FIG. 9, a flowchart illustrating the operation of an iterative decoding and retraining process is shown in accordance with a preferred embodiment of the present invention. The process begins and sets initial probabilities in the general language model (step 902). Then, the process extracts name entities in a corpus of training sentences (step 904) and replaces the name entities with name entity labels in the training sentences (step 906). The process then retrains the general language models using the training sentences with name entity labels (step 908) and a determination is made as to whether probabilities in the general language models have changed (step 910). If the general language model has changed, the process returns to step 904 to re-decode the training sentences and retrain the general language model; otherwise, the process ends.

[0092] The decode-and-retrain technique allows a developer to build a name entity extractor without manually annotate large amount of natural language utterances. However, the technique still requires a large amount of text utterances to be collected. Data collection is an expensive process which requires a lot of money and time. Furthermore, collected data is usually domain-dependent and the resulting model is also domain-dependent. Therefore, the model obtained from one application cannot be applied to other applications to extract the same name entity.

[0093] Thus, in accordance with a preferred embodiment of the present invention, a uniform bigram language model is used for the general language model. The uniform bigram language model is defined as follows:

[0094] The probability defined by equation (10) is not a true probability distribution. This uniform probability distribution is introduced to provide some background probability value for word pairs that are impossible to appear in the name entities.

[0095] Using the uniform bigram language model for the general language model makes it unnecessary to collect a large amount of domain-dependent natural language utterances to train the general language model. It also makes the approach domain-independent and the vocabulary size is infinite.

[0096] The present invention provides an automatic, extensible and domain-independent name entity extraction technique. The name entity extraction technique of the present invention allows name entity language models to be reused, expedites the development process, and improves consistency and recognition performance. The context of the name entities could be drastically different in different applications. Therefore, the models for these name entities based on the context information could be quite different from application to application. However, the way to say the name entities themselves, regardless of the context around them usually conforms to some regular formats. Usually name entities could be recognized without the information of their surrounding contexts. In the name entity extraction method of the present invention, the linguistic information within the name entities themselves is emphasized. The context information around the name entities are encoded by, in case of bigram language model, the probabilities G(w_tENT_i), G(ENT_iw_t) and G(ENT_iENT_j) where (1<i, j<(K1)). Rather than manually annotating a set of domain-dependent data to train the statistical model, the only effort made in this approach is to build domain-independent linguistic models for name entities, and use the conventional statistical methods to decode unsupervisedly.

[0097] The technique of the present invention is also extensible. Once the model of a name entity is established, the model can be directly applied to other domains of application. The decoding algorithm can accept any number of models of name entities and simultaneously extract all interested name entities at the end of the decoding. With this new technique, developers can build generic models for some commonly seen name entities, such as currency amount, location, date, time etc. In a new application, one can reuse the development work that was done in some previous applications, and develop the models for the name entities specific to this new domain. The newly developed models could again be reused in future applications.

[0098] It is important to note that while the present invention has been described in the context of a fully functioning data processing system, those of ordinary skill in the art will appreciate that the processes of the present invention are capable of being distributed in the form of a computer readable medium of instructions and a variety of forms and that the present invention applies equally regardless of the particular type of signal bearing media actually used to carry out the distribution. Examples of computer readable media include recordable-type media, such as a floppy disk, a hard disk drive, a RAM, CD-ROMs, DVD-ROMs, and transmission-type media, such as digital and analog communications links, wired or wireless communications links using transmission forms, such as, for example, radio frequency and light wave transmissions. The computer readable media may take the form of coded formats that are decoded for actual use in a particular data processing system.

[0099] The description of the present invention has been presented for purposes of illustration and description, and is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art. Although the depicted illustrations show the mechanism of the present invention embodied on a single server, this mechanism may be distributed through multiple data processing systems. The embodiment was chosen and described in order to best explain the principles of the invention, the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.