지구라트 알고리즘

Ziggurat algorithm

지구라트 알고리즘은 의사 난수 샘플링을 위한 알고리즘이다.거부 샘플링 알고리즘의 종류에 속하는, 그것은 일반적으로 의사 난수 생성기 및 사전 계산된 표에서 나오는 균일하게 분포된 난수의 기본 소스에 의존한다.알고리즘은 단조롭게 감소하는 확률 분포로부터 값을 생성하는데 사용된다.정규 분포와 같은 대칭 단모형 분포에도 적용할 수 있는데, 분포의 절반에서 값을 선택한 다음 어떤 값이 도출되었다고 간주되는지를 임의로 선택하는 것이다.1960년대에 조지 마르사글리아 등이 개발했다.null

알고리즘에서 산출되는 일반적인 값은 하나의 랜덤 부동소수 값과 하나의 랜덤 테이블 인덱스 생성만을 필요로 하며, 그 다음에 하나의 테이블 조회, 하나의 곱셈 연산, 하나의 비교가 필요하다.때로는 (일반적인 테이블 크기를 사용할 때 정규 분포나 지수 분포의 경우)[citation needed] 더 많은 계산이 필요하다.그럼에도 불구하고 알고리즘은 정상적으로 분포된 무작위 숫자를 생성하는 가장 일반적으로 사용되는 두 가지 방법인 마르사글리아 극지방법과 박스-뮬러 변환보다 계산적으로 훨씬 더[citation needed] 빨라서 생성된 값의 각 쌍에 대해 적어도 하나의 로그와 1제곱근 계산을 필요로 한다.단, 지그구라트 알고리즘은 구현이 더 복잡하기 때문에 대량의 난수가 필요할 때 가장 잘 사용된다.null

지구라트 알고리즘이라는 용어는 2000년 마사글리아 논문에서 와이완창(Wai Wan Tsang)으로 유래한 것으로, 크기순으로 적층된 직사각형 세그먼트로 확률 분포를 커버하는 개념에 기초해 지구라트와 닮은 형상을 만들어 내기 때문에 그렇게 이름이 붙여졌다.null

정규 분포로 표본 값을 생성하는 데 사용되는 Ziggurat 알고리즘. (단순함을 위해 양수 값만 표시)분홍색 점들은 처음에 균일하게 분포된 난수들이다.원하는 분포 함수는 먼저 동일한 영역 "A"로 분할된다.왼쪽의 균일한 소스에 의해 임의로 1 레이어 i를 선택한다.그런 다음, 최상위 소스의 무작위 값을 선택한 층의 너비로 곱하고, 그 결과는 3가지 가능한 결과: 1) (왼쪽, 검은색 고체 영역) 샘플이 곡선 아래 명확하게 전달되고, 2) (오른쪽, 수직 줄무늬 영역) 샘플 값이 놓여질 수 있는 슬라이스의 어느 영역에 속하는지 보기 위해 x 테스트된다.커브 아래에서 추가 테스트를 수행해야 한다.이 경우, 선택된 레이어 내의 임의 y 값이 생성되어 f(x)와 비교된다.작을 경우 점이 곡선 아래에 있고 x 값이 출력된다.그렇지 않을 경우(세 번째 경우), 선택한 포인트 x는 거부되고 알고리즘은 처음부터 재시작된다.

운영이론

지구라트 알고리즘은 거부 샘플링 알고리즘으로, 원하는 분포보다 약간 큰 분포에서 임의로 점을 생성한 다음 생성된 점이 원하는 분포 내에 있는지 여부를 검정한다.그렇지 않으면 다시 시도한다.확률밀도곡선 아래에 랜덤 포인트가 주어진 경우, x 좌표는 원하는 분포를 갖는 랜덤 숫자다.null

지그구라트 알고리즘이 선택한 분포는 n개의 동일한 영역으로 구성된다. 즉, 원하는 분포의 대부분을 커버하는 n - 1개의 직사각형이며, 분포의 꼬리가 포함된 직사각형이 아닌 베이스 위에 배치된다.null

모든 x ≥ 0에 대해 정의된 모노톤 감소 확률밀도함수 f(x)를 고려할 때, 지그거랏의 기저부는 분포1 내부 및 y = f(x1) 이하 모든 점으로 정의된다.이것은 분포의 (0, 0)에서 (x1, y)까지의1 직사각형 영역과 (일반적으로 무한) 꼬리로 구성되며, 여기서 x > x1 (및 y < y)이다1.null

이 레이어(레이어 0이라 부름)는 영역 A를 가지고 있다.그 위에 가로 x와1 높이 A/x의1 직사각형 층을 추가하여 A 영역도 가진다.이 층의 상단은 높이2 y = y1 + A/x이며1, 지점(x2, y2)에서 밀도 함수를 교차시킨다. 여기서2 y = f(x2)이 계층은 y와1 y2 사이의 밀도함수의 모든 점을 포함하지만, (기본 계층과 달리) 또한 원하는 분포에 없는1 (x2, y)와 같은 점을 포함한다.null

그리고 나서 더 많은 층들이 위에 쌓인다.사전 계산된 n 크기 표(n = 256이 일반적임)를 사용하려면 xn = 0으로 x를1 선택한다. 즉, 맨 위 상자 n - 1이 정확하게 분포의 피크(0, f(0)에 도달한다는 뜻이다.null

층 i는 y에서i y까지i+1 수직으로 확장되며, 수평으로 두 영역으로 나눌 수 있는데, 0에서 x까지의i+1 (일반적으로 더 큰) 부분과 x에서i+1i (작은) 부분만 포함하는 부분이다.null

레이어 0의 문제를 잠시 무시하고, 균일한 랜덤 변수 U와0 U and1[0,1]을 주어진 지그구라트 알고리즘은 다음과 같이 설명할 수 있다.

  1. 랜덤 레이어 0 ≤ i < n을 선택한다.
  2. let x = Ux0i.
  3. x < x인i+1 경우 x를 반환한다.
  4. y = yi + U1(yi+1i - y)로 한다.
  5. f(x)를 계산한다.y < f(x)인 경우 x를 반환하십시오.
  6. 그렇지 않으면 새 난수를 선택하고 1단계로 돌아가십시오.

1단계는 저해상도 y 좌표를 선택하는 것과 같다.3단계에서는 y 좌표에 대해 자세히 알지 못한 상태에서 x 좌표가 원하는 밀도 함수 내에 있는지 여부를 검정한다.그렇지 않은 경우 4단계는 고해상도 y 좌표를 선택하고 5단계에서는 거부 테스트를 수행한다.null

밀접하게 간격을 두고 있는 레이어들과 함께 알고리즘은 3단계에서 매우 큰 시간에서 종료된다.그러나 상위 계층 n - 1의 경우 xn = 0이기 때문에 이 테스트는 항상 실패한다.

레이어 0도 중앙 지역과 가장자리로 나눌 수 있지만 가장자리는 무한 꼬리다.점이 중심 영역에 있는지 확인하기 위해 동일한 알고리즘을 사용하려면 가상 x0 = A/y를1 생성하십시오.이렇게 하면 정확한 주파수를 가진 x < x로1 포인트가 생성되며, 레이어 0이 선택되고 x x1 x가 선택되는 드문 경우에는 특수한 폴백 알고리즘을 사용하여 꼬리에서 임의로 포인트를 선택한다.폴백 알고리즘은 천 번에서 한 번 이하로 사용되기 때문에 속도가 필수적이지 않다.null

따라서 단측 분포를 위한 전체 지그거랏 알고리즘은 다음과 같다.

  1. 랜덤 레이어 0 ≤ i < n을 선택한다.
  2. 렛트 x = ux0i
  3. x < x인i+1 경우 x를 반환한다.
  4. i = 0이면 폴백 알고리즘을 사용하여 꼬리에서 점을 생성하십시오.
  5. y = yi + U1(yi+1i - y)로 한다.
  6. f(x)를 계산한다.y < f(x)인 경우 x를 반환하십시오.
  7. 그렇지 않으면 새 난수를 선택하고 1단계로 돌아가십시오.

양면 분포의 경우 물론 그 결과는 시간의 50%를 부정해야 한다.이것은 종종0 U ∈(-1,1)을 선택하고, 3단계에서 x < x를i+1 시험하면 쉽게 할 수 있다.

꼬리에 대한 예비 알고리즘

직구라트 알고리즘은 대부분의 출력을 매우 빠르게 생성할 뿐이고, x > x마다1 폴백 알고리즘을 필요로 하기 때문에, 항상 보다 직접적인 구현보다 더 복잡하다.물론 예비 알고리즘은 분포에 따라 달라진다.null

지수 분포의 경우 꼬리는 분포의 본체와 똑같이 보인다.한 가지 방법은 가장 기본적인 알고리즘 E = -ln(U1)으로 돌아가서 x = x - ln(U1)으로1 하는 것이다.또 하나는 지그구라트 알고리즘을 재귀적으로 호출하여 결과에 x를1 추가하는 것이다.null

정규 분포를 위해 Marsaglia는 다음과 같은 콤팩트한 알고리즘을 제안한다.

  1. x = -ln(U1)/x로1 두십시오.
  2. y = -ln(U2)으로 한다.
  3. 2y > x인2 경우 x + x를1 반환한다.
  4. 그렇지 않으면 1단계로 돌아가십시오.

일반적인 테이블 크기에 대한1 x ≈ 3.5이므로, 3단계의 테스트는 거의 항상 성공적이다.null

최적화

알고리즘은 x와i yi = f(xi)의 사전 계산된 표로 효율적으로 수행될 수 있지만, 훨씬 더 빠르게 하기 위해 약간의 수정이 있다.

  • 지그구라트 알고리즘의 어떤 것도 정규화되고 있는 확률 분포 함수에 의존하지 않는다(곡선 아래의 통합은 1과 같음), 정규화 상수를 제거하면 f(x)의 계산 속도를 높일 수 있다.
  • 대부분의 균일한 난수 생성기는 [0, 232 - 1] 범위의 정수를 반환하는 정수 난수 생성기를 기반으로 한다.2x의−32i 표는 당신이 U를0 위해 직접 그러한 숫자를 사용할 수 있게 해준다.
  • 앞에서 설명한 양면 U를0 사용하여 양면 분포를 계산할 때 임의의 정수는 [-231, 231 - 1] 범위의 부호수로 해석할 수 있으며, 2의−31 척도를 사용할 수 있다.
  • 3단계에서 ux와0i x를i+1 비교하기보다는 xi+1/x를i 미리 계산해 U와0 직접 비교하는 것이 가능하다.U가0 정수 난수 생성기인 경우, 이러한 한계는 232(또는 적절한 경우 231)로 미리 설정하여 정수 비교를 사용할 수 있다.
  • 위의 두 가지 변경으로 인해 수정되지 않은 xi 값 표는 더 이상 필요하지 않으며 삭제될 수도 있다.
  • 24비트 맨티사(암묵적 선행 1 포함)만 있는 IEEE 754 단일정밀 부동소수 값을 생성할 때는 32비트 정수 난수 비트가 사용되지 않는다.이 비트는 레이어 번호를 선택하는 데 사용될 수 있다.자세한 내용은 아래 참조를 참조하십시오.
  • 처음 세 단계는 덜 자주 필요한 단계의 아웃오브 이행을 호출할 수 있는 인라인 함수에 넣을 수 있다.

테이블 생성

사전 계산된 테이블 전체를 저장하거나, 소스 코드에 n, y1, A, f(y)의 −1 구현 값만 포함시킬 수 있으며, 난수 생성기를 초기화할 때 나머지 값을 계산할 수 있다.null

앞에서i+1 설명한 대로i x = f −1(yi) 및 y = y + Ai/x를i 찾을 수 있다.지그거랏의 층에 대해 n - 1회 반복한다.마지막에n y = f(0)를 가져야 한다.물론 약간의 반올림 오류가 있을 것이지만, 그것이 받아들일 수 있을 정도로 작다는 것을 보는 것은 유용한 분별력 시험이다.null

실제로 표 값을 입력할 때는 xn = 0과 yn = f(0)로 가정하고, 도면층 n - 1의 면적의 약간의 차이를 반올림 오류로 인정한다.null

x1 및 A 찾기

초기 (guess at x) x에1 주어진 경우 x > x에1 해당하는 꼬리의 면적 t를 계산하는 방법이 필요하다. 지수 분포의 경우 이것은 e일−x1 뿐이고, 정규 분포의 경우, 비정규화된 f(x−x2/2) = e를 사용한다고 가정하면 this√/2 erfc(x/x2)이다.좀 더 어색한 분포를 위해서는 수치적 통합이 필요할 수 있다.null

이것을 손에 들고, x로부터11 y = f(x1), 꼬리 부분의 면적 t, 기초층 A = xy11 + t를 찾을 수 있다.

그런 다음 위의 y와 x 시리즈를ii 계산하십시오.어떤 i < n에 대해서도i y > f(0)가 되면 초기 추정치 x가1 너무 낮아서 A 영역이 너무 커지게 된다.yn < f(0)이면 초기 추정치 x가1 너무 높았다.null

이 경우, 뿌리 찾기 알고리즘(이분법 등)을 사용하여 가능한 한 y를 f(0)에n−1 가깝게 생성하는 x 값을1 찾으십시오.또는 가장 높은 계층의 영역인 x(fn−1(0) - yn−1)를 원하는 값 A에 근접하게 만드는 값을 가능한 한 찾아보십시오.이것은 f −1(x)에 대한 하나의 평가를 저장하며, 실제로 가장 큰 관심의 조건이다.null

참조

  • George Marsaglia; Wai Wan Tsang (2000). "The Ziggurat Method for Generating Random Variables". Journal of Statistical Software. 5 (8). Retrieved 2007-06-20. 이 논문은 위에서 시작하는 층수를 1에서 시작하여 층수를 0으로 하고, 아래쪽의 층수를 0에서 특별한 경우로 한다.
  • C 논문의 코드의 사본인 정상 밀도 함수와 지수 밀도 함수에 대한 지그구라트 방법의 구현. (잠재적 사용자는 이 C 코드가 32비트 정수를 가정한다는 것을 알아야 한다.)
  • 지그구라트 알고리즘의 C# 구현 및 방법 개요.
  • Jurgen A. Doornik (2005). "An Improved Ziggurat Method to Generate Normal Random Samples" (PDF). Nuffield College, Oxford. Retrieved 2007-06-20. {{cite journal}}: Cite 저널은 (도움말) 적층 번호를 선택하기 위해 정수 난수 발생기의 최소 중요 비트를 사용하는 위험을 설명한다.
  • MATLAB 버전 5, 2001에 소개된 지그구라트 알고리즘을 설명하는 MathWorks의 Cleve Moler에 의한 정상 행동.
  • 2015년 5월 18일 Cleve Moler가 게시한 MathWorks의 Ziggurat Random Normal Generator 블로그.
  • 데이비드 B.토마스, 필립 H.Leong;웨인 Luk;JohnD.Villasenor(2007년 10월)."가우시안 랜덤 번호 업자"(PDF).ACM컴퓨팅 조사 39(4):11:1–38. doi:10.1145/1287620.1287622.ISSN 0360-0300.S2CID 10948255.2009-07-27 Retrieved.극도로 높은 통계적 품질 유지[W]hen이 우선, 그 제약 조건에 의거, 속도 또한 원하는, 지구라트 법 가끔 가장 적절한 선택이다.비교 여러 알고리즘 가우스의 무작위 번호를 생성하는.
  • Nadler, Boaz (2006). "Design Flaws in the Implementation of the Ziggurat and Monty Python methods (And some remarks on Matlab randn)". arXiv:math/0603058..은 균일한 의사 난수 생성기의 기본적인 문제와 그러한 문제들이 지그구라트 알고리즘의 출력에 어떻게 영향을 미치는지 설명한다.
  • Edrees, Hassan M.; Cheung, Brian; Sandora, McCullen; Nummey, David; Stefan, Deian (13–16 July 2009). Hardware-Optimized Ziggurat Algorithm for High-Speed Gaussian Random Number Generators (PDF). 2009 International Conference on Engineering of Reconfigurable Systems & Algorithms. Las Vegas.
  • Marsaglia, George (September 1963). Generating a Variable from the Tail of the Normal Distribution (Technical report). Boeing Scientific Research Labs. Mathematical Note No. 322, DTIC accession number AD0423993 – via Defense Technical Information Center.