Какова вероятность правильного ответа при разных стратегиях выбора класса в листе дерева и как это вычислить для произвольных вероятностей

Что проверяют

Умеете ли вы перейти от интуиции «берём самый частый класс» к формуле и доказать, что это лучшая стратегия. Хороший ответ сам выходит на критерий Джини, а следом интервьюер обычно спрашивает, как посчитать точность всего дерева.

Как отвечать

Пусть в листе доли классов p_1, ..., p_k, и новый объект из этого листа принадлежит классу i с вероятностью p_i. Если стратегия выбирает класс i с вероятностью q_i, то вероятность угадать равна сумме q_i * p_i по всем классам. Отсюда все частные случаи:

• самый частый класс (так работает predict в DecisionTreeClassifier): вся вероятность выбора на классе с наибольшей долей, получается max(p_i);
• случайный класс по распределению листа: q_i = p_i, получается сумма квадратов p_i. Ошибка такой стратегии равна 1 - sum(p_i^2), это ровно индекс Джини;
• равновероятный класс: 1/k независимо от распределения.

Пример для долей 0.6, 0.3 и 0.1: самый частый класс даёт 0.6, случайный по распределению 0.36 + 0.09 + 0.01 = 0.46, равновероятный 0.33.

Почему выбор самого частого класса оптимален: вероятность угадать линейна по q, а максимум линейной функции на симплексе достигается в вершине, то есть при выборе одного класса с наибольшим p_i. Сумма квадратов никогда не больше максимума, потому что каждый p_i^2 не больше p_i * max(p).

Для всего дерева усредните по листьям с весами, равными доле объектов, попадающих в каждый лист. Оговорите, что p_i в листе это оценка по обучающей выборке: в маленьких листьях она шумная, поэтому ограничивают min_samples_leaf или сглаживают частоты.

Где спотыкаются

Для пороговой стратегии пишут, что при непрохождении порога вероятность угадать равна нулю. Но если выбран другой класс, стратегия угадывает с его вероятностью.

Не видят связи с Джини и пересказывают формулы по отдельности, хотя именно эту связь обычно и ждут.

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