基本形式

由d个属性描述的示例$\textbf{x} = (x_1; x_2;…;x_d))$,线性模型试图通过属性的线性组合来进行预测函数，即
$$f(\textbf{x}) = \textbf{w}^T\textbf{x}+b$$
$\textbf{w}$和$b$学得后模型就可以确定。由于w直观表达各属性在预测中的重要程度，
优点：

1. 形式简单，易于建模。
   但是蕴藏着机器学习中一些重要的基本思想。许多功能强大的非线性模型可在线性模型基础上，通过引入层次结构或者高维映射得到。
2. w直观表达属性的权值，因此线性模型具有很好的“可解释性”。

线性回归

定义： 线性回归试图学得一个线性模型尽可能准确预测实值输出标记。

预处理

离散属性：若属性值之间存在“序”关系，可通过连续化转换为连续值。
若属性之间不存在序关系，通常转换为k维向量。

一元线性回归

假设只有一个属性 $f(x) = wx+b$.确定w和b可通过最小化均方误差求得。求解方法是最小二乘法，即试图找到一条直线使得所有样本到直线上的欧氏距离之和最小。

多元线性回归

$$f(\textbf{x}) = \textbf{w}^T\textbf{x}+b$$
也可以通过最小二乘法计算w和b，但是设计矩阵逆运算比单变量复杂。
然而$\textbf{X}^T\textbf{X}$不一定是满秩矩阵，例如可能会出现很大的变量数目甚至超过样本数。导致x列数多与行数，此时可以解除多个w，使均方误差最小化。选择哪一个作为输出将由学习算法的归纳偏好决定。常见做法是引入正则化项。

对数线性回归

将输出标记的对数作为线性模型逼近的目标：
$$\ln y= \textbf{w}^T\textbf{x}+b$$
它实际上实在试图让$e^{w^T+b}$逼近$y$。上式在形式上仍是线性回归，但是实质上已是在再求取输入空间到输出空间的非线性函数映射。这里的对数函数起到了将线性回归模型的预测值与真实标记联系起来的作用。

广义线性模型

更一般的考虑单调微调函数$g(\cdot)$(称作“联系函数”)令：
$$y = g^{-1}(\textbf{w}^T \textbf{x} +b)$$
显然现行回归模型是在$g(\cdot) = \ln (\cdot)$时的特例。

对数几率回归(逻辑回归)

线性模型做分类任务怎么办？答案在上面的广义线性模型中：找到一个可以单调可微函数将真实标记y与线性回归模型的预测值联系起来。由于$z= \textbf{w}^T\textbf{x}+b$是实值，需要将z转换为0,1.最理想的是单位越阶函数。
但是单位越界函数不连续。故采用近似的对数几率函数(logistic function):
$$y = \frac{1}{1+e^{-z}}$$
对数几率函数是一种Sigmod函数，将z值转换成一个接近0或者1的y值，并且输出值在z=0附近很陡。

带入线性模型中可以得到
$$y = \frac{1}{1+e^{-(\textbf{w}^T\textbf{x}+b)}}$$
$$\ln \frac{y}{1-y} = \textbf{w}^T\textbf{x}+b$$
若将y视为样本x作为正例的可能性，则1-y是器反例的可能性，两者的比值$\frac{y}{1-y}$称为“几率”，反映了x作为正例的可能性。对几率取对数得到“对数几率”（logit）：$\frac{\ln y}{1-y}$.。可以看出上式是用线性回归预测的结果去逼近真实标记的对数几率。

方法优点：

1. 直接对分类可能性建模，无需事先假设数据分布。避免了假设数据分布不准确所带来的问题。
2. 不仅可以预测出“类别”，而是可以得到近似概率预测，这对许多需要利用概率辅助决策的任务很有用。
3. 对数函数是任意阶可导的凸函数，有很好的数学性质，现有的很多优化算法都可以直接用于求解最优值。

如何求解w和b

将y视为后延概率估计$p(y=1|x)$，重写逻辑回归式有
$$\ln \frac{p(y=1|x)}{p(y=0|x)} = \textbf{w}^T\textbf{x}+b$$
有
$$p(y=1| x) = \frac{e^{\textbf{w}^T\textbf{x}+b}}{1+e^{\textbf{w}^T\textbf{x}+b}}$$

$$p(y=0| x) = \frac{1}{1+e^{\textbf{w}^T\textbf{x}+b}}$$

于是可以用极大似然法来估计w和b，令每个样本属于其真实标记的概率越大越好。
将（w；b）表示为$\beta$.可以得到最大似然式子是关于$\beta$的高阶可导凸函数。

根据凸优化理论，经典的数值优化算法如梯度下降法、牛顿法等都可以求得最优解。

线性判别分析

LDA是一种经典的线性学习方法。思想非常朴素：给定训练样例集，设法将样例投影到一条直线上，使得同类样例投影点尽可能近，一类样例投影点尽可能远；在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别。如图：

若使同类样例投影尽可能接近，可以让同类样例投影点的协方差尽可能小；
欲使一类样例的投影点尽可能远离，可以让类中心的距离尽可能大。

值的注意的是LDA可以从贝叶斯决策理论的角度来阐述，并可证明，当两类数据同先验、满足高斯分布并且协方差相等时候，LDA可以达到最优值。
另外LDA也常被视为一种经典的监督降维技术。

多分类学习

一般思路

解决多分类问题的一般思路是“拆解法”，即将多分类任务拆分为若干个二分类任务求解。具体来说就是先对问题进行拆分，然后为拆出的每个二分类任务训练一个分类器；
在测试的时候，对这些分类器预测结果进行集成以获得最终的多分类结果。
这里的 关键是如何对多分类任务进行拆分，以及如何对多个分类器进行集成。

拆分策略

1. 一对一 OvO
2. 一对其余 OvR
3. 多对多 MvM

OvO

给定数据集，N个类。OvO将N个类进行两两配对产生N(N-1)个二分类任务。在测试阶段，新样本将同时提交给所有分类器，于是得到N(N-1)个分类结果，最终结果可以通过投票产生：即把被预测最多的类别作为最终的结果。

OvR

每次将一个类的样例作为正例，其他所有的样例作为反例训练N个分类器，在测试时候若仅有一个分类器预测为正类，则对应的标记作为最终的分类结果；若有多个分类器预测为正类，则通常考虑各种分类器的预置信度，选择置信度最大的类标记作为分类结果。

OvO与OvR

可以看出，OvR值需要训练N个分类器，而OvO需要N(N-1)个分类器，因此OvO的存储开销和测试时间开销通常比OvR大。但在训练的时候，OvR的每个分类器均使用全部的训练样例，而OvO的每个分类器只使用两个类的样例。
因此，在类别很多的时候，OvO训练时间开销通常比OvR更小，至于预测性能，取决于数据分布，两者大多数情形差不多。

MoM

每次将若干个类作为正类，其他类作为反类。显然OvO和OvR是MvM的特例。
但是MvM的正反类需要特殊设计，不能随意挑选。常用的技术是：“纠错输出码（EOCO）”。

EOEC是将编码的思想引入类别拆分，尽可能在解码中具有容错性。主要分为两步：

1. 编码：对N个类别进行M次划分，每划分一部分类为正类，一部分为反类，形成二分类训练集；这样一共产生M个训练集，可以训练出M个分类器。
2. M个分类器分别对测试样本进行预测，这些预测标记组成一个编码，将这个编码与每个类别各自的编码进行比较，返回其中距离最小（距离通常用海明距离或者欧氏距离）的类别作为最终的预测结果。

类别划分通过“编码矩阵”实现：二元码（正类，反类），三元码（正类，反类，停用类）。EOCO编码越长，纠错能力越强，但是需要训练的分类器也越多。

类别不均衡问题

前面介绍的分类学习方法都是基于几个基本假设：不同类别训练样例数目相当。然而实际可能会出现类别不均衡。
定义：类别不均衡是指分类任务中不同类别的训练样例数目相差很大的情况。

在线性分类中，阈值设置为0.5表明分类器认为真实真返利可能性相同，即分类器决策规则：若$\frac{y}{1-y}>1$则预测为正例。然而观测几率应该是$\frac{m^+}{m^-}$（假设训练集是基于样本的无偏估计，这个应该等于真实几率），即只要分类器预测几率高于观测几率就应该判定为正例即:$\frac{y}{1-y}>\frac{m^+}{m^-}$预测为正例。因此应该对预测值进行调整为
$$\frac{y’}{1-y’} = \frac{y}{1-y} \times \frac{m^+}{m^-}$$
这就是类别不均衡学习的一个基本策略：再缩放。
这个方法有效但是不平凡，因为我们未必能基于训练集的观测几率来推断出真实几率。现有的三大类做法（假定正类较少，反类样例较多）：

1. 欠采样：去除反例使得正反例数目接近再进行学习。
2. 过采样：增加一些正例
3. 直接基于原始训练集进行学习，但是采用再缩放嵌入到决策过程，称为“阈值移动”。

欠采样开销远小于过采样。但是可能丢失重要信息。代表算法EasyEnsemb，则是利用继承学习机制将反例划分为若干个不同集合供不同学习器使用。看起来每个学习器都欠采样，但是全局却不会丢失重要信息。

过采样不能简单地对初始正例样本进行重复采样，否则会导致严重过拟合。
过采样代表算法SMOTE：对训练集正例进行插值产生额外正例。

注意区别多分类与多标记

多分类中虽然有多个类别，但是每个样本仅仅属于一个类别。
如果希望一个样本同时预测出多个类别标记。例如一幅图标记为“蓝天”，“白云”“自然场景”等，这样的任务叫“多标记学习（multi-label learning）”。