0%

ML-Basics Recap-软核

软核机器学习,记录结论和性质,推导细节省略。

所有向量默认是列向量。

零、Basics

Sum Rule:

Product Rule:

Chain Rule:

Bayesian Rule:

观测数据$X = {\cdots, x_i, \cdots}$, 标签$Y = {\cdots, y_i, \cdots}$,隐变量$Z = {\cdots, z_i, \cdots}$

生成模型:能够以某种方式估计到观测数据的分布,比如计算联合分布或者边缘分布来求解参数。

判别模型:无法获取观测数据的分布,只能估计条件分布$p(y|x)$。

一、线性模型

线性回归

线性回归模型使用最小二乘法等价于噪声为一维)的极大似然估计。

正则化和MAP的类似性:如果权重服从先验,那么利用MAP极大后验估计的结果类似于MLE增加L2正则项;而如果权重服从Laplace分布,那么类似于增加L1正则项。

线性分类

1.硬分类(直接得到类别)

感知机:线性回归的基础上增加不可导的激活函数,没有解析解,使用梯度下降求解。

线性判别分析:将样本投影到一条向量上,并使得类内聚合、类间分开。

2.软分类(得到分类概率)

判别式

logistic回归:线性回归增加激活函数,MLE作为目标函数,使用梯度下降求解。

生成式

高斯判别分析:假设从两个方差相同的正态分布中采样,代表样本属于哪个正态分布。通过贝叶斯公式,最大化以下先验的联合概率求解:,包含四个参数。推断时利用条件概率进行推断。

朴素贝叶斯:对于属性之间增加了独立性假设,使得后验分布能够按照维度分解。

二、指数族分布

具有如下形式概率密度函数的分布:。其中是参数向量,

充分统计量:,能够表述样本的统计性质。

对数配分函数:,因为转换为的形式的时候,

对数配分函数的性质:

极大似然估计的性质:,令导数为0可得。因此MLE对指数族分布来说只需要保留样本的充分统计量即可优化。

从最大熵的角度:1.没有已知信息的时候熵最大出现在均匀分布下。2.在有一个样本集合的情况下,利用经验分布和最大熵原理,最终得到的分布一定是指数族分布,而且能够得到其PDF的形式。

一维高斯分布

对于具有参数的一维高斯分布,转换为指数族分布的形式后,指数族的参数可以求出来:

充分统计量:。对数配分函数的形式略复杂。

三、支持向量机(SVM)

主要关注点:间隔,对偶,核技巧。

分类:硬间隔(hard-margin),软间隔,kernel SVM。

用来解决二分类问题,其模型和感知机相同$f(x;w) = sign(w^Tx + b)$,属于线性分类模型中的硬分类模型。

1.最大间隔分类器

对于属于两个类别的的数据样本,求解使得,也就是要正确划分。并满足如下的最大间隔:

那么存在一个正数等于这些样本到分类超平面的最小距离,那么上面的间隔约束可以转化为,可以约束为1,这个约束变成了。且满足

$\gamma$为什么可以取值为1?1)$aw^Tx + ab = 0$与$w^Tx + b = 0$是同一个超平面,2)且同一个向量到这两个超平面的距离相同。

所以可以用$\gamma$来缩放$w,b$使得$\gamma=w^Tx = 1$。

2.优化问题的转化。

拉格朗日乘子法,将上面的有约束优化问题转化为无约束优化问题(两者实际上可以证明是等价的):

对这个先min再max的原始优化问题,有一个对偶形式(先max再min)的问题,这个对偶形式总是原问题的(弱对偶关系),而在当前的原始问题下这两个问题是等价的()「满足KKT条件」:

这个对偶问题比原始问题更容易求解。

然后从里到外推偏导数等于0的公式,推推推,得到了的形式,w和b都被约去了。还有两个约束

3.优化问题的求解。

根据上面的最优化问题可以求出的值。然后就求出了参数的最优解析

其中是w的最佳值。b的最佳值如下,其中是支持向量,距离超平面距离为1。

这样就求解出了硬间隔SVM。

四、概率图模型(PGM)

什么样的方法可以转化为PGM?概率图又是如何得到的?

高维随机变量的困难:联合概率计算复杂。

Naive Bayes:增加维度独立的假设进行简化。这样就可以方便的计算后验分布。但是这个假设过强。(样本x的第3维特征是年龄,第8维特征是收入,就无法独立)

Markov假设:并没有要求每个维度完全独立,而是第i个维度从依赖前i-1个维度变成只依赖第i-1个维度。但是这样顺序性的依赖太单一。(比如收集的样本x的第3维特征刚好依赖于第5、6维特征,就不能满足这个假设)

条件独立性假设:只是假设把维度分为若干个集合,其中两个集合的特征在第三个集合被观测到的时候独立。比如划分出A、B、C三个集合:$A\bot B|C$。

1.概率图表示

  • 有向图
    • 离散:贝叶斯网络
    • 连续:高斯贝叶斯网络
  • 无向图
    • 离散:马尔科夫网络
    • 连续:高斯马尔科夫网络
有向图-贝叶斯网络

利用拓扑排序进行图的构造。那么根据构造了的有向图,就能够把高维随机变量的联合概率因子分解为条件概率和边缘概率的乘积。

对图的局部进行观察,会发现几种特殊的节点关系:

  • 1.从图上面看,某个节点上面若有tail-tail路径或者head-tail路径,那么当该节点事件发生时,这条路径被阻塞;间接相连的两个节点所代表的维度在这个条件下就是独立的。

  • 2.而如果存在head-head路径(该节点C同时依赖于另外两个维度的变量A、B),那么刚好相反,如果C不发生那么A和B独立;反之路径连通,A和B不独立。

  • 3.另一种特殊的局部拓扑,两个节点A、B同时指向节点C,节点C又指向节点D,那么若节点D被观测到,那么节点A和B也是连通的,就不独立了。

D划分:一种划分特征节点构成的图的方式,对于划分出来的集合A、B、C,要满足。那么C中所有的点都要是上面这几种关系中第一种关系中的特殊节点。D划分可以应用在bayes定理,用来计算,计算的结果只涉及到,这两个集合中的节点叫做Markov blanket(马尔科夫毯)。

模型:

  • 单一,朴素贝叶斯:,体现在图上就是y和构成tail-to-tail的子图。
  • 混合,GMM(Gaussian Mixture Model),隐变量z表示聚类的类别,
  • 时间,马尔科夫链和高斯过程。
  • 动态系统,{HMM,LDS,粒子滤波}。
  • 连续,高斯贝叶斯网络。
无向图-马尔科夫网络

无向图组成的网络,适用于离散多维变量。

  • Global Markov:根据无向图找到具有条件独立性的三个节点集合。
  • Local Markov:一个节点a,节点集合N,邻居节点集合
  • 成对 Markov:不相连的两个节点在其他节点被观测时独立。

团和最大团:图中若干节点的集合,其中任意两个节点都互相连通。最大团就是节点最多再也无法添加时的团。

那么就可以利用团的概念把因子分解成:

其中称为势函数大于0,最终的分布的形式叫做Gibbs分布。这个分布的形式和指数族分布一致,也就满足了样本集合的最大熵原理。

2.概率图推断

已知概率图、参数和观测样本,推测未知变量的分布。比如计算联合概率、条件概率或者是极大后验估计。

  • 精确推断
    • 变量消除Variable Elimination
    • 信念传播Belief Propagation
    • Junction Tree
  • 近似推断
    • Loop Belief
    • Monte Carlo采样:重要性采样、MCMC
    • 确定性近似(变分推断)
变量消除

已知一个概率图,求某个变量d的边缘概率,也就是对其他所有变量做求和/积分:。首先根据概率图对联合概率进行因子分解,分解之后逐步求积分。(从依赖的发起节点开始),比如。其实也就是先对内部求和/求积分,再把求得的概率函数和外部的其他部分相乘。

缺点就是会有很多重复计算的部分,还有就是在图的计算中很难选择最优的消除次序,可能会导致消除的时间复杂度很高。

信念传播

无向无环图

对于上面这种图(无向无环),定义,这可以认为是把从C到B的路径上的依赖C约掉,只保留B的部分,那么可以这样求

  • 首先写出四条边四个点因子分解式:

  • 求出,即消去b上游的所有依赖节点。

  • 最后得到了无向图节点j到i的信息传播的公式,以及i节点的边缘概率:

所以只要有即可计算边缘概率,对n条边的无向图来说遍历图求得2n个就可以计算任意的边缘概率了。其中的叫做节点i的belief。 这种变量消除+Cache的方法就是BP信念传播。流程见下图,其中搜集信息即递归计算入信息,分发信息即递归计算出信息。

信念传播

Max Product

Max Product可以看作是BP的一种改进。是Viterbi算法i的推广形式。

对于上面信念传播图中的图,首先我们明确一个概念,就是a、b、c、d都是随机变量,而信念传播是一种求它们边缘概率的方法。

那知道了这个图,假如说我希望求一个序列使得它们的联合概率最大要怎么办呢?可以稍微修改BP方法中m函数的定义为如下形式:

这样把sum改成max的意思就是,我消去变量j的方式从求和/积分,变成了求使得后面的部分最大化的j的值。

这实际上就是一种动态规划求最佳序列的方式,只是在图/树上求解,所以是Viterbi的一种推广。

势函数

势函数是来自物理中的一个概念。我们在无向图中,利用极大团来因子分解联合概率的时候引入了它,。实际应用中需要对势函数进行设计,并满足配分函数的求和/积分等于1。

道德图

将有向图转化为无向图的一种途径。需要特殊处理的只有head-2-head类型的结构,也就是对一个节点i,转化的时候需要将其所有的父亲节点两两互相连接。(有向树转化为无向图)

因子图

可以视为对有向图更精细的分解,而且分解之后的节点需要满足,其中是因子节点。

3.学习

  • 参数学习
  • 结构学习

五、EM算法

有隐变量情况下的参数估计算法。

1.收敛性

首先从MLE参数估计的公式,最大化观测数据x的似然概率:。可以证明这样求得的参数一定满足随着$t$越来越大$log p(x|\theta^t)$越来越大。

2.公式推导(KL + ELBO角度)

E步:根据当前隐变量z的后验分布,求出$E_{z|x} [log p(x,z|\theta)]$。

M步:根据当前的期望,用上一时刻的参数$\theta^t$从后验分布中采样z,优化参数$\theta$以最大化联合分布的期望

其中我们从KL + ELBO角度进行如下推导(有点像VAE的推导过程),首先对数似然变形,并引入一个隐变量的先验分布$q(z)$【因为$p(z|x)$不好求】:

$\log p(x|\theta) = \log p(x, z|\theta) - \log p(z|\theta) = \log \frac{p(x, z|\theta)}{q(z)} - \log \frac{p(z|\theta)}{q(z)}$。

然后对等式两边分别求$q(z)$的期望。左边等于不求。右边等于:

$\int_{z} q(z) \log \frac{p(x, z|\theta)}{q(z)}dz - \int_z q(z) \log \frac{p(z|\theta)}{q(z)}dz$。

也就是:$ELBO + KL(q(z)||p(z|x,\theta))$,第二项KL散度$\geq 0$,所以第一项也被称为ELBO证据下界。

那么,当KL散度等于0的时候,也就是$q(z) = p(z|x, \theta^t)$的时候,我们在M步做的事情是:

而由于此时的$\theta^t$是个常数,所以可以省略掉上面的式子中和$\theta$无关的部分,留下:$argmax_\theta \int_z p(z|x, \theta^t)\log p(x|\theta)dz$,也就是我们一开始写的那个与z的后验有关的联合分布期望。

3.公式推导(Jensen不等式角度)

Jensen不等式,concave函数的中点函数值$\geq$其两端连线直接在当前点的值。

首先从log likelihood开始,$\log p(x|\theta) = \log E_{q(z)}[\frac{p(x,z|\theta)}{q(z)}] $。

利用jensen不等式得到它 $\geq E_{q(z)}[\log\frac{p(x,z|\theta)}{q(z)}]$即ELBO。等式成立的情况下有$p(x,z|\theta) = c\cdot q(z)$,其中c是常数。这里经过推导,就可以得到$c == p(x|\theta)$,所以z的先验概率$q(z) = \frac{p(x,z|\theta)}{p(x|\theta)} = p(z|x, \theta)$,就等于后验概率。

EM实际上是为了生成模型估计参数,引入隐变量z来更新参数。

4.广义EM

log likelihood = ELBO + KL(q||p)。由此可以推广EM算法到其广义的形式。

E步,固定$\theta$求z的分布q使得$KL$最小或者$ELBO$最大;M步,固定$\hat q$求参数$\theta$去最大化ELBO也就是联合分布$E_q[\log p(x, z)] + H(q)$。

而原始的EM中分布q就等于后验$p(z|x)$。

六、变分推断(VI)

引言

频率角度->优化问题。(模型、策略、算法)

贝叶斯角度->积分问题。

  • 贝叶斯推断计算参数后验。(精确推断或者近似推断)
  • 贝叶斯决策,使用参数后验求期望。

公式推导

$x$: 观测数据,$z$:隐变量 + 参数,$(x, z)$完整数据。目标:找到一个变分分布$q(z)$,使得ELBO:$1: \mathcal{L}(z) = \int_z q(z) \frac{p(x,z)}{p(z)}dz$最大,也就是变分接近后验分布。

$q(z) = \prod_{i=1}^M q_i(z_i)$,假设z可以划分为M份互不相关的分量,那么可以因子分解为左边。然后固定其他所有分量求解分量$z_j$的话,1式可以变成:

再进行变换就得到$-KL(q_j||P(x, z_j))$。

经典变分推断的目标就是找到一个变分分布,可以最小化KL,最大化ELBO。然后每次固定M-1组,交替求解其中的一组隐变量。(坐标上升的思想),迭代求解直到$\mathcal{L}$不再下降。

但是这样做:1)平均场假设太强,2)intractable。

SGVI(Stochastic Gradient)

随机梯度变分推断利用梯度下降来计算变分分布的参数。

经过推导,ELBO对变分分布参数$\phi$的导数是:

能写成期望的形式意味着可以通过在q分布采样的方式计算下一轮的导数,也就是采样L个隐变量$z^{(l)}$,梯度约等于:

但是这样采样的方差很大,因为q很大和很小的时候对log q求期望差别很大。那如何降低方差呢?引入了重参数化技巧(即VAE中的那个,不仅仅可以处理不可微问题,而且可以减少方差)。找一个$\epsilon\sim p(\epsilon)$,这个p分布要尽量简单一点,然后保证得到的$\epsilon$可以用来采样$z$,也就是z可以通过现有后验分布的参数$\phi$和这个$\epsilon$进行简单的变换$g_\phi(\epsilon, x)$得到。然后进行一系列推导,最后得到的结论是这样采样$\epsilon$并计算$z$最终算出来的梯度就减少了方差。

举例:比如VAE里面$z$服从高斯分布,那么分布参数$\phi$就是均值$\mu$和方差$\sigma$,这时候这个$\epsilon$从标准高斯分布中采样,$g_\phi = \mu + \sigma * \epsilon$就可以得到服从$z$分布的隐变量。

得到了梯度之后,就可以利用梯度上升/下降对q分布的参数$\phi$进行参数优化了。

七、MCMC

采样方法介绍

蒙特卡洛方法是一种基于采样的随机近似方法,可以用来进行近似推断。

也就是把积分形式$\int p(z|x)f(z)dz$近似为$\frac{1}{N}\sum_{i=1}^N f(z_i)$。但是假如说后验分布比较复杂,怎么才能采样得到$z_i$呢?

  • 1)概率分布采样:计算机能够从均匀分布$U(0, 1)$中采样,如果能够根据z的分布的概率密度函数能够计算累计分布函数cdf,则可以根据cdf的逆函数将$o\sim U(0, 1)$作为逆函数输入进行采样,但是这也仅限于简单的分布。

  • 2)拒绝采样,引入一个提议分布$q(z)$和正整数$M$,保证处处都有$Mq(z)\geq p(z|x)$。那么对$z_i$可以计算出接受率$\alpha$,每次从$q(z)$中采样出一个点,从$U(0, 1)$中采样出一个$u$,如果$u \leq \alpha$那么接受当前采样,否则拒绝。

  • 3)重要性采样,从$q(z)$中采样,每个样本的权重等于$p$与$q$的比值,对两个分布的形式有要求否则采样效率低:

这些采样方法要求proposal distribution 和原始分布接近,且简单易于采样,这有时很困难。

MCMC

马尔科夫链:时间和状态都是离散的。为状态转移矩阵。

齐次(一阶)马氏链:

平稳分布:如有或者写成,则称的平稳分布,也就是最终的状态分布稳定了,状态$k$的概率值为。(对离散型随机变量)

细致平衡:,detailed balance是产生平稳分布的充分条件,其中$q (x)$表示取值为$x$的概率,$q$表示一个平稳分布。

MCMC采样:

  • 这组序列中,选择n个采样样本,其中到第m步马氏链形成了平稳分布。
  • 平稳分布接近或者等于目标分布,那么在平稳分布上采样就等价于在目标分布上采样了。
  • 关于能够到达平稳分布的证明:
    • 首先能够得到,也就是
    • 状态转移矩阵是一个随机矩阵,方阵 & 每一行之和等于1。它有一个性质即特征值,所以。(A是一个矩阵,其每一列以此是A的特征向量的分量。L是一个矩阵,其对角线依次是A的特征值;其他元素为0。)
    • 因此存在足够大的T,使得只有若干个元素为1(即Q本身为1的那些特征值)。此时,且,而,所以q形成了平稳分布。

Metropolis-Hastings:

  • 均匀分布中采样$u\sim U(0, 1)$,Q为proposal matrix可以由任意先验给出,,接受率
  • 如果,那么,否则
  • 这里的原理就是保证了最终得到的是平稳分布。
  • 在x是连续变量的情况下,转换矩阵Q变为核函数积分形式。
  • 问题:1)高维变量计算很慢,而且转移会被拒绝效率较低;2)在多维变量采样时可能面临联合分布难以计算的问题。

Gibbs采样:在采样第i维的时候,固定住其他维度不变。它需要知道每个维度在其他维度下的条件概率。

  • 比如对一个m维的变量,
  • MH采样中的在某一时刻对第i维度采样就等于,而就等于
  • 而且,因为某一个时刻采样i维的时候,是固定不变的,所以
  • 这样算出的接受率,也就是每个时刻都选择从中采样的值。

Tricks:

  • 通常多维变量采样Gibbs采样。
  • MH或者Gibbs采样的相邻样本之间是相关的,如果要求独立性,需要重新在生成的平稳序列下再次随机采样。
  • 关于“燃烧期”,即抛弃的不稳定的MC序列的长度,通常是经验性的判定,或者可以使用序列窗口的均值来判断是否平稳。

MCMC的问题:

  • 不能保证多少步收敛;
  • 如果p分布过于复杂或者维数很大,燃烧期可能很长(比如分布很陡峭、或者具有某些概率极低的低谷)
  • 样本之间有关联性,不符合采样的独立性原则。

HMC

参考

https://www.bilibili.com/video/BV1aE411o7qd

https://www.yuque.com/books/share/f4031f65-70c1-4909-ba01-c47c31398466