技術的概要：メトリック学習および類似度学習における深層 ReLU ネットワークを用いた一般化解析

1. 問題定義

メトリック学習および類似度学習は、ラベルに基づいて観測ペア $(x, x')$ 間の距離または類似度を推定する関数 $d(x, x')$ を学習することを目的とする。性能は通常、一般化誤差（真のリスク）$E(d) = \mathbb{E}_{Z,Z'}[\ell(\tau(Y, Y')d(X, X'))]$ によって測定される。ここで、$\ell$ は凸な代替損失関数（例えば、ヒンジ損失）であり、$\tau$ はラベルが一致するかどうかを示す縮小関数である。

メトリック学習における推定誤差（固定された仮説空間内の最良の関数への経験的最小化子の収束）に関する理論的研究は広範に存在するが、近似誤差（仮説空間内の最良の関数と真の最適メトリック $d_\rho$ の間のギャップ）に対する厳密な理解は欠けていた。従来の研究は主に、マハラノビス距離 $d_M(x, x') = (x-x')^\top M (x-x')$ やペアワイズ類似度 $s_M(x, x') = x^\top M x'$ などの線形仮説空間に焦点を当てていた。これらの空間は表現力に限界があり、その複雑さは入力次元 $p$ によって制約される（具体的には $O(p^2)$）。そのため、推定誤差が急速に収束した場合でも、近似誤差が大きくなる可能性がある。

本論文は、真のメトリック $d_\rho$ の特定の構造を調査し、深層 ReLU ネットワークを用いてそれを効果的に近似できる仮説空間を構築することにより、一般化解析におけるこのギャップに対処する。

2. 手法

2.1 真のメトリックの明示的表現

著者らはまず、ヒンジ損失に対する真のメトリック $d_\rho$ の明示的な表現を導出する。損失の条件付き期待値を最小化することにより、真のメトリックが 2 つのサンプルが同じラベルを持つ条件付き確率によって決定されることを証明する：
$$\eta(x, x') = \mathbb{P}(Y = Y' \mid X=x, X'=x') = \langle P_x, P_{x'} \rangle$$
ここで、$P_x$ は $x$ が与えられたときのラベルの条件付き確率ベクトルである。真のメトリックは以下のように示される：
$$d_\rho(x, x') = \text{sgn}(1 - 2\eta(x, x')) = \text{sgn}\left(1 - 2\sum_{i=1}^m p_i(x)p_i(x')\right)$$
ここで、$p_i(x) = \mathbb{P}(Y=y_i \mid X=x)$ である。この表現は、メトリックを学習することが、条件付き確率 $p_i(x)$ とそれらの内積を学習することに等価であることを明らかにする。

2.2 構造化された深層 ReLU ネットワークの構築

$d_\rho$ を近似するために、著者らは 3 つの部分から構成される構造化された深層 ReLU ネットワーク $d(x, x')$ を構築する：

1. サブネットワーク（$h_i$）： 条件付き確率 $p_i(x)$ を近似する $m$ 個の深層 ReLU ネットワーク。
2. 積近似（$\phi$）： 乗算関数 $xy$ を近似する深層 ReLU ネットワーク。
3. 符号近似（$F_a$）： 符号関数 $\text{sgn}(\cdot)$ を近似する 2 層 ReLU ネットワーク。これは $F_a(t) = \frac{1}{a}(\sigma(t+a) - \sigma(t-a) - a)$ として定義される。

最終的な仮説は以下のように定義される：
$$d(x, x') = F_a\left(1 - 2\sum_{i=1}^m \phi(h_i(x), h_i(x'))\right)$$
この構造は、導出された $d_\rho$ の形式を明示的に模倣する。

2.3 誤差解析フレームワーク

著者らは、超過一般化誤差 $E(\hat{d}_S) - E(d_\rho)$ を近似誤差と推定誤差に分解することで解析する：

1. 近似誤差： 条件付き確率の滑らかさ（ソボレフ空間 $W^{r, \infty}$）とツィャバコフのノイズ条件を用いて、構造化されたネットワークによる $d_\rho$ の近似誤差を評価する。
2. 推定誤差： 仮説空間の擬似次元と、ノイズ条件から導出された分散 - 期待値評価を用いて、経験的リスクと真のリスクの間の偏差を評価する。
3. トレードオフ： ネットワークの複雑さ（深さ、幅、重みの数）とサンプルサイズ $n$ のバランスを取ることで、超過リスクの明示的な率を導出する。

3. 主要な貢献

• 最初の明示的な超過リスク評価： 本論文は、推定誤差と近似誤差の両方をカバーする、メトリック学習および類似度学習に対する最初の一般化解析を提供し、明示的な超過リスク評価を与える。従来の研究は推定誤差のみを評価していた。
• 明示的な学習率： 穏やかな条件（条件付き確率のソボレフ滑らかさとツィャバコフのノイズ条件）の下で、著者らは以下の順序の学習率を導出する：
  $$O\left(n^{-\frac{(\theta+1)r}{p+(\theta+2)r}}\right)$$
  （対数因子を除く）。ここで、$p$ は入力次元、$\theta$ はノイズパラメータ、$r$ は滑らかさ指数である。
• 構造化された仮説空間： 真のメトリックの理論的形式と整合する特定の深層 ReLU 構造の構築。このようなネットワークが有利な近似および推定評価を達成し得ることを実証する。
• 構造的洞察：
  • バイアス項： メトリック学習でよく用いられるバイアス項 $b$ は、真のメトリックの理論的特徴付けに本質的ではないことを示す。これは単に定数シフトを引き起こすに過ぎない。
  • 有限ラベル： ラベル空間 $Y$ は有限であるべきであると主張される。$Y$ が連続である場合、真のメトリックはほとんど確実に一般化された定数となる。
  • 対称性と自己類似性： 真のメトリックが対称であることが証明される。さらに、凸かつ単調非減少の損失関数のもとで、同一サンプル間の距離が異なるサンプル間の距離以下となる条件を調査し、マハラノビス距離のような対称モデルに対する理論的根拠を提供する。

4. 実験結果

著者らは、2 つの一連の実験を通じて理論的知見を実証的に検証する：

1. 実世界データ（FashionMNIST）：

   • 提案された構造化モデルを、距離ベースの基準 $\|f(x) - f(x')\|^2 - b$ を使用する標準的な深層メトリック学習（DML）のベースラインと比較した。
   • 中程度の難易度と高い難易度のクラスペアの両方において、提案モデルはわずかに高いバランス精度を達成した（中程度のペアで 93.86% 対 93.67%、高い難易度のペアで 74.87% 対 74.30%）。
   • 結果は、提案モデルが基礎となる類似度構造をより効果的に捉えていることを示唆する。

2. 合成データ：

   • 真のメトリックが標準的な距離ベースの直観に反する内積構造によって支配される制御実験を設計した（具体的には、「不確実な領域」内のペアは、幾何学的距離ではなくラベル確率に基づいて類似または非類似となり得る）。
   • 提案モデルは、不確実性のレベル（$\lambda$）とクラス数（$m$）が変化する中で、ほぼ最適な精度（約 99.9%）を維持した。
   • 対照的に、距離ベースの DML ベースラインの性能は、不確実な領域が拡大するかクラス数が増加するにつれて著しく低下し、困難な領域では約 75% まで落ち込んだ。これは、類似度構造が純粋に幾何学的でない場合、距離ベースのメトリックが失敗するという理論的予測を確認するものである。

5. 意義と主張

本論文は、制限された線形仮説空間内での推定誤差のみに焦点を当てた従来の解析の限界を超え、メトリック学習および類似度学習に対する明示的な超過リスク評価を提供する最初の研究であると主張する。

真のメトリックの特定の構造を利用することで、著者らは深層 ReLU ネットワークが万能近似器としてだけでなく、学習問題の確率的性質と整合する構造化されたツールとしても理論的に正当化され得ることを実証する。導出された学習率は、入力次元、ノイズ、滑らかさの間の相互作用を浮き彫りにし、これらのタスクにおける一般化に対するより微妙な理解を提供する。

著者らは、自身の仮定が証明手法（一様近似に依存）に合わせて調整されていることに留意し、他の損失関数（例えばロジスティック損失）や代替のノイズ条件への拡張を今後の課題として残している。