Kaggle: Історія про те як ми вчилися передбачати релевантність пошукових запитів і зайняли 3-е місце

kaggle-monster2

Превью

Здрастуй, Хабр! 25-го квітня 2016 року закінчилося 3-х місячне напружене змагання Home Depot Product Search Relevance в якому нашій команді Turing Test (Igor Buinyi, Kostiantyn Omelianchuk, Chenglong Chen) вдалося не тільки непогано розібратися з Natural Language Processing і ML, але і зайняти 3-е місце з 2125 команд. Повний опис нашого рішення і код доступні тут, коротке інтерв'ю тута мета цієї публікації не тільки розповісти про рішення, яке принесло нам такий результат, але і про ті труднощі і переживання, через які нам довелося пройти під час змагання.

Пару слів про Kaggle

Мабуть, більшість читачів знайомі з Kaggle. Для решти відзначу, що на даний момент це найбільша у світі майданчик, де постійно проходить значна кількість змагань за Data Science тематики, в яких колективний розум тисяч учасників генерує велику кількість рішень реальних прикладних задач. В результаті учасники змагань отримують знання та досвід (переможці — ще й призи), а організатори отримують ідеї, які можна успішно впровадити на практиці.

Постановка завдання

— є сайт з продажу інструментів для ремонту і будматеріалів, на якому можна знайти більше кількість специфічних товарів
— є юзери, які намагаються знайти потрібний товар, використовуючи функцію пошуку
— є кілька сотень тисяч відповідностей «пошуковий запит» /«показаний товар»; інформація про товар складається з кількох текстових полів, таких як назва, опис і безліч атрибутів (наприклад, бренд або колір)
— є усереднені оцінки релевантності від асесорів за деякої частини таких відповідностей
— стоїть завдання побудувати алгоритм, який буде добре прогнозувати оцінки релевантності, які поставили б асесори, для інших пар «запит» /«товар»

Навіщо це потрібно?

Оцінки релевантності необхідні при оптимізації пошукового алгоритму, який підбирає відповідність «запит»/ «товар».
Такі оцінки можуть проставити асесори, але вони працюють повільно, а їх час коштує дорого або отримати автоматично, тоді можна заощадити на асессорах і істотно підвищити швидкість зворотного зв'язку. Однак якість оцінок повинно залишитися на тому ж рівні.

Асесори — це люди, які можуть помилятися

Ми намагалися навчити модель імітувати поведінку людей, виставляють оцінки (і нічого понад це). Відповідь на питання, наскільки їх оцінки відповідають «реальної релевантності» незмінно веде нас від конкретної задачі до витоків філософії.

оцінювалося Як якість моделі?

В якості метрики використовувалася RMSE, яка як і будь-яка інша квадратична метрика найсильніше штрафує великі помилки.
rmse4

Якими були вихідні дані?

Дані складалися з пар «запит»(search term)/«товар» (який складався з трьох частин: product title, product description, attributes) і усередненої оцінки релевантності (яка приймала значення від 1 до 3, включаючи деякі дробові).
Розбивка на train/test була зроблена в пропорції 74 067/166 693 і не була випадковою (було багато запитів, які були присутні тільки в test або тільки в train і їх розподіл не можна було назвати нормальним).
Дані були досить брудні (велика кількість граматичних помилок у запитах)

Трохи про нас

Наша команда протягом 5/6 конкурсу складалася з двох чоловік (Ігор Буйний і Костянтин Омелянчук). Ми обидва колеги-аналітики, які працюють в українській компанії, що розробляє браузерні ігри. До початку цього змагання у нас за спиною було багато прослуханих курсів і всього одне змагання на kaggle.com, в якому ми потрапили тільки в топ 15%. Ігор якраз закінчив один проект, де використовувалося NLP, і покликав мене взяти участь у цьому конкурсі.

Наші цілі

Початковими цілями були:
— отримати практичні навички роботи з реальними даними
— глибше розібратися з NLP
— підтягнути навички програмування
— потрапити в топ-10%
Але апетит, як відомо, приходить під час їжі, і по мірі наближення кінця змагання наші цілі переглядалися в бік більш амбітних.

Перші кроки

Як вже говорилося раніше, повне опис нашого рішення опубліковано в іншому місці, а в цій статті ми хотіли б розповісти про хронології наших дій, тому подаємо основні результати і відкриття в тому порядку, в якому вони досягалися.

Етап 1

Ми почали з самого простого, з чого можна було почати — розібралися з готовими сценаріями, які завжди можна знайти на форумі. Оскільки ніяких «порахованих змінних» не було, їх треба було генерувати. Першими змінними у нас (як і у багатьох інших учасників) були числові змінні типу кількості збігів слів між запитом і документом. Першою обробкою тексту було використання stemmer, який залишав від кожного слова його корінь. Модель xgboost на цих фичах після обробки тексту за допомогою stemmer давала RMSE в районі 0,49.

Етап 2

Далі ми почали рухатися в трьох напрямках:
— генерація нових простих змінних
— підгонка параметрів моделі
— виправлення найбільш часто зустрічаються помилок у тексті і приведення однакових за змістом слів до єдиного формату.
Поступово рухаючись у цих трьох напрямках, ми наблизили RMSE до 0,48 і прийшли до висновку, що третій напрямок давало найбільше покращення порівняно з іншими. На цьому етапі було зроблено два важливих відкриття:
1. Виникла ідея якось автоматизувати процес виправлення помилок, і було знайдено рішення використовувати відстань Дамерау-Левенштейна, щоб врахувати не тільки збігаються, але і схожі слова. Це відстань показувало, скільки потрібно зробити операцій вставки/заміни/видалення/транспозиції символів, що б перетворити один рядок в іншу. Ми вважали два слова (word1,word2) однаковими, якщо ця відстань менше min(3,max(len(word1)-3,1)). Нові змінні, підраховані з використанням цього критерію, дозволили поліпшити RMSE до 0,478 і стали ще одним підтвердженням думки про те, що обробка тексту є дуже важливою в цьому конкурсі.
2. До переліку наших простих змінних ми додали змінні, які враховували кількість літер в словах збігаються. Як не дивно, це виявилися дуже сильні змінні, за допомогою яких ми поліпшили RMSE до 0,474.

Етап 3

Стало зрозуміло, що одними простими (keyword match) змінними ми не обійдемося і потрібно використовувати більш складні. Класичними змінними в даній задачі є tf/idf змінні, які враховують вагу кожного збігається слова в залежності від його частоти в конкретному документі і у всій колекції документів. Перші ж спроба додати ці змінні принесла нам 0,468 на RMSE.
Паралельно з цим ми стали шукати корисну інформацію серед атрибути(attributes) документа. Включення змінних пов'язаних з брендами і матеріалами підвищило RMSE до 0,464.

Етап 4

Наступним етапом було генерація змінних, які б враховували смисловий зв'язок між словами. В цій задачі нам допоміг пакет WordNet з бібліотеки NLTK. Використовуючи вбудовані функції, які по-різному вважали синонимическую близькість (similarity) між словами, ми отримали ще одну категорію змінних з принципово новою інформацією, яка не використовувалася раніше.
Також були пораховані змінні, які враховували, до якої частини мови належать слова (використовувався NLTK POS tagger). Разом з цим ми суттєво просунулися в обробці тексту і виправлення помилок. Все це разом дозволило поліпшити RMSE до 0,454 і потрапити в топ 10 команд. (примітка 1 на графіку прогресу)

Етап 5

У міру нашого просування ставало все складніше і складніше покращувати RMSE і співвідношення вдалих дій до спроб, які не приносили бажаний результат, стало схилятися не в нашу сторону. Це навело на думку, що пора братися за побудови ансамблю. Перші спроби побудувати ансамбль не принесли успіху, але ми продовжили працювати в цьому напрямку
Ключовими діями, які дозволили зробити нам наступний стрибок, стали:
— обробка тексту і виправлення помилок;
— локальні tf/idf змінні, які вважалися на рівні документів, що мають відношення до кожному конкретному пошуковому запиту;
— word2vec змінні, які дали дуже істотний приріст до якості прогнозу.
Таким чином, ми довели RMSE до 0,445 на окремої моделі (single model) і вийшли на перше місце цього рейтингу через перші півтора місяці з початку змагання. (примітка 2 на графіку прогресу)

plot1
Малюнок. Графік прогресу результатів

Додаткові проблеми потенційних призерів

До виходу на перше місце, ми розглядали це змагання як майданчик для навчання, але в цей момент ми зрозуміли, що є шанси, як мінімум, пробитися в топ10 (замість початкової мети в топ10%), а як максимум — потрапити в призи (перші три місця). Але для того, що б боротися за призи, нам потрібно було додатково вирішити дві проблеми.

Відтворюване рішення

Переможці змагання повинні надати добре оформлену документацію і код, здатний відтворити фінальне рішення. Наше рішення, м'яко кажучи, не відповідало цій вимозі, так як в код постійно вносилися якісь правки, старі версії коду часто не зберігалися, а проміжні результати розрахунків записувалися в цілу купу файлів. Крім того, що не можна було встановити точну відповідність між версією коду і конкретним файлом з змінними, так і ще повний перерахунок в ручному режимі вимагав більше тижня обчислювального часу на наших машинах.

Шарінг всіх сторонніх зовнішніх даних

Другим важливим моментом стала піднялася дискусія на форумі про те, яка обробка тексту є допустимою, а яка-ні. Цей спір породив скрипт юзера steubk, який хитрим чином проганяв всі пошукові запити через гугл і підтягував виправлений гуглом текст. Адміни конкурсу спершу виступили проти використання цього алгоритму і проти «ручних виправлень» (hand labeling) помилок у тексті. Але оскільки не було чіткої межі між тим, що є «ручним виправленням», а що — узагальненим правилом заснованим на нашому судженні (feature engineering), то в результаті таки дозволили використовувати свої словники виправлень. Єдиною умовою було запостити цей словник на форум за тиждень до кінця змагання (merger deadline). Розуміючи важливість обробки тексту і вважаючи, що ми створили дуже хороший словник, ми не хотіли публікувати його на форумі і шукали шляхи, як автоматизувати велику частину обробки тексту. Така автоматизація призводила до погіршення результатів, а оскільки без обробки тексту ми не могли приступити до перерахунку всіх змінних, то це припиняло подальшу роботу.

Хіба це так складно?

У загальній складності на переписування всього коду за єдиним форматом і перерахунок змінних ми витратили близько місяця (це ще співпало з дефіцитом вільного часу на змагання; дивись примітку 3 на графіку прогресу). Деяке просування ми отримали від побудови ансамблю. Загальна ідея ансамблю — навчити на частини даних багато моделей 1-го рівня з різними настройками і на різних наборах змінних і на підставі прогнозів цих моделей побудувати модель 2-го рівня. Цей підхід добре працює, якщо грамотно розділити дані для навчання та валідації моделей. У нашому випадку це ускладнювалося ще й тим, що дані в train і test відрізнялися по своїй структурі. Використання StratifiedKFold (K разів навчити модель на K-1 частинах даних і зібрати прогнози на інших частинах) призводило до збільшення розриву між результатами на крос-валідації (cross-validation) і на поточному рейтингу (public leaderboard). Тим не менш, ми змирилися з такою схемою побудови ансамблю, так як у міру додавання нових моделей 1-го рівня вона продовжувала покращувати результат на поточному рейтингу.

Таким чином за три тижні до кінця змагання ми довели наш RMSE до 0,44 і все ще були на першому місці з вірою в те, що більшість наших труднощів позаду і залишилося лише трішки натиснути для фінального ривка. І тут почалося об'єднання команд (team merging).

To merge or not to merge?

Навіщо потрібні об'єднання?

Об'єднання команд в першу чергу дає аналогічний ефект додавання нового рівня до ансамблю. Якась лінійна комбінація рішень команд до об'єднання буде краще будь-якого окремо взятого рішення в силу того, що ці рішення сильно відрізняються між собою (мають низький коефіцієнт кореляції, наприклад 0.9). У нашому змаганні цю різницю в чому забезпечувало відмінність у підходах до обробки тексту і генерації змінних.
Другий плюс від об'єднання — це можливість вчитися один у одного, запозичити якісь ідеї і обмінюватися досвідом (для чого, у принципі, існує Kaggle).

— Що сталося?

Ми розуміли, що ближче до merger deadline процес злиттів піде більш інтенсивно, але явно недооцінили масштаб події. Якщо за три тижні до кінця змагання в топ10 було всього кілька команд, де було більше 2-х осіб, то після того, як все закінчилося, в топ10 зовсім не було команд менше трьох осіб (середня кількість учасників у топ10 командах склало 4.6 осіб).
Спочатку ми не планували з кимось об'єднуватися, незважаючи на хороші шанси потрапити в призи: не стільки з жадібності, скільки з бажання зрозуміти конкретно свій рівень. Але приблизно за тиждень до дедлайну об'єднань нас відкинули на 4-5 місце, і ми залишилися чи не єдиною командою з 2-х учасників в топ10 (не рахуючи єдиного на той момент хлопця, який був один). Ми ще раз обговорили ситуацію і вирішили таки спробувати запропонувати йому об'єднатися. На його згоду ми особливо не розраховували: цей хлопець Chenglong Chen одноосібно виграв попередній схоже змагання CrowdFlower Search Relevance, входить в топ-50 рейтингу Kaggle і воліє змагатися один (до нашого змагання він взяв участь приблизно в трьох десятках змагань, і тільки один раз був з ким-то в команді). Ми вважали, що раз він до цих пір продовжує змагатися один, значить не хоче об'єднуватися з ким-небудь. Ми сильно здивувалися і зраділи, коли через 2 години у відповідь на нашу пропозицію побачили привітний і лаконічну відповідь:
“Sure! Just send me a team merge request :) We will discuss in details later."
Певна іронія полягає в наступному: єдиним доступним каналом зв'язку для нас була система внутрішніх повідомлень на Kaggle доступна для учасників з рейтингом вище 500. Так як до цього ми брали участь всерйоз тільки в одному конкурсі, то виявилося, що рейтинг у жодного з нас трохи нижче 500, що не дозволяє відправляти повідомлення. Щасливим збігом послужило те, що інший з нас витратив кілька годин пару місяців тому на інший конкурс, де потрапив у топ90% і цього фантастичного результату вистачило для того, що б отримати можливість надсилати повідомлення. Цілком ймовірно, що якби не цей факт, нашого об'єднання з Ченглонгом не було б, як і не було б цієї статті.

Що це нам дало?

По-перше, після злиття ми оцінили кореляцію наших кращих рішень, і вона за мірками Kaggle виявилася досить низькою 0.87. Просте середнє наших двох рішень дало нам RMSE 0,435 і повернуло нас на друге місце на LB.(примітка 4 на графіку прогресу)
По-друге, ми познайомилися з неймовірно талановитим, приємним і скромним хлопцем, у якого встигли багато чому навчитися за такий невеликий проміжок часу.

Відкриття на фініші.

Часу залишалося всього два тижні, а ми перебували на відстані п'яти часових поясів один від одного. Тому вирішили, що оптимальна стратегія для нас — це обмінятися ідеями, змінними та кодом, але зосередитися на доделывании власних рішень, які потім об'єднаємо простим зважуванням (blending). У підсумку Ченглонг використав частину наших змінним і отримав рішення краще, але зате кореляція між нашими рішеннями збільшилася до 0.94. Тому покращення нашого спільного результату виявилася не такою великою, як нам хотілося б.

Важливість правильної крос-валідації

Як вже говорилося вище, для крос-валідації при побудові ансамблю ми спочатку вчили моделі на 2/3 даних і перевіряли на 1/3 даних. Цей підхід для даного змагання не можна назвати вдалим, оскільки він призводив до все збільшується розриву між CV LB.
Приблизно за місяць до завершення змагання ми написали код, який використовував використовував 1/3 даних для навчання і 2/3 даних для валідації (тобто використовував розбивку, наближену до розбивці між train і test). Розрив між CV LB значно зменшився, проте результати погіршилися. Тому ми продовжили дотримуватися початкової розбиття.
Забігаючи наперед, скажемо, що в той момент ми зробили помилку. Ми отримали хороші результати при старій стратегії крос-валідації не тому, що ця стратегія була кращою (вона була гіршою), а тому, що ансамбль будувався на сотнях моделей, які були побудовані в різні періоди при різних підходах до обробки тексту і підрахунку змінних. Використання таких різних підходів у цьому змаганні поліпшувало рішення. Приблизно за тиждень до кінця ми перерахували всі змінні за єдиним алгоритмом (нам потрібно було зробити відтворюване рішення, щоб претендувати на призове місце) і жахнулися, що отримали гірше результат. Тут нам знадобився код, який ми відкинули раніше. Сотні моделей ми вже не встигли б перерахувати, але навіть з восьми моделей отримали кращий результат, ніж при старому підході.
Ченглонг ж спочатку використовував більш ефективну розбивку. Справа в тому, що частина пошукових запитів була тільки в train, частина — тільки в test, а частина — і там, і там. Те ж саме з продуктами. Ченглонг звернув на це увагу, і зробив схожий розподіл у частинах для навчання та валідації (малюнок нижче). У підсумку, він отримав на крос-результати валідації, набагато більш наближені до реальності, ніж у нас.
У нас не було часу впроваджувати цю ж крос-валідацію в наше рішення, хоча ми розуміли, що вона краще нашого підходу. Тому ми не стали використовувати змінні від Ченглонга, щоб:
а) зберегти якомога меншу кореляцію між нашими рішеннями
б) отримати ситуацію, в якій найбільш сильне рішення пораховано з використанням правильного алгоритму крос-валідації (для уникнення сюрпризів в кінці)

cross
Малюнок. Розбивка для крос-валідації від Ченглонга

Такий уже й випадковий private?

Буквально в останні дні змагання ми звернули увагу, що у вихідних даних є залежність між ID запису і оцінкою її релевантності. Протягом майже всього змагання ми як і багато інших вважали, що це послідовність записів у даних випадкова. Ми випробували величезне здивування, побачивши, що в залежності від ID можна чітко виділити три різні області, на яких сильно відрізняється середнє значення релевантності. Ще більш дивним було те, що 2 наших кращих рішення абсолютно по-різному поводилися в одній з областей (part 3 на малюнку). До цього результат, який ми бачили на LB відповідав public даними (30% від test), але фінальний результат повинен був бути підрахований на решту 70% test (private). З урахуванням того, що дані були упорядковані явно невипадковим чином, питання полягало в тому, чи є розбивка на public і private теж невипадковою? І яке з наших рішень краще працює на спірній області (part3)?

p1
p2
p3

Для вирішення останнього питання ми склеїли наших два кращих рішення (взяли перші дві частини від одного рішення, а останню частину від іншого). Результат на LB виявився таким же! Це означало, що цілий величезний шматок даних повністю знаходиться в private, і ми поняття не маємо яке з двох наших рішень краще працює на цій частині даних. Так як Kaggle дозволяє вибрати в якості фінального два рішення, то ми вирішили просто вибрати діаметрально різні ваги для спірної частини на наших рішеннях, що б крупно не промахнутися.
Чесно кажучи, ми очікували великого потрясіння в рейтингу за невипадковою розбивки на public/private, але цього не сталося, так як виявилося, що третину всіх даних test була спеціально «заражена» для того, що б відбити бажання у учасників займатися ручною обробкою" тексту. Ця частина даних ніяк не оцінювалася. Вельми жорстокий хід з боку організаторів.

Чесність у збиток результату

Протягом конкурсу ми вважали злочином залишати комп'ютери без розрахунків на ніч і найчастіше вночі вважалися нові моделі для ансамблю. Після того, як нам довелося переписати весь код для отримання відтвореного рішення, у нас залишилося близько 300 різних моделей 1-го рівня, які ми не могли точно відтворити, не мали на це досить часу, і не опублікували старі словники на форумі за тиждень до кінця змагання, як це вимагалося в правилах. Тим не менш, додавання цих моделей до ансамблю давало невелике поліпшення на LB (швидше за все і за те, що ці моделі ставилися до різними версіями обробки тексту). Ми вирішили не використовувати рішення з цими моделями в якості фінального, так як це в нашому розумінні суперечило умовам конкурсу. Ще ми не виключали неприємних сюрпризів з-за невипадкового розподілу даних і вважали стару стару стратегію крос-валідації менш надійною.
Якби ми все-таки зважилися на це, то підсумкове рішення з цими моделями (це було наше хороше рішення в public) принесло б нам 0,43188 на RMSE і перше місце.

Момент істини, висновки і життя після перемоги

Ось і настав момент, коли обидва наших фінальних рішення були готові, і нам залишилося тільки чекати публікації остаточних підсумків на private. До цього моменту ситуація була такою, що ми займали третє місце, з непоганим відривом від нас команда йшла на першому місці, команди з 9-го місця і нижче значно відстали, а результати команд з 2 по 8 місця були досить близькі, тому вони цілком могли помінятися місцями в підсумковому заліку. З урахуванням очікуваного потрясіння ми розуміли, що результат міг бути будь-яким для нас всередині топ вісімки. В заповітні 3 години ночі, після багаторазових оновлень сторінки ми нарешті побачили свій результат. 4-е місце...

Що таке перемога?

Потрясіння було величезним. Другий удар пішов, коли ми побачили, що наше рішення зі старими не відтвореними моделями принесло б нам друге місце. Заснути в ту ніч було нелегко, але ближче до ранку прийшли думки, що за фактом підсумковий розрив між топ-командами нікчемний і факт досягнення висот подібного рівня значущий сам по собі, не кажучи вже про те колосальний досвід і навички, які були отримані в процесі. Грошове винагородження за 3-е місце не було настільки великим, що б це могло ще більше засмучувати, тому через деякий час на зміну смутку прийшли приємні відчуття від добре виконаної роботи. А на наступний день ми дізналися, що команду, яка була на першому місці, дискваліфікували, так як один з її учасників був помічений у використанні декількох акаунтів. Це суворе рішення організаторів принесло нам підсумкове третє місце, якого ми в той момент вже не чекали.

Життя

Після конкурсу нас спіткало моральне та фізичне виснаження, все-таки ми витратили багато часу і сил. Але наївному бажанням відпочити після його завершення не судилося збутися. За два місяці після конкурсу ми додатково:
— зробили повну документацію по нашому рішенню
— підготували интервью
— підготували і провели презентацію дзвінок-конференцію з HomeDepot
— підготували презентацію і виступили для Kaggle ком'юніті в Києві
— написали цю статтю
В цілому це вже були приємні моменти, але все одно на все це пішло набагато більше часу, ніж ми очікували.

Висновки і поради

Підсумки цього змагання можна розбити на дві групи. Перша — це те, що ми для себе зробили з цього змагання:
1. Результат змагання в першу чергу залежить від того, скільки сил і часу ви готові в нього інвестувати. Знання і скіли теж вирішують, але їх недолік в більшості випадків можна і потрібно компенсувати надлишком наполегливості.
2. Навіть сама по собі участь у змагання є корисним і цікавим досвідом, не кажучи вже про те, що це сильно розширює кругозір і дозволяє об'єктивно оцінити свій персональний рівень на фоні гідних конкурентів зі всього світу.
3. Не варто боятися пробувати! Коли починаєш займатися улюбленою справою, то одразу і час на нього, і натхнення. Якщо data science вам цікавий — дерзайте і не пошкодуєте!
Друга — це ті причини, по яким нам вдалося досягти подібного результату:
1. Велика кількість інвестованого часу.
2. Ретельна обробка тексту.
3. Використання досвіду попередніх переможців і більшості класичних підходів, які застосовуються в natural language processing.
4. Правильний розподіл зусиль.
5. Об'єднання з Ченглонгом.
Переконаний, що це не останній наш конкурс на Kaggle, і сподіваюся, що ми зможемо поділитися майбутніми досягненнями.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.