# Sampling

> Organization contact [name= [ierosodin]([e-mail])]
###### tags: `deep learning` `學習筆記`

==[Back to Catalog](https://hackmd.io/@ierosodin/Deep_Learning)==

* From [cnblogs](https://read01.com/zLn6K.html)
* 重要性抽樣(Importance sampling)
* Importance Sampling 也是藉助了容易抽樣的分布 q (proposal distribution)來解決這個問題，直接從公式出發：
* 
* 其中，$\frac{p(z)}{q(z)}$ 可以看做 importance weight。我們來考察一下上面的式子，$p$ 和 $f$ 是確定的，我們要確定的是 $q$。要確定一個什麼樣的分布才會讓採樣的效果比較好呢？直觀的感覺是，樣本的方差越小期望收斂速率越快。比如一次採樣是 0, 一次採樣是 1000, 平均值是 500,這樣採樣效果很差，如果一次採樣是 499, 一次採樣是 501, 你說期望是 500,可信度還比較高。在上式中，我們目標是 $\frac{p×f}{q}$ 方差越小越好，所以 $|p×f|$ 大的地方，proposal distribution $q(z)$ 也應該大。舉個稍微極端的例子：
* 
* 第一個圖表示 $p$ 分布， 第二個圖的陰影區域 $f = 1$，非陰影區域 $f = 0$, 那麼一個良好的 $q$ 分布應該在左邊箭頭所指的區域有很高的分布機率，因為在其他區域的採樣計算實際上都是無效的。這表明 Importance Sampling 有可能比用原來的 $p$ 分布抽樣更加有效。
* 但是可惜的是，在高維空間裡找到一個這樣合適的 $q$ 非常難。即使有 Adaptive importance sampling 和 Sampling-Importance-Resampling(SIR) 的出現，要找到一個同時滿足 easy to sample 並且 good approximations 的 proposal distribution, it is often impossible！
* 馬爾科夫鏈，馬爾科夫穩態
* 在講蒙特卡洛方法之前，必須要先講一下馬爾科夫鏈；馬氏鏈的數學定義：
* 也就是說前一個狀態只與當前狀態有關，而與其他狀態無關，Markov Chain 體現的是狀態空間的轉換關係，下一個狀態只決定與當前的狀態(可以聯想網頁爬蟲原理，根據當前頁面的超連結訪問下一個網頁)。如下圖：
* 
* 舉一個例子，如果當前狀態為 $u(x) = (0.5, 0.2, 0.3)$, 那麼下一個矩陣的狀態就是 $u(x)T = (0.18, 0.64, 0.18)$, 依照這個轉換矩陣一直轉換下去，最後的系統就趨近於一個穩定狀態 $(0.22, 0.41, 0.37)$ (此處只保留了兩位有效數字)。而事實證明無論你從那個點出發，經過很長的 Markov Chain 之後都會匯集到這一點。
* 
* 這個馬氏鏈的收斂定理非常重要，所有的 MCMC(Markov Chain Monte Carlo) 方法都是以這個定理作為理論基礎的。
* 對於給定的機率分布 $p(x)$,我們希望能有便捷的方式生成它對應的樣本。由於馬氏鏈能收斂到平穩分布， 於是一個很的漂亮想法是：如果我們能構造一個轉移矩陣為P的馬氏鏈，使得該馬氏鏈的平穩分布恰好是 $p(x)$, 那麼我們從任何一個初始狀態 $x_0$ 齣發沿著馬氏鏈轉移, 得到一個轉移序列 $x_0,x_1,x_2,⋯x_n,x_{n+1}⋯$， 如果馬氏鏈在第 n 步已經收斂了，於是我們就得到了 $\pi(x)$ 的樣本 $x_n,x_{n+1}⋯$。
* 我們接下來介紹的MCMC 算法是 Metropolis 算法的一個改進變種，即常用的 Metropolis-Hastings 算法。由上一節的例子和定理我們看到了，馬氏鏈的收斂性質主要由轉移矩陣 $P$ 決定, 所以基於馬氏鏈做採樣的關鍵問題是如何構造轉移矩陣 $P,使得平穩分布恰好是我們要的分布 $p(x)$。如何能做到這一點呢？我們主要使用如下的定理。
* 
* 
* 
* 馬氏鏈轉移和接受機率
* 假設我們已經有一個轉移矩陣 $Q$ (對應元素為 $q(i,j)$), 把以上的過程整理一下，我們就得到了如下的用於採樣機率分布 $p(x)$ 的算法。
* 
* 
* 
* MCMC——Gibbs Sampling算法
* 
* 
* 平面上馬氏鏈轉移矩陣的構造
* 
* 
* 
* 
* 
* 以上算法收斂後，得到的就是機率分布 $p(x_1, x_2, ⋯, x_n)$ 的樣本，當然這些樣本並不獨立，但是我們此處要求的是採樣得到的樣本符合給定的機率分布，並不要求獨立。同樣的，在以上算法中，坐標軸輪換採樣不是必須的，可以在坐標軸輪換中引入隨機性，這時候轉移矩陣 $Q$ 中任何兩個點的轉移機率中就會包含坐標軸選擇的機率，而在通常的 Gibbs Sampling 算法中，坐標軸輪換是一個確定性的過程，也就是在給定時刻t，在一根固定的坐標軸上轉移的機率是1。
* 參考資料
* [1] http://blog.csdn.net/xianlingmao/article/details/7768833
* [2] http://www.cnblogs.com/daniel-D/p/3388724.html
* [3] http://cos.name/2013/01/lda-math-mcmc-and-gibbs-sampling/
* [4] An Introduction to MCMC for Machine Learning，2003
* [5] Introduction to Monte Carlo Methods