有任何的书写错误、排版错误、概念错误等，希望大家包含指正。

由于字数限制，分成两篇博客。

【自然语言处理】潜在语义分析【上】潜在语义分析

【自然语言处理】潜在语义分析【下】概率潜在语义分析

基础概念

文档（Document）：泛指一般的文本或者文本中的片断（段落、句群或句子），一般指一篇文章，尽管文档可以是多媒体对象，但是以下讨论中我们只认为是文本对象，对文本与文档不加以区别。

项（Term）：文本的内容特征常常用它所含有的基本语言单位（字、词、词组或短语等）来表示，这些基本的语言单位被统称为文本的项，因此文本可以用项集表示为 d(t1,t2,...,ts)d(t_1,t_2,...,t_s)d(t1​,t2​,...,ts​)，其中 tk(1≤k≤s)t_k\space(1\le k\le s)tk​(1≤k≤s) 表示项。

向量空间模型（Vector Space Model，VSM）：由于用于表示文本的项可能存在重复、先后的关系，所以分析起来有一定的难度。为了简化分析，暂时不考虑的顺序，并要求互异（使用不重复的单词表示一段文本），这时可以将文本表示成 mmm 维向量 d(w1,w2,...,wm)d(w_1,w_2,...,w_m)d(w1​,w2​,...,wm​)，mmm 为互异的单词个数，故一般 m≤sm\le sm≤s 。文本的每一维可以表示每个单词的权重（重要程度），也可以表示单词在文本中出现的次数，或者其他含义。

相似度（Similarity）：两个文本 d1d_1d1​ 和 d2d_2d2​ 之间的相关程度（Degree of Relevance）常常用他们之间的相似度来度量。当文本被表示为向量空间模型时，我们可以借助与向量之间的某种距离来表示文本间的相似度，一般用内积或者夹角余弦（标准化内积）度量，这两种度量方法对应的值越大说明相似度越大。

具体情况下，文本信息检索的任务是，用户提出查询时，帮助用户找到与询最相关的文本，以排序的形式展示给用户 。一个最简单的做法是将查询内容看成伪文本，采用单词向量空间模型，将查询内容与文本表示为单词的向量，计算查询向量与文本向量的内积，作为语义相似度，以这个相似度的高低对文本进行排序。我们有理由认为排名靠前的文本更符合用户的需求。

1. 潜在语义分析

1.1. 概述

潜在语义分析（latent semantic analysis，LSA）是一种无监督学习方法，主要用于文本的话题分析，其特点是通过矩阵分解发现文本与单词之间的基于话题的语义关系。潜在语义分析由 Deerwester 等于1990年提出，最初应用于文本信息检索，所以也被称为潜在语义索引（latent semantic indexing。LSI) ，在推荐系统、图像处理、生物信息学等领域也有广泛应用。

文本信息处理中，传统的方法以单词向量表示文本的语义内容，以单词向量空间的度量表示文本之间的语义相似度。潜在语义分析旨在解决这种方法不能准确表示语义的问题，试图从大量的文本数据中发现潜在的话题，以话题向量表示文本的语义内容，以话题向量空间的度量更准确地表示文本之间的语义相似度。这也是话题分析（topic modeling）的基本想法。

潜在语义分析使用的是非概率的话题分析模型。具体地，将文本集合表示为单词-文本矩阵，对单词-文本矩阵进行奇异值分解（singular value decomposition，SVD），从而得到话题向量空间，以及文本在话题向量空间的表示，其特点是分解的矩阵正交。非负矩阵分解（non-negative matrix factorization，NMF）是另 种矩阵的因子分解方法，其特点是分解的矩阵非负。

1.2. 单词向量空间

文本信息处理，比如文本信息检索、文本数据挖掘的一个核心问题是对文本的语义内容进行表示，并进行文本之间的语义相似度计算。最简单的方法是利用向量空间模型（vector space model，VSM），也就是单词向量空间模型（word vector space model）。向量空间模型的基本想法是，给定一个文本，用一个向量表示该文本的“语义”，向量的每一维对应一个单词，其数值为该单词在该文本中出现的频数或权值；基本假设是文本中所有单词的出现情况表示了文本的语义内容；文本集合中的每个文本都表示为一个向量，存在于一个向量空间；向量空间的度量，如内积或标准化内积表示文本之间的“语义相似度”。

下面给出严格定义。给定一个含有 nnn 个文本的集合 D={d1,d2,…,dn}D=\{d_1, d_2,\dots, d_n\}D={d1​,d2​,…,dn​}，以及在所有文本中出现的 mmm 个单词的集合 W={w1,w2,…,wm}W = \{w_1, w_2,\dots , w_m\}W={w1​,w2​,…,wm​} 。将单词在文本中出现的数据用一个单词-文本矩阵（word-document matrix）表示，记作 XXX

X=[x11x12…x1nx21x22…x2n⋮⋮⋮xm1xm2…xmn]X= \left[ \begin{matrix} x_{11} & x_{12} & \dots & x_{1n} \\ x_{21} & x_{22} & \dots & x_{2n} \\ \vdots & \vdots & & \vdots \\ x_{m1} & x_{m2} & \dots & x_{mn} \\ \end{matrix} \right] X=⎣⎢⎢⎢⎡​x11​x21​⋮xm1​​x12​x22​⋮xm2​​………​x1n​x2n​⋮xmn​​⎦⎥⎥⎥⎤​

这是一个 m×nm\times nm×n 矩阵，元素 xijx_{ij}xij​ 表示单词 wiw_iwi​ 在文本 djd_jdj​ 中出现的频数或权值。由于单词的种类很多，而每个文本中出现单词的种类通常较少，所以单词-文本矩阵是一个稀疏矩阵。

权值通常用单词频率-逆文本频率（term frequency-inverse document frequency，TF-IDF）表示，其定义是

TFIDFij=tfijtf⋅jlogdfdfi,i=1,2,…,m;j=1,2,…,n{\rm TFIDF}_{ij}=\frac{{\rm tf}_{ij}}{{\rm tf}_{·j}}{\rm log}\frac{\rm df}{{\rm df}_i},\space\space i=1,2,\dots,m;\space j=1,2,\dots,n TFIDFij​=tf⋅j​tfij​​logdfi​df​,i=1,2,…,m;j=1,2,…,n

式中 tfij{\rm tf}_{ij}tfij​ 是单词 wiw_iwi​ 出现在文本 djd_jdj​ 中的频数，tf⋅j{\rm tf}_{·j}tf⋅j​ 是文本 djd_jdj​ 中出现的所有单词的频数之和，dfi{\rm df}_idfi​ 是含有单词 wiw_iwi​ 的文本数，df{\rm df}df 是文本集合 DDD 的全部文本数。直观上，一个单词在一个文本中出现的频数越高，这个单词在这个文本中的重要度就越高；一个单词在整个文本集合中出现的文本数越少，这个单词就越能表示其所在文本的特点，重要度就越高；一个单词在一个文本的TF-IDF是两种重要度的积，表示综合重要度。

上式的 TFIDFij{\rm TFIDF}_{ij}TFIDFij​ 表示单词 wiw_iwi​ 在文本 djd_jdj​ 中的综合重要程度。

单词向量空间模型直接使用单词-文本矩阵的信息。单词-文本矩阵的第 jjj 列向量 xjx_jxj​ 表示文本 djd_jdj​

xj=[x1jx2j⋮xmj],j=1,2,…,nx_j= \left[ \begin{matrix} x_{1j} \\ x_{2j} \\ \vdots \\ x_{mj} \\ \end{matrix} \right],\space\space j=1,2,\dots, n xj​=⎣⎢⎢⎢⎡​x1j​x2j​⋮xmj​​⎦⎥⎥⎥⎤​,j=1,2,…,n

其中 xjx_jxj​ 是单词 wiw_iwi​ 在文本 djd_jdj​ 的权值，i=1,2,…,mi= 1,2,\dots ,mi=1,2,…,m，权值越大，该单词在该文本中的重要度就越高。这时矩阵 XXX 也可以写作 X=[x1x2…xn]X=\left[x_1\space\space x_2\space\space \dots\space\space x_n\right]X=[x1​x2​…xn​]。

两个单词向量的内积或标准化内积（余弦）表示对应的文本之间的语义相似度。因此，文本 did_idi​ 与 djd_jdj​ 之间的相似度为

xi⋅xj,xi⋅xj∣∣xi∣∣∣∣xj∣∣x_i·x_j,\space\space \frac{x_i·x_j}{||x_i||\space|| x_j||} xi​⋅xj​,∣∣xi​∣∣∣∣xj​∣∣xi​⋅xj​​

直观上，在两个文本中共同出现的单词越多，其语义内容就越相近，这时，对应的单词向量同不为零的维度就越多，内积就越大（单词向量元素的值都是非负的），表示两个文本在语义内容上越相似。这个模型虽然简单，却能很好地表示文本之间的语义相似度，与人们对语义相似度的判断接近，在一定程度上能够满足应用的需求，至今仍在文本信息检索、文本数据挖掘等领域被广泛使用，可以认为是文本信息处理的一个基本原理。注意，两个文本的语义相似度并不是由一两个单词是否在两个文本中出现决定，而是由所有的单词在两个文本中共同出现的“模式”决定。

单词向量空间模型的优点是模型简单，计算效率高。因为单词向量通常是稀疏的，两个向量的内积计算只需要在其同不为零的维度上进行即可，需要的计算很少，可以高效地完成。单词向量空间模型也有一定的局限性，体现在内积相似度未必能够准确表达两个文本的语义相似度上。因为自然语言的单词具有一词多义性（polysemy）及多词一义性（synonymy），即同一个单词可以表示多个语义，多个单词可以表示同个语义，所以基于单词向量的相似度计算存在不精确的问题。

图 1单词-文本矩阵例

图 111 给出一个例子。单词-文本矩阵，每一行表示一个单词，每一列表示一个文本，矩阵的每一个元素表示单词在文本中出现的频数，频数 000 省略。单词向量空间模型中，文本 d1d_1d1​ 与 d2d_2d2​ 相似度并不高，尽管两个文本的内容相似，这是因为同义词“airplane”与“aircraft”被当作了两个独立的单词，单词向量空间模型不考虑单词的同义性，在此情况下无法进行准确的相似度计算。另一方面，文本 d3d_3d3​ 与 d4d_4d4​ 有一定的相似度，尽管两个文本的内容并不相似，这是因为单词“apple”具有多义，可以表示“apple computer”和“fruit”，单词向量空间模型不考虑单词的多义性，在此情况下也无法进行准确的相似度计算。

1.3. 话题向量空间

两个文本的语义相似度可以体现在两者的话题相似度上。所谓话题（topic），并没有严格的定义，就是指文本所讨论的内容或主题。一个文本一般含有若干个话题。如果两个文本的话题相似，那么两者的语义应该也相似。话题可以由若干个语义相关的单词表示，同义词（如“airplane”与“aircraft”）可以表示同一个话题，而多义词（如“apple”）可以表示不同的话题。这样，基于话题的模型就可以解决上述基于单词的模型存在的问题。

可以设想定义一种话题向量空间模型（topic vector space model）。给定一个文本，用话题空间的一个向量表示该文本，该向量的每一分量对应一个话题，其数值为该话题在该文本中出现的权值。用两个向量的内积或标准化内积表示对应的两个文本的语义相似度。注意话题的个数通常远远小于单词的个数，话题向量空间模型更加抽象。事实上潜在语义分析正是构建话题向量空间的方法（即话题分析的方法），单词向量空间模型与话题向量空间模型可以互为补充，现实中，两者可以同时使用。

1.3.1. 话题向量空间

假设所有文本共含有 kkk 个话题。假设每个话题由一个定义在单词集合 WWW 上的 mmm 维向量表示，称为话题向量，即

tl=[t1lt2l⋮tml],l=1,2,…,kt_{l}=\left[\begin{matrix} t_{1l} \\ t_{2l} \\ \vdots \\ t_{ml} \end{matrix} \right],\space\space l=1,2,\dots,k tl​=⎣⎢⎢⎢⎡​t1l​t2l​⋮tml​​⎦⎥⎥⎥⎤​,l=1,2,…,k

其中 tilt_{il}til​ 是单词 wiw_iwi​ 在话题 tlt_ltl​ 的权值，i=1,2,…,mi = 1,2,\dots ,mi=1,2,…,m，权值越大，该单词在该话题中的重要度就越高。这 kkk 个话题向量 t1,t2,…,tkt_1,t_2,\dots,t_kt1​,t2​,…,tk​ 张成一个话题向量空间（topic vector space），维数为 kkk。注意话题向量空间 TTT 是单词向量空间 XXX 的一个子空间。

话题向量空间 TTT 也可以表示为一个矩阵，称为单词-话题矩阵（word-topic matrix），记作

T=[t11t12…t1kt21t22…t2k⋮⋮⋮tm1tm2…tmk]T= \left[ \begin{matrix} t_{11} & t_{12} & \dots & t_{1k} \\ t_{21} & t_{22} & \dots & t_{2k} \\ \vdots & \vdots & & \vdots \\ t_{m1} & t_{m2} & \dots & t_{mk} \\ \end{matrix} \right] T=⎣⎢⎢⎢⎡​t11​t21​⋮tm1​​t12​t22​⋮tm2​​………​t1k​t2k​⋮tmk​​⎦⎥⎥⎥⎤​

矩阵 TTT 也可以写作 T=[t1t2…tk]T=\left[\begin{matrix} t_1 & t_2 &\dots & t_k\end{matrix}\right]T=[t1​​t2​​…​tk​​]。

1.3.2. 文本在话题向量空间的表示

现在考虑文本集合 DDD 的文本 djd_jdj​，在单词向量空间中由一个向量 xjx_jxj​ 表示，将 xjx_jxj​ 投影到话题向量空间 TTT 中，得到在话题向量空间的一个向量 yjy_jyj​，yjy_jyj​ 是一个 kkk 维向量，其表达式为

yj=[y1jy2j⋮ykj],j=1,2,…,ny_{j}=\left[\begin{matrix} y_{1j} \\ y_{2j} \\ \vdots \\ y_{kj} \\ \end{matrix} \right],\space\space j=1,2,\dots,n yj​=⎣⎢⎢⎢⎡​y1j​y2j​⋮ykj​​⎦⎥⎥⎥⎤​,j=1,2,…,n

其中 yljy_{lj}ylj​ 是文本 djd_jdj​ 在话题 tlt_ltl​ 的权值，l=1,2…,kl = 1,2\dots,kl=1,2…,k，权值越大，该话题在该文本中的重要度就越高。

矩阵 YYY 表示话题在文本中出现的情况，称为话题-文本矩阵（topic-document matrix），记作

Y=[y11y12…y1ny21y22…y2n⋮⋮⋮yk1yk2…ykn]Y= \left[ \begin{matrix} y_{11} & y_{12} & \dots & y_{1n} \\ y_{21} & y_{22} & \dots & y_{2n} \\ \vdots & \vdots & & \vdots \\ y_{k1} & y_{k2} & \dots & y_{kn} \\ \end{matrix} \right] Y=⎣⎢⎢⎢⎡​y11​y21​⋮yk1​​y12​y22​⋮yk2​​………​y1n​y2n​⋮ykn​​⎦⎥⎥⎥⎤​

矩阵 YYY 也可以写作 Y=[y1y2…yn]Y =\left[\begin{matrix} y_1 & y_2& \dots & y_n\end{matrix}\right]Y=[y1​​y2​​…​yn​​]。

1.3.3. 从单词向量空间到话题向量空间的线性变换

这样一来，在单词向量空间的文本向量 xjx_jxj​ 可以通过它在话题空间中的向量 yjy_jyj​ 近似表示，具体地由 kkk 个话题向量以 yjy_jyj​ 为系数的线性组合近似表示。

xj≈y1jt1+y2jt2+⋯+ykjtk,j=1,2,…,nx_j≈y_{1j}t_1+y_{2j}t_2+\dots+y_{kj}t_k,\space\space j=1,2,\dots, n xj​≈y1j​t1​+y2j​t2​+⋯+ykj​tk​,j=1,2,…,n

所以，单词-文本矩阵 XXX 可以近似的表示为单词-话题矩阵 TTT 与话题-文本矩阵 YYY 的乘积形式。这就是潜在语义分析。

X≈TYX≈TY X≈TY

直观上潜在语义分析是将文本在单词向量空间的表示通过线性变换转换为在话题向量空间中的表示，如图 222 所示。这个线性变换由矩阵因子分解式 X≈TYX≈TYX≈TY 的形式体现。图 333 示意性的表示实现潜在语义分析的矩阵因子分解。

图 2将文本在单词向量空间的表示通过线性变换转换为话题空间的表示

图 3潜在语义分析通过矩阵因子分解实现，单词-文本矩阵 X 可以近似的表示为单词-话题矩阵 T 与话题-文本矩阵 Y 的乘积形式

在原始的单词向量空间中，两个文本 did_idi​ 与 djd_jdj​ 的相似度可以由对应的向量的内积表示，即 xi⋅xjx_i·x_jxi​⋅xj​ 。经过潜在语义分析之后，在话题向量空间中，两个文本 did_idi​ 与 djd_jdj​ 的相似度可以由对应的向量的内积即 yi⋅yjy_i·y_jyi​⋅yj​ 表示。

要进行潜在语义分析，需要同时决定两部分的内容，一是话题向量空间 TTT，二是文本在话题空间的表示 YYY，使两者的乘积是原始矩阵数据的近似，而这一结果完全从话题-文本矩阵的信息中获得。

1.4. 潜在语义分析算法

潜在语义分析利用矩阵奇异值分解，具体地，对单词-文本矩阵进行奇异值分解，将其左矩阵作为话题向量空间，将其对角矩阵与右矩阵的乘积作为文本在话题向量空间的表示。

潜在语义分析根据确定的话题个数对单词-文本矩阵进行截断奇异值分解

X≈UkΣkVkT=[u1u2…uk][σ10000σ20000⋱0000σk][v1Tv2T⋮vkT](1)X≈U_k\Sigma_kV_k^T=\left[\begin{matrix}u_1& u_2 & \dots & u_k\end{matrix}\right] \left[ \begin{matrix} \sigma_1 & 0 & 0 & 0 \\ 0 & \sigma_2 & 0 & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & \sigma_k \end{matrix}\right] \left[\begin{matrix}v_1^T\\ v_2^T \\ \vdots\\ v_k^T\end{matrix}\right]\tag{1} X≈Uk​Σk​VkT​=[u1​​u2​​…​uk​​]⎣⎢⎢⎡​σ1​000​0σ2​00​00⋱0​000σk​​⎦⎥⎥⎤​⎣⎢⎢⎢⎡​v1T​v2T​⋮vkT​​⎦⎥⎥⎥⎤​(1)

式中 k≤n≤mk ≤ n ≤mk≤n≤m，UkU_kUk​ 是 m×km \times km×k 矩阵，它的列由 XXX 的前 kkk 个互相正交的左奇异向量组成，Σk\Sigma_kΣk​ 是 kkk 阶对角方阵，对角元素为前 kkk 个最大奇异值，VkV_kVk​ 是 n×kn \times kn×k 矩阵，它的列由 XXX 的前 kkk 个互相正交的右奇异向量组成。

在式 (1)(1)(1) 中，矩阵 UkU_kUk​ 的每一个列向量 u1u_1u1​，u2u_2u2​，…\dots…，uku_kuk​ 表示一个话题，称为话题向量。由这 kkk 个话题向量张成一个子空间

Uk=[u1u2…uk]U_k=\left[\begin{matrix}u_1& u_2 & \dots & u_k\end{matrix}\right] Uk​=[u1​​u2​​…​uk​​]

称为话题向量空间。

有了话题向量空间，接着考虑文本在话题空间的表示。将式 (1)(1)(1) 写作

X=[x1x2…xk]≈UkΣkVkT=[u1u2…uk][σ10000σ20000⋱0000σk][v11v21…vn1v12v22…vn2⋮⋮⋮v1kv2k…vnk]=[u1u2…uk][σ1v11σ1v21…σ1vn1σ2v12σ2v22…σ2vn2⋮⋮⋮σkv1kσkv2k…σkvnk](2)\begin{aligned} X&=\left[\begin{matrix}x_1& x_2 & \dots & x_k\end{matrix}\right]≈U_k\Sigma_kV_k^T \\ &=\left[\begin{matrix}u_1& u_2 & \dots & u_k\end{matrix}\right] \left[ \begin{matrix} \sigma_1 & 0 & 0 & 0 \\ 0 & \sigma_2 & 0 & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & \sigma_k \end{matrix}\right] \left[ \begin{matrix} v_{11} & v_{21} & \dots & v_{n1} \\ v_{12} & v_{22} & \dots & v_{n2} \\ \vdots & \vdots & & \vdots \\ v_{1k} & v_{2k} & \dots & v_{nk} \\ \end{matrix} \right]\\ &=\left[\begin{matrix}u_1& u_2 & \dots & u_k\end{matrix}\right] \left[ \begin{matrix} \sigma_1v_{11} & \sigma_1v_{21} & \dots & \sigma_1v_{n1} \\ \sigma_2v_{12} & \sigma_2v_{22} & \dots & \sigma_2v_{n2} \\ \vdots & \vdots & & \vdots \\ \sigma_kv_{1k} & \sigma_kv_{2k} & \dots & \sigma_kv_{nk} \end{matrix}\right] \tag{2} \end{aligned} X​=[x1​​x2​​…​xk​​]≈Uk​Σk​VkT​=[u1​​u2​​…​uk​​]⎣⎢⎢⎡​σ1​000​0σ2​00​00⋱0​000σk​​⎦⎥⎥⎤​⎣⎢⎢⎢⎡​v11​v12​⋮v1k​​v21​v22​⋮v2k​​………​vn1​vn2​⋮vnk​​⎦⎥⎥⎥⎤​=[u1​​u2​​…​uk​​]⎣⎢⎢⎢⎡​σ1​v11​σ2​v12​⋮σk​v1k​​σ1​v21​σ2​v22​⋮σk​v2k​​………​σ1​vn1​σ2​vn2​⋮σk​vnk​​⎦⎥⎥⎥⎤​​(2)

其中

ul=[u1lu2l⋮uml],l=1,2,…,ku_l=\left[\begin{matrix} u_{1l} \\ u_{2l} \\ \vdots \\ u_{ml} \\ \end{matrix} \right],\space\space l=1,2,\dots,k ul​=⎣⎢⎢⎢⎡​u1l​u2l​⋮uml​​⎦⎥⎥⎥⎤​,l=1,2,…,k

由式 (2)(2)(2) 知，矩阵 XXX 的第 jjj 列向量 xjx_jxj​ 满足

xj≈Uk(ΣkVkT)j=[u1u2…uk][σ1vj1σ2vj2⋮σkvjk]=∑l=1kσlvjlul,j=1,2,…,n(3)\begin{aligned} x_j&≈U_k(\Sigma_kV_k^T)_j\\ &=\left[\begin{matrix}u_1& u_2 & \dots & u_k\end{matrix}\right] \left[\begin{matrix} \sigma_1v_{j1} \\ \sigma_2v_{j2} \\ \vdots \\ \sigma_kv_{jk} \\ \end{matrix} \right] \\ &=\sum_{l=1}^k \sigma_lv_{jl}u_l,\space\space j=1,2,\dots,n \tag{3} \end{aligned} xj​​≈Uk​(Σk​VkT​)j​=[u1​​u2​​…​uk​​]⎣⎢⎢⎢⎡​σ1​vj1​σ2​vj2​⋮σk​vjk​​⎦⎥⎥⎥⎤​=l=1∑k​σl​vjl​ul​,j=1,2,…,n​(3)

式中 (ΣkVkT)j(\Sigma_kV_k^T)_j(Σk​VkT​)j​ 是矩阵 (ΣkVkT)(\Sigma_kV_k^T)(Σk​VkT​) 的第 jjj 列向量。式 (3)(3)(3) 是文本 djd_jdj​ 的近似表达式，由 kkk 个话题向量 ulu_lul​ 的线性组合构成。矩阵 (ΣkVkT)(\Sigma_kV_k^T)(Σk​VkT​) 的每一个列向量

[σ1v11σ2v12⋮σkv1k],[σ1v21σ2v22⋮σkv2k],…,[σ1vn1σ2vn2⋮σkvnk]\left[\begin{matrix} \sigma_1v_{11} \\ \sigma_2v_{12} \\ \vdots \\ \sigma_kv_{1k} \\ \end{matrix} \right] ,\space\left[\begin{matrix} \sigma_1v_{21} \\ \sigma_2v_{22} \\ \vdots \\ \sigma_kv_{2k} \\ \end{matrix} \right] ,\space\dots,\space\left[\begin{matrix} \sigma_1v_{n1} \\ \sigma_2v_{n2} \\ \vdots \\ \sigma_kv_{nk} \\ \end{matrix} \right] ⎣⎢⎢⎢⎡​σ1​v11​σ2​v12​⋮σk​v1k​​⎦⎥⎥⎥⎤​,⎣⎢⎢⎢⎡​σ1​v21​σ2​v22​⋮σk​v2k​​⎦⎥⎥⎥⎤​,…,⎣⎢⎢⎢⎡​σ1​vn1​σ2​vn2​⋮σk​vnk​​⎦⎥⎥⎥⎤​

是一个文本在话题向量空间的表示。

综上，可以通过对单词-文本矩阵的奇异值分解进行潜在语义分析

X≈UkΣkVkT=Uk(ΣkVkT)X≈U_k\Sigma_kV_k^T=U_k(\Sigma_kV_k^T) X≈Uk​Σk​VkT​=Uk​(Σk​VkT​)

得到话题空间 UkU_kUk​，以及文本在话题空间的表示 (ΣkVkT)(\Sigma_kV_k^T)(Σk​VkT​) 。

下面介绍潜在语义分析的一个例子。假设有 999 个文本，111111 个单词，单词-文本矩阵 XXX 为 11×911\times911×9 矩阵，矩阵的元素是单词在文本中出现的频数，表示如下：

进行潜在语义分析。实施对矩阵的截断奇异值分解，假设话题的个数是 333，矩阵的截断奇异值分解结果为

可以看出，左矩阵 U3U_3U3​ 有 333 个列向量（左奇异向量）。第 111 列向量 u1u_1u1​ 的值均为正，第 222 列向量 u2u_2u2​ 和第 333 列向量 u3u_3u3​ 的值有正有负。中间的对角矩阵 Σ3\Sigma_3Σ3​ 的元素是 333 个由大到小的奇异值（正值）。右矩阵是 V3TV_3^TV3T​，其转置矩阵 V3V_3V3​ 也有 333 个列向量（右奇异向量）。第 111 列向量 v1v_1v1​ 的值也都为正，第 222 列向量 v2v_2v2​ 和第 333 列向量 v3v_3v3​ 的值有正有负。

现在，将 Σ3\Sigma_3Σ3​ 与 V3TV_3^TV3T​ 相乘，整体变成两个矩阵乘积的形式

X≈U3(Σ3V3T)=[0.15−0.270.040.240.38−0.090.13−0.170.070.180.190.450.220.09−0.460.74−0.210.210.18−0.30−0.280.180.190.450.360.59−0.340.25−0.42−0.280.12−0.140.23][1.370.861.331.020.861.921.091.131.72−0.84−0.39−1.20−0.63−0.371.440.18−0.811.15−0.820.28−0.320.500.44−1.021.100.000.68]\begin{aligned} X&≈U_3(\Sigma_3V_3^T) \\ &=\left[\begin{array}{r} 0.15 & -0.27 & 0.04 \\ 0.24 & 0.38 & -0.09 \\ 0.13 & -0.17 & 0.07 \\ 0.18 & 0.19 & 0.45 \\ 0.22 & 0.09 & -0.46 \\ 0.74 & -0.21 & 0.21 \\ 0.18 & -0.30 & -0.28 \\ 0.18 & 0.19 & 0.45 \\ 0.36 & 0.59 & -0.34 \\ 0.25 & -0.42 & -0.28 \\ 0.12 & -0.14 & 0.23\\ \end{array}\right] \left[\begin{array}{r} 1.37 & 0.86 & 1.33 & 1.02 & 0.86 & 1.92 & 1.09 & 1.13 & 1.72 \\ -0.84 & -0.39 & -1.20 & -0.63 & -0.37 & 1.44 & 0.18 & -0.81 & 1.15 \\ -0.82 & 0.28 & -0.32 & 0.50 & 0.44 & -1.02 & 1.10& 0.00 & 0.68 \end{array}\right] \end{aligned} X​≈U3​(Σ3​V3T​)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​0.150.240.130.180.220.740.180.180.360.250.12​−0.270.38−0.170.190.09−0.21−0.300.190.59−0.42−0.14​0.04−0.090.070.45−0.460.21−0.280.45−0.34−0.280.23​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​⎣⎡​1.37−0.84−0.82​0.86−0.390.28​1.33−1.20−0.32​1.02−0.630.50​0.86−0.370.44​1.921.44−1.02​1.090.181.10​1.13−0.810.00​1.721.150.68​⎦⎤​​

矩阵 U3U_3U3​ 有 333 个列向量，表示 333 个话题，矩阵 U3U_3U3​ 表示话题向量空间。矩阵 (Σ3V3T)(\Sigma_3V_3^T)(Σ3​V3T​) 有 999 个列向量，表示 999 个文本，矩阵 (Σ3V3T)(\Sigma_3V_3^T)(Σ3​V3T​) 是文本集合在话题向量空间的表示。

1.5. 非负矩阵分解算法

非负矩阵分解也可以用于话题分析。对单词-文本矩阵进行非负矩阵分解，将其左矩阵作为话题向量空间，将其右矩阵作为文本在话题向量空间的表示。注意通常单词-文本矩阵是非负的。

若一个矩阵的所有元素非负，则称该矩阵为非负矩阵，若 XXX 是非负矩阵，则记作 X≥0X ≥0X≥0。

给定一个非负矩阵 X≥0X ≥0X≥0，找到两个非负矩阵 W≥0W≥0W≥0 和 H≥0H≥0H≥0 ，使得

X≈WH(4)X≈ WH\tag{4} X≈WH(4)

即将非负矩阵 XXX 分解为两个非负矩阵 WWW 和 HHH 的乘积的形式，称为非负矩阵分解。因为 WHWHWH 与 XXX 完全相等很难实现，所以只要求 WHWHWH 与 XXX 近似相等。

假设非负矩阵 XXX 是 m×nm\times nm×n 矩阵，非负矩阵 WWW 和 HHH 分别为 m×km\times km×k 矩阵和 k×nk\times nk×n 矩阵。假设 k<min⁡(m,n)k< \min(m,n)k<min(m,n) ，即 WWW 和 HHH 小于原矩阵 XXX ，所以非负矩阵分解是对原数据的压缩。

由式 (4)(4)(4) 知，矩阵 XXX 的第 jjj 列向量 xjx_jxj​ 满足

xj≈Whj=[w1w2…wk][h1jh2j⋮hkj]=∑l=1khljwl,j=1,2,…,n\begin{aligned} x_j&≈ Wh_j \\ &=\left[\begin{matrix}w_1& w_2 & \dots & w_k\end{matrix}\right]\left[\begin{matrix}h_{1j} \\ h_{2j} \\ \vdots \\ h_{kj}\end{matrix}\right] \\ &=\sum_{l=1}^kh_{lj}w_l,\space\space j=1,2,\dots,n \end{aligned} xj​​≈Whj​=[w1​​w2​​…​wk​​]⎣⎢⎢⎢⎡​h1j​h2j​⋮hkj​​⎦⎥⎥⎥⎤​=l=1∑k​hlj​wl​,j=1,2,…,n​

其中 hjh_jhj​ 是矩阵 HHH 的第 jjj 列，wlw_lwl​ 是矩阵 WWW 的第 lll 列，hljh_{lj}hlj​ 是 hjh_jhj​ 的第 lll 个元素，l=1,2,…,kl =1,2,\dots , kl=1,2,…,k。

上式表示，矩阵 XXX 的第 jjj 列 xjx_jxj​，可以由矩阵 WWW 的 kkk 个列 wlw_lwl​ 的线性组合逼近，线性组合的系数是矩阵 HHH 的第 jjj 列 hjh_jhj​ 的元素。这里矩阵 WWW 的列向量为一组基，矩阵 HHH 的列向量为线性组合系数。称 WWW 为基矩阵，HHH 为系数矩阵。非负矩阵分解旨在用较少的基向量、系数向量来表示较大的数据矩阵。

非负矩阵分解具有很直观的解释，话题向量和文本向量都非负，对应着“伪概率分布”，向量的线性组合表示局部叠加构成整体。

非负矩阵分解可以形式化为最优化问题求解。设两个非负矩阵 A=[aij]m×nA= [a_{ij}]_{m×n}A=[aij​]m×n​ 和 B=[bij]m×nB= [b_{ij}]_{m×n}B=[bij​]m×n​，首先定义损失函数或代价函数。

第一种损失函数是平方损失。平方损失函数定义为

∣∣A−B∣∣2=∑i,j(aij−bij)2||A-B||^2=\sum_{i,j}(a_{ij}-b_{ij})^2 ∣∣A−B∣∣2=i,j∑​(aij​−bij​)2

其下界是 000，当且仅当 A=BA=BA=B 时达到下界。

另一种损失函数是散度（divergence）。散度损失函数定义为

D(A∣∣B)=∑i,j(aijlog⁡aijbij−aij+bij)D(A||B)=\sum_{i,j}\left( a_{ij}\log\frac{a_{ij}}{b_{ij}}-a_{ij}+b_{ij} \right) D(A∣∣B)=i,j∑​(aij​logbij​aij​​−aij​+bij​)

其下界也是 000，当且仅当 A=BA=BA=B 时达到下界。AAA 和 BBB 不对称。当 ∑i,jaij=∑i,jbij=1\sum\limits_{i,j} a_{ij}= \sum\limits_{i,j} b_{ij}= 1i,j∑​aij​=i,j∑​bij​=1 时散度损失函数退化为 Kullback-Leiber 散度或相对嫡，这时 AAA 和 BBB 是概率分布。

接着定义以下的最优化问题。

目标函数 ∣∣X−WH∣∣2||X - WH||^2∣∣X−WH∣∣2 关于 WWW 和 HHH 的最小化，满足约束条件 W,H≥0W,H≥0W,H≥0，即

min⁡W,H∣∣X−WH∣∣2s.t.W,H≥0(5)\min_{W,H}||X-WH||^2 \\ \tag{5} {\rm s.t.}\space\space\space\space W,H\ge 0 W,Hmin​∣∣X−WH∣∣2s.t.W,H≥0(5)

或者，目标函数 D(X∣∣WH)D(X||WH)D(X∣∣WH) 关于 WWW 和 HHH 的最小化，满足约束条件 W,H≥0W,H ≥ 0W,H≥0，即

min⁡W,HD(X∣∣WH)s.t.W,H≥0(6)\min_{W,H}D(X||WH) \\ \tag{6} {\rm s.t.}\space\space\space\space W,H\ge 0 W,Hmin​D(X∣∣WH)s.t.W,H≥0(6)

考虑求解最优化问题 (5)(5)(5) 和问题 (6)(6)(6)。由于目标函数 ∣∣X−WH∣∣2||X - WH||^2∣∣X−WH∣∣2 和 D(X∣∣WH)D(X||WH)D(X∣∣WH) 只是对变量 WWW 和 HHH 之一的凸函数，而不是同时对两个变量的凸函数，因此找到全局最优（最小值）比较困难，可以通过数值最优化方法求局部最优（极小值）。梯度下降法比较容易实现，但是收敛速度慢。共轭梯度法收敛速度快，但实现比较复杂。Lee 和 Seung 提出了新的基于“乘法更新规则”的优化算法，交替地对 WWW 和 HHH 进行更新，其理论依据是下面的定理。

平方损失 ∣∣X−WH∣∣2||X-WH||^2∣∣X−WH∣∣2 对下列乘法更新规则

Hlj←Hlj(WTX)lj(WTWH)ljWil←Wil(XHT)il(WHHT)ilH_{lj}\leftarrow H_{lj}\frac{(W^TX)_{lj}}{(W^TWH)_{lj}} \\ W_{il}\leftarrow W_{il}\frac{(XH^T)_{il}}{(WHH^T)_{il}} \\ Hlj​←Hlj​(WTWH)lj​(WTX)lj​​Wil​←Wil​(WHHT)il​(XHT)il​​

是非增的。当且仅当 WWW 和 HHH 是平方损失函数的稳定点时函数的更新不变。

散度损失D(X−WH)D(X -WH)D(X−WH) 对下列乘法更新规则

Hlj←Hlj∑i[WilXij/(WH)ij]∑iWilWil←Wil∑j[WljXij/(WH)ij]∑jHljH_{lj}\leftarrow H_{lj}\frac{\sum\limits_i[W_{il}X_{ij}/(WH)_{ij}]}{\sum\limits_iW_{il}} \\ W_{il}\leftarrow W_{il}\frac{\sum\limits_j[W_{lj}X_{ij}/(WH)_{ij}]}{\sum\limits_jH_{lj}} Hlj​←Hlj​i∑​Wil​i∑​[Wil​Xij​/(WH)ij​]​Wil​←Wil​j∑​Hlj​j∑​[Wlj​Xij​/(WH)ij​]​

是非增的。当且仅当 WWW 和 HHH 是散度损失函数的稳定点时函数的更新不变。

现叙述非负矩阵分解的算法。只介绍第一个问题 (5)(5)(5) 的算法，第二个问题 (6)(6)(6) 的算法类似。

最优化目标函数是 ∣∣X−WH∣∣2||X-WH||^2∣∣X−WH∣∣2，为了方便将目标函数乘以 12\frac{1}{2}21​，其最优解与原问题相同，记作

J(W,H)=12∣∣X−WH∣∣2=12∑[Xij−(WH)ij]2J(W,H)=\frac{1}{2}||X-WH||^2=\frac{1}{2}\sum [X_{ij}-(WH)_{ij}]^2 J(W,H)=21​∣∣X−WH∣∣2=21​∑[Xij​−(WH)ij​]2

应用梯度下降法求解。首先求目标函数的梯度

∂J(W,H)∂Wil=−∑j[Xij−(WH)ij]Hlj=−[(XHT)il−(WHHT)il](7)\begin{aligned} \frac{\partial J(W,H)}{\partial W_{il}}&=-\sum_j[X_{ij}-(WH)_{ij}]H_{lj} \\ &=-[(XH^T)_{il}-(WHH^T)_{il}] \\\tag{7} \end{aligned} ∂Wil​∂J(W,H)​​=−j∑​[Xij​−(WH)ij​]Hlj​=−[(XHT)il​−(WHHT)il​]​(7)

同样可得

∂J(W,H)∂Hlj=−[(WTX)lj−(WTWH)lj](8)\frac{\partial J(W,H)}{\partial H_{lj}}=-[(W^TX)_{lj}-(W^TWH)_{lj}]\tag{8} ∂Hlj​∂J(W,H)​=−[(WTX)lj​−(WTWH)lj​](8)

然后求得梯度下降法的更新规则，由式 (7)(7)(7) 和式 (8)(8)(8) 有

Wil=Wil+λil[(XHT)il−(WHHT)il]Hlj=Hlj+μlj[(WTX)lj−(WTWH)lj]W_{il}=W_{il}+\lambda_{il}[(XH^T)_{il}-(WHH^T)_{il}] \\ H_{lj}=H_{lj}+\mu_{lj}[(W^TX)_{lj}-(W^TWH)_{lj}] \\ Wil​=Wil​+λil​[(XHT)il​−(WHHT)il​]Hlj​=Hlj​+μlj​[(WTX)lj​−(WTWH)lj​]

式中 λil\lambda_{il}λil​，μlj\mu_{lj}μlj​ 是步长。选取

λil=Wil(WHHT)il,μlj=Hlj(WTWH)lj\lambda_{il}=\frac{W_{il}}{(WHH^T)_{il}},\space\space\space\space \mu_{lj}=\frac{H_{lj}}{(W^TWH)_{lj}} λil​=(WHHT)il​Wil​​,μlj​=(WTWH)lj​Hlj​​

即得乘法更新规则

Wil=Wil(XHT)il(WHHT)il,i=1,2,…,m;l=1,2,…,kHlj=Hlj(WTX)lj(WTWH)lj,l=1,2,…,k;j=1,2,…,nW_{il}=W_{il}\frac{(XH^T)_{il}}{(WHH^T)_{il}},\space\space i=1,2,\dots,m;\space\space l=1,2,\dots, k \\ H_{lj}=H_{lj}\frac{(W^TX)_{lj}}{(W^TWH)_{lj}},\space\space l=1,2,\dots,k;\space\space j=1,2,\dots, n Wil​=Wil​(WHHT)il​(XHT)il​​,i=1,2,…,m;l=1,2,…,kHlj​=Hlj​(WTWH)lj​(WTX)lj​​,l=1,2,…,k;j=1,2,…,n

选取初始矩阵 WWW 和 HHH 为非负矩阵，可以保证迭代过程及结果的矩阵 WWW 和 HHH 均为非负。

下面叙述基于乘法更新规则的矩阵非负分解迭代算法。算法交替对 WWW 和 HHH 迭代，每次迭代对 WWW 的列向量归一化，使基向量为单位向量。

输入:单词文本矩阵X≥0;文本集合的话题个数k;最大迭代次数t;过程:\begin{array}{ll} \textbf{输入:}&\space 单词文本矩阵 \space X\ge 0 \space;&&&&&&\\ &\space 文本集合的话题个数\space k \space;\\ &\space最大迭代次数 \space t\space;\\ \textbf{过程:} \end{array} 输入:过程:​单词文本矩阵X≥0;文本集合的话题个数k;最大迭代次数t;​

1:W≥0，并对W的每一列数据归一化;H≥0;2:repeat3:t=t−14:forl=1,2,⋅⋅⋅,kdo5:fori=1,2,⋅⋅⋅,mdo6:Wil=Wil(XHT)il(WHHT)il7:endfor8:endfor9:forl=1,2,⋅⋅⋅,kdo10:forj=1,2,⋅⋅⋅,ndo11:Hlj=Hlj(WTX)lj(WTWH)lj12:endfor13:endfor14:untilt=0\begin{array}{rl} 1:&W\ge 0，并对\space W\space 的每一列数据归一化\space;\\ & H\ge 0\space; \\ 2:&\textbf{repeat}\\ 3:&\space\space\space\space t=t-1\\ 4:&\space\space\space\space \textbf{for}\space l=1,2,···,k \space \textbf{do}\\ 5:&\space\space\space\space \space\space\space\space \textbf{for}\space i=1,2,···,m \space \textbf{do}\\ 6:&\space\space \space\space\space\space \space\space \space\space\space\space W_{il}=W_{il}\frac{(XH^T)_{il}}{(WHH^T)_{il}} \\ 7:&\space\space \space\space\space\space \space\space \textbf{end}\space \textbf{for}\\ 8:&\space\space\space\space\textbf{end}\space \textbf{for}\\ 9:&\space\space\space\space \textbf{for}\space l=1,2,···,k \space \textbf{do}\\ 10:&\space\space \space\space\space\space \space\space \textbf{for}\space j=1,2,···,n \space \textbf{do}\\ 11:&\space\space \space\space\space\space \space\space \space\space\space\space H_{lj}=H_{lj}\frac{(W^TX)_{lj}}{(W^TWH)_{lj}} \\ 12:&\space\space \space\space\space\space \space\space \textbf{end}\space \textbf{for} \\ 13:&\space\space\space\space\textbf{end}\space \textbf{for}\\ 14:& \textbf{until}\space t = 0\\ \end{array} 1:2:3:4:5:6:7:8:9:10:11:12:13:14:​W≥0，并对W的每一列数据归一化;H≥0;repeatt=t−1forl=1,2,⋅⋅⋅,kdofori=1,2,⋅⋅⋅,mdoWil​=Wil​(WHHT)il​(XHT)il​​endforendforforl=1,2,⋅⋅⋅,kdoforj=1,2,⋅⋅⋅,ndoHlj​=Hlj​(WTWH)lj​(WTX)lj​​endforendforuntilt=0​

输出:话题矩阵W，文本表示矩阵H\begin{array}{l} \textbf{输出:}\space 话题矩阵 \space W，文本表示矩阵 \space H &&&& \end{array} 输出:话题矩阵W，文本表示矩阵H​​​​​

算法 1非负矩阵分解的迭代算法