1. は じ め に 情報理論は Shannon1)によって 1947 年に創始されて以 降，飛躍的に進歩してきた．この理論は情報をデジタル データとして表現，通信，蓄積するための基礎的な理論 であり，現在のデジタルメディア時代の到来は情報理論 なくしては有り得なかったといっても良い．情報理論に おける基本的な研究分野はデータ圧縮，暗号，誤り訂正 符号の三つであるが，その中でもデータ圧縮はエントロ ピー（情報量）と呼ばれる最も基本的な量によって定式 化され，情報理論の中でも最も重要な研究分野である。 データ圧縮には，大きく分けて無歪みデータ圧縮と有 歪みデータ圧縮が存在する。前者は，与えられたデータ が元々デジタルデータであり，圧縮および伸長を行った 際に元のデータと異なるようなデータが得られては困る ような場合に一般に使用される。これに対して後者の有 歪みデータ圧縮は，音声データや画像データなどのよう に，元々存在する情報がアナログ情報であり，デジタル データを作成した時点で既に歪みが含まれているため， 圧縮・伸長の際に若干の歪みが付加されてもそれ程困ら ない場合に用いられる。本稿では無歪みデータ圧縮につ いて考察する。 情報理論において無歪みデータ圧縮を取り扱う場合に は，情報源からデータが生成されるというモデル化をす るが，特に情報源として確率過程，データとして確率過 程の標本を用いて確率的に取り扱う場合が多い。このと き無歪みデータ圧縮においては，符号語長の期待値が情 報源のエントロピーを下回ることはあり得ないが，符号 化するデータのサイズを十分大きくすることによって， 1シンボルあたりの符号語長の期待値が，1 シンボルあ たりに直した情報源のエントロピーにいくらでも近い符 号を構成することが可能である，という情報源符号化定 理が存在する。このうち，前半を情報源符号化第 2 定 理，後半を情報源符号化第 1 定理と呼ぶ。初期の情報理 論においては，この定理に基づいて，与えられた一つの 情報源に対して圧縮性能が理論的限界になるべく近いよ うな圧縮アルゴリズムが設計されていた。 ところが情報理論の研究が進むにつれて，一つの情報 源に対してその限界を達成できる符号だけでなく，複数 の情報源に対してそれぞれの情報源に対する理論的限界 を一つのアルゴリズムで達成できる，ユニバーサル符号 と呼ばれる定式化が提案されてきた2) 。この性質は，ど のようなデータが出現するか分からない状況でデータ圧 縮を行っている現実の多くの場合には大変重要な性質で あり，なるべく広い情報源クラスに対してユニバーサル 性を満たすような符号の提案とその圧縮性能の解析は， 情報理論における無歪みデータ圧縮の大きなテーマの一 つとなっている。 ユニバーサル符号の例として基本的なものの一つが Lynch–Davisson符号3),4) である。 この符号はその後に提
ユニバーサルデータ圧縮と十分統計量
有 村 光 晴 *
Universal Data Compression and Sufficient Statistic
Mitsuharu ARIMURA*
In this paper we discuss on the data compression from the viewpoint of universal lossless source coding in the area of information theory. Especially we focus on the usefulness of the type (empirical frequency distribution of a given data). From the viewpoint of mathematical statistics, the type has properties of sufficient statistics and maximum likelihood estimator for Bernoulli sequences. Therefore, we show some relationships between these properties and universal data compression. After that, we introduce the notion of asymptotically sufficient statistic, which is an extension of the suffi-cient statistic.
INSTITUTE OF TECHNOLOGY
Vol. 39, No. 1, 2005
*システムコミュニケーション工学科 講師
案されている他の符号に比べて実用性は少ないが，理論 的な取り扱いが極めて簡単であることと，その符号化ア ルゴリズムが使用している経験頻度分布（タイプ）の性 質が情報理論における証明のテクニックとして極めて強 力であるため，情報源符号化定理を証明するのに良く用 いられる符号である。この符号は，まず与えられたデー タのタイプのみを先に符号化する。これだけでは，同じ タイプをもつデータは複数あり，誤りなしで元のデータ を符号から復元することが不可能であるため，さらに， タイプが同じデータの集合の中で与えられたデータを指 定するための情報を符号化する。このような符号を 2 段 階符号と呼ぶ。これまで，Lynch–Davisson 符号の定常無 記憶情報源全体のクラスに対するユニバーサル性の証明 を行う場合には，タイプと経験分布のエントロピー（経 験エントロピー）との関連を用いて証明されるのがほと んどであった。 ところが一方で，統計的推定の立場から経験頻度分布 を眺めると，これは定常無記憶情報源全体のクラスに対 して十分統計量および最尤推定量としての性質をもって いる。そこで，本論文では，この Lynch–Davisson 符号お よび経験頻度分布を対象として，データ圧縮の問題を十 分統計量と最尤推定量を用いて議論する。このような視 点はこれまで情報理論においてデータ圧縮の性能評価を 行なう際には行なわれていなかったものである。タイプ の十分統計量という性質を用いて議論を行なうことによ り，これまでの経験エントロピーを経由するよりも議論 が簡潔になり，タイプの果たす役割がより明確になると いう利点が存在する。 本稿における議論は，筆者らの一連の研究5)–9) への導 入である。本稿ではユニバーサル性の定義として，符号 語長の期待値とエントロピーとの差を 1 シンボルあたり に換算したものが，入力データサイズを大きくしていく と 0 へ収束するという性質を用いているが，筆者らの研 究 に お い て は ， 各 デ ー タ xnに 対 す る 符 号 語 長 と log21/Pq n(xn ) との差を xn に関して最大化した冗長度の定 義を用いることで，本稿で用いた符号語長の期待値によ るユニバーサル性よりも精密な評価が行われている。特 に 9) においては，ユニバーサル符号を構成する二つの代 表的な手法である，マルコフ情報源に対する遷移確率を 推定する方法と，系列をブロックに分割して各ブロック を辞書に登録し，辞書内のインデックスを用いて符号化 する組合せ的な手法の両者を統合したユニバーサル性の 評価手法も得られつつある。本論文ではこれら具体的な 符号の精密な評価については触れずに，入力されるデー タのサイズが大きくなったときの 1 シンボルあたりの符 号語長の期待値の収束先が情報源のエントロピーに近付 くという漸近最良性を持つ符号を，十分統計量を用いて 構成する方法について議論する。 本論文の構成を以下に示す。まず 2 節では，一般の無 歪みデータ圧縮およびユニバーサルデータ圧縮の定式化 を行う。つぎに 3 節において，これまで広く用いられて きた， タイプの経験エントロピーとの関連を用いた Lynch–Davisson符号の符号語長の評価を行う。次に 4 節 でタイプを統計学的な視点から眺めたときに一般に用い られる，十分統計量と最尤推定量という性質を導入し， これらの性質を用いて同じ Lynch–Davisson 符号の符号語 長の評価を行う。最後に 5 節で，このタイプに対する十 分統計量としての性質を拡張した概念として提案されて いる，漸近十分統計量について紹介し，今後の展望を述 べる。 2. ユニバーサルデータ圧縮 本節では情報源符号化定理および情報源符号化のユニ バーサル性について説明する。 まず，記法の説明を行なう。で正整数を表す。{n} n を有限集合の列とし，nを n 上の確率分布全体の集合 とする。確率分布列 Pq{Pqn} n,qQ, Pqnnが qQ によってパラメタライズされているとする。Pq全体の集 合をQdef {Pq}qQと書く。集合 のサイズを || と書 き，文字列 x の長さを ||x|| と書く。また，def k1 k とする。 一般にデータ圧縮は，長さ n の与えられたデータ xn x1x2· · · xnnを 2 進列へと変換する関数 jn:n→{0, 1} によって表現される。このとき，データ xn に対して jn(x n) を xnの符号語と呼び，その長さ ||j n(xn)||を符号語長と 呼ぶ。無歪みデータ圧縮においては，データ xn が異なっ ていれば符号語 jn(xn)も異なっていて欲しい（そうでな いと符号から元のデータを復元できない）。さらに，符 号語を連続して出力した際に，先の符号語を読まなくて も現時点の符号語からデータを復元する（復号）が可能 であった方が都合がよい。そこで，jnに対して各符号 語がそれ以外の符号語の語頭 (prefix) になっていないと いう語頭条件を仮定する。語頭条件を満たす 2 進符号 （語頭符号）jnは Kraft の不等式 (1) x x n n n n ∈
∑
2|| (ϕ )||1ユニバーサルデータ圧縮と十分統計量（有村光晴） を満たす。 ここで，情報理論において最も基本的な量を定義する。 定義 1（エントロピー）．n 次元アルファベットn 上 の確率分布 Pnに従う情報源 Xnに対して，そのエントロ ピーを (2) と定義する。 このとき，Kraft の不等式を満たす符号に関する圧縮 限界は次の定理で与えられる。 定義 1（情報源符号化逆定理 (cf. [11])）．データ xn の生成確率が Pn(xn ) であるような任意の情報源 Xn に対 して，Kraft の不等式を満たすような符号 jnの符号語長 の期待値E[||jn(X n )||] は E[||jn(Xn)||]H(Xn) (3) を満たす。 このように，Kraft の不等式を満たす符号に関しては， その符号語長の期待値が情報源のエントロピーを下回る ことがあり得ない。よって，この限界を漸近的に達成す る場合には，その符号が最良の性能を達成できているこ とになる。この符号語長と情報源のエントロピーとの差 を，符号の冗長度と呼ぶ。特に，情報源が qQ を用い て Xq{Xqn} n, Xq nPqn のようにパラメタライズされて いるとき，その集合{Xq}qQを考えよう。データ xnが情 報源 Xq n の出力である場合に，符号語長 ||jn(x n)|| の期待 値を確率 Pq n で計算することにし，これをEq[||jn(Xq n)||] で表す。情報源の集合全体{Xq}qQで，エントロピーと 符号語長の期待値に関して以下のような性質が成立する 場合には，この符号がとても良い性質を満たしているこ とになる。 定義 2（弱ユニバーサル性）． (4) 定義 3（強ユニバーサル性）． (5) これらユニバーサル性は，ある一つの符号列 jj{jn}n と情報源の集合{Xq}qQが与えられているとき，どの情 報源 Xqから生成されたデータでも，データが十分に大 きければその限界まで圧縮できていることを示す。特に 強ユニバーサル性は，冗長度の 0 への収束の速さが情報 源のパラメータ q によらず一様であることから，ある データサイズ n が与えられている場合にはその符号語長 と圧縮限界との差が情報源によらないことを示している。 これは，各 qQ に対してそれぞれ冗長度が 0 に収束す れば良い弱ユニバーサル性に比べてとても強い性質であ る。これは，実際にどのようなデータを圧縮するか分か らないような現実の世界においては重要な性質であり， 情報理論的な立場からのデータ圧縮の研究においては， 十分に広い情報源クラスに対してユニバーサル性を示す ようなデータ圧縮アルゴリズムを開発することがその重 要な目的の一つとなっている。 もちろんこの性質を満たす符号は対象とする情報源モ デルや処理速度，使用メモリ量などによって様々なもの が存在するが，ここでは以下のような定常無記憶情報源 のクラスに対する情報源符号化順定理を示す。 定理 2（情報源符号化順定理）．有限アルファベット の定常無記憶情報源全体のクラス{Xq}qQ, q{Xqn}n に対して，データ Xqnの符号語長の期待値とエントロピー との差をデータ 1 シンボルあたりに換算した値 が，データサイズ n とともに 0 に近付くユニバーサル符 号{jn}が存在する。 この定理の証明は，具体的な符号を構成し，その符号 語長を評価することによって行なわれる。次節では， Lynch–Davisson符号を用いてこの定理の証明を行なう。 3. タイプと経験エントロピーの関係を用いた Lynch–Davisson 符号の評価 本節では，ユニバーサル符号として最も簡単なアルゴ リズムの一つである Lynch–Davisson 符号について，その アルゴリズムとユニバーサル性の評価方法を述べる。こ の節での証明の方法は，これまで標準的に用いられてき たタイプと経験エントロピーの関係に着目した手法10) を 用いる。 データ xnn が与えられたとき，その中に含まれるシ ンボルの頻度分布を Tn(x n)def{N(a|xn) : a} で表す。ただし，N(a|xn ) はデータ xn の中に現れるシン 1 n nX H X n n {Eθ[||ϕ ( θ)||] ( θ)}
lim sup sup
n n n n n X H X →∞ θ∈Θ θ ϕ θ θ 1 0 {E[|| ( )||] ( )} ∀ →∞ ∈ θ Θ, lim sup θ ϕ θ θ n n n n n X H X 1 0 {E [|| ( )||] ( )} H Xn P a P a a n n n n n n ( )def ( )log2 ( ) ∈
∑
ボル a の個数である。また，各頻度をデータ長 n で割っ たものを のように書く。一般に Pˆn(xn )を xn のタイプと呼ぶが，本 稿では Tn(x n ) もタイプと呼ぶことにする。また，xn とタ イプ Tn(x n ) が同じデータの集合を Sn(x n)defT n1(Tn(x n)) {xˆ:Tn(xˆ n)T n(x n)} と定義する。 Lynch–Davisson符号の符号化アルゴリズムは以下のと おりである。 アルゴリズム 1（Lynch–Davisson 符号）． 1. データ xn に対して，まず Tn(x n ) を 2 値符号化する， 2. Sn(x n ) の中で xn を指定するための情報を 2 値符号 化する。 この符号の圧縮性能を評価する対象の情報源クラスと して，以下のような情報源の集合を考える。 定義 4（定常無記憶情報源）．任意の n および xn n に対して xn の確率 Pq n(xn )が 1 シンボル単位の確率 {pq(a) : a}を用いて (6) と表されるとき，情報源 Xq{Xqn} nは定常無記憶情報 源と呼ばれる。 この符号の性能を評価するために，まず以下の補題を 証明する。 補題 1. |Sn(x n)|2H(Pˆn(xn)) (7) Proof. xnnが定常無記憶情報源 Pˆnからの出力である と仮定する。このとき xn のタイプが Tn(x n ) であるとする と
2ÍaN(a|xn) log
2Pˆn(a)
2nÍaPˆn(a) log
2Pˆn(a) 2nH(Pˆn) が成立する。また，この式の右辺は Pˆn(xn )が同じ xn に対 して同じ値を取る。よって |Sn(x n)|Pˆn(xn) |Sn(xn)|2nH(Pˆ n) となり，(7) 式が示された。 これより，Lynch–Davisson 符号のユニバーサル性を証 明することができる。 定理 2 の証明 各 a に対して N(a|xn ) は 0 から n までの値を取り得る ので，1 段階目のタイプの表現は m log2(n1) m log2(n1)1 ビットの 2 進数で可能である。2 段階目の，同じタイプ の中での与えられたデータの表現は log2|Sn(xn)| nH(Pˆn(xn))1 ビットの 2 進数で可能である。以上で，この符号の符号 語長は ||LDn(xn)||m log2(n1)2nH(Pˆn(xn)) (8) となり，その期待値は Eq[||LDn(Xq n)||]m log2(n1)2nE q[H(Pˆ n(X q n))] のように上から押さえられる。ここで， が成立する。さらに，N(a|Xq, i) は，Xq, ia のときに 1， そうでないときに 0 となるからEq[N(a|Xq, i)]Pr{Xq, ia} であり， となる。したがって，Jensen の不等式から， Eθ[ ˆ ( )]P a Pr{ θ, } Pr{ θ, } n X a X a n i n i i 1 1
∑
Eθ[ ˆ ( )] Eθ θ Eθ θ ( | ) [ ( | ,)] P a N a X n n N a X n n i n i ∑
1 1 ∑ « ∑ « ˆ ( ) ˆ ( ) x T x n n n n n P x ∈∑
1 ˆ ˆ ( ) x n n n n P x ∈∑
∈∏
2N a x( |n)logP aˆ ( )n 2 ˆ ( ) ˆ ( ) ( | ) P xn n P an N a xn ∈∏
P xn n p x p a t t n N a x a n θ( ) θ( ) θ( ) ( | ) 1∏
∏
∈ ˆ ( ) ( | ): P x N a x n a n n n def ∈ ユニバーサルデータ圧縮と十分統計量（有村光晴） H(Xqn) が得られるので，Lynch–Davisson 符号の冗長度は となる。さらに，この式の右辺は q によらないので，左 辺の qQ に関する上界も同じ右辺で押さえられる。さ らに上極限を取ると が成立し，強ユニバーサル性が示された。 4. ユニバーサル符号と十分統計量 前節においては，経験エントロピーの性質を用いて Lynch–Davisson符号の性能を評価した。しかし，タイプ を統計的推定の観点から眺めると，十分統計量や最尤推 定量など，情報理論のデータ圧縮アルゴリズムの評価で は余り用いられることの無い，いくつかの性質が存在す る。本節は 8) の議論に基づき，同じ Lynch–Davisson 符 号の定常無記憶情報源に対するユニバーサル性を従来と は異なった手法で証明する。 4.1 十分統計量 まず，統計的推定の分野で用いられている概念である 十分統計量について述べる12) 。統計的推定を行なう際に， データ xnの値を用いなくても，その関数（これを統計量 と呼ぶ）t(xn ) を用いて q の推定に関して十分な情報を提 供されているときには，この t(xn) のみを用いて統計的推 定を行えば良い。このような統計量の性質を十分性と呼 び，これは以下のように定義される。 定義 5（十分統計量）．Tn(x n ) を統計量とするとき，Tn を与えたときの xnの条件つき確率 P qn(xn|Tn(xn)) が qQ の値に無関係なとき，Tn(x n ) が情報源クラスQに関す る十分統計量であるという。 なお，タイプ（経験頻度分布）は定常無記憶情報源の クラスに対する十分統計量であることが知られている。 これは，(6) から明らかである。 統計量の十分性とデータ圧縮のユニバーサル性は両者 とも，あるクラスに含まれる情報源に関係しない性質を 取り出したものであるから，タイプが与えられたときの データの条件つき確率が，Lynch–Davisson 符号のユニ バーサル性に関連していると考えられる。そこで，この ことをはっきりさせるために，タイプを用いる符号化法 である Lynch–Davisson 符号を，十分統計量の考えを用い て評価する。 4.2 十分統計量を用いた Lynch–Davisson 符号の強 ユニバーサル性 本節では，十分統計量の性質を用いて定理 2 の証明を 行なう。対象とする定常無記憶情報源のクラスをQ {Pq}qQ, Pq{Pqn} nと書く。 まず，各 a に対する N(a|xn ) は 0 から n までの値を 取り，これは log2(n1) bits で表現できるので，第 1 段 階の符号語長は m log2(n1) m log2(n1)m (9) ビットで押さえられる。 第 2 段階の符号語長の評価では，同じタイプとなる系 列の数え上げを行う。定常無記憶情報源においては，確 率 Pq n(xn ) は (6) のようにタイプ Tn(x n ) の関数として与えら れるので，条件つき確率 Pqn(xˆn|Tn(xn))Pqn(xˆn|Tn(xˆn))は xˆnS n(x n )に対して定数となる。よって任意の xnn に対 して (10) が成立する。この性質を用いると第 2 段階の符号語長は (11) で与えらえる。式 (9) および (11) を合わせると，Lynch– Davisson符号の冗長度は次式のように上から押さえられ る； 1 1 n LD xn P x T x n n n n n || ( )|| ( | ( )) log2 θ 1 1 n LD xn P x n n n || ( )|| ( ) log2 θ ∑ « log2| ( )| log2 ( | ( )) S x P x T x n n n n n n 1 1 θ | ( )| ( | ( )) S x P x T x n n n n n n 1 θ ∑ « ∑ «
lim sup sup
n n n n n LD X H X →∞ θ∈Θ θ θ θ 1 0 {E [|| ( )||] ( )} 1 1 2 n LD X H X m n n n n n {Eθ[|| ( θ)||] ( θ)} log2( ) Pr{Xθ,i a}log2Pr{Xθ,i a} ∈
∑
Eθ[ ˆ ( )]P an log2Eθ[ ˆ ( )]P an ∈∑
Eθ[P aˆ ( )n P aˆ ( )]n a log2 ∈∑
Eθ[ ( ˆ (H P Xn θn))] P aˆ ( )n P aˆ ( )n∑
∈ log2(12) なお，この上界は"qQ, "n1, "xnn に対して成立する。 式 (12) を用いると，この符号の強ユニバーサル性は次 のように証明できる。両辺の期待値を取ると が成立する。この式の右辺は q によらないので，左辺の q に関する上界を取ったものは同じ右辺で押さえられ， 上極限を取ると が成立する。 ここで重要なのが，(10) 式の十分性である。これは Lynch–Davisson符号の 2 段階目の符号語長の評価のため に用いられるという点で補題 1 と同様の道具であるが， この式を用いたユニバーサル性の証明は，期待値の性質 や凸関数の性質などを全く用いておらず，補題 1 を用い た証明よりも全体として簡潔な証明になっていることが 分かる。 ただし，Lynch–Davisson 符号のユニバーサル性を証明 するにはタイプの十分統計量としての性質を用いるだけ では不十分である。それは，Tn(x n)xn として定義される データそのものも，実は十分統計量であるからである。 このようにして定義した十分統計量を用いて 2 段階符号 を構成した場合には，2 段階符号によってデータを全く 圧縮することができない。よって，2 段階符号のユニバー サル性を示す際には，1 段階目の符号語長が十分に小さ くなることも必要な条件となる。 4.3 経験エントロピーと最尤推定量との関係 前節においては，タイプの十分統計量としての性質を 用いることで，Lynch–Davisson 符号の強ユニバーサル性 の証明を，従来のタイプと経験エントロピーの関係を用 いるよりも簡単に行なうことができた。これは，従来の 評価においては補題 1 を用いていたのが，タイプの十分 統計量という性質から導かれる (10) 式を用いて評価した ことによる。ただし，これら 2 種類の評価は全然別のも のではなく，以下のタイプの最尤推定量としての性質を 用いることで，お互いの関連を見ることができる。 まず，(12) の右辺は q に依存しないので左辺の q に関 する上界を取ったものに対しても同じ不等式が成立する。 さらに，符号語長は q に依存しないので，次式が成立す る； . また，定常無記憶情報源のクラスと任意の xn において は，経験エントロピーに関して次式が成立する； . (13) これはタイプが定常無記憶情報源のクラスに関して最尤 推定量であることを示している。この関係を用いると， Lynch–Davisson符号の経験エントロピーに対する冗長度 の上界を のように求めることができるが，この式は (8) と同じ式 である。 以上で，Lynch–Davisson 符号の符号語長の評価におい ては，タイプの十分統計量や最尤推定量としての性質が 関連していることを見ることができた。また，これらの 性質を積極的に用いることで，より簡単な冗長度の評価 が可能であることが分かった。 5. 漸近十分統計量への拡張 前節において，Lynch–Davisson 符号の定常無記憶情報 源のクラスに対する冗長度の評価を，タイプが同じ情報 源クラスに対する十分統計量であるという性質を用いて 行なった。タイプを用いたこの方法論は定常無記憶情報 源のクラスに対して有効であるものの，一般の記憶のあ る情報源クラスに対して用いることはできない。それは， タイプがそれらの情報源クラスに対しては十分統計量で はないからである。そこで本節では十分統計量の性質を 拡張することで得られる漸近十分統計量という性質を紹 介する5)–9)。 定義 6（ ゼロレート性）． 関数 fn: n→n に対して Rn1( fn) を R f n n n 1( )def1 | | 2 log 1 1 1 n LD x H P x m n n m n n n n n {|| ( )|| ( ˆ ( ))} log2( )
inf log2 inf
θ∈Θ θ θ∈Θ θ 1 P xn n D P P H P H P n n n n ( ) ( ˆ || ) ( ˆ ) ( ˆ ) sup log2 θ∈ θ Θ 1 1 n LD xn P x n n n || ( )|| ( ) 1 1 n LD xn P x n n n || ( )|| ( ) inf log2 θ∈ θ Θ
lim sup sup
n n n n n LD X H X →∞ θ∈Θ θ θ θ 1 0 {E [|| ( )||] ( )} 1 1 1 n LD X H X m n n m n n n n {Eθ[|| ( θ)||] ( θ)} ( ) log2 m n n m n log2( 1) 1
ユニバーサルデータ圧縮と十分統計量（有村光晴） と定義する。このとき fnは全射であると仮定しておく。 関数列 f{ fn}nが を満たすとき，f はゼロレートであると言う。 定義 7（漸近十分性）．関数 fn: n→n と条件つき確 率 Pq n, Qn に対して Rn 2( f n, Pq n, Qn ) を と定義する。関数列 f{ fn}n, fn:n→nと情報源クラ スQ{Pq}qQに対して，もし q に依存しない条件つき 確率分布の列{Qn( ·|· )} nが存在し，"ynn, Qn( ·|yn) nおよび (14) を満たすとき，f は情報源クラスQに関して漸近十分 であると言う。 上記の定義において，任意の n および xn で R2 n( fn, Pq n, Qn)0 とした条件は，各 n において f nが{Pq n} qQに 対する十分統計量であることを示しているので，この漸 近十分性は十分性の自然な拡張となっていることが分か る。 次の定理は，上記のゼロレート性かつ漸近十分性を満 たすような統計量が存在する場合には，必ず弱ユニバー サルな符号が存在することを保証するものである。 定理 3．エントロピー H(Xq n) が任意の n で有限で あるような任意の情報源クラスQ{Pq}qQを考える。 もし関数列{ fn}nが存在し，これがゼロレートかつQ に関して漸近十分であるとすると，Qに関して弱ユニ バーサル性を満たす 2 値語頭符号が存在する。 Proof.関数列{ fn}nがゼロレートであるという仮定よ り，十分大きい n に対して |n| は有限となる。また， { fn}nの漸近十分性より，q に依存しない条件つき確率 分布の列{Qn( ·|· )} nが存在する。これらの値を用いる と，q によらない確率分布を のように定義することができる。この確率分布を用いる と語頭符号である Shannon–Fano 符号{jn}nを構成する ことができ，その符号語長は となる。この符号語長は不等式 (15) を満たす。ただし，一つ目の不等号は Pqn(xn)Pqn(xn, f n(x n)) Pqn( f n(xn))Pqn(xn| fn(xn)) Pqn(xn| f n(x n)) を用いた。(15) にゼロレート性と漸近十分性を適用する と が成立する。従ってこの符号の冗長度は 0 を満たし，弱ユニバーサル性が示された。 この証明は，漸近十分統計量が存在すれば弱ユニバー サル符号が存在するという存在定理だけでなく，漸近十 分統計量が存在すればそれを 1 段階目で用いる次のよう な符号によって弱ユニバーサル符号を具体的に構成でき ることも示している。 まず与えられたデータ xn に対して，統計量 ynfn(x n ) を 固定長 log2|n| ビットで符号化する。さらに，関数 fn( · ) の出力として ynを与えるような集合 fn1(yn) def {x˜n| f n(x˜ n) yn}の中からデータ x n を示す情報を log2(1/Qn(xn|f n(x n))) ビットで符号化する。特に実際の実用的な 2 段階圧縮ア ルゴリズムにおいては，2 段階目の符号語長として一様 ∑ «
lim sup max log2
n x n n n n n nn x P x →∞ ∈ 1 1 || ( )|| ( ) ϕ θ lim sup n n n n n X H X →∞ 1 {Eθ[||ϕ ( θ)||] ( θ)}
lim sup max log2
n x n n n n n n n x P x →∞ ∈ 1 1 0 || ( )|| ( ) ϕ θ 1 1 1 n n P x f x Q x f x n n n n n n n n n n
log2| | log log2 2
( | ( )) ( | ( )) θ 1 1 1 n Q x f x P x f x n n n n n n n n n log2 log2 | | ( | ( )) ( | ( )) θ 1 1 n nx P x f n n n n n n || ( )|| ( | ( )) ϕ θ log2 1 1 n nx P x n n n || ( )|| ( ) ϕ θ log2 || ( )|| | ( | ( )) ϕn n n n n n n x Q x f x log2 ˆ ( ) ( | ( )) | | P xn n Q x f x n n n n n def ∀ →∞ ∈ ∈
θ Θ, lim sup max θ
n x n n n n nnR2(f P Q, , )0 R f P Q n P x f x Q x f x n n n n n n n n n n n n 2( , , ) 1 ( | ( )) ( | ( )) θ def log2 θ lim n→∞R fn n 1( )0
な符号語長が用いられている場合が多い。この定理をそ のようなアルゴリズムに適用するには，Qn(xn| f n(xn)) を Qn(xn| f n(x n)) def と設定すれば良い。このようにした符号の符号語長は ||jn(x n)|| log2|n| log2|S n(x n)| と計算される。上記のようにして構成した符号の弱ユニ バーサル性は，定理 3 によって直接示すことができる。 6. お わ り に 本論文では，定常無記憶情報源に対する情報源符号化 定理の一つとして Lynch–Davisson 符号の符号語長の評価 を紹介した。その際，経験頻度分布（タイプ）の性質に 着目し，これまで行なわれてきた経験エントロピーを経 由する議論を述べると共に，著者らの研究で行われてい るタイプの十分統計量としての性質を用いた評価方法を 新しく紹介し，これら 2 種類の評価の関係について議論 した。さらに，十分統計量という性質を記憶のある情報 源にも拡張する新しい性質として，統計量のゼロレート 性と漸近十分性という新しい性質を定義し，この両方の 性質を満たす統計量が存在すれば，弱ユニバーサルな無 歪みデータ圧縮アルゴリズムが存在することを証明した。 今後の研究課題としては，現実に用いられている各種 の符号の様々なデータに対する符号化性能を，この手法 を用いて評価することが挙げられる。さらに，与えられ た圧縮したいデータの種類（クラス）に対して十分統計 量や漸近十分統計量を設計することによって，そのデー タに適した圧縮アルゴリズムを設計するための指針を提 案できればと考えている。 参 考 文 献
1) Claude E. Shannon, “A Mathematical Theory of Commu-nication,” Bell Systems Technical Journal, Vol. 27, pp. 379–423, July, pp. 623–656, Oct. 1948.
2) Lee D. Davisson, “Universal Source Coding,” IEEE
Transactions on Information Theory, Vol. IT-19, No. 6,
pp. 783–795, Nov. 1973.
3) T. J. Lynch, “Sequence Time Coding for Data Compres-sion,” Proceedings of the IEEE, Vol. 54, pp. 1490–1491, 1966.
4) Lee D. Davisson, “Comments on ‘Sequence Time Coding for Data Compression,’ ” Proceedings of the IEEE, Vol. 54, p. 2010, 1966.
5) 有村光晴，長岡浩司，“弱ユニバーサルな FV 情報
源符号の存在条件について，”第 25 回情報理論とそ
の応用シンポジウム予稿集 (SITA2002)，伊香保， 2002.
6) Mitsuharu Arimura and Hiroshi Nagaoka, “General Con-ditions for Existence of Weakly Universal FV Source Codes,” Proc. of 2003 IEEE International Symposium on
Information Theory (ISIT2003), Yokohama, 2003.
7) 有村光晴，長岡浩司，“FV 情報源符号の個別弱ユ
ニバーサル性と個別漸近十分統計量，”第 1 回シャ ノン理論ワークショップ予稿集 (STW2003)，草津， 2003.
8) Mitsuharu Arimura and Hiroshi Nagaoka, “Asymptoti-cally Sufficient Statistic Method for Evaluation of Point-wise Redundancy of FV Source Codes,” Proc. 2004
Inter-national Symposium on Information Theory and Its Ap-plications (ISITA2004), Parma, 2004.
9) 有村光晴，長岡浩司，“十分統計量と強ユニバーサ ル情報源符号化，”第 27 回情報理論とその応用シン ポジウム予稿集 (SITA2004)，下呂，2004. 10) 植松友彦，現代シャノン理論，培風館，1998. 11) 韓 太舜，小林欣吾，情報と符号化の数理，培風 館，1999. 12) 中村隆英，新家健精，美添泰人，豊田 敬，統計 入門，東京大学出版会，1984. ∑ « ∑ « 1 |S xn( )| n
