Информатика и искусственный интеллект: учебник для 10–11 классов

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

Обещание теоремы

В уроке о глубине мы видели, что композиция прямых даёт любую область на плоскости. Есть утверждение сильнее и точнее, из которого выросла вера в нейросети, — теорема об универсальной аппроксимации. В формулировке Джорджа Цыбенко (1989) она звучит так:

Звучит почти волшебно: не «некоторые функции», не «функции особого вида», а любую непрерывную зависимость — движение цен, форму буквы, кривую спроса — можно с любой точностью повторить сетью всего из двух слоёв. Ниже мы поймём, почему это правда, собрав такую сеть руками из простейших кирпичей.

ОсторожноСуществует — не значит найдётся

Теорема закрашивает лишь круг «существует». Найдётся ли сеть обучением и переносится ли она на новые данные — вопросы за пределами теоремы.

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

Сигмоида — это ступенька, разность двух — горбик

Начнём собирать. Один нейрон со сглаженной активацией даёт гладкую ступеньку: почти $0$ слева, почти $1$ справа, а где именно происходит переход и насколько он крут — задают вес и смещение. Уже из ступенек можно кое-что построить, но полезнее другой кирпич — горбик.

Возьмём две ступеньки, сдвинутые друг относительно друга, и вычтем одну из другой. Там, где обе ещё внизу, разность ноль; там, где обе уже наверху, тоже ноль; а между их переходами — там, где первая уже поднялась, а вторая ещё нет, — разность даёт всплеск, горбик:

\text{горбик}(x) = \sigma\bigl(k(x-a)\bigr) - \sigma\bigl(k(x-b)\bigr).

Ширину горбика задаёт расстояние между ступеньками $b-a$ , крутизну стенок — $k$ , а высоту можно домножить на любой коэффициент. Мы получили из нейронов настраиваемый локальный всплеск — кирпич, из которого сложится что угодно.

Слева две сигмоидные ступеньки, сдвинутые по горизонтали; справа их разность даёт локальный горбик-всплеск, ноль по краям и максимум между переходами ступенек — Рис. 19.1. Из двух ступенек — горбик
Две сдвинутые сигмоидные ступеньки (слева) и их разность (справа) — локальный горбик. Он ненулевой только между переходами ступенек, а его ширину, высоту и крутизну задают четыре числа-веса. Два нейрона дают один настраиваемый всплеск в любом месте оси.

Кривая как сумма горбиков

Дальше идея проста до наглядности. Любую кривую можно накрыть частоколом узких горбиков: поставить горбик в каждой точке оси и сделать его высоту равной значению функции там. Сумма таких горбиков повторит функцию ступеньками-столбиками — как гистограмма обводит плавную кривую. Чем у́же горбики и чем их больше, тем точнее сумма прилегает к цели:

f(x) \approx \sum_{i=1}^{K} c_i \cdot \text{горбик}_i(x).

А теперь вспомним: каждый горбик — это пара нейронов, а взвешенная сумма $\sum c_i(\cdot)$ — ровно то, что делает выходной нейрон. Значит, вся конструкция и есть сеть с одним скрытым слоем: скрытые нейроны рисуют ступеньки, выходной складывает их с нужными весами. Больше горбиков — шире скрытый слой — точнее приближение. Вот и всё доказательство «на пальцах»: сеть приближает любую функцию, потому что любую функцию можно сложить из локальных всплесков, а всплеск — это пара нейронов.

ВариантReLU строит из изломов

Сумма ReLU-изломов — ломаная. Достаточно частая ломаная сколь угодно точно повторяет любую гладкую кривую.

С активацией ReLU кирпич другой, но идея та же. ReLU — это шарнир, излом-«галочка»; складывая изломы с разными наклонами и точками перегиба, получают ломаную линию, а достаточно частая ломаная сколь угодно точно повторяет любую гладкую кривую. Сигмоиды дают гладкое приближение горбиками, ReLU — кусочно-линейное изломами; обе дороги ведут к одной вершине — универсальной аппроксимации.

УпражнениеСоберите горбик в нуле

Постройте горбик высотой $1$ , ненулевой примерно на отрезке $[-1,1]$ , из двух сигмоид с крутизной $k=5$ . Какие сдвиги $a,b$ взять? Проверьте значение суммы в точках $x=-2$ , $x=0$ , $x=2$ .

Сверить построение

Возьмём $\sigma(5(x+1))-\sigma(5(x-1))$ : первая ступенька поднимается около $x=-1$ , вторая — около $x=1$ . В $x=-2$ : $\sigma(-5)-\sigma(-15) \approx 0{,}007-0\approx 0$ . В $x=0$ : $\sigma(5)-\sigma(-5)\approx 0{,}993-0{,}007\approx 0{,}99$ — почти единица, вершина горбика. В $x=2$ : $\sigma(15)-\sigma(5)\approx 1-0{,}993\approx 0{,}007\approx 0$ . Горбик ровно там, где нужно. Увеличив $k$ , сделаете стенки отвеснее; уменьшив расстояние между сдвигами — у́же горбик.

УпражнениеСколько блоков на ступеньку спроса

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

Сверить рассуждение

Для $K$ уровней нужно $K-1$ переходов, то есть $K-1$ ступенек-нейронов: каждая поднимает или опускает выход на разницу соседних уровней. Схема «два нейрона на горбик» расточительна, потому что соседние горбики делят общую ступеньку — конец одного всплеска есть начало другого. Экономная запись — цепочка ступенек с накоплением: выход равен сумме всех сработавших перепадов. Так $K$ уровней обходятся $K-1$ нейронами вместо $2K$ .

На реальных данных: кривая проката по часам

Проверим теорему на живой кривой. Возьмём датасет велопроката из урока о регрессии и посчитаем средний спрос по часам рабочего дня. Кривая получается выразительная: почти ноль ночью, резкий утренний пик к восьми часам (люди едут на работу — до $477$ поездок в час), спад к полудню, второй, ещё выше, вечерний пик к пяти-шести часам ( $525$ ), и спад к ночи. Два горба и провал между ними — функция, которую одной прямой и близко не передать.

Обучим на этой кривой сеть из $K$ сигмоидных блоков и посмотрим, как растёт точность. Один блок способен лишь на ступеньку — ошибка велика. Четыре блока намечают два горба грубо; восемь уже уверенно ловят оба пика; шестнадцать повторяют кривую почти в точности, а двадцать четыре — по числу часов — проходят через все точки без ошибки. Среднеквадратичная ошибка падает от $127$ поездок при одном блоке до $60$ при восьми, $19$ при шестнадцати и нуля при двадцати четырёх. Теорема не соврала: добавляя блоки, приближение можно довести до любой точности.

Четыре панели: реальная двугорбая кривая спроса велопроката по часам и её приближение суммой сигмоид при 2, 4, 8 и 16 блоках; с ростом числа блоков приближение всё точнее повторяет утренний и вечерний пики — Рис. 19.2. Спрос проката по часам, собранный из сигмоидных блоков
Реальный спрос велопроката по часам рабочего дня (точки) и его приближение суммой сигмоидных блоков при $K=2,4,8,16$ . Два блока дают одну ступень, четыре намечают горбы, восемь ловят оба пика, шестнадцать почти сливаются с данными. Число под каждой панелью — среднеквадратичная ошибка в поездках. Двугорбую кривую собрали из простых сглаженных ступенек.

УпражнениеКрутизна и гладкость

В формуле горбика $\sigma(k(x-a))-\sigma(k(x-b))$ крутизну задаёт $k$ . Что происходит с горбиком при $k\to\infty$ и при $k\to 0$ ? Как это связано с выбором между гладким и «квадратным» приближением кривой?

Сверить рассуждение

При $k\to\infty$ сигмоиды превращаются в жёсткие ступеньки, и горбик становится прямоугольным столбиком с отвесными стенками — приближение делается «пиксельным», как гистограмма. При $k\to 0$ сигмоиды расплываются в почти прямые, горбик размазывается в пологий холм и перестаёт быть локальным. Крутизна $k$ — это ручка между гладкостью и резкостью приближения: большие $k$ дают точные, но ступенчатые формы; малые — гладкие, но грубые. Обучение подбирает $k$ каждого нейрона так, чтобы кривая вышла и точной, и гладкой там, где это нужно.

Ширина против глубины

Раз одного скрытого слоя достаточно, зачем вообще глубокие сети? Тут кроется важная тонкость. Теорема гарантирует, что широкий слой справится, но молчит о цене: для некоторых функций число нейронов в одном слое растёт астрономически:

\text{нейронов в одном слое} \sim \left(\tfrac{1}{h}\right)^{d} \quad\text{против}\quad \text{в глубокой сети} \sim d\cdot\log\tfrac1h ,

то есть экспоненциально с размерностью входа $d$ против почти линейно. Проклятие широкого слоя в том, что горбиками покрывать многомерное пространство неимоверно дорого: в двух измерениях нужен частокол горбов на плоскости, в ста измерениях — в стомерном кубе.

Глубина обходит эту цену. Многослойная сеть строит признаки из признаков: первый слой ловит простые куски, второй комбинирует их в сложные, третий — в ещё более сложные, и так одна и та же функция часто представляется экспоненциально меньшим числом нейронов, чем в одном широком слое. Универсальность — довод в пользу того, что сети вообще могут всё; эффективность — довод в пользу того, чтобы делать их глубокими. Обе теоремы верны, и вместе они объясняют, почему на практике побеждают не широкие, а глубокие сети.

Схема: слева широкая мелкая сеть с одним слоем из многих нейронов, справа глубокая сеть из нескольких слоёв с малым числом нейронов; обе представляют одну функцию, но глубокая — куда меньшим числом нейронов — Рис. 19.3. Одна функция: широко и мелко против узко и глубоко
Одну и ту же сложную функцию можно собрать широким мелким слоем из множества нейронов (слева) или глубокой сетью из немногих (справа). Обе возможны по теореме, но глубокая часто обходится экспоненциально меньшим числом нейронов. Универсальность говорит «сеть может всё», эффективность — «делай её глубокой».

УпражнениеЦена размерности

Чтобы покрыть отрезок горбиками с шагом $h$ , нужно примерно $1/h$ блоков. А чтобы покрыть с тем же шагом $d$ -мерный куб? Оцените число горбиков и объясните, почему одного широкого слоя хватает в теории, но не на практике для картинок ( $d$ в тысячах пикселей).

Сверить оценку

В одном измерении блоков $\sim 1/h$ ; в $d$ измерениях горбами приходится замостить весь куб, и их число растёт как $(1/h)^d$ — экспоненциально по размерности. Для картинки $28\times 28=784$ пикселя даже грубый шаг даёт немыслимое число блоков. Это и есть проклятие размерности: универсальность одного слоя честна математически, но цена её — экспоненциальная ширина. Глубина разрывает эту экспоненту, строя признаки из признаков, — оттого распознавание картинок и делают глубокими сетями, а не одним гигантским слоем.

Чего теорема не обещает

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

Хуже того, всемогущество может выйти боком. Сеть, способная изобразить любую функцию, способна и в точности запомнить обучающие точки вместе со всем их шумом — и опозориться на новых данных. Мы уже видели этот призрак у полинома, идеально прошедшего через планеты и рухнувшего на экзопланетах в уроке о Кеплере; у нейросетей он тот же. Мощность модели — это возможность, а не гарантия: слишком мощная сеть переобучается так же легко, как слишком слабая недоучивается. Как найти золотую середину — предмет отдельного урока о переобучении. Пока запомним трезвую мысль: то, что сеть может приблизить что угодно, не делает её хорошей моделью; хорошей её делает то, чему она научилась на данных и как это переносится на новые.

Русская линия: приближать функции простым

Идея приближать сложную функцию суммой простых родилась в русской математике за век до нейросетей. Её основателем был Пафнутий Чебышёв, создавший в 1850-х теорию приближений: как наилучшим образом заменить неудобную функцию многочленом. А в 1912 году Сергей Бернштейн дал конструктивное доказательство теоремы Вейерштрасса — построил из простых блоков (многочленов Бернштейна) явное приближение любой непрерывной функции. Это прямой математический предок нашей теоремы: там простые блоки — многочлены, здесь — сигмоидные ступеньки, но мысль одна и та же: любую непрерывную зависимость можно собрать из достаточного числа простых кирпичей. Нейросети унаследовали эту вековую традицию, поменяв кирпич.

ИсторияМногочлены Бернштейна

Базис Бернштейна: колокол на каждую точку отрезка. Взвесив их значениями функции, получаем её приближение — конструкция 1912 года.

Бернштейн приближал функцию $f$ на отрезке $[0,1]$ суммой $\sum_k f(k/n)\binom{n}{k}x^k(1-x)^{n-k}$ — комбинацией простых «колоколов», каждый из которых отвечает за свою точку отрезка. Сравните с нашим частоколом горбиков: там нейронные всплески, здесь полиномиальные, но обе конструкции берут значения функции в точках и взвешивают ими локальные блоки. Бернштейн строил свои блоки в 1912 году, за семь десятилетий до Цыбенко, — теория приближений давно знала то, что нейросети переоткрыли на новом языке.

Лаборатория: соберите кривую из блоков

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

Сборка: могущество и его цена

Универсальная аппроксимация — фундамент веры в нейросети: сеть даже с одним скрытым слоем приближает любую непрерывную функцию, потому что любую функцию можно сложить из локальных всплесков, а всплеск — это пара нейронов. Мы собрали двугорбую кривую спроса из сигмоидных блоков и видели, как ошибка падает до нуля с ростом их числа. Но у могущества две цены. Первая — эффективность: широкому слою нужны иногда экспоненциально много нейронов там, где глубокий обходится немногими, — оттого сети и делают глубокими. Вторая, важнейшая, — честность: теорема говорит лишь о существовании сети, а не о том, что обучение её найдёт и что она не переобучится. Способность приблизить что угодно — это возможность, а не качество. Оттого весь остаток курса будет не о том, что сеть может, а о том, как научить её находить нужные веса по данным и не запоминать шум. С этого — с измерения ошибки и спуска по ней — начинается следующий блок.

Задачи

4баллов

Существование против обучения: возьмите функцию из пяти случайных точек и постройте руками сеть-частокол, точно проходящую через них (по горбику на точку). Затем обучите с нуля градиентным спуском сеть той же ширины на тех же точках и сравните: приходит ли обучение к столь же хорошему решению? Объясните, что показывает расхождение, ссылаясь на разницу «существует» и «находится». Рубрика: 2 балла за ручную сеть, 2 за обученную и вывод.

6баллов

Мощность и переобучение: возьмите $10$ точек, лежащих на прямой с небольшим шумом. Обучите на них сети возрастающей ширины ( $2,5,20,100$ скрытых нейронов) и для каждой постройте предсказание на плотной сетке. Покажите, что широкие сети идеально проходят через шумные точки, но дико виляют между ними, и свяжите это с полиномом из урока о Кеплере и с грядущим уроком о переобучении. Рубрика: 3 балла за сети и графики, 3 за анализ виляния и связь с переобучением.

Из простых блоков — универсальный аппроксиматор