Online dictionary learning for sparse coding
Summary:
Sparse coding是利用一組從dictionary中找出的basis去組成目標之向量，而這篇paper的重點在於如何有效率的去建構出這個dictionary。作者提出了一個給dictionary training用的online optimization algorithm，這個建立在stochastic approximation上的方法，可以在有幾個billion個training sample的dataset中也達到不錯的效果。
作者有提到這篇paper的contribution如下:
1. 將dictionary learning problem轉成一個optimization of a smooth nonconvex objective function over a convex set的問題。
2. 提出了一個iterative online algorithm去有效率地解決問題。利用的是在每個step去極小化surrogate function。
3. 證明了其演算法相較於傳統的方式快上許多，特別式也在一個1200萬畫素的圖片上去作處理，達到很好的效果。
作者還提出了一些方法去對他提出的演算法作optimization的動作，如下:
1. 針對已經處理過的部分去作捨棄，因為在文中的algorithm1中有提到A、B兩個矩陣都會帶有著過往的資訊alpha，但是如果今天在一個很大的dataset中，有一個x是之前已經處理過的，又再出現一次的時候，就可以把他之前算過的alpha給相減掉。
2. 利用一次處理多組的sample，而不是一次只對一組sample的alpha值去對A和B兩個矩陣作更新，也可以達到加速的效果。
3. 當dictionary中出現不常使用的element時，就在optimization的過程之中將其刪除，也可以達到更好的performance。
作者也在文中提出了一些前提假設來去證明這個方法的收斂性，有興趣的朋友們可以去細看那些推導的過程(我個人是覺得有點難通透…)。
最後作者還作了一些實驗來證明其方法的效果，可以看出在速度上比batch的方式快上許多。
Comment:
之前在另外一門課(數位視訊技術)的期末project中，曾經利用sparse coding去實作image super-resolution，那時候在dictionary training的時候就花了很多時間去跑，而實際上在跑後面的sparse coding也是很花時間，雖然說這是一個較新的領域，但是實際上在應用的時候，可能還是會卡在computation量太大的困擾上，導致比較不實用的情形。
2011年6月9日 星期四
2011年6月1日 星期三
Fast concurrent object localization and recognition
Fast concurrent object localization and recognition
Summary:
這篇文章中，作者提出了一個方法去實作同時達到object localization和object recognition的動作，假設一張圖片抽出了N個local feature，和給定M個possible object model，要找到在image i中一個bounding region r (localization)去極大化第i個possible model (recognition)的prediction score。
在此目標下，作者使用了branch-and-bound的方式去找解。但是branch-and-bound有兩個很重要的部分，一個是如何去將一個set作分割(branching)，另一個是如何找到一個上限或下限去對每個子集合作處理(bounding)。作者在bounding方面使用的是和ESS[1]中相同的方法，不過在region的取法上，原來的ESS中只針對了長方形的方式來尋找；作者在本篇文章後段也提出了一個改進的方法，可以用composite bounding boxes來用同時搜尋K個長方形，另外一個改進的方法則是選定一個直線邊界的兩端的interval，這樣就可以對一個polygon作出許多不同大小的範圍。這兩種形狀剛好也可以套入branch-and-bound演算法中，且也提出了方法證明了得到score相較於純粹長方形的搜尋中還好，且雖然複雜度稍微提升，但其效果還算顯著。
另外，在搜尋的時候，作者還提出了一個data-dependent的概念，只針對有包含的特徵點的區域來作搜尋，可減少需要搜尋的set。
Comment:
而在原來的ESS中加入一個object model的變數，是否也可讓演算法對應到recognition的功能。還有，雖然作者提出了一些新的方式來定義搜尋區域，但是如何自動選定一個適用的區域形狀，也是一個相當值得思考的課題。
Summary:
這篇文章中，作者提出了一個方法去實作同時達到object localization和object recognition的動作，假設一張圖片抽出了N個local feature，和給定M個possible object model，要找到在image i中一個bounding region r (localization)去極大化第i個possible model (recognition)的prediction score。
在此目標下，作者使用了branch-and-bound的方式去找解。但是branch-and-bound有兩個很重要的部分，一個是如何去將一個set作分割(branching)，另一個是如何找到一個上限或下限去對每個子集合作處理(bounding)。作者在bounding方面使用的是和ESS[1]中相同的方法，不過在region的取法上，原來的ESS中只針對了長方形的方式來尋找；作者在本篇文章後段也提出了一個改進的方法，可以用composite bounding boxes來用同時搜尋K個長方形，另外一個改進的方法則是選定一個直線邊界的兩端的interval，這樣就可以對一個polygon作出許多不同大小的範圍。這兩種形狀剛好也可以套入branch-and-bound演算法中，且也提出了方法證明了得到score相較於純粹長方形的搜尋中還好，且雖然複雜度稍微提升，但其效果還算顯著。
另外，在搜尋的時候，作者還提出了一個data-dependent的概念，只針對有包含的特徵點的區域來作搜尋，可減少需要搜尋的set。
Comment:
而在原來的ESS中加入一個object model的變數，是否也可讓演算法對應到recognition的功能。還有，雖然作者提出了一些新的方式來定義搜尋區域，但是如何自動選定一個適用的區域形狀，也是一個相當值得思考的課題。
2011年5月17日 星期二
PEGASUS - A Peta-Scale Graph Mining System Implementation and Observations
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處理的需求，應該可以組成另外一種不同方式的應用。
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/
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)