Computer-implemented method for performing hierarchical classification
Inventors
Beskales, George • Kraemer, John • Ilyas, Ihab F. • Cleary, Liam • Roome, Paul
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-10803105-B1
Publication Date
2020-10-13
Expiration Date
Abstract
Given a number of records and a number of target classes to which these records belong to, a (weakly) supervised machine learning classification method leverages known possibly dirty classification rules, efficiently and accurately learns a classification model from training data, and applies the learned model to the data records to predict their classes.
Core Innovation
The invention relates to a weakly supervised, scalable hierarchical classification system for millions of records and hundreds of thousands of classes. It uses record deduplication or clustering to consolidate records, thereby reducing the number of records that are processed for hierarchical classification. The system then identifies a subset of hierarchical classes as candidate hierarchical classes for each unlabeled record, to prune the search space.
For modeling, the system trains a plurality of binary classifiers for a hierarchy of classes. Positive examples are obtained from the class and descendants, while negatives are obtained from sibling and descendant-of-sibling sets. Hierarchical classes are predicted using conditional probability Pr(R∈C|R∈parent(C)) together with a chain rule and probability normalization, which are then combined with a scoring function and a search algorithm.
A top-scoring hierarchical classification is obtained for each unlabeled record using a search algorithm over a class hierarchy or directed acyclic graph (DAG). The system includes targeted active learning that selects high-entropy and high-impact records for human labeling. The approach also covers rule-based weak supervision by applying existing classification rules to generate labeled data, using down-sampling or weights for imbalance and deferring conflicts to human experts.
Claims Coverage
Independent claim clm-00001 covers a computer-implemented method for hierarchical classification that combines consolidated records, per-record candidate class restriction, multiple binary classifiers, scoring, and a search algorithm to obtain a top-scoring hierarchical classification for each unlabeled record. The claim includes five inventive features.
Hierarchical classification model with plurality of binary classifiers
Building, by the software, a classification model from the training data records configured to predict a hierarchical class of an unlabeled record, the classification model including a plurality of binary classifiers, each binary classifier configured to predict whether an unlabeled record belongs to a certain hierarchical class.
Consolidating unlabeled records through deduplication or clustering
Consolidating, by the software, the unlabeled records through deduplication or clustering, and performing steps (e)-(h) on the consolidated records.
Candidate hierarchical class selection for each unlabeled record
Identifying, by the software, a subset of the hierarchical classes as being candidate hierarchical classes for each of the unlabeled records.
Scoring and top-scoring hierarchical classification via search algorithm
Scoring, by the software, using a scoring function, each of the predicted hierarchical classifications of the unlabeled records; obtaining, by the software, using a search algorithm, a top-scoring predicted hierarchical classification of each unlabeled record; and outputting, by the software, the top-scoring predicted hierarchical classification as the predicted classification for each of the unlabeled records.
Prediction restricted to candidate hierarchical classes
Predicting the hierarchical classifications for each record in the unlabeled records, by the software, using only the candidate hierarchical classes for each of the unlabeled records.
The independent claim centers on a hierarchical classification method that trains a hierarchy-aware model using multiple binary classifiers, consolidates unlabeled records via deduplication or clustering, selects candidate hierarchical classes per record, predicts hierarchical classifications, scores them, and uses a search algorithm to obtain a top-scoring hierarchical classification while restricting prediction to only the candidate classes for each record.
Stated Advantages
Scalable hierarchical classification for millions of records and hundreds of thousands of classes.
Prunes the search space by using only candidate hierarchical classes for each unlabeled record.
Uses targeted active learning by selecting high-entropy and high-impact records for human labeling.
Supports weak supervision by applying existing classification rules and deferring conflicts to human experts.
Documented Applications
Performs hierarchical classification of large datasets with millions of records and hundreds of thousands of classes.
Supports weak supervision using existing classification rules with down-sampling or weights for imbalance and conflicts deferred to human experts.
Uses active learning to select high-entropy/high-impact records for human labeling.
Interested in licensing this patent?