Просто о сложном

Данные как данность:
как решить задачу по Big Data



Текст: Настя Николаева / Иллюстрации: Casey Richardson
Big Data — это нечто популярное, но очень сложное — огромные массивы информации, записанные в виде кода, доступные только для избранных. T&P попытались понять, как устроена работа с большими данными, и описать ход мысли датамайнера, который ищет в данных закономерности и строит по ним алгоритмы. Для этого мы попросили Александра Дьяконова, директора по науке компании «АлгоМост», показать, как на деле выглядят задачи по Big Data, и объяснить, как их решать.
Задача: Выявить химические эксперименты, не нуждающиеся в повторном проведении
Речь пойдет об анализе данных в экспериментальной химии при изобретении нового материала. Его цель — выявить заведомо успешные и не успешные эксперименты, и тем самым существенно сэкономить на последующем производстве: зная описания предыдущих химических тестов и их результаты, можно исключить проведение новых дорогостоящих экспериментов.

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

В задаче дано описание различных экспериментов, а также условий, в которых они проходили. Решатели получают эти данные в виде двух огромных матриц, в каждой из которых — по три миллиона строк. Математически, суть задачи — построить вектор ответов, соответствующий тестовой матрице. То есть фактически — получить некую функцию, которая по строкам матриц (то есть описаниям экспериментов) вычисляет (оценивает) их предполагаемую успешность.

1
Признаковая матрица
Массив чисел, который описывает объекты классификации. Строки матрицы являются описаниями объектов, а столбцы соответствуют признакам. Таким образом, каждый объект описывается набором чисел — значениями признаков.
2
Обучающая матрица
Признаковая матрица, снабженная правильными метками классов описанных объектов, т.е. каждой строке приписан класс соответствующего объекта. Обычно метки классов записываются в вектор, который называют целевым.
3
Тестовая (контрольная) матрица
Используется для контроля качества работы алгоритма классификации. Правильные метки объектов, которые описаны по строкам этой матрицы, на момент создания алгоритма могут быть неизвестны или известны.
Иллюстрация данных в задаче: пример обучающей, тестовой матриц и целевого вектора
В матрицах расписаны условия экспериментов: каждой строчке, которые отображают значение отдельных признаков, соответствует некое значение целевого вектора. Проблема в том, что эти матрицы гигантских размеров. Во-первых, потому что сами эксперименты были разбиты на некоторые промежуточные этапы: каждая строчка это даже не сам эксперимент, а его некоторые составляющие или этапы. Во-вторых, признаки, фигурирующие в матрицах, — были обезличены, поскольку всегда есть опасение, что конкуренты могут вскрыты механизмы производства и пополнить свои базы данных.
Дано
Обучающая матрица: целочисленная, размера 3413011*240 + целевой вектор

В строках обучающей матрицы указаны условия экспериментов, то есть количество градусов, паскалей и так далее. Им соответствуют элементы целевого вектора, их около двухсот. В столбцах указаны признаки, например, в первом столбце стоит температура, при которой проходили эксперименты, во втором — давление и т.п. Целевой вектор состоит из 3413011 элементов: столько же строк и в обучающей матрице. В нем содержатся правильные ответы: либо 1 (если эксперимент был успешным), либо 0 (если не успешный).

Тестовая матрица: целочисленная, размера 2771628*240

Просто говоря, тестовая информация — это обучающая матрица без правильных ответов.
В этой конкретной задаче участники не знали, какому столбцу какой признак соответствует: где указана температура, где давление, где катализатор и так далее. Кроме того, числовые значения признаков были еще и зашифрованы: можно записать точные значения температуры, например, 15, 20, 35, 40 градусов, а можно просто: 1, 2, 3, 4 (в математике это называется «выполнение монотонного преобразования»). Полученная кодировка данных бессмысленна с точки зрения арифметических операций.

Кажется, что описанные искажения значений признаков только портят исходные данные. Но в этой задаче важны не сами значения, а факт превышения ими некоторых порогов: например, «была ли температура выше 35 градусов». В новой кодировке просто меняется порог: «превышает ли значение признака 3.
Монотонное преобразование значений признака
Кроме того, некоторые данные в исходной матрице были просто продублированы. Это делается для искажения общей информации, в том числе, чтобы понять, насколько решатели умеют обращаться с данными.
Первый этап
Для начала нужно понять, как устроены данные матрицы в контексте задачи. Во-первых, смущают их размеры: откуда взялось по три миллиона строк? Неужели есть какое-то химическое производство, которое сделало три миллиона экспериментов? В это сложно поверить, поэтому сначала полезно проверить наличие дубликатов и общих частей в описаниях отдельных экспериментов, и свести исходные данные до минимума.

Во-вторых, нужно понять, почему структура данных именно такая, откуда берутся эти значения признаков? В нашем случае, как мы уже говорили, значения были подвержены монотонному преобразованию. Выяснив это, можно было раскрыть зависимости, которые в этих данных есть (одному из участников удалось даже восстановить примерные значения исходных признаков). Так же нужно выяснить, какие признаки имеют отношение к задаче, какие не имеют: какие-то могут коррелировать с ответом и их можно использовать, какие-то нет, какой-то признак может просто не иметь ничего общего с экспериментом. Например, признак даты эксперимента или идентификатор сотрудника, который обычно вносится в базу данных, не влияет на результаты. Конечно, возможна закономерность, что какой-то сотрудник халтурит и из-за этого эксперименты получаются не успешными. Но если это не так, то признак — шумящий, он просто мешает и его надо удалить.
Иллюстрация хорошего и шумового признака. В данном случае, большие значения хорошего признака соответствуют успешным экспериментам, маленькие — не успешным. По значениям шумового признака нельзя хорошо классифицировать эксперименты.
Второй этап
Смешать алгоритмы — профессиональный термин, означающий усреднение ответов разных использованных для решения алгоритмов.
Затем начинается процедура решения. Она менее романтическая, чем первая, где вы пытаетесь визуализировать данные, смотрите на картинки, графики, гистограммы. Второй этап более формальный — нужно понять, каким алгоритмом вам решать задачу, точнее какой моделью алгоритмов. Действовать можно по-разному. Алгоритмов решения очень много. Гипотетически, их тысячи, потому что каждый, посидев, может придумать какой-то алгоритм или смешать уже существующие. Но есть и популярные модели алгоритмов. Их несколько десятков: «решающие списки и деревья», «случайные леса», регрессии разных типов, «нейронные сети», SVM (машины опорных векторов), «бустинг» («усиление») простых алгоритмов, байесовские алгоритмы и т.д.

Все эти алгоритмы реализованы в библиотеках популярных языков, например в библиотеке scikit-learn языка Python. Особенность в том, что в разных пакетах и языках алгоритмы реализованы немного по-разному: как по скорости их работы, так и по эффективности. Бывает, что при выборе правильной реализации получаешь небольшое преимущество (где-то в полпроцента), но в режиме соревнования эти пол процента могут отделить первое место от второго.

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

Бустинг — очень популярный и эффективный алгоритм машинного обучения. Здесь тоже строится большое число простых алгоритмов, например, тех же решающих деревьев, только процедура построения более сложная: каждое следующее дерево строится так, чтобы оно лучше классифицировало объекты, на которых ошибались предыдущие. То есть, построенное с учетом ошибок предыдущих каждое новое дерево совершенствует работу алгоритма и, соответственно, качество решения.
Иллюстрация идеи бустинга
Описанные две модели (случайных лесов и бустинга) лучше всех подходят для решения этой конкретной задачи. Победитель конкурса задействовал целых три семейства алгоритмов: основанное на случайных лесах, бустинге и на алгоритме SVM (машине опорных векторов), используя разные хитрости, которые обычно применяются в задачах по классификации текстов. Модель алгоритмов для решения часто подсказывают сами данные. Часть классических алгоритмов была бесполезна в этой задаче из-за больших объемов данных, часть отбрасывалась из-за характера признаков.

Например, в банковском скоринге, когда банк решает, вернет клиент кредит или нет, многие признаки «говорящие»: уровень образования, количество детей и так далее. Часто здесь используют логистическую регрессию, в которой формируется линейная комбинация подобных факторов. Действительно, чем выше образование, тем больше вероятность возврата кредита, поэтому в линейную комбинацию войдет значение признака «образование» с положительным коэффициентом. В нашей же задаче по химии данные перекодированы, и, как мы уже говорили, значения признаков бесполезны в арифметических выражениях, поэтому напрямую логистическую регрессию применять нельзя.
Как может выглядеть решение в логистической регрессии
Третий этап
Это непосредственная настройка модели алгоритмов, на которой вы остановились. Модель — это параметрическое семейство алгоритмов (т.е. алгоритм, у которого есть параметры — константы, от которых зависит его работа, но которым еще не приписаны конкретные значения) Например, в методе случайного леса много параметров: число деревьев, их глубина и т.п. Их значения надо выбрать. С числом деревьев просто: чем их больше, тем лучше (главное, чтобы мощность компьютера позволила все построить вовремя). А другие параметры более тонкие, они, в частности, влияют на то, насколько деревья в лесе будут отличаться друг от друга. А это, как уже говорилось, важно, поскольку разные алгоритмы исправляют ошибки друг друга при голосовании.

Для настройки параметров решатель продумывает процедуру контроля. Она должна моделировать ситуацию, в которой алгоритм сталкивается с новым (ранее неизвестным) объектом и принимает решение о его классификации. Например, можно разбить обучающую матрицу на две части. Первую дать на вход алгоритму как обучающую, а на второй проверять качество его решений.
Четвертый этап
Это, как ни странно, смешивание решений. Победитель, как мы говорили, использовал три модели, результаты которых он в итоге усреднил. Это грамотная стратегия: если вы посмотрите погоду в трех источниках, то будете ориентироваться скорее всего на их среднее значение (ну или на худший вариант). Та же самая парадигма есть в машинном обучении, она, как мы видели, используется в случайном лесе и бустинге, где тоже смешивают результаты разных алгоритмов.

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

При обработке входящей почты мы хотим отличать spam от обычных писем. Эта информация тоже записывается в виде матрицы, где строки соответствую текстам, а столбцы — словам. Скажем, элемент в пятой строке и седьмом столбце равен числу вхождения седьмого слова в словаре в пятый текст. При этом мы знаем, что при оценке схожести текстов не все слова нужно учитывать одинаково: тексты, где часто встречаются союзы «и», «а» не обязательно похожи, а тексты, в которых часто упоминаются слова «мебель», «ремонт» — наверняка. Чаще всего используют специальные нормировки, такие как преобразование TF-IDF, оно позволяет нивелировать предлоги, союзы или артикли, и увеличивать вес слов, которые встречаются реже. Другие примеры задач с текстами: детектирование оскорбительных отзывов на форумах и каталогизация информация на новостных ресурсах (алгоритм кладет новость в папку, которая соответствует теме новости). Есть алгоритмы, которые оценивают гранты с точки зрения их успешности. Они исследует аннотации грантов, описания проектов, состав участников и т.п.

Работа с графической информацией

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

Обработка естественного языка и искусственный интеллект

Технология word2vec переводит слова в векторы. В результате анализа большого массива текстов слова отображаются в некотором многомерном пространстве с помощью функции f, то есть каждому слову соответствует числовой вектор. Если мы из функции f слова «Россия» вычтем f от «США» и прибавим f от «Обама», то получится вектор, похожий на f от «Путин». Таким образом, с точки зрения упоминания слов в текстах разница между США и Россией примерно такая же как между Обамой и Путиным, и если мы сделаем то же самое с Германией, не факт, что результатом станет фамилия президента, а не канцлер, поскольку алгоритм смотрит именно на употребляемость. Так же, если из слова «брак» вычесть «Бред Питт» получится «Анджелина Джоли». Подробнее об этом можно почитать здесь.
Made on
Tilda