社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

カーネル法に基づく構造データのラベル付け学習アルゴリズム
鹿島

久嗣

坪井

祐太

† 日本アイ・ビー・エム株式会社 東京基礎研究所 〒 242–8502 神奈川県大和市下鶴間 1623–14
E-mail: †{hkashima,yutat}@jp.ibm.com
あらまし 本稿において，我々はパーセプトロンアルゴリズムに基づく，配列や木，グラフなどの構造を持ったデータのラベル付け学習アルゴリズムを提案する．また，ラベル付けに用いることのできるいくつかのカーネル関数とその効率的な計算法を与える．提案手法は，完全にカーネル化されており，かつ，点ごとのラベル予測を行うため，任意の数の非観測変数を含む，サイズの大きい素性を用いることができる．この点において，提案手法は最大エントロピー
マルコフモデルや条件付確率場など少数の非観測変数をもつ素性しか扱うことのできない既存の手法と大きく異なる．
キーワード

カーネル法， パーセプトロン，周辺化カーネル，固有表現抽出，情報抽出

Kernel-based Discriminative Learning Algorithms
for Labeling Structured Data
Hisashi KASHIMA and Yuta TSUBOI† IBM Tokyo Research Laboratory Shimotsuruma 1623–14, Yamato-shi, Kanagawa, 242–8502 Japan
E-mail: †{hkashima,yutat}@jp.ibm.com
Abstract We introduce a new perceptron-based discriminative learning algorithm for labeling structural datasuch as sequences, trees and graphs. Since it is fully kernelized and employs the pointwise label prediction, large
features including arbitrary number of hidden variables can be incorporated with polynomial time complexity. Thisis contrasted with existing labelers that can handle only features of a small number of hidden variables such as
Maximum Entropy Markov Models and Conditional Random Fields. We also introduce several kernel functions forlabeling sequences, trees and graphs and the efficient algorithms for them.
Key words Kernel Methods, Perceptron, Marginalized Kernel, Named Entity Recognition, Information Extraction

1. ま え が きることが求められるため，単語と，その頭文字のように互いに独立でない素性を自然に扱うことができないという問題がある．

ラベル付け問題は，観測変数集合の値が与えられたときに，一方，近年，最大エントロピーマルコフモデル (MEMM) [1] や非観測変数集合の値を予測する問題であり，教師ありの多クラ条件付確率場 (CRF) [2] などの条件付モデルと呼ばれるモデル

ス分類問題を一般化した問題である．特に，配列ラベル付けは，が，観測変数から非観測変数を予測するという目的に適してい自然言語処理，バイオインフォマティクス，Web データの解析るため，注目を集めている．さらに，Collins [3] は隠れマルコなど多くの分野で見られる重要な問題である．配列ラベル付け

フ (HM) パーセプトロンと呼ばれる，パーセプトロンアルゴリの学習問題は長年活発に研究がなされてきたが，より一般的なズムに基づく効率的なアルゴリズムを提案している．これを拡木やグラフといった構造データのラベル付けについてはほとん

張する形で，サポートベクターマシン (SVM) に基づくアルゴ

ど研究がなされていない．本稿では，これら一般的な構造デー

リズム [4] やブースティングに基づくアルゴリズム [5] も提案さ

タのラベル付け学習問題において，カーネル法によるアプロー

れている．

チを行う．

いくつかの問題において，自然言語処理におけるイディオム

配列ラベル付け問題には長年，隠れマルコフモデル (HMM)

や，バイオインフォマティクスにおけるモチーフなどのようにが用いられ，一定の成功を収めてきた．しかしながら，HMM

バイグラムなどの局所的な素性を組み合わせるだけでは広い範は観測変数と非観測変数の同時確率分布を推定するという，よ囲の文脈を捉えるのに充分でない場合がある．しかしながら，り難しい問題を解いており，多くの学習データを必要とする．

現在提案されているほとんどの手法では，少数の非観測変数を

また，観測変数は，非観測変数が与えられると互いに独立であ含む素性しか用いることができない．ラベル付けの段階は，通—1—

図 1 (a) 1 次のマルコフ仮定に基づく配列のグラフィカルモデル表現．

図 2“the, man, saw ,· · · , glasses.”は，観測変数のラベル列 x，品
詞タグ列 “DT, NN, VBD, . . ., NNS”は，非観測変数のラベル
列 y を表す．(b) 観測変数と非観測変数のペアからなる素性 (c)
連続する 2 つの非観測変数からなる素性

配列ラベリングのための素性 (長さ 3)．バイグラムの素性では”marked”の品詞を決定するのには充分でない．

黒いノードは観測変数を，白いノードは非観測変数を表す．文

トロンに基づくラベル付け学習アルゴリズムである HM パーセ
プトロンを提案した．HM パーセプトロンは訓練例をオンライン型で順番に処理できるため効率がよく，その性能は CRF に

常 Viterbi アルゴリズムのような動的計画法に基づく方法が用いられるが，ひとつの素性に含まれる非観測変数の数に対して計算量が指数的に増大する．HM パーセプトロンや HMSVMは双対型で書くこともできるが，やはりこの問題は解決されない．
本稿では，はじめにラベル付け候補を絞ることなく，大局的な素性を用いてラベル付けを行うことのできる方法である周辺
化ラベル付けパーセプトロンを提案する．これは，周辺化カー
ネル [6] と，点ごとのラベル予測 [7] という 2 つのアイデアに基匹敵することが示されている [16]．HM パーセプトロンの重要な点は，観測変数集合から非観測変数集合へのマッピングを，観測変数集合の値と非観測変数集合の値の組の 2 値分類，すな
わち Σx T × Σy T → {+1, −1} として捉える点である．F を全ての素性の集合とし，φf (x, y) を，素性 f ∈ F が (x, y) 内に出現する回数，Φ(x, y) はそれをベクトルの形にあらわしたものとする．x が入力として与えられると，HM パーセプトロン
は現在の素性の重みに基づき，予測 ŷ を出力する．

ŷ = argmaxy∈Σy

づいている．点ごとのラベル予測によって，各非観測変数のラ

T

X

­

®

wf φf (x, y) = argmax w, Φ(x, y) (1)
y∈Σy

f ∈F

T

ベルをそれぞれ予測できるため，前述の問題が解決される．まここで wf は素性 f の重みであり，w はこれらをベクトルの形

た，周辺化カーネル [6] を用いたカーネル化によって，任意ので表したものとする．1 次のマルコフ仮定の下では，観測変数数の非観測変数を含むような大きい素性を扱うことができるよと非観測変数のペアからなる素性 (図 1(b)) と，連続する 2 つうになる．さらに我々は，配列や順序木といったいくつかの構の非観測変数からなる素性 (図 1(c)) の，2 つのタイプの素性が造データにたいして，実際の周辺化カーネル関数を提案する．

考えられる．重みの学習は，訓練例 e(i) に対する予測が誤り，

近年，カーネル法を用いた構造データの分類は精力的に研究さすなわち ŷ (i) =| y (i) であったときに，れており，配列カーネル [8], [9] や木カーネル [10], [11]，グラフ
カーネル [12], [13] などが提案されている（注 1）．これらは大抵，

wnew = wold + Φ(x(i) , y (i) ) − Φ(x(i) , ŷ (i) )(2)

広範囲にわたる文脈を取り入れるため，部分列や部分グラフなによって更新される．さらに (1) は訓練例の重み α を用いるこどの部分構造が，構造データ内に出現する回数などを用いて素とで双対型で書くことができる．

性ベクトルを定義している．これらの素性ベクトルは通常，高次元 (場合によっては無限次元) になるため，接尾辞木や動的計

ŷ = argmaxy∈Σy

画法，あるいは行列計算などを用いて，素性を陽に数え上げる
ことなく効率的にカーネル関数を計算する方法を提案されている．我々はこれらのカーネルに基づき，配列や順序木に対する周辺化カーネルと，その効率的な計算方法を与える．（注 2）
また，最後に実世界データを用いた，配列と木に対するラベル付け問題の実験を行い，その有効性を検証する．

2. 隠れマルコフ (HM) パーセプトロン
ラベル付け問題は，観測変数 x = (x1 , x2 , . . . , xT ) から非観
測変数 y = (y1 , y2 , . . . , yT ) へのマッピングを求める問題として定義できる．ここで xt ∈ Σx ，yt ∈ Σy とする．例えば，品詞タ
グ付けなどのタスクにおいて，xt は t 番目の単語を表わし，yt
は t 番目の単語の品詞を表す (図 1)．学習器は，訓練データの集合 E = (e(1) , e(2) , . . . , e(|E|) ) を用いることができる．ここで，e(i) = (x(i) , y (i) ) は i 番目の訓練例で，|x(i) | = |y (i) | = T (i)とする．
Collins [3] は，CRF や MEMM の代替手法としてパーセプ（注 1）： [14] に詳細なサーベイがある．
（注 2）：非循環有向グラフに対する周辺化カーネルは [15] を参照されたい．

T

|E|
X
X

­

®

αj (ỹ) Φ(x(j) , ỹ), Φ(x, y)(3)

j=1 ỹ∈Σy T

初期値 ¸ = 0 から始めると，重みの更新ルールは以下のように書き直せる．
• αinew (y (i) ) = αiold (y (i) ) + 1

αinew (ŷ (i) ) = αiold (ŷ (i) ) − 1(x(i) , ŷ (i) ) は負例として働くため，擬似負例と言われる．
さて，問題によっては上で用いたサイズ 2 の素性 (図 1(b)(c))
では広範囲にわたる文脈をモデル化するのには充分でない場合がある．そこで HM パーセプトロンにおいて，長さ d までの素性 (図 2) を用いることを考える．xtt21 は x の t1 番目から t2 番
目までの観測変数集合を表すとし，y tt21 も同様に定義する．全ての素性は高々d 個の非観測変数に依存することを考慮すると，
Φ(x, y) は以下のように展開できる．
•

Φ(x, y) = Φ(xd1 , y d1 ) − Φ(xd2 , y d2 ), y d+1), y d+1) − Φ(xd+1+Φ(xd+1
3
2
3
2
···

(4)

−1
−1
−1
−1
+Φ(xTT −d, y TT −d) − Φ(xTT −d+1
, y TT −d+1)

+Φ(xTT −d+1 , y TT −d+1 ).
—2—

(4) を (1) に代入することで，y の予測は動的計画法を用いて行うことができる．

­

max w, Φ(x, y) = max s(y1 , . . . , yd )®

wnew= wold +, y t+d−1)+ w, Φ(xtt+d−1 , y tt+d−1 ) − Φ(xt+d−1
t+1
t+1

®

X

(i)

しかしながら，各再帰のステップの計算時間は d について指数的に増加してしまう．たとえ双対型 (3) にしても，長さ d までの非観測変数の文脈は陽に考えなければならないため同様の問
題は残る．これはカーネルを用いて任意のサイズの素性を導入する上で重大な障害となる．CRF も同様の分解に基づく動的計画法を用いるため同様である．さらには，素性の出現を数えP (y|x)Φ(x, y) (6)(i)

y:yt =ŷt

次に，周辺化ラベル付けパーセプトロンの双対型を導くことで，これをカーネル化する．φf (x, y; t) を，素性 f が (x, y) 内に，(x, y) の t 番目の非観測変数を含む形で出現する回数とし，また Φf (x, y; t) をそのベクトル表現とする．まず，もともとの形(5) を ỹt に依存しない項を足すことで以下のように変形する．

Xŷt = argmaxỹt ∈Σy

る際ギャップなどの曖昧さを許すようなカーネル [8] を用いるに到っては，長さ d の素性が，長さ d 以上の領域にまたがりうる+

ため，分解 (4) でさえ用いることができない．Collins は，あら

X

­

−

y:yt =ỹt

X

器を用いて，適当な数のラベル付け候補を出力し，それをよりX­= argmaxỹt ∈Σy性に基づく始めの候補の中に含まれているという保証はない．

®

P (y|x) w, Φ(x, y; t)­®

P (y|x) w, Φ(x, y)y∈Σy T

広範囲にわたる素性を用いて再ランキングするという方法でこ®

P (y|x) w, Φ(x, y)ỹt ∈Σy y:yt =ỹt

かじめ学習された，局所的な素性のみを用いる別のラベル付けの問題を避けている [17] が，正しいラベル付けが，広範囲の素X

P (y|x)Φ(x, y) −y:yt =yts(yT −d+1 , . . . , yT ) = w, Φ(xTT −d+1 , y TT −d+1 )

X

­

®

P (y|x) w, Φ(x, y; t)(7)

y:yt =ỹt

更新則は以下のように書き換えられる．

3. 周辺化ラベル付けパーセプトロン
前節で述べた問題点を解決するために，カーネル法に基づ

wnew = wold +P

log Ps (y (i) |x(i) ) を最大化することによって学習する．この目的関数は，ひとつの配列上の全部の非観測変数を正しくラベル付することを目指しているといえる．一方，Kakade ら [7] は多くのタスクにおいて，個々の非観測関数のラベルを正しくラベル付けできればよいという点に注目し，点ごとに周辺化された尤度に基づく目的関数
P P(i)log Pp (yt = yt |x(i) ) を提案した．ここで，
i
t
i

X

P (y|x)Φ(x, y; t) −(i)y:yt =yt

くラベル付け器を提案する．通常，MEMM や CRF は，モデ(i)
Pp (yt = yt |x(i) ) =(i)=| yt のとき，重みベクトル w は，以下の更新則によって更新される．

yt+d

ル Ps (y|x) は対数尤度の和

P (y|x)Φ(x, y) は，新しい素性ベクトルと

y:yt =ỹt(i)s(yt , . . . , yt+d−1 ) = max s(yt+1 , . . . , yt+d )­Pの予測が誤りだったとき，すなわち，ŷty1 ,...,yd

­

ベクトル

考えることができるので，e(i) の t 番目の非観測変数について®

y

れた MEMM や CRF などでもよい．また，周辺化された素性XP (y|x)Φ(x, y; t)(i)y:yt =ŷt

例の重み ¸ を導入して，w を線形和の形で書くと，
(j)

w=

|E| T
X
X X

X

αjτ (y̆τ )j=1 τ =1 y̆τ ∈Σy

P (y|x)Φ(x(j) , y; τ )(8)y:yτ =y̆τとなるので，これを (7) に代入することで，周辺化カーネルラ
ベル付けパーセプトロン
(j)

X

Ps (y

(i)

(i)

ŷt = argmax|x )ỹt ∈Σy(i)

y:yt =yt

は，t 番目の非観測変数のラベルを yˆt ∈ Σy に固定し，それ以

|E| T
X
X X

j=1 τ =1 y̆τ ∈Σyを得る．ここで，外の非観測変数について周辺化した Ps (y|x) である．この目的

K(x(j) , x, τ, t, y̆τ , ỹt ) =関数は，もともとの配列ごとの尤度に基づく目的関数に匹敵す(j)る性能をもつことが示されている [16]．ここで重要な点は，Pp
は yt にのみ依存するため，ラベル予測も点ごとに行われると

αjτ (y̆τ )K(x(j) , x, τ, t, y̆τ , ỹt ),(9)X

X

P (y|x0­)P (y |x) Φ(x

(10)
(j)

0

®

, y; τ ), Φ(x, y ; t)y:yτ =y̆τ y 0 :y 0 =ỹttいうことである．我々はこのアイデアと，パーセプトロンに基は 2 つの例の τ 番目と t 番目の非観測変数のラベルをそれぞれづくラベル付け器とを組み合わせることで，以下に定義される

固定し周辺化されたカーネル関数であるため周辺化カーネル [6]

周辺化ラベル付けパーセプトロンを提案する．

と呼ばれる．アルゴリズムを図 3 に示す．

ŷt = argmaxỹt ∈ΣyX­®

P (y|x) w, Φ(x, y)(5)y:yt =ỹtargmax 操作は ỹt にのみ依存するので，点ごとのラベル予測が実現されている．基本的な考え方としては以下のとおりである．
yt を予測する際，もともとのラベル付けパーセプトロンの出力
hw, Φ(x, y)i は，t 番目の非観測変数のラベルを yˆt に固定し，そのほかの非観測変数について周辺化される．P (y|x) は，非観測変数についての事前分布であり，これはあらかじめ訓練さ

4. 周辺化カーネル関数の計算
本節では配列及び順序木のラベル付けのための周辺化カー
ネル (10) を提案する．近年，さまざまな構造データに対するカーネル関数は精力的に研究されている [14] が，これをラベ
ル付けに使えるよう拡張する．ここでは簡単のため，事前分布

QT

P (y|x) は，P (y|x) = t=1 P (yt |xt ) のように分解できるとするが，本稿の結果は CRF などのより一般的なモデルを事前分布として用いる場合にも拡張可能である．また，表記上の簡単—3—

// Initialization¸ := 0// Training
for round = 1, . . . , max round,for i = 1, . . . , |E|,// kernel computation
for j = 1, . . . , |E|,for t = 1, . . . , T (i) , and τ = 1, . . . , T (j) ,for y̆τ ∈ Σy , and ỹτ ∈ Σy ,compute K(x(j) , x(i) , τ, t, y̆τ , ỹt )// prediction & update
for t = 1, . . . , T (i) ,(i)predict ŷt(i)if ŷt

図 4め，素性は図 2 に示すような，任意の長さ連結した非観測変数と観測変数のペアとする．素性のサイズに制限を設けないため，

by using Equation (9)様々なサイズの素性が入り混じることになるが，そこで，混合(i)=| yt ,

定数 c > 0 を用いて，φf を属性 f のサイズ d に応じて重み付

(i)

(i)

αit (yt ) := αit (yt ) + 1

ける．例えば f が (x, y) に N 回出現したとすると，φf (x, y)(i)(i)αit (ŷt ) := αit (ŷt ) − 1

図3

上流の素性と下流の素性を組み合わせることで，大きい素性が構成される例は N · cd と定義する．KU (τ, t) や KD (τ, t) において，ある点

周辺化カーネルラベル付けパーセプトロンのため本節の残りの部分では，K(τ, t, y̆τ , ỹt ) を i 番目の例と j
番目の例が与えられたときのカーネル関数とする．我々のカーネル関数を計算する上で重要な点は，すべての素性が，より小さい素性を組み合わせることで表現できる点である．たとえば，

τ より上流の変数 y U (τ ) とは，その点とそれより左にある変数のことである．同様に下流の変数 y D (τ ) とは，その点とそれより右にある変数のことであるとする．アルゴリズムは，丁度 HMM の前向き・後ろ向きアルゴリズムのように，それぞれKU と KD を計算するための 2 つの動的計画法のループからなる．

図 4 で素性 (b) が，その一番右端を t 番目の非観測変数に，まKU (τ, t) = c2 k(xτ(j) , xt )(KU (τ − 1, t − 1) + 1)

(i)

(14)

た素性 (c) が，その一番左端を t 番目の非観測変数に置いて出(i)
KD (τ, t) = c k(xτ(j) , xt )(KD (τ + 1, t + 1) + 1)

(15)

現しているとすると，素性 (b) と (c) を組み合わせた素性 (a)は，その 2 番目の変数を t 番目の非観測変数に置いて出現していることになる．従って，本節で提案する周辺化カーネルはす
べて上流カーネル KU (τ, t)，下流カーネル KD (τ, t)，点カーネ

2

ここで，

(i)

·ky (y̆τ , ỹt )kx (xτ(j) , xt )K(τ, t, y̆τ , ỹt ) = KU (τ, t) · KP (τ, t, y̆τ , ỹt ) · KD (τ, t)

X X

­

(i)

(j)

P (y U (τ )|xU (τ ))P (y 0U (t)|xU (t))

y U (τ ) y 0 (t)
U

(j)

®

(i)

· Φ(xU (τ ), y U (τ ); τ ), Φ(xU (t), y 0U (t); t)X X

KD (τ, t) =

­

(11)
(i)

(j)

P (y D (τ )|xD (τ ))P (y 0D (t)|xD (t))

y D (τ ) y 0 (t)
D

(j)

(i)

(i)

P (y̆τ |xτ(j) )P (ỹt |xt )y̆τ ∈Σy ỹt ∈Σyル KP (τ, t, y̆τ , ỹt ) の 3 つに分解できるとする．

KU (τ, t) =

X X

(i)

k(x(j)
τ , xt ) =®

· Φ(xD (τ ), y D (τ ); τ ), Φ(xD (t), y 0D (t); t)(12)とする．境界条件は KU (τ, 0) = KU (0, t) = KD (τ, |T (i) |+1) =KD (|T (j) | + 1, t) = 0 である．KP は以下によって計算できる．
KP (τ, t, y̆τ , ỹt )
(j)

=

(j)

(i)

(i)

c2 P (y̆τ |xτ )P (ỹt |xt )ky (y̆τ , ỹt )kx (xτ , xt )

¡

¢

(j)
(i) 2
c2 k(xτ , xt )(16)

ここで，kx と ky は 2 つの引数が同一であるときに 1 を，そうでないときに 0 を返す関数とするが，ここを 2 つの変数の間のカーネル関数で置き換えることも可能である．明らかに，このKP (τ, t, y̆τ , ỹt ) =
(j)

(i)

­

(j)

¡PP

(j)

(i)

­

(j)

カーネル関数の計算量は O(T (i) T (j) ) である．（注 3）®

(i)

P (y̆τ |xτ )P (ỹt |xt ) Φ(xτ , y̆τ ; τ ), Φ(xt , ỹt ; t)
(i)

®¢2

P (y̆τ |xτ )P (ỹt |xt ) Φ(xτ , y̆τ ; τ ), Φ(xt , ỹt ; t)y̆τ ỹt(13)
ここで，y U (τ ) と y D (τ ) は，それぞれ τ 番目から上流あるいは下流に位置する非観測変数の集合とする (y U (τ )∩y D (τ ) = {yτ })．
また KP (τ, t, y̆τ , ỹt ) の分母は KU (τ, t) と KD (τ, t) の重なり部
分を打ち消すための項である．KU や KD における周辺化を陽に計算することは現実的ではないが，多くの場合，動的計画法などをつかうことで効率的に計算可能である．この分解によって，i 番目と j 番目の例が与えられたときに，全ての (τ, t, y̆τ , ỹt ) のとりうる値に対し周辺化カーネルを 1 回の計算で計算できる．
4. 1 配列のラベル付けのための周辺化カーネル
ここでは配列における広範囲にわたる依存関係を考慮するた

4. 2 順序木のラベル付けのための周辺化カーネル
順序木 (図 5) のラベル付けのためのカーネルを，順序木カー
ネル [11] を拡張することによって設計する．素性は図 5 に示すような任意の順序木の形をしているとする．配列ラベル付けのときと同様，混合定数 c を用いて φf (x, y) を定義する．KU (τ, t)
や KD (τ, t) において，ある点 τ より上流の変数 y U (τ ) とは，その点とそれより外側にある変数のことであり，下流の変数
y D (τ ) とは，その点とそれより内側にある変数のことであるとする．アルゴリズムは，丁度，確率文脈自由文法の内側・外側
アルゴリズムのように，それぞれ KU と KD を計算するための2 つの動的計画法のループからなる．ch(τ, υ) を τ 番目のノー（注 3）：ここでの結果は [8] にみられるようなギャップを許した曖昧なマッチングを許すように拡張可能である．詳しくは [15] を参照されたい．

—4—

図5

順序木の例：黒いノードは観測変数を，白いノードは非観測変数を表す．

ドの υ 番目の子を表すインデクスとし，pa(τ ) を τ 番目のノー
ドの親ノードを表すインデクスとする．また，#ch(τ ) を τ 番

図6

順序木における KU (τ, t) の計算のイメージ.

目のノードの子供の数とし，chID(τ ) を，τ 番目のノードがその親ノードの何番目の子ノードであるかを表すインデクスとする．
順序木カーネル [11] の再帰的計算と同様にして，KD は後行順
で動的計画法により，

表1

精度
適合率
再現率
F1
配列カーネル
88.7% (3.4) 49.0% (6.0) 23.1% (8.1) 30.5 (6.7)
HM パーセプトロン 80.2% (11.5) 23.8% (14.6) 17.9% (3.0) 18.6 (5.2)

表2(i)
KD (τ, t) = c k(x(j)τ , xt )SF (τ, t, #ch(τ ), #ch(t))
2によって計算される．ここで SF も以下によって再帰的に定義

固有表現抽出結果 (括弧内は標準偏差)

製品使用情報抽出結果 (括弧内は標準偏差)

精度
適合率
再現率
F1
Sequence Kernel 89.7% (2.0) 52.2% (9.5)
29.6% (4.0)
37.5(4.1)
Tree Kernel
89.9% (2.7) 51.4% (10.9) 32.5% (14.4) 38.9 (12.1)
HM-Perceptron
89.7%(1.8)
51.5%(8.5)
24.0%(21.4)
28.9(20.3)

される．
抽出) での実験結果を示し，提案手法により効率的に扱うこと

SF (τ, t, υ, u) = KD (ch(τ, υ), ch(t, u))SF (τ, t, υ − 1, u − 1)
+SF (τ, t, υ − 1, u) + SF (τ, t, υ, u − 1)

は周辺化ラベル付けパーセプトロンと HM パーセプトロンの性−SF (τ, t, υ − 1, u − 1)

能比較を行った．

境界条件は SF (τ, t, 0, u) = SF (τ, t, υ, 0) = 1 である．直感的には SF (τ, t, υ, u) は ch(τ, 1) 番目から ch(τ, υ) 番目の子集合と，

ch(t, 1) 番目から ch(t, u) 番目まで子集合の全ての，順序を保存したマッチングについての和をとっているといえる．
同時に，あとで KU を計算するときのために，ch(τ, υ) 番目からch(τ, #ch(τ )) 番目の子集合と，ch(t, u) 番目から ch(t, #ch(t))
番目まで子集合の全てのマッチングについての和をとったものを表す SB (τ, t, υ, u) をSB (τ, t, υ, u) = KD (ch(τ, υ), ch(t, u))SB (τ, t, υ + 1, u + 1)
+SB (τ, t, υ + 1, u) + SB (τ, t, υ, u + 1)
−SB (τ, t, υ + 1, u + 1)と 定 義 す る ．境 界 条 件 は SB (τ, t, #ch(τ ) + 1, u)=

SB (τ, t, υ, #ch(t) + 1) = 1 である．
KU は先行順の動的計画法で計算される．KU (τ, t) は，親ノード同士の上流カーネルと，兄弟同士の下流カーネルを組み合わせることで計算できる (図 6)．
(i)³

KU (τ, t) = c2 k(x(j)τ , xt ) 1 + KU (pa(τ ), pa(t))·SF (pa(τ ), pa(t), chID(τ ) − 1, chID(t) − 1)´

·SB (pa(τ ), pa(t), chID(τ ) + 1, chID(t) + 1)
KP は (16) と同様である． [11] と同様の解析によってこのカー
ネルの計算量は O(T (i) T (j) ) であることが容易に分かる．

5. 実が可能になった大きな構造素性の有用性を検証する．本実験で験

5. 1 固有表現抽出
固有表現抽出は情報抽出課題の一つで，文書内の人名・地名・組織名などを識別する問題である．実験では，CoNLL2002 固
有表現抽出課題で提供されたスペイン語のデータの最初の 300
文 (8,541 単語) を使用した．この課題は，各単語に固有表現の種類を示すラベルを付与する課題である．ラベルの数は，各固有表現の種類と表現の境界種別の組み合わせ 8 ラベルと非固有表現を示すダミーラベルを合わせた 9 種類 (|Σy | = 9) である．
観測変数のカーネルは単語とそのスペリング (詳細は [16] の S2
素性を参照のこと) を素性とした 2 次の多項式カーネルを使用した．ただし，HM パーセプトロンは [4] に倣い前後 1 単語の素性も含めた．周辺化ラベル付けパーセプトロンでは配列ラベ
ル付けカーネル (配列カーネル) を用いた．混合定数は事前実験により求めた c = 1 とした．また，非観測変数に対する事前分
布は一様分布 (P (yt |xt ) = 1/|Σy |) として設計した．性能評価にはダミーラベルを含めたラベル付けの精度，固有表現ラベルの適合率・再現率，適合率と再現率の調和平均値である F1 尺度を用いた．
表 1 は 5 分割交差検定の結果である．提案手法は HM パー
セプトロンを大きく上回る性能を示した．配列ラベル付けカー
ネルを用いた提案手法が良い性能を示した理由は，固有表現抽出の性質によるものと考えられる．固有表現抽出課題は自然言語処理の問題の中で広い文脈情報を考慮する必要がある問題の一つである．例えば，「ホワイトハウス」は文脈により場所または組織を示すかが異なる．この実験結果は，人手による素性の選択なしに幅広い文脈情報を効率的に扱うことが出来るカーネル化されたラベル付け学習アルゴリズムの優位性を示すものと言える．

本節では自然言語処理の課題 (固有表現抽出と製品使用情報

—5—

図 7

文 “昨年サーバはリナックスクラスタに移行した” の依存構造
木． 非観測変数 “D-p” は顧客の使用している製品名，“O” は
ダミーラベルを示す．

5. 2 製品使用情報抽出
製品使用情報抽出は営業記録から顧客の製品使用状況を抽出する固有表現抽出の特殊な課題である．実験では日本語の営業記録 184 文 (3,570 語) を用いた．この課題では単語に対して，顧客が導入している製品・製造企業名・導入数・購入理由と導入済み・検討中・導入却下という導入状況の組み合わせのラベルの付与を目的とした．ダミーラベルを含め使用データでのラベル数は 12 である (|Σy | = 12)．日本語文は形態素解析器により単語に分割し品詞と正規形を付与した．観測変数のカーネル
は単語・品詞・正規形・文字種を素性とした 2 次の多項式カー
ネルを使用した．ただし，HM パーセプトロンは前後 1 単語の素性も含めた．周辺化ラベル付けパーセプトロンでは配列カー
ネルと順序木のラベル付けカーネル (木カーネル) を用いた．木
カーネルでは単語間の依存関係を示す依存構造木に対するラベ
ル付け問題とした．図 7 に依存構造木の例を示す．文の依存構
造木の生成には統計パーザ [18] を用いた．（注 4） 両カーネルとも
混合定数は c = 0.8 とした．
5 分割交差検定の結果を図 2 に示す．固有表現抽出課題と同様に HM パーセプトロンに比べて提案手法は優れた性能を示した．また，総合的には木カーネルが若干良い性能を示した．この結果は製品使用情報抽出において製品名と字面としては離れている用言との依存関係が重要であるという直感に合致しており，構造的な情報の有用性を示していると言える．

6. お わ り にパーセプトロンアルゴリズムに基づく，配列や木，グラフなどの構造を持ったデータのラベル付け学習アルゴリズムを提案した．また，配列や順序木のラベル付けに用いることのできる
周辺化カーネル関数とその効率的な計算法を提案し，実際のデータを用いた実験により，その有効性を検証した．今後の発展としては，CRF や MEMM などのより複雑な事前分布の導入，HM-SVM [4] のような SVM 化などが考えられる．
文

献[1] A. McCallum, D.Freitag, and F. Pereira, “Maximum entropy Markov models for information extraction and segmentation,” Proceedings of the Seventeenth International
Conference on Machine Learning, San Francisco, CA,
pp.591–598, Morgan Kaufmann, 2000.
[2] J. Lafferty, A. McCallum, and F. Pereira, “Conditional random fields: Probabilistic models for segmenting and labeling sequence data,” Proceedings of the Eighteenth International Conference on Machine Learning, San Francisco, CA,

pp.282–289, Morgan Kaufmann, 2001.
[3] M. Collins, “Discriminative training methods for hidden
Markov models: Theory and experiments with perceptron
algorithms,” Proceedings of the Conference on Empirical
Methods in Natural Language Processing, 2002.
[4] Y. Altun, I. Tsochantaridis, and T. Hofmann, “Hidden
Markov support vector machines,” Proceedings of theTwentieth International Conference on Machine Learning,
2003.
[5] Y. Altun, T. Hofmann, and M. Johnson, “Discriminative
learning for label sequences via boosting,” Advances in
Neural Information Processing Systems 15, ed. S. Becker,
S. Thrun, and K. Obermayer, Cambridge, MA, MIT Press,
2003.
[6] K. Tsuda, T. Kin, and K. Asai, “Marginalized kernels forbiological sequences,” Bioinformatics, vol.18, no.Suppl. 1,
pp.S268–S275, 2002.
[7] S. Kakade, Y.W. Teh, and S. Roweis, “An alternative objective function for Markovian fields,” Proceedings of the
Nineteenth International Conference on Machine Learning,
San Francisco, CA, pp.275–282, Morgan Kaufmann, 2002.
[8] H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, andC. Watkins, “Text classification using string kernels,” Journal of Machine Learning Research, vol.2, pp.419–444, 2002.
[9] C. Leslie, E. Eskin, and W.S. Noble, “The spectrum kernel:
A string kernel for SVM protein classification,” Proceedings of the Pacific Symposium on Biocomputing, ed. R.B.
Altman, A.K. Dunker, L. Hunter, K. Lauerdale, and T.E.
Klein, pp.566–575, World Scientific, 2002.
[10] M. Collins and N. Duffy, “Convolution kernels for natural
language,” Advances in Neural Information Processing Systems 14, Cambridge, MA, MIT Press, 2002.
[11] H. Kashima and T. Koyanagi, “Kernels for semi-structured
date,” Proceedings of the Nineteenth International Conference on Machine Learning, San Francisco, CA, pp.291–298,
Morgan Kaufmann, 2002.
[12] H. Kashima, K. Tsuda, and A. Inokuchi, “Marginalized kernels between labeled graphs,” Proceedings of the TwentiethInternational Conference on Machine Learning, San Francisco, CA, Morgan Kaufmann, 2003.
[13] T. Gärtner, P. Flach, and S. Wrobel, “On graph kernels:
Hardness results and efficient alternatives,” Proceedings of
the Sixteenth Annual Conference on Computational Learning Theory, 2003.
[14] T. Gärtner, “A survey of kernels for structured data,”
SIGKDD Explorations, vol.5, no.1, pp.S268–S275, 2003.
[15] H. Kashima and Y. Tsuboi, “Kernel-based discriminative learning algorithms for labeling sequences, trees, andgraphs,” Proceedings of the Twenty-First International
Conference on Machine Learning, 2004.
[16] Y. Altun, M. Johnson, and T. Hofmann, “Investigating
loss functions and optimization methods for discriminative
learning of label sequences,” Proceedings of the Conference on Empirical Methods in Natural Language Processing,
2003.
[17] M. Collins, “Discriminative reranking for natural language
parsing,” Proceedings of the Seventeenth International Conference on Machine Learning, San Francisco, CA, pp.175–
182, Morgan Kaufmann, 2000.
[18] H. Kanayama, K. Torisawa, Y. Mitsuishi, and J. Tsujii,“A hybrid Japanese parser with hand-crafted grammar andstatistics,” Proceedings of the 18th International Conference on Computational Linguistics, pp.411–417, 2000.

（注 4）：パーザの精度は 88%と報告されている [18]．

—6—