или нет?
В математике есть теоремы, названия которых могут показаться шуткой: теорема о четырёх красках, теорема о причёсывании ежа, теорема о бесконечных обезьянах. К их числу относится и No Free Lunch Theorem — в буквальном переводе «бесплатных ланчей не бывает», а в более литературном — «бесплатный сыр бывает только в мышеловке».
⠀
За этим названием скрывается результат современной теории оптимизации и ML, о котором часто вспоминают, когда говорят о нейросетях и ИИ.
⠀
Смысл теоремы примерно такой: если рассматривать все возможные задачи, то никакой алгоритм не может быть лучше любого другого.На первый взгляд это звучит абсурдно. Неужели сложнейшие нейронные сети ничем не превосходят примитивные алгоритмы? Оказывается, всё зависит от того, какие задачи мы рассматриваем.
⠀
Представим себе две выборки данных. Первая напоминает прямую с небольшим шумом. Вторая выглядит как сложная волнообразная кривая. Где больше шума?
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀___________________________
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀
Большинство скажет, что первая задача проще второй: прямую легко описать уравнением вида y = ax + b, а извилистую волну придётся моделировать чем-то более сложным. Но так кажется лишь потому, что мы уже выбрали язык описания.
Если моделью служит линейная функция, первая выборка действительно оказывается простой. Но если модель — например, волновой пакет с единственным параметром (сдвигом по оси), картина меняется. Теперь вторая выборка описывается одним параметром.
Иными словами, простота задачи — не абсолютное свойство данных. Она зависит от того, какую модель мы заранее решили использовать.
⠀
⠀⠀⠀⠀История вопроса
⠀⠀⠀⠀⠀⠀⠀
⠀
В середине XVIII века философ Дэвид Юм сформулировал проблему индукции: можем ли мы логически обосновать перенос выводов из уже увиденного на то, чего мы ещё не видели?
⠀
Если все лебеди, которых мы встречали, были белыми, у нас нет логического основания утверждать, что и следующий лебедь окажется белым, — потому что прошлый опыт сам по себе не гарантирует будущего.
⠀
Та же логика лежит в основе No Free Lunch: без дополнительных предположений о мире ни один способ обучения на прошлых данных не имеет преимущества перед другим.
⠀⠀⠀⠀⠀⠀
⠀
Позже, в 1990-х, физик Дэвид Вольперт работал в Санта-Фе, где учёные годами пытались найти общий язык для описания сложности. Его интересовало, почему одни эвристики поиска работают на одних задачах прекрасно, а на других — из рук вон плохо, и можно ли вообще найти универсально хорошую стратегию поиска.
В 1997 году он опубликовал результат, который сегодня и называют No Free Lunch Theorem: если усреднить качество работы любых двух алгоритмов оптимизации по всему пространству возможных целевых функций, оказывается, что оно совпадает. Ни один метод не имеет преимущества перед другим — включая обычный случайный перебор.
⠀
Следствие теоремы выглядит парадоксально: если алгоритм работает исключительно хорошо на каком-то классе задач, обязательно найдётся другой класс задач, на котором тот же алгоритм будет работать исключительно плохо.
⠀
На этом месте многие делают неверный вывод: «Значит, бессмысленно создавать новые алгоритмы?». Совсем наоборот!
Секрет в том, что реальный мир не состоит из математических задач. Мы не пытаемся распознавать произвольные функции — мы работаем с данными, имеющими реальную структуру. Поэтому поиск лучшего алгоритма — это не поиск самой мощной математической конструкции, а поиск правильных предположений о природе задачи. Так что успех ИИ зависит не от универсальности алгоритма, а от того, насколько хорошо он учитывает устройство нашего мира. Будущему AGI достаточно работать не во всех мыслимых вселенных, а в нашей.
Накидайте Вольперту 🏆 за кликбейтную теорему. А нам ❤️, если хотите узнать, причём тут теория сложности и бритва Оккама.
#это_база
