数理解析研究所講究録 1420 巻 2005 年 206-215206

周辺分布の高速近似計算と誤り訂正
渋谷 智治

Tomoharu Shibuya
独立行政法人メディア教育開発センター研究開発部

R&D Department, National Institute of Multimedia Education

1

まえがき

誤り訂正符号とは, 情報を送信する側において送信情報に冗長を付加することによって, 通信路で生じた誤りを受信側において訂正することを可能にする符号化の技術である. 1990 年代初頭に開発された
ターボ符号 [1] や, 1960 年代初頭に提案され [4] その後再発見された low-density parity-check (LDPC)
符号 [7] は誤り訂正符号の一クラスであり, 誤り訂正符号の性能限界 (シャノン限界 [2]) をほぼ達成する

符号クラスであることから, 近年多くの研究者の注目を集めている. これらの符号が高い性能を示す鍵
は, belief propagation[8] や, それと本質的に等価な sum-product アルゴリズム [3] に基づく復号法と, sum-product アルゴリズムによる計算の近似精度が向上するような符号構成とにある [7].
信頼性の高い通信を実現するためには, 実際に送信したビットと受信側で推定したビットとが異なる
確率 (誤り率) を最小にするような復号戦略をとることが望ましい. このような復号を実現するためには, 受信系列を条件とする送信符号語の条件付確率 (事後確率) を各送信ビットごとに周辺化する手続きが必要となるが, この手続きは一般に符号長の指数関数に比例する計算量を必要とする. このため実際の情報通信でこのような復号法が採用されることはほとんど無く, 上述した周辺化計算をより少ない計
算量で精度良く近似するための代替アルゴリズムがこれまでに数多く提案されてきた. その一つである
sum-product アルゴリズムは, 符号化の際に織り込まれた送信ビット間の依存関係に注意しながら局所的な和積計算を積み重ねることによって, 符号長に比例する計算量で事後確率の周辺分布をきわめて精度良く近似することが可能である.
本稿では, まず, sum-product アルゴリズムの概要を紹介し, その導出について説明する. また, それと同時に, sum-product アルゴリズムによって計算された周辺分布の近似値が, ある条件下では真の周辺分布に一致することを示す. さらに, sum-product アルゴリズムの応用として, 線形符号の誤り訂正アルゴリズムを紹介する. 最後に,ダイバージェンスに密接に関わるある評価関数の極値探索アルゴリズ
ムとして sum-product アルゴリズムが解釈できることを紹介する.
$\mathrm{K}\mathrm{L}$2

誤り訂正符号
本章では, 無記憶通信路上で生じた誤りを線形符号を用いて訂正する原理について説明する. なお, 情報通信における誤り訂正問題の一般的なモデル化については, 情報理論や符号理論の教科書 [2, 6, 9] を参
照のこと.

2.1
$n$

線形符号
を自然数とし, F2 $=\{0,1\}$ を二つの要素からなる体とする. 囎の F22 線形部分空間

長 $n$ の 2 元線形符号または単に符号とよぶ.

$c\subset \mathrm{F}_{2}^{n}$

を符号

207
F22 線形空間としての

$C$

の次元を

$k$

とおく. $C$ の基底$g_{1},$ $g_{2},$$\ldots,$$g_{k}$

を行とする$k\mathrm{x}n$行列:$G:=\ovalbox{\tt\small REJECT}_{g_{k}}^{g_{1}}g_{2}..\cdot\ovalbox{\tt\small REJECT}$を考えると, $C=\{iG|i\in \mathrm{F}_{2}^{k}\}$ が成り立つ. このことから, $G$ を符号 $C$ の生成行列という. 送信情報を掛け合わせることを符号化といい, 得られた $C$ の要素 $iG$ を送信情報 に対す
に生成行列
$i$

$G$

$i\in \mathrm{F}_{2}^{k}$

る符号語という.
$C^{[perp]}$

を $C$ に直交する$C^{[perp]}:=${とする. 但し,行とする$\mathrm{F}_{2}^{n}$の元の集合:$v\in \mathrm{F}_{2}^{n}|v\cdot x=0$$v\cdot x$

は $v$ と$x$

for all $x\in C$ }の内積を表す.

$C^{[perp]}$を生成する$h_{1},$ $h_{2},$$\ldots,$$h_{m}\in \mathrm{F}_{2}^{n}$に対して, それらを行列

$m\mathrm{x}n$$H:=\ovalbox{\tt\small REJECT}_{h_{m}}^{h_{1}}h_{2}..\cdot\ovalbox{\tt\small REJECT}$を考えると, $x\in$ 鴎が符号語であるための必要十分条件は $Hx^{T}=0$ が成り立つこと, 即ち,$h_{\nu}\cdot x=0$,$\nu=1,2,$$\ldots$

(1)

, $m$

が成り立つことである. このことから, $H$ を符号 $C$ の検査行列という. また, $k,$ $m$ を符号 $C$ の情報点
数, 検査点数という. 一般に $m\geq n-k$ が成り立つ.

2.2

誤り訂正の原理

以下では $C$ を符号とし, 送信符号語および受信語をそれぞれ$(y_{1}, y_{2}, \ldots, y_{n})\in \mathcal{Y}^{n}$で表す. 但し$\mathcal{Y}$$x=(x_{1}, x_{2}, \ldots, x_{n})\in C,$

は通信路の出カアルファベットを表す. また,$m\mathrm{x}n$

行列

$y=$

$H=(h_{\nu i})$を $C$ の検査行列とし, $H$ に対して,
$B_{i}:=\{I/|h_{\nu i}=1\}$ ,$A_{\nu}:=\{i|h_{\iota/i}=1\}$$\{$$\nu=1,2,$ $\ldots,m$$i=1,2,$$\ldots,$

,

$n$

と定める.
送信符号語は $C$ から一様に選ばれるものとする.

(式 (1)) が,$A_{\nu}$$x\in \mathrm{F}_{2}^{n}$

が $C$ の符号語であるための必要十分条件

を用いて $\sum_{i\in A_{\nu}}x_{i}=0(\nu=1,2, \ldots, m)$ と表せることに注意すると,$x\in \mathrm{F}_{2}^{n}$の事前分

布 $P(x)$ は$P(x)= \frac{1}{|C|}\prod_{\iota’=1}^{m}\delta(\sum_{i\in A_{\nu}}x_{i},$$0)$と表せる. 但し$\delta(a, b):=\{$

1, if $a=b$ ,0, if $a\neq b$

である.

一方, 通信路において誤りが生じる過程は, 条件付確率 $P(y|x)$ で表される. ここで, $P(y|x)=$が成り立つとき, 通信路は無記憶であるという. 以下では無記憶通信路上で通信が行われ$\prod_{i=1}^{n}P(y_{i}|x_{i})$るものとする.

208
以上の仮定の下では, 受信旅を得たときの, 送信符号語 $x\in C$ の事後分布 $P(x|y)$ は, ベイ$y\in \mathcal{Y}^{n}$ズの公式より(2)$P(x|y)= \frac{P(x)P(y|x)}{\sum_{\infty}P(oe)P(y|x)}=\kappa\prod_{\nu=1}^{m}\delta(\sum_{i\in A_{\nu}}x_{i},$ $0) \prod_{i=1}^{n}P(y_{i}|x_{i})$と表される. 但し$\kappa$は正規化定数であり,ここで, 受信側で推定した符号語$(\hat{x}_{1},\hat{x}_{2}, \ldots,\hat{x}_{n})$を満たすように定められる.

$\sum ae\in \mathrm{F}_{2}{}_{n}P(x|y)=1$$\hat{x}\in C$

が送信符号語$x$と異なる確率を最小にするためには,$\hat{x}=$を$\hat{x}=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}s\mathrm{c}P(x|y)oe\epsilon c$

で定めればよい [9]. この復号は最大事後確率 (maximum aposteriori probability, MAP) 復号とよばれる

1. 一方, 推定した各ビット$\hat{x}i\in \mathrm{F}_{2}$が送信ビット$x_{i}$と異なる確率を最小にするためには, 勾を$\hat{x}_{i}=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}x_{\mathfrak{i}}\in \mathrm{F}_{2}P(x_{i}|y)$で定めればよい [9]. ここで, $P(x_{i}|y)$ は, $P(x|y)$ の$P(x_{i}|y):= \sum_{x_{1}}\cdots\sum_{x_{\mathrm{t}-1}}\sum_{x_{\dot{\mathrm{t}}+1}}\cdots\sum_{x_{n}}P(x|y)$$x_{i}$

に関する周辺分布(3)$(=o \sum_{e\sim x}.\cdot P(oe|y))$を表す 2. この復号は周辺事後確率 (maximizer of posterior marginals, MPM) 復号とよばれる [5].

MAP 復号では,$C$の全ての符号語 (を探索する必要がある. したがって,$k$$2^{k}$

個) に対して $P(x|y)$ を評価し, その最大値を与える符号語$x$が大きな場合には現実的な時聞で MAP 復号を行うことは困難である. 一方 MPM 復号では, $P(x|y)$ の周辺化に, $2^{n-1}$ 個の$x\in \mathrm{F}_{2}^{n}$に対する $P(x|y)$ の評価とそれらの和を計算する必要があり, こちらも が大きい場合に現実的な時聞で復号を行うことは困難である.
このように, 誤り訂正における復号問題は計算量的に非常に困難な問題であるといえる. これに対し,
sum-product アルゴリズムに基づく反復復号法 $[4, 10]$ (以後, sum-product 復号法と呼ぶ) は, 符弩弓に比例する計算量で MPM 復号を精度良く近似する復号法である.
$n$

$n$

3

sum-product アルゴリズムと誤り訂正

3.1

sum-product アルゴリズ

離散値をとる確率変数$x_{1},$ $x_{2},$$\ldots,$$x_{6}$$\Lambda$の概要の同時分布 $P(x)=P(x_{1}, x_{2}, \ldots, x_{6})$ が(4)$P(oe)=f_{\alpha}(x_{1}, x_{2}, x_{3})f\beta(x_{1}, x_{4})f_{\gamma}(x_{4},x_{5})f_{\delta}(x_{4}, x\epsilon)$のように分解できる場合を考える. このとき, 確率変数と因子関数の依存関係を考慮すると,$x_{1}$の周辺

分布 $P_{1}(x_{1}):= \sum_{\alpha\sim x_{1}}P(x)$ は(iv)$\sum_{x_{4}}f_{\beta}(x_{1}, x_{4})(\sum f_{\gamma}(x_{4}, x_{5}))(\sum f_{\delta}(x_{4}, x_{6}))\}\ovalbox{\tt\small REJECT}$$P_{1}(x_{1})= \{\sum_{x_{2}}o\sum_{e\mathrm{a}}f_{\alpha}(x_{1_{1}}x_{2}, x_{3})\}\{\ovalbox{\tt\small REJECT}$$\infty x_{5}$(i)$\underline{q\mathrm{i}_{6}}$$\ovalbox{\tt\small REJECT}^{(ii)(ii\mathrm{i})}$(v)

1 ここでは

2 以後,$x_{i}$

事前分布を–様と仮定ので, 最尤 (maximum likelihood,) 復号に 1 致する.
以外の全ての ‘\Re の和 $\sum_{x_{1}}\cdots\sum_{x_{i-1}}\sum_{x_{t+1}}\cdots\sum_{x_{n}}$ を\mbox{\boldmath $\tau$}. 表す.
$x\text{の}$$\llcorner^{\sim}\mathrm{c}\iota\backslash \epsilon$$\mathrm{M}\mathrm{L}$$\sum_{\varpi\sim x_{\dot{\mathrm{t}}}}$

(5)

208

図 1: 式 (4) で与えられる $P(x)$ のファクターグラフ. ファクターグラフ上でメッセージが伝播することによって, 周辺分布の計算が実行されると解釈できる.

のように分割して計算できることが示せる, 即ち,[(1) (i1), (iii) の和]$-arrow$$,$[$(\mathrm{i}\mathrm{v})$の積]$arrow$[$(\mathrm{v})$の和]$arrow$[$(\mathrm{i})$と (v) の積]$(*)$

のとり得る値を求めることができる. ここで,の周辺分布の順番に計算することによって,回の $P(x)$ の評価がの個数をで表すと, 式 (3) のような単純な周辺化ではおよその計算に必要であるのに対し, 式 (5) ではおよそ $n_{2}n_{3}+n_{4}(n_{5}+n_{6})$ 回の因子関数の評価で十分である$P_{1}(x_{1})$$x_{1}$$x_{i}$$P_{1}(x_{1})$$n_{2}n_{3}n_{4}n\mathrm{s}n_{6}$$n_{i}$

ことがわかる. すなわち, 式 (5) に基づいた周辺分布計算の方が効率的である. このように, 与えられた確率分布を, 局所的な変数集合に対する和とその結果の積に分解して周辺分布計算の高速化を図るのが,sum-product アルゴリズムの基本原理である $[3, 8]$ .
一般に $P(x)(x=(x_{1}, x_{2}, \ldots, x_{n}))$ が(6)$P(x)= \kappa\prod_{\nu=1}^{m}f_{\nu}(oe_{1/})$の変数の集合を表す. また, は正規化定数である.
はと因数分解される場合を考える. 但し,, x 訂,
をラベルとするノードの集合 $V,$ $F$ をそれぞれ $V:=\{x_{1},$式 (6) の分解に対し,$x_{i},$$F:=\{f_{1}, f_{2)}\ldots, f_{m}\}$$\kappa$$f_{\nu}$$x_{\nu}$$x_{2},$$f_{\nu}$で定める. 一方, 枝集合 $E\subset V\mathrm{x}F$ を,$x_{i}\in x_{\nu}$

かつそのときに限り$\ldots$$(x_{i}, f_{\nu})\in E$

は, $P(x)$ の (式 (6) の因数分解に関, 関数ノーする) ファクターグラフ (factor graph) と呼ばれる. また $V,$ $F$ の要素をそれぞれ変数とすることによって定める. このとき, 二部グラフ$\mathcal{G}=(V\cup F, E)$$\text{ノ}-\vdash.$ドと呼ぶ
図 1 に式 (4) のファクターグラフを示す. この図からわかるように, ファクターグラフを用いることによって, 因数分解における変数と因子関数の関係を視覚化することができる. さらに, 図 1 のようにファクターグラフがループを含まない場合, $(*)$ で記述される式 (5) の計算は, ファクターグラフの端点から開始し, ノードの配列に従って全てのノードに行き渡るまで局所的な和積計算を繰り返すことによって実現されると考えることができる.
ここで, $(*)$ における局所的な和積計算の結果をそれぞれ,
ヤージ $(m_{\nuarrow i}(x_{i})),$$\text{ノ}-\vdash^{\backslash ^{\backslash }}x_{i}$からノード$f_{\nu}$

ノードんからノードへ送られるメッセージ$(m_{i\prec\nu}(x_{i}))$$x_{i}$^送られるメッであると考える.

このとき, $(*)$ で記述される —\\llcorner の計算は, 図 1 に示すようにあたかもファクターグラフ上をメッセージが伝播することによって実行されているようにみなすことができる.
$(*)$の和積計算を一般化すると, 次章で示すように, 各ノード聞で受け渡しされるメッセージ$m_{\dot{\mathrm{t}}arrow\nu}(x_{i})$$m_{\nuarrow i}(x_{i})$,を計算するアルゴリズム :(7)$m_{\nuarrow i}(x_{i}):=o \sum_{e_{\nu}\sim xj}f_{\nu}(x_{\nu})\prod_{i’\in N(\nu)\backslash \{i\}}m_{i’arrow\nu}(x_{i^{\prime)}}\}$$m_{iarrow\nu}(x_{i}):= \prod_{\nu’\in N(i)\backslash \{\nu\}}m_{\nu’arrow i}(x_{i})$が導かれる. さらに, グラフの端点からメッセージを逐次計算し, 全ての$\nu\in N(\mathrm{i})$に対して$m_{\nuarrow i}(x_{i})$21$\mathfrak{g}$が得られた時点で(8)$m_{\nuarrow i}(x_{i})$$\prod$$Q_{i}(x_{i}):= \kappa_{i}\prod_{\nu\in N\langle i)}m_{\nuarrow i}(x_{i})$$Q_{i}(x_{i}):=\kappa_{i}$$\nu\in N\langle i)$$N(\nu)$ はファクターグラフにおけるは正規化定数,に隣接する変数ノードのインデックスを表す.
ノード x\sim こ隣接する関数ノードおよびノードに一致することが示される. 一方, ファはファクターグラフにループがない場合にはによって定められる分布を考える. ここで,$N(\mathrm{i}),$$\kappa_{i}$$f_{\nu}$$P_{i}(x_{i})$$Q_{i}(x_{i})$クターグラフがループを含む場合には, グラフの端点からメッセージを逐次計算していくと, ある時点で既に計算済みのメッセージを再計算する場合が生じる. つまり, 再計算のたびにメッセージの値が変化する可能性があるため, 式 (8) の値が定まる保証はなく, 従って式 (8) が真の周辺分布を与える保証はない.
しかしながら, ループの長さが比較的大きな場合には, 全メッセージを式 (7) に従って同期的に反復更を定めることにより, 周辺分布
新し, さらにメッセージの収束値を式 (8) に代入して似が求まることが期待される. これが, 一般の分布に対する sum-product アルゴリズムである.

$P_{i}(x_{i})$$Q_{i}(x_{i})$

3.2

の近

sum-product アルゴリズムの導出

本節では, $P(x)$ のファクターグラフにループが含まれないとき, 式 (7), (8) で記述される sum-productがに一致することを示す.
の周辺分布
アルゴリズムが与える軌のように因数分解されているものとする. $P(x)$ のファクターグラフ $\mathcal{G}=(V\cup F, E)$ に$P(x)$ が式 (6)$(x_{i})$

ループが含まれない場合,
きる. さらに

数ノード$x_{i}$$x_{i}$$\mathcal{G}$に対して$P_{i}(x_{i})$$x_{i}$の変数ノード$\iota/\in N(\mathrm{i})$を根とし関数ノード$f_{\nu}$$x_{i}$

に対して,$\mathcal{G}$を$x_{i}$を根 (root) とする木とみなすことがでを一つ定めると, にループがないことから,を含む の木が唯一っ定まる. この木を$\mathcal{G}$$V(\mathrm{i}, \nu),$$\cup$$V(i, \nu)=\{1,2, \ldots, n\}$,$\cup$の部分グラフで, 変$T(\mathrm{i}, \nu)$$\mathcal{G}$

含まれる変数ノードおよび関数ノードのインデックスの集合をそれぞれ
容易に確認できるように, 全ての変数ノード $x_{i}(\mathrm{i}=1,2, \ldots, n)$ に対して$\nu\in N(i)$$\mathcal{G}$で表し, $T(i, \nu)$ に$F(\mathrm{i}, \nu)$

で表す.

(9)

$F(\mathrm{i}, \nu)=\{1,2, \ldots,m\}$$\nu\in N(i)$が成り立つ. また, $N(i)$ の互いに異なる二つの要素$V(i, \nu_{1})\cap V(i, \nu_{2})=\emptyset$,$\nu_{1},$$\nu_{2}$

に対して

(10)

$F(i, \nu_{1})\cap F(\mathrm{i}, \nu_{2})=\{\mathrm{i}\}$が成り立つ.
命題 1 分布 $P(x)$ が式 (6) のように分解されているものとする.
$m_{\nuarrow i}(x_{i}):= \sum_{\ddagger x_{i’}:i’\in V(i_{1}J)\backslash \{i\}}f_{\nu}(x_{\nu})\prod_{\nu’\in F(i,\nu)\backslash \{\nu\}}f_{\nu’}(x_{\nu’})$

とおくと, $P(x)$ のファクターグラフにループが存在しないとき,$P_{i}\langle x_{i}$立つ.

(証明) 式 (9), (10) の関係に注意すると,$P_{i}(x_{i})= \kappa o\sum_{e\sim x_{\dot{\mathrm{t}}}}\prod_{\nu=1}^{m}f_{\nu}(x_{\nu})$$= \kappa\sum$$\prod$$\prod$$f_{\nu’}(x_{\nu’})$$i\mathrm{r}\sim x_{\dot{\mathrm{a}}}\nu\in N(i)\nu’\in F(i,\nu)$$= \kappa\prod_{\nu\in N(i)}(\sum_{x_{i’}:i^{l}\in V(i,\nu)\backslash \{i\}}\prod_{\nu’\in F(i,\nu)}f_{\nu’}(x_{\nu’}))$$= \kappa\prod_{\nu\in N(i)}(.\sum_{x_{\^{l}}:i’\in V(i,\nu)\backslash \{i\}}f_{\nu}(i\mathrm{r}_{\nu})\prod_{\nu’\in F(i,\nu)\backslash \{\nu\}}f_{\nu’}(x_{\nu’}))$$= \kappa\prod_{\nu\in N(i)}m_{\nuarrow i}(x_{i})$)$= \kappa\prod_{\nu\in N(i)}m_{\nuarrow i}(x_{i})$

が成り

211
を得る.

口

$m_{\nuarrow i}(x_{i})$の定義および命題 1 から,$T(\mathrm{i}, \nu)$の周辺分布の計算は,$\mathcal{G}$の各部分グラフに$T(\mathrm{i}, \nu)(\nu\in N(\mathrm{i}))$(x のの計算に分割できることがわかる. さらに, 次の命題は, これらのメッセー
内のメッセージのみを用いた漸化式によって表されることを示している.

おけるメッセージ
ジが$x_{i}$$m_{\nuarrow i}$

命題 2 分布 $P(x)$ が式 (6) のように分解されているものとする. $P(x)$ のファクターグラフにループが存在しないとき$m_{l/arrow i(x_{i})=o\sum_{e_{U}\sim x_{i}}f_{\nu}(x_{\nu})\prod_{i’\in N(\nu)\backslash \{i\}}\prod_{\nu’\in N(i^{J})\backslash \{\nu\}}m_{\nu’arrow i’}(x_{i’})}$

が成り立つ.

(証明) $V(i, \nu),$$F(\mathrm{i}, \nu)$の定義より$F(i, \nu)\backslash \{\nu\}=\cup\cup F(\mathrm{i}’, \nu’)i’\in N(\nu)\backslash \{i\}\nu’\in N(i’)\backslash \{\nu\}$および$V(\mathrm{i}, \nu)\backslash \{\mathrm{i}\}=(N(\nu)\backslash \{\mathrm{i}\})\cup(_{i’\in N(\nu)\backslash \{i\}\nu’\in N(i’)\backslash \{\nu\}}\cup\cup V(\mathrm{i}’, \nu’)\backslash \{\mathrm{i}’\})$

が成り立つ. さらに, 式 (9), (10) の関係に注意すると,$m_{\nuarrow i}(x_{\dot{\mathrm{t}}})=$$\sum_{\dot{\mathrm{r}},x_{i’}:i’\in V(,\nu)\backslash \{i\}}f_{\nu}(x_{\iota/})\prod_{\nu’\in F(\dot{\mathrm{a}},\nu)\backslash \{\nu\}}f_{\mathrm{J}J’}(x_{\nu^{\prime)}}$$= \sum_{ix_{i’}:i’\in V(\iota J\mathrm{I}\backslash \{i\}},f_{\nu}(x_{\nu})\prod_{i’\in N(\nu)\backslash \{i\}}\prod_{\nu’\in N(i’)\backslash \{\nu\}}\prod_{\mu\in F(i’\nu’)},f_{\mu}(x_{\mu})$$=, \sum_{\mathrm{a}_{\nu}\sim x_{i}}f_{\nu}(oe_{\nu})\prod_{i’\in N(\nu)\backslash \{i\}\nu’\in}\prod_{\iota N(i)\backslash \{\prime\}}(\sum_{x_{l}:\ell\in V(i’,\nu’)\backslash \{i\}}h’(x_{\nu’}),\prod_{\mu\in F(i,\nu’)\backslash \{\nu’\}}f_{\mu}(x_{\mu}))$$=o \sum_{e_{\nu}\sim x_{\dot{\mathrm{t}}}}f_{\nu}(x_{\nu})\prod_{i’\in N(\nu)\backslash \{i\}}\prod_{\nu’\in N(i)\backslash \{\nu\}},m\iota/’arrow i^{;(x_{i’})}$

口

が導かれる

sum-product アルゴリズムの更新式 (7) が直ちに導かれる. また, 命題 1, 2 をあわせると, ファクターグラフの端点力 1 ら式 (7) に従ってが真の周辺分布を与えることがわかる.
メッセージを更新することにより, 式 (8) によって定まる
ここで $m_{iarrow\nu}(x_{\nu}):= \prod_{\nu\in N(i)\backslash \{\nu\}},m_{\nu’arrow i}(x_{i})$ とおくと、 命題 2 より

$Q_{i}(x_{i})$33sum-product 復号法

22 飾で述べたように, 線形符号の MPM 復号を行うためには, 式 (2) で与えられる事後確率を x\sim こつ
いて周辺化すれば良い. この周辺化を近似的に行うために sum-product アルゴリズムを適用する場合,
メッセージの更新式は$m_{\nuarrow i}$($i) $:=$$m_{i’arrow\nu}(x_{i’})$$\prod$$\sum$$\mathfrak{B}_{y}:\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\sim x_{i}i’\in A_{\nu}\backslash \{i\}$$\prod$$m_{iarrow\nu}(x_{i}):=p(y_{i}|x_{i})$$m_{\nu’arrow i}$($i)/$\nu^{J}\in B_{i}\backslash \{\nu\}$

となる.

{

$\underline{\mathrm{f}\exists}$

し,

, 重みが

$l\mathrm{f}\mathrm{f}\backslash \text{数}$$\mathrm{L}.:\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\sim oe:l\mathrm{h}$である$oe_{\nu}$に対して x 湯槽’ こつ$\mathrm{V}^{\backslash }$ての和をとることをする. また、 $P(x_{i}|y)$ の近似値は(11)$Q_{i}(x_{i}):= \kappa_{i}P(y_{i}|x_{i})\prod_{\nu\in B_{i}}m_{\nu\prec i}(x_{i})$212

図 2: sum-product 復号アルゴリズム. 受信系列の推定値を計算し, 復号結果 を出力する.

$y$に対し, sum-product アルゴリズムを用 \mbox{\boldmath $\nu$}‘て$P_{i}(x_{i}|y\}$$\hat{x}$で与えられる. 但し$\kappa_{i}$は正規化定数を表す.

図 2 に線形符号の sum-product 復号アルゴリズムの概要を示す [10].

product アルゴリズムにおいて全メッセージが同期的に更新された後に求め,$\hat{x}:=(\hat{x}_{1},\hat{x}_{2}, \ldots,\hat{x}_{n})$sum-product 復号では, sum$P_{i}(x_{i}|y)$の推定値を式 (11) で

,

$\{$

$\hat{x}_{i}:=\arg\dot{.}\max_{x}\{P_{i}(x_{i}|y)\}$により一時推定語$\hat{x}$を求める. なお, $H\hat{x}=0$ が成り立つか否かによって, あが符号語であるか否かを直ちに判定できる. そこで, sum-product アルゴリズムによるメッセージの反復計算に終了判定を組み込むことができ, 不必要な反復を省くことができる.

sum-product アルゴリズムと4$\mathrm{K}\mathrm{L}$ダイバージェンス

のある確率分布 $Q(x)$ によって確率分布 $P(x)$ を近似する場合, 近似の良し悪しを測る尺度として,ダイバージェンス:$Q(x)$ と $P(x)$ の間の$x$$\mathrm{K}\mathrm{L}$$D(Q||P):= \mathrm{a}\sum_{\mathrm{e}}Q(x)$in$\frac{Q(x)}{P(x)}$がしばしば用いられる, よく知られているように,$\mathrm{K}\mathrm{L}$ダイバージェンスは非負であり, $D(Q||P)=0$ となるための必要十分条件は $Q(oe)=P(x)$ が成り立つことである. 従って, 与えられた $P(x)$ に対して$\mathrm{K}\mathrm{L}$ダイバージェンスを小さくする $Q(x)$ は, $P(x)$ の良好な近似となることが期待される.

補題 3 与えられた分布 P(切が式 (6) のように分解されているものとする. $P(x)$ のファクターグラフ

が木ならば

I\sim (x の$:= \mathrm{a}\sum_{\mathrm{e}\sim oe_{\dot{\mathrm{t}}}}P(x)=\kappa\prod_{\nu\in N(i)}m_{\nuarrow i}(x_{i})$,$\backslash$(12)$P_{\nu}(oe_{\nu}):= \sum_{\approx\sim\alpha_{\nu}}P(x)=\kappa f_{\nu}(x_{\nu})\prod_{i\in N(\nu)}\prod_{\nu’\in N(i)\backslash \{\nu\}}m_{\nu^{J}arrow i}(x_{i})$,が成り立つ.

213(証明) 第 1 式については, sum-product アルゴリズムの結果より明らか. 第 2 式については$P_{\nu}(x_{\nu})= \kappa\sum\prod f_{\nu’}(x_{\nu’})$$oe\sim‘ \mathrm{r}_{\nu}\nu’=1$$= \kappa\sum_{\varpi\sim \mathrm{a}\mathrm{i}_{\vee}}f_{\nu}(x_{\nu})\prod_{\nu’=1,\nu’\neq\nu}^{m}f_{\nu’}(x_{l/}’)$$= \kappa a\sum_{e\sim \mathrm{o}\mathrm{e}_{\nu}}f_{\nu}(x_{\nu})\prod_{i\in N(\nu)}\prod_{\nu’\in N(i)\backslash \{\nu\}}\prod_{\mu\in F(i,\nu’)}f_{\mu}(x_{\mu})$$= \kappa f_{\nu}(x_{\nu})\prod_{i\in N(\nu)}\prod_{\nu’\in N(i)\backslash \{\nu\}}(\sum_{x_{j’}:i’\in V(i,\nu’)\backslash \{i\}}f_{\nu’}(x_{\nu’})\prod_{\mu\in F(i,\nu’)\backslash \{\nu’\}}f_{\mu}(x_{\mu}))$$= \kappa f_{\nu}(X_{\mathcal{U}})\prod_{i\in N(\nu)}\prod_{\nu’\in N(i)\backslash \{\nu\}}m_{U}!\prec i(x_{i})$.
口

命題 4 与えられた分布 $P(x)$ が式 (6) のように分解されているものとする. $P(x)$ のファクターグラフ
が木ならば$P(oe)= \kappa’\frac{\prod_{\nu=1}^{m}P_{\nu}(x_{\nu})}{\prod_{i=1}^{n}P_{i}^{|N(i)|-1}(x_{i})}$が成り立つ. 但し, \kappa 嫁ま正規化定数を表す.

(証明)$\prod_{\nu=1}^{m}\prod_{i\in N(\nu)}\prod_{\nu’\in N(i)\backslash \{\nu\}}m_{\nu’arrow i(x_{i})=\prod_{i=1}^{n}\prod_{\iota/\in N(i)}(m_{\iota/arrow i}(x_{i}))^{|N(i)|-1}}$が成り立つことに注意すると, 補題 3 の結果からん (x の $=P(x)$$. \frac{\Pi_{\nu=1}^{m}P_{\nu}(x_{\nu})}{\Pi_{\=1}^{n}P_{i}^{|N(i)|-1}(x\dot{.})}=\frac{\Pi_{\nu=1}^{m}(\kappa f\nu(x_{\mu})\Pi_{i\in N(\nu)}\Pi_{\nu’\in N(i\rangle\backslash \{\nu\}}m_{\nu’arrow i}(x_{i}))}{\Pi_{i=1}^{n}(\kappa\Pi_{\nu\in N\langle i)}m_{\nuarrow i}(x_{i}))^{|N(i)|-1}}\propto\kappa\prod_{\nu=1}^{n}$口が成り立つ.
ここで,$Q_{\nu}(x_{\nu}),$$Q_{i}(x_{i})$をそれぞれ$x_{\nu},$$x_{i}$の分布とし,(13)$Q(x)= \kappa’\frac{\prod_{\nu=1}^{m}Q_{\nu}(x_{\nu})}{\prod_{i=1}^{n}Q_{i}^{|N(i)|-1}(x_{i})}$で定義される$x$の分布を考える. 式 (6) で与えられる $P(x)$ および式 (13) で与えられる $Q(x)$ を $D(Q||P)$に代入すると$D(Q||P):= \mathrm{a}\sum_{\mathrm{e}}Q(x)\sum_{\nu=1}^{m}\log\frac{Q_{\nu}(x_{\nu})}{f_{\nu}(x_{\nu})}-o\sum_{e}Q(x)\sum_{i=1}^{n}(|N(i)|-1)Q_{i}(x_{i})\log Q_{i}(x_{i})+c$(14)は定数. ここで, P(ののファクターグラフが木であるとき, 命題 4 より, 式 (13) で与えられる $Q(x)$ で $Q(x)=P(x)$ となるものが存在する. さらに, 補題 3 より, このような $Q(x)$ に関しが成り立って る. これらの関係を式 (14) に代入すてを得る. 但し$c$$1/\backslash$$Q_{\nu}(x_{\nu})= \sum oe\sim oe_{\mathcal{U}}Q(x),$$Q_{i}(x_{i}\rangle$$= \sum \mathrm{a}\mathrm{e}\sim x:Q(x)$ると$D(Q||P)= \sum_{\nu=1}^{m}o\sum_{e_{U}}Q_{\nu}(x_{\nu})\log\frac{Q_{\nu}(x_{\nu})}{f_{\nu}(x_{\nu})}$–$\dot{\iota}(|N(\dot{x})|-1)$ $\sum_{x_{\mathrm{i}}}Q_{i}(x_{i})\log Q_{i}(x_{i})+\mathrm{c}$214となる. ここで$D^{*}(Q||P):= \sum_{\nu=1}^{m}\sum_{\Phi_{\mu}}Q_{\nu}(x_{\nu})\log\frac{Q_{\nu}(x_{\nu})}{f_{\nu}(oe_{\nu})}-\sum_{i}(|N(i\rangle|-1)\sum_{x_{i}}Q_{i}(x_{i})\log Q_{i}(x_{i})$を求めるこダイバージェンスの性質から, $D(Q||P)^{*}$ を最小化する分布が求められる. 但し,は, それらが分布となるよう,とによって, 所望の周辺分布

とおくと,$\{Q_{\nu}(x_{\nu}), Q_{i}(x_{i})\}$$\mathrm{K}\mathrm{L}$$\{Q_{\nu}(x_{\nu}), Q_{i}(x_{i})\}$$P_{i}(x_{i})$$o \sum_{e_{\nu}}Q_{\nu}(x_{\nu})=1$

,

(15)

$\sum_{x}\dot{.}Q_{i}(x_{i})=1$を満たさなければならない. さらに,

$x_{\nu}$に$x_{i}$

が含まれる場合,(16)$o \sum_{e_{\nu}\sim xj}Q_{\nu}(oe_{\nu})=Q_{i}(x_{i})$が成り立つ必要がある.
式 (15), (16) の制約の下で $D^{*}(Q||P)$ を最小化する $\{Q_{\nu}(x_{\nu}), Q_{i}(x_{i})\}$ は, $D^{*}(Q||P)$ が極値をとるための必要条件, すなわち, Lagrange 乗数形式:$L:=D^{*}(Q||P)+ \sum_{i=1}^{n}\gamma_{i}(1-\sum_{x_{\dot{\mathrm{t}}}}Q_{i}(x_{i}))+\sum_{\nu=1}^{m}\sum_{i\in N(\nu)}o\sum_{e_{i}}\lambda_{\nu i}(x_{i})(Q_{i}(x_{i})-o\sum_{e_{\nu}\backslash x_{\dot{\mathrm{z}}}}Q_{\nu}(x_{\nu}))$において$\gamma_{i},$(17)として得られる連立方程式の解として得られることが多い. ここで,は, 式 (15), (16) で与えられる各制約に対応する Lagrange 未定乗数である. なお, 式 (15) の$\frac{\theta L}{\partial Q_{i}}\overline{x\dot{.})}=0,$$\lambda_{\nu i}(x_{i})$$\frac{\partial L}{\partial Q_{\nu}(oe_{\nu})}=0$

1 番目の制約は, 2 番目の制約および式 (16) の制約から得られるため省略している. 実際にこれらの連立方程式を解くと$\sim$$Q_{i}(x_{i})= \exp[\frac{1}{|N(i)|-1}(\sum_{\nu\in N(i)}\lambda_{\nu i}(x_{i})-\gamma_{i})-1],$(18)$Q_{\nu}(x_{\nu})=f_{\nu}(x_{\nu}) \exp[\sum_{i\in N(\nu)}\lambda_{\nu i}(x_{i})-1]$

を得る.
$P(x)$ のファクターグラフが木であるとき, 式 (12), (18) において鶏 $(x_{i})=Q_{i}(x_{i}),$ $P_{\nu}(x\mapsto=Q_{\nu}(x_{\nu})$が成り立っていることに注意すると, sum-product アルゴリズムによって求められたメッセージ
および極値条件を満たす Lagrange 未定乗数
を,$miarrow\nu(x_{\mathcal{U}})$$m_{\nuarrow i}(x_{i})$,$\lambda_{\nu i}(x_{i})$$\lambda_{\nu i}=$$\sum$$\ln m_{\nu’arrow i}(x_{i})$$(=\ln m_{iarrow\nu}(x_{\nu}))$(19)$\nu^{l}\in N(i)\backslash \{\nu\}$

によって対応付けることができる [11]. 実際, 式 (19) を式 (18) に代入して整理すると$Q_{i}(x_{i})= \exp[-\frac{\gamma_{i}}{|N(\mathrm{i})|-1}-1]\exp[\frac{1}{|N(\mathrm{i})|-1}\sum_{\nu\in N(i)}\sum_{\nu’\in N(i)\backslash \{\nu\}}\ln m_{\nu’arrow i}(x_{i})]$$= \exp[-\frac{\gamma_{i}}{|N(i)|-1}-1]\exp[\frac{1}{|N(i)|-1}\sum_{\nu\in N\{i)}(|N(i)|-1)\ln m_{\nuarrow i}(x_{i})]$$= \exp[-\frac{\gamma_{i}}{|N(\mathrm{i})|-1}-1]\prod_{\nu\in N(i)}m_{\nuarrow i}(x_{i})$となり,$\gamma_{i}$を適当に定めることによって$Q_{i}$(r の $=P_{i}(x_{i})$ が確かめられる. 同様に$Q_{\nu}(x_{\nu})=f_{\nu}(x_{\nu}) \exp[\sum_{i\in N(\nu)}\sum_{\nu’\in N(i)\backslash \{\nu\}}m_{\nu^{\mathit{1}}\prec i}(x_{i})-1]=e^{-1}f_{\nu}(x_{\nu})\prod_{i\in N(\nu)}\prod_{\nu’\in N(i)\backslash \{\nu\}}m_{\nu’arrow i}(x_{i})$

215
より

$Q_{\nu}(x_{\nu})=$F\mbox{\boldmath $\nu$}(x のが確かめられる. 以上の考察から, sum-product アルゴリズムのメッセージ更新

は, 極値条件を満たす Lagrange 未定乗数の探索アルゴリズムとみなすことができる.
の $Q(x)$ に対する周辺分布とは限らない) –般のここで, 式 $Q,(x_{\nu})$ , Qi(x のを, ($x_{\nu},$ $x_{i}$$x_{\nu}\dot,$$x_{i}$の分布は P(ののファクターグラフにループがあるか否かにかかわらず定義
とおくと, 式 (17) で定義される可能な量であることがわかる. 但し, この場合には $\sum ae\sim\varpi_{\nu}Q(x)=Q_{\nu}(x_{\nu}),$ $\sum oe\sim x_{i}Q(x)=Q_{i}(x_{i})$ をダイバージェンスとなるとは限らない. しかしなが満たす $Q(x)$ の存在は保証されず, $D^{*}(Q||P)$ がダイバージェンスの近ら, $P(x)$ のファクターグラフ内のループの長さが大きければ, $D^{*}(Q||P)$ は$L$$\mathrm{K}\mathrm{L}$$\mathrm{K}\mathrm{L}$似を与えていることが期待でき,5$L$の極値条件から周辺分布の近似値を得ることができる.

むすび

本稿では, 周辺分布の高速近似計算アルゴリズムである sum-product アルゴリズムを紹介し, ファク
ターグラフが木である場合には, アルゴリズムの結果が真の周辺分布に一激することを示した. また,
sum-product アルゴリズムの応用として, 線形符号の MPM 復号問題を近似的に実現する sum-product

復号を紹介した. さらに, ふたつの分布の近さの尺度としてしばしば用いられる KL ダイバージェンスに密接に関わるある評価関数を導入すると, sum-product アルゴリズムが収束した際のメッセージとその評価関数の勾配が零となる点が一対一に対応することを見た.

参考文献[1] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding anddecoding: Turbo-codes,” Proc. of ICC (Geneva), pp.1064-1070, 1993.

[2] T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley Series in Telecommunications, Wiley, 1991.

[3] B. J. Frey, Graphical Models for Machine Learning and Digital Comrnunication, The MIT Press,

1998.
[4] R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory vol.IT-8, pp.21-28,

1962.
[5] 王金芳, 田栗正章, 手塚集, 樺島祥介, 上田修功, 計算統計 I, 確率計算の新しい手法 (統計科学のフロンティア 11), 岩波書店, 2003.
[6] J. H. van Lint, Introduction to Coding Theory. Springer-Verlag, second ed., 1991.
[7] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans.
Inform. Theory, vol.IT-45, PP.399-431, 1999.
[8] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference,
Kaufmann Publishers, 1988.

Morgan[9] J. G. Proakis, Digital Communications, 3rd. ed., McGraw-Hill, 1995.

[10] 和田山正, 低密度パリティ検査符号とその復号法, トリケップス, 2002.

and[11] J. S. Yedidia, W. T. Freeman, and Y. Weiss, “Bethe free energy, Kikuchi approximations,
Mitsubishi Electric Research Lab., TR-2001-16,
propagation algorithms,” Tech. Rep.

belief2001.

of