隐含主题分析和大规模机器学习.ppt
隐含主题分析和大规模机器学习,Zhihui JIN 2011-4-26,提纲,什么是 Latent Topic Analysis (LTA) LTA 简史和各种方法比较 LDA 模型介绍 LTA 在目前互联网产品中的应用 实际产品中的 LTA 问题,什么是LTA,从文本相关性中的问题说起： 给定一个短文本（比如query），信息量太少，机器常常误解。 无法从字面（word）上正确判断相关性！,梦想,什么是LTA,短文本信息量不够怎么办？ 使用机器学习技术从大量训练文本中总结知识，帮助理解短文档 “知识”应该是什么样子的？ 表示同一个主题的词聚为一类（topic）；知识=topics 例子： topic 1 = apple, tree, pie, fruit, etc topic 2 = computer, iphone, ipod, apple “apple pie” topic 1: 99%, topic 2: 1% “iphone crack topic 1: 1%, topic 2: 99% “Apple Computer” topic 1: 1%, topic 2: 99% “The apple is ” topic 1: 99%, topic 2: 1%,什么是LTA,LTA的两个功能部件 训练算法（training algorithm）： 输入：训练文档（每个文档是一包词） 输出：模型（topics以及topic和word之间的关系） 训练算法是离线的，挑战在于使用并行计算技术，从海量数据中获得搜索用户可能关注的所有topics。 推演算法（inference algorithm）： 输入1：一个文档（一包词） 输入2：模型 输出：输入文档的意思（和那些topics相关） 推演算法有在线的、也有离线的。在线算法用于理解query；离线算法用于理解文档。挑战在于快速且准确。,什么是LTA,LTA不仅仅能处理文本，只要是一包xx就行 一次购物=一包货品 一个用户=一包浏览记录 一个被点击的URL=一包导致点击的queries 一个mp3文件=一包音频features 一个视频文件=一包视频features LTA在实际互联网产品中的应用 Blog categorization News recommendation Friends suggestion Search matching and ranking Ads targeting,LTA 的发展和方法比较,Latent Semantic Analysis (1990) Singular Value Decomposition Non-negative Matrix Factorization (2005) Probabilistic LSA, PLSA (1999) Noisy-OR Component Analysis (2005) Latent Dirichlet Allocation (2003),Latent Semantic Analysis Term-Document Matrix,Latent Semantic Analysis,LTA 的发展和方法比较,矩阵分解 典型方法： SVD (singular value decomposition) NMF (non-negative matrix factorization) 输入：一个DxV的矩阵M。 D是训练文档的个数，V是词典大小。 Mij=词j在文档i中出现次数 输出：DxK矩阵U: 每个文档和topic的相关度 KxV矩阵V: 每个词和topic的相关度 通常线性投影一个新文档到topic空间，借此理解新文档: t = dTV 问题：投影结果没有物理意义，所以很难选择一个相似度度量 (similarity measure) 来衡量两个文档的相似度。 有人使用点积(sij = titj) ，但是没法说明道理，无法保证效果,Statistical Text Modeling Bag of Words,Documents Terms,proof,induction,object,bouquet,memory,Documents Terms,Documents Topics Terms,proof,induction,object,bouquet,memory,引入 Hidden Topics,什么是 Topic,Topic 是 Vocab 上的概率分布 Hofmann, 1999,Statistical Text Modeling Mixture of Unigrams,所有terms 由同一个topic生成,Statistical Text Modeling Probabilistic Latent Semantic Analysis,proof,induction,object,bouquet,memory,Terms 由不同的 topic 生成,Statistical Text Modeling Probabilistic Latent Semantic Analysis,使用 EM 算法最大化 L 求解模型参数,PLSA 的优缺点,概率模型 输出：P(topic | document) P(word | topic) 因为输出矩阵中是概率，所以可以用度量两个probability distributions 的方法来度量两个文档的相似度： sij = JS P(topic | di); P(topic | dj) 问题：理解新文档很困难：需要把新文档和之前的训练文档放在一起继续训练几个迭代 大规模训练需要几十台几百台计算机并行：inference成本太高 query不断的来，几十台几百台机器也存不下：放弃哪些老文档,Statistical Text Modeling Latent Dirichlet Allocation,Documents Terms,Documents Topics Terms,proof,induction,object,bouquet,memory,proof,induction,object,LDA 文档生成模型,概率计算,参数求解,先验分布选什么 ?,本身是多项分布，一个自然的选择是使用其 共轭分布 Dirichlet 分布,给定数据， 后验分布还是 Dirichlet 分布,联合分布,Gibbs Sampling,如何生成样本符合密度分布,Gibbs Sampling,P(word|topic) P(topic|document),LDA Training via Gibbs Sampling,w,z,w,z,w,z,w,z,w,z,w,z,w,z,w,z,z,z,Doc_1 Doc_n,Step1 : 随机初始化语料库中的每个词的 topic,LDA Training via Gibbs Sampling,w,z,w,z,w,z,w,z,w,z,w,z,w,z,w,z,z,z,Doc_1 Doc_n,Step2 : 重新采样每个topic, 更新模型，直到收敛,z,z,z,LDA Training via Gibbs Sampling,w,z,w,z,w,z,w,z,z,z,Doc_1 Doc_n,Step3 : 输出模型参数 Topic-Word matrix,LDA Inference via Gibbs Sampling,对新来的文档中的词采样 n 次,w,z,w,z,z,Doc_new,P(topic|word),P(topic|document),Parallel LDA Training,文档数量巨大, Map-Reduce,Parallel LDA Training,模型太大了，内存存放不下 1500 * 300,000 * 8B = 3.6GB 模型按 vocab 分片加载, 多次扫描文档,LDA 正确性验证,每张图片是一个 Topic,Size 512 x 512 每个点(i,j)代表一个 term 点的灰度值代表term的频率 所有term权重 normalize 为概率分布,1,2,0.5,0.2,0.3,4,6,4,6,10,2,4,6,文档长度为1000， 生成了共10万篇文档 所有文档使用 LDA 训练，设置 topic 个数为 12 Q： 收敛以后的 topic(图像) 和原始的 topic (图像) 对应吗 ?,20 iteration 50 iteration,LDA 正确性验证,LTA 和其他机器学习方法的结合,有监督(supervised)机器学习系统 二分类器： SETI (logistic regression) 广告、spam fighting, junk mail detection, porn detection, machine translation 多分类器： Pegasos (SVM) 文本（网页、blog、新闻）分类 Taxonomy分类器 CAT 把视频等归入预先定义的树状分类体系中 线性空间变换 PAMIR 将query（文本）投影到图像空间：image search 将图像投影到文本空间：image tagging,Thanks for your attentions!,
