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

簡(jiǎn)單分布的采樣，如均勻分布、高斯分布、Gamma分布等，在計(jì)算機(jī)中都已經(jīng)實(shí)現(xiàn)，但是對(duì)于復(fù)雜問(wèn)題的采樣，就需要采取一些策略， 拒絕采樣就是一種基本的采樣策略，其采樣過(guò)程如下：

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

所以使用接受-拒絕采樣可以得到采樣的概率分布。拒絕采樣的目的就是在每個(gè)采樣點(diǎn)用一個(gè)拒絕分布來(lái)包含接受分布，通過(guò)計(jì)算接受概率來(lái)表示采樣的分布。從而在隨機(jī)游走的過(guò)程中用接受-拒絕采樣得到復(fù)雜分布，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

責(zé)任編輯：haq