[Title of Invention]

METHOD FOR CLASSIFYING TEXT

[Technical Field]

[0001]

This invention is related generally to a method for classifying text, and more particularly to classifying the text for a large number of categories.

[Background Art]

[0002]

Text classification is an important problem for many tasks in natural language processing, such as user-interfaces for command and control. In such methods, training data derived from a number of classes of text are used to optimize parameters used by a method for estimating a most likely class for the text.

[0003]

Multinomial Logistic Regression (MLR) Classifiers for Text Classification.

Text classification estimates a class from an input text x, where y is a label of the class. The text can be derived from a speech signal.

[0004]

In prior art multinomial logistic regression, information about the input text is encoded using a feature function

typically defined such that [0005]

In other words, the feature is 1 if a term t _} - is contained in the text x, the class label y is equal to category

[0006]

A model used for the classification is a conditional exponential model of the form

where

lj,kfj,k ^y)

y

and and Λ are the classification parameters.

[0007]

The parameters are optimized on training pairs of texts x _t and labels y _h using an objective function

which is to be maximized with respect to Λ .

[0008]

Regularized Multinomial Logistic Regression Classifiers

Regularization terms can be added to classification parameters in logistic regression to improve a generalization capability.

[0009] In regularized multinomial logistic regression classifiers, a general formulation using both the LI -norm and the L2-norm regularizers is

where I i is an

LI -norm regularizer, and a and ? are weighting factors. This objective function is again to be maximized with respect to Λ .

[0010]

Various methods can optimize the parameters under these regularizations.

[0011]

Topic Modeling

In prior art, probabilistic latent semantic analysis (PLSA) and latent Dirichlet analysis (LDA) are generative topic models in which topics are multinomial latent variables, and the distribution of topics depends on particular document including the text where the words are distributed multinomially given the topics. If the documents are associated with classes, then such models can be used for text classification.

[0012]

However with generative topic models, the class-specific parameters and the topic-specific parameters are additive according to a logarithmic probability.

[Summary of Invention]

[0013] The embodiments of the invention provide a method for classifying text using discriminative topic transformations. The embodiments of the invention also performs classification in problems where the classes are arranged in a hierarchy.

[0014]

The method extracts features from text, and then transforms the features into topic features, before classfying text to determine scores.

[0015]

Specifically, the text is classified by determining text features from the text, and transforming the text feature to topic features. The text can be obtained from recognized speech.

[0016]

Scores are determined for each topic features using a discrcrinative topic transformation model.

[0017]

The model includes a classifier that operates on the topic features, wherein the topic features are determined by the transformation from the text features, and the transformation is optimized to maximize the scores of a correct class relative to the scores of incorrect classes.

[0018]

Then, a set of class labels with highest scores is selected for the text. The number of labels selected can be predetermined, or dynamic.

[0019]

In situations where the classes are organized in a hierarchical structure, where each class corresponds to a node in the hierarchy, the method proceeds as follows. The hierarchy can be traversed in a breadth-first order.

[0020] The first stage of the method is to evaluate the class scores of the input text at the highest level of the hierarchy (level one) using a discriminative topic transformation model trained for the level-one classes in the same way as described above. Scores for each level-one class are produced by this stage and are used to select a set of level-one classes having the greatest scores. For each of the selected level-one classes, the corresponding level-two child classes are then evaluated using a discriminative topic transformation model associated with each level-one class. The procedure repeats for one or more levels, or until the last level of the hierarchy is reached. Scores from each classifier used on the path from the top level to any node of the hierarchy are combined to yield a joint score for the classification at the level of that node. The scores are used to output the highest scoring candidates at any given level in the hierarchy. The topic transformation parameters in the discriminative topic transformation models can be shared among one or more subsets of the models, in order to promote generalization within the hierarchy.

[Brief Description of the Drawings]

[0021]

[Fig. l]

Fig. 1 is a flow diagram of a text classification method and system according to embodiments of the invention.

[Fig. 2]

Fig. 2 is a flow diagram of a hierarchical text classification method and system according to embodiments of the invention.

[Description of Embodiments]

[0022]

The embodiments of the invention provide a method for classifying text using discriminative topic transformation model. [0023]

The method extracts text features / j,k(x,y) from the text to be classified, where j is an index for a type of feature, k is an index of a class associated with the feature, x is the text, and y is a hypothesis of the class.

[0024]

The text features are transformed to topic features using gi,k ( ^x >y) = ^h i (h,k ( ^x > y)>-> fj,k ( ^x >y)l

where ¾ (.) is a function that transforms the text features, and / is an index of the topic features.

[0025]

The term "topic features" is used because the features are related to semantic aspects of the text. As used in the art and herein, "semantics" relate to the meaning of the text in a natural language as a whole. Semantics focuses on a relation between signifiers, such as words, phrases, signs and symbols, and what the signifiers denote. Semantics is distinguished from the "dictionary" meaning of the individual words.

[0026]

A linear tr nsform, hi (fi,k ( ^x >y) >

parameterized b a feature transformation matrix^, produces the topic features

[0027]

Then, our discriminative topic transformation model is

where

[0028]

We construct and optimize our model using training text. The model includes the set classification parameters A and and the feature transformation matrix A. The parameters maximize the scores of the correct class labels. The model is also used to evaluate the scores during classification. The construction can be done in a one time preprocessing step.

[0029]

The model parameters can also be regularized during optimization using various regularizers designed for the feature transformation matrix A, and the classification parameters Λ .

[0030]

One wa uses a mixture of regularizers on the classification parameters Λ , and a combined L1/L2 regularizer

on the feature transformation matrix A matrix, where a ,

β , and Y are weighting factors.

[0031]

Objective Function for Training Model Parameters

Then, the objective function for training model parameters Λ and A on training pairs of texts and labels y, is

where α, β, γ are the weights controlling a relative strength of each regularizer, which are determined using cross-validation. This objective function is to be maximized with respect to Λ and A.

[0032]

Scoring

Scores for each class y given text x can be computed using a similar formula as used in the objective function above, leaving out the constant terms:

[0033]

Hierarchical Classification

We now consider the case where the classes are organized in a hierarchical structure. For each text x, we now have labels y ^d ,d = 1,...,D for each level of the hierarchy. The label variable y ^d at each level d takes values in a set ^d .The set of considered values for

'( d 1 d 1 according to the values taken by the label variables y = y ,.··? ^ at previous levels.

[0034]

For example, in the case of a tree structure for the classes, each set

^ / can be defined as the set of children of the label at level d-1.

[0035]

For estimating the class at each level d, we can construct classifiers for the text that depend on the hypothesis of the classes at the previous levels d'≤ d - 1.

The score for class is computed usin the following formula:

Kd [ V.(d -1) )

where is the set of parameters for classes at level d given the classes at level 1 to d-1. Optionally, the matrix A can depend on the level d and

. Md -1)

previous levels' classes , but there may be advantages to having it shared across levels.

[0036]

In the case of a tree representation, one possibility is to simplify the above formula to

so that scoring only depends on the class of the previous level. [0037]

In this framework, inference can be performed by traversing the hierarchy, and combining scores across levels for combinations of hypotheses /

[0038]

Combining the scores across levels can be done in many ways. Here, we shall

In so

of y . In the case of conditional exponential models, this is given (up to an irrelevant constant) by

[0039]

In the case of a tree, we simply have s{ ^d \ x) = s[y ^d \ x) as there is only d

a single path that leads to y .

[0040]

The combined scores for different hypotheses are used to rank the hypotheses and determine the most likely classes at each level for the input text.

[0041]

Traversing the hierarchy can also be done in many ways, we traverse the hierarchy from the top in a breadth-first search strategy. In this context, we can speed up the process by eliminating from consideration hypotheses y ^{' }} up to level d-1 whose scores are too low. At level d, we now only have to consider hypotheses y ^ that include the top scoring y ^ ^ .

[0042]

The hierarchy can also be represented by a directed acyclic graph (DAG). The DAG has no cycles. An undirected graph can be converted into a DAG by choosing a total ordering of the nodes of the undirected graph, and orienting every edge between two nodes from the node earlier in the order to the node later in the order.

[0043]

Method

Fig. 1 shows a method for classifying text using discriminative topic transformation models according to embodiments of our invention.

[0044]

As described above, we construct 105 our model 103 from known labeled training text 104 during preprocessing.

[0045]

After the model is constructed, unknown unlabeled text can be classified.

[0046]

Input to the method is text 101, where the text includes glyphs, characters, symbols, words, phrases, or sentences. The text can be derived from speech.

[0047]

Output is a set of class labels 102 that most likely correspond to the unknown input text, i.e., class hypotheses.

[0048] Using the model, text features 111 are determined 110 from the input text 101. The text features are transformed 120 to topic features 121.

[0049]

Class scores are determined 130 according to the model 103. Then, the set of class labels 102 with the highest scores is produced.

[0050]

The steps of the above methods can be performed in a processor 100 connected to memory and input/output interfaces as known in the art.

[0051]

Fig. 2 shows a method for classifying text using the above method in the case where the classes are arranged in a tree-structured hierarchy.

[0052]

Parameters 202 are constructed according to the above method for performing classification at each level of the hierarchy. Scores for level 1 classes are evaluated 210 on unlabeled text 201 as above, producing scores for level 1 classes 203. One or more nodes in the next level 2 are then selected 220 based on the scores for level 1. Scores for selected nodes for level 2 are again evaluated 230 using the above method on unlabeled text 201, and are aggregated 204 with scores for the previous level.

[0053]

The same method is performed at each subsequent level of the hierarchy, beginning with selection 220 of nodes for the level i, evaluation 230 of scores at level i, and storage of the scores up to level i 204.

[0054]

After the scores up to the final level i = n have been aggregated, the scores are combined 240 across levels, and the set 205 of class labels for each level with the highest scores is produced. [0055]

Effect of the Invention

The invention provides an alternative to conventional text classification methods. Conventional methods can use features based on topic models. However, those features are not discriminatively trained within a framework of the classifier.

[0056]

The use of topic features allows parameters to be shared among all classes, which enables the model to determine relationships between words across the classes, in contrast to only within each class, as in conventional calssification models.

[0057]

The topic features also allow the parameters for each class to be used for all classes, which can reduce noise and over-fitting during the parameter estimation, and improve generalization.

[0058]

Relative to latent variable topic models, our model involves multiplication of the topic-specific and class-specific parameters in the log probability domain, whereas the prior art latent variable topic models involve addition in the log probability domain, which yields a different set of possible models.

[0059]

As another advantage, our method uses a multivariate logistic function with optimization that is less sensitive to the training texts points that are far from a decision boundary.

[0060]

The hierarchical operation of the classification combined with the discriminative topic transformations, enables the system to generalize well from training data by sharing parameters among classes. It also enables to back off to higher level classes if inference at lower levels cannot be performed with sufficient confidence.