MLClass
Компания
33,67
рейтинг
25 января 2015 в 19:59

Разработка → Когда данных действительно много: Vowpal Wabbit

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



В предыдущих двух постах (раз, два) мы расмотрели основные алгоритмы и техники, применяющиеся участниками соревнований 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. Мы применили довольно тривиальную модель. Оптимизируя параметры и «поиграв» с признаками можно немного улучшить результат (читателю предлагается сделать это в качестве упражнения). Надеюсь, это введение поможет новичкам справляться с обьемом данных в соревнованиях по машинному обучению!
Автор: @akrot
MLClass
рейтинг 33,67
Компания прекратила активность на сайте

Комментарии (13)

  • +1
    Я так чувствую, следующая статья про LibFM будет :).
    • 0
      Следующая статья выбирается по принципу: что из материалов «завалялось» и что можно написать быстро) К сожалению, времени совсем не хватает все рассказать, что есть, даже эта статья совсем без подробностей получилась
  • 0
    Online Machine Learning (или активное обучение)
    Active Learning это немного другое, там про то, что модель может попросить разметить какой-нибудь ранее неразмеченный пример. Онлайновость, конечно, будет только плюсом в данном случае.
    • 0
      Спасибо, поправил! Немного не то я хотел сказать, говоря про активное обучение и, честно говоря, не знал, что эти методы, которые описаны в википедии — имеют отдельное название. Я считал, что это просто набор разрозненных эвристик
  • +2
    Честно говоря, несмотря на всеобщее восхищение Wabbit-ом, я до сих пор не понимаю его нишу и преимущества перед другими инструментами: онлайн модели реализованы чуть меньше чем во всех библиотеках ML, всякие хеширования и bag-of-words реализуется парой строк кода, а для действительно больших данных в любом случае нужно брать что-нибудь на основе MapReduce, чтобы избежать передачи больших объёмов данных по сети. При этом: VW умеет работать только с линейными моделями, запускается как отдельная программа без какого-либо программного интерфейса, да ещё и требует данные в специальном формате. Так в каких ситуациях, на ваш взгляд, его действительно имеет смысл применять?
    • 0
      То, что VW умеет работать только с линейными моделями — это в целом нормально, т.к. мы говорим об онлайн обучении, к тому же линейные модели зачастую дают хорошее качество и все для этого есть в VW. То, что принимает на вход определынный формат — тоже ничего необычного, в целом даже чаще удобно. То, что без интерфейса — как-то не задумывался, многие работают с командной строкой и сходу непонятно, что еще нужно.

      В чем же преимущество VW перед остальными инструментами — сложно ответить на этот вопрос, потому как действительно — у каждого инструмента есть свои плюсы и минусы. Популярность скорее связана с тем, что сам проект разрабатывался сначала в Microsoft Research, а позже — в Yahoo, т.е. выходит из коммерческой среды, в то время как, например, Liblinear — из академической.

      Детальное же сравнение фреймворком между собой я не видел
      • 0
        То, что VW умеет работать только с линейными моделями — это в целом нормально, т.к. мы говорим об онлайн обучении

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

        Программный интерфейс как раз и нужен для того, чтобы в одном скрипте подгатавливать входные данные и скармливать его алгоритму обучения. Да и отдавать наружу такие результаты удобней через API, чем парсить результат работы консольной программы. Поэтому и удивительно, что он вышел из коммерческой среды, где его, по идее, должны постоянно интегрировать в реальные проекты.
        • 0
          >Хм, а как связаны линейность модели и онлайн обучение?
          В общем случае никак. Просто когда говорят об онлайн обучении — сразу вспоминается пример с линейными моделями (потому что они почти все основаны на градиентных методах, где онлайн обучение напрашивается)

          Про программный интерфейс — сложно согласиться насчет программного интерфейса. По моему опыту трудностей не возникает особых — и в целом, очень удобно пользоваться (лично мое мнение). Просто не очень представляю, как выглядит в данном месте программный интерфейс — вроде и так всего хватает. Мне кажется, тут уже, что называется «на вкус и цвет». Это все равно, что работать с первичной обработкой данных с помощью пакета Pandas на Python или из юниксовой консоли (что, кстати, иногда даже удобнее) или же в Excel
  • 0
    Почему требуется столько проходов по данным? Чем больше проходов тем лучше?

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

    Еще вот есть сравнение:
    fastml.com/vowpal-wabbit-liblinear-sbm-and-streamsvm-compared/
    • 0
      В данном случае количество проходов по данным — это в некотором смысле количество итераций градиентного спуска, поэтому — да, чаще чем больше итераций, тем лучше. Однако, на практике лучше приблизиться к оптимальному решению, а дальше использовать BFGS (http://en.wikipedia.org/wiki/Limited-memory_BFGS)

      По второму вопросу — это зависит от конкретной задачи. Но в целом, я бы сказал, что на практике чаще нужно больше данных (если данные соответствующего качества и релевантны для обучения). В целом, выбрасывать данные, когда они есть — это как-то странно)
      • 0
        А какой алгоритм минимизации целевой ф-ии используется на практике? Я слышал о SGD или L-BFGS тоже применим для Big Data?

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

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

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

        • 0
          Если выборка линейно неразделима — это ничего страшного, просто в функционал, который оптимизируется добавляются соответствующие ошибки. Это нормально, на практике выборка почти всегда линейно не разделима. Для полного понимания рекомендую прочитать в лекциях К.В.Воронцова соответствующую главу — там рассматриваеются оба случая — думаю, все остальные вопросы отпадут по-ходу. Если нет — обращайтесь)
  • 0
    Вы бы написали, что это перевод http://mlwave.com/tutorial-titanic-machine-learning-from-distaster/

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка