DEIM Forum 2017 F6-5

文脈誘導型ランキング学習加藤誠†

内田 臣了†

Wiradee

Imrattanatrai†

山本 岳洋†

大島 裕明†

田中 克己†† 京都大学大学院情報学研究科 〒 606–8501 京都府京都市左京区吉田本町
E-mail: †{kato,uchida,wiradee,tyamamot,ohshima,tanaka}@dl.kuis.kyoto-u.ac.jp
あらまし 本論文では，順序付けられた一部のエンティティを訓練データ，エンティティの数値属性を特徴として線形関数を学習することで，エンティティのランキングを行う問題に取り組む．例えば，f (Entity) = +0.5(GDP) − 0.8(
自殺者数 ) という関数を「幸福度」によって順序づけられたエンティティから学習する．この問題では訓練データの数が非常に少ないため，Web 上に存在する大量の「文脈」による補助を受けて学習を行う機械学習手法，文脈誘導型学
習を本論文では提案する．実験では 3 クラスのエンティティについて 158 個の様々な順序によるランキングを行った．
実験結果から，既存のランキング学習手法よりも高い精度が文脈誘導型学習によって得られることが明らかとなった．
キーワード

ランキング学習，エンティティランキング，Web マイニング

1. は じ め に与えられた時，f (Entity) = +0.5(GDP) − 0.8( 自殺者数 ) という線形関数を学習することができる．

エンティティの順序は人気の高いコンテンツであり，多くのこの問題の主な課題の 1 つは，訓練データが不足しているこ

Web サイトで紹介されている．例えば，国，都市，企業，有とである．多くの Web サイトでは，すべてのエンティティの名人，および，製品などが，居住性，革新性，美しさ，性能な順序は記述されてはいない．さらに，一部のエンティティクラ

どのさまざまな基準によって順序づけられている．順序は比較

スでは，すべてのエンティティの順序が記述されていたとして文（例えば， “レオナルド ディカプリオはブラッド ピットよりも訓練データのサイズは十分ではない（たとえば，日本の都道も背が高い”）や，最上級（例えば，“東京は最も物価の高い都

府県数は 47 であり，アメリカの州の数は 50 である）．数値属

市である”），ランキング（例えば，“1 位：デンマーク，2 位：性の数は，通常，Web 上で順序づけられたエンティティの数よ

スイス，3 位：アイスランド”）などの形式で表現されている．

りもはるかに多いので，エンティティの順序を学習する際に，人々はそのようなエンティティの順序を意思決定，比較，計画

深刻な過学習の問題が起こりうる．

などに利用する．

この本質的な問題に対処するために，我々は文脈誘導型学習

順序づけの基準の詳細は，場合によっては正確かつ客観的にと呼ばれる学習方法を提案する．文脈誘導型学習は，順序づけ記述されているが，省略されたり基準が主観的である場合もあられたエンティティだけでなく，各特徴の重みを学習するためる．例えば，デンマークはいくつかのウェブサイトで最も幸せに順序基準と属性に関する文脈を利用する．文脈は追加の情な国として紹介されているが詳細な証拠が提示されていない場

報をモデルに与え，過学習を防止して学習を正しい方向に誘合も多い．その根拠は，国民の自己申告，他の国の評判，ある導する．例えば， “幸福度” という基準に関する線形関数の，いは，GDP や自殺者数などの客観的尺度かもしれない．不確“GDP” という特徴に対する重みは，（デンマーク，スイス，ア

かな証拠だけでそのような知識を獲得することは，偏見やステイスランド）というエンティティ列だけでなく，“GDP は幸レオタイプにつながる可能性がある．

福のための重要な要素である” や “GDP が向上すれば幸福度

本論文では，部分的に観測された順序を訓練データとして，も改善する”，といった「幸福」と「GDP」の文脈（「幸福」とエンティティの数値属性を特徴として使用することで，エン「GDP」の関係について記述された文や文書）によっても推測

ティティの順序を学習する方法を提案する．学習されたモデル

されることになる．文脈誘導型学習は，文脈に対するアノテー

によって，Web 上の順序を説明することが可能であり，また，ションを必要とせず，代わりに，文脈と関数 f 中の重みの関係学習に使用されていない他のエンティティをランキングするこを学習するために，複数の順序を同時に学習する．

とも可能である．順序付けは数値属性の線形関数 f によって表

我々の知る限りにおいて，文脈誘導型学習は，機械学習におすことができると仮定する．これは，主にユーザへの説明能力

いて「ラベル基準」と特徴の文脈を直接活用する最初の試みでが高く，現実世界における順序の大部分は，いくつかの尺度をある（ラベル基準とはラベル付けの基準を表すテキストのこと

線形結合することによって求められるという事実があるためでであり，エンティティランキングの問題における順序基準に対ある．例えば，「幸福度」という「順序基準」によって順序づけ応する）．文脈誘導型学習は，ラベル基準と特徴の関係が特定られた（デンマーク，スイス，アイスランド）というエンティのコーパスに記述されてれば，順位付けだけでなく分類や回帰

ティ列と「GDP」，「国土面積」，「自殺者数」という数値属性がの問題にも適用することが可能である．

実験では，国，都道府県，カメラの 3 つのエンティティクラ

という関係と “Microsoft” というエンティティを入力し “Billスを対象とし 158 種類の順序を学習した．訓練された順序の精

Gates” を得ることができる．彼らはあるエンティティ対の関係

度を測定し，与えられた順序が学習されたモデルによってどれに関する検索スニペットから得られた特徴を用いて，訓練クエだけ説明可能であるかを評価した．実験の結果，文脈誘導型学

リとラベル付けされたエンティティを元に各関係についてラン

習は既存のランキング学習手法よりも統計的有意に高い精度をキングを学習した．この研究と我々の研究は共に文脈（または示した．

検索スニペット）を用いてランキング学習を行うという点ではこの論文における我々の貢献を以下に示す：(1) 数値属性を特徴とした，エンティティの順位付けを学習する問題を提案し類似するが，我々のモデルは主にエンティティの属性に基づくものであり，エンティティ対の文脈は用いていない．

た．これによって，Web 上の順序を正確に理解し，さまざまな

我々のタスクに類似した自然言語処理タスクもいくつか提基準でエンティティを順序付けすることが可能である．
（2）文案されている．Iwanari らは，与えられた形容詞に基づいてエ脈誘導型学習を提案した．これは，過学習を防止するためにランティティを順序づける問題に取り組んでいる [21]．手法はテ

ベル基準および特徴の文脈を利用する一般的な機械学習モデル

キストから得られたいくつかの根拠に基づいており，エンティ

である．
（3）幅広い順序に対する実験を行い，エンティティのティと形容詞の共起やエンティティと形容詞の依存関係，直喩，

順序づけタスクにおいて文脈誘導型学習の有効性を示した．

比較文などが用いられている．このタスクには既存のランキン

本論文の構成は以下の通りである．2 節ではエンティティの

グ学習および回帰モデルが用いられている．ある順序基準に基ランキングに関する関連研究，および，文脈誘導型学習と他のづいてエンティティをランキングを行うという点でこのタスク

機械学習手法との関係について述べる．3 節では問題設定を説は我々のタスクと類似する．彼らの手法は順序基準とエンティ

明し，文脈誘導型学習，および．その主問題への適用方法につティの文脈を利用するが，我々の手法では順序基準とエンティいて述べる．4 節では実験結果を示す．最後に，5 節では今後

ティの「属性」の文脈を利用している．また，本論文ではこのの課題と共に本論文の結論を述べる．

タスクについて効果的な学習手法についても提案を行ってい

2. 関 連 研 究
本節では，エンティティのランキングに関する関連研究，および，文脈誘導型学習と他の機械学習手法，特にマルチタスク
学習との関係について述べる．

2. 1 エンティティランキング

る．エンティティの数値的な属性を抽出する研究も存在するが，我々のタスクでの順序基準は多くの場合に定量化することが困難であり，これらの研究で提案される手法では推定できないと思われる [13, 27, 31]．

2. 2 マルチタスク学習
文脈誘導型学習の重要な特徴を以下に要約する：(1) 関数 f

エンティティランキングは INEX や TREC のいくつかのトの重みはラベルだけでなく，ラベル基準と特徴の文脈に基づいラックで取り組まれてきている．INEX の Entity Ranking トて学習される，また，(2) 文脈と関数 f 中の重みの関係を学習

ラックでは，エンティティランキングとエンティティリスト補するために，複数の関数が同時に学習される．以下では，いく完の 2 つのタスクが提案された [14–16]．エンティティランキン

つかの機械学習手法について述べ文脈誘導型学習との関連につグタスクは，与えられたクエリに対して適合するエンティティ

いて議論する．

を発見するタスクであり，他方，エンティティリスト補完タス

マルチタスク学習とは複数のタスクを同時に学習すること

クでは与えられたエンティティ例に関連するエンティティを発によって個々のタスクの学習を改善する方法である [10]．文脈見するタスクであった．TREC のエンティティトラックでは，誘導型学習はマルチタスク学習の一種であると考えられる．

あるエンティティ例と発見対象のエンティティタイプ，それら

Evgeniou と Pontil によって提案された正則化マルチタスク学の関係性が与えられたときに関連するエンティティを取得する，

習は複数のタスクにおける関数の重みが似ていることを仮定し関連エンティティ発見タスクが提案された [2–4]．これらのタスている [17]．後に述べるように，彼らのモデルは我々のモデル

クでは，発見されたエンティティが与えられたエンティティ例の特殊な場合であり，すべての文脈が同じである場合に等価なとの関連性に基づいて順序づけされることだけが求められ，関モデルとなる．また，共通の事前分布から重みが生成されるこ

連エンティティに対して様々な順序付けを行うことまでは求めとを仮定するモデルもある [12, 26, 34]．Argyriou らは重みが複られていない．

数のタスクに共通する低次の部分空間において表現できること

エンティティリスト補完タスクと関連エンティティ発見タスを仮定している [1]．これらのように全てのタスクが関連すると

クとは別に，エンティティのランキング学習に関する関連研究仮定する研究とは対照的に，いくつかの研究ではどのタスクがも存在する．Kang らは与えられたクエリに関連するエンティ

関連し，似た重みを共有すべきか選択するようなモデルを提案

ティを発見するために，決定木ブースティングに基づくランキしている [22, 24]．同様に，文脈誘導型学習はタスク間の類似性

ングアルゴリズムを用いている [23]．Tran らはイベントのタイを文脈を用いることで暗に推定し，似たようなタスクに対して

ムライン要約のために主要度と情報量に基づいてエンティティ

似たような重みを推定する傾向にある．文脈誘導型学習と他のをランキングする手法を提案している [32]．Zhou らは与えられマルチタスク学習手法の興味深い違いは，いずれのタスクも類たエンティティと特定の関係にあるようなエンティティを発見す

似しない場合においても文脈誘導型学習は適用可能であるといる問題に取り組んでいる [35]．例えば，ユーザは “FounderOf”

う点である．文脈誘導型学習は複数のタスク間でいくつかの文

脈が類似することだけを仮定する．したがって，文脈誘導型学がしばしば小さいことである．例えば，我々の実験において習の適用範囲は既存のマルチタスク学習が対象とする問題に限「国」では M = 83，「都道府県」では M = 137 である．10 件以らない．

下のエンティティしかランキングされていない場合，訓練デー

最後に，文脈誘導型学習（Context-guided Learning，CGL）

タとして我々が得られるのは高々45 個のエンティティペアであと似た名前を持つ機械学習手法との差違を明確にする．文脈依り，これらのクラスにおいては学習に十分な量であるとは考え

存型学習（Context-sensitive Learning）はしばしば特徴の文

にくい．さらに，幅広い順序を扱うためには M はできるだけ脈（例えば，ピクセルを特徴とする場合の周辺ピクセル [5] や大きい方が良い．したがって，訓練データの不足から起こりう

単語を特徴とする場合の共起単語 [11] など）を用いる手法を指る過学習を防ぐためになんらかの手段が必要となる．

す．他の場合，与えられたデータに対して選択的にモデルを用′本研究における主なアイデアは wk の学習のために，O⪯kいる機械学習手法 [30] や直前・直後のデータを予測に用いる手以外のデータを活用することである．我々の問題の特徴，また法 [28] を文脈依存型学習と呼ぶ．これらの手法は主に文脈を追は，仮定として，順序基準と属性に対するテキスト表現が利用

加の特徴として用いることに焦点を当てており，文脈誘導型学可能であることが挙げられる．そのため，順序基準と属性に関習はモデルを変えることなく，文脈を用いてモデルの学習を改する文脈を活用することによって，各属性に対する重みをおお善する手法である．さらに，文脈誘導型学習で用いられる文脈

よそ推定することができるのではないかと我々は考えた．例えは特徴に関するものではなく，ラベル基準と特徴に関するもの

ば，“GDP が向上すれば幸福度も改善する” という文脈からである．

は「GDP」に対する正の重みを，“自殺者数が増えれば幸福度

3. 手が低下する” という文脈からは「自殺者数」に対する負の重み法を推定する．一方で，ある順序基準と属性の対に対して，もし本節では，まず部分的に観測されたエンティティの順序から，

文脈が得られなかった場合には，その属性に対する重みは 0 に

エンティティの順序を数値属性に基づいて学習する問題につい近いという推測をする．これらのアイデアは次節で説明する文て説明を行う．それから，文脈誘導型学習を導入し，その主問

脈誘導型学習によって具体化される．

3. 2 文脈誘導型学習

題への適用について述べる．

3. 1 問 題 設 定

本節ではラベル基準と特徴の文脈を活用する文脈誘導型学習

E をあるクラスのエンティティ集合とし，エンティティ順序という学習手法を提案する．まず，分類問題に対する文脈誘導⪯k を E 上の全順序として定義する．各順序は順序の基準を示

型学習を導入し，次にランキング問題に対する拡張を行う．

す順序基準 lk を持つ．例えば，順序基準として「住みやすさ」，

入 力 は ベ ク ト ル と ラ ベ ル の ペ ア の 集 合 の 集 合 で あ る：N

「革新性」，「美しさ」，「性能」などが挙げられる．順序付き集合Mk
D = {Dk }K
k=1 ．ただし， Dk = {(xk,i , yk,i )}i=1 ，xk,i ∈ R ,O⪯k (⊂ E × E) は ei ⪯k ej を満たす全てのエンティティ対のyk,i ∈ {−1, +1}，そして，K はラベル基準の総数である．ラ集合 (ei , ej ) ∈ E × E である．Web 上においてエンティティ順

ベル基準 lk はラベル yk,i を決定するためのテキスト表現であ序はこれら順序付き集合の部分集合によって表現されることがる．例えば，xk,i が都市の特徴を表し，都市が大都市であれ多い．従って，エンティティ順序の学習のために観測・利用可能

ば yk,i = +1，そうでなければ yk,i = −1 とする．この場合，′⊂ O⪯k である．例えば， “レオナルド ディカプリ
なのは O⪯k′= {(“ブオはブラッド ピットよりも背が高い” という文は O⪯
kラベル基準 lk は「大都市」となる．例えば，xk,i が文書の特徴を表し，文書がスパムであれば yk,i = +1，そうでなければ

ラッド ピット”, “レオナルド ディカプリオ”)} を示し，“1 位：

yk,i = −1 とする．この場合，ラベル基準 lk は「スパム」となデンマーク，2 位：スイス，3 位：アイスランド” というランキ

る．ベクトルの d 次元目の値はある特徴に対応し，その特徴の′= {(“スイス”, “デンマーク”), (“アイスランド”,
ングは O⪯k

名前を ad とする．例えば，特徴名として「人口」や「面積」，“デンマーク”), (“アイスランド”, “スイス”)} を示す．

「リンク数」などが考えられる．

我々の主目的は，各エンティティ⪯k に対して順序部分的に′観測された順序付き集合 O⪯から線形関数 fk (ei ) = wkT ei をk

学習することである．ただし，ei はエンティティei ∈ E の数
値属性を表す M 次元ベクトルであり，このベクトルの d 次元
目はエンティティの ad という属性を表す．我々はこの関数 fkがエンティティ順序 ⪯k を保つことを期待する：つまり，任意

文脈誘導型学習を適用するための要件は以下の 3 つである：（ 1 ） ラベル基準 lk が言語で表現されている．
（ 2 ） 特徴 A = {ad }M
d=1 が言語で表現されている．
（ 3 ） ラベル基準と特徴の関係に関する文脈を含むコーパスが存在する．

の ei , ej ∈ E に対して ei ⪯k ej ⇒ fk (ei ) <= fk (ej ) を満たすこ

マルチタスク学習問題とは異なり，文脈誘導型学習ではタスクとを期待する．学習された関数 fk を用いることで順序基準 lkの類似性を仮定しない（または，文脈誘導型学習の言葉で言えによってエンティティを順位付けすることが可能であり，学習ば，ラベル基準が類似する必要がない）．また，全てのラベルされた関数中において 0 でない重みを持つ数値属性によって順基準および特徴が言語で表現されている必要もない．

序基準を説明することができる．

分類問題は，各ラベル基準 k = 1, . . . , K に対して fk (xk,i ) ≃先に述べたように，この問題の主となる課題は訓練データのyk,i であるような関数 fk を学習する問題であると定式化でき′不足である．より正確には，数値属性の数 M と比較して |O⪯|k

る．文脈誘導型学習によってこの問題を解くために，我々は線形関数 fk (xk,i ) = wkT xk,i を用いる．ラベル基準 lk と特徴

ad ∈ A の文脈を ck,d とし，以下のようにして wk を推定するために文脈を用いることができる：

wk,d = uT ϕ(ck,d ) + vk,d ,(1)

ただし，wk,d は wk の d 次元目の値，ϕ は文脈からベクトルへの特徴写像関数，u はラベル基準に依存しない重みベクトルでF (x, k) = wT ψ(x, k)
ただし，
√

w=(

(6)

K T T
T T
u , v1 , . . . , vK
) ,
c

かつ，

√

ψ(x, k) = (ある．上記の式は，あるラベル基準 lk と特徴 ad の重みがそれ(7)c(Φk x)T , 0T , . . . , 0T , xT , 0T , . . . , 0T )T (, 8)| {z }| {z }
K
k−1

K−kらの文脈である ck,d と切片 vk,d から推定されることを意味すである．ここで，ψ は特徴写像関数，0 は要素がすべて 0 である．また，我々は vk,d が「大きくない」ことを，つまり，wk,dるような M 次元ベクトルである．

Tが vk,d のみによって決定されるのでなく，u ϕ(ck,d ) によっても決定されることを期待する．式 1 は正則化マルチタスク学
習 [17] における wk,d = zd + vk,d （zd は複数タスクに共通の重み）を一般形である．もし全ての文脈が同じであれば式 1 は正則化マルチタスク学習に還元される．もし 2 つのラベル基準の文脈が似る，つまり，ラベル基準が類似するのであれば，wk,dはそれらのラベル基準に対して似た値となる．この性質はいく
つかのマルチタスク学習手法に似ている [22, 24]．
本論文ではサポートベクターマシン（SVM）と正則化マルチタスク学習 [17] に似た，正則化によるアプローチによって，文脈を含む線形関数を学習する．重みを学習するための最適化問

このとき，Problem 1 は以下に示すように一般的な SVM の問題へと帰着できる.

Theorem 1. The optimization of Problem 1 is equivalent tosolving the following problem:
Problem 2. Given D = {((xi , ki ), yi )}N
i=1 where N =
}
∑K
∪K {
k=1 Nk such that D =k=1 ((xk,i , k), yk,i ) (xk,i , yk,i ) ∈ Dk ,
N
∑
1
ξi ,
min ∥w∥2 + C ′w,ξi 2i=1

subject, for i = 1, . . . , N , to the constraints thatyi wT ψ(xi , ki ) >= 1 − ξi ,題を以下に示す：

ξi >
= 0,

Problem 1.
∑∑c ∑min ∥u∥2 +∥vk ∥2 + C
ξk,i ,
u,vk ,ξk,i
K
i=1
K

K

k=1

k=1

(10)
(11)

where C ′ = CKand ξi is a slack variable for ((xi , ki ), yi ) ∈
2c

Nk

(2)

subject, for k = 1, . . . , K and i = 1, . . . , Nk , to the constraints thatyk,i wkT xk,i(9)D.
Proof. i =∑k−1

k′ =1 Nk′

+ i′ として，Problem 2 の ξi に ξk,i′を，xi に xk,i′ を，yi に yk,i′ を代入すれば，Problem 1 を得られる．

>
= 1 − ξk,i ,ξk,i >
= 0,

(3)
(4)

Problem 2 は一般的な SVM の問題であるため，以下に示す
ように一般的な SVM の双対問題を利用することで Problem 1

where c and C are parameters, vk = (vk,1 , . . . , vk,M ), wk =を解くことができる．

ΦTk u + vk , and Φk = (ϕ(ck,1 ), . . . , ϕ(ck,M )).

Theorem 2. Define a kernel function Kk,k′ as:

スラック変数 ξk,i は訓練データにおける線形関数の誤差を表し，他の 2 つの項は u と vk に対する正則化項である．パラ
メータ c と C はそれぞれ文脈のモデルに対する影響と訓練デー
タにおける誤差への感度を調節する役割を持つ．パラメータ c
に対する高い値は文脈の影響を高め，一方でパラメータ C に対する高い値は訓練データにおける誤分類を許容しにくくさせ

Kk,k′ (xi , xi′ ) = ψ(xi , k)T ψ(xi′ , k′ ),c T T=xi (Φk Φk′ + δk,k′ I)xi′ ,K
where δk,k′ = 1 if k = k′ , and 0, otherwise.
The dual problem of Problem 2 is given by:
Problem 3.

る．関数 fk は同時に学習するのではなく，個別に学習することも可能ではある．しかし，その場合，利用可能なデータ量を

max
αi

N
∑

1∑∑
αi yi αi yi′ Kki ,ki′ (xi , xi′ ),2 i=1 ′
N

αi −

i=1

を示す．このために，まず関数 fk (k = 1, . . . , K) を要約する
ような，学習されるべき 1 つの関数を以下のように定義する：

F (x, k) = fk (x)(5)

この関数 F : RM × {1, . . . , K} → R は以下の線形関数として表現することができる：

N

(13)

i =1

増やすことなく，単に推定すべき重みの数を増加させてしまう．
次に，Problem 1 が一般的な SVM と同じように解けること(12)

subject, for i = 1, . . . , N , to the constraint that′0<= αi <=C.

(14)

If αi∗ is a solution for the problem above, then the solution
to Problem 1 is given byfk∗ (xk,i ) =

N
∑
i′ =1

αi∗′ yi′ Kki′ ,k (xi′ , xk,i ).

(15)上記の双対問題を解くためには，N 個の訓練データを用いを学習するものとする．

て通常の SVM を解くのと同じ計算量が必要となる（N は全て

以下のように Dk を再定義することによって，ランキンのラベル基準に対するベクトルとラベルのペアの総数であり，∑
N = K
k=1 Nk である）．例えば，n 個の訓練データに対してグ問題が分類問題に帰着できることは明らかである：Dk′ ={}(xk,j − xk,i , 1) (xk,i , xk,j ) ∈ Dk ．これは，fk (xk,j −xk,i ) =通常の SVM を解くのに O(n3 ) の計算量が必要であれば，上fk (xk,j ) − fk (xk,i ) であるためである．

記の双対問題を解くのにかかる計算量は O(N 3 ) となる．一方，

3.1 節にて説明したエンティティランキング問題への適用は，通常の分類問題のように異なるラベル基準に対して別々の関数∑
3を学習するような場合には，O( K
k=1 Nk ) の計算量のみが必要′
訓練データとして O⪯
中のエンティティペアのベクトルを用k{}′いれば良い．すなわち，Dk = (ei , ej )|(ei , ej ) ∈ O⪯とする
kとなる．本論文中で行う実験ではラベル基準の数が 40 から 64

ことで，エンティティランキング問題へと適用できる．

程度であるため計算量が大きな問題とはならないが，特にラベ

3. 4 文脈モデル

ル基準が多いとき，計算量は文脈誘導型学習の欠点となり得る．

エンティティランキング問題に対する学習方法は既に述べた

我々の問題は一般的な SVM の問題に還元できるため，SVM

ため，ここでは学習に用いられる文脈モデルについて説明する．

と同様にカーネルによって非線形関数を扱うことができる．モ

文脈はあるラベル基準と特徴に関する文や文書の集合とするこデルの性質上，分類のための線形関数 fk は非線形関数にするとができる．文脈を公開されているコーパスから得ることもでことはできないが，文脈に基づく重みの推定（式 1 参照）のた

きれば，代わりに Web をコーパスとして用いそこから得るこめに非線形関数を用いることが可能である．Problem 3 にて見ともできる．Web は巨大なコーパスであり，また，ラベル基準

られるように，最適な関数を求めるためには文脈から得られると特徴から適切なクエリを作ることができれば効率よくアクセベクトル ϕ(ck,d ) のカーネル関数のみが必要であることがわかスすることも可能である．そのため，本研究では，Web 検索結る．したがって，特徴写像関数 ϕ をここで ϕ : C → H と定義

果から得られた文を用いて文脈を表現する方法について述べる．

できる．ただし，C は文脈集合，H は可分な一般抽象ヒルベル

ラベル基準 lk と特徴 ad が与えられた時，まず我々は lk とト空間である．この特徴写像関数 ϕ に対応するカーネルは以下

ad を AND 演算子で組み合わせたクエリを生成し，ある Webのように定義される：

検索エンジンへそのクエリを入力し上位 N (c) 件の検索結果をκ(ck,d , ck′ ,d′ ) = ⟨ϕ(ck,d ), ϕ(ck′ ,d′ )⟩H ,(16)

ただし，⟨·, ·⟩H は H 中での内積を表す．

果のスニペットを文に分割し，ラベル基準 lk と特徴 ad の両方を含む文を抽出した．これらの文集合を以下では Sk,d と表記

Problem 3 中のカーネル関数 Kk,k′ を以下のように置き換する．
ラベル基準と特徴の文脈を表現する方法として 2 つの基本的える：

Kk,k′ (xi , xi′ ) =得る（実験においては N (c) = 500 とした）．それから，検索結c Txi (Φk,k′ + δk,k′ I)xi′ ,
K

(17)

′

な方法を提案する．1 つ目は TF-IDF 重み付け法によるベクト
ル表現であり，2 つ目は文の分散表現である [25]．両方法とも

ここで， Φk,k′ の (d, d ) 要素は κ(ck,d , ck′ ,d′ ) である．上記のベクトルによって文脈を表現するが，先に述べたとおり，より置き換えによって，カーネル κ の計算だけが必要となり，ϕ に

複雑な表現方法も利用可能である．以下ではこれらの方法の詳よる特徴写像の計算が不要となる．

細について簡潔に説明する．以下で用いられるいくつかの記号

文脈誘導型学習におけるカーネルの利用によって，幅広い文

は，前の節での定義と異なった定義が与えられる．

脈の表現を行うことが可能となる．文脈のカーネル関数 κ が適

語彙の集合を W とする．このとき，文集合 Sk,d 中の各文

切に設計されている限り，ベクトル，ベクトル集合，グラフな

si はベクトル vi によって表現され，vi の j 次元目の値は以

ど様々な文脈表現が可能である．

下のように定義される：vi,j = tf(si , wj ) log(n/df(wj ))．ただ3. 3 文脈誘導型ランキング学習

し，tf(si , wj ) は si 中に現れる語 wj ∈ W の頻度，df(wj ) は

ここでは，文脈誘導型学習をランキング問題へと拡張し，エSk,d (k = 1, . . . K; d = 1, . . . , M ) 中で wj を含む文の数である．

ンティティランキングの問題に適用する方法について説明する．

定数 n は Sk,d (k = 1, . . . K; d = 1, . . . , M ) 中の文の数を表す．

M
ランキング問題の入力は D = {Dk }K
k=1 であり，Dk ⊂=R ×

文脈 ck,d は文集合 Sk,d のベクトルの平均によって表すこと

R ，K は順序基準の数である．順序基準 lk は Dk の順序を決ができる．しかし，もしあるラベル基準と特徴のペアに対して定するためのテキスト表現であり，Dk において (xk,i , xk,j ) で少数の文しか得られない場合，それらのラベル基準と特徴にはあることは，xk,j が順序基準 lk の観点から xk,i に勝ることをあまり関係がない可能性が高い．つまり，wk,d ∼ 0 である可能示す．Dk のベクトルにおける d 次元目の値はある特徴と対応性が高い．これを実現するため，文集合 Sk,d のベクトルの平しており，その特徴の名前を ad とする．文脈誘導型ランキング

均へ文の数に基づきペナルティを与える．そのため，文脈 ck,d

学習の要件は，分類問題のための文脈誘導型学習と同じである．

は以下のように表現される：Mランキング問題は各順序基準 lk (k = 1, . . . , K) において，Dk
中の (xk,i , xk,j ) に対して fk (xk,j ) − fk (xk,i ) ≃ 1 となるよう

ck,d =

d(|Sk,d |) ∑vi ,|Sk,d | s ∈S
i

(18)

k,d

な関数 fk を学習することであると定式化できる．分類問題においても仮定されていたように，線形関数 fk (xk,i ) = wkT xk,i

ここで d(x) はペナルティ関数である．関数 d(x) は x = 0 のとき 0，x に対して単調増加し，x → ∞ のとき 1 に収束する
ことが望ましい．そのため，我々は d(x) = tanh(αx) をペナル

表1

各クラスの統計情報とエンティティ，エンティティ順序，および，
属性の例．
都道府県

ティ関数として用いた．ただし，α は関数の勾配を調整するパ国

カメラ

ラメータである（実験では α = 1.0 とした）．もしあるラベル# Entities

47

138

基準 lk と特徴 ad に対してわずかな文しか発見できなかった場# Orders

64

40

54

合，d(|Sk,d |) は ck,d のノルムを減少させるため，wk,d を 0 に# Entities / Order

13.3

17.7

14.4

# Attributes

137

83

16

近づけることができる．

(# Entities / Order)

0.097

0.213

0.900

もう一方の方法は文の分散表現を用いる方法である [25]．ある文集合が与えられた時，分散メモリモデルは文と前に出現す/ # Attributes
Entity examples

る T 語によって条件付けられた語の確率の平均を最大にする
ような語と文の分散表現を得る．本論文ではこの手法の詳細にAttribute examples

ついては割愛する．分散メモリモデルの中でも，語と文の分散表現の平均によって語の確率を計算する手法を用いて，文集合

Order examples

Sk,d 中の各文 si に対して，分散表現 vi を得ることができる．
あとは，式 18 と全く同じ方法により文脈 ck,d を表現するベク
トルを得られる．

149

東京

デンマーク

京都

アイスランド Nikon D3300

人口

旅行者数

解像度

犯罪率

自殺者数

重さ

魅力度

住みやすさ

持ち運びやすさ

豊かさ

幸福度

耐久性

EOS 5DSによって正規化を行った．
表 1 に統計情報とエンティティ，エンティティ順序，および，

上記で述べた 2 つの手法は異なる性質を持つ．TF-IDF 重み属性の例を示す．多くのエンティティ順序に対して，我々はす付け法によるベクトル表現は疎で，文脈に出現した語そのもの

べてのエンティティを含むようなランキングを見つけることがを表現することができる．対照的に，文の分散表現は密で，文できなかった．これは，それらのページが上位 1，3，5 件のみ

脈に出現した語そのものを保持することはできない．そのため，を紹介することが多かったためである．また，表中に示されて実験ではこれら 2 つの手法を比較する．

いる統計値の中で最も重要な値は属性数に対する 1 エンティ

4. 実

験

ティ順序あたりのエンティティ数の比率である（(# Entities /Order) / # Attributes）．この比率は全てのクラスで 1.0 以下
我々のタスクには公開されたデータセットが存在しないため，
まずデータセットの作成の概略と統計情報について説明する．
それからベースライン手法を含む実験設定について紹介し最後に実験結果を示す．

であり，カメラクラスが最も高く，都道府県クラスが最も低くなっている．

4. 2 実 験 設 定
我々は実験におけるベースライン手法として，文脈を用いない

4. 1 データセット

既存のランキング学習手法を用いた：(1) RankNet [6]: ニュー

Web や雑誌から自動，または，手動によって，3 クラスのエラルネットワークを用いクロスエントロピー損失を最適化するペンティティに対する様々なエンティティ順序を抽出した．これ

アワイズランキング手法，(2) RankBoost [18]: AdaBoost [19]ら 3 クラスは都道府県，国，カメラである．クラス選定は以下のペアワイズランキングへの応用，(3) LinearFeature [29]:の 4 つの理由に基づいた：(1) 順序基準と特徴に関する Web

座標上昇法によって最適化された線形特徴モデル，(4) Lamb-

ページの量，(2) エンティティ順序の種類数，(3) 数値属性のdaMART [33]: ランキング学習手法である LambdaRank [7]量，(4) 統計情報の多様性．

と決定木ブースティングモデルである MART [20] を組み合わ

都道府県と国に関してはエンティティ列を Web ページ中のせた手法，(5) ListNet [8]: ニューラルネットワークを用いたランキング（各エンティティが 1 位，2 位等に順位付けされてリストワイズランキング手法．我々は RankLib（注 2） での実装をいるコンテンツ）から自動的に抽出した．カメラに関しては，実験に用いた．なお，タスクが互いに関連しているという仮定

国内で発売されている 10 のカメラ雑誌からエンティティ順序をしなかったため，マルチタスク学習との比較は行わなかった．

を手動で抽出した．このような雑誌には，各カメラに様々な観構築したデータセットを用いた実験の手順を以下で述べる．各点から点数や順位が与えられているため，それらに基づいてエ

順序集合 O⪯k に対し，O⪯k に含まれるエンティティ集合 E を 1

ンティティ列を構築した．上記の結果として得られたエンティ

対 1 に分割し，これらを Etrain および Etest とした．訓練データ

ティ列はそれぞれエンティティペアに変換され，部分的に観測

は Otrain = {(ei , ej )|(ei , ej ) ∈ O⪯k ∧ ei ∈ Etrain ∧ ej ∈ Etrain }された順序集合 O⪯k を得た．要素数が 5 未満であった順序集であり，テストデータは Otest = O⪯k − Otrain とした．実合を除き，最終的に 158 のエンティティ順序を得た．

験でのタスクは，Otrain に基づいて順序モデルを学習し，各都道府県と国の数値属性は Web 上で公開されているものを(ei , ej ) ∈ Otest に対して ei と ej のどちらが上位に順序づけさ自動的に抽出し，カメラについては価格.com（注 1） のページよりれるかを予測する問題とした．この問題において，精度は正し

スペック情報などを抽出し数値属性とした．数値属性を抽出後く予測できたエンティティペア数と定義された．我々はあるクに，各属性ごとに [0, 1] に収まるよう各属性の最大値と最小値ラスにおけるエンティティ順序に対して，5 分割交差法を用い（注 1）：http://kakaku.com/（注 2）：https://sourceforge.net/p/lemur/wiki/RankLib/

Rate

表 2 各ランキング手法の精度 (± 標準誤差)．太字は各エンティティ−2

クラスでの最大の精度を表す．

LinearFeature

RankBoost [18]LinearFeature [29]LambdaMART [33]ListNet [8]CGL (TF-IDF, Linear)

CGL (TF-IDF, RBF)

CGL (Distributed, Linear)

CGL (Distributed, RBF)

カメラ

総合

0.482

0.478

0.530

0.497

(0.023)(0.025) (0.030)(0.015)

0.513

0.636

0.552

0.557

(0.028)(0.024) (0.036)(0.018)

0.566

0.670

0.614

0.609

(0.019)(0.024) (0.034)(0.015)

0.614

0.659

0.697

0.654

(0.021)(0.019) (0.024)(0.013)

0.559

0.518

0.504

0.530

(0.020)(0.022) (0.031)(0.014)

Country
Rank

RankNet [6]国Camera
Rank

都道府県

City
Rank

精度

−1

0

+1

+2

CGL

1

1

2

2

3

3

4

4

5

5

1

1

2

2

3

3

4

4

5

5

1

1

2

2

3

3

4

4

5

5
0%

20%

40%

60%

80%

100%

0%

20%

40%

60%

80%

100%

図1

最も絶対値の高い重みを持つ 5 つの属性の評価値の分布．

表 3 文脈誘導型学習によって学習された線形関数の例．最も絶対値の

0.661

0.716

0.823

0.730

(0.017)(0.022) (0.019)(0.012)

0.661

0.725

0.799

0.724

クラス

(0.019)(0.021) (0.019)(0.012)

都道府県

魅力度= +0.035 女性の平均寿命 −0.032 交通事故死者数 −0.031 人口／世帯数

都道府県

貯蓄額

= −0.174 最高気温

+0.160 健康寿命

+0.148 旅館数

0.646

0.701

0.798

0.712

国

評判

= +0.058 幸福度−0.057 難民申請数−0.045 自殺者数

国平和

= +0.170 穀物収穫量+0.166 GDP 成長率−0.126 自殺者数

(0.020)(0.023) (0.021)(0.013)カメラ

操作性= −0.240 重さ−0.213 高さ+0.133 シャッタースピード

0.661

0.731

0.804

0.728

(0.018)(0.022) (0.021)(0.013)

高い重みを持つ 3 つの属性のみを示している．
学習された線型モデルのユーザに対して提示した．この実験では学習された属性がどの程度順序を説明できるのかを理解することを目的としている．

て各手法の最適なパラメータを決定した．

ユーザは与えられた順序基準と属性の間に相関があるかどうか

文脈誘導型学習（CGL）では以下の設定を用いた．文脈モを，−2 から +2 までの 5 段階で評価した．我々は各順序基準

デルとして TF-IDF と Distributed (L = 400 の分散表現)と属性のペアに対して 5 名のユーザを割り当てた．最も精度のを用いた．パラメータ c と C は上述の交差法を用いて決定され高かった CGL (TF-IDF, Linear) とベースライン中で唯一線形た．式 16 中のカーネル κ として，線形カーネル (Linear) お関数を用いる LinearFeature が評価に選ばれた．

よび RBF カーネル (RBF) を採用し比較した．

図 1 に最も絶対値の高い重みを持つ 5 つの属性の評価値の4. 3 実 験 結 果

分布を示す．都道府県，国，カメラに対して，文脈誘導型学

表 2 に精度と標準誤差を示す．文脈誘導型学習（CGL）は習の平均評価値はそれぞれ，−0.455，−0.166，+0.581 であどの設定においてもベースライン手法を上回る精度を達成してり，LinearFeature の平均評価値はそれぞれ，−0.560，−0.204，

いる．文脈誘導型学習に基づいた手法の中で最も精度の高かっ+0.516 であった．これらの評価値は手法の精度と高い相関があた手法は CGL (TF-IDF, Linear) であり，次点は CGL (Dis-る．文脈誘導型学習はすべてのクラスにおいて LinearFeature

tributed, RBF) であった．最も精度の高いベースライン手法

よりも妥当な属性を発見できていたが，全てのクラスにおいてである LambdaMart からの総合的な精度改善は 11.6%であっその差はわずかである．都道府県と国における平均評価値は 0

た．ランダム化 Tukey HSD テスト [9]（注 3）（α = 0.01）によれ以下となっており，各属性の低い説明可能性を示唆している．

ば，CGL (TF-IDF, Linear) と全ベースライン手法との差は統

これは単に各属性が順序基準と相関があったものの，順序基準

計的有意であり，文脈誘導型学習に基づいた手法の中では統計に変化をもたらす要因として評価されなかったためではないか

的有意差は認められなかった．

と考えている．文脈誘導型学習はベースラインよりも精度が高クラスごとに見ると，都道府県，国，カメラクラスにおいて，いモデルを学習できたものの，与えられた順序基準に対して高CGL (TF-IDF, Linear) は LambdaMART の精度をそれぞれい説明可能性を持った属性を発見するのは未だ挑戦的な課題で8%，11%，18%改善した．我々は，事前に行った人工データであると言える．

の実験と文脈モデルに用いられた 1 属性当たりの文数がそれぞ

最後に，文脈誘導型学習によって学習された線形関数の例をれ 36.0，45.7，137 であったことから，文脈の質と量が文脈誘表 3 に示す．多くの属性はエンティティ順序を説明可能で影響

導型学習の効果を決定する主な要因ではないかと考えている．

を与えているように見える．一方，いくつかの属性はエンティ

我々は学習された関数内で用いられている属性の評価も行っ

ティ順序を説明するために適切でないように見えるが（例えば，た．最も絶対値の高い重みを持つ 5 つの属性をエンティティ順“魅力度” に対する “世帯当たりの人口” や “貯蓄額” に対する

序ごとにプールし，クラウドソーシングサービス Lancers（注 4）“最高気温”），データセット中ではエンティティ順序と高い相関を示している．これらは主観的評価では妥当でないと判断され（注 3）：http://www.f.waseda.jp/tetsuya/tools.html（注 4）：http://www.lancers.jp/

たものの，予測においては大きく貢献している属性の例である．

5. ま と め
本論文では，部分的に観測された順序を訓練データ，エンティ
ティの数値属性を特徴として線形関数を学習することで，エンティティの順序を学習する問題に取り組んだ．この問題では，訓練データの数が非常に少ないため，我々は文脈誘導型学習という機械学習手法を提案した．文脈誘導型学習は，ラベル付け
されたデータだけでなく，各特徴の重みを学習するためにラベル基準と特徴に関する文脈を利用する．実験では文脈誘導型学
習によって既存のランキング学習手法を上回る高い精度が得られることが明らかとなった．
今後の課題としては，文脈誘導型学習の理論的解析，文脈誘
導型学習の他の問題への応用（マルチラベル学習やゼロショット学習），より良い文脈モデルの検討，大規模データに対応するため効率化などを挙げる．
謝辞 本研究の一部は，文科省科研費 15H01718, 26700009,

16H02906, 16K16156, 25240050, 24680008 によるものです．
ここに記して謝意を表します．
文

献[1] A. Argyriou, T. Evgeniou, and M. Pontil. Convex multi-task
feature learning. Machine Learning, 73(3):243–272, 2008.
[2] K. Balog, P. Serdyukov, and A. P. d. Vries. Overview of the
TREC 2010 entity track. In TREC, 2010.
[3] K. Balog, P. Serdyukov, and A. P. d. Vries. Overview of the
TREC 2011 entity track. In TREC, 2010.
[4] K. Balog, A. P. d. Vries, P. Serdyukov, P. Thomas, and
T. Westerveld. Overview of the TREC 2009 entity track.
In TREC, 2009.
[5] F. Bovolo, L. Bruzzone, and M. Marconcini. A novel
context-sensitive svm for classification of remote sensing images. In IGARSS, pages 2498–2501, 2006.
[6] C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds,
N. Hamilton, and G. Hullender. Learning to rank using
gradient descent. In ICML, pages 89–96, 2005.
[7] C. J. Burges, R. Ragno, and Q. V. Le. Learning to rankwith nonsmooth cost functions. In NIPS, pages 193–200,
2006.
[8] Z. Cao, T. Qin, T.-Y. Liu, M.-F. Tsai, and H. Li. Learning
to rank: from pairwise approach to listwise approach. In
ICML, pages 129–136, 2007.
[9] B. A. Carterette. Multiple testing in statistical analysis
of systems-based information retrieval experiments. ACM
TOIS, 30(1):4, 2012.
[10] R. Caruana.
Multitask learning.
Machine Learning,28(1):41–75, 1997.
[11] W. W. Cohen and Y. Singer. Context-sensitive learning
methods for text categorization. ACM TOIS, 17(2):141–
173, 1999.
[12] H. Daumé III. Bayesian multitask learning with latent hierarchies. In UAI, pages 135–142, 2009.
[13] D. Davidov and A. Rappoport. Extraction and approximation of numerical attributes from the web. In ACL, pages
1308–1317, 2010.
[14] A. P. De Vries, A.-M. Vercoustre, J. A. Thom, N. Craswell,and M. Lalmas. Overview of the INEX 2007 entity ranking
track. In INEX, pages 245–251, 2007.
[15] G. Demartini, A. P. de Vries, T. Iofciu, and J. Zhu.
Overview of the INEX 2008 entity ranking track. In INEX,
pages 243–252, 2008.

[16] G. Demartini, T. Iofciu, and A. P. De Vries. Overview of the
INEX 2009 entity ranking track. In INEX, pages 254–264,
2009.
[17] T. Evgeniou and M. Pontil. Regularized multi–task learning. In KDD, pages 109–117, 2004.
[18] Y. Freund, R. Iyer, R. E. Schapire, and Y. Singer. An eﬃcient boosting algorithm for combining preferences. Journalof machine learning research, 4:933–969, 2003.
[19] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting.
Journal of Computer and System Sciences, 1(55):119–139,
1997.
[20] J. H. Friedman. Greedy function approximation: a gradientboosting machine. Annals of statistics, pages 1189–1232,
2001.
[21] T. Iwanari, N. Yoshinaga, N. Kaji, T. Nishina, M. Toyoda,
and M. Kitsuregawa. Ordering concepts based on common
attribute intensity. IJCAI, pages 3747–3753, 2016.
[22] L. Jacob, J.-p. Vert, and F. R. Bach. Clustered multi-task
learning: A convex formulation. In NIPS, pages 745–752,
2009.
[23] C. Kang, D. Yin, R. Zhang, N. Torzec, J. He, and Y. Chang.
Learning to rank related entities in web search. Neurocomputing, 166:309–318, 2015.
[24] A. Kumar and H. Daumé III. Learning task grouping andoverlap in multi-task learning. In ICML, pages 1383–1390,
2012.
[25] Q. V. Le and T. Mikolov. Distributed representations ofsentences and documents. In ICML, pages 1188–1196, 2014.
[26] S.-I. Lee, V. Chatalbashev, D. Vickrey, and D. Koller.
Learning a meta-level prior for feature relevance from multiple related tasks. In ICML, pages 489–496, 2007.
[27] A. Madaan, A. Mittal, G. R. Mausam, G. Ramakrishnan,
and S. Sarawagi. Numerical relation extraction with minimal supervision. In AAAI, pages 2764–2771, 2016.
[28] A. Metallinou, M. Wollmer, A. Katsamanis, F. Eyben,
B. Schuller, and S. Narayanan. Context-sensitive learningfor enhanced audiovisual emotion classification. IEEE TAC,
3(2):184–198, 2012.
[29] D. Metzler and W. B. Croft. Linear feature-based models
for information retrieval. Information Retrieval, 10(3):257–
274, 2007.
[30] Y. Qi and R. W. Picard. Context-sensitive bayesian classifiers and application to mouse pressure pattern classification. In ICPR, pages 448–451, 2002.
[31] H. Takamura and J. Tsujii. Estimating numerical attributesby bringing together fragmentary clues. In HLT-NAACL,
pages 1305–1310, 2015.
[32] T. A. Tran, C. Niederée, N. Kanhabua, U. Gadiraju, and
A. Anand. Balancing novelty and salience: Adaptive learning to rank entities for timeline summarization of highimpact events. In CIKM, pages 1201–1210, 2015.
[33] Q. Wu, C. J. Burges, K. M. Svore, and J. Gao. Adapting
boosting for information retrieval measures. Information
Retrieval, 13(3):254–270, 2010.
[34] K. Yu, V. Tresp, and A. Schwaighofer. Learning gaussian
processes from multiple tasks. In ICML, pages 1012–1019,
2005.
[35] M. Zhou, H. Wang, and K. C.-C. Change. Learning to rank
from distant supervision: Exploiting noisy redundancy for
relational entity search. In ICDE, pages 829–840, 2013.