1.8 データ処理不等式

「データをいじっても，もとになかった情報は生まれない」は，情報理論の格率の一つである．受け取った $𝑌$ にどんな後処理 $𝑓$ を施しても， $𝑋$ について新たに知れることは増えない．当たり前に聞こえるが，主張の射程は広い． $𝑓$ は任意でよいので，どんなに巧妙な信号処理・特徴抽出・機械学習モデルであっても，通信路から出てきた $𝑌$ を加工しただけでは $𝑋$ についての情報は増えない，と言っている．だから「どんな受信機を設計しても超えられない限界」を論じられる．第6章の通信路符号化の逆定理（容量を超えるレートでは誤りが消えない）は，この不等式なしには証明できない．

形式的には相互情報量の単調性として述べられる．本節では，いちばん一般的な形（相対エントロピーの単調性）から出発して，相互情報量の言葉へ，さらにマルコフ連鎖の言葉へと三段階で降りていく．

相対エントロピーの単調性（土台）

定理 1.8.1. 同じアルファベット上の二つの分布 $𝑝, 𝑞$ と写像 $𝑓$ をとる． $𝑓$ で送った先の分布を $𝑓$ による 像測度 といい， $𝑓 * 𝑝$ ， $𝑓 * 𝑞$ と書く．このとき

𝐷 (𝑓 * 𝑝 ∥ 𝑓 * 𝑞) \leq 𝐷 (𝑝 ‖ 𝑞) .

これは「分布を $𝑓$ で粗くまとめると，二つの分布の見分けはつきにくくなる」という主張である． $𝑓$ が単射なら情報は何も失われず等号，逆に $𝑓$ が定数写像なら送り先では両者が同じ分布になってしまい左辺は 0，というのが両極である．証明は前節の対数和不等式そのままで， $𝑓$ で同じ値に潰される点たちを一つの和にまとめるだけである．

証明. $𝑝 (𝑥) > 0$ かつ $𝑞 (𝑥) = 0$ となる $𝑥$ があれば右辺が $+ \infty$ で主張は自明だから， $𝑞 (𝑥) = 0$ の点では $𝑝 (𝑥) = 0$ としてよい．そうした点は両辺のどの項にも寄与しないので最初から取り除き，以下 $𝑞 > 0$ とする．

送り先の点 $𝑧$ ごとに， $𝑓$ で $𝑧$ に潰される点たちをまとめる．定義から

(𝑓 * 𝑝) (𝑧) = \sum 𝑥 : 𝑓 (𝑥) = 𝑧 𝑝 (𝑥), (𝑓 * 𝑞) (𝑧) = \sum 𝑥 : 𝑓 (𝑥) = 𝑧 𝑞 (𝑥)

である．この和に対数和不等式（定理 1.7.1）を $𝑎 𝑥 \leftarrow 𝑝 (𝑥)$ ， $𝑏 𝑥 \leftarrow 𝑞 (𝑥)$ として適用すると

(𝑓 * 𝑝) (𝑧) l o g (𝑓 * 𝑝) (𝑧) (𝑓 * 𝑞) (𝑧) \leq \sum 𝑥 : 𝑓 (𝑥) = 𝑧 𝑝 (𝑥) l o g 𝑝 (𝑥) 𝑞 (𝑥)

を得る．左辺は「まとめてから測った量」，右辺は「個別に測って足した量」である． $𝑧$ について足し合わせると，左辺は $𝐷 (𝑓 * 𝑝 ‖ 𝑓 * 𝑞)$ ，右辺は $𝑥$ 全体にわたる和なので $𝐷 (𝑝 ‖ 𝑞)$ となり，主張を得る． $◼$

符号長で読む. $𝑞$ だと思い込んで符号化する人の損（1.6 節）は，観測を粗くするほど小さくなる．細かく見ていれば「 $𝑞$ ではありえない値が出た」と気づけたのに，まとめてしまうと気づけない．だから損も減る．これがデータ処理不等式すべての土台になる．

形式化: klDiv_map_le (ソース)

後処理は相互情報量を増やさない

定理 1.8.2（後処理不等式）. $𝑌$ を後処理 $𝑓$ に通すと相互情報量は増えない：

𝐼 (𝑋; 𝑓 (𝑌)) \leq 𝐼 (𝑋; 𝑌) .

証明. 写像 $𝑔 (𝑥, 𝑦) : = (𝑥, 𝑓 (𝑦))$ を考え，定理 1.8.1 を $𝑝 \leftarrow 𝑝 𝑋, 𝑌$ （同時分布）， $𝑞 \leftarrow 𝑝 𝑋 \otimes 𝑝 𝑌$ に対して $𝑔$ で適用する．ここで $(𝑝 𝑋 \otimes 𝑝 𝑌) (𝑥, 𝑦) : = 𝑝 (𝑥) 𝑝 (𝑦)$ を 周辺積 と書く．鍵は次の二つの像測度の等式である．

(i) $𝑔$ で同時分布を送ると $(𝑋, 𝑓 (𝑌))$ の同時分布になる： $𝑔 * 𝑝 𝑋, 𝑌 = 𝑝 𝑋, 𝑓 (𝑌)$ ．実際 $𝑔 (𝑋, 𝑌) = (𝑋, 𝑓 (𝑌))$ だから定義どおり．

(ii) $𝑔$ で周辺積を送ると，第 2 成分だけが $𝑓$ で送られて $𝑔 * (𝑝 𝑋 \otimes 𝑝 𝑌) = 𝑝 𝑋 \otimes (𝑓 * 𝑝 𝑌) = 𝑝 𝑋 \otimes 𝑝 𝑓 (𝑌)$ ． $𝑓 (𝑌)$ の周辺分布は $𝑓 * 𝑝 𝑌 = 𝑝 𝑓 (𝑌)$ なので，これは $𝑋$ と $𝑓 (𝑌)$ の周辺積にほかならない．

したがって，定理 1.8.1（ $𝐷 (𝑔 * 𝑝 ‖ 𝑔 * 𝑞) \leq 𝐷 (𝑝 ‖ 𝑞)$ ）は

𝐷 (𝑝 𝑋, 𝑓 (𝑌) ∥ 𝑝 𝑋 \otimes 𝑝 𝑓 (𝑌)) ⏟_____⏟_____⏟ = 𝐼 (𝑋; 𝑓 (𝑌)) \leq 𝐷 (𝑝 𝑋, 𝑌 ∥ 𝑝 𝑋 \otimes 𝑝 𝑌) ⏟____⏟____⏟ = 𝐼 (𝑋; 𝑌)

となり，定義 1.3.1 により $𝐼 (𝑋; 𝑓 (𝑌)) \leq 𝐼 (𝑋; 𝑌)$ ． $◼$

証明でやったのは「相互情報量は同時分布と周辺積のあいだの相対エントロピーである」（定義 1.3.1 の読み）ことに気づき，その二つの分布を同じ写像 $𝑔 = (i d, 𝑓)$ で送って定理 1.8.1 を当てただけである． $𝑋$ 側には何もせず $𝑌$ 側だけを粗くしたので，「 $𝑌$ の解像度を落とすと，そこから読み取れる $𝑋$ の情報も落ちる」という当然の主張になっている．等号が成り立つのは $𝑓$ が $𝑋$ についての情報を一切捨てないときで，その状況をきちんと特徴づけたのが 1.9 節の十分統計量である．

形式化: mutualInfo_le_of_postprocess (ソース)

マルコフ連鎖版

ここまでの二つの定理では， $𝑌$ の加工が写像 $𝑓$ による決定論的なものだった．しかし実際の通信路は「送った $𝑍$ にノイズが乗って $𝑌$ が出てくる」という確率的な加工である．これを含む形へ進むために，三つの確率変数が一列に並ぶという状況を定義しておく．

定義 1.8.3（マルコフ連鎖）. 確率変数 $𝑋, 𝑍, 𝑌$ が マルコフ連鎖をなす とは， $𝑍$ を与えたとき $𝑋$ と $𝑌$ が条件付き独立であること，すなわち $𝑝 (𝑧) > 0$ である各 $𝑧$ について

𝑝 (𝑥, 𝑦 ∣ 𝑧) = 𝑝 (𝑥 ∣ 𝑧) 𝑝 (𝑦 ∣ 𝑧)

が成り立つことをいう．このとき $𝑋 \to 𝑍 \to 𝑌$ と書く．

形式化: IsMarkovChain (ソース)

条件が言っているのは「 $𝑧$ を知ってしまえば， $𝑋$ の値をさらに教わっても $𝑌$ の見え方は変わらない」ということである． $𝑋$ から $𝑌$ への影響がすべて $𝑍$ を通ってしか届かない，と読める．典型例は $𝑍$ にノイズを乗せて $𝑌$ を作る状況で， $𝑌$ の分布が $𝑍$ だけで決まり $𝑋$ には直接よらないなら，この条件が成り立つ．定理 1.8.2 の決定論的な後処理 $𝑌 \mapsto 𝑓 (𝑌)$ はその特別な場合（ノイズのない加工）にあたる（定理 1.8.2 を後で定理 1.8.4 から復元するときは，次に述べる対称性を使って連鎖を $𝑓 (𝑌) \to 𝑌 \to 𝑋$ の向きに読む）．1.4 節で条件付き相互情報量が「減る例」として挙げた， $𝑋$ も $𝑌$ も $𝑍$ もすべて同じコインの値である状況も， $𝑋 \to 𝑍 \to 𝑌$ の最も単純な例である．

命題 1.4.2 の等号条件により，この定義は $𝐼 (𝑋; 𝑌 ∣ 𝑍) = 0$ と言い換えられる．以下の証明ではこの形で使う．

矢印は向きのある絵を与えるが，定義そのものは $𝑋$ と $𝑌$ について対称であり， $𝑋 \to 𝑍 \to 𝑌$ と $𝑌 \to 𝑍 \to 𝑋$ は同じ条件である．矢印が表しているのは時間の流れではなく， $𝑍$ が両側のあいだに挟まっていることだと思えばよい．なお確率過程論でいうマルコフ連鎖（状態が時刻ごとに遷移し，次の状態が直前の状態だけで決まる列）と同じ語だが，本章で必要なのは上の三変数の条件付き独立だけであり，遷移行列や定常分布は使わない（その意味でのマルコフ連鎖は第3章で定常情報源の例として現れる）．

定理 1.8.4（データ処理不等式・マルコフ版）. $𝑋 \to 𝑍 \to 𝑌$ がマルコフ連鎖（定義 1.8.3）のとき，

𝐼 (𝑋; 𝑌) \leq 𝐼 (𝑍; 𝑌) .

読み方は素直である．「 $𝑋$ の情報が中継変数 $𝑍$ を経由してしか $𝑌$ に届かないなら， $𝑌$ が $𝑋$ について持つ情報は $𝑍$ が持つ情報を超えない」．これは中継地点がボトルネックになる，という素朴な見立てそのものである．実際の通信路（送信語 $𝑋$ を符号化し，通信路を通し，受信語から復号する）はまさにこの形の連鎖なので，以降の議論で使うのはほぼこの版である．

証明. 対 $(𝑋, 𝑍)$ が $𝑌$ について持つ情報 $𝐼 (𝑋, 𝑍; 𝑌)$ を，チェイン則（定理 1.5.1）で二通りに展開する：

𝐼 (𝑋, 𝑍; 𝑌) = 𝐼 (𝑍; 𝑌) + 𝐼 (𝑋; 𝑌 ∣ 𝑍), 𝐼 (𝑋, 𝑍; 𝑌) = 𝐼 (𝑋; 𝑌) + 𝐼 (𝑍; 𝑌 ∣ 𝑋) .

（後者は前者で $𝑋$ と $𝑍$ の役割を入れ替えたもの． $𝐼 (𝑋, 𝑍; 𝑌)$ は対の取り方の順序によらない．）マルコフ連鎖 $𝑋 \to 𝑍 \to 𝑌$ の定義（定義 1.8.3）は，命題 1.4.2 の等号条件を通して $𝐼 (𝑋; 𝑌 ∣ 𝑍) = 0$ と言い換えられる．よって第 1 式から $𝐼 (𝑋, 𝑍; 𝑌) = 𝐼 (𝑍; 𝑌)$ ．これを第 2 式に代入すると

𝐼 (𝑍; 𝑌) = 𝐼 (𝑋; 𝑌) + 𝐼 (𝑍; 𝑌 ∣ 𝑋) .

条件付き相互情報量の非負性（命題 1.4.2）より $𝐼 (𝑍; 𝑌 ∣ 𝑋) \geq 0$ だから， $𝐼 (𝑍; 𝑌) \geq 𝐼 (𝑋; 𝑌)$ ，すなわち $𝐼 (𝑋; 𝑌) \leq 𝐼 (𝑍; 𝑌)$ ． $◼$

形式化上の注記. 形式化はマルコフ連鎖を， $𝑍$ を与えたときの $𝑋$ と $𝑌$ の条件付き独立を結合分布の分解として述べる IsMarkovChain で定義する．教科書の矢印記法 $𝑋 \to 𝑍 \to 𝑌$ とは表層が異なるが，内容は定義 1.8.3 と同じである．まずマルコフ下で $𝐼 (𝑋; 𝑌 ∣ 𝑍) = 0$ を示し，そこから本定理を導く．なお本ライブラリの結論は $𝐼 (𝑋; 𝑌) \leq 𝐼 (𝑍; 𝑌)$ の形（中継 $𝑍$ を $𝑌$ 側と組む配置）で，教科書でよく見る $𝐼 (𝑋; 𝑌) \leq 𝐼 (𝑋; 𝑍)$ とは引数配置が異なるが，どちらもデータ処理不等式の正しい一形態である．

形式化: mutualInfo_le_of_markov (ソース)

応用：記憶のない通信路を 1 文字ごとに分解する

定理 1.8.5（記憶のない通信路の 1 文字分解）. 入力 $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ を通信路に通して出力 $𝑌 𝑛 = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ を得るとし，通信路は 記憶がない（memoryless）とする．すなわち，入力 $𝑋 𝑛$ を与えたとき，出力の各文字 $𝑌 𝑖$ の条件付き分布が同じ時刻の入力 $𝑋 𝑖$ だけで決まり，しかも $𝑌 0, \dots, 𝑌 𝑛 - 1$ が条件付き独立であるとする．このとき

𝐼 (𝑋 𝑛; 𝑌 𝑛) \leq 𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑋 𝑖; 𝑌 𝑖) .

証明. 定理 1.3.4 より $𝐼 (𝑋 𝑛; 𝑌 𝑛) = 𝐻 (𝑌 𝑛) - 𝐻 (𝑌 𝑛 ∣ 𝑋 𝑛)$ と書ける．二項をそれぞれ評価する．

第 2 項は等号で分解する. 定理 1.2.3 を繰り返し当てると $𝐻 (𝑌 𝑛 ∣ 𝑋 𝑛) = \sum 𝑖 𝐻 (𝑌 𝑖 ∣ 𝑌 0, \dots, 𝑌 𝑖 - 1, 𝑋 𝑛)$ である（各段で補題 1.2.5 を $𝑋 𝑛$ を条件に抱えたまま使う）．記憶のなさから， $𝑋 𝑛$ を知ったうえでは $𝑌 𝑖$ は他の出力に依存せず，しかも $𝑋 𝑖$ だけで決まるので，各項は $𝐻 (𝑌 𝑖 ∣ 𝑋 𝑖)$ に等しい．よって $𝐻 (𝑌 𝑛 ∣ 𝑋 𝑛) = \sum 𝑖 𝐻 (𝑌 𝑖 ∣ 𝑋 𝑖)$ ．

第 1 項は不等号で分解する. 同じく定理 1.2.3 を繰り返して $𝐻 (𝑌 𝑛) = \sum 𝑖 𝐻 (𝑌 𝑖 ∣ 𝑌 0, \dots, 𝑌 𝑖 - 1)$ ，各項に条件付けの単調性（定理 1.2.4）を当てて $𝐻 (𝑌 𝑖 ∣ 𝑌 0, \dots, 𝑌 𝑖 - 1) \leq 𝐻 (𝑌 𝑖)$ ．よって $𝐻 (𝑌 𝑛) \leq \sum 𝑖 𝐻 (𝑌 𝑖)$ ．

二つを合わせると

𝐼 (𝑋 𝑛; 𝑌 𝑛) \leq \sum 𝑖 𝐻 (𝑌 𝑖) - \sum 𝑖 𝐻 (𝑌 𝑖 ∣ 𝑋 𝑖) = \sum 𝑖 (𝐻 (𝑌 𝑖) - 𝐻 (𝑌 𝑖 ∣ 𝑋 𝑖)) = \sum 𝑖 𝐼 (𝑋 𝑖; 𝑌 𝑖),

最後は定理 1.3.4 による． $◼$

全体で運べる情報が 1 文字あたりの情報の $𝑛$ 倍を超えない，というこの上界が，通信路容量を「1 文字あたりの量」として定義してよいことの根拠になる．第6章を先取りする結果である．

証明で不等号が入ったのは第 1 項，出力どうしの相関を捨てたところだけである．定理 1.5.3（i.i.d. 加法性）では等号だったのに，ここが不等号なのは，入力 $𝑋 0, \dots, 𝑋 𝑛 - 1$ に相関を許しているからで，入力が相関すれば出力も相関し， $𝐻 (𝑌 𝑛) < \sum 𝑖 𝐻 (𝑌 𝑖)$ になりうる．裏返せば「入力を相関させても得はしない」という主張でもある．

形式化上の注記. 形式化では記憶のなさを二つの IsMarkovChain 仮定（各文字の出力が他文字の入力を経由しないこと，出力どうしが条件付き独立であること）として与える．本文の定理 1.8.5 が括弧で述べた二条件がそのままこの形になっている．どちらも通信路の構造そのものを表す前提条件で，結論の核心を仮定に抱えさせるものではない．

形式化: mutualInfo_le_sum_per_letter_of_memoryless_strong (ソース)

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．