몬테카를로 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

몬테카를로 알고리즘은 결정론적 알고리즘과 달리, 답이 항상 정확하지 않을 수 있는 확률적 알고리즘의 한 종류이다. 몬테카를로 알고리즘은 '거짓' 편향 또는 '참' 편향을 가질 수 있으며, 편향의 유무에 따라 단측 오류 또는 양측 오류가 있는 알고리즘으로 분류된다. 몬테카를로 알고리즘은 오류 증폭을 통해 정확도를 높일 수 있으며, 복잡도 클래스 BPP, RP, ZPP 등으로 표현될 수 있다. 몬테카를로 알고리즘은 라스베이거스 알고리즘과 함께 랜덤 알고리즘을 구성하며, 계산 정수론, 확률적 최적화 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

확률적 알고리즘 - 알고리즘 정보 이론
알고리즘 정보 이론은 콜모고로프 복잡성을 기반으로 객체의 정보량을 측정하는 척도를 제공하며, 최소 설명 길이 원리 등에 응용될 수 있다.
확률적 알고리즘 - 몬테카를로 방법
몬테카를로 방법은 확률적 모델링에 기반하여 무작위 표본 추출을 통해 수치적 결과를 얻는 계산 알고리즘으로, 복잡한 시스템 시뮬레이션, 다차원 적분, 최적화 등 다양한 분야에서 결정론적 문제 해결에 응용된다.

몬테카를로 알고리즘
개요
종류	확률 알고리즘
성격	'무작위성을 이용하여 문제를 해결하는 알고리즘: 시행 횟수와 정확도는 trade-off 관계를 가짐'
활용 분야	최적화 수치 적분 물리학 시뮬레이션 기타 계산 문제
특징
장점	복잡한 문제를 비교적 간단하게 해결 가능 병렬 처리 용이
단점	해의 정확성 보장 불가 문제에 따라 효율성이 크게 달라짐
유형
라스베이거스 알고리즘	항상 정확한 해를 반환하지만, 실행 시간이 보장되지 않음
몬테카를로 알고리즘	실행 시간은 보장되지만, 해가 정확하지 않을 수 있음
예시
최소 컷 문제	카거-스타인 알고리즘
최소 피드백 아크 셋 문제	몬테카를로 랜덤화 알고리즘

2. 몬테카를로 알고리즘의 종류와 오류 유형

결정적 알고리즘과 달리 몬테카를로 알고리즘의 답은 항상 정확하지 않을 수 있다. 몬테카를로 알고리즘은 오류 유형에 따라 단측 오류 알고리즘과 양측 오류 알고리즘으로 분류할 수 있다.

단측 오류 알고리즘은 '거짓' 또는 '참' 중 한쪽으로 편향된 결과를 낸다. 예를 들어 '거짓' 편향 알고리즘은 '거짓'을 반환할 때 항상 정확하다. 반면 양측 오류 알고리즘은 편향이 없어 '참' 또는 '거짓' 결과가 모두 일정 확률로 부정확할 수 있다.

솔로바이-슈트라센 소수판별법은 몬테카를로 알고리즘의 한 예시이다. 이 알고리즘은 소수 입력에 대해 항상 '참'을 반환하지만, 합성수 입력에 대해서는 1/2 이상의 확률로 '거짓'을 반환하고 1/2 이하의 확률로 '참'을 반환한다. 따라서 '거짓' 결과는 확실히 정확하지만, '참' 결과는 정확한지 확신할 수 없다. 이러한 알고리즘을 ''1/2-옳은 거짓 편향 알고리즘''이라고 부른다.

2. 1. 단측 오류 (One-sided error)

결정 문제의 경우 몬테카를로 알고리즘은 일반적으로 '''거짓''' 편향 또는 '''참''' 편향으로 분류된다. '''거짓''' 편향된 몬테카를로 알고리즘은 '''거짓'''을 반환할 때 항상 정확하다. 반대로 '''참''' 편향된 몬테카를로 알고리즘은 '''참'''을 반환할 때 항상 정확하다. 이러한 거짓 편향과 참 편향이 있는 몬테카를로 알고리즘을 ''단측'' 오류가 있다고 한다.

예를 들어, 솔로바이-슈트라센 소수판별법은 주어진 숫자가 소수인지 여부를 결정하는 데 사용된다. 이 검정은 소수 입력에 대해 항상 '''참'''으로 답한다. 합성수 입력의 경우 1/2 이상의 확률로 '''거짓'''으로 답하고 1/2 이하의 확률로 '''참'''으로 답한다. 따라서 이 검정이 '''거짓'''으로 도출한 답은 그 답이 정확하다고 확신할 수 있는 반면에, '''참'''으로 도출한 답은 정확한지 확신할 수 없다. 이런 방식의 알고리즘을 ''1/2-옳은 거짓 편향 알고리즘''이라 부른다.

2. 2. 양측 오류 (Two-sided error)

결정적 알고리즘에 의해 반환된 답은 항상 정확할 것으로 예상되지만 몬테카를로 알고리즘의 경우는 그렇지 않다. 결정 문제의 경우 몬테카를로 알고리즘은 일반적으로 '''거짓''' 편향 또는 '''참''' 편향으로 분류된다. '''거짓''' 편향된 몬테카를로 알고리즘은 '''거짓'''을 반환할 때 항상 정확하다. 반대로 '''참''' 편향된 몬테카를로 알고리즘은 '''참'''을 반환할 때 항상 정확하다. 이러한 거짓 편향과 참편향이 있는 몬테카를로 알고리즘을 ''단측 오류''가 있다고 한다. 반면, 거짓 편향과 참편향의 두 분류에 속하지 않는, 즉 편향이 없는 몬테카를로 알고리즘 또한 존재할 수 있다. 이들은 ''양측 오류''가 있다고 한다. 양측 오류가 있는 몬테카를로 알고리즘이 도출하는 참 또는 거짓의 답은 어느 정도 제한된 확률로 부정확할 수 있다.

예를 들어, 솔로바이-슈트라센 소수판별법은 주어진 숫자가 소수인지 여부를 결정하는 데 사용된다. 이 검정은 소수 입력에 대해 항상 '''참'''으로 답한다. 합성수 입력의 경우 1/2 이상의 확률로 '''거짓'''으로 답하고 1/2 이하의 확률로 '''참'''으로 답한다. 따라서 이 검정이 '''거짓'''으로 도출한 답은 그 답이 정확하다고 확신할 수 있는 반면에, '''참'''으로 도출한 답은 정확한지 확신할 수 없다. 이런 방식의 알고리즘을 ''1/2-옳은 거짓 편향 알고리즘''이라 부른다.

3. 오류 증폭 (Amplification)

몬테카를로 알고리즘은 단측 오류 또는 양측 오류를 가질 수 있는데, 이러한 오류 확률을 줄이기 위해 알고리즘을 여러 번 반복 실행하는 방법을 사용할 수 있다.

단측 오류의 경우, 알고리즘을 ''k''번 실행하여 실패 확률을 줄이고 성공 확률을 증폭시킬 수 있다. 예를 들어 솔로바이-슈트라센 알고리즘을 ''k''번 반복 실행하여 '''거짓'''이라는 답이 나오면 '''거짓'''을, 그렇지 않으면 '''참'''을 반환하는 방식으로 오류 확률을 줄일 수 있다.

양측 오류의 경우에도 알고리즘을 ''k''번 실행하고 그 결과들의 다수 함수를 취하여 실패 확률을 줄일 수 있다.

3. 1. 단측 오류 알고리즘

단측 오류가 있는 몬테카를로 알고리즘의 경우 알고리즘을 k번 실행하여 실패 확률을 줄이고 성공 확률을 증폭시킬 수 있다. 솔로바이-슈트라센 알고리즘은 1/2-옳은 거짓 편향 알고리즘이다. 솔로바이-슈트라센 알고리즘으로 시행을 ''k''번 반복하는 동안 '''거짓''' 반응에 도달하면 '''거짓'''이라는 답을 반환하고, 그렇지 않으면 '''참'''이라는 답을 반환하면서 알고리즘을 여러 번 실행할 수 있다. 만약 숫자가 소수이면 답은 항상 옳고 숫자가 합성수이면 답은 최소한 1 − (1/2)^''k'' = 1−2^''−k'' 이상의 확률로 옳다.^[1]

3. 2. 양측 오류 알고리즘

양측 오류가 있는 몬테카를로 결정 알고리즘의 경우, 알고리즘을 ''k''번 실행하고 결과의 다수결 함수를 반환하여 실패 확률을 줄일 수 있다.^[1]

4. 복잡도 클래스 (Complexity Classes)

복잡도 클래스에는 BPP, RP, ZPP, PP 등이 있다. BPP는 양측 오류에 대한 유계 오류 확률을 갖는 다항 시간 몬테카를로 알고리즘으로 해결할 수 있는 결정 문제를 표현한다. RP는 단측 오류에 대한 유계 오류 확률이 1인 몬테카를로 알고리즘으로 해결할 수 있는 문제를 표현한다. 즉, 정답이 '거짓'이면 알고리즘 또한 항상 거짓을 반환하지만, 정답이 '참'이면 경우에 따라 '거짓'을 잘못 반환할 수 있다.^[4] ZPP는 다항 기대 시간 라스베가스 알고리즘으로 해결할 수 있는 문제를 표현한다. 이러한 복잡도 클래스들의 관계는 ZPP ⊆ RP ⊆ BPP로 나타낼 수 있지만, 서로 구별되는지 여부는 알려져 있지 않다. PP는 동전을 던지는 것보다는 더 정확하지만 오류 확률이 모든 시행에서 1/2 보다 낮다고는 할 수 없는 다항 시간 몬테카를로 알고리즘의 결정 문제를 표현한다.^[4]

4. 1. BPP (Bounded-error Probabilistic Polynomial time)

복잡도 클래스 BPP는 양측 오류에 대한 유계 오류 확률을 갖는 다항 시간 몬테카를로 알고리즘으로 해결할 수 있는 결정 문제를 표현한다.^[4] 복잡도 클래스 RP는 단측 오류에 대한 유계 오류 확률이 1인 몬테카를로 알고리즘으로 해결할 수 있는 문제를 표현한다. 즉, 만약 정답이 '''거짓'''이면 알고리즘 또한 항상 거짓을 반환하지만, 정답이 '''참'''이면 경우에 따라 옳지 않은 답인 '''거짓'''을 잘못 반환할 수 있다.^[4] 대조적으로, 복잡도 클래스 ZPP는 다항 기대 시간 라스베가스 알고리즘으로 해결할 수 있는 문제를 표현한다. 따라서 위 복잡도 클래스들의 관계는 ZPP ⊆ RP ⊆ BPP 로 나타낼 수 있다. 그러나 이러한 복잡성 클래스들이 서로 구별되는지 여부는 알려져 있지 않다. 즉, 몬테카를로 알고리즘은 라스베가스 알고리즘보다 더 큰 계산 능력을 가질지도 모르지만 이는 아직 증명되지 않았다.^[4] 또 다른 복잡도 클래스인 PP는 동전을 던지는 것보다는 더 정확하지만 오류 확률이 1/2 보다 낮다고는 할 수 없는 다항 시간 몬테카를로 알고리즘의 결정 문제를 표현한다.^[4]

4. 2. RP (Randomized Polynomial time)

복잡도 클래스 RP는 단측 오류에 대한 유계 오류 확률을 갖는 몬테카를로 알고리즘으로 해결할 수 있는 문제를 표현한다. 즉, 정답이 '거짓'이면 알고리즘 또한 항상 거짓을 반환하지만, 정답이 '참'이면 경우에 따라 옳지 않은 답인 '거짓'을 잘못 반환할 수 있다.^[4]

4. 3. ZPP (Zero-error Probabilistic Polynomial time)

복잡도 클래스 ZPP는 다항 기대 시간 라스베가스 알고리즘으로 해결할 수 있는 문제를 표현한다.^[4] ZPP, RP, BPP 복잡도 종류 중 어느 것이 서로 다른지는 알려져 있지 않다. 즉, 몬테카를로 알고리즘이 라스베이거스 알고리즘보다 더 많은 계산 능력을 가질 수 있지만, 이는 증명되지 않았다.^[4]

4. 4. PP (Probabilistic Polynomial time)

복잡도 클래스 PP는 동전을 던지는 것보다는 더 정확하지만 오류 확률이 모든 시행에서 보다 낮다고는 할 수 없는 다항 시간 몬테카를로 알고리즘의 결정 문제를 표현한다.^[4]

4. 5. 복잡도 클래스 간의 관계

복잡도 클래스 ZPP, RP, BPP의 관계는 ZPP ⊆ RP ⊆ BPP로 나타낼 수 있다. 그러나 이러한 복잡도 클래스들이 서로 구별되는지 여부는 알려져 있지 않다. 즉, 몬테카를로 알고리즘은 라스베가스 알고리즘보다 더 큰 계산 능력을 가질지도 모르지만 이는 아직 증명되지 않았다.^[4]

5. 몬테카를로와 라스베가스 알고리즘

랜덤 알고리즘은 크게 몬테카를로 알고리즘과 라스베이거스 알고리즘 두 가지 유형으로 나뉜다.^[4]

라스베이거스
셔우드
수치
몬테카를로
애틀랜틱 시티
수치

라스베이거스 알고리즘과 몬테카를로 알고리즘 비교
	효율성	최적성	실패 (LV) / 오차 (MC)
라스베이거스 (LV)	확률적	확정적	$\tfrac{1}{2}$
셔우드	확정적 또는 셔우드 확률적 (일반 LV보다 강력한 경계)	확정적	0
수치	확률적, 확정적 또는 셔우드 확률적	확정적	$\tfrac{1}{2}$ 또는 0
몬테카를로 (MC)	확정적	확률적	$<1$ (반복 실행을 통해 지수적으로 증가하는 확률은 알고리즘의 유용성을 저해할 수 있음; 일반적인 경우는 $\tfrac{1}{2}$ )
애틀랜틱 시티	확정적	확률적	$\tfrac{1}{4}$
수치	확정적	확률적	$<1$ (알고리즘 유형에 따라 다름)

위 표는 몬테카를로와 라스베이거스 랜덤 알고리즘에 대한 일반적인 프레임워크를 나타낸다.^[4]

5. 1. 라스베가스 알고리즘 (Las Vegas algorithms)

라스베가스 알고리즘은 항상 정확한 결과를 반환하지만, 실행 시간이 확률적으로 변동한다.^[4] 셔우드(Sherwood), 수치 알고리즘 등이 이에 해당한다.^[4]

라스베가스 알고리즘과 몬테카를로 알고리즘은 모두 결정 형태의 문제, 즉 결정을 다루는 데 사용될 수 있다.^[4] 그러나 이러한 알고리즘이 결정 문제에만 국한되는 것은 아니며, 두 유형의 랜덤 알고리즘 모두 수치적 문제, 즉 출력이 단순히 '예'/'아니오'가 아니라 본질적으로 수치적인 결과를 얻어야 하는 문제에도 사용될 수 있다.^[4]

라스베이거스 알고리즘과 몬테카를로 알고리즘 비교
	효율성	최적성	실패 (LV) / 오차 (MC)
라스베가스 (LV)	확률적	확정적	<math><mfrac>1</mfrac></math>
셔우드	확정적 또는 셔우드 확률적 (일반 LV보다 강력한 경계)	확정적	0
수치	확률적, 확정적 또는 셔우드 확률적	확정적	<math><mfrac>1</mfrac></math> 또는 0
몬테카를로 (MC)	확정적	확률적	<math><1</math>(반복 실행을 통해 지수적으로 증가하는 확률은 알고리즘의 유용성을 저해할 수 있음; 일반적인 경우는 <math><mfrac>1</mfrac></math>)
애틀랜틱 시티	확정적	확률적	<math><mfrac>1</mfrac></math>
수치	확정적	확률적	<math><1</math>(알고리즘 유형에 따라 다름)

위 표는 몬테카를로와 라스베이거스 랜덤 알고리즘에 대한 일반적인 프레임워크를 나타낸다.^[4]

5. 2. 몬테카를로 알고리즘 (Monte Carlo algorithms)

몬테카를로 알고리즘은 실행 시간은 정해져 있지만, 결과는 확률적으로 부정확할 수 있는 알고리즘이다. 애틀랜틱 시티 알고리즘과 수치 알고리즘 등이 몬테카를로 알고리즘에 속한다.^[4]

라스베이거스와 몬테카를로 알고리즘은 모두 결정 형태의 문제를 다루지만,^[4] 이러한 알고리즘이 결정 문제에만 국한되는 것은 아니다. 두 유형의 랜덤 알고리즘 모두 수치적 문제, 즉 출력이 '예'/'아니오'가 아니라 수치적인 결과를 얻어야 하는 문제에도 사용될 수 있다.^[4]

라스베이거스 알고리즘과 몬테카를로 알고리즘 비교
	효율성	최적성	실패 (LV) / 오차 (MC)
몬테카를로 (MC)	확정적	확률적	$<1$ (반복 실행을 통해 지수적으로 증가하는 확률은 알고리즘의 유용성을 저해할 수 있음; 일반적인 경우는 $<\tfrac{1}{2}$ )
애틀랜틱 시티	확정적	확률적	$<\tfrac{1}{4}$
수치	확정적	확률적	$<1$ (알고리즘 유형에 따라 다름)

위 표는 몬테카를로와 라스베이거스 랜덤 알고리즘에 대한 일반적인 프레임워크를 나타낸다.^[4]

6. 계산 정수론 및 기타 분야에서의 응용

몬테카를로 알고리즘은 계산 정수론 및 확률적 최적화 등 다양한 분야에서 활용된다. 계산 정수론 분야에서는 솔로바이-슈트라센 소수판별법, 베일리–PSW 소수판별법, 밀러-라빈 소수판별법 등이, 확률적 최적화 분야에서는 개미 영감 몬테카를로 등이 몬테카를로 알고리즘을 활용한 예시이다.^[4]^[5]

6. 1. 계산 정수론

솔로바이-슈트라센 소수판별법, 베일리–PSW 소수판별법, 밀러-라빈 소수판별법 및 계산적 군론에서 Schreier-Sims 알고리즘의 실행 속도를 높인 특정 변형이 몬테카를로 알고리즘에 포함된다.^[4]

6. 2. 확률적 최적화 (Stochastic Optimization)

확률을 미리 알 수 없고 경험적으로 결정되는 알고리즘 그룹인 확률적 최적화 (SO)에 속하는 알고리즘의 경우, 몬테카를로 알고리즘과 이러한 알고리즘을 병합하여 "미리 계산된 확률 바운드와 확률적 최적화 구성 요소를 모두 가질 수 있다."^[4] 이러한 방식으로 "SO의 단점이 완화되었고, 솔루션에 대한 신뢰도가 확립되었다."^[4]^[5] 이러한 알고리즘의 예로는 개미 영감 몬테카를로가 있다.^[4]^[5]

참조

_[1] 논문 A New Approach to the Minimum Cut Problem 1996-07
_[2] 논문 Monte-Carlo randomized algorithm for minimal feedback arc set problem 2016-04-01
_[3] 논문 The beginning of the Monte Carlo method http://library.lanl.[...]
_[4] 서적 IOT with Smart Systems Springer Nature 2023
_[5] 논문 Ant inspired Monte Carlo algorithm for minimum feedback arc set https://doi.org/10.1[...] 2019
_[6] 논문 A New Approach to the Minimum Cut Problem 1996-07
_[7] 논문 Monte-Carlo randomized algorithm for minimal feedback arc set problem 2016-04-01
_[8] 논문 The beginning of the Monte Carlo method http://library.lanl.[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com