にゅーろえぼりゅーしょん

22 Dec 2018

この記事は IQ1の2まいめっ Advent Calender 2018 の21日目の記事です．間に合いました（ハワイ時間）．

TL;DR

みんな大好き ANN（Artificial Neural Network）の話
ANN の学習って実数値最適化問題でしょ → 進化計算で最適化できるよね
ANN の構造に依存しない → CNN だろうが RNN だろうが関係なし（強い！）
勾配計算に依存しない → 微分できなくても学習できる（強い！）
IQ が 1 なので実装はない（頭が弱い…）
機械学習界の公用語 C++ で書かれたライブラリがあるから実装はすぐできそう

What’s Neuroevolution

Neuroevolution（ニューロエボリューション）は，’Neuro’ + ‘evolution’の意味で，’Neuro’ = Aritificial Neural Network（ANN）， ‘evolution’ = Evolutionary Algorithm（進化計算・進化アルゴリズム）をそれぞれ表しています．

読んで字のごとく， ANN の学習に Evolutionary Algorithm を使いましょうという話です．

Artificial Neural Networkの学習

ANN は IQ1 でもわかる人類の基礎知識なので，詳しいことは書きません．

重要なことは， ANN はあるパラメータセット \( \mathbf{w} \in \mathbb{R}^k \) が与えられた時に，入力 \( \mathbf{x} \in \mathbb{R}^n \)，出力 \( \mathbf{y} \in \mathbb{R}^m \) に対し，以下の関係式を満たす関数 \( f \) と捉えることができるでしょ？ということです．（乱暴）

\[ \mathbf{y} = f(\mathbf{x}; \mathbf{w}) \]

なお，ここではパラメータセット \( \mathbf{w} \) をベクトルのように表記していますが，実際には行列だったりすることが多いでしょう．また次元 \( k \) は，入力次元 \( n \) および出力次元 \( m \)，ANN自体の構造などに依存します．

通常のANNの学習では，学習のために対応のとれた入力 \( \mathbf{x} \) と出力 \( \mathbf{y} \) に関する教師データを用意し，すべての教師データを十分に説明でき，かつ未知のデータに対する汎化性を持つようパラメータセット \( \mathbf{w} \) を決定します．（教師あり学習）

一般には，単純に入力 \( \mathbf{x} \) を入れた時の出力 \( \mathbf{y}\prime \) を計算し，\( \mathbf{y} \) と \( \mathbf{y}\prime \) の誤差（＋正則化項）を最小化するよう誤差逆伝播法（バックプロパゲーション）を用いて \( \mathbf{w} \) を最適化する方法がとられます．また，同様の仕組みを用いて，環境から得られる報酬を近似することで最適行動などを獲得する強化学習の方法 (Q-Network) も考案されています．

こうしたANNの学習では，\( \mathbf{w} \) の改善のため勾配を計算する必要があります．したがって，微分できない構造を持っていると，原理的に学習が困難になります．また，リカレントニューラルネットワーク（Reccurent Neural Neuwork; RNN）のための Backpropagation through time といった方法も考案されていますが，学習は可能だが難しいといったケースも多いのが実情かと思います．

Neuroevolution による ANN の学習は，概念的には強化学習の枠組みに入るのかもしれませんが，かなり違ったスタイルの学習方法になります．

上述の通り ANN は単なる実数空間上の関数なので，なにかしらパラメータセット \( \mathbf{w} \) を与えれば入力 \( \mathbf{x} \) に対して出力 \( \mathbf{y} \) を計算することができます．出力の計算ができるということは，その計算の良さ，すなわち設定した \( \mathbf{w} \) の良さ（適切さ）を評価する方法さえあれば，適当な \( \mathbf{w} \) を試行錯誤を通じて探索することができます．

計算の良さを評価する評価関数は，問題依存で決定されます．例えば教師あり学習が扱う回帰問題や分類問題では，誤差や正答率を直接使うことができるでしょう．強化学習のような問題では，生成されるアクション系列（行動）の良さがそのまま計算の良さになります．

評価関数が決まれば \( \mathbf{w} \) の良さを評価できるため，極端な話ランダムに \( \mathbf{w} \) を五千兆個生成し，一番良いものを使うようなランダム探索ですら ANN を学習できます．とはいえ，お察しの通りランダム探索では非常に低確率でしか良い \( \mathbf{w} \) を発見できません．特に ANN はパラメータセットの次元が大きくなりがちなので，最適解を得る確率は限りなく 0 に近いでしょう．

実数値最適化の手法は数多く提案されていますが，特にこの次元が大きくなるという性質から厳密解法の適用は難しいというのが事実です．そこで多くの研究では近似解法を用いて \( \mathbf{w} \) の最適化を行なっており，Neuroevolution はそういった中でも特に Evolutionary Algorithm を使う方法論となります．

Evolutionary Algorithms

進化計算は，生物の進化過程にヒントを得た最適化手法で，一般に Population-based なメタ解法の一種とされます．なお，同様の Population-based な実数値最適化手法である粒子群最適化法 (Particle Swarm Optimisation; PSO) を使うこともありますが， PSO は厳密には Evolutionary Algorithm ではないため，査読者に怒られます．（本当に）

基本的な枠組みとしては，複数のパラメータセットを生成・評価し，それらの組み替え，変更を通じてより良い \( \mathbf{w} \) を探します．

進化計算の代表的な手法として，組合せ最適化問題などにも適用できる遺伝的アルゴリズム (Genetic Algorithm; GA) が有名だと思います．実数値最適化問題においては，進化戦略 (Evolutionary Strategy; ES) の有効性も広く知られています．

Genetic Algorithm (GA)

GA はダーウィン的進化論をモデル化した最適化手法です．

解候補を遺伝子からなる個体とみなし，個体同士の交叉，遺伝子の突然変異，個体の適応度（評価値）に基づく選択・淘汰と呼ばれる遺伝操作を繰り返し適用することで，より良い個体，すなわち解を得る方法になります．

機械学習の分野におけるデファクトスタンダード言語である C++ で実装された GAlib などのライブラリが公開されており，気軽に試してみることができます．

ANN を GA によって最適化する場合，経験的に交叉は使用しない場合が多いです．というのも，交叉は個体の部分遺伝子列を保存しながら他の個体の部分遺伝子列を取り込むことで複数個体の性質を混ぜ合わせる効果を持つ遺伝操作なのですが， ANN の構造を部分的に保存するような交叉オペレータの定義は難しく，突然変異と選択のみで改善する方が効率的な場合が多いためです．

Evolutionary Strategy (ES)

ES は GA と似ていますが，主に適応的突然変異と決定論的選択の繰り返しに基づく実数値最適化手法です．（交叉に似た組み替え操作も含みますが，主に適応的変化のために他の個体の情報も使う程度の印象が強い（あくまで個人の印象です））

適応的突然変異は，GAにおいて用いられる突然変異と似ていますが，探索に関するパラメータを導入し，変異方向および変異量を適応的に調整することで効果的な突然変異を起こすよう改良された突然変異モデルになります．

例えば自己適応進化戦略では，突然変異の戦略パラメータ \( \sigma_i \) と解 \( \mathbf{x}_i \) のペアとして個体 \( \mathbf{a}_i = (\sigma_i, \mathbf{x}_i) \)を表現し，以下の式にしたがって個体の更新を進めます．

\[\begin{aligned} \sigma_i &\leftarrow \langle \sigma \rangle e^{\alpha N_i(0, 1)}\\ \mathbf{x}_i &\leftarrow \langle \mathbf{x} \rangle \sigma_i \mathbf{N_i(0, I)} \end{aligned}\]

ここで，\( \langle * \rangle \) は最善な \( \mu \) 個の個体が持つ \( * \) の算術平均，\( N_i(0, 1) \) は平均 0, 分散 1 の正規分布に従う乱数，\( \alpha \) は学習率を表します．（書いていて思いましたが，解自体は変異というより再生成に近いですね）

また，自己適応進化戦略では突然変異の方向，変量を自身の持つパラメータに応じて決定しますが，これを個体群の分散共分散行列から適応的に生成する CMA-ES (Covariance Matrix Adaptation-ES) と呼ばれる方法も提案されています．個体群の更新に記述が面倒な統計処理を挟むため説明は省略しますが，実数値を扱う進化計算手法としては非常に性能が良いとされています．

実際に， Neuroevolution を行う際にはぶっちゃけ CMA-ES を使っておけばいい程度に性能がよく，とりあえずの入門としては libcmaes を使うのがたぶん一番早いと思います．こちらも C++ で実装されていますが，どういうわけかPyなんとかというよく知らない言語のバインディングもついているようです．まぁ機械学習強者の皆様は当然 C++ をお使いのことと思いますので，あまり関係がありませんね．

NEAT（にーと）

私の職業です．

さて，ここまで結合荷重あるいはバイアスを最適化することを暗に意図して ANN の学習を実数値最適化問題として扱ってきたわけですが，実際に ANN を構成するパラメータは他にもあります．

そうです，結合構造（トポロジ）です．

実は，進化計算の中でも特に遺伝的アルゴリズムを用いて ANN の結合構造まで最適化する方法があります． Kenneth O. Stanley 先生が発表したトポロジを含む ANN の進化的獲得手法， NEAT (Neuroevolution through Augmenting Topology) です．

残念ながら IQ が 1 なので詳細を説明する気力も能力もありませんが，気になる方は読んでください．

まとめ

Neuroevolution は， ANN の学習を Evolutionary Algorithms を用いた最適化により実現する方法です．特にロボットの制御に関する研究では，制御器として ANN を使用し，シミュレーションを通じた行動評価から制御器を進化的に獲得する進化ロボティクス（Evolutionary Robotics）と呼ばれる分野も存在します．制御器の決定的振る舞いだけで学習を進めることができるため，マルコフ性を満たさないことが多い複数ロボットの同時学習にも適用することができ，群行動の創発などといった人工生命との関わりが大きな範囲において頻繁に用いられる手法となっています．

最近では CNN や DNN を進化的に獲得し，既存手法より高い精度を得ようとする研究も盛んに行われています．もちろん，バックプロパゲーションのような勾配ベースの手法の方が良い場合も多くありますが，強化学習との比較では相当拮抗した性能を出すことも多いようです．（何事も一番良い手法というのは難しいものですね．）

進化計算は記事中でも紹介したように最適化機能がライブラリとして公開されている場合も多く，使い勝手といった面も悪くはないでしょう． ANN の実装も，途中計算を保存する必要は基本的にないので，割と簡素なもので良いのも特徴です．

非常に雑な要約記事でしたが， Neuroevolution の味わいが伝わって欲しいっぽい… みんなも Let’s try neuroevolution! っぽい！