如果真的要根據表格算某個 joint probability，會很花時間，所以有時候用採樣的會比較快

# Prior Sampling

根據表格內容逐次採樣。

根據網路的條件機率表，依照 topology 順序，依序去取樣，例如 R->T->S 的網路，首先根據 R 的機率採樣，然後看 R 的值是多少，在根據條件下的機率採樣 T，以此類推

只要採樣夠多，就會趨近於原本的機率，這樣子叫做 consistent。

這樣就可以直接根據採樣的結果知道各種情形的 joint 機率了。

# Reject Sampling

有時後我們只想求某種條件下的機率，例如 R ->T，如果我們只想知道當 R = true 條件下 t 的機率，那麼在採樣的時候一旦遇到 R = False 就可以直接丟棄了。

這種採樣可以適用很多很奇怪的情境，例如想採樣出只限制於 1 跟 -1 之間的 標準 Gaussian，他的標準型不容易寫出來，此時就可以直接用 reject 採樣出來。

# Likelihood Weighting

Reject sampling 的缺點是如果遇到機率很小的條件，或者說 evidence，就會丟掉很多次。

所以我們修正上面的 Prior 採樣，假如 R -> S -> T 我們想知道 S = true 的條件下的機率，一樣直接做 Prior 採樣，但是要採樣 S 的時候我們就直接令他為 S = true ，然後接著採樣 T。

但是這筆 Sample 要乘上一個權重，也就是 S = true 的機率，例如是 0.01。

你固定多少 evidence ，就要乘上他們的條件機率作為權重。

這樣就可以避免掉 Reject Sampling 遇到很多 reject 的問題。

缺點是

如果我們想固定的變數位於網路的下游，那麼有可能在 sample 的時候其實是碰不到該變數的，也因此導致才樣完後，大部分 sample example 的權重都是 少部分是有固定 evidence 的 example ，加上因為乘上了權重導致占比很小，實際算出來的效果就不會很好，或者說遇到這種情形就一樣要採樣很多次。

只有當要固定的 example 在上游的時候效果才會好，因為大家大概都會有權重；或者說權重可以很好的發揮作用。

# Gibbs Sampling

為了解決剛剛上游的問題。

第一步：固定 evidence。
第二步：為其他變數隨機的選定初始值。
第三步，隨機挑一個不是 evidence 的變數，然後以其他變數當前的值作為 evidence，根據這樣的條件機率做採樣。(或者說看他的父節點當前是哪些值，用那些值作為 evidence)

然要重複第三步，每一次都當作一個 sampling example，那麼只要夠多次，就會趨近原本的 distributin.

在第三步的時候，會需要去算給定其他變數值作為 evidence 的機率，才能採樣，而這個機率展開後可以消掉很多項，最終只有跟當前要採樣的變數有關的機率會留下來，這樣的計算量是可以負荷的。

:::info
其實 Gibbs 採樣算是 Markov chain Monte Carlo 採樣方法的一種特例
:::

:::warning
總結一下遇到的問題跟解決方法：
- Prior
- 可能會遇到機率太小的變數不好採樣出來
- 假如情況只需要知道某個特殊條件下的機率，就可以用 reject 採樣
- Reject
- 可能會拒絕太多次，如果想要適用不同情境也要重新採樣
- 改成乘上權重
- Likelihood Weighting
- 如果要有權重的變數在下游，那麼他的占比會很小
- Gibbs
- 終極版本，但是採樣時需要一點運算
:::

# Decision Network

希望有了貝氏網路後，可以做出決策。

## VPI

原本我們想求給定某個 evidence $e$ 的 MEU：

$$
MEU(e)=\max_{a}\sum_{s}P(s|e)U(s,a)
$$

$a$ 是我們的 actions，$s$ 是我們不知道情形的變數。

如果我們好奇，當我多知道新的 evidence $e'$，MEU 會變怎樣，所以我們可以算有了新 evidence 的 MEU：

$$
MEU(e,e')=\max_{a}\sum_{s}P(s|e,e')U(s,a)
$$

但是新的 evidence $e'$，他是某個變數 $E'$ 的某個可能結果，所以我們就算出所有 $E'$ 的可能結果的 MEU，在乘上在 $e$ 之下的條件機率作為權重，算出期望值：

$$
MEU(e,E')=\sum_{e'}P(e'|e)MEU(e,e')
$$

有了期望值後，我們可以看他跟原本的 MEU 差多少，就可以算出 VPI：

$$
VPI(E'|e)=\left(\sum_{e'}P(e'|e)MEU(e,e')\right)-MEU(e)
$$

## VPI 性質

1. 非負
2. 不可加
- 例如算出了知道 $E_j$ 或 $E_k$ 的 VPI，那麼兩者相加會代表同時知道兩個變數的 VPI 嗎
- 答案是不會的，因為有可能兩個變數之間是有關聯的，加權的部分就會不一樣
- 最簡單的例子是 $E_j=E_k$，此時 VPI應u該要是一樣的
3. 不分順序
- 想要算上面的 $V(E_j,E_k|e)$，要嘛先算出 $VPI(E_j|e)$ 在算出 $VPI(E_k|e,E_j)$
- 或是相反

## 直觀理解

例如你想知道待會要買哪張彩券：

如果你知道一件事情，跟你現在觀察到的事情無關，那麼 VPI 就是 0。
例如你知道了今天會不會出太陽，這跟你待會買彩券無關，所以知道會不會出太陽的 VPI 是 0。

這個結論也可以用上面的公式推導出來，因為計算 $MEU(e,e')$ 的時候，機率的獨立性讓條件機率跟沒有條件的機率是一樣的。

如果你知道了彩券號碼，那麼這個的 VPI 就超高。

# Markov model

## Stationary Distributions

最終會趨近一個分佈，所以一樣可以用採樣的方式來得到這個分佈。

## Web Link Analysis

我的推測，用戶的搜尋結果就是一次採樣，可以根據採樣的結果算出每個 page (state) 的分佈機率。

## HMM 更新算法

可以透過前一個 state 的 $B_t$ 跟變數的 transition 機率 $P(X_{t+1}|X_{t})$ 算出 $B'_{t+1}$。

$$
B'(X_{t+1})=\sum_{x_t} P(X_{t+1}|x_{t})B(x_t)
$$

然後 $B'_{t+1}$ 可以透過給定變數得 evidence 機率 $P(e_{t+1}|X_{t+1})$ 算出 $B_{t+1}$

$$
B(X_{t+1})\propto P(e_{t+1}|X_{t+1})B'_{t+1}(X_{t+1})
$$

每次更新不需要立即 normalize，可以直接透過

## Particle Filtering

上面 X 這個變數種類可能很多，不太可能每次真的都用上面的 forward 演算法去算，因為想要算的快的話一定不能用遞迴，但是要儲存的話就會特別龐大。

所以一樣可以採用取樣的方式去估計，當我想要知道 $P(X_{i})$，也就是是某個變數的機率時，就只要算採樣的點就可以知道了。

- 採樣方式就是先灑一堆球，或者說 particle
- 然後接下來每一部都是根據 transition 機率決定一顆球會走到哪個 $X_i$
- evidence 的機率會做為權重乘上去，因為下一次抵達的 $P(X_{i})$ 會正比於 前一次的 $P(e|X)$。
- 根據上面的結論。
- 有了權重，以及新移動的位子，會直接搭配權重，看某個 $X_i$ 有多少球來計算新的機率，重新灑球，然後重複上面的過程
- 灑求的數量可以隨模擬的次數遞減