Passive-Aggressive Classifier for Embedded Devices

When working with memory-constrained devices, you may not able to keep all the training data in memory: passive-aggressive classifiers may help solve your memory problems.

Batch learning

A couple weeks ago, I started exploring the possibility of training a machine learning classifier directly on a microcontroller. Since I like SVM, I ported the simplified SVM SMO (Sequential Minimal Optimization) algorithm to plain C, ready to be deployed to embedded devices.

Now, that kind of algorithm works in the so-called "batch-mode." It needs all the training data to be available in memory to learn.

This may be a limiting factor on resource-constrained devices, since it poses an upper bound to the number of samples you can train on. And when working with high-dimensional datasets, the number of samples could be not enough to achieve good accuracy.

Enter incremental learning

To solve this limitation, you need a totally different kind of learning algorithms: you need incremental (a.k.a online a.k.a out of core) learning.

Incremental learning works by inspecting one training sample at a time, rather than all at once.

The clear advantage is that you have a tiny memory footprint, and this is a huge advantage.

The clear disadvantage is that you don't have the "big picture" of your data, so:

• the end result will probably be affected by the order of presentation of the samples.
• you may not be able to achieve top accuracy.

Passive-aggressive classifier

Passive-aggressive classification is one of the available incremental learning algorithms and it is very simple to implement, since it has a closed-form update rule.

Please refer to this short explanation on passive-aggressive classifiers for a nice description with images.

The core concept is that the classifier adjusts its weight vector for each misclassified training sample it receives, trying to correct it.

Benchmarks

I run a couple benchmarks on my ESP32 to assess both accuracy and training time.

First of all, it is fast!. When I say it is fast I mean it takes ~1ms to train on 400 samples x 30 features each.

Talking about accuracy instead... um...

Accuracy varies. Greatly.

You can achieve 100% on some datasets.

And 40% on others. But on those same datasets you can achieve >85% if training on a different number of samples, or in a different order.

I guess this is the trade-off for such a simple and space-efficient algorithm.

I report my results in the following table. It is not meant to be an exhaustive benchmark of the classifier, since those numbers will vary based on the order of presentation. But you can still get an idea of what it is able to achieve.

Time to code

Here, I'll report an extract of the example code that you can find on GitHub for this classifier.

#include <EloquentPassiveAggressiveClassifier.h>
#include <EloquentAccuracyScorer.h>
#include "iris.h"

using namespace Eloquent::ML;

void loop() {
    int trainSamples;
    PassiveAggressiveClassifier clf;
    AccuracyScorer scorer;

    trainSamples = readSerialNumber("How many samples will you use as training?", DATASET_SIZE - 2);

    if (trainSamples == 0)
        return;

    clf.setC(1);

    // train
    for (uint16_t i = 0; i < trainSamples; i++)
        clf.fitOne(X[i], y[i]);

    // predict
    for (uint16_t i = trainSamples; i < DATASET_SIZE; i++) {
        int predicted = clf.predict(X[i]);
        int actual = y[i] > 0 ? 1 : -1;

        scorer.scoreOne(actual, predicted);
    }

    Serial.print("Accuracy: ");
    Serial.print(round(100 * scorer.accuracy()));
    Serial.print("% out of ");
    Serial.print(scorer.support());
    Serial.println(" predictions");
}

You can find the code to reproduce these numbers on the project page.