系列パターンマイニングを用いた有効な素性の組み合わせの発見
工藤 拓

松本 裕治

奈良先端科学技術大学院大学 情報科学研究科〒 630-0101 奈良県生駒市高山町 8916-5{taku-ku,matsu}@is.aist-nara.ac.jp

近年, Support Vector Machine を中心とする Kernel 法が注目され , 自然言語処理においても良い結果を示している. Kernel 法により, これまで巧妙に選択する必要があった「組み合わせ素性」を一般性や計算量を落とすことなく取り入れることができる. しかし , Kernel を用いた場合には , 素性の組み合わせは陰に展開されるため, 有効な素性の分析が難しく, さらに , 解析時の計算量が大きくなる問題がある. 本稿では , マイ
ニングアルゴ リズムの 1 つである PrefixSpan を用い, サポートベクターの集合から有効な素性の組み合わせを発見し , 解析の速度向上を試みる. 日本語係り受け解析における実験では , Kernel を用いた通常の解析器に比べ, 約 30 倍の速度向上に繋がった.
キ ー ワ ード :Support Vector Machine, Kernel 法, Data Mining, PrefixSpan, 係 り 受け 解 析Mining Effective Feature Combinations from Support Vectors
Taku Kudo

Yuji Matsumoto

Graduate School of Information Science,Nara Institute of Science and Technology
8916-5 Takayama, Ikoma Nara 630-0101 Japan{taku-ku,matsu}@is.aist-nara.ac.jp

The kernel method (e.g. Support Vector Machines) has gained the focus of attention recently. In the fieldof Natural Language Processing, many successes have been reported. The merit of the kernel method isthat the effective feature combinations, which have been manually selected in the previous approaches,
are implicitly expanded without loss of generality and computational cost. However, the kernel-basedclassifier is usually too slow to apply to large-scale text analysis. In this paper, we extend the PrefixSpan
algorithm, one of efficient algorithms for sequential pattern mining, to explicitly extract effective feature
combinations from a set of support vectors and make a classification speed faster. Experimental results on
Japanese dependency analysis show that our new classifier(parser) is about 30 times faster than standard
kernel-based classifier(parser).
Keywords : Support Vector Machines, Kernel Method, Data Mining, PrefixSpan, Dependency Analyisis

1

はじめに

近年, 学習理論に基く自然言語処理が急激に進展しており, 多くの研究者から注目されている. 得に ,Support Vector Machine[12] は , テキストチャンキン
グ [8], 固有名詞抽出 [13, 4], 構文解析等 [14] の自然
言語処理タスクに応用され , いずれにおいても高い精度を示している. 今後もそのタスクの裾野を広げて行くであろう.
パターン認識における従来の方法論は , 与えられた学習データを分類に寄与するであろうできるだけ小さな素性集合で表現し 1 , その後に , 分類誤差が小さくなるような識別関数を構成するものであった . 前
処理の素性選択こそが , 汎化誤差を小さくする鍵となる. いっぽ う, SVM では , Kernel 関数を使い, 超高次元空間上にデータを写像し , そこでの線型分離を考える. このとき, データを表現する素性空間は非常に大きいのにもかかわらず , 分離平面はマージン最大化
により決定されるため, 結果的に汎化誤差を小さくすることができる.
この方法論の違いは , 非常に大きい. 従来の機械学習を用いた自然言語処理の多くは , 前者の方法論であったため, 素性集合の設計がひとつの腕の見せどころであった. もちろん , 基本素性としてどのような素性集合を仮定すればよいかが問題となるが , 多くの自然言語処理タスクでは , 1 つの素性のみで決定できる
ことが少ないため2 , それらの基本素性の任意の個数の組み合わせも同時に考慮しなければならない. 結果として , 候補となる素性集合が膨大になり, この中から有効な素性を選択する必要があった .
SVM では , 巧妙な素性選択をせずとも, 従来手法
で巧妙に選択した場合と比較して , 少なくとも同等
か場合によってはそれ以上の認識率が得られることが実験的に知られている. また, 素性の組み合わせに関しても, Polynomial Kernel を用いることで , 計算量や一般性を落とすことなく考慮することが可能である.
しかし , SVM に問題点が無いわけではない. まず ,Kernel 関数は , 陰に素性の組み合わせを展開するために , どのような素性の組み合わせが (一般には事例の部分構造が ) 分類に寄与しているのかが分からな
い. 分類に有効な素性は , 我々が知らない一種の知識と考えられるため, 有効な素性そのものを分析対象したいことがある. もう一つの問題とは分類速度である. Kernel 関数を用いた場合の分類速度は , サポー
トベクターの数 (時として数万になる) に依存するため, テキストマイニングといった大規模テキストデー
タの解析が必要な場合, 適用が難しい.

本稿では , この 2 つの問題を解決すべく, データマ
イニングの手法を使い, 学習後のサポートベクターの集合から , 分類に寄与する有効な素性の組み合わせ(一般には事例の中の部分構造) を抽出, 提示する手法を提案する. また, この結果を用い, 分類の高速化を試みる. 日本語係り受けにおける実験では , Kernelを用いた従来の分類器に比べ, 30 倍の速度向上に成功した.

2

Kernel Method

2.1

Support Vector Machines

正例, 負例 の二つのクラスに属す学習データのベ
クトル集合を ,(x1 , y1 ), . . . , (xL , yL )xi ∈ RN , yi ∈ {+1, −1}とする. SVM では , 二値分類を仮定しているために ,yi は , クラスに応じて +1 もし くは , -1 をとるものとする. この時, SVM の分離関数は , 次式で与えられる.

y = sgnL³X´
yi αi φ(xi ) · φ(x) + b

(1)

i=1

ただし ,

(1) φ は , RN から RH (一般に N ¿ H) への写像
関数であり,(2) αi , b ∈ R, 0 ≤ αi ≤ C である.

式 (1) は , テストデータを高次元空間に写像したデータ φ(x) と l 個の学習データを写像したデータ φ(xi )との内積を全事例についてそれぞれ計算し , 重み yi αi
線形結合した形となっている.
ここで , 高次元空間への写像関数 φ は , すべての事
例が , RH における超平面で分離できるようにユーザが設計する. 通常, H は , N よりもはるかに高い次元になるために計算量が大きくなる問題がある. この問題を解決する手段として Kernel 関数がある.
式 (1) より, 実際に SVM を構成する場合には , 写像関数は , φ(xi ) · φ(x) という内積の形で出現する.
本稿では , αi , の最適化手法について言及しないが ,SVM における学習の式も, 写像関数の内積のみで表現できる. したがって, 高次元空間 RH 上での内積
φ(x) · φ(x0 ) が効率良く計算できれば , RH が高次元空間であることの計算量的問題は解決できる. このように , 写像された高次元空間上での内積を表現する
1 人手で巧妙に素性集合を表現したり, PCA 等の次元圧縮手法
ための関数 K(x1 , x2 ) = φ(x1 ) · φ(x2 ) を Kernel 関を用いて素性集合を選択する
2 係り受けタスクは , 係り元の係り先の基本素性 (単語, 品詞, 活 数と呼ぶ . Kernel 関数を用いると , 式 (1) は以下のよ
用など ) の組み合わせが必要である.
うに書き直すことができる.

3
y = sgnL³X´
yi αi K(xi , x) + b(2)

マイニングアルゴリズムによる有効な部分構造の発見

i=1

本稿では , SVM によって求められたサポートベク
ターの集合から, 分類に寄与する部分構造を発見する
式 (2) より, SVM の学習, 分類には , 陽に表現された素性の集合は必ずしも必要ではなく, 事例間の類似 ことを試みる.
度 (内積) を与える Kernel 関数のみ定義できればよいことが分かる3 . この「分類したいデータ構造に関する情報を Kernel 関数と形で学習アルゴ リズムとは
3.1 基本的なアイデア
独立に設計できる」という性質こそが , SVM を中心とする Kernel 法が急激に脚光を浴びることとなった
式 (1) を以下のように書きかえる.
1 つの要因と考えられる.
実際に , 近年, 素性の集合として表現するのが困L³X´
難である離散データの分類のための Kernel 関数のy = sgnyi αi φ(xi ) · φ(x) + b
提案が活発である. 文字列間の内積を与える Stringi=1³´
Kernel[10], 順序木の内積を与える Tree Kernel[5, 3],= sgn w · φ(x) + b(3)
さらに , 無向グラフのノード 間の内積を与える DefL
fusion Kernel [6] などが提案されている.
X
ただし w =
yi αi φ(xi )
i=1

2.2

Kernel 法の問題点

Kernel 法は , 非常にエレガントではあるが , 実際の応用においては , 以下の 2 つの問題があると我々は考えている.
• 有効な素性の分析が困難
Kernel 法では , 素性空間が陰に表現されてしまうため, いったいどのような素性 (部分構造) が分類に寄与したのか , 分析が困難である.
• 分類時の計算量
式 (2) から分かるように , Kernel を用いた場合の分類の計算量は , サポートベクターの数に比例する. サポートベクターの数は , 数万を超える事もあるために , 分類にかかる計算コストが非常に大きく, 実際の応用に耐えられない場合が多い.
この 2 つは , 自然言語処理において特に深刻な問題点である. かつて , 自然言語処理において決定木が爆発的に使用された理由として , ルールが木という形で表現され , その結果を内省と照らし合わせるといった分析が可能であったことがある. このような分析は ,自然言語処理ではご く一般的に行われている. SVM
においては , 分類に有効な事例がサポートベクターという形で表現されるが , その事例のどの部分が有効に機能しているのかは与えてくれない.
また, 近年大量のテキストデータから知識を発掘するといった, Text Mining の研究が活発になっている.
これらのタスクにおいては , 大規模なテキストデータを高速に解析する必要があり, 通常の SVM を用いた分類器では遅くて実用に耐えない.

w は , φ(x) と同じ H 次元のベクトルであり, その
要素は , 写像後の各素性が分類にどれだけ寄与するかを表現する. もし , w が計算できると , 前節で取りあげた問題点は解決できると考える. 以下にその理由を述べる.
• 有効な素性の分析
w の各要素について絶対値の大きい軸は , 分類に寄与する軸だと考えられる. すなわち, 事例 xの中で分類に寄与する部分構造を目に見える形で提示することが可能である.
• 分類時の計算量
分類は , 式 (3) で実行される. 式 (3) は , サポー
トベクターの数に依存せず , 写像空間中での単純な内積を計算すればよいので , 一般に高速になる. しかし , 写像そのものにコストが必要な場合
はその限りではない.
ここでの問題は , いかにして w を求めるかにある.
事例が少なく, 写像した空間も計算機で扱える程度の次元の場合は , 式 (3) を直接計算可能である. これは ,磯崎らが 2 次の polynomial kernel に限り, 素性中のすべての 2 つまでの組み合わせを全展開した手法と本質的に同一である [4].

しかし , 3 次や 4 次の polyinomial Kernel, String
Kernel, Tree Kernel といった Kernel に対し , 素性の組み合わせや事例中の部分構造を全て展開することは , 部分構造の数が , 指数的に増えるために非常に困難である. さらに , RBF Kernel といった関数は , 写
3 実際には Kernel として満たすべき制約 (Mercer’s condition) 像後の空間がヒルベルト空間 (H = ∞) になるため ,が存在する
そもそも全展開ができない.

3.2

写像空間上での近似解 w0w の近似解 w0 を次のように定義する.
定義 1 (w の近似解 w0 ) w ∈ RH の各要素 wj (j =1, . . . , H) について, σneg < wj < σpos (σneg <0, σpos > 0, σneg ) となる場合は , wj = 0 に近似
する. このようにして作成されたベクトルを w の近似解 w0 と定義する.

(1) サ ポ ー ト ベ ク タ ー の 集 合(y1 α1 , x1 ), . . . , (yL αL , xL ), を , 正 例 の 集 合Γpos = {(yi αi , xi )|yi = +1} と負例の集合
Γneg = {(yi αi , xi )|yi = −1} に分割する.
(2) yi αi を事例 xi の頻度とみなす(3) 正例の集合 Γpos に対し , 頻度 σpos 以上の部分構
造と頻度のタプルの集合をマイニングアルゴ リ
ズムを使って抽出する. 抽出された部分構造と頻度の集合を Ωpos = {hpj , ηj i} とする.

w0 は , 0 付近の微少な範囲 (σneg , σpos ) 内にある重みをもつ部分構造は分類に寄与しないという仮定の (4) 負例の集合 Γneg に対し , 頻度 (最小サポート )σneg 以下の部分構造と頻度のタプルの集合をマ基での近似解である. また, たとえ w がヒルベルト
0
4
イニングアルゴリズムを使って抽出する. 抽出さ空間になっても, w の非 0 の要素は有限となる .
0
れた部分構造と頻度の集合をΩneg = {hpj , µj i}
w の導出の最も単純な方法として , 部分構造を全0とする.
展開し , 定義どおりに直接 w を作成することである.
しかし , この手法は全展開を必要とするため , 前節で (5) 正例負例の各部分構造 pj について, wj = ηj +µj ≥ σpos または , wi = ηj + µj ≤ σneg となる述べた計算量的問題点の解決にはならないことに注ような部分構造
pi を抽出し , それらを結果集合意されたい. ここで , σneg < wj < σpos となる場合Ω = {hpj , wj i} とする.
は , その素性 (部分構造) の軸が無いものとみなせる
ことに注意すると , w0 の導出は , 次に述べるマイニン
σpos および σneg は , どれくらいの近似精度を要求
グタスクと本質的に同一である.
するかを決定する変数である. 一般に , 正例と負例の事例数には , 偏り (bias) がある. その偏りを考慮し ,ユーザは閾値 σ(> 0) のみを与え , それを以下のように正例と負例の数で線型分配して σpos , σneg を決定
3.3 有効部分構造のマイニング
する.
定義 2 (有効部分構造のマイニング ) サポ ート ベ ク³ サポートベクターの正例数 ´
ターの集合 (y1 α1 , x1 ), . . . , (yL αL , xL ), 写像関数 φσpos = σ ·全サポートベクター数が与えられた時に , wj ≥ σpos または wj ≤ σneg と³ サポートベクターの負例数 ´
なるような , 部分構造 pj と , その重み wj を網羅的
σneg = −σ ·全サポートベクター数に求めるタスクを有効部分構造のマイニングと定義する.
この問題に対し , 本稿では , データマイニングアル
ゴ リズムを適用する. データマイニングアルゴ リズ 4
具体例: 部分集合 Kernel
ムとは , 任意の構造 (集合, 系列, 順序木, グラフなど )前節で , Support Vector からの部分構造マイニンの集合から , 頻出する部分構造 (部分集合, 部分系列,
部分木, 部分グラフ) を高速に , 効率良く発見, 抽出す グの一般的な手法について述べた. 本節では , 部分集
るアルゴ リズムの総称である. これらのアルゴ リズ 合 Kernel という種類の Kernel を取り挙げ , その具体的な適用方法について述べる.
ムの特徴として以下が挙げられる.
• 部分構造を全展開できないような大規模なデー
タを想定しいる.

• 種となる小さな部分構造から始め, 深さ優先, もしくは幅優先で部分構造を広げていきながら , 頻
出する部分構造のみを抽出する.
Kernel 関数が持つ射影関数 φ が , どのような部分構
造の空間にデータを射影するかによって , 選択する
データマイニングアルゴ リズムが決定される.
以下に , 有効部分構造マイニングの具体的な適用方法の手順を示す. 通常のマイニング手法と異なる点
は , 正例, 負例, 個別に頻出パターンをマイニングし ,最後にその結果をマージする点にある.
4 もし , w < σ
neg または wj > σpos となる軸が無限個あるj場合, 自分自身との内積が発散してしまい, 内積が定義できない.

4.1

バイナリ素性

自然言語処理タスクにおける事例は , その事例にマッチする任意の条件の集合という形で表現されることが多い. これは , 言語データそのものが離散デー
タあることに起因する. このような離散データは , 素
性空間を以下のようなバイナリで表現することと等価である.

(x1 , y1 ), . . . , (xL , yL )xi ∈ {0, 1}N , yi ∈ {+1, −1}

本稿では , 応用として自然言語処理を念頭に置いているため, 上記のようなバイナリ素性で表現されるデー
タのみを考える.

4.2√√
分集合重みは c0 = 1, c1 = 3, c2 = 2 となることが分かる. 以上の議論を , 一般の d 次の polyinomial
kernel に拡張する.

部分集合 Kernel

バイナリ素性として表現される事例 x ∈ {0, 1}Nを , 事例 x の k 個 (k = {0, 1, . . . , N }) のすべての「 部分集合」の「 集合」(k 個までのすべての素性のK(x1 , x2 ) = φ(x1 ) · φ(x2 ) = (1 + x1 · x2 )d(5)
組み合わせの「集合」) の空間に射影するような 射NN
影関数 φ を持つ Kernel を部分集合 Kernel と呼ぶ x1 ∈ {0, 1} , x2 ∈ {0, 1} に対し , d 次の polynoこととする. ただし , r 個 で構成される部分集合に mial Kernel は二項定理より以下のように展開できる.
は , 部分集合重み cr ∈ R が付加される. 部分集合重K(x1 , x2 ) = (1 + x1 · x2 )d
み cr は , r 個で構成される部分集合をどれだけ重要d
X
視するかを与える事前分布となる. 個々の部分集合l=d Cl (x1 · x2 )Kernel は , 固有の部分集合重み分布を持ち, その分布l=0が Kernel としての性質を与える.
(x1 · x2 )l において, r 個で構成される部分構造の個数を τ (l, r) と表現すると 5q, d 次の polynomial Kernel
φ(x) = (
c0
,
Pd
|{z}
は , 部分構造重み cr =l=r d Cl · τ (l, r) を持つ
0 個の部分集合 (組み合わせ)(ただし r = {0, 1, . . . , d}).
kernelc1 x1 , c1 x2 , . . . , c1 xN ,√ 3 次の polynomial
√
√
{z
}
|
の場合は
,
c
=
1,
c
=
7,
c
=
12,
c
=
6と
0
1
2
3
1 個の部分集合 (組み合わせ)なる.
c2 x1 x2 , . . . , c2 x1 xN , . . . , c2 xN −1 xN ,
|
{z
}
...,

2 個の部分集合 (組み合わせ)4.2.2

ck x1 x2 ..xk , . . . , ck xN −k xN −k+1 ..xN )

|

{z

}

ただし , x = {x1 , x2 , . . . , xN },K(x1 , x2 )xj ∈ {0, 1}, ck ∈ R, k = {0, 1, . . . , N }この部分集合 Kernel に族す Kernel として , 本稿では , 頻繁に使用される Polynomial Kernel と RBF
Kernel を取り挙げる.

4.2.1

R2 から R6 への写像関数 φ を√√√
φ((x1 , x2 )) = (1, 2x1 , 2x2 , x21 , x22 , 2x1 x2 )とする. この時, 高次元空間上での内積はφ(x1 ) · φ(x2 ) = (1 + x1 · x2 )=exp(−s||x1 − x2 ||2 )=exp(−s||x1 ||2 ) exp(−s||x2 ||2 ) exp(2s(x1 · x2 ))=exp(−s||x1 ||2 ) exp(−s||x2 ||2 ) ·∞³X´(2s)l (x · x )l
1

l=0

2

l!

(x1 · x2 )l において, r 個で構成される部分構造の個数を τ (l, r) と表現すると
RBF Kernel は , 部分構造
q, P
∞ (2s)l τ (l,r)
2
重み cr = exp(−s||x|| )を持つ (たl=r
l!
だし r = {0, 1, . . . , n}).

Polynomial Kernel

2

RBF Kernel

x1 ∈ {0, 1}N , x2 ∈ {0, 1}N に対し , RBF Kernel(分散パラメータ s ∈ R, s > 0) は , 以下のように漸近展開できる.

k 個の部分集合 (組み合わせ)

4.3
(4)

となる. つまり R6 での内積 (左辺) が R2 の空間の内積 (右辺) のみで計算できることを意味する. バイ
ナリ素性の場合は , x21 = x1 , x22 = x2 となることに注意すると射影関数は√√√φ((x1 , x2 )) = (1, 3x1 , 3x2 , 2x1 x2 )ただし x1 , x2 ∈ {0, 1}√となる. φ で表現される 4 番目の軸 2x1 x2 は , 素
性 x1 , x2 の組み合わせを表現している. 以上より,
式 (4) で表現される 2 次の polynomial kernel の部

PrefixSpan

部分集合 Kernel に対するマイニングアルゴリズム
は , 素性集合から頻出する部分集合を枚挙するような
アルゴ リズムとなる. 代表的なアルゴ リズムとして ,Apriori[1] があるが , 実行速度や実装の手軽さを考えて, 本稿では PrefixSpan[11] を用いる. PrefixSpan
は , もともと系列データのためのマイニングアルゴ
リズムであるが , 集合に対し , 個々の要素を辞書順にソートしたものを系列とみなせば , 集合のマイニングも可能となる.
PrefixSpan は , 系列の集合 (系列データベース) から , ユーザが与えた最小サポート値, ξ 回以上の系列
5 τ (l, r) の具体的な値は , 付録 A を参照のこと

minsup = 2
project

sid sequence
1
2
3
4

acd
abc
cba
aab

a:4
b:2
c:2
d:1

1
2
4

c d
b c
a b

projected
database

2

c c:1

1

d d:1

よって射影をコントロールする. 一方, 実際の部
分系列の頻度計算には , 重み cr を用いる.

4.4
2
3

c
a

a:1
c:1

1
3

d
b a

a:1
b:1
d:1

sequence databasecount sup. of 1 item

a:1
b:2
c:2

a:4
b:2
c:2
a b:2
a c:2
results

図 1: PrefixSpan の動作過程に含まれるすべての部分系列を列挙するアルゴ リズ
ムである. このアルゴ リズムは , 分割統治法に基づき,パターンを深さ優先で広げていきながらマイニングを行う. 具体的には , まず , 1 つの要素のみで構成される系列のうち, 最小サポート値以上の部分系列を列挙
する. 次に , 頻出パターンが出現する系列の postfix
を集め, それをあらたな部分系列集合とする. この部
分系列集合を , 改めて系列データベースとみなし , 同
じ処理を再帰的に繰り返す.
図 1 に , ξ = 2 とした場合の PrefixSpan の動作過程を示す. まず , サイズ 1 の多頻度系列 a, b, c を抽出する. d は , サポートが 1 であるため, 多頻度系列ではない. 多頻度系列は , これら 3 種類あるが , そのう
ち a について考え , S の a による 射影データベース
S|a を作成する (図 1 中央上). この データベースから , 多頻度系列 b, c を生成する. 以下再帰的にこれらの作業を繰り返すことで , すべての多頻度系列を抽出することができる.
以上が , オリジナルの PrefixSpan であるが , 部分
集合 Kernel におけるマイニング問題に適用する場合
は , 以下の 3 点を変更する必要がある.
• 頻度 yi αi
系列データベースの各系列が , サポートベクター
xi に対応する. サポートベクター xi は , それに対応する重み yi αi を持つ. PrefixSpan を動作させる時には , yi αi をその系列の頻度とみなす.

TRIE による部分集合の格納

マイニング後, 部分集合 pi と , それに付与される
重み wj のタプルの集合 Ω = {hpj , wj i} が抽出される. 部分集合 pj のそれぞれは , 多くの共通した部分構造を持つため, それを単純な Hash 等を使って格納するのは記憶効率が悪い.
その問題を解決するために , 共通部分を共有する
TRIE を作成する. 具体的には , 部分集合の要素を辞書順にソートし , 要素の左から順に TRIE に格納す
る. TRIE の各ノード には , その ノード に対応する部分構造が持つ重み wj が格納される.
事例 x を分類する時は , x の部分構造を深さ優先に列挙しながら , TRIE の ノード を探索していけばよい. TRIE の実装として , Double-Array [2, 7] を用
いた.

5

実験

5.1

設定

提案手法の有効性を示すために , 日本語係り受け解析タスクに対し 実験を行った. 採用した係り受け解析モデルは , Cascaded Chnking Model[14] と呼ばれるモデルで , 直後に係るか係らないかのみで動作し ,その判定に SVM を用いている.
実験に用いたコーパスは京大コーパス（ Version
2.0 ）[9] の一部で , 学習には 1 月 1 日から 8 日分（ 7958
文）, テストには 1 月 9 日分の （ 1246 文）を用いた.
これは , 文献 [14] で用いたデータと同一である. また,実験には , 3 次の polynomial kernel を用いた. これも, 文献 [14] と同一の設定である. RBF Kernel については , 分散パラメータの値に精度が敏感に反応し ,本タスクでは実用に向かなかったので , 実験を行っていない. すべての実験は , XEON 2.4GHz 4.0Gbyte
Memory の Linux 上で実験を行った. マイニング , 解• サイズの制限
析のプログラムは , すべて C++ で実装した.
d 次の polynomial kernel の場合は , d 個 までの
表 1 に , 実験データのサイズ等の情報, それぞれ部分系列を列挙するだけで十分である. そのたの解析精度 (係り受け精度), および式 (2) の通常のめ, d + 1 個の部分系列への射影は行わない.
Kernel を用いて解析を行った場合の解析時間を示す.
• 部分集合重み cr
サイズ r の部分系列の頻度を cr 倍する. しかし , 大きい部分系列に対する重みが , 小さい部分
5.2 結果系列に対する重みより大きい場合, 射影が行われない場合が発生し , パターンを取りこぼしてし表 2 に , σ を 0.1 から 0.0001 まで変化させた時の,まう可能性がある. そのため, 便宜的に , cr のう 解析時間, 解析精度, モデルサイズをまとめる. σ =ち最大の値 m(= max({c1 , c2 , . . . , cn })) を選び , 0.0005 の時に , テストデータを通常の Kernel を用い
部分系列のサイズに関わらず , m 倍した頻度に た分類器と同じ 精度で解析することができた . この

- {係り元, 主辞, 品詞細分類, 普通名詞} and{係り元, 機能語, 表層, と } and {係り先, 主辞, 品詞細分類, 普通名詞}(「普通名詞 と 普通名詞」並列構造)- {係り元, 機能語, 表層, を } and {係り先, 主辞, 表層, 中心} and {係り先, 機能語, 表層, に }(「〜を 中心に」 頻出言い回し )- {係り元, 機能語, 表層, から } and{係り元, 機能語, 品詞, 助詞} and {係り先, 機能語, 表層, まで }(「〜から 〜まで」 頻出言い回し )図 2: 取り出された 3 つ組み部分構造の一部時の解析速度は , 通常の Kernel を用いた分類器に比べ, 約 1/30 (0.0097/0.2848) となった.
図 2 に , 実際抽出された 3 つ組パターンのうち, 値の大きいものを 3 つ列挙した. 「名詞 と 名詞」「〜を中心に」「〜から〜まで」といった, 頻出する言い回しを適度に一般化した素性の組みが抽出されている.

造) を抽出, 提示する手法を提案した. 具体的には , 部
分集合 Kernel という種類の Kernel に注目し , その
Kernel の 部分構造の展開に データマインングアル
ゴ リズムの 1 つである PrefixSpan を用いた. 日本語
係り受けの実験では , Kernel を用いた従来の分類器に比べ, 30 倍の速度向上に成功した.
今後は , 部分集合 Kernel のうち RBF Kernel に関する実験, 係り受け解析以外のタスクにおける実験を行いたいと考える. さらに , 部分集合 Kernel 以外の
5.3 頻度によるフィルタリング
Kernel (Tree Kernel, String Kernel) についても 部
実験より, 通常の Kernel に基づく解析器と同程度 分木 や 部分系列のマイニングアルゴ リズムを用い,の解析精度を得るためには , 少なくとも σ = 0.0005 提案手法の有効性を検証したいと考える.
程度に設定する必要があることが分かる. しかし , この時のパターン数は , 約 826 万 で , モデルのファイル
付録 Ar
サイズは , 391MB にも及び , 非常に大きく, あまり実Xr−m
τ (l, r) =· ml
r Cm (−1)
用的ではない.
m=0
一般に , Ω のサイズが小さくなれば , TRIE を探索する空間が減少するために , 速度向上に繋がる. そこ [証明]で , 不必要な部分構造を削除するために , サポートベ
x = {x1 , x2 , . . . , xN }, y = {y1 , y2 , . . . , yN }クターの集合から , Ω 中の各部分構造の出現頻度を計(ただし xj , yj ∈ {0, 1})
算し , 高頻度の部分構造のみを残し , 残りを削除するという単純なフィルタリング実験を行った . 各部分構 とする. この時, 多項定理を用いると造の頻度は , PrefixSpan を用いて効率良く計算できN³X´l
る. σ=0.0005 にし , 頻度閾値 ξ(= {1, 2, 3, 4}) 回以上(x · y)l =xj yjのパターンのみを残した実験結果を表 3 に示す.
j=1
結果 ξ = 2 とし た場合, サ イズを 約 1/3 に
k1 +...+kN =l
Xl!
することが で きた.
また, 若干ながら 精度向上
(x1 y1 )k1 . . . (xN yN )kN=k!
.
. . kN !
1(89.29%→89.34%) が確認できた. これは , 低頻度にkl ≥0もかかわらず , 高い重みを持つ部分構造が削除されたからと考える. このような部分構造は , 学習データの となる. xkj ∈ {0, 1} に注意しながら同類項をまとめ, さj
誤りや特殊な事例と考えられ , 過学習の原因になりや らに対称性に注意すると, r 個 (r = {0, 1, . . . , l}) の部分構
すい.
造の個数は , (x1 y1 x2 y2 . . . xr yr ) の定数項となる. よって,

X

k1 +...+kr =lτ (l, r)6=

今後の課題とまとめ

本稿では , データマイニングの手法を使い, 学習後のサポートベクターの集合から , 分類に寄与する有効な素性の組み合わせ (一般には事例の中の部分構

kl ≥1,l=1,2,...,r==l!
k1 ! . . . kr !

rl − r C1 (r − 1)l + r C2 (r − 2)l − . . .
rX
m=0r Cm (−1)

r−m

· ml

■.

表 1: 係り受け実験データとベースライン結果
学習データ数

SV 数 (正例/負例)

次元数

平均非 0 次元数

解析時間 (秒/文)

係り受け正解率 (%)

110,355

34,996 (17,528/17,468)

43,63717.64

0.284889.29

表 2: 実験結果

σ|Ω|

TRIE ファイルサイズ (MB)

82.02
86.27
88.91

7,289
30,52373,9147

1.8
3.1
37.2

0.001
0.00050.00010.00670.00920.00970.0101

89.05
89.26
89.29
89.29

1,924,221
6,686,737
8,262,428
9,846,092

93.4
317.5
391.1
464.9

通常 Kernel

0.2848

89.29

0.1
0.05
0.01
0.005

解析時間 (秒/文)

係り受け正解率 (%)

0.00130.00200.0050

表 3: 頻度によるフィルタリング結果

ξ

解析時間 (秒/文)

1
2

0.00970.00740.00690.00653
4

係り受け正解率 (%)|Ω|

TRIE ファイルサイズ (MB)89.29

8,262,428

391.1

89.34
89.31
89.25

2,450,855
1,360,019
945,286

118.0
66.4
46.8

参考文献

[9] Sadao Kurohashi and Makoto Nagao. Kyoto University text corpus project. In Proceedings of the
ANLP, pp. 115–118, 1997.

[1] Rakesh Agrawal and Ramakrishnan Srikant. Fast
algorithms for mining association rules. In Jorge B. [10] Huma Lodhi, Craig Saunders, John Shawe-Taylor,Bocca, Matthias Jarke, and Carlo Zaniolo, edNello Cristianini, and Chris Watkins. Text classiitors, Proc. 20th Int. Conf. Very Large Data
fication using string kernels. Journal of Machine
Bases, VLDB, pp. 487–499. Morgan Kaufmann,
Learning Research, Vol. 2, , 2002.
12–15 1994.
[11] Jian Pei, Jiawei Han, and et al. Prefixspan: Min[2] Junichi Aoe. An efficient digital search algorithm
ing sequential patterns by prefix-projected growth.
by using a double-array structure. IEEE TransIn Proc. of International Conference of Data Engiactions on Software Engineering, Vol. 15, No. 9,
neering, pp. 215–224, 2001.
1989.
[12] Vladimir N. Vapnik. The Nature of Statistical[3] Michael Collins and Nigel Duffy. Convolution kerLearning Theory. Springer, 1995.
nels for natural language. In NIPS, 2001.
[13] 山田寛康, 工藤拓, 松本裕治. Support vector machine[4] Hideki Isozaki and Hideto Kazawa. Efficient supを用いた日本語固有表現抽出. 情報処理学会論文誌,
port vector classifiers for named entity recognition.
Vol. 43, No. 1, pp. 44–53, 2002.
In Proceedings of COLING-2002, 2002.
[5] Hisashi Kashima and Teruo Koyanagi. Svm kernels [14] 工藤拓, 松本裕治. チャンキングの段階適用による日本語係り受け解析. 情報処理学会論文誌, Vol. 43, No. 6,
for semi-structured data. In Proc. 19th Int. Conf.
pp. 1834–1842, 2002.
Machine Learning, 2002.
[6] Risi Imre Kondor and Jon Lafferty. Diffusion kernels on graphs and other discrete input spaces. In
Proc. 19th Int. Conf. Machine Learning, 2002.
[7] Taku Kudo. Darts: Double-ARray Trie System.
[8] Taku Kudo and Yuji Matsumoto. Chunking withsupport vector machines. In Proceedings of the Second Meeting of the NAACL, 2001.