人工知能特論 9.パーセプトロン 北陸先端科学技術大学院大学 鶴岡 慶雅 今日の講義内容 • 特徴空間 • 分離平面 • パーセプトロン(Perceptron) – パーセプトロンの収束定理 • 平均化パーセプトロン(Averaged Perceptron) • 講義資料 • http://www.jaist.ac.jp/~tsuruoka/lectures/ 特徴空間 • 事例を特徴空間中における点で表現 特徴空間 • 事例を特徴空間中における点で表現 正例 <Outlook = sunny, Temperature = cool, Humidity = normal> 負例 <Outlook = rain, Temperature = high, Humidity = high> 分離平面 • 学習とは、学習データを利用して、正例・負例 をうまく分離する平面を見つけること パーセプトロン学習 • 学習データが線形分離可能であれば、学習 データを正しく分離する平面を見つけられる 線形モデル • 線形モデルによる2値分類 yx 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. すべてのサンプルを正しく分類できるまで 2 に戻り繰り返す 学習例 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 11 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 11 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 11 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 なぜうまく学習できるのか? • 正例の分類に失敗した場合 yx f wT x この部分の値が小さすぎた w w x として重みベクトルを更新すると w x x w x x T T もともとの値 2 必ず正 少なくとも同じサンプルに関しては間違いにくくなっている パーセプトロンの収束定理 • 正例と負例が線形分離可能であるならば、前 述のアルゴリズムにより、それらを分離する 超平面を有限のステップで見つけられること が保証されている。 • データが線形分離可能でないならば、パーセ プトロン学習は収束しない • 線形分離可能である場合でも、ステップ数が 非常に大きくなることがある 収束定理の証明(1) • 学習データ x1 , t1 , x2 , t2 , ..., xn , tn • 学習データを正しく分類する単位重みベクトルを u とする ・・・式(1) t j uT x j u 1 すべての学習サンプルをγ の余裕(マージン)をもって分類できている • 特徴ベクトルの大きさの最大値を D とする x j D ・・・式(2) 収束定理の証明(2) • k 回目の更新時の重みベクトルを wk とする 分類を間違えたのだから ti wk T xi 0 ・・・式(3) • u と k+1 回目の更新時の重みベクトルとの内積を考 えると T k 1T k w u w ti xi u wk T u ti xi u T k T w u 1回の更新につき少なくとも だけ増えるので 式(1)より wk 1T u k ・・・式(4) 収束定理の証明(3) • 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 wk 2 T 式(3)より 2 式(2)より 2 1回の更新あたり最大でも D しか増えないので w k 1 2 kD2 wk 1 k D ・・・式(5) 収束定理の証明(4) • 式(5)より k D wk 1 wk 1T u k u は単位ベクトルなのでベクトル の大きさを大きくすることはない 式(4)より • 結局 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 モデルの場合、新たな特徴を追加す ると、たとえその特徴が有用な特徴であっても性 能が落ちることが多い • 実装が簡単 • 学習のための計算コストが小さい • 確率値は出力されない
© Copyright 2024 ExpyDoc