Perceptron の実装とか見ると、ものすごく簡単なので、本当にこれで学習できちゃうの？ と不安になってしまいました(苦笑)。
こういうときは、実際にパーセプトロンが計算しているとおりに、紙と鉛筆で計算してみて、期待する結果が出てくることを確認してみたくなります。
参照する教科書は「パターン認識と機械学習・上」(PRML) の「 4.1.7 パーセプトロンアルゴリズム」。
短い節です。必要最低限のことを一通り書いてある感じかな。
計算に用いるサンプルですが、手で計算できる規模でないといけないので、論理演算の AND を試してみることにします。
簡単に勉強
ちゃんとした説明は PRML などを見て欲しいですが、とても簡単にまとめます。
２値の線形識別モデルは、N 次元空間内を (N-1) 次元の超平面(決定面)で分割することで、入力ベクトル x から得られる特徴ベクトル φ(x) が２つのクラスのどちらに属するかを分類します(２次元で言えば、座標平面を直線で分割している感じ)。
その超平面は重みベクトル w を使って、 w^T φ(x) = 0 と表します。
空間を w^T φ(x) ≧ 0 と w^T φ(x) < 0 に分割するわけですね。
重みベクトル w を決定する一般的なアプローチは、誤差関数を決め、それを w の関数と見なし、最小化する w を求める、となります。
パーセプトロンは、誤差関数としてパーセプトロン基準を用い、また最小化に確率的最急降下アルゴリズムを用いるのが特徴、と。
パーセプトロン基準は、目的変数として t ∈ {-1, +1} を用いつつ(通常は {0, 1})、誤差関数を次のように定義しています。
E_P(w) = - Σ w^T Φ(x_n) t_n
ここで Σは誤分類されたパターン全体を走るとします。
すると、w^T Φ(x_n) ≧ 0 のとき t_n は「間違って」 -1 になっているし、w^T Φ(x_n) < 0 のときは t_n は「間違って」 +1 になっているため、E_P(w) は常に０以上であることがわかります。
これを最小化するために、「誤分類された x_n １つずつに対して」次の式を使って逐次的に最小値に近づけていきます。
イメージとしては、ニュートン法(多次元版)って感じです。
このあたり、PRML には 3.1.3 節を見ろ、と書いてますが、5.2.4 節もあわせて見るといいかもしれません。
w^(γ+1) = w^(γ) - η▽E_P(w) = w^(γ) + φ(x_n) t_n
ややこしそうに書いてますが、アバウトにぶっちゃけると「ハズレのときは、そのハズレが出てしまった特徴ベクトルを重みベクトルに足すか引くかする」ということです。
こんな方法では最小値に本当に近づくのかどうか必ずしもわからないんですが、「解が存在する場合は」この計算を有限回繰り返すことで解が得られます、というのが「パーセプトロンの収束定理」で、Perceptron のキモです。
ね、ほんとにそんなんでうまく学習できるんですか？ という気になるでしょう。
手で計算してみる
論理演算 AND とは……は、さすがに略。
AND の入力ベクトルと目的変数は次のようになります(ベクトルは転置した状態で記述します)。
x_0 = (0, 0), t_0 = -1 x_1 = (1, 0), t_1 = -1 x_2 = (0, 1), t_2 = -1 x_3 = (1, 1), t_3 = +1
これを学習できるのか、手で計算してみましょう。
特徴関数 φ は x_n そのままでもいいんですが、「φ_0 はバイアスでしょ、jk」と PRML にもあるので、次のように定義します。
φ( x_0 ) = (1, 0, 0) φ( x_1 ) = (1, 1, 0) φ( x_2 ) = (1, 0, 1) φ( x_3 ) = (1, 1, 1)
これより重みベクトル w も３次元、初期値は w^(0) = (0, 0, 0) となります。
さて、ここから計算していきますが、誤分類ベクトルは本来ランダムに選ぶべきところ、ここでは少々恣意的に選んでいくことにします(理由は後述)。
■Step 1
x_0 は w^T Φ(x_0) = 0 ≧ 0 となり t_0 = -1 と合致しません。
よって、「次の w 」は次の式で求まります。
w^(1) = w^(0) + φ(x_0) t_0 = (0, 0, 0) - (1, 0, 0) = (-1, 0, 0)
ますます不安……この調子で大丈夫？
■Step 2
x_3 は w^T Φ(x_3) = -1 + 0 + 0 < 0 となり t_3 = +1 と合致しません。よってw^(2) = w^(1) + φ(x_3) t_3 = (-1, 0, 0) + (1, 1, 1) = (0, 1, 1)
■Step 3
x_1 は w^T Φ(x_1) = 0 + 1 + 0 ≧ 0 となり t_1 = -1 と合致しません。よってw^(3) = w^(2) + φ(x_1) t_1 = (0, 1, 1) - (1, 1, 0) = (-1, 0, 1)
■Step 4
x_2 は w^T Φ(x_2) = -1 + 0 + 1 ≧ 0 となり t_2 = -1 と合致しません。よってw^(4) = w^(3) + φ(x_2) t_2 = (-1, 0, 1) - (1, 0, 1) = (-2, 0, 0)
■Step 5
x_3 は w^T Φ(x_3) = -2 + 0 + 0 < 0 となり t_3 = +1 と合致しません。よってw^(5) = w^(4) + φ(x_3) t_3 = (-2, 0, 0) + (1, 1, 1) = (-1, 1, 1)
■Step 6
x_1 は w^T Φ(x_1) = -1 + 1 + 0 ≧ 0 となり t_1 = -1 と合致しません。よってw^(6) = w^(5) + φ(x_1) t_1 = (-1, 1, 1) - (1, 1, 0) = (-2, 0, 1)
■Step 7
x_3 は w^T Φ(x_3) = -2 + 0 + 1 < 0 となり t_3 = +1 と合致しません。よってw^(7) = w^(6) + φ(x_3) t_3 = (-2, 0, 1) + (1, 1, 1) = (-1, 1, 2)
■Step 8
x_2 は w^T Φ(x_2) = -1 + 0 + 2 ≧ 0 となり t_2 = -1 と合致しません。よってw^(8) = w^(7) + φ(x_2) t_2 = (-1, 1, 2) - (1, 0, 1) = (-2, 1, 1)
これで全ての w^T Φ(x_n) が目的変数と合致するようになり、w = (-2, 1, 1) が得られます。
いやあ本当に学習できるんですね。
めでたしめでたし。
もしよければ、各ステップごとに決定面がどのように遷移するか描いてみると面白いかもしれませんね。
w = (a, b, c)、φ = (1, x, y) とすると、w^T φ = a + bx + cy = 0 なので、座標平面の ( - a/b , - a/c ) を通る直線として表せるので。
こんな簡単な例でも、いろいろ問題点が見えてきます。
(1) 収束に時間がかかる。
明確に解があることがわかっている、これだけ低次元の例でも収束に８回かかっています。
オンライン学習ライブラリで「学習を１０回繰り返す」必要があるのも大納得。
(2) 学習データの偏りに強い影響を受ける。
上の計算で(恣意的に)選ばれた誤分類ベクトルを見ると、x_3 が多いことがわかります。これは、正例が x_3 しかないためです。
これを本当にランダムに選んでいたら(そして実際の計算ではおおむねそうせざるを得ない)、収束にはもっと回数を要したでしょう。
あるいは学習データに偏りがなくても、ランダムに選んだ順番がたまたま「ずっと正例でトレーニングした後、今度はずっと負例」なんてことになったら、間違った結果が確実に出てしまうでしょう。
このあたりの問題点を少しでも解消しようとするのが Averaged Perceptron その他の方式、ということでしょうか。
なんにせよ、オンライン学習で「ランダム！」「繰り返し！」と叫ばれる理由がよくわかって、一安心です。
次回は実装。