freQuensy23 21 мая в 11:47

Разбираем KAN по полочкам

4 мин

6.7K

Аналитика

Недавно, аспиранты MIT выпустили очень интересную статью про концептуально новый подход к проектированию наверное самого базового "кирпичика" нейронок - полносвязного слоя.

Тут следовало бы сделать довольно большую справку, но что бы не превращать этот пост учебник по ML, коротко и не полностью строго:

Любую приличную функцию f: $R^n \rightarrow R^m$ можно близко приблизить комбинацией линейных многомерных преобразований и нелинейных одномерных функций активации. . То есть: $f(\vec x) \approx A_n\cdot \sigma(A_{n-1} \cdot \sigma ........ A_1 \cdot x))))))$ (ведь если сигма линейна то комбинция линейных преобразований - линейно. В качестве сигмы можно взять $\sigma(x) = max(x, 0)$ )

где - матрицы линейных преобразований (P.S. функция активации применяется к элементам векторов поэлементно)

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

Удобное для понимания представление нейронки. Каждая связь имеет свой вес, который соотвествует числу из матрицы A_i

Такая архитектура сети немного напоминает структуру мозга, где есть множество связных между собой нейронов, у каждой связи есть свой вес (сила связи). За это такие сети и назвали нейронные

Как работает KAN

К величию тернистый путь (не все так сразу)

Что такое сплайн

Представим, что мы исследуем движение частицы по двухмерной поверхности, причем закон движения частицы совсем неизвестен. Раз в 0.1 секунды прибор сохраняет координаты частицы- наш датасет. Мы хотим отобразить эту траекторию на экране пользователя в виде гладкой траектории (а не в виде набора точек) [по сути дела задача регрессии]. То есть мы должны придумать способ интерполировать положение нашей частицы между точками. Довольно интуитивным методом является сплайн:

$\vec{P(t)} \approx \Sigma_i^n B_i(t) \vec p_i$

Где B_i(t) выглядят вот так (см картинку ниже), пики каждый 0.1 секунды, когда мы записываем координату.

То есть в момент между точками (в которых мы знаем положение частицы) для определения ее координаты мы берем взвешенную сумму из "соседних по времени" точек из нашего датасета.

Сплайн вместо нейронки

Почему бы просто не использовать сплайн для решения задачи регрессии вместо нейронки? Вот у нас есть датасет признаков, есть некоторый таргет. Почему бы просто не построить сплайн в пространстве $(\vec x, y)$ и использовать его для предсказаний? Оказывается он хорош только в одномере и очень сильно страдает от проклятья размерности.

Это можно легко качественно доказать. Представим мы хотим интерполировать некоторую одномерную функцию (R -> R) по набору точек в положительной 5-окрестности нуля.

Что бы ошибиться не сильно (в первом знаке), нужен датасет из точек с шагом 1, нам потребуется около 5и точек

Если же функция 2-у мерная, $(x_1, x_2) \mapsto y$ , то для достижения схожей точности нам потребуется уже построить сетку из точек, их уже будет 25 штук.

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

Короче говоря - сплайн так себе интерполятор многомерных данных. Но что же делать? Тут на помощь приходит:

Теорема Колмогорова — Арнольда

Она доказывает, что единственная истинная функция многих переменных — это сложение, поскольку все другие функции можно записать с использованием функций одной переменной и сложения.

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

$f(\vec {x} )=f(x_{1},\ldots ,x_{n})=\sum _{q=0}^{2n}\Phi _{q}\left(\sum _{p=1}^{n}\phi _{q,p}(x_{p})\right)$

Например(какие функции $\phi$ и $\Phi$ выбраны в этом случае можете подсмотреть в таблице)

Таким образом многомерную функцию можно представить в виде суммы и композиции одномерных, которые мы уже умеем приближать сплайном.

На самом деле авторы статьи использовали чуть менее строгое и более страшное утверждение (которое сводится к этому обнулением и заменой на тривиальные части функций), но идейно все остается так же

Таким образом KAN-сеть состоит из обучаемых (сплайнами) функций $\phi_\cdot$ , узлами ●, в которых прозводится сумирование, и ребрами, обозначающих композиции (или более просто - по ним "передается" значние

Результат работы

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

Забавы ради я написал peft-kan - форк от пефта с возможностью обучения LoRA для моделей с использованием канов. Что удивительно, иногда сходится немного получше (но конечно теряет все преимущества лоры, типо мерджа итп). - подробнее тут

Оптимизации в реальной реализации

Although a KAN layer Eq. (2.5) looks extremely simple, it is non-trivial to make it well optimizable. The key tricks are:

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

Заключение

Вместо моих слов, лучше прикреплю табличку, с ключевыми моментами:

Теги:

Хабы:

Разбираем KAN по полочкам

Как работает KAN

Что такое сплайн

Сплайн вместо нейронки

Теорема Колмогорова — Арнольда

Результат работы

Оптимизации в реальной реализации

Заключение

Публикации

Истории

Работа

Ближайшие события