はじめに
ホントに生成AIの進化は凄まじいですよね。その基本アルゴリズムは言わずと知れたディープラーニング❗️世界中の優秀な頭脳が よってたかって その技術を深掘りしてます。
しかし、ご存知の通り🌎️世界のGPUは偏在していて... 悔しいけど普通の研究者（特に日本の大学）は全く太刀打ち出来ません。これに少しでも風穴を開けようと頑張って書いたのがこの記事です。
なんと！新しい（と思う）機械学習のアルゴリズムが完成しました。ガチです。本当に新しいかどうか？ 是非、記事を読んで確かめて下さい。
ランダムフォレスト
今回、新しく創ったアルゴリズムはランダムフォレストの亜種です。
Random Forestの特性は下記の通り
- アルゴリズムが超シンプル
- 学習が爆速（並列化容易）
- そこそこの認識性能
最初の2つは良しとして、問題は3つ目の《認識性能》です。学習データの量がある程度多くなると、どう頑張ってもニューラルネットに勝てなくなります。そしてニューラルネットの方はというと... 速度問題をハードで解決し今のディープラーニングの全盛に至るわけです。
このRandom Forestの問題点を乗り越えようとしたのがDeep Forestです。
Deep Forest
元論文はこれです↓
Qiitaさんの記事もあります。アルゴリズムの詳細は下記の記事をご参照下さい。
「Random Forest舐めんなよ！」と著者も思ったかどうか？は定かではありませんがw、論文からは Random Forest愛 がヒシヒシと伝わってきます。Random Forestの良さに惚れ込んで何とか認識率をDeep Learningと同等に持っていこうと頑張った結果、このアルゴリズムが完成したのでしょう。
しかしながら２点だけ残念な所があります。
- アルゴリズムの複雑さ
- データ構造に関する暗黙の仮定
です。
1つ目は見たまんま。色々複雑な処理を施していて苦労の跡が伺われます。2つ目は1次元もしくは2次元の連続性・トポロジーを仮定している所です。これは強い条件で、論文にも書かれてますが、条件を取っ払うと認識性能はガクンと落ちます。
Deep Forestの狙い
残念な所は有りつつも、色々工夫すればディープラーニングと肩を並べられる事を示したDeep Forestはランダムフォレストガチ勢の私に希望を与えてくれました。
Deep Forestが狙ったのは下図の処理です。
ニューラルネットはimplicitにこの高次元へのデータ投影をしている、と考えられています。Input空間でスパゲッティのように絡まったデータを高次元に解きほぐしながら写像する。（SVMのコンセプトも同じ感じですよね）一方、Random ForestはInput空間をダイレクトに分割します。ワンクッションがないんです！
そこでニューラルネットの中間層のような空間を用意しました。で、問題はこの高次元空間の形です。Deep ForestのようにRandom Forestの答えであるラベル確率（クラス確率）を使うと大量に繋げないとダメだし、どうしてもアドホックなアルゴリズムになってしまいます。う～ん、自然で安全でシンプルな方法はないものか？と考えた末に今回のアルゴリズムが出来ました。
素のランダムフォレスト
本題の新アルゴリズムの説明に入る前に、ベースラインとして、素のランダムフォレストの性能を押さえておきたいと思います。
評価に使ったのは皆大好きMNISTです。
MNISTデータのダウンロードと0～1 floatへの正規化(normalize)はこのスクリプトを使いました。
データ出力はこのスクリプトで行いました
import struct
import mnist as dl
if __name__ == '__main__':
(X_train, y_train), (X_test, y_test) = dl.load_mnist()
print(len(X_test))
print(max(X_train[0]))
print(min(X_train[0]))
sample_num, dimension_num = X_train.shape
with open("data_train.bin", "wb") as f:
f.write(struct.pack("i", sample_num))
f.write(struct.pack("i", dimension_num))
for arr in X_train:
for val in arr:
f.write(struct.pack("f", val))
with open("label_train.bin", "wb") as f:
f.write(struct.pack("i", sample_num))
for val in y_train:
f.write(struct.pack("b", val))
sample_num, dimension_num = X_test.shape
with open("data_test.bin", "wb") as f:
f.write(struct.pack("i", sample_num))
f.write(struct.pack("i", dimension_num))
for arr in X_test:
for val in arr:
f.write(struct.pack("f", val))
with open("label_test.bin", "wb") as f:
f.write(struct.pack("i", sample_num))
for val in y_test:
f.write(struct.pack("b", val))
今回のアルゴリズムのソースコードはGithubに上げてます。
ES_Forest.cpp: 素のランダムフォレストから新アルゴリズムまで全て入ったcpp
License: MIT
ビルド環境: Visual Studio Community 2022 Version 17.14.5
素のRandom Forestを動作させるためには
Program_Type g_Program_Type = Program_Type::Simple_Random_Forest;
とすれば良いです。
パラメータを下記のようにすると 誤認識率2.21% をたたき出します。
const int Tree_Num_for_Recognition = 512;
int Query_Candidate_Num = 16;
ランダムフォレストは、木構造の最初の方（ルートノードに近い浅い所）のクエリーをバリエーション多くするのが肝です。そのために下記の工夫をしてます。
- (A) ２点の値の線形結合を使う
- (B) ツリーの深さに応じて探索空間を広げる
それぞれ対応するソースコードは下記の部分となります。
float base_value = a * value_array[base];
float look_value = b * value_array[look];
if ((look_value - base_value + offset) <= 0)
return 0;
else
return 1;
baseとlookは入力画像の中の比較する２点のポインタです。
int query_candidate_num = Query_Candidate_Num * (depth + 1);
Treeの浅い所ではクエリー候補をすごく少なくしてランダム性を高め、深くなるにつれて頑張って効率の良いクエリーを探すという作戦です。
高い高い壁
これらの工夫をすることで 誤認識率2.21% をたたき出せましたが、これがなかなか凄いんですよ。思いついた改良を片っ端から実装しましたが、この成績には遠く及びませんでした。いや～生き残っているアルゴリズムはやはり長い間多くの人のチャレンジを退けてきたんだな...と思いましたね。
実際、MNISTに何の前処理もしないでニューラルネットを使っても、下記の記事のモデル2となって、ちょうど誤認識率2.2%ぐらいなんです。
これはもうMNISTに何の条件も入れない状態の 限界性能 だろう❗️と思って何度も諦めそうになりました。
しかし原点に戻って、この図の真ん中にある大きな次元の空間を、explicitで、simpleだけどtrivialじゃない物にするとどうなるか？考えた結果、このアルゴリズムを思い付きました。
Exponentiation Space Forest
引っ張り過ぎですねw すみません。やっと新アルゴリズムのお披露目です。
新アルゴリズムは Exponentiation Space Forest といいます。
アルゴリズム名について
Exponentiation Spaceは、日本語にすると【べき乗空間】です。ググっても出てきません。（造語ですw）
定義は「特徴空間を出力ラベルの数分、直積にした空間」です。MNISTでのイメージとしては0～9までの10枚の28×28サイズの画像群と同じ意味になります。
中間層にあたる高次元空間をこのべき乗空間にしたのが本アルゴリズムです。
実装ロジック
べき乗空間への写像にもRandom Forestを使いました。もしかしたら、このやり方自体が肝である可能性はありますが、基本、べき乗空間への写像は色んなバリエーションがあり得ると思ってます。
ソースでは以下のようにしてます。
- 学習データをN分割する
- 各分割に対して自分以外の（N-1）個の分割データを使ってRandom Forest学習
- 各データに対して自分を含まない分割で学習したRandom Forestをリーフノードまで辿る
- リーフノードにある学習データの各ラベルにおける平均形を計算してべき乗空間に射影する
それぞれソースの対応箇所は以下です
void Set_g_Ptr_Arrays()
{
mt19937_64 random_engine(0);
vector<int> ptr_array;
for (int n = 0; n < g_Sample_Num; n++) ptr_array.push_back(n);
shuffle(ptr_array.begin(), ptr_array.end(), random_engine);
for (int n = 0; n < g_Sample_Num; n++) {
g_Ptr_Arrays[n % Partition_Num].push_back(ptr_array[n]);
}
}
switch (g_RF_Type)
{
case RF_Type::Projection_1:
case RF_Type::Projection_2:
{
int partition_n = 0;
if (g_RF_Type == RF_Type::Projection_1)
partition_n = tree_number / Tree_Num_for_Projection_1;
else if (g_RF_Type == RF_Type::Projection_2)
partition_n = tree_number / Tree_Num_for_Projection_2;
for (int n = 0; n < Partition_Num; n++) {
if (n == partition_n) continue;
for (auto ptr : g_Ptr_Arrays[n]) ptr_array.push_back(ptr);
}
break;
}
for (int n = 0; n < tree_num; n++) {
int tree_n = partition_n * tree_num + n;
ptr_array[n] = tree_array[tree_n].Get_Leaf_Ptr(value_array);
}
memset(pattern, 0, pattern_dimension_num * sizeof(float));
for (int n = 0; n < tree_num; n++) {
int ptr = ptr_array[n];
int tree_n = partition_n * tree_num + n;
int pattern_label_num = tree_array[tree_n].memory_sequence[ptr++].int_value;
for (int label_n = 0; label_n < pattern_label_num; label_n++) {
int label = tree_array[tree_n].memory_sequence[ptr++].int_value;
int SIZE = pattern_dimension_num / Label_Num;
for (int i = 0; i < SIZE; i++) {
pattern[label * SIZE + i] += (float)(tree_array[tree_n].memory_sequence[ptr++].float_value);
}
}
}
以上の処理で、べき乗空間には、もし他のラベルだったらこんな形だろう...という情報も含めた形が現れます。そして、それぞれのラベルの形の強度にはそのラベルの《確からさ》が反映されてます。
性能
さあ！スパゲッティもほぐれた事だし、と思って意気揚々とべき乗空間からRandom Forestを学習した結果、 誤認識率 2.54%
なんと、悪化してる！
ハイお疲れ～ ほわん、ほわん、ほわん だったのです。
でも絶対何とかなる！と思い気を取り直してRandom Forestのクエリーを２つの次元の線形結合ではなくて、２つのサンプルからの距離の比較にしました。
ソースコードはこの部分↓
case Query_Ptr_Type::Instance_Ptr:
{
int dim_num = g_Input_Dimension_Num;
float base_norm = a * Calc_Norm(g_Input_Data + base * dim_num, value_array, dim_num);
float look_norm = b * Calc_Norm(g_Input_Data + look * dim_num, value_array, dim_num);
if ((look_norm - base_norm + offset) <= 0)
return 0;
else
return 1;
}
こうすると 誤認識率 1.81% やっとRandom Forestの高い高い壁を越えました！
Deepにすると
本アルゴリズムの重要な性質は、データ構造に全く何の仮定も置いていない所と、Deep Learningのようにどんどん深くできる所です。
試しにMNISTで下図のように２回べき乗空間を展開してみました。
メモリが足りなくなるのとメッチャ時間がかかるのでデータを1/10にしてやってみましたが、結果は悪化してしまいました。データが少ないのが原因なのか？ラベルが10個（OK/NGの2個ならもっとマイルドに空間が大きくなる）なのが原因なのか？深く追求してませんが、原理的にはこのようにどんどん深くすることが出来ます。
結局ベクトル演算必要なの？？
今回の計算機実験でわかった面白い結果の1つは、べき乗空間でのクエリーは２点比較ではなく、２サンプルからの距離を使う方が性能が高い事です。
でも考えてみれば当然のことかもしれません。だって空間の次元数が大きくなると１つ１つの次元の寄与度は少なくなるわけなので、クエリーをたった２つの次元の値比較にすると効率が悪くなりますよね。
結局、次元が大きくなるとニューラルネットのようにベクトル計算が必須になるようです…
今後の展開
高速化
今回はベクトル演算の部分をSIMD使って少しだけ高速化しました。本格的に高速化するにはGPU使うのが筋だと思います。しかし木構造の宿命で、ベクトル演算とベクトル演算の間にif文が入るため普通のグラボではオーバーヘッドが大きいかもしれません。（最近のはデータ転送が爆速になってて問題なかったりして...）
なので、もしかしたらJetsonのようなCPUとGPUが同じ石の上にあるアーキテクチャ使う方が効率高い可能性はあります。（どうせクエリーにランダム性を持たせたいのでINT8で丸っと計算しても問題ないかも？）
LLMへの適用
やはり一丁目一番地はここでしょう。今回のアルゴリズムを回帰に拡張しその延長で解くとか？ 強引に次のトークンをダイレクトに予測するとか？？ どうにかしてLLMへの横展開が出来ないかなぁ～
正直、機械学習界隈の第一線を退いて久しいためtransformerの学習さえしたこともなく、これは希望的観測に過ぎません。立ちはだかる壁がどれ程の高さかも知らずに無責任に言ってます。しかし冒頭にも述べたように、このまま指をくわえて生成AIの進化を見守るのは悔しいじゃありませんか⁉️ もし、このアルゴリズムにインスパイアされた優秀な方がいらっしゃったら、是非チャレンジしてみて下さい‼️
ホントに新しいか？問題
前述の通りパターン認識の最新研究に疎いので、ここで開示したアルゴリズムは、もしかしたら既に誰かが発表してる内容かもしれません。「そんなの既に○○さんがやってるよ！」というツッコミ大歓迎です。コメント欄にお願いします。
もし本当に新しいなら、研究会発表とかでベンチマークテストぐらい発表出来るんじゃないかな？ご興味のある学生さんいらっしゃったら是非トライしてみて下さい。
ソースはMITライセンスですので、煮るなり焼くなりやりたい放題ですw アルゴリズムのいろんなバリエーションもすぐ思いつくでしょう（AIに相談してもいいし...）
もしこんなの出来た❗️という方がいらっしゃったらコメント欄に書いて下さると幸いです。