Method for named-entity recognition and verification

• US 7,171,350 B2
• Filed: 08/26/2002
• Issued: 01/30/2007
• Est. Priority Date: 05/03/2002
• Status: Expired due to Fees

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Lin, Yi-Chung, Hung, Peng-Hsiang
• Primary Examiner(s): Hudspeth; David
• Assistant Examiner(s): ALBERTALLI, BRIAN LOUIS
• Application Number:
  US10/227,470
• Publication Number:
  US 20030208354A1
• Time in Patent Office: 1,618 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

A method for named-entity (NE) recognition and verification is provided. The method can extract at least one to-be-tested segments from an article according to a text window, and use a predefined grammar to parse the at least one to-be-tested segments to remove ill-formed ones. Then, a statistical verification model is used to calculate the confidence measurement of each to-be-tested segment to determine where the to-be-tested segment has a named-entity or not. If the confidence measurement is less than a predefined threshold, the to-be-tested segment will be rejected. Otherwise, it will be accepted.

Claims

1. A method for named-entity recognition and verification, comprising the steps of:

(A) segmenting text data from an article into at least one to-be-tested segments according to a text window;

(B) parsing the to-be-tested segments to remove ill-formed segments from the to-be-tested segments according to a predefined grammar;

(C) using a hypothesis test to assess a confidence measure of each to-be-tested segment, wherein the confidence measure is determined from dividing a probability

$P<br><br>\left(o<br><br><br><br>\begin{array}{c}L,x\\ L,1\end{array},o<br><br>\begin{array}{c}C,y\\ C,1\end{array},o<br><br>\begin{array}{c}R,z\\ R,1\end{array}|H_0\right)$

of assuming that the to-be-teated tested segment has a named-entity by a probability

$P<br><br>\left(o<br><br><br><br>\begin{array}{c}L,x\\ L,1\end{array},o<br><br>\begin{array}{c}C,y\\ C,1\end{array},o<br><br>\begin{array}{c}R,z\\ R,1\end{array}|H_1\right)$

of assuming that the to-be-tested segment doesn'"'"'t have a named-entity, where

$O<br><br>\begin{array}{c}C,y\\ C,1\end{array}$

is a candidate,

$O<br><br>\begin{array}{c}L,x\\ L,1\end{array}$

is the left context of the candidate, and

$O<br><br>\begin{array}{c}R,z\\ R,1\end{array}$

is the right context of the candidate; and

(D) determining that the to-be-tested segment has a named-entity if the confidence measure is greater than a predefined threshold, wherein the confidence measure is expressed by a log likelihood ratio,

$\mathrm{LLR}<br><br>\left(O<br><br>\begin{array}{c}L,x\\ L,1\end{array},O<br><br>\begin{array}{c}C,y\\ C,1\end{array},O<br><br>\begin{array}{c}R,z\\ R,1\end{array}\right)=\log <br><br>\frac{P<br><br>\left(O<br><br>\begin{array}{c}L,x\\ L,1\end{array},O<br><br>\begin{array}{c}C,y\\ C,1\end{array},O<br><br>\begin{array}{c}R,z\\ R,1\end{array}|H_0\right)}{P<br><br>\left(O<br><br>\begin{array}{c}L,x\\ L,1\end{array},O<br><br>\begin{array}{c}C,y\\ C,1\end{array},O<br><br>\begin{array}{c}R,z\\ R,1\end{array}|H_1\right)}.$

2. The method as claimed in claim 1, wherein the text window has a plurality of random variables.

3. The method as claimed in claim 2, wherein the random variables have the candidate and its left and right contexts, and the named-entity of the to-be-tested segment corresponds to the candidate.

4. The method as claimed in claim 3, wherein the text window is

$O=\left(o\; <li></li><br><br>\begin{array}{c}L,x\\ L,1\end{array},o<br><br>\begin{array}{c}C,y\\ C,1\end{array},o<br><br>\begin{array}{c}R,z\\ R,1\end{array}\right).$

5. The method as claimed in claim 4, wherein in step (D), the confidence measure is determined by using Neyman-Pearson Lemma.

6. The method as claimed in claim 1, wherein a named-entity model (NE model) is used to determine log

$P$

( o L , 1 L , x , o C1 C , y , o R , 1 R , z | H 0 ) ,

where

$P<br><br>\left(O<br><br>\begin{array}{c}L,x\\ L,1\end{array},O<br><br>\begin{array}{c}C,y\\ C,1\end{array},O<br><br>\begin{array}{c}R,z\\ R,1\end{array}|H_0\right)$

approximates to

$P_0<br><br>\left(o_{L,1}^{L,x},o_{\mathrm{C1}}^{C,y},o_{R,1}^{R,z}\right),$

and

$P_0<br><br>\left(o_{L,1}^{L,x},o_{\mathrm{C1}}^{C,y},o_{R,1}^{R,z}\right)$

approximates to

$P_0<br><br>\left(o_{L,1}^{L,x}\right)<br><br>P_0<br><br>\left(o_{\mathrm{C1}}^{C,y}\right)<br><br>P_0<br><br>\left(o_{R,1}^{R,z}\right).$

7. The method as claimed in claim 6, wherein

$P_0$

( o L , 1 L , x )

approximates to

$\underset{i=1}{\overset{x}{\prod <br><br>}}<br><br><br><br>P_0<br><br>\left(o_{L,i}|o_{L,i-N+1}^{L,i-1}\right),$

and

$P_0<br><br>\left(o_{L,i}|o_{L,i-N+1}^{L,i-1}\right)$

equals to

$\{\begin{array}{ccc}{P}_0<br><br>\left(o_{L,i}|o_{L,1}^{L,i-1}\right),& \mathrm{if}<br><br><br><br>N><br><br>1<br><br><br><br>\mathrm{and}<br><br><br><br>i><br><br>1& \mathrm{and}<br><br><br><br>i-N\le <br><br>0\\ P_0<br><br>\left(o_{L,i}\right),<br><br>& \mathrm{if}<br><br><br><br>N=1<br><br><br><br>\mathrm{or}<br><br><br><br>i=1<br><br>& \end{array},$

where N is a positive integer.

8. The method as claimed in claim 6, wherein

$P_0$

( o R , 1 R , z )

approximates to

$\underset{i=1}{\overset{2}{\prod <br><br>}}<br><br><br><br>P_0(o_{R,i}<br><br><br><br>o_{R,i-N+1}^{R,i-1}),$

and

$P_0(o_{R,i}<br><br><br><br>o_{R,i-N+1}^{R,i-1})$

equals to

$\{\begin{array}{cc}{P}_0<br><br>\left(o_{R,i}<br><br><br><br>o_{R,1}^{R,i-1}\right),& \mathrm{if}<br><br><br><br>N><br><br>1<br><br><br><br>\mathrm{and}<br><br><br><br>i><br><br>1<br><br><br><br>\mathrm{and}<br><br><br><br>i-N\le <br><br>0\\ P_0<br><br>\left(o_{R,i}\right),& \mathrm{if}<br><br><br><br>N=1<br><br><br><br>\mathrm{or}<br><br><br><br><br><br>i=1<br><br>\end{array},$

where N is a positive integer.

9. The method as claimed in claim 6, wherein

$P_0$

( o C , 1 C , y )

equals to

$\underset{T}{\sum <br><br>}<br><br>P_0<br><br>\left(T\right),$

and

$\underset{T}{\sum <br><br>}<br><br>P_0<br><br>\left(T\right)$

approximates to

$\underset{T}{\max }<br><br>P_0<br><br>\left(T\right)=\underset{T}{\max }<br><br>\underset{A\to <br><br>\mathrm{\alpha <br><br>}\in <br><br>T}{\overset{}{\prod <br><br>}}<br><br><br><br>P_0<br><br>\left(\mathrm{\alpha <br><br>}|A\right),$

where T is a possible parsing tree, and A→

α

is a rule in the parsing tree T.

10. The method as claimed in claim 9, wherein the NE model

$S_{\mathrm{NE}}$

( o L , ⁢

1 L , ⁢

x , ⁢

o C , ⁢

1 C , ⁢

y , ⁢

o R , ⁢

1 R , ⁢

z ) ⁢

⁢

is ⁢

⁢

∑

i = 1 x ⁢

⁢

log ⁢

⁢

P 0 ⁡

( o L , ⁢

i | o L , ⁢

i - N + 1 L , ⁢

i - 1 ) + ∑

i = 1 z ⁢

⁢

log ⁢

⁢

P 0 ⁡

( o R , ⁢

i | o R , ⁢

i - N + 1 R , ⁢

i - 1 ) + max T ⁢

∑

A ->

α

∈

T ⁢

⁢

log ⁢

⁢

P 0 ⁡

( α

| A ) ⁢

.

11. The method as claimed in claim 1, wherein an anti-named-entity model (anti-NE model) is used to determine

$P$

( o L , ⁢

1 L , ⁢

x , ⁢

o C , ⁢

1 C , ⁢

y , ⁢

o R , ⁢

1 R , ⁢

z | H 1 ) ,

where

$P(o_{L,1}^{L,x},o_{C,1}^{C,y},o_{R,1}^{R,z}<br><br><br><br>H_1)<br><br><br><br>\mathrm{is}<br><br><br><br>P_1<br><br>\left(o_{L,1}^{L,x},o_{C,1}^{C,y},o_{R,1}^{R,z}\right),P_1<br><br>\left(o_{L,1}^{L,x},o_{C,1}^{C,y},o_{R,1}^{R,z}\right)$

approximates to

$\underset{i=1}{\overset{x}{\prod <br><br>}}<br><br><br><br>P_1(o_{L,i}<br><br><br><br>o_{L,i-N+1}^{L,i-1})\times <br><br>\underset{i=1}{\overset{y}{\prod <br><br>}}<br><br><br><br>P_1(o_{C,i}<br><br><br><br>o_{C,i-N+1}^{C,i-1})\times <br><br>\underset{i=1}{\overset{z}{\prod <br><br>}}<br><br><br><br>P_1(o_{R,i}<br><br><br><br>o_{R,i-N+1}^{R,i-1}),$

and N is a positive integer.

12. The method as claimed in claim 11, wherein o_R,j equals to o_C,y+j if j=0, −

1, −

2, . . . , o_C,j equals to o_L,x+j if j=0, −

1, −

2, . . . , and

$P_1<br><br>\left(o_{L,i}<br><br><br><br>o_{L,i-N+1}^{L,i-1}\right)$

equals to

$\{\begin{array}{cc}{P}_1<br><br>\left(o_{L,i}<br><br><br><br>o_{L,1}^{L,i-1}\right),& \mathrm{if}<br><br><br><br>N><br><br>1<br><br><br><br>\mathrm{and}<br><br><br><br>i><br><br>1<br><br><br><br>\mathrm{and}<br><br><br><br>i-N\le <br><br>0\\ P_1<br><br>\left(o_{L,i}\right),& \mathrm{if}<br><br><br><br>N=1<br><br><br><br>\mathrm{or}<br><br><br><br><br><br>i=1<br><br>\end{array}.$

13. The method as claimed in claim 11, wherein the anti-NE model

$S_{\mathrm{anti}-\mathrm{NE}}$

( o L , ⁢

1 L , ⁢

x , ⁢

o C , ⁢

1 C , ⁢

y , ⁢

o R , ⁢

1 R ⁢

, ⁢

z ) ⁢

⁢

is ⁢

⁢

∑

i = 1 x ⁢

⁢

log ⁢

⁢

P 1 ⁡

( o L , ⁢

i | o L , ⁢

i - N + 1 L , ⁢

i - 1 ) + ∑

i = 1 y ⁢

⁢

log ⁢

⁢

P 1 ⁡

( o C , ⁢

i | o C , ⁢

i - N + 1 C , ⁢

i - 1 ) + ∑

i = 1 z ⁢

⁢

log ⁢

⁢

P 1 ⁡

( o R , ⁢

i | o R , ⁢

i - N + 1 R , ⁢

i - 1 ) ⁢

. ⁢

14. The method as claimed in claim 1, wherein the candidate

$o_{C,}^{}$

1 C , ⁢

y

is composed of random variables o_c,1, o_c,2 . . . , and o_c,y, where y is the number of characters of the candidate.

15. The method as claimed in claim 1, wherein the left context

$o_{L,}^{}$

1 L , ⁢

x

is composed of random variables o_L,1, o_L,2 . . . , and o_L,x, where x is the number of characters of the left context.

16. The method as claimed in claim 1, wherein the right context

$o_{R,}^{}$

1 R ⁢

, ⁢

⁢

z

is composed of random variables o_R,1, o_R,2 . . . , and o_R,z, where z is the number of characters of the right context.

17. The method as claimed in claim 2, wherein each random variable is a Chinese character.

18. The method as claimed in claim 2, wherein each random variable is an English word.