模式识别导论复习

Ch1 - 线性回归

LASSO 问题

LASSO 问题：Least absolute shrinkage and selection operator.

min_{w} γ \sum_{j = 1}^{n} | w_{j} | + \frac{1}{2} \sum_{i = 1}^{m} (w^{⊤} x_{i} - y_{i})^{2}

$a \to 0$ 近似一范数，

\begin{matrix} h (x) = {\begin{cases} \frac{1}{2 a} x^{2}, & | x | \leq a \\ | x | - \frac{a}{2}, & | x | > a \end{cases} \end{matrix}

$\displaystyle g(x,u)=\frac{1}{2a}(x-u)^2+|u|$ ，我们有：

min_{u} g (x, u) = h (x)

$u^*=0,u^*<0,u^*>0$ ，
$u^*>0$ $-\frac{1}{a}(x-u^*)+1=0$ $x=u^*+a>a$ $x-\frac{a}{2}$ .
$u^*=0$ $-\frac{1}{a}(x-u^*)+C=0$ $x\in[-a,a]$ $\frac{1}{2a}x^2$ .
$u^*<0$ $-\frac{1}{a}(x-u^*)-1=0$ $x=u^*-a<-a$ $-x-\frac{a}{2}$ .
并且得到
$\begin{matrix} u^{*} = S_{a} (x) ≐ {\begin{cases} x - a, & x > a \\ 0, & | x | \leq a \\ x + a, & x < - a \end{cases} \end{matrix}$
也就是，
$g (x, S_{a} (x)) = h (x)$

LASSO 问题可以写为矩阵表示的形式：

min_{w} \underset{= E (w)}{\underset{⏟}{γ | | w | |_{1} + \frac{1}{2} (X w - Y)^{⊤} (X w - Y)}}

构建：

\tilde{E} (w) = γ \sum h (w_{i}) + \frac{1}{2} (X w - Y)^{⊤} (X w - Y)

$\tilde{E}(w)$ $a\to 0$ $\tilde{E}(w)\to E(w)$ .

再构建：

E (w, u) = γ \sum g (u_{i}, w_{i}) + \frac{1}{2} (X w - Y)^{⊤} (X w - Y)

$E(w,u)\ge \tilde{E}(w)$ $E(w,u^*)=\tilde{E}(w)$ .

$E(w,u)$ 得到

E (w, u) = γ \sum_{j = 1}^{n} [\frac{1}{2 a} (w_{j} - u_{j})^{2} + | u_{j} |] + \frac{1}{2} (X w - Y)^{⊤} (X w - Y)

$k$ $u^k,w^k$ .

$k+1$ $u$ 只和第一项有关，即

{\frac{\partial E (w^{k}, u)}{\partial u} |}_{u = u^{k + 1}} = 0 \Rightarrow u^{k + 1} = S_{a} (w^{k})

$w$ 只和平方项有关，

\begin{matrix} {\frac{\partial E (w, u^{k})}{\partial u} |}_{w = w^{k + 1}} = 0 \\ \Rightarrow \frac{γ}{a} (w^{k + 1} - u^{k}) + X^{⊤} (X w^{k + 1} - Y) = 0 \\ \Rightarrow (\frac{γ}{a} + X^{⊤} X) w^{k + 1} = \frac{γ}{a} u^{k} + X^{⊤} Y \\ \Rightarrow w^{k + 1} = {(\frac{γ}{a} I + X^{⊤} X)}^{- 1} (X^{⊤} Y + \frac{γ}{a} u^{k + 1}) \end{matrix}

解释稀疏性 $a\to 0$ 时，主要是主对角线元素起作用，
$w^{k + 1} \to \frac{a}{γ} I (X^{⊤} Y + \frac{γ}{a} u^{k + 1}) = u^{k + 1}$
$u^{k+1}=S_a(w^{k})$ $0$ 靠近。

0 范数问题

零范数问题：

min_{w} γ \sum_{j = 1}^{n} | w_{j} |_{0} + \frac{1}{2} \sum_{i = 1}^{m} (w^{⊤} x_{i} - y_{i})^{2}

$L_2$ $a\to 0$ 时，近似零范数。

\begin{matrix} T (x) = {\begin{cases} \frac{1}{a^{2}} x^{2}, & | x | \leq a \\ 1, & | x | > a \end{cases} \end{matrix}

$\displaystyle g(x,u)=\frac{1}{a^2}(x-u)^2+|u|_0$ .

$u^*=0,u^*\not=0$ ，可得：
$u^*=0$ $|u|_0$ $u=0$ $C$ $\frac{2}{a^2}(x-u^*)+C=0$ $x$ 是未知数，此时
$g (x, u^{*}) = \frac{1}{a^{2}} x^{2} ≐ g_{1} (x)$
$u^*\not=0$ $\frac{2}{a^2}(x-u^*)=0$ $x=u^*$ $g(x,u^*)$ $1\doteq g_2(x)$ .
$|x|\le a$ $g_1(x)\le g_2(x)$ $|x|>a$ $g_1(x)>g_2(x)$ . 因此
$\begin{matrix} T (x) = {\begin{cases} g_{2} (x) = \frac{1}{a^{2}} x^{2} & | x | \leq a (u^{*} = 0) \\ g_{1} (x) = 1 & | x | > a (u^{*} = x) \end{cases} \end{matrix}$
结论是：
$\begin{matrix} u^{*} = H_{a} (x) ≐ {\begin{cases} x, & x > a \\ 0, & | x | \leq a \\ x, & x < - a \end{cases} \end{matrix}$

交替迭代求解思路类似，这里给出结论：

\begin{matrix} u_{i}^{k + 1} = H_{a} (w_{i}^{k}) \\ w^{k + 1} = {(\frac{2 γ}{a^{2}} I + X^{⊤} X)}^{⊤} (X^{⊤} Y + \frac{2 γ}{a^{2}} u^{k + 1}) \end{matrix}

Ch2 - 线性分类

Fisher Discrimination

正负样本中心：

\begin{matrix} \overset{―}{x_{+}} = \frac{1}{n_{+}} \sum_{i : y_{i} = 1} w^{⊤} x_{i} \\ \overset{―}{x_{-}} = \frac{1}{n_{-}} \sum_{i : y_{i} = - 1} w^{⊤} x_{i} \end{matrix}

投影后正负样本中心之间距离：

w^{⊤} (\overset{―}{x_{+}} - \overset{―}{x_{-}})

正负样本类间方差：

\begin{matrix} S_{+}^{2} = \sum_{i : y_{i} = 1} (w^{⊤} x_{i} - w^{⊤} \overset{―}{x_{+}}) \\ S_{-}^{2} = \sum_{i : y_{i} = - 1} (w^{⊤} x_{i} - w^{⊤} \overset{―}{x_{-}})^{2} \end{matrix}

使用类间方差标准化中心距离：

max_{w} \frac{(w^{⊤} (\overset{―}{x_{+}} - \overset{―}{x_{-}}))^{2}}{S_{+}^{2} + S_{-}^{2}}

使用矩阵简化：

$\Gamma_B=(\overline{x_+}-\overline{x_-})(\overline{x_+}-\overline{x_-})^\top$ .
$\Gamma_+=\sum_{i:y_i=1}(x_i-\overline{x_+})(x_i-\overline{x_+})^\top$ .
$\Gamma_-=\sum_{i:y_i=-1}(x_i-\overline{x_-})(x_i-\overline{x_-})^\top$ .

那么问题等价于：

max_{w} F (w) = \frac{w^{⊤} Γ_{B} w}{w^{⊤} (Γ_{+} + Γ_{-}) w} ≐ \frac{w^{⊤} Γ_{B} w}{w^{⊤} Γ_{I} w}

对分母做尺度的约束，

min_{w} - w^{⊤} Γ_{B} w, s . t . w^{⊤} Γ_{I} w = 1

等价于广义特征值问题：

Γ_{B} w = λ Γ_{I} w

方法一 $v=\Gamma_B^{1/2} w$ ，

\begin{matrix} Γ_{B}^{1 / 2} v = λ Γ_{I} Γ_{B}^{- 1 / 2} v \\ Γ_{B}^{1 / 2} Γ_{I}^{- 1} Γ_{B}^{1 / 2} v = λ v \end{matrix}

$\Gamma_B^{1/2}\Gamma_I^{-1}\Gamma_B^{1/2}$ 最大特征值。

方法二 展开可得：

(\overset{―}{x_{+}} - \overset{―}{x_{-}}) \underset{α}{\underset{⏟}{(\overset{―}{x_{+}} - \overset{―}{x_{-}})^{⊤} w}} = λ Γ_{I} w

$w\propto \Gamma_I^{-1}(\overline{x_+}-\overline{x_-})$ .

Logistic Regression

$w^\top x$ $(0,1)$ $\rho$ ，我们可以采用

\begin{matrix} \ln \frac{ρ}{1 - ρ} = w^{⊤} x \\ \Rightarrow ρ = \frac{1}{1 + \exp (- w^{⊤} x)} \end{matrix}

$w$ $(x,y)$ 的概率可以写为：

p (x) = ρ^{y} (1 - ρ)^{1 - y}

$(x_i,y_i)$ 的对数概率可以写为：

\begin{aligned} J (w) & = \log \prod_{i} p (x_{i}) \\ = \sum_{i} \log p (x_{i}) \\ = \sum_{i} y \log ρ + (1 - y) \log (1 - ρ) \\ = \sum_{i} y_{i} \log (ρ (w^{⊤} x_{i})) + (1 - y_{i}) \log (1 - ρ (w^{⊤} x_{i})) \\ = \sum_{i} y_{i} (\log (ρ (w^{⊤} x_{i})) - \log (1 - ρ (w^{⊤} x_{i}))) + \log (1 - ρ (w^{⊤} x_{i})) \\ ∵ \frac{ρ}{1 - ρ} = e^{w^{⊤} x_{i}}, 1 - ρ = \frac{1}{1 + e^{w^{⊤} x_{i}}} \\ = \sum_{i} y_{i} (w^{⊤} x_{i}) - \log (1 + \exp (w^{⊤} x_{i})) \end{aligned}

$J(w)$ $w$ ，可以使用梯度下降的方法。

BCE Loss

$H_p=-\sum p(x)\log p(x)$ .
$H_{pq}=-\sum p(x)\log q(x)$ .
$D_{KL}(p||q)=H_{pq}-H_p$ .
$p$ $H_p$ $q$ 是模型计算出来的结果，且只存在两个分类，转换为二分类交叉熵损失：
$L = - [y \log \hat{y} + (1 - y) \log (1 - \hat{y})]$
逻辑回归相当于对每个样本的二分类交叉熵损失求和，需要最小化这个损失和。

Ch3 - SVM

SVM 模型

最大化间隔的分类器：

\begin{matrix} max_{w, b} \frac{2}{| | w | |_{2}} . \\ s . t . y_{i} (w^{⊤} x_{i} + b) \geq 1 \end{matrix}

如果样本线性不可分，则问题不可解。

允许部分误分类的软间隔分类器：

\begin{matrix} min_{w, b} \frac{1}{2} | | w | |_{2}^{2} + C \sum_{i} ρ_{i} \\ s . t . y_{i} (w^{⊤} x_{i} + b) \geq 1 - ρ_{i} \\ ρ_{i} \geq 0 \end{matrix}

$\rho_i$ 越大，误分类的程度越大。

SVM 对偶问题

$\le0$ 的形式：

\begin{matrix} min_{w, b} \frac{1}{2} | | w | |_{2}^{2} + C \sum_{i} ρ_{i} \\ s . t . 1 - ρ_{i} - y_{i} (w^{⊤} x_{i} + b) \leq 0 \\ - ρ_{i} \leq 0 \end{matrix}

$\alpha_i,\beta_i$ ，写出拉格朗日项：

\begin{matrix} L (w, b, ρ; α, β) = \frac{1}{2} | | w | |_{2}^{2} + C \sum_{i} ρ_{i} \\ + \sum_{i} α_{i} (1 - ρ_{i} - y_{i} (w^{⊤} x_{i} + b)) - \sum_{i} ρ_{i} β_{i} \end{matrix}

写出 KKT 条件，包含四个部分：

Stationarity Condition:
$\begin{matrix} {\frac{\partial L (w)}{\partial w} |}_{w = w^{*}} = w - \sum_{i} α_{i} y_{i} x_{i} = 0 \\ {\frac{\partial L (b)}{\partial b} |}_{b = b^{*}} = - \sum_{i} α_{i} y_{i} = 0 \\ {\frac{\partial L (ρ)}{\partial ρ} |}_{ρ = ρ^{*}} = C - α_{i} - β_{i} = 0 \end{matrix}$
Primal Feasibility Condition:
${\begin{cases} 1 - ρ_{i} - y_{i} (w^{⊤} x_{i} + b) \leq 0 \\ - ρ_{i} \leq 0 \end{cases}$
Dual Feasibility Condition:
$α_{i} \geq 0, β_{i} \geq 0$
$C-\alpha_i-\beta_i=0$ $0\le \alpha_i\le C$ .
Complementary Slackness Condition:
${\begin{cases} α_{i} (1 - ρ_{i} - y_{i} (w^{⊤} x_{i} + b)) = 0 \\ - β_{i} ρ_{i} = 0 \end{cases}$

重组拉格朗日函数，并且代入 KKT 条件可得：

\begin{matrix} L = \frac{1}{2} | | w | |_{2}^{2} + \underset{代 入 K K T 条 件 = 0}{\underset{⏟}{\sum_{i} ρ_{i} (C - α_{i} - β_{i})}} \\ + \sum_{i} α_{i} - \underset{= w^{⊤} w = | | w | |^{2}}{\underset{⏟}{\sum_{i} α_{i} y_{i} w^{⊤} x_{i}}} - \underset{代 入 K K T 条 件 = 0}{\underset{⏟}{b \sum α_{i} y_{i}}} \end{matrix}

L = - \frac{1}{2} | | w | |^{2} + \sum_{i} α_{i}

其中，

\begin{aligned} \frac{1}{2} | | w | |^{2} & = \frac{1}{2} \sum_{i} y_{i} α_{i} x_{i}^{⊤} \sum_{j} y_{j} α_{j} x_{j} \\ = \frac{1}{2} \sum_{i} \sum_{j} α_{i} y_{i} x_{i}^{⊤} x_{j} y_{j} α_{j} \end{aligned}

因此对偶问题可以表示为：

\begin{matrix} max_{α} - \frac{1}{2} \sum_{i} \sum_{j} α_{i} y_{i} x_{i}^{⊤} x_{j} y_{j} α_{j} + \sum_{i} α_{i} \\ s . t . \sum_{i} α_{i} y_{i} = 0, 0 \leq α_{i} \leq C \end{matrix}

通过对偶问题得到原问题参数

$w,b$ 的形式：

w = \sum_{i} y_{i} α_{i} x_{i} = \sum_{i, α_{i} \neq 0} y_{i} α_{i} x_{i}

$0\le \alpha_i \le C,\alpha_i+\beta_i=C$ 以及互补松弛条件：

{\begin{cases} (1 - ρ_{i} - y_{i} (w^{⊤} x_{i} + b)) α_{i} = 0 \\ ρ_{i} β_{i} = 0 \end{cases}

$\boldsymbol{\alpha_i=0}$ 时 $\beta_i=C$ $\rho_i=0$ ，再代入

1 - ρ_{i} - y_{i} (w^{⊤} x_{i} + b) \leq 0 \Rightarrow y_{i} (w^{⊤} x_{i} + b) \geq 1

$x_i$ $y_i=1$ $y_i=-1$ $4$ 区。

$\boldsymbol{\alpha_i >0}$ 时 $(1-\rho_i - y_i(w^\top x_i+b))=0$ $x_i$ 成为支持向量：

$\boldsymbol{0<\alpha_i<C}$ 时 $\beta_i>0$ $\rho_i=0$ .
$y_i(w^\top x_i+b)=1-\rho_i=1$ $x_i$ $y_i=1$ $y_i=-1$ 时处于 3,4 区的交界处。
$\boldsymbol{\alpha_i=C}$ 时 $\beta_i=C-\alpha_i=0$ $\rho_i\ge0$ .
$y_i(w^\top x_i+b)\le 1$ ，样本可能分类错误。

$\alpha_i\not=0(0<\alpha_i\le C)$ $x_i$ 属于 支持向量 (SV) $0<\alpha_i<C$ 的 $y_i(w^\top x_i+b)=1$ $y_i\in \{1,-1\}$ $w^\top x_i+b=y_i$ ，

\begin{aligned} b_{i} & = y_{i} - w^{⊤} x_{i} \\ = y_{i} - \sum_{j : α_{j} \neq 0} y_{j} α_{j} x_{j}^{⊤} x_{i} \\ = y_{i} - \sum_{x_{j} \in SV} y_{j} α_{j} x_{j}^{⊤} x_{i} \end{aligned}

$b$ $b_i$ 取平均：

\begin{aligned} f (x) & = w^{⊤} x + b \\ = \sum_{x_{i} \in SV} y_{i} α_{i} x_{i}^{⊤} x + \frac{1}{n} \sum_{k \in {k | 0 < α_{k} < C}} (y_{k} - \sum_{x_{j} \in SV} y_{j} α_{j} x_{j}^{⊤} x_{k}) \end{aligned}

$n$ $0<\alpha_i<C$ 的向量的个数。

Kernel Trick

$x\to \phi(x)$ $n$ $d\gg n$ .

SVM 分隔函数和对偶问题都可以用内积的形式表示：

f (x) = \sum_{x_{i} \in SV} y_{i} α_{i} ϕ^{⊤} (x_{i}) ϕ (x) + b

\begin{matrix} min_{α} \sum_{i} \sum_{j} α_{i} y_{i} ϕ (x_{i})^{⊤} ϕ (x_{j}) y_{j} α_{j} - \sum_{i} α_{i} \\ s . t . \sum_{i} α_{i} y_{i} = 0, 0 \leq α_{i} \leq C \end{matrix}

$K(u,v)=\phi(u)^\top \phi(v)$ .

$K(u,v)=(u^\top v+1)^2$ ，可以看成：

\begin{aligned} K (u, v) & = (u^{⊤} v + 1)^{2} = (u_{1} v_{1} + u_{2} v_{2} + 1)^{2} \\ = u_{1}^{2} v_{1}^{2} + u_{2}^{2} v_{2}^{2} + 1 + 2 u_{1} v_{1} u_{2} v_{2} + 2 u_{1} v_{1} + 2 u_{2} v_{2} \\ = \underset{ϕ (u)^{⊤}}{\underset{⏟}{(\begin{array}{c} u_{1}^{2} & u_{2}^{2} & 1 & \sqrt{2} u_{1} u_{2} & \sqrt{2} u_{1} & \sqrt{2} u_{2} \end{array})}} \\ \underset{ϕ (v)}{\underset{⏟}{{(\begin{array}{c} v_{1}^{2} & v_{2}^{2} & 1 & \sqrt{2} v_{1} v_{2} & \sqrt{2} v_{1} & \sqrt{2} v_{2} \end{array})}^{⊤}}} \\ = ϕ (u)^{⊤} ϕ (v) \end{aligned}

从二维映射到六维。

高斯核函数推导

RBF(Radial Basis Function) Kernel / Gaussian Kernel

K (u, v) = \exp (- \frac{| | u - v | |_{2}^{2}}{2 σ^{2}})

\begin{aligned} K (u, v) & = \exp (- \frac{| | u - v | |_{2}^{2}}{2 σ^{2}}) \\ = \exp (- \frac{| | u | |_{2}^{2}}{2 σ^{2}}) \exp (\frac{u v}{σ^{2}}) \exp (- \frac{| | v | |_{2}^{2}}{2 σ^{2}}) \end{aligned}

$\exp\left(\frac{uv}{\sigma^2}\right)$ .

\begin{aligned} \exp (\frac{u v}{σ^{2}}) & = \sum_{n = 0}^{\infty} \frac{1}{n!} {(\frac{u v}{σ^{2}})}^{n} \\ = 1 + \sum_{n = 1}^{\infty} \frac{1}{\sqrt{n!}} \frac{u^{n}}{σ^{n}} \frac{1}{\sqrt{n!}} \frac{v^{n}}{σ^{n}} \\ = \underset{\tilde{ϕ} (u)^{⊤}}{\underset{⏟}{(\begin{array}{c} 1 & \frac{u}{σ} & \frac{1}{\sqrt{2!}} {(\frac{u}{σ})}^{2} & \frac{1}{\sqrt{3!}} {(\frac{u}{σ})}^{3} & \dots & \frac{1}{\sqrt{n!}} {(\frac{u}{σ})}^{n} & \dots \end{array})}} \\ \underset{\tilde{ϕ} (v)}{\underset{⏟}{{(\begin{array}{c} 1 & \frac{v}{σ} & \frac{1}{\sqrt{2!}} {(\frac{v}{σ})}^{2} & \frac{1}{\sqrt{3!}} {(\frac{v}{σ})}^{3} & \dots & \frac{1}{\sqrt{n!}} {(\frac{v}{σ})}^{n} & \dots \end{array})}^{⊤}}} \\ = \tilde{ϕ} (u)^{⊤} \tilde{ϕ} (v) \end{aligned}

则：

ϕ (u) ≐ \exp (- \frac{| | u | |_{2}^{2}}{2 σ^{2}}) \tilde{ϕ} (u)

Ch4 - 无监督学习

PCA

$n$ $m$ $X$ $n\times m$ 的矩阵，PCA 问题

max_{w^{⊤} w = 1} w^{⊤} C w C = \frac{1}{m - 1} X X^{⊤}

$w^\top w=1$ 对投影向量做出了尺度归一化的要求；
$C$ $n\times n$ $m$ 无关。
$X$ $\overline{X}=\overline{Y}=0$ .

对 PCA 进行理论解释，因为样本方差的无偏估计为：

\begin{aligned} S^{2} & = \frac{1}{m - 1} cov (Y) \\ = \frac{1}{m - 1} (E {Y^{⊤} Y} - {\overset{―}{Y}}^{2}) \\ = \frac{1}{m - 1} w^{⊤} X X^{⊤} w \end{aligned}

$w^\top X$ $C$ $w$ .

PCA 过程

$x_i$ $n$ $k$ 维，要求每维之间不相关也就是协方差为零。

$x_i-\overline{x}$ ;
$\displaystyle C=\frac{1}{m-1} XX^\top \in \R^{n\times n}$ .
$Cw=\lambda w$ $\lambda_1>\lambda_2>\cdots>\lambda_n$ .
$k$ 特征值和特征向量（模长为一）：
$\begin{matrix} λ_{1}, λ_{2}, \dots, λ_{k} \\ w_{1}, w_{2}, \dots, w_{k} \end{matrix}$
$w_i^\top w_j\not=0 \iff i=j$ .
$y_i=[w_1^\top x_i,w_2^\top x_i,\cdots,w_k^\top x_i]$ .
$\operatorname{cov}(w_i^\top X,w_i^\top X)=\lambda_i$ $\operatorname{cov}(w_i^\top X,w_j^\top X)=0$ .
$\operatorname{cov}(Y)$ $\operatorname{diag}\{\lambda_i\}$ 。

转录组PCA

CCA

$x_a,x_b$ 是对同一个对象的不同观测（可能维度不同）， $x_a,x_b$ $y_a,y_b$ 相关系数尽量大。

$x_a\in \R^m,x_b \in \R^{n}$ $y_a=w_a^\top x_a,y_b=w_b^\top x_b$ $y_a,y_b\in \R$ .

计算其相关系数：

\begin{aligned} ρ & = \frac{cov (y_{a}, y_{b})}{\sqrt{cov (y_{a})} \sqrt{cov (y_{b})}} \\ = \frac{E {y_{a} y_{b}}}{\sqrt{E {y_{a}^{2}} E {y_{b}^{2}}}} \\ = \frac{E {w_{a}^{⊤} x_{a} w_{b}^{⊤} x_{b}}}{\sqrt{E {w_{a}^{⊤} x_{a} w_{a}^{⊤} x_{a}} E {w_{b}^{⊤} x_{b} w_{b}^{⊤} x_{b}}}} \end{aligned}

$C_{ab}=\mathbb E(x_ax_b^\top),C_{aa}=\mathbb E(x_ax_a^\top),C_{bb}=\mathbb E(x_bx_b^\top)$ .

优化问题变为：

max_{w_{a}, w_{b}} \frac{w_{a}^{⊤} C_{a b} w_{b}}{\sqrt{w_{a}^{⊤} C_{a a} w_{a}} \sqrt{w_{b}^{⊤} C_{b b} w_{b}}}

做尺度一致性的变化（类似于 Fisher Discriminant 的做法）：

\begin{matrix} max w_{a}^{⊤} C_{a b} w_{b} \\ s . t . w_{a}^{⊤} C_{a a} w_{a} = 1, w_{b}^{⊤} C_{b b} w_{b} = 1 \end{matrix}

写出拉格朗日项：

\begin{matrix} L (w_{a}, w_{b}; λ_{a}, λ_{b}) \\ = w_{a}^{⊤} C_{a b} w_{b} - \frac{λ_{a}}{2} (w_{a}^{⊤} C_{a a} w_{a} - 1) - \frac{λ_{b}}{2} (w_{b}^{⊤} C_{b b} w_{b} - 1) \end{matrix}

$w_a$ $w_b$ 分别求导：

{\begin{cases} \frac{\partial L}{\partial w_{a}} = C_{a b} w_{b} - λ_{a} C_{a a} w_{a} = 0 \\ \frac{\partial L}{\partial w_{b}} = C_{b a} w_{a} - λ_{b} C_{b b} w_{b} = 0 \end{cases}

$\lambda_a=\lambda_b$ ，也就是：

{\begin{cases} C_{a b} w_{b} = λ C_{a a} w_{a} \\ C_{b a} w_{a} = λ C_{b b} w_{b} \end{cases}

因此，

\begin{matrix} w_{b} = λ C_{a b}^{- 1} C_{a a} w_{a} \\ C_{b a} w_{a} = λ^{2} C_{b b} C_{a b}^{- 1} C_{a a} w_{a} \\ w_{a} = λ^{2} C_{b a}^{- 1} C_{b b} C_{a b}^{- 1} C_{a a} w_{a} \\ C_{a a}^{- 1} C_{a b} C_{b b}^{- 1} C_{b a} w_{a} = λ^{2} w_{a} \end{matrix}

$C_{aa}^{-1}C_{ab} C_{bb}^{-1} C_{ba}$ $w_a$ .

EM 算法

高斯分布表达式：

N (x; μ, Σ) = \frac{1}{\sqrt{(2 π)^{d} det (Σ)}} \exp [- \frac{1}{2} (x - μ)^{⊤} Σ^{- 1} (x - μ)]

高斯混合模型：

\begin{matrix} p (x | Θ) = \sum_{k} α_{k} N (x; μ_{k}, σ_{k}) \\ {\begin{cases} α_{k} > 0 \\ \sum_{k} α_{k} = 1 \end{cases} \end{matrix}

使用极大似然估计求解：

\begin{matrix} Θ = \arg max_{Θ} \underset{L (x | Θ)}{\underset{⏟}{\ln (\prod_{i} p (x_{i} | Θ))}} \\ L (x | Θ) = \sum_{i} \ln (\sum_{k} α_{k} N (x_{i} | μ_{k}, σ_{k})) \end{matrix}

$\ln$ 里面有求和符号，不好直接做，需要利用琴生不等式化简，具体推导过程省略，我们可以直观地来理解 EM 迭代求解的过程：

$\Theta^t$ 的值；
Expectation Step $\Theta^t$ $\omega_{i,k}^t$ .
$ω_{i, k}^{t} = \frac{α_{k}^{t} N (x_{i}^{t} | μ_{k}^{t}, σ_{k}^{t})}{\sum_{k} α_{k}^{t} N (x_{i} | μ_{k}^{t}, σ_{k}^{t})}$
$\alpha_k^t$ $k$ 类高斯分布的先验概率。
$\omega_{i,k}^t$ : $i$ $k$ 个高斯分布的概率。
$\sum_{k=1}^K \omega_{i,k}^t=1$ ，也就是一个样本一定属于某一类。
Maximization Step
1. $\alpha_k$ 的更新：
  $α_{k}^{t + 1} = \frac{\sum_{i} ω_{i, k}^{t}}{N}$
  可以理解为频率估计概率。
2. $\mu_k$ $\sigma_k^2$ 的更新：
  $μ_{k}^{t + 1} = \frac{\sum_{i} ω_{i, k}^{t} x_{i}}{\sum_{i} ω_{i, k}^{t}} (σ_{k}^{2})^{t + 1} = \frac{\sum_{i} ω_{i, k}^{t} (x_{i} - μ_{k}^{t + 1})^{2}}{\sum_{i} ω_{i, k}^{t}}$
  可以理解为加权求和。
  注：对于高维问题只有一点不同，这里的乘法改成协方差矩阵。
  $(Σ_{k})^{t + 1} = \frac{\sum_{i} ω_{i, k} (x_{i} - μ_{k}^{t + 1}) (x_{i} - μ_{k}^{t + 1})^{⊤}}{\sum_{i} ω_{i, k}}$

初始化方法

$\alpha_k$ $=1/N$ ；
$\mu_k$ 使用聚类算法选择；
$\sigma_k^2$ 使用聚类簇方差。

Ch5 - 集成学习

AdaBoost

AdaBoost 流程：给定二分类的训练数据集，

$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_{N},y_{N})\}$ $x_i \in \mathcal X\subseteq \R^n,y_i \in \mathcal Y=\{-1,1\}$ .
$G(x)$ .

初始化训练数据的权值分布，代表训练数据的重要程度：
$D_{1} = {w_{1 i}}, w_{1 i} = \frac{1}{N} .$
$m=1,2\cdots,M$ （迭代序数）
1. $G_{m}(x):\mathcal X \to \{-1,+1\}$ $G_{m}(x)$ 在训练数据集上的分类误差率；
  $e_{m} = P (G_{m} (x_{i}) \neq y_{i}) = \sum_{i = 1}^{N} w_{m i} I (G_{m} (x_{i}) \neq y_{i})$
  $I(G_{m}(x_i)\not=y_i)$ $w_{mi}$ 做加权求和。
  $G_m(x)$ .
2. $G_{m}(x)$ 的系数；
  $α_{m} = \frac{1}{2} \log \frac{1 - e_{m}}{e_{m}}$
3. 更新训练数据集的权值分布。
  $\begin{matrix} w_{m + 1, i} = {\begin{cases} \frac{w_{m i}}{Z_{m}} e^{- α_{m}}, & G_{m} (x_{i}) = y_{i} \\ \frac{w_{m i}}{Z_{m}} e^{α_{m}}, & G_{m} (x_{i}) \neq y_{i} \end{cases} \end{matrix}$ $Z_{m} = \sum_{i = 1}^{N} w_{m i} \exp (- α_{m} y_{i} G_{m} (x_{i}))$
  分类正确分类错误
  $\alpha_m>0$ 权值降低权值提升
  $\alpha_m<0$ 权值提升权值降低
4. $G(x)=\operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right)$ .

	分类正确	分类错误
$\alpha_m>0$	权值降低	权值提升
$\alpha_m<0$	权值提升	权值降低

Ch6 - 决策规则

贝叶斯决策

基础为贝叶斯公式：

p (ω | x) = \frac{p (x | ω) p (ω)}{p (x)}

$p(\omega)$ $p(x|\omega)$ $x$ $\omega$ 类中的概率分布。

$x$ $\omega_1$ $\omega_2$ 类，即计算：

p (ω_{1} | x) ≶ p (ω_{2} | x)

p (x | ω_{1}) p (ω_{1}) ≶ p (x | ω_{2}) p (ω_{2})

$d_i(x)=p(x|\omega_i) p(\omega_i)$ $k$ ：

k = \arg max_{k} d_{k} (x)

等价于最大化分类正确率。

$p(x|\omega_1)p(\omega_1)=p(x|\omega_2)p(\omega_2)$ ，考试题会问高斯分布下的决策面是什么样子的。

最小风险贝叶斯决策

$\omega_1$ $\omega_2$ $L$ :

\begin{matrix} L = (\begin{matrix} 0 & 1 \\ 5 & 0 \end{matrix}) \end{matrix}

$L_{11},L_{22}$ $L_{12}=1,L_{21}=5$ 表示把有病的判断为没病的损失更大。

$\omega_j$ $x$ 定义决策函数为：

r_{j} (x) = \sum_{i = 1}^{M} L_{i j} p (ω_{i} | x) = \sum_{i = 1}^{M} L_{i j} \frac{p (x | ω_{i}) p (ω_{i})}{p (x)}

最小化分类失误：

k = \arg min_{k} r_{k} (x)

$L_{ij}=1-\delta_{ij}$ ，转换为普通的贝叶斯决策问题。

r_{j} (x) = \sum_{i = 1}^{M} p (ω_{i} | x) - p (x | ω_{j}) p (ω_{j}) = p (x) - d_{j} (x)

$x$ $p(x)$ $r_j(x)$ $d_j(x)$ 最大。

Neyman-Pearson 决策

$\varepsilon_1$ $\omega_1$ $\omega_2$ $\varepsilon_2$ $\omega_2$ $\omega_1$ 类。

$\varepsilon_2=\varepsilon_0$ $\varepsilon_1$ 最小的决策。

举例子叮咚鸡：

	$\omega_1$	$\omega_2$
阴性		$\varepsilon_2=\varepsilon_0$
阳性	$\varepsilon_1$

$99.99\%$ $\varepsilon_1$ 希望控制最小，这就是 NP 决策的问题。我们再用图形直观地说明这个问题：

使用抗体浓度作为是否为阳性的依据，两类病人的抗体浓度分别服从正态分布。

$t$ $\varepsilon_2=\varepsilon_0$ $\varepsilon_1$ $t$ .

求解 NP 决策问题，我们可以使用拉格朗日法：

L = ε_{1} + λ (ε_{2} - ε_{0})

\begin{aligned} L = & \int_{R_{2}} p (x | ω_{1}) d x + λ \int_{R_{1}} p (x | ω_{2}) d x - λ ε_{0} \\ = & 1 - \int_{R_{1}} p (x | ω_{1}) d x + λ \int_{R_{1}} p (x | ω_{2}) d x - λ ε_{0} \\ = & (1 - λ ε_{0}) + \int_{R_{1}} [λ p (x | ω_{2}) - p (x | ω_{1})] d x \end{aligned}

代入拉格朗日极值条件：

\begin{aligned} \frac{\partial L}{\partial t} = & λ p (t | ω_{2}) - p (t | ω_{1}) = 0 \end{aligned}

$x=t$ $\displaystyle \frac{p(x|\omega_2)}{p(x|\omega_1)}=\lambda$ .

$x<t$ $\displaystyle \frac{p(x|\omega_2)}{p(x|\omega_1)}<\lambda$ $\omega_1$ .
$x>t$ $\displaystyle \frac{p(x|\omega_2)}{p(x|\omega_1)}>\lambda$ $\omega_2$ .

$\lambda$ $\varepsilon_2=\varepsilon_0=\displaystyle \int_{R_1} p(x|\omega_2)\mathrm d x$ $\lambda$ .