《机器学习》西瓜书习题第 3 章

3.1

　　试析在什么情况下式 \((3.2)\) 中不必考虑偏置项 \(b\) .

　　书中有提到, 可以把 \(x\) 和 \(b\) 吸收入向量形式 \(\hat{w} = (w;b)\) .此时就不用单独考虑 \(b\) 了.
　　其实还有很多情况不用, 比如说使用了 \(\mathrm{one-hot}\) 编码, 就可以不用考虑偏置项.
　　更广泛的情况是, 如果偏置项 \(b\) 可以被 "包含" 在另外的一些离散特征里, 那么就不用考虑. 就是偏置项可以以一定系数加到离散特征中. (可能看了还是不太懂, 我以后有时间会重写一个的.)

3.2

　　试证明, 对于参数 \(w\), 对率回归的目标函数 \((3.18)\) 是非凸的, 但其对数似然函数 \((3.27)\) 是凸的.

\[y = \frac{1}{1 + e^{-(\boldsymbol w^\mathrm T\boldsymbol x + b)}}\tag{3.18}
\]

\[\ell(\boldsymbol\beta) = \sum^m_{i = 1}(-y_i\boldsymbol \beta^\mathrm T\boldsymbol{\hat{x}}_i)\tag{3.18}
\]

　　计算其海森矩阵, 判断是否正定. 海森矩阵可以类比成一元函数的二阶导, 正定可以类比为二阶导恒大于 \(0\) .

3.3

　　编程实现対率回归, 并给出西瓜数据集 \(3.0\alpha\) 上的结果.

　　《机器学习》西瓜书第 3 章编程实例

3.4

　　选择两个 \(\mathrm{UCI}\) 数据集, 比较 \(10\) 折交叉验证法和留一法所估计出的错误率.

　　《机器学习》西瓜书第 3 章编程实例

3.4

　　编程实现线性判别分析, 并给出西瓜数据集 \(3.0\alpha\) 上的结果.

　　《机器学习》西瓜书第 3 章编程实例

3.6

　　线性判别分析仅在线性可分数据上能获得理想结果, 试设计一个改进方法, 使其能较好地用于飞线性可分数据.

　　像 \(6.3\) 节介绍的那样, 使用核函数, 就可以运用于非线性可分数据.

3.7

　　令码长为 \(9\), 类别数为 \(4\) , 试给出海明距离意义下理论最优的 \(\mathrm{ECOC}\) 二元码并证明之.

　　首先要给出理论最优, 我们先要确定 '最优' 的指导标准.

　　对同等长度的编码, 理论上来说, 任意两个类别之间的编码距离越远, 则纠错能力越强.

　　我们要将 '任意两个类别的编码距离' 用数学表达, 这样才能进行求解. 那么怎么用数学表达这个 '距离' 呢? 这里考虑到 '总体距离最大' , 同时我们还要保证每两个类别之间的反码的距离也 '最大' , 所以我们浅显的使用每两个类别之间的海明距离乘和其反码的海明距离的积来作为衡量标准(有点绕), 我们定义一个变量 \(L\) 用来表达这个积, 也就是有

\[L = \prod_{1\leqslant i< j\leqslant 4}dis(r_i, r_j)dis(r_i, -r_j)
\]

\(dis(r_i, r_j)\) 表示第 \(i\) 个编码和第 \(j\) 个编码之间的海明距离, \(dis(r_i, r_j)\) 表示第 \(i\) 个编码和第 \(j\) 个编码的反码之间的海明距离. \(L\) 越大代表这种编码方式越好.
　　于是我写了段程序来搜索 \(L\) 的最大值 ~~(直接爆搜)~~ .

#include<iostream>
#include<cmath>
using namespace std;


const int MAXCOL = 9;  // 码长为 9 
const int MAXROW = 4;  // 类别数为 4 

bool code[MAXROW][MAXCOL];  // 记录最大值时编码排列
bool temp_code[MAXROW][MAXCOL];  // 表示当前编码排列

int mmax = 0;  // 记录最大值


int dif_val(bool a[MAXCOL], bool b[MAXCOL]){  // 求两个编码之间的海明距离
    int cnt1 = 0;
    int cnt2 = 0;
    for(int i = 0 ; i < MAXCOL ; ++i){
        if(a[i] != b[i])    ++cnt1;
        if(a[i] == b[i])	++cnt2;
    }
    return cnt1 * cnt2;
}

int cost(bool code[MAXROW][MAXCOL]){  // 求当前编码排列的 L
    int res = 1;
    for(int i = 0 ; i < MAXROW ; ++i){
        for(int j = i + 1 ; j < MAXROW ; ++j){
            res *= dif_val(code[i], code[j]);
        }
    }
    return res;
}

void dfs(int row = 2, int col = 0){  // 深度优先搜索, 枚举每个位置的编码 (0 和 1)
    if(row == MAXROW)    return;  // 边界条件
    temp_code[row][col] = 1;  // 先枚举 1
    int temp = cost(temp_code);
    if(mmax < temp){  // 发现更好的编码排列, 进行更新
        mmax = temp;
        for(int i = 0 ; i < MAXROW ; ++i)
            for(int j = 0 ; j < MAXCOL ; ++j)
                code[i][j] = temp_code[i][j];
    }
    if(col == MAXCOL - 1)    dfs(row + 1, 0);  // 下一层
    else    dfs(row, col + 1);
    temp_code[row][col] = 0;  // 返回再枚举 0
    temp = cost(temp_code);
    if(mmax < temp){  // 同上
        mmax = temp;
        for(int i = 0 ; i < MAXROW ; ++i)
            for(int j = 0 ; j < MAXCOL ; ++j)
                code[i][j] = temp_code[i][j];
    }
    if(col == MAXCOL - 1)    dfs(row + 1, 0);  // 同上
    else    dfs(row, col + 1);
    return ;
}

int main(){
    for(int i = 0 ; i < MAXCOL ; ++i){
        temp_code[0][i] = 1;  // 不失一般性, 令第一个类别的编码全部为 1 
    }
    for(int i = 1 ; i <= MAXCOL ; ++i){  // 不失一般性, 枚举第二个类别 1 的数量 (1 ~ 9)
        temp_code[1][i - 1] = 1;
        dfs();
    }
    for(int i = 0 ; i < MAXROW ; ++i){  // 打印最终结果
        for(int j = 0 ; j < MAXCOL ; ++j){
            cout << code[i][j] << ' ';
        }
        cout << endl;
    }
    cout << mmax;
    return 0;
}  // 我的码风是不是很好看

结果: