что означает выражение нет бесплатного обеда по free lunch

Какое значение имеет теорема «Нет бесплатного обеда» для машинного обучения?

Теорема об отсутствии бесплатного обеда (НФЛ) (см. Статью «Коэволюционные бесплатные обеды » Дэвида Х. Вольперта и Уильяма Дж. Макриди)

любые два алгоритма эквивалентны, когда их производительность усредняется по всем возможным проблемам

Действительно ли теорема «Нет бесплатного обеда» верна? Что это на самом деле означает? Хороший пример (в контексте ML), иллюстрирующий это утверждение, был бы хорош.

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

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

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

Теоремы об отсутствии бесплатного обеда говорят о том же. Если вы не знаете, как выглядит ваше пространство поиска, то, если вы итеративно уточняете свое предположение о том, как выглядит хорошее решение, в ответ на сделанные вами в прошлом наблюдения о том, как выглядят хорошие решения (т.е. данные), то такая же вероятность, что выполняемая вами операция помогает, так же, как и то, что она причиняет боль. Вот почему ключевым моментом является «усреднение по всем возможным проблемам оптимизации». Для любой задачи оптимизации, где восхождение на гору является хорошей стратегией после k ‘ role=»presentation»> k ходы, мы можем сделать один, который идентичен, за исключением того, что ход восхождения на kth холм приводит к ужасному решению. Фактическое доказательство более тонкое, чем это, но это основная идея.

Очень краткое краткое изложение может быть:

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

Некоторые общие ответы:

Независимо от того, это бесспорно, что некоторые алгоритмы лучше, чем другие, в некоторых поддоменов (мы можем увидеть это эмпирически). НФЛ говорит нам, что, чтобы быть там лучше, они должны быть хуже где-то еще. Вопрос для обсуждения заключается в том, являются ли «где-то еще» настоящими проблемами или чисто искусственными.

Источник

Что означает выражение нет бесплатного обеда по free lunch

Войти

Авторизуясь в LiveJournal с помощью стороннего сервиса вы принимаете условия Пользовательского соглашения LiveJournal

Записки на полях

Ноябрь 2021

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

Интересно, что NFL оказывается тесно связана с Колмогоровской сложностью.

Результат интересный, но, в общем, довольно логичный.

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

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

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

Я далёк от подобных задач, так что может быть глупый вопрос задам.

Ну, т.е., если общего подхода нет, возможно мы можем как-то [автоматически] классифицировать функции и интеллектуально выбирать способ оптимизации.

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

как думаете, насколько сложная функция должна быть, что бы сделать жизнь (белковую)? Думаю это ОЧЕНЬ сложная функция (и, подозреваю, ученые обычными методами не смогут повторить еще долго).

Это что касается задач «вообще», «про жизнь».

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

К чему это я веду: аналоги ГА работают в нашем мире не только на компьютерах. И они доказали право на существование.

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

Поскольку я почти ни с чем из Вами написанного не согласен, буду отвечать по частям 🙂

Это почему Вы так решили?
Во-первых, буду придираться. Если Вы пишете «создание», то это слово предполагает, что есть кто-то, кто создает. Бог?

Во-вторых, и создание, и возникновение, никак не объясняется и не может быть объяснено приспособленностью к размножению. Возникновению жизни предшествовало появление аминокислот, которые не обладают способностью к размножению.

Поэтому Ваша функция «Жизни» не подходит.

(Кстати, число мутаций, по моему, занижено и последнее число следует повысить на несколько порядков.

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

Принимаю уточнение, хотя я как раз и указал, что свойства ГА зависят очень сильно от способов кодирования, скрещивания, мутации и т.п. Общий только принцип.

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

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

Нет ничего проще случайного поиска (Монте-Карло), о чем Вы? И таки Вы не верите, что бесплатного обеда не бывает? 🙂

что касается мутаций, то они пусть редко, но всё-таки двигают человечество вперед.

К примеру 10 тысяч лет назад взрослые люди не могли усваивать молоко. Однако позже в геноме людей (в разных племенах в разное время) произошли мутации, которые позволили взрослым усваивать молоко. http://www.membrana.ru/print.html?1166028720 С тех пор эти мутированные гены встречаются часто, потому что закрепились в геноме как полезные.

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

> Нет ничего проще случайного поиска
Я не о простоте, а о скорости нахождения минимума (пусть и не глобального, а просто «хорошего»).

Дадим одинаковое время разным людям: «найти самое маленькое значение у функции f(x)=. «. При этом функцию подберем довольно сложную, да еще с ограничениями (как это часто бывает в жизни). Это может быть и поиск молекулы-катализатора химической реакции или нахождение формы манипулятора робота, который работает в быстром течении жидкости. Программист может выбирать любой метод решения задачи. Выиграет тот, кто за (к примеру) неделю выдаст наиболее хорошее решение.

отдельно упомянем вариант «Программист, выбравший симбиоз методов A и B».

Мой прогноз:
a) при высокой сложности задачи аналитик почти не имеет шанса;
б) Монте-карло получит среднее(посредственное) решение, которое можно будет легко улучшить градиентным спуском
в) ГА получит хорошее решение
в случае, если программист сможет быстро(!) аналитически решить хоть часть задачи, то (вместе с ГА) он может получить отличное решение.

Твой прогноз, скорее всего, будет другой.

Что касается метода симуляции отжига, то я его пробовал. На сложных задачах он хуже.

Ты так и не сказал, на каких задачах получил лучший результат у Монте-Карло и более плохой у ГА.

Какой метод ты предпочитаешь, когда аналитически не можешь разобрать (решить) функцию?

Дадим одинаковое время разным людям: «найти самое маленькое значение у функции f(x)=. «. При этом функцию подберем довольно сложную, да еще с ограничениями (как это часто бывает в жизни). Это может быть и поиск молекулы-катализатора химической реакции или нахождение формы манипулятора робота, который работает в быстром течении жидкости. Программист может выбирать любой метод решения задачи. Выиграет тот, кто за (к примеру) неделю выдаст наиболее хорошее решение.

Аналитические решения не рассматриваем. Реальные нелинейные задачи с десятками, а то и сотнями размерностей аналитически не решаются.

В соответствии с теоремой о бесплатном обеде (с чего мы и начали), у 1 и 2 равные шансы при одинаковом времени работы (временем здесь является количество вычислений целевой функции). Но так как запрограммировать Монте-Карло гораздо проще и быстрее, чем ГА, то за неделю можно перебрать куда большее количество случайных вариантов и найти наименьший, чем с ГА, для которого придется писать программу (или использовать библиотеку) и подбирать коэффициенты. То есть Монте-Карло выиграет. Ведь казино выигрывает всегда 🙂

И это не прогноз, а научно доказанный факт. О чем и был мой пост.

Источник

Теорема «Бесплатных обедов не бывает»

Через 250 лет после того, как Юм подбросил нам свою гранату, ей придал элегантную математическую форму Дэвид Уолперт, физик, ставший специалистом по машинному обучению. Его результаты, известные как уже упомянутая выше теорема «Бесплатных обедов не бывает», ставят ограничения на то, как хорош может быть обучающийся алгоритм. Ограничения довольно серьезные: никакой обучающийся алгоритм не может быть лучше случайного угадывания! Вот и приехали: Верховный алгоритм, оказывается, — это просто подбрасывание монетки. Но если серьезно, как может быть, что никакой обучающийся алгоритм не в состоянии победить угадывание с помощью орла или решки? И почему тогда мир полон очень успешных алгоритмов, от спам-фильтров до самоуправляющихся машин (они вот-вот появятся)?

Теорема «Бесплатных обедов не бывает» очень сильно напоминает причину, по которой в свое время Паскаль проиграл бы пари. В своей книге «Мысли», опубликованной в 1669 году, он заявил, что нам надо верить в христианского Бога, потому что, если он существует, это дарует нам вечную жизнь, а если нет — мы мало что теряем. Это был замечательно утонченный аргумент для того времени, но, как заметил на это Дидро, имам может привести точно такой же довод в пользу веры в Аллаха, а если выбрать неправильного бога, придется расплачиваться вечными муками в аду. В целом, учитывая огромное количество мыслимых богов, вы ничего не выиграете, выбрав в качестве объекта своей веры одного из них в пользу любого другого, потому что на любого бога, который говорит «делай то-то», найдется еще один, который потребует нечто противоположное. С тем же успехом можно просто забыть о богах и наслаждаться жизнью без религиозных предрассудков.

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

Однако не торопитесь сдаваться и списывать со счетов машинное обучение и Верховный алгоритм. Дело в том, что нас заботят не все возможные миры, а только тот, в котором живем мы с вами. Если мы уже знаем что-то об этом мире и введем это в наш обучающийся алгоритм, у него появится преимущество перед произвольным угадыванием. На это Юм ответил бы, что знание как таковое тоже должно быть получено путем логической индукции и, следовательно, ненадежно. Это верно, даже если знание закодировано в наш мозг эволюцией. Однако нам приходится идти на этот риск. Еще можно задуматься: есть ли бесспорный, фундаментальный самородок знаний, на котором можно построить всю свою индукцию? (Что-то вроде Декартова «Я мыслю, следовательно, я существую», хотя сложно придумать, как превратить конкретно это утверждение в обучающийся алгоритм.) Я думаю, ответ — «да, есть», и мы увидим этот самородок в главе 9.

Практическое следствие теоремы «Бесплатных обедов не бывает» — то, что обучение без знаний невозможно. Одних данных недостаточно. Если начинать с чистого листа, мы придем к чистому листу. Машинное обучение — своего рода насос знаний. С помощью машинного обучения можно «выкачать» из данных много знаний, но сначала нам надо его заполнить данными, как насос перед пуском заполняют водой.

Машинное обучение с точки зрения математики относится к категории некорректно поставленных задач, так как единственного решения не существует. Вот простой пример: сумма каких двух чисел равна 1000? Если исходить из того, что числа положительные, у этой задачи 500 возможных ответов: 1 и 999, 2 и 998 и так далее. Чтобы решить некорректно поставленную задачу, придется ввести дополнительные условия. Если я скажу, что второе число в три раза больше первого, — все станет просто! Ответ — 250 и 750.

Том Митчелл, ведущий символист, называет это «тщетностью беспристрастного обучения». В обычной жизни слово «пристрастный» имеет негативный оттенок: предвзятость суждений — это плохо. Однако в машинном обучении предвзятые суждения необходимы. Без них нельзя учиться. На самом деле они незаменимы и для человеческого познания, но при этом так жестко встроены в наш мозг, что мы принимаем их как должное. Вопросы вызывает только пристрастность, выходящая за эти рамки.

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

У машинного обучения имеется неотъемлемый элемент азартной игры. В конце первого фильма про Грязного Гарри Клинт Иствуд гонится за ограбившим банк бандитом и раз за разом в него стреляет. Наконец грабитель повержен. Он лежит рядом с заряженным ружьем и не знает, хватать его или нет. Было шесть выстрелов или только пять? Гарри сочувствует (если можно так выразиться): «Тебе надо лишь спросить: “Повезет или нет?” Ну как, мерзавец?» Этот вопрос специалисты по машинному обучению должны задавать себе каждый день, когда они приходят на работу. Повезет или нет? Как и эволюция, машинное обучение не будет каждый раз попадать в десятку. Вообще говоря, ошибки — не исключение, а правило. Но это нормально, потому что промахи мы отбрасываем, а попаданиями пользуемся, и важен именно совокупный результат. Когда мы получаем новую частицу знаний, она становится основой для логической индукции еще большего знания. Единственный вопрос — с чего начать.

Источник

СОДЕРЖАНИЕ

Обзор

«Теорема Вольперта и Макреди о запрете бесплатного обеда», как прямо сформулировали сами Вольперт и Макреди, заключается в том, что «любые два алгоритма эквивалентны, если их производительность усредняется по всем возможным задачам». Результаты «без бесплатного обеда» показывают, что сопоставление алгоритмов задачам дает более высокую среднюю производительность, чем применение фиксированного алгоритма ко всем. Игель, Туссент и Инглиш установили общее условие, при котором бесплатный обед не предоставляется. Хотя это физически возможно, в точности нет. Дросте, Янсен и Вегенер доказали теорему, которую они интерпретируют как указание на то, что на практике «(почти) нет бесплатного обеда».

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

Теоремы

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

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

Исходные теоремы об отсутствии бесплатного обеда (NFL) предполагают, что все целевые функции с одинаковой вероятностью будут входить в алгоритмы поиска. С тех пор было установлено, что NFL существует тогда и только тогда, когда, грубо говоря, «перемешивание» целевых функций не влияет на их вероятности. Хотя это условие для НФЛ физически возможно, утверждалось, что оно определенно не выполняется в точности.

Колмогоровская случайность

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

Практически все целевые функции имеют настолько высокую колмогоровскую сложность, что их нельзя сохранить на конкретном компьютере. Точнее, если мы смоделируем данный физический компьютер как регистровую машину с памятью заданного размера порядка памяти современных компьютеров, то большинство объективных функций не могут быть сохранены в их памяти. Типичная целевая функция или алгоритм содержит больше информации, чем по оценке Сета Ллойда, которую наблюдаемая вселенная способна зарегистрировать. Например, если каждое возможное решение закодировано как последовательность из 300 нулей и единиц, а значения качества равны 0 и 1, то большинство целевых функций имеют сложность Колмогорова не менее 2300 бит, и это больше, чем граница Ллойда, равная 10. 90 ≈ 2299 бит. Отсюда следует, что исходная теорема «без бесплатного обеда» неприменима к тому, что может храниться на физическом компьютере; вместо этого нужно применять так называемые «ужесточенные» теоремы об отсутствии бесплатного обеда. Также было показано, что результаты НФЛ применимы к невычислимым функциям.

Формальный синопсис

Источник

По сути, это говорит о том, что когда все функции f равновероятны, вероятность наблюдения произвольной последовательности из m значений в ходе поиска не зависит от алгоритма поиска. Теорема 1 устанавливает «более тонкий» результат НФЛ для изменяющихся во времени целевых функций.

Интерпретации результатов

На практике в хранилище компьютеров помещаются только сильно сжимаемые (далеко не случайные) целевые функции, и не всегда каждый алгоритм хорошо работает почти со всеми сжимаемыми функциями. Как правило, включение в алгоритм предварительных знаний о проблеме дает преимущество в производительности. Хотя результаты НФЛ представляют собой, в строгом смысле, теоремы о полной занятости для специалистов по оптимизации, важно иметь в виду более широкий контекст. Во-первых, у людей часто мало предварительных знаний, с которыми можно работать. Во-вторых, использование предшествующих знаний не дает большого увеличения производительности при решении некоторых проблем. Наконец, человеческое время очень дорого по сравнению с компьютерным. Во многих случаях компания предпочла бы медленно оптимизировать функцию с помощью неизмененной компьютерной программы, а не быстро с помощью программы, модифицированной человеком.

Результаты НФЛ не указывают на то, что бесполезно пытаться решать проблемы с неспециализированными алгоритмами. Никто не определил долю практических задач, для которых алгоритм быстро дает хорошие результаты. И есть практический бесплатный обед, нисколько не противоречащий теории. Выполнение алгоритма на компьютере стоит очень мало по сравнению с затратами человеческого времени и преимуществом хорошего решения. Если алгоритму удается найти удовлетворительное решение за приемлемое время, небольшие вложения принесут большую отдачу. Если алгоритм не работает, то мало что теряется.

Коэволюция

Источник