潜在意味解析のソースを表示

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

[[1988年]]、アメリカ合衆国でLSAの特許が取得されている<ref>[http://patft.uspto.gov/netacgi/nph-Parser?patentnumber=4839853 US Patent 4,839,853]、Scott Deerwester、Susan Dumais、George Furnas、Richard Harshman、Thomas Landauer、Karen Lochbaum、Lynn Streeter</ref>。[[情報検索]]の分野では、'''潜在的意味索引'''または'''潜在意味インデックス'''（{{lang-en-short|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)}

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

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

:<math>
\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}
</math>

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

:<math>\textbf{t}_i^T = \begin{bmatrix} x_{i,1} & \dots & x_{i,n} \end{bmatrix}</math>

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

:<math>\textbf{d}_j = \begin{bmatrix} x_{1,j} \\ \vdots \\ x_{m,j} \end{bmatrix}</math>

2つの単語ベクトルの[[ドット積]] <math>\textbf{t}_i^T \textbf{t}_p</math> は、その文書群における単語間の[[相関]]を示す。[[行列#和・積|行列積]] <math>X X^T</math> にはそのようなドット積が全て含まれている。その成分 <math>(i,p)</math>（成分 <math>(p,i)</math> と等しい）は、ドット積 <math>\textbf{t}_i^T \textbf{t}_p</math>（<math> = \textbf{t}_p^T \textbf{t}_i</math>）になっている。同様に行列 <math>X^T X</math> は全ての文書ベクトル間のドット積が含まれていて、その単語群における文書間の相関を示す。すなわち、<math>\textbf{d}_j^T \textbf{d}_q = \textbf{d}_q^T \textbf{d}_j</math> である。

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

:<math>
X = U \Sigma V^T
</math>

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

:<math>
\begin{matrix}
X X^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}
</math>

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

:<math>
\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}
</math>

<math>\sigma_1, \dots, \sigma_l</math> という値は特異値と呼ばれ、<math>u_1, \dots, u_l</math> は左特異ベクトル、<math>v_1, \dots, v_l</math> は右特異ベクトルと呼ばれる。<math>U</math> のうち <math>\textbf{t}_i</math> に関与するのは第 <math>i</math>行だけである。その行ベクトルを <math>\hat{\textrm{t}_i}</math> と呼ぶ。同様に、<math>V^T</math> のうち <math>\textbf{d}_j</math> に関与するのは第 <math>j</math> 列だけであり、これを <math>\hat{\textrm{d}_j}</math> と呼ぶ。これらは固有ベクトルではないが、全ての固有ベクトルに依存している。

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

:<math>X_k = U_k \Sigma_k V_k^T</math>

ここで、以下のようなことが可能となる。
* ベクトル <math>\hat{\textbf{d}_j}</math> と <math>\hat{\textbf{d}_q}</math> を（通常[[ベクトル空間モデル|コサイン相関量]]によって）比較することで、文書 <math>j</math> と <math>q</math> の相関の度合いがわかる。これによって、文書群のクラスタリングが得られる。
* ベクトル <math>\hat{\textbf{t}_i}</math> と <math>\hat{\textbf{t}_p}</math> を比較することで、単語 <math>i</math> と <math>p</math> 比較でき、概念空間における単語群のクラスタリングが得られる。
* クエリが与えられたとき、これを短い文書と考え、概念空間内で文書群と比較できる。

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

:<math>\textbf{d}_j = U_k \Sigma_k \hat \textbf{d}_j</math>
:<math>\hat \textbf{d}_j = \Sigma_k^{-1} U_k^T \textbf{d}_j</math>

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

:<math>\textbf{t}_i^T = \hat \textbf{t}_i^T \Sigma_k V_k^T</math>
:<math>\hat \textbf{t}_i^T = \textbf{t}_i^T V_k^{-T} \Sigma_k^{-1} = \textbf{t}_i^T V_k \Sigma_k^{-1}</math>
:<math>\hat \textbf{t}_i = \Sigma_k^{-1}  V_k^T \textbf{t}_i</math>

== 実装 ==
[[特異値分解]] (SVD) は一般に大規模行列手法（例えば[[ランチョス法]]）を使って計算されるが、[[ニューラルネットワーク]]的な手法を使って計算資源を節約することもできる。後者の場合、行列全体をメモリに保持する必要がない<ref>[http://www.dcs.shef.ac.uk/~genevieve/gorrell_webb.pdf Generalized Hebbian Algorithm for Incremental Latent Semantic Analysis] Genevieve Gorrell and Brandyn Webb, 2005</ref>。

高速で逐次的なメモリ使用量の少ない大規模行列SVDアルゴリズムが最近開発されている<ref>[http://www.merl.com/publications/TR2006-059/ Fast Low-Rank Modifications of the Think Singular Value Decomposition] Brand, M., 2006。Gorrell and Webb (2005) は統計的近似だが、Brand (2006) は正確な解が得られるアルゴリズムである。</ref>。

== 限界 ==
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では、[[ポアソン分布]]が観測されたとしても、単語と文書は同時[[正規分布]]モデルを形成すると仮定される（[[エルゴード仮説]]）。最近では[[多項分布]]モデルに基づいた[[確率的潜在意味解析]]が考案され、標準の潜在意味解析よりもよい結果が得られたとの報告がある<ref>[http://www.cs.brown.edu/people/th/papers/Hofmann-UAI99.pdf Probabilistic Latent Semantic Analysis] T. Hofmann, 1999</ref>。

== 関連項目 ==
* [[ベクトル空間モデル]]
* [[検索エンジンスパム|スパムデキシング]]
* [[主成分分析]]

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* {{cite web | url= http://lsa.colorado.edu/ | title=The Latent Semantic Indexing home page|accessdate=2008-06-29}} 
* {{cite journal | url= http://www.merl.com/publications/TR2006-059/ | title=Fast Low-Rank Modifications of the Thin Singular Value Decomposition | author=Matthew Brand | journal=Linear Algebra and Its Applications | volume=415 | pages=20–30 | date=2006年 | doi=10.1016/j.laa.2005.07.021}} -- [http://www.eecs.umich.edu/~wingated/resources.html Brand のアルゴリズムの MATLAB での実装]がある。
* {{cite journal | url= http://lsa.colorado.edu/papers/dp1.LSAintro.pdf | title=Introduction to Latent Semantic Analysis | author=Thomas Landauer, P. W. Foltz, & D. Laham | journal=Discourse Processes | volume=25 | pages=259–284 |date=1998年}}
* {{cite journal | url= http://lsi.research.telcordia.com/lsi/papers/JASIS90.pdf | title=Indexing by Latent Semantic Analysis | author=S. Deerwester, Susan Dumais, G. W. Furnas, T. K. Landauer, R. Harshman | journal=Journal of the American Society for Information Science | volume=41 | issue=6 | pages=391–407 |date=1990年 | doi=10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9}} モデルを提案した最初の論文
* {{cite journal | url= http://citeseer.ist.psu.edu/berry95using.html | title=Using Linear Algebra for Intelligent Information Retrieval | author=Michael Berry, S.T. Dumais, G.W. O'Brien |date=1995年}} [http://lsirwww.epfl.ch/courses/dis/2003ws/papers/ut-cs-94-270.pdf PDF]. 文書検索への応用の解説
* {{cite web | url= http://iv.slis.indiana.edu/sw/lsa.html | title=Latent Semantic Analysis | publisher=InfoVis |accessdate=2008-06-29}}
* {{cite conference | url= http://www.cs.brown.edu/people/th/papers/Hofmann-UAI99.pdf | title=Probabilistic Latent Semantic Analysis | author=T. Hofmann | book-title=Uncertainty in Artificial Intelligence | pages=289-296 | date=1999年}}
* {{cite conference | url= http://www.cs.brown.edu/~th/papers/Hofmann-SIGIR99.pdf | title=Probabilistic Latent Semantic Indexing | author=T. Hofmann | book-title=Proceedings of the 22nd International Conference on Research and Development in Information Retrieval | pages=50-57 | date=1999年}}
* {{cite conference | url= http://www.dcs.shef.ac.uk/~genevieve/gorrell_webb.pdf | title=Generalized Hebbian Algorithm for Latent Semantic Analysis | author=G. Gorrell and B. Webb | book-title=Interspeech |date=2005年}}
* {{cite web | url= http://cran.at.r-project.org/web/packages/lsa/index.html | title=An Open Source LSA Package for R | publisher=CRAN | author=Fridolin Wild | date=2005-11-23 | accessdate=2006-11-20}}
* {{ cite web | url= http://www.welchco.com/02/14/01/60/96/02/2901.HTM | title=A Solution to Plato's Problem: The Latent Semantic Analysis Theory of Acquisition, Induction, and Representation of Knowledge | author=Thomas Landauer | accessdate=2007-07-02}}
* {{cite web | url= http://scgroup.hpclab.ceid.upatras.gr/scgroup/Projects/TMG/ | title=A MATLAB Toolbox for generating term-document matrices from text collections | author=Dimitrios Zeimpekis and E. Gallopoulos | date=2005年9月11日 | accessdate=2006-11-20}}

== 外部リンク ==
* [http://blog.targetwoman.com/latent-semantic-analysis/ Latent Semantic Analysis] - 自然言語処理への応用例
* [http://www.seobook.com/lsi/lsa_definition.htm Latent Semantic Indexing] - 潜在的意味インデクシングの数学的でない解説
*[https://mieruca-ai.com/ai/lsa-lsi-svd/ 潜在意味解析（LSA）～特異値分解から文書検索まで～]　- 潜在的意味解析の解説（日本語）
* [http://knowledgesearch.org/ The Semantic Indexing Project] - 潜在的意味インデクシングのオープンソースプログラム
* [http://senseclusters.sourceforge.net SenseClusters] - 潜在意味解析などのオープンソースパッケージ

{{DEFAULTSORT:せんさいいみかいせき}}
[[Category:検索]]
[[Category:自然言語処理]]

[[fa:آنالیز پنهان مفهومی احتمالی]]