\section{はじめに}
\label{sec:introduction}文書検索では，検索対象の文書集合が大きくなるにつれ，高速/高精度な検索が困難になる．例えば，AltaVista~\footnote{{\tthttp://altavista.digital.com}}に代表されるインターネット上のキーワード検索エンジンでは，検索時に入力されるキーワード数が極端に少ないため~\footnote{AltaVistaでは平均2個弱のキーワードしか入力されない}，1)望んた文書が検索されない(再現率の問題)，2)望まない文書が大量に検索される(適合率の問題)，といった問題が生じている．そのため，要求拡張(queryexpansion)~\cite{smeaton:83:a,peat:91:a,schatz:96:a,niwa:97:a}，関連度フィードバック(relevancefeedback)~\cite{salton:83:a,salton:90:a}などの手法が提案されてきた．これらの手法はいずれも，要求となるキーワード集合を拡張したり洗練したりすることで，ユーザの検索意図を明確かつ正確なものに導いていく．これに対し，検索時にキーワード集合ではなく文書それ自身を入力し，入力文書と類似する文書を検索する方法が考えられる~\cite{wilbur:94:a}．この検索方法を{\gt文書連想検索}と呼ぶ．文書連想検索が有効なのは，検索要求と関連する文書を我々が既に持っているという状況や，キーワード検索の途中で関連する文書を一つでも見つけたという状況である．また，論文，特許など，我々自身が書いた文書もそのまま検索入力として利用できる．文書連想検索を使うことにより，適切なキーワード集合を選択することなしに，関連する文書を見つけることができる．文書連想検索を実現する際の問題点は，類似文書の検索に時間がかかることである．単純な網羅検索では，検索対象の大きさ$N$に比例した$O(N)$の時間を要する．そこで本論文では，{\gtクラスタ検索}~\cite{salton:83:a}と呼ばれる検索方法を用いる．クラスタ検索では，通常，クラスタリングによりクラスタの二分木をあらかじめ構築しておき~\footnote{クラスタリングにも，対象データ集合を平坦なクラスタ集合に分割する方法(非階層的クラスタリング)もあるが~\cite{anderberg:73:a}，本論文では，クラスタの階層的な木構造を構築する方法(階層的クラスタリング)に限る．また，クラスタ木も相互背反な二分木に限る．}，その上でトップダウンに二分木検索を行う．よって，検索時間は平均$O(\log_2N)$に抑えられる．ところが，クラスタ検索に関する従来の研究~\cite{croft:80:a,willett:88:a}では，単純な二分木検索では十分な検索精度が得られないという問題があった．その理由の一つは，クラスタリング時と検索時に異なる距離尺度を用いていたことである．ほとんどの研究では，クラスタリングの手法として単一リンク法，Ward法などを用いていたが，これらの手法は，後の検索で使われる尺度(例えば，TF$\cdot$IDF法や確率)とは直接関係のない尺度でクラスタの二分木を構築していく．これに対し本論文では，クラスタリングの対象文書それぞれを自己検索した際の精度を最大化していく確率的クラスタリングを提案する．よって本クラスタリング法は，検索に適した手法であると言える．実際に，クラスタ検索に本クラスタリング法を用いた場合，単純な二分木検索でも十分な検索精度を得ることができる．検索速度が速い点に加え，クラスタ検索には幾つかの利点がある．クラスタ検索が提案されたそもそもの理由は，「密接に関連した文書群は，同じ検索要求に対する関連性も同等に高い」という{\gtクラスタ仮説}~\cite{van-rijsbergen:74:a}である．通常のキーワード検索では，検索要求と単一文書を厳密なキーワード符合に基づいて比較するため，キーワードの表記の異なりにより関連する文書をとり逃すこともあるが，クラスタ検索では，検索要求を意味的にまとまった文書集合(クラスタ仮説で言うところの「密接に関連した文書群」)と比較するため，この問題も起りにくくなる．クラスタ仮説は，特に検索精度の向上という点において実験的に検証されていない仮説であったが，近年，Hearst等により，キーワード検索で検索した文書集合を絞りこむという状況で，その有効性が実証されている~\cite{hearst:96:a}．本論文では，クラスタ検索が検索対象に含まれているノイズの影響を受けにくいこと(ノイズ頑健性)に注目し，本論文で提案するクラスタ検索が網羅検索に比べ優れていることを実証する．以下，\ref{sec:cluster_based_search}~節では，クラスタ検索について説明する．\ref{sec:hbc}~節では，本論文で提案する確率的クラスタリングについて説明する．\ref{sec:experiment}~節では，本論文で提案したクラスタ検索の有効性を調べるために行なった幾つかの実験について述べる．
\section{クラスタ検索}
\label{sec:cluster_based_search}クラスタ検索に限らず，文書対文書の比較を行うには，まず文書間の距離を定義する必要がある．本論文では，条件付き確率$P(C|d)$を用い，文書$d$から文書集合$C$への方向性のある類似性を定義する．ある文書集合を検索する際は，$d$が入力文書(検索要求)となり，$C$がこれから検索しようとする文書集合の部分集合となる．最も極端な例が網羅検索であり，$C$は文書集合の各文書それ自身になる(図~\ref{fig:search_strategies}~(a)参照)．一方，クラスタ検索では，$C$は何らかの指針により自動/人手で作られたクラスタである．$P(C|d)$を推定する方法は幾つか提案されているが~\cite{robertson:76:a,fuhr:89:a,kwok:90:a}，本論文ではIwayama等の推定法~\cite{iwayama:94:b}を用いることにする．付録~\ref{app:SVMV}に$P(C|d)$の推定法を記す．図~\ref{fig:search_strategies}~(b)が典型的なクラスタ検索を図式化したものである．本論文で扱うクラスタ検索では，文書集合を二分木として自動的に構成し(このステップを{\gtクラスタリング}または{\gt訓練}と呼ぶ)，検索要求を各クラスタ(ノード)と比較することによって，検索要求と類似する文書を指定した数だけとりだす(このステップを{\gt検索}または{\gtテスト}と呼ぶ)．最も単純な検索法は{\gt二分木検索}であり(図~\ref{fig:search_strategies}~(b)参照)，クラスタ木の根からトップダウンに木をたどり，指定した数の文書を含むクラスタを探す．木をたどる際は，各ノードでそれぞれの子ノードについて$P(C|d)$を計算し，どちらに進むかを決定する．二分木検索は，平均$O(\log_2N)$の検索時間しか必要とせず，網羅検索($O(N)$)に比べ高速な検索が可能である．一般に，網羅検索はその検索コストのため大規模な文書集合の検索/ランキングには適用しづらい．事実，現実に運用されている検索システムのほとんどは，ランク付きの検索出力が提供されていないか，提供されていても近似計算~\cite{cutting:97:a}である場合が多い．連想検索のように検索要求が長い場合は，ランク付けの計算に検索要求の全情報を使わないこともある~\cite{frakes:92:a}．検索コストを軽減する効果的な方法は，キーワードから文書への逆インデクス(invertedfile)~\cite{salton:83:a}を使い，検索要求に含まれているキーワードを全く含まない文書を検索対象から除外することである~\cite{perry:83:a}．残った文書集合を網羅検索することで計算量も幾分軽減できる．しかし，逆インデクスの導入は問題の本質的解決ではなく，原理的には依然として$O(N)$の検索コストが必要である．\begin{figure*}\begin{center}\epsfile{file=iwayama1.eps,width=0.9\textwidth}\end{center}\caption{連想検索における文書検索法:網羅検索とクラスタ検索}\label{fig:search_strategies}\vspace{-2mm}\end{figure*}クラスタ木上をトップダウンに二分木検索する方法とは逆に，葉からボトムアップにクラスタ木を検索する方法もある．この検索法は{\gtボトムアップクラスタ検索}と呼ばれ，二分木検索よりも精度的に有効であることが実証されている~\cite{croft:80:a,willett:88:a}．ところが，ボトムアップクラスタ検索では，まず検索の出発点となる葉ノードを決める必要がある．既に何らかの方法で出発点がわかっている場合はよいが，そうでない場合はゼロからこのノードを見つけるため，網羅検索に近い計算量が必要となる．本論文では，その簡素さと高速性のため，トップダウンな二分木検索を使うことにする．また，二分木検索にも，ビーム幅内を並行して検索する，検索の出発ノードを葉に近いノードにするなど様々な拡張が考えられるが，本論文では，断わりのない限り単純な二分木検索に限ることにする．
\section{確率的クラスタリング(HBC)}
\label{sec:hbc}クラスタ検索におけるクラスタリングの目的は，検索を行った際に高い精度を与えるようなクラスタ木を構築することである．不適切なクラスタ木は，検索要求に対して関連の低い文書を出力してしまう．特に，クラスタ木の根に近い部分は，与えられたほとんどの文書集合を含むため漠然性が高く，二分木検索もこの部分での比較で誤りを起しやすい．従来のクラスタ検索において二分木検索の精度が悪かったのは主にこの理由である．以下では，二分木検索でも高い精度を与えるような確率的クラスタリングを提案する．核となるアイデアは，クラスタリング(訓練)にも検索(テスト)にも前節で説明した確率$P(C|d)$を用いることである．まず，クラスタリングで使う尺度として{\gt\bf自己再現率(selfrecall)}を定義する．あるクラスタ$C$に関する自己再現率$SR(C)$を以下のように定義する．\begin{equation}SR(C)=\prod_{d\inC}P(C|d).\end{equation}自己再現率は，クラスタ内の各文書が自分自身を含むクラスタを見つけることができる確率，と解釈することができる．あるクラスタ$C$にとって，$SR(C)$の値が大きいということは，$C$内の各文書を検索入力とした時，それらが$C$を見つける確率が高いということである．文書集合${\calD}$がクラスタの集合$\{C_1,C_2,\ldots\}$に分割されているとすると，その文書集合${\calD}$に対する自己再現率は以下のように定義できる．\begin{equation}SR({\calD})=\prod_{C\in{\calD}}SR(C)=\prod_{C\in{\calD}}\prod_{d\inC}P(C|d).\end{equation}これは，文書集合全体に関する自己検索の精度に関連する．ここまでで，クラスタリングの目的は「文書集合${\calD}$が与えられた時，$SR({\calD})$が最大となる分割を見付けること」と詳細化できる．ただし，通常は山登り法になどにより局所的な最大分割を求めることが多い．例えば，$SR({\calD})$を評価関数として非階層的クラスタリングアルゴリズム~\cite{anderberg:73:a}を適用すると，文書集合を平坦なグループに分割することができる．また，文書集合${\calD}$に対して階層的な二分クラスタ木を構築するには，以下に示す凝集型アルゴリズムを適用すればよい．\begin{enumerate}\item初期クラスタ集合を，${\calD}$内の各文書それ自身のみからなるクラスタの集合とする．\itemマージにより$SR({\calD})$の増分が最大になるようなクラスタのペアを見つけ実際にマージする．\item残りのクラスタの数が1でなければステップ2に戻る．\end{enumerate}以上のアルゴリズムを{\gt\bf階層的ベイズクラスタリング(HBC:HierarchicalBayesianClustering)}と呼ぶ．HBCの詳細については，\cite{iwayama:95:b,iwayama:95:a}を参照されたい．そこでは，HBCと従来のクラスタリング手法との比較実験も行われている．また，付録~\ref{app:hbc}にHBCの形式的な記述を示す．従来のクラスタ検索における実験では，二分木検索に関して否定的な結果がでていた．考えられる理由は，クラスタリング(訓練)と検索(テスト)で異なった尺度(原理)を用いていたことである．従来の実験では，単一リンク法やWard法をクラスタリングの方法として用いていたが，これらの方法は，検索に使う尺度とは直接関係のない尺度を使いクラスタ木を構築している．例えば単一リンク法では，二つのクラスタ間の距離として，それらのクラスタを構成する要素(文書)間の最も近い距離を使う．よって，クラスタ内の他の構成要素の情報は無視されてしまう．また，構成要素(文書)とクラスタ全体との関係が考慮されていない．検索で用いるのは文書とクラスタとの距離である．これらの欠点は，完全リンク法や平均リンク法にもあてはまる．Ward法は，群内誤差の平方和によりクラスタ間の距離を計算するため，上記の欠点はない．しかし，群内誤差の平方和は，検索時に用いる距離尺度とは直接関係がない．それに対しHBCは，文書集合が与えられると，それらを自己検索した時の精度(具体的には自己再現率)を最大化するようなクラスタ木を構築する．つまり，訓練例に対する検索精度の最大化を行っているため，クラスタ検索という用途に直接関連した手法である．次節では，HBCをクラスタ検索に用いた場合の有効性を実験により検証する．なお，単一リンク法やWard法も統計解析という元々の用途には有効な手法である．
\section{実験}
\label{sec:experiment}\subsection{実験方式とデータについて}実験では，連想検索の精度を評価するために{\gtトピック割り付け}を行った．トピック割り付けとは，あらかじめ定義されたトピックの中から1個以上のトピックを文書に割り付けるタスクである．例えば，ある文書に$\{x,y,z\}$という3個のトピックが付いているとする．これらの正解トピックは，通常，専門家によって割り付けられる．そして，自動的な方法により，同じ文書に$\{x,w\}$という2個のトピックが割り付けられたとする．ここで，$x$という1つのトピックのみが3個の正解トピックから再現されたという意味で，{\gt\bf再現率(recall)}は$1/3$となる．また，$x$という1つのトピックのみが，自動的に割り付けられた2個のトピックのなかで正解であったという意味で，{\gt\bf適合率(precision)}は$1/2$となる．自動的なトピック割り付け法としては，$k$-NN法($k$-NearestNeighborclassifiers)~\cite{weiss:90:a,masand:92:a,mouri/97/a}を用いた．$k$-NN法では，ある文書$d$にトピックを割り付ける際，あらかじめ専門家によりトピックが割り付けられている文書集合(訓練データ)の中から$d$に近いものを$k$個検索する．この検索法に，文書連想検索の手法(網羅検索，クラスタ検索)を用い比較した．検索した$k$個の訓練データには既にトピックが付いているため，それぞれのトピックを重み付きで集計し，あるしきい値以上になるトピックを$d$に割り付ける．重みとしては，$d$と各々の訓練データとの距離(条件付き確率)を用いた．ここで，$d$に割り付けられるべき正解トピックが既にわかっているため，再現率/適合率が計算できる．また，自動割り付けにおけるしきい値を変化させることで，再現率/適合率のトレードオフ曲線が描ける．実験データには，「現代用語の基礎知識(92年版)~\cite{gk/92/a}(GK)」と「WallStreetJournal~\cite{liberman:91:a}(WSJ)」を用いた．それぞれの特徴は以下のとおりである．\begin{description}\item[{\gt\bf現代用語の基礎知識(GK)}]\strut\\日本語の辞書データ．$18,476$個の辞書見出しを持ち，それぞれ$149$の小カテゴリいずれかに分類されている．この小カテゴリをトピックとして用いた．つまり，各辞書見出しは単一の正解トピックを持っていることになる．各辞書見出しの説明文は，$13$から$1,938$，平均$287$の文字長を持つ．短い説明文の影響を除くため，説明文中に名詞，未知語(抽出法については後述)を$100$個以下しか含まない辞書見出しを除去した．また，辞書見出しを少数しか持たないカテゴリの影響を除くため，辞書見出しを$20$個以下しか含まないカテゴリを除去した．この結果，残った辞書見出し数は$1,072$，カテゴリ数は$39$となった．\item[{\gt\bfWallStreetJournal(WSJ)}]\strut\\英語の新聞記事データ．'89/7/25から'89/11/2までの$8,907$記事を使った．各記事には，$78$個のトピックの中から複数のトピックが割り付けられている．一つもトピックを持たない記事は取り除いた．記事に割り付けられている平均トピック数は$1.94$個である．\end{description}これら二つのデータセットには，日本語と英語という大きな相違点の他に，以下の特筆すべき相違点がある．\begin{itemize}\itemGKの各文書が単一のトピックしか持たないのに対し，WSJは複数(平均$1.94$個)のトピックを持つ．\itemGKは，文書長，および各トピックが持つ文書数が比較的均一なデータセットであるのに対し，WSJは非均一なデータセットである．GKには各トピックを担当する編集者が存在し，その編集者が担当トピックの辞書見出しを管理しているからである.それに加え，GKでは，短い辞書見出し，辞書見出し数が少ないトピックを上記の方法により強制的に除去している．よって，WSJに比べ，GKはよりノイズの少ないデータセットであると言える．逆の視点から見ると，WSJはより現実データに近いと言える．\end{itemize}実験の前処理として，まず，文書表現として用いるタームを抽出する必要がある．両データセットとも，名詞と未知語をタームとして用いた．タガーとして，GKではJUMAN~\cite{juman/94/a}を，WSJではXeroxPart-of-SpeechTagger~\cite{cutting:93:a}を用いた．WSJに関しては，ispell~\cite{ispell}を用いて語尾処理を行ない，単語の原形のみ用いた．また，トピック割り付けを行うには，データセットを訓練データとテストデータに分割する必要がある．GKは文書数が少ないため，4分割のクロスバリデーションを行った．WSJでは，'89/7/25から'89/9/29までの$5,820$記事を訓練データとして，'89/10/2から'89/11/2までの$3,087$記事をテストデータとして使った．\subsection{従来のクラスタ検索との比較}まず，比較的ノイズの少ないGKを用いて，HBCを用いたクラスタ検索と従来から行われていたクラスタ検索を比較する．従来法としては，クラスタリングにWard法~\cite{anderberg:73:a}を，検索に確率モデルを用いた．よって，両者はクラスタリングの手法のみが異なる．また，比較対象として，網羅検索による実験も行った．網羅検索における文書間の距離尺度には，クラスタ検索と同じ確率モデルを用いた．以上は$k$-NN法によるトピック割り付けであるが，この他にトピック割り付けの代表的な方法(以下，{\gtトピック検索法}と呼ぶ)も比較対象として実験に用いた．トピック検索法では，まず，各トピック毎にそのトピックが割り付けられている文書を集め，トピックを表現する文書集合とする．次に，トピックを割り当てようとする文書と，各トピックを表現している文書集合との間の距離を計算して，距離が近いトピックを文書に割り当てる．距離尺度としては，上記手法と同じ確率モデルを用いた．GKでは，割り当てられるべきトピックが一つであるため，実験に用いた手法でも，上位1位のトピックを割り付け，それが正解となっている割合で精度を測定した．実験結果を図~\ref{fig:gk}に示す．図中，X軸は，$k$-NN法でいうところの$k$，つまり，判定に用いた訓練データ数である．\begin{figure}\begin{center}\epsfile{file=iwayama2.eps,width=0.9\textwidth}\end{center}\vspace{-2mm}\caption{トピック割り付けにおける連想検索の比較(GK)}\label{fig:gk}\vspace{-2mm}\end{figure}図~\ref{fig:gk}から，$k$が極端に小さくない場合，網羅検索の精度が最も良いことがわかる．また，HBCを用いたクラスタ検索も，網羅検索の精度曲線を良く近似している．このことから，検索に要する速度などを考えると，HBCを用いたクラスタ検索は速度/精度の点でバランスの取れた手法であると言える．逆に，Ward法を用いたクラスタ検索が与える精度曲線は，網羅検索の精度曲線とは極端に異なり，特に$k$が$300$以下での精度が非常に悪くなっている．興味深いのは，網羅検索，二つのクラスタ検索共に，$k$が大きくなるにつれトピック検索法が与える精度に収束していく点である．ただし，HBCを用いたクラスタ検索，網羅検索が，$k$を適当に設定するとトピック検索法を上回るのに対し，Ward法を用いたクラスタ検索は，常にトピック検索法を下回る．以上の実験結果から，HBCを用いたクラスタ検索法は，従来のクラスタ検索よりも有効であることが確認できた．次節では，ノイズを含むより実データに近いWSJを用いて，HBCを用いたクラスタ検索と網羅検索との違いを詳しく調べる．\subsection{クラスタ検索のノイズ頑健性}クラスタ検索は，網羅検索と比べると汎化能力という点で優れている．クラスタ検索は訓練データを一般化したクラスタ集合を扱うためである．網羅検索は訓練データそれ自体を扱うため，訓練データ中に存在するノイズの影響を受けやすい．前節のGKによる実験では，この点が確かめられなかったが，これはGKがノイズの少ない均一なデータセットであることによる．本節では，WSJを使って，データセット中に存在するノイズがトピック割り付け(すなわち連想検索)に及ぼす影響を調べる．WSJの各文書には複数のトピックが割り付けられているため，前述の再現率/適合率で評価を行った．トピック割り付け戦略としては以下の3種類を用い比較した．\begin{description}\item[{\gt\bf定数割り付け(k-per-doc)}]\strut\\各テストデータに，均一に$k$個づつトピックを割り当てる．ここでは$k$の値を変化させて再現率/適合率曲線を描く．\item[{\gt\bf確率的割り付け(probabilitythreshold)}]\strut\\各テストデータに割り付けられるトピックには，確率から重みが計算できる．よって，あるしきい値以上の重みを持つトピックを各テストデータに割り付ける．ここでは割り付けのしきい値を変化させて再現率/適合率曲線を描く．\item[{\gt\bf比例配分割り付け(propotionalassignment)~\cite{lewis:92:a}}]\strut\\各トピック毎にテストデータを重みの順にソートしておき，訓練データ中でそのトピックが占める割合に比例した数のテストデータにそのトピックを割り付ける．例えば，訓練データ中で$2\%$の文書に割り付けられているトピックは，比例配分の定数を$0.1$とすると，テストデータ中の$0.2\%$の文書に割り付けられる．比例配分の定数を$5$とすると，テストデータ中の$10\%$の文書に割り付けられる．ここでは，比例配分の定数を変化させて再現率/適合率曲線を描く．\end{description}従来行なわれた実験~\cite{lewis:92:a,iwayama:94:b,nishino/95/a}では，比例配分割り付けの優位性が確認されている．しかし，比例配分割り付けを行うには，あらかじめ十分な数のテストデータがそろっている必要がある．よって，比例配分割り付けは，バッチ的な割り付け処理の局面では有効であるが，オンライン(リアルタイム)で割り付けを行なうような状況に適用することはできない．\begin{figure}\begin{center}\epsfile{file=iwayama3.eps,width=0.9\textwidth}\end{center}\vspace{-1.5mm}\caption{トピック割り付けにおける連想検索の比較(WSJ,定数割り付け)}\label{fig:wsj-kdoc}\vspace{-1.5mm}\end{figure}\begin{figure}\begin{center}\epsfile{file=iwayama4.eps,width=0.9\textwidth}\end{center}\vspace{-1.5mm}\caption{トピック割り付けにおける連想検索の比較(WSJ,確率的割り付け)}\label{fig:wsj-thresh}\vspace{-1.5mm}\end{figure}\begin{figure}\begin{center}\epsfile{file=iwayama5.eps,width=0.9\textwidth}\end{center}\vspace{-1.5mm}\caption{トピック割り付けにおける連想検索の比較(WSJ,比例配分割り付け)}\label{fig:wsj-prop}\vspace{-1.5mm}\end{figure}図~\ref{fig:wsj-kdoc}~$\sim$~\ref{fig:wsj-prop}にそれぞれの割り付け戦略による実験結果を示す．ここでは，HBCによるクラスタ検索と網羅検索を比較している．また，ベースラインとして，トピック検索法による結果も示した．Y軸のbreakevenとは，再現率/適合率トレードオフ曲線において，再現率と適合率が等しくなる点の値である．X軸は，前節と同じく$k$-NN法における$k$の値である．図~\ref{fig:wsj-kdoc}~$\sim$~\ref{fig:wsj-prop}から，まず，他の二つの割り付け戦略に比べ，比例配分割り付けが優れていることがわかる．また，比例配分割り付けでは，網羅検索，クラスタ検索共に，トピック検索と同程度の精度である．更に，両者共に$k$-NN法の$k$による影響をあまり強く受けていない．よって，比例配分割り付けは，検索の手法に対して安定した割り付け戦略であると言える．ところが，前述したように，比例配分割り付けはバッチ処理に限られるという制限がある．定数割り付け，確率的割り付けでは，網羅検索，クラスタ検索共に，ベースラインのトピック検索を大きく上回っている．これは，$k$-NN法の優位性を示している．ここで注目して欲しいのは，$k$-NN法でも，網羅検索の精度曲線が$k$の値に大きく影響を受けている点である．特に，最大breakevenを与える$k$の範囲が非常に狭く，それより$k$の値が大きくなると，breakevenが急激に低下している．これは，訓練データ中に存在するノイズの影響を強く受けていることを意味している．一方，クラスタ検索の精度曲線は$k$に依存せず安定している．つまり，最大breakevenを与える$k$の範囲が広いため，微妙なパラメータ($k$)設定を行う必要がない．これは，クラスタリングという汎化操作により，訓練データ中のノイズの影響があらわれにくくなっていることを意味している．以上から，HBCを用いたクラスタ検索は，網羅検索に比べノイズ頑健性に優れていると言える．
\section{おわりに}
本論文では，文書連想検索のための新しいクラスタ検索法を提案した．提案したクラスタ検索では，与えられた文書集合を自己検索した時の精度を最大化する確率的クラスタリングを用いている．よって，本クラスタリング手法は，従来のクラスタ検索で用いられていたクラスタリング手法に比べると，検索に密接に関連した手法であると言える．「現代用語の基礎知識」「WallStreetJournal」を用いた実験の結果，従来のクラスタ検索に対する本手法の優位性が確認できた．また，網羅検索に対しては，本手法がノイズ頑健性という点で優れていることが確認できた．以下，問題点と今後の課題を挙げる．\begin{description}\item[{\gtクラスタリングの高速化}]\strut\\本論文で提案したクラスタリングに限らず，通常の階層的クラスタリングは，サイズ$N$の文書集合をクラスタリングするのに$O(N^2)$の空間的/時間的計算資源を要する．今後は，特に大規模文書集合の文書連想検索に対処するために，クラスタリングに要する計算量を抑える必要がある．この問題に関して近年，文書表現として用いる単語の次元数を減らす~\cite{schutze:97:a}，クラスタ間の距離を計算せず単語分布を調べる~\cite{tanaka/97/a}などの方法が提案されている．我々は，HBCの近似アルゴリズムによりこの問題を解決することを考えており，既に幾つかの手法を提案し，予備的な実験で有望な結果を得ている~\cite{iwayama/97/a}．今後は，大規模データに適用してその有効性を実証する必要がある．\item[{\gt多重分類}]\strut\\現状のクラスタ木は単純な二分木であるため，同一文書が複数の観点から分類されるといった多重分類を扱えない．この問題については，クラスタ生成時に同一文書が複数のクラスタに分類されることを許す，あるいは検索時に複数の検索パスを探索するなどの手法が考えられる．前者の手法については，既に提案したHBCの近似アルゴリズム~\cite{iwayama/97/a}が有望である．また，後者の手法については，シソーラス構築というタスクで有効な結果を得ている~\cite{tokunaga:97:a}．\item[{\gt動的な文書集合への対応}]\strut\\通常のクラスタリングでは，対象となる文書集合が文書の追加/削除などにより変化すると，一からクラスタリングを実行し直さなければならない．クラスタリングの高速化により再計算の時間が軽減されるとはいえ，大規模な文書集合を変化の都度再クラスタリングするのは非現実的である．この問題については，ほとんど研究がなされていない~\cite{crouch:75:a,can:89:a}．我々は，HBCの近似アルゴリズム~\cite{iwayama/97/a}の一種がインクリメンタルに動作することに着目し，動的な文書集合に対応することを考えている．\end{description}\vspace{-2mm}\bibliographystyle{jnlpbbl}\bibliography{IFIR,jIFIR}\clearpage\begin{biography}\biotitle{略歴}\bioauthor{岩山真}{1987年東京工業大学工学部情報工学科卒業．1992年同大学院理工学研究科博士後期課程修了．同年(株)日立製作所基礎研究所入所．博士(工学)．自然言語処理，情報検索の研究に従事．情報処理学会，人工知能学会，AAAI,ACMSIGIR各会員．}\bioauthor{徳永健伸}{1983年東京工業大学工学部情報工学科卒業．1985年同大学院理工学研究科修士課程修了．同年(株)三菱総合研究所入社．1986年東京工業大学大学院博士課程入学.現在，同大学大学院情報理工学研究科助教授．博士(工学)．自然言語処理，計算言語学，情報検索などの研究に従事．情報処理学会，人工知能学会，計量国語学会，AssociationforComputationalLinguistics,ACMSIGIR各会員．}\bioreceived{受付}\bioaccepted{採録}\end{biography}\vspace{-3mm}\appendix
\section{$P(C|d)$の推定法}
\label{app:SVMV}まず，「存在する全てのターム~\footnote{本研究ではタームとして名詞および未知語を用いた．}から一つを乱数抽出したとき，それが$t$と等しい」という事象を``$T=t$''とする．$P(C|d)$を可能な全ての``$T=t$''で条件付けすると\begin{eqnarray}P(C|d)&=&\sum_{t}P(C|d,T=t)P(t|d)\nonumber\\&\approx&\sum_{T=t}P(C|T=t)P(T=t|d).\label{eq:svmv1}\end{eqnarray}となる．ここでの近似は，$T=t$が与えられたという条件下での$C$と$d$の条件付き独立性の仮定による~\footnote{詳しくは$P(C|d,T=t)=P(C|T=t)$．この式は，もし$T=t$を知れば，$C$に関する情報と$d$に関する情報は独立であることを示している．これは強い仮定であるが，$T=t$が$d$の特殊化された表現だと考えると妥当である．}．ベイズの定理を用いると，(\ref{eq:svmv1})は以下のようになる．\begin{equation}P(C|d)=P(C)\sum_{T=t}\frac{P(T=t|C)P(T=t|d)}{P(T=t)}.\label{eq:svmv2}\end{equation}ここで，各々の要素確率を以下のように推定する．\begin{itemize}\item$P(T=t|C)$:$C$における$t$の相対頻度．\item$P(T=t|d)$:$d$における$t$の相対頻度．\item$P(T=t)$:与えられた文書集合全体における$t$の相対頻度．\item$P(C)$:本論文では定数として扱った．\end{itemize}
\section{階層的ベイズクラスタリング(HierarchicalBayesianClustering)}
\label{app:hbc}\fbox{\begin{minipage}{100mm}\baselineskip=12pt\sfcode`;=3000\def\q{}{\bfInput}:\\\q${\calD}=\{d_{1},d_{2},\ldots,d_{N}\}$:asetof$N$documents;\\\q\\{\bfInitialize}:\\\q$M_0=\{C_1,C_2,\ldots,C_N\}$:asetofclusters;\\\q$C_i=\{d_{i}\}$for$1\lei\leN$\\\qcalculate$SR(C_i)$for$1\lei\leN$\\\qcalculate$SR(C_i\cupC_j)$for$1\lei<j\leN$\\\q\\{\bffor}$k=1${\bfto}$N-1${\bfdo}\\\q$(C_x,C_y)=\arg\max_{C_x,C_y}\frac{SR(C_x\cupC_y)}{SR(C_x)SR(C_y)}$\\\q$M_k=M_{k-1}-\{C_x,C_y\}+\{C_x\cupC_y\}$\\\qcalculate$SR(C_x\cupC_z)$forall$C_z\inM_k$where$z\nex$\\\q\\{\bfFunction}$SR(C)$\\\q{\bfreturn}$\prod_{d\inC}P(C|d)$\end{minipage}}\end{document}