Спикер о работе:
«В этом семинаре, я представлю новый алгоритм для обучения деревьев решений и моделей на их основе — Tree Alternating Optimization (TAO); Несмотря на свою простоту, алгоритм показал высокую эффективность в ряде задач. В частности, мы продемонстрировали, что обыкновенный ансамбль деревьев (Random Forests), где каждое дерево обучается алгоритмом TAO, превосходит state-of-the-art методы на основе деревьев (например, XGBoost). Более того, алгоритм легко обобщается для обучения более сложных деревообразных структур, например, гибридов деревьев решений и нейронных сетей.»
Запись: https://youtu.be/sN0MDfZifes
Презентация: https://drive.google.com/file/d/1Jr5EEWwTyGLNA1owrVodMXJmut-RAGhs/view?usp=share_link
(00:00:00) (Начало записи.)
Николай Михайловский: Добрый день. Я Николай Михайловский. Я приветствую всех на очередном научно-техническом вебинаре, который НТР проводит вместе с Высшей IT-школой Томского университета. У нас сегодня Арман Жармагамбетов, University of California, Merced, прямо рядом с _____ (00:00:22). Я передаю слово Арману Жармагамбетову, который нам расскажет про обучение древесных моделей. Или, как правильно по-русски сказать, моделей, основанных на деревьях.
Арман Жармагамбетов: Да. Спасибо большое. Во-первых, хотел бы поблагодарить за приглашение и предоставленную возможность рассказать про нашу работу. Также хотел бы поблагодарить Руфину за решение организационных вопросов.
Меня зовут Арман, я родом из Казахстана, на данный момент являются PhD студентом в калифорнийском университете Merced, факультет компьютерных наук. Сегодня я расскажу про деревья решений и про наш альтернативный метод по их обучению, а также по обучению гибридных моделей на основе деревьев решений. Это основная тема моей диссертации, над которой я работаю совместно с моим руководителем Мигель Анхель Каррейра-Перпинья [Miguel Á. Carreira-Perpiñán] также с калифорнийского университета Merced.
Хотелось отметить: что нового можно придумать в новом направлении «деревья решений»? казалось бы, классический алгоритм, ничего особого тут не придумаешь. Но, как оказалось, тут есть еще нераспаханное поле, и люди трудятся над оптимизацией всяких алгоритмов, по их ускорению, а также по изучению каких-либо новых методов по их обучению.
Немного про содержание. Я сначала смотивирую, можно сказать, нашу работу, а также постараюсь провести краткий обзор по деревьям решений для тех, кто, может быть, подзабыл или не знает. Совсем быстро. И сразу же продолжу рассказ про наш алгоритм, который мы называли TAO сокращенно от tree alternating optimization, то есть который мы можем применить для обучения деревьев решений и всяких моделей на их основе. Здесь я расскажу про математическую формулировку, и как решается эта оптимизационная задача, и так далее.
И дальше уже прикладные направления, то есть как мы можем обучить, то есть одно дерево или же ансамбль деревьев, с помощью TAO. Для начала рассмотрим для задач классификации и регрессии. И, скорее всего, закончу другим прикладным направлением – как мы можем применить наш алгоритм TAO для обучения гибридов деревьев решений и нейронных сетей. Такие гибриды в наше время становятся популярными. Скорее всего, это в виду популярности нейронных сетей.
Немного про мотивацию. Несмотря на популярность deep learning, нейронных сетей, деревья решений до сих пор являются одними из наиболее популярных алгоритмов и методов машинного обучения. Согласно анкетирования от kdnuggets, популярного сайта по дата-майнингу, машинному обучению, где есть всякие туториалы, форумы и так далее, так вот по их анкетированию методы на основе деревьев решений всегда стоят на топ-местах. Вот, допустим, хоть и с прошлого года, но не думаю, что что-либо кардинально поменялось в этом году, анкетирование в прошлом году выявило, что, допустим, логистические линейные регрессии, кто использует деревья решений, и Random Forests, которые тоже используют ансамбль деревьев решений.
На третьем месте здесь стоит gradient boosting machines (XGBoost), но все мы знаем, что под капотом XGBoost и другие библиотеки используют деревья решений как base learner, поэтому мы как-то можем совместить, скорее всего, эти два пункта, и получится так, что методы на основе деревьев решений – на топе по используемости.
(00:05:50)
Также в литературе, в научном мире очень много всяких review paper по поводу прикладных назначений деревьев решений, а также всякие теоретические аспекты деревьев решения, как и в машинном обучении, так и в статистике. То есть все эти ссылки появятся в конце слайда, и вы сможете увидеть.
Сначала поговорим, что такое деревья решения. Формально говоря, если использовать определения, которые даются в книжках – здесь я немного упростил, – деревья решений – это иерархические модели, которые разделяют пространство признаков на некие локальные регионы. И используют одну и ту же предиктивную функцию для всех точек, которые попадают в этот регион. То есть наше дерево разделяет это пространство признаков на некие локальные регионы.
Давайте рассмотрим, как он это делает. Здесь представлены некие гипотетические деревья решений.
Традиционно мы разделяем на два типа нодов, то есть узлы деревьев решений. Это внутренние узлы (internal nodes), и terminal nodes, которые чаще всего называются leaves (листья). И основная задача этих внутренних узлов – направить наш input в определенный leaf node.
Допустим, рассмотрим этот путь от корня (самый первый внутренний узел называется «корень») до листьев. В этом внутреннем узле мы проверяем: первый _____ (00:08:03) если больше, чем определенное число, то мы идем налево. И рекурсивно применяем эти функции на каждом узле до тех пор, пока мы ни встретили наш определенный листик (leaf node).
Как только мы находим этот листик, то применяем нашу предиктивную функцию. В данном случае это константа. То есть, что бы сюда ни попало, мы тупо возвращаем значение 0,6. Это для задачи регрессии.
Как оно разделяет? На первом разделении, где у нас корень, мы отправляем все наши точки, которые больше, чем 38,5 (первый атрибут), налево. По сути, мы избавляемся от всего этого полупространства, и фокусируемся на этом полупространстве.
На следующем делении он смотрит на второй атрибут, на второй признак, и говорит, что если это больше, чем 2,5, то мы идем наверх, а иначе идем вниз. То есть мы, опять-таки, избавляемся от этого пространства и фокусируемся на этом полупространстве.
И если мы объединяем с предыдущим решением – то есть это первое разбиение, второе разбиение, – то у нас появляется этот локальный регион. То есть эта граница, она здесь лишняя (здесь ее не должно быть, здесь, по сути, не ограничена в эту сторону, так же, как и здесь вниз). То есть весь этот регион, неважно, какая точка попадет сюда или сюда, наша предиктивная функция будет предсказывать данное значение. Или это, допустим, класс 1, 10, кошка или собака (зависит от задачи).
Вот деревья решений. Если нам дерево решений дается, конечно же.
(00:10:33)
Что такое обучение деревьев решений? Это, по сути, нахождение этих параметров: почему здесь должно стоять 38,5, почему здесь должно стоять 2,5 или 0,6, и так далее. То есть мы должны найти эти параметры. Также мы должны найти структуру этого дерева. Также мы должны найти, почему корень должен смотреть на первый атрибут, почему следующий узел должен смотреть на второй атрибут, и так далее.
То есть нахождение всех этих параметров является процессом обучения деревьев решений. Но как только оно обучено, мы применяем его таким образом.
Описанная модель, без всяких сомнений, является нелинейной. И очень много преимуществ у деревьев решений. Первое, наиболее популярное, почему люди чаще всего пользуются деревьями решений – это их интерпретируемость. То есть этот путь от корня до листьев можно описать в виде логических определений.
Допустим, если это какой-нибудь банкинг, человек приходит получить кредит, и мы обучаем нашу модель деревьев решений, и там есть определенный сет параметров, то есть средний доход, текущая работа, пол и так далее, и человеку отказали в кредите, и он хочет узнать, почему, или мы хотим узнать, почему данному потенциальному клиенту отказали в кредите. И мы можем объяснить, следуя этой цепочке решений, почему модель предсказал отказ в кредите. То есть такое примитивное объяснение можно применить для интерпретируемости.
(00:12:56)
Следующее преимущество – быстрое предсказание (fast inference time). Если сравним с нейронными сетями, которые чаще всего имеют миллионы параметров, множество слоев, для того, чтобы сделать предсказание для одной точки, нужно делать все эти трансформации… То есть там тоже идет эта иерархическая структура, нужно посчитать все эти матричные векторные умножения, convolutional и так далее. То есть это может быть долго, в зависимости от нейронной сети. Чаще всего это происходит очень быстро. Во-первых, этот путь от корня до листьев, предиктивное время будет логарифмично пропорционально общему количеству узлов дерева, поэтому inference time очень быстрый чаще всего. Кроме того, здесь на каждом узле обычно мы используем очень простые модели, такие как эти логистические функции. То есть первый признак равен или больше, чем данное число. Или, может быть, если это oblique (00:14:17) decision, тогда это будет линейная функция, после чего исследуется булева (00:14:28) функция.
Поэтому это всё будет происходить очень быстро на каждом ноде. Весь этот путь очень быстрый.
(00:14:41)
Другое преимущество. Чаще всего традиционные алгоритмы, которые обучают эти деревья, они натуральны, им свойственно как есть работать с дискретными признаками, категорическими признаками. Допустим, пол и так далее.
И еще множество преимуществ у деревьев решений. Но, так же, как и любая другая модель, она не лишена недостатков. Самый основной недостаток – это обучить деревья решений. Чаще всего это очень трудная задача. Я имею в виду proper optimization, то есть правильно обучить, найти глобальный минимум проблемы – очень сложная задача. На самом деле, было доказано, что обучение деревьев решений является NP-hard problem, то есть нахождение решений с оптимальной структурой и с оптимальными параметрами является NP-hard проблемой. Ввиду того, что задача non-convex (не выпуклая), а также non-differentiable (не дифференцируемая). Это из-за того, что здесь на каждом ноде у нас есть вот эта trash holding function, булева (00:16:08) функция, какая не дифференцируема. Даже если есть дифференциал, он равен нулю. Поэтому забудьте про SGD или другие gradient based optimization.
Также, если сравнить с нейронными сетями, они не извлекают признаки, не делают эту трансформацию, в которой хорошо работать с нейронными сетями. То есть convolution layers и так далее. Очень хорошо, они автоматически извлекают необходимые признаки, которые делают задачу классификации очень легкой.
Даже, более того, модель на каждом ноде – это чаще всего очень простые модели, такие как axis-aligned. Вот эти деревья axis-aligned, потому что каждое деление – по сути, они параллельны какому-то axis. То есть оно смотрит только на один признак на каждом делении, и не учитывает нелинейность между признаками, корреляцию между признаками, по крайней мере у традиционных деревьев решений. Конечно, есть алгоритмы, которые обучают более комплексные деревья решений. Мы еще поговорим про нейронные деревья. В классическом понимании это так.
Немного расскажу про литературу деревьев решений.
Если смотреть историю, деревья решений – одна из самых первых моделей, которая начала применяться в машинном обучении. То есть самые ранние работы я мог найти, датируются 1950-ми годами, и даже в 1948 году были работы, например, Фишера. Речь вообще не идет про датасет, машинное обучение. Люди это в то время применяли для объяснения статистических моделей, строили такие модели. И так далее. Но расцвет пришелся в 1980-е, 1990-е, когда появился бум машинного обучения, люди начали этим интересоваться благодаря Брайману, Фридману и другим чувакам, которые придумали Random Forests, бустинг постепенно начал набирать популярность в 1990-е годы. И после этого пошло-поехало – очень много работ было написано начиная с 1980–1990-х, по обучению деревьев решений или ансамблям деревьев решений.
Здесь я разделил их на следующие категории. Конечно, когда такой объем литературы, очень сложно делать такие разрезы. Но все-таки, мне кажется, наиболее популярные алгоритмы попадают в эти категории. Я здесь говорю про обучение нейронных сетей.
Самая первая категория – это greedy, то есть жадные рекурсивные алгоритмы. Самый популярный из них – это CART, который мы, скорее всего, чаще всего используем. Он применяется, например, by default используется внутри scikit-learn для обучения decision trees. Также для обучения каждого деревья внутри Random Forests используется CART.
(00:19:49)
То есть оно начинает с корня. Мы имеем только корень. У нас нет ничего. То есть структура дерева неизвестна. Мы начинаем с корня. И начинаем рекурсивное деление. Чаще всего это применяется для бинарных деревьев. Мы пытаемся разделить этот корень на два потомка, по сути, так, чтобы наша выборка в левом или в правом потомке была наиболее чистой. Допустим, есть у нас только два класса, мы постараемся найти тупо через invariation, то есть мы проверяем возможные эти thresholds, values, и также все возможные features (признаки) на предмет того, какая комбинация лучше всего делит наш датасет на два сабсета. И делим.
И, допустим, у нас есть весь датасет на root. Дальше мы делим: допустим, половина датасета уходит налево, половина уходит направо, в идеале. И мы рекурсивно начинаем делать это для каждого потомка. Это достаточно простой и быстрый способ обучения деревьев решений.
Но, как оказалось, люди тоже изучали всякие теоретические аспекты этого метода. Хоть он очень быстрый и очень простой, было доказано, что такие алгоритмы обучают очень не оптимальные деревья с точки зрения оптимизации. Там даже были такие патологические примеры, когда, допустим, нужно разрез делать именно здесь, но так как алгоритм жадный, эта ошибка накапливается. Если, допустим, ошибка на корне, то мы не можем вернуться и исправить эту ошибку. Дальше мы уже идем вниз и рекурсивно начинаем это делить. Эта прогрессивная ошибка накапливается, и в конце очень неоптимальные деревья могут получиться. Существует очень много вариаций этого алгоритма.
(00:22:20)
Кардинально противоположный метод – это brute force search. Я только что рассказывал, что получение оптимальных деревьев решений является NP-hard problem, но есть методы, которые пытаются решить этот NP-hard problem точно. Чаще всего это мотивируется тем, что современные коммерческие решения в mixed integer programming (00:22:52), то есть в constraint optimization… то есть это всякие коммерческие решения, они очень продвинутые, они очень быстрые, они используют достаточно сложные и быстрые алгоритмы, но все-таки они решают NP-hard problem. Поэтому они, во-первых, формулируют процесс обучения деревьев с точки зрения оптимизационной проблемы, поэтому здесь нужны эти целевые числа – mixed-integer constrains для того, чтобы заэнкодить эти решения (то есть нужно идти налево или направо). То есть эти булевы функции должны быть как-то отображены в оптимизационной задаче. Чаще всего используется mixed-integer programming, такая формулировка.
Но так как задача всё еще считается NP-hard, такие алгоритмы, методы чаще всего применяются только для маленьких датасетов – буквально бинарная классификация, где количество признаков может быть от силы 10, и количество датасета – это 1000 поинтов. То есть это, наверное, потолок для таких алгоритмов. Это на основе моего опыта, и также на основе этих пэйперов. Но все-таки такие методы существуют. Люди пытаются как-то оптимизировать, использовать динамическое программирование.
И третья группа не жадная, но все-таки использует некоторую аппроксимацию. Есть путь исправить ошибку, которую мы допустили на корне. Наш алгоритм, который я собираюсь объяснять (TAO), он входит в эту категорию, которая пытается оптимизировать все параметры деревьев. И чаще всего у таких алгоритмов изначальная структура дерева уже дается. И мы пытаемся оптимизировать параметры этого дерева. То есть оно по себе тоже, по сути, HP-hard problem.
Там другие алгоритмы существуют, допустим, soft decision tress – это топорный метод аппроксимации, я бы сказал, где булева функция hard thresholding function, она заменяется смягчением, то есть люди смягчают его. Вместо того, чтобы отправлять input налево или направо, мы его отправляем и налево, и направо, но с каким-то весом, с какой-то вероятностью. Допустим, с вероятностью 0,9 мы отправим это налево, и с вероятностью 0,1 мы отправляем его направо. И всё дерево становится дифференцируемым, можно найти производные, и поэтому можно его оптимизировать. Конечно, там есть свои минусы, потому что, по сути, это уже не дерево, а некий другой объект. И все эти преимущества – интерпретируемость, быстрые инференсы, – это всё теряется. Думаю, это не надо объяснять.
Литература деревьев решений не ограничивается обучением одного дерева. Мне кажется, редко кто использует только одно дерево решений для своих моделей. Чаще всего оно используется в качестве ансамблей. Допустим, Random Forests, где каждое дерево тренируется независимо, потом оно каким-то образом усредняется или соединяется. Или же boosting, где мы тренируем каждое дерево последовательно неким образом. Думаю, не надо представлять популярные алгоритмы XGBoost, CatBoost и так далее.
(00:27:27)
Также очень много литературы по комбинированию деревьев решений и других моделей. Допустим, люди пытались применить support-vector machines (SVM) вместе с деревьями решений, также LDA. Сюда входят нейронные деревья решения, а также байесовские деревья решения.
На этом заканчиваю со введением. Давайте поговорим про наш алгоритм.
Мы рассматриваем, во-первых, классическую задачу, где у нас есть лейбл, то есть обучение с учителем. Лейбл известен – это наиболее популярная задача, думаю, в машинном обучении, где у нас есть классификация, регрессия и так далее. То есть лейбл у нас дается. И также наш алгоритм предполагает, что изначальная структура дерева уже дана. Она может быть рандомно сгенерирована. Допустим, задаем какую-то группу дерева (depth), говорим «Заполни полностью эту глубину бинарным деревом», а параметр на каждом ноде можно инициализировать random.
А также мы можем использовать какой-то warm start. То есть мы можем запустить CART, CART даст нам начальную структуру, также начальные параметры, и мы начинаем нашу работу, наш алгоритм с этой структуры.
С этими двумя предположениями мы формулируем следующую оптимизационную задачу. То есть это классическая задача машинного обучения, где у нас дается функция ошибки, и мы пытаемся минимизировать эту функцию ошибки, где это T – наше предсказание, которое дается на дерево решения, и y – это наш лейбл. И мы пытаемся оптимизировать параметры для того, чтобы оптимизировать функцию ошибки.
И достаточно обобщенный loss function. Мы не требуем определенную формулировку. Для регрессии это может быть среднеквадратическая ошибка. Для классификации чаще всего применяется cross-entropy loss, или hinge loss, или misclassification loss. То есть нам не нужно, чтобы он был дифференцируем.
(00:30:25)
Также здесь – это по выбору, необязательно – можно добавить регуляризацию, допустим, l2 regularization, где мы регулиризируем параметры на каждом узле. Это помогает тому, чтобы не было переобучаемости, или для того, чтобы получить более компактную модель. Допустим, если у нас железо с ограниченными свойствами, допустим, память и так далее, то для того, чтобы получить более компактную модель, мы можем применить эту регуляризацию: допустим, l1 norm, l2 norm и так далее. Но это optional.
Наш алгоритм TAO базируется на трех теоремах. Здесь все эти три теоремы упрощаю, без каких-либо доказательств и математических формул. Всё это вы можете найти в сопутствующих публикациях.
Коротко говоря, первая самая важная теорема – это условие разделимости (separability condition). По названию алгоритма можно предположить, что… То есть tree alternating optimization (TAO), то есть мы собираемся оптимизировать с помощью чередования. Не знаю, правильный ли это перевод. То есть мы собираемся замораживать определенную часть нашего дерева и оптимизировать другой набор, часть деревьев, которую мы не замораживали. Поэтому это separability condition нам позволяет это делать.
Давайте рассмотрим для простоты две ноды, два узла i и j. И давайте предположим, что мы заморозили все остальные параметры всех остальных узлов. Допустим, у нас есть два узла i и j, а все остальные параметры мы замораживаем. Мы их не оптимизируем, по сути, рассматриваем как константы.
И теорема дальше следует, что если ноды i и j не наследуют друг друга, то мы можем написать наш loss function с предыдущего слайда как функция ошибки над узлом i и функция ошибки над узлом j. По сути, это говорит, что мы можем оптимизировать каждый такая нода независимо друг от друга, параллельно. И это нам дает возможность фокусироваться только на одном узле и оптимизировать только этот узел.
Здесь визуальное представление. Это тот же пример, который я использовал ранее. Рассматриваем этот узел и этот узел. Они не наследуют друг друга, по сути, они независимы. Если мы рассматриваем, допустим, ноду два… корень и этот узел, то у них есть это потомственное отношение. По сути, этот узел зависит от параметров этого узла. В зависимости от этого узла мы будем решать, отправлять сюда или нет. Но эти два узла независимы друг от друга. Поэтому мы можем оптимизировать их независимо друг от друга. Более того, мы собираемся замораживать параметры корня, также замораживать параметры всех листьев здесь. И задача упрощается.
Хоть это и звучит просто, но это математически имеет смысл. В публикации мы рассматриваем сходимость этого алгоритма, если соблюдать определенные условия.
Продолжаю дальше. Если мы замораживаем эти параметры, то можем оптимизировать каждую ноду независимо друг от друга.
Если это так, то давайте рассмотрим. Ранее я рассказывал, что традиционно мы имеем два типа узлов: листья и внутренние узлы. Давайте рассматривать их отдельно.
Если это leaf node (листья), то, во-первых, логично, что все листья независимы друг от друга, то есть не наследуют друг друга, поэтому мы можем оптимизировать каждый из них независимо. Во-вторых, мы можем последовательно оптимизировать каждый нод отдельно. Давайте рассмотрим только один листик (leaf node) и то, как его оптимизировать.
(00:36:00)
Также я ранее сказал, что actual prediction, то есть предсказание нашей модели дается листьями, на самом деле, потому что внутренние узлы непосредственно отвечают за то, отправить нашу точку налево или направо. Это их основная обязанность. Но наше предсказание дается на самом деле этими листьями. Если это регрессия, то это конкретное значение. Если классификация, то это будет определенный класс: собака или кот, допустим.
(00:36:43)
Если эту задачу упрощать, то, оказывается, задача оптимизации одного листа, одного узла, сводится к тому, что мы должны решить нашу оригинальную задачу – это классификация или регрессия – для этого leaf. Допустим, если это регрессия, то мы минимизируем среднеквадратическую ошибку между лейблом и output этого leaf. Здесь это более обобщенная формулировка, но если мы используем традиционное дерево решений, то это будет константа. То есть мы должны найти такое константное значение, которое бы минимизировало нашу среднеквадратичную ошибку. Если это среднеквадратичная ошибка, то мы можем найти решение этой задачи – это будет тупо среднее значение этих лейблов для задачи регрессии. Но это среднее значение будет не над всей выборкой, не над всем датасетом, а только на определенном куске датасета.
Напоминаю, что мы собираемся заморозить все параметры: для этого узла, этого узла, этого узла. И так как они заморожены, мы начинаем пропускать каждый наш data point. Здесь и есть наш целый датасет. И мы начинаем с корня. И начинаем применять эту булеву функцию. В первой точке мы решаем, что она окажется здесь. Для другой точки она окажется здесь, допустим. И мы пропускаем весь наш датасет. И этот leaf узел получил, допустим, 10 точек, а этот получил 100 точек, и так далее. Каждый leaf будет работать только над своей выборкой.
Это мы называем reduced set (приуменьшенная выборка). И решаем эту нашу задачу, если это классификация, или же регрессия. Для регрессии это будет среднее арифметическое значение, если мы будем использовать константную функцию на каждом leaf узле. Для классификации это будет majority vote, то есть самый часто встречаемый лейбл будет решением этой проблемы. Если это будет более сложная функция, допустим, линейная, то мы будем решать линейную регрессию. В любом случае, задача легко решаема.
(00:39:58)
Если это внутренний узел, то здесь немного сложновато, но давайте разберемся поэтапно. Мы здесь, опять-таки, будем применять separability condition.
Давайте рассмотрим этот узел и этот узел. Они независимы друг от друга, то есть они не преемственны, поэтому мы можем минимизировать каждый из них независимо.
Допустим, возьмем этот нод № 2. Он имеет двух потомков: узел № 4 и узел № 5. Но напоминаю, что мы замораживаем всю остальную часть нашего дерева: это корень и все эти потомки. Все эти параметры заморожены. Поэтому мы можем рассматривать это как некую функцию, которая принимает какой-то аргумент, и предсказывает какое-то значение.
Здесь, на самом деле, будет какой-то тоже sub tree, то есть такую форму будет иметь. Но так как все параметры заморожены, какой-то input будет в каком-то leaf узле, он будет предсказывать какой-то output, и мы можем измерить, насколько была ошибка. То есть это, опять-таки, константная функция.
Второе наблюдение – это то, что эта функция на каждом узле… Опять-таки, предсказание дается нашими листьями. Внутренний узел отвечает за то, чтобы направить наш input налево или направо. Здесь мы, по сути, имеем только два выбора. Это предполагает, что мы здесь должны использовать бинарную классификацию. Но что должно классифицировать этот внутренний узел? Для этого мы делаем следующее. Так как вся остальная часть дерева заморожена, какая-то часть датасета окажется здесь, и мы каждый наш поинт, каждую нашу точку пропускаем через левую часть, через левый потомок и через правый потомок. И измеряем нашу функцию ошибки.
Допустим, если это классификация, то мы пропускаем через левый потомок, она предсказывает класс 4. Правый потомок предсказывает, допустим, что это класс 10. И мы знаем, что должно быть правильным. Допустим, класс 10 правильный. И логично, что я должен отправить эту нашу точку на правый потомок, потому что он дает правильное решение.
По сути, мы здесь переразмечаем наш датасет. У него уже есть лейбл, но на каждый датасет мы объявляем новый лейбл. Но этот лейбл будет иметь только два типа: правый потомок или левый потомок. Поэтому на этом ноде, на этом узле мы будем решать задачу бинарной классификации.
Для простоты давайте рассмотрим, что у нас рассматривать линейный кейс, то есть каждая эта функция имеет линейную форму. То есть мы будем умножать вектор. X здесь – это наш input. W – это вектор весов. Мы делаем вектор умножения. Это у нас Bayes term. Если это больше или равно нулю, то мы отправляем его налево, допустим. Otherwise мы отправляем этот input направо.
(00:44:01)
Если использовать эту модель и формулировать эту бинарную классификацию, по сути, это сводится к тому, что здесь мы будем решать задачу логистической регрессии.
Это более формальное представление оптимизационной задачи, где этот Y bar, по сути, означает переразметку. Для каждого input мы будем выявлять, какой из потомков дает лучше функцию ошибки, меньше функцию ошибки. И мы будем говорить, что если правый потомок, допустим, дает лучшую ошибку, то для этого input правильный ответ будет +1, для другого будет –1. И мы это делаем для каждого input, который разместился на этом узле. И решаем эту оптимизационную задачу. Это мы можем применить liblinear (00:44:58), или, допустим, внутри scikit-learn можем применить логистическую регрессию для решения этой проблемы.
(00:45:10)
Мы имеем всё, что нам нужно. Оптимизация для внутренних узлов и оптимизация для каждого из листьев. И здесь всё это можем как summary объединить внутри этого алгоритма. Как input нам дается наш training set. И нам нужно начальное дерево, рандомное или из другого алгоритма.
Эта часть не особо важна.
Мы здесь запускаем наш for loop.
Забыл здесь сказать, что эти separability condition мы применяем для каждого taps (00:46:02), потому что это логично. По сути, мы можем применять это для всех узлов, которые не имеют этой преемственной связи. Допустим, этот нод или этот нод. Но для упрощения алгоритма мы будем использовать все ноды на одном уровне. Все узлы на одном уровне независимы друг от друга, не имеют этой преемственной связи, поэтому мы можем оптимизировать каждую из них индивидуально независимо друг от друга. Поэтому мы рассматриваем наше дерево на каждом уровне, на каждой глубине, и начинаем с корня. Но этот порядок не имеет никакого значения. Мы можем начать с листьев и идти вверх, или же можем начать с корня и идти вниз, или можем использовать какой-то другой порядок.
(00:46:59)
На каждом уровне, на каждой глубине мы оптимизируем каждый нод независимо друг от друга.
Если это лист (leaf node), тогда мы решаем оригинальную задачу: или регрессия, или классификация, в зависимости от типа листьев. Если это константа, то это будет точное решение. Мы можем и усреднять, или majority vote. Linear – мы можем обучить линейную регрессию. Если это нейронная сеть, то это будет HDD optimization на этих данных, на subset data points (00:47:40).
Если же это внутренние узлы, то мы всегда тренируем бинарную классификацию на дата-поинтах, которые окажутся на данном узле. И мы это повторяем, то есть это корень alternating optimization.
И если определенные условия сходятся, если мы решаем каждую задачу точечно на каждом узле, то есть необходимые гарантии, что алгоритм будет сходиться. Также мы можем гарантировать, что оно будет monotonically decreasing. То есть хорошо иметь такие теоретические свойства в целом.
(00:48:24)
Дальше практическое применение. Давайте рассмотрим один из более простых примеров, где мы применяем наш TAO алгоритм для обучения каждого дерева внутри ансамбля.
Давайте рассмотрим Random Forests, где мы тренируем каждое дерево на какой-то подвыборке, и тренируем каждое дерево независимо друг от друга. И потом усредняем, или же берем majority vote для классификации.
Для decision nodes (для внутренних узлов) мы будем использовать линейные узлы, линейную функцию. Это векторное умножение. Если это больше, чем ноль, то мы отправляем налево, в ином случае – направо.
Также мы рассматриваем два типа листьев: это константа, то есть очень просто решается, или же линейные узлы (тоже просто решается, можем приманить scikit-learn для того, чтобы зафитить линейную регрессию, или же логистическую регрессию, где у нас будет k классов, или какой-то linear soft max обучить).
В качестве инициализации мы собираемся использовать рандомные деревья. То есть структура изначально будет… Мы задаем глубину и заполняем эту глубину полностью. А на каждом ноде мы инициализируем рандомными параметрами.
(00:50:13)
Также мы будем использовать l1 regularization. Широко известно, что оно будет нам генерировать более разреженные деревья, разреженные вектора на каждом ноде, и это помогает для того, чтобы получить более компактное дерево.
И вот выборочные результаты. Больше датасетов можете найти в публикациях.
Здесь для MNIST мы сперва сравниваем одно дерево. T означает, сколько деревьев мы будем использовать в каждом ансамбле. Также дельта означает максимальную глубину дерева.
Для простоты мы здесь сравниваем с CART. И можем увидеть, что одно дерево уже показывает достаточно хорошие результаты – 5% для MNIST. Для деревьев это достаточно неплохой результат.
Но самое интересное происходит с ансамблями. Во-первых, используя всего лишь 30 деревьев, мы уже можем получить, по сути, точность, которая сопоставима с нейронными сетями. Не конволюционными, но multilayer perceptron показывает примерно такой же результат, как и forest.
И мы сравниваем с популярными методами, такими как XGBoost, Random Forests, AdaBoost, и другими методами в литературе. На многих датасетах, которые мы использовали, наш алгоритм показывал всегда или же лучший результат, или же близко к лучшему результату.
Это другой пример, и, в принципе, тут то же самое.
В публикации мы еще показываем общее количество параметров, то есть на каждом ноде, используя разреженные вектора. В принципе, наша модель сопоставима с другими моделями, допустим, Random Forests, а в некоторых ситуациях и более компактнее.
(00:52:57)
Тот же самый результат можно понаблюдать для регрессии.
Забыл сказать, что означает TAO-c, TAO-l.
TAO-c – это если оба используют линейную функцию на каждом внутреннем узле. Но эти leaf nodes отличаются. TAO-c использует constant leaf, константную модель на каждом leaf узле.
TAO-l использует линейную функцию на каждом узле. Логично, что линейный узел, оно намного более сложно, поэтому должно вести к лучшему результату.
По сути, тут везде TAO-l показывает результаты лучше.
То же самое можно наблюдать и здесь. В некоторых результатах TAO-l использует только одно дерево, и иногда показывает лучше результат, чем некоторые ансамбли деревьев, что было для нас неким сюрпризом.
(00:54:07)
Здесь более визуальный результат, где мы придумываем вымышленный сценарий, где нужно предсказать…
Input для нас – это MNIST датасет, то есть 28 на 28, картинка. Мы это flatten, отображаем как один большой вектор. И output должен быть класс specific rotation. Допустим, № 1 – мы собираемся повернуть 45° против 1. Или, допустим, цифру 3 мы должны повернуть на 60° по оси. И, конечно же, мы не говорим алгоритму, для какого класса какой rotation мы используем. Мы просто даем ground-truth, то есть тренировочный сет, что будет input, что будет output. Сама задача нетривиальна, потому что это регрессия, во-первых (это not classification), где мы должны предсказать другую картинку, что является многоразмерным output. То есть это достаточно непростая задача. И мы сравниваем разные алгоритмы. Random forest, используя тысячи деревьев. Мы видим, что, в принципе, неплохо, но она здесь усредняет некоторые классы.
(00:55:49)
Для XGBoost можем наблюдать какие-то шумы.
Для нашего алгоритма наиболее близка к оригинальному лейблу.
Это conclusion. Пропущу эту часть.
А, здесь хотелось бы отметить, что мы пробовали не только с bagging, где каждое дерево обучается независимо. Также пробовали делать ансамбли с помощью boosting. И там мы наблюдали такой же результат, если ни лучше.
В качестве hyperparameters… по поводу hyperparameter, оно не нуждается в особом тюнинге. Мы должны указать, если рандомно инициализируем наши деревья, которая будет максимальная длина. И дальше еще мы должны указать, что должен быть regularization parameter alpha для регуляризации. И количество итераций, и так далее. Вот эти параметры, нужно с ними поиграться. Возможно, использовать cross-validation. Но оно не намного сложнее, чем hyperparameter tuning для XGBoost или других альтернативных моделей.
(00:57:36)
В конце хотел быстро поговорить про гибрид между деревьями решений и нейронными сетями. Для этого хотел повторить о преимуществах и недостатках деревьев решений. Интерпретируемость, быстрый prediction time, и так далее.
И также я сказал, что деревья решений не лишены минусов, определенных недостатков. Оно не делает этот feature extraction, как в нейросетях. Также каждый нод обычно использует очень примитивные модели, как axis aligned tress, то есть один признак на каждом узле. Или, как мы использовали, oblique (00:58:25) decision tress, линейную функцию на каждом узле (что тоже достаточно простая модель, на самом деле, по сравнению с нейронными сетями или kernel machines).
(00:58:38)
С другой стороны, у нас тут есть нейронные сети, у которых есть это свойство representation learning. То есть они могут экстрактить хорошие признаки, тоже имеют эту иерархическую структуру. Но там иерархия заключается в другом, не как в деревьях. Трансформация, по сути, извлекает очень полезные признаки, которые делают классификацию очень легкой.
Также нейронные сети, используя современные фреймворки, можно очень эффективно их оптимизировать, используя SGD, тогда как тренировка деревьев решений – достаточно сложная задача.
С другой стороны, нейронные сети имеют ряд недостатков. Достаточно долгий inference time. Для одной точки мы должны пропустить через всю сетку. Согласен, что в ту сторону тоже идет research, как можно компрессить нейронные сети. Но если опустить эти моменты…
Также интерпретируемость. Часто нейронные сети используют как black box models, то есть нетривиально их интерпретировать, во всяком случае не так просто, как традиционные деревья решений.
(01:00:11)
В литературе это уже есть, но, по идее, это логично – скрестить две этих модели. Мы берем лучшее из двух сторон: интерпретируемость у деревьев решений, также representation learning, capability от нейронных сетей. То есть мы собираемся использовать нейронные сети на каждом узле, и это дает нам в некотором роде свои преимущества. То есть иерархическая структура дает нам преимущество того, что у нас будет fast inference time, то есть нам необязательно пропускать через каждую нейронную сеть, а мы будем использовать одну нейронную сеть или несколько нейронных сетей только на этом пути от корня до листьев. А все остальные не будут использоваться для этого конкретного input. Поэтому inference time будет быстрым. В какой-то степени мы можем интерпретировать эту модель. Она не будет очень тривиально интерпретируема как классические деревья решений, но какую-то информацию мы можем извлечь. Я покажу на следующих слайдах.
Также мы будем брать всё хорошее с нейронных сетей. Наши узлы будут более мощными. Оно будет использовать более нетривиальные модели, нелинейные модели, чем являются нейронные сети, в которых есть representation learning ability. Допустим, если это картинка, то традиционные деревья решений будут смотреть только на один пиксель на каждом делении, что очень нехорошо, потому что один пиксель не дает никакой информации. Мы должны смотреть на некоторые патчи в изображении. Поэтому чаще люди делают трансформацию функцию, извлекают какие-то признаки с картинок, а только потом используют деревья решений.
(01:02:36)
Для простоты, мы собираемся использовать следующую модель для демонстрации нашей идеи, но можно обобщить достаточно легко.
На каждом внутреннем узле мы собираемся использовать все те же oblique decision tress, где линейная функция используется при каждом делении, как и в предыдущих экспериментах, которые я показывал для ансамблей. Но каждый наш лист будет использовать нейронную сеть. Но эта нейронная сеть будет не такой большой и сложной, а она будет намного проще, для того, чтобы модель была намного компактнее.
Наша цель – не достичь здесь state of the art, не достичь самый лучший результат на каком-то датасете, а наша основная задача – получить модель, которая балансирует точность, компактность, и если возможно, то и интерпретируемость. Мы преследуем несколько целей.
Для демонстрации мы выбрали эту модель. Как обучать эту модель? По сути, это не требует каких-либо модификаций для нашего TAO алгоритма. Просто для обучения внутренних узлов мы будем использовать бинарную классификацию, а если быть точнее, логистическую регрессию, потому что здесь у нас линейная функция на каждом узле. Для каждого из листьев мы собираемся использовать нейронную сеть. Это единственное различие. Мы здесь будем оптимизировать нейронную сеть на подвыборке, которые будут использоваться на данном leaf node, на данном узле. Это единственное различие. Если в предыдущих экспериментах в ансамбле мы используем константу и линейную функцию, то здесь мы будем использовать нейронную сеть. И для обучения нейронных сетей это достаточно прямолинейно, то есть мы будем использовать готовые фреймворки. То есть это supervised task. Опять-таки, будем использовать SGD для обучения.
Здесь results. Для других датасетов у нас есть и forten (01:05:26), и, по-моему, еще какой-то датасет (можете посмотреть в публикации). Здесь для простоты показал для MNIST. Это Random Forests performance.
(01:05:54)
И это разная архитектура. То есть tao-mnist-cnn2 означает, что на каждом листе мы собираемся использовать convolutional neural net. Но какой именно тип – можете посмотреть, мы всё это указали в публикации. Но сразу говорю, что это очень маленькая сверточная нейронная сеть, которая использует очень мало параметров. Это намного меньше, чем LeNet (01:06:26) или другие сверточные нейронные сети, которые используются для MNIST. Даже с использованием такой, по сути, крошечной сверточной нейронной сети, но так как мы используем здесь гибрид, собираемся использовать несколько таких маленьких сверточных сетей, результат достаточно хороший в виду того, что мы здесь используем достаточно маленькое количество параметров. Если посчитать также inference time, если посчитать FLOPS, то тоже достаточно маленький. Допустим, есть LeNet, там примерно в 15 раз меньше FLOPS и намного меньше параметров.
Если немного усложнить сверточную нейронную сеть, добавить пару слоев, немного увеличить параметры, то можно достичь точность LeNet5, и если взглянуть на number of parameters, он меньше, чем LeNet5, и FLOPS тоже намного меньше, чем LeNet5.
То есть как основной summary – это наши нейронные деревья, по сути. Может достичь или почти достичь уровня state of the art сверточных нейронных сетей в данном примере. Но оно более компактное, если судить по количеству параметров, а также по inference time.
(01:08:19)
По поводу интерпретируемости, признаю, что это очень непросто интерпретировать такую модель, где на каждом листовом узле у нас есть нейронная сеть. Но какую-то информацию мы все-таки можем извлечь.
Допустим, здесь у нас есть class distribution, то есть распределение классов на каждом узле.
В корне мы будем иметь, по сути, все классы, поэтому здесь присутствуют все классы. Это для CFAR (01:08:59), кстати.
Если мы опустимся на следующую глубину, то можем посмотреть, что точки, которые достигли этого узла, у нас здесь не имеются все классы, у нас только есть subset of classes, то есть не все классы присутствуют на данном узле, по сути. Даже если присутствуют, их количество очень маленькое.
По сути, это означает, что каждый subtree специализируется на каких-то классах. Не на всех классах, а на каких-то subset of classes, что делает, в принципе, обучение намного проще, потому что этот узел будет иметь дело с относительно меньшим количеством классов. И если приблизить, то можно посмотреть, что это деление не рандомное. По сути, оно делит всех эти наши animals (dog, frog и так далее), всех животных, от видов машин (airplanes, trucks и другие средства передвижения), что очень прикольно.
(01:10:17)
Если мы опустимся еще ниже, то можем увидеть еще большее разбиение. По сути, каждый наш листовой узел фокусируется только на четырех классах, а этот фокусируется более-менее только на двух классах. Поэтому эта маленькая сверточная сеть фокусируется на меньших количествах классов, что делает процесс обучения более легким. И в унисоне всё это дает хороший перформанс.
Мы еще не копали в эту сторону, но, возможно, есть еще другие способы проинтерпретировать данные нейронные деревья, но это уже хоть что-то.
На этом всё. Извините, что забрал так много времени. Как всегда, потерял счет времени.
В конце ссылки на статьи, которые я указал в данной презентации.
Николай Михайловский: Арман, спасибо большое. Очень интересный рассказ. Коллеги, пожалуйста, можно задавать Арману вопросы. У нас есть Q&A, у нас есть чат. Можно поднимать руки. Постараюсь дать вам возможность голосом поговорить.
Пока вы собираетесь с вопросами, я на правах хозяина прокомментирую.
Во-первых, вопрос. Когда вы работаете с MNIST, вы на вход даете чистое значение пикселов.
Арман Жармагамбетов: Да.
Николай Михайловский: То есть это raw pixels?
Арман Жармагамбетов: Да. Для всех экспериментов с ансамблями и нейронными деревьями мы работаем напрямую с пикселями 28 на 28. Это всё мы отображаем как один длинный вектор, и работаем непосредственно с ними. По-моему, применяется нормализация в целом.
Николай Михайловский: Прокомментирую, а вы, может, про это что-то скажете.
Мысль 1-я. Структурно ваш алгоритм чем-то похож на обратное распространение ошибки. То есть вы берете некие подмножества, считаете, по сути, на них ошибку, и дальше ее гоните по слоям.
Арман Жармагамбетов: В алгоритме propagational, в обратном распределении эта ошибка распределяется на все предыдущие узлы. Эта ошибка должна propagated распространяться от листьев до корня. А здесь всё происходит независимо. Мы обучаем, допустим, листья, и всё. Идем наверх. И независимо обучаем узлы на следующем уровне. И так до корня. Explicitly явно так ошибка не распространяется.
Николай Михайловский: Она распространяется в некотором другом смысле, что вы получаете из листьев ошибку, используете ее для обучения следующего уровня, и дальше оно проходит. То есть оно не эквивалентно обратному распространению ошибки, но неким образом структурно…
Арман Жармагамбетов: Да, как будто присутствует там неявно.
Николай Михайловский: И еще одна алгоритмическая рифма, она с бустингом, когда мы, по сути, берем и учим некое дерево решений, а на residuals учим следующее дерево решений. У вас эта вещь в некоем неявном виде тоже присутствует, хотя тоже не эквивалентна.
(01:15:00)
У нас появились вопросы. Илья Трофимов спрашивает: «В алгоритме TAO если изменяется условие сплитинга на уровне N, как изменяются условия в узлах ниже?».
Арман Жармагамбетов: Боюсь, что я не понял вопрос.
Если мы меняем, вместо того, чтобы отправить точку, которая больше, чем A, направо, мы вместо этого если отправляем налево, что тогда изменится? В этом состоит вопрос?
Николай Михайловский: Я свою интерпретацию сейчас дам. Если это всё не поможет, то мы Илье дадим слово. В моем понимании, вопрос о том, что вы начинаете оптимизировать, начиная с листьев, вы оптимизируете лист, поднимаетесь уровнем выше – оптимизируете над неким набором листьев веточку. Поднимаетесь набором еще выше – оптимизируете следующую веточку. Вопрос: после этого вы возвращаетесь ниже на уровень или вы так и продолжаете ходить снизу вверх?
Арман Жармагамбетов: Как я говорил, порядок не имеет значения. Если мы идем снизу вверх, то одна итерация… Это только одна итерация: мы начинаем с листьев, потом идем выше, потом идем на следующий уровень, и так до корня. Потом мы опять начинаем с листьев. То есть это одна итерация: прогон от листьев до корня – это один прогон. Но мы опять возвращаемся…
(01:17:23)
Здесь порядок указан наоборот, но последовательно мы начинаем от листьев, следующий уровень, следующий уровень, и так до корня. И потом возвращаемся и опять делаем. Это делается несколько раз. На практике, по сути, 20 итераций хватает. Но если мы хотим теоретически обосновать результат, то нужно это повторять, пока мы ни встретили сходимость. Но на практике 20 итераций достаточно.
Николай Михайловский: Илья, мы ответили на ваш вопрос?
Илья Трофимов: Вроде да. Спасибо за доклад. Я правильно понимаю, что вы, во-первых, берете какое-то уже готовое дерево изначально…
Арман Жармагамбетов: Да.
Илья Трофимов: …и потом дооптимизируете его, причем не как обычное дерево строится сверху вниз, а наоборот, бегаете снизу вверх несколько раз?
Арман Жармагамбетов: Да-да.
Илья Трофимов: От листьев к корню?
Арман Жармагамбетов: Да. Но можно двигаться от корня к листьям тоже. Порядок не сильно имеет значение.
Илья Трофимов: ОК.
Николай Михайловский: Спасибо. Коллеги, еще вопросы?
Арман Жармагамбетов: Я бы хотел добавить. Берется готовое дерево. Но это дерево, допустим, в публикации, где мы используем ансамбль деревьев, мы каждое дерево инициализируем рандомно. По сути, это complete… полное дерево до определенной глубины. И мы начинаем от этого дерева, мы начинаем с корня. Когда оптимизируем корень, то вся остальная часть frozen, заморожена, и мы оптимизируем корень. А дальше идем на следующий уровень, и так далее. То есть большой разницы in terms of performance там нет. То есть начинать идти с корня и идти вниз, или начинать с листьев и идти вверх, большой разницы мы экспериментально не наблюдали. Потому что мы это делаем несколько раз. Даже если какая-то ошибка произошла, в следующей итерации есть возможность это исправить.
(01:20:05)
Николай Михайловский: Спасибо. Коллеги, еще вопросы? Пока вы собираетесь с вопросами, я хотел поделиться еще одной мыслью.
Дерево есть пример гиперболического пространства Громова. Помимо деревьев гиперболическими пространствами Громова являются многие другие объекты, в том числе пространство-время Минковского, и прочее. И здесь возникает несколько интересных, на мой взгляд, алгоритмических рифм. Одна рифма состоит в том, что раз уж у нас есть вложение дискретного объекта в непрерывный объект, то, вероятно, есть некая непрерывная процедура, которая позволяет такой объект строить сначала как непрерывный объект, а потом уже его дискретизовать. Теоретически такая конструкция, вероятно, могла бы привести к построению дифференцируемой процедуры, ведущей не к soft trees, а к hard tress, но через дифференцируемые процедуры, через дифференцируемые объекты. Может быть, там какая-нибудь интересная собака порылась.
Арман Жармагамбетов: Да. Мне приходит на ум несколько статей на этот счет, где применяется схожая идея. Во-первых, люди применяют soft decision tree, обучая его полностью непрерывно, находя производные и оптимизируя их стандартными способами. Затем превращают его в дискретное пространство, где на каждом узле у нас hard decision trees. Но в теоретическом плане нет доказательств эквивалентности и так далее. Потому что обучение происходило в непрерывности, но после этого оно дальше аппроксимировалось. Аппроксимация, и насколько хороша эта аппроксимация, нет теоретической обоснованности.
Дальше есть методы на основе квантизации, где есть этот forward propagation и backward propagation. В процессе forward propagation используется hard decision tree, а для backward propagation использует soft version (01:23:07) – straight-through estimator, там есть свои методы, которые люди берут с квантования. Но, опять-таки, там тоже нет теоретического обоснования.
В нашей ситуации мы не переходим в soft decision tree. By construction метод не использует такой непрерывный вид, то есть soft decision tree, он напрямую работает с hard decision tree. Для этого мы вынуждены применять замораживание на каждой глубине. Поэтому в этом различается.
Николай Михайловский: Я просто говорю, что, возможно, метрические гиперболические пространства, пространства Громова, они являются естественным математическим инструментом для того, чтобы доказать теоремы сходимости, например, как для непрерывных аналогов, так и для дискретизации этих непрерывных аналогов в собственно деревья решений.
Арман Жармагамбетов: Да, вполне возможно.
Николай Михайловский: Но это, опять же, чисто мысли вслух, и никакой гарантии того, что это на самом деле так. Просто те мысли вслух, которые вызывает ваш действительно неожиданно интересный доклад, я бы так сказал.
Арман Жармагамбетов: Спасибо.
(01:24:51) (Конец записи.)