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

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 如何預測分類

Photo by Clem Onojeghuo on Unsplash

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

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

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

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

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

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

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

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

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

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

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

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

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

SEFR in Python:二元分類器

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(負)。

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

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

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

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

改寫為 SEFR 多元分類器

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)就能負負得正、找到預測標籤了。以這種方式來預測,效能確實提高了。

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
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 的運算時間

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 之類的開發板上?

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);}
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

Photo by Matt Noble on Unsplash

Former translator, after-hours Maker, sunny-day analog film shooter. Currently a junior 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