别背刺我/ll

Chapter 1

修正过的 A 算法

维护 $\mathrm{OPEN}, \mathrm{CLOSE}, \mathrm{NEST}, f_m$；

注意一下，只有 $\mathrm{NEST}=\varnothing$ 的时候更新 $f_m=f(\mathrm{FIRST}(\mathrm{OPEN}))$。

Chapter 2

BP 算法

$t_k$: 期望输出，$o_k$: 实际输出.

$x_{j,i}$: $j$ 的第 $i$ 个输出

$w_{j,i}$: $j$ 的第 $i$ 个权重

$$ net_j = \sum_i w_{j,i}\times x_{j,i} + b $$

输出层

$$ E_d=\frac{1}{2}\sum_{k=1}^m (t_k-o_k)^2 $$

$$ \Delta w_{j,i} = -\eta\frac{\partial E_d}{\partial w_{j,i}} $$

$$ \frac{\partial E_d}{\partial w_{j,i}}=\frac{\partial E_d}{\partial o_j} \times \frac{\partial o_j}{\partial net_j}\times \frac{\partial net_j}{\partial w_{j, i}}=-(t_j-o_j)\times [o_j(1-o_j)]\times x_{j,i} $$

令 $\delta_j=\displaystyle -\frac{\partial E_d}{\partial net_j}=(t_j-o_j)o_j(1-o_j)$, 则 $\displaystyle \frac{\partial E_d}{\partial w_{j,i}}=-\delta_j x_{j,i}$.

隐含层

同样令 $\delta_j=-\displaystyle \frac{\partial E_d}{\partial net_j}$

$$ \frac{\partial E_d}{\partial w_{j,i}}=\frac{\partial E_d}{\partial net_j}\times \frac{\partial net_j}{\partial w_{j,i}} $$

其中：

$$ -\delta_j=\frac{\partial E_d}{\partial net_j}=\sum_k \frac{\partial E_d}{\partial net_k}\times \frac{\partial net_k}{\partial net_j}\\ = \sum_k (-\delta_k)\frac{\partial net_k}{\partial o_j}\times \frac{\partial o_j}{\partial net_j}\\ =\sum_k (-\delta_k) w_{k,j}o_j(1-o_j)\\ $$

即：

$$ \delta_j = o_j(1-o_j)\sum_k \delta_k \times w_{k,j} $$

取：

$$ \Delta w_{j,i} = -\eta \frac{\partial E_d}{\partial w_{j,i}} \\ =-\eta \frac{\partial E_d}{\partial net_j}\times \frac{\partial net_j}{\partial w_{j,i}}\\ =\eta \times \delta_j\times x_{j,i} $$

注意输出层 $\delta_j=o_j(1-o_j)(t_j-o_j)$.

Chapter 3

$\alpha-\beta$ 剪枝

$\max$ 节点的下界为 $\alpha$，$\min$ 节点的上界为 $\beta$.

如果后代的 $\beta\le$ 祖先的 $\alpha$，剪枝；

如果后代的 $\alpha\ge$ 祖先的 $\beta$，剪枝；

感性理解：一个 $\max$ 节点往外吐出去的已经至少是 $\alpha$ 了，如果一个后代返回的东西至多是 $\beta\le \alpha$，就肯定逃不出这棵子树。

注意单次 $\alpha-\beta$ 剪枝只确定单步的行为。

信心上限树

$$ I_j=\bar{X_j} +\sqrt{\frac{2\ln n}{T_j(n)}} $$

注意每个节点上标注的是“使得局面到达当前节点的人”的胜率，也即“选择从父节点走向当前节点的人”的胜率 (感谢 rsx。)

Chapter 4

SVM

线性可分向量机

给定 $(x_i, y_i)$, 其中 $x_i\in \mathbb{R}^n, y_i\in \{-1, 1\}$，求一个 $w^*\in \mathbb{R}^n, b^*\in \mathbb{R}$ 来分类。

定义函数间隔：

$$ \hat{\gamma_i}=y_i(w \cdot x_i+b)\\ \hat{\gamma} = \min \gamma_i $$

几何间隔：

$$ \gamma_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})\\ \gamma=\min \gamma_i=\min \frac{\hat{\gamma_i}}{||w||} $$

要求 $\max \gamma$, 即 $\displaystyle \max_{w,b} \frac{\hat{\gamma}}{||w||}$.

其中有：$y_i(w\cdot x_i+b)\ge \hat{\gamma}$, 不妨设 $\hat{\gamma}=1$.

于是就变成了 $\displaystyle \min_{w,b} \frac{1}{2}||w||^2$, 其中：

$$ y_i(w\cdot x_i+b)\ge 1 $$

使用 Lagrange 函数：

$$ L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum \alpha_i[1-y_i(w\cdot x_i+b)] $$

其中 $\alpha_i\ge 0$. 在 $y_i(w\cdot x_i+b)\ge 1$ 满足的时候，$\displaystyle \max_{\alpha} L(w,b,\alpha)=\frac{1}{2}||w||^2$, 否则是 $\infty$.

于是转化成求：

$$ \min_{w,b} \max_{\alpha} L(w,b,\alpha) $$

KKT 条件：

$\nabla_{w,b} L(w,b,\alpha) = 0$ 的地方，$\alpha[1-y_i(w\cdot x_i+b)]=0, \alpha_i\ge 0, [1-y_i(w\cdot x_i+b)]\le 0$.

满足 KKT 条件（基本假设）的时候，有对偶：

$$ \min_{w,b} \max_{\alpha} L(w,b,\alpha)=\max_{\alpha} \min_{w,b} L(w,b,\alpha) $$

后者转化为：

$$ \max_{\alpha}\Big(-\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)+\sum_{i=1}^n \alpha_i\Big) $$

其中 $\sum_{i=1}^n \alpha_i y_i=0, \alpha_i \ge 0$.

也即为

$$ \min_{\alpha}\Big(\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)-\sum_{i=1}^n \alpha_i\Big) $$

得到一个对应的 $\alpha^*$.

反推：

$$ w^*=\sum_{i=1}^n \alpha^*_i y_i x_i\in \mathbb{R}^n\\ b^*= y_j-\sum_{i=1}^n \alpha^*_i y_i (x_i \cdot x_j) $$

其中 $\alpha^*_j\ne 0$.

其中 $\alpha_i>0$ 的 $x_i$ 就是支持向量.

线性支持向量机

限制改为：

$$ y_i(w\cdot x_i+b)\ge 1- \xi_i, \xi_i\ge 0 $$

目标变成：

$$ \min_{w,b,\xi}\Big(\frac{1}{2}||w||^2+C\sum_{i=1}^n \xi_i\Big) $$

其中 $C>0$ 是一个惩罚参数.

变成了优化:

$$ \min_{\alpha}\Big(\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)-\sum_{i=1}^n \alpha_i\Big) $$

要求 $\sum_{i=1}^n \alpha_i y_i=0, 0\le \alpha_i\red{\le C}$.

$$ w^*=\sum_{i=1}^n \alpha^*_i y_i x_i\in \mathbb{R}^n\\ b^*= y_j-\sum_{i=1}^n \alpha^*_i y_i (x_i \cdot x_j) $$

其中 $0<\alpha^*_j\red{<C}$.

• $\alpha^*_i>0$ 就是支持向量；
• $\alpha^*_i < C$ 则 $\xi_i=0$，在分割边界上；
• $\alpha^*_i=C, \xi_i=1$，在超平面上；
• $\alpha^*_i=C, \xi_i>1$，在另一边。

非线性 SVM

做一个变换 $\phi$ 使得变换之后是线性可分的。然后把 $(x_i\cdot x_j)$ 变成了 $(\phi(x_i)\cdot \phi(x_j))$.

$$ K(x,z)=\phi(x)\cdot \phi(z) $$

之后只需要适当选取 $K$，而不需要显式写出 $\phi$.

变成了优化:

$$ \min_{\alpha}\Big(\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j K(x_i,x_j)-\sum_{i=1}^n \alpha_i\Big) $$

要求 $\sum_{i=1}^n \alpha_i y_i=0, 0\le \alpha_i\red{\le C}$.

选取一个 $0<\alpha^*_j<C$，则：

$$ w^*=\sum_{i=1}^n \alpha^*_i y_i \phi(x_i)\\ b^*=y_j-\sum_{i=1}^n \alpha^*_i y_i K(x_i,x_j) $$

超平面：

$$ w^*\cdot \phi(x)+b^*=0\\ \sum_{i=1}^n \alpha^*_i y_i K(x_i,x)+b^*=0 $$

所以其实不需要知道 $\phi$.

决策树

信息熵：

$$ H(X)=-\sum_{i=1}^n p_i\log_2 p_i\\ H(Y|X)=\sum_{i=1}^n p_i H(Y|X=x_i) $$

$H$ 越大，数据越混乱。

信息增益：

$$ g(D,A) = H(D) - H(D|A) $$

越大说明分类效果越好。

ID3

输入：训练集 $D$, 特征集 $A$, $\epsilon>0$;

1. 如果 $D$ 都属于类 $C_k$, 将当前点标记为 $C_k$ 类；
2. 如果 $A=\varnothing$, 将 $D$ 中最多的类 $C_k$ 作为当前点标记；
3. 计算 $A$ 中所有特征的信息增益，选择最大的 $A_g$；
4. 如果 $g(D|A_g)< \epsilon$, 将 $D$ 中最多的类 $C_k$ 作为当前点标记；
5. 否则按照 $A_g$ 的可能值划分 $D$ 为 $D_i$, 作为当前点的子节点；
6. 如果某个 $D_i=\varnothing$, 将 $D$ 中最多的类 $C_k$ 作为当前点标记；
7. 否则对 $(D_i, A\backslash A_g)$ 递归。

C4.5

信息增益比：

$$ g_R(D,A)=\frac{g(D,A)}{H_A(D)}\\ H_A(D)=-\sum_{k=1}^n \frac{ |D_k| }{ |D| } \log_2 \frac{ |D_k| }{ |D| } $$