Семинар «Построение рандомизированных ансамблей деревьев решений с использованием ядерных разделителей»
17 июня в 16:30 по московскому времени
В процессе анализа текстов, изображений, структурированных данных зачастую необходимо решать задачи моделирования дискретных процессов. Наилучшей точности решения этой задачи можно было бы достигнуть при применении моделей с дискретными зависимыми переменными. Случайные леса деревьев решений (Random Forests) являются разновидностью подобных моделей, используемой для решения задач классификации и регресии. В основе Random Forest лежат деревья решений с одномерными разделителями, для построения которых используются алгоритмы CART, C4.5, или ID3. Случайные леса показывают высокую точность в некоторых задачах анализа данных и текстов, однако их выразительная способность ограничена, что снижает применимость при обработке данных высокой размерности. Этого недостатка лишены деревья решений с многомерными (линейными и нелинейными) разделителями; однако большинство существующих подходов к обучению таких деревьев имеют низкую вычислительную эффективность и не позволяют использовать произвольные критерии однородности данных (Gini impurity, информационная энтропия) при построении узлов деревьев. Кроме того, при обучении лесов подобных деревьев на небольших наборах данных негативное влияние оказывают эффекты, связанные с переобучением. Поэтому необходимо выявить механизмы регуляризации, позволяющие найти компромисс между сложностью получаемых моделей и их обобщающей способностью.
В работе предложен алгоритм для построения случайных лесов деревьев решений с ядерными разделителями (линейными, полиномиальными, Гауссовскими). Построение этих разделителей осуществляется методом выпуклой оптимизации с ограничеиями-неравенствами. Следовательно, при построении разделителей могут быть использованы вычислительно-эффективные алгоритмы, реализованные в библиотеках LibSVM, Liblinear и ThunderSVM. Сформированы также теоретические основы для подбора методов регуляризации случайных лесов: разработаны методы оценки обобщающей способности рандомизированных ансамблей деревьев решений.
В ходе работы проведены экспериментальные исследования разработанных методов на нескольких задачах классификации: изучение реакции пользователей социальных сетей, распознавание изображений и банковский скоринг. Результаты исследований показывают, что регуляризованные случайные леса с ядерными разделителями превосходят по точности и полноте классификации случайные леса деревьев решений, а также леса деревьев с линейными разделителями, построенные другими методами.
Докладчик
Девяткин Дмитрий Алексеевич, научный сотрудник ФИЦ ИУ РАН.