03linear_model.md

线性模型

给定一个包含d个属性的实例 $\mathbf{x} = (x_1;x_2;...;x_d)$，**线性模型（linear model）**的原理是学得一个可以通过属性的线性组合来进行预测的函数，也即：

$$f(\mathbf{x}) = w_1x_1 + w_2x_2 + ... + w_dx_x + b$$

一般写作向量形式：$f(\mathbf{x}) = \mathbf{w}^T\mathbf{x} + b$。其中权重向量 $\mathbf{w}$ 和偏置项 $b$ 就是我们需要学习的参数。

线性模型有良好的可解释性，每个属性对应的权重可以理解为它对预测的重要性。并且建模较为简单，许多功能更为强大的非线性模型都是在线性模型的基础上引入层级结构或高维映射得到的。

这一章的内容大致如下：

• 线性回归：如何把离散属性连续化？怎样用最小二乘法进行参数估计？多元线性回归如何求解？广义线性模型是怎样的？。

• 对数几率回归：分类任务和线性回归是如何关联起来的？从概率的角度来看，如何用极大似然法进行参数估计并获取最优解？

• 线性判别分析：二分类任务如何求得LDA模型的参数？如何推广到多分类任务？

• 多分类学习：如何把多分类任务拆分为二分类任务？有哪些拆分策略？是如何进行建模和预测的？

• 类别不平衡问题：再缩放思想以及三种解决类别不平衡问题的主要方法。

线性回归

离散属性连续化

由于不同模型对数据的要求不一样，在建模之前，我们需要对数据做相应的处理。一般的线性回归模型要求属性的数据类型为连续值，故需要对离散属性进行连续化。

具体分两种情况：

1. 属性值之间有序：也即属性值有明确的大小关系，比方说把三值属性 “高度” 的取值 {高，中，低} 转换（编码）为 {1.0，0.5，0.0}；

2. 属性值之间无序：若该属性有 $k$ 个属性值，则把它转换为 $k$ 维向量（把1个属性扩展为k个属性），比方说把无序离散属性 “商品” 的取值 {牙膏，牙刷，毛巾} 转换为 (0,0,1)，(0,1,0)，(1,0,0)。 这种做法在自然语言处理和推荐系统实现中很常见，属性 “单词” 和 “商品” 都是无序离散变量，在建模前往往需要把这样的变量转换为哑变量，否则会引入不恰当的序关系，从而影响后续处理（比如距离的计算）。

补充：对应于离散属性连续化，自然也有连续属性离散化。比方说决策树建模就需要将连续属性离散化。此外，在作图观察数据分布特征时，往往也需要对连续属性进行离散化处理（比方说画直方图）。

最小二乘法

回归任务最常用的性能度量是均方误差（mean squared error, MSE）。首先介绍单变量线性回归，试想我们要在二维平面上拟合一条曲线，则每个样例（即每个点）只包含一个实值属性（x值）和一个实值输出标记（y值），此时均方误差可定义为：

$$E(f;D) = \frac{1}{m} \sum_{i=1}^m(y_i-f(x_i))^2\\ \qquad\qquad = \frac{1}{m} \sum_{i=1}^m(y_i-wx_i-b)^2$$

有时我们会把这样描述模型总误差的式子称为损失函数或者目标函数（当该式是优化目标的时候）。这个函数的自变量是模型的参数 $w$ 和 $b$。由于给定训练集时，样本数 $m$ 是一个确定值，也即常数，所以可以把 $\frac{1}{m}$ 这一项拿走。

最小二乘法（least square method）就是基于均方误差最小化来进行模型求解的一种方法，寻找可使损失函数值最小的参数 $w$ 和 $b$ 的过程称为最小二乘参数估计（parameter estimation）。

通过对损失函数分别求参数 $w$ 和 $b$ 的偏导，并且令导数为0，可以得到这两个参数的闭式（closed-form）解（也即解析解）：

$$w = \frac{\sum_{i=1}^m y_i(x_i - \bar{x})}{\sum_{i=1}^m x_i^2 - \frac{1}{m}(\sum_{i=1}^m x_i)^2}$$

$$b = \frac{1}{m} \sum_{i=1}^m (y_i-wx_i)$$

在实际任务中，只要我们把自变量（x, y, m）的值代入就可以求出数值解了。

为什么可以这样求解呢？因为损失函数是一个凸函数（记住是向下凸，类似U型曲线），导数为0表示该函数曲线最低的一点，此时对应的参数值就是能使均方误差最小的参数值。特别地，要判断一个函数是否凸函数，可以求其二阶导数，若二阶导数在区间上非负则称其为凸函数，若在区间上恒大于零则称其为严格凸函数。

多元线性回归

前面是直线拟合，样例只有一个属性。对于样例包含多个属性的情况，我们就要用到多元线性回归（multivariate linear regression）（又称作多变量线性回归）了。

令 $\mathbf{\hat{w}} = (\mathbf{w};b)$。把数据集表示为 $m \times (d+1)$ 大小的矩阵，每一行对应一个样例，前 $d$ 列是样例的 $d$ 个属性，最后一列恒置为1，对应偏置项。把样例的实值标记也写作向量形式，记作 $\mathbf{y}$。则此时损失函数为：

$$E_{\mathbf{\hat{w}}} = (\mathbf{y} - X\mathbf{\hat{w}})^T (\mathbf{y} - X\mathbf{\hat{w}})$$

同样使用最小二乘法进行参数估计，首先对 $\mathbf{\hat{w}}$ 求导：

$$\frac{\partial E_{\mathbf{\hat{w}}}}{\partial \mathbf{\hat{w}}} = 2 X^T(X\mathbf{\hat{w}} - \mathbf{y})$$

令该式值为0可得到 $\mathbf{\hat{w}}$ 的闭式解：

$$\mathbf{\hat{w}}* = (X^TX)^{-1}X^T\mathbf{y}$$

这就要求 $X^TX$ 必须是可逆矩阵，也即必须是满秩矩阵（full-rank matrix），这是线性代数方面的知识，书中并未展开讨论。但是！现实任务中 $X^TX$ 往往不是满秩的，很多时候 $X$ 的列数很多，甚至超出行数（例如推荐系统，商品数是远远超出用户数的），此时 $X^TX$ 显然不满秩，会解出多个 $\mathbf{\hat{w}}$。这些解都能使得均方误差最小化，这时就需要由学习算法的归纳偏好决定了，常见的做法是引入**正则化（regularization）**项。

广义线性模型

除了直接让模型预测值逼近实值标记 $y$，我们还可以让它逼近 $y$ 的衍生物，这就是**广义线性模型（generalized linear model）**的思想，也即：

$$y = g^{-1}(\mathbf{w^Tx} + b)$$

其中 $g(\cdot)$ 称为联系函数（link function），要求单调可微。使用广义线性模型我们可以实现强大的非线性函数映射功能。比方说对数线性回归（log-linear regression），令 $g(\cdot) = ln(\cdot)$，此时模型预测值对应的是实值标记在指数尺度上的变化：

$$\ln y = \mathbf{w^Tx} + b$$

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

前面说的是线性模型在回归学习方面的应用，这节开始就是讨论分类学习了。

线性模型的输出是一个实值，而分类任务的标记是离散值，怎么把这两者联系起来呢？其实广义线性模型已经给了我们答案，我们要做的就是找到一个单调可微的联系函数，把两者联系起来。

对于一个二分类任务，比较理想的联系函数是单位阶跃函数（unit-step function）：

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

但是单位阶跃函数不连续，所以不能直接用作联系函数。这时思路转换为如何近似单位阶跃函数呢？**对数几率函数（logistic function）**正是我们所需要的（注意这里的 $y$ 依然是实值）：

$$y = \frac{1}{1+e^{-z}}$$

对数几率函数有时也称为对率函数，是一种Sigmoid函数（即形似S的函数）。将它作为 $g^-(\cdot)$ 代入广义线性模型可得：

$$y = \frac{1}{1+ e^{-(\mathbf{w^Tx} + b)}}$$

该式可以改写为：

$$\ln{\frac{y}{1-y}} = \mathbf{w^Tx} + b$$

其中，$\frac{y}{1-y}$ 称作几率（odds），我们可以把 $y$ 理解为该样本是正例的概率，把 $1-y$ 理解为该样本是反例的概率，而几率表示的就是该样本作为正例的相对可能性。若几率大于1，则表明该样本更可能是正例。对几率取对数就得到对数几率（log odds，也称为logit）。几率大于1时，对数几率是正数。

由此可以看出，对数几率回归的实质使用线性回归模型的预测值逼近分类任务真实标记的对数几率。它有几个优点：

1. 直接对分类的概率建模，无需实现假设数据分布，从而避免了假设分布不准确带来的问题；
2. 不仅可预测出类别，还能得到该预测的概率，这对一些利用概率辅助决策的任务很有用；
3. 对数几率函数是任意阶可导的凸函数，有许多数值优化算法都可以求出最优解。

最大似然估计

有了预测函数之后，我们需要关心的就是怎样求取模型参数了。这里介绍一种与最小二乘法异曲同工的办法，叫做极大似然法（maximum likelihood method）。我在另一个项目中有这方面比较详细的讲解，欢迎前往项目主页交流学习。

前面说道可以把 $y$ 理解为一个样本是正例的概率，把 $1-y$ 理解为一个样本是反例的概率。而所谓极大似然，就是最大化预测事件发生的概率，也即最大化所有样本的预测概率之积。令 $p(c=1|\mathbf{x})$ 和 $p(c=0|\mathbf{x})$ 分别代表 $y$ 和 $1-y$。（注：书中写的是 $y=1$ 和 $y=0$，这里为了和前面的 $y$ 区别开来，我用了 $c$ 来代表标记）。简单变换一下公式，可以得到：

$$p(c=1|\mathbf{x}) = \frac{e^(\mathbf{w^Tx} + b)}{1+e^{\mathbf{w^Tx} + b}}$$ $$p(c=0|\mathbf{x}) = \frac{1}{1+e^{\mathbf{w^Tx} + b}}$$

但是！由于预测概率都是小于1的，如果直接对所有样本的预测概率求积，所得的数会非常非常小，当样例数较多时，会超出精度限制。所以，一般来说会对概率去对数，得到对数似然（log-likelihood），此时求所有样本的预测概率之积就变成了求所有样本的对数似然之和。对率回归模型的目标就是最大化对数似然，对应的似然函数是：

$$\ell(\mathbf{w},b) = \sum_{i=1}^m \ln p(c_i | \mathbf{x_i;w};b)\\ = \sum_{i=1}^m \ln (c_ip_1(\hat{\mathbf{x_i}};\beta) + (1-c_i)p_0(\hat{\mathbf{x_i}};\beta))$$

可以理解为若标记为正例，则加上预测为正例的概率，否则加上预测为反例的概率。其中 $\beta = (\mathbf{w};b)$。

对该式求导，令导数为0可以求出参数的最优解。特别地，我们会发现似然函数的导数和损失函数是等价的，所以说最大似然解等价于最小二乘解。最大化似然函数等价于最小化损失函数：

$$E(\beta) = \sum_{i=1}^m (-y_i\beta^T\hat{x_i} + \ln (1+e^{\beta^T\mathbf{\hat{x_i}}}))$$

这是一个关于 $\beta$ 的高阶可导连续凸函数，可以用最小二乘求（要求矩阵的逆，计算开销较大），也可以用数值优化算法如梯度下降法（gradient descent method）、**牛顿法（Newton method）**等逐步迭代来求最优解（可能陷入局部最优解）。

线性判别分析（LDA）

二分类

线性判别分析（Linear Discriminant Analysis，简称LDA），同样是利用线性模型，LDA提供一种不同的思路。在LDA中，我们不再是拟合数据分布的曲线，而是将所有的数据点投影到一条直线上，使得同类点的投影尽可能近，不同类点的投影尽可能远。二分类LDA最早有Fisher提出，因此也称为Fisher判别分析。

具体来说，投影值 $y = \mathbf{w}^T\mathbf{x}$，我们不再用 $y$ 逼近样例的真实标记，而是希望同类样例的投影值尽可能相近，异类样例的投影值尽可能远离。如何实现呢？首先，同类样例的投影值尽可能相近意味着同类样例投影值的协方差应尽可能小；然后，异类样例的投影值尽可能远离意味着异类样例投影值的中心应尽可能大。合起来，就等价于最大化：

$$J = \frac{\Vert \mathbf{w}^T\mu_0 - \mathbf{w}^T\mu_1 \Vert^2_2}{\mathbf{w}^T\Sigma_0\mathbf{w}+\mathbf{w}^T\Sigma_1\mathbf{w}}\\ = \frac{\mathbf{w}^T(\mu_0 - \mu_1)(\mu_0 - \mu_1)^T\mathbf{w}}{\mathbf{w}^T(\Sigma_0+\Sigma_1)\mathbf{w}}$$

其中，分子的 $\mu_i$ 表示第i类样例的均值向量（即表示为向量形式后对各维求均值所得的向量）。分子表示的是两类样例的均值向量投影点（也即类中心）之差的 $\ell_2$ 范数的平方，这个值越大越好。 分母中的 $\Sigma_i$ 表示第i类样例的协方差矩阵。分母表示两类样例投影后的协方差之和，这个值越小越好。

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

$$S_w = \sigma_0 + \sigma_1\\ = \sum_{x \in X_0} (\mathbf{x} - \mu_0)(\mathbf{x} - \mu_0)^T + \sum_{x \in X_1} (\mathbf{x} - \mu_1)(\mathbf{x} - \mu_1)^T$$

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

$$S_b = (\mu_0 - \mu_1)(\mu_0 - \mu_1)^T$$

这两个矩阵的规模都是 $d\times d$，其中 $d$ 是样例的维度（属性数目）。于是可以重写目标函数为：

$$J = \frac{\mathbf{w}^T S_b \mathbf{w}}{\mathbf{w}^T S_w \mathbf{w}}$$

也即 $S_b$ 和 $S_w$ 的广义瑞利熵（generalized Rayleigh quotient）。

可以注意到，分子和分母中 $w$ 都是二次项，因此，最优解与 $w$ 的大小无关，只与方向有关。

令分母为1，用拉格朗日乘子法把约束转换为方程，再稍加变换我们便可以得出：

$$\mathbf{w} = S_w^{-1}(\mu_0 - \mu_1)$$

但一般不直接对矩阵 $S_w$ 求逆，而是采用奇异值分解的方式。

多分类

多分类LDA与二分类不同在于，学习的是一个规模为 $d \times d'$ 的投影矩阵 $\mathbf{W}$，而不是规模为 $d \times 1$ 的投影向量 $\mathbf{w}$。这个投影矩阵把样本投影到 $d'$ 维空间（或者说 $d'$ 维超平面）上，由于 $d'$ 通常远小于样例原来的属性数目 $d$，且投影过程用到了类别信息（标记值），所以LDA也常常被视为一种监督降维技术。（注：$d'$ 最大可取为类别数-1）

多分类学习

有些二分类学习方法（如LDA）可以直接推广到多分类，但现实中我们更多地是基于一些策略，把多分类任务分解为多个二分类任务，利用二分类模型来解决问题。有三种最经典的拆分策略，分别是一对一，一对其余，和多对多。

一对一

**一对一（One vs. One，简称OvO）**的意思是把所有类别两两配对。假设样例有N个类别，OvO会产生 $\frac{N(N-1)}{2}$ 个子任务，每个子任务只使用两个类别的样例，并产生一个对应的二分类模型。测试时，新样本输入到这些模型，产生 $\frac{N(N-1)}{2}$ 个分类结果，最终预测的标记由投票产生，也即把被预测得最多的类别作为该样本的类别。

一对其余

一对其余（One vs. Rest，简称OvR）在有的文献中也称为一对所有（One vs. All，简称OvA），但这种说法并不严谨。因为OvR产生 $N$ 个子任务，每个任务都使用完整数据集，把一个类的样例当作正例，其他类的样例当作反例，所以应该是一对其余而非一对所有。OvR产生 $N$ 个二分类模型，测试时，新样本输入到这些模型，产生 $N$ 个分类结果，若只有一个模型预测为正例，则对应的类别就是该样本的类别；若有多个模型预测为正例，则选择置信度最大的类别（参考模型评估与选择中的比较检验）。

OvO和OvR各有优劣：OvO需要训练的分类器较多，因此OvO的存储开销和测试时间开销通常比OvR更大；OvR训练时要用到所有样例，因此OvR的训练时间开销通常比OvO更大。测试性能取决于具体的数据分布，大多情况下这两个拆分策略都差不多。

多对多

**多对多（Many vs. Many，简称MvM）**是每次将多个类作为正例，其他的多个类作为反例。OvO和OvR都是MvM的特例。书中介绍的是一种比较常用的MvM技术——纠错输出码（Error Correcting Outputs Codes，简称ECOC）。

MvM的正反例划分不是任意的，必须有特殊的构造，否则组合起来时可能就无法定位到预测为哪一类了。ECOC的工作过程分两步：

• 编码：对应于训练。假设有N个类别，计划做M次划分，每次划分把一部分类别划为正类，一部分类别划分为反类，最终训练出M个模型。而每个类别在M次划分中，被划为正类则记作+1，被划为负类则记作-1，于是可以表示为一个M维的编码。

• 解码：对应于预测。把新样本输入M个模型，所得的M个预测结果组成一个预测编码。把这个预测编码和各个类别的编码进行比较，跟哪个类别的编码距离最近就预测为哪个类别。

类别划分由编码矩阵（coding matrix）指定，编码矩阵有多重形式，常见的有二元码（正类为+1，负类为-1）和三元码（多出了停用类，用0表示，因为有停用类的存在，训练时可以不必使用全部类别的样例）。举个三元码的例子：

	f1 $\downarrow$	f2 $\downarrow$	f3 $\downarrow$	f4 $\downarrow$	f5 $\downarrow$	海明距离 $\downarrow$	欧氏距离 $\downarrow$
$C_1\rightarrow$	-1	+1	-1	+1	+1	4	4
$C_2\rightarrow$	+1	-1	-1	+1	-1	2	2
$C_3\rightarrow$	-1	+1	+1	-1	+1	5	2$\sqrt{5}$
$C_4\rightarrow$	-1	-1	+1	+1	-1	3	$\sqrt{10}$
测试样本$\rightarrow$	-1	-1	+1	-1	+1	-	-

这里一共有4个类别，对应每一行。计划做5次划分，得到f1至f5共五个二分类器，对应每一列。可以看到每一个类别有一个5位的编码表示。测试时，把新样本输入到5个模型，得到预测编码。然后计算这个预测编码和每个类别编码的距离。这里举了海明距离（不同的位数的数目）和欧氏距离作为例子。可以看到测试样本与类别2的距离最近，因此预测该样本为类别2。

特别地，为什么称这种方法为纠错输出码呢？因为ECOC编码对分类器的错误有一定的容忍和修正能力。即使预测时某个分类器预测成了错误的编码，在解码时仍然有机会产生正确的最终结果。具体来说，对同一个学习任务，编码越长，纠错能力越强。但是相应地也需要训练更多分类器，增大了计算和存储的开销。

对同等长度的编码来说，理论上任意两个类别之间的编码距离越远，纠错能力越强。但实际任务中我们一般不需要获取最优编码，一方面非最优编码已经能产生不错的效果；另一方面，即使获得理论上最优的编码，实际性能也不一定最好。因为机器学习还涉及其他一些方面，在划分多个类时产生的新问题难度往往也不同，有可能理论最优的编码产生的类别子集难以区分，问题难度更大，从而使得性能下降。

类别不平衡问题

**类别不平衡（class-imbalance）**问题非常普遍，比方说推荐系统中用户购买的商品（通常视作正例）和用户未购买的商品（通常视作反例）比例是极为悬殊的。如果直接用类别不平衡问题很严重的数据集进行训练，所得模型会严重偏向所占比例较大的类别。本节默认正类样例较少，负类样例较多。这里主要介绍三种做法：

欠采样

欠采样（undersampling）针对的是负类，也即移取训练集的部分反例，使得正类和负类的样例数目相当。由于丢掉了大量反例，所以时间开销也大大减少。但是带来一个问题就是，随机丢弃反例可能会丢失一些重要信息。书中提到一种解决方法是利用集成学习机制，将反例划分为多个集合，用于训练不同的模型，从而使得对每个模型来说都进行了欠采样，但全局上并无丢失重要信息。

过采样

过采样（oversampling）针对的是正类，也即增加训练集的正例，使得正类和负类的样例数目相当。过采样的时间开销会增大很多，因为需要引入很多正例。注意！过采样不能简单地通过重复正例来增加正例的比例，这样会引起严重的过拟合问题。一种较为常见的做法是对已有正例进行插值来产生新的正例。

阈值移动

阈值移动（threshold-moving）利用的是再缩放思想。回想前面对数几率回归中，几率 $\frac{y}{1-y}$ 表示正例的相对可能性，我们默认以1作为阈值，其实是假设了样本的真实分布为正例反例各一半。但这可能不是真相，假设我们有一个存在类别不平衡问题的训练集，正例数目为 $m^+$，反例数目为 $m^-$，可以重定义：

$$\frac{y'}{1-y'} = \frac{y}{1-y} \times \frac{m^-}{m^+}$$

这就是再缩放（rescaling）。当几率大于 $\frac{m^+}{m^-}$ 时就预测为正例。但必须注意，这种思想是基于观测几率近似真实几率这一假设的，现实任务中这一点未必成立。

习题

3.1

问：试析在什么情形下，预测函数 $f(\mathbf{x}) = \mathbf{w}^T\mathbf{x} + b$ 中不必考虑偏置项 $b$。

Quora上就有这个问题，而且解释得也不错。试想一下，拟合曲线时，如果不考虑偏置项，则只能拟合一条过原点的曲线。在多元线性回归中也同理，如果不考虑偏置项，那么拟合的超平面就只能过原点，但现实中数据点的分布并不是这样的。使用一个不依赖于属性的的偏置项能够让权重向量所描述的超平面更好地拟合数据点的分布。如果输出值的期望（均值）为0就不需要考虑偏置项了，或者说偏置项此时就等于0。

3.2

问：试证明，对于参数w，对率回归（logistics回归）的目标函数（式1）是非凸的，但其对数似然函数（式2）是凸的。

式1：$y = \frac{1}{1+ e^{-(\mathbf{w^Tx} + b)}}$

式2：$E(\beta) = \sum_{i=1}^m (-y_i\beta^T\hat{x_i} + \ln (1+e^{\beta^T\mathbf{\hat{x_i}}}))$

笔记中已经提到了，检验一个函数是否凸函数，可以看其二阶导数是否在区间上恒大于0.

目标函数（也即sigmoid函数）：

显然，sigmoid的二阶导数在自变量大于0处取值小于0，所以它不是凸函数。

对数似然函数：

可以看到这个函数在区间上恒大于0（两边无限延伸），符合凸函数的要求，但我不太明白的是为什么作者把这个函数仍然称为对数似然函数，对数几率回归目标是最大化对数似然，最小化损失，私以为把这个函数称为损失函数更合适。

3.3

问：编程实现对率回归，并给出西瓜数据集3.0α上的结果

西瓜数据集3.0α：

编号	密度	含糖率	好瓜
1	0.697	0.460	是
2	0.774	0.376	是
3	0.634	0.264	是
4	0.608	0.318	是
5	0.556	0.215	是
6	0.403	0.237	是
7	0.481	0.149	是
8	0.437	0.211	是
9	0.666	0.091	否
10	0.243	0.0267	否
11	0.245	0.057	否
12	0.343	0.099	否
13	0.639	0.161	否
14	0.657	0.198	否
15	0.36	0.37	否
16	0.593	0.042	否
17	0.719	0.103	否

把这个数据集转换为csv表格，并且注意要把标记转换为0、1，注意不是-1、+1！！逻辑回归的二分类标记必须是0、1，对应于sigmoid函数的值域。

代码实现放在了code文件下的exercise3.3.ipynb，不过Github似乎不支持ipynb的在线预览，可以下载下来用ipython notebook打开。结果如下：

用了梯度上升法来更新权值，步长0.05，最大迭代次数2000次。上图中红色为好瓜，绿色为坏瓜，圆形标记表示预测正确，叉号标记表示预测错误。可以看到有一个好瓜被预测为坏瓜，有两个坏瓜被预测为好瓜。事实上，在200次迭代后，已经基本定型了，权值并没有太大的变化。

3.4

问：选择两个UCI数据集，比较10折交叉验证法和留一法所估计出的对率回归的错误率。

在UCI数据集上可以进行下载。最近时间不多，暂且挖个坑。

3.5

问：编程实现线性判别分析，并给出西瓜数据集3.0α上的结果

最近时间不多，暂且挖个坑。

3.6

问：LDA仅在线性可分数据上能获得理想结果，试设计一个改进方法，使其能较好地用于非线性可分数据

可以利用核方法，把非线性可分数据的分布转换为线性可分，书上137页有介绍：KLDA（核线性判别分析方法）。

3.7

问：令码长为9，类别数为4，试给出海明距离意义下理论最优的EOOC二元码并证明之。

码长为9，即要产生9个分类器，因此需要9种划分方面。类别数为4，因此1V3有4种分法，2V2有6种分法，3V1同样有4种分法。书上说理论上任意两个类别之间的距离越远，纠错能力就越强。这句话可以理解为各个类别之间的距离之和越大约好。对于1个2V2分类器，4个类别的海明距离累积为4；对于3V1与1V3分类器，海明距离均为3，所以可以认为2V2的效果更好。故最优EOOC二元码由6个2V2分类器和3个3v1或1v3分类器构成。

3.8*

问：EOOC编码能起到理想纠错作用的重要条件是：在每一位编码上出错的概率相当且独立。试析多分类任务经ECOC编码后产生的二类分类器满足该条件的可能性及由此产生的影响。

在每一位编码上出错的概率即指在第i个分类器上的错误率，假设每个分类器选择相同的模型与最优的参数。那么满足概率相当并且独立应该需要每个分类器的正负例比例相当，并且每个分类器划分的正负例在空间中的相对分布情况应当相近。一般情况下一般很难满足这样的条件，肯定会有错误率较高的分类器。错误率较高的分类器在较少时影响不大，但当高错误率分类器占到多数时，就会拖低整体的错误率。所以我认为在某些极端情况下，增加码长可能会降低正确率

3.9

问：使用OvR和MvM将多分类任务分解为二分类任务求解时，试述为何无需专门针对类别不平衡性进行处理。

因为OvR或者MvM在输出结果阶段，是对各个二分类器的结果进行汇总，汇总的这个过程就会消除不平衡带来的影响（因为总和总是1）

3.10*

问：试推导出多分类代价敏感学习（仅考虑基于类别的误分类代价）使用“再缩放“能获得理论最优解的条件。

最近时间不多，暂且挖个坑。