第17章 潜在语义分析

习题17.1

  试将图17.1的例子进行潜在语义分析，并对结果进行观察。

解答：

解答思路：

1. 给出潜在语义分析算法
2. 使用numpy的奇异值分解方法对图17.1的例子进行潜在语义分析
3. 对结果进行观察及分析

解答步骤：

第1步：潜在语义分析算法

  根据书中第17.2节的潜在语义分析算法的计算步骤：

1. 单词-文本矩阵
   给定文本集合$D=\{d_1,d_2,\cdots ,d_n\}$和单词集合$W=\{w_1,w_2,\cdots ,w_m\}$。潜在语义分析首先将这些数据表示成一个单词-文本矩阵

$$X=\left[\begin{array}{cccc}{x}_{11}& x_{12}& \cdots & x_{1n}\\ x_{21}& x_{22}& \cdots & x_{2n}\\ \cdots & \cdots & \cdots & \cdots \\ x_{m1}& x_{m2}& \cdots & x_{mn}\end{array}\right]$$

其中，元素$x_{ij}$表示单词$w_i$在文本$d_j$中出现的频数或权值。

2. 截断奇异值分解
   根据确定的话题个数$k$对单词-文本矩阵$X$进行截断奇异值分解

$$X\approx U_k{\mathrm{\Sigma }}_k{V}_k^T=[u_1{u}_2\cdots u_k]\left[\begin{array}{cccc}{\sigma }_1& 0& 0& 0\\ 0& {\sigma }_2& 0& 0\\ 0& 0& \ddots & 0\\ 0& 0& 0& {\sigma }_k\end{array}\right]\left[\begin{array}{c}{v}_1^T\\ v_2^T\\ ⋮\\ v_k^T\end{array}\right]$$

其中$k⩽n⩽m$，$U_k$是$m\times k$矩阵，它的列由$X$的前$k$个相互正交的左奇异向量组成，${\mathrm{\Sigma }}_k$是$k$阶对角方阵，对角元素为前$k$个最大奇异值，$V_k$是$n\times k$矩阵，它的列由$X$的前$k$个相互正交的右奇异向量组成。

3. 话题向量空间
   矩阵$U_k$的每一个列向量$u_1,u_2,\cdots ,u_k$表示一个话题，称为话题向量。由这$k$个话题向量张成一个子空间

$$U_k=[u_1{u}_2\cdots u_k]$$

称为话题向量空间。

4. 文本的话题空间表示
   矩阵$X$的第$j$列向量$x_j$满足

$$x_j\approx \sum _{l=i}^k{\sigma }_l{v}_{jl}{u}_l,j=1,2,\cdots ,n$$

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

$$X\approx U_k{\mathrm{\Sigma }}_k{V}_k^T=U_k({\mathrm{\Sigma }}_k{V}_k^T)$$

得到话题空间$U_k$，以及文本在话题空间的表示$({\mathrm{\Sigma }}_k{V}_k^T)$。

第2步：对图17.1的例子进行潜在语义分析

import numpy as np


def lsa_svd(X, k):
    """
    潜在语义分析的矩阵奇异值分解
    :param X: 单词-文本矩阵
    :param k: 话题数
    :return: 话题向量空间、文本集合在话题向量空间的表示
    """
    # 单词-文本矩阵X的奇异值分解
    U, S, V = np.linalg.svd(X)
    # 矩阵的截断奇异值分解，取前k个
    U = U[:, :k]
    S = np.diag(S[:k])
    V = V[:k, :]

    return U, np.dot(S, V)

X = np.array([[2, 0, 0, 0],
              [0, 2, 0, 0],
              [0, 0, 1, 0],
              [0, 0, 2, 3],
              [0, 0, 0, 1],
              [1, 2, 2, 1]])

# 设置精度为2
np.set_printoptions(precision=2, suppress=True)
# 假设话题的个数是3个
U, SV = lsa_svd(X, k=3)
print("话题空间U：")
print(U)
print("文本在话题空间的表示SV：")
print(SV)

话题空间U：
[[-0.08  0.28  0.89]
 [-0.16  0.57 -0.45]
 [-0.14 -0.01  0.  ]
 [-0.73 -0.55  0.  ]
 [-0.15 -0.18  0.  ]
 [-0.63  0.51 -0.  ]]
文本在话题空间的表示SV：
[[-0.79 -1.57 -2.86 -2.96]
 [ 1.08  2.15 -0.1  -1.33]
 [ 1.79 -0.89  0.    0.  ]]

第3步：对结果进行观察及分析

  在假设话题个数为3的情况下，单词airplane在话题3上的权值最大为0.89，表示单词airplane在话题3中的重要度最高；文本$d_2$在话题2中的权值最大为2.15，表示话题2在文本$d_2$中的重要度最高。

习题17.2

  给出损失函数是散度损失时的非负矩阵分解（潜在语义分析）的算法。

解答：

解答思路：

1. 给出散度的定义
2. 给出散度损失的定义
3. 给出损失函数是平方损失时的非负矩阵分解算法
4. 写出损失函数是散度损失时的非负矩阵分解算法
5. 自编程实现损失函数是散度损失时的非负矩阵分解算法

解答步骤：

第1步：散度的定义

  根据书中附录E的KL散度的定义：

  KL散度是描述两个概率分布$Q(x)$和$P(x)$相似度的一种度量，记作$D(Q\parallel P)$。对离散随机变量，KL散度定义为

$$\begin{array}{}\text{(E.1)}& D(Q\parallel P)=\sum _{i}Q(i)\log \frac{Q(i)}{P(i)}\end{array}$$

对连续随机变量，KL散度定义为

$$\begin{array}{}\text{(E.2)}& D(Q\parallel P)=\int Q(x)\log \frac{Q(x)}{P(x)}dx\end{array}$$

第2步：散度损失的定义

  根据书中第17章的定理17.2：

定理17.2 散度损失$D(X\parallel WH)$对下列乘法更新规则

$$\begin{gathered} H_{lj}\leftarrow H_{lj}\frac{{\displaystyle \sum _i[W_{il}{X}_{ij}/(WH{)}_{ij}]}}{{\displaystyle \sum _i{W}_{il}}} \\ {W}_{il}\leftarrow W_{il}\frac{{\displaystyle \sum _j[H_{lj}{X}_{ij}/(WH{)}_{ij}]}}{{\displaystyle \sum _j{H}_{lj}}} \end{gathered}$$

是非增的。当且仅当$W$和$H$是散度损失函数的稳定点时，函数的更新不变。

第3步：损失函数是平方损失时的非负矩阵分解算法

  根据书中第17章的算法17.1的非负矩阵分解的迭代算法

算法17.1 （非负矩阵分解的迭代算法）
输入：单词-文本矩阵$X⩾0$，文本集合的话题个数$k$，最大迭代次数$t$；
输出：话题矩阵$W$，文本表示矩阵$H$。
（1）初始化
  $W⩾0$，并对$W$的每一列数据归一化；$H⩾0$。
（2）迭代
  对迭代次数由1到$t$执行下列步骤：
  （a）更新$W$的元素，对$l$从1到$k$，$i$从1到$m$按照如下公式更新$W_{il}$

$$W_{il}=W_{il}\frac{(X{H}^T{)}_{il}}{(WH{H}^T{)}_{il}},i=1,2,\cdots ,m;l=1,2,\cdots ,k$$

  （b）更新$H$的元素，对$l$从1到$k$，$j$从1到$n$按照如下公式更新$H_{lj}$

$$H_{lj}=H_{lj}\frac{(W^{T}X{)}_{lj}}{(W^{T}WH{)}_{lj}},l=1,2,\cdots ,k;j=1,2,\cdots ,n$$

第4步：损失函数是散度损失时的非负矩阵分解算法

输入：单词-文本矩阵$X⩾0$，文本集合的话题个数$k$，最大迭代次数$t$；
输出：话题矩阵$W$，文本表示矩阵$H$。
（1）初始化
  $W⩾0$，并对$W$的每一列数据归一化；
  $H⩾0$；
（2）迭代
  对迭代次数由1到$t$执行下列步骤：
  （a）更新$W$的元素，对$l$从1到$k$，$i$从1到$m$按照如下公式更新$W_{il}$

$$W_{il}\leftarrow W_{il}\frac{{\displaystyle \sum _j[H_{lj}{X}_{ij}/(WH{)}_{ij}]}}{{\displaystyle \sum _j{H}_{lj}}}$$

  （b）更新$H$的元素，对$l$从1到$k$，$j$从1到$n$按照如下公式更新$H_{lj}$

$$H_{lj}\leftarrow H_{lj}\frac{{\displaystyle \sum _i[W_{il}{X}_{ij}/(WH{)}_{ij}]}}{{\displaystyle \sum _i{W}_{il}}}$$

  （c）计算损失函数

$$\sum _{i=0}^m\sum _{j=0}^n(X_{ij}\log \frac{X_{ij}}{(WH{)}_{ij}}-X_{ij}+(WH{)}_{ij})$$

第5步：自编程实现损失函数是散度损失时的非负矩阵分解算法

import numpy as np


class DivergenceNmfLsa:
    def __init__(self, max_iter=1000, tol=1e-6, random_state=0):
        """
        损失函数是散度损失时的非负矩阵分解
        :param max_iter: 最大迭代次数
        :param tol: 容差
        :param random_state: 随机种子
        """
        self.max_iter = max_iter
        self.tol = tol
        self.random_state = random_state
        np.random.seed(self.random_state)

    def _init_param(self, X, k):
        self.__m, self.__n = X.shape
        self.__W = np.random.random((self.__m, k))
        self.__H = np.random.random((k, self.__n))

    def _div_loss(self, X, W, H):
        Y = np.dot(W, H)
        loss = 0
        for i in range(self.__m):
            for j in range(self.__n):
                loss += (X[i][j] * np.log(X[i][j] / Y[i][j]) if X[i][j] * Y[i][j] > 0 else 0) - X[i][j] + Y[i][j]

        return loss

    def fit(self, X, k):
        """
        :param X: 单词-文本矩阵
        :param k: 话题个数
        :return:
        """
        # (1)初始化
        self._init_param(X, k)
        # (2.c)计算散度损失
        loss = self._div_loss(X, self.__W, self.__H)

        for _ in range(self.max_iter):
            # (2.a)更新W的元素
            WH = np.dot(self.__W, self.__H)
            for i in range(self.__m):
                for l in range(k):
                    s1 = sum(self.__H[l][j] * X[i][j] / WH[i][j] for j in range(self.__n))
                    s2 = sum(self.__H[l][j] for j in range(self.__n))
                    self.__W[i][l] *= s1 / s2

            # (2.b)更新H的元素
            WH = np.dot(self.__W, self.__H)
            for l in range(k):
                for j in range(self.__n):
                    s1 = sum(self.__W[i][l] * X[i][j] / WH[i][j] for i in range(self.__m))
                    s2 = sum(self.__W[i][l] for i in range(self.__m))
                    self.__H[l][j] *= s1 / s2

            new_loss = self._div_loss(X, self.__W, self.__H)
            if abs(new_loss - loss) < self.tol:
                break

            loss = new_loss

        return self.__W, self.__H

X = np.array([[2, 0, 0, 0],
              [0, 2, 0, 0],
              [0, 0, 1, 0],
              [0, 0, 2, 3],
              [0, 0, 0, 1],
              [1, 2, 2, 1]])

# 设置精度为2
np.set_printoptions(precision=2, suppress=True)
# 假设话题的个数是3个
k = 3
div_nmf = DivergenceNmfLsa(max_iter=1000, random_state=2022)
W, H = div_nmf.fit(X, k)
print("话题空间W：")
print(W)
print("文本在话题空间的表示H：")
print(H)

话题空间W：
[[0.   0.   1.39]
 [0.   1.47 0.  ]
 [0.35 0.   0.  ]
 [1.77 0.   0.  ]
 [0.35 0.   0.  ]
 [1.06 1.47 0.7 ]]
文本在话题空间的表示H：
[[0.   0.   1.41 1.41]
 [0.   1.36 0.   0.  ]
 [1.44 0.   0.   0.  ]]

习题17.3

  给出潜在语义分析的两种算法的计算复杂度，包括奇异值分解法和非负矩阵分解法。

解答：

解答思路：

1. 给出潜在语义分析的奇异值分解法，并计算复杂度
2. 给出潜在语义分析的非负矩阵分解法，并计算复杂度

解答步骤：

  给定文本集合$D=\{d_1,d_2,\cdots ,d_n\}$和单词集合$W=\{w_1,w_2,\cdots ,w_m\}$，则单词-文本矩阵为

$$X=\left[\begin{array}{cccc}{x}_{11}& x_{12}& \cdots & x_{1n}\\ x_{21}& x_{22}& \cdots & x_{2n}\\ \cdots & \cdots & \cdots & \cdots \\ x_{m1}& x_{m2}& \cdots & x_{mn}\end{array}\right]$$

第1步：计算潜在语义分析的奇异值分解法的复杂度

奇异值分解法（含截断奇异值分解）的复杂度分析：

1. 求行空间和零空间标准正交基，其复杂度是$O(n{m}^2)$
2. 对$X{X}^T$进行特征值分解，其复杂度是$O(m^3)$

可知，总复杂度为$O(n{m}^2)+O(m^3)$

第2步：计算潜在语义分析的非负矩阵分解法的复杂度

由于非负矩阵分解是迭代的，假设迭代次数为$t$：

• 损失函数是平方损失时的非负矩阵分解的复杂度

  1. 迭代次数从1到$t$次，复杂度包含$t$因子
  2. 更新$W$的元素，复杂度为$O(km)$
  3. 更新$H$的元素，复杂度为$O(kn)$

  可知，复杂度为$O(tkm)+O(tkn)$

• 损失函数是散度损失时的非负矩阵分解的复杂度

  1. 迭代次数从1到$t$次，复杂度包含$t$因子
  2. 更新$W$的元素，复杂度为$O(km)$
  3. 更新$H$的元素，复杂度为$O(kn)$
  4. 计算损失函数，复杂度为$O(mn)$

  可知，复杂度为$O(tkm)+O(tkn)+O(tmn)$

习题17.4

  列出潜在语义分析与主成分分析的异同。

解答：

解答思路：

1. 给出主成分分析的定义
2. 给出潜在语义分析的定义
3. 写出两者的相同点
4. 写出两者的不同点

解答步骤：

第1步：主成分分析的定义

  根据书中第16章的主成分分析介绍：

  主成分分析（PCA）是一种常用的无监督学习方法，这一方法利用正交变换把由线性相关变量表示的观测数据转换为少数几个由线性无关变量表示的数据，线性无关的变量称为主成分。主成分分析属于降维方法。主成分分析主要用于发现数据中的基本结构，即数据中变量之间的关系，是数据分析的有力工具，也用于其他机器学习方法的前处理。主成分分析属于多元统计分析的经典方法。

  根据书中第16章的本章概要的主成分分析方法：

  主成分分析方法主要有两种，可以通过相关矩阵的特征值分解或样本矩阵的奇异值分解进行。
  （1）相关矩阵的特征值分解算法。针对$m\times n$样本矩阵$X$，求样本相关矩阵

$$R=\frac{1}{n-1}X{X}^T$$

再求样本相关矩阵的$k$个特征值和对应的单位特征向量，构造正交矩阵

$$V=(v_1,v_2,\cdots ,v_k)$$

$V$的每一列对应一个主成分，得到$k\times n$样本主成分矩阵

$$Y=V^{T}X$$

  （2）矩阵$X$的奇异值分解算法。针对$m\times n$样本矩阵$X$

$$X^{\prime }=\frac{1}{\sqrt{n-1}}{X}^T$$

对矩阵$X^{\prime }$进行截断奇异值分解，保留$k$个奇异值、奇异向量，得到

$$X^{\prime }=US{V}^T$$

V的每一列对应一个主成分，得到$k\times n$样本主成分矩阵$Y$

$$Y=V^{T}X$$

第2步：潜在语义分析的定义

  根据书中第17章的潜在语义分析介绍：

  潜在语义分析（LSA）是一个无监督学习方法，主要用于文本的话题分析，其特点是通过矩阵分解发现文本与单词之间的基于话题的语义关系。潜在语义分析使用的是非概率的话题分析模型，关键是对单词-文本矩阵进行矩阵因子分解（话题分析）。

  算法部分详见书中第17.2节的潜在语义分析算法的计算步骤。

第3步：两者的相同点

1. 两者都属于无监督学习方法
2. 两者都基于矩阵的奇异值分解
3. 两者都可采用截断奇异值分解
4. 两者都可用于降维

第4步：两者的不同点

1. PCA对数据矩阵的协方差矩阵或者相关系数矩阵进行奇异值分解，而LSA直接对数据矩阵进行奇异值分解
2. PCA需要对数据进行正规化，而LSA可以不对数据进行正规化
3. PCA的原始矩阵一般不是稀疏矩阵，而LSA的矩阵一般是稀疏矩阵