Открытый курс машинного обучения. Тема 8. Обучение на гигабайтах с Vowpal Wabbit

Открытый курс машинного обучения. Тема 8. Обучение на гигабайтах с Vowpal Wabbit

Вот мы постепенно и дошли до продвинутых методов машинного обучения. Сегодня обсудим, как вообще подступиться к обучению модели, если данных гигабайты или десятки гигабайт. Обсудим приемы, позволяющие это делать: стохастический градиентный спуск (SGD) и хэширование признаков, посмотрим на примеры применения библиотеки Vowpal Wabbit.

UPD 01.2022: С февраля 2022 г. ML-курс ODS на русском возрождается под руководством Петра Ермакова couatl. Для русскоязычной аудитории это предпочтительный вариант (c этими статьями на Хабре – в подкрепление), англоговорящим рекомендуется mlcourse.ai в режиме самостоятельного прохождения.

Видеозапись лекции по мотивам этой статьи в рамках второго запуска открытого курса (сентябрь-ноябрь 2017).

Стохастический градиентный спуск и онлайн-подход к обучению

Стохастический градиентный спуск

Несмотря на то, что градиентный спуск – одна из первых тем, изучаемых в теории оптимизации и машинном обучении, сложно переоценить важность одной его модификации – стохастического градиентного спуска, который мы часто будем называть просто SGD (Stochastic Gradient Descent).

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

Это я в Шерегеше – всем катающим советую хотя бы раз в жизни там оказаться. Картинка для успокоения глаз, но с ее помощью можно пояснить интуицию градиентного спуска. Если задача – как можно быстрее спуститься с горы на сноуборде, то нужно в каждой точке выбирать максимальный уклон (если это совместимо с жизнью), то есть вычислять антиградиент.

Пример: парная регрессия

Задачу простой парной регрессии можно решать с помощью градиентного спуска. Предположим, мы прогнозируем одну переменную по другой – рост по весу – и постулируем линейную зависимость роста от веса.

Даны вектор длины – значения веса для каждого наблюдения (человека) и – вектор значений роста для каждого наблюдения (человека).

Задача: найти такие веса и , чтобы при прогнозе роста по весу в виде (где – -ое значение роста, – -ое значение веса) минимизировать квадратичную ошибку (можно и среднеквадратичную, но константа погоды не делает, а заведена для красоты):

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

Если обратиться к ручке и бумажке и найти аналитические выражения для частных производных, то получим

И все это довольно хорошо работает (в этой статье мы не будем обсуждать проблемы локальных минимумов, подбора шага градиентного спуска, момент и т.д. – про это и так много написано, можно обратиться к главе "Numeric Computation" книги "Deep Learning") пока данных не становится слишком много. Проблема такого подхода в том, что вычисление градиента сводится к суммированию некоторых величин для каждого объекта обучающей выборки. То есть попросту, проблема в том, что итераций алгоритму на практике требуется много, а на каждой итерации веса пересчитываются по формуле, в которой есть сумма по всей выборке вида . А что если объектов в выборке миллионы и миллиарды?

Суть стохастического градиентного спуска – неформально, выкинуть знак суммы из формул пересчета весов и обновлять их по одному объекту. То есть в нашем случае

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

В качестве иллюстрации возьмем картинку Эндрю Ына из его курса машинного обучения.

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

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

Онлайн-подход к обучению

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

В случае парной регрессии, который мы рассмотрели, на диске можно хранить обучающую выборку и, не загружая ее в оперативную память (она может попросту не поместиться), считывать объекты по одному и обновлять веса:

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

Такой подход к обучению моделей часто называют онлайн-обучением, термин появился еще до того, как MOOC-и стали мэйнстримом.

В этой статье мы не рассматриваем многих нюансов стохастической оптимизации (вот хорошая статья на Хабре, фундаментально изучить эту тему можно по книге Boyd "Convex Optimization"), перейдем скорее к библиотеке Vowpal Wabbit, с помощью которой можно обучать простые модели на огромных выборках за счет стохастической оптимизации и еще одного трюка – хэширования признаков, о котором пойдет речь далее.

В библиотеке Scikit-learn классификаторы и регрессоры, обучаемые стохастическим градиентным спуском, реализованы классами SGDClassifier и SGDRegressor из sklearn.linear_model .

Работа с категориальными признаками: Label Encoding, One-Hot Encoding, Hashing trick

Label Encoding

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

Рассмотрим выборку UCI bank, в которой большая часть признаков – категориальные.

Нетрудно заметить, что достаточно много признаков в этом наборе данных не представлены числами. В таком виде данные нам еще не подходят: мы не сможем применять подавляющее большинство доступных нам методов.

Чтобы найти решение, давайте рассмотрим признак education :

Естественным решением такой проблемы было бы однозначное отображение каждого значения в уникальное число. К примеру, мы могли бы преобразовать university.degree в 0, а basic.9y в 1. Эту простую операцию приходится делать часто, поэтому в модуле preprocessing библиотеки sklearn именно для этой задачи реализован класс LabelEncoder :

Метод fit этого класса находит все уникальные значения и строит таблицу для соответствия каждой категории некоторому числу, а метод transform непосредственно преобразует значения в числа. После fit у label_encoder будет доступно поле classes_ , содержащее все уникальные значения. Можно их пронумеровать и убедиться, что преобразование выполнено верно.

Что произойдет, если у нас появятся данные с другими категориями? LabelEncoder ругнется, что не знает новую категорию.

Таким образом, при использовании этого подхода мы всегда должны быть уверены, что признак не может принимать неизвестных ранее значений. К этой проблеме мы вернемся чуть позже, а сейчас заменим весь столбец education на преобразованный:

Продолжим преобразование для всех столбцов, имеющих тип object – именно этот тип задается в pandas для таких данных.

Основная проблема такого представления заключается в том, что числовой код создал евклидово представление для данных.

К примеру, нами неявным образом была введена алгебра над значениями работы – мы можем вычесть работу клиента 1 из работы клиента 2. Конечно же, эта операция не имеет никакого смысла. Но именно на этом основаны метрики близости объектов, что делает бессмысленным применение метода ближайшего соседа на данных в таком виде. Аналогичным образом, никакого смысла не будет иметь применение линейных моделей. Посмотрим, как на таких данных сработает логистическая регрессия и убедимся, что ничего хорошего не получается.

Для того, чтобы мы смогли применять линейные модели на таких данных, нам необходим другой метод, который называется One-Hot Encoding.

One-Hot Encoding

Предположим, что некоторый признак может принимать 10 разных значений. В этом случае One Hot Encoding подразумевает создание 10 признаков, все из которых равны нулю за исключением одного. На позицию, соответствующую численному значению признака мы помещаем 1.

Эта техника реализована в sklearn.preprocessing в классе OneHotEncoder . По умолчанию OneHotEncoder преобразует данные в разреженную матрицу, чтобы не расходовать память на хранение многочисленных нулей. Однако в этом примере размер данных не является для нас проблемой, поэтому мы будем использовать "плотное" представление.

Мы получили 53 столбца — именно столько различных уникальных значений могут принимать категориальные столбцы исходной выборки. Преобразованные с помощью One-Hot Encoding данные начинают обретать смысл для линейной модели – точность по классу 1 (кто подтвердил кредит) составила 61%, полнота) – 17%.

Хэширование признаков (Hashing trick)

Реальные данные могут оказаться гораздо более динамичными, и мы не всегда можем рассчитывать, что категориальные признаки не будут принимать новых значений. Все это сильно затрудняет использование уже обученных моделей на новых данных. Кроме того, LabelEncoder подразумевает предварительный анализ всей выборки и хранение построенных отображений в памяти, что затрудняет работу в режиме больших данных.

Для решения этих проблем существует более простой подход к векторизации категориальных признаков, основанный на хэшировании, известный как hashing trick.

Хэш-функции могут помочь нам в задаче поиска уникальных кодов для различных значений признака, к примеру:

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

Представим, что у нас в выборке есть холостой студент, которому позвонили в понедельник, тогда его вектор признаков будет сформирован аналогично One-Hot Encoding, но в едином пространстве фиксированного размера для всех признаков:

Стоит обратить внимание, что в этом примере хэшировались не только значения признаков, а пары название признака + значение признака. Это необходимо, чтобы разделить одинаковые значения разных признаков между собой, к примеру:

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

Возможно, вы спросите: "а что за хрень вообще происходит?", и покажется, что при хэшировании признаков страдает здравый смысл. Возможно, но эта эвристика – по сути, единственный подход к тому, чтобы работать с категориальными признаками, у которых много уникальных значений. Более того, эта техника себя хорошо зарекомендовала по результатами на практике. Подробней про хэширование признаков (learning to hash) можно почитать в этом обзоре, а также в материалах Евгения Соколова.

Библиотека Vowpal Wabbit

Vowpal Wabbit (VW) является одной из наиболее широко используемых библиотек в индустрии. Её отличает высокая скорость работы и поддержка большого количества различных режимов обучения. Особый интерес для больших и высокоразмерных данных представляет онлайн-обучение – самая сильная сторона библиотеки. Также реализовано хэширование признаков, и Vowpal Wabbit отлично подходит для работы с текстовыми данными.

Основным интерфейсом для работы с VW является shell. Vowpal Wabbit считывает данные из файла или стандартного ввода (stdin) в формате, который имеет следующий вид:

[Label] [Importance] [Tag]|Namespace Features |Namespace Features . |Namespace Features

где [] обозначает необязательные элементы, а (. )* означает повтор неопределенное число раз.

  • Label является числом, "правильным" ответом. В случае классификации обычно принимает значение 1/-1, а в случае регрессии некоторое вещественное число
  • Importance является числом и отвечает за вес примера при обучении. Это позволяет бороться с проблемой несбалансированных данных, изученной нами ранее
  • Tag является некоторой строкой без пробелов и отвечает за некоторое "название" примера, которое сохраняется при предсказании ответа. Для того, чтобы отделить Tag от Importance лучше начинать Tag с символа '.
  • Namespace служит для создания отдельных пространств признаков. В аргументах Namespace именуются по первой букве, это нужно учитывать при выборе их названий
  • Features являются непосредственно признаками объекта внутри Namespace. Признаки по умолчанию имеют вес 1.0, но его можно переопределить, к примеру feature:0.1.

К примеру, под такой формат подходит следующая строка:

VW является прекрасным инструментом для работы с текстовыми данными. Убедимся в этом с помощью выборки 20newsgroups, содержащей новости из 20 различных тематических рассылок.

Новости. Бинарная классификация

Каждая новость относится к одной из 20 тем: alt.atheism, comp.graphics, comp.os.ms-windows.misc, comp.sys.ibm.pc.hardware, comp.sys.mac.hardware, comp.windows.x, misc.forsalerec.autos, rec.motorcycles, rec.sport.baseball, rec.sport.hockey, sci.crypt, sci.electronics, sci.med, sci.space, soc.religion.christian, talk.politics.guns, talk.politics.mideast, talk.politics.misc, talk.religion.misc.

Рассмотрим первый текстовый документ этой коллекции:

Приведем данные к формату Vowpal Wabbit, при этом оставляя только слова не короче 3 символов. Здесь мы не выполняем многие важные в анализе текстов процедуры (стемминг и лемматизацию), но, как увидим, задача и так будет решаться хорошо.

Разобьем выборку на обучающую и тестовую и запишем в файл преобразованные таким образом документы. Будем считать документ положительным, если он относится к рассылке про автомобили rec.autos. Так мы построим модель, отличающую новости про автомобили от остальных.

Запустим Vowpal Wabbit на сформированном файле. Мы решаем задачу классификации, поэтому зададим функцию потерь в значение hinge (линейный SVM). Построенную модель мы сохраним в соответствующий файл 20news_model.vw .

Модель обучена. VW выводит достаточно много полезной информации по ходу обучения (тем не менее, ее можно погасить, если задать параметр --quiet). Подробно вывод диагностической информации разобран в документации VW на GitHub – тут. Обратите внимание, что average loss снижался по ходу выполнения итераций. Для вычисления функции потерь VW использует еще не просмотренные примеры, поэтому, как правило, эта оценка является корректной. Применим обученную модель на тестовой выборке, сохраняя предсказания в файл с помощью опции -p:

Загрузим полученные предсказания, вычислим AUC и отобразим ROC-кривую:

Полученное значения AUC говорит о высоком качестве классификации.

Новости. Многоклассовая классификация

Используем ту же выборку, что в прошлой части, но решаем задачу многоклассовой классификации. Тут Vowpal Wabbit слегка капризничает – он любит, чтоб метки классов были распределены от 1 до K, где K – число классов в задаче классификации (в нашем случае – 20). Поэтому придется применить LabelEncoder, да еще и один добавить потом ( LabelEncoder переводит метки в диапозон от 0 до K-1).

Выборки будут те же, а метки поменяются, train_labels_mult и test_labels_mult – векторы меток от 1 до 20.

Обучим Vowpal Wabbit в режиме многоклассовой классификации, передав параметр oaa (от "one against all"), равный числу классов. Также перечислим параметры, которые можно понастраивать, и от которых качество модели может зависеть довольно значительно (более полно – в официальном тьюториале по Vowpal Wabbit):

  • темп обучения (-l, по умолчанию 0.5) – коэффициент перед изменением весов модели при каждом изменении
  • степень убывания темпа обучения (--power_t, по умолчанию 0.5) – на практике проверено, что если темп обучения уменьшается при увеличении числа итераций стохастического градиентного спуска, то минимум функции находится лучше
  • функция потерь (--loss_function) – от нее, по сути, зависит обучаемый алгоритм. Про функции потерь в документации

регуляризация (-l1) – тут надо обратить внимание на то, что в VW регуляризация считается для каждого объекта, поэтому коэффициенты регуляризации обычно берутся малыми, около

Дополнительно можно попробовать автоматическую настройку параметров Vowpal Wabbit с Hyperopt. Пока это работает только с Python 2. Статья на Хабре.

Получаем долю правильных ответов около 87%.

В качестве примера анализа результатов, посмотрим, с какими темами классификатор путает атеизм.

Эти темы: rec.autos, rec.sport.baseball, sci.med, soc.religion.christian и talk.religion.misc.

Рецензии к фильмам IMDB

В этой части мы будем заниматься бинарной классификацией отзывов к фильмам, публикованным на сайте IMDB. Обратите внимание, насколько быстро будет работать Vowpal Wabbit.

Используем функцию load_files из sklearn.datasets для загрузки отзывов по фильмам отсюда. Скачайте данные и укажите свой путь к каталогу imdb_reviews (в нем должны быть каталоги train и test). Разархивирование может занять несколько минут – там 100 тыс. файлов. В обучающей и тестовой выборках по 12500 тысяч хороших и плохих отзывов к фильмам. Отделим данные (собственно, тексты) от меток.

То же самое с тестовой выборкой.

Это был хороший отзыв. А вот плохой:

Будем использовать ранее написанную функцию to_vw_format . Подготовим обучающую ( movie_reviews_train.vw ), отложенную ( movie_reviews_valid.vw ) и тестовую ( movie_reviews_test.vw ) выборки для Vowpal Wabbit. 70% исходной обучающей выборки оставим под обучение, 30% – под отложенную выборку.

Обучим модель Vowpal Wabbit со следующими аргументами:

  • -d, путь к обучающей выборке (соотв. файл .vw )
  • --loss_function – hinge (хотя можно и поэкспериментировать с другими)
  • -f – путь к файлу, в который запишется модель (можно тоже в формате .vw)

Сделаем прогноз для отложенной выборки с помощью обученной модели Vowpal Wabbit, передав следующие аргументы:

  • -i –путь к обученной модели (соотв. файл .vw)
  • -t -d – путь к отложенной выборке (соотв. файл .vw)
  • -p – путь к txt-файлу, куда запишутся прогнозы

Считаем прогноз из файла и посчитаем долю правильных ответов и ROC AUC. Учтем, что VW выводит оценки вероятности принадлежности к классу +1. Эти оценки распределены на [-1, 1], поэтому бинарным ответом алгоритма (0 или 1) будем попросту считать тот факт, что оценка получилась положительной. Получаем AUC 88.5% и долю правильных ответов – 94.2% и на проверочной выборке и примерно столько же – на тестовой.

Попробуем улучшить прогноз за счет задействования биграмм. Качество немного повышается – до 89% AUC и 95% верных ответов.

Классификация вопросов на StackOverflow

Теперь посмотрим, как в действительности Vowpal Wabbit справляется с большими выборками. Имеется 10 Гб вопросов со StackOverflow – ссылка на данные, там аккурат 10 миллионов вопросов, и у каждого вопроса может быть несколько тегов. Данные довольно чистые, и не называйте это бигдатой даже в пабе.

Из всех тегов выделены 10, и решается задача классификации на 10 классов: по тексту вопроса надо поставить один из 10 тегов, соответствующих 10 популярным языкам программирования.

Вот как выглядят строки, на которых будет обучаться Vowpal Wabbit. 10 означает 10 класс, далее вертикальная черта и просто текст вопроса.

Обучим на обучающей части выборки (3.3 Гб) модель Vowpal Wabbit со следующими аргументами:

  • -oaa 10 – указываем, что классификация на 10 классов
  • -d – путь к данным
  • -f – путь к модели, которая будет построена
  • -b 28 – используем 28 бит для хэширования, то есть признаковое пространство ограничено признаками, что в данном случае больше, чем число уникальных слов в выборке (но потом появятся би- и триграммы, и ограничение размерности признакового пространства начнет работать)
  • также указываем random seed

Модель обучилась всего за 40 секунд, для тестовой выборки прогнозы сделала еще за 14 секунд, доля правильных ответов – почти 92%. Далее качество модели можно повышать за счет нескольких проходов по выборке, задействования биграмм и настройке параметров. Это вместе с предобработкой данных и будет второй частью домашнего задания.

Домашнее задание №8

В качестве закрепления материала предлагаем самостоятельно реализовать алгоритмы онлайн-обучения классификатора и регрессора. Заполните недостающий код в Jupyter notebook и выберите ответы в веб-форме (в ней же найдете и решение).

Актуальные и обновляемые версии демо-заданий – на английском на сайте курса, вот первое задание. Также по подписке на Patreon ("Bonus Assignments" tier) доступны расширенные домашние задания по каждой теме (только на англ.).

Полезные ссылки

Материал статьи доступен в виде Jupyter Notebook в GitHub-репозитории курса. Но актуальная обновляемая версия – только на английском.

📎📎📎📎📎📎📎📎📎📎