DEIM Forum 2013 A4-5

Wikipedia と WordNet を用いたテラバイト級 Web コーパスからのクラス間関係抽出白川真澄†

中山浩太郎††

荒牧 英治††

原隆浩†

西尾章治郎†† 大阪大学大学院情報科学研究科〒 565-0871 大阪府吹田市山田丘 1-5†† 東京大学知の構造化センター〒 113-8656 東京都文京区本郷 7-3-1
E-mail: †{shirakawa.masumi,hara,nishio}@ist.osaka-u.ac.jp, ††nakayama@cks.u-tokyo.ac.jp,†††eiji.aramaki@gmail.com
あらまし

本研究では，Wikipedia の記事と WordNet のクラスを用いて，大規模な Web コーパスからドメイン非依

存でクラス間の関係を抽出する手法を提案する．高い精度を維持しつつ多種多様なドメインのクラス間の関係を網羅的に抽出するためには，関係の絶対数を増やすことが不可欠であり，そのためには膨大なテキストを解析する必要がある．そこで提案手法では，処理速度を優先するため，自然言語処理技術を一切用いずにテキストコーパスから語句を抽出し，2 つの語句間に出現する文字列を関係パターンとして取得する．そして，抽出した語句間の関係から，

Wikipedia の記事を介して WordNet のクラスに置き換えることで，クラス間の関係を取得する．また，出現確率を考慮したスコアリングによりクラス間の関係のスコア（確信度）を定義することで，適当な粒度でクラス間の関係を取得する手法を提案する．Hadoop 環境を利用して 10 億以上の Web ページ（約 15TB）から 1 億以上のクラス間の関係を抽出し，様々な観点から評価を行い，提案手法の有効性，および抽出したクラス間の関係の有用性を確認した．
キーワード

関係抽出，Wikipedia，WordNet，YAGO

1. は じ め に中に自分の知らない語句が含まれていても，テキストの意味を理解できることがある．たとえば，「シャラポワがエラニを破人がテキストの意味を理解する背景には概念（concept）ある」という文を見たとき，シャラポワがテニス選手であること

るいはクラス（class）が存在する．概念あるいはクラスとは，を知っていれば，エラニが何かを知らなくてもそれがテニス選

事物を抽象化し，共通する意味や性質を表したものであり，事手であることを推測でき，結果としてこの文の意味を把握でき物そのものを表すエンティティ（entity）あるいはインスタンス

る．これは，我々が日々の経験から，エンティティを概念（ク（instance）とは区別される．たとえば，「大阪大学」や「東京大ラス）に置き換えながら関係を学習しており，テニス選手が破学」がある事物を表すエンティティであるのに対し，「大学」やるのは同じくテニス選手であるといったクラス間の関係がある「教育機関」はこれらのエンティティの共通の側面を表した概ことを学んでいるためである．

念である．また，「大阪大学」と「大阪城」というエンティティ

このようなクラスを利用したテキストの内容の把握をコンに対しては「大阪に存在する建造物」という概念が存在しうる．

ピュータに行わせることを目指し，筆者らは先行研究 [21] におこのように，1 つのエンティティには様々な上位の概念が存在いて，テキストコーパスから，語句間やエンティティ間ではな

し，他のエンティティとの共通点や相違点およびその他の関係

く，クラス間の関係を抽出してきた．先行研究では，人がクラは多くの場合，この概念を介して表現される．

ス間の関係を学習する方法にならい，テキストから関係を抽出

心理学者 Gregory Murphy が自身の著書 [14] で「概念は我々する際に語句をクラスに置き換えてから関係を抽出する手法をの心的世界を結び付ける接着剤である（concepts are the glue

提案している．また，実際に 30GB 程度の Wikipedia の全記

that holds our mental world together）」と述べていることか事をテキストコーパスとして関係抽出を行い，数百万規模でクらも分かるように，概念は言葉の意味を理解するためのカギとラス間の関係を抽出している．しかし，Wikipedia 内のテキスなるものである．また，彼は「それら（概念）によって我々は

トに限定して関係を抽出しているため，関係の種類に偏りが多新しい物や事象を認識・理解できるようになる（they enable us

いという問題があった．Web 上に出現しうる関係を網羅するた

to recognize and understand new objects and events）」と述

めには，Web の様々なドメインの膨大なテキストデータを対象べている．実際，我々人間はテキスト中に，あるエンティティとして関係を抽出する必要がある．

を意味する語句を観測したとき，それを概念に置き換えること

そこで本研究では，先行研究で提案した手法を拡張し，10 億でテキストの意味を把握しようとする．これにより，テキスト

以上の Web ページというテラバイトスケールのテキストコー

パスから現実的な処理時間でクラス間の関係を抽出する手法をは動詞句に限定して語句間の事実関係を抽出しており，現在公提案する．提案手法では，膨大な量のテキストを高速に処理す

開しているシステムでは 5 億の Web ページから抽出した関係るため，テキストから語句間の関係を抽出する際，自然言語処に，Freebase [2] のタイプ（クラス）を付与することで，どのよ

理技術を用いず，文字列処理のみを適用する．具体的には，トうなクラス間で関係があるかを表現している．PATTY [15] でライ辞書を用いて語句を検出し，語句間に出現する文字列を関は，YAGO [18] を用いて Wikipedia の WordNet [9] のクラス

係パターンとして抽出する．これにより，膨大な Web コーパ

間の関係を抽出し，関係パターンのクラスタリングを行っていスからの関係抽出を比較的高速に処理できる．また，自然言語る．本研究では WordNet のクラス間の関係を抽出することを処理技術を用いないことで，英語以外の様々な言語にも実装コ目的としており，特に PATTY との類似性が高いが，PATTY

ストをかけずに応用できる可能性がある．一方で，抽出した関とは異なり，完全にクラス間の関係抽出のみを対象としたアプ係の精度が低下するという問題が発生する．この問題に対してローチをとっている．また，本研究の提案手法は，構文解析やは，関係の出現頻度をもとに確率的なスコアを与える手法を提

形態素解析などの自然言語処理技術を一切用いない手法である

案することにより，できる限り精度を維持する．本研究では，ため，上記の研究で提案された手法よりも高速に機能し，また，提案手法の有効性を確認するために，Hadoop 環境を用いて約

英語以外の言語にも実装コストをかけずに応用できる可能性が15TB という規模の Web コーパスからクラス間の関係抽出を高い．

行い，1 億以上のクラス間の関係を抽出している．

2. 関 連 研 究

3. クラス間の関係抽出手法
本研究では，テキストから関係を抽出する際に，語句をクラテキストから語句間の関係を抽出する研究はこれまで数多く

スに置き換えることで，クラス間の関係を抽出する手法を提案行われてきたが，Web の普及に伴い，大規模な Web コーパスする．以下ではまず，人がどのように概念（クラス）を利用しを対象としたドメイン非依存の関係抽出手法が注目を集めてきて関係を学習し，推測するかについて述べた後，それを模倣した．Etzioni らの KnowItAll [6] はドメイン非依存で関係抽出をたクラス間の関係抽出手法について詳述する．なお，本研究に行った代表的な例である．KnowItAll では，関係抽出のためのおける提案手法は先行研究 [21] の手法を拡張したものであるが，パターン（例：capitalOf 関係に対して「is the capital of」な

大量のテキストを処理するために文字列処理のみを用いて速度ど）を用いて関係抽出を開始し，得られた出力を新たな入力とを重視している点，多言語展開を可能とするため Freebase [2]

して反復を行うブートストラッピング法 [17] によって新たなパではなく WordNet [9] を用いている点で大きく異なる．また，ターンを学習することで，関係タプル（例：Tokyo, capitalOf,

次章では，得られた関係のスコア（確信度）を確率的に決定し，Japan の 3 つ組）の数を拡大していく．KnowItAll では Web

より明確な意味を持つ関係に高いスコアを与える手法を提案

検索クエリを用いて Web ページを取得するため処理に時間がする．

かかるが，TextRunner [1] は KnowItAll の非効率さを改善す

3. 1 人が行う関係の学習と推測るため，Web コーパスをあらかじめ全て取得してから処理を概念（クラス）とは，あるエンティティのまとまりを抽象化行う．また，彼らは文献 [7] において，抽出した関係タプルがし，共通する意味・性質を表したものである．たとえば，「東京

実際の Web の文書中にどのような構文を伴って出現するかを大学」や「京都大学」，「大阪大学」といったエンティティ群に検証することにより，精度および網羅性の向上を図っている．

対し，共通した意味として「大学」や「教育機関」といったも

WOE [20] では，Wikipedia を信頼できる情報として用いるこのが概念となる．また，「大阪大学」「大阪城」「通天閣」といっとで，TextRunner よりも高い精度で関係抽出を達成している．

たエンティティ群に対しては，概念は「大阪に存在する建造物」

Bollegala らの Relational Duality [3] では，関係を表す方法となどが該当する（注 1）．1 つのエンティティには様々な上位の概念

して，関係パターン（例：「is the capital of」）と語句ペア（例：が存在し，他のエンティティとの共通点や相違点およびその他「Tokyo」「Japan」）の 2 つの側面があることを利用し，完全にの関係は多くの場合，この概念を介して表現される．概念を介教師なしでの関係抽出を実現している．これらの Web コーパ

して関係を学習することで，人は未知の事物を認識・理解する

スからの関係抽出手法では，1) いかに多くの事実関係を 2) 精ことができる [14]．

度良く抽出するか，という 2 点に注視しているが，アプリケー

以下では，人がどのように概念間の関係を学習するかについションにおいて未知の語句や関係に対応するためには，クラスて簡単に説明する．たとえば，「イチローがヤンキースに移籍す間の関係を充実させる必要がある．本研究では，未知の語句やる」という文があったとする（図 1）．人はこの文を観測した関係に対する推測能力をコンピュータに持たせることを目標ととき，「イチロー」，「ヤンキース」といったエンティティを概念

し，エンティティ間の関係ではなくクラス間の関係の抽出を第「野球選手」，「球団」などを通して認識する．このとき，単に一の目的としている．

「イチローがヤンキースに移籍する」というエンティティ間のまた最近では，本研究と同様にクラスに注目した大規模かつ関係のみならず，「野球選手が球団に移籍する」という概念間のドメイン非依存な関係抽出も行われている．NELL [5], [13] では，名詞句がどのようなクラスを持っているか，およびどのようなクラス間の関係があるかを同時に抽出している．ReVerb [8]（注 1）：なお，組織としての大阪大学と単なる建造物としての大阪大学は別のエンティティであるとする見方もあるが，ここでは区別しないものとする．

習方法にならい，本研究では，テキストから関係を抽出する際に，語句をクラスに置き換えて関係を抽出する手法を提案する．
提案手法では，入力として Web コーパスを与えると，クラス間の関係とその出現頻度が出力として得られる．
提案手法の処理の流れを図 2 に示す．まず，Web コーパスに出現する語句をトライ辞書によって抽出し，語句間に出現する
文字列パターンを関係として取得する．その後，語句をクラスに置き換えることで，クラス間の関係を抽出する．以下では提案手法で使用する前提知識，および図 2 の各処理について説明する．

3. 3 使用する前提知識
図1

概念（クラス）間の関係の学習本研究では，自然言語処理技術を用いない代わりに，既に構関係が存在しうることも学習する．また，別の文「高橋尚成が築されている知識を利用してテキストから語句を抽出しクラス

パイレーツに移籍する」を観測したときにも，同様の関係を学に置き換えることで，様々なドメインのクラス間の関係を抽出習する．同じ概念間の関係をより多く観測すればするほど，そする．具体的には，提案手法では Wikipedia（注 3），WordNet [9]，の関係が一般的であると認識するようになる．一度概念間の関および YAGO [11], [18] の知識を利用する．

係を学習すれば，以降は未知の語句に対しても，学習した関係

Wikipedia は現時点において，世界最大規模のコンテンツ量をもとにその語句の意味を推測できるようになる．たとえば，を誇る Web 事典である．Wikipedia では，幅広い分野につい「モラレスがマリナーズに移籍する」という文に対し，モラレて，一般的なエンティティから新しいエンティティに至るまで

スが何かを知らない人でも，モラレスが野球選手であるという記事が網羅されており，その記事（エンティティ）数は，2013

推測が可能である．

年 1 月時点において，最も多い英語版で 411 万，日本語版でこのように，文章を観測するたびにエンティティを概念に置

83 万である．また，本研究で Wikipedia を用いる別の理由とき換えることで，人は概念間の関係を学習していく．もちろん，

して，Wikipedia のアンカーテキストが語義曖昧性解消（語句

実際には人はこれよりもはるかに複雑なプロセスを経て言葉のからエンティティへの置き換え）のリソースとして活用できる

意味を理解・学習していると考えられるが，根本的には，こうことが挙げられる．さらに，Wikipedia が世界中の様々な言語した概念への置き換えが関係の学習において重要な役割を果たで展開されていることも理由の一つである．同じエンティティ

している．

に関する記事どうしが言語間リンクでつながってることから，

コンピュータがクラス（概念）間の関係を学習する際にこの多言語展開が実現可能となる．

ような概念への置き換えを用いることの利点としては，実際のWordNet は心理学に基づく包括的な概念体系を有しており，

テキストに出現するような関係を取得できることが挙げられる．

WordNet で定義されているクラス（WordNet ではシンセット

クラス間の関係を抽出するための手法として，直接クラスを意と呼ばれる）を基準とした関係を定義することは，クラス間の味する語句が出現するテキストから関係を抽出する方法が考え

関係抽出において重要な第一歩となりうる．提案手法では，語句られる．しかし，実際のテキストでは，直接クラスを意味する

間の関係において，Wikipedia のエンティティを介して語句を語句が出現する関係は，クラスに属するエンティティを意味す

WordNet のクラスに置き換える．ここで，語句から Wikipedia

る語句が出現する関係と比較すると少ない．たとえば，2013 年のエンティティへの変換は Wikipedia の情報のみを用いて実行

2 月 15 日時点では Web のテキストには「tennis player beat

できるが，Wikipedia のエンティティから WordNet のクラス

tennis player」が 2 件，
「person graduated from educationalへの変換は，Wikipedia と WordNet をそのまま用いただけで．一方，は実行できない．そこで本研究では，YAGO で定義されている「Maria Sharapova beat Sara Errani」や「George W. Bush

上位下位関係の情報を利用する．YAGO の上位下位関係の精

graduated from Yale University」など，具体的なエンティティ

度は 98%を超えているため，これを利用することで Wikipediaを伴う関係は多くのテキストに出現していた．このことから，のエンティティから WordNet のクラスへの精度の高い置き換

クラスに属するエンティティを意味する語句が出現する関係をえが可能となる．

（注 2）

institution」にいたっては全く存在していなかった

抽出し，語句をクラスに置き換えることで，実際のテキストに

3. 4 トライ辞書による語句間の関係抽出

出現する語句（あるいはエンティティ）間の関係を網羅できる提案手法では，Web コーパスが入力として与えられたときようなクラス間の関係を抽出できると考えられる．

に，はじめの処理として語句（Wikipedia のアンカーテキスト）

3. 2 手法の概要を抽出する．そして，2 つの語句が近接して出現する箇所から，前節で述べた，人が行っている概念（クラス）間の関係の学語句の間に出現する文字列パターンを抽出し，語句間の関係を抽出する．大量のテキストを入力とした関係抽出では，精度向（注 2）：Web 上のテキストの検索には Google（http://www.google.com/）を使用した．

（注 3）：http://www.wikipedia.org/

図 2 提案手法の処理の流れ上のため，一般的に構文解析あるいは形態素解析を用いてヘッることで，Wikipedia を整理する役目を持っている．そのため，

ドワード（名詞句の意味の中心となる部分）を検出し，語句間これらの語句（アンカーテキスト）は全て Wikipedia のエンの関係を抽出する．先行研究 [21] においても形態素解析を用いティティに置き換えることが可能となる．

た手法により語句間の関係を抽出しているが，本研究では，そ3. 5 語句からクラスへの置き換えのような自然言語処理技術を用いず，文字列処理のみを行う．

提案手法では，抽出した語句間の関係において，語句をクラ

これは，本研究では様々なドメインの多様な関係を網羅するた

スに置き換えることでクラス間の関係を得る．ここで問題とめに，膨大なテキストを対象とし，抽出できる関係の絶対数をなるのが，曖昧性のある語句の処理である．すなわち，語句を増やす必要があるためである．現状では，Web 上に存在するテ

クラスに置き換える際に，語義曖昧性解消（語句からエンティ

キストの量は，自然言語処理技術を適用できる量を圧倒的に凌ティへの置き換え）を行う必要がある．しかし，語義曖昧性解駕しているため，本研究ではあえて自然言語処理処理技術を使消は（手法にもよるが）トライ辞書による語句抽出や形態素解

用せずに処理速度を重視したアプローチを採用する．なお，次析などと比較して重い処理であるため，今回のような膨大なテ

章では，得られた関係のスコアリングにより，精度をできる限

キストを処理する場合，適用が難しい．

り維持することを目指す．

そこで提案手法では，曖昧性のない語句のみを対象とするこ本研究では英語を対象としているため，具体的にはまず，とで語義曖昧性解消の問題を回避する．これは，膨大なテキス

Web ページに対して英単語 the を用いた簡単な言語判定を行

トからの関係抽出では，時間をかけて精度を重視した処理を行い，Web ページが英語で記述されているか否かを判定する．そうよりも，簡単な処理だけで高い精度を達成できそうな箇所のして，Wikipedia のアンカーテキストを語句としてトライ辞書

みから関係を抽出するアプローチをとるほうが効率的であるたを構築し，これを用いて各 Web ページから語句が出現する箇めである．なお，将来的には，曖昧性のある語句についても処所を検出する．その後，2 つの語句が近接して出現する箇所か

理可能な手法を検討する．

ら，語句間に出現する単語（最大 K 語）を，関係を表すパター

曖昧性のない語句を判別するため，Milne らの研究 [12] なンとして抽出し，語句間の関係を得る．なお，対象言語を英語

どで用いられている Wikipedia のアンカーテキストとエンとしているため，ここでは英単語と特定の記号（「’」「,」「-」）

ティティの対応関係を利用する．前述の「ウィキ化」のとおり，のみから成る関係のみを抽出する．本研究では 12Dicts（注 4）と呼Wikipedia では記事中に登場する語句（アンカーテキスト）とばれる英単語リストを用いている．提案手法は自然言語処理技

それが意味するエンティティ（記事）がハイパーリンクにより術を用いず，また，多言語で展開されている Wikipedia を利用繋がっている．そこで，ある語句を見たとき，それがリンクさしているため，同様のアプローチにより，英語以外の多くの言れている記事に対し，出現頻度に応じた確率を割り当てる．具語でも語句間の関係抽出が可能である．

体的には，アンカーテキストを t，t のリンク先の記事を e，tWikipedia のアンカーテキストのみを抽出対象の語句としているのは，次節で後述するように語句を Wikipedia のエンティ
ティ（記事）および WordNet のクラスに置き換えるためである．Wikipedia の記事の編集方針の一つに「ウィキ化 (wikifi-

cation)（注 5）」というものがあり，記事中に登場する語句とそれが意味する記事（エンティティ）をハイパーリンクにより繋げのリンク先の記事の集合を Et とし，以下の式によりリンク確率 P (e|t) を算出する．

CountLinks(t, e)CountLinks(t, ei )e ∈Et

P (e|t) = ∑(1)iCountLinks(t, e) はアンカーテキスト t から記事 e へのリンク数である．提案手法では，P (e|t) が 95%以上の確率である場（注 4）：http://wordlist.sourceforge.net/

合，t には曖昧性がないと判断し，t を e に置き換える．それ以（注 5）：http://en.wikipedia.org/wiki/Wikipedia:WikiProject_Wikify

外の場合は t には曖昧性があるとみなし，t を含む関係においては，語句からクラスへの置き換えを行わない．
また，Wikipedia のエンティティから WordNet のクラスへの置き換えでは，YAGO の上位下位関係の知識をそのまま利用する．これらの処理により，語句間の関係から，最終的にクえる．クラスを c，関係パターンを r としたとき，PMI は以下の式により算出される．

P M I(2) (c, r) = log2

( P (c, r) )(2)

P (c)P (r)ラス間の関係，およびそれらの出現頻度を取得できる．

P (c, r) はクラスと関係パターンの同時出現確率，P (c) および

4. クラス間の関係のスコアリング手法

P (r) はそれぞれクラスの出現確率，関係パターンの出現確率である．また，関係パターンと両側のクラスの三者間に対して提案手法により，クラス間の関係とその出現頻度が出力としも，同様の考え方により PMI を算出する．関係パターンの両て得られるが，これをそのままスコアとして用いると，一般的側のクラスをそれぞれ cL ，cR ，関係パターンを r とすると，こなクラス（「person」や「group」など）がスコアの上位に出現

れら三者間の PMI は以下の式により表される．

(

しやすくなる．これは，単純に一般的なクラスを持つエンティ
ティの数が相対的に多いことに起因する．しかし，本研究では，関係の種類に適した粒度のクラスを用いることで，より人が学習するクラス間の関係に近い状態で関係を定義することを目指している．たとえば，関係の種類に適した粒度のクラスの例
として，「person wrote X」という関係においては，X に対して書き物全般を表す「writing」といったクラスを定義する一方，「lawyer wrote X」という関係においては，法律家が書く物として X に「law」などのより詳細な書き物のクラスを定義す
るほうが人にとっては自然な認識であると考えられる．また，「musician wrote X」という関係では，X に対して「song」といったクラスが当てはまると考えられる．このとき，単純に出現頻度をスコアとして用いた場合，人の間で伝達されるあらゆるものという意味として「communication」といった一般的なクラスがスコアの上位に出現しやすくなる．これは関係としては誤りではないが，「communication」よりも限定的な意味のクP M I(3) (cL , r, cR ) = log2

P (cL , r, cR )P (cL )P (r)P (cR ))(3)

PMI では，単体での出現頻度が低い事象に対して極端なスコアを与えてしまうことが知られている [4]．この問題を解決する
ため，LPMI や NPMI といったスコアリング手法が提案されている．LPMI では，二者間あるいは三者間の関連の強さを表す PMI に対し，それらが同時に出現する頻度を掛け合わせる
ことでスコアを調整する．二者間については，クラス c と関係パターン r が同時に出現する頻度を F req(c, r) とすると，

LP M I(2) (c, r) = P M I(2) (c, r) · F req(c, r)(4)

により LPMI が算出される．三者間の場合 ，関係パターンの
両側のクラス cL ，cR と関係パターン r が同時に出現する頻度
を F req(cL , r, cR ) とすると，LPMI は以下の式により計算できる．

ラスを用いても関係を定義できるため，クラスの粒度としては

LP M I(3) (cL , r, cR ) = P M I(3) (cL , r, cR ) · F req(cL , r, cR )あまりふさわしくないと考えられる．関係の種類に適した粒度(5)のクラスを取得するためには，その関係にのみ出現していることが重要な指標となる．

NPMI は，PMI の最大値が 1 となるよう正規化した値であ

そこで本研究では，クラスの粒度を考慮してクラス間の関係

り，単体での出現頻度によるスコアの偏りを軽減できる．二を定義するため，関係（関係パターンとその両側のクラス）の者間あるいは三者間の NPMI はそれぞれ以下の式により表さ

出現頻度だけでなく，クラスあるいは関係パターンの単体でのれる．

出現頻度を考慮したスコアリング手法を提案する．具体的には，

N P M I(2) (c, r) =自己相互情報量（PMI），ローカル PMI（LPMI）[10]，正規化

P M I(2) (c, r)−log2 P (c, r)

PMI（NPMI）[4] をそれぞれ導入する．これらの指標を用いる
ことで，ある関係においてどれだけ偏って（関連して）出現しN P M I(3) (cL , r, cR ) =ているかを算出できる．

PMI は，クラスあるいは関係パターンがそれぞれ単体で出現する確率と，それらが同時に出現する確率を用いたスコアリン
グ手法である．なお，ここでいう出現確率とは，あるクラスあるいは関係パターンの出現頻度を，全体の出現頻度の和で除算した値である．クラスと関係パターンが独立に出現している場
合，クラスと関係パターンの同時出現確率は，クラスと関係パ
ターンそれぞれの単体での出現確率の積で表される．一方，クラスと関係パターンが関連して出現している場合，同時出現確
率は単体での出現確率の積に対して大きくなる．PMI では，より強く関連して出現するクラスと関係パターンに対して高いスコアを与える．
まず，関係パターンとその片側のクラスの二者間について考P M I(3) (cL , r, cR )−2log2 P (cL , r, cR )

(6)

(7)

5. 10 億ページからの関係抽出
先行研究 [21] では，30GB 程度の Wikipedia の全記事に対してクラス間の関係抽出を行ったが，本研究では 10 億以上のWeb ページ（約 15TB）を対象としてクラス間の関係抽出を行う．3 章で説明した手法を用いてクラス間の関係を抽出した
後，4 章で説明したスコアリングを行い，様々な観点から評価を行う．
解析対象とする Web コーパスとして，Common Crawl コー
パス（注 6）を利用した．Common Crawl コーパスは，Amazon

Web Services（AWS）で使用できる Web コーパスであり，全（注 6）：http://commoncrawl.org/

表 1 小規模なテキストデータに対する処理時間の比較

表 3 Web コーパスから抽出したクラス間の関係の精度

形態素解析を用いた手法

8,953 秒本研究

0.86

トライ辞書のみを用いた手法

1,921 秒

先行研究 [21]0.96

PATTY [15]（判定基準は異なる） 0.85
表 2 Web コーパスから抽出したクラス間の関係数
本研究

170,701,978

先行研究 [21]7,409,974

PATTY [15]350,569

サイズは 81TB である．本研究ではそのうち，15TB 程度を対象としてクラス間の関係抽出を行った．Common Crawl コーパ
スを利用してクラス間の関係抽出を行うため，Amazon Elastic

MapReduce（注 7） （Hadoop クラスタ）の環境を用いて解析を行った．実際には，3 章で説明した手法のうち，トライ辞書による語句間の関係抽出を Amazon Elastic MapReduce を用いて並列処理し，以降の処理は 1 台のローカルマシンで行った．
語句間に出現する単語数 K は 3 とした．

図3

テストセットの再現率とエラー率の関係

5. 1 処 理 時 間

対して手法を適用すると処理時間が膨大となることに起因して

約 15TB のテキストに対し，Hadoop クラスタを構成して関いる．本研究では，文字列処理のみによる高速な関係抽出によ

係抽出を行った．使用した計算機は，メモリが 7 GiB（ギビバイ

り，大規模なテキストデータへの適用を可能としている．そのト），CPU は 20 ECU（1ECU は 1.0-1.2 GHz 2007 Opteron

結果，大規模な数のクラス間の関係を取得できている．

または 2007 Xeon プロセッサの CPU 能力と同等の性能を持

5. 3 抽出した関係の精度

つ） ，プラットフォームは 64 ビットで，この計算機を 100 台抽出した関係の精度について評価するため，被験者によるサ用いて解析を行った．このとき，語句間の関係抽出にかかったンプルの判定を行った．ドメイン非依存な事実関係の抽出に関

時間は 14 時間 8 分であった．このことから，テラバイトスケーする研究 [16] や先行研究 [21] で用いられているクラスから 20

ルのテキストから高速に語句間の関係を抽出できていることが種類を基準として選び，ランダムにそれぞれ 30 件ずつ，計 600

わかる．コーパスサイズが大きく，同じテキストに対して他のの関係をサンプルとして抽出し，テストセットを作成した．被手法と処理時間の比較を行うことが困難であるため，小規模な

験者には，クラス間の関係が正しいかどうかの判定，および，

テキストデータに対して，先行研究 [21] で用いた形態素解析

正しい場合にはその関係がどの程度明確かを 1（曖昧である）かによる語句間の関係抽出手法と比較を行った．表 1 は Reuter

ら 5（明確である）の 5 段階で判定させた．たとえば，「person

Corpus RCV1（注 8）の 1997 年 6 月 1 日から 1997 年 8 月 19 日

and university」という関係は誤りではないがあまり情報を持っまでの記事に対し，高速なモデルによる形態素解析（Stanfordていない曖昧な関係であり，「person studied at university」とPOS Tagger [19], english-left3words-distsim モデル）を用いいう関係は明確な意味を持つ．具体的には，3 人の被験者のうた手法とトライ辞書のみを用いる提案手法によって語句間の関

ち，2 人以上が正しいと判定した場合に，その関係が正しいと係を抽出したときの処理時間を計測した結果である．トライ辞判断した．また，正しいと判断された関係について，被験者に書のみを用いた手法は，形態素解析を用いた手法と比較して処よる明確さの判定の中央値（一人の被験者が誤っていると判断

理時間が 4 分の 1 以下に抑えられていることがわかる．大規模した関係に対しては残り二人によるスコアの下限値）を算出し，な Web コーパスにおいても処理時間の比が変化しないことを出現頻度，PMI，LPMI，および NPMI との関係を調査した．

考慮すると，提案手法の処理速度の速さは大きな利点として機表 3 にテストセット全体の精度，図 3 に頻度，PMI，LPMI，能しているといえる．

NPMI それぞれのスコアでソートしたときのテストセットの再5. 2 抽出した関係の規模

現率（カバー率）と精度との関係を示す．なお，再現率が 0.2

約 15TB のテキストから抽出した関係の数を表 2 に示す．提以下の精度については，関係数が 120 以下と少なく，信頼でき案手法により得られたクラス間の関係は全部で 1 億 7 千万種類る値が算出できないため省いた．まず，全体でみると，本研究となり，先行研究や PATTY [15] と比較してもその規模の大きで抽出したクラス間の関係の精度は先行研究に劣っている．こさがわかる．特に，PATTY では提案手法と同様に WordNet

れは，本研究の提案手法では形態素解析を用いずに文字列処理のクラスを用いていることから，規模の観点では，得られたクのみで関係を抽出しているためであると考えられる．一方，図ラス間の関係に十分価値があるといえる．先行研究や PATTY

3 より，出現頻度や PMI，LPMI，NPMI のスコアが上位の関では，Wikipedia の全テキストを対象としてクラス間の関係抽係のみをみると，精度が向上する傾向にあることがわかる．中出を行っているが，これは，テラバイトスケールのテキストにでも，LPMI あるいは出現頻度によるスコアでソートしたとき（注 7）：http://aws.amazon.com/jp/elasticmapreduce/（注 8）：http://trec.nist.gov/data/reuters/reuters.htmlに，全般的に精度が高くなっている．
図 4 は頻度，PMI，LPMI，NPMI それぞれのスコアでソー同じ「wrote」という関係パターンでも，伴って出現するクラスによって意味合いが異なることを表している．一般的に「人が X を書いた」といえば，X には本や小説などが入ると考えられる．また，「ミュージシャンが X を書いた」の場合，X は曲である可能性が高い．さらに，「法律家が X を書いた」という場合
では，X は単なる書き物ではなく，法律という専門的な書き物であると予測できる．このように，X に関する情報を持っていなくても，X がどういうものかということを，学習したクラス
間の関係を用いることで推測できる．

6. お わ り に
図 4 テストセットの再現率と被験者による判定スコアの平均の関係

本研究では，Wikipedia から得られた語句，エンティティ，おトしたときのテストセットの再現率（カバー率）と被験者によよび WordNet のクラスを用いて，テラバイトスケールの Web

る判定スコアの平均との関係を表している．判定スコアの平均

コーパスからクラス間の関係を抽出する手法を提案した．提案が高いほど，より明確な関係が多く含まれていることを意味し手法では，Web コーパスから語句を抽出し，2 つの語句が近接ている．図 4 より，出現頻度以外のスコアにおいて上位の関係して出現する箇所から語句間の関係を抽出する．そして，得らほど，明確な関係が多くなる傾向があることがわかる．出現頻れた語句間の関係から，Wikipedia のエンティティを介して語度の高い関係がそれほど明確でないことの理由として，一般的句を WordNet のクラスに置き換えることで，クラス間の関係

すぎるクラス間の関係が多いことが挙げられる．このようなクを取得する．また，抽出した関係に対して，出現確率にもとづラス間の関係は誤りではないため単純な正誤の精度としてはくスコアリングを行い，関係の精度向上を図る手法を提案した．

高くなるが，関係の明確さという指標でみると出現頻度はス

実際に 10 億以上の Web ページ（約 15TB）から抽出した関係

コアリング手法としてあまり適していないといえる．一方で，の規模や精度，そのときの処理時間について評価を行い，提案

PMI，LPMI，NPMI では，クラスと関係パターンの関連度を手法およびそれによって抽出したクラス間の関係の有用性を確考慮しているため，あまり出現頻度が多くなくても，明確な関認した．

係に対して高いスコアを付与できる．図 3 の結果を踏まえると，

LPMI が他の手法に比べて有効であると考えられる．

今後の課題として，今回の手法で使用しなかった曖昧性のある語句の利用や，抽出した関係に対しての自然言語処理技術の以上の結果から，提案手法によって得られたクラス間の関係適用が挙げられる．提案手法では，簡単な文字列処理によっては，全体としては精度の点で従来手法に劣っているが，確率的抽出可能な関係のみに焦点を当てて関係抽出を行ったが，今後な関係のスコアリングによって上位の関係のみをみることで，はより高度な処理を，処理速度を考慮しつつ取り入れる予定で精度の問題を解決できる可能性がある．

ある．また，同じ意味を表す関係の集約，クラス間の関係の多5. 4 抽出したクラス間の関係の例

言語化を検討している．提案手法によって抽出した関係は文字抽出したクラス間の関係の中から，関係パターンと片側のク列によって表現されているため，これを意味レベルに変換，すラスをクエリとし，LPMI のスコア順に関係を 3 つ取得した例

なわち，同じ意味を持つ関係を 1 つにまとめて定義することで，を表 4 に示す．太字はクエリによって得られたクラスを表してより汎用性のある知識として利用できる．また，クラス間の関いる．表 4 より，各クエリに対して，やや不適切な関係も一部

係の多言語化についても，同じ意味を持つ関係を，言語の枠をみられるが，多くの場合，適当な粒度でクラスが取得できてい超えて定義することにより実現できると考えられる．

ることがわかる．たとえば，本論文の背景では「テニス選手がテニス選手を破る」という例を紹介したが，「tennis player beatX（テニス選手が X を破る）」というクエリに対して，出現頻度
や PMI などのスコアが最も高いクラスが「tennis player」となっている．また，「X acquired company」というクエリに対し，「company」というクラスの PMI，LPMI，NPMI の各ス
コアが最も高くなっている．この例では，「company」よりも出現頻度が多い「institution」や「organization」は，クラス単体
での出現頻度が大きいため，PMI，LPMI，NPMI の各スコアが低くなり，結果として「company」という適当な粒度でクラスを取得できている．
「wrote」という関係パターンに注目すると，「person wrote

X」，「musician wrote X」，「lawyer wrote X」という各クエリに対して，それぞれに適したクラスが得られている．これは，謝辞

本研究の一部は，日本学術振興会特別研究員奨励費(24-807) の助成によるものである．ここに記して謝意を表す．
文

献[1] M. Banko, M.J. Cafarella, S. Soderland, M. Broadhead, andO. Etzioni, “Open Information Extraction from the Web,”
Proc. of IJCAI, pp.2670–2676, 2007.
[2] K. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor, “Freebase: A Collaboratively Created Graph Database
For Structuring Human Knowledge,” Proc. of SIGMOD,
pp.1247–1249, 2008.
[3] D.T. Bollegala, Y. Matsuo, and M. Ishizuka, “Relational
Duality: Unsupervised Extraction of Semantic Relations between Entities on the Web,” Proc. of WWW, pp.151–160,
2010.
[4] G. Bouma, “Normalized (Pointwise) Mutual Information in
Collocation Extraction,” Proc. of GSCL, pp.31–40, 2009.
[5] A. Carlson, J. Betteridge, B. Kisiel, B. Settles, E.R.

表4
クエリ

X acquired company

institution is based on X

person graduated from X抽出したクラス間の関係の例
クラス間の関係

出現頻度

country attacked X

X adjacent to urban area

person wrote X

musician wrote X

lawyer wrote X

[6]

[7]

[8]

[9]
[10]

[11]

[12]

NPMI

9.1145 5924.3992 0.2052

institution acquired company

703

8.2089 5770.8676 0.1858

organization acquired company

703

7.1760 5044.7589 0.1624

institution is based in region

302

4.0894 1234.9977 0.0877

institution is based in location

302

3.9204 1183.9725 0.0841

institution is based in district

271

4.1120 1114.3511 0.0876

person graduated from educational institution

65

6.1243398.0786 0.1199

person graduated from body64

5.4762350.4746 0.1072

person graduated from institution

65

2.9981

194.8778 0.0587

pioneer invented electronic device

36.259318.7779 0.1044

3

6.259118.7774 0.1044

interior designer invented electronic device

36.208418.6253 0.1036

company was founded by executive

20

6.9602

139.2037 0.1278

company was founded by administrator

20

6.4629129.2584 0.1187

company was founded by head20

6.1806

123.6125 0.1135

country attacked ethnic group56.584932.9243 0.1126

country attacked state55.236526.1823 0.0896

country attacked political unit

55.234726.1733 0.0895

location adjacent to urban area

92.684824.1630 0.0473

highway adjacent to urban area

2

8.637817.2757 0.1414

7

2.455317.1872 0.0427

region adjacent to urban area
tennis player beat X

LPMI

650

X invented electronic device originator invented electronic devicecompany was founded by X

PMI

company acquired company

tennis player beat tennis player

193 15.0577 2906.1371 0.3142

tennis player beat champion

177 12.6894 2246.0303 0.2634

tennis player beat rival

177 12.5984 2229.9152 0.2615

person wrote novel

75.032635.2281 0.0875

person wrote fiction

7

4.809733.6676 0.0837

person wrote literary composition

7

4.758433.3087 0.0828

musician wrote music

67

8.1238544.2951 0.1594

musician wrote auditory communication

67

8.0711

540.7637 0.1583

musician wrote song48

9.1085437.2096 0.1754

lawyer wrote law

2 10.3136

20.6272 0.1688

lawyer wrote fundamental law

2 10.3136

20.6272 0.1688

lawyer wrote statesman

314.4220 0.0802

Hruschka, and T.M. Mitchell, “Toward an Architecture
for Never-Ending Language Learning,” Proc. of AAAI,
pp.1306–1313, 2010.
O. Etzioni, M. Cafarella, D. Downey, A.M. Popescu,
T. Shaked, S. Soderland, D.S. Weld, and A. Yates, “Unsupervised Named-Entity Extraction from the Web: An
Experimental Study,” Artiﬁcial Intelligence, vol.165, no.1,
pp.91–134, 2005.
O. Etzioni, A. Fader, J. Christensen, S. Soderland, andMausam, “Open Information Extraction: The Second Generation,” Proc. of IJCAI, pp.3–10, 2011.
A. Fader, S. Soderland, and O. Etzioni, “Identifying Relations for Open Information Extraction,” Proc. of EMNLP,
pp.1535–1545, 2011.
C. Fellbaum, WordNet: An Electronic Lexical Database,
The MIT Press, 1998.
H.H. Hoang, S.N. Kim, and M.Y. Kan, “A Re-examinationof Lexical Association Measures,” Proc. of MWE, pp.31–39,
2009.
J. Hoﬀart, F.M. Suchanek, K. Berberich, E. Lewis-Kelham,
G. de Melo, and G. Weikum, “YAGO2: Exploring andQuerying World Knowledge in Time, Space, Context, andMany Languages,” Proc. of WWW, pp.229–232, 2011.
D. Milne and I.H. Witten, “Learning to Link with
Wikipedia,” Proc. of CIKM, pp.509–518, 2008.

4.8073[13] T.P. Mohamed, E.R.H. Jr., and T.M. Mitchell, “Discovering Relations between Noun Categories,” Proc. of EMNLP,
pp.1447–1455, 2011.
[14] G.L. Murphy, The Big Book of Concepts, The MIT Press,
2002.
[15] N. Nakashole, G. Weikum, and F. Suchanek, “PATTY: A
Taxonomy of Relational Patterns with Semantic Types,”
Proc. of EMNLP, pp.1135–1145, 2012.
[16] M. Paşca, “Organizing and Searching the World Wide
Web of Facts - Step Two: Harnessing the Wisdom of the
Crowds,” Proc. of WWW, pp.101–110, 2007.
[17] E. Riloﬀ and R. Jones, “Learning Dictionaries for Information Extraction by Multi-Level Bootstrapping,” Proc. of
AAAI, pp.474–479, 1999.
[18] F.M. Suchanek, G. Kasneci, and G. Weikum, “YAGO: A
Core of Semantic Knowledge,” Proc. of WWW, pp.697–706,
2007.
[19] K. Toutanova, D. Klein, C.D. Manning, and Y. Singer,“Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network,” Proc. of HLT-NAACL, pp.252–259, 2003.
[20] F. Wu and D.S. Weld, “Open Information Extraction using
Wikipedia,” Proc. of ACL, pp.118–127, 2010.
[21] 白 川 真 澄, 中 山 浩 太 郎, 荒 牧 英 治, 原 隆 浩, 西 尾 章 治 郎,
“Wikipedia と Freebase の知識を利用したテキストからの上位概念間の関係抽出,” WebDB Forum, 2012.