확률적 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
확률적 알고리즘은 알고리즘 실행 과정에 무작위성을 활용하는 알고리즘으로, 암호학, 계산 복잡도 이론, 그래프 이론 등 다양한 분야에서 활용된다. 재전송 공격 방지, 배열 내 특정 값 탐색, 퀵 정렬 등에서 효율성을 보이며, 라스베가스 알고리즘과 몬테카를로 알고리즘으로 분류된다. 계산 복잡도 이론에서는 확률적 튜링 기계로 모델링되며, RP, Co-RP, BPP, ZPP, NP-난해 등의 복잡도 종류가 연구된다. 밀러-라빈 소수 판별법은 확률적 알고리즘 연구의 중요한 시작점이며, 퀵 정렬, 최소 컷 알고리즘, 해시 테이블, 블룸 필터 등 다양한 자료 구조와 알고리즘에 응용된다. 탈난수화는 확률적 알고리즘에서 무작위성을 제거하거나 줄이는 과정이며, 조건부 확률, 불일치 이론, 해시 함수 등을 활용한다.
더 읽어볼만한 페이지
- 확률적 알고리즘 - 알고리즘 정보 이론
알고리즘 정보 이론은 콜모고로프 복잡성을 기반으로 객체의 정보량을 측정하는 척도를 제공하며, 최소 설명 길이 원리 등에 응용될 수 있다. - 확률적 알고리즘 - 몬테카를로 알고리즘
몬테카를로 알고리즘은 정확한 답을 보장하지 않는 확률적 알고리즘으로, 단측 또는 양측 오류를 가지며 반복 실행으로 오류를 줄일 수 있고, 라스베가스 알고리즘과 함께 랜덤 알고리즘의 주요 분류를 이루며 다양한 분야에 응용된다. - 알고리즘 분석 - 계산 복잡도
계산 복잡도는 알고리즘의 효율성을 평가하는 척도로, 시간, 공간 등의 자원을 고려하며, 입력 크기의 함수로 표현되고, 빅 오 표기법을 사용하여 알고리즘의 예상 성능을 파악하는 데 중요한 역할을 한다. - 알고리즘 분석 - 비결정적 알고리즘
비결정적 알고리즘은 계산 과정에서 여러 선택지를 가질 수 있는 비결정론적 튜링 기계 또는 비결정성을 활용하는 프로그래밍 패러다임인 비결정론적 프로그래밍과 관련된 알고리즘을 포괄적으로 지칭한다.
| 확률적 알고리즘 | |
|---|---|
| 알고리즘 종류 | |
| 유형 | 확률론 활용 알고리즘 |
| 특징 | 알고리즘 논리 또는 절차의 일부로 무작위성을 활용 |
| 기대 실행 시간 | 평균적인 성능을 분석하는 데 사용되는 지표 |
| 세부 종류 | |
| 몬테카를로 알고리즘 | 항상 답을 내놓지만, 틀릴 수도 있음 |
| 라스베이거스 알고리즘 | 항상 정확한 답을 내놓지만, 답을 내놓지 못할 수도 있음 |
| 셔우드 알고리즘 | 항상 정확한 답을 내놓으며, 실행 시간이 입력에 의존하지 않도록 설계됨 |
2. 필요성
''n''개의 요소로 이루어진 배열에서 "a"라는 요소를 찾는 문제를 생각해 보자. 이 배열의 절반은 "a"이고 나머지는 "b"이다. 순차 탐색과 같이 요소를 조사하는 순서가 고정된 결정론적 알고리즘은, "b"가 앞쪽에 몰려 있는 경우처럼, 최악의 경우 n/2번의 연산이 필요하여 시간이 오래 걸릴 수 있다. 그러나 배열 요소를 무작위 순서로 조사하는 확률적 알고리즘을 사용하면, 입력과 무관하게 높은 확률로 "a"를 빠르게 찾을 수 있다.
암호학 분야에서도 확률적 알고리즘은 매우 중요하다. 예를 들어, 온라인 계좌 이체 시 악의적인 사용자의 재전송 공격을 방지하기 위해, 임의의 난수를 발생시켜 알고리즘 실행 과정을 매번 다르게 만들어야 한다. 이때 의사 난수 생성기 대신 실제 난수 또는 암호학적으로 안전한 의사 난수 생성기를 사용해야 한다. 양자컴퓨터에서 실행되는 모든 알고리즘은 본질적으로 확률적 알고리즘이다.
확률적 알고리즘은 실행 시간이 오래 걸릴 확률이 존재하지만, 항상 옳은 결과를 내놓는다. 반면, 오류가 발생할 확률을 감수하고서라도 알고리즘을 빠르게 실행하는 것이 중요한 경우도 있다. 전자를 라스베가스 알고리즘, 후자를 몬테카를로 알고리즘이라고 한다.
2. 1. 라스베가스 알고리즘과 몬테카를로 알고리즘
확률적 알고리즘은 결과의 정확성과 실행 시간에 따라 라스베가스 알고리즘과 몬테카를로 알고리즘으로 분류할 수 있다.- '''라스베가스 알고리즘''': 항상 정확한 결과를 반환하지만, 실행 시간이 확률적으로 변동한다.
- '''몬테카를로 알고리즘''': 실행 시간은 제한되지만, 작은 확률로 오류가 발생할 수 있다.
모든 라스베가스 알고리즘은 몬테카를로 알고리즘으로 변환될 수 있으며, 그 반대도 특정 조건 하에서 가능하다. 예를 들어, 라스베가스 알고리즘이 정해진 시간 안에 완료되지 않으면 임의의 (틀릴 수도 있는) 결과값을 출력하도록 하면 몬테카를로 알고리즘이 된다. 만약 몬테카를로 알고리즘의 결과가 정답인지 확인할 수 있는 효율적인 방법이 있다면, 정답을 얻을 때까지 알고리즘을 반복 실행하여 라스베가스 알고리즘으로 만들 수 있다.
''n''개의 원소가 들어있는 배열에서 절반은 ''a''이고 나머지 절반은 ''b''일 때, 배열에서 ''a''를 찾는 문제를 예시로 들 수 있다.
- '''라스베가스 알고리즘'''의 경우, 배열에서 임의의 원소를 골라 ''a''가 나올 때까지 반복한다. 이 알고리즘은 항상 성공하지만, 실행 시간은 확률적이다.
- '''몬테카를로 알고리즘'''의 경우, 배열에서 임의의 원소를 ''k''번 골라 ''a''를 찾는다. 이 알고리즘은 ''k''번 안에 ''a''를 찾지 못하면 실패하지만, 실행 시간은 ''k''로 제한된다.
3. 복잡도
계산 복잡도 이론에서는 확률적 알고리즘을 확률적 튜링 기계로 모형화하여 연구한다. 라스베이거스 알고리즘과 몬테카를로 알고리즘을 모두 대상으로 하며, 이와 관련된 여러 복잡도 종류가 연구되고 있다.
'예'와 '아니오' 두 가지 답변 모두 오류가 발생할 수 있는 복잡도는 BPP이다. 평균적으로 다항 시간 안에 올바른 답을 낼 수 있는 문제들의 종류는 ZPP이다. NP-난해 문제들은 이러한 복잡도 종류에 포함되지 않는다고 추정되며, 확률적 알고리즘만으로는 풀기 어렵고 근사 알고리즘을 사용해야 한다.
확률적 알고리즘 연구는 1976년에 제안된 밀러-라빈 소수판별법을 계기로 활발해졌다.
3. 1. 주요 복잡도 종류
RP는 효율적인(다항 시간) 확률적 알고리즘(또는 확률적 튜링 기계)이 존재하는 판정 문제의 집합이다. 이 알고리즘은 다음 조건을 만족해야 한다.- '아니오' 입력에 대해서는 항상 '아니오' 결과를 출력한다.
- '예' 입력에 대해서는 최소 50% 확률로 '예' 결과를 출력한다.
co-RP는 RP의 여집합이다. 즉, '예' 입력은 항상 '예'로, '아니오' 입력은 최소 50% 확률로 '아니오'로 판정하는 문제의 집합이다.
BPP는 '예'와 '아니오' 입력 모두에 대해 오류 확률이 제한된 효율적인 확률적 알고리즘이 존재하는 문제의 집합이다. 즉, '예' 입력을 '예'로, '아니오' 입력을 '아니오'로 판정할 확률이 모두 2/3 이상인 문제들이다.
ZPP는 평균적으로 다항 시간 안에 올바른 답을 낼 수 있는 문제의 집합이다. 어떤 입력에 대해서는 알고리즘이 무한히 실행될 수 있지만, 평균 실행 시간은 다항 시간이다.
NP-난해 문제들은 RP, co-RP, BPP, ZPP 등에 속하지 않는다고 추정되는 문제들이다. 이러한 문제들은 확률적 알고리즘만으로는 풀기 어렵고, 근사 알고리즘이 필요할 수 있다.
다음은 주요 복잡도 종류를 표로 정리한 것이다.
| 복잡도 종류 | 설명 |
|---|---|
| RP | 아니오 입력은 항상 아니오, 예 입력은 최소 50% 확률로 '예' |
| co-RP | 예 입력은 항상 예, 아니오 입력은 최소 50% 확률로 '아니오' |
| BPP | 예와 아니오 입력 모두 오류 확률이 제한됨 (2/3 이상 올바르게 판정) |
| ZPP | 평균 다항 시간 안에 항상 올바른 답을 출력 |
| NP-난해 | RP, co-RP, BPP, ZPP에 속하지 않는다고 추정되는 문제들 |
3. 2. 밀러-라빈 소수 판별법
1976년에 제안된 밀러-라빈 소수 판별법은 확률적 알고리즘 연구의 중요한 계기가 되었다. 이 알고리즘은 주어진 수가 소수인지 합성수인지 판별하는 효율적인 방법을 제공하며, 소수 판별 문제가 Co-RP에 속한다는 것을 보여준다.밀러-라빈 소수판별법은 두 개의 자연수 ''k''와 ''n'' 사이의 '증거'(witness)라는 이항관계를 사용한다. '증거' 관계는 다음과 같은 성질을 가진다.
- ''n''에 대한 증거가 존재하면, ''n''은 합성수이다. (즉, ''n''은 소수가 아니다.)
- ''n''이 합성수이면 ''n''보다 작은 수 중에서 최소한 3/4은 ''n''이 합성수라는 증거이다.
- ''k''와 ''n''이 주어졌을 때, ''k''가 ''n''이 합성수라는 것에 대한 증거인지 아닌지 판별하는 빠른 알고리즘이 존재한다.
합성수 ''n''보다 작은 임의의 수를 100번 선택하여 알고리즘을 실행시킨다면, 이런 '증거'를 못 찾을 확률은 (1/4)100이다. 그러므로 거의 대부분의 경우에서, 이와 같은 소수 판별법은 매우 좋은 알고리즘이라고 생각할 수 있다. 특히 ''n''이 아주 크다면, 이 방법 이외에는 효율적인 알고리즘이 없다. 알고리즘을 여러 번 시행하면 오류가 일어날 확률을 원하는 만큼 줄일 수도 있다.
작은 확률로 오류가 발생하더라도 알고리즘을 조금만 주의해서 실행시키면 오류가 일어날 확률을 천문학적으로 작은 숫자만큼 줄일 수 있기 때문에, 실제로 오류가 발생하는 것은 그다지 큰 문제가 되지 않는다. 실제로 결정론적으로 소수를 판별하는 다항시간 알고리즘이 발견되었어도, 다양한 암호 관련 소프트웨어에서는 기존의 소수 판별법을 그대로 사용하고 있으며, 소수 판별 분야에서는 결정론적 알고리즘이 가까운 시일 안에 기존 확률적 알고리즘을 대체할 수는 없을 것으로 보인다.
4. 응용
확률적 알고리즘은 다양한 분야에서 활용되고 있다.
퀵 정렬은 난수를 사용하여 피벗을 선택함으로써, 높은 확률로 *O*(*n* log *n*) 시간에 정렬을 완료한다. 결정론적 알고리즘은 *n*개를 정렬하는데 O(*n*2) 만큼의 시간이 걸릴 수 있지만, 확률적 알고리즘은 임의의 원소를 무작위로 선택하여 이러한 문제를 완화한다.[28]
그래프 이론에서 최소 컷을 찾는 알고리즘 또한 확률적 알고리즘이 사용되는 예시이다. *n*이 그래프의 꼭짓점 개수일 때, 최소 절단을 찾기 위해 알고리즘을 *n*2 log *n* 번 실행하여 그 중 가장 작은 값을 선택하면 높은 확률로 최소 절단을 찾을 수 있다.
튜링 머신 계산 모델에서 무작위 선택을 통해 다항 시간 내에 해결 가능한 문제의 범위(P = BPP 인지)는 아직 열린 질문이지만, 다른 맥락에서는 무작위성이 성능 향상을 가져오는 경우가 존재한다.
- 2''k''개의 문자열(절반은 'a', 절반은 'b')에서 'a'의 색인을 찾는 문제에서, 랜덤 액세스 머신은 최악의 경우 2''k''−1번의 조회가 필요하지만, 무작위 선택을 허용하면 예상되는 다항 횟수의 조회로 해결 가능하다.
- 임베디드 시스템 또는 사이버-물리 시스템에서 수치 계산 시, 확률적으로 근사한 결과를 제공하는 PACC (Probably Approximately Correct Computation) 방식이 활용될 수 있으며, 무작위화는 근사 계산과 정확한 계산 사이의 불일치 손실 평가에 효과적이다.[21]
- 통신 복잡도에서 두 문자열의 동일성은 무작위 프로토콜을 사용하면 log *n* 비트의 통신으로 확인 가능하지만, 결정적 프로토콜은 Θ(*n*) 비트가 필요하다.[22]
- 볼록 다면체의 부피는 다항 시간 내에 임의의 정밀도로 무작위 알고리즘으로 추정할 수 있지만,[23] 바라니와 퓌레디는 결정적 알고리즘으로는 불가능함을 보였다.[24]
- IP는 강력한 증명자와 BPP 알고리즘을 구현하는 검증자 간의 다항식 길이 상호작용을 통해 허용될 수 있는 언어로 구성되며, IP = PSPACE이다.[25] 그러나 검증자가 결정적이면 IP = NP이다.
- 화학 반응 네트워크에서 초기 상태에서 목표 상태에 도달하는 능력은 결정 가능하지만, 목표 상태에 도달할 확률을 근사하는 것은 결정 불가능하다. 무작위 화학 반응 네트워크는 제한된 튜링 머신을 높은 확률로 시뮬레이션할 수 있지만, 비결정적 화학 반응 네트워크는 원시 귀납적 함수로 제한된다.[26]
4. 1. 퀵 정렬
퀵 정렬은 난수를 사용하여 피벗을 선택함으로써, 높은 확률로 *O*(*n* log *n*) 시간에 정렬을 완료하는 대표적인 확률적 알고리즘이다. 결정론적 퀵 정렬은 특정 입력에 대해 *O*(*n*2) 시간이 걸릴 수 있지만, 확률적 퀵 정렬은 이러한 문제를 완화한다.[28] 토니 호어는 1959년에 퀵 정렬을 발견하였고, 1961년에 발표하였다.[4]확률적 퀵 정렬은 피벗 원소를 무작위로 균일하게 선택하기 때문에 입력의 특성과 관계없이 높은 확률로 *O*(*n* log *n*) 시간 안에 정렬을 완료한다. 반면, 결정론적 퀵 정렬은 피벗 선택 방법에 따라 특정 입력(예: 이미 정렬된 배열)에 대해 *O*(*n*2) 시간이 걸릴 수 있다. 결정론적 퀵 정렬의 최악의 경우는 알고리즘의 피벗 선택 프로토콜에 의해 정의되는 특정 입력 클래스에 대해 발생한다. 그러나 무작위성을 활용하면 이러한 문제를 해결할 수 있다.[28]
4. 2. 그래프 이론 (최소 컷 알고리즘)
카게르의 최소 컷 알고리즘은 그래프에서 최소 컷을 찾기 위해 확률적 방법을 사용하는 예시이다. 이 알고리즘은 임의의 간선을 반복적으로 축약하여 최소 컷을 높은 확률로 찾아낸다.'''입력''': 그래프 ''G''(''V'',''E'')
'''출력''': 정점을 ''L''과 ''R''로 분할하는 컷, ''L''과 ''R'' 사이의 최소 개수의 간선을 가짐.
두 노드 ''u''와 ''v''의 축약은 (다중) 그래프에서 ''u'' 또는 ''v''에 인접한 간선의 합집합인 간선이 있는 새로운 노드 ''u'' '를 생성하지만, ''u''와 ''v''를 연결하는 간선은 제외한다. 축약 후, 결과 그래프는 평행 간선을 가질 수 있지만 자기 루프는 포함하지 않는다.
카게르의[20] 기본 알고리즘은 다음과 같다.
'''시작'''
# i = 1
# '''반복'''
## '''반복'''
### G에서 임의의 간선 (u,v) ∈ E 선택
### u와 v를 축약 u'로 대체
## '''종료될 때까지''' 단 두 개의 노드만 남음
## 해당 컷 결과 Ci 획득
## i = i + 1
# '''종료될 때까지''' i = m
# C1, C2, ..., Cm 중에서 최소 컷 출력.
'''종료'''
외부 루프의 각 실행에서 알고리즘은 두 개의 노드만 남을 때까지 내부 루프를 반복하고 해당 컷을 얻는다. 한 번의 실행 시간은 이며, ''n''은 정점의 수를 나타낸다. 외부 루프의 ''m''번 실행 후, 모든 결과 중에서 최소 컷을 출력한다.
알고리즘이 성공할 확률은 모든 시도가 실패할 확률의 1 − 이다. 독립성에 의해, 모든 시도가 실패할 확률은 다음과 같다.
:
보조정리 1에 따르면, 일 확률은 반복 ''i'' 동안 ''C''의 어떤 변도 선택되지 않을 확률이다. 내부 루프를 고려하고, 를 ''j''개의 변 축약 후의 그래프로 나타내며, 여기서 이다. 는 개의 정점을 가진다. 우리는 조건부 가능성의 연쇄 규칙을 사용한다. 반복 ''j''에서 선택된 변이 ''C''에 속하지 않을 확률은, 이전에 ''C''의 어떤 변도 선택되지 않았다는 조건 하에,