第10章 降维与度量学习
10.1 k近邻学习
k-近邻(k-Nearest Neighbor,KNN)学习是一种常用的监督学习方法，其工作机制：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这个k个“邻居”的信息来进行预测
在分类任务中可使用投票法，即选择这k个样本中出现最多的类别标记作为预测结果
在回归任务中可使用平均法，即将这k个样本的实值输出标记的平均值作为预测结果
懒惰学习(lazy learning)：此类学习技术在训练阶段仅仅把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。
急切学习(eager learning)：在训练阶段对样本进行学习处理的方法
给定测试样本x，若其最近邻样本为z，则最近邻分类器出错的概率就是x与z类别标记不同的概率
P ( err ) = 1 − ∑ c ∈ y P ( c ∣ x ) P ( c ∣ z ) P\left( \text{err} \right) = 1 - \sum_{c \in y}^{}{P\left( c \middle| x \right)P\left( c \middle| z \right)} P(err)=1−c∈y∑P(c∣x)P(c∣z)
假设样本独立同分布，且对任意x和任意小正数 δ \delta δ，在x附近 δ \delta δ距离范围内总能找到一个训练样本。
P ( err ) = 1 − ∑ c ∈ y P ( c ∣ x ) P ( c ∣ z ) P\left( \text{err} \right) = 1 - \sum_{c \in y}^{}{P\left( c \middle| x \right)P\left( c \middle| z \right)} P(err)=1−c∈y∑P(c∣x)P(c∣z)
≃ 1 − ∑ c ∈ y P 2 ( c ∣ x ) \simeq 1 - \sum_{c \in y}^{}{P^{2}\left( c \middle| x \right)} ≃1−c∈y∑P2(c∣x)
≤ 1 − P 2 ( c ∗ ∣ x ) \leq 1 - P^{2}\left( c^{*} \middle| x \right) ≤1−P2(c∗∣x)
= ( 1 + P ( c ∗ ∣ x ) ) ( 1 − P ( c ∗ ∣ x ) ) = \left( 1 + P\left( c^{*} \middle| x \right) \right)\left( 1 - P\left( c^{*} \middle| x \right) \right) =(1+P(c∗∣x))(1−P(c∗∣x))
≤ 2 × ( 1 − P ( c ∗ ∣ x ) ) \leq 2 \times \left( 1 - P\left( c^{*} \middle| x \right) \right) ≤2×(1−P(c∗∣x))
10.2 低维嵌入
训练样本的采样密度足够大或称为密采样(dense sample)
维度灾难(curse of dimensionality)：在高维情形下出现的数据样本稀疏、距离计算困难等问题
维数约简：缓解维数灾难的一个重要途径是降维(dimension reduction)，即通过某种数学变换将原始高维属性空间转变为一个低维子空间
若要求原始空间中的样本之间的距离在低维空间得以保持，即得到多维缩放(Multiple
Dimensional Scaling, MDS)
假定m个样本在原始空间的距离矩阵为 D ∈ R m × m D \in \mathbb{R}^{m \times m} D∈Rm×m，其第i行j列的元素 dist ij \text{dist}_{\text{ij}} distij为样本 x i x_{i} xi到 x j x_{j} xj的距离。
目标：获得样本在 d ′ d^{'} d′维空间表示 Z ∈ R d ′ × m , d ′ ≤ d Z \in \mathbb{R}^{d^{'} \times m},d^{'} \leq d Z∈Rd′×m,d′≤d，且任意两个样本在 d ′ d^{'} d′维空间中的欧式距离等于原始空间中的距离，即 ∥ z i − z j ∥ = dist ij \left\| z_{i} - z_{j} \right\| = \text{dist}_{\text{ij}} ∥zi−zj∥=distij
令 B = Z T Z ∈ R m × m B = Z^{T}Z \in \mathbb{R}^{m \times m} B=ZTZ∈Rm×m，其中B为降维后样本的内积矩阵， b ij = z i T z j b_{\text{ij}} = z_{i}^{T}z_{j} bij=ziTzj，有
dist ij 2 = ∥ z i ∥ 2 + ∥ z j ∥ 2 − 2 z i T z j = b ii + b jj − 2 b ij \text{dist}_{\text{ij}}^{2} = \left\| z_{i} \right\|^{2} + \left\| z_{j} \right\|^{2} - 2z_{i}^{T}z_{j} = b_{\text{ii}} + b_{\text{jj}} - 2b_{\text{ij}} distij2=∥zi∥2+∥zj∥2−2ziTzj=bii+bjj−2bij
令降维后的样本Z被中心化，即 ∑ i = 1 m z i = 0 \sum_{i = 1}^{m}{z_{i} = 0} ∑i=1mzi=0，则矩阵B的行和列之和均为零，即 ∑ i = 1 m b ij = ∑ j = 1 m b ij = 0 \sum_{i = 1}^{m}{b_{\text{ij}} = \sum_{j = 1}^{m}{b_{\text{ij}} = 0}} ∑i=1mbij=∑j=1mbij=0，则
∑ i = 1 m dist ij 2 = tr ( B ) + m b jj \sum_{i = 1}^{m}{\text{dist}_{\text{ij}}^{2} = \text{tr}\left( B \right) + mb_{\text{jj}}} i=1∑mdistij2=tr(B)+mbjj
∑ j = 1 m dist ij 2 = tr ( B ) + m b ii \sum_{j = 1}^{m}{\text{dist}_{\text{ij}}^{2} = \text{tr}\left( B \right) + mb_{\text{ii}}} j=1∑mdistij2=tr(B)+mbii
∑ i = 1 m ∑ j = 1 m dist ij 2 = 2 m tr ( B ) \sum_{i = 1}^{m}{\sum_{j = 1}^{m}{\text{dist}_{\text{ij}}^{2} = 2m\text{tr}\left( B \right)}} i=1∑mj=1∑mdistij2=2mtr(B)
其中 tr ( . ) \text{tr}\left( . \right) tr(.)表示矩阵的迹(trace)， tr ( B ) = ∑ i = 1 m ∥ z i ∥ 2 \text{tr}\left( B \right) = \sum_{i = 1}^{m}\left\| z_{i} \right\|^{2} tr(B)=∑i=1m∥zi∥2。令
dist i 2 = 1 m ∑ j = 1 m dist ij 2 \text{dist}_{i}^{2} = \frac{1}{m}\sum_{j = 1}^{m}\text{dist}_{\text{ij}}^{2} disti2=m1j=1∑mdistij2
dist j 2 = 1 m ∑ i = 1 m dist ij 2 \text{dist}_{j}^{2} = \frac{1}{m}\sum_{i = 1}^{m}\text{dist}_{\text{ij}}^{2} distj2=m1i=1∑mdistij2
dist .. 2 = 1 m 2 ∑ i = 1 m ∑ j = 1 m dist ij 2 \text{dist}_{\text{..}}^{2} = \frac{1}{m^{2}}\sum_{i = 1}^{m}{\sum_{j = 1}^{m}\text{dist}_{\text{ij}}^{2}} dist..2=m21i=1∑mj=1∑mdistij2
则
b ij = − 1 2 ( dist ij 2 − dist i. 2 − dist .j 2 + dist .. 2 ) b_{\text{ij}} = - \frac{1}{2}\left( \text{dist}_{\text{ij}}^{2} - \text{dist}_{\text{i.}}^{2} - \text{dist}_{\text{.j}}^{2} + \text{dist}_{\text{..}}^{2} \right) bij=−21(distij2−disti.2−dist.j2+dist..2)
由此即可通过降维前后保持不变的距离矩阵D求取内积矩阵B
对矩阵B做特征值分解(eigenvalue decomposition)， B = V Λ V T B = V\Lambda V^{T} B=VΛVT，其中 Λ = d i a g ( λ 1 , λ 2 , … , λ d ) \Lambda = diag\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{d} \right) Λ=diag(λ1,λ2,…,λd)为特征构成的对角矩阵， λ 1 ≥ λ 2 ≥ … ≥ λ d \lambda_{1} \geq \lambda_{2} \geq \ldots{\geq \lambda}_{d} λ1≥λ2≥…≥λd，V为特征向量矩阵。假定其中有 d ∗ d^{*} d∗个非零特征值，它们构成对角矩阵 Λ ∗ = d i a g ( λ 1 , λ 2 , … , λ d ∗ ) \Lambda_{*} = diag\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{d^{*}} \right) Λ∗=diag(λ1,λ2,…,λd∗)，令 Λ ∗ \Lambda_{*} Λ∗表示相应的特征向量矩阵，则Z可表达为
Z = Λ ∗ 1 2 V ∗ T ∈ R d ∗ × m Z = \Lambda_{*}^{\frac{1}{2}}V_{*}^{T} \in \mathbb{R}^{d^{*} \times m} Z=Λ∗21V∗T∈Rd∗×m
此时可取 d ′ ≪ d d^{'} \ll d d′≪d个最大特征值构成对角矩阵 Λ ~ = dia g ( λ 1 , λ 2 , … , λ d ′ ) \tilde{\Lambda} = \text{dia}g\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{d^{'}} \right) Λ~=diag(λ1,λ2,…,λd′)，令 V ~ \tilde{V} V~表示相应的特征向量矩阵，则
Z = Λ ~ 1 2 V ~ T ∈ R d ′ × m Z = {\tilde{\Lambda}}^{\frac{1}{2}}{\tilde{V}}^{T} \in \mathbb{R}^{d^{'} \times m} Z=Λ~21V~T∈Rd′×m
10.3 主成分分析
主成分分析(Principal Component Analysis, PCA)是最常用的一种降维方法。
最大重构性：样本点到这个超平面的距离都足够近
最大可分性：样本点在这个超平面上的投影能尽可能分开
假定数据样本进行中性化，即 ∑ i x i = 0 \sum_{i}^{}{x_{i} = 0} ∑ixi=0；再假定投影变换后得到的新坐标系为 { ω 1 , ω 2 , … , ω d } \left\{ \omega_{1},\omega_{2},\ldots,\omega_{d} \right\} {ω1,ω2,…,ωd}，其中 ω i \omega_{i} ωi是标准正交基向量， ∥ ω i ∥ 2 = 1 , ω i T ω j = 0 ( i ≠ j ) \left\| \omega_{i} \right\|_{2} = 1,\omega_{i}^{T}\omega_{j} = 0\left( i \neq j \right) ∥ωi∥2=1,ωiTωj=0(i̸=j)，将维度降低到 d ′ < d d^{'} < d d′<d，则样本点 x i x_{i} xi在低维坐标系中的投影为 z i = ( z i 1 ; z i 2 ; … ; z id ′ ) z_{i} = \left( z_{i1};z_{i2};\ldots;z_{\text{id}^{'}} \right) zi=(zi1;zi2;…;zid′)，其中 z i j = ω j T x i z_{ij} = \omega_{j}^{T}x_{i} zij=ωjTxi是 x i x_{i} xi在低维坐标系下第j维的坐标。若基于 z i z_{i} zi来重构 x i x_{i} xi，则会得到 x ^ i = ∑ j = 1 d ′ z ij ω j {\hat{x}}_{i} = \sum_{j = 1}^{d^{'}}{z_{\text{ij}}\omega_{j}} x^i=∑j=1d′zijωj。
考虑整个训练集，原样本点 x i x_{i} xi与基于投影重构的样本点 x ^ i {\hat{x}}_{i} x^i之间的距离为
∑ i = 1 m ∥ ∑ j = 1 d ′ z ij ω j − x i ∥ 2 2 = ∑ i = 1 m z i T z i − 2 ∑ i = 1 m z i T W T x i \sum_{i = 1}^{m}\left\| \sum_{j = 1}^{d^{'}}{z_{\text{ij}}\omega_{j} -}x_{i} \right\|_{2}^{2} = \sum_{i = 1}^{m}z_{i}^{T}z_{i} - 2\sum_{i = 1}^{m}{z_{i}^{T}W^{T}x_{i}} i=1∑m∥∥∥∥∥∥j=1∑d′zijωj−xi∥∥∥∥∥∥22=i=1∑mziTzi−2i=1∑mziTWTxi
+ c o n s t ∝ − tr ( W T ( ∑ i = 1 m x i x i T ) W ) + const \propto - \text{tr}\left( W^{T}\left( \sum_{i = 1}^{m}{x_{i}x_{i}^{T}} \right)W \right) +const∝−tr(WT(i=1∑mxixiT)W)
其中 W = ( ω 1 , ω 2 , … , ω d ) W = \left( \omega_{1},\omega_{2},\ldots,\omega_{d} \right) W=(ω1,ω2,…,ωd)。根据最近重构性，上式应被最小化，考虑到 ω j \omega_{j} ωj是标准正交基， ∑ i = 1 m x i T x i \sum_{i = 1}^{m}x_{i}^{T}x_{i} ∑i=1mxiTxi是协方差矩阵，优化目标有
投影后样本点的方差是 ∑ i = 1 m W T x i x i T W \sum_{i = 1}^{m}{{W^{T}x}_{i}x_{i}^{T}}W ∑i=1mWTxixiTW，则
使用拉格朗日乘子法有
X X T ω i = λ i ω i XX^{T}\omega_{i} = \lambda_{i}\omega_{i} XXTωi=λiωi
只需要对协方差矩阵 X X T XX^{T} XXT进行特征值分解。将求得的特征值排序 λ 1 ≥ λ 2 ≥ , … , ≥ λ d \lambda_{1} \geq \lambda_{2} \geq ,\ldots, \geq \lambda_{d} λ1≥λ2≥,…,≥λd，再取前 d ′ d' d′个特征值对应的特征向量构成 W ∗ = ( ω 1 , ω 2 , … , ω d ′ ) W^{*} = \left( \omega_{1},\omega_{2},\ldots,\omega_{d^{'}} \right) W∗=(ω1,ω2,…,ωd′)
10.4 核化线性降维
核主成分分析(Kernelized PCA,KPCA)是一种基于核技巧对线性降维方法进行核化，是非线性降维的一种常用方法。
假定将在高维特征空间中把数据投影到由 W = ( ω 1 , ω 2 , … , ω d ) W = \left( \omega_{1},\omega_{2},\ldots,\omega_{d} \right) W=(ω1,ω2,…,ωd)确定的超平面上，则对于 ω j \omega_{j} ωj有
( ∑ i = 1 m z i z i T ) ω j = λ j ω j \left( \sum_{i = 1}^{m}{z_{i}z_{i}^{T}} \right)\omega_{j} = \lambda_{j}\omega_{j} (i=1∑mziziT)ωj=λjωj
其中 z i z_{i} zi是样本点 x i x_{i} xi在高维特征空间中的像，则
ω j = 1 λ j ( ∑ i = 1 m z i z i T ) ω j = ∑ i = 1 m z i z i T ω j λ j = ∑ i = 1 m z i α i j \omega_{j} = \frac{1}{\lambda_{j}}\left( \sum_{i = 1}^{m}{z_{i}z_{i}^{T}} \right)\omega_{j} = \sum_{i = 1}^{m}{z_{i}\frac{z_{i}^{T}\omega_{j}}{\lambda_{j}}} = \sum_{i = 1}^{m}{z_{i}\alpha_{i}^{j}} ωj=λj1(i=1∑mziziT)ωj=i=1∑mziλjziTωj=i=1∑mziαij
其中 α i j = 1 λ j z i T ω j \alpha_{i}^{j} = \frac{1}{\lambda_{j}}z_{i}^{T}\omega_{j} αij=λj1ziTωj是 α i \alpha_{i} αi的第j个分量。
假定 z i z_{i} zi是由原始属性空间中的样本点 x i x_{i} xi通过映射 ϕ \phi ϕ产生，即 z i = ϕ ( x i ) , i = 1 , 2 , … , m z_{i} = \phi\left( x_{i} \right),i = 1,2,\ldots,m zi=ϕ(xi),i=1,2,…,m，若 ϕ \phi ϕ能被显式表达出来，则
( ∑ i = 1 m ϕ ( x i ) ϕ ( x i ) T ) ω j = λ j ω j \left( \sum_{i = 1}^{m}{\phi\left( x_{i} \right){\phi\left( x_{i} \right)}^{T}} \right)\omega_{j} = \lambda_{j}\omega_{j} (i=1∑mϕ(xi)ϕ(xi)T)ωj=λjωj
ω j = ∑ i = 1 m ϕ ( x i ) α i j \omega_{j} = \sum_{i = 1}^{m}{\phi\left( x_{i} \right)\alpha}_{i}^{j} ωj=i=1∑mϕ(xi)αij
引入核函数：
K ( x i x j ) = ϕ ( x i ) T ϕ ( x i ) \mathcal{K}\left( x_{i}x_{j} \right) = {\phi\left( x_{i} \right)}^{T}\phi\left( x_{i} \right) K(xixj)=ϕ(xi)Tϕ(xi)
则化简为
K α j = λ j α j K\alpha^{j} = \lambda_{j}\alpha^{j} Kαj=λjαj
其中K为 K \mathcal{K} K对应的核矩阵， ( K ) ij = K ( x i x j ) , α j = ( α 1 j ; α 2 j ; … ; α m j ) \left( K \right)_{\text{ij}} = \mathcal{K}\left( x_{i}x_{j} \right),\alpha^{j} = \left( \alpha_{1}^{j};\alpha_{2}^{j};\ldots;\alpha_{m}^{j} \right) (K)ij=K(xixj),αj=(α1j;α2j;…;αmj)
对新样本x，其投影后的第 j ( j = 1 , 2 , … , d ′ ) j(j = 1,2,\ldots,d') j(j=1,2,…,d′)维坐标为
z i = ω j T ϕ ( x ) = ∑ i = 1 m α i j ϕ ( x ) T ϕ ( x ) = ∑ i = 1 m α i j K ( x i , x j ) z_{i} = \omega_{j}^{T}\phi\left( x \right) = \sum_{i = 1}^{m}\alpha_{i}^{j}{\phi\left( x \right)}^{T}\phi\left( x \right) = \sum_{i = 1}^{m}{\alpha_{i}^{j}\mathcal{K}\left( x_{i,}x_{j} \right)} zi=ωjTϕ(x)=i=1∑mαijϕ(x)Tϕ(x)=i=1∑mαijK(xi,xj)
10.5 流形学习
流形学习(manifold learning)是一类借鉴了拓扑流形概念的降维方法。在局部具有欧式空间的性质，能用欧式距离历来进行距离计算。
10.5.1 等度量映射
等度量映射(Isometric Mapping,Isomap)基本出发点是低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性。
每个点基于欧式距离找出其近邻点，然后就能建立一个近邻连接图，图中近邻点之间存在连接，而非近邻点之间不存在连接。计算两点之间测地线距离的问题，就转变为计算近邻连接图上两点之间的最短路径问题。
对近邻图的构建通常的方法：指定近邻点个数或指定距离阈值 ϵ \epsilon ϵ
15.5.2 局部线性嵌入
局部线性嵌入(Locally Linear Embedding, LLE)试图保持领域内样本之间的线性关系。
假定样本点 x i x_{i} xi的坐标能通过它的领域样本 x j , x k , x l x_{j},x_{k},x_{l} xj,xk,xl的坐标通过线性组合而重构，即
x i = ω ij x j + ω i k x k + ω i l x l x_{i} = \omega_{\text{ij}}x_{j} + \omega_{ik}x_{k} + \omega_{il}x_{l} xi=ωijxj+ωikxk+ωilxl
LLE先为每个样本 x i x_{i} xi找到其近邻下标集合 Q i Q_{i} Qi，然后计算出基于 Q i Q_{i} Qi中的样本点 x i x_{i} xi进行线性重构的系数 ω i \omega_{i} ωi：
其中 x i x_{i} xi和 x j x_{j} xj均为已知，令 C jk = ( x i − x j ) T ( x i − x k ) C_{\text{jk}} = \left( x_{i} - x_{j} \right)^{T}\left( x_{i} - x_{k} \right) Cjk=(xi−xj)T(xi−xk)有闭解
ω ij = ∑ k ∈ Q i C jk − 1 ∑ l , s ∈ Q i C ls − 1 \omega_{\text{ij}} = \frac{\sum_{k \in Q_{i}}^{}C_{\text{jk}}^{- 1}}{\sum_{l,s \in Q_{i}}^{}C_{\text{ls}}^{- 1}} ωij=∑l,s∈QiCls−1∑k∈QiCjk−1
LLE在低维空间中保持 ω i \omega_{i} ωi不变，于是 x i x_{i} xi对应的低维空间坐标 z i z_{i} zi可通过下式求解：
令 Z = z 1 , z 2 , … , z m ∈ R d ′ × m , ( W ) ij = ω ij Z = z_{1},z_{2},\ldots,z_{m} \in \mathbb{R}^{d^{'} \times m},\left( W \right)_{\text{ij}} = \omega_{\text{ij}} Z=z1,z2,…,zm∈Rd′×m,(W)ij=ωij，则
M = ( I − M ) T ( I − M ) M = \left( I - M \right)^{T}\left( I - M \right) M=(I−M)T(I−M)
则
可通过特征值分解求解：M最小的 d ′ d' d′个特征值对应的特征向量组成的矩阵即为 Z T Z^{T} ZT
10.6 度量学习
度量学习(metric learning)的基本动机：寻找一个合适的距离度量。
对两个的维度样本 x i x_{i} xi和 x j x_{j} xj,它们之间的平方欧式距离为
dist ed 2 ( x i , x j ) = ∥ x i − x j ∥ 2 2 = dist i j , 1 2 + dist i j , 2 2 + … + dist i j , d 2 \text{dist}_{\text{ed}}^{2}\left( x_{i},x_{j} \right) = \left\| x_{i} - x_{j} \right\|_{2}^{2} = \text{dist}_{ij,1}^{2} + \text{dist}_{ij,2}^{2} + \ldots + \text{dist}_{ij,d}^{2} disted2(xi,xj)=∥xi−xj∥22=distij,12+distij,22+…+distij,d2
其中 dist i j , k \text{dist}_{ij,k} distij,k表示 x i x_{i} xi和 x j x_{j} xj在第k维上的距离。
若假定不同属性的重要性不同，则可引入属性权重 ω \omega ω，得到
dist ed 2 ( x i , x j ) = ∥ x i − x j ∥ 2 2 = ω 1 ∙ dist i j , 1 2 + ω 2 ∙ dist i j , 2 2 + … + ω d ∙ dist i j , d 2 = ( x i − x j ) T W ( x i − x j ) \text{dist}_{\text{ed}}^{2}\left( x_{i},x_{j} \right) = \left\| x_{i} - x_{j} \right\|_{2}^{2} = {\omega_{1} \bullet \text{dist}}_{ij,1}^{2} + \omega_{2} \bullet \text{dist}_{ij,2}^{2} + \ldots + \omega_{d} \bullet \text{dist}_{ij,d}^{2} = \left( x_{i} - x_{j} \right)^{T}W\left( x_{i} - x_{j} \right) disted2(xi,xj)=∥xi−xj∥22=ω1∙distij,12+ω2∙distij,22+…+ωd∙distij,d2=(xi−xj)TW(xi−xj)
将上式中的M替换为一个普通的半定对称矩阵M，得到马氏距离(Mahalanobis distance)：
dist mah 2 ( x i , x j ) = ( x i − x j ) T M ( x i − x j ) = ∥ x i − x j ∥ M 2 \text{dist}_{\text{mah}}^{2}\left( x_{i},x_{j} \right) = \left( x_{i} - x_{j} \right)^{T}M\left( x_{i} - x_{j} \right) = \left\| x_{i} - x_{j} \right\|_{M}^{2} distmah2(xi,xj)=(xi−xj)TM(xi−xj)=∥xi−xj∥M2
其中M亦称度量矩阵。M必须是正定对称矩阵，即必有正交基P使得M能写为 M = P P T M = PP^{T} M=PPT
近邻成分分析(Neighborhood Component Analysis, NCA)
对任意样本 x j x_{j} xj，它对 x i x_{i} xi分类结果影响的概率为
p ij = exp ( − ∥ x i − x j ∥ M 2 ) ∑ l exp ( − ∥ x i − x l ∥ M 2 ) p_{\text{ij}} = \frac{\exp\left( - \left\| x_{i} - x_{j} \right\|_{M}^{2} \right)}{\sum_{l}^{}{\exp\left( - \left\| x_{i} - x_{l} \right\|_{M}^{2} \right)}} pij=∑lexp(−∥xi−xl∥M2)exp(−∥xi−xj∥M2)
若以留一法正确率的最大化为目标，被自身之外的所有样本正确分类的概率为
p i = ∑ j ∈ Ω i p ij p_{i} = \sum_{j \in \Omega_{i}}^{}p_{\text{ij}} pi=j∈Ωi∑pij
其中 Ω i \Omega_{i} Ωi表示与 x i x_{i} xi属于相同类别的样本的下标集合，则整个样本集上的留一法正确率为
∑ i = 1 m p i = ∑ i = 1 m ∑ j ∈ Ω i p ij \sum_{i = 1}^{m}{p_{i} = \sum_{i = 1}^{m}{\sum_{j \in \Omega_{i}}^{}p_{\text{ij}}}} i=1∑mpi=i=1∑mj∈Ωi∑pij
则NCA的优化目标为
通过求解下面的这个凸优化问题获得适当的度量矩阵M