人工知能特論 6．機械学習概論とバージョン空間法

人工知能特論
６．機械学習概論とバージョン空間法
北陸先端科学技術大学院大学鶴岡慶雅
今日の講義内容
• 機械学習概論
– 機械学習って何？
– 機械学習の応用例
• バージョン空間法
– 仮説の表現、バージョン空間
– 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）
– 正解ラベルが与えられていない
– データ間の関係を学習（クラスタリングなど）
• 強化学習（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 アルゴリズム
学習データと概念
• 学習データ
属性（attributes）
No.
Sky
AirTemp
Humidity
Wind
Water
Forecast
EnjoySport
1
Sunny
Warm
Normal
Strong
Warm
Same
Yes
2
Sunny
Warm
High
Strong
Warm
Same
Yes
3
Rainy
Cold
High
Strong
Warm
Change
No
4
Sunny
Warm
High
Strong
Cool
Change
Yes
• 学習したい概念
– Days on which my friend Aldo enjoys his favorite
water sports
仮説（hypothesis）
• 仮説の表現
h1 = <Sunny, ?, ?, Strong, ?, ?>
天気が晴れで風が強い日
（他の属性はどうでもよい）
h2 = <Sunny, ?, ?, ?, ?, ?>
天気が晴れの日
• General と Specific
h1 は h2 よりも specific
(h2 は h1 よりも general)
Find-S アルゴリズム
1. 仮説 h を最も specific な仮説で初期化
2. 全ての正例 x に対して、以下の処理を行う
– 個々の属性に関する制約 ai に対して以下の処理
を行う
• もし x が制約を満足しているならば何もしない
• そうでなければ制約 ai を、x が満足するように最小限
緩める
3. 仮説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
– バージョン空間：
VS H ,D  h  H Consistenth, D
– 学習データと矛盾しない仮説の集合
LIST-THEN-ELIMINATEアルゴリズム
1. バージョン空間を仮説空間 H のすべての仮
説を含むリストとして初期化
2. 個々の学習事例 d に対して
– d と整合的でない仮説をバージョン空間からすべ
て削除
3. バージョン空間に含まれるすべての仮説を
出力
バージョン空間
• 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, ?, ?, ?, ?> }

Download Report