Я. Гудфеллоу, И. Бенджио, А. Курвилль

решающее 
дерево
(Breiman et al., 1984) и его многочисленные варианты. На рис. 5.7 показано, 
что с каждым узлом решающего дерева ассоциирована область пространства входов, 
и внутренние узлы разбивают эту область на две части – по одной для каждого дочер-
него узла (обычно рассекая параллельно оси). Таким образом, пространство входов 
делится на непересекающиеся области, взаимно однозначно соответствующие лис-
товым узлам. Обычно каждый листовый узел сопоставляет каждой входной точке 
в своей области один и тот же выход. Для обучения решающих деревьев применяются 
специальные алгоритмы, выходящие за рамки этой книги. Алгоритм обучения можно 
Рис. 5.7 

Описание работы решающего дерева. (
Вверху
) Каждый узел 
дерева выбирает, кому отправить входной пример: левому потомку (0) или 
правому (1). Внутренние узлы изображены кружочками, листовые – квад-
ратиками. Каждый узел обозначается строкой нулей и единиц, описываю-
щей его позицию в дереве. Строка получается дописыванием одного 
разряда к идентификатору родительского узла (0 – слева от родителя, 1 – 
справа от родителя). (
Внизу
) Дерево разбивает пространство на области. 
На рисунке приведен пример разбиения плоскости 
ℝ
2
. На этой плоскости 
нарисованы узлы дерева, через каждый внутренний узел проходит разде-
лительная линия, показывающая, как он классифицирует примеры, а лис-
товые узлы находятся в центре множества попадающих в них примеров. 
В результате получается кусочно-постоянная функция, сопоставляющая 
свой «кусок» каждому листовому узлу. В каждом листовом узле должен на-
ходиться хотя бы один пример, так что решающее дерево не может обучить 
функцию, имеющую больше локальных максимумов, чем число обучающих 
примеров.

---

Алгоритмы обучения с учителем 
