- 簡述
- 介紹
- 概述
- 總結
一．簡述
本次翻譯一篇Liu Wei的一篇論文，之前介紹譜聚類的時候大家都知道，用譜聚類對樣本進行分割，大概的流程就是先将原始資料通過不同的規則建構出相似度矩陣，然後再用相似度矩陣表示拉普拉斯矩陣，再對拉普拉斯矩陣進行特征分解，取前k個最小的特征值對應的特征向量，這幾個特征向量組成的矩陣每行表示樣本，進行聚類。但是在大資料下，傳統的方法建構的相似度矩陣，需要每個樣本都與别的樣本之間計算相似度，那這樣建構高緯度的相似度矩陣會很耗時間。傳統的建構相似度矩陣都是樣本與樣本之間計算得到的，本篇論文中Liu就提出了全新的基于樣本與m個初始聚類中心的關系建構樣本與m個聚類中心的相似度矩陣Z後，再建構樣本與樣本間的相似度矩陣W。
二．介紹
随着網際網路的快速發展，現在我們能收集大量的無類标資料，比如圖像，聲音，接着對對高次元半監督學習的需求就上升了。不幸的是，大多數的半監督學習方法對高次元下的資料具有很差的适應性。比如，經典的TSVM在面對以指數增長的資料大小時，是具有很高的計算量的挑戰的。在大量的TSVM不同版本中，CCCP-TSVM具有最低的複雜度，但是也至少需要O(n^2)的複雜度，是以也很難處理高維資料。
基于圖建構的半監督學習(Graph-based SSL)近來得到大家的注意，因為它很容易實施并且得到封閉解的方法。然而自從n*n的圖拉普拉斯矩陣的逆矩陣需要後，Graph-based SSL經常會有立方的時間複雜度O(n^3)。是以，阻礙了對真實生活中大量無類标問題的廣泛應用。為了調和立方的時間複雜度，近來的學習是尋找降低對拉普拉斯矩陣操作的計算量。Delalleu在2005年提出了一個無參歸納的方法，該方法能讓類标預測建立在樣本的子集上，接着縮短了子集樣本上的拉普拉斯矩陣跟剩餘樣本德聯系。很明顯，這樣的縮短方法忽略了輸入資料的主要部分的拓撲結構，由此，丢失了大量資料資訊。Zhu&Lafferty在2005年對原生資料建構了一個生成混合模型，提出了harmonic mixtures來測量類标預測的方法，但是這個沒有解釋怎樣建構一個像提出的harmonic mixtures一樣的高維稀疏矩陣。
在這片paper中，我們提出了一個高維圖建構方法來高效的利用所有樣本點。這個方法是簡單且可可更新的，享有線性空間複雜性，時間複雜度與資料尺寸相關。
三．概述
我們從兩方面嘗試解決與半監督學習相關的可擴充問題：基于中心點的類标預測（anchor-based label prediction），鄰接矩陣即樣本與樣本間的相似度矩陣的設計(adjacency matrix design)。
3.1Anchor-Based Label Prediction
我們關鍵的觀察點是來自全尺寸下樣本預測模型的基于圖的半監督學習計算的密集型。自從在高次元下應用的無類标樣本的數量變得巨大了以後，學習一個全尺寸下的預測模型是很低效率的。假設一個類标預測函數f : R^d → R，定義在輸入樣本上X={X1，X2，…,Xn}。我們假設前l個樣本是有類标的，其餘的樣本是無類标的。為了在高維資料下适用，Delalleu在2005年建構了一個預測函數，該函數是在其中一部分anchors下的樣本類标的權重平均值。如果能夠推出類标與小得多的anchors子集的聯系，其他無類标的樣本就能很容易從簡單的線性組合中獲得類标。
這個想法是用了一個子集，這其中每個Uk充當了一個anchor中心點，（這些點就是初始化的anchors聚類中心點），現在對于每個xi的預測函數f（xi），我們替換成m個uk點放入預測函數求和。
這裡Z_ik是樣本适應權重（代表Xi樣本與Uk的關聯強度）,這樣的類标預測高效的進行無參的回歸。讓我們定義兩個向量
重新寫公式一:
這個公式提供了一個可擴充半監督學習的主要處理方法，因為它減少了無類标的解空間，從很大的f（n*1）到小的多的a（m*1）。這種高效的類标預測模型确實緩和了最初全尺寸模型的計算負擔。
重要的是，我們使用Kmeans聚類中心代替随機取某些樣本來表示這些anchor點{Uk}。因為使用kmeans聚類中心會有一個更好的充分覆寫，得到的聚類中心會更加均勻。
3.2鄰接矩陣的設計
假設存在由n個資料點建構一個無向圖G（V,E,W），V是圖的節點，代表n個資料點，Vi代表Xi，E（V*V的次元）是邊的集合，代表鄰接矩陣的中的點，W是一個權重的鄰接矩陣，該W測量邊的長度。顯然，圖中的邊連接配接是很重要的，一個廣泛使用的連接配接政策是基于KNN原則建構圖，當Xi是Xj最近的幾個相鄰點或者反之亦然時，KNN圖會創造一條邊來表示他兩之間的聯系。基于KNN原則建構圖的時間複雜度為O（kn^2），是以傳統的基于KNN原則建構的圖在大尺度資料下是不可行的。即使我們或許能構造一個近似KNN原則建構的圖來節省點時間，在涉及到操作高維圖時，大矩陣的求逆或者大尺寸的線性求解仍然是一個大的障礙。
3.3設計原則
現在我們研究了一些指定高次元問題下設計Z和W的一些原則。
原則1
鄰近的資料應該擁有相似的類标，相隔很遠的資料應該類标很不相同。這使得我們也對Zik同樣施加了影響，當Uk離Xi很遠時，Zik=0.最終我們會得到一個稀疏非負的矩陣Z（n*m次元）
原則2
我們需要W>=0，非負的鄰接矩陣能充分讓得到的拉普拉斯矩陣L=D-W正定，該理論已經由Chuang在1997年證明了。這個非負的性質對確定得到很多基于圖的半監督學習得到全局最優解很重要。
原則3
我們更想要一個稀疏矩陣W，因為稀疏矩陣能在不相似的點之間有更少的無用連接配接，這樣的稀疏矩陣W會傾向于有更高的品質。Zhu在2008年已經指出稠密矩陣相比于稀疏矩陣會表現的更差。
直覺的，我們會用一個非負的稀疏矩陣Z去設計非負稀疏矩陣W。實際上，在下一部分，我們會共同設計Z和W，産生一個經驗上稀疏的高次元圖。相反地，最近Zhang在2009年提出的Prototype Vector Machine （PVM）,分開設計Z和W，産生了不适當的密集型圖，除此之外，當使用Nystrom方法時，PVM未能保證圖相鄰矩陣的非負性。是以，PVM不能保證圖拉普拉斯的時間消耗是收斂的。是以，我們直接設計W，確定它非負和稀疏的特性。
四．總結
本篇論文先翻譯到這裡，在這裡我們發現了，在處理高次元資料時，傳統的方法都因為很高的時間複雜度，而難以駕馭得了高次元資料處理問題。大家都在找原來樣本與樣本之間的相似矩陣W的近似表達。近期人們提出了樣本與初始聚類的關系建構了相似度矩陣Z，想通過Z建構鄰接矩陣也就是相似度矩陣W，這樣的話，本來求W（n*n）的問題就會被轉換成Z（n*m）的問題，m<<n，這就為我們在處理高次元資料上帶來了可能。下次會着重講解如何建構Z和W。