Dictionary learning method and device using the same, input method and user terminal device using the same

US 20060206313A1
Filed: 01/24/2006
Published: 09/14/2006
Est. Priority Date: 01/31/2005
Status: Abandoned Application

First Claim

Patent Images

1. A dictionary learning method, comprising the steps of:

learning a lexicon and a Statistical Language Model from an untagged corpus;

integrating the lexicon, the Statistical Language Model and subsidiary word encoding information into a dictionary.

View all claims

1 Assignment

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

This invention provides a dictionary learning method, said method comprising the steps of: learning a lexicon and a Statistical Language Model from an untagged corpus; integrating the lexicon, the Statistical Language Mode and subsidiary word encoding information into a small size dictionary. And this invention also provides an input method on a user terminal device using the dictionary with Part-of-Speech information and a Part-of-Speech Bi-gram Model added, and a user terminal device using the same. Therefore, sentence level prediction and word level prediction can be given by the user terminal device and the input is speeded up by using the dictionary which is searched by a Patricia Tree index of a dictionary index.

Citations

28 Claims

1. A dictionary learning method, comprising the steps of:
- learning a lexicon and a Statistical Language Model from an untagged corpus;
  
  integrating the lexicon, the Statistical Language Model and subsidiary word encoding information into a dictionary.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
- - 2. The dictionary learning method as claimed in claim 1, said method further comprising the steps of:
    - obtaining Part-of-Speech information for each word in the lexicon and a Part-of-Speech Bi-gram Model from a Part-of-Speech tagged corpus; and
      
      adding the Part-of-Speech information and the Part-of-Speech Bi-gram Model into the dictionary.
  - 3. The dictionary learning method as claimed in claim 1 or 2, wherein the subsidiary word encoding information comprises Chinese encoding information or non-Chinese encoding information.
  - 4. The dictionary learning method as claimed in claim 3, wherein the Chinese encoding information comprises at least one of Pinyin encoding information and Stroke encoding information.
  - 5. The dictionary learning method as claimed in one of claims 1 and 2, wherein:
    - the step of learning a lexicon and Statistical Language Model from an untagged corpus comprises the steps of a) segmenting the untagged corpus into word sequence;
      
      b) creating a Statistical Language Model using the word sequence, wherein the Statistical Language Model comprises a Word Uni-gram Model and a Word Tri-gram model;
      
      c) computing perplexity and determining whether the perplexity is the first time to be computed or it decreases by a number more than a first threshold;
      
      d) re-segmenting the corpus into word sequence by Word Tri-gram Model and performing the step b) if the result of c) is positive;
      
      e) refining the lexicon based on the Statistical Language Model such that new words are added and unimportant words are removed if the result of c) is negative; and
      
      f) updating the word Uni-gram Model, deleting the word Tri-gram Model which is invalid and performing the step a) until the lexicon does not change any more.
  - 6. The dictionary learning method as claimed in claim 5, wherein the step a) segments the untagged corpus according to the equation $\hat{S}$
    - {w1⁢
      
      w2⁢
      
      ⁢
      
      …
      
      ⁢
      
      ⁢
      
      wnS^}=arg⁢
      
      ⁢
      
      maxs⁢
      
      P⁡
      
      (S⁢
      
      {w1⁢
      
      w2⁢
      
      ⁢
      
      …
      
      ⁢
      
      ⁢
      
      wns}),wherein S{w₁w₂. . . w_n_s} denotes a word sequence w₁w₂. . . w_n_s, P(S{w₁w₂. . . w_n_s}) denotes the probability of this word sequence'"'"'s likelihood. The optimized word sequence will be $\hat{S} {w_{1} w_{2} \dots w_{n_{\hat{S}}}} .$
  - 7. The dictionary learning method as claimed in claim 6, wherein the step d) comprises re-segmenting the corpus by using maximal matching based on the lexicon.
  - 8. The dictionary learning method as claimed in claim 5, wherein the step a) comprises segmenting the corpus by using maximal matching based on the lexicon.
  - 9. The dictionary learning method as claimed in claim 8, wherein the step d) comprises re-segmenting the corpus by using maximal matching based on the lexicon.
  - 10. The dictionary learning method as claimed in claim 5, wherein the step e) comprises the steps of e1) filtering all Tri-gram entries and Bi-gram entries by a first occurrence count threshold so as to form a new word candidate list;
    - e2) filtering all candidates from the new word candidate list by a mutual information threshold as first candidates;
      
      e3) calculating Relative Entropy for all first candidates in the new word candidate list and sorting them in Relative Entropy descending order;
      
      e4) filtering all words in the Lexicon by a second occurrence count threshold so as to form a deleted word candidate list;
      
      e5) segmenting each word in the deleted word candidate list into a sequence of other words in Lexicon as second candidates;
      
      e6) calculating Relative Entropy for all of the second candidates in the deleted word candidate list and sorting them in Relative Entropy ascending order;
      
      e7) determining the number of the first candidates should be added and the number of the second candidates should be removed and updating the Lexicon.
  - 11. The dictionary learning method as claimed in claim 10, wherein the step e2) comprises calculating the mutual information of all candidates according to the equation:
    - $MI (w_{1}, w_{2} \dots w_{n}) = \frac{f (w_{1}, w_{2} \dots w_{n})}{\sum_{i = 1}^{n} f (w_{i}) - f (w_{1}, w_{2} \dots w_{n})}$ where (w₁,w₂. . . w_n) is a word sequence and f(w₁,w₂. . . w_n) denotes an occurrence frequency of the word sequence (w₁,w₂. . . w_n), and n equals to 2 or 3.

12. A dictionary learning device, comprising:
- a dictionary learning processing module which learns a dictionary;
  
  a memory unit which stores an untagged corpus;
  
  a controlling unit which controls each part of the device;
  
  wherein the dictionary learning processing module comprises a lexicon and Statistical Language Model learning unit which learns a lexicon and a Statistical Language Model from the untagged corpus; and
  
  a dictionary integrating unit which integrates the lexicon, the Statistical Language Model and subsidiary word encoding information into a dictionary.
- View Dependent Claims (13, 14, 15, 16, 17)
- - 13. The dictionary learning device as claimed in claim 12, wherein the memory unit further stores a Part-of-Speech tagged corpus, and the dictionary learning processing module further comprises:
    - a Part-of-Speech learning unit which obtains Part-of-Speech information for each word in the lexicon and a Part-of-Speech Bi-gram Model from the Part-of-Speech tagged corpus; and
      
      the dictionary integrating unit adding the Part-of-Speech information and Part-of-Speech Bi-gram Model into the dictionary.
  - 14. The dictionary learning device as claimed in claim 12 or 13, wherein the lexicon and Statistical Language Model learning unit learns a lexicon and a Statistical Language Model from the untagged corpus by segmenting the untagged corpus into word sequence;
    - creating the Statistical Language Model using the word sequence, wherein the Statistical Language Model comprises a Word Uni-gram Model and a Word-Tri-gram model;
      
      repeating to re-segment the corpus into word sequence by Word Tri-gram Model and creating the Statistical Language Model using the word sequence, until the perplexity is not the first time to be computed and is decreases by a number smaller than a first threshold;
      
      refining the lexicon based on the Statistical Language Model such that new words are added and unimportant words are removed; and
      
      updating the word Uni-gram Model, deleting the invalid word Tri-gram Model and repeating to segment the untagged corpus into word sequence until the lexicon does not change any more.
  - 15. The dictionary learning device as claimed in claim 14, wherein the lexicon and Statistical Language Model learning unit refines the lexicon by filtering all Tri-gram entries and Bi-gram entries by a first occurrence count threshold so as to form a new word candidate list;
    - filtering all candidates from the new word candidate list by a mutual information threshold as first candidates;
      
      calculating Relative Entropy for all the first candidates in the new word candidate list and sorting them in Relative Entropy descending order;
      
      filtering all words in the lexicon by a second occurrence count threshold so as to form a deleted word candidate list;
      
      segmenting each word in the deleted word candidate list into a sequence of other words in the lexicon as second candidates;
      
      calculating Relative Entropy for all the second candidates in the deleted word candidate list and sorting them in Relative Entropy ascending order;
      
      determining the number of the first candidates should be added and the number of the second candidates should be removed and updating the Lexicon.
  - 16. The dictionary learning device as claimed in claim 12, wherein the subsidiary word encoding information comprises Chinese encoding information or non-Chinese encoding information.
  - 17. The dictionary learning device as claimed in claim 16, wherein the Chinese encoding information comprises at least one of Pinyin encoding information and Stroke encoding information.

18. An input method for processing a user input, wherein the method comprises:
- a receiving step for receiving a user input;
  
  an interpreting step for interpreting the user input into encoding information or a user action, wherein the encoding information for each word in a dictionary is obtained in advance on the basis of the dictionary;
  
  a user input prediction and adjustment step for giving sentence and word prediction using Patricia Tree index in a dictionary index based on a Statistical Language Model and a Part-of-Speech Bi-gram Model in the dictionary and adjusting the sentence and word prediction according to the user action, when the encoding information or the user action is received;
  
  a displaying step for displaying the result of sentence and word prediction.
- View Dependent Claims (19, 20, 21, 22)
- - 19. The input method for processing a user input as claimed in claim 18, wherein the receiving step receives Chinese input or non-Chinese input.
  - 20. The input method for processing a user input as claimed in claim 19, wherein the Chinese input includes one of Pinyin input, Stroke input and pen trace input.
  - 21. The input method for processing a user input as claimed in claim 18, wherein the user input prediction and adjustment step comprises the steps of:
    - a) receiving the interpreted encoding information or a user action;
      
      b) modifying the predicted result if it is the user action and performing the step h);
      
      c) searching for all possible new Patricia Tree nodes of the Patricia Tree index from all current Patricia Tree nodes according to the encoding information;
      
      d) ignoring this encoding information and restoring all searching results and status and performing step a) if there are no any new Patricia Tree nodes;
      
      e) setting new Patricia Tree nodes as current Patricia Tree nodes if there are any new Patricia Tree nodes;
      
      f) searching for all possible words from the current Patricia Tree nodes and giving sentence prediction;
      
      g) determining a current word from the result of the sentence prediction, and giving word prediction, wherein the word prediction comprises a word candidate list and a predictive word candidate list; and
      
      h) outputting the predicted result to display and returning to perform the step a).
  - 22. The input method for processing a user input as claimed in claim 21, wherein the step f) gives the sentence prediction by determining the most probable word sequence as a predicted sentence according to the following equation:
    - $\hat{S} (w_{1} w_{2} \dots w_{n_{\hat{S}}}) = \arg \max_{s} \sum_{i_{1} \in {POS}_{w_{1}}, i_{2} \in {POS}_{w_{2}}, \dots} P (S (w_{1} o_{i_{1}} w_{2} o_{i_{2}} \dots w_{n_{s}} o_{i_{n_{s}}}) | I), P (S) = P (O_{i_{1}}) \frac{P (w_{1}) P (O_{i_{1}} | w_{1})}{P (O_{i_{1}})} P (O_{i_{2}} | O_{i_{1}}) \frac{P (w_{2}) P (O_{i_{2}} | w_{2})}{P (O_{i_{2}})} \dots P (O_{i_{n_{s}}} | O_{i_{n_{s} - 1}}) \frac{P (w_{n_{s}}) P (O_{i_{n_{s}}} | w_{n_{s}})}{P (O_{i_{n_{s}}})},$ where POS_w₁is a set of all Part-of-Speech that word W₁has;
      
      O_i_nis one of the Part-of-Speech of word w_n;
      
      P(O_i₁) and P(O_i₂O_i₁) are Part-of-Speech Uni-gram and Part-of-Speech Bi-gram respectively;
      
      P(w₁) is Word Uni-gram; and
      
      P(O_i₁|w₁) is the probability of a Part-of-Speech corresponding to a word.

23. A user terminal device for processing a user input, wherein the device comprises:
- a user input terminal which receives a user input;
  
  a memory unit which stores a dictionary and a dictionary index comprising a Patricia Tree index;
  
  an input processing unit which gives sentence and word prediction based on the user input; and
  
  a display which displays the result of sentence and word prediction;
  
  wherein the input processing unit comprises an input encoding interpreter which interprets the user input into encoding information or a user action, wherein the encoding information for each word in the dictionary is obtained in advance on the basis of the dictionary;
  
  a user input prediction and adjustment module which gives sentence and word prediction using Patricia Tree index in a dictionary index based on Statistical Language Model and Part-of-Speech Bi-gram Model in the dictionary and adjusts the sentence and word prediction according to the user action, when the encoding information or the user action is received.
- View Dependent Claims (24, 25, 26, 27, 28)
- - 24. The user terminal device for processing a user input as claimed in claim 23, wherein the input processing unit further comprises a dictionary indexing module which gives encoding information for each word entry of the dictionary, sorts all word entries by encoding information and Word Uni-gram, builds Patricia Tree index and adds it to the dictionary index.
  - 25. The user terminal device for processing a user input as claimed in claim 23 or 24, wherein the user input prediction and adjustment module gives sentence and word prediction and adjusts the prediction by receiving the interpreted encoding information or a user action;
    - modifying the predicted result if the received information is the user action and output the result to display;
      
      searching for all possible new Patricia Tree nodes of the Patricia Tree index from all current Patricia Tree nodes if the received information is the encoding information;
      
      ignoring this encoding information and restoring all searching results and status if there are no any new Patricia Tree nodes, then repeating to receive the interpreted encoding information or a user action;
      
      setting new Patricia Tree nodes as current Patricia Tree nodes if there are any new Patricia Tree nodes;
      
      searching for all possible words from the current Patricia Tree nodes and giving sentence prediction;
      
      determining a current word from the result of the sentence prediction, and giving word prediction, wherein the word prediction comprises a word candidate list and a predictive word candidate list; and
      
      outputting the predicted result to display.
  - 26. The user terminal device for processing a user input as claimed in claim 23, wherein the user input terminal is used for Chinese input or non-Chinese input.
  - 27. The user terminal device for processing a user input as claimed in claim 23, wherein the user input terminal can be a digital key board in which each digital button stands for several pinyin codes or several stroke codes.
  - 28. The user terminal device for processing a user input as claimed in claim 26, wherein the user input terminal can be a touch pad.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
NEC China Co Ltd (NEC Corporation)
Original Assignee
NEC China Co Ltd (NEC Corporation)
Inventors
Xu, Liqin, Hsueh, Min-Yu

Application Number

US11/337,571
Publication Number

US 20060206313A1
Time in Patent Office

Days
Field of Search
US Class Current

704/10
CPC Class Codes

G06F 40/242 Dictionaries

Dictionary learning method and device using the same, input method and user terminal device using the same

First Claim

1 Assignment

0 Petitions

Accused Products

Abstract

Citations

28 Claims

Specification

Solutions

Use Cases

Quick Links

Dictionary learning method and device using the same, input method and user terminal device using the same

First Claim

1 Assignment

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

Citations

28 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links