6 数値実験 35
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) log p(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) [logp(z|u)−logp(z)]}
=X
u
p(u)X
x,z
p(x|u)(W1W2)(z|x)
"
logX
x
p(x|u)(W1W2)(z|x)−logX
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(µ)(W1, W2)を数値的に求める問題は凸関数を目的関数とした 凸最適化問題になることがわかる。
前節の総当たりアルゴリズムは、2元、3元の場合において妥当な結果を得ることがで きていると考えられる。しかし、その計算量は交互最大化アルゴリズムと比べて非常に 大きなものとなっている。以下では、p(x|u)についての総当たりとp(u)についての交互 最大化を組み合わせた近似アルゴリズムについて記述する。
DBCにおいて、境界の領域を与える最適な分布をq∗(u, x) = q∗(u)q∗(x|u)とする。以
第 6 章 数値実験 41 下ではq(x|u)をq∗(x|u)に固定し、W0(x|u)と表記する。
F(pU, qU) =µI(X;Y|U) +I(U;Z) +D(qZ||pZ)−D(qU||pU)
=X
u
q(u) (
µX
x,y
q∗(x|u)W1(y|x) logW1(y|x) q∗(y|u) +X
z
q∗(z|u) log q∗(z|u) q(z)
+X
z
q∗(z|u) logq(z) p(z)
)
−X
u
q(u) logq(u) p(u)
=X
u
q(u) (
µX
x,y
W0(x|u)W1(y|x) log W1(y|x) P
xW0(x|u)W1(y|x)
+X
x,y,z
W0(x|u)W1(y|x)W2(z|u) log P
x,yW0(x|u)W1(y|x)W2(z|u) p(z)
)
−X
u
q(u) log q(u) p(u)
=X
u
q(u) log
exp{ApU(u)} · p(u) q(u)
=−X
u
q(u) log q(u) exp{ApU(u)}p(u)
=−X
u
q(u) log q(u)
1
K exp{ApU(u)}p(u) + logK
≤logK ここで
ApU(u) =µX
x,y
W0(x|u)W1(y|x) log W1(y|x) P
xW0(x|u)W1(y|x)
+X
x,y,z
W0(x|u)W1(y|x)W2(z|u) log P
x,yW0(x|u)W1(y|x)W2(z|u) p(z)
等号条件は
q(u) = 1
K exp{ApU(u)}p(u)
D(qZ||pZ)≤D(qU||pU)より、pU =qU のときF(pU, qU)は最大値 F(qU, qU) = µI(X;Y|U) +I(Z;U) 分布更新式を
q[t+1](u) = 1 Ktexp
Aq[t](u) q[t](u)
第 6 章 数値実験 42 ここで
Kt=X
u
exp
Aq[t](u) q[t](u) 命題 9. 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]) (6.1)
(a)≤ F(q[t], q[t+1]) (6.2)
(b)≤ F(q[t+1], q[t+1])≤. . . .
≤C(µ)(W1, W2)
ここで不等式 (6.1)および式 (6.2)の右辺に現れる量に関してはそれぞれ以下が成り 立つ。
F(q[t], q[t]) =Iq[t](X;Y|U) +µIq[t](U;Z) F(q[t], q[t+1]) = logKt
=Aq[t](u, x) + log q[t]
q[t+1]
F(pU, qU)の最適値を与える分布をq∗(u)とすると C(µ)(W1, W2) = max
pU {µIpU(X;Y|U) +IpU(U;Z)}
=F(q∗, q∗)
=µIq∗(X;Y|U) +Iq∗(U;Z) 収束性について次の命題が成り立つ。
命題 10. t = 0,1,2, . . . に対し、以下が成り立つ。
C(µ)(W1, W2)−F(q[t], q[t+1])
=F(q∗, q∗)−F(q[t], q[t+1])
=X
u
q∗(u)
Aq∗(u)−Aq[t](u)
+X
u
q∗(u) logq[t+1](u) q[t](u)
=−D(q∗Z||qZ[t]) +D(q∗U||qU[t])−D(qU∗||q[t+1]U )
第 6 章 数値実験 43 命題2の結果より、次の定理が得られる。
定理 2. Arimoto-Blahutアルゴリズムの定める分布列n q[t]U
o+∞ t=0
はt→ +∞のときqU∗ に 収束する。
証明. 命題2よりt = 0,1,2, . . . について以下が成り立つ。
C(W)−F(q[t], q[t+1])≤D(qU∗||qU[t])−D(q∗U||qU[t+1]) そこで∆t=C(W)−F(q[t], q[t+1])とおくと、
∆t≤D(qU∗||qU[t])−D(qU∗||qU[t+1]) t= 0,1,2, . . . T について和をとると、
XT t=0
∆t ≤D(qU∗||q[0]U )−D(qU∗||qU[T+1]) (6.3) 命題1より{∆t}Tt=0は単調減少列であるから式 (6.3)より、
T∆T ≤ XT
t=0
∆t ≤D(qU∗||q[0]U) これより
0≤∆t ≤ 1
TD(qU∗||q[0]U )→0(T →+∞) となり、分布更新アルゴリズムが最適値を与える分布へ収束する。
この近似アルゴリズムは、総当たりアルゴリズムより計算量が少なくなることが期待 されたが、3元以降では総当たりアルゴリズムより計算量が大きくなってしまうことがわ かった。
6.4 結果の考察
異なる収束が得られる理由を考察する。µ = 1のときの収束分布qU X∗ (u, x)を以下に 示す
第 6 章 数値実験 44
C−1 :
0.106 0.097 0.116 0.091 0.131 0.113 0.137 0.122 0.089
C−2 :
0.104 0.118 0.125 0.097 0.096 0.130 0.119 0.149 0.063
C−3 :
0.130 0.078 0.132 0.085 0.100 0.114 0.130 0.101 0.131
C−4 :
0.138 0.106 0.097 0.111 0.132 0.082 0.125 0.136 0.072
C−5 :
0.090 0.104 0.113 0.111 0.101 0.100 0.131 0.119 0.130
図 6.3より、µ= 1のとき、それぞれ同じR1, R2が得られている。つまり、初期分布に 関わらず目的関数はR1 =C(W1), R2 = 0へと収束している。しかし、分布は異なる値へ と収束している。したがって、R1 =C(W1), R2 = 0を与える最適分布が複数存在してい ることがわかる。以上より、それぞれの分布は目的関数を交互最大化によって同じ値へ と最大化させているが、目的関数上では異なる座標に収束しているのではないかと考え られる。
第 7 章
収束の十分条件
安井[5]は、自身の提案したArimoto-Blahut型通信路容量域計算アルゴリズムにおい て、分布列が領域の境界を与える最適分布に収束するための十分条件を得た。次節では、
緩和項を用いた容量域計算アルゴリズムが定める分布列が最適分布に収束するための十 分条件を導き、安井の結果と比較を行う。
7.1 凸領域における収束
f(α,µ)(q)を以下のように定義する。
f(α,µ)(q) =F(α,µ)(q, q)
=µIq(X;Y|U) +Iq(Z;U)−αD(qZY|XU||W1, W2|qXU)
−µD(qY|XU||W1|qXU)
f(α,µ)(q)のk−上位集合を以下のように定義する。
定義 1.
Sk,(α,µ) ≜
q|f(α,µ)(q)≥k
集合Tk,(α,µ)(˜q)をq(˜∈ Sk,(α,µ))から連続経路で到達できる全てのq(∈ Sk,(α,µ))の集合と 定義する。このとき、補題 8を得る。
補題 8. q[t]∈ Sk,(α,µ)であると仮定する。このときアルゴリズムによりq[t]から生成され
るq[t+1]はTk,(α,µ)(q[t])に入る。
証明. pをq[t]で固定したときの目的関数を
F˜q(α,µ)[t] (q) = F(α,µ)(q[t], q)
45
第 7 章 収束の十分条件 46 とし、そのk−上位集合を
S˜k,(α,µ) = n
q|F˜q(α,µ)[t] (q)≥k o
とする。補題2よりf(α,µ)(q)≥ F˜q(α,µ)[t] (q)なのでS˜k,(α,µ) ⊆Sk,(α,µ)である。また、q =q[t]
であるときf(α,µ)(q[t]) = ˜Fq(α,µ)[t] (q[t])となるのでq[t]∈S˜k,(α,µ)である。
pを固定するとF(α,µ)(p, q)はqで上に凸である。したがってS˜k,(α,µ)は凸集合である。
S˜k,(α,µ)が凸集合であることより、∀q′ ∈ S˜k,(α,µ)とq[t]を結ぶ線分上の任意の点はS˜k,(α,µ) に属する。Tk,θ(q[t])はq[t](∈ Sk,(α,µ))から連続経路で到達できる全てのq(∈ Sk,(α,µ))の集 合なので、S˜k,(α,µ)⊆Tk,(α,µ)(q[t])である。
凸関数F˜q(α,µ)[t] (q)の最適分布をq[t+1]とすると、q[t+1]= arg max ˜Fq(α,µ)[t] (q[t])である。その ためF˜(α,µ)
q[t] (q[t+1]) ≥ F˜(α,µ)
q[t] (q[t])≥ kとなり、q[t+1] ∈ S˜k,(α,µ)である。したがってq[t+1] ∈ Tk,(α,µ)(q[t])となる。
以後、領域T で関数f(α,µ)(q)が上に凸だと仮定して議論する。
補題 9. 関数f :Rn→ Rが領域T ⊆Rnで上に凸であることと、T が凸集合であり、任 意のx, y ∈ T に対してf(y)≤ f(x) + (∇f|x)T(y−x)が成り立つことは同値である。こ こで、∇f|xは点xにおけるfの勾配である。
補題 9より命題 11を得る。
命題 11. 関数f(α,µ)(q)が集合T において上に凸であることと、T が凸集合であり任意の
qa, qb ∈T について
µD(qa Y|U||qb Y|U|qa U) +D(qa Z||qb Z)
+αD(qa ZY|XU||qb ZY|XU|qa XU)−D(qa Z|U||qb Z|U|qa U)≥0 (7.1) が成り立つことは同値である。
証明. f(α,µ)(q)を入力分布について偏微分すると
∂f
∂q(u, x, y, z) = X
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)
−Rs(q)
ここで Rs(q)≜ X
u,x,y,z
( µ qY|U(y|u) ·
P
x,zq(u, x, y, z) P
x,y′,zq(u, x, y′, z)
!′
− 1
qZ|U(z|u)· P
x,yq(u, x, y, z) P
x,y,z′q(u, x, y, z′)
!′
+ 1
qZ(z)· X
u,x,y
q(u, x, y, z)
!′
+α· 1
qZY|XU(z, y|x, u)
q(u, x, y, z) P
y′,z′q(u, x, y′, z′)
!′)
第 7 章 収束の十分条件 47 以上より
X
u,x,y,z
qb(u, x, y, z) ∂f
∂q(u, x, y, z)
qb
= X
u,x,y,z
qb(u, x, y, z)
µlog W1(y|x)
qb Y|U(y|u) + logqb Z|U(z|u) qb Z(z)
+αlog W2(z|y)W1(y|x) qb ZY|XU(z, y|x, u)
− X
u,x,y,z
qb(u, x, y, z)Rs(qb)
=f(α,µ)(qb)−Rs(qb) と
X
u,x,y,z
qa(u, x, y, z) ∂f
∂q(u, x, y, z)
qb
=f(α,µ)(qa) +µ X
u,x,y,z
qa(u, x, y, z) log qa Y|U(y|u) qb Y|U(y|u)
+ X
u,x,y,z
qa(u, x, y, z) log qa Z(z)qb Z|U(z|u) qb Z(z)qa Z|U(z|u)
+α X
u,x,y,z
qa(u, x, y, z) logqa ZY|XU(z, y|x, u)
qb ZY|XU(z, y|x, u) −Rs(qb)
が成り立つ。補題 9より
f(α,µ)(qa)≤f(α,µ)(qb) + X
u,x,y,z
∂f
∂q(u, x, y, z)
qb(qa(u, x, y, z)−qb(u, x, y, z)) したがって
µ X
u,x,y,z
qa(u, x, y, z) logqa Y|U(y|u)
qb Y|U(y|u) + X
u,x,y,z
qa(u, x, y, z) logqa Z(z)qb Z|U(z|u) qb Z(z)qa Z|U(z|u)
+α X
u,x,y,z
qa(u, x, y, z) log qa ZY|XU(z, y|x, u) qb ZY|XU(z, y|x, u)
=µD(qa Y|U||qb Y|U|qa U) +D(qa Z||qb Z) +αD(qa ZY|XU||qb ZY|XU|qa XU)
−D(qa Z|U||qb Z|U|qa U)≥0 以上より命題11は証明された。
式 (7.1)より、qa, qbをq∗, q[t]に置き換えれば µD(qY∗|U||qY[t]|U|qU∗) +D(q∗Z||q[t]Z)
+αD(qZY∗ |XU||qZY[t] |XU|qXU∗ )−D(qZ∗|U||q[t]Z|U|qU∗)≥0 (7.2)
第 7 章 収束の十分条件 48 が得られる。
以上より、緩和項を用いた容量域計算アルゴリズムに対し、領域の境界を与える最適 な分布に収束するための十分条件が得られた。
定理 3. 0 ≤ µ≤ 1に対し、q∗がTk,(α,µ)(˜q)に存在し、関数f(α,µ)(q)が領域Tk,(α,µ)(˜q)で 上に凸であり、初期分布q[0] ∈Tk,(α,µ)(˜q)ならば、F(α,µ)(p, q)はC(α,µ)(W1, W2)に下から 収束する。
7.2 十分条件の比較
q∗, q[t]∈ P(W1, W2)とすると補題6の証明と同様に f(α,µ)(q) = µIq(X;Y|U) +Iq(Z;U)
−αD(qZY|XU||W1, W2|qXU)−µD(qY|XU||W1|qXU)
=µIq(X;Y|U) +Iq(Z;U) = f(µ)(q)
また、式 (7.2)においても以下が成り立つ。
µD(qY∗|U||qY[t]|U|qU∗) +D(qZ∗||qZ[t])−D(qZ∗|U||q[t]Z|U|qU∗)≥0 (7.3)
目的関数f(µ)(q)と式 (7.3)の条件式は、安井の提案したアルゴリズムにおける目的関数
と大域収束のための十分条件に一致している。したがって、式 (7.2)の条件は、緩和項を 用いたことによりq∗, q[t]∈ P(W1, W2)という制約を満たす必要がないことから、安井の 得た大域収束の十分条件より緩いことが期待される。
第 8 章 結論
本研究では緩和項を用いた容領域計算アルゴリズムに対する数値実験を行った。アル ゴリズムの妥当性を検討するために提案した総当たりアルゴリズム、近似アルゴリズム との比較を行い、アルゴリズムの収束性について考察した。同一の通信路に対して複数 の収束が得られた理由について考察を行った。同じ結果を与える複数の最適分布が存在 する理由について予想を行ったが、これを証明するためにはさらに厳密な目的関数の解 析が必要だと考えられる。また、凸領域において緩和項を用いた容量域計算アルゴリズ ムが境界を与える最適分布へ収束するための十分条件を導いた。この結果は、安井の得 た結果を内包する形となっており、比較した場合に条件が緩い可能性がある。
49
謝辞
本論文は、電気通信大学 大濱靖匡教授ご指導のもと、筆者が在学中に行った研究の成果 をまとめたものです。ご多忙を極める中、先生から賜った御教示、御鞭撻に深く感謝致 します。また、ゼミや学会でお世話になりました川端勉教授、八木秀樹准教授、サント ソ・バグス准教授に心より感謝致します。そして、ともに研究に勤しんだ大濱研究室や 関連研究室の学生の皆様方に、感謝申し上げます。
50