木オートマトン•トランスデューサによる自然言語処理

(1)

木オートマトン•トランスデューサによる

自然言語処理

†林克彦

NTTコミュニケーション科学基礎研究所 †[email protected]

(2)

自然言語処理: 1980-1990年代 (1/5)

• 1980年代: 木に関連する形式文法の研究 (構文解析手法など)

• CFG、LFG、HPSG、TAG、Prologなど

• 1990年代: 統計モデル + 文字列(変換)に関連する研究

• 隠れマルコフモデル (HMM)、有限オートマトン (FSA)、

有限トランスデューサ (FST)

• n-gram言語モデル

[eg, Jelinek 90]

• 品詞タグ付け

_{[eg, Church 88]}

• 統計的機械翻訳

_{[eg, Brown 93]}

• 重み付き (w)FSA, wFSTのツールキット (OpenFST)

[eg, Mohri et. al. 00]

• 統計的文字列処理の汎用ツールとして活躍

1. HMM、CRFなどのモデルをエンコード可能[Kempe 97, Wu et. al. 14] 2. 合成などの演算を使い複雑な問題が簡単に表せる

(3)

自然言語処理: wFSAとwFSTとは? (2/5)

(4)

自然言語処理: wFSTの合成によるモデルの

連結 (3/5)

(5)

自然言語処理: wFSAとwFSTによる日英翻

字

_{[Knight & May 09]}

(4/5)

• 日英翻字の例

•

マスターズトーナメント_{⇒ m a s u t a a z u t o o n a m e n t o ⇒} M AE S T ER Z T ER N UH M EH N T_{⇒ Masters Tournament}

** 一般にNoisy Channelモデルを考えるため逆向き

(6)

•

複数のwFSTを経由するとき

入力のFSTへの埋め込み I モデル1 T1 モデル2 T2

•

アプローチ1: バケツリレー式合成 (Bucket brigade)

I◦ T1 Pro j(I◦ T1◦ T2) (出力空間)

(7)

自然言語処理: 2000-2010年代 (5/5)

• 2000年代: 統計モデル + 木(変換)に関連する研究

• 機械翻訳

[Wu 97, Yamada & Knight 02, Melamed 03, Chiang 05, ...]

• 文書要約

[Knight & Marcu 00, ...]

• 言い換え

[Pang et al 03, ...]

• 質問応答

[Echihabi & Marcu 03, ...]

• 自然言語文生成

[Bangalore & Rambow 00, ...]

形式的な枠組み

• 同期文法 (同期文脈自由文法、同期木接合文法など)

(8)

木オートマトン•トランスデューサ

• TATA

_{[Comon et. al. 08]}

• 木オートマトン

[Thacher 67, Rounds 68]

• 木トランスデューサ

[Rounds 68, Thatcher 70, Rounds 70]

• 応用:

• 自然言語処理

_{[Knight 06]}

• XML文書処理

_{[高田 & 関 08]}

• データベース、項書き換え、

定理証明 ...

(9)

階層化アルファベット

(Ranked Alphabet)

• _{階層化アルファベット (Ranked Alphabet) (}

_Σ,rk)

• 記号の有限集合

Σ

• 記号から正の整数への写像 rk :

Σ → N ∪ {0}

• _{ランクnの記号}

_σ

(n)

_(rk(

_{σ) = n, σ ∈ Σ)}

• _{ランクnの記号から成る集合}

_Σ

(n)

_{⊆ Σ}

注意: 場合によって(n)は省き、(_{Σ,rk)は単にΣと書く}

(10)

木の定義

• _{Σの記号から構成される木の集合 T}

_Σ

_(A)

• _{記号集合A (A}

(0)

_{)の記号は木の葉のみに現れる}

• 木の定義

• 全ての記号

_σ

_{∈ A ∪ Σ}

(0)

_{に対して、}

_σ

_{∈ T}

Σ

(A)

• 全ての記号

_σ

_{∈ Σ}

(k)

_{に対して、}

_σ

_(t

1

, . . . ,t

k

)

∈ T

Σ

(A) (t

1

, . . . ,t

k

∈ T

Σ

(A))

• 例:

_{Σ = {σ}

(0)

_,

_λ

(0)

_,

_γ

(0)

_,

_ξ

(0)

_,

_δ

(0)

_,

_α

(1)

_,

_θ

(1)

_,

_σ

(5)

_{}, A = {}

_β}

....

σ

(0)

_.

_α

(1)

_..

_...

..

γ

(0)

.

_....

_σ

(5)

..

_.

..

δ

(0)

.

....

..

θ

(1)

_...

..

β

(0)

.

....

..

α

(1)

_...

..

ξ

(0)

.

....

..

β

(0)

.

..

γ

(0)

(11)

木のラベル、部分木、置換

....

S. ....

..

VP

.

....

..

V...

..

開けた

.

....

..

を

.

..

NP

...

..

ドア

.

....

..

が

.

..

NP

...

..

犬

.

..

VP

.

....

..

V...

..

開けた

.

....

..

、

.

..

V...

..

壊して

• 位置集合 pos(t) =

{

ε} ∪ {i.v | 1 ≤ i ≤ k,v ∈ pos(t

i

)

}

• 位置 v

∈ pos(t)に対して

• _{ラベル t(v): t(}

_ε

_{) =}

S

、t(3.3) =

V

• _{部分木 t}

_|v

_{: t}

_|

_3.3

=

(V 開けた)

(12)

木のラベル、部分木、置換

....

S

.

_ε

....

..

VP

.

₃

....

..

V

_3.3

...

..

開けた

_3.3.1

.

....

..

を

_3.2

.

..

NP

...

_3.1

..

ドア

_3.1.1

.

....

..

が

₂

.

..

NP

...

₁

..

犬

_1.1

.

..

VP

.

....

..

V...

..

開けた

.

....

..

、

.

..

V...

..

壊して

• 位置集合 pos(t) =

{

ε} ∪ {i.v | 1 ≤ i ≤ k,v ∈ pos(t

i

)

}

• 位置 v

∈ pos(t)に対して

• _{ラベル t(v): t(}

_ε

_{) =}

S

、t(3.3) =

V

• 部分木 t

|v

: t

|

3.3

=

(V 開けた)

(13)

木のラベル、部分木、置換

....

S

.

_ε

....

..

VP

.

₃

....

..

V

_3.3

...

..

開けた

_3.3.1

.

....

..

を

_3.2

.

..

NP

...

_3.1

..

ドア

_3.1.1

.

....

..

が

₂

.

..

NP

...

₁

..

犬

_1.1

.

..

VP

.

....

..

V...

..

開けた

.

....

..

、

.

..

V...

..

壊して

• 位置集合 pos(t) =

{

ε} ∪ {i.v | 1 ≤ i ≤ k,v ∈ pos(t

i

)

}

• 位置 v

∈ pos(t)に対して

• _{ラベル t(v): t(}

_ε

_{) =}

S

、t(3.3) =

V

• _{部分木 t}

_|v

_{: t}

_|

_3.3

=

(V 開けた)

(14)

木のラベル、部分木、置換

....

S

.

_ε

....

..

VP

.

₃

....

..

V

_3.3

...

..

開けた

_3.3.1

.

....

..

を

_3.2

.

..

NP

...

_3.1

..

ドア

_3.1.1

.

....

..

が

₂

.

..

NP

...

₁

..

犬

_1.1

.

..

VP

.

....

..

V...

..

開けた

.

....

..

、

.

..

V...

..

壊して

• _{位置集合 pos(t) =}

_{

_{ε} ∪ {i.v | 1 ≤ i ≤ k,v ∈ pos(t}

_i

₎

_}

• 位置 v

∈ pos(t)に対して

• _{ラベル t(v): t(}

_ε

) =

S

、t(3.3) =

V

• 部分木 t

|v

: t

|

3.3

=

(V 開けた)

(15)

木のラベル、部分木、置換

....

S

.

_ε

....

..

VP

.

₃

....

..

V

_3.3

...

..

開けた

_3.3.1

.

....

..

を

_3.2

.

..

NP

...

_3.1

..

ドア

_3.1.1

.

....

..

が

₂

.

..

NP

...

₁

..

犬

_1.1

.

..

VP

.

....

..

V...

..

開けた

.

....

..

、

.

..

V...

..

壊して

• _{位置集合 pos(t) =}

_{

_{ε} ∪ {i.v | 1 ≤ i ≤ k,v ∈ pos(t}

_i

₎

_}

• 位置 v

∈ pos(t)に対して

• _{ラベル t(v): t(}

_ε

) =

S

、t(3.3) =

V

• 部分木 t

|v

: t

|

3.3

=

(V 開けた)

(16)

木のラベル、部分木、置換

....

S. ....

..

VP

.

....

..

VP

.

....

..

V...

..

開けた

.

....

..

、

.

..

V...

..

壊して

.

....

..

を

.

..

NP

...

..

ドア

.

....

..

が

.

..

NP

...

..

犬

• 位置集合 pos(t) =

{

ε} ∪ {i.v | 1 ≤ i ≤ k,v ∈ pos(t

i

)

}

• _{位置 v}

_{∈ pos(t)に対して}

• _{ラベル t(v): t(}

_ε

_{) =}

S

、t(3.3) =

V

• 部分木 t

|v

: t

|

3.3

=

(V 開けた)

• 木 sによる置換 t[s]

v

: t[

(VP (V 壊して) 、 (V 開けた))

]

3.3

=

(17)

変数、木の代入の定義

• _{変数の集合: X =}

_{x

₁

_{, x}

₂

_{, . . .}}

• _X

_k

₌

_{x

₁

_{, . . . , x}

_k}

• 木の代入

_{φ : X → T}

_Σ

(X )

• _{定義域: DOM(}

_φ

) =

{x ∈ X |

φ

(x)

, x}

• _DOM(

_φ

) =

{x

1

, . . . , x

k}、かつ、φ

(x

i

) = t

i

のとき、

φ

を

_{x

₁

_{← t}

₁

, . . . , x

_k

← tk}と書く

• _{拡張代入 ¯}

_φ

_{: T}

_Σ

_{(X )}

_{→ T}

_Σ

_{(X )}

• φ(σ(s

¯

1

, . . . , s

k

)) =

σ( ¯φ(s

1

), . . . , ¯

φ(s

k

))

• 代入の例:

_φ

=

{x

1

← a,x

2

← b,x

3

← c}

..

¯

φ

(.

..

α.

....

..

γ...

..

x

3

.

....

..

x

2

.

..

β...

..

x

1

.

)

₌

.

..

α.

....

..

γ...

..

c

.

....

..

b

.

..

β...

..

a

(18)

木に対する文法、受理機械、変換機械

• 文法•受理機械:

文字列

木

文法

正規文法

??

文脈自由文法

受理機械

有限オートマトン

??

プッシュダウンオートマトン

• 変換機械:

文字列ペア

木ペア

変換機械

有限トランスデューサ

??

(19)

正規木文法 (Regular Tree Grammars)

• _{正規木文法 (RTG) G = (N,}

_Σ,P,I)

• _{N: 非終端記号 (状態記号)の集合}

• _I

_{⊆ N: 開始となる非終端記号の集合}

• _{Σ: 終端記号 (木のラベル記号)の集合}

• P: 生成規則の集合

• _{各生成規則 n}

_{→ u ∈ Pの形をとる (n ∈ N, u ∈ T}

_Σ

(N))

• _{導出ステップ s}

_⇒

p G

t (s,t

∈ T

Σ

(N), p = n

→ u ∈ P):

• _{規則 pはn}

_{→ uとする (n ∈ N, u ∈ T}

_Σ

_(N))

• _{位置 v}

_{∈ pos(s)に対して、ラベル s(v) = nかつ置換 s[u]v}

_{= t}

• _{例: 規則 p =}

qv

→

(V 走る)

(20)

正規木文法 (Regular Tree Grammars)

• 正規木文法 (RTG) G = (N,

Σ,P,I)

• N: 非終端記号 (状態記号)の集合

• I

⊆ N: 開始となる非終端記号の集合

• _{Σ: 終端記号 (木のラベル記号)の集合}

• _{P: 生成規則の集合}

• 各生成規則 n

→ u ∈ Pの形をとる (n ∈ N, u ∈ T

Σ

(N))

• 導出ステップ s

⇒

p G

t (s,t

∈ T

Σ

(N), p = n

→ u ∈ P):

• _{規則 pはn}

_{→ uとする (n ∈ N, u ∈ T}

_Σ

_(N))

• _{位置 v}

_{∈ pos(s)に対して、ラベル s(v) = nかつ置換 s[u]v}

_{= t}

• _{例: 規則 p =}

qv

→

(V 走る)

....

S. ....

..

qv

.

....

..

が

.

..

NP

...

..

犬

.

⇒

p

.

....

S. ..

..

V...

..

走る

.

....

..

が

.

..

NP

...

..

犬

(21)

例: RTGによる木の生成過程

• _{正規木文法 G = (N,}

_Σ,P,I)

• N =

{

q, qv1, qv2

}

• _{Σ = {}

S, NP, VP, V, 犬, が, ドア, を, 開ける

}

• _{I =}

_{

q

}

• _{規則集合 P:}

p

1

:

q

→

(S (NP 犬) が qv1)

p

2

:

qv1

→

(VP (NP ドア) を qv2)

p

3

:

qv2

→

(V 開ける)

• 生成可能な木の集合

L(G) =

{t ∈ T

_Σ

|

q

⇒

∗_G

_t,

q

∈ I}

.

(22)

例: RTGによる木の生成過程

• _{正規木文法 G = (N,}

_Σ,P,I)

• N =

{

q, qv1, qv2

}

• _{Σ = {}

}

• _{I =}

_{

q

}

• _{規則集合 P:}

p

1

:

q

→

p

2

:

qv1

→

p

3

:

qv2

→

(V 開ける)

• 生成可能な木の集合

L(G) =

{t ∈ T

_Σ

|

q

⇒

∗_G

_t,

q

∈ I}

.... q.. _⇒p1 .... S... .. qv1 . .... .. が . .. .. NP... .. 犬

(23)

例: RTGによる木の生成過程

• _{正規木文法 G = (N,}

_Σ,P,I)

• N =

{

q, qv1, qv2

}

• _{Σ = {}

}

• _{I =}

_{

q

}

• _{規則集合 P:}

p

1

:

q

→

p

2

:

qv1

→

p

3

:

qv2

→

(V 開ける)

• 生成可能な木の集合

L(G) =

{t ∈ T

_Σ

|

q

⇒

∗_G

_t,

q

∈ I}

.... q.. _⇒p1 .... S... .. qv1 . .... .. が . .. .. NP... .. 犬 . ⇒p2 . .. S. .... .. VP. .... .. qv2 . .... .. を . .. .. NP... .. ドア . .... .. が . .. .. NP... .. 犬

(24)

例: RTGによる木の生成過程

• 正規木文法 G = (N,

Σ,P,I)

• N =

{

q, qv1, qv2

}

• _{Σ = {}

}

• I =

{

q

}

• 規則集合 P:

p

1

:

q

→

p

2

:

qv1

→

p

3

:

qv2

→

(V 開ける)

• 生成可能な木の集合

L(G) =

{t ∈ T

_Σ

|

q

⇒

∗_G

t,

q

∈ I}

.... q.. _⇒p1 .... S... .. qv1 . .... .. が . .. .. NP... .. 犬 . ⇒p2 . .. S. .... .. VP. .... .. qv2 . .... .. を . .. .. NP... .. ドア . .... .. が . .. .. NP... .. 犬 . ⇒p3 . .. S. .... .. VP. .... .. V... .. 開ける . .... .. を . .. .. NP... .. ドア . .... .. が . .. .. NP... .. 犬

(25)

例: RTGによる木の生成過程

• 正規木文法 G = (N,

Σ,P,I)

• N =

{

q, qv1, qv2

}

• _{Σ = {}

}

• I =

{

q

}

• 規則集合 P:

p

1

:

q

→

p

2

:

qv1

→

p

3

:

qv2

→

(V 開ける)

• 生成可能な木の集合

L(G) =

{t ∈ T

_Σ

|

q

⇒

∗_G

t,

q

∈ I}

.... q.. _⇒p1 .... S... .. qv1 . .... .. が . .. .. NP... .. 犬 . ⇒p2 . .. S. .... .. VP. .... .. qv2 . .... .. を . .. .. NP... .. ドア . .... .. が . .. .. NP... .. 犬 . ⇒p3 . .. S. .... .. VP. .... .. V... .. 開ける . .... .. を . .. .. NP... .. ドア . .... .. が . .. .. NP... .. 犬

(26)

文脈自由文法 (CFG)との関係 (1/2)

• 木の生成力

• あらゆるCFGに対して、その導出木を生成する

RTGが存在?

_⇒

Yes

• あらゆるRTGに対して、その生成する木を導出木として持つ

CFGが存在?

_⇒

No

木の集合

..

{

.

..

X. ....

..

Y...

..

b

.

..

Y...

..

a

.

,

.

..

X. ....

..

Y...

..

a

.

..

Y...

..

b

.

}

RTG

q_{→ (X (Y a) (Y b))} q_{→ (X (Y b) (Y a))}

CFG

存在しない

(27)

文脈自由文法 (CFG)との関係 (2/2)

• 文字列の生成力

• RTGが生成する木の葉の列を文字列としたとき、

その集合は文脈自由言語に属する

..

文字列世界

.

···

.

インデックス言語

.

文脈自由言語

.

正規言語

.

_木世界

..

···

.

文脈自由木言語

.

正規木言語

.

生成

.

生成

(28)

RTGでは表せない木集合

..

{

.

_b

_..

.

_,

.

..

a.

....

..

b

.

..

b

.

_,

.

..

a.

....

..

a.

....

..

b

.

..

b

.

..

a.

....

..

b

.

..

b

.

_,

.

..

a.

....

..

a.

....

..

a.

....

..

b

.

..

b

.

..

a.

....

..

b

.

..

b

.

..

a.

....

..

a.

....

..

b

.

..

b

.

..

a.

....

..

b

.

..

b

.

_,

.

_···

.

}

• 左右の部分木の高さが常に同じ木の集合

• 文字列言語

_{b

2n

| n ≥ 0} , CFL

• 文脈自由木文法 (Context-free Tree Grammar)

(29)

RTGでは表せない木集合

..

{

.

_b

_..

.

_,

.

..

a.

....

..

b

.

..

b

.

_,

.

..

a.

....

..

a.

....

..

b

.

..

b

.

..

a.

....

..

b

.

..

b

.

_,

.

..

a.

....

..

a.

....

..

a.

....

..

b

.

..

b

.

..

a.

....

..

b

.

..

b

.

..

a.

....

..

a.

....

..

b

.

..

b

.

..

a.

....

..

b

.

..

b

.

_,

.

_···

.

}

• 左右の部分木の高さが常に同じ木の集合

• 文字列言語

_{b

2n

| n ≥ 0} , CFL

• 文脈自由木文法 (Context-free Tree Grammar)

• 左辺に変数を持つことができる

..

q

_{. →}

.

₀

_..b

q

..

_{. →}

.

₀

q

₁

(q

..

0

)

..

q

₁

(x)

.

_→

..a.

....

..x

.

..

..x

(30)

木に対する文法、受理機械、変換機械

• 文法•受理機械:

文字列

木

文法

正規文法

正規木文法

文脈自由文法

受理機械

有限オートマトン

??

プッシュダウンオートマトン

• 変換機械:

文字列ペア

木ペア

変換機械

有限トランスデューサ

??

(31)

上昇型木オートマトン (Bottom-up FTA)

• 非決定性上昇型木オートマトン (FTA

_{↑) A = (Q,Σ,F,E)}

[Thacher & Wright 68; Doner 70]

• Q: 状態集合、F

⊆ Q: 終了状態の集合

• _{Σ: 入力の階層化アルファベット}

• E

⊆

k

z }| {

Q

× ··· × Q×Σ

(k)

× Q: 遷移の集合

• 遷移:

_σ(q

₁

, . . . , q

k

)

→ q ∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 決定性:

• ある記号

_σ

(k)

_{∈ Σと状態系列q}

1

, . . . , q

k

に対して、

遷移先が一意に決まる

• 実行 (Run)

_{ρ: pos(t) → Q}

• _{t(v) =}

_σ

(k)

_{となる位置 v}

_{∈ pos(t)に対して、}

σ

(

ρ

(v.1), . . . ,

ρ

(v.k))

→

ρ

(v)

∈ Eが存在する

(32)

例: FTA

_{↑による木の受理過程}

• FTA

_{↑ A = (Q,Σ,F,E)}

• Q =

{

q, qv, qnp, qvp, qx

}

• F =

{

q

}

• _{Σ = {}

}

• _{遷移集合 E:}

犬

_→

qx が

→

qx ドア

_→

qx を

→

qx 開ける

_→

qx NP(qx)

_→

qnp V(qx)

_→

qv VP(qnp,qx,qv)

_→

qvp S(qnp,qx,qvp)

→

q .... S. .... .. VP. .... .. V... .. 開ける . .... .. を . .. .. NP... .. ドア . .... .. が . .. .. NP... .. 犬

• 受理可能な木の集合

L(A) =

{t ∈ T

_Σ

|

ρ(ε) ∈ Fとなる実行ρが存在}

(33)

例: FTA

_{↑による木の受理過程}

• FTA

_{↑ A = (Q,Σ,F,E)}

• Q =

{

q, qv, qnp, qvp, qx

}

• F =

{

q

}

• _{Σ = {}

}

• _{遷移集合 E:}

犬

_→

qx が

→

qx ドア

_→

qx を

→

qx 開ける

_→

qx NP(qx)

_→

qnp V(qx)

_→

qv VP(qnp,qx,qv)

_→

qvp S(qnp,qx,qvp)

→

q .... S. .... .. VP. .... .. V... .. ρ(3.3.1)=qx . .... .. ρ(3.2)=qx . .. .. NP... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. NP... .. ρ(1.1)=qx

• 受理可能な木の集合

L(A) =

{t ∈ T

_Σ

|

ρ(ε) ∈ Fとなる実行ρが存在}

(34)

例: FTA

_{↑による木の受理過程}

• FTA

_{↑ A = (Q,Σ,F,E)}

• Q =

{

q, qv, qnp, qvp, qx

}

• F =

{

q

}

• _{Σ = {}

}

• _{遷移集合 E:}

犬

_→

qx が

→

qx ドア

_→

qx を

→

qx 開ける

_→

qx NP(qx)

_→

qnp V(qx)

_→

qv VP(qnp,qx,qv)

_→

qvp S(qnp,qx,qvp)

→

q .... S. .... .. VP. .... .. V... .. ρ(3.3.1)=qx . .... .. ρ(3.2)=qx . .. .. NP... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

• 受理可能な木の集合

L(A) =

{t ∈ T

_Σ

|

ρ(ε) ∈ Fとなる実行ρが存在}

(35)

例: FTA

_{↑による木の受理過程}

• FTA

_{↑ A = (Q,Σ,F,E)}

• Q =

{

q, qv, qnp, qvp, qx

}

• F =

{

q

}

• _{Σ = {}

}

• _{遷移集合 E:}

犬

_→

qx が

→

qx ドア

_→

qx を

→

qx 開ける

_→

qx NP(qx)

_→

qnp V(qx)

_→

qv VP(qnp,qx,qv)

_→

qvp S(qnp,qx,qvp)

→

q .... S. .... .. VP. .... .. V... .. ρ(3.3.1)=qx . .... .. ρ(3.2)=qx . .. .. ρ(3.1)=qnp... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

• 受理可能な木の集合

L(A) =

{t ∈ T

_Σ

|

ρ(ε) ∈ Fとなる実行ρが存在}

(36)

例: FTA

_{↑による木の受理過程}

• FTA

_{↑ A = (Q,Σ,F,E)}

• Q =

{

q, qv, qnp, qvp, qx

}

• F =

{

q

}

• _{Σ = {}

}

• _{遷移集合 E:}

犬

_→

qx が

→

qx ドア

_→

qx を

→

qx 開ける

_→

qx NP(qx)

_→

qnp V(qx)

_→

qv VP(qnp,qx,qv)

_→

qvp S(qnp,qx,qvp)

→

q .... S. .... .. VP. .... .. ρ(3.3)=qv... .. ρ(3.3.1)=qx . .... .. ρ(3.2)=qx . .. .. ρ(3.1)=qnp... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

• 受理可能な木の集合

L(A) =

{t ∈ T

_Σ

|

ρ(ε) ∈ Fとなる実行ρが存在}

(37)

例: FTA

_{↑による木の受理過程}

• FTA

_{↑ A = (Q,Σ,F,E)}

• Q =

{

q, qv, qnp, qvp, qx

}

• F =

{

q

}

• _{Σ = {}

}

• _{遷移集合 E:}

犬

_→

qx が

→

qx ドア

_→

qx を

→

qx 開ける

_→

qx NP(qx)

_→

qnp V(qx)

_→

qv VP(qnp,qx,qv)

_→

qvp S(qnp,qx,qvp)

→

q .... S. .... .. ρ(3)=qvp. .... .. ρ(3.3)=qv... .. ρ(3.3.1)=qx . .... .. ρ(3.2)=qx . .. .. ρ(3.1)=qnp... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

• 受理可能な木の集合

L(A) =

{t ∈ T

_Σ

|

ρ(ε) ∈ Fとなる実行ρが存在}

(38)

例: FTA

_{↑による木の受理過程}

• FTA

_{↑ A = (Q,Σ,F,E)}

• Q =

{

q, qv, qnp, qvp, qx

}

• F =

{

q

}

• _{Σ = {}

}

• _{遷移集合 E:}

犬

_→

qx が

→

qx ドア

_→

qx を

→

qx 開ける

_→

qx NP(qx)

_→

qnp V(qx)

_→

qv VP(qnp,qx,qv)

_→

qvp S(qnp,qx,qvp)

_→

q .... ρ(ε)=q. .... .. ρ(3)=qvp. .... .. ρ(3.3)=qv... .. ρ(3.3.1)=qx . .... .. ρ(3.2)=qx . .. .. ρ(3.1)=qnp... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

• 受理可能な木の集合

L(A) =

{t ∈ T

_Σ

|

ρ(ε) ∈ Fとなる実行ρが存在}

(39)

例: FTA

_{↑による木の受理過程}

• FTA

_{↑ A = (Q,Σ,F,E)}

• Q =

{

q, qv, qnp, qvp, qx

}

• F =

{

q

}

• _{Σ = {}

}

• _{遷移集合 E:}

犬

_→

qx が

→

qx ドア

_→

qx を

→

qx 開ける

_→

qx NP(qx)

_→

qnp V(qx)

_→

qv VP(qnp,qx,qv)

_→

qvp S(qnp,qx,qvp)

_→

q .... ρ(ε)=q. .... .. ρ(3)=qvp. .... .. ρ(3.3)=qv... .. ρ(3.3.1)=qx . .... .. ρ(3.2)=qx . .. .. ρ(3.1)=qnp... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

• 受理可能な木の集合

L(A) =

{t ∈ T

_Σ

|

ρ(ε) ∈ Fとなる実行ρが存在}

(40)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

[Rabin 69; Doner 70]

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qnp,qx,qvp) NP(qnp)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

(qnp,qx,qvp) ドア(qx)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... S. .... .. VP. .... .. V... .. 開ける . .... .. を . .. .. NP... .. ドア . .... .. が . .. .. NP... .. 犬

(41)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. VP.... _ρ_(3)=qvp. .. V... .. 開ける . .... .. を . .. .. NP... .. ドア . .... .. が_ρ_(2)=qx . .. .. NP_ρ_(1)=qnp... .. 犬

(42)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. VP.... _ρ_(3)=qvp. .. V... .. 開ける . .... .. を . .. .. NP... .. ドア . .... .. が_ρ_(2)=qx . .. .. ρ(1)=qnp... .. 犬_ρ_(1.1)=qx

(43)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. VP.... _ρ_(3)=qvp. .. V... .. 開ける . .... .. を . .. .. NP... .. ドア . .... .. が_ρ_(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

(44)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. VP.... _ρ_(3)=qvp. .. V... .. 開ける . .... .. を . .. .. NP... .. ドア . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

(45)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. ρ(3)=qvp. .... .. V_ρ_(3.3)=qv... .. 開ける . .... .. を_ρ_(3.2)=qx . .. .. NP_ρ_(3.1)=qnp... .. ドア . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

(46)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. ρ(3)=qvp. .... .. V_ρ_(3.3)=qv... .. 開ける . .... .. を_ρ_(3.2)=qx . .. .. ρ(3.1)=qnp... .. ドア_ρ_(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

(47)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. ρ(3)=qvp. .... .. V_ρ_(3.3)=qv... .. 開ける . .... .. を_ρ_(3.2)=qx . .. .. ρ(3.1)=qnp... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

(48)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. ρ(3)=qvp. .... .. V_ρ_(3.3)=qv... .. 開ける . .... .. ρ(3.2)=qx . .. .. ρ(3.1)=qnp... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

(49)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. ρ(3)=qvp. .... .. ρ(3.3)=qv... .. 開ける_ρ_(3.3.1)=qx . .... .. ρ(3.2)=qx . .. .. ρ(3.1)=qnp... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

(50)

下降型木オートマトン (Top-down FTA)

• 非決定性下降型木オートマトン (FTA

_{↓) A = (Q,Σ,I,E)}

• _I

_{⊆ Q: 初期状態の集合}

• _E

_{⊆ Q × Σ}

(k)

_×

k

z }| {

Q

× ··· × Q: 遷移の集合

• 遷移:

_{σ(q) → (q}

₁

, . . . , q

k

)

∈ E (q,q

1

, . . . , q

k

∈ Q、σ ∈ Σ

(k)

)

• 例: FTA

_{↓による受理過程}

• I =

{

q

}

• 遷移集合 E:

S(q)

→

(qx) 犬(qx)

→

accept が(qx)

→

accept VP(qvp)

→

accept を(qx)

→

accept V(qv)

→

(qx) 開けた(qx)

→

accept .... ρ(ε)=q. .... .. ρ(3)=qvp. .... .. ρ(3.3)=qv... .. ρ(3.3.1)=qx . .... .. ρ(3.2)=qx . .. .. ρ(3.1)=qnp... .. ρ(3.1.1)=qx . .... .. ρ(2)=qx . .. .. ρ(1)=qnp... .. ρ(1.1)=qx

(51)

FTA

_{↑とFTA↓の比較}

• FTA

_{↑ = FTA↓ (まとめてFTAと呼ぶ)}

• _{終了状態の集合 F}

_{⇔ 初期状態の集合 I}

• _σ

(q

₁

, . . . , q

_k

)

→ q ⇔

σ

(q)

→ (q

₁

, . . . , q

_k

)

• 決定性FTA

_{↑ (Det-FTA↑) , 決定性FTA↓ (Det-FTA↓)}

木の集合

..

{

.

..

X. ....

..

b

.

..

a

.

,

.

..

X. ....

..

a

.

..

b

.

}

Det-FTA

_↑

X(qa qb)_{→ q} X(qb qa)_{→ q} a_{→ qa} b_{→ qb}

Det-FTA

_↓

存在しない

(52)

RTGとの関係

• 任意のRTGは標準形を持つ

_{[Alexandrakis & Bozapalidis 87]}

• 標準形のRTG規則 q

→ t

• _t

_{∈ Σ}

(0)

_{: ランク0の記号}

• t

∈ N: 非終端記号 (状態)

• t =

σ

(k)

(q

1

, . . . , q

k

) (

σ ∈ Σ, q

1

, . . . , q

k

∈ N)

• FTA

_↑の規則

• _σ

(0)

_{→ q}

• _ε(q

₁

)

→ q

• _σ

(k)

_(q

1

, . . . , q

k

)

→ q

⇒

RTGとFTAは等価

(53)

正規木言語の性質 (閉包性、判定問題)

• 文字列

_{[Hopcroft & Ullman 79]}

、木

_{[Gécseg & Steinby 84]}

文字列

木

正規言語

文脈自由言語

正規木言語

(FSA, rexp)

(CFG, PDA)

(FTA, RTG)

補集合

Yes

L(A) =

{t | t < L(A)} = L(A)

和集合

Yes

No

L(A

1

)

∪ L(A

2

) = L(A

1

∪ A

2

)

積集合

Yes

No

L(A

1

)

∩ L(A

2

) = L(A

1

∩ A

2

)

所属判定

Yes

PTIME

空判定

Yes

PTIME

(54)

重み付きFTA

_↑

. . 0 _. start . 1 . 2 . 3 _. 4 . n . 1′ . 2′ . 3′_. 4′ . n′ ... . 1′′ . 2′′ . n′′ . g ... S / 1.0 . S / 1.0 . the / 2.0 . man / 1.0 . the / 4.2 . a / 3.3 _. man / 4.9 . . / 10.0 . saw / 1.1 . DT / 9.0 . NN / 2.0 . DT / 5.0 . NN / 4.0 . . / 10.0 . NP / 3.0 . NP / 2.8 . VP / 4.9

• 重み付き (w)FTA

_{↑ A = {Q,Σ,F,E,}

_π}

• _{重み付き遷移 r =}

_σ

_(q

₁

_{, . . . , q}

_k

₎

₋

_{→ q ∈ E}

w

• 遷移の重み

_π

(r) = w

• 構文解析や構文に基づく機械翻訳などの解空間

(55)

FTA

_{↑上での演算}

• 自然言語処理で役立ちそうな演算等

重みなし

重み付き

現状 (NLP)

決定化

_{[Comon et. al. 08]} _{[May & Knight 06]}

現実的に動かない

無曖昧化

_{[林 & 永田 14]} _{[林 & 永田 14]}

現実的に動かない

最小化

_{[Comon et. al. 08]} _{[Maletti 08]}

出番がない

積集合

_自明? _{[May 10]}

リスコアリング

制約付き探索

k-best探索

N/A [Huang & Chiang 05]

識別学習

(56)

積集合演算 (Intersection)

• Intersection A

1

=

{Q

1

,

Σ,F

1

, E

1

,

π

1

} ∩ A

2

=

{Q

2

,

Σ,F

2

, E

2

,

π

2

}

1:

E = /0

2:

for all (q, q

′

)

∈ Q

1

× Q

2

do

3:

for all

_σ

(k)

_{∈ Σ do}

4:

for all

_σ

(k)

_(q

1

, . . . , q

k

)

w1

−→ q ∈ E

1

do

5:

for all

σ

(k)

(q

′₁

, . . . , q

′_k

)

_{−→ q}

w2 ′

_{∈ E}

2

do

6:

_r

←

σ

(k)

_((q

1

, q

′1

), . . . , (q

k

, q

′k

))

w1+w2

−−−−→ (q,q

′

₎

7:

E

← E ∪ {r}

8:

π(r) ← w

₁

_{+ w}

₂

9:

_{return A =}

{Q

₁

× Q

₂

_,

Σ,F

₁

× F

₂

_{, E,}

π}

• _{計算量 O(}

_|E

₁

_||E

₂

_|)

• wFTA

_{↑ A}

₂

: 精巧な木言語モデルや制約を表した木正規表現

(57)

wFTA

_{↑上でのk-best導出探索}

ビタビ

最良優先

A*

wFSA

1-best

[Viterbi 67] [Dijkstra 59] [Hart et. al. 68]

k-best

[Eppstein 94] ?? ??

wFTA

_↑

1-best

_自明? [Knuth 77] [Klein & Manning 03]

k-best

[Huang & Chiang 05] [Huang 06] [Paul & Klein 09]

• 文献

_{[Huang & Chiang 05]}

ではAlgorithm0、

1、

2、

3が提案されている

• Algorithm2が実装と効率の観点から最も良く使われている

(58)

Huang & Chiang 05のAlgorithm2

• 各状態で累積重み上位k個の仮説を効率的に求める

• 例: 状態

_q0

における累積重み上位3個の仮説を求め

る (3

× 3 + 3 × 3 = 18通り)

q₂ X(q1q2)−−→ q0.5 0 0.6 0.4 0.3 0.9 q1 0.5 0.3 q₄ Y(q3q4)−−→ q0.3 0 0.8 0.2 0.1 0.8 q3 0.4 0.2

priority queue:

3-best:

• 計算量 O(

|E| + |Q|klogk)

(59)

Huang & Chiang 05のAlgorithm2

• 各状態で累積重み上位k個の仮説を効率的に求める

• 例: 状態

_q0

における累積重み上位3個の仮説を求め

る (3

× 3 + 3 × 3 = 18通り)

q2 X(q1q2)−−→ q0.5 0 0.6 0.4 0.3 0.9 0.27 q₁ 0.5 0.3 q4 Y(q3q4)−−→ q0.3 0 0.8 0.2 0.1 0.8 0.192 q₃ 0.4 0.2

priority queue: 0.27 0.192

3-best:

• 計算量 O(

|E| + |Q|klogk)

(60)

Huang & Chiang 05のAlgorithm2

• 各状態で累積重み上位k個の仮説を効率的に求める

• 例: 状態

_q0

における累積重み上位3個の仮説を求め

る (3

× 3 + 3 × 3 = 18通り)

q2 X(q1q2)−−→ q0.5 0 0.6 0.4 0.3 0.9 1-best 0.18 q1 0.5 0.15 0.3 q₄ Y(q3q4)−−→ q0.3 0 0.8 0.2 0.1 0.8 0.192 q3 0.4 0.2

priority queue: 0.192 0.18 0.15

3-best: 0.27

• _{計算量 O(}

_{|E| + |Q|klogk)}

(61)

Huang & Chiang 05のAlgorithm2

• 各状態で累積重み上位k個の仮説を効率的に求める

• 例: 状態

_q0

における累積重み上位3個の仮説を求め

る (3

× 3 + 3 × 3 = 18通り)

q2 X(q1q2)−−→ q0.5 0 0.6 0.4 0.3 0.9 1-best 0.18 q1 0.5 0.15 0.3 q4 Y(q₃q₄)0.3 −−→ q0 0.8 0.2 0.1 0.8 2-best 0.048 q3 0.4 0.096 0.2

priority queue:

0.18 0.15 0.096 0.048

3-best: 0.27 0.192

• _{計算量 O(}

_{|E| + |Q|klogk)}

(62)

Huang & Chiang 05のAlgorithm2

• 各状態で累積重み上位k個の仮説を効率的に求める

• 例: 状態

_q0

における累積重み上位3個の仮説を求め

る (3

× 3 + 3 × 3 = 18通り)

q2 X(q₁q₂)_{−−→ q}0.5 0 0.6 0.4 0.3 0.9 1-best 3-best q₁ 0.5 0.15 0.3 q4 Y(q₃q₄)0.3 −−→ q0 0.8 0.2 0.1 0.8 2-best 0.048 q3 0.4 0.096 0.2

priority queue:

0.15 0.096 0.048

3-best: 0.27 0.192 0.18

• _{計算量 O(}

_{|E| + |Q|klogk)}

(63)

Huang & Chiang 05のAlgorithm2

• 各状態で累積重み上位k個の仮説を効率的に求める

• 例: 状態

_q0

における累積重み上位3個の仮説を求め

る (3

× 3 + 3 × 3 = 18通り)

q2 X(q₁q₂)_{−−→ q}0.5 0 0.6 0.4 0.3 0.9 1-best 3-best q₁ 0.5 0.15 0.3 q4 Y(q₃q₄)0.3 −−→ q0 0.8 0.2 0.1 0.8 2-best 0.048 q3 0.4 0.096 0.2

priority queue:

0.15 0.096 0.048

3-best: 0.27 0.192 0.18

• _{計算量 O(}

_{|E| + |Q|klogk)}

(64)

木に対する文法、受理機械、変換機械

• 文法•受理機械:

文字列

木

文法

正規文法

正規木文法

文脈自由文法

受理機械

有限オートマトン

木オートマトン

プッシュダウンオートマトン

• 変換機械:

文字列ペア

木ペア

変換機械

有限トランスデューサ

??

木オートマトン•トランスデューサによる 自然言語処理