거부 샘플링

수치 분석과 계산 통계에서 거부 샘플링은 분포로부터 관측치를 생성하는 데 사용되는 기본 기법이다.일반적으로 수용 거부 방법 또는 "수용 거부 알고리즘"이라고도 하며 정확한 시뮬레이션 방법의 일종이다.이 방법은 밀도가 있는 $\mathbb {R} ^{m}$ $\mathbb {R} ^{m}$ ${\$ 의 모든 분포에 대해 작동한다.

기각 표본 추출은 랜덤 변수를 한 차원 표본으로 추출하기 위해 2차원 데카르트 그래프의 균일하게 랜덤 표본을 추출할 수 있고, 표본들을 밀도함수의 그래프 아래 영역에 유지할 수 있다는 관측에 근거한다.^[1]^[2]^[3]이 속성은 N차원 함수로 확장될 수 있다는 점에 유의하십시오.

설명

거부 샘플링 뒤의 동기를 시각화하려면 큰 사각형 보드에 랜덤 변수의 밀도 함수를 그래프로 표시하고 다트를 던지는 것을 상상해 보십시오.다트가 보드 주위에 균일하게 분포되어 있다고 가정한다.이제 곡선 아래 영역 밖에 있는 다트를 모두 제거하십시오.나머지 다트는 곡선 아래 영역 내에서 균일하게 분포하며, 이들 다트의 x-포즈들은 랜덤 변수의 밀도에 따라 분포한다.곡선이 가장 높은 곳에 다트가 착륙할 여지가 가장 많아 확률밀도가 가장 크기 때문이다.

방금 설명한 시각화는 "제안 분포"가 균일한 경우(그 그래프가 직사각형임을 나타냄) 거부 샘플링의 특정 형태와 동일하다.일반적인 형태의 거부표본 추출은 보드가 반드시 직사각형이 아니라 우리가 표본으로 추출하는 방법을 알고 있는 (예를 들어 반전표본 사용) 제안 분포의 밀도에 따라 형성되며, 최소한 표본으로 추출하고자 하는 분포의 모든 점에서 높아서 이전의 불평등한 것으로 가정한다.특히 후자를 감싸고 있다. (그렇지 않으면, 우리가 표본으로 추출하고 싶은 곡선 영역의 부분은 도달하지 못할 것이다.)

거부 샘플링은 다음과 같이 동작한다.

제안 분포에서 x축의 점을 표본으로 추출한다.
제안 분포의 확률 밀도 함수의 최대 y 값까지 이 x 위치에 수직선을 그린다.
확률밀도함수의 0에서 최대값까지 이 선을 따라 균일하게 표본 추출.표본 값이 이 수직선에서 원하는 분포 값보다 크면 x-값을 기각하고 1단계로 돌아가십시오. 그렇지 않으면 x-값은 원하는 분포의 표본입니다.

이 알고리즘은 함수가 1에 통합되는지 여부에 관계없이 어떤 곡선 아래 면적에서 샘플링하는 데 사용할 수 있다.실제로 상수에 의한 함수의 스케일링은 샘플링된 x-포지션에 영향을 미치지 않는다.따라서 알고리즘을 사용하여 계산 통계에서 흔히 볼 수 있는 정규화 상수를 알 수 없는 분포로부터 표본을 추출할 수 있다.

이론

거부 샘플방식 방법은 확률밀도 $g(x)$ $g(x)$ 가 $y$ $g(x)$ {\ $displaystyle$ $g$ $(x)}$ 인 $제안$ 분포 Y ${\displaystyle$ $Y$ $}$ 을(를) 사용하여 $f(x)$ 임의 확률밀도함수 $f(x)$ ( $f(x)$ ) ${\$ $displaystyle$ f( $x)}$ 를 $x$ 갖는 대상 분포 X ${\displaystystyleg$ (x $)$ 에서 샘플방식 값을 생성한다 $g(x)$ $대신$ $Y$ $Y$ 에서 표본을 추출하고 $Y$ Y {\ $f(x)/(Mg(x))$ $Y}$ 에서 $y$ 표본을 추출하여 $X$ $확률$ $f(x)/(Mg(x))$ ( x $f(x)/(Mg(x))$ ) $f(x)/(Mg(x))$ / $f(x)/(Mg(x))$ ( $f(x)/(Mg(x))$ $f(x)/(Mg(x))$ ( x $f(x)/(Mg(x))$ ) ${\displaystyle f(x)/(Mg(x$ 액셀 값이 $될$ 때까지 $Y$ Y ${\displaystystyle$ Y $}$ 에서 표본을 추출할 수 있다는 생각이다.Pted.M{M\displaystyle}여기서 일정한 경우, 유한한 가능성 비율 f())/g()){\displaystyle f())())}에, 1<>를 충족시키면 반드시;M<>∞{1<\displaystyle을 말한다.M<, X{X\displaystyle}의 양육에 관해서 \infty}; 다른 말로, M≤ f())모든 Mg()){\displaystyle f())\leq Mg())}을 충족해야 한다. $x$ $x$ 의 값 $x$ 이 경우 $Y$ $Y$ 의 지원에는 $X$ $g(x)>0$ $g(x)>0$ $displaystyle X}$ 의 지원이 포함되어야 한다는 점에 유의하십시오 $g(x)>0$ $g(x)>0$ $f(x)>0$ $f(x)>0$ ( ) > $f(x)>0$ x $g(x)>0$ ) > 0 $(\displaystyle$ $g($ $x)0$

이 메서드의 유효성 검사는 봉투 원칙은:한 M감속()){Mg())\textstyle}의 부분 그래프에 대한 균일 시뮬레이션을 생산할 때(x, v=너 ⋅ Mg())한쌍이 모의){\textstyle(x,v=u\cdot Mg()))},.를 받아들인 것 유일한 쌍과 같은 그런 식으로<>이름())/(Mg())){\textstyle u<, f())(Mg()))}. produc $(x,v)$ 쌍 $(x,v)$ x $(x,v)$ , $(x,v)$ ) ${\displaystyle (x,v$ )}은 $($ 는) $f(x)$ ( $f(x)$ ) $f(x)$ 의 하위 그래프에 균일하게 $(x,v)$ 분포하므로 $f(x)$ , $f(x).$ f $f(x).$ ( x ) $f(x).$ . ${\displaystyle$ f $(x)$ 에서 시뮬레이션이 수행된다 $.$ $}$

즉, 충분한 반복실험을 통해 알고리즘이 원하는 $f(x)$ f $f(x)$ ( $f(x)$ ) $f(x)$ 로부터 샘플을 생성한다는 것을 의미한다 $f(x)$ 메트로폴리스 알고리즘과 같은 이 알고리즘에는 여러 가지 확장이 있다.

이 방법은 마르코프 체인 몬테카를로 알고리즘을 포함한 몬테카를로 기법의 일반 분야와 관련되는데, 이 알고리즘은 또한 대상 $f(x)$ f ( $f(x)$ $){\displaystyle$ f $(x)}$ 로부터 시뮬레이션을 얻기 위해 대리 분포를 사용한다 $f(x)$ 메트로폴리스 알고리즘과 같은 알고리즘의 기초를 형성한다.

무조건 합격 확률은 제안된 표본이 합격된 비율이다.

{\begin}\mathb {P} \좌측(U\leq {\frac {f(Y)}{Mg(Y)}}}\operatorname {E} \mathbf {1} _{\좌측[]U\leq {\frac {f(Y)}{Mg(Y)}}\오른쪽]\\[6pt]&=E\left[\operatorname {E} [\mathbf {1} _{\left[]U\leq {\frac {f(Y)}{Mg(Y)}}\right]} Y]\right]&({\text{by tower property }})\\[6pt]&=\operatorname {E} \left[\mathbb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}{\biggr  }Y\right)\right]\\[6pt]&=E\왼쪽[{\frac {f(Y)}{Mg(Y)}}}}}\오른쪽]&({\text{{\text{pr(U\leq u)=u,{\text{}}}}{{{{{{{{{{{{{}가 },1)에 균일 경우)\\[6pt]&=\int \limits _{y:g(y)>0}{\frac {f(y)}{Mg(y)}}g(y)\,dy\\[6pt]&={\frac {1}{M}}\int \limits _{y:g(y)>0}f(y)\,dy\\[6pt]&={\frac {1}{M}}&({\text{since support of }}Y{\text{ includes support of }}X)\end{aligned}}

여기서

U\sim \mathrm {Unif} (0,1)

~

U\sim \mathrm {Unif} (0,1)

U\sim \mathrm {Unif} (0,1)

U\sim \mathrm {Unif} (0,1)

(

U\sim \mathrm {Unif} (0,1)

, 1

U\sim \mathrm {Unif} (0,1)

)

U\sim \mathrm {Unif} (0,1)

및

y

y

{\displaystyle

y

}

의 값은 제안서

배포

Y

{\\displaystyle

Y}의

g(\cdot )

밀도

g(\cdot )

g (

g(\cdot )

)

g(\cdot )

{\

displaysty

y

}

에 따라 생성된다

Y

따라서 $Y$ 값을얻기 $위해$ Y {\displaystyle $Y}$ 에서 필요한 샘플 수는 $평균$ M $M$ 을(를) 갖는 $1/M$ 1 $1/M$ / $1/M$ ${\displaystyle$ 1 $/M}$ 의 기하학적 분포를 따른다 $M$ 직관적으로 $M$ ${\displaystytle M}$ 은 $m$ co의 측도로서 필요한 반복의 예상 수입니다.알고리즘의 mputical 복잡성.

위의 방정식을 다시 쓰세요,

M={\frac {1}{\\mathb {P} \left(U\leq {\frac {f(Y)}{Mg(Y)}}}\오른쪽)}}

1≤ M<>∞{1\leq M<, \infty\textstyle}, 위의 공식 때문에, P(U≤ f(Y)Mg(Y)){\textstyle \mathbb{P}\left(U\leq{\frac{f(Y)}{Mg(Y)}}\right)}, 이는 간격에서 값을 취할 수 있는 확률[0,1]c{\displaystyle[0,1]}. M{M\displaystyle}은 있다는 점에 유의하십시오HOSE의 복수형

M

M

이

M

(

{\textstyle f(x)/g(x)}

) 우도비

{\textstyle f(x)/g(x)}

( x

{\textstyle f(x)/g(x)}

) /

{\textstyle f(x)/g(x)}

(

{\textstyle f(x)/g(x)}

)

{\textstyle f(x)/g(x)}

에 대한 상한이기 때문에 무조건 합격 확률이 높을수록 높으며

{\textstyle f(x)/g(x)}

실제로는 1에 가까운

M

M

M

의 값이 평균적으로 거부된 샘플 수를 더 적게 의미하기 때문에 선호된다.따라서 알고리즘의 반복 횟수가 줄어든다.이러한 의미에서 사람들은

M

한 한

M

M

{\

displaystyle M

}

을(를) 작게(

f(x)\leq Mg(x)

도 f

f(x)\leq Mg(x)

)

f(x)\leq Mg(x)

f(x)\leq Mg(x)

f(x)\leq Mg(x)

(

f(x)\leq Mg(x)

f(x)\leq Mg(x)

{\displaystyle

f

g(x)

x)\leq Mg(x)}

을(를) 만족시키는 반면

f(x)\leq Mg(x)

M

{\displaystystyle g

(x

)}

은

g(x)

으로

f(x)

f(x)

(

)

를 닮아야 한다는

g(x)

것을 선호한다.그러나

M

M

이(가) 1과 같을 수 없다는

M

것은

f(x)=g(x)

(

f(x)=g(x)

)

f(x)=g(x)

= g

f(x)=g(x)

(

f(x)=g(x)

)

{\displaystyle f(x)=g(x)},

즉 대상 분포와 제안 분포가 실제로 동일한 분포임을 의미한다.

기각 샘플링은 $f(x)$ ( $f(x)$ ) $f(x)$ 의 형태가 샘플링을 어렵게 하는 $f(x)$ 경우에 가장 많이 사용된다.거부 알고리즘의 단일 반복은 제안 분포에서 추출하고, 균일한 분포에서 도출하며, $f(x)/(Mg(x))$ ( $f(x)/(Mg(x))$ ) $f(x)/(Mg(x))$ / $f(x)/(Mg(x))$ ( $f(x)/(Mg(x))$ $f(x)/(Mg(x))$ ( x $f(x)/(Mg(x))$ ) ${\displaystyle f(x)/(Mg(x)})$ 식을 $f(x)/(Mg(x))$ 평가해야 한다.따라서 거부 샘플링은 M이 이러한 운영 비용(거부 샘플링이 있는 샘플을 얻는 예상 비용)을 곱할 때마다 다른 방법을 사용하는 샘플링 비용보다 더 낮을 때마다 일부 다른 방법보다 더 효율적이다.

알고리즘.

농도 $g$ 가{\ $displaystyle$ 인 $y$ 분포 $Y$ $Y$ 에서 표본을 사용하여 $f$ 분포 $X$ $f$ 의 $x$ 분포 $X$ ${\displaystyle$ 에서 표본을 얻기 위한 알고리즘은 다음과 $g$ 같다.

분포 $Y$ $Y$ 에서 $y$ $샘플$ y $y$ 을 $Y$ (를) 얻고 $\mathrm {Unif} (0,1)$ ( $0$ , 1) ${\displaystyle$ $u}$ 을 $u$ (를) $Unif}$ 에서 샘플 $u$ ${\displaystyle$ u}을(단위 간격에 걸쳐 균일한 분포) 얻으십시오. $\mathrm {Unif} (0,1)$
${\textstyle u<f(y)/Mg(y)}$ < ${\textstyle u<f(y)/Mg(y)}$ ( ${\textstyle u<f(y)/Mg(y)}$ ) ${\textstyle u<f(y)/Mg(y)}$ / ${\textstyle u<f(y)/Mg(y)}$ g ${\textstyle u<f(y)/Mg(y)}$ ( ${\textstyle u<f(y)/Mg(y)}$ ) ${\textstyle u<f(y)/Mg(y)}$ 의 여부를 확인하십시오 ${\textstyle u<f(y)/Mg(y)}$
- 이 값이 유지되면 $y$ $y$ 을(를) $f$ $f$ 에서 추출한 샘플로 $y$ 받아들이십시오 $f$
- $그렇지$ 않으면 y $y$ 값을 거부하고 샘플링 $y$ 단계로 돌아가십시오.

알고리즘은 샘플을 얻으려면 평균 $M$ ${\displaystyle$ M $}번$ 반복이 $M$ 필요하다.

순진한 방법을 사용한 샘플링에 대한 장점

거부 샘플링은 어떤 상황에서 순진한 방법에 비해 훨씬 더 효율적일 수 있다.For example, given a problem as sampling ${\textstyle X\sim F(\cdot )}$ conditionally on $X$ given the set $A$ , i.e., ${\textstyle X X\in A}$ , sometimes ${\textstyle X}$ can be easily simulated, using the naive methods (e.g. by inverse transform sampling):

${\textstyle X\sim F(\cdot )}$ ${\textstyle X\sim F(\cdot )}$ ~ F ( ${\textstyle X\sim F(\cdot )}$ ) ${\textstyle X\sim$ F $(\cdot )}$ 을(를) 독립적으로 ${\textstyle X\sim F(\cdot )}$ 사용하고 $\{n\geq 1:X_{n}\in A\}$ { $\{n\geq 1:X_{n}\in A\}$ $\{n\geq 1:X_{n}\in A\}$ 1 $\{n\geq 1:X_{n}\in A\}$ : X $\{n\geq 1:X_{n}\in A\}$ $\{n\geq 1:X_{n}\in A\}$ $\{n\geq 1:X_{n}\in A\}$ } ${\displaystyle \{n\geq 1:X_{n}\in$ A $\}}}}}}$ 에 만족하는 사람은 그대로 두십시오.
출력: $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ { $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ , $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ , $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ . $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ . $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ , $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ : $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ A $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ , $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ = $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ 1 $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ , . . $\{X_{1},X_{2},...,X_{N}:X_{i}\in A,i=1,...,N\}$ . . $}$ {\ $displaystyle \{X_{$ 1}, $X_{$ 2}, $X_{N$ },X_{N},X $:X_{i}\in,i=1,...$ $,N\}}$

문제는 ${\textstyle \mathbb {P} (X\in A)\approx 0}$ X ${\textstyle \mathbb {P} (X\in A)\approx 0}$ ${\textstyle \mathbb {P} (X\in A)\approx 0}$ ) ${\textstyle \mathbb {P} (X\in A)\approx 0}$ 0 ${\textstyle \mathb {P}(X\in A)\$ 약 $0$ 일 경우 이 샘플링이 어렵고 비효율적일 수 있다는 점이다.예상 반복 횟수는 ${\frac {1}{\mathbb {P} (X\in A)}}$ ${\frac {1}{\mathbb {P} (X\in A)}}$ A ${\frac {1}{\mathbb {P} (X\in A)}}$ ) ${\$ 이며 ${\frac {1}{\mathbb {P} (X\in A)}}$ 무한대에 가까울 수 있다.더욱이 Reject 샘플링 방법을 적용할 경우에도 항상 우도비에 대해 $M$ 바운드 $M$ $M$ 을(를) 최적화하기 어렵다. $대개$ M $M$ 은 $M$ (는) 크고 거부율이 높기 때문에 알고리즘이 매우 비효율적일 수 있다.지수 기울기라고도 알려진 자연 지수 패밀리(존재하는 경우)는 계산 복잡성을 낮추고 $M$ 값 $M$ 을 $M$ (를) 낮추고 계산 속도를 높일 수 있는 제안 분포의 클래스를 제공한다(예: 자연 지수 패밀리와의 작업 참조).

예제: 자연 지수 패밀리 작업

랜덤 변수 $X\sim F(\cdot )$ ~ F ( $X\sim F(\cdot )$ ) ${\displaystyle$ X $\sim$ F $(\cdot )},$ $F(x)=\mathbb {P} (X\leq x)$ ( x $F(x)=\mathbb {P} (X\leq x)$ ) $F(x)=\mathbb {P} (X\leq x)$ = P $F(x)=\mathbb {P} (X\leq x)$ ( $F(x)=\mathbb {P} (X\leq x)$ $F(x)=\mathbb {P} (X\leq x)$ $F(x)=\mathbb {P} (X\leq x)$ ) ${\displaystyle F(x)=\mathb {P}(X\leq$ x $)}$ 이 대상 분포다 $F(x)=\mathbb {P} (X\leq x)$ .단순성을 위해 밀도 함수를 $f(x)$ $f(x)$ ) $f(x)$ 로 명시적으로 작성할 수 있다고 가정하고 $f(x)$ 제안서를 다음과 같이 선택하십시오.

{\reasoned}F_{\theta }(x)&=\mathb {E} \left[\exp(\theta X-\psi(\theta ))\mathb {I}(X\leq x)\right]\\\&=\int _{-\int _{-\int _{-\x}e^{\theta y-\pa (\theta )}f(y)dy\\\g_{\ta }(x)&.=F'_{\theta }(x)=e^{\theta x-\psi(\theta )}f(x)\ended}}}

어디 ψ(θ)=log⁡(E지수 함수 ⁡(θ X)){\displaystyle\psi(\theta)=\log \left(\mathbb{E}\exp(\theta X)\right)}과 Θ){θ:ψ(θ)<>∞}{\displaystyle\Theta =\{\theta:\psi(\theta)<,\infty)}}. 분명히,{Fθ(⋅)}θ∈ Θ{\displaystyle\와 같이{F_{\theta}(\cdot)\}_{\in \Theta\theta}}, a로부터는natur기하급수적인 가족더욱이 우도비율은

Z(x)={\frac {f(x)}{g_{\theta }}}}{\frac {f(x)}{e^{\teta x-\psi(\teta )}f(x)}}}=e^{-\ta x+\psi(\ta)}}}}}}}}

참고;∞{\displaystyle \psi(\theta)<,\infty}실제 통나무 moment-generation 기능, 그것은,ψ(θ)=log⁡ Eexp ⁡(t=θ=log⁡ MX(t)t)θ{\displaystyle\psi(\theta)=\log \mathbb{E}{\exp(tX)}_{t=\theta}=\log M_ᆴ(t)_{t=\theta}}. 그리고ea 있음을 암시한다.(θ)<>ψ.sy에제안의 로그 모멘트 생성 기능을 도출하고, 따라서 제안의 순간을 도출한다.

{\begin{aligned}\psi _{\theta }(\eta )&=\log \left(\mathbb {E} _{\theta }\exp(\eta X)\right)=\psi (\theta +\eta )-\psi (\theta )<\infty \\\mathbb {E} _{\theta }(X)&=\left.{\frac {\partial \psi _{\theta }(\eta )}{\partial \eta }}}\right _{\eta =0}\\mathrm {Var} _{\theta }(X)&=\왼쪽.{\frac {\fract ^{2}\regated _{\theta }(\eta )}{\data }{\data }\right _{\eta =0}\end}}}}}}

As a simple example, suppose under

F(\cdot )

,

X\sim \mathrm {N} (\mu ,\sigma ^{2})

, with

{\textstyle \psi (\theta )=\theta \mu +{\frac {\sigma ^{2}\theta ^{2}}{2}}}

.

X|X\in \left[b,\infty \right]

는

X|X\in \left[b,\infty \right]

X X

X|X\in \left[b,\infty \right]

[

X|X\in \left[b,\infty \right]

,

X|X\in \left[b,\infty \right]

]

{\

b>\mu

>

b>\mu

{\displaysty b>\mu

b>\mu

분석은 다음과 같다.

Choose the form of the proposal distribution $F_{\theta }(\cdot )$ , with log moment-generating function as ${\textstyle \psi _{\theta }(\eta )=\psi (\theta +\eta )-\psi (\eta )=\eta (\mu +\theta \sigma ^{2})+{\frac {\sigma$ $^{2}\eta ^{2}}:{2$ 더 나아가 정규 분포 $\mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})$ + $\mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})$ $\mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})$ $\mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})$ , $\mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})$ $\mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})$ ) ${\displaystyle \mathrm {N}(\mu +\theta \sigma ^{2},\sigma ^{2})$ 임을 암시한다 $\mathrm {N} (\mu +\theta \sigma ^{2},\sigma ^{2})$
제안서 배포를 위해 $\theta ^{*}$ 잘 선택된 ${\$ 를 결정한다.In this setup, the intuitive way to choose $\theta ^{*}$ is to set $\mathbb {E} _{\theta }(X)=\mu +\theta \sigma ^{2}=b$ , that is $\theta ^{*}={\frac {b-\mu }{\sigma ^{2}}}$
목표값, 제안서 및 우도비 명시적 작성 ${\begin{aligned}f_{X X\geq b}(x)&={\frac {f(x)\mathbb {I} (x\geq b)}{\mathbb {P} (x\geq b)}}\\g_{\theta ^{*}}(x)&=f(x)\exp(\theta ^{*}x-\psi (\theta ^{*}))\\Z(x)&={\frac {f_{X X\geq b}(x)}{g_{\theta ^{*}}(x)}}={\frac {\exp(-\theta ^{*}x+\psi (\theta ^{*}))\mathbb {I} (x\geq b)}{\mathbb {P} (x\geq b)}}\end{aligned}}$
따라서 우도비 $z(x)$ ) $z(x)$ {\ $displaystyle$ z(x $z(x)$ 에 $M$ 대한 $바운드$ $M$ {\ $displaystyle$ z $(x$ $)}$ 을(를) 도출하십시오. 이 함수는 $x\in [b,\infty ]$ [ $b$ , $x\in [b,\infty ]$ $]$ {\ $displaystyle$ x $\in$ [b,\fty $x\in [b,\infty ]$ 에 대한 감소함수입니다. $M=Z(b)={\frac {\exp(-\theta ^{*}b+\psi (\theta ^{*}))}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} (X\geq b)}}={\frac {\exp \left(-{\frac {(b-\mu )^{2}}{2\sigma ^{2}}}\right)}{\mathbb {P} \left(\mathrm {N} (0,1)\geq {\frac {b-\mu }{\sigma }}\right)}}$
거부 샘플링 기준: $U\sim \mathrm {Unif} (0,1)$ ~ $U\sim \mathrm {Unif} (0,1)$ n $U\sim \mathrm {Unif} (0,1)$ $U\sim \mathrm {Unif} (0,1)$ ( 0 $U\sim \mathrm {Unif} (0,1)$ $U\sim \mathrm {Unif} (0,1)$ ) ${\displaystyle U\sim \mathrm {Unif} (0,1$ )에 대한 경우 $U\sim \mathrm {Unif} (0,1)$ $U\leq {\frac {Z(x)}{M}=e^{-\theta ^{*(x-b)}\mathb {I}(x\geq b)$ holds, $X$ ${\displaystyle$ X $}$ 의 값을 수락한다 $X$ ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ 않으면 새 ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ ~ ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ + ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ ∗ ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ ∗ ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ , ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ ) ${\textstyle$ X $\sim _{i.d.$ d. $}\mathrm {N}(\mu +\theta ^{*}\sigma ^{2})$ 및 수락 ${\textstyle X\sim _{i.i.d.}\mathrm {N} (\mu +\theta ^{*}\sigma ^{2},\sigma ^{2})}$ 전까지 ${\textstyle U\sim \mathrm {Unif} (0,1)}$ 새로운 ${\textstyle U\sim \mathrm {Unif} (0,1)}$ ~ ${\textstyle U\sim \mathrm {Unif} (0,1)}$ ${\textstyle U\sim \mathrm {Unif} (0,1)}$ , ${\textstyle U\sim \mathrm {Unif} (0,1)}$ ) ${\textstyle U\sim \mathrmatrm {Unif} (0,1).$

For the above example, as the measurement of the efficiency, the expected number of the iterations the NEF-Based Rejection sampling method is of order b, that is $M(b)=O(b)$ , while under the naive method, the expected number of the iterations is ${\textstyle {\frac {1}{\mathbb {P} (X\geq b)}}=O(b\cdot e^{\frac {(b-\mu )^{2}}{2\sigma ^{2}}})}$ $){\textstyle{\frac{1}{\mathb {P}(X\geq$ b $)}}}}}=O(b\cdot$ e $^{\frac {(b-\mu )^{2}}:{2\sigma$ ^{ $2$ 훨씬 비효율적이다.

일반적으로 제안 분포의 파라메트릭 클래스인 지수 기울기는 제안의 분포를 직접 특성화하는 유용한 속성으로 최적화 문제를 편리하게 해결한다.이러한 유형의 문제의 경우 $단순$ 분포의 클래스 중 $X\in A$ $X\in A$ A ${\displaystyle X$ A}에서 조건부로 X {\ $displaystyle$ X $}$ 을(를) 시뮬레이션하려면 NEF를 사용하여 복잡성을 어느 정도 제어하고 계산 속도를 상당히 빠르게 하는 것이 요령이다.사실, NEF를 사용하는 데에는 깊은 수학적 이유가 있다.

단점

거부 샘플링은 샘플링되는 함수가 특정 영역에 고도로 집중된 경우, 예를 들어 특정 위치에서 스파이크가 발생하는 경우 많은 원치 않는 샘플 채취로 이어질 수 있다.많은 분포에서 이 문제는 적응형 확장을 사용하여 해결할 수 있다(적응 거부 샘플링 참조). 또는 균등 비율의 방법에 따라 변수의 적절한 변화를 통해 해결할 수 있다.또한 문제의 치수가 커질수록 임베디드 볼륨의 "코너"에 대한 임베디드 볼륨의 비율은 0을 지향하는 경향이 있으므로 유용한 샘플이 생성되기 전에 많은 거부반응이 일어날 수 있으므로 알고리즘이 비효율적이고 비실용적이 된다.차원성의 저주를 보라.높은 차원에서는 메트로폴리스 샘플링이나 깁스 샘플링과 같은 마르코프 체인 몬테카를로 방식, 즉 일반적으로 다른 접근법을 사용할 필요가 있다.(단, 다차원 샘플링 문제를 일련의 저차원 샘플링으로 분해하는 Gibbs 샘플링은 그 단계 중 하나로 거부 샘플링을 사용할 수 있다.)

적응 제거 샘플링

많은 분포의 경우, 낭비되는 공간이 많지 않은 주어진 분포를 포함하는 제안 분포를 찾기가 어렵다.이러한 어려움을 극복하고 다양한 분포에서 효율적으로 샘플링하는 데 사용할 수 있는 거부반응 샘플링의 확장(실제 일반적인 분포의 대부분에 해당되며, 밀도 함수가 오목하지 않은 분포도 포함)을 적응형 rejec이라고 한다.티온 샘플링(ARS).

1992년 Gilks에 의해 궁극적으로 소개된 이 기술에는 세 가지 기본 아이디어가 있다.^[4]

도움이 될 경우 대신 로그 공간(예: 로그 확률 또는 로그 밀도)에서 봉투 분포를 정의하십시오.즉, $h\left(x\right)=\log g\left(x\right)$ ( $h\left(x\right)=\log g\left(x\right)$ ) $h\left(x\right)=\log g\left(x\right)$ = $h\left(x\right)=\log g\left(x\right)$ $h\left(x\right)=\log g\left(x\right)$ $h\left(x\right)=\log g\left(x\right)$ ( $h\left(x\right)=\log g\left(x\right)$ ) ${\$ g $\$ $left(x\right)}$ 을 $h\left(x\right)=\log g\left(x\right)$ (를) $g\left(x\right)$ g (x ) $g\left(x\right)$ {\ $displaystystyle$ g $\left(x\$ right $)}$ 대신 log g.
- 종종 대수적으로 지저분한 밀도 함수를 갖는 분포는 상당히 단순한 로그 밀도 함수를 가진다(예: $f\left(x\right)$ ( $f\left(x\right)$ ) ${\$ right $)}$ 이(가) 지저분할 $f\left(x\right)$ 경우, $\log f\left(x\right)$ f ( $\log f\left(x\right)$ ) $\log f\left(x\right)$ {\ $displaystyle \log$ f\ $left(x\$ rift $)}$ 은 부분 선형으로 작업하기가 더 쉬울 수 있다 $\log f\left(x\right)$ .
단일 균일한 봉투 밀도 함수 대신 조각으로 된 선형 밀도 함수를 봉투로 사용하십시오.
- 표본을 기각해야 할 때마다 평가한 $f\left(x\right)$ $f\left(x\right)$ $f\left(x\right)$ ) ${\$ 값을 사용하여 조각 근사 $h\left(x\right)$ ) ${\$ 을(를) 개선할 수 있다 $h\left(x\right)$ 따라서 이것은 당신의 다음 시도가 거절당할 가능성을 줄여준다.점증적으로, 당신의 샘플을 거부해야 할 확률은 0으로 수렴해야 하며, 실제로 매우 빠르게 수렴되어야 한다.
- 제안된 대로, 거부된 점을 선택할 때마다, 우리는 선택한 점과 동일한 x 좌표로 점의 곡선에 접하는 다른 선 세그먼트로 외피를 조인다.
- 제안 로그 분포의 조각별 선형 모형은 조각별 지수 분포 집합(즉, 하나 이상의 지수 분포의 세그먼트, 부착된 끝에서 끝까지)을 생성한다.지수 분포는 잘 행동하고 잘 이해된다.지수 분포의 로그는 직선이며, 따라서 이 방법은 밀도의 로그선을 일련의 선 세그먼트로 둘러싸는 것을 포함한다.이것이 로그-콘케이브 제한의 근원이 된다: 만일 분포가 로그-콘케이브라면, 그 로그는 오목(위쪽 U와 같은 모양)으로, 곡선에 접하는 선 세그먼트가 항상 곡선을 통과한다는 것을 의미한다.
- 로그 공간에서 작동하지 않을 경우 삼각형 분포를 통해 단편적인 선형 밀도 함수를 샘플링할 수도 있다.
$f\left(x\right)$ 는 당신의 샘플이 받아들여질 때 $f\left(x\right)$ $f\left(x\right)$ ( $f\left(x\right)$ x $){\$ \left $(x\$ right $)}$ 의 평가 비용을 잠재적으로 피하기 위해 (log) concidity 요건을 더욱 활용할 수 있다.
- 현재의 거부 체인에서 평가해야 했던 $h\left(x\right)$ $h\left(x\right)$ ( x $h\left(x\right)$ ) ${\$ 의 값을 사용하여 조각으로 된 선형 상한("발굴" 함수)을 구성할 수 있듯이, 이러한 값을 사용하여 조각으로 된 선형 하한(" $h\left(x\right)$ " 함수)도 구성할 수 있다.
- (잠재적으로 비싼) f $f\left(x\right)$ ( $f\left(x\right)$ ) ${\$ 을(를) 평가하기 $f\left(x\right)$ 전에 (이상적으로 저렴한) g $g_{l}\left(x\right)$ ( $g_{l}\left(x\right)$ ) ${\$ right $)}($ $h_{l}\left(x\right)$ $h_{l}\left(x\right)$ ${\$ rift $\)}}}}}}"$ 에 있는 t)과(x\우)를 비교하여 합격할지 여부를 이미 알 수 있다.그의 경우) 가능한 조임 기능.
- 이 짜임새 있는 단계는 길크스가 제안할 때도 선택사항이다.기껏해야 목표 밀도에 대한 추가 평가(메시지 및/또는 값비싼) 한 번만 수행하면 된다.그러나 추정하건대, 특히 값비싼 밀도함수(그리고 기각률이 0으로 빠르게 수렴된다고 가정함)의 경우, 이는 최종 런타임에서 상당한 차이를 만들 수 있다.

이 방법에는 기본적으로 일정한 수의 세그먼트(아마도 단 하나의 접선만 있을 것이다)로 시작하여 곡선을 상회하는 동안 로그에 근접한 직선 세그먼트의 엔벨롭을 연속적으로 결정하는 것이 포함된다.잘린 지수 랜덤 변수에서 표본을 추출하는 것은 간단하다.(적절한 간격과 그에 상응하는 잘림) 균일한 랜덤 변수의 로그를 취하십시오.

불행히도 ARS는 로그 컨베이어 대상 밀도에서 채취한 경우에만 적용할 수 있다.이러한 이유로, 비로그 콘베어 대상 분포에 대처하기 위해 문헌에서 ARS의 몇 가지 연장이 제안되었다.^[6]^[7]^[8]또한, 자체 조정 제안 밀도를 구축하는 범용 샘플러(즉, 제안서가 자동으로 구성되고 대상에 맞게 조정됨)를 얻기 위해 ARS와 Metropolitan-Hastings 방법의 다른 조합이 설계되었다.이러한 종류의 방법을 흔히 적응 거부 메트로폴리스 샘플링(ARMS) 알고리즘이라고 부른다.^[9]^[10]결과적인 적응 기법은 항상 적용할 수 있지만 생성된 샘플은 이 경우에 상관 관계가 있다(반복 횟수가 증가함에 따라 상관 관계가 빠르게 0으로 사라지기는 하지만).

참고 항목

참조

^ Casella, George; Robert, Christian P.; Wells, Martin T. (2004). Generalized Accept-Reject sampling schemes. Institute of Mathematical Statistics. pp. 342–347. doi:10.1214/lnms/1196285403. ISBN 9780940600614.
^ Neal, Radford M. (2003). "Slice Sampling". Annals of Statistics. 31 (3): 705–767. doi:10.1214/aos/1056562461. MR 1994729. Zbl 1051.65007.
^ Bishop, Christopher (2006). "11.4: Slice sampling". Pattern Recognition and Machine Learning. Springer. ISBN 978-0-387-31073-2.
^ Gibbs 샘플링을 위한 Adaptive Reject 샘플링.https://stat.duke.edu/~cnk/Links/tangent.method.pdf
^ D.B. Thomas와 W. Luk, 조각과 같은 선형 근사를 통한 불균일 난수 생성, 2006.http://www.doc.ic.ac.uk/~wl/sshd/sshd07dt.pdf
^ Hörmann, Wolfgang (1995-06-01). "A Rejection Technique for Sampling from T-concave Distributions". ACM Trans. Math. Softw. 21 (2): 182–193. CiteSeerX 10.1.1.56.6055. doi:10.1145/203082.203089. ISSN 0098-3500.
^ Evans, M.; Swartz, T. (1998-12-01). "Random Variable Generation Using Concavity Properties of Transformed Densities". Journal of Computational and Graphical Statistics. 7 (4): 514–528. CiteSeerX 10.1.1.53.9001. doi:10.2307/1390680. JSTOR 1390680.
^ Görür, Dilan; Teh, Yee Whye (2011-01-01). "Concave-Convex Adaptive Rejection Sampling". Journal of Computational and Graphical Statistics. 20 (3): 670–691. doi:10.1198/jcgs.2011.09058. ISSN 1061-8600.
^ Gilks, W. R.; Best, N. G.; Tan, K. K. C. (1995-01-01). "Adaptive Rejection Metropolis Sampling within Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 44 (4): 455–472. doi:10.2307/2986138. JSTOR 2986138.
^ Meyer, Renate; Cai, Bo; Perron, François (2008-03-15). "Adaptive rejection Metropolis sampling using Lagrange interpolation polynomials of degree 2". Computational Statistics & Data Analysis. 52 (7): 3408–3423. doi:10.1016/j.csda.2008.01.005.

로버트 C.P.와 카셀라 G. "몬테 카를로 통계적 방법"(제2판)뉴욕: Springer-Verlag, 2004.
J. von Neumann, "다양한 기술들이 임의의 숫자와 연관지어 사용되었다.몬테카를로 방법", 냇.Bureau Standards, 12 (1951), 페이지 36–38.

[1] Casella, George; Robert, Christian P.; Wells, Martin T. (2004). Generalized Accept-Reject sampling schemes. Institute of Mathematical Statistics. pp. 342–347. doi:10.1214/lnms/1196285403. ISBN 9780940600614.

[radford03-2] Neal, Radford M. (2003). "Slice Sampling". Annals of Statistics. 31 (3): 705–767. doi:10.1214/aos/1056562461. MR 1994729. Zbl 1051.65007.

[bishop06-3] Bishop, Christopher (2006). "11.4: Slice sampling". Pattern Recognition and Machine Learning. Springer. ISBN 978-0-387-31073-2.

[4] Gibbs 샘플링을 위한 Adaptive Reject 샘플링.https://stat.duke.edu/~cnk/Links/tangent.method.pdf

[5] D.B. Thomas와 W. Luk, 조각과 같은 선형 근사를 통한 불균일 난수 생성, 2006.http://www.doc.ic.ac.uk/~wl/sshd/sshd07dt.pdf

[6] Hörmann, Wolfgang (1995-06-01). "A Rejection Technique for Sampling from T-concave Distributions". ACM Trans. Math. Softw. 21 (2): 182–193. CiteSeerX 10.1.1.56.6055. doi:10.1145/203082.203089. ISSN 0098-3500.

[7] Evans, M.; Swartz, T. (1998-12-01). "Random Variable Generation Using Concavity Properties of Transformed Densities". Journal of Computational and Graphical Statistics. 7 (4): 514–528. CiteSeerX 10.1.1.53.9001. doi:10.2307/1390680. JSTOR 1390680.

[8] Görür, Dilan; Teh, Yee Whye (2011-01-01). "Concave-Convex Adaptive Rejection Sampling". Journal of Computational and Graphical Statistics. 20 (3): 670–691. doi:10.1198/jcgs.2011.09058. ISSN 1061-8600.

[9] Gilks, W. R.; Best, N. G.; Tan, K. K. C. (1995-01-01). "Adaptive Rejection Metropolis Sampling within Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 44 (4): 455–472. doi:10.2307/2986138. JSTOR 2986138.

[10] Meyer, Renate; Cai, Bo; Perron, François (2008-03-15). "Adaptive rejection Metropolis sampling using Lagrange interpolation polynomials of degree 2". Computational Statistics & Data Analysis. 52 (7): 3408–3423. doi:10.1016/j.csda.2008.01.005.

[1]

[2]

[3]

[4]

[6]

[7]

[8]

[9]

[10]

Search