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

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

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) 信赖域

Importance sampling

MCMC

最优化信赖域( Nocedal chap4)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

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

Importance sampling

MCMC

最优化 信赖域( Nocedal chap4)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

最优化信赖域( Nocedal chap4)