確率論理プログラムを用いた確率文法のパラメータ推定

人工知能学会研究会資料
SIG-FPAI-B502-20
確率論理プログラムを用いた確率文法のパラメータ推定
Parameter Estimation of Stochastic Grammars
with Probabilistic Logic Programs
山口慧 1∗
Satoru Yamaguchi1
吉仲亮 1
Ryo Yoshinaka
1
山本章博 1
Akihiro Yamamoto1
京都大学大学院情報学研究科
Graduate School of Informatics, Kyoto University
1
1
Abstract: We propose a parameter estimation method of stochastic grammars by utilizing
elementary formal systems and probabilistic logic progarams. A stochastic grammar is a formal
grammar where probabilisties are assigned to production rules. Stochastic context-free grammars
are well-known because they are used for statistical parsing and predicting secondaty structures
of RNA sequences. However, some natural language sentences and RNA sequences have more
complicated structure than that expressed with context-free grammars. Our method can be applied
to the class of phrase structure grammars. The advantage of our method is from using a kind of
logic programs called elementary formal systems (EFSs) to express grammars. We extend them
into probabilistic EFSs by assigning probabilities to each clause. We estimate those probabilities
by utilizing a parameter estimation method of a kind of logic programs called probabilistic logic
programs (PLPs). We convert a probabilistic EFS into an extended PLP and apply the parameter
estimation method to the PLP.
1
はじめに
一般的に確率文法とは, その生成規則に対して確率
が付与された形式言語である. また, 確率文法のパラ
メータ推定とは与えられた確率文法に対して, 文字列の
データをもとにその確率文法の確率パラメータの最適
な値を推定することである. 本研究はこれまで提案さ
れてきた手法よりも一般的な言語のクラスに対して用
いることができる確率文法のパラメータ推定手法を提
案する. 本研究では確率文法を表現するために基本形
式体系 (Elementary Formal System, EFS) と呼ばれる
論理プログラムに確率を付与した確率 EFS を定義し,
確率 EFS で表した確率文法の確率を確率論理プログラ
ム (Probabilistic Logic Program, PLP) と呼ばれる論
理プログラムの手法を用いて推定する. 本研究で用い
る EFS は変数限定 EFS と呼ばれる EFS の部分クラス
であり, 変数限定 EFS が定義することができる言語は,
チョムスキー階層における句構造文法が生成可能な言
語に対応しているため, 提案手法は句構造文法に対して
適用可能である.
∗ 連絡先：京都大学大学院情報学研究科知能情報学専攻山本・
Cuturi 研究室
〒 606-8501 京都府京都市左京区吉田本町総合研究７
号館３階３２７号室
E-mail: [email protected]
確率文法としてよく用いられるものに確率文脈自由
文法があり, 言語や RNA の統計的モデルとして利用さ
れている [2][4]. また, Inside-Outside アルゴリズムと
呼ばれる一種の EM アルゴリズムがその確率パラメー
タの推定手法として有名である. 一方で, 文脈自由文法
よりも複雑な構造を表すために, より一般的なクラス
の文法も提案されている. 例えば, 多重文脈自由文法
(Multiple Context-Free Grammar) は文脈自由文法の
拡張の一つであり, RNA におけるシュードノット構造
と呼ばれる二次構造のような交差する依存関係を表現
することができる. このような文法に対応する確率文
法及びその確率パラメータの推定手法も提案されてい
る. 例えば, 加藤らの研究は確率付きの多重文脈自由文
法を用いて RNA の二次構造予測を行っている [5].
これまで提案されてきた確率文脈自由文法の拡張は弱
文脈依存言語と呼ばれる, 文脈自由言語と文脈依存言語
の間の言語クラスを対象にしている. これらの文法より
一般的な文法のクラスを扱うこと考える際, 文脈依存文
n
法を用いた場合, 例えば {a2 |n ≥ 1} や {an bn cn |n ≥ 1}
のような一見単純に見える言語でも複雑な生成規則が
必要となるため, それらの規則に確率を付与したとし
ても, それらの確率の意味がわかりにくくなってしま
う. 一方で, 論理プログラムの一種である基本形式体系
(Elementary Formal System, EFS) はそのような言語
− 81 −
も単純に表すことができる [6]. 我々は EFS の節に対し
て確率を付与することで確率 EFS を定義し, 確率 EFS
を用いて確率文法を表す.
提案手法では確率 EFS を確率論理プログラムと呼ば
れる論理プログラムに変換し, 確率論理プログラムの
確率パラメータ推定手法を用いて確率 EFS の確率パラ
メータを推定する [3]. 確率論理プログラムとはいくつ
かの節に確率が付与された論理プログラムである. た
だし, 一般的な確率論理プログラムでは確率 EFS を表
すことができないため, 我々は確率論理プログラムを拡
張し, それに対してパラメータ推定手法を適用する. 本
稿では我々の定義した確率 EFS と確率論理プログラム
の違いを説明しながら, 確率 EFS を確率論理プログラ
ムに変換する手法について説明する.
2
2.1
準備
p(t1 θ, . . . , tn θ) と定義する. 同様に節 c = h : −b1 , . . . , bn
に対して, cθ = hθ : −b1 θ, . . . , bn θ と定義する. cθ が
基礎確定節のとき, cθ を c のインスタンスと呼ぶ.
Γ 及び節 c に対して, 関係 Γ ⊢ c を次のように定義
する.
1. c ∈ Γ ならば Γ ⊢ c.
2. 任意の代入 θ に対して, Γ ⊢ c ならば Γ ⊢ cθ.
3. Γ ⊢ h : −b1 , . . . , bn かつ Γ ⊢ bn : − ならば Γ ⊢
h : −b1 , . . . , bn−1 .
関係 Γ ⊢ c が成り立つとき節 c が Γ(または EFS(Σ, Π, Γ))
によって証明可能であるという. EFS E = (Σ, Π, Γ)
及びアリティが 1 の述語記号 p ∈ Π に対して, 集合
L(E, p) = {t ∈ Σ+ |Γ ⊢ p(t) : −} は Σ 上の言語をな
す. 言語 L に対して L(E, p) = L となるような EFS E
及びその述語記号 p が存在するとき, 言語 L は EFS に
よって定義可能であるという.
例 2.2. 例 2.1 の EFS を E と置くと, L(E, p) = {
an bn cn |n ≥ 1} となる.
基本形式体系
Σ と Π を互いに交わらない有限集合とする. Σ の
要素を定数, Π の要素を述語記号と呼ぶ. 各述語記号
はアリティと呼ばれる自然数を持つ. Σ 及び Π のいず
れとも共通部分を持たない可算集合を X と置く. X
の要素を変数と呼ぶ. X ∪ Σ の要素の, 長さが 1 以上
の列を項と呼ぶ. 変数を含まない項を基礎項と呼ぶ.
アリティが n の述語記号 p 及び項 t1 , . . . , tn に対して,
p(t1 , . . . , tn ) という表現を原子式と呼ぶ. 項がすべて基
礎項のとき, その原子式を基礎原子式と呼ぶ. 本稿で
は項に含まれる変数を大文字で, 定数を小文字で表記
する. 原子式 h1 , . . . , hm , b1 , . . . , bn (m, n ≥ 0) に対し
て h1 , . . . , hm : −b1 , . . . , bn という表現を節と呼ぶ. 節
に対して, h1 , . . . , hm を頭部と呼び, b1 , . . . , bn を本体
と呼ぶ. 頭部が空の節 : −b1 , . . . , bn をゴール節と呼ぶ.
頭部が一つの項のみからなる節 h : −b1 , . . . , bn を確定
節と呼ぶ. 以降単に節と言った場合, 確定節を指す. 頭
部も本体も空の節を空節と呼び □ と表記する. Γ を確
定節の有限集合とする. 三つ組み (Σ, Π, Γ) を基本形式
体系 (Elementary Formal System, EFS) と呼ぶ.
原子式または節 e に対して, V (e) は e に含まれる全
ての変数の集合を表すとする. 節 h : −b1 , . . . , bn が
V (h) ⊇ V (bi ) (i = 1, . . . , n) を満たすとき, その節は変
数限定であるといい, EFS (Σ, Π, Γ) に対して, Γ が変
数限定節のみからなるとき, その EFS は変数限定であ
るという. 同様に, V (h) ⊆ ∪n
i=1 V (bi ) が成立するとき
その節は範囲限定であるといい, Γ が範囲限定節のみか
らなるとき, その EFS は範囲限定であるという. 範囲
限定 EFS はそうでない EFS と比べ定義可能な言語に
変わりはないが, 以降で述べる確率 EFS における確率
の総和が 1 を超えないようにするために必要な性質で
ある. 以降では変数限定かつ範囲限定の EFS を扱う.
二つの原子式 a1 , a2 に対して, a1 θ = a2 θ を満たす
代入 θ を a1 , a2 の単一化と呼ぶ. a1 , a2 が単一化を持
つとき, a1 , a2 は単一化可能であるという. EFS E =
(Σ, Π, Γ) 及びゴール節 g に対して, E による g の導出
とは, 次のような条件を満たすゴール節 gi , 確定節 ci 及
び代入 θ の三つ組み (gi , ci , θi ) の列である.
例 2.1. Γ を次の三つの節の集合とするとき, 三つ組み
({a, b, c}, {p, q}, Γ) は EFS である.
p(XY Z)
:−
q(X, Y, Z)
(1)
q(aX, bY, cZ)
:−
q(X, Y, Z)
(2)
q(a, b, c)
:−
(3)
互いに異なる変数を v1 , . . . , vn (n ≥ 0) と置き, t1 , . . . , tn
を項とするとき, {v1 /t1 , . . . , vn /tn } という表現を代入
と呼ぶ. t を項, θ を代入するとき, tθ は t 中の vi (i =
1, . . . , n) をそれぞれ ti に同時に置き換えてできる項を
表すとする. 原子式 a = p(t1 , . . . , tn ) に対して, aθ =
− 82 −
1. g0 = g.
2. gi =: −h1 , . . . , hk のとき,
i 頭部の原子式が h1 と単一化可能な節 h:b1 , . . . , bn が存在する場合,ci = h : −b1 , . . . , bn
かつ θi は a1 と a の単一化であり, gi+1 =
(b1 , . . . , bn , h2 , . . . , hk )θi である.
ii そのような節が存在しない場合, ci = □,
θi = {} であり (gi , ci , θi ) が導出の最後の
要素となる.
3 もし gi = □ の場合, ci = □, θi = {} であり
(gi , ci , θi ) が導出の最後の要素となる.
(□, □, {}) で終了する有限な導出を成功導出と呼ぶ.
2.2
p(Xyz):-append(X,Yz,Xyz),
append(Y,Z,Yz), q(X,Y,Z).
0.8::q([a|X],[b|Y],[c|Z]):-q(X,Y,Z).
0.2::q([a,b,c]).
確率論理プログラム
この節では確率論理プログラムを定義する. 確率論
理プログラムでは EFS と同じ用語が用いられるが, 必
要に応じて「確率論理プログラムの」や「EFS の」等
の言葉を用いて区別する.
C, Π 及び Ψ を互いに共通部分を持たない有限集合と
する. C の要素を定数, Π の要素を述語記号, Ψ の要素
を命題変数と呼ぶ. 各述語記号はアリティと呼ばれる
自然数を持つ. X は C, Π 及び Ψ のいずれとも共通部
分を持たない可算集合とする. X の要素を変数と呼ぶ.
確率論理プログラムにおける項は変数, 定数またはリ
ストのいずれかである. 確率論理プログラムにおいて
は, 変数は大文字で始まる文字列で表し, 定数は小文字
で始まる文字列で表すとする. 従って Xyz は変数 X と
定数 y,z の列ではなく一つの変数を表すことに注意す
る. リストとは [t1 , . . . , tn ] (n ≥ 0) または [t1 , . . . , tn |v]
(n ≥ 1) のいずれかの表現である. ただし, t1 , . . . , tn
は項, v は変数またはリストを表すとする. s1 , . . . , sm
を項とすると, [t1 , . . . , tn |[s1 , . . . , sn |v ]] は [t1 , . . . , tn ,
s1 , . . . , sn |v ] と等価であり, [t1 , . . . , tn |[s1 , . . . , sn ]] は
[t1 , . . . , tn , s1 , . . . , sn ] と等価である. 項が定数または
変数を含まないリストのとき, その項を基礎項と呼ぶ.
命題変数及び表現 p(t1 , . . . , tn ) を原子式と呼ぶ. た
だし p はアリティが n の述語記号であり, t1 , . . . , tn は
項である. もし原子式が命題変数であるか, 項として基
礎項のみを含むとき, その原子式を基礎原子式と呼ぶ.
原子式 a に対して, a 及び \ + a をリテラルと呼ぶ. リテ
ラル a を正リテラル, \ + a を負リテラルと呼ぶ. a が基
礎原子式のとき, その原子式からなるリテラルを基礎リ
テラルと呼ぶ. 正リテラル h 及びリテラル b1 , . . . , bn に
対して, h : −b1 , . . . , bn という表現を確定節と呼ぶ. 確
定節において h を頭部, b1 , . . . , bn を本体と呼ぶ. 確定
節が基礎リテラルのみからなるとき, その確定節を基礎
確定節と呼ぶ. 確率論理プログラムにおいては, 本体が
空の確定節を単に h と表記する. 以降でただ単に節と
言った場合, 確定節を指すとする. 確率論理プログラム
(Probabilistic Logic Program, PLP) はラベルな
し節の集合 D 及びラベル付き節の集合 L からなる. 各
ラベル付き節 c ∈ L は 0 以上 1 以下の実数のラベル wc
を持ち, c = h : −b1 , . . . , bn のとき, wc :: h − b1 , . . . , bn
と表記する.
例 2.3. 確率論理プログラムの例は次のようになる.
append([],X,X).
append([H|X],Y,[H|Z]):-append(X,Y,Z).
互いに異なる変数を v1 , . . . , vn (n ≥ 0) と置き, t1 , . . . , tn
を項とするとき, {v1 /t1 , . . . , vn /tn } という表現を代入
と呼ぶ. t を項, θ を代入するとき, tθ は t 中の vi (i =
1, . . . , n) をそれぞれ ti に同時に置き換えてできる項
を表すとする. 原子式 a = p(t1 , . . . , tn ) に対して, aθ
を aθ = p(t1 θ, . . . , tn θ) と定義する. a が命題変数から
なる場合, aθ = a とする. リテラル l に関して l = a
ならば, lθ = aθ, l = \ + a ならば lθ = \ + aθ と
する. 同様に節 c = h : −b1 , . . . , bn に対して, cθ を
cθ = hθ : −b1 θ, . . . , bn θ と定義する. cθ が基礎確定節
の時 cθ を c のインスタンスと呼ぶ.
確定節の集合 Γ 及び節 c に対して, 関係 Γ ⊢ c を次
のように定義する.
1. c ∈ Γ ならば Γ ⊢ c.
2. 任意の代入 θ に対して, Γ ⊢ c ならば Γ ⊢ cθ.
3. Γ ⊢ h : −b1 , . . . , bn であり,b1 が正リテラルかつ
Γ ⊢ bn : − ならば Γ ⊢ h : −b1 , . . . , bn−1 .
4. Γ ⊢ h : −b1 , . . . , bn であり,b1 が負リテラルかつ
Γ
⊢bn : − ならば Γ ⊢ h : −b1 , . . . , bn−1 .
Γ ⊢ c が成り立つとき c は Γ によって証明可能である
という. PLP T = (D, L) に対して, L に含まれる確定
節に代入を適用してできる全ての基礎確定節の集合を
GT とし, G を GT の部分集合とする. T の下での G の
確率を以下のように定義する
.
}
}{
{∏
∏
(1 − wc ) .
(4)
wc
P (G|T ) =
cθ∈G
cθ ∈G
/
PLP T に対するリテラル l の確率を以下のように定義
する.
∑
P (l|T ) =
P (G|T ).
(5)
G⊆GT ,G∪D⊢l
PLP T が明らかなときは, 省略して P (l) と書く.
2.3
確率論理プログラムの確率パラメータ
推定手法
この節では PLP のパラメータ推定手法について簡単
に説明する. PLP の確率パラメータの推定とは, PLP
T = (D, L) に対して, 訓練集合としてリテラルの有限
∏n
集合 I = {ij |j ≥ 1} が与えられたとき, j=1 p(i) が最
大となるような, いくつかまたは全ての L のラベルの
値を推定することである.
PLP のパラメータ推定は最尤法で行うことができ, 尤
度関数を計算する方法として Deterministic Decompos-
− 83 −
able Negation Normal Form (d-DNNF) 等の Knowledge Compilation の手法を使うものがある [3]. d-DNNF
とは論理式のデータ構造の一種である. この手法では,
初めに訓練集合の各リテラルに関して PLP T を和積
標準形 (Conjunctive Normal Form, CNF) に変換した
ものをさらに d-DNNF に変換し, d-DNNF を演算回路
として用いることで各リテラルの確率やその勾配を求
める [3].
この手法の利点として, d-DNNF を用いた計算はと
ても高速に行うことができ, かつ各リテラルを d-DNNF
に変換したものを保存しておけば, 訓練集合の追加や削
除を行った後に再度パラメータの推定を行う際, 再び同
じ d-DNNF へ変換を行う必要がないという点がある.
3
確率 Elementary Formal System
この節では EFS に確率を付与した確率 EFS を定義
する. 本研究では確率 EFS を用いて確率文法を表す.
EFS E = (Σ, Π, Γ) に対して, 五つ組 (Σ, Π, Γ, Ω, p0 )
を確率 EFS と呼ぶ. ここで Ω は 0 以上 1 以下の実数の
ラベルの集合, p0 ∈ Γ はアリティが 1 の述語記号であ
るとする. 各節 c ∈ Γ はラベル wc ∈ Ω を持つ. 頭部の
リテラルに述語記号 p ∈ Π を持つ全ての節の集合を Γp
∑
と置くとき, ラベルは条件 c∈Γp wc = 1 を満たさなけ
ればならない. ラベル wc を持つ節 c = h : −b1 , . . . , bn
は以下のように表記する. wc :: h : −b1 , . . . , bn
例 3.1. Γ を次の節の集合とし, 各節は以下のようにラ
ベルを持つとするとき, 五つ組 ({a, b, c}, {p, q}, Γ, {1.0,
0.8, 0.2}, p) は確率 EFS をなす.
1.0
::
p(XY Z) : −q(X, Y, Z)
(6)
0.8
::
q(aX, bY, cZ) : −q(X, Y, Z)
(7)
0.2
::
q(a, b, c) : −
(8)
確率 EFS の確率論理プログラムへ
の変換
4
本研究では確率 EFS を PLP に変換することで, PLP
のパラメータ推定手法を用いて確率 EFS の確率を推定
する. この節では確率 EFS の PLP への変換に関して
説明する. ただし, PLP の手法を用いて確率 EFS の確
率パラメータを推定するには PLP を拡張する必要があ
るため, それに関してもこの節で述べる.
確率 EFS と PLP の間には主に次の三つの違いがある.
1. 項等の構成要素
2. 確定節間の排他性の有無
3. 節に付与されたラベル (確率) の意味
以降ではこれらの違いに関して述べながら, 確率 EFS
の PLP への変換方法について述べる.
4.1
構成要素の違い
確率 EFS においては項は変数と定数の列のため文字
列を直接表現することができる. 一方, PLP は文字列
を直接表現することができないため, リストを用いて文
字列を表現する.
例 4.1. 確率 EFS における基礎項 aabbcc 及び a に対
応する PLP の要素はそれぞれリスト [a, a, b, b, c, c] 及
び [a] である.
より重要な違いとして, 確率 EFS においては複数の
変数を項の中に含めることで, 文字列の接続関係を表現
することができるが, PLP ではリスト同士の接続関係
を直接自由に表現することができない. そこで, 変換の
際には確率 EFS の変数を含む項をすべて PLP におけ
る変数に置き換え, 置き換えた変数間の接続関係を表す
リテラルをその節の本体に加えることで, 文字列同士
の接続関係を表す. 提案手法では次の述語記号 append
を用いて文字列の接続関係を表す.
確率 EFS E = (Σ, Π, Γ, Ω, p0 ) は Σ の要素の列全て
の確率を定義する. まず有限の導出の確率を定義する.
append([], Xs, Xs).
(10)
確率 EFS に関しても導出を EFS と同様に定義すると
append([X|Xs], Ys, [X, |Zs]) : −append(Xs, Ys, Zs). (11)
する. 導出 d = (g1 , c1 , θ1 ), . . . , (gn , cn , θn ) をあるゴー
append(Xs, Ys, Zs) は Zs が Xs と Ys をつなげてできる
ル節 g の E による有限導出とする. このとき, d の確率
リストであるとき証明可能であり, そうでなければ証明
を以下のように定義する.
{
可能ではない
.
wc1 P ((g2 , c2 , θ2 ), . . . , (gn , cn , θn )) (if c1 ̸= □)
P (d) =
1
(otherwise) 例 4.2. 確率 PEFS の節
次にゴール節 g の全ての成功導出の集合を Sg と置く.
このとき g の確率を
∑
P (g) =
P (d)
(9)
d∈Sg
と定義する. 最期に Σ の要素の列 t の確率を P (t) =
P (: −p0 (t)) と定義する.
0.7 :: p(XY Z) : −q(X, Y ), r(Z)
(12)
を PLP の節に変換すると,
0.7 :: p(Xyz) : −append(X, Yz, Xyz), append(Y, Z, Yz),
q(X, Y), r(Z) (13)
となる.
− 84 −
4.2
排他性
4.4
次に排他性に関して説明する. 確率 EFS では一つの
原子式を証明するために一つの確定節が用いられる. す
なわち確定節の間に排他性が存在するが PLP では一般
に各節が独立して選択されるため, そのような排他性は
存在しない. 本節では PLP において排他性を表現する
ための手法に関して説明する.
4.3
異なる節の間の排他性
異なる節の間の排他性に関しては例を用いて説明す
る. ある確率 EFS 及びある述語記号 p に関して, 頭部
の述語記号が p である全ての確定節の集合 Γp の要素が
以下の三つの節であるとする.
前節では異なる節の間の排他性を表現したが, 同じ節
のインスタンス間でも排他性は存在する. 例えば p(XY) :
−q(X), r(Y) という確率 EFS の節を用いて, p(abc) を
導出する際には p(abc) : −q(ab), r(c) 及び p(abc) :
−q(a), r(bc) の二通りのインスタンスが考えられ, どち
らか一方のみが一つの導出で用いられる. この排他性は
一般的な PLP では表現できないため, 本研究では PLP
を拡張する. 具体的には特別な述語記号 excl を追加す
る. ここで, PLP の確定節 c に対して, V (c) は c に含ま
れるすべての変数の集合であるとする. v1 , . . . , vm を
互いに異なる変数とするとき, 節 c を
wc1 :: h1 : −.
(14)
h : −b1 , . . . , bn , excl([v1 , . . . , vk ], [vk+1 , . . . , vm ])
(23)
とおく. ただし
wc2 :: h2 : −b1 , b2 .
(15)
{v1 , . . . , vk } ⊆ V (c)
(24)
wc3 :: h3 : −b3 .
(16)
{vk+1 , . . . , vm } ⊆ V (c)\{v1 , . . . , vk }
(25)
これらの節をそれぞれ c1 , c2 及び c3 と置く. これらを
排他性を勘案して PLP に変換すると以下のようにな.
h1 : −choose1p .
h2 :
(17)
−b1 , b2 , choose2p .
h3 : −b3 , choose3p .
wc1 ::
wc2 /(1 − wc1 ) ::
choosep3
同じ節のインスタンスの間の排他性
: −\ +
(19)
choosep1 .
choosep2
(20)
: −\ +
choosep1 , \
(18)
である. excl は c のインスタンスに関して, 第二引数が
一致するインスタンスの集合毎に一つのインスタンス
でのみ証明可能となる. 実装においては PLP を CNF
に変換する段階で各節が排他的となるような論理式を
加えることにより実現する. 変換において, の第二引
数に頭部に現れる変数を加え, そうでない変数を第一引
数に加えたリテラルを各節に追加する.
+
choosep1 .
(21)
choosep2 .
(22)
ここで, choosepi は新たに追加した命題変数であり, 直
感的には頭部に述語記号 p を持つ節の中から i 番目の
節が選ばれたことを意味する. これらの命題変数を本
体に加えることで, その命題変数が証明可能であるとき
のみ, 頭部が証明可能となる. 節 (20) から節 (22) は追
加した命題変数を用いて, 各 ci の確率と排他性を表現
している. 節 (20) に関して, choosep1 は確率 wc1 で無条
件に証明可能である. これに対して, 節 (21) の choosep2
は排他性を表現するため, choosep1 が証明可能でないと
きにのみ成り立つ. したがってこの節の確率は c1 が選
ばれない下での c2 の選ばれる確率となる. 最期に節
(22) に関して, choosep3 は他の choosepi が成り立たない
とき, すなわち他の節が選ばれないとき常に証明可能で
なければならないので, 確率は付与されない.
4.5
確率の意味の違い
この節では確率 EFS と PLP のそれぞれの節に付与
されたラベルの意味の違いに関して述べる. どちらのラ
ベルも節が用いられる確率を表しているが, 確率 EFS
における原子式の確率は, その原子式を本体に持つゴー
ル節の全ての成功導出の確率の和である. 導出の確率
は, 導出の各要素において用いられている確定節の確
率の積を求めることによって計算できる. すなわち, 同
じ節であっても一つの導出内で複数回使われていれば,
その数だけその節のラベルが掛けられる. 一方で, PLP
におけるリテラルの確率は, そのリテラルを頭部に持つ
節が証明可能であるような, ラベル付き節の選択の確率
の和である. 各選択の確率は選択した節のラベルの積
で求められる. 従って選択された節は証明において何
度用いたとしても確率に影響はない.
そこで提案手法では変換において PLP の各節に対し
て, その節が証明のどこで用いられるかを区別するよう
な項を加える. 新たに追加する項を文脈と呼ぶ. こうす
ることで, 異なる場所で使われている節に関しては, そ
の場所ごとに節を選択する必要があるため, 確率 EFS
と同様の確率を求めることができる. 具体的には文脈
はリストであり, 節 c が Γp に含まれる i 番目の節であ
− 85 −
るとすると, その節の本体の, append を除いて j 番目
の原子式にはリストの要素として [p, i, j] を先頭に加え
る. 例えば, 節 (13) が Γp における三番目の節であると
すると, 次のように変換できる.
0.7 :: p(Xyz, C) : −append(X, Y, Xy), append(Xy, Z, Xyz),
q(X, Y, [[p, 3, 1]|C]), r(Z, [[p, 3, 2]|C]),
choose3p (C), excl([X, Y, Xy, Z], [Xyz, C]).
4.6
変換手続き
この節ではこれまで述べてきた変換手続きをまとめ
る. 確率 EFS の節 c に対して, clauseP LP (c, C) は文脈
C を頭部の項に持つ PLP の節であり, 次のように変換
される.
1. 各項に対して,
おわりに
本稿では句構造文法にまで適用可能な確率文法のパ
ラメータ推定手法を提案した. 本研究では基本形式体系
(EFS) に確率を付与した確率 EFS を定義し, 確率 EFS
を用いて確率文法を表す. 提案手法は確率 EFS を確率
論理プログラム (PLP) に変換し, PLP の確率パラメー
タ推定手法を用いて確率文法のパラメータ推定を行う.
本稿では確率 EFS と PLP の違いに触れながら変換手
法を説明した.
本研究の今後の課題としては計算量に関して詳しく
調べることに加え, PLP のパラメータ推定手法におい
て用いているデータ構造に関して, より小さなものに変
換することにより計算量を減らすことが考えられる.
参考文献
i もし項が変数を含まないならば, 対応するリ
ストに置き換える.
ii そうでない場合, 変数に置き換える
2. append を用いて置き換えた変数間の接続関係を
表すリテラルを本体の初めに加える.
3. choosepi を本体に加える.
4. 文脈を各リテラルに加える.
5. もし頭部に含まれない変数が本体に含まれる場
合, リテラル excl(l1 , l2 ) を本体に加える. ただ
し, l1 は本体のみに現れる全ての変数を要素に持
つリストであり, l2 は頭部に現れる全ての変数を
要素に持つリストである.
次に確率 EFS E = (Σ, Π, Γ, Ω, p0 ) を PLP T = (D, L)
に変換する手順を述べる.
1. D, L を空集合とする.
2. D に節 (10) 及び (11) を加える.
3. 述語記号 p ∈ Π 毎に次の手順を行う.
i i = 1, . . . , n に関して, cpi を Γp の i 番目の
節と置いて以下の手順を行う.
a L に節
wc′ p :: choosepi (C) : −\+choosep1 (C), . . . ,
i
\+choosepi−1 (C).
を加える.
b D に clauseP LP (cpi , C) を加える.
ただし, wc′ p = wcpi /(1 − wcp1 − · · · − wcpi−1 ) である. 変
i
5
換した PLP において p0 に対応する述語記号を p′0 , 確
率 EFS における基礎項 t に対応するリストを t′ と置く
と p0 (t) = p′0 (t′ , []) となる. 変換された PLP に対して
確率パラメータ推定手法を適用することにより, 確率
EFS のパラメータ推定を行う.
[1] Adnan Darwiche: On the tractability of counting
theory models and its application to belief revision and truth maintenance, Journal of Applied
Non-Classical Logics 11(1-2): 11-34, (2001).
[2] Rogin D. Dowell and Sean R. Eddy: Evaluation of several lightweight stochastic context-free
grammars for RNA secondary structure prediction, BMC Bioinformatics, (2004).
[3] Daan Fierens, Guy Van den Broeck, Joris
Renkens, Dimitar Shterionov, Bernd Gutmann,
Ingo Thon, Gerda Janssens and Luc De Raedt:
Inference and learning in probabilistic logic programs using weighted Boolean formulas, Theory
and Practice of Logic Programming, (2013).
[4] Daniel Jurafsky, Chuck Wooters, Jonathan Segal,
Andreas Stolcke, Eriv Fosler, Gary Tajchman
and Nelson Morgan: Using a stochastic contextfree grammar as a language model for speech
recognition, Acoustics, Speech, and Signal Processing, (1995).
[5] Yuki Kato, Hiroyuki Seki, and Tadao Kasami:
RNA Structure Prediction Including Pseudoknots Based on Stochastic Multiple Context-Free
Grammar, Workshop on Probabilistic Modeling
and Machine Learning in Structural and Systems
Biology, (2006).
[6] 西野哲朗, 石坂裕毅, 有川節夫: 形式言語の理論,
丸善, pp.133-159, (1999).
− 86 −

Download Report