論文
DBSJ Letters Vol.6, No.4――――――――――――――――――――――――――――――――――――In this paper, we propose a cost-effective searchstrategy framework to extract keywords in the same
semantic class from the Web. Bootstrapping techniquebased on Web search API is one of the promising
approaches for constructing a lexicon for named entity
recognition. However, too many queries can overload thesearch engines. Our goal is to optimize a search strategy
which can collect as many new words as possible withthe least API calls. Our results shows that the optimized
search strategy can extract more than 100,000 words
with a precision of 0.90 with only 2,000 search API calls.

語集合から1語ずつクエリとして検索し（シングルシードクエリ），複数の文書に共通して出現するシード語の周辺文字
列（グローバルパタン）を用いて新語の抽出を行う．グロー
バルパタンの例としては，”cities such as”等の定型表現[1]や，HTMLのテーブルタグ[3]などが挙げられる．
しかし，従来の同位語増殖手法は，非常に多くの検索回数を必要とする問題がある．その理由は，グローバルパタン構
築のために，1 語1 語のシード語について大量の検索結果文書を照合する必要があるからである．
そこで本稿では，より少ない検索回数でより多くの新語を抽出できる検索戦略を備えたブートラップ式同位語増殖手法として，Cost-EffectiveSearch Strategy (CESS) フレー
ムワークを提案する．本フレームワークは，複数のシード語を組み合わせてAND 検索するマルチシードクエリと，使い捨てのローカルパタンの2 点を特徴とする．
例えば，シード語が俳優名リストだった場合，マルチシー
ドクエリとして，5 人の名前をランダムに組み合わせてAND
検索を行ったとする．検索結果中のあるWebページにおいて，クエリに使った5人の俳優名が全て<OPTION>タグで囲まれていた場合，そのページには俳優名をメニューとするフォームが記述されており，そのフォームにはシード語に未登録の別の俳優名も記述されていることが期待できる．つまり，単一
ページのみから一貫性の高い周辺文字列をローカルパタンとして構築でき，さらに，そのページから複数の新語を抽出できるため，検索効率を向上できる．ただし，ローカルパタ
ンは単一ページ内にだけ通用するフォーマットであるために使い捨てである．
Web ページの局所的な構造情報をローカルパタンとして利用する手法としては Web ラッパー生成技術[4-6] が挙げられる．特に，SEAL[6] は，文字列ベースのローカルパタンを利用している点で提案手法と類似している．しかし，Web
ラッパー生成技術では，検索戦略については何ら考慮されていない．他の関連技術として，クエリログを活用した同位語
発見手法[7] も存在するが，提案手法に比べると辞書の規模や精度の面でまだ課題がある．
一方，CESS フレームワークの別の特徴としては，マルチ
シードクエリとローカルパタンの採用により，誤抽出されたノイズ語に対する高いロバスト性を維持できるという利点もある．評価実験では，検索効率と辞書の適合率を指標として，提案手法の有効性を検討する．

1. はじめに

2. CESS フレームワーク

近年，Web上に散在した知識を収集するアプローチの一つとして，サーチエンジンの検索APIを用いたブートストラッ
プ式同位語増殖手法が注目を集めている[1-3]．同位語増殖とは，辞書として構築したい単語の例（シード語集合）を数
十語程度入力して，同一の意味的階層に属する単語集合を収集するタスクであり，自然文から人名，地名，組織名などの固有表現を抽出する要素技術として非常に重要である．
従来の検索APIを用いた同位語増殖手法では主に，シード

図 1 に，CESS フレームワークの概要を示す．本フレーム
ワークは，主に検索部と抽出部の 2 つのモジュールから構成される[8]．ユーザーから初期の入力としてシード語集合 S ={s1, s2, ..., sn}を受付けると，検索部の Query Builder は，
2.1 節で述べる検索戦略に従ってω個の単語を S から選び出
し，AND 検索用のクエリ Q を作成する．次に，Crawler が，
WWW を介して検索 API にクエリ Q を発行し，検索結果の文書
本体をクロールして文書群 D を作成し，抽出部の Pattern
Generator に渡す．
Pattern Generator は，Crawler から渡された文書群 D 内の各文書 d について，各シード語の周辺の一貫性の高い文字列を 2.2 節で述べる方法によって検出し，パタン集合 P に格納する．次に，Instance Extractor は，パタン集合 P 中の個
別のパタン p について文書 d を照合し，シード語集合 S に未登録の新語 i を抽出する．Seed Sifter は，新語 i を抽出しブートストラップ式同位語増殖における検索戦略の研究
SearchStrategies
Lexicon Acquisition

河合 英紀♥
土田 正明♦
山田 敬嗣♠

on

Bootstrapping

水口 弘紀♦
國枝 和雄♠

Hideki KAWAI Hironori MIZUGUCHI
Masaaki TSUCHIDA Kazuo KUNIEDA
Keiji YAMADA

本稿では，同一の意味的階層に属する単語集合（同位語辞書）を高い検索効率で Web から抽出する方法を提案する．
近年，Web 上に散在した知識を収集するアプローチの一つとして，サーチエンジンの検索 API を用いたブートストラ
ップ式同位語増殖手法が注目を集めている．しかし，検索
API を通じて大量の検索を行うことは，サーチエンジンに過剰な負荷をかけてしまうことになる．そこで本稿では，検索回数をコストとして考慮し，なるべく少ない検索回数でより多くの同位語を収集可能な検索戦略を求めることを目標とする．実験の結果，合計 2000 回の検索で 10 万語以上のキーワードを適合率 0.9 以上で抽出することができた．

♥

正会員 NEC C&C イノベーション研究所
h-kawai@ab.jp.nec.com♦
正会員 NEC サービスプラットフォーム研究所{hironori@ab, m-tsuchida@cq}.jp.nec.com♠
NEC C&C イノベーション研究所 {k-kunieda@ak,
kg-yamada@cp}.jp.nec.com

1

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

論文
DBSJ Letters Vol.6, No.4――――――――――――――――――――――――――――――――――――
γを検索戦略パラメータと呼ぶ．検索戦略パラメータγ が

CESSフレームワーク

検索API

WWW

検索部

抽出部

Seed
Words

Seed Sifter

Query
Builder

Instance
Extractor

Crawler

Pattern
Generator

図1

CESS フレームワークの概要

Fig.1

Overview of CESS framework

大きいほど，高頻出・高信頼度の語を優先したクエリとなる．

2.2

Coherence( xp) = Occurence( xp) / matchCnt (2)たパタン p の異なり数を計数し，閾値θ以上であれば，新語
i をシード語集合 S に追加する．これは，新語 i の抽出パタンの異なり数が多いほど，様々なサイトでシード語と同じグ
ループの単語として記述されていると判断できるからである．閾値θをヘテロ性判定パラメータと呼ぶ．

2.1

マルチシードクエリ

ここでは，マルチシードクエリとしてシード語から複数の語を選択する際の Query Builder の検索戦略について説明する．最も単純な検索戦略は，一様にランダムにω 語を選ぶ方法である．一般的に，ωの値が大きくなるほど，シード
語がリストやテーブルで構造化されたリストページが検索されやすい．しかし，ωが大きすぎると，検索結果は 0 件になってしまうため，適切なωの値を求める必要がある．本稿では，ωをシードパラメータと呼ぶ．
一方，適切なωを選んだとしても，単純な一様乱数に基づく検索戦略では，シード語集合が大規模になるとシード語同士の低共起性が問題になってくる．具体的には，多くのクエリが出現頻度の低いシード語の組合せになり，検索結果が 0
件になってしまう．また，低頻度語はシード語としての信頼性も低く，間違ったパタンが構築されるリスクもある．そこ
で本稿では，シードスコアのべき乗分布に従う乱数による検索戦略によって，高頻出・高信頼度のシード語を優先して選択する方法を提案する．あるシード語 sj のシードスコア
Score(sj)は，以下のように定義できる．

Score( s j ) = v j / v max(1)

ここで，vj はシード語 sj の抽出に使われたパタンの異なり
数，vmax はシード語全体での抽出パタンの異なり数の最大値である．シードスコアの値の範囲は，0<Score(sj)≤1 であり，
シード語 sj の出現頻度と信頼度の両方を表している．
Query Builder による検索戦略アルゴリズムの詳細は以下の通りである．
① 最初に入力引数としてシード語集合 S を受取り，サン
プルシード集合 SS を空集合に初期化する．
② 2 つの一様乱数 j と k を生成する．(ただし 0<j, k ≤1)③ もし，k < Score(sj)γ であれば，実際に j*|S|番目のシード語 sj*|S|をシード語集合 S からサンプルシー
ド集合 SS に移動する．そうでなければ，②に戻る．
④ サンプルシード集合 SS がω語になったら，SS 中の語を AND 演算子で結んでクエリ Q とする．
提案アルゴリズムでは，j*|S|番目のシード語がクエリとして選ばれる確率は，シードスコアのγ乗に比例する．指数2

ローカルパタン

Pattern Generator は入力引数として，シード語集合 S と単一文書 d を受け取る．Pattern Generator の処理は，大きく，Pattern Detection と，Coherence Validation の 2 つの処理から構成される．
Pattern Detection 処理では，シード語集合 S に含まれる全てのシード語 s について，文書 d 内の出現位置を照合し，出現回数を matchCnt に計数する．同時に，シード語 s の左
右の 2～50 文字をそれぞれ左側パタン集合 LP ，右側パタン
集合 RP に格納する．
Coherence Validation 処理では，周辺文字列 xp の一貫性
Coherence(xp) を次式で評価する．
ここで，周辺文字列 xp には，左側パタン lp，右側パタン
rp が該当する．また，Occurence(xp) は，文書 d 内でシード
語 s が周辺文字列 xp に隣接する回数である．式(2) は，Coherence(xp) が高いほど，文書 d 内でシード語 s の周辺文
字列 xp が一貫したフォーマットで記述されていることを意味する．一方，シード語 s が自然文中に現れている場合は，多様な周辺文字列が存在するため，ある周辺文字列 xp の一
貫性 Coherence(xp) は低くなる．最終的に，Coherence(xp)が閾値μ 以上の場合にのみ，周辺文字列 xp を抽出パタンとして残す．閾値μ を一貫性判定パラメータと呼ぶ．
最後に，Pattern Generator は，残った左側パタン集合 LPと右側パタン集合 RP に含まれる周辺文字列の組み合わせ<lp,rp> をローカルパタンとして Instance Extractor に渡す．
ローカルパタンは処理対象となる文書 d に強く依存するため，新語の抽出に用いるのは文書 d 内だけで使い捨てとなる．

3. 評価実験と考察
CESS フレームワークにおけるブートストラップ式辞書構
築アルゴリズムを Perl で実装し，評価実験を行った．辞書構築のターゲットとした言語は英語と日本語，ドメインはActor，Film，Location，Company，School の 5 種類で，シード語にはそれぞれ既存のランキングから機械的に 10 語を選んで利用した[8]．
また，Web サーチエンジンとしては，Yahoo! Web API1を用いた．検索 API のパラメータとしては，基本的な機能のみを利用した．具体的には，1 回の検索で返される文書の最大件
数 result を 50，検索結果の先頭位置 start を 0，検索対象とするファイルの種類 format を html，検索対象の言語
language は辞書のターゲット言語が英語の場合は en，日本
語の場合は jp を設定した．

3.1 抽出部のパラメータ設定
同一条件で様々な検索戦略を比較するため，最初に抽出部
における，一貫性判定パラメータμ，およびヘテロ性判定パ
ラメータθの決定を行った．予備実験として，日本語の Actor
ドメインの初期シード語集合から 3 語ずつランダムに選んで20 種類のクエリを作成し，それぞれ 1 回ずつ検索を行って1000 件の Web ページを得た．この 1000 ページに対して，各パラメータの値を変化させながらシード語として追加される新語の数と正解率を測定した．その結果，正解率 90%以上

1

http://developer.yahoo.co.jp/

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

論文
DBSJ Letters Vol.6, No.4――――――――――――――――――――――――――――――――――――
を達成し，新語の数が最も多くなるパラメータの組み合わせとして(μ, θ) = (0.5, 5) を得た．以下，これら 2 つのパラメータを固定して実験を行った．
ローカルパタンの例を表 1 に示す．新語が HTML タグに挟まれていない「非タグ」のケースは 49.9%とほぼ半数を占めた．具体例としては，カンマ「,」やセミコロン「;」やダブ
ルクォーテーション「”」のような記号に挟まれたパタンがあった．また，パタンの一部にタグを含む「一部タグ」のケースは全体の 15.5%であった．具体例としては，シード語がハイフン「-」で列挙されるパタンや，シード語の後に年度を表す「(19」という文字列が付与されるパタンがあった．
一方，新語が HTML タグに正確に挟まれている「両側タグ」のケースは，全抽出パタンの 34.6%であった．具体例として
は，リ ン ク を 指 定 する <A> タ グ や オ プ シ ョ ン を 指 定す る
<OPTION>タグに挟まれたケースが大半であった．以上より，
文字列ベースのローカルパタンは HTML タグベースのパタンよりも多くの新語を抽出できることが分かる．

教育機関が確認できた語を正解として精度を評価した．
英語に関しては，合計で 64,642 語を平均 0.94 の精度で抽出できた．200 回の繰り返し処理後にも関わらずこれほど高い精度を達成できたのは，マルチシードクエリとローカルパタンにより実現されるロバスト性が主な原因である．例えば，
シングルシードクエリと比較してマルチシードクエリでは，クエリがノイズ語のみで構成される確率を低減できる．また，
ノイズ語により間違ったローカルパタンが構築されても，パタン自体が使い捨てであるため，影響範囲を限定できる．
不正解となったノイズ語の例としては，Actor ドメインでは，俳優名のタイプミス，ミュージシャンのような異なるカ
テゴリに属する人名があった．Film ドメインでは，俳優名
やミュージシャン名がノイズ語として含まれていた．
Location ドメインでは，大陸名，国名，州名などの広域地域
名がノイズ語であった．Company ドメインでは，国名や「Software」「Network」のような一般名詞がノイズ語であ3.2 検索戦略による同位語増殖効率の違い

3.3 言語・ドメイン別辞書構築結果
異なる言語，および異なるドメインにおける結果の概要を
表 3 に示す．本実験では，シードパラメータμと検索戦略パラメータγを，(μ,γ)= (3, 3) に固定して 200 回の検索を行った．また，最終的な同位語集合からランダムサンプリング
した 500 語について，実存する俳優，映画，都市名，企業，3

表1

ローカルパタンの例

Table.1 Examples of local patterns
パタン例
非タグ(49.9%)(例1) , Keanu Reeves,(例2) title="View all posts filed under Keanu Reeves">(例3) alt="Keanu Reeves" style="text-decoration;">両側タグ(34.6%)(例4) .htm">Keanu Reeves</A><IMG SRC=
(例5) ">Keanu Reeves</option> <option value="(例6) /">Keanu Reeves</a></li><br/> <li><a href="一部タグ(15.5%)(例7) <br><em>Starring Keanu Reeves</em><br>(例8) - Keanu Reeves<br>(例9) <br> </strong> Keanu Reeves (1930,00025,000

同位語増殖数 （語）検索戦略の評価として，英語の Actor と，Film ドメインにおいて検索結果を 200 回に固定して詳細な実験を行った．両ドメインの結果はほぼ同一の傾向であったため，ここでは，Actor ドメインにおける結果についてのみ述べる．
図 2 に，シードパラメータωと検索戦略パラメータγを変化させた場合の，同位語増殖数の違いを示す．γ=0 は，一様にランダムにω 語を選ぶ最も単純な検索戦略に相当する．
この場合，シードパラメータωを 2 とした場合に最大規模の
26,564 語が得られ，ωが大きいほど同位語増殖数は少なかった．これは，2.1 節で述べたように，ωが大きいと低共起性の問題が大きく，ほとんどのクエリで検索結果が 0 件になるからである．また，γを増やすとω≥3 における同位語増殖数は増加した．これは，高頻度・高信頼度語を優先的に利用した結果，低共起性の問題が緩和されたからである．一方，ω
=2 の場合は，γが増えると逆に同位語増殖数は減少した．その理由は，2 語のマルチシードクエリでは低共起性の問題は小さく，高頻度語を優先しても検索結果は増えない一方で，同じ高頻度語を含むクエリにより新語の重複が増えるからである．検索戦略パラメータがγ=4 になると，ω≥3 でも同位語増殖数が減少した．これは，ω=2 の場合と同様に，高頻度語の優先により新語の重複の効果が支配的になるからである．最終的に，(γ,ω) = (3,3)で，最大 27,344 語に増殖できた．
γ=3 での同位語増殖の詳細データを表 2 に示す．ω=2 の場合は，Crawler が取得したページ数は最大で，検索結果の重複率も少ないが，新語が抽出されたリストページの割合は0.23 に過ぎず，1 ページ当りに抽出された新語数も 5.8 語と少ないため，同位語数は 11,608 語に留まっている．これは，2 語のクエリではヒットするページは多いが，同位語が一貫性の高い書式で記述されている確率が低いことを示唆している．一方，ω=6 の場合は，リストページがヒットする確率は高いが，その数は限られており重複が多い．結果的に，ω
=3 で上記のトレードオフがバランスしている．

ω2
ω3
ω4
ω5
ω6

20,00015,00010,000
5,000
0
0

1

2

3

4

検索戦略パラメータ γ

図2

検索戦略に対する増殖数の変化

Fig.2 Effect of search strategy parameter γ
表2γ=3 での取得ページとリスト率のトレードオフ

Table.2 Trade-off of accessed/list pages at γ=3ω 同位語数2
3
4
5
6

11,60827,344
21,074
18,104
16,312

取得
ページ
8,753
5,885
4,138
2,796
2,159

重複率 リスト率
0.12
0.27
0.43
0.58
0.56

0.23
0.43
0.46
0.53
0.55

ページ当
り新語数
5.8
10.9
11.2
12.3
13.7

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

論文
DBSJ Letters Vol.6, No.4――――――――――――――――――――――――――――――――――――った．School ドメインでは国名や州名がノイズ語であった．
日本語に関しては，合計で 38,086 語を平均 0.84 の精度で抽出できた．不正解となったノイズ語のうち，日本語に特有のノイズ語が含まれるページについて調べたところ，大量の関連語を埋め込んで過剰に検索エンジン最適化を施した
Web ペ ー ジ が 目 立 っ て い た ． 例 え ば ， 最 も 精 度 の 悪 いCompany ドメインではノイズ語として，「食品系メーカー」
等の業界を表す表現，「警備員」等の職種を表す表現，「広島」
等の地名，などが数多く存在していた．これらが出現するページは，ほとんどが同じ就職・転職関連サイトへのリンクをあらゆる業界・職種・地域別のアンカー文字列で詰め込んだアフィリエイトページであった．このような過剰な検索エンジン最適化ページに対する対策は，今後の課題である．
最終的に，日・英あわせて 10 ドメインについて，合計 2,000回の検索で 102,728 語の辞書を精度 0.90 で構築できた．この時，クロールした全ページ数は 50,340 件であったので，1ページ当り約 2 語の新語を抽出できたことになる．一方，
KnowItAll[1] は ， 54,753 語 の 辞 書 を 構 築 す る た め に ，313,349 ページをクロールしており，1 ページ当りの新語抽出件数は 0.2 語にも満たない．対象としているドメインが若干異なるために単純な比較はできないが，この事実も提案手法の有効性を示している．
表3

河合 英紀

異なる言語・ドメインにおける結果の概要
Table.3 Lexicons in different domains
英語
同位語数

日本語
精度

同位語数

[2] Soderland, S., Etzioni, O., Shaked, T., Weld, D.: The
use of Web-based statistics to validate information
extraction. In: AAAI workshop on Adaptive Text
Extraction and Mining, 2004.
[3] 楠村幸貴, 土方嘉徳, 西田正吾: テンプレートの交叉とDOM 構造の解析による情報抽出手法の提案, 第 17
回データ工学ワークショップ(DEWS), 2006.
[4] Kushmerick, N.:Wrapper induction: efficiency andexpressiveness. In: AAAI Workshop on AI andInformation Integration, 1998.
[5] 野口正人, 廣川佐千男: Web からの同系統単語知識獲得についての実験, 情報処理学会第 65 回全国大会講演
論文集, p223-226, 2003.
[6] Wang, R. C., Cohen, W. W.: Languageindependent set
expansion of named entities using the Web. (toappear) In: Proc. IEEE International Conference on
Data Mining, 2007.
[7] 大島裕明, 山口雅史, 小山聡, 田中克己: Web 検索エン
ジンのインデックスとクエリログを用いた同位語発見,
情報処理学会データベースと Web 情報システムに関するシンポジウム(DBWeb2006)論文集, pp.305-312,
2006.
[8] 河合英紀, 水口弘紀, 土田正明: ブートストラップ式辞
書構築における検索効率の向上, データベースと Web
情報システムに関するシンポジウム (DBWeb), 2007.

精度

Actor

27,3440.93

10,9440.85

Film

17,5920.97

12,011

0.98

水口 弘紀

Location

6,496

0.92

2,646

0.87

Company

3,422

0.96

10,6200.68

School

9,788

0.91

1,865

0.84

合計

64,642

0.94

38,0860.84

平成 12 年筑波大学工学研究科 電子・情報工学専攻 修士課
程修了．同年日本電気株式会社入社．現在，NEC サービスプ
ラットフォーム研究所 主任．テキストマイニング，データ
ベース統合技術の研究開発に従事．情報処理学会，日本デー
タベース学会，各会員．

土田 正明

4. 結論
本稿では，検索回数を節約できる検索戦略を備えたブート
ラップ式辞書構築手法として，CESS フレームワークを提案
した．提案手法の特徴は，複数のシード語を組み合わせて
AND 検索するマルチシードクエリと，使い捨てのローカル
パタンの 2 点である．実験では，マルチシードクエリによって多数の同位語が構造化されたリストページがヒットしや
すくなり，周辺文字列の一貫性を考慮したローカルパタンによって高いロバスト性を達成できることを示した．日・英それぞれ 5 種類のドメインについて，200 回の検索で構築される辞書の規模と精度を評価し，合計 2000 回の検索で，10万語以上の辞書を精度 0.9 以上で構築することができた．

[文献］[1] Etzioni, O., Cafarella, M., Downey, D., Kok, S.,
Popescu, A.-M., Shaked, T., Soderland, S., Weld, D. S.,
and Yates, A.: Web-scale information extraction in
KnowItAll. In: Proc. the 13th International
Conference on World Wide Web, 2004.

4

Hideki KAWAI

平成 10 年慶應義塾大学大学院理工学研究科計測工学専攻修士課程修了．同年日本電気株式会社入社．平成 17 年から平成 18 年まで米国 Stanford 大学客員研究員．現在，NEC C&C
イノベーション研究所 主任．情報検索，Web マイニングに関する研究に従事．IEEE, ACM, 情報処理学会，日本データベ
ース学会各会員．

Hironori MIZUGUCHI

Masaaki TSUCHIDA

平成 17 年東京理科大学大学院理工学研究科経営工学専攻修士課程修了．同年日本電気株式会社入社．現在，NEC サービ
スプラットフォーム研究所にて情報抽出，情報検索に関する研究に従事．情報処理学会，言語処理学会，日本データベー
ス学会，各会員．

國枝 和雄

Kazuo KUNIEDA

平成元年京都大学大学院工学研究科情報工学専攻修士課程修了．平成 4 年 同 博士後期課程単位取得認定退学．同年
日本電気株式会社入社．GUI，航空ステレオ写真測量の研究開発に従事．現在，C&C イノベーション研究所研究部長．知識コンピューティング研究に従事．京都大学博士(工学)．映
像情報メディア学会，日本バーチャルリアリティ学会各会員．

山田 敬嗣

Keiji YAMADA

昭和 62 年京都大学大学院工学研究科情報工学専攻博士後期課程修了（工学博士）．同年 NEC C&C 情報研究所入社．平成 2
年から平成 3 年まで，カリフォルニア大学サンディエゴ校客員研究員．現在，NEC C&C イノベーション研究所研究所長．
パタン認識，人工神経回路網，機械学習，ユビキタス情報シ
ステムの研究に従事．情報処理学会，電子情報通信学会，IEEE
など会員．情報処理学会坂井記念特別賞，学術奨励賞等受賞．

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