PEGASUS - A Peta-Scale Graph Mining System Implementation and Observations
Summary:
作者提出了一個GIM-V(Generalized Iterated Matrix-Vector Multiplication)的架構，擁有以下特性:
1. 可以在多台機器上來平行運算。
2. 提出了一個加速的方法，可以擁有比同樣架構non-optimized的情況下快五倍的運算速度。
3. 對於graph中的edge有linear running time。
GIM-V其演算法的核心想法如下，他把一個M x v = v’的矩陣相乘式分成三個operation:
(1) combine2: mij和vj相乘。
(2) combineAll:將n個在combine2相乘出來的結果(for node i)給相加起來。
(3) assign:將算好的vi’指定回原來的vi向量中。
而這個架構可以拆成一個兩個stage的工作，每個stage分別都是可以套入map-reduce的架構之中。這樣就可以用多台機器去平行處理一個矩陣乘法的工作。而此一架構，不只能夠解矩陣的乘法，還可以套用到如page-rank、random walk with restart、diameter estimation和connected component上。
將上述方法直接套用起來的話，就是文中所提到的GIM-V BASE版本，而之後作者提出了加速的一些版本，如GIM-V BL:以一個個bolck為基準，將矩陣M分解成一個N*N個b*b的小block，再把v分解成N個b維的向量，這樣就可將HADOOP中的主要瓶頸(shuffling stage where network transfer, sorting)給降低。而在資料壓縮的部分，因為透過這種方式可以將原本矩陣中每個元素都需要兩個4byte整數來儲存其位置，改由只要儲存block所在的位置就好，裡面每個元素總共只需要利用2xlogb的bit數來儲存，故在壓縮上效果也不錯。另外如GIM-V CL:他會先對矩陣M去作clustering，使得元素擺放的位置可以建構出一個擁有最多zero-block的M，如此一來由於全零的block不需要加入運算，就可以達到加速和資料壓縮的效果。還有GIM-V DI，像在找connected component的HCC演算法中，可以利用在一個block中先作多次處理的方式，使得最後須要運算的次數就變少了(即不需要多花時間在多次的map和reduce上)。
而作者在實驗的部分，也針對了現有的資料去作分析，即對wikipedia和yahoo的網頁等等去作分析，都可以對超大規模的資料去作處理。
Comment:
作者提出的架構雖然是在HADOOP架構上用map reduce的方法在多台機器上跑large scale data的處理，尤其是在矩陣運算上的有顯著的效果。此一架構說不定可以轉換至CUDA的平行運算上，雖然在個人電腦上可能不需要用到如此large-scale的處理，但是有些需要矩陣運算的功能可能會有要real-time處理的需求，應該可以組成另外一種不同方式的應用。
2011年5月14日 星期六
Building a high-level dataflow system on top of Map-Reduce the Pig experience
Summary:
作者們在這篇中提出了一個簡單、且明確的dataflow的programming model。Pig這個model是一個high-level dataflow system，其切中了一個介於SQL和map-reduce之間的甜蜜點。其擁有類似SQL的high-level data manipulation，而靠此特性可以整合成有明確的dataflow客制化map和reduce function。
而由於map-reduce簡單的特性，會導致以下的問題:
1. 沒有辦法直接的去support N-step dataflow, 但這個需求在實際上卻很常見。
2. Map-reduce也缺少了給予combined processing of multiple datasets一個明確的support。
3. 一些需要頻繁的去抓取data的運作，像是filter、aggregation、top-k thresholding等等都必須要用人工去coding。
以上的問題會導致data analysis的速度，也會造成某些錯誤，或是使得data processing program變得難以閱讀。
作者提供了一個有著SQL精神的可組合式高階data manipulation constructs，同時又保留了map-reduce某些吸引人的特性，提出了Pig這個系統。
而在performance的部分，作者也提出了和map-reduce比較的數據，目前是需花費較純粹map-reduce多出50%的運算時間，但是這個可以視為一個介於code development/maintenance effort和執行時間之間的取捨。
作者們在這篇中提出了一個簡單、且明確的dataflow的programming model。Pig這個model是一個high-level dataflow system，其切中了一個介於SQL和map-reduce之間的甜蜜點。其擁有類似SQL的high-level data manipulation，而靠此特性可以整合成有明確的dataflow客制化map和reduce function。
而由於map-reduce簡單的特性，會導致以下的問題:
1. 沒有辦法直接的去support N-step dataflow, 但這個需求在實際上卻很常見。
2. Map-reduce也缺少了給予combined processing of multiple datasets一個明確的support。
3. 一些需要頻繁的去抓取data的運作，像是filter、aggregation、top-k thresholding等等都必須要用人工去coding。
以上的問題會導致data analysis的速度，也會造成某些錯誤，或是使得data processing program變得難以閱讀。
作者提供了一個有著SQL精神的可組合式高階data manipulation constructs，同時又保留了map-reduce某些吸引人的特性，提出了Pig這個系統。
而在performance的部分，作者也提出了和map-reduce比較的數據，目前是需花費較純粹map-reduce多出50%的運算時間，但是這個可以視為一個介於code development/maintenance effort和執行時間之間的取捨。
2011年5月4日 星期三
Describable Visual Attributes for Face Verification and Image Search
Summary:
作者提出了一個利用attribute的classifier來作有關face verification的方法，並可以用這個方法拓展到face search等應用，其作法如下:
利用OKAO face detector可以將網路上取得的圖片作處理，可以將臉的角度、眼和嘴的角給抽取出來，之後再利用Amazon Mturk來作一個媒合指定labeling的工作，如此一來就可將每張圖的attribute給選定出來。
作者將臉部定義出10個region，包含1個全臉的區域及9個子區域，並在每個region中抽取中low level feature，而feature則是利用不同的pixel value types；不同的normalization方法；與不同的aggregation方式來湊出不同種類的feature。有了這些feature之後，作者使用了一個forward feature selection的方式，將每個不同的attribute classifier給train出來，使用的是RBF kernel的SVM，給定每個attribute 500個positive example和2000個negative example就可將所需的classifier給train好了。文中也呈現了其產生的數據，在73個attribute classifier中都有很好的正確率。
作者還提出了一個simile classifier的作法，是將一個人的10個區域給選出來之後，透過和上方所提的training方式相同選出最適合的8個區域與6種feature type，對於每個人共train出48個classifier。
有了以上這些資料之後，給定兩張input image，先經過face & fiducial detector，再經過一個affine alignment，之後再利用上述兩種classifier就可算出一連串的output，比對那些output就可以決定這兩張input image所指出的是不是同一個人了。
因為training的過程中所標記的其實是一個個attribute，每個attribute都是具有實際上的意義的，如亞洲人、高加索人、黑髮、金髮等等，故可以在image search上作為一個很好的輔助。再輸入一個query如:”dark-haired people with sunglass”就可以透過” dark-haired”和”sunglass”找出很符合要求的照片了，在此一架構下，搜尋的方式便很直覺的變成了我們平常要找東西時習慣用文字來描述的概念。
Comment:
這篇提出了一個很好的方法去做face verification和image search的工作。很重要的一個貢獻他不像LBP那樣每個特定的feature其實並不知道實際上有什麼意義，而在此的classifier所選定出來的feature代表的即是一個特定attribute，相較起來跟人類的想法較為接近。
作者提出了一個利用attribute的classifier來作有關face verification的方法，並可以用這個方法拓展到face search等應用，其作法如下:
利用OKAO face detector可以將網路上取得的圖片作處理，可以將臉的角度、眼和嘴的角給抽取出來，之後再利用Amazon Mturk來作一個媒合指定labeling的工作，如此一來就可將每張圖的attribute給選定出來。
作者將臉部定義出10個region，包含1個全臉的區域及9個子區域，並在每個region中抽取中low level feature，而feature則是利用不同的pixel value types；不同的normalization方法；與不同的aggregation方式來湊出不同種類的feature。有了這些feature之後，作者使用了一個forward feature selection的方式，將每個不同的attribute classifier給train出來，使用的是RBF kernel的SVM，給定每個attribute 500個positive example和2000個negative example就可將所需的classifier給train好了。文中也呈現了其產生的數據，在73個attribute classifier中都有很好的正確率。
作者還提出了一個simile classifier的作法，是將一個人的10個區域給選出來之後，透過和上方所提的training方式相同選出最適合的8個區域與6種feature type，對於每個人共train出48個classifier。
有了以上這些資料之後，給定兩張input image，先經過face & fiducial detector，再經過一個affine alignment，之後再利用上述兩種classifier就可算出一連串的output，比對那些output就可以決定這兩張input image所指出的是不是同一個人了。
因為training的過程中所標記的其實是一個個attribute，每個attribute都是具有實際上的意義的，如亞洲人、高加索人、黑髮、金髮等等，故可以在image search上作為一個很好的輔助。再輸入一個query如:”dark-haired people with sunglass”就可以透過” dark-haired”和”sunglass”找出很符合要求的照片了，在此一架構下，搜尋的方式便很直覺的變成了我們平常要找東西時習慣用文字來描述的概念。
Comment:
這篇提出了一個很好的方法去做face verification和image search的工作。很重要的一個貢獻他不像LBP那樣每個特定的feature其實並不知道實際上有什麼意義，而在此的classifier所選定出來的feature代表的即是一個特定attribute，相較起來跟人類的想法較為接近。
2011年4月27日 星期三
Learning to rank - from pairwise approach to listwise approach
Learning to rank - from pairwise approach to listwise approach
Summary:
作者使用了一個新的概念來定義ranking的這個問題，本來使用的方法都是用pairwise的方式，例如上次指定的SVR中定義兩個input的feature的差來當作一個classifier的input之類，都是一次處理兩個sample的方式。但是這篇使用了一個使用list的方式來處理，其方法如下。
首先，對應到一個query時，每一個原有的document都會有一個相對關係的答案值(y)，而此時作者定義將一個query和一個document視為一個feature vector x，經過一個ranking function f(.)後，可以得到一個值f(x)，對應到一個query時會列出一堆document而產生一個list of score (x)，而將這個z和原來給定的y透過一個listwise loss function來計算後，就可以算出這個z作ranking的效果了。
而要如何定義這個listwise loss function呢? 作者先定義了一個permutation probability，這一個permutation probability可以計算出一組排列的機率值，由於其定義的方式，使得在score較大要排在較前方，score較小的要排在較後面，如此會得到一個較高的機率值。透過此一function，就可以比較不同排列組合下的好壞之分。但是因為要計算出全部的排列組合數將是一個O(n!)的問題，在實際上是可個不太可行的作法，作者又定義了另外一個function叫作top k probability，只會對排在前面K個順序的object來作計算，而在經過一些計算上的轉換，這個top k probability就可以很有效率的被計算出來。
有了這些function之後，作者就定義listwise loss function為兩個機率分布間的cross entropy，也就是L(y,z)=-ΣPy*log(Pz)。
有了這個listwise loss function，作者便利用neural network作為model，gradient descent當作optimization的方法，來達到learning的效果，並稱此方法為ListNet。有趣的一點是，當每個query對應到的document只有2個的時候，其實這個方法就等同於RankNet了!不過在之後的實驗部分，作者也證明了以listwise的方法去作ranking其實效果會優於pairwise所作出來的效果。
Summary:
作者使用了一個新的概念來定義ranking的這個問題，本來使用的方法都是用pairwise的方式，例如上次指定的SVR中定義兩個input的feature的差來當作一個classifier的input之類，都是一次處理兩個sample的方式。但是這篇使用了一個使用list的方式來處理，其方法如下。
首先，對應到一個query時，每一個原有的document都會有一個相對關係的答案值(y)，而此時作者定義將一個query和一個document視為一個feature vector x，經過一個ranking function f(.)後，可以得到一個值f(x)，對應到一個query時會列出一堆document而產生一個list of score (x)，而將這個z和原來給定的y透過一個listwise loss function來計算後，就可以算出這個z作ranking的效果了。
而要如何定義這個listwise loss function呢? 作者先定義了一個permutation probability，這一個permutation probability可以計算出一組排列的機率值，由於其定義的方式，使得在score較大要排在較前方，score較小的要排在較後面，如此會得到一個較高的機率值。透過此一function，就可以比較不同排列組合下的好壞之分。但是因為要計算出全部的排列組合數將是一個O(n!)的問題，在實際上是可個不太可行的作法，作者又定義了另外一個function叫作top k probability，只會對排在前面K個順序的object來作計算，而在經過一些計算上的轉換，這個top k probability就可以很有效率的被計算出來。
有了這些function之後，作者就定義listwise loss function為兩個機率分布間的cross entropy，也就是L(y,z)=-ΣPy*log(Pz)。
有了這個listwise loss function，作者便利用neural network作為model，gradient descent當作optimization的方法，來達到learning的效果，並稱此方法為ListNet。有趣的一點是，當每個query對應到的document只有2個的時候，其實這個方法就等同於RankNet了!不過在之後的實驗部分，作者也證明了以listwise的方法去作ranking其實效果會優於pairwise所作出來的效果。
2011年4月19日 星期二
Support vector learning for ordinal regression
Summary:
作者提出了一個distribution independent model來解ordinal regression的問題，而這個方法則是建立在一個針對pair of ranks的loss function上。
其核心的想法如下: 假設給定一組sample( S={(xi,yi)}, i=1,…,l)，也就是共有l個data，每個data對應到一個n-D的feature vector(xi)和一個rank值(yi)。作者想要找到的是一個合適的mapping h，使得empirical risk (Remp(h;S)) 最小化。
透過paper中的定理2，利用一個linear function U(x) = w_T*x可將feature vector投影到一個實數值，且這個實數值一定會落在某個rank投影在此實數空間的區間([Θ(r_i-1), Θ(r_i)])之內。推導至(9)式時，再導入了一個degree of violation constraint(ζ)，而使得margin最大的那個解w，可以轉換成求||w||^2+C*Σζ的解。而這個解w則是透過Lagrangian multiplier轉成了另外一個dual problem(式(10))去解α，之後再透過式(11)經由α回推w之最佳解。此外，透過式(12)還證明了每個rank和rank間的optimal threshold就是兩個rank中距離最近的兩點之中間值。求得了這些rank boundaries，如果有新的data要進來排序時，就可透過U(x)將其對應到一實數值，再看此值落在哪個rank的區間內，就可以得到分類的效果了。
作者提出了一個ordinal regression的問題其實對應到一個unique preference learning problem on pairs of object，如此一來就可將ordinal regression和對pairs of objects的classification problem給連結在一起了。
Critiques:
這篇提出了一個可以利用一小筆的training data，來建立出一個將n維的feature vector投影到一個實數軸上的線性轉換，並盡量保留住原有的分類方式，並透過此一線性轉換來對unseen data也能作ranking的動作，但其實此一方法有一個缺點，如同之前manifold learning相關文獻中所提到的，如果今天data的分布是像三維空間中瑞士捲般的分布，假設瑞士捲越內部的部分其rank越高，但由於本篇採用的是linear function U: X→R，對於非線性分布的資料可能就不會有如同在paper中Fig.1般那麼好的實驗結果。實際上平常在作的許多應用應該都是對一個高維度的非線性分布來作實驗及處理，因此對於非線性分布的ranking問題可能還需要用其他的方法來解決。
作者提出了一個distribution independent model來解ordinal regression的問題，而這個方法則是建立在一個針對pair of ranks的loss function上。
其核心的想法如下: 假設給定一組sample( S={(xi,yi)}, i=1,…,l)，也就是共有l個data，每個data對應到一個n-D的feature vector(xi)和一個rank值(yi)。作者想要找到的是一個合適的mapping h，使得empirical risk (Remp(h;S)) 最小化。
透過paper中的定理2，利用一個linear function U(x) = w_T*x可將feature vector投影到一個實數值，且這個實數值一定會落在某個rank投影在此實數空間的區間([Θ(r_i-1), Θ(r_i)])之內。推導至(9)式時，再導入了一個degree of violation constraint(ζ)，而使得margin最大的那個解w，可以轉換成求||w||^2+C*Σζ的解。而這個解w則是透過Lagrangian multiplier轉成了另外一個dual problem(式(10))去解α，之後再透過式(11)經由α回推w之最佳解。此外，透過式(12)還證明了每個rank和rank間的optimal threshold就是兩個rank中距離最近的兩點之中間值。求得了這些rank boundaries，如果有新的data要進來排序時，就可透過U(x)將其對應到一實數值，再看此值落在哪個rank的區間內，就可以得到分類的效果了。
作者提出了一個ordinal regression的問題其實對應到一個unique preference learning problem on pairs of object，如此一來就可將ordinal regression和對pairs of objects的classification problem給連結在一起了。
Critiques:
這篇提出了一個可以利用一小筆的training data，來建立出一個將n維的feature vector投影到一個實數軸上的線性轉換，並盡量保留住原有的分類方式，並透過此一線性轉換來對unseen data也能作ranking的動作，但其實此一方法有一個缺點，如同之前manifold learning相關文獻中所提到的，如果今天data的分布是像三維空間中瑞士捲般的分布，假設瑞士捲越內部的部分其rank越高，但由於本篇採用的是linear function U: X→R，對於非線性分布的資料可能就不會有如同在paper中Fig.1般那麼好的實驗結果。實際上平常在作的許多應用應該都是對一個高維度的非線性分布來作實驗及處理，因此對於非線性分布的ranking問題可能還需要用其他的方法來解決。
2011年4月6日 星期三
Manifold Methods
Nonlinear dimensionality reduction by locally linear embedding
Summary:
作者提出了一個利用locally linear embedding的方式，透過保存local geometry的方式，將data point投影到一個比原來維度D還低的d維度空間上，就可以做到nonlinear dimensionality reduction的效果。
其作法如下:
1. 對於每個data point(Xi)，找出最接近此點的K個nearest point，找出一組係數Wij，使得Σj|Wij| = 1且讓cost function:Σi|Xi - ΣjWijXj |^2極小化。
2. 有了這組linear weights之後，接下來要解如何將D維的Xi投影到d維的Yi上，其cost function為Σi|Yi - ΣjWijYj |^2，可將其視為一個解NxN的eigenvalue problem，就可得到符合cost minimization的解。
作者還用此方法對著臉的照片以及word-document count去作實驗，也證明了此種方法可以將臉的表情變換投影到一個二維的low dimension座標系上的轉換，並且可在轉換路徑上看到表情的逐漸變換；而在文字上作實驗的結果上來看，也可以看出此方法成功的將意義相關的字投影到距離較短的分布上。
Critiques:
這篇提到了利用LLE作nonlinear dimensionality reduction的方法，而最近由於本身研究的關係，看到了一些作spectral clustering的方法，其方法也是類似利用affinity matrix(對graph中每個vertex都有連結或是類似bilateral filter的限制來建立)，再對此一個affinity matrix去求其eigevector的解，而對前幾大的eigenvalue對應到的eigenvector值去作K-means clustering就可做到分群的效果，此一方法也是可以做到manifold dimensionality reduction的效果。此外，在 “Diffusion Maps and Coarse-Graining: A Unified Framework for Dimensionality Reduction, Graph Partitioning, and Data Set Parameterization’’. IEEE Trans. on Pattern Analysis and Machine Intelligence(2006). 中還提到了如何利用diffusion map來作有關分群、降維的動作，有興趣的人可以參考一下。
Summary:
作者提出了一個利用locally linear embedding的方式，透過保存local geometry的方式，將data point投影到一個比原來維度D還低的d維度空間上，就可以做到nonlinear dimensionality reduction的效果。
其作法如下:
1. 對於每個data point(Xi)，找出最接近此點的K個nearest point，找出一組係數Wij，使得Σj|Wij| = 1且讓cost function:Σi|Xi - ΣjWijXj |^2極小化。
2. 有了這組linear weights之後，接下來要解如何將D維的Xi投影到d維的Yi上，其cost function為Σi|Yi - ΣjWijYj |^2，可將其視為一個解NxN的eigenvalue problem，就可得到符合cost minimization的解。
作者還用此方法對著臉的照片以及word-document count去作實驗，也證明了此種方法可以將臉的表情變換投影到一個二維的low dimension座標系上的轉換，並且可在轉換路徑上看到表情的逐漸變換；而在文字上作實驗的結果上來看，也可以看出此方法成功的將意義相關的字投影到距離較短的分布上。
Critiques:
這篇提到了利用LLE作nonlinear dimensionality reduction的方法，而最近由於本身研究的關係，看到了一些作spectral clustering的方法，其方法也是類似利用affinity matrix(對graph中每個vertex都有連結或是類似bilateral filter的限制來建立)，再對此一個affinity matrix去求其eigevector的解，而對前幾大的eigenvalue對應到的eigenvector值去作K-means clustering就可做到分群的效果，此一方法也是可以做到manifold dimensionality reduction的效果。此外，在 “Diffusion Maps and Coarse-Graining: A Unified Framework for Dimensionality Reduction, Graph Partitioning, and Data Set Parameterization’’. IEEE Trans. on Pattern Analysis and Machine Intelligence(2006). 中還提到了如何利用diffusion map來作有關分群、降維的動作，有興趣的人可以參考一下。
2011年3月23日 星期三
Latent Semantic Analysis
Probabilistic latent semantic indexing
Summary:
在PLSA之前，有人提出了用的SVD方法來作latent semantic indexing的動作，而本篇作者用一個較有統計基礎的機率模型(aspect model)來模擬，這個模型是以likelihood來產生一個對training data的generative model。
其實aspect model也就是一個建立在兩個假設上的一種statistical mixture model。第一個假設為，觀察到的document和word是獨立的。第二個假設則為，latent z和word w的關係，和document d是沒有相關的。如此一來就可以將N個document的檔案，降維到一個含有K個latent的關係上，而K個latent(z)就可以拿來在給定條件d的情況下預測w。
而作者利用likelihood principle，希望能求出L = ∑d ∑w [n(d,w)logP(d,w)]的最大值，其中n(d,w)是term frequency，P(d,w)= ∑z P(z)P(w|z)P(d|z)。在這裡使用的方法是EM algorithm:
Step E: Hidden parameters (posterior)將被估計，也就是計算出P(z|d,w)。
Step M: 建立在已經觀測到的部分，進行parameter estimation。
如此EM的過程將持續進行，直到上方的L值收斂為止，就可建出這個模型。
而在PLSA中，作者為了避免over-fitting的問題，還加入了一個beta控制項來修改EM，這個方式稱為Tempered EM。Beta在一開始被指定為1，之後漸漸減少，利用held-out data來測試目前beta的效果，如果沒有辦法透過減少beta繼續改善的話就停止這個遞迴的過程，定為收斂。
Critiques:
雖然在本篇paper中後面對text作了一些測試效果很好，但是在其一開始的假設上，提出document和word是independent的概念，在實際運用上是否真的成立仍是一個問題。另外，在LDA那篇paper中也提到了，PLSA雖然不像unigram的方法在perplexity上會有很大的問題，但相對LDA的方法而言，其perplexity還是增加的較快。
------------------------------------------------------------
Latent dirichlet allocation
Summary:
在之前所提到的PLSI(PLSA)中把每個文件表示成一個數字的list(semantic topics的組合)，但是沒有一個用機率來表示的模型，會衍生出兩個問題:
(1) 參數的數量會因為corpus的量增加而線性增加，造成一個overfitting的問題。
(2) 無法去對不在traing data中出現過的document去assign機率。
因此，作者提出了LDA這個方法，希望能找出一個機率模型，不只能assign機給在已經看過的member of corpus，也能對其他類似的document給定一個機率。
其和PLSA不同之處在於，LDA利用了一個k維的Dirichlet random variable來取代原來在PLSA中的d(document)，而這個Dirichlet random variable還擁有finite dimensional sufficient statistics的特性，且conjugate to multinomial distribution，這對於作者後來在推導和參數估計的地方有很大的幫助。
而LDA也做到了一個降低參數維度的動作，原來的PLSA要在對k個semantic topic，V個word，N個document設定共k*V+k*M個參數；而LDA只要設定k(alpha的參數)+k*V(beta的參數)就好了。
LDA的架構是一個包含了三個level的hierarchical model，在corpus level有alpha和beta參數，只需要在產生corpus的時候sample一次。而theta則是document-level variable，需要在每個document中sample一次。最後一層則是word level，這裡面的變數則需要在每個document的每個word中都要sample一次。
而在paper後半部的實驗中也展現出了LDA在對於沒有看過的document中還是可以有很好的效果。此外，其在perplexity的表現上，由於PLSI在每個document給定對於每個z給定一個值，但當有些z沒有出現在此document中，導致到某些特定字在估計時機率很小，就會讓perplexity上升很快。但在LDA中就不會有這個問題。
Conclusion:
本周這兩篇paper大概是從開學以來aMMAI指定閱讀裡面讀起來最難的了，就算多看了一遍，其中還是有許多數學的部分不太理解，可能是之前對於機率模型的部分理解的不夠透徹。目前也只有在概念上稍為理解作者們的想法，希望在明天上完課後能夠更通透一些。
補充:
在網路上搜尋一些相關資料的時候，發現了一個有關PLSA的公式推導的網站，寫的還滿詳細的，有興趣的朋友們可以參考一下:
http://www.hongliangjie.com/2010/01/04/notes-on-probabilistic-latent-semantic-analysis-plsa/
Summary:
在PLSA之前，有人提出了用的SVD方法來作latent semantic indexing的動作，而本篇作者用一個較有統計基礎的機率模型(aspect model)來模擬，這個模型是以likelihood來產生一個對training data的generative model。
其實aspect model也就是一個建立在兩個假設上的一種statistical mixture model。第一個假設為，觀察到的document和word是獨立的。第二個假設則為，latent z和word w的關係，和document d是沒有相關的。如此一來就可以將N個document的檔案，降維到一個含有K個latent的關係上，而K個latent(z)就可以拿來在給定條件d的情況下預測w。
而作者利用likelihood principle，希望能求出L = ∑d ∑w [n(d,w)logP(d,w)]的最大值，其中n(d,w)是term frequency，P(d,w)= ∑z P(z)P(w|z)P(d|z)。在這裡使用的方法是EM algorithm:
Step E: Hidden parameters (posterior)將被估計，也就是計算出P(z|d,w)。
Step M: 建立在已經觀測到的部分，進行parameter estimation。
如此EM的過程將持續進行，直到上方的L值收斂為止，就可建出這個模型。
而在PLSA中，作者為了避免over-fitting的問題，還加入了一個beta控制項來修改EM，這個方式稱為Tempered EM。Beta在一開始被指定為1，之後漸漸減少，利用held-out data來測試目前beta的效果，如果沒有辦法透過減少beta繼續改善的話就停止這個遞迴的過程，定為收斂。
Critiques:
雖然在本篇paper中後面對text作了一些測試效果很好，但是在其一開始的假設上，提出document和word是independent的概念，在實際運用上是否真的成立仍是一個問題。另外，在LDA那篇paper中也提到了，PLSA雖然不像unigram的方法在perplexity上會有很大的問題，但相對LDA的方法而言，其perplexity還是增加的較快。
------------------------------------------------------------
Latent dirichlet allocation
Summary:
在之前所提到的PLSI(PLSA)中把每個文件表示成一個數字的list(semantic topics的組合)，但是沒有一個用機率來表示的模型，會衍生出兩個問題:
(1) 參數的數量會因為corpus的量增加而線性增加，造成一個overfitting的問題。
(2) 無法去對不在traing data中出現過的document去assign機率。
因此，作者提出了LDA這個方法，希望能找出一個機率模型，不只能assign機給在已經看過的member of corpus，也能對其他類似的document給定一個機率。
其和PLSA不同之處在於，LDA利用了一個k維的Dirichlet random variable來取代原來在PLSA中的d(document)，而這個Dirichlet random variable還擁有finite dimensional sufficient statistics的特性，且conjugate to multinomial distribution，這對於作者後來在推導和參數估計的地方有很大的幫助。
而LDA也做到了一個降低參數維度的動作，原來的PLSA要在對k個semantic topic，V個word，N個document設定共k*V+k*M個參數；而LDA只要設定k(alpha的參數)+k*V(beta的參數)就好了。
LDA的架構是一個包含了三個level的hierarchical model，在corpus level有alpha和beta參數，只需要在產生corpus的時候sample一次。而theta則是document-level variable，需要在每個document中sample一次。最後一層則是word level，這裡面的變數則需要在每個document的每個word中都要sample一次。
而在paper後半部的實驗中也展現出了LDA在對於沒有看過的document中還是可以有很好的效果。此外，其在perplexity的表現上，由於PLSI在每個document給定對於每個z給定一個值，但當有些z沒有出現在此document中，導致到某些特定字在估計時機率很小，就會讓perplexity上升很快。但在LDA中就不會有這個問題。
Conclusion:
本周這兩篇paper大概是從開學以來aMMAI指定閱讀裡面讀起來最難的了，就算多看了一遍，其中還是有許多數學的部分不太理解，可能是之前對於機率模型的部分理解的不夠透徹。目前也只有在概念上稍為理解作者們的想法，希望在明天上完課後能夠更通透一些。
補充:
在網路上搜尋一些相關資料的時候，發現了一個有關PLSA的公式推導的網站，寫的還滿詳細的，有興趣的朋友們可以參考一下:
http://www.hongliangjie.com/2010/01/04/notes-on-probabilistic-latent-semantic-analysis-plsa/
訂閱：
文章 (Atom)