Methods for multi-class cost-sensitive learning

Abstract

Methods for multi-class cost-sensitive learning are based on iterative example weighting schemes and solve multi-class cost-sensitive learning problems using a binary classification algorithm. One of the methods works by iteratively applying weighted sampling from an expanded data set, which is obtained by enhancing each example in the original data set with as many data points as there are possible labels for any single instance, using a weighting scheme which gives each labeled example the weight specified as the difference between the average cost on that instance by the averaged hypotheses from the iterations so far and the misclassification cost associated with the label in the labeled example in question. It then calls the component classification algorithm on a modified binary classification problem in which each example is itself already a labeled pair, and its (meta) label is 1 or 0 depending on whether the example weight in the above weighting scheme is positive or negative, respectively. It then finally outputs a classifier hypothesis which is the average of all the hypotheses output in the respective iterations.

1 . A method for multi-class, cost-sensitive learning based on iterative example weighting schemes applied to a chosen data set comprising the steps of: 
 a) obtaining an expanded data set, which is defined by enhancing each example in an original data set with as many data points as there are possible labels for any single instance;    b) repeatedly drawing sub-samples from the expanded data set using weighted sampling according to a certain example weighting scheme that remains constant throughout the iterations, in which each labeled example is given the weight specified as the difference between the maximum possible misclassification cost for the instance in question and the misclassification associated with the label in the particular labeled example;    c) calling a component classification learning algorithm to the sub-sample obtained in step b) and obtaining a hypothesis representing a classifier;    d) outputting all classifier representations obtained through the iterations and representing an average over them, each of which can be an arbitrary representation of classifier for a problem at hand; and    e) outputting all of the representations obtained through the iterations representing an average over them, each of which can be an arbitrary representation of classifier for the problem at hand.    
     
     
         2 . The method for multi-class, cost-sensitive learning recited in  claim 1 , wherein the learning algorithm is an arbitrary algorithm for classification.  
     
     
         3 . The method for multi-class, cost-sensitive learning recited in  claim 1 , wherein the learning algorithm is selected from the group consisting of decision tree algorithms, naïve Bayes method, logistic regression method and neural networks.  
     
     
         4 . A method for multi-class, cost-sensitive learning based on an example weighting scheme applied to a chosen data set comprising the steps of: 
 a) obtaining an expanded data set, which is defined by enhancing each example in an original data set with as many data points as there are possibles for any single instance;    b) iteratively applying weighted sampling from the expanded data set, using a dynamically changing weighting scheme involving both positive and negative weights;    c) calling a component classification algorithm on a modified binary classification problem in which each example is itself already a labeled pair, and its (meta) label is 1 or 0 depending on whether the example weight in the above weighting scheme is positive or negative, respectively, and obtains a hypothesis representing a classifier;    d) optionally modifying the obtained classifier, which is in general a relation on the original classification (mapping elements of domain to the labels, so that it is stochastic, namely a conditional probability distribution so that its probabilities over the set of labels sum to one for each instance;    e) outputting all representations obtained through the iterations and representing an average over them, each of which can be an arbitrary representation of classifier for the problem at hand.    
     
     
         5 . The method for multi-class, cost-sensitive learning recited in  claim 4 , wherein the learning algorithm is an arbitrary algorithm for classification.  
     
     
         6 . The method for multi-class, cost-sensitive learning recited in  claim 4 , wherein the learning algorithm is selected from the group consisting of decision tree algorithms, naïve Bayes method, logistic regression method and neural networks.  
     
     
         7 . The method for multi-class, cost-sensitive learning recited in  claim 4 , wherein the dynamically changing weighting of step b) gives each labeled example a weight specified as a difference between an average cost on that instance by the averaged hypotheses from iterations so far and a misclassification cost associated with the label in the labeled example in question  
     
     
         8 . The method for multi-class, cost-sensitive learning recited in  claim 4 , wherein the dynamically changing weighting of step b) gives each labeled example a weight specified as a difference between an average cost on that instance by an averaged hypotheses from iterations so far divided by a number of labels per instance, and a misclassification cost associated with the label in the labeled example in question.  
     
     
         9 . The method for multi-class, cost-sensitive learning recited in  claim 4 , wherein the dynamically changing weighting of step b) gives each labeled example a weight specified as a difference between an average cost on that instance by an averaged hypotheses from iterations so far divided by a number of labels per instance, and a misclassification cost associated with the label in the labeled example in question, and the weighted sampling comprises the steps of: 
 sampling the instance in step a) according to a probability proportional to a maximum of weights for that instance and any of the labels, and    choosing a label with a probability proportional to the absolute value of a weight for that instance and the label in question.    
     
     
         10 . The method for multi-class, cost-sensitive learning recited in  claim 4 , wherein the dynamically changing weighting of step b) gives each labeled example a weight specified as a difference between an average cost on that instance by an averaged hypotheses from iterations so far divided by a number of labels per instance, and a misclassification cost associated with the label in the labeled example in question, and the weighted sampling comprises the steps of: 
 sampling the instance step a) according to a probability proportional to a maximum of weights for that instance and any of the labels, and    for the chosen instance, deterministically added examples for all possible labels.    
     
     
         11 . A system implementing a method for multi-class, cost-sensitive learning based on iterative example weighting schemes applied to a chose data set comprising: 
 a multi-class cost-sensitive learning top control module controlling the overall control flow;    a learning algorithm storage module storing a representation of a learning algorithm for classification learning;    a model output module storing models obtained as a result of applying the learning algorithm to training data given by a weighted sampling module and outputting a final model by aggregating these models, said weighted sampling module accessing data stored in a data storage module, sampling a relatively small subset of the data with acceptance probability determined using the example weights, and passing the obtained sub-sample to said top control module;    a weight calculation module updating the example weights for sampling using weighted sampling according to a weighting scheme that remains constant throughout iterations, in which each labeled example is given a weight specified as a difference between a maximum possible misclassification cost for the instance in question and a misclassification cost associated with the label in the particular labeled example; and    a model update module updating current models using a model's output in previous iterations stored in a current model storage module and an output model of a current iteration output and storing a resulting updated model in said current storage module.    
     
     
         12 . The system for implementing a method for multi-class, cost-sensitive learning recited in  claim 11 , wherein the learning algorithm is an arbitrary algorithm for classification.  
     
     
         13 . The system for implementing a method for multi-class, cost-sensitive learning recited in  claim 11 , wherein the learning algorithm is selected from the group consisting of decision tree algorithms, naïve Bayes method, logistic regression method and neural networks.  
     
     
         14 . A system implementing a method for multi-class, cost-sensitive learning based on an example weighting scheme applied to a chosen data set comprising: 
 a multi-class cost-sensitive learning top control module controlling the overall control flow;    a learning algorithm storage module storing a representation of a learning algorithm for classification learning;    a model output module storing models obtained as a result of applying the learning algorithm to training data given by a weighted sampling module and outputting a final model by aggregating these models, said weighted sampling module accessing data stored in a data storage module, sampling a relatively small subset of the data with acceptance probability determined using the example weights, and passing the obtained sub-sample to said top control module;    a weight calculation module calculating the example weights for sampling using a dynamically changing weighting scheme involving both positive and negative weights; and    a model update module updating the current models using the models output in the previous iterations stored in a current model storage module and the output model of the current iteration output and storing the resulting updated model in said current storage module.    
     
     
         15 . The system for implementing a method for multi-class, cost-sensitive learning recited in  claim 14 , wherein the learning algorithm is an arbitrary algorithm for classification.  
     
     
         16 . The system for implementing a method for multi-class, cost-sensitive learning recited in  claim 14 , wherein the learning algorithm is selected from the group consisting of decision tree algorithms, naïve Bayes method, logistic regression method and neural networks.  
     
     
         17 . The system implementing a method for multi-class, cost-sensitive learning recited in  claim 14 , wherein the dynamically changing weighting scheme used by the weight calculation module gives each labeled example a weight specified as a difference between an average cost on that instance by the averaged hypotheses from iterations so far and a misclassification cost associated with the label in the labeled example in question  
     
     
         18 . The system implementing a method for multi-class, cost-sensitive learning recited in  claim 14 , wherein the dynamically changing weighting scheme used by the weight calculation module gives each labeled example a weight specified as a difference between an average cost on that instance by an averaged hypotheses from iterations so far divided by a number of labels per instance, and a misclassification cost associated with the label in the labeled example in question.  
     
     
         19 . The system implementing a method for multi-class, cost-sensitive learning recited in  claim 14 , wherein the dynamically changing weighting scheme used by the weight calculation module gives each labeled example a weight specified as a difference between an average cost on that instance by an averaged hypotheses from iterations so far divided by a number of labels per instance, and a misclassification cost associated with the label in the labeled example in question, and the weighted sampling samples the instance according to a probability proportional to a maximum of weights for that instance and any of the labels, and a label is chosen with a probability proportional to the absolute value of a weight for that instance and the label in question.  
     
     
         20 . The system implementing a method for multi-class, cost-sensitive learning recited in  claim 14 , wherein the dynamically changing weighting scheme used by the weight calculation module gives each labeled example a weight specified as a difference between an average cost on that instance by an averaged hypotheses from iterations so far divided by a number of labels per instance, and a misclassification cost associated with the label in the labeled example in question, and the weighted sampling samples the instance according to a probability proportional to a maximum of weights for that instance and any of the labels, and for the chosen instance, deterministically adds examples for all possible labels.