深入机器学习系列16-保序回归

1 保序回归

保序回归解决了下面的问题：给定包含n个数据点的序列, 怎样通过一个单调的序列来归纳这个问题。形式上，这个问题就是为了找到

大部分时候，我们会在括号前加上权重w_i。解决这个问题的一个方法就是 pool adjacent violators algorithm(PAVA) 算法。粗略的讲，PAVA算法的过程描述如下：

我们从左边的开始，右移直到我们遇到第一个违例(violation)，然后，我们用违例之前的所有y的平方替换这些y，以满足单调性。我们继续这个过程，直到我们最后到达。

2 近似保序给定一个序列，我们寻找一个近似单调估计，考虑下面的问题

在上式中，

表示正数部分，即= X.1 (x>0)。这是一个凸优化问题，处罚项处罚违反单调性（即）的邻近对。

在公式（2）中，隐含着一个假设，即使用等距的网格测量数据点。如果情况不是这样，那么可以修改惩罚项为下面的形式

表示测量得到的值。

3 近似保序算法流程

这个算法是标准PAVA算法的修改版本，它并不从数据的左端开始，而是在需要时连接相邻的点，以产生近似保序最优的顺序。相比一下，PAVA对中间的序列并不特别感兴趣，只关心最后的序列。

有下面一个引理成立。

这个引理证明的事实极大地简化了近似保序解路径（solution path）的构造。假设在参数值为lambda的情况下，有K_lambda个连接块，我们用表示。这样我们可以重写（2）为如下（3）的形式。

上面的公式，对beta求偏导，可以得到下面的次梯度公式。通过这个公式即可以求得beta。

为了符合方便，令== 0。并且，

现在假设，当lambda在一个区间内增长时，组不会改变。我们可以通过相应的lambda区分（4）。

这个公式的值本身是一个常量，它意味着上式的beta是lambda的线性函数。

随着lambda的增长，方程（5）将连续的给出解决方案的斜率直到组

改变。更加引理1，只有两个组合并时，这才会发生。m_i表示斜率，那么对于每一个i=1,...,K_lambda - 1，和合并之后得到的公式如下

因此我们可以一直移动，直到lambda “下一个”值的到来

并且合并和,其中

注意，可能有超过一对组别到达了这个最小值，在这种情况下，会组合所有满足条件的组别。公式（7）和（8）成立的条件是,i+1大于lambda，如果没有,i+1大于lambda，说明没有组别可以合并，算法将会终止。

算法的流程如下：

初始时，lambda=0，K_lambda=n,, i=1,2,...,n。对于每个i，解是

重复下面过程

通过公式（5）计算每个组的斜率

通过公式（6）计算没对相邻组的碰撞次数

如果,i+1 < lambda，终止

计算公式（7）中的临界点 ,并根据斜率更新解

对于每个i，根据公式（8）合并合适的组别（所以K_lambda^star = K_lambda - 1），并设置lambda =

4 源码分析

在1.6.x版本中，并没有实现近似保序回归，后续会实现。现在我们只介绍一般的保序回归算法实现。

4.1 实例

4.2 训练过程分析

parallelPoolAdjacentViolators方法用于实现保序回归的训练。parallelPoolAdjacentViolators方法的代码如下：

parallelPoolAdjacentViolators方法的主要实现是poolAdjacentViolators方法，该方法主要的实现过程如下：

pool方法的实现如下所示。

经过上文的处理之后，input根据中的label和feature均是按升序排列。对于拥有相同预测的点，我们只保留两个特征边界点。

最后将训练的结果保存为模型。

4.3 预测过程分析

当测试数据精确匹配一个边界，那么返回相应的特征。如果测试数据比所有边界都大或者小，那么分别返回第一个和最后一个特征。当测试数据位于两个边界之间，使用linearInterpolation方法计算特征。 这个方法是线性内插法。