13
области искусственного интеллекта был смещен на комбинаторно-логические
модели.
В этот же период предпринимаются попытки оценить первые инвестиции
в исследования в области искусственного интеллекта. В 1973 совет научных
исследований Великобритании попросил математика Джеймса Майкла Латхилла
подготовить доклад, дающий научную оценку данному направлению. Этот
документ был представлен в том же году под названием «Искусственный
интеллект. Общий обзор». В данном исследовании он классифицировал все
исследования в области искусственного интеллекта на три группы, из которых
первая включала в себя модели, имеющие прикладное значение, вторая —
фундаментальные исследования, третья — самая многочисленная - включала
попытки имитировать человеческое мышление комбинаторно-логическими
моделями. Общий вывод Латхилла в отношении перспектив исследований в
области искусственного интеллекта носил скептический характер [22].
В 1980 году выходит статься Джона Серла «Сознание, мозг и программы»,
в которой он последовательно критикует тезисы о том, что компьютер обладает
некоторыми когнитивными состояниями, и о том, что компьютер способен
объяснять человеческое познание.
Совокупность критических работ и отсутствие ожидаемого эффекта от
инвестиций периода «золотого века» машинного обучения вызвали снижение
интереса научного сообщества к этому направлению науки. Наряду с
уменьшением финансирования данного направления происходило и сокращение
количества исследований в данной области.
1.1.3 Возрождение интереса к машинному обучению
В 1974 году советским математиком Александром Галушкиным и
американским ученым Полом Вербосом независимо и практически
одновременно был представлен алгоритм обратного распространения ошибки в
нейронных сетях, обеспечивающий их эффективное обучение. Ранее было
14
показано, что функции, недоступные обычным однослойным перцептронам,
способны моделироваться многослойными сетями. В 1986 году, после
публикации этого алгоритма Дэвидом Руммельхартом, началась его широкая
популяризация.
На сегодняшний день он остается основным методом обучения нейронных
сетей, получив ряд модификаций, предоставляющих преимущества при решении
тех или иных задач.
В 1997 году компьютер IBM Deep Blue выигрывает матч по шахматам у
чемпиона мира Гарри Каспарова. И хотя данный программно-аппаратный
комплекс использовал алгоритмы поиска по дереву, эта победа вновь вызвала
интерес к вопросам машинного обучения.
В 2006 году Джеффри Хинтон ввел в обиход термин «Глубокое обучение»
(Deep Learning). Под этим определением понимается модель обучения, акцент в
которой сделан на представление опыта и данных в терминах иерархии понятий,
каждое из которых определено через более простые понятия. Вследствие
получения знаний опытным путем исключается необходимость формального
описания человеком всех необходимых компьютеру знаний. Иерархическое
представление позволяет компьютеру обучаться более сложным понятиям путем
построения из более простых. Граф, описывающий данную иерархию, будет
глубоким, поскольку содержит много уровней, поэтому подобный подход к
машинному обучению называется глубоким обучением. [7]
В 2011 году компьютер IBM Watson выиграл в телевикторине Jeopardy,
которая полностью проводилась на естественном языке. В дальнейшем Watson
стал использоваться в ряде коммерческих проектов IBM, в частности в
диагностике и лечении онкологических заболеваний.
Тогда же, в 2011 году был запущен исследовательский проект Google Brain,
призванный улучшить качество жизни людей при помощи искусственного
интеллекта. У истоков данного проекта стояли Джефф Дин и Эндрю Ын.
15
Алгоритмы, созданные участниками этой команды, применяются, в частности, в
машинном переводе Google, системах распознавания речи. В основе данных
моделей лежат нейронные сети.
Свои подразделения по работе с машинным обучением создали другие
крупнейшие компании, работающие в сфере информационных технологий:
Microsoft, Facebook, Baidu, Apple.
В 2014 году Facebook представила систему DeepFace, способную
распознавать людей с эффективностью на уровне 97,25%, что сравнимо с 97,53%,
характерными для человеческого мозга.
В 2016 году произошло еще одно знаменательное событие — программа
AlphaGo, созданная в Google обыграла мастера по игре в Го Ли Седоля.
Принципиальный момент игры Го заключается в слишком большом дереве
решений, препятствующем применению стандартных алгоритмов поиска по
дереву. Нахождение оптимального хода за разумное время практически
недостижимо. В отличие от DeepBlue, AlphaGo основана на глубоком обучении
нейронных сетей, а основную часть тренировок она провела, играя сама с собой.
Это позволило добиться столь выдающихся результатов — по прогнозам
экспертов такая победа не могла состояться раньше 2020 года — и окончательно
показало превосходство нейронных сетей перед комбинаторно-логическими
методами при решении задач, требующих имитации деятельности мозга
человека.
На сегодняшний день машинное обучение остается одним из наиболее
активно развивающихся направлений в области информационных технологий,
выступая в качестве сложного, но эффективного инструмента, помогающего
специалистам решать множество задач, требующих обработки больших объемов
данных.
1.2 Характеристика основных методов машинного обучения
1.2.1 Обучение с учителем
16
Обучение с учителем — группа методов, в которых применяется обучение
с помощью примеров «стимул — реакция». При этом, между входными данными
и ответами предполагается наличие зависимости, характер которой неизвестен.
Для создания модели применяется т. н. «обучающая выборка», представляющая
собой совокупность пар «объект (представляющий собой набор параметров) —
ответ» (или в другой формулировке - «стимул — реакция»). Задача обучения с
учителем сводится к восстановлению зависимости и создания алгоритма,
способного предсказать ответ для произвольного объекта. Для оценки точности
ответов вводится функционал качества.
1.2.1.1 Линейная регрессия
В общем случае регрессия определяется как задача предсказания одной
или более целевой переменной на основе x входных переменных в форме D-
мерного вектора.
Линейный алгоритм в задачах регрессии представлен следующим образом [4]:
d
a(x) = w
0
+ ∑ w
j
x
j
,
j=1
где w
0
— свободный коэффициент, x
j
— признаки, а w
j
— их веса.
Если добавить (d + 1)-й признак, который на каждом объекте принимает
значение 1, линейный алгоритм можно будет записать в более компактной
форме:
d+1
a(x) = ∑ w
j
x
j
= <w,x>,
j=1
где <w,x> обозначает скалярное произведение двух векторов.
В качестве функционала качества могут служить как функция модуля
отклонения предсказанных ответов от истинных значений целевой переменной,
так и квадрат разности этих показателей.
В первом случае следует учитывать, что функция не имеет производной в
нуле, а значит ее оптимизация затруднена. В отличие от модуля, квадрат
17
разности является гладкой функцией, следовательно, при поиске минимума
допустимо применение градиентных методов.
Задача поиска минимума функции ошибки имеет также аналитическое
решение, представленное в виде [4]:
w
∗
= (X
T
X)
−1
X
T
y
Но аналитический подход имеет свои недостатки, к которым относятся
вычислительная сложность (операция обращения матрицы для d признаков
требует выполнения d
3
операций) и ограничения, связанные с невозможностью
вычисления обратной матрицы для плохо обусловленных матриц. В связи с этим
на практике широко применяются численные методы оптимизации. К ним
относятся градиентный спуск, стохастический градиентный спуск [16].
Среднеквадратичная ошибка является выпуклой и гладкой функцией. Данные
свойства гарантируют наличие одного минимума и существование вектора
градиента в каждой точке функции, что в сумме позволяет применить
градиентный спуск для поиска минимума функции ошибки.
Для этого в первую очередь необходимо выбрать начальное приближение.
Наиболее простым способом является инициализация вектора весов нулями.
w
0
= 0
На каждой дальнейшей итерации (t = 1, …, n) из приближения,
рассчитанного в предыдущей итерации (w
t-1
), производится вычитание вектора
градиента в соответствующей точке w
t-1
с учетом коэффициента η
t,
определяющего шаг спуска.
w
t
= w
t−1
− η
t
∇ Q(w
t−1
, X)
18
Данные итерации прекращаются при наступлении сходимости. Для
сходимости существуют различные определения, однако в значительной части
случаев сходимость определяется следующим образом: итеративный процесс
прекращается в том случае, если разница между двумя последовательными
приближениями не превышает некую заданную величину:
||w
t
− w
t−1
||< ε
Одной из проблем построения моделей линейной регрессии является
правильный подбор шага градиентного спуска. В большинстве моделей
целесообразным представляется применение переменного размера шага, при
этом, с каждой итерацией его размер сокращается. Это позволяет ускорить
процесс поиска оптимума, снижая при этом риск «перепрыгивания» через
минимум, по мере его приближения.
Один из способов задания переменного шага выглядит следующим образом:
η
t
= k/t ,
где t - номер итерации, а k - константа, определяемая опытным путем.
Выражение для градиента в матричной форме имеет следующий вид:
∇
w
Q(w, X) = (2/ℓ) X
T
(Xw − y)
Выражение для j-ой компоненты градиента, таким образом, содержит
суммирование по всем объектам обучающей выборки:
ℓ
∂Q/∂w
j
= (2/ℓ) ∑ x
j
i
(<w, x
i
> − y
i
)
i = 1
Одним из недостатков данного метода оптимизации является длительность
расчетов при большом количестве признаков. Поэтому при построении моделей
на основе больших выборок целесообразнее использовать метод
стохастического градиентного спуска [13].
19
Данный метод основан на том, что под знаком суммы в выражении для j-й
компоненты градиента i-е слагаемое показывает, как необходимо изменить
значение w
j,
чтобы функция качества улучшилась для i-го объекта выборки.
Полная сумма при этом указывает на необходимое изменение данного веса с
целью улучшения качества на всех объектах выборки.
При применении стохастического градиентного спуска вычисление
производится только на одном объекте, выбранном из обучающей выборки
случайным образом.
Первый шаг алгоритма стохастического градиентного спуска не
отличается от предыдущего метода: производится инициализация весов
нулевыми значениями. В дальнейшем запускается итеративный процесс, при
котором на каждой итерации из выборки X берется случайный объект x
i
и на нем
производится вычисление вектора градиента функции качества. Далее
вычисляется следующее приближение путем вычитания вектора из
предыдущего, с учетом шага градиента η
t
:
w
t
= w
t−1
− η
t
∇ Q(w
t−1
, {x
i
})
Итеративный процесс останавливается при достижении определенного
уровня сходимости, определяемого так же, как и для градиентного спуска:
||w
t
− w
t−1
||< ε
Стохастический градиентный спуск имеет ряд преимуществ, по сравнению
с градиентным спуском, в частности данный метод не требует хранить всю
выборку в оперативной памяти компьютера, что позволяет использовать для
построения модели большие обучающие выборки. Кроме того, он применим при
так называемой «онлайн» форме обучения, при котором алгоритм
последовательно получает по одному объекту и проводит коррекцию модели с
учетом новых данных.
20
1.2.1.2 Линейная классификация
Задача линейной бинарной классификации подразумевает наличие всего
двух возможных значений в множестве ответов, которые, как правило,
определяются следующим образом [15]:
Y={−1,+1}
Линейные классификаторы (в случае бинарной классификации) — это
семейство алгоритмов, схожее с линейной регрессией, но в качестве ответов они
возвращают бинарные значения:
d
a(x) =sign(w
0
+∑w
j
x
j
)
j=1
Данную формулу можно упростить, путем добавления ко всем объектам
признака со значением, равным единице:
d
a(x) =sign∑w
j
x
j
= sign〈w, x〉
j=1
Данное выражение возвращает знак скалярного произведения вектора
признаков и вектора весов, относя тем самым объект к «положительному» или
«отрицательному» классу.
Кроме того, в задачах линейной классификации широко применяется
понятие отступа:
M
i
= y
i
〈w, x
i
〉
21
Отступ показывает корректность ответа: положительный отступ
свидетельствует о верном ответе, отрицательный — о ложном. При этом
величина отступа, взятая по модулю, характеризует «уверенность» алгоритма в
ответе.
Для обучения линейного классификатора необходимо, как и в случае
линейной регрессии, определить функцию потерь. Наиболее очевидным
решением представляется вычисление доли неправильных ответов. В этом
случае функция потерь приобретает следующий вид [10]:
ℓ
Q(a, x)
j
= (1/ℓ) ∑ (a(x
i
) ≠ y
i
)
i = 1
Используя определение отступа, данное выше, можно преобразовать
данное выражение:
ℓ
Q(a, x)
j
= (1/ℓ) ∑ [M
i
< 0]
i = 1
Поскольку данная функция является разрывной в точке 0, то к ней
неприменим метод градиентного спуска. Чтобы обойти данное ограничение,
функцию потерь приближают гладкой функцией:
˷
[Mi
< 0]
≤ L(M
i
)
В этом случае возможно построить оценку функционала ошибки:
˷
ℓ
˷
Q(a, X) ≤ Q(a , X) = (1/ℓ) ∑ L(M
i
) →min
a
i = 1
Это позволяет минимизировать гладкую функцию, которая является
оценкой сверху доли неправильных ответов. Данная оценка основана на
предположении, что точке минимума верхней оценки соответствует
минимальное число ошибок (данное условие выполняется не всегда).
В качестве оценок функции потерь используются: логистическая функция
потерь, экспоненциальная функция потерь, кусочно-линейная функция потерь.
22
Для логистической функции потерь функционал ошибки принимает
следующий вид:
ℓ
ℓ
Q(a, X) = (1/ℓ) ∑ ln(exp(-M
i
)) = ∑ ln(exp (-y
i
<w, x
i
>))
i = 1 i = 1
Интересным является тот факт, что если при построении модели ошибка
стала нулевой, то в ходе дальнейшего обучения будут увеличиваться значения
отступов, то есть алгоритм будет повышать степень «уверенности» в
полученных результатах.
1.2.1.3 Решающие деревья
Решающие деревья — это семейство алгоритмов, которое в общем случае
можно определить как k-ичное дерево (на практике, чаще всего, используются
бинарные деревья), обладающее некими решающими правилами в узлах и
некотором заключении о целевой функции в листовых вершинах (которое
представляет собой прогноз для новых объектов). [6]
Таким образом, решающее дерево представляет собой связный
ориентированный ациклический граф.
Решающее правило — функция от объекта, определяющая, в которую из
дочерних вершин должен быть помещен объект на основании его признакового
описания.
В зависимости от характера решаемой задачи листы могут содержать ответ
в виде принадлежности к конкретному классу; d-мерного вектора,
определяющего вероятность принадлежности объекта к каждому из классов,
либо непосредственное значение целевой функции (для задачи регрессии).
В качестве решающего правила выбираются очень простые условия. Наиболее
применимым является проверка, является ли значение признака x
j
меньше некой
пороговой величины t.