23
[xj≤t]
Критерий ошибки разбиения для множества X
m
, пришедшего в вершину
m, является также функцией от признака j, порогового значения t:
Q (X
m
, j, t) →min
j, t
Критерий ошибки разбиения может быть представлен в следующей форме:
Q (X
m
, j, t) = (|X
ℓ
| / |X
m
|) H(X
ℓ
) + (|X
r
| / |X
m
|) H(X
r
)
Параметры j и t подбираются путем перебора. Функция H(X) носит
название критерия информативности; ее значение пропорционально разбросу
ответов в подмножестве X. [16]
При решении задачи регрессии выражение критерия информативности
принимает вид дисперсии:
H(X)
=
(1/|X|)∑ (y
i -
ӯ(X))
2
ӯ = (1/|X|)∑ y
i
i ∈ X
i ∈ X
При решении задачи классификации применяются, в частности, критерий
информативности Джини и энтропийный критерий.
Критерий информативности Джини выражается следующим образом:
K
H(X)
=
∑ p
k
ln(p
k
),
k = 1
где p
k -
доля объектов класс k в множестве X. [10]
Энтропийный критерий имеет следующий вид:
K
H(X)
=
-∑ p
k
(1 - p
k
),
k = 1
где p
k -
доля объектов класс k в множестве X.
24
По результатам подбора множество X
m
разбивается на два подмножества
(в случае применения бинарных деревьев):
X
ℓ
= { x ∈ Xm| [x
j
≤t] }, X
r
= { x ∈ X
m
| [x
j
> t] }
В каждой из полученных дочерних вершин продолжается процесс
разбиения множества, до достижения некоторого критерия останова, после
которого данная вершина будет определена как «лист». В качестве выбранного
критерия останова может служить, например, тот факт, что все объекты,
попавшие в вершину, принадлежат к одному классу, или что в данную вершину
пришел только один объект. Также критерием останова может служить глубина
дерева.
После того, как вершина была объявлена листом, происходит вычисление
прогноза, который предоставляет данный лист.
В случае решения задачи регрессии (и использовании в качестве
функционала ошибки MSE) оптимальным прогнозом является среднее
арифметическое значений объектов подмножества обучающей выборки,
содержащегося в данном листе. [10]
a
m
=
(1/|X
m
|)∑ y
i
i∈ Xm
В задачах классификации в качестве прогноза выступает тот класс,
который оказался наиболее распространенным в подмножестве, пришедшем в
данный лист.
am = argmax
y∈ Y
∑ [y
i
= y]
i ∈ Xm
25
В случае, если в качестве прогноза необходимы вероятности классов,
прогноз вычисляется как доля объектов, принадлежащих к определенному
классу, в составе данного подмножества.
a
mk
=
(1/|X
m
|)∑ [y
i
= k]
i ∈ Xm
1.2.1.4 Случайный лес
Одним из основных недостатков решающих деревьев является их
склонность к переобучению. Другая особенность данного алгоритма
проявляется в сильном изменении прогноза при небольшом изменении выборки.
Именно это свойство лежит в основе применения композиций решающих
деревьев, что позволяет снизить риск переобучения, сохраняя при этом
способность к восстановлению сложных зависимостей. [13]
Под композицией понимают объединение N алгоритмов (b
1
, …, b
n
) с
формированием общего усредненного ответа.
В случае решения задачи регрессии композицию можно представить в
следующем виде:
N
a(x)
=
(1/N)∑ b
n
(x),
n = 1
Решение задачи классификации композиция подразумевают взятие знака
полученного ответа:
N
a(x)
=
sign(1/N)∑ b
n
(x),
n = 1
Отдельные алгоритмы семейства b
1
(x), …, b
n
(x) носят название базовых
алгоритмов.
Для построения композиции необходимо выполнить обучение на
различных данных (использование общей обучающей выборки приведет к
построению N одинаковых решающих деревьев, имеющих один и тот же
26
прогноз), для чего применяется рандомизация — использование различных
подвыборок из обучающей выборки. Способность решающих деревьев сильно
изменять прогноз при небольшом изменении обучающей выборки позволяет
получить алгоритмы с отличающимся ответом. [15]
Одним из самых популярных методов рандомизации является бутстрап. Он
заключается в формировании подвыборки длинной ℓ путем случайного взятия с
возвращением объектов из обучающей выборки той же длины ℓ. В результате
отдельные объекты попадут в новую выборку два или более раз, другие не
попадут вовсе. В среднем, новая выборка содержит 63% объектов исходной
выборки.
Другой метод рандомизации — формирование случайного подмножества
на основе обучающей выборки. При этом дополнительной задачей при
построении модели является подбор размера обучающей подвыборки.
Для повышения качества ответов композиции алгоритмов необходимо,
чтобы они как можно меньше коррелировали друг с другом. Это позволяет
уменьшить разброс ответов базовых алгоритмов. Поскольку обучение
проводится на одной выборке, то корреляция неизбежна. Для уменьшения
степени корреляции на практике зачастую применяется метод случайных
подпространств. Он заключается в случайном выборе при формировании
подмножества признаков для каждого базового алгоритма. При использовании
данного метода появляется задача подбора размера этого подмножества.
Один из наиболее распространенных методов объединения решающих
деревьев в композиции носит название случайного леса. [13]
При построении модели на основе случайного леса для повышения
качества применяется рандомизация на этапе построения базового алгоритма.
При этом для разбиения подмножества, пришедшего в очередную вершину, на
два поддерева подбор оптимального значения параметра j идет с использованием
случайного подмножества признаков размерности q. Данный подход позволяет
снизить степень корреляции между базовыми алгоритмами.
27
В практических рекомендациях значение параметра q указывается равным
одной трети от общего числа признаков при решении задачи регрессии, и корню
квадратному от общего числа признаков при решении задачи классификации.
В общем виде построение случайного леса включает в себя следующие
этапы:
1. Формирование N случайных подмножеств с применением бутстрапа.
2. Построение N решающих деревьев с применением рандомизации в каждой
из вершин при разбиении на поддеревья, до достижения критерии останова
(до достижения числа n
min
объектов в каждом листе)
3. Объединение базовых алгоритмов в композицию в зависимости от
решаемой задачи, с помощью приведенных выше формул.
К преимуществам случайного леса относятся: отсутствие переобучения
при увеличении числа базовых алгоритмов, легкость распараллеливания.
Кроме того, применение бутстрапа позволяет использовать для оценки качества
метод, называемый out-of-bag. При этом оценивается ответ для объекта из
обучающей выборки на тех базовых алгоритмах, в обучающие подвыборки
которых он не был включен. Это позволяет использовать для построения модели
всю обучающую выборку, не выделяя ее часть на тестовую подвыборку.
1.2.1.5 Градиентный бустинг
Бустинг — это метод построения композиций, в котором используется
последовательное построение базовых алгоритмов, при этом каждый
последующий направлен на исправление ошибки предыдущего. [10]
Алгоритм построения модели на основе градиентного бустинга для
решения задачи регрессии (при использовании MSE в качестве функции ошибки)
выглядит следующим образом:
1. Построение первого простого алгоритма (дерево небольшой глубины):
28
ℓ
b
1
(x) =argmin
b
(1/ℓ)∑(b(x
i
) - y
i
)
2
j=1
2. Обучение второго алгоритма, направленного на исправление ошибки
первого:
b
1
(x
i
)
+ b
2
(x
i
)
=
y
i
,
При этом
ℓ ℓ
b
2
(x) =argmin
b
(1/ℓ)∑(b
1
(x
i
) + b(x
i
) - y
i
)
2
=
argmin
b
(1/ℓ)∑(b(x
i
) - (y
i
- b
1
(x
i
)))
2
j=1
j=1
Соответственно на шаге N алгоритм будет иметь вид:
ℓ N-1
b
N
(x) = argmin
b
(1/ℓ)∑(b(x
i
) - (y
i
- ∑b
n
(x
i
)))
2
j=1 n=1
Выполнение данного цикла прекращается при достижении заданного
уровня ошибки.
Одним из недостатков метода градиентного бустинга заключается в в его
способности к переобучению. Это связано с низкой способностью простых
базовых алгоритмов приближать вектор антиградиента. Чтобы предотвратить
случайное «блуждание» вектора в пространстве алгоритмов, применяется
сокращение размера шага антиградиента. Таким образом смещение на каждой
итерации выглядит следующим образом:
a
N
(x) =a
N−1
(x) +ηb
N
(x),
где η∈ (0,1] — длина шага. Это обеспечивает более аккуратное смещение,
делая возможным достижение локального минимума функции ошибки. Таким
образом, длина шага является еще одним гиперпараметром, требующим
настройки при построении итоговой модели.
29
При этом следует учитывать следующее взаимоотношение: уменьшение
длины шага обеспечивает меньший уровень ошибки, но при этом требует
большего количества базовых алгоритмов, и как следствие, большего времени на
обучение. Построение модели на основе градиентного бустинга связано с
поиском компромисса между временем обучения и качеством итоговой
композиции. При этом связь между этими параметрами нелинейная: более
длительное обучение лишь немного уменьшает ошибку, хотя в отдельных
применениях это может оказаться критически важным повышением качества. [3]
Другим способом борьбы со склонностью градиентного бустинга к
переобучению является бэггинг — обучение каждого базового алгоритма на
случайной подвыборке.
1.2.1.6 Нейронные сети
В основе нейронных сетей лежит модель нейрона, называемая
персептроном, разработанная Фрэнком Розенблаттом в 1957 году.
Однослойный персептрон — это линейный алгоритм классификации,
принцип работы которого основан на модели работы нейрона. С точки зрения
современной классификации нейронных сетей можно также определить
персептрон как частный случай нейронной сети с прямой передачей сигнала,
одним скрытым слоем и пороговой функцией активации. [5]
В составе перцептрона различают элементы трех типов: S-элементы, A-
элементы и R-элементы.
S-элементы — это слой рецепторов. Каждый из них может находиться
либо в состоянии покоя, либо в состоянии возбуждения. Во втором случае S-
элемент передает сигнал на следующий слой, состоящий из A-элементов.
Каждому А-элементу соответствует определенное количество S-элементов. При
превышении количеством сигналов некоторой пороговой величины θ
происходит активация A-элемента. Сигналы от A-элементов передаются на вход
30
сумматору R. При этом сигал от каждого ассоциативного элемента умножается
на соответствующий ему коэффициент w
i,
называемый весом.
R-элемент суммирует произведения значений входных сигналов на
соответствующие веса и сравнивает полученный результат с порогом θ. При
превышении порога перцептрон выдает на выходе «1», иначе - «-1».
Таким образом, работу R-элемента можно описать следующим выражением:
Обучение перцептрона заключается в подборе значений весов w
i
.
Обоснование нейронной сети как универсальной модели предоставляется
теоремой Колмогорова (1957), которая гласит, что каждая непрерывная функция
a(x), заданная на единичном кубе d-мерного пространства представима в виде:
2d + 1 d
a(x) = ∑ σ
i
(∑f
ij
(x
j
)),
i=1 j = 1
где x = |x
1
,
x
2
, …, x
d
|
T
- вектор описания объекта, функции σ
i
и f
ij
являются
непрерывными, а f
ij
не зависит от выбора a.
Модель однослойной нейронной сети можно представить следующим образом:
d
a(x, w) = σ (w
T
x) = σ
i
(∑w
j
(1)
x
j
+ w
0
(1)
),
j = 1
где
σ — функция активации, w — вектор параметров (весов), x — вектор
описания объекта. Функция активации должна быть непрерывной, монотонной,
предпочтительно дифференцируемой.
В качестве функции активации можно использовать тождественную
функцию σ = id (при решении задач линейной регрессии). В этом случае ответ,
предоставляемый моделью определяется выражением:
31
a(x, w) = w
T
x.
При решении задачи классификации применяется пороговая функция a(x,
w) = sign(w
T
x). [4]
Применение сигмоидной функции в качестве функции активации
позволяет построить модель логистической регрессии:
a(x, w) = w
T
x = 1/(1+exp(-w
T
x)).
При решении задачи многоклассовой классификации (с наличием K
классов) целесообразно построение нейронной сети, состоящей из K нейронов и
использующей в качестве функции активации soft max:
σ (w
1
T
x, w
2
T
x, …, w
K
T
x) = exp(w
K
T
x)/∑
i=1
K
(
w
i
T
x).
На практике для замены пороговой функции sign(x) на дифференцируемую
широко применяется гиперболический тангенс:
tanh(x) = exp(2x - 1)/exp (2x + 1)
Одним из основных недостатков однослойного перцептрона является его
применимость только по отношению к линейно разделимым выборкам. Однако
этот недостаток нивелируется применением многослойных перцептронов, к
которым относятся большинство современных нейронных сетей. [5]
Двуслойную нейросеть можно представить следующим образом:
a(x, w) = σ
(2)
(w
T(2)
σ
(1)
([w
1
T(1)
x, …, w
D
T(1)
x])).
В качестве функции ошибки, применяемой при обучении нейронной сети,
часто применяются средняя квадратичная ошибка (при решении задачи
32
линейной регрессии) и кросс-энтропия (задачи логистической регрессии). В
последнем случае выражение, описывающее функцию, имеет вид:
ℓ
Q(w) = -∑(y
i
ln a(x
i
, w) + (1 - y
i
) ln (1 - a(x
i
, w)))
i = 1
Процесс обучения нейронной сети можно представить как задачу
оптимизации в виде следующего выражения:
w
*
= argmin
w
Q(w),
где Q - функция ошибки, определяемая исследователем.
Алгоритмы оптимизации делятся на два основных типа: алгоритмы
стохастической оптимизации (к ним относятся случайный перебор, генетические
алгоритмы, моделируемый отжиг) и алгоритмы градиентного спуска.
Одним из наиболее популярных методов является алгоритм обратного
распространения ошибки, в основе которого лежит градиентный спуск.
Соответственно, применяться он может при обучении сетей, обладающих
дифференцируемой функцией ошибки, такими как среднеквадратичная ошибка
или кросс-энтропийная. [6]
Данный алгоритм включает следующую последовательность действий:
1. Для каждого нейрона сети h(w
t
x) и вектора описания объекта x обучающей
выборки вычисляется взвешенная сумма входных сигналов z = w
t
x
2. Вычисляется значение выходного сигнала h(z)
3. Вычисляется производная ошибки dφ(z)/d(z) по значению выходного
сигнала нейрона и его параметрам. Это значение зависит от нейронов
предыдущих слоев и называется обратным распространением ошибки.
С помощью принципа обратного распространения можно вычислить
градиент функции ошибки по w:
∇
w
φ(z) = dφ(z)/d(z)∇
w
z = dφ(z)/d(z)x