On-line Independent Support Vector Machines for Cognitive Systems

Francesco Orabona, Claudio Castellini, Barbara Caputo, Jie Luo, Giulio SandiniInfoscience 2007

Abstract

Artificial cognitive systems require the ability to learn from experience and adapt to changing environments in real-time. This necessitates on-line learning methods that balance high accuracy with limited computational resources. We present the On-line Independent Support Vector Machine (OISVM), a discriminative classifier designed for autonomous agents. By employing an active sparsification mechanism based on linear independence, OISVM maintains a bounded model size and constant testing time while converging to an optimal solution at each incremental step. We demonstrate the effectiveness of OISVM on standard benchmarks and two real-world applications: indoor robot localization and human grasping posture classification.

Introduction

The development of autonomous agents capable of long-term operation in dynamic environments is a central goal of cognitive robotics. While probabilistic frameworks have been widely used for navigation and imitation learning, recent research highlights the potential of discriminative classifiers like Support Vector Machines (SVMs). However, standard SVMs suffer from a "memory leak" in on-line settings: the number of support vectors typically grows with the amount of training data, leading to unbounded memory usage and increasing computational overhead. For a robot operating over months, this growth eventually compromises real-time performance.

The On-line Independent SVM (OISVM)

To address the scalability issues of traditional SVMs, we propose the On-line Independent SVM (OISVM). The algorithm is built upon two primary pillars:

1. Active Sparsification

OISVM maintains a compact model by ensuring that only "linearly independent" data points are stored in the feature space. When a new training sample arrives, the system evaluates whether it can be approximated by a linear combination of existing support vectors within a tolerance factor $\eta$. If the point is redundant, it is discarded; if it provides novel geometric information, it is added to the basis. This mechanism effectively bounds the complexity of the solution, ensuring that testing time remains constant regardless of the total number of training samples encountered.

2. Incremental Optimization

Unlike batch SVMs that require re-solving the entire optimization problem, OISVM updates its parameters ($\beta$ coefficients) instantly using a modified Newton method. This allows the model to reach an optimal solution at every incremental step, providing immediate adaptation to new stimuli without the need for infinite data to achieve convergence.

Experimental Validation

The OISVM was evaluated across three distinct domains to test its versatility and efficiency:

  • Benchmark Datasets: Performance was assessed on 11 standard datasets (e.g., Diabetes, Adult7, Waveform). OISVM consistently achieved accuracy comparable to batch SVMs while using significantly fewer support vectors.
  • Robot Localization (IDOL2): Using the Image Database for rObot Localization 2, we tested the algorithm's ability to recognize five different rooms over a six-month period under varying lighting and weather conditions.
  • Human Grasping Posture: We utilized a dataset of hand joint angles captured via a 22-sensor CyberGlove. The task involved classifying five distinct grasp types across multiple subjects, testing the system's ability to generalize across different physiological styles in real-time.

Key Results and Discussion

The experimental results underscore the efficiency of the OISVM approach:

  • Model Compression: On the Adult7 dataset, OISVM utilized only 2% of the support vectors required by a standard SVM while maintaining nearly identical accuracy. In the IDOL2 navigation task, model size was reduced to 18-34% of standard incremental methods.
  • Real-time Viability: The bounded number of support vectors ensures that classification remains fast enough for interactive applications, such as real-time gesture recognition and robot navigation.
  • Parameter Control: The tolerance parameter $\eta$ provides a direct "knob" for trading off a marginal amount of accuracy for significant gains in memory and speed, allowing developers to tune the system for specific hardware constraints.

Conclusion and Future Work

OISVM provides a robust framework for continuous learning in resource-constrained cognitive systems. By focusing on the linear independence of data, it achieves a superior trade-off between accuracy and compactness. Future research will focus on implementing formal "forgetting" mechanisms to handle non-stationary environments where old data may become obsolete, as well as extending the framework to multi-modal sensor fusion and semi-supervised learning scenarios.

Summary updated

Abstract

Learning from experience and adapting to changing stimuli are fundamental capabilities for artificial cognitive systems. This calls for on-line learning methods able to achieve high accuracy while at the same time using limited computer power. Research on autonomous agents has been actively investigating these issues, mostly using probabilistic frameworks and within the context of navigation and learning by imitation. Still, recent results on robot localization have clearly pointed out the potential of discriminative classifiers for cognitive systems. In this paper we follow this approach and propose an on-line version of the Support Vector Machine (SVM) algorithm. Our method, that we call On-line Independent SVM, builds a solution on-line, achieving an excellent accuracy vs.~compactness trade-off. In particular the size of the obtained solution is always bounded, implying a bounded testing time. At the same time, the algorithm converges to the optimal solution at each incremental step, as opposed to similar approaches where optimality is achieved in the limit of infinite number of training data. These statements are supported by experiments on standard benchmark databases as well as on two real-world applications, namely $(a)$ place recognition by a mobile robot in an indoor environment, and $(b)$ human grasping posture classification.
BibTeX
@inproceedings{orabona2007line,
  author = {Francesco Orabona and Claudio Castellini and Barbara Caputo and Jie Luo and Giulio Sandini},
  title = {{On-line Independent Support Vector Machines for Cognitive Systems}},
  booktitle = {Infoscience},
  year = {2007},
}
Figure