---
title: "棄却サンプリング（棄却法）とは？Python実装と受容率1/M、Mの決め方・適応的棄却法"
url: "https://www.issoh.co.jp/tech/details/10503/"
published: 2026-01-07
updated: 2026-11-10
categories: ["AI"]
publisher: "株式会社一創"
---

# 棄却サンプリング（棄却法）とは？Python実装と受容率1/M、Mの決め方・適応的棄却法

棄却サンプリング（rejection sampling）は、直接は乱数を作れない確率分布から、乱数を作りやすい別の分布で候補を出し、その一部を捨てることでサンプルを得る方法です。棄却法、採択棄却法、受容・棄却法とも呼ばれ、どれも同じアルゴリズムを指します。

この記事では、手順と「捨てるだけで目標の分布になる理由」を押さえたうえで、NumPyでの実装、包絡定数Mを小さく取りすぎたときにどの区間が崩れるか、屋根を自動で作る適応的棄却サンプリング（ARS）の実装、高次元で使えなくなる理由を、2026年11月10日に手元で実行した数値（Python 3.12.13・NumPy 2.5.4・SciPy 1.18.1）で示します。後半では、SciPyとNumPyの内部の棄却法と、LLMの文脈で使われる「rejection sampling」の2つの意味も扱います。

## まとめ：棄却サンプリングの要点

- **手順**：提案分布q(x)から候補xを引き、一様乱数uが f(x) ÷ (M·q(x)) 以下なら受容、そうでなければ捨てる。すべてのxで f(x) ≤ M·q(x) が成り立つことが前提
- **受容率**：fが正規化済みなら1/M。Beta(2,5)を一様分布で包むとM=2.4576で受容率0.4069、実測0.4051
- **最大の落とし穴**：Mが小さすぎても、エラーは出ず受容率はむしろ上がる。Beta(2,5)でM=2.0にすると最頻値付近の0.1〜0.3の区間が約2ポイントずつ減り、KS検定のp値は10の−128乗まで落ちた
- **Mを手で決めない方法**：対数凹の密度なら適応的棄却サンプリング（ARS）が接線で屋根を作る。10万件の生成で密度の評価は初期接点を含めて145回、受容確率は0.9999まで上がった。実務ではSciPyのTransformedDensityRejectionを使う
- **使えない場面**：高次元で、提案分布とのずれによって包絡定数Mが極端に大きくなる場合。幅1.1倍の正規分布で包むだけでも、1000次元で受容率は10の−42乗になる。そこではMCMCを使う

## 棄却サンプリングの手順：提案分布q(x)と包絡定数Mによる受容判定

サンプルを得たい分布の密度をf(x)（目標分布）、乱数を簡単に作れる分布の密度をq(x)（提案分布）とします。最初に、すべてのxで f(x) ≤ M·q(x) となる定数Mを決めます。M·q(x)は目標の密度を上から覆う「屋根」で、包絡関数と呼ばれます。

1. 提案分布q(x)から候補xを1つ引く
2. 区間\[0, 1\]の一様乱数uを1つ引く
3. u ≤ f(x) ÷ (M·q(x)) なら、xをサンプルとして受容する
4. そうでなければxを捨てて、1に戻る

図で考えると、屋根M·q(x)の下に一様に点を打ち、目標の曲線f(x)より下に落ちた点のx座標だけを残す操作です。曲線の高いところほど点が残りやすいので、残った点はf(x)の形に沿って分布します。手法の原典は、ジョン・フォン・ノイマンの1951年の論文「Various techniques used in connection with random digits」とされます。

## 受容された点がf(x)に従う理由と受容率1/M

### 受容条件から目標分布が出てくる計算

候補が区間\[x, x+dx\]に入り、かつ受容される確率は、q(x)dx（その区間から候補が出る確率）と f(x) ÷ (M·q(x))（受容される確率）の積です。q(x)が約分されて f(x)dx ÷ M になります。全区間で足し合わせると、1回の試行で受容される確率は (∫f(x)dx) ÷ M です。fが正規化済みなら受容率は1/Mで、受容されたという条件のもとでのxの密度は (f(x) ÷ M) ÷ (1/M) = f(x) になります。

この計算から分かることは2つです。最初に受容されるまでの試行回数は成功確率1/Mの[幾何分布](/column/details/4358/)に従うので、サンプル1個に平均M回の試行が要ります。そして受容されたサンプル同士は独立で、MCMCのように前のサンプルに引きずられる相関は生じません。

### 正規化定数が分からない密度でも使える条件

受容判定には f(x) ÷ (M·q(x)) という比しか出てこないので、fを定数倍しても、Mを同じ倍率で調整すれば結果は変わりません。ベイズ推定の事後分布のように「尤度×事前分布」までは計算できても、積分して1にする正規化定数が分からない場面で使えるのはこのためです。

その場合、受容率は1/Mではなく Z ÷ M（Zは比例する関数fの積分）になります。f(x) = exp(−x⁴/4) を標準正規分布で包む例では、f÷qの最大値からM=3.2186、数値積分でZ=2.5637となり、受容率の理論値0.7965に対して100万回の実測は0.7967でした。受容されたサンプルの分散も0.6749で、数値積分で求めた0.6760と一致します。

## Pythonでの実装：一様分布からベータ分布Beta(2,5)を作る

例として、区間\[0, 1\]のベータ分布Beta(2,5)を、提案分布に一様分布U(0,1)を使って生成します。q(x)=1なので、Mはベータ密度の最大値そのものです。a>1かつb>1のとき、Beta(a,b)の最頻値は (a−1) ÷ (a+b−2) で、Beta(2,5)では0.2、そこでの密度は2.4576です。

### whileループによる最小実装

```
import numpy as np
from scipy import stats

rng = np.random.default_rng(42)
a, b = 2.0, 5.0
M = stats.beta.pdf(0.2, a, b)  # 最頻値 x=(a-1)/(a+b-2)=0.2 での密度 = 2.4576

def rejection_sample(n):
    samples, trials = [], 0
    while len(samples) < n:
        x = rng.random()          # 提案分布 q(x)=U(0,1) から候補
        u = rng.random()          # 判定用の一様乱数
        trials += 1
        if u * M <= stats.beta.pdf(x, a, b):  # u <= f(x) / (M q(x))
            samples.append(x)
    return np.array(samples), trials

s, trials = rejection_sample(10_000)
print(f"受容率 {len(s) / trials:.4f}（理論値 1/M = {1 / M:.4f}）")
```

実行結果は「受容率 0.4051（理論値 1/M = 0.4069）」です。ただしこの書き方は遅く、1万件の生成に5.4秒かかりました（Intel Core i9-9880H・macOS 26.6.2で3回測った中央値）。原因はループそのものより、scipy.stats.beta.pdf を1点ずつ呼ぶオーバーヘッドです。

### NumPyのベクトル化による100万件の生成

候補をまとめて配列で引き、受容判定もまとめて行うと速くなります（上のコードの rng・a・b・M をそのまま使います）。足りない分だけ追加で引くループにしておけば、件数はぴったりそろえられます。

```
def rejection_sample_vec(n, M=M):
    chunks, total = [], 0
    while total < n:
        k = int((n - total) * M * 1.1) + 10   # 受容率1/Mを見込んで多めに引く
        x = rng.random(k)
        u = rng.random(k)
        accepted = x[u * M <= stats.beta.pdf(x, a, b)]
        chunks.append(accepted)
        total += accepted.size
    return np.concatenate(chunks)[:n]

rng = np.random.default_rng(42)
s = rejection_sample_vec(1_000_000)
print(f"平均 {s.mean():.4f}（理論値 a/(a+b) = {a / (a + b):.4f}）")
print("KS検定のp値:", stats.kstest(s[:100_000], "beta", args=(a, b)).pvalue)
```

100万件の生成は1.05秒（3回の中央値）で、ループ版の1万件より速く終わります。平均は0.2860で理論値0.2857と一致し、10万件で行ったKS検定（標本が指定した分布に従うかを調べる検定）のp値は0.47でした。0.05を大きく上回るので、Beta(2,5)に従っていないという証拠は出ていません。実装を書いたら、ヒストグラムやKS検定で理論分布と突き合わせておくと、次の章のようなMの誤りに気づけます。

## Mの決め方と失敗パターン：包絡条件の違反による分布の歪み

### Mの過小設定による最頻値付近の密度の歪み

棄却サンプリングで最も見落とされやすいのが、Mが f(x) ÷ q(x) の最大値を下回るケースです。プログラムはエラーを出さずに動き、受容率もむしろ上がるので、見た目では異常に気づけません。Beta(2,5)で M=2.0 にすると（真の最大値は2.4576）、密度が2を超える区間、つまり定義域の約22.6%で屋根が曲線より低くなり、そこの山が平らに削られます。

上のベクトル化関数で100万件ずつ作り、区間ごとの割合を理論値と比べたのが次の表です。削られた0.1〜0.3の確率が、裾の区間へ押し出されています。

| 区間      | 理論値    | M=2.4576（正しい） | M=2.0（小さすぎ） |
| ------- | ------ | ------------- | ----------- |
| 0〜0.1   | 0.1143 | 0.1141        | 0.1233      |
| 0.1〜0.2 | 0.2304 | 0.2311        | 0.2145      |
| 0.2〜0.3 | 0.2352 | 0.2343        | 0.2151      |
| 0.3〜0.4 | 0.1869 | 0.1875        | 0.1968      |
| 0.4〜0.6 | 0.1923 | 0.1921        | 0.2064      |
| 0.6〜1.0 | 0.0410 | 0.0407        | 0.0439      |

候補200万回で比べると、M=2.0の受容率は0.4667、平均は0.2914（理論値0.2857）、受容した標本の先頭20万件のKS検定のp値は1.2×10の−128乗でした。逆にMを大きく取りすぎても分布は正しいままで、効率だけが落ちます。M=3.0の受容率は0.3338（理論値0.3333）、M=10.0では0.0997（理論値0.1000）でした。

### Mを確かめる手順と提案分布の条件

Mは、全域で f(x) ≤ M·q(x) が成り立つと確かめた値を使います。決め方は次の順で考えます。

- **解析的に求める**：f÷qを微分して最大値を出す。ベータ分布と一様分布なら最頻値での密度、正規分布とラプラス分布なら下の章の式
- **数値最適化は補助に使う**：f÷qを格子や最適化で調べる方法は、単峰であるなど形が分かっていて、無限区間の裾でf÷qが増えないことを確かめた場合に限る。格子の最大値に一定の割合を足せば安全という保証はなく、格子の間の鋭いピークや裾での発散は取りこぼす
- **実行時に検査する**：判定のたびに f(x) ÷ q(x) > M になった候補を数え、1件でも出たらMが足りないと判断する。ただし0件だったことは、包絡条件が全域で成り立つ証明にはならない

f÷qの最大値が無限大になる組み合わせ（例：裾の重いコーシー分布を正規分布で包む）では、どんなMでも包めません。提案分布は、目標分布の密度が正の範囲ではどこでも正で、f÷q が有界になるもの、つまり目標分布より速く0に近づかないものを選びます。

## 提案分布の選び方：正規分布をラプラス分布で包む例

受容率1/Mを上げるには、提案分布q(x)の形を目標分布に近づけます。標準正規分布を、乱数を作りやすいラプラス分布（両側指数分布・位置0・スケール1）で包む例では、f÷qの最大値はx=±1でとり、M=√(2e/π)=1.3155です。理論受容率0.7602に対し、100万回の実測は0.7603でした。

一様分布は区間の外に候補を出せないので、正規分布全体の提案には使えません。区間\[−4, 4\]に切断した正規分布（区間外の確率は約0.006%）なら一様分布で包めますが、受容率は0.3133にとどまります。裾まで含めて形が似ている提案分布ほどMが1に近づきます。提案分布を選ぶ条件を重要な順に並べると次のとおりです。

- 目標分布の密度が正の範囲でq(x)も正で、f(x) ÷ q(x) が有界であること。満たさないとMが存在しない
- 乱数生成と密度の評価が速いこと。逆関数法で作れる一様・指数・ラプラス・コーシー分布がよく使われる
- 形が目標分布に近く、Mが1に近いこと

## 適応的棄却サンプリング（ARS）：接線で屋根を自動で作る方法

### ARSの仕組み：接線の屋根・弦のsqueeze・評価点の追加

Mと提案分布を手で決める作業を省くのが、GilksとWildの適応的棄却サンプリング（adaptive rejection sampling、ARS）です。原典は「[Adaptive Rejection Sampling for Gibbs Sampling](https://hedibert.org/wp-content/uploads/2013/12/1992GilksWild.pdf)」（Applied Statistics、1992年、41巻2号、337〜348頁）で、対象は1変数の対数凹な密度、つまり h(x) = log f(x) が上に凸な分布です。正規分布、指数分布、a≥1かつb≥1のベータ分布などが当てはまります。

対数凹なら、h(x)の接線は必ずh(x)の上にあります。ARSはこの性質を使って、3つの部品で動きます。

- **屋根（上側包絡）**：いくつかの点で引いたh(x)の接線をつないだ折れ線。指数をとると区分的な指数関数になり、そのまま乱数を引ける
- **squeeze（下側包絡）**：隣り合う点のh(x)を結ぶ弦。候補がこの下に落ちたら、f(x)を評価せずに受容する
- **更新**：squeezeで判定できずf(x)を評価した点は、受容・棄却にかかわらず接点に加え、屋根とsqueezeを作り直す

棄却が起きた場所ほど接点が増えて屋根が曲線に張り付くので、使うほど受容率が1に近づき、f(x)の評価も減っていきます。

### Pythonでの最小実装と受容確率の推移

Beta(2,5)に比例する f(x) = x(1−x)⁴ を、接点0.05と0.5の2つから始めるARSで生成するコードです。分かりやすさを優先し、接線の傾きがちょうど0になる場合の処理は省いています。

```
import numpy as np

# 目標：f(x) = x(1-x)^4（Beta(2,5)に比例）。対数密度 h とその導関数 dh
h  = lambda x: np.log(x) + 4 * np.log1p(-x)
dh = lambda x: 1 / x - 4 / (1 - x)
LO, HI = 0.0, 1.0

def hull(xs, hx, d):
    """接線の交点zと、各区間の屋根の面積wを返す（h・dhは評価済みの値を使う）"""
    z = (hx[1:] - hx[:-1] - xs[1:] * d[1:] + xs[:-1] * d[:-1]) / (d[:-1] - d[1:])
    z = np.concatenate([[LO], z, [HI]])
    a, b = z[:-1], z[1:]
    w = np.exp(hx + d * (a - xs)) * np.expm1(d * (b - a)) / d   # ∫exp(接線)dx
    return z, w

def ars(n, xs=(0.05, 0.5), seed=0):
    rng = np.random.default_rng(seed)
    xs = np.array(xs, dtype=float)
    hx, d = h(xs), dh(xs)                                        # 初期接点だけ評価
    evals = len(xs)
    z, w = hull(xs, hx, d)
    out = []
    while len(out) < n:
        j = rng.choice(len(w), p=w / w.sum())                    # 屋根の区間を面積比で選ぶ
        x = z[j] + np.log1p(rng.random() * np.expm1(d[j] * (z[j+1] - z[j]))) / d[j]
        up = hx[j] + d[j] * (x - xs[j])                          # 屋根（対数）
        i = np.searchsorted(xs, x)
        low = -np.inf
        if 0 < i < len(xs):                                      # 弦によるsqueeze（対数）
            low = ((xs[i] - x) * hx[i-1] + (x - xs[i-1]) * hx[i]) / (xs[i] - xs[i-1])
        lw = np.log(rng.random())
        if lw <= low - up:                                       # squeezeの下：fを評価せずに受容
            out.append(x); continue
        hnew, dnew = h(x), dh(x)                                 # ここでだけ f を評価する
        evals += 1
        if lw <= hnew - up:
            out.append(x)
        xs = np.insert(xs, i, x)                                 # 評価した点は接点に加える
        hx = np.insert(hx, i, hnew)
        d = np.insert(d, i, dnew)
        z, w = hull(xs, hx, d)
    return np.array(out), evals, len(xs), (1 / 30) / w.sum()

s, evals, k, acc = ars(100_000)
print(f"f の評価 {evals} 回、接点 {k} 個、最終の受容確率 {acc:.4f}、平均 {s.mean():.4f}")
```

受容確率は「目標の面積1/30 ÷ 屋根の面積」で計算できます。接点の数ごとの値は次のとおりでした。

| 接点の数         | 受容確率   | そこまでの試行回数 |
| ------------ | ------ | --------- |
| 2（初期値）       | 0.6258 | 0         |
| 3            | 0.8595 | 2         |
| 10           | 0.9652 | 51        |
| 20           | 0.9929 | 177       |
| 145（10万件生成後） | 0.9999 | 100,042   |

10万件の生成でf(x)（対数密度h）を評価したのは、初期接点の2回を含めて145回でした。10万件のうち99,899件はsqueezeの判定だけで受容され、評価が要ったのはsqueezeを通らなかった143件だけです。評価済みの接点のhとh′は配列に持ち回し、屋根を作り直すときも再評価しません。KS検定のp値は0.29、平均は0.2863です。一様分布の提案で受容率0.4069だった同じ分布が、Mを一度も手で決めずにほぼ捨てずに作れています。f(x)の評価が重い場面、たとえばギブスサンプリングの中で条件付き分布から1点ずつ引く用途のために作られた手法です。

一方、対数凹でない分布（多峰の混合分布、裾の重いt分布など）では接線が曲線の下にもぐり、屋根になりません。そうした分布向けにはMetropolis法の受理判定を組み合わせたARMS（Gilks・Best・Tan、1995年）がありますが、出力はマルコフ連鎖になり独立性を失います。

## SciPy・NumPyの内部で使われている棄却法

### scipy.stats.sampling のTransformedDensityRejection

自前の密度から乱数を作るなら、ARSを手書きするより SciPy 1.8.0 で追加された [scipy.stats.sampling](https://docs.scipy.org/doc/scipy/reference/stats.sampling.html) を使うのが確実です。C言語の乱数生成ライブラリUNU.RANを使う仕組みで、その1つ[TransformedDensityRejection](https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.sampling.TransformedDensityRejection.html)（TDR）は、ARSの log を一般の変換Tに広げた手法です。変換後の密度T(f(x))が凹になる「T凹」な1変数・単峰の分布が対象で、変換のパラメータcの既定値は−0.5（T(x) = −1/√x）、c=0にすると T(x) = log(x) でARSと同じ対数凹の条件になります。pdfは正規化しなくてよく、導関数dpdfも渡します。

```
from scipy.stats.sampling import TransformedDensityRejection

class Beta25:
    # 正規化のための係数30を掛けない「比例するだけ」の密度でよい
    def pdf(self, x):
        return x * (1 - x) ** 4
    def dpdf(self, x):
        return (1 - x) ** 4 - 4 * x * (1 - x) ** 3

gen = TransformedDensityRejection(Beta25(), domain=(0, 1), random_state=1)
s = gen.rvs(1_000_000)
print("hat関数の面積:", gen.hat_area)            # 目標の面積は 1/30 = 0.0333...
print("squeeze/hat比:", gen.squeeze_hat_ratio)
```

hat関数の面積0.03340は目標の面積1/30=0.03333とほぼ同じで、受容率に直すと約99.8%です。squeezeがhatの99.3%を覆うので、ほとんどの候補はpdfを評価せずに受容されます。100万件の生成は0.10秒で、NumPyのrng.beta（0.13秒）と同じ水準でした（いずれも3回の中央値、初期化は0.0004秒）。1変数の単峰分布を自作するなら、まずこれを試します。scipy.stats.sampling には ratio-of-uniforms 法の SimpleRatioUniforms と RatioUniforms もあり、2026年11月時点の最新安定版 SciPy 1.18.1（2026年8月21日公開）でも棄却系のサンプラーとして載っています。

### NumPyの正規乱数・指数乱数はジッグラト法

NumPyの Generator が標準正規乱数と標準指数乱数を作るときのジッグラト法も、棄却法の変形です。密度の下を面積の等しい横長の長方形の積み重ねで覆い、乱数が長方形の内側に入ったときは密度を評価せずに返し、端や裾に落ちたときだけ判定や別処理をします。[NumPyのドキュメント](https://numpy.org/doc/stable/reference/random/new-or-different.html)には、正規・指数・ガンマの生成器が256段のジッグラト法を使うと書かれています。standard\_exponential は method=’inv’ を指定すると逆関数法に切り替わります。普段使っている rng.standard\_normal も、棄却サンプリングの工夫の上に成り立っています。

## 高次元の棄却サンプリング：一括受容による受容率の低下

多次元の分布を1つの提案分布でまとめて包み、全座標を一括で受容・棄却する使い方では、提案分布とのずれによって包絡定数Mが次元とともに増え、受容率が極端に低下することがあります。座標ごとに独立な分布なら1次元ずつ別々に棄却サンプリングすれば済みます。相関のある多変量正規分布のように、共分散行列の分解（NumPyのmultivariate\_normalはsvd・eigh・choleskyを選べる）や条件付き分布からの逐次生成で作れる分布もあり、依存があるから一括で包むしかないとは限りません。問題になるのは、そうした変換が使えず、一括で包んだときのMが大きくなる分布です。

理由は、各次元の屋根と曲線の比が少しでも1を超えると、その積が次元の数だけ掛け合わされるからです。d次元の標準正規分布を幅1.1倍の正規分布で包むと M=1.1のd乗、受容率は1.1の−d乗になります。

| 次元d  | \[−4,4\]のd乗に切断した正規分布を一様分布で包む | 標準正規分布を標準偏差1.1倍の正規分布で包む |
| ---- | ---------------------------- | ----------------------- |
| 1    | 0.313                        | 0.909                   |
| 5    | 0.00302（実測0.00299）           | ―                       |
| 10   | 9.1×10の−6乗                   | 0.386                   |
| 20   | 8.3×10の−11乗                  | ―                       |
| 100  | ―                            | 7.3×10の−5乗              |
| 1000 | ―                            | 4.0×10の−42乗             |

箱で包む場合の受容率は {√(2π)・\[Φ(4) − Φ(−4)\] ÷ 8} のd乗です（Φは標準正規分布の累積分布関数）。1次元の0.3133は、高さ1・幅8の箱の面積のうち、曲線exp(−x²/2)の下にある面積の割合にあたります。この割合が次元ごとに掛け合わされるため、20次元で10の−11乗台まで落ちます。ARSやTDRも1変数向けで、この問題は解決しません。数十次元を超える事後分布からサンプルを得たいなら、[MCMC（マルコフ連鎖モンテカルロ法）](/tech/details/10270/)を使います。

## MCMC・重要度サンプリング・逆関数法との使い分け

乱数を作りたい分布が決まったら、次の順で手法を選びます。

| 手法        | 得られるもの           | サンプル間の相関 | 向く次元  | 必要なもの      |
| --------- | ---------------- | -------- | ----- | ---------- |
| 逆関数法      | 目標分布に従うサンプル      | なし       | 1次元   | 累積分布関数の逆関数 |
| 棄却サンプリング  | 目標分布に従うサンプル      | なし       | 1〜数次元 | f÷qの上限M    |
| ARS・TDR   | 目標分布に従うサンプル      | なし       | 1次元   | 対数凹・T凹な密度  |
| 重要度サンプリング | 重み付きサンプル（期待値の推定） | なし       | 低〜中次元 | 重みf÷q      |
| MCMC      | 目標分布に従う系列        | あり       | 高次元   | 比例する密度のみ   |

- **累積分布関数の逆関数が書ける**なら逆関数法。捨てる候補はないが、速度は逆関数の評価コストに依存する
- **1変数で対数凹（T凹）**ならSciPyのTDR。Mを決めずに済み、上のBeta(2,5)では受容率が約99.8%だった
- **1〜数次元で、f÷qの上限が求まる**なら素の棄却サンプリング。独立なサンプルが正確に得られる
- **サンプルそのものではなく期待値が欲しい**なら重要度サンプリング。全候補を捨てずに重み f(x) ÷ q(x) を付けて平均するのでMが要らない。ただし重みのばらつきが大きいと推定が不安定になる
- **高次元、またはMが求まらない**ならMCMC。メトロポリス・ヘイスティングス法も提案と受容判定を使うが、判定に前の状態との比を使うため、サンプル間に相関が出る

どれも乱数で積分や期待値を求める[モンテカルロ法](/tech/details/15242/)の部品で、MCMCの土台である状態遷移の考え方は[マルコフ連鎖の解説](/tech/details/15219/)で扱っています。機械学習モデルの中にこうした推定を組み込む開発を外部に頼む場合は、当社の[機械学習モデル開発](/service/ai/machine-learning/)で要件整理から相談できます。

## LLMで使われる「棄却サンプリング」：投機的デコーディングとRejection Sampling fine-tuning

### 投機的デコーディングの受理判定は棄却法の変形

LLMの推論を速くする投機的デコーディング（speculative decoding）では、小さい下書きモデルが次のトークンを提案し、大きいモデルがそれを受理するか判定します。大きいモデルの分布をp、下書きモデルの分布をqとすると、提案されたトークンxを確率 min(1, p(x) ÷ q(x)) で受理し、棄却したときは max(0, p−q) を正規化した残差分布から引き直します。古典的な棄却サンプリングと違い、棄却しても必ず1トークンが確定し、それでも出力の分布はpと一致します。1回あたりの受理率は Σmin(p(x), q(x)) です。この方式を示したLeviathanらの論文「[Fast Inference from Transformers via Speculative Decoding](https://proceedings.mlr.press/v202/leviathan23a.html)」（ICML 2023）は、T5-XXLで出力を変えずに2〜3倍の高速化を報告しています。速くなる条件やllama.cpp・vLLMでの設定は[投機的デコーディングの解説](/tech/details/6948/)にまとめています。

```
import numpy as np

rng = np.random.default_rng(7)
p = np.array([0.50, 0.20, 0.15, 0.10, 0.05])  # 大きいモデルの次トークン分布
q = np.array([0.30, 0.30, 0.10, 0.25, 0.05])  # 小さい下書きモデルの分布

N = 1_000_000
x = rng.choice(5, N, p=q)                       # 下書きモデルが提案
accept = rng.random(N) <= np.minimum(1, p[x] / q[x])
residual = np.maximum(p - q, 0)
residual /= residual.sum()                      # 棄却時は残差分布から引き直す
out = x.copy()
out[~accept] = rng.choice(5, (~accept).sum(), p=residual)

print("受理率:", accept.mean(), "（理論値 Σmin(p,q) =", np.minimum(p, q).sum(), "）")
print("出力の分布:", np.round(np.bincount(out, minlength=5) / N, 4))
```

5語の語彙で動かすと、受理率0.7504（理論値0.75）、出力の分布は\[0.5001, 0.1998, 0.1502, 0.1004, 0.0495\]で、目標のpと一致しました。同じpとqで古典的な棄却サンプリングを使うと、Mはp÷qの最大値1.667、受容率は0.6になり、棄却のたびに下書きモデルを呼び直すことになります。

### Llama 2のRejection Sampling fine-tuning：best-of-K選抜による追加学習

LLMの学習の文脈で出てくる「rejection sampling」は、乱数生成とは意味が異なります。Meta社のLlama 2の論文（[arXiv:2307.09288](https://arxiv.org/abs/2307.09288)、2023年）では、1つのプロンプトに対してモデルからK個の出力を生成し、報酬モデルで最も良い出力を選んでファインチューニングに使う手法をRejection Sampling fine-tuningと呼んでいます。論文自身も、この再ランキングの考え方をBaiら（2022）と同じものと説明しています。分布を正確に再現するための判定はなく、実質は「K個から最良を1つ選ぶ（best-of-K）」選抜です。論文で「rejection sampling」が出てきたら、乱数生成の話か学習データの選抜の話かを最初に見分けてください。

## 棄却サンプリングのよくある質問

### 棄却法と採択棄却法、棄却サンプリングは違う手法ですか？

同じ手法です。英語のrejection sampling、acceptance-rejection method、rejection methodの訳語が分野ごとに分かれただけで、統計・機械学習では「棄却サンプリング」、乱数生成やシミュレーションの教科書では「棄却法」「採択棄却法」と書かれることが多いです。

### 受容率はどれくらいあれば実用的ですか？

決まった基準値はありません。1サンプルあたり平均M回の試行が要るので、「必要なサンプル数×M×1回あたりの候補生成と密度評価の時間」が許容時間に収まるかで判断します。収まらない場合は、提案分布を目標に近づけるか、逆関数法・SciPyのTransformedDensityRejection・MCMCへの切り替えを検討します。

### Mの値が分からないときはどうすればよいですか？

f÷qを微分するなどして、全域での上限を解析的に確かめるのが基本です。上限を保証できず、密度が1変数で対数凹（T凹）なら、屋根を自動で作るARSやSciPyのTransformedDensityRejectionが使えます。それ以外は逆関数法やMCMCを検討します。実行中に f(x) ÷ q(x) がMを超えた候補を数えればMの不足には気づけますが、0件でも安全の証明にはなりません。

### 離散分布にも棄却サンプリングは使えますか？

使えます。密度を確率質量関数に置き換えるだけで、手順も受容率1/Mの関係も同じです。上の投機的デコーディングの例も、5語の離散分布で動かしています。

### 正規化されていない事後分布からサンプルを得られますか？

f÷qの上限Mが求まる範囲なら得られます。受容判定は比だけで決まるため、尤度×事前分布のような比例する関数のまま使えます。事前分布と尤度の関係は[ベイズの定理の解説](/tech/details/15236/)を参照してください。パラメータが多く上限が求まらない場合はMCMCを使います。

## 関連記事

- [MCMC（マルコフ連鎖モンテカルロ法）とは？仕組み・MH法とHMCの違い・収束判定をPythonで解説](/tech/details/10270/)
- [モンテカルロ法とは？乱数で近似解を求める仕組みと誤差の見積もり・Python/Excelでの使い方](/tech/details/15242/)
- [マルコフ連鎖とは？仕組み・遷移行列・定常分布とAI実装での使いどころ](/tech/details/15219/)
- [Speculative Decoding（投機的デコーディング）とは？仕組みと速くなる条件、LM Studio・llama.cpp・vLLMでの設定](/tech/details/6948/)
- [ベイズの定理とは？公式の意味・具体例からナイーブベイズ実装まで](/tech/details/15236/)

---

出典: [棄却サンプリング（棄却法）とは？Python実装と受容率1/M、Mの決め方・適応的棄却法](<https://www.issoh.co.jp/tech/details/10503/>)（株式会社一創）
