人工知能

人工知能
青木恭太
宇都宮大学
1
–
–
–
–
–
–
–
Game playing 人工知能とは何か?
Theorem proving
General problem solving
Perception
Vision
Speech
Natural language understanding
2
人工知能とは？
–
–
–
–
–
Expert problem solving
Symbolic mathematics
Medical diagnosis
Chemical analysis
Engineering design
3
別の人工知能研究の定義
人がうまく出来ることを如何にコンピュー
タに行わせるかを研究すること。
 人工感情
 人工倫理
 人工人格
 鉄腕アトムを作ることが究極の目標か?
 最近の話題、IBMの？DeepBlueがチェスの
チャンピオンに勝った。

4
人工知能
計算機が人と同一のアルゴリズムを用いて
いることは保障されていない。
 人工人型知能システムを構成しているの
か?
 我々が利用するには人工人型知能が使いや
すい。
 人工イルカ型知能が人に取り使いやすい
か？

5
高度人工知能
高度な知能システムは、自発的な問題提
起と目標設定が重要である。
 成すべき事をちゃんと実行する。
 何が成すべき事であるかを知る必要があ
る。
 どのような問題が自己の周辺に存在する
か?
 どの問題が重要であるか?
 どの問題を最初に解決すべきか?

6
高度人工知能
解決すべき問題を解決する為にどのように
すれば良いか? 現在，ここからは多くの人
工知能の問題となっているものが出現して
いる。将棋に勝つにはどうすれば良いか。
 自発的な問題提起と目標設定の為には人工
倫理が必要となる。

7
高度問題
地球環境の保全が人類の生存の為に必要で
ある。これは、極めて高度な問題の提起と
目標の設定である。
 科学技術の社会への適用である現在の技術
文明を捨て去り環境の保全を最優先とする
のか?我々地球上の生命は、長期的には小
惑星の衝突などの危険に曝されている。

8
将来の問題

我々が強大な科学技術文明の成果である衛
星打ち上げ技術と核エネルギー技術を有効
に用いれば将来の小惑星衝突を回避するこ
とが可能となる。
9
将来の将来の問題

更に超長期的（１００億年）には、科学技
術のみが１惑星の生命体系をその星系の存
続期間を超えて存在させる可能性を持つ。
10
パズル＆ゲーム
 パズルは，ひとり遊び．

ゲームは，２人以上の競技
– パズルとゲームは，まとめて分類されている．
11
パズル
 問題が良く定義されている
答えがある
 迷路、知恵の輪、ジグソーパズル、ハノ
イの塔，クロスワードパズル，人食い人
種と宣教師(全部で5人)，8パズル
 人工知能の基本的技術と手法
 状態空間と探索

12
ハノイの塔

台の上に３本の棒が固定されており、そのうちの一本に何枚
かの円盤がはまっています。
円盤は下へいくほど半径が大きくなっています。
話しを簡単にするために、一番左の棒をＡ、真ん中の棒をＢ、
一番右の棒をＣとし、最初にＡに何枚かの円盤がはまってい
るとしましょう。
棒Ｂを利用して全ての円盤をＡからＣに移してください。
ハノイの塔のルールは次の通りです。

一回に一枚の円盤しか動かしてはいけない。
移動の途中で円盤の大小を逆に積んではいけない。常に大
きい方の円盤が下になるようにする。
棒以外のところに円盤を置いてはいけない。


13
ハノイの塔
|
|
|
|
|
000
|
|
11111
|
|
2222222
|
|
333333333
|
|
44444444444
|
|
5555555555555
|
|
666666666666666
=======================================================
14
ハノイの塔
ある板を動かすには，その

上におかれているすべて
の板を，その板の動かし
先でない棒に移動する必
要がある．
再帰的プログラミング
– もしかしたら複雑な問題を簡潔に記述する方法を
与える
再入可能サブプログラム
 関数型プログラミング言語

– f(x)
解答例をXYZZなどで示します．
15
クロスワードパズル
タテのカギ
1 温泉のことを○○とも呼ぶ
2 海での救助を○○○○救助と呼ぶ
3 1年生になったら～♪では、何が100人でき
るの？
6 サナギから蝶になることを何という？
ヨコのカギ
1 男の子がズボンなら、女の子は○○○○が
正装。
4 生地を何層にも重ねて作るお菓子は？
5 小学生が、胸に着けて歩くものといえば？
7 ○○○○とチリ紙持った？
16
クロスワードパズル

知識ベース探索
– 辞書をひくのは簡単
– 言葉の意味から適合する言葉を見つける
– 文の意味の一致の発見
無矛盾
 拘束条件付連立虫食い算問題

– A12B+AA=BBBB
17
迷路
可能な道筋がただ一つ存在して、迷路中
の全ての場所に至る経路が存在する。
 探索問題
 ２次元迷路ならば迷路を上から見ればそ
う困難なく解が得られる。それでも大規
模になると正しい経路を発見するには困
難が伴う。

18
由緒正しい迷路例
19
パズルの共通課題＝探索
パズルは，基本的には状態空間における探
索問題ととらえることができる。
 状態空間で距離が定義できる？

– 状態空間が多次元ベクトルで表現できれば距離
も定義可能である。

状態空間で近傍が定義できる？
– １つの動作で移動可能な位置を近傍とすればよ
い。

状態空間で近傍への移動が可能? YES
20
状態空間
パズルの状態を完全に記述したベクトル
 そのベクトルの可能な値全体の空間

ハノイの塔
 （N1,N2,…,N64)

– Nnは，ｎ番目の環のありか｛１，２，３｝の要素
– 初期値(1,1,1,...,1)
– 目標(2,2,2,…,2)
21
ハノイの塔

（N1,N2,…,N64)
–
–
–
–
–
Nnは，ｎ番目の環のありか｛１，２，３｝の要素
初期値(1,1,1,...,1)
目標(2,2,2,…,2)
大きさは，Ｎ６４の方が大きい側とする．
Ｎｉが移動可能：：Ｎｉ ≠ Nj:j<i
• Ｎｉが一番上
– Ｎｉが塔ｎへ移動可能
• min(j){Nj=n} > i
22
探索
状態空間で距離が近ければ移動可能？ ???
 距離が近い＝近傍ならば何の問題もない。

– パズルでは，単純な状態空間表現において，距
離が近いことと，近傍であることが一致しない。
– ほとんど解なのに解に直接いたる経路がない．
23
迷路
2次元空間距離と隣接性はかけ離れている。
 出口からの道のりを用いれば，隣接性と道の
りが一致する。

– 簡単に解ける。

全探索
– すべての可能な経路をしらみつぶしにする
– 同じ場所を2度以上探索しない
– 繰り返しに陥らない
24
迷路探索解法
迷路は，ますに別れている．ますの間には通
路か壁がある．
 すべてのますに∞が書かれている．
 ゴール（出口）のますに０を書く
 すべてのますでmin(Nn)＋１を書き込む．ここ
でmin(Nn)は，ますnに直接通路で接続されて
いるますに書き込まれている値の最小値

25
迷路解法
前スライドの解法は，巾優先探索法（横型）
 由緒正しい迷路でなくとも解を得る．

– ゴールが複数ある．
– 経路が複数ある．
26
迷路解法例
15
14
13
12
13
14
15
S
14
13
12
11
10
9
10
23
12
11
10
9
8
11
22
13
14
15
16
7
12
21
20
19
18
17
6
13
0 G
1
2
3
4
5
14
27
迷路解法例
∞
∞
∞
∞
∞
∞
∞
S
14
13
12
11
10
9
10
23
12
11
10
9
8
11
22
13
14
15
16
7
12
21
20
19
18
17
6
13
0 G
1
2
3
4
5
14
28
近傍
近いこと
 例

–
–
–
–
距離が近い
隣
道のりが近い
違いが少ない
29
探索法

深さ優先探索 depth first
– 解に早くたどり着く可能性がある
– 解を見逃す可能性
– 後戻り（Back track)

巾優先探索 width first
– 全探索
– 解を見逃さない
30
探索の効率化
巾優先探索を行えば必ず，有限解を見つけ
る
 でも，これは知恵がない
 ハノイの塔などでは，現実的な時間内に解を
見つけることはできない。

– ハノイの塔は，もともと解自体が巨大で解を記述
することさえ困難であるが
31
枝刈り
巾優先探索において，探索しない部分を決定
する
 深さ優先探索において，その経路の探索を中
止し，後戻りする
 解が先にある枝を刈ってしまうと解が見つか
らなくなる
 解があるはずがない枝を探索対象から外す
ことができれば，探索速度が向上する

32
探索順序の決定
深さ優先探索において，解の存在する枝から
探索する
 解の存在する可能性の高い枝から探索する
 評価関数による決定

33
評価関数
状態空間の1点が，どの程度解に近いかを評
価する関数
 評価関数の計算がたいへん

– 本当に探索して評価値を求める
– ランダムに決定する
– 周りの情報を統合して決定する
34
ハノイの塔（補足）


N枚のハノイの塔の板を動かす回数を考察する．
N番目の一番大きい板の上に乗っかっているN-1枚
のハノイの塔問題を解き，目的の棒に動かし，残り
のN-1枚のハノイの塔問題を再度解けばよい．
– H(n)=H(n-1)＊２＋１
– H(1)=１
– H(n)≒２＊＊ｎ
35
宣教師と人食い人種問題
3人と宣教師と3人の人食い人種の一行が2
人乗りボートで川を渡りたい．
 人食い人種の人数が宣教師の人数より多く
なると人食い人種は，誘惑に負けて宣教師を
食べてしまう．
 どうしたら一行は，問題なく対岸へ渡れる
か？

36
宣教師と人食い人種問題
船には2人しか乗れないので，船で宣教師が
食べられる可能性はない．
 両岸で宣教師の人数が常に人食い人種の人
数と等しいか多くなければならない．
 この拘束条件の下で全員が対岸へ移動する
経路を探索する．

37
左岸
右岸
宣教師
人食い人種
宣教師
人食い人種
3
3
0
0
L-0
3
2
0
1
L-2
3
1
0
2
R-1
3
0
0
3
R-3
2
3
1
0
2
2
1
1
2
1
1
2
0
1
1
1
2
L-4
3
1
4
0
5
1
6
2
0
7
1
3
0
8
3
2
0
0
9
1
2
2
1
0
10
1
1
2
2
1
11
1
0
2
3
0
12
0
3
3
0
L-9
1
13
0
2
3
1
R-8
L-11
0
1
3
2
R2
R-10
15
0
0
3
3
R0
R-12
16
L-7
R-5
L1
14
38
完全な評価関数
常に一番よい評価関数を持つ状態へ移動す
ることにより，解へ到達する．
 何の迷いもない．何の無駄も無い探索の実
現．
 もちろん，多くの困難な問題では，完璧な評
価関数どころかまあまあ使える評価関数も無
い場合がある．

39
状態空間
問題で可能性のあるすべての状態を包含す
る空間
 抜けがあってはいけない．
 可能であれば，無駄がないほうが扱いが容
易．
 状態空間を決定する過程が問題の分析とな
る．

40
状態変化

状態空間での移動は？？
– 状態変化
– オペレータ
• 状態の変化を引き起こす作用
• 制御できるオペレータもある．制御できないオペレータ
もある．
41
状態空間記述例
ハノイの塔は前述
 迷路は？？
 格子状迷路なら整数座標空間で表現

– （x,y)
8クイーン？？
 ((x0,y0),(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5
),(x6,y6),(x7,y7))

(xn,yn)は，ｎ番目のクイーンの盤上の位置
42
状態空間例

宣教師と人食い人種
– 左岸の宣教師人数と人食い人種人数とボート位
置
– (2,1,L)
• 左岸に宣教師2人，人食い人種１人，ボートは左岸に
• このとき，自動的に右岸に宣教師1人，人食い人種2人
で，宣教師は人食い人種に食べられてだめ．
43
オペレータ例
迷路
 格子状迷路なら(+1,0),(-10),(0,+1),(0,-1)のい
ずれか
 （ｘ，ｙ）の位置の右に壁があれば，オペレータ
(+1,0)は，位置(x,y)では適用不能．

44
探索
状態空間の初期状態からはじめて
 そのときに適用可能なオペレータを適用して
 そのとき適用されるオペレータを適用して
 最終状態（解状態）へ至る経路を探す

45
探索法＋

状態空間が分かっている．
– 問題が良く定義されていれば，状態空間も分かっ
ているはずである．
状態空間は，巨大である．
 探索目標(解)と探索開始点の距離は，そんな
に大きくない．

– 意味のある解が存在する．
46
探索法＋

探索開始点の近傍のみを探索したい．
– 迷路探索法は，迷路全体（状態空間全体)を対象
として探索している．これでは，巨大な問題は，扱
えない．

探索開始点から解に至る経路を生成しながら
探索する．
47
基本探索方式
同じ状態を探索しない
 同じオペレータ系列を探索しない
 何でも探索する

48
同じ状態を探索しない
解が状態で定義されているとき，同じ状態を
繰り返し探索するとむだ．
 同一の状態に至る経路が多数存在する．

– 同一の状態を探索しないと，同一の経路を探索し
ない場合と比較して，探索範囲が大幅に減少す
る．
49
同じオペレータ系列を探索しない
答えは，多くの場合解に至る操作の系列を示
す必要がある．
 同じ操作系列を探すのは無駄．

– 同一の操作系列を繰り返すことを防げば，探索
数の爆発を抑えられる．
50
何でも探索する
問題がよく分かっていないとき，めくらめっぽ
うに探索する
 効率は良いはずはない．

– でも，解が有限の範囲にあるのであれば，いつか
解に行き着く
– ランダム探索
– よく分からない問題でも解ける可能性がある．
– 案外，運良く高速に解けてしまうかもしれない．
51
何でも探索する
もう少し工夫すると，遺伝アルゴリズムなども．
 ランダムに探索するとあまりに効率が悪い．

– でもランダム探索ならどんなわけの分からない問
題でも解があるのであれば取り組める．

なるべく悪影響が出ないように探索する．
– 問題の分かっている性質を遺伝子に表現する．

うまくいっている探索を生かす．
52
ランダムアルゴリズム例
イサーネット
 通信路で混信が起こったときに，再送待ち時
間をランダムに決定する．

– 運が悪いと，再度混信する．
– ほとんどの場合，うまくいく．
– 実用上問題なく動作している．
53
イサーネット問題
混信時に再送待ち時間を決定する．
 ネットワークにつながっているすべてのホスト
で調整すれば簡単．

– でもネットワークの通信問題なので，ネットワーク
を使って調整はできない．

そこで，ランダム探索
– ネットワークに接続されているホスト間で調整す
ることなく，再送待ち時間を決定する．
54
ゲーム

最初の状態と勝利条件が決まっている．
– パズルと同様

可能な動作（指し手）が決まっている．
– パズルと同様

複数のプレーヤーがいる．
– パズルは，一人
55
ゲームの例

2人０和ゲーム
– 最も簡単な構造を持つゲーム
ｎ人０和ゲーム
 2人非０和ゲーム

– 生物の共棲
寄生
56
2人０和ゲーム
• 最も簡単な構造を持つゲーム
• ゲーム参加者が2人で，ゲーム参加者の利益（不利益）
の和が変わらない．あるいは，有利・不利の合計が変化
しない．
• 交互手順・同時手順
• 対称性
– 対称・非対称
57
N人０和ゲーム
人数が増えた場合．
 多くのボードゲーム．



順次手順・同時手順
対称性
– 対称・非対称
– ばくちは，胴元も含めて考えるとN人０和ゲームで，非対称
58
Ｎ人非0和ゲーム
非対称
 多くの社会現象

–株

戦略
– 最適戦略

ネットワークゲーム
59
決定性

決定性と非決定性
– 決定性
• 確率が関与しない
– 非決定性
• 確率が関与する
60
手順

交互手順
– 将棋、碁などの2人ゲーム

順次手順
– ７並べなどの多人数ゲーム

同時手順
– じゃんけん

実時間手順
– ネットワークゲーム
– 対戦型ビデオゲーム
– 戦争
61
情報

完全情報
– ゲーム状態のすべての情報がプレーヤーにわか
っている。
– 将棋、碁

不完全情報
– ゲーム状態に関する一部の情報がプレーヤーに
わからない。
– ババ抜き、7並べ（3人以上）…
62
ゲームの扱い

2人0和・完全情報・交互手順・決定性ゲーム
– 初期状態
– 勝利条件．最終状態．
– 可能な手が決まっている・可能な手が決まっていない．

パズル
– 1人決定性・完全情報・順次手順（離散手順）ゲーム
63
2人決定性・完全情報・０和ゲーム
パズルでプレーヤーが2人になった
 状態空間で記述できる
 状態空間で勝ちを探索すれば良い
 手順

– 交互
• ほとんどのゲーム，将棋とか
– 同時
• じゃんけん
64
2人決定性０和交互手順
将棋，碁，チェス．．．．．
 相手の手順を考える

– 相手は，最も相手にとって良い手を打つ
– 相手は，最も自分にとって悪い手を打つ

max-min探索
– min max探索
– and or 探索
65
Max-min探索
（2人交互手順ゲーム）
 自分自身は，自分にもっとも良い手を打つ
次に相手は，相手にもっとも良い手を打つ
 自分の打ち手＋相手の打ち手＝1回の動き
 自分の手を打った直後は有利
 相手が手を打った直後は不利

66
Max-min探索の詳細




自分に有利な手を探索する
相手は，相手にもっとも有利な手を探索する．（仮定）
上記２つを合わせてもっとも自分に有利な手を探索
する．
max(Max-min)となる自分の手を探索する
– 評価関数の存在を仮定している．
– 完璧な評価関数を持てば，完璧な手がうてる．
– 完璧でない評価関数では，完璧でないてしか打てない．
67
11月16日質問
回答（解答ではありません)
「もっとも良い」の定義はコンピュータには難しいの
では？
利用可能な評価関数の評価値のもっとも高いもの
「決定性」と「非決定性」の違いがよく分かりません
決定性は，プレーヤーの動作以外の要因で結果が変わらない．
非決定性は，プレーヤーの動作・行動以外の要因で結果
が変わる．
オセロは先手必勝ですか？
むむむ．知りません．
「なぜ０和」と言うのか？
プレーヤーの利得（有利不利)の合計(和)が零になるからです．
将棋と碁の違いは？
見たとおりですが，碁は盤面が圧倒的に大きい．探索（先読み)
が困難．
複数の手を読む場合はどうするの？
バックトラックあるいは巾優先で探索して，良いものをおいておく
．
AND・OR探索は？
評価値が2値の場合です．
囲碁では後手にハンディーが与えられているから
有利・不利は変わらないのでは？
ハンディーが正しく与えられているか，否かは不明です．完全に
正しく与えられていれば，多数回の同じ強さのプレーヤー
の勝負を見ると50%ずつ勝つはずですがそんなことは検証
できない．
決定性と非決定性の例がもっと欲しい．
非0和ゲームとは？
プレーヤーの利得（有利不利)の合計(和)が零にならないもの．
株．経済．企業．人間関係．生活．さまざま．
スポーツなどはN人非0和ゲームか？
野球は，プレーヤーの人数は2人ではありませんが，ゲーム分
類では2人0和ゲームです．２人＝2チーム．
スポーツで試合の流れがあると思うのだが，決定
性の問題？？
人間の心理状態の影響であると認識しています．
人工知能が最善の手を考えるのであれば，そういう
状況にならない場合の考え方を深く知りたい
68
最善と思われる手を考えているのであって，最善であることを保
障していません．
嵌め手にはまる



自分の手を打った直後の評価関数の値は非常に高
い．
これは，よい手だと思ってその手をうってしまう．
相手が対抗してある手を打つと，その結果の評価関
数は劇的に低下する．
– 相手の対抗して打つある手以外では，多くの場合評価関
数は，非常に高い値を維持する．
– 相手の対抗して打つある手を見逃すと，よい手としてその
手をうってしまう．
69
嵌め手にはまる
この手がと
てもよく見
える
現在の状態
手Aをうった後↑↑
相手の手X↑↑
手Bをうった後↑
相手の手Y↓↓↓
相手の手Z↓
手Cをうった後↓
相手の手G↓
でも相手の
この手まで
考えれば良
くない
70
必要事項
状態の評価
 手の選択は，min あるいは max となる状態に
移り変わる手を選択すればよい
 手の評価は，状態の評価の差分

71
Max-Min探索
 自分の打ち手と相手の打ち手をあわせて考
えるとMax-Min探索になる
 決定性・完全情報・交互手順・2人０和なら，
先手必勝，後手必勝，引き分け
– ??????
– でもそれを決定するほどには，手筋を探索するこ
とは出来ない．
– 将棋，碁：時間制限あり
72
先手必勝・後手必勝・引き分け？



先手が有利になる手があれば，それを最初に先手
がうつと有利になる．後手は，どうがんばってもその
不利を回復できない．
先手がどんな手をうっても不利になる．後手は先手
の不利を利用して，勝ちを目指す．先手は，初期の
不利を回復できずに負けとなる．
先手・後手が完璧な手を打ち続けると，どちらも決
定的に優勢にはならない．そのうちに，以前の状態
に戻る．その後は，同一の繰り返しになる．
73
ゲーム探索の困難

将棋を例に取る
– こま40枚
•
•
•
•
•
このすべてがゲームが終了するまで使用可能
平均的には，一手に20枚が使用可能
動かすこまを選択するだけでも20通り
相手のこまを選択するのにも２０通り
自分の一手と相手の一手でこまの選択だけで400通り
– こまの可能な動きは，それぞれ異なっているが平均２通り存在すると
仮定すると
• 1600通りになる．
• 10手先まで読むと160010≒1030 とても全探索はできない．
• 完璧でない評価関数を利用せざる得ない．
74
ゲーム探索の困難
一回の手順で1600通りの可能な手が存在す
ると仮定
 最も短くとも勝敗が決するまでに6手は必要
 最短でも初期状態から一方が勝利するまで
の探索対象状態は，

– 1600＾6≒１０＾１９≒１０＾１０Ｇ
– 現在のパソコンで１０＾１０Ｓほど317年
75
ゲームを面白くするために

対称性の破壊
– 先手必勝なら後手が有利になるように

我々が探索できない程度に手筋を複雑にす
る．
76
評価関数
手筋をすべて探索せずにどの手が良いかを
決定する．
 本当に手筋をすべて探索して評価値を決定
する．
 その状態空間点のみの情報で評価値を決定
する．
 何手か先までの手筋を探索して，そこの状態
空間点を評価する．

77
評価関数
手筋をある程度探索して，そこの評価値で評
価を与える．
 状態空間点の情報のみで評価を与える．

– 相手の王将と自分のこまの距離の最小
– 少なくとも勝利状態で良い評価値を与える必要が
ある．

有利・不利の理解
78
状態空間点の評価
これでゲームの強さが決まる．
 これを使って枝刈り

– 良い状態空間点評価関数があれば，探索手順範
囲が増加する．
79
枝刈り
不十分な状態評価関数であっても，十分な手
筋を探索できれば勝つことができる．
 探索の量を減らせば良い．
 あらかじめ可能な手を制限する

– 可能な手を制限すると思いもかけない独創的な手
は生まれない
– 定石を覚えて，それを活用する．
– 知識ベースを整備して，利用する．
80
ノルム






最小～平均～最大
Xの要素が非負なら
N=1なら平均
Ｎ→∞なら最大
N→0なら最小
N=2なら2乗平均
 x
 xX

 X

n





1
n
81
ノルム
右の表を見ると
分かるが，乗数
を大きくするとだ
んだん平均から
MAXに近づいて
いる．
何乗(n)
x^n
y^n
(x^n+y^n)/2
((x^n+y^n)/2)^(1
/n)
1
1
100
50.5
50.5
2
1
10000
5000.5
70.71421356
3
1
1000000
500000.5
79.37007906
10
1
1E+20
5E+19
93.30329915
20
1
1E+40
5E+39
96.59363289
40
1
1E+80
5E+79
98.28205985
80
1
1E+160
5E+159
99.13730875
100
1
1E+200
5E+199
99.30924954
120
1
1E+240
5E+239
99.42404238
140
1
1E+280
5E+279
99.5061185
150
1
1E+300
5E+299
平均
99.53896791 82
平均で評価するの？MAXで評価する
の？
Normを使えば，最小～平均～最大の中で適
当に調整することができる．
 ノルムは，調整可能な最小・平均・最大の一
般化されたもの．

83
決定性2人０和交互手順完全情報
ゲーム







例としてチックタックトウ（○×ゲーム)を考える．
盤面3×３
交互にますに○×をかく．
先に３つ並べた方が勝ち
○○○
○の勝ち
××○
××
84
評価関数

自分の最大長さー相手の最大長さ
自分の最大長さが３なら100000
相手の最大長さが３から-100000

自分の勝利が分かる．


– ちゃんと分かる．

十分大きければ
OK
自分の負けが分かる．
– ちゃんと分かる．

自分の有利がわかる．
– 本当か否かは別にして，分かる．
85
手の選択
置いてみて，最も評価関数の値の大きい手を
選択する．
 現在の状況は，決定しているので，最も評価
関数が大きくなる手が最も良い手．
 評価関数が完璧であれば，完璧な手を選択
する．

86
拡張評価関数
ｎ手先まで手筋を読んでそこの盤面の評価関
数値を値として返す．
 自分と相手の双方が同じアルゴリズムを使う．

– 本当は，違うが利用可能な最も良いプレーヤー
のモデルを使用する．
– 自分自身しかない．別のもっと良いモデルがあれ
ば，それを使ってプレーする．
87
プログラムによる実現
186行perlプログラム
 本体は，131行（コメント込み)
 実行してみると，チックタックトウは引き分け．
 変なおき方をしてしまうと必勝・必敗になる．
 実は，ｎ×ｎで動作する．
 全手順を探索すると４分ほどかかる．

88
知恵は使っていない




評価関数は，「何手か先までの手筋を探索して，そ
この状態空間点を評価する．」タイプです．
十分な手数を探索すれば，良い手を選択する．
枝刈りなし．
巾優先探索．
– 指定された手数まで探索

全探索なので深さ優先・巾優先はあまり関係ない
89
将棋:例

自分のこまの数ー相手のこまの数
– 各こまの重みを決めてその和
相手の王将と自分のこまの距離
 局面で変わる

– 序盤，中盤，終盤
90
決定性２人０和交互手順
それ以外も基本的には同一
 非決定性

– 現実の問題では，多い
– 評価値がぼやける
• Fazzy：計量体系
• 確率密度分布

ｎ人
– max-min-min-min…..-min
– 手順を読むこと(探索)が困難
91
Fuzzy

AND・OR
– 2値論理ならこれ

MIN・MAX
– 多値論理ならこれ
– 2値にするとAND・ORと同じ

MIN・MAXは，AND・ORの一般化になっている．
– 良い手，悪い手を明確に区別することは困難．明確でな
い値を処理するならMIN・MAXになる．
92
2値論理（０・１）
制御系をこれで作ると，遅れなし定常（目標
値の変動なし)なら完璧に目標値に制御可能．
 目標値が変化すると，急激なON/OFF．

– 乗り物だと乗り心地が悪い．機器が傷む．

遅れと慣性があると振動．
93
FUZZY
目標値が変動したりしたときに，滑らかな制
御が可能．
 ある程度の誤差を容認．

– 現実の機器では，もともと誤差0はありえない．列
車の停止位置が１ｍずれれば問題．
– 列車の停止位置が，１ｃｍずれても問題ではない．
94
決定性２人非０和交互手順
–
–
–
–
きつねとたぬきの化かしあい
親友
例:派閥闘争，暴力団の抗争，２大政党
競技参加者ごとに評価値（結果の良さ)自体が異
なっている．
• 参加者ごとの勝利条件自体が異なる
– パレスチナ
95
決定性２人０和非交互手順
– 同時
• じゃんけん
– ランダム
• ネットワーク対戦型ゲーム
– 実時間手順
• 現実世界
96
ゲーム分類

参加者？
– １，２，ｎ

手順？
– 交互、順次、同時、実時間

ゲーム全体の利得の合計？
– ０和、非０和

決定性？
– 決定性、非決定性
97
将棋は、先手必勝・後手必勝・引
き分け
決定性、交互手順
 帰無仮説

– 将棋の勝敗は、ｎ手目以降の手順のみで決まる。
– 言い方を変えると、n-1手目までで決定するn手目
を開始する盤面の状態（こまの並び）に依存しな
い。

つめ将棋では、勝敗は決定している。詰め将
棋の局面となるＸ手目以降では、上記帰無仮
説は成立しない。
98
将棋は、先手必勝・後手必勝・引
き分け
。nは、Ｘよりも小さい。
 。ｎは、有限の数である。
 。n手目までの可能な手順の数は、有限であ
る。

– 後手は、後手必勝とな手順を目指す。
– 先手は、先手必勝となる手順を目指す。
– どちらもそのような手順を発見できないときには、
引き分けとなる手順を選択する。
99
将棋は、先手必勝・後手必勝・引
き分け

将棋の盤面のパタンは、有限である。
– 各パタンは、先手必勝・後手必勝・引き分けのい
ずれかである。
– 先手必勝の盤面に必ず到達する盤面は、先手必
勝である。
– 後手必勝の盤面に必ず到着する盤面は、後手必
勝である。
– 先手必勝にも後手必勝にも到達しない盤面は、
引き分けである。
100
課題
ゲームおよびパズルをあわせて分類し，各タ
イプを説明せよ．また，そのタイプの実例(ゲ
ームおよび実世界の各種現象）をあげよ．
 A4 １枚にまとめること．
 提出1２月７日講義開始前

101
中間試験予定

日時
– 未定．授業時間

範囲
– 定理証明の前まで．
102
探索としてのまとめ
縦型探索（深さ優先探索）
 横型探索（巾優先探索）
 ＭＡＸ－ＭＩＮ探索
 枝刈り

– 横型探索では、全探索を避けるために必要

バックトラック
– 縦型探索では、解にたどり着くために必要
103
状態空間と評価関数

状態空間
– ゲームに関するすべての情報を表現するベクト
ル全体が張る空間

評価関数
– 状態空間の各点（ゲームの局面）がどの程度よ
いかを与える．
– すべての可能性を探索することが不可能であれ
ば，そのゲームの局面を評価することが必要に
なる。
104
枝刈り
不十分な状態評価関数であっても，十分な手
筋を探索できれば勝つことができる．
 探索の量を減らせば良い．
 あらかじめ可能な手を制限する

– 可能な手を制限すると思いもかけない独創的な手
は生まれない
– 定石を覚えて，それを活用する．
– 知識ベースを整備して，利用する．
105
枝刈り・バックトラックの理論的局
面

その先に解が無い枝のみを刈れれば理想的
– ＭＡＸ（その先のゲーム状態の評価値）が勝ち・解
でなければその枝を刈ればよい．
106
知識ベース
ゲームの解析でも，現在重用されている．
 人工知能の基本方式の多くが分かる．
 知識ベースでは，記憶の方式とその検索方式
が重要
 音声応答システム

– YES・NOと意思表示する各種の受け答えを収集
記録する．
107
知識ベース

ヒューリスティックス
– 理論的根拠は、薄弱あるいは不明であるがその
ようにすれば良い・うまくいくと分かっていること
– 将棋・碁の序盤の手順
• 棒銀とか
108
質問・回答（11月30日）
ＡＮＤ・ＯＲがよく分からない．
評価値が2値で表現できるゲーム，あるいは2値で表現してし
まうとＡＮＤ／ＯＲ探索になります．
Ｆａｚｚｙ？Ｆｕｚｚｙ？
Fuzzyです
ＮＯＲＭ？
説明します．
ＯＸプログラムを将棋向けにすると行数は異なっ
てくるか？
ものすごく変わります．こまの種類がＯＸゲームでは1種類です
．こまの種類が増えるとこまの関係が爆発します．
囲碁や将棋などでは，とてつもない時間がかかる
ようだが？現実のプログラムではどうしてい
るのか？
ヒューリスティックスなどを利用してがんばって枝刈をしている
．
株が非０和であることが納得できない．
株が値上がりすれば，株の資産価値が上昇します．全体で価
値が上昇するので多くの人が儲かって，損をする人の損
を上回ります．
最小・平均・最大の関係がよく分からなかった．
説明します．
人工知能で人間くらいの判断ができるためには，
どのくらいのスペックが必要か？
単純なアルゴリズムで実現しようとすると膨大なスペックが必
要になります．逆に，人に遜色ないアルゴリズムを実現で
きれば現在の高性能パソコンレベルですむはずです．
109
すごい計算機でやると100日かかるところがど
のくらいの時間でできるか？
1時間くらいだと思います．１０００倍は十分早いので．
中間試験にプリント持込は不可か？
不可です．一度くらいは覚えてください．もちろん忘れますが．
なぜＭＡＸ－ＭＩＮ探索というのか？
2人０和ゲームの場合，Ａは評価値を最大にしようとします．Ｂ
は，Ａ基準の評価値を最小にしようとします．Ｂ基準の評価値
を最大にすることと，Ａ基準の評価値を最小にすることは同じ
です．
引き分け状態は？（千日手になるの？）
そうです．
評価関数が何をしているのか？
状態空間における状態点の良さを評価します．
評価関数が悪くても時間をかければ結果は同
じになるか？
勝ち負けが正しく判定できるれば，全手数を読みきることで最
適の手を選択可能になります．
評価関数の値をどのように決定するのが良い
か？
これが分かれば問題は解決です．
評価関数は，評価値の大小のことですか？
評価値をもとめる機能のことです．
評価関数は全探索と幅優先探索のどっちな
のか，よく分からない．
さまざまなものがあります．例示プログラムでは幅優先探索＋
状態空間点評価です．
量子コンピュータの完成に期待大
量子コンピュータで性能が１０００００００倍くらいになっても解
決可能な問題の数はそう増えません．多くの困難な問題は，多
項式時間では解けないので．
110
○×ゲームプログラムの構造
ＯＸmain
nhyouka
hyouka
teselect
oitemiru
tlong
111
○×ゲームプログラムの実行構造
可能な場所に
おいてみて，
その結果を評
価する．
準備が終わったら
手の選択を開始す
る．
ＯＸmain
teselect
oitemiru
nhyouka
ここを繰り返すこ
とにより必要な手
数読む．
指定された手数先まで手
順を読んで，そこの状態
空間点の評価値を返す．
指定された手数先まで手順を
読むのにteselectを使う．
teselect
oitemiru
112
定理証明（Theorem Proving）

人が数学などの定理を証明することは難
しい。これを計算機に行わせることは一
つの挑戦であった。
命題論理
 述語論理

113
雨が降る日は天気が悪い

これが本当に定理か?
– この言明は何を述べているのか?この言明を計
算機で記述するにはどのような方法があるの
か?
– 任意の（雨が降っている日）の天気は悪い。
– 任意の場所の（雨が降っている日）の天気は悪
い。
– 任意の場所の（（雨が降っている日）の天気は
悪い）。
114
定理？
– 雨が降る日は天気が悪い。
– これが本当に定理か?
– この言明は何を述べているのか?この言明
を計算機で記述するにはどのような方法が
あるのか?
– 任意の（雨が降っている日）の天気は悪い。
– 任意の場所の（雨が降っている日）の天気
は悪い。
– 任意の場所の（（雨が降っている日）の天
115
気は悪い）。
言語


情報を交換する．
自然言語
– 効率重視
– 最低限の通信で情報を交換する
– 自然言語で表現された内容は，それのみでは不完全であ
る．常識で補われて解釈されることを前提としている．
– 論文では，なるべく完全に表現されることを期待されてい
る．
116
定理証明の準備
記号表現への変換
まず，証明する前にその定理があらわし
ている事柄（言明）を明確にすることが
必要である．
 ￢Goodday，FallingRain
 FallingRain ⇒ ￢Goodday
 明確にする：定理証明システムの記述方
式で表現する．

– 機械の表現にしてやる．
117
定理証明システムの記述方式：論理式で
記述する。
 定理証明システム:論理式で与えられた言
明を与えられた公理に基づいて証明する。
 定理証明システム:論理演算を用いて定理
の否定が与えられた公理系と矛盾するこ
とを示す。

118
例:
– 公理：天気が良い⇔青空が広がり心地よく
日が照っている。
– 定理:雨の降る日は天気が悪い。
– ￢定理：雨の降る日は天気が悪くない。⇔
雨の降る日は天気が良い。⇔雨の降る日は
青空が広がり日が良く照っている。：これ
は偽か？
– 人が見れば偽と思える。思えるだけ。これ
を人は証明できるか?これを青木恭太は証明
できるか?これを君たち学生さんは証明でき
るか?
119
定理である
– 公理系→言明
• このとき言明は定理である
– （公理系＝真＆言明＝真）＝真
– (公理系＝偽＆・・・ )=真
– (公理系=真＆言明=偽）＝偽
120
– 定理証明システムの記述方式：論理式で記述
する。
– 定理証明システム:論理式で与えられた言明を
与えられた公理に基づいて証明する。
– 定理証明システム:論理演算を用いて定理の否
定が与えられた公理系と矛盾することを示す。
121
例:
– 公理：天気が良い⇔青空が広がり心地よく
日が照っている。
– 定理:雨の降る日は天気が悪い。
– ￢定理：雨の降る日は天気が悪くない。⇔
雨の降る日は天気が良い。⇔雨の降る日は
青空が広がり日が良く照っている。：これ
は偽か？
– 人が見れば偽と思える。思えるだけ。これ
を人は証明できるか?これを青木恭太は証明
できるか?これを君たち学生さんは証明でき
るか?
122
– 雨が降るということと青空が広がっているこ
ととの関連が公理には記述されていない。人
は各種の知識として我々が確かな事実である
と思っている形で公理を持っているつもりに
なっている。
– 人工知能システムに定理証明を行わせるには，
記号間関係を表現する全ての公理を与える必
要がある。
– 上記の事実が明確になったことも人工知能研
究の成果である。
123
追加公理
公理＋：雨はその元となる雲から降って
くる。
 公理＋：雲は青空を遮る。
 公理＋：雲は日の光を遮る。

124

（雨の降る日）は青空が広がり日が良く
照っている。⇒（雨の元となる雲がある
日）は青空が広がり日が良く照っている。
⇒ある日（雨の元となる雲がある∧青空が
広がり日が良く照っている。）⇒ある日
（雨の元となる雲が青空を遮る∧青空が広
がり日が良く照っている）
125
さらに公理を加える
公理＋＋：雲が被う空と青空の合計が一
定である。
 公理＋＋：雲が空を被うと日が照らない。
 ある日（雨の元となる雲が青空を遮る∧青
空が広がり日が良く照っている）
 天気が悪いと雨が降る。

126
結論

我々の真似をして我々が当たり前である
と思っていることを定理証明システムで
証明させるにさせるには多くの公理と推
論規則を用意しておく必要がある。また，
我々が当たり前と思っていることの多く
は，証明不能な単に多く見られる事実で
あったり，まったく事実でさえなかった
する。証明可能な場合であっても証明す
る為には，我々が常識として持っている
膨大な知識を公理の形で与える必要があ
る。
127
証明過程
公理＝正しいと仮定された言明の集合
 定理＝正しいと証明したい言明
 公理＋￢定理＝言明の集合

– AND・OR標準形
• A∧B∨C∧D
– 証明は，AND項を一つづつ消していく過程
128
命題論理と述語論理
命題論理：言明の論理結合（論理演算子
による演算の組合わせ）
 述語論理：論理変数，全称記号など

– ∀x，Ｘ∧￢Ｘ≡偽

論理演算：∧，∨，￢など。少なくとも完
全性が保障されている演算子の組を含む。
– 例えばnand

言明：？？？？？？？
129
述語論理
命題論理では，命題を真偽だけをもつ変数と
して，その構造は無視した．
 Ｘは，人間である．Ｘは，死すべきものである．
 Is_human(x), Is_motal(x)の２つの論理式を考
える．
 Is_human(x)などの論理変数式は，ｘの値によ
り真になったり偽になったりする．

130

A0∧A1∧ A2⇒Ｂが恒真

A0∧A1∧A2∧￢Ｂが恒
偽

任意，あるを先頭に集
める
A⇒Ｂは，Aが真でBが偽のときのみ偽
(x  D)(y  D) P( x, y)
131

A0∧A1∧ A2⇒Ｂが恒真
– A ⇒ B Aが真であるときBが真，Aが真でないとき何事
も与えない．
– A⇒B １１，０１，００で真，10で偽
– １１，０１→*1∨0*
– *1∨0*全体を否定する．￢（*1∨0*）
– ￢(*1)∧￢(0*)
– ￢B∧ A0∧A1∧ A2

A0∧A1∧A2∧￢Ｂが恒偽
132
スコーレム標準形
(x  D)(y  D) P( x, y)
任意のｘでＰ（ｘ，ｙ）が成立するｙを見るけることができる．
その見つけるｙを与える関数をｆ（ｘ）とする．
(x  D) P( x, f ( x))
これで（ある）は，消える．
133
A0∧A1∧A2∧￢Ｂが恒偽



スコーレム標準形では，任意ののみがある．任意の
ｘｘを省略すれば，
A0∧A1∧ A2⇒Ｂが恒真を示すことはA0∧A1∧A2∧￢
Ｂが恒偽であることを示すことになる．
OR-AND標準形を考える．
– OR-AND標準形では，新しい項が付け加わるにしたがっ
て，偽となる領域が増す．
• 項の数が0個の極限は，偽．
– でもその前に A∧￢A⇒FでFを示す．
• 全体を真とする項が存在しない．
• OR＝MAX
134
AND-OR標準形では？
– AND-OR標準形では，新しい項が付け加わるに
したがって，真となる領域が増える．
•
•
•
•
項の数が0個の極限は，偽．
全体を偽とする可能性のある項が存在しない．
AND=MIN
OR=MAX
135
導出原理
{( A  B)  ((A)  C )}  ( B  C )
上記を推論規則として，下記のように書く．
これを導出原理と呼ぶ．
A  B, A  C
BC
136
導出原理
A  B, A  C
BC
これを繰り返して適用していくと，どんどん変数記号が減
っていく．
最後には，全部消えるかもしれない．
全部消えれば，偽が示されたことになる．
137
述語論理
変数論理式は，真偽が確定しない．
 任意のxにおいてIs_human(x)⇒Is_motal(x)
 上記は，真偽が確定する．
 真偽が単独で確定している命題と
Is_human(x)のように変数値により真偽が確
定する論理式をあわせて作成した論理式を
述語という．

138
導出原理
公理（系）＋言明（証明したい）を示したい。
 公理＋言明の否定は、矛盾するはず。
 公理＋言明の否定が矛盾することを示す。
 公理＋言明の否定を適当に変換すれば、Ｏ
Ｒ／ＡＮＤ標準形に変換できる。
 公理＋言明の否定が矛盾する。

139
導出原理

公理系＝公理集合
– 公理集合中の公理をT0~Tnとすると、そのすべてが真で
ある。
– Ｔ０＊Ｔ１＊…＊Tnが真⇒言明
• Ｔ０＊Ｔ１＊…＊Tn＊￢言明
– これは、ＯＲ／ＡＮＤ標準形となる。

導出原理
– （Ａ＋Ｂ）＊（￢Ａ＋Ｃ）⇒Ｂ＋Ｃ
• 節を使って簡単な一つの節を導く
• これを繰り返して、消していく
140
パーセプション（認知・認識）

音響，画像，触覚などを解釈して，その表現
する環境を認識する．
– 画像→何がどこにある？
• 1枚の画像を見て何が写っているかを知る．
• 連続した画像を見て何が写っているかを知る．
– 音響→何がどっちにある？
• 車のホーン
– 触覚→どんなもの？
• 群盲像をなでる
141
画像の認識

膨大な情報から認識結果を得る．
– 情報量を削減する過程
– ７４０ｘ４８０ｘ３Ｂ≒１ＭＢ
– 動画だと1秒に15枚から30枚
• 10秒間の動画像で１５０ＭＢ
– 認識結果は，１ＫＢ程度．
• 情報量は，１／１０００
• 膨大な雑音の中に必要な情報が埋もれている．
142
画像による環境の認識

膨大な情報から周りの環境を認識する．
–
–
–
–
–
見たものの距離も分かっている．
見たものの塊も分かっている．
見えないものを含めて塊が分かっている．
塊の名前が分かっている．
塊の役割も分かっている．
143
画像による環境の認識

見たものの距離も分かっている．
– 3次元空間の認識

見たものの塊も分かっている．
– 3次元空間中のオブジェクト認識

見えないものを含めて塊が分かっている．
– 3次元空間中のオブジェクト認識

塊の名前が分かっている．
– 環境の意味付けがなされている．

塊の役割も分かっている．
– 環境におけるオブジェクト間の関係を分かっている．
144
画像による環境の認識

見たものの距離も分かっている．
– 3次元空間の認識
– 距離の認識
• ステレオ画像処理
– 人の目と同じ
• 多眼画像処理
– 目の数が増えると処理量は多くなるが，解釈の曖昧性が減少する
• 映像処理
– 時間的に異なっているが，カメラあるいはオブジェクトが移動してい
れば，多数カメラと同じ画像系列が得られる．
– ステレオと異なりオブジェクト自体の変形や照明の変動や移動によ
る見えの変動が重畳している
145
画像による環境の認識

見たものの塊も分かっている．
– 3次元空間中のオブジェクト認識
• 距離が得られていれば，3次元座標が得られるので，
画像中では連続しているものも途切れていることが分
かる．
• 3次元形状も分かる
– 隠蔽の理解
• カメラに近いオブジェクトのためにカメラから遠いオブ
ジェクトが隠される．
• 一つのオブジェクトのカメラから遠い面は見えない．
146
画像による環境の認識

見えないものを含めて塊が分かっている．
– 3次元空間中のオブジェクト認識
– 見えない部分を含めて，そのものの形状を推定する．
• 映像なら以前見た情報を元に見えていない部分も推定する．

塊の名前が分かっている．
– 環境の意味付けがなされている．
• 見えている部分および形状が推定されている部分から既知
のものと対応付ける．
• 顔の認識（撮影条件を制限することで可能となっている）
– 見えているオブジェクトに目，耳，口，鼻などの認識
– 顔の個人識別
147
画像による環境の認識

塊の役割も分かっている．
– 環境におけるオブジェクト間の関係を分かっている．
– 机の上のコップは，机に支えられている．
– 机の上のコップは，机に接着されているわけではなく，摩
擦で位置が保持されている．
– 扇風機は，空気をかき混ぜることで部屋の温度の上下方
向の差を減少させている．

塊の内部状態を推定する．
– 前で講義をしている先生は，機嫌が良さそうだ．
– 左から2番目の計算機の調子が悪そうだ．
– この患者さんは，胃の調子が悪そうだ．
148
画像による環境の認識

塊の機能を理解する．
–
–
–
–

扇風機のスイッチを入れれば動作する．
コンセントを引き抜けは，止まる．
塊の入出力関係を理解している．
普通は，ここまで分かっていればほぼ完璧．
塊の内部状態を推定する．
– 塊の内部機構を理解している．
• 重力の発生機構を理解している．
149
画像による環境の認識

見たものの距離も分かっている．
– 3次元空間の認識

見たものの塊も分かっている．
– 3次元空間中のオブジェクト認識

見えないものを含めて塊が分かっている．
– 3次元空間中のオブジェクト認識

ここまでは，画像のみを基にしてできる可能性がある．
ここからは，画像のみを基にしてできる可能性はない．知能システムとしての知
識処理などがぜひとも必要．

塊の名前が分かっている．

– 環境の意味付けがなされている．

塊の役割も分かっている．
– 環境におけるオブジェクト間の関係を分かっている．
150
映像認識例

映像中の動きオブジェクトを認識
– 四角がオブジェクト外接長方形
– 円が信頼度
– 線が動きベクトル




ここまで分かれば，車，バイク，人の区別はつきそう
木の枝・葉は，かすかに揺れている．
手前のアスファルト面はほとんど模様がない部分が
ある．
人は，きわめてゆっくり動いている．
151
映像認識例
152
映像認識例
高速小移動物体
 変化が激しい
 さまざまな動きのオブジェクトが存在する
 カメラワークの変化もある

153
トップダウンとボトムアップ

トップダウン
– 見つけたいものが分かっている．
• テンプレートマッチング
– 定規に会う画像部分を見つける
– ＬＳＩの位置決め
» 高速，高精度が達成されている．
• 人の顔を見つける．歩いている人を見つける．走って
いる車を見つける．
• 顔の部品を見つける．
154
トップダウンとボトムアップ

ボトムアップ
– 見つけたいものが分かっていない．
– 一定の条件で見つけたものを報告する．
• 進入検知，動き物体検出
– 条件が厳しければ，簡単．条件が一般的であれ
ば困難．
155
画像認識
通常は，トップダウンとボトムアップの組み合
わせ．
 ボトムアップ

– まったく見たいものが分かっていないと検出結果
の出力形式も決まらない．

トップダウン
– 完全に見たいものが分かっている場合は，テンプ
レート（定規）マッチングで容易にうまくいく
• 人工知能にはならない（画像工学）
156
認識レベル

何が写っているか？
– 白い丸いものが写っている．

写っているものは何か？
– 人が写っている．

写っている世界は，どのようなものか？
– カメラの10ｍ前方に身長１７４ｃｍの男性が立っている．

写っている人は，何をしているのか？
– 計算機に向かって仕事をしている．

写っている人は，何を考えているのか？
– 心配事を心に持って考え込んでいるの？
157
認識レベル
写っている現場写真から犯人を推定する．
 部屋の写真から住んでいる人の性格を推定
する．
 これらのことを人は行う．
 人工知能システムの究極の認識レベルは，こ
こまで．．．

158
音声認識



人の発声は，さまざま
必然的に自然言語処理が加わる．
会話シナリオに基づく音声認識
–
–
–
–
計算機が会話の主導権を握って会話を進める．
まともな人の答えは，限られる．
YES/NOだけを答えさせる．
各種の肯定的答えと否定的答えを収集して照合する．
• はい，そうです／いいえ，ちがいます，
• 男．．，男性．．夫，彼，女．．女性，妻，彼女
• いち，ひとつ，わん，いっこ，はじめ，さいしょ，いちばんめ，
159
音声認識



いかに自然にシナリオに誘導していくか？
目的が決定していれば，シナリオの準備も容易．
チケット予約
– 誰の，どこの，いつの，どんな席の，くらいがわかれば良
い．
– 分からないときは，オペレータに回す．．．．
• これが使える場合は，シナリオをサボって実用的なシステ
ムを組める．
• 99％がシナリオ通りであれば，コールセンターの人員を大
幅に削減できる．
160
音声認識


自由発話は，がんばっているがまだまだ．
人が行っても大変．
– テープから原稿を起こす．
– テープを吹き込んだ本人が行えば楽．別人が行えば大変．


会話状況が分からなければ，解釈のしようがない．
人は，そのまま原稿になるような話方はしない
161
音声認識
実用システムでは，音声認識もサボって，電
話でボタンを押させている．
 シナリオの充実が自由発話に近づく道か？

– トップダウン

発話モデルの充実
– どのように発音が変動するか？
– どのように発音されるか？
– ボトムアップ
162
音声認識実用例

カーナビ
– 施設
– 会社
– 機能

限定シナリオ，限定会話
– 単語数は多い

雑音の多い環境でがんばっている
– 資金の投入
– 膨大なデータベースの維持・管理
• 新しい施設ができる．古い施設がなくなる
163
GPS(General Problem Solving)
一般問題解決(問題解決)
 定理証明では，論理演算の積み重ねとし
て定理を証明しようとしていた。問題解
決では，我々の知っている問題を定義す
る方法とその問題を解決する為に利用可
能な手段を記述する方法を与える。その
もとで与えられた問題を与えられた手段
の組合わせで解決する方法を求める。

164
問題の定義と手段の定義
問題解決では，問題をどのように定義し，問
題を解決する為に利用可能な手段をどのよう
に定義するかが課題となる。
 問題を適切に定義し,問題を解決する為に利
用可能な手段を適切に定義できれば，問題
解決の大部分は成功したことになる。

165
例：乗り換え案内(実用化)



問題：AからBまで人が移動する。利用可能な手段：鉄道, 飛
行機および徒歩(乗り換えのための駅構内の移動および近
い駅間の移動)。選択基準：費用，時間，乗り換え回数など。
すでにパソコンソフトとして売られている。また，ネットワーク
で無償でサービスされている．では，その実態は何かと言う
と，経路探索である。ネットワーク中の経路探索は，難しい問
題である。賢くない探し方をすると，ループの中で迷ってしま
う。
実際に利用してみると役立つ。知らなかった乗り換えパタン
を知ることが出来るし,意外と安くて速い経路が見つかる。今
は誰もこの様なソフトを人工知能ソフトと呼ばないかもしれな
いが昔の人工知能そのものである。
166
自動車用ナビゲーションシステム
（実用化）
目的地を入力すると目的地に到達するため
の経路を発見・表示する．
 前記乗り換え案内に比較して困難

– 選択可能な経路が膨大
167
ナビの仕掛け

位置：ＧＰＳによる絶対位置検出＋移動経路
マッピング
– ＧＰＳで絶対位置は，検出可能．±１５ｍ程度の
誤差
• 計測誤差＋地図誤差
– 絶対位置近傍の移動経路に当てはまる道路へ
の割付
• 仮定：：道路を走っている．
168
ナビの仕掛け

幹線道路＋枝道
– 全道路をすべて探索すると長距離の探索に膨大
な時間を消費する．
• 幹線道路で現在地と目的地の近傍を結ぶ
• 現在地と現在地近傍を全道路で探索する．
• 目的地と目的地近傍を全道路で探索する．

バグつきナビも売られていた．
– 青木の車のナビはバグつきです．
• ループありの経路を探索する．
169
ナビの仕掛け

最新のナビでは，運転者の意図を把握しよう
としている．
– 下記の意図を運行経路から判定する
•
•
•
•
道の間違い
近道選択
寄り道
提示ルート無視
170
ナビの仕掛け

知能システムの目標
– 人の意図を測る
– 推測した意図を実現する方法を考え出す

上記の2つが両方とも高いレベルで実現され
る必要がある．
– 人のやってほしいことを取り違えていては問題外
– 正しく人の意図を推定しても，それを実現する方
法を考え出せなければ無意味
171
自動診断（人）



問題：各種の検査などの結果を見て,そのような病
状を示す病気を見つける。（健康体からそのような
病状を示すに至る道筋を見つける。）
利用可能な手段：各種の病気。個人差。
困難：診断を間違えた責任を誰が取るのか?決して，
自動診断の結果が人の医師と比較して悪いわけで
もない。でも，人の医師であれば問題とはされない
ような誤診が機械では許されない。自動診断システ
ムが売り出される可能性はあるか？個人が自分の
為に利用するソフトとして売り出される可能性はある。
172
自動診断（機械）




問題：各種の検査などの結果を見て,そのような故
障状況を示す故障箇所を見つける。（その様な故障
状態を示すに至る道筋（故障箇所・故障状態を見つ
ける。）
利用可能な手段：各種の故障箇所。
困難：なし．各種機械に導入されている．
例：
– 計算機のＰＯＳ．正常か否かを検査して報告する．
– エアコンの表示．各種故障・点検項目を表示する．
173
自動診断（機械）の困難

診断する機械（ソフト＆ハード）自身を誰が診断する
のか？
– 中核となる部分を定義して，その無故障を仮定する．
– 計算機ならプロセッサ．
• プロセッサとＢＩＯＳＲＯＭの一部が正常と仮定する．
– プロセッサなら基本命令セット
• 8086基本命令セットが正常に動作すると仮定する．
– ＯＳからＯＳの中核
• ＯＳの中核（計時インタラプト処理）が正常に動作していると
仮定する．
174
昔の研究具体例:モンキーバナナ
登場するもの:サル,木箱,棒，バナナ。
 問題：部屋の中に箱と棒が置いてある。天井
から吊られているバナナを取って食べる。バ
ナナは,飛びついても届かない。箱に乗っても
届かない。棒を持っても届かない。
 手段:サルは木箱を動かすことが出来る。サ
ルは棒を持って振り回すことが出来る。サル
はバナナを持って食べることが出来る。

175
モンキーバナナ


人ならバナナを見て，届きそうだったら，取ろうとす
る。取れなかったら飛びついて取ろうとする。だめな
ら部屋の中に何かないかと探す。箱を見つけて箱を
バナナの下に動かしてその上に乗って取ろうとする。
だめなら箱の上で飛んで取ろうとする。だめなら棒
があったのを思い出して，棒を持って箱の上に乗っ
て取ろうとする。それでもだめなら箱に乗って棒を持
って飛んで取ろうとする。
解：木箱をバナナの下に動かして,棒を持って木箱に
乗って棒でバナナをたたいて取る。
176
問題の記述と利用可能な手段の
記述
状態空間記述，
 猿,箱,バナナ,棒の3次元位置
 状態空間に関するオペレータ
 C:P⇒S


どのように問題を解決すべきかの基準を与え
る必要がある。
177
C:P⇒S
Ｃ：条件
 Ｐ：前の状態
 Ｓ：後の状態
 条件が満たされているとき，状態Ｐを状態Ｓ
へ変えることができる．
 サルが箱の隣にいるとき（Ｃ），箱の横のサル
（Ｐ）は箱の上に登れる（Ｓ）．

178
アルゴリズムの表現


条件付き手続き
awk
–
–
–
–
パターン処理言語
条件に一致するとき動作する．
手続き表現から条件表現へ
C:動作
• 条件Cが満たされれば，動作を実行する
– awk '/^0 1 /{print $4,$5}‘
• 先頭が0 1の行があれば，そこの4番目と5番目を書き出す
179
知識表現
知識を如何に表現するか？
 知識は，アルゴリズム，モデル．
 知識は，ハード，ソフト

– オートマトンと言語理論
• アルゴリズム．言語
• モデル．オートマトン
我々が容易に表現できる方法は？
 計算機で容易に処理できる方法は？

180
モデル

構造のあるモデルを構築
– 男→人→哺乳類→動物→生物
• 階層構造を表現する手立てを与える．
• 上位階層で定義されていることを下位階層で再度定
義する必要がない．
• フレームシステム
• オブジェクトの概念
– C++
– samllTalk(Zerox)
181
概念の継承
より上位の概念を下位は引き継ぐ
 a_kind_of

– フレームシステムで概念を引き継ぐ

a_class_of
– オブジェクト言語で手続きを引き継ぐ
182
まとめ
カーナビを見ると，昔の研究では人工知能と
いわれた各種機構の塊となってきている．
 カーナビは，情報提示のみなので問題が起こ
りにくい．
 社会と知能システムの関わりがこれから次第
に問題となってくるであろう．

183

Download Report