P-N learning: Bootstrapping binary classifiers by structural constraints

TLDR

Structured data are defined by the property that knowing the label of one example restricts the labeling of the others. The authors introduce P‑N learning, a paradigm that trains a binary classifier using both labeled and unlabeled data guided by a theory of positive and negative structural constraints. P‑N learning iteratively evaluates the classifier on unlabeled data, identifies contradictions with the constraints, corrects the labels, and augments the training set, and it is applied to online learning of object detectors during tracking. The method yields significant performance gains, enabling accurate object detectors to be learned from a single labeled example and an unlabeled video, and it outperforms related approaches on faces, pedestrians, cars, motorbikes, and animals.

Abstract

This paper shows that the performance of a binary classifier can be significantly improved by the processing of structured unlabeled data, i.e. data are structured if knowing the label of one example restricts the labeling of the others. We propose a novel paradigm for training a binary classifier from labeled and unlabeled examples that we call P-N learning. The learning process is guided by positive (P) and negative (N) constraints which restrict the labeling of the unlabeled set. P-N learning evaluates the classifier on the unlabeled data, identifies examples that have been classified in contradiction with structural constraints and augments the training set with the corrected samples in an iterative process. We propose a theory that formulates the conditions under which P-N learning guarantees improvement of the initial classifier and validate it on synthetic and real data. P-N learning is applied to the problem of on-line learning of object detector during tracking. We show that an accurate object detector can be learned from a single example and an unlabeled video sequence where the object may occur. The algorithm is compared with related approaches and state-of-the-art is achieved on a variety of objects (faces, pedestrians, cars, motorbikes and animals).