일반화된 분배 법칙

일반화된 분배 법칙(, GDL)은 분배법칙을 일반화한 것으로, 일반적인 메시지 전달 알고리즘을 발생시킨다. 이는 정보 이론, 디지털 통신, 신호 처리, 통계학, 인공지능 분야의 많은 저자들의 작업을 종합한 것이다. 이 법칙과 알고리즘은 스리니바스 M. 아지(Srinivas M. Aji)와 로버트 매켈리스(Robert J. McEliece)가 같은 제목의 준-튜토리얼에서 소개했다.

 서론 
"수학에서 분배 법칙은 곱셈과 덧셈 연산을 관련시키는 법칙으로, 기호적으로 로 표현된다. 즉, 단항식 인수 는 이항식 인수 의 각 항에 분배되거나 개별적으로 적용되어 곱 를 생성한다" - 브리태니커.

정의에서 알 수 있듯이, 산술식에 분배 법칙을 적용하면 연산의 수가 줄어든다. 이전 예에서 총 연산 수는 세 개(에서 두 개의 곱셈과 하나의 덧셈)에서 두 개(에서 하나의 곱셈과 하나의 덧셈)로 줄었다. 분배 법칙의 일반화는 많은 고속 알고리즘을 탄생시킨다. 여기에는 FFT와 비터비 알고리즘이 포함된다.

이는 아래 예에서 더 형식적으로 설명된다.

 여기서 와 는 실수 값 함수이고, 이며 (가령)

여기서 우리는 독립 변수(, , )를 "주변화(marginalizing out)"하여 결과를 얻는다. 계산 복잡도를 계산할 때, 의 각 쌍에 대해 삼중항 로 인해 개의 항이 존재하며, 각 단계에서 하나의 덧셈과 하나의 곱셈을 포함하여 의 평가에 참여해야 함을 알 수 있다. 따라서 필요한 총 계산 수는 이다. 그러므로 위 함수의 점근적 복잡도는 이다.

방정식의 RHS에 분배 법칙을 적용하면 다음을 얻는다.

 

이는 가 곱 로 설명될 수 있음을 의미한다. 여기서 이고 

이제 계산 복잡도를 계산할 때, 와 각각에 개의 덧셈이 있고, 곱 를 사용하여 를 평가할 때 개의 곱셈이 있음을 알 수 있다. 따라서 필요한 총 계산 수는 이다. 그러므로 를 계산하는 점근적 복잡도는 에서 로 줄어든다. 이는 분배 법칙을 적용하는 것이 계산 복잡도를 줄여 "고속 알고리즘"의 좋은 특징 중 하나임을 예시로 보여준다.

 역사 
분배 법칙을 사용하여 해결된 문제 중 일부는 다음과 같이 분류할 수 있다.

 디코딩 알고리즘: GDL과 유사한 알고리즘이 갤러거(Gallager)에 의해 저밀도 패리티 검사 부호(low density parity-check codes) 디코딩에 사용되었다. 갤러거의 작업을 기반으로 태너(Tanner)는 태너 그래프를 도입하고 갤러거의 작업을 메시지 전달 형식으로 표현했다. 태너 그래프는 비터비 알고리즘을 설명하는 데도 도움이 되었다. 포니(Forney)는 컨볼루션 부호에 대한 비터비의 최대 우도 디코딩(maximum likelihood decoding) 또한 GDL과 유사한 일반성의 알고리즘을 사용했음을 관찰했다.
 전방향-후방향 알고리즘: 전방향-후방향 알고리즘은 마르코프 연쇄에서 상태를 추적하는 알고리즘으로 도움이 되었다. 그리고 이것 또한 GDL과 유사한 일반성의 알고리즘으로 사용되었다.
 인공지능: 결합 트리의 개념은 AI의 많은 문제를 해결하는 데 사용되었다. 또한 버킷 제거의 개념도 많은 개념을 사용했다.

 MPF 문제 
MPF 또는 곱 함수 주변화(marginalize a product function)는 이산 아다마르 변환, 무기억 채널을 통한 선형 부호의 최대 우도 디코딩, 행렬 연쇄 곱셈과 같은 많은 고전적인 문제를 특수한 경우로 포함하는 일반적인 계산 문제이다. GDL의 힘은 덧셈과 곱셈이 일반화되는 상황에 적용된다는 사실에 있다.

가환 반환은 이러한 동작을 설명하는 좋은 프레임워크이다. 이는 집합 에서 연산 ""와 ""를 사용하여 정의되며, 여기서 와 는 가환 모노이드이고 분배 법칙이 성립한다.

을 변수라고 하자. 여기서 이고 는 유한 집합이며 이다. 여기서 이다. 만약 이고 이면,
, ,
, , 그리고

라고 하자. 여기서 이다. 함수가 로 정의된다고 가정하자. 여기서 은 가환 반환이다. 또한, 는 지역 도메인(local domains)으로, 는 지역 커널(local kernels)로 명명된다.

이제 전역 커널(global kernel) 는 다음과 같이 정의된다: 

MPF 문제의 정의: 하나 이상의 인덱스 에 대해, 전역 커널 의 -주변화(marginalization) 값 테이블을 계산한다. 이는 로 정의된 함수로 이다.

여기서 는 에 대한 의 여집합이고, 는 목표 함수 또는 에서의 목표 함수라고 불린다. 목표 함수의 계산은 명백한 방법으로 연산이 필요하다는 것을 알 수 있다. 이는 목표 함수의 계산에 개의 덧셈과 개의 곱셈이 필요하기 때문이다. 다음 섹션에서 설명할 GDL 알고리즘은 이러한 계산 복잡도를 줄일 수 있다.

다음은 MPF 문제의 예이다.

 및 를 변수라고 하자. 여기서 및 이다. 여기서 이고 이다. 이 변수들을 사용하여 정의된 함수는 와 이며, 우리는 다음과 같이 정의된 와 를 계산해야 한다.

 

 

여기서 지역 도메인과 지역 커널은 다음과 같이 정의된다.

여기서 는 목표 함수이고 는 목표 함수이다.

이고 가 실수 값 함수인 또 다른 예를 생각해보자. 이제, 교환 가능한 반환(commutative semiring)이 일반적인 덧셈과 곱셈을 가진 실수의 집합으로 정의되는 MPF 문제를 고려할 것이며, 지역 도메인과 지역 커널은 다음과 같이 정의된다.

이제 전역 커널은 지역 커널의 곱으로 정의되므로, 다음과 같다.

 

그리고 지역 도메인 에서의 목표 함수는 다음과 같다.

 

이것은 함수 의 아다마르 변환이다. 따라서 아다마르 변환의 계산이 MPF 문제의 특수한 경우임을 알 수 있다. 위에서 설명했듯이 MPF 문제가 많은 고전적인 문제의 특수한 경우를 형성한다는 것을 입증하기 위해 더 많은 예를 제시할 수 있으며, 자세한 내용은 다음에서 찾을 수 있다.

 GDL: MPF 문제를 해결하기 위한 알고리즘 
주어진 집합 의 요소들 사이에 관계를 찾을 수 있다면, "메시지 전달" 기술의 특별한 용법인 신뢰전파의 개념을 기반으로 MPF 문제를 해결할 수 있다. 필요한 관계는 주어진 지역 도메인 집합이 결합 트리로 구성될 수 있다는 것이다. 다시 말해, 의 요소를 트리 의 정점으로 사용하여 그래프 이론적 트리를 생성하는데, 임의의 두 정점 와 (단 이고 이 두 정점 사이에 간선이 존재함)에 대해, 해당 레이블의 교집합, 즉 가 에서 까지의 유일한 경로에 있는 각 정점의 레이블의 부분 집합이 되도록 한다.

예를 들어,

예시 1: 다음 아홉 가지 지역 도메인을 고려해 보자.

 
 
 
 
 
 
 
 
 

위에서 주어진 지역 도메인 집합에 대해 다음과 같이 결합 트리를 구성할 수 있다.

center|주어진 집합에 대한 결합 트리의 예시

마찬가지로 다음과 같은 또 다른 집합이 주어진다면

예시 2: 다음 네 가지 지역 도메인을 고려해 보자.

 
 
 
 

이러한 지역 도메인만으로 트리를 구성하는 것은 불가능하다. 이 값 집합에는 위 집합의 어떤 두 값 사이에도 배치할 수 있는 공통 도메인이 없기 때문이다. 하지만, 아래와 같이 두 개의 더미 도메인을 추가하면 업데이트된 집합을 결합 트리로 구성하는 것이 가능하고 쉽다.

5.,
6.,

마찬가지로 이러한 도메인 집합에 대한 결합 트리는 아래와 같이 보인다.
center|결합 트리의 또 다른 예시

 일반화된 분배 법칙(GDL) 알고리즘 
입력: 지역 도메인 집합.
출력: 주어진 도메인 집합에 대해, 문제를 해결하는 데 필요한 최소 연산 수를 계산한다.
따라서, 와 가 결합 트리에서 간선으로 연결되어 있다면, 에서 로의 메시지는 함수로 주어지는 값의 집합/테이블이다: :. 시작 시 모든 함수, 즉 주어진 트리의 모든 와 의 조합에 대해 는 항등적으로 로 정의되며, 특정 메시지가 업데이트될 때 아래 주어진 방정식을 따른다.

 = 

여기서 는 가 트리에서 의 인접 정점임을 의미한다.

마찬가지로 각 정점은 함수 에서 값을 포함하는 테이블로 정의된 상태를 가진다. 메시지가 항등적으로 1로 초기화되는 것처럼, 의 상태는 지역 커널 로 정의되지만, 가 업데이트될 때마다 다음 방정식을 따른다.

 

 알고리즘의 기본 작동 
입력으로 주어진 지역 도메인 집합에 대해, 먼저 집합을 직접 사용하거나 더미 도메인을 추가하여 결합 트리를 생성할 수 있는지 알아낸다. 만약 결합 트리 생성이 불가능하면, 알고리즘은 주어진 방정식 문제를 계산하기 위한 단계 수를 줄일 방법이 없다고 출력한다. 하지만 결합 트리가 있으면, 알고리즘은 메시지를 스케줄링하고 상태를 계산해야 한다. 이를 통해 단계 수를 줄일 수 있는 지점을 알 수 있으므로, 아래에서 논의할 것이다.

 메시지 전달 및 상태 계산의 스케줄링 

여기서 다룰 두 가지 특수한 경우가 있다. 하나는 목표 함수가 단 하나의 정점 에서 계산되는 단일 정점 문제(Single Vertex Problem)이고, 다른 하나는 모든 정점에서 목표 함수를 계산하는 것이 목표인 모든 정점 문제(All Vertices Problem)이다.

단일 정점 문제부터 시작하자. GDL은 각 간선을 대상 정점 방향으로 지정하는 것으로 시작한다. 여기서는 메시지가 대상 정점 방향으로만 한 번만 전송된다. 메시지는 잎 노드(Degree가 1인 노드)에서 시작하여 대상 정점 방향으로 이동한다. 메시지는 잎에서 부모로, 그리고 거기서부터 다시 부모로 계속 이동하여 대상 정점 에 도달한다. 대상 정점 은 모든 이웃 노드로부터 모든 메시지를 받은 후에만 상태를 계산한다. 상태를 얻으면 답을 얻은 것이므로 알고리즘이 종료된다.

예를 들어, 위에 주어진 지역 도메인 집합, 즉 예시 1의 집합으로 구성된 결합 트리를 고려해 보자.이제 이 도메인에 대한 스케줄링 테이블은 다음과 같다(대상 정점은 ).

따라서 단일 정점 GDL의 복잡도는 다음과 같이 표현될 수 있다.

 산술 연산
여기서 (참고: 위 방정식에 대한 설명은 이 문서 뒷부분에 설명되어 있다.)
는 의 레이블이다.
는 의 차수 (즉, 에 인접한 정점의 수)이다.

모든 정점 문제를 해결하기 위해 GDL을 여러 가지 방법으로 스케줄링할 수 있다. 그중 일부는 병렬 구현으로, 각 라운드에서 모든 상태가 업데이트되고 모든 메시지가 동시에 계산 및 전송된다. 이러한 유형의 구현에서 상태와 메시지는 트리의 지름(diameter)과 같거나 그 이하의 라운드 후에 안정화된다. 이 시점에서 모든 정점의 모든 상태는 원하는 목표 함수와 동일해진다.

이 문제에 대한 GDL을 스케줄링하는 또 다른 방법은 직렬 구현이다. 이는 단일 정점 문제와 유사하지만, 필요한 집합의 모든 정점이 모든 이웃으로부터 모든 메시지를 받고 자신의 상태를 계산할 때까지 알고리즘을 멈추지 않는다는 점이 다르다.
따라서 이 구현에 필요한 산술 연산의 수는 최대 개이다.

 결합 트리 구성 
결합 트리를 구성하는 핵심은 지역 도메인 그래프 에 있다. 이는 개의 정점 을 가진 가중치 있는 완전 그래프이다. 즉, 각 지역 도메인에 대해 하나의 정점이 있으며, 간선 의 가중치는 다음과 같이 정의된다.
.
만약 이면, 가 에 포함된다고 말한다. ( 의 최대 가중치 신장 트리의 가중치)는 다음과 같이 정의된다.

 

여기서 n은 해당 집합의 요소 수이다. 더 명확하고 자세한 내용은 다음을 참조하라.

스케줄링 정리

를 정점 집합 와 간선 집합 를 가진 결합 트리라고 하자. 이 알고리즘에서 메시지는 어떤 간선에서든 양방향으로 전송되므로, 간선 집합 E를 순서쌍 정점의 집합으로 간주할 수 있다. 예를 들어, 그림 1에서 는 다음과 같이 정의될 수 있다.

 

참고:는 트리를 통해 메시지가 이동할 수 있는 모든 가능한 방향을 나타낸다.

GDL의 스케줄은 의 부분집합으로 이루어진 유한 수열로 정의된다. 이는 일반적으로 다음과 같이 표현된다.
{}, 여기서 은 알고리즘 실행의 라운드 동안 업데이트된 메시지 집합이다.

몇 가지 표기법을 정의/확인했으니, 정리가 무엇을 말하는지 살펴보자. 스케줄 이 주어지면, 해당 메시지 트렐리스는 정점 집합이 인 유한 방향 그래프로, 일반적인 요소는 에 대해 로 표시된다. 메시지 전달 완료 후, 정점 에서의 상태는 다음에 정의된 목표가 된다.

 

그리고 iff 에서 로의 경로가 존재한다.

 계산 복잡도 
여기서는 계산에 필요한 수학적 연산의 수로 MPF 문제 해결의 복잡도를 설명하고자 한다. 즉, 일반적인 방법(여기서 일반적인 방법이란 메시지 전달이나 결합 트리를 사용하지 않는 방법, 요컨대 GDL의 개념을 사용하지 않는 방법)과 일반화된 분배 법칙을 사용한 방법 간에 필요한 연산 수를 비교한다.

예시: 와 같은 표현을 계산해야 하는 가장 간단한 경우를 고려해 보자.

이 표현을 순진하게 평가하려면 두 번의 곱셈과 한 번의 덧셈이 필요하다. 분배 법칙을 사용하여 표현하면 로 쓸 수 있으며, 이는 연산 수를 한 번의 덧셈과 한 번의 곱셈으로 줄이는 간단한 최적화이다.

위에 설명된 예시와 유사하게, GDL을 적용하여 가능한 한 적은 연산을 수행하도록 방정식을 다른 형태로 표현할 것이다.

이전 섹션에서 설명했듯이, 우리는 결합 트리 개념을 사용하여 문제를 해결한다. 이러한 트리를 사용하여 얻은 최적화는 트리에서 반군 문제를 해결하여 얻은 최적화와 비교할 수 있다. 예를 들어, 일련의 숫자 중 최소값을 찾으려면 트리가 있고 요소가 모두 트리 바닥에 있을 때, 두 항목의 최소값을 병렬로 비교하고 결과 최소값은 부모에게 기록된다. 이 과정이 트리를 따라 위로 전파되면 그룹 요소의 최소값이 루트에서 발견될 것이다.

메시지 전달을 사용하여 결합 트리를 해결하는 복잡도는 다음과 같다.

이전에 사용된 공식을 다음 형태로 다시 작성한다. 이는 정점 v에서 w로 메시지를 보낼 때 사용되는 방정식이다.

 ----메시지 방정식

마찬가지로, 정점 v의 상태를 계산하는 방정식을 다음과 같이 다시 작성한다.

 

먼저 단일 정점 문제에 대해 분석하고, 대상 정점을 라고 가정하며, 따라서 에서 로의 간선이 하나 존재한다.
간선 가 있다고 가정하고, 메시지 방정식을 사용하여 메시지를 계산한다. 를 계산하는 데는 다음이 필요하다.

 

덧셈과

 

곱셈.

(를 로 나타낸다.)

그러나 에 대해 많은 가능성이 있을 것이므로 
개의 에 대한 가능성.
따라서 전체 메시지에는 다음이 필요하다.

 

덧셈과

 
곱셈.

트리의 간선을 따라 를 향해 메시지를 보내는 데 필요한 총 산술 연산은 다음과 같다.

 

덧셈과

 

곱셈.

모든 메시지가 전송되면, 에서의 상태 계산으로 알고리즘이 종료된다. 상태 계산에는 개의 곱셈이 추가로 필요하다.

따라서 상태를 계산하는 데 필요한 계산 수는 다음과 같다.

 

덧셈과

 

곱셈.

따라서 총 계산 수는 다음과 같다.

 ----

여기서 는 간선이며, 그 크기는 로 정의된다.

위 공식은 상한을 제공한다.

만약 간선 의 복잡도를 다음과 같이 정의한다면,

 

따라서 은 다음과 같이 쓸 수 있다.

 

이제 그림 1에서 정의된 문제에 대한 간선 복잡도를 다음과 같이 계산한다.

 
 
 
 
 
 
 
 

총 복잡도는 로, 직접적인 방법(여기서 직접적인 방법이란 메시지 전달을 사용하지 않는 방법을 의미한다. 직접적인 방법을 사용한 시간은 각 노드에서 메시지를 계산하고 각 노드의 상태를 계산하는 시간과 동일할 것이다)에 비해 상당히 낮다.

이제 모든 정점 문제를 고려한다. 여기서 메시지는 양방향으로 전송되어야 하며, 두 정점에서 모두 상태가 계산되어야 한다. 이는 가 소요되지만, 사전 계산을 통해 곱셈 횟수를 로 줄일 수 있다. 여기서 는 정점의 차수이다. 예: 개의 숫자로 구성된 집합 가 있다면, 중 개의 모든 곱을 명백한 대신 최대 개의 곱셈으로 계산할 수 있다.
이는 와 를 사전 계산하여 수행하며, 이는 개의 곱셈을 필요로 한다. 그런 다음 가 를 제외한 모든 의 곱을 나타낸다면, 등이 또 다른 개의 곱셈을 필요로 하여 총 가 된다.

결합 트리 구성에 있어서는 우리가 할 수 있는 일이 많지 않다. 단지 많은 최대 가중치 신장 트리가 있을 수 있으며, 가장 적은 를 가진 신장 트리를 선택해야 한다는 점만 기억하면 된다. 때로는 이를 위해 결합 트리 복잡도를 낮추기 위해 지역 도메인을 추가해야 할 수도 있다.

GDL은 지역 도메인이 결합 트리로 표현될 때만 정확한 것처럼 보일 수 있다. 하지만 사이클이 존재하고 여러 번 반복되는 경우에도 메시지는 목표 함수와 거의 같아진다. 저밀도 패리티 검사 코드에 대한 Gallager–Tanner–Wiberg 알고리즘 실험은 이러한 주장을 뒷받침했다.

 각주 

분류:알고리즘
분류:정보 이론
분류:디지털 신호 처리
분류:그래프 모형