Никаких бесплатных обедов в поиске и оптимизации

В области вычислительной сложности и оптимизации теорема о бесплатном обеде - это результат, который утверждает, что для определенных типов математических задач вычислительные затраты на поиск решения, усредненные по всем задачам в классе, одинаковы для любого метода решения. Название отсылает к поговорке « нет такого понятия, как бесплатный обед », то есть ни один метод не предлагает «короткого пути». Это при условии, что пространство поиска является функцией плотности вероятности . Это не применимо к случаю, когда пространство поиска имеет базовую структуру (например, является дифференцируемой функцией), которую можно использовать более эффективно (например, метод Ньютона в оптимизации ), чем случайный поиск, или даже имеет решения в замкнутой форме (например, экстремумы квадратичного многочлена), которые можно определить вообще без поиска. При таких вероятностных предположениях результаты всех процедур, решающих задачи определенного типа, статистически идентичны. Красочный способ описания такого обстоятельства, предложенный Дэвидом Вулпертом. и Уильям Г. Макриди в связи с проблемами поиска ^[1] и оптимизация, ^[2]это значит, что бесплатного обеда не существует . Ранее Вулперт не вывел никаких теорем о бесплатном обеде для машинного обучения ( статистический вывод ). ^[3] Прежде чем статья Вулперта была опубликована, Каллен Шаффер независимо доказал ограниченную версию одной из теорем Вулперта и использовал ее для критики текущего состояния исследований машинного обучения по проблеме индукции. ^[4]

«нет бесплатного обеда» В метафоре каждый «ресторан» (процедура решения проблемы) имеет «меню», связывающее каждую «тарелку с обедом» (проблему) с «ценой» (выполнением процедуры решения проблемы). Меню ресторанов идентичны, за исключением одного: цены варьируются от одного ресторана к другому. Для всеядного человека , который заказывает каждую тарелку с такой же вероятностью, как и любую другую, средняя стоимость обеда не зависит от выбора ресторана. Но веган , который регулярно ходит на обед с хищником , стремящимся к экономии, может заплатить за обед высокую среднюю цену. Чтобы методично снижать среднюю стоимость, необходимо заранее знать: а) что заказывать и б) сколько будет стоить заказ в различных ресторанах. То есть улучшение эффективности решения проблем зависит от использования предварительной информации для сопоставления процедур с проблемами. ^[2]^[4]

Формально, бесплатного обеда не бывает, если распределение вероятностей экземпляров задачи таково, что все решатели задач имеют одинаково распределенные результаты. В случае поиска экземпляром проблемы в этом контексте является конкретная целевая функция , а результатом является последовательность значений, полученных при оценке возможных решений в области определения функции. Для типичных интерпретаций результатов поиск представляет собой процесс оптимизации . В поиске нет бесплатного обеда тогда и только тогда, когда распределение целевых функций инвариантно относительно перестановки пространства вариантов решений. ^[5]^[6]^[7] На практике это условие в точности не выполняется, ^[6] но теорема «(почти) отсутствия бесплатных обедов» предполагает, что она приблизительно верна. ^[8]

Обзор [ править ]

Некоторые вычислительные задачи решаются путем поиска хороших решений в пространстве возможных решений . Описание того, как неоднократно выбирать возможные решения для оценки, называется алгоритмом поиска . В конкретной задаче разные алгоритмы поиска могут давать разные результаты, но для всех задач они неотличимы. Отсюда следует, что если алгоритм достигает превосходных результатов в некоторых задачах, он должен расплачиваться худшими результатами в других задачах. В этом смысле бесплатного обеда в поиске не бывает. ^[1] Альтернативно, следуя Шафферу, ^[4] производительность поиска сохраняется . Обычно поиск интерпретируется как оптимизация , и это приводит к наблюдению, что в оптимизации не бывает бесплатных обедов. ^[2]

«Теорема Уолперта и Макриди об отсутствии бесплатного обеда», как ясно изложили сами Уолперт и Макриди, заключается в том, что «любые два алгоритма эквивалентны, если их производительность усреднена по всем возможным задачам». ^[9] Результаты «бесплатного обеда» показывают, что сопоставление алгоритмов с задачами дает более высокую среднюю производительность, чем применение фиксированного алгоритма ко всем. ^{[ нужна ссылка ]} Игель и Туссен ^[6] и английский ^[7] установили общее условие, при котором бесплатный обед невозможен. Хотя это физически возможно, но не совсем верно. ^[6] Дросте, Янсен и Вегенер доказали теорему, которую они интерпретируют как свидетельствующую о том, что на практике «(почти) не бывает бесплатных обедов». ^[8]

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

Теоремы [ править ]

Более формально, «проблема» — это целевая функция , которая связывает варианты решения со значениями качества. Алгоритм поиска принимает на вход целевую функцию и оценивает возможные решения одно за другим. Результатом работы алгоритма является последовательность наблюдаемых значений добротности. ^[10]^[11]

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

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

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

Очевидная интерпретация фразы «не НФЛ» — это «бесплатный обед», но это заблуждение. НФЛ – это вопрос степени, а не предложения «все или ничего». Если условие НФЛ выполняется приблизительно, то все алгоритмы дают примерно одинаковые результаты по всем целевым функциям. ^[7] «Не НФЛ» подразумевает только то, что алгоритмы в целом неэквивалентны по некоторым показателям производительности. Что касается интересующего показателя производительности, алгоритмы могут оставаться эквивалентными или почти эквивалентными. ^[7]

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

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

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

Почти все целевые функции имеют настолько высокую колмогоровскую сложность , что их невозможно хранить в конкретном компьютере. ^[5]^[7]^[11] Точнее, если мы смоделируем данный физический компьютер как регистровую машину с заданным размером памяти порядка памяти современных компьютеров, то большинство целевых функций не смогут храниться в их памяти. В типичной целевой функции или алгоритме содержится больше информации, чем, по оценкам Сета Ллойда , способна зарегистрировать наблюдаемая Вселенная. ^[12] Например, если каждое возможное решение закодировано как последовательность из 300 нулей и единиц, а значения качества равны 0 и 1, то большинство целевых функций имеют колмогоровскую сложность не менее 2. ³⁰⁰ биты, ^[13] и это больше, чем граница Ллойда в 10 ⁹⁰ ≈ 2 ²⁹⁹ биты. Отсюда следует, что первоначальная теорема «без бесплатного обеда» не применима к тому, что может храниться на физическом компьютере; вместо этого необходимо применять так называемые «ужесточенные» теоремы об отсутствии бесплатных обедов. Также было показано, что результаты НФЛ применимы к невычислимым функциям. ^[14]

Формальный синопсис [ править ]

$Y^{X}$ — это набор всех целевых функций f : X → Y , где $X$ является конечным пространством решений и $Y$ является конечным частично упорядоченным множеством . Множество перестановок X — это J. всех Случайная величина F распределена на $Y^{X}$ . Для всех j в J по F o j — случайная величина, распределенная $Y^{X}$ , причем P( F o j = f ) = P( F = f o j ⁻¹) для всех f в $Y^{X}$ .

Пусть a ( f ) обозначает результат алгоритма поиска a на входе f . Если a ( F ) и b ( F ) одинаково распределены для всех алгоритмов поиска a и b , то F имеет распределение NFL . Это условие выполняется тогда и только тогда, когда F и F o j одинаково распределены для всех j в J . ^[6]^[7] Другими словами, для алгоритмов поиска не существует бесплатного обеда тогда и только тогда, когда распределение целевых функций инвариантно относительно перестановки пространства решений. ^[15] Теоретико-множественные теоремы НФЛ недавно были обобщены на случай произвольной мощности. $X$ и $Y$ . ^[16]

Происхождение [ править ]

Вулперт и Макриди приводят две основные теоремы НФЛ: первая касается целевых функций, которые не меняются во время поиска, а вторая касается целевых функций, которые могут меняться. ^[2]

Теорема 1. Для любой пары алгоритмов a ₁ и a ₂

\sum _{f}P(d_{m}^{y}|f,m,a_{1})=\sum _{f}P(d_{m}^{y}|f,m,a_{2}),

где

d_{m}^{y}

обозначает упорядоченный набор размера

m

стоимостных значений

y\in Y

связанный с входными значениями

x\in X

,

f:X\rightarrow Y

оптимизируется ли функция и

P(d_{m}^{y}|f,m,a)

— условная вероятность получения заданной последовательности значений стоимости из алгоритма

a

бегать

m

раз на функции

f

.

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

Вторая теорема устанавливает «более тонкий» результат НФЛ для изменяющихся во времени целевых функций. ^[2]

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

Традиционная, но не совсем точная интерпретация результатов НФЛ заключается в том, что «универсальная стратегия оптимизации общего назначения теоретически невозможна, и единственный способ, которым одна стратегия может превзойти другую, - это если она специализирована для конкретной рассматриваемой проблемы». ^[17] Несколько комментариев уместны:

Теоретически существует почти универсальный оптимизатор общего назначения. Каждый алгоритм поиска хорошо работает практически по всем целевым функциям. ^[11] Так что, если вас не беспокоят «относительно небольшие» различия между алгоритмами поиска, например, потому что компьютерное время стоит дешево, то вам не следует беспокоиться об отсутствии бесплатных обедов.
Алгоритм может превзойти другой при решении проблемы, если ни один из них не специализируется на этой проблеме. Действительно, возможно, что оба алгоритма являются одними из худших для решения этой задачи. В более общем плане Вулперт и Макриди разработали меру степени «согласованности» между алгоритмом и распределением задач (строго говоря, внутренним продуктом). ^[2] Сказать, что один алгоритм лучше соответствует распределению, чем другой, не означает, что какой-либо из них сознательно специализировался на этом распределении; алгоритм может иметь хорошее выравнивание просто по счастливой случайности.
На практике некоторые алгоритмы переоценивают возможные решения. Причина рассматривать производительность только кандидатов, которые никогда ранее не оценивались, состоит в том, чтобы убедиться, что при сравнении алгоритмов сравниваются яблоки с яблоками. Более того, любое превосходство алгоритма, который никогда не переоценивает кандидатов, над другим алгоритмом, который занимается конкретной проблемой, может не иметь ничего общего со специализацией на этой проблеме.
Почти для всех целевых функций специализация по существу случайна. Несжимаемые или колмогоровские случайные целевые функции не имеют регулярности для использования алгоритмом, что касается универсальной обработки Тьюринга, используемой для определения колмогоровской случайности. Итак, предположим, что существует одна, явно лучшая универсальная машина Тьюринга. Тогда, если целевая функция несжимаема для этой машины Тьюринга, нет оснований для выбора между двумя алгоритмами, если оба сжимаемы, как измерено с помощью этой машины Тьюринга. Если выбранный алгоритм работает лучше, чем большинство других, результат является случайностью. ^[11] Случайная функция Колмогорова не имеет представления меньше, чем справочная таблица, содержащая (случайное) значение, соответствующее каждой точке в пространстве поиска; любая функция, которую можно выразить более компактно, по определению не является колмогоровской случайной.

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

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

Недавно некоторые философы науки заявили, что существуют способы обойти теорему о бесплатном обеде, используя «метаиндукцию». Вулперт рассматривает эти аргументы в ^[18].

Коэволюция [ править ]

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

См. также [ править ]

Примечания [ править ]

^ Jump up to: Перейти обратно: ^а ^б Вулперт, Д.Х.; Макреди, WG (1995). «Теоремы о бесплатном обеде для поиска отсутствуют». Технический отчет СФИ-ТР-95-02-010 . Институт Санта-Фе. S2CID 12890367 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Вулперт, Д.Х.; Макриди, WG (1997). «Теоремы для оптимизации не требуют бесплатного обеда» . Транзакции IEEE в эволюционных вычислениях . 1 : 67–82. CiteSeerX 10.1.1.138.6606 . дои : 10.1109/4235.585893 . S2CID 5553697 .
^ Вулперт, Дэвид (1996). «Отсутствие априорных различий между алгоритмами обучения». Нейронные вычисления . Том. 8. стр. 1341–1390. дои : 10.1162/neco.1996.8.7.1341 . S2CID 207609360 .
^ Jump up to: Перейти обратно: ^а ^б ^с Шаффер, Каллен (1994). «Закон сохранения эффективности обобщения» (PDF) . В Виллиане, Х.; Коэн, В. (ред.). Международная конференция по машинному обучению . Сан-Франциско: Морган Кауфманн. стр. 259–265.
^ Jump up to: Перейти обратно: ^а ^б Стритер, М. (2003) « Два широких класса функций, для которых не справедлив результат отсутствия бесплатного обеда », « Генетические и эволюционные вычисления» – GECCO 2003 , стр. 1418–1430.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Игель К. и Туссен М. (2004) « Теорема об отсутствии бесплатного обеда для неравномерного распределения целевых функций », Журнал математического моделирования и алгоритмов 3 , стр. 313–322.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Инглиш, Т. (2004) No More Lunch: Анализ последовательного поиска , Труды Конгресса IEEE 2004 г. по эволюционным вычислениям , стр. 227–234.
^ Jump up to: Перейти обратно: ^а ^б ^с С. Дросте, Т. Янсен и И. Вегенер. 2002. « Оптимизация с помощью эвристики рандомизированного поиска: теорема (A) НФЛ, реалистичные сценарии и сложные функции », Theoretical Computer Science, vol. 287, нет. 1, стр. 131–144.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Вулперт, Д.Х., и Макреди, WG (2005) « Коэволюционные бесплатные обеды », IEEE Transactions on Evolutionary Computation , 9(6): 721–735.
^ Алгоритм поиска также выводит последовательность оцененных возможных решений, но этот вывод не используется в этой статье.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Английский, ТМ (2000). «Оптимизация обычной функции проста, а обучение сложно». Материалы Конгресса 2000 г. по эволюционным вычислениям. CEC00 (Кат. номер 00TH8512) . Том. 2. С. 924–931. дои : 10.1109/CEC.2000.870741 . ISBN 0-7803-6375-2 . S2CID 11295575 .
^ Ллойд, С. (2002). «Вычислительная мощность Вселенной». Письма о физических отзывах . 88 (23): 237901–237904. arXiv : Quant-ph/0110141 . Бибкод : 2002PhRvL..88w7901L . doi : 10.1103/PhysRevLett.88.237901 . ПМИД 12059399 . S2CID 6341263 .
^ Ли, М.; Витаньи, П. (1997). Введение в колмогоровскую сложность и ее приложения (2-е изд.). Нью-Йорк: Спрингер. ISBN 0-387-94868-6 .
^ Вудворд, Джон Р. (2009). «Вычислимые и невычислимые функции и алгоритмы поиска» . Международная конференция IEEE по интеллектуальным вычислениям и интеллектуальным системам, 2009 г. Том. 1. ИИЭР. стр. 871–875. CiteSeerX 10.1.1.158.7782 .
^ Часть «только если» была впервые опубликована Шумахер, CW (2000). Поиск в черном ящике: рамки и методы (кандидатская диссертация). Университет Теннесси, Ноксвилл. ПроКвест 304620040 .
^ Роу; Восе; Райт (2009). «Переосмысление отсутствия бесплатных обедов» . Эволюционные вычисления . 17 (1): 117–129. дои : 10.1162/evco.2009.17.1.117 . ПМИД 19207090 . S2CID 6251842 .
^ Хо, ЮК; Пепин, Д.Л. (2002). «Простое объяснение теоремы об отсутствии бесплатных обедов и ее последствий». Журнал теории оптимизации и приложений . 115 (3): 549–570. дои : 10.1023/A:1021251113462 . S2CID 123041865 .
^ Вулперт, Д.Х. (2023). «Следствие теорем об отсутствии бесплатного обеда для метаиндукции» . Журнал общей философии науки . 1 : 67–82. дои : 10.1109/4235.585893 . S2CID 5553697 .

Внешние ссылки [ править ]

[WM95-1] Jump up to: Перейти обратно: ^а ^б Вулперт, Д.Х.; Макреди, WG (1995). «Теоремы о бесплатном обеде для поиска отсутствуют». Технический отчет СФИ-ТР-95-02-010 . Институт Санта-Фе. S2CID 12890367 .

[WM97-2] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Вулперт, Д.Х.; Макриди, WG (1997). «Теоремы для оптимизации не требуют бесплатного обеда» . Транзакции IEEE в эволюционных вычислениях . 1 : 67–82. CiteSeerX 10.1.1.138.6606 . дои : 10.1109/4235.585893 . S2CID 5553697 .

[Wolpert96-3] Вулперт, Дэвид (1996). «Отсутствие априорных различий между алгоритмами обучения». Нейронные вычисления . Том. 8. стр. 1341–1390. дои : 10.1162/neco.1996.8.7.1341 . S2CID 207609360 .

[Schaffer94-4] Jump up to: Перейти обратно: ^а ^б ^с Шаффер, Каллен (1994). «Закон сохранения эффективности обобщения» (PDF) . В Виллиане, Х.; Коэн, В. (ред.). Международная конференция по машинному обучению . Сан-Франциско: Морган Кауфманн. стр. 259–265.

[Streeter-5] Jump up to: Перейти обратно: ^а ^б Стритер, М. (2003) « Два широких класса функций, для которых не справедлив результат отсутствия бесплатного обеда », « Генетические и эволюционные вычисления» – GECCO 2003 , стр. 1418–1430.

[Igel-6] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Игель К. и Туссен М. (2004) « Теорема об отсутствии бесплатного обеда для неравномерного распределения целевых функций », Журнал математического моделирования и алгоритмов 3 , стр. 313–322.

[English2004-7] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Инглиш, Т. (2004) No More Lunch: Анализ последовательного поиска , Труды Конгресса IEEE 2004 г. по эволюционным вычислениям , стр. 227–234.

[ANFL-8] Jump up to: Перейти обратно: ^а ^б ^с С. Дросте, Т. Янсен и И. Вегенер. 2002. « Оптимизация с помощью эвристики рандомизированного поиска: теорема (A) НФЛ, реалистичные сценарии и сложные функции », Theoretical Computer Science, vol. 287, нет. 1, стр. 131–144.

[WM-coev-9] Jump up to: Перейти обратно: ^а ^б ^с ^д Вулперт, Д.Х., и Макреди, WG (2005) « Коэволюционные бесплатные обеды », IEEE Transactions on Evolutionary Computation , 9(6): 721–735.

[10] Алгоритм поиска также выводит последовательность оцененных возможных решений, но этот вывод не используется в этой статье.

[English2000-11] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Английский, ТМ (2000). «Оптимизация обычной функции проста, а обучение сложно». Материалы Конгресса 2000 г. по эволюционным вычислениям. CEC00 (Кат. номер 00TH8512) . Том. 2. С. 924–931. дои : 10.1109/CEC.2000.870741 . ISBN 0-7803-6375-2 . S2CID 11295575 .

[Lloyd2002-12] Ллойд, С. (2002). «Вычислительная мощность Вселенной». Письма о физических отзывах . 88 (23): 237901–237904. arXiv : Quant-ph/0110141 . Бибкод : 2002PhRvL..88w7901L . doi : 10.1103/PhysRevLett.88.237901 . ПМИД 12059399 . S2CID 6341263 .

[LV-13] Ли, М.; Витаньи, П. (1997). Введение в колмогоровскую сложность и ее приложения (2-е изд.). Нью-Йорк: Спрингер. ISBN 0-387-94868-6 .

[14] Вудворд, Джон Р. (2009). «Вычислимые и невычислимые функции и алгоритмы поиска» . Международная конференция IEEE по интеллектуальным вычислениям и интеллектуальным системам, 2009 г. Том. 1. ИИЭР. стр. 871–875. CiteSeerX 10.1.1.158.7782 .

[15] Часть «только если» была впервые опубликована Шумахер, CW (2000). Поиск в черном ящике: рамки и методы (кандидатская диссертация). Университет Теннесси, Ноксвилл. ПроКвест 304620040 .

[Rowe-16] Роу; Восе; Райт (2009). «Переосмысление отсутствия бесплатных обедов» . Эволюционные вычисления . 17 (1): 117–129. дои : 10.1162/evco.2009.17.1.117 . ПМИД 19207090 . S2CID 6251842 .

[17] Хо, ЮК; Пепин, Д.Л. (2002). «Простое объяснение теоремы об отсутствии бесплатных обедов и ее последствий». Журнал теории оптимизации и приложений . 115 (3): 549–570. дои : 10.1023/A:1021251113462 . S2CID 123041865 .

[WOLP23-18] Вулперт, Д.Х. (2023). «Следствие теорем об отсутствии бесплатного обеда для метаиндукции» . Журнал общей философии науки . 1 : 67–82. дои : 10.1109/4235.585893 . S2CID 5553697 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]