교차엔트로피법

교차 엔트로피(CE) 방법은 중요도 샘플링과 최적화를 위한 몬테카를로 방법이다.그것은 정적이거나 시끄러운 목적을 가진 결합형 및 연속형 문제 모두에 적용된다.

이 방법은 다음과 같은 두 단계를 반복하여 최적 중요도 샘플링 추정기에 근접한 값이다.^[1]

1. 확률 분포에서 표본을 추출하십시오.
2. 이 분포와 목표 분포 사이의 교차 엔트로피를 최소화하여 다음 반복에서 더 나은 표본을 생성하십시오.

Reuven Rubinstein은 네트워크 신뢰성 분석, 대기열 모델 또는 통신 시스템의 성능 분석과 같이 아주 작은 확률을 추정해야 하는 희귀 사건 시뮬레이션의 맥락에서 이 방법을 개발했다.이 방법은 또한 여행 판매원, 2차 배정, DNA 시퀀스 정렬, 최대 절단 및 버퍼 할당 문제에도 적용되었다.

중요도 샘플링을 통한 추정

수량을 추정하는 일반적인 문제를 고려

${\displaystyle \ell =\mathbb {E} _{\mathbf {u} }[H(\mathbf {X} )]=\int H(\mathbf {x} )\,f(\mathbf {x} ;\mathbf {u} )\,{\textrm {d}}\mathbf {x} }$,

여기서 $H{\displaystyle }$ ${\displaystyle H}$은(는) 일부 성능 함수이고 $f{\displaystyle (}$ x${\displaystyle }$; ${\displaystyle u\mathbf{}}$) ${\displaystyle f(\mathbf {x};\mathbf {u})$는 일부 모수 분포 계열의 구성원이다$$.중요도 표본을 사용하여 이 수량을 다음과 같이 추정할 수 있다.

${\displaystyle {\hat {\ell }}={\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{g(\mathbf {X} _{i})}}}$,

여기서 $X{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}{}_{}}$,${\displaystyle }$… , ${\displaystyle {\mathbf{}}_{}}$ N ${\$는 g {\displaystyle $g\,}$에서 무작위로 추출한$$ $표본$이다$.$$$양수 H {\$displaystyle$H$\}$의 경우 이론적으로 최적의 중요도 샘플 밀도(PDF)가 주어진다.

${\displaystyle {}^{}g}$ ${\displaystyle {\ast }^{}}$( ${\displaystyle x\mathbf{}}$)${\displaystyle }$= ${\displaystyle H}$( ${\displaystyle x\mathbf{}}$) f${\displaystyle }$( ${\displaystyle x\mathbf{}}$; ${\displaystyle u\mathbf{}}$)${\displaystyle }$/ ${\displaystyle \ell }$ ${\displaystyle g^{*}(\mathbf {x})=H(\mathbf {x} )f(\mathbf {x};\mathbf {u} )/\ell$ $\}.$

그러나 이는 알려지지 않은 ${\displaystyle \ell }}$에 따라 달라진다$.$ CE 방법은 $최적{\displaystyle {}^{}}$ PDF g$∗{\$ g$^{*}$에 가장 가까운 파라메트릭 계열의 멤버를 (Kullback-Leibler 감각에서) 적응적으로 선택함으로써 최적의 PDF를 근사하게 하는 것을 목표로 한다$.$

일반 CE 알고리즘

1. 초기 매개 변수 $벡터{\displaystyle {\mathbf{}}^{}}$v (${\displaystyle 0^{}}$ )$${\$displaystyle \mathbf {v}$^{($0$ ; t = 1을 선택하십시오.
2. $f{\displaystyle (\cdot ;}$${\displaystyle }$${\displaystyle {}^{}}$( ${\displaystyle {\mathrm{t}}^{}}$ -${\displaystyle {}^{}}$1${\displaystyle {}^{}}$) ${\$cdot; {$n} _{1},\dots,\mathbf {X} _{N}}$에서 랜덤 표본 $X{\displaystyle {\mathbf{}}_{}{}_{}}$ 생성, ${\$$displaystyle$ f$(\cdot;\mathbf)$ {$v} ^{{(t-1)}$
3. $v{\displaystyle {\mathbf{}}^{}}$( ${\displaystyle t^{}}$) ${\$에 대해 해결하십시오$.$ 여기서
   ${\displaystyle \mathbf {v} ^{(t)}=\mathop {\textrm {argmax}} _{\mathbf {v} }{\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}}\log f(\mathbf {X} _{i};\mathbf {v} )}$
4. 수렴에 도달하면 정지한다. 그렇지 않으면 t를 1씩 증가시키고 2단계부터 반복한다.

여러 경우에 3단계의 해결책은 분석적으로 찾을 수 있다.이러한 상황이 발생하는 상황은

• $f{\displaystyle }$ ${\$이(가) 자연 지수 계열에 속할$$ 때
• $f{\displaystyle }$ ${\$이(가) 유한 지지로 분리된 경우
• When ${\displaystyle H(\mathbf {X} )=\mathrm {I} _{\{\mathbf {x} \in A\}}}$ and ${\displaystyle f(\mathbf {X} _{i};\mathbf {u} )=f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}$, then ${\displaystyle \mathbf {v} ^{(t)}}$ corresponds이러한 $X{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle A}$에 기반한 최대우도 추정기까지 ${\displaystyle \mathbf {X} _{k}\in$ A$\}$ .

연속 최적화—예:

추정이 아닌 최적화에 동일한 CE 알고리즘을 사용할 수 있다.Suppose the problem is to maximize some function ${\displaystyle S}$, for example, ${\displaystyle S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}}$. To apply CE, one considers first the associated stochastic problem of estimating ${\displaystyle {\mathbb{P}}_{\mathit{\theta }}}$${\displaystyle \mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )}$ for a given level ${\displaystyle \gamma \,}$, and parametric family ${\displaystyle \left\{f(\cdot ;{\boldsymbol {\theta }})\right\}}$, for example the 1-dimensional Gaussian distribution, parameterized by its mean $$${\displaystyle {\mu }_{}}$ ${\displaystyle t_{}}$ $displaystyle \mu _{t}\,}$ 및 분산$$ ${\displaystyle {\mathrm{}}_{}^{}}$ t$$2 {\$displaystyle \sigma _{t}^{2}}($소$$ $\theta {\displaystyle \mathit{}}$= (${\displaystyle \mu }$,${\displaystyle }$μ, ${\displaystyle {}^{}}$ $){\displaystystyle {\\ta }=(\mu ,\\ma$^{$2}).$Hence, for a given ${\displaystyle \gamma \,}$, the goal is to find ${\displaystyle {\boldsymbol {\theta }}}$ so that ${\displaystyle D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\ f_{\boldsymbol {\theta }})}$ is minimized.이는 위의 3단계에서와 같이 KL 발산 최소화 문제의 샘플 버전(스토스틱 상대편)을 해결함으로써 이루어진다.이러한 대상 분포와 모수 계열의 선택에 대한 확률적 상대를 최소화하는 매개변수는 엘리트 표본에 해당하는 표본 평균과 표본 분산으로, ${\displaystyle \mathrm{객관적}}$인 함수 값 $\ge {\displaystyle }$ $≥{\displaystyle \geq \gamma }$을 갖는 표본이다$.$ 엘리트 표본 중 최악의 경우는 바로 우리들이다.다음 반복에 대한 수준 매개변수로 ed.이것은 분포 알고리즘의 추정인 소위 다변량 정규 알고리즘(EMNA)의 추정과 일치하는 다음과 같은 무작위화된 알고리즘을 산출한다.

가성음

//초기화 매개 변수:)−6 σ2:=100t:=0maxits:=100N:=100로마:=10을 끓여는 동안 maxits고 t<>융합되지 않을 초과하지 않는다면;maxits과σ2>ε // 현재 샘플링 분배에서 N샘플을 얻다.니 X:)SampleGaussian(μ, σ2, N)으로 표본 추출한 포인트 S에서 객관적인 기능을 평가하라 //:=exp(−(X− 2)^ 2)+ 0.8지수 함수(−(X+μ.2)^2) // 목표 함수 값으로 X를 내림차순으로 정렬 X := 소트(X, S) // 샘플링 분배 μs의 매개변수 업데이트 := 평균(X(1:Ne) 22 : = var(1:Ne) t := t + 1 // 솔루션 반환 μs로 최종 샘플링 분배의 반환 평균

관련 방법

• 시뮬레이션 어닐링
• 유전 알고리즘
• 하모니 검색
• 분포 알고리즘 추정
• 타부 검색
• 자연 진화 전략

참고 항목

• 크로스 엔트로피
• 쿨백-라이블러 발산
• 랜덤화 알고리즘
• 중요도 샘플링

저널 페이퍼

• P-T, Kroese, D.P, Mannor, S.와 R.Y.의 Rubinstein(2005)의 De Boer, Kroese, D.P., Mannor, S., R.Y.의 Rubinsteinstein.교차-엔트로피 방법에 대한 자습서.운영연구연보, 134 (1), 19-67.[1]
• 루빈스타인, R.Y. (1997년)희귀 사건을 포함한 컴퓨터 시뮬레이션 모델의 최적화, 유럽 학술지 운영 연구, 99, 89–112.

소프트웨어 구현

• CE최적 R 패키지
• 노박타분석.NET 패키지

참조