無歪み情報源符号化、有歪み情報源符号化、有限長解析

「無歪み情報源符号化」と「有歪み情報源符号化」

データ圧縮は、「無歪み情報源符号化」と「有歪み情報源符号化」に分けられます。無歪み情報源符号化は、もとのデータと復号後のデータが一致するデータ圧縮です。一方で、有歪み情報源符号化は、もとのデータと復号後のデータとの間の違い（歪み）を許容するデータ圧縮です。

有限長解析

伝統的に、情報源符号化の研究では、データの長さが無限に大きくなるという仮定のもとでデータをどこまで圧縮できるかという理論限界が研究されてきました。これに対して、データの長さが有限である等の実用的な仮定のもとでデータ圧縮率の理論限界を研究する「有限長解析」も近年行われています。

有歪み情報源符号化に関する研究

研究例

有歪み情報源符号化の有限長解析において、歪みがある値を超過する確率（歪み超過確率）を一定値以下にしたもとで、データをどこまで圧縮できるかを測る指標の理論限界を解明しました。この研究成果は、情報理論分野で最も権威のある学術雑誌 IEEE Transactions on Information Theory に掲載されました。

S. Saito and T. Matsushima, "Non-Asymptotic Bounds of Cumulant Generating Function of Codeword Lengths in Variable-Length Lossy Compression," in IEEE Transactions on Information Theory, vol. 69, no. 4, pp. 2113-2119, April 2023, doi: 10.1109/TIT.2022.3229358.　リンク

無歪み情報源符号化に関する研究

ベイズ符号の性能解明および効率的な符号化アルゴリズムの開発

情報理論におけるデータ圧縮の研究は、データを発生させる源である情報源の確率分布が既知の場合と、未知の場合に大別されます。ベイズ符号は、情報源の確率分布が未知の場合に動作するデータ圧縮法のひとつであり、情報源の確率分布をベイズ決定理論のもとで最適に推定することでデータの圧縮を行います。

研究例 1

ベイズ符号は、さまざまな評価基準のもとで「良い」性能を示すことを理論的に明らかにしました。

S. Saito and T. Matsushima, "Evaluation of Overflow Probability of Bayes Code in Moderate Deviation Regime," in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E100-A, no. 12, pp. 2728-2731, December 2017, doi: 10.1587/transfun.E100.A.2728.　リンク

S. Saito, N. Miya and T. Matsushima, "Evaluation of the Bayes Code from Viewpoints of the Distribution of Its Codeword Lengths," in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E98-A, no. 12, pp. 2407-2414, December 2015, doi: 10.1587/transfun.E98.A.2407.　リンク

S. Saito, N. Miya and T. Matsushima, "Fundamental limit and pointwise asymptotics of the Bayes code for Markov sources," 2015 IEEE International Symposium on Information Theory (ISIT), Hong Kong, China, 2015, pp. 1986-1990, doi: 10.1109/ISIT.2015.7282803.　リンク

研究例 2

時点によって情報源のモデルが変化する非定常な情報源に対して、効率的なベイズ符号のアルゴリズムを開発しました。

K. Shimada, S. Saito and T. Matsushima, "An Efficient Bayes Coding Algorithm for Changing Context Tree Model," in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E107.A, no. 3, pp. 448-457, March 2024, doi: 10.1587/transfun.2023TAP0017. 　リンク

smooth最大エントロピーを用いた理論限界の特徴付け

研究例 1

オーバーフロー確率という評価基準のもとでのデータ圧縮率の限界が、smooth最大エントロピーという情報量を用いて特徴付けられることを明らかにしました。

S. Saito and T. Matsushima, "Threshold of Overflow Probability Using Smooth Max-Entropy in Lossless Fixed-to-Variable Length Source Coding for General Sources," in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E99-A, no. 12, pp. 2286-2290, December 2016, doi: 10.1587/transfun.E99.A.2286.　リンク

研究例 2

マルチユーザー情報源符号化の代表的な問題の一つであるSlepian-Wolf情報源符号化の2次達成可能レート領域が、smooth最大エントロピーを用いて特徴付けられることを明らかにしました。

S. Saito and T. Matsushima, "Second-Order Achievable Rate Region of Slepian-Wolf Coding Problem in terms of Smooth Max-Entropy for General Sources," in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E99.A, no. 12, pp. 2275-2280, December 2016, doi: 10.1587/transfun.E99.A.2275.　リンク

Guessingに関する研究

情報理論のGuessingという研究分野では、推測問題を数理的に定式化し、理論解析を行います。一例としては、ある値を推測するという試行を繰り返したとき、推測に成功するまでの試行回数の平均について理論解析が行われます。さらに、平均は統計学では1次モーメント（1次の積率）と呼ばれる量であるため、より一般的には、推測に成功するまでの試行回数の$k$次モーメントの理論解析も行われます。従来、推測に成功するまでの試行回数の平均や$k$次モーメントが、ShannonエントロピーやRenyiエントロピー等の情報量によって特徴付けられることが明らかにされています。

研究例

もとデータとそれを推測した結果との間に違いを許したGuessing問題に対して、損失として対数損失を仮定したもとで、推測に成功するまでの試行回数の$k$次モーメントの理論解析を行いました。

S. Saito, "Soft Guessing Under Log-Loss Distortion Allowing Errors," IEEE International Symposium on Information Theory (ISIT), 2024.