情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences 2009 (IBIS2009)

代理ベイズ学習と隠れマルコフモデルへの応用

Vicarious Bayes Learning and its Application to HMMs
山崎 啓介∗
Keisuke Yamazaki
Abstract: Hierarchical parametric models, such as Gaussian mixture models, Bayesian
networks, and hidden Markov models, are widely used in the information engineering ﬁelds.
These models are generally expressed as probability functions of the given data space, andthere are a number of learning algorithms for each model. However, it is still unknown
whether the space is suitable and eﬀective for learning of the function. Therefore, thepresent paper considers a feature map to a diﬀerent domain space, and investigates how
the map changes the generalization error. Then, we proposed the vicarious learning in
the Bayes estimation, which preserves the error value of the original space in a diﬀerent
space. This new learning framework reduces the computational learning and evaluation
costs because a simpler space makes the calculation of the likelihood faster. As one of its
applications, we can derive a necessary length of training data for HMMs.
Keywords: Bayes Learning, Feature Selection, Generalization Error

1

Introduction

Hierarchical parametric models, such as Gaussian mixture models, Bayesian networks and hidden
Markov models, are used in a number of practical engineering ﬁelds. The parameter space of such models
can have singularities due to the hierarchical structureor the latent variables. Then, these models are referred
to as singular. Models are regular when the parameter
space does not include any singularity.
The conventional statistical analysis is establishedon the basis of unique probabilities of the regularmodel. The analysis is not available for singular models. More statistically, the inverse of the Fisher information matrix is required to describe the convergenceof the optimal parameter. The matrices are not positive deﬁnite on the singularities, which means that theinverse matrices do not exist. Therefore, the algebraic
geometrical method has been developed to reveal theBayesian generalization error of singular models [6].
Based on the method, the errors of the hierarchical∗ 東京工業大学 精密工学研究所, 〒 226-8503 横浜市緑区長津田4259 R2-5, e-mail k-yam@pi.titech.ac.jp,
Tokyo Institute of Technology, R2-5, 4259 Nagatuta, Midori-ku
Yokohama

models are revealed (e.g. [8, 7]).
The present paper focuses on a relation between thedata space and the generalization error. To project
the given data to a diﬀerent space is a common technique in feature extraction and dimensionality reduction. Models dealing with sequential data have large
computational cost for learning and evaluation eventhough they have eﬀective algorithms [4, 3, 2]. A feature map actually seems to reduce the cost because themodels can be simpliﬁed in the feature space. However,eﬀect of the map on the error has not been studied yet.
The feature space has to be designed properly. Let
us consider the following simple example: Discrete
data x are assumed to be D dimensional binary vectors. Then, the dimension of the data space is 2D .
The most naive modeling is to provide parameters asprobability variables of each x. In this case, 2D − 1variables are required to represent all x. For example, three variables p1 , p2 , p3 are suﬃcient for D = 2,
i.e. P (00) = p1 , P (01) = p2 , P (10) = p3 . Note thatP (11) = 1 − p1 − p2 − p3 . A parametric model p(x|w),
where w is the parameter, generally has to have lessnumber of parameters than 2D −1. Now, a feature map
projects the data to 2d dimensional space. The featurespace is assumed to be much smaller than the original
one, d ¿ D. It is easy to prove that the parameter

ples. The predictive distribution is constructed byp(x|w). For example, the maximum likelihood method

w cannot be correctly identiﬁed when 2d − 1 < dim w.
Thus, a theoretical evaluation of a feature map is required to clarify if the feature space is suitable for the

gives

parameter learning.
Based on the algebraic geometrical method, thewhere ŵ is the maximum likelihood estimator:

p(x|X n ) = p(x|ŵ)ŵ = arg max L(w, X n ),nally used in the original space. Our task is to design
the optimal model available not for the feature space,but for the original one. Then, the feature space preserving the generalization error is desired because theparameters can be completely estimated. The present
paper deﬁnes training and test procedures in such feature space as the vicarious Bayes learning, and thefeature map as the vicarious feature map. As for thedemonstration, the vicarious feature map will be foundfor hidden Markov models, and a necessary length ofdata sequences is derived for the complete learning.
The remainder of the paper is organized as follows.
Section 2 formalizes the Bayes learning and summarizes important results of the algebraic geometricalmethod. Section 3 proposes the vicarious Bayes learning. Section 4 shows an application to hidden Markov
models (HMMs). Sections 5 and 6 present discussions
and our conclusion, respectively.

2

The Bayes Learning and
the Algebraic Geometrical
MethodLet us formally deﬁne the generalization error. A setof training data X n = {X1 , . . . , Xn } is independently
and identically distributed from the true model q(x).
The learning model with its parameter w is generativeand is represented as p(x|w). The generalization error
is the average Kullback divergence from q(x) to thepredictive distribution p(x|X n ),
]
[∫
q(x)
dx ,
(1)
G(n) = EX nq(x) lnp(x|X n )where n is the number of the training data and EX n [·]represents the expectation value over all training sam-(3)

w

present paper proposes an evaluation method the feature map. The main purpose is to design the modelp(x|w) through the feature space. Therefore, one of
the expected applications is the model selection withthe cross-validation [5]. The selected model will be ﬁ-(2)

L(w, X n ) =n∏p(Xi |w).

(4)

i=1

The Bayes estimation yields the predictive distribution∫
p(x|X n ) = p(x|w)p(w|X n )dw,
(5)
where the posterior p(w|X n ) is deﬁned byp(w|X n ) =1
L(w, X n )ϕ(w)Z(X n )

(6)

using a prior ϕ(w) and the normalization factorZ(X n ).
The asymptotic form of Eq.(1) is expressed as
( 1 )
λ m−1
G(n) = −+onn ln nn ln n(7)

when Wt ≡ {w : p(x|w) = q(x)} 6= ∅, i.e. p(x|w) can
attain q(x) [6]. The coeﬃcients are deﬁned as follows:
All poles of the zeta function∫
J(z) = H(w)z ϕ(w)dw(8)
are real negative and rational, where the Kullback divergence∫
H(w) =

q(x) lnq(x)dxp(x|w)(9)is analytic. Then, z = −λ is the largest pole and m is
its order.
Eqs (7)-(9) shows that the generalization error is determined by the relation between q(x) and p(x|w). Behavior of H(w) in the neighborhood of Wt directly af∫
fects λ and m. For example, J(z) = w2jz dw (j =1, 2, . . .) when H(w) = w2j and ϕ(w) is closed to uniform around Wt = {0}. It is easily found that J(z)has a factor 1/(2jz + 1) by integrating over w, which
implies λ = 1/2j.

3

Proposedwork

Learning

Frame-In this section, we propose the vicarious Bayes learning.

3.1

Mapping to a Feature Space

generalization error over a feature space are referred
to as the vicarious Bayes learning when G(n) andAs can be noticed in Eqs (7)-(9), the error G(n) depends on the probabilities p(x|w) and q(x). Herein, weGΦ (n) have the common asymptotic form.

consider the error value over a diﬀerent domain space.
Let Φ : x 7→ y be a feature map. Based on the map,

In the present paper, we refer to this preserving map as
the vicarious feature map. Herein we are not interested

the models on y are deﬁned by∫qΦ (y) = q(x)δ(y − Φ(x))dx,∫pΦ (y|w) = p(x|w)δ(y − Φ(x))dx,

in the case G(n) > GΦ (n) because our purpose is toinvestigate model properties on the given space x. The

(10)
(11)

where δ(·) is the Dirac’s delta function. The likelihood
function Eq (4) is given byLΦ (w, Y n ) =n∏pΦ (Yi |w),

smaller error implies that not all parameters have tobe estimated in the feature space, which means thatthe proper form of p(x|w) cannot be obtained.

3.3

A Theory of the Feature Map on
the Error(12)

A novelty of the proposed learning is to restrict thefeature map Φ to the vicarious one in the asymptotic

where Y n = {Y1 , . . . , Yn } = {Φ(X1 ), . . . , Φ(Xn )}.
The Bayes estimation yields the posterior pΦ (w|Y n )manner. Therefore, we study a condition, under whichΦ becomes vicarious.

and the predictive distribution pΦ (y|Y n ) by replacingp(x|w) of Eqs (5) and (6) with pΦ (y|w). Then, theThe coeﬃcients of the asymptotic error is determined by behavior of the Kullback divergence H(w)or HΦ (w) in the neighborhood of Wt . The divergence

i=1

generalization error deﬁned as[∫GΦ (n) = EY nqΦ (y) ln]qΦ (y)dy,pΦ (y|Y n )(13)

has the asymptotic form, whose coeﬃcients are determined by the zeta function of∫qΦ (y)
HΦ (w) = qΦ (y) lndy.
(14)pΦ (y|w)∫∑∑
and/or y should be substituted for dx and/or∫ x
dy in the discrete space, respectively.

3.2

Vicarious Bayes Learning

Comparing Eq (13) with Eq (1), let us determine
how the data space aﬀects the parameter learning.
It is known that the generalization error implicitly
expresses the tuning cost of all essential parameters.
For example, the regular model has the coeﬃcients
λ = dim w/2 and m = 1. In singular models, λ also
depends on the number of parameters to be tuned[6, 8]. The learning process is preserved if a featuremap Φ does not change the error. Observing the error
change, we can theoretically investigate which factor ofthe data space is necessary for the parameter learning.
We propose the following learning framework:
Deﬁnition 1 (Vicarious Bayes Learning) The
Bayesian parameter learning and its evaluation of theis expressed as a polynomial form of w because it isanalytic. Based on the Noetherian property of polynomial ring, the divergence consists of bases. For example, if polynomials f1 (w) and f2 (w) are bases, the nonnegative function H(w) can have the following form,
H(w) = f1 (w)2 + f2 (w)2 + f3 (w),(15)

where f3 is a sum of squared polynomials with respect
to f1 and f2 , and is higher order than f12 and f22 . Moreprecisely, f3 consists of terms, such as (f1 f2 )2 , (f1 +f22 )2 and (f12 +f2 )2 , with coeﬃcients. It naturally holds
that f1 (w) = f2 (w) = 0 on Wt . The error GΦ (n) will
have the same asymptotic form if HΦ (w) is given byHΦ (w) = f1 (w)2 + f2 (w)2 + f4 (w),(16)

where f4 consists of the same terms as f3 with diﬀerent coeﬃcients. Based on this example, we derive a
condition:
Theorem 1 A feature map Φ becomes vicarious if
H(w) and HΦ (w) have the same essential terms for
λ and m.
This theorem is easily proved according to the relationof Eqs (7)-(9). Note that Theorem 1 shows a suﬃcientcondition: The largest poles in the zeta functions of

H(w) and HΦ (w) can be at the same position even if
the essential parts are diﬀerent from each other.

initial state is always the ﬁrst one in both models.
The parameter w includes the transition probability

A general feature map provides insight of the generalization error even when it is not straightforward toﬁnd the vicarious one.

aij , indicating the probability of transition from theith state to the jth state, and the output probability
bim , indicating the probability of generating alphabet

Theorem 2 For a feature map Φ, it holds that
G(n) ≥ GΦ (n).

(17)

The proof is in Appendix.
Theorem 2 intuitively shows that the learning in afeature space is more accurate than in the original
space because the domain space y is generally simpliﬁed based on the deﬁnition of pΦ (y|w). For example,
let us divide elements of vector x into two sets x1 andx2 , i.e. x = (x1 , x2 ), and deﬁne two feature maps as
πi : (x1 , x2 ) 7→ xi for i = 1, 2. The map πi selects
the attribute xi . The original model p(x|w) is a joint
probability of x1 and x2 . According to the deﬁnition,pπi (xi |w) is a marginal probability of xi . Then, G(n)measures the error over x1 and x2 whereas Gπi (n) is
about only xi . This derives that Gπi (n) should besmaller than G(n). Theorem 2 claims this fact mathematically.
A vicarious feature map puriﬁes the domain spacewhen the dimension of the feature space is less thanthe original one. If π1 is a vicarious feature map, theattributes in x1 are essential for the parameter learningand x2 is nuisance dimension. Considering the map
πi , we can regard the vicarious learning as a feature
selection in a Bayes scenario.

4

An Application to HMMs

In this section, we apply the vicarious Bayes learning
to HMMs. We show that a restriction map of a data
length can be a vicarious feature map, which derives anecessary length for the parameter learning.

4.1

Model Setting

m at the ith hidden state. These probabilities satisfy∑K+1
the conditions, aii = 1 − i6=j aij for ∀aij ≥ 0 and∑M
biM +1 = 1 − m=1 bim for ∀bim ≥ 0.

4.2

Restriction Maps on the Length

We consider the following map of the data space,ΦL : {1, . . . , M + 1}L0 → {1, . . . , M + 1}L(18)

for L ≤ L0 , which cuts oﬀ the data sequences to change
the length into L. For example, Φ3 (8145924518) = 484
when L0 = 10, L = 3 and M = 8. In the similar way
to πi , pΦ3 (814|w) is the marginal probability over joint
probabilities p(814 ∗ ∗ ∗ ∗ ∗ ∗ ∗ |w), where ‘∗’ means any
number from {1, . . . , 9}.

4.3

Necessary Length for the Vicarious
Bayes Learning

Using the restriction map, we consider a necessary
length for the parameter learning.
It can be conjectured that L = 3 is suﬃcient for thelearning according to the following reason: The process
to generate data with L = 3 includes two transitions.
All transition parameters aij are used for two transitions in the complete graph. All output parameters
bim are used for generating data at all hidden states.
Therefore, the information of all parameters w can beextracted from the output sequences when inﬁnitely
large number of sequences are given as training data.
We hereinafter prove that L = 3 is not enough evenwhen n → ∞ and derive a necessary length.
Lemma 1 The Kullback divergence HΦL (w) is expressed as a sum of squared terms, which follows therules:The present paper focuses on the ergodic HMMs,

1. The squared terms monotonically increase withgrowth of the data length.
More precisely,in which the transition connections among the hidden states construct a complete graph. The numberof output alphabets and the length of data are M + 1

HΦL2 (w) includes all the terms of HΦL1 (w) forL1 ≤ L2.

and L0 , respectively, i.e. x ∈ {1, . . . , M + 1}L0 . The
numbers of the hidden states are K + 1 and K0 + 1
in the learning and true models. For simplicity, the2. The signiﬁcant number of the squared terms
N ST (L, M ) can be expressed as
N ST (L, M ) = (M + 1)L−1 + M − 1.

(19)

The proof is in Appendix.

that L = 3, M = 1 and K = 1.
N ST (1, 3) = (1 + 1)2 + 1 − 1 = 4

Theorem 3 For suﬃciently large L0 , vicarious feature maps exist in the series of ΦL .

< dim w = (1 + 1)(2 + 1) = 6,

(24)

Proof: Based on Lemma 1, N ST (L, M ) monotoni-

which does not satisfy the condition of Lm . The nec-

cally increases and all squared terms in HΦL1 (w) are included by those in HΦL2 (w) for L1 < L2. We consider

essary length is derived as

the series of the squared terms of H(w) = HΦL0 (w).
Let SL be a set of the squared terms f (w)2 deﬁned by
SL = {f (w) : f (w) ∈ HΦL (w), f (w) 6∈ HΦL−1 (w)},
(20)
2

2

2

where S0 = ∅. The order of the series is given by

Lm = arg minL {(1 + 1)L−1 + 1 − 1 ≥ 6} = 4.

(25)

Note that this length could not be suﬃcient, i.e. the vicarious Bayes learning requires longer sequences. Let
us assume that HΦL (w) consists of the square terms
f1 (w)2 , f2 (w)2 and f3 (w)2 , and that dim w = 3.

(21)

If f3 (w) is a polynomial with respect to f1 and f2 ,
f1 (w) = f2 (w) = 0 automatically satisﬁes f3 (w) = 0.
Then the actual number of the equations to identify

The Noetherian property on H(w) shows that there isa constant Le < L0 , which is the number of the essen-

w decreases to two, which is less than dim w. In suchcase, L should be larger to obtain more squared terms

tial squared terms for HΦL (w) = 0, since L0 is suﬃciently large for the parameter learning. More mathematically, Le is the minimum number, such that SLein HΦL (w).

S1 , S2 , . . . , SL , . . . SL0 .

4.4

Experimental Validation of the
Minimum Length

includes all generating elements for H(w) = 0 in termsof the ideal theory on polynomial ring. Then ΦL for

As seen in the previous part, Lm is a necessary

Le ≤ L < L0 is vicarious. (End of Proof )Let dim w be the dimension of the parameter in thelearning model. In the present HMMs,

length, which implies that longer sequences are required for the vicarious Bayes learning. In this part,
we experimentally verify the minimum (necessary anddim w = (K + 1)(K + M ).

(22)

suﬃcient) length.
We suppose that (K, M ) = (2, 2) and investigate theComparing Eq (22) with Eq (19), the following theorem indicates a necessary length:

generalization error when L = 1, . . . , 10. The original
length is L0 = 10. The dimension of parameters is
dim w = 12 and the number of the squared terms is

Theorem 4 A necessary length Lm for the vicarious
Bayes learning of HMMs are represented by

N ST (L, 2) = 3L−1 +1. According to Theorem 4, Lm =4. The number of training data sequences is n = 500.

Proof: The maximum number of the parameters to

We used the MCMC method to construct the posteriorpΦL (w|Y n ) [1]. The number of parameters to construct
the predictive model pΦL (y|Y n ) is Nw = 500, i.e.

be tuned is dim w. According to Eqs (7)-(9), we focus
on the case pΦL (y|w) = qΦL (y), i.e., HΦL (w) = 0. In
the case, the squared terms are all zero, where each500
1 ∑pΦL (y|Y ) 'pΦ (y|wi ),Nw i=1 L

Lm = arg minL {N ST (M, L) ≥ dim w}.

(23)

term is a polynomial of w. To identify all elements ofw, the number of the polynomials N ST (M, L) should
not be less than dim w based on the relation between
the number of variables and that of equations. (Endof Proof )Theorem 4 shows that L = 3 can not attain thevicarious Bayes learning. For example, let us assume

n

(26)

where wi is taken from the posterior. In the evaluation,
the number of the test data sequences is N = 5000 andthe average EY n [·] is taken by 100 training sets.
Figure 1 shows the results. The horizontal axis indicates the lengths L of training and test data. The
vertical one does the generalization error. There arethree curves for the true model sizes K0 = 0, 1, 2. It isrespectively. This procedure is then repeated after reversing the roles of the sets, and the generalization er-

Generalization error

0.012
0.01

ror is estimated. This validation method is commonlyused for selecting the optimal size of a model, so called
the model selection problem. To change the domain(dim w)/(2n)
K_0=0
K_0=1
K_0=2

0.008

space by the vicarious feature map ΦL for L ≥ Lm
is a powerful method for the model selection because

0.006both the training and testing sessions are enormously
repeated in the cross-validation and GΦL (n) has thesame value as G(n) in any size.

0.004
0.002

1

2

3

4
5
6
7
Training data length

図 1: The generalization error w.r.t.

8

9

10

6
the sequencelength.
derived that
G(n) =

(1)
dim w
+O 2
2n
n

(27)

when K = K0 [6]. The horizontal line described as’(dim w)/(2n)’ is the theoretical asymptotic value ofthe error, dim w/(2n) = 12/(2 × 500) = 0.012. The
error on K0 = 2 has to reach the line for G(n) =GΦL (n). As can be seen in the graph, the curve of
K0 = 2 has a gap between L = 3 and L = 4, andalmost reaches the horizontal line at L = 4, which
implies that Lm = 4 will be the minimum length ofthe vicarious learning.

5

Discussions

The vicarious learning on HMMs reduces the computational cost in both training and test sessions.
It is known that the time complexity of p(x|w) isO((K + 1)2 L) in HMMs. Then, the complexity of thelikelihood L(w, X n ) is O(n(K + 1)2 L0 ) for a given w,
which shows the cost O(n(K + 1)2 L) of LΦL (w, Y n )is much less than that of L(w, X n ) when a number ofdata exist. The MCMC method requires the calculantion of L(w, X ) in each update of the parameter for
training. The computation of p(x|w) is frequently used
for the generalization error in the test session. Therefore, to shorten the length of the data sequences saves
a number of computational complexity.
The reduction of the computational cost is also effective for cross-validation [5]. In the validation, thegiven data is divided into training data and validation
data. These data sets are used for training and testing

Conclusion

We proposed the vicarious Bayes learning. It is regarded as a feature selection preserving the Bayes generalization error in an asymptotic manner. We also
demonstrated its availability in HMMs. The length restriction is a theoretically guaranteed feature selection
on the basis of the vicarious learning framework.

Acknowledgement
This research was partially supported by the Ministry of Education, Science, Sports and Culture in
Japan, Grant-in-Aid for Scientiﬁc Research 18079007.

Appendix
Proof of Theorem 2First, let us state the following lemmas without their
proofs:Lemma 2 Let λ1 , m1 and λ2 , m2 be the largest poles
and the orders in the zeta functions of H1 (w) andH2 (w), respectively. Then, the following relation holds
if H1 (w) ≤ H2 (w) for all w [8],λ1m1 − 1λ2m2 − 1−≤−.
nn ln nnn ln n(28)

Lemma 3 (Continuous Log-Sum Inequality)∫∫q(x,y)For
q(x, y)p(y) ln p(x,y)
dxdy < ∞,∫ ∫q(x, y)q(x, y)p(y) ln
dxdyp(x, y)∫ (∫) ∫ q(x, y)p(y)dy≥q(x, y)p(y)dy ln ∫dx,p(x, y)p(y)dy(29)

where p(y), q(x, y), p(x, y) are all probability density
functions.

Eq (9) is rewritten as∫
H(w) = Hy (w)dy,∫q(x)Hy (w) = q(x)δ(y − Φ(x)) lndx.
p(x|w)

Using biM +1 = 1 −
(30)

{∑

∑M

m=1 bim ,

path

(31)

b∗1 a∗ b∗ a∗ b∗·M +1

}2

path

M
{∑
∑
=
b1 aba(1 −b·m )Based on Lemma 3,

m=1

path

H(w) ≥ HΦ (w).

∑b1 abab·M +1 −

(32)

−

∑

b∗1 a∗ b∗ a∗ (1 −b∗·m )

}2
.

(40)

m=1

path

Lemma 2 indicates that

M∑

Note that the right-hand side of Eq (39) includes terms

G(n) ≥ GΦ (n),

(33)

{∑

which proves the theorem. (End of Proof )∑b1 abab·m −pathb∗1 a∗ b∗ a∗ b∗·m

}2
(41)

path

for 1 ≤ m ≤ M . For any constant c, it holds that

Proof of Lemma 1
First, we focus on L = 3, then generalize the result.
We use the following notation:h1 (w)2 + {ch1 (w) + h2 (w)}2 ≷ h1 (w)2 + h2 (w)2 .

H(w) ≷ K(w),Combining Eq (42) and the presence of the terms in(34)

where there are positive constants C1 , C2 such that
C1 K(w) ≤ H(w) ≤ C2 (w)(42)

Eq (41), the term in Eq (40) is rewritten as
{∑

(35)

b1 abab·M +1 −path

in the neighborhood of H(w) = 0. The true model has
the true parameter w∗ = {{a∗ij }, {b∗im }} for 1 ≤ i, j ≤K0 + 1 and 1 ≤ m ≤ M + 1. It is known that thelargest poles in the zeta functions of H(w) and K(w)are the same [8]. It holds that∑HΦ3 (w) ≷{pΦ3 (y|w) − qΦ3 (y)}2(36)
because y is discrete [7]. To simplify the descriptions,
we use the notation,∑∑
b1 abab=∑∑which represents that

alph

path

is themarginalization over all generation of alphabets andall paths of transitions among the hidden states. For
the true parameters {{a∗ij }, {b∗im }},
∑
∑
≡

+

b1 abab·m −l,m∈{1,...,K0

.

(38)

Based on

∑K+1i=1

a·i = 1,alph pathpath∑b∗1 a∗ b∗ a∗ b∗·m

}2
.

(43)

∑

path b1 aba =∑path b1 ab.

Then the term in Eq (43) is rewritten as{∑

b1 aba −∑b∗1 a∗ b∗ a∗

}2

path

{∑
}2
∑
=
b1 ab −b∗1 a∗ b∗ .
path

(44)

path

Applying this procedure to biM +1 of the last factor
recursively, we can eliminate the biM +1 , i.e.
HΦ3 (w) ≷M∑(b1 − b∗1 )2 +

+

M
∑

+

M
∑

M ∑
∑
∑
{
b1 ab −b∗1 a∗ b∗ }2alph path{∑alph path

Then, Eq (36) is rewritten as
}2
∑{ ∑
∑
HΦ3 (w) ≷b1 abab −b∗1 a∗ b∗ a∗ b∗ . (39)

}2

path

alph

+1}2

b∗1 a∗ b∗ a∗ b∗·m

path

M {∑
∑

path

and

∑
path

path

(37)

path

b1 abab·m −m=1 pathb1i a1l blj alm bmk ,

∑

}2

}2
{∑
∑
b∗1 a∗ b∗ a∗
b1 aba −≷i,j,k∈{1,...,M +1}3 l,m∈{1,...,K+1}2∑b∗1 a∗ b∗ a∗ b∗·M +1

path

M {∑
∑

m=1 pathyalph path

+

∑

{

∑

alph pathb1 aab −∑pathb∗1 a∗ a∗ b∗ }2path

b1 abab −∑b∗1 a∗ b∗ a∗ b∗ }2 ,

path

(45)

∑M
where alpha means the marginalization over all generation of alphabets except for M +1. We apply a map
b1m = b01m − b∗1m to HΦ3 (w). For simplicity, we use thesame symbol b1m for b01m .
HΦ3 (w) ≷

M
∑

b21 +

alph path

alph

+

+

M ∑
∑
∑
{
(b1 + b∗1 )ab −b∗1 a∗ b∗ }2
path

M ∑
∑
∑
{
(b1 + b∗1 )aab −b∗1 a∗ a∗ b∗ }2alph path

path

∑

∑

M
∑

{

(b1 + b∗1 )abab −b∗1 a∗ b∗ a∗ b∗ }2 .

pathalph path(46)
According to Eq (42),HΦ3 (w) ≷

M
∑

b21 +

alph

+

M ∑
∑
∑
{
b∗1 ab −b∗1 a∗ b∗ }2alph path

M
∑

{

∑

∑

b∗1 a∗ a∗ b∗ }2+alph path

{

aab −

alph path= (M + 1)− 1 + M,(50)

which proves Lemma 1-2. (End of Proof )alph path

参考文献[1] Christophe Andrieu, Nando de Freitas, Arnaud Doucet,
and Michael I. Jordan. An introduction to MCMC
for machine learning. Machine Learning, 50(1-2):5–43,
2003.

path

∑

[2] R. E. Kalman. A new approach to linear ﬁltering andprediction problems. J. Basic Engineering, 82:35–45,
1960.

a∗ a∗ b∗ }2

path

M ∑
∑
∑
+
{
abab −a∗ b∗ a∗ b∗ }2 .

(48)

path

∑M
The number of terms in alph {·}2 is M #b , where #b is
the number of bim because only the output probability∑M
bim is counted in alph . Then N ST (M, 3) = M +M +M + M 2 = (M + 1)3−1 + M − 1.
Hereinafter, let us generalize the proof for any L.
Because of the reduction procedure, the right-hand sideof Eq (48) includes the terms
M
∑

b21 )

path

M ∑
∑
∑
{
ab −
a∗ b∗ }2

∑

M
∑
alph

Since b∗1m is a constant,M∑

to conﬁrm that

L−1

(47)

alph

the term for the alphabet y = (M + 1)(M + 1)(M + 1)∑∑
in Eq (39) vanishes i.e. { path aa − path a∗ a∗ }2 = 0.
∑
Then, the numbers of alph and bim in ST 1L−1 are∑Mcompletely the same as those of alph and bim in ST 2L∑M 2
except for the ﬁrst term alph b1 . Therefore it is easypathalph pathb21 +not aﬀect the number of the terms, which implies thatthe number of the squared terms is determined by the∑
number of bim in alph . Let us assume that b·M +1 = 1
in Eq (39) in order not to count it as a parameter. Under this assumption, #(ST 1L ) = (M + 1)L − 1 because#(ST 2L ) = #(ST 1L−1 ) + #(M ∑∑∑b∗1 a∗ b∗ a∗ b∗ }2 .
b∗1 abab −
+
{

M
∑

ST 2L , respectively. Let #(·) be a function to indicate
the number of squared terms. Obviously #(ST 1L ) =∑(M + 1)L . The suﬃx on the summation path doespathb∗1 aab −alph pathHΦ3 (w) ≷We count the squared terms. We deﬁne that thesquared terms in Eqs (39) and Eq (48) are ST 1L and

M ∑
∑
∑
{
ab −
a∗ b∗ }2 ,[3] Karim Lari and Steve J. Young. The estimationof stochastic context-free grammars using the insideoutside algorithm. Computer Speech and Language,
4:35–56, 1990.
[4] L. R. Rabiner. A tutorial on hidden Markov models andselected applications in speech recognition. Proceedingsof the IEEE, 77(22):257–2862, 1989.
[5] M. Stone. Cross-validatory choice and assessment ofstatistical predictions. Journal of the Royal StatisticalSociety, Series B, 36:111–147, 1974.
[6] S. Watanabe. Algebraic analysis for non-identiﬁable
learning machines. Neural Computation, 13 (4):899–
933, 2001.

(49)[7] K. Yamazaki, M. Aoyagi, and S. Watanabe. Asymptotic
analysis of Bayesian generalization error with Newton
diagram. Neural Networks, to appear.

which are the term of L = 2. Moreover, the ﬁrst term
appears when L = 1. This shows that the squared[8] Keisuke Yamazaki and Sumio Watanabe. Algebraic
geometry and stochastic complexity of hidden Markov
models. Neurocomputing, 69(1-3):62–84, 2005.

alph

b21 , andalph path

path

terms of L = l includes those of L < l, which proves
Lemma 1-1.