論文 | 半監督學習下的高維圖構建

08-15

論文 | 半監督學習下的高維圖構建

來自專欄 TensorFlowNews6 人贊了文章

翻譯：荔枝boy

【磐創AI導讀】：本文主要介紹了半監督下的高緯圖重建。歡迎大家關注我們的網站和系列教程：http://www.tensorflownews.com/，學習更多的機器學習、深度學習的知識！也可以搜索公眾號：磐創AI，關注我們的文章。

一．簡述

二．介紹

三．概述

四．總結

一．簡述

本次翻譯一篇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。

最後，對深度學習感興趣，熱愛Tensorflow的小夥伴，歡迎關注我們的網站！http://www.tensorflownews.com。我們的公眾號：磐創AI。