2019-11-22 采样方法(MCMC) 信赖域

作者: 苏格兰低地弟弟打滴滴 | 来源:发表于2019-11-22 09:12 被阅读0次

2019-11-22 采样方法(MCMC) 信赖域
技术积累
MCMC 采样
MCMC(一)蒙特卡罗方法
MCMC采样原理
贝叶斯模型与M-H采样
MCMC与Gibbs采样
MCMC把妹法
梯度优化算法
也谈MCMC方法与Gibbs抽样

Nocedal 4.0

gaol 2.5

采样的一个问题是，假如维度高了，我们想要采样到的点在高维中很小的区域，所以需要的样本点的个数指数增长。

Importance sampling

和前面不一样，我们不采样某个分布p，而是直接对 $\mathbb{E}[f]=\int f(\mathbf{z}) p(\mathbf{z}) \mathrm{d} \mathbf{z}$ 给出一个逼近。

如果符合p(x)分布的样本不太好生成，我们可以引入另一个分布q(x)，可以很方便地生成样本。使得

$\begin{aligned} \int_{x} f(x) p(x) d x &=\int_{x} f(x) \frac{p(x)}{q(x)} q(x) d x \\ &=\int_{x} g(x) q(x) d x \\ \text { where } g(x) &=f(x) \frac{p(x)}{q(x)}=f(x) w(x) \end{aligned}$

很多时候我们只有 $\begin{array}{l}{p(x)=\frac{\tilde{p}(x)}{Z_{p}}} \\ {q(x)=\frac{\tilde{q}(x)}{Z_{q}}}\end{array}$ 所以我们利用

$\begin{aligned} \int_{x} f(x) p(x) d x &=\int_{x} f(x) \frac{p(x)}{q(x)} q(x) d x \\ &=\int_{x} f(x) \frac{\tilde{p}(x) / Z_{p}}{\tilde{q}(x) / Z_{q}} q(x) d x \\ &=\frac{Z_{q}}{Z_{p}} \int_{x} f(x) \frac{\tilde{p}(x)}{\tilde{q}(x)} q(x) d x \\ &=\frac{Z_{q}}{Z_{p}} \int_{x} \tilde{g}(x) q(x) d x \end{aligned}$

其中 $\tilde{g}(x)=f(x) \frac{\tilde{p}(x)}{\tilde{q}(x)}=f(x) \tilde{w}(x)$ 是我们可以算的（知道精确表达式的）

但是现在问题是，就算我们可以从q采样，我们还是不能知道常数 $\frac{Z_{q}}{Z_{p}}$ ，但是他的倒数也可以写成蒙特卡洛的形式： $\frac{Z_{p}}{Z_{q}}=\int_{x} \frac{\tilde{p}(x)}{\tilde{q}(x)} q(x) d x=\int_{x} \tilde{w}(x) q(x) d x$

所以以下等式近似成立

$\frac{Z_{p}}{Z_{q}}=\frac{1}{m} \sum_{i=1}^{m} \tilde{w}\left(x_{i}\right) . \quad x_{i} \sim q$

所以结合以上： $E f(x)=\sum_{i=1}^{m} \hat{w}\left(x_{i}\right) f\left(x_{i}\right) \cdot x_{i} \sim q$ $\hat{w}\left(x_{i}\right)=\frac{\tilde{w}\left(x_{i}\right)}{\sum_{j=1}^{m} \tilde{w}\left(x_{j}\right)}$

我这的 $\frac{Z_{p}}{Z_{q}}$ 都不知道，怎么评估。🔺

同拒绝采样一样，这里如果q和p越接近，效果就越好。

这边有些关于graph model提出的进一步的方法没懂。看暂存\importance sampling 🔺

后面几个小节也还没看。🔺

MCMC

最优化信赖域( Nocedal chap4)

在每一步都用一个二次函数去近似目标函数 $m_{k}(p)=f_{k}+g_{k}^{T} p+\frac{1}{2} p^{T} B_{k} p$ 其中 $B_{k}$ 是一个对称矩阵。（ $m_{k}(p)$ 和 $f\left(x_{k}+p\right)$ 差大概是 $O\left(\|p\|^{2}\right)$ （注意不是小o））

🔺暂时还缺少对于 $B_k$ 选择的指导，如果取hessian就是信赖域牛顿法。

我们需要根据当前步骤的表现，来决定我们的 $\Delta_k$ 是大了还是小了。

每一步定义一个比值： $\rho_{k}=\frac{f\left(x_{k}\right)-f\left(x_{k}+p_{k}\right)}{m_{k}(0)-m_{k}\left(p_{k}\right)}=\frac{\text { Ared }_{k}}{\text { Pred }_{k}}$

因为我们的 $p_{k}$ 总是取让m最小的，所以分母肯定大于0（如果分母等于0会说明g=0，那就没什么好做了。）所以如果分子也大于0（ $\rho_{k}$ 大于0），那么说明我们做了下降的一步，如果 $\rho_{k}$ 很大，说明我们的m和f还match很好。如果 $\rho_{k}$ 小于0，说明我们搞反了。

所以如果我们的 $\rho_{k}$ 很接近1，我们就可以放心扩展信赖域大小到下一步。 $\rho_{k}$ 虽然大于0但是和1还是有距离的话，我们就不改变信赖域大小。如果小于0，那么就要缩小信赖域了。

如果信赖区域太小得话，就会错过可能存在的，朝着实质性方向前进的机会。

如果信赖区域太大得话，因为我们毕竟还是用一个二次函数去近似这个模型，所以可能会跟原来的模型有偏离。

最重要一个定理

🔺补充一下这里的证明。

🔺

2019-11-22 采样方法(MCMC) 信赖域
Nocedal 4.0 gaol 2.5 采样的一个问题是，假如维度高了，我们想要采样到的点在高维中很小的区域，所...
技术积累
数学基础 MCMC 采样 MCMC 采样一、机器学习 1、无监督学习聚类 Kmeans 聚类降维 PCA 理...
MCMC 采样
蒙特卡罗方法原理是通过大量随机样本，去了解一个系统，进而得到所要计算的值。概率分布采样如何基于概率分布去采样...
MCMC(一)蒙特卡罗方法
作为一种随机采样方法，马尔科夫链蒙特卡罗（Markov Chain Monte Carlo，以下简称MCMC）在机...
MCMC采样原理
为什么要引入采样原理？因为精确推断随着随机变量数目的增长在时间复杂度上呈现指数级的增长趋势。为了降低计算复杂度，...
贝叶斯模型与M-H采样
多次采样的直观理解相信这个词大家都不太陌生，而像现在的拒绝采样，蒙特卡洛采样，MCMC都是基于多次采样而来的。比...
MCMC与Gibbs采样
一、均匀随机数生成算法平方取中法将2s位十进制数字平方后取中间的2s位数字：但其长度较短且均匀性较差，针对性的改...
MCMC把妹法
声明：此方法建立在著名的马尔可夫链蒙特卡洛采样算法（MCMC）之上，并一改巴普诺夫把妹法和薛定谔把妹法的送餐设定，...
梯度优化算法
梯度下降，共轭梯度法；牛顿法，拟牛顿法；信赖域方法，罚函数法。
也谈MCMC方法与Gibbs抽样
原文传送门：也谈MCMC方法与Gibbs抽样 MCMC，即传说中的Markov Chain Mento Carlo...