CoBoost is a semi-supervised training algorithm proposed by Collins and Singer in 1999.
[1] The original application for the algorithm was the task of named-entity recognition using very weak learners, but it can be used for performing semi-supervised learning in cases where data features may be redundant.
Each example is available in two views (subsections of the feature set), and boosting is applied iteratively in alternation with each view using predicted labels produced in the alternate view on the previous iteration.
CoBoosting is not a valid boosting algorithm in the PAC learning sense.
CoBoosting was an attempt by Collins and Singer to improve on previous attempts to leverage redundancy in features for training classifiers in a semi-supervised fashion.
CoTraining, a seminal work by Blum and Mitchell, was shown to be a powerful framework for learning classifiers given a small number of seed examples by iteratively inducing rules in a decision list.
CoBoosting accomplishes this feat by borrowing concepts from AdaBoost.
In both CoTrain and CoBoost the training and testing example sets must follow two properties.
The first is that the feature space of the examples can separated into two feature spaces (or views) such that each view is sufficiently expressive for classification.
While ideal, this constraint is in fact too strong due to noise and other factors, and both algorithms instead seek to maximize the agreement between the two functions.
The second property is that the two views must not be highly correlated.
that minimizes expanded training error.
that minimizes expanded training error.
Update the value for current strong non-thresholded classifier:
CoBoosting builds on the AdaBoost algorithm, which gives CoBoosting its generalization ability since AdaBoost can be used in conjunction with many other learning algorithms.
In the AdaBoost framework, weak classifiers are generated in series as well as a distribution over examples in the training set.
(See AdaBoost Wikipedia page for notation).
In the AdaBoost framework Schapire and Singer have shown that the training error is bounded by the following equation:
is the feature selected in the current weak hypothesis.
Three equations are defined describing the sum of the distributions for in which the current hypothesis has selected either correct or incorrect label.
Schapire and Singer have shown that the value
can be minimized (and thus the training error) by selecting
Providing confidence values for the current hypothesized classifier based on the number of correctly classified vs. the number of incorrectly classified examples weighted by the distribution over examples.
The training error thus is minimized by selecting the weak hypothesis at every iteration that minimizes the previous equation.
CoBoosting extends this framework in the case where one has a labeled training set (examples from
), as well as satisfy the conditions of redundancy in features in the form of
The algorithm trains two classifiers in the same fashion as AdaBoost that agree on the labeled training sets correct labels and maximizes the agreement between the two classifiers on the unlabeled training set.
The bounded training error on CoBoost is extended as follows, where
is the summation of hypotheses weight by their confidence values for the
iteration we can set the pseudo-labels for the jth update to be: