Scalable feature selection for multi-class problems
AssigneeXerox Corporation
InventorsBoris Chidlovskii, Loic Lecerf
Life of this patent
Estimating the term…
Abstract
In a feature filtering approach, a set of relevant features and a set of training objects classified respective to a set of classes are provided. A candidate feature and a second feature are selected from the set of relevant features. An approximate Markov blanket criterion is computed that is indicative of whether the candidate feature is redundant in view of the second feature. The approximate Markov blanket criterion includes at least one dependency on less than the entire set of classes. An optimized set of relevant features is defined, consisting of a sub-set of the set of relevant features from which features indicated as redundant by the selecting and computing are removed.
Claims21
A method including filtering a set of features to remove selected features that are substantially redundant respective to relating a set of classes and a set of training objects classified respective to the set of classes, the feature filtering method comprising:
- selecting a candidate feature of the feature set;
- measuring redundancy of the candidate feature respective to a second feature based on comparison of an estimated uncertainty reduction respective to the set of training objects provided by the candidate feature and provided by the second feature, the estimated uncertainty reductions being further respective at least in part to a sub-set of the classes that is smaller than the set of classes;
- filtering out the candidate feature if the redundancy satisfies a filtering criterion;
- and
- repeating the selecting, measuring, and filtering for a plurality of pairs of candidate and second features to generate a filtered set of features.
A storage medium storing instructions executable to perform a feature filtering method comprising (i) providing a set of relevant features and a set of training objects classified respective to a set of classes, (ii) selecting from the set of relevant features a candidate feature and a second feature, (iii) computing an approximate Markov blanket criterion indicative of whether the candidate feature is redundant in view of the second feature, the approximate Markov blanket criterion including at least one dependency on less than the entire set of classes, and (iv) defining an optimized set of relevant features consisting of a sub-set of the set of relevant features from which features indicated as redundant by the selecting and computing are removed.
A classifier trainer comprising a processor configured to perform a method comprising:
- training a classifier to classify an object respective to a set of classes, the training employing a set of pre-classified training objects and an optimized set of relevant features;
- selecting the optimized set of relevant features from a set of relevant features using an approximate Markov blanket criterion that includes at least one dependency on less than the entire set of classes;
- and
- selecting the set of relevant features from a set of features based on relevance of the features to the classifications of the set of pre-classified training objects.
Dependencies are inferred from the claim text.