鄰里成分分析

鄰里成分分析（Neighborhood components analysis，NCA）是一種監督式學習的方法，根據一種給定的距離度量算法對樣本數據進行度量，然後對多元變量數據進行分類。在功能上其和k近鄰算法的目的相同，直接利用隨即近鄰的概念確定與測試樣本臨近的有標籤的訓練樣本。^[1]

定義

鄰里成分分析是一種距離度量學習方法，其目的在於通過在訓練集上學習得到一個線性空間轉移矩陣，在新的轉換空間中最大化平均留一（LOO）分類效果。該算法的關鍵是與空間轉換矩陣相關的的一個正定矩陣A，該矩陣A可以通過定義A的一個可微的目標函數並利用迭代法（如共軛梯度法、共軛梯度下降法等）求解得到。該算法的好處之一是類別數K可以用一個函數f（確定標量常數）來定義。因此該算法可以用來解決模型選擇的問題。

解釋說明

為了定義轉換矩陣A，我們首先定義一個在新的轉換矩陣中表示分類準確率的目標函數，並且嘗試確定A^*使得這個目標函數最大化。

$A^{*}={\mbox{argmax}}_{A}f(A)$

留一分類

對一個單一的數據點進行類別預測時，我們需要考慮有一種給定的距離度量確定的K個最近鄰居，根據 $k$ 個近鄰的類別標籤投票得到該樣本的類別。這就是留一（Loo）分類算法。但是對所有數據集進行一個線性空間變換之後，新空間中的同一樣本的最近鄰居集可能跟原空間的最近鄰居集有很大差別。特別的，為了平滑 $A$ 中元素的變化，我們可以使該樣本的最近鄰居集離散化，也就是說任意一個基於一個點的最近鄰居集的目標函數f都是離散的，因此也是不連續的。

解決方法

我們可以用一種受隨機梯度下降法算法的啟示得到的方法解決該問題。在新的轉換空間中，我們並不是對每個樣本點用留一分類方法求取 $k$ 個最近鄰居，而是在新空間中考慮整個數據集作為隨機最近鄰居。我們用一個平方歐氏距離函數來定義在新的轉換空間中的留一數據點與其他數據的距離，該函數定義如下：

$p_{ij}={\begin{cases}{\frac {e^{-||Ax_{i}-Ax_{j}||^{2}}}{\sum _{k}e^{-||Ax_{i}-Ax_{k}||^{2}}}},&{\mbox{if}}j\neq i\\0,&{\mbox{if}}j=i\end{cases}}$

輸入點 $i$ 的分類準確率是與其相鄰的最近鄰居集 $C_{i}$ 的分類準確率： $p_{i}=\sum _{j}^{n}p_{ij}\quad$ 其中 $p_{ij}$ 是 $j$ 是 $i$ 的最近鄰居的概率。定義用全局數據集作為隨機最近鄰的留一分類方法確定的目標函數如下：

$f(A)=\sum _{i}\sum _{j\in C_{i}}p_{ij}=\sum _{i}p_{i}$

由隨機近鄰理論知，與單一樣本點 $C_{i}$ 的同類別的在隨機近鄰域 $C_{i}$ 樣本點 $j$ 可以表示為：

$P(Class(X_{i})=Class(X_{j}))=p_{ij}$ 。因此，單一樣本點 $i$ 的預測類別是隨機近鄰集中其他樣本類別的某種組合，其準確率與隨機近鄰域 $C_{i}$ 中與 $i$ 同類別的 $y$ 所占的比例有關。因此，目標函數可以更好的選為：

${\frac {\partial f}{\partial A}}=-2A\sum _{i}\sum _{j\in C_{i}}p_{ij}\left(x_{ij}x_{ij}^{T}-\sum _{k}p_{ik}x_{ik}x_{ik}^{T}\right)$

這裡用到了連續梯度下降算法。

目標函數優化

最大化函數f（.）相當於最小化預測的類分布和真正的類分布之間的差距，即使兩者更接近。故目標函數和梯度可以重新寫作：

$g(A)=\sum _{i}\log \left(\sum _{j\in C_{i}}p_{ij}\right)=\sum _{i}\log(p_{i})$

${\frac {\partial g}{\partial A}}=2A\sum _{i}\left(\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-{\frac {\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}}{\sum _{j\in C_{i}}p_{ij}}}\right)$

在實際應用中運用此方法得到優化的 $A$ 與之前的方法得到的 $A$ 有相似的預測結果。

歷史和背景

鄰里成分分析是由Jacob Goldberger, Sam Roweis, Ruslan Salakhudinov和Geoff Hinton 等人在2004年在多倫多大學計算機系創建的。

參考文獻

^ J. Goldberger, S. Roweis, G. Hinton, R. Salakhutdinov. (2005) Neighbourhood Component Analysis （頁面存檔備份，存於網際網路檔案館）. Advances in Neural Information Processing Systems. 17, 513-520.

外部連結

Neighbourhood Components Analysis （頁面存檔備份，存於網際網路檔案館） (University of Toronto DCS)
nca （頁面存檔備份，存於網際網路檔案館） (C++)

[1] J. Goldberger, S. Roweis, G. Hinton, R. Salakhutdinov. (2005) Neighbourhood Component Analysis （頁面存檔備份，存於網際網路檔案館）. Advances in Neural Information Processing Systems. 17, 513-520.

[1]

定義