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です。

書誌情報

全体像

まずは論文の全体像を確認します。論文の章立ては以下のようになっています。

  1. INTRODUCTION
  2. THE YAGO MODEL
  3. SOURCE FOR YAGO
  4. THE YAGO SYSTEM
  5. EVALUATION AND EXPERIMENTS
  6. 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となります。

    • f:id:wanchan-daisuki:20200530152929p:plain

  • wordは、MEANS relationによって、entityと紐づけられます。

    • f:id:wanchan-daisuki:20200530154018p:plain

  • 各entityはclassを持っていて、これはTYPE relationによって表現されます。

    • f:id:wanchan-daisuki:20200530154333p:plain

  • classには階層があり、subClassOf relationで表現されます。

    • f:id:wanchan-daisuki:20200530155657p:plain

  • relationもentiryでありclassをもっています。例えば、subclassOfは、transitiveRelation（推移的関係）のサブクラスです。

    • f:id:wanchan-daisuki:20200530155618p:plain

  • factはidによって管理されており、それ自体がentiyです。FOUNTIN relationによって、factの情報源を示すentityであるURLと紐づけられたfactを形成します。

    • f:id:wanchan-daisuki:20200530160050p:plain

  • factは2項関係ですが、多項関係（n-ary関係）を表現したいこともあります。例えば（winner, prize, time）という3項からなるfactは、TIME relation を含む以下の2つのfactによって表現できます。先に示したFOUNTIN関係によって作られるfactも、多項関係の一種といえます。

    • f:id:wanchan-daisuki:20200530154802p:plain

なお、なんでもかんでもentityなので、区別のために以下のような呼称が採用されています。 - factやrelation以外のentityは、common entityと呼ばれます。 - common entityのうちclassでないものは、individualと呼ばれます。

individualは、後ほども出てくる重要な概念です。

YAGOのセマンティクス

YAGOを構成する要素について確認してきましたが、それらをもとにどのように知識全体を表現できるのかを確認していきます。 ここでいうセマンティクスは、プログラム意味論のことなのでしょうが、あんまりなじみのない分野ということもあってイマイチぴんと来ないまま読みました。要するに「公理」をきっちり定めておいて、そのなかで生じる推論に矛盾が生じないようにしよう、という程度のことだと理解しました。

ここから、あるfact集合から推論によって導ける最大のfact集合は一意であること（定理1）、あるfact集合から導ける基底fact集合は一意であること（定理2）をえることができます。

まず、以下のようなrelationとcommon entityが事前に用意されます。

  • relation: \mathcal{R}
    • 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: \mathcal{C}
    • entity
    • class
    • relation
    • acyclicTransitiveRelation
    • 以降の自明な規則にあるliteralとそのclass

factのidentifierの集合を\mathcal{I}とし、\mathcal{C, R}とともに、fact集合\mathcal{F}は以下のように記述されます。

\mathcal{F} = (\mathcal{I} \cup \mathcal{C} \cup \mathcal{R}) \times \mathcal{R} \times (\mathcal{I} \cup \mathcal{C} \cup \mathcal{R})

ここで、複数のfact集合から自動的に別のfactが得られる場合、以下のように表記します。

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

この表記を利用し、自明な規則は以下のように列挙されています。空集合から導かれるので、\emptysetが左項に置かれています。

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

以上のような自明な規則に加え、以下のような規則も定義しておきます。上の規則は下準備感が強いですが、下の規則は論履的な推論感が強いですね。

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

こういった規則をもとに、定理1と定理2が導かれるわけですが、、、結構読むのがハードだったのでとばしとばし読みました。気になる方は論文を読んでみてください。

SOURCES FOR YAGO

YAGOを構成する２つの情報源である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の検索結果の丸かっこ内の数字のことです。 f:id:wanchan-daisuki:20200622224335p:plain

と、このような処理である程度の自動化はできるようですが、十数個の間違いはあったそうで、最終的には人手でチェックする必要があるそうです。

ところで、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の論文を読んでわかったことをまとめてみました。スマートに解決している部分もある一方で、手作業で修正が必要など、なかなか泥臭い世界を覗くことができました。しかし、「ここまでは自動的にできるけど、あとは手作業で頑張ろう」というスタンスは、実際に機能するものを作るときには重要だなと思いました。