情報処理学会第 74 回全国大会

1D-7
マルコフモデルによる自動分類に対する分類誤り確率の推定
小林学†

後藤正幸 ‡† 湘南工科大学

1松嶋敏泰 ‡‡ 早稲田大学

はじめに与えられた学習データを用いて，新規データがどのカテゴリに所属するかを自動的に判別する自動分類問
題は，ベクトル空間モデルやサポートベクターマシン(SVM)[1] などの手法により大きく発展した．一方，J.Ziv
らは無ひずみデータ圧縮法である LZ アルゴリズムを用いて文書分類を行う手法を提案した [3]．また圧縮性能の非常に優れた文脈木重みづけ (CTW) 法が提案されており，これを文書分類に適用する手法も提案されている [4]．
本研究ではマルコフモデルを用いた文書分類法を対象とする．ここで各カテゴリに対する文書が同一のマルコフモデルから生起するという仮定を置く．そのとき，新規テスト文書の文書長が有限の場合の分類誤り確率を評価する．具体的には新規テスト文書に対する理想符号長の平均と分散を評価し，中心極限定理を用いることにより各カテゴリの分類誤り確率を近似する手法を提案する．

2

FSMX 情報源

定義 1 整数 a, b に対して本稿では [a, b] = {a, a+1, . . . , b}と定義する．また，ある 2 つのシンボル c と d の連結を cd とつなげて表記する．さらに任意のシンボル系列· · · ya−1 ya · · · yb yb+1 · · · に対して，yba = ya ya+1 · · · yb と定義する．さらにシンボル系列 yba , a ≤ b に対する系列長を |yba | = b − a + 1 と表記する．
次に 2 元情報源からの n ビットの出力を x1n = x1 x2 · · · xnと表記する．ただし任意の i ∈ [1, n] に対して xi ∈ [0, 1]
である．
2
例えば 2 次マルコフ情報源は，長さ 2 の文脈 xi−2 xi−1
によりシンボル xi の生起する確率が定まる．さて FSMX
情報源は，シンボルの生起する確率が文脈により異なり，さらにその文脈の長さも異なるマルコフ情報源である．今情報源を規定する文脈の集合を S と書く．
例 1 S = {00, 10, 1} とする．このとき情報源シンボル xi ∈ [0, 1] が生起する確率は，パラメータ ΘS ={θ00 , θ10 , θ1 } により次式で規定される．

P(xi = 1|xi−1 = 1) =

θ1 ,An Error Probability Estimation of the Text Classification Using MarkovModel†Manabu KOBAYASHI ‡Masayuki GOTO ‡Toshiyasu MATSUSHIMA††Shigeichi HIRASAWA†School of Engineering, Shonan Institute of Technology‡Faculty of Science and Engineering, Waseda University††Fuculty of Information Technology and Business, Cyber University2-61

平澤茂一 †††† サイバー大学
P(xi = 1|xi−2 xi−1 = 10) =θ10 ,P(xi = 1|xi−2 xi−1 = 00) =

θ00 .

(1)

すなわち，文脈が 1 の場合に xi = 1 となる確率は θ1 であり，文脈が 10 の場合に xi = 1 となる確率は θ10 などとなる．
2
このように xi は 2 元ならば，S が与えられた下で，xi に対する文脈が定まるとそのパラメータは 2 項パラメータとなる．

3 FSMX モデルによる文書分類
各文書はその文書が所属するカテゴリが存在するものと仮定する．簡単のためカテゴリには自然数の番号が付いており，カテゴリ数を C で表す．またカテゴリの集合を C = [1, C] と表す．学習文書はその所属するカテゴリが既知の文書であり，カテゴリ c ∈ C に所属する Nc 個の学習文書をそれぞれ x̃1(c) , x̃2(c) , . . . , x̃(c)Nc と表記する．文書分類問題はこれらの学習文書が与えられた下で，カテゴリが未知の新規テスト文書 zn1 ∈ [0, 1]nがどのカテゴリに所属するかを推定する問題である．
ここで，カテゴリ c ∈ C の文書は文脈の集合 S(c) を持つ同一の FSMX 情報源から生成されるものと仮定する．また本稿では簡単のため，各 S(c) , c ∈ C, は既知と仮定する．今カテゴリ c ∈ C に対して，連結した学習(c)
文書を x̃(c) = x̃1(c) x̃2(c) · · · x̃(c)中の文脈
Nc とする．また x̃(c)(c)s ∈ S の下での 0 の出現回数を a s ( x̃ )，1 の出現回数を b s ( x̃(c) ) とする．このときカテゴリ c に対する FSMXモデルの文脈 s ∈ S(c) に対するパラメータのラプラス型推定量はθ̂ s =b s ( x̃(c) ) + 12,a s ( x̃(c) ) + b s ( x̃(c) ) + 1s ∈ S(c) ,(2)とできる．さて，カテゴリ c ∈ C の文書が生起する事
前確率を P(c) と表記すると，新規テスト文書 zn1 の事
後確率は式 (2) を用いて
∏ b (zn )nθ̂ s s 1 (1 − θ̂ s )as (z1 ) ,P(zn1 | x̃(c) ) = P(c)(3)s∈S(c)となる．結果的に式 (3) を最大とするカテゴリを zn1 の推定カテゴリとすれば良い．

4 文書分類の誤り確率
さて本節では C = [1, 2] として学習文書数がある程度大きな場合に，前節の文書分類法の分類誤り確率のCopyright 2012 Information Processing Society of Japan.
All Rights Reserved.

情報処理学会第 74 回全国大会

2()∑ 
a s ( x̃(1) ) 
1 − θ̂(1) a s ( x̃(1) )s ≈n
 | x̃(1) | 1 − | x̃(1) | log(2) 
1−θ̂ss∈S(1,2)

推定値を出力することを目的とする．さて∆(zn1 ) ≜ log

P(zn1 | x̃(1) ),P(zn1 | x̃(2) )(4)a s ( x̃(1) )b s ( x̃(1) )1 − θ̂(1)θ̂(1)
ssloglog (2)(1)2(2)| x̃ |1 − θ̂ sθ̂ s()(1) 2 (1)(1)
b s ( x̃ )b s ( x̃ ) θ̂ s  log (2)  + (1) 1 −| x̃ || x̃(1) |
θ̂ s


∑

1 − θ̂(1)b s ( x̃(1) )θ̂(1) a s ( x̃(1) )
ss log+log−n | x̃(1) |(2)(1)(2)
| x̃ |
1 − θ̂ sθ̂ s s,s′ ∈S(1,2) |s,s′
1 − θ̂(1)θ̂(1)
b s′ ( x̃(1) ) a s′ ( x̃(1) )s′s′ loglog×+

(2)
(1)
(2)
 | x̃(1) || x̃ |1 − θ̂ s′θ̂ s′ −2と定義すると，新規テスト文書の真のカテゴリが 1 であるときの分類誤り確率 P(1)
E は()
nn
P(1)
(5)
E = P z1 ∆(z1 ) ≤ 0 ,と表される．ただし上の確率はカテゴリ 1 の真のパラメータ集合 ΘS(1) で規定される．ここで式 (3),(4) より∑(1)n(a s (zn1 ) log(1 − θ̂(1)∆(zn1 ) =s ) + b s (z1 ) log θ̂ s )s∈S(1)∑−n(2)(a s (zn1 ) log(1 − θ̂(2)s ) + b s (z1 ) log θ̂ s ),= Ê[(∆(zn1 )2 ],(6)s∈S(2)が成り立つ．ただし注意しなければならないのは，確率変数は a s (zn1 ) 及び b s (zn1 ) である．
さて，式 (6) を用いて ∆(zn1 ) の平均と分散を求めることを考える．
∑n(1)E[∆(zn1 )] =(E[(a s (zn1 )] log(1 − θ̂(1)s ) + E[b s (z1 )] log θ̂ s )s∈S(1)−∑n(2)(E[(a s (zn1 )] log(1 − θ̂(2)s ) + E[b s (z1 )] log θ̂ s )s∈S(2)≈ n∑ ( a s ( x̃(1) )s∈S(1)− n=∑ (| x̃(1) |b s ( x̃(1) )log(1 − θ̂(1)log θ̂(1)s )+s(1)| x̃ |a s ( x̃(1) )b s ( x̃(1) )(2)log(1−θ̂)+log θ̂(2)ss| x̃(1) || x̃(1) |s∈S(2)Ê[∆(zn1 )],)となる．次に 2 次のモーメントを求めるために，S(1) , S(2)に対応する完全 2 分木をそれぞれ MS(1) , MS(2) と表記し，それぞれのノード及び枝の和集合を取った木を MS(1,2) =MS(1) ∪ MS(2) とする．結果的に MS(1,2) に対応する文脈の集合を S(1,2) とする1 ．ここで ∀s ∈ S(1,2) に対して a s (zn1 )及び b s (zn1 ) に対する分散・共分散を考える必要がある
が，これを厳密に評価するのは大変である．そこで本稿ではこれらを多項分布で近似することを考える．このとき多項分布の分散・共分散を用いると

E[a s (zn1 )b s (zn1 )]E[a s (zn1 )a s′ (zn1 )]≈≈2(1) (1)−n(q(1)
s ) (1 − θ s )θ s ,(1)(1) (1)−nq(1)s (1 − θ s )q s′ (1 − θ s′ ),と計算可能である．∆ = ∆(zn1 ) となる確率密度は µ =Ê[∆(zn1 )], σ2 = Ê[(∆(zn1 )2 ] − Ê[∆(zn1 )]2 と置いて，中心極限定理より正規分布を用いて P(∆) ≈ N(∆|µ, σ2 ) と近似できる．従って式 (4),(5) より∫ 0P(1)≈N(∆|µ, σ2 )d∆,(12)E−∞と近似することが可能である．
さらに各カテゴリの学習文書に対するパラメータ推定において，a s ( x̃(c) ), b s ( x̃(c) ) 及び θ̂(c)s に対して重複対数の法則を用いることもできる．そのとき，P(1)E の上界と下界の推定値を得ることも可能である．

)

(7)

(1)
(1)
(1)
E[a s (zn1 )2 ] ≈ nq(1)s (1 − θ s )(1 − q s (1 − θ s )),(11)

(8)
(9)

s , s′ ,(10)などと簡単になる．ただし q(1)s はカテゴリ 1 の情報源における文脈 s に対する定常確率である．従ってE[(∆(zn1 )2 ]2
1 − θ̂(1)θ̂(1)
  ∑ ss nna (z ) log+ b s (z1 ) log (2) = E   (1,2)  s 1
θ̂ s 1 − θ̂(2)ss∈S

1 すなわち S(1) , S(2) それぞれにおける長い方の文脈を取ったものの集合が S(1,2) である．

2-62

5 まとめ
本研究ではマルコフモデルを用いた文書分類法を対象とし，2 値分類問題に対する分類誤り確率の推定法について検討を行った．このとき新規テスト文書に対する理想符号長の平均と分散を評価し，中心極限定理を用いることにより分類誤り確率を近似する手法を提案した．

参考文献[1] C.M. ビ ショップ，パ タ ー ン 認 識 と 機 械 学 習 ，Springer，2008.
[2] H. Chen, P. Ti and X. Yao, “Probabilistic Classification Vector Machines,” IEEE Trans. On Neural Networks, vol.20, no.6, pp.902-914, June 2009.
[3] J. Ziv and N. Merhav,“A Measure of Relative Entropy Between Individual Sequences with Application to Universal Classification,” IEEE Trans. on Information Theory, vol.39, no.4, pp.1270–1279, July
1993.
[4] Z. Dawy,
J. Hagenauer and A. Hoﬀmann,“Implementing the context tree weighting
method for content recognition,” Proc. of the IEEE
Data Compression Conference, p.536, March 2004.
[5] H. Cai, S. R. Kulkarni and S. Verdú,“Universaldivergence estimation for finite-alphabet sources,”
IEEE Trans. on Information Theory, vol.52, no.8,pp.3456–3475, Aug. 2006.
[6] D. Benedetto, E. Caglioti, and V. Loreto, Language
Trees and Zipping, Physical Review Letters, vol.
88, no.4, p.28, Jan. 2002.

Copyright 2012 Information Processing Society of Japan.
All Rights Reserved.