확률 컴퓨팅

**확률 컴퓨팅** 또는 **확률적 컴퓨팅**(stochastic computing)은 연속적인 값을 임의의 비트 스트림으로 표현하는 기술 집합이다. 복잡한 계산은 스트림에 대한 간단한 비트별 연산을 통해 수행될 수 있다. 확률 컴퓨팅은 확률적 알고리즘 연구와는 구별된다.
# 동기 부여 및 간단한 예시
p,q \in [0,1]가 주어졌을 때 p \times q를 계산한다고 가정하자. 확률 컴퓨팅은 산술 대신 확률을 사용하여 이 연산을 수행한다. 특히, 확률 수(즉, 베르누이 과정)라고 불리는 두 개의 무작위 독립 비트 스트림이 있다고 가정하자. 여기서 첫 번째 스트림에서 1이 나타날 확률은 p이고, 두 번째 스트림에서 1이 나타날 확률은 q이다. 두 스트림의 논리곱(AND)을 취할 수 있다. {| class="wikitable" | 1 || 0 || 1 || 1 || 0 || 1 || ... |- ! b_i | 1 || 1 || 0 || 1 || 1 || 0 || ... |- ! a_i \land b_i | 1 || 0 || 0 || 1 || 0 || 0 || ... |} 출력 스트림에서 1이 나타날 확률은 pq이다. 충분한 출력 비트를 관찰하고 1의 빈도를 측정함으로써 pq를 임의의 정확도로 추정할 수 있다. 위의 연산은 상당히 복잡한 계산(p와 q의 곱셈)을 무작위 비트에 대한 매우 간단한 연산(a_i \land b_i 평가)의 시리즈로 변환한다. 다른 관점에서 보면, AND 게이트의 진리표를 가정해 보자. 일반적인 해석은 입력 A와 B가 참일 경우에만 출력이 참이라는 것이다. 그러나 표를 수직으로 해석하면 (0011) AND (0101)는 (0001)이 된다. 즉, 1/2 x 1/2 = 1/4이며, 이는 정확히 산술 곱셈이다. 정보가 확률 분포로 제시되기 때문에 확률 곱셈은 문자 그대로 AND 연산이다. {| class="wikitable" |+ !A !B !Out |- |0 |0 |0 |- |0 |1 |0 |- |1 |0 |0 |- |1 |1 |1 |} 더 일반적으로 말해서, 확률 컴퓨팅은 숫자를 무작위 비트 스트림으로 표현하고 빈도를 계산하여 숫자를 재구성한다. 계산은 스트림에서 수행되며 p와 q에 대한 복잡한 연산을 스트림 표현에 대한 간단한 연산으로 변환한다. (재구성 방식 때문에 이 연산을 수행하는 장치를 확률 평균화 프로세서라고 부르기도 한다.) 현대적인 용어로, 확률 컴퓨팅은 확률적 관점에서 계산을 해석하는 것으로 볼 수 있으며, 이는 기브스 샘플러로 평가된다. 또한 하이브리드 아날로그/디지털 컴퓨터로도 해석될 수 있다.
# 역사
확률 컴퓨팅은 1953년 존 폰 노이만의 선구적인 논문에서 처음 소개되었다.isbn = 978-0-393-05169-8 그러나 이 이론은 1960년대 컴퓨팅의 발전,url=https://books.google.com/books?id=94BQAAAAMAAJ 주로 미국 s2cid=8504153과 영국 s2cid=832296에서 동시에 여러 연구 노력을 통해 발전하기 전까지는 완전히 개발될 수 없었다. 1960년대 후반에 이르러 확률 계산을 수행하기 위한 특수 목적 하드웨어 설계에 관심이 집중되었다. 1969년부터 1974년 사이에 수많은 isbn=978-0-906048-44-3 기계가 제작되었으며, 이 글에는 RASCEL publisher=University of Illinois, Urbana, Illinois 이 그림으로 제시되어 있다. 1960년대와 1970년대의 열띤 관심에도 불구하고, 확률 컴퓨팅은 아래에 설명된 이유로 인해 결국 기존 디지털 논리와 경쟁하는 데 실패했다. 제1회 (이자 마지막) 확률 컴퓨팅 국제 심포지엄 oclc=499229066 은 1978년에 개최되었고, 이후 몇 년 동안 이 분야의 활발한 연구는 감소했다. 확률 컴퓨팅은 일반적인 컴퓨팅 방법으로는 쇠퇴했지만, 여러 응용 분야에서 가능성을 보여주었다. 연구는 전통적으로 기계 학습 및 제어 분야의 특정 작업에 집중되었다. isbn=9781489958433 s2cid=14929278 비교적 최근에는 확률 컴퓨팅을 오류 정정 코드 디코딩에 적용하는 확률 디코딩으로 관심이 옮겨갔다. bibcode=2003ElL....39..299G 더 최근에는 확률 회로가 윤곽선 검출s2cid = 18174415 및 영상 임계 처리와 같은 영상 처리 작업에 성공적으로 사용되었다.s2cid = 6591306 확률 회로의 최근 발전은 에지 컴퓨팅에서 인공지능(AI) 하드웨어 가속에 유망한 속도와 에너지 효율성 이점을 보여주고 있다.
# 장점과 단점
확률 컴퓨팅은 역사적으로 실패했지만, 특정 문제를 해결하는 데 여전히 유용할 수 있다. 언제 유용한지 이해하려면 확률 컴퓨팅을 기존 디지털 컴퓨팅 방법과 비교하는 것이 유용하다.
## 장점
각각 n 비트 정밀도를 가진 두 숫자를 곱한다고 가정하자. 일반적인 세로 곱셈 방법을 사용하면 n^2 연산을 수행해야 한다. 확률 컴퓨팅을 사용하면 임의의 수의 비트를 AND 연산할 수 있으며 기대값은 항상 정확하다. (그러나 적은 수의 샘플로는 분산으로 인해 실제 결과가 매우 부정확해진다.) 또한 디지털 곱셈기의 기본 연산은 전가산기인 반면, 확률 컴퓨터는 AND 게이트만 필요하다. 게다가 디지털 곱셈기는 단순히 2n개의 입력 와이어가 필요하지만, 확률 곱셈기는 두 개의 입력 와이어만 필요하다. (그러나 디지털 곱셈기가 출력을 직렬화한다면 두 개의 입력 와이어만 필요할 것이다.) 또한 확률 컴퓨팅은 노이즈에 강하다. 스트림의 몇몇 비트가 뒤집혀도 이러한 오류는 해결책에 큰 영향을 미 미치지 않는다. 또한 확률 컴퓨팅 요소는 입력 도착 시간의 왜곡을 허용한다. 입력이 시간적으로 어긋나 있어도 회로는 올바르게 작동한다. 결과적으로 확률 시스템은 전역 클록 및 값비싼 클록 분배 네트워크를 사용하는 대신 저렴한 로컬 생성 클록으로 작동하도록 설계할 수 있다.s2cid = 8973285 마지막으로 확률 컴퓨팅은 비트 스트림을 확장할수록 더욱 정확해지는 해결책 추정치를 제공한다. 특히, 매우 빠르게 대략적인 추정치를 제공한다. 이 속성은 일반적으로 점진적 정밀도라고 불리며, 계산이 진행됨에 따라 확률 수(비트 스트림)의 정밀도가 증가함을 시사한다.s2cid = 4689958 이는 숫자의 최상위 비트가 최하위 비트보다 먼저 도착하는 것과 같다. 기존 산술 회로에서는 최상위 비트가 보통 마지막에 도착하는 것과는 다르다. 일부 반복 시스템에서는 점진적 정밀도를 통해 얻은 부분 해결책이 전통적인 컴퓨팅 방법보다 빠른 피드백을 제공하여 수렴 속도를 높일 수 있다.
## 약점
확률 컴퓨팅은 본질적으로 무작위적이다. 무작위 비트 스트림을 검사하고 기본 값을 재구성하려고 할 때, 유효 정밀도는 샘플의 분산으로 측정될 수 있다. 위 예시에서 디지털 곱셈기는 2n 비트 정확도로 숫자를 계산하므로 정밀도는 2^{-2n}이다. 무작위 비트 스트림을 사용하여 숫자를 추정하고 해결책 추정치의 표준 편차가 최소한 2^{-2n}이 되기를 원한다면, O(2^{4n})개의 샘플이 필요할 것이다. 이는 작업량의 기하급수적인 증가를 나타낸다. 그러나 특정 응용 분야에서는 확률 컴퓨팅의 점진적 정밀도 속성을 활용하여 이러한 기하급수적인 손실을 보상할 수 있다. 둘째, 확률 컴퓨팅은 무작위 편향 비트 스트림을 생성하는 방법이 필요하다. 실제로 이러한 스트림은 유사난수 생성기로 생성된다. 불행히도 (유사)무작위 비트를 생성하는 것은 상당히 비용이 많이 든다(예를 들어 전가산기 비용에 비해). 따라서 확률 컴퓨팅의 게이트 수준 이점은 일반적으로 사라진다. 셋째, 확률 컴퓨팅의 분석은 비트 스트림이 독립적(비상관적)이라고 가정한다. 이 가정이 유효하지 않으면 확률 컴퓨팅은 극적으로 실패할 수 있다. 예를 들어, p에 대한 비트 스트림을 자기 자신과 곱하여 p^2를 계산하려고 하면 프로세스가 실패한다. a_i \land a_i=a_i이므로 확률 계산은 p \times p = p 를 산출할 것이며, 이는 일반적으로 참이 아니다( p=0 또는 1이 아닌 한). 피드백이 있는 시스템에서는 비상관 문제 가 더 복잡한 방식으로 나타날 수 있다. 확률 프로세서 시스템은 래칭(latching)에 취약하며, 여기서 다른 구성 요소 간의 피드백이 교착 상태에 도달할 수 있다. s2cid=16390484 래칭을 해결하기 위해 시스템을 비상관화하는 데 많은 노력을 기울여야 한다. 넷째, 일부 디지털 함수는 매우 간단한 확률적 대응물(곱셈과 AND 게이트 사이의 변환과 같이)을 가지고 있지만, 많은 함수는 그렇지 않다. 이러한 함수를 확률적으로 표현하려고 하면 다양한 문제점이 발생할 수 있다. 예를 들어, 확률 디코딩은 함수 f(p,q)\rightarrow pq/(pq + (1-p)(1-q))의 계산을 필요로 한다. 이 함수를 계산할 수 있는 단일 비트 연산은 없으며, 일반적인 해결책은 상관된 출력 비트를 생성하는 것을 포함하는데, 이는 위에서 보았듯이 많은 문제를 일으킬 수 있다. 다른 함수(예: 평균 연산자 f(p,q)\rightarrow (p+q)/2)는 스트림의 간축(decimation) 또는 확장(inflation)을 필요로 한다. 정밀도와 메모리 간의 절충은 어려울 수 있다.
# 확률 디코딩
확률 컴퓨팅은 일반적인 계산 방법으로 고려될 때 여러 가지 결함이 있지만, 그 강점을 강조하는 특정 응용 분야가 있다. 주목할 만한 한 가지 경우는 특정 오류 정정 코드의 디코딩에서 발생한다. 확률 컴퓨팅과 관련 없는 개발에서 신뢰전파 알고리즘을 사용하는 LDPC 코드의 매우 효과적인 디코딩 방법이 개발되었다. 이 맥락에서 신뢰 전파는 두 가지 기본 연산(본질적으로 확률적 XOR 연산과 평균 연산)을 사용하여 특정 매개변수를 반복적으로 재추정하는 것을 포함한다. 2003년, 연구원들은 이 두 연산이 확률 컴퓨팅으로 매우 간단하게 모델링될 수 있음을 깨달았다. bibcode=2003ElL....39..299G 게다가 신뢰 전파 알고리즘이 반복적이기 때문에 확률 컴퓨팅은 더 빠른 수렴으로 이어질 수 있는 부분 해결책을 제공한다. 확률 디코더의 하드웨어 구현은 FPGAs에 구축되었다. year=2006 이러한 방법의 지지자들은 확률 디코딩의 성능이 디지털 대안과 경쟁할 만하다고 주장한다.
# 확률 컴퓨팅에 대한 결정론적 방법
SC 회로로 완전히 정확한 계산을 수행하기 위한 SC의 결정론적 방법이 개발되었다.doi-access=free 이 방법들의 본질적인 원리는 한 비트 스트림의 모든 비트가 다른 비트 스트림의 모든 비트와 정확히 한 번 상호작용한다는 것이다. 이 방법들로 완전히 정확한 결과를 얻으려면 연산은 입력 비트 스트림 길이의 곱만큼 실행되어야 한다. 결정론적 방법은 단항 비트 스트림,s2cid=11281124doi-access=free 유사난수 비트 스트림,doi-access=free 및 저불일치 비트 스트림doi-access=free을 기반으로 개발되었다.
# 확률 컴퓨팅의 변형
기본 확률 컴퓨팅 패러다임에는 여러 가지 변형이 있다. 더 자세한 정보는 Mars와 Poppelbaum의 참고 서적에서 찾을 수 있다. 번들 처리(Bundle Processing)는 스트림 대신 고정된 수의 비트를 전송하는 것을 포함한다. 이 접근 방식의 장점 중 하나는 정밀도가 향상된다는 것이다. 그 이유를 이해하기 위해 s개의 비트를 전송한다고 가정하자. 일반적인 확률 컴퓨팅에서는 추정치의 분산 때문에 대략 O(1/\sqrt{s})개의 다른 값을 표현할 수 있다. 번들 처리에서는 1/s의 정밀도를 표현할 수 있다. 그러나 번들 처리는 일반 확률 처리와 동일한 오류 강건성을 유지한다. 에르고딕 처리(Ergodic Processing)는 번들 스트림을 전송하는 것을 포함하며, 이는 일반 확률 처리와 번들 처리의 이점을 모두 포착한다. 버스트 처리(Burst Processing)는 증가하는 스트림을 통해 숫자를 더 높은 기저로 인코딩한다. 예를 들어, 우리는 4.3을 10진수로 다음과 같이 인코딩할 것이다. ::: 4444444555 이전 스트림의 평균값이 4.3이기 때문이다. 이 표현은 여러 가지 장점을 제공한다. 숫자가 증가하는 순서로 나타나기 때문에 무작위화가 없어 PRNG 문제가 방지되지만, 확률 컴퓨팅의 많은 장점(예: 해결책의 부분적 추정)은 유지된다. 또한 번들 및 에르고딕 처리의 선형 정밀도를 유지한다.
# 더 읽어보기
* access-date=2013-11-11 * s2cid=4689958 위키데이터 속성 추적 분류:컴퓨팅 하드웨어의 역사 분류:통계적 무작위성 분류:계산 모형