Дерево решений принимает в качестве входных данных объект или ситуацию, описанную с помощью множества атрибутов, и возвращает "решение" — предсказанное выходное значение, соответствующее входным данным. Входные атрибуты могут быть дискретными или непрерывными. На данный момент подразумевается, что входные данные являются дискретными. Выходные значения также могут быть дискретными или непрерывными; процесс формирования в ходе обучения функции с дискретными значениями называется обучением классификации; формирование в ходе обучения непрерывной функции называется обучением регрессии. Вначале мы сосредоточимся на булевой классификации, согласно которой каждый пример обозначается как истинный ( положительный) или ложный ( отрицательный).

Дерево решений позволяет перейти к содержащемуся в нем решению путем выполнения последовательности проверок. Каждый внутренний узел в дереве соответствует проверке значения одного из свойств, а ветви, исходящие из этого узла, обозначены возможными значениями результатов проверки. Каждый листовой узел в дереве задает значение, возвращаемое после достижения этого листа. По-видимому, представление в виде дерева решений кажется людям вполне естественным; в действительности многие инструктивные руководства (например, по ремонту автомобилей) полностью оформлены в виде одного дерева решений, разбросанного по нескольким сотням страниц.

Несколько более простой пример может быть основан на применении методов обучения к задаче, в которой клиент ждет, пока освободится место за столиком в ресторане. Цель состоит в том, чтобы изучить определение для целевого предиката WillWait (Следует ли ждать). Подготавливая данный пример для использования в качестве задачи обучения, необходимо вначале определить, какие атрибуты доступны для описания примеров ситуаций в данной проблемной области. В главе 19 будет показано, как автоматизировать выполнение этого этапа, а на данный момент предположим, что решено использовать приведенный ниже список атрибутов.