ECML PKDD 2008

Incremental Exemplar Learning Schemes for Classification on Embedded Devices

Although memory-based classifiers offer robust classification performance, their widespread usage on embedded devices is usually hindered due to device's limited memory resources. Moreover, embedded devices often operate in an environment where data exhibits evolutionary changes which entails frequent update of the in-memory training data. A viable option for dealing with the memory constraint is to use Exemplar Learning (EL) schemes that learn a small meory set (called the exemplar set) of high functional information that fits in memory. However, traditional EL schemes have several drawbacks which make them inapplicable for the embedded devices; (1) they have high memory overheads and are unable to handle incremental updates to the exemplar set, (2) they are not customizable to obtain exemplar sets of any user-defined size that fits in the memory and (3) they learn exemplar sets based on local neighborhood structures that do not offer robust classification performance. In this paper, we propose two novel EL schemes, EBEL (Entropy-Based Exemplar Learning) and ABEL (AUC-Based Exemplar Learning) that overcome the aforementioned short-comings of traditional EL algorithms. We show that our incremental schemes can be efficiently updated with new training datasets while maintaining high quality exemplar sets of any user-defined size. We present a comprehensive experimental analysis showing excellent classification-accuracy versus memory-usage trade-offs using our proposed methods.