修 士 論 文 の 和 文 要 旨 研究科・専攻 大学院 情報理工学研究科 情報・ネットワーク工学専攻 博士前期課程 氏 名 橋元 雄祐 学籍番号 1931112 論 文 題 目 有限窓重み付け記号分解法の冗長度性能 ～確率的コンプレクシティを用いた解析～ 要 旨 情報源の確率推定と算術符号を用いた符号化方法のひとつとして Willems らによって考案 された文脈木重み付け(CTW)法がある．これは，二進木情報源，すなわち文脈構造を持つ二 進情報源に対してほぼ最適に符号化する方法である．しかしながら，CTW 法を多進木情報源 に単純に拡張した場合に冗長度性能が悪化する問題が明らかになり，それを解消するために 改良された重み付け記号分解法が考案された． 重み付け記号分解法とは，CTW 法と記号分解法を組み合わせた確率推定方法である．記号 分解法とは，多進シンボルをビットに分解して二進木に対応させ，各ビットの推定確率を求 め，それらの積により次シンボルの予測確率を求めるアルゴリズムである．これを CTW 法 に組み合わせることによって，各ビットに対応した文脈構造を参照するので多進木情報源に 対してほぼ最適に符号化が行える． 重み付け記号分解法について，従来研究ではシミュレーションによる実験は行われているが，理 論解析については十分に行われていない． 本稿では，ビッグデータに対応した実用的改善である 有限窓を付与した場合において，基本予測子にKrichevsky-Trofimov(KT)推定量，及びゼロ冗長 度推定量を用いた際における差分冗長度の理論的証明を確率的コンプレキシティを用いて行う． 本稿の構成について，第2 章では重み付け記号分解法を構成する既存研究について紹介する．第 3 章では冗長度解析で用いた確率的コンプレキシティについて紹介する．第 4 章では有限窓重み 付け記号分解法について，KT 推定量及びゼロ冗長度推定量を用いた場合の冗長度解析結果につ いて述べる．
令和
3
年度
修士卒業論文
有限窓重み付け記号分解法の冗長度性能
∼確率的コンプレクシティを用いた解析∼
電気通信大学 大学院 情報理工学研究科
博士前期課程 情報・ネットワーク工学専攻
情報通信システムコース
1931112
橋元 雄祐
指導教員 川端 勉 教授 八木 秀樹 准教授
提出 令和
3
年
3
月
25
日
THE UNIVERSITY OF ELECTRO-COMMUNICATIONS
Department of Communication Engineering and Informatics
目 次
1 はじめに 2 2 既存研究 3 2.1 Krichevsky-Trofimov 推定量 . . . . 3 2.2 文脈木重み付け法（CTW 法） . . . . 3 2.2.1 文脈木 . . . . 3 2.2.2 木情報源 . . . . 4 2.2.3 確率推定 . . . . 4 2.3 記号分解法 . . . . 6 2.3.1 記号分解アルゴリズム . . . . 6 2.3.2 記号分解法とその解釈 . . . . 7 3 確率的コンプレクシティ 9 3.1 確率的コンプレクシティ . . . . 9 3.2 FSMX モデルに関する確率的コンプレクシティ . . . . 10 3.3 tree モデルに関する確率的コンプレクシティ . . . . 11 4 有限窓重み付け記号分解法 13 4.1 有限窓 . . . . 13 4.2 重み付け記号分解法 . . . . 13 4.2.1 定義 . . . . 13 4.2.2 アルゴリズム . . . . 14 5 冗長度解析 16 5.1 KT 推定量を用いた場合の冗長度解析 . . . . 16 5.2 ゼロ冗長度推定量を用いた場合の冗長度解析 . . . . 23 6 まとめ 27 1第
1
章
はじめに
情報源の確率推定と算術符号を用いた符号化方法のひとつとして Willems らによって 考案された文脈木重み付け (CTW) 法 [2] がある．これは，二進木情報源，すなわち文脈 構造を持つ二進情報源に対してほぼ最適に符号化する方法である．しかしながら，CTW 法を多進木情報源に単純に拡張した場合に冗長度性能が悪化する問題が明らかになり，そ れを解消するために改良された重み付け記号分解法 [?] が考案された． 重み付け記号分解法は上記の問題を解消するために CTW 法と記号分解法 [3] の組み合 わせによって構成される．CTW 法を多進木情報源に適応した際に冗長度性能が悪化する 原因として２つの事柄が挙げられる．１つは CTW 法で基本予測子として用いられてい る Krichevsky-Trofimov(KT) 推定量についてであり，これは単に二進から多進に拡張す るだけでは冗長度性能が悪化する性質を持つ．もう１つはビット列の周期性についてで あり，多進系列をビット列の連接として表現した場合に二進の CTW 法を適応するとビッ ト列の周期性を十分に活用することができない．重み付け記号分解法は，CTW 法による 多進系列に対する文脈構造の重み付け，記号分解法によるビット列に対する確率推定を 行うことによって，上記の問題の解消を行っている． 重み付け記号分解法について，従来研究ではシミュレーションによる実験は行われて いるが，理論解析については十分に行われていない. 本稿では，ビッグデータに対応した 実用的改善である有限窓を付与した場合において，基本予測子に Krichevsky-Trofimov 推 定量，及びゼロ冗長度推定量を用いた際における個別冗長度の理論的証明を確率的コン プレクシティ [4] を用いて行う. 本稿の構成について，第２章では重み付け記号分解法を構成する既存研究について紹 介する．第３章では冗長度解析で用いた確率的コンプレクシティについて紹介する．第 ４章では有限窓重み付け記号分解法について，KT 推定量及びゼロ冗長度推定量を用いた 場合の冗長度解析結果について述べる． 2第
2
章
既存研究
2.1
Krichevsky-Trofimov
推定量
B ={0, 1} とする．ある 2 進系列 xn∈ Bkにおいて，０が n0個，１が n1個含まれている とする．2 進 Krichevsky-Trofimov(KT) 推定量 [1] は無記憶情報源の系列確率 θn0 (1− θn1) に無記憶過程の Jeffreys 事前分布を重み付けしたものであり，次のように定義される．た だし，θ は０の生起確率である． Pe(n0, n1) := ∫ 1 0 1 π√θ(1− θ)θ n0(1− θ)n1dθ = (n 0− 1 2)!(n 1− 1 2)! (n0+ n1)! (2.1) さらに，KT 推定量の性質として，現時刻 t における KT 推定量を Pe(xt1) とおくと，次時刻 の KT 推定量 Pe(xt+11 ) は次のように逐次計算可能である．ただし，xmn は系列 xnxn+1. . . xm を表し，n > m の場合は空列 λ である． Pe(xt+11 ) = nxt+1+ 1 2 n + 1 Pe(x t 1) (2.2) プログラムに用いる場合，上記の再帰式を用いてシンボルを読み込むごとに逐次更新し ていくのが一般的である．2.2
文脈木重み付け法（
CTW
法）
2.2.1
文脈木
情報源アルファベット A ={a1, a2, . . . , am} について考える．時刻 t に出力されるシン ボルを xtと表記すると，系列 xmn の語尾集合は{xmn, xmn+1, . . . , xm, λ} となる．ただし，λ は空列を表す．T ⊂ A∗ :=∪ l≥0Alにおいて，全ての s ∈ T に対して，その s の全ての語 3第 2 章 既存研究 4 尾が T に含まれるとき，T を語尾木または文脈木と呼ぶ．文脈木 T について，外部葉集 合 ∂T を次のように定義する． ∂T := {as : a ∈ A, s ∈ T } ∪ {λ} \ T (2.3) ∂T の各要素を T の葉と呼ぶ．∂T は A の完全語尾集合である．すなわち，∂T の要素が ∂T の他の要素の語尾になることはなく，かつ ∂T の要素の長さの集合は Kraft の不等式 を満たす．
2.2.2
木情報源
列 s∈ A∗について，s の語尾のうち ∂T の要素となるものを表す関数を β T(s) と定義し， β を文脈関数と呼ぶ．d := maxs∈∂T |s| を T の深さと呼ぶ．ただし，|s| は s の長さを表す． もし|s| ≥ d ならば βT(s) は一意に定まる．このとき，列 s(|s| ≥ d) について，βT(s) を文 脈または状態と呼ぶ．このような文脈木で定義される，文脈ごとに次の文字の発生する 確率分布が定義される Markov 情報源を木情報源と呼ぶ． 木情報源について，系列 xt −∞におけるシンボル xtの生起確率について考える．ある有 限の文脈木 T を仮定し，この T の外部葉集合 ∂T に対して，パラメータベクトル θ∂T = {θa s : s∈ ∂T, a ∈ A}, 0 ≤ θsa≤ 1 を作る．ここで θasは文脈 s の後に a を出力する確率を表 す．以上より，シンボル xtの生起確率は次のように表記できる． p(xt = a|xt−∞−1, T, θ∂T) = θsa (2.4) すなわち，木情報源は T がモデルとなり，初期状態とモデルとパラメータの組 (x0 −∞, T, θ∂T) で表現される．2.2.3
確率推定
ある木情報源 (x0 −∞, T, θ∂T) が系列 xt1を生成したとする．xt1 において文脈 s の後にシ ンボル a ∈ A が生成された回数を na sとすると，文脈 s が出現した回数は ns = ∑ a∈Anas となる．このとき，木情報源が系列 xt 1を生成する確率は以下のようになる． p(xt1|x0−∞, T, θ∂T) = ∏ s∈∂T ∏ a∈A (θsa)nas (2.5) 上式について，１つの外部葉ごとに∏a∈A(θa s)n a s という生成確率が与えられている．この 生成確率，すなわちパラメータ（ベクトル）が未知の場合に，{na s} から推定確率を与え るのが KT 推定量である．多進 KT 推定量は次のように定義される． Pe({nas}a∈A) := ∏ a∈A 1 2 · 3 2· · · (n a s − 12) m 2 · m+2 2 · · · (ns+ m−2 2 ) (2.6)第 2 章 既存研究 5 上式は a ∈ {0, 1} のとき，(2.1) 式の 2 進 KT 推定量に対応する．この KT 推定量につい て，木情報源に対して拡張することを考える．文脈木 T の外部葉 s ∈ ∂T におけるパラ メータベクトル θ∂T に対しても Jeffreys 事前分布を仮定するとき，T を固定した下での θ∂T の事前分布 J(θ∂T|T ) は次のようになる． J (θ∂T|T ) = ∏ s∈∂T ∏ a∈A(θ a s)−1/2 Γ(12)m/Γ(m 2) (2.7) ただし，Γ(·) はガンマ関数である．これにより混合をとったものを文脈木 T に関して固 定した木情報源についての KT 推定量と定義する． Pe(xt1|x0−∞, T ) := ∏ s∈∂T Pe({nas}a∈A) (2.8) = ∏ s∈∂T ∏ a∈A 1 2 · 3 2· · · (n a s − 1 2) m 2 · m+2 2 · · · (ns+ m−2 2 ) (2.9) したがって，モデルが既知でパラメータベクトルが未知の場合の (2.5) 式は次のように なる． p(xt1|x0−∞, T ) = Pe(xt1|x 0 −∞, T ) = ∏ s∈∂T Pe({nas}a∈A) (2.10) モデルも未知の場合は，それを推定するために深さが D で一定の文脈木T ∪ ∂T を用意 して，モデル T の確率分布（事前分布）を ω(T ) =∏s∈Tγ(s)¯ ∏s∈∂T γ(s) とする．ただし， 1 2 ≤ γ(s) < 1, ¯γ(s) = 1 − γ(s) である．このとき，推定確率は次のように表される． p(xt1|x0−∞) = ∑ T⊂T ω(T ) ∏ s∈∂T Pe({nas}a∈A) (2.11) これは，文脈木T ∪ ∂T 中に含まれる全ての T について推定確率∏s∈∂TPe({nas}a∈A) を求 め，各 T が ω(T ) で分布していると仮定して平均をとっていることを表している． 次に，CTW 法のアルゴリズムについて述べる．まず，深さ D で一定の文脈木T ∪ ∂T の 各ノード s に，カウンタの集合{na s}a∈A，変数 Pe(s), Pw(s) が保持される．ただし，Pe(s) = Pe({nas}) であり，Pw(s) は重み付け確率と呼ばれ，次のようにT ∪ ∂T の各ノード s に関 して再帰的に定義される． Pw(s) := { γ(s)Pe(s) + ¯γ(s) ∏ a∈APe(as) if s∈ T Pe(s) if s∈ ∂T (2.12) このように各ノードに対してカウンタと推定量 Pe(s) と重み付け確率 Pw(s) を保持させた ものを，重み付け文脈木と呼ぶ．また，Pw(λ) が系列推定確率 p(xt1|x0−∞) に対応する．
第 2 章 既存研究 6
2.3
記号分解法
2.3.1
記号分解アルゴリズム
情報源アルファベット A ={a1, a2, . . . , am}，m = k について考える．このとき，各シ ンボル a∈ A の 2 進 k ビット表示には b = b1b2· · · bk ∈ Bkが対応する．さらに，分解木と 呼ばれる，ラベル集合{0, ω, 1} をもつ深さ k − 1 の完全 3 分木を用意する．ただし，ω は 常に終端枝へとラベル付けされ，根は空列 λ によって表される．分解木の各節点を枝ラベ ル列によって一意に表現する．つまり，分解木は∪k−2 l=0B lの内部節点と(∪k−2 l=0B lω)∪ Bk−1 の葉で表される． 図 2.1: 分解木 (m = 8) 次に，多進シンボルの系列 x1x2· · · xn ∈ Anについて考える．系列 xji において，語頭 集合を{λ, xi, xi+1i , . . . , xji−1} と定義する．また，系列 xji において，シンボル a ∈ A の出 現回数を na，語頭 τ b（τ は Bk内のあるシンボルの語頭であり，また b∈ B）をもつシン ボルの出現回数を nb τとする．いま，シンボル a∈ A に関して語頭 τ と a = τb となる b が 存在するので，次式が成立する． nbτ = ∑ a:τ b⪯a na (2.13) ここで，⪯ は左のオペラントが右のオペラントの語頭であるか等しいことを意味する．分 解木の各葉(∪k−2 l=0Blω ) ∪ Bk−1には{0, 1} のカウンタ (n0 τ, n1τ) とそれに基づく 2 進 KT 推 定量 Pe(τ ) を保持される，ただし，Pe(τ ) は次の通りである． Pe(τ ) = (n0 τ− 12)!(n 1 τ − 12)! (n0 τ + n1τ)! (2.14) また，分解木の各内部節点∪k−2 l=0Blには．次のように再帰的に計算させる推定量 Pi(τ ) を第 2 章 既存研究 7 保持させる． Pi(τ ) = { Pi(τ 0)Pe(τ ω)Pi(τ 1) f or |τ| < k − 2 Pe(τ 0)Pe(τ ω)Pe(τ 1) f or |τ| = k − 2 (2.15) ただし，|τ| は τ の深さを表す． τ における推定量は，新しいシンボル b = b1b2· · · bkを読んだ上で次のように更新する． まず，根の葉 λω において，カウンタ nb1 ω および KT 推定量 Pe(λω) = Pe(n0ω, n1ω) を更新す る．次に，λ から枝 b1を下る．葉 b1ω において，カウンタおよび KT 推定量の更新を先 ほどと同様に行い，内部節点 b1から枝を下る．これを，最深部の葉にたどり着くまで繰 り返す．今度は，今までたどったパスに従って根に向かって引き返しながら，内部節点 の推定量 Pi(τ ) を上記の再帰的な式によって更新する．最終的に根で求まる推定量 Pi(λ) が，記号分解法によって求められる系列確率推定量 PSD(xn1) である．
2.3.2
記号分解法とその解釈
T を，k ビットの系列の真の語頭 τ ∈ T の集合とする．シンボル a ∈ A が確率 ξaで生 成されると仮定し，新たな確率パラメータ θb τを次のように定義する． θτb := ∑ τ b≺=aξa ∑ τ≺=aξa (2.16) このとき，次の等式が成立する． ∏ τ b≺=a θτb = ξa (2.17) すなわち，多進シンボル a = b1· · · bkは，確率 ∏k l=1θ bl b1···bl−1に従って，つまり確率パラ メータが{0 ≤ θb τ ≤ 1}τ∈T ,b∈{0,1}のマルコフ過程に従って生成されるということである． いま，θτ := θ0τ, ¯θτ := 1− θτ = θ1τと書くことにすると，シンボルを 2 進木の葉に対応さ せた木において，各内部節点 τ で分岐する際にパスを左に取る確率が θτであるようなモ デルが，記号分解法の確率モデルである． ここで，このモデルにおける系列確率について次の補題が成立する． 補題 2.3.1. 確率パラメータ{0 ≤ θb τ ≤ 1}τ∈T ,b∈{0,1}に基づいてシンボルが発生するモデ ルの系列確率 P (xn 1) は次式で表される： P (xn1) = ∏ a∈A (ξa)n a (2.18) = ∏ τ∈T ∏ b∈{0,1} (θτb)nbτ (2.19)第 2 章 既存研究 8 証明 2.3.1. 系列確率において，τ ∈ T と b ∈ {0, 1} を固定すれば，{θb τ}τ∈T は，出現した シンボルが語頭に τ b をもつ回数分掛けられるので，次のように計算できる． P (xn1) = ∏ a∈A (ξa)n a = ∏ a∈A ( ∏ τ b≺=a θτb)na (2.20) = ∏ τ∈T ,b∈{0,1} (θτb)∑τ b≺=ana (2.21) = ∏ τ∈T ∏ b∈{0,1} (θbτ)nbτ (2.22) 2 記号分解法の推定量 PSD(xn1) は，この系列確率に以下の事前分布を重み付けしたもの である． wSD(θ) = ∏ τ∈T π−1{θτθ¯τ}− 1 2 (2.23) 実際，dθ =∏τ∈T dθτと書けば，次のように計算できる． ∫ wSD(θ) ∏ τ∈T ∏ b∈{0,1} (θbτ)nbτdθ (2.24) = ∏ τ∈T (n0 τ − 1 2)!(n 1 τ − 1 2)! (n0 τ + n1τ)! (2.25) = ∏ τ∈T Pe(n0τ, n 1 τ) (2.26) = PSD(xn1) (2.27) すなわち，記号分解法は各語頭 τ の下でのビット b の分岐確率{θb τ} を２進 KT 推定量で 推定し，その推定値の積で系列予測確率を得ていると解釈される．
第
3
章
確率的コンプレクシティ
確率分布が未知の情報源から出力される系列に対して，符号化する際の最小符号長の 限界を確率的コンプレクシティと定義する． 本章では，一般的な場合について述べた後に FSMX モデル，tree モデルといった特殊な 場合の確率的コンプレクシティについて述べる．3.1
確率的コンプレクシティ
regret を次のように定義する． R = log 1 p(xn)− log 1 p(xn|θ∗) = log p(xn|θ∗) p(xn) (3.1) ここで，θ∗は真の確率パラメータを表す． このとき，minimax regret を達成する符号は次であることが知られている． ˆ m(xn) = p(x n|θ∗) ∑ xnp(xn|θ∗) (3.2) しかしながら，上式の分母を具体的に求めることは一般的に困難である．それに対して， Bayse 符号の方法で漸近的に確率的コンプレクシティを達成する方法が知られている． Jeffreys 事前分布は次のように定義される． wJ(θ) = √ det J (θ∗) CJ (3.3) ここで，J(θ) は Fisher 情報量であり，CJ := ∫ √ det J (θ∗)dθ である．これを用いた Bayse 混合は ρ(xn) = ∫ p(xn|θ)w J(θ)dθ として与えられる．これが漸近的 minimax 予測である ことは次のように Laplace 近似にを使って示される．アルファベットサイズを d + 1，Bn 9第 3 章 確率的コンプレクシティ 10 を中心が θ，半径が log n/√n のボールとするとき， ρ(xn) p(xn|θ∗) ∼ ∫ Bnp(x n|θ∗)w J(θ∗)dθ∗ p(xn|θ∗) (3.4) ∼ ∫ Bn exp ( −nuTJ (xˆ n, θ∗)u 2 ) wJ(θ)dθ (3.5) ∼ wJ(θ∗)(2π)k/2 nd/2(det( ˆJ (xn, θ∗)))1/2 (3.6) ∼ (det(J (θ∗)))1/2(2π)k/2 CJnd/2(det( ˆJ (xn, θ∗)))1/2 (3.7) ただし， ˆJ は経験的 Fisher 情報量，k はパラメータ数を表す． ここで，指数型分布族の場合は J(θ) = ˆJ (xn, θ) であるから， ρ(xn) p(xn|θ∗) ∼ (2π)k/2 CJnd/2 (3.8) すなわち， log 1 ρ(xn)− log 1 p(xn|θ∗) ∼ k 2 log n 2π + log CJ (3.9) を得る，ただし CJは定数である．
3.2
FSMX
モデルに関する確率的コンプレクシティ
FSMX モデルとは，2.2.2 節において，ある木情報源が任意の s ∈ ∂T と任意の a ∈ A に対して，（|sx| < d であっても）β(sx) が一意に存在する情報源である． 本節ではアルファベットサイズを d + 1 とする．SFMX モデルの確率的コンプレクシ ティは (3.9) と同様の値となる．したがって，CJ の値を求めれば良いので次の補題が成 立する． 補題 3.2.1. 情報源アルファベット X ={0, 1, · · · , d} に関する FSMX モデルについて考 える．X′ ={1, 2, · · · , d}，状態 s ∈ ∂T において x ∈ X が生起する確率を ηx|sとする．ま た，ηs= (η1|s, . . . , ηd|s)T，η = (ηsT1, η T s2, . . . , η T sL) とする．ただし，L は外部葉集合 ∂T の 要素数を表す．系列 xnについて，n が十分に大きいとき，C J は次のようになる． CJ = ∫ ∏ s∈∂T µd/2s D1/2(ηs)dη (3.10) ただし，µsは状態 s における定常確率，Dα(ηs) := ∏ x∈X(ηx|s)−(1−α)はディリクレ関数， dη :=∏s∈∂T ∏x∈X′dηx|sはルベーグ測度を表す．また，積分の範囲は { ηs : ∀x ∈ X′, ηx|s ≥ 0 and ∑ x∈X′ ηx|s ≤ 1 } (3.11)第 3 章 確率的コンプレクシティ 11 である． 証明 3.2.1. p(xn|η) について次の計算が成立する． log p(xn|η) = n−1 ∑ t=0 log ηxt+1|β(xt) (3.12) = ∑ s∈∂T,x∈X nx|slog ηx|s (3.13) ただし，nx|sは状態 s において x が出現した回数，β(·) は文脈関数を表す．
次に経験的 Fisher 情報量について考える．経験的 Fisher 情報量は−(1/n) log p(xn|η) の
ヘッセ行列である．したがって，各要素の計算結果は次のようになる． ˆ Jsx,ty(xn, η) = δstpˆs ( δxyηˆx|s (ηx|s)2 + ηˆ0|s (η0|s)2 ) (3.14) (x, y ∈ X′, s, t∈ ∂T ) ただし，ˆps:= ns/n，ˆηx|s := nx|s/nsであり，δ はクロネッカーのデルタである． これより，Fisher 情報量は次のように求めることができる． Jsx,ty(η) = lim n→∞Eη ˆ Jsx,ty(xn, η) (3.15) = δstµs ( δxy ηx|s + 1 (η0|s) ) (3.16) したがって，CJの定義より CJ = ∫ √ det J (η)dη (3.17) =∫ √ ∏ s∈∂T µs ∏ x∈X 1 ηx|s dη (3.18) =∫ ∏ s∈∂T µd/2s D1/2(ηs)dη (3.19) 2
3.3
tree
モデルに関する確率的コンプレクシティ
tree モデルにおいて，FSMX モデルに埋め込むことによって漸近的に確率的コンプレ クシティを達成する手法について述べる． 一般の有限アルファベット X ={0, 1, . . . , d} を考える．T′を一般の tree モデルを定義す る文脈木とする．T は T′を拡張した，FMSX モデルを定義する文脈木とする．要素数を第 3 章 確率的コンプレクシティ 12 L とする状態集合 S(T ) ={s1, . . . , sL} について，そのパラメータを η = (ηs1, . . . , ηsL) と する．また，要素数を L′とする状態集合 S(T′) ={g 1, . . . , gL′} について，そのパラメー タを ζ = (ζg1, . . . , ζgL′) とする．ただし，ζgaは文脈 gaにおいて x∈ X が生成される確率 ζx|ga(x = 1, . . . , d) を成分とするベクトルである．ここで，∂T の要素のうち gaを語尾と して持つものの集合を次のように定義する． F (g) :={s : s ∈ ∂T, ∃t ∈ X∗, tg = s} (3.20) すなわち，F (g) は T の状態のうち，T′において g でマージされる状態の集合である．こ のとき，ϕ を次のように定義する． ∀s ∈ F (g), ϕs(ζ) := ζg (3.21) このとき，S(T ) における η の Fisher 情報行列を J(η)，S(T′) における ζ の Fisher 情報行 列を J′(ζ) とおく．J (η) の η x|s, ηy|tに関する成分は以下のようになる． J(s,x),(t,y)(η) = δstµs ( δxy ηx|s + 1 η0|s ) (3.22) J′(ζ) の ζx|g, ηy|hに関する成分は以下のようになる． J(g,x),(h,y)′ (ζ) = δgh ∑ s∈F (g) µs(ϕ(ζ)) (δxy ζx|g + 1 ζ0|g ) (3.23) このとき，J′(ζ) の行列式の平方根は次のようになる． √ det J′(ζ) = ∏ g∈∂T′ ∑ s∈F (g) µs(ϕ(ζ)) d/2 D1/2(ζg) (3.24) このとき，定数 CJは次のようになる． CJ = ∫ ∏ g∈∂T′ ∑ s∈F (g) µs(ϕ(ζ)) d/2 D1/2(ζg)dζ (3.25)
第
4
章
有限窓重み付け記号分解法
重み付け記号分解法とは，前章で紹介した文脈木重み付け法と記号分解法を組み合わ せた確率推定法であり，これに有限窓を付与することによって参照範囲を制限したもの が有限窓重み付け記号分解法である．この章では，有限窓重み付け記号分解法の要素で ある有限窓及び重み付け記号分解法について述べる．4.1
有限窓
有限窓を用いたデータ系列に対する推定法の場合，次のシンボル xtは窓の内容によっ て推定される．例えば，窓の大きさを B とした場合，窓の内容は{xt−Bxt−B+1· · · xt−1} となる．xtを推定した後，窓の内容は t 方向へスライドされて{xt−B+1xt−B+2· · · xt} とな る．上記手順を系列全体に対して逐次的に行う．4.2
重み付け記号分解法
4.2.1
定義
木情報源の情報源アルファベット A :={a1, a2,· · · , am}，状態集合を ∂T と定義し， m = 2kの場合を考える．このとき，a∈ A に対応した k ビット表現 {0, 1}k =: Akの真の 語頭集合をT ，深さ k − 1 の分解木の葉集合を L と定義する．これらの定義より，シン ボル系列 an∈ Anをビットで表現した系列 ank ∈ Ankを時系列として考える．このとき， 任意時刻 t = lk +|τ| + 1 とするとき，atの状態は all−1−B の語尾である c∈ ∂T と語頭であ る τlk+1lk+|τ|の対 (c, τ ) である．つまり，(c, τ ) の全体 ∂T × T =: S を状態集合とする． 13第 4 章 有限窓重み付け記号分解法 14
4.2.2
アルゴリズム
はじめに，図 4.1 のような分解木と文脈木の直積構造を用意する．図 5.2 の右方向には 記号分解法を用い，図 4.1 の下方向には文脈に関する重み付けを行う．座標 (c, d) のノー ドに保存される推定確率として Pc,d e を定義する．c 方向は文脈木方向を表し，d 方向は分 解木方向を表す．同様に，座標 (c, d) のノードに保存される重み付け確率として Pc,d w を 定義する．(c, d) の位置関係によって以下のように場合分けされる．分解木において内部 ノードかつ文脈木において内部ノードの場合， Pec,d := Pec,d0Pec,dωPec,d1 (4.1) Pwc,d := 1 3P c,d e + 1 3 ∏ a∈A Pwac,d+ 1 3P c,d0 w P c,dω w P c,d1 w (4.2) 分解木において内部ノードかつ文脈木において葉の場合， Pec,d := Pec,d0Pec,dωPec,d1 (4.3) P wc,d := Pec,d (4.4) 分解木において葉かつ文脈木において内部ノードの場合， Pec,d:= Pe(n0c,d, n 1 c,d) (4.5) Pwc,d:= 1 2P c,d e + 1 2 ∏ a∈A Pwac,d (4.6) 分解木において葉かつ文脈木において葉の場合， Pec,d := Pe(n0c,d, n 1 c,d) (4.7) Pwc,d := Pe(n0c,d, n 1 c,d) (4.8) のように計算する．ただし，na c,dは座標 (c, d) における a の出現回数を表す．上記計算 を有限窓を用いて逐次的に行う． (4.6) 式は CTW 法と同じ形である．したがって，分解木における葉ノードは文脈木方 向で CTW 法を適用できるので次式のように表現できる． Pwλ,ϕ =∑ N w(N )∏ d∈L ∏ c∈∂Td Pec,d (4.9) ただし，L は分解木の葉集合であり，Tdはモデル N を１つ決めると定まる全多進木（語 尾木）の内部節点を表す．第 4 章 有限窓重み付け記号分解法 15 d a2, ω a2, 11 a2, 1ω a2, 10 a2, 0ω a2, 00 a2, 01 am, ϕ am, 1 am, 0 am, ω am, 11 am, 1ω am, 10 am, 0ω am, 00 am, 01 ama1, ϕ a1a1, ϕ a2a1, ϕ c λ, 1 λ, 0 λ, ω λ, 11 λ, 1ω λ, 10 λ, 01 λ, 0ω λ, 00 λ, ϕ a1, ϕ a1, 1 a1, 0 a1, ω a1, 11 a1, 1ω a1, 10 a1, 01 a1, 0ω a1, 00 a2, ϕ a2, 1 a2, 0 図 4.1: 分解木と文脈木
第
5
章
冗長度解析
冗長度解析において，性能指標として差分冗長度を導入する．差分冗長度とは次の定 義を満たす冗長度である． 定 義 5.0.1. 冗長度を符号長と理想符号長の差分 ρ(xn) := log 1/p(xn) − log 1/p(xn|θ∗) とする．このとき，系列長 n, n + 1 の系列について冗長度の差分 ρ(xn+1)− ρ(xn) (5.1) を差分冗長度と呼ぶ．差分冗長度は１シンボル当たりの冗長度を表す． 差分冗長度を性能指標とする理由は，有限窓を用いたシステムを考えているため窓に 入る新たな１シンボルに対する冗長度が性能指標となるからである． この章では，推定量に KT 推定量，ゼロ冗長度推定量を用いた場合の解析結果を定理 として示した後に，その結果に至る過程を述べる．5.1
KT
推定量を用いた場合の冗長度解析
定理 5.1.1. 木情報源に対して基本予測子に KT 推定量を用いた有限窓重み付け記 号分解法を適用する場合を考える． 未知の情報源アルファベット A :={a1, a2, . . . , am}，文脈構造をによる状態集合を ∂T と定義し，m = 2kとする．また，a∈ A に対応した k ビット表現 {0, 1}kの語頭 集合T ，その葉集合を L とすると，全体の状態集合は S := {(c, d), d ∈ L, c ∈ ∂Td} である． このとき，十分に大きな有限窓長 B に対して差分冗長度は次のように示される． |S| 2B + o ( 1 B ) (5.2) 16第 5 章 冗長度解析 17 はじめに，確率モデル N について定義する．確率モデル N は分解木と文脈木の組み合 わせによって決定される．ただし，文脈木は分解木の各葉に付随して定まる．分解木の 葉集合をL，モデル N を一つ決めると定める全文脈木の内部ノードを Tdとすると N の 定義式は次のように示すことが出来る． N :={∂Td, d∈ L} (5.3) このとき，真の確率モデル N∗に対して推定される確率モデル N を次のように場合分け することが出来る． (ⅰ) N = N∗ when ∀d ∈ L, ∂Td= ∂Td∗ (ⅱ) ∂N ∩ N∗ ̸= ϕ when ∃d ∈ L, ∂Td∩ Td∗ ̸= ϕ (ⅲ) N ⊋ N∗ when∀d ∈ L, Td⊇ Td∗, and ∃d ∈ L, Td ⊋ Td∗ ただし，Td∗は真の確率モデル N∗によって決定される文脈木の内部ノードである． 図 5.1: 確率モデルの場合分け したがって，冗長度を次のように表すことができる． − log pλ,ϕ w (x n) + log p(xn|N∗, θ∗) (5.4) =− log p(xn|N∗) + log p(xn|N∗, θ∗) − log w(N∗)− log { 1 + ∑ N :∂N∩N∗̸=ϕ w(N )p(xn|N) w(N∗)p(xn|N∗)+ ∑ N :N⊋N∗ w(N )p(xn|N) w(N∗)p(xn|N∗) } (5.5) ここで，N∗は真の確率モデルを示し，p(xn|N) := ∏ d∈L ∏ c∈∂TdP c,d e である．上式につい て差分 ∆ を取ると次のように計算できる． ∆(5.5)∼ ∆ {− log p(xn|N∗) + log p(xn|N∗, θ∗)} − ∑ N :∂N∩N∗̸=ϕ ∆ w(N )p(x n|N) w(N∗)p(xn|N∗) − ∑ N :N⊋N∗ ∆ w(N )p(x n|N) w(N∗)p(xn|N∗) (5.6)
第 5 章 冗長度解析 18 次に，(5.6) 式各項について解析を行う．一項目について (3.9) 式より次のように変形する ことができる． ∆{− log p(xn|N∗) + log p(xn|N∗, θ∗)} (5.7) =∑ s∈S ∆ { 1 2log n 2π + log CJ } (5.8) =∑ s∈S 1 2n = |S| 2n (5.9) さて，残りの項の解析の準備として KT 推定量の比 ∏c∈∂T Pe/ ∏ c∈∂T∗Peに関する補題 を用意する． 補題 5.1.1. KT 推定量は次のように定義される． Pe(xn) := (n0− 1 2)!(n 1− 1 2)! n! (5.10) このとき，次の等式が成立する． ∏ c∈∂T Pe(xn) ∏ c∈∂T∗Pe(xn) = O ( 1 P oly(√n) ) (T ⊋ T∗) exp{−Θ(n)} (∂T ∩ T∗ ̸= ϕ) (5.11) 証明 5.1.1. 図 5.2 のような T, T∗の場合について考える．∂T と ∂T∗ を各々 B1∪ B2∪ B3 と C1∪ C2 ∪ C3 のように分割し，B1 の各 c は C1のある c′ の真の子孫，B3の各 c は C3 のある c′の真の先祖，また B2, C2については B2＝ C2 となるようにできる． 図 5.2: B と C の関係 (n− 12)! = 2(2n)!2nn!，スターリングの公式 n ≃ √ 2πn(ne)nより，(5.10) 式は次のように変 形することが出来る． Pe(xn)≃ √ 2 πn ( n0 n )n0( n1 n )n1( n e )n (5.12) また，na cは文脈 c の後に a が出現する回数を表すとして nc= ∑ an a c ∼ q(c)n と近似でき るとする．ただし，q(·) は定常確率を表す．
第 5 章 冗長度解析 19 上式を用いてそれぞれの場合について解析を行う． 初めに，B1, C1に対して解析を行う． C1の文脈 c′を先祖とする B1の部分集合を S(c′) とすると次のように計算できる． log ∏ c∈B1Pe(x n) ∏ c′∈C1Pe(x n) = log ∏ c′∈C1 ∏ c∈S(c′) √ 2 πnc ( n0 c nc )n0 c(n1 c nc )n1 c( nc e )nc √ 2 πnc′ (n0 c′ nc′ )n0 c′ (n1 c′ nc′ )n1 c′(n c′ e )nc′ (5.13) = ∑ c′∈C1 [ log √ 2 πn |S(c′)|−1 + log √ q(c′) ∏ c∈S(c′)q(c) + log ∏ c∈S(c′) ( n0c nc )n0 c(n1 c nc )n1 c (n0 c′ nc′ )n0 c′(n1 c′ nc′ )n1 c′ + log ∏ c∈S(c′) ( q(c) q(c′) )q(c) q(c′) e(nc′−nc) (5.14) さて，(5.14) 式３項目の計算に関して次のような準備を行う． nc = ∑ l∈S(c)nlより，(nl | l ∈ S(c)) は多項分布 (n, q(c) q(c′)) と捉えることが出来る．また， θ = P (0) をベルヌーイ分布のパラメータとした場合，その最尤推定値は ˆθ = n0/n, ˆθl = n0 l/nlとなり，ˆθ 周りでテーラー展開すると次式を得る． log p(xn|θ) = log p(xn|ˆθ) + (θ − ˆθ) d dθ log p(x n|ˆθ) + 1 2(θ− ˆθ) 2 d 2 dθ2 log p(x n|ˆθ) (5.15) = log p(xn|ˆθ) + 1 2(ˆθ− θ) 2nJ (ˆθ) (5.16) ただし，J(ˆθ) は Fisher 情報量である． これらより，J(ˆθ)≈ J(θ) が成立する場合，ある c′において (5.14) 式３項目は次のように 計算できる． log ∏ c∈S(c′) ( n0 c nc )n0c(n1 c nc )n1c (n0 c′ nc′ )n0 c′ (n1 c′ nc′ )n1 c′ = log ∏ l∈S(c)p(x nl|ˆθ l) p(xn|ˆθ) (5.17) = J (θ) 2 { ∑ l (ˆθl− θ)2nl− (ˆθ − θ)2n } (5.18) = J (θ) 2 ∑ l nl { (ˆθl− θ)2− (ˆθ − θ)2 } (5.19) = J (θ) 2 ∑ l nl { (ˆθl− ˆθ)2 } (5.20) = J (θ) 2 ∑ l √nl ˆθl− ∑ k∈S(c) nk n ˆ θk 2 (5.21)
第 5 章 冗長度解析 20 ただし，(5.21) 式への変形に ˆθ =∑k∈S(c) nk nθˆkを用いた． ここで，クロネッカーのデルタ δ を導入すると，ある l について次のように計算できる． √ nl ˆθl− ∑ k∈S(c) nk n ˆ θk = ∑ k∈S(c) (δlk √ nkθˆk− √ nlnk nn √ nkθˆk) (5.22) =∑ k ( δlk− √ nl n √ nk n ) √ nkθˆk (5.23) =∑ k (δlk− vlvk) ηk (5.24) ただし，vl:= √nl n，ηk := √ nkθˆkとおいた． nkは２項分布なので正規分布に近似できるとすると，ˆθk ∼ N ( θ,nθ ¯θ k ) ，ηk ∼ N(√nkθ, θ ¯θ ) が成立する．したがって，ηkは次のように表現できる． ηk = √ nθvk+ √ θ ¯θϵk (5.25) ただし，ϵkは i.i.d. で標準正規分布 ϵk ∼ N(0, 1) に従うものとする． これを用いて (5.24) 式を変形すると次式を得る． ∑ k (δlk− vlvk) ηk = (1− ∑ k vlvk) √ θ ¯θϵk (5.26) 上式より平均値が０であることがわかる．したがって，(5.21) 式は正規分布の 2 乗和， J (θ) = 1/θ ¯θ であることに注意すると次のように計算できる． J (θ) 2 ∑ l √nl ˆθl− ∑ k∈S(c) nk n ˆ θk 2 = J (θ) 2 θ ¯θχ 2 (|S(c′)|−1) (5.27) = 1 2χ 2 (|S(c′)|−1) (5.28) 以上より，(5.14) 式全体において log O(1/√n) と表現できる． 次に，B3, C3について解析を行う．
第 5 章 冗長度解析 21 B3の文脈 c を先祖とする C3の部分集合を S(c) とすると次のように計算できる． log ∏ c∈B3Pe(x n) ∏ c′∈C3Pe(x n) = log ∏ c∈B3 √ 2 πnc ( n0c nc )n0 c(n1 c nc )n1 c( nc e )nc ∏ c′∈S(c) √ 2 πnc′ (n0 c′ nc′ )n0 c′(n1 c′ nc′ )n1 c′(n c′ e )nc′ (5.29) = ∑ c∈B3 log √ 2 πn 1−|S(c)| + log √∏ c′∈S(c)q(c′) q(c) + log ∏ c′∈S(c) ( n0 c nc )n0 c(n1 c nc )n1 c (n0 c′ nc′ )n0 c′(n1 c′ nc′ )n1 c′ + log ∏ c′∈S(c) ( q(c) q(c′) )q(c) q(c′) e(nc′−nc) (5.30) (5.30) 式の３項目について計算を行う．ある c について注目すると次のように計算できる． ∏ c′∈S(c) ( n0 c nc )n0 c(n1 c nc )n1 c (n0 c′ nc′ )n0 c′(n1 c′ nc′ )n1 c′ = exp { nc′h ( n0 c′ nc′ ) −∑ c nch ( n0 c nc )} (5.31) = exp [ nc′ { h ( n0 c′ nc′ ) −∑ c nc nc′ ( n0 c nc )}] (5.32) ただし，h(α) :=−α log α − (1 − α) log(1 − α) である． q(c′) := nc′/n, p(0|c′) := n0c′/nc′, q(c|c′) := nc/nc′, p(0|c, c′) := n0c/ncの下で I(X; C|C′)≥ α≥ 0, q(c′) > 0 が成り立つとする．ただし，X はデータ系列に関する事象，C は文脈に 関する事象を表し，I(·) は相互情報量を表す． このとき，上式指数部において次のように計算できる． nc′ { h ( n0 c′ nc′ ) −∑ c nc nc′ ( n0 c nc )} = nq(c′) H(X|C′)− ∑ c∈S(c′) q(c|c′)H(H|C, C′) (5.33) = nq(c′)I(X; C|C′) (5.34) ただし，H(·) は情報エントロピーを表す． ここで，α が n が十分大きい時に正に取れることを示す． はじめに，仮定しているのは定常マルコフ情報源であるので， q(c′) > 0 の下で，n′cは 確率１で無限になる．したがって，確率分布は確率１で真の確率に収束する． これらを踏まえて，次の背反事象について議論する． (A) lim infnI(X; C|C′) > 0
第 5 章 冗長度解析 22
c′における真の確率分布が不一致の場合に (B) の確率は０である．一方，一致の場合に
(B) の確率は１である．言い換えると，確率１で (A) が成立する． ゆえに，
α = min
C′ lim infn I(X; C|C
′) (5.35) ととることが出来る． したがって，I(X; C|C′)≥ α ≥ 0 より (n0 c′ nc′ )n0 c′(n1 c′ nc′ )n1 c′ ∏ c′∈S(c) ( n0 c nc )n0 c(n1 c nc )n1 c ≤ exp {−nq(c ′)α} (5.36) ≤ exp{−Θ(n)} (5.37) が成立する．したがって，(5.14) 式全体において−Θ(n) と表現することが出来る． T ⊋ T∗の場合において，∂T = B1∪ B2，∂T = C1∪ C2と見なせるので ∏ c∈∂T Pe(x n) ∏ c∈∂T∗Pe(xn) = O ( 1 P oly(√n) ) (5.38) と表現できる． ∂T ∩ T∗ ̸= ϕ の場合において，∂T = B1∪ B2∪ B3，∂T = C1∪ C2∪ C3となるが log ∏ c∈∂T Pe(xn) ∏ c∈∂T∗Pe(xn) = log ∏ c∈B1Pe(x n) ∏ c′∈C1Pe(x n) + log ∏ c∈B3Pe(x n) ∏ c′∈C3Pe(x n) (5.39) と項を分けることによって個別に計算できる．それぞれの項の解析結果より ∏ c∈∂T Pe(x n) ∏ c∈∂T∗Pe(xn) = exp{−Θ(n)} (5.40) と表現することが出来る． 以上より，次の等式 ∏ c∈∂T Pe(xn) ∏ c∈∂T∗Pe(xn) = O ( 1 P oly(√n) ) (T ⊋ T∗) exp{−Θ(n)} (∂T ∩ T∗ ̸= ϕ) (5.41) は満たされる． 2
第 5 章 冗長度解析 23 (5.6) 式二項目について，まず補題 5.1.1 より，Θ(n) = αn（α は定数）で表現できるこ とに注意すると次のように計算できる． ∆ w(N )p(x n|N) w(N∗)p(xn|N∗) (5.42) = w(N ) w(N∗)∆ ∏ d∈L ∏ c∈∂TdP c,d e (xn|N) ∏ d∈L ∏ c∈∂Td∗P c,d e (xn|N∗) (5.43) = w(N ) w(N∗)∆ { ∏ d∈L ∏ c∈C1P c,d e (xn|N) ∏ d∈L ∏ c∈B1P c,d e (xn|N∗) · ∏ d∈L ∏ c∈C3P c,d e (xn|N) ∏ d∈L ∏ c∈B3P c,d e (xn|N∗) } (5.44) = w(N ) w(N∗)∆ exp { log ∏ d∈L ∏ c∈C1P c,d e (xn|N) ∏ d∈L ∏ c∈B1P c,d e (xn|N∗) + log ∏ d∈L ∏ c∈C3P c,d e (xn|N) ∏ d∈L ∏ c∈B3P c,d e (xn|N∗) } (5.45) = w(N ) w(N∗)∆ exp {
−αn − log O(P oly(√n))} (5.46) =− w(N ) w(N∗) ( α + 1 O(P oly(n)) )
exp{−αn − log O(P oly(√n))} (5.47) 次に (5.6) 式三項目について，全ての d について ∂Td∩ Td∗ = ϕ が成立するので (5.6) 式二 項目の計算において α = 0 の場合と考えることができる．従って，(5.6) 三項目は次のよ うに計算できる． ∆ w(N )p(x n|N) w(N∗)p(xn|N∗) =− w(N ) w(N∗) 1 O(P oly (n√n)) (5.48) これらの結果から，有限窓のサイズを十分に大きい B とした場合の有限窓重み付け記号 分解法の平均冗長度は次のように示すことが出来る. |S| 2B + o ( 1 B ) (5.49)
5.2
ゼロ冗長度推定量を用いた場合の冗長度解析
定理 5.2.1. 木情報源に対して基本予測子にゼロ冗長度推定量を用いた有限窓重み 付け記号分解法を適用する場合を考える． 未知の情報源アルファベット A :={a1, a2, . . . , am}，文脈構造をによる状態集合を ∂T と定義し，m = 2kとする．また，a∈ A に対応した k ビット表現 {0, 1}kの語頭 集合T ，その葉集合を L とすると，全体の状態集合は S := {(c, d), d ∈ L, c ∈ ∂Td} である． このとき，十分に大きな有限窓長 B に対して差分冗長度は次のように示される． |S1| 2B + o ( 1 B ) (5.50)第 5 章 冗長度解析 24 ただし，S1 :={(c, d), d ∈ L1, c ∈ ∂Td} は，パラメータ 0 < θ < 1 を持つ葉集合 L の部分集合 L1とそれに付随する文脈木の葉集合 ∂Tdの積である． 有限窓重み付け記号分解法のなかで用いられる記号分解法の推定確率に対してゼロ冗 長度推定量を適用した場合を考える．有限窓ゼロ冗長度推定量は，ゼロ頻度問題に対し て冗長度を定数で抑えることが出来る推定量であり，次式のように定義される． Pzc,d(n0c,d, n1c,d) = 1 2P c,d e (n 0 c,d, n 1 c,d) + 1 4· 1{n 0 c,d= 0} + 1 4· 1{n 1 c,d = 0} (5.51) ただし，1{·} は括弧の中の条件が真のとき 1，偽のとき 0 になる． (5.5) 式より，p(xn|N) :=∏ d∈L ∏ c∈∂TdP c,d z として計算を行う．この時，(5.6) 式の一項目 について (3.9) 式より次のように変形することができる． ∆{− log p(xn|N∗) + log p(xn|N∗, θ∗)} (5.52) = ∆ logp(x n|N∗, θ∗) p(xn|N∗) (5.53) = ∆ { log ∏ d∈L1 ∏ c∈∂Td pc,d(xn|N∗, θ∗) 1 2P c,d e (xn|N∗) + log ∏ d∈L2 ∏ c∈∂Td 1 1 2P c,d e (xn|N∗) + 14 } (5.54) = ∆{∑ s∈S1 ( log p c,d(xn|N∗, θ∗) Pec,d(xn|N∗) + log 2 ) +∑ s∈S2 A1 } (5.55) = ∆ { ∑ s∈S1 ( 1 2log n 2π + log CJ ) +∑ s∈S2 A1 } (5.56) = ∑ s∈S1 1 2n = |S1| 2n (5.57) ただし，L1は分解木において 0 < θc,d < 1 を持つ葉集合であり，L2は分解木において
θc,d= 0 or θc,d= 1 を持つ葉集合である．また，A1は log43 ≤ A1 ≤ log 4 を満たす定数で
あり，Sa:={(c, d), d ∈ La, c∈ ∂Td} である． さて，(5.6) 式の二項目について考える．初めに， log ∏ d∈L ∏ c∈∂TdP c,d z (xn|N) ∏ d∈L ∏ c∈∂Td∗P c,d z (xn|N∗) (5.58) と表現し，この評価を考えることにしよう．
第 5 章 冗長度解析 25 図 5.3: B と C の関係 分母の ∂T∗ d と分子の ∂Td を各々 B1∪ B2∪ B3 と C1∪ C2∪ C3 のように分割し，B1 の 各 c は C1のある c′ の真の子孫，B3の各 c は C3のある c′の真の先祖，また B2, C2につ いては B2＝ C2 となるようにできる．また，B3の文脈 c を先祖とする C3の部分集合を S(c) とし，B2, C2に関する積は各々等しい． B3, C3が存在する場合には，B3の文脈 c を先祖とする C3の部分集合 S(c) が存在するが， c に基づくデータサンプルは S(c) に属する文脈に基づくサブサンプルに分割されるわけ であるから，十分長い時間がたてば対応する比の部分は，c に基づく確率分布が非縮退で あること，つまり，0 < θc,d< 1 を満たす葉集合L1に含まれるならば，O(P oly(1√n)) とな る．また，縮退していれば θc,d= 0 or 1 を満たす葉集合L2に含まれるため，正の上下限 をもつ定数になる．ただし，poly(·) は多項式を表す．もし B1, C1に対応する部分が存在 するならば，B1と C1に関する積の比は指数部が−Θ(n) となる． 以上の考察のもとに，(5.6) 式の二項目については，ある d が存在して B1, C1に対応す る部分が必ず存在するわけであるから，指数部が−Θ(n) となる．したがって，Θ(n) = αn （α は定数）と表せることに注意すると (5.6) 式の二項目は次のように計算できる． ∆ w(N )p(x n|N) w(N∗)p(xn|N∗) = w(N ) w(N∗)∆ exp { log p(x n|N) p(xn|N∗) } = w(N ) w(N∗)∆ exp { log ∏ d∈L ∏ c∈C1P c,d z (xn|N) ∏ d∈L ∏ c∈B1P c,d z (xn|N∗) + log ∏ d∈L1 ∏ c∈C3P c,d z (xn|N) ∏ d∈L1 ∏ c∈B3P c,d z (xn|N∗) + log ∏ d∈L2 ∏ c∈C3P c,d z (xn|N) ∏ d∈L2 ∏ c∈B3P c,d z (xn|N∗) } (5.59) = w(N ) w(N∗)∆ exp {
−αn − log O(P oly(√n)) + A2
} (5.60) =− w(N ) w(N∗) ( α + 1 O(P oly(n)) )
e(−αn−log O(P oly(√n))+A2) (5.61)
第 5 章 冗長度解析 26 が成立するので (5.6) 式二項目の計算において α = 0 の場合と考えることができる．従っ て，(5.6) 三項目は次のように計算できる． ∆ w(N )p(x n|N) w(N∗)p(xn|N∗) =− w(N ) w(N∗) eA2 O(P oly (n√n)) (5.62) これらの結果から，有限窓のサイズを十分に大きい B とした場合の有限窓重み付け記号 分解法の平均冗長度は次のように示すことが出来る. |S1| 2B + o ( 1 B ) (5.63)
第
6
章
まとめ
本論文では，有限窓重み付け記号分解法について，確率的コンプレクシティを用いた 差分冗長度の導出とゼロ冗長度推定量を基本予測子とすることによって差分冗長度を改 善できることを理論的に示した． 本研究ではゼロ冗長度推定量を用いることによってパラメータが極値である分解木の 葉ノードの数だけ差分冗長度を改善できることを示した．しかしながら，ビット列に出 現しないビットが存在することは，多進系列にも出現しない文脈が存在することが考え られる．今後の課題として，上記のような文脈構造に対して最適な重み付け方法を行う ことによって分解木と文脈木の両面から冗長度の改善ができるアルゴリズムの模索が考 えられる． 27謝辞
最後に, 本研究を進めるにあたりお忙しいところ, ご指導していただいた川端勉教授に 深 く感謝いたします. また, 日常生活やゼミなどでお世話になった大濱靖匡教授, 八木秀 樹 准教授, SANTOSO BAGUS 助教に深く感謝いたします. そして, 研究室やゼミ室にお い て共に研究を進めてきた皆様に感謝いたします. 28参考文献
[1] R. Krichevsky and V. Trofimov. ”The performance of universal encoding,” IEEE
Transactions on Information Theory, Vol. 27, No. 2, pp. 199–207, March 1981.
[2] Frans M. J. Willems, Yuri M. Shtarkov and Tjalling J. Tjalkens. ”The Context Tree Weighting Method: Basic Properties,” IEEE Transactions on Information Theory, Vol.41, pp.653–664, 1995.
[3] Ryoma Fujita and Tsutomu Kawabata. ”Weighted Symbol Decomposition Method and its Redundancy,” Proceedings of the 31st Symposium on Information Theory
and its Applications, 2008.
[4] 竹内 純一，川端 勉, ”木情報源と確率的コンプレクシティ,” 科研費報告書（多次 元二段階量子化器への新しい幾何学的アプローチ，課題番号 6560325, 研究代表者 川端 勉), pp.55–61, Nov. 2007.
[5] Thomas M. Cover and Joy A. Thomas. ”Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing),” Wiley- Interscience, July 2006.
