Сокращение сложности затрат: ошибка сокращения

Question

Кто-нибудь может объяснить это два утверждения:

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

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

Первое утверждение верно, а второе неверно.

Answer 1

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

Верно: ошибка сокращенного дерева никогда не может быть меньше, чем исходное дерево в наборе обучающих данных.

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

False: ошибка сокращенного дерева никогда не может быть меньше, чем исходное дерево в наборе данных проверки.

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

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