潜在意味解析

潜在意味解析（せんざいいみかいせき、英: Latent Semantic Analysis、略称: LSA）は、ベクトル空間モデルを利用した自然言語処理の技法の1つで、文書群とそこに含まれる用語群について、それらに関連した概念の集合を生成することで、その関係を分析する技術である。潜在的意味解析とも。

1988年、アメリカ合衆国でLSAの特許が取得されている^[1]。情報検索の分野では、潜在的意味索引または潜在意味インデックス（英: Latent Semantic Indexing, LSI）とも呼ばれている。

出現行列

LSA では、各文書における用語の出現を表した文書-単語マトリクスが使われる。これは各行が各単語に対応し、各列が各文書に対応した疎行列である。この行列の各成分の重み付けには tf-idf (term frequency–inverse document frequency) が用いられることが多い。この場合、行列の各成分はその文書でその単語が使われた回数に比例した値であり、文書全体での出現回数が少ない単語はその相対的重要性を反映するために強く重み付けされる。

この行列は標準意味モデルでも一般的だが、必ずしも行列として明確に表現される必要性はなく、行列として数学的に利用するとは限らない。

LSA はこの出現行列を用語と何らかの概念の関係および概念と文書間の関係に変換する。したがって、用語と文書は概念を介して間接的に関連付けられる。

応用

この新たな概念空間は以下のような場面で利用される。

概念空間での文書の比較（データ・クラスタリング、文書分類、など）
翻訳文書群の基本セットを分析した後、異なる言語間で類似の文書を探す（言語間検索）。
用語間の関係を探す（類義性や多義性）。
用語群によるクエリを与えられたとき、それを概念空間で解釈し、一致する文書群を探す（情報検索）。

自然言語処理において、類義性と多義性は根本的な問題である。

類義性は、異なる単語が同じ事象を表す現象である。したがって検索エンジンにおいて、クエリにない類義語を見落として、適切な文書を検索できないことがある。例えば、"doctors" を検索したとき、同義である "physicians" という単語を含む文書を検索できないという可能性がある。
多義性は、同じ単語が複数の意味を持つ現象である。そのため、クエリに指定した単語が多義的であった場合、検索要求者が意図しない意味で使っている不適切な文書が検索されてしまうことがある。例えば、植物学者と計算機科学者が "tree" という単語で検索したいのは、全く異なる文書と思われる。

階数の低減

出現行列を構築後、LSAでは文書-単語マトリクスの行列の階数を低減した近似を行う必要がある場合がある。ただし、近似に伴う精度の低下を考慮に入れなくてはならない。この近似には以下のような理由がある。

元の文書-単語マトリクスがコンピュータのメモリ上に格納するには大きすぎる場合。この場合、階数を低減した行列は「近似」と解釈される。
元の文書-単語マトリクスにノイズが多い場合。その用語の逸話的出現を除去するなど。この場合の近似行列は「ノイズ除去」行列と解釈される。
元の文書-単語マトリクスが理想的な文書-単語マトリクスよりも疎らな場合。すなわち、元の行列には文書で実際に使われている単語のみカウントされているが、各文書の関連する単語に興味がある場合など。つまり、類義性を考慮した行列がほしい場合。

階数の低減の結果、いくつかの次元が統合され、複数の単語に依存するようになる。

{(car), (truck), (flower)} → {(1.3452 * car + 0.2828 * truck), (flower)}

階数低減が類似の意味を持つ用語に対応する次元を統合することで、類義性問題がある程度解消される。また、多義語の成分が複数の類義語に分配されて統合されるなら、多義性の問題もある程度解消される。逆に、他の方向の成分は単に消去されるか、最悪でも意図した意味よりも成分として小さくなる。

導出

行列 $X$ の成分 $(i,j)$ は、単語 $i$ の文書 $j$ における出現（例えば頻度）を表すとする。 $X$ は次のようになる。

{\begin{matrix}&{\textbf {d}}_{j}\\&\downarrow \\{\textbf {t}}_{i}^{T}\rightarrow &{\begin{bmatrix}x_{1,1}&\dots &x_{1,n}\\\vdots &\ddots &\vdots \\x_{m,1}&\dots &x_{m,n}\\\end{bmatrix}}\end{matrix}}

この行列の行は1つの単語に対応したベクトルになっており、各成分が各文書との関係を示している。

{\textbf {t}}_{i}^{T}={\begin{bmatrix}x_{i,1}&\dots &x_{i,n}\end{bmatrix}}

同様に、この行列の列は1つの文書に対応したベクトルになっており、各成分が各単語との関係を示している。

{\textbf {d}}_{j}={\begin{bmatrix}x_{1,j}\\\vdots \\x_{m,j}\end{bmatrix}}

2つの単語ベクトルのドット積 ${\textbf {t}}_{i}^{T}{\textbf {t}}_{p}$ は、その文書群における単語間の相関を示す。行列積 $XX^{T}$ にはそのようなドット積が全て含まれている。その成分 $(i,p)$ （成分 $(p,i)$ と等しい）は、ドット積 ${\textbf {t}}_{i}^{T}{\textbf {t}}_{p}$ （ $={\textbf {t}}_{p}^{T}{\textbf {t}}_{i}$ ）になっている。同様に行列 $X^{T}X$ は全ての文書ベクトル間のドット積が含まれていて、その単語群における文書間の相関を示す。すなわち、 ${\textbf {d}}_{j}^{T}{\textbf {d}}_{q}={\textbf {d}}_{q}^{T}{\textbf {d}}_{j}$ である。

$X$ の分解として、直交行列 $U$ と $V$ 、対角行列 $\Sigma$ が存在すると仮定する。このような分解を特異値分解 (SVD) と呼ぶ。

X=U\Sigma V^{T}

単語の相関と文書の相関を与える行列積は、次のように展開される。

{\begin{matrix}XX^{T}&=&(U\Sigma V^{T})(U\Sigma V^{T})^{T}=(U\Sigma V^{T})(V^{T^{T}}\Sigma ^{T}U^{T})=U\Sigma V^{T}V\Sigma ^{T}U^{T}=U\Sigma \Sigma ^{T}U^{T}\\X^{T}X&=&(U\Sigma V^{T})^{T}(U\Sigma V^{T})=(V^{T^{T}}\Sigma ^{T}U^{T})(U\Sigma V^{T})=V\Sigma U^{T}U\Sigma V^{T}=V\Sigma ^{T}\Sigma V^{T}\end{matrix}}

$\Sigma \Sigma ^{T}$ と $\Sigma ^{T}\Sigma$ は対角行列なので、 $U$ には $XX^{T}$ の固有ベクトルが含まれるはずであり、一方 $V$ は $X^{T}X$ の固有ベクトルのはずである。どちらの行列積にも $\Sigma \Sigma ^{T}$ のゼロでない成分に由来する、または等価的に $\Sigma ^{T}\Sigma$ のゼロでない成分に由来する、同じゼロでない固有値がある。以上から分解は次のようになる。

{\begin{matrix}&X&&&U&&\Sigma &&V^{T}\\&({\textbf {d}}_{j})&&&&&&&({\hat {\textbf {d}}}_{j})\\&\downarrow &&&&&&&\downarrow \\({\textbf {t}}_{i}^{T})\rightarrow &{\begin{bmatrix}x_{1,1}&\dots &x_{1,n}\\\\\vdots &\ddots &\vdots \\\\x_{m,1}&\dots &x_{m,n}\\\end{bmatrix}}&=&({\hat {\textbf {t}}}_{i}^{T})\rightarrow &{\begin{bmatrix}{\begin{bmatrix}\,\\\,\\{\textbf {u}}_{1}\\\,\\\,\end{bmatrix}}\dots {\begin{bmatrix}\,\\\,\\{\textbf {u}}_{l}\\\,\\\,\end{bmatrix}}\end{bmatrix}}&\cdot &{\begin{bmatrix}\sigma _{1}&\dots &0\\\vdots &\ddots &\vdots \\0&\dots &\sigma _{l}\\\end{bmatrix}}&\cdot &{\begin{bmatrix}{\begin{bmatrix}&&{\textbf {v}}_{1}&&\end{bmatrix}}\\\vdots \\{\begin{bmatrix}&&{\textbf {v}}_{l}&&\end{bmatrix}}\end{bmatrix}}\end{matrix}}

$\sigma _{1},\dots ,\sigma _{l}$ という値は特異値と呼ばれ、 $u_{1},\dots ,u_{l}$ は左特異ベクトル、 $v_{1},\dots ,v_{l}$ は右特異ベクトルと呼ばれる。 $U$ のうち ${\textbf {t}}_{i}$ に関与するのは第 $i$ 行だけである。その行ベクトルを ${\hat {{\textrm {t}}_{i}}}$ と呼ぶ。同様に、 $V^{T}$ のうち ${\textbf {d}}_{j}$ に関与するのは第 $j$ 列だけであり、これを ${\hat {{\textrm {d}}_{j}}}$ と呼ぶ。これらは固有ベクトルではないが、全ての固有ベクトルに依存している。

$k$ 個の最大の特異値と $U$ と $V$ からそれに対応する特異ベクトルを選んだとき、階数 $k$ の X への近似を最小誤差で得ることができる（フロベニウス・ノルム）。この近似の驚くべき点は、単に最小誤差であるという点だけでなく、単語ベクトルと文書ベクトルを概念空間に変換するという点である。ベクトル ${\hat {{\textbf {t}}_{i}}}$ には $k$ 個の成分があり、それぞれが単語 $i$ の $k$ 個の概念の1つに対応した出現を表している。同様にベクトル ${\hat {{\textbf {d}}_{j}}}$ は、文書 $j$ と各概念との関係を表している。この近似を次のように記述する。

X_{k}=U_{k}\Sigma _{k}V_{k}^{T}

ここで、以下のようなことが可能となる。

ベクトル ${\hat {{\textbf {d}}_{j}}}$ と ${\hat {{\textbf {d}}_{q}}}$ を（通常コサイン相関量によって）比較することで、文書 $j$ と $q$ の相関の度合いがわかる。これによって、文書群のクラスタリングが得られる。
ベクトル ${\hat {{\textbf {t}}_{i}}}$ と ${\hat {{\textbf {t}}_{p}}}$ を比較することで、単語 $i$ と $p$ 比較でき、概念空間における単語群のクラスタリングが得られる。
クエリが与えられたとき、これを短い文書と考え、概念空間内で文書群と比較できる。

最後の項目を行うには、最初にクエリを概念空間に変換してやる必要がある。したがって直観的に、次のように文書群に対して行ったのと同じように変換をする必要がある。

{\textbf {d}}_{j}=U_{k}\Sigma _{k}{\hat {\textbf {d}}}_{j}

{\hat {\textbf {d}}}_{j}=\Sigma _{k}^{-1}U_{k}^{T}{\textbf {d}}_{j}

このことが意味するのは、クエリベクトル $q$ が与えられたとき、概念空間における文書ベクトルと比較する前に ${\hat {\textbf {q}}}=\Sigma _{k}^{-1}U_{k}^{T}{\textbf {q}}$ という変換をする必要があるということである。同じことは擬似単語ベクトルにも行える。

{\textbf {t}}_{i}^{T}={\hat {\textbf {t}}}_{i}^{T}\Sigma _{k}V_{k}^{T}

{\hat {\textbf {t}}}_{i}^{T}={\textbf {t}}_{i}^{T}V_{k}^{-T}\Sigma _{k}^{-1}={\textbf {t}}_{i}^{T}V_{k}\Sigma _{k}^{-1}

{\hat {\textbf {t}}}_{i}=\Sigma _{k}^{-1}V_{k}^{T}{\textbf {t}}_{i}

実装

特異値分解 (SVD) は一般に大規模行列手法（例えばランチョス法）を使って計算されるが、ニューラルネットワーク的な手法を使って計算資源を節約することもできる。後者の場合、行列全体をメモリに保持する必要がない^[2]。

高速で逐次的なメモリ使用量の少ない大規模行列SVDアルゴリズムが最近開発されている^[3]。

限界

LSA には以下の2つの欠点がある。

結果として得られる次元が解釈が困難な場合がある。例えば、

{(car), (truck), (flower)} → {(1.3452 * car + 0.2828 * truck), (flower)}

となった場合、(1.3452 * car + 0.2828 * truck) は「車」と解釈できる。しかし、以下のような場合

{(car), (bottle), (flower)} → {(1.3452 * car + 0.2828 * bottle), (flower)}

数学的レベルでは問題ないのだが、自然言語レベルでは解釈のしようがない。

LSAの確率モデルは測定データと一致しない。LSAでは、ポアソン分布が観測されたとしても、単語と文書は同時正規分布モデルを形成すると仮定される（エルゴード仮説）。最近では多項分布モデルに基づいた確率的潜在意味解析が考案され、標準の潜在意味解析よりもよい結果が得られたとの報告がある^[4]。

脚注

^ US Patent 4,839,853、Scott Deerwester、Susan Dumais、George Furnas、Richard Harshman、Thomas Landauer、Karen Lochbaum、Lynn Streeter
^ Generalized Hebbian Algorithm for Incremental Latent Semantic Analysis Genevieve Gorrell and Brandyn Webb, 2005
^ Fast Low-Rank Modifications of the Think Singular Value Decomposition Brand, M., 2006。Gorrell and Webb (2005) は統計的近似だが、Brand (2006) は正確な解が得られるアルゴリズムである。
^ Probabilistic Latent Semantic Analysis T. Hofmann, 1999

参考文献

“The Latent Semantic Indexing home page”. 2008年6月29日閲覧。
Matthew Brand (2006年). “Fast Low-Rank Modifications of the Thin Singular Value Decomposition”. Linear Algebra and Its Applications 415: 20–30. doi:10.1016/j.laa.2005.07.021. http://www.merl.com/publications/TR2006-059/. -- Brand のアルゴリズムの MATLAB での実装がある。
Thomas Landauer, P. W. Foltz, & D. Laham (1998年). “Introduction to Latent Semantic Analysis”. Discourse Processes 25: 259–284. http://lsa.colorado.edu/papers/dp1.LSAintro.pdf.
S. Deerwester, Susan Dumais, G. W. Furnas, T. K. Landauer, R. Harshman (1990年). “Indexing by Latent Semantic Analysis”. Journal of the American Society for Information Science 41 (6): 391–407. doi:10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9. http://lsi.research.telcordia.com/lsi/papers/JASIS90.pdf. モデルを提案した最初の論文
Michael Berry, S.T. Dumais, G.W. O'Brien (1995年). Using Linear Algebra for Intelligent Information Retrieval. http://citeseer.ist.psu.edu/berry95using.html. PDF. 文書検索への応用の解説
“Latent Semantic Analysis”. InfoVis. 2008年6月29日閲覧。
T. Hofmann (1999年). "Probabilistic Latent Semantic Analysis" (PDF). Uncertainty in Artificial Intelligence. pp. 289–296.
T. Hofmann (1999年). "Probabilistic Latent Semantic Indexing" (PDF). Proceedings of the 22nd International Conference on Research and Development in Information Retrieval. pp. 50–57.
G. Gorrell and B. Webb (2005年). "Generalized Hebbian Algorithm for Latent Semantic Analysis" (PDF). Interspeech.
Fridolin Wild (2005年11月23日). “An Open Source LSA Package for R”. CRAN. 2006年11月20日閲覧。
Thomas Landauer. “A Solution to Plato's Problem: The Latent Semantic Analysis Theory of Acquisition, Induction, and Representation of Knowledge”. 2007年7月2日閲覧。
Dimitrios Zeimpekis and E. Gallopoulos (2005年9月11日). “A MATLAB Toolbox for generating term-document matrices from text collections”. 2006年11月20日閲覧。