If you thought machine learning on mobile is already a bit of a stretch, how about machine learning on microcontrollers?<\/p>\n
Take the Arduino Uno<\/a>. This has an 8-bit CPU running at 16 MHz, no real floating point support \u2014 it does not even have a division instruction \u2014 and only has 2KB of RAM. Is it even possible to do machine learning on these devices?<\/p>\n The answer is yes<\/strong>, but you need to be smart about the algorithm you\u2019re using.<\/p>\n A simple neural network<\/a> might work but a full-blown convnet will be way too slow without specialized hardware. My interest is in smart algorithms such as Bonsai<\/a> or SEFR, the topic of today\u2019s blog post.<\/p>\n SEFR, which stands for Scalable, Efficient, and Fast classifieR<\/strong>, was first published last year in a paper<\/a> from three Iranian researchers. Just for fun, I implemented the algorithm in Swift so we can run it on iOS or Mac devices.<\/p>\n You can find the source code for this blog post<\/a> on GitHub, as usual.<\/p>\n The paper is a quick read, so definitely give that a go if you\u2019re interested in reading papers. As is usual for these kinds of papers, the algorithm is described using math. As a programmer, I find algorithms easier to understand when they\u2019re expressed in (pseudo)code. Fortunately, the SEFR algorithm is very straightforward.<\/p>\n SEFR is a binary classifier<\/strong>, meaning it can tell apart two classes: the positive class and the negative class. Usually the positive class is the thing you\u2019re looking for, and the negative class is the absence of that thing.<\/p>\n Binary classification is certainly important, but many interesting classification tasks involve multiple classes. You can extend SEFR to do multiclass classification as well, basically by running it multiple times. I\u2019ll show how to do this later on.<\/p>\n Since SEFR is a supervised learning<\/strong> algorithm, you\u2019ll need to train it on a set of examples and their labels. The labels are 0 or 1, for the negative class and positive class, respectively. The examples themselves consist of numerical data.<\/p>\n To illustrate this, here is a portion of a possible dataset:<\/p>\n Here, each example uses four features<\/strong>. In other words, each example is made up of four floating-point numbers.<\/p>\n Usually The training set does not have to be randomly shuffled.<\/p>\n Note:<\/strong> The paper says that the feature data must always be non-negative, i.e. The key idea in SEFR is that we want to determine for each feature whether it helps to identify positive examples, or whether it helps to identify negative examples.<\/p>\n During training, SEFR computes a weight<\/strong> value for each feature. If the training data has M features per example, then SEFR learns M weights in total.<\/p>\n The weight is just a number that tells us how much an individual feature \u201cpulls\u201d the example towards the positive class (the weight is close to +1), or how much it pulls the example towards the negative class (the weight is close to -1).<\/p>\n If the weight is close to 0, the feature isn\u2019t very useful to the classification process and can be considered irrelevant.<\/p>\n That\u2019s basically all there is to it. Let\u2019s look at how to compute these weights.<\/p>\n Since SEFR is a really simple algorithm, I will describe it by stepping through the source code. You can follow along with the full version<\/a>.<\/p>\n First, we need to define the parameters that SEFR will learn. I already mentioned the weights, but it also learns a bias<\/strong> value. This bias will determine the decision boundary between the two classes. More about this later. There will be M weights \u2014 one for each feature \u2014 but there is only a single bias.<\/p>\n To train the model, we define the function Recall that First, we will count how many<\/strong> positive examples and how many negative examples there are in the training data. If the label for an example is 1, the example belongs to the positive class. If the label is 0 \u2014 or really, anything except 1 \u2014 the example is from the negative class.<\/p>\n Note:<\/strong> Even though the counts are whole numbers, we store them as Next, we look at each of the features in turn. For each individual feature, we compute its average value<\/strong> across all the positive examples. We also compute the average value over the negative examples.<\/p>\n Why do we do this? Let\u2019s say a particular feature usually has a large value when it appears in a positive example, but for any of the negative examples its value is close to zero. Then If We can now combine these two averages<\/strong> into a single weight value for this feature:<\/p>\n The formula used here accomplishes the following:<\/p>\n Since If However, if If OK, still with me? At this point we have computed a weight for each individual feature by analyzing our training data.<\/p>\n We can now multiply the data from a given training example with these weights to calculate a score<\/strong>. In math terms, we\u2019re taking the dot product between the weights and the example\u2019s features.<\/p>\n The code for calculating the score looks like this:<\/p>\n A higher score implies this example is likely positive; a lower score implies the example likely belongs to the negative class. However\u2026 we don\u2019t know yet where the actual decision boundary<\/strong> is. We can\u2019t say for sure yet how large the score must be to mean \u201cthis example is positive\u201d.<\/p>\n For instance, if one example has a score of +43.1 and another has a score of -7.8, does that mean the second example belongs to the positive class or the negative class? We don\u2019t know yet. First, we have to figure out where the decision boundary is. Say the decision boundary is at +10.0, then the second example belongs to the negative class. But if the decision boundary is at -15.4, that example still belongs to the positive class, and only examples with a score less than -15.4 are negative.<\/p>\n In order to figure out the decision boundary, we first compute the average scores<\/strong> for all our training examples. As before, we do this separately for the positive and for the negative examples:<\/p>\n Here, The final step in the training process is to compute the bias<\/strong> value:<\/p>\n As I explained, we need to know above which score an example is considered positive. That score is what I called the decision boundary. The bias is used to shift this decision boundary to 0 (hence the minus sign).<\/p>\n To make a prediction, we can now simply take the dot product and add the bias:<\/p>\n If this score is >= 0, the example is positive. If this score is < 0, the example is negative. Thanks to the bias, we don\u2019t need to worry about the decision boundary at all.<\/p>\n In essence, the bias is simply the average of If you\u2019re wondering why we do This is all you need to do to train the classifier. As you can see, it\u2019s just a bunch of for-loops. It doesn\u2019t get much simpler than that!<\/p>\n Note:<\/strong> It should be possible to optimize this even more by using the routines from the Accelerate framework. Instead of computing the average using a for loop, you could use Once the model has been trained, making a prediction on a new example is very straightforward.<\/p>\n I split this up into two functions. The first one computes the \u201craw\u201d score, just like we did above. This multiplies each feature from the example with its corresponding weight, adds them all up, and also adds the bias.<\/p>\n Turning this into a yes\/no prediction is as simple as comparing the score to 0:<\/p>\n Here, a A common strategy to turn a binary classifier into a multiclass classifier is to use one-vs-rest<\/strong>. If there are, say, 3 classes, you train three separate binary classifiers:<\/p>\n To train the first classifier, you give the examples from class A the label \u201cpositive\u201d and the examples from class B and C both get the label \u201cnegative\u201d. Similarly for the other classifiers.<\/p>\n To make a prediction, you run the example through all three classifiers and pick the one that gave the highest score. Here, if the second classifier had the highest score, the predicted class is B.<\/p>\nHow it works<\/h2>\n
let examples: [[Float]] = [\n [6.4, 3.1, 5.5, 1.8],\n [5.4, 3.0, 4.5, 1.5],\n [5.2, 3.5, 1.5, 0.2],\n [6.1, 3.0, 4.9, 1.8],\n [6.4, 2.8, 5.6, 2.2],\n [5.2, 2.7, 3.9, 1.4],\n [5.7, 3.8, 1.7, 0.3],\n [6.0, 2.7, 5.1, 1.6],\n ...\n]\n\nlet labels: [Int] = [\n 1, 1, 0, 1, 0, 1, 1, 1, ...\n]\n<\/code><\/pre>\nexamples<\/code> will be a two-dimensional array of shape N\u00d7M where N is the number of examples and M is the number of features. The labels<\/code> array will be of length N and contains integer values.<\/p>\n0.0<\/code> or larger, and recommends normalizing the data into the range [0, 1]. In my testing it didn\u2019t really make much difference, but I suppose negative numbers can mess up the math in interesting ways.<\/p>\n<\/div>\nIt\u2019s all about the features<\/h2>\n
The algorithm in Swift<\/h2>\n
var weights: [Float] = []\nvar bias: Float = 0\n<\/code><\/pre>\nfit()<\/code>. This takes an array of examples and another array of the training labels:<\/p>\nfunc fit(examples: [[Float]], targets: [Int]) {\n let numExamples = examples.count\n let numFeatures = examples[0].count\n<\/code><\/pre>\nexamples<\/code> is a two-dimensional array of size N\u00d7M, or numExamples<\/code> by numFeatures<\/code>, containing floating-point numbers; targets<\/code> is an array containing numExamples<\/code> labels, where each label is either 0 or 1.<\/p>\n var countPos: Float = 0\n var countNeg: Float = 0\n\n for i in 0..<numExamples { \/\/ loop through all examples\n if targets[i] == 1 { \/\/ this example has positive label\n countPos += 1\n } else { \/\/ this example has negative label\n countNeg += 1\n }\n }\n<\/code><\/pre>\nFloat<\/code> to avoid having to cast them later. If you\u2019re worried about losing precision, have no fear: a Float<\/code> can store integer values just fine (up to 24 bits).<\/p>\n<\/div>\n for f in 0..<numFeatures { \/\/ loop through all features\n var sumPos: Float = 0\n var sumNeg: Float = 0\n\n for i in 0..<numExamples { \/\/ loop through all examples\n if targets[i] == 1 { \/\/ this example has positive label\n sumPos += examples[i][f]\n } else { \/\/ this example has negative label\n sumNeg += examples[i][f]\n }\n }\n\n let avgPos = sumPos \/ countPos\n let avgNeg = sumNeg \/ countNeg\n<\/code><\/pre>\navgPos<\/code> for that feature will be large and avgNeg<\/code> will be small. That means this feature is highly correlated with predicting the positive class.<\/p>\navgNeg<\/code> is greater than avgPos<\/code>, it\u2019s the other way around: this particular feature is more likely to predict the negative class. And if avgPos<\/code> and avgNeg<\/code> are more or less the same, this feature by itself doesn\u2019t really say anything about the example\u2019s class.<\/p>\n let weight = (avgPos - avgNeg) \/ (avgPos + avgNeg + 0.0000001);\n weights.append(weight)\n }\n<\/code><\/pre>\n\n
avgPos<\/code> and avgNeg<\/code> can be anything, we want to normalize them so that the weights are always in the range [-1, +1]<\/strong>. That\u2019s what the division is for. The small \u201cepsilon\u201d value in the denominator prevents division by zero.<\/p>\n<\/li>\navgPos<\/code> for this feature is larger than avgNeg<\/code>, it means the feature is more correlated with the positive class. The formula turns this into a positive weight value between 0 and +1, because the numerator is positive.<\/p>\n<\/li>\navgNeg > avgPos<\/code>, the feature is correlated with the negative class. The numerator is negative, making the weight a number between -1 and 0.<\/p>\n<\/li>\navgPos<\/code> and avgNeg<\/code> are identical or very similar, the numerator is a small number. The resulting weight is close to 0, meaning that the feature is not very important.<\/p>\n<\/li>\n<\/ul>\n var score: Float = 0\n for f in 0..<numFeatures {\n score += examples[i][f] * weights[f] \/\/ dot product!\n }\n<\/code><\/pre>\n var sumPosScore: Float = 0\n var sumNegScore: Float = 0\n \n for i in 0..<numExamples {\n \n var score: Float = 0\n for f in 0..<numFeatures {\n score += examples[i][f] * weights[f]\n }\n\n if targets[i] == 1 { \/\/ example has positive label\n sumPosScore += score\n } else { \/\/ example has negative label\n sumNegScore += score\n }\n }\n\n let avgPosScore = sumPosScore \/ countPos\n let avgNegScore = sumNegScore \/ countNeg\n<\/code><\/pre>\navgPosScore<\/code> should be larger than avgNegScore<\/code> because the weights for \u201cpositive\u201d features are greater than zero, while the weights for \u201cnegative\u201d features are less than zero.<\/p>\n bias = -(countNeg * avgPosScore + countPos * avgNegScore) \n \/ (countNeg + countPos)\n}\n<\/code><\/pre>\nscore = example \u2022 weight + bias\n<\/code><\/pre>\navgPosScore<\/code> and avgNegScore<\/code>. The formula looks a bit more complex because we use a weighted average, in case the number of positive examples in the training dataset is different from the number of negative examples. This is why we multiply by countNeg<\/code> and countPos<\/code>, and divide by the total number of examples.<\/p>\ncountNeg * avgPosScore<\/code> and vice versa: If there are fewer negative examples than positive examples, we want to the avgPosScore<\/code> to count less.<\/p>\nvDSP.mean()<\/code> to do it in one go, for example. Also, if you split the training examples into two sets, one for the positive examples and one for the negative examples, you can optimize the implementation even more.<\/p>\n<\/div>\nAfter training comes sunshine<\/h2>\n
func predictScore(example: [Float]) -> Float {\n var score = bias\n for f in 0..<weights.count {\n score += example[f] * weights[f]\n } \n return score\n}\n<\/code><\/pre>\npublic func predict(example: [Float]) -> Bool {\n predictScore(example: example) >= 0\n}\n<\/code><\/pre>\ntrue<\/code> result means the example belongs to the positive class, while false<\/code> means it belongs to the negative class.<\/p>\nGoing multiclass<\/h2>\n
\n