Понимание отсутствия теоремы о бесплатном обеде в Duda et al.

У меня есть несколько вопросов по поводу обозначений, использованных в Разделе 9.2. Отсутствие врожденного превосходства любого классификатора в классификации образцов Дуды, Харта и Аиста . Сначала позвольте мне процитировать некоторый соответствующий текст из книги:

• Для простоты рассмотрим задачу с двумя категориями, где обучающий набор состоит из шаблонов и соответствующих меток категорий для сгенерированных неизвестной целевой функцией, подлежащей изучению, , где .$D$$x^i$$y_i = ± 1$$i = 1,..., n$$F(x)$$y_i = F(x^i)$
• Пусть обозначает (дискретный) набор гипотез или возможные наборы параметров, которые необходимо изучить. Конкретная гипотеза может быть описана квантованными весами в нейронной сети, или параметрами 0 в функциональной модели, или наборами решений в дереве, и так далее.$H$$h(x) \in H$
• Кроме того, - априорная вероятность того, что алгоритм выведет гипотезу после обучения; обратите внимание, что это не вероятность того, что является правильным.$P(h)$$h$$h$
• Далее, обозначает вероятность того, что алгоритм позволит получить гипотезу , когда на подготовку данных . В детерминированных алгоритмах обучения, таких как деревья ближайшего соседа и деревья решений, будет везде нулевым, за исключением одной гипотезы . Для стохастических методов (таких как нейронные сети, обученные по случайным начальным весам) или стохастического обучения Больцмана, может быть широким распределением.$P(h|D)$$h$$D$$P(h|D)$$h$$P(h|D)$
• Пусть будет ошибкой для нулевой или другой функции потерь.$E$

Ожидаемая ошибка классификации вне тренировочного набора, когда истинная функция равна а вероятность алгоритма обучения го кандидата равна , определяется какк Р к ( ч ( х ) | Д ) Е к ( Е | Р , п ) = Σ х ∉ Д Р ( х ) [ 1 - δ ( Р ( х ) , ч ( х ) ) ] Р k ( h ( x ) | D $F(x)$$k$$P_k(h(x)|D)$

$$\mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D)$$

Теорема 9.1. (Без бесплатного обеда) Для любых двух алгоритмов обучения и справедливо следующее, независимо от распределения выборки и количества тренировочных точек:P 2 ( h | D ) P ( x ) $P_1 (h |D)$$P_2(h|D)$$P(x)$$n$

1. Равномерно усреднено по всем целевым функциям ,E 1 ( E | F , n ) - E 2 ( E | F , n ) = $F$$\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n) = 0$

2. Для любого фиксированного обучающего набора , равномерно усредненного по , $D$$F$$\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D) = 0$

Часть 1 на самом деле говорит

$$\sum_F \sum_D P(D|F) [\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n)] = 0$$

Часть 2 на самом деле говорит

$$\sum_F [\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D)] = 0$$

Мои вопросы

1. В формуле , то есть можно ли заменить на и переместить его за пределы суммы , потому что это действительно распределение по заданное для го алгоритма стохастического обучения?$\mathcal{E}_k(E|F,n)$ $$\mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D),$$ $P_k(h(x)|D)$$P_k(h|D)$$\sum_{x \notin D}$$h$$H$$D$$k$
2. Учитывая, что алгоритм обучения го кандидата является стохастическим методом, почему в формуле нет суммы по , т.е. ?$k$$\mathcal{E}_k(E|F,n)$$h$$\sum_{h \in H}$

3. Чем и отличаются друг от друга?$\mathcal{E}_i (E|F, D)$$\mathcal{E}_i (E|F, n)$

   Означает ли частоту ошибок при обучении с учетом обучающего набора ?$\mathcal{E}_i (E|F, D)$$D$

   Означает ли частоту появления ошибок при обучении, усредненную по всему обучающему набору с учетом размера обучения ? Если да, почему часть 1 в теореме НФЛ усредняет по обучающим наборам снова, записывая , и почему в формуле для не существует среднего значения по всему тренировочному набору, учитывая размер обучения ?$\mathcal{E}_i (E|F, n)$$n$$\mathcal{E}_i (E|F, n)$$\sum_D$$\mathcal{E}_k(E|F,n)$$n$

4. В части 1 теоремы НФЛ означает ли суммирование по всем тренировочным наборам с фиксированным размером обучения ?$\sum_D$$n$
5. Если дальнейшее суммирование по всем возможным значениям в обучающего размера в части 1, результат по-прежнему равен 0, верно?$\mathbb{N}$$n$
6. В формуле , если я изменю на , т. не обязательно ограничен вне обучающего набора, обе части Теорема НФЛ все еще будет правдой?$\mathcal{E}_k(E|F,n)$$\sum_{x \notin D}$$\sum_x$$x$
7. Если истинное соотношение между и не предполагается как детерминированная функция при , а вместо этого - условное распределение или совместное распределение которое эквивалентно зная и (см. также мой другой вопрос ), я могу изменить на (со странным указано в части 1 и 2). Две части в теореме НФЛ все еще верны?$x$$y$$F$$y=F(x)$$P(y|x)$$P(x,y)$$P(y|x)$$P(x)$$\mathcal{E}_k (E|F,n)$ $$\mathcal{E}_k(E|P(x,y),n) = \mathcal{E}_{x,y} [1-\delta(y, h(x))] P_k(h(x)|D)$$ $P_k(h(x)|D)$

Спасибо и всего наилучшего!

Я отвечу на вопросы, на которые, я думаю, я знаю ответы.

1. Этот ответ отрицательный, потому что вы выбираете который не был частью набора подгонки и поэтому зависит от .$x$$D$$h$$x$
2. $h$ оценивается только по значениям в тестовом наборе для получения ожидаемой частоты ошибок, поэтому он оценивается не по всему набору а только по дискретному набору в тестовом наборе.$x$$H$$x$
3. $\mathcal{E}_i(E|F, D)$ является ожидаемым от частоты ошибок обучения набора заданной функции и обучающее множество . Но я думаю, отличается, потому что вы только обусловливаете количество тренировочных точек а не фактические значения . Но это озадачивает, учитывая последующие заявления.$F$$D$$\mathcal{E}_i(E|F, n)$$n$$x$
4. $D$ - набор обучающих векторов. В есть обучающих векторов . Таким образом , вы суммирование по фиксированному обучения векторов в . Существует только один набор .$n$$D$$n$$D$$D$
5. Я думаю, что ответ на 5 - нет. Запись кажется немного запутанной.

Не могу комментировать 6 и 7.