隱含主題分析和大規(guī)模機(jī)器學(xué)習(xí).ppt

隱含主題分析和大規(guī)模機(jī)器學(xué)習(xí),Zhihui JIN 2011-4-26,提綱,什么是 Latent Topic Analysis (LTA) LTA 簡史和各種方法比較 LDA 模型介紹 LTA 在目前互聯(lián)網(wǎng)產(chǎn)品中的應(yīng)用 實際產(chǎn)品中的 LTA 問題,什么是LTA,從文本相關(guān)性中的問題說起： 給定一個短文本（比如query），信息量太少，機(jī)器常常誤解。 無法從字面（word）上正確判斷相關(guān)性！,夢想,什么是LTA,短文本信息量不夠怎么辦？ 使用機(jī)器學(xué)習(xí)技術(shù)從大量訓(xùn)練文本中總結(jié)知識，幫助理解短文檔 “知識”應(yīng)該是什么樣子的？ 表示同一個主題的詞聚為一類（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的兩個功能部件 訓(xùn)練算法（training algorithm）： 輸入：訓(xùn)練文檔（每個文檔是一包詞） 輸出：模型（topics以及topic和word之間的關(guān)系） 訓(xùn)練算法是離線的，挑戰(zhàn)在于使用并行計算技術(shù)，從海量數(shù)據(jù)中獲得搜索用戶可能關(guān)注的所有topics。 推演算法（inference algorithm）： 輸入1：一個文檔（一包詞） 輸入2：模型 輸出：輸入文檔的意思（和那些topics相關(guān)） 推演算法有在線的、也有離線的。在線算法用于理解query；離線算法用于理解文檔。挑戰(zhàn)在于快速且準(zhǔn)確。,什么是LTA,LTA不僅僅能處理文本，只要是一包xx就行 一次購物=一包貨品 一個用戶=一包瀏覽記錄 一個被點擊的URL=一包導(dǎo)致點擊的queries 一個mp3文件=一包音頻features 一個視頻文件=一包視頻features LTA在實際互聯(lián)網(wǎng)產(chǎn)品中的應(yīng)用 Blog categorization News recommendation Friends suggestion Search matching and ranking Ads targeting,LTA 的發(fā)展和方法比較,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 的發(fā)展和方法比較,矩陣分解 典型方法： SVD (singular value decomposition) NMF (non-negative matrix factorization) 輸入：一個DxV的矩陣M。 D是訓(xùn)練文檔的個數(shù)，V是詞典大小。 Mij=詞j在文檔i中出現(xiàn)次數(shù) 輸出：DxK矩陣U: 每個文檔和topic的相關(guān)度 KxV矩陣V: 每個詞和topic的相關(guān)度 通常線性投影一個新文檔到topic空間，借此理解新文檔: t = dTV 問題：投影結(jié)果沒有物理意義，所以很難選擇一個相似度度量 (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 求解模型參數(shù),PLSA 的優(yōu)缺點,概率模型 輸出：P(topic | document) P(word | topic) 因為輸出矩陣中是概率，所以可以用度量兩個probability distributions 的方法來度量兩個文檔的相似度： sij = JS P(topic | di); P(topic | dj) 問題：理解新文檔很困難：需要把新文檔和之前的訓(xùn)練文檔放在一起繼續(xù)訓(xùn)練幾個迭代 大規(guī)模訓(xùn)練需要幾十臺幾百臺計算機(jī)并行：inference成本太高 query不斷的來，幾十臺幾百臺機(jī)器也存不下：放棄哪些老文檔,Statistical Text Modeling Latent Dirichlet Allocation,Documents Terms,Documents Topics Terms,proof,induction,object,bouquet,memory,proof,induction,object,LDA 文檔生成模型,概率計算,參數(shù)求解,先驗分布選什么 ?,本身是多項分布，一個自然的選擇是使用其 共軛分布 Dirichlet 分布,給定數(shù)據(jù)， 后驗分布還是 Dirichlet 分布,聯(lián)合分布,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 : 隨機(jī)初始化語料庫中的每個詞的 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 : 輸出模型參數(shù) 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,文檔數(shù)量巨大, Map-Reduce,Parallel LDA Training,模型太大了，內(nèi)存存放不下 1500 * 300,000 * 8B = 3.6GB 模型按 vocab 分片加載, 多次掃描文檔,LDA 正確性驗證,每張圖片是一個 Topic,Size 512 x 512 每個點(i,j)代表一個 term 點的灰度值代表term的頻率 所有term權(quán)重 normalize 為概率分布,1,2,0.5,0.2,0.3,4,6,4,6,10,2,4,6,文檔長度為1000， 生成了共10萬篇文檔 所有文檔使用 LDA 訓(xùn)練，設(shè)置 topic 個數(shù)為 12 Q： 收斂以后的 topic(圖像) 和原始的 topic (圖像) 對應(yīng)嗎 ?,20 iteration 50 iteration,LDA 正確性驗證,LTA 和其他機(jī)器學(xué)習(xí)方法的結(jié)合,有監(jiān)督(supervised)機(jī)器學(xué)習(xí)系統(tǒng) 二分類器： SETI (logistic regression) 廣告、spam fighting, junk mail detection, porn detecti