![研究背景 （5／6） ベイズ符号 特徴 仮定した事前分布の下では，ベイズ最適 漸近的（シンボル系列長を無限とした場合）に， 平均符号長がエントロピーに収束 必要メモリ量，計算量を削減した効率的な 構成アルゴリズム [ 松嶋 95] -> 必要メモリ量削減アルゴリズム [ 中野 05]](https://image.slidesharecdn.com/ma99992006id3654598/85/ma99992006id365-6-320.jpg)
![研究背景 （6／6） ベイズ符号 実データに[中野 05]を適用する際の問題点 必要メモリ量が依然として莫大 -> 使用メモリ量に何らかの制約が必要 無情報事前分布以外の事前分布設定 -> 従来研究が行われていない](https://image.slidesharecdn.com/ma99992006id3654598/85/ma99992006id365-7-320.jpg)
![CT情報源に対するベイズ符号 Context Tree を利用して符号化確率を計算 [ 松嶋 95] 例）次数の最大値が 2 の Context Tree パラメータの事前分布 で重み付け 状態の事前分布 で重み付け 0 1 0 1 0 1 （ 4/7 ） (5)](https://image.slidesharecdn.com/ma99992006id3654598/85/ma99992006id365-18-320.jpg)
![CT情報源に対するベイズ符号 Context Tree を利用して符号化確率を計算 [ 松嶋 95] 問題点： 時点 t ごとに，全状態 s の P ( s | x t － 1 ) を計算が必要 （ 5/7 ） (5) 計算量削減 ??? 31 15 7 状態数 ??? ??? 677 4 26 3 5 2 モデル数 最大次数](https://image.slidesharecdn.com/ma99992006id3654598/85/ma99992006id365-19-320.jpg)
![CT情報源に対するベイズ符号 P ( s ) の代わりに下式の q ( s ) を利用 [ 松嶋 95] q ( s ) の事後確率の計算でも， x t － 1 に対応する状態のみで OK ↓ 最大次数 D に対して O ( D 2 ) の計算量 ※ D を設定しない場合でも O ( n 2 ) の計算量 0 1 0 1 0 1 例） x t － 1 ＝??? 10 なら （ 6/7 ） s (10) s (0) s (λ)](https://image.slidesharecdn.com/ma99992006id3654598/85/ma99992006id365-20-320.jpg)
![CT情報源に対するベイズ符号（7/7） 必要メモリ量を削減したアルゴリズム [ 中野 05] [ 松嶋 95] で最大次数 D を設定しない場合 必要メモリ量： O ( n 2 ) ↓ Context Tree の表現方法の改良 -> 必要メモリ量が O ( n ) となる アルゴリズムの提案](https://image.slidesharecdn.com/ma99992006id3654598/85/ma99992006id365-21-320.jpg)
![考察 どのように事後分布の調整を行うのがよいか モデルの事前分布： αの値の変更によるメモリ量の削減 パラメータの事前分布： c＝10～100の間で設定 （さらに細かく調べる必要） 計算量に関して [中野 05]と比較して同等の計算量（ O ( n 2 ) ） ↓ 実用的なオーダー](https://image.slidesharecdn.com/ma99992006id3654598/85/ma99992006id365-37-320.jpg)
![[論文紹介] LSTM (LONG SHORT-TERM MEMORY)](https://cdn.slidesharecdn.com/ss_thumbnails/2018-181019021803-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Similar to ma99992006id365 (20)
![[PRML勉強会資料] パターン認識と機械学習 第３章 線形回帰モデル (章頭-3.1.5)(p.135-145)](https://cdn.slidesharecdn.com/ss_thumbnails/prmlp-150228215621-conversion-gate01-thumbnail.jpg?width=560&fit=bounds)
More from matsushimalab (20)
ma99992006id365
- 1. ベイズ符号化アルゴリズムを 用いたテキストデータ圧縮 中野晶 小泉大城 松嶋敏泰 早稲田大学 理工学部 経営システム工学科
- 2. 研究背景 （1／6） データ圧縮とは？ シンボル系列を，別の短い系列（符号語）に 変換する技術 情報源 モデル m 符号化 復号化 シンボル系列 x n 符号語 P ( x n | m ) シンボル系列 x n 受信者
- 3. 研究背景 （2／6） データ圧縮の評価基準 平均符号長 ＝ （符号語 bit 長）／（シンボル系列長） m に対して平均符号長の下限 （エントロピー H ( m ) ） P ( x n | m ) が既知のとき， H ( m ) まで圧縮が可能 (1)
- 4. データ圧縮の手法 bzip2 （ BS 法）， gzip など（ LZ 法） 計算量が少ない 実用化が行われている ベイズ符号 理論的には優れた圧縮率 計算量，必要メモリ量が多い 研究背景 （3／6）
- 5. 研究背景 （4／6） ベイズ符号 情報源モデルのクラス M を既知とする． モデル m ∈ M （ 未知）に対してモデルの事前分布 P ( m ) を仮定 ↓ 事前分布の下でベイズ最適な符号長となる符号 シンボル系列 x n に対して，符号化確率 P C ( x n ) を計算 (2)
- 6. 研究背景 （5／6） ベイズ符号 特徴 仮定した事前分布の下では，ベイズ最適 漸近的（シンボル系列長を無限とした場合）に， 平均符号長がエントロピーに収束 必要メモリ量，計算量を削減した効率的な 構成アルゴリズム [ 松嶋 95] -> 必要メモリ量削減アルゴリズム [ 中野 05]
- 7. 研究背景 （6／6） ベイズ符号 実データに[中野 05]を適用する際の問題点 必要メモリ量が依然として莫大 -> 使用メモリ量に何らかの制約が必要 無情報事前分布以外の事前分布設定 -> 従来研究が行われていない
- 8. 研究目的 ベイズ符号の実用化に向けて 事前分布の設定 学習対象データを利用 使用メモリ量に制約 圧縮率，必要メモリ量の評価 従来使用してきた無情報事前分布との比較 すでに実用化されているデータ圧縮法 bzip2 との比較 圧縮率は向上，必要メモリ量は依然莫大 主結果：
- 9. Context Tree（CT）情報源 （1／4） パラメトリックな情報源モデルクラス m ：CT情報源モデル θ ( m ) ： m の下でのパラメータ シンボル x t の生起確率： P ( x t | x t － 1 , θ ( m ), m ) 過去のシンボル系列 x t － 1 から x t の 生起確率が決まる情報源 モデルが 一意に定まる
- 10. CT情報源 （2／4） s i ：直前シンボル系列が??? i であることを表す状態 モデル m ：複数の状態 s で定義 例） m 1 ＝ { s 00 ， s 10 ， s 1 } 直前のシンボル系列 x t － 1 により時点 t の状態 s ( x t － 1 ) が一意に定まる 状態 s が持つパラメータ θ ( s ) により，シンボルの生起確率 P ( x t | x t － 1 ,θ( s ), s ) が定まる P ( x t | x t － 1 ,θ( m ), m ) ＝ P ( x t | x t － 1 ,θ( s ( x t － 1 )), s ( x t － 1 )) (3)
- 11. CT情報源 （3／4） CT 情報源は木モデルで表現可能 枝：情報シンボル x ノード：状態 s 例1 状態 { s 00 ， s 10 ， s 1 } を持つCT情報源 m 1 x t － 1 を表す x t － 2 を表す 0 0 s 1 1 1 s 10 s 00
- 12. CT情報源 （4／4） x t － 1 ＝??? 1 1 0 の場合 シンボル x t － 1 ＝ 0 シンボル x t － 2 ＝ 1 例1 状態 { s 00 ， s 10 ， s 1 } を持つCT情報源 m 1 x t － 1 を表す x t － 2 を表す 0 0 s 1 1 1 s 10 s 00 状態は s 10
- 13. Context Tree （1／2） Context Tree とは CT 情報源モデルが未知である場合にシンボル系列から状態の候補を求めるための木モデル 例）次数の最大値が 2 の CT 情報源モデルクラス （次数：系列 x t － 1 を何文字遡れば状態が定まるか） m 1 m 2 m 3 m 4 m 5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
- 14. Context Tree （2／2） Context Treeとは CT情報源モデルが未知である場合にシンボル系列から状態の候補を求めるための木モデル 例）次数の最大値が 2 の Context Tree 0 1 0 1 0 1 x t － 1 ＝??? 1 0 1 の場合， 時点 t で考えられる状態 S t は S t ＝ { s λ ， s 1 ， s 01 } s λ s 01 s 1
- 15. CT情報源に対するベイズ符号（1/7） 問題設定 既知：情報源モデルが CT 情報源 未知：情報源モデル m ，パラメータ θ( m ) 仮定：モデルの事前分布 P ( m ) パラメータの事前分布 P (θ( m )) 目的：符号化確率 P C ( x n ) の計算 ベイズ 符号器 算術 符号器 符号語 符号化確率 P C ( x n ) シンボル系列 x n 事前分布 P ( m ) ， P(θ( m )| m ) 事後分布 P ( m | x n ) ， P (θ( m )| m , x n )
- 16. CT情報源に対するベイズ符号（2/7） 逐次型ベイズ符号 時点 t ごとにシンボル x t の符号化確率 P C ( x t | x t － 1 ) の計算 同時に事後分布 P ( m | x t ) ， P (θ( m ), m | x t ) の計算 -> 次の時点 ( t ＋ 1) の事前分布として利用 ベイズ 符号器 算術 符号器 符号語 符号化確率 P C ( x t | x t － 1 ) シンボル x t 事前分布 事後分布 次の時点 (t ＋ 1) の事前分布
- 17. CT情報源に対するベイズ符号（3/7） 符号化確率を次式で計算 問題点： 最大次数が増加 ↓ モデル数が莫大 ↓ 莫大な計算量 (4) ??? ??? 677 4 26 3 5 2 モデル数 最大次数
- 18. CT情報源に対するベイズ符号 Context Tree を利用して符号化確率を計算 [ 松嶋 95] 例）次数の最大値が 2 の Context Tree パラメータの事前分布 で重み付け 状態の事前分布 で重み付け 0 1 0 1 0 1 （ 4/7 ） (5)
- 19. CT情報源に対するベイズ符号 Context Tree を利用して符号化確率を計算 [ 松嶋 95] 問題点： 時点 t ごとに，全状態 s の P ( s | x t － 1 ) を計算が必要 （ 5/7 ） (5) 計算量削減 ??? 31 15 7 状態数 ??? ??? 677 4 26 3 5 2 モデル数 最大次数
- 20. CT情報源に対するベイズ符号 P ( s ) の代わりに下式の q ( s ) を利用 [ 松嶋 95] q ( s ) の事後確率の計算でも， x t － 1 に対応する状態のみで OK ↓ 最大次数 D に対して O ( D 2 ) の計算量 ※ D を設定しない場合でも O ( n 2 ) の計算量 0 1 0 1 0 1 例） x t － 1 ＝??? 10 なら （ 6/7 ） s (10) s (0) s (λ)
- 21. CT情報源に対するベイズ符号（7/7） 必要メモリ量を削減したアルゴリズム [ 中野 05] [ 松嶋 95] で最大次数 D を設定しない場合 必要メモリ量： O ( n 2 ) ↓ Context Tree の表現方法の改良 -> 必要メモリ量が O ( n ) となる アルゴリズムの提案
- 22. 実データに対するベイズ符号 問題点 必要メモリ量 256 進の Context Tree を利用 -> ノードを表現するのに必要なメモリ量が莫大 事前分布の設定 従来は無情報事前分布を利用 -> 実データは無情報事前分布に適合しない -> 圧縮率の低下（ bzip2 と同程度） ※ 実データに適合するような事前分布の研究はされていない
- 23. 本研究のアプローチ（1／5） モデルの事前分布 必要メモリ量 ∝ Context Tree のノード数 逐次型ベイズ符号化確率 P C ( x t | x t － 1 ) 計算時， P ( s ) の値が小さい状態 s small に関する和計算 P ( s small ) ＝ 0 とみなしても符号化確率に微小の差 P ( s small ) ＝ 0 とする （状態がないとみなす） ??? (6)
- 24. 本研究のアプローチ（2／5） パラメータの事前分布 状態の下でシンボルが何回生起したか という情報（頻度カウンタ）として保持． 状態における頻度カウンタの合計値 ??? 事前分布の圧縮における影響の強さ ↓ 頻度カウンタの合計値を調整することによる圧縮率の変動は？
- 25. 事前分布設定の流れ 事後分布 P ( m | x , Y ) ， P (θ( m )| x , Y , m ) ベイズ 符号器 符号化確率 P C ( Y ) 学習対象 データ セット Y 無情報事前分布 P ( m ) ， P (θ( m )| m ) 学習済み事後分布 P ( m | Y ) ， P (θ( m )| Y , m ) ベイズ 符号器 算術 符号器 符号語 符号化確率 P C ( x | Y ) 圧縮対象 データ x 事前分布と して利用 本研究のアプローチ（ 3 ／ 5 ）
- 26. 本研究のアプローチ（4／5） モデルの事前分布の調整法の流れ 学習 データ y 2 y k ??? 事後分布 学習済み 事前分布 P ( m | Y ) P ( m | y 2 ) P ( m | y k ) y 1 P ( m | y 1 ) ??? ベイズ符号化 ノード削減① 事後分布の合成 ノード削減② q ( s | y i ) ＞ α より 次数の高いノード P ( s | Y ) ＜ β と なる葉ノード
- 27. パラメータの事前分布の調整法 パラメータの分布：頻度カウンタで表現 学習データから単純に出現頻度を計算 ↓ 頻度カウンタの値が大きすぎる ↓ 各状態の頻度カウンタの比率を変えずに， 合計値が定数 c となるように正規化 本研究のアプローチ（5／5）
- 28. シミュレーション シミュレーション目的 シミュレーション1 学習済み事前分布を用いた逐次形ベイズ符号の 圧縮性能評価 シミュレーション2 パラメータの事前分布の調整を行った逐次型ベイズ符号の圧縮性能評価 シミュレーション3 モデルの事前分布の調整を行った逐次型ベイズ符号の圧縮性能，必要メモリ量評価
- 29. シミュレーション シミュレーション条件 テキストのクラスと，使用ファイルの総サイズ： 学習データ 圧縮対象データ （ 100 ファイル） （ 20 ファイル） 英文テキスト 約40MB 約6MB 英文HTML 約35MB 約5.5MB 日本語テキスト 約5MB 約1.2MB 日本語HTML 約3.5MB 約0.6MB
- 30. シミュレーション1 目的 学習済み事前分布を用いた逐次型ベイズ符号 無情報事前分布を用いた逐次型ベイズ符号 bzip2 を用いて圧縮を行った場合の圧縮性能評価
- 32. シミュレーション2 目的 パラメータの事前分布の調整を行った際の 圧縮性能評価 頻度カウンタの合計値 c を以下のように設定 c＝{1,10，100,調整無し}
- 34. シミュレーション3 目的 必要メモリ量削減に向けて， ノード削減を行う条件（α，β）を変更 ↓ 圧縮率と必要メモリ量のトレードオフの関係
- 37. 考察 どのように事後分布の調整を行うのがよいか モデルの事前分布： αの値の変更によるメモリ量の削減 パラメータの事前分布： c＝10～100の間で設定 （さらに細かく調べる必要） 計算量に関して [中野 05]と比較して同等の計算量（ O ( n 2 ) ） ↓ 実用的なオーダー
- 38. まとめと今後の課題 まとめ 学習対象データを利用した事前分布の設定，調整 -> 圧縮率の向上 事前分布 P ( s ) の小さいノードを削減した下での 圧縮性能評価 今後の課題 複数のモデルクラスを考慮した事前分布の設定 -> 性能評価 必要メモリ量の更なる削減 （圧縮率とのトレードオフを考慮する必要）