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

В математической теории искусственных нейронных сетей универсальными теоремами аппроксимации являются теоремы следующего вида: Учитывая семейство нейронных сетей, для каждой функции $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.

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

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

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

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

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

Количественные

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

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

Колмогоровская сеть

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

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

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

Варианты

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

Свойство универсальной аппроксимации сетей с ограниченной шириной изучалось как двойственное к классическим результатам универсальной аппроксимации сетей с ограниченной глубиной. Для входного размера 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$).

См. также

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