Source-linked AI summary
Online semi-supervised perception: Real-time learning without explicit feedback
Branislav Kveton, Michal Valko, Matthai Phillipose, Ling Huang
TL;DR
Online learners rarely observe true labels, making adaptation to changing environments dependent on indirect feedback. The paper tracks a data-adjacency graph using harmonic predictions, with offline labeled examples and online unlabeled data; on V1 and V2, the learner achieves 95 percent precision at 90 percent recall.
Problem
Online learning rarely observes true labels, while adapting to environmental change requires indirect feedback; labeled examples are also limited relative to abundant data.
Source: §1 · p. 1Method
The method tracks a data-adjacency graph and infers unlabeled labels with its harmonic-function solution, updating offline labeled bias with online unlabeled examples.
Source: §1 · p. 1Results
On both V1 and V2, the learner achieves 95 percent precision at 90 percent recall.
Source: §4.2 · p. 5Takeaways & Limitations
Tracking the data manifold allows the method to adapt to changing data over time.
Source: §1 · p. 1The paper assumes binary labels for simplicity, while stating that its ideas generalize to multiclass classification.
Source: §2.1 · p. 2
Abstract
from arXiv · showhide
This paper proposes an algorithm for real-time learning without explicit feedback. The algorithm combines the ideas of semi-supervised learning on graphs and online learning. In particular, it iteratively builds a graphical representation of its world and updates it with observed examples. Labeled examples constitute the initial bias of the algorithm and are provided offline, and a stream of unlabeled examples is collected online to update this bias. We motivate the algorithm, discuss how to implement it efficiently, prove a regret bound on the quality of its solutions, and apply it to the problem of real-time face recognition. Our recognizer runs in real time, and achieves superior precision and recall on 3 challenging video datasets.
1. Introduction
The paper addresses online semi-supervised learning when true labels are rarely observed, using the data manifold to provide indirect feedback. It tracks a data-adjacency graph to infer labels and adapt over time, with offline labeled examples and online unlabeled data.
1. Introduction
- Semi-supervised learning combines labeled and unlabeled examples, a setting motivated by abundant data and limited labeling resources.The introduction identifies the harmonic function on a data-adjacency graph as a popular method for inferring unlabeled examples.Source: §1 · p. 1
- Because true labels are rarely observed during the online game, adapting to environmental change requires indirect feedback such as the data manifold.At each step, the learner observes an example and predicts its label, but rarely sees the true label.Source: §1 · p. 1
- The learner tracks the data-adjacency graph and uses its harmonic-function solution to infer unlabeled labels, retaining a random-walk interpretation and adapting to changing data.The authors also state that this approach generalizes beyond binary classification and is robust to outliers.Source: §1 · p. 1
- Labeled examples provide the initial bias offline, while a stream of unlabeled examples is collected online to update it.The paper describes this as a paradigm for adaptive machine-learning algorithms and notes little prior work on the topic.Source: §1 · p. 1
- The paper demonstrates the approach through adaptive face recognition, aiming to show the value of unlabeled data rather than compare recognizers.The objective is to build a high-quality recognizer from streams of unlabeled data and a small set of labeled faces.Source: §1 · p. 1
2. Semi-supervised face recognition
The section presents graph-based semi-supervised face recognition: harmonic predictions on a similarity graph assign identities, while regularization controls extrapolation to unlabeled faces. It describes the random-walk interpretation and a simple image-distance measure that corrects for lighting.
2.1. Harmonic function solution
- Adding γ_gI to the graph Laplacian controls extrapolation to unlabeled examples by reducing labeling confidence with distance from labeled vertices.The regularized random walk may terminate at an extra sink with probability γ_g/(d_i + γ_g); γ_g = 0 recovers the ordinary harmonic solution, while γ_g = ∞ drives unlabeled confidence to zero.Source: §2.1 · p. 2
2. Semi-supervised face recognition
- The harmonic function solution on a face-similarity graph yields face identities, and its predictions can be interpreted through random walks that terminate at labeled vertices.Prediction magnitude represents confidence, with values nearer zero corresponding to more uncertain labels; the paper assumes binary labels for simplicity and says the ideas generalize to multiclass classification.Source: §2.2 · p. 2, §2.1 · p. 2
2.2. Face recognition
- Face recognition is represented by a graph whose vertices are faces, whose edge weights encode face similarity, and whose harmonic solution predicts identity.The similarity uses a heat parameter and feature-space distance; the paper says its simple distance corrects for additive and multiplicative lighting and yields extremely good results in its experiments.Source: §2.2 · p. 2
- Thresholding similarities below ε makes the face graph sparse; disconnected faces receive prediction zero and may be treated as outliers or left unlabeled.The experiments vary ε and set γ_g = 10ε.Source: §2.2 · pp. 2–3
3. Online harmonic function solution
The online method avoids rebuilding a growing full graph by maintaining a compact quantized graph. Its quantization updates bound approximation distance, while the analysis bounds regret under sufficient regularization.
3.1. Quantization
- Collapsing identical vertices preserves the harmonic solution through a multiplicity-weighted graph, with merged vertices’ sinks summed in the closed-form solution.The compact graph is formed as ˆW = V W V.Source: §3.1 · p. 3
- Maintaining a graph with at most ng representative vertices makes the harmonic-function computation O(ng^3), independent of time t, instead of the naive O(t^3) approach.The graph is updated incrementally using the doubling algorithm.Source: §3.1 · p. 3, §3 · p. 3
- The doubling updates keep every example within 2R of its representative while maintaining the representative set’s separation and enforcing the ng cap.When the set exceeds ng, R is doubled and the representatives are greedily repartitioned.Source: §3.1 · pp. 3–4
3.2. Theoretical analysis
- With sufficient regularization, the learner’s per-step regret decreases over time.The supplied passage states a rate but its exponent is incomplete.Source: §3.2 · p. 4
3.3. Outliers
- To handle outliers, the learner withholds predictions when the harmonic score is zero and excludes those examples from representative updates.The passage describes this as representing all outliers by one vertex with zero impact on the harmonic solution.Source: §3.3 · p. 5
4. Experiments
The experiments evaluate online face recognition with a small labeled set and unlabeled video streams, varying neighborhood radius and graph size. The learner achieves strong precision and recall, adapts to changing conditions, and trades graph size against recall and computation time.
4.1. Datasets
- V1 and V2 feature eight people filmed by two cameras, while VO follows one participant across locations and adds other people to test false positives.Only four initial frontal faces are labeled for each person in V1 and V2; only the participant’s first four faces are labeled in VO.Source: §4.1 · p. 5
4.2. Face recognition
- On V1 and V2, the learner reaches 95 percent precision at 90 percent recall; at matched recall, its precision is typically 10 percent higher than nearest-neighbor classification.The 95/90 operating point uses ε = 10−8.Source: §4.2 · pp. 5–6
4.3. Sudden changes in the environment
- On VO, the learner achieves 100 percent precision and 95 percent recall while adapting to location and lighting changes, despite half the dataset containing other people.The authors conclude it adapts without extrapolating too far to outliers.Source: §4.3 · p. 6
- Online semi-supervised boosting matches the learner with suitable weak learners, but degrades significantly when those learners cover only part of VO.The learner updates its representation of the world, whereas incorporating a similar step into boosting is not obvious.Source: §4.3 · p. 6
4.4. Size of data adjacency graphs
- With ε fixed at 10−5, increasing graph size improves recall, mostly through tracking the first 200 representative vertices, while computation time grows superlinearly with ng.The harmonic-function computation takes O(ng^3) time steps.Source: §4.4 · p. 6, Figure 5 · p. 6
- At ng = 500, the recognizer processes about 7 frames per second on average.The authors characterize the recognizer as running in real time.Source: §4.4 · p. 6, Figure 5 · p. 6
5. Existing work
The section compares the learner with online semi-supervised methods and face-recognition systems, emphasizing differences in model complexity and adaptation.
5.1. Online semi-supervised learning
- Online learning from partially labeled data had received little attention, with online semi-supervised boosting and online manifold-regularized SVMs identified as notable examples.The section frames its comparisons against these two approaches.Source: §5.1 · p. 6
- Online manifold regularization of SVMs uses the data adjacency graph to regularize max-margin classifiers, but this method has fewer parameters, bounded solution quality, and supports multiclass classification and outlier robustness.With suitable parameterization, the SVM approach may produce the same result, but it learns an additional decision boundary over the graph.Source: §5.1 · p. 6
- Online semi-supervised boosting greedily labels unlabeled examples but relies on a predefined set of weak learners, which may be unknown in advance.In contrast, the paper's learner tracks the data manifold and can discover and adapt to nonlinear patterns in real time.Source: §5.1 · p. 6
5.2. Face recognition
- Prior video face-recognition work focused on improved features and temporal models, whereas this method uses a graph built over video data and is orthogonal to feature design.It learns with little human feedback, but without modeling the environment it must be careful when generalizing to new data points.Source: §5.2 · pp. 6–7
6. Conclusions
The conclusion presents online semi-supervised learning as a framework for adaptive algorithms and illustrates it with face recognition. Future work targets additional domains, richer features, and faster graph-based learning.
6. Conclusions
- The proposed online semi-supervised learner builds and updates a graphical representation from unlabeled examples, and the paper illustrates the framework with a highly accurate face recognizer using simple features.The authors describe the framework as useful for designing adaptive learning algorithms.Source: §6 · p. 7
- Future work includes applying the learner to domains such as object recognition and enhancing face recognition with features such as Haar-like features.These are proposed directions, not evaluated results in the conclusion.Source: §6 · p. 7
- A further goal is to develop online graph-based learning algorithms that are significantly faster than the harmonic function solution.Source: §6 · p. 7