# カテゴリ間の兄弟関係を活用した集合拡張
## 高瀬 翔 $\dagger$ ・岡崎 直観 $\dagger,+\dagger$ ・乾 健太郎 $\dagger$

## 集合拡張手法の多くはシードインスタンスだけを手掛かりに新たなインスタンスを 取得するものであり，対象が複数のカテゴリであっても，各カテゴリのインスタン スの収集を独立に行う。しかし，複数カテゴリを対象にした集合拡張ではカテゴリ 間の関係など，シードインスタンスとは別の事前知識も利用できる。本研究ではこ のようなカテゴリ間の関係，特に兄弟関係を事前知識として活用した集合拡張手法 を提案する。 さらに, Wikipedia から半自動で抽出したインスタンスと兄弟関係を 事前知識として実験を行い，兄弟関係が集合拡張に有用であることを示す。 \\ キーワード：知識獲得，集合拡張，ブートストラッピング，意味ドリフト \\ Set Expansion Using Sibling Relationships Between Semantic Categories

\author{
Sho TAKASE $^{\dagger}$, NAOAKI OKazaKI ${ }^{\dagger, \dagger \dagger}$ and Kentaro Inui ${ }^{\dagger}$
}

\begin{abstract}
Most set expansion algorithms are assumed to independently acquire new instances of each of the different semantic categories even when instances of multiple semantic categories are seeded. However, in the setting of set expansion with multiple semantic categories, we might leverage other types of prior knowledge about semantic categories. In this paper, we present a method of set expansion in case ontological information related to target semantic categories is available. Specifically, the proposed method uses sibling relationships between semantic categories as an additional type of prior knowledge. We demonstrate the effectiveness of using sibling relationships in set expansion on a dataset in which instances and sibling relationships are extracted from Wikipedia in a semi-automatic manner.
\end{abstract}

Key Words: Knowledge acquisition, Set expansion, Bootstrapping, Semantic drift

## 1 はじめに

自然言語の理解に向けて，常識的知識の獲得が重要である．特に意味カテゴリに属する固有表現のリストは，質問応答 (Wang and Cohen 2009), 情報抽出 (Mintz, Bills, Snow, and Jurafsky 2009)，語義曖昧性解消 (Pantel and Lin 2002)，文書分類 (Pantel, Crestan, Borkovsky, Popescu, and Vyas 2009), クエリ補完 (Cao, Jiang, Pei, He, Liao, Chen, and Li 2008) など様々なタスク


で有用である，固有表現リストを人手で構築すると多大なコストがかかるうえ，新しい実体や概念に対応できないため, 固有表現リストを（半）自動的に獲得する方法が研究されてきた.

集合拡張はある意味カテゴリに属する既知の固有表現の集合を入力とし，その意味カテゴリの未知の固有表現を獲得するタスクである。例えば「プリウス」，「レクサス」，「インサイト」という自動車カテゴリの固有表現から，「カローラ」，「シビック」，「フィット」のように自動車力テゴリに属する固有表現を新たに獲得する。なお本論文では，意味カテゴリに属する固有表現をその意味カテゴリのインスタンスと呼び，特に入力として与えるインスタンスをシードインスタンスと呼ぶ.

集合拡張には通常，ブートストラッピング手法を用いる (Hearst 1992; Yarowsky 1995; Abney 2004; Pantel and Ravichandran 2004; Pantel and Pennacchiotti 2006). ブートストラッピング手法とはシードインスタンスを用いて新たなインスタンスを反復的に獲得する手法である. ブー トストラッピング手法では，まず，コーパス中でシードインスタンスと頻繁に共起するパター ンを獲得する．例えば自動車カテゴリについて「プリウス」や「レクサス」のようなシードインスタンスから「トヨタの $\mathrm{X} 」$ やハイブリッド車の $\mathrm{X} 」$ （X は名詞句を代入する変数）のようなパターンが得られる。次にこれらのパターンと頻繁に共起するインスタンス，すなわち，パターンの変数 X 部分に多く現れる名詞句を獲得する。例えば「トヨタのX」というパターンからトヨタの自動車製品を表す語が得られる。次に新たに得られたインスタンスをシードインスタンスに加え, 再びパターンの獲得を行う。ブートストラッピング手法はこのようにパターンの獲得とインスタンスの獲得を繰り返し行うことにより, 少数のシードインスタンスから大規模なインスタンス集合を獲得する。

しかしブートストラッピング手法はシードインスタンス集合とは無関係なインスタンスを獲得してしまう場合もある。これは対象とする意味カテゴリのインスタンス以外とも共起するパターンによって引き起こされる。例えば「プリウス」や「レクサス」といったシードインスタンスから「新型の X」というパターンを獲得したとすると, このパターンを用いることにより, $\lceil\mathrm{iPad} 」$ やThinkPad」のようなシードとは無関係なインスタンスを抽出してしまう．ブートストラッピング手法において, 対象とする意味カテゴリとは無関係なインスタンスを獲得してしまう現象を意味ドリフトと呼ぶ (Curran, Murphy, and Scholz 2007). 意味ドリフトはブートストラッピング手法において非常に重大な問題である.

ブートストラッピング手法は意味カテゴリに関する事前知識をシードインスタンスという形で受け取っている. しかしながら, シードインスタンスのみで意味カテゴリを正確に表現することは難しく，意味ドリフトが引き起こされる。一方，事前知識として，Wikipedia における意味カテゴリ間の上位下位・兄弟関係に見られるように, シードインスタンス以外の知識を得られる場合がある．例えば人カテゴリに属するインスタンスは男優と女優カテゴリに同時に属することはできないという知識や, 自動車と自動二輪カテゴリという 2 つの異なったカテゴリが共通の
特徴 (例: 乗り物, ガソリン式, 陸上) と異なる特徴（例：タイヤの数, 窓の有無）を持つというような知識が入手できる。近年，テキストに非明示的な情報を推論するため, Machine Reading project (Etzioni, Banko, and Cafarella 2006)に見られるように大規模なテキストコーパスを利用し，ありとあらゆる種類の語彙知識を獲得しようとする研究が盛んである。意味カテゴリのインスタンスの収集においても， Carlson ら (Carlson, Betteridge, Kisiel, Settles, Hruschka Jr., and Mitchell 2010a)のように，複数のカテゴリを対象として同時に収集を行う需要が高まっている。このような場合には, シードインスタンス以外に, 意味カテゴリ間の関係も事前知識として利用できると考えられる。

本研究では, 複数の意味カテゴリを対象とした集合拡張において, 事前知識として意味カテゴリ間の兄弟関係を活用する手法を提案する，評価実験では，Wikipedia から抽出したインスタンスと兄弟関係を事前知識として集合拡張を行い, 兄弟関係の知識が有用であることを示す.

本論文の構成は以下の通りである。2 節では本研究のベースライン手法である Espresso アルゴリズムを概説する。また，この節では意味ドリフト問題とその対処法に関する先行研究を紹介する． 3 節では意味カテゴリの兄弟関係を追加の事前知識として活用する手法を提案する．4 節では提案手法の効果を実験で検証し，考察を行う。最後に 5 節で本論文の結論を述べる.

## 2 関連研究

## 2.1 Espresso アルゴリズム

Espresso (Pantel and Pennacchiotti 2006) は, パターンの取得とインスタンスの取得の 2 つのステップを反復する集合拡張アルゴリズムである。 パターンの取得とインスタンスの取得は共に，コーパスからの候補の抽出と，候補のランキングという同じ手順にもとづいている。候補の抽出では既に獲得したインスタンスと共起するパターン, 既に獲得したパターンと共起するインスタンスを抽出する。候補のランキングでは候補インスタンス／パターンのスコアを計算し，上位 $N$ 個の候補を採用する。 Espresso アルゴリズムでは候補パターン $p$ のスコア $r_{\pi}(p)$ と候補インスタンス $i$ のスコア $r_{\iota}(i)$ を，それぞれ式 (1) と式 (2) で計算する.

$
\begin{gathered}
r_{\pi}(p)=\frac{1}{|I|} \sum_{i \in I} \frac{\operatorname{pmi}(i, p)}{\operatorname{maxpmi}} r_{\iota}(i) \\
r_{\iota}(i)=\frac{1}{|P|} \sum_{p \in P} \frac{\operatorname{pmi}(i, p)}{\max } \operatorname{pmi} r_{\pi}(p) \\
\operatorname{pmi}(i, p)=\log _{2}\left(\frac{|i, p|}{|i, *||*, p|} \times \operatorname{discounting~factor}\right) \\
\text { discounting factor }=\frac{|i, p|}{|i, p|+1} \times\left(\frac{\min (|i, *|,|*, p|)}{\min (|i, *|,|*, p|)+1}\right)
\end{gathered}
$
$P$ と $I$ は各カテゴリにおけるパターンとインスタンスの集合である。 $|P|$ と $|I|$ はそれぞれ集合 $P$ と $I$ に含まれるパターンとインスタンスの数である. $|i, *|$ と $|*, p|$ はインスタンス $i$ とパターン $p$ のコーパス中での出現頻度であり, $|i, p|$ はインスタンス $i$ とパターン $p$ の共起頻度である. すなわち, 式 (3)における右辺第 1 項はインスタンス $i$ とパターン $p$ の自己相互情報量である. 自己相互情報量は単語間の相関の指標として一般的であるが，めったに出現しない単語に対して値が大きくなってしまうという問題がある. これに対処するため, Pantel と Ravichandran は式 (4) に示される discounting factor を導入した (Pantel and Ravichandran 2004). また, $\max$ pmi はカテゴリ内のすべてのインスタンスとパターンの pmi の最大值である. なお, 初期值としてシードインスタンスのスコアは 1.0 とする.

Espresso アルゴリズムの動作を説明する。始めに，シードインスタンスと共起するパターンを候補として抽出する。次に，式 (1)で候補パターンのスコアを計算し，上位 $N$ 個のパターンを獲得することで，対象とする意味カテゴリに対応するパターンを獲得する．インスタンスの獲得については，獲得したパターンと式 (2)を用い, 上記の手順をパターンとインスタンスを逆にして行うことで達成する。 すなわち, 獲得したパターンと共起するインスタンスを候補として抽出し, 式 (2) で高スコアのパターンとよく共起するインスタンスを獲得する.

## 2.2 意味ドリフト

ブートストラッピング手法においてシードとは無関係なインスタンスを獲得してしまい, 対象とするカテゴリから逸脱してしまう現象を意味ドリフトと呼ぶ (Curran et al. 2007). 例として，「プリウス」や「レクサス」をシードインスタンスとして持つ自動車カテゴリについて考える. Espresso アルゴリズムは何回か反復を行うと「Xの性能」や「新型のX」など多くのカテゴリのインスタンスと共起するパターン（ジェネリック・パターン）を得る。これらのパター ンを用いてインスタンスの収集を行うと，「iPad」や「ThinkPad」のようなインスタンスが抽出され得る. これらは対象とする意味カテゴリの特徴を備えておらず，シードが表そうとしている意味カテゴリとは無関係なインスタンスである。しかしながら，これらの間違ったインスタンスを獲得してしまうことで，アルゴリズムの取得するパターンは元々の想定からかけ離れたものになってしまう。

また意味ドリフトは多義性のある語によっても引き起こされる．例えば自動車メーカーのシー ドとして「サターン」や「スバル」を与えた場合，ブートストラッピング手法は「木星」や「天王星」のような星カテゴリに属するインスタンスを獲得してしまう。これは「サターン」や「スバル」に多義性があり, 自動車メーカーだけでなく天体（惑星や恒星）も表す語だからである.

小町ら (小町, 工藤, 新保, 松本 2010) は Espresso アルゴリズムをグラフ解析の観点から分析することで，ブートストラッピング手法において，意味ドリフトが本質的には回避できない問題であることを示した.

## 2.3 g-Espresso アルゴリズム

小町ら (小町他 2010) は Espresso アルゴリズムをグラフ解析として定式化し, さらに意味ドリフトへの対処として, グラフカーネルの適用を提案した. 彼らはまず, Espresso アルゴリズムを行列計算によって定式化した。なお，ここでは Espresso アルゴリズムにおける，毎回の反復において上位 $N$ 個の候補を獲得する，というステップが省略されており，全パターンと全インスタンスにスコアを付与する形になっている。インスタンスとパターンの共起行列を $M$ とし，その $(p, i)$ 要素 $[M]_{p i}$ は式 (3)の pmi を用いて，

$
[M]_{p i}=\frac{\operatorname{pmi}(i, p)}{\max \operatorname{pmi}}
$

とする。また，シードインスタンスに対応する位置の要素は 1 ，それ以外の要素は 0 である， $|I|$次元のベクトルをシードベクトル $i_{0}$ とする.

このとき， $n$ 回目の反復におけるパターンへのスコアの付与は, $p_{n}=M i_{n}$ を計算した後に $p_{n} \leftarrow p_{n} /|I|$ として正規化する操作に対応する. 同様に，インスタンスへのスコアの付与は, $i_{n+1}=M^{T} p_{n}$ を計算した後に $i_{n+1} \leftarrow i_{n+1} /|P|$ として正規化する操作に対応する. したがって, $n$ 回目の反復後に得られるインスタンスのスコアベクトル $i_{n}$ は, 式 (6) と書ける.

$
\begin{gathered}
\boldsymbol{i}_{\boldsymbol{n}}=A^{n} \boldsymbol{i}_{\mathbf{0}} \\
A=\frac{1}{|I||P|} M^{T} M
\end{gathered}
$

$I$ をノード集合, $A$ を隣接行列とした重み付き無向グラフ $G$ を考えると, 反復におけるインスタンスのスコアの更新は，シードインスタンスのスコアがグラフ上を伝播していく過程と見なすことができる。よって，グラフカーネルによりこの過程を形式化することが可能である.

小町ら (小町他 2010) はジェネリック・パターンの影響を減らし, 意味ドリフトを抑制するために，正則化ラプラシアンカーネル (Smola and Kondor 2003) を用いた. まず， グラフGのラプラシアン $L$ を式 $(8)$ によって求める.

$
\begin{gathered}
L=D-A \\
{[D]_{i, i}=\sum_{j}[A]_{i j}}
\end{gathered}
$

次に，正則化ラプラシアンカーネルを式 (10) で計算する.

$
R_{\beta}(A)=A \sum_{n=0}^{\infty} \beta^{n}(-L)^{n}=(I+\beta L)^{-1}
$

正則化ラプラシアンカーネルはそれぞれのノードに対し, 次数に応じて接するエッジの重みを減ずる．このため，ジェネリック・パターンの影響を低く抑えることができる．萩原ら (萩原,
小川，外山 2011)はこのグラフ理論によって再定式化した Espresso アルゴリズムを g-Espresso と呼び，集合拡張において意味ドリフトを抑制する効果があることを示した.

## 2.4 意味ドリフトへの対処

意味ドリフトの影響を軽減するために, 小町ら (小町他 2010) や萩原ら (萩原他 2011)の手法に加え, シードインスタンス集合の洗練 (Vyas, Pantel, and Crestan 2009), 分類器の使用 (Bellare, Talukdar, Kumaran, Pereira, Liberman, Mccallum, and Dredze 2007; Sadamitsu, Saito, Imamura, and Kikui 2011; Pennacchiotti and Pantel 2011), 人間の判断の導入 (Vyas and Pantel 2009), 意味カテゴリ間の関係の活用 (Curran et al. 2007; Carlson, Betteridge, Wang, Hruschka Jr., and Mitchell 2010b) など様々な手法が提案されている.

Vyas らはブートストラッピング手法におけるシードインスタンスの影響を調査した (Vyas et al. 2009). その結果，専門家でない人の選んだシードインスタンス集合はランダムに選択したものよりも結果が悪くなる可能性があることを示した。また彼らは，人手で作成されたシー ドインスタンス集合を洗練し，集合拡張の性能を向上させる手法を提案した.

Bellare らはブートストラッピング手法のランキング時にスコア関数の代わりに分類器を使用する手法を提案した (Bellare et al. 2007). 分類器を用いる手法はインスタンスのランキング時にパターン以外の素性を使うためである. Sadamitsu らは Bellare らの手法 (Bellare et al. 2007) を拡張し, Latent Dirichlet Allocation (LDA) から推定されるトピック情報を素性として使用する手法を提案した (Sadamitsu et al. 2011). 彼らはまた，意味的に近いカテゴリの情報を与え, LDA のトピックの粒度を調整する手法も提案している (Sadamitsu, Saito, Imamura, and Matsuo 2012). Pennacchiotti と Pantel は分類器のためのトレーニングデータを自動で収集する手法を提案した (Pennacchiotti and Pantel 2011). しかしながら,これらの研究は複数の意味カテゴリに対して同時に集合拡張を行うことを想定しておらず， 1 節で説明したような，意味カテゴリ間の関係知識の利用を考慮していない.

Vyas と Pantel は意味ドリフトの原因となったパターンを検出し，それを削除する手法を提案した (Vyas and Pantel 2009). 彼らは意味ドリフトを防ぐため, ブートストラッピング手法の反復に人間の正否判定を取り入れた. 彼らの手法では, 人手によって誤りインスタンスが発見された場合，その誤りインスタンスとそれを獲得する原因となったパターンを除去する。また，同様の誤りを防ぐため，誤りインスタンスと類似した文脈ベクトルを持つインスタンスも除去する。彼らもカテゴリ間の関係のような事前知識は使用していない.

Curran らはブートストラッピング手法にカテゴリ間の排他制約を導入した, Mutual Exclusion Bootstrapping という手法を提案した (Curran et al. 2007). Mutual Exclusion Bootstrapping は, インスタンスやパターンの属するカテゴリはたた 1 つであるという制約を取り入れたものである。複数のカテゴリに出現するインスタンスやパターンには曖昧性があり，意味ドリフトの原
因になると考えられる。そこで，曖昧性のあるインスタンスやパターンを除去することにより，彼らの手法は高い精度を達成した。

同じく排他関係を使用する手法として Carlson らは Coupled Pattern Learner (CPL) アルゴリズムを提案した (Carlson et al. 2010b). CPL アルゴリズムは意味カテゴリのインスタンス (例 :自動車カテゴリのインスタンス）と関係インスタンス（例：CEO-of-Company という関係に対する (Larry Page, Google) や Company-acquired-Company に対する (Google, Youtube)）を同時に収集する手法である。CPL アルゴリズムはこれらのインスタンスを取得するために，カテゴリ間の排他関係とカテゴリ間の意味的関係（例：CEO カテゴリのインスタンスは会社カテゴリに属するインスタンスのうちいずれかの CEO である）を使用する。しかしながら，カテゴリ間の意味的関係は関係インスタンスの取得にしか用いられておらず，意味カテゴリのインスタンスについては複数カテゴリに対する排他制約という事前知識しか用いていない.

Curran ら (Curran et al. 2007) と Carlson ら (Carlson et al. 2010b) はどちらも事前知識としてシードインスタンスだけではなくカテゴリ間の排他関係も利用している。しかし，意味カテゴリ間には上位下位や兄弟関係など排他関係以外の関係も存在する。兄弟関係は共通の特徴を持つべきであるカテゴリについての知識であり，排他関係という，インスタンスが同時に属さないカテゴリに関する知識とは別種のものである。兄弟関係についての知識は Wikipediaのような既存のリソースから容易に取得することができるため, 事前知識として利用しやすい. 本研究では，既存のリソースから入手できるカテゴリ間の兄弟関係に関する知識を事前知識として集合拡張に導入し，その有用性を検証する。

## 3 提案手法

## 3.1 兄弟カテゴリのパターンによるフィルタリング

本節では，意味カテゴリ間の兄弟関係を事前知識として活用する手法を提案する．以降では，兄弟関係にあるカテゴリの集合を兄弟グループと呼ぶこととする．例えば，自動車と自動二輪のカテゴリは兄弟関係にあるため, 同一の兄弟グループに属する，本研究では, 同一の兄弟グループに含まれるインスタンスは共通の特徴を保有していると仮定する. 例えば，自動車と自動二輪の兄弟グループに含まれるインスタンスは「乗り物」や「ガソリン式」という特徵を持ち,「乗る」や「燃費」などの語と係り受け関係を持ちやすい.この兄弟グループに共通の特徴を持っていないインスタンスは，正しいインスタンスである可能性が低いと考えられる。そのため，提案手法は兄弟グループのシードインスタンス集合を利用して兄弟グループに共通の特徵を取得し, グループ内の候補インスタンスがこの共通の特徴を保有しているか否かを検証することで，誤ったインスタンスの獲得を防ぐ.

同一の兄弟グループに属する自動車と自動二輪カテゴリについて，提案手法を用いて集合拡

図 1 兄弟関係を活用した集合拡張

張の際の誤りインスタンスを除去する例を図 1 に示す。提案手法はまず，この兄弟グループのインスタンスに共通の特徴として,「乗る」や「燃費」という表現と係り受け関係を持ちやすいという知識を得る。既存のブートストラッピング手法では，自動車カテゴリにおいて「新型の $\mathrm{X}\rfloor$ というパターンを獲得してしまった場合, シードや兄弟グループとは無関係のインスタンスである「iPad」を除去することができない。これに対して，提案手法では候補インスタンスが「乗る」や「燃費」と係り受け関係にある文節に出現しているかを，インスタンスの獲得（厳密には候補のランキング）の前に検証することによって，「iPad」のような誤りインスタンスを取り除くことができる。この結果, 提案手法は「カムリ」のような兄弟グループに共通する特徵を持つインスタンスのみを獲得する。

ここで, 兄弟グループに共通の特徴が, 対象とする意味カテゴリ以外も包含してしまうと, 意味ドリフトが発生してしまう．これを防ぐために，兄弟グループ間は排他関係にあるとし，兄弟グループに共通の特徴は対象としている兄弟グループに固有の特徴とする.

本研究では兄弟グループに共通の特徴は「乗る」や「燃費」などの表現によって表されると仮定する。このような表現をフィルタパターンと呼ぶ。提案手法では，候補インスタンスがフィルタパターンと共起しているか, すなわち, 候補インスタンスがフィルタパターンと係り受け関係にある文節に出現しているかの検証を行うことで，インスタンスが兄弟グループに共通の特徴を保有しているかを確認する。この確認はインスタンスの獲得の直前に行い, 候補インスタンスの抽出法については, 既存の手法を用いる。 すなわち, 提案手法は Espresso アルゴリズムや g-Espresso などの既存手法と組み合わせて利用することができる.

## 3.2 Espresso アルゴリズムをベースとした手法

Espresso アルゴリズムを利用し，図 1 のアイディアをアルゴリズムとして記述したものが Algorithm 1 である. このアルゴリズムは入力として対象とするカテゴリの集合 $C, S_{1}$ から $S_{T}$

までの兄弟グループ，それぞれのカテゴリ $c \in C$ に対応するシードインスタンス集合 $I_{c}$, 反復の回数 $L$, コーパス $W$ を受け取る. 兄弟グループはそれぞれ $C$ の部分集合であり，また，互いに素である. まず， 1 行目から 3 行目において各兄弟集合 $S_{j}$ に対するフィルタパターン $F_{S_{j}}$ を選択する。次に 9 行目において兄弟グループ $S_{j}$ 内の各カテゴリ $c$ のインスタンスを関数 ESPRESSO_EXCLUSIONを用いて取得する．ESPRESSO_EXCLUSIONは要素のそれぞれがインスタンス $i$ ，カテゴリ $c$ ，スコア $s$ のタプル，すなわち $(i, c, s)$ からなるリスト $R$ を返す。この関数において, インスタンスの抽出とスコアの計算は, 2.1 節で説明した Espresso アルゴリズムに,兄弟グループのカテゴリ間でパターンに対する排他制約を導入した手法を用いて行う.

本研究ではパターンはインスタンスと係り受け関係にある文節と定義する。例えば，「プリウス」というインスタンスと図 2 に示す文が与えられたとする（図 2 では文を文節で区切り，係り受け関係を文節間の矢印で表現している)。このとき，プリウスと同じ意味クラスに属するイ

図 2 文節間の係り受け関係の例

ンスタンスを取得するためのパターンとして，
- $\mathrm{X} \longrightarrow$ 販売を
- $\mathrm{X} \longleftarrow$ 新型

を得る。ここで，係り受け関係の向きについて，インスタンスを含む文節が別の文節に係る

めた表現形式をパターンとする。

次に $R$ に含まれる候補インスタンス $i$ が兄弟グループに共通の特徵を持つか否かの検証を，関数 FILTERによって行う（10 行目）。関数 FILTER は 23 行目から 31 行目に書かれている通りであり，Rに含まれる $i$ がそれぞれフィルタパターン $f$ と共起しているかどうかを検証する。この関数はフィルタパターンと共起しているインスタンスをそのスコアとともにリストとして返す. 言い換えれば，この関数はフィルタパターンの集合 $F$ によって表される兄弟グループに共通の特徴を保有していないインスタンスを除去している.

兄弟グループ内でのドリフトを防ぐため, 提案手法は兄弟グループのカテゴリ間に排他制約を導入している。 パターンやインスタンスが兄弟グループ内の複数のカテゴリで出現している場合, 提案手法はそれらが属するべき最適なカテゴリをたた 1 つ決定する。提案手法ではこの決定をランキングの結果をもとに行う．例えば自動車と自動二輪カテゴリにおいて「X $\rightarrow$ マフラー」というパターンが出現していたとする。 ランキングの結果, もしこのパターンが自動車カテゴリでは 13 位であり自動二輪カテゴリでは 4 位だったとすると, このパターンは自動二輪カテゴリにのみ属するものとする。すでに説明したように, Algorithm 1 において関数 ESPRESSO_ExCLUSION はパターンに対する排他制約が導入されているものであるとしており，インスタンスに対する排他制約は 13 行目から 17 行目に実装されている.

提案手法ではスコア $s$ を元に， 13 行目から 17 行目での排他制約を適用しながら, 反復数 $(l$回目）に応じて上位 $N \times l$ 個のインスタンスを獲得する。すべてのカテゴリについて新たなインスタンスの取得が終わった後, 次の反復へと進む. 入力として与えた回数だけ反復した後, アルゴリズムはそれぞれのカテゴリ $c \in C$ に対応するインスタンス集合 $I_{c}^{\prime}$ 出力する.

## $3.3 \mathrm{~g$-Espresso をべースとした手法}

正則化ラプラシアンカーネルを利用した g-Espresso によるインスタンスの抽出と, フィルタパターンによる候補インスタンスの特徴の検証を組み合わせた手法を，アルゴリズムとして記述したものが Algorithm 2 である. このアルゴリズムは Algorithm 1 の入力から反復回数 $L$ を除いたものを入力として受け取る.

Algorithm 2 は Algorithm 1 と同様，まず各兄弟集合 $S_{j}$ に対するフィルタパターン $F_{S_{j}}$ を選択する。次に兄弟グループ $S_{j}$ 内の各カテゴリ $c$ について, 候補インスタンス集合 $I_{v_{c}}$ とパター ンの集合 $P_{v_{c}}$ を関数 ESPRESSO によって，抽出する（8 行目）。関数 ESPRESSO は 2.1 節において説明した Espresso アルゴリズムによって，パターンとインスタンスのスコアを計算し，上位 $N_{\text {pattern }}$ 個のパターンと上位 $N_{\text {instance }}$ 個のインスタンスを返す関数である。なお, ここでのパターンも 3.2 節での関数 ESPRESSO_EXCLUSION で用いたものと同様,「X $\rightarrow$ 発表した」のような係り受け関係の向きも含めたものとする。g-Espresso は対象とするカテゴリ毎に，コーパス中の全パターンと全インスタンスを対象とした計算を行うため， ウェブページなどの大規模コーパスや，複数の意味カテゴリを対象とした場合には計算量が膨大になってしまう．計算量を抑えるため, 萩原ら (萩原他 2011) はブートストラッピング手法によって計算対象を制限し, その後グラフカーネルを適用する手法を用いた. 本手法でも同様に, Espresso アルゴリズムによってシードインスタンス集合と相関の高いパターン／インスタンスを $P_{v_{c}}, I_{v_{c}}$ として抽出し, g-Espresso への入力とする. なお, 今回は萩原ら (萩原他 2011)を参考に $N_{\text {pattern }}=2,000$ と

し, $N_{\text {instance }}=2,000 \times\left|S_{j}\right|$ とした.

次に候補インスタンス集合 $I_{v_{c}}$ に含まれるインスタンスが兄弟グループに共通の特徴を持つか否かの検証を, Algorithm 1 における関数 FILTER を用いて行う（9 行目）. 次に $P_{v_{c}}$ と関数 FILTER の返した $I_{v_{c}}$ を対象とし，g-Espresso によってインスタンスのスコアを計算する。これは関数 G-ESPRESSO を用いて行う（10 行目）。関数 G-ESPRESSO は要素のそれぞれがインスタンス $i$ ，カテゴリ $c$ ，スコア $s$ のタプルからなるリスト $R$ を返す.

最後に Algorithm 1 と同様に, 兄弟グループのカテゴリ間での排他制約を考慮しつつ, 各力テゴリについて，スコアの上位 $N_{a l l}$ 個のインスタンスを獲得し（13行目から 17 行目）, $I_{c}^{\prime}$ として出力する.

## 3.4 フィルタパターンの獲得

既に説明したように，提案手法はインスタンスが兄弟グループに共通の特徴を持っているか否かをフィルタパターンを用いて判定する。この節ではフィルタパターンの獲得方法について述べる。

フィルタパターンの獲得は候補の抽出とランキングの 2 つのステップからなる。候補の抽出では，兄弟グループのシードインスタンスと共起しているパターンを集める．例えば，自動車と自動二輪カテゴリからなる兄弟グループに対し, 自動車か自動二輪カテゴリに含まれるシー ドインスタンスと共起しているパターンを抽出する.

フィルタパターンは兄弟グループの特定のカテゴリのインスタンスを取得するためのものではなく, 兄弟グループに無関係のインスタンスを除去するためのものであるため, 兄弟グルー プに共通の特徴をとらえていることが望ましい. しかし，インスタンスとの係り受け関係の向きや, 助詞や副詞など構成する語を厳密に指定する形式にしてしまうと, 正解インスタンスまで取り除いてしまう可能性もある1.このため, フィルタパターンは係り先, 係り元といった係り受け関係の向きを考慮せず，さらに名詞と動詞に限定する。すなわち，フィルタパターンは Espresso アルゴリズムや g-Espresso で用いたパターンとは異なり，「乗る」や「エンジン」,「愛車」などの，インスタンスと係り受け関係にある文節に出現する名詞や動詞とする ${ }^{2}$.

候補のランキングでは, 抽出された候補の中からフィルタパターンとして最適なものを選択する. 兄弟グループに含まれる意味カテゴリのインスタンスが獲得されるには, フィルタパター ンと共起する必要がある。 そのため, 兄弟グループに属するインスタンスとできるだけ多く共起するようなフィルタパターンが適している。また，フィルタパターンによって，インスタンスが兄弟グループに共通の特徵を保有しているかどうかを検証するため, 兄弟グループ内のカ


テゴリに均等に出現するようなフィルタパターンが適している。この 2 の要素をそれぞれ網羅性と平等性として定式化し, これにもとづいてフィルタパターンの選択を行う.

フィルタパターンは兄弟グループに属する正しいインスタンスを網羅するようなものであることが望ましい，そのため，兄弟グループ中の多くのシードインスタンスと共起しているパターンが適している。例として，自動車と自動二輪カテゴリのフィルタパターンについて考える（図 3)。図 3 において，パターンは斜体で表されている。また，パターンの下の四角で覆われた朹内の文字はシードインスタンスであり，特にパターンと共起しているものは太字で示してある。この図の (a)において, パターン「乗る」は「マイナーチェンジ」よりも多くのシードインスタンスと共起しているため, よりフィルタパターンに適していると考える。この要素を網羅性と呼び，Coverage という指標で測定する．ある兄弟グループ $S_{j}$ に属するパターン $f$ の Coverage は次の式 (11)を用いて計算する.

$
\begin{gathered}
\operatorname{Coverage}\left(S_{j}, f\right)=\frac{\sum_{c \in S_{j}} \sum_{i \in I_{c}} \operatorname{cooccur}(f, i)}{\sum_{c \in S_{j}}\left|I_{c}\right|} \\
\operatorname{cooccur}(f, i)= \begin{cases}1 & i \text { と } f \text { が共起している場合 } \\
0 & \text { それ以外 }\end{cases}
\end{gathered}
$

$I_{c}$ はカテゴリ $c$ のシードインスタンス集合であり， $\left|I_{c}\right|$ はカテゴリ $c$ のシードインスタンスの数である。 $\operatorname{cooccur}(f, i)$ はインスタンス $i$ がパターン $f$ と共起しているか否かを表しており, 共起しているなら 1 を，していなければ 0 を返す関数である。よって， $\sum_{i \in I_{c}} \operatorname{cooccur}(f, i)$ はカテゴリ $c$ に属し，かつパターン $f$ と共起しているシードインスタンスの数を表す.

さらに，フィルタパターンはインスタンスが兄弟グループに共通の特徴を保有しているかど

(a)網羅性

(b)平等性

図 3 フィルタパターンとして望ましい性質

うかを検証するためのものであるため，特定のカテゴリに偏って出現しているパターンは不適当である。したがって，パターンは兄弟グループ内のカテゴリのうち，2つ以上で出現していなければならないとする。図 3 の (b) において,「エンジン」というパターンは自動車と自動二輪の両方のカテゴリのインスタンスと共起しているが,「トヨタ」は自動車カテゴリのみでしか出現していない.このため「トヨタ」はフィルタパターンとしては不適当とし, 候補から除去する.また, 図 3 の (b) では「乗る」というパターンは両方のカテゴリのインスタンスと均等に共起しているため, 「エンジン」よりもフィルタパターンとして適している.この, パターンが兄弟グループ内のそれぞれのカテゴリのインスタンスと, どれだけ均等に共起するかという要素を平等性と呼ぶ. 兄弟グループ内のあるカテゴリのインスタンスとパターンが共起するとき， パターンがそのカテゴリに出現したと定義すれば，平等性は兄弟グループ内での，パターンがどのカテゴリに出現するかの分散の大きさと言える。このため, 平等性は情報量 (Entropy)を用いて測定できる。ある兄弟グループ $S_{j}$ に属するパターン $f$ の Entropy は次の式 (13) を用いて計算する.

$
\begin{gathered}
\operatorname{Entropy}\left(S_{j}, f\right)=-\sum_{c \in S_{j}} P_{c}(f) \log _{|C|} P_{c}(f) \\
P_{c}(f)=\frac{\sum_{i \in I_{c}} \operatorname{cooccur}(f, i)}{\sum_{c \in S_{j}} \sum_{i \in I_{c}} \operatorname{cooccur}(f, i)}
\end{gathered}
$

$|C|$ はパターン $f$ の出現しているカテゴリの数である. もしパターン $f$ が兄弟グループ内のそれぞれのカテゴリのインスタンスと均等に共起したとすると, $\operatorname{Entropy}\left(S_{j}, f\right)$ は最も高い値 $(1.0)$ となる.

網羅性と平等性の両方の観点において優れているパターンを獲得するため, パターン $f$ のスコアを次の式 (15) を用いて計算する.

$
\operatorname{Score}\left(S_{j}, f\right)=\operatorname{Entropy}\left(S_{j}, f\right) \times \operatorname{Coverage}\left(S_{j}, f\right)
$

各兄弟グループ $S_{j}$ の候補パターン $f$ について $\operatorname{Score}\left(S_{j}, f\right)$ を計算し, 兄弟グループに共通の特徵を特に表していると考えられる，上位 15 個を兄弟グループのフィルタパターンとして獲得する. なお, 兄弟グループが他の兄弟グループへ意味ドリフトしてしまうことを防ぐため, 兄弟グループ間は排他関係にあるとする。そのため, 複数の兄弟グループで候補となっているフィルタパターンについては，属する兄弟グループをただ 1 つ決めなければならない. この決定はフィルタパターンの出現頻度にもとづいて行う. すなわち, 兄弟グループ内のシードインスタンスとの共起頻度の和をフィルタパターンの兄弟グループ内での出現頻度とし, これが最大である兄弟グループにのみフィルタパターンは属するとする。これにより，それぞれの兄弟グルー プに固有のフィルタパターンが得られる. このフィルタパターンを用いることで, 兄弟グルー

プに共通の特徴を持たない，無関係なインスタンスを除去できる.

## 4 実験

## 4.1 実験設定

本節では集合拡張において，カテゴリ間の兄弟関係を事前知識として使用することの効果を実験的に検証する。実験では Espresso アルゴリズム (Pantel and Pennacchiotti 2006), Espresso アルゴリズムにカテゴリ間の排他制約を加えたもの（Espresso＋排他制約），Espresso アルゴリズムにカテゴリ間の排他制約と兄弟関係を事前知識として加えたもの（提案手法（ベース： Espresso)）のブートストラッピング手法と, g-Espresso アルゴリズム (萩原他 2011), g-Espresso アルゴリズムにカテゴリ間の排他制約と兄弟関係を事前知識として加えたもの（提案手法 (ベー ス：g-Espresso））のグラフカーネルを用いた手法について比較を行う．グラフカーネルを用いた手法における，正則化ラプラシアンカーネルの拡散パラメータは萩原ら (萩原他 2011) と同様， $\beta=5.0 \times 10^{-4}$ とした. ブートストラッピング手法では反復毎に，各カテゴリのインス夕ンスとパターンの獲得数を 15 個ずつ増加（すなわち $N=15$ ）させた.

集合拡張は未知のインスタンスを取得するタスクであるため，再現率を正確に測定することは難しい，そのため，各手法の比較は，同じ数のインスタンスを取得した際の適合率を比べることによって行う。 さらに, 各手法の出力した正解インスタンスの集合を正解セットと考え,再現率を疑似的に計算し，比較する。なお，獲得インスタンスの正否は 3 人の評価者によって判定する.

1 節で説明したように，近年では，全てのカテゴリのインスタンスを収集する需要が高まっている.このため実験では, Carlson ら (Carlson et al. 2010a)のように，様々な種類のカテゴリを対象とする．代表的なカテゴリをまんべんなく対象とするため，関根の拡張固有表現階層のリスト ${ }^{3}$ と Wikipediaを参考に，人手で 41 個のカテゴリを実験対象として選択した．対象カテゴリは表 2 に示した通りであり，この表に示した全てのカテゴリについて，同時に集合拡張を行う，なお，表 2 ではカテゴリを兄弟グループが同一のものでまとめてあり, 兄弟グループ間は赫線によって区切られている。兄弟グループは同じ上位カテゴリを持つカテゴリの集合となるよう，Wikipediaを参考に人手で作成した．各カテゴリはただ 1 つの兄弟グループに属するものとし, 各兄弟グループは 2 つ以上のカテゴリを含む.

シードインスタンスについては Wikipedia から自動でインスタンスを抽出するツール (Sumida， Yoshinaga, and Torisawa 2008)を利用し，各カテゴリ毎に 15 個ずつ用意した。なお，自動で抽出した結果には誤りも含まれているため，人手によって誤りインスタンスを除去している.
^{3}$ https://sites.google.com/site/extendednamedentityhierarchy/
}
実験には 1 億 1 千万の日本語ウェブページをコーパスとして用いた。 ウェブページ中の文は日本語係り受け解析器である KNP (Kurohashi and Nagao 1994) を用いて係り受け構造を解析した。また, 計算時間を削減するため, 出現頻度が 2 回以下であるパターンとインスタンスは除去している.

## 4.2 結果

ブートストラッピングの反復を 10 回行った際の, 各手法における全カテゴリでの獲得インスタンス数とその適合率を図 4 に示す. グラフカーネルを用いた手法では, ブートストラッピングと同数のインスタンスを獲得した際の適合率を示している。また, 提案手法ではフィルタパター ンにおいて係り受け関係の方向を指定しないとしていたが, この効果を確認するため, フィルタパターンにおいて係り受け関係の方向を指定した手法での結果も記した. この図より, Espresso + 排他制約は Espressoよりも適合率が上昇していることがわかる. Espresso + 排他制約の適合率は Espresso と比べると， 4,305 個のインスタンスを獲得したときに最も上昇し, $2.4 \%$ 高い. また，10 回の反復後，すなわち 6,765 個のインスタンスを獲得したときには $1.3 \%$ 上昇している. 提案手法 (ベース：Espresso）は Espresso + 排他制約よりもさらに適合率が上がっており， Espresso と比べると， 4,305 個のインスタンスを獲得したときには $4.4 \%$ 上昇し， 6,765 個のインスタンスを獲得したときには $2.1 \%$ 上がっている. さらに, g-Espresso と提案手法（ベース： g-Espresso）を比較しても，提案手法の適合率が上昇していることがわかる. 提案手法（ベー ス：g-Espresso）の適合率は g-Espresso と比べ， 3,690 個のインスタンスを獲得したときに最も上昇し, $6.1 \%$ 高い. この結果から, カテゴリ間の兄弟関係についての事前知識は意味ドリフトの抑制に寄与し，集合拡張の精度を向上させることがわかる.

また図 4 より, フィルタパターンにおいて係り受け関係の方向を指定した手法では, Espresso

図 4 各手法における取得インスタンス数とその適合率

よりも適合率が上昇するが，提案手法（フィルタパターンにおいて係り受け関係の方向を指定しない場合）よりは適合率が低いことがわかる。したがって，フィルタパターンにおいて係り受け関係の方向まで指定することは厳しすぎる制約であり，フィルタパターンを用いて兄弟グループの共通性を検証する際には，係り受け関係の方向を指定する必要はないことがわかる.

小町ら (小町他 2010) や萩原ら (萩原他 2011) はグラフカーネルを用いることにより， 意味ドリフトが抑制できることを示した。 しかし, 図 4 において, グラフカーネルを用いた手法である g-Espresso の適合率は Espresso より低い。これは， 3.3 節で説明したように，グラフカー ネルを適用するパターンと候補インスタンスを制限しているためであると考えられる．例えば， ヨーロッパの国カテゴリについて,「ドイツ」というシードインスタンスから「X $\rightarrow$ サッカー選手一覧」,「X $\rightarrow$ キーパーは」というパターンが抽出されるため, 「強豪」や「代表」のような,対象とする意味カテゴリとは無関係なインスタンスのスコアが高くなってしまう。この問題について萩原ら (萩原他 2011) は，グラフの範囲を広げることで解消できるとしたが，複数の意味カテゴリを対象にした集合拡張では，計算量を抑えるためにグラフはできるだけ小さくせねばならず，避けられない問題であると考えられる。

再現率を疑似的に計算するため, 反復を 10 回行った（すなわち各カテゴリで 165 個のインスタンスを獲得した）ときの，各手法で獲得した正解インスタンスの和集合を正解セットとして，反復毎 ${ }^{4}$ の適合率と再現率を計算した。この結果を図 5 に示した. 図 5 より, 提案手法 (ベー ス：Espresso）は Espresso, Espresso + 排他制約よりも性能が良く, また, 提案手法（ベース： g-Espresso）は g-Espresso よりも性能が良いことがわかる。これより，提案手法は再現率を保ったまま，適合率を上昇させることが可能であると言える。

図 5 各手法における適合率と再現率

適合率，再現率共に高いブートストラッピング手法に着目し，さらに詳しい分析を行う。まず，各手法における取得インスタンスの傾向を調べる。同じ兄弟グループに属する神社と寺カテゴリについて，各手法で反復を 5 回行った際の，獲得インスタンスのうち上位 15 個を表 1 に示す.なお，表 1 ではインスタンスを正解と誤りに分けて記している。表 1 によると, Espresso と Espresso + 排他制約は多くの誤りインスタンスを獲得しているが, 誤りの傾向には違いがある. Espresso は「八幡宮」や「太宰府天満宮」、「浅草寺」など，いくつかのインスタンスを神社と寺カテゴリの両方に属するものとしてしまっている。これに対して, Espresso + 排他制約はインスタンスが複数カテゴリに所属しないように，インスタンスの属するただ 1 つのカテゴリを選択しており, Espressoのような誤りは発生していない. すなわち, 排他制約は意味ドリフトを緩和する効果があることがわかる。しかしながら, Espresso + 排他制約は寺カテゴリにおいて，「袋屋奨油店」や「あだしのまゆ村」など，対象カテゴリとは無関係のインスタンスを多く獲得してしまっている．提案手法は兄弟グループの共通性についての知識を利用することにより，このような誤りインスタンスを除去することに成功している。この結果から, 兄弟関係は集合拡張に対して，有用な情報であることがわかる。

反復を 5 回行った際の, 各カテゴリにおける各手法の獲得インスタンスの適合率を表 2 に記

表 1 神社と寺カテゴリにおける各手法の獲得インスタンスの上位 15 個

 &  &  \\

表 2 反復を 5 回行った際の各カテゴリにおける各手法の適合率

 & 提案手法 & 上昇率 &  &  \\

す.また表 2 には提案手法の適合率の, Espresso からの上昇率も示した. さらに，それぞれの兄弟グループでのフィルタパターンのうち, 上位 3 つをそのスコアとともに記した. 表 2 より,提案手法と Espresso + 排他制約は多くのカテゴリにおいて Espresso よりも適合率が上昇していることがわかる．この結果は，カテゴリ間の排他関係と兄弟関係は集合拡張の精度を向上させることを示している。しかしながら，いくつかのカテゴリにおいては適合率が下がっており，兄弟関係の知識が有効に働いていないようである。この原因は以下の 2 つに分類されると考えられる。

(1) フィルタパターンのスコアが低い

(2) ベースラインでの適合率が高い

(1)の場合は自動車メーカーと医薬品メーカー, 美術館と劇場など, 兄弟グループのカテゴリすべてで適合率が下がっている。例えば, 自動車メーカーと医薬品メーカーカテゴリについては, Espresso と比べ，適合率がそれぞれ $14.44 \%, 2.22 \%$ 下がっている.この 2 つのカテゴリを含む兄弟グループでは, 最もスコアの高いフィルタパターンでさえスコアが 0.1837 とかなり低い.各兄弟グループで取得したフィルタパターンのスコアの最大値と, その兄弟グループの適合率の Espresso からの上昇率を図 6 に記した. さらに図 6 には一次近似曲線を引き，スコアと上昇率の相関を示した. この図より, 取得したフィルタパターンのスコアの最大値が低いほど上昇率が下がり，スコアが 0.6 以下の場合には Espresso よりも精度が悪くなることがわかる。 フィルタパターンのスコアとは, 兄弟グループの共通性を表したパターンをフィルタパターンとして取得できるよう，兄弟グループのシードインスタンスを用いて計算されたものである。つまり, 取得したフィルタパターンのスコアが低いということは, 提案手法がフィルタパターンに

図 6 各兄弟グループで取得したフィルタパターンのスコアの最大値と適合率の上昇率
必要な要素である, 網羅性と平等性を持つパターンを見つけられなかったことを示唆している.網羅性と平等性を持つパターンを獲得できなかった原因は, 自動車メーカーと医薬品メーカー など共通性の少ないカテゴリを兄弟グループとしてしまったためであると考えられる．兄弟グループの選択による提案手法への影響については, 今後調査していきたい.

映画監督やコメディアンカテゴリは (2)にあてはまる。（2）の場合, Espresso において意味ドリフトは起こっていないにもかかわらず，提案手法はフィルタを適用し，正解インスタンスを削除してしまっている。言い換えれば，提案手法は誤りインスタンスよりも正解インスタンスを多く除去してしまっている。この原因としては，フィルタパターンはシードインスタンスによってのみ決定されるため，ブートストラッピングの反復中に新たに抽出したインスタンスによってもたらされる，兄弟グループの共通性を扱えていない可能性がある。これに対処するために，ブートストラッピングの反復中にフィルタパターンを更新することが必要であると考えられる。しかし，新たに獲得したインスタンスを用いてフィルタパターンを更新した場合，意味ドリフトを抑制する効果が失われてしまうことも考えられるため，更新は慎重に行わなければならない.フィルタパターンの更新方法については今後の課題である.

## 5 まとめ

本論文では，ブートストラッピングにおいて，カテゴリ間の兄弟関係を事前知識として利用する手法を提案し，兄弟関係が集合拡張に対して有用な知識であることを示した．実験では，提案手法はベースラインである Espresso アルゴリズムと比べ, 適合率を最大で $4.4 \%$ 向上させた.

しかしながら，4.2節において述べた通り, 提案手法にはいくつかの副作用もある。この副作用の原因は，共通性の少ない兄弟グループの設計と，フィルタパターンを更新しないためであると考えられる。これらの要因への対処は今後の課題である。また，本研究ではカテゴリ間の兄弟関係がカテゴリのインスタンスを収集する際に有用な情報であることを示したが，今後は， この手法を関係インスタンスの取得に拡張していきたい。すなわち, 関係（例：is-president-of やis-citizen-of）間にある含意関係や因果関係を利用して，関係インスタンスを獲得する手法を構築したい.

## 謝 辞

本研究は, 文部科学省科研費 (23240018), 文部科学省科研費 (23700159), および JST 戦略的創造研究推進事業さきがけの一環として行われた.

## 参考文献

Abney, S. (2004). "Understanding the Yarowsky Algorithm." Comput. Linguist., 30 (3), pp. 365-395.

Bellare, K., Talukdar, P. P., Kumaran, G., Pereira, O., Liberman, M., Mccallum, A., and Dredze, M. (2007). "Lightly-Supervised Attribute Extraction." In Proceedings of the Advances in Neural Information Proceeding Systems Workshop on Machine Learning for Web Search, pp. 1-7.

Cao, H., Jiang, D., Pei, J., He, Q., Liao, Z., Chen, E., and Li, H. (2008). "Context-Aware Query Suggestion by Mining Click-Through and Session Data." In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 875-883.

Carlson, A., Betteridge, J., Kisiel, B., Settles, B., Hruschka Jr., E. R., and Mitchell, T. M. (2010a). "Toward an architecture for never-ending language learning." In Proceedings of the 24th AAAI Conference on Artificial Intelligence, pp. 1306-1313.

Carlson, A., Betteridge, J., Wang, R. C., Hruschka Jr., E. R., and Mitchell, T. M. (2010b). "Coupled Semi-Supervised Learning for Information Extraction." In Proceedings of the 3rd ACM International Conference on Web Search and Data Mining, pp. 101-110.

Curran, J. R., Murphy, T., and Scholz, B. (2007). "Minimising semantic drift with Mutual Exclusion Bootstrapping." In Proceedings of the 10th Conference of the Pacific Association for Computational Linguistics, pp. 172-180.

Etzioni, O., Banko, M., and Cafarella, M. J. (2006). "Machine Reading." In Proceedings of The 21st National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, pp. 1517-1519.

萩原正人，小川泰弘，外山勝彦 (2011)．グラフカーネルを用いた非分かち書き文からの漸次的語彙知識獲得. 人工知能学会論文誌, 26 (3), pp. 440-450.

Hearst, M. A. (1992). "Automatic Acquisition of Hyponyms from Large Text Corpora." In Proceedings of the 14th Conference on Computational Linguistics, pp. 539-545.

小町守, 工藤拓, 新保仁, 松本裕治 (2010). Espresso 型ブートストラッピング法における意味ドリフトのグラフ理論に基づく分析. 人工知能学会論文誌, 25 (2), pp. 233-242.

Kurohashi, S. and Nagao, M. (1994). "KN Parser: Japanese Dependency/Case Structure Analyzer." In Proceedings of the Workshop on Sharable Natural Language Resources, pp. 48-55.

Mintz, M., Bills, S., Snow, R., and Jurafsky, D. (2009). "Distant supervision for relation extraction without labeled data." In Proceedings of the Joint Conference of the 47th Annual Meeting of the Association for Computational Linguistics and the 4th International Joint

Conference on Natural Language Processing of the AFNLP, pp. 1003-1011.

Pantel, P., Crestan, E., Borkovsky, A., Popescu, A.-M., and Vyas, V. (2009). "Web-scale distributional similarity and entity set expansion." In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pp. 938-947.

Pantel, P. and Lin, D. (2002). "Discovering word senses from text." In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 613-619.

Pantel, P. and Pennacchiotti, M. (2006). "Espresso: Leveraging Generic Patterns for Automatically Harvesting Semantic Relations." In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pp. 113-120.

Pantel, P. and Ravichandran, D. (2004). "Automatically Labeling Semantic Classes." In Proceedings of the 2004 Human Language Technology Conference of the North American chapter of the Association for Computational Linguistics, pp. 321-328.

Pennacchiotti, M. and Pantel, P. (2011). "Automatically Building Training Examples for Entity Extraction." In Proceedings of the 15th Conference on Computational Natural Language Learning, pp. 163-171.

Sadamitsu, K., Saito, K., Imamura, K., and Kikui, G. (2011). "Entity Set Expansion using Topic information." In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 726-731.

Sadamitsu, K., Saito, K., Imamura, K., and Matsuo, Y. (2012). "Entity Set Expansion using Interactive Topic Information." In Proceedings of the 26th Pacific Asia Conference on Language, Information and Computation, pp. 114-122.

Smola, A. J. and Kondor, R. (2003). "Kernels and Regularization on Graphs." In Proceedings of the Conference on Learning Theory and Kernel Machines, pp. 144-158.

Sumida, A., Yoshinaga, N., and Torisawa, K. (2008). "Boosting Precision and Recall of Hyponymy Relation Acquisition from Hierarchical Layouts in Wikipedia." In Proceedings of the 6th International Conference on Language Resources and Evaluation, pp. 2462-2469.

Vyas, V. and Pantel, P. (2009). "Semi-Automatic Entity Set Refinement." In Proceedings of the 2009 Human Language Technologies Conference of the North American Chapter of the Association for Computational Linguistics, pp. 290-298.

Vyas, V., Pantel, P., and Crestan, E. (2009). "Helping Editors Choose Better Seed Sets for Entity Set Expansion." In Proceedings of the 18th ACM Conference on Information and Knowledge Management, pp. 225-234.

Wang, R. C. and Cohen, W. W. (2009). "Automatic Set Instance Extraction using the Web."

In Proceedings of the Joint Conference of the 47th Annual Meeting of the Association for Computational Linguistics and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pp. 441-449.

Yarowsky, D. (1995). "Unsupervised Word Sense Disambiguation Rivaling Supervised Methods." In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, pp. 189-196.

## 略歴

高瀬翔：2012 年東北大学工学部情報知能システム総合学科卒業. 同年, 同大学大学院情報科学研究科博士前期課程に進学, 現在に至る. 自然言語処理の研究に従事.

岡崎直観 : 2007 年東京大学大学院情報理工学系研究科・電子情報学専攻博士課程修了. 同大学院情報理工学系研究科・特別研究員を経て, 2011 年より東北大学大学院情報科学研究科准教授. 自然言語処理, テキストマイニングの研究に従事. 情報理工学博士. 情報処理学会, 人工知能学会, ACL 各会員.

乾健太郎：1995 年東京工業大学大学院情報理工工学研究科博士課程修了. 同研究科助手, 九州工業大学助教授, 奈良先端科学技術大学院大学助教授を経て, 2010 年より東北大学大学情報科学研究科教授, 現在に至る. 博士 (工学).自然言語処理の研究に従事. 情報処理学会, 人工知能学会, ACL, AAAI 各会員.

