Online dictionary learning for sparse coding

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量太大的困擾上，導致比較不實用的情形。

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的功能。還有，雖然作者提出了一些新的方式來定義搜尋區域，但是如何自動選定一個適用的區域形狀，也是一個相當值得思考的課題。

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處理的需求，應該可以組成另外一種不同方式的應用。

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和執行時間之間的取捨。

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，相較起來跟人類的想法較為接近。

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所作出來的效果。

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問題可能還需要用其他的方法來解決。