人工知能特論９．パーセプトロン北陸先端科学技術大学院大学鶴岡慶雅今日の講義内容 • 特徴空間 • 分離平面 • パーセプトロン（Perceptron） – パーセプトロンの収束定理 • 平均化パーセプトロン（Averaged Perceptron） • 講義資料 • http://www.jaist.ac.jp/~tsuruoka/lectures/ 特徴空間 • 事例を特徴空間中における点で表現特徴空間 • 事例を特徴空間中における点で表現正例 <Outlook = sunny, Temperature = cool, Humidity = normal> 負例 <Outlook = rain, Temperature = high, Humidity = high> 分離平面 • 学習とは、学習データを利用して、正例・負例をうまく分離する平面を見つけることパーセプトロン学習 • 学習データが線形分離可能であれば、学習データを正しく分離する平面を見つけられる線形モデル • 線形モデルによる２値分類   yx  f wT x  1, a  0 f a     1, a  0 x ：サンプル  x  ：特徴ベクトル w ：重みベクトルバイアス要素 0 x  1 重みベクトルと特徴ベクトルの内積をとって、それがゼロ以上であれば +1 （正例と判定）、そうでなければ -1 （負例と判定）を返す関数パーセプトロン学習アルゴリズム 1. 重みベクトルを要素0で初期化 2. 学習データからランダムにサンプルを選択 3. 分類が間違っていたら以下の式で重みベクトルを更新 w  w   x  正例の場合 w  w   x  負例の場合 4. すべてのサンプルを正しく分類できるまで２に戻り繰り返す学習例 OR の学習 • 学習データ 1    x 2    0  1   1    x 3    1  0   1    x 4   1 1   t1  1 t2  1 t3  1 t4  1 負例正例正例正例 1    x1    0  0   Step 1 • x1 0   w  0 0   1    x1    0  0   t1  1 y x1   f 0 1  0  0  0  0  f 0 1 不正解！ w  w   x1    1   w  0  0   Step 2 • x4   1   w  0  0   1    x 4   1 1   t4  1 y x3   f  11  0 1  0 1  f  1  1 不正解！ w  w   x4  0   w  1 1   Step 3 • x2 0   w  1 1   1    x 2    0  1   t2  1 y x 2   f 0 1  1 0  11  f 1 1 正解！ w w 0   w  1 1   Step 4 • x3 0   w  1 1   1    x 3    1  0   t3  1 y x3   f 0 1  11  1 0  f 1 1 正解！ w w 0   w  1 1   Step 5 • x1 0   w  1 1   1    x1    0  0   t1  1 y x1   f 0 1  1 0  1 0  f 0 1 不正解！ w  w   x1    1   w  1  1   分離平面 • 最終的な重みベクトル   1   w  1  1   分離平面 r 1 w  x  0 T 入力（特徴ベクトルの2番目、3番目の要素）をそれぞれ q, r とすると 1  q  r  0 q 1 なぜうまく学習できるのか？ • 正例の分類に失敗した場合   yx  f wT x この部分の値が小さすぎた w  w   x として重みベクトルを更新すると w   x   x   w  x    x  T T もともとの値 2 必ず正少なくとも同じサンプルに関しては間違いにくくなっているパーセプトロンの収束定理 • 正例と負例が線形分離可能であるならば、前述のアルゴリズムにより、それらを分離する超平面を有限のステップで見つけられることが保証されている。 • データが線形分離可能でないならば、パーセプトロン学習は収束しない • 線形分離可能である場合でも、ステップ数が非常に大きくなることがある収束定理の証明（１） • 学習データ  x1 , t1 ,  x2 , t2 , ...,  xn , tn  • 学習データを正しく分類する単位重みベクトルを u とする・・・式（１） t j  uT x j    u 1 すべての学習サンプルをγ の余裕（マージン）をもって分類できている • 特徴ベクトルの大きさの最大値を D とする  x j   D ・・・式（２）収束定理の証明（２） • k 回目の更新時の重みベクトルを wk  とする分類を間違えたのだから ti  wk T xi   0 ・・・式（３） • u と k+1 回目の更新時の重みベクトルとの内積を考えると T k 1T k  w u  w  ti xi  u  wk T u  ti xi  u T k T w u  1回の更新につき少なくとも  だけ増えるので式（１）より wk 1T u  k ・・・式（４）収束定理の証明（３） • k+1 回目の更新時の重みベクトルの大きさを考える w  k 1 2  w k   ti  xi   w k  2  w k  2    xi   w k  2 D 2 2    xi   2ti xi  wk  2 T 式（３）より 2 式（２）より 2 1回の更新あたり最大でも D しか増えないので w k 1 2  kD2 wk 1  k D ・・・式（５）収束定理の証明（４） • 式（５）より k D  wk 1  wk 1T u  k u は単位ベクトルなのでベクトルの大きさを大きくすることはない式（４）より • 結局 D k      2 更新回数 k は有限であることがわかる PlayTennis の学習 • 特徴ベクトル – バイナリの特徴量で11次元 • パーセプトロンで学習 • 239ステップで収束学習された重みベクトル Bias 0 Outlook = Sunny -3 Outlook = Overcast 5 Outlook = Rain -2 Temperature = Hot 0 Temperature = Mild 3 Temperature = Cool -3 Humidity = High -4 Humidity = Normal 4 Wind = Strong -3 Wind = Weak 3 平均化パーセプトロン（Averaged Perceptron） • 実用的で高性能な機械学習アルゴリズム • Perceptron 学習アルゴリズムを少しだけ変形 – 最後の重みベクトルをそのまま使うのではなく、重みベクトルを全ステップにわたって平均したものを使う • ステップ数は、validation set の精度を観察して決めることが多いパーセプトロン学習の利点と欠点 • 特徴間に依存関係があってもかまわない（特徴どうしが条件付独立でなくてもよい） – Naive Bayes モデルの場合、新たな特徴を追加すると、たとえその特徴が有用な特徴であっても性能が落ちることが多い • 実装が簡単 • 学習のための計算コストが小さい • 確率値は出力されない