Основы машинного обучения

ВВЕДЕНИЕ

В МАШИННОЕ ОБУЧЕНИЕ. ЭТАПЫ РЕШЕНИЯ ЗАДАЧ МАШИННОГО ОБУЧЕНИЯ

В результате освоения данной главы обучающийся будет: знать

• • цели и задачи, лежащие в области машинного обучения; уметь
• • производить замеры качества машинно-обученных систем; владеть
• • методами эксплуатации алгоритмов машинного обучения.

Цели и задачи машинного обучения

Задача машинного обучения

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

Чтобы понять, что такое машинное обучение, не обязательно владеть серьезным математическим аппаратом, достаточно рассмотреть работу алгоритма на примере одной задачи, в данном случае — вышеупомянутой задачи фильтрации спама.

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

Как бы человек, не знающий алгоритмов машинного обучения, подошел к решению данной задачи? Во-первых, он попытался бы отыскать слова или последовательности слов в тексте письма или его заголовке, которые часто можно увидеть в спаме, например такие слова или словосочетания, как «только сейчас», «невероятное предложение», «подарок», «купите», «скидка» и т. д. Во-вторых, попытался бы найти множество картинок или же, например, ссылок на вредоносные сайты. Такие критерии могут в той или иной степени характеризовать «спамность» письма. Каждому критерию можно сопоставить некоторую переменную, которая определяла бы его значение. В табл. 4.1 приведено описание таких переменных.

Таблица 4.1

Признаки «сиамности» сообщения.

Критерии, представленные в табл. 4.1, в машинном обучении называются признаками (Jeatures)^x (Флах, 2015) и являются главными параметрами, определяющими объект задачи. Именно с их помощью алгоритм машинного обучения будет пытаться решить задачу. Таким образом, от того, насколько правильно и полно подобраны признаки, описывающие объект задачи, зависит качество работы алгоритма машинного обучения. Об оценке качества работы алгоритма машинного обучения мы будем говорить в параграфе 4.4, а пока попробуем разобраться с тем, как же алгоритм машинного обучения будет использовать эти признаки.

Наиболее простым предположением о том, как при помощи этих признаков определить, к какому классу принадлежит сообще-^[1]

ние, является взвешенная сумма всех этих признаков. Взвешенной суммой называется свертка значений признаков с некоторыми весовыми коэффициентами, определяющими степень важности данного признака. Далее, получив значение свертки, можно использовать некоторую пороговую функцию, область значений которой {0; 1} — не-спам и спам.

В формуле (4.1) в качестве пороговой функции выбрана функция sign. Здесь можно легко увидеть, что выражение под функцией sign представляет собой не что иное, как часть уравнения гиперплоскости, наклон которой описывается скалярным произведением вектора признаков и вектора весов, а смещение гиперплоскости задается нулевым весовым коэффициентом. Данную формулу можно упростить:

Если представить функцию как sign (x) = [т > 0], где выражение в квадратных скобках представляет собой нотацию Айверсона^[2]

то станет очевидно, что вся функция (4.2) как раз задает гиперплоскость, представляющую собой границу между двумя классами — (0; 1}. Функция (4.2) в терминах машинного обучения называется алгоритмом, при помощи которого решается поставленная задача. В данном случае представлен алгоритм линейного классификатора (linear classifier)'^[2]. Более подробно об алгоритмах классификации мы будем говорить в гл. 5.

Выбрав веса для свертки, мы получим так называемую модель классификации, т. е. конкретный вид функции (4.2), позволяющий ^[4]

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

Таблица 4.2

Пример похожих между собой моделей

Значения признаков.	Спам?	Пример модели.	Альтернатива.
(1,1.1).
(1,0,1).
(1,0,0).

Так, в первой строке табл. 4.2 для объекта со значениями признаков (1, 1, 1) и ответом «спам» можно подобрать две функции / (х, w) = sign (х_{ + х₂ + х₃) и / (х, w) = sign (х_{ + 2х₂ + Зх₃ + 1), которые для этого набора признаков будут возвращать ответ «спам». В данной ситуации возникает неопределенность — какую из двух моделей необходимо выбрать?

Из табл. 4.2 видно, что для одного вектора признаков существует множество альтернативных моделей, в связи с чем появляется необходимость выбора какой-либо одной альтернативы из множества. Решение данной задачи представляет некоторую сложность, так как выбрать правильные веса наугад или при помощи экспертизы не так просто. Правильные веса — это такие веса, при которых модель будет давать результаты не только на известных примерах, на которых она обучалась, но и при практическом применении для других задач.

Так, если в нашем экспертном выборе признак количества картинок получит достаточно большой вес, то вполне вероятно, что письма, например, с сайта любителей фотографии скорее всего будут отнесены к спаму. Способность машинно-обученной модели правильно классифицировать новые данные называется обобщающей способностью, а ситуация, в которой модель хорошо работает на известных примерах и плохо — на новых, называется ситуацией переобучения (overfittingY.

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

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

Во-первых, появляется термин «выборка» (learning set, testing set). Всегда, когда мы хотим оценить качество некоторой модели, мы должны получить вручную или автоматически сгенерированную выборку с правильными ответами (в данном случае рассматривается пример обучения с учителем). Это просто таблица, где в каждой строке содержится объект классификации и правильный ответ. Данная выборка не используется в процессе формирования признаков и для выбора параметров модели. Почему — мы ответим позже. Такой подход называется оценкой модели при помощи тестовой выборки. Этот подход не всегда возможен по причине того, что зачастую выборку все же приходится формировать вручную, а от этого она не бывает слишком большой. Тем не менее с точки зрения оценки обобщающей способности классификатора такая выборка была бы наиболее корректной при условии ее репрезентативности.

Во-вторых, в определении полноты присутствует термин «верные гипотезы». Мы оцениваем полноту по некоторому классу, например по классу «спам». Тогда гипотезой является пара «объект — ответ классификатора». Соответственно, верной гипотезой называется такая гипотеза, которая подтверждается в нашем случае тестовой выборкой, т. е. в тестовой выборке содержится такая пара «объект — ответ». Общее же число ответов по данному классу — это число пар «объект — ответ», где ответ — это интересующий нас класс. В примере со спамом — это число всех пар «объект — спам».^[5]

Формула полноты для случая классификации спама выглядит следующим образом (более общую формулу мы рассмотрим в параграфе 4.4):

где N — общее число примеров в тестовой выборке; х_{ — i-й объект тестовой выборки; г/, — правильный ответ, но г-му объекту.

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

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

Существует множество способов выбора оптимальных весов для предложенной модели (4.2). Одним из них является способ, заключающийся в том, чтобы взять некоторую релевантную обучающую выборку, подобную тестовой выборке, и подобрать веса модели так, чтобы на все или большинство примеров модель отвечала верным образом, или, например, как в случае с методом оценки полноты, модель на обучающей выборке имела наибольшую полноту.

Таким образом, выбор весов можно определить как задачу математического программирования, например:

где mm означает минимизацию по вектору w.

w

В формуле (4.3) представлено не что иное, как оценка среднеквадратичной ошибки. Причем с точки зрения задачи минимизации от извлечения корня и вычисления дисперсии можно отказаться:

Таким образом мы сможем минимизировать все ошибки на обучающей выборке. Однако встает непростой вопрос: как минимизировать данное выражение аналитическими методами, если под функцией f (x, w) стоит операция sign? Это довольно неприятное занятие, так как данная функция недифференцируема и найти ее минимум просто так не получится. Именно в этой точке возникает множество алгоритмов, называемое линейными алгоритмами классификации. О них мы поговорим в гл. 5, но вся разница между различными линейными алгоритмами классификации в основном и заключается в том, что в разных алгоритмах выбирается та или иная апроксимация функции sign, чтобы было проще минимизовать ошибку.

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

Машинное обучение (machine learning) — это раздел искусственного интеллекта, математическая дисциплина, в основе которой лежат теория вероятностей, математическая статистика, численные методы оптимизации, дискретный анализ, основной целью которого является выделение знаний из имеющихся данных. В примере со спамом такими данными является множество значений признаков. Под знанием подразумевается обученная модель, способная совершать предсказания на новых поступающих данных. Однако машинное обучение — это не только математическая, но и практическая, инженерная дисциплина. В первую очередь это касается моментов изобретения признаков для объектов и использования машинно-обученных алгоритмов на практике, например в такой задаче, как определение спама.

Все методы машинного обучения можно классифицировать в зависимости от способа обучения. Метод обучения, рассмотренный в задаче фильтрации спама, называется обучением с учителем. Обучение с учителем (supervised learning) — это метод обучения модели, заключающийся в том, что для каждого объекта, на котором происходит обучение (в примере со спамом — эго набор признаков, высчитанных по письму) задается пара: «прецедент — решение». Таким образом, обучение с учителем фактически моделирует индуктивный вывод, когда на основе примеров делается некоторое обобщение. Обучение без учителя (unsupervised learning) предполагает, что заранее известных ответов для набора прецедентов нет и модель должна сама, на основе, например, сходства данных, объединить данные в кластер, который бы и являлся ответом, общим для этих данных. В этом смысле обучение без учителя является прекрасным инструментом для поиска новых знаний и данных в работе аналитика. Существует множество других разновидностей методов обучения, однако в данном пособии будут рассматриваться именно эти два.

• [1] См.: Флах П. Машинное обучение. Наука и искусство построения алгоритмов, которые извлекают знания из данных. М.: ДМК-Пресс, 2015.
• [2] 2 Грэхем Р., Кнут Д., Паташик О. Конкретная математика. Основания информатики. М.: Мир, 1998.
• [3] 2 Грэхем Р., Кнут Д., Паташик О. Конкретная математика. Основания информатики. М.: Мир, 1998.
• [4] Ian II., Witten Е. F. Data Mining. Practical Machine Learning Tools andTechniques. Burlington: Elsevier, 2011.
• [5] Hastie Т., Tibshirani R, Friedman J. The Elements of Statistical Learning, DataMining, Inference, and Prediction. California: Springer, 2008.