WebConf2018 Test of Time Award: "YAGO: A Core of Semantic Knowledge Unifying WordNet and Wikipedia"
ナレッジベースをどのように作るのか、ということに興味を持ちました。一例として、WebConf2018でTest of Time Awardに選ばれたYAGOの論文を読んでみたいと思います。YAGOはWikipediaとWordNetを情報源としたナレッジベースで、現在はバージョン4が公開されており、なかなか活発に開発されている模様です。
今回は、初代の論文"YAGO: A Core of Semantic Knowledge Unifying WordNet and Wikipedia"を読んでみました。初出は2007年のWebConfです。
書誌情報
- Fabian, M. S., K. Gjergji, and W. E. I. K. U. M. Gerhard. "Yago: A core of semantic knowledge unifying wordnet and wikipedia." 16th International World Wide Web Conference, WWW. 2007.
- https://www2007.org/papers/paper391.pdf
全体像
まずは論文の全体像を確認します。論文の章立ては以下のようになっています。
- INTRODUCTION
- THE YAGO MODEL
- SOURCE FOR YAGO
- THE YAGO SYSTEM
- EVALUATION AND EXPERIMENTS
- CONCLUSION
このうち、記事では2, 3, 4について読解してきます。ここで簡単に内容を見ておきます。
- THE YAGO MODEL: YAGOがどのように知識をモデル化しているのかについて説明します。
- SOURCE FOR YAGO: YAGOの情報源であるWikipediaとWordNetについておさらいします。
- THE YAGO SYSTEM: 情報源からどのように知識を抽出し、YAGOを構築するのかを説明します。
THE YAGO MODEL
YAGOがどのように知識をモデル化するのかについて、確認してきます。
YAGOの構造
YAGOでは、以下のような要素によって知識を表現します。
- entity: 最小の構成要素。
- word: 文字列。表面上あらわれる表現で、entityに紐づけられる。
- relation: 2つのentityとそれらを結ぶ関係を表現する。relationもentityのひとつ。
- class: entityの型
- fact: 2つのentityとそれらを結ぶrelationで構成される。factもまたentityのひとつ。
以下、これらの要素がどのように結びついていくのかを示します。
factは以下のように、2つのentityと1つのrelationによって作られます。1つ目の文章でいえば、AlbertEinsteinやNorbelPrizeがentiry、HASWONPRIZEがrelationとなります。
wordは、MEANS relationによって、entityと紐づけられます。
各entityはclassを持っていて、これはTYPE relationによって表現されます。
classには階層があり、subClassOf relationで表現されます。
relationもentiryでありclassをもっています。例えば、subclassOfは、transitiveRelation(推移的関係)のサブクラスです。
factはidによって管理されており、それ自体がentiyです。FOUNTIN relationによって、factの情報源を示すentityであるURLと紐づけられたfactを形成します。
factは2項関係ですが、多項関係(n-ary関係)を表現したいこともあります。例えば(winner, prize, time)という3項からなるfactは、TIME relation を含む以下の2つのfactによって表現できます。先に示したFOUNTIN関係によって作られるfactも、多項関係の一種といえます。
なお、なんでもかんでもentityなので、区別のために以下のような呼称が採用されています。 - factやrelation以外のentityは、common entityと呼ばれます。 - common entityのうちclassでないものは、individualと呼ばれます。
individualは、後ほども出てくる重要な概念です。
YAGOのセマンティクス
YAGOを構成する要素について確認してきましたが、それらをもとにどのように知識全体を表現できるのかを確認していきます。 ここでいうセマンティクスは、プログラム意味論のことなのでしょうが、あんまりなじみのない分野ということもあってイマイチぴんと来ないまま読みました。要するに「公理」をきっちり定めておいて、そのなかで生じる推論に矛盾が生じないようにしよう、という程度のことだと理解しました。
ここから、あるfact集合から推論によって導ける最大のfact集合は一意であること(定理1)、あるfact集合から導ける基底fact集合は一意であること(定理2)をえることができます。
まず、以下のようなrelationとcommon entityが事前に用意されます。
- relation:
- TYPE: 第1項のclassを第2項で指定する
- subClassOf: 第1項(class)が第2項(class)の下位classであることを表す
- DOMAIN: 第1項(relation)の引数の第1項が、第2項(class)であることを表す
- RANGE: 第1項(relation)の引数の第2項が、第2項(class)であることを表す
- subRelationOf: 第1項(relation)が第2項(relation)の下位relationであることを表す。
- common entity:
- entity
- class
- relation
- acyclicTransitiveRelation
- 以降の自明な規則にあるliteralとそのclass
factのidentifierの集合をとし、とともに、fact集合は以下のように記述されます。
ここで、複数のfact集合から自動的に別のfactが得られる場合、以下のように表記します。
この表記を利用し、自明な規則は以下のように列挙されています。空集合から導かれるので、が左項に置かれています。
以上のような自明な規則に加え、以下のような規則も定義しておきます。上の規則は下準備感が強いですが、下の規則は論履的な推論感が強いですね。
こういった規則をもとに、定理1と定理2が導かれるわけですが、、、結構読むのがハードだったのでとばしとばし読みました。気になる方は論文を読んでみてください。
SOURCES FOR YAGO
YAGOを構成する2つの情報源であるWordNetとWikipediaについておさらいしておきましょう。
WordNet
WordNetは117,097のユニークな名詞に対する81,426のsynsetから成っている辞書です。synsetは「意味、概念」くらいでとらえておくとよいでしょう。このsynsetに対して、複数の名詞が登録されています。たとえば、homo, man, human being, humanという複数の名詞を抱えているsynset(人類)があったり、 man, adult male からなるsynset(男性)があったりします。一つの名詞が複数のsynsetに含まれていることが多く、上記の例ではmanは非常に多くのsynsetに含まれています。
WordNetには動詞や形容詞も含まれるますが、本論文が対象とするのは名詞のみです。synsetどうしは、上位/下位や、全体/部分という関係によって接続されていて、本論文では、上位/下位関係のみにフォーカスしています。
このような名詞と上位/下位関係のみを抽出すると、WordNetは、Entityというsynsetを頂点とする有向非巡回グラフとし表現できます。
Wikipedia
wikipediaの記事には、1つ以上のcategoryが人手でつけられています。wikipediaの記事に対するカテゴリの割当やページ間のリンク構造は、SQLテーブルとして利用できるので記事をパースする必要はありません。あまりカテゴリに気を付けてWikipediaのdumpデータをいじったことがないのでわかりませんが、categorylinks.sql.gzの中に格納されていそうですね。
必要なのはカテゴリとページタイトルだけで、他は必要ありません。
THE YAGO SYSTEM
さて、いよいよYAGOをどのように構築するのかを見ていきます。基本的には情報抽出の泥臭い話が続きます。しかし、その前に大きな枠組みだけ示しておきます。
YAGOでは、Wikipediaの各ページタイトルをindividualとします。そして、Wikipediaの各ページに振られているカテゴリ情報をもとに、individualのclassを求めたり、individual同士の関係を抽出し、factにしていきます。そして様々なfactが集められることでYAGOが完成します。
TYPE関係の特定
TYPE関係、つまり各individualのclassを求めます。classとindivisualは上位/下位の上位関係にあるといえます。そのために、Wikipediaの記事についているカテゴリのうち、Conceptual Categoryを用います。 WikipediaのカテゴリにはYAGOにとってはどうでも良いカテゴリがあります。それは、漠然としたテーマを表すカテゴリ(Thema Category)や、Wikipediaの管理上付与されているカテゴリ(Administrative Category)や、上位関係以外の関係を表すカテゴリ(Relational Category)です。これらは除外して考えます。
例えば、Albert Einsteinの記事には、以下のようなカテゴリが設定されていたようです。
- Naturalized citizens of the United States:Conceptual Category
- Articles with unsourced statements:Administrative Category
- 1879 births:Relational Category
- Physics:Theme Category
Administrative CategoryとRelational Categoryは数が限られているので手作業で除去できるそうです。しかし、Theme Categoryだけは数が多く手作業では無理だと判断したそうです。 Theme Categoryを除外するために、本手法では、以下のような手順を採っています。
例えば、Naturalized citizens of the United Statesのようなカテゴリを考えます。このカテゴリに簡単な構文解析を行うことで、前修飾語(Naturalized)、head(citizens)、後修飾語(of the United States)に分割します。そして、head部分(citizens)が複数形の名詞であるときにそのカテゴリはConceptual Categoryである可能性が高い、としています。
以上のような操作を通じて、無事にカテゴリからTYPE関係を抽出することができています。
SubClassOf関係の特定
YAGOにおけるclassは、基本的にはWordNetのsynsetが使用されます。そして、class間の階層関係を表すSubClassOf関係は、WordNet上のsynsetの上下関係から特定されます。
各individualのclassはTYPE関係の特定で述べた通り、Wikipediaのカテゴリから特定されますが、このカテゴリとWordNetのsysnsetを結びつける必要があります。 WikipediaのカテゴリはDAGになっているため、ひとつの記事に上下関係を持つ2つ以上のカテゴリが割り振られていることがありますが、このなかのLeafとなっているカテゴリのみを使用します。
WikipediaのLeafカテゴリはWordNetのsynsetよりも細かいので、カテゴリ文字列を分析し、上位カテゴリを抽出する必要があります。例えば、"American people in Japan"というカテゴリーから、"American person"または"person"という上位カテゴリーを特定する必要があるわけです。
こちらも簡単な構文解析とステミング処理によって実現します。"American people in Japan"という文字列をpre/head/postという3つの部分に分けます。この例だとそれぞれ、American/person/in Japanが対応します。そして、pre+headがまずはsynsetに存在するかを確認します。存在しなければheadがsynsetに存在するかを確認します。synsetとの対応が見つかったならば、それでWikipediaのカテゴリとsynsetの対応付けは完了です。
ところで、synsetの中には、様々な単語が含まれているので、対応するsynsetが複数見つかることがあります。この場合は、最も頻度の高いsynsetを選択します。「頻度」というのは、以下のようなWordNetの検索結果の丸かっこ内の数字のことです。
と、このような処理である程度の自動化はできるようですが、十数個の間違いはあったそうで、最終的には人手でチェックする必要があるそうです。
ところで、WordNetのsynsetをそのままclassとして使用するというのには問題点があります。例えば、Albert Einsteinのような超有名人は、Wikipediaに記事が存在すると同時にWordNetにも登場しますが、普通に考えるとclassとして扱うのではなくindividualとして扱いたいです。逆に、Physicistのような一般名詞は、Wikipediaに記事があるとしてもindividualとしてではなく、classとして扱いたいです。このようなWikipediaにもWordNetにも出現するConflictは15000もあるため、著者らは、一般名詞はWordNetを優先し、それ以外はWikipediaを優先しています。つまり、先ほどの例でいうと、PysicistというWikipediaの記事は無いものとして処理を進めるというわけです。このあたりの取捨選択にも人手がかかっていそうです。
MEANS関係の特定
MEANS関係は、文字列とindividualを紐づけるRelationです。複数のやり方が採用されています。
まず、WordNetのsynsetには、様々な単語が登録されているのでこれを使わない手はありません。これを使うと、あるsynsetに対応するclassとsynsetないの各単語の間にMEANS関係を確立することができます。例えば、synset{city, metropolis, urban center}と対応するYAGO class cityを使うと、("metropolis",MEANS,city)というMEANS関係が確立できます。
次に、WikipediaのRedirectを活用する方法があります。Wikipediaのリダイレクトは、alternative nameとみなすことができます。例えば、"Einstein, Albert"という文字列が、記事"Albert Einstein"にリンクされているのなら、("Einstein, Albert", MEANS, AlbertEinstein)というMEANS関係が確立できます。
その他の関係の特定
wikipediaのカテゴリ文字列を利用すれば、様々なRelationを抽出できます。以下に一例をあげます。
- bornInYear, diedInYear:"_births", "_deaths"
- establishedIn: "_establishments"
- locatedIn: "Cities in ", "Countries in ", "Revers of ", "Attractions in "
- writtenInYear, politicianOf, hasWonPrizeなども同じ
Meta-Relations
YAGOの拡張のためのメタ関係を特定するために考えられているRelationがあります。例えば、Witness関係はあるfactがどの情報源(URLなど)から得られたのか、ということを表現できます。また、Context関係は、individualのもとになっているWikipediaの記事においてリンクが存在していれば関係づける、というもので曖昧性解消に使用できる、としています。
まとめ
以上、ざっとですがYAGOの論文を読んでわかったことをまとめてみました。スマートに解決している部分もある一方で、手作業で修正が必要など、なかなか泥臭い世界を覗くことができました。しかし、「ここまでは自動的にできるけど、あとは手作業で頑張ろう」というスタンスは、実際に機能するものを作るときには重要だなと思いました。
WebConf2018 BestPaper "HighLife: Higher-arity Fact Harvesting"
CS系の学会のベストペーパーに選出された論文や古典といえる論文を読むということを習慣的にやっていきたいなと思っています。 2ヶ月に1本くらいのペースで読んでいきたいと思っています。飽きたら自然消滅することでしょう。
初回の題材は、2018年のWorld Wide Web Conferenceでベストペーパーに選ばれた"HighLife: Higher-arity Fact Harvesting"です。
World Wide Web Conferenceは、World Wide Webに関する包括的なトピックを扱う国際学会で、毎年開催されているようです。Webに関する包括的な、ということでかなり幅広いジャンルの研究が集まるわけですが、機械学習に近い分野でいうと、ウェブマイニングやパーソナライズ、SNSの分析などが挙げられます。
今回取り上げる論文は、テキストマイニングに関する研究です。ウェブを含むテキスト情報から、何らかの知識を抽出する、という種類の研究です。 何となくぼんやり知っている範囲では、例えば、テキストからある単語の上位-下位、全体-部分といった関連性を持つ単語を抽出したり、特定のエンティティの属性を抽出するというというタスクがあります。
今回の論文では、n-arity factと呼ばれる、より高度な情報抽出を行います。例えば以下のような2つのタスクをある程度自動的にこなせるようになります。
より具体的には、実験において以下のようなn-arity factを抽出しています。
これらのタスクが先に上げた関連語や属性の抽出と比較して何が異なっているのかというと、与えられたエンティティに対して、一意に定まる様々な属性やエンティティを抽出するのではなく、複数の要素の組み合わせ全体を抽出する必要がある、という点にあります。
論文中では以下のような例が挙げられています。
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)が患者の種類(子供/大人)によって異なってきます。そのため、薬の用量という知識を正確に得るためには、誰に対して投与するのかという条件も込みで抽出しなければならない、というわけです。
- 全体像
- NERD(Named Entity Recognition & Disambiguation)
- Tree Mining
- Tree Analysis
- Tree Matching
- Consistency Reasoning
- 感想
全体像
まずは、手法の全体像を確認しましょう。
- Preprocessing/NERD:入力されたコーパスをもとに、前処理とNERDを行います。NERDは、Named Entity Recognition(固有表現抽出)とDisambiguation(曖昧性解消)の略です。エンティティの辞書として、既存のナレッジベースを使用しています。これによって、エンティティのアノテーションが行われた文章が得られます。
- Tree Mining:得られた文章に対して、依存関係木を構築します。そして依存関係木をもとに、Pattern Treeと呼ばれる構造に変換します。この木構造は、rootがn-arity factの要素のひとつである文章の主語、leafがn-arity factの各要素となるようなものになっています。
- Tree Analysis:コーパスから大量のPattern Treeが得られたところで、その中から、十分な頻度で出現する部分木pattern subtreeを抽出します。その後、検証済みのn-arity factをシードとして利用し、信頼できるpattern subtreeを得ます。この信頼できるpattern subtreeを、salient seed treeと呼びます。
- Tree Matching:このsalient seed treeを利用すると、他のpattern subtreeからn-arity factの候補を抽出できます。しかし、salient seed treeに完全にマッチする表現がpattern subtree内に出現することは稀ですので、salient seed treeとpatten subtreeの類似度を算出し、候補としての重みを決定します。
- 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候補を抽出する、という流れがつかめればよいかと思います。
なお、本手法を特徴づける概念として、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に変換します。その流れを表したのが以下の図です。
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などですが、それぞれについて以下のようなパスが抽出されます。
これらのpairwise pathをまとめ、pattern treeにします(2つ上の図の右)。pattern treeは、主語targetをrootとし、別のtargetがleafとなるような構造になります。複数のpairwise pathで重複する部分は、マージされます。これによって、各target、つまりfactの構成要素の間にどのような関係があるのかを木構造として抽出できたことになります。
Tree Analysis
一つの文章から得られたpattern treeは、様々なノイズを含む汚いものです。これを、コーパス内のすべての文章に対して抽出し(下図左)、その中で共通して高頻度で現れる部分木を比較的信頼できるpattern subtreeとして抽出します。
ここで、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は以下のような式で表現されます。
はseed fact(の一部)に含まれる要素からなる組、は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、長さが同一のときはパス内の要素がどれくらい同じかによって計算されます。
そして、部分木同士の類似度は下式のように、そこに含まれるpairwise pathの類似度の掛け算として表現されます(をここで使っているのは、誤植のように思います。たぶん。。。)。
この部分木同士の類似度を使って、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については、以下のようなものを人手で頑張って用意しています。ドメイン知識を利用した臓器の全体-部分関係などは特徴的です。
次に、これらのPredicateを使ってfact候補の要素を論理的に表現し、以下のようないくつかのルールによってできるだけ整合性のあるもののみを最終的なfactとして出力します。
一番上の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まわりの手作業の部分が再現を困難にしているためではないか、と思いました。