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 這部分的著墨比較少