Comments
Description
Transcript
人工知能，HCI (1)
情報科学基礎 2016年7月12日
人工知能，HCI (1)
西田豊明
Copyright © 2016 Toyoaki Nishida All Rights Reserved.
人工知能とは
知能を持つマキナ
知能
心
心を持つマキナ
“Deus Ex Machina” (「機械仕掛けの神」)
知能とは何か，心とは何か？
最近の映画では…
•
•
•
『ロボット』 (Enthiran)
http://www.masala-movie.com/robot/
『her/世界でひとつの彼女』 (her)
http://her.asmik-ace.co.jp/movie01.html
『Ex Machina』
http://trailers.apple.com/trailers/independent/exmachina/
人工知能の過去～現在
1971
自然言語理解システム
SHRDLU
コンピュータグラフィクスでシミュレートされた「積み木の世
界」で，英語表現を状況や変化と対応づけて理解して動作する
「ことばがわかる」ロボットアームを実現した．
http://hci.stanford.edu/winograd/shrdlu/
1985
絵を描くAIアーティスト
AARON
絵画という創造を要する領域でも，知覚に訴える表現の技法を捉
えれば作品を生成できることを示した．創作のプロセスを理解す
るための研究として重要．
http://www.scinetphotos.com/aaron.html
http://www.aaronshome.com/aaron/index.html
1989
自律走行自動車
ALVINN
ニューラルネットワークを使った画像認識によって，道路の視覚
的特徴をハンドル操作に対応づけるレーン追跡方式の自律走行車
の草分け．
http://repository.cmu.edu/cgi/viewcontent.cgi?article=2874&context=compsci
1997
チェスコンピュータ
IBM Deep Blue
スーパーコンピュータで，かなり先まで駒の動きを予測し，膨大
な可能性のなかから最善手を推定することで，チェスの世界チャ
ンピオンに勝る棋力を実現できることを示した．
https://www.research.ibm.com/deepblue/home/html/b.shtml
2004
NASA火星探検ロボット
Mars Exploration Rover
利用可能な資源を使って，与えられた状況においてミッョン達成
のための最善の行動計画を立案する人工知能システムMAPGENが搭
載された火星探査ロボット．
http://www.nasa.gov/centers/ames/research/exploringtheuniverse/spiffy_prt.htm
2011
Google Self-Driving Car
センサー情報，GPS情報，地図データを総合して，道路状況を
認識しながら走行する．重い責任が問われる生活空間での実
用レベルに達した人工知能の草分け．
http://www.google.com/selfdrivingcar/reports/
http://www.google.com/selfdrivingcar/
2011
質問応答システム
IBM Watson
クイズ番組で出題される問題文を読解し，膨大なデータに基づい
て解答を生成する．解答の確信度に基づく戦略的な行動もする．
2011年に人間のチャンピオンに勝った．
http://www-03.ibm.com/innovation/us/watson/index.shtml
2011
音声アシスタント
Apple Siri
汎用性が高く，天気予報やカレンダーなどのアプリとも連携する
音声対話システム．iOSに組み込まれて一般消費者にリリースさ
れ，実際に使われ始めた．
http://www.apple.com/jp/ios/siri/?cid=MAR-JP-GOOG-IPHONE
20113
災害救助の領域で高度な自律制御機能をもつヒューマノイドロ
DARPA
ボットのコンテスト．Atlasロボットなど，ユーザが高度な人工
ロボティクスチャレンジ
知能を組み込める研究用共通基盤が登場した．
http://www.ii.ist.i.kyoto-u.ac.jp/?p=3333&lang=ja，http://www.ii.ist.i.kyoto-u.ac.jp/?p=3351&lang=ja
http://www.bostondynamics.com/robot_Atlas.html
http://www.theroboticschallenge.org/
人工知能と社会
Up side
• 困難な問題の解決
• 人間の解放
Down side
•
•
•
•
•
技術の乱用 … 悪意，善意
責任能力の破たん … 製造者，所有者，使用者
モラルの危機 … SIが解決
人工物への過度の依存 … 人類は脆弱に
人間の職を奪う
大格差
機械の進歩はこんなジョークまで生んでいる―「近代的な繊維工場では，人間を一人と犬を一頭しか雇わ
ない．人間の仕事は犬にエサをやること，犬の役割は人間を機械に触れさせないこと」 (訳書 p. 11）
あなたが好むと好まざるとにかかわらず，ビジネスの現場であなたが対峙する相手は，機械の知能を活用
するようになるだろう…相手とのやりとりを機械の知能にリアルタイムで解析させる…機械の分析は，完璧
である必要はない．ほぼ完璧である必要すらない．人間よりも質の高い分析ができれば，それで十分に意
味がある． (訳書 p. 15～16）
マーケティングの重要性が高まる背景には，今日の世界を特徴づける二つの要素がある．一つは，所得格
差が拡大していること．もう一つは人々の関心の争奪戦が激化していることだ． (訳書 p. 29）
もう一つの新しい潮流は，経済的価値の測定が容易になるにともない，多くの人の職業生活が昔よりも過
酷になることだ． (訳書 p. 32）
ここまで見てきたのは，「労働市場の二極化」と呼ばれる現象だ．…労働者が次第に二つのグループに―
労働市場で大きな成功を収める人たちと，非常に恵まれない境遇に置かれる人たちに―わかれはじめてい
るのだ． (訳書 p. 46）
人間のプレーヤーが対局中にコンピュータプログラムの助言を仰ぐ試合形式が生まれたのだ．それが「フ
リースタイル・チェス」である． (訳書 p. 57）
それ以上に問題なのは，新しく創出されている雇用の中身だ．そう，すでに述べたように，中賃金の職より，
低賃金の職のほうが多く生まれているのである． （訳書 p. 67）
Cowen, Tyler. Average is Over: Powering America beyond the Age of the Great Stagnation. Dutton. 2013. (邦訳) 池村，大格差，NTT出版
テクノロジーが変容させる人間社会
職業
•
•
•
•
•
Rifkin, Jeremy. The End of Work: The Decline of the Global Labor Force and the Dawn of
the Post-Market Era. G. P. Putnam’s Sons, 1995.
（大失業時代：「技術革新は職業を消滅させる」）
Kurzweil, Ray. The Singularity is Near: When Humans Transcend Biology. Viking Penguin,
2005. （技術的特異点：技術革新による超人間的知性の出現）
Brynjolfsson, Erik; McAfee Andrew. Race Against the Machine. Digital Frontier Press, 2011.
（機械との競争：機械に勝てる人間の数は激減しつつある）
Gratton, Lynda. The Shift: The Future of Work is Already Here. Harper Collins Pub., 2011.
（ワークシフト：「自分だけにしかできないことを見つけよう」）
Cowen, Tyler. Average is Over: Powering America beyond the Age of the Great Stagnation.
Dutton. 2013. （大格差：「機械の知能による仕事と所得の変容」）
スーパー知能
•
•
•
•
Nick Bostrom. Superintelligence: Paths, Dangers, Strategies. Oxford University Press,
Oxford, 2014.
Erik Brynjolfsson and Andrew McAfee. The Second Machine Age. W.W. Norton & Company,
New York, 2014.
Nicholas Carr. The Glass Cage: Automation and Us. W. W. Norton & Company, 2014.
James Barrat. Our Final Invention: Artificial Intelligence and the End of the Human Era. St.
Martin's Griffin, 2015.
シンギュラリティ（技術的特異点）
人工知能の知性が（それを作りだした）人間の
知性を超える日．
Kurzweil, Ray (2005). The Singularity is Near. New York: Viking Books.
IEEE Spectrum 2008年6月号
http://spectrum.ieee.org/biomedical/ethics/signs-of-the-singularity
“The AI Scenario: We create superhuman artificial
intelligence (AI) in computers.”
“The IA Scenario: We enhance human intelligence
through human-to-computer interfaces--that is, we
achieve intelligence amplification (IA).”
理想郷の恐怖
Alone Together
Alone Together picks up these two strands in the story of digital culture over the past fifteen years,
with a focus on the young, those from give through their early twenties – “digital natives” growing up
with cell phones and toys that ask for love.
(p. xii)
“Twice a week and I stay on the call for an hour,” [Ellen] told me. It should have been rewarding;
instead, when I met her, Ellen was unhappy. She knew that her grandmother was unaware that
Skype allows surreptitious multitasking. … Ellen’s multitasking removed her to another place. … I
have often observed this distinctive confusion: these days, whether you are online or not, it is easy
for people to end up unsure if they are closer together or further apart. I remember my own sense of
disorientation the first time I realized that I was “alone together”.
(p. 13～14）
In 1983, thirteen-year-old Bruce talked about robots and argued for the unique “emotionality” of
people. Bruce rested his case on the idea that computers and robots are “perfect,” while people are
“imperfect.” flawed and frail. … But for Bruce it was human imperfection that makes for the ties that
bind. … Twenty-five years later, … , Howard [, fifteen, ] thinks the robot would be better able to grasp
the intricacies of high school life: “Its database would be larger than Dad’s. Dad has knowledge of
basic things, but not enough of high school.” Howard hopes that robots might be specially trained to
take care of “the elderly and children” – something he doesn’t see the people around him as much
interested in.
(p. 51)
Once coupled with My Real Baby, Edna gives the impression of wanting to be alone – “together”
only with the robot.
(p. 117)
Turkle, Sherry. Alone Together: Why We Expect More from Technology and Less from Each Other. Basic Books, 2011.
これからのAI
人工知能
人間社会
共有基盤
西田豊明．人工知能とは(2)，人工知能学会誌，28巻2号，pp. 326-335, 2013.
草稿：http://www.ii.ist.i.kyoto-u.ac.jp/wordpress/wp-content/uploads/2013/06/人工知能とは何か-西田豊明-2012-12-30-1405.pdf
西田豊明．人工知能研究半世紀の歩みと今後の課題，情報管理 Vol. 55, No. 7, pp. 461-471, 2012.
http://dx.doi.org/10.1241/johokanri.55.461
Toyoaki Nishida．The Best of AI in Japan – Prologue. AI Magazine. 2012, Vol. 33, No. 2, pp. 108-111
http://www.aaai.org/ojs/index.php/aimagazine/article/view/2358/2288
AIの主な手法
発見的探索
知識の表現と利用
機械学習・データマイニング
http://www.ii.ist.i.kyoto-u.ac.jp/?p=3333&lang=ja，http://www.ii.ist.i.kyoto-u.ac.jp/?p=3351&lang=ja
発見的探索—状態空間探索
状態空間探索問題(state space search problem)とは，
・状態集合 S
・初期状態 s0 S
・状態に適用される述語 P : S {T, F}
・基本操作の集合
O : {oi | oi ( s1 ) s2 }
s1 , s2 S
が与えられたとき，
P(o jn ( o j1 ( s0 ) )) T
となる操作の系列 o j1 , , o jn を求めよ，という問題である．
[西田 1999]
状態空間探索と8パズル
2
4
3
7
2
7
4
6
2
3
5
3
1
8
7
1
2
8
7
3
4
6
?
6
5
1
8
6
2
4
4
5
3
5
1
8
7
1
6
8
2
4
6
3
1
5
7
8
状態集合:可能な盤面の集合
初期状態:可能な盤面のうちの一つ、任意に与えられる。
目標状態:整った状態
基本操作:板を上下左右のうちの一方向に動かす(高々4通り)
5
[西田 1999]
基本的な探索アルゴリズム
横型探索 (breadth-first search)
(setq open-list (initialize-open-list))
(loop
(if (null open-list) (return nil))
(setq node (pop open-list))
(if (p node) (return node))
(setq x (expand node))
(setq open-list (append open-list x)))
0
1
3
9
2
3
1 6 4
8 7 5
2 3
1 6 4
8 7 5
10
1 2 3
6 4
8 7 5
4
青字のところは個別に定義する
2 3
1 6 4
8 7 5
2
2
3
1 6 4
8 7 5
5
2 3
1 6 4
8 7 5
11
12
2
3
1 6 4
8 7 5
2 3 4
1 6
8 7 5
13
2 6 3
1 4
8 7 5
6
2 6 3
1
4
8 7 5
14 15
2 6 3
1
4
8 7 5
2
3
1 6 4
8 7 5
16
2 6 3
1 7 4
8
5
17
1 2 3
6 4
8 7 5
7
1 2 3
6
4
8 7 5
18 19
1 2 3
6 4
8 7 5
1 2 3
6 4
8 7 5
1
3
6 2 4
8 7 5
20
1 2 3
6 7 4
8
5
2 3
1 6 4
8 7 5
21
2
3
1 6 4
8 7 5
1 2 3
8 6 4
7 5
8
22
1 2 3
6 4
8 7 5
23
24
1 2 3
8 6 4
7
5
1 2 3
6 4
8 7 5
[西田 1999]
基本的な探索アルゴリズム
縦型探索 (depth-first search)
(setq open-list (initialize-open-list))
(loop
(if (null open-list) (return nil))
(setq node (pop open-list))
(if (p node) (return node))
(setq x (expand node))
(setq open-list (append x open-list)))
0
1
青字のところは個別に定義する
2 3
1 6 4
8 7 5
2
3
1 6 4
8 7 5
1 2 3
6 4
8 7 5
2
2 3
1 6 4
8 7 5
2 3
1 6 4
8 7 5
2 6 3
1
4
8 7 5
1 2 3
6
4
8 7 5
2 3
1 6 4
8 7 5
1 2 3
8 6 4
7 5
3
2
3
1 6 4
8 7 5
1 2 3
6 4
8 7 5
2
3
1 6 4
8 7 5
2 3 4
1 6
8 7 5
2 6 3
1 4
8 7 5
2 6 3
1
4
8 7 5
2
3
1 6 4
8 7 5
2 6 3
1 7 4
8
5
1 2 3
6 4
8 7 5
1 2 3
6 4
8 7 5
1
3
6 2 4
8 7 5
1 2 3
6 7 4
8
5
2
3
1 6 4
8 7 5
1 2 3
6 4
8 7 5
1 2 3
8 6 4
7
5
1 2 3
6 4
8 7 5
[西田 1999]
基本的な探索アルゴリズム
深さ制限縦型探索 (depth-limited search)
(setq open-list-2 (mapcar #'(lambda (x) `(,0 ,x)) open-list))
(loop
(if (null open-list-2) (return nil))
(setq pair (pop open-list-2))
(setq d (first pair))
(setq node (second pair))
(if (p node) (return node))
(cond ((< d depth-limit)
(setq expanded (expand node))
(setq a (mapcar #'(lambda (x) `(,(1+ d) ,x)) expanded))
(setq open-list-2 (append a open-list-2)))))
0
depth-limit=2の場合
1
青字のところは個別に定義する
2 3
1 6 4
8 7 5
5
2
3
1 6 4
8 7 5
1 2 3
6 4
8 7 5
2
2 3
1 6 4
8 7 5
2
3
1 6 4
8 7 5
1 2 3
6 4
8 7 5
3
4
2 3
1 6 4
8 7 5
2
3
1 6 4
8 7 5
2 3 4
1 6
8 7 5
2 6 3
1 4
8 7 5
6
2 6 3
1
4
8 7 5
2 6 3
1
4
8 7 5
2
3
1 6 4
8 7 5
2 6 3
1 7 4
8
5
1 2 3
6 4
8 7 5
7
1 2 3
6
4
8 7 5
1 2 3
6 4
8 7 5
1
3
6 2 4
8 7 5
1 2 3
6 7 4
8
5
2 3
1 6 4
8 7 5
2
3
1 6 4
8 7 5
8
1 2 3
6 4
8 7 5
1 2 3
8 6 4
7 5
1 2 3
8 6 4
7
5
1 2 3
6 4
8 7 5
[西田 1999]
基本的な探索アルゴリズム
反復深化探索 (iterative deepening search)
(setq depth 0)
(loop
(setq result (depth-limited-search depth …))
(if result (return result))
(setq depth (1+ depth)))
2 3
1 6 4
8 7 5
2
3
1 6 4
8 7 5
2
16
2
3
1 6 4
8 7 5
2 3
1 6 4
8 7 5
7 18
1
4
13
3
1 2 3
6 4
8 7 5
5 14
6 15
2 3
1 6 4
8 7 5
0
8
2 6 3
1
4
8 7 5
17
19
20
22
23 24
1 2 3
6 4
8 7 5
2
3
1 6 4
8 7 5
2 3 4
1 6
8 7 5
2 6 3
1 4
8 7 5
2 6 3
1
4
8 7 5
2
3
1 6 4
8 7 5
1 2 3
6
4
8 7 5
21
25
2 6 3
1 7 4
8
5
28
1 2 3
6 4
8 7 5
10
29 30
1 2 3
6 4
8 7 5
1
3
6 2 4
8 7 5
2 3
1 6 4
8 7 5
27
9
26
11 32
1 2 3
8 6 4
7 5
31
33
34
36
1 2 3
6 7 4
8
5
2
3
1 6 4
8 7 5
1 2 3
6 4
8 7 5
1 2 3
8 6 4
7
5
12
35
37
1 2 3
6 4
8 7 5
[西田 1999]
ヒューリスティックを用いた状態空間探索
状態空間探索では，コスト関数が与えられ，初期状態から最小コストで解に至る操作
系列を見つけることが求められることが多い．
操作系列 p {o1 ,, on } のコスト c( p ) が
c( p) c(oi )
…
p を構成する各操作 ci のコスト p(ci) の和
i
で与えられる場合，状態 s を経由して最小コストで解に至る操作系列のコストを f(s) と
すると，
f ( s ) g ( s ) h( s )
である．
s0
どのノードを経由すれば最小コス
トで解に至るかわからないし，
我々が興味を持つ問題については，
探索過程では，h(s) はわからない
（わかるのは簡単すぎる問題）．
g (s )
s
h(s )
h(s) の代わりに推定値 h’(s) を用い
る（h’はヒューリスティック関数
と呼ばれる）．
解： sを経由する解のなかでコストが最小となるもの
[西田 1999]
ヒューリスティック探索の代表的方法
- 山登り法：h’(s)しか考慮しない．局所的な最適性を追求する．
- 最良優先探索： h’(s)しか考慮しない．大域的な最適性を追求する．
- A*アルゴリズム： g(s)+h’(s)を考慮する．大域的な最適性を追求する． h’(s)が
楽天的ヒューリスティック（常に，h' ( s ) h( s ) ）ならば，最初に見つける解
の最適性が保証される．
s0
g (s )
s
h' ( s )
解
[西田 1999]
山登り法
(setq open-list (mapcar #'(lambda (x) `(0 0 ,x)) open-list-3))
(loop
(if (null open-list-3) (return nil))
(setq item (pop open-list-3))
(setq state (third item))
(if (p state) (return state))
(setq d0 (state-expander state))
(setq d (mapcar
#'(lambda (x)
`(,(h- (second x))
,(+ g (first x))
,(second x)))
d0))
(setq e (add-to-open-list-for-a-star d nil))
(setq open-list-3 (append e open-list-3)))
青字のところは個別に定義する
s0
g (s )
s
h' ( s )
解
[西田 1999]
最良優先探索
(setq open-list-3 (mapcar #'(lambda (x) `(0 0 ,x)) open-list))
(loop
(if (null open-list-3) (return nil))
(setq item (pop open-list-3))
(setq state (third item))
(if (p state) (return state))
(setq d0 (expand state))
(setq d (mapcar
#'(lambda (x) `(,(h- (second x))
,(+ g (first x))
,(second x))) d0))
(setq open-list-3 (add-to-open-list-for-a-star d open-list-3)))
青字は関数引数
s0
g (s )
s
h' ( s )
解
[西田 1999]
A*アルゴリズム
(setq open-list-3 (mapcar #'(lambda (x) `(0 0 ,x)) open-list))
(loop
(if (null open-list-3) (return nil))
(setq item (pop open-list-3))
(setq g (second item))
(setq state (third item))
(if (p state) (return state))
(setq d0 (expand state))
(setq d (mapcar
#'(lambda (x)
`(,(+ g (h- (second x)))
,(+ g (first x))
,(second x))) d0))
(setq open-list-3 (add-to-open-list-for-a-star d open-list-3)))
青字は関数引数
s0
g (s )
s
h' ( s )
解
[西田 1999]
A*アルゴリズムの探索範囲と最適性
最適解をsk，非最適解をslとする：
s0
sk
g ( sk ) g ( sl )
H {si | g ( si ) h' ( si ) g ( sk )}
sl
g ( si ) h' ( si ) g ( si ) h( si ) g ( sk ) h' ( sk ) g ( sk ) g ( sl ) h' ( sl ) g ( sl )
であるので，最適解skが出力される前に非最適解slが出力されることはない
[西田 1999]
発見的探索—問題分割法
O
A
OR分岐
B
C
AND分岐
D
E
F
G
H
I
J
OR分岐
L
M
N
P
Q
[西田 1999]
問題分割法 ― 不定積分
x 1
x3 1 dx
f ( x) g ' ( x)dx f ( x) g ( x) f ( x) g ' ( x)dx
OR分岐
x2
2
x2
3 x
x
x
2
2
dx
2
3
3
x 1
x 1
2
1
x 1
3
3 ( 2 x 1)
x3 1 x 1 x 2 x 1
2 1
1
2x 1
dx
dx
3 x 1
3 x2 x 1
AND分岐
1
x 1 dx
2x 1
x 2 x 1 dx
[西田 1999]
問題分割法 ― ゲーム
黒、白、黒、白と石が置かれ、次は黒の手番。
…
…
[西田 1999]
基本minimax法
(defun maximizer (state max-expander max-evaluator min-expander min-evaluator)
(let* (descendants x (result *minfty*))
(setq descendants (apply max-expander `(,state)))
(cond
((null descendants) (apply max-evaluator `(,state)))
(t (dolist (d descendants)
(setq x (minimizer d
max-expander max-evaluator
min-expander min-evaluator))
(if (> x result) (setq result x)))
result))))
(defun minimizer (state max-expander max-evaluator min-expander min-evaluator)
(let* (descendants x (result *pinfty*))
(setq descendants (apply min-expander `(,state)))
(cond
((null descendants) (apply min-evaluator `(,state)))
(t (dolist (d descendants)
(setq x
(maximizer d
max-expander max-evaluator
min-expander min-evaluator))
(if (< x result) (setq result x)))
result))))
[西田 1999]
基本minimax法の動き
評価値：大きいほど自分にとって有利
＋∞：勝利，－∞：敗北
∞
∞
2
1
∞
2
3
∞
-∞
5
-∞
4
2
∞
-∞
2
-∞
7
∞
∞
1
∞
1
[西田 1999]
深さ限度付きminimaxアルゴリズム
(defun maximizer-depth-bound (state max-expander max-evaluator min-expander min-evaluator max-depth)
(let* (descendants x (result *minfty*))
(cond ((<= max-depth 0) (apply max-evaluator `(,state)))
(t (setq descendants (apply max-expander `(,state)))
(cond ((null descendants) (apply max-evaluator `(,state)))
(t (dolist (d descendants)
(setq x (minimizer-depth-bound d
max-expander max-evaluator
min-expander min-evaluator
(1- max-depth)))
(if (> x result) (setq result x)))
result))))))
(defun minimizer-depth-bound (state max-expander max-evaluator min-expander min-evaluator max-depth)
(let* (descendants x (result *pinfty*))
(cond ((<= max-depth 0) (apply min-evaluator `(,state)))
(t (setq descendants (apply min-expander `(,state)))
(cond ((null descendants) (apply min-evaluator `(,state)))
(t (dolist (d descendants)
(setq x (maximizer-depth-bound d
max-expander max-evaluator
min-expander min-evaluator
(1- max-depth)))
(if (< x result) (setq result x)))
result))))))
[西田 1999]
深さ限度付きminimax法の動き
定められた深さ限度（例えば，3）に
達したら評価値計算
(3)
評価値：大きいほど自分にとって有利
＋∞：勝利，－∞：敗北
(1)
(3)
1
(1)
(4)
3
∞
(4)
(2)
(-7)
(0)
(1)
[西田 1999]
評価関数の例
3目並べに対する評価関数の一例：
f(s)：勝敗が自明の局面 s では，－∞（相手の勝ち），0（引き分け），＋∞
（自分の勝ち）のいずれかとする．そうでない局面 s では，自分の石
を３つ連続して並べることのできる縦横斜め筋の数から， 相手の石を
３つ連続して並べることのできる縦横斜め筋の数を差し引いたものを
値とする．
s=
を黒の立場から評価する
黒が３つ並べるこ
とができるのは
３通り
f ( s ) 3 4 1
白が３つ並べる
ことができるの
は４通り
[西田 1999]
評価関数の使用例
黒、白、黒、白と石が置かれ、次は黒の手番。
赤は真の値，（青）は評価値
0
0
1
0
-1
0
1
-1
-1
0
0
-1
-2
-1
-2
-1
-2
-1
0
-1
0
0
-1
-2
-2
-1
[西田 1999]
α-β探索
(1) αカット
(2) βカット
a
b
(3) 深いところで枝刈り
a
a
c
b
10
b
c
10
4
d
e
-1
f
c
d
e
d
e
8
e
f
h
g
i
j
-5
[西田 1999]
α-βカット適用前
黒、白、黒、白と石が置かれ、次は黒の手番。
赤は真の値，（青）は評価値
0
0
1
0
-1
0
1
-1
-1
0
0
-1
-2
-1
-2
-1
-2
-1
0
-1
0
0
-1
-2
-2
-1
[西田 1999]
α-βカット適用後
黒、白、黒、白と石が置かれ、次は黒の手番。
赤は真の値，（青）は評価値
0
0
1
0
0
1
-1
-1
0
-1
[西田 1999]
α-β探索
(defun alpha-depth-bound (state max-expander max-evaluator min-expander min-evaluator max-depth alpha beta)
(let* (descendants x (result *minfty*))
(cond ((<= max-depth 0) (apply max-evaluator `(,state)))
(t (setq descendants (apply max-expander `(,state)))
(cond ((null descendants) (apply max-evaluator `(,state)))
(t (dolist (d descendants)
(setq x (beta-depth-bound d
max-expander max-evaluator
min-expander min-evaluator
(1- max-depth)
result beta))
(cond ((null x))
((<= beta x) (setq result nil) (return))
((> x result) (setq result x))))
result))))))
(defun beta-depth-bound (state max-expander max-evaluator min-expander min-evaluator max-depth alpha beta)
(let* (descendants x (result *pinfty*))
(cond ((<= max-depth 0) (apply min-evaluator `(,state)))
(t (setq descendants (apply min-expander `(,state)))
(cond ((null descendants) (apply min-evaluator `(,state)))
(t (dolist (d descendants)
(setq x (alpha-depth-bound d
max-expander max-evaluator
min-expander min-evaluator
(1- max-depth)
alpha result))
(cond ((null x))
((>= alpha x) (setq result nil) (return))
((< x result) (setq result x))))
result))))))
[西田 1999]
実験用データ
1
3
5
1
3
2
4
2
-∞
4
10
∞
5
-7
2
-∞
1
0
7
∞
∞
∞
1
応用 オセロゲーム
置かれた黒石によって黒に反転した白石
黒石が置かれたところ
(1)
最初の盤面
(2a) ある盤面(次は黒)
(2b) 黒石の置けるところ
(2c) 次の盤面
応用 オセロゲーム
120
-20
20
5
5
20
-20
120
-20
-40
-5
-5
-5
-5
-40
-20
20
-5
15
3
3
15
-5
20
5
-5
3
3
3
3
-5
5
5
-5
3
3
3
3
-5
5
20
-5
15
3
3
15
-5
20
-20
-40
-5
-5
-5
-5
-40
-20
120
-20
20
5
5
20
-20
120
評価関数の例
[Novig 1992]
知識の記号的な表現と利用
[西田 1999]
知識の記号的な表現と利用
講義室
共有表示
演者
表示装置
聴衆
[西田 1999]
知識の記号的な表現と利用
講義室
共有表示
包含
包含
表示
包含
演者
表示装置
操作
前
注目
注目
聴衆
[西田 1999]
知識の記号的な表現と利用
講義室
共有表示
包含
包含
表示
包含
演者
表示装置
操作
前
注目
注目
聴衆
[西田 1999]
知識の記号的な表現と利用
講義室
- プロトタイプ的知識の表現と利
用：
共有表示
包含
- プロトタイプ：典型性の高い関連し
た情報をパッケージ化したもの。
個々の個体に関する情報を表すフ
レーム
包含
表示
包含
演者
表示装置
操作
前
注目
聴衆
注目
- フレーム型知識表現言語
- クラスフレーム
- 類似の個体の集まりに関する情
報を表す
- インスタンスフレーム
- 特定の状況を表す
- slot-filler構造
- 属性-属性値（attribute-value）
対の集まり
- 継承と概念階層
- 知識の多次元化
- 知識ベースの中の知識の構造
化のメカニズムを提供する。
- デフォールト（暗黙値、default）
- データ駆動型の手続き呼び出し。
デーモンとサーバント
[西田 1999]
知識の記号的な表現と利用
superCリンク
もの
植物
動物
無機質
哺乳類
動物・♂
人間
男
魚類
動物・♀
女
馬
下位概念は上位概念の性質を継承
[西田 1999]
知識の記号的な表現と利用
スクリプト：(欧米の）レストラン(概要）
登場人物：客Ｓ、ウェイター(ウェイトレス）Ｗ、コックＣ、店長Ｏ
起動条件：Ｓが空腹、Ｓが金を持っている。
結果：Ｓが満腹になる、Ｓの金が減る、Ｏの金が増える。
シーン：
•Ｓ１：Ｓが店に入る。
•Ｓ２：ＷがＳをテーブルに案内する。
•Ｓ３：ＳがＷに注文する。
•Ｓ４：Ｃが注文された料理をつくる。
•Ｓ５：Ｗが料理をＳのところにもっていく。
•Ｓ６：Ｓが料理を食べる。
•Ｓ７：Ｓが支払いをし、チップを残す。
•Ｓ８：Ｓが店を出る。
逸脱のタイプ：
•障害：スクリプトの進行を妨げる状態や行為
•障害物：行為を可能にする条件が欠けている
•エラー：行為の失敗や予想外の結果
•転向：行為者が新しいゴールをもち、一時的または永久にス
クリプトから離れる。
与えられた文章：
ジョンはレストランに行きま
した。ステーキを注文しまし
たが、切ろうとして床に落と
してしまいました。
解釈
障害の発生による
スクリプトの中断
[西田 1999]
記号的な推論
- プロダクションシステム
〈条件1〉, …, 〈条件n〉→〈行動〉
〈条件1〉, …, 〈条件n〉の全てが成立すると〈行動〉をする
実行系
[西田 1999]
プランニング
アクション： precondition, add-list, delete-listで表現。
precondition: アクションを実行するための前提条件
add-list: アクションが実行された結果、成立する述語
delete-list: アクションが実行された結果、成立しなくなる述語
初期条件
at(A, Home)
available(Food, SuperMarket)
available(CharCoal, SuperMarket)
permitted(SeaShore, BBQ)
move(x, y,z) ; xがyからzに移動する
precondition: at(x, y)
add-list: at(x, z)
delete-list: at(x, y)
buy(x, y, z) : xがzでyを購入する
precondition: at(x, z)
available(y, z)
add-list: has(x, y)
delete-list: -
目標
happy(A)
with(A, B)
bbq(x, y) : xがyでバーベキューをする
precondition: at(x, y)
permitted(y, BBQ)
has(x, Food)
has(x, CharCoal)
add-lost: happy(x)
delete-list: -
call-friends(x, y) ; xが友人yを呼ぶ
precondition: at(x, y)
add-list: with (x, y)
delete-list: -
[西田 1999]
プランニング
初期条件
at(A, Home), available(Food, SuperMarket), available(CharCoal, SuperMarket), permitted(SeaShore, BBQ)
move(A, Home, B) ; AがHomeから友人B宅 に移動する
at(A, B)
call (A,B) ; Aが友人Bを呼ぶ
at(A, Home)
move(A, B, SuperMarket) ; Aが友人B宅からSuperMarket に移動する
at(A, SuperMarket)
buy(A, Food, SuperMarket) : AがSuperMarketでFoodを購入する
at(A, SuperMarket)
buy(A, CharCoal, SuperMarket ) : AがSuperMarketでCharCoalを購入する
at(A, SuperMarket)
move(A, OutDoorShop, SuperMarket) ; AがSuperMarketからSeaShoreに移動する
完全順序プランニング
at(A, SeaShore), Permitted(SeaShore, BBQ),
has(A, Food), has(A, CharCoal)
bbq(A, SeaShore) : AがSeaShoreでバーベキューをする
目標 happy(A), with (A, B)
[西田 1999]
プランニング
初期条件
at(A, Home), available(Food, SuperMarket), available(CharCoal, SuperMarket), permitted(SeaShore, BBQ)
at(A, Home)
move(A, Home, B) ; AがHomeから友人B宅 に移動する
at(A, B)
at(A, B)
call (A,B) ; Aが友人Bを呼ぶ
move(A, B, SuperMarket) ; Aが友人B宅からSuperMarket に移動する
at(A, SuperMarket)
buy(A, Food, SuperMarket) : AがSuperMarketでFoodを購入する
at(A, SuperMarket)
buy(A, CharCoal, SuperMarket ) : AがSuperMarketでCharCoalを購入する
at(A, SuperMarket)
move(A, OutDoorShop, SuperMarket) ; AがSuperMarketからSeaShoreに移動する
at(A, SeaShore), Permitted(SeaShore, BBQ),
has(A, Food), has(A, CharCoal)
半順序プランニング
bbq(A, SeaShore) : AがSeaShoreでバーベキューをする
目標 happy(A) , with (A, B)
因果リンク
保護リンク
[西田 1999]
階層的プランニング
ヨセミテ旅行する
旅行準備
パスポート手配
移動
自宅から空港まで
フライト
交通手段手配
空港からヨセミテまで
[西田 1999]
英語における場所表現
the potatoes are in the bowl.
じゃがいもは器の内部にある。
器の壁に含まれているのではない。
じゃがいもは完全に器の内部に
含まれていなくてもよい。
the crack in the vase
この場合は、花瓶の容器が欠けている
と考えなければならない。
the bird is in the bush.
the potato is not in the bowl.
じゃがいもは器の内部にあるが、
器がひっくり返っている。
鳥の占めている場所の一部は、しげみの
占めている場所の可視部分の内部に包含される。
[Herskovits 1987; 西田 1999]
英語における場所表現
the hole in the wall
the dust on the bowl.
ほこりは器の上にあり、
容器に付着している。
穴の場所（穴の空く前の）壁の標準化
された領域に包含されている。
the ladder on the wall
はしごは壁より高いところに置かれて
いるわけではない
*the milk on the bowl
ミルクの占める位置が器の上にあっても
"on"は使えない。
[Herskovits 1987; 西田 1999]
英語における場所表現
客観論者
the potatoes are in the bowl.
[Herskovits 1987; 西田 1999]
英語における場所表現
規範的見方
理想化、近似、概念化、選択
この場合は許容シフト
the potatoes are in the bowl.
[Herskovits 1987; 西田 1999]
場所表現の解釈の枠組み
場所表現
英語前置詞の理想的な意味を少数の単純な幾何学
的概念によって捉える。
英語前置詞の理想的な意味からの逸脱を、語義シ
フトと許容シフトに分類。
語義シフト：文脈における意味が理想的意味
と定性的に異なる場合
許容シフト：理想的意味からのずれが定量的
であり、適合の度合の程度の差に留まる
英語前置詞の理想的な意味からの逸脱のいくつか
を語用論的な要因によって説明。語用論的な要因
として、顕現性、関連性、許容、典型性を考慮。
場所表現の意味を、標準的な状況のもとでその表
現が正しくかつ適切に用いられていると言えるた
めの条件の集合（標準状況型）として表わす。
英語前置詞の理想的な意味からの逸脱を全て語用
論的な要因によって説明することはできない。そ
のような場合は、逸脱は使用型の違いとして説明
する。
英語の投影的前置詞（相当句）の意味を捉えるた
めに、参照枠、基軸、実行観測点、仮想観測点な
どの概念を導入する。
理想的意味
使用型
許容シフト
語義シフト
状況型
標準状況型
目的
[Herskovits 1987; 西田 1999]
場所表現の解釈の枠組み
標準状況型
- 標準性とは ⇔
プロトタイプ性：最良の例
- 常識的な物理法則に適合すること
- 重力を含む状況
- 対象と標準的な方式で相互作用
- 標準状況型の構造
-
表現の前提
表現によって伝達されるもの
目的
物体の配置とシーン
- 規準的な記述のレベル
- 幾何学的概念化のレベル
- 例えば、Maggie is at her desk.
机のところに座っていて、机を使える状態にある。
マギーと机はともに点とみなされ、同じ位置にある。
- 文脈上の制約
[Herskovits 1987; 西田 1999]
場所表現の解釈の枠組み
目的 -- 話し手が場所表現を使用する目的
- プロトタイプ的目的
- 聞き手が容易にわかるのに十分な、ただし必要以上に煩わしくない程度に空間
的制約を与える。指示物体（探し求められる物体、位置が特定されるべき物体）と
参照物体（位置づけるとき参照される物体；聞き手が知っているか、容易に見つ
けられるものでなければならない）を結び付ける関係。
- 例：The teapot is on the kitchen table ・ Where is the teapot?
- 非プロトタイプ的目的
- 同定：話し手が心に描いている物体を聞き手に同定させる。
- 例：The store at the corner sells cigarettes.
- 推論の暗示：指定される場所から推論される結果に聞き手の注意をひく
- 例：I bought this present in a store on Fifth Avenue
- 関係の強調：物体の特徴をわからせる
- 例：He had bright eyes in a long thin face
- 指示物体の位置以外の説明：例えば、地と字の逆転
- 例：a man in a red hat
[Herskovits 1987; 西田 1999]
場所表現の解釈の枠組み
幾何的記述
- 基本的な幾何的記述関数
- Interior（内部）、Outline（輪郭）、VisiblePart（可視部分）、Place（場所）
- 場所のタイプ
- 通常の固体の対象
- 閉じた表面によって完全に囲まれている物体に占められている空間
- ばらばらな固体物質
- 別々の部分の場所の和。例えば、the sand, the rice
- 固体の対象の集まり
- 結合していない個々の対象の場所の集合。
- 例：There are worms in the strawberries. ・曖昧性
- 液状あるいは気体状の対象
- 漠然と定義された境界をもつことが多い。
- 例： the fog in San Francisco
- 地理的対象 -- 例：the grass and the trees on the meadow
- 部分 -- 例：the seats at the front of the theater
- 幾何的対象 -- 例：The children were standing in a circle.
- 空間の部分 -- 例：There are nice flowers in this place.
- 穴 -- 例: There is a hole in my shirt.
- 境界のない「実体」 -- 例：The fog around me was very thick.
[Herskovits 1987; 西田 1999]
場所表現の解釈の枠組み
幾何的記述関数
- 部分 -- 空間領域をその部分に写像する
- ３次元部分、縁、底面、有向な外面の全体、有向な上の空いた面、下面、上面
- 理想化
- 点への近似、線への近似、面への近似、水平面への近似、帯への近似
- よい形態
- 輪郭、完全化封入、標準化された領域
- 隣接体
- 内部、頂点から連想される立体的領域／平面的領域、表面から連想される薄片
- 軸
- 主軸、連想される観測点
- 投影
- 無限遠の平面への投影、地面への投影
[Herskovits 1987; 西田 1999]
場所表現の解釈の枠組み
３次元部分
- VisiblePart -- 可視部分を取り出す
GroundSurface -- 実体を有向な地面の領域に写像する
例： the tree on the meadow
Contiguous(VisiblePart(Place(Tree)),
GroundSurface(Place(Meadow)))
- Outline -- 幾何的構造物をそのすき間を埋めてなめらかにした形に写像する
例： She is under the tree.
Under(Place(She),
UnderSide(Outline(BranchPart(Place(Tree)))))
- SeatPart -- 椅子の座る部分
例： the child must sit at the back of the chair
AtTheBack(Place(Child), SeatPart(Place(Chair)))
- Head -- 先頭、Front -- 前面
例： the waiting line at the counter
[A(Coincide)](PtApprox(Head(Place(Line))),
PtApprox(Front(Place(Counter))))
[Herskovits 1987; 西田 1999]
場所表現の解釈の枠組み
縁，底面
- Edge -- 縁を取り出す
例： the path along the ocean
[A(Along)](HProj(LineApprox(Place(Path))),
LineApprox(Edge(Place(Ocean))))
- Base -- 最も低い水平面内にある領域の点の集合からなる面を取り出す。
例： The house is above the apartment building.
Above(Base(VisiblePart(Place(House))),
Base(VisiblePart(Place(Building))))
the apartment building
the house
[Herskovits 1987; 西田 1999]
場所表現の解釈の枠組み
語用論上の要因 -- 理想的意味からのシフトが許容される原則
- 顕現性
- 基本的にある対象全体を示す名詞を、典型的に際立って特徴的なその対
象の位置部分によって占められる領域を参照するために使うことができ
る。
- 例： a waiting line at the counter
- ある対象の典型的な可視部分によって占められる領域を参照するため
に、その対象全体を基本的に示すような名詞句を使うことができる。
- 例：There is a rabbit under the bush.
- 適当な幾何的記述は、対象の基盤（すなわち、地面との接触面）について
の場合がある。
- 例：the house above the apartment
- 適当な幾何的記述は、対象を無限遠にある平面上に投影したものである
場合がある。
- 例：The Morning Star is to the left of the church.
- 適当な幾何的記述は、対象を地面に投影したものである場合がある。
- 例：The painting is to the right of the chair.
[Herskovits 1987; 西田 1999]
場所表現の解釈の枠組み
語用論上の要因 -- 理想的意味からのシフトが許容される原則
- 関連性
- 意思伝達上のゴール（＝話し手が表現したいもの、現在の文脈で含意し
たいもの）に関係がある。
- 例１： *the milk on the bowl
- 例２： The bulb is in the socket.
- 許容と理想化
- ２つの対象AとBがある。ある参照物体との位置関係において、Aの方がB
よりも、ある前置詞の意味的関係（もしくは、シフトした理想的意味）が当
てはまるとき、AとBを区別するためにその前置詞を用いることができる。
それにより、その位置に関する句が、Aについてあてはまるものであって、
Bについてではないことが暗黙の前提とされる。（シフト対比原理）
- 例：A is to the right of X.
- 文脈中に格子状のパターンがあり、その格子状のパターンが話し手の立
場に関連がある場合、その格子状のパターンは投影的な前置詞を使う上
での許容を規定する。（背景格子原理）
- 典型性
- 例：The fountain is behind the city hall.
[Herskovits 1987; 西田 1999]
機械学習とデータマイニング
- 機械学習
AIシステムが経験を通して自らの振舞いや知識を改良するた
めの手法
- データマイニング：
データの中から法則性を推定する技術．
データ
分類／予測
分類／予測器
トレーニング用
法則
教師有／無
学習システム
[西田 1999]
決定木学習
決定木
taste?
sweet
good
marginal
mild
size?
L
fair
S
good
fair
分類
データ
分類器
トレーニング用
法則
教師有
学習システム
[西田 1999]
決定木
taste?
sweet
good
marginal
mild
fair
size？
L
good
S
fair
[西田 1999]
決定木の学習 -- 例題
taste
size
surface
decision
sweet
L
shining
good
sweet
sweet
mild
S
S
L
shining
dull
shining
good
good
good
mild
S
shining
fair
marginal
L
dull
fair
marginal
S
dull
fair
marginal
S
shining
fair
[西田 1999]
決定木の例
taste
sweet
sweet
sweet
mild
mild
marginal
marginal
marginal
size
L
S
S
L
S
L
S
S
surface
shining
shining
dull
shining
shining
dull
dull
shining
decision
good
good
good
good
fair
fair
fair
fair
taste?
sweet
good
marginal
mild
size?
L
good
fair
S
fair
[西田 1999]
決定木の例
taste
sweet
sweet
sweet
mild
mild
marginal
marginal
marginal
size
L
S
S
L
S
L
S
S
surface
shining
shining
dull
shining
shining
dull
dull
shining
decision
good
good
good
good
fair
fair
fair
fair
taste?
mild
good
size?
S
good
fair
surface?
dull
shining
dull
taste?
taste?
size?
size?
mild, marginal
sweet
sweet
L
S
L
S
good
good
fair
taste?
sweet, mild,
good
taste?
marginal sweet
fair
fair
L
surface?
shining
marginal
sweet
good
mild, marginal
fair
size?
L
good
good
Mild, marginal
fair
S
fair
[西田 1999]
決定木の良さ
構造の簡単な決定木を優先
オッカムのかみそり(Occum‘s razor)：
与えられたデータと整合する仮説のなかで最も単純なものを優先する．
データ集合SのエントロピーH(S)：
H (S )
p(c) log p(c)
cC ( S )
C(S)： データ集合 S に対する可能なカテゴリの集合
p(c)： カテゴリ c に分類されるデータの割合
[西田 1999]
アルゴリズムID3
(defun id3 (attributes data)
(let* ((possible-classes (get-possible-classes data)) children)
(cond ((= (length possible-classes) 1) (first possible-classes))
((null attributes) '?)
(t (setq children (select-and-split attributes data))
`(,(first children)
. ,(mapcar #'(lambda (x)
`(,(first x)
,(id3 (delete (first children) attributes)
(second x))))
(second children)))))))
(defun get-possible-classes (data)
(let* ((result nil))
(dolist (d data)
(cond ((not (member (second d) result))
(push (second d) result))))
result))
(defun select-and-split (attributes data)
(select-minimal-entropy (find-all-partitions attributes data)))
(defun find-all-partitions (attributes data)
(let* ((result nil) possible-values entropy-attribute-partition)
(dolist (attribute attributes)
(setq possible-values (get-possible-values attribute data))
(setq entropy-attribute-partition (get-partition data attribute possible-values))
(push entropy-attribute-partition result))
result))
[西田 1999]
アルゴリズムID3
(defun get-possible-values (attribute data)
(let* ((possible-values nil) x)
(dolist (d data)
(setq x (second (assoc attribute (cdr (first d)))))
(cond ((not (member x possible-values)) (push x possible-values))))
possible-values))
(defun get-partition (data attribute possible-values)
(let* ((entropy 0) (partition nil) (data-count (length data)) subdata)
(dolist (possible-value possible-values)
(setq subdata nil)
(dolist (d data)
(cond ((equal possible-value (second (assoc attribute (cdr (first d)))))
(push d subdata))))
(setq entropy (+ entropy (* (/ (length subdata) data-count)
(calculate-entropy subdata))))
(push `(,possible-value ,subdata) partition))
`(,entropy ,attribute ,partition)))
(defun calculate-entropy (data)
(let* ((size (length data)) (entropy 0) (possible-classes (get-possible-classes data)) c)
(cond ((= (length possible-classes) 1))
((= size 1))
(t (dolist (possible-class possible-classes)
(setq c (count-if #'(lambda (x) (equal possible-class (second x))) data))
(setq entropy (- entropy (* (/ c size) (log (/ c size) 2)))))))
entropy))
(defun select-minimal-entropy (partitions)
(cdr (first (sort partitions #'(lambda (x y) (< (first x) (first y)))))))
[西田 1999]
頻出集合発見
頻出集合発見
トランザクションデータベース
トランザクション名（取引）
レコード：アイテムの集合
A
1,2,5,6,7,9
B
2,3,4,5
C
1,2,7,8,9
D
1,7,9
E
2,3,7,9
F
2,7,9
トランザクション
アイテム
3つ以上のトランザクションに
含まれるアイテム集合
{1} {2} {7} {9}
{1, 7} {1, 9}
{2, 7} {2, 9} {7, 9}
{1, 7, 9} {2, 7, 9}
データ
頻出集合
頻出集合発見
[西田 1999]
頻出集合発見問題 (frequent itemset mining)
Given：トランザクションデータベース D
例：
t1: {1, 2, 5, 8, 11, 12, 15, 17, 18, 19, 23, 25, 27}
t2: {2, 4, 5, 8, 11, 17, 19, 23, 27, 29}
t3: {1, 3, 5, 6, 7, 8, 9, 10, 14, 15, 21, 25, 26, 30}
t4: {7, 8, 10, 11, 12, 13, 14, 15, 17, 23, 25, 29}
t5: {2, 5, 6, 8, 11, 13, 15, 17, 18, 20, 23, 25, 30}
t6: {2, 3, 7, 8, 12, 13, 15, 17, 18, 23, 26, 29}
Find：頻出度θ以上の頻出集合を全て見つける
例（θ=5の場合）：
大きさ1: {{8}, {15}, {17}, {23}}
大きさ2: {{17, 23}, {8 ,23}, {8, 17}, {8 ,15}}
大きさ3: {{17, 8, 23}}
θ: 閾値（最小サポート）
θが大：解となる頻出集合の数は小さい
θが小：有用な知識をもらさず見つけ出すため，モデルの立場からは望ましい．
[西田 1999]
アプリオリ法
基本アイデア
頻出集合の族の単調性：トランザクション t が頻出集合 X
を含むならば，t は X の任意の部分集合を含む．
⇒ X の部分集合の出現集合は X の出現集合を含み，頻出
度は X より同じか大きくなる．
[西田 1999]
アルゴリズム
アプリオリ法のアルゴリズム
空集合から出発し，幅優先的にアイテムを１つずつ追加していく．
アプリオリ
D1=大きさ1の頻出集合の集合; k:=1
while Dk≠φ
(1) 大きさがk+1であり，Dkの2つのアイテム集合の和集合となっ
ているものを全てDk+1 に挿入する
(2) frq(S)<θ となるSを全てDk+1から取り除く
(3) k := k+1
end while
特長：データベースへのアクセス数の少なさ．
計算時間：
〈候補の総数〉×〈データベースの大きさ〉に比例
〈候補の総数〉は頻出アイテム集合の数のn倍(nはアイテムの数)を超えない．
⇒ 頻出集合１つあたり，最悪でも〈データベースの大きさ〉×nに比例
[西田 1999]
ニューラルネットワーク
― 多層フィードフォーワードネットワーク ―
多層フィードフォーワードネットワーク
出力層
中間層
入力層
分類
データ
分類器
トレーニング用
法則
教師有
学習システム
[西田 1999]
フィードフォーワード型ニューラルネットワーク
出力層
ユニットｊ
中間層
oi
oj
wji
netj=Σwjioi+θj
i
oj(t+1)=fj(netj)
fj ：単調非減少，微分可能
入力層
θj：バイアス
[西田 1999]
ニューラルネットワークを構成するユニット（より一般的なもの）
ユニットｊ
oi
wji
ユニットiから
oj
netj
aj(t+1)
=Σwjioi+θj
= F(aj(t), netj (t))
i
oj=fj(aj)
ユニット j の
出力
aj ： ユニット j の活性度
[西田 1999]
排他的選言(exclusive OR)を計算するためのフィードフォーワード型ネットワーク
x
x
－6.7
7.7
7.7
-3.3
14
-3.9
y
z
0
0
0.0
0
1
1.0
1
0
1.0
1
1
0.0
z
－6.7
y
入力ユニット
出力ユニット
中間ユニット
c は，そのユニットへのバイアスが c であることを示す
[西田 1999]
誤差逆伝播
入力パターン p に対する出力層での誤差
E p E pj (t pj o pj )
1
2
j
2
j
が最小になるように，ユニットmからユニットnへの結合に対応づ
けられている重みwnm各ユニットnのバイアス θnを調節する．Epjは
入力パターンpに対する出力ユニットjにおける誤差(希望出力tpjと
実際の出力opjとの差の2乗の半分)である．
E p
pに対するwnmへの修正： p wnm w
nm
pに対するθ nへの修正：
p n
E p
n
[西田 1999]
誤差逆伝播の基本的な考え方
net pn wnm o pm pn
ユニットn
Ep
m
o pn f n (net pn )
opm
に注意すると
p wnm
p n
wnm
net pn wnm o pm pn
o pn f n (net pn )
opn
m
E p
wnm
E p net pn
net pn wnm
E p
net pn
o pm pn o pm
E p
pn
E p net pn
net pn pn
E p
net pn
pn
E p
ただし， net pn
pn
[西田 1999]
誤差逆伝播の基本的な考え方
ユニット n が出力ユニットのとき
ユニット n
om
pn
on
wnm
netn=Σwjioi+θj
i
on=fn(netn)
出力
E p
net pn
t pn o pn
ユニット n が隠れユニットのとき
pn
ユニット n
ユニットk
om w
nm netn=Σwjioi+θj on=fn(netn)
i
出力
on
1
t pj o pj 2
net pn j 2
o pn
net pn
t pn o pn f n (net pn )
'
E p
net pn
E p o pn
o pn net pn
k
E p net pk
net pk o pn
f n ' (net pn )
pk wkn f n ' (net pn )
k
[西田 1999]
実行例
x
x
2
3
-0.3
3
2
0.7
y
x
z
0
0
0.74
0
1
0.89
1
0
0.98
1
1
0.99
1000サイクル後
x
-3.6
5.9
-2.3
z
5.9
y
x
10サイクル後
1.9
3.0
-0.5
3.0
1.8
-0.2
y
z
0
0
0.61
0
1
0.81
1
0
0.97
1
1
0.97
7.7
-3.3
0.2
1.8
-6.7
7.7
100サイクル後
-0.8
0.13
0
1
0.85
1
0
0.85
1
1
0.17
z
10000サイクル後
z
x
3.3
0
x
x
y
3.1
0
y
-0.0
x
-2.6
z
-3.6
0
x
8.2
y
-1.4
y
z
0
0
0.29
0
1
0.52
1
0
0.60
1
1
0.61
14
-3.9
y
z
0
0
0.00
0
1
0.97
1
0
0.97
1
1
0.00
z
-6.7
y
z
-0.1
y
[西田 1999]
深層学習 (Deep Learning)
x1
x2
x3
…
x4
…
…
x5
…
…
xn
L1
•
L2
L3
L4
L5
Deep Boltzmann Machine (DBM)では，自己符号化器 (Autoencoder)，深層1層ずつ階層ご
とに学習していく（事前学習）
• Convolutional Neural Network (CNN)では，畳み込み層とプーリング層を交互に繰り返す
,
深層学習 (Deep Learning)
自己符号化器 (Autoencoder)
原データ(O)
原データ(R)
2000
RBM1
1000
2000
RBM: Restricted Boltzmann Machine
原データ(O)
[Hinton 2006] Hinton G and Salakhutdinov, R. Reducing the Dimensionality of Data with Neural Networks, Science 313: 504-507
深層学習 (Deep Learning)
原データ(O)
自己符号化器 (Autoencoder)
原データ(R)
Decoder
2000
1000
500
RBM3
RBM2
RBM1
30
500
1000
2000
Encoder
原データ(O)
[Hinton 2006] Hinton G and Salakhutdinov, R. Reducing the Dimensionality of Data with Neural Networks, Science 313: 504-507
深層学習 (Deep Learning)
原データ(O)
自己符号化器 (Autoencoder)
原データ(R)
Decoder
2000
1000
500
RBM3
RBM2
RBM1
30
500
1000
2000
Encoder
原データ(O)
[Hinton 2006] Hinton G and Salakhutdinov, R. Reducing the Dimensionality of Data with Neural Networks, Science 313: 504-507
深層学習 (Deep Learning)
Convolutional Neural Network (CNN)
入力
出力
畳み込み(Convolution)
プーリング(Pooling)
特徴抽出・符号化
画像内で現れる特徴の微小な位置変
化に対する応答の普遍性
[神嶌 2015] 神嶌（編） 深層学習，近代科学社，2015
まとめ
1. 人工知能
a. 人工知能とは
b. 人工知能の発展の歴史
c. 人工知能と社会
2. 発見的探索
a. 状態空間探索
b. 問題分解法
3. 知識の記号的な表現と利用
a. 知識の記号的な表現
b. 記号的な推論
c. 人間の言語行動の説明
4. 機械学習とデータマイニング
a. 決定木学習
b. 頻出集合発見
c. ニューラルネットワーク学習
References
[西田 1999] 西田豊明: 人工知能の基礎, 丸善, 1999.
[Novig 1992] Peter Norvig, Paradigms of Artificial Intelligence Programming: Case Studies in Common
Lisp, Morgan Kaufman, 1992.
[Herskovits 1987] Annette Herskovits, Language and Spatial Cognition: An Interdisciplinary Study of the
Prepositions in English, Cambridge University Press, 1987.
レポート課題 (1/2)
情報科学基礎論13～14回の成績は2回のレポートによって採
点します．
人工知能のもたらす社会的影響の明暗について重要な議論し
ている文献を少なくとも1つあげ，それに基づいて人工知能
技術の研究開発を今後どのように進めていくかについて自分
の考えを2000字以上で論じなさい．なお，文献の出典（Web
の場合はそのURL）は必ず明示すること．採点にあたっては，
深く，独自性が高い考察を評価します．
提出期日
提出方法
7月18日（月） 17:00
メール添付などで[email protected]に送付