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

2025-07-22 в 11:15, admin, рубрики: approximation, deep learning, kan, machine learning, math, MLP, neural networks, research, science

Введение

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

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

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

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

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

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

Моя идея заключалась в том, чтобы попытаться установить подобное свойство, которое разделяло бы KAN и MLP. Конкретно, вопрос ставился следующим образом: пусть - KAN глубины , ширины и - MLP сеть той же глубины и полиномиальной ширины. Существует ли такая функция , что она приближается , но не приближается ?

Для того, чтобы ответить на этот вопрос, нам придется вникнуть в устройство KAN, рассмотреть один из известных результатов разделения глубины для MLP сетей глубины 2 и 3 (ширины ), а также объединить это все с помощью результата по преобразованию кусочно-линейного (станет понятно далее) 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}colonmathbb{R}^{n_{text{in}}}tomathbb{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)ldotsright)$

где — входная размерность -го 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-сплайнами.

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

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

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

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

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

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

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

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

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

Теорема: Пусть $gcolon mathbb{R}^n to mathbb{R}^m$ — это MLP-сеть с функциями активации из семейства . Тогда существует KAN $fcolon mathbb{R}^n to mathbb{R}^m$ с функциями активации, которые являются либо аффинно-линейными, либо принадлежат , такой что для всех $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)$

В частности

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

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

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

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

Предположение 1: Для заданной функции активации существует константа $c_{sigma} geq 1$ (зависящая только от ), такая что выполняется следующее:
Для любой -липшицевой функции , которая постоянна вне ограниченного интервала , и для любого существуют скаляры $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: Функция активации является (лебегово) измеримой и удовлетворяет условию:

для всех и некоторых констант .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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}$ , где - непересекающиеся интервалы ширины , значения которых лежат в пределах . Более подробное построение можно посмотреть в исходной статье, либо в полном тексте моей курсовой.

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

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

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

Предположение 1(KAN): Пусть - активационная функция (сплайн с сегментами), тогда для любой -липшицевой функции , такой, что вне интервала и для любого найдется , такое, что верно:

$sup_{xinmathbb{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 xin[x_i, x_{i+1}], \ f(x) equiv const quad x notin [-R, R] \ end{array} right.$

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

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

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

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

Лемма 1: Предположим, что . Для любого выбора $epsilon_i in {-1, +1}$ , существует -липшицева функция , носитель которой содержится в и принимающая значения в , удовлетворяющая условию

$intleft( 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}}$

Здесь - большая числовая константа, которая должна быть больше определенного порога, также она участвует в построении (подробнее в оригинальной статье).

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

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

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

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

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

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

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

$sup_{xinmathbb{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}^dtilde{l}(x_i)$

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

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

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

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

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

Теперь рассмотрим композицию , которая из определений и имеет вид:

$g(x)=etaleft(sum_{i=1}^dphi_i(x_i)right)$

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

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

$=\|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}|)|$

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

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

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

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

Теорема: Существует универсальная константа такая, что выполняется следующее. Пусть . Предположим, что и функции построены как указано выше. Для любого выбора $epsilon_i in {-1, +1}$ , существует функция , представимая двухслойным кусочно-линейным 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 с параметрами , , ( тогда $K geq frac{8alpha^{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$ , а также что значения лежат в (поскольку ). Объединяя это с равенством выше и используя неравенство треугольника, завершаем доказательство.

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

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

$mathbf{KAN}{left(2, poly(d), leftlceil frac{8alpha^{3/2}d^{3/4}N}{delta}rightrceil + 1right)} notsubseteq mathbf{ReLU}{(2, poly(d))}$

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

Автор: E_P_H_E_M_E_R_I_S

Источник