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 的結果研究

Support Vector Learning for Ordinal Regression

Support Vector Learning for Ordinal Regression

Ralf Herbrich, Thore Graepel, Klaus Obermayer
ICANN, 1999
================================================

這篇提出了一種regression的問題，簡單來說就是在做classification的時候
不僅僅只用 '+' '-' 來作區隔，'+'的部分可以'+' 很多， '-' 的部分同理
用的是Support Vector Learning 的方法，但效果卻比之前的
Support Vector Classification 跟 Support Vector Regression來得好 

這篇說這種Ordinal Regression的問題可以看成
i. classification & ii. regression 的結合
因為在number及分類有限的情況下就像 i.
如果沒有限制 '+'跟'-' 的上限，就比較像 ii.
問題主要就是在怎樣maximize boundary
然後如何對同一個classifier 作 Rank 來表示

在2. 的部分先把問題定義出來，要怎樣表達這種排序的觀念
以及所要求的目標，其實這個部分就是regression
然後定義要怎樣判斷哪種結果比較好

求解的部分用了一般SVM的解法：
1. 加上cost function : minimize the squared norm
2. Lagrangian Multipliers: QP-problem

實驗的部分跟SVM classification 及SVR來作比較
================================================
優點：
1. 提出一個新的regression方式，不僅如此還將這個問題refer 到其他問題上
增加這個方法的實用性，同時也延伸了問題的解法
2. 跟兩種常用的baseline作比較，增加說服力
3. 用之前的解法(cost function, QP-problem)延伸來求解

缺點：
1. 文章的變數好多，整篇看下來我能理解的部分很有限，閱讀很困難
這有可能是因為我對machine learning的領域不熟，不過明明上學期才剛修了一門...
2. 實驗放的圖說明沒有很清楚，看了很久才懂
3. 參數的調整對SVM的影響很大，paper裡沒對這部分多加著墨就用了一組數字

Nonlinear Dimensionality Reduction by Locally Linear Embedding

Nonlinear Dimensionality Reduction by Locally Linear Embedding


Sam T. Roweis and Lawrence K. Saul
SCIENCE   VOL 290   22 DECEMBER 2000
======================================================

這篇paper提出一個方法可以在做dimension reduction 的時候
還能夠保有原先相近的neighbors

因為做完dimension reduction 原先很遠的point 有可能變到很近
這樣就會造成distance distortion
這篇的方法就是把每個 point 利用neighbor 來表示
主要可以分為以下三個步驟：

1. K nearest neighbor
2. 找出這些neighbor的weight
3. 組成 low dimension embedding vector

1. K nearest neighbor:
這部分在很多相關的paper都有提到
這篇沒有特別詳述
不過這裡要找的是each point 的 exactly K nearest
不是 K-centroid 或是 K nearest-approximate

2. 找出這些neighbor的weight:
K neighbors 用 linear 的方式組起來，總和為1
這些weight求解是least sqaure problem 
paper裡還有提到這樣的解法可以invariant to rotation, scaling, translation

3. 組成 low dimension embedding vector
最後假設要降成 d dimension
列出跟 2. 一樣的embedding cost function
這裡的解法是 NxN eigenvalue problem

paper裡提到以上的步驟裡唯一的變數是 K
一旦K決定了之後，剩下的東西都可以按照optimize 來求解
(d應該是User自己決定要用多少，但對每個point來說  K有可能不同
每個point 要用怎樣的K 才是問題，因此才是唯一的變數)

paper裡也提到很多algorithm
(ex: neural networks, self-organizing maps, latent variable models)
幾乎都有很多要set 的變數
而且也不能保証會 global convergence
這篇paper 提出的LLE 可以保証 global convergence
也就是不用set 變數  求出來的解會一致

實驗的部分 有提供兩個實驗
1. 用sequential face 表情變換 project 到2d 圖上，
然後找出它們的transfer path
這樣就可以証明相似的neighbor 會在附近 不會亂跳

2. 把term word project 到 2d semantic meaning map上
意思相近的term 就會在附近
這個map 的意義比較抽象

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

優點：
1. paper 寫得很簡潔，一看就懂，figure 2 一張圖就可以把全部過程表達清楚
2. 方法很簡單，也很make sense，可以應用的地方很多
3. problem solving 都有對應的解法，解出來的答案會converge
4. 變數幾乎沒有(只要找每個K)，不用一些ad-hoc 的setting
5. 兩個實驗都很有創意，比起一般的perfomance showing 來得有意思

缺點：
1. KNN 那裡要找每個point 的 K neighbor，這裡會很耗時間
2. 第二個實驗的結果好像有些部分不是很好，但paper裡沒解釋