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/

Lost in Binarization : Query-Adaptive Ranking for Similar Image Search with Compact Codes

Lost in Binarization : Query-Adaptive Ranking for Similar Image Search with Compact Codes

Summary:
本篇作者為了改進Hamming Distance會有很多vector pair會共享同樣的distance，但在作image search的時候如此就無法找出較適合的ranking，進而會使效果變差。作者提出了一個在同樣的Hamming Distance時query-adaptive ranking的方法，能夠預先算好在每個class中的weighting，而當query進來的時候再去動態算出一個屬於query的weighting，進而達到較好的image search結果。
這篇paper提出的query-adaptive weight，主要有兩個好處。一是利用bit-level weights，可以將query找出的結果找出一個從粗到細的rank，也就是可以把ranking的精細度從原來的d提升到2的d次方。二是相較只用既有的一組weight來給query使用，作者提出的query-adaptive weight可以使query找出一個更貼近其主題的weight，進而達到更好的效果。

其細節如下:
1. 作者探討了三種資料結構，包含inverted index、tree-based index和binary embedding。當把inverted index套用到VW作image search時，會碰到一個原來在text裡面沒有的問題-關鍵字太多，一個文字的搜尋關鍵字平均而言只會有四個，但在一個image query中VW的數量可能高達幾百個，因此不適合。而在tree-based index則會遇到不適合拿來作高維向量的問題。因為假設是d維向量，有n個sample時，tree-based index要在n>>2^d時才會比exhaustive search有效率。因此作者選用了binary embedding中的SSH和DBN來使用。
2. 其系統的架構如下:
a. 利用Lowe的DoG detector和SIFT descriptor來計算BoW feature，在此系統使用了約500個VW。有了每張圖的BoW feature之後，再透過SSH或DBN轉成binary code(Hamming space)。
b. 在有了每張圖的binary code之後，再利用已經label好的圖片，對於每個semantic class算出屬於那個class的bit-level weight。假設共有k組semantic class，這k組weight的解，則是希望達到兩個目的:
i. Intra-class中的總和distance最小，有點像是K-means的那種感覺，同一個class中的每個點到其中心(每個點的平均)之距離要越小越好。而在這裡的distance則是經過weight(ai)加成過的，即|| ai˙x – ai˙ci ||^2 。
ii. Inter-class中的總和distance最大，即每個class兩兩之間的距離要越大越好，這裡的距離則是經由各自weight(ai & aj)加成過的向量差所算出來的，即|| ai˙ci – aj˙cj ||^2 。
但是同時要作的這兩個項的極小化，作者提出了以遞迴的方式來解目標的quadratic program，最終可以求出每一組class所對應到的weight。
c. 每當有一個query進來的時候，系統會動態算出一個屬於這個query的bit-level weight(aq)，而計算每兩張圖之間的距離的公式就會變成: || aq˙xq – aq˙xt ||^2 。但是這邊的aq要如何算出呢? 作者假設在query中top k的解(直接用hamming distance所算出來的解)當中，數量前三多的class中的weight的加權平均，即為aq的解，如此一來就可以算出query-adaptive weight了。
3. 在實驗的部分，作者使用了NUS-WIDE dataset來測試，因為其已經label好了81個semantic class/label。作者分別對DBN和SSH兩種方式來作測試，其在code length為48時表現皆比為36時好，並且和baseline傳統的hamming distance相比，表現有4.6%~9.5%的成長。

Critiques:
這篇提出的query-adaptive weight的方法，成功改進了原來的hamming distance沒辦法在同一群內排出ranking的問題，且在training process雖然要花上一天左右的時間，但實際在搜尋一張圖時只要花很短時間，很符合作搜尋的需求。另外，在這篇裡面所使用的SIFT加到BoW的概念，不知是否能夠改成套用上周的那篇paper中所提到的aggregating的概念，說不定會有意想不到的好效果。

Aggregating local descriptors into a compact image representation

Summary:

本篇作者提出了一個利用local descriptor(SIFT)中的特性，來對於整張圖片作一個描述，進而可以利用dimension reduction等方法，在image search中不論在運算效率上和記憶體的使用上皆有了改善。其細部內容如下:

1. 作者提出了一個方法VLAD(vector of locally aggregated descriptors)，其方法是如同BOF先建立出一個有k個visual word的codebook，而不同於BOF將一個local descriptor用NN分類到最近的visual word中，VLAD所採用的是計算出local descriptor和每個visual word(c­_i)在每個分量上的差距，將每個分量的差距加總起來，就可以形成一個新的向量來代表圖片。

2. 之後再利用asymmetric distance computation(ADC)的方式來作approximate nearest neighbor的動作。而ADC的方式是用將原來一個query在一個set中找NN的方法，改成把set中的既有的n個向量y先利用一個有k個centroid的quantizer先切好，這樣一來就可以將y的向量encode成log2(k) bit。此外，由於如果當k值很大時(文中舉例當k=2^64)，要建出codebook將是不太可行的方式，於是他再將每個D維向量再切成m個D/m維的subvector，每個subvector再去建立一個ks個centroid的codebook，如此一來就大大降低了運算量，從最原來的O(D x n)降至O(D x ks) (因為ks<。

3. 而作者還提到了另外一個部分是要作dimensionality reduction的部分，利用PCA來降維。在裡面提到了有兩個要注意的地方，第一個是因為要在作完PCA之後再來作quantization的動作，但是作完PCA之後其實向量在每個方向的分量之variance會變得很不平衡，eigenvalue較大的向量其variance較大，但是如果照著之前一段一段去quantize的話這樣在eigenvalue較大的向量上作出來的quantization error就會變大，因此要採用一個在主要component切的較細，但是比較不重要的component的部分就切的鬆一些；第二個是降的維度D’，如果D'大的話，projection error就會小但是quantization error就會大，如果D’小的話，則是相反的情況，所以D’的選擇也是一個trade-off。

4. 作者還提出了針對D’的最佳化，並和BOF、Fisher的效能作比較。也對於有沒有對D'作optimization作比較，還有D'、k值等對效能來作探討。

Critiques:

本篇利用local descriptor的方法套入image search之中，將原本找特徵點的descriptor拿來difference累加進而描述一張image，尤其是在1000萬張圖片中的large scale database中還有一定的mAP，這種將現有的東西加以改進並套用在其他方面的想法相當新奇。而在此篇所提到的dimensionality reduction和ADC的概念，如果套到之前的object search好像也是可以實行的。

Interesting Points and Local Descriptors

Distinctive image features from scale-invariant keypoints

Summary:

本篇作者提出了一個Scale Invariant的Feature Transform的方法，其主要的流程如下:

1. 利用difference-of-Gaussian來找出對於不同down-sampling過的圖片畫面中較有特徵的keypoint的位置，為何使用DOG則是因為，DOG function有著invariant to scale & orientation的特性。而在找出不同sampling的每個位置不同scale的值之後，再在同層image size中的連續三層中3*3*3的方塊中，找出local extreme，先以此作為keypoint candidate。

2. 在找出keypoint candidates之後，如圖5的(C)中所示，將一個minimum contrast的限制加上去後，就會先將一先candidate過濾掉，會過濾掉低對比的點的原因為，當contrast小時DOG算出來的值會較容易受到noise的影響，所以要把這些容易造成誤差的點去掉；另外，由於DOG會對邊緣處有較強的反應，就算標出來的位置不是相當有代表性還是會有很高的值，並很容易受到noise的影響，因此還要把這些點去掉。

3. 做好以上步驟，會再對那些點取出其orientation，並利用這些資訊，將特徵轉換到一個可以統一比較的domain，之後才可拿來比較計算。而descriptor則是利用一個4*4的array，將keypoint的周圍切成16個region，每個region中的每個小點的強度*Gaussian weight作為weight，累積出方向的histogram作為其descriptor。

Critiques:

在此方是當中，是否如果要找的對象為非剛體，即其可能產生外觀上的形變之類，在辨識上的效果可能降低許多。此外，SIFT的缺點為其速度還是沒有像後來的SURF來的快。

------------------------------------------------------------

Efficient visual search of videos cast as text retrieval

Summary:

作者提出了一個方法，利用SIFT來抽feature，並且利用這些feature來作為在影片中搜尋object的工具，其細節內容如下:

1. 首先作者找出許多affine covariant的橢圓區塊(SA和MS，SA注重於挑出corner-like feature，MS注重於挑出高對比的區域。)，這每個區塊再用SIFT的128維向量來描述。而在這些區塊當中，會再利用一個”stability check”，將沒有在連續三個frame中出現的區塊視為不穩定，就把那個區塊從資料庫中清除。

2. 接下來，作者對這些feature作一個分類的動作，但是不是對整個影片中的所有frame都作，因為這樣將浪費過多的計算。於是，作者在影片中隨機找出474個frame，來將這些frame中的feature作分類，即使已經作了如此的簡化動作，仍然有30萬個feature要來處理，數量還是很多。

在這裡作者是使用K-Means的方法來實作，而分類出來的結果傾向符合SIFT descriptor的特性，即注重在每個區域中的強度變化，而非依照每個區域與區域間的相似關係來分類。另外一個需要注意的點是，這裡SA和MS是分別各自作分類的，由於各是描述不同的特性，故要分開來作分類效果會較好。

3. 上述所分好的一類即稱為一個word，而透過這些分好的words可以建出一個vocabulary，這些visual words就可以拿來採用傳統的text retrieval的方法來作object search的動作。套用到text中的tf-idf公式，將每個key frame想成一個document，每個key frame中所包含到的特定區塊之feature，依其分類可想為一個個word，以此轉換方式，就可以作搜尋。

4. 而在此還要先定義一些進階的刪除條件，例如如果一個word在太多不同的key frame中都有出現的話，這樣出現太過於頻繁的word，在影片中可視為雜訊，因為不太可能會有一個東西會從頭到尾一直出現。或是作matching的同時，在query和data雙方的特徵點中的一定範圍內，要有同時幾個特徵點都有match到才算一個正式的match。

Critiques:

這篇利用了文字搜尋的方式來進行visual search，但說不定還可以利用像google那樣使用者互動的方式來增進搜尋的正確率，利用使用者會點擊正確結果的方式來增進效果。

另外，這個搜尋方式，雖然他有測試當資料庫中加入distractors時，如果不將word數增加，其正確率從63%降到了56%，但如果將對應的word數相對增加，其正確率即可以提升，但應用在實際情形之中，要搜尋的範圍可能很大，要怎麼找到適當的word數增加數也是一個問題。