指数分布の平均の分散の爆発:最小二乗法による解決
Exploding variance of means of exponentials: least-squares to the rescue (francisbach.com)
要約
本稿では、機械学習における「log-sum-exp」関数の推定という課題に焦点を当てています。この関数は、特に指数関数的な値が大きい場合に、サンプリングによる推定値の分散が爆発するという問題があります。記事では、この問題に対して、計算的・統計的に単純な最小二乗法(least-squares)の利点を活かしつつ、log-sum-expの利点を維持する新しいアプローチを提案しています。これは、相対密度推定をテストケースとして、f-ダイバージェンスの枠組みを用いて探求されます。
全文翻訳
指数関数の平均値における分散爆発:最小二乗法による解決策
機械学習における一般的なタスクは、$$ \log \Big( \int
_{\mathcal{X}} e^{v(x)} dq(x) \Big),$$ のような(連続的に多くの項を持つ可能性のある)対数和指数関数(log-sum-exp)を推定または最適化することです。ここで、(v: \mathcal{X} \to \mathbb{R}) は何らかのポテンシャル関数であり、(q) は集合 (\mathcal{X}) 上の確率分布です。これは、データサイエンスの様々な分野で数多くの応用があります。確率モデルの正規化を通じて、あるいは最大値の滑らかな近似として、その微分を通じてトランスフォーマーで、またはエントロピー正則化を用いる強化学習
[19] で利用されます。集合 (\mathcal{X}) が有限(かつ大きい可能性もある)で積分が明示的な合計で実行できる場合もありますが、多くの場合、厳密な計算は不可能であり、代わりに確率分布 (q) からのサンプリングが使用されます。
主な困難は、このような推定値の分散に由来します。特に (v) が大きな値をとる場合に顕著です。最も単純な例では、平均 (\mu) と分散 (\sigma^2) を持つ独立な正規分布 (z_1,\dots,z_n \in \mathbb{R}) に対して、(\mathbb{E}[e^z]) を推定する際の相対二乗誤差は次のようになります。
$$ \frac{ {\rm var}\big( \frac{1}{n} \sum
_{i=1}^n e^{z_i} \big) }{( \mathbb{E}[ e^{z} ])^2} = \frac{1}{n} \frac{ {\rm var}(e^z) }{( \mathbb{E}[ e^{z} ])^2} = \frac{ e^{\sigma^2}-1}{n}.$$ (n) が増加するとゼロに収束しますが(大数の法則から期待されるように)、(\sigma) が増加すると指数関数的に爆発します。対数を取っても分散の爆発は解消されません。つまり、({\rm var}\big( \log \big( \frac{1}{n} \sum
_{i=1}^n e^{z_i} \big)\big)) もまた、(n) が大きい場合、デルタ法から得られるように、(\frac{ e^{\sigma^2}-1}{n}) と同様に漸近的に増加することが示されます。
推定は困難ですが、対数和指数関数は多くの優れた特性を備えています(だからこそ人々はそれを好むのです)。私は特に、(1) 最大値の滑らかな近似であること(例えば、この以前の投稿を参照)、および (2) 確率モデルの正規化方法であり、特に階層的確率モデルにおいて、条件付き独立性の仮定が関連する損失関数の分離可能性につながるため、最尤推定に適していること(確率的グラフィカルモデルで徹底的に使用されているように)を気に入っています。
この投稿で私が答えようとしている主な質問は次のとおりです。
対数和指数関数の最適化の利点を維持しつつ、計算上および統計上の欠点への暴露を減らすことは可能でしょうか?
スペクトルの反対側には、本質的に正反対の特性を持つ最小二乗回帰があります。
- 肯定的な側面:線形代数による線形モデルの閉形式推定、分散が制御されたモーメントの計算に基づいていること、様々な設定(加速、確率的勾配降下法など)でのシャープな分析につながることなど、計算上および統計上の単純さを様々な形で得られます。例えば、加速に関するこの投稿、および平均化に関するこの投稿を参照してください。
- 否定的な側面:特に離散的な出力を持つすべての予測問題に最小二乗回帰を使用すると、いくつかのアーティファクトが生じます。伝統的な例は、ガウスクラス条件付きデータ(同一の共分散行列を持つ)の分類であり、one-hotエンコードされた出力に対する最小二乗法は、「マスキング」(13, Section 2.4および以下の例を参照)や、多項ロジスティック回帰(ソフトマックス回帰とも呼ばれる)と比較して高い近似誤差を伴う問題を引き起こします。なぜなら、その場合、対数条件付き確率がアフィンになるからです。
これらを調和させることは可能でしょうか?言い換えれば、最小二乗法は本当に私が必要とするすべてでしょうか?(私の同僚は、最小二乗法への私の愛情をからかうことがあります)。
最小二乗法を通して世界を見る別の(古典的な)試みがあることに注意してください。それは逐次的に、ニュートン法を通して行うことです。この文脈では、反復加重最小二乗法につながりますが、これは計算のためだけであり、統計的な改善はありません。私たちが目指しているのは、より強力なものです。通常、凸関数の最適化(ロジスティック回帰やソフトマックス回帰など)を必要とする最尤推定問題に対して、最小二乗法ベースの閉形式推定器を得ることは可能でしょうか?
興味深いことに、私の新しい試みは、次の積分方程式に要約できます。
$$ t \log t, – t + 1 = \int_0^1 !! \frac{ (t-1)^2}{\rho t + 1-\rho} (1-\rho) d\rho,$$ これは通常の積分トリックで確認できます。なぜ、そしてどのようにしてそれが可能になるのかを見てみましょう!
相対密度推定をテストベッドとして
この投稿では、様々な推定フレームワークを研究・比較できる単純で基本的な問題に焦点を当てます。これは、いくつかの方法で拡張できることに注意してください(特に、相互情報量を通じて、以下を参照)。
( \mathcal{X} ) 上の2つの確率分布 (p) と (q) を考えます。目標は、相対密度 (\log \big(\frac{dp}{dq}(x)\big)) の対数を推定することです。これは、変分定式化
[1] のため、カルバック・ライブラー(KL)ダイバージェンスの推定と同等であることがわかります。
$${\rm KL}(p|q) = \int
_{\mathcal{X}} \log \big(\frac{dp}{dq}(x)\big) dp(x) = \sup
_{v: \mathcal{X} \to \mathbb{R}} \int
_{\mathcal{X}} v(x) dp(x) + 1, – \int
_{\mathcal{X}} e^{v(x)} dq(x). \tag{1} $$
これは f-ダイバージェンスの特に重要なインスタンスです(例えば、
[2] を参照)。その定義と、(f) のフェンケル共役 (f^\ast) に基づく変分定式化は次のようになります。
$$D(p|q) = \int
_{\mathcal{X}} f \big( \frac{dp}{dq}(x) \big) dq(x)= \sup
_{v: \mathcal{X} \to \mathbb{R}} \int
_{\mathcal{X}} v(x) dp(x) , – \int
_{\mathcal{X}} f^\ast(v(x)) dq(x),$$ (f(t) = \sup
_{ u \in \mathbb{R}} ut-f^\ast(u)) を各 (t = \frac{dp}{dq}(x)) に適用した結果として表現されます。KLダイバージェンスは (f(t) = t \log t , – t + 1) と (f^\ast(u) = e^u , – 1) に対応します。
KLダイバージェンスの特定のケースでは、(v) の上に定数を最適化すると、ドンスカー・バラダン表現
[3] が得られます。
$${\rm KL}(p|q) = \sup
_{v: \mathcal{X} \to \mathbb{R}} \int
_{\mathcal{X}} v(x) dp(x), – \log \Big( \int
_{\mathcal{X}} e^{v(x)} dq(x) \Big). \tag{2}$$
対数和指数関数が明示的に現れるのがわかります。i.i.d.サンプル (p) および (q) からのサンプルを用いてポテンシャル (v) を推定するために、従来の変分アプローチは、積分を経験的平均に置き換えることに対応します。(q) の場合、サンプルのみが利用可能な場合には、不安定な経験的平均につながる可能性があります。この投稿の目的は、別の方法を探求することです(この新しいフレームワークの主な原則を提示します。詳細については
[7] を参照してください)。
f-ダイバージェンスを通じた定式化は、新しいアプローチにとって非常に重要です。なぜなら、他のダイバージェンスも定義において重要になるからです。次に進む前に、2つのポテンシャル (v) と (w) を持つ別の(同等の)変分定式化を示します。これは後で必要になります。(D(p|q)) は次と等しくなります。
$$ \sup
_{v,w: \mathcal{X} \to \mathbb{R}} \int
_{\mathcal{X}} v(x) dp(x) + \int
_{\mathcal{X}} w(x) dq(x) \mbox{ such that } \forall x \in \mathcal{X}, w(x) \leqslant -f^\ast(v(x)). \quad \tag{3} $$ 最適な場合、(w(x) = -f^\ast(v(x))) が得られ、KLケースの式(1)に戻ります。制約は凸ですが、(f(t) = t \log t – t + 1) の場合、従来の凸最適化手法が通常許可するものとはかけ離れています。この定式化は
[25 Theorem 4.4] に現れ、問題の対称性を維持するという良い特性を持っています(つまり、(p) と (q) が交換されると、これは (f) を (t \mapsto t f(1/t)) に置き換えることに相当し、(v) と (w) の交換に対応します)。以下では、制約 (\forall x \in \mathcal{X}, \ w(x) \leqslant -f^\ast(v(x))) を満たす関数 (v) および (w) の候補を得ます。通常は等号なしで満たされます。
重み付きカイ二乗ダイバージェンス
f-ダイバージェンスにとって関連性の高い別の関数 (f) は、パラメータ (\rho \in (0,1) ) に対して次のようになります。
$$ f(t) = \frac{1}{2} \frac{ (t-1)^2}{ \rho t + 1-\rho}. $$ これは重み付きカイ二乗ダイバージェンス $$ D(p|q) = \frac{1}{2} \int
_{\mathcal{X}} \frac{ \big(\frac{dp}{dq}(x)-1 \big)^2}{ \rho \frac{dp}{dq}(x) + 1-\rho} dq(x).$$ をもたらします。これは応用数学の様々な分野で利用されており
[4, 5]、特殊なケースでは、(\rho =0) の場合はピアソンカイ二乗ダイバージェンス、(\rho=1) の場合はネイマンカイ二乗(または逆ピアソン)、(\rho=1/2) の場合はルカムダイバージェンスなどの複数の名前で呼ばれます。
上記の関数 (f) は、「二次関数/アフィン関数」の形式をしており、次の「二次関数+アフィン関数」による変分表現を持ちます。
$$ \frac{1}{2} \frac{ (t-1)^2}{ \rho t + 1-\rho} = \sup
_{u \in \mathbb{R}} \ (t-1) u , – \frac{1}{2} ( \rho t + 1 – \rho) u^2, $$ 最適な (u = \frac{t-1}{\rho t + 1 , – \rho}) が得られます(これは、ちなみにフェンケル表現ではありません)。
したがって、これを (t = \frac{dp}{dq}(x)) に対して ( \mathcal{X} ) の各 (x) に適用すると、この関数 (f) に対して次のようになります。
$$ D(p|q) = !! \sup
_{u(\rho,\cdot):\mathcal{X} \to \mathbb{R}} \int
_{\mathcal{X}} \Big{ \big(\frac{dp}{dq}(x) -1\big) u(\rho,x) , – \frac{1}{2} \big( \rho \frac{dp}{dq}(x) + 1 – \rho\big) u(\rho,x)^2 \Big} dq(x). $$ これはまさに二次変分問題です。なぜなら、関数 (u(\rho,\cdot): \mathcal{X} \to \mathbb{R}) は二次的にしか現れないからです。最適な変分関数は (\displaystyle u(\rho,x) = \frac{ \frac{dp}{dq}(x) , – 1}{ \rho \frac{dp}{dq}(x) + 1-\rho}.) となります。
ここで定義した二次コスト関数は、まさに最小二乗回帰問題です。(x) を与えられたときに (y) を予測する問題で、確率 (\rho) で (y) が (1/\rho) の値を取り (x) は (p) からサンプリングされ、確率 (1-\rho) で (y) が (-1/(1-\rho)) の値を取り (x) は (q) からサンプリングされるというものです(これはノイズ対比推定
[26] を連想させます)。したがって、(\rho=0) または (\rho=1) での不安定性の可能性が見られます(後でそうではないことがわかります)。
この (D(p|q)) の変分定式化は、(p) または (q) に関する期待値をまとめて再構成することで書き換えることができます。
$$ \sup
_{u(\rho,\cdot):\mathcal{X} \to \mathbb{R}} \int
_{\mathcal{X}} \big( u(\rho,x) , – \frac{\rho}{2} u(\rho,x)^2 \big) dp(x) + \int
_{\mathcal{X}} \big( -u(\rho,x), – \frac{1-\rho}{2} u(\rho,x)^2 \big) dq(x) .$$ これにより、次の2つのポテンシャル定式化が正確に得られます。
$$v(x) = u(\rho,x) , – \frac{\rho}{2} u(\rho,x)^2 \ \ \mbox{ and } \ \ w(x) = -, u(\rho,x) , – \frac{1-\rho}{2} u(\rho,x)^2 $$ が2つのポテンシャルとなります(厳密な読者は、(\forall x \in \mathcal{X}, w(x) \leqslant -f^\ast(v(x))) をチェックできます。これは明白ではありませんが、それらが式(3)の最適化因子となります)。
要約すると、関数 (f: t \mapsto \frac{1}{2} \frac{ (t-1)^2}{ \rho t + 1-\rho}) に対して、まさに求めているもの、すなわち最小二乗法による変分定式化が得られました。これをより一般的なf-ダイバージェンスに拡張するにはどうすればよいでしょうか?
積分による拡張
(\displaystyle f(t) = \frac{1}{2} \int_0^1 \frac{ (t-1)^2}{\rho t + 1-\rho} d\nu(\rho)) と積分表現できる場合、非負測度 (\nu) が ([0,1]) 上に存在するとすれば、上記の展開を直接使用して (D(p|q) ) の表現を得ることができます。
$$ !!\sup
_{u: D\times \mathcal{X} \to \mathbb{R}} \int_0^1!!!! \int
_{\mathcal{X}} !! \Big[
, (\frac{dp}{dq}(x) -1) u(\rho)(x) , – \frac{1}{2} ( \rho \frac{dp}{dq}(x) + 1 , – \rho) u(\rho)(x)^2 dq(x) !\Big] d\nu(\rho), \tag{4} $$ ここで (u) は ([0,1] \times \mathcal{X}) から (\mathbb{R}) への関数となります。
これにより、式(3)で提示された2つのポテンシャル定式化が正確に得られます。
$$v(x) = \int_0^1 \big[ u(\rho,x) , – \frac{\rho}{2} u(\rho,x)^2 \big] d\nu(\rho) \tag{5} $$ および
$$w(x) = \int_0^1 \big[ -u(\rho,x) , – \frac{1-\rho}{2} u(\rho,x)^2 \big] d\nu(\rho), \tag{6} $$ ((w(x) + f^\ast(v(x)) \leqslant 0) を満たす。これもまた、単純ではない)ここで、(u(\rho,\cdot)) は式(4)の最大化因子です。これは、並列で最小二乗問題の連続体を実行することに対応します。
これらの展開は、積分表現を持つすべてのf-ダイバージェンスに有効であり、特にKLダイバージェンスについても有効です。なぜなら、次の関係があるからです。
$$t \log t, – t + 1 = \int_0^1 !! \frac{ (t-1)^2}{\rho t + 1-\rho} (1-\rho) d\rho,$$ すなわち、(d\nu(\rho) = 2 (1-\rho) d\rho) です。この積分表現はどこからともなく現れたものではありません。実際、それは以前の投稿で探求した演算子凸関数および演算子単調関数の理論から来ています。これには、KL、明らかにすべての重み付きカイ二乗ダイバージェンス((\nu) がディラック測度である場合)、およびすべての (\alpha)-ダイバージェンス
[14] が含まれますが、残念ながら全変動は含まれません。
これで、各 (\rho \in (0,1) ) に対する最小二乗推定値 (u(\rho,\cdot)) の積分としてポテンシャル (v) と (w) を学習するための一般的なフレームワークが得られました。関数空間を使用してそれらをパラメータ化し、線形モデルから始めることができます(より一般的なモデルについては以下を参照)。
閉形式スペクトル推定による線形モデル
各関数 (u(\rho,\cdot)) が何らかの特徴ベクトル (\varphi: \mathcal{X} \to \mathbb{R}^m) における線形モデルとしてモデル化される場合、つまり、ある (\theta(\rho) \in \mathbb{R}^m) に対して (u(\rho,x) = \theta(\rho)^\top \varphi(x)) ((\rho) によってインデックス付けされたパラメータのファミリー)である場合、式(4)の最適化問題は次のようになります。
$$ \sup
_{\theta(\rho) \in \mathbb{R}^m} \ (\mu_p – \mu_q)^\top \theta(\rho), -, \frac{1}{2} \theta(\rho)^\top ( \rho \Sigma_p + (1-\rho) \Sigma_q) \theta(\rho), $$ (p) および (q) に関する (\varphi) のモーメント:(\mu_p = \mathbb{E}
_p[\varphi(x)]), (\mu_q = \mathbb{E}
_q[\varphi(x)]), (\Sigma_p = \mathbb{E}
_p[\varphi(x)\varphi(x)^\top]), および (\Sigma_q = \mathbb{E}
_q[\varphi(x)\varphi(x)^\top]) を用います。
最適な (\theta(\rho)) は、線形システムを解くことによって得られます。
$$ \theta(\rho) = ( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} ( \mu_p ,- \mu_q), $$ 最適値は次のようになります。
$$ \frac{1}{2} ( \mu_p , – \mu_q)( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} ( \mu_p, – \mu_q).$$
これをすべての (\rho \in (0,1) ) に対して行い、積分すると、分布 (p, q) および特徴マップ (\varphi) に依存する新しいダイバージェンスが得られます。
$$F(p|q,\varphi) = \frac{1}{2} \int_0^1 ( \mu_p , – \mu_q)^\top( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} ( \mu_p, – \mu_q) d\nu(\rho), \tag{7} $$ および式(5)を使用して (f'(dp/dq(x))) を推定するための新しい候補 (v(x)) が得られます。構成により、(D(p|q)) の下限が得られます。
これは閉形式ですが、(\rho) に関する積分が必要であり、特に最小二乗問題が (\rho) が 0 または 1 に近づくと発散する可能性があるため、数値積分を使用する場合、積分を推定するために多くの求積点が必要になると予想されるため、実用的ではありません。
固有値による解決! (\rho \in (0,1) ) のすべての値に対して行列 (\rho \Sigma_p + (1-\rho) \Sigma_q) を反転する必要があるため、リッジ回帰を解く際に(正則化パラメータの複数の値に対して)行われる固有値分解を使用するのが自然に思えます
[6]。私たちの状況では、((\Sigma_p,\Sigma_q)) のペアの一般化固有値分解が必要です。つまり、基底 ((v_1,\dots,v_m)) を (\mathbb{R}^m) に見つけることです。
$$ \forall i,j \in {1,\dots,m}, \ v_i^\top \Sigma_q v_j = 1
{i=j} \ \mbox{ and } \ \Sigma_p v_i = \lambda_i \Sigma_q v_j.$$ 代数計算(
[7] を参照)により、次のようになります。
$$F(p|q,\varphi) = \sum{i=1}^m \frac{1}{2} \int_0^1 \frac{ \big( ( \mu_p , – \mu_q)^\top v_i \big)^2}{ \rho \lambda_i+ 1-\rho } d\nu(\rho) = \sum_{i=1}^m \big( ( \mu_p , – \mu_q)^\top v_i \big)^2 \frac{f(\lambda_i)}{(\lambda_i-1)^2}. $$ (\theta(\rho)) の固有値に対する和、およびポテンシャル (v(x)) と (w(x)) の二次線形形式としての同様の「単純な」公式があります。
$$v(x) = \varphi(x)^\top M \varphi(x) + 2c^\top \varphi(x)\ \mbox{ and } \ w(x) = \varphi(x)^\top N \varphi(x) , – 2c^\top \varphi(x),$$ (M,N,c) の詳細な公式があります。詳細については
[7] を参照してください。また、凸解析愛好家向けには、参考文献の下のセクションでさらに詳細を確認してください。特に、平方和最適化との興味深い関連性があります。
個々の最小二乗問題は (\rho=0) または (\rho = 1) の周りで不安定性を持つ可能性がありますが、積分後、(t \mapsto f(t)/(t-1)^2) が有界のままであるすべての関数 (f) に対して推定は安定しています(KLの場合、(f(0)=1) で単調減少します)。
このブログ投稿全体を通して、「単純な閉形式」という概念は非常に主観的であることを指摘しておきます。私が意味するのは、明示的な保証を持つ数値線形代数からの安定したルーチンです。これには、線形システムの反転と(一般化)固有値分解
[8] が含まれます。
計算量。 古典的な数値線形代数ルーチンを使用すると、ダイバージェンスの計算と (v) および (w) の推定値の検索にかかる実行時間計算量は (O(m^2n +m^3)) であり、(n) または (m) が大きい場合には問題となります。以下で簡単に説明する特徴学習は、すべての (\rho) にわたって共有される (r) 次元線形表現を学習することを可能にし、反復の複雑さが (O(r^3 + rmn)) である反復アルゴリズムにより、(r) が小さいままであれば効率的です。
スペクトル推定の利点
これで、これらの (\rho) に依存するすべての最小二乗問題を一度に解くことができるようになりました。分散を減らすという約束は果たされるでしょうか?主な競合相手は、式(1)または式(2)を最大化する直接的な変分アプローチです。
データが与えられた場合、スペクトル法では、単純に(そして古典的に)期待値を経験的平均に置き換えます(これは経験的モーメントの使用に対応します)。そして、正則化を追加する可能性があります。つまり、(( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} ) を (( \rho \Sigma_p + (1-\rho) \Sigma_q + \lambda I)^{-1} ) に置き換えます。これは、すべての (\rho) に依存する最小二乗問題に対してリッジ回帰を実行することに対応します。
利点は、理論的議論またはシミュレーションのいずれかで測定できます。以下に両方を示します。
ガウスモデルでの高次元評価。 最も単純なセットアップは、共通の共分散行列を持つガウスケースです(これは
[9] で徹底的に探求します)。正則化されていない推定器はアフィン変換に対して不変であるため、平均 (\Delta \in \mathbb{R}^m) と共分散恒等行列を持つガウス分布 (p) と、平均 (0) と共分散恒等行列を持つガウス分布 (q) を考えることができます。次元 (m) とサンプル数 (n_p) および (n_q) が固定比率で無限大に増加する高次元極限では、変分推定器とスペクトル推定器の性能は (s = | \Delta|^2) と「アスペクト比」(\alpha_p = \frac{m}{n_p}) および (\alpha_q = \frac{m}{n_q}) にのみ依存します。線形特徴を考慮します。
このセットアップは、真の対数密度比が (x) のアフィン関数であるため、変分推定器に有利ですが、新しいスペクトル推定器はバイアスを発生させます(これは明示的に特徴付けられます。
[9] を参照)。増加したバイアスは、分散の減少によって補償されるでしょうか?これは、(n_p, n_q, m) が固定比率 (\alpha_p = \frac{m}{n_p}) および (\alpha_q = \frac{m}{n_q}) で無限大に増加する高次元領域で、ランダム行列理論
[11] または凸ガウス最小最大定理(CGMT)
[12] を使用して正確に分析できます。これにより、(正則化されていない)変分アプローチとスペクトルアプローチの漸近性能を計算できます。固定 (s=1) の場合、(\alpha_p) および (\alpha_q) のすべての値について(詳細については
[9] を参照)。
[画像: スペクトル推定と変分推定の性能差。負の値はスペクトル法の勝利、正の値は変分法の勝利を示す。]
期待されるように、観測数が多い場合((\alpha_p,\alpha_q) が小さい場合)、バイアスが減少するため変分法がより良い性能を発揮しますが、観測数が少ない場合、その分散の増加によりスペクトル法が好まれます。
シミュレーション。 2次元((d=2))のデータと非線形対数密度を持つ単純な状況を考えます。これはReLUに基づくランダム特徴量を使用して学習されます。つまり、(\varphi(x)
i = (w_i^\top x + b_i)+) で、(i \in {1,\dots,m}) はランダムに選択された ((w_i,b_i) \in \mathbb{R}^{d+1}) であり、観測数 (n = n_p = n_q) が増加します。一般的な分布間のKLダイバージェンスを推定する問題は、ノンパラメトリックな問題であり、収束率は次元の呪いを示します。(n) が非常に大きいか、特別なスパース性仮定がない限り、高次元では(特徴学習を使用する場合の以下を参照)正確に推定することはできません。
KLダイバージェンスがピアソンダイバージェンス(これは密度推定に最小二乗法を使用する伝統的な方法です
[22, 23, 24)、および変分法よりも優れていることがわかります。ただし、観測数が多い場合は、変分法とKLスペクトル法が同じになります。
[画像: (D(p|q)) を基準とした (v) の推定値の比較。データは ([0, 1]^2) で、(q) は一様分布、(p) は独立成分を持ち、(\log(dp/dq)) がいくつかのコサインの和である場合。ReLUランダム特徴量、(m = 512) を使用。]
相互情報量と条件付き推定
情報理論では、KLダイバージェンスはランダム変数間の独立性の尺度としてよく使用され、相互情報量につながります。積空間 (\mathcal{X}
_1 \times \mathcal{X}
_2) と結合分布 (p(x_1,x_2)) が与えられた場合、(q(x_1,x_2)) を、(p) と同じ周辺分布を持つ独立成分の分布と考えることができます。これは、通常のグラフィカルモデルの規約に従って、(q(x_1,x_2) = p(x_1) p(x_2)) と書きます。この場合、最適な対数相対密度は次のようになります。
$$ \log \frac{ p(x_1,x_2)}{p(x_2) p(x_1)} = \log \frac{ p(x_2|x_1)}{p(x_2)}.$$
したがって、閉形式推定のフレームワークにより、条件付き密度推定 (\log p(x_2|x_1)) を実行できます((\log p(x_2)) の追加の必要性があります)。これは一般に任意の (\mathcal{X}
_2) に対して行うことができますが、(\mathcal{X}
_2) が有限の場合、閉形式推定はソフトマックス回帰を実行する正確な方法となります。
ただし、この新しい閉形式推定は、one-hotエンコーディングに対する分類の最小二乗法とは同等ではありません。これは本質的に、ピアソンダイバージェンスから得られるポテンシャルが行うこと(そして古典的な正則化正準相関分析につながる)です。下の図では、2次元の単純なガウスデータの場合、KLダイバージェンスの新しいスペクトル推定器がソフトマックス回帰と「類似」(ただし同一ではない)の振る舞いをすることがわかります。
[画像: 条件付き密度の推定値の比較。クラスのいずれかが支配的になる表面を描画。分類データから学習(同じ色のデータに基づく)。左:ソフトマックス回帰、右:新しい閉形式スペクトル推定器。]
対数密度が二次関数であるため(クラス条件付き共分散行列が等しくないため)、二次特徴量を追加すること、および古典的な二乗損失(ピアソンダイバージェンス、つまり (\nu) が (\rho=0) のディラック測度であることの使用に対応)と比較することも興味深い。より多くの特徴量を使用すると、すべての手法はより類似した分類領域を持つ傾向があります(特徴量のセットがすべての実数値関数をモデル化するのに十分大きい場合、それらは同一になります)。なお、右上では、最小二乗法のマスキング問題が見られます。一部のクラスが完全に消滅します(これは下の右側のプロットで特徴量を追加することで解決されますが、不自然なコスト関数を示しています)。
[画像: 条件付き密度の推定値の比較。クラスのいずれかが支配的になる表面を描画。分類データから学習(同じ色のデータに基づく)。上:線形特徴量を使用、下:二次特徴量を使用。左から右へ:ソフトマックス回帰、KLダイバージェンスのスペクトル推定、ピアソンダイバージェンスのスペクトル推定。]
計算量。 (k) クラスで次元 (d) の特徴ベクトルを持つ機械精度での推定値を得るために、ソフトマックス回帰をニュートン法で実行する場合、ニュートン反復ごとに (O( nd^2 k^2 + d^3 k^3)) かかります。一方、閉形式推定器は、1回の固有値分解に (O(d^2 n + kd^3)) しかかからず、これは大幅な改善です。特徴学習で勾配ベースのアルゴリズムを使用する場合、両方の計算時間を削減できます。
特徴学習
線形モデルは優れていますが、ディープラーニングが主流になって以来学んだ教訓の1つは、エンドツーエンドでより優れた特徴学習が必要であり、定義済みの特徴量の大きなセットは、特に未知の(線形または非線形)潜在変数への適応性などの理由で十分ではないということです。KLダイバージェンスの下限である変分フレームワークでは、これは単純に式(7)の (F(p|q, \varphi)) を (\varphi) に関して最大化し、(F(p|q, \varphi)) が (\varphi) のモーメントに関して凸であるという事実を利用します。
実際、(\Sigma_p,\Sigma_q), および (\mu_p – \mu_q) のモーメントの凸関数として、定数に次の項を加えたもので下限されます。
$$ {\rm tr} \big( M \mathbb{E}
_p \[ \varphi \varphi^\top \] \big) + {\rm tr} \big( N \mathbb{E}
_q \[ \varphi \varphi^\top \] \big) + 2c^\top \big( \mathbb{E}
_p \[\varphi] – \mathbb{E}
_q[\varphi]),$$ ここで (M,N) は行列、(c) はベクトルであり、任意の (\bar\varphi) から計算できます(これはポテンシャル (v) および (w) を計算するために必要なものであり、下限が (\varphi = \bar\varphi) に対してタイトになるように選択されます(参考文献の下のセクションを参照))。これにより、期待値最大化(EM)アルゴリズム
[17] に似た最小化最大化アルゴリズム
[15, 16] が可能になります。EMとの関連により、オンラインEM
[18] など、そこで開発された多くの計算トリックを再利用して、アルゴリズムを大規模ネットワークにスケーラブルにし、(\varphi) をパラメータ化し、多数の観測を処理することができます。これについては次の投稿で詳しく説明します。
結論
このブログ投稿では、指数関数の平均値における分散爆発を回避する相対密度推定のための新しいフレームワークを紹介しました。これは、安定した最小二乗問題の連続体によって実現され、単一の一般化固有値分解によって計算可能になりました。正規化が必要なモデルの分散爆発問題に対処することに加えて、正規化モデル(合計/積分が計算できるモデル)に対する意図しない結果として、ソフトマックス回帰の閉形式推定器が得られました。
最近の論文
[7] は、特にKLダイバージェンスの推定率に関して、時にはミニマックス率と線形潜在変数への部分的な適応性を持つ他の結果を探求しています。全体として、道のりは長いですが、この新しいフレームワークは、クロスエントロピー損失と対数和指数が支配的なニューラルネットワークの最終層の代替となる可能性を秘めていると私は見ています。これについては次の投稿で詳しく説明します。
謝辞とツールの使用に関する開示。 有益な明確化の提案をしてくれた Frederik Kunstner と Nicolas Flammarion に感謝します。Frontier LLMモデルは、図の生成とタイプミスの修正に使用されました。
参考文献
[1] XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(11):5847–5861, 2010.
[2] Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2025.
[3] Monroe D. Donsker and S. R. Srinivasa Varadhan. Asymptotic evaluation of certain Markov process expectations for large time-III. Communications on Pure and Applied Mathematics, 29(4):389–461, 1976.
[4] László Györfi and Igor Vajda. A class of modified Pearson and Neyman statistics. Statistics & Risk Modeling 19(3): 239-252, 2001.
[5] Lucien Le Cam. Asymptotic Methods in Statistical Decision Theory. Springer Science & Business Media, 2012.
[6] Gene H. Golub, Michael Heath, and Grace Wahba. Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21(2):215-223, 1979.
[7] Francis Bach. A Spectral Framework for Closed-Form Relative Density Estimation. Technical report, arXiv:2605.10668, 2026, to appear in Advances of Neural Processing Systems (NeurIPS).
[8] Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, 1996.
[9] Francis Bach. Regularized Variational and Spectral Log-Density-Ratio Estimation in the Gaussian Location Model. Technical report, arXiv:2607.01895, 2026.
[10] Didier Henrion, Milan Korda, and Jean Bernard Lasserre. The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs. World Scientific, 2020.
[11] Zhidong Bai and Jack W. Silverstein. Spectral Analysis of Large Dimensional Random Matrices. Springer, 2nd edition, 2010.
[12] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. The Gaussian min-max theorem in the presence of convexity. Technical report, arXiv:1408.4837, 2014.
[13] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer, 2009.
[14] Andrzej Cichocki and Shun-ichi Amari. Families of alpha-beta- and gamma-divergences: Flexible and robust measures of similarities. Entropy, 12.6:1532-1568, 2010.
[15] David R. Hunter and Kenneth Lange. A tutorial on MM algorithms. The American Statistician, 58(1):30–37, 2004.
[16] Julien Mairal. Stochastic majorization-minimization algorithms for large-scale optimization. In Advances in Neural Information Processing Systems, 2013.
[17] Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: series B (methodological) 39(1):1-22, 1977.
[18] Olivier Cappé and Eric Moulines. On-line expectation–maximization algorithm for latent data models. Journal of the Royal Statistical Society Series B: Statistical Methodology, 71(3):593–613, 2009.
[19] Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. AAAI Conference on Artificial Intelligence, 2008.
[20] Francis Bach. Sum-of-squares relaxations for information theory and variational inference. Foundations of Computational Mathematics, 25.3: 865–903, 2025.
[21] Keiji Matsumoto. A new quantum version of f-divergence. In Nagoya Winter Workshop: Reality and Measurement in Algebraic Quantum Theory, pages 229–273. Springer, 2015.
[22] Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density Ratio Estimation in Machine Learning. Cambridge University Press, 2012.
[23] Zaid Harchaoui, Francis Bach, and Eric Moulines. Testing for homogeneity with kernel Fisher discriminant analysis. Technical Report 0804.1026, arXiv, 2008.
[24] Mónica Ribero, Antonin Schrab, and Arthur Gretton. Regularized (f)-divergence kernel tests. Technical Report 2601.19755, arXiv, 2026.
[25] Michel Broniatowski and Amor Keziou, Minimization (\varphi)-divergences on sets of signed measures, Studia Scientiarum Mathematicarum Hungarica, 43(4):403–442, 2006.
[26] Michael U. Gutmann and Aapo Hyvärinen. Noise-Contrastive Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics. Journal of Machine Learning Research, 13(11):307−361, 2012.
SDPとの連携
新しいダイバージェンスを式(7)で定義しました。
$$F(p|q,\varphi) = \frac{1}{2} \int_0^1 ( \mu_p , – \mu_q)^\top( \rho \Sigma_p + (1-\rho) \Sigma_q)^{-1} ( \mu_p, – \mu_q) d\nu(\rho). $$ これは (\Sigma_p), (\Sigma_q), および (\mu_p – \mu_q) に関して凸であり、ここには良い双対理論があります。これは、上記で定義された (M,N,2c) が実際には上記のパラメータに関する微分であることを示しています。主な結果は、
[7] で示されています。
$$F(p|q,\varphi) = \ \sup
_{M,N,c} {\rm tr}(\Sigma_p M) + {\rm tr}(\Sigma_q N) + 2c^\top (\mu_p – \mu_q) \qquad \qquad \qquad \qquad$$
$$ \qquad \qquad \qquad \qquad \mbox{ such that } \ \forall \lambda \geqslant 0, \left( \begin{array}{cc} \lambda M + N & (\lambda-1)c \ (\lambda-1)c^\top & -f(\lambda) \end{array} \right) \preccurlyeq 0.$$ 上記の半正定値制約は、ポテンシャル (v(x)) と (w(x)) が (\forall x \in \mathcal{X}, \ w(x) + f^\ast(v(x)) \leqslant 0) を満たすことを正確に意味します。これは、半正定値計画法が平方和による最適化に使用できるのと(例えば、
[10] を参照)、全く同じ方法です。実際、任意の (\lambda \geqslant 0) に対して、次のようになります。
$$ \lambda v(x) + w(x) -f(\lambda) = { \varphi(x) \choose 1}^\top \left( \begin{array}{cc} \lambda M + N & (\lambda-1)c \ (\lambda-1)c^\top & -f(\lambda) \end{array} \right) { \varphi(x) \choose 1} \leqslant 0,$$ これは (w(x) + f^\ast(v(x)) \leqslant 0) と同等です。
以前の研究
[20] では、正規化された特徴マップ (| \varphi(x)|=1) を持つ同様のフレームワークを開発しました。これにより、(D(p|q)) の下限は次のようになります。
$$ \sup
_{M,N} {\rm tr}(\Sigma_p M) + {\rm tr}(\Sigma_q N) \ \mbox{ such that } \ \forall \lambda \geqslant 0, \ \lambda M + N + f(\lambda) I \preccurlyeq 0, $$ これは、量子情報理論
[21] で一般的な式、つまり次の値に等しくなります。
$$ {\rm tr} \big[ \Sigma_q f( \Sigma_q^{-1/2} \Sigma_p \Sigma_q^{-1/2})\big] .$$ 最大の新規性は、正規化されていない特徴量を使用する必要がなくなったことです。これにより、特徴学習が大幅に容易になります。