Универсальная аппроксимационная теорема

В математической теории сетей искусственных нейронных универсальными теоремами аппроксимации являются теоремы следующего вида: Учитывая семейство нейронных сетей, для каждой функции $f$ из некоторого функционального пространства существует последовательность нейронных сетей $\phi _{1},\phi _{2},\dots$ из семьи, так что $\phi _{n}\to f$ по какому-то критерию. То есть семейство нейронных сетей плотно в функциональном пространстве.

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

Универсальные теоремы аппроксимации — это теоремы существования: они просто утверждают, что существует такая последовательность. $\phi _{1},\phi _{2},\dots \to f$и не предоставляют никакого способа найти такую ​​последовательность. Они также не гарантируют, что какой-либо метод, например обратное распространение ошибки , действительно сможет найти такую ​​последовательность. Любой метод поиска в пространстве нейронных сетей, включая обратное распространение ошибки, может найти сходящуюся последовательность или нет (т. е. обратное распространение ошибки может застрять в локальном оптимуме).

Универсальные аппроксимационные теоремы — это предельные теоремы: они просто утверждают, что для любого $f$ и критерии близости $\epsilon >0$, если в нейронной сети достаточно нейронов, то существует нейронная сеть с таким количеством нейронов, которая приближается $f$ внутри $\epsilon$. Нет никакой гарантии, что любого конечного размера, скажем, 10 000 нейронов будет достаточно.

Настраивать

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

Большинство универсальных аппроксимационных теорем относятся к одному из двух классов. Первый количественно определяет возможности аппроксимации нейронных сетей с произвольным количеством искусственных нейронов (« случай произвольной ширины »), а второй фокусируется на случае с произвольным количеством скрытых слоев, каждый из которых содержит ограниченное количество искусственных нейронов (« случай произвольной глубины »). " случай). Помимо этих двух классов существуют также универсальные аппроксимационные теоремы для нейронных сетей с ограниченным числом скрытых слоев и ограниченным числом нейронов в каждом слое (случай « ограниченной глубины и ограниченной ширины »).

История

Произвольная ширина

Первыми примерами были случай произвольной ширины . Джордж Цыбенко в 1989 году доказал это для функций активации сигмовидной кишки . Курт Хорник , Максвелл Стинчкомб и Халберт Уайт показали в 1989 году, что многослойные сети с прямой связью всего с одним скрытым слоем являются универсальными аппроксиматорами. Хорник также показывался в 1991 году. что не конкретный выбор функции активации, а сама многоуровневая архитектура прямой связи дает нейронным сетям потенциал быть универсальными аппроксиматорами. Моше Лешно и др. в 1993 году. а затем Аллан Пинкус в 1999 году. показал, что свойство универсальной аппроксимации эквивалентно наличию неполиномиальной функции активации.

Произвольная глубина

Случай произвольной глубины также изучался рядом авторов, таких как Густав Грипенберг в 2003 году. Дмитрий Яроцкий, Чжоу Лу и др. в 2017 г. Борис Ханин и Марк Селлке в 2018 году который сосредоточился на нейронных сетях с функцией активации ReLU. В 2020 году Патрик Киджер и Терри Лайонс распространил эти результаты на нейронные сети с общими функциями активации , такими как tanh, GeLU или Swish.

Особый случай произвольной глубины состоит в том, что каждый компонент композиции происходит из конечного набора отображений. В 2024 году Цай построил конечный набор отображений, названный словарем, такой, что любую непрерывную функцию можно аппроксимировать, составив последовательность из словаря. Это похоже на концепцию композиционности в лингвистике, которая заключается в том, что ограниченный словарь основных элементов может быть объединен с помощью грамматики для выражения бесконечного диапазона значений.

Ограниченная глубина и ограниченная ширина

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

Гулиев и Исмаилов построил гладкую сигмоидальную функцию активации, обеспечивающую универсальное свойство аппроксимации для двух нейронных сетей прямого распространения скрытых слоев с меньшим количеством элементов в скрытых слоях.

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

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

Количественные границы

Вопрос о минимально возможной ширине универсальности впервые изучался в 2021 году. Парк и др. получили минимальную ширину, необходимую для универсальной аппроксимации L ^п функции, использующие нейронные сети прямого распространения с ReLU в качестве функций активации. Аналогичные результаты, которые можно напрямую применить к остаточным нейронным сетям, были получены в том же году Пауло Табуада и Бахманом Гаресифардом с использованием теории управления . аргументов В 2023 году Лошади получена оптимальная граница минимальной ширины для универсального приближения.

Для случая произвольной глубины Леони Папон и Анастасис Крациос получены явные оценки глубины в зависимости от регулярности целевой функции и функции активации.

Kolmogorov network

Теорема о представлении Колмогорова –Арнольда аналогична по духу. Действительно, некоторые семейства нейронных сетей могут напрямую применять теорему Колмогорова – Арнольда для получения универсальной аппроксимационной теоремы.

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

показывает практическое применение.

Варианты

Прерывистые функции активации, некомпактные области, сертифицированные сети, случайные нейронные сети, и альтернативные сетевые архитектуры и топологии.

Свойство универсальной аппроксимации сетей с ограниченной шириной изучалось как двойственное к классическим результатам универсальной аппроксимации сетей с ограниченной глубиной. Для входного размера dx и выходного размера dy минимальная ширина, необходимая для универсальной аппроксимации L ^п функций в точности max{dx + 1, dy} (для сети ReLU). В более общем смысле это также справедливо, если как ReLU, так и функция пороговой активации . используются

Аппроксимация универсальной функции на графах (или, скорее, на классах изоморфизма графов ) с помощью популярных сверточных нейронных сетей графов (GCN или GNN) может быть сделана такой же дискриминационной, как тест изоморфизма графов Вейсфейлера-Лемана. В 2020 году результат теоремы универсальной аппроксимации был установлен Брюлем-Габрильссоном, показывающим, что представление графа с определенными инъективными свойствами достаточно для аппроксимации универсальной функции на ограниченных графах и ограниченной аппроксимации универсальной функции на неограниченных графах с сопровождающим ${\mathcal {O}}(\left|V\right|\cdot \left|E\right|)$- метод времени выполнения, который выполняется на современном уровне техники для набора тестов (где $V$ и $E$ — множества узлов и ребер графа соответственно).

Есть также множество результатов между неевклидовыми пространствами. и другие широко используемые архитектуры и, в более общем смысле, алгоритмически генерируемые наборы функций, такие как архитектура сверточной нейронной сети (CNN), радиальные базисные функции , или нейронные сети с определенными свойствами.

Случай произвольной ширины

В 1980-1990-х годах в ряде статей Джорджа Цибенко , Курта Хорника и др. было установлено несколько универсальных аппроксимационных теорем для произвольной ширины и ограниченной глубины. Видеть для отзывов. Чаще всего цитируют следующее:

Теорема об универсальной аппроксимации . Пусть $C(X,\mathbb {R} ^{m})$ обозначим множество непрерывных функций из подмножества $X$ евклидова $\mathbb {R} ^{n}$ пространство в евклидово пространство $\mathbb {R} ^{m}$. Позволять $\sigma \in C(\mathbb {R} ,\mathbb {R} )$. Обратите внимание, что $(\sigma \circ x)_{i}=\sigma (x_{i})$, так $\sigma \circ x$ обозначает $\sigma$ применяется к каждому компоненту $x$.

Затем $\sigma$ не является полиномиальным тогда и только тогда, когда для любого $n\in \mathbb {N}$, $m\in \mathbb {N}$, компактный $K\subseteq \mathbb {R} ^{n}$, $f\in C(K,\mathbb {R} ^{m}),\varepsilon >0$ существуют $k\in \mathbb {N}$, $A\in \mathbb {R} ^{k\times n}$, $b\in \mathbb {R} ^{k}$, $C\in \mathbb {R} ^{m\times k}$ такой, что $$\sup _{x\in K}\|f(x)-g(x)\|<\varepsilon$$ где $g(x)=C\cdot (\sigma \circ (A\cdot x+b))$

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

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

Эскиз доказательства

Достаточно доказать случай, когда $m=1$, поскольку равномерная сходимость по $\mathbb {R} ^{m}$ это просто равномерная сходимость по каждой координате.

Позволять $F_{\sigma }$ быть набором всех нейронных сетей с одним скрытым слоем, построенных с помощью $\sigma$. Позволять $C_{0}(\mathbb {R} ^{d},\mathbb {R} )$ быть набором всех $C(\mathbb {R} ^{d},\mathbb {R} )$ с компактной опорой.

Если функция является полиномом степени $d$, затем $F_{\sigma }$ содержится в замкнутом подпространстве всех многочленов степени $d$, поэтому в нем содержится и его замыкание, что еще не все $C_{0}(\mathbb {R} ^{d},\mathbb {R} )$.

В противном случае мы покажем, что $F_{\sigma }$закрытие - это все $C_{0}(\mathbb {R} ^{d},\mathbb {R} )$. Предположим, мы можем построить сколь угодно хорошие аппроксимации линейной функции $$r(x)={\begin{cases}-1&{\text{if }}x<-1\\{\phantom {+}}x&{\text{if }}|x|\leq 1\\{\phantom {+}}1&{\text{if }}x>1\\\end{cases}}$$ тогда его можно объединить для построения произвольной непрерывной функции с компактным носителем с любой точностью. Осталось аппроксимировать функцию линейного изменения.

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

если $\sigma$ является «раздавливающим», то есть имеет пределы $\sigma (-\infty )<\sigma (+\infty )$, то можно сначала аффинно уменьшить ее ось X так, чтобы ее график выглядел как ступенчатая функция с двумя резкими «выбросами», а затем составить линейную сумму из них, достаточных для получения «лестничной» аппроксимации функции линейного изменения. При увеличении количества ступеней лестницы выбросы сглаживаются, и мы получаем сколь угодно хорошее приближение функции линейного изменения.

Случай, когда $\sigma$ является общей неполиномиальной функцией, это сложнее, и читатель направляется к ней.

В приведенном выше доказательстве не указано, как можно использовать функцию линейного изменения для аппроксимации произвольных функций в $C_{0}(\mathbb {R} ^{n},\mathbb {R} )$. Схема доказательства состоит в том, что можно сначала построить плоские функции выпуклости, пересечь их, чтобы получить сферические функции выпуклости, аппроксимирующие дельта-функцию Дирака , а затем использовать их для аппроксимации произвольных функций в $C_{0}(\mathbb {R} ^{n},\mathbb {R} )$. Оригинальные доказательства, такие как доказательство Цыбенко, используют методы функционального анализа, включая теоремы о представлении Хана-Банаха и Рисса-Маркова-Какутани .

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

Проблему с полиномами можно устранить, разрешив умножать выходные данные скрытых слоев («сети пи-сигма»), что дает обобщение:

Универсальная теорема аппроксимации для пи-сигма-сетей . С любой непостоянной функцией активации пи-сигма-сеть с одним скрытым слоем является универсальным аппроксиматором.

Случай произвольной глубины

«Двойные» версии теоремы рассматривают сети ограниченной ширины и произвольной глубины. Вариант универсальной аппроксимационной теоремы был доказан для случая произвольной глубины Чжоу Лу и др. в 2017 году. Они показали, что сети ширины n + 4 с ReLU функциями активации могут аппроксимировать любую интегрируемую по Лебегу функцию в n -мерном входном пространстве относительно $L^{1}$ расстояние, если разрешено увеличивать глубину сети. Было также показано, что если ширина меньше или равна n , эта общая выразительная сила аппроксимации любой интегрируемой по Лебегу функции теряется. В той же статье было показано, что сетей ReLU шириной n + 1 достаточно для аппроксимации любой непрерывной функции от n -мерных входных переменных. Следующее уточнение определяет оптимальную минимальную ширину, для которой такое приближение возможно и обусловлено.

Теорема об универсальной аппроксимации (расстояние L1, активация ReLU, произвольная глубина, минимальная ширина) — для любой p-интегрируемой функции Бохнера – Лебега. $f:\mathbb {R} ^{n}\to \mathbb {R} ^{m}$ и любой $\varepsilon >0$, существует полностью подключенная ReLU сеть $F$ ширины ровно $d_{m}=\max\{n+1,m\}$, удовлетворяя $$\int _{\mathbb {R} ^{n}}\|f(x)-F(x)\|^{p}\,\mathrm {d} x<\varepsilon .$$ Более того, существует функция $f\in L^{p}(\mathbb {R} ^{n},\mathbb {R} ^{m})$ и некоторые $\varepsilon >0$, для которого не существует полносвязной сети ReLU шириной менее $d_{m}=\max\{n+1,m\}$ удовлетворяющее указанной выше границе приближения.

Примечание. Если активация заменена дырявым ReLU, а ввод ограничен компактной областью, то точная минимальная ширина равна $d_{m}=\max\{n,m,2\}$.

Количественное уточнение: В том случае, когда, когда ${\mathcal {X}}=[0,1]^{d}$ и $D=1$ и где $\sigma$ — это функция активации ReLU , точная глубина и ширина сети ReLU, которую необходимо достичь. $\varepsilon$ ошибка тоже известна. Если при этом целевая функция $f$ гладкая, то необходимое количество слоев и их ширина могут быть экспоненциально меньшими. Даже если $f$ не является гладким, проклятие размерности можно снять, если $f$ допускает дополнительную «композиционную структуру».

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

Теорема об универсальной аппроксимации (Равномерная неаффинная активация , произвольная глубина , ограниченная ширина). - Позволять ${\mathcal {X}}$ быть компактным подмножеством $\mathbb {R} ^{d}$. Позволять $\sigma :\mathbb {R} \to \mathbb {R}$ — любая неаффинная непрерывная функция , непрерывно дифференцируемая хотя бы в одной точке, с ненулевой производной в этой точке. Позволять ${\mathcal {N}}_{d,D:d+D+2}^{\sigma }$ обозначим пространство нейронных сетей прямого распространения с $d$ входные нейроны, $D$ выходные нейроны и произвольное количество скрытых слоев, каждый из которых $d+D+2$ нейронов, так что каждый скрытый нейрон имеет функцию активации $\sigma$ и каждый выходной нейрон имеет идентичность в качестве функции активации, а входной слой $\phi$ и выходной слой $\rho$. Тогда учитывая любой $\varepsilon >0$ и любой $f\in C({\mathcal {X}},\mathbb {R} ^{D})$, существует ${\hat {f}}\in {\mathcal {N}}_{d,D:d+D+2}^{\sigma }$ такой, что $$\sup _{x\in {\mathcal {X}}}\left\|{\hat {f}}(x)-f(x)\right\|<\varepsilon .$$

Другими словами, ${\mathcal {N}}$ плотный ​ в $C({\mathcal {X}};\mathbb {R} ^{D})$ относительно топологии равномерной сходимости .

Количественное уточнение: количество слоев и ширина каждого слоя, необходимые для аппроксимации. $f$ к $\varepsilon$ точность известна; более того, результат справедлив, когда ${\mathcal {X}}$ и $\mathbb {R} ^{D}$ неположительной кривизны заменяются любым римановым многообразием .

Определенные необходимые условия для случая ограниченной ширины и произвольной глубины установлены, но между известными достаточными и необходимыми условиями все еще существует разрыв.

Случай ограниченной глубины и ограниченной ширины

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

Универсальная теорема аппроксимации: — Имеется функция активации $\sigma$ которая является аналитической, строго возрастающей, сигмоидальной и обладает следующим свойством: для любого $f\in C[0,1]^{d}$ и $\varepsilon >0$ существуют константы $d_{i},c_{ij},\theta _{ij},\gamma _{i}$и векторы $\mathbf {w} ^{ij}\in \mathbb {R} ^{d}$ для чего $$\left\vert f(\mathbf {x} )-\sum _{i=1}^{6d+3}d_{i}\sigma \left(\sum _{j=1}^{3d}c_{ij}\sigma (\mathbf {w} ^{ij}\cdot \mathbf {x-} \theta _{ij})-\gamma _{i}\right)\right\vert <\varepsilon$$ для всех $\mathbf {x} =(x_{1},...,x_{d})\in [0,1]^{d}$.

Это результат существования. В нем говорится, что существуют функции активации, обеспечивающие универсальное свойство аппроксимации для сетей ограниченной глубины и ширины. Используя определенные методы алгоритмического и компьютерного программирования, Гулиев и Исмаилов эффективно построили такие функции активации в зависимости от числового параметра. Разработанный алгоритм позволяет мгновенно вычислять функции активации в любой точке действительной оси. Алгоритм и соответствующий компьютерный код см. Теоретический результат можно сформулировать следующим образом.

Универсальная теорема аппроксимации: - Позволять $[a,b]$ быть конечным отрезком вещественной прямой, $s=b-a$ и $\lambda$ быть любым положительным числом. Тогда можно алгоритмически построить вычислимую сигмоидальную функцию активации. $\sigma \colon \mathbb {R} \to \mathbb {R}$, которая бесконечно дифференцируема и строго возрастает на $(-\infty ,s)$, $\lambda$ - строго возрастает по $[s,+\infty )$и удовлетворяет следующим свойствам:

1. Для любого $f\in C[a,b]$ и $\varepsilon >0$ существуют числа $c_{1},c_{2},\theta _{1}$ и $\theta _{2}$ такой, что для всех $x\in [a,b]$ $$|f(x)-c_{1}\sigma (x-\theta _{1})-c_{2}\sigma (x-\theta _{2})|<\varepsilon$$
2. Для любой непрерывной функции $F$ на $d$-размерная коробка $[a,b]^{d}$ и $\varepsilon >0$, существуют константы $e_{p}$, $c_{pq}$, $\theta _{pq}$ и $\zeta _{p}$ такая, что неравенство $$\left|F(\mathbf {x} )-\sum _{p=1}^{2d+2}e_{p}\sigma \left(\sum _{q=1}^{d}c_{pq}\sigma (\mathbf {w} ^{q}\cdot \mathbf {x} -\theta _{pq})-\zeta _{p}\right)\right|<\varepsilon$$ держится для всех $\mathbf {x} =(x_{1},\ldots ,x_{d})\in [a,b]^{d}$. Здесь весы $\mathbf {w} ^{q}$, $q=1,\ldots ,d$, фиксируются следующим образом: $$\mathbf {w} ^{1}=(1,0,\ldots ,0),\quad \mathbf {w} ^{2}=(0,1,\ldots ,0),\quad \ldots ,\quad \mathbf {w} ^{d}=(0,0,\ldots ,1).$$ Кроме того, все коэффициенты $e_{p}$, кроме одного, равны.

Здесь " $\sigma \colon \mathbb {R} \to \mathbb {R}$ является $\lambda$-строго возрастает на некотором множестве $X$означает, что существует строго возрастающая функция $u\colon X\to \mathbb {R}$ такой, что $|\sigma (x)-u(x)|\leq \lambda$ для всех $x\in X$. Ясно, что $\lambda$-возрастающая функция ведет себя как обычная возрастающая функция: $\lambda$ становится маленьким. В терминологии « глубины-ширины » приведенная выше теорема гласит, что для некоторых функций активации глубина $2$ ширина- $2$ сети являются универсальными аппроксиматорами одномерных функций и глубинных $3$ ширина- $(2d+2)$ сети являются универсальными аппроксиматорами $d$-переменные функции ( $d>1$).

См. также

• Теорема о представлении Колмогорова–Арнольда
• Представление теоремы
• Теорема «Нет бесплатного обеда»
• Теорема Стоуна – Вейерштрасса
• ряд Фурье