2025-11-15T09:01:12.242557

Numerical Methods for Kernel Slicing

Rux, Hertrich, Neumayer

Kernels are key in machine learning for modeling interactions. Unfortunately, brute-force computation of the related kernel sums scales quadratically with the number of samples. Recent Fourier-slicing methods lead to an improved linear complexity, provided that the kernel can be sliced and its Fourier coefficients are known. To obtain these coefficients, we view the slicing relation as an inverse problem and present two algorithms for their recovery. Extensive numerical experiments demonstrate the speed and accuracy of our methods.

academic

カーネルスライシングの数値計算法

基本情報

論文ID: 2510.11478
タイトル: Numerical Methods for Kernel Slicing
著者: Nicolaj Rux (ケムニッツ工科大学)、Johannes Hertrich (パリ・ドーフィーヌ大学-PSL およびInria Mokaplan)、Sebastian Neumayer (ケムニッツ工科大学)
分類: math.NA, cs.NA
発表日: 2025年10月14日
論文リンク: https://arxiv.org/abs/2510.11478v1

要約

カーネル関数は機械学習における相互作用関係のモデル化に不可欠である。しかし、関連するカーネル関数の総和の直接計算の計算複雑度はサンプル数に対して二次的に増加する。最近のフーリエスライシング法は、カーネル関数がスライス可能であり、そのフーリエ係数が既知である場合、複雑度を線形に削減できる。これらの係数を得るため、本論文はスライシング関係を逆問題として扱い、2つの復元アルゴリズムを提案する。大規模な数値実験により、提案手法の速度と精度が実証されている。

研究背景と動機

中核的問題

カーネル法は機械学習において密度推定、サポートベクトルマシン分類、主成分分析、最大平均乖離度(MMD)などのタスクに広く応用されている。これらの応用の計算ボトルネックは通常、以下の形式の式の評価である：

$s_m := \sum_{n=1}^N F(\|x_n - y_m\|)w_n, \quad m = 1,\ldots,M$

ここで $F \in C([0,\infty))$ は動径基底関数、 $x_1,\ldots,x_N, y_1,\ldots,y_M \in \mathbb{R}^d$ はサンプル点、 $w \in \mathbb{R}^N$ は重みである。

計算複雑性の課題

直接計算には $O(NMd)$ 回の演算が必要であり、大規模データセットに対しては実行不可能である。高速フーリエ総和や高速多重極法などの古典的手法は複雑度を $O(M+N)$ に削減できるが、高速フーリエ変換または空間分割に依存するため、次元 $d > 4$ の場合に指数的な依存性が生じ、実用的ではない。

スライシングアルゴリズムの利点

スライシングアルゴリズムの基本的な考え方は、以下を満たす関数 $f \in L^1_{loc}([0,\infty))$ を探すことである：

$F(\|x\|) = \frac{1}{\omega_{d-1}} \int_{S^{d-1}} f(|\langle\xi, x\rangle|)d\xi$

ここで $\omega_{d-1} = 2\pi^{d/2}/\Gamma(d/2)$ は $d$ 次元球面の表面測度である。積分を離散化することにより、カーネル総和は1次元の場合に簡略化され、高速フーリエ総和を用いて効率的に計算できる。

核心的貢献

スライシング関数復元問題を逆問題として形式化し、完全な理論的枠組みを確立
2つの数値アルゴリズムを提案し、高速フーリエ総和に必要なコサイン級数係数を復元
厳密な誤差推定を提供し、前向き誤差とスライシング誤差の分析を含む
広範な数値実験により、様々なカーネル関数における手法の効率性と精度を検証
手法の適用範囲を拡張し、解析的知識なしに未知のスライシング関数を持つカーネルを処理

方法の詳細

タスク定義

動径基底関数 $F: [0,\infty) \to \mathbb{R}$ が与えられたとき、スライシング関係 $F = S_d[f]$ を満たす関数 $f: [0,\infty) \to \mathbb{R}$ を探す。ここで $S_d$ は一般化されたRiemann-Liouville分数積分演算子である：

$S_d[f](s) = \int_0^1 f(ts)\varrho_d(t)dt$

ここで $\varrho_d(t) := c_d(1-t^2)^{(d-3)/2}$ 、 $c_d := \frac{2\Gamma(d/2)}{\sqrt{\pi}\Gamma((d-1)/2)}$ である。

モデルアーキテクチャ

1. 最適化問題の構築

スライシング関数復元を正則化最小化問題に変換する：

$\hat{a} = \arg\min_{a \in \mathbb{R}^K} \|S_d[f_a] - F\|_H^2 + \tau^2\|f_a\|_G^2$

ここで $f_a = C^{-1}[a]$ は $K$ 項コサイン級数である：

$f_a(t) = a_0 + \sqrt{2}\sum_{k=1}^{K-1} a_k \cos(\pi kt)$

2. 空間領域法（アルゴリズム1）

行列構築： $h_k := S_d[g_k]$ を計算。ここで $g_k$ はコサイン基底関数
離散化：Gauss-Legendre求積法を用いて積分を近似
求解：最小二乗問題 $\|\hat{H}^T a - \hat{b}\|_2^2 + \tau^2\|Da\|_2^2$ を解く

3. 周波数領域法（アルゴリズム2）

演算子表現：演算子 $S := C \circ S_d \circ C^{-1}$ の行列表現を構築
係数計算：関係 $S_{j,k} = S_d[\text{sinc}(\cdot + j) + \text{sinc}(\cdot - j)](k)$ を利用
最適化求解：周波数領域空間で正則化問題を解く

技術的革新点

理論的基礎：異なる関数空間上のスライシング演算子 $S_d$ の有界性理論を確立
数値安定性：Tikhonov正則化により病態問題を処理
誤差分解：総誤差を前向き誤差とスライシング誤差の2つの部分に分解
収束性分析：関数の滑らかさの仮定の下での収束率を証明

実験設定

データセット

複数の動径基底関数を用いてテストを実施：

ガウス: $F(s) = \exp(-s^2/(2c^2))$
ラプラス: $F(s) = \exp(-c|s|)$
逆多二次関数(IMQ): $F(s) = (c^2 + s^2)^{-1/2}$
薄板スプライン(TPS): $F(s) = (cs)^2\log(|cs|)$
対数カーネル(LOG): $F(s) = \log(|cs|)$
バンプ関数および多二次関数(MQ)

評価指標

前向き誤差： $|F_K(s) - F(s)|$
相対L2誤差： $\|s - \hat{s}\|_2/\|s\|_2$
実行時間比較

比較手法

直接法：解析解 $f = S_d^{-1}[F]$ が既知の場合の打ち切りフーリエ級数
PyKeOps：高度に最適化されたGPU暴力計算パッケージ
3つの構成：S-L2-H1、F-L2-H1、F-H1-H1

実装の詳細

$L = 2^{10}$ 個の求積点を使用
領域内 $K = 2^8$ 個のコサイン係数、値域内 $J = 2^{10}$ 個
正則化パラメータ $\tau \in \{10^{-6}, 10^{-7}, 10^{-4}\}$

関数	S-L2-H1	F-L2-H1	F-H1-H1	Direct
ガウス	6.53×10⁻³	6.62×10⁻³	6.61×10⁻³	6.56×10⁻³
ラプラス	8.58×10⁻³	8.32×10⁻³	1.30×10⁻²	5.90×10⁻³
IMQ	2.25×10⁻³	2.27×10⁻³	2.28×10⁻³	2.26×10⁻³
LOG	1.00×10⁻¹	1.80×10⁻¹	1.55×10⁻¹	2.98×10¹