内容
計算機科学入門(応用編)
言語と情報
„
“言語”を人工知能(Artificial Intelligence)の
視点から考察する
„
„
パターン認識
形式文法を用いた構文解析
山本章博
情報学研究科 知能情報学専攻
(工学部 情報学科)
計算機科学と“言語”(1)
自然言語処理技術の発展
„
基礎
„
„
„
„
„
„
形態素解析・品詞同定
構文解析
意味処理
音声認識
人工言語
„
„
void main() {
init x; x = x+1;
}
応用
„
„
„
„
„
„
機械翻訳・自動翻訳
談話理解
情報検索,情報抽出
文書要約
かな漢字変換,スペルチェッカ
DNA解析
„
„
計算機科学と“言語”(2)
„
プログラミング言語(C, C++, Java, Scheme,…)
マークアップ言語(HTML, XML,…)
自然言語
„
„
文の構成要素と伝達(1)
意 図
日本語,英語,ドイツ語,…
私は京都が好きです.
I like Kyoto.
„
人間がコンピュータに指示する
コンピュータが別のコンピュータと交信する
文構造と意味が定義されている
人間が人間に意図を伝える
文構造と意味は人間の知的活動中に成立
構文,意味が曖昧
美しい水車小屋の乙女
Time flies like an arrow.
意 味
構 文
は
が
語の連接
文字・音素
わ た し は きょ う と が す き で す
信号波形
1
言語の構成要素と伝達(3)
文の構成要素と伝達(2)
意 図
意 味
構 文
意 図
意 図
意 味
意 味
構 文
構 文
語の連接
語の連接
文字・音素
文字・音素
信号波形
信号波形
S
NP
N
VP
V
NP
N
語の連接
文字・音素
I
like Kyoto
信号波形
TCP/IP プロトコルの階層
言語の構成要素と伝達(3)
意 図
伝えたい内容・意図
意 図
意 味
意 味
構 文
構 文
語の連接
語の連接
文字・音素
文字・音素
信号波形
信号波形
HTTP
アプリケーション層
トランスポート層
ネットワーク層
TCP
IP
Ether
アプリケーション層
トランスポート層
ネットワーク層
ネットワークアクセス層
ネットワークアクセス層
ハードウェア
ハードウェア
信号のデジタル化
„
音声: 連続した空気の振動
„
画像: 連続し光の振動
„
信号の特徴と音素・文字の抽出
„
時間方向に1次元
空間方向に2次元
0111001111110
1100001100111
0000001111…
2
(離散)Fourier級数
標本化定理
関数 f (θ ) は f (θ ) = f (θ + 2π)を満たすと仮定
f (θ ) = a0 + Σk=1Κ (ak cos kθ + bk sin kθ )
k: 周波数
と表すことが目標
„ 区間 [0, 2π) に等間隔に設定したN個の観測点
θ n = 2π / n
n = 0, 1, 2,..., N-1
での値 f (θn ) から, f (θ ) が決定できるか?
„
„
N ≥ 2K+1のとき
級数 f (θ ) = a0 + Σk=1Κ (ak cos kθ + bk sin kθ ) の
係数ak ,bk はf (θn )から決定可能である.
f (θ ) = Σn=0Ν −1 f (θn ) φ (θ− θn )
φ = (1+2 Σk=1Ν/2 cos kθ ) / Ν
特徴の抽出(1)
„
特徴の抽出(1)
音声認識では フォルマント(formant):
f (θ )を構成する正弦波の周波数に着目
„
音声認識では フォルマント(formant):
f (θ )を構成する正弦波の中で, いくつかの周波数
のもののエネルギーが高い
„
周波数の低い順に第1フォルマント, 第2フォルマント,...
長尾真: パターン情報処理
コロナ社
Wikipedia
三角関数から指数関数へ
„
1の原始N乗根: ω = cosθ1 + i sin θ1
Euler の公式 eiθ = cosθ + i sin θ
„
f (θ ) = a0 + Σk=1Κ (ak cos kθ + bk sin kθ )
と表す代わりに,
f (θ ) = Σk= 0Ν F(k) eikθ
と表すことを目標にする
F(k) : f (θ )の離散Fourier変換
„
„
離散Fourier変換
高速Fourier変換 (FFT)
3
特徴空間で例の分類(1)
„
多数の発音データを収集して, 各特徴を座標
軸とする座標で表示
特徴空間で例の分類(2)
„
クラスC1, C2の境界線をどのように引くか?
„
クラス C1
クラス C2
„
データに偏りがあると,重心(分散を最小にする
点)間の垂直2等分線は正しく機能しない可能性
がある.
クラス C1
クラス C2
重心
新しいデータ が得られたとき, どの発音と識
別すべきか?
cf. 事例ベース
パーセプトロン(Rosenblatt)
„
„
簡単のため, 2クラスの分類を考える
問題の定式化
データを分離する線形識別関数
„
„
(視覚)神経を模倣した機構として考案
パーセプトロン学習アルゴリズム
„
„
„
パーセプトロン学習(1)
線形識別関数をデータから構成する
線形分離可能であれば,必ず求められる
データを読み込むたびに識別が正確になっていくので“機
械学習”の一種とみなされる
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 + ρ x に置き換える
xn ∈ D かつ (w, xn) > 0
w を w − ρ x に置き換える
それ以外は何もしない
4. n = 1,2,…, N に対して
xn ∈ C かつ (w, xn) < 0 またはxn ∈ D かつ (w, xn) > 0
を満たすものがなければ終了. そうでなけば3へもどる.
4
句構造文法(1)
文法を“句の構造を生成するための規則”とと
らえる
例 I like Kyoto.
„
文の構造の解析
(文(名詞句(代名詞I )) (動詞句(他動詞 like) (名詞句(固有名詞 Kyoto))))
HTML(XML)風に
<文>
<名詞句> <代名詞> I </代名詞> </名詞句>
<動詞句> <他動詞> like </他動詞>
<名詞句> <固有名詞> Kyoto</固有名詞> </名詞句>
</動詞句>
</文>
句構造文法(2)
生成規則: α→β という形の規則
例 文 → 名詞句 動詞句
名詞句 → 代名詞
動詞句 → 動詞
名詞句 → 固有名詞
動詞句 → 動詞 名詞句
名詞句 → 冠詞 名詞
...
...
代名詞 → I 代名詞 → you 代名詞 → he …
固有名詞→ Kyoto 固有名詞→ Tom …
動詞 → like 動詞 → have …
„
文法による導出(例)
文 |− 名詞句 動詞句 |− 代名詞 動詞句
|− 固有名詞 動詞句 |− I 動詞句
|− I 動詞 名詞句 |− I like 名詞句
|− I like 固有名詞 |− I like Kyoto
文 |− 名詞句 動詞句 |− 代名詞 動詞句
|− 固有名詞 動詞句 |− Tom 動詞句
|− Tom 動詞 名詞句 |− Tom have 名詞句
|− Tom have 冠詞 名詞 |− Tom have a 名詞
|− Tom have a bag
句構造文法(3)
„
生成規則 α→β のα, βは
非終端記号(構文要素)
„
文, 名詞句, 動詞句,代名詞,動詞, ...
終端記号(単語・文字)
の有限列
„ 文法 G : 生成規則の集合
と非終端記号,終端記号,文全体(開始)を表す非終端
記号
„
Gによって生成される文: “文” に生成規則を有
限回適用して得られる終端記号列
文法による導出(例2)
式→式+式
式→式*式
式 → a, b, c
非終端記号: 式
終端記号 : a, b, c, +, *
開始記号 : 式
式 |− 式 + 式 |− a + 式 |− a +式 * 式
|− a + b * 式 |− a + b * c
5
文法による導出(例3)
A→aABC
A→aBC
aB→ab
bB→bb
cC→bc
非終端記号: A, B, C
終端記号 : a, b, c
開始記号 : A
CB→BC
bC→bc
構文解析
„
„
A |− ... |− a a a B C B C B C|− ...|− a a a B B B C C C
|− ... |− a a a b B B C C C |− ... |− a a a b b b C C C
|− ...|− a a a b b b c c c
形式言語理論
言語を文字列・単語列の集合と抽象化した上で
„ 文を生成(構成・定義)するための理論
„
„
文を受理するための理論
„
„
正しい文字列・単語列を生成(定義)する
送られてきた文字列・単語列が正しいかどうかを
判定する
句構造文法と受理機械
単語(文字)の列σ が与えられたとき, “文”
から始まりσ で終わる導出を構成する.
I like Kyoto
ある文法を用いると,一つの単語(文字)の
列σ に対して異なる2種類以上の導出が構
成されることがあるとき,その文法は曖昧で
ある.
a+b*c
文法の型
„
文脈自由文法(context free) 文法中の全て
の生成規則α→β について,αが非終端記
号一つであるもの
„
生成規則に制限を加えることで,様々な文法の
型が導入できる.
0型
句構造文法
Turing Machine
1型
文脈依存文法
線形有界オートマトン
2型
文脈自由文法
非決定性プッシュダウ
ン・オートマトン
3型
正則文法
有限状態オートマトン
6
ダウンロード

4/16