階層型の確率モデル族に基づくユニバーサル情報源符号化に関する研究

[ホーム]
[研究業績]
[研究業績詳細]

タイトル	階層型の確率モデル族に基づくユニバーサル情報源符号化に関する研究
著者	宮希望
年度	2016
形式	博士論文
分野	情報源符号化
掲載雑誌名	早稲田大学博士論文
掲載号・ページ
掲載年	2016
掲載月	7
アブスト（日本語）	情報理論の一分野である情報源符号化問題はデータ圧縮や機械学習等の基礎理論として近年盛んに研究が行われている．情報源符号化の代表的な問題設定として，ある確率構造を仮定した情報源から出力される情報源系列を符号語と呼ばれる別の系列に符号化し，符号語を伝送や蓄積した後，一切誤り無く元の情報源系列に復号する事が考えられる．これは無歪み情報源符号化と呼ばれる．無歪み情報源符号化において可変長，すなわち符号語長が情報源系列毎に異なる事を許容した場合，代表的な評価基準として平均符号語長が挙げられる．平均符号語長とは各情報源系列に対する符号語長の情報源の確率分布に関する期待値である．特に，情報源に定常エルゴードな確率分布を仮定した場合，任意の無歪み符号に対し，情報源系列1シンボルあたりの平均符号語長の下限が漸近的にエントロピーレートで与えられる事および1シンボルあたりの平均符号語長が漸近的にエントロピーレートに等しくなる，ある無歪み符号が存在する事がシャノンの情報源符号化定理として知られている．エントロピーレートとは情報源の確率分布から一意に定まる量である．さらに，情報源の確率構造を利用する事により，情報源系列1シンボルあたりの平均符号語長がエントロピーレートに漸近する実用的な符号化アルゴリズムまで提案されている．その代表的な例としてハフマン符号や算術符号等が挙げられる．一方，ユニバーサル符号と呼ばれる情報源の確率構造の一部が未知である情報源符号化の問題は実用的に重要な研究となっている．特に，情報源が定常エルゴードな確率分布であれば，情報源系列1シンボルあたりの平均符号語長がエントロピーレートに漸近する符号を構成する事が重要なテーマとなってくる．ユニバーサル情報源符号化における代表的な問題設定として，情報源の確率構造に対し，例えば，情報源系列の出現確率が1次マルコフ過程と呼ばれる直前の値のみに依存する確率モデルに従う事は既知であるが遷移確率の確率パラメータは未知であるという様な仮定を置く事が挙げられる．さらに，出現確率が直前の長さkの系列に依存するk次マルコフ過程である事，すなわち確率モデルはマルコフ過程であると仮定されているが次数kが未知，つまり何次のマルコフ過程かは未知であるという問題設定等も考えられている．前者をモデル既知の確率モデル，後者をモデル未知の確率モデルとそれぞれ呼ぶ事にする．確率モデルの仮定に基づくユニバーサル符号においては，ある評価関数を導入した下でその評価関数の最適化に基づいた符号化に関する研究が一部で行われている．その際，評価関数として対数損失関数が導入されるのが一般的である．対数損失関数の情報源の確率分布に関する期待値は冗長度と呼ばれ，これは平均符号語長とエントロピーレートの差分を表す．特に，各時点において観測される情報源シンボルを逐次的に符号化する問題は，逐次的に観測されるデータを基に母集団分布を予測する統計的予測問題と等価であるとみなせ，さらに，冗長度は統計的予測問題におけるカルバックライブラー情報量と等価であるとみなせる.統計的予測問題においては度々，仮定した確率モデルが母集団の確率分布を表現できるか否かという事が問題となる一方，ユニバーサル符号化問題では確率モデルに基づく符号化においてさえもそのような事はあまり議論されていない．ユニバーサル符号は様々な問題設定や評価基準から研究が行われているが，確率モデルのパラメータに事前分布を導入し，符号語長をベイズ基準の下で最小化するベイズ符号は，理論的にも重要な符号である．情報源符号化においては，例えば圧縮対象のテキストの種類に応じて，ある単語の出現頻度がどの程度であり，さらにその頻度がそれまでの文脈にどの程度依存して変わってくるか等が事前に分かっている場合が多いため，パラメータに事前分布を仮定する事は比較的自然である．特にベイズ符号の場合，その性能を理論的に容易かつ精密に解析する事が可能であり，実際，平均符号語長がエントロピーレートに漸近する事が明らかにされているが，その漸近式はo(1)まで明らかにされており，収束オーダーも明確である．さらに，情報源がマルコフ過程のように高次のモデルが低次のモデルを含む入れ子構造を持つ階層型のモデル未知の確率モデルに対し，ベイズ符号の平均符号語長が精密に解析されており，ベイズ符号の有効性が理論的に証明されている．本研究ではまず，モデル既知の確率モデルに基づくベイズ符号において情報源の確率分布がその確率モデルでは表現されない分布だった場合の平均符号語長を精密に漸近評価している．さらに，その結果を応用し，階層型のモデル未知の確率モデルに基づくベイズ符号において，情報源の確率分布がその確率モデルでは表現されない分布だった場合の平均符号語長を精密に漸近評価し，そのように仮定が崩れた場合でもベイズ符号が有効である事を論じている．本研究ではさらに，区分定常情報源に関するベイズ符号の応用について考察を行っている．区分定常情報源とは，モデル未知の確率モデルで表される情報源の一種であり，ある定常分布に従って情報源系列を発生させている情報源の確率パラメータがある時点で突然に変化し，その後またある時点まではその変化したパラメータを持つ定常分布に従って系列を発生させ，またパラメータが変化するといった情報源である．インターネット上でやり取りされるファイルのデータ圧縮等で利用されているbzip2は，ブロックソート法と呼ばれるユニバーサル符号を実装したものであるが，これまでのところ，その符号化性能は理論的に明確に解析されていない．本研究では，モデル未知の確率モデルの一種である，次数kが未知のマルコフ過程を仮定した情報源に対し，ブロックソート法の特徴的前処理であるブロックソート後の系列が区分定常情報源からの出力系列とみなせる事を利用し，区分定常情報源のベイズ符号を応用する事により，実用性をほとんど失う事無く理論的にも明確な符号化アルゴリズムを提案し，その有効性を論じている．
アブスト（英語）
備考（日本語）
備考（英語）
論文原稿
発表資料