SEFR 演算法:可在 Arduino Uno 等低耗能微控制器運行的高速多元線性分類器(ML 機器學習,使用 Python 與 Arduino C++)

Image for post
Image for post
Photo by fabio on Unsplash

筆者是個坦白說數學不怎麼樣,也沒什麼興致做純學術研究的人。不過,在大約三個月前,網路上有人分享一個叫做 SEFR 的演算法,由伊朗塔比阿特莫達勒斯大學和美國波士頓大學的研究者提出。該演算法的設計對象居然是 Arduino Uno 這類低耗能嵌入式裝置,而且可直接在開發板上進行模型訓練 — — 可想而知,這讓筆者相當感興趣。最近剛好有些時間,便決定來鑽研一下。

你可在此閱讀這篇論文:SEFR: A Fast Linear-Time Classifier for Ultra-Low Power Devices

SEFR 名稱其實來自自 2012 的一篇論文 A semi-supervised feature ranking method with ensemble learning(使用集成學習的半監督式特徵選取)。不過,感覺跟現在的演算法沒啥關係就是。以下提到的 SEFR 都是以新論文的內容為主。

正如論文所說,在開發板上使用機器學習分類器,最大的挑戰是訓練及預測時間:有些諸如 KNN(K 近鄰)這類演算法完全不需訓練,但預測時非常耗時;Naïve Bayes(單純貝氏分類器)只適合特徵完全獨立的資料;而 SVM(支援向量機)這類強大的演算法不僅耗時,對小樣本的效果也較差。

此外,目前設計來在開發板跑機器學習模型的工具並不多,最著名的大概是 TinyML(即 Tensorflow Lite),在電腦訓練模型後上載到開發板上使用,而這個過程相當繁雜。除此以外,筆者唯一一個看過能在開發板上進行「訓練」的,就只有一個 KNN 顏色識別應用而已。

現在,SEFR 也許可提供我們另一個選擇 — — 讓我們以簡單許多的方式,在低耗能裝置上直接訓練並使用分類器模型。

不過有個問題:論文提出的 SEFR 是個二元分類器。意即,它只能用來預測 label 為正或負的資料而已。不過論文結尾也說,這個原理可套用到多元預測上。因此,筆者在這篇試圖做的事,就是拿網路上的既有程式碼改寫一個多元分類器版本出來 — — 首先用 Python 實作,並檢視其運作效率,接著將這個多元模型連同資料移植到 Arduino Uno 與其他開發板上,證明它的可行性。

SEFR 如何預測分類

Image for post
Image for post
Photo by Clem Onojeghuo on Unsplash

即使和 KNN 相比,SEFR 的計算過程也簡單太多了。不過,請切記筆者是數學苦手,所以我無法解釋當中的實際原理,也有可能講錯(歡迎指正)。但既然運算上夠簡單,要在其他語言複製就不會太難。

簡單地說,SEFR 要找出一個「超平面」(hyperplane)來區分正負分類資料。超平面的公式如下:

Image for post
Image for post

x 是自變數或特徵資料,w 是權重,加上偏誤 b 後應等於 0。因此若代入 x 後 wx + b 的值若大於 0(高於超平面),就視為是正分類,反之小於 0(低於超平面)則是負分類。

為了計算此模型的權重,首先得分別算出正負分類對應的資料的平均:

Image for post
Image for post

也就是說,把所有分類為正的資料加總,除以正分類資料的個數,就得到正分類的平均(u 正三角)。負分類的平均算法相同(u 負三角)。

有了兩個平均數後,就能用「相減除以相加」算出權重(每個特徵各有一個權重值):

Image for post
Image for post

只要拿權重去跟 x 做矩陣相乘,就能得出加權後的分數 ei(每筆資料一個):

Image for post
Image for post

第一筆資料 e1 = w1 * x11 + w2 * x12…

第二筆資料 e2 = w1 * x21 + w2 * x22…

e 加上偏誤 b(不管有多少資料都只有一個 b),等於 0 即為超平面。因此,理想的 b 值就是 e 的負數。問題在於正負分類的樣本可能不一樣多,所以得用加權平均來算。

於是,裡需要先算正分類與負分類各自的 e 之平均:(比如把正分類的特徵資料單獨抓出來,加權後除以正分類的個數 N 正三角)

Image for post
Image for post

然後用加權平均的公式,便能得到偏誤 b:

Image for post
Image for post

得出權重和偏誤後,只要將待預測的資料算出加權結果 e 並和 b 相加,看它是否大於 0,就可預測是正還是負分類了。

SEFR in Python:二元分類器

Image for post
Image for post
Photo by Kelly Sikkema on Unsplash

以下假設你對 NumPy,scikit-learn 跟相關 Python 套件有基本了解。

來看標準的 SEFR 二元分類器是如何運作的。下面的程式碼取自 https://github.com/sefr-classifier/sefr,我做了少許修改:

import numpy as npclass SEFR:    # 訓練模型
def fit(self, data_train, target_train):

self.weights = []
self.bias = 0
# 如果輸入資料是 list, 轉成 ndarray
if isinstance(data_train, list):
data_train = np.array(data_train, dtype='float32')
if isinstance(target_train, list):
target_train = np.array(target_train, dtype='int32')
# 將 label 為 1 或 0 的部分標為 True (公式 2)
pos_labels = (target_train > 0)
neg_labels = np.invert(pos_labels)
# 篩選出正負分類資料
pos_indices = data_train[pos_labels]
neg_indices = data_train[neg_labels]
# 計算正負分類資料的平均數 (公式 3, 4)
avg_pos = np.mean(pos_indices, axis=0)
avg_neg = np.mean(neg_indices, axis=0)
# 計算權重 (公式 5)
self.weights = (avg_pos - avg_neg) / (avg_pos + avg_neg)
# 計算資料加權分數 (公式 6)
weighted_scores = np.dot(data_train, self.weights)
# 計算正負分類加權分數的平均 (公式 7, 8)
pos_score_avg = np.mean(weighted_scores[pos_labels])
neg_score_avg = np.mean(weighted_scores[neg_labels])

pos_label_count = pos_indices.size
neg_label_count = neg_labels.size
# 計算偏誤 (公式 9)
self.bias = -(neg_label_count * pos_score_avg + pos_label_count * neg_score_avg) / (neg_label_count + pos_label_count)

# 預測資料
def predict(self, data_test):
if isinstance(data_test, list):
data_test = np.array(data_test, dtype='float32')
# 計算加權測試資料
weighted_score = np.dot(data_test, self.weights)

# 若資料加權值加偏誤高於超平面 (公式 1) 就視為 label=1, 否則為 0
preds = np.where(weighted_score + self.bias > 0, 1, 0)

# 傳回預測 labels
return preds

拜 NumPy 之賜,很多計算跟資料篩選作業可以用一行程式碼簡化。此外,我將分類定義為 1(正)和 0(負)。

Image for post
Image for post
Photo by David Travis on Unsplash

現在,我們來用 scikit-learn 產生一些二元分類的測試資料,順便用 matplotlib 將分類前後的資料圖形化,好看看 SEFR 的分類超平面在哪:

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, classification_report
import matplotlib.pyplot as plt
# 產生兩組隨機資料
data, target = datasets.make_blobs(n_samples=5000, n_features=2, centers=2, random_state=0)
# 分割資料 (80% 訓練集, 20% 測試集)
data_train, data_test, target_train, target_test = train_test_split(data, target, test_size=0.2)
# 建立 SEFR 分類器並取得測試集的預測結果
sefr = SEFR()
sefr.fit(data_train, target_train)
predictions = sefr.predict(data_test)
# 取得預測成績
print(classification_report(target_test, predictions))
plt.rcParams['font.size'] = 14
plt.figure(figsize=(16, 8))
# 按原始分類顯示的測試集資料
plt.subplot(121)
plt.title('Test Data')
plt.scatter(data_test.T[0], data_test.T[1], c=target_test, cmap=plt.cm.Paired)
# 按預測分類顯示的測試集資料
plt.subplot(122)
plt.title('SEFR predictions')
plt.scatter(data_test.T[0], data_test.T[1], c=predictions, cmap=plt.cm.Paired)
# 畫出分界線 (x2 = (-b - w1x1) / w2)
x1 = np.linspace(data_test.T[0].min(), data_test.T[0].max(), 2)
x2 = (-sefr.bias - sefr.weights[0] * x1) / sefr.weights[1]
plt.plot(x1, x2, color='green')
# 顯示圖表
plt.tight_layout()
plt.show()

得到結果如下:

              precision    recall  f1-score   support           0       0.96      0.95      0.95       508
1 0.95 0.96 0.95 492
accuracy 0.95 1000
macro avg 0.95 0.95 0.95 1000
weighted avg 0.95 0.95 0.95 1000
Image for post
Image for post

你可以清楚看到,SEFR 在兩塊略有重疊的資料中間切出一條線,以此作為分類的基準 — — 這條線就是此二維空間的超平面。

你可以試試看其他的 random_state 參數,比如 random_state=12:

Image for post
Image for post

不過,取決於隨機資料生成的狀況,有時會從很奇怪的地方切過去,也許是因為超平面是用資料的平均位置去計算的。也有時辨識出來的標籤跟實際上剛好顛倒,可能是因為「正負」分類資料的大小順序所致。不過,這現象在後面的多元分類版本中倒是(還)沒有看過。

改寫為 SEFR 多元分類器

Image for post
Image for post
Photo by Miguel Teirlinck on Unsplash

那麼,若要將對正負分類的預測擴展到三個以上的分類(多元),該怎麼做呢?畢竟其他二元分類器,比如邏輯斯迴歸或 SVM,就可以套用在多元分類資料上。

筆者參考了機器學習: 如何在多類別分類問題上使用用二元分類器進行分類這篇文章,其中「一對多」(one-vs-rest)的處理方式如下:

  1. 若有 N 個分類,訓練時會做 N 次二元分類訓練,每次對分類 X 及非 X、Y 及非 Y、Z 及非 Z…產生權重與偏誤。
  2. 到了預測時,把新資料分別對每一組權重產生一個加權分數,算出該值跟對應偏誤的差距。於是,每一筆資料會得到 N 個加權分數減偏誤的結果,代表分類 X、Y、Z…。
  3. 看這些值中誰最大,資料就最有可能是該值對應的分類。

不過筆者在嘗試時,預測出來的結果似乎沒有特別好。後來改個方向,每次都以「不是 X、不是 Y、不是 Z…」的方式訓練(也就是說,每次針對的標籤都被當成負分類,其他的標籤則是正分類)。等到預測時,計算出 wx + b 後,只要看最小值(比如,「不是 X」的預測結果中,可能性最低的那個就很可能是 X)就能負負得正、找到預測標籤了。以這種方式來預測,效能確實提高了。

Image for post
Image for post
Photo by Eric Prouzet on Unsplash

下面就是筆者改寫成多元分類器版的 SEFR:

import numpy as npclass SEFR_MULTI:    def fit(self, data_train, target_train):

self.weights = []
self.bias = []

if isinstance(data_train, list):
data_train = np.array(data_train, dtype='float32')
if isinstance(target_train, list):
target_train = np.array(train_target, dtype='int32')
self.labels = np.unique(target_train) # 取得所有 labels

for label in self.labels: # 依次對所有 labels 計算權重及偏誤
pos_labels = (target_train != label) # 判斷「不是該 label」
neg_labels = np.invert(pos_labels)

pos_indices = data_train[pos_labels]
neg_indices = data_train[neg_labels]
avg_pos = np.mean(pos_indices, axis=0)
avg_neg = np.mean(neg_indices, axis=0)
weight = (avg_pos - avg_neg) / (avg_pos + avg_neg) weighted_scores = np.dot(data_train, weight)
weight = np.nan_to_num(weight) # 如果算出 NaN 就設為 0
pos_score_avg = np.mean(weighted_scores[pos_labels])
neg_score_avg = np.mean(weighted_scores[neg_labels])

pos_label_count = pos_indices.size
neg_label_count = neg_labels.size

bias = -(neg_label_count * pos_score_avg + pos_label_count * neg_score_avg) / (neg_label_count + pos_label_count)

self.weights.append(weight)
self.bias.append(bias)

def predict(self, new_data):
probs = []
self.preds = []
if isinstance(data_test, list):
new_data= np.array(new_data, dtype='float32')
for i in self.labels:
probs.append(np.dot(new_data, self.weights[i]) + self.bias[i])

probs = np.array(probs).T

# 根據權重減偏誤的最小值 (最不可能不是的 label) 做出預測
for prob in probs:
self.preds.append(self.labels[np.argmin(prob)])

self.preds = np.array(self.preds)
# 傳回預測 labels
return self.preds
Image for post
Image for post
Photo by UX Indonesia on Unsplash

現在,我們來使用 scikit-learn 提供的經典鳶尾花資料集,看看這個多元分類器的預測效果如何:

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, classification_report
data, target = datasets.load_iris(return_X_y=True)
data_train, data_test, target_train, target_test = train_test_split(data, target, test_size=0.2, random_state=0)
sefr = SEFR_MULTI()
sefr.fit(data_train, target_train)
predictions = sefr.predict(data_test)
print('Pred:', predictions) # 測試集預測 label
print('Real:', target_test) # 測試集真實 label
print('Accuracy:', accuracy_score(target_test, predictions).round(3))
print(classification_report(target_test, predictions))

得到結果如下:

Pred: [2 1 0 2 0 2 0 1 1 1 1 1 1 1 1 0 1 1 0 0 2 1 0 0 1 0 0 1 1 0]
Real: [2 1 0 2 0 2 0 1 1 1 2 1 1 1 1 0 1 1 0 0 2 1 0 0 2 0 0 1 1 0]
Accuracy: 0.933
precision recall f1-score support
0 1.00 1.00 1.00 11
1 0.87 1.00 0.93 13
2 1.00 0.67 0.80 6
accuracy 0.93 30
macro avg 0.96 0.89 0.91 30
weighted avg 0.94 0.93 0.93 30

準確率有 93%,對 3 個分類的結果都不錯。以這麼簡單的演算法來說還不賴吧?

再來換一個葡萄酒資料集玩玩:

data, target = datasets.load_wine(return_X_y=True)

結果會比較差一點(78%),特別是分類 2:

Pred: [0 2 1 0 1 1 0 2 1 1 2 1 0 2 2 1 0 0 1 0 1 0 2 2 2 1 1 1 2 2 0 0 2 0 0 2]
Real: [0 2 1 0 1 1 0 2 1 1 2 2 0 1 2 1 0 0 1 0 1 0 0 1 1 1 1 1 1 2 0 0 1 0 0 0]
Accuracy: 0.778
precision recall f1-score support
0 1.00 0.86 0.92 14
1 0.92 0.69 0.79 16
2 0.42 0.83 0.56 6
accuracy 0.78 36
macro avg 0.78 0.79 0.75 36
weighted avg 0.87 0.78 0.80 36

聊以慰藉的是,KNN(K=3)對葡萄酒資料集的準確率也只有 78%,K=5 時則僅提高到 81%。所以,SEFR 的預測效能也取決於各 label 之資料之間的重疊程度。

在處理 scikit-learn 的手寫數字資料集(每張圖是 8x8 灰階圖片,標籤為 0 至 9),也可以達到 84% 的準確率:

data, target = datasets.load_digits(return_X_y=True)

準確率雖然沒有其他演算法高,但執行速度上明顯快得多,而這就是 SEFR 的最大優點。

Accuracy: 0.842
precision recall f1-score support
0 1.00 1.00 1.00 27
1 0.85 0.66 0.74 35
2 1.00 0.58 0.74 36
3 1.00 0.83 0.91 29
4 1.00 0.97 0.98 30
5 1.00 0.75 0.86 40
6 1.00 0.89 0.94 44
7 0.92 0.87 0.89 39
8 0.51 1.00 0.68 39
9 0.74 0.90 0.81 41
accuracy 0.84 360
macro avg 0.90 0.84 0.86 360
weighted avg 0.89 0.84 0.85 360

SEFR 的運算時間

Image for post
Image for post
Photo by Curtis MacNewton on Unsplash

那麼,SEFR 做訓練和預測的時間效率跟其他演算法相比如何呢?筆者在自己的電腦上用 scikit-learn 提供的幾個模型來試驗。這裡使用鳶尾花資料集,一樣分割成 80% 與 20%,random_state = 0,每個跑 100 次後取 time.time_ns() 的平均:

  • SEFR:約 500 奈秒,準確率 93%
  • KNN(K=3):約 2700 奈秒,準確率 97%
  • 邏輯斯迴歸(預設迭代 100 次):約 37000 奈秒,準確率 100%
  • 線性 SVM(預設迭代 100 次):約 8600 奈秒,準確率 100%

你可以發現,SEFR 需要的時間少非常多。在時脈不高的嵌入式系統上,這就會有很大的優點,而且更簡單的運算可能也意味著不需要那麼多記憶體。如果開發板得倚賴電池運作,這還能延長電力壽命。

移植到微控制器上

好,現在比較困難的來了:我們要怎麼把這技術應用在 Arduino Uno 之類的開發板上?

Image for post
Image for post
Photo by Daniel Andrade on Unsplash

https://github.com/sefr-classifier/sefr/blob/master/arduino-c 有個寫給 Arduino 的範例程式,不過幾乎什麼也沒解釋,也不知道資料集跟執行結果意味著什麼。反正,筆者只得自行重寫一個多元分類器版的程式。

基本上,訓練資料會連同程式一起燒錄到板子上,每次重開時會重新訓練,然後就能投入使用:

  1. 由於找不太到有什麼辦法把 scikit-learn 的資料集轉成 C++ 形式,筆者最後乾脆…用一些迴圈和 print() 把它印成 C++ 語法字串,輸出後複製貼上。
  2. 為了有效節省記憶體,資料集的所有特徵資料乘以 10(運算時會再除以 10),這樣就能用整數儲存。
  3. 至於測試,本來想做一個 UART 介面去讀使用者輸入的資料,不過決定直接拿既有資料,每個特徵用亂數隨機增減原值的 0~30%。這樣一來也可以跟原本的 label 比對。

這支程式可在 Arduino Uno 和 Arduino Micro 上運作;記憶體更大的開發板自然就不用說了。

這篇文章不會教如何燒錄程式到 Uno。

/*
This is the multiclass classifier version of the SEFR algorithm for Arduino C++
based on my own Python version.
It's runnable on Arduino Uno/Nano and Arduino Leonardo/Micro.
*/
const byte FEATURES = 4; // number of features
const byte LABELS = 3; // number of labels
const byte DATAFACTOR = 10; // scale factor of data
// the Iris dataset (times DATAFACTOR so it can be stored as integer and save space/memory)
int DATASET[][FEATURES] = {
{51, 35, 14, 2}, {49, 30, 14, 2}, {47, 32, 13, 2}, {46, 31, 15, 2}, {50, 36, 14, 2}, {54, 39, 17, 4}, {46, 34, 14, 3}, {50, 34, 15, 2}, {44, 29, 14, 2}, {49, 31, 15, 1}, {54, 37, 15, 2}, {48, 34, 16, 2}, {48, 30, 14, 1}, {43, 30, 11, 1}, {58, 40, 12, 2}, {57, 44, 15, 4}, {54, 39, 13, 4}, {51, 35, 14, 3}, {57, 38, 17, 3}, {51, 38, 15, 3}, {54, 34, 17, 2}, {51, 37, 15, 4}, {46, 36, 10, 2}, {51, 33, 17, 5}, {48, 34, 19, 2}, {50, 30, 16, 2}, {50, 34, 16, 4}, {52, 35, 15, 2}, {52, 34, 14, 2}, {47, 32, 16, 2}, {48, 31, 16, 2}, {54, 34, 15, 4}, {52, 41, 15, 1}, {55, 42, 14, 2}, {49, 31, 15, 2}, {50, 32, 12, 2}, {55, 35, 13, 2}, {49, 36, 14, 1}, {44, 30, 13, 2}, {51, 34, 15, 2}, {50, 35, 13, 3}, {45, 23, 13, 3}, {44, 32, 13, 2}, {50, 35, 16, 6}, {51, 38, 19, 4}, {48, 30, 14, 3}, {51, 38, 16, 2}, {46, 32, 14, 2}, {53, 37, 15, 2}, {50, 33, 14, 2}, {70, 32, 47, 14}, {64, 32, 45, 15}, {69, 31, 49, 15}, {55, 23, 40, 13}, {65, 28, 46, 15}, {57, 28, 45, 13}, {63, 33, 47, 16}, {49, 24, 33, 10}, {66, 29, 46, 13}, {52, 27, 39, 14}, {50, 20, 35, 10}, {59, 30, 42, 15}, {60, 22, 40, 10}, {61, 29, 47, 14}, {56, 29, 36, 13}, {67, 31, 44, 14}, {56, 30, 45, 15}, {58, 27, 41, 10}, {62, 22, 45, 15}, {56, 25, 39, 11}, {59, 32, 48, 18}, {61, 28, 40, 13}, {63, 25, 49, 15}, {61, 28, 47, 12}, {64, 29, 43, 13}, {66, 30, 44, 14}, {68, 28, 48, 14}, {67, 30, 50, 17}, {60, 29, 45, 15}, {57, 26, 35, 10}, {55, 24, 38, 11}, {55, 24, 37, 10}, {58, 27, 39, 12}, {60, 27, 51, 16}, {54, 30, 45, 15}, {60, 34, 45, 16}, {67, 31, 47, 15}, {63, 23, 44, 13}, {56, 30, 41, 13}, {55, 25, 40, 13}, {55, 26, 44, 12}, {61, 30, 46, 14}, {58, 26, 40, 12}, {50, 23, 33, 10}, {56, 27, 42, 13}, {57, 30, 42, 12}, {57, 29, 42, 13}, {62, 29, 43, 13}, {51, 25, 30, 11}, {57, 28, 41, 13}, {63, 33, 60, 25}, {58, 27, 51, 19}, {71, 30, 59, 21}, {63, 29, 56, 18}, {65, 30, 58, 22}, {76, 30, 66, 21}, {49, 25, 45, 17}, {73, 29, 63, 18}, {67, 25, 58, 18}, {72, 36, 61, 25}, {65, 32, 51, 20}, {64, 27, 53, 19}, {68, 30, 55, 21}, {57, 25, 50, 20}, {58, 28, 51, 24}, {64, 32, 53, 23}, {65, 30, 55, 18}, {77, 38, 67, 22}, {77, 26, 69, 23}, {60, 22, 50, 15}, {69, 32, 57, 23}, {56, 28, 49, 20}, {77, 28, 67, 20}, {63, 27, 49, 18}, {67, 33, 57, 21}, {72, 32, 60, 18}, {62, 28, 48, 18}, {61, 30, 49, 18}, {64, 28, 56, 21}, {72, 30, 58, 16}, {74, 28, 61, 19}, {79, 38, 64, 20}, {64, 28, 56, 22}, {63, 28, 51, 15}, {61, 26, 56, 14}, {77, 30, 61, 23}, {63, 34, 56, 24}, {64, 31, 55, 18}, {60, 30, 48, 18}, {69, 31, 54, 21}, {67, 31, 56, 24}, {69, 31, 51, 23}, {58, 27, 51, 19}, {68, 32, 59, 23}, {67, 33, 57, 25}, {67, 30, 52, 23}, {63, 25, 50, 19}, {65, 30, 52, 20}, {62, 34, 54, 23}, {59, 30, 51, 18}
};
// labels of the Iris dataset
byte TARGET[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
};
float weights[LABELS][FEATURES]; // model weights on each labels
float bias[LABELS]; // model bias on each labels
unsigned int training_time; // mode training time
// ==================================================// train SEFR model with DATASET and TARGET
void fit() {
unsigned int datasize = sizeof(TARGET), start_time = millis(); // iterate all labels
for (byte l = 0; l < LABELS; l++) {
unsigned int count_pos = 0, count_neg = 0; // iterate all features
for (byte f = 0; f < FEATURES; f++) {
float avg_pos = 0.0, avg_neg = 0.0;
count_pos = 0;
count_neg = 0;
for (unsigned int s = 0; s < datasize; s++) {
// use "not the label" as positive class
if (TARGET[s] != l) {
avg_pos += float(DATASET[s][f]);
count_pos++;
} else { // use the label as positive class
avg_neg += float(DATASET[s][f]);
count_neg++;
}
}
avg_pos /= (float(count_pos) * float(DATAFACTOR));
avg_neg /= (float(count_neg) * float(DATAFACTOR));
// calculate weight of this label
weights[l][f] = (avg_pos - avg_neg) / (avg_pos + avg_neg);
}
// weighted score of data
int weighted_scores[datasize];
for (unsigned int s = 0; s < datasize; s++) {
weighted_scores[s] = 0.0;
for (byte f = 0; f < FEATURES; f++) {
weighted_scores[s] += (float(DATASET[s][f]) * weights[l][f] * 100);
}
}
float avg_pos_w = 0.0, avg_neg_w = 0.0;
for (unsigned int s = 0; s < datasize; s++) {
if (TARGET[s] != l) {
avg_pos_w += float(weighted_scores[s]);
} else {
avg_neg_w += float(weighted_scores[s]);
}
}
avg_pos_w /= (float(count_pos) * float(DATAFACTOR) * 100.0);
avg_neg_w /= (float(count_neg) * float(DATAFACTOR) * 100.0);
// calculate bias of this label
bias[l] = -1 * (float(count_neg) * avg_pos_w + float(count_pos) * avg_neg_w) / float(count_pos + count_neg);
}
// calculate training time
training_time = millis() - start_time;
}// predict label from a single new data instance
byte predict(int new_data[FEATURES]) {
float score[LABELS];
for (byte l = 0; l < LABELS; l++) {
score[l] = 0.0;
for (byte f = 0; f < FEATURES; f++) {
// calculate weight of each labels
score[l] += (float(new_data[f]) / float(DATAFACTOR) * weights[l][f]);
}
score[l] += bias[l]; // add bias of each labels
}
// find the min score (least possible label of "not the label")
float min_score = score[0];
byte min_label = 0;
for (byte l = 1; l < LABELS; l++) {
if (score[l] < min_score) {
min_score = score[l];
min_label = l;
}
}
return min_label; // return prediction}// ==================================================void setup() { Serial.begin(9600);
randomSeed(42);
fit(); // train SEFR model}void loop() { // randomly pick a random data instance in DATASET as test data unsigned int test_index = random(0, sizeof(TARGET));
int test_data[FEATURES];
byte test_label = TARGET[test_index];
Serial.print("Test data: ");
for (byte f = 0; f < FEATURES; f++) {
int sign = (random(0, 2) == 0) ? 1 : -1;
int change = int(DATASET[test_index][f] * float(random(4)) / 10.0);
test_data[f] = DATASET[test_index][f] + change * sign; // randomly add or subtract 0-30% to each feature
Serial.print(float(test_data[f]) / float(DATAFACTOR));
Serial.print(" ");
}
Serial.println("");
// predict label
byte result_label = predict(test_data);
// compare the results
Serial.print("Predicted label: ");
Serial.print(result_label);
Serial.print(" / actual label: ");
Serial.print(test_label);
Serial.print(" / (SEFR training time: ");
Serial.print(training_time);
Serial.println(" ms)");
Serial.println("");
delay(1000);}
Image for post
Image for post
Photo by israel palacio on Unsplash

在 Arduino IDE 中編譯和上傳程式,可看到以下訊息:

草稿碼使用了 7324 bytes (22%) 的程式儲存空間。上限為 32256 bytes。
全域變數使用了 1692 bytes (82%) 的動態記憶體,剩餘 356 bytes 給區域變數。上限為 2048 bytes 。
可用記憶體低下,可能會出現穩定性問題

儘管出現警告訊息,仍可見這程式有辦法塞進 Uno 小小的的 32 KB 儲存空間以及區區 2 KB 記憶體,而這幾乎已是市面上開發板中最低規格的產品了!打開序列部監控視窗,也可看到針對測試資料的預測結果:

測試資料: 6.20 3.30 1.40 0.30 
預測分類: 0 / 實際分類: 0 / (SEFR 訓練時間: 100 ms)
測試資料: 8.30 3.30 4.00 2.30
預測分類: 2 / 實際分類: 2 / (SEFR 訓練時間: 100 ms)
測試資料: 3.50 2.40 2.40 1.30
預測分類: 1 / 實際分類: 1 / (SEFR 訓練時間: 100 ms)
測試資料: 3.60 3.80 1.60 0.20
預測分類: 0 / 實際分類: 0 / (SEFR 訓練時間: 100 ms)
測試資料: 7.40 2.80 4.90 1.00
預測分類: 1 / 實際分類: 1 / (SEFR 訓練時間: 100 ms)
測試資料: 6.40 2.60 4.90 1.10
預測分類: 1 / 實際分類: 1 / (SEFR 訓練時間: 100 ms)
測試資料: 3.70 2.30 1.30 0.20
預測分類: 0 / 實際分類: 0 / (SEFR 訓練時間: 100 ms)
測試資料: 6.30 2.70 6.10 1.80
預測分類: 2 / 實際分類: 2 / (SEFR 訓練時間: 100 ms)
測試資料: 5.10 3.00 1.30 0.10
預測分類: 0 / 實際分類: 0 / (SEFR 訓練時間: 100 ms)
測試資料: 6.30 2.70 4.50 1.30
預測分類: 1 / 實際分類: 2 / (SEFR 訓練時間: 100 ms)

這裡同時告訴我們,模型訓練時間為 100 毫秒(0.1 秒)。Uno 和 Micro 的處理器(Atmega328p,Atmega32u4)都是 16 MHz,所以訓練時間一樣;筆者改用 Seeeduino XIAO(48 MHz 的 SAMD21)測試時降到 40 毫秒,而 ESP8266(80 MHz)則僅花費 11 毫秒。

板子通電後還是會有一點可察覺的微小延遲時間,大概是因為得讀取資料集。不過,和 Tensorflow 之類的模型相比(光在電腦上跑就要老半天),SEFR 的訓練確實沒花上什麼顯著的時間。

結語

當然,你不是一定得用 Uno 不可;如今有許多 32 位元開發板已經相當廉價,不僅時脈更快、儲存空間跟記憶體都更大,比起能夠運行 TinyML 的高階開發板也相對更容易取得。只要你能找到辦法將新資料輸入給板子,就能立刻運用 SEFR 來運行機器學習模型,而這則可進一步延伸到邊緣運算領域。

其實,既然演算法是如此簡單,你可以在電腦上訓練,接著把權重和偏誤拷貝到別的開發板就能直接做預測了。反過來說,SEFR 的一個優勢說不定是能快速地動態更新模型 — — 在現場收集新資料後即時調整權重跟偏誤。至於如何透過裝置儲存資料和給予標籤,那就是另一個挑戰了。

無論如何,在微控制器上跑機器學習模型,仍是個有許多可能性等待發掘的新天地。而 SEFR 或許可證明:你不一定需要最強、最貴的東西才能在嵌入式系統玩 ML。

後註:這篇的程式其實是稍舊一點的版本,我偶爾會更新演算法,目前 Arduino 版在 Uno 上的訓練時間已經縮減到 70+ ms。

最新版 code 請至我的 Github 上取得:https://github.com/alankrantas/sefr_multiclass_classifier

Image for post
Image for post
Photo by Matt Noble on Unsplash

Written by

Former translator and currently a tech-book editor based in Taiwan. https://krantasblog.blogspot.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store