\section{はじめに}
近年，インターネットの普及とともに，個人でWWW(WorldWideWeb)を代表とするネットワーク上の大量の電子データやデータベースが取り扱えるようになり，膨大なテキストデータの中から必要な情報を取り出す機会が増加している．しかし，このようなデータの増加は必要な情報の抽出を困難とする原因となる．この状況を反映し，情報検索，情報フィルタリングや文書クラスタリング等の技術に関する研究開発が盛んに進められている．情報検索システムの中でよく使われている検索モデルに，ベクトル空間モデル\cite{salton}がある．ベクトル空間モデルは，文書と検索要求を多次元空間ベクトルとして表現する方法である．基本的には，文書集合から索引語とするタームを取り出し，タームの頻度などの統計的な情報により，文書ベクトルを表現する．この際，タームに重みを加えることにより，文書全体に対するタームの特徴を目立たせることが可能である．この重みを計算するために，IDF(InverseDocumentFreqency)\cite{chisholm}などの重みづけ方法が数多く提案されている．また，文書と検索要求を比較する類似度の尺度として，内積や余弦(cosine)がよく用いられている．この類似度計算により，類似度の高いものからランクづけを行い，ユーザに表示することができることもベクトル空間モデルの特徴のひとつである．ベクトル空間モデルを用いた検索システムを新聞記事などの大量の文書データに対して適用した場合，文書データ全体に存在するタームの数が非常に多くなるため，文書ベクトルは高い次元を持つようになる．しかし，ひとつの文書データに存在するタームの数は文書データ全体のターム数に比べると非常に少なく，文書ベクトルは要素に0の多い，スパースなベクトルになる．このような文書ベクトルを用いて類似度を計算する際には，検索時間の増加や文書ベクトルを保存するために必要なメモリの量が大きな問題となる．このため，単語の意味や共起関係などの情報を用いたり，ベクトル空間の構造を利用してベクトルの次元を圧縮する研究が盛んに行われている．このようなベクトルの次元圧縮技術には，統計的なパターン認識技術や線形代数を用いた手法などが用いられている\cite{Kolda}\cite{Faloutsos}．この中で，最も代表的な手法として，LSI(LatentSemanticIndexing)がある\cite{Deerwester}\cite{Dumais}．この手法は，文書・単語行列を特異値分解を用いて，低いランクの近似的な行列を求めるものであり，これを用いた検索システムは，次元圧縮を行わない検索モデルと比較して一般的に良い性能を示す．しかし，特異値分解に必要な計算量が大きいために，検索モデルを構築する時間が非常に長いことが問題となっている．上記の問題を解決するベクトル空間モデルの次元圧縮手法に，ランダム・プロジェクション\cite{Arriaga}が存在する．ランダム・プロジェクションは，あらかじめ指定した数のベクトルとの内積を計算することで次元圧縮を行う手法である．これまでに報告されているランダム・プロジェクションを用いた研究には，VLSI(VeryLarge-ScaleIntegratedcircuit)の設計問題への利用\cite{Vempala}や次元圧縮後の行列の特性を理論的に述べたものがある\cite{Papadimitriou}\cite{Arriaga}．しかし，これらの文献では，ランダム・プロジェクションの理論的な特性は示されているものの，情報検索における具体的な実験結果は報告されていない．そのため，情報検索に対するランダム・プロジェクションの有効性に疑問が残る．我々は，ランダム・プロジェクションを用いた情報検索モデルを構築し，評価用テストコレクションであるMEDLINEを利用した検索実験を行った．この検索実験より，情報検索における次元圧縮手法として，ランダム・プロジェクションが有効であることを示す．また，ランダム・プロジェクションを行う際にあらかじめ指定するベクトルとして，文書の内容を表す概念ベクトル\cite{Dhillon}の利用を提案する．概念ベクトルは文書の内容が似ているベクトル集合の重心で，この概念ベクトルを得る際，高次元でスパースな文書データ集合を高速にクラスタリングすることができる球面$k$平均アルゴリズム\cite{Dhillon}を用いる．これにより，文書集合を自動的にクラスタリングできるだけでなく，ランダム・プロジェクションに必要な概念ベクトルも同時に得ることができる．この概念ベクトルをランダム・プロジェクションで用いることにより，任意のベクトルを用いた検索性能と比較して，検索性能が改善されていることを示し，概念ベクトルを利用した次元圧縮の有効性を示す．
\section{ランダム・プロジェクションによるベクトルの次元圧縮}
本節では，ランダム・プロジェクションを用いたベクトル空間モデル\cite{Papadimitriou}\cite{Arriaga}についての概観を述べる．ランダム・プロジェクションは，ひとつの文書データを$n$次元空間上のベクトル${\bfu}$として表現するとき，このベクトルを$k\(k<n)$次元空間に射影する手法である．その際，$k$個の任意の$n$次元ベクトル${\bfr}_1,\cdots,{\bfr}_k$を用意する．用意したこれらのベクトルと$n$次元ベクトル${\bfu}$の内積，\begin{equation}{\bfu}'_1={\bfr}_1\cdot{\bfu},\cdots,{\bfu}'_k={\bfr}_k\cdot{\bfu}\end{equation}をそれぞれ計算する．その結果，$k$次元に圧縮した${\bfu}'_1,\cdots,{\bfu}'_k$を要素とするベクトルが得られる．次元圧縮に必要なベクトル${\bfr}_1,\cdots,{\bfr}_k$を列ベクトルとする$n\timesk$の行列${\bfR}$を用いると，求める$k$次元ベクトルは\begin{equation}{\bfu}'={\bfR}^T{\bfu}\end{equation}となり，ランダム・プロジェクションは行列計算のみの簡単な形で表現することができる．この行列${\bfR}$が任意の正規直交行列のとき，すなわち，行列${\bfR}$の列ベクトルがすべて単位ベクトルで，かつ，相異なる列ベクトルが互いに直交していれば，ランダム・プロジェクションは射影前後におけるベクトル間距離を近似的に保存する特性を持っている．
\section{概念ベクトルを用いたランダム・プロジェクション}
ランダム・プロジェクションに必要な行列${\bfR}$は，これまでの研究では正規分布などの確率分布をなす任意の行列が用いられている\cite{Papadimitriou}\cite{Vempala}\cite{Arriaga}\cite{Kleinberg}\cite{Blum}\cite{Feige}．このような行列を用いて任意の部分空間に射影する場合，次元圧縮を行う前後の任意のベクトル間距離は近似的に保存されることが示されている\cite{Frankl}\cite{Johnson}．しかし，任意の正規直交行列を用いる場合，次元圧縮を行う前後のベクトル間距離を保存する効果は得られたとしても，LSIのように，ベクトルの要素が抽象的な意味を持つ索引語の生成や内容的に関連のある文書をまとめる効果があるとは考えられない．このことから，LSIのような，情報検索に有効な索引語を生成するために，ランダム・プロジェクションの改良が課題となる．このような課題を解決するものとして，ランダム・プロジェクションでベクトルを次元圧縮をした後，さらに特異値分解を行うことにより，LSIの効果を得る手法が提案されている\cite{Papadimitriou}．この手法は，関連文書をまとめる効果を得ると同時に，特異値分解のみを用いた場合に比べ，モデル作成に必要な時間を短縮したものである．しかし，ランダム・プロジェクションと特異値分解は，共にベクトル間距離を保存する効果を持つ手法であるため，特異値分解が内容的に関連のある文書，あるいはタームをまとめるために適用されているとしても，これらの手法を同時に利用することは，検索モデルを構築する時間に関して，効率の良い手法であるとはいえない．さらに，非常に大きい次元数をもつ行列について考えた場合，特異値分解に多くの計算量が必要であることも問題となる．したがって，特異値分解により誤差を最小とする近似行列を得る代わりに，誤差は最小ではないものの，ランダム・プロジェクションのみを用いてLSIの効果を得ることで，より高速に検索モデルが構築できるのではないかと考えられる．これを実現するために，我々は，ランダム・プロジェクションにおける行列${\bfR}$に，文書の内容を表現した概念ベクトルを利用することを提案する．概念ベクトルは，文書ベクトル集合をクラスタリングしてできたクラスタの，各クラスタに属する文書ベクトルの重心を正規化したベクトルとして表される．この概念ベクトルによる次元圧縮は，単にベクトルを近似するだけではなく，クラスタに属するベクトル集合の重心を求めることにより，ターム間で特徴づけられる隠れた関連性やタームの同義性と多義性を捉えることができる．クラスタリングにより得られた各クラスタは互いに異なる概念を持ち，これより得られる概念ベクトルが圧縮した空間の軸となるように用いられる．これにより，次元圧縮された行列は文書と概念ベクトルの類似度を表し，元の空間において内容の近い文書は，圧縮した空間においても近くなる可能性がある．また，類似しているが，異なるタームを使った文書の場合，元の空間では近くないが，圧縮した空間では近くなる可能性があり，検索性能が改善されると考えられる．さらに，多義語により元の空間において近いとされる文書どうしが圧縮した空間では遠くに離れ，誤った検索が取り除かれる可能性も期待できる．このように，これまで単語などが要素であったベクトルが，文書の内容を要素とするようなベクトルに変換され，文書を低い次元で，より検索性能が向上するベクトル表現ができると考えられる．概念ベクトルからなる行列${\bfR}$を求めるために，球面$k$平均アルゴリズム\cite{Dhillon}と呼ばれるクラスタリング手法を用いる．球面$k$平均アルゴリズムは，目的関数が局所的に最大となるまで，高い次元でスパースな文書データ集合をクラスタリングする手法である．球面$k$平均アルゴリズムでは，ユークリッド空間内でベクトル間のなす角の余弦を類似度とし，多次元空間の単位円を分割することによりクラスタリングを行う．これにより，文書ベクトルの集合は指定した数の部分集合に分割され，各クラスタの中心を計算することで，容易に概念ベクトルを作ることができる．さらに，このアルゴリズムは文書ベクトルのスパースさを逆に利用して高速に収束する利点を持ち，得られる概念ベクトルは特異値分解を用いたものに非常に近いことが示されている\cite{Dhillon}．しかし，球面$k$平均アルゴリズムにより得られる概念ベクトルは一般的に直交性を満たしているとは限らないため，概念ベクトルをランダム・プロジェクションに適用するには疑問が生じる．先に述べたように，距離を保存するには正規直交性を満たすベクトルを利用する必要があるが，この概念ベクトルをランダム・プロジェクションに適用する場合，直交性を満たしていないとしても独立であれば，任意の行列においても十分に距離を保存する可能性のあることが示されている\cite{Arriaga}．球面$k$平均アルゴリズムでは，内容的に似通ったベクトルをクラスタとしてまとめるため，原理的には独立した概念ベクトルを生成すると考えられる．このため，直交性に関して，概念ベクトルをランダム・プロジェクションに適用するのは問題ないと考えられる．本節では，まず，球面$k$平均アルゴリズムの概要を述べる前に，クラスタリングにより得られる概念ベクトルについて述べる．\subsection{概念ベクトル}ベクトルの集合をベクトル空間にプロットしたとき，同質のベクトルが多く存在する場合を除いて，いくつかのグループに分かれる．このようなグループはクラスタと呼ばれ，類似した内容をもつベクトルの集合が形成される．概念ベクトルはクラスタに属するベクトルの重心を求めることにより得られ，そのクラスタの内容を表す代表ベクトルである．概念ベクトルを求める例として，正規化された$N$個のベクトル${\bfx}_1,{\bfx}_2,\cdots,{\bfx}_N$を，異なる$s\(s<N)$個のクラスタ$\pi_1,\pi_2,\cdots,\pi_s$にクラスタリングすることを考える．このとき，ひとつのクラスタ$\pi_j$に含まれるベクトル$x_i$の平均である重心${\bfm}_j$は以下のように表される．\begin{equation}{\bfm}_j=\frac{1}{n_j}\sum_{{\bfx}_i\in\pi_j}{\bfx}_i\end{equation}ここで$n_j$はクラスタ$\pi_j$に含まれるベクトルの数を表す．ベクトルの重心は単位長にはなっていないので，そのベクトルの長さで割ることにより概念ベクトル${\bfc}_j$を得る．\begin{equation}{\bfc}_j=\frac{{\bfm}_j}{\|{\bfm}_j\|}\end{equation}\subsection{目的関数}\label{moku}$k$平均アルゴリズムでは，目的関数は一般的に概念ベクトルとクラスタに属するベクトルとの距離の和\begin{equation}\sum_{{\bfx}_i\in\pi_j}\|{\bfm}_j-{\bfx}_i\|\end{equation}を最小にするような概念ベクトルを求める，最小二乗法が用いられる．球面$k$平均アルゴリズムでは，このような最小化問題ではなく，ミクロ経済学の分野における，生産計画の最適化問題で扱われている目的関数を用いている\cite{Kleinberg}．これは，各クラスタ$\pi_{j}(1\leqj\leqs)$の密度を\begin{equation}\sum_{{\bfx}_i\in\pi_j}{\bfx}_i^T{\bfc}_j\end{equation}とし，クラスタの結合密度の和を目的関数としている．\begin{equation}D=\sum_{j=1}^{s}\sum_{{\bfx}_i\in\pi_j}{\bfx}_i^T{\bfc}_j\end{equation}クラスタの密度は，以下のコーシー・シュワルツの不等式より，任意の単位ベクトル${\bfz}$に対して，クラスタ$\pi_j$に含まれるベクトル$x_i$と概念ベクトルとの内積の総和が最大となる．\begin{equation}\sum_{{\bfx}_i\in\pi_j}{\bfx}_i^T{\bfz}\leq\sum_{{\bfx}_i\in\pi_j}{\bfx}_i^T{\bfc}_j\end{equation}また，クラスタの密度は，それに属するベクトル和の距離に等しくなるという特徴を持っている．\begin{equation}\sum_{{\bfx}_i\in\pi_j}{\bfx}_i^T{\bfc}_j=\|\sum_{{\bfx}_i\in\pi_j}{\bfx}_i\|\end{equation}\subsection{球面$k$平均アルゴリズム}\ref{moku}節で示した目的関数$D$を最大にするように，ベクトルの集合を反復法によりクラスタリングする．文書ベクトル${\bfx}_1,{\bfx}_2,\cdots,{\bfx}_N$を$s$個のクラスタ$\pi_1^{\star},\pi_2^{\star},\cdots,\pi_s^{\star}$に分割するためのアルゴリズムを以下に示す．\begin{enumerate}\itemすべての文書ベクトルを$s$個のクラスタに任意に分割する．これらの部分集合を$\{\pi_j^{(0)}\}_{j=1}^{s}$とし，これより求められた概念ベクトルの初期集合を$\{{\bfc}_j^{(0)}\}_{j=1}^{s}$とする．また，$t$を繰り返しの回数とし，初期値は$t=0$である．\item各文書ベクトル${\bfx}_i(1\leqi\leqN$)に対し，余弦が最も大きい，最も文書ベクトルに近い概念ベクトルを見つける．このとき，すべての概念ベクトルは正規化されているので，余弦は文書ベクトル${\bfx}_i$と概念ベクトル${\bfc}_j^{(t)}$の内積を求めることと同値である．これにより，前回の繰り返しで求めた概念ベクトル$\{{\bfc}_j^{(t)}\}_{j=1}^{s}$から，文書ベクトルが新たな部分集合$\{\pi_j^{(t+1)}\}_{j=1}^{s}$に分割される．\begin{equation}\pi_j^{(t+1)}=\{{\bfx}_i:{\bfx}_i^T{\bfc}_j^{(t)}\geq{\bfx}_i^T{\bfc}_l^{(t)}\}\(1\leql\leqN,\1\leqj\leqs)\end{equation}ここで，$\pi_j^{(t+1)}$は概念ベクトル${\bfc}_j^{(t)}$に近いすべての文書ベクトルの集合とする．\item新たに導かれた概念ベクトルの長さを正規化する．\begin{equation}{\bfc}_j^{(t+1)}=\frac{{\bfm}_j^{(t+1)}}{||{\bfm}_j^{(t+1)}||},\\\(1\leqj\leqs)\end{equation}ここで，${\bfm}_j^{(t+1)}$はクラスタ$\pi_j^{(t+1)}$の文書ベクトルの重心を表す．\item目的関数$D^{(t+1)}$の値を求め．前回の繰り返しにおける目的関数の値$D^{(t)}$との差を計算する．このとき，\begin{equation}\|D^{(t)}-D^{(t+1)}\|\leq1\end{equation}を満たす場合，$\pi_j^{\star}=\pi_j^{(t+1)}$，${\bfc}_j^{\star}={\bfc}_j^{(t+1)}$($1\leqj\leqs$)とし，アルゴリズムを終了する．停止基準を超えていない場合は，$t$に1を加え，ステップ2に戻る．ここで，停止基準における目的関数の差は，文書数が約4000で，クラスタの数が8よりも大きい場合，収束した時の目的関数は1000を超えることがこれまでの研究で報告されている\cite{Dhillon}．このため，繰り返しでの1以下の差は無視できるとし，便宜的に1という値を設定した．\end{enumerate}
\section{実験}
本節では，ランダム・プロジェクションを用いた検索モデルを構築し，その評価として，MEDLINEを用いた検索実験について述べる．\subsection{データ}実験で用いたデータは，情報検索システムの評価用テストコレクションであるMEDLINEを利用した．MEDLINEは医学・生物学分野における英文の文献情報データベースで，検索の対象となる文書の件数は1033件で，約1Mbyteの容量を持つテキストデータである．また，MEDLINEには30個の評価用検索要求文と各要求文に対する正解文書が用意されている．MEDLINEに含まれている1033件の文書全体から，前処理として，``a''や``about''などの一般的な439個の英単語を不要語リストに指定して，文書の内容と関係のほとんどない単語は削除した．この後，接辞処理を行い，残った英単語を語幹に変換する処理を行った．この前処理の結果，文書全体に5526個あった単語から，4329個の単語が索引語として抽出され，実験データとして用いた．\subsection{検索実験方法}実験では，MEDLINEから前処理により得られた索引語を要素とする文書ベクトルと検索要求ベクトルを作成し，比較することで検索スコアを計算する．文書ベクトルを作成するとき，ベクトルの要素には局所的，大域的な索引語の分布を考慮するために，索引語の頻度に重み付けした数値が用いられる．数多く提案されている重みづけ手法で，今回の実験では以下の式で定義された対数エントロピー重み\cite{chisholm}を用いた．$L_{ij}$は$j$番目の文書に対する$i$番目の索引語への重み，$G_i$は文書全体に対する$i$番目の索引語への重みを表す．\begin{equation}L_{ij}=\left\{\begin{array}{l}1+\logf_{ij}\\(f_{ij}>0)\\0\\\\\\\\\\\\\(f_{ij}=0)\end{array}\right.\end{equation}\begin{equation}G_i=1+\sum_{j=1}^{n}\frac{\frac{f_{ij}}{F_i}\log\frac{f_{ij}}{F_i}}{\logn}\end{equation}ここで，$n$は全文書数，$f_{ij}$は$j$番目の文書に出現する$i$番目の索引語の頻度，$F_i$は文書集合全体における$i$番目の索引語の頻度を表す．これより，$j$番目の文書から得られる文書ベクトルの$i$番目の要素$d_{ij}$は，\begin{equation}d_{ij}=L_{ij}\timesG_i\end{equation}となる．得られた文書ベクトルから，球面$k$平均アルゴリズムを用い，これらの文書ベクトルより指定された数の概念ベクトルを作成する．作成した概念ベクトルを結合した行列に対し，ランダム・プロジェクションを行い，文書ベクトル，検索要求ベクトルの次元を削減する．次元の削減されたベクトルを用いて，内積の計算を行い，その値を各文書に対する検索スコアとする．これらのスコアのうち，上位50文書を検索結果として出力する．検索システムの評価には，一般的に用いられている正解率(Precision)と再現率(Recall)を用いた\cite{lewis2}\cite{Witten}．\begin{equation}\mbox{Recall}=\frac{システムが出力した正解文書数}{全正解文書数}\end{equation}\begin{equation}\mbox{Precision}=\frac{システムが出力した正解文書数}{システムが出力した文書数}\end{equation}再現率と正解率は，それぞれ個別に用いて，システム評価を行うことができるが，本実験では，一般にランクづけ検索システムの評価に用いられる再現率・正解率曲線を用い，システムの評価を行った．この曲線は，各質問に対しひとつの曲線が作成されるが，本稿の検索システム評価には，全30個の質問に対する各再現率での平均を計算した再現率・正解率曲線を用いた．\vspace*{0.3cm}
\section{実験結果および考察}
\subsection{次元数による比較}本実験では，ランダム・プロジェクションにより，ベクトルの次元を100から900まで圧縮した検索モデルについて，検索実験を行った．その結果，各次元における平均正解率は表\ref{pre_sys}のようになった．平均正解率は，ベクトルの次元が大きくなるにつれて増加し，次元数300において，次元圧縮を行わないベクトル空間モデルよりも良い結果となった．また，次元数が400から500に変化させたときの平均正解率の増加が最も大きく，それ以降は変化の割合が少なくなっている．次元数を大きくすれば，検索に必要な計算量が増加する．このことから，効果的な検索を行うためには，全文書数の約半分に次元圧縮を行う必要があることが分かった．\begin{table}\caption{各次元数における平均正解率}\ecaption{Averageprecisionateachnumberofdimensions}\label{pre_sys}\renewcommand{\arraystretch}{}\centering\begin{tabular}{c|c|c}\hline\hline次元数&ランダム・プロジェクション&平均正解率\\\hline100&あり&0.3982\\200&あり&0.4711\\300&あり&0.5154\\400&あり&0.5231\\500&あり&0.5673\\600&あり&0.5748\\700&あり&0.5822\\800&あり&0.5979\\900&あり&0.6037\\\hline1033&なし&0.4936\\\hline\end{tabular}\end{table}\subsection{検索モデル作成時間}検索モデルを作成する時間，および，一つの検索要求に対し，検索を行うために必要な時間を測定した結果を述べる．検索実験には，UltraSparc(330MHz)のマシンを使用し，ベクトルの次元を500とした結果，表\ref{time}に示すように，ランダム・プロジェクションを用いた場合，モデルを作成する時間は約11分必要であった．LSIの場合，SVDの計算についてはSVDPACKの中で最も高速なLanczos法を利用し，同様にベクトルの次元を500とした結果，モデルを作成する時間は約24分で必要であった．この結果，ランダム・プロジェクションはLSIに比べ，高速に検索モデルを構築することができた．このモデル作成時間においては，メモリサイズの大きさによる，SVDの計算時間に与える影響が考えられる．スワップ領域を用いるほどの大規模なデータについては大きな影響を及ぼし，モデル作成の時間を多く必要とするが，本実験において用いたマシンには640Mバイトのメモリを搭載しているため，MEDLINEコレクションのような規模のデータに対しては，メモリサイズの影響はほとんどないと考えられる．本実験で用いたMEDLINEには収録されているデータは1033件と比較的少ない．このため，文書数を変化させたときの検索モデル構築時間の変化について比較を行った．文書数を増加させるために，MEDLINEと同様なテストコレクションであるCISIを併せた2493記事，さらにCRANFIELDを併せた3893記事について，それぞれの検索モデル作成時間を測定した．その結果，ランダム・プロジェクションとLSIのモデル作成時間は表\ref{model_time}のようになった．これより，文書数が増加に対して球面$k$平均アルゴリズムの1回の反復による計算量が大きくなるのであるが，ランダム・プロジェクションが検索時間に関しても有効であることが分かる．しかし，非常に大規模な文書数に対しては，より1回の反復による計算量が増加するため，反復計算を必要とせずに，球面$k$平均アルゴリズム並の概念ベクトルを得ることが課題となった．\begin{table}\caption{モデル作成時間とひとつの検索要求に対する検索時間}\ecaption{Processingtimeformakingaretrievalmodelandretrievingonequery}\renewcommand{\arraystretch}{}\label{time}\centering\begin{tabular}{c|c|c}\hline\hline手法&モデル作成時間&検索時間\\\hlineランダム・プロジェクション&約2分&4秒\\LSI&約24分&4秒\\\hline\end{tabular}\end{table}\begin{table}\caption{文書数の変化によるモデル作成時間}\ecaption{Processingtimeformakingaretrievalmodelandretrievingonequery}\renewcommand{\arraystretch}{}\label{model_time}\centering\begin{tabular}{l|c|c}\hline\hlineデータ&ランダム・プロジェクション&LSI\\\hlineMEDLINE&約2分&約24分\\MEDLINE+CISI&約14分&約26分\\MEDLINE+CISI+CRANFIELD&約34分&約43分\\\hline\end{tabular}\end{table}\subsection{他の検索モデルとの比較}ランダム・プロジェクションを用いた検索モデルに対して，モデルとしての有効性について評価をする．この評価をするために，次元圧縮をしていない元のベクトル空間モデルと特異値分解を用いたLSIによる検索モデルについての検索実験も同時に行い，性能を比較した．このとき，比較として用いたLSIは，次元数100として次元圧縮した検索モデルを用いている．これらの検索モデルについて，同様に検索実験を行い，すべての検索質問の平均を求めた再現率・正解率曲線を図\ref{re_pre}に示す．図\ref{re_pre}において，横軸は再現率を表し，縦軸は正解率を表す．またグラフの`LSI100'は次元数100のLSI，`VSM'は次元圧縮なしのベクトル空間モデル，`RP500'，`RP700'，`RP900'はランダム・プロジェクションによるそれぞれに示された次元数に圧縮したモデルの実験結果である．その結果，ベクトル空間モデルと比較して，ランダム・プロジェクションを用いた検索モデルは，大幅に性能が改善されていることが分かった．また，次元数100のLSIと比較すると，ランダム・プロジェクションはLSIに比べ少し下がってはいるものの，ほぼ同じ程度に検索精度が改善されていることを示している．このことから，ランダム・プロジェクションが検索モデルとして，LSIと同等の性能を持っていることが分かる．\begin{figure}[tb]\begin{center}\atari(100,82)\end{center}\caption{モデルに対する再現率・正解率曲線}\ecaption{Recall-Precisioncurveforcomparisonbetweenmodels}\label{re_pre}\end{figure}\subsection{概念ベクトルの有効性}ランダム・プロジェクションで次元圧縮に用いられる概念ベクトルが有効であるかを評価するために，他のベクトルを用いて次元圧縮が行われた場合との検索結果の比較を行った．ベクトルには，乱数を用いて，全要素の平均が0，分散が1の正規分布$N(0,1)$となるベクトルと，指定された数の文書ベクトルを任意に抽出して得られた部分集合からなるベクトルを，それぞれ次元圧縮に用いた．この結果，再現率・正解率曲線は図\ref{concept}となった．ここで，`Random'は正規分布となるベクトル，`Subset'は文書ベクトルの部分集合を表し，共にベクトルの次元数は500として，次元圧縮を行ったモデルの実験結果である．また，サンプルに使った文書集合の偏りを考慮するため，グラフに示した実験でのベクトルの他にいくらかのサンプルを用意し，同様の実験を行い，平均的な検索精度を求めた．その結果，正規分布による任意のベクトルにおける平均正解率の平均値は0.38，文書ベクトルの部分集合における平均値は0.47となった．このグラフと平均値から，正規分布の性質を持つ任意のベクトルや文書ベクトルの部分集合を用いて次元圧縮を行った結果とそれぞれ比較すると，概念ベクトルを用いて次元圧縮を行った結果が，明らかに優れていることが分かる．乱数により生成したベクトルを用いた場合，これらのベクトルの各要素には，索引の重要度や索引語間の関連性はほとんど存在しない．このようなベクトルにより次元圧縮を行う場合，ベクトルの要素には文書の内容を表すような潜在的な意味がほとんど含まれていないために，検索性能が下がってしまったと考えられる．文書ベクトルの部分集合を用いた場合は，次元圧縮後，ベクトル中のいくつかの要素が似通った意味を持っているために，検索性能が下がったと考えられる．概念ベクトルは，内容の似通った文書がクラスタリングによりひとつにまとめられ，それらの重心を求めることで，文書の内容を端的に表すことができる．また，クラスタリングを行うことで似通った内容を持つ概念ベクトルが少なくなるため，内容がほとんど変わらない概念ベクトルを重複して生成する可能性が少ない．しかし，文書の部分集合では，内容の重複した文書が複数存在する可能性がある．このため，次元圧縮後のベクトル空間モデルに意味の重なった要素が存在し，検索性能が下がってしまう可能性が大きくなってしまうと考えられる．これらのことにより，情報検索に対してランダム・プロジェクションを用いて次元圧縮を行う場合，内容の近い文書や同義語などのような索引語の特徴を表した概念ベクトルを用いることにより，優れた検索性能が得られることが示された．\begin{figure}[tb]\begin{center}\atari(90,75)\end{center}\caption{概念ベクトルに対する再現率・正解率曲線}\ecaption{Recall-Precisioncurveforcomparisonbetweenvectors}\label{concept}\end{figure}
\section{おわりに}
本論文では，ベクトル空間モデルの次元圧縮手法として，ランダム・プロジェクションを用いた検索モデルを提案した．このモデルの有効性を評価するために，MEDLINEを利用した検索実験を行った．その結果，次元圧縮していない元のベクトル空間モデルと比べ検索精度が改善されていることが分かった．また，LSIと比較しても，検索精度の差は少なく，ランダム・プロジェクションがLSIと同程度の次元圧縮性能を持っていることが分かった．LSIとランダム・プロジェクションのモデル作成，検索に必要な時間を比較すると，LSIは特異値分解を行うこともあり，ランダム・プロジェクションはLSIに比べ約半分の時間で検索を行うことができた．また，MEDLINEよりも大規模な文書集合に対しても，ランダム・プロジェクションが高速に検索モデルが構築することができる．これらのことから，ランダム・プロジェクションはLSIに比べ，高速，かつ有効な次元圧縮手法であることが分かった．また，ランダム・プロジェクションで次元圧縮に必要な行列を得るために，球面$k$平均アルゴリズムで得られる概念ベクトルの利用を提案し，その有効性を検索実験にて評価した．その結果，乱数により生成したベクトルや文書ベクトルの部分集合を用いた場合に比べ，検索精度が優れていた．文書間の内容などの特徴を表した概念ベクトルを用いることで，その概念における索引語の分布を，ベクトルのひとつの要素として表現することができる．これより，ランダム・プロジェクションを用いて検索モデルを構築するとき，概念ベクトルが潜在的な意味を有効にとらえることができることが分かった．今後の研究課題としては，まず，球面$k$平均アルゴリズムは初期段階での分割に非常に大きな影響を及ぼす可能性があるため，初期分割に依存しない有効な概念ベクトルの生成方法を考慮し，より有効な次元圧縮を実現が可能であると考えられる．さらに，より有効な次元圧縮を行うために，評価用データの解答やユーザの評価をフィードバック情報として，概念ベクトルの調節を行った検索モデル\cite{Vogt}\cite{Tai}を構築することが挙げられる．\bibliographystyle{jnlpbbl}\bibliography{sankou}\begin{biography}\biotitle{略歴}\bioauthor{佐々木稔}{1973年生．1996年徳島大学工学部知能情報工学科卒業．1998年徳島大学大学院博士前期課程修了．同年，徳島大学大学院博士後期課程入学，現在に至る．機械学習，情報検索等の研究に従事．情報処理学会会員．}\bioauthor{北研二}{1957年生．1981年早稲田大学理工学部数学科卒業．1983年から1992年まで沖電気工業(株)勤務．この間，1987年から1992年までATR自動翻訳電話研究所に出向．1992年9月から徳島大学工学部勤務．現在，同教授．工学博士．確率・統計的自然言語処理，情報検索等の研究に従事．情報処理学会，電子情報通信学会，日本音響学会，日本言語学会，計量国語学会，ACL各会員．}\bioreceived{受付}\biorevised{再受付}\bioaccepted{採録}\end{biography}\end{document}