Online Dictionary Learning for Sparse Coding

Online Dictionary Learning for Sparse Coding

Julien Mairal, Francis Bach, Jean Ponce, Guillermo Sapiro
ICML' 09
====================================================

sparse coding 就是用basis 的 linear combination 找出distance最小的
這篇paper主要是在探討怎樣去取那個basis set
然後用新的optimization方法(stochastic approximation)去作dictionary learning

之前的paper有提到2nd-order iterative batch
可以比1st order gradient descent來得快，但缺點是不能用在非常大的training set上
而且也不能動態地更新training data
這篇提到的online approach 就是要能夠解決這個問題，就是可以動態更新
另外這篇也提到這裡用的方法用的memory比較少且compute 也較少

contribution:
1. optimization: smooth nonconvex objective function over a convex set
2. iterative online algorithm
3. faster then previous approach

sparse coding 最基本的條件就是要滿足兩個部分：





這個部分跟Vector Quantization(VQ) 一樣
就是要找出一種basis 讓它們的distance 最小
但sparse coding 跟 VQ最大的差別就是在

這個式子就是把原來只能用dictionary 某個basis當作vector的限制拿掉
也就是可以用basis set 的linear combination 來當成vector
但又不想要這組linear的element 太多
所以後面就加了L1-distance 來當作regularization
然後這篇就証明說用了stochastic gradient descent (SGD) 的方法
來作optimization 的效果很好而且比較快，然後會收斂
後面就用了很多的篇幅在講收斂的效果

實驗的部分就跟之前Batch的方式來比較
這篇提出的方法收斂的速度較快，且最後結果也都差不多(甚至更好)
另外也利用這個方法應用在impainting上，表示在很多image processing
都可以利用這樣的方法來解決問題

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

優點：
1. 証明很嚴謹，除了証明可以work，還証明了時間跟收斂程度
2. 利用很多solved problem 來推導証明 (least square, LARS-Lasso, Cholesky ...)
3. 提出這種想法(or solve method)可以應用在很多類似的問題上
4. improve state-of-art

缺點：
1. 相當難唸且難懂(可能是牽涉到太多專有名詞及optimization tool)
2. 應用的部分(impainting) 沒有作仔細的比較

Fast concurrent object localization and recognition

Fast concurrent object localization and recognition
T. Yeh, J.J. Lee, and T. Darrell
CVPR '09

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

這次換我報告，所以比較晚補上來
這篇主要的目的是要improve ESS 對於multi query model的改進
原本的ESS是針對某一種 query model 去作有效率的sub-window search
但如果query model 是很多種的時候(ex: 120)，如果是重複做120遍
那就會變得很沒有效率，需要花費很多時間，這篇的目的就是要改進這樣的作法
作者把這樣的方法稱作 Concurrent Localization and Recognition (CLR) 以下用CLR來稱呼

其實CLR說穿了跟ESS相比，就差在每個iteration會去切那個object boundary
所以當x, y 的boundary找出來的時候，同時也知道這個區域比較像哪一個object
方法是用 vocabulary tree 先建好每個bag of word(BoW)的inverted index
然後透過SVM去learn出query models 對應BoW的weight
最後用這些 weight去算出每個 boundary candidate 的 score
利用score去算出和哪些model比較相似

比較technical的部分是：
利用upper bound來作為branching and bounding的依據
所以子集合的upper bound < 母集合，有這個條件 bounding才能成立
然後透過每種 query upper bound 來切割每個iteration 的 object candidate

這篇有趣的地方是它提出了以下兩個idea
1. Multi-instance CLR
就是在target image裡面有不只一個object
這裡提出的方法是當找到那個object之後就把那個區域所有的BoW都挖掉
2. Polygons bounding
利用多邊形(ex: 三角形或組合多個矩形)來作bounding
不過上面兩個idea在這篇裡面都沒有多作探討

實驗的部分有詳細說明為什麼不用既有的dataset
a. Caltech256: 背景太乾淨
b. PASCAL: model class 太少
然後實驗的時候有跟各個model來比較以及各model的好壞
像是BoF的方法雖然快，但無法找出object的位置
ISM 的方法應該算是state-of-art 但是花的時間太多

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

優點：
1. data-dependent: 會考慮feature 的位置來作branching and bounding
2. Multi-class
3. Branching and bounding on objects
4. Flexible bounding geometries
5. 實驗的說明跟比較很全面且詳細

缺點：
1. query models 雖然是很多個，但都是事先給死的，所以可以off-line 建好
2. Flexible bounding 這部分的著墨比較少

PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations

PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations

U Kang, Charalampos E. Tsourakakis, Christos Faloutsos
SCS, Carnegie Mellon University
ICDM'09
======================================================

這篇最要是在探討 PEGASUS這個 peta graph mining library 對 peta-scale 資料的處理
其中提到了很多graph mining operations, ex: PageRank, diameter 等
都可以用GIM-V(Generalized Iterated Matrix-Vector)來解決

GIM-V 就是一個matrix 乘上一個vector (答案淺而易見也是一個vector)
這中間的步驟分為三個部分
1. combine2: 兩個element 相乘  (就是做一次乘法)
2. combineAll: 把n個乘法的結果全部加起來 (n-1個加法)
3. assign: 把算好的值填回去
利用這樣的架構之下，要平行來處理就變得很容易
因為在distributed system是用 <key, value> 這樣的pair來運作
combine2() 可以平行來算
算好之後全部由combineAll()來加總，每個row都要作一次combineAll()
但row之間是互相獨立來運算，所以也很容易平行
assign的值每個都是獨立的，也很容易平行

paper後面就介紹怎樣用SQL語法來做到GIM-V  (看來SQL對database真的很重要)
然後再透過GIM-V來實作
1. PageRank
2. Random Walk with Restart
3. Diameter Estimation
4. Connected Components
其實很明顯上面四件事幾乎都是search engine要做的事
也因此才會用到這樣peta-scale的data mining

後面就做了一些實驗來跟baseline (naive method) 比較
從time 跟 space 上面來分析  他們所提出的fast GIM-V 至少快了5倍

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

優點：
1. 利用GIM-V來作比較
    像這樣large-scale data mining 要如何來比較真的很困難
    作者能夠想到利用這樣的方式，然後再証明一些運算(ex: PageRank)
    都能透過這樣的方法來解，提供一種比較的基準，是最大的賣點
2. 提出 fast GIM-V 比naive 方法快了5倍，這部分比較像演算法，寫得很詳細
3. 真的實作且實驗在large-scale data上  (1.5Pb & 120Gb)
    之前應該沒有人實驗這麼large-scale 的data

Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience

Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience


Alan F. Gates, Olga Natkovich, Shubham Chopra, Pradeep Kamath,
Shravan M. Narayanamurthy, Christopher Olston, Benjamin Reed,
Santhosh Srinivasan, Utkarsh Srivastava
Yahoo!, Inc.

VLDB ‘09

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

面對現在愈來愈大量的及運端資料的處理，Map-Reduce是運端資料處理的方式
但其對於很多地方都有限制(ex: user define function, data type)
這篇提出的方法是用dataflow programming model 就像SQL語法一樣
提供類似的服務給大量的database處理，並研究它們的performance

"Pig" 是一種high-level dataflow system 作為SQL跟Map-Reduce的媒介
所以它也提供像是SQL那樣的語法(ex: filter, join, count...)以供search

Paper裡提到Map-Reduce的架構上有些缺點：
1. 不能直接提供較為複雜的N-step dataflows
2. 無法直接處理multiple data sets
3. 一些處理data的function ex: filtering, aggregation 都要自己implement

然後Pig會compile 這些dataflow programs成為Pig Latin然後丟進Hadoop Map-Reduce

這篇paper主要focus在一些跟原本SQL架構上不同的部分


Map-Reduce Data type的部分，原本只支援int, long, double 及 char array
這裡提到可以全部轉用Pig的byte array 來handle

Map-Reduce在Map階段，會透過指派的key來控制
然後在Reduce階段再利用這些key來作sort 及 aggregation

Pig 是把logical plan 轉為physical plan 然後再轉為Map-Reduce plan
另外在Flow control 的部分在Pig可以用push model 和 pull model來達到nested program

另外在文中也提到因為Map-Reduce是用java寫的，所以memory management是很大的問題
因為java不允許developer直接對memory allocation來作控制
最直接的想法就是把直接調整 java virtual machine 能用的記憶体空間
但這樣會降低performance 很多
這裡用的方法是透過Pig，先把data集成 bags再去處理

另外在user define function (UDF)這裡也可以透過streaming的概念
把executable files 放在Pig 的處理階一併執行，這樣就可以解決原本的限制

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

這篇感覺是在Map-Reduce 的架構上說出它們現有的缺點，然後用Pig再以改進

Describable Visual Attributes for Face Verification and Image Search

Describable Visual Attributes for Face Verification and Image Search
 
Neeraj Kumar,  Alexander C. Berg, Peter N. Belhumeur, and Shree K. Nayar
PAMI 2011
========================================================

這篇paper主要是想找出face attributes進而來做face verification 跟 image research

先利用low-level features 去learn intermediate representations
再根據given的attribute label 然後自動去train classifier
藉由classifier 去找出該用哪些representations 比較適合 each attribute
所以最後找出來的這些attribute都是有具体實際意義而不是latent
這些叫作visual attribute ，可以把它們當作visual word來用
這樣的好處是，這些representations 可以重複使用
也就是要加一種attribute 就可以用representation的組合來表示，彈性比較大

這裡主要是應用在face verification 跟 image research
a. face verification: 拿出兩張圖，問是不是同一位(可以不用非常frontal)
b. image research: "smiling asian men with glasses" 找出符合這些條件的圖

方法就是在取完各種low-level feature後
用的概念就是假設要找"gender" 來當作attribute
利用SVM來train, 準備的training data 大概是500~2000張 (可能是從網路上抓的)
然後看哪些low-level feature 最能表現出在 male > 0; female < 0
接著這個attribute就用這些feature來表示
當然這些feature的combine 要經過一些weight的調整

這樣做出來的classifier的結果  比起其他的方法都要好得多

另外還有作simile classifier
有點類似說這張臉有沒有類似某人的鼻子這樣的classifier

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

實驗的結果  用這樣的方法
face verification 可以達到91.86%
如果是用人的判斷來當groundtruth 更可達到99.2% (因為有些case連人都認不出)
image search的部分則是用結果來呈現最後的結果比yahoo! image search 要好

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

優點：
1. 把缺點跟不足的部分都講得很清楚，也提供別人可以研究的方向
2. 取出來的attribute都是有physical meaning ，這樣在visualization等會有幫助
3. 跟其他相關paper的結果作比較

缺點
1. 要找的 attribute都是 given，可能存在更有鑑別度的attribute
2. 每種attribute 的training data 都要去標

Where’s Waldo: Matching People in Images of Crowds

Where’s Waldo: Matching People in Images of Crowds

Rahul Garg, Deva Ramanan, Steven M. Seitz, Noah Snavely
CVPR 2011
=================================================

這篇paper的目的很簡單，就是像在玩 "where's Waldo" 這個遊戲一樣
在一張人很多的相片裡，找出所要找的那個指定的人

這個問題困難的地方在於要找的對象通常很小，而且是在一大群人裡面找出來
傳統的一些方法，像是取feature 作matching 或是用人臉來判斷 效果都很有限
因為人很小所以feature一定很少，且人常常不是正面，所以也沒有人臉feature

不過這篇paper的假設很強，他是說在接近的時間點，同一個地點會有不同的拍攝者
也就是說這些照片是時間間隔很短，拍的場景幾乎一樣，但角度不同
那一大群人也幾乎是同一群，要找的人就在裡面

第一步是先把 user input 的那個人learn appearance model
這裡有提到如果build 相當精確的model，那就會因為動作不同或遮蔽物而影響結果
因此這裡採用的是part-based，也就是分別算出每個部分的分數，最後再合併
值得注意的是這裡的training data就只有user 的那張input
color model用的是 pixel-level RGB
因為要找的人很小，SIFT等的feature 不多
另外這裡也有說如果color特別明顯，它的weight就會上升
對於遮蔽的問題，這裡用的part-based的方法，然後根據不同part給不同的weight
最後找出的目標會用2D的投射來猜出這樣的動作改變是否合理

除了對目標一些feature的處理，還用到了3D環境一些簡單的model來輔助
例如說把input跟candidate投影到1D上面，看看高度等限制是否合理
然後用了一些假設：
a. 人通常會在同一群人裡
b. 鄰近的人通常就會是那群人
接著用MRF optimization 作出最後的結果，判斷是不是有找到

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

實驗的部分
這裡有強調groundtruth是他們自己標的
但標這個的工作就算是由人來做也是相當困難
有些時候甚至是system找出來才發現之前沒有標到
最後利用PR-curve來呈現出結果
=================================================

優點：
1. 整個問題很有創意，而且算是自己定義的新問題
2. 這個問題本身就算是要人來做也不容易，問題的難度很高

缺點：
1. 假設很強，也就是換個場景就找不到，例子也都是在同一個時間點下的結果
2. 實驗的groundtruth那裡其實不是很嚴謹，不過這就算要人來標也很困難十
3. 每個input 的找出的結果個數應該都不多，不知道怎麼畫出這麼詳細的PR-curve

Learning to Rank: From Pairwise Approach to Listwise Approach

Learning to Rank: From Pairwise Approach to Listwise Approach

ICML 2007
Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, Hang Li
==================================================

這篇的目的是要改進以前用的pairwise ranking的方法
利用listwise learning method 然後搭配適合的 model 跟 training method

主要可分為以下三個階段：
1. Listwise Approach
2. Probability Models:
     a. Permutation Probability
     b. Top One Probability
3. Learning Method: ListNet
下面將分別詳述：

1.  Listwise Approach
簡單地說就是在training 的時候，要餵給一個list
要告訴它說這個list裡每個object的分數，愈前面愈高分
相較於以往的方法，以前用的是pairwise
所以之前是會分是或不是  也就是 +1 or -1
現在則是要有類似ranking的分數在list裡

2. Probability Models:
    a. Permutation Probability
因為input是list，所以排的順序也變得很重要
如何去算出這樣順序的好壞或是分數要用到permutation
所以這裡定了這樣的方法

    b. Top One Probability
為了有別於以往的pairwise，上述listwise的方法是可以直接拿整個list來算score
這裡就用了一些推導証明出可以只用Top One的就好
因此就不用像以前pairwise算的次數那麼頻繁
另外這篇paper用來算distance的方法是 Cross Entropy (不過為什麼不用DL-divergence?)

3. Learning Method: ListNet
搭配上面的model，利用GD (Gradient Descent) 來作optimization
找到最佳的weight之後，後面丟進來的query就可以利用這些weight來算score
然後做完ranking 排出好的結果
另外paper裡也提到這部分與RankNet大致上相同
唯一的差異是在RankNet是pairwise，這裡改成listwise
也因為這個改進，時間複雜度下降了一個O(n), n = #doc
==================================================

實驗的部分用了TREC跟OHSUMED這兩個dataset
然後拿另外的RankBoost, RankSVM, RankNet 來當baseline
其中RankNet還是當時的 state-of-art
實驗的結果在accuracy跟NDCG的結果幾乎都比較好
此外我很好奇他們怎麼evaluate ranking的結果
他們用CSearch的dataset，裡面對每個query都有1000筆結果
然後有分別給出0~4分，不過這個dataset似乎是要付費的

在Discussion裡有說明他們的方法為什麼會比RankNet來得好
因為training data取的部分很有可能會biased
然後在作pairwise similarity的時候可能就會當成negative class
因此就算不到它的weight
而在listwise就沒有這個問題，因此表現也較RankNet來得好
==================================================

優點：
1. 數學算式推導及lemma儘管用得不少，但條理很清楚，非常容易看懂!!
2. baseline的方法用了三種，其中有一種還是state-of-art，無論是速度或效果都比較好
3. 整套的方法從listwise input, model, 到training method 都有做好調整，且寫得很清楚

缺點：(Nothing to complain!!)
在introduction裡面，有寫到ranking對很多問題(領域)都有幫助 ex: sentiment analysis
但沒有真的去做application 的結果研究