部分木に基づくマルコフ確率場と言語解析への適用
工藤 拓

松本 裕治

奈良先端科学技術大学院大学 情報科学研究科〒 630-0192 奈良県生駒市高山町 8916-5{taku-ku,matsu}@is.aist-nara.ac.jp
近年, 統計的言語処理の分野において , 分類アルゴ リズムを順次適用して結果を得る History-based Methodsに代わり, 解析木, 解析タグ列 1 つを学習データとみなし , 大域的な最適解を導出できるモデル (マルコフ確
率場 (MRF), 条件付き確率場 (CRF)) が注目を浴びている. しかし , 素性の設計は任意であり, 恣意的に設計されることが多かった. 本稿では , MRF に基づく言語解析のための, 一般的で , 効率よい素性選択手法を提案する. 具体的には , 全部分木を素性候補とし , 統計的な相関性に基づき, 有益な素性を選択する. 英語の品詞タグ付け , 英語の基本句同定を用いて有効性を検証したところ, 従来手法に比べ, 高精度を示した.
キーワード : マルコフ確率場, 対数線形モデル , 頻出部分木マイニング , テキストチャンキング , 品詞タグ付与

Subtree-based Markov Random Fields and
Its application to Natural Language Analysis
Taku Kudo

Yuji Matsumoto

Graduate School of Information Science, Nara Institute of Science and Technology
8916-5 Takayama, Ikoma Nara 630-0192 Japan{taku-ku,matsu}@is.aist-nara.ac.jp
Global discriminative models, such as Markov Random Fields, (MRF) and Conditional Random Fields(CRF), have gained a great attention in the statistical natural language analysis. These models are shownto outperform the history-based approaches, where a parsed-tree can be generated by a sequential processof classifications. In the global optimization with MRF/CRF, the feature set can be selected heuristically.
In this paper, we propose a subtree-based log-linear model, where statistically-useful subtrees are used
as a feature set. Experiments with POS-Tagging and Base-Phrase Chunking show that our approaches
outperform the previous heuristic selections.
Keywords : MRF, CRF, Log-Linear Model, Frequent Subtree Mining, Text Chunking, POS Tagging

1

Random Fields, MRF) を構文解析に最初に適用している [2]. Jung らは , MRF を , 品詞タグ付与問題に適
機械学習の各種の手法が , 品詞タグ付与, テキストチ 用している [3]. Lafferty らは , MRF をタグ付与問題
ャンキング , 固有表現抽出, 構文解析といった自然言語 に特殊化した条件付き確率場 (Conditional Random
処理に適用されるようになり, 数多くの成功をおさめ Fields, CRF) を提案している [20, 27]. MRF は , 対ている. これらの多くは , History-based Methods 数線形モデルの一種であり, 構文木の確率値の対数という一連の手法として一般化できる. History-based が , 構文木の局所的な , ポテンシャル (尤度) を返す素Methods では , 品詞列や構文木が , 「分類問題の順次 性関数の線形結合として表現される. MRF に基づく適用」という形で表現され , 解析結果に対する確率は , 構文解析では , 素性は , 構文木の部分構造として特徴
それぞれの分類問題の確率の積で表現される. 個々 付けられる. これらの手法に共通する特徴としては ,の分類には , SVM といった既知の分類器が用いられ 1 つの構文木を 1 つの学習事例として捉えているとる. この手法は , 比較的高精度であり, 機械学習の手 ころであろう. これらには , 構築順序という概念が無法を直接適用可能であるといった利点を備えている. く, どのような方法, 順序で構文木を構築しても, 一
しかし , 「最適な」適用順序を一意に決定することは 意の確率値を得ることができる.
容易ではないという問題が内在する. 換言すると , 構
MRF は , 構文木全体をモデル化するのに優れてい
文木や品詞タグ列を表現するための「構築順序」に るが , モデルの良さは , 部分構造を特徴付ける 「素性は多くの候補があり, 精度はその設計に強く依存して 関数」の設計に強く依存する. 広い文脈情報を考慮いる. 最適な設計はしばしば発見的に選択される.
するために , 複雑な素性関数を用意すると , 素性関数
この問題を解決するためのいくつかの手法が提案 の候補数が指数的に増えてしまう. 逆に , 素性関数をされている. Abney は , マルコフ確率場 (Markov 単純にすると , 構文解析に必要な重要な文脈情報を取はじめに

りこぼしてしまう可能性がある. 素性関数の設計は ,モデル化するデータに強く依存しており, 事前に求まるものではない. これまでの研究では , いわゆる「素性テンプレート 」を人手で発見的に用意し , それに基づき素性を選択していた [12, 27]. しかし , このような人手に基づく設計では , 重要な部分構造を取りこぼしてしまう可能性がある. かといって, テンプレート
をいたずらに複雑にすることは , 解析効率という観点からも無駄が多く, 避けるべきである.

1.2

History-based Methods

History-based Methods[6](以下 HM) は , 言語解析の多くのタスクに適用されている [18, 30, 11, 25]. HM
は , 言語解析を分類問題の順次適用として定式化し ,解析木 Y を , ある正準的な構築順序 D = hd1 . . . dn iに分解する. つまり, 解析とは , 最も確からしい構築
順序 D̂ を全候補 Y ∈ Y(X) から発見する一種の探索問題として定式化される. これらの表記を用いると ,条件付き確率 P (Y |X) は , 以下のように与えられる.
本稿では , MRF に基づく言語解析のための, 一般的Y
P (di | Φ(ψ(X, d1 . . . di−1 ))),
で , 効率よい素性選択手法を提案する. 従来の MRF P (Y |X) =i=1...nに基づく手法では , 人手によって素性を設計していたが , 本手法では , 膨大な素性候補から , 統計的な相関 ただし , (d1 . . . di−1 ) は , i 番目の決定に用いられる性に基づき, 有益な素性を選択する. 効率良い素性選 履歴 (history) であり, ψ(·, ·) は , 履歴と入力木から ,択のために , 頻出部分木マイニングアルゴ リズムであ 部分的に解析された解析木を構成する関数である. さる FREQT [1, 29] を用いる. さらに , FREQT を拡 らに , Φ(·) は , 部分的に解析された解析木から , <H
張した効率良い構文解析手法についても言及する. ま 次元のベクトルに写像する関数である. HM では , 現た, 英語の品詞タグ付与, 英語の基本句同定を用いて 在の位置での分類は , 以前に与えられた分類結果に依本手法の有効性を検証する.
存する. HM の学習は , 元の解析問題を , 既知の多値

1.1

統計的言語解析

構文解析や, 品詞タグ付与といった言語解析は , 木
から木への写像関数 f : X → Y, を与えられた学習
データ {hXk , Yk i}L
k=1 , (ただし Xk ∈ X , Yk ∈ Y) から導出する一種の教師付き学習として定式化できる.
言語解析では , X は , 入力文であり, Y(X) は , 入力
文 X に対する可能な解析候補である. 議論を一般化するために , X, Y は , 一般的な木として表現されるものとする. (文や品詞列, 構文木は , 木の特殊形である). このような定式化のもと , X, Y を , それぞれ 入
力木 , 解析木 と呼ぶこととする. 図 1 に , 言語解析の例を示す.
統計的な言語解析では , 木のペア hX, Y i に対し ,条件付き確率 P (Y |X) を与えることを考える. 入力
木 X に対する, 最も確からしい解析木 Ŷ は , Ŷ =argmaxY ∈Y(X) P (Y |X) として与えられる. 言語解
析における研究の議論は , 確率 P (Y |X) の精度良い導出方法と , 候補集合 Y(X) から Ŷ を発見する高効
率な探索手法に注がれる.

YX

PRP VBD DT NN

PRP VBD DT NN

X
I ate a cakeIatea cakeIate

Y
a cake

NP

X
I

ate

a cakeX

VBD
PRP ate
I

NN
DT

ate

a

cake

Y

PRP VBD DT NNI

atea cake

cake

S
NP
PRP

a

Dependency Parsing

2

NP

Text Chunking (Shallow Parsing)Y

PRP VBD DT NN

VP

PRP VBD DT NN
I

Part of Speech Tagging

分類器が適用可能である部分問題の集合に分解する
ことから始まる (hX, Y i 7→ (hx1 , y1 i . . . hxn , yn i), ただし yi = di , xi = Φ(ψ(X, d1 . . . di−1 ))). 次に , 個々の部分問題が iid (独立同一分布) から生成されたものと仮定し , 任意の機械学習アルゴ リズムを実行する.
HM は , 既知の学習アルゴ リズムをブラックボック
ス的に用いることができ, 実装が容易であり, 比較的精度が高いといった多くの利点を備える一方で , いく
つかの欠点が存在する. まず , 木を正準的な構築順序に変換する方法には多くの候補 (トップダウン , ボト
ムアップ , 左角, 右角, 前向き, 後ろ向き など ) が存在
し , ど の順序が最適が一般に決定できない. さらに ,個々の部分問題が , iid から生成されるといるという仮定にはいささか無理がある. 例えば , 品詞タグ付与
やテキストチャンキングといったタグ付与問題を考えてみよう. これらのタスクでは , 文を前から後ろに解析する (前向き解析) か , 後ろから前に解析する (後ろ向き解析) かで , 解析精度が大きく変わることが知られている [18]. 最適な解析方法は , タスクのみならず個々の入力事例に依存する. 従来の手法では , 前向き解析と後ろ向き解析の発見的な組みあわせで , この問題を解決している [18]. HM におけるこのような問題は , ラベルバイアス問題 として認知されている.
詳細は , 文献 [20] に譲る.

ate

I

Phrase Structure Parsing

図 1: 言語解析の例

この章では , Subtree-based Log-Linear Model (以下 SLL) を定式化する. 詳細に入る前に , 木に対する
いくつかの定義, 表記について言及する.

2.1

VP
NP

VBD

DT

NN

a

cake

部分木に基づく対数線形モデル

準備

定義 1 ラベル付き順序木
ラベル付き順序木は , すべてのノードに一意のラベルが付与されており, 兄弟関係に順序が与えられる木である.

本稿では , ラベル付き順序木を単純に木と呼ぶ.

=

Xh X

i
λy − log(Z(Xk ))ky∈S(Yk )定義 2 部分木T と U ラベル付き順序木とする. ある木 T が , Uにマッチする, もし くは , T が U の部分木である の最大化として与えられる. 実際には , 過学習を防ぐ(T ⊆ U ) とは , T と U ノード 間に , 1 対 1 の写像関 ために , パラメータ Λ に対し正規分布の正則化を与数 ψ が定義できることである. ただし , ψ は , 以下の える [9].
3 つの条件を満たす. (1) ψ は , 親子関係を保持する.
i ||Λ||2Xh X(2) ψ は , 兄弟の順序関係を保持する. (3) ψ はラベ LΛ =λy − log(Z(Xk )) −σ2
ルを保持する.
ky∈S(Yk )Λ̂ = argmax LΛ
本稿では , 木 Y 中のすべての部分木の集合を S(Y )Λ(S(Y ) = {Y 0 |Y 0 ⊆ Y }), さらに 木 Y のノード の数
を |Y | と表記する.
これは , 一種の事後確率最大化 (maximum a posteriori estimation, MAP) である. パラメータ σ は , SLL
2.2 SLL の定式化のハイパーパラメータであり, モデルの複雑さと , 学
習データに対する対数尤度のバランスを決定する. σ
マ ル コ フ 確 率 場 (Markov Random Fields
は , デベロップ メントデータを用いたり, 交差検定と(MRF))[8] は , 画像のピクセル , ラベル列といった,いった既知のモデル選択手法を用いて選択される. 最周辺の文脈に依存する値をモデル化するのに適した
適解 Λ̂ は , IIS や GIS といった, Iterative Scaling手法である. m 個のランダムな値 (実数, 離散値, ラ
Algorithm を用いて求められる [9, 24].
ベルなど ) f = {f1 , . . . , fm } を考える. f が , MRF
であるとは , f が以下の条件を満たす時で , かつその時に限る. (1) P (f ) > 0 (∀f ∈ F ) (positivity), 2.3 SLL の近似 (ASLL)(2) P (fi |f1 , . . . , fi−1 , fi+1 , . . . , fm ) = P (fi |Ni )SLL は , すべての部分木を素性として用いることを(markovinaity) (ただし , Ni は , i の近隣 (i ∈/ Ni ) で 除けば , 単純な 対数線形モデルである. ただし , SLLある). 近隣ど うしを結ぶと一種の無向グラフが完成 を実際に運用するには , 以下のような問題がある.
する. このグラフのクリーク集合 C を考えると , 確(1) 解析木の列挙
率 P (f ) は , 個々のクリーク c ∈ C のポテンシャルLΛ の微分 L0Λ の計算は , 最適化問題に不可欠で関数 Vc (f ) の対数線形モデルになることが知られてP
あるが , この導出には , 正規化項 Z(X) を陽に計いる [16] (i.e., P (f ) = exp( c∈C Vc (f ))/Z).
算する必要がある. 換言すると , 入力木 X に対
我々の言語解析問題では , F は , Y(X) が張る森に ,する解析可能なすべての解析木 Y を列挙しなけ
f は , 1 つの木 Y ∈ Y(X) に , 各値 fj は , 木のノードればならない. 解析木の候補数 |Y(X)| は , 入力に , 近隣は , 周辺のノードや構造にそれぞれ対応する.
木のサイズ |X| に対し , 指数的に増えるため, すすべての近隣が全ノード であるような完全グラフをべての解析木を陽に列挙することは , 一般に困難
考え , そのクリークのうち, もとの木 Y の部分木 yである1 2のみに非 0 のポテンシャル λy を与えると , 以下のよ
うな対数線形モデルで条件付き確率 P (Y |X) を定式 (2) 素性集合の構築
SLL における素性は , 解析木 Y 中のすべての部化できる.
分木であり, 部分木のサイズは , 元の木のサイズ
定義 3 Subtree-based Log-Linear Model (SLL)に対し 指数的に増えるため , 素性集合のサイズ
木のペア hX, Y i, に対し , SLL は以下のように条件|F| は , しばしば巨大になる. 素性 (部分木) それ付き確率 P (Y |X) を与える.
ぞれに 1 つのパラメータが対応するため , 巨大なP
パラメータ空間となり, パラメータ Λ の導出がexp( y∈S(Y ) λy )困難になる.
,(1)
P (Y |X) =Z(X)
これらの問題を解決するために , 以下のような修正
X
X
ただし Z(X) =exp(λy ), λy ∈ < を SLL に与える.
Y ∈Y(X)y∈S(Y )
(1) すべての解析候補を使う代わりに , history-based
S
parser が出力する n ベスト解 (例えば n = 20)
木の集合 F = k S(Yk ) は , SLL の素性集合と呼ばを , 全候補とみなす. これは , 文献 [12, 13, 14] とれる. Λ = (λy1 , . . . , λy|F | ) は , SLL のパラメータで同じ設定である. 本稿では , このような候補集合
あり, 素性集合の個々のアイテム (木) に対応する. こを Yh (X) と表記する. 全候補 Y(X) を Yh (X)れらは , 単純な最尤推定法で求めることができる. つで代用した場合, 学習データ hXk , Yk i に対し ,まり, 学習データ T = {hYk , Xk i}L
k=1 に対する対数1 文法や , 事前知識を用いて制限する事は可能であるが , これら
尤度の情報が常に利用できるとは限らない.
X
2 CRF[20] や , Feature Forests[21, 10] は , 動的計画法を用いLΛ =log(P (Yk |Xk ))kて, この問題を解決している. 詳細は , 4.3 章で論じる

Yh (Xk ) ∩ {Yk } = φ となる場合がある. このような場合は , 解析木 Yk に対して SLL の学習が行えない. この問題は , 擬似結果 Yh0 (Xk ) =Yh (Xk ) ∪ {Yk } を用いたり, Yh (Xk ) から最も正解に近い (精度が良い) 擬似解答 Yk0 を正解 Ykの代用とするなどして解決する. このような擬似データを用いることで , Yh (Xk ) ∩ {Yk } 6= φ という条件を想定できる.

定義 4 Approximated SLL (ASLL)
学習デ ータ {hXk , Yk i}L
k=1 , 素性選択パラ メータ
Σ = hτ, χ, L, M i, さらに任意の history-based parser
Yh (·), が与えられた時に , ASLL は , 条件付き確率
P (Y |X) を以下のように与える.
Pexp( y∈S(Y )∩F 0 λy ),(2)
P (Y |X) =Z(X)(2) 全素性集合 F を使う代わりに , その部分集合 ただしXX
F 0 ⊂ F を素性として用いる (ただし , |F 0 | ¿Z(X) =exp(λy ),|F|). 一般には , 任意の素性選択関数 Q(·, ·) ∈Y ∈Yh (X)y∈S(Y )∩F 0{true, f alse} を与え , この関数が真を返す部分
λy ∈ <,
木のみを集合として用いる (i.e., F 0 = {y|y ∈[0
F = {y| y ∈S(Yk ) & Q(y, Σ) = true}
F & Q(y, Σ) = true}, ただし Σ は , 素性選択k
パラメータと呼ばれる).
便宜上, 素性選択関数 Q を以下のような 3 つの素性選択ラメータ Σ = hτ, χ, L, M i は , 交差検定
部分関数 Q1 , Q2 , Q3 に分解する (i.e., Q(y, Σ) = といった既知のモデル選択手法を用いて求めること
Q1 (y, Σ) ∧ Q2 (y, Σ) ∧ Q3 (y, Σ)).
ができる. さらに , 最尤の解析木は以下で与えられる.
(1) 頻度: Q1
X
一般に , 頻出する集合が重要である. そこで , τ Ŷ = argmax P (Y |X) = argmax (λy ) (3)Y ∈Yh (X)Y ∈Yh (X)個以上の学習事例に出現した 部分木のみを素性
y∈S(Y )∩F 0として用いる (i.e., Q1 (y, Σ) = true if |{Yk |y ⊆Yk }| ≥ τ ). このような頻度に基づくフィルタリ 実際には , History-based Method (HM) と , ASLL は
ングは , 統計的自然言語処理において頻繁に適用 異なる観点に基づき解析が行われる. 例えば , 品詞タ
グ付与問題では , HM の多くは , 未知語処理のために ,される.
部分文字列の情報を用いているが , これらの情報は ,(2) 部分木のサイズ : Q2
ASLL
では用いられない. それぞれの情報をうまく大きな部分木 (素性) は , 過学習の原因となりや組みあわせるために, 実際の解析では , 以下のような
すい. また, すべての部分木を用いることは , 汎
線形補完を考える.
化能力という意味で悪い影響を与えるとことが
hiX
知られている [15]. さらに , 与えられたタスクにŶ=argmax
α
λ
+
(1
−
α)L
(Y
|X)
(4)
y
h
対し , 最適な部分木のサイズが存在すると考えるのが自然であろう. これらの理由から , 部分木のサイズに制限を設ける. 具体的には , サイズが L
から M の間にある部分木のみを素性として用いる (i.e., Q2 (y, Σ) = true if L ≤ |y| ≤ M ).
(3) 統計的相関性: Q3
L学 習デ ー タ {hXk , Yk i}
Sk=1 , に 対し , P =L{Yk }k=1 を正例, N = k {Yh (Xk ) − {Yk }} を負例とする. 素性の「 良さ」を , 正例, 負例の分布との一種の相関性で評価することは自然であろう. 相関性を具体的に計測するために , 本
稿では , カイ二乗統計量を用いる. Oij (ただし(i, j) ∈ {P, N } × {y, ȳ}) を部分木 j を含む (含まない), 正例 (i = P ) もし くは , 負例 (i = N )の学習事例とする. 例えば , ON ȳ は , 部分木 y を含まない負例の数となる. 部分木 (素性) y に対する カイ二乗値は , 以下で与えられる.

Y ∈Yh (X)y∈S(Y )∩F 0

ただし 0 ≤ α ≤ 1

Lh (Y |X) は , 解析木 Y の HM Yh (·) に基づく対数
尤度である. このような線形補完は , 文献 [12, 13, 14]でも用いられている. α (0 ≤ α ≤ 1) は , それぞれの影響を決定するパラメータであり, Σ と同様, 交差検定を用いて選択される.

3

実装

3.1

部分木マイニングアルゴリズムの適用

本章では , 素性集合 F 0 を効率良く構築するためのアルゴ リズムについて言及する. 最も単純な方法は ,すべての部分木を事前に完全に列挙して , その後に ,低頻度の素性を取り除くという手法であるが , 素性集
chi(y) = (ad − bc)2 /(a + b)(a + c)(b + d)(c + d),
合のサイズは一般に巨大であり, この手法は実際には
ただし a = OP y , b = ON y , c = OP ȳ d = ON ȳ 適用困難である. さらに , 全部分木を列挙する問題は ,NP 困難であることが知られている. この問題を解決
3 つ目の制約として , カイ二乗値が , ある閾値 χするために , 本稿では , 頻出部分木マイニングアルゴ
以上となるすべての部分木を素性として用いる
リズムを適用する.
(i.e., Q3 (y, Σ) = true if chi(y) ≥ χ).
これらの近似を用い, Approximated SLL は以下 問題 1 頻出部分木マイニング
木の集合 T = {Y1 , . . . , YL } が与えらえた時に , すべのように定式化できる.

Sての部分木 y ∈ k S(Yk ) の候補から , ξ P
個以上の 素性を列挙した後に , カイ二乗に基づき素性を再選択
木に含まれる部分木のみを列挙せよ (i.e., k I(y ⊆ する5 .
Yk ) ≥ ξ).

3.2

ξ はユーザが与えるパラメータで , 一般に , 最小サポート値と呼ばれる. Abe と Zaki は , この問題のために ,効率良い方法 FREQT, TreeMinerV をそれぞれ独立に提案している3 [1, 29]. FREQT, TreeMinerV の鍵となるアイデアは , 木の集合から効率良く部分木を列挙する手法, 最右拡張に集約される.
定義 5 最右拡張 [1]
3 つの木 T (6= φ), T 0 (6= φ) U (6= φ), が与えらた時,
T 0 が , T の U に基づく最右拡張であるとは , 以下の3 つの条件が満たされる時であり, かつその時に限る.
(1) T と T 0 は U の部分木である (i.e., T ⊆ U かつ
T 0 ⊆ U ). (2) T 0 は , T に 1 つの ノード を追加することで構築される (i.e., T ⊂ T 0 かつ |T | + 1 = |T 0 |).
(3) ノードは , T の最右パス上のノード (ルートから
常に右端のノード を葉まで選ぶ) に追加される. (4)追加されるノードは , 最右の兄弟である.

解析の高速化式 (3) (もしくは (4)) を用いて , 実際の解析が行われる. この計算量は , 以下の TreeMatcher 問題のそれと等価であるため, ここではこの問題に着目する.
問題 2 TreeMatcher
木の集合 F 0 と , 木 Y が与えられた時, Y 中のすべての部分木のうち, F 0 に含まれるものを列挙せよ.
(i.e., 集合 {y|y ∈ S(Y ) ∩ F 0 } を構築せよ)

これまでの MRF に基づく言語解析では , 事前に用意された 素性テンプレート を用いていた. つまり, テンプレートに基づき素性を完全に生成し , F 0 中の有無をテストする単純な 「生成-テスト 」で実現できる. しかし , 本モデルでは , そのような明示的なテンプレートがない. 最も単純な解析手法は , Y 中の全素
性 (部分木) を完全に列挙することであるが , 素性集
合 F 0 に存在しない無駄な部分木を大量に生成する可能性があり効率が悪い. 実際に , この問題も, 最右拡
便 宜 上, こ こ で は 次 の よ う な 表 記 を 用 い る: 張を用いて高速に実現できる. 詳細の前に , 木の文字
{hT10 , i01 i, . . . , hTn0 , i0n i} = RME(T, i, U ). ただし 列表現について言及する.
T, Tj0 (j = 1, . . . , n) 及び U は , 定義 5 で導入した木である. つまり, {Tj0 |j = 1, . . . , n} は T の U に基 定義 6 木の文字列表現 [29]づく最右拡張となる木の集合である. また, i (および 木 T を , 以下の方法で一意の文字列表現 str(T ) に
i0j ) は , T (および Tj0 ) の U に基づく最右葉の位置 で 変換する. (1) 初期化 str(T ) = φ (2) 前順序探索
ある (U 中のノードは , 前順序 (pre-order) で順序が付 (pre-order) で , 木のノード を列挙し , 各ノード のラ
与されているものとする). 図 2 に 最右拡張の具体例 ベルを str(T ) の末尾に追加する. (3) 探索中に , 子を示す. 最右拡張を , 再帰的に適用することで , 一種の から親に後戻りする場合, ラベル集合に含まれない特
殊なラベル -1 を str(T ) の末尾に追加する.
RME (T, 4, u)

このような文字列表現の例を図 3 に示す. さらに , F 0
中のすべての木を , 文字列表現に変換し , それらすべ
1 a
c d
c d
h 8
subtree Tてを単一のTRIE で表現する (図 4). 文字列表現中
5
e
b
i
2
9
のラベルの順番と , 最右拡張が広げていくラベルのc 4 d 6 f 8 haa3
順番は同一なので , 構築された TRIE は , 最右拡張
b
b
i 9
c d
f 6
5 e
7 g
c d
によって定義される「 探索木」と同一になる. つまり, 木 Y が与えられると , Y の各ノード に対し , 最
右拡張を行いながら , TRIE を探索していくことで ,図 2: 最右拡張
TreeMatcher が実現できる. TreeMatcher の計算量「探索木」を構築するとができる. FREQT, TreeMi- は , TRIE の深さに依存するが , 深さは定数で抑えら
nierV は , この探索木を深さ優先探索し , 頻出部分木 れるため, O(|Y |) となる.
を発見していく. 位置 i は , 部分木の出現位置を示aroot
す. また, T の任意の上位集合 (上位木) T 0 (T 0 ⊃ T )bsubtrees
λ
a
b
abc
0.3
c d
の頻度は , T の頻度以下になることを利用して , 効率
abd
-0.2
e
良く探索空間を枝刈りすることができる (T が頻出で
bdcda b –1 c
0.5
a b c –1 d e
0.1 0.2
ad
0.1
なければ , どんな上位木 T 0 も頻出ではない). 素性集
c
d
-1
-1
a
bc
0.2
0.3
-0.2
合 F 0 は , 基本的に FREQT(TreeMinerV) を用いて
bib d –1 e
-0.3
c
e
c d
-0.3
構築できる. ただし , カイ二乗値については , 上記の0.5
4
a b c –1 –d –1 –1 i
頻度のような性質 を持たないので , 単純には枝刈りできない. そのため, 頻度とサイズを条件にいったん
図 3: 文字列表現 図 4: 素性集合の TRIEU

arightmost-path

b

a

b

3 FREQT と TreeMinerV は , 定式化や , 解こうとしている問題が微妙に異なるが , 本質的なアイデアは同一である
4 反単調性 (anti-monotonicity) と呼ばれる

5 これまでに , カイ二乗といった統計的検定に基づくマイニン
グアルゴ リズムが提案されている [22]. しかし , 本タスクでは , 後処理で十分実行可能であったため, 採用を見送った.

4は , ESG と呼ばれる高度な言語情報 (syntactic role等) を素性として用いているため, 直接の比較は行わ
4.1 実験環境, 設定
ない. 表 3 は , 本手法の詳細な結果である. また, CRF
は , 8-SVM-HC と同等の精度であることが報告され実験は , 以下の 2 種類のタスクで行った.
ている [27].
• 英語品詞タグ付与 (POS-Tagging)
結果, 両タスクにおいて , 提案手法が , 既存の手法
一般的な英語品詞タグ付与タスクである. Penn に比べ高い精度を示すことが分かった .
Tree-bank/WSJ の 15-18 を学習データ, 21 をテ
ストデータとし , 各種パラメータは , 20 を用いて
表 1: 実験結果 (POS-Tagging)
設定した. History-based Tagger は , 最大エントモデル
精度 (%)
ロピー法 (ME) に基づく解析器 [25] を用いた6 .
ME-HT(n ベスト出力)[25]
95.98
ASLL の適用には , Histroy-based Tagger の結RLT[23]95.87
果を木構造に変換する必要があるが , 図 5(上) のASLL(提案手法)
96.10
ように単純な左下りの木とした . 部分木 (素性)は , 任意の品詞 n-gram や語彙が付与された品詞
表 2: 実験結果 (Base-Phrase Chunking)n-gram である. 評価は , 精度で行った.
モデル
F値• 英語基本句同定 (Base-Phrase Chunking)
ME-HC(n ベスト出力)[25] 93.40
CoNLL-2000 の Shared Task[26] で用いられた,
SVM-HC[19]93.46
英語の基本句 (入れ子が無い最小の句構造) の同
8-SVM-HC[18]93.91
定タスクである7 . Penn Tree-bank/WSJ の 15RW-HC[30]93.57
18 を学習データ, 21 をテストデータとし , 各種
ASLL(提案手法)
94.13
パラメータは , 交差検定にて設定した. HistoryRW-ESG-HC
[30]
94.17
based Chunker には , 正則化付き最大エントロ

実験と考察

ピー法 (ME)[9] に基づく解析器を独自に設計した. 基本的に文献 [25] の拡張であるが , 詳細は割愛する. History-based Chunker の結果は , 図
5(下) のような木構造に変換した. 基本的に , 句
レベルでは , 直後の句に係けておき, 単語はその品詞に , 品詞は , 句内の主辞に係ける. 主辞は , 文
献 [11] のルールに従って選択した. また, 図中には示していないが , 左右ど ちらから係るのか ,句の先頭か末尾か , といった情報を示すノードを単語の兄弟として追加した . 評価は , 一般的な F
値 (精度と再現率の調和平均) で行った.
本手法は , 木構造であれば , どのような表現でも学習対象になりえ , その点からも汎用的な手法であると言える. もちろん , POS-Tagging, Chunking のための,
より洗練された「木表現」について議論の余地はあるが , これらの表現に固定して実験を行った.

4.2

実験結果

表 1 に , POS-Tagging の結果を示す. ME に基づ
く History-based Tagger (ME-HT) に加え , SVM に基づく修正学習法 (RLT)[23] の結果を示す. RLT に用いられるパラメータも, WSJ20 を用いて選択したため, 公平な比較となっている.
表 2 に , Base-Phrase Chunking の結果を示す. MEに基づく History-based Chunker (ME-HC) の結果に加え , SVM に基づく History-based Chunker(SVMHC)[19], 8 つの SVM-HC の多数決 (8-SVM-HC)[18],Reguralized-Winnow に基づく History-based Chunker (RW-HC)[30] の結果を示す. RW-ESG-HC[30]
6 通常の ME ではなく, 正則化項付きの ME[9] を用いた.
7 http://lcg-www.uia.ac.be/conll2000/chunking/ASLL には , 選択すべきパラメータがいくつかある.
その中で L, M は , 各タスクにおいて必要な部分木のサイズであり, 素性選択の上で最も重要なパラメータだと考えられる. L = 2 に固定し , M を変化させた
場合, 精度の最も良い M は , M = 4 (POS-Tagging),
M = 5 (Base-Phrase Chunking) であった. この結果は , 最適なサイズが存在するという我々の直観, 及び , 文献 [15] の分析と合致する.

4.3

関連研究との比較

Collins は , 対 数 線 形モデ ル で , History-based
Parser の結果をリランキングする手法を提案している [12]. CRF[20] は , 同様に対数線形モデルである
が , History-based Parser の結果を用いず , 直接式 (1)の結果を解析木の全候補から学習している. さらに
近年, 対数線形モデルではなく, SVM の枠組みで ,ラベル付与問題を定式化する手法も提案されている(HMM-SVM)[4, 5]. これらの手法は , 人手で設計された「素性テンプレート 」を用いてる点が本手法と異なる. 本手法は , 自動的に素性を選択し , その手法が個々のタスクに依存しないという点で , 優れていると考える.
Data Oriented Parsing (DOP), は , SLL のように木の中のすべての部分木を用いる構文解析アルゴ リ
ズムである [7]. DOP は , 木のサイズや語彙化に関係なく, すべての部分木を , PCFG ベースの文法に変換する. 個々の PCFG の派生ルールの確率は , 親ラベルを共有する全部分木のルールの確率の総和で計算される. DOP は NP 困難であることが知られ , 実
現には , モンテカルロ等のサンプリング法が用いられる. しかし , このようなテクニックを使っても, 十分

POS-Tagging
BOS PRP VP

DT JJ

NN

NN

MD VP

TO RB #

CD NN

.

EOS

He reckons the current account deficit will narrow to only # 1.8 billon .

Base-Phrase Chunking
BOS

NP VP
PRP VP

NP
DT JJ

VP
NN

NN

MD VP

PP

NP

O EOS

TO RB #CD NN.

He reckons the current account deficit will narrow to only # 1.8 billon .

図 5: 木構造への変換, POS-Tagging(上) Base-Phrase Chunking(下)表 3: ASLL による Chunking の結果 (詳細)precision
recall
Fβ=1
ADJP
83.59%
74.43% 78.74
ADVP
81.65%
82.22% 81.93
CONJP
38.46%
55.56% 45.45
INTJ
100.00% 50.00% 66.67
LST
0.00%
0.00%
0.00
NP
94.64%
94.55% 94.60
PP
96.82%
98.19% 97.50
PRT
79.80%
74.53% 77.07
SBAR
91.33%
84.67% 87.88
VP
94.13%
94.38% 94.25
all
94.17%
94.08% 94.13の文法上に実装していたりと , 計算量は問題にならな
い規模である. 我々の目的は , 自動的な素性選択と ,解析に必要な十分大きい素性 (部分木) を用いて解析することであるため, この目的が実現できるようなア
ルゴ リズムを適用するほうが望ましいと考える.

5

おわりに

本稿では , MRF に基づく言語解析のための, 一般
的で , 効率よい素性選択手法を提案した . さらに , 英
語の品詞タグ付与, 英語の基本句同定を用いて本手法の有効性を検証した. 今後の計画として , 以下が挙げられる.
• 他のタスク
本手法は , 言語解析全般に適用できる汎用的な手法である. 今後は , 係り受け解析, 構文解析といったタスクで有効性を検証したいと考える.
な統計量を得るためには , 文のサイズに対し指数的に• グラフ構造増えるルールが必要であり, 実際の応用に適用できる
これまでは , 木構造のみに着目していたが , より
かど うか疑問が残る.
複雑な情報を表現するには , グラフを用いるほう
Tree Kernel [13, 14, 17] に基づく言語解析でも,がよい. 効率良いグラフマイニングアルゴ リズ
SLL, DOP と同様にすべての部分木の情報を用いて
ムが提案されているので [28], 今後は , それらをいる. Kernel 法では , 結果が事例間の内積 (類似度)適用したいと考える.
のみに依存するため, DOP のように , 陽に部分木を列挙する必要はなく, 効率良く内積が計算できさえ• 候補木の列挙
すれば良い. 実際に Tree Kernel は , 動的計画法を
本稿では , History-based Parser の n ベスト解用いて , 陽に列挙することなく内積を計算している.
を用いて, 全候補を近似した. しかし , この近似
しかし , Tree Kernel を用いた言語解析の計算量は ,は妥当とは言いがたい. 今後は , マルコフ連鎖モ
O(L · N · |Y |) であり, 他の手法に比ばれば依然大き
ンテカルロといった精度の良いサンプ リング手
い (ただし , N はサポートベクターとなるの木の平均法を用いて , 解析候補を選択したいと考える8 .
サイズ , L はサポートベクターの数, Y は解析木の候• 学習アルゴ リズム
補). 本手法の計算量は , O(|Y |) であり, Tree Kernel
本稿では , 単純な 対数線形モデルを学習に用いた.
に基づく手法に比べれば , 高速に解析が行える.
しかし , 近年, HMM-SVM のように , SVM の枠
CRF[20] や, その木構造への拡張である Feature
組みで定式化する手法が提案されている [4, 5].
Forests [21, 10] は , 2.3 節の (1) で述べた解析木のSVM を用いると , 限られたサポート事例のみで ,列挙の問題を , 巧妙に解決し ている. 具体的には ,パラメータを表現できるため, 陽に正規化項を列Forward-Backward, Inside-Outside といった, 動的
挙しなければならない問題を解決できるばかり
計画法を拡張し , 正規化項を , 陽に全解析木を列挙す
でなく, 汎化能力を高めることができる9 .
ることなく, 陰に計算している. しかし , これらの手
8 n ベスト解を用いることは , Hitory-based Parser を近似分法は , 部分木のサイズが小さい場合は有効だが , 部分布とする重点サンプ リングを行ってるものと解釈できるが , その木のサイズが大きくなるにつれ , 空間計算量が指数的近似がうまくいくのは , n ベスト解の確率の和がほぼ 1 になる場に増加してしまう. 実際に , 彼等の実験では , 人手で 合のみで, 実際にはこのような仮定は成立しない.
9 HMM-SVM は , 式 (1) を , SVM の枠組みで学習する. 通常の用意された単純な素性テンプレートを用いたり, 既存

参考文献[15] Chad Cumby and Dan Roth. On kernel methods
for relational learning. In Proc. of ICML, pages
107–114, 2003.

[1] Kenji Abe, Shinji Kawasoe, Tatsuya Asai, Hiroki [16] Hammersley and Clifford. Markov fields on finite
graphs and lattices. 1971.
Arimura, and Setsuo Arikawa. Optimized substructure discovery for semi-structured data. In Proc. [17] Hisashi Kashima and Teruo Koyanagi. Svm kernels
6th European Conference on PKDD, 2002.
for semi-structured data. In Proc. of the ICML,[2] Steven P. Abney. Stochastic attribute-value grampages 291–298, 2002.
mars. Computational Linguistics, 23(4):597–618, [18] Taku Kudo and Yuji Matsumoto. Chunking with
1997.
support vector machines. In Proc. of NAACL,[3] Sung-Young Jung adn Young C. Park, Key-Sun
pages 192–199, 2001.
Choi, and Youngwhan Kim. Markov random field[19] Taku Kudoj and Yuji Matsumoto. Use of Support
based english part-of-speech tagging system. In
Vector Learning for Chunk Identification. In Proc.
The 16th International Conference on Computaof of CoNLL-LLL-2000, pages 142–144, 2000.
tional Linguistics, Vol.1, pages 236–242, 1996.
[20] John Lafferty, Andrew McCallum, and Fernando[4] Yasemin Altun, Mark Johnson, and Thomas HofPereira. Conditional random fields: Probabilistic
mann. Investigating loss functions and optimizamodels for segmenting and labeling sequence data.
tion methods for discriminative learning of label seIn Proc. of ICML, pages 282–289, 2001.
quences. In Proc. of EMNLP, pages 145–152, 2003.
[21] Yusuke Miyao and Junichi Tsujii. Maximum en[5] Yasemin Altun, Ioannis Tsochantaridis, andtropy estimation for feature forests. In Proc. ofThomas Hofmann. Hidden markov support vector
HLT-NAACL, 2002.
machines. In Proc. of ICML, pages 3–10, 2003.
[6] Ezra Black, Fred Jelinek, John Lafferty, David M. [22] Shinichi Morishita and Jun Sese. Traversing itemset lattices with statistical metric pruning. In Proc.
Magerman, Robert Mercer, and Salim Roukos.
of ACM SIGACT-SIGMOD-SIGART Symp. on
Towards history-based grammars: Using richer
Database Systems (PODS), pages 226–236, 2000.
models for probabilistic parsing. In Proceedings,
DARPA Speech and Natural Language Workshop, [23] Tetsuji Nakagawa, Taku Kudo, and Yuji Matsumoto. Revision learning and its application to
1992.
part-of-speech tagging. In Proc. of ACL, pages 497–
[7] Rens Bod.
Beyond Grammar: An Experi504, 2002.
ence Based Theory of Language. CSLI Publications/Cambridge University Press, 1998.

[24] Della Pietra, Stephen, Vincent J. Della Pietra, andJohn D. Lafferty. Inducing features of random[8] Rama Chellappa and Anil Jain (eds.). Markov Ranfields. IEEE Transactions on Pattern Analysis anddom Fields: Theory and Applications. Academic
Machine Intelligence, 19(4):380–393, 1997.
Press, 1993.
[9] Stanley F. Chen and Ronald. Rosenfeld. A gaus- [25] Adwait Ratnaparkhi. A maximum entropy model
for part-of-speech tagging. In Proc. of EMNLP,
sian prior for smoothing maximum entropy models.
pages 133–142, 1996.
Technical report, Carnegie Mellon University, 1999.
[10] Stephen Clark and James Curran. Log-linear mod- [26] Erik F. Tjong Kim Sang and Sabine Buchholz.
Introduction to the CoNLL-2000 Shared Task:
els for wide-coverage CCG parsing. In Proc. of
Chunking. In Proc of CoNLL-LLL, pages 127–132,
EMNLP, pages 97–104, 2003.
2000.
[11] Michael Collins. Head-Driven Statistical Models for
Natural Language Parsing. PhD thesis, University [27] Fei Sha and Fernando Pereira. Shallow parsing
with conditional random fields. In Proc. of HLTof Pennsylvania, 1999.
NAACL, pages 213–220, 2003.
[12] Michael Collins. Discriminative reranking for natural language parsing. In Proc. of ICML, pages [28] Xifeng Yan and Jiawei Han. gspan: Graph-based
substructure pattern mining. In Proc. of ICDM,
175–182, 2000.
pages 721–724, 2002.
[13] Michael Collins and Nigel Duffy. Convolution kernels for natural language. In Proc. of Neural Infor- [29] Mohammed Zaki. Efficiently mining frequent trees
in a forest. In Proc. of KDD, pages 71–80, 2002.
mation Processing Systems (NIPS), 2001.
[14] Michael Collins and Nigel Duffy. New ranking al- [30] Tong Zhang, Fred Damerau, and David Johnson.
Text chunking based on a generalization of winnow.
gorithms for parsing and tagging: Kernels over disJournal of Machine Larning Resarch, 2:615–637,
crete structures, and the voted perceptron. In Proc
2002.
of ACL, 2002.
SVM と異なるのは , 負例 (全候補解析木から正解の解析木を取りのぞいた集合) が明示的に与えれれないことである. HMM-SVM
は , 学習しながら負のサポートベクターを発見していく