蒙特·卡羅方法(Monte Carlo method)也稱統計模擬方法，通過重復隨機采樣模擬對象的概率與統計的問題，在物理、化學、經濟學和信息技術領域均具有廣泛應用。拒絕采樣(reject sampling)就是針對復雜問題的一種隨機采樣方法。 首先舉一個簡單的例子介紹Monte Carlo方法的思想。假設要估計圓周率 $\pi$ 的值，選取一個邊長為1的正方形，在正方形內作一個內切圓，那么我們可以計算得出，圓的面積與正方形面積之比為 $\pi/4$ 。現在在正方形內隨機生成大量的點，如圖1所示，落在圓形區域內的點標記為紅色，在圓形區域之外的點標記為藍色，那么圓形區域內的點的個數與所有點的個數之比，可以認為近似等于 $\pi/4$ 。因此，Monte Carlo方法是通過隨機采樣的方式，以頻率估計概率。

簡單分布的采樣，如均勻分布、高斯分布、Gamma分布等，在計算機中都已經實現，但是對于復雜問題的采樣，就需要采取一些策略， 拒絕采樣就是一種基本的采樣策略，其采樣過程如下：

給定一個概率分布 $p(z)=\dfrac{1}{Z_p}\tilde{p}(z)$ 其中 $\tilde{p}(z)$ 已知 $Z_p$ 為歸一化常數，是未知的。要對該分布進行拒絕采樣。首先定義一個參考分布 $G$ ，概率密度函數 $g(x)$ ，該分布可選均勻分布或高斯分布等。另外再定義一個輔助分布 $U(0,1)$ ，為均勻分布。然后引入常數 $k$ 使得對所有的 $z$ 滿足 $kg(z)\le\tilde{p}(z)$ ，然后開始進行采樣，在每次采樣中先從 $g(z)$ 中采樣一個 $z_0$ ，然后在區間 $[0, kg(z_0)]$ 里進行均勻采樣，得到 $u_0$ 。如果 $u_0<\tilde{p}(z_0)$ ，則接受，保留該采樣值，否則拒絕，舍棄該采樣值。最后得到的數據就是對該分布的一個近似采樣。

所以使用接受-拒絕采樣可以得到采樣的概率分布。拒絕采樣的目的就是在每個采樣點用一個拒絕分布來包含接受分布，通過計算接受概率來表示采樣的分布。從而在隨機游走的過程中用接受-拒絕采樣得到復雜分布，python代碼參考如下：

? def node2vec_walk2(self, walk_length, start_node):
? ? ? """
? ? ? Reference:
? ? ? KnightKing: A Fast Distributed Graph Random Walk Engine
? ? ? http://madsys.cs.tsinghua.edu.cn/publications/SOSP19-yang.pdf
? ? ? """

? ? ? def rejection_sample(inv_p, inv_q, nbrs_num):
? ? ? ? ? upper_bound = max(1.0, max(inv_p, inv_q))
? ? ? ? ? lower_bound = min(1.0, min(inv_p, inv_q))
? ? ? ? ? shatter = 0
? ? ? ? ? second_upper_bound = max(1.0, inv_q)
? ? ? ? ? if (inv_p > second_upper_bound):
? ? ? ? ? ? ? shatter = second_upper_bound / nbrs_num
? ? ? ? ? ? ? upper_bound = second_upper_bound + shatter
? ? ? ? ? return upper_bound, lower_bound, shatter

? ? ? G = self.G
? ? ? alias_nodes = self.alias_nodes
? ? ? inv_p = 1.0 / self.p
? ? ? inv_q = 1.0 / self.q
? ? ? walk = [start_node]
? ? ? while len(walk) < walk_length:
? ? ? ? ? cur = walk[-1]
? ? ? ? ? cur_nbrs = list(G.neighbors(cur))
? ? ? ? ? if len(cur_nbrs) > 0:
? ? ? ? ? ? ? if len(walk) == 1:
? ? ? ? ? ? ? ? walk.append(
? ? ? ? ? ? ? ? ? ? ? cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])])
? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? upper_bound, lower_bound, shatter = rejection_sample(
? ? ? ? ? ? ? ? ? ? ? inv_p, inv_q, len(cur_nbrs))
? ? ? ? ? ? ? ? ? prev = walk[-2]
? ? ? ? ? ? ? ? ? prev_nbrs = set(G.neighbors(prev))
? ? ? ? ? ? ? ? ? while True:
? ? ? ? ? ? ? ? ? ? ? prob = random.random() * upper_bound
? ? ? ? ? ? ? ? ? ? ? if (prob + shatter >= upper_bound):
? ? ? ? ? ? ? ? ? ? ? ? ? next_node = prev
? ? ? ? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? ? ? ? next_node = cur_nbrs[alias_sample(
? ? ? ? ? ? ? ? ? ? ? ? ? alias_nodes[cur][0], alias_nodes[cur][1])]
? ? ? ? ? ? ? ? ? ? ? if (prob < lower_bound):
? ? ? ? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? ? ? ? if (prob < inv_p and next_node == prev):
? ? ? ? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? ? ? ? _prob = 1.0 if next_node in prev_nbrs else inv_q
? ? ? ? ? ? ? ? ? ? ? if (prob < _prob):
? ? ? ? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? ? walk.append(next_node)
? ? ? ? ? else:
? ? ? ? ? ? ? break
? ? ? return walk

責任編輯：haq