北京9月秋季班贝叶斯PCASVD

北京9月秋季班·机器学习初步极大似然估计、贝叶斯、PCA、SVD邹博2014年9月21日2/42机器学习机器学习比想象中要简单的多举例：kNN用于分类在具体学习机器学习的过程中，往往是因为推导造成的障碍了解基本的高等数学知识是必要的3/42k近邻分类(属于有监督学习)4/42向量间相似度计算的方法欧式距离Pearson相关系数(Pearsoncorrelation)余弦相似度(cosinesimilarity)5/42k-均值聚类(属于无监督学习)创建k个点作为起始质心(如：随机选择起始质心)当任意一个点的簇分配结果发生改变时对数据集中的每个数据点对每个质心计算质心与数据点之间的距离将数据点分配到距其最近的簇对每个簇，计算簇中所有点的均值并作为质心思考：点的簇分配结果发生改变的标准如何判断？实践中可以选择误差的平方和最小为何如此选择？6/42利用SSE进行聚类后处理SSE:SumofSquaredError误差平方和7/42二分k-均值聚类后的结果8/42线性回归y=ax+b9/42多个变量的情形考虑两个变量10/42最小二乘的目标函数m为样本个数，则一个比较“符合常理”的误差函数为：11/42使用极大似然估计解释最小二乘12/42似然函数13/42对数似然14/42计算极大似然函数的最优解15/42最小二乘意义下的参数最优解16/42贝叶斯准则条件概率公式P(x|y)=P(x,y)/P(y)P(x,y)=P(x|y)*P(y)P(y|x)=P(x,y)/P(x)P(x,y)=P(y|x)*P(x)则P(x|y)*P(y)=P(y|x)*P(x)从而：P(x|y)=P(y|x)*P(x)/P(y)分类原则：在给定的条件下，哪种分类发生的概率大，则属于那种分类。17/42朴素贝叶斯的假设一个特征出现的概率，与它相邻的特征没有关系（特征独立性）每个特征同等重要（特征均衡性）18/42以文本分类为例样本：1000封邮件，每个邮件被标记为垃圾邮件或者非垃圾邮件分类目标：给定第1001封邮件，确定它是垃圾邮件还是非垃圾邮件方法：朴素贝叶斯19/42分析类别c：垃圾邮件c1，非垃圾邮件c2词汇表：统计1000封邮件中出现的所有单词，记单词数目为N，即形成词汇表。将每个样本si向量化：初始化N维向量xi，若词wj在si中出现，则xij=1，否则，为0。从而得到1000个N维向量x。使用：P(c|x)=P(x|c)*P(c)/P(x)20/42分解P(c|x)=P(x|c)*P(c)/P(x)P(x|c)=P(x1,x2…xN|c)=P(x1|c)*P(x2|c)…P(xN|c)P(x)=P(x1,x2…xN)=P(x1)*P(x2)…P(xN)带入公式：P(c|x)=P(x|c)*P(c)/P(x)等式右侧各项的含义：P(xi|cj)：在cj(此题目，cj要么为垃圾邮件1，要么为非垃圾邮件0)的前提下，第i个单词xi出现的概率P(xi)：在所有样本中，单词xi出现的概率P(cj)：(垃圾邮件)cj出现的概率21/42关于贝叶斯分类器的若干探讨遇到生词怎么办？拉普拉斯平滑编程的限制：小数乘积怎么办？问题：一个词在样本中出现多次，和一个词在样本中出现一次，形成的词向量相同由0/1改成计数如何判定该分类器的正确率样本中：K个生成分类器，1000-K个作为测试集交叉验证22/42复习：特征值和特征向量方阵A的特征值为λ，特征向量为x，则：Ax=λx取x为单位向量，两边左乘x’，得到x’Ax=λ将单位正交列向量x并排写成矩阵Q，得到Q’AQ=ΣA=QΣQ-1Q是这个矩阵A的特征向量组成的矩阵，Σ是一个对角阵，每一个对角线上的元素就是一个特征值。23/42有趣的推导假定观测到m个样本为a1’,a2’…am’，每个样本有n个维度，即A={ai}(m×n)。向量A*u=(a1’u,a2’u…am’u)’λ=Var(Au)=Σ(ai’u)2=(Au)’Au=u’A’Au左乘uA’Au=λuA’A是A的协方差矩阵，u是A’A的一个特征向量，λ的值的大小表示原始观测数据经在向量u的方向上投影值的方差的大小。实践中，先将A去均值，然后得到A的协方差矩阵以上即为主成分分析PCA的核心推导过程。24/42PCA的两个特征向量25/42PCA的重要应用OBB树OrientedBoundingBoxGIS中的重要应用特征提取数据压缩降维：人脑看电视对原始观测数据A在λ值前k大的特征向量u上投影后，获得一个A(m×n)Q(n×k)的序列，再加上特征向量矩阵Q，即将A原来的m×n个数据压缩到m×k＋k×n个数据。26/42PCA的应用——去噪和冗余利用PCA去噪实质上是对PCA压缩数据的一个还原（图片在下页PPT）。左图是二维原始观测数据，向对原始数据主成分方向（图中虚线方向）投影后，获得1维列向量Au。此时可以看做数据压缩过程。将此1维标量序列重新经u投影回原2维空间，即Auu’。此时得到二维空间的投影分布如右图，可见实际上都分布在一条直线上，此过程可以看做对原数据方差较小方向上的信息丢弃，只保留u方向的信息，这也可以看做一个去噪过程，从数学角度而言去噪势必导致原始信息的自由度的丢失，如右图，虽然分布在一个二维的坐标系上，但实际其只是分布在一个一维的直线上。27/42PCA的重要应用——去噪28/42PCA的重要应用——降维29/42关于特征值的进一步推广若A是m×n阶矩阵，不妨认为mn，则A’A是n×n阶方阵。按照上面的方法，得到：A=UΣV*v是n维列向量，组成方阵V；u是m维向量，组成方阵U。即：奇异值分解SVD30/42SVD的概念奇异值分解（SingularValueDecomposition）是线性代数中一种重要的矩阵分解，是矩阵分析中正规矩阵酉对角化的推广。在信号处理、统计学等领域有重要应用。奇异值分解在某些方面与对称矩阵或Hermite矩阵基于特征向量的对角化类似。然而这两种矩阵分解尽管有其相关性，但还是有明显的不同。奇异值分解可以看做对称方阵在任意矩阵上的推广。突出的、奇特的、非凡的31/42奇异值分解的提法假设A是一个m×n阶矩阵，其中的元素全部属于域K，也就是实数域或复数域。如此则存在一个分解使得A=UΣV*，其中U是m×m阶酉矩阵；Σ是半正定m×n阶对角矩阵；而V*，即V的共轭转置，是n×n阶酉矩阵。这样的分解就称作M的奇异值分解。Σ对角线上的元素Σi,i即为M的奇异值。常见的做法是为了奇异值由大而小排列。如此Σ便能由A唯一确定了。U和V的列分别是A的奇异值的左、右奇异向量32/42SVD举例已知4×5阶实矩阵M，求M的奇异值分解M=UΣV*矩阵Σ的所有非对角元为0。矩阵U和V都是酉矩阵，它们乘上各自的共轭转置都得到单位矩阵。在这个例子中，由于U和V都是实矩阵，故它们都是正交矩阵。33/42U、V的列向量是正交的：正交矩阵34/42奇异值分解不是唯一的由于Σ有一个对角元是零，故这个奇异值分解值不是唯一的。35/42奇异值分解中的U、V矩阵奇异值分解能够用于任意m×n阶矩阵，而特征分解只能适用于特定类型的方阵，故奇异值分解的适用范围更广：M=UΣV*关系式的右边描述了关系式左边的特征值分解：V的列向量（右奇异向量）是M*M的特征向量。U的列向量（左奇异向量）是MM*的特征向量。Σ的非零对角元（非零奇异值）是M*M或者M*M的非零特征值的平方根。36/42直观的解释在矩阵A的奇异值分解中A=UΣV*U的列组成一套对A的正交输入或分析的基向量。这些向量是AA*的特征向量。V的列组成一套对A的正交输出的基向量。这些向量是A*A的特征向量。Σ对角线上的元素是奇异值，可视为是在输入与输出间进行的标量的“膨胀控制”。这些是A*A及AA*的奇异值，并与U和V的行向量相对应。37/42SVD四个矩阵的大小关系实际中，往往只保留Σ前k个较大的数38/42求伪逆奇异值分解可以被用来计算矩阵的伪逆。若矩阵A的奇异值分解为A=UΣV*，那么A的伪逆为A+=VΣ+U*其中Σ+是Σ的伪逆，是将主对角线上每个非零元素都求倒数之后再转置得到的。求伪逆通常可以用来求解最小二乘法问题。39/42广义逆矩阵（伪逆）若A为非奇异矩阵,则线性方程组Ax=b的解为x=A^(-1)b，其中A的A的逆矩阵A^(-1)满足A^(-1)A=AA^(-1)=I(I为单位矩阵)。若A是奇异阵或长方阵,x=A+b。A+叫做A的伪逆阵。1955年R.彭罗斯证明了对每个m×n阶矩阵A,都存在惟一的n×m阶矩阵X，满足：①AXA=A；②XAX=X；③(AX)*＝I；④(XA)*＝I。通常称X为A的穆尔-彭罗斯广义逆矩阵,简称M-P逆，记作A+。在矛盾线性方程组Ax＝b的最小二乘解中,x=A+b是范数最小的一个解。统一前文使用极大似然得到的公式：40/42隐形语义索引LSI利用SVD方法的信息检索被成为隐形语义索引（LatentSemanticIndexing，LSI）或隐形语义分析（LatentSemanticAnalysis，LSA）。在LSI中，一个矩阵由文档和词语组成。当在该矩阵上应用SVD时，就会构建出多个奇异值。这些奇异值代表了文档中的概念(主题)，这一特点可以用于高效的文档搜索。同义词的查找：在千篇相似文档中抽取出概念，那么，相似词就可以影射为同一个概念。比simHash更具有智能化意义。41/42参考文献Prof.AndrewNg,MachineLearning,StanfordUniversity,2003PeterHarrington著，李锐，李鹏，曲亚东等译，人民邮电出版社，2013年6月HansWackernagel,PrincipalComponentAnalysisforautocorrelateddata:ageostatisticalperspecitve,August,1998(PCA)MiaHubert,PeterJ.Rousseeuw,KarlienVandenBranden,ROBPCA:aNewApproachtoRobustPrincipalComponentAnalysis,October27,2003(PCA)(SVM)(Bayes)(机器学习)(SVD)(广义逆矩阵)(SVD)(SVD)42/42感谢大家！恳请大家批评指正！