LMNN(large margin nearest neighbour) 算法以及代码使用

桃扇骨 2022-05-20 08:35 117阅读 0赞

我看了论文，同时推荐简短概括，[wiki][]。

同时我对该算法概括如下：

训练：（特征空间）

首先用普通knn对所有训练节点跑一遍找出每个节点o的三近邻邻居正例（标签和o一致）

然后根据这几个节点的位置，确定一个半径Lmin，在此半径范围内的都会被认为是正例。

有那么一些反例不听话，特征会正好落在该半径范围内，这些节点就是imposter。

假如有个节点能做到半径内没有反例，那么离他最近的imposter定义了一个新的半径Lmax。

引入一个概念Largest margin = Lmax - Lmin

我把这个空间用半定矩阵转化，那么所有的节点坐标都变了。该转化的目的在于降低木变函数数值。通过不断的变化找到一个最小值。由于是凸优化问题，所以是全局最优。

目标函数的意图就在于对任一个节点，把所有的imposter推出去，并且扩大Largest Margin的距离。看出来没，和SVM概念挺像的。

目标函数看wiki，因为这个博客提供的数学公式，诶？好像没提供？

再给出代码：http://www.cs.cornell.edu/~kilian/code/lmnn/lmnn.html

我说下matlab版本的：

% function [L,Det]=lmnnCG(x,y,Kg,'Parameter1',Value1,'Parameter2',Value2,...);
    %
    % Input:
    % x = input matrix (each column is an input vector) 
    % y = labels 
    % Kg = attract Kg nearest similar labeled vectors 
    % 
    % Important Parameters:
    % outdim = (default: size(x,1)) output dimensionality
    % maxiter = maximum number of iterations (default: 1000)
    % quiet = true/false surpress output (default=false)  
    %
    %
    % Specific parameters (for experts only):
    % initL = define initial matrix L to be passed in (default initL=[])
    % thresh = termination criterion (default=1e-05)
    % single = true/false performs most computations in sigle precision (default=true)
    % GPU = true/false performs computation on GPU (default: false)
    %
    %
    % Output:
    %
    % L = linear transformation xnew=L*x
    %    
    % Det.obj = objective function over time
    % Det.nimp = number of impostors over time
    % Det.pars = all parameters used in run
    % Det.time = time needed for computation
    % Det.iter = number of iterations
    % Det.verify = verify (results of validation - if used) 
    %

那么不清楚的就是失败或者终止提供的信息了。

比如我的input matrix的维度就是800\*50000的，然后在循环了45次，且极慢之后停止了，按理说应该是1000次迭代才能停止。但是由于样本点太多了：Reached Maximum Number of Function Evaluations。问题是也不告诉我是样本点超了，还是损失函数的计算值超了。

根据wiki的公式，wiki有一句话写的比较有意思：

‘In particular, most impostor constraints are naturally satisfied and do not need to be enforced during runtime. A particularly well suited solver technique is the [working set][] method, which keeps a small set of constraints that are actively enforced and monitors the remaining (likely satisfied) constraints only occasionally to ensure correctness.’

不翻译了，只有小部分的imposter是限制条件，会使距离变化矩阵改变，使得损失函数变化。

注意函数输出的L是转换矩阵，想得到低维样本还要X\_new = X \*L;

# 部分函数解析 #

## 代码学习： ##

%计算每个样本的模长
        sum_X = sum(X .^ 2, 2);
        %不同维度相加操作的函数，DD矩阵具体每个元素：||xi-xj||2
        DD = bsxfun(@plus, sum_X, bsxfun(@plus, sum_X', -2 * (X * X')));

这是计算两个feature矩阵之间距离的方法，比起自己写的for循环，优雅且不容易出错。

举个例子：

A= rand(3,1);
    B = rand(3,3);
    %假设要计算A与B当中每个行向量差的模。也就是sum((B(i,:)-A').^2,2);i = 1:3
    sum_A = sum(A.^2);
    sum_B = sum(B.^2,2);
    DD = sum_A +sum_B - 2*B*A;
    %为什么不需要bsxfun因为2016版后不需要这个函数也可以直接扩展维度不同的矩阵，进而加减乘除。

![70][]

[wiki]: https://en.wikipedia.org/wiki/Large_margin_nearest_neighbor
[working set]: https://en.wikipedia.org/wiki/Working_set
[70]: /images/20220520/644bfec7a549499aa86575848335967b.png