Правда ли KAN лучше MLP? Свойство разделения глубины между двумя архитектурами / forpes.ru

Главная
Правда ли KAN лучше MLP? Свойство разделения глубины между двумя архитектурами

Правда ли KAN лучше MLP? Свойство разделения глубины между двумя архитектурами +12

22.07.2025 11:15

E_P_H_E_M_E_R_I_S 2 961 Источник

Введение

Прошлым летом в свет вышла новая архитектура нейронных сетей под названием Kolmogorov-Arnold Networks (KAN). Основная статья есть в открытом доступе на архиве по следующей ссылке. На момент выхода статьи эта новость произвела фурор в мире машинного обучение, так как KAN показывали существенный прирост в качестве аппроксимации различных сложных функций. На фото ниже видно, что ошибка новых сетей падает значительно быстрее при увеличении числа параметров.

графики RMSE на тестовой выборке к числу параметров у KAN и MLP на разных функциях

Однако, за все приходится платить, и цена таких маленьких значений функции ошибки - медленное обучение: KAN обучается примерно в 10 раз медленнее, чем старый добрый MLP. Из всего этого возникает вопрос: насколько все же уместно использование новой архитектуры вместо привычных всем MLP?

Конечно же, ответ на этот вопрос не столь однозначный: кому-то больше важна скорость обучения и работы модели, кому-то качество предсказаний. В поисках ответа я пришел к интересной задаче, которая легла в основу моей курсовой работы (полная версия по ссылке) и которую я собираюсь здесь изложить.

Разделение глубины и постановка задачи

Один из способов сравнить архитектуры - выявить так называемое свойство разделения глубины. Для MLP сетей оно заключается в следующем: пусть есть MLP сеть $\mathcal{N}_1$ глубины и MLP сеть $\mathcal{N}_{2}$ глубины , при этом , а ширина обоих сетей полиномиальна относительно размерности входного пространства (далее обозначаем через $\mathcal{poly}(d)$ ) если существует функция такая, что она приближается (в каком именно смысле будет понятно позднее) сетью $\mathcal{N}_1$ , но не приближается $\mathcal{N}_{2}$ , то говорят, что выполняется свойство разделения глубины между $\mathcal{N}_1$ и $\mathcal{N}_{2}$ .

Моя идея заключалась в том, чтобы попытаться установить подобное свойство, которое разделяло бы KAN и MLP. Конкретно, вопрос ставился следующим образом: пусть $\mathcal{K}$ - KAN глубины , ширины $\mathcal{poly}(d)$ и $\mathcal{N}$ - MLP сеть той же глубины и полиномиальной ширины. Существует ли такая функция , что она приближается $\mathcal{K}$ , но не приближается $\mathcal{N}$ ?

Для того, чтобы ответить на этот вопрос, нам придется вникнуть в устройство KAN, рассмотреть один из известных результатов разделения глубины для MLP сетей глубины 2 и 3 (ширины $\mathcal{poly}(d)$ ), а также объединить это все с помощью результата по преобразованию кусочно-линейного (станет понятно далее) KAN в MLP и обратно. Итак, начнем по порядку.

1. Устройство KAN

Для начала определим, что такое слой KAN.

Определение: Слой сети КАN (KAN-слой) с входной размерностью $n_{\text{in}}$ и выходной размерностью $n_{\text{out}}$ задаётся матрицей $\mathbf{\Phi} = \{\phi^{q}_{p}\}_{p=1,\ldots,n_{\text{in}}}^{q=1,\ldots,n_{\text{out}}}$ вещественных функций одной переменной $\phi^{q}_{p}\colon \mathbb{R} \to \mathbb{R}$ , которые мы называем функциями активации. Он представляет функцию

$\mathbf{\Phi}\colon\mathbb{R}^{n_{\text{in}}}\to\mathbb{R}^{n_{\text{out}}}$ $\mathbf{x} = (x_i)_{i=1,\ldots,n_{\text{in}}} \mapsto \mathbf{\Phi}\mathbf(x) = \left(\sum_{i=1}^{n_{\text{in}}}\phi^{j}_{i}(x_i)\right)_{j=1,\ldots,n_{\text{out}}}$

На фото ниже представлен в схематичном виде слой KAN (для удобства связи проведены только между входом и первым выходом, т.е $y_1 = \phi^{1}_{1}(x_1) + \phi^{1}_{2}(x_2) + \dots + \phi^{1}_{n_{in}}(x_{n_{in}})$ ).

Теперь определим KAN как композицию слоев.

Определение: Сеть Колмогорова-Арнольда (KAN) глубины — это композиция KAN-слоёв $\mathbf{\Phi}_{L-1} \circ \ldots \circ \mathbf{\Phi}_0$ .

Например, в случае, когда последний слой имеет выходную размерность 1, функция, задаваемая KAN, будет иметь такой страшный вид:

$f(\mathbf{x}) = \sum_{i_{L-1}=1}^{n_{L-1}}\phi^{L-1,i_{L}}_{i_{L-1}}\!\left(\ldots \sum_{i_1=1}^{n_1}\phi^{1,i_2}_{i_1}\left(\sum_{i_0=1}^{n_0}\phi^{0,i_1}_{i_0}(x_{i_0})\right)\ldots\right)$

где $n_\ell$ — входная размерность $\ell$ -го KAN-слоя $\mathbf{\Phi}_\ell = \{\phi^{\ell,q}_{p}\}_{p=1,\ldots,n_\ell}^{q=1,\ldots,n_{\ell+1}}$ .

Добавлю также пару слов про механизм обучения KAN. Изначально все $\phi^{\ell,q}_{p}$ задаются в виде сплайнов и некоторой нелинейной добавки , т.е $\phi^{\ell,q}_{p} = w_bb_p^{l,q}(x) + w_sspline_p^{l,q}(x)$ где

$spline_p^{l,q}(x) = \sum_{i}{c_{i}B_i(x)}$

есть линейная комбинация B-сплайнов. Для тех, кто не знаком со сплайнами, добавлю: сплайн - это просто кусочно-полиномиальная функция (многочлен фиксированной степени на каждом отрезке разбиения), а B-сплайны - базис в пространстве таких функций. На фото ниже можно посмотреть пример интерполяции функции сплайнами разной степени и B-сплайнами.

Сейчас и далее не столь важно, как строятся эти самые сплайны, мы хотим понять основной механизм обучения. При инициализации , $spline(x) \approx 0$ и определяется в соответствии с инициализацией Xavier. Далее происходит процесс обратного распространения ошибки: вычисляется градиент функции потерь по параметрам модели, в которые входят коэффициенты в реализациях сплайнов (обычно берутся кубические сплайны и итоговые функции являются гладкими), а также веса и , затем делается шаг в направлении антиградиента и процесс повторяется снова. При обучении происходит так называемое расширение сетки: каждые k шагов обучения мы увеличиваем число точек разбиения отрезков для аппроксимации сплайнами, тем самым увеличивая число параметров сети.

2. От KAN к MLP и обратно

Для начала введем несколько определений, которые понадобятся в этом разделе:

Определение: Кусочно-линейный KAN - это KAN, в котором все функции $\phi^{q}_{p}$ - кусочно-линейные.

Определение: Через $\mathbf{KAN}{(L, n, k)}$ будем обозначать семейство функций, задаваемых с помощью кусочно-линейного KAN глубины и ширины . Здесь - число сегментов кусочно-линейных функций $\phi^{q}_{p}\colon \mathbb{R} \to \mathbb{R}$ .

Определение: Через $\mathbf{ReLU}{(L, n)}$ будем обозначать семейство функций, задаваемых с помощью ReLU MLP сети глубины и ширины .

В попытках найти подход к изначальной задаче о разделении глубины я наткнулся на статью Relating Piecewise Linear Kolmogorov Arnold Networks to ReLU Networks, в которой показано, что кусочно-линейный KAN ширины и глубины может быть представлен ReLU MLP сетью глубины на 1 больше, ширины . Более строго, верна следующая теорема:

Теорема: Для любого кусочно-линейного KAN $f\colon \mathbb{R}^n \to \mathbb{R}$ существует ReLU-сеть $g\colon \mathbb{R}^n \to \mathbb{R}$ такая, что для всех $x \in \mathbb{R}^n$ , при этом после перехода к MLP глубина увеличивается на 1, а ширина становится равной , где k - число сегментов кусочно-линейных функций $\phi^{q}_{p}$ . (верно и для $f\colon \mathbb{R}^n \to \mathbb{R}^m$ ).

В этой же статье доказывается и обратный факт:

Теорема: Пусть $g\colon \mathbb{R}^n \to \mathbb{R}^m$ — это MLP-сеть с функциями активации из семейства $\mathcal{F}$ . Тогда существует KAN $f\colon \mathbb{R}^n \to \mathbb{R}^m$ с функциями активации, которые являются либо аффинно-линейными, либо принадлежат $\mathcal{F}$ , такой что для всех $x \in \mathbb{R}^n$ , при этом глубина и ширина сети не меняются при переходе к KAN. В частности, если — это ReLU-сеть, то существует кусочно-линейный KAN , для которого при всех $x \in \mathbb{R}^n$ .

Из этих теорема мы можем понять, что

$\mathbf{KAN}(L, n, k) \subseteq \mathbf{ReLU}(L+1, n^2(k+1)) \subseteq \mathbf{KAN}(L+1,n^2(k+1),1)$

В частности

$\mathbf{KAN}(2, poly(d), k) \subseteq \mathbf{ReLU}{(3, poly(d))}$

Иначе говоря, любой двухслойный кусочно-линейный KAN ширины может быть реализован в виде трехслойной ReLU MLP сети, имеющей полиномиальную ширину (на всякий случай нужно уточнить, что ширина у них не обязана совпадать, она просто должна быть полиномиальной относительно входной размеренности).
Таким образом, интерес представляет следующий вопрос: если мы можем представить любой двухслойный кусочно-линейный KAN трехслойной ReLU MLP, может мы можем представить его ограничившись лишь двумя слоями?
Отрицательный ответ на этот вопрос вел бы к отсутствию вложения

$\mathbf{KAN}{(2, poly(d), k)} \not\subseteq \mathbf{ReLU}{(2, poly(d))}$

а следовательно было бы установлено свойство разделения глубины между двухслойным кусочно-линейным (а значит и произвольным) KAN и двухслойной ReLU MLP (везде ширина предполагается ). То есть, существовала бы такая функция , что она реализуется двухслойным KAN, но не реализуется двухслойной ReLU MLP.
На самом деле, мы можем пойти наоборот: построим функцию , а затем покажем, что она удовлетворяет нужным условиям. Как раз этому посвящены следующие разделы.

3. Поиск искомой функции

В этом разделе нам понадобятся 2 предположения об используемых активационных функциях MLP-сетей:

Предположение 1: Для заданной функции активации $\sigma$ существует константа $c_{\sigma} \geq 1$ (зависящая только от $\sigma$ ), такая что выполняется следующее:
Для любой -липшицевой функции $f\colon \mathbb{R} \rightarrow \mathbb{R}$ , которая постоянна вне ограниченного интервала , и для любого $\delta \gt 0$ существуют скаляры $a, \{\alpha_i, \beta_i, \gamma_i\}_{i=1}^w$ , где $w \leq c_{\sigma}\frac{RL}{\delta}$ , такие что функция

$h(x) = a + \sum_{i=1}^w \alpha_i \cdot \sigma(\beta_i x - \gamma_i)$

удовлетворяет условию:

$\sup_{x \in \mathbb{R}} |f(x) - h(x)| \leq \delta.$

Предположение 2: Функция активации $\sigma$ является (лебегово) измеримой и удовлетворяет условию:

$|\sigma(x)| \leq C(1 + |x|^\alpha)$

для всех $x \in \mathbb{R}$ и некоторых констант $C, \alpha \gt 0$ .

Стоит заметить, что эти два предположения выполняются для многих известных активационных функций, в частности для ReLU. Первое предположение говорит о том, что мы можем приблизить любую липшицеву функцию с ограниченным носителем с помощью двухслойной MLP сети с данной активационной функцией, а второе ограничивает рост активационной функции некоторым полиномом.

В процессе поиска подходящего кандидата на роль "плохой" функции я вспомнил про статью 2016 года с результатом разделения глубины для MLP сетей глубины 2 и 3 - The Power of Depth for Feedforward Neural Networks. Основным результатом данной работы является следующая теорема:

Теорема: Предположим, что функция активации $\sigma(\cdot)$ удовлетворяет предположению 1 с константой $c_{\sigma}$ , а также предположению 2. Тогда существуют универсальные константы $c, C \gt 0$ такие, что для любой размерности $d \gt C$ найдется вероятностная мера $\mu$ на $\mathbb{R}^{d}$ и функция $\tilde{g}: \mathbb{R}^{d} \to \mathbb{R}$ со следующими свойствами:

Функция $\tilde{g}$ ограничена в , имеет носитель на $\{\mathbf{x} : \|\mathbf{x}\| \leq C\sqrt{d}\}$ и может быть представлена 3-слойной нейронной сетью с шириной не более $Cc_{\sigma}d^{19/4}$ .
Любая функция , представленная двухслойной сетью с шириной не более $ce^{cd}$ , удовлетворяет неравенству:

$\mathbb{E}_{\mathbf{x}\sim\mu}\left(f(\mathbf{x}) - \tilde{g}(\mathbf{x})\right)^2 \geq c.$

То есть, теорема говорит о том, что существует некоторая функция $\tilde{g}$ и вероятностная мера $\mu$ , что $\tilde{g}$ не приближается никакой двухслойной ReLU MLP сетью полиномиальной ширины по норме $L_2{(\mu)}$ , но трехслойной сети уже достаточно для ее приближения.

Моя идея заключалась в том, что такая функция $\tilde{g}$ может подойти и для моей задачи. Для этого надо было проверить, возможно ли приблизить ее с помощью двухслойного кусочно-линейного KAN.

Перед тем, как доказывать, что $\tilde{g}$ действительно приближается KAN-ом, обсудим ее построение.

Для начала зададим вероятностную меру $\mu$ на $\mathbb{R}^d$ . Это будет такая мера, что ее плотность имеет вид $\phi^2(\mathbf{x})$ , где $\phi$ - преобразование Фурье индикатора единичного евклидова шара $\mathbf{1}\{\mathbf{w} \in R_dB_d\}$ , здесь - множитель, такой, что . График такой плотности для приведен ниже, а явная формула имеет вид

$\varphi(\mathbf{x}) = \left(\frac{R_d}{\|\mathbf{x}\|}\right)^{d/2} J_{d/2}(2\pi R_d \|\mathbf{x}\|)$

где $J_{d/2}(\cdot)$ - функция Бесселя первого типа, порядка . (график для $J_{20}(\cdot)$ ниже)

График искомой плотности, справа - увеличенный масштаб

График функции Бесселя первого типа порядка 20

Идея брать именно такую меру исходит из того, что носитель двухслойной нейронной сети представляет из себя объединение многомерных трубок ограниченного радиуса, проходящих через начало координат. А это значит, что функция $\widehat{\tilde{g}*\phi}$ (преобразование Фурье произведение $\tilde{g}$ и $\phi$ ) должна иметь большую часть своей $L_2{(\mu)}$ -массы далеко от начала координат. Но $\widehat{\tilde{g}\phi} = \hat{\tilde{g}} \ast \hat{\phi}$ (справа - свертка преобразований Фурье), а свертка с индикатором единичного шара как раз "разносит" массу от центра (это известный факт для , но из построения это будет верно и для ). Подробнее об этом можно прочитать в исходной статье в разделе "Proof Sketch".

Теперь зададим $\tilde{g}$ как комбинацию индикаторов некоторых "тонких" оболочек:

$\tilde{g}(\mathbf{x}) = \sum_{i=1}^N \epsilon_i g_i(\mathbf{x})$

где $\epsilon_i \in \{-1, +1\}$ , и $g_i(\mathbf{x}) = \mathbf{1}\{\|\mathbf{x}\| \in \Delta_i\}$ , где $\Delta_i$ - непересекающиеся интервалы ширины $\mathcal{O}{(1/N)}$ , значения которых лежат в пределах $\mathcal{\Theta}{(\sqrt{d})}$ . Более подробное построение можно посмотреть в исходной статье, либо в полном тексте моей курсовой.

4. Приближение с помощью KAN

Теперь нам остается проверить, что построенная в предыдущем разделе функция действительно приближается двухслойным кусочно-линейным KAN. Тогда, в силу того, что двухслойной ReLU MLP она не приближается, будет получена невложимость классов $\mathbf{KAN}{(2, poly(d), k)} \not\subseteq \mathbf{ReLU}{(2, poly(d))}$ .

Начнем с переформулировки Предположения 1 из предыдущего раздела для архитектуры KAN:

Предположение 1(KAN): Пусть $\phi$ - активационная функция (сплайн с сегментами), тогда для любой -липшицевой функции $f: \mathbb{R} \to \mathbb{R}$ , такой, что $f \equiv const$ вне интервала и для любого $\delta \gt 0$ найдется $K \in \mathbb{N}$ , такое, что верно:

$\sup_{x\in\mathbb{R}}|f(x) - \phi(x)| \leq \delta\$

Заметим, что для кусочно-линейных сплайнов это предположение выполняется. Отрезок можно разбить на K равных частей с шагом $h = \frac{2R}{K}$ , затем строим сплайн , совпадающий с в точках :

$S(x) = \left\{ \begin{array}{l} f(x_i) + \frac{f(x_{i+1}) - f(x_i)}{h}(x-x_i) \quad x\in[x_i, x_{i+1}], \\ f(x) \equiv const \quad x \notin [-R, R] \\ \end{array} \right.$

Оценим точность приближения, так как является -липшицевой, то на каждом отрезке $[x_{i}, x_{i+1}]$ :

$\sup_{x\in\mathbb{R}}|f(x)-S(x)| \leq L \cdot h\$

Чтобы выполнялось $L \cdot h \leq \delta$ , достаточно положить $h \leq \frac{\delta}{L}$ , т.е $K \geq \frac{2LR}{\delta}$ .

Также нам понадобится следующая лемма из оригинальной статьи:

Лемма 1: Предположим, что $d \geq 2$ . Для любого выбора $\epsilon_i \in \{-1, +1\}$ , $i = 1, \ldots, N$ существует -липшицева функция , носитель которой содержится в $[\alpha \sqrt{d}, 2\alpha \sqrt{d}]$ и принимающая значения в , удовлетворяющая условию

$\int\left( f(\mathbf{x}) - \sum_{i=1}^N \epsilon_i g_i(\mathbf{x}) \right)^{2} \varphi^2(\mathbf{x}) dx \leq \frac{3}{\alpha^2 \sqrt{d}}$

Здесь $\alpha \geq 1$ - большая числовая константа, которая должна быть больше определенного порога, также она участвует в построении $\tilde{g}$ (подробнее в оригинальной статье).

Из данной леммы уже видно, что наша "плохая" функция может быть приближена по $L_2{(\mu)}$ -норме некоторой липшицевой функцией многих переменных. Заметим также, что значения $\tilde{g}$ зависят лишь от нормы $\|\mathbf{x}\|$ . Осталось понять, можем ли мы приближать двухслойным кусочно-линейным KAN такие липшицевы функции, зависящий от нормы входного вектора. Об этом следующая лемма:

Лемма 2: Предположим, что функция активации $\phi$ удовлетворяет предположению 1(KAN). Пусть - -липшицева функция с носителем на , где $r \geq 1$ . Тогда для любого $\delta \gt 0$ существует функция , представимая двухслойным кусочно-линейным KAN ширины , в котором число сегментов кусочно-линейных функций $K \geq \frac{2RL}{\sqrt{r}\delta}\cdot\max(R, L)$ , такая что

$\sup_{\mathbf{x}\in\mathbb{R}^{d}}|g(\mathbf{x}) - f(\|\mathbf{x}\|)| < \delta.$

Доказательство: Определим -липшицеву функцию

$l(x) = \min(x^2, R^2)$

которая константа вне отрезка . Такими же свойствами обладает и функция

$l(\mathbf{x}) = \sum_{i=1}^{d}l(x_i)$

определенная на $\mathbb{R}^d$ . Применим Предположение 1(KAN) к функции $l(\cdot)$ , получим функцию $\tilde{l}(x) = \phi(x)$ такую, что

$\sup_{x\in\mathbb{R}}|\tilde{l}(x) - l(x)| \leq \frac{\sqrt{r}\delta}{dL}$

Такое неравенство верно при $K \geq \frac{2RL^2}{\sqrt{r}\delta}$ . Следовательно, функция

$\tilde{l}(\mathbf{x}) = \sum_{i=1}^d\tilde{l}(x_i)$

будет иметь вид $\tilde{l}(\mathbf{x}) = \sum_{i=1}^d\phi_i(x_i)$ .

Введем теперь следующую функцию:

$s(x) = \left\{ \begin{array}{l} f(\sqrt{x}) \quad x \geq 0, \\ 0 \quad x < 0 \\ \end{array} \right.$

Так как является -липшицевой с носителем в множестве $\{x \colon r \leq x \leq R\}$ , отсюда следует, что является $\frac{L}{2\sqrt{r}}$ -липшицевой с носителем в . Снова применим предположение 1(KAN) к функции $s{(\cdot)}$ с $K \geq \frac{2R^2L}{\sqrt{r}\delta}$ . Получим функцию $\tilde{s}(x) = \eta(x)$ , что

$\sup_{x\in\mathbb{R}}|\tilde{s}(x) - s(x)| \leq \frac{\delta}{2}$

Теперь рассмотрим композицию $g = \tilde{s} \circ \tilde{l}$ , которая из определений $\tilde{s}$ и $\tilde{l}$ имеет вид:

$g(x) = \eta\left(\sum_{i=1}^d\phi_i(x_i)\right)$

Т.е представляет собой двухслойный KAN ширины .

Покажем, что $\sup_{\mathbf{x}\in\mathbb{R}^d}|g(\mathbf{x}) - f(\|\mathbf{x}\|)| \leq \delta$ . Для любого $\mathbf{x}$ из $\mathbb{R}^d$ мы имеем:

$|g(\mathbf{x}) - f(\|\mathbf{x}\|)| \leq |\tilde{s}(\tilde{l}(\mathbf{x})) - s(\tilde{l}(\mathbf{x}))| + |s(\tilde{l}(\mathbf{x})) - s(l(\mathbf{x}))| + |s(l(\mathbf{x})) - f(\|\mathbf{x}\|)| =$ $= \\|\tilde{s}(\tilde{l}(\mathbf{x})) - s(\tilde{l}(\mathbf{x}))| + |s(\tilde{l}(\mathbf{x})) - s(l(\mathbf{x}))| + |f(\sqrt{l(\mathbf{x})}) - f(\|\mathbf{x}\|)|$

Рассмотрим каждое из трёх абсолютных значений:

Первое абсолютное значение не превосходит $\delta/2$ согласно построению $\tilde{s}$ .
Второе абсолютное значение, поскольку является $\frac{L}{2\sqrt{r}}$ -липшицевой, не превосходит $\frac{L}{2\sqrt{r}}|\tilde{\ell}(\mathbf{x}) - \ell(\mathbf{x})|$ , что по построению $\tilde{l}$ составляет не более $\delta/2$ .
Что касается третьего абсолютного значения: если $\|\mathbf{x}\|^{2} \leq R^{2}$ , то $\ell(\mathbf{x}) = \|\mathbf{x}\|^{2}$ и значение равно нулю. Если $\|\mathbf{x}\|^{2} > R^{2}$ , то легко проверить, что $\ell(\mathbf{x}) \geq R^{2}$ , и поскольку непрерывна и имеет носитель на , следует, что $f(\sqrt{\ell(\mathbf{x})}) = f(\|\mathbf{x}\|) = 0$ , и снова получаем ноль.

Суммируя вышесказанное, получаем $|g(\mathbf{x}) - f(\|\mathbf{x}\|)| \leq \frac{\delta}{2} + \frac{\delta}{2} + 0 = \delta$ , что и требовалось. Лемма 2 доказана.

Наконец, объединим Лемму 1 и Лемму 2 для доказательства того, что функция $\tilde{g}$ приближается двухслойным KAN:

Теорема: Существует универсальная константа $C \gt 0$ такая, что выполняется следующее. Пусть $\delta \in (0, 1)$ . Предположим, что $d \geq C$ и функции построены как указано выше. Для любого выбора $\epsilon_i \in \{-1, +1\}$ , $i = 1, \ldots, N$ существует функция , представимая двухслойным кусочно-линейным KAN ширины , со значениями в , такая что

$\| g(x) - \sum_{i=1}^N \epsilon_i g_i(\|x\|)\|_{L_2(\mu)} \leq \frac{\sqrt{3}}{\alpha d^{1/4}} + \delta.$

Доказательство: Сначала применим Лемму 2, чтобы получить -липшицеву функцию со значениями в , удовлетворяющую условию

$\| h{(\mathbf{x})} - \sum_{i=1}^{N} \epsilon_{i} g_i{(\mathbf{x})} \|_{L_2{(\mu)}} = \sqrt{\int_{\mathbb{R}^d}{\left( h{(\mathbf{x})} - \sum{\epsilon_i g_i{(x)}} \right)^2 \varphi^2(x) dx}} \leq \frac{\sqrt{3}}{\alpha d^{1/4}}.$

Затем используем Лемму 2 с параметрами $R = 2\alpha\sqrt{d}$ , $r = \alpha\sqrt{d}$ , ( тогда $K \geq \frac{8\alpha^{3/2}d^{3/4}N}{\delta}$ ) для построения функции , представимой двухслойным кусочно-линейным KAN ширины , такой что $\sup_{x \in \mathbb{R}^d} |g(x) - h(x)| \leq \delta$ . Это означает, что $\|g - h\|_{L_2(\mu)} \leq \delta$ , а также что значения лежат в $[-1 - \delta, 1 + \delta] \subseteq [-2, +2]$ (поскольку $\delta < 1$ ). Объединяя это с равенством выше и используя неравенство треугольника, завершаем доказательство.

Подведение итогов

Проделав такую большую работу, мы показали, что существует функция $\tilde{g}$ такая, что она не может быть приближена двухслойной ReLU MLP ширины , но может быть приближена двухслойным кусочно-линейным KAN ширины с числом сегментов $K \geq \frac{8\alpha^{3/2}d^{3/4}N}{\delta}$ . Иначе говоря, доказано отсутствие вложения

$\mathbf{KAN}{\left(2, poly(d), \left\lceil \frac{8\alpha^{3/2}d^{3/4}N}{\delta}\right\rceil + 1\right)} \not\subseteq \mathbf{ReLU}{(2, poly(d))}$

Таким образом, существуют функции, которые не могут быть приближены старой архитектурой MLP, однако могут быть реализованы с помощью KAN (даже в случае кусочно-линейных активационных функций у последнего). Конечно же, этот результат в большей степени теоретический, но он показывает, что в новой архитектуре может быть заложена куда большая выразимостная мощность, чем в классической.

Комментарии (2)

Flokis_guy
22.07.2025 16:49
#28607850
Статья отличная. И благодаря подобным хабр ещё торт.

В целом сравнение через выразительную способность отличное. Хотя двухслойный MLP имеет универсальную аппроксимацию в C и Lp. Ширина его при желаемой точности растет экспоненциально, а не полиномиально. Но с другой стороны, так как KAN в общем случае обобщает MLP имея произвольную функцию в сравнении с w*activation(x). Где в первом слое активация является линейной. И вот тут интересный момент, если представить MLP как двухслойный KAN, то выходит, что это и портит всю ситуацию. И тут возникает вопрос, а честно ли так сравнивать, так как линейная функция является сплайном первого порядка, но не любой сплайн это линейная функция вида w*x+b.
1. E_P_H_E_M_E_R_I_S Автор
  22.07.2025 16:49
  #28607930
  Спасибо за приятный отзыв! Как я понял, вопрос про то, что работая только с кусочно-линейными KAN мы теряем как раз то, что и обобщает KAN - произвольные сплайны. Да, это действительно так, я рассматриваю лишь частный случай новой архитектуры, самый простой, в некотором смысле. Но даже так получается, что с точки зрения выразимостной мощности при равном числе слоев (в нашем случае 2) KAN оказывается мощнее.
  
  Интересно было бы посмотреть дальше на KAN уже в общем виде, но там есть свои сложности, например, произвольный KAN уже не перестроить в классическую MLP, нужно добавлять специальные активационные функции с покоординатным возведением в степень.