第一题
给定三分类判别函数：
$d_1(x)=-x_1,\quad d_2(x)=x_1+x_2-1,\quad d_3(x)=x_1-x_2-1$
为便于核对，常用的等值边界（两两相等）为：
$$ \begin{aligned} d_1 = d_2 &\Rightarrow x_2 = 1 - 2x_1 \ d_1 = d_3 &\Rightarrow x_2 = 2x_1 - 1 \ d_2 = d_3 &\Rightarrow x_2 = 0 \end{aligned} $$
图中背景色表示分类区域（1/2/3 类），黑色线条为主要分界线（同时附上 $d_i=0$ 的参考线）。
(a) 一对多（One-vs-Rest）
- 规则：对同一个 $x$，计算 $d_1(x),d_2(x),d_3(x)$，取最大者对应的类别：$\hat\omega(x)=\arg\max_i d_i(x)$。
(b) 一对一（One-vs-One）
给定：
$d_{12}(x)=d_1(x),\quad d_{13}(x)=d_2(x),\quad d_{23}(x)=d_3(x)$
- 两两判决：若 $d_{ij}(x)>0$ 则投票给 $i$，否则投票给 $j$。
- 最终类别：多数票获胜（平票按类别编号小者）。
(c) 多类情况3（1v1 的特例）
- 先根据三对分类器判断是否存在“全胜者”（Condorcet winner）：某一类在其相关的两场两两比较中都获胜，则直接选它。
- 若不存在全胜者（出现循环/平局），则回退到 (b) 的多数投票法。
第二题
Fisher 线性判别的步骤如下：
- 计算总类内散度矩阵 $\mathbf{S}_w = \mathbf{S}_1 + \mathbf{S}_2$。
- 求最佳投影方向 $\mathbf{w} = \mathbf{S}_w^{-1}(\mathbf{m}_1 - \mathbf{m}_2)$。
- 将两类中心投影到 $\mathbf{w}$ 上，取中点作为分类阈值 $y_0$，从而得到决策面 $\mathbf{w}^T\mathbf{x} = y_0$。
1. 总类内散度矩阵
$$
\mathbf{S}_1 = \begin{bmatrix} 1 & \frac{1}{2} \ \frac{1}{2} & 1 \end{bmatrix}, \quad
\mathbf{S}_2 = \begin{bmatrix} 1 & -\frac{1}{2} \ -\frac{1}{2} & 1 \end{bmatrix}
$$
$$
\mathbf{S}_w = \mathbf{S}_1 + \mathbf{S}_2 =
\begin{bmatrix} 1+1 & \frac{1}{2} - \frac{1}{2} \ \frac{1}{2} - \frac{1}{2} & 1+1 \end{bmatrix} =
\begin{bmatrix} 2 & 0 \ 0 & 2 \end{bmatrix} = 2\mathbf{I}
$$
其逆矩阵为 $\mathbf{S}_w^{-1} = \frac{1}{2}\mathbf{I}$。
2. 最佳投影方向
$$
\mathbf{m}_1 = \begin{pmatrix} 2 \ 0 \end{pmatrix}, \quad
\mathbf{m}_2 = \begin{pmatrix} 2 \ 2 \end{pmatrix}, \quad
\mathbf{m}_1 - \mathbf{m}_2 = \begin{pmatrix} 0 \ -2 \end{pmatrix}
$$
$$
\mathbf{w} = \mathbf{S}_w^{-1}(\mathbf{m}_1 - \mathbf{m}_2) =
\frac{1}{2}\begin{pmatrix} 0 \ -2 \end{pmatrix} =
\begin{pmatrix} 0 \ -1 \end{pmatrix}
$$
（注：$\mathbf{w}$ 的方向可乘以任意正数，这里取上述结果。）
3. 投影及阈值
两类中心在 $\mathbf{w}$ 上的投影值：
$$
y_1 = \mathbf{w}^T \mathbf{m}_1 = (0,,-1)\begin{pmatrix} 2 \ 0 \end{pmatrix} = 0
$$
$$
y_2 = \mathbf{w}^T \mathbf{m}_2 = (0,,-1)\begin{pmatrix} 2 \ 2 \end{pmatrix} = -2
$$
取中点作为分类阈值（假设两类先验概率相等）：
$$
y_0 = \frac{y_1 + y_2}{2} = \frac{0 + (-2)}{2} = -1
$$
于是决策面方程为：
$$
\mathbf{w}^T\mathbf{x} = y_0 \quad\Longrightarrow\quad -x_2 = -1 \quad\Longrightarrow\quad x_2 = 1
$$
最终结果：
投影阈值 $y_0 = -1$，对应的空间决策面为 $x_2 = 1$。
第三题
首先整理题目中的两类样本：
$\omega_1$ 类样本（$n_1=3$）：
$$\boldsymbol{x}{11} = (0, 0, 1)^T,\ \boldsymbol{x}{12} = (0, 1, 0)^T,\ \boldsymbol{x}_{13} = (0, 1, 1)^T$$$\omega_2$ 类样本（$n_2=3$）：
$$\boldsymbol{x}{21} = (1, 1, 0)^T,\ \boldsymbol{x}{22} = (1, 0, 1)^T,\ \boldsymbol{x}_{23} = (1, 1, 1)^T$$
均值向量公式：
$$\boldsymbol{m}i = \frac{1}{n_i} \sum{\boldsymbol{x} \in \omega_i} \boldsymbol{x}$$$\omega_1$ 类均值：
$$
\boldsymbol{m}_1
= \frac{1}{3} \left(
\begin{pmatrix} 0 \ 0 \ 1 \end{pmatrix}
- \begin{pmatrix} 0 \ 1 \ 0 \end{pmatrix}
- \begin{pmatrix} 0 \ 1 \ 1 \end{pmatrix}
\right)
= \begin{pmatrix} 0 \ \dfrac{2}{3} \ \dfrac{2}{3} \end{pmatrix}
$$
- $\omega_2$ 类均值：
$$
\boldsymbol{m}_2
= \frac{1}{3} \left(
\begin{pmatrix} 1 \ 1 \ 0 \end{pmatrix}
- \begin{pmatrix} 1 \ 0 \ 1 \end{pmatrix}
- \begin{pmatrix} 1 \ 1 \ 1 \end{pmatrix}
\right)
= \begin{pmatrix} 1 \ \dfrac{2}{3} \ \dfrac{2}{3} \end{pmatrix}
$$
类间差异向量：
$$
\boldsymbol{m}_1 - \boldsymbol{m}_2
= \begin{pmatrix} -1 \ 0 \ 0 \end{pmatrix}
$$
2. 计算类内散度矩阵 $S_w$
类内散度矩阵公式：
$$S_w = S_1 + S_2,\quad S_i = \sum_{\boldsymbol{x} \in \omega_i} (\boldsymbol{x} - \boldsymbol{m}_i)(\boldsymbol{x} - \boldsymbol{m}_i)^T$$
（1）计算 $S_1$（$\omega_1$ 类的类内散度）
中心化向量：
$$
\boldsymbol{x}_{11} - \boldsymbol{m}1 = \begin{pmatrix} 0 \ -\dfrac{2}{3} \ \dfrac{1}{3} \end{pmatrix},\
\boldsymbol{x}{12} - \boldsymbol{m}1 = \begin{pmatrix} 0 \ \dfrac{1}{3} \ -\dfrac{2}{3} \end{pmatrix},\
\boldsymbol{x}{13} - \boldsymbol{m}_1 = \begin{pmatrix} 0 \ \dfrac{1}{3} \ \dfrac{1}{3} \end{pmatrix}
$$
外积求和：
$$
S_1 = \begin{pmatrix}
0 & 0 & 0 \
0 & \dfrac{2}{3} & -\dfrac{1}{3} \
0 & -\dfrac{1}{3} & \dfrac{2}{3}
\end{pmatrix}
$$
（2）计算 $S_2$（$\omega_2$ 类的类内散度）
同理，中心化向量与 $\omega_1$ 类完全相同，因此：
$$
S_2 = S_1 = \begin{pmatrix}
0 & 0 & 0 \
0 & \dfrac{2}{3} & -\dfrac{1}{3} \
0 & -\dfrac{1}{3} & \dfrac{2}{3}
\end{pmatrix}
$$
（3）合并类内散度矩阵 $S_w$
$$
S_w = S_1 + S_2
= \begin{pmatrix}
0 & 0 & 0 \
0 & \dfrac{4}{3} & -\dfrac{2}{3} \
0 & -\dfrac{2}{3} & \dfrac{4}{3}
\end{pmatrix}
$$
3. 求解Fisher最优投影方向 $\boldsymbol{w}$
Fisher准则的目标是最大化类间散度与类内散度的比值：
$$
J(\boldsymbol{w}) = \frac{\boldsymbol{w}^T S_b \boldsymbol{w}}{\boldsymbol{w}^T S_w \boldsymbol{w}}
$$
其中类间散度：
$$S_b = (\boldsymbol{m}_1 - \boldsymbol{m}_2)(\boldsymbol{m}_1 - \boldsymbol{m}_2)^T$$
最优解理论公式：
$$\boldsymbol{w} = S_w^{-1} (\boldsymbol{m}_1 - \boldsymbol{m}_2)$$
关键分析：$S_w$ 的奇异性
观察 $S_w$，其第一行、第一列元素均为$0$，说明$S_w$ 是奇异矩阵（不可逆），原因是：
- $\omega_1$ 类所有样本的 $x_1=0$，$\omega_2$ 类所有样本的 $x_1=1$，因此类内的 $x_1$ 方差为0，导致 $S_w$ 的第一维无变化。
此时需通过Fisher准则的本质求解：
- 类间差异向量 $\boldsymbol{m}_1 - \boldsymbol{m}_2 = (-1, 0, 0)^T$，说明类间差异完全集中在 $x_1$ 方向；
- 在 $x_1$ 方向上，类内散度 $\boldsymbol{w}^T S_w \boldsymbol{w} = 0$，类间散度 $\boldsymbol{w}^T S_b \boldsymbol{w} = 1$，比值 $J(\boldsymbol{w})$ 趋于无穷大（理论最大值）。
因此，最优投影方向为：
$$
\boldsymbol{w} = (1, 0, 0)^T
$$
（方向相反的 $(-1, 0, 0)^T$ 也可，仅影响投影后符号，不影响分类结果）
4. 计算投影后均值与分类阈值
（1）投影后样本与均值
将两类样本投影到 $\boldsymbol{w} = (1, 0, 0)^T$ 方向（即取 $x_1$ 坐标）：
- $\omega_1$ 类投影：$y_{11}=0,\ y_{12}=0,\ y_{13}=0$，均值 $$\bar{Y}_1 = 0$$
- $\omega_2$ 类投影：$y_{21}=1,\ y_{22}=1,\ y_{23}=1$，均值 $$\bar{Y}_2 = 1$$
（2）分类阈值 $W_0$
阈值公式：
$$
W_0 = \frac{\bar{Y}_1 + \bar{Y}_2}{2}
$$
代入得：
$$
W_0 = \frac{0 + 1}{2} = 0.5
$$
5. 分类结果与性能分析
（1）分类规则
对于任意样本 $\boldsymbol{x}$，计算投影值：
$$y = \boldsymbol{w}^T \boldsymbol{x}$$
- 若 $$y < 0.5$$判定为 $\omega_1$ 类；
- 若 $$y > 0.5$$判定为 $\omega_2$ 类。
（2）样本验证
- $\omega_1$ 类所有样本投影值均为 $$0 < 0.5$$全部判定为 $\omega_1$，正确；
- $\omega_2$ 类所有样本投影值均为 $$1 > 0.5$$全部判定为 $\omega_2$，正确。
第四题
支持向量机（SVM）的原始优化问题（以线性可分情况为例）为：
$$
\min_{\mathbf{w}, b} \frac{1}{2}|\mathbf{w}|^2 \quad \text{s.t.} \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \ge 1,; \forall i
$$
引入拉格朗日乘子 $\alpha_i \ge 0$，构造拉格朗日函数：
$$
L(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}|\mathbf{w}|^2 - \sum_{i=1}^n \alpha_i \big[y_i(\mathbf{w}^T\mathbf{x}_i + b) - 1\big]
$$
原始问题等价于极小极大问题：$\min_{\mathbf{w}, b} \max_{\boldsymbol{\alpha} \ge 0} L(\mathbf{w}, b, \boldsymbol{\alpha})$。
1. 拉格朗日对偶优化问题
对 $\mathbf{w}$ 和 $b$ 求偏导并令其为 $0$：
$$
\frac{\partial L}{\partial \mathbf{w}} = 0 ;\Rightarrow; \mathbf{w} = \sum_{i=1}^n \alpha_i y_i \mathbf{x}i
$$
$$
\frac{\partial L}{\partial b} = 0 ;\Rightarrow; \sum{i=1}^n \alpha_i y_i = 0
$$
将上述关系代回 $L$，消去 $\mathbf{w}$ 和 $b$，得到对偶问题：
$$
\max_{\boldsymbol{\alpha}} \quad W(\boldsymbol{\alpha}) = \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T\mathbf{x}j
$$
$$
\text{s.t.} \quad \alpha_i \ge 0,; \forall i,\quad \sum{i=1}^n \alpha_i y_i = 0
$$
这就是支持向量机的拉格朗日对偶优化问题。求解出最优 $\boldsymbol{\alpha}^$ 后，即可恢复判别函数参数 $\mathbf{w}^, b^*$。
2. 对“固定 $\boldsymbol{\alpha}$ 最小化 $\mathbf{w}, b$，再固定 $\mathbf{w}, b$ 最大化 $\boldsymbol{\alpha}$”的理解
这种交替优化的视角源于拉格朗日函数的鞍点性质，本质上是在求解 $\min_{\mathbf{w}, b} \max_{\boldsymbol{\alpha} \ge 0} L$。
固定 $\boldsymbol{\alpha}$，对 $(\mathbf{w}, b)$ 求极小：
此时 $\boldsymbol{\alpha}$ 被视为常数，$L$ 是关于 $\mathbf{w}$ 的二次函数（对 $b$ 是线性的），可直接求闭式解。这一步得到的是在给定乘子下让模型尽可能满足间隔约束的最优判别函数，相当于 求解当前 $\boldsymbol{\alpha}$ 对应的原问题近似解。数学上定义了函数
$$ \theta(\boldsymbol{\alpha}) = \min_{\mathbf{w}, b} L(\mathbf{w}, b, \boldsymbol{\alpha}) $$
且该极小值正是对偶目标 $W(\boldsymbol{\alpha})$。固定 $\mathbf{w}, b$，对 $\boldsymbol{\alpha}$ 求极大：
此时 $\mathbf{w}, b$ 固定，$L$ 关于 $\boldsymbol{\alpha}$ 是线性的，最大化会倾向于让 $\alpha_i$ 对违反 $y_i(\mathbf{w}^T\mathbf{x}_i+b)-1<0$ 的样本增大，而对满足约束的样本趋于 $0$，这实际上是在 寻找当前模型下最违反 KKT 条件的样本，通过调整乘子来“惩罚”错分或间隔内的点。这一步等价于求解对偶问题的一步迭代，如采用梯度上升或 SMO 算法中固定部分变量优化另一部分。
交替进行这两步，就是从两个方向逼近 $L$ 的鞍点：
- $\min_{\mathbf{w},b}$ 使 $L$ 下降，保证模型复杂度低且拟合当前乘子强调的困难样本；
- $\max_{\boldsymbol{\alpha}\ge 0}$ 使 $L$ 上升，找出当前模型最不满意的样本并增强其影响。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 kipleyarch@gmail.com
