A global Geometric Framework for Nonlinear Dimensionality Reduction

 在很多的研究當中，設法從高維度的資料當中找出具有意義的低維度的結構是很重要的事情

比如在下面這張圖中，雖然在原始資料中，
每一張圖片是64*64 pixel，
如果用row feature來表示的話，我們會有4096維的資料，
但是其實我們可以用三個維度(也就是上下、左右、光線角度)
來表示data














傳統的降維技巧包括了PCA跟MDS，
他們都實做簡單、計算快速、並且能確實發現在高維之下的線性子空間投影


但是實際上，我們可能會遇到非線性的情況，
例如在下圖A的例子中，
資料非線性的分布在一個我們稱為"二維瑞士捲"的子空間上

圖A中的兩個點，即便他們在二維瑞士捲上的距離異常的遙遠，
但是在真正的空間中，可能會詐欺似的靠近，
在這種情況下，PCA跟MDS都會失敗














這篇paper設法解決這個問題，我們設法設法找到兩點之間的真實距離
而方法的核心是如何計算在原始空間中遙遠的兩點的真實距離
大致上來說，
距離較近的兩點，我們直接使用原始空間的距離當作距離，
而對於距離遙遠的兩點，我們使用類似於shortest path的方法來處理
藉由加總path上的short hops的距離，來估計真正的距離。




首先，我們先決定哪些點是靠近的兩點，並且將那些點的距離代入原始空間的距離
            並且在圖上將他們連線

             在這裡我們有兩個'方法，第一個是取一個固定的半徑，只取在半徑內的
             而第二個則是建立K-NN graph

第二步，我們計算all pair shortest path，並以此做維兩點之間的真正距離



















第三步，我們設法利用這些距離的資料，在低維度的空間中找到合理的映射




式子如上，其中前項是我們計算出來的distance matrix，後項是在映射的子空間中，我們所得到的距離

Nonlinear Dimensionality Reduction by Locally Linear Embedding

承上篇文章，我們往往會將一個複雜的資訊用一個高維的空間中的點加以表達。
而我們常常會遇到需要將維度加以減少的情況，
如下圖所示

這篇PAPER提出了一個 Locally Linear Embedding的方法，
可以避免計算距離過遠的兩個點的距離。



而LLE的大致過程我們可以由下圖表達

首先，我們對點選取特定數量的鄰居(通常用KNN)，
接著，設法利用這些選定的鄰居線性組合出i這個點，
也就是最小化下式

值得注意的是，如果j點並非i的鄰居，那他們之間的權重即為0，
另外一個是，我們加入了下式的限制。

而minimize這個的過程，也就等同於解least-squares problem，



值得一提的是，這樣提出來的組合，
在縮放，旋轉，變形之下，都是保持穩定的。



接著，我們設法將這樣的線性組合關係映射到低維度的空間中，
也就是minimize下面的式子

同樣的，這樣的問題也可以表達成quadratic 的形式，
更明確的說，我們可以利用解疏矩陣的eigenvalue來找到解。



LLE這個方法有一些其他方法所缺乏的特點，

最顯而易見的就是，不同於一些其他的方法需要大量參數，
他只有一個參數，也就是KNN的K

另外一個則是，LLE可以較輕易的達到global optimality

接著，由於LLE在區域性結構的穩定性，'當我們所映射到的子空間維度提升時，
我們不需要重新處理原先高維度的空間中的資料

最後，由於避免掉了計算兩點間的距離，
LLE也可以避免掉計算高維的DP所花費的時間。

2012 Multimedia Grand challenge

Analyzing social media via event facets

Wang, Zhiyu, et al. "Analyzing social media via event facets." Proceedings of the 20th ACM international conference on Multimedia. ACM, 2012.

facets:

5w1h : who, when , where , what , why ,how

事情的六個面向

兩步驟:

1.同時藉由影像及文字得到更豐富的內容

2.利用BC-LDA設法得到具代表性的內容

最後再視覺化

做法 

1.先做斷詞，斷出來的詞跟TAG常常有很大的不同
2.影像部分用SIFT

利用BC-LDA學習文字與影像的主題












一個事件利用上述的六個面向展示
同時，我們也可以利用時間軸展示事件的起始與結束


how!!!!!!!!找不到tech report QQ
同時把文字跟影像放進LDA感覺是個不錯的做法
可以避免將文字跟影像分開做時，要將兩者link在一起的困難

Multimedia news digger on emerging topics from social streams

Bao, Bing-Kun, et al. "Multimedia news digger on emerging topics from social streams." Proceedings of the 20th ACM international conference on Multimedia. ACM, 2012.

同時利用了三個資料來源:
Twitter,  Flicker,  Google news

步驟

(1)在不需要使用者介入下，自動從Twitter偵測緊急的主題
(2)在不受訊息長度影響下，正確偵測關鍵字
(3)自動的從三個資料來源收集資料

方法 

co-clustering 應該盡量減少資訊的損失

其他用到的方法

(1) 資料蒐集

text:    TF-IDF 加入stop word

image: vector of Bag of Word features

Porter, Martin F. "An algorithm for suffix stripping." Program: electronic library and information systems 14.3 (1980):

(2)緊急關鍵字探勘

age theory

Chen, Kuan-Yu, Luesak Luesukprasert, and Seng-cho Timothy Chou. "Hot topic extraction based on timeline analysis and multidimensional sentence modeling." IEEE transactions on knowledge and data engineering 19.8 (2007): 1016.

(3)跨媒體的搜尋

manifold ranking

感覺要做的好還是必須要跨媒體去做，而不能只考慮單一媒體的資訊

TWIPIX: a web magazine curated from social media

Bansal, Romil, et al. "Twipix: a web magazine curated from social media."Proceedings of the 20th ACM international conference on Multimedia. ACM, 2012.

interestingness          : I = P*F*R*N

popularity                   : P : number of unique user tweeting about  the tweet

information value       :F = a*log(w) + b*i +c*n 

                                      a.b.c:weight

                                      w:word-count of the event title 

                                      i :number of image

                                      n:number of news article

 recentness                :R:number of original  tweet  on data

novelty                        :N: 1/(1+e^(eta*(d-delta)))

                                    d:number of days which event is active

如果相似度比T1大，並且時間有重疊，那就把兩個合併在一起

如果相似度比T2大，不管時間有沒有重疊，他們會被稱做相關的，並且，如果他們共用了同一個影像或者新聞文章，那麼他們就會被合併在一起

(T1>T2)