修 士 論 文 の 和 文 要 旨 研究科・専攻 大学院 情報理工 学研究科 情報・ネットワーク工学専攻 博士前期課程 氏 名 八田 悠司 学籍番号 1931115 論 文 題 目 劣化型放送通信路における緩和項を用いた容量域計算アルゴリズムと収束性 要 旨 情報理論分野において、通信路の論理モデルに対する情報通信の理論的限界を解明するため の研究がこれまでに数多く行われてきた。有本や Blahut によって、離散無記憶な単一通信路 に対する通信の理論限界を、具体的に数値化された通信路容量として求めるための逐次計算ア ルゴリズムが得られている。しかし、多端子通信路に対する通信路容領域を求めることのでき るアルゴリズムは未だ確立されておらず、情報理論分野における基本的未解決問題となってい る。 本論文では、1 入力 2 出力の劣化型放送通信路(DBC)に対する通信路容量域を求めるための 容領域計算アルゴリズムについて考察する。 安井は DBC の容領域を求める Arimoto-Blahut 型領域計算アルゴリズムを提案し、領域の境界 を与える最適分布へ収束するための十分条件を得た。 新井は DBC に対し、目的関数に緩和項を導入した容領域計算アルゴリズムを提案したが、ア ルゴリズムの収束性について十分な議論がなされなかった。 本論文では緩和項を用いた容領域計算アルゴリズムに対する数値実験を行い、アルゴリズムの 妥当性を調べるために提案した総当たりアルゴリズム、近似アルゴリズムによって得られた結 果と比較した。結果として、2 元対称 DBC における実験の値は理論、総当たりアルゴリズム、 近似アルゴリズムの値と一致した。3 元対称 DBC における実験では、複数の異なる確率分布か ら同一の通信路容量が得られた。これに対してアルゴリズムの持つ性質について考察を行った。 また、緩和項を用いた容領域計算アルゴリズムが最適分布へ収束するための十分条件を導いた。 この結果は安井の得た結果を内包する形となっており、安井の収束条件よりも緩い可能性があ る。 DBC の収束性についての考察や収束するための十分条件は、未だ解明されていない DBC の 理論限界を求める問題において、その進展に大きく寄与するものと考えられる。
令和
2
年度
修士学位論文
劣化型放送通信路における緩和項を用いた容量域
計算アルゴリズムと収束性
学籍番号
1931115
氏
名
八田 悠司
指導教員
大濱 靖匡 教授
川端 勉 教授
バグス サントソ 准教
電気通信大学 情報理工学研究科
博士前期課程 情報・ネットワーク工学専攻
提出 令和
3
年
3
月
25
日
THE UNIVERSITY OF ELECTRO-COMMUNICATIONS
Department of Communications and Systems Engineering
目 次
1 はじめに 3 2 2 端子通信路と通信路容量計算 5 2.1 2 端子通信路 . . . . 5 2.2 Arimoto-Blahut アルゴリズム . . . . 5 2.3 最適分布への収束 . . . . 9 3 劣化型放送通信路と容量域計算 12 3.1 劣化型放送通信路 . . . . 12 3.2 容量域の支持直線表現 . . . . 14 3.3 DBC に関するこれまでの研究 . . . . 15 4 Arimoto-Blahut 型領域計算アルゴリズム 17 4.1 Arimoto-Blahut アルゴリズムの拡張 . . . . 17 4.2 最適分布への収束 . . . . 20 5 緩和項を用いた容領域計算アルゴリズム 22 5.1 緩和項の導入 . . . . 22 5.2 従来アルゴリズムとの相違 . . . . 30 5.3 収束性に関する結果 . . . . 30 5.4 最適分布への収束条件 . . . . 33 6 数値実験 35 6.1 実験結果 . . . . 35 6.1.1 2 元における数値実験 . . . . 35 6.1.2 3 元における数値実験 . . . . 37 6.2 総当たりアルゴリズム . . . . 39 6.3 近似アルゴリズム . . . . 40 12 6.4 結果の考察 . . . . 43 7 収束の十分条件 45 7.1 凸領域における収束 . . . . 45 7.2 十分条件の比較 . . . . 48 8 結論 49
第
1
章
はじめに
こんにち、コンピュータやインターネットの普及に伴いより多くの情報が通信端末を 通じてやりとりされている。これらの情報のデータ量は端末の性能向上、普及が進むと ともにその大きさを増し、年々データ通信に求められる効率、速さ、正確さは増大してい る。同一の情報を不特定多数の受信者に対し同時に送信するための通信方式として、ブ ロードキャスト通信やマルチキャスト通信が用いられている。特に、異なる情報を複数 の受信者に対し同時に送信する理論モデルである放送通信路は、ブロードキャスト通信 の中でもその需要を大きくしており、その解析が重要な課題となっている。 情報理論分野において、通信路の論理モデルに対する情報通信の理論的限界を解明す るための研究がこれまでに数多く行われてきた。有本 [1] や Blahut[2] によって、離散無 記憶な単一通信路に対する通信の理論限界を、具体的に数値化された通信路容量として 求めるための逐次計算アルゴリズムが得られている。しかし、多端子通信路に対する通 信路容領域を求めることのできるアルゴリズムは未だ確立されておらず、情報理論分野 における基本的未解決問題となっている。 本論文では、1 入力 2 出力の劣化型放送通信路 (DBC) に対する通信路容量域を求める ための容領域計算アルゴリズムについて考察する。安井 [5] は DBC の容領域を求める Arimoto-Blahut 型領域計算アルゴリズムを提案し、領域の境界を与える最適分布へ収束 するための十分条件を得た。新井 [6] は DBC に対し、目的関数に緩和項を導入した容領 域計算アルゴリズムを提案したが、アルゴリズムの収束性について十分な議論がなされ なかった。本論文では緩和項を用いた容領域計算アルゴリズムに対する数値実験を行い、 アルゴリズムの妥当性を調べるために提案した総当たりアルゴリズム、近似アルゴリズ ムによって得られた結果と比較した。結果として、2 元対称 DBC における実験の値は理 論、総当たりアルゴリズム、近似アルゴリズムの値と一致した。3 元対称 DBC における 実験では、複数の異なる確率分布から同一の通信路容量が得られた。これに対してアル ゴリズムの持つ性質について考察を行った。また、緩和項を用いた容領域計算アルゴリ ズムが最適分布へ収束するための十分条件を導いた。この結果は安井の得た結果を内包 する形となっており、安井の収束条件よりも緩い可能性がある。 3第 1 章 はじめに 4 本論文の 2 章以降の構成は以下のようになっている。第 2 章では、2 端子通信路に対す る通信路容量を数値的に求める Arimoto-Blahut アルゴリズムについて記述する。第 3 章 では、劣化型放送通信路の定義や通信路容量域を求めるための基本的な考え方、また劣化 型放送通信路に関するこれまでの研究について記述する。第 4 章では、Arimoto-Blahut ア ルゴリズムを自然に拡張し、劣化型放送通信路の通信路容量域を求めるための Arimoto-Blahut 型領域計算アルゴリズムと、その収束性に関する問題点について記述する。第 5 章では、前述の問題点を改善するために提案された緩和項を用いた容領域計算アルゴリ ズムと、最適分布へ収束するための条件を記述する。第 6 章では、緩和項を用いた容領域 計算アルゴリズムの数値実験と比較、総当たりアルゴリズムと近似アルゴリズムの定義、 数値実験の結果の考察を記述する。第 7 章では、最適分布へ収束するための十分条件を 導き、安井の得た結果と比較する。第 8 章では、本論文の結論と今後の課題を記述する。
第
2
章
2
端子通信路と通信路容量計算
2.1
2
端子通信路
X , Y を有限集合とし、通信路の入力を表す確率変数を X ∈ X 、出力を表す確率変
数を Y ∈ Y とする。X , Y の各要素をそれぞれ x, y とすると、通信路は遷移確率行列 W ={W (y|x)}(x,y)∈X ×Yで表現される。(X, Y ) の同時分布を pXY とすると、この同時分
布は通信路の入力分布 pX と W を用いて pXY ={pXY(x, y)}(x,y)∈X ×Y ={pX(x)W (y|x)}(x,y)∈X ×Y で与えられる。入力確率変数 X と出力確率変数 Y との間の相互情報量 I(X; Y ) は I(X; Y ) =X x,y pXY(x, y) log pXY(x, y) pX(x)pY(y) =X x,y pXY(x, y) log pX(x)W (y|x) pX(x)pY(y) =X x,y pXY(x, y) log W (y|x) pY(y)
で与えられる。I(X; Y ) が入力分布の関数であることを明示したい場合、I(X; Y ) = I(pX, W )
と表す。2 端子通信路の通信路容量 C(W ) は以下の式で定義される。 C(W )≜ max pX I(pX, W )
2.2
Arimoto-Blahut
アルゴリズム
入力集合X 上の 2 つの確率分布を pX, qX としたとき、以下の目的関数を定義する。 F (pX, qX)≜ I(qX, W ) + D(qY||pY)− D(qX||pX) 5第 2 章 2 端子通信路と通信路容量計算 6
ここで pY, qY はそれぞれ入力分布 pX, qX で指定される確率変数 X ∈ X を通信路につな
いだときに得られる出力 Y ∈ Y の確率分布であり、以下のように定義される。
pY ={pY(y)}y∈Y, pY(y) =
X
x∈X
pX(x)W (y|x)
qY ={qY(y)}y∈Y, qY(y) =
X x∈X qX(x)W (y|x) また D(qY||pY) および D(qX||pX) はそれぞれ分布 qY と pY および qX と pXの間の差異の 度合いを表すダイバージェンスと呼ばれる非負の量であり、以下で定義される。 D(qY||pY)≜ X y qY(y) log qY(y) pY(y) D(qX||pX) の定義は D(qY||pY) と全く同様である。ダイバージェンス D(qY||pY) は非負性 を持っており qY = pY ⇔ D(qY||pY) = 0 となることが知られている。同様の性質が D(qX||pX) についても成り立つ。pY, qY がそ れぞれ入力分布 pX, qXに対する通信路 W から得られた出力分布であることを明示すると きには、pY = pXW, qY = qXW と記す。このとき F (pX, qX) は以下のように書き直すこ とができる。 F (pX, qX)≜ I(qX, W ) + D(qXW||pXW )− D(qX||pX) この目的関数について次の補題が成り立つ。 補題 1. 固定した qX に対し、pX = qX のとき F (pX, qX) は最大値 F (qX, qX) = I(qX, W ) をとる。 証明. 対数和不等式より D(qY||pY) =D(qXW||pXW ) =X y qXW (y) log qXW (y) pXW (y) ≤X x,y qX(x)W (y|x) log qX(x)W (y|x) pX(x)W (y|x) =X x qX(x) log qX(x) pX(x) =D(qX||pX) (2.1)
第 2 章 2 端子通信路と通信路容量計算 7 が成り立つ。式 (2.1) より以下を得る。 F (pX, qX) =I(qX, W ) + D(qXW||pXW )− D(qX||pX)≤ I(qX, W ) 等号条件は pX = qX。 補題 2. 固定した pX に対し F (pX, qX) は qX(x) = 1 K exp ( X y W (y|x) logW (y|x) pY(y) ) pX(x) のときに最大値 log K をとる。ここで規格化定数 K は K =X x exp ( X y W (y|x) log W (y|x) pY(y) ) pX(x) 証明. F (pX, qX) =I(qX, W ) + D(qXW||pXW )− D(qX||pX) =X x,y qX(x)W (y|x) log W (y|x) qY(y) +X x,y qX(x)W (y|x) log qY(y) pY(y) −X x,y qX(x) log qX(x) pX(x) =X x,y qX(x)W (y|x) logW (y|x) qY(y) + logqY(y) pY(y) −X x,y qX(x) log qX(x) pX(x) =X x,y qX(x)W (y|x) log W (y|x) pY(y) − X x qX(x) log qX(x) pX(x) =−X x qX(x) log qX(x) exp ( X y W (y|x) logW (y|x) pY(y) ) pX(x) (2.2) 式 (2.2) の分母を確率分布にするため、分母に 1 Kをかけると F (pX, qX) =− X x qX(x) log qX(x) 1 Kexp ( X y W (y|x) log W (y|x) pY(y) ) pX(x) + log K (a) =−X x qX(x) log qX(x) ˜ qX(x) + log(K) (b) =− D(qX||˜qX) + log(K) (c) ≤ log K (2.3)
第 2 章 2 端子通信路と通信路容量計算 8 ステップ (a) は ˜ qX(x) = 1 K exp ( X y W (y|x) logW (y|x) pY(y) ) pX(x) とおいたことによる。またステップ (b) は ˜qX = {˜qX}x∈X が確率分布となる様に K を選 んだことによる。またステップ (c) はダイバージェンスの非負性による。不等式 (2.3) に おいて、等号条件は qX(x) = 1 K exp ( X y W (y|x) logW (y|x) pY(y) ) pX(x) 次に補題 1,2 に基づき C(W ) を求めるアルゴリズムを導出する。t = 0, 1, 2, . . . に対し X 上の分布の列 qX[t]={q[t]X(x)}x∈X を次の様に定める。 分布更新アルゴリズム 1. qX[0]をX 上の適当な分布にとる。 2. t = 0, 1, 2, . . . に対する分布更新式を以下で定める。 q[t+1]X (x) = 1 Kt exp ( X y W (y|x) log W (y|x) qY[t](y) ) q[t]X(x), x∈ X (2.4) ここで Kt= X x exp ( X y W (y|x) logW (y|x) qY[t](y) ) q[t]X(x) 上記の分布更新アルゴリズムに対して、次の命題が成り立つ。
第 2 章 2 端子通信路と通信路容量計算 9 命題 1. t = 0, 1, 2, . . . に対し、次の不等式が成り立つ。 F (q[0]X, qX[0]) (a) ≤ F (q[0] X, q [1] X) (b) ≤ F (q[1] X, q [1] X)≤ . . . . (a) ≤ F (q[t−1] X , q [t] X) (b) ≤ F (q[t] X, q [t] X) (2.5) (a) ≤ F (q[t] X, q [t+1] X ) (2.6) (b) ≤ F (q[t+1] X , q [t+1] X )≤ . . . . ≤ C(W ) ここで不等式 (2.5) および不等式 (2.6) の右辺に現れる量に関してはそれぞれ以下が成 り立つ。 F (qX[t], q[t]X) =X x,y q[t]X(x)W (y|x) logW (y|x) qY[t](y) (2.7) F (qX[t], q[t+1]X ) =X x,y qX[t+1](x) ( W (y|x) log W (y|x) qY[t](y) + log qX[t](x) qX[t+1](x) ) (2.8) 証明. 命題 1 の不等式におけるステップ (b) と式 (2.7) は、補題 1 より従う。またステッ プ (a) と式 (2.8) は、補題 2 より従う。 次の節で、Arimoto-Blahut アルゴリズムの定める分布例が最適分布へ収束することを 証明する。
2.3
最適分布への収束
F (qX, qX) の最適値を与える分布を qX∗ とすると、補題 1 より C(W ) = F (q∗X, qX∗ ) =X x,y qX∗(x)W (y|x) logW (y|x) q∗Y(y) Arimoto-Blahut アルゴリズムの収束性について次の命題が成り立つ。第 2 章 2 端子通信路と通信路容量計算 10 命題 2. t = 0, 1, 2, . . . に対し、以下が成り立つ。 C(W )− F (q[t]X, qX[t+1]) =C(W )− log Kt =− D(q∗Y||qY[t]) + D(qX∗||qX[t])− D(q∗X||q[t+1]X ) 証明. 式 (2.4) より任意の x∈ X と任意の t = 0, 1, 2, . . . に対し、以下が成り立つ。 Kt= q[t]X(x) q[t+1]X (x)exp ( X y W (y|x) log W (y|x) qY[t](y) ) 両辺の対数をとると log Kt= X y W (y|x) logW (y|x) q[t]Y (y) + log q[t]X(x) q[t+1]X (x) (2.9) が任意の x∈ X に対して成り立つ。式 (2.9) の両辺に q∗ X(x) をかけて和をとると、以下の 等式を得る。 log Kt= X x,y qX∗(x)W (y|x) logW (y|x) q[t]Y (y) +X x qX∗(x) log q [t] X(x) qX[t+1](x) (2.10) このとき次の一連の等式を得る。 C(W )− F (qX[t], qX[t+1]) = F (qX∗, qX∗)− log Kt (a) = X x,y qX∗ (x)W (y|x) logW (y|x) qY∗(y) − X x,y q∗X(x)W (y|x) logW (y|x) qY[t](y) + X x q∗X(x) logq [t+1] X (x) q[t]X(x) =X x,y q∗X(x)W (y|x) logq [t] Y (y) q∗Y(y) + X x q∗X(x) " log q ∗ X(x) qX[t](x) + log qX[t+1](x) qX∗(x) # =−D(q∗Y||qY[t]) + D(q∗X||q[t]X)− D(qX∗||q[t+1]X ) ステップ (a) は式 (2.10) より従う。 命題 2 の結果より、次の定理が得られる。 定理 1. Arimoto-Blahut アルゴリズムの定める分布列nqX[t] o+∞ t=0 は t→ +∞ のとき q ∗ X に 収束する。 証明. 命題 2 より t = 0, 1, 2, . . . について以下が成り立つ。 C(W )− F (qX[t], q[t+1]X )≤ D(qX∗ ||qX[t])− D(q∗X||q[t+1]X )
第 2 章 2 端子通信路と通信路容量計算 11 そこで ∆t= C(W )− F (q [t] X, q [t+1] X ) とおくと、 ∆t≤ D(q∗X||q [t] X)− D(qX∗||q [t+1] X ) t = 0, 1, 2, . . . T について和をとると、 T X t=0 ∆t≤ D(qX∗||q [0] X)− D(qX∗||q [T +1] X ) (2.11) 命題 1 より{∆t} T t=0は単調減少列であるから式 (2.11) より、 T ∆T ≤ T X t=0 ∆t≤ D(q∗X||q [0] X) これより 0≤ ∆t ≤ 1 TD(q ∗ X||q [0] X)→ 0(T → +∞) となり、分布更新アルゴリズムが最適値を与える分布へ収束することがわかる。以上で 定理 1 は証明された。 以上より、Arimoto-Blahut アルゴリズムの定める分布は最適分布に収束し、2 端子通 信路の通信路容量を求めることができる。
第
3
章
劣化型放送通信路と容量域計算
3.1
劣化型放送通信路
X , Y, Z を有限集合とし、通信路の入力を表す確率変数を X ∈ X 、出力を表す確率変 数を Y ∈ Y, Z ∈ Z とする。X , Y, Z の各要素をそれぞれ x, y, z とするとその遷移確率行 列は以下で与えられる。W ={W (y, z|x)}(x,y,z)∈X ×Y×Z
図 3.1: 放送通信路 本稿では特に、上記の遷移確率行列が
W (y, z|x) = {W1(y|x)W2(z|y)}(x,y,z)∈X ×Y×Z (3.1)
なる条件を満たす場合を考える。
第 3 章 劣化型放送通信路と容量域計算 13
𝑊
1(𝑦|𝑥)
𝑊
2(𝑧|𝑦)
出力
𝑍
入力
𝑋
出力
𝑌
図 3.2: 劣化型放送通信路 条件式 (3.1) を満たす放送通信路は劣化型放送通信路と呼ばれる。以後、DBC と記述 する。DBC の容量域をCDBC(W1, W2) と表す。DBC の容量域を記述するために有限集合 U に値をとる確率変数 U を導入し、(U, X, Y, Z) の同時分布 pU XY Z(u, x, y, z) とその集合 P(W1, W2) を以下で定義する。pU XY Z(u, x, y, z) ={pU XY Z(u, x, y, z)}(u,x,y,z)∈U×X ×Y×Z
P(W1, W2)≜ {p = pU XY Z : p(u, x, y, z) = p(u, x)W1(y|x)W2(z|y), |U| ≤ min {X , Y, Z}}
この条件は U, X, Y, Z がマルコフ連鎖 U → X → Y → Z をなすことと等価である。確率 変数 X ∈ X , Y ∈ Y, Z ∈ Z がこの条件に従うとき、以下を得る。 Ip(X; Y|U) = X u pU(u) X x,y pXY|U(x, y|u) log pXY|U(x, y|u) pX|U(x|u)pY|U(y|u) =X u pU(u) X x,y pU XY(u, x, y) pU(u) log pXY|U(x, y|u) pX|U(x|u)pY|U(y|u) (a) = X u,x,y pU XY(u, x, y) log W1(y|x) pY|U(y|u) Ip(Z; U ) = X u,z pU Z(u, z) log pU Z(u, z) pU(u)pZ(z) =X u,z pU Z(u, z) log pZ|U(z|u) pZ(z) ステップ (a) は U → X より W1(y|x) = pXYp (x,y) X(x) = pXY|U(x,y|u) pX|U(x|u) 。
第 3 章 劣化型放送通信路と容量域計算 14 このときCDBC(W1, W2) は以下で与えられる。 CDBC(W1, W2) ={(R1, R2) : R1 ≤ Ip(X; Y|U), R2 ≤ Ip(Z; U ),∃p ∈ P(W1, W2)} 本研究では容量域CDBC(W1, W2) を数値的に計算するアルゴリズムを考察する。そのため CDBC(W1, W2) の支持直線による表現を導入する。
3.2
容量域の支持直線表現
容領域を支持直線で表現するために、支持直線の導出を行う。まず次の量を定義する。 C(µ)(W1, W2)≜ max p∈P(W1,W2) {µIp(X; Y|U) + Ip(Z; U )} (3.2) このとき次の命題が成り立つ。 命題 3. CDBC(W1, W2) = \ 1≥µ≥0 (R1, R2) : µR1+ R2 ≤ C(µ)(W1, W2)𝑅
2𝑅
1 𝐼𝑞 𝑍; 𝑈 𝐼𝑞 𝑋; 𝑌|𝑈 max 𝑞 𝜇𝐼𝑞 𝑋; 𝑌|𝑈 + 𝐼𝑞 𝑍; 𝑈 = 𝐶 𝜇 𝑊 1, 𝑊2 𝑅2= −𝜇𝑅1+ 𝜇𝐼𝑞 𝑋; 𝑌|𝑈 + 𝐼𝑞 𝑍; 𝑈 𝜇𝐼𝑞 𝑋; 𝑌|𝑈 + 𝐼𝑞 𝑍; 𝑈 𝜇, 1 𝑅1− 𝐼𝑞 𝑋; 𝑌|𝑈 , 𝑅2− 𝐼𝑞 𝑍; 𝑈 45°線 図 3.3: 劣化型放送通信路の通信路容量域第 3 章 劣化型放送通信路と容量域計算 15 直線 µR1+ R2 ≤ C(µ)(W1, W2) は領域CDBC(W1, W2) の支持直線とよばれる。支持直線 R1+ µR2 ≤ C(µ)(W1, W2) は法線ベクトルを (µ, 1) とする直線で領域CDBC(W1, W2) と共 有点を持つようなもののうち、その R2切片が最大となるものと等しい。 命題 3 より容量域CDBC(W1, W2) は µ を動かしたときに得られる全ての支持直線の下側 の領域となっている。支持直線は C(µ)(W 1, W2) を求めることによって導出することがで きる。つまり、容量域CDBC(W1, W2) を数値的に求める問題は、C(µ)(W1, W2) を数値的に 求める問題に帰着される。
3.3
DBC
に関するこれまでの研究
この節では DBC の容量域計算に関するこれまでの結果を述べる。 Calvo et. AI ’2008[4] の研究 Calvo[4] は、DBC の容領域計算において C(µ)(W 1, W2) を数値的に求める問題、即ち 式 (3.2) C(µ)(W1, W2)≜ max p∈P(W1,W2) {µIp(X; Y|U) + Ip(Z; U )} 上記の最大化問題について考察し、DBC の容領域計算問題が差凸関数を目的関数とする 非凸最適化問題であることを示した。実際、µIp(X; Y|U) + Ip(Z; U ) について µIp(X; Y|U) + Ip(Z; U ) = X u,x p(u, x) " µ ( X y W1(y|x) log W1(y|x) p(y|u) ) +X z (W1W2)(z|x) log p(z|u) p(z) # 上式の第一項 X u,x p(u, x) " µ ( X y W1(y|x) log W1(y|x) P xp(x|u)W1(y|x) )# は上に凸な関数である。また、 X u,x p(u, x) " X z (W1W2)(z|x) log p(z|u) p(z) # =X u,x p(u, x)X z{(W1W2)(z|x) [log p(z|u) − log p(z)]}
=X u,x p(u, x)X z (W1W2)(z|x) " logX x p(x|u)(W1W2)(z|x) − log X u,x p(u, x)(W1W2)(z|x) #
第 3 章 劣化型放送通信路と容量域計算 16
上式の第一項は下に凸、第二項は上に凸な関数である。以上から、µIp(X; Y|U)+Ip(Z; U )
は凸関数同士の差で表される差凸関数となっていることがわかる。したがって、C(µ)(W
1, W2)
第
4
章
Arimoto-Blahut
型領域計算アルゴリ
ズム
4.1
Arimoto-Blahut
アルゴリズムの拡張
Arimoto-Blahut アルゴリズムを自然に拡張し、DBC の通信路容量を求める。通信路容 量 C(µ)(W 1, W2) は C(µ)(W1, W2) = max p:p=(pU X,W1,W2) {µIp(X; Y|U) + Ip(U ; Z)} = max pU X {µI pU X(X; Y|U) + IpU X(U ; Z)} ここで p = (pU X, W1, W2) について、W1, W2 は固定されている事を明示するために p = pU Xと表記する。C(µ)(W1, W2) を求めるために目的関数を以下に定義する。 F (pU X, qU X)≜µIqU X(X; Y|U) + µD(qY|U||pY|U|pU)− µD(qX|U||pX|U|pU) + IqU X(U ; Z) + D(qZ||pZ)− D(qZ|U||pZ|U|pU)− D(qU||pU) (4.1) このとき次の補題が成り立つ。 補題 3. 固定した qU Xに対し、pU X = qU Xのとき F (pU X, qU X) は最大値 F (qU X, qU X) = IqU X(X; Y|U) + µIqU X(U ; Z) 証明. 補題 1 の証明と同様 D(qY|U||pY|U|pU)≤D(qX|U||pX|U|pU) (4.2) D(qZ||pZ)≤D(qZ|U||pZ|U|pU) (4.3) 式 (4.2), 式 (4.3) より、式 (4.1) は F (pU X, qU X) =µIqU X(X; Y|U) + µD(qY|U||pY|U|pU)− µD(qX|U||pX|U|pU) + IqU X(U ; Z) + D(qZ||pZ)− D(qZ|U||pZ|U|pU)− D(qU||pU) ≤µIqU X(X; Y|U) + IqU X(U ; Z) 17第 4 章 Arimoto-Blahut 型領域計算アルゴリズム 18 等号条件は pU X = qU X。 同様に固定した pU X に対し、F (pU X, qU X) の最大値について、次の補題が成り立つ。 補題 4. 固定した pU Xに対し、F (pU X, qU X) は qU X(u, x) = 1
K exp{µApU X(u, x) + BpU X(u, x)} pU X(u, x)
のときに最大値 log K をとる。ここで ApU X(u, x) = X y W1(y|x) log W1(y|x) pY|U(y|u) (4.4) BpU X(u, x) = X z (W1W2)(z|x) log pZ|U(z|u) pZ(z) (4.5) また、K は規格化定数であり K =X u,x
exp{µApU X(u, x) + BpU X(u, x)} pU X(u, x)
証明. F (pU X, qU X) = X u,x qU X(u, x) " µ ( X y W1(y|x) log W1(y|x) pY|U(y|u) ) +X z (W1W2)(z|x) log pZ|U(z|u) pZ(z) # +X u,x qU X(u, x) log pU X(u, x) qU X(u, x) 式 (4.4), 式 (4.5) より F (pU X, qU X) = X u,x
qU X(u, x) [µApU X(u, x) + BpU X(u, x)] +
X u,x qU X(u, x) log pU X(u, x) qU X(u, x) =−X u,x qU X(u, x) log qU X(u, x)
exp{µApU X(u, x) + BpU X(u, x)} pU X(u, x)
分母を確率分布にするために、分母に 1 K をかける。 F (pU X, qU X) =−X u,x qU X(u, x) log qU X(u, x) 1
K exp{µApU X(u, x) + BpU X(u, x)} pU X(u, x)
+ log K
≤ log K
等号条件は
qU X(u, x) =
1
第 4 章 Arimoto-Blahut 型領域計算アルゴリズム 19 補題 4 に基づき、C(µ)(W
1, W2) を求めるアルゴリズムを導出する。t = 0, 1, 2, . . . に対
し、U × X 上の分布の列
q[t]=q[t](u, x) (u,x)∈U×X を次の様に定める。 分布更新アルゴリズム 1. q[0]をU × X 上の適当な分布にとる。 2. t = 0, 1, 2, . . . に対する分布更新式を以下で定める。 q[t+1](u, x) = 1 Kt
expµAq[t](u, x) + Bq[t](u, x)
q[t](u, x) ここで Kt = X u,x
expµAq[t](u, x) + Bq[t](u, x)
q[t](u, x) 上記の分布更新アルゴリズムに対して、次の命題が成り立つ。 命題 4. t = 0, 1, 2, . . . に対し、次の不等式が成り立つ。 F (q[0], q[0]) (a) ≤ F (q[0], q[1])(b)≤ F (q[1], q[1])≤ . . . . (a) ≤ F (q[t−1] , q[t]) (b) ≤ F (q[t], q[t]) (4.6) (a) ≤ F (q[t], q[t+1]) (4.7) (b) ≤ F (q[t+1], q[t+1])≤ . . . . ≤ C(µ)(W 1, W2) ここで不等式 (4.6) および不等式 (4.7) の右辺に現れる量に関しては以下が成り立つ。 F (q[t], q[t]) = Iq[t](X; Y|U) + µIq[t](U ; Z) (4.8) F (q[t], q[t+1]) = log Kt
=µAq[t](u, x) + Bq[t](u, x) + log
q[t]
第 4 章 Arimoto-Blahut 型領域計算アルゴリズム 20 証明. 命題 4 の不等式におけるステップ (b) と式 (4.8) は補題 3 より従う。またステップ (a) と式 (4.9) は補題 4 より従う。
𝐹 𝑞
0, 𝑞
0𝐹 𝑞
0, 𝑞
1𝐹 𝑞
1, 𝑞
1最大化
𝐹 𝑞
∗, 𝑞
∗= 𝐶 𝑊
1, 𝑊
2 図 4.1: 交互最大化アルゴリズム 次節に、拡張された Arimoto-Blahut アルゴリズムの収束性について記述する。4.2
最適分布への収束
F (pU X, qU X) の最適値を与える分布を q∗(u, x) とすると、補題 3 より C(µ)(W1, W2) = max pU X {µIpU X(X; Y|U) + IpU X(U ; Z)} =F (q∗, q∗) =µIq∗(X; Y|U) + Iq∗(U ; Z) 拡張された Arimoto-Blahut アルゴリズムの収束性について次の命題が成り立つ。第 4 章 Arimoto-Blahut 型領域計算アルゴリズム 21 命題 5. t = 0, 1, 2, . . . に対し、以下が成り立つ。 C(µ)(W1, W2)− F (q[t], q[t+1]) =F (q∗, q∗)− F (q[t], q[t+1]) =X u,x
q∗(u, x)µAq∗(u, x)− Aq[t](u, x)
+ Bq∗(u, x)− Bq[t](u, x) +X u,x q∗(u, x) logq [t+1](u, x) q[t](u, x) =− µD(q∗Y|U||qY[t]|U|qU[t])− D(qZ∗||qZ[t]) + D(q∗Z|U||qZ[t]|U|qU[t]) + D(q∗||q[t])− D(q∗||q[t+1]) もし全ての t = 0, 1, 2, . . . について −µD(q∗ Y|U||q [t] Y|U|q [t] U) + D(qZ∗|U||q [t] Z|U|q [t] U)− D(qZ∗||q [t] Z)≤ 0 が成り立つならば、拡張された Arimoto-Blahut アルゴリズムの定める分布列は最適分布 へと収束する。しかし、ダイバージェンスの性質により D(qZ∗|U||q[t]Z|U|qU[t])− D(q∗Z||q[t]Z)≥ 0 であるから、µ が小さいとき成立が非常に難しくなる。つまり、拡張された Arimoto-Blahut アルゴリズムでは、DBC の通信路容量を導出するのが困難となる。この問題に対して、緩 和項を目的関数に導入することで収束性の改善を図ったアルゴリズムを次章で記述する。
第
5
章
緩和項を用いた容領域計算アルゴリズム
5.1
緩和項の導入
CDBC(W1, W2) を数値的に求めるために次の量を定義する。 ωq(α,µ)(u, x, y, z)≜µ log W1(y|x) qY|U(y|u) + logqZ|U(z|u) qZ(z) + α log W2(z|y)W1(y|x) qZY|XU(z, y|x, u) F(α,µ)(p, q)≜(µ + α) X u,x,y,z q(u, x, y, z) 1 µ + αω (α,µ) p (u, x, y, z) + log p(u, x, y, z) q(u, x, y, z) 以後はパラメータ (α, µ) が以下の条件 1− µ ≤ α (5.1) を満たすと仮定して議論する。ここで次の補題が成り立つ。 22第 5 章 緩和項を用いた容領域計算アルゴリズム 23 補題 5. 固定した q に対し、p = q のとき F(α,µ)(p、q) は最大値 F(α,µ)(q, q) = X u,x,y,z q(u, x, y, z)ωq(α,µ)(u, x, y, z) = X u,x,y,z q(u, x, y, z) µ log W1(y|x) qY|U(y|u) + logqZ|U(z|u) qZ(z) + α log W2(z|y)W1(y|x) qZY|XU(z, y|x, u) = X u,x,y,z q(u, x, y, z) µ log qXY|U(x, y|u) qX|U(x|u)qY|U(y|u) · W1(y|x)qX|U(x|u) qXY|U(x, y|u) + logqZ|U(z|u) qZ(z) − α logqZY|XU(z, y|x, u) W2(z|y)W1(y|x) = X u,x,y,z q(u, x, y, z) µ log qXY|U(x, y|u) qX|U(x|u)qY|U(y|u) + logqZ|U(z|u) qZ(z) −α logqZY|XU(z, y|x, u) W2(z|y)W1(y|x) − µ log qXY|U(x, y|u) W1(y|x)qX|U(x|u) =µIq(X; Y|U) + Iq(Z; U ) − αD(qZY|XU||W1, W2|qXU)− µD(qY|XU||W1|qXU) (5.2)
第 5 章 緩和項を用いた容領域計算アルゴリズム 24 証明. F(α,µ)(p、q) に 1 µ+αをかけた量について、以下が成り立つ。 1 µ + αF (α,µ)(p, q) = X u,x,y,z q(u, x, y, z) 1 µ + αω (α,µ) p (u, x, y, z) + log p(u, x, y, z) q(u, x, y, z) = X u,x,y,z q(u, x, y, z) 1 µ + αω (α,µ) q (u, x, y, z) + 1 µ + α[ω (α,µ) p (u, x, y, z)− ω (α,µ) q (u, x, y, z)] + log p(u, x, y, z) q(u, x, y, z) = X u,x,y,z q(u, x, y, z) 1 µ + αω (α,µ) q (u, x, y, z) + 1 µ + α µ log W1(y|x) pY|U(y|u) + logpZ|U(z|u) pZ(z) +α log W2(z|y)W1(y|x) pZY|XU(z, y|x, u) − µ log W1(y|x) qY|U(y|u) − log qZ|U(z|u) qZ(z) − α log W2(z|y)W1(y|x) qZY|XU(z, y|x, u) + log p(u, x, y, z) q(u, x, y, z) = X u,x,y,z q(u, x, y, z) 1 µ + αω (α,µ) q (u, x, y, z) + α µ + αlog p(x|u) q(x|u)+ 1 µ + αlog p(u|z) q(u|z) + µ µ + αlog p(x, z|u, y) q(x, z|u, y) + 1 µ + α[−1 + α + µ] log p(u) q(u) = X u,x,y,z q(u, x, y, z) 1 µ + αω (α,µ) q (u, x, y, z) + J1 ここで J1は以下で与えられる。 J1 = X u,x,y,z q(u, x, y, z) α µ + αlog p(x|u) q(x|u) + 1 µ + αlog p(u|z) q(u|z) + µ µ + α log p(x, z|u, y) q(x, z|u, y) + 1 µ + α[−1 + α + µ] log p(u) q(u) = 1 µ + α −αD qX|U||pX|U − µD qXZ|UY||pXZ|UY − D qU|Z||pU|Z − [−1 + α + µ] D (pU|qU) 条件式 (5.1) の元で J1は J1 ≤ 0 が成り立つ。よって条件式 (5.1) の元で、p = q のとき F(α,µ)(p, q) は最大値をとる。 補題 5 の式 (5.2) の −αD(qZY|XU||W1, W2|qXU)− µD(qY|XU||W1|qXU)
第 5 章 緩和項を用いた容領域計算アルゴリズム 25 は緩和項となっている。以下の量を定義する。 C(α,µ)(W1, W2)≜ max (p,q) F (α,µ)(p, q) このとき次の補題が成り立つ。 補題 6. 1− µ ≤ α のとき、C(α,µ)(W 1, W2) は C(α,µ)(W1, W2) = max q F (α,µ)(q, q) = max q {µIq(X; Y|U) + Iq(Z; U ) −αD(qZY|XU||W1, W2|qXU)− µD(qY|XU||W1|qXU) (5.3) また、α > 0 に関して単調減少であり、任意の α > 0 に対し C(µ)(W1, W2)≤ C(α,µ)(W1, W2) (5.4) 特に lim α→+∞C (α,µ)(W 1, W2) = C(µ)(W1, W2) (5.5) 証明. まず式 (5.3) を示す。補題 5 より、固定した q に対し、p = q のとき F(α,µ)(p, q) は 最大値 F(α,µ)(q, q) = X u,x,y,z q(u, x, y, z)ω(α,µ)q (u, x, y, z)
= µIq(X; Y|U) + Iq(Z; U )− αD(qZY|XU||W1, W2|qXU)− µD(qY|XU||W1|qXU)
をとる。よって式 (5.3) が示された。次に式 (5.4), 式 (5.5) を示す。C(α,µ)(W
1, W2) を達成
する分布を
q∗ = qα∗ ={q∗α(u, x, y, z)}(u,x,y,z)∈U×X ×Y×Z とすると以下が成り立つ。
C(α,µ)(W1, W2) =F(α,µ)(qα∗, q∗α)
=µIq∗α(X; Y|U) + Iq∗α(Z; U )
− αD(q∗
ZY|XU,α||W1, W2|qXU,α∗ )− µD(qY∗|XU,α||W1|q∗XU,α) (5.6)
ここで、q∗ZY|XU,α, q∗Y|XU,αおよび q∗XU,αは分布 q∗α = q∗U XY Z,αより誘導される条件分布で ある。
∆(α,µ) ≜ µIq∗α(X; Y|U) + Iq∗α(Z; U )− C
(α,µ)(W 1, W2)
第 5 章 緩和項を用いた容領域計算アルゴリズム 26 とおくと、式 (5.6) より 0≤ D(q∗ZY|XU,α||W1, W2|qXU,α∗ ) = ∆(α,µ)− µD(q∗ Y|XU,α||W1|q∗XU,α) α ≤ ∆(α,µ) α これより、∆(α,µ) ≥ 0 である。よって C(α,µ)(W1, W2)≤ µIq∗α(X; Y|U) + Iqα∗(Z; U ) (5.7) 分布 ˆqα = ˆqU XY Z,αを ˆ
qU XY Z,α(u, x, y, z) = qXU,α∗ W1(y|x)W2(z|y)
と定めると ˆqα ∈ P(W1, W2) であり、以下が成り立つ。 D(qα∗||ˆqα) =D(qU XY Z,α∗ ||ˆqU XY Z,α) =D(qZY∗ |XU,α||W1, W2) = ∆(α,µ) α α→ +∞ とすると D(qα∗||ˆqα)→ 0 が成り立つ。すると Iq(X; Y|Z) および Iq(Z; U ) の分布 q に関する連続性より、以下が成り立つ。
µIq∗α(X; Y|U) + Iq∗α(Z; U )≤ µIqˆα(X; Y|U) + Iqˆα(Z; U ) + τ (α) (5.8)
ここで、τ (α) は lim α→+∞τ (α) = 0 となる量である。このとき以下の一連の不等式が成り 立つ。 C(α,µ)(W1, W2) (a) ≤µIq∗α(X; Y|U) + Iq∗α(Z; U ) (b) ≤µIqˆα(X; Y|U) + Iqˆα(Z; U ) + τ (α) (c) ≤C(µ)(W 1, W2) + τ (α) (5.9) ここでステップ (a) は式 (5.7) より従う。また、ステップ (b) は式 (5.8) より従う。また、 ステップ (c) は ˆqα ∈ P(W1, W2) と C(µ)(W1, W2) の定義より従う。他方、C(µ)(W1, W2) を達成する分布を ˜qαとすると、˜qα ∈ P(W1, W2) であることより、任意の (u, x, y, z) ∈ (U × X × Y × Z) に対し、以下が成り立つ。 ˜ qY|XU,α(y|x, u) =W1(y|x) ˜ qZY|XU,α(z, y|x, u) =W2(z|y)W1(y|x) よって D(˜qZY|XU,α||W1, W2|˜qXU ,α) = D(˜qY|XU,α||W1|˜qXU ,α) = 0
第 5 章 緩和項を用いた容領域計算アルゴリズム 27 このとき C(µ)(W1, W2) =µIq˜α(X; Y|U) + Iq˜α(Z; U ) =µIq˜α(X; Y|U) + Iq˜α(Z; U ) − αD(˜qZY|XU,α||W1, W2|˜qXU ,α)− µD(˜qY|XU,α||W1|˜qXU ,α) ≤C(α,µ) (W1, W2) (5.10) が成り立つ。式 (5.9), 式 (5.10) より以下を得る。 0≤ C(α,µ)(W1, W2)− C(µ)(W1, W2)≤ τ(α) 上式で α→ +∞ とすると式 (5.5) を得る。 補題 6 より、C(µ)(W 1, W2) を求める問題は、十分大きな α に対する F(α,µ)(q, q) の最大 化問題に帰着されることになる。 C(µ)(W1, W2) を求める方法 • α を十分大きい値に固定する。 • 順次 p, q を更新し、F(α,µ)(p, q) を最大化する。 以下ではこの最大化問題を考察する。固定した p に対する F(α,µ)(p、q) の最大値について、 次の補題が成り立つ 補題 7. 固定した p に対し、F(α,µ)(p、q) は、 q(u, x, y, z) = 1 K exp 1 µ + αω (α,µ) p (u, x, y, z) p(u, x, y, z) のとき最大値 (µ + α) log K をとる。ここで K = X (u,x,y,z) exp 1 µ + αω (α,µ) p (u, x, y, z) p(u, x, y, z) は規格化定数である。 証明. 1 µ+αF (α,µ)(p, q) の具体的な形は以下で与えられる。 1 µ + αF (α,µ)(p, q) = X u,x,y,z q(u, x, y, z) log exp n 1 µ+αω (α,µ) p (u, x, y, z) o p(u, x, y, z) q(u, x, y, z) (5.11)
第 5 章 緩和項を用いた容領域計算アルゴリズム 28 式 (5.11) の分子を確率分布にするために、分子に 1 K をかけると 1 µ + αF (α,µ)(p, q) = X u,x,y,z q(u, x, y, z) log 1 K exp n 1 µ+αω (α,µ) p (u, x, y, z) o p(u, x, y, z) q(u, x, y, z) + log K (5.12) 式 (5.12) の右辺第 1 項について X u,x,y,z q(u, x, y, z) log 1 Kexp n 1 µ+αω (α,µ) p (u, x, y, z) o p(u, x, y, z) q(u, x, y, z) ≤ 0 であるから、上式と式 (5.12) より以下を得る。 F(α,µ)(p, q)≤ (µ + α) log K 等号は q(u, x, y, z) = 1 K exp 1 µ + αω (α,µ) p (u, x, y, z) p(u, x, y, z) のとき成り立つ。 補題 5-7 に基づき、十分小さな α に対する C(α,µ)(W 1, W2) を求めるアルゴリズムを導 出する。t = 0, 1, 2, . . . . に対しU × X × Y × Z 上の分布の列 q[t]=q[t](u, x, y, z) (u,x,y,z)∈U×X ×Y×Z を次の様に定める。 分布更新アルゴリズム 1. q[0]をU × X × Y × Z 上の適当な分布にとる。 2. t = 0, 1, 2, . . . に対する分布更新式を以下で定める。 q[t+1](u, x, y, z) = 1 Kt exp 1 µ + αω (α,µ) q[t] (u, x, y, z) q[t](u, x, y, z) (5.13) ここで exp 1 µ + αω (α,µ) q[t] (u, x, y, z) = " W1(y|x) qY[t]|U(y|u) # µ µ+α "q[t] Z|U(z|u) q[t]Z(z) # 1 µ+α " W2(z|y)W1(y|x)
qY Z[t] |UX(yz|ux) # α
µ+α
第 5 章 緩和項を用いた容領域計算アルゴリズム 29 と置くことにより、q[t+1](u, x, y, z) を以下のように書き直す。 q[t+1](u, x, y, z) = 1 Kt Ω[t]α,µ(u, x, y, z) q[t](u, x, y, z) ここで Kt= X (u,x,y,z) Ω[t]α,µ(u, x, y, z) q[t](u, x, y, z) 上記の分布更新アルゴリズムに対して、次の命題が成り立つ。 命題 6. t = 0, 1, 2 . . . に対し、次の不等式が成り立つ。 F(α,µ)(q[0], q[0]) (a) ≤ F(α,µ)(q[0], q[1])(b)≤ F(α,µ)(q[1], q[1])≤ . . . . (a) ≤ F(α,µ)(q[t−1], q[t]) (b) ≤ F(α,µ) (q[t], q[t]) (5.14) (a) ≤ F(α,µ)(q[t], q[t+1]) (5.15) (b) ≤ F(α,µ)(q[t+1], q[t+1])≤ . . . . ≤ C(α,µ) ここで不等式 (5.14) および不等 (5.15) の右辺に現れる量に関しては以下が成り立つ。 F(α,µ)(q[t], q[t]) = X u,x,y,z q[t](u, x, y, z) n ω(α,µ)q[t] (u, x, y, z) o =µIq[t](X; Y|U) + Iq[t](Z; U )− αD(q [t] ZY|XU||W1, W2|q [t] XU)− µD(q [t] Y|XU||W1|q [t] XU) F(α,µ)(q[t], q[t+1]) =(µ + α) log Kt =(µ + α) log X (u,x,y,z) exp 1 µ + αω (α,µ) q[t] (u, x, y, z) q[t](u, x, y, z) 証明. 命題 6 の不等式におけるステップ (b) と式 (5.14) は補題 5 より従う。またステップ (a) と式 (5.15) は補題 7 より従う。 緩和項を用いた分布更新アルゴリズムは、新しいパラメータ α が導入されている点で、 拡張された Arimoto-Blahut アルゴリズムとは異なるものになっている。次の節でそのこ とについて記す。
第 5 章 緩和項を用いた容領域計算アルゴリズム 30
5.2
従来アルゴリズムとの相違
拡張された Arimoto-Blahut アルゴリズム C(µ)(W1, W2) = max p∈P(W1,W2) {µIp(X; Y|U) + Ip(U ; Z)} • p ∈ P (W1, W2) の制約あり • µ が 0 に近い場合に収束の保証がされない 緩和項を用いた容領域計算アルゴリズム C(α,µ)(W1, W2) = max q F (α,µ)(q, q) = max q {µIq(X; Y|U) + Iq(Z; U ) −αD(qZY|XU||W1, W2|qXU)− µD(qY|XU||W1|qXU) • 目的関数に緩和項を導入したことにより、q の動く範囲に制約がない • 緩和項の導入により差凸が緩和され、収束性の改善が期待される C(α,µ)(W1, W2) > C(µ)(W1, W2) より、緩和項を用いた容領域計算アルゴリズムの定める 分布列は容領域CDBC(W1, W2) の内点を与えるものになるとは限らない。しかし、緩和項 を導入したことにより目的関数の差凸が緩和され、収束性の改善が期待できる。次節で は、このアルゴリズムの境界を与える最適分布への収束性について記述する。5.3
収束性に関する結果
F(α,µ)(q, q) の最適値を与える分布を q∗(u, x, y, z) とすると、補題 5 より以下が成り立つ。 C(α,µ)(W1, W2) = max q F (α,µ) (q, q) =F(α,µ)(q∗, q∗) = X u,x,y,z q∗(u, x, y, z) n ω(α,µ)q∗ (u, x, y, z) o (5.16) 提案アルゴリズムの収束性について、次の命題が成り立つ。第 5 章 緩和項を用いた容領域計算アルゴリズム 31 命題 7. t = 0, 1, 2, . . . に対し、以下が成り立つ。 C(α,µ)(W1, W2)− F(α,µ)(q[t], q[t+1]) = F(α,µ)(q∗, q∗)− F(α,µ)(q[t], q[t+1]) = X u,x,y,z
q∗(u, x, y, z)ω(α,µ)q∗ (u, x, y, z)− (µ + α) log Kt
= (µ + α)D(q∗||q[t])− D(q∗||q[t+1])− µD(qY∗|U||qY[t]|U|qU∗)− D(qZ∗||qZ[t]) − αD(q∗ ZY|XU||q [t] ZY|XU|q∗XU) + D(qZ∗|U||q [t] Z|U|q∗U) (5.17) 証明. 式 (5.13) より以下を得る。 Kt= exp 1 µ + αω (α,µ) q[t] (u, x, y, z) q[t](u, x, y, z) q[t+1](u, x, y, z) 任意の (u, x, y, z) に対し、以下が成り立つ。 F(α,µ)(q[t], q[t+1]) =(µ + α) log Kt =(µ + α) log exp 1 µ + αω (α,µ) q[t] (u, x, y, z) q[t](u, x, y, z) q[t+1](u, x, y, z) =(µ + α) 1 µ + αω (α,µ) q[t] (u, x, y, z) + log q[t](u, x, y, z) q[t+1](u, x, y, z) =ωq(α,µ)[t] (u, x, y, z)− (µ + α) log q[t+1](u, x, y, z) q[t](u, x, y, z) (5.18) 式 (5.18) の両辺に q∗(u, x, y, z) をかけて (u, x, y, z) について和をとると F(α,µ)(q[t], q[t+1]) = X u,x,y,z q∗(u, x, y, z)(µ + α) log Kt = X u,x,y,z q∗(u, x, y, z) ω(α,µ) q[t] (u, x, y, z)− (µ + α) log q[t+1](u, x, y, z) q[t](u, x, y, z) (5.19)
第 5 章 緩和項を用いた容領域計算アルゴリズム 32 式 (5.16), 式 (5.19) より以下を得る。 C(α,µ)(W1, W2)− F(α,µ)(q[t], q[t+1]) = X u,x,y,z q∗(u, x, y, z)ωq(α,µ)∗ (u, x, y, z) − X u,x,y,z q∗(u, x, y, z) ωq(α,µ)[t] (u, x, y, z)− (µ + α) log q[t+1](u, x, y, z) q[t](u, x, y, z) = (µ + α) X u,x,y,z q∗(u, x, y, z) logq [t+1](u, x, y, z) q[t](u, x, y, z) + X u,x,y,z q∗(u, x, y, z) n ω(α,µ)q∗ (u, x, y, z)− ωq(α,µ)[t] (u, x, y, z) o = J2+ J3 (5.20) ここで、 J2 =(µ + α) X u,x,y,z q∗(u, x, y, z) logq [t+1](u, x, y, z) q[t](u, x, y, z) J3 = X u,x,y,z q∗(u, x, y, z) n ωq(α,µ)∗ (u, x, y, z)− ωq(α,µ)[t] (u, x, y, z) o 上記の J2について、 J2 =(µ + α) X u,x,y,z q∗(u, x, y, z) log q [t+1](u, x, y, z) q[t](u, x, y, z) − log q∗(u, x, y, z) q∗(u, x, y, z) =(µ + α) X u,x,y,z q∗(u, x, y, z) log q ∗(u, x, y, z) q[t](u, x, y, z) − log q∗(u, x, y, z) q[t+1](u, x, y, z) =(µ + α)D(q∗||q[t])− D(q∗||q[t+1]) 次に J3について、 J3 = X u,x,y,z q∗(u, x, y, z) ( µ log W1(y|x) q∗Y|U(y|u) + log q∗Z|U(z|u) q∗Z(z) + α log W2(z|y)W1(y|x) q∗ZY|XU(z, y|x, u) −µ log W1(y|x) qY[t]|U(y|u) − log qZ[t]|U(z|u) qZ[t](z) − α log W2(z|y)W1(y|x) q[t]ZY|XU(z, y|x, u) ) = X u,x,y,z q∗(u, x, y, z) ( µ logq [t] Y|U(y|u) q∗Y|U(y|u) + log q[t]Z(z) qZ∗(z) + log qZ∗|U(z|u) qZ[t]|U(z|u) + α log qZY[t] |XU(z, y|x, u) qZY∗ |XU(z, y|x, u) ) =− µD(q∗Y|U||q[t]Y|U|q∗U)− D(q∗Z||q[t]Z) − αD(q∗ ZY|XU||q [t] ZY|XU|q ∗ XU) + D(qZ∗|U||q [t] Z|U|qU∗) (5.21)
第 5 章 緩和項を用いた容領域計算アルゴリズム 33 したがって、式 (5.20)-式 (5.21) より C(α,µ)(W1, W2)− F(α,µ)(q[t], q[t+1]) = (µ + α) X u,x,y,z q∗(u, x, y, z) logq [t+1](u, x, y, z) q[t](u, x, y, z) + X u,x,y,z q∗(u, x, y, z) n ωq(α,µ)∗ (u, x, y, z)− ωq(α,µ)[t] (u, x, y, z) o = (µ + α)D(q∗||q[t])− D(q∗||q[t+1])− µD(qY∗|U||qY[t]|U|qU∗)− D(qZ∗||qZ[t]) − αD(q∗ ZY|XU||q [t] ZY|XU|qXU∗ ) + D(qZ∗|U||q [t] Z|U|qU∗) 以上で命題 7 が証明された。
5.4
最適分布への収束条件
命題 8. 式 (5.17) より、任意の t = 0, 1, 2, . . . に対し、以下の不等式が成り立つと仮定 する。 − µD(q∗ Y|U||q [t] Y|U|qU∗)− D(qZ∗||q [t] Z) − αD(q∗ ZY|XU||q [t] ZY|XU|qXU∗ ) + D(qZ∗|U||q [t] Z|U|qU∗)≤ 0 (5.22) このとき、分布更新アルゴリズムの定める分布列 q[t]∞ t=1は C(α,µ)(W1, W2) を与える最適分 布に収束する。 証明. 式 (5.22) の仮定が成り立つとすると、以下が成り立つ。 0≤ C(α,µ)(W1, W2)− F(α,µ)(q[t], q[t+1])≤ (µ + α) D(q∗||q[t])− D(q∗||q[t+1])(5.23) 式 (5.23) の両辺について t = 1 から T まで和をとると T X t=1 C(α,µ)(W1, W2)− F(α,µ)(q[t], q[t+1]) ≤ (µ + α)D(q∗||q[1])− D(q∗||q[T +1])(5.24) ここで、 ∆t = C(α,µ)(W1, W2)− F(α,µ)(q[t], q[t+1]) とおくと命題 6 より、{∆t}∞t=1は単調減少列である。したがって、式 (5.24) より T ∆T ≤ T X t=1 ∆t ≤ (µ + α) D(q∗||q[1])− D(q∗||q[T +1])≤ (µ + α)D(q∗||q[1])第 5 章 緩和項を用いた容領域計算アルゴリズム 34 これより 0≤ ∆T ≤ µ + α T D(q ∗||q[1])→ 0(T → +∞) 以上より、分布更新アルゴリズムが最適値を与える分布へ収束することがわかる。以上 で命題 8 は証明された。 命題 8 の式 (5.22) の仮定が成り立つかどうかは不明であり、収束性の証明はなされて いない。収束性について、次のような考察がなされている。 • µ = 1, 0 のとき、この仮定は成り立つ。この場合は単一通信路の通信路容量を計算 していることと同義であり、収束が保証されている。 • 0 ≤ µ ≤ 1 のときも、α が十分大きい値であるときは、この仮定は成り立ちそうに 思える。しかし、現時点ではこのことは証明されていない。 次章では、緩和項を用いた容領域計算アルゴリズムについて数値実験を行い、アルゴリ ズムの収束性について評価する。また、アルゴリズムの持つ特性について考察を行う。
第
6
章
数値実験
この章では、補正項を用いた容量域計算アルゴリズムの数値実験を行い、アルゴリズ ムの収束性を考察する。6.1
実験結果
6.1.1
2
元における数値実験
2 元における数値実験では、図 6.1 に示すような劣化型 2 元対称放送通信路に対して実 験を行う。ҧ
𝛽
𝛽
𝑈
𝛽
ҧ𝛾
1𝛾
1𝑋
ҧ
𝛽
1ҧ𝛾
𝑌
𝛾
1ҧ𝛾
2𝛾
2ҧ𝛾
2𝑍
𝛾
2 図 6.1: 劣化型 2 元対称放送通信路 35第 6 章 数値実験 36 劣化型 2 元対称放送通信路の通信路容量を求める理論式は以下である。
I(X; Y|U) =H(Y |U) − H(Y |U, X)
=H(β∗ γ1)− H(γ1) I(Z; U ) =H(Z)− H(Z|U) =1− H(β ∗ pγ¯) ここで β∗ γ1 =β ¯γ1+ ¯βγ1 β∗ pγ¯ =β ¯p¯γ+ ¯βp¯γ pγ¯ =γ1γ¯2+ ¯γ1γ2 各種パラメータの設定 2 元の実験で使用するパラメータを以下のように設定する。ここで、C(α,µ)(W 1, W2) を 求めるアルゴリズムによって定められるU × X × Y × Z 上の分布列をnqµ[t] o+∞ t=0 とし、そ のときの µ を明示する。 各種パラメータの設定 αk = 106× µk, µk = 1 ρk , ρ : 1→ 104, ρk+1 = ρk+ 0.1, k = 0, 1, 2, . . . 分布更新の停止条件は、任意の (u, x, y, z) のもとで qµ[t] k(u, x, y, z)− q [t−1] µk (u, x, y, z) ≤ϵ, ϵ = 10 −4 を満たす最小の t(これを t∗とする) のとき停止する。 初期分布の設定 1. k = 0 に対しU × X × Y × Z 上の分布 qµ[0]0 をを適当にとる 2. k = 1, 2, . . . に対し初期分布を qµ[0]k = q [t∗] µk−1とする 2 元通信路 A,B の確率行列を以下に示す。 2 元の遷移確率行列 A : W1(y|x) = " 0.95 0.05 0.05 0.95 # , W2(z|y) = " 0.95 0.05 0.05 0.95 # B : W1(y|x) = " 0.95 0.05 0.05 0.95 # , W2(z|y) = " 0.70 0.30 0.30 0.70 #
第 6 章 数値実験 37 0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
R
2[bit]
R
1[bit]
A-実験値
0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8R
2[bit]
R
1[bit]
A-実験値
A-理論値
0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8R
2[bit]
R
1[bit]
A-実験値
A-理論値
A-総当たり
0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8R
2[bit]
R
1[bit]
A-実験値
A-理論値
A-総当たり
A-近似
0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8R
2[bit]
R
1[bit]
A-実験値
A-理論値
A-総当たり
A-近似
B-実験値
0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8R
2[bit]
R
1[bit]
A-実験値
A-理論値
A-総当たり
A-近似
B-実験値
B-理論値
0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8R
2[bit]
R
1[bit]
A-実験値
A-理論値
A-総当たり
A-近似
B-実験値
B-理論値
B-総当たり
0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8R
2[bit]
R
1[bit]
A-実験値
A-理論値
A-総当たり
A-近似
B-実験値
B-理論値
B-総当たり
B-近似
図 6.2: 2 元の通信路容量域 図 6.2 より、A,B どちらにおいても実験値・理論値・総当たりアルゴリズム (6.2 参照) の実験値・近似アルゴリズム (6.3 参照) の実験値が一致している。したがって、2 元の劣 化型放送通信路では補正項を用いた容量域計算アルゴリズムによって最適な分布に収束 しているのではないかと考えられる。6.1.2
3
元における数値実験
2 元における数値実験では、図 6.1 に示すような劣化型 2 元対称放送通信路に対して実 験を行う。 各種パラメータの設定 2 元の実験で使用するパラメータを以下のように設定する。ここで、C(α,µ)(W1, W2) を 求めるアルゴリズムによって定められるU × X × Y × Z 上の分布列をnqµ[t] o+∞ t=0 とし、そ のときの µ を明示する。 各種パラメータの設定 αk = 105× µk, µk = 1 ρk , ρ : 1→ 104, ρk+1 = ρk+ 0.1, k = 0, 1, 2, . . .第 6 章 数値実験 38 分布更新の停止条件は、任意の (u, x, y, z) のもとで qµ[t] k(u, x, y, z)− q [t−1] µk (u, x, y, z) ≤ϵ, ϵ = 10 −2 を満たす最小の t(これを t∗とする) のとき停止する。 初期分布の設定 1. k = 0 に対しU × X × Y × Z 上の分布 qµ[0]0 をを適当にとる 2. k = 1, 2, . . . に対し初期分布を qµ[0]k = q [t∗] µk−1とする 3 元通信路 C の遷移確率行列を以下に示す。 3 元の遷移確率行列 C : W1(y|x) = 0.90 0.05 0.05 0.05 0.90 0.05 0.05 0.05 0.90 , W2(z|y) = 0.90 0.05 0.05 0.05 0.90 0.05 0.05 0.05 0.90 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 0.2 0.4 0.6 0.8 1 1.2
R
2[bit]
R
1[bit]
C-1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 0.2 0.4 0.6 0.8 1 1.2R
2[bit]
R
1[bit]
C-1
C-2
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 0.2 0.4 0.6 0.8 1 1.2R
2[bit]
R
1[bit]
C-1
C-2
C-3
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 0.2 0.4 0.6 0.8 1 1.2R
2[bit]
R
1[bit]
C-1
C-2
C-3
C-4
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 0.2 0.4 0.6 0.8 1 1.2R
2[bit]
R
1[bit]
C-1
C-2
C-3
C-4
C-5
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 0.2 0.4 0.6 0.8 1 1.2R
2[bit]
R
1[bit]
C-1
C-2
C-3
C-4
C-5
総当たり
図 6.3: 3 元の通信路容量域 図 6.3 より、C-1 は総当たりと近い結果を示しており、大域収束した場合に結果と近い のではないかと考えられる。しかし、C-2∼C-5 については、初期分布によって異なる収 束が確認された。これについての考察を 6.4 に記述する。第 6 章 数値実験 39
6.2
総当たりアルゴリズム
劣化型放送通信路は 2 元対称の場合において、理論値を求めることができる。しかし、 3 元の場合の理論式はわかっていない。そのため、3 元の場合においても提案されたアル ゴリズムの描く容領域と比較するために、次のような総当たりアルゴリズムを考えた。 2 元の場合 1. qU X(u, x) = " h i j k # と置く 2. k = 1− (h + i + j) とし、h, i, j のステップ幅を 0.1 として 0 ≤ h + i + j ≤ 1 の範囲 で動かし q = qU X(u, x)W1(y|x)W2(z|y) を計算する 3. 任意の µ に対し、µI (X; Y|U)q+ I (Z; U )qが最大となる q をその µ の最適分布 q∗と する 4. q∗のときの I (X; Y|U) と I (Z; U) をグラフにプロットする 以上の手順を µ を 1→ 0 の範囲で動かしプロットしていく。 3 元の場合 1. qU X(u, x) = h i j k l m n o p と置く 2. p = 1− (h + i + j + k + l + m + n + o) とし、h, i, j, k, l, m, n, o のステップ幅を 0.1 とし て 0≤ h + i + j + k + l + m + n + o ≤ 1 の範囲で動かし q = qU X(u, x)W1(y|x)W2(z|y) を計算する 3. 任意の µ に対し、µI (X; Y|U)q+ I (Z; U )qが最大となる q をその µ の最適分布 q∗と する 4. q∗のときの I (X; Y|U) と I (Z; U) をグラフにプロットする 3 元の通信路において qU X(u, x) = h i j k l m n o p と置く。p = 1−(h+i+j+k+l+m+n+o)と して、h, i, j, k, l, m, n, o のステップ幅を 0.1 として 0≤ h+i+j+k+l+m+n+o ≤ 1の範囲で動かし q = qU X(u, x)W1(y|x)W2(z|y) を計算する。ある µ のとき、µI (X; Y |U)q+I (Z; U )q
が最大となる q を q∗とする。q∗のときの I (X; Y|U) と I (Z; U) をグラフにプロットする。
第 6 章 数値実験 40
6.3
近似アルゴリズム
DBC の通信路容量域を求める問題において、その目的関数 C(µ)(W1, W2)≜ max p∈P(W1,W2) {µIp(X; Y|U) + Ip(Z; U )}は p(u, x) = p(u)p(x|u) の p(x|u) を固定すると、p(u) について上に凸な関数を目的関数と
する凸最適化問題となる。実際、µIp(X; Y|U) + Ip(Z; U ) について µIp(X; Y|U) + Ip(Z; U ) = X u p(u) " µ ( X x,y p(x|u)W1(y|x) log W1(y|x) p(y|u) ) +X z
p(z|u) logp(z|u) p(z) # 上式の第一項 X u p(u) " µ ( X x,y p(x|u)W1(y|x) log W1(y|x) P xp(x|u)W1(y|x) )# は p(u) に線形な関数である。また、 X u p(u) " X z
p(z|u) log p(z|u) p(z) # =X u p(u)X z
{p(z|u) [log p(z|u) − log p(z)]}
=X u p(u)X x,z p(x|u)(W1W2)(z|x) " logX x p(x|u)(W1W2)(z|x) − log X u,x p(u)p(x|u)(W1W2)(z|x) # 上式の第一項は p(u) について線形な関数、第二項は p(u) について上に凸な関数である。 以上から、µIp(X; Y|U) + Ip(Z; U ) は p(x|u) を固定することで、凸関数となっていること
がわかる。したがって、C(µ)(W 1, W2) を数値的に求める問題は凸関数を目的関数とした 凸最適化問題になることがわかる。 前節の総当たりアルゴリズムは、2 元、3 元の場合において妥当な結果を得ることがで きていると考えられる。しかし、その計算量は交互最大化アルゴリズムと比べて非常に 大きなものとなっている。以下では、p(x|u) についての総当たりと p(u) についての交互 最大化を組み合わせた近似アルゴリズムについて記述する。
