音声を電話で伝えるとき、どれだけデータを圧縮すれば十分な音質が保てるでしょうか。画像をJPEGで保存するとき、ファイルサイズと画質のトレードオフはどう決まるのでしょうか。これらの問いに対する根本的な回答を与えるのがレート歪み理論（rate-distortion theory）です。
シャノンの源符号化定理は、無損失圧縮の限界がエントロピーで与えられることを示しました。しかし、実用的な圧縮の多くは非可逆圧縮（lossy compression）であり、ある程度の歪み（distortion）を許容する代わりに、エントロピーよりも低いレート（ビット数）で圧縮することができます。レート歪み理論は、許容する歪みのレベルに対して達成可能な最小ビットレートを厳密に定めます。
- 通信工学: デジタル音声・映像の圧縮限界を理論的に予測します
- データ圧縮: JPEG, MP3, H.264などの圧縮アルゴリズムの理論的な性能指標です
- 機械学習: 情報ボトルネック法（Information Bottleneck）はレート歪み理論の拡張です
- 統計学: 最小記述長原理（MDL）との関連があります
本記事では、レート歪み関数の定義と基本性質を解説し、ガウス情報源やバイナリ情報源の場合の閉じた式を導出します。
本記事の内容
- 非可逆圧縮の基本的な枠組み
- 歪み関数とレート歪み関数の定義
- レート歪み定理の主張
- ガウス情報源のレート歪み関数
- バイナリ情報源のレート歪み関数
- Pythonによる数値計算と可視化
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 交差エントロピーとKLダイバージェンスの関係 — 相互情報量とKLダイバージェンス
- エントロピー — シャノンエントロピーの基礎
非可逆圧縮の枠組み
無損失圧縮と非可逆圧縮
無損失圧縮（lossless compression）では、圧縮したデータを完全に元に戻せます。シャノンの源符号化定理により、圧縮の限界はエントロピー $H(X)$ ビット/シンボルです。
非可逆圧縮（lossy compression）では、ある程度の情報損失（歪み）を許容する代わりに、$H(X)$ よりも少ないビット数で圧縮できます。日常的に使われるJPEG（画像）、MP3（音声）、H.264（動画）はすべて非可逆圧縮です。人間の知覚特性を利用して、知覚できない範囲の情報を捨てることで、劇的なデータ量の削減を実現しています。
非可逆圧縮で重要なのは、どれだけの歪みを許容すれば、どれだけ圧縮できるかというトレードオフの関係です。歪みを多く許容すれば少ないビットで済みますが、品質は低下します。逆に高品質を維持しようとすればビットレートが増大します。レート歪み理論は、このトレードオフの理論的限界——いかなる圧縮アルゴリズムを使っても越えられない壁——を厳密に定量化します。
歪み関数
情報源のアルファベットを $\mathcal{X}$、再構成のアルファベットを $\hat{\mathcal{X}}$ とします。歪み関数（distortion function）$d: \mathcal{X} \times \hat{\mathcal{X}} \to [0, \infty)$ は、元のシンボル $x$ と再構成されたシンボル $\hat{x}$ の間の「ずれ」を測る量です。
歪み関数の選び方は応用に依存します。代表的なものを2つ紹介しましょう。
二乗歪み（squared error distortion）: $d(x, \hat{x}) = (x – \hat{x})^2$
二乗歪みは連続値の情報源で最もよく使われる歪み関数です。信号処理ではMSE（平均二乗誤差）に対応し、数学的に扱いやすい性質を持ちます。
ハミング歪み（Hamming distortion）: $d(x, \hat{x}) = \begin{cases} 0 & x = \hat{x} \\ 1 & x \neq \hat{x} \end{cases}$
ハミング歪みは離散情報源で使われ、シンボルが正しく再現されたかどうかだけを問います。平均ハミング歪みはシンボル誤り率に等しくなります。
長さ $n$ の系列 $x^n = (x_1, \dots, x_n)$ と $\hat{x}^n = (\hat{x}_1, \dots, \hat{x}_n)$ の間の平均歪みは、
$$ d(x^n, \hat{x}^n) = \frac{1}{n}\sum_{i=1}^n d(x_i, \hat{x}_i) $$
で定義されます。
レート歪み関数の定義
レート歪み関数 $R(D)$ は、平均歪み $D$ 以下を達成するために必要な最小ビットレートです。
形式的には、$X$ と $\hat{X}$ の同時分布 $p(x, \hat{x}) = p(x)p(\hat{x}|x)$ に対して、
$$ \begin{equation} R(D) = \min_{\substack{p(\hat{x}|x) : \\ E[d(X, \hat{X})] \leq D}} I(X; \hat{X}) \end{equation} $$
ここで $I(X; \hat{X})$ は $X$ と $\hat{X}$ の間の相互情報量です。
$$ I(X; \hat{X}) = H(X) – H(X | \hat{X}) = \sum_{x, \hat{x}} p(x, \hat{x}) \log \frac{p(x, \hat{x})}{p(x)p(\hat{x})} $$
直感的には、$R(D)$ は「歪み $D$ 以下で情報源を再現するために、少なくとも保存しておかなければならない情報量」です。相互情報量 $I(X; \hat{X})$ は $X$ と再構成 $\hat{X}$ の間でどれだけの情報が共有されているかを測る量であり、これを最小化することは「必要最小限の情報だけを保持する」最も効率的な圧縮に対応します。制約が $E[d(X, \hat{X})] \leq D$ であるため、歪みを $D$ 以下に抑えながら情報を最も少なく保持する方法を探す問題です。
符号の定義
レート歪み理論を厳密に述べるために、まず符号の概念を定義しましょう。$(2^{nR}, n)$ レート歪み符号は、以下の2つの写像の組です。
符号化器（encoder）: $f_n: \mathcal{X}^n \to \{1, 2, \dots, 2^{nR}\}$
情報源系列 $x^n = (x_1, \dots, x_n)$ を $2^{nR}$ 個のインデックスの一つに写像します。このインデックスが圧縮されたデータに対応します。
復号器（decoder）: $g_n: \{1, 2, \dots, 2^{nR}\} \to \hat{\mathcal{X}}^n$
インデックスから再構成系列 $\hat{x}^n$ を生成します。
符号のレートは $R$（ビット/シンボル）であり、平均歪みは $E[d(X^n, g_n(f_n(X^n)))]$ です。
レート歪みの対 $(R, D)$ が達成可能（achievable）であるとは、任意の $\epsilon > 0$ に対して、十分大きな $n$ で平均歪みが $D + \epsilon$ 以下となる $(2^{nR}, n)$ 符号が存在することです。
ここまでで符号化・復号の枠組みが整いました。次に、この枠組みのもとでレート歪み関数がどのような役割を果たすかを、シャノンのレート歪み定理として述べましょう。
レート歪み定理
定理の主張
シャノンのレート歪み定理（Shannon’s rate-distortion theorem, 1959）: i.i.d.情報源 $X_1, X_2, \dots$ に対して、レート歪みの対 $(R, D)$ が達成可能であるための必要十分条件は $R \geq R(D)$ である。
より詳しく述べると、
順定理（achievability）: $R > R(D)$ ならば、十分長いブロック長 $n$ に対して、レート $R$ で平均歪み $D + \epsilon$ 以下を達成する符号が存在します。
逆定理（converse）: $R < R(D)$ ならば、いかなるブロック長 $n$ の符号も、平均歪み $D$ を達成することはできません。
順定理の証明の直感
順定理の証明はランダム符号化の手法に基づきます。そのアイデアを直感的に説明しましょう。
$R(D)$ の最適解を達成する条件付き分布 $p^*(\hat{x}|x)$ が得られたとします。この分布に従って $2^{nR}$ 個の再構成系列 $\hat{x}^n(1), \dots, \hat{x}^n(2^{nR})$ をランダムに生成します。これが符号帳（codebook）です。
情報源系列 $x^n$ が生成されたとき、符号帳の中から $x^n$ との歪みが $D + \epsilon$ 以下となるエントリを探します。$R > R(D)$ であれば、$n$ が十分大きいとき、高い確率でそのようなエントリが見つかることが典型系列の議論から示されます。
これは通信路符号化定理の「逆向き」の議論に対応しています。通信路符号化定理では符号語の中から受信信号に「近い」ものを探しますが、レート歪み定理では再構成系列の中から情報源系列に「近い」ものを探します。
逆定理の証明の概略
逆定理は情報量の連鎖を追うことで示されます。任意の $(2^{nR}, n)$ 符号に対して、
$$ nR \geq H(M) \geq I(X^n; \hat{X}^n) = \sum_{i=1}^n I(X_i; \hat{X}_i | \text{past}) \geq \sum_{i=1}^n I(X_i; \hat{X}_i) $$
ここで $M = f_n(X^n)$ は符号化されたインデックスです。最後の不等式はデータ処理不等式と独立性から従います。
各 $I(X_i; \hat{X}_i) \geq R(D_i)$（$D_i = E[d(X_i, \hat{X}_i)]$）であり、$R(D)$ の凸性から、
$$ R \geq \frac{1}{n}\sum_{i=1}^n R(D_i) \geq R\!\left(\frac{1}{n}\sum_{i=1}^n D_i\right) = R(\bar{D}) $$
$\bar{D} \leq D$ ならば $R \geq R(D)$ が得られます。
レート歪み関数の基本性質
上記の定理を支える $R(D)$ は以下の性質を持ちます。
- 単調非増加: $D$ が大きいほど（歪みを多く許容するほど）必要なレートは減少します。これは直感的に明らかです——品質を落としてよいなら、より少ないビットで済みます
- 凸関数: $D$ の凸関数です。これはタイムシェアリング（時分割）の議論から従います。2つのレート歪みの対 $(R_1, D_1)$ と $(R_2, D_2)$ が達成可能であれば、時間を分割してそれぞれの符号を使うことで、凸結合 $(\lambda R_1 + (1-\lambda)R_2, \lambda D_1 + (1-\lambda)D_2)$ も達成できます
- $R(0) = H(X)$（離散情報源の場合）: ゼロ歪みでは完全な再現が必要であり、これは無損失圧縮に相当します。必要なレートはシャノンエントロピーです
- $R(D_{\max}) = 0$: $D_{\max} = \min_{\hat{x}} E[d(X, \hat{x})]$ は、何も伝えずに固定値で再現したときの歪みです。この歪みを許容するなら、ビットを送る必要はありません
これらの性質から、$R(D)$ は $D = 0$ の $H(X)$ から $D = D_{\max}$ のゼロまで凸に減少する曲線です。
ここまでで一般的な枠組みを理解しました。次に、閉じた形（解析解）が得られる代表的な情報源について、レート歪み関数を具体的に計算しましょう。
ガウス情報源のレート歪み関数
問題の設定
情報源が $X \sim N(0, \sigma^2)$（平均0, 分散 $\sigma^2$ のガウス分布）であり、歪み関数が二乗歪み $d(x, \hat{x}) = (x – \hat{x})^2$ の場合を考えます。
解の導出
レート歪み関数の定義に基づき、$I(X; \hat{X})$ を $E[(X – \hat{X})^2] \leq D$ の制約のもとで最小化するラグランジュ最適化問題を解きます。
ラグランジアンは、
$$ \mathcal{L}[p(\hat{x}|x)] = I(X; \hat{X}) + s\left(E[(X – \hat{X})^2] – D\right) $$
です。ここで $s \geq 0$ はラグランジュ乗数です。
最適解を求めるために、$\hat{X}$ の最適な形を考えます。$X$ と $\hat{X}$ の関係を $\hat{X} = \alpha X + N$（$N$ は $X$ と独立なノイズ）と仮定し、$\alpha$ と $N$ の分布を最適化します。
歪み制約は、
$$ E[(X – \hat{X})^2] = E[(X – \alpha X – N)^2] = (1-\alpha)^2 \sigma^2 + \text{Var}(N) = D $$
です。相互情報量は、
$$ I(X; \hat{X}) = h(\hat{X}) – h(\hat{X}|X) = h(\hat{X}) – h(N) $$
ここで $h(\cdot)$ は微分エントロピーです。分散を固定したとき微分エントロピーを最大化するのはガウス分布ですので、$h(\hat{X})$ はガウスの場合に最大化され、$I(X; \hat{X})$ を最小化するには $h(\hat{X})$ を最小化し $h(N)$ を最大化する必要があります。$N$ がガウスのとき $h(N)$ は最大であり、$X$ がガウスで $N$ がガウスなら $\hat{X}$ もガウスです。
$\text{Var}(N) = D – (1-\alpha)^2\sigma^2$ とすると、$\text{Var}(\hat{X}) = \alpha^2 \sigma^2 + \text{Var}(N) = \alpha^2 \sigma^2 + D – (1-\alpha)^2 \sigma^2 = (2\alpha – 1)\sigma^2 + D$ です。
$I(X; \hat{X})$ を $\alpha$ で最小化すると、$\alpha^* = 1 – D/\sigma^2$ が得られます（$D \leq \sigma^2$ のとき）。このとき、
$$ \text{Var}(N) = D – \frac{D^2}{\sigma^2}, \quad \text{Var}(\hat{X}) = \sigma^2 – D $$
相互情報量は、
$$ I(X; \hat{X}) = \frac{1}{2}\log\frac{\text{Var}(\hat{X})}{\text{Var}(N)} = \frac{1}{2}\log\frac{\sigma^2 – D}{D(1 – D/\sigma^2)} = \frac{1}{2}\log\frac{\sigma^2}{D} $$
別の導出として、$h(X) – h(X|\hat{X})$ の形からも同じ結果が得られます。最適な条件のもとで $X|\hat{X}$ は分散 $D$ のガウス分布となり、
$$ I(X; \hat{X}) = \frac{1}{2}\log(2\pi e \sigma^2) – \frac{1}{2}\log(2\pi e D) = \frac{1}{2}\log\frac{\sigma^2}{D} $$
したがって、ガウス情報源のレート歪み関数は次のようになります。
$$ \begin{equation} R(D) = \begin{cases} \frac{1}{2}\log\frac{\sigma^2}{D} & 0 \leq D \leq \sigma^2 \\ 0 & D > \sigma^2 \end{cases} \end{equation} $$
結果の解釈
この結果には深い意味があります。
$D = 0$（歪みなし）では $R = \infty$ です。連続情報源を完全に無損失で表現するには無限のビットが必要という当然の結果です。
$D = \sigma^2$ では $R = 0$ です。何も伝えず $\hat{X} = 0$（平均値）と推定すれば、平均二乗誤差は $E[X^2] = \sigma^2$ になるので、歪み $\sigma^2$ は「何もしなくても達成できる」水準です。
$R$ ビットを使うと達成可能な最小歪みは $D = \sigma^2 \cdot 2^{-2R}$ です。1ビット追加するたびに歪みは $1/4$ になり、SNR（信号対雑音比）は約6 dB改善されます。これは6 dB/bit ルールと呼ばれ、音声や画像の量子化設計で広く使われる基準です。
さらに、ガウス情報源のレート歪み関数はあらゆる情報源の中で最悪（同じ分散に対して最大の $R(D)$）であることが知られています。これは通信路容量の議論でガウスノイズが最悪であることの「双対」です。
ガウス情報源では閉じた形の解が得られましたが、離散情報源でも同様の解析が可能です。次に、最も単純な離散情報源であるバイナリ情報源のケースを見ましょう。
バイナリ情報源のレート歪み関数
問題の設定
情報源が $X \in \{0, 1\}$（$P(X = 1) = p$）であり、歪み関数がハミング歪みの場合を考えます。
解の導出
ハミング歪みのもとで、平均歪みはビット誤り率に相当します。
$$ E[d(X, \hat{X})] = P(X \neq \hat{X}) = D $$
レート歪み関数の最適化問題を解きます。$X \in \{0, 1\}$ で $P(X=1)=p$ とし、テスト通信路 $p(\hat{x}|x)$ を対称通信路と仮定します。すなわち、$P(\hat{X} \neq X | X = 0) = P(\hat{X} \neq X | X = 1) = \delta$ とします。
このとき、歪み制約は $E[d(X, \hat{X})] = \delta = D$ です。相互情報量を計算すると、
$$ I(X; \hat{X}) = H(\hat{X}) – H(\hat{X}|X) = H(\hat{X}) – H(\delta) $$
$H(\hat{X})$ を最大化する（最も情報を多く送る）のではなく、最小化する条件を求めます。$P(\hat{X} = 1) = p(1-\delta) + (1-p)\delta = p + \delta – 2p\delta$ ですが、相互情報量を $\delta$ で最小化すると、$H(\hat{X})$ が $H(p)$ に等しくなる対称な場合が最適であることがKKT条件から示されます。
結果として、
$$ \begin{equation} R(D) = \begin{cases} H(p) – H(D) & 0 \leq D \leq \min(p, 1-p) \\ 0 & D > \min(p, 1-p) \end{cases} \end{equation} $$
ここで $H(D) = -D\log D – (1-D)\log(1-D)$ は二値エントロピー関数です。
結果の解釈
$D = 0$ では $R(0) = H(p)$ です。これは源符号化定理と一致します——バイナリ情報源を完全に再現するには $H(p)$ ビット/シンボルが必要です。
$D = \min(p, 1-p)$ では $R = 0$ です。何も伝えずに最も確率の高い値を常に出力すれば、誤り率は $\min(p, 1-p)$ になります。これはMAP（最大事後確率）推定のビット誤り率であり、情報を全く使わない「最悪の圧縮」に対応します。
$p = 1/2$（公平なコイン）の場合、$R(D) = 1 – H(D)$ となり、エントロピーが最大（1ビット）であるため、最もビットレートが必要です。一方 $p$ が0か1に近い場合は、元のエントロピーが低いため少ないレートで済みます。
ガウス情報源とバイナリ情報源の2つの例は、連続と離散のそれぞれにおける典型的なレート歪みの振る舞いを示しています。次に、Pythonでこれらのレート歪み関数を可視化し、理論的な結果を視覚的に確認しましょう。
Pythonによる数値計算と可視化
import numpy as np
import matplotlib.pyplot as plt
def binary_entropy(p):
"""二値エントロピー関数"""
if p <= 0 or p >= 1:
return 0
return -p * np.log2(p) - (1 - p) * np.log2(1 - p)
fig, axes = plt.subplots(1, 3, figsize=(16, 5))
# --- 左: ガウス情報源のレート歪み関数 ---
ax = axes[0]
sigma2_values = [1.0, 2.0, 4.0]
for sigma2 in sigma2_values:
D_range = np.linspace(0.01, sigma2, 200)
R = 0.5 * np.log2(sigma2 / D_range)
R = np.maximum(R, 0)
ax.plot(D_range, R, linewidth=2, label=rf'$\sigma^2 = {sigma2}$')
ax.set_xlabel('Distortion $D$', fontsize=12)
ax.set_ylabel('Rate $R(D)$ [bits]', fontsize=12)
ax.set_title('Rate-distortion: Gaussian source', fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
ax.set_ylim(0, 5)
# --- 中: バイナリ情報源のレート歪み関数 ---
ax = axes[1]
p_values = [0.5, 0.3, 0.1]
for p in p_values:
D_max = min(p, 1 - p)
D_range = np.linspace(0.001, D_max - 0.001, 200)
R = np.array([binary_entropy(p) - binary_entropy(d) for d in D_range])
R = np.maximum(R, 0)
ax.plot(D_range, R, linewidth=2, label=f'$p = {p}$')
ax.set_xlabel('Distortion $D$ (bit error rate)', fontsize=12)
ax.set_ylabel('Rate $R(D)$ [bits]', fontsize=12)
ax.set_title('Rate-distortion: Binary source', fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
# --- 右: SNRとビットレートの関係（ガウス） ---
ax = axes[2]
sigma2 = 1.0
R_range = np.linspace(0.1, 5, 100)
D_R = sigma2 * 2**(-2 * R_range)
SNR_dB = 10 * np.log10(sigma2 / D_R)
ax.plot(R_range, SNR_dB, 'b-', linewidth=2)
# 6 dB/bit の傾斜線
ax.plot(R_range, 6.02 * R_range, 'r--', linewidth=1.5, label='6.02 dB/bit')
ax.set_xlabel('Rate $R$ [bits/sample]', fontsize=12)
ax.set_ylabel('SNR [dB]', fontsize=12)
ax.set_title('SNR vs Rate (Gaussian)', fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('rate_distortion.png', dpi=150, bbox_inches='tight')
plt.show()
レート歪み関数のグラフから、以下のことが確認できます。
-
左図: ガウス情報源の $R(D)$ は凸な減少関数です。分散 $\sigma^2$ が大きいほど、同じ歪みレベルに対してより多くのビットが必要です。これは直感的に「情報量が多い（不確実性が大きい）ソースほど圧縮に多くのビットが必要」ということです
-
中図: バイナリ情報源では $p = 0.5$（最大エントロピー）のとき最もビットが必要です。$p$ が0や1に近いほどエントロピーが低く、少ないビットで圧縮できます
-
右図: ガウス情報源では1ビット追加するごとにSNRが約6 dB改善します。これはオーディオやビデオの圧縮設計で広く使われる「6 dB/bit ルール」の理論的根拠です
情報ボトルネック法への接続
レート歪み理論の発展的な応用として、情報ボトルネック法（Information Bottleneck method, Tishby et al., 1999）があります。標準的なレート歪み理論では歪み関数 $d(x, \hat{x})$ を事前に定めますが、情報ボトルネック法では「関連する変数 $Y$ との相互情報量の保存」を歪みの代わりに使います。
具体的には、$(X, Y)$ の同時分布が与えられたとき、圧縮表現 $T$ について以下を最小化します。
$$ \mathcal{L}_{\text{IB}} = I(X; T) – \beta\, I(T; Y) $$
第一項は $X$ を $T$ にどれだけ圧縮するか（レート）、第二項は圧縮後に $Y$ に関する情報をどれだけ保持するか（関連性の保存）を表します。$\beta$ はトレードオフを制御するラグランジュ乗数です。
$\beta \to \infty$ では $Y$ の情報を完全に保持しようとし、$\beta \to 0$ では $X$ を最大限圧縮します。この枠組みは、深層学習の中間層がデータを「圧縮しつつ予測に必要な情報を保持する」メカニズムの理論的基盤として注目されています。
まとめ
本記事では、レート歪み理論の基本定理から具体的な情報源のレート歪み関数の導出まで解説しました。
- レート歪み関数 $R(D)$ は、歪み $D$ 以下を達成するための最小ビットレートであり、条件付き分布 $p(\hat{x}|x)$ にわたる相互情報量 $I(X; \hat{X})$ の最小化として定義されます
- レート歪み定理により、$R(D)$ は達成可能なレート歪みの対の境界を厳密に定めます。順定理はランダム符号化の存在性を示し、逆定理は情報量の連鎖からの下界を与えます
- ガウス情報源では $R(D) = \frac{1}{2}\log(\sigma^2/D)$ であり、1ビット追加で歪みが $1/4$ に減少します（6 dB/bit ルール）。ガウスは同じ分散の情報源の中で最悪（最大レートが必要）です
- バイナリ情報源では $R(D) = H(p) – H(D)$ であり、エントロピーと二値エントロピー関数の差で表されます
- 情報ボトルネック法はレート歪み理論の拡張であり、関連変数の情報保持を歪み基準とすることで、深層学習の理論的理解への道を開いています
レート歪み理論は、通信路符号化定理と双対をなすシャノンの理論の柱です。通信路符号化が「ノイズのある通信路でどれだけ速く情報を送れるか」を問うのに対し、レート歪み理論は「情報源をどれだけ少ないビットで表現できるか」を問います。両者を合わせることで、エンドツーエンドの通信システムの理論的限界が完全に特徴づけられます。
次のステップとして、以下の記事も参考にしてください。
- データ処理不等式と十分統計量 — 情報量の非増大性とレート歪み理論の基盤
- 交差エントロピーとKLダイバージェンスの関係 — 相互情報量の詳細
- 微分エントロピーと連続確率変数の情報量 — ガウス情報源のレート歪み導出の基礎