Processing math: 0%

2012/02/20

Processingで魔法使いの組分け帽子を作る

今日はちょっとしたパターン認識をやってみようと思います。あ、タイトルは釣りですよ。

とりあえずデモ動画をご覧ください。



こんな感じで、ある「特徴」を手掛かりにして正体をつきとめる処理は「パターン認識」と呼ばれており、文字認識などに応用されている技術です。

現在に至るまで、様々な認識手法（というか識別手法）が提案されていますが、今日はフィードフォワード型のニューラルネットワーク（3層パーセプトロン）にフォーカスを当てたいと思います。


【ニューラルネットワークの構成】

ここでは、ニューラルネットワークの理論的背景について、石井 健一郎ほか著『わかりやすいパターン認識』の 3 章に準拠して解説したいと思います。前提知識として、「パターン認識とは何か」という根本的な理解と、単純パーセプトロンを実装できる程度の能力があるとよいと思います。

まず、ニューロンと呼ばれる神経細胞の働きを、以下に示す閾値論理ユニットでモデル化します。これは、適当なウェイト \vect{w} = \left( w_0,\,\cdots,\,w_d\right)^t によって重みづけした入力信号 \vect{x} = \left(x_0,\,\cdots,\,x_d\right)^t の総和を基に、閾値処理を行う単純な仕組みです。出力 g_i(\vect{x}) は 0 か 1 となります。

閾値論理ユニット

ニューラルネットワークは、複数の閾値論理ユニット（以下、ユニット）を含む層を、入力層から出力層まで多数並べたネットワークの事です。各ユニットは隣接する層とだけで結合しており、かつ入力層から出力層へ向かう一方向のネットワーク構成です（下図参照）。


ニューラルネットワークのある層における j 番目のユニットに注目し、これをユニット j と呼ぶ事にします。また、ユニット j の1階層前の i 番目のユニットをユニット i、1階層後ろの k 番目のユニットをユニット k と呼び、さらにユニット i からユニット j への結合の重みを w_{ij}、ユニット j からユニット k への結合の重みを w_{jk} で表します。

ここで、ネットワークにある学習パターン \vect{x}_p を入力したとき、ユニット i からの出力を g_{ip}、ユニット j への入力を h_{jp} とすると、h_{jp} は j に結合している1階層前の層内のユニットからの出力の重み付き信号の総和、つまり
\begin{align} h_{jp}=\sum_{i}w_{ij}g_{ip} \end{align}となります。

ユニット j の出力 g_{jp} は閾値関数 f_j を用いて
\begin{align} g_{jp}=f_j(h_{jp}) \end{align}と表すものとします。


【誤差の定式化と重みの更新】

ニューラルネットワークを構築したら、理想的な識別結果が既知の入力データを用いて学習（重みの調整）を行う必要があります。

ある学習パターン \vect{x}_p に対する二乗誤差は、出力層のユニット l の出力 g_{lp} と、ユニット l に対する教師信号（理想的な識別結果）を b_{lp} を用いて、以下のように表す事ができます。
\begin{align} J_p = \frac{1}{2}\sum_l \left( g_{lp} - b_{lp} \right)^2 \end{align}従って、全学習パターンに対する二乗誤差 J は
\begin{align} J=\sum_p J_p \end{align}となります。

識別性能を高めるためには、この誤差 J を最小化するようにユニット間の重みを調整する必要があります。つまり、ある重み w_{ij} に対して、以下の更新式を適用する事になります。
\begin{align} w'_{ij} &= w_{ij} - \rho \frac{\partial J_p}{\partial w_{ij}} \\ &= w_{ij} - \rho \underbrace{ \frac{\partial J_p}{\partial h_{jp}}}_{\varepsilon_{jp}} \cdot \underbrace{\frac{\partial h_{jp}}{\partial w_{ij}}}_{g_{ip}} \\ &= w_{ij} - \rho \varepsilon_{jp}g_{ip} \end{align}ここで \rho を学習係数と呼び、任意の正定数とします。

また、上式右辺の \varepsilon_{jp} は、合成関数の微分を用いて以下のように式変形できます。
\begin{align} \varepsilon_{jp} &= \frac{\partial J_p}{\partial h_{jp}} = \frac{\partial J_p}{\partial g_{jp}} \cdot \frac{\partial g_{jp}}{\partial h_{jp}} \\ &= \frac{\partial J_p}{\partial g_{jp}} \cdot f'_j(h_{jp}) \end{align}なお、上式中の \dfrac{\partial J_p}{\partial g_{jp}} は、ユニット j が中間層か出力層かで以下のように場合分けされます。
\begin{align} \frac{\partial J_p}{\partial g_{jp}} = \begin{cases} g_{jp} - b_{jp} & \textrm{（出力層）} \\ \sum_{k}\varepsilon_{kp}w_{jk} & \textrm{（中間層）} \end{cases} \end{align}

【閾値関数の選定】

最後に、閾値関数 f_j を考えます。ここまでの議論で、この関数が微分可能でなければならない事にはお気付きでしょう。

通常、f_j には以下のようなシグモイド関数 S(u) が選ばれます。
\begin{align} S(u) = \frac{1}{1 + \exp(-u)} \end{align}
この関数は、微分すると S'(u) = S(u)\left( 1 - S(u)\right) になりますから、f'_j は
\begin{align} f'_j (h_{jp}) = g_{jp} (1 - g_{jp}) \end{align}となります。

以上を整理すると、\varepsilon_{jp} に関する再帰式を以下のように得る事ができます。
\begin{align} \varepsilon_{jp} = \begin{cases} \left( g_{jp} - b_{jp} \right) g_{jp} \left( 1 - g_{jp} \right) & \textrm{（出力層）} \\ \left( \sum_k \varepsilon_{kp} w_{jk} \right) g_{jp} \left( 1 - g_{jp} \right) & \textrm{（中間層）} \end{cases} \end{align}上式において、0 < g_{jp} \left( 1 - g_{jp} \right) < 1 であり、ユニットの出力値 g_{jp} が 0.5 のときに重みの修正量が最も大きく、0 か 1 に近づくほど修正量が小さくなります。

学習パターンが入力されると出力層で各ユニットの出力と教師信号の誤差が計算され、それに基づいて \varepsilon_{jp} が求められ、出力層での重みの修正が行われます。

この結果によって、1つ前の階層でも重みの修正が行われます。これを同様に繰り返す事で、すべての層で重みが修正されます。 このように、出力層から入力層に向かって誤差を伝播させる学習こそが、誤差逆伝播法と呼ばれる所以です。


【実装】

3層から成るフィードフォワード型ニューラルネットワークの実装は以下の通りです。こちらも、David M.Bourg, Glenn Seemann 著『ゲーム開発者のための AI 入門』を参考にしました（そこそこ長いので展開してご覧ください）。

で、使い方はこんな感じです。

view plainprint?
  1. // --------------------------------------  
  2. // ======================================  
  3. // ニューラルネットワークを用いた  
  4. //                  2クラス識別のサンプル  
  5. // ======================================  
  6. // --------------------------------------  
  7.   
  8. // NeuralNetworkオブジェクトを宣言  
  9. NeuralNetwork theBrain;  
  10.   
  11. // 学習用データセット  
  12. List<PVector> class1;  
  13. List<PVector> class2;  
  14.   
  15. void setup() {  
  16.   size(400, 300);  
  17.     
  18.   // ======================================  
  19.   // 学習用データ（教師信号）のセットアップ  
  20.   // ======================================  
  21.   class1 = new ArrayList<PVector>();  
  22.   class2 = new ArrayList<PVector>();  
  23.     
  24.   for(int i = 0; i < 10; i++) {  
  25.     class1.add(new PVector(random(width / 2),        random(height)));  
  26.     class2.add(new PVector(random(width / 2, width), random(height)));  
  27.   }  
  28.     
  29.     
  30.   // ======================================  
  31.   // ニューラルネットワークのセットアップ  
  32.   // ======================================  
  33.   theBrain = new NeuralNetwork();  
  34.     
  35.   // 入力層、隠れ層、出力層の数をそれぞれ指定  
  36.   theBrain.initialize(2, 10, 3);  
  37.     
  38.   // 学習係数を0.2に設定  
  39.   theBrain.setLearningRate(0.2);  
  40.     
  41.   // 局所解回避のためのモーメンタムを使用  
  42.   theBrain.setMomentum(true, 0.9);  
  43.     
  44.   // ======================================  
  45.   // 学習  
  46.   // ======================================  
  47.   double error = 1;  
  48.   long c = 0;  
  49.   
  50.   // 収束するか、一定の回数に達するまで反復  
  51.   while((error > 0.01) && (c < 50000)) {  
  52.     error = 0;  
  53.     c++;  
  54.   
  55.     // ------------------------------------  
  56.     // クラス1の学習  
  57.     // ------------------------------------  
  58.     for(int i = 0; i < class1.size(); i++) {  
  59.       // 入力層に、インデックスとデータの組を与える  
  60.       // ※ データは必ず 0 ～ 1 の範囲  
  61.       theBrain.setInput(0, (float)class1.get(i).x / width);  
  62.       theBrain.setInput(1, (float)class1.get(i).y / height);  
  63.         
  64.       // 出力層に、インデックスとデータの組を与える  
  65.       // ※ シグモイド関数を使用しているため、  
  66.       //      0.1 → 不活性  
  67.       //      0.9 → 活性  
  68.       //    となるようにデータを与える  
  69.       theBrain.setDesiredOutput(0, 0.9);  
  70.       theBrain.setDesiredOutput(1, 0.1);  
  71.         
  72.       // 誤差の計算  
  73.       theBrain.feedForward();  
  74.       error += theBrain.calculateError();  
  75.         
  76.       // 誤差逆伝播  
  77.       theBrain.backPropagate();  
  78.     }  
  79.       
  80.     // ------------------------------------  
  81.     // クラス2の学習  
  82.     // ------------------------------------  
  83.     for(int i = 0; i < class2.size(); i++) {  
  84.       theBrain.setInput(0, (float)class2.get(i).x / width);  
  85.       theBrain.setInput(1, (float)class2.get(i).y / height);  
  86.         
  87.       theBrain.setDesiredOutput(0, 0.1);  
  88.       theBrain.setDesiredOutput(1, 0.9);  
  89.         
  90.       theBrain.feedForward();  
  91.       error += theBrain.calculateError();  
  92.       theBrain.backPropagate();  
  93.     }  
  94.       
  95.     // 誤差の平均化  
  96.     error = error / (float)(class1.size() + class2.size());  
  97.   }    
  98. }  
  99.   
  100.   
  101. void draw() {  
  102.   background(0);  
  103.     
  104.   // ======================================  
  105.   // 識別境界の視覚化  
  106.   // ======================================  
  107.   for(int i = 0; i < width; i++) {  
  108.     for(int j = 0; j < height; j++) {  
  109.         
  110.       // ------------------------------------  
  111.       // データ入力と識別  
  112.       // ------------------------------------  
  113.       theBrain.setInput(0, (float)i / width);  
  114.       theBrain.setInput(1, (float)j / height);  
  115.       theBrain.feedForward();  
  116.         
  117.       // 識別結果の取得  
  118.       int ret = theBrain.getMaxOutputID();  
  119.         
  120.       if(ret == 0)      stroke(0xFFFF7F7F);  // クラス1の場合  
  121.       else if(ret == 1) stroke(0xFF7F7FFF);  // クラス2の場合  
  122.         
  123.       // 識別境界の表示  
  124.       point(i, j);  
  125.     }  
  126.   }  
  127.     
  128.   // 学習データの表示  
  129.   pushStyle();  
  130.   strokeWeight(3);  
  131.     
  132.   stroke(0xFFFF0000);  
  133.   for(PVector c1 : class1) point(c1.x, c1.y);  
  134.   
  135.   stroke(0xFF0000FF);  
  136.   for(PVector c2 : class2) point(c2.x, c2.y);  
  137.   
  138.   popStyle();  
  139. }  
時刻: 23:44
ラベル: , ,

0 件のコメント:

コメントを投稿

ひとことどうぞφ(・ω・,,)

登録: コメントの投稿 (Atom)