Thursday, May 3, 2012

Kaggle.com мы третьи!

И вот, наконец, закончилось мое первое соревнование в kaggle.com с неожиданным для меня результатом: третье место. Это, пожалуй, были самые лучшие два месяца с точки зрения изучения data mining-а и я постараюсь в ближайшее время поделиться своими находками.

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


Сложности добавляла низкая ликвидность на рынке бондов. Некоторые контракты не торговались неделями и, понятно, что ни о каком High Frequency Trading тут и речи идти не может.

Моя первая идея была использовать random forest, благо что и пример организаторов использовал его и в целом было понятно что при такой неопределенности данных эта модель должна как-минимум работать неплохо. Поэтому, первым, что я сделал, это нормализовал цены относительно curve_based_price так, чтобы избавиться насовсем от абсолютных значений в долларах США. Это простое изменение в тот момент подняло меня на 5-ую строчку в рейтинге и мотивировало на дальнейшие исследования. Следующим существенным изменением было разбить тренировочные данные на несколько множеств (по типу сделки и по типу бонда). Основной эффект этого разбиения заключался в том, что эффективное время обучения random forest на большом множестве данных упало многократно. Это изменение подняло меня на первое место где я и находился около месяца. За это время успев получить приглашение от организаторов и посетить Stanford Conference of Quantitative Finance.

А дальше был творческий кризис, я пробовал добавлять различные предикторы, пробовал оптимизировать модель, удалять outliers и даже переписал реализацию random forest на Java надеясь что оптимизировав функцию оценки смогу получить лучший результат. Но тщетно, некоторые изменения давали мне небольшое улучшение, но большинство не влияли на результат либо влияли негативно. Постепенно участники стали формировать команды и я потерял свое первое место и рисковал оказаться в районе 5-го места в финале. Что было бы весьма обидно ведь денежный приз дается только за первые три места. Но в последние три дня нам удалось объединить усилия с участником VikP, посчитать арифметическое среднее наших моделей и выйти на третье место.

Немного разочаровало то, что модели победителей это просто смесь большого количества не самых лучших индивидуальных моделей. Т.е. рецепт победы в общем случае прост: натренируйте кучу разных моделей а потом с помощью линейной регресси найдите оптимальную комбинацию. Такой подход мне кажется немного ущербным. Ведь в основе часто лежат модели типа random forest и GBM которые уже сами по себе являются ансамблями большого числа еще более слабых моделей. Но, видимо, в настоящее время, этот подход является лучшим из известного, достаточно например посмотреть на описания решений победителей промежуточных туров Heritage Health Prize.


18 comments:

  1. Мои поздравления. Тоже очень хотел участвовать в этом кейсе, но нехватка времени и лень помешали:-)
    Было бы интересно прочитать о том, что читал по machine learning за это время. Курс ml by Andrew Ng я тоже прошел с большим удовольствием, а вот современные методы типа random forest и boosting пока остаются не проясненными для меня.

    ReplyDelete
    Replies
    1. Статьи, мануалы, форумы, на том же kaggle периодически проскакивают описания участников. Полезней всего, конечно, практика.

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

    наш лучший GBM и без комбинации с другими моделями занял бы второе место
    (кстати ты и сам пытался усереднить свою модель с моделью VikP, но это не сработало.Т.е. это не так просто)

    Удачи в следующих соревнованиях

    ReplyDelete
    Replies
    1. У меня есть подозрение что разбиение по типам помогло исключительно за счет того, что понизило вычислительную сложность задачи, тем самым увеличив эффективный sample size.

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

      Спасибо!

      Delete
  3. Сергей, искренне поздравляю, побежал по наводке читать "Статьи, мануалы, форумы, на том же kaggle периодически проскакивают описания участников" :)

    ReplyDelete
  4. Сергей, поздравляю!
    1. Что можете посоветовать почитать, чтобы сформировать теоретическую базу по machine leraning (желательно на русском)?
    2. В своих экспериментах в конкурсе вы использовали R?

    ReplyDelete
    Replies
    1. 1. На русском, к сожалению, ничего, т.к. давно уже не читаю книг на русском, а тут их и достать то негде. По английски, думаю что лучше всего пройти курс Andrew Ng https://www.coursera.org/course/ml

      2. Да, непосредственно алгоритм был написан на R, препроцессинг на Java.

      Delete
    2. А в курсах на www.coursera.org есть какие-нибудь примеры (на том же R)?

      Delete
  5. Сходите по ссылке. Курс там на octave/matlab. Но по сути это разницы нет никакой.

    ReplyDelete
  6. "Немного разочаровало то, что модели победителей это просто смесь большого количества не самых лучших индивидуальных моделей. Т.е. рецепт победы в общем случае прост: натренируйте кучу разных моделей а потом с помощью линейной регресси найдите оптимальную комбинацию."

    Почему разочаровало? Обычное объединение ансамблей слабых моделей, только вместо вычисления среднего значения каждой модели (как в RandomForest например) прогнозу каждой модели присваивают вес на основании регрессионных коэффициентов. Этот подход называется stacking в англоязычной литературе.

    Павел.

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

      Посмотрите на нынешнего лидера KDD Cup http://www.kddcup2012.org/c/kddcup2012-track2/leaderboard у них в команде 23 участника. Подозреваю что они просто слили в одной регрессии 23 разных модели и получили первое место. И какой в этом смысл?

      Delete
  7. А что подразумевается под непредсказуемостью моделей, можно чуть подробнее? Я не совсем понимаю.

    И еще вопрос, какого рода изменения в алгоритме случайного леса вы делали? Я тоже с этим игрался в свое время.

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

    За ссылку на KDD спасибо, улыбнулся. Согласен что практическая польза от массового объединения моделей весьма сомнительна.

    В свое время знакомился с R на примере решения задач с kaggle. Хороший тренинг. Теперь использую R наверно чаще всего в своей повседневной работе.

    Спасибо за статьи!

    PS. Ранее оставлял коммент к статье "Random Forest с примерами на R", а сейчас его нет, он удален как спам?

    ReplyDelete
    Replies
    1. "А что подразумевается под непредсказуемостью моделей" - это как черный ящик, что-то приходит на вход, что-то выходит на выходе, но как и почему оно выходит именно такое, никому не известно. Помните историю, про алгоритмы машинного зрения, когда нейронную сеть пытались учить распознавать образы, а она научилась распознавать фон, при этом результат был отличным, но при внедрении начались проблемы. Тоже самое вполне может произойти и с этими моделями. Что они предсказывают и почему? А кто знает...

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

      Комментарий в другой статье восстановил, почему-то он действительно попал в спам, вот и пример странного поведения антиспам алгоритма от гугл :)

      Delete
    2. В оригинальной работе по случайному лесу, автор метода предлагал использовать для деления узла не значение одного параметра, а значение случайной комбинации нескольких параметров, например, X2 + 3*X56 - 2*X89. И демонстрировал, что в ряде случаев это дает лучшую точность модели. Но у меня этот алгоритм не взлетел и я его забросил. Потом пробовал другие варианты комбинаций параметров, тоже не показало преимуществ. Возможно конечно все зависит от задачи.
      Сейчас есть мысль сделать что-то вроде трансдуктивного случайного леса (возможно что-то подобное уже существует) по аналогии с трансдуктивным SVM. Это по идее по крайней мере не должно ухудшить результаты, а возможно позволит их и улучшить. Идей много, нет времени все их реализовывать. :)

      Delete
  8. This comment has been removed by the author.

    ReplyDelete
  9. Поздравляю вас с отличным результатом!
    Хотел спросить совета. Может быть подскажите, как найти хорошую команду для участия в соревнованиях на kaggle? В идеале хотелось бы чему-то научиться у сокомандников :)

    ReplyDelete
  10. а что дальше происходит с победителями? т.е. в чем смысл участия, размяться и поднять самооценку? или можно потом это превратить в реальный продукт с первыми клиентами?

    ReplyDelete
  11. Третье место - это шикарный результат. Поздравляем вас! Могу только представить, сколько труда вложено на подготовку. Но оно того стоит!

    ReplyDelete