高校数学を使って誤差逆伝播を”再発見”できるAutoML-zero
この記事について
この記事はGoogle Brain/Google Researchから発表されたAutoML-zero: Evolving Machine Learning Algorithms From Scratch[1]の解説です。
この論文の要点をまとめると以下のようになります。
- 既存のNASのように人手で作ったものの組み合わせを探索するのとは異なり、可能な限り人の介在によるバイアスを防ぐ。そのため、高校数学レベルの簡単な変換の組み合わせを進化的アルゴリズムで探索させる。
- 進化的アルゴリズムを使って、それらの最適な組み合わせを探索する。
- 学習させると誤差逆伝播や学習率減衰、勾配の規格化等を再発見できる。
Neural Architecture Search とは
Neural Architecture Searchはニューラルネットでよく行われるAutoMLの１つで、ニューラルネットの最適なネットワーク構造探索を行います。Google Brainが発表したNASNet[2]を皮切りに多くの研究がなされるようになりました。
NASNetでは、Reduction CellとNormal Cellという２つの基本セルでネットワーク構造を構成し、それらのセルの内部構造を強化学習で探索します。
セルの内部構造は、1つ層を飛ばしてネットワークを結合するSkip ConnectionやPooling、Convolution等の操作が複雑に組み合わさっています。これらのOperationは以下の人手で設定された一覧から強化学習を使って選択されます。
簡単に強化学習(PPO[4])を使ったセル構造決定方法を解説します。図で表すと以下の図のとおりです。まずController RNNというネットワークが逐次的にセル内部の処理を出力します。
セル中の１つの枝は5つの選択で成り立っています。まず、最初に2つの入力をどこからとってくるかを選びます(灰色)。次にそれらに適用する7x7 MaxPoolingなどOperationを上記のテーブルから選択します(黄色)。そして２つの処理の組み合わせを要素毎の足し合わせか行列の結合、どちらかから選択します(緑)。これらの５つの選択が１つの分岐中にB個ある（NASNetではB=５）ので、5xBの時系列の出力をController RNNが行いながら、強化学習でどの操作を選択するかController RNNを学習させるという要領です。
NASNetで使われている強化学習の代わりに進化的アルゴリズムを使うこともでき[3]、NASNetと同じようにネットワーク構造を探索する問題設定で、トーナメント形式の進化的アルゴリズムを改良したRegularized Evolutionという手法が提案されています。Regularized Evolutionでは、同じ世代で一番よかったものを変異させて新しい遺伝子を作る一方、一番古いものを削除します。同じ計算資源だと、強化学習やランダム探索を上回ったと報告しています。
他にも、1GPUを使って半日程度でNASNetと同等の結果を出せるENAS[5]や微分可能にすることで強化学習を使わないDARTS[6]など様々な発展研究が発表されています。
AutoML-zero
AutoML-zeroはNASと異なり、可能な限り人の介在によるバイアスを減らして最適なアルゴリズムを”開発”させるというアルゴリズムです。SOTAの精度には及びませんが、ゼロから２層ニューラルネットの誤差逆伝播を初めとして、今日我々が使っている様々な学習テクニックを開発することができます。
Key Insight and Method
この論文の重要な点は下記の３つです。
- トーナメント形式でアルゴリズムを進化させ、古いものを徐々に捨てて更新する進化戦略、Regularization Evolutionを使用
- 人の介在バイアスを減らすため、高校数学レベルの簡単な変換の組み合わせのみでアルゴリズムを作る
- 多くのアルゴリズムを評価するため、データセットをそのまま使わずに小さなタスクに分けてアルゴリズムを評価する
Regularization Evolution
進化戦略で機械学習アルゴリズムを生成・改善していくのですが、まず機械学習アルゴリズム初期化を担うSetup関数、変数を学習させるLearn関数、Forward pass(予測)をするPredict関数の３つに分割します。
Setup, Predict, Learnの例を、アルゴリズム探索の結果発見した二層ニューラルネットの機械学習アルゴリズムで示します。s0は正解ラベル、s1は予測ラベル、v0は入力データで、それ以外は進化的アルゴリズムによって変数が追加されたものです。
Setup関数は機械学習アルゴリズムの変数の初期化を行う関数で、下の例では層の重みと学習率を定義し、初期値を割り当てています。Predict関数は特徴量v0を入力として二層ニューラルネットで順伝播をさせて出力s1を得ています。Learn関数は誤差逆伝播で、アルゴリズム(二層ニューラルネット)の重みパラメータを更新しています。
AutoML-zeroではRegularization Evoluationを使っているので、以下の手順でアルゴリズムを更新していきます。まず、一番古いアルゴリズムを削除します(step1)。次にアルゴリズムを評価して一番いいものを選びます(step2)。次に一番いいものをコピーして、変異(mutate)させて新しいアルゴリズムを作ります。(step3, step4)
変異させるときは以下の３タイプの変異を行います(下図)。
- Type(i) : 新しい変換を挿入
- Type(ii) : 関数をランダム化に変える
- Type(iii) : 変数を入れ替える
人の介在バイアスを防ぐ
NASNetは経験的に良い操作の組み合わせを探索させます。下の表はNASNet[2]の探索空間で、3x3 Conv、depthwise-convなど論文で良く見る操作が並んでいます。これに対して、AutoML-zeroはこのような人間の仮定を排除するというコンセプトで作られています。
そのため、あまり高等な変換は用いず、高校数学レベルの変換のみを使用して、それらの組み合わせのみで機械学習アルゴリズムを構成します。基礎的な算数、三角関数、線形変換などです。
小さなタスクに分ける
AutoML-zeroでは進化的アルゴリズムを使って膨大な数のアルゴリズムを評価するため、全てのアルゴリズム全データセット全てを使って評価はできません。分散処理等で高速化はしていますが、それでもデータセット全てを使うことは現実的ではないので、データセットを小さな”タスク”に分割してアルゴリズムの評価を行なっています。
まず全データセットから”タスク”を作り、それをアルゴリズム探索用のT_searchと、良かったものを評価するT_selectにわけます。さらにそれぞれの中でtrain,validationに分けてアルゴリズムの学習・評価を行うという仕組みです。例えば、CIFAR10を元に２値分類させるというタスクを考え得る場合、まず各クラスを２つ選んでそれらを分類するというタスクを45個作り、そのうち36ペアをT_search、残り9ペアをT_selectにします。CIFAR10は32x32x3のデータなので、そのまま扱うと次元数が多いです。そこで100個のランダムベクトルで射影させて事前削減をすることで、合計4500個の小タスクができる。(T_search:3600, T_select:900)。それぞれのタスクには、10000個のデータが所属しているのでそれらをtrain:valid=8000:2000に分割し、データセットを作ります。
アルゴリズムの学習と評価
T_searchに所属するタスクの中から複数のタスクを選んで、その中でアルゴリズムの評価・変異をさせていきます。AutoML-zeroではRegularization Evolutionに従って評価した結果良かったアルゴリズムを次世代の親アルゴリズムとして変異させて子アルゴリズムを作る、という手順を繰り返してアルゴリズムを改善していきます。それぞれのアルゴリズムは下図のEvaluationという関数を使って学習と評価を行っていきます。
Evaluation関数の中には学習データDtrain,評価データDvalidのほかに、進化的アルゴリズムで改善対象になっているSetup, Predict, Learn関数が引数になっています。まず、setup関数でアルゴリズムを初期化し、Dtrainを使って学習させます。Evaluate関数中央あたりにあるNormalize関数はsigmoid関数やsoftmax関数の値域(-∞、∞)のスカラーを[0,1]にする関数です。そして、Dvalidを使って損失を計算して、その平均をそのアルゴリズムの評価値とする、というものになっています。
結果
では、AutoML-zeroがどのようなアルゴリズムを探索し、どの程度の精度がでるのかを見てみます。
ランダム探索との比較
まず、単純な線形回帰問題におけるランダム探索と進化的アルゴリズムRegularized Evolutionの比較結果をみてみます。ランダム探索は、AutoML-zeroのRegularized Evolutionによるアルゴリズム生成をランダム生成に変更したもです。
比較対象のタスクはLinear, Affineの２つです。Linearはy=ax, Affineはy=ax+bで生成された入力・正解データから、人手で作ったReferenceアルゴリズムの精度を超えるアルゴリズムを探索させる問題です。ランダム探索と進化的アルゴリズムを比較したのが下の図です。
task difficulty は、” 人が作ったReferenceアルゴリズムを超えた探索アルゴリズムの数 / ランダム探索の探索空間 “ で、成功するアルゴリズムの出現確率のようなものを表しています。結果を見ると、タスクが難しくなるほど進化的アルゴリズムがランダム探索より効果的にアルゴリズムを探索できていることがわかります。
次に非線形回帰を考えるため、ランダムに初期化したニューラルネットを使った入出力ペアをデータにします。そうすると、ランダム探索ではReferenceアルゴリズムの性能を超えるアルゴリズムを発見できませんでした。しかし進化的アルゴリズムでは、ニューラルネットの順伝播だけでなく誤差逆伝播を使って学習させる方法まで”再発見”できています。
再掲になりますが、再発見したアルゴリズムが下図のものです。
Binary CIFAR10
前述したBinary CIFAR10で学習させると、今日我々が知っている色々なテクニックを再発見してくれます。学習の過程をあわらしたのが下図です。
最終的に”発見”されたアルゴリズムはweight Averagingなどのテクニックを使った手法になっています。このアルゴリズムをvalidationデータとランダム探索を使って微調整し、T_searchやT_selectにも使っていないCIFAR10のテストデータで評価すると制度は84.06±0.10%という結果。これは人がデザインした2層ニューラルネットを超える結果です
他のデータセットで評価しても２層ニューラルネットを超えるアルゴリズムを発見できています
まとめ
AutoML-zeroは人間の介在によるバイアスを極限まで減らすという新しいAutoMLの取り組みをしています。精度はまだそこまで高くないですが、探索空間の改善やGPUの進化で、研究が進めば人間が発見できていない有望なアルゴリズムが発見されるかもしれません。
Reference
- Esteban Real, Chen Liang, David R. So, Quoc V. Le. AutoML-Zero: Evolving Machine Learning Algorithms From Scratch. arXiv:2003.03384 (2020)
- Zoph, B., Vasudevan, V., Shlens, J., and Le, Q. V. Learning transferable architectures for scalable image recognition. CVPR2018.
- Real, E., Aggarwal, A., Huang, Y., and Le, Q. V. Regularized evolution for image classifier architecture search. AAAI, 2019.
- J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
- Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, Jeff Dean. Efficient Neural Architecture Search via Parameter Sharing. arXiv preprint arXiv:1802.03268, 2018.
- Hanxiao Liu, Karen Simonyan, Yiming Yang. DARTS: Differentiable Architecture Search. arXiv preprint arXiv:1806.09055, 2018.
