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