Участник:Tolstikhin/Песочница

Материал из MachineLearning.

< Участник:Tolstikhin(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Введение. == В этой статье будeт рассматриватьтся задача поиска совместной подсистемы максимальног...)
(Параметры решающих деревьев.)
 
(43 промежуточные версии не показаны)
Строка 1: Строка 1:
-
== Введение. ==
+
Решающие деревья - разделение объектов.
-
В этой статье будeт рассматриватьтся задача поиска совместной подсистемы максимального веса
+
В этой статье будет рассмотрен один из возможных вариантов настройки бинарных решающих деревьев, основанный на
-
для систем линейных уравнений и неравенств (''Maximum feasible subsystem problem'').
+
''разделении объектов''.
-
Вначале будут введены общие определения и приведены некоторые результаты касательно сложности решения данной задачи.
+
Будет рассматриваться задача классификации с двумя классами в n-мерном пространстве объектов.
-
Дальше будут сформулированы вспомогательные утверждения, на основе которых мы сможем построить эффективный алгоритм
+
-
решающий задачу..
+
-
Изложение алгоритма будет сопровождаться численными примерами его работы.
+
Напомним, что задачей настройки является получение параметров модели на основе обучающей выборки <tex>X^l</tex>.
-
== Постановка задачи. ==
+
== Метод разделения объектов ==
-
Пусть задана произвольная ''несовместная'' система линейных неравенств вида
+
Для описания метода разделения объектов для начала введём понятие ''отступа'' объектов обучающей выборки.
-
<tex>a_{i_1}x_1+\dots+a_{i_n}x_n\leq b_i,\ i=1,2,\dots,m,</tex> (1)
+
Предположим, что мы имеем алгоритм классификации вида <tex>a(x)=arg\max_{y\in Y}G_y(x)</tex>, где x - классифицирумый объект, y - класс из множества
 +
классов Y, а <tex>G_y(x)</tex> - ключевая величина, являющаяся оценкой принадлежности объекта x классу y. В этом случае ''отступом'' обекста <tex>x_i\in X^l</tex>
 +
назовём величину <tex>M(x_i)=G_{y_i}(x_i)-\max_{y\in Y\setminus y_i}G_y(x_i)</tex>. Здесь <tex>y_i</tex> - класс, которому принадлежит объект обучающей выборки
 +
<tex>x_i</tex>.
 +
Грубо говоря, отсупом объекта является ''расстояние'' от него до границы, отделяющей объекты ''своего'' класса, от всех остальных.
-
где <tex>a_{i_j},b_i</tex> - конечные действительные числа, числа m и n фиксированы.
+
Понятие отступа лежит в основе метода разделения объектов. Его идеей является максимизация отступа объектов обучающей выборки. Интуитивно ясно, что
-
За исходную задачу примем нахождение совместной подсистемы данной системы, имеющей максимальную мощность (МСП).
+
чем больше отступы объектов, тем надёжнее будет классификация, поскольку это означает, что есть достаточно большой ''зазор'' между двумя классами.
-
В случае системы равенств заменим каждое из равенств
+
== Параметры решающих деревьев. ==
-
<tex>a_{i_1}x_1+\dots+a_{i_n}x_n = b_i</tex>
+
При построении решающих деревьев основными параметрами являются предикаты <tex>\phi_i(x)</tex>, соответствующие узлам деревьев, классы, приписанные терминальным вершинам и структура самого дерева.
 +
Под структурой в данном случае понимаются свойства дерева, как графа - его высота, число узлов, сбалансированность и так далее.
-
на два неравенства
+
== Настройка параметров решающих деревьев методом разделения объектов. ==
-
<tex>a_{i_1}x_1+\dots+a_{i_n}x_n\leq b_i,</tex>
+
Как мы знаем, алгоритм классификации, реализуемый бинарными решающими деревьями, может быть записан в виде простого голосования конъюнкций:
-
<tex>a_{i_1}x_1+\dots+a_{i_n}x_n\beq b_i.</tex>
+
:<tex>a(x)=arg\max_{y\in Y}\sum_{v\in T\\c_v=y}K_v(x)</tex>.
-
Тем самым мы сведём задачу к исходной.
+
Поясним буквы, входящие в эту фурмулу.
-
(Строгое обоснование этого сведения будет приведено в разделе "Точное решение задачи. Алгоритм 1.")
+
y - по-прежнему класс из множества классов Y. T - множество терминальных (листовых) вершин бинарного дерева, V - вершина дерева, а <tex>c_v</tex> -
 +
класс, соответствующий терминальной вершине v. <tex>K_v(x)</tex> - конъюнкция всех предикатов на пути от корня дерева к терминальной вершине v.
-
Данная задача часто возникает при решении различных математических задач - в том числе при решении
+
Понятно, что напрямую воспользоваться методом разделения объектов в данном случае не получается, поскольку из всех конъюнкций, учавствующих в сумме,
-
задач прогнозирования и распознавания.
+
при фиксированном объекте ровно одна принимает значение 1.
-
Примером может служить разделение объектов 2х классов обучающей выборки
+
Мы немного изменим подход и будем использовать метод разделения объектов для настройки предикатов решающего дерева.
-
гиперплоскостью.
+
-
В случае, когда эту задачу не удаётся решить точно, мы хотим провести
+
-
гиперплоскость так, чтобы она допускала минимальное число ошибок.
+
-
== Сложность задачи. ==
+
За основу синтеза решающего дерева взят жадный алгоритм, описанный в лекции [1] К.В. Воронцова.
-
'''Задача выделения максимальной совместной подсистемы является NP-сложной'''. ([2])
+
=== Настройка предикатов. ===
-
Посчитаем приблизительно сложность ''простого перебора''.
+
В каждом узле дерева предлагается строить предикаты вида <tex>\phi(x)=[f_n(x)\leq a]</tex>, где <tex>f_n(x)</tex> - n-ый признак объекта х.
 +
Мы хотим найти одномерное разбиение объектов (по одной координате), которое будет соответствовать максимальным отступам объектов части обучающей выборки,
 +
попавшей в данный узел.
 +
В данном случае в качестве оценки принадлежности объекта x к классу y можно взять величину <tex>y(x-a)</tex>, если условиться, что у нас
 +
2 класса - <tex>Y=\{1,-1\}</tex>. (При этом в каждом узле элементы класса, среднее значение рассматриваемой координаты которого больше, помечать классом 1,
 +
а элементы второго класса - классом -1.)
-
Всего подсистем <tex>2^m-1</tex>.
+
Максимизация отступов в пределах одного признака сводится к нахождению такого a, что величины расстояний от элементов обучающей выборки до границы a, взятые
-
Каждую подсистему надо проверить на совместность.
+
с соответствующими знаками, максимальны. Как варианты можно максимизировать минимальный из отступов или сумму отступов по всем объектам.
-
Например, методы, упомянутые в [1], требуют для определения совместности подсистемы, состоящей из
+
После этого остаётся максимизировать отступ по номеру признака - и мы имеем предикат <tex>\phi(x)=[f_n(x)<=a]</tex>.
-
<tex>l</tex> неравенств и имеющей ранг <tex>r</tex>,
+
-
<tex>\left(^l_r\right)\left(^n_r\right)O((l-r)r^3)</tex> операций.
+
-
Понятно, что на практике данный метод не годится.
+
Стоит отметить, что выбранный вид предиката осуществляет разбиение выборки на прямоугольники со сторонами параллельными осям координат.
-
Также существует другой подход к получению точного решения.
+
=== Настройка формы дерева. ===
-
Произвольный булевый вектор <tex>(\alpha_1,...,\alpha_m)</tex> однозначно определяет подсистему <tex>Sub_{\alpha}</tex>
+
Форма дерева настраиватся автоматически при синтезе решающего дерева жадным алгоритмом.
-
системы 1.
+
Мы будем рекурсивно в каждой вершине дерева делить часть обучающей выборки, попавшую в данный узел, получать предикаты описанным образом и наращивать
-
<tex>i</tex>-е неравенство входит в подсистему <tex>Sub_{\alpha}</tex> тогда и только тогда, когда <tex>\alpha_i=1</tex>.
+
сыновей вершины, если это надо. Причём условимся, что правым сыновьям вершины будут соответствовать объекты, на которых предикат принял значение 0,
 +
а левым - на которых принял значение 1.
 +
Так мы будем действовать до тех пор, пока в какую-то из вершин не придут элементы, все принадлежащие классу y. Эту
 +
терминальную Вершину мы пометим классом y и закончим наращивание.
-
Введём булеву функцию <tex>g</tex> на <tex>m</tex>-мерном булевом кубе, принимающую единицу на тех и только тех наборах
+
После жадного алгоритма можно применять различные эвристики и методы, позволяющие упростить форму дерева, такие как редукция, пост-редукция, заглядывание вперёд
-
<tex>\alpha</tex>, которые соответствуют несовместным системам <tex>Sub_{\alpha}</tex>.
+
и так далее.
-
Очевидно, что такая булева функция монотонна.
+
-
Исходная задача сводится к поиску максимального верзнего нуля монотонной функции <tex>g</tex>.
+
-
В книге [1] есть ссылка на алгоритм, решающий эту задачу.
+
-
В худшем случае он делает <tex>\left(2^m/sqrt{m}\right)</tex> шагов, где шаг - вычисление одного значения функции g.
+
-
Этот подход немного ускоряет решение задачи, но по-прежнему работает слишком медленно.
+
== Реализация жадного алгоритма и оптимизация отступов. ==
-
Предлагагается более эффективный метод решения исходной задачи.
+
В рамках изучения вопроса настройки решающих деревьев был написан код программы, реализующей настройку методом разделения объектов, в основу которой лёг
 +
жадный алгоритм синтеза деревьев.
-
== Точное решение задачи. Алгоритм 1. ==
+
Для настройки предикатов и оптимизации отступа по выбранному признаку проводилось несколько этапов. Сначала сортировкой пузырька сортировался массив значений
 +
выбранного признака у объектов. Далее составлялся набор ''узловых'' точек, которые в дальнейшем использовались в качестве значения порога. Эти точки выбирались посередине
 +
между двумя соседними значениями признака в отсортированном массиве. После этого применялся полный пребор по найденным ''узловым'' точкам.
-
=== Вспомагательные определения и утверждения. ===
+
Жадный алгоритм реализовывался без досрочных остановов (использующихся для повышения надёжности классификации) и без дальнейших упрощений вида дерева.
-
По-прежнему будем рассматривать систему 1.
 
-
Допустим, что она совместна и имеет ранг <tex>r</tex>.
 
-
'''Определение 1.''' Решение системы 1 - ''узловое'', если оно обращает в равенства какие-нибудь <tex>r</tex> её
 
-
неравенств с линейно независимыми левыми частями.
 
-
'''Определение 2.''' Подсистема системы 1 - ''крайняя'', если, во-первых, её ранг больше нуля и равен числу неравенств в ней,
+
== Список литературы ==
-
во-вторых, хотя бы одно её узловое решение удовлетворяет системе 1.
+
-
'''Определение 3.''' Крайняя подсистема - ''узловая подсистема'', если все её узловые решения удовлетворяют системе 1.
+
[1] К.В. Воронцов, "Логические алгоритмы классификации", лекция, 2007.
-
 
+
[2] K. Bennett, N. Cristianini, J. Shawe-Taylor, D. Wu. "Enlarging the margin in perceptron
-
'''Свойство 1.''' Крайняя подсистема тогда и только тогда является узловой подсистемой системы 1, когда её ранг
+
decision trees", Machine Learning, 2000.
-
совпадает с рангом <tex>r</tex> системы 1.
+
-
 
+
-
'''Теорема 1.''' Каждая совместная система линейных неравенств вида 1 отличного от нуля ранга имеет хотя бы одну узловую
+
-
подсистему, а значит, хотя бы одно узловое решение.
+
-
 
+
-
С помощью этих утверждений доказывается основная лемма, на которой держится следующий алгоритм.
+
-
 
+
-
'''Лемма.''' Ранг максимальной совместной подсистемы совпадает с рангом всей системы.
+
-
 
+
-
=== Изложение алгоритма 1. ===
+
-
 
+
-
Алгоритм будет выглядеть следующим образом.
+
-
Будем перебирать одну за другой подсистемы мощности и ранга <tex>r</tex> для данной несовместной системы 1
+
-
ранга <tex>r</tex>.
+
-
Среди них обязательно найдутся все узловые подсистемы для искомой МСП, так как по лемме ранг МСП равен <tex>r</tex>.
+
-
Из определения следует, что все узловые решения любой узловой подсистемы МСП удовлетворяют всей МСП.
+
-
Это означает, что достаточно найти хотя бы одно узловое решение любой узловой подсистемы МСП и подставить его в систему 1,
+
-
чтобы выделить саму МСП.
+
-
Таким образом мы заменяем все неравенства в найденной подсистеме на равенства и находим решение полученной
+
-
системы уравнений (в случае бесконечного числа решений - достаточно найти одно).
+
-
Затем мы подставляем полученное решение в исходную систему 1 и выделяем те неравенства, которым удовлетворяет полученное
+
-
решение.
+
-
Эти неравенства образуют некую совместную подсистему системы 1.
+
-
В какой-то момент мы найдём одну из узловых подсистем МСП и выделим МСП.
+
-
 
+
-
Трудность заключается в том, что мы не знаем какая из подсистем является узловой для МСП.
+
-
Поэтому приходится перебирать все подсистемы мощности и ранга <tex>r</tex> и находить одно их узловое решение.
+
-
Затем выделять по узловому решению подсистему, соответствующую ему.
+
-
Сравнивая мощности всех систем, полученных таким путём, мы найдём МСП. Также мы найдём одно его решение.
+
-
 
+
-
=== Сложность алгоритма ===
+
-
 
+
-
Общее число операций приведённого алгоритма оценивается сверху выражением:
+
-
 
+
-
::<tex>K_1mn^2+\left(^m_r\right)\left(K_2nr^2+K_3mn\right),
+
-
 
+
-
где <tex>K_1,K_2,K_3</tex> - некоторые действительные числа.
+
-
 
+
-
''Краткое обоснование полученной оценки.''
+
-
Предположим, что <tex>n < m</tex>.
+
-
Вычисление ранга <tex>r</tex> матрицы исходной системы 1 требует <tex>O(mn^2)</tex> операций
+
-
(приведение к треугольному виду). Число подсистем мощности <tex>r</tex> в системе 1 - <tex>\left(^m_r\right)</tex>.
+
-
Для найденной подсистемы ранга <tex>r</tex> нахождение одного узлового решения занимает <tex>O(r^2)</tex> операций.
+
-
Подстановка найденного решения во все неравенства системы 1 - <tex>O(mn)</tex> операций.
+
-
 
+
-
Эта оценка уже гораздо лучше оценки для полного перебора.
+
-
К сожалению алгоритм всё ещё остаётся неподъёмным на практике при больших значениях <tex>n</tex> и <tex>m</tex>.
+
-
 
+
-
== Приближённое решение задачи. Алгоритм 2. ==
+
-
 
+
-
Точное решение задачи выделения максимальной совместной подсистемы - NP-полная задача.
+
-
 
+
-
Однако, если отказаться от нахождения точной МСП и ограничиться нахождением ''приближённой'' МСП, задачу можно решить
+
-
за полиномиальное время.
+
-
Основная идея - перебирать не всевозможные подсистемы ранга и мощности <tex>r</tex>, а только часть из них.
+
-
 
+
-
Дело в том, что для нахождения точного решения нам достаточно ''наткнуться'' хотя бы на одну узловую подсистему МСП.
+
-
При малом числе переменных и большом числе неравенств в системе 1 можно рассчитывать на то, что МСП имеет большое число
+
-
узловых подсистем.
+
-
А значит мы с большой вероятностью ''наткнёмся'' на неё.
+
-
В противном случае мы не рассмотрим ни одну из узловых подсистем МСП и получим неточное решение.
+
-
 
+
-
Одна из возможных реализаций неполного перебора, приведённая в [1], представлена ниже.
+
-
 
+
-
=== Изложение алгоритма 2. ===
+
-
 
+
-
По-прежнему пытаемся найти МСП несовместной системы 1 ранга <tex>r</tex>.
+
-
Как и выше каждая подсистема определяется вектором <tex>v=(v_1,...,v_r)</tex>.
+
-
Введём вспомогательные переменные:
+
-
 
+
-
<tex>s</tex> - номер строящейся "ветви" множества подсистем;
+
-
 
+
-
<tex>t</tex> - номер текущего неравенства в подсистеме, <tex>1\leq t \leq r</tex>;
+
-
 
+
-
<tex>p</tex> - параметр перехода к одному из '''этапов''' алгоритма. <tex>p \in \{-1,0,1\}</tex>.
+
-
 
+
-
<tex>h</tex> - параметр алгоритма.
+
-
 
+
-
Алгоритм выглядит следующим образом.
+
-
 
+
-
'''Инициализация переменных:'''
+
-
<tex>s=1, p=1, v_1=1, t=2</tex>.
+
-
 
+
-
'''Этап 1 (<tex>p=1</tex>)'''
+
-
 
+
-
<tex>v_t:=v_{t-1}+1</tex>;
+
-
+
-
Если(<tex>v_t>m</tex>)
+
-
 
+
-
::<tex>t:=t-1, p=-1</tex>;
+
-
 
+
-
Иначе
+
-
 
+
-
{
+
-
 
+
-
::Если(<tex>t<r</tex>)
+
-
 
+
-
::::<tex>t:=t+1,p=1</tex>;
+
-
 
+
-
::Если(<tex>t==r</tex>)
+
-
 
+
-
::::{построили очередную подсистему.
+
-
 
+
-
::::обрабатываем её.
+
-
 
+
-
::::<tex>p:=0</tex>}
+
-
 
+
-
}
+
-
 
+
-
'''Этап 2 (<tex>p=0</tex>)'''
+
-
 
+
-
<tex>v_t:=v_t+h</tex>;
+
-
 
+
-
Если(<tex>v_t>m</tex>)
+
-
 
+
-
::<tex>t:=t-1, p=-1</tex>;
+
-
 
+
-
Иначе
+
-
 
+
-
::{построили очередную подсистему.
+
-
 
+
-
::обрабатываем её.
+
-
 
+
-
::<tex>p:=0</tex>}
+
-
 
+
-
'''Этап 3 (<tex>p=-1</tex>)'''
+
-
 
+
-
Если(<tex>t\neq 1</tex>)
+
-
 
+
-
{
+
-
 
+
-
::<tex>v_t:=v_t+h</tex>;
+
-
 
+
-
::Если(<tex>v_t>m</tex>)
+
-
 
+
-
::::<tex>t:=t-1</tex>;
+
-
 
+
-
::Иначе
+
-
 
+
-
::::<tex>t:=t+1, p=1</tex>;
+
-
 
+
-
}
+
-
 
+
-
Если (<tex>t==1</tex>)
+
-
{
+
-
::<tex>s:=s+1</tex>;
+
-
 
+
-
::<tex>v_1:=s</tex>;
+
-
 
+
-
::Если(<tex>v_1>m</tex>) '''возврат''';
+
-
 
+
-
::Иначе <tex>t=2, p=1</tex>
+
-
}
+
-
 
+
-
Уменьшая параметр <tex>h</tex> мы увеличиваем мощность перебираемых подсистем.
+

Текущая версия

Решающие деревья - разделение объектов.

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

Напомним, что задачей настройки является получение параметров модели на основе обучающей выборки X^l.

Содержание

Метод разделения объектов

Для описания метода разделения объектов для начала введём понятие отступа объектов обучающей выборки.

Предположим, что мы имеем алгоритм классификации вида a(x)=arg\max_{y\in Y}G_y(x), где x - классифицирумый объект, y - класс из множества классов Y, а G_y(x) - ключевая величина, являющаяся оценкой принадлежности объекта x классу y. В этом случае отступом обекста x_i\in X^l назовём величину M(x_i)=G_{y_i}(x_i)-\max_{y\in Y\setminus y_i}G_y(x_i). Здесь y_i - класс, которому принадлежит объект обучающей выборки x_i. Грубо говоря, отсупом объекта является расстояние от него до границы, отделяющей объекты своего класса, от всех остальных.

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

Параметры решающих деревьев.

При построении решающих деревьев основными параметрами являются предикаты \phi_i(x), соответствующие узлам деревьев, классы, приписанные терминальным вершинам и структура самого дерева. Под структурой в данном случае понимаются свойства дерева, как графа - его высота, число узлов, сбалансированность и так далее.

Настройка параметров решающих деревьев методом разделения объектов.

Как мы знаем, алгоритм классификации, реализуемый бинарными решающими деревьями, может быть записан в виде простого голосования конъюнкций:

a(x)=arg\max_{y\in Y}\sum_{v\in T\\c_v=y}K_v(x).

Поясним буквы, входящие в эту фурмулу. y - по-прежнему класс из множества классов Y. T - множество терминальных (листовых) вершин бинарного дерева, V - вершина дерева, а c_v - класс, соответствующий терминальной вершине v. K_v(x) - конъюнкция всех предикатов на пути от корня дерева к терминальной вершине v.

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

За основу синтеза решающего дерева взят жадный алгоритм, описанный в лекции [1] К.В. Воронцова.

Настройка предикатов.

В каждом узле дерева предлагается строить предикаты вида \phi(x)=[f_n(x)\leq a], где f_n(x) - n-ый признак объекта х. Мы хотим найти одномерное разбиение объектов (по одной координате), которое будет соответствовать максимальным отступам объектов части обучающей выборки, попавшей в данный узел. В данном случае в качестве оценки принадлежности объекта x к классу y можно взять величину y(x-a), если условиться, что у нас 2 класса - Y=\{1,-1\}. (При этом в каждом узле элементы класса, среднее значение рассматриваемой координаты которого больше, помечать классом 1, а элементы второго класса - классом -1.)

Максимизация отступов в пределах одного признака сводится к нахождению такого a, что величины расстояний от элементов обучающей выборки до границы a, взятые с соответствующими знаками, максимальны. Как варианты можно максимизировать минимальный из отступов или сумму отступов по всем объектам. После этого остаётся максимизировать отступ по номеру признака - и мы имеем предикат \phi(x)=[f_n(x)<=a].

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

Настройка формы дерева.

Форма дерева настраиватся автоматически при синтезе решающего дерева жадным алгоритмом. Мы будем рекурсивно в каждой вершине дерева делить часть обучающей выборки, попавшую в данный узел, получать предикаты описанным образом и наращивать сыновей вершины, если это надо. Причём условимся, что правым сыновьям вершины будут соответствовать объекты, на которых предикат принял значение 0, а левым - на которых принял значение 1. Так мы будем действовать до тех пор, пока в какую-то из вершин не придут элементы, все принадлежащие классу y. Эту терминальную Вершину мы пометим классом y и закончим наращивание.

После жадного алгоритма можно применять различные эвристики и методы, позволяющие упростить форму дерева, такие как редукция, пост-редукция, заглядывание вперёд и так далее.

Реализация жадного алгоритма и оптимизация отступов.

В рамках изучения вопроса настройки решающих деревьев был написан код программы, реализующей настройку методом разделения объектов, в основу которой лёг жадный алгоритм синтеза деревьев.

Для настройки предикатов и оптимизации отступа по выбранному признаку проводилось несколько этапов. Сначала сортировкой пузырька сортировался массив значений выбранного признака у объектов. Далее составлялся набор узловых точек, которые в дальнейшем использовались в качестве значения порога. Эти точки выбирались посередине между двумя соседними значениями признака в отсортированном массиве. После этого применялся полный пребор по найденным узловым точкам.

Жадный алгоритм реализовывался без досрочных остановов (использующихся для повышения надёжности классификации) и без дальнейших упрощений вида дерева.


Список литературы

[1] К.В. Воронцов, "Логические алгоритмы классификации", лекция, 2007. [2] K. Bennett, N. Cristianini, J. Shawe-Taylor, D. Wu. "Enlarging the margin in perceptron decision trees", Machine Learning, 2000.

Личные инструменты