Теорема об отсутствии свободного обеда и согласованность K-NN

10

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

Предполагать μ имеет плотность. если К а также К/N0 тогда для каждого ε>0, есть N, улица для всех N>N:п(рN-р*>ε)<2еИксп(-СdNε2)
р*ошибка оптимального байесовского правила, - истинная ошибка вывода K-NN (вероятность превышает обучающий набор размера ), - мера вероятности в пространстве экземпляра и - некоторая постоянная, зависит только от евклидовой размерности. Следовательно, мы можем максимально приблизиться к наилучшей гипотезе (не лучшей в некотором ограниченном классе), не делая никаких предположений о распределении. Поэтому я пытаюсь понять, как этот результат не противоречит теореме НФЛ? Спасибо!рNNμрdСd

Майкл Дж
источник

Ответы:

6

Насколько я понимаю, теорема о НФЛ заключается в том, что в каждой задаче нет алгоритма обучения, который лучше, чем остальные. Это, однако, не теорема в ясном математическом смысле, что она имеет доказательство, а скорее эмпирическое наблюдение.

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

Теперь, как это не сломать НФЛ? В основном это говорит о том, что вы можете решить любую мыслимую проблему с помощью простого двухслойного NN. Причина в том, что хотя теоретически NN могут приближаться к чему угодно, на практике их очень трудно научить приближать что угодно. Вот почему для некоторых задач предпочтительнее использовать другие алгоритмы.

Более практичный способ интерпретации НФЛ заключается в следующем:

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

CaucM
источник
3
Спасибо за ответ, но есть некоторые неточности. Во-первых, теорема НФЛ имеет доказательство (например, Шалев-Шварц и Бен-Давид, понимание машинного обучения, глава 5). Для теоремы универсального приближения - эта теорема имеет дело с выразительностью, в то время как теорема НФЛ имеет дело с обобщением.
Майкл Дж