P-N Learning: Bootstrapping Binary Classifiers by Structural Constraints

Zdenek Kalal (University of Surrey, Guildford, UK)
Joint work with K. Mikolajczyk and J. Matas

A novel paradigm for training a binary classifier from labeled and unlabeled examples that we call P-N learning will be introduced. The learning process is guided by positive (P) and negative (N) constraints which restrict the label- ing of the unlabeled set. P-N learning evaluates the clas- sifier 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.

A theory is proposed 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 the performance of a binary clas- sifier can be significantly improved by the processing of structured unlabeled data, i.e. data are structured if know- ing the label of one example restricts the labeling of the others. 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).