\begin{equation*} \newcommand\innerp[2]{\langle #1, #2 \rangle} \newcommand\ve[1]{\boldsymbol{#1}} \newcommand\parfrac[2]{\frac{\partial #1}{\partial #2}} \newcommand\mean[2]{\mathrm{E}_{#1} \left[ #2 \right]} \newcommand\KL[2]{\mathrm{KL} \left[ #1 \ \middle| \middle| \ #2 \right]} \end{equation*}

よくなる条件はさっぱり。。

一方、再帰的Golomb-Rice符号は何が得意なんだろ、というのをまとめ直している。gnuplotで一様分布と幾何分布を重ねてみると、幾何分布の方が裾が重い(原理上台(サポート)が無限)。一様分布は急に確率が0になるので裾が軽い。

だからガウス分布に近い分布を効率的に符号化できる、ということになる。例の圧縮本と言ってることが逆になるんだが、大丈夫か・・・

同一の平均を持つ一様分布と幾何分布でエントロピーを計算してみると、圧倒的に幾何分布の方がエントロピーが高い。。。??直感に反する。一様分布が最も高いケースは離散だけだっけ・・・

悶絶しながらエントロピー最大の分布を探っていたら、

証明を示しておこう。(上のURLには概略のみ)

考えるべき問題は、以下の最適化問題である

\begin{equation*} \max \sum_{n = 0}^{\infty} p_{n} \log p_{n} \quad \text{subject to:} \sum_{x = 0}^{\infty} n p_{n} = \mu,\ \sum_{x = 0}^{\infty} p_{n} = 1 \end{equation*}

ラグランジュの未定乗数法より、

\begin{align*} \mathcal{L}(p_{1}, ..., p_{n}, \lambda_{1}, \lambda_{2}) &= \sum_{n = 0}^{\infty} p_{n} \log p_{n} + \lambda_{1} \left( \sum_{n = 0}^{\infty} n p_{n} - \mu \right) + \lambda_{2} \left( \sum_{n = 0}^{\infty} p_{n} - 1 \right) \\ \parfrac{}{p_{i}} \mathcal{L} &= \log p_{i} + 1 + i\lambda_{1} + \lambda_{2} \tag{1} \\ \parfrac{}{\lambda_{1}} \mathcal{L} &= \sum_{n = 0}^{\infty} n p_{n} - \mu = 0 \tag{2} \\ \parfrac{}{\lambda_{2}} \mathcal{L} &= \sum_{n = 0}^{\infty} p_{n} - 1 = 0 \tag{3} \end{align*}

(1)より、

\begin{equation*} p_{i} = \exp(-1-i\lambda_{1}-\lambda_{2}) \tag{4} \end{equation*}

よって(3)より

\begin{equation*} \sum_{n = 0}^{\infty} p_{n} = \sum_{n = 0}^{\infty} \exp(-1-n\lambda_{1}-\lambda_{2}) = 1 \implies \sum_{n = 0}^{\infty} \exp(-n\lambda_{1}) = \exp(1 + \lambda_{2}) \end{equation*}

(この等式から、級数 \(\sum_{n = 0}^{\infty} \exp(-n\lambda_{1})\) は有界なので \(\lambda_{1} \geq 0\) )これを(4)に代入すると

\begin{equation*} p_{i} = \frac{\exp(-i\lambda_{1})}{\sum_{n = 0}^{\infty} \exp(-n\lambda_{1})} = \frac{a^{i}}{\sum_{n = 0}^{\infty} a^{n}} \quad a := \exp(-\lambda_{1}) \end{equation*}

これを(2)に代入すると

\begin{align*} \sum_{n = 0}^{\infty} n \frac{a^{n}}{\sum_{i = 0}^{\infty} a^{i}} = \mu \\ \implies \sum_{n = 0} n a^{n} = \frac{a}{(1 - a)^{2}} = \mu \sum_{i = 0}^{\infty} a^{i} = \frac{\mu}{1 - a} \\ \implies a = \mu(1 - a) \implies a = \frac{\mu}{1 + \mu} \end{align*}

この結果と

\begin{equation*} \sum_{n = 0}^{\infty} a^{n} = \frac{1}{1 - \frac{\mu}{1 + \mu}} = \frac{1 + \mu}{1 + \mu - \mu} = 1 + \mu \end{equation*}

より、

\begin{equation*} p_{i} = \frac{1}{1 + \mu} \left( \frac{\mu}{1 + \mu} \right)^{i} \end{equation*}

となって、これは \(\rho = \frac{1}{1 + \mu}\) の幾何分布である。

非負値整数の最もエントロピーが高い情報源を符号化できるのはGolomb-Rice符号ということになった。…となると、再帰的Golomb-Riceは何が得意なんだ。比較の結果、 \(\rho\) が大きい(より0に集中した)分布で強いことがわかっている(クラシックやジャズで強く、ポップスで弱いのも納得)。結論としては、heavy-tailとは言わないけどより0集中した符号に有利である、というべきかもしれない。グラフの差し替えがいるかも。

上記の考察はWavPack作者の見解と真っ向から対立する。ちゃんと議論するなら、再帰的Golomb-Rice符号の確率分布、少なくともHinge損失の確率分布を議論し、それが真に幾何分布よりもheavy-tailであることを言わなければならないと思う。

散歩してたらKLダイバージェンス最小化基準で符号設定するのもありだなあと思った