Incremental Semi-Supervised Learning from Streams for Object Classification

The Label Propagation (LP) algorithm, first introduced by Zhu and Ghahramani [1], is a semi-supervised method used in transductive learning scenarios, where all data are available already in the beginning. In this work, we present a novel extension of the LP algorithm for applications where data samples are observed sequentially - as is the case in autonomous driving. Specifically, our “Incremental Label Propagation” algorithm efficiently approximates the so called harmonic solution on a nearest-neighbor graph that is regularly updated by new labeled and unlabeled nodes. We achieve this by reformulating the original algorithm based on an active set of nodes and by introducing a threshold to decide whether the label of a given node should be updated or not. Our method can also deal with graphs that are not fully connected, and we give a formal convergence proof for this general case. In experiments on the challenging KITTI benchmark data stream, we show superior performance in terms of both test accuracy and number of required training labels compared to state-of-the-art online learning methods.

Authors

• Ioannis Chiotellis
• Franziska Zimmermann
• Daniel Cremers
• Rudolph Triebel

Keywords

• Harmonic analysis
• Convergence
• Approximation algorithms
• Semisupervised learning
• Benchmark testing
• Training data
• Clustering algorithms
• Object Classification
• Semi-supervised Learning
• Data Streams
• Semi-supervised Methods
• Label Propagation
• Nearest Neighbor Graph
• Online Learning Methods
• Label Propagation Algorithm
• Edge Weights
• Cluster Centers
• Nodes In The Graph
• Convergence Of Algorithm
• Test Error
• Large Graphs
• Label Vector
• Label Matrix
• Utilization Of Samples