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所作出來的效果。
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/
2011年3月15日 星期二
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的概念，說不定會有意想不到的好效果。
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的概念，說不定會有意想不到的好效果。
2011年3月9日 星期三
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(ci)在每個分量上的差距，將每個分量的差距加總起來，就可以形成一個新的向量來代表圖片。
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好像也是可以實行的。
2011年3月2日 星期三
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數增加數也是一個問題。
訂閱：
文章 (Atom)