技术报告_SVD与LDA

SVD与LDA一、矩阵的奇异值分解(SingularValueDecomposition，SVD）1.矩阵的奇异值定义设C是MxN实矩阵，称n阶方阵CTC的非0特征值的算术平方根为矩阵C的奇异值。2.矩阵的奇异值分解定理SVD（SingleValueDecomposition），即奇异值分解，是潜在语义索引的理论基础。它是线性代数中有关矩阵分解的一个理论。设A是秩为r的mn阶实矩阵，则存在m阶正交阵U和n阶正交阵V，使得TUSVA（1）其中，矩阵U、S和V分别为mm、mn和nn维的矩阵。矩阵U的各列为AAT的特征向量，矩阵V的各列为ATA的特征向量。且矩阵AAT和矩阵ATA的特征值均为1,…,r（i0，i=1,2,…,r），设ii，则)(1diagS。即矩阵S为对角阵，S中的对角元素称为奇异值。图1给出了一个奇异值分解的示例。图1SVD分解图示Fig.1AnexampleofSVDSVD分解能被用来计算最优的low-rankapproximation，即SVD分解能得到原矩阵的最优低阶近似。这转化为一个近似问题，即：找到秩为k的矩阵Ak，使得FkXrankXkXAAmin)(:（2）其中，minjijFaA112称为Frobeniuserror，Ak和X均为mn的矩阵。kr。在SVD中，解决办法是采用TruncatedSVD。即将SVD分解中的对角矩阵中的后面r-k个对角元素置为0，只保留前k个对角元素。因为对角元素是按照从大到小降序排列的，这样一来，就能保持在降维的情况下，还能保证最小错误率（minimumFrobeniuserror）。TruncatedSVD的公式是：TkkVUdiagA0,..,0,.,...,1（3）矩阵Ak也可以表示成：TiikiikvuA1（4）图2是TruncatedSVD的一个示例。图2TruncatedSVD分解图示Fig.2AnexampleofTruncatedSVD3.低阶近似LSA潜在语义分析中，低阶近似是为了使用低维的矩阵来表示一个高维的矩阵，并使两者之差尽可能的小。给定一个MxN矩阵C(其秩为r)和正整数k，我们希望找到一个MxN矩阵Ck，其秩不大于K。设X为C与Ck之间的差，X=C–Ck，X的F-范数为（5）当k远小于r时，称Ck为C的低阶近似，其中X也就是两矩阵之差的F范数要尽可能的小SVD可以被用与求低阶近似问题，步骤如下：(1)给定一个矩阵C，对其奇异值分解：（6）(2)构造，它是将的第k+1行至M行设为零，也就是把的最小的r-k个(ther-ksmallest)奇异值设为零。(3)计算Ck：TKkVUC（7）对文本分类，SVD中的矩阵A即是词项-文本矩阵（term-documentvectormatrix），矩阵U即是词项-概念矩阵（term-conceptvectormatrix），V即是概念-文档矩阵（concept-documentvectormatrix），矩阵S是奇异值矩阵，它是对角阵。由于在文本中，词项-文本矩阵的维数（m，n）经常是几万维，矩阵的秩也是上千维。因此，采用TruncatedSVD的方式进行降维处理，在文本分类领域就显得尤为重要。实际中，通过利用TruncatedSVD进行low-rankapproximations，矩阵的秩可以降到100-300维，同时，能保证分类的效果不出现明显的下降。潜在语义空间与原来的空间（VSM）相比，空间维数要小的多。因此，LSI其实是一种降维方法。通过采用TruncatedSVD，能使得特征空间的维度进一步的下降。但同时，LSI的特点是它获取的新的维度在直观上无法给出解释，这一点不同于特征选择的降维方法。4.潜在语义索引示例为了更好的理解潜在语义索引方法在文本分类领域的应用。下面举一个简单的例子。图3是一个词项-文本矩阵A。每一行表示一个词项特征，每一列表示一篇文档。行列元素的值表示该词项是否在对应的文档中出现，如果出现，元素值为1，否则，元素值为0。图3词项-文档矩阵示例Fig.3Anterm-documentvectormatrix对该矩阵进行SVD分解，得到如下三个矩阵，即词项矩阵U、文本矩阵VT和奇异值矩阵S。图4，图5和图6分别表示这三个矩阵。图4词项-概念矩阵示例Fig.4Anterm-conceptvectormatrix图5概念-文档矩阵示例Fig.5Anconcept-documentvectormatrix图6奇异值矩阵示例Fig.6Ansinglevaluevectormatrix其中，矩阵U和矩阵VT中的数字（1,2,…,5）是空间维度标号。采用TruncatedSVD的方法，只保留前2个最大的奇异值，得到新的奇异值矩阵S2，如图7所示。图7新的奇异值矩阵Fig.7Anewsinglevaluevectormatrix再次计算，得到新的矩阵A2，如图8所示。图8新的词项-文档矩阵Fig.8Thenewterm-documentvectormatrix二．LDA（LatentDirichletAllocation）模型LDA模型是目前应用最广泛的一种概率主题模型，它具有比其他模型更全面的文本生成假设。LDA模型对pLSI模型存在的两个问题提出了修正，克服了pLSI模型的缺点：①区别于pLSI模型当中的特征矩阵，LDA在主题-类别层的表示上，采用了一个Dirichlet概率分布。这是一个连续分布，可以给未知文本分配属于某个主题集的概率；②去掉了文本标签这个表示，因此取消了原来对于文本标签的先验概率表示，取而代之的是直接从一个主题分布当中选择合适的主题集合。此外，LDA模型还在模型上更符合现实语义条件。比如在主题的选取上，pLSI模型需要先确定一个文本类别标签，然后根据这个标签产生主题分布，不同主题之间在概率上是相互独立的，而LDA通过Dirichlet分布产生的是一个主题的集合，这个集合不是pLSI当中的一系列独立参数，而是以隐含的随机变量来表示，因此对于现实世界的语义，具有更强的描述能力。有学者指出，pLSI模型是LDA模型在Dirichlet分布退化到一元时的一个特例（Girolamietal，2003）。LDA模型继承了pLSI生成模型的所有优点，不需要加入理想化条件，可以更接近真实的去描述一个语义模型1.LDA模型的基本思想LDA是一种对离散数据集(如文档集)建模的概率增长模型，是一个三层贝叶斯模型，是一种对文本数据的主题信息进行建模的方法，对文档进行一个简短的描述，保留本质的统计信息，有助于高效地处理大规模的文档集。如图9（a）所示，它假设文档集合(顶部大圆)可以分成若干隐含主题(底部小圆)，而这些隐含主题拓扑结构是线性的，进一步利用概率推断算法可以将单个文档表示为这些隐含主题特定比例的混合。如图9（b）所示，LDA模型是典型的有向概率图模型，具有清晰的层次结构，依次为文档集合层、文档层和词层。LDA模型由文档集合层的参数(，)确定，其中反映了文档集合中隐含主题间的相对强弱，刻画所有隐含主题自身的概率分布。随机变量e表征文档层，其分量代表目标文档中各隐含主题的比重。在词层，z表示目标文档分配在每个词上的隐含主题份额，w是目标文档的词向量表示形式。图9LDA模型Fig.9LDAmodel下面是LDA模型应用于文档集主题建模的符号约定：(1)词是文本数据的基本单元，是用{1……V}索引的词表的分项。词表中的第v个词用一个V维的向量w表示，其中对于任意vu，1vw，0uw。(2)文档是N个词的序列，用d={wl，w2，…，wn}表示，wn是序列中的第n个词。(3)文档集是M个文档的集合，表示成D={d1，d2，……，dM}LDA概率主题模型生成文本的过程如下：(1)对于主题j，根据Dirichlet分布Dir切)得到该主题上面的一个单词多项式分布向量)(j。(2)根据泊松分布Poisson（）得到文本的单词数目N。(3)根据Dirichlet分布Dir(a)得到该文本的一个主题分布概率向量。(4)对于该文本N个单词中的每一个单词Wn：a)从的多项式分布Multinomial()随机选择一个主题kb)从主题k的多项式条件概率分布Multinomial（)(k）选择一个单词作为Wn假设有k个主题，则文档d中的第i个词汇琳的概率可以表示为如下:（8）其中，z，是潜在变量，表示第i个词汇wi取自该主题，是词汇wi属于主题j的概率，给出文档d属于主题j的概率。第j个主题表示为词表中V个词的多项式分布，文本表示成K个隐含主题上的随机混合。于是文本d中“发生”词汇w的概率为:（9）通过EM(期望最大化算法)求最大似然函数:(10)的最大似然估计量、，估计、的参数值，从而确定LDA模型。其中文本d“发生”的条件概率分布(11)存在，配对，无法计算出解析式，需要求出近似解。LDA模型的关键变量是主题一单词分布功和主题分布e。显然，通过可采用Laplace近似、变分推理(variationalInferenCe)、GibbS抽样以及期望一扩散(Expectati。nPropagati。n)等近似推理算法获取待估参数值。ThomaSL.GriffithS[32]等人提出GibbS抽样在困惑度和运行速度方面均优于变分推理和期望一扩散算法。2.模型描述文本中的主题z的分布为P(z)，对于给定的某个主题z，该主题上面的单词概率分布为P(w|z)。我们用P(zi=j)表示生成第i个单词时第j个主题被选中的概率，P(wi|zi=j)表示通过主题j选中单词wi的概率。因此文本中单词的概率分布可以表示为：(12)其中T表示主题数目。为方便起见，令表示单词在主题j上面的多项式分布，表示主题在文本d上面的多项式分布LDA模型采用Dirichlet分布作为多项式分布φ和θ的共轭先验，简化了模型的统计推导，对于T维多项式分布，对应的Dirichlet分布概率密度为：(13)参数称为多项式的超参数，αj可以看作文本中主题j出现次数的先验观测，即在采样文本当中任何一个实际的单词之前就假定主题j已经出现了αj次。为了简化模型，LDA采用了均衡的Dirichlet分布，即令超参数，显然，Dirichlet先验分布通过超参数α能够平滑多项式的分布，防止对数据集产生过度拟合问题。图10LDA模型Fig.10LDAmodel图10是LDA模型的一个图形示意图，超参数α、β分布通过Dirichlet分布Dir(α)、Dir(β)控制主题分布θ和主题上的单词分布φ，θ和φ再共同决定文本中的每个单词w。对于文本d，它的所有已知和潜在变量的联合分布为：定文本中的每个单词w。对于文本d，它的所有已知和潜在变量的联合分布为：(14)消去变量，得到文本的似然值(15)对于整个文本集D，其似然值为：(16)LDA概率主题模型生成文本的过程如下：1.对于每个主题j，根据Dirichlet分布Dir(β)得到该主题上的一个单词多项式分布向量φ(j)2.根据泊松分布Poisson(ξ)得到文本的单词数目N3.根据Dirichlet分布Dir(α)得到该文本的一个主题分布概率向量θ4.对于该文本N个单词中的每一个单词wna)从θ的多项式分布Multinomial(θ)随机选择一个主题kb)从主题k的多项式条件概率分布Multinomial(φ(k))选择一个单词作为wn3.抽取算法LDA模型的关键变量是主题-单词分布φ和文本上的主题分布θ。显然，通过公式(16)运用极大化似然值方法直接求出这些变量的精确值是不现实的。目前抽取LDA模型的方法有变分法（Bleietal，2003）、期望最大化（ExpectationMaximization，EM）（Minkaetal，2002）及Gibbs抽样算法（Griffithsetal，2004）。其中变分法得到的模型与真实情况有所偏差，而EM算法往往由于似然函数的局部最大化问题导致无法找到最优解。