线性模型

基本形式

设x=(x1;x2;x3;xd)是D个变量的描述，在第i个变量上取xi。线性模型的目的是一个学习函数，通过输入变量的线性组合进行预测。即

$$ f(x)=w_1x_1+w_2x_2+...+w_dx_d+b $$

或者通常写成向量的形式

$$ f(x)=w $$

或者通常写成向量形式

w 是一个权重向量，通常用行向量表示。为了计算 w 和 x 的点积（也称为内积），需要将其中一个向量转换为列向量形式。通过将 w 转置 (wᵀ)，我们可以得到一个列向量，并将其与 x 相乘以获得点积的结果。

一般来说w和x都是列向量，但是我们要对这俩个向量进行点积的时候，需要一个行向量一个列向量（行列相同，所以需要做转置矩阵）

$$ f(x) = w^\top x + b $$

w=(w1;w2;...;wd)一旦学习了w和b就确定了模型

尽管它形式简单易于建模，线性模型包含了一些机器学习中的重要和基本理念。事实上，很多强大的非线性模型可以通过引入多层结构或者高纬度映射从线性模型中推到出来。此外，学习到的权重w显然代表了每个输入变量的重要性，并使线性模型具有良好的可理解性。例如，假设我们在西瓜问题中学到的线性模是$f_{ripe}(x)=0.2\times x_{color}+0.5\times x_{root}+0.3\times x_{sound}+1$，它代表了西瓜的成熟度可以由颜色，根部和声音信息决定，而且声音比颜色来的重要。

本章的其他部分会介绍一些典型的线性回归模型，从回归问题开始，接着是二分类和多分类问题。

线性回归

每个$x_i$是d维的项链，表示第i个样本的特征。其中写作$X_i=(x_{i1};x_{i2};...;x_{id}),Y_i \in \mathbb{R}$其中每个$x_{ij}$对应于一个特定的特征维度j的值

给定数据集$D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}$其中$X_i=(x_{i1};x_{i2};...;x_{id}),Y_i \in \mathbb{R}$，线性回归（. Linear regression）目标是学习线性模型，可以准确的预测实际值的输出标签。

m代表数据点的集合，i=1代表从i=1开始从i=m结束

$x_i$是一个实数，D表示一个数据集（dataset）

我们讨论单个输入变量中最简单的例子。为了简化符号，我们省略了变量的下标，即$D=\{(x_i,y_i)\}^m_{i=1}$，其中$x_i \in\mathbb{R}$。对于离散属性，若属性值之间存在序（order）关系，可以通过连续化将其转化为连续值，例如，值‘长’和‘短’可以转换为{1.0,,0.0};海拔的高中低可以转化为{1.0,0.5,0.0}。如果没有顺序关联存在，我们经常转换向量，将具有k个可能性的值的离散变量转换为转化为k-维变量，例如，对于瓜类，西瓜，南瓜，黄瓜，可以分别转化为(0,0,1),(0,1,0)和(1,0,0)。

线性回归试图学得

$$ f(x_i)=wx_i+b,使得f(x_i)\approx y_i $$

为了确定w和b，关键是测定不同f(x)和y。为了这个目的，在这个部分中引入了均方误差。均方误差是最常用的性能度量，我们可以最小化均方误差，即

arg min即argument of the minimum。表示的是该函数取到最小值时，自变量（也称为参数或变元）的值或值的集合。

$$ (w^*, b^*) = arg\ min_{(w,b)} \sum^{m}_{i=1}(f(x_i) - y_i)^2\\ =arg\ min_{(w,b)} \sum^{m}_{i=1}(y_i - wx_i - b)^2 .（例3.4） $$

MSE对应着欧几里得距离或简称欧氏距离，具有直观的几何解释。最小化的MSE的一半方法是最小二乘法（least squares method.）对于线性回归，最小二乘法企图找到一根直线，使得所有样本的直线欧几里得距离最小。

在给定一系列数据点的情况下，最小二乘法被用来找到一条直线（或更高维度的超平面），这条直线最好地拟合这些数据点。在简单线性回归中，我们寻找最佳拟合直线的斜率和截距

欧氏距离是多维空间中两点之间的“直线”距离，基于欧几里得几何中两点间的距离公式

对于俩个点A(x1,x2,x3)和B(y1,y2,y3)欧氏距离如下

$$ d(A, B) = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + ... + (x_n - y_n)^2} $$

在机器学习的上下文中，当你将单个样本视为多维空间中的一个点时，MSE实际上可以被视为一组点到另一组点的欧氏距离的平方的平均值。具体来说，如果我们将每个观测值$y_i$视为一个点在多维空间中的坐标，而对应的预测值$\hat y_i$作为另一个点的坐标，那么MSE是这些点对之间欧氏距离的平方的平均值。

查找w和b使$E(w,b)=\sum_{i=1}^m(y_i-wx_i-b)^2$最小的过程，称为线性回归模型的最小二乘参数估计（least squares parameter estimation）具体的说，我们可以计算$E(w,b)$对于w和b的导数，分别为

$$ \frac{\partial E_{(w,b)}}{\partial w} = 2 \left(w \sum_{i=1}^{m} x_i^2 - \sum_{i=1}^{m}(y_i-b)x_i\right),（例3.5） $$

$$ \frac{\partial E_{(w,b)}}{\partial b} = 2 \left(mb - \sum_{i=1}^{m}(y_i-wx_i)\right)（例3.6） $$

在数学和相关领域中，术语 "closed-form"（闭型或封闭形式）指的是可以使用有限数量的标准数学操作（如加、减、乘、除、指数、对数、根等）和基本函数（如多项式、指数函数、三角函数等）来明确表达的解或表达式。一个闭型解或闭型表达式意味着可以直接计算出结果，而不需要迭代计算、逼近方法或数值解法。

然后让3.5和3.6为零可以得到w和b的最有的闭式（closed-form）解

$$ w = \frac{\sum_{i=1}^{m} y_i(x_i - \bar{x})}{\sum_{i=1}^{m} x_i^2 - \frac{1}{m}\left(\sum_{i=1}^{m} x_i\right)^2},（例3.7） $$

$$ b = \frac{1}{m} \sum_{i=1}^{m}(y_i - w x_i),（例3.8） $$

其中$\overline x=\frac{1}{m}\sum_{i=1}^{m}x_i$为x的均值

一般，样本由d个属性描述，如本章开头的数据集D，在这个例子中，模型变成

$$ f(x) = w^\top x + b ，使得f(x_i)\approx y_i，i=1,....,m $$

这称为多元线性回归(multivariate linear regression.)

同样的，参数w和b可以使用最小二乘法进行估计。为了便于讨论，我们把w和b吸收如向量的形式$\hat w=(w;b)$，相应的数据集D代表着mx(d+1)大小的矩阵X，其中每行对应于一个示例，d个元素对应于示例的d个属性，最后一个元素值恒为1，即

$$ \mathbf X = \left( \begin{array}{cccc} x_{11} & x_{12} & \ldots & x_{1d} \\ x_{21} & x_{22} & \ldots & x_{2d} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m1} & x_{m2} & \ldots & x_{md} \end{array} \right) = \left( \begin{array}{c} (x_1^\top, 1) \\ (x_2^\top, 1) \\ \vdots \\ (x_m^\top, 1) \end{array} \right). $$

将标签向量化为y=(y1; y2;...; ym),类似3.4我们有

mathbf是粗体的代表向量

$$ \hat{\mathbf{w}}^* = argmin_{\hat{\mathbf{w}}} (\mathbf{y}-\mathbf{X}\hat{\mathbf{w}})^T(\mathbf{y}-\mathbf{X}\hat{\mathbf{w}}).（例3.9） $$

令$E_\hat w= (\mathbf{y}-\mathbf{X}\hat{\mathbf{w}})^T(\mathbf{y}-\mathbf{X}\hat{\mathbf{w}})$，对$\hat w$求导得到

$$ \frac{\partial E_{\hat{w}}}{\partial \hat{w}} = 2X^{T}(X\hat{w} - y)（例3.10） $$

令上式为0可得$\hat w$的最有解的闭式解，但由于设计矩阵逆运算，比单变量情况要复杂一些，下面我们做一个简单的讨论。

当$\mathbf x^T\mathbf x$是满秩矩阵（full-rank matrix）或正定矩阵(positive definite matrix)时，令3.10为0可得

$$ \hat{w}^{*} = (\mathbf X^{T}\mathbf X)^{-1}\mathbf X^{T}y（例3.11） $$

其中$(\mathbf x^T\mathbf x)^{-1}$是矩阵$\mathbf x^T\mathbf x$的逆矩阵，令$\hat x=(x_i,1)$，则最终学习得多元线性回归模型为

$$ f(\hat{x}_i) = \hat{x}_i(X^TX)^{-1}X^Ty（例3.12） $$

然而，$X^TX$通常在现实应用中不是满秩的。实践中，变化的数量可以很大，甚至比样本数量还大。$\mathbf x$的数量大于行数在这个例子中，$X^TX$不是满秩的，这意味着不止一个$\hat w$可以最小化MSE。$\hat w$的选择由学习算法的归纳偏好决定，常见的做法是引入规则化（regularization）项

假设解一个线性方程组，当方程数大于自由变量数时，是没有解的。反过来，当方程数小于自由变量数的时候，解就有很多个了。往往，我们会碰到这种情况，参数多，“方程”少的情况，那么有很多个w（权值向量）都能使均方误差最小，那么该选哪一个呢？ 这就涉及到 归纳偏好问题了，常见的做法是引入正则化项。

线性模型是简单多变的。以$(x, y), y \in \mathbb{R}$为例，通过线性模型近似真实标签y。我们得到线性回归模型，简写成

$$ y = w^{\top}x + b.（例3.13） $$

是否有可能让预测值近似由于y导出的变量？例如，假设输出标签在指数尺度上变化，然后可以使用输出标签的对数进行近似

这里是让x去逼近lny。形式上还是线性的，但是设置上已经是在求输入空间到输出空间的非线性函数映射。

$$ \ln y = w^{\top}x + b.（例3.14） $$

这就是对数线性回归，它实际上是让$e^{w^Tx+b}$逼近y，然而这还是线性回归，它实际上是在寻找从输出空间到输入空间的非线性映射。如图3.1,对数函数将线性回归的预测与基本真值标签联系起来。

在机器学习和统计学中，模型ln(y) = w^T x + b通常被称为对数线性模型，或者说是广义线性模型的一种。尽管从直观上看起来这可能不是"线性"的，但这里的"线性"是指模型参数与特征之间的关系是线性的。

广义线性回归的假设空间包括多项式函数，而非仅有的线性函数

联系函数是一个单调可导的函数，作用是链接预测期与因变量的期望值。联系函数的选择取决于变量类型和分布。

一般来说对于单调可微的函数g(.)

$$ y = g^{-1}(w^{\top}x + b).（例3.15） $$

这叫做广义线性模型，函数g(.)是联系函数。显然对数线性回归是广义线性模型在g(.)=ln(.)时的特例。

逻辑回归（对数几率回归）

可微必可导，可导不一定可微微分可以看作是导数作用于自变量微小变化的结果，即df(x) = f'(x)dx。

之前的章节讨论了在回归问题中使用线性模型，但是我们如何解决分类问题呢？答案在3.15的广义线性模型中。我们只需要找到一个单调可微函数G。它链接里线性回归的预测和分类问题的真值标签。

对于带有输出标签的二分类$y \in \{0,1\}$，线性回归模型的实际预测值$w^\top x+b$需要转换成0/1,最理想的是单位阶跃( unit-step function)函数

$$ \begin{cases} 0, & z < 0 \\ 0.5, & z = 0 \\ 1, & z > 0 \end{cases} \ $$

它预测z大于0时为正，小于0时为负数，等于0的时候任意输出，阶跃函数如图3.2所示

图3.2可以看出单位阶跃函数并不连续，所以不能转换为3.15中的单调可微函数即$g^{-1}(.)$。因此我们需要找到单调可微函数作为替代这个单位阶跃函数，通常是选择这样一个对数几率函数（logistic function）

$$ y=\frac{1}{1+e^{-z}}（例3.17） $$

我们可以看到这个逻辑函数是一个S型（sigmoid）函数，它把z转换成y，要么接近0要么接近1，输出值在z=0附近有一个陡峭的变化。

对于g的反函数我们有

$$ y=\frac{1}{1+e^{-w^\top x+b}}（例3.18） $$

与3.14和3.18类似可以转化为

$$ ln\frac{y}{1-y}=w^\top x+b（3.19） $$

设y为x是正样本的可能性，1-y是x为负样本的可能性，曲线

$$ \frac{y}{1-y}（3.20） $$

叫做几率（odds），表示x为正例的可能性。对几率取对数则得到对数几率(log odds 即logit)

$$ ln\frac{y}{1-y}（3.21） $$

结果证明，3.18是使用线性回归模型的预测结果去逼近真实标记的对数几率，相应的模型叫做对数几率回归（logistic regression或者logit regression）。必须注意对数几率回归虽然名字里有回归，但是其实是分类问题

确实如此，尽管“逻辑回归”（Logistic Regression）这个名字中包含了“回归”这个词，但它实际上是一种分类算法，主要用于解决分类问题，尤其是二分类问题。逻辑回归的名字来源于历史上它与线性回归的关系，以及它使用了回归分析的技术来建模。

逻辑回归有几个很好的特性。例如，它直接对标签概率进行建模，不需要对数据分布做任何假设，因此避免了不适当的假设数据分布等问题，此外，他预测与标签相关的概率，这对于使用概率来帮助决策的任务是必不可少的。最后，逻辑回归的目标函数，我们稍后会看到，是一个凸函数具有多种导数并具有许多有用的数学性质，他的凸性质使得可以用数值优化方法求解。

现在我们把注意力转向测定3.18中的w和b，如果我们考虑y在3.18中的后验概率 p=(y=1|x),那么3.19可以改写成

$$ ln\frac{p(y=1|\mathbf x)}{p(y=0|\mathbf x)}=\mathbf w^\top \mathbf x+b $$

因此

$$ p(y=1|\mathbf x)=\frac{e^{\mathbf w^\top +b}}{1+e^{\mathbf w^\top x+b}}（3.23） $$

$$ p(y=0|\mathbf x)=\frac{1}{1+e^{\mathbf w^\top x+b}}（3.24） $$

最大似然法（Maximum Likelihood Estimation, MLE）是一种广泛应用于统计学中的参数估计方法。这种方法的基本思想是，当我们有一组观测数据，并且假设这些数据是从某个特定的统计模型（如正态分布、泊松分布等）中随机抽取的，那么我们可以利用这些数据来估计模型的未知参数。

为了最大化后验概率，我们可以使用最大似然法去拟定w和b。给定数据集$\{(\mathbf x_i,y_i)\}^m_i=1$,对率回归模型最大化"对数似然(log-likelihood)"

式子的$\ell$通常表示损失函数或者似然函数。

损失函数是用来评估模型结果和真实结果之间的差异程度。它衡量的是模型预测的错误程度，通常越小越好。

似然描述了在给定一组观测数据（记为 X）下，模型参数（记为 θ）的“可能性”或“合理性”。换句话说，似然函数是参数 θ 的函数，表示在观测到数据 X 的条件下，模型参数 θ 使得数据出现的概率。

在最大似然估计（Maximum Likelihood Estimation, MLE）中，目标是找到一组参数，使得观测数据出现的概率最大。似然函数的数学形式通常是所有独立观测数据点的概率分布函数的乘积。

$$ \begin{equation} \ell(\mathbf{w}, b) = \sum_{i=1}^{m} \ln p(y_i | x_i; \mathbf{w}, b),（3.25） \end{equation} $$

每个样本属于真是标记的概率越大越好。为了便于讨论，我们重写$\beta=(\mathbf w;b),\hat x=(x;1)$则$\mathbf w^\top x+b$可以简写为$\beta^\top \hat x$。再令$p_1(\hat x;\beta)=p(y=1|\hat x;\beta),p_0(\hat x;\beta)=p(y=0|\hat x;\beta)=1p_1(\hat x\beta)$,则式3.25中的似然项可以重写为，

$$ p(y_i \mid x_i; w, b) = y_ip_1(\hat{x}_i; \beta) + (1 - y_i)p_0(\hat{x}_i; \beta).（3.26） $$

用3.26带入3.25，宾根据3.23和3.24可知，最大化式3.25等价于最小化

$$ \ell(\beta) = \sum_{i=1}^{m}\left( -y_i \beta^\top \hat{x}_i + ln\left(1+e^{\beta^\top \hat{x}_i}\right)\right).（3.27） $$

因为3.27是一个关于B的高阶可微凸函数，根据凸优化理论求解，可以通过典型的优化方式，例如梯度下降（gradient descent method）或者牛顿法（Newton’s method.）因此我们有

$$ \beta^* = \arg \min_\beta \ell(\beta).（3.28） $$

以牛顿法为例，第t+1次的迭代规则为

$$ \beta^{t+1} = \beta^t - \left(\frac{\partial^2 \ell(\beta)}{\partial \beta \partial \beta^\top}\right)^{-1} \frac{\partial \ell(\beta)}{\partial \beta}, $$

其中一阶导数和二阶导数分别为

$$ \frac{\partial \ell (\beta)}{\partial \beta} = -\sum_{i=1}^{m} \hat{x}_i (y_i - p_1(\hat{x}_i; \beta)),（3.30） $$

$$ \frac{\partial^2 \ell (\beta)}{\partial \beta \partial \beta^\top} = \sum_{i=1}^{m} \hat{x}_i \hat{x}_i^\top p_1(\hat{x}_i; \beta) (1 - p_1(\hat{x}_i; \beta)).（3.31） $$

线性判别分析

线性判别分析（Linear Discriminant Analysis (LDA)）是一种经典的线性方法，因为最早是由Fisher在二分类问题提出的，所以也称Fisher判别分析法（ Fisher’s Linear Discriminant ）

LDA的概念很简单：将训练样本投影到一条线上，使同一类的样本彼此接近，当样本不同的时候彼此距离很远。当遇到新样本，它们被投影到同一条线上，分类由他们投影的位置所决定，图3.3展示了二维的图例

对于给定的数据集$\{(\mathbf x_i,y_i)\}^m_{i=1},y_i \in \{0,1\}$设$x_i,μ_i,和Σ_i$分别代表第i个的样本集，平均向量，协方差矩阵。

协方差是用来描述俩个随机变量的相关性，y随x增大cov也就是协方差大于0，如果x增大y减小，协方差小于0，当x增大时y可能增大可能减小，即不想关时，协方差等于0

以身高体重为例，如果身高增加了体重大概率增加，所以大部分样本是正相关的，小部分样本是负相关的（即长得矮还胖）

判断相关信可以通过求所有点的均值，然后看每个点和均值是正相关还是负相关，计算面积求平均值就知道整体是正向相关还是负相关的

如果在原点移动到加权平均的位置（权重可能是概率）

所以通过式子$\sum_{i}^{n} p_i(x_i - \mu_X)(y_i - \mu_Y)$我们可以判断随机变量的相关性，将式子改写成期望的样子就是协方差公式

$$ Cov(X, Y) = E[(X - \mu_X)(Y - \mu_Y)] $$

协方差矩阵计算不同维度之间的协方差，他由方差和协方差俩部分组成，对角线上的元素是随机变量的方差，非对角线的元素是俩个随机变量之间的协方差。它是一个对称矩阵。要计算协方差矩阵需要特征按照列向量的方式保存到矩阵中，然后计算矩阵和矩阵转置的乘积

在数据投影到w上之后，这俩个类型的中心分别为为$\mathbf w^\top \mu_0和\mathbf w^\top \mu_1$，若将所有样本都投影到直线上，俩类样本的协方差分别为$\mathbf w^\top \muΣ_0\mathbf w和\mathbf w^\top \muΣ_0\mathbf w$。由于直线是一维空间因此它们均为实数。

为了让相似样本的投影点尽可能的近，我们可以使相似样本的投影点的协方差尽可能小。即最小化$\mathbf w^\top \muΣ_0\mathbf w+\mathbf w^\top \muΣ_0\mathbf w$，让不同样例的投影点越远越好。我们可以让类中心的距离尽可能的大，即$||\mathbf w^\top \mu_0-\mathbf w^\top \mu_1||^2_2$尽可能的大。同时考虑二者，则可得到最大化目标。

$$ J = \frac{\left\| w^\top \mu_0 - w^\top \mu_1 \right\|_2^2}{w^\top \Sigma_0 w + w^\top \Sigma_1 w} \\ = \frac{w^\top (\mu_0 - \mu_1)(\mu_0 - \mu_1)^\top w}{w^\top (\Sigma_0 + \Sigma_1)w}（3.32） $$

定义 类内散度矩阵（between-class scatter matrix）

$$ \begin{align*} S_w &= \Sigma_0 + \Sigma_1 \\ &= \sum_{x \in X_0} (x - \mu_0)(x - \mu_0)^\top + \sum_{x \in X_1} (x - \mu_1)(x - \mu_1)^\top \end{align*}（3.33） $$

以及类间散度矩阵

$$ S_b = (\mu_0 - \mu_1)(\mu_0 - \mu_1)^\top,（3.34） $$

可以将3.32重写成

$$ J = \frac{w^\top S_b w}{w^\top S_w w},（3.35） $$

这就是LDA欲最大化的目标，即$S_b,S_w$的广义瑞利商（generalized Rayleigh quotient）

那么如何确定w呢？因为3.35中分子分母都是w的二次项，3.35的解与w无关，只关心他的方向，不失一般性，另$w^\top S_w w = 1$，最大化3.3.5等同于

$$ \min_{w} -w^\top S_b w\\ s.t. w^\top S_W w = 1.（3.36） $$

使用拉格朗日乘子法；上式等价于

$$ S_b w = \lambda S_w w,（3.37） $$

其中λ是拉格朗日乘子，注意到$S_bw$的方向恒为$\mu_0-\mu_1$另

$$ S_b w = \lambda(\mu_0 - \mu_1),（3.38） $$

带入3.37得

$$ S_b w = \lambda(\mu_0 - \mu_1),（3.39） $$

显然多分类LDA可以由很多种实现方法，使用$S_B,S_w,S_t$三者其中的俩种即可。常见的一种实现是采用优化目标

$$ \max_{W} \frac{\text{tr}(W^T S_b W)}{\text{tr}(W^T S_w W)} $$

其中$W \in \mathbb{R}^{d \times (N-1)}$,tr(.表示矩阵的trace)

$$ S_b W = \lambda S_w W . $$

W的闭式解则是$S_w^{-1}S_b$的一个N-1个最大广义特征值对应的特征向量组成的矩阵。

若将W视为一个投影矩阵，则多分类LDA样本投影到N-1维空间，N-1通常小于原有的属性数。于是可以通过投影减小样本点的维数，且投影过程中使用了类别信息，因此LDA也被经常视为一种降维技术。

多分类学习

在实践中我们通常遇到的是多分类问题。一些二分类问题方法可以直接扩展到多分类案例。然而，在更多情况下，我们是基于一些基本战略，利用二分类学习器来解决多分类问题。

不失一般性，给定N个类C1，C2，C3，Cn，多分类的基本思想是分解，即将多分类问题化解为多个二分类问题。我们从分解问题开始，然后为每个被分解的二分类问题训练一个二分类器。在测试阶段，我们将所有二分类器的输出集成到最终的多累预测中。在这个过程中，关键问题是如何划分多分类问题还有如何集成多个分类器。本节的其他部分会引入三个分类策略，分别为一对一(One versus One OVO),一对其余(One versus Rest OVR)还有多对多Many versus Many(MvM).

给定数据集$D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}$当$y_i \in \{C_1,C_2,...C_n\}$。一对一让N个类俩俩配对，返回了N(n-1)/2的二分类问题数。举个例子，一对一训练器来区分Ci和Cj，其中Ci为正，Cj为负。在测试中一个新样本被所有分类器分类，返回N(N − 1)/2类个输出 。最终预测可以通过投票进行，即预测的分类是获得投票最多的分类，如图3.4给定了一个一对一的图解

OVR训练N个分类器将每个分类依次考虑为正，其他分类视为反例。通过测试，如果他只有一个分类器推断新样本是正，那么直接作为最终结果返回。然而，如果多分类预测为反例，那么通常要评估预测的可信度，并将置信度最高的类作为分类结果。

因为OvR需要多个分类器，OvO需要N(N-1)/2个分类器，OVO的内存与测试开销会比OvR来的更大。然而每一个OvR分类器使用所有的训练样本，而每个OvO分类器只使用俩个类型的样本。因此，OvO训练的计算开销要比OvR更低，尤其是由很多类型的时候。对于性能预测。预测性能取决于特定的数据分布，但是在大部分例子中，俩个方法的性能是相似的。

MvM进行多次试验，每个试验都有几个类别为正，也有几个类别为负。正例和反例的构建需要精心设计。这里我们介绍一种最常用的MvM技术纠错输出码（Error Correcting Output Codes ECOC）

ECOC是将编码的思想引入类别拆分，并尽可能在编码过程中具有容错性。ECOC工作过程主要分为俩步。

每一个类别会被分配一个唯一的二进制代码或符号

• 编码：将N个对象分为M次，每次拆分都会分为正例和反例。用这种方式，总共产生M个训练集和M个类型，可以训练M个分类器。
• 解码：使用M个分类器预测测试样例，这些预测标记将会组成一个编码。将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果

类别划分通过编码矩阵(coding matrix)指定，编码矩阵有不同的设计，通常使用二元编码和三元编码。二进制编码将每个类设置为正或者反。三进制编码则增加了一个额外的排除类，如图3.5所示

其实就是汉明距离和欧几里得距离

在3.5的a中，分类器f2将c1和c3视为正例c2和c4视为反例。此外，分类器f4在3.5将c1和c4视为正例，c3视为反例。在解码环节，所有分类的预测结果共同生成测试样例的编码。然后计算出每个类型的编码和基础编码的距离。最短距离的分类被视为结果输出。举个例子，3.5的a中，当使用欧氏距离时，预测值为C3.

为什么叫做纠错输出码呢？因为ECOC编码对分类器的错误有一定的容忍和修正能力。例如，图3.5中的a，测试样本的正确编码为(−1, +1, +1, −1, +1)。分类器f2犯了一个错误，编码变成了（−1, −1, +1, −1, +1）但是最终还是输出了正确的预测结果C3。一般，对于同一个问题，ECOC编码越长，纠错能力越好。然而，更差的编码代表着更多的分类器需要训练，因此增加了计算和内存的成本，此外，因为类的组合在有限分类中是有限的，当编码达到极限时，额外的程度是无意义的。

在理论上，固定长度编码的纠错能力随着类间距离增加而增加（俩个类距离越远纠错能力越强）。遵循这个原则，当码字长度较短时，可以计算出理论上最优的码字。然而，寻找最长代码变成了np-hared问题。幸运的是，非最优编码通常是足够的，而最佳编码很少是必要的。更好的理论性质不一定与更好的分类相关，因为机器学习涉及很多因素。例如，当多个分类被划分到俩个类子集时，不同的划分方法导致不同的分类子集，分类难度也不同。于是，我们有俩个编码：一种有很好的理论纠错性质，但回导致二分类困难，另一个有较弱的纠错能力但是会导致二分类问题较为简单。很难说哪个编码更好。

类别不平衡问题

目前介绍的分类问题都有一个共同的假设：每个样本数量没有显著的差异。一般来说小差异的影响是有限的，但是巨大的差异在学习过程中将会带来麻烦。例如，假设有998个反例只有俩个正例，学习器可以通过预测样本永远为反轻松达到99.8%的正确率，显然这样的学习器是没用的因为永远不会输出正例。

这种情况被叫做类别不平衡（Class Imbalance），它是指类别的样本数量明显不同的分类问题。不失一般性，这个章节假设正例是少数，反例是多数。类别不平衡在阶级中很常见。例如，即便元数据集是类平衡的，这仍然是由可能的，OvR和MvM构成的二分类问题是类不平衡的，所以必须要了解类别不平衡的基本方法。

这在线性分类器是容易理解的。当使用$y=\mathbf w^\top \mathbf x +b$分类新的样本x，我们实际上比较预测值和阈值，即如果y>0.5为正，否则为负。y代表了为正例的可能性，几率$\frac{y}{1-y}$代表了正负概率的比例。设置阈值为0.5意味着分类器假设正例和反例的概率是相等的，分类器的决策规则为

$$ 如果\frac{y}{1-y}>1那么预测为正例（3.46） $$

当分类是不平衡的，设m+和m-分别代表正例数和反例数。那么观察到的类比例为$\frac{m^+}{m^-}$代表真值的概率，因为训练集的样本为无偏差抽样。因此新的样本分类在预测值大于观测到的概率时为正例

$$ 如果\frac{y}{1-y}>\frac{m^+}{m^-}那么预测为正例（3.47） $$

然而，因为我们分类器通过3.46进行决策，他必须对预测值进行调整，让他在基于3.46做决策时，实际上是在执行3.47.要做到这点我们可以使用

$$ \frac{y'}{1-y'}=\frac{y}{1-y}>\frac{m^+}{m^-}（3.48） $$

它给了一个基础的策略去处理类不平衡学习：再缩放（rescaling）

虽然再缩放的思想很简单，实际操作却不平凡，因为假设"训练集样本是无偏采样的"在实践中通常是想不通的。换句话说，从训练集推断的比例可能是不准确的。有三种主要的再缩放方法。第一个方法是在原本的反例中进行欠采样，即，一些反例被有选择的丢弃直到类型平衡。第二个方法是执行过采样（oversampling）在正例中，即增加样例中正例的数量。第三个方法是阈值移动(threshold-moving),它使用原先的训练集进行训练，但是使用4.48进行决策。

因为欠采样丢弃了原本的样本，所以计算代价相比于增加正样本数量的过采样减少了。值得一提的是过采样不是单纯的复制已有样本，否则会发生严重的过拟合情况。具有代表性的过采样方法是SMOTE，是通过训练集里的正例插值来产生额外的正例。对于欠采样，如果随机丢弃负样本，可能会丢失有价值的信息。EasyEnsemble是一个典型的欠采样算法，它利用了集成学习机制。EasyEnsemble划分了原本样例到几个更小的集合中用于不同的学习者，比如对每个学习者进行欠采样，但总体而言信息没有丢失。

在缩放也是成本敏感型学习(cost-sensitive learning)的基础，在其中将3.48中的m-/m+替换为cost+/cost-，其中cost+是将正例分为反例的代价，cost-是将反例分为正例的代价。