論文
DBSJ Letters Vol.6, No.2――――――――――――――――――――――――――――――――――――

継承関係と同位関係に基づく概念階層の Web からの抽出
Inheritance and Coordinate Relation-based
Concept Hierarchy Extraction from the Web

服部 峻♥
小山 聡♦

大島 裕明♦
田中 克己♦

Shun HATTORI Hiroaki OHSHIMA
Satoshi OYAMA Katsumi TANAKA

概念間の階層関係は自然言語処理システムにおいて非常に重要な知識の一つであり，Web などの大量の文書コーパスをテキストマイニングすることで概念階層を自動的に抽出するための研究が盛んに行われている．従来手法の多くは，ある上位語 x とその下位語 y との上位下位関係抽出に対して，「“y は x の一種である”といった特定の構文パターンに合致する記述が文書コーパス中に多く含まれている」という十分条件に基づく．より厳密な構文パターンを用いると適合率は高いが再現率は低く，より緩い構文パターンを用いると再現率は改善されるが適合率を著しく損なう．本稿で我々は，再現率を改善しつつ適合率もより高く維持するために，上位下位関係の必要十分条件として概念間の性質の継承関係に基づいて，Web から概念階層を抽出する手法を提案する．
ある概念の下位概念を求める場合，まず，緩い構文パターンなどで下位概念候補を広く（やや粗く）求め，次に，対象の概念と各候補の典型的な性質を求めた上で，対象の概念から各候補へ性質が継承される度合いを算出し，対象の概念の確かに下位概念である相応度を評価する．さらに，対象の概念から各候補の同位概念への性質の継承度も加算することで，よりロバストに概念間の上位下位関係を抽出できる．
Concept hierarchies, such as hyponymy and meronymy,
are indispensable for natural language processing (NLP)
systems. Many researchers have studied how to extract
concept hierarchies from a very large corpus of documents,
such as the Web. Almost all of their methods use some
sort of lexico-syntactic pattern, e.g., “y is a kind of x”, as
not a necessary but sufficient condition of conceptual
relations. Such methods usually achieve enough highprecision but too low recall if using stricter patterns, andhigh recall but too low precision if using looser patterns.
In this paper, we assume property inheritance relations
between concepts to be necessary and sufficient conditionsof hyponymy to achieve high recall and not low precision,and propose a novel method to robustly extract hyponymy
relations from the Web based on two degrees of property
inheritance not only between a target concept and acandidate for its subordinate concepts but also between it
and the coordinate concept of the candidate.
♥学生会員 京都大学大学院情報学研究科博士後期課程
hattori@dl.kuis.kyoto-u.ac.jp♦
正会員 京都大学大学院情報学研究科{ohshima, oyama, tanaka}@dl.kuis.kyoto-u.ac.jp

1

1. はじめに概念間の上位下位（is-a）関係や部分全体（has-a）関係といった意味的な階層関係は，情報検索における検索質問の拡張・修正[1]，質問応答[2]や機械翻訳，セマンティック Webなどにおける知識の共有・再利用，テキストマイニングによるオブジェクトの情報抽出など，様々な自然言語処理システムにとって非常に重要な知識の一つである．オブジェクトの外観情報抽出[3]の場合，例えば「カワセミ」の外観情報は，「青い鳥」「美しい鳥」などと「カワセミ」の上位語である「鳥」と，或いは，「青い羽」「長い嘴」などと「カワセミ」の構成要素である「羽」や「嘴」と外観修飾句のペアで記述されることが多く，対象のオブジェクト名の上位語や部分語が利用できれば，より効率的に抽出することが可能になる．
上位下位関係の有無を判断する方法として，Miller ら[4]は，「英語常用者が“y is a (kind of) x”という表現を受け入れられるならば，概念 y は概念 x の下位概念である（概念 x は概念 y の上位概念である）」と定義している．
Webや新聞記事などの大量の文書コーパスから上位下位関係を抽出する従来手法の多く[5-10]は，Millerらの定義の近似として，「“x such as y”などの構文パターンに合致する記述が文書コーパス中に多く含まれているならば，概念yは概念xの下位概念である」という仮説に基づいている．この仮説が成り立つような構文パターンを様々に用意できれば，任意の概念間における上位下位関係の有無を高い適合率で判定可能である．一方で，この仮説が真であったとしても，「構文パターンに合致する記述が文書コーパス中に多く含まれる」ことは，「概念yが概念xの下位概念である」ことの十分条件でしかなく必要条件ではないため，たとえ「概念yは概念xの下位概念である」ことが真であったとしても，必ずしも「構文パターンに合致する記述が文書コーパス中に多く含まれる」とは限らない．従って，高い適合率を実現するために厳密な構文パターンだけを用意すると，その構文パターンに合致する記述が文書コーパス中で少なくなり，本来は上位下位関係を持つ概念間に対して上位下位関係が無いと誤判定する危険性が増し，再現率を損なうというトレードオフの問題が付き纏う．ある程度の再現率を確保するために緩い構文パターンを使用し，適合率が悪化することは妥協している場合も多い．Hearstら[5]によって，上位下位関係を表現する構文パターンを発見する手法も提案されてはいるが，十分条件に基づく手法であることの問題は根本的に残る．
文書コーパスから上位下位関係を抽出する際，再現率を改善しつつ，適合率も高く維持するためには，十分条件だけでなく必要条件も用いる必要があると考える．そこで，我々は，「概念 y は概念 x の下位概念である」という上位下位関係の必要条件として，「概念 y が概念 x の性質を全て継承する」という性質の継承関係を仮定する．この仮説は，オブジェク
ト指向方法論におけるクラス間でのデータメンバ（属性）とメソッド（振る舞い）の継承関係[11]や，属性分析法における事象階層構造での属性遺伝[12]に裏付けされている．
本稿で我々は，上位下位関係の必要十分条件として概念間の性質の継承関係を仮定し，ある概念間に対して，各々の概念の典型的な性質を求めた上で，互いへ性質が継承される度合いを算出することで，上位下位関係リンクを付与すべきか否かの相応度を評価する．さらに，一方を上位概念と仮定した場合に，他方への性質の継承度だけで評価するのではなく，その同位概念への性質の継承度も加算することで，概念間の上位下位関係をよりロバストに抽出する手法を提案する．

日本データベース学会 Letters Vol.6, No.2

論文
DBSJ Letters Vol.6, No.2――――――――――――――――――――――――――――――――――――
2. 性質の継承関係に基づく下位概念の抽出

3. 語の同位関係に基づく下位概念の抽出

本章では，概念間の上位下位関係の必要十分条件として，「下位概念 y は上位概念 x の性質の全てを継承する」という概念間の性質の継承関係を仮定することで，構文パターンや文書構造を十分条件として仮定する従来手法よりも精度良く上位下位関係を Web から抽出する手法について提案する．
ある概念 x が与えられた場合に，その下位概念をできる限り漏れなく含む下位概念候補集合 Y を収集した上で，対象の概念 x から各下位概念候補 yi への性質の継承度に基づいてランキングし，概念 x の下位概念を Web から抽出する手法について述べる．以下の四つのステップから成る．
Step 1. 概念 x の下位概念候補集合の収集：「“yi は x である”に合致する記述が多いほど，概念 yiは概念 x の下位概念である」といった構文パターンに基づく仮説や「概念 x をタイトルに含む文書中に下位概念 yiが出現し易い」といった文書構造に基づく仮説などの中から，やや緩い十分条件を仮定して，概念 x の下位概念候補集合 Y をできる限り網羅的に Web から収集する．
Step 2. 概念 x および下位概念候補の性質の抽出：
各概念の持つ性質として，オブジェクト指向に則り，属性名と振る舞いを想定している．オブジェクトの外観情報抽出[3]で用いたオブジェクトの構成要素名の抽出手法を本稿でも利用する．概念 x の典型的な性質を求めるには，まず，[x の]という検索クエリを画像検索エンジンで実行し，検索された画像の周辺テキスト中で“x の”に続く名詞や動詞を概念 x の典型的な性質候補 pj とし，概念 x の性質としての典型度 propertyx(pj)を次式により評価する．
propertyx(pj) := if([x の pj])/if([x の pj])
但し，if([q])は，画像検索エンジンで検索クエリ q を実行した検索結果件数である．文書検索エンジンではなく，画像検索エンジンを使うのは，写真の題目を記述する語句が概念 x の性質を表していることが多いという観測に基づく．
Step 3. 概念 x から下位概念候補への性質の継承度の算出：
概念 x から下位概念候補 yi への性質の継承度 inheritx(yi)を評価するには，概念 x の上位 n 件の性質の集合 Pn(x)を元に，各々に対する典型度によって n 次元性質ベクトルを生成し，両者の性質ベクトル間の内積値により定義する．
inheritx(yi) := Σpj∈Pn(x) propertyx(pj)・propertyyi(pj)Step 4. 下位概念候補の概念 x に対する相応度の評価：
下位概念候補 yi に対して，概念 x の下位概念としての相応度 hyponymx(yi)を次式で定義し，概念 x の下位概念候補集合 Y 全体をそれぞれの相応度に基づいてランキングする．
hyponymx(yi) := inheritx(yi)

本章では，上位概念から下位概念への性質の継承関係に加えて，概念間の同位関係も考慮することで，前章で提案した性質の継承関係だけに基づく Web から上位下位関係の抽出手法よりもロバスト性の改善が図られている．
前章では，「下位概念 yi は上位概念 x の性質全てを継承する」という仮説を用いたが，本章の改良手法は，「概念 yi が概念 x の下位概念ならば，概念 x を上位概念とする概念 yiの同位概念 yiｃが存在し，概念 yi だけでなく同位概念 yiｃも上位概念 x の性質を全て継承する」という仮説に基づく．
ある概念 x が与えられた場合に，その下位概念をできる限り漏れなく含む下位概念候補集合 Y を収集した上で，対象の概念 x から各下位概念候補 yi および yi の同位概念 yiｃへの性質の継承度の総和に基づいてランキングすることで，概念 xの下位概念をより精度良く Web から抽出する手法について述べる．以下の五つのステップから成る．
Step 1. 概念 x の下位概念候補集合の収集：
前章の Step 1.と同様に，やや緩い構文パターンや文書構造に基づく仮説を用いて Web から網羅的に収集する．
Step 2. 概念 x における下位概念候補の同位概念の抽出：
下位概念 yi の同位概念のうち，対象の概念 x を上位概念として持つ同位概念 yiｃを求める．大島ら[13]の同位語抽出手法を利用して，対象の概念 x を上位概念として持つ同位概念としての相応度 coordinatex,yi(yiｃ)の値が最大となるyiｃを下位概念候補 yi の同位概念として採用する．
coordinatex,yi(yiｃ) := yax (yi, yiｃ)・yax (yiｃ,yi,)yax (yi, yiｃ) := df([“yi や yiｃ” AND x])
yax (yiｃ,yi,) := df([“yiｃや yi” AND x])
但し，df([q])は，文書検索エンジンで検索クエリ q を実行した検索結果の件数を表す．
Step 3. 概念 x，下位概念候補，同位概念の性質の抽出：
新たに登場した同位概念についても，前節の Step 2.と同様に処理して典型的な性質を求める．
Step 4. 概念 x から下位概念への性質の継承度の算出：
概念 x から下位概念候補 yi およびその同位概念 yiｃへの性質の継承度を，前節の Step 3.と同様にして計算する．
Step 5. 下位概念候補の概念 x に対する相応度の評価：
下位概念候補 yi に対して，概念 x の下位概念としての相応度 hyponymx(yi)を次式のように，下位概念候補 yi への性質の継承度とその同意概念 yiｃへの性質の継承度との総和によって定義し，概念 x の下位概念候補集合 Y 全体をそれぞれの相応度に基づいてランキングする．
hyponymx(yi) := inheritx(yi) + inheritx(yic)

図 1 性質の継承関係に基づく下位概念抽出
Fig.1 Subordinate Concept Extraction based on
Property Inheritance Relations

図 2 語の同位関係も考慮した下位概念抽出
Fig.2 Subordinate Concept Extraction based onInheritance and Coordinate Relations2

日本データベース学会 Letters Vol.6, No.2

論文
DBSJ Letters Vol.6, No.2――――――――――――――――――――――――――――――――――――
本章では，2 章で述べた性質の継承関係に基づく下位概念抽出手法，及び，3 章で述べた語の同位関係も考慮した下位概念抽出手法を，「鳥」と「野菜」という二種類の概念に対して適用することで各々の下位概念を抽出した実験結果を示し，両手法の有効性について考察する．
表 1 は，「鳥」という概念の下位概念抽出として，文書コーパス（Web）中で“～は鳥である”という構文パターンに合致した語句を Google での検索件数によってランキングした結果，及び，この構文パターンに合致した 96 個の語句全てを「鳥」の下位概念の候補とした上で，「鳥」の上位 5 件の典型的な性質を継承している度合いに基づいてランキングした結果，及び，各候補の同位概念への性質の継承度も加算してランキングした結果各々の上位 10 件を比較している．
但し，「鳥」の典型的な性質を表す語句は次の順で求まり，声，さえずり，鳴き声，巣，名前，唐揚げ，夏，姿，糞，種類，群れ，歌，絵，足，形，フン，卵，…
上位 5 件を用いて「鳥」および下位概念候補に対して 5 次元の性質ベクトルを生成し，性質ベクトル間の類似度によって「鳥」から下位概念候補への性質の継承度を算出している．
また，96 個の下位概念候補の中に全部で 21 個の適合解が含まれており，図 3 では，各々の抽出手法の適合率・再現数のグラフを描いている．提案した両手法とも，ベースラインである構文パターンに基づく手法の精度以上を常に保っている．再現数 21（再現率 1.0）での適合率を比較すると，構文パターンに基づく手法が 0.21 であるのに対し，性質の継承関係を用いることで 0.35 に改善し，さらに，語の同位関係も考慮することで 0.49 までに改善できている．

次に表 2 は，「野菜」という概念に対して，表 1 と同様に三種類の下位概念抽出手法による結果各々の上位 10 件を表している．但し，「野菜」の典型的な性質は次の順に求まり，サラダ，スープ，味，甘み，苗，煮物，カレー，収穫，旨み，種，旨味，花，栽培，煮込み，…
上位 5 件を用いて「野菜」と下位概念候補に対して 5 次元の性質ベクトルを生成し，性質ベクトル間の類似度によって「野菜」から下位概念候補への性質の継承度を算出している．
また，57 個の下位概念候補の中に全部で 17 個の適合解が含まれており，図 4 は，各々の抽出手法の適合率・再現数のグラフである．再現数 2 を除いては，提案した両手法とも，ベースラインである構文パターンに基づく手法の精度以上を保っている．性質ベクトルを精査すると，「野菜」の上位 5件の性質の中で「サラダ」しか「パパイヤ」は典型的な性質として持っていないにも関わらず，「サラダ」次元を通じての類似度への影響が十分に他よりも大きかったために「野菜」の下位概念として上位にランクされ，一方，「野菜」の上位 5 件の性質に対して万遍無く「オクラ」は典型的な性質として持っているにも関わらず，各次元を通じての類似度への影響が十分に大きくはなかったために総和しても「野菜」の下位概念として下位にランクされてしまっている．本稿では，単純な内積に基づく類似度によって性質の継承度を評価したが，コサイン類似度や，確かに継承していると判定された性質の次元数を用いるなど，改良の余地が残る。再現数 17（再現率 1.0）での適合率を比較すると，構文パターンに基づく手法が 0.30 であるのに対し，性質の継承関係を用いても全く改善しなかったが，さらに，語の同位関係も考慮することで 0.81 までに大きく改善できている．

表 1 「鳥」の下位概念抽出の上位 10 件
Table 1 Top 10 Subordinate Concepts for “tori”
構文パターン
継承関係
同位関係 [同位語]1 ペンギン
うぐいす
コマドリ [オオルリ]
2 カラス
コマドリ
うぐいす [ひばり]3 動物
ツバメ
ツバメ [スズメ]
4 カナリアカナリヤ
海猫 [カモメ]
5 我輩海猫
スズメ [カラス]6 スズメ
カラス
カラス [スズメ]
7 ハト
天馬
カナリヤ [文鳥]8 もの
スズメ
アリ [ハチ]
9 私
カナリヤ
ハト [カラス]10 兎
アリカナリア [文鳥]表 2 「野菜」の下位概念抽出の上位 10 件
Table 2 Top 10 Subordinate Concepts for “yasai”
構文パターン
継承関係
同位関係 [同位語]1 トマトナス
ナス [キュウリ]
2 スイカ
パパイヤ
パパイヤ [マンゴー]
3 食べ物
トマト
オクラ [トマト]4 源
豆
トマト [ナス]
5 イチゴエンドウ豆 イチゴ [トマト]
6 もの本来
豆 [雑穀]
7 物
にんじん
にんじん [大根]8 トウモロコシ ニンジン
ごぼう [にんじん]
9 服飾
ごぼう
エンドウ豆 [大豆]10 バナナオクラ
ニンジン [大根]図 3 「鳥」の下位概念抽出の適合率・再現数グラフ
Fig.3 Precision-Recall Graph of Subordinate Concept
Extraction for “tori” (bird)

図 4 「野菜」の下位概念抽出の適合率・再現数グラフ
Fig.4 Precision-Recall Graph of Subordinate Concept
Extraction for “yasai” (vegetable)

4. 実験結果

3

日本データベース学会 Letters Vol.6, No.2

論文
DBSJ Letters Vol.6, No.2――――――――――――――――――――――――――――――――――――
5. まとめと今後の課題
Web などの大量の文書コーパスをテキストマイニングすることで概念間の上位下位関係を抽出する従来手法の多くは，「“y は x の一種である”特定の構文パターンに合致する記述が文書コーパス中に多く含まれている」という十分条件に基づいており，より厳密な構文パターンを用いると適合率は高いが再現率は低く，より緩い構文パターンを用いると再現率は改善されるが適合率を著しく損なってしまうという問題があった．そこで，本稿で我々は，再現率を改善しつつ適合率も高く維持するために，上位下位関係の必要十分条件として概念間の性質の継承関連に基づいて，Web から概念階層を抽出する手法を提案した．ある概念の下位概念を求める
場合，まず，緩い構文パターンなどで下位概念候補を網羅的に収集し，次に，対象の概念から各候補へ性質が継承される度合いによって対象の概念の確かに下位概念である相応度を評価する．さらに，対象の概念から各候補の同位概念への性質の継承度も加算することで，よりロバストに概念間の上位下位関係を抽出する手法も提案した．
今後は，より大規模な実験によって提案手法の有効性の検証，各概念の典型的な性質の抽出精度の向上，性質の継承度の算出方法の改良を行う必要がある．また，上位下位関係だけでなく部分全体関係の抽出にも取り組んでいきたい．

[謝辞]
本研究の一部は，文部科学省研究委託事業「異メディア・アーカイブの横断的検索・統合ソフトウェア開発（研究代表者：田中克己）」，及び，文部科学省科学研究費補助金特定領域研究「情報爆発時代に向けた新しい IT 基盤技術の研究」
における計画研究「情報爆発時代に対応するコンテンツ融合と操作環境融合に関する研究」（研究代表者：田中克己，
A01-00-02, 課題番号：18049041），及び，計画研究「情報爆発に対応する新 IT 基盤研究支援プラットフォームの構築」（研究代表者：安達淳，Y00-01，課題番号：18049073），文部科学省科学研究費補助金若手研究（B）「Web からの履歴情報の発見とその呈示方式の研究」（研究代表者：小山聡，課題番号：19700091），及び，文部科学省グローバル COE
拠点形成プログラム「知識循環社会のための情報学教育研究拠点」（研究代表者：田中克己，平成 19～23 年度）による．
ここに記して謝意を表します．

[文献］[1] Mandala, R., Tokunaga, T., and Tanaka, H.: “The Useof WordNet in Information Retrieval”, Proceedings ofthe COLING ACL Workshop on Usage of WordNet in
Natural Language Processing, pp.31-37 (1998).
[2] Fleischman, M., Hovy, E. and Echihabi, A.: “Offline
Strategies for Online Question Answering: Answering
Questions Before They Are Asked”, Proceedings of the41st Annual Meeting of the Association for
Computational Linguistics (ACL'03), pp.1-7 (2003).
[3] 服部 峻, 手塚太郎, 田中克己: “オブジェクトの外観情報の Web マイニング”, 電子情報通信学会 第 18 回データ工学ワークショップ（DEWS'07）論文集, L4-6 (2007).
[4] Miller, G. A., Beckwith, R., Fellbaum, C., Gross, D.,
and Miller, K. J.: “Introduction to WordNet: An On-line
LexicalDatabase”,
International
JournalofLexicography, vol.3, no.4, pp.235-312 (1993).
[5] Hearst, M. A.: “Automatic Acquisition of Hyponyms

4from Large Text Corpora”, Proceedings of the 14th
International Conference on Computational Linguistics(COLING'92), vol.2, pp.539-545 (1992).
[6] Caraballo, S. A.: “Automatic Construction of aHypernym-labeled Noun Hierarchy from Text”,
Proceedings of the 37th Annual Meeting of theAssociation for Computational Linguistics (ACL'99),
pp.120-126 (1999).
[7] 森本貴之, 藤原 譲: “例外処理を考慮した用語間の階層・関連関係の抽出”, 情報知識学会 第 8 回研究報告会講演論文集, no.8, pp.17-22 (2000).
[8] 安藤まや, 関根 聡, 石崎 俊: “定型表現を利用した新聞記事からの下位概念単語の自動抽出”, 情報処理学会研究報告「自然言語処理」, vol.2003, no.98, pp.77-82 (2003).
[9] Emmanuel, M., Christian, J.: “Automatic Acquisitionand Expansion of Hypernym Links”, Computer and theHumanities, vol.38, no.4, pp.363-396 (2004).
[10] 大石康智, 伊藤克亘, 武田一哉, 藤井 敦: “単語の共起関係と構文情報を利用した単語階層関係の統計的自動識別”, 情報処理学会研究報告「音声言語情報処理」, vol.2006,
no.40, pp.25-30, (2006).
[11] 青木利晃, 片山卓也: “オブジェクト指向方法論のための形式的モデル”, 日本ソフトウェア科学会学会誌コンピュータソフトウェア, vol.16, no.1, pp.12-32 (1999).
[12] 王 凱軍, 池田 満, 國藤 進: “属性分析法に基づく類似性の分析”, 第 18 回人工知能学会全国大会, 2F3-02 (2004).
[13] 大島裕明, 小山 聡, 田中克己: “Web 検索エンジンのイ
ンデックスを用いた同位語とそのコンテキストの発見”,
情報処理学会論文誌（トランザクション）データベース,
vol.47, no.SIG19(TOD32), pp.98-112 (2006).

服部 峻

Shun HATTORI京都大学大学院情報学研究科社会情報学専攻博士後期課程在学中．2006 年京都大学大学院情報学研究科社会情報学専
攻修士課程修了．主にモバイル・ユビキタス環境における社会基盤技術の研究に従事．情報処理学会，電子情報通信学会，日本データベース学会各学生会員．

大島 裕明

Hiroaki OHSHIMA

京都大学大学院情報学研究科社会情報学専攻特任助教．2007
年京都大学大学院情報学研究科社会情報学専攻博士後期課
程修了．博士（情報学）．主にウェブ，情報検索，データベースの研究に従事．情報処理学会，電子情報通信学会，日本データベース学会，ACM 各会員．

小山 聡

Satoshi OYAMA

京都大学大学院情報学研究科社会情報学専攻助教．2002 年
京都大学大学院情報学研究科博士後期課程修了．博士（情報学）．主に機械学習，データマイニング，情報検索の研究に従事．電子情報通信学会，情報処理学会，人工知能学会，日本データベース学会，IEEE，ACM，AAAI 各会員．

田中 克己

Katsumi TANAKA

京都大学大学院情報学研究科社会情報学専攻教授．1976 年
京都大学大学院修士課程修了．博士（工学）．主にデータベース，マルチメディアコンテンツ処理の研究に従事．IEEE
Computer Society，ACM，人工知能学会，日本ソフトウェ
ア科学会，情報処理学会，日本データベース学会等各会員．

日本データベース学会 Letters Vol.6, No.2