西瓜书第三章习题

1.试分析在什么情况下，在式 $f(x) = w^Tx + b$ 式子中不比考虑偏置项b。

答 :

ωT 和b有各自的意义，简单来说，ωT决定学习得到模型的方向，而b则决定截距，可以理解为模型不能解释的一部分，因此一般情况下是需要考虑偏置项的。当学习得到的模型恰好经过原点时，可以不考虑偏置项b。但如果对数据进行了归一化处理，学习到的模型会经过原点，那么此时b = 0,可以不考虑b。

2.试证明，对于参数w，对率回归（logistics回归）的目标函数（式1） $y=\frac{1}{ 1+e^{−(ω^Tx+b)}}$ 是非凸的，但其对数似然函数（式2） $l(β)=∑^m_{i=1}(−y_iβ^Tx_i+ln(1+e^{β^T}x))$ 是凸的。

答：

凸函数的定义：对区间[a,b]上定义的函数f(x)，若它对区间中任意两点x1，x2均有 $f(\frac{x_1+x_2}{2} )≤\frac{f(x_1)+f(x_2)}{2}$ ，

则称f(x)为区间[a,b]上的凸函数。

证明式一函数为非凸的，这里根据其图像判断

图像的在【- $∞$ ，0】是凸函数，在【0，+ $∞$ 】区间上是凹函数，函数有凸也有凹，因此式一函数为非凸。

logistics

对于式2       $l(β)=∑^m_{i=1}(−y_iβ^Tx_i+ln(1+e^{β^T}x))$ ，

证明其函数为凸函数，可以证明其二阶导是非负的

对于 β 的二阶导有（原书p60）

       $\frac{∂^2 l(β)}{∂β∂β^T} = ∑_{i=1}^m x_i x_i^{T} p_1( x_i ;β)(1−p_ 1( x_i))=XPX^T$

关于 $XPX^T$ ,对于任意向量 z都有：

       $z^TXPX^Tz=(X^Tz)^TP(X^Tz)=v^TPv=∑_iP_{ii}v_i^2≥0$

因此其二阶导非负。

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

西瓜数据集3.0α

代码思路：

1. 初始化变量

定义学习率，模型参数w, 迭代次数

2. 定义训练函数

接收输入的数据data

根据输入的数据定义模型参数w的形状大小

采用SGD算法对参数w进行计算

每次选择样本集中的一个样本

根据公式计算梯度

更新参数，直到迭代次数到达输入的迭代次数为止

3.定义预测函数

根据模型计算输出的概率值

判断该值是否大于阈值（0.5）判断其正负

代码执行结果

代码链接：我的码云

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

网络上大多采用 iris数据集，该数据集可有sklearn导入，因此本题的两个数据集，iris数据集，乳腺癌数据集，均由sklearn内置数据集导入

k折交叉验证法KFold将所有的样例划分为 k个组，称为折叠 (fold) ，都具有相同的大小（如果可能）。预测函数学习时使用 k-1 个折叠中的数据，最后一个剩下的折叠会用于测试。

留一法LOO 是一个简单的交叉验证。每个学习集都是通过除了一个样本以外的所有样本创建的，测试集是被留下的样本。因此，对于 n个样本，我们有 n个不同的训练集和 n个不同的测试集。这种交叉验证程序不会浪费太多数据，因为只有一个样本是从训练集中删除掉的

代码结果

对应两种选择数据集集的方法，在乳腺癌数据集上者无明显区别，但在iris数据集上，留一法明显优于10折交叉验证法,出现该现象的原因我认为是

iris 的数据量大小为150条，乳腺癌数据的大小接近600条

每一次训练留一法可以考虑更多的样本的特征，因此在数据量小的情况下，留一法效果比 k 折交叉验证法要好，对于上了一定规模的数据，两者之间效果就没有很明显的差异。

因此用在小量的数据集上采用留一法可以达到更好的效果。

代码链接：我的码云

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

代码思路：

1. 模型初始化

接收模型最终降维的维度d

2. 定义求均值函数

根据输入的数据计算每个类别对应的均值向量

3. 计算两个主要的矩阵

类内散布矩阵

类间散布矩阵

4.定义训练函数，求出lda模型的参数w

接收输入的数据

通过2，3计算得到必要的两个矩阵

根据公式对两个矩阵的乘积做特征值分解

根据其特征值的大小排序，组合前d个最大的对应的特征向量为模型参数w

5.定义预测函数

将第4步得到的模型参数对预测的数据做线性运算得到降维后的输出

代码执行结果

代码链接：我的码云

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

答：

参考svm的算法设计，lda于svm两者之间有着共同的特性

1.两者都是线性模型

2.两者均可用于处理分类任务

当svm线性不可分的时候，会采用核函数的方法将低纬线性不可分的数据映射到高维，使得线性可分。

同理，lda出现当前维度线性不可分的时候，采取核函数的方法，将数据映射到高维，使之线性可分。

典型的方法有KLDA（核线性判别分析）

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

答：

问题的解决思路：

对同等长度的编码，理论上来说，任意两个类别之间的编码距离越远，则纠错能力越强。因此，在码长较小时可根据这个原则计算出理论最优编码。

假设任意两个类别之间最小的海明距离为 d，那么此纠错输出码最少能矫正 $\left[\frac{d-1}{2}\right]$

拿上图的例子解释一下，上图中，所有类别之间的海明距离都为4，假设一个样本正确的类别为 c1 ，那么codeword应该为 ‘0 0 1 1 0 0 1 1’，若此时有一个分类器输出错误，变成‘0 0 0 1 0 0 1 1’，那么此时距离最近的仍然为 c1，若有两个分类输出错误如‘0 0 0 0 0 0 1 1’，此时与 c1,c2的海明距离都为2，无法正确分类。即任意一个分类器将样本分类错误，最终结果依然正确，但如果有两个以上的分类器错误，结果就不一定正确了。这是 $\left[\frac{d-1}{2}\right]$ 的由来。

一个好的纠错输出码应该满足两个条件：

行分离。任意两个类别之间的codeword距离应该足够大。

列分离。任意两个分类器 $f_{i}, f_{j}$ 的输出应相互独立，无关联。这一点可以通过使分类器 $f_{i}$ 编码与其他分类编码的海明距离足够大实现，且与其他分类编码的反码的海明距离也足够大。

下面引用的一篇文章中给出了构造编码的方法

按照这种方法，在类别为4时，其可行的编码有7种

当码长为9时，那么 $f_6$ 之后加任意两个编码，即为最优编码，因为此时再加任意的编码都是先有编码的反码，此时，类别之间最小的海明距离都为4，不会再增加。

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

答：

问题拆解，一是出错的概率相当，二是出错的可能性相互独立。

第一：出错的概率相当，

满足该条件的可能性 ：将多个类拆解为两个"类别子集“，所形成的两个类别子集的区分难度往往不同，即其导致的二分类问题的难度不同。所以每个编码拆解后类别之间的差异越相同（区分难度相当），则满足此条件的可能性越大。在实际中其实很难满足。（原书P66）

由此产生的影响 ：因为如果某个码位的错误率很高，会导致这位始终保持相同的结果，不再有分类作用，这就相当于全0或者全 1的分类器。

第二：相互独立，