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