情報論的学習理論テクニカルレポート 2009

Te hni al Report on Information-Based Indu tion S ien es 2009 (IBIS2009)

Latent Diri hlet Allo ation の量子アニーリング変分ベイズ学習佐藤一誠

Issei Sato

栗原賢一yKeni hi Kurihara

田中宗z

Shu Tanaka

宮下 精二xSeiji Miyashita

中川 裕志{

Hiroshi Nakagawa

This paper presents a quantum annealing variant of variational Bayes (QAVB)
for Latent Diri hlet allo ation(LDA). QAVB estimates latent topi s in LDA by introdu ing\quantum e e t" where we assume that the states of latent topi s are quantum states.
Experiments revealed QAVB nds a better lo al optimum than simulated annealing interms of the variational free energy in LDA.
Keywords: Latent Diri hlet allo ation, Variational Bayes, Quantum annealing

Abstra t:

1

Introdu tion

Latent Diri hlet allo ation (LDA)(Blei et al., 2003)
is one of the most famous topi models in do ument
modeling where do uments are represented as random
mixtures over latent topi s ( lasses) and ea h topi ishara terized by a distribution over words. In termsof lustering, LDA is regarded as a semanti lusteringmodel for words in do uments. In this study, we explore a Bayesian inferen e algorithm to estimate topi s(word lasses) in LDA by introdu ing \quantum e e t"where we assume that the states of latent topi s arequantum states.
Several studies that are related to ma hine learning with quantum me hani s have re ently been ondu ted. The main idea behind these has been basedon a generalization of the probability distribution obtained by using a density matrix, whi h is a self-adjoint
positive-semide nite matrix of tra e one. Wolf (2006)
onne ts the basi probability rule of quantum mehani s, alled the \Born Rule", whi h formulates a
generalized probability by using a density matrix, tospe tral lustering and other ma hine learning algorithms based on spe tral theory. Crammer and Glober 東 京 大 学 情 報 理 工 学 系 研 究 科, e-mail sator.dl.it .utokyo.a .jp,
Information S ien e and Te hnology, University of Tokyoy Google, e-mail keni hi.kuriharagmail. om,z 東京大学 物性研究所, e-mail shu-tissp.u-tokyo.a .jp,
Institute for Solid State Physi s, University of Tokyo
x東 京 大 学
理 学 系 研 究 科,
CREST, JST, e-mailmiyaspin.phys.s.u-tokyo.a .jp,
Dept. of Physi s, University of Tokyo, CREST and JST{ 東 京 大 学 情 報 基 盤 セ ン タ ー, e-mail nakagawadl.it .utokyo.a .jp,
Information Te hnology Center, University of Tokyoson (2006) ombined a margin maximization s hemewith a probabilisti modeling approa h by in orporating the on epts of quantum dete tion and estimation
theory (Helstrom, 1969). Tanaka and Horigu hi (2002)
proposed a quantum Markov random eld using a density matrix and quantum me hani s and applied to image restoration.
Generalizing a Bayesian framework based on a density matrix has also been proposed. S ha k et al. (2001)
proposed a \quantum Bayes rule" for onditional density between two probability spa es. Warmuth et al.
generalized the Bayes rule to treat a ase where theprior was a density matrix (Warmuth, 2005) and unied Bayesian probability al ulus for density matri es
with rules for translation between joints and onditionals (Warmuth, 2006). Typi ally, the formulas derived
by quantum me hani s generalization have retained
the onventional theory as a spe ial ase when thedensity matri es have been diagonal. Computing thefull posterior distributions over model parameters forprobabilisti graphi al models, su h as latent Diri hlet allo ation (Blei et al., 2003), remains diÆ ult inthese quantum Bayesian frameworks, as well as lassial Bayesian frameworks. In this paper, we generalize
the variational Bayes inferen e (Attias, 1999), whi h is
widely used framework for probabilisti graphi al models, based on ideas that have been used in quantum
me hani s.
Variational Bayes (VB) inferen e has been widelyused as an approximation of Bayesian inferen e forprobabilisti models that have dis rete latent variables.

For example, in a probabilisti mixture model, su h as
the SAVB algorithm.
a mixture of Gaussians, ea h data point is assigned to
Sin e SAVB does not ne essarily nd a global opa latent lass, and a latent variable orresponding totimum, we still need to run multiple SAVBs indepena data point indi ates the latent lass. VB is an opdently with di erent random initializations where mtimization algorithm that minimizes the ost fun tion.
denote the number of SAVBs. Here, let us onsider
The ost fun tion, alled the negative variational freerunning dependently, not independently, multiple SAVBs
energy, is a fun tion of latent variables. We have alled
where \dependently" means that we run multiple SAVBs
the ost fun tion \energy" in this paper.
introdu ing intera tion f among neighboring SAVBs
Sin e VB is a gradient algorithm similar to the Exthat are randomly numbered su h as j 1, j and j + 1
pe tation Maximization (EM) algorithm, it su ers from (see Fig.1(b)). In Fig.1, j indi ates the latent lassa lo al optimal problem in pra ti e. Deterministi anstates of N data points in the j -th SAVB. The indenealing (DA) algorithms have been proposed for thependent SAVBs have a very low transition probabilEM algorithm (Ueda and Nakano, 1995) and VB (Katahira ity among states, i.e., they have been trapped, at highet al., 2008) based on simulated annealing (SA) (Kirktemperature as shown in Fig.1( ), while the dependent
patri k et al., 1983) to over ome issue with lo al opQAVBs an hanges the state in that situation. This
tima. We alled simulated annealing based VB SAVB.
is be ause intera tion f starts from zero (i.e., \indeSA is one of the most well known physi s based appendent"), gradually in reases, and makes j 1 andproa hes to ma hine learning. SA is based on thej approa h ea h other, the state will then be moved
on ept of statisti al me hani s, alled \temperature".
into  . If there is a better state around sub-optimal
We de rease the parameter of \temperature" gradustates that the independent SAVBs nd, the depenally in SA. Be ause the energy lands ape be omes atdent SAVBs are expe ted to work well. The depenat high temperature, it is easy to hange the state
dent SAVBs are just QAVB where intera tion f and(see Fig.1(a)). However, the state is trapped at low
the above s heme are derived from QA me hanisms as
temperature be ause of the valley in the energy barwill be explained in the following se tion.
rier and the transition probability be omes very low.
This paper is organized as follows. In Se tion 2, we
Therefore, SA does not ne essarily nd a global optiintrodu e the notations used in this paper. In Se mum in the pra ti al ooling s hedule of temperaturetion 3, we motivate QAVB in terms of a density maT . In physi s, quantum annealing (QA) has attra ted
trix. Se tion 4 and 5 explain how we derive QAVB andattention as an alternative annealing method of optipresent the experimental results in latent Diri hlet almization problems by a pro ess that is analogous tolo ation (LDA). Se tion 6 on ludes this paper.
quantum u tuations (Apolloni et al., 1989; Kadowaki
and Nishimori, 1998; Santoro et al., 2002). QA is ex2 Preliminaries
pe ted to help states avoid being trapped by poor lo al
We assume that we have N data points, and they
optima at low temperatures.
are assigned to K latent lasses. The latent lass of
The main point of this paper is to explain the novel
the i-th data point is denoted by the latent variable zi .
DA algorithm for VB based on the QA (QAVB) we
zi = k indi ates that the latent lass of the i-th data
derived and present the e e ts of QAVB we obtained
point is k. The latent lass of the i-th data point isthrough experiments. QAVB is a generalization of VB
also denoted by K dimensional binary indi ator ve and SAVB attained by using a density matrix. We
tor ~i where if zi is equal to k, the k-th element ofdes ribe our motivation for deriving QAVB in terms
~i is equal to 1 and the other elements are all equalof a density matrix in Se tion 3. Here, we overview
to 0. The number of available lass assignment of all
the QAVB that we derived. Interestingly, althoughdata points is K N . The lass assignment of all data
QAVB is generalized and formulated by a density mapoints is denoted by K N dimensional binary indi ator
NN
trix, the algorithm for QAVB we nally derived does
~i whereis the Krone ker prodve tor  = N
i=1 
not need operations for a density matrix su h as eigenu t, whi h is a spe ial ase of a tensor produ t. If A
value de omposition and only has simple hanges fromis k-by-l matrix and B is an m-by-n matrix, then theCost function (energy)

Cost function (energy)

Cost function (energy)

State
Cost function (energy)

State

State

(a)

State

(b)

()

図 1: (a) S hemati

pi ture of SAVB. (Upper panel) At low temperature, the state often falls into lo al optima.
(Bottom panel) At high temperature, sin e the energy lands ape be omes at, the state an hange over a wide
range. (b) and ( ) S hemati pi ture of QAVB. (b) QAVB onne ts neighboring SAVBs. ( ) j an rea h 
owing to the intera tion f . It seems to go through energy barrier.
Krone ker produ t Atrix as follows: A

N

N

B0
is the km-by-ln blo1k maa11 B    a1l B

B .
.
B =B
 .

...

..
.

C
C.
A

For

ak1 B    akl B
example, if K = 2, N = 2, z1 = 1 (~1 = (1; 0)T ) andN
z2 = 2 (~2 = (0; 1)T ), then  = ~1 ~2 = (0; 1; 0; 0)T .
Let x = (x1 ;    ; xN ) denote the N observed data
points and  denote the model parameters. (l) indiates the l-th latent lass states of K N available latent lass states. For example, if K = 2 and N = 2,
then (1) = (1; 0; 0; 0)T , (2) = (0; 1; 0; 0)T , (3) =(0; 0; 1; 0)T and (4) = (0; 0; 0; 1)T . The set of available latent lass states is denoted by  = f(l) j(l =1; 2;    ; K N )g.
3

Motivation for QAVB in termsof Density matrix

For those unfamiliar with quantum information proessing, we will explain a density matrix whi h an beused as an extension of onventional probability. Ourde nition of a density matrix is based on (Warmuth,
2006).
A density matrix is a self-adjoint positive-semide nitematrix and its tra e is one. Conventional probability
whi h we alled lassi al statisti s an be expressed bya diagonal density matrix as follows. For example, let
us onsider the ase of two data points and two latent lasses as well as Se tion 2. We de ne four states,
denoted by indi ator ve tors f(i) g4i=1 , and probabil-

ity ve tor p = (p1 ; p2 ; p3 ; p4 )T , where pi indi ates theo urren e probability of the i-th state (i) .
Then, the density matrix of this system is given bydiag fp1; p2 ; p3 ; p4 g =

4
X
i=1

pi  (i)  (i)T ;(1)

where diagfg indi ates diagonal matrix. We an extend the on ept of probability by introdu ing nondiagonal elements in a density matrix whi h is alled
quantum statisti s. A state of a system in quantum
statisti s is de ned by a unit ( olumn) real ve tor1 , u,where dyad uuT has tra e one, Tr uuT = Tr uT u =1. A density matrix, , generalizes a nite probability
distribution and an be de ned as a mixture of dyads,
=Xipi ui uTi ;(2)

where pi is a mixture proportion ( oeÆ ient) that is
non-negative and sums to one. pi spe i es the proportion of the system in state ui . A density matrix assigns a probability to the unit ve tor or its asso iated
dyad given by p(u) = Tr uuT (= uT u). This isalled the \Born rule" in quantum me hanisms. A ording to Gleason's theorem, there is a one to one
orresponden e between generalized probability distributions and density matri es (Gleason, 1957).
p For example, when a state ve tor is u = 12 ; 0; 23 ; 0 , it
1 A state ve tor generally does not need to be a restri ted realve tor. If we onsider a omplex ve tor, the de nition of the
tra e of a dyad is repla ed by Tr (uu ) = Tr (u u) = 1, whereu indi ates omplex onjugate of u. However, for simpli ity,
we have restri ted the real ve tor in this paper.

represents the mixture of the rst state
and the third p 22
1
1state with probability 2 = 4 and 23 = 34 , respe tively.
A probabilisti model employs un ertainty to model
phenomena, and has demonstrated its pra ti ally inmany s ienti
elds. Although lassi al statisti s involves un ertainty over mixture proportions (fpi g), it
restri ts state ve tors to indi ator ve tors (f(i) g). In
ontrast, quantum statisti s involves un ertainty over
not only mixture proportions (fpi g) but also state ve tors (fui g) be ause if density matrix  has o -diagonal
elements, state ve tors fui g take arbitrary ve tors.
Therefore, a probabilisti model based on quantum
statisti s is a more generalized model in terms of un ertainty, and the generalization is expe ted to be more
useful. In the same way, sin e lassi al VB inferen e
in luding SA variants only involves un ertainty over
mixture proportions, this paper proposes a method of
maintaining un ertainty over state ve tors.
Finally, Fig 2 sums up the relationship between VB,
SAVB, and QAVB in terms of a density matrix. SAVB
and QAVB ontrol un ertainty of mixture proportions
via temperature T . However, QAVB an ontrol theun ertainty of state ve tors by introdu ing quantume e t parameter that is des ribed in Se tion 4, leading to enhan ed generalization.
Conventional Target field
fieldsin this paper

Uncertainty

Mixtureproportions

State
vectors

MethodVB (Attias, 1999)
SAVB (Katahira, 2008)
QAVB (This study)

図 2:

The un ertainty over mixture proportions has
been well studied in ma hine learning. VB and SAVB
also only involve un ertainty over mixture proportions.
We study the un ertainty over another omponent ofa density matrix, state ve tors. QAVB involves un ertainty over not only mixture proportions but also stateve tors.

4

Quantum Annealing for Variational Bayes Inferen eThis se tion explains how we derive update equations for QAVB. First, we de ne the lower bound of themarginal likelihood in QAVB as typi al VB. Then, weapply Suzuki-Trotter expansion (Trotter, 1959; Suzuki,1976) to the marginal of QA to analyti ally obtain update equations.

4.1 Introdu ing Quantum E e t
We de ne H with a K N by K N diagonal matrix asfollows:

H = diagf log p(x; (1) );    ;log p(x; (K ) )g(3)N

The onditional probability of indi ator state ve tor 
given x is al ulated byp(x;  )  T e H = T   = Tr  T ;=p( jx) =Hp(x)Tr (e )
(4)
H

where  = Tre(e H ) is a density matrix.
The marginal log-likelihood of N data points is formulated aslog p(x) = log Trfe H g:

(5)

Sin e the fully onditional posteriors are intra table,
VB inferen e is proposed as an approximated algorithm for estimating onditional posteriors.
The marginal log-likelihood of p(x) an be lower
bounded by introdu ing distribution over latent variables , parameters  and the approximate distribution q()q( ) of a posteriori distribution p(; jx) as
follows.
XZ
p(x; ;  )d (6)
log p(x) q ( )q ( ) log
q ( )q ( )=F~ [q(); q()℄:(7)
We maximize F~ [q(); q( )℄ with respe t to q()q()to obtain a better approximation of p(; jx) in VB
inferen e. F~ [q(); q()℄ is alled the variational freeenergy.
We derive QAVB by maximizing the lower bound of
the following marginal log-likelihood.
log p(x; ; ) = log Trfe Hg;(8)where is the quantum e e t parameter, is inverse
temperature, i.e., = T1 , and we de ne H with a K N
by K N matrix as follows:

H =H + Hq ;
Hq =

N
X
i=1

xi ;

 x = (E K

1
0
i 1
O
xi =  E K A
j =1

(9)

N
O

x

l=i+1

1K );

!

EK

;

(10)

where E K is the K by K identity matrix, 1K is the K
by K matrix whose elements are all one, and Hq is asymmetri al matrix. The above H is a standard settingfor QA (Kadowaki and Nishimori, 1998). The onditional probability of  given x, and is al ulatedbyT e Hp( jx; ; ) == T q  = Tr q T ;H
Tr (e )
(11)s(j ; j +1 ) =

N
X
i=1

Æ (~j;i ; ~j +1;i ); f ( ; ) = log(

1

a+b
);
b

(14)

); b = a(a K 1); (15)mKwhere Æ(~j;i ; ~j+1;i ) = 1 if ~j;i = ~j+1;i , and Æ(~j;i ; ~j+1;i ) =a = exp(

0 otherwise. We assume a periodi boundary ondition, i.e., ~m+1;i = ~1;i . m is alled Trotter number where the above tra e an be a urately evaluatedwithin the limit of m ! 1. N1 s(j ; j+1 ) indi ates asimilarity measure that takes [0,1℄ where N1 s(j ; j+1 ) =1 when j = j+1 and N1 s(j ; j+1 ) = 0 when j andj +1 are ompletely di erent.
In the following, we derive the lower bound of log p(x; ; ; m)by introdu ing the approximated distributions q(j )and q(j ) (j = 1;    ; m).

log p(x; ; ; m)  F [m; ℄ + Fq [m; ℄;(16)
F [m; ℄ =


H
m XZ
X
p(x; j ; j ) eff
where q = Tre(e H ) is a density matrix.
dj g;fq (j )q (j ) log
q (j )q ( j )Note that H be omes diagonal if is zero, in whi hj =1 jase it redu es to H , and quantum log-likelihood log p(x; ; )(17)
in Eq. (8) be omes lassi al loglikelihood log p(x) in
Fq [m; ℄ =Eq. (5) if is one.
m XX
X
The following se tion explains how we derived an
q (j )q (j +1 )(N log b + s(j ; j +1 )f ( ; ));j =1 j j+1
approximated posteriori distributions that maximized(18)
the lower bound of log p(x; ; ).

4.2 Derivation
Let j be one of all the available lass assignment
states of N data points, s.t. j 2 . The lass of
the i-th data point in j is denoted by ~j;i , s.t. j =NN
~j;i . It is intra table to evaluate log Trfe Hg
i=1 be ause H is not diagonal. However, we an approximately tra e e H by Suzuki-Trotter expansion as follows2 (Suzuki, 1976).
p(x; ; )  p(x; ; ; m) + O

 2

m

;

(12)

p(x; ; ; m) =
X
1

:::

m
XY
m j =1

e m log p(x;j ) bN es(j ;j+1 )f ( ; ) ; (13)2 For details, please refer to Appendix of full version at
http://www.r.dl.it .u-tokyo.a .jp/~sato/paper/IBIS2009.pdf

where e = m is alled the e e tive inverse temperature. If e = 1, F [m; ℄ is the sum of m lassi al variP~
ational free energy, i.e., F [m; = 1℄ = m
j =1 F [q (j ); q (j )℄.
Fq [m; ℄ be omes large as j and j +1 move approa h
ea h other. In pra ti e, the Trotter number m indiates the number of multiple SAVBs with di erent initializations. q(j ) and q(j ) are the approximations ofposterior distributions in the j -th SAVB where index
j = 1;    ; m is randomly labeled. f ( ; ) indi ates theintera tion between the j -th and the j + 1-th SAVB.
One problem rops up here. The lass labels are
not always onsistent between the j -th and the j + 1th SAVB, i.e., lass label k in the j -th SAVB does
not always orrespond to lass label k in the j + 1th SAVB be ause the initialization of SAVBs is not
the same. For example, assume that (zj;1 ; zj;2 ; zj;3) =(1; 1; 2) and (zj+1;1 ; zj+1;2 ; zj+1;3 ) = (2; 2; 1) where zj;idenotes the latent lass label of the i-th data point in
the j -th SAVB. In this situation, it an be said that

lass label 1 in the j -th SAVB does not orrespond to
ity O(K 3 ), we use the following approximation algolass label 1 but lass label 2 in the j + 1-th SAVB.
rithm whose omputational omplexity is O(K 2 )Let us introdu e the proje tion j in lass labels toNXabsorb the di eren e of lass labels between the j -th(22)
q (j;i;k )q (j +1;i;k0 );j (k ) = argmax
0 i=1
k
0
and the j + 1-th SAVB. k = j (k) indi ates that k inNX
the j -th SAVB orresponds to k0 in the j +1-th SAVB.
q (j;i;k )q (j 1;i;k0 ):(23)
j 11 (k ) = argmax
PK
In this way, we have Æ(~j;i ; ~j+1;i ) = k=1 j;i;k j+1;i;j (k)k0i=1where ~j;i = (j;i;1 ;    ; j;i;K ), i.e., j;i;k takes 1 if
The j above means that k in the j -th SAVB orrezj;i = k , and otherwise 0. q (j;i;k ) denotes q (zj;i = k ).
sponds to k0 in the j + 1-th SAVB that has the highWe have
est orrelation between (q(j;1;k );    ; q(j;N;k )) and(q(j+1;1;k0 );    ; q(j+1;N;k0 )).
Fq [m; ℄ =mN log b + f ( ; )

m X
N X
K
X
j =1 i=1 k=1

q (j;i;k )q (j +1;i;(k) ):(19)

Therefore, we obtain the following updates by taking
the fun tional derivatives of F [m; ℄ + Fq [m; ℄ withrespe t to q(j;i;k ) and q(j ) , and equating them tozero
q (j;i;k ) / expf

Zq (j ) e log p(x; j ; j )d j+f ( ; )(q(j 1;i;j 11 (k) ) + q(j+1;i;j (k) ))g
(20)
X

5

Experiments

We applied SAVB and QAVB to latent Diri hlet alloation (LDA) (Blei et al., 2003). We used the Reuters
orpus3 and the Medline orpus4.We randomly hose
1,000 do uments from the Reuters orpus that had avo abulary of 12,788 items. We randomly hose 1,000
do uments from the Medline orpus that had a vo abulary of14,252 items. We set the number of topi s of
LDA to 20.

5.1 Annealing s hedule

The annealing s hedule of temperature T (in pra ti e, inverse temperature = T1 ) and quantum e e tjparameter exert a substantial in uen e of SAVB and
(21)
QAVB
pro esses. Although a erti ed s hedule forwhere  1 is the inverse proje tion of . q(j;i;k ) intemperature is well known in Monte Carlo simulations
di ates the probability that the latent lass of the i-th
(Geman and Geman, 1984), we have not yet obtained
data point will be k in the j -th SAVB. As lari ed
any mathemati ally rigorous arguments for T andby Eq. (20), q(j;i;k ) approa hes q(j 1;i;j 11 (k) ) andin SAVB and QAVB. Sin e intera tion f is a fun tionq (j +1;i;j (k) ) as f ( ; ) In reases. Therefore, f ( ; )of and , we have to onsider the s hedule of f inworks as the intera tion explained by Fig 1(b).
pra ti e.
In this paper, we use the annealing s hedule =4.3 Estimates of Class-Label Proje tiontt
0 r and e = e 0 r eff that Katahira et al. (2008)
used. t denotes the t-th iteration.
We estimate the lass label proje tion, , be ause
We also use the following annealing s hedule =su h proje tions represent impli it information. We
10 pt Kadowaki and Nishimori (1998) used. We tried
estimate  by maximizing F [m; ℄ + Fq [m; ℄．To be
the s hedules of with ombinations of 0 =0:2, 0:4,
more pre ise, we extra t the pairs (k; j (k))(j = 1;    ; m) 0:6 and 0:8, and r =1:05, 1:1 and 1:2 in SAVB. As
m X
N X
K
X
a results, we observed 0 = 0:6 and r = 1:05 rethat maximizeq (j;i;k )q (j +1;i;j (k) ) in Eq.
j =1 i=1 k=1
ated an e e tive s hedule in SAVB for LDA. The too(19). This is alled the \assignment problem", whi h
low inverse temperature did not work well in LDA.
is one of the fundamental ombinatorial optimization
3 http://www.daviddlewis. om/resour es/
problems. Even though the Hungarian algorithm solves
test olle tions/reuters21578/
4 http://www.nlm.nih.gov/pubs/fa tsheets/medline.html
the assignment problem with omputational omplexq ( j ) /p( j ) eff expf

q (j ) e log p(x; j ; j )g;This observation was similar to SAVB for the hidden
Markov model (Katahira et al., 2008). Therefore, we
set 0 = e 0 = 0:6 and r = r eff = 1:05 in SAVB and
QAVB. We varied 0 and have shown the s hedule ofand f in Fig.3.

5.2 Experimental results
We ran QAVB ve times in all experiments with aTrotter number, m, of 10. The results from this experiment were the average of the minimum negative variational free energy, minj f F~ [q(j ); q(j )℄g, of ea h run.
SAVB was randomly restarted until it onsumed thesame amount of time as QAVB. We ran ve bat hesof SAVB, and ea h bat h onsisted of 20 repetitionsof SAVB. The results from this experiment were theaverage of the minimum variational free energy of all
bat hes. These experimental onditions for QAVB and
SAVB enabled a fair omparison of these two experiments in terms of the exe ution time. In fa t, theaveraged exe ution times for QAVB (m = 10) and 20
SAVBs orresponds to 20.5 and 22.3 h for Reuters, and20.4 and 22.9 h for Medline. We set the number of iterations to 300 in SAVB and QAVB for LDA.
Fig.4 plots the averages for the minimum negative
variational free energy with the mean squared error for
Reuters and Medline. In both orpora, ea h of whi hhas di erent properties, QAVB outperforms SAVB forea h 0 be ause the introdu tion of a novel un ertainty into a model, in this ase LDA, works well.
QAVB approa hes SAVB as 0 in reases be ause intera tion f remains 0 in the limited number of iterations. Moreover, we observed QAVB worked well ifintera tion f > 0 after SAVBs nd sub-optimal states.
We think fast s hedules, i.e. small 0 , did not perform
well be ause the term with intera tion f in Eq. (20)is noisy when q() is not estimated a urately in thesmall number of iterations.
6

Con lusion

We proposed quantum annealing for variational Bayes
inferen e (QAVB). QAVB is a generalization of theonventional variational Bayes (VB) inferen e and simulated annealing based VB (SAVB) inferen e obtainedby using a density matrix that generalizes a nite probability distribution. QAVB is as easy as SAVB to implement be ause QAVB only has to add intera tion

図 3: S hedules for inverse temperaturetion f .

図 4:

and intera -Comparison of QAVB and SAVB in Reuters(Top) and Medline (Bottom). The horizontal axis is
0 . The verti al axis is the average for the minimum
energy where the low energy is preferable.
f to multiple SAVBs, and only one parameter, 0 ,is added in pra ti e. The omputational omplexity
of QAVB is larger than that of SAVB be ause QAVB
looks like m parallel SAVBs with intera tions. However, we empiri ally demonstrated that QAVB works
better than SAVB whi h is randomly restarted until
it uses the same amount of time as QAVB in latent
Diri hlet allo ation (LDA). A tually, it is typi al to
run SAVB many times be ause SAVB does not ne essarily nd a global optimum and is trapped by poor
lo al optima at low temperature. In pra ti e, the bottlene k in QAVB is the omputational omplexity ofthe proje tion of lass labels in Se tion 4.3, whi h is asear h problem for one nearest neighbor. An improvement in this algorithm to proje t lass labels would
lead to more e e tive QAVB.
Finally, let us des ribe future work. We intend to investigate an e e tive proje tion algorithm, other onstru tions of quantum e e t Hq , and a suitable s hedule of a quantum eld for . We also plan to apply
QAVB to the hidden Markov model.

Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse Ising model. Physi al Review
E, 58:5355{5363, 1998.

A knowledgements

Giuseppe E. Santoro, Roman Martonak, Erio Tosatti, andRoberto Car. Theory of Quantum Annealing of an Ising
Spin Glass. S ien e, 295(5564):2427{2430, 2002.

This resear h was funded in part by a MEXT Grant-inAid for S ienti Resear h on Priority Areas \i-explosion"in Japan. This work was partially supported by Resear hon Priority Areas \Physi s of new quantum phases in super lean materials" (Grant No. 17071011) from MEXT,
and also by the Next Generation Super Computer Proje t,
Nanos ien e Program from MEXT. The authors also thankthe Super omputer Center, Institute for Solid State Physi s,
University of Tokyo for the use of the fa ilities. S.T. ispartly supported by Grant-in-Aid for Young S ientists Startup (No.21840021) from the JSPS.

参考文献
B. Apolloni, C. Carvalho, and D. de Fal o. Quantum
Sto hasti Optimization. Sto hasti Pro esses and their
Appli ations, 33:233{244, 1989.
Hagai Attias. Inferring Parameters and Stru ture of Latent
Variable Models by Variational Bayes. In Kathryn B.
Laskey and Henri Prade, editors, Pro eedings of the
15th Conferen e on Un ertainty in Arti ial Intelligen e(UAI-99), pages 21{30, 1999.
D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent Diri hlet
Allo ation. Journal of Ma hine Learning Resear h, 3:993{1022, 2003.
Koby Crammer and Amir Globerson. Dis riminative
Learning via Semide nite Probabilisti Models. In
Pro eedings of the 22nd Annual Conferen e on Unertainty in Arti ial Intelligen e, Arlington, Virginia,
2006. AUAI Press.
Stuart Geman and Donald Geman. Sto hasti relaxation,
Gibbs distributions, and the Bayesian restoration of images. IEEE Pattern Analysis and Ma hine Intelligen e,,
6:721{741, 1984.
A. M. Gleason. Measures on the losed subspa es of a
Hilbert spa e. Journal of Mathemati s and Me hani s,
6:885{893, 1957.
Carl W. Helstrom. Quantum dete tion and estimation theory. Journal of Statisti al Physi s, 1(2):231{252, 1969.

Kentaro Katahira, Kazuho Watanabe, and Masato Okada.
Deterministi annealing variant of variational Bayes
method. Journal of Physi s: Conferen e Series, (95):012015 (9pages), 2008.
S. Kirkpatri k, C. D. Gelatt, and M. P. Ve hi. Optimization by Simulated Annealing. S ien e, 220(4598):671{
680, 1983.

Ruediger S ha k, Todd A. Brun, and Carlton M. Caves.
Quantum Bayes rule. Physi al Review A, 64:014305(4pages), 2001.
Masuo Suzuki. Relationship between d-Dimensional Quantal Spin Systems and (d+1)-Dimensional Ising Systems{ Equivalen e , Criti al Exponents and Systemati Approximants of the Partition Fun tion and Spin Correlations {. Progress of Theoreti al Physi s, 56(5):1454{
1469, 1976.
Kazuyuki Tanaka and Tsuyoshi Horigu hi. Probabilisti ,Iterated and Quantum-Iterated Computational Methods
in Gray-Level Image Restoration. Interdis iplinary Information S ien es, 8(1):33{50, 2002.
H. F. Trotter. On the Produ t of Semi-Groups of Operators. Pro eedings of the Ameri an Mathemati al So iety,10(4):545{551, 1959.
Naonori Ueda and Ryohei Nakano. Deterministi Annealing Variant of the EM Algorithm. In NIPS7, pages 545{
552, 1995.
Manfred Warmuth. A Bayes Rule for Density Matri es. In
Y. Weiss, B. S holkopf, and J. Platt, editors, Advan es in
Neural Information Pro essing Systems 18, pages 1457{
1464. MIT Press, Cambridge, MA, 2005.
Manfred K. Warmuth. A Bayesian Probability Cal ulus
for Density Matri es. In Pro eedings of the 22nd Annual Conferen e on Un ertainty in Arti ial Intelligen e,
2006.
Lior Wolf. Learning using the Born Rule. Te hni al report,
2006.