python

Когда данных действительно много: Vowpal Wabbit

  • понедельник, 26 января 2015 г. в 02:10:22
http://habrahabr.ru/post/248779/

Привет, хабр!



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

Многие, кто знаком с машинным обучением знают, что довольно часто хорошее качество можно получить благодаря простым линейным моделям, при условии, что были хорошо отобраны и сгенерированы признаки (что мы и обсуждали ранее). Данные модели радуют также своей простотой и зачастую даже наглядностью (например, SVM, который максимизирует ширину разделяющей полосы). Однако, есть еще одно очень важное достоинство линейных методов — при обучении можно добиться того, что настройка параметров алгоритма (т.е. этап обновления весов) будет производится каждый раз при добавлении нового обьекта. Данные методы машинного обучения в литературе часто также называют Online Machine Learning.

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

На сегодняшний день одной из самых известных реализаций таких методов является пакет Vowpal Wabbit, который можно кратко описать несколькими пунктами:

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

Итак, остановимся подробнее на том, как работать на практике с данным инструментом и какие результаты можно с помощью него получить. В качестве примера рассмотрим известную задачу Titanic: Machine Learning from Disaster. Наверное, это не самый удачный пример ввиду того, что данных в этой задаче немного. Однако, т.к. статья рассчитана в первую очередь на новичков в машинном обучении — данная пост будет отличным продолжением официального Tutorial'а. К тому же, довольно легко будет в последствии переписать используемый в данном посте код для реальной (и актуальный на момент написания поста) задачи Click-Through Rate Prediction — в ней обучающая выборка имеет размер более 5Гб.

Перед началом описания конкретных шагов отметим, что описанный далее код запускался довольно давно (еще до того, как Vawpal Wabbit стал популярен), а сам проект в последнее время активно обновляется, поэтому далее все приведенные исходники верны с некоторой точностью — автор оставляет это на проверку читателю.

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

Итак, начнем с того, что Vowpal Wabbit принимает на вход данные в определенном формате:

label |A feature1:value1 |B feature2:value2

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

Подготовка обучающей и тестовой выборок


Для этого можно взять простой скрипт (а можно просто воспользоваться отличной библиотекой phraug2), который читает файл train.csv построчно и преобразуем каждый обьект обучающей выборки к нужному формуту. Стоит отметить, что label в случае двухклассовой классификации у нас принимает значения +1 или -1

import csv
import re

i = 0

def clean(s):
  return " ".join(re.findall(r'\w+', s,flags = re.UNICODE | re.LOCALE)).lower()
  
with open("train_titanic.csv", "r") as infile, open("train_titanic.vw", "wb") as outfile:
  reader = csv.reader(infile)
  
  for line in reader:
    i += 1
    if i > 1:
      vw_line = ""
      if str(line[1]) == "1":
        vw_line += "1 '"
      else:
        vw_line += "-1 '"
        
      vw_line += str(line[0]) + " |f "
      vw_line += "passenger_class_"+str(line[2])+" "

      vw_line += "last_name_" + clean(line[3].split(",")[0]).replace(" ", "_") + " "
      vw_line += "title_" + clean(line[3].split(",")[1]).split()[0] + " "
      vw_line += "sex_" + clean(line[4]) + " "
      
      if len(str(line[5])) > 0:
        vw_line += "age:" + str(line[5]) + " "
        
      vw_line += "siblings_onboard:" + str(line[6]) + " "
      vw_line += "family_members_onboard:" + str(line[7]) + " "
      vw_line += "embarked_" + str(line[11]) + " "
      
      outfile.write(vw_line[:-1] + "\n")

Аналогично поступим и с тестовой выборкой:

i = 0

with open("test_titanic.csv", "r") as infile, open("test_titanic.vw", "wb") as outfile:
  reader = csv.reader(infile)
  
  for line in reader:
    i += 1
    if i > 1:
      vw_line = ""
      vw_line += "1 '"
      vw_line += str(line[0]) + " |f "
      vw_line += "passenger_class_"+str(line[1])+" "
      vw_line += "last_name_" + clean(line[2].split(",")[0]).replace(" ", "_") + " "
      vw_line += "title_" + clean(line[2].split(",")[1]).split()[0] + " "
      vw_line += "sex_" + clean(line[3]) + " "
      
      if len(str(line[4])) > 0:
        vw_line += "age:" + str(line[4]) + " "
        
      vw_line += "siblings_onboard:" + str(line[5]) + " "
      vw_line += "family_members_onboard:" + str(line[6]) + " "
      vw_line += "embarked_" + str(line[10]) + " "
      
      outfile.write(vw_line[:-1] + "\n")

На выходе получаем 2 файла train_titanic.vw и test_titanic.vw соответственно. Стоит отметить, что это зачастую самй сложный и долгий этап — подготовка выборки. Фактически далее мы будем лишь запускать несколько раз методы машинного обучения на этой выборке и тут же получать результат

Обучение линейных моделей в Vowpal Wabbit


Работа происходит из командной строки посредством запуска утилиты vw с переданными ей параметрами. Чтобы запустить. Мы не будем сосредатачиваться на подробном описании всех параметров, а запустим лишь один из примеров:

vw train_titanic.vw -f model.vw --binary --passes 20 -c -q ff --adaptive --normalized --l1 0.00000001 --l2 0.0000001 -b 24

Тут мы сообщаем о том, что хотим решить задачу бинарной классификации (--binary), хотим сделать 20 проходов по обучающей выборке (--passes 20) хотим сделать L1 и L2 регуляризацию (--l1 0.00000001 --l2 0.0000001), нормализацию, а саму модель сохранить в model.vw. Параметр -b 24 используется для указания функции хэширования (как говорилось вначале — все признаки хэшируются, а сами хэши принимают значения от 0 до 2^b-1). Также, важно отметить параметр -q ff, который указывает, что мы также хотим добавить в модель парные признаки (это очень полезная фича VW, порой позволяющая заметно увеличить качество алгоритмов)

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

vw -d test_titanic.vw -t -i model.vw -p preds_titanic.txt

И сконвертировать результат для отправки в систему kaggle.com:

import csv

with open("preds_titanic.txt", "r") as infile, open("kaggle_preds.csv", "wb") as outfile:
  outfile.write("PassengerId,Survived\n")
  
  for line in infile.readlines():  
    kaggle_line = str(line.split(" ")[1]).replace("\n","")
    if str(int(float(line.split(" ")[0]))) == "1":
      kaggle_line += ",1\n"
    else:
      kaggle_line += ",0\n"

    outfile.write(kaggle_line)

Данное простое решение показывает довольно неплохое качество — более 0.79 AUC. Мы применили довольно тривиальную модель. Оптимизируя параметры и «поиграв» с признаками можно немного улучшить результат (читателю предлагается сделать это в качестве упражнения). Надеюсь, это введение поможет новичкам справляться с обьемом данных в соревнованиях по машинному обучению!