Boosting是集成学习中的典型代表之一，与随机森林的不同在于：Boosting中的个体学习器之间有着强依赖、必须串行生成。Boosting族最典型的算法是AdaBoost。AdaBoost每轮迭代尝试调整训练数据的分布以使得下一轮的基学习器能够修正现有学习器的一些错误。Boosting算法从“偏差-方差”的角度看更加专注于降低偏差。

---

AdaBoost

---

指数损失函数

AdaBoost可以理解成基学习器的叠加，即

$$\begin{aligned} H(x)=\sum_{t=1}^T \alpha_th_t(x) \end{aligned}$$

来最小化损失函数

$$\begin{aligned} l_{exp}(H|\mathcal{D})&=E_{x\sim D}[e^{-f(x)H(x)}] \\ &= E_{x\sim D}[e^{-H(x)}P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x)] \end{aligned}$$

其中$\mathcal{D}$表示数据集$D$的分布，也就是每个样本出现的概率。要选取最佳的$H(x)$使得损失函数$l$最小。这里假设原始数据集的标签$y_i\in \lbrace -1,+1 \rbrace$，$f(x)$是真实函数。自然地考虑$l_{exp}(H|\mathcal{D})$对$H(x)$求偏导数并且设置为0

$$\begin{aligned} \frac{\partial l_{exp}(H|\mathcal{D})}{\partial H(x)} &= -e^{-H(x)}P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x) = 0 \\ H(x) &= \frac{1}{2} ln \frac{P(f(x)=1|x)}{P(f(x)=-1|x)} \end{aligned}$$

其中，$H(x)$与真实函数输出一致，那么$-f(x)H(x)$为-1；反之$-f(x)H(x)=1$，所以最小化上述损失函数的意义就是希望$H(x)$与真实函数$f(x)$输出尽量一致。最后，考虑到问题本质，$sign \left( \frac{1}{2} ln \frac {P(f(x)=1|x)} {P(f(x)=-1|x)}\right) $还需要

$$sign(H(x)) = sign \left( \frac{1}{2} ln \frac {P(f(x)=1|x)} {P(f(x)=-1|x)} \right) = \begin{cases} 1 & {P(f(x)=1|x) \ge P(f(x)=-1|x)} \\ -1 & {P(f(x)=1|x) < P(f(x)=-1|x)} \end{cases}$$

表明$sign(H(x))$达到了贝叶斯最优错误率，也就是：若指数损失函数最小化，那么分类错误率最小化。

---

权重更新

AdaBoost中，第一个分类器$h_1$通过直接将基学习算法用于初始数据分布$\mathcal{D}$而得，此后迭代地生成$h_t,\alpha_t$。当基分类器$h_t$基于分布$\mathcal{D}_t$产生后，$h_t$对应的权重$\alpha_t$应该使得$\alpha_th_t$最小化指数损失函数

$$\begin{aligned} l_{exp}(\alpha_th_t|\mathcal{D}_t) &= E_{x\sim \mathcal{D}_t} \left[ e^{-f(x)\alpha_th_t(x)} \right] \\ &= E_{x\sim \mathcal{D}_t} \left[ e^{-\alpha_t}I(f(x)=h_t(x)) + e^{\alpha_t}I(f(x)\neq h_t(x)) \right] \\ &= e^{-\alpha_t}P_{x\sim \mathcal{D}_t}(f(x)=h_t(x)) + e^{\alpha_t}P_{x\sim \mathcal{D}_t}(f(x)\neq h_t(x)) \\ &= e^{-\alpha_t}(1-\epsilon_t) + e^{\alpha_t}\epsilon_t \end{aligned}$$

其中，$\epsilon_t=P_{x\sim \mathcal{D}_t}(f(x)\neq h_t(x))$。上式对$\alpha_t$求导并使之为0可得

$$\begin{aligned} \alpha_t=\frac{1}{2} ln\left( \frac{1-\epsilon_t}{\epsilon_t} \right) \end{aligned}$$

---

样本分布调整

获取$H_{t-1}$之后将样本分布进行调整，使下一轮的基学习器$h_t$能纠正$H_{t-1}$的错误，依旧采用最小化指数损失函数的思想，有

$$\begin{aligned} l_{exp}(H_{t-1}+h_t | \mathcal{D}) &= E_{x\sim \mathcal{D}} [e^{ -f(x) ( H_{t-1}(x)+h_t(x) ) }] \\ &= E_{x\sim \mathcal{D}} [ e^{-f(x)H_{t-1}} e^{-f(x)h_t(x)} ] \\ \end{aligned}$$

对上式中的$e^{-f(x)h_t(x)}$做二阶泰勒展开，近似为

$$\begin{aligned} l_{exp}(H_{t-1}+h_t|\mathcal{D}) &\simeq E_{x\sim \mathcal{D}}\left[e^{-f(x)H_{t-1}(x)} \left( 1-f(x)h_t(x)+\frac{f(x)^2h_t(x)^2}{2} \right) \right] \\ &= E_{x\sim \mathcal{D}}\left[e^{-f(x)H_{t-1}(x)} \left( \frac{3}{2}-f(x)h_t(x) \right)\right] \\ \end{aligned}$$

因为$\frac{3}{2}-f(x)h_t(x)>0$并且$f(x)H_{t-1}(x)$也是确定的值，所以最小化上式也就是等价于下式，也可以做一点变化变体

$$\begin{aligned} &\to \arg\max_{h} E_{x\sim \mathcal{D}}\left[e^{-f(x)H_{t-1}(x)} f(x)h(x)\right] \\ &\to \arg\max_{h} E_{x\sim \mathcal{D}}\left[\frac{e^{-f(x)H_{t-1}(x)}} {E_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t-1}(x) } \right] } f(x)h(x)\right] \end{aligned}$$

因为$E_{x\sim \mathcal{D}}e^{-f(x)H_{t-1}(x)}$是一个常数，令$\mathcal{D}_t$表示一个分布

$$\begin{aligned} D_t(x)=\mathcal{D}(x) \frac { e^{-f(x)H_{t-1}(x)} } { E_{x\sim \mathcal{D}} \left[ e^{ -f(x)H_{t-1}(x) } \right] } \end{aligned}$$

根据数学期望的定义，这等价于令

$$\begin{aligned} h_t(x) &= \arg\max_{h} E_{x\sim \mathcal{D}}\left[\frac{e^{-f(x)H_{t-1}(x)}} {E_{x\sim \mathcal{D}} [e^{-f(x)H_{t-1}(x)}]} f(x)h(x)\right] \\ &= \arg\max_{h} E_{x\sim \mathcal{D}_t} [f(x)h(x)] \end{aligned}$$

由于$f(x),h(x)$都只能取$\lbrace -1,1 \rbrace$，所以上式中的优化问题也可以变成

$$\begin{aligned} h_t(x) = \arg\min_{h} E_{x\sim \mathcal{D}_t} [I(f(x) \neq h(x))] \end{aligned}$$

所以理想的$h_t$将在分布$\mathcal{D}_t$下最小化分类误差，因此弱分类器将基于$\mathcal{D}_t$来训练，且针对$\mathcal{D}_t$的分类误差应该不小于0.5（二分类至少要比猜的强）。根据上面的推导，分布之间的关系应该是

$$\begin{aligned} \mathcal{D}_{t+1}(x) &= \mathcal{D}(x) \frac{e^{-f(x)H_{t-1}(x)}} { E_{x\sim \mathcal{D}} [ e^{ -f(x) H_{t-1}(x) } ] } \\ &= \mathcal{D}(x) \frac{ e^{-f(x)H_{t-1}(x)} e^{-f(x) \alpha_t h_t(x)} } {E_{x\sim \mathcal{D}} [ e^{ -f(x) H_{t-1}(x) } ] } \\ &= \mathcal{D}_{t}(x) e^{-f(x) \alpha_t h_t(x)} \frac{E_{x\sim \mathcal{D}} [ e^{-f(x)H_{t-1}(x)} ]} {E_{x\sim \mathcal{D}} [e^{-f(x)H_{t}(x)}]} \end{aligned}$$

至此，AdaBoost算法流程介绍完毕，下面是其算法描述

---

输入：训练集$D=\lbrace (x_1,y_1),…,(x_m,y_m) \rbrace$；基学习算法$\gamma$；训练轮数$T$

---

1. $\mathcal{D}_{1}(x)=\frac{1}{m}$. //初始为均匀分布
2. $for\;t=1,…,T$
3. $h_t=\gamma(D,\mathcal{D}_{t})$.
4. $\epsilon_t=P_{x\sim \mathcal{D}_{t} }(h_t(x)\neq f(x))$.
5. $if\;\epsilon_t>0.5\;then\;break\;$. // 错误率大于0.5的不要，至少比随机猜测好
6. $\alpha_t=\frac{1}{2}ln \frac {1-\epsilon_t}{\epsilon_t}$. //权重更新
7. $\mathcal{D}_{t+1}=\mathcal{D}_{t} \frac{exp(-\alpha_t f(x) h_t(x))} {Z_t}$. //分布调整

---

输出：$H(x)=sign\left( \sum_{t=1}^T \alpha_t h_t(x) \right)$

---

由算法描述的第三行可以看出，基学习算法需要能够对特定的数据分布进行学习，可以通过两种方法实现：

• 重赋权法：每一轮训练过程中，根据样本分布为每个样本重新赋予一个权重。也可以是在计算误差率的时候，为每个样本对应的项加上权重。
• 重采样法：每一轮训练过程中，根据样本分布进行重采样，用采样的样本集训练数据。（特别用于样本无法接受权值的基算法场景，此方法还可以在基学习器错误率大于0.5时不用退出，创新采样开始）

Boosting Tree

• 提升树被认为是统计学习中性能最好的方法之一
• 与RF类似，提升树也可以通过线性叠加基学习器的方法获得准确率的提升
• 基学习器为二叉树，分为分类、回归两种

提升树

提升树的模型可以表示为$f_M(x)=\sum_{m=1}^MT(x;\theta_m)$其中，$M$为树的个数，$T(x;\theta_m)$表示决策树，$\theta_m$为决策树的参数。

步骤：首先确定初始提升树$f_0(x)=0$，第$m$步的模型是$f_m(x)=f_{m-1}(x)+T(x;\theta_m)$，通过经验风险最小化确定参数$\theta_m$为

$$\begin{aligned} \theta_m=\arg\min_{\theta_m^{\*}} \sum_{i=1}^N L \left (y_i,f_{m-1}(x_i)+T(x_i;\theta_m^{\*}) \right) \end{aligned}$$

即使输入数据与输出数据之间的关系很复杂，树的线性组合也可以很好地拟合训练数据。

在回归问题中，考虑使用平方误差损失函数，所以损失变为

$$\begin{aligned} &L \left(y,f_{m-1}(x)+T(x;\theta_m^{\*})\right) \\ &= \left(y-f_{m-1}(x)-T(x;\theta_m^{\*})\right)^2 \\ &= \left(r-T(x;\theta_m^{\*})\right)^2 \end{aligned}$$

其中$r=y-f_{m-1}(x)$是当前模型拟合数据的残差，所以算法就是拟合当前模型的残差，描述如下：

---

输入：训练数据集$D$

---

1. 初始化$f_0(x)=0$，迭代次数$M$
2. 对$m=1,…,M$
   • 计算每个样本的残差$r_{mi}=y_i-f_{m-1}(x_i)$
   • 拟合残差$r_m$得到一个回归树$T(x;\theta_m)$
   • 计算$f_m(x)=f_{m-1}(x)+T(x;\theta_m)$
3. 得到回归提升树$f_M(x)=\sum_{m=1}^MT(x;\theta_m)$

---

输出：$F_M(x)$

---

梯度提升

• 损失函数是平方误差、指数损失函数时每一步优化比较明显；但一般损失函数就不那么容易了
• 使用最速下降的近似方法
• 利用损失函数的负梯度在当前模型的值残差的近似值作为提升回归树的残差近似值

下面是梯度提升回归树算法

---

输入：数据集$D$，数量为$N$，迭代次数$M$

---

1. 初始化$f_0(x)=\arg\min_{c}\sum_{y=1}^NL(y_i,c)$
2. 对$m=1,…,M$
   • 计算$r_{mi}=-\left[ \frac{\partial{L(y_i,f_{m-1}(x_i))}}{\partial{f_{m-1}(x_i)}} \right]$
   • 对$r_m$拟合一个回归树，对于它的每一个叶节点$R_{mj}$，确定节点的值为$c_{mj}=\arg\min_c\sum_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$
   • 更新$f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$
3. 得到回归树$f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$

---

输出：$f_M(x)$

---

GBDT(Gradient Boosting Decision Tree)几乎可用于所有的回归问题

集成学习的概念

机器学习中有着多种多样的算法，不同的算法有着不同优劣。对于现有单一算法的优化往往比较困难而且不一定会取得更好的效果。集成学习的思想就是将多个个体学习器组合起来以取得更好的性能。这对于弱学习器更加实用，集成学习的很多理论都是针对弱学习器的。集成学习有如下几个优点：

1. 减小“泛化性能不佳”的风险
2. 降低陷入局部极小值的风险
3. 更加全面的假设空间近似(多个学习器可以扩大假设空间)

目前集成学习方法按照个体学习器的生成方法可以分为两类：Boosting和随机森林。Boosting方法不在这里介绍，本文会介绍到随机森林。

---

学习器的结合方法

---

平均法

平均法的思想很简单，即将各个学习器加权平均

$$\begin{aligned} H(x)=\sum_{i=1}^T \omega_i h_i(x)\quad s.t.:\;\sum_{i=1}^T\omega_i=1 \end{aligned}$$

其中，$h_i(x)$为第$i$个学习器的结果。

---

投票法

投票法的思想也很简单，就是按照一定的规则进行投票选出最佳结果。一般作用于分类任务，定义学习器$h_i(x)$从预测标记集合中$\lbrace c_1,c_2,…,c_N \rbrace$。加权投票法可以表示为

$$\begin{aligned} H(x)=c_{\arg\max_j \sum_{i=1}^T \omega_ih_i^j(x)} \end{aligned}$$

其中，$h_i^j(x)$表示$h_i(x)$在类别标记$c_j$上的输出。

---

Stacking

Stacking先从数据集中训练出初级学习器，然后再生成“新的数据集”用于生成次级学习器。具体来说，初级学习器的输出被当作次级学习器的样例输入。Stacking算法描述如下（假定初级学习器使用不同的学习算法）

---

输入：训练集$D=\lbrace (x_1,y_1),…,(x_m,y_m) \rbrace$；初级学习器算法$\gamma_1,…,\gamma_T$；次级学习算法$\gamma$

---

1 $h_t = \gamma_t(D), \; t=1,…,T$
2 $D^{‘}=\varnothing$
3 $for\; i=1,…,m$
4 $\quad for\; t=1,…,T$
5 $\quad \quad z_{it}=h_t(x_i)$
6 $\quad D^{‘}=D^{‘} \cup ((z_{i1},…,z_{iT}),y_i)$
7 $h^{‘}=\gamma(D^{‘})$

---

输出：$H(x)=h^{‘}(h_1(x),…,h_T(x))$

---

训练阶段，次级训练集的是初级学习器产生的。如果直接使用初级学习器的训练集来产生次级训练集，过拟合风险比较大。一般使用cross validation或者留一法等方法，用初级学习器未使用的样本来产生次级学习器的训练样本。

---

Bagging与随机森林 （Random Forest）

---

Bagging

Bagging是并行式集成学习算法的代表，基于自助采样法（bootstrap sampling）。给定包含$m$个样本的训练集，每次随机选择一个样本，采样方式为放回式采样。采样$m$次，得到一个训练集，初始训练集中大约有63.2%的样本出现在新样本集中。

按照上面的方法，采集$T$个新的训练集，然后基于每个新的样本集训练出基学习器，然后将基学习器组合起来。这便是Bagging的基本思想。Bagging算法描述如下

---

输入：训练集$D=\lbrace (x_1,y_1),…,(x_m,y_m) \rbrace$；基学习器算法$\gamma$；训练轮数$T$

---

1 $for\;t=1,…,T$
2 $\quad D_{bs} \xleftarrow{bootstrap\; sampling} D$
3 $\quad h_t=\gamma(D_{bs})$

---

输出：$H(x)=\arg\max_{y\in Y} \sum_{t=1}^T I(h_t(x)=y)$

---

因为自助采样平均只使用初始训练集的63.2%，剩下的样本可用做验证集来对泛化性能进行“包外估计”（out-of-bag estimate）。令$D_t$表示$h_t$使用的样本集，令$H^{oe}(x)$表示对样本$x$的包外估计，且仅考虑那些未使用样本$x$的基学习器再$x$上的预测

$$\begin{aligned} H^{oe}(x)=\arg\max_{y\in Y} \sum_{t=1}^T I(h_t(x)=y)\times I(x\not\in D_t) \end{aligned}$$

Bagging的泛化误差的包外估计为

$$\begin{aligned} \epsilon^{oe}(x)=\frac{1}{\vert D\vert} \sum_{(x,y)\in D} I(H^{oe}(x)\neq y) \end{aligned}$$

Bagging主要侧重于降低方差，所以在不剪枝决策树、神经网络等易受样本扰动的学习器上效果明显。

---

随机森林

随机森林是Bagging的扩展，规定基学习器为决策树，在以基学习器为决策树构建Bagging集成学习器的基础上，进一步在决策树的训练过程中引入了随机属性选择。传统决策树在训练时，需要选取当前结点属性集中最佳属性，而在随机森林中则是先从属性集随机选出一个包含$k$个属性的子集，然后再从这个自己中选择最佳属性。很明显，随机森林的效率要比Bagging高，二者收敛性相似。一般地，随机森林的起始性能较差，随着个体学习器的数目增大，随机森林的泛化误差会收敛到更低。

背景描述

多臂老虎机问题来源于赌场，描述的是赌场中的一个赌徒，面对多个老虎机（多个摇臂），如何选择使用摇臂才能使自己的收益最大化的问题。想要最大化收益，赌徒需要知道每个摇臂对应的奖赏，然后选择下一次应该使用哪个摇臂。然而现实中，摇臂对应的奖赏往往不是一个确定的值，而是服从于某个分布的。这个问题属于强化学习研究的范畴。

对于每一次使用摇臂的机会，赌徒有两种选择:
1) 探索策略(exploration)：尝试新的摇臂以确定新的要比对应的奖赏
2) 利用策略(exploitation)：使用当前已知最好的摇臂
探索策略能很好估计每个摇臂的奖赏，却会失去很对选择好的摇臂的机会；而利用策略则相反，它只使用当前最好的选择，可能会错过最佳摇臂。这两个策略的出发点相同，但是操作上是相悖的，所以解决多臂老虎机问题可以从对这两个问题的折中上入手。

---

$\epsilon$-贪心

$\epsilon$-贪心法的思想是：每次尝试时，以$\epsilon$的概率进行搜索（均匀搜索），以$1-\epsilon$的概率利用现有最佳。

令$Q(k)$表示摇臂$k$的平均奖赏，摇臂$k$被使用了$n$次，收益分别是$v_1,v_2,…,v_n$，所以$Q(k)$可以表示成

$$\begin{aligned} Q(k)=\frac{1}{n} \sum_{i=1}^n v_i \end{aligned}$$

每次获得一个摇臂对应的奖赏，则更新其平均奖赏，这个只需要记录摇臂尝试次数和当前平均值即可进行下一次平均值的计算。算法描述如下：

---

输入：摇臂个数$K$，奖赏函数$R$，尝试次数$T$，搜索概率$\epsilon$

---

1 $r=0$.
2 $\forall i=1,…,K:set\;Q(i)=0,count(i)=0$.
3 $for\;t=1,…,T$
4 $\quad if\;rand()<\epsilon$
5 $\quad \quad k \xleftarrow{均匀选取} \lbrace 1,…,K \rbrace$.
6 $\quad else$
7 $\quad \quad k=\arg\max_i Q(i)$.
8 $\quad v=R(k)$.
9 $\quad r=r+v$.
10 $\quad Q(k)=\frac{Q(k)\times count(k)+v}{count(k)+1}$.
11 $\quad count(k)=count(k)+1$.

---

输出：累计奖励$r$

---

如果摇臂奖赏的不确定性较大，则需要更多的探索，对应的$\epsilon$也应该更大。反之，较小的$\epsilon$比较合适。当尝试次数非常大时，摇臂的奖赏可能都能很好地表示出来，而不再需要探索。为了防止问题退化，可让$\epsilon$随着尝试次数地增加而减少，比如$\epsilon=\frac{1}{\sqrt{t}}$。

---

Softmax

Softmax根据当前已知摇臂的平均奖赏对探索和利用进行折中，令$Q(k)$表示摇臂$k$的平均奖赏，摇臂概率的分布基于波尔兹曼分布

$$\begin{equation} P(k)=\frac{e^{\frac{Q(k)}{\tau}}} {\sum_{i=1}^K e^{\frac{Q(k)}{\tau}}} \end{equation}$$

其中，$\tau > 0$称为温度，$\tau$越小则平均奖赏高的摇臂被选取的概率越高。$\tau$趋近于0时，算法倾向于仅利用，$\tau$趋近于无穷大时，算法倾向于仅探索。Softmax算法描述如下：

---

输入：摇臂个数$K$，奖赏函数$R$，尝试次数$T$，温度参数$\tau$

---

1 $r=0$.
2 $\forall i=1,…,K:set\;Q(i)=0,count(i)=0$.
3 $for\;t=1,…,T$
4 $\quad$根据式$(1)$选取$k\gets \lbrace 1,…,K \rbrace$.
5 $\quad v=R(k)$.
6 $\quad r=r+k$.
7 $\quad Q(k)=\frac{Q(k)\times count(k)+v}{count(k)+1}$.
8 $\quad count(k)=count(k)+1$.

---

输出：累计奖励$r$

---

---

$\epsilon$-贪心和Softmax的优劣与应用相关，下图就是例子。


马尔可夫决策过程MDP是经典的增强学习算法。MDP可以表示为一个元组$MDP=(S,A,\lbrace P_{sa} \rbrace,\gamma,R)$其中$S$是状态集合；$A$是动作集合，也就是可能的操作集合；$P_{sa}$为每一个状态$s$在每一个动作$a$上定义转移概率，转移到不同状态的概率不同；$\gamma \in [0,1]$为折扣因子；$R:S\times A \to \mathbb{R}$表示回报函数。


---

贝尔曼方程（Bellman equation）

贝尔曼方程是理查德贝尔曼提出的，它是典型的动态规划方程，也是动态规划最优性的必要条件。贝尔曼方程在最优控制理论中有着重要的作用。理查德贝尔曼证明了离散时间上的动态规划问题可以被表示成递归的、一步一步完成的后向推导形式，其中这过程需要写出价值函数的递推关系，其实贝尔曼方程的最基本思想就是重叠子问题思想。代价函数的递推关系被称为贝尔曼方程，其形式化表述如下。

假设时刻$t$时的状态为$s_t$，采取的动作是$a_t$，到达的新状态可以计算成$T(s_t,a_t)$，对应的收益为$F(s_t,a_t)$。联系折扣因子$\beta$，从$s_0$开始的无穷决策问题的收益是

$$\begin{aligned} V(s_0)=\max_{\lbrace a_t \rbrace_{t=0}^{\infty}} \sum_{t=0}^{\infty} \beta^tF(s_t,a_t) \\ s.t.:\; s_{t+1}=T(s_t,a_t) \end{aligned}$$

上是可以简化为

$$\begin{aligned} V(s_0)=\max_{a_0} \lbrace F(s_0,a_0)+\beta V(s_1) \rbrace,\;s.t.:\;s_1=T(s_0,a_0) \end{aligned}$$

---

MDP模型描述

---

MDP形式定义

MDP可表示成这样的过程

$$\begin{aligned} s_0 \xrightarrow{a_0} s_1 \xrightarrow{a_1} s_2 \xrightarrow{a_2} s_3 \xrightarrow{a_3} ... \end{aligned}$$

在上面的情况下，整体收益可以表示成

$$\begin{aligned} R(s_0,a_0)+\gamma R(s_1,a_1) + \gamma^2 R(s_2,a_2) + ... \end{aligned}$$

MDP的目标就是选取一组动作以最大化收益均值即

$$\begin{aligned} \arg \max_{a_0,a_1,...}E[R(s_0,a_0)+\gamma R(s_1,a_1) + \gamma^2 R(s_2,a_2) + ... ] \end{aligned}$$

一个策略（policy）是由状态到动作的任意映射$\pi : S \to A$。执行一个策略$\pi$也就是对于任意状态$s$，系统采取的动作是$a=\pi(s)$。定义一个策略$\pi$的价值函数（value function）为

$$\begin{aligned} V^{\pi}(s)&=E[R(s_0,a_0)+\gamma R(s_1,a_1) + \gamma^2 R(s_2,a_2) + ... |s_0=s,\pi] \\ V^{\pi}(s)&=R(s)+\gamma \sum_{s^{'}\in S}P_{s\pi(s)}(s^{'})V^{\pi}(s^{'}) \end{aligned}$$

表示从状态$s$开始，根据策略$\pi$执行的累积收益和的均值。
定义最优价值函数为

$$\begin{aligned} V^{\*}(s)&=\max_{\pi} V^{\pi}(s) \\ V^{\*}(s)&=R(s)+\max_{a\in A}\gamma \sum_{s^{'}\in S}P_{sa}(s^{'})V^{\*}(s^{'}) \end{aligned}$$

指的是任何可能的策略下的最优解.

接下来定义最优策略，一个最优策略$\pi^{*}:S \to A$可以定义为

$$\begin{equation} \pi^{\*}(s)=\arg\max_{a\in A}\sum_{s^{'}\in S}P_{sa}(s^{'})V^{\*}(s^{'}) \end{equation}$$

策略$\pi^{*}$为每一个状态提供了最优策略，也就是说无论初始状态是什么，$\pi^{*}$都是最优策略。事实上，对每一个状态$s$和每一个策略$\pi$，我们有

$$\begin{aligned} V^{\*}(s)=V^{\pi^{\*}}(s) \ge V^{\pi}(s) \end{aligned}$$

---

价值迭代和策略迭代

为了描述简单，这里仅考虑有限状态空间、有限动作空间的MDP。在下面两个算法中，转移概率$\lbrace P_{sa} \rbrace$和回报函数$R$都是已知的。

---

价值迭代（value iteration）
1 初始化每个状态的价值$V(s)=0$
2 重复迭代直到收敛：
3 $\quad$对每个状态$s$，更新：$V(s)=R(s)+\max_{a\in A}\gamma \sum_{s^{‘}}P_{sa}(s^{‘})V(s{‘})$

---

其中，更新方式有两种
同步更新：先计算所有状态的价值函数，然后再将其一起更新
异步更新：每计算出一个状态的价值函数，就将其更新
但无论是同步还是异步，$V$都会逐渐收敛至$V^{*}$。有了$V^{*}$，就可以根据公式$(1)$计算出对应的策略了。

---

策略迭代（policy iteration）
1 随机初始化$\pi$
2 重复迭代直到收敛：
3 $\quad (a):$使得$V=V^{\pi}$
4 $\quad (b):$对每个状态$s$，使得$\pi(s)=\arg\max_{a\in A}\sum_{s^{‘}}P_{sa}(s^{‘})V(s^{‘})$

---

迭代过程中，先计算在当前策略$\pi$下每个状态的价值函数值，然后根据这些值找到每个状态对应的最佳动作（greedy）。这些动作的集合就构成了下一步的新策略。步骤$(a)$的计算还是先赋值再迭代计算直到收敛，只是要按照$\pi$策略跳转而已。

---

学习一个MDP模型

上面的讨论中，转移概率$\lbrace P_{sa} \rbrace$和回报函数$R$都是已知的，但是实际中这两部分经常是未知的（通常$S,A,\gamma$是已知的），因此需要通过学习算法来学习。

数据可以是采集的，也可以是通过实验得出来的。对$P_{sa}$的估计方法可以是

$$\begin{aligned} P_{sa}(s^{'})=\frac{times\; s \xrightarrow{a} s^{'}}{times\; s \xrightarrow{a} any\; state} \end{aligned}$$

在样本不够大的情况下，可能出现$\frac{0}{0}$的情况，如果分母为0，则把对应的概率换成$\frac{1}{\vert S\vert}$.

$R$的更新思想类似。

---

连续状态的MDP

现实中，MDP的离散状态假设是比较脆弱的。比如二维坐标中的位置就是连续的。那如何处理连续状态下的MDP呢

---

离散化

离散化的思想很直观，比如二维空间就可以通过网格化来达到离散化的目的。但是离散化有两个缺陷：
1 naive representation
对于$V^{*}$和$\pi^{*}$的表示太过简单，因为离散化会主动放弃潜在信息因此对平滑函数的表示效果比较差。比如离散化后的线性回归可能会得到如下图中的结果


2 维度诅咒
假设状态空间是$n$维的，离散化会使得离散化后的状态个数指数增加。

---

价值函数近似

一般地，在连续MDP问题中通常假设

在价值迭代中，连续状态的迭代公式应该是

$$\begin{aligned} V(s)&= R(s)+\gamma \max_{a} E_{s^{'}\sim P_{sa}}[V(s_{'}] \\ &= R(s)+\gamma \max_{a} \int_{s^{'}}P_{sa}(s^{'})V(s^{'})\,ds^{'} \end{aligned}$$

此式跟上面的区别是把原来的求和改成了积分。

在对应状态为$s^{(1)},s^{(2)},…,s^{(m)}$的有限个数样本情况下，价值函数近似就是要将价值函数近似为状态的函数，即

$$\begin{aligned} V(s)=\theta^T\phi(s) \end{aligned}$$

其中$\phi(s)$是状态$s$的合理映射。对于每一个样本$i$，算法先计算一个

$$\begin{aligned} y^{(i)} \gets R(s)+\gamma \max_{a} E_{s^{'}\sim P_{sa}}[V(s_{'}] \end{aligned}$$

上式的计算要使用采样逼近的原理，即采集多个样本求均值以逼近收集到每个样本的状态和对应的$y^{(i)}$，就可以使用监督学习算法训练出$V(s)$和$s$的模型。算法描述如下

---

1 随机采样$m$个状态，$s^{(1)},s^{(2)},…,s^{(m)} \in S$.
2 初始化$\theta=0$.
3 迭代：
4 $\quad for\;i=1,…,m$.
5 $\quad \quad for\;each\;a\in A$.
5 $\quad \quad \quad $采样$s_1^{‘},…,s_k^{‘} \sim P_{s^{(i)}a}$.
6 $\quad \quad \quad $设置$q(a)=\frac{1}{k} \sum_{j=1}^k R(s^{(i)})+\gamma V(s_j^{‘})$.
7 $\quad \quad \quad $//因此$q(a)$就是$R(s^{(i)})+\gamma E_{s^{‘}\sim P_{s^{(i)}a}}[V(s_{‘}]$的估计.
8 $\quad \quad $令$y^{(i)}=\max_{a}q(a)$.
9 $\quad \quad $//因此$q(a)$就是$R(s^{(i)})+\gamma \max_{a} E_{s^{‘}\sim P_{s^{(i)}a}}[V(s_{‘}]$的估计.
10 $\quad$使得$\theta=\arg\min_{\theta}\frac{1}{2} \sum_{i=1}^m (\theta^T\phi(s^{(i)})-y^{(i)})^2$.

得到了近似于$V^{*}$的$V$，最后选择action时还是根据

$$\begin{aligned} \arg\max_{a} E_{s^{'}\sim P_{sa}}[V(s^{'})] \end{aligned}$$

---

上述算法最后求$\theta$时使用的是线性回归方法，当然其他合适的方法也是可以的。
需要注意的是，价值函数近似方法并不能保证收敛，但是通常是收敛得。控制计算量的可用方法是调节算法第5步中的$k$值，有时候设置$k=1$也是可以的。

概率图模型

概率图模型是一类用图来表达变量相关关系的概率模型，常见的是用一个节点表示一个或一组随机变量，节点之间的边表示变量之间的概率关系。概率模型可以大致分为两类：

• 第一类使用有向无环图表示变量之间的依赖关系，称之为有向图模型或者贝叶斯网
• 第二类使用无向无环图表示变量之间的依赖关系，称之为无向图模型或者马尔可夫网

本文要介绍的隐马尔可夫模型就是结构简单的动态贝叶斯网。

隐马尔可夫模型

HMM的主要作用是时序数据建模，应用范围包括语音识别、自然语言处理等领域。
与马尔可夫过程不同，HMM中状态是无法直接观测的，取而代之，我们可以获取到与状态值息息相关的观测变量值，图中是经典的海藻与天气例子。


一个HMM模型中有两组变量，第一组是状态变量$Y=\lbrace y_1,y_2,…,y_n \rbrace$表示隐含的状态，下标表示时序。另一组是观测变量$X=\lbrace x_1,x_2,…,x_n \rbrace$，下标表示时序。系统可能会存在多个状态，这些状态的集合为$S=\lbrace s_1,s_2,…,s_N \rbrace$，如果$y_i = k$那么表示$i$时刻的状态为$s_k$。观测变量可以是离散的也可以是连续的，不妨假设其为离散值。同样地，定义观测值的集合$O = \lbrace o_1,o_2,…,o_M \rbrace$，如果$x_i = k$那么表示$i$时刻的状态为$o_k$。

HMM中有两个重要的性质：

• 观测变量的取值仅依赖于状态变量
• t时刻的状态仅依赖于t-1时刻的状态

基于上面两个性质，可以得到如下公式

$$\begin{aligned} p(x_1,y_1,...,x_n,y_n)=p(y_1)p(x_1|y_1)\prod_{i=2}^n p(y_i|y_{i-1})p(x_i|y_i) \end{aligned}$$

上式基本上描述了HMM的结构信息，在实际计算时还需要如下参数

---

状态转移概率$A=[a_{ij}]_{N\times N}$，其中$a_{ij}=p(y_{t+1}=j|y_t=i)$表示由状态$s_i$转移到状态$s_j$的概率。

输出观测概率$B=[b_{ij}]_{N\times M}$，其中$b_{ij}=p(x_t=j|y_t=i)$表示在状态$s_i$下观测值为$o_j$的概率。

初始状态概率$\pi=(\pi_1,…,\pi_N)$，其中$\pi_i=p(y_1=i)$表示初始状态为$s_i$的概率。

---

指定了状态空间$Y$，观测空间$X$和上述三组参数，一个HMM就确定了，所以一个HMM可以表示成一个五元组$(N,M,A,B,\pi)$，$N,M$分别表示状态值和观测值的可能取值范围。HMM也可以表示成$\lambda=(A,B,\pi)$。

下面考虑三个实际问题：

---

模型于观测序列匹配度

给定模型$\lambda=(A,B,\pi)$，如何有效计算其产生观测序列$X=(x_1,x_2,…,x_T)$的概率$p(X|\lambda)$？

为解决这一问题，Baum提出了前向算法，具体如下：
定义$\theta_t(j)$为在$t$时刻，整体观测序列为$x_1,…,x_t$，此时状态为$s_j$的概率。其中我们有

$$\begin{aligned} \theta_1(i) = \pi_ib_{ix_1} \end{aligned}$$

表示第一个观测值的概率，其递推式也很容易写出

$$\begin{aligned} \theta_{t+1}(i)=\left[\sum_{j=1}^N\theta_t(j)a_{ji}\right]b_{ix_{t+1}} \end{aligned}$$

有两部分构成，第一部分是由枚举$t$时刻的状态并跳转到$t+1$时刻，第二部分是$t+1$时刻的状态产生观测值的概率。

当$n=1$时，输出序列为$x_1$，此时计算概率$p(x_1|\lambda)$也就是计算初始状态集合每个可能的状态产生观测值$x_1$的概率和，也就是

$$\begin{aligned} p(x_1|\lambda)=\sum_{i=1}^N \theta_1(i) \end{aligned}$$

当$n=2$时，输出序列为$x_1x_2$，所以有

$$\begin{aligned} p(x_1,x_2|\lambda) &= \sum_{j=1}^N \theta_2(j) \end{aligned}$$

后面的依此类推，前向算法的描述如下：

---

1 初始化：$\theta_1(i)=\pi_ib_{i1}, 1\le i \le N$
2 $\theta_{t+1}(j)=\left[\sum_{i=1}^N \theta_t(i)a_{ij}\right]b_{jx_{t+1}}$
3 $p(x_1,…,x_T|\lambda)=\sum_{j=1}^N \theta_T(j)$

---

一共有$T$个时刻，每个时刻要考虑$N$个状态，每个状态又要考虑钱一个时刻的$N$个状态，所以时间复杂度为$O(N^2T)$。

推断隐藏序列

由于有时候我们需要隐藏序列包含的信息，所以给出隐藏序列是有必要的（比如词性标注最终就需要给出词性序列）。问题的形式化表述即为

$$\begin{aligned} \arg\max_{y_1,...,y_T} p(y_1,...,y_T|x_1,...,x_T,\lambda) \end{aligned}$$

这个问题的解决方法是维特比（Viterbi）算法。

定义维特比变量$\gamma_t(j)$：表示在时序$t$，观察序列为$x_1,…,x_t$，状态为$s_j$的最大概率，即

$$\begin{aligned} \gamma_t(j)=\max p(y_1,...,y_t=j|x_1,...,x_t,\lambda) \end{aligned}$$

直观来说，在时序$t+1$状态为$s_j$的最大概率应该是时序$t$时所有状态转换到时序$t+1$、观测值为$x_{t+1}$并且状态为$s_j$的最大值，即

$$\begin{aligned} \gamma_{t+1}(j)=\max_k \gamma_{t}(k)a_{kj}b_{jx_{t+1}} \end{aligned}$$

并且，为了记忆路径，定义路径变量$\phi_t(j)$为该路径上的状态$s_j$的前一个状态，即从$t-1$时序到$t$的最优转移方式。

维特比算法的描述如下：

---

1 初始化：
2 $\quad \gamma_1(j)=\pi_i b_{ix_{1}},\;\phi_1(i)=0,1\le i \le N$
3 归纳计算：
4 $\quad \gamma_t(j)=\max_k \gamma_{t-1}(k)a_{kj}b_{jx_{t}}$
5 $\quad \phi_t(i)=\arg\max_j \gamma_{t-1}(j)a_{jk}b_{kx_{t}}$
6 确定路径：
7 $\quad y_T=\arg\max_{y_j} \gamma_{T}(j)$
8 $\quad for\;t=T-1,…,1$
9 $\quad \quad y_t=\phi_{t+1}(y_{t+1})$

---

模型训练

HMM的学习就是给定观测序列$X=x_1,…,x_T$，试图找到最优的参数$\lambda$使得$p(X|\lambda)$最大。如果知道了状态序列，那么$\pi,A,B$就都可以统计出来。但是状态序列其实是隐变量，求解此问题的方法是前向后向算法，也叫做Baum-Welch算法。

定义

$$\begin{aligned} \beta_t(i)=p(x_{t+1},...,x_T|y_t=i,\lambda) \end{aligned}$$

表示当前$t$时刻状态为$s_i$，部分观测序列为$x_{t+1},…,x_T$的概率。与前向算法类似，$\beta_t(i)$也可以有效地计算，公式如下

$$\begin{aligned} \beta_t(i)&=\left[\sum_{j=1}^N \beta_{t+1}(j)a_{ij}\right]b_{jx_{t+1}},\; 1\le t \le T-1 \\ \beta_T(i)&=1 \end{aligned}$$

进一步可以得到

$$\begin{aligned} p(X,y_t=i|\lambda)&=p(x_1,...,x_t,y_t=i|\lambda)p(x_{t+1},...,x_T,y_t=i|\lambda)=\theta_t(i)\beta_t(i) \\ p(X,y_t=i|\lambda)&=\sum_{i=1}^N \theta_t(i)\beta_t(i) \end{aligned}$$ 

在前后向算法中，定义$\xi_t(i,j)=p(y_t=i,y_{t+1}=j|X,\lambda)$表示给定HMM和观测序列$X$，$t,t+1$时刻的状态分别是$s_i,s_j$的概率。如上图所示，对上式的推导为

$$\begin{aligned} \xi_t(i,j)&=\frac{p(y_t=i,y_{t+1}=j,X|\lambda)}{p(X|\lambda)} \\ &= \frac{\theta_t(i)a_{ij}\beta_{t+1}(j)b_{jx_{t+1}}} {\sum_{i=1}^N \sum_{j=1}^N \theta_t(i)a_{ij}\beta_{t+1}(j)b_{jx_{t+1}}} \end{aligned}$$

除此之外，再定义$\eta_t(i)=p(y_t=i|X,\lambda)$表示给定HMM和观测序列$X$，$t$时刻状态为$s_i$的概率，所以有

$$\begin{aligned} \eta_t(i) = \frac{p(y_t=i,X|\lambda)} {p(X|\lambda)} = \frac{\theta_t(i)\beta_t(i)}{\sum_{i=1}^N \theta_t(i)\beta_t(i)} \end{aligned}$$

考虑$\xi_t(i,j)$和$\eta_t(i)$的定义，就能够得到（想想就能得到）$\eta_t(i)=\sum_{i=1}^N \xi_t(i,j)$下面介绍前向后向算法的描述：

---

1 初始化：随机初始化参数$A,B,\lambda$
2 不满足停止条件时迭代计算：
3 $\quad \beta_T(i)=1,1\le i \le N$
4 $\quad \beta_t(i)=\left[\sum_{j=1}^N \beta_{t+1}(j)a_{ij}\right]b_{jx_{t+1}},\; t \in \lbrace T-1,…,1 \rbrace,1\le i \le N $
5 $\quad \theta_{t}(i)=\left[\sum_{j=1}^N \theta_{t-1}(j)a_{ji}\right]b_{ix_{t}}$
6 $\quad$计算$\xi_t(i,j),\eta_t(i), 1\le i,j \le N,1 \le t \le T$
7 $\quad $更新参数：
8 $\quad \pi=\eta_1(i),1\le i \le N$
9 $\quad a_{ij}=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\eta_t(i)},1\le i,j \le N$
10 $\quad b_{jk}=\frac{\sum_{t=1,x_t=k}^T\quad \eta_t(j)} {\sum_{t=1}^{T}\eta_t(j)} ,1\le j \le N,1\le k \le M$
11 输出HMM：$\lambda=(A,B,\pi)$

$o_t=k$表示$t$时刻的观测值为第$k$种观测值。停止条件可以是：参数$\lambda=(A,B,\pi)$收敛。

---

支持向量机（SVM）

---

支持向量机是一种非常优秀的线性分类器。
给定数据集$D=\lbrace (x_1,y_1),(x_2,y_2),…,(x_m,y_m) \rbrace ,y_i\in \lbrace -1,1 \rbrace$，当$y_i=1$时，称$x_i$为正类；否则为负类。基本思想是在样本及空间内找到一个超平面将不同类别的样本分开。设超平面为

$$\begin{aligned} \omega^Tx+b=0 \end{aligned}$$

将特征空间划分两个部分，一部分是正类，一部分是负类，法向量指向的一侧为正类，反之为负类。相应的分类决策函数为$f(x)=sign(\omega^Tx+b)$。

---

函数间隔

定义超平面$(\omega,b)$关于样本点$(x_i,y_i)$的函数间隔为

$$\begin{aligned} \hat{\gamma_i}=y_i(\omega^Tx_i+b) \end{aligned}$$

函数间隔的正负可以表示分类结果是否准确，其大小可以相对地表示样本点到超平面的远近，越远置信度越高。
定义超平面$(\omega,b)$关于数据集$D$的函数间隔为$(\omega,b)$关于$D$中样本点$(x_i,y_i)$的函数间隔的最小值，即

$$\begin{aligned} \hat{\gamma}=\min_{i=1,...,m}\hat{\gamma_i} \end{aligned}$$

函数间隔可以表示分类的准确度和置信度。但是，函数间隔还存在一个明显问题，比如将$\omega$和$b$都扩大2倍，超平面不变，但是函数间隔却扩大了2倍，解决方案是对函数间隔添加规范化约束。

几何间隔

定义超平面$(\omega,b)$关于分类正确的样本点$(x_i,y_i)$的几何间隔为

$$\begin{aligned} \gamma_i=\frac{y_i( \omega^Tx_i+b )}{\Vert \omega \Vert} \end{aligned}$$

定义超平面$(\omega,b)$关于数据集$D$的几何间隔为$(\omega,b)$关于$D$中样本点$(x_i,y_i)$的几何间隔的最小值，即

$$\begin{aligned} \gamma=\min_{i=1,...,m}\gamma_i \end{aligned}$$

间隔最大化

SVM学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面，意味着以充分大的确信度对训练数据进行分类，以获得更好的泛化能力。所以问题就变成了

$$\begin{aligned} & \max_{\omega,b}\quad\gamma \\ & s.t. \quad \frac{y_i( \omega^Tx_i+b )}{\Vert \omega \Vert} \ge \gamma,\; i=1,2,...,m \end{aligned}$$

考虑到$\gamma=\frac{\hat{\gamma} }{\Vert \omega \Vert}$，所以上式可以写成

$$\begin{aligned} & \max_{\omega,b}\quad\frac{\hat{\gamma} }{\Vert \omega \Vert} \\ & s.t. \quad y_i( \omega^Tx_i+b ) \ge \hat{\gamma},\; i=1,2,...,m \end{aligned}$$

前面提到将$(\omega,b)$按比例缩放不会影响最终结果，所以可以取$\hat{\gamma}=1$，所以原问题可以转化为如下问题

$$\begin{aligned} & \max_{\omega,b}\quad\frac{1 }{\Vert \omega \Vert} \\ & s.t. \quad y_i( \omega^Tx_i+b ) \ge 1,\; i=1,2,...,m \end{aligned}$$

即

$$\begin{aligned} &\min_{\omega,b} \frac{1}{2}\Vert \omega \Vert^2 \\ & s.t. \quad y_i( \omega^Tx_i+b ) \ge 1,\; i=1,2,...,m \end{aligned}$$

这就是SVM的基础形态，是一个凸二次规划问题。

---

拉格朗日对偶性

考虑如下的优化问题

$$\begin{aligned} \min_{\omega} f(\omega) \\ \quad \quad s.t. \quad g_i(\omega) &\le 0 \\ h_i(\omega) &= 0 \end{aligned}$$

对应的拉格朗日函数如下，$\alpha,\beta$是拉格朗日乘子

$$\begin{aligned} L(\omega,\alpha,\beta)=f(\omega)+\sum_{i=1}^k\alpha_ig_i(\omega) + \sum_{i=1}^l\beta_ih_i(\omega). \end{aligned}$$

考虑下面的优化问题

$$\begin{aligned} \theta_P(\omega)=\max_{\alpha,\beta:\alpha_i\ge 0} L(\omega,\alpha,\beta) \end{aligned}$$

下标$P$是$primal$的意思，优化目标针对变量$\alpha,\beta$。给定$\omega$，如果$\omega$的任何一个分量违背了限制条件(比如$g_i(\omega)>0$或者$h_i(\omega) \neq 0$)，那么$\theta_P(\omega)$就是无穷大！反之，如果限制条件没有被打破，那么$\theta_P(\omega)=f(\omega)$，所以

$$\theta_P(\omega)=\begin{cases} f(\omega) & 如果 \omega满足限制条件 \\ \infty & 其他 \end{cases}$$

下式成立

$$\begin{aligned} \min_{\omega} \theta_P(\omega) = \min_{\omega} \max_{\alpha,\beta:\alpha_i\ge 0} L(\omega,\alpha,\beta) = p^{\*} \end{aligned}$$

---

下面考虑对偶问题，定义

$$\begin{aligned} \theta_D(\alpha,\beta) = \min_{\omega} L(\omega,\alpha,\beta) \end{aligned}$$

这里下标$D$表示$dual$，优化目标针对变量$\omega$。所以有

$$\begin{aligned} \max_{\alpha,\beta:\alpha_i\ge 0} \theta_D(\alpha,\beta) = \max_{\alpha,\beta:\alpha_i\ge 0} \min_{\omega} L(\omega,\alpha,\beta) = d^{\*} \end{aligned}$$

---

对于上面的$p^{*}$和$d^{*}$，有如下的规律

$$\begin{aligned} d^{\*}=\max_{\alpha,\beta:\alpha_i\ge 0} \min_{\omega} L(\omega,\alpha,\beta) \le \min_{\omega} \max_{\alpha,\beta:\alpha_i\ge 0} L(\omega,\alpha,\beta) = p^{\*} \end{aligned}$$

上式中等号成立的条件是：函数$f$和$g_i$都是凸函数，$h_1,h_2,…,h_l$函数是同族函数。并且每个$g_i$函数都是严格合理的，即对每一个$i$，都存在一些$\omega$满足$g_i(\omega)小于0$。此外，存在$(\alpha,\beta,\omega)$满足KKT条件，即

$$\begin{aligned} \frac{dL(\alpha,\beta,\omega)}{d\omega_i} &= 0,\quad i=1,...,m \\ h_i(\omega)&= 0,\quad i=1,...,l \\ \alpha_i g_i(\omega) &= 0, \quad i=1,...,k \\ g_i(\omega) &\le 0, \quad i=1,...,k \\ \alpha_i &\ge 0 , \quad i=1,...,k \end{aligned}$$

---

对偶问题

由最大化间隔得出的优化问题是一个凸二次规划问题，可以使用现成的工具完成。使用拉格朗日乘子法可得到其对偶问题，为其每项约束添加一个拉格朗日乘子$\alpha_i \ge 0$，拉格朗日目标函数为

$$\begin{aligned} L(\omega,b,\alpha) = \frac{1}{2}\Vert \omega \Vert^2 + \sum_{i=1}^m \alpha_i(1-y_i(\omega^Tx_i+b)) \end{aligned}$$

其中，$\alpha=(\alpha_1;\alpha_2;…;\alpha_m)$。上式分别对$\omega,b$求偏导并令其为0可得

$$\begin{aligned} \omega = \sum_{i=1}^m \alpha_iy_ix_i \\ 0 = \sum_{i=1}^m \alpha_iy_i \end{aligned}$$

将上式代入$L(\omega,b,\alpha)$中，消去$\omega,b$，则上式变成

$$\begin{aligned} L(\omega,b,\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j x_i^T x_j \end{aligned}$$

由于满足KKT条件，所以原问题$f(\omega)$的优化问题可以写成

$$\begin{aligned} \min_{\omega,b} f(\omega) &\to \min_{\omega,b} \max_{\alpha} L(\omega,b,\alpha) \\ &\to \max_{\alpha} \min_{\omega,b} L(\omega,b,\alpha) \end{aligned}$$

这里$ \max_{\alpha} L(\omega,b,\alpha)$的意义在于选择参数$\alpha$使得$ L(\omega,b,\alpha)$最大，根据$ L(\omega,b,\alpha)$的公式，由于$1\le y_i(\omega^Tx_i+b)$，所以一旦出现$1 < y_i(\omega^Tx_i+b)$的情况，就应该有$\alpha_i=0$，否则这一项就是负值，整体也就不是最小值了。所以，优化问题最终转化为

$$\begin{aligned} \max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j x_i^T x_j \\ s.t. \; \sum_{i=1}^m\alpha_iy_i=0,\alpha_i \ge 0,\; i=1,...,m \end{aligned}$$

---

Sequential Minimal Optimization

对偶问题依旧是二次规划问题，但问题的规模正比于训练样本数。SMO是高效算法之一，其思想是每次选取两个变量$\alpha_i,\alpha_j$并固定其他的$\alpha_k$，不断执行迭代步骤。这种方法也称为坐标上升方法（coordinate ascent）。

令$\alpha_iy_i+\alpha_jy_j=-\sum_{k\neq i,j}\alpha_ky_k=c$用这个式子消去优化目标函数中的$\alpha_j$可以得到一个以$\alpha_i$为单变量的二次规划问题，该问题有闭式解且简单易懂。解出之后，$\alpha_i,\alpha_j$就得到了更新。SMO选取$\alpha_i,\alpha_j$时，启发式地选择对应样本间隔最大的变量进行更新。

然后根据$\omega = \sum_{i=1}^m \alpha_iy_ix_i$求出$\omega$，对于$b$，可以使用任意一个支持向量的性质$y_s \left(\omega^Tx_s+b \right)=1$来计算。当然更鲁棒的方法是使用所有的支持向量并对求出的$b$取均值。

---

软间隔支持向量机（Soft Margin SVM）

基础型的SVM的假设所有样本在样本空间是线性可分的(硬间隔)，但是现实中的情况通常不满足这种特性。对应的软间隔允许某些样本不满足

$$\begin{aligned} y_i(\omega^Tx_i+b)\ge 1 \end{aligned}$$

为了解决这个问题，可以对每个样本点引入一个松弛变量$\xi_i\ge 0$满足

$$\begin{aligned} y_i(\omega^Tx_i+b)+\xi_i\ge 1 \end{aligned}$$

同时，对每个松弛变量支付一个代价$\xi_i$。训练时应该要保持不满足约束的样本尽量少，所以优化函数可以表示成

$$\begin{aligned} &\min_{\omega,b,\xi_i} \frac{1}{2}\Vert \omega \Vert^2 + C\sum_{i=1}^m \xi_i \\ &s.t. \; y_i(\omega^Tx_i+b) \ge 1-\xi_i \\ &\quad \xi_i \ge 0,\;i=1,...,m \end{aligned}$$

其中，$C>0$是一个惩罚参数，调节损失函数两项的权重。
这就是常用的软间隔支持向量机，通过拉格朗日乘子法，得到如下拉格朗日函数

$$\begin{aligned} L(\omega,b,\alpha,\xi,\mu) = \frac{1}{2}\Vert \omega \Vert^2 + C\sum_{i=1}^m \xi_i + \sum_{i=1}^m \alpha_i(1-\xi_i-y_i(\omega^Tx_i+b)) - \sum_{i=1}^m \mu_i\xi_i \end{aligned}$$

其中，$\alpha_i,\mu_i$就是拉格朗日乘子。令$L(\omega,b,\alpha,\xi,\mu)$对$\omega,b,\xi$的偏导数为0得到

$$\begin{aligned} \omega &= \sum_{i=1}^m \alpha_iy_ix_i \\ 0 &= \sum_{i=1}^m \alpha_iy_i \\ C &= \alpha_i + \mu_i \end{aligned}$$

由上式可知$0 \le \alpha_i \le C$。将上式代入$L(\omega,b,\alpha,\xi,\mu)$中，并求解优化函数的对偶形式

$$\begin{aligned} &\max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j x_i^T x_j \\ &s.t. \sum_{i=1}^m\alpha_iy_i=0 \\ &0 \le \alpha_i \le C,\; i=1,...,m \end{aligned}$$

对于软间隔支持向量机，其KKT条件是

$$\begin{aligned} \alpha_i y_i(\omega^x_i+b)-1+\xi_i &= 0, \quad i=1,...,m \\ y_i(\omega^x_i+b)-1+\xi_i &\le 0, \quad i=1,...,m \\ \alpha \ge 0,\mu_i &\ge 0, \quad i=1,...,m \\ \xi_i \ge 0, \mu_i \xi_i &= 0, \quad i=1,...,m \end{aligned}$$

对于非支持向量，$\alpha_i=0$。对支持向量，有$0 < \alpha_i \le C$，即有$y_i(\omega^x_i+b)=1-\xi_i$，样本点$x_i$到间隔边界的距离为$\frac{\xi_i}{\Vert \omega \Vert}$，软间隔的支持向量有以下几种情况

• 或者在间隔边界上（$\alpha_i < C,\xi_i=0$）
• 或者在间隔边界与分离超平面之间（$\alpha_i=C,0 < \xi_i < 1$，此时分类也是正确的）
• 或者在分离超平面误分那一侧（$\alpha_i=C,\xi_i>1$，分类错误，该样本是异常点）

上述优化问题依旧可以使用SMO算法，求出$\omega$之后，$b$的求法如下。注意到满足$0<\alpha_i < C$的样本是支持向量，即满足$y_i(\omega^Tx_i+b)=1$，所以$b$就可解了。

非线性核支持向量机（Kernal SVM）

核函数判定定理

设$X$是输入空间，$k(\cdot,\cdot)$是定义在$X\times X$的对称函数，则$k$是核函数当且仅当对于任意数据集$D=\lbrace x_1,x_2,…,x_m \rbrace$，核矩阵$K$总是半正定的，其中半正定是指对于每个非零的复向量$z$，$z^{*}Kz > 0$，其中$z^{*}$是$z$的共轭转置。

常用的核函数有

$$\begin{aligned} Linear\; kernal &: \quad k(x_i,x_j)= x_i^Tx_j \\ Multinomial\; kernal &: \quad k(x_i,x_j)= (x_i^Tx_j)^d \\ Gaussian\; kernal &: \quad k(x_i,x_j)= e^{-\frac{\Vert x_i-x_j \Vert^2}{2\sigma^2}} \\ Laplace\; kernal &: \quad k(x_i,x_j)= e^{-\frac{\Vert x_i-x_j \Vert}{\sigma}} \\ Sigmoid\; kernal &: \quad k(x_i,x_j)= tanh(\beta x_i^Tx_j+\theta),\beta>0,0>\theta \end{aligned}$$

另外核函数的线性组合、乘积也是核函数。并且对于任意函数$g(\cdot)$，$k(x,z)=g(x)k_1(x,z)g(z)$也是核函数。

---

KSVM

基础型的SVM的假设样本在样本空间是线性可分的，但是现实中的情况通常不满足这种特性。对于这种问题，一种可能的方法是将样本从原始空间映射到更高维的特征空间，使得其在线性可分。令$\phi (x)$表示将$x$映射后的特征向量，于是特征空间中的超平面可以表示为$f(x)=\omega^T \phi (x)+b$优化的对偶问题变成

$$\begin{aligned} \max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \phi (x_i)^T \phi (x_j) \\ s.t. \; \sum_{i=1}^m\alpha_iy_i=0,\alpha_i \ge 0,\; i=1,...,m \end{aligned}$$

由于可能存在维度诅咒，计算$\phi (x_i)^T \phi (x_j)$将非常困难。这里引入核函数的概念

$$\begin{aligned} k(x_i,x_j) = \langle \phi (x_i),\phi (x_j) \rangle = \phi (x_i)^T \phi (x_j) \end{aligned}$$

满足$x_i,x_j$在特征空间的内积等于它们在原始样本空间中通过函数$k(\cdot)$计算的结果，核函数是避免维度诅咒的一种方法。

引用
[1]. 统计学习方法. 李航著. 清华大学出版社
[2]. 机器学习. 周志华.

字典学习

字典学习是与稀疏性相关的学习方法，它被用来寻找一组“超完备”基向量来更高效地表示样本数据。稀疏性会降低计算和存储的开销，并且会提高模型的可解释性。

稀疏表示侧重于学习一个字典

给定数据集$\lbrace x_1,x_2,…,x_m \rbrace$，字典学习的简单形式如下

$$\begin{aligned} \min_{B,\alpha_i} \sum_{i=1}^m \Vert x_i-B\alpha_i \Vert_2^2 + \lambda \sum_{i=1}^m \Vert \alpha_i \Vert_1 \end{aligned}$$

其中$B\in R^{d\times k}$为字典矩阵，$k$称为字典的词汇量，$\alpha_i \in R^k$是样本$x_i$的稀疏表示。实际中，根据应用场景的要求，第二项中的$\lambda \sum_{i=1}^m \Vert \alpha_i \Vert_1$也可以替换成别的代价函数。

奇异值分解简述SVD

对任意矩阵奇异值分解$M=U\Sigma V^T$其中，$\Sigma$是对角矩阵，对角线上是矩阵的奇异值，$U$中的每一列是经过$M$转化后的标准正交基组成之一，而$V$表示了原始域的标准正交基，每一列是一个向量。

以后应该还有关于SVD的解释

训练方法

上式的训练目标参数有$\alpha_i,B$，可以用交替优化的方法。

---

1 为每个样本$x_i$找到相应的$\alpha_i$，即

$$\begin{aligned} \min_{\alpha_i} \Vert x_i-B\alpha_i \Vert_2^2 + \lambda \Vert \alpha_i \Vert_1 \end{aligned}$$

这一步可以使用lasso的优化方法。

---

2 以$\alpha_i$为初值来更新字典$B$，即

$$\begin{aligned} \min_{B} \Vert X-BA \Vert_F^2 \end{aligned}$$

其中，$X=(x_1,x_2,…,x_m)\in R^{d\times m},A=(\alpha_1,\alpha_2,…,\alpha_m)\in R^{k\times m}$，矩阵的F范数是矩阵每个元素的平方和再开方。

上式的常用优化方法为KSVD，这是基于逐列更新的方法。令$b_i$表示字典$B$的第$i$列，$\alpha^i$表示稀疏矩阵$A$的第$i$行($\alpha_i$表示稀疏矩阵$A$的第$i$列)，$b_i\alpha^i$其实是个矩阵。则上式可以重写成

$$\begin{aligned} \min_{B} \Vert X-BA \Vert_F^2 &= \min_{b_i} \left\Vert X-\sum_{j=1}^k b_ja^j \right\Vert_F^2 \\ &= \min_{b_i} \left\Vert X-\sum_{j=1,j\not i}^k b_ja^j - b_i\alpha^i \right\Vert_F^2 \\ &= \min_{b_i} \Vert E_i-b_i\alpha^i \Vert_F^2 \end{aligned}$$

更新字典第$i$列时，$E_i$是固定的，$E_i$表示没有$b_i$时表示的误差。所以最小化上式原则上就是对$E_i$进行奇异值分解(SVD)取得最大奇异值所对应的正交向量。对$E_i$进行奇异值分解$E_i=U\Sigma V^T$，那么$b_i$是$U$中最大奇异值对应的正交向量，但此时$\alpha^i$也需要更新，这就会破坏$\alpha^i$的稀疏性质。

为了避免这种情况，KSVD做如下处理。注意到要保持稀疏性，我们不能将$\alpha_i$原来为0的位置变成非零数。$b_i \alpha^i$是一个矩阵，它的第$j$列是$b_i\alpha_j^i$。如果原来$\alpha_j^i=0$，那么$b_i\alpha_j^i$就是全为0的列向量。这里，我们可以把$E_i$对应位置的列变成全0，这样奇异值分解后的结果就不会破坏$A$的稀疏性。然后，对$E_i$进行奇异值分解，更新$b_i$为$U$中最大奇异值对应的正交向量，更新$\alpha^i$为$V$中最大奇异值对应的正交向量(列向量)乘以最大奇异值。

---

稀疏编码

稀疏编码是字典学习的下一步，在学习到了字典$B$后，给定一个新的样本$x_k$，只需要通过优化

$$\begin{aligned} \min_{\alpha_i} \Vert x_k-B\alpha_k \Vert_2^2 + \lambda \Vert \alpha_k \Vert_1 \end{aligned}$$

来找到$\alpha_k$，即求解出了基于字典$B$的关于$x_k$的稀疏表示。上式的优化方法即经典的Lasso优化问题，使用Proximal Gradient Descent方法。

比如说：


流形

流形学习是一类借鉴了拓扑流行概念的概念降维方法
直观上来讲，一个流形好比是一个 d 维的空间
在一个 m 维的空间中 (m > d) 被扭曲之后的结果

比如说一块布，可以把它看成一个二维平面，这是一个二维的欧氏空间，现在我们（在三维）中把它扭一扭，它就变成了一个流形（当然，不扭的时候，它也是一个流形，欧氏空间是流形的一种特殊情况），地球表面其实也只是一个二维流形。

流形的一个特点是：流形是在局部与欧式空间 同胚 的空间
即局部上具有欧式空间的特性，距离度量可以使用欧氏距离

所以，低维流形嵌入到高维空间中，数据样本在高维空间中的分布看上去会比较复杂，但在局部上具有欧式空间的特性。因此，可以容易地在局部建立降维映射关系，然后设法将局部关系映射到全局。此种降维方法可被用于数据可视化。

---

等度量映射（Isometric Mapping）

Isomap的出发点是：低维嵌入流形上两点距离是“测地线距离”（地理上的概念，比如地球上两点的距离就不是欧氏距离）
但是利用流形的局部与欧式空间同胚特性，我们就能在局部空间内找到每个点的近邻点，从而建立一个近邻连接图。
所以，“测地线距离”就是图中的最短距离。最短路径算法可以使用Dijkstra算法或者Floyd算法。
有了距离度量表示，就可以降维了，降维方法可以使用MDS算法（当然也可以使用其他方法）

Isomap算法描述如下：

---

输入：样本集$D= \lbrace x_1,x_2,…,x_m \rbrace $; 近邻参数$k$; 低维空间维度$d^{‘}$

---

1 $for\quad i=1,…,m \quad do$
2 $\quad$确定$x_i$的$k$近邻
3 $\quad x_i$与其$k$近邻的距离设置为其欧氏距离，与其他点的距离设置为无穷大
4 $end \quad for$
5 调用最短距离路径算法计算任意两点之间的距离$dist(x_i,x_j)$
6 将$dist(x_i,x_j)$作为MDS算法的输入，输出结果$Z$

---

输出：样本集$D$在低维空间的投影$Z$

---

局部线性嵌入（Locally Linear Embedding）

Isomap 希望保持任意两点之间的测地线距离，保存的信息量大，但是计算量随着节点数量的增长爆炸增长（Dijkstra算法$O(n^2)$或者Floyd算法$O(n^3)$）。
LLE 希望保持局部线性关系，信息量较小，但是对数据量较大的情形则比较有效。

LLE假设$x_i$能够通过其邻域内的样本$x_j,x_k,x_l$线性表出，即$x_i=\omega_{ij}x_j+\omega_{ik}x_k+\omega_{il}x_l$所以，LLE需要先找出每个样本$x_i$的近邻下标集合$Q_i$，然后计算出基于$Q_i$中的样本对$x_i$进行线性重构的系数$\omega_i$：

$$\begin{aligned} \min_{\omega_1,\omega_2,...,\omega_m} \sum_{i=1}^m \left\Vert x_i-\sum_{j \in Q_i}\omega_{ij}x_j \right\Vert^2 \\ s.t. \quad \sum_{j \in Q_i}\omega_{ij}=1 \end{aligned}$$

这里令$C_{jk}=(x_i-x_j)^T(x_i-x_k)$，$\omega_{ij}$有闭式解

$$\begin{aligned} \omega_{ij}=\frac{\sum_{k\in Q_i}C_{jk}^{-1}}{\sum_{l,s\in Q_i}C_{ls}^{-1}} \end{aligned}$$

因为LLE假设在低维空间中保持$\omega_i$保持不变，令$Z=(z_1,z_2,…,z_m)\in R^{d^{‘}\times m},W_{ij}=\omega_{ij}$.所以$x_i$的低维坐标$z_i$可以通过

$$\begin{aligned} \min_{z_1,z_2,...,z_m} \sum_{i=1}^m \left\Vert z_i-\sum_{j\in Q_i}\omega_{ij}z_j \right\Vert^2 \\ \min_{z_1,z_2,...,z_m} \sum_{i=1}^m \left\Vert z_i-W_iZ \right\Vert^2 \end{aligned}$$

求解，这里需要对$z_i$正规化以满足$\sum_i z_i=0,\frac{1}{m}\sum_i z_iz_i^T=I$。可以令$M=(I-W)^T(I-W)$，那么优化函数可以写成$\min_Z tr(ZMZ^T) \quad s.t \; ZZ^T=I$这里需要注意我们假设对$Z$正规化，才能满足$ZZ^T=I$。然后上面的优化函数可以通过特征值分解，取最小的$d^{‘}$个非零特征值对应的特征向量即为$Z^T$。

LLE算法描述

---

输入：样本集$D={x_1,x_2,…,x_m}$; 近邻参数$k$; 低维空间维度$d^{‘}$

---

1 $for\; i=1,…,m \quad do$
2 $\quad$确定$x_i$的$k$近邻
3 $\quad$求$\omega_{ij},\; j\in Q_i$, 不在$x_i$邻域内的系数为0
4 $end \; for$
5 求矩阵$M$
5 对$M$进行特征值分解
6 输出最小的$d^{‘}$个非零特征值对应的特征向量

---

输出：样本集$D$在低维空间的投影$Z$

---

拉普拉斯特征映射(Laplacian Eigenmaps)

待更……

Multiple Dimensional Scaling (MDS、多维缩放)是经典的聚类算法。

---

假设原始$d$维样本空间中有$m$个样本$x_1,x_2,…,x_m$，其距离矩阵为$D \in R^{m\times m}$，$dist_{ij}$为$x_i$到$x_j$的距离。MDS的出发点是获得样本在$d^{‘}$维空间内的表示$Z\in R^{d^{‘} \times m}$，新空间内样本的距离等于原始空间的距离，即$\Vert z_i-z_j \Vert = dist_{ij}$令$B=Z^TZ \in R^{m\times m}$，其中$B$为降维后的样本内积矩阵，$b_{ij}=z_i^Tz_j$，有

$$\begin{aligned} dist_{ij}^2 &= \Vert z_i \Vert + \Vert z_j \Vert - 2z_i^Tz_j \\ &= b_{ii}+b_{jj}-2b_{ij} \end{aligned}$$

假设样本$Z$被中心化(normalization)，即$\sum_{i=1}^m z_i=0$。于是有$\sum_{i=1}^mb_{ij}=\sum_{j=1}^mb_{ij}=0$。继而有

$$\begin{aligned} \sum_{i=1}^m dist_{ij}^2 = tr(B)+mb_{jj} \\ \sum_{j=1}^m dist_{ij}^2 = tr(B)+mb_{ii} \\ \sum_{i=1}^m \sum_{j=1}^m dist_{ij}^2 = 2mtr(B) \end{aligned}$$

其中，$tr$表示矩阵的秩，$tr(B)=\sum_{i=1}^m \Vert z_i \Vert^2$，联立上式可得$b_{ij}=-\frac{1}{2} \left( dist_{ij}^2 - \frac{1}{m}\sum_{i=1}^m dist_{ij}^2 -\frac{1}{m}\sum_{j=1}^m dist_{ij}^2 + \frac{1}{m^2}\sum_{i=1}^m \sum_{j=1}^m dist_{ij}^2 \right)$由此即可通过降维前后保持不变的距离矩阵$D$求取内积矩阵$B$。

那么，下面就需要求$Z$了。方法是对$B$做特征值分解，得到

$$\begin{aligned} B=Z^TZ=V\Lambda V^T \end{aligned}$$

其中，$\Lambda=diag(\lambda_1,…,\lambda_{d})$为$d$个特征值构成的对角矩阵，$\lambda_1 \ge \lambda_2 \ge … \ge \lambda_d$。令$\Lambda_{*}=diag(\lambda_1,…,\lambda_{d^{*}})$为对角矩阵，$\Lambda_{*}$表示对应的特征向量矩阵，则$Z=\Lambda_{\*}^{\frac{1}{2}}V_{\*}^T \in R^{d^{\*}\times m}$现实中，仅需要降维后的距离与原始空间内的距离尽可能接近，不必严格相等。此时可取$d^{*}$远小于$d$求解。

MDS算法描述如下：

---

输入：距离矩阵$D\in R^{m\times m}$，其元素$dist_{ij}$为样本$x_i$到$x_j$的距离；低维空间维度$d^{‘}$

---

1 计算矩阵$B$
2 对$B$做特征值分解
3 取$\Lambda$为$d^{‘}$个最大特征值所构成的对角矩阵，$V$为相应的特征向量矩阵

---

输出：$Z=\Lambda^{\frac{1}{2}}V^T$，其中$Z$的每列对应一个样本的低维坐标

---

Logistic Regression

Logistic Regression的思想源于广义线性模型$y=g(\omega^Tx+b)$其中，函数$g()$称为联系函数。
逻辑回归中，联系函数其实sigmoid函数: $y=\frac{1}{1+e^{-z}}$其函数图如下：


令$z=\omega^T x $，所以$y=\frac{1}{1+e^{-(\omega^T x)}}$其中，（通过扩展训练数据将bias部分加入，就省去了bias部分）上式可以写成$ln\frac{y}{1-y}=\omega^T x$如果把$y$当作正样本的后验概率$p(y=1|x)$，那么$1-y$就是负样本的后验概率$p(y=0|x)$。所以有：

$$\begin{aligned} p(y=1|x) = \frac{e^{-(\omega^T x)}}{1+e^{-(\omega^T x)}} \\ p(y=0|x) = \frac{1}{1+e^{-(\omega^T x)}} \end{aligned}$$

我们通过极大似然法来估计$\omega$，给定数据集${(x_i,y_i)}_{i=1}^m$，对数似然函数可以写成：

$$\begin{aligned} l(\omega) &= ln\prod_{i=1}^m \left(\frac{e^{-\omega^T x_i}}{1+e^{-\omega^T x_i}}\right)^{y_i} \cdot \left(\frac{1}{1+e^{-\omega^T x_i}}\right)^{1-y_i} \\ &= \sum_{i=1}^m \left( y_i ln \frac{e^{-\omega^T x_i}}{1+e^{-\omega^T x_i}} + (1-y_i) ln \frac{1}{1+e^{-\omega^T x_i}} \right) \end{aligned}$$

这里使用经典的方法，$l(\omega)$对$\omega$求导，闭式解不好表示，所以可以使用梯度上升的方法表示，其中

$$\begin{aligned} \frac{dl(\omega)}{d\omega} &= \sum_{i=1}^m \left( y_ix_i-\frac{x_i e^{-\omega^T x_i}}{1+e^{-\omega^T x_i}} \right) \\ \omega &= \omega+\frac{dl(\omega)}{d\omega} \end{aligned}$$

将批量梯度下降转换成随机梯度下降有

$$\begin{aligned} & for\quad i\; \in \; \{1,2,...,m\} \\ & \quad\quad\omega = \omega+\alpha \cdot \left(y_i-\frac{e^{-\omega^T x_i}}{1+e^{-\omega^T x_i}} \right) \cdot x_i \end{aligned}$$

Generalized Linear Models

上面提到，广义线性模型的形式如下</b>$y=g(\omega^Tx+b)$联系线性回归、logistic回归。广义线性模型的训练，如果满足条件，其随机梯度下降的训练方法如下：

$$\begin{aligned} & for\quad i\; \in \; \{1,2,...,m\} \\ & \quad\quad\omega = \omega+\alpha \cdot \left(y_i-h_{\theta}(x_i) \right) \cdot x_i \end{aligned}$$

其中，$h_{\theta}(x) = g(\theta^Tx)$即是目标模型的形式.