首页 > 代码库 > Topic Model之Probabilistic Latent Semantic Indexing(PLSI/PLSA)
Topic Model之Probabilistic Latent Semantic Indexing(PLSI/PLSA)
一、 基本概念
1. SVD奇异值分解：SVD主要用来求低阶近似问题。当给定一个MXN的矩阵C时(其秩为r)，我们希望找到一个近似矩阵C‘（其秩不大于k），当k远小于r时，我们称C’为C的低阶近似，设X = C - C‘为两个矩阵的差，X的F-范数为：
SVD计算步骤：
a、 给定一个矩阵C，对其奇异值进行分解：C = U ∑ V
b、 构造∑ ‘， 其秩为k，选择将∑ 中奇异值最小的r-k个值置为0，即得到∑ ’
c、 计算C‘ = U ∑’ V
因为特征值大小对矩阵和向量乘法的影响大小成正比，而奇异值和特征值也是成正比，因而选择最小的r-k个奇异值置为0 是合理的。
2. PCA主成分分析：PCA试图在丢失数据信息最少的情况下，对多维的数据进行最优综合简化，对高维的变量空间进行降维处理。
PCA计算步骤：
a、 首先计算训练样本的均值和协方差矩阵：
b、 对协方差矩阵进行特征值分解：
c、 选择前k个最大的特征值对应的特征向量作为主成分分量，这些分量构成特征空间，我们就得到变换矩阵
对任何一条数据X，通过如下变化，将其转化到新的特征空间中的向量y:
3. TF-IDF:
首先介绍TF-term frequency，它用来度量 一个单词在一个文档中出现的频率。由于不同的文档长短不同，为了防止TF偏向于长文件，通常对词频进行归一化处理。
通常一个文档中如果某个词出现的频率较高，可以认为这个文档和这个词的相关性比较高，但是，如果所有的文档都含有这个词，这时候，这个词的区分度反而就不是那么高。因此，可以用IDF来度量一个词的区分度：逆向文件频率——将总文件数除以包含该词语的文件数，将结果取对数，即得到逆向文件频率。
最后，综合TF和IDF，我们得到TF-IDF的计算方法：
某一个特定文件中的高频词，以及该词在所有文件中的低文件频率，可以产生出较高的TFIDF. TF-IDF倾向于过滤掉常见词，保留区分度较高的词。
4. BOW： bag of words
BOW将一篇文章看成是词汇的集合，忽略单词在文章中出现的位置、句法语法等信息。利用文章中出现过的词构建一个词表，基于词表将每一篇文章转化为一个向量，向量的每一维对应一个单词，每一维的值对应单词出现的次数。
二、 LSI模型
LSA(LSI)使用SVD来对单词-文档矩阵进行分解。SVD可以看作是从单词-文档矩阵中发现不相关的索引变量(因子)，将原来的数据映射到语义空间内。在单词-文档矩阵中不相似的两个文档，可能在语义空间内比较相似。
SVD，亦即奇异值分解，是对矩阵进行分解的一种方法，一个t*d维的矩阵(单词-文档矩阵)X，可以分解为T*S*DT，其中T为t*m维矩阵，T中的每一列称为左奇异向量(left singular bector)，S为m*m维对角矩阵，每个值称为奇异值(singular value)，D为d*m维矩阵,D中的每一列称为右奇异向量。在对单词文档矩阵X做SVD分解之后，我们只保存S中最大的K个奇异值，以及T和D中对应的K个奇异向量，K个奇异值构成新的对角矩阵S’，K个左奇异向量和右奇异向量构成新的矩阵T’和D’：X’=T’*S’*D’T形成了一个新的t*d矩阵。
假设索引的文档的集合如下：
对应的单词-文档矩阵X如下：
[[ 1. 0. 0. 1. 0. 0. 0. 0. 0.] [ 1. 0. 1. 0. 0. 0. 0. 0. 0.] [ 1. 1. 0. 0. 0. 0. 0. 0. 0.] [ 0. 1. 1. 0. 1. 0. 0. 0. 0.] [ 0. 1. 1. 2. 0. 0. 0. 0. 0.] [ 0. 1. 0. 0. 1. 0. 0. 0. 0.] [ 0. 1. 0. 0. 1. 0. 0. 0. 0.] [ 0. 0. 1. 1. 0. 0. 0. 0. 0.] [ 0. 1. 0. 0. 0. 0. 0. 0. 1.] [ 0. 0. 0. 0. 0. 1. 1. 1. 0.] [ 0. 0. 0. 0. 0. 0. 1. 1. 1.] [ 0. 0. 0. 0. 0. 0. 0. 1. 1.]]
对其进行SVD分解得到X=T*S*DT：
其中T如下：
[-0.22 -0.11 0.29 -0.41 -0.11 -0.34 -0.52 0.06 0.41] [-0.2 -0.07 0.14 -0.55 0.28 0.5 0.07 0.01 0.11] [-0.24 0.04 -0.16 -0.59 -0.11 -0.25 0.3 -0.06 -0.49] [-0.4 0.06 -0.34 0.1 0.33 0.38 -0. 0. -0.01] [-0.64 -0.17 0.36 0.33 -0.16 -0.21 0.17 -0.03 -0.27] [-0.27 0.11 -0.43 0.07 0.08 -0.17 -0.28 0.02 0.05] [-0.27 0.11 -0.43 0.07 0.08 -0.17 -0.28 0.02 0.05] [-0.3 -0.14 0.33 0.19 0.11 0.27 -0.03 0.02 0.17] [-0.21 0.27 -0.18 -0.03 -0.54 0.08 0.47 0.04 0.58] [-0.01 0.49 0.23 0.02 0.59 -0.39 0.29 -0.25 0.23] [-0.04 0.62 0.22 0. -0.07 0.11 -0.16 0.68 -0.23] [-0.03 0.45 0.14 -0.01 -0.3 0.28 -0.34 -0.68 -0.18]DT如下：
[-0.2 -0.61 -0.46 -0.54 -0.28 -0. -0.01 -0.02 -0.08] [-0.06 0.17 -0.13 -0.23 0.11 0.19 0.44 0.62 0.53] [ 0.11 -0.5 0.21 0.57 -0.51 0.1 0.19 0.25 0.08] [-0.95 -0.03 0.04 0.27 0.15 0.02 0.02 0.01 -0.02] [ 0.05 -0.21 0.38 -0.21 0.33 0.39 0.35 0.15 -0.6 ] [-0.08 -0.26 0.72 -0.37 0.03 -0.3 -0.21 0. 0.36] [-0.18 0.43 0.24 -0.26 -0.67 0.34 0.15 -0.25 -0.04] [ 0.01 -0.05 -0.01 0.02 0.06 -0.45 0.76 -0.45 0.07] [ 0.06 -0.24 -0.02 0.08 0.26 0.62 -0.02 -0.52 0.45]S如下：
[ 3.34
2.54
2.35
1.64
1.50
1.31
0.85
0.56
0.36]
如果我们只保留奇异值最大的两个，则得到T’
[-0.22 -0.11] [-0.2 -0.07] [-0.24 0.04] [-0.4 0.06] [-0.64 -0.17] [-0.27 0.11] [-0.27 0.11] [-0.3 -0.14] [-0.21 0.27] [-0.01 0.49] [-0.04 0.62] [-0.03 0.45]
得到的D‘T如下：
[-0.2 -0.61 -0.46 -0.54 -0.28 -0. -0.01 -0.02 -0.08] [-0.06 0.17 -0.13 -0.23 0.11 0.19 0.44 0.62 0.53]S’如下：
[[ 3.34 0. ] [ 0. 2.54 ]]最后还原得到X‘如下：
[ 0.16 0.4 0.38 0.47 0.18 -0.05 -0.12 -0.16 -0.09] [ 0.14 0.37 0.33 0.4 0.16 -0.03 -0.07 -0.1 -0.04] [ 0.15 0.51 0.36 0.41 0.24 0.02 0.06 0.09 0.12] [ 0.26 0.84 0.61 0.7 0.39 0.03 0.08 0.12 0.19] [ 0.45 1.23 1.05 1.27 0.56 -0.07 -0.15 -0.21 -0.05] [ 0.16 0.58 0.38 0.42 0.28 0.06 0.13 0.19 0.22] [ 0.16 0.58 0.38 0.42 0.28 0.06 0.13 0.19 0.22] [ 0.22 0.55 0.51 0.63 0.24 -0.07 -0.14 -0.2 -0.11] [ 0.1 0.53 0.23 0.21 0.27 0.14 0.31 0.44 0.42] [-0.06 0.23 -0.14 -0.27 0.14 0.24 0.55 0.77 0.66] [-0.06 0.34 -0.15 -0.3 0.2 0.31 0.69 0.98 0.85] [-0.04 0.25 -0.1 -0.21 0.15 0.22 0.5 0.71 0.62]还原后的X’与X差别很大，这是因为我们认为之前X存在很大的噪音，X’是对X处理过同义词和多义词后的结果。
在查询时，对与每个给定的查询，我们根据这个查询中包含的单词(Xq)构造一个伪文档：Dq=XqTS-1，然后该伪文档和D’中的每一行计算相似度(余弦相似度)来得到和给定查询最相似的文档。
（此处参考：http://www.cnblogs.com/kemaswill/）
三、 PLSI
1. Model引入：
PLSI是一个生成模型，它同时产生文档d和文档中包含的词w，以及文档的话题z（隐变量）。
下图示意了PLSI的生成过程：
首先从语料库中以P(d)的概率选择一篇文档d，然后从文档d中以P(z|d)的概率选择文档所包含的话题z，对于话题z，以P（w|z）的概率从词表中选择话题z包含的词w。在话题模型中，单词-文档矩阵被分解成为两个矩阵：一个话题矩阵Φ和一个文档矩阵Θ。
2. PLSI的应用介绍
这样的分解方式，可以有很多应用，中间的隐变量（话题）在不同的场景下可以有不同的理解：
以上这个例子中，将隐变量（话题）理解为客户的Latent Profile，根据用户的Latent Profile可以知道什么样的客户喜欢什么样的Product。这样可以用来为客户推荐新的Product。
再比如，对于文档而言，我们可以将文档-单词矩阵X表示成文档-话题矩阵V（用话题来表示文档），以及话题-单词矩阵U（用单词来表示话题）。
3. Maxium Likelihood
为了理解PLSI模型，我们首先介绍一下Maxium Likelihood：
我们知道，很多的概率分布函数都是由一些参数所控制着，例如，对于正态分布（X~N（μ，σ^））有均值和方差两个参数控制，当我们知道参数的时候，我们就知道了随机变量X的分布情况。假如我们有了一个从某分布产生的数据集X={x1, x2, ..., xn},但是我们不知道分布的参数，那么我们可以假定，这个参数最有可能是使得产生数据集X的概率最大的参数。假定我们已经知道这个参数，那么产生数据集X的概率可以用下面这个式子来表示：
注：a、此处假定数据集中的每个样本都是独立同分布的；b、实际上这个式子是概率的对数形式——log-likelihood。
有了关于数据集X的概率的表达式，我们寻求使这个概率最大的参数Θ*，在参数Θ取这个Θ*时，概率L最大。那我们有理由认为，Θ很有可能就是我们求得的Θ*.
4. PLSI的推导
依据Maxium Likelihood的原理，我们按照PLSI的生成模型来计算已知文档的log-likelihood.
以上的Θ即我们这个生成模型中控制所有概率分布的位置参数，我们得到likelihood的表达式以后，通过最大化likelihood来求解Θ的值。
在求解使likelihood最大的Θ的值的过程中，我们用到了Jensen不等式。Jensen不等式的直观理解如下图所示：
设随机变量X以及一个凸函数f，对于随机变量f(X)的期望值E[f(x)]大于或者等于X的期望值EX对应的函数值f(EX).等号成立当且仅当X = EX，即X是一个常量
直接求解L是比较困难的，我们可以通过不断迭代，每次寻求一个L的下界（lower-bound），然后不断优化这个lower-bound的值，使其逼近最优值。
按照上面的思路，我们来推导PLSI：
我们首先定义
把之前求得的L应用Jensen不等式计算一个Lower-bound
得到lower-bound的表达式以后，我们用拉格朗日乘子法来求解未知参数。
E-Step：
a、 求解：P（w|z）
由于ΣP（w|z） = 1，所以采用拉格朗日乘子法以后，我们将得到的拉格朗日表达式对P(w|z)求导，得到下式
解得：
由于ΣP（w|z） = 1， 我们可以得到：
b、 求解P(d|z): 同a，我们求得表达式如下
c、 求解P（z）
由于条件ΣP（z） = 1，我们同样采用拉格朗日乘子法，
求解得到：
由于条件ΣP（z） = 1，我们得到：
M-Step:
最终迭代更新的方程为：
5. PLSI算法设计：
注：初始化的时候，几个待求的未知参数可以设置为随机的值，只要满足所有概率的总和为1即可。