Method and apparatus for detecting data anomalies in statistical natural language applications

• US 20070016399A1
• Filed: 07/12/2005
• Published: 01/18/2007
• Est. Priority Date: 07/12/2005
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gao, Yuqing, Pieraccini, Roberto, Kuo, Hong-Kwang, Wu, Cheng, Quinn, Jerome
• Application Number:
  US11/179,789
• Publication Number:
  US 20070016399A1
• Time in Patent Office: Days
• US Class Current: 704/5
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

Techniques for detecting data anomalies in a natural language understanding (NLU) system are provided. A number of categorized sentences, categorized into a number of categories, are obtained. Sentences within a given one of the categories are clustered into a number of sub clusters, and the sub clusters are analyzed to identify data anomalies. The clustering can be based on surface forms of the sentences. The anomalies can be, for example, ambiguities or inconsistencies. The clustering can be performed, for example, with a K-means clustering algorithm.

Claims

1. A computer-implemented method of detecting data anomalies in a natural language understanding (NLU) system, comprising the steps of:

obtaining a plurality of categorized sentences that are categorized into a plurality of categories;

clustering those of said sentences within a given one of said categories into a plurality of subclusters; and

analyzing said subclusters to identify data anomalies therein.

2. The method of claim 1, wherein said clustering is based on surface forms of said sentences.

3. The method of claim 1, wherein said data anomalies comprise data ambiguities.

4. The method of claim 1, wherein said clustering comprises clustering with a K-means clustering algorithm.

5. The method of claim 1, wherein said subclusters have centroids and said analyzing step comprises determining at least one parameter associated with pairs of said centroids for selected ones of said subclusters falling into different ones of said categories.

6. The method of claim 5, wherein said categorized sentences have features and are represented as feature vectors that are normalized into normalized feature vectors, and wherein said at least one parameter comprises a similarity metric given by:

sim({square root over (v)}₁, {square root over (v)}₂)={square root over (v)}₁·

{square root over (v)}₂=Σ

_i{square root over (v)}₁[i]{square root over (v)}₂[i]

where the i^th normalized feature vector is given by;

{right arrow over (v)}[i]=v′

[i]/∥

v′

∥

, with ∥

v′

∥

=√

{square root over (Σ

_iv′

[i]²)}, and where, for each sentence with corresponding class label c_k, for each given one of said features f_i, v′

[i]=v[i]λ

(f_i, c_k), where λ

(f_i, c_k) is a feature/class pair.

7. The method of claim 1, wherein said categorized sentences are categorized according to a categorization model and said analyzing step comprises:

applying said categorization model to sentences within a given one of said subclusters to obtain model results; and

analyzing said model results to detect the presence of at least one of conflicting labeling and potentially incorrect labeling.

8. The method of claim 1, wherein at least some of said subclusters are represented by a canonical sentence.

9. The method of claim 1, wherein at least some of said subclusters are represented by a centroid comprising important words with weights.

10. The method of claim 9, wherein said categorized sentences are represented as feature vectors, and wherein said centroids are represented by centroid vectors in the form:

{right arrow over (C)}(k)=(Σ

<sub>vjε

cluster(k)</sub>{circumflex over (v)}_j)/N_k,

for the k^th cluster, having N_k members, where;

v_j is the j^th feature vector in said cluster, and is a corresponding normalized feature vector to said j^th feature vector in said cluster.

11. The method of claim 1, further comprising the additional step of relabeling selected ones of said sentences, on a subcluster basis as opposed to a sentence-by-sentence basis, responsive to identification of said data anomalies.

12. The method of claim 11, wherein said data anomalies comprise data inconsistencies.

13. The method of claim 1, wherein said clustering step comprises the sub-steps of:

checking a given number of said sentences that have been clustered into a given one of said subclusters against a quantity criteria; and

reassigning said given number of said sentences to another given one of said subclusters responsive to said checking against said quantity criteria.

14. The method of claim 1, wherein said clustering step comprises the sub-steps of:

modeling each of said sentences as a feature vector; and

creating a new centroid model for those of said feature vectors that differ, by more than a specified amount, from any existing centroid models.

15. The method of claim 1, wherein a first portion of said sentences fall within a first one of said classes and a second portion of said sentences, having surface forms similar to surface forms of said first portion of said sentences, fall within a second one of those classes, further comprising the additional steps of:

forming a new set for said first and second portions of said sentences; and

obtaining data representative of a disambiguation dialog suitable for disambiguating between said first and second portions of said sentences.

16. The method of claim 15, wherein said obtaining step comprises:

prompting a user to construct said disambiguation dialog; and

receiving said data from said user.

17. The method of claim 1, wherein said clustering step comprises the sub-steps of:

assigning each of said sentences to a pre-existing centroid corresponding to a given subcluster;

computing a distortion measure; and

responsive to a change in said distortion measure being at least equal to a threshold value, conducting an additional iteration of said assigning and computing steps.

18. A computer program product comprising a computer usable medium having computer usable program code for detecting data anomalies in a natural language understanding (NLU) system, said computer program product including:

computer usable program code for obtaining a plurality of categorized sentences that are categorized into a plurality of categories;

computer usable program code for clustering those of said sentences within a given one of said categories into a plurality of subclusters; and

computer usable program code for analyzing said subclusters to identify data anomalies therein.

19. The computer program product of claim 18, wherein said clustering is based on surface forms of said sentences.

20. An apparatus for detecting data anomalies in a natural language understanding (NLU) system, comprising:

a memory; and

at least one processor coupled to said memory and operative to;

obtain a plurality of categorized sentences that are categorized into a plurality of categories;

cluster those of said sentences within a given one of said categories into a plurality of subclusters; and

analyze said subclusters to identify data anomalies therein.