Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks

技術要約：O-minimal構造におけるReLUニューラルネットワークを用いたバイナリ分類タスクの高速近似と学習

問題設定
本論文は、決定集合 $A \subseteq [-1/2, 1/2]^n$ が実体のO-minimal拡大（o-minimal expansion）内で定義されているような、バイナリ分類問題について調査している。深層ニューラルネットワークは経験的な成功を収めているが、その近似能力や統計的学習可能性に関する理論的理解は、ターゲットとなる集合の滑らかさやBarron型の関数クラスといった、特定の構造的仮定に依存することが多い。著者らは、複雑な決定境界において成立しない可能性のあるグローバルな滑らかさの仮定に依存することなく、O-minimal性によって定義される「行儀の良い（tame）」集合のより広いクラスに対して、定量的な近似および学習率を確立することを目的としている。

手法
著者らは、O-minimal幾何学における細胞分解定理に由来する概念として、定義可能な集合の古典的なプロキシ（代理）となる**traceable sets（追跡可能集合）**というクラスを導入する。

1. Traceable Sets（追跡可能集合）: 集合 $A$ は、$m$-traceableであるとは、その集合の境界をファイバーごとに定義する有界な $C^m$ 写像 $f_i, g_i$ を用いて、帰納的に構成できることを指す。具体的には、各層が滑らかな関数によって上下に抑えられた「ホライゾン（水平線）」関数の列として構築される。著者らは、このような集合の有限個の互いに素な和集合として、$(m, \ell)$-traceable集合を定義している。
2. 拡張特性（Extension Properties）: 近似を容易にするため、境界関数 $f_i, g_i$ が、ソボレフノルムが有界な全領域上の $C^m$ 関数へと拡張可能であるという$(m, B)$-拡張特性を課している。
3. 近似戦略: コアとなる近似手法は以下の通りである：
   • 「ホライゾン関数」（滑らかなグラフによって境界付けられた領域の特性関数）を、ReLUニューラルネットワークを用いて近似する。これは、滑らかな関数とその合成の近似に関する既存の結果を活用している。
   • ReLUベースの最小および最大操作（$\chi_{\cap} = \min$ および $\chi_{\cup} = \max$ であるため）を用いて、これらの近似を合成することで、traceable集合の特性関数を構成する。
   • 拡張の仮定の下で、これらの集合のフロンティア（境界）のルベーグ測度がゼロであることを利用し、集合の閉包を近似することが $L^p$ 近似において十分であることを保証する。
4. 学習フレームワーク: 統計的学習分析は、導出された近似率と、ReLUニューラルネットワーククラスのエントロピー推定（被覆数）を組み合わせる。著者らは、構築された特定のニューラルネットワーククラスに対して、ヒンジ損失を用いた経験リスク最小化（ERM）を適用し、汎化境界を導出する。

主要な貢献と結果

• 定量的な近似率: 任意の $(m, \ell)$-traceable集合 $\Omega \subseteq [-1/2, 1/2]^n$ の特性関数 $\chi_\Omega$ は、精度 $\epsilon$ でReLUニューラルネットワーク $\Phi_\epsilon$ によって $L^p$ ノルムの意味で近似可能であることを証明している。

  • ネットワークサイズ: 必要な非ゼロ重みの数（サイズ）は $O(\epsilon^{-p(n-1)/m})$ である。
  • 深さ: ネットワークの深さは $\epsilon$ に依存せず、具体的には $O(\log(\ell n) + \log(m))$ である。
  • 重み: 重みは $1/\epsilon$ に対して高々多項式的に増大する。
  • この結果は、traceableな領域上で区分的に滑らかな定義可能な写像 $f: [-1/2, 1/2]^n \to \mathbb{R}$ の部分クラスにも拡張される。

• 統計的学習率: ドメインから一様に抽出された $N$ 個の独立なサンプルに対し、構築されたReLUネットワーククラスに対する経験リスク最小化の学習率を導出している。

  • 得られる分類器の期待誤分類誤差は、任意の微小な多項式損失因子 $N^\kappa$ を考慮すると、$O(N^{-m/(m+pn-p)})$ で抑えられる。
  • このレートは、近似誤差の境界と、仮説クラスの被覆エントロピーを組み合わせることによって導かれる。

• O-minimal構造への適用: 著者らは、「m-admissible」な定義可能なコレクション（細胞分解に関する一様な境界を持つ、定義可能な集合のファイバーのコレクション）が、traceable集合の特性を満たすことを示している。したがって、導出された近似および学習率は、これらの定義可能なコレクションに直接適用できる。

意義と主張
本論文は、分類理論における正則性の数学的に堅牢な概念として、O-minimal構造における定義可能性に基づいたものを提供することを主張している。近似理論、統計的学習、および最適化を同時に研究するために必要な解析的特徴（traceabilityおよび滑らかな拡張）を分離することで、著者らは、O-minimal性が広範な実用的な決定集合を捉えつつ、強力で定量的な近似および推定率を可能にすることを示している。これはBarron型の設定とは対照的であり、Barron型の設定は関数の合成において困難が生じることがあるが、O-minimalフレームワークは、定義可能な写像の合成が定義可能であり続けることから、深層ニューラルネットワークに見られるアフィン写像と非線形活性化の繰り返しの合成を自然に受け入れることができる。

結果は、決定境界が（O-minimal構造内で）「行儀の良い（tame）」ものである場合、境界がグローバルに滑らかである必要はなく、ReLUニューラルネットワークが滑らかさのパラメータ $m$ と次元 $n$ に応じて最適または準最適なレートを達成できることを示唆している。論文では、これらのレートが特定の定義可能な集合および写像の部分クラスに対して導出されていること、および学習率が、O-minimal構造における定義可能なコレクションに固有の一様な有限性（連結成分の一様な境界およびVC次元）に依存していることが明記されている。