Мы говорим машине: «Выбери 1, если два входа равны 1, иначе выбирай 0». Это функция «И», таблица истинности которой, то есть список всех выходных показателей для всех возможных конфигураций входов, будет следующей: (00, 0) (01, 0) (10, 0) (11, 1).
Возьмем колонку № 6. Говорим машине: «Выбери 1, если только один из двух входов равен 1, иначе выбирай 0.» Таким образом, таблица истинности будет следующей: (00, 0) (01, 1) (10, 1) (11, 0).
Это функция «исключающего ИЛИ», которую перцептрон не может вычислить (см. главу 3, рис. 3.6). Напомним, что это ограничение перцептрона связано с тем, что он может «вычислять» только линейно разделимые функции.
Цель – увидеть, сколько комбинаций входов возможно из серии n 0 и 1, то есть из n бит.
Если n равно 1, то 21 = 2.
Если n равно 2, то 21 умножается на 2, то есть 22 = 4.
Если n равно 3, то 22 умножаются на 2, то есть 23 = 8; затем 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 и т. д.
Каждый раз, когда мы добавляем 1 бит, мы удваиваем количество возможных комбинаций. Если у нас есть n битов в качестве входов, будет 2n возможных конфигураций входа. Он начинается с 00000 … затем 00001, затем 00010, 00011 и т. д. Когда мы сделаем подсчет, мы поймем, что это 2n.
Конкретная булева функция представляет собой список от 2 до n битов.
Каждая конфигурация из n битов входа связана с одним из двух возможных выходов 0 или 1. Сколько существует конфигураций из 2n битов? Это будет (22)n. Таково количество возможных булевых функций для n битов входа – цифра астрономическая даже для малых значений n.
Если у нас 25-битная функция входа, такая как перцептрон в главе 2, количество возможных функций этих 25 битов уже равно 233 554 432. Это число, состоящее в десятичной записи из 10 100 890 цифр, что непредставимо больше, чем число атомов в видимой части Вселенной (их количество оценивается числом, состоящим примерно из 80 цифр)! И оно достигается за счет использования только простых бинарных функций.
В данном примере мы работали над булевой функцией с двумя входами и 16 возможными функциями. Среди таких 16 функций есть две, которые не могут быть достигнуты перцептроном или другим линейным классификатором (исключающим ИЛИ и его противоположностью), и остаются еще 14, которые могут быть достигнуты линейным классификатором. Это большое количество.
Но по мере увеличения числа битов входа количество функций, которые может выполнять перцептрон, сокращается. Другими словами, как только n существенно возрастет, n-битная булева функция вряд ли будет достижима перцептроном.
Это можно визуализировать таким образом: представим, что мы произвольно добавляем на плоскость символы + и –. Есть ли возможность разделить их пополам прямой линией? Если у нас всего 3 точки, мы сможем это сделать почти всегда (если точки не выровнены!). Но если у нас их миллионы, очень маловероятно, что мы сможем разделить их прямой линией. Перцептрон не может полностью изучить обучающую систему, состоящую из множества примеров.
Вывод: линейный классификатор (однослойная архитектура нейронов), такой как перцептрон, недостаточно гибок. Как только количество обучающих точек превышает количество входов линейного классификатора, шансы, что он может отделить точки класса A от точек класса B, сильно уменьшаются. Это теорема была продемонстрирована американским статистиком из Стэнфордского университета Томасом Ковером в 1966 г.[50]
И наоборот, слишком большая гибкость в семействе функций, достижимая системой обучения, равносильна отсутствию обучения.
Пример
Возьмем случай из главы 2 с двоичными изображениями C и D на сетке 5 × 5 пикселей. При этом возможны 233 554 432 возможных 25-битных функций. Если у нас 100 обучающих примеров, будет указано значение функции для 100 строк из нашей таблицы булевых функций. Но значение функции для остальных 33 554 332 строк (то есть 33 554 432 – 100) не будет указано. Следовательно, есть 233 554 332 функций, которые совместимы с данными, то есть дают правильный ответ на 100 примерах. Как машина может выбрать нужную функцию среди этого гигантского числа? Как выбрать одну из функций, которая будет правильно классифицировать C и D, если их нет в 100 обучающих примерах?
Регуляризация: ограничение возможностей модели
Данное наблюдение приводит к метафизическим вопросам: если обучающаяся машина может вычислить все возможные функции, какую стратегию она будет использовать, чтобы выбрать приемлемую функцию из огромного количества функций, совместимых с обучающими примерами, то есть среди всех функций, которые дают правильный ответ? Цифра огромна. Требуется индукционное смещение, то есть критерий для решения, какую функцию выбрать. Это смещение индукции и есть наша «бритва Оккама»: алгоритм обучения должно выбрать более простую функцию. Однако теперь нужно определить понятие простоты так, чтобы можно было измерить (или вычислить) простоту любой функции. Здесь может быть полезным любое понятие простоты (или сложности). Что нам нужно создать, так это регуляризатор, программу (или математическую функцию), которая вычисляет сложность функции. Например, в семействе многочленов возможной мерой сложности модели является степень многочлена. Для нейронной сети это может быть количество нейронов или количество соединений.
Чтобы обучение было эффективным, необходимо найти компромисс между ошибкой обучения и сложностью функции, используемой для получения этой ошибки (или возможностями семейства функций, из которых она получена). Чем выше сложность функции, тем меньше ошибка обучения, но тем меньше и вероятность того, что система будет склонна к обобщению.
Вместо того чтобы минимизировать только ошибку обучения L(w), необходимо минимизировать новый критерий:
L(w) = L(w) + a * R(w)
где L(w) – ошибка обучения, R(w) – наш регуляризатор (то есть наша мера сложности функции, параметры которой равны w), a – константа, которая управляет компромиссом между моделированием данных и минимизацией сложности модели.
Такой обходной путь – не просто прихоть математика. Метод регуляризации повсеместно используется при создании систем ИИ на основе обучения. На практике мы предпочитаем использовать термин регуляризации, который легко вычислить и минимизировать с помощью градиентного спуска. Для линейных классификаторов и нейронных сетей мы часто используем сумму квадратов весов.
Для линейного классификатора использование в качестве регуляризатора суммы квадратов весов приводит к тому, что система помещает границу между классами «посередине» нейтральной зоны, расположенной между точками двух классов (то, что сторонники SVM называют «максимизация пределов»).
Другой регуляризатор – это сумма абсолютных значений весов.
Использование суммы абсолютных значений подталкивает систему к поиску решения, в котором ненужные (или не очень полезные) веса равны 0. Когда мы упорядочиваем обучение коэффициентов многочлена таким образом, это исключит коэффициенты условия высокой степени,
