部分木を素性とする Decision Stumps と Boosting Algorithm の適用
工藤 拓

松本 裕治

奈良先端科学技術大学院大学 情報科学研究科〒 630-0192 奈良県生駒市高山町 8916-5{taku-ku,matsu}@is.aist-nara.ac.jp
近年, テキスト分類タスクの多様化に伴い, 単語の集合 (Bag-of-Word) を素性とする古典的手法では , 十分な精度を得にくくなっている. 精度向上には , テキストの構造 (構文/レ イアウト ) を考慮する必要があるが ,恣意的に選択された部分構造のみを用いた手法が多い. 本稿では , 構造を考慮したテキスト分類 (半構造化
テキスト分類) に向け , 部分木を素性とする Decision Stumps と , それを弱学習器とする Boosting アルゴ
リズムを提案する. また, Tree Kernel を用いた SVM との関連性, 及び本手法の利点について言及する. 実
データを用いた実験により, 提案手法の有効性を検証する.
キーワード : Decision Stumps, Boosting, 半構造化テキスト分類, Tree Kernel

Boosting with Subtree-based Decision Stumps and
Its application to Semi-strucutred Text Classification
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
The research focus in text classification has expanded from a simple topic identification to a more challenging task, such as opinion/modality identification. For the latter, the traditional bag-of-word representations are not sufficient, and a richer, more structural representation will be required. Accordingly,
learning algorithms must be able to handle such sub-structures observed in text. In this paper, we
propose a Boosting algorithm that captures sub-structures embedded in text. The proposal consists ofi) decision stumps that use subtree as features and ii) Boosting algorithm in which the subtree-based
decision stumps are applied as weak learners. We also discuss a relation between our algorithm and SVM
with Tree Kernel. Three experiments on the opinion/modality classification tasks confirm that subtree
features are important. Our Boosting algorithm is computationally efficient for classification tasks involving discrete structural features.
Keywords : Decision Stumps, Boosting, Semi-structured Text Classification, Tree Kernel

1

はじめに

SVM といった機械学習手法が , テキスト分類に応用され , 多くの成功をおさめている. テキスト分類では , 一般に単語の集合 (Bag-of-Word 以下 BOW) を素性とし , 政治, 経済, スポーツといったカテゴ リにテキストを分類する. 個々の単語が , これらのカテゴ リを特徴付けるのに十分な情報を与えるため , BOW といった単純な素性でも十分な精度を達成できる.
一方, テキストマイニングの分野では , 「お客様の声」や「現場の声」といったテキストデータから , 早期に危機情報や要求を発見, 分析するための要素技術が求められている. 具体的には , コールセンターログ
からの知識発見, 自由記述アンケートや製品レビュー
記事からの不満表現の発見といったタスクがそれにあたる. これらのタスクでは , 旧来の文書分類に典型的なカテゴ リではなく, 主観的/客観的に述べているのか ?, (ある製品を ) 誉めてる/けなしているのか ?, 背景/結果/結論を述べているのか ? といった書き手の意図に関するカテゴ リが使われる. さらに , 分類単位
が , 文書といった大きな単位からパッセージ , 文のよ
うな小さな単位に変化している. これらのタスクは ,テキスト分類には変わりないが , BOW といった素朴な素性では , 高い精度が得られにくい. 単純には , 品
詞による単語のフィルタリング , 固定長の N-グラム,
係り受け関係 (係り元, 係り先のペア) といった, 有効
そうな素性を発見的に追加することで , ある程度精度向上が期待できる. しかし , これらの手法は , あまりにも発見的であり, タスク依存性が強い.
本稿では , テキストが単語の集合であると仮定す
る従来手法に対し , テキストの「構造」を考慮する学
習/分類アルゴ リズムを提案する. ここでの構造とは ,N-グラム, 係り受け構造, HTML/XML といったラベル付き順序木を指す. この構造は , 自然言語処理に

おいて一般的なものである. さきほど の発見的な手法は , 構造情報を部分的に選択し , 利用しているモデルであると解釈できる.
本稿で提案する学習/分類アルゴ リズムは , 以下の3 点の特徴を持つ.
(1) テキストの構造 (構文構造やレイアウト構造) を考慮した, 学習/分類

2.3

Decision Stumps for Trees

Decision Stumps は , 1 つの素性の有無に基づき分類を行う, 単純な分類アルゴ リズムである. Decision
Stumps は , 深さ 1 の Decision Tree (決定木) とみなすことができる. ラベル付き順序木の分類問題に
対し , 本稿では , 以下のような部分木の有無に基づく
Decision Stumps を考える.

(2) 学習の素性に , 構造の部分木を用いるが , そのサイズに制限を設けず , 全部分木を素性の候補とす 定義 3 Decision Stumps for Trees
る. (係り受け木中の任意のサイズの部分木, 任 t および x を , ラベル付き順序木, y ∈ {±1} を ,クラスラベルとする. 木を分類するための Decision
意の長さの N-グラムが素性となる)
Stumps を以下のように定義する.
(3) 分析を容易にするために , 分類に必要な最小限の(素性を学習アルゴ リズムが自動的に選択する.
y t⊆x
def
hht,yi (x) =以下, 次章では提案手法の詳細, 3 章でその実装方−y otherwise.
法について説明する. 4 章で Tree Kernel を用いた
= y · (2I(t ⊆ x) − 1)
SVM と提案手法の関連性に言及する. 5 章で , 評価
実験とそれらの結果を報告し , 6 章でまとめと今後の分類器のパラメータは , 木 t と ラベル y の組 ht, yi,
課題について述べる.
である. 以後この組を , 分類器の ルール と呼ぶ.

2

提案手法

詳細に入る前に , 木に対するいくつかの定義, 表記について言及する.

Decision Stumps の学習は , 学習デ ータ T ={hyi , xi i}L
i=1 に対するエラー率を最小にするルール
ht̂, ŷi を導出することで実現できる.
L

ht̂, ŷi =

2.1

準備

1 X
(1 − yi · hht,yi (xi ))t∈F ,y∈{±1} 2L i=1
argmin(1)

定義 1 ラベル付き順序木
ただし , F は , 全部分木の集合 (素性集合) である
ラベル付き順序木は , すべてのノードに一意のラベル (i.e., F = SL S(x )). ここで , ルール ht, yi に対すii=1が付与されており, 兄弟関係に順序が与えられる木で る gain(ht, yi)
を以下のように定義する.
ある.
def

gain(ht, yi) =本稿では , ラベル付き順序木を単純に木と呼ぶ.

LX

yi · hht,yi (xi )

(2)

i=1

定義 2 部分木t と u ラベル付き順序木とする. ある木 t が , u にマッチする, もしくは , t が u の部分木である (t ⊆ u)とは , t と u ノード 間に , 1 対 1 の写像関数 ψ が定
義できることである. ただし , ψ は , 以下の 3 つの条件を満たす. (1) ψ は , 親子関係を保持する. (2) ψは , 兄弟の順序関係を保持する. (3) ψ はラベルを保持する.
本稿では , 木 t 中のすべての部分木の集合を S(t)(S(t) = {t0 |t0 ⊆ t}), さらに 木 t のノード の数を |t|と表記する.

2.2

ラベル付き順序木の分類問題

ラベル順序木の分類問題 (木の分類問題) とは , L
個の学習データ T = {hyi , xi i}L
i=1 から , 分類関数
f (x) : X → {±1} を導出することである. ただし ,xi ∈ X はラベル付き順序木であり, yi ∈ {±1} は , 木
xi に付与されたラベルである (ここでは , 2 値分類問
題を考える). 通常の学習, 分類問題との違いは , 事例
xi が , 数値ベクトルで表現されるのではなく, ラベル付き順序木として表現される点にある.

gain を用いると , (1) の最小化問題は , 以下の最大化問題と等価となる.
ht̂, ŷi =argmax gain(ht, yi)t∈F ,y∈{±1}

本稿では , エラー率最小のかわりに , それと等価である gain の最大化を用いて , Decision Stumps の学習を定式化する.

2.4

Boosting の適用

部分木を素性とする Decision Stumps は , 1 つの部分木の有無に基づき分類を行うため , それ単独では精度が悪い. しかし , Boosting[6] を用いて , その精度を向上させることができる. Boosting は , 逐次
弱学習器 (ここでは , 部分木を素性とする Decision
Stumps) を構築し , それらの重み付き多数決によって, 最終的な分類器 f を構成する. k 番目の弱学
習器は , それぞれ異なった事例分布 (重み) d(k) を(k)(k)
用いて学習される. d(k) = (di , . . . , dL ), (ただしPNk(k)
は , 分類が困難な事
i=1 di = 1, di ≥ 0). 分布 d
例に高い重みが与えられるように逐次更新される. 弱学習器が無作為分類よりも精度が良いことさえ満足す
れば , 単一の弱学習器より, Boosting の汎化能力が高くなることが理論的に証明されている [6]. Decision
Stumps を弱学習器とする Boosting を構築するには ,分布 d を考慮するよう 式 (2) を再定義すればよい.

gain(ht, yi)

def

=

L
X

di · yi · hht,yi (xi )i=1

イズ 1 の木が列挙される. そして , サイズ (k − 1) の木に , 1 つのノードを追加することでサイズ k の木を構築する. この手続きを再帰的に適用することで全部分木を列挙する. しかし , 任意の位置にノード を追加すると重複する木を生成してしまうため , ノードの追加に一種の制限を設ける. この制限が最右拡張の鍵となるアイデアである. 以下に最右拡張の定義を与える.

Boosting の 中で , 最も 有名なアルゴ リズ ムは ,AdaBoost[6] であろう. しかし , 本稿では , AdaBoostの代わりに , Breiman らによる Arc-GV [2] を用いる
(Arc-GV を用いる理由は , 4 節で説明する). また, 以
下断りが無い限り, Boosting は , Arc-GV のことを差すこととする.

定義 4 最右拡張 [1]
3 つの木 t(6= φ), t0 (6= φ) u(6= φ), が与えらた時, t0
が , t の u に基づく最右拡張であるとは , 以下の 3つの条件が満たされる時であり, かつその時に限る.
(1) t と t0 は u の部分木である (i.e., t ⊆ u かつt0 ⊆ u). (2) t0 は , t に 1 つの ノード を追加することで構築される (i.e., t ⊂ t0 かつ |t| + 1 = |t0 |). (3)ノードは , t の最右パス上のノード (ルートから常に3 実装
右端のノード を葉まで選ぶ) に追加される. (4) 追加
本章では , 最適なルール ht̂, ŷi を発見するための高されるノードは , 最右の兄弟である.
速なアルゴ リズムを提案する. 最適ルール発見問題
は以下のように定式化される.
便 宜 上, こ こ で は 次 の よ う な 表 記 を 用 い る :ただし{ht01 , i01 i, . . . , ht0n , i0n i} = RME(t, i, u).
問題 1 最適ルール発見問題
学習データ T = {hx1 , y1 , d1 i . . . , hxL , yL , dL i} (ただ t, t0j (j = 1, . . . , n) 及び u は , 定義 4 で導入した木
し , xi は順序木, yi ∈ {±1} は木に対応するクラスラ である. つまり, {t0j |j = 1, . . . , n} は t の u に基づPL
ベル , di ( i=1 di = 1, di ≥ 0) は , 木の重み) が与え く最右拡張となる木の集合である. また, i (および00
らえた時, gain を最大にするルール ht̂, ŷi を発見せよ. ij ) は , t (および tj ) の u に基づく最右葉の位置 で(ただし , ht̂, ŷi = argmaxt∈F ,y∈{±1} di yi hht,yi (xi ), ある (u 中のノード は , 前順序 (pre-order) で順序がSL付与されているものとする). 図 1 に 最右拡張の具体
F = i=1 S(xi )).
例を示す.
単純な方法は , 全部分木 F を陽に列挙し , そこかRME (t, 4, u)u
ら最大の gain を与える部分木を選択することであろaarightmost-pathう. しかし , 部分木の個数は , 木のサイズに対し指数bb1 a
的に増えていくために , こういったしらみつぶしの方
c d
c d
h 8
subtree te 5i
法は実際の問題には適用困難である. 実際に , 木の集
2 b
9合から全部分木を完全に列挙する問題は , NP 困難で
c 4 d 6 f 8 haa3あることが分かっている.
bbi 9
本稿では , 最適ルール発見問題のための効率良いア
c d
f 6
5 e
7 g
c d
ルゴ リズムを提案する. 提案手法は以下の 3 つの戦略から構成される.
図 1: 最右拡張(1) 木の集合から , 全部分木を完全に重複なく列挙するための正準的な探索空間を定義する(2) 1 で定義した探索空間を深さ優先探索し , 最大のgain を与える部分木を発見する.
(3) 1, 2. だけでは , 全部分木をしらみつぶしに列挙
してることと変わりない. そこで , gain の上限値を用い, 探索空間を枝刈りする.
この 3 つの戦略について , 順に説明する.

3.1

部分木の列挙方法
図 2: 最右拡張の再帰 (探索木)
Abe と Zaki は , 木から , その部分木を , 完全に重複なく列挙するアルゴ リズム最右拡張を , それぞれ独
最右拡張を , 再帰的に適用することで , 一種の「探立に提案している [1, 17]. 最右拡張は , 部分集合を列 索木」を構築するとができる. 図 2 に , その探索木の挙するアルゴ リズム Set Enumuration Tree [8] の部 例を示す (図 2 中では , 便宜的にラベルの種類を 1 種
分木への自然な拡張となっている. まずはじめに , サ 類のみとしている).

3.2

探索空間の枝刈り

本章では , 前章で定義した探索空間を , 効率良く枝刈りする手法について議論する. 定理 1 (Morishita[10]の拡張) は , t の上位木 t0 に対する gain(ht0 , yi) の上限値を与える.
定理 1 gain の上限値: µ(t)t の全上位木 t0 ⊇ t, y ∈ {±1} について, ルー
ル ht0 , yi の gain は µ(t) を 上限値とする (i.e.,gain(ht0 yi) ≤ µ(t)). ただし , µ(t) は以下で与えら
れる.
def

µ(t)

=

³
max 2

X

{i|yi =+1,t⊆xi }

X

2

L
X

di −
di +

i=1
L
X

Algorithm: Find Optimal Rule
argument: 学習データ: T = {hx1 , y1 , d1 i . . . , hxL , yL , dL i}(ただし , xi は順序木, yi ∈ {±1} はクラス,
PLdi ( i=1 di = 1, di ≥ 0) は重み)returns:
最適ルール ht̂, ŷi
beginτ = 0 // 準最適 gain
function project (t, loc = {hi1 , j1 i, . . .})if µ(t) ≤ τ then return (1)y 0 = argmaxy∈{±1} gain(ht, yi)
if gain(ht, y 0 i) > τ thenht̂, ŷi = ht, y 0 i
τ = gain(ht̂, ŷi) // 準最適
endyi · di ,´
yi · di .

i=1{i|yi =−1,t⊆xi }証明 1

gain(ht0 , yi)=LXdi yi hht0 ,yi (xi )

i=1
L

=

X

で , 任意の木 t について, もし µ(t) ≤ τ ならば , t の
全上位木 t0 の gain は , τ 以下であるため, t が張る部分空間は安全に枝刈りできる. 逆に µ(t) > τ ならば , gain(t0 , y) > τ となる上位木 t0 が存在する可能性があるため, 枝刈りできない.
また, µ(t) > τ となり, ノード s が , 木 t に最右拡張により追加される場合でも, µ(s) < τ ならば , 拡張
された木 t0 が張る部分空間を枝刈りできる.
図 3 にアルゴ リズム Find Optimal Rule の擬似
コード を示す. 上記の 2 つの枝刈りの条件を それぞれ (1) と (2) に記す.

di yi · y · (2I(t0 ⊆ xi ) − 1)

i=1

ここで , y = +1 の場合に着目すると
0gain(ht , +1i)

=

2

X

¡

di

−

{i|yi =+1,t0 ⊆xi }
L

−

X

X

di

idx = φ // hashforeach hi, ji ∈ loc
foreach ht0 , j 0 i ∈ RME(t, j, xi )if µ(t0 − t) ≤ τ then continue (2)idx[t0 ] = idx[t0 ] ∪ {hi, j 0 i}
end
end
foreach keys t0 ∈ idx
project(t0 , idx[t0 ])end¢{i|yi =−1,t0 ⊆xi }yi · di

i=1

≤

X

2

di −

{i|yi =+1,t0 ⊆xi }

≤

X

2

di −

{i|yi =+1,t⊆xi }LX

yi · d i

i=1
L

X

end

yi · dii=1

foreach t0 ∈ {t|t ∈ ∪L
i=1 S(xi ), |t| = 1}
loct0 ← t0 を含む 事例 i と位置のペアの集合
project (t0 , loct0 )end
return ht̂, ŷi(∵ t の全上位木 t0 ⊇ t について |{i|yi = +1, t0 ⊆ xi }| ≤|{i|yi = +1, t ⊆ xi }| が成立するため.) 同様に ,gain(ht0 , −1i)

≤

2

X

di +

{i|yi =−1,t⊆xi }LX

yi · d i

図 3: アルゴ リズム: Find Optimal Rulei=1

以上より, t の全上位木 t0 ⊇ t, y ∈ {±1} について

³

X

end

X
L

3.3

Boosting の高速化

Boosting の逐次計算の度に , 準最適解 τ は 0 にリセットされる. しかし , もしタイトな上限値をあらか
i=1{i|yi =+1,t⊆xi }L´ じめ見積もることができれば , 探索空間を , より効率
X
X
良く枝刈りできる. この目的のために , 逐次計算中にyi · di2
di +発見されたルールをキャッシュに保持していく. 準最i=1{i|yi =−1,t⊆xi }適解 τ は , キャッシュ中のルール集合から最大の gain
= µ(t) ■を与えるルールを選択し , 計算する. このアイデアは ,最右拡張が定義する探索空間を , 深さ優先探索しなが Boosting の逐次計算が進むにつれ , 同じルールが繰
ら , 準最適 gain τ と準最適ルールを保持する. ここ り返し使われるという我々の観察に基づいている.
gain(ht0 , yi)

≤

max 2

di −

yi · di ,3.4

分類の高速化ab

最終的な分類関数 f (x) は , 2|F| (= |F| × |{±1}|)個の仮説の線形結合として表現できる.
³´
X
wht,yi · hht,yi (x) (3)f (x) = sgn

csubtrees

d

abc

0.3

e

abd

-0.2

a b c –1 d eabt∈F ,y∈{±1]}

c

i

root

λ

a b –1 c

0.5

ad

0.1

bc

0.2

b d –1 e

-0.3

a
b
c

d

0.3

-0.2

d

b
d

c

0.1

0.2

d

-1

-1

c

e

0.5

-0.3

a b c –1 –d –1 –1 i

各仮説 hht,yi に対する重み wht,yi (≥ 0) が , Boostingの逐次計算で導出される. さらに , 式 (3) は , 以下のような線形分類器に変形できる.
³´
X
f (x) = sgn
wht,yi · y · (2I(t ⊆ x) − 1)

図 4: 文字列表現4

図 5: 素性集合の TRIESVM との関連性

本節では , Tree Kernel[5, 9] を用いた Support Vector
Machine (SVM) と提案手法の関連性を 文献 [11]´
³X
λt · I(t ⊆ x) − b(4) の分析に基づき論じる. 近年の研究 [2, 12, 11] によ= sgn
り, Boosting と SVM は本質的に同一であり, 共にt∈G
最小マージンの最大化に基づく学習アルゴ リズムと
ただし ,して単一化できることが明らかになった . SVM とBoosting の唯一違いは , マージンのノルムである.
G = {t|t ∈ F , (wht,+1i − wht,−1i ) 6= 0},
AdaBoost 及び , Arc-GV は , 漸近的に以下の線形
λt = 2 · (wht,+1i − wht,−1i ),計画問題を解いていることが知られている [2, 12, 11].
Xb =(wht,+1i − wht,−1i )
max
ρ
(5)
t∈G
t∈F ,y∈{±1]}w∈<J ,ρ∈<+G は , 分類に必要な素性集合 (以後, サポート 素性 と呼ぶ) である. 式 (4) の計算量は , 以下の TreeMatcher
問題のそれと等価であるため, ここではこの問題に着
目する.

s.t.

yi

J
X

wj hj (xi ) ≥ ρ

(6)

j=1

||w||1 = 1,

(7)

ただし , J は , 仮説の個数である. (Decision Stumps
を用いた場合は , J = |{±1} × F| = 2|F| となる.)Breiman らは , Arc-GV が上記の問題を漸近的に解いていることを理論的に示している [2]. この理論的漸近性から , 本稿では AdaBoost を用いず Arc-GV
実際に , この問題も, 最右拡張を用いて高速に実現で を用いることとした.
きる. 詳細の前に , 木の文字列表現について言及する.
一方, SVM は , 以下の 2 次計画問題の最適化として定式化される [14] 1 .
定義 5 木の文字列表現 [17]木 t を , 以下の方法で一意の文字列表現 str(t) に変
max
ρ
(8)
w∈<J ,ρ∈<+換する. (1) 初期化 str(t) = φ (2) 前順序探索 (pres.t.
yi · (w · Φ(xi )) ≥ ρ(9)order) で , 木のノードを列挙し , 各ノード のラベルを||w||2 = 1.
(10)
str(t) の末尾に追加する. (3) 探索中に , 子から親に問題 2 TreeMatcher
木の集合 G と , 木 x が与えられた時, x 中のすべての部分木のうち, G に含まれるものを列挙せよ. (i.e.,
集合 {t|t ⊆ x} ∩ G を構築せよ)

後戻りする場合, ラベル集合に含まれない特殊なラベ関数 Φ(x) は , 事例 x を J 次元空間に写像する関ル -1 を str(t) の末尾に追加する.
数である (i.e., Φ(x) ∈ <J ). l2 -norm のマージンのこのような文字列表現の例を図 4 に示す. さらに , G 場合, 分離平面の構築には , 素性を陽に展開する必要
中のすべての木を , 文字列表現に変換し , それらすべ はなく, 事例間の内積 (Kernel) K(x1 , x2 ) = Φ(x1 ) ·てを単一の TRIE で表現する (図 5). 文字列表現中 Φ(x2 ) さえ与えられればよい. このような考えに基づのラベルの順番と , 最右拡張が広げていくラベルの き, ラベル付き順序木の内積を定義したものが Tree
順番は同一なので , 構築された TRIE は , 最右拡張 Kernel[5, 9] である. Tree Kernel は , 個々の部分木をによって定義される「 探索木」と同一になる. つま 個別の素性とする. つまり, 写像関数 Φ(x) は , Φ(x) =り, 木 x が与えられると , x の各ノード に対し , 最 (I(t1 ⊆ x), . . . , I(t|F | ⊆ x)) となる. ここで , 全ルー
右拡張を行いながら , TRIE を探索していくことで , ル ht, yi ∈ F × {+1, −1} それぞれの分類結果を ,TreeMatcher が実現できる. TreeMatcher の計算量 個々の次元に対応させるよう, 写像関数 Φ(x) を再設
は , TRIE の深さに依存するが , 深さは定数で抑えら 計してみる (Φ(x) = (2I(t1 ⊆ x) − 1, . . . , 2I(t|F | ⊆れるため, O(|x|) となる. これは Tree Kernel に基 x) − 1, −2I(t1 ⊆ x) + 1, . . . , −2I(t|F | ⊆ x) + 1)).
1 議論を単純にするために , バイアス項 (b), ソフトマージンはづく SVM の計算量に比べ小さい (詳細は次章で説明
する).
考えない

PHS ユーザに , 良い点/悪い点を区別してレビ
全弱学習器を個々の次元とする素性性空間 (仮説素ューを投稿するよう指示した掲示板のデータで性空間) は , 全部分木を用いる Tree Kernel の基礎ある. 分類単位は「文」, 文数は 5,741, カテゴとなる概念を変えない. つまり, 部分木を素性とする
リは「良い点」「悪い点」の 2 つである.
Decision Stumps と Tree Kenrnel に基づく SVM は ,素性空間という観点において , 本質的に同一であると• 文のモダリティ分類 (MOD)いえる.
被験者 1 名が , 田村ら [18] の大分類に従い, 99 年
2 つのアルゴリズムの唯一の違いは , ||w|| のノルム
毎日新聞の社説からランダムに選んだ 60 記事に ,である (Boosting は l1 , 式 (7), SVMs は l2 , 式 (10)).
文単位のモダ リティ付与したデータである. 分
文献 [11] では , このノルムの違いを , モデルのスパー
類単位は「文」, 文数は 1,710, カテゴ リは , 「意ス性という観点で議論している. 詳細は [11] に譲る
見」「断定」「叙述」の 3 つである.
が , SVM は , 事例スパースの解を導出することが知3 つのタスクのデータの一例を図 6 に示す.
られている. つまり, できるだけ少数の事例で w を文の表現方法として , 以下の 3 つを用いた表現しようとする. SVM の分離平面 (w) は , 学習事
PL• Bag-of-Word (bow), ベースライン
例の線形結合で与えられる (w = i=1 λi Φ(xi )). 非構造は考慮せず , 単語の有無を素性とする. 英語
0 の係数が付いた事例が , サポート ベクター (分離平はCharniak Parser[3] を , 日本語は ChaSen2を面を支える事例) と呼ばれるのは上記の理由からで用いて単語を切り出す. 日本語のみ, 単語の表層ある. 一方, Boosting は , 素性スパースの解を導出す
ではなく, 原形を用いた. Boosting を用いた提る. つまり, できるだけ少数の素性で w を表現しよ
案手法では, サイズ 1 の構造のみが素性集合と
うとする.
なる
.
SVM と Boosting を精度という観点で比較することは , タスク依存性が強いため , ここでは行わない.
• 係り受け (dep)
しかし , Boosting を用いる提案手法は以下のような単語単位の係り受け構造として文を表現する. 英「現実的な」利点があると考える.
語は , Charniak Parser と文献 [4] の主辞規則を用い単語単位の係り受けに変換する. 日本語は ,• 解釈のしやすさ
CaboCha3を使い, 文節単位の係り受け構造を導できるだけ少数の素性で分類し , その分類自身が出した後, 単語 (原形) 単位の係り受け構造に変陽に実行されるため, どのような素性が分類に使換する. 基本的に , 文節中の単語は , 直後の単語用されているか , 分類に寄与する素性は何か , とに係け, 文節中の最後の単語は , 係り先文節の主いった分析が行いやすい. SVM では , 素性空間
辞となる単語に係ける. ただし , 文頭, 文末にはが陰に表現されるため, そのような分析を与えにダミーのノード を置く.
くい.
• N-グラム (ngram)
各単語 (原形) の係り先が , 直後の単語であるとみなした係り受け木である. 任意の部分木は , 単語 N-グラムになる.
これらのデータ, 文の表現方法を用い, 提案手法
(Boosting) と , Tree Kernel による SVM の比較実験を行った. Tree Kernel には , 文献 [9] で提案されている部分木のサイズに対する事前分布や , 親子間の伸縮等は考慮せず , 全部分木に展開するオリジナルの Tree
Kernel を用いた. これは , 学習に使われる素性を同一にし , 比較を公平にするためである. SVM のソフ
5 実験と考察
トマージンパラメータ, 及び Boosting の繰り返し回
数は , それぞれ適当に変化させながら , 最良の結果を
5.1 実験環境, 設定採用した. 複数クラスの分類には , 2 値分類器を多値実験は , 以下の 3 種類のタスクで行った.
分類問題へ拡張する手法の 1 つである one-vs-rest を• MEDLINE 文の役割分類 (MEDLINE)用いた. 評価は , 5-fold 交差検定により得られた F 値
MEDLINE には , 構造化アブ ストラクトと呼ば の平均にて行う.
れる, 各段落の先頭にその段落の役割 (背景, 目
的など ) が明記されたものが含まれる. これらの 5.2 実験結果
データを用い, 与えられた文がどの役割の段落に
表 1,2,3 に , MEDLINE,PHS,MOD の実験結果を含まれているかを同定するタスクを考える (詳細は , 文献 [15] を参照). 分類単位は「文」, 文数は 示す. B は , 提案手法 (Boosting) は , S は , SVM を用
2 万, カテゴ リは「背景」
「目的」
「手法」
「結果」 いた結果である.
「結論」の 5 つである.
2• 高速な分類
スパースな素性空間は , 高速な分類を可能にす
る. Tree Kernel の計算量は , O(|N1 ||N2 |) である (ただし N1 と N2 は内積をとる 2 つの木である). さらに Kernel 法に基づく分類アルゴ リ
ズムはサポートベクターの数 L0 に依存する. つまり, SVM の分類コストは , O(L0 |N1 ||N2 |) となり非常に大きい. この問題は , 実際の応用において障壁になっている.

• PHS レビュー分類 (PHS)

http://chasen.org/

3 http://cl.aist-nara.ac.jp/˜ taku-ku/software/cabocha//MY¶'·  Y¡¡  ¢£ YU¤ ¥§¦¡¨ ¤ ¢©¤ ~ª«¨¬ ¤ ¨­¢¡¨ ¤ ®§ ¤ ®¯£°¦>°®±² ³ ¡´  ¤ ®£¥¡U³ ¯±ª©¨ ¦²µ µ µ»5¼ /¸Y½¾ª° ¤ ¿ ®  ¤³ ¦¡§¤ ¾À £¥§¨§´ ¢£¥§ ª> ¤ ª«¡~³ ª¡¦¹ºÁ g¥°¢¬ °¤  gU ª«~ ¤ª««§¬¢>¢¡¹ ¨ ³ª«¤ ®¯5¨ ±¦±ª¡§¹© ¨ «´°¡ ¤ ¨º¡¤ °µÂ3Ã /
Â%Í ¸~ÄU§®¡g¤ °¢UÀF° ±Å«Æ§Ç¡´ Uª«¡ ¨ Y  ~§ªUº¹­¥Èª«É¡ ¸Ê ¯£¦U¤ ³ª©¢¡¥§¢>¡g° ª³ ³ ¨ ª¡ªU¹­¡Ë¡Ì>Ë¡Ç£¨ § ¡¨ § °¯£ ¯±§Y¨  °¢«µ ´§¾ «¨ ¤ Î¹ ª«¨­¡«¤ ª¡©¨ ¥¡U¤ ´ ³ ¦ µ !#"%$'&#(*)+-,/.!01 /32546
7 8 9:;8<>=@?%ABC?3 7  DFE'G3HI34/J
R/S >TUA VWB5XY)!Z#[ 2 )/\]#*^/_/G `92%ab#c58 Jde!gf )/hi!jlkM[m/G%no#p/*"4 q#2/b83)rJ
s#tlu!v*!wx#23y/z{l|w&l~}#!!1l<~!#+F#'J
…

KMLFN
OP>Q

…

図 6: データの例

B/bow
B/dep
B/ngram
S/bow
S/dep
S/ngram5.3

表 1: 結果 (MEDLINE)
背景 目的 方法 結果
53.7 58.2 80.9 78.0
55.1 60.2 82.2 80.4
56.1 66.1 82.5 79.7
53.3 59.4 81.8 79.1
26.7 8.6
71.0 70.0
41.5 65.7 79.8 76.4

結論
58.6
60.5
61.4
57.8
22.3
43.8

表 2: 結果 (PHS)
F値
B/bow
76.6
B/dep
79.0
79.3
B/ngram
S/bow
77.2
S/dep
77.2
S/ngram
79.4

考察

5.3.1 構造を考慮する有効性
全タスクにおいて , 構造を用いないベースライン(bow) に比べ, 構造を考慮する提案手法が顕著に精度が高いことが確認できる. 係り受け (dep) と N-グラム (ngram) を比較すると , タスク依存性が強く, 顕著な差は確認できない.
5.3.2 提案手法 vs SVM + Tree Kernel
bow を素性とした場合, Boosting と SVM には顕著な差は確認されない. しかし , SVM を用いた場合,
タスクによっては著し く精度が悪い. これらの「 顕著な」精度低下の要因として , Tree Kernel をはじめとする Convolution Kernel 全体が持つ欠点が挙げられる. 言語データといった疎データに Convolution
Kernel を用いると , 素性数が指数的に増えるため, 自分以外との内積と比較して , 自分自身との内積が極めて大きくなる傾向にある. これにより, 学習事例に酷似した事例のみを分類し , 残りはデフォルトクラスに分類するような , 丸暗記学習が行われやすくなる. これを回避する方法として , 1) 大きな部分構造の重みを減衰させる [9], 2) 正規分布の分散と同形の平滑化を与える [7], 3) カイ 2 乗値により素性選択する [13],といった手法が提案されている. これらの手法を用いることで , 精度という意味では , 提案手法を上まわる可能性はある. しかし , 使用される素性そのものが大きく変わり, 減衰率といったハイパーパラメータの設定方法についての議論の余値が残るため , 公平な比
較ができない.

表 3: 結果 (MOD)
断定 意見 叙述
B/bow
71.2 62.1 83.0
B/dep
87.5 80.5 91.9
87.6 78.4 91.9
B/ngramS/bow
72.1 59.2 82.5
S/dep
81.7 26.1 88.1
S/ngram
81.7 26.1 88.1

よる分析に耐えうるサイズであった. 学習データから抽出した全 1-gram, 2-gram, 3-gram の異なり数がそれぞれ 4,211, 24,206, 43,658 であることから , い
かに少数の素性で分類を行ってるかが分かる. もし ,SVM のサポートベクターの集合から , サポート素性を列挙すると , 数十万から数百万の素性数になると予想される.
サポート素性の分析の例として , 図 7 に , 個々のサポート素性 t ∈ G と , Boosting が算出した素性重みλt の一部を示す.
(A)「 (〜し ) にくい」を含む素性「 (〜し ) にくい」は , 一般に否定的な意味の形容詞であり, 大くの素性は負 (悪い点) の重みが与えらえている. しかし , 「切れにくい」のみ正の重みとなり,
ド メイン知識 (PHS) をよく反映している.
(B)「使う」を含む素性「使う」は , 評判には中立な意味の単語だが , 周辺のコンテキストで重みが変化している (「使いたい」→
正, 「使いやすい」→正). さらに , 過去形 (「使いやすかった」) になったり, 他の要素との比較 (「 (〜の/〜する) 方が使いやすい」) になると , 負の重みが与えられており, 興味深い.
(C)「充電」を含む素性ド メイン知識を反映した素性 (「充電時間が短い」→
正, 「充電時間が長い」→負) が抽出されている. また, これらは , 係り受け構造を考慮した素性である4 .
さらに , 図 8 に , 分類の実行例を示す. 入力文「液晶が大きくて , 綺麗, 見やすい」に対し , ど ういう素性が適用されたか陽に出力し , 分析を容易にしている.
このような分析は , Tree Kernel では困難である.

5.3.3 提案手法の利点
最後に , 分類速度であるが , 提案手法の分類速度が4 章にて, 提案手法の「現実的な」利点について述 0.135 秒/1,149 事例に対し , SVM は , 57.91 秒/1,149
べた. ここでは , 実験結果 (PHS) から , それらの利点 事例 であった. 提案手法が , およそ 400 倍高速であを検証する.
ることが確認された.
提案手法は , 必要最小限の素性を自動的に選択する
4「充電時間がとても短い」は , 係り受けパターンならマッチで能力を備える. PHS タスクにおいて , 実際に使われた素性 (サポート素性) の数は , 1,793 であり, 人手に きるが , ngram だとできない.

9 ;:<>=@?BA.DCFE   !#" $$%'&)( $%**'+" *,*)-/.0 1%23'& *54/67 8
c__:edFf/=<?BA.DCFE2'dFfhgFijZjkl
 %mndFfhg/i\Z[o^ _:`4/6a=@?bA/.;C E
1 4/6G(>H$ 4/6
81 4/6JIK 4/6MLDN/ OP4/6JL;N/'( %*P4/6Q %2R$3S'4/6UT/VW <22YX[Z\4/6JLDN/ %11)?54/6GIK](

参考文献[1] Kenji Abe, Shinji Kawasoe, Tatsuya Asai, Hiroki
Arimura, and Setsuo Arikawa. Optimized substructure discovery for semi-structured data. In Proc.
6th European Conference on PKDD, 2002.

PHS
r {%}~sutaswp>vyqD
x!z|( aW

xaWz|(dep){%}u~xww

)

図 7: サポート素性の一部   



[2] Leo Breiman. Prediction games and arching algoritms. Neural Computation, 11(7):1493 – 1518,
1999.
[3] Eugene Charniak. A maximum-entropy-inspiredparser. In In Proc. of NAACL, pages 132–139,
2000.
[4] Michael Collins. Head-Driven Statistical Models for
Natural Language Parsing. PhD thesis, Universityof Pennsylvania, 1999.
[5] Michael Collins and Nigel Duffy. Convolution kernels for natural language. In Proc. of Neural Information Processing Systems (NIPS), 2001.
[6] Yoav Freund and Robert E. Schapire. A decisiontheoretic generalization of on-line learning and an
application to boosting. Journal of Computer and
System Sicences, 55(1):119–139, 1996.
[7] David Haussler. Convolution kernels on discrete
structures. Technical report, UC Santa Cruz (UCSCRL-99-10), 1999.

[8] Roberto J. Bayardo Jr. Efficiently mining long patterns from databases. In SIGMOD 1998, Proceed図 8: 分類の実行例
ings ACM SIGMOD International Conference on(注: 前順序の S 式で木を表現しているため, 語順が逆になる)
Management of Data. ACM Press, 1998.
[9] Hisashi Kashima and Teruo Koyanagi. Svm kerおわりにnels for semi-structured data. In Proceedings of the
ICML-2002, pages 291–298, 2002.
本稿では , テキストの構造 (構文構造やレ イアウト構造) を考慮したテキスト分類 (半構造化テキスト分 [10] Shinichi Morhishita. Computing optimal hypotheses efficiently for boosting. In Progress in Discovery類) に向け , 部分木を素性とする Decision Stumps と ,Science, pages 471–481. Springer, 2002.

6

それらを弱学習器として用いる Boosting アルゴ リズ
ムを提案した. さらに , 部分木列挙アルゴ リズムを拡張し , 弱学習器の効率良い学習/分類手法を提案した.
実データを用いた実験にて , 文の構造を考慮する本手法の有効性を示した. さらに , 提案手法の 2 つの利点
(解釈のしやすさ, 高速分類) を実タスクにおいて確認
した.
今後の計画として , 以下が挙げられる.
• 他のタスク
本手法は , 言語処理全般に適用できる汎用的な手法である. 今後はテキスト分類だけではなく, 係
り受け解析, 構文解析といった言語解析タスクでの有効性を検証したいと考える.

[11] Gunnar. Rätsch. Robust Boosting via Convex Optimization. PhD thesis, Department of Computer
Science, University of Potsdam, 2001.
[12] Robert E. Schapire, Yoav Freund, Peter Bartlett,and Wee Sun Lee. Boosting the margin: a new
explanation for the effectiveness of voting methods.
In Proc. 14th International Conference on Machine
Learning, pages 322–330. Morgan Kaufmann, 1997.
[13] Jun Suzuki, Tsutomu Hirao, Hideki Isozaki, andEisaku Maeda. String kernel with feature selection
function (in Japanese). In IPSJ SIG Technical Reports 2003-FI-72/2003-NL-157, 2003.

[14] Vladimir N. Vapnik. The Nature of Statistical
Learning Theory. Springer, 1995.
[15] Takahiro Yamasaki, Masashi Shimbo, and Yuji
• グラフ構造
Matsumoto. Automatic classification of sentencesusing sequential patterns (in Japanese). In Techniこれまでは , 木構造のみに着目していたが , より
cal Report of IECE AI2002-83, 2003.
複雑な情報を表現するには , グラフを用いるほうがよい. 効率良いグラフ列挙アルゴ リズムが提 [16] Xifeng Yan and Jiawei Han. gspan: Graph-based
substructure pattern mining. In Proc. of ICDM,
案されているので [16], 今後は , それらを適用しpages 721–724, 2002.
たいと考える.

謝辞[17] Mohammed Zaki. Efficiently mining frequent trees
in a forest. In Proceedings of the 8th International Conference on Knowledge Discovery andData Mining KDD, pages 71–80, 2002.

MEDLINE のタスク設定について, 奈良先端大学の山崎[18] 和田啓二 田村直良. セグ メントの分割と統合による
貴宏氏に助言をいただきました. また, 文のモダ リティ判
文章の構造解析. 自然言語処理, 5(1), 1996.
別データを NTT コミュニケーション科学基礎研究所の平尾努氏に提供していただきました. ここに感謝いたします.