エントロピー・モデルにおける数理計画

(1)

特集

エントロビー・モデル

エントロビー・モデルにおける数理計画

神保雅一

エントロピー・モデルは，情報が少なく，不確定要素が多い場合に，情報理論を応用してその内部構造の一端を探る 1 つの便利な手法であろうと思われる.ここでは，

2 ,

3 のエントロビー・モデルとそれに関する数理計画問題について論じる. 1.因子情報路(国沢 [8

J

)

ある商品に m 銘柄があり，それぞれの販売価格 (コスト)が，九… ， lm(>O) である.このとき，大衆のランダムな選択による各銘柄の選択比率 P=(Ph … ， P明)を，

里佳1_→ rnRY

l

(p)

P

となる p を用いて推定するのが 1 因子情報路による方法である.ただし， H(p)= 一五戸 log 釦

"‘

I(p)=511小

である.すなわち， H(p) は，大衆が銘柄を選択する際の選択のあいまいさの度合いを表わす mea sure であり， l は平均コストである. 1 因子情報路においては，単位コストあたりのあいまいさを最大にするような比率 p で推定しようとし、うわけである.この問題は，制約条件五戸 =1 P企 o

(i=l

, "',

m)

のもとで，

H(p)/l (p)

を最大にする.

)

-(

1979 年 10 月号とし、う数理計画問題と考えることができるが，その最適解は， Pi=W-!i( ただし W は 'L. w-!i= 1 の最大正根)として得られ，その最大値は logw である.この問題に関連して，平均コスト I を一定に保ち，エントロピーを最大にする問題制約条件

El小 =l

(

2 )

EfFl ， pd ミ O

のもとで， H(p) を最大にする

を考える. (2) の最適解を J の関数とみなし H(Ï)

と書くと， (1)の解は，原点、を通り H(l) の曲線に接する直線の傾きである.

2 .

判別関数によるモデル 2 種類の確率分布 p=(ρ1，… ， pm) と r=

(rr , …,

rm) に対して，初、

D(p

,

r

)

=

-

'

L

.

pdog

~"-τ~l ri を， p と r の判別関数とよぶ. (2) の形のモデルを拡張して，制約条件

d

m

一一一一 C0 ・ 'b ' R 一一 b A 4 n u ム> mZ

剖戸

(

3 )

のもとで，

D(p,

r) を p に関して，最小にする. (ただし，

b.i

,

ks は定数であり r は与えられた確率分布) なる凸計画問題を考える.この問題の最適解を求

(2)

めるには，反復尺度法(Iterative

Scaling Methｭ

od) によるのが便利である (Darroch

&

Ratchif

[6J ，国沢 [8J). (3) の問題は，一般性を失うことなく，つぎのように修正できる. 制約条件

Z1asfpt=h8

5=l

,

・・・，

c

Pi'?O

i=

1 ，・ "， m

(

3 )

'

のもとで， D(p ， r) を最小にする. (ただし， asi 二三 0，

L

:

aSi=

1,

L

:

hs=

1 ,

hs ミ 0)

(

3 )

，の形の最適解は，つぎの反復尺度法によって求められる. 反復尺度法

(

i

)

Pi(O)=qi を初期確率分布とする.

(川 p/

k

₊

ll

_{=〆官(すい)ぺ=1 ，"'， m}

とする.ここに， h.，(加 =s ーム aSipi'!<J ，

L

asiÞ 刷

s=

1 ，・， C この手)1原によって， j片山は， (3)' の最適解を与える確率分布に収束する.また， (3) の最適解を与える確率分布は， & u

u a

dH

円

μa

r

一一

P

_i

₌

1, 2 ，・ー， m の形で与えられることも知られている. また， (3)' の双対問題制約条件

(

3 )

"

t

s

>

O

s ニ 1 ，・ "， C のもとで，。 (t)

=e

L

:

q

i

n

t

sa

S

i_

L

:

h

s

l

o

g

t

s

を最小にする. と (3)' との duality に関する議論が Charnes

and Cooper

[3 J にある.

3 .

D

i

s

c

r

e

t

e

Memoryle自由 Channel における

Capacity

と Con自仕ained

Capacity

n 個の入力シンボルと m 個の出力シンボルをも

っ Discrete

Memoryless

Channel を，

P=( 釦 1')

(i

=I

,

…

.m;j=l.

….

n)

Pi l 立 O， PPM=l

なる推移行列で表わす.そして，その相互情報量

l(p， P)= い pj| ￠ log す

の最大値を Capacity とよんでいる. ただし， p=(ρh … ， pm) および q=(qh ・・・， qπ) はそれぞれ入力確率分布，出力確率分布である.

Capacity

を求める直接的な手法が，

Muroga [9J

,

Cheng

[5J

,

Takano [

1

J 等によって研究されている. 一方で，

Arimoto[ 1

J と Blahut [2J は，

Capacity

を求める簡単な逐次近似法を提案した.さらに，

Blahut

は，制約条件

1 L

:

aSipi 孟 h.

s=

1,…

,

c

p之 o

i=l

,

…

,

m

;

(

4 )

なるもとで相互情報量 I(p， P) を最大|

にする

)

なる形の凸計画問題の最適解を求める近似法も導いている. この最適解を constrained

c

a

p

a

c

i

t

y

とよんでいる.

4 .

R

e

l

a

t

i

v

e

Capacity

入力シンボル Bi を送るのに，コストん (>0) を要する場合には，相互情報量を大きくする p を求めるより，単位コストあたりの相互情報量を大きくするほうがより妥当であると思われる.ここでは，つぎのような数理計画問題について論じる. 制約条件 m

AP4=1

戸ミ O

のもとで (5)

l(p

,

P)

R(p)= ー

_l(p)

を最大にする.ただし， l(p)= L: l!p. この問題の最適解を relative capacity とよんでいる (R巴 za

[

I

O

J

)

.

R(p) は p に関して quasi concave であり，この問題は quasi-convex

programming であるが，

Jimbo & Kunisawa

(3)

案した.この方法は，簡単であり，また syste matic である.また， capacity を求める Arimoto ， Blahut の結果を lt=

1 (

i

=

1 ， … ， m) なる特殊ケースとして含んでいる.その Iteration 法はつぎのとおりである.

I

t

e

r

a

t

i

o

n

Procedure

(

*

)

a=mln

んとし，

(

i

)

初期確率戸山 (>0) を任意に選ぶ.

(

i

)

k ステップ目の確率分布 pω を用いて，

(

k

+

1)ステップ日の確率分布 pほ+1)をつぎのように作る. 五円+l )=p/k₎

_{exp [}

_a

_D

_i

₍

_k

₎

_/

_I

_J

ただし， -S 一〉 's 一k 44 フバ F ρ 一位

g

H

o j J M Y --危 -av''' 巴、 i

uu

」一=ー

た的 D 市町'

L

L 』初出 ="E. Pi 伽1)

p/k+

1 )

=ん (k +l )/W(k) によって pt(k+l) を定める. この Iteration 法に関して，つぎの定理が成り立つ. 定理この Iteration

Procedure(

*)によって作られた p 山 (k=0， 1 ， 2 ， …)に関して， R(p 伽)は単調に増加し，

r

e

l

a

t

i

v

e

c

a

p

a

c

i

t

y

C

R に収束する.また C

R

を達成する出力確率分布 q=(qt， …， qn) は，一意に決まる.

5 .

I

t

e

r

a

t

i

o

n

Procedure(

*)の収束の証明ここで，前節の Iteration

Procedure

(*)の収束性を証明しておこう. 九 pili

Dt(p)

=

"

E

.

pj

I

dog

r~ l'

(i=

1 , "',

m)

j=l qj とおくと，相互情報量 l(p， P) は，

l(p

,

P)

=

"

E

.

P蓜i(P)

と書ける . k ステップ目と (k+ 1)ステァプ目の確率分布 pω ， p伽1)を簡単のために，

p

,

r で表わす.そして，

ft=exp

[aDt(p)/ん] ω =

"

E

.

P凬

とおくと， n=pifdw であり，つぎの補題が成り立つ. 補題上で与えた確率分布 p ， r に対して，

1

0

11:ﾀ R(p) 豆一五ー←孟 R(r)

a

が成り立つ. ただし，

R(p) =l(p

,

p)/l(p) で hH ノよ

式

等

不 A 一の g 一 a tO 一 fnl 一

的民話一

4

白印判

=J 凡 2 A Y I 明

り証

あであることが容易にわかる .

q=

(q/， …， φ)

,

s=(s/' ・"， sη) を入力確率分布 p， r に対応する出力確率分布とすると， D(r， p) 孟 D(s，

q

)

が成り立つ.ただし， D( ・，・)は判別関数である. このことに注意すると，

l(r

,

P)

=

"

E

.

nD r)

=

"

E

.

nD p)

-D(s

,

q

)

~~"E.nlí logβ -D(r， p)

_a

であり， À= "E. udi=wl(r)/I(p) を用いて，

al(r

,

P)-I(r) l

ogﾀ

ミ"E.

_官

n

l

i

log 五 -aD(r，p)

_w

_---,

_，~-，

-l(r)

log 型旦

_--~

_l

₍

_p

₎

-.,

1 (

r

)

=

"

E

.

n

(

l

i-a)

log~-l(r)

l

o

g

~ー

_l(p)

1 (

r

)

-a

_{,,_\}

1

1 (

r

)

~ (l(r) 一)

1 _og

τ一一一一 l(r)

₁

₍

_p

₎

_{-a qr)}

l

_lO

o

_g

g

~一一

_l(p)

が成り立つ(上の不等式の最後の不等号は判別関数の凸性より導かれる).この不等式の最右辺が非負であることは，つぎの関数

f

(

z

)

=

(z-a)

log と2-zlog7(は a>O)

が， z~a で非負であることより直ちに導かれる.

これで、収束の単調性が言えた.つぎに，

I

t

eraｭ

t

i

o

n

Procedure

(*)の収束性を示す.

定理の証明 fí(恥 =exp

[aDi(p(k))/I

iJ,

Uí(お)=

p

i

(

k

)

l

i

/

l

(p山)

(i

=1

, …,

m; k=O

,

1 ,

2 , …)

とおき，

(4)

n W(k) ニ Zρ ，(恥 f，山， '1:=1 え恥 ='L，p ，山 l， f/剖 /l

(

p

(

k

l

)

n

='L,

U/

kl

_f/削 ' 1 :=1 とおくと，定義より， Pi(肘 1l=j片山 fí(kl/W山である.補題により，任意の k=O， 1 ， 2 ，…に対して，

l

o

g

j!(kl~ ~I __(>+1 R(p山)豆一←ム一三五 R(p(k+1 l) 孟 CR である.したがって， {R(p は+1l) }および{log j! (kl/a} はともに単調に増加し，同じ値に収束する.さて， p* を relative capacity を達成する確率分布とし， uグ =pi*ldl(p*) とおく. さらに， q(削 (k=O， 1 ， 2 ，・ー)およびザを，それぞれ，入力確率 p 山， p* に対応する出力確率とする. U /k+1l/ Uí(却 =

f

i

(

k

l

/

j! (kl に注意すれば， D(u大がお )

-D(u*

,

U

(

k

+1

l

)

冊目ー (k+1 l

=

'L,

U

i

*

log 竺万子 1 峰も =a 'L， uグ Dí(P山)

-log

j!山

=1Jibm(p*)+Drf)一 logj!(ペ

_{ル、 F ノ lazlj}

=aC

_{R 一}

log λ山 +τ竺~D(q*， q(船

(6)

l

(p*)

を得る.この等式の右辺の最後の項は非負であるから，

1

(r\.!__.J..__(,")\ T't./__.J..__(v+1)¥1__匀 l02À 曲〉

士 ID(u* ， u(kl) -D(U* ， U(k+ 1J)!;;;; 仏一 ~V~^

U l

a

が k=O， 1 ， 2 ，…に対して成り立つ.これらを k=O から k=N-l まで加えると，任怠の N に対して，

J21(CR-h2fT) 孟よD(u*，

U

O)

(<∞)

k=O

a

が成り立つ.したがって，

{

l

o

g

j!ω/a} は relative capacity に収束し，ゆえに， {R(p山) }も CR に収束する.また，不等式 (6) から，

O 主主 τ竺~D(q， q(kl) 豆 D(u ，

U(kl)-D(u*

,

U

(

k

+1

l

)

=

l

(p*)

が，任意の k=O， 1 ， 2 ，…に対して成り立つが，これらを前と同様に k=O から N-l まで加えると，

D(q*

,

qN) ー→o (N→∞) であることがわかる.したがって q* は一意である. これで定理の証明が終わったわけで、あるが，この Iteration Procedure の収束の速さについては，

r

e

l

a

t

i

v

e

capacity を達成する入力確率 p* が一意で、任意の i に対して， Pi*>O であるときには，この収束の誤差は，指数オーダーで減少することがわかっている.また， pキが relative capacity を達成するならつぎの Kuhn-

Tucker

条件

Di(P*)

li し R 話 CR Pí*>O の時戸水 =0 の時を満たさなければならないことも容易にわかる. ところで relative capacity をつぎのように解釈することもできる.すなわち，計画問題 (4) において，制約条件を 2 つにした場合，制約条件 m

zf小豆 1

zp=l ，

p必 O

(

4 )

'

のもとで，相互情報量 I(p， P) を最大にするなる問題の最適解を，とくに capacity

a

t

cost とよび， C( l) と書くと， C( l) は 1 に関して単調増加であり凹である. この曲線 C( l) に接して，原点を通る直線の傾きが relative capacity である.

6 .

R

e

l

a

t

i

v

e

Capacity のエントロピー・モデル的解釈市場に n 銘柄 Bh"' ， Bn があり，その販売価格は市場の状態 Sí (i =I ， … ， m) によって異なるとする.状態がふであるときに銘柄 Bj の販売価格はん (>0) であるとする.また，状態ふのもとでの各銘柄の選択比率向 lí (j =I ，… ， n) はわかっているものとする.もしこの選択比率がわからないならば因子情報路を用いて P!lí (j=

1 , …,

(5)

n) を推定すればよい.われわれは，どの状態が生起するかということに関してなんら情報を得られないとして，各銘柄 Bj が選択される比率を推定したい.ここで，

p =

(P J， … ， pm) を状態 8=(SJ，

"

Sm) の生起確率とし，つぎの 3 つの仮説を設定してみる.

I

平均コスト J(p)=5仰j 1

i ん=号pili を

小さくしたい(ただし，ん =pj1414j) ・

H

状態は，しようとする. どの状態にもかたよらない生起を皿各状態における最適配分比率 p・ li=(Plli， … ， pπ1 i) と q=(qJ， … ， qn) との「距離(半U 5]1j関数)

J

Di=

'E,

pj

I i

log 企1

i

q

j

i=l

,… ,

m

の平均千戸 Di をできるだけ小さくしたい.すなどの配分比率にもかたよらない配分をしたわち，し、. これら 3 つの仮説を同時に満足するような配分比率 q を推定することを考える. ところで， ρ 1I i

5 仰f

1

i

log す孟 EP4Pj141ogD石戸

であるから，仮説 E は，

qj=

'E,

PiPj

I もとおくことによって満足される.したがって，'E，戸 Ði= l(p， P) となり，

'E,

piﾐi

l(p

,

P)

二 =)=R(p)

l(p)

を最大にする問題に帰着される.したがって，これは (5) の解，すなわち relative capacity を求める問題に他ならない. 参ラ巻文献

[

1 J Arimoto

,

S. ,

An AIgorithm f

o

r

Computing

t

h

e

Capacity o

f

Arbitrary D

i

s

c

r

e

t

e

Memory-111 川11山11川川11川酬H川川111川111川H川l

[2J

[3

J

[4J

[5

J

[6J

[7]

[8J

l

e

s

Channels

,

IEEE Trans. l

n

f

o

r

m

.

Theor

;o;,

IT-18

,

1

4-

2

0 (

1

9

7

2 )

.

Blahut

,

R

.

E. ,

Computation o

f

Capacity and

Rate D

i

s

t

o

r

t

i

o

n

Functions

,

IEEE

,

T

r

a

n

s

.

Inf01明.

Theor

;ý,

IT

-18

,

4

6

0 -

4

7

3 (

1

9

7

2 )

.

Charnes and Cooper

,

Constrained

Kullback-L

e

i

b

l

e

r

e

s

t

i

m

a

t

i

o

n

;

g

e

n

e

r

a

l

i

z

e

d

Cobb-Douglas

balance and unconstrained convex programｭ

ming

,

A

t

i

.

Accad.

58 ,

5

6

8 -

5

7

6 .

N

a

z

.

Lincei

,

Rc s

e

r

8 ,

Charnes

,

Cooper

,

and Learner

,

Constrained

Information Theoretic C

h

a

r

a

c

t

e

r

i

z

a

t

i

o

n

ln

Consumer Purchase Behaviour

,

J

.

Opr. R

e

s

.

S

o

c

.

vo

l

.

2

9 .

9 p

p

.

8

3

3 -

8

4

2 .

Cheng

,

M. C.

,

On t

h

e

Computation o

f

Capacity o

f

a D

i

s

c

r

e

t

e

Memoryless Channel

,

I

n

f

o

r

m

.

Contr

,

24 ,

2

9

2 -

2

9

8 .

Darroch and Ratchiff

,

Generalized i

t

e

r

a

t

i

v

e

s

c

a

l

i

n

g

f

o

r

l

o

g

-

l

i

n

e

a

r

models

,

Annals of

Math. S

t

a

t

.

vo

l

.

43 ,

1972

,

1

4

7

0 -

1

4

8

0 .

Jimbo

,

M. and Kunisawa

,

K. ,

An

I

t

e

r

a

t

i

o

n

Method f

o

r

C

a

l

c

u

l

a

t

i

n

g

t

h

e

R

e

l

a

t

i

v

e

Capacity

(

t

o

a

p

e

a

r

)

.

間沢清典，エントロピーモデル，日科技連出版.

[9 J Muroga

,

S. ,

On t

h

e

c

a

p

a

c

i

t

y

o

f

a D

i

s

c

r

e

t

e

Channel 1

,

J

.

Ph

;

s

.

S

o

c

.

Jap

,

vo

l

.

8 ,

4

8

4-

4

9

4 [

1

0 J

[

1

1 J

(

1

9

5

3 )

.

Reza

,

F

.

M. ,

An l

n

t

r

o

d

u

c

t

i

o

n

t

o

lnformati側

Thcl町'Y，

McGraw-Hill

,

New York.

Takano

,

S. ,

On a method o

f

C

a

l

c

u

l

a

t

i

n

g

t

h

e

Capacity o

f

a

D

i

s

c

r

e

t

e

Memoryless Chanｭ

nel

,

lnform

,

C

o

n

t

r

.

29 ,

3

2

7 -

3

6 (

1

9

7

5 )

.

(じんぼ・まさかず東京理科大学) 呈三

会員名簿ができます

一

=

= 一一先に皆様よりお送りいただし、た名簿作成資料にもとづき，現在名簿発行の準備をすすめており，

1

2

月にはでき上る予定です.頒布は希望者のみとさせていただきますので，学会事務局 (03-81 ラー3351

)

までお申込みください(頒布価格 1000 円).

Z

塁

童

I!III!川川11刷川H川111111川11川H川川H川H川川H川1111川H川1111川川111川H川山H川川H川川H川H川川川川111H川川111川川H川川111川H川川川111川H川川H川11川川川|附附H則|川川 1111111111111111111111111111111111111111111111111111111111川 11111111111111111111111111111川111111111111111川川 1111川川川川 111111111川 111111111111111111111111111川1I!!!1II!I!I!I!I!!!儒

5

8

9