近年の通信ネットワークの発達に伴い,動画などの大規模なデータを高速に伝送する必要が高まっている.通常の通信路を介してデータを伝送する場合には,データ圧縮技術を使ってデータのもつ冗長性を取り除くことによって,効率的なデータ伝送が可能になる.特に画像や音声のデータは,元のデータと再生されるデータに許容できる程度の歪を許せば,より高いデータ圧縮率を得ることができる.本論文ではこの歪を許す符号化をレート・歪理論の立場から考察する.

　定常エルゴード的な情報源を歪を許して圧縮するとき,符号化によって達成可能なデータの圧縮率はレート・歪関数と呼ばれる歪の関数になる.レート・歪関数を漸近的に達成するブロック符号の存在は,情報源符号化定理によって保証される.ところが,情報源符号化定理は一般に広い情報源のクラスに対して構成的でない形で証明されるので,漸近的にレート・歪関数を達成する符号の実体が明確でない.本論文では離散無記憶情報源とガウス性無記憶情報源の2つの情報源クラスに対して,漸近最良性をもつ符号化法のもつ性質を明らかにするとともに,その符号化法をユニバーサルな形で実現する方法について議論する.

　この章ではガウス性無記憶情報源に対するブロック符号化法を提案し,情報源の平均と分散が既知,未知の各場合に符号化法のもつ漸近的な特性を解析する.情報源が既知の場合は一般性を失うことなく平均0,分散1を仮定できる.情報源が出力する系列の長さnのブロックをx＝(x₁,x₂,…,x_n)^Tで表すとき,そのユークリッドノルム||x||₂がスカラー量子化器によって,x/||x||₂がn次元単位超球S^n-1上の点集合Y＝{y₁,y₂,…,y_M}によってそれぞれ符号化される.符号化は以下の写像＝(₁,₂)によって定義される.

　ここでarg は内積〈x,y〉を最大にする引数を表し,A＝{a₁,a₂,…,a_L},C＝{c₁,c₂,…,c_L}は0＝a₁c₁2c₂<…Lc_Lを満たすスカラー量子化器を記述するパラメータである.xと(x)の間の歪d_n(x,(x))は1シンボルあたりの二乗誤差で定義し,歪の集合平均をと書いて平均歪と呼ぶ.xはc_l,y_mの添字を復号器側に伝えることによって伝送され,この符号化に必要なレートは1シンボルあたりR＝Mビットである.また,分散1のガウス性無記憶情報源に対するレート・歪関数はD∈(0,1]に対してと書ける.Mを任意に固定した歪水準∈(0,1)に対して)と定め,A,Cが次の3条件

　1)任意に固定した>0に対して

　2)はを満たす.

　3)Lはnの多項式のオーダーである,

　を満たすとき,漸近的な特性が

　で表される漸近最良な符号化が行えることが証明できる.この符号化法では漸近的な特性は主にスカラー量子化器によって決定される.

　上記の符号化法は2パス符号化によって平均または分散が未知の情報源に対しても拡張できる.未知パラメータはある既知の有界領域に属するという仮定をおくと,情報源ブロックxと(x)の間の歪が歪水準を越えない確率は,既知情報源と未知情報源のいずれの場合にも漸近的に1に近づく.この性質を満たすために必要なレートは既知情報源の場合は1シンボルあたりMビット,未知情報源の場合はさらに未知パラメータ1つあたりビット,加えて分散が未知の場合にはビットが余分に求められる.

　1977年に発表されたLempel-Ziv符号は定常エルゴード的な情報源に対して漸近的にエントロピーを達成する.いまを有限アルファベットAに値をとる定常エルゴード的な確率変数列,をXの実現値,PをXの確率測度とし,任意のijに対してと定める.正整数nに対して正整数M_n(x)を

　と定義すると,(x)はエントロピーに確率収束し,この事実はLempel-Ziv符号の1つの理論的基盤を与えている.この章では適当な歪測度d_nと任意に固定した歪水準のもとで定義される系列の有歪再帰時間

　がレート・歪関数に確率収束する十分条件を,離散無記憶情報源とガウス性無記憶情報源の2つの情報源クラスについて導出し,その結果自然に導かれる符号化法についての議論を行う.

　最初にアルファベットA＝{a₁,a₂,…,a_J}をもつ離散無記憶情報源を考察する.A上の確率分布をpで表し,j＝1,2,…,Jに対してp(a_j)>0を仮定する.d:A×A→[0,∞)をd(a_j,a_k)＝0(j＝k),d(a_j,a_k)>0(j≠k)を満たす1シンボルあたりの歪測度とし,ブロック,∈Aⁿ間の歪d_nを文脈自由の形で定義する.この情報源に対するレート・歪関数をR(p,D)と書く.歪水準に対応する試験通信路行列をW^*と書き,

　で定まるA上の確率分布をp^*と記す.このとき,任意の>0に対してM_n(X,)は次の性質を満足する.

　ここにD(p^*||p)はダイバージェンスである.また,qをp^*(a_j)>0なるすべてのa_j∈Aに対してq(a_j)>0を満たすA上の任意の確率分布とすると,任意の>0に対して

　が成り立つことも示される.Qはqから導かれるXの確率測度,P_|i,j|は確率測度のへの制限である.特にq＝p^*のときは(X,)はレート・歪関数R(p,)に確率収束することが証明できる.式(8),(9)は.符号器と復号器で確率分布p^*に従う系列をデータベースとして共通に保持すれば,長さnのブロックの伝送に必要なレートはnが十分大きいときには1シンボルあたりR(p,)程度必要なこと,またデータベースの確率分布がqであればD(p^*||q)がレートの冗長度になることを主張している.

　次に平均0,分散²のガウス性無記憶情報源を対象とする.情報源アルファベットAは実数Rに等しく,u,∈Aに対して歪測度dをd(u,v)＝(u-v)²,ブロック間の歪を文脈自由の形で定める.歪水準∈(0,²)を任意に1つ固定し,u∈Aⁿに対してB_n(u,)を

　とおくと,(X,)は系列の測度Pのもとでレート・歪関数に確率収束する.この事実は符号器と復号器がともに平均と分散が既知のガウス性の独立な系列を保持すれば,nが十分大きいときには長さnのブロックがレート・歪関数程度のレートで伝送できることを意味する.

　情報源が離散無記憶のとき,与えられた歪水準に対応する試験通信路行列から決まる情報源アルファベット上の確率分布p^*は,式(9)で見たように有歪符号化において重要な役割を果たす.この章ではp^*の一意性の仮定のもとで,2種類のp^*のユニバーサルな推定アルゴリズムを提案し,推定に必要なサンプル数を評価する.

　有限アルファベットA＝{a₁,a₂,…,a_J}をもつ情報源の確率分布をpで表す.推定アルゴリズムはq(a_j)>0,j＝1,2,…,Jを満たす確率分布qの補助情報源の出力が利用できると仮定する.最初の推定アルゴリズムは情報源の長さnのL個のブロックX＝{x₁,x₂,…,x_L}と補助情報源の長さnのM個のブロックY＝{y₁,y₂,…,y_M}を使ってp^*の推定値を出力する.歪は前章と同様に定義する.推定アルゴリズムには,任意に固定した>0と∈(0,1)に対して

　を満たすという規範を課す.上式のProbはX×Yに関する確率を表す.規範(12)を満たす確率分布を使うと,式(6)で定義したM_n(x,)は任意の>に対して

　を満たす.ここにはに対応する確率測度である.すなわち,規範(12)は歪を許容してデータを圧縮するときのレートの冗長度を以下にするという意味をもつ.

　この推定アルゴリズムは,任意に固定した_e∈(0,]に対してを満たすpの推定値をもつことを仮定する.また与えられたX,Yに対して,

　と定義する.∈(0,_e)は任意に選んだ定数,t(x)はxのタイプ,||・||₁はノルムである.推定アルゴリズムは以下の手順でp^*を推定する.

　この推定アルゴリズムが実際に規範(12)を満たすを出力するための,nの下限をとの関数として導出した.R_Xの下限は相互情報量,R_Yの下限はダイバージェンスを使って表現され,任意に与えられた>0に対してととればよいことが証明できた.また,規範(12)は計算論的学習理論におけるPAC学習モデルと同種のモデルであり,シャノン理論とPAC学習モデルに内在する関係を初めて明らかにしたという意味をもっている.

　同様の問題設定のもとで,2番目の推定アルゴリズムは情報源からX＝{x₁,x₂,…,x_L}を,補助情報源からを得てp^*の推定値を出力する.最初の推定アルゴリズムとは,Yの要素を1つ記憶するためのメモリがあればよいという点で大きく異なる.この推定アルゴリズムは,としてアルゴリズム中のパラメータを適当に選べば,任意の推定精度をもつが高い確率で得られ,がつ確率1で停止することが示される.