計算機科学概論(応用編) 人工知能のこれまでとこれから 計算機科学概論(応用編) 人工知能のこれまでとこれから 山本章博 情報学研究科 知能情報学専攻 　　　　（工学部 情報学科) 　　　

今日の内容 人工知能研究の誕生 探索を基本にした人工知能 ３目並べ 迷路 神経回路シミュレーションと人工知能 これからの人工知能

人工知能とは(1) 用語“人工知能(artificial intelligence)” 1956年 ダートマス大学で 関連研究者が会議を開催 “人間の知能機能はいかに してコンピュータによって シミュレートできるか?” 言語理解 チェスなどのゲーム 神経回路(ニューラ ルネット)，自己学習 前年：数学の定理証明プログラム 1956年当時のコンピュータの様子

人工知能とは(2) 原義：人間の知能機能をシミュレートするプログラムを造る コンピュータに人間とオセロを対戦させるようなプログラム コンピュータがことばを理解させるプログラムを造る ことばの理解をシミュレートことにより，逆にことばの理解プロセスをさぐる

探索を基本にした人工知能

ゲームの例: 3目並べ 正方形状に配置された９マスからなる盤に ２人のプレーヤーが交互に石（○と×）を置いていき，自分の石が縦，横，対角線のいずれか３個１列に並べることができれば勝ち．

状態空間表現(1) 石が置かれているマスの位置の集合の組 (W, B)で W , B Ì {1,2,…,9} W Ç B = Æ 3 4 5 6 7 8 9 石が置かれているマスの位置の集合の組 (W, B)で　 W , B Ì {1,2,…,9} W Ç B = Æ を満たすもの 例 ({1, 6}, {5, 9}), ({1,6,7},{5,9}) 集合は状態空間表現の一手段 他にも表現方法は考えられる ○ × ○ ×

状態空間表現(2) “起こり得ない”状態もある． 例 ({1, 3, 4, 6}, {5, 9}) “起こる”とは何かを定義しておく必要がる 7 8 9 “起こり得ない”状態もある．　 例 ({1, 3, 4, 6}, {5, 9}) ({1,6,7},{2, 3, 5,9}) “起こる”とは何かを定義しておく必要がる ○ × ○ ×

状態空間表現(3) 状態遷移 |W | = |B| ならば W に要素を１個追加 |W | > |B| ならば Bに要素を１個追加 1 2 3 4 5 6 7 8 9 状態空間表現(3) 状態遷移 |W | = |B| ならば W に要素を１個追加 |W | > |B| ならば 　　 Bに要素を１個追加 (それ以外 W に要素を１個追加) ○ × ({1, 6}, {5, 9}) ○ × ○ × … ({1,6,7}, {5, 9}) ({1,3,6,7}, {5, 9})

状態空間表現(4) 初期状態 (Æ , Æ ) 終了状態 1 2 3 4 5 6 7 8 9 初期状態 (Æ , Æ ) 終了状態 W, Bのいずれか一方だけが, 下のFの要素をちょうど１つを含むとき(目標状態)または, W, Bの両方がFの要素を含まず W È B = {1,2,…,9}のとき F = {{1,2,3},{4,5,6},{7,8,9}, 　　 {1,4,7},{2,5,8}, {3,6,9} 　　 {1,5,9},{3,5,7}} ○ × ○ ×

性質(1) 初期状態から状態遷移を繰り返すとき，ループは生じない 初期状態から状態遷移を繰り返すとき，到達する状態では必ず ループ: “千日手” 初期状態から状態遷移を繰り返すとき，到達する状態では必ず |W | = |B| または |W | = |B| + 1 “起こり得る状態”の定義 ○ ○ … …

性質(2) 初期状態から状態遷移を繰り返すとき，有限時間で必ず終了状態に到達する

MIN-MAX法(1) ○ 2 3 × 8 ○ 3 × 8 ○ 2 × 8 ○ 2 3 × ○ × 8 ○ 3 × ○ × 8 ○ 2 ×

MIN-MAX法(2) 0 -1 0 -1 0 1 ○ 2 3 × 8 ○ 3 × 8 ○ 2 × 8 ○ 2 3 × ○ × 8 ○ 3 0 -1 0 -1 0 1

MIN-MAX法(3) 子の 最小値 -1 -1 0 -1 0 -1 0 1 ○ 2 3 × 8 ○ 3 × 8 ○ 2 × 8 ○ 2 3 -1 ○ × 8 ○ 3 × ○ × 8 ○ 2 × ○ × 3 ○ 2 × 0 -1 0 -1 0 1

MIN-MAX法(3) 子の 最大値 子の 最小値 -1 -1 0 -1 0 -1 0 1 ○ 2 3 × 8 ○ 3 × 8 ○ 2 × ○ 3 × 8 ○ 2 × 8 ○ 2 3 × 子の 最小値 -1 -1 ○ × 8 ○ 3 × ○ × 8 ○ 2 × ○ × 3 ○ 2 × 0 -1 0 -1 0 1

迷路の例 エージェントが入口から出口まで通り抜ける ○

単純な状態空間と探索 状態: エージェントがいるマスの位置で表す 遷移：エージェントが 移動できるマス 初期状態から終了状態 への経路は存在する ループができてしまう 1 2 3 4 5 6 7 8 9 ○ ○ 　　　○

ループの回避(1) 進んできた経路を記録する 次に進むべきマスの位置を記録する 失敗したら，後戻りする ○ ○ 　　　○

ループの回避(2) 次に進むべきマスの位置の記録方法によって探索が変化する 　　　○ ○ ○ 　　　　　　○ ○ 　　 ○

深さ優先探索 次に進むべきマスを スタックに記録する スタック:対象の列で，後に入れた対象を先に取り出す 1 2 3 4 5 6 7 8 9 ○ 深さ優先探索 次に進むべきマスを スタックに記録する スタック:対象の列で，後に入れた対象を先に取り出す 進めるだけ先に進み，失敗したら，直近の分岐点からやりなおす ○ P={7, 4} S= 1,5 ○ ○ P={7, 4, 1} S= 5 P={7, 4, 1, 5} S= 2,6,8 ○ ○ ○ P={7,4,1,5,2} S= 6,8 P={7,4,1,5,2,6, 3,8} S= 9 P={7,4,1,5,2,6} S= 3,8

幅優先探索 次に進むべきマスをキュー (待ち行列，queue)に記録する キュー:対象の列で，先に入れた対象を先に取り出す 1 2 3 4 5 6 7 8 9 ○ 幅優先探索 次に進むべきマスをキュー (待ち行列，queue)に記録する キュー:対象の列で，先に入れた対象を先に取り出す 各状態に到達した時点で，すでに(最適な)経路が見つかっている ○ P={7, 4} Q= 1,5 ○ ○ P={7, 4, 1} Q= 5 P={7, 4, 1, 5} Q= 2,6,8 ○ ○ ○ P={7,4,1,5,2} Q= 6,8 P={7,4,1,5,2,6, 3,8} Q= 3,9 P={7,4,1,5,2,6} S= 8,3

神経回路のシミュレーション

人工知能を研究すること 異なるアプローチ 異なる目的 知的行為をシミュレートする 知能を持つ機械を実現する (人間の)知性の理解したい (人間より)大量に，速く，正確な実行 計算機科学の基礎

形式ニューロン 神経細胞(ニューロン) 形式ニューロン z = H(Sk=1n wk xk - q ) 樹状突起(dendrite)で刺激受け, 軸索終末(axon terminal)から他を刺激する 形式ニューロン z = H(Sk=1n wk xk - q ) ただし H(u) = 1 if u > 0 　0 otherwise Wikipediaより x1 w1 x2 w2 w3 x3 q z … wn xn

Perceptron[Rosenblatt] 形式ニューロンを3層に組合せることにより，画像を学習識別させる S層は網膜に相当し，外部からの入力のみ S層-A層間の重みwiはランダムに設定し，固定する． 中野他：ニューロコンピュータの基礎

A B 学習方法(1) 画像を入力する(入力信号)と同時に, その画像が, 提示者の意図している性質を持っているか(yes)か持っていない(no)かも信号(教師信号)として与える 例 文字Aを意図している場合， 入力 教師信号 yes no A B

学習方法(2) Perceptronの出力と教師信号の組合せによって，過重 wi を変更する 変更方法によって学習過程が変わってくる 出力と教師信号一致していれば，何もしない． 一致いていなければ，過重 wi を一致する方向にrだけ変更する

パーセプトロンの分析 データを分離する線形識別関数 パーセプトロン学習アルゴリズム (視覚)神経を模倣した機構として考案 線形識別関数をデータから構成する 線形分離可能であれば，必ず求められる データを読み込むたびに識別が正確になっていくので“機械学習”の一種とみなされる 線形分離可能 線形分離不可能

パーセプトロン学習(1) 簡単のため, 2クラスの分類を考える 問題の定式化 Rnの有限部分集合 C, D ( CÇD = Æ)が与えられたとき，直線 px + c = 0 で以下を満たすものを求めよ xÎ C Þ (w, x) + c > 0 xÎ D Þ (w, x) + c < 0 定数項cも求めなければならないのだから, データ x を (x, 1) とみなして, 求める直線を (w, x) = 0 としておく.

パーセプトロン学習(2) 1.与えられたデータを x1, x2, …, xN とする． 2. w を適当な初期値設定する. 3. n = 1,2,…, N に対して順に以下を行う もし xn Î C かつ (w, xn) < 0 であれば 　　 w を w + r x に置き換える xn Î D かつ (w, xn) > 0　 　　 w を w - r x に置き換える それ以外は何もしない 4. n = 1,2,…, N に対して xn Î C かつ (w, xn) < 0 またはxn Î D かつ (w, xn) > 0 を満たすものがなければ終了. そうでなけば３へもどる.

パーセプトロンの例

これまでの人工知能研究 これからの人工知能研究

人工知能とは “人工知能”の意味するところは，研究と技術の進展とともに変化している． 人工知能学会のホームページ “What’s AI” http://www.ai-gakkai.or.jp/jsai/whatsai/ “推論” と “学習”は人工知能研究の代表

日常化した”機械学習” かな漢字変換における“学習” かな(ローマ字)綴りを入力 ユーザは意図された漢字かどうかを示す信号を与える 変換システムの出力と教師信号が 一致していれば，何もしない． 一致いていなければ，漢字の優先度を変更する １回目 あきひろ 彰浩 no n回目 あきひろ 章博

抽象化した学習のモデル 教師 学習機械 概念Hに関する 例示 推測 データ h1, h2, h3,… d1, d2, d3,… 　推測 h1, h2, h3,… データ d1, d2, d3,… 学習機械 例からを仮説を導出する アルゴリズム

頻出アイテム集合 TID Transaction 1 {a, c, d} 2 {a, b, e, f} 3 {a, b, c, e} 4 C1 = {{a}, {b}, …, {f}} TID Transaction 1 {a, c, d} 2 {a, b, e, f} 3 {a, b, c, e} 4 {b, c} L1 = {{a},{b},{c},{e}} C2 = {{a, b}, {a, c}, {a, e}, {b, c}, {b, e}, {c, e}} L2 = {{a, b}, {a, c}, {a, e}, {b, c}, {b, e}} s = 0.5 C3 = {{a, b, c}, {a, b, e}} L3 = {{a, b, e}} C4 = Æ

数学の歩んだ道 有向線分 公理化(抽象化) ベクトル a+b = b+a a+ (b+c) = (a+b)+c 　公理化(抽象化) ベクトル a+b = b+a a+ (b+c) = (a+b)+c k(a+b) = ka+kb … 　　　　　　　　　　　　　　　　 具体化 解析 f (q) = a sinq + b cos q + c

自然言語処理＋機械学習 自然言語処理をより正確にするために機械学習を用いる 機械学習のデータとして自然言語処理の結果を利用する 文を単語(形態素)へ分解 構文の推定 機械学習のデータとして自然言語処理の結果を利用する 単語の共起関係分析　　 Web Intelligence へ

人工知能学事典(2005, 共立出版) ヒューマン・インタフェース 人工知能基礎， エージェント Webインテリジェンス ロボティクス 知識発見・データマイニング ソフトコンピューティング AI応用(人工知能の産業応用，ナレッジマネジメント，バイオロジー，教育支援，ゲーム） 人工知能基礎， 知の基礎科学(哲学， 心理学，認知科学，脳科学) 知識表現・論理・推論 知識モデリング 機械学習 進化・創発 自然言語処理 画像・音声メディア

人工知能学事典(2005, 共立出版) 相互 集合・社会 身体 ヒューマン・インタフェース 人工知能基礎， エージェント Webインテリジェンス ロボティクス 知識発見・データマイニング ソフトコンピューティング AI応用(人工知能の産業応用，ナレッジマネジメント，バイオロジー，教育支援，ゲーム） 人工知能基礎， 知の基礎科学(哲学， 心理学，認知科学，脳科学) 知識表現・論理・推論 知識モデリング 機械学習 進化・創発 自然言語処理 画像・音声メディア

“計算”も“人工知能”であった ダグラス・ホフスタッター: ゲーデル,エッシャー,バッハ-あるいは不思議の環-, 白揚社 D. R. Hofstadter: Goedel, Escher, Bach 　　-an Eternal Golden Braid-