Перевод Глубокие нейронные деревья принятия решений

Описание

Глубокие нейронные сети доказали свою эффективность при обработке данныхот органов чувств, таких,как изображения и аудио. Однако для табличных данных более популярны древовидные модели. Хорошим свойством древовидных моделей является их естественная интерпретируемость. В этой работе мы представляемDeepNeuralDecisionTrees(DNDT)древовидныемодели, реализованные нейронными сетями. DNDT внутренне интерпретируем, так как это дерево. Тем не менее, поскольку это также нейронная сеть (NN), ее можно легко реализоватьс помощьюинструментарияNN и обучитьпо алгоритмуградиентногоспуска, а непо жадному алгоритму (алгоритмужадного разбиения). Мы проводим оценку DNDT на нескольких табличных наборах данных, проверяем его эффективность и исследуем сходства и различия между DNDT и обычными деревьями решений. Интересно, что DNDT самообучаетсякак на разделенном, так и на функциональном уровне.

1. Введение

Интерпретируемость прогностических моделей важна, особенно в тех случаях, когда речь идет об этикеправовой, медицинскойи финансовой,критически важных приложениях, где мы хотим вручную проверитьрелевантностьмодели. Глубокие нейронные сети (Lecunetal., 2015 [18];Schmidhuber, 2015 [25]) достигли превосходных результатов во многих областях, таких как компьютерное зрение, обработка речи и языковое моделирование. Однако отсутствие интерпретируемости не позволяет использоватьв приложенияхэто семейство моделейкак черныйящик, для которогомы должны знатьпроцедурупрогноза, чтобыверифицироватьпроцесс принятия решения. Более того, в некоторых областях, таких как бизнес-аналитика (BI), часто более важно знать, как каждый фактор влияет на прогноз, а не сам вывод. Методы, основанные на дереве решений (DT), такие как C4.5 (Quinlan, 1993 [23]) и CART (Breimanetal., 1984 [5]), имеют явное преимущество в этом аспекте, поскольку можно легко проследить структуру дерева и точно проверить, как делается прогноз.

В этой работе мы предлагаем новую модель на пересечении этих двух подходов глубокое нейронное дерево решений (DNDT),исследуем егосвязи с каждым из них. DNDT- это нейронные сети со специальной архитектурой, где любой выборвесов DNDT соответствует определенному дереву решений и поэтому интерпретируем. Однако, поскольку DNDT реализуется нейронной сетью (NN), она наследует несколько интересных свойств, отличныхоттрадиционныхDT: DNDT может быть легкореализованнесколькимистрокамикода в любом программном фреймворке NN; все параметры одновременно оптимизируются с помощью стохастического градиентного спуска, а не более сложной и потенциально неоптимальной процедурыжадногорасщепления.DNDTготов к крупномасштабной обработке с обучением на основе мини-патчейи ускорением GPUот коробочного решения, его можно подключить к любой более крупной модели NN в качестве строительного блока для сквозного обучения с обратным распространением (back-propagation).

2.Похожие работы

Модели на основе деревьев решений.Древовидные модели широко используются в обучении под наблюдением, например, взадачахклассификации. Они рекурсивно разбивают входное пространство и присваивают метку/оценку конечному узлу. Хорошо известные древовидные моделииспользуютC4. 5 (Quinlan, 1993 [23]) и CART (Breimanetal., 1984 [5]). Ключевым преимуществом древовидных моделей является то, что они легко интерпретируются, поскольку предсказания задаются набором правил. Также часто используется ансамбль из нескольких деревьев, таких какслучайный лес(Breiman, 2001 [6]) иXGBoost(Chen&Guestrin, 2016 [8]), чтобы повысить производительность за счет интерпретируемости. Такие древовидные модели часто конкурируют или превосходят нейронные сети в задачах прогнозирования с использованием табличных данных.

Интерпретируемые модели. По мере того как предсказания, основанные на машинном обучении,используютсяповсеместнои затрагивают многие аспекты нашей повседневной жизни, фокус исследований смещается от производительности модели (например, эффективности и точности) к другим факторам, таким как интерпретируемость (Weller, 2017 [26];Doshi-Velez, 2017 [11]). Это особеннонеобходимов приложениях, где существуютпроблемыэтические (Bostrom&Yudkowsky, 2014 [4]) или безопасности, и предсказания моделей должны быть объяснимы, чтобы проверить правильность процесса рассуждения или обосновать решениядля них. В настоящее время предпринимается ряд попыток сделать моделиобъяснимыми.Некоторые из них являются модельно-агностическими (Ribeiroetal., 2016 [24]), в то время как большинство из них связаны с определенным типом модели, например, классификаторамина основе правил (Dashetal., 2015 [10];Malioutovetal., 2017 [19]), моделями ближайших соседей (Kimetal., 2016 [15]) и нейроннымисетями (Kimetal., 2017 [16]).

Нейронные сети и деревья решений. В некоторых исследованиях предлагалось унифицировать модели нейронной сети и деревьев решений.Bul&Kontschieder(2014) [7] предложили нейронныелеса решений( Neural Decision Forests NDF) как ансамбль нейронных деревьев решений, где расщепленные функции реализуютсяслучайнымимногослойными персептронами.Deep-NDF (Kontschiederetal., 2015 [17]) использовал стохастическую и дифференцируемую модель дерева решений, которая совместно изучает представления (черезCNNs) и классификацию (через деревья решений). Предлагаемый нами DNDT во многом отличается от этих методов. Во-первых, у нас нет альтернативной процедуры оптимизации для изучения структуры (разделения) и обучения параметров (матрица оценок). Вместо этого мы изучаем их все с помощьюоднопроходногообратного распространения (back propagation). Во-вторых, мы не ограничиваем разбиение двоичным (левым или правым), поскольку мы применяем дифференцируемую функцию разбиения, которая может разбивать узлы на несколько ( 2) листьев. Наконец, что наиболее важно, мы разрабатываем нашу модель специально для интерпретируемости, особенно для приложенийк табличным данным, где мы можем интерпретировать каждую входную функцию. Напротив, модели в (Bul&Kontschieder, 2014 [7];Kontschiederetal., 2015 [17]) предназначены для прогнозирования и применяются к необработанным данным изображения. Некоторые проектные решения делают их непригодными для табличных данных. Например, вKontschiederetal. (2015 [17]), они используют менее гибкое дерево, в котором структуражесткофиксируется, пока изучается разбиение узла.

Несмотря на похожее название, наша работа кардинально отличается от работыБалестриеро(2017 [2]), которая разработала своего рода наклонное дерево решений, реализованное нейронной сетью. В отличие от обычных одномерных деревьев решений, каждый узел внаклонномдереве решений включает в себя все функции, а не одну функцию, что делает модель не интерпретируемой.

Альтернативныеактиваторыдереварешений.ОбычныеDT изучаются рекурсивнымжаднымрасщеплением признаков (Quinlan, 1993;Breimanetal., 1984 [23]). Это эффективно и имеет некоторые преимущества для выбора признаков, однако такойжадныйпоиск может быть неоптимальным (Norouzietal., 2015 [20]). В некоторых недавних работах исследуются альтернативные подходы к обучению деревьев решений, которые направлены на достижение лучшей производительности при менеетребовательнойоптимизации, например с помощью латентного структурированного прогнозирования переменных (Norouzietal., 2015 [20]) или обучения контроллера расщепления RNN с использованием обучения с подкреплением (Xiongetal., 2017 [28]). Напротив,нашDNDT намного проще, чемуказанные, но все же потенциально может найти лучшие решения, чем обычные индукторы DT,содновременным поискомструктурыи параметровдерева с SGD. Наконец, также отмечаем, что в то время как обычные активаторы DT используют только двоичные расщепления(для простоты), наша модель DNDT может одинаково легко работать с расщеплениями произвольной мощности, что иногда может привести к более интерпретируемым деревьям.

3.Методология

3.1.Функция мягкого контейнера

Основной модуль, который мы здесь реализуем, - это функция мягкой ячейки(Doughertyetal., 1995)или объединения множества точечных объектов в динамические полигоны (бины),которуюмы будем использовать для принятия решений о разделении в DNDT. Как правило, функциябиннингапринимает в качестве входных данныхвещественныйскаляр x и выдает индексячейки, которойонпринадлежит.Жесткоеразделение по ячейкамнедифференцируемое, поэтому мы предлагаем дифференцируемую аппроксимацию этой функции.

Предположим, что у нас есть непрерывная переменная x, которую мы хотим разбить на N + 1 интервалов. Это приводит к необходимости n точек среза, которые в данном контексте являются обучаемыми переменными. Обозначим точки среза [1, 2,, n]какмонотонно возрастающие, то есть 1 < 2 < < n. Во времяобученияпорядок может быть перетасован после обновления, поэтому мы должны сначала сортировать их в каждом прямом проходе. Однако это не повлияет на дифференцируемость, потому что сортировка просто меняет местами позиции .

Теперь построим однослойную нейронную сеть с функцией активацииsoftmax.

Здесь w-это константа, а не обучаемая переменная, и ее значение задается как w = [1; 2;:: : ; n + 1]. b строится как,

> 0 - фактор напряженности. При 0 выход стремится ктекущемувектору.

Мы можем проверить это, проверив три последовательныхлогита

Когда у нас есть как

x должен попасть в интервал

Таким образом, нейронная сеть в уравнении 1 будет производить почти однократноегорячеекодированиеячейкиx, особенно при более низкой напряженности. При желании,мы можем применить трюкотжига наклона(Chungetal., 2017 [9]), который постепенно снижает напряжение приобучении, чтобы,в конце концов,получить более детерминированную модель.

Если кто-то предпочитает фактическийгорячий (текущийкодируемый)вектор, можно применитьStraight-Through(ST)Gumbel-Softmax(Jangetal., 2017): для прямого прохода мысэмплируемоднократный вектор, используя хитрость с Gumbel-Max, тогда как для обратного прохода (backward pass) мы используемGumbel-Softmaxпривычисленииградиента (см.Bengio(2013 [3]) для более подробного анализа.

На рис.1 показан конкретный пример, где мы имеем скаляр x в диапазоне [0, 1] и две точки среза в 0.33 и 0.66 соответственно. Основываясь на уравнениях1 и 2, мы имеем трилогитаo₁ = x, o₂ = 2x 0.33, o₃ = 3x 0.99.

Рисунок 1. Конкретный пример нашей функции мягкого биннинга с использованием точек среза в 0.33 и 0.66. Ось x - это значение непрерывной входной переменной x2 [0; 1]. Вверху слева: исходные значения логитов; вверху справа: значения после применения функции softmax с т = 1; Внизу слева: т= 0.1; внизу справа: т = 0.01.

3.2Построениепрогнозов

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

Связывая каждый признакx_d со своей собственной нейронной сетьюf_d(x_d), мы можем исчерпывающе найти все конечные узлы с помощью,

Здесь z теперь также является почтигорячимвектором, который указывает индекс листового узла, куда поступает экземпляр x. Наконец, мы предполагаем, что линейный классификатор на каждом листе z классифицирует поступающие туда экземпляры. DNDT проиллюстрирован на Рис. 2.

Рисунок 2. Изученный DNDT для набора данных Iris (сокращенная версия с двумя функциями). Вверху: DNDT - показано, где красным шрифтом указаны обучаемые переменные, а черным константы. Внизу: DT визуализация той же сети, что и обычное дерево решений. Дроби указывают маршрут случайно выбранных 6 классифицируемых экземпляров.

3.3Обучение дерева

С помощью описанного выше метода мы можем направлять входные экземпляры в конечные узлы и классифицировать их. Таким образом, обучение дерева решений теперь становится вопросом обученияв узловыхточкахсрезаи листьевклассификаторов. Поскольку все шаги нашего прямого прохода дифференцируемы, все параметры (Рис. 2, Красный) теперь могут бытьнапрямуюи одновременно обучены с помощью SGD.

Обсуждение. DNDT хорошо масштабируется с количеством экземпляров благодаря мини-пакетному обучению в стиле нейронной сети. Однако ключевым недостатком этогостилядо сих пор является то, что из-за использования продуктаKroneckerон не масштабируется по количеству функций. В нашей текущей реализации мы избегаем этой проблемы с "широкими" наборами данных, обучаялесслучайногоподпространства(Ho, 1998 [13]) - за счет нашей интерпретируемости. То есть вводится несколько деревьев, каждое из которых обучается на случайном подмножестве признаков. Лучшим решением, которое не требует неинтерпретируемоголеса, является использование разреженности конечногоразделения на ячейкиво время обучения: количество непустых листьев растет намного медленнее, чем общее количество листьев. Но это несколько усложняет простую в остальном реализацию DNDT.

4.Эксперименты

4.1Реализация

DNDT концептуально прост и легок в реализации с помощью 20 строк кода вTensorFlowилиPyTorch. Поскольку он реализован как нейронная сеть, DNDT поддерживает "из коробки" ускорение GPU и мини-пакетное обучение наборов данных, которые не помещаются в память, благодаря современным фреймворкам глубокого обучения.

4.2Наборы данных и конкуренты

Мы сравниваем DNDT с нейронными сетями (реализованнымиTensorFlow(Abadietal., 2015) [1]) и деревом решений (отScikit-learn(Pedregosaetal., 2011 [22])) на 14 наборах данных, собранных изKaggleи UCI (подробности набора данных см. В табл. 1).

Для базовой линии дерева решений (DT) мы установили два ключевых критериягиперпараметров: критерий'gini' иразделитель 'best'. Для нейронной сети (NN) мы используем архитектуру из двух скрытых слоев по 50 нейронов в каждом для всех наборов данных. DNDT также имеетгиперпараметр-количество точек среза для каждого объекта (коэффициент ветвления), который мы устанавливаемравным1 для всех объектов и наборов данных. Подробный анализ эффекта этогогиперпараметраможно найти в разделе 4.4.Длянаборовданных с более чем 12 признаками,мы используем ансамбль DNDT, где каждое дерево выбирает 10 признаков случайным образом, и у нас есть 10уровнейв общей сложности. Окончательный прогноз дается большинством голосов.

4.3Точность

Мы оцениваем производительность DNDT, дерева решений инейросетевыхмоделей на каждом из наборов данных в Табл. 1. точность тестового набора представлена в Табл.2.

В целом наиболее эффективной моделью является DT. Хорошая производительность DT неудивительна, поскольку эти наборы данных в основном табличные, а размерность объектов относительно невелика.

Таблица 1. Коллекция из 14 наборов данных от Kaggle (обозначается буквой (K)) и UCI: количество экземпляров (#inst.), количество объектов (#feat.) и количество классов (#cl.)Таблица 2. Точность тестового набора каждой модели: DT: дерево решений. NN: нейронная сеть. DNDT: наше глубокое нейронное дерево решений, где ( * ) указывает, что используется ансамблевая версия.

Условно говоря, нейронные сети не имеют явного преимущества в отношении такого рода данных. Однако DNDT немного лучше, чемванильнаянейронная сеть, так как она ближе к дереву решений попостроению. Конечно, это только ориентировочный результат, так как все эти модели имеют настраиваемыегиперпараметры. Тем не менее интересно, что ни одна модель не обладает доминирующим преимуществом. Это напоминает теоремы об отсутствиибесплатного обеда(Wolpert, 1996[27]).

4.4Анализ активных точек среза

В DNDT количество точек среза на объект является параметром сложности модели. Мы не связываем значения точек среза, а это значит, что некоторые из них неактивны, например, они либо меньше минимальногоx_d, либо больше максимальногоx_d.

В этом разделе мы исследуем, сколько точек среза фактически используется после обучения DNDT. Точка среза активна, когда по крайней мере один экземпляр из набора данных попадает на каждую ее сторону. Для четырех наборов данных-CarEvaluation,Pima,IrisиHabermanмы устанавливаем количество точек среза на объект от 1 до 5 и вычисляем процент активных точек среза, как показано на рис. 3.Видно, что по мере увеличения числа точек среза их использование в целом уменьшается. Это означает, что DNDT несколько саморегулируется: он не использует все доступные ему параметры.

Рисунок 3. Доля (%) активных точек, используемых DNDT.

Мы можем дополнительно исследовать, как количество доступных точек среза влияет на производительность этих наборов данных. Как видно из Рис. 4, производительность первоначально увеличивается с увеличением числа точек среза, а затем стабилизируется после определенного значения. Это обнадеживает, потому что это означает, что большие DNDT не слишком подходят к данным обучения, даже без явной регуляризации.

Рисунок 4. Точность тестирования DNDT для увеличения числа точек разреза (сложность модели).

4.5Анализ активных признаков

При обучении DNDT также возможно, что для определенного объекта все точки среза неактивны. Это соответствует отключению функции, чтобы она не влияла на прогнозирование,аналогично обычному ученику DT, который никогда не выбирает данную функцию, чтобызадать узел-распознавательв любом месте дерева. В этом разделе мы анализируем, как DNDT исключает функции таким образом. Мы запускаем DNDT 10 раз и записываем,сколькораз данный объект исключаетсяиз-за того,что все его точки среза неактивны.

Учитывая случайностьчерезинициализируемыевесадлямини-пакетнойвыборки, мы наблюдаем, что некоторые функции (например, функция индекса 0 вiris) последовательно игнорируются DNDT (см. табл. 3 для всех результатов). Это говорит о том, что DNDT делает некоторый неявныйвыбор объектов, выталкивая точки отсечениязаграницы данных для несущественных объектов. В качестве побочного продукта мы можем получить меру важности(веса)функции изнаборафункции в течение нескольких запусков: чем больше функция игнорируется, тем менее важной она, вероятно,ибудет.

Таблица 3. Процент ( % ) случаев, когда DNDT игнорирует каждую функцию

4.6Сравнение с деревом решений

Используя методы, разработанные в разделе 4.5, мы исследуем, благоприятствуют ли DNDT и DTсосходнымихарактеристиками. Мы сравниваем важность признака черезкритерийgini (Джини), используемыйв дереве решений (Рис. 5), с нашей метрикой скорости отбора (табл.3).

Рисунок 5. Рейтинг важности характеристик, произведенный DT (Gini).

Сравнивая эти результаты, мы видим, что иногда DNDT и DT предпочитаютвыбор признаков, например, дляIrisони оба оценивают Признак 3 как наиболее важный. Но бывает, что они также могут иметь разные взгляды, например, дляХаберманаDT выбрал функцию 0 как наиболее важную, тогда как DNDT полностью проигнорировал ее. На самом деле DNDT использует только функцию 2 для прогнозирования, которая занимает второе место поDT.Однако такого рода разногласия не обязательно могут привести к существенным различиям в производительности. Как видно из Табл. 2, дляХаберманаточность испытаний DNDT и DT составляет 70,9% и 66,1% соответственно.

Наконец, мы количественно оцениваем сходстворанжированийпризнаков DNDT и признаков DT, вычисляяTauкритерияКендаллаподвумрейтинговымспискам. Результаты, приведенные в Табл.4, свидетельствуют об умеренной корреляции в целом.

Таблица 4. Рейтинг функций DNDT и DT по Кендаллу: большие значения означают большее сходство.

4.7Ускорение GPU

Наконец, мы проверяем легкость ускорения обучения DNDT с помощью обработки графическим процессором - возможность, которая не является обычной или простойдля DT. Увеличивая количество точек отсечения для каждой функции, мы можем получить более крупные модели, для которых режим графического процессора имеет значительно меньшее время работы (см. Рис. 6).

Рисунок 6. Иллюстрация ускорения GPU: время обучения DNDT включено. 3,6 ГГц CPU против GTX Titan GPU. В среднем за 5 прогонов.

5.Заключение

Мы представили древовидную модель на основе нейронной сети DNDT. Он имеет лучшую производительность, чем NN для определенных наборов табличных данных, при этом обеспечиваетинтерпретируемое дерево решений. Между тем, по сравнению с обычными DT, DNDT проще в реализации, одновременно выполняет поиск в древовидной структуре и параметрах с помощью SGD и легко ускоряется на GPU. Есть много возможностей для будущей работы. Мы хотим исследовать источник наблюдаемой нами саморегуляции; изучить подключение DNDT как модуля, подключенного к обычному элементу обучения CNN, для сквозного обучения; выяснить, можно ли использовать обучение на основе SGD целого дерева DNDT в качестве постобработки для точной настройки обычных,жаднообученных DT и повышения ихпроизводительности; выяснить, можно ли использовать многие подходы кадаптивномуобучению на основе NN для обеспечения возможности переносаобучения для DT.

Ссылки