ことばとコンピュータ

言語体系とコンピュータ
第7回
本日の内容
• 前回のおさらい
– 文がどんな構造をしているか決める
• 文脈自由文法を使った文構造の解析
• アルゴリズムをちゃんと考えた解析
– CKY法
– チャート法
2
前回のおさらい
• 文がどんな構造をしているか決める
– 文の構造は曖昧なので,複数あることが多い
– ただし,候補の中でありえないものは排除したい
– どんな構造があるかを見つける必要がある
→文として「あり」か,「なし」か
を見極める作業ともいえる
3
前回のおさらい(2)
• ある文字列が文か文でないか?
– どうやって決める?
– 確実なのは母語話者の直感!
• 母語話者でも判定が難しいこともあるけど...
「まじありえなくなくない?」
どちらにせよ.毎回母語話者が必要だとしたら
不便だし, コンピュータでの処理は無理...
• それを克服するには,文法が必要
4
前回のおさらい(3)-文法(1)
• 文脈自由文法(CFG: Context Free Grammar)
G = < VT, VX,VC,PD,PP,σ>
– VT :終端記号
– VX :非終端記号
– VC :前終端記号 ←終端記号の1つ前の状態
– PD :辞書規則の集合
– PP :句構造規則の集合
– σ :初期記号 σ∈ VN
というような記号を使って表現
5
前回のおさらい(4) ー文法(2)
• 文脈自由文法の例
– PP :句構造規則の集合
(1)S→NP VP (4)NP→DET N (7)VP→VP NP
(2)NP→N
(5)VP→V
(8)VP→VP PP
(3)NP→NP PP (6)VP→V NP
(9)PP→Prep NP
– PD :辞書規則の集合
N→ I, apples, garden
V→ eat
Det → the
Prep→ in
6
前回のおさらい(5)
• 手順は気にせず文の構造を決める作業
S
↑
ボトムアップ
I eat
the
apples
in
the garden.
7
前回のおさらい(6)
• 手順は気にせず作業
PP :句構造規則を調べて,句をつくる
NP
NP
以降も最後まで
続けた!
N V
I eat
Det N
the
apples
Prep Det
in
the
N
garden.
8
前回のおさらい(7)
• トップダウンも説明
S
トップダウン
↓
I eat
the
apples
in
the garden.
9
前回のおさらい(8)
S
NP
I eat
the
apples
VP
in
the garden.
10
前回のおさらい(9)
S
NP
I
I eat
VP
VP
I
V
I
I
eat
I eat NP
the
apples
V
in
NP
最後まで
続ける
the garden.
11
アルゴリズムを考えた解析
• ボトムアップとトップダウン
– すでに体験済み
– トップダウン
S →NP VP
規則は左から右へ
S
12
アルゴリズムを考えた解析
• ボトムアップとトップダウン
– すでに体験済み
– ボトムアップ
S →NP VP
規則は右から左へ
S
13
アルゴリズムを考えた解析
• 深さ優先(縦型)探索と幅優先(横型)探索
– 競合する規則をどのように採用していくかの違い
14
アルゴリズムを考えた解析
• 深さ優先(縦型)探索
– とりあえず1つの結果が出るまで探索を進める
– 複数の結果を得るためには,後戻りして結果を探す
1
2
3
4
8
5
6
15
7
17
14
1
1
12
16
10
9
1
3
15
アルゴリズムを考えた解析
• 幅優先(横型)探索
– 最初の頂点から到達可能な頂点を順に探す
1
2
5
3
6
4
109
7
11
14
15
16
16
アルゴリズムを考えた解析
• 比較的枝分かれが少ない場合
– 深さ優先× 幅優先○
• 枝分かれが多い場合
– 深さ優先○ 幅優先×
17
CKY法(Cocke-Kasami-Younger法)
• 制約:
– ボトムアップ型...右辺から左辺への書き換え
– 文法はチョムスキー標準形(結構きつい制約)
• チョムスキー標準形
(右辺が必ず非終端か前終端記号2つ)
A→B C A∈Vx, B,C∈(Vc ∪ Vx)
Vx 非終端記号,Vc前終端記号
18
CKY法(2)
• 文法
句構造規則PP
辞書規則PD
(1)S→NP VP
(5) VP→VP NP
(2) NP→NP PP
(6) VP→VP PP
(3) NP→DET N
(7) PP→Prep NP
(4) VP→V NP
N → I, apples, garden
V → eat
NP→ I, apples, garden
Det → the
VP→ eat
Prep→ in
NP, VPはチョムスキー標準形への対応
19
CKY法(3)
• アルゴリズム
1.単語
数分の
マスを
書く
20
CKY法(3b)
• アルゴリズム
1
2
3
4
5
6
7
1.単語 1
数分の
マスを
書く
2
3
4
5
6
7
21
CKY法(3c)
• アルゴリズム
1
2
3
4
a1,7
5
6
7
1.単語 1
数分の
マスを
書く
2
a1,1
マスの番号
3
4
ai,j
5
6
a7,7
7
22
CKY法(4)
2.辞書規則を元にa1,1から a7,7まで記入
1
2
3
4
5
6
7
1
2
3
4
for (i=1 to n) {
iを1から始めて,nまで以下を繰り返す
ai,i ={A|A→wi∈ PD}
5
6
7
}
23
CKY法(4b)
2.辞書規則を元にa1,1から a7,7まで記入
1
2
3
4
5
6
7
1
2
3
4
for (i=1 to n) {
iを1から始めて,nまで以下を繰り返す
ai,i ={A|A→wi∈ PD}
}
ai,i = a1,1
ai,i = a2,2
ai,i = a3,3
5 ai,i = a4,4
ai,i6= a5,5
ai,i = a6,67
ai,i = a7,7
24
CKY法(4c)
2.辞書規則を元にa1,1から a7,7まで記入
1
2
3
4 i=1 5to n 6do
7
for
N1,NP1
(iを1から始めて,nまで以下を
1 I
繰り返す)
V1,VP1
2 eat
ai,i ={A|A→wi∈ PD}
i=1
Det1
3 the
a1,1
i=2
a2,2 i=3
a3,3
N2,NP2
4
a4,4
apples
5
a5,5
Prep1
in
6
a6,6
i=7
a7,7
Det2
the
7
N3,NP3
garden
25
CKY法(5)
3.句構造規則を適用
1
2
N1,NP1
1 II
3
4
5
6
7
V1,VP1
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
ai,j= ai,j∪
{A|A→BC∈PD,
B∈ai,k, C∈ak+i,j}
}}
eat
Det1
3
the
N2,NP2
4 apples
5
Prep1
in
6
Det2
the
N3,NP3
7 garden
26
CKY法(5b)
3.句構造規則を適用
1
2 d=13
N1,NP1
1 II
4
5
6
7
V1,VP1
i,j= 1,2U(A|A→BC∈Pp,B∈ 1,1,
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
ai,j= ai,j∪
{A|A→BC∈PD,
B∈ai,k, C∈ak+i,j}
}}
eat
a a
a
C∈a2,2)
ai,j=a2,3Det1
U(A|A→BC∈Pp,B∈a2,2, C∈a3,3)
3
the
N2,NP2
ai,j=a3,4U(A|A→BC
∈Pp,B∈a3,3, C∈a4,4)
4 apples
Prep1
ai,j=a4,5U(A|A→BC
∈
inPp,B∈a4,4, C∈a5,5)
5
Det2
ai,j=a5,6U(A|A→BC∈Pp,B6∈athe
5,5, C∈a6,6)
N3,NP3
ai,j=a6,7U(A|A→BC∈Pp,B∈a6,6, C7∈agarden
7,7)
27
CKY法(5c)
3.句構造規則を適用
1
2
N1,NP1
1 II
3
4
5
6
7
V1,VP1
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
eat
Det1
3
the
N2,NP2
4 apples
5
Prep1
in
ai,j= ai,j∪
d=1D,
{A|A→BC∈P
B∈ai,k, C∈
}
ai,j=aak+i,j
1,2U(A|A→BC∈Pp,B∈a1,1, C∈a2,2)
6
Det2
the
N3,NP3
7 garden
}}
28
CKY法(5d)
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
5
6
7
V1,VP1
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
eat
(1)S→NP VP
Det1
3
the
N2,NP2
4 apples
5
Prep1
in
ai,j= ai,j∪
d=1D,
{A|A→BC∈P
B∈ai,k, C∈
}
ai,j=aak+i,j
1,2U(A|A→BC∈Pp,B∈a1,1, C∈a2,2)
6
Det2
the
N3,NP3
7 garden
}}
29
CKY法(5e)
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
5
6
7
V1,VP1
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
eat
Det1
3
the
なし
N2,NP2
4 apples
5
Prep1
in
ai,j= ai,j∪
d=1D,
{A|A→BC∈P
B∈ai,k, C∈
}
ai,j=aak+i,j
2,3U(A|A→BC∈Pp,B∈a2,2, C∈a3,3)
6
Det2
the
N3,NP3
7 garden
}}
30
CKY法(5f)
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
5
6
7
(3) NP→DET N
V1,VP1
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
eat
Det1
3
the
NP4(Det1 N2)
N2,NP2
4 apples
5
Prep1
in
ai,j= ai,j∪
d=1D,
{A|A→BC∈P
B∈ai,k, C∈
}
ai,j=aak+i,j
3,4U(A|A→BC∈Pp,B∈a3,3, C∈a4,4)
6
Det2
the
N3,NP3
7 garden
}}
31
CKY法(5g)
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
5
6
7
V1,VP1
2
eat
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
ai,j= ai,j∪
d=1D,
{A|A→BC∈P
B∈ai,k, C∈
ak+i,j}
つづけます
Det1
3
the
NP4(Det1 N2)
N2,NP2
4 apples
5
Prep1
in
6
Det2
the
N3,NP3
7 garden
}}
32
CKY法(5h)
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
6
7
(3) NP→DET N
V1,VP1
2
5
eat
Det1
3
the
NP4(Det1 N2)
N2,NP2
4 apples
5
Prep1
in
ai,j= ai,j∪
d=1D,
{A|A→BC∈P
B∈ai,k, C∈
}
ai,j=aak+i,j
6,7U(A|A→BC∈Pp,B∈a6,6, C∈a7,7)
6
Det2
NP5(Det2 N3)
the
N3,NP3
7 garden
}}
33
CKY法(5i)
3.句構造規則を適用
1
2 d=2 3
4
5
6
7
N1,NP1 S1(NP1 VP1)
ai,j=a1,3U(A|A→BC∈Pp,B∈a1,1,C∈a2,3)
1 II
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
ai,j= ai,j∪
{A|A→BC∈PD,
B∈ai,k, C∈ak+i,j}
}}
V1,VP1
eat i,j= 1,3U(A|A→BC∈Pp,B∈ 1,2,
a a
a C∈a3,3)
Det1 NP4(Det1 N2)
ai,j=athe
2,4U(A|A→BC
∈Pp,B∈a2,2, C∈a3,4)
3
N2,NP2
ai,j=a2,4U(A|A→BC
∈Pp,B∈a2,3, C∈a4,4)
4 apples
ai,j=a3,5U(A|A→BC∈PpPrep1
,B∈a3,3, C∈a4,5)
in
5
ai,j=a3,5U(A|A→BC∈Pp,B∈a3,4, C
∈a5,5NP5(Det2
)
Det2
N3)
the
ai,j=a4,6U(A|A→BC∈Pp,B∈6a4,4, C∈a5,6N3,NP3
)
garden
ai,j=a4,6U(A|A→BC∈Pp,B∈a4,5, C∈7a6,6
)
ai,j=a5,7U(A|A→BC∈Pp,B∈a5,5, C∈a6,7)
ai,j=a5,7U(A|A→BC∈Pp,B∈a5,6, C∈a7,7)
34
CKY法(5j)
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
5
6
なし
V1,VP1
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
7
eat
Det1
3
the
NP4(Det1 N2)
N2,NP2
4 apples
5
Prep1
in
ai,j= ai,j∪
d=2D,
{A|A→BC∈P
B∈ai,k, C∈
}
ai,j=aak+i,j
1,3U(A|A→BC∈Pp,B∈a1,1,C∈a2,3)
6
Det2
NP5(Det2 N3)
the
N3,NP3
7 garden
}}
35
CKY法(5k)
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
5
6
なし
V1,VP1
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
7
eat
Det1
3
the
NP4(Det1 N2)
N2,NP2
4 apples
5
Prep1
in
ai,j= ai,j∪
d=2D,
{A|A→BC∈P
B∈ai,k, C∈
}
ai,j=aak+i,j
1,3U(A|A→BC
∈Pp,B∈a1,2, C∈a3,3)
6
Det2
NP5(Det2 N3)
the
N3,NP3
7 garden
}}
36
CKY法(5l)
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
7
VP2(VP1 NP4)
eat
Det1
3
6
(5) VP→VP NP
V1,VP1
2
5
the
NP4(Det1 N2)
N2,NP2
4 apples
5
Prep1
in
ai,j= ai,j∪
d=2D,
{A|A→BC∈P
B∈ai,k, C∈
}
ai,j=aak+i,j
3,4U(A|A→BC
∈Pp,B∈a3,3, C∈a4,4)
6
Det2
NP5(Det2 N3)
the
N3,NP3
7 garden
}}
37
CKY法(5m) d=5
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
V1,VP1
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
ai,j= ai,j∪
{A|A→BC∈PD,
B∈ai,k, C∈ak+i,j}
}}
5
6
7
VP2(VP1 NP4)
eat
Det1
3
the
NP4(Det1 N2)
N2,NP2
4 apples
d=3
5
Prep1
in
6
d=4
Det2
NP5(Det2 N3)
the
N3,NP3
7 garden
d=n-1=6
38
CKY法(5n)
3.句構造規則を適用
1
2
3
N1,NP1 S1(NP1 VP1)
1 II
4
V1,VP1
2
for (d=1 to n-1) {
for (i=1 to n-d) {
j=i+d
for (k=i to j-1) {
5
7
VP2(VP1 NP4)
eat
Det1
3
the
NP4(Det1 N2)
N2,NP2
4 apples
5
Prep1
in
6
ai,j= ai,j∪
{A|A→BC∈PD,
B∈ai,k, C∈ak+i,j}
}}
6
Det2
NP5(Det2 N3)
the
N3,NP3
(1)S → NP VP
7 garden
がここで適合するはず
39
CKY法(6)
4.できあがった状態から構文木を作る
1
2
3
4
5
N1,NP1 S1(NP1 VP1)
1 II
V1,VP1
2
6
7
VP2(VP1 NP4)
eat
Det1
3
Sx(NPy VPz)
NPy(? ?) VPz(? ?)
the
NP4(Det1 N2)
N2,NP2
4 apples
5
Prep1
in
6
Det2
NP5(Det2 N3)
the
N3,NP3
7 garden
40
一応ここまで
• CKY法を学習した.
• もっと有名なアルゴリズムに
– チャート法
– LR法などがある
41
言語に関する基本概念(1)
• 文字...言語を構成する基本単位
(ここで意味は考えない)
• ある言語(例:英語)で使用される文字の集合:
– アルファベットと呼びSで表す
SE ={ a, b, c, …, z, A, B, C,…,Z}+{‘,’, ‘.’, , …}などの記号
– このアルファベットは有限の集合である.
(日,中は微妙...でも一応有限とする)
42
言語に関する基本概念(2)
•
•
S ...アルファベット1個の集合,
S  {a, b, c,...,z,...}
S
2
..アルファベット2個の集合,
S  {aa, ab, ac,...,bb,...,zz,...}
2
•
•
S
3
..アルファベット3個の集合
S  {aaa, aab, aac,...,zzz ,...}
3
S ..アルファベット0個(空語,空列)
0
S  {}
0
43
言語に関する基本概念(3)
S  S  S  S  S  ...  S  i 0 S n
*
0
2
3
n
n
S  S  S  S  ...  S  i 1 S n

2
3
n
n
• もし,Sに英語の全ての文字を含めれば
– S*は世の中の全英語のテキストを含む集合
→S*はあまり意味がない(でたらめな文字列も含む)
• ある文字列αが言語Lの意味のある文字列である時,
– α ∈ L と表す.で, L⊂S*
集合の要素
部分集合
44
言語に関する基本概念(4)
• ある文字列αが言語Lの要素かどうか?
– 言語Lのネイティブに聞く
代わりに:言語Lの文法を用意する
– 文法に照らして,構造の解析ができる
→文字列αが文であるとわかる
=αがα∈Lと言える
– 文法から構造が解析できない(文法に合わない)
→文字列αは文でない(非文)
= αがα∈Lでないと言える
45