Санкт-Петербургский государственный университет
Прикладная математика и информатика
Исследование операций и принятие решений в задачах оптимизации,
управления и экономики
Мирошниченко Никита
Самообучающиеся системы и их
приложения
Бакалаврская работа
Научный руководитель:
д. ф.-м. н., профессор Романовский И. В.
Рецензент:
доцент Машарский С. М.
Санкт-Петербург
2016
SAINT-PETERSBURG STATE UNIVERSITY
Applied Mathematics and Computer Science
Operation Research and Decision Making in Optimisation, Control and
Economics Problems
Nikita Miroshnichenko
Self-learning systems and their applications
Graduation Thesis
Scientific supervisor:
Dr. Sci., Professor Joseph V. Romanovsky
Reviewer:
Associate Professor Sergey M. Masharsky
Saint-Petersburg
2016
Оглавление
Введение
4
1. Основные понятия
5
2. Метрические методы классификации
2.1. Метод ближайшего соседа. . . . . . . . . . . . . . .
2.2. Алгоритм k ближайших соседей. . . . . . . . . . .
2.3. Метод парзеновского окна. . . . . . . . . . . . . . .
2.4. Метод потенциальных функций . . . . . . . . . . .
2.5. Отбор эталонных объектов. . . . . . . . . . . . . .
2.6. Применение метрических методов классификации
.
.
.
.
.
.
7
8
8
9
10
11
12
3. Линейные классификаторы
3.1. Метод стохастического градиента . . . . . . . . . . . . . .
3.2. Применение линейных классификаторов. . . . . . . . . .
14
16
18
4. Линейные композиции. Бустинг
4.1. Композиция алгоритмов . . . . . . . . . . . . . . . . . . .
4.2. Градиентный бустинг для произвольной функции потерь
4.3. Применение градиентного бустинга . . . . . . . . . . . . .
19
19
20
22
Заключение
23
Список литературы
24
5. Приложения
5.1. Приложение 1: метрический классификатор . . . . . . . .
5.2. Приложение 2: линейный классификатор . . . . . . . . .
5.3. Приложение 3: градиентный бустинг . . . . . . . . . . . .
25
25
26
27
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Введение
Мы живем в век информации: нас окружает огромное количество
данных, которые создаются ежесекундно, просто кликом по ссылке. Таким образом, возникает важная задача анализа данных. Машинное обучение занимается этой дисциплиной.
Машинное обучение — обширный подраздел искусственного интеллекта, математическая дисциплина, использующая разделы математической статистики, численных методов оптимизации, теории вероятностей, дискретного анализа, и извлекающая знания из данных. Имеется
множество объектов (ситуаций) и множество возможных ответов (откликов, реакций). Существует некоторая зависимость между ответами
и объектами, но она неизвестна. Известна только конечная совокупность прецедентов — пар «объект, ответ», называемая обучающей выборкой. На основе этих данных требуется восстановить зависимость, то
есть построить алгоритм, способный для любого объекта выдать достаточно точный ответ. [2]
Эта область заинтересовала меня уже давно, так как имеет большое приложение в реальной жизни и позволяет делать многие вещи
проще. Поэтому я решил изучить эту тему более детально. К действию
меня побудил конкурс, который проводила компания «Билайн». Были
предложены обезличенные данные по пятидесяти тысячам пользователей, состоящие из идентификатора и шестидесяти переменных, которые
необходимо было связать с возрастной группой пользователей и проверить эту зависимость на тестовой выборке. На мой взгляд, довольно
интересная задача, для решения которой нужно изучить основные направления машинного обучения и существующие инструменты. В данной работе будет предпринята попытка решить эту задачу и сравнить
результаты с конкурсными.
4
1. Основные понятия
Задано множество объектов X, множество допустимых ответов Y ,
и существует целевая функция y ∗ : X→Y , значения которой yi = y ∗ (xi )
известны только на конечном подмножестве объектов {x1 . . . xl } ⊂ X.
Пары «объект–ответ» (xi , yi ) называются прецедентами. Совокупность
пар X l = (xi , yi )li=1 называется обучающей выборкой.
Задача обучения по прецедентам заключается в том, чтобы по выборке X l восстановить зависимость y ∗ , то есть построить решающую
функцию a : X→Y , которая приближала бы целевую функцию y ∗ (x),
причём не только на объектах обучающей выборки, но и на всём множестве X.
Решающая функция a должна допускать эффективную компьютерную реализацию, по этой причине будем называть её алгоритмом.
Также необходимо уточнить тип решаемой задачи. В зависимости
от природы множества допустимых ответов Y задачи обучения по прецедентам делятся на следующие типы.
Если Y = {1, . . . , M }, то это задача классификации на M непересекающихся классов. В этом случае всё множество объектов X разбивается
на классы Ky = x ∈ X : y ∗ (x) = y, и алгоритм a (x) должен давать ответ
на вопрос ”какому классу принадлежит x?”.
Если Y = R, то это задача восстановления регрессии, то есть в
качестве ответа нужно предъявить функцию.
Метод обучения — это отображение µ : (X×Y )l →A, которое произвольной конечной выборке X l = (xi , yi )li=1 ставит в соответствие некоторый алгоритм a ∈ A. Говорят, что метод µ строит алгоритм a по
выборке X l . [3]
Встает проблема оценки построенного алгоритма. Для этого введем
следующее понятие.
Функция потерь — это неотрицательная функция L (a, x), характеризующая величину ошибки алгоритма a на объекте x. Если L (a, x) = 0,
то ответ a (x) называется корректным.
5
Функционал качества алгоритма a на выборке Xl :
(
Q a, X
l
)
1∑
L (a, xi ) .
=
l i=1
l
Основной задачей является минимизация функционала качества алгоритма для выборки, то есть в заданной модели необходимо найти такой алгоритм , что фукционал Q принимает на нем свое минимальное
значение для заданной обучающей выборки X l :
( )
(
)
µ X l = argmin Q a, X l .
a∈A
Однако необходимо понимать, что существует риск переобучения на
тренировочной выборке — качество работы алгоритма на объектах, не
вошедших в нее, может оказаться существенно хуже. Построенный алгоритм может быть слишком сильно привязан к обучающей выборке,
поэтому для успешной работы метод должен уметь обобщать данные.
Теперь, когда мы ввели необходимые определения, рассмотрим некоторые методы машинного обучения.
6
2. Метрические методы классификации
При рассмотрении таких сложных объектов, как фотографии, временные ряды, подписи, мы обнаруживаем, что сравнивать их между
собой выгоднее и проще, чем изобретать признаки и сравнивать признаковые описания. Действительно, если мера сходства подобрана удачно,
то зачастую оказывается, что схожим объектам очень часто соответствуют схожие объекты. Если формализовать это высказывание: классы образуют компактно локализованные подмножества. Это предположение принято называть гипотезой компактности. Для того, чтобы формализовать понятие «сходства» вводится функция расстояния
в пространстве объектов X. Методы обучения, основанные на анализе
сходства объектов, будем называть метрическими
Пусть на множестве объектов X задана функция расстояния ρ :
X × X→[0, ∞). Существует целевая зависимость y ∗ : X → Y , значения которой известны только на объектах обучающей выборки X l =
(xi , yi )li=1 , yi = y ∗ (xi ). Множество классов Y конечно. Требуется построить алгоритм классификации a : X→Y , аппроксимирующий целевую
зависимость y ∗ (x) на всём множестве X.
Если мы выберем любой объект из X и расположим элементы обучающей выборки в порядке возрастания до этого элемента, то получим
(1)
перенумерованную выборку: yu - i-тый сосед объекта u.
Метрический алгоритм классификации с обучающей выборкой X l
относит объект u к тому классу y ∈ Y , для которого суммарный вес
(
)
ближайших обучающих объектов Γy u, X l максимален:
(
a u; X
l
)
(
l
)
(
= argmax Γy u, X ; Γy u, X
y∈Y
l
)
l
∑
[yu(i) = y]w (i, u) ,
=
i=1
где весовая функция w (i, u) оценивает степень важности i-го соседа
(
)
для классификации объекта u. Функция Γy u, X l называется оценкой
близости объекта u к классу y.
Метрический классификатор определён с точностью до весовой функции w (i, u). Для того, чтобы соответствовать гипотезе компатности,
7
необходимо выбирать неотрицательную и возрастающую по i функцию.
Параметрами такого алгоритма является сама обучающая выборка и весовая функция. Но если настройка обучающей выборки больше
относится к вопросу обработки поступающей информации, то весовая
функция позволяет менять сам алгоритм. Выбирая весовую функцию,
можно получать различные метрические классификаторы.
2.1. Метод ближайшего соседа.
Алгоритм ближайшего соседа крайне прост: он находит ближайший
к классифицируемому объект из обучающей выборки, смотрит на его
класс и относит классифицируемый объект к этому классу. Если формализовать это высказывание:
(
)
w (i, u) = [i = 1]; a u, X l = yu(1) ,
(1)
где u ∈ X — классифицируемый объект, а yu - класс ближайшего к
нему объекта.
Достоинства этого алгоритма простота и объяснимость выводов, а
недостатками являются неустойчивость к погрешностям, низкое качеством классификации, отсутствие гибкости, то есть при построении алгоритма не учитыввается достаточно большое количество информации.
Некоторым решением может являться алгоритм k ближайших соседей.
2.2. Алгоритм k ближайших соседей.
Ранее учитывался только один сосед — ближайший, рассмотрим алгоритм, который использует k ближайших соседей.
k
∑
w (i, u) = [i ≤ k]; a u; X , k = argmax
[yu(i) = y].
(
)
l
y∈Y
i=1
Предыдущий алгоритм является частным случаем этого при k = 1,
и так же неустойчив к погрешностям. Однако, не стоит стремиться к
максимально возможному увеличению k, так как в данном случае ал8
горитм будет вырождаться в константу. Появляется проблема выбора
константы k, для решения которой предлагается использовать критерий скользящего контроля с исключением объекта по одному: для каждого объекта проверяется правильно ли он классифицируется по своим
k ближайшим соседям (разумеется нужно исключить сам объект).
l
(
) ∑
(
)
l
LOO k, X =
[a xi ; X l \{xi }, k ̸= yi ]→ min .
k
i=1
Необходимо отметить, что существует еще один вариант этого метода, когда в каждом классе выбирается k ближайших к u объектов, и
объект u относится к тому классу, для которого среднее расстояние до
k ближайших соседей минимально.
Также существует проблема достижения максимума на нескольких
классах. Решением данной проблемы, является введение строго убывающей последовательности вещественных весов wi , задающих вклад i-го
соседа в классификацию. Стоит брать нелинейную последовательность,
в противном случае неоднозначности все же могут возникнуть.
Рассмотренные выше алгоритмы имеют неустранимые недостатки:
необходимость хранить всю обучающую выборку целиком, сравнение
классифицируемого объект в лучшем случае с O (lnl) соседями, а также
небольшой набор параметров. Следующий алгоритм предлагает устранить некоторые из них.
2.3. Метод парзеновского окна.
Будем изменять функцию веса так, чтобы она зависела от расстояния до соседа, а не от его ранга. Для этого введем функцию
(
)ядра K (z),
(i)
ρ(u,xu )
невозрастающую на [0, ∞). Положив w (i, u) = K
, получим
h
алгоритм
)
(
(i)
l
ρ u, xu
∑
(
)
l
(i)
.
a u; X , h = argmax
[yu = y]K
y∈Y
h
i=1
9
Параметр h — ширина окна, роль которого соответствует роли количества соседей — k. ”Окно” — сферическая окрестность объекта u радиуса h, при попадании в которое обучающий объект повышает шанс
на попадание u в свой класс.Скользящий контроль помогает задавать
параметр h так, чтобы окно не было слишком узким, что приводит к
неустойчивой классификации, или слишком широким, так как в этом
случае алгоритм вырождается в константу.
Фиксация окна не всегда оправдана, так как в задачах, может оказаться, большое количество соседей в одних окрестностях, а других —
вообще ни одного. В данных задачах можно применять переменную ширину окна. Необходимо использовать функцию K (z), положительную
на отрезке [0, 1] и равную нулю вне его. Определить h как наибольшее
число, при котором ровно
соседей объекта u получают
( k ближайших
)
(k+1)
ненулевые веса: h (u) = ρ u, xu
. Тогда алгоритм принимает вид:
(
)
a u; X l , k = argmax
y∈Y
k
∑
[yu(i)
i=1
(
(i)
u, xu
)
ρ
(
) .
= y]K
(k+1)
ρ u, xu
2.4. Метод потенциальных функций
К методу ”окон” можно использовать другой подход: рассматривать
окрестности объектов обучающей выборки — при попадании u в окрестность xi , шанс попадания в класс yi повышается.
l
∑
(
)
l
a u; X = argmax
[yi = y]γi K
y∈Y
i=1
(
)
ρ (u, xi )
, γi > 0, hi > 0.
hi
Алгоритм имеет достаточно богатый набор из 2l параметров γi , hi .
Один из методов настройки представлен в следующем алгоритме:
Вход: X l — обучающая выборка;
Выход: Коэффициенты γi , i = 1, . . . , l;
1: инициализация: γi = 0; i = 1, . . . , l;
2: повторять
10
3: выбрать объект xi ∈ X l ;
4: если a (xi ) ̸= yi , то
5: γi := γi + 1;
6: пока число ошибок на выборке не окажется достаточно мало.
Данный алгоритм находит только веса γi , предполагая, что радиусы потенциалов hi и ядро K выбраны заранее. Идея алгоритма заключается
в следующем, если обучающий объект xi классифицируется неверно, то
потенциал класса yi недостаточен в точке xi , и вес γi увеличивается на
единицу. Выбор объектов на шаге 3 лучше осуществлять в случайном
порядке.
Представленный алгоритм достаточно эффективен, при поступлении обучающей выборки потоком. Однако он имеет некоторые недостатки: медленная сходимость, зависимость результата от порядка предъявления объектов, грубая настройка параметров с шагом в единицу.
И как результат алгоритм обладает недостаточно высоким качеством
классификации.
2.5. Отбор эталонных объектов.
В приведенных выше алгоритмах одним из важных параметров является сама обучающаяся выборка. Необходимо упомянуть о некоторых методах, которые позволяют улучшить ее качество, выделить типичных представителей класса. Если рассматриваемый объект близок
к такому типичному представителю — эталону, то скорее всего он сам
принадлежит к этому классу. Но как найти такие объекты? Для этого
введем функцию отступа, которая позволит оценивать степень типичности объекта.
Отступом объекта xi ∈ X l относительно алгоритма классификации, имеющего вид a (u) = argmaxy∈Y Γy (u), называется величина
M (xi ) = Γyi (xi ) − max Γy (xi ) .
y∈Y \yi
Отступ — это показатель степени типичности объекта. Отрицательным он может быть только в случае, когда алгоритм допускает
11
ошибку на данном объекте. В зависимости от значения отступа обучающие объекты условно делятся на типы.
Эталонные объекты имеют большой положительный отступ, плотно
окружены объектами своего класса и являются наиболее типичными
его представителями.
Неинформативные объекты также имеют положительный отступ.
Изъятие этих объектов из выборки (при условии, что эталонные объекты остаются) не влияет на качество классификации.
Пограничные объекты имеют отступ близкий к нулю. Классификация таких объектов неустойчива: малые изменения метрики или состава
обучающей выборки могут изменять их классификацию.
Ошибочные объекты имеют отрицательные отступы и классифицируются неверно. Возможной причиной может быть неадекватность алгоритмической модели, в частности, неудачная конструкция метрики
ρ.
Шумовые объекты или выбросы — объекты с большими отрицательными отступами. Они плотно окружены объектами чужих классов и
классифицируются неверно.
Рассматривая распределение значений отступов, можно сделать некоторые выводы о выборке в общем. При большом количестве отрицательных отступов велика вероятность того, что гипотеза компактности
не выполняется и применение метрических алгоритмов в данной задаче нецелесообразно по отношению к выбранной метрике. Большое
количество пограничных объектов показывает, что надежность данной
классификации недостаточна.
2.6. Применение метрических методов классификации
В качестве релизации метода k-ближайших соседей был выбран класс
KNeighborsClassifier библиотеки sclearn для языка Python. Признаки
были отранжированы по корреляции с классом объекта. Для данного
метода была использованп переменная, обладавшая наибольшей корре12
ляцией с классом объекта. Количество рассматриваемых соседей было
фиксировано — 200. Получившаяся точность пресказания равна 72.287%.
На первом этапе при обучении были использованы все переменные, однако качество предсказания оставляло желать лучшего. При изменении
учитываемого количества соседей точность оставалась в пределах 40%.
На втором этапе с помощью метода get_f score() класса XGBclassifier
(библиотека xgboost) переменные были отранжированы по влиянию на
класс объекта, и при последовательном исключении переменных с наименьшей важностью точность повышалась. На третьем этапе осталась
только самая важная переменная, для которой было подобрано оптимальное значение количества соседей. Изменение метрики со стандартной давало только ухудшение результатов. Код для получения наилучшей точности приведен в Приложении 1.
13
3. Линейные классификаторы
Пусть X — пространство объектов; Y = {−1, 1} — множество допустимых ответов; объекты описываются n числовыми признаками fj :
X → R, j = 1, . . . , n. Вектор x = (x1 , . . . , xn ) ∈ Rn , где xj = fj (x),
называется признаковым описанием объекта x. Рассмотрим линейный
классификатор:
( n
)
∑
a (x, w) = sign
wj fj (x) − w0 = sign⟨x, w⟩.
j=1
Уравнение ⟨x, w⟩ = 0 задаёт гиперплоскость, разделяющую классы в
пространстве Rn . Если вектор x находится по одну сторону гиперплоскости, то объект x относится к классу +1, иначе — к классу −1. [1]
Параметр w0 может быть опущен, в связи с тем, что среди признаков
есть константа, fj (x) ≡ −1, и тогда роль свободного коэффициента w0
играет параметр wj .
В случае произвольного числа классов линейный классификатор
определяется выражением
a (x, w) = arg max
y∈Y
n
∑
wyj fj (x) = arg max ⟨x, wy ⟩,
y∈Y
j=0
где каждому классу соотвествует свой вектор весов wy = (wy0 , wy1 , . . . , wyn ).
Обучение линейного классификатора заключается в том, чтобы по
заданной обучающей выборке X m = {(x1 , y1 ) , . . . , (xm , ym )} построить
алгоритм a : X → Y указанного вида, минимизирующий фунционал
эмпирического риска:
m
∑
[
]
Q (w) =
a (xi , w) ̸= yi → min .
w
i=1
Методы обучения линейных классификаторов различаются подходами
к решению данной оптимизационной задачи.
Для удобства введем понятие отступа для произвольного обучаю-
14
щего объекта xi ∈ X m в случае произвольного числа классов:
M (xi ) = ⟨xi , wyi ⟩ − max ⟨xi , wy ⟩.
y∈Y, y̸=yi
Отступ определяет ”степень погруженности” объекта в своей класс,
чем он меньше, тем больше вероятность, что на этом объекте допускается ошибка классификации. В том случае, когда отступ принимает
отрицательное значение, алгоритм допускает ошибку на этом объекте.
Если формализовать данное высказывание:
Q (w) =
m
∑
[
]
M (xi ) < 0 .
i=1
Минимизация функционала Q (w) по вектору весов — задача нахождения максимальной совместной подсистемы в системе неравенств. Однако она NP-полная, и количество решений может быть очень большим,
поиск всех точных решений зачастую не представляет практического
интереса. Нас устроит решение достаточно близкое к точному. Самым
частым упрощением задачи является замена пороговой функции потерь
на ее аппроксимацию:
[
]
M < 0 ≤ L (M ) ,
где L : R → R+ — непрерывная или гладкая функция, как правило,
невозрастающая.
Соотвественно, минимизируется не сам функционал эмпирического
риска, а его верхняя оценка:
m
∑
(
)
Q (w) ≤ Q̃ (w) =
L M (xi ) .
i=1
Такие непрерывные аппроксимации позволяют применять известные
численные методы оптимизации для настройки весов.
К оценке стоит добавить штрафное слагаемое, которое запретит
слишком большое значение нормы вектора весов.
m
∑
(
)
Q (w) ≤ Q̃ (w) =
L M (xi ) + γ||w||p → min .
w
i=1
15
Данное штрафное слагаемое-регуляризатор снижает риск переобучения и повышает устойчивость вектора весов по отношению к малым
изменениям обучающей выборки. Этот параметр подбирается исходя
из априорных соображений, либо по скользящему контролю.
3.1. Метод стохастического градиента
Существует оптимизационная задача
Q (w) =
l
∑
L (a (xi , w) , yi ) → min,
w
i=1
где L (a, y) — заданная функция потерь. Применим для минимизации
Q (w) метод градиентного спуска. Сначала выбираем некоторое начальное приближение для вектора весов w, затем запускаем итерационный
процесс, на каждом шаге которого вектор w изменяется в направлении
наиболее быстрого убывания функционала
( Q.)nЭто направление проти:
воположно вектору градиента Q′ (w) = δQ(w)
δwj
j=1
w := w − ηQ′ (w) ,
где η > 0 – величина шага в направлении антиградиента, называемая
также темпом обучения. Предполагая, что функция потерь L дифференцируема, распишем градиент:
w := w−η
l
∑
L′ (⟨w, xi ⟩yi ) xi yi .
i=1
Каждый прецедент (xi , , yi ) вносит аддитивный вклад в изменение вектора w, но вектор w изменяется только после перебора всех l объектов.
Сходимость итерационного процесса можно улучшить, если выбирать
прецеденты (xi , yi ) по одному, для каждого делать градиентный шаг и
сразу обновлять вектор весов:
w := w−η
l
∑
L′a (⟨w, xi ⟩yi ) xi yi .
i=1
16
В методе стохастического градиента прецеденты перебираются в случайном порядке, если же объекты предъявлять в некотором фиксированном порядке, процесс может зациклиться или разойтись
Алгоритм стохастического градиента.
Вход: X l — обучающая выборка; η — темп обучения; λ — параметр
сглаживания функционала Q;
Выход: Вектор весов w;
1: инициализировать веса wj j = 0, . . . , n;
2: инициализировать текущую оценку функционала:
Q :=
l
∑
L (a (xi , w) , yi ) ;
i=1
3: повторять пока значение Q не стабилизируется и/или веса w не
перестанут изменяться
4: выбрать объект xi из X l (например, случайным образом);
5: вычислить выходное значение алгоритма a (xi , w) и ошибку:
εi := L (a (xi , w) , yi ) ;
6: сделать шаг градиентного спуска:
w := w − ηL′a (a (xi , w) , yi ) φ′ (< w, xi >) xi ;
7: оценить значение функционала:
Q := (1 − λ) Q + λεi ;
Одним из параметров данного метода является порядок предъявления объектов. Существует несколько определенных вариантов: выбирать объекты случайным образом. Выбирать случайно, но попеременно из разных классов, что позволяет сильнее изменять вектор весов.
Еще один вариант: предъявлять объекты с вероятностью обратно пропорциональной величине ошибки на объекте, что, однако, приводит к
чуствительности к шумам.
Инициализация вектора весов — также один из параметров. Наи17
более распространено — заполнение нулями, что не всегда является
лучшим подходом.
(
)
1 1
wj :=rand − ,
,
n n
где n — размерность пространства признаков. Этот подход существенно
более удачен, чем предыдущий, при условии нормализации признакового описания.
Недостатками данного алгоритма являются: отсутствие сходимости или слишком медленная сходимость. Возможно ”застревание” на
локальных минимумах, так как функционал Q многоэкстремален. Для
устранения данного недостатка используются техника встряхивания коэффициентов: при стабилизации функционала производятся случайные
модификации вектора w в большой окрестности текущего значения, далее процесс запускается для модифицированного вектора.
3.2. Применение линейных классификаторов.
Для реализации линейного классфикатора был испоьлзован класс
SGDclassifier из библиотеки sklearn для языка python. В котором в качестве метода минимизации эмпирического риска используется метод
стохастического градиента, а в качестве функции потерь L (M (xi )) =
(
)
log2 1 + e−M (xi ) . В выборке все отсутствующие значения были заменены на средние по столбцу. Получившаяся точность предсказания на
тестовой выборке равняется: 31.51%. Код для применения линейного
классификатора приведен в Приложении 2.
18
4. Линейные композиции. Бустинг
При решении задач классификации зачастую оказывается, что ни
один из используемых алгоритмов не обеспечивает нужной нам точности предсказания. Одним из выходов может быть построение композиции этих алгоритмов для компенсации проблем каждого из них. В
качестве примера композиции можно привести простое или взвешенное
голосование.
4.1. Композиция алгоритмов
Композицией K алгоритмов ak (x) = C (bk (x)) , k = 1, . . . , K называется суперпозиция алгоритмических операторов bk : X → R (иногда называющихся базовыми алгоритмами), корректирующей операции
F : RK → R и решающего правила C : R → Y :
a (x) = C (F (b1 (x) , . . . , bK (x))) , x ∈ X.
То есть алгоритм классификации имеет следующю структуру: сначала b (x) вычисляет некую оценку попадания объекта в тот или иной
класс, далее с помощью решающего правила алгоритм переводит их в
конечный результат — номер класса. С помощью пространства оценок
R расширяется множество допустимых корректирующих операций, так
как при определении F как отображения Y t → Y возникает проблема
выбора ”хорошего” F, и количество оптимальных F мало. При комбинировании ответов алгоритмических операторов операция использует
оценки принадлежности объекта к классам, которые более точны. Например, можно использовать линейную комбинацию и настраивать для
каждого базового алгоритма свой коэффициент. [4]
19
4.2. Градиентный бустинг для произвольной функции потерь
Рассмотрим обобщенный случай бустинга в задачах классификации, где корректирующая функция является линейной комбинацией
базовых алгоритмов, что является взвешенным голосованием. Пусть
Y = 1, . . . , M , R = RM , базовые алгоритмы возвращают вектора оценок
принадлежности объекта к тому или иному классу. Введем алгоритмическую композицию как:
a (x) = C (F (b1 (x) , . . . , bK (x))) = argmax
y∈Y
K
∑
ak bk,y (x) , x ∈ X.
k=1
Определим функционал качества получившегося алгоритма как число ошибок, допускаемых на обучающей выборке:
QK =
l
∑
(
argmax
y∈Y
j=1
K
∑
)
ak bk,y (xj ) ̸= yj
k=1
Очевидно, что наша задача заключается в минимазации данного
функционала QK . Для упрощения введем эвристику: пороговая функция потерь функционала качества заменяется непрерывно дифференцируемой оценкой сверху L (M ). Данная оценка является одним из варьируемых параметров.
′
QK ≤ QK =
l
∑
L
( K
∑
i=1
)
ak bk (xi ) , yi
k=1
В целях упрощения задачи минимизации введем следующую эвристику: при добавлении k-того слагаемого, оптимизируются только kтый базовый алгоритм и коэффициент при нем, все ранее введенные
слагаемые остаются фиксированными. С помощью такой тактики оптимизируется набор базовых алгоритмов под наши нужды, то есть при
обучении следующего алгоритма повышается вес объектов, на которых совершалась ошибка классификации. Таким образом, учитывают20
ся недостатки прежних базовых алгоритмов. Получим:
(K−1
)
l
∑
∑
(
)
L
ak bk (xi ) + ab (xi ) , yi → min
Q a, b; X l =
i=1
a,b
k=1
Введем обозначения:(
)l
∑K−1
l
fK−1 = (fK−1,i )i=1 =
— текущее приближение,
k=1 ak bk (xi )
i=1
(∑
)l
l
K−1
fK = (fK,i )i=1 =
— следующее приблиk=1 ak bk (xi ) + ab (xi )
i=1
жение.
Для минимизации Q (f ) используем градиентный метод, первоначально не обращая внимания на тот факт, что fK имеет непроизвольные координаты. Получив результат, далее будем аппроксимируем его
с помощью a и b. Положим начальное приближение:
f0 := 0,
fK,i := fK−1,i − agi , i = 1, . . . , l;
′
gi = L (fK−1,i , yi ) — компоненты вектора градиента, a — градиентный шаг
Зная вектор-градиент, аппроксимируем его базовым алгоритмом bK
так, чтобы (bk (xi ))li=1 приближал вектор (−gi )li=1 :
bK := argmax
b
l
∑
(b (xi ) + gi )2 .
i=1
Данный шаг отражает главную идею бустинга — последовательного построения композиции алгоритмов, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих. С помощью градиентного шага минимизируем функционал и в
результате получаем новый базовый алгоритм. Выкладки можно записать в формальный алгоритм:
Вход: обучающая выборка X l ; параметр K;
Выход: базовые алгоритмы и их веса ak bk , k = 1, . . . , K;
1: инициализация: fi := 0, i = 1, . . . , l;
21
2: для всех k = 1, . . . , K:
3: найти базовый алгоритм, приближающий градиент;
bK := argmin
b
l (
∑
)2
b (xi ) + L (fi , yi ) ;
′
i=1
4: решить задачу одномерной минимизации:
ak := argmin
a>0
l
∑
′
L (fi + abk (xi ) , yi )2 ;
i=1
5: обновить значения композиции на объектах выборки:
fi := fi + ak bk (xi ) ; i = 1, . . . , l.
4.3. Применение градиентного бустинга
Для реализации был использован класс XGBclassifier из библиотеки
xgboost для языка python. В данном классе в качестве базовых алгоритмов используются решающие деревья, а в качестве функции потерь
(
)
L (M (xi )) = log2 1 + e−M (xi ) , количество базовых алгоритмов — решающих деревьев — было ограничено 1900, с глубиной не более 10.
В выборке все отсутствующие значения были заменены на средние
по столбцу. Получившаяся точность предсказания на тестовой выборке
равно 76.53%.
Основными инструментами для настройки алгоритма бустинга являются количество используемых базовых алгоритмов и шаг градиентного метода. Варьируя данные параметры, на первом этапе был найден
локальный максимум точности по количеству базовых алгоритмов, на
втором этапе был выбран шаг градиентного метода для данного количества. Код приведен в Приложении 3.
22
Заключение
В работе были рассмотрены и применены три вида классификаторов: метрический, линейный и бустинговый. Каждый из них обладает
своими преимуществами и недостатками.
Метрические классификаторы просты в применении, однако не обладают достаточной гибкостью, неустойчивы к шумам и выбросам в
исходных данных. Для устранения недостатков — необходимо дополнительно работать с выборкой и использовать лишние ресурсы.
Линейные классификаторы довольно гибки. Можно самостоятельно
подобрать способы нахождения вектора весов, замену функции потерь.
Однако существует проблема сходимости , и неустойчивости к шумам
и выбросам. Одним из решений является применение различных эвристик для улучшения сходимости методов нахождения вектора весов.
Бустинг позволяет объединить слабые классификаторы в один сильный. Так как базовые классифкаторы выступают в роли черного ящика, что является несомненным преимуществом. Объединение базовых
алгоритмов позволяет устранить недостатки каждого алгоритма.
Таким образом, заданная цель классификации объекта, обозначенная в работе, была решена. Самый лучший результат показала реализация алгоритма бустинга XGBclassifier из библиотеки xgboost для
языка python. При сравнении результатов победителя конкурса компании ”Билайн” с результатами, полученными в данной работе, точность
предсказания улучшена на 0.14%.
23
Список литературы
[1] Wikipedia. Линейный классификатор. –– 2008. –– URL: http://goo.
gl/cyVON9.
[2] Wikipedia. Машинное обучение. –– 2016. –– URL: https://goo.gl/
vraQGr.
[3] Воронцов К. В. Лекции по алгоритмическим компощициям. ––
2012. –– URL: http://goo.gl/dtF1OI.
[4] Воронцов К. В. Математические методы обучения по прецедентам. –– 2014. –– URL: http://goo.gl/7eOltj.
24
5. Приложения
В приложениях содержится код для метрического, линейного классификаторов и градиентного бустинга.
5.1. Приложение 1: метрический классификатор
import xgboost as xgb
import numpy as np
import pandas as pd
from sklearn import ensemble
def toInt(x):
if (type(x) ==str):
return int(x, 16)
else:
return x
#чтение
train_df = pd.read_csv(’train.csv’, header=0)
test_df = pd.read_csv(’test.csv’, header=0)
ans_df = pd.read_csv(’ans.csv’, header=0)
train_X = pd.DataFrame();
test_X= pd.DataFrame();
#приведение к удобному виду
train_Y = train_df[’y’]
test_Y = ans_df[’y’]
predictors = [x for x in train_df.columns if x not in [’y’]]
for x in range(0, len(predictors)):
train_X[predictors[x]] = train_df[predictors[x]].apply(toInt)
test_X[predictors[x]] = test_df[predictors[x]].apply(toInt)
#обработка отсутствующих значений
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import Imputer
imp = Imputer(missing_values=’NaN’, strategy=’mean’, axis=0)
25
imp.fit(train_X)
train_X = pd.DataFrame(imp.transform(train_X))
test_X = pd.DataFrame(imp.transform(test_X))
#вычисление важности переменных
XGBclass = xgb.XGBClassifier(max_depth=10, n_estimators=800,
learning_rate=0.03)
XGBclass.fit(train_X, train_Y)
bst = XGBclass.booster()
imps = bst.get_fscore()
feat_imp = pd.Series(imps).sort_values(ascending=False)
#применение knn на самой важной переменной
test_x = test_X[int(feat_imp.axes[0][0])].reshape(-1, 1)
train_x = train_X[int(feat_imp.axes[0][0])].reshape(-1, 1)
neigh = KNeighborsClassifier(n_neighbors=250)
neigh.fit(train_x, train_Y)
knn = neigh.predict(test_x)
print (’Accuracy=%f’ % ((1 - (sum( int(knn[i]) != test_Y[i]
for i in range(len(test_Y))) / float(len(test_Y)) ))*100))
5.2. Приложение 2: линейный классификатор
import pandas as pd
from sklearn.preprocessing import Imputer
from sklearn import linear_model
import xgboost as xgb
#чтение
train_df = pd.read_csv(’train.csv’, header=0)
test_df = pd.read_csv(’test.csv’, header=0)
ans_df = pd.read_csv(’ans.csv’, header=0)
train_X = pd.DataFrame();
test_X= pd.DataFrame();
#приведение к удобному виду
def toInt(x):
26
if (type(x) ==str):
return int(x, 16)
else:
return x
train_Y = train_df[’y’]
test_Y = ans_df[’y’]
predictors = [x for x in train_df.columns if x not in [’y’]]
for x in range(0, len(predictors)):
train_X[predictors[x]] = train_df[predictors[x]].apply(toInt)
test_X[predictors[x]] = test_df[predictors[x]].apply(toInt)
#обработка отсутствующих значений
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import Imputer
imp = Imputer(missing_values=’NaN’, strategy=’mean’, axis=0)
imp.fit(train_X)
train_X = pd.DataFrame(imp.transform(train_X))
test_X = pd.DataFrame(imp.transform(test_X))
#применение линейного классификатора
SGD = linear_model.SGDClassifier()
SGD.fit(train_X, train_Y)
SGDtest = SGD.predict(test_x)
print (’Accuracy=%f’ % (1 - (sum( int(SGDtest[i]) != test_Y[i]
for i in range(len(test_Y))) / float(len(test_Y)) ))*100)
5.3. Приложение 3: градиентный бустинг
import xgboost as xgb
import numpy as np
import pandas as pd
from sklearn import ensemble
def toInt(x):
if (type(x) ==str):
27
return int(x, 16)
else:
return x
#чтение
train_df = pd.read_csv(’train.csv’, header=0)
test_df = pd.read_csv(’test.csv’, header=0)
ans_df = pd.read_csv(’ans.csv’, header=0)
train_X = pd.DataFrame();
test_X= pd.DataFrame();
#приведение к удобному виду
train_Y = train_df[’y’]
test_Y = ans_df[’y’]
predictors = [x for x in train_df.columns if x not in [’y’]]
for x in range(0, len(predictors)):
train_X[predictors[x]] = train_df[predictors[x]].apply(toInt)
test_X[predictors[x]] = test_df[predictors[x]].apply(toInt)
#обработка отсутствующих значений
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import Imputer
imp = Imputer(missing_values=’NaN’, strategy=’mean’, axis=0)
imp.fit(train_X)
train_X = pd.DataFrame(imp.transform(train_X))
test_X = pd.DataFrame(imp.transform(test_X))
#применение градиентного бустинга
XGBclass = xgb.XGBClassifier(max_depth=10, n_estimators=1900,
subsample=0.5, learning_rate=0.01)
XGBclass.fit(train_X, train_Y)
XGBtest = XGBclass.predict(test_X)
print (’Accuracy=%f’ % ((1 - (sum( int(XGBtest[i]) != test_Y[i]
for i in range(len(test_Y))) / float(len(test_Y)) ))*100))
28
Отзывы:
Авторизуйтесь, чтобы оставить отзыв