Отдел новостей 25 августа 2011, 00:00

Machine Learning: сила данных

Не так давно в списке вакансий одной белорусской компании, чьё название обычно пишется в виде HTML-тега, висела вакансия лингвиста. Зачем софтверной компании лингвист? Ответ можно найти в одном из пунктов требований – для “opinion mining” (“добыча мнений”, “извлечение мнений”, хотя сама компания переводит этот термин как “сентиментный анализ”, подразумевая, видимо, другое распространённое название этой задачи – “sentiment analysis”, дословно “анализ настроений”). Грубо говоря, извлечение мнений – это определение отношения говорящего к предмету разговора. Используется, например, для мониторинга репутации продуктов компании, оценки политических явлений и даже для предсказания индекса Dow Jones. Об извлечении мнений я обязательно напишу отдельную развёрнутую статью, но сначала расскажу про более общую область, на которой и основан opinion mining, а именно про машинное обучение. Можно сказать, что машинное обучение (machine learning) – это набор алгоритмов и методов, позволяющих вычислительной машине делать предсказания на основании предыдущего опыта, такого как статистические данные. Так, например, GMail собирает спам сообщения, помеченные пользователями, и на их основе строит классификатор, позволяющий определять, является ли спамом новое письмо. Другой пример иcпользования ML компанией Google – ранжирование результатов поиска. На основании статистики от пользователей или экспертов строится линейная модель (уравнение вида y = w₀ + w₁x₁ + w₂x₂ + ... + w_nx_n, где w₁…w_n – веса, а x₁…x_n – признаки объекта), показывающая, какой вклад в итоговый рейтинг страницы вносят различные показатели, такие как количество ссылок с других страниц, количество ключевых слов в названии, тексте и ссылке, индекс tf*idf и т.д. При этом результатом обучения является не просто программа, способная сортировать результаты, но понятная человеку формула. То есть с помощью машинного обучения из “сырых” данных можно получить новую полезную информацию. В таких случаях вместо названия “машинное обучение” обычно используют другое – “извлечение данных” (data mining). Извлечение данных активно используется аналитиками для оптимизации процессов в своих областях. Например, изучение ассоциативных правил (см. ниже) может помочь выяснить, какие товары чаще всего покупают вместе, и разместить их в магазине соответствующим образом. Однако этот блог в первую очередь для технарей, а не для аналитиков, поэтому в дальнейшем я буду говорить в основном про машинное обучение, а случаи, когда алгоритм или метод может быть применён для извлечения данных, буду оговаривать специально. Иногда машинное обучение можно обнаружить в самых необычных местах. Так, например, не многие знают, что современные виртуальные машины, такие как CLR или JVM, используют его для оптимизации скомпилированного кода. Например, наиболее распространённая реализация JVM – Oracle HotSpot – постоянно следит за производительностью кода и собирает статистику. Как только статистики оказывается достаточно, чтобы принять решение об оптимизации, код перестраивается и улучшается. Отсюда следует ещё одно определение ML: машинное обучение – это научная дисциплина, занимающаяся созданием алгоритмов, позволяющим вычислительной машине улучшать свою производительность на основании эмпирических данных. При этом под производительностью понимается процентное количество правильно обработанных образцов, например, правильно угаданных ветвей выполнения программы. Всё это хорошо, но довольно абстрактно. Как же процесс машинного обучения происходит на практике? Ниже я опишу, как представляются входные и выходные данные, а также как происходит решение наиболее распространённых задач машинного обучения.

Представление данных

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

Сами атрибуты могут быть нескольких типов. В примере выше возраст – это числовой атрибут. Наличие высшего образования – булевский. Кроме этих двух типов часто встречаются категориальные или номинальные атрибуты, грубо говоря – перечисления. Например, для кандидата на работу это может быть национальность или семейное положение (и речь тут не о дискриминации, а о сборе максимального количества доступной информации :)). Очень редко вводят также строковые атрибуты, где значением могут являться произвольные строки. Как правило, в наборе данных вводят также один специальный атрибут – так называемый атрибут класса. На обучающих данных (если используется метод с обучением, конечно же) его значение известно, а для обрабатываемых – его требуется вычислить. Для примера с кандидатами на работу обучающая выборка может включать в себя признак того, считается ли кандидат подходящим, неподходящим или возможно_подходящим для данной работы. Именно этот признак и будет являться атрибутом класса, и именно его будет требоваться вычислить для новых резюме. Для хранения таких наборов данных используется обычная табличная форма. Это может быть, например, база данных, файл CSV или таблица MS Excel. При этом названия колонок обозначают имена атрибутов, а строки самой таблицы – отдельные объекты, подлежащие обработке. (Внутри программы, как и при математических рассуждениях, объекты представляются в виде векторов в многомерном пространстве. При этом оси координат соответствуют отдельным атрибутам, то есть отдельным элементам вектора.)

Основные задачи

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

Классификация

Классификация (classification) – это группировка объектов по определённому признаку или набору признаков. Спам/не спам, отзыв положительный/отрицательны, кандидат подходит/не подходит/возможно_подходит. Группировка вида тёплый/холодный, синий/зелёный/красный, мальчик/девочка и тому подобное – это тоже классификация, но только по одному признаку, поэтому правила для неё легко определить вручную. В сложных же случаях, таких как определение, является ли письмо спамом, сможет ли заёмщик отдать кредит и т.д. обычно делают так. Вначале собирается статистическая информация об объектах, для которых уже известен их класс, – набор этих объектов называется обучающей выборкой. Затем к этим данным применяется алгоритм машинного обучения, в результате чего получается обученный классификатор, или модель. То есть модель = алгоритм + обучающая выборка. Перед тем как применять модель на реальных данных, как правило, проводят тестирование её производительности. Наиболее распространённым методом тестирования является так называемая перекрёстная проверка (cross-validation). Её суть заключается в том, что обучающая выборка делится на n частей. Классификатор обучается на (n-1) частях, а одну часть используют непосредственно для проверки результата. Эта процедура повторяется n раз, а результатом считается среднее арифметическое результатов отдельных тестов.

Кластеризация

Кластеризация (clustering) в целом похожа на классификацию – в ней объекты также группируются по набору признаков, однако в отличие от классификации при кластеризации нет обучающей выборки. И классов, соответственно, изначально никаких нет. Есть просто набор объектов, которые нужно как-то объединить в группы. Спрашивается, и как же это сделать, если объекты даже не с чем сравнивать? А сравнивать как раз есть с чем – друг с другом. Оказывается, в основе всех алгоритмов классификации лежит понятие расстояния. Проще всего это представить в виде географической проблемы. Предположим, что нам нужно объединить точки на карте – дома, рестораны, стоянки и т.д. – в города. При этом всё, что у нас есть – это координаты отдельных точек, но никакой информации об административном делении. Человек визуально может решить эту задачу элементарно – любая группа точек, расстояние между которыми меньше расстояния до другой группы, и будет считаться городом. После понимания этого, всё, что остаётся сделать, - это выбрать меру расстояния и найти эффективный алгоритм. В общем и целом кластеризация используется скорее для изучения, то есть для извлечения и анализа данных, чем для «серийного» применения. Она может быть проведена для любых данных, которые можно представить в виде графа. Например, в последнее время всё чаще появляются исследования социальных сетей и блогов.

Числовые предсказания

Как Gismeteo определяет, сколько градусов завтра ожидать на термометре? Верно, плохо определяет. Но речь не об этом. Как вообще можно предсказать погоду? По народным приметам, конечно же! Думаете, это шутка? Отнюдь. Народные приметы формировались на основании опыта предыдущих наблюдений. Современные методы работы метеослужб, как ни странно, мало чем отличаются от прабабушкиных предсказаний. pac-man

По сути единственное отличие в том, что с появлением современных компьютерных технологий появилась также и возможность более точно собирать данные и на их основе строить статистические модели. Именно так работают метеослужбы, и именно на этом основаны числовые предсказания (numeric predictions). В отличие от классификации, числовые предсказания, занимаются определением не качественного, а количественного значения некоторой зависимой переменной. В случае погоды зависимым параметром является температура, а также возможное отклонение от среднего значения. Другим примером может быть предсказание количества голосов, отданных за отдельных кандидатов на президентских выборах на основании их политических программ и опыта предыдущих лет. Стандартным приложением числовых предсказаний является также определение технических характеристик, таких как, например, производительность компьютера, на основании данных о его компонентах и прошлых исследованиях. По методологии же числовые предсказания мало чем отличаются от классификации – в них также создаётся обучающая выборка с атрибутом класса числового типа, запускается один из подходящих алгоритмов машинного обучения, а затем обученная модель применяется для предсказаний на новых образцах.

Извлечение ассоциативных правил

Когда вы заказываете книгу на Амазоне или просматриваете трейлер нового фильма на КиноПоиске, где-нибудь внизу обязательно высвечивается несколько похожих книг/фильмов. Система рекомендаций сейчас есть чуть ли не на каждом сайте, который предлагает товары или услуги. Но как они работают? Очень часто веб-мастера поступают просто: берут название товара и ищут по базе данных похожие записи. Но что, если ни названия, ни какие-либо другие атрибуты товаров не пересекаются? Например, «Гарри Поттер» и «Властелин Колец» тематически довольно похожи, и ими, наверняка, интересуется примерно одна и та же категория людей, однако вряд ли вы найдёте много общего в описаниях этих фильмов. Так что же общего тогда между ними. А общие между ними зрители. Если 100 человек посмотрели оба фильма, а 101-й посмотрел только «Властелина Колец», то имеет смысл предложить ему посмотреть и «Гарри Поттера». Если 20 человек заказали книги «Паттерны проектирования» и «Совершенный код», а 21-й только «Паттерны», то почему бы не предложить ему и «Код»? Вывод таких правил и называется извлечением ассоциаций (association mining, association rule learning). Ассоциации не обязательно должны связывать только 2 объекта. В общем виде такие правила можно записать так: Если A1, A2, …, An, то B1, B2, …, Bn. Или даже проще: A1, A2, …, An => B1, B2, ..., Bn. Вот несколько примеров возможных ассоциативных правил для магазинов:

ноутбук => мышка, сумка для ноутбука;
суши => васаби, соевый соус;
понедельник, 8 утра => плохое настроение.

Ассоциативные правила – это мощнейший инструмент маркетинга, однако область их применения не ограничена рекламой. Метеослужбы могут использовать, например, следующее правило: область циклона, область антициклона => дождь. Ассоциации используются в медицине для определения причин болезней (курение, загрязнение окружающей среды => понижение иммунитета, рак), в экономике и социологии для предсказания возможных изменений (девальвация, командная экономика => народные волнения) и т.д.

Интересно?

То, что описано в данной статье, - это только самые общие сведения о машинном обучении. В принципе, есть материал ещё как минимум на 2 части: одна про конкретные методы, другая - про готовые инструменты и их использование на практике. Вопрос: интересует ли сообщество тема машинного обучения и стоит ли продолжать?