Ｆ値を最大化するテキストの多重ラベリング法
賀沢秀人
泉谷知範
平博順
前田英作
{kazawa,izumi,taira,maeda}@cslab.kecl.ntt.co.jp
ＮＴＴコミュニケーション科学基礎研究所

概要

このような状況を踏まえ，本研究では，テキスト多重ラベリングにおいて，Ｆ値を最大化するような学習テキストに対して複数のラベルを付与する多重ラベ方法を提案する．

リング問題において，高いＦ値 (=ラベリングの適合率と再現率の調和平均) を達成し，かつ，ノイズに対しても頑健なラベリング学習アルゴリズムを提案する．
本アルゴリズムでは，ラベル集合を F-space と呼ぶベクトル空間に埋め込んだのち，間違ったラベリングにたいするマージンが大きくなるように線形写像を推定することで，ラベリングの学習を行う．
実際の医学生物学文献と Web ページとを用いた実2Ｆ値によるラベリング評価
Ｆ値は，ある正解集合 A とそれにたいする予測集合

B が与えられたときに，その「差」を評価する尺度の一つで次のように定義される．
F (A, B) =験で，SVM や最近傍法などの 識別学習器に比べてＦ値が向上することがわかった．

2|A ∩ B|
|A| + |B|(1)

Ｆ値は，情報検索で良く用いられる尺度である適合率と再現率の調和平均に等しい [5]．
本研究のラベリング問題においては，A をあるテキ

1

テキスト多重ラベリング問題

ストに実際に付与されたラベルの集合とし，B をそのテキストにシステムが付与したラベルの集合として，本研究では，ラベルが付与されたテキストがサンプＦ値を用いることにする [3]．この点，情報検索で用いルとして与えられたときに，ラベリング規則を自動的られるＦ値とは計測する対象が異なっているので，注に学習する方法を提案する．なお，ここでは一つのテ意して頂きたい．1

キストに同時に複数のラベルを付与することを想定しており，通常一つのラベルのみ付与するテキスト分類[1] と比較すると，ラベル間の相関情報を用いることができる点が特徴である．以下では，テキスト分類との区別のため，本研究の問題設定を「テキスト多重ラベリング」もしくは単に「ラベリング」と呼ぶことにする．
テキスト多重ラベリングの研究が盛んになってきたのは，比較的最近である [2, 3, 4]．Schapire と Tingaud
は，与えられたサンプルにおいて，ラベルの有無を正しく判定した割合 (accuracy) が最大になるように学習する手法を提案している [2, 4]．しかし，上田が [3] において指摘しているように，ラベルの種類が多い場合には，「常にラベルを付与しない」という規則を用いることで，容易に高い accuracy が得られるという問題がある．そこで，[3] では評価手法として，ラベリングのＦ値が用いられているが，そこで提案された手法自体はＦ値を最大化するような学習となっていない．

一方，[2, 4] で用いられている正解率 (accuracy) は，次のように定義される．

Acc(A, B) =|A ∩ B| + |Ac ∩ B c ||L|(2)

ここで，L はラベリングに用いるラベル全体の集合である．式（2）では，実際には付与されなかったラベル（Ac ）にたいする精度と，付与されたラベル（A）にたいする精度が，同じ重みで正解率に寄与している．そのため，テキスト多重ラベリングでしばしば起こるよ
うに，テキストに付与されるラベルのほうが遥かに少ない場合（|A| ¿ |Ac |），「常にラベルを付与しない」という規則（B = φ）を用いるだけで，大きな正解率が得られてしまう．
それに対し，高いＦ値を達成できるような自明な規則は存在しない．そのため，ラベリング問題においては正解率よりも適切な評価尺度であると考えられる．
1 情報検索でＦ値を用いる場合は，A は検索要求に適合するテキスト集合であり，B は検索システムが出力するテキスト集合である．

3

最大マージンラベリング法
本節では，Ｆ値を最大化する学習アルゴリズムとして，最大マージンラベリング法を提案する．
いま，テキストは適当な方法により Rn のベクトルx に変換されているとする．さらに，Ω は全てのラベル組合せからなる集合とする．また，テキストへのラベリング規則を f : Rn 7→ Ω と書く．すると，サンプル (x1 , L1 ), . . . , (xm , Lm ) （xi ∈ Rn , Li ∈ Ω）が与えられたときの f のＦ値は次のように書くことができる．
mX2|Li ∩ f (xi )|i=1|Li | + |f (xi )|この式は分母と分子の両方に f を含んでいるため，最大化する f を直接求めることは困難である．そこで，
本研究では次のような二段階のアプローチを取ること

図 1: 最大マージンラベリング法とする．

1. Ｆ値が内積に相当するような空間を構成し，その中に全てのラベル組合せを埋め込む．
2. テキストベクトル xi を上記空間中で正しいラベ
リング Li に近い点に写すように写像 f を求める．
第一段階については，次のような性質を持つベクトル空間 HF （F-space と呼ぶ）の存在が証明できる．2hφF (A), φF (B)iF = F (A, B) + O(²)(3)

ここで，φF はラベリングを HF に埋め込む写像であり，h·, ·iF は F-space の内積である．また，² は F (A, B)
を行列と見たときの最小の固有値であり，O(²) は ² の最適化問題の解となるものを求めよ．
mX
X
1min kW k2 + C
ξiω
W 2i=1 ω∈Ω,ω6=Li¿À
φF (Li )−φF (ω)
s.t. W xi ,≥ 1−ξiωkφF (Li )−φF (ω)k F
ξiω ≥ 0 for 1 ≤ i ≤ m, ∀ω ∈ Ω, ω 6= Li .(4)

ただし，必ずしもサンプルに対して正しいラベリングが可能とは限らないので，式（4）においては，条件が破られた度合い ξiω に応じて，ペナルティC を課している．
実際に式（4）を解くにあたっては，式（4）と等価な以下の双対問題の形が便利である．

オーダーの量を表す．数値計算によると ² は通常非常に小さいため，式（3）は，F-space の内積がＦ値とほmax
ωmXαi

とんど等しいことを表している．

ち，（１）xi の像 W xi が正しいラベリング Li の近く

1αiω −m X X
X

2 i,j=1i=1 ω∈Ω,ω6=Li0αiω αjω (xi · xj )

ω6=Li ω 0 6=Lj

0

F (Li , Lj )−F (Li , ω )−F (Lj , ω)+F (ω, ω 0 )p2 (1−F (Li , ω))(1−F (Lj , ω 0 ))0 ≤ αiω ≤ C for 1 ≤ i ≤ m, ∀ω ∈ Ω, ω 6= Li . (5)×アプローチの第二段階においては，テキスト・ベク
トル空間 Rn から F-space HF への線形写像 W のうX

s.t.に位置し，かつ，（２）Li 以外の間違ったラベリング ω

式（5）は式（4）と異なり，φF を含んでおらず，直接との境界との間にできるだけ大きなマージン（h· · ·i で計算可能な量だけで構成されている．

表される量）を持つような写像を求める．
（図 1）

MML によるテキスト x のラベリングは，W により写像された点に最も近いラベリング L を選びだすこと最大マージンラベリング法（Maximal Margin La-で行われる．すなわち，式（4）の解 W ，もしくは式

beling，MML） 線形写像 W : Rn 7→ HF で，次の（5）の解 αiω を用いて

2 紙面の都合上，本稿では証明についての詳細は記載しない．基
本的には（１）F (A, B) を要素とする行列 F の大きさは高々有限であり，その固有値は有限の最小値を持つ，（２）適当な正定数倍した単位行列を F に加えた行列は，正定値行列となる，（３）その行列要素が内積の値と一致するベクトル空間 HF が存在する [6]，という三段階で証明される．

max hW x, φF (L)iFL∈Ω= maxL∈ΩmX

X

i=1 ω∈Ω,ω6=Liαiω (x·xi )F (L, Li )−F (L, ω)× p2(1−F (Li , ω))

0.78

(6)

0.76の解として求めることができる．

F−measure

0.74
0.72

4

実験

0.7

提案手法 MML を，医学生物学文献 [4] と Web ペー

0.68

ジ [3] のラベリングに適用し，性能評価をおこなった．

0.66

また，同一のデータを用いて，SVM および最近傍法に0.6450

より各ラベルの有無を判別する方法も適用し，MMLと比較した．各学習手法の実験時に使用したパラメー

MML
SVM
3NN
5NN
100150200
Number of Training Samples

250

タは次の通りである．

MML ペナルティC は１とした．
SVM [7, 8] を参考に，正例と負例とで異なるペナルテ
C+m+ィC+ , C− を使用し，C− = 1, C−=m（m+(−)−は正（負）例の数）とした．

図 2: 全てのテストデータを用いた結果（Bio データ）．
横軸：訓練データ数，縦軸：平均Ｆ値．図中，３（５）─ＮＮ は，近傍事例数を３および５とした最近傍法．
MML
SVM
3NN
5NN

0.8

最近傍法 近傍事例の数を３および５とした．

示す．

0.6

F−measure

表 1 に使用した文書集合に関する基本的な情報を

0.4

4.1

医学生物学文献のラベリング

0.2

3

Tingaud は，PubMed に登録されている論文概要のうち，酵母に関する約２０００件に対して，酵母遺伝子の発現形態や機能に関する１１の GO コード [9] をラベリングするという実験をおこなった [4]．以下，この Tingaud が用いたデータを「Bio データ」と呼ぶ．
我々は，Bio データの中からランダムに５０／１００／１５０／２００／２５０文書を取り出し訓練デー
タとし，残った中からランダムに取り出した５００文書をテストデータとし，実験をおこなった．なお，各手法の評価尺度はテストデータにおける平均Ｆ値とし，データの偏りによる影響を減らすために，全ての手順を１０回繰り返した結果をさらに平均した．
文書のベクトル化は，TF×IDF により各単語の重みを決定したのち，長さが１になるように正規化した．
図 2 に全てのテストデータを用いた場合の結果を示す．全ての訓練データ数において，提案手法 MML が他の手法を大きく上回る結果が得られた．また，SVMは比較的データ数の多い場合に精度が高く，逆に，最近傍法はデータ数の少ない場合に高精度という傾向も見られた．
3 http://www.ncbi.nlm.nih.gov/PubMed

0

Ar Bu Co Ed En He Rc Rf Si SS SC
Dataset

図 3: Ｗｅｂページのラベリング実験結果．データセッ
トの略称は表 1 を参照．

4.2

Ｗｅｂページのラベリング

上田は，検索エンジンのディレクトリサービスからリンクを辿って収集した Web ページを用いて，各ページが割り当てられたサブカテゴリ4 をラベリングするという実験をおこなった [3]．上田の用いたデータでは，ラベルとなるサブカテゴリ数が２０〜４０程度あったが，本実験では，計算時間の都合上，各データセットごとに出現頻度の多い１０個のサブカテゴリについてラベリングをおこなった．以下，このデータを「WWWデータ」と呼ぶ．
4 トップカテゴリに関しては多重性が少なかったため，トップカテゴリごとに別のデータセットとし，階層が一つ下のサブカテゴリをラベリングすることがタスクとされている．

データセット名

語彙数

(略称)

総ラベル組合せ数(訓練データに非出現)文書あたりのラベル数分布 (%)

0123≥4

医学生物学文献 (Bio)11,70182 (6.5–16.8%)

059.9

23.7

9.3

7.1

Web ページ (WWW)
Arts & Humanities (Ar)Business & Economy (Bu)Computers & Internet (Co)
Education (Ed)Entertainment (En)
Health (He)Recreation (Rc)
Reference (Rf)
Science (Si)Social Science (SS)Society & Culture (SC)21,45819,29828,271
23,89428,55025,166
26,68934,54433,931
39,74428,947133 (10.3%)
50 (3.1%)
62 (4.1%)
116 (8.5%)
88 (6.6%)
83 (5.4%)
98 (7.5%)
55 (2.8%)
76 (5.5%)
67 (5.3%)
143 (10.5%)

7.9
2.6
7.6
6.3
2.5
2.2
7.5
9.4
16.9
6.8
9.4

61.1
61.2
68.1
62.1
75.3
57.1
75.6
81.7
66.2
78.5
62.0

23.4
27.2
19.3
23.6
17.6
32.0
14.1
8.4
14.1
12.7
20.5

6.1
7.9
4.4
6.3
3.3
6.7
2.2
0.5
2.3
1.7
5.5

1.7
1.2
0.7
1.9
1.4
2.1
0.6
0.1
0.7
0.5
2.8

表 1: 実験で用いた文書集合に関する情報．
実験は，各データセットごとに，ランダムに取り出した２５０ページを訓練データ，２０００ページをテストデータとし，平均Ｆ値を計算した．また，データによる偏りを減らすために，実験を５回繰り返しその平均を取った．
文書ベクトルは [3] と同様に，単語の出現頻度を重みとし，長さが１になるように正規化したものを用いた．
図 3 に実験結果を示す．Bio データと比べると差は顕著ではないが，全てのテストデータで評価した場合，１１データセット中９セットで MML が最も良い性能を示した．
（残り２セットでは，SVM が最も良かった．
）

参考文献[1] 永田昌明 and 平博順. テキスト分類 ─ 学習理論の「見本市」─、. 情報処理, 21(1), 2001.
[2] Robert E. Schapire and Yoram Singer. BoosTexter: A boosting-based system for text categorization. Machine Learning, 39(2/3):135–168, 2000.
[3] Naonori Ueda and Kazumi Saito. Single-shot detection of multiple categories of text using parametric mixture models. In Proc. of the 8th ACM
SIGKDD International Conference on Knowledge
Discovery and Data Mining, pages 626–631, 2002.

[4] Frédéric Tingaud, Tomonori Izumitani, Hirotoshi Taira, and Eisaku Maeda. Classifying genes
into gene otologoy categories using text-based supervised learning methods. In Proc. of European Conference on Computational Biology 2003,
pages 81–82, 2003.
[5] 北研二, 津田和彦, and 獅々堀正幹. 情報検索アルゴリズム, chapter 2. 共立出版, 2002.
[6] Klaus-Robert Müller, Sebastian Mika, GunnarRätsch, Koji Tsuda, and Bernhard Schölkopf.
An introduction to kernel-based learning algorithms. IEEE Transactions on Neural Networks,12(2):181–201, 2001.
[7] 平博順, 向内隆文, and 春野雅彦. Support vector
machine によるテキスト分類. In 情報処理学会研究報告, volume 98-NL-128-24, pages 173–180, 1998.
[8] Katharina Morik, Peter Brockhausen, andThorsten Joachims. Combining statistical learning with a knowledge-based approach - a casestudy in intensive care monitoring. In Proc. of the
16th International Conference on Machine Learning, pages 268–277, 1999.
[9] The Gene Ontology Consortium. Gene ontlogy:
Tool for the unification of biology. Nature Genetics, 25(1):25–29, 2000.