System and method for utilizing distance measures to perform text classification

US 20060142993A1
Filed: 12/28/2004
Published: 06/29/2006
Est. Priority Date: 12/28/2004
Status: Abandoned Application

First Claim

Patent Images

1. A system for performing text classification, comprising:

text classification categories that each include reference models of reference N-grams;

input text that includes input N-grams upon which said text classification is performed; and

a text classifier that calculates distance measures between said input N-grams and said reference N-grams, said text classifier utilizing said distance measures to identify a matching category for said input text.

View all claims

1 Assignment

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A system and method for utilizing distance measures to perform text classification includes text classification categories that each have reference models of reference N-grams. Input text that includes input N-grams is accessed for performing the text classification. A text classifier calculates distance measures between the input N-grams and the reference N-grams. The text classifier then utilizes the distance measures to identify a matching category for the input text. In certain embodiments, a verification module performs a verification procedure to determine whether the initially-selected matching category is a valid classification result for the text classification.

88 Citations

View as Search Results

41 Claims

1. A system for performing text classification, comprising:
- text classification categories that each include reference models of reference N-grams;
  
  input text that includes input N-grams upon which said text classification is performed; and
  
  a text classifier that calculates distance measures between said input N-grams and said reference N-grams, said text classifier utilizing said distance measures to identify a matching category for said input text.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
- - 2. The system of claim 1 wherein a verification module performs a verification procedure to determine whether said matching category is a valid classification result for said text classification.
  - 3. The system of claim 1 wherein said distance measures quantify correlation characteristics between said input text and said reference models.
  - 4. The system of claim 1 wherein each of said text classification categories corresponds to a different text classification subject.
  - 5. The system of claim 1 wherein said text classifier calculates input statistics corresponding to said input N-grams, reference statistics corresponding to said reference models, and said distance measures by comparing said input statistics and said reference statistics.
  - 6. The system of claim 1 wherein said input N-grams and said reference N-grams are configured as unigrams that each are formed of a single word.
  - 7. The system of claim 1 wherein said input N-grams and said reference N-grams are configured as bi-grams that each are formed of a word pair.
  - 8. The system of claim 1 wherein said input N-grams and said reference N-grams are configured as tri-grams that each are formed of a word triplet.
  - 9. The system of claim 1 wherein said text classifier calculates input statistics corresponding to said input N-grams, each of said input statistics defining an observation frequency for one of said input N-grams in said input text.
  - 10. The system of claim 9 wherein said input statistics are calculated with formulas:
    - $P (w_{i}) = \frac{C (w_{i})}{\sum_{w_{i}} C (w_{i})}, P (w_{i} | w_{i - 1}) = \frac{C (w_{i - 1} w_{i})}{\sum_{w_{i}} C (w_{i - 1} w_{i})}, P (w_{i} | w_{i - 2} w_{i - 1}) = \frac{C (w_{i - 2} w_{i - 1} w_{i})}{\sum_{w_{i}} C (w_{i - 2} w_{i - 1} w_{i})}$ where P(w_i) is a first frequency of single word unigrams, P(w_i|wi-1) is a second frequency of word-pair bigrams, P(w_i|w_i-2w_i-1) is a third frequency of three-word trigrams, and C(w_i) is said observation frequency of a word w_i.
  - 11. The system of claim 1 wherein said text classifier calculates reference statistics corresponding to said reference N-grams, each of said reference statistics defining an observation frequency for one of said reference N-grams in a corresponding reference database for one of said text classification categories.
  - 12. The system of claim 9 wherein said reference statistics are calculated with formulas:
    - $P (w_{i}) = \frac{C (w_{i})}{\sum_{w_{i}} C (w_{i})}, P (w_{i} | w_{i - 1}) = \frac{C (w_{i - 1} w_{i})}{\sum_{w_{i}} C (w_{i - 1} w_{i})}, P (w_{i} | w_{i - 2} w_{i - 1}) = \frac{C (w_{i - 2} w_{i - 1} w_{i})}{\sum_{w_{i}} C (w_{i - 2} w_{i - 1} w_{i})}$ where P(w_i) is a first frequency of single word unigrams, P(w_i|wi-1) is a second frequency of word-pair bigrams, P(w_i|w_i-2w_i-1) is a third frequency of three-word trigrams, and C(w_i) is said observation frequency of a word w_i.
  - 13. The system of claim 1 wherein said distance measures are calculated with a formula:
    - $D (inp, tar) = \sum_{Seq (w_{i}) \in input} (F_{tar} (w_{i}) \ln (\frac{F_{tar} (w_{i})}{F_{inp} (w_{i})}) + (1 - F_{tar} (w_{i})) \ln (\frac{1 - F_{tar} (w_{i})}{1 - F_{inp} (w_{i})}))$ where D(inp, tar) is a current distance measure between a current input N-gram and a current reference model, said F_inp(w_i) being an N-gram probability statistic estimated from said input text, said F_tar(w_i) being an N-gram probability statistic estimated from said reference models.
  - 14. The system of claim 1 wherein said text classifier generates an N-best list of classification candidates that are ranked according to said distance measures.
  - 15. The system of claim 14 wherein a top candidate from said N-best list of classification candidates is a proposed text classification result for said text classification.
  - 16. The system of claim 1 wherein a verification module accesses a pre-defined verification threshold value for performing a verification procedure for said matching category.
  - 17. The system of claim 1 wherein a verification module accesses said distance measures to calculate a verification measure corresponding to said text classification.
  - 18. The system of claim 17 wherein said verification measure is calculated with a formula:
    - Verification Measure=Distance A/Average Distance B where Distance A is a best distance measure for a top classification candidate, and Average Distance B is an average distance measure from all remaining classification candidates.
  - 19. The system of claim 17 wherein said verification manager compares said verification measure and a verification threshold value to confirm said matching category for said text classification.
  - 20. The system of claim 19 wherein said matching category of the a hypothesis is accepted when said verification measure is less than said verification threshold, and wherein said matching category of said first hypothesis is rejected and said input text is not classified when said verification measure is greater than or equal to said verification threshold.

21. A method for performing text classification, comprising:
- providing text classification categories that each include reference models of reference N-grams;
  
  accessing input text that includes input N-grams upon which said text classification is performed;
  
  calculating distance measures between said input N-grams and said reference N-grams; and
  
  utilizing said distance measures to identify a matching category for said input text.
- View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40)
- - 22. The method of claim 21 further comprising determining whether said matching category is a valid classification result for said text classification.
  - 23. The method of claim 21 wherein said distance measures quantify correlation characteristics between said input text and said reference models.
  - 24. The method of claim 21 wherein each of said text classification categories corresponds to a different text classification subject.
  - 25. The method of claim 21 further comprising calculating input statistics corresponding to said input N-grams, calculating reference statistics corresponding to said reference models, and calculating said distance measures by comparing said input statistics and said reference statistics.
  - 26. The method of claim 21 wherein said input N-grams and said reference N-grams are configured as unigrams that each are formed of a single word.
  - 27. The method of claim 21 wherein said input N-grams and said reference N-grams are configured as bi-grams that each are formed of a word pair.
  - 28. The method of claim 21 wherein said input N-grams and said reference N-grams are configured as tri-grams that each are formed of a word triplet.
  - 29. The method of claim 21 further comprising calculating input statistics corresponding to said input N-grams, each of said input statistics defining an observation frequency for one of said input N-grams in said input text.
  - 30. The method of claim 29 wherein said input statistics are calculated with formulas:
    - $P (w_{i}) = \frac{C (w_{i})}{\sum_{w_{i}} C (w_{i})}, P (w_{i} | w_{i - 1}) = \frac{C (w_{i - 1} w_{i})}{\sum_{w_{i}} C (w_{i - 1} w_{i})}, P (w_{i} | w_{i - 2} w_{i - 1}) = \frac{C (w_{i - 2} w_{i - 1} w_{i})}{\sum_{w_{i}} C (w_{i - 2} w_{i - 1} w_{i})}$ where P(w_i) is a first frequency of single word unigrams, P(w_i|wi-1) is a second frequency of word-pair bigrams, P(w_i|w_i-2w_i-1) is a third frequency of three-word trigrams, and C(w_i) is said observation frequency of a word w_i.
  - 31. The method of claim 21 wherein said text classifier calculates reference statistics corresponding to said reference N-grams, each of said reference statistics defining an observation frequency for one of said reference N-grams in a corresponding reference database for one of said text classification categories.
  - 32. The method of claim 29 wherein said reference statistics are calculated with formulas:
    - $P (w_{i}) = \frac{C (w_{i})}{\sum_{w_{i}} C (w_{i})}, P (w_{i} | w_{i - 1}) = \frac{C (w_{i - 1} w_{i})}{\sum_{w_{i}} C (w_{i - 1} w_{i})}, P (w_{i} | w_{i - 2} w_{i - 1}) = \frac{C (w_{i - 2} w_{i - 1} w_{i})}{\sum_{w_{i}} C (w_{i - 2} w_{i - 1} w_{i})}$ where P(w_i) is a first frequency of single word unigrams, P(w_i|wi-1) is a second frequency of word-pair bigrams, P(w_i|w_i-2w_i-1) is a third frequency of three-word trigrams, and C(w_i) is said observation frequency of a word w_i.
  - 33. The method of claim 21 wherein said distance measures are calculated with a formula:
    - $D (inp, tar) = \sum_{Seq (w_{i}) \in input} (F_{tar} (w_{i}) \ln (\frac{F_{tar} (w_{i})}{F_{inp} (w_{i})}) + (1 - F_{tar} (w_{i})) \ln (\frac{1 - F_{tar} (w_{i})}{1 - F_{inp} (w_{i})}))$ where D(inp, tar) is a current distance measure between a current input N-gram and a current reference model, said F_inp(w_i) being an N-gram probability statistic estimated from said input text, said F_tar(w_i) being an N-gram probability statistic estimated from said reference models.
  - 34. The method of claim 21 wherein said text classifier generates an N-best list of classification candidates that are ranked according to said distance measures.
  - 35. The method of claim 34 wherein a top candidate from said N-best list of classification candidates is a proposed text classification result for said text classification.
  - 36. The method of claim 21 further comprising accessing a pre-defined verification threshold value for performing a verification procedure for said matching category.
  - 37. The method of claim 21 further comprising accessing said distance measures to calculate a verification measure corresponding to said text classification.
  - 38. The method of claim 37 wherein said verification measure is calculated with a formula:
    - Verification Measure=Distance A/Average Distance B where Distance A is a best distance measure for a top classification candidate, and Average Distance B is an average distance measure from all remaining classification candidates.
  - 39. The method of claim 37 further comprising comparing said verification measure and a verification threshold value to confirm said matching category for said text classification.
  - 40. The method of claim 39 wherein said matching category of the a hypothesis is accepted if said verification measure is less than said verification threshold, and wherein said matching category of said first hypothesis is rejected and said input text is not classified if said verification measure is larger than or equal to said verification threshold.

41. A system for performing text classification, comprising:
- means for providing text classification categories that each include reference models of reference N-grams;
  
  means for accessing input text that includes input N-grams upon which said text classification is performed;
  
  means for calculating distance measures between said input N-grams and said reference N-grams; and
  
  means for utilizing said distance measures to identify a matching category for said input text.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
Original Assignee
Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
Inventors
Emonts, Michael W., Duan, Lei, Menendez-Pidal, Xavier

Application Number

US11/024,095
Publication Number

US 20060142993A1
Time in Patent Office

Days
Field of Search
US Class Current

704/9
CPC Class Codes

G06F 16/353 into predefined classes

System and method for utilizing distance measures to perform text classification

First Claim

1 Assignment

0 Petitions

Accused Products

Abstract

88 Citations

41 Claims

Specification

Solutions

Use Cases

Quick Links

System and method for utilizing distance measures to perform text classification

First Claim

1 Assignment

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

88 Citations

41 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links