블라후트-아리모토 알고리즘

Blahut-Arimoto 알고리즘이라는 용어는 종종 채널의 정보 이론적 용량, 소스의 비율-분산 함수 또는 소스 인코딩(즉, 중복 제거를 위한 압축)을 숫자로 계산하기 위한 알고리즘의 클래스를 가리키기 위해 사용된다. 그것들은 결국 이러한 정보 이론적 개념과 연관된 최적화 문제의 최대치 중 하나로 수렴되는 반복 알고리즘이다. 문제는 비컨벡스(nonvex)이므로 로컬 최대값에 걸리지 않도록 충분한 초기화가 필요하다.

개요

일반적으로 알고리즘은 머신러닝(제프리 힌튼이 소개한)에서 (제한/비파르타이트) 볼츠만 머신(예: "접힌" 깊은 믿음 네트워크)의 훈련과 강한 유사성을 보여준다. 방정식과 관련하여, 대조적 분산을 갖는 Gibbs Sampling(물리학에서 차용한 개념과 지수적 가족을 훈련시키기 위해 사용되는 베이지안 통계학)과 강하게 관련되어 있다. 머신러닝에 대한 연결은 "코드"(또는 정보의 효율적인 표현)에 확률밀도함수(pdf) (용량용) 또는 미지의 pdf에서 도출된 데이터(머신학습용)에 대한 관련 정보만 포함하고 있다는 사실이며, 이는 모델 파라미터를 최소화에 맞춰 조정함으로써 학습해야 한다.e 예상 왜곡

반복하는 동안 일반적으로 계산하기 어려우므로 후방에서 표본을 추출하여 근사치를 구하는 파티션 함수를 계산해야 한다. 전체 알고리즘은 (두 레이어 사이에 정보를 연속적으로 전달함으로써) 냉각 과정으로 상상할 수 있으며, 이것이 마침내 최적의 조건부(균형) pdf에서 동결된다. "에너지에서 영감을 받은" 형식주의로 설명할 때, 그것은 그것의 지상 상태 중 하나에 도달하도록 훈련된다. 도달한 접지 상태는 초기화, 트레인니그 파라미터에 따라 달라지며 모든 경우에 결정론적이지 않다(디지털 기계의 경우 시드 값을 선택하는 즉시 결정론적임). 물리학에 기초한 해석은 훈련 중에 전달된 정보의 흐름이 가상 입자의 교환에 해당하며, 따라서 (왜곡 제약 하에서) 입력의 통계를 가능한 한 잘 재현하기 위해 두 조건부 pdfs를 구부리는 계층 사이의 힘을 최종적으로 기술하는 것일 수 있다.

이력 및 적용

채널 용량의 경우, 알고리즘은 아리모토^[1] 스구루와 리차드 블라후트에 의해 독자적으로 발명되었다.^[2] 손실 압축의 경우, 해당 알고리즘은 리처드 블라후트에 의해 발명되었다. 알고리즘은 임의의 유한한 알파벳 소스의 경우에 가장 적용할 수 있다. 그것을 더 일반적인 문제 사례로 확대하기 위해 많은 작업이 이루어졌다.^[3][4] 최근, 연속 출력과 다변량 출력을 설명하는 알고리즘 버전이 셀룰러 신호에서 응용 프로그램과 함께 제안되었다.^[5] 지시된 정보에 대한 Blahut-ARimoto 알고리즘 버전도 존재한다.^[6]

알고리즘.

지정된 기호의 확률$$ $($ ${\displaystyle x}$) {\$displaystyle p(x)}$이(가) 있는 소스 $X{\displaystyle }$ ${\displaystyle X}$이(가) 있다고 가정해 보십시오. 예상 왜곡 $⟨{\displaystyle d(x,}$${\displaystyle }$^ ${\displaystyle x\stackrel{}{}}$ ${\displaystyle )\{\backslash }$$displaystyle p({\hat {x})\$$rangle$을(를) 최소화하는 동시에 원래 신호에서$$ 압축 신호 $X{\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ ${\$$displaystyle$ ${\x}$을(를) 생성하는$$ 인코딩 $p{\displaystyle }$$(x,{\hat {x})$를 찾으십시오. $X{\displaystyle }$ ${\displaystyle X}$과 $X{\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ ${\$의 공동 확률에 걸쳐$.$ 수렴될 때까지 다음과 같은 반복을 반복함으로써 로컬로 요율 분산 기능을 최소화하는 인코딩을 찾을 수 있다.

${\displaystyle p_{t+1}({\hat {x}})=\sum _{x}p(x)p_{t}({\hat {x}x}x}x)}}$

${\displaystyle p_{t+1}({\hat {x}x} x)={\frac {p_{t}({\hat {x})\expect\d(x,{\hat {x}})}}{\sum _{\hat{x}p_{t}({\hat {x})\expect\properties d(x,{\hat {x}))}}}$

여기서 $\beta {\displaystyle }$ ${\displaystyle \beta }$은 우리가 목표로 하는 속도 변화 곡선의 기울기와 관련된 매개 변수로서, 따라서 압축 대 왜곡을 얼마나 선호하는지와 관련이 있다( ( $\beta {\displaystyle }$ ${\displaystyle$\ \}은$$압축을 더 적게 의미한다).

참조