В вычислительном обучении теорема НФЛ утверждает, что универсального ученика не существует. Для каждого алгоритма обучения существует распределение, которое приводит к тому, что учащийся выдает гипотезу с большой ошибкой и высокой вероятностью (хотя гипотеза с низкой ошибкой существует). Вывод заключается в том, что для обучения класс гипотезы или ее распределение должны быть ограничены. В своей книге «Вероятностная теория распознавания образов» Деврой и его коллеги доказывают следующую теорему для ученика с K-ближайшими соседями:
гдеПредположим, что µ имеет плотность. если к →∞ и k / n → 0 то для любого е > 0 , существует N, Ул для всех п > Н:п( RN- R*> ϵ ) < 2 e x p ( - CdN ϵ2)
р*ошибка оптимального байесовского правила, - истинная ошибка вывода K-NN (вероятность превышает обучающий набор размера ), - мера вероятности в пространстве экземпляра и - некоторая постоянная, зависит только от евклидовой размерности. Следовательно, мы можем максимально приблизиться к наилучшей гипотезе (не лучшей в некотором ограниченном классе), не делая никаких предположений о распределении. Поэтому я пытаюсь понять, как этот результат не противоречит теореме НФЛ? Спасибо!рNNμрdСd