Компьютер загадал одного из 24 персонажей. Задавайте вопросы с ответом «да/нет», отсекайте лишних — и следите, как из ваших вопросов вырастает дерево решений. Чем лучше вопрос делит оставшихся пополам, тем меньше вопросов понадобится.
Жадный алгоритм на каждом шаге задаёт вопрос с наибольшим приростом информации для оставшихся персонажей — так же строятся деревья ID3 и C4.5. Нажмите на лист, чтобы подсветить путь к нему.
Пока мы не знаем, кто загадан, все 24 персонажа равновероятны. Неопределённость измеряют энтропией: для n равновероятных вариантов это log2 n бит. Для 24 персонажей — 4,58 бит: столько «идеальных» вопросов нужно, чтобы наверняка назвать ответ.
Вопрос делит оставшихся на две группы: k ответят «да», n − k — «нет». После ответа мы окажемся в одной из групп, и ожидаемая неопределённость равна взвешенному среднему их энтропий. Разница с исходной энтропией — прирост информации:
Максимум — ровно 1 бит — достигается, когда вопрос делит группу пополам. Вопрос, на который все ответят одинаково, даёт 0 бит: он бесполезен. Именно по этому правилу дерево решений выбирает признак в каждом узле: включите «Показывать прирост информации» в игре, и лучший вопрос будет подсвечен.
Дерево, построенное жадно, не обязано быть самым коротким из всех возможных, но на практике оно близко к оптимуму: здесь глубина 5 при теоретическом минимуме ⌈log2 24⌉ = 5. В машинном обучении всё то же самое, только «персонажи» — это объекты выборки, «вопросы» — признаки, а листья дерева — классы.