人工知能特論 ６．機械学習概論とバージョン空間法 北陸先端科学技術大学院大学　鶴岡 慶雅

今日の講義内容 機械学習概論 バージョン空間法 http://www.jaist.ac.jp/~tsuruoka/lectures/ 機械学習って何？ 機械学習の応用例 バージョン空間法 仮説の表現、バージョン空間 Find-S アルゴリズム Candidate-Elimination アルゴリズム http://www.jaist.ac.jp/~tsuruoka/lectures/

機械学習の応用分野 画像・音声の認識 品詞タグ付け、構文解析、語義曖昧性解消 スパムメールの検出 サーバーへの不正アクセスの検出 クレジットカードの不正利用の検出 車の自動運転 ゲームのAI etc.

手書き文字の認識 Christopher M. Bishop, Pattern Recognition and Machine Learning, 2006

デモ GENIA tagger 英語用の言語処理ツール Tokenization 品詞タグ付け 原型の出力 浅い構文解析 固有表現認識 http://www-tsujii.is.s.u-tokyo.ac.jp/GENIA/tagger/

機械学習の種類 教師あり学習（supervised learning） 教師なし学習（unsupervised learning） 個々の事例に「正解」ラベルが与えられている 正解となるべく同じ動作をするように学習 教師なし学習（unsupervised learning） 正解ラベルが与えられていない データ間の関係を学習（クラスタリングなど） 強化学習（reinforcement learning） 自動的に試行錯誤して経験から学ぶ

教師無し学習の例 検索エンジン ＋ クラスタリング http://clusty.com

強化学習の例 ヘリコプター、ロボットの自動操縦 Inverted autonomous helicopter flight via reinforcement learning, Andrew Y. Ng, Adam Coates, Mark Diel, Varun Ganapathi, Jamie Schulte, Ben Tse, Eric Berger and Eric Liang. In International Symposium on Experimental Robotics, 2004 Quadruped Robot Obstacle Negotiation via Reinforcement Learning, Honglak Lee, Yirong Shen, Chih-Han Yu, Gurjeet Singh, and Andrew Y. Ng. In Proceedings of the IEEE International Conference on Robotics and Automation , 2006

機械学習（machine learning）とは？ 機械が学ぶ？ 言語を学ぶ？　数学を学ぶ？？ 現在の機械学習技術でやっていること 分類、回帰等を目的としたパラーメータの最適化 要素技術 確率、統計、アルゴリズム、数値計算

なぜ機械学習が必要か？ システムの動作を決めるルールを手で書けばよいのでは？ 参考 ルールの数が爆発的に増える 整合性を保つことが難しい 品詞タグ付け器、将棋の評価関数などのパラメータ数は、数十万～数億

バージョン空間法 Chapter 2 of Mitchell, T., Machine Learning (1997) 概念の学習 学習データ 仮説の表現 Find-S アルゴリズム バージョン空間 Candidate-Elimination アルゴリズム

学習データと概念 学習データ 学習したい概念 Days on which my friend Aldo enjoys his favorite water sports 属性（attributes） No. Sky AirTemp Humidity Wind Water Forecast EnjoySport 1 Sunny Warm Normal Strong Same Yes 2 High 3 Rainy Cold Change No 4 Cool

仮説（hypothesis） 仮説の表現 General と Specific h1 = <Sunny, ?, ?, Strong, ?, ?> 天気が晴れで風が強い日 （他の属性はどうでもよい） h2 = <Sunny, ?, ?, ?, ?, ?> 天気が晴れの日 General と Specific h1 は h2 よりも specific (h2 は h1 よりも general)

Find-S アルゴリズム 仮説 h を最も specific な仮説で初期化 全ての正例 x に対して、以下の処理を行う 仮説hを出力する 個々の属性に関する制約 ai に対して以下の処理を行う もし x が制約を満足しているならば何もしない そうでなければ制約 ai を、x が満足するように最小限緩める 仮説hを出力する

例 h0 = <0, 0, 0, 0, 0, 0> x1 = <Sunny, Warm, Normal, Strong, Warm, Same>, yes h1 = <Sunny, Warm, Normal, Strong, Warm, Same> x2 = <Sunny, Warm, High, Strong, Warm, Same>, yes h2 = <Sunny, Warm, ?, Strong, Warm, Same> x3 = <Rainy, Cold, High, Strong, Warm, Change>, no h3 = <Sunny, Warm, ?, Strong, Warm, Same> x4 = <Sunny, Warm, High, Strong, Cool, Change>, yes h4 = <Sunny, Warm, ?, Strong, ?, ?>

Find-S アルゴリズムの問題点 出力された仮説が本当に学習したい概念かどうかわからない 学習データに矛盾があっても検出されない 他にも学習データを説明する仮説があるかもしれない もっと general な仮説でもいいかもしれない 学習データに矛盾があっても検出されない

バージョン空間 定義 仮説空間 H 学習データ D バージョン空間： 学習データと矛盾しない仮説の集合

LIST-THEN-ELIMINATEアルゴリズム 個々の学習事例 d に対して d と整合的でない仮説をバージョン空間からすべて削除 バージョン空間に含まれるすべての仮説を出力

バージョン空間 Specific boundary と General boundary S: { <Sunny, Warm, ?, Strong, ?, ?> } <Sunny, ?, ?, Strong, ?, ?> <Sunny, Warm, ?, ?, ?, ?> <?, Warm, ?, Strong, ?, ?> G: { <Sunny, ?, ?, ?, ?, ?>, <?, Warm, ?, ?, ?, ?> } 仮説を羅列することなく S と G だけでバージョン空間を表現できる！

Candidate-Elimination アルゴリズム 初期化 G: 最も general な仮説の集合 S: 最も specific な仮説の集合 個々の学習事例 d に対して以下の処理を行う d が正例の場合 G から d と整合的でない仮説をすべて削除 S に含まれる d と整合的でない個々の仮説 s に対して S から s を削除 S に s より最小限 generalな仮説 h をすべて追加 ただし h は d と整合的であり、G に h より general な仮説が存在しなければならない S から冗長な仮説を削除 d が負例の場合 省略（正例の場合と反対の手続きを行えばよい）

例 最初の学習事例 <Sunny, Warm, Normal, Strong, Warm, Same>, yes S0: { <0, 0, 0, 0, 0, 0> } S1: { <Sunny, Warm, Normal, Strong, Warm, Same> } G0, G1: { <?, ?, ?, ?, ?, ?> }

例 ２番目の学習事例 <Sunny, Warm, High, Strong, Warm, Same>, yes S1: { <Sunny, Warm, Normal, Strong, Warm, Same> } S2: { <Sunny, Warm, ?, Strong, Warm, Same> } G0, G1 , G2 : { <?, ?, ?, ?, ?, ?> }

例 ３番目の学習事例 <Rainy, Cold, High, Strong, Warm, Change>, no S2,S3 :{ <Sunny, Warm, ?, Strong, Warm, Same> } G3: { <Sunny, ?, ?, ?, ?, ?> <?, Warm, ?, ?, ?, ?> <?, ?, ?, ?, ?, Same> } G2 : { <?, ?, ?, ?, ?, ?> }

例 ４番目の学習事例 <Sunny, Warm, High, Strong, Cool, Change>, yes S3 :{ <Sunny, Warm, ?, Strong, Warm, Same> } S4 :{ <Sunny, Warm, ?, Strong, ?, ?> } G4: { <Sunny, ?, ?, ?, ?, ?> <?, Warm, ?, ?, ?, ?> } G3: { <Sunny, ?, ?, ?, ?, ?> <?, Warm, ?, ?, ?, ?> <?, ?, ?, ?, ?, Same> }

最終的なバージョン空間 S4 :{ <Sunny, Warm, ?, Strong, ?, ?> } <Sunny, ?, ?, Strong, ?, ?> <Sunny, Warm, ?, ?, ?, ?> <?, Warm, ?, Strong, ?, ?> G4: { <Sunny, ?, ?, ?, ?, ?> <?, Warm, ?, ?, ?, ?> }