Text categorizers based on regularizing adaptations of the problem of computing linear separators

A method of supervised learning for the purpose of text categorization, said method comprising the steps of:

• selecting values for parameters which determine an empirical loss function Ff,g,s(D,w), of the form F ⁡ ( D , w ) = F f , g , s ⁡ ( D , w ) = 1 n ⁢ ∑ i = 1 n ⁢ ⁢ f mod ⁡ ( w T ⁢ x i ⁢ y i ) + sg ⁡ ( w ) ,
• thereby modifying by approximation a training error function for a set of n categorized training documents and then regularizing the function thereby approximated to create a regularized convex optimization problem, wherein the training error function to be thereby approximated is defined by 1 n ⁢ ∑ i = 1 n ⁢ ⁢ f ⁡ ( w T ⁢ x i ⁢ y i ) ,
• where f is a step function f ⁡ ( x ) = { 1 if ⁢ ⁢ x ≤ 0 , 0 if ⁢ ⁢ x > 0
• w is a weight vector, D is a set {xi, yi} of vectors derived from categorized training documents such that x, is a vector derived from an ith training document, yiε{+1, −1} is a label designating whether or not the ith document is in a particular category C, wTx is a dot product of w and x, and wherein the training error function thereby modified by approximation for a set of n training documents is defined by 1 n ⁢ ∑ i = 1 n ⁢ ⁢ f mod ⁡ ( w T ⁢ x i ⁢ y i ) ,
• where fmod is a convex approximation of the step function f, and wherein fmod is regularized by the addition of a convex term g, g being a smooth function expressible as a sum of real-valued functions, each real-valued function being a function of exactly one component of the weight vector w, and s is a small positive real, number establishing a balance in the resulting optimization problem between minimizing an error rate on the training data and ensuring weights are not too large;
• assembling a set of tokenized representations of a set of training documents with a list L of selected features for the set of training documents for a selected category;
• creating a set D of numerical vector representations of the set of training documents using the list L of selected features;
• determining a weight vector w that minimizes F(D,w) by using a relaxation algorithm that takes the set D as input, and
• providing the determined weight vector w by optimizing components of weight vector w one component at a time.

A method for predicting whether a document is a member of a category using a weight vector w, a threshold t, and a set L of selected features that were used in the determination of w, said method comprising the steps of:

• inputting a document d;
• creating a tokenized representation r for document d;
• creating a a vector x which represents d by using r and the selected features L;
• determining whether for a rule defined as an inner product of w and x being greater than or equal to t, and if so, assigning d to the category corresponding to this rule, but if not, refraining from assigning d to the category corresponding to this rule,
• wherein w is determined by:
• modifying a training error function for a set of n categorized training documents, wherein the training error function to be modified is defined by 1 n ⁢ ∑ i = 1 n ⁢ ⁢ f ⁡ ( w T ⁢ x i ⁢ y i ) ,
• where f is a step function f ⁡ ( x ) = { 1 if ⁢ ⁢ x ≤ 0 , 0 if ⁢ ⁢ x > 0
• w is a weight vector, xi is a vector derived from an ith training document, yiε{+1, −1} is a label designating whether or not the ith document is in a particular category C, wTx is a dot product of w and xi and wherein the modified training error function for a set of n training documents is defined by 1 n ⁢ ∑ i = 1 n ⁢ ⁢ f mod ⁡ ( w T ⁢ x i ⁢ y i ) ,
• where fmod is a convex approximation of the step function f;
• deriving a convex optimization problem from the modified training error function by finding a value of weight vector w that minimizes the modified training error function;
• regularizing the convex optimization problem by adding a convex term, said convex term being dependent only on weight vector w;
• solving the problem by relaxation, thereby obtaining a weight vector w that minimizes the modified training error by optimizing components of weight vector w one component at a time.

A system of supervised learning for the purpose of text categorization, comprising:

• a computing device having memory and means for processing;
• means for inputting a set of training documents;
• means for modifying a training error for a set of categorized training documents by expressing the training error as a function which describes an ill-posed problem and replacing the ill-posed problem function with a convex function which approximates the ill-posed problem function;
• means for deriving a convex optimization problem from the modified training error function by finding a weight vector w whose dot product with vectors derived from the training documents minimizes the modified training error function;
• means for regularizing the convex optimization problem by adding a convex term, said convex term being dependent only on weight vector w;
• and
• computer code in said memory implementing the step of solving the problem by relaxation, wherein components of the weight vector w are optimized one at a time, the solution to the problem being available for further processing using processing means in order to categorize text.

A system for predicting whether a document is a member of a category using a weight vector w, a threshold t, and a set L of selected features that were used in the determination of w, comprising:

• a computing device having memory and means for processing;
• means for inputting documents;
• means for modifying a training error for a set of categorized training documents by expressing the training error as a function which describes an ill-posed problem and replacing the ill-posed problem function with a convex function which approximates the ill-posed problem function;
• means for deriving a convex optimization problem from the modified training error function by finding a weight vector w whose dot product with vectors derived from the training documents minimizes the modified training error function;
• means for regularizing the convex optimization problem by adding a convex term, said convex term being dependent only on weight vector w;
• ad
• a first computer code section in said memory implementing the step of solving the convex optimization problem by relaxation, wherein components of the weight vector w are optimized one at a time, the solution to the problem being available for further processing using processing means in order to categorize text;
• a second computer code section in said memory implementing the step of inputting a document d;
• a third computer code section in said memory implementing the step of creating a tokenized representation r for document d;
• a fourth computer code section in said memory implementing the step of creating a a vector x which represents d by using r and the selected features L;
• and
• a fifth computer code section in said memory implementing the step of determining whether for a rule defined as an inner product of w and x being greater than or equal to t, and if so, assigning d to the category corresponding to this rule, but if not, refraining from assigning d to the category corresponding to this rule,
• wherein w is determined by processing the first code section in said memory to solve the problem by relaxation.