WebConf2018 BestPaper "HighLife: Higher-arity Fact Harvesting"

CS系の学会のベストペーパーに選出された論文や古典といえる論文を読むということを習慣的にやっていきたいなと思っています。 2ヶ月に1本くらいのペースで読んでいきたいと思っています。飽きたら自然消滅することでしょう。

初回の題材は、2018年のWorld Wide Web Conferenceでベストペーパーに選ばれた"HighLife: Higher-arity Fact Harvesting"です。

www2018.thewebconf.org

World Wide Web Conferenceは、World Wide Webに関する包括的なトピックを扱う国際学会で、毎年開催されているようです。Webに関する包括的な、ということでかなり幅広いジャンルの研究が集まるわけですが、機械学習に近い分野でいうと、ウェブマイニングやパーソナライズ、SNSの分析などが挙げられます。

今回取り上げる論文は、テキストマイニングに関する研究です。ウェブを含むテキスト情報から、何らかの知識を抽出する、という種類の研究です。 何となくぼんやり知っている範囲では、例えば、テキストからある単語の上位-下位、全体-部分といった関連性を持つ単語を抽出したり、特定のエンティティの属性を抽出するというというタスクがあります。

今回の論文では、n-arity factと呼ばれる、より高度な情報抽出を行います。例えば以下のような2つのタスクをある程度自動的にこなせるようになります。

  • 医療情報コーパスをもとにした、症状に対する薬の用法・用量の抽出
  • ニュース記事コーパスをもとにした、企業の買収情報、および、スポーツの受賞情報の抽出

より具体的には、実験において以下のようなn-arity factを抽出しています。

f:id:wanchan-daisuki:20200224115652p:plain

これらのタスクが先に上げた関連語や属性の抽出と比較して何が異なっているのかというと、与えられたエンティティに対して、一意に定まる様々な属性やエンティティを抽出するのではなく、複数の要素の組み合わせ全体を抽出する必要がある、という点にあります。

論文中では以下のような例が挙げられています。

An example is to capture which drug is used for which disease at which dosage (e.g. 2.5 mg/day) for which kinds of patients (e.g., children vs. adults).

薬物の疾患に対する利用においては、用量（dosage）が患者の種類（子供/大人）によって異なってきます。そのため、薬の用量という知識を正確に得るためには、誰に対して投与するのかという条件も込みで抽出しなければならない、というわけです。

全体像

まずは、手法の全体像を確認しましょう。

f:id:wanchan-daisuki:20200223183200p:plain

  1. Preprocessing/NERD：入力されたコーパスをもとに、前処理とNERDを行います。NERDは、Named Entity Recognition（固有表現抽出）とDisambiguation（曖昧性解消）の略です。エンティティの辞書として、既存のナレッジベースを使用しています。これによって、エンティティのアノテーションが行われた文章が得られます。
  2. Tree Mining：得られた文章に対して、依存関係木を構築します。そして依存関係木をもとに、Pattern Treeと呼ばれる構造に変換します。この木構造は、rootがn-arity factの要素のひとつである文章の主語、leafがn-arity factの各要素となるようなものになっています。
  3. Tree Analysis：コーパスから大量のPattern Treeが得られたところで、その中から、十分な頻度で出現する部分木pattern subtreeを抽出します。その後、検証済みのn-arity factをシードとして利用し、信頼できるpattern subtreeを得ます。この信頼できるpattern subtreeを、salient seed treeと呼びます。
  4. Tree Matching：このsalient seed treeを利用すると、他のpattern subtreeからn-arity factの候補を抽出できます。しかし、salient seed treeに完全にマッチする表現がpattern subtree内に出現することは稀ですので、salient seed treeとpatten subtreeの類似度を算出し、候補としての重みを決定します。
  5. Consistency Reasoning：得られたpattern subtreeからn-arity factの候補を抽出し、それらをマージし最終的なn-arity factとして採用します。その際に、事前に用意されたルールにpattern subtreeを当てはめていき、Weighted Max-Sat問題として解きます。

2, 3, 4あたりにたくさんの木構造が出てくるので、少し整理してみました。要するにseed factという検証済みのn-arity factを使って信頼できるパターンであるsalient seed treeを抽出し、それを使って他のfactに関わるpattern subtreeからfact候補を抽出する、という流れがつかめればよいかと思います。

f:id:wanchan-daisuki:20200224112251p:plain
fact候補抽出までの流れ

なお、本手法を特徴づける概念として、partial factというものがあります。n-arity factのn個の要素すべてが同一の文章に出現する、ということはあまりありません。そのため、n個の要素の一部のみを含む文章からもfactの一部を抽出し、マージしてあげることで完全なfactを得る必要があります。最後のステップであるConsistency Reasoningにおいては、その処理を行っています。

以下、細かく見ていきましょう。

NERD（Named Entity Recognition & Disambiguation）

NER

NERには、Stanford CoreNLPを使っています。既存のナレッジベースに収録されているエンティティを辞書として用いています。 ここらへんの処理は、この手の研究ではおそらく色々と蓄積があるんだろうなあ、と思いながら読んでいました。

  • 医療関係の文書に対しては、Unified Medical Language Systemに収録されているエンティティ辞書を用いています。この辞書は、3,221,702エンティティ、12,842,558名称をカバーしているそうです。効率的にエンティティの候補を見つけるために、MinHashを使用しているそうです。
  • ニュース記事に関しては、AIDAを曖昧性解消に利用しています。これは、YAGOのエンティティとリンクしています。
  • より一般的なDisambiguationは、WordNetのConsceptを利用して行っています。
  • 量的な表現（薬の投与量や企業の買収金額）については、エンティティの型やPOSタグ、具体的な単語を利用した正規表現を使って抽出しています。
  • 時表現は、Stanford CoreNLP sutime moduleを用いて、標準化しています。

Tree Mining

エンティティの情報が付与された文章に対して依存関係木を構築し、pattern treeに変換します。その流れを表したのが以下の図です。

f:id:wanchan-daisuki:20200224122239p:plain

2.5 mg Albuterol may be used to treat acute exacerbations, particularly in children.

という文章から依存関係木をつくっています。この依存関係木のノードに含まれるエンティティや量表現などをtargetと呼びます。targetは、最終的にはn-arity factを構成する要素の候補になります。

次に、得られた依存関係木（上図左下）から、pairwise pathと呼ばれるものを抽出します。pairwise pathは、主語であるtargetから、別のtargetへの道のりを表現します。 上記の例では、主語となるtargetはAlbuterolで、他のtargetは2.5 mg, acute exacerbations, childrenなどですが、それぞれについて以下のようなパスが抽出されます。

f:id:wanchan-daisuki:20200224140220p:plain

これらのpairwise pathをまとめ、pattern treeにします（2つ上の図の右）。pattern treeは、主語targetをrootとし、別のtargetがleafとなるような構造になります。複数のpairwise pathで重複する部分は、マージされます。これによって、各target、つまりfactの構成要素の間にどのような関係があるのかを木構造として抽出できたことになります。

Tree Analysis

一つの文章から得られたpattern treeは、様々なノイズを含む汚いものです。これを、コーパス内のすべての文章に対して抽出し（下図左）、その中で共通して高頻度で現れる部分木を比較的信頼できるpattern subtreeとして抽出します。

f:id:wanchan-daisuki:20200224145551p:plain

ここで、pattern subtreeは、高頻度で出現する部分木で、FreeTreeMinerというアルゴリズムによって抽出されます。いわゆるFrequent Pattern Miningの一手法ですね。

その後、人手で検証済みのseed factを用意します。このseed factを用いて、pattern subtreeの中で、より信頼のおけるsalient seed treeを抽出します。この時、Frequent Pattern Miningでよく使われるsupport（支持度）を用いて、pattern subtreeの信頼度（confidence）を算出します。これにより、どんなに高頻度であっても、seed factと相容れないtargetの組でも出現する無節操なpattern subtreeを除外できます。

confidenceは以下のような式で表現されます。

{confidence}(PS(s))=\frac{{ support }(PS(s), SX(R))}{{ support }(PS(s), SX(R) \cup CX(R))}

SX(R)はseed fact（の一部）に含まれる要素からなる組、CX(R)はseed fact（の一部）とは相容れない要素からなる組です。これにより、n-arity fact及びその一部であるpartial factでよく出現する信頼度付きのsalient seed treeが得られます。

Tree Matching

salient seed treeを用いることで、seed factとは別のfact候補を表すpattern subtreeとの類似度を算出し、その中に現れる(partial) factの候補を得ることができます。

salient seed treeとpattern subtreeの類似度は、まず、そこに含まれるpairwise path同士の類似度を算出し、それらを掛け合わせて算出します。

pairwise path同士の類似度は、下式で表現されます。要するに、パスの長さが同一でない場合は0、長さが同一のときはパス内の要素がどれくらい同じかによって計算されます。

f:id:wanchan-daisuki:20200224160808p:plain

そして、部分木同士の類似度は下式のように、そこに含まれるpairwise pathの類似度の掛け算として表現されます（\operatorname{argmax}をここで使っているのは、誤植のように思います。たぶん。。。）。

f:id:wanchan-daisuki:20200224160707p:plain

この部分木同士の類似度を使って、salient seed treeに近いpattern subtreeに現れているfact候補を抽出します。この時、この(partial) fact候補には、salient seed treeのconfidenceと、salient seed treeとpattern subtreeの類似度を使って算出された重みが割り当てられます。

Consistency Reasoning

以上のようにして得られた大量の重み付き（partial）fact候補には、矛盾する内容も含まれるはずです。そういうわけで、候補同士の一貫性を、重みを考慮しながら整理していく必要があります。

ここで、様々なPredicateとそれらによって成り立つConsistency Ruleを用意し、そこにpattern subtreeから得られるfact候補の要素を当てはめ、論理的な推論をすすめることでfact候補の正当性を明らかにするという処理を進めます。この推論は、重み付きのものなので、Weighted Max-Sat problemという問題に帰着されますが、これに対する近似解法であるSOFIEという手法が本論文では使用されています。

まず、Predicateについては、以下のようなものを人手で頑張って用意しています。ドメイン知識を利用した臓器の全体-部分関係などは特徴的です。

f:id:wanchan-daisuki:20200224165948p:plain

次に、これらのPredicateを使ってfact候補の要素を論理的に表現し、以下のようないくつかのルールによってできるだけ整合性のあるもののみを最終的なfactとして出力します。

f:id:wanchan-daisuki:20200224164152p:plain

一番上のTree pattern-fact dualityは、pattern subtreeから、その中に含まれるtargetの型などの整合性を確認し、fact候補のタプルを作るというルールです。Mutual Exclusionは、矛盾する組み合わせのPredicate、例えば病気の原因を表すタプルの構成要素と病気への処方箋のタプルの構成要素が同じものであってはならないとか、企業の買収関係を表すタプルに含まれる買収する側・される側が逆転することがあってはならない、というように、論理的な矛盾を抑制するようなルールが挙げられています。

また、一番下のEquality Constraintsでは、partial factを組み合わせることで、一つの完全なfactを構築できるケースについてのルールを整備しています。 例えば、AthleteWonAward(Kerber,OlympicSilver,tennis, 2016,X)という一部が歯抜けになっているPredicateと AthleteWonAward(Kerber,OlympicSilver,Y, 2016, Rio) というPredicateは、組み合わせることで、AthleteWonAward(Kerber,OlympicSilver,tennis, 2016, Rio)という完全な形を作ることができます。

感想

と、パターンマイニング初心者が、畏れ多くも最高峰の論文をざっと読んでみました。 この分野の様々な蓄積が確認でき、それらをフルに活用している手法であることがわかりました。

固有表現抽出やら依存関係木の構築などは、自然言語処理の重要なアウトプットなわけですが、それを何に使うの、というのは恥ずかしながらあまり意識したことがなかったので、なるほどこういったナレッジベース構築の一つの前処理として使われるのだな、ということがわかり意義がよくわかった気がします。

また、Consistency Reasoningの部分で、機械学習分野だとおろそかにされがち？な論理的な推論をベースにした方法が採られているのが面白かったです。Weighted Max-Sat problemという問題の形式も初めて知ったのですが、それ以上に、人手でルールを書いていってそれをもとに推論させていくというプロセスは、大変そうだがうまく問題にハマるように設計できると気持ちいいだろうなと思いました。

なお、本論文を読む前に気になっていた点として、引用件数の少なさというのがあったのですが、その理由はConsistency Reasoningまわりの手作業の部分が再現を困難にしているためではないか、と思いました。