講義ノート¶
第 1 回: シラバス (10.12.2010)¶
人工知能とは知的システムの設計や構成に関する研究分野である.
講義内容:
- 問題定式化
- 問題解決
- 知識表現
- エキスパートシステム
- エージェント
- 機械学習 (コンピュータは人間のように作ること)
- 進化計算 (GA, Genetic Programming)
- 人工生命
- Web Intelligence
機械学習アルゴリズム
人工知能に関する技術の改良やアイディアを提案することができる.
レポート 1 (30%) レポート 2 (30%) レポート 3 (30%) mini レポート 3 (10%)
ゲーム木とゲーム理論が違う!!
情報収集
最高レベル 人間の処理能力を実現する
[推論] とは [知識をもとに, 新しい結論を得ること]
[学習] はなにか機械が勉強をする感じがするが, ここでは [情報から将来使えそうな知識を見つけること]
推論 (ゲームの対戦) (オセロ)
人間との対戦は囲碁には全然だめ
清水市代女流王将 vs あから 2010 速報
学習 [買い物の調査]
協調フィルタリング (CF: Collaborative Filtering)
画像認識はできてない部分はまだ山ほどある.
人工知能 あなたのイメージ
第 2 回: 問題解決 (10.19.2010)¶
人工知能 (Artificial Intelligence)
AI については様々な定義がある
組み合わせ的爆発 (combinatorial explosion)
指数的 (exponential order)
多項式時間 (polynomial time)
問題解決 (Problem Solving)
鶴亀(つるかめ) 演算:
連立方程式の解き方:
- 代入法, 加減法, 未知数消去
- 逆行列
- すべての組み合わせを調べる
問題解決のプロセス:
1. 問題の定式化 (問題の本質を抽出)
2. 形式的処理 (アルゴリズム)
3. 対象世界での解釈
4. etc
外部世界と内部世界
フレーム問題 (1969, マッカーシーとベイズが指摘した)
http://www.ai-gakkai.or.jp/jsai/whatsai/AItopics1.html
定式化がきわめて難しい
ゲーム, パズルを解く問題
(1950 C.E.Shannon チェスプログラム) (1997 Deep Blue チェスプログラム)
解法, 解決手順が決まっていない
解が存在する空間の中から解を試行錯誤的に探索する (内部世界: 探索)
知能 = 探索
Toy Problem
問題定式化の方法:
状態空間法 (Well-Structured 問題, ill-Structured 問題)
状態空間法の基本要素:
1. 状態空間集合
2. オペレータ集合
3. 状態遷移関数
4. 初期状態
5. 最終状態
- 8 パズル問題
- 水差し問題 (状態空間法を用いる)
Water Jug Problem
You are given two jugs, a 4-gallon one and 3-gallon one. Neither has any measuring marks on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?
A = full B = full A -> B B -> A A = 0 B = 0
BFS (Breadth-First-Search)
DFS (Depth-First-Search)
Iterated Deepening: Attempt to combine BFS and DFS to get search with the following desirable
Example Problem:
3 Puzzle
8 Puzzle
Missionaries and Cannibals
第 3 回: 探索 (Search) (10.26.2010)¶
問題解決 -> 定式化 (状態空間法など) -> 探索
ブレンド探索: (付加情報を用いない)
ヒューリスティック探索: 付加情報を用いる
知能 = 探索
知識 = ヒューリスティクス
縦型探索, 深さ優先探索 (Depth First Search)
２つのリストを使うこと
リスト L1 の先頭に
横型探索, 幅優先探索 (Breadth First Search)
リスト L1 の 最後に
縦型探索 (DFS)のほうが有利であり, メモリを食わずに計算できる.
反復深化法: DFS のメモリ効率のよさを保持しつつ, 現実的な探索手段.
cutoff の初期値を導入する
欠点: 不要な探索が含まれている (オーバーヘッド)
全探索
ヒューリスティックス (heuristics) 探索
8 パズルにおける展開したノードと最終状態の類似性
ヒューリスティック関数 h(x): 状態 x が目標状態にどれだけ近いと考えられるかを定量的に与える関数.
山登り法 (hill climbing)
最良優先探索 (Best First Search)
A* アルゴリズム
探索コストの最小化: 各節点でのオペレータのコストの総和, 各ノードのコスト一定のときは, 最も浅い位置の目的状態を見つけること.
評価関数 f’(n) = g’(n) + h’(n)
g と h を決めること
A* アルゴリズムは最良の解をもっとも速く求めているが, 探索に用いている情報の量も一番多いので, 当然といえば当然かもしれない.
局所探索アルゴリズム (Local Search Algorithms):
1. 山登り法 (hill climbing)
2. 制約違反最小化 (min-conflicts)
3. 焼きなまし法 (simulated annealing)
局所最適解からいかに脱出するかが, アルゴリズム設計のポイントとなる.
山登り法の欠点:
局所最適解で停止する. 対策: ランダムな初期状態から再出発する (random restart) など. 高原では進むべき方向を判断できない.
制約違反最小化の実績:
百万クイーン問題: 平均 50 ステップ
ハッブル天体望遠鏡の観察スケジュール: 3 週間から 10 分に短縮
焼きなまし法では局所解をある確率で脱出できる.
焼きなまし法の最適性:
温度 T を十分ゆっくり下げるならば, 確率 1 で大域的最適解を見つける.
対数冷却: 収束時間は O(n!) より長い
向光性と局所解: ハエや蜂など向光性の昆虫は, ガラス窓の枠からなかなか外に出られない.
最良優先探索は, 局所解に陥らない. 幅優先探索に似ている.
ヒューリスティック探索の問題点:
1. 評価関数の与える評価値が実際の値に十分に近ければ, うまくいく.
2. そうでなければ, 局所解に陥ったり, 遠回りをしなければならなかったりする.
3. 最良優先探索でも, 評価関数によっては探索コストが最小の解を必ず見つけ出せるよいう保証はない.
4. 旅行計画では, 直線距離を評価関数に使うのが, 妥当.
A* アルゴリズムは, これまでの経路コストと現在地からゴールまでのコストの予測値の和を評価値とする.
A* アルゴリズムは, 探索コストが最小の解を必ず求めることができる.
最良優先探索との相違は, これまでの経路コストを考慮している点.
エージェントのスコア関数 f = g + h
g: 開始タイルからの距離 h: ヒューリスティック関数
第 4 回: ゲーム情報学 (11.02.2010)¶
科学的にゲームを捉える:
明確なルールがある
人間がプレーする
人工知能の問題設定:
数学的, 計算論的 => 探索, 計算可能性
認知か学的 => ヒューリスティクス
社会学的 => ゲーム理論, 合理性
ゲームの分類:
プレーヤーの数 (2, 3, 4 人)
情報の完全性 (隠れている情報は? 裏返っているトランプ)
情報の不確定性 (確率要素をふむ?) バックギャモン
勝敗による利得 (勝ち負けによって得られる対価)
将棋や囲碁は, 二人完全確定(不完全な要素を含まない)9ゼロ和ゲーム
ゲーム木の探索 (定式化 -> 探索)
2 人ゼロ和ゲーム (Two-person Zero-sum Game)
プレーヤの指し手 => オペレータ 起こりうる盤面 => 状態空間 盤面の評価 => ヒューリスティク関数
採用すべき探索法は?
特徴:
2 人のプレーヤが交互にプレーを行う
プレーヤの目的が相反する
三目並べを例に
ゲーム木の探索 (A* アルゴリズム)
プロ棋士は 15 ~ 20 手先読み
DeepBlue 11 手程度
mini・max 法の思考ルーチン: 相手の手番で最小値, 自分の手番で最大値
α カット ( 最大評価値の下限 h(s) ) β カット ( 最小評価値の上限 h(s) )
(12 通りの計算は 7 通りになる) (アルゴリズムを効率化する)
盤面評価: 評価関数
囲碁では? (難しい):
石の価値は平等
領域の広さを競うので広さを基準にする
オセロのような明らかに特徴のある箇所が少ない
局所的な最善手が全局的な最善手になりにくい
モンテカルロ囲碁:
モンテカルロ木探索
従来の問題を解決した?
残された問題と改善法についてのアイディアを示せ
モンテカルロ木探索を用いて
第 5 回: (11.09.2010)¶
学習: 日本語入力システムの変換結果学習などが挙げられる.
どのように実現する?:
ディジタルカメラの自動認識 (笑顔を認識できる)
自律ロボットの歩行獲得
メールクライアントソフトのスパムフィルタ
手書き文字認識
Amazon の本を買う
Google の検索キーワード予測
ビールを買った人は紙おむつも一緒に買う (知識発見)
強い囲碁のプログラム
日本語変換で過去の変換が変換候候補に反映される
コーヒー Bluemountain
機械学習 (machine learning):
学習:過去に行った問題や似た問題を経験をもとに, うまく解決する
機械学習: 学習能力を計算機システム上に実現する
機械学習の分類:
教師あり学習
教師なし学習
強化学習(教師なし学習の一種とも考えられる)
帰納学習 (inductive learning) (教師あり学習の例として)
クラスタリングに近い
仮説空間 (正例)
概念記述空間 (正例+負例)
一般化規則の例:
1. 条件削除規則
2. 一般化木上昇規則
仮説空間における探索
条件削除規則で (所属, 性別, 学年) を消去
バージョン空間法 (version space):
全体記述 (一般化)
^
|
|
|
|
訓練例 (特殊化)
バイアス (bias)
決定木 (Decision tree) J.R.Quinlan
人を特徴づける
属性: 対象の性質を表す要素
属性値: 各属性の取りうる値
クラス: 事例の所属先 ( 教師信号(+, -) )
学習データを正しくクラス分類するルール (決定木) を獲得する.
パートナーになれる (+) パートナーになれない (-)
クラスが出るかでないか確率である
確率って曖昧さも取り扱う
最も, 多くの情報量が減少する属性が好ましいので M(C) - B(C, A) を 最大にする属性 A がされる.
情報量の期待値はクラスの数には関係ない, いくつでも OK.
第 6 回: プログラムを使う (11.16.2010)¶
決定木生成アルゴリズム:
STEP1: 集合 C の全てのデータが同一クラスならクラスノードを作り停止. それ以外なら, 属性の
選択基準により一つの属性 A を選択し判別ノードを作る.
STEP2: 属性 A の属性値により C を部分集合 C1, C2, ..., Cn に分けてノードを作り属性値の枝
を貼る.
STEP3: ノード Ci (1 <= i <= n) について, アルゴリズムを再帰的に適用する.
C4.5 プログラムにより, 決定木を実装する
自分で決定木作成する
企画書の作成
ルール獲得実験:
トレーニングデータの作成
C4.5 プログラムの実行
得られた決定木の分析
テストデータによる評価
考察
[cactus:~/algo/AI/c4.5]% ls R8/ c4.5r8.patch2 [cactus:~/algo/AI/c4.5]% patch -p0 -d . < c4.5r8.patch2 patching file R8/Src/average.c patching file R8/Src/besttree.c patching file R8/Src/makerules.c patching file R8/Src/rules.c patching file R8/Src/siftrules.c patching file R8/Src/st-thresh.c patching file R8/Src/testrules.c patching file R8/Src/trees.c
[cactus:~/algo/AI/c4.5/R8/Src]% lv ../Data/golf.names [cactus:~/algo/AI/c4.5/R8/Src]% lv ../Data/golf.data [cactus:~/algo/AI/c4.5/R8/Src]% ./c4.5 -f ../Data/golf
[cactus:~/algo/AI/c4.5/R8/Src]% ./c4.5rules -f ../Data/golf | lv
問題設定
- 目的: 決定木により何を分析するのか?
- データの設計: どのような属性と属性値, およびクラスの設定をするか?
- データの収集: どのように必要なデータを集めるか? あるいは, どのようなデータを利用するか?
結果の評価:
第 7 回: 遺伝的アルゴリズム (12.14.2010)¶
C4.5 の課題は 12/21 の講義時間 (プレゼンテーション) 12/28 休講とする GA (Genetic Algorithm, 進化的計算) GA は汎用的に使われている
探索アルゴリズム, 近似解を求める, 最適解を求める.
計算の特徴
2 個体集団の突然変異による進化
GA はフレームワーク
集団に自然選択, GA オペレータ (交叉, 突然変異)を適用し, 次世代の集団を生成していく
1980 J.Koza Genetic Programming: GP
染色体 (chromosome)
遺伝子 (gene)
遺伝座 (locus, 遺伝子の場所)
遺伝子型 (genotype, Bit Coding)
表現型 (phenotype)
個体 (individual)
個体群 or 集団 (population)
すばらしい答えがたくさん残っているはず
Lisp は関数型のプログラミング言語
Simple GA:
Step0: コーディング
Step1: 初期集団の生成
Step2: 適応度 (fitness) の計算
Step3: 選択 (selection)
Step4: 交叉 (cross-over)
Step5: 突然変異 (mutation)
致死遺伝子 のところは, 初期集団のところではない!!
淘汰:
1. 高い適応度を持つ個体は生きのびる確率が高い
2. 低い適応度を持つ個体は淘汰される
生存競争を生き抜いた個体が最も優れた個体 (最適解)
初期集団のサイズは 50, 100, 1000 とか
選択の戦略::
1. ルーレット選択 (OK)
2. ランキング選択 (OK)
3. エリート保存選択 (微妙)
交叉確率が必要, 一定ではない.
突然変異, 新しい個体を作る, 局所解からを脱出
染色体上のある遺伝子を一定の突然変異確率で他の対立遺伝子に置き換える操作
ELD の定義, プロセスプランニング
CSD_HTCAI/GA/Ch5_2_5.html
終了判定: (世代交代の回数が, あらかじめ設定したを超えたか?)
GA の特徴:
多点型探索の近似解法
大規模問題空間へ有効 10^(10~20) 程度が目安
大域的探索であるため, 最適化問題の解法として利用する
GA3DSimulator
インタラクティブ GA
主観評価に基づく最適化問題へのアプローチ
進化計算における適応度関数を人間の感覚, 感性に置き換える
rgeSample 3D モデルの自動生成
今週の金曜日 18:00 以降 プレゼンの話
第 8 回¶
決定木プレゼンの発表:
観光地の特徴をルール化する
属性と属性値
クラス (観光地として良い, 悪い)
2006 年の観光地のデータにより評価
実は決定木のクラスは 二つだけじゃなくても OKAY
学生の財布
売れる映画の探索 (その特徴を抽出)
整合性がない
適合率がかなり低かった
第 9 回¶
ゲーム理論 (Game Theory)
意思決定の理論
経済活動の原理を解明する
協調, 環境, 情報, 競合, 意思決定.
ゲームの状況において, どのような意思決定が合理的であるかを解析する理論が必要となる.
Player (プレーヤ)
payoff function (利得関数): 利得とは, プレーヤがある行動をとったとき, その行動がどのくらい好ましいかを表す指標. 一般に, 他のプレーヤの行動を含めた行動対の結果として利得表により与えられる.
behavior (選択可能な行動)
合理的エージェントとは, 可能な限り自分の利得を最大化しようとする.
ゲームの定義 John Nash
非協力ゲーム (non-cooperative game)
–> 非協力ゲームはプレーヤ間でコミュニケーションが可能でなく, さらに拘束力のある合意が可能でないゲーム = プレーヤの独立な意思決定.
協力ゲーム (cooperative game)
戦略型ゲーム (game in strategic form) –> 静的な環境で各エージェントが一度だけ意思決定を行う.
展開型ゲーム (game in extensive form) –> プレーヤの手番を木構造によって表現し, 意思決定を行う.
繰り返しゲーム (iterated game) –> 戦略型を繰り返し行う環境で意思決定を行う.
A だけが戦略を変更しても不利になる. 同様に B も戦略を変更できない. この平衡状態を最適戦略といい, A の利得をゲームの値という.
混合戦略: (確率ゲームを導入)
囚人のジレンマゲーム: (非協力ゲーム)
- 繰り返し囚人のジレンマゲーム
- C D
C (3, 3) (1, 4) D (4, 1) (2, 2)
(2, 2) はナッシュ均衡
囚人のジレンマゲームを無限回繰り返して行うのが 繰り返し囚人のジレンマゲーム (IPD) である. IPD では, 過去の自分,相手のとった行動履歴を完全に知ることができ, これに基づいた戦略をとることができる.
IPD における戦略 all-D 戦略:
過去の自分, 相手の行動の履歴によらず, 必ず D を選択する.
- ex. all-D 戦略同士の利得ベクトルは
- 1回目 2回目 ...
利得 (2, 2) (2, 2) ...
all-C 戦略
好成績を得たルールの特徴: 相手がランダムに見えたり, 非協力的だと思うと協調をあきらめる. 対戦の後半で自ら裏切らない (上品さ: nice)
IPD (Iterated Prisoner’s Dilemma, 繰り返し囚人のジレンマ)
合理的なエージェントを選択する
戦略の評価は
IPD におけるには, 強い戦略を検討する.
過去 2 回までの手
2^21 = 2097152
0 = 協調 1 = 裏切り
0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 (TFT 戦略) 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 1 0 (この戦略を編集すること)
./run-bestpop.sh 1(集団作成用シード値) 1(GA 動作用シード値) 100(終了世代数) hand.pop(戦略を書き込んだファイル名) 2(読み込む戦略数)
出力ファイルのパス: /Users/wtopia/src_algo/IPD/vsIPD/output-ro_si_no
世代ごとにゲームの性質が変わる
IPD 戦略を GA で評価する
設計した IPD 戦略をエリート個体として GA を実行する.
STFT (Super Tit for Tat, 目には目を戦略)
蟻コロニー最適化 (Ant Colony Optimization, ASO) 粒子群最適化 (Particle Swarm Optimization, PSO) 確率的拡散探索 (Stochastic Diffusion Search, SDS)
- Natural Computing::
- Introduction
- Simulated Annealing
- Swarm Intelligence
- Particle Swarm Optimization
- Ant Colony Optimization
6. Cellular Automata 6a. Cyclic Cellular Automata 7. Neural Networks 8. Dynamical Chaos 9. Fractal Geometry 10. Firefly Systems 11. Artificial Immune Systems 12. DNA Computing 13. Evolutionary Algorithms
- Computing Inspired by Nature::
- Simulated Annealing
- Evolutionary Computing
- Neurocomputing
- Swarm Intelligence
- Immunocomputing
- Simulation and Emulation::
- Fractals
- Artificial Life
- Computing with Natural Materials::
- Molecular Computing
- Quantum Computing
協力ゲーム (cooperative game)
player 同士の協力が前提
どのような提携関係が形成されるのか? 提携後の利得配分の合理性は?
非協力ゲーム (non-cooperative game)
特性関数型ゲーム (game in characteristic function form)
player 集合: N = {1, 2, ..., n}
協力ゲームの定式化
(A, B, C) = (2300, 2200, 400)
協力ゲームの問題, その具体的な例は
問題:タクシーの相乗り
Xa + Xb + Xc = 3000 Xa + Xb >= 1300 Xa + Xc >= 1000 Xb + Xc >= 1800 Xi >= 0
提携合理性を満たす配分の全体 -> コア (core)
コアは存在しない場合, 多数ある場合がある.
コアの問題点:
1. 必ず存在するとは限らない
2. 一意だであるとは限らない
全体の満足度
ポリシー: 最も大きな不満を最小化する
シンプレックス法 カーマーカー法
貢献度に基づく分担法として sharpley 値が有名である.
MAS の具体例: テーマパークの問題
入場者 アトラクション: 三つ ゲート 道
上記の構成要素は全部エージェントとなる.
artisoc
