Вопрос или проблема
Я использую случайные леса, и в моих данных существует много ситуаций, когда $X_1$ является плохим предиктором, $X_2$ является плохим предиктором, но совместное распределение может быть хорошим предиктором.
Предположим, что $X1$, $X2$ и $Y$ — это бинарные переменные. У нас есть $P(X_1|Y)=0.5$ и $P(X_2|Y=y)=0.5$ для любых $X_1,X_2,Y\in\{0,1\}$, но $P(X_1=1,X_2=1|Y=1)=1$.
Практический пример: я хочу предсказать, совпадают ли text1 и text2. Я добавил в качестве признака разность-в-использовании-!. Но разность-в-использовании-! может равняться нулю в двух очень разных случаях: когда ни один текст не содержит !, или когда оба используют ! в одинаковом количестве. Поэтому я добавил еще один признак: оба-текста-используют-!.
Проблема теперь заключается в том, что дерево решений должно быть ориентировано в будущее, потому что текст действительно совпадает только если разность-в-использовании-! очень мала и оба-текста-используют-! равняется 1.
Теперь, вероятно, я мог бы и должен объединить эти два признака в один более умный признак (всегда приветствуются предложения). Но у меня много таких признаков, и я задаюсь вопросом, являются ли деревья решений в моем случайном лесу, которые обучаются с использованием традиционного локального поиска, субоптимальными по сравнению с поиском с заглядыванием вперед.
Я прочитал в этой диссертации, что,
Как эмпирически исследовано в [Murthy and Salzberg, 1995], такой подход (использующий поиск с заглядыванием вперед) не только более вычислительно затратный, но и не значительно лучше, чем жадно построенные деревья решений.
Комментарий в скобках добавлен мной. Работа цитируется как другая диссертация, и она действительно говорит, что, например,
Контр-интуитивный результат о том, что поиск с заглядыванием вперед не улучшает жадный поиск, может показаться разумным, если последний сам строит близкие к оптимальным деревья.
Обе работы устарели, и, судя по тому, что я прочитал, они не углубляются в это (но я не читал их полностью). Мне интересно, знает ли кто-нибудь, существуют ли признаки, для которых будет работать только какой-то поиск с заглядыванием вперед, или же обычный локальный поиск подходит даже для этих случаев, и любые мысли о локальном пояске против поиска с заглядыванием вперед.
Не существует общепринятой реализации дерева решений с поиском с заглядыванием вперед; все общепринятые реализации используют жадный поиск по признакам.
Используя жадный поиск по признакам, дерево решений может изучать условные зависимости. Например, дерево решений может выявлять описанные вами шаблоны. Первый разбиение будет либо 𝑃(𝑋₁|𝑌)=0.5, 𝑃(𝑋₂|𝑌=𝑦)=0.5, затем дополнительные разбиения определят 𝑃(𝑋₁=1,𝑋₂=1|𝑌=1)=1. Это похоже на задачу XOR, которую могут изучить деревья решений.
Ответ или решение
Рассмотрим важность поиска с предвосхищением в контексте построения деревьев решений, особенно в свете вашего примера с использованием случайных лесов.
Зачем нужен поиск с предвосхищением?
Поиск с предвосхищением в деревьях решений может показаться привлекательным, когда речь идет об обучении на данных, где простые характеристики не способны эффективно захватывать сложные взаимосвязи. Ваша ситуация, где $X_1$ и $X_2$ по отдельности являются плохими предикторами, но в их совместном распределении содержит важную информацию, подчеркивает эту необходимость.
Вы упомянули, что даже при использовании обычного жадного поиска (feature-by-feature greedy search) дерево решений может извлекать некоторые зависимости. Этот подход основан на локальных решениях, которые зачастую достаточно хороши, чтобы построить деревья, адекватно отражающие данные. Например, жадный алгоритм может сначала разделить данные по одному из предикторов, а затем последующим разделением охватить совместное влияние обоих предикторов.
Однако, когда корреляции между признаками чрезвычайно важны для модели, как в вашем случае, где существует зависимость между $X_1$ и $X_2$, поиск с предвосхищением позволяет более глубоко оценить влияние следующего разбиения, что потенциально может привести к более оптимальным решениям.
Практическая реализация
Существует множество реализаций алгоритмов деревьев решений, которые используют жадный алгоритм, поскольку он более эффективен. Но ни одна из широко используемых библиотек (например, scikit-learn) не включает реализацию поиска с предвосхищением, в основном из-за его вычислительной сложности.
Обоснование жадного подхода
Исследования, такие как упомянутое вами исследование Мёрти и Зальцберга, показывают, что жадные методы, как правило, построят деревья, которые достаточно близки к оптимальным даже в сложных случаях, таких как ваша задача. Некоторые из контр-интуитивных результатов показывают, что результативность жадного метода может не уступать более сложному анализу с предвосхищением, если концентрация на простоте данных явным образом достаточна для задачи.
Рекомендации
-
Присоединение признаков: Возможно, наиболее эффективным решением вашей проблемы будет создание комбинации признаков, как вы уже упомянули. Создание нового признака, который одновременно учитывает $X_1$ и $X_2$, может позволить вашему дереву лучше различать случаи, когда текст один и тот же.
-
Углублённый анализ: Если ваши данные имеют сложные зависимости, возможно, стоит рассмотреть более сложные подходы машинного обучения, такие как градиентный бустинг или ансамбли моделирования, которые могут более эффективно справиться с многомерными зависимостями.
-
Исследование альтернативных методов: Кроме использования смешанных признаков, вы могли бы рассмотреть возможность интеграции нелинейных моделей, таких как нейронные сети или методы, использующие регуляризацию, которые могут лучше справляться с такими взаимодействиями.
В заключение, хотя поиск с предвосхищением может оказаться полезным в определённых условиях, жадные алгоритмы, как правило, достаточны для большинства задач построения деревьев решений. Исследуйте возможность объединения признаков для улучшения модели, а также подумайте над применением методов, оптимизированных для выявления сложных взаимосвязей.