\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法の一つである{\itltc-lnc}手法について述べる\cite{bib:Buckley5}．{\itltc-lnc}手法は検索要求文，サンプル文書については{\itltc}手法により単語の持つ重みを計算することでベクトルを作成し，検索対象文書については{\itlnc}手法によって同様にベクトルを作成する．{\itltc}手法は以下の式により単語の重みを計算する．\\文ないし文書$d_{j}$中の単語$t_{i}$の重み$w_{i,j}$は，文ないし文書$d_{j}$中に単語$t_{i}$が出現する回数$f_{i,j}$（TermFrequency,$\:$TF）および単語$t_{i}$が出現する文書データベース中の文書数$n_{i}$の逆数（InvertedDocumentFrequency,$\;$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|$は文書データベース中の文書総数である．{\itlnc}手法は以下の式により単語の重みを計算する．\[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=\alphav_{q}+\frac{\betav_{rel}}{num_{rel}}-\frac{\gammav_{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は弱学習アルゴリズムによる分類結果に，分類の確からしさを示すスコアが与えられる場合，これを信頼度(confidenceratio)として利用することができる\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}\itemRocchioフィードバックの式により$\vec{Q}_{s}$を計算する\begin{eqnarray*}\vec{Q}_{s}&=&\alpha\vec{Q}_{org}\\&&+\frac{\betam}{R}\sum_{y_{i}=1}{D_{s}(i)\vec{x_{i}}}\\&&-\frac{\gammam}{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\leqh_{s}(x_{i})\leq1$となる)．\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)&質問数&平均質問語数&平均正解数\\\hline11429&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{\bfrel}&{\bfBoost}&6.46&10.61&15.39&20.23\\\hline\hline{\bfrel}&{\bfRoc}&14.78&21.26&28.28&35.15\\\hline{\bfrel+unf}&{\bfRoc}&-&21.98&29.47&36.55\\\hline{\bfunc}&{\bfRoc}&-&21.29&28.30&35.16\\\hline{\bfunc+unf}&{\bfRoc}&-&22.01&29.69&36.71\\\hline\hline{\bfrel}&{\bfRoc-Boo}&14.83&21.73&31.31&38.35\\\hline{\bfrel+unf}&{\bfRoc-Boo}&-&22.77&34.16&38.42\\\hline{\bfunc}&{\bfRoc-Boo}&-&21.74&31.31&38.35\\\hline{\bfunc+unf}&{\bfRoc-Boo}&-&22.82&34.54&38.94\\\hline\end{tabular}\label{table:NPL_n30}\end{center}\end{table*}表中{\bfrel}がレレバンスサンプリング，{\bfunc}がuncertaintyサンプリングを示す．{\bf+unf}はunfamiliarサンプリングをレレバンスサンプリング，uncertaintyサンプリングに適用したことを示す．また``順位付け''の欄は検索結果の順位付けに用いた手法を示し，それぞれRocchioフィードバック({\bfRoc})，Rocchio-Boost({\bfRoc-Boo})，決定株を弱学習アルゴリズムとするBoosTexter({\bfBoost})を示す．なおフィードバック回数$f=1$では検索要求文による検索結果の上位30件をサンプルとして用いるので，サンプリング手法による違いはない．本稿で用いた学習例は30文書($f=1$)から60文書($f=4$)と比較的少数であるが，Rocchioフィードバックを弱学習アルゴリズムとするAdaBoost({\bfRoc-Boo})がRocchioフィードバック({\bfRoc})より優れた結果を示している．一方，弱学習アルゴリズムに決定株を用いる場合({\bfBoost})，本実験で扱う少数の学習例では優れた結果が得られないことが確認できる．そのため弱学習アルゴリズムとしてRocchioフィードバックを用いたことが，少数の学習例でも比較的良好な精度が得られるアルゴリズムとなった原因と考えられる．unfamiliarサンプリング({\bf+unf})をレレバンスサンプリング，uncertaintyサンプリングに適用すると{\bfRoc}，{\bfRoc-Boo}ともに検索精度が向上している．順位付けを{\bfRoc}から{\bfRoc-Boo}に変えた場合と同じ程度，すなわちAdaBoostによる精度向上効果と同じ程度の効果を示す場合もあり，比較的良好な結果と考えられる．unfamiliarサンプリングとRocchio-Boostの両方を適用した場合には$f＝3$で6\,\%程度の精度向上効果が得られていることがわかる．本稿で実施した実験ではレレバンスサンプリング({\bfrel})とuncertaintyサンプリング({\bfunc})で精度にほとんど差が見られない．表\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$に最も近い点ではなく，必要文書の平均順位と不要文書の平均順位の中間の順位にある文書を最も分類が難しい文書とした場合の結果({\bfunc2})を表\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{\bfunc}&{\bfRoc-Boo}&21.74&31.31&38.35\\\hline{\bfunc2}&{\bfRoc-Boo}&23.51&30.18&33.35\\\hline\end{tabular}\label{table:unc_n30}\end{center}\end{table}{\bfunc}と{\bfunc2}で精度が大きく異なる．{\bfunc2}は{\bfunc}より優れた方法とはいえないが，少なくとも{\bfunc}における「最も分類が難しい文書」の選択方法を変化させることで精度が向上する場合があることがわかる．
\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}