1.1. 广义线性模型

英文原文

以下介绍的方法均是用于求解回归问题，其目标值预计是输入变量的一个线性组合。写成数学语言为：假设$\hat{y}$是预测值，则有 $$\hat{y}(w,x) = w_0 + w_1x_1 + \ldots w_px_p$$ 在本节中，称向量$w=(w_1,\ldots,w_p)$为coef_，{% math %}w0{% endmath %}为`intercept`

若要将通用的线性模型用于分类问题，可参见Logistic回归

1.1.1 普通最小二乘法

LinearRegression使用系数$w=(w_1,\ldots,w_p)$拟合一个线性模型。拟合的目标是要将线性逼近预测值（$Xw$）和数据集中观察到的值（$y$）两者之差的平方和尽量降到最小。写成数学公式，即是要解决以下形式的问题 $$\min_{w}{||Xw-y||_2}^2$$ LinearRegression的fit方法接受数组X和y作为输入，将线性模型的系数$w$存在成员变量coef_中：

>>> from sklearn import linear_model
>>> clf = linear_model.LinearRegression()
>>> clf.fit ([[0, 0], [1, 1], [2, 2]], [0, 1, 2])
LinearRegression(copy_X=True, fit_intercept=True, n_jobs=1, normalize=False)
>>> clf.coef_
array([ 0.5,  0.5])

需要注意的是，普通最小二乘法的系数预测取决于模型中各个项的独立性。假设各个项相关，矩阵$X$的列总体呈现出线性相关，那么$X$就会很接近奇异矩阵，其结果就是经过最小二乘得到的预测值会对原始数据中的随机误差高度敏感，从而每次预测都会产生比较大的方差。这种状况称为重共线性。例如，在数据未经实验设计就进行收集时就会发生重共线性。

线性回归的例子

1.1.1.1 普通最小二乘法的复杂度

此方法使用$X$的奇异值分解来求解最小二乘。如果$X$是$n\times p$矩阵，则算法的复杂度为$O(np^2)$，假设$n\ge p$。

1.1.2 岭回归

岭回归（Ridge regression）引入了一种对系数大小进行惩罚的措施，来解决普通最小二乘可能遇到的某些问题。岭回归最小化带有惩罚项的残差平方和： $$\min_w {||Xw-y||_2}^2 + \alpha{||w||_2}^2$$ 这里，$\alpha \ge 0$是一个复杂的参数，用以控制系数的缩减量。$\alpha$值越大，系数缩减得越多，因而会对共线性更加鲁棒。 和其它线性模型类似，Ridge将数组X和y作为fit方法的参数，将线性模型的系数$w$存在成员变量coef_中：

>>> from sklearn import linear_model
>>> clf = linear_model.Ridge (alpha = .5)
>>> clf.fit ([[0, 0], [0, 0], [1, 1]], [0, .1, 1]) 
Ridge(alpha=0.5, copy_X=True, fit_intercept=True, max_iter=None,
      normalize=False, random_state=None, solver='auto', tol=0.001)
>>> clf.coef_
array([ 0.34545455,  0.34545455])
>>> clf.intercept_ 
0.13636...

例子：

• 岭回归系数图像：一种正则化方法
• 使用稀疏特征进行文本文档分类

岭回归的时间复杂度

岭回归的复杂度与普通最小二乘法一样

使用广义交叉验证设置正则化参数

RidgeCV使用内置的交叉验证方法选择参数$\alpha$，进而实现了岭回归。该对象和GridSearchCV的原理类似，只不过RidgeCV默认使用广义交叉验证方法（留一交叉验证的一种高效形式）：

>>> from sklearn import linear_model
>>> clf = linear_model.RidgeCV(alphas=[0.1, 1.0, 10.0])
>>> clf.fit([[0, 0], [0, 0], [1, 1]], [0, .1, 1])       
RidgeCV(alphas=[0.1, 1.0, 10.0], cv=None, fit_intercept=True, scoring=None,
    normalize=False)
>>> clf.alpha_                                      
0.1

参考文献

• “Notes on Regularized Least Squares”, Rifkin & Lippert （技术报告，课程胶片）

1.1.3. Lasso

Lasso是一种预测稀疏系数的线性模型。在某些情况下，Lasso非常有用，因为其倾向于选择拥有更少参数数量的模型，从而有效减少了最终解决方案所依赖的变量个数。这样的特性使得Lasso和它的变种成为了压缩感知（compressed sensing）这一领域的基石。在特定情况下，它可以恢复非零权重的确切集合（it can recover the exact set of non-zero weights）（参见Compressive sensing: tomography reconstruction with L1 prior (Lasso)）

用数学语言讲，Lasso是一个增加了$\ell_1$正则项的线性模型。需要优化的目标函数为 $$\min_w \frac{1}{2n_\mathrm{samples}}||Xw-y||_2^2 + \alpha ||w||_1$$ 因此，Lasso是要将带有$\alpha||w||_1$这一项的最小二乘误差降到最小。这里$\alpha$是一个常数，$||w||_1$是参数向量的$\ell_1$范数

Lasso类的实现使用了坐标下降算法来拟合系数。Least Angle Regression使用了另一种实现方法。

>>> from sklearn import linear_model
>>> clf = linear_model.Lasso(alpha = 0.1)
>>> clf.fit([[0, 0], [1, 1]], [0, 1])
Lasso(alpha=0.1, copy_X=True, fit_intercept=True, max_iter=1000,
   normalize=False, positive=False, precompute=False, random_state=None,
   selection='cyclic', tol=0.0001, warm_start=False)
>>> clf.predict([[1, 1]])
array([ 0.8])

对于一些底层的任务来说，函数lasso_path也很有效。该函数沿所有可能值的全部路径计算系数

例子：

• Lasso and Elastic Net for Sparse Signals
• Compressive sensing: tomography reconstruction with L1 prior (Lasso)

注释

• 使用Lasso进行特征选择：由于Lasso回归可以给出稀疏模型，因此该方法可以用于特征选择。参见“基于L1的特征选择”了解更多细节
• 随机化稀疏：对于特征选择或稀疏性恢复，可以考虑使用随机化稀疏模型

1.1.3.1. 设定正则化参数

参数alpha用来控制所得到模型系数的系数程度

1.1.3.1.1. 使用交叉验证

使用scikit-learn提供的一些类，可以通过交叉验证的方式设置Lasso的alpha变量。这些类包括LassoCV和LassoLarsCV。其中LassoLarsCV基于下面介绍的最小角回归算法。

对于有很多共线性回归项的高维数据集来说，LassoCV更为适用。但是，LassoLarsCV的优势在于，它可以找出更多alpha的相关值，而且如果样本数量显著小于变量数量，它比LassoCV更快。

1.1.3.1.2 基于信息准则的模型选择

作为另一种可选方案，LassoLarsIC使用赤池信息量准则（AIC）和贝叶斯信息量准则（BIC）进行预测。在使用k折交叉验证方法时，该预测器只计算一遍正则化路径来寻找alpha的最优值，而不像其它预测其那样计算k+1遍。因此这种方法所需的计算资源更少。然而，这种准则需要对最终结果的自由度有一个正确预测。它是由大量样本（渐进结果）得来，而且假设模型是正确的（也就是说，数据就是由这个模型产生的）。如果所解问题badly conditioned（特征数多于样本数），那么这种方法也容易失败。

例子

• Lasso模型选择：交叉验证/AIC/BIC

1.1.4. 弹性网

弹性网（ElasticNet）同时使用L1和L2正则化项来训练线性回归模型。使用这样的组合可以得到一个稀疏模型，也就是像Lasso那样只有少量权重是非零的，同时这样的模型还能够保持Ridge的正则化特性。我们使用参数l1_ratio来控制L1和L2的凸组合。

当多个特征互相相关时，弹性网就可以派上用场。面对这样的情况，Lasso可能会随机选择一个特征，而弹性网会两个都选。

在Lasso和岭回归中选择一个平衡点的应用优势在于，它允许弹性网在轮转情况（rotation）下继承岭回归的某些稳定性。其实质是最小化如下目标函数： $$\min_w \frac{1}{2n_{\mathrm{samples}}}||Xw-y||^2_2 + \alpha \rho ||w||_1 + \frac{\alpha(1-\rho)}{2}||w||_2^2$$ ElasticNetCV类可以用来设置参数alpha({% math %}\alpha{% endmath %})和l1_ratio({% math %}\rho{% endmath %})，使用的方法仍然是交叉验证方法。

例子

• 用于稀疏信号的Lasso和弹性网
• Lasso和弹性网

1.1.5 多任务Lasso

多任务Lasso（MultiTaskLasso）对多元联合回归问题给出一个系数稀疏的线性模型。这里y是一个n_samples * n_tasks的二维数组。其限制是选出的特征对所有回归问题（也叫作任务）都一样。

下图比较了使用简单Lasso和多任务Lasso得到的权重中非零系数的位置。Lasso得到的是离散的非零点，而多任务Lasso得到的是一整列。 下图给出了两种模型对时间序列模型的拟合比较（？Fitting a time-series model, imposing that any active feature be active at all times.） 例子：

• 使用多任务Lasso进行联合特征选择

数学上讲，该模型使用了混合的{% math %}\ell1{% endmath %}和{% math %}\ell_2{% endmath %}正则项来训练线性模型，即求解下述最优函数的最小值： {% math %} \min_w \frac{1}{2n{\mathrm{samples}}}||XW-Y||^22 + \alpha ||W||{21} {% endmath %} 其中 {% math %} ||W||{21} = \sum_i \sqrt{\sum_j w{ij}^2} {% endmath %} MultiTaskLasso类的实现使用了坐标下降算法来拟合系数。

1.1.6. 最小角回归（LARS）

最小角回归（Least-angle regression (LARS)）是一种用于高维数据的回归算法，由Bradley Efron, Trevor Hastie, Iain Johnstone和Robert Tibshirani共同提出。

LARS的优点在于

• 当p>>n时（即数据集维度远大于数据数量时），计算效率很高。
• 计算速度与前向选择算法（forward selection）一样快，和普通最小二乘算法有同阶的复杂度。
• 产生的是完整的，逐步的线性求解路径，在交叉验证或其他类似模型调优时尤其有用。
• 如果两个自变量与因变量（响应变量）的相关性近乎等同，那么它们的系数应该以大致相同的速率增加。算法过程正与此直觉相符，而且更加稳定。
• 可以很容易地修改来为其它预测器（如Lasso）产生结果。

LARS的缺点包括

• LARS是对残差项迭代重拟合，因此对数据中的噪声尤其敏感。详细讨论可见Efron et al. (2004) Annals of Statistics article一文中的讨论部分（由Weisberg所写）。

可以使用Lars或者更底层的实现lars_path来训练LARS模型。

1.1.7. LARS Lasso （本小节翻译蹩脚，需要优化）

LassoLars是一种使用LARS算法实现的lasso模型。和基于坐标下降的实现不同，该模型产生确切解，是其系数范数函数的逐步线性 (which is piecewise linear as a function of the norm of its coefficients)。

>>> from sklearn import linear_model
>>> clf = linear_model.LassoLars(alpha=.1)
>>> clf.fit([[0, 0], [1, 1]], [0, 1])  
LassoLars(alpha=0.1, copy_X=True, eps=..., fit_intercept=True,
     fit_path=True, max_iter=500, normalize=True, positive=False,
     precompute='auto', verbose=False)
>>> clf.coef_    
array([ 0.717157...,  0.        ])

例子

• 使用LARS产生的Lasso路径

Lars算法给出了系数沿着正则化参数的完整路径（almost for free？），因此通常可以使用函数lars_path获得该路径。

1.1.7.1 数学表述

算法与前向逐步回归类似，但是LARS Lasso算法并不在每一步都包含变量，而是将预测到的参数沿与残差相关度同角度的方向增加。

LARS Lasso给出的不是一个向量解，而是一组解的曲线。每个解都对应于一个参数向量的L1范数。完整的系数路径存储在数组coef_path_中，大小为n_features * max_features + 1。第一列恒为0。

参考文献

• 原始算法的细节可参考Hastie等人所著的《最小角回归》一文。

1.1.8. 正交匹配追踪（Orthogonal Matching Pursuit, OMP）

OrthogonalMatchingPursuit和orthogonal_mp实现了OMP算法。该算法使用非零系数数目（即L0伪范数）作为限定条件，来拟合线性模型。

和最小角回归一样，OMP也是一个前向特征选择模型。在非零元素个数确定的情况下，该算法可以逼近最优解向量： $$\arg \min ||y-X\gamma ||_2^2\ \ \mathrm{subject}\ \mathrm{to}\ ||\gamma||_0 \le n_{\mathrm{non\_zero\_coefs}}$$ OMP也可以针对某个给定的误差值，而不用非零元素个数作为目标进行优化 $$\arg \min ||\gamma||_0\ \ \mathrm{subject}\ \mathrm{to}\ ||y-X\gamma||_2^2 \le \mathrm{tol}$$ OMP是一种贪心算法，在每一步都选择和当前残差最相关的项。它与简单匹配追踪方法（MP）相似，但是在每步迭代中的表现都更好一些。因为每步中残差都使用到之前选择的字典元素所组成空间的正交投影重新计算。

例子

• 正交匹配追踪

参考文献

• http://www.cs.technion.ac.il/~ronrubin/Publications/KSVD-OMP-v2.pdf
• Matching pursuits with time-frequency dictionaries, S. G. Mallat, Z. Zhang,

1.1.9. 贝叶斯回归

使用贝叶斯回归技术，可以在预测阶段就将正则项参数包括进来：正则化参数不再是一个被写死的固定值，而是可以根据手头数据调优。

达到这一效果的方法是引入模型超越参数上的无信息先验。岭回归中使用的$\ell_2$正则项所起到的作用在于，在参数集$w$上的高斯先验下寻找一个准确度为$\lambda^{-1}$的最大化后验的解。这个解可以被看作是可从数据中预测的随机变量，而不用手动去设置$\lambda$。

为了得到一个完整的概率模型，我们假设输出$y$是关于$Xw$的高斯分布： $$p(y|X,w,\alpha) = \mathcal{N}(y|Xw, \alpha)$$ 其中$\alpha$是从数据中预测的随机变量。

贝叶斯回归的优点在于：

• 适应于手头数据
• 可以用来在预测阶段就将正则参数包含进来

其缺点在于

• 模型推导会比较花时间

参考文献

• Bishop的经典著作PRML中有关于贝叶斯方法的很好介绍
• 原始算法细节可见Radford M. Neal所著Bayesian learning for neural networks一书

1.1.9.1. 贝叶斯岭回归

BayesianRidge使用上述原理对给定的回归问题建立概率模型。参数$w$的先验分布由球面高斯分布（spherical Gaussian）给出： $$p(w|\lambda) = \mathcal{N}(w|0, \lambda^{-1}\mathbf{I_p})$$ $\alpha$和$\lambda$上的分布由$\Gamma$-分布给出。

得到的模型称为贝叶斯岭回归，其与经典的岭回归模型Ridge类似。参数$w$, $\alpha$和$\lambda$在拟合模型的过程中联合求得。剩余的超越参数是$\alpha$和$\lambda$上$\Gamma$分布的参数，通常被选作是无信息的。这些参数通过最大化边际对数似然（marginal log likelihood）得到。默认值是$\alpha_1 = \alpha_2 = \lambda_1 = \lambda_2 = 1 \times e^{-6}$

贝叶斯岭回归可以被用于回归分析：

>>> from sklearn import linear_model
>>> X = [[0., 0.], [1., 1.], [2., 2.], [3., 3.]]
>>> Y = [0., 1., 2., 3.]
>>> clf = linear_model.BayesianRidge()
>>> clf.fit(X, Y)
BayesianRidge(alpha_1=1e-06, alpha_2=1e-06, compute_score=False, copy_X=True,
       fit_intercept=True, lambda_1=1e-06, lambda_2=1e-06, n_iter=300,
       normalize=False, tol=0.001, verbose=False)

训练后，模型可以用来预测新值：

>>> clf.predict ([[1, 0.]])
array([ 0.50000013])

通过变量coef_获取系数$w$：

>>> clf.coef_
array([ 0.49999993,  0.49999993])

由于贝叶斯框架的原因，该方法得到的权重与通过普通最小二乘得到的参数略有差别。不过贝叶斯岭回归对ill-posed问题有更强的鲁棒性。

例子

• 贝叶斯岭回归

参考文献

• 更多细节可参考MacKay, David J. C.所著Bayesian Interpolation一文

1.1.9.2. 自动相关判定（Automatic Relevance Determination, ARD）

ARDRegression和贝叶斯岭回归很像，但是会得到更稀疏的$w$[1][2]。ARDRegression使用了一个不同的$w$的先验分布：它不再假设高斯分布是球面的，而是认为是平行于坐标轴的椭球形高斯分布。这意味着每个从高斯分布得到的权重$w_i$都以0位中心，精确度为$\lambda_i$。 $$p(w|\lambda) = \mathcal{N}(w|0, A^{-1})$$ 与贝叶斯岭回归不同的是，每个权重$w_i$都有自己的标准差$\lambda_i$。所有$\lambda_i$上的先验分布与给定超越参数$\lambda_1$和$\lambda_2$的$\Gamma$分布相同。 例子

• 自动相关判定回归(ARD)

参考文献

• [1] Christopher M. Bishop: Pattern Recognition and Machine Learning, Chapter 7.2.1
• [2] David Wipf & Srikantan Nagarajan: A new view of autonomic relevance determination

1.1.10. Logistic回归

虽然名字中带着“回归”两字，但实际上Logistic回归一般是用来解决分类问题，而不是回归问题。在文献中，该方法也被称为“Logit回归”、“最大熵分类（MaxEnt）”或者“对数-线性分类器”。该模型使用logistic函数对给定样本属于不同类别的概率进行建模。

Scikit-learn使用LogisticRegression实现Logistic回归。可以通过该实现拟合一个多类别（一对多）Logistic回归模型。拟合时还可以根据需要选择是否增加L1或者L2惩罚项。

从优化问题的角度看，带有L2正则项的二元Logistic回归是要求解下式 $$\min_{w,c}\frac{1}{2}w^Tw + C\sum_{i=1}^n \log(\exp(-y_i(X_i^Tw+c)) + 1)$$ 类似的，如果是使用L1正则项，则是求解 $$\min_{w,c}||w||_1 + C\sum_{i=1}^n \log(\exp(-y_i(X_i^Tw+c)) + 1)$$ LogisticRegresssion实现的求解器有“liblinear”（C++库LIBLINEAR）的封装、“newton-cg”、“lbfgs“和”sag“。其中“newton-cg”和“lbfgs“只支持L2惩罚项，这两个求解器在某些高维数据上收敛更快。使用L1惩罚项会得到稀疏的预测系数。

求解器“liblinear”在Liblinear的基础上实现了坐标下降（CD）算法。对于L1惩罚项，可以使用sklearn.svm.l1_min_c来计算C的一个更深的下界，以得到一个非“空”（这里“空”的意思是所有特征的权重都为0）模型。该实现得益于底层出色的LIBLINEAR库。然而，liblinear实现的坐标下降算法不能够学到一个真正的多项（多类别）模型；而是把优化问题分解为多个一对多问题，所以会对每个类别各自训练一个二元分类器。不过这些分解都是在底层进行，对用户透明，因此LogisticRegression使用这个求解器作为多类别分类器（？）。

使用LogisticRegression时，将solver设成“lbfgs”或者“newton-cg”，并将multi_class设为“multinomial”，可以学习到一个真正的多项logistic回归模型。这意味着使用该模型预测得到的概率应该会比默认的一对多方法得到的结果准确度更高。然而这两个求解器（以及“sag”）不能优化带有L1惩罚项的模型，因此“multinomial”不能学到稀疏模型。

“sag”求解器使用了随机平均梯度下降算法[3]。它不能处理多类别问题，而且只能使用带有L2惩罚项的模型。但是在大数据集上（样本量和特征数都很大的情况下）它比其它求解器要快。

简而言之，下表给出了一个粗略的求解器选择标准

对于大数据集，也可以考虑使用SGDClassifier，该分类器使用了“对数”损失函数。

例子

• Logistic回归中的L1惩罚项与稀疏性
• L1-线性回归的路径

与liblinear的不同

如果将fit_intercept设为False，而且拟合出的coef_（或）被预测的数据为0，则设置了solver=liblinear的LogicRegression或LinearSVC得到的得分与直接使用底层外部库得到的得分会有差别。因为对于decision_function值为0的样本，LogicRegression和LinearSVC将其划分为负类，而liblinear库划分为正类。需要注意的是，如果出现了这种情况（即设置fit_intercept为False且很多样本的decision_function值为0）通常意味着产生了欠拟合，得到的模型不是一个好模型。在这种情况下，建议将fit_intercept设为True并增大intercept_scaling。

注解：使用稀疏Logistic回归进行特征选择

使用L1惩罚项的logistic回归会得到稀疏模型，因此可以用来进行特征选择。细节可参见基于L1的特征选择。

LogisticRegressionCV同样实现了Logistic回归。该类是使用了自带的交叉验证方法来找到最优的C。由于“暖启动”机制，“newton-cg”、“sag”和“lbfgs”求解器在高维密集数据上速度更快。对于多类别问题，如果参数multi_class被设成ovr，是对每个类别获得一个最优的C；如果被设成Multinomial，则最优的C使得交叉熵损失（cross-entropy loss）最小。

参考文献： [3]. Mark Schmidt, Nicolas Le Roux, and Francis Bach: Minimizing Finite Sums with the Stochastic Average Gradient.

1.1.11. 随机梯度下降（SGD）

随机梯度下降是一种简单但是非常有效的拟合线性模型的方法。当样本数（以及特征数）非常大时该方法尤其有效。partial_fit方法支持在线/核外学习。

SGDClassifier和SGDRegressor允许用户使用不同的（凸）损失函数和不同的惩罚项，分别针对分类问题和回归问题训练线性模型。例如将loss设为“log”，则SGDClassifier会拟合一个logistic回归模型；设成“hinge”则拟合一个线性支持向量机（SVM）。

参考文献

• 随机梯度下降

1.1.12. 感知机

Perceptron是另一种适用于大规模学习的简单算法。默认情况下：

• 该算法不需要学习率
• 该算法不被正则化
• 该算法只有在遇到错误的情况下才更新模型

最后一个特征表明感知机比使用合页损失函数（hinge loss）的SGD训练起来要快，而且得到的模型更稀疏。

1.1.13. 被动攻击算法（Passive Aggressive Algorithm）

被动攻击算法是一种适用于大规模学习的算法。它们与感知机类似的地方是也不需要设置学习率。但是不同在于这些算法会包含一个正则项参数C。

对于分类问题，可以使用PassiveAggressiveClassifier，其中损失函数loss可以设为“hinge”（PA-I）或者“squared_hinge”（PA-II）。对于回归问it，可以使用PassiveAggressiveRegressor，其中损失函数loss可以设为“epsilon_insensitive”（PA-I）或者“squared_epsilon_insensitive”（PA-II）。

参考文献

• K. Crammer, O. Dekel, J. Keshat, S. Shalev-Shwartz, Y. Singer, "Online Passive-Aggressive Algorithms", JMLR 7, 2006

1.1.14. 稳健回归（鲁棒回归）：异常值与模型误差

稳健回归所着力解决的问题是，如果数据中有坏点（或是异常值或是模型中的误差），如何拟合回归模型。

1.1.14.1. 不同的场景和一些有用的概念

处理带异常值的数据时，有些事情要谨记于心

• 异常值出现在X中还是在y中？
• 异常值比例 vs. 误差偏移量

异常点个数对模型影响很大，但是偏差多少也很重要

An important notion of robust fitting is that of breakdown point: the fraction of data that can be outlying for the fit to start missing the inlying data.

需要注意的是，稳健拟合在高维度数据集（特征个数很大的数据集）中很难实现。稳健模型在这些情况下可能不会工作。

综合考虑：使用哪个预测器？

Scikit-learn提供两种稳健回归预测器：RANSAC和Theil Sen

• RANSAC更快，样本数量变大时规模可扩展性更好（译者认为，可以看作是对更大的样本量表现更好）。
• 如果在X轴方向出现了中等大小的异常值，则Theil Sen表现更好。但是如果数据维度太高，这样的优势就没有了。

如果不知道该用哪个，就用RANSAC。

1.1.14.2. RANSAC: 随机抽样一致性算法

RANSAC（随机抽样一致性算法）从完整的数据集中随机选择一个由正常点组成的子集，并在该子集上拟合模型。

RANSAC是一种非确定性算法，仅以特定概率（依赖于迭代次数，即参数max_trials）产生一个比较合理的结果。该算法对线性回归和非线性回归问题都适用，在摄影测量计算机视觉（photogrammetric computer vision）这个领域中尤其受欢迎。

该算法将完整的输入样本集分成一系列正常值（可能受到噪声影响）和异常值（因错误的测量手段或对数据的非法假设而产生）。最终只使用得到的正常值拟合模型。

1.1.14.2.1. 算法细节

在每次迭代中都完成以下工作

1. 从原始数据中随机选择min_samples个样本，检查数据集是否合法（参看is_data_valid。
2. 在这个随机得到的数据集上拟合模型，检查得到的模型是否合法（参看is_model_valid）。
3. 对每条数据，计算对应y与模型预测值的残差（base_estimator.predict(X)-y），判断数据是正常点还是异常点。所有残差绝对值小于阈值residual_threshold的数据都被认为是正常点。
4. 如果当前得到的正常值数量是开始迭代以来最高的（严格好于之前的最大值），则把该模型设为当前最佳模型。

迭代停止的条件为达到最大迭代次数（max_trials）或者满足其它指定的终止条件（见stop_n_inliers和stop_score）。最终模型使用之前得到的最佳模型里的正常值（一致集）进行拟合。

函数is_data_valid和is_model_valid允许开发人员发现和舍弃随机子样本的退化组合。如果预测模型不需要找出退化情况，则仍然要使用is_data_valid。因为这个函数在模型拟合之前被调用，可以提高计算性能。

例子

• 使用RANSAC进行稳健线性模型预测
• 稳健线性预测器拟合

参考文献

• http://en.wikipedia.org/wiki/RANSAC
• “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography” Martin A. Fischler and Robert C. Bolles - SRI International (1981)
• “Performance Evaluation of RANSAC Family” Sunglok Choi, Taemin Kim and Wonpil Yu - BMVC (2009)

1.1.14.3. Theil-Sen预测器：基于广义中位数的预测器

TheilSenRegressor模型使用了高维空间中的广义中位数，因此对多变量异常值是鲁棒的。需要注意的是，即便如此，该模型的鲁棒性还是会随着求解问题维度的增加而快速减少。在高维空间中，它的鲁棒性会越来越差，最后不比普通最小二乘强多少。

例子：

• Theil-Sen回归
• 稳健线性预测器拟合

参考文献

• http://en.wikipedia.org/wiki/Theil%E2%80%93Sen_estimator

1.1.14.3.1. 理论支持

TheilSenRegressor在逼近效率上可与普通最小二乘（OLS）媲美，而且是一种无偏模型。和OLS不同的是，Theil-Sen是一种非参数方法，这意味着它并不对数据服从的分布做任何假设。由于Theil-Sen是基于中位数的，因此它对坏点（异常点）更加鲁棒。在单变量情况下，Theil-Sen和简单线性回归相比能多容忍29.3%的坏点。 在Scikit-learn的实现中，TheilSenRegressor使用了一种对多变量线性回归模型的泛化算法。该算法使用了稀疏中位数（在多元空间中对中位数概念的一个推广）。

Theil-Sen算法的时间复杂度和空间复杂度随 $${n_{\mathrm{samples}}} \choose {n_{\mathrm{subsamples}}}$$ 变化。这说明当有大量数据和特征时该算法会不再使用。在这种情况下，可以只考虑所有可能组合的一个子集来控制复杂度。

例子

• Theil-Sen回归

参考文献

• [4] Xin Dang, Hanxiang Peng, Xueqin Wang and Heping Zhang: Theil-Sen Estimators in a Multiple Linear Regression Model.
• [5] T. Kärkkäinen and S. Äyrämö: On Computation of Spatial Median for Robust Data Mining.

1.1.15. 多项式回归：使用基本函数扩展线性模型

在机器学习领域中有一个普遍现象，就是用数据的非线性函数来训练线性模型。这种方法既保留了线性方法在速度上的优势，又拓宽了模型所拟合的数据的范围。

比如，可以通过构造系数的多项式特征来扩展简单的线性回归模型。对于标准线性回归，如果输入数据只有二维，那么构造的模型可能会像这样： $$\hat{y}(w,x) = w_0 + w_1x_1 + w_2x_2$$ 假设我们不想拟合出来一个平面了，而是要拟合出来一个抛物面，那么我们可以加入特征的二次多项式，得到这样的模型 $$\hat{y}(w,x) = w_0 + w_1x_1 + w_2x_2 + w_3x_1x_2 + w_4x_1^2 + w_5x_2^2$$ 让人略感意外的是，得到的模型其实仍然是一个线性模型：为了验证这一点，假设我们创建一个新的变量： $$z = [x_1, x_2, x_1x_2, x_1^2, x_2^2]$$ 使用这种被重新标注的数据，得到的模型可以重写为 $$\hat{y}(w,x) = w_0 + w_1z_1 + w_2z_2 + w_3z_3 + w_4z_4 + w_5z_5$$ 可以看到，得到的多项式回归与之前所述的线性回归是同一类的（即模型对$w$仍然是线性的），可以用同样的技术求解。这样一来，线性方法在由这些基本函数构建的更高维空间中仍然适用，模型的灵活性得到了增强，可以适用于更广的数据范围。

这里给出了一个例子，将上述思想应用到一维数据中，通过增加变量的次数来构造多项式特征： 图像创建之前使用了PolynomialFeatures进行预处理。该类将输入矩阵转化为给定度数的新矩阵，用法如下

>>> from sklearn.preprocessing import PolynomialFeatures
>>> import numpy as np
>>> X = np.arange(6).reshape(3, 2)
>>> X
array([[0, 1],
       [2, 3],
       [4, 5]])
>>> poly = PolynomialFeatures(degree=2)
>>> poly.fit_transform(X)
array([[  1.,   0.,   1.,   0.,   0.,   1.],
       [  1.,   2.,   3.,   4.,   6.,   9.],
       [  1.,   4.,   5.,  16.,  20.,  25.]])

特征x从$[x_1, x_2]$转化成了$[1,x_1,x_2,x_1^2,x_1x_2, x^2_2]$，可以被任何线性模型所使用。

这种预处理可以经Pipeline这种工具流水线化。表示简单多项式回归的对象可以如下创建使用：

>>> from sklearn.preprocessing import PolynomialFeatures
>>> from sklearn.linear_model import LinearRegression
>>> from sklearn.pipeline import Pipeline
>>> import numpy as np
>>> model = Pipeline([('poly', PolynomialFeatures(degree=3)),
...                   ('linear', LinearRegression(fit_intercept=False))])
>>> # fit to an order-3 polynomial data
>>> x = np.arange(5)
>>> y = 3 - 2 * x + x ** 2 - x ** 3
>>> model = model.fit(x[:, np.newaxis], y)
>>> model.named_steps['linear'].coef_
array([ 3., -2.,  1., -1.])

使用多项式特征训练出来的线性模型可以被精确转回至输入多项式系数上（？）

在有些情况下，没必要包含某个单独特征的高阶形式，只需要加入所谓的交互特征，即之多$d$个不同特征的乘积。这时可以通过将PolynomialFeatures的interaction_only设为“True”得到。

例如，如果特征是布尔值，则对所有$n$都有$x_i^n=x_i$，这样的特征是没用的。但是$x_ix_j$代表了两个布尔值的合取。这种情况下，可以使用线性分类器解决异或问题：

>>> from sklearn.linear_model import Perceptron
>>> from sklearn.preprocessing import PolynomialFeatures
>>> import numpy as np
>>> X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
>>> y = X[:, 0] ^ X[:, 1]
>>> X = PolynomialFeatures(interaction_only=True).fit_transform(X)
>>> X
array([[ 1.,  0.,  0.,  0.],
       [ 1.,  0.,  1.,  0.],
       [ 1.,  1.,  0.,  0.],
       [ 1.,  1.,  1.,  1.]])
>>> clf = Perceptron(fit_intercept=False, n_iter=10, shuffle=False).fit(X, y)
>>> clf.score(X, y)
1.0