\documentstyle[jnlpbbl]{jnlp_j_b5}
\setcounter{page}{47}
\setcounter{巻数}{10}
\setcounter{号数}{1}
\setcounter{年}{2003}
\setcounter{月}{1}
\受付{2002}{3}{18}
\再受付{2002}{7}{27}
\採録{2002}{10}{4}

\setcounter{secnumdepth}{2}

\title{類似学習例の除外とRocchioフィードバックを\\
弱学習アルゴリズムとするAdaBoostによる\\
レレバンスフィードバックの精度向上}
\author{中島 浩之\affiref{NTTCS}\affiref{NTTD}}

\font\headks=goth10 at 6.5pt
\font\headrs=cmr10 at 6.5pt
\def\HEADS{}

\headauthor{\HEADS 中島}
\headtitle{\HEADS 類似学習例の除外とRocchioフィードバックを
弱学習アルゴリズムとするAdaBoostによる
レレバンスフィードバックの精度向上}
\affilabel{NTTCS}{NTTコミュニケーション科学基礎研究所}
{NTT Communication Science Laboratories,$\;$NTT Corporation}
\affilabel{NTTD}{現在，NTTデータ技術開発本部}
{Presently with Research and Development Headquarters,$\;$NTT DATA Corporation}

\jabstract{
レレバンスフィードバックは検索者が与えた検索条件を利用してシステムが選択する文書(サンプル文書)について，検索者が必要文書と不要文書を選択し，フィードバックすることで，より正確な文書検索を実現する手法である．
レレバンスフィードバックによる検索精度はフィードバックの対象となるサンプル文書の選択方法によって異なる．通常のレレバンスフィードバックでは検索要求との関連が最も強いと推定される文書をサンプルとするレレバンスサンプリングが用いられるが，これに対して必要文書か不要文書かを分類するのが難しい文書をサンプルとするuncertaintyサンプリングが提案され，より高い検索精度が得られると報告されている．
しかしいずれのサンプリング手法も複数の類似した文書をサンプルとして選択することがあるため，検索精度が十分に向上しない恐れがあった．
本稿ではレレバンスサンプリングおよびuncertaintyサンプリングを改良する手段として
unfamiliarサンプリングを提案する．unfamiliarサンプリングは既存のサンプリング手法において，新たにサンプルとして加える候補と既存のサンプルの文書間距離を評価し，既存サンプルの最近傍であればサンプルから排除する．
この処理により，既存サンプルと類似した文書が排除されることにより検索精度が向上される．レレバンスフィードバックを用いた文書検索においては，少数のサンプル文書で高い精度を得ることが重要になる．本稿ではAdaBoostにおいてRocchioフィードバックを弱学習アルゴリズムとして用いる手法を提案し，これをRocchio-Boostと呼ぶ．
NPLテストコレクションを用いた実験の結果，unfamiliarサンプリングによる
サンプリング手法の改良とRocchio-Boostにより従来のRocchioフィードバック
とレレバンスサンプリングに対して平均適合率を6\,\%程度向上できることが分
かった．
}

\jkeywords{レレバンスフィードバック，Rocchioフィードバック，サンプリング}

\etitle{Removing Similar Documents\\
 from Training Samples and Applying\\
 Rocchio feedback as week learner of AdaBoost\\
 for Improving Relevance Feedback}

\eauthor{Hiroyuki Nakajima\affiref{NTTCS}\affiref{NTTD}}

\eabstract{
Relevance feedback is a method to achieve accurate information retrieval
through the application of both evaluated relevant and irrelevant sample documents which are chosen based on an initial query by the system.
Retrieval accuracy achieved by relevance feedback changes according to
the sample selection methodology for user judgement. Relevance sampling, a method which is often utilized for choosing samples, asks users to label the sample documents which are classified as most likely to be relevant. On the other hand, uncertainty sampling, a method which selects samples according to an unclear classification system, has been reported to be more effective than the original sampling method. However, both sampling methods may select multiple numbers of similar documents, and thus in both cases, the retrieval accuracy should be improved. 
In this paper, we propose `unfamiliar sampling', a method which evaluates the distance between each pair of documents and removes a candidate for sampling if it is the nearest neighbor of any sample that has already been selected. With this procedure, not only multiple numbers of similar documents are not used for sampling, but, moreover, retrieval accuracy improves.
 In applying relevance feedback for document retrieval, it is important to achieve high retrieval accuracy with a small number of sample documents. 
Also, in this paper, we propose `Rocchio-Boost', which applies Rocchio feedback as a weekly learner of AdaBoost. Furthermore, we show that it can achieve high retrieval accuracy. Empirical results on NPL test collection show that the proposed methods improve the average precision of retrieval by 6\% over the original relevance sampling and Rocchio feedback.
}

\ekeywords{Relevance feedback, Rocchio feedback, Sampling}

\begin{document}

\thispagestyle{empty}
\maketitle

\section{はじめに}
文書データベースから必要な文書を検索する場合，対象となる文書を正確に表
現する検索式を作成する必要がある．しかし正確な検索式を作成するためには，
検索対象となる文書の内容について十分な知識が必要であり，
必要な文書を入手する前の検索者にとって適切な検索式を作成するのは難しい．
レレバンスフィードバックはこの問題を解決する手法であり，
システムと検索者が協調して検索式を作成することで，
検索者にとって容易かつ高い精度で文書検索を行う手段である．
検索者はまず初期の検索条件を与え，この検索条件により検索される文書から
システムが特定のアルゴリズムに従ってサンプル文書を選択する(本稿ではこの
選択アルゴリズムをサンプリングと呼ぶ)．
サンプル文書から検索者が必要文書と不要文書を選択すると，選択された文書
からシステムが自動的に検索条件を更新し，検索を行う．
この検索結果に対してシステムによるサンプリング，検索者による選択，再検
索が繰り返される．
この選択による検索条件の更新がレレバンスフィードバックであり，検索結果
について必要文書と
不要文書を選択することで，利用者は容易に必要文書を収集することができる．
また，この選択--検索のプロセスを繰り返すことで，検索条件がより検索者の
ニーズを反映したものとなるとともに，検索者は検索要求に適合する文書をよ
り多く入手することができる．

レレバンスフィードバックの検索精度はサンプリング手法によって異なる．
通常のレレバンスフィードバックでは最も検索条件に適合すると考えられる
文書をサンプル文書とする（本稿ではこの手法を「レレバンスサンプリング」
と呼ぶ）．
これに対してLewisらはuncertaintyサンプリングを提案している
\cite{bib:DLewis}．
これは文書のうち必要であるか不要であるかを最も判定しにくい
ものをサンプルとする手法で，レレバンスサンプリングよりも高い検索精度が
得られると報告されている．

これらサンプリング手法は検索結果の上位から順に（レレバンスサンプリング），
ないし必要文書と不要文書の境界と推定される文書，およびその前後の順位の
文書（uncertaintyサンプリング）をサンプル文書として選択する．
このため検索条件との適合度により順位付けされた検索結果
のうち，適合度がある範囲にある文書からサンプルが選択される．
比較的類似した文書は同じ検索条件との適合度が類似した値となる傾向が
あることから，これらサンプリング手法は複数の類似した文書をサンプルとし
て選択する可能性が高い．

この問題点に対処するため，筆者はunfamiliarサンプリングを提案する．
unfamiliarサンプリングはレレバンスサンプリングおよびuncertaintyサンプ
リングを改良する手法であり，既存のサンプル文書と類似した文書がサンプル
として追加されないように，サンプル選択の際に既存のサンプルと文書間距離
が近いサンプルを排除する．
この改良により，選択されるサンプル文書はよりバラエティに富んだものとな
り，複数の類似した文書がサンプルとして用いられる場合に比べて検索精度の
向上が期待できる．

レレバンスフィードバックを用いた文書検索を行う場合，
検索者が多くの文書について必要ないし不要の判定をすることは考えにくいので，
少数のサンプル文書で高い精度を得ることが重要になる．
近年，文書検索や文書分類を高い精度で実現する手法としてAdaBoostがよく用
いられる\cite{bib:Boost}．AdaBoostは既存の分類アルゴリズム(弱学習アル
ゴリズム)を組合せることでより精度の高いアルゴリズムを生成する手法であ
るが，決定株，ベイズ推定法を弱学習アルゴリズムとして用いる場合，
サンプル文書が少ない場合にはRocchioフィードバックに劣る精度となること
が知られている\cite{bib:Boost_and_Rocchio,bib:Yu}．
本稿ではRocchioフィードバックを弱学習アルゴリズムとして用いる例
(Rocchio-Boost)を示し，
実験により少数のサンプル文書でも高い検索精度を実現することを示す．

次章以降の本稿の構成は次の通りである．
2章で既存のレレバンスフィードバック技術であるRocchioフィードバックにつ
いて述べ，3章ではAdaBoostのRocchioフィードバックへの適用について述べる．
4章で既存のサンプリング手法であるレレバンスサンプリング，uncertaintyサ
ンプリングについて述べ，5章で提案手法であるunfamiliarサンプリングにつ
いて述べる．
6章で実験に用いたNPLテストコレクションおよび実験手法について述べる．
7章で実験結果とその考察について述べ，8章で本稿のまとめを述べる．


\section{従来のレレバンスフィードバック技術}
\label{sec:jyuurai}
本章ではレレバンスフィードバックを実現する標準的な手法であるRocchioフィー
ドバックアルゴリズムについて述べる．

Rocchioフィードバック\cite{bib:Rocchio}はベクトル空間法とTF/IDF法
\cite{bib:Salton}を用いた文書検索システムにおいて，レレバンスフィード
バックを実現する．
Rocchioフィードバックは検索要求文とその要求に適合するかどうか判定
された文書(サンプル文書)を入力として，検索要求を表すベクトルを出力する．
作成されたベクトルと検索対象となる文書のベクトルの内積が，
文書と検索要求文との関連度を示す．

ベクトル空間法\cite{bib:Salton}は文書や検索要求文をベクトル空間上のベ
クトルとして表現する．
このベクトルは文書および文中の単語が持つ重要性を示す``重み''を要素とし
て持つ．

TF/IDF法は，文書データベース中の
少数の文書に数多く登場する語を重要な語として扱い，
大きな重みを与えることで語の``重み''を決定する
\cite{bib:Salton,bib:Umino,bib:Buckley}．
本稿ではTF/IDF法の一つである{\it ltc-lnc}手法について述べる
\cite{bib:Buckley5}．

{\it ltc-lnc}手法は検索要求文，サンプル文書については{\it ltc}手法によ
り単語の持つ重みを計算することでベクトルを作成し，検索対象文書について
は{\it lnc}手法によって同様にベクトルを作成する．

{\it ltc}手法は以下の式により単語の重みを計算する．\\
文ないし文書$d_{j}$中の単語$t_{i}$の重み$w_{i,j}$は，
文ないし文書$d_{j}$中に単語$t_{i}$が出現する回数$f_{i,j}$
（Term Frequency,$\:$TF）および
単語$t_{i}$が出現する文書データベース中の文書数$n_{i}$の
逆数（Inverted Document Frequency,$\;$IDF）を用いて以下の式により計算
される
\cite{bib:Buckley}．
\[
w_{i,j}=\frac{(\log(f_{i,j})+1.0)*log(\frac{|DB|}{n_{i}})}
{\sqrt{\sum_{k=1}^{N}{(\log(f_{k,j})+1.0)*log(\frac{|DB|}{n_{k}})}^2}}
\label{eqn:tf-idf}
\]

なお$|DB|$は文書データベース中の文書総数である．

{\it lnc}手法は以下の式により単語の重みを計算する．
\[
w'_{i}=\frac{(\log(f_{i})+1.0)}
{\sqrt{\sum_{k=1}^{N}{(\log(f_{k})+1.0)}^2}}
\]

Rocchioフィードバック\cite{bib:Rocchio}は検索要求文およびサンプル文書
のベクトルを用いて以下の式により検索者の意図を反映したベクトルを作成する．
検索要求文のベクトルを$v_q$，提示した文書中から検索者が選択した必要文書
$num_{rel}$件の持つベクトルの和を$v_{rel}$，
検索者が選択しなかった文書（不要文書）$num_{nonrel}$件
の持つベクトルの和を$v_{nonrel}$としたとき，新たなベクトルは
\[
v = \alpha v_{q} + \frac{\beta v_{rel}}{num_{rel}} - \frac{\gamma v_{nonrel}}{num_{nonrel}}
\]
となる．ここで$\alpha, \beta, \gamma$は定数(本稿では各々16,32,8とした)，
また重みが負の値となる語は用いない．
得られたベクトルと検索対象となる文書のベクトルの内積値が，
検索要求に対する文書の関連度を表す．
関連度が高い文書は必要文書に，関連度の低い文書は不要文書に分類されたと
考えることができるため，
Rocchioフィードバックは必要ないし不要の判定がされたサンプル文書を学習
例として，未知の文書について必要ないし不要の判定をする分類学習アルゴリ
ズムと考えられる．
また内積値の大きさが必要文書に分類される確からしさを表していると考えら
れる．

\section{Rocchio-Boost}
AdaBoostはランダム予測より良い予測を行う学習アルゴリズム(弱学習アルゴリズム)を
組み合わせることで，より高精度な予測を行う強学習アルゴリズムを構成する
アルゴリズムであり，多くの実験結果から既存の分類学習アルゴリズムを
弱学習アルゴリズムとして得られる強学習アルゴリズムは，従来の分類学習
アルゴリズムに比べて高い性能が得られることが示されている\cite{bib:Boost}．
AdaBoostの特徴は学習例に重みを付け，弱学習アルゴリズムでは学習が難しい
学習例の重みを相対的に増加させることで，難しい例に適応した学習結果を得
ること，また重み付きの学習例に対する学習の正確さを評価し，その正確さに
応じた重みを付けて各学習結果を結合して強学習アルゴリズムを得る点にある．

AdaBoostは多くの実験によりその効果が確認されているが，
得られる強学習アルゴリズムの性質は弱学習アルゴリズムの性質に強く
依存する．レレバンスフィードバックへの適用例として決定株，ベイズ推定
を弱学習アルゴリズムとする手法が提案されているが，十分な数の学習例が得
られる場合にはRocchioフィードバックより優れた精度が得られるものの，決
定株，ベイズ推定は学習例が少ない場合には良好な精度が得られないため，こ
れらを弱学習アルゴリズムとするAdaBoostは少ない学習例ではRocchioフィー
ドバックに劣る精度となることが報告されている
\cite{bib:Boost_and_Rocchio,bib:Yu}．
これら結果は逆に，Rocchioフィードバックが少数の学習例でも良好な精度
を示すと捉えることができる．

Rocchioフィードバックによる検索対象文書の順位付けは
文書を必要文書ないし不要文書に分類していると考えることができるため，
Rocchioフィードバックを弱学習アルゴリズムとして用いることもできる．
Rocchioフィードバックは少ない学習例でも比較的良好な精度が得られると考
えられることから，Rocchioを弱学習アルゴリズムとしてAdaBoostを適用する
ことで，少数の学習例でも良好な結果が得られる可能性がある．

ここではRocchioフィードバックを弱学習アルゴリズムとしてAdaBoostを適用
したアルゴリズムの一例(Rocchio-Boost)を示す．
AdaBoostは弱学習アルゴリズムによる
分類結果に，分類の確からしさを示すスコアが与えられる場合，これを信頼度
(confidence ratio)として利用することができる\cite{bib:Boost_conf}．以
下では長さ1に正規化した
Rocchioフィードバックによるベクトルと，文書ベクトル間の内積値(0から1ま
での値を取る)を-1から1にマッピングし，これを信頼度として用いる．

\begin{enumerate}
\item $x_{i}$を$i$番目のサンプル文書，$y_{i}$を$x_{i}$が正解文書なら1，
不要文書なら-1とする．$m$をサンプル文書数とする．
\item $D_{1}(i)=\frac{1}{m}$とする(学習例の重みを示す変数)
\item ラウンド$s$を1から1ずつ加算して$T$に達するまで以下の作業を繰
り返す
\begin{enumerate}
\item Rocchioフィードバックの式により$\vec{Q}_{s}$を計算する
\begin{eqnarray*}
\vec{Q}_{s} & = & \alpha\vec{Q}_{org}\\
& & + \frac{\beta m}{R}\sum_{y_{i}=1}{D_{s}(i)\vec{x_{i}}}\\
& & - \frac{\gamma m}{N}\sum_{y_{j}=-1}{D_{s}(j)\vec{x_{j}}}
\end{eqnarray*}
ここで$\vec{x_{i}}$は文書$x_{i}$のベクトルを表す．
\item ベクトル$\vec{Q'}_{s}=\frac{\vec{Q}_{s}}{|\vec{Q}_{s}|}$とする．
\item $\vec{Q'}_{s}$とサンプル文書$x_{i}$のベクトルの内積$p_{i}$を計算
し，$h_{s}(x_{i})=2p_{i}-1$とする($\vec{Q'}_{s}$と文書ベクトルの内積値
が0から1までの値を取るため，$-1 \leq h_{s}(x_{i}) \leq 1 $となる)．
\item 弱学習アルゴリズムによる学習の正確さを示す変数$\alpha_{s}$を以下
の式で求める．
\[
r = \sum_{i=1}^{m}D_{s}(i)y_{i}h_{s}(x_{i})
\]
\[
\alpha_{s} = \frac{1}{2}\ln(\frac{1+r}{1-r})
\]
\item 学習例の重みを更新する．
\[
D_{s+1}(i) = \frac{D_{s}(i)\exp{(- \alpha_{s}y_{i}h_{s}(x_{i})})}{Z_{s}}
\]
$Z_{s}$はいずれのラウンド$s$でも
\[
\sum_{i}D_{s+1}(i)=1
\]
となるよう定める．
\end{enumerate}
\item ラウンド$s$が$T$に達したら，各ラウンド$s$で得られた
$\alpha_{s}$，$h_{s}$，$\vec{Q'_{s}}$を用いて最終的な強学習アルゴリズム
を得ることができる．
検索対象となる文書$x'_{i}$の文書ベクトルを$\vec{x'_{i}}$とすると，
最終的な強学習アルゴリズム$H(x'_{i})$は
\begin{eqnarray*}
H(x'_{i}) & = & \sum_{s=1}^{T}{\alpha_{s} h_{s}(x'_{i})}\\
& = & \sum_{s=1}^{T}{\alpha_{s}(2(\vec{Q'_{s}} \cdot \vec{x'_{i}})
- 1)}\\
& = & 2(\sum_{s=1}^{T}{\alpha_{s}\vec{Q'_{s}}}) \cdot
\vec{x_{i}}-\sum_{s=1}^{T} \alpha_{s}
\end{eqnarray*}
となり，この式の値が検索要求に対して文書$x'_{i}$が持つ関連度となる．
なお上式では文書$x'_{i}$を評価する際にRocchioフィードバックと同じく
内積計算は一度のみ行えばよい．
$H(x'_{i})$が大きい文書$x'_{i}$ほど検索要求に適合する度合が強いと考えら
れ，この値の大小で文書をソートし順位付けして出力する．
\end{enumerate}

\section{既存のサンプリング手法}
本章では既存のサンプリング手法について述べる．
レレバンスサンプリングは最も検索条件に適合すると考えられる文書をサンプ
ル文書とする手法であり，レレバンスフィードバックでのサンプル選択方法と
して最も良く用いられる．
サンプル文書と検索者が閲覧する文書を同一のものとした場合，レレバンス
フィードバックの繰り返しの過程で検索者に示されるサンプル文書は，常に既
知のサンプルから推定される最も検索要求に合致した文書となる．
このため，少数の正解文書を閲覧すれば十分な場合，サンプル文書の閲覧と
フィードバックのみで目的が達成できる．

以下にレレバンスサンプリングのアルゴリズムを示す．
なお，本稿では各フィードバックにおいて選択されるサンプル文書を$n$文書と
し，この$n$文書を各サンプリング手法により選択するものとする．
また各フィードバックにおいては既存のサンプル文書全てを用いる．
このためフィードバックの繰り返しごとにサンプル文書は$n$文書ずつ増加す
る．

\renewcommand{\theenumii}{}
\begin{enumerate}
\item 検索要求と既存のサンプル文書を用いたレレバンスフィードバックで得
られる分類アルゴリズムを$A_{1}$とする．
\item $s=1$として$s$を1ずつ加算して以下を任意の回数繰り返す．
\begin{description}
\item[(a)] 検索対象の文書$x_{i}$をアルゴリズム$A_{s}$により分類し，
より必要文書である(検索要求に適合する)と判定された文書の順に順位付けす
る．
\item[(b)] 高い順位の文書から$n$文書選択する．なお既存のサンプル文書は選択
対象から外す．
\item[(c)] 選択された$n$文書について必要/不要の判定を行い，サンプル文書に追
加する．
\item[(d)] 増加したサンプル文書を用いてレレバンスフィードバックを行い新たな
分類アルゴリズム$A_{s+1}$を得る．
\end{description}
\end{enumerate}

このレレバンスサンプリングと異なるサンプリング手法としてLewisらによっ
てuncertaintyサンプリングが提案されている\cite{bib:DLewis}．
これは文書のうち必要であるか不要であるか最も判定しにくいものをサンプル
とする手法である．
このサンプリング手法を用いることで，より良い分類学習が可能となり，
最終的に得られる検索結果はレレバンスサンプリングに比して良くなると報告
されている．
uncertaintyサンプリングによるレレバンスフィードバックの過程では，
検索者に示されるサンプル文書はレレバンスサンプリングに比べて検索要求と
の関連は低いため，
フィードバックの過程で検索者が閲覧する文書の正解率は低い．
このため，少数の正解文書を閲覧すれば十分な場合でも，
サンプル文書とは別に検索結果の上位文書を閲覧する必要がある．

以下にuncertaintyサンプリングのアルゴリズムを示す．
\begin{enumerate}
\item 検索要求と既存のサンプル文書を用いたレレバンスフィードバックで得
られる分類アルゴリズムを$A_{1}$とする．
\item $s=1$として$s$を1ずつ加算して以下を任意の回数繰り返す．
\begin{description}
\item[(a)] 検索対象の文書$x_{i}$をアルゴリズム$A_{s}$により分類し，
より必要文書である(検索要求に適合する)と判定された文書の順に順位付けす
る．
\item[(b)] 必要文書か不要文書か最も分類が難しい文書から順に$n$文書選択する．
「最も分類が難しい文書」としては分類アルゴリズムにより出力される
分類の確からしさを表す値を用いて判定するが，
AdaBoostでは強学習アルゴリズム$H(x_{i})$がこれに相当する．
$H(x_{i})$が0に近いほど必要文書か不要文書か最も曖昧な，分類の難しい文
書と判定されるので，$H(x_{i})$が0に近い文書から$n$文書を選択する．
なお既存のサンプル文書は選択対象から外す．
\item[(c)] 選択された$n$文書について必要/不要の判定を行い，サンプル文書に追
加する．
\item[(d)] 増加したサンプル文書を用いてレレバンスフィードバックを行い新たなベ
クトル$A_{s+1}$を得る．
\end{description}
\end{enumerate}

\section{unfamiliarサンプリング}
検索要求に対して文書検索結果を順位付きで出力する文書検索システム
(例えばWebサイトを検索するインターネット検索サイト等)
を用いると，ほとんど同じ内容の文書が近い順位に複数提示されることがある．
\footnote{この現象はクラスタ仮説(「文書が類似していれば，同じ検索要求に対する適合性も同様に類似している」\cite{bib:Cluster_hypo})の妥当性を裏付けるものと考えられる．}
これはサンプリングにおいて以下のような問題を起こす可能性がある．

レレバンスサンプリングは検索結果の上位文書を，uncertaintyサンプリング
は最も判定が難しい文書をサンプル文書として選択する．
このため検索要求との適合度により順位付けされた検索結果のうち，適合度が
一定の範囲にある文書からサンプルが選択される．
互いに類似した文書の文書ベクトルは，多くの共通した単語を同じ重みで持つ
ことが多いため，同じ検索要求との適合度が類似した値となることがあり，
これらサンプリング手法は複数の類似した文書をサンプルとして選択する可能性が
ある．
文書データベースには内容がほぼ同一の文書が複数登録されていることがある
ため，サンプルとして追加される文書が全て同じ内容の文書となるこ
とすらあり得る．
このような場合，サンプル文書を追加しても，検索精度向上の効果が十分に得
られない恐れがある．

この問題点は互いに類似した文書がサンプル文書として用いられるために生じ
る．そのため追加サンプル選択の際に，既存のサンプル文書と文書間距離が近
い文書を対象から除外することで，この問題を避けることができる．
本稿では$ltc$手法により計算される文書ベクトル間の内積値を文書間距離と
して用い，
レレバンスサンプリングおよびuncertaintyサンプリングにおける追加サンプ
ル文書選択の際にいずれか既存のサンプル文書の最近傍(＝全ての文書の中で
内積値が最小となるもの)となっていないか確認する．
もしいずれか既存のサンプル文書の最近傍であれば，既存サンプルの類似文書
と考えられるので，この文書はサンプルとして追加しないことで，類似した文
書がサンプルに追加されるのを防ぐ．

レレバンスサンプリングに類似サンプル除外の手順を加えると，(2)-(b)の手順が
以下の(2)-(b)\('\)に置き換わる．
\begin{description}
\item[(2)-(b)\('\)] $t=0$とし，$t < n$の間，以下を繰り返す．
\begin{enumerate}
\item 順位付けされた文書から(2)-(b)\('\)で処理されていない最も内積値の高い文
書$x_{i}$を取り出す．
なお既存のサンプル文書は対象から外す．
\item $x_{i}$がいずれのサンプル文書の最近傍でなければサンプル文書集合
に追加し$t$を1加算する．最近傍ならサンプル文書集合に加えない．
\end{enumerate}	
\end{description}

uncertaintyサンプリングも手順(2)-(b)が以下の(2)-(b)\(''\)に置き換わる．
\begin{description}
\item[(2)-(b)\(''\)] 
$t=0$とし，$t < n$の間，以下を繰り返す．
\begin{enumerate}
\item 順位付けされた文書から(2)-(b)\(''\)で処理されていない文書のうち，
最も$H(x_{i})$が0に近い文書$x_{i}$を取り出す．
なお既存のサンプル文書は対象から外す．
\item $x_{i}$がいずれのサンプル文書の最近傍でなければサンプル文書集合
に追加し$t$を1加算する．最近傍なら集合に加えない．
\end{enumerate}	
\end{description}

本稿では上記の手順でサンプリングの際に類似文書を除外する手法を
unfamiliarサンプリング
と呼ぶ．
このunfamiliarサンプリングをレレバンスサンプリング，
uncertaintyサンプリングに適用することで，選択されるサンプル文書はより
バラエティに富んだものとなり，複数の類似した文書がサンプルとして用いら
れる場合に比べて検索精度の向上が期待できる．

\section{実験}
\label{sec:experiment}
本章では実験に用いたデータと実験手順について述べる．
\subsection{実験に用いたデータ}
検索精度の評価には，英文を対象とした文書検索テストコレクションとして
広く用いられているNPLテストコレクション
\cite{bib:NPL,bib:Glasgow}を用いた
（表\ref{table:collections}，対象文書は物理分野の文献の要約）．
テストコレクションは文書の集合と検索要求文からなり，
検索要求文に対して関連する文書（正解）が与えられている．
\begin{table}[tbp]
\begin{center}
\caption{NPLテストコレクション}
\begin{tabular}{c|c|c|c|c} \hline
文書数 & 文書総量(MB) & 質問数 & 平均質問語数 & 平均正解数 \\ \hline
11429 & 3.1 & 93 & 6.7 & 22.4 \\ \hline
\end{tabular}
\label{table:collections}
\end{center}
\end{table}
テストコレクションの各質問，文書からは
FreeWAIS-sf
\cite{bib:free_wais}の不要語辞書に登場する語を除去後，
Porterのstemmingアルゴリズム\cite{bib:Porter}により
語幹を取り出して利用した．

\subsection{実験手順}
以下に実験手順を示す．
\begin{enumerate}
\item 検索要求文からTF/IDF法を用いて$\vec{v_{q}}$を作成し，各文書の
ベクトルとの内積を計算して各文書のスコアとする．
\label{enu:normal_search}
\item スコア上位30件を最初のサンプル文書集合とする．なお，
この30件の文書については精度評価に用いない．
\item $f＝1$として以下のフィードバックを繰り返す．各フィードバックによっ
てサンプル文書が追加されるが，
各サンプリング手法，文書順位付け手法によって追加されるサンプル文書が
異なり，その違いが検索精度に与える影響を検証する．
\begin{description}
\item[(a)] テストセットの正解を用いてサンプル文書集合中の各文書について正解
（$=$必要文書）と不正解（$=$不要文書）を判定する．
\label{enu:sample_doc}
\item[(b)] RocchioフィードバックおよびRocchio-Boost(ラウンド数$T=50$)
により，検索対象文書の順位付けを行う．
$\alpha,\beta,\gamma$は文献\cite{bib:Buckley}より各々8,16,4とした．
また他の弱学習アルゴリズムを用いたAdaBoostと比較するため，
決定株を用いたAdaBoost(BoosTexterを使用\cite{bib:Boostexter})
\footnote{学習例には$ltc$手法により重み付けされた文書ベクトルを与え
た．ラウンド数$T$は300とした．}
も用いる．
\item[(c)] 順位付けされた出力の各順位での適合率の平均を求める．
評価にはtrec\_eval\cite{bib:trec_eval}を使用した．
なお検索結果が検索要求文に対する正解記事であれば正解とする．
\item[(d)] 順位付けされた結果から各サンプリング手法によりサンプル文書を選択
し，サンプル文書集合に追加する．
\item[(e)] $f$に1を加算し，(a)に戻る．
\end{description}
\end{enumerate}

なおRocchioフィードバックによって順位付けを行う場合，uncertaintyサンプ
リングでの$H(x_{i})$による「最も分類が難しい文書」の判定ができないため，
代わりにサンプル文書中で最も順位の低い必要文書と最も順位の高い不要文書
の中間の順位の文書を「最も分類が難しい文書」として扱い，その文書より
上位にある4文書，下位にある5文書をサンプル文書として選択した．

\section{実験結果}
各サンプル手法のフィードバック回数$f$における平均適合率を
表\ref{table:NPL_n30}に示す．

\begin{table*}[tbp]
\begin{center}
\caption{平均適合率(\%)}
\begin{tabular}{c|c||c|c|c|c} \hline
サンプリング手法 & 順位付け & $f = 1$ & $f = 2$ & $f = 3$ & $f = 4$\\ \hline \hline
{\bf rel}     & {\bf Boost}  & 6.46 & 10.61 & 15.39 & 20.23 \\ \hline \hline
{\bf rel}     & {\bf Roc}    & 14.78 & 21.26 & 28.28 & 35.15 \\ \hline
{\bf rel+unf} & {\bf Roc}    & -     & 21.98 & 29.47 & 36.55 \\ \hline
{\bf unc}     & {\bf Roc}    & -     & 21.29 & 28.30 & 35.16\\ \hline
{\bf unc+unf} & {\bf Roc}    & -     & 22.01 & 29.69 & 36.71 \\ \hline \hline
{\bf rel}     & {\bf Roc-Boo} & 14.83 & 21.73 & 31.31 & 38.35 \\ \hline
{\bf rel+unf} & {\bf Roc-Boo} & -     & 22.77 & 34.16 & 38.42 \\ \hline
{\bf unc}     & {\bf Roc-Boo} & -     & 21.74 & 31.31 & 38.35 \\ \hline
{\bf unc+unf} & {\bf Roc-Boo} & -     & 22.82 & 34.54 & 38.94 \\ \hline
\end{tabular}
\label{table:NPL_n30}
\end{center}
\end{table*}

表中{\bf rel}がレレバンスサンプリング，{\bf unc}がuncertaintyサンプリ
ングを示す．{\bf +unf}はunfamiliarサンプリングをレレバンスサンプリング，
uncertaintyサンプリングに適用したことを示す．
また``順位付け''の欄は検索結果の順位付けに用いた手法を示し，それぞれ
Rocchioフィードバック({\bf Roc})，Rocchio-Boost({\bf Roc-Boo})，決定株
を弱学習アルゴリズムとするBoosTexter({\bf Boost})を示す．
なおフィードバック回数$f=1$では検索要求文による検索結果の上位30件をサ
ンプルとして用いるので，サンプリング手法による違いはない．

本稿で用いた学習例は30文書($f=1$)から60文書($f=4$)
と比較的少数であるが，Rocchioフィードバックを弱学習アルゴリズムとする
AdaBoost({\bf Roc-Boo})がRocchioフィードバック({\bf Roc})より優れた結果
を示している．一方，弱学習アルゴリズムに決定株を用いる場合
({\bf Boost})，本実験で扱う少数の学習例では優れた結果が得られないことが
確認できる．
そのため弱学習アルゴリズムとしてRocchioフィードバックを用いたことが，
少数の学習例でも比較的良好な精度が得られるアルゴリズムとなった原因
と考えられる．

unfamiliarサンプリング({\bf +unf})をレレバンスサンプリング，
uncertaintyサンプリングに適用すると{\bf Roc}，{\bf Roc-Boo}ともに検索
精度が向上している．
順位付けを{\bf Roc}から{\bf Roc-Boo}に変えた場合と同じ程度，すなわち
AdaBoostによる精度向上効果と同じ程度の効果を示す場合もあり，比較的良好
な結果と考えられる．
unfamiliarサンプリングとRocchio-Boostの両方を適用した場合には
$f＝3$で6\,\%程度の精度向上効果が得られていることがわかる．

本稿で実施した実験ではレレバンスサンプリング({\bf rel})とuncertaintyサ
ンプリング({\bf unc})で精度にほとんど差が見られない．
表\ref{table:common_sample}に順位付けにRocchio-Boostを用いた場合に
レレバンスサンプリングとuncertaintyサンプリングの両方で用いられる
サンプル数(共通サンプル数)を示す(サンプル数は全ての検索要求文について
の平均)．
\begin{table}[tbp]
\begin{center}
\caption{共通サンプル数}
\begin{tabular}{c||c|c|c} \hline
 &  $f = 2$ & $f = 3$ & $f = 4$\\ \hline \hline
総サンプル数 & 40 & 50 & 60 \\ \hline
共通サンプル数 & 38.04 & 46.11 & 54.17 \\ \hline
\end{tabular}
\label{table:common_sample}
\end{center}
\end{table}
これはuncertaintyサンプリングで最も分類が難
しいと判断される文書が比較的高い順位にあり，その前後の文書を選択して
も，検索結果の上位から文書を選択するレレバンスサンプリングとあまり差が
ないためと考えられる．
どの文書を最も分類が難しいと判断するかによって精度が変化すると考えられ
るので，$h_{t}(x_{i})=0$に最も近い点ではなく，必要文書の平均順位と不要
文書の平均順位の中間の順位にある文書を最も分類が難しい文書とした場
合の結果({\bf unc2})を
表\ref{table:unc_n30}に示す．

\begin{table}[tbp]
\begin{center}
\caption{2つのuncertaintyサンプリングの比較}
\begin{tabular}{c|c||c|c|c} \hline
サンプリング手法 & 順位付け & $f = 2$ & $f = 3$ & $f = 4$\\ \hline \hline
{\bf unc}  & {\bf Roc-Boo} & 21.74 & 31.31 & 38.35 \\ \hline
{\bf unc2} & {\bf Roc-Boo} & 23.51 & 30.18 & 33.35 \\ \hline
\end{tabular}
\label{table:unc_n30}
\end{center}
\end{table}

{\bf unc}と{\bf unc2}で精度が大きく異なる．{\bf unc2}は{\bf unc}より優
れた方法とはいえないが，少なくとも{\bf unc}における「最も分類が難しい
文書」の選択方法を変化させることで精度が向上する場合があることがわかる．

\section{まとめ}
レレバンスフィードバックにおけるサンプル文書選択(サンプリング)において，
類似したサンプルが追加されることを防ぐunfamiliarサンプリングと，
少ないサンプル数でも良好な検索精度を得ることができるRocchioフィードバッ
クを弱学習アルゴリズムとするAdaBoost(Rocchio-Boost)を提案した．
これら手法をNPLテストコレクションを用いて検証したところ，
従来手法に比較して平均適合率を6\,\%程度向上させることができた．
また弱学習アルゴリズムとして決定株を用いるAdaBoost(BoosTexter)と比較し
たところ，30から70文書程度の比較的少数のサンプル数ではBoosTexterは
Rocchioフィードバックに劣る検索精度であるのに対して，
Rocchio-BoostはRocchioフィードバックより優れた検索精度を示したことから，
少数のサンプル数においてRocchioフィードバックを弱学習アルゴリズムと
して用いる手法が有効であることがわかった．

unfamiliarサンプリングを用いる際には文書間距離を計算する必要がある．
今回は文書ベクトル間の内積値を用いたが，
実際の検索システムでは大量の文書が検索対象となる上，
同じ文書が何回も検索されることがあるので，検索毎に内積値を計算するのは
無駄が多い．
あらかじめ文書間距離が近いものを計算しておく，ないし一度発見された最近
傍文書をキャッシュしておくなどの手段が必要になると考えられる．

本稿のRocchio-Boostでは弱学習アルゴリズムとしてRocchioフィードバック
を適用するAdaBoostの一例を示した．Rocchioフィードバックを弱学習アルゴ
リズムとして用いる手法は他にも考え得るが，本稿で提案する利用法では
検索対象文書との内積計算を一度だけ行えばよい．一般にTF/IDF法を用いる
文書検索においては，この内積計算に最も処理時間が必要となるが，通常の
Rocchioフィードバックと同じくRocchio-Boostにおいても内積計算は一度
のみ行えばよいので実用上の利点として大きいと考えられる．

本稿で述べた実験ではuncertaintyサンプリングの効果が明らかには得られな
かった．Rocchio-Boostにおける強学習アルゴリズム$H(x_{i})$では分類の
確からしさをうまく判定できていない可能性がある．また用いたテストコレク
ションによって効果に違いがある可能性があるので，条件を変更して検証する
予定である．



\bibliographystyle{jnlpbbl}
\bibliography{bunken}

\begin{biography}
\biotitle{略歴}
\bioauthor{中島 浩之}{
1994年東京工業大学大学院理工学研究科情報工学専攻修了．
1994年4月NTTデータ通信（株）（現（株）NTTデータ）入社．
2000年5月から2002年3月までNTTコミュニケーション科学基礎研究所に勤務．
2002年4月より（株）NTTデータ，現在に至る．
情報検索，言語処理の技術開発に従事．
情報処理学会および人工知能学会会員．}


\bioreceived{受付}
\biorevised{再受付}
\bioaccepted{採録}

\end{biography}
\end{document}
