Latent Dirichlet Allocation

Latent Dirichlet Allocation

David M. Blei
Andrew Y. Ng
Michael I. Jordan (這個人的名字頗出名)
Journal of Machine Learning Research 3 (2003) 993-1022
===============================================================

這篇說的LDA跟上一篇pLSA的應用面其實很相近
LDA是想要找出document裡面 term所對應到的 class
所以一個document裡面會包含各種class 的 term

可能是因為journal的關係，這篇在比較的方面寫得相當地詳細
跟最原本的tf-idf然後再跟pLSA作了比較，當然也列出了它們的一些性質及缺點

LSI 是因為 dimension reduction 而出現的觀念
pLSA 就是 improve LSI 的結果
但是pLSA也有下列兩個缺點：
a. corpus增加的時候變數也會等比例增加，會造成overfitting
b. training set 以外的就會沒辦法處理 (有點類似沒有background model)
所以這篇提出的LDA 算是pLSA的改進，用的方法當然也有不同
建model的條件就是不只對該doc的機率要高，對同類的doc也要高

LDA的主要觀念就是每個document可能會含有很多不同的latent class
而每種class的機率就是靠著每個term的機率來算
所以用的跟pLSA一樣是bayessian probability然後一樣用EM 來找出比較好的參數
然後LDA有個假設是說每個term或每個topic 彼此的次序是independent (exchangable)
這跟最原本的language model 可以說是完全不同

中間就說明了
uni-gram -> mixture of uni-gram -> pLSI -> LDA 這些model的演進

實驗的部分當然就做了上述四種方法的比較
不論在perplexity及Accuracy ，LDA 的表現都比其他三者要好

結論的部分提到說 LDA 一樣有 dimension reduction的效果
且比起pLSA 更多了modularity 和 extensibility
===============================================================

優點：
1. 這篇的比較相當完善，每個方法都有說明清楚
2. 數學推導結果
3. 對提出的假設(exchangable) 有說明原因

缺點：
1. 實驗在做accuracy 的時候就沒有用上述的其他方法作比較，而用word feature當baseline
2. 在training 數量很大的時候 跟word feature相比 improve 其實沒有說的這麼凸出

Probabilistic Latent Semantic Indexing

Probabilistic Latent Semantic Indexing

Thomas Hofmann
International Computer Science Institute, Berkeley, CA &
EECS Department, CS Division, UC Berkeley
hofmann@cs.b   erkeley.edu

CVPR' 1999
=======================================================

這個方法是用在text search 的 indexing system上

傳統的text search作法就是利用literal term matching
也就是每個字去比對
但這樣的缺點是因為text 的表示很有可能not precise
e.g. query term 出現在很多class 裡
因此就有人提出了LSA的概念
想要找出latent term 再用這些term去search
這篇paper提出的方法就是去improve LSA   兩者主要的差異在於：
a. short vector   V.S   long vector
b. TEM   V.S   SVD

tempered EM 跟原本EM的方法只差在多乘上一個weight
這樣在做EM converge的時候可以調整去避免 overfitting

後面search的方法也是用 vector-space model(VSM)
1. transformation function:  TF
2. term weighting scheme: IDF
3. similarity measure: cosine sim
簡單地說就是用tf-idf 然後算cosine similarity，這些現在來看就是標準程序

實驗的部分
列出不同class 找出的 latent term 和它們彼此的關係
比較傳統(tf-idf)、LSI、pLSI 三者的precision and recall
從結果來看  pLSI 在各dataset的表現都勝過 LSI
=======================================================

優點：
1. latent term 的觀念 (不過最早提出的不是這篇)
2. 詳細的數學式推導
3. result 跟之前的state-of-art作比較，一目了然

缺點：
1. 標準的踩在巨人肩膀上，其實觀念就是LSA，不過找到更好的方法去improve
2. 找出的latent term 好像沒有考慮出現在class的機率(出現在越少class越好)
3. 同一class的latent term 應該要越diverse越好
(2跟3的觀念在image search 裡就常常被強調，不過這篇好像都沒考慮)

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






ICMR'2011
Yu-Gang Jiang  , Jun Wang  , Shih-Fu Chang
Columbia University, New York, NY 10027, USA
IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA
========================================================

這篇paper講的是在large-scale image search上的improve
他在state-of-art 的 scheme上  用hamming distance的時候可以作re-ranking

這篇就是標準的踩在巨人肩膀上
甚至在hamming distance re-ranking的概念都是別人提出來的
不過裡面的related work 寫得很清楚
把過程及一些方法的優缺點都寫出來了

目前很多paper提出的state-of-art作法
1. 取BoW(Bag-of-words) feature
    用SIFT 再quantize 成 visual words
2. binary embedding (hashing)
3. reranking (Hamming distance)
   這篇paper主要的improve是在這裡，他提出一種reranking 是可以根據query
   給不同的weight 去作 reranking

在 related work 有作 2. 的比較，目前比較efficient image search有三種方法
a. inverted index:
    缺點是 image 不像 text 在 query的時候會用關鍵字，image的 word很多
    所以return 的 candidate images 也就會很多
b. tree-based index:
   目前大多是用KD-tree，但對high dimension的效果不好
c. binary embedding:
   很多人用Locality Sensitive Hashing(LSH)
   但在hamming distance相同下有很多不同的意義
   這篇主要是用這個方法然後improve reranking的結果
   最近也有很多paper在研究如何reranking
   但這篇最大的不同點是會因query改變weight

方法在概念上是在query 後，先找出一些比較相似的class
然後利用這些class算出hamming code 每個dimension 的weight
再用這個weight 去 內積原本的hamming distance
最後用這個score 去作re-ranking

這篇 實驗的部分就是show出用提出的方法 MAP可以提升多少
========================================================

優點：
1. 對於 state-of-art 各步驟的一些方法，在related work裡有作說明及比較
2. Adaptive weights 用數學式去推導，而且可以用 quadratic programming來算
3. improve the state-of-art

缺點：
1. 方法建立在state-of-art上，改進某一個部分，而且想法別人也提出過
這部分的創意點比較不夠
2. 用adaptive weight 變成要有一定數量的class，但在實驗裡這部分沒有詳細討論
不過在future work裡有說之後可以improve # class
3. 我覺得這個方法應該可以考慮 diversity 的問題，但paper對這部分沒有多作著墨

Aggregating local descriptors into a compact image representation

Aggregating local descriptors into a compact image representation

Herv´e J´egou INRIA Rennes
Matthijs Douze INRIA Grenoble
Cordelia Schmid INRIA Grenoble
Patrick P´erez Technicolor
========================================================

這篇paper主要的目的是要做一個large-scale image search
著力點在三方面：
1. accuracy
2. efficiency
3. memory usage
所以這個系統不但要結果好，同時在空間及時間運用上都要有效率

paper裡提到很多篇related work
上面所提到的三個目的在很多paper 裡都有研究
但通常都是只針對其中的某一項
這篇的作者比較像是集大成然後再統整
所以方法也是用之前別人用過的，然後再加以修改
步驟跟目的也有說明很清楚，主要可以分為三個
1. aggregate local descriptors
2. dimensionality reduction
3. indexing system
以下將對每項作說明：

1. aggregate local descriptors:
這步就是取feature然後作fusion，最後會形成一個high-dimension vector
這裡用的方法是BOF跟Fisher kernel，然後再aggregate成SIFT descriptors
作者把最後的結果vector 稱為VLAD
再用 K-means 作quantization 然後把每個word跟centroid difference 存起來

2. dimensionality reduction:
在1. 作完之後，每張image都有一個high dimension vector可以代表
這步的目的就是要做降維，用兩個方法 a. projection(PCA), b. quantization
這裡找 nearest neighbor用的方法是 product quantization-based approximate search method
先找出重要的 centroids 再把之前的結果 quantize 成這些 codes
再用PCA去找出最具代表性的dimensions
這裡在paper裡用比較多的數學來說明他們的結果可以work及運算方法

3. indexing system:
有了2. 的codes後，就可以把每張image都用這些codes來表示
然後用IR的方法去作inverted indexing
利用這樣去加速搜尋的結果，而不能用pair-wise comparison
paper裡最後用20 bytes 來代表一張圖

實驗的部分
作者有作了一些實驗去找出適合的 K 和 D 的值
然後去算出他的方法mAP
接著再跟 miniBOF(state-of-art)方法比較
他提出的方法用的byte較少，mAP也比較高
最後再用large-scale data 上去算 mAP 效果也能夠維持
有提到用inverted file ADC 只要 46 ms 就可以，等於是可以real-time
========================================================

這篇paper的條理很清楚
一步一步依序寫下來，用的字也很淺顯易懂
大概是對image search 比較有概念，所以都能理解他做這些步驟的目的跟想法

優點：
1. 這篇算是集大成，求好、求快、求效率，全部都有考慮到
2. 方法論述很清楚，都會說明這個步驟的目的，而不是單純寫作法
3. 相關的related work 優缺點都有提出，並且說明哪個方法為什麼不用，哪裡要改進
4. 實驗有提供state-of-art的結果，更加有說服力

缺點：
1. K 跟 D 的值像是用trial-and-error的方法去找，沒有比較有說服力的決定方法
但這個部分是trade-off 因為 K 跟 D 愈大，搜尋花的時間就愈高
2. 最後用的real-time方法 IVFADC or ADC 對 mAP的犧牲都很大，從圖上可以看到
跟baseline(BOF)至少下降0.1  等於是變差至少30%，但paper裡對這個部分說明沒有很清楚
只有強調花的時間很少
3. state-of-art 只是針對accuracy，並不是跟large-scale system的state-of-art做比較(除非沒有)
而且這篇的方法是去improve state-of-art 因此在不考慮時間效率下，應該就是要比較好

Efficient visual search of videos cast as text retrieval

Efficient visual search of videos cast as text retrieval

Josef Sivic and Andrew Zisserman

===================================================

這篇paper主要的目的是能用運像 text search 的技術來作 image search
實驗的部分是找出電影中含有query object 的 keyframes，當然要在real-time完成

一開始看的時候就想說怎麼跟「Video Google」這篇這麼像，後來查了才知道原來作者一樣

主要的步驟可以分為以下幾個：
1. 找出 viewpoint invariant descriptor
2. 利用SA及MS找出重要的橢圓形region
3. 用SIFT去找出橢圓形的descriptor
4. 用SIFT descriptor建立visual word 再用K-means 去建 visual vocabulary
5. visual indexing by text retrieval
以下將分別敘述

1. 找出 viewpoint invariant descriptor
viewpoint invariant 是想找出不會因為拍攝角度變化而改變的一些feature
所以就假設用不同視角去找，取出不變的那些feature
這部分在paper是引用其他paper的技術，沒有詳述

2. 利用SA及MS找出重要的橢圓形region
利用Harris interest point 來找出Shape Adapted (SA) region
以及找出反差很大的區域 Maximally Stable (MS) region
前者主要會出現在細節變化很多的部分，後者則是找出一個region 跟週圍顏色反差很大之處
用這兩個方法去標出所要的橢園region

3. 用SIFT去找出橢圓形的descriptor
在所有的橢圓都找出 SIFT descriptor
(SIFT 的取法在另一篇有提到)
paper裡也提到這裡的SIFT沒用到顏色

4. 用SIFT descriptor建立visual word 再用K-means 去建 visual vocabulary
以SIFTdescriptor 當feature把每個橢圓當成visual word
就像text search 的 word 一樣
因為要把類似的 visual word 分為同一群，否則 visual word 不會像 text word 一樣會有相同
所以要用K-means 去建 visual volcabulary

5. visual indexing by text retrieval
有了word 跟 volcabulary 就可以像text search 一樣
利用 stop word list 及 tf-idf 等方法來ranking
這裡的spatial consistency 就是看visual word 彼此的spatial 距離

另外video 有 temporal information 所以可以參考neighbor frame  去過濾一些比較不確定的

實驗的部分
作者用了三部影片，每1秒取一個keyframe
然後在realtime找出指定object出現的keyframes
這篇paper有著重在time efficiency
retrieval time baseline就是把每個frame  用linear search 去比對
作者提出的方法是像text search 有作indexing (tf-idf system)
另外也舉了一些比較麻煩的case，像是平滑的地方取不出feature
最後合併了很多 text search 的ranking方法測試它們的效果

最後在結論裡有提到
像這篇所用的vector-quantizing  方法跟nearest neighbor matching 的相比其實差不多
但 nearest neighbor matching 是很花時間的(目前不存在有效的演算法)
也提到可以用像 hierarchical tree 來 indexing 增加效率
spatial consistency re-ranking 很重要
另外作者提出說text retrieval 在 web search上可以用 web page 本身的內容來決定它的預設分數，image可能也可以這樣做，靠著 visual word 來判斷這是否是一個很有意義的frame

=======================================

優點：
1. 能夠串連已成熟的技術(text retrieval)來運用，直接就跨出很大一步
2. real-time 所以很強調 time efficiency ，所以才要用text retrieval idea
3. 作者提到的一些觀點很有趣，像是結論裡所說的判斷image本身的meaning，以及把很平淡的東西當作object來測試

缺點：
1. 只利用3部電影當data，而且search的時候好像侷限在同一部影片，這個assumption太強
2. 好像是為了運用temporal relation 所以才每秒取一張keyframe，而不是用適合的shot detection，但這樣pre-processing的運算量就很大。但如果只取shot frame 就要再另外找出一個frame 來作 temporal reference。這個問題是tradeoff，所以也不能僅僅看成是缺點。
3. 最後用了很多不同ranking方法(tf-idf, Bhatta, KL, L2, chi-square, ....)，沒有分析出它們的好壞在哪裡

Distinctive Image Features from Scale-Invariant Keypoints

Distinctive Image Features from Scale-Invariant Keypoints

David G. Lowe
Computer Science Department
University of British Columbia
Vancouver, B.C., Canada
lowe@cs.ubc.ca
January 5, 2004
=================================================

這篇paper 主要是用 SIFT 當作 feature，然後用這些feature 去作 object finding或是 pattern recognition。

主要可以分為四個部分：
1. scale invariance (SIFT)
2. keypoints Accurate
3. orientation invariance
4. local descriptor
以下會針對這四個部分作說明

1.  scale invariance
paper裡先說明了取SIFT的步驟，如何才能達到 invariant to scale
這個部分有用數學來証明，因此可以說是相當地嚴謹
主要的想法是用space 跟 scale 兩種變化去作 Gaussian convolution
然後找出幾乎不會變化的octave，把這些當作keypoint candidates，這樣就能達到目的
但要決定scale size、space range及 Gaussian Sigma 的範圍在哪裡
paper裡的實驗說明如果取的範圍大就需要花費較多時間
而且某些unstable keypoints 會因為scale size 增加而 mismatch
因此範圍的決定算是一種tradeoff，paper裡有給一些實驗用較好的參數值 ex: σ = 1.6

2. keypoints Accurate
用SIFT 找到 keypoints candidates 後，要過濾掉一些不適合的keypoints
所以要detail 跟neighbor 作比對
這裡有用到 1. 部分取出的 local maxima and minima of the difference-of-Gaussian
利用threshold 去除不適合的 keypoints
paper裡有提到這樣可能會去掉一些有用的information
因為local minima 有可能是因為 low contrast，這樣的算法會受到edge response 影響
所以去掉edge response後再用threshold 去刪掉會比較好

3. orientation invariance
這些過濾之後的 keypoints descriptor 會因為rotation 而找不到
因此paper利用 region around keypoint 來算 orientation histogram
用36 bins 去表示 360°
利用 peak of histogram 來決定rotation 的角度，把它們都轉正(即轉統一的角度)

4. local descriptor
由1 跟 3 我們可以得到 keypoints 的 scale, orientation 及 location 
因此要作 feature fusion
另外paper裡提到 descriptor 可以把原本pixelwise的 image gradients 合併成一個vector
這樣在比對上速度會比較快

之後做了一些實驗在object recognition上
從最基本的keypoint matching 開始
找出跟給定的object 一樣的keypoints
為了要快速找到類似的keypoints 這裡用了一些方法
efficient nearest neighbor indexing (ex: K-D tree)  找出相似的keypoints
clustering with Hough transform 先將keypoints分群再去找

最後結論裡提到SIFT找出keypoints後再作orientation當作feature
可以有效地達到object recognition
也可以用來作object categorize
然後一些像是invariant to color and texture 也可能是之後可以研究很重要的feature

==================================

優點：
1. 取feature，invariant to scale and rotation 這部分的闡述很清楚而且很容易理解
2. 用數學式証明SIFT的一些性質，很有說服力
3. 可以作到object recognition ，甚至被擋住大部分都找得出來

缺點：
1. 實驗用的是gray-level image (在conclusion 這部分有補充)
2. 參數的取法是用實驗作的結果，取比較理想的值，比較ad-hoc，沒有一個直接方法去算出optimal或較好的值
3. paper裡提到可以作object categorize，這部分應該還要再多一些information才有辦法。因為在example裡面，作者有用屋子的牆當object，但卻不會找到另一間屋子的牆。理論上它們的color, texture 及很多pattern都很像(甚至幾乎一樣)，但卻不會被找到，所以作者實驗用的參數及辨識是very strict，這樣用在找"類似"的object時，表現可能不會如預期這麼好。