Міський ПЕКЛО: школярі і студенти


Привіт, Хабр. В цьому році у нас досить успішно пройшли експерименти по залученню юних програмістів в ПЕКЛО:
  • затіяли хакатон, де школярі і студенти змагалися на рівних (виграли, до речі, школярі), допомогли організувати олімпіаду НТІ з великим даними.
  • відкрили напрямок Пекельних чудес у літніх школах. Про те, як школярі написали рекомендаційну систему стрічки новин Дощу, освоїли параметричне моделювання (не забувши відлити в силіконі цицьки директору), освоювали ази соціальної інженерії по Митнику, розповімо в наступній статті.
  • організували митапы для "укушених" в Яндексі з Їжаком. Їжак (Олександр Панін) не встояв перед чарівністю юних "датасайнтистов" на хакатоне, з тих пір кожну суботу одна з переговорок перетворюється в Малий ПЕКЛО під звуки арфи, на якій Їжак грає в перервах.
Натхнені завзятістю хлопців, вирішили почати залучати студентів старших. Задумали школи прямо в Москві, вона пройде з 1 по 8 серпня на факультеті комп'ютерних наук ВШЕ, до участі запрошуються всі бажаючі віком до 22 років.

Відбір


Для участі необхідно пройти відбір – вирішити реальну проблему, з якою зіткнувся наш партнер E-Contenta при розробці рекомендаційного движка для Tviz.tv. До 20 липня приймаємо рішення будь-яким способом – цікаво подивитися на нестандартні ідеї, можливо, хто переплюне рішення партнера. Досвідчені учасники мають можливість заявити про себе і виграти грант на безкоштовне навчання.
Розуміємо, що хтось у 20-21 вже рулить R&D у великих компаніях, входить в топ Kaggle. До речі, Семенов став першим у світовому рейтингу. Але хотіли б дати шанс молоді з нуля зануритися в Data Science не за 180 тисяч на курсах для "дорослих". Відбір націлений насамперед на перевірку мотивації.

Відбіркове завдання


Головне завдання — на підставі наявних даних проаналізувати інтереси користувачів і побудувати алгоритм рекомендації нових фільмів.
На початку пропонується вирішити декілька простих аналітичних задач (задачі 1 і 2) за допомогою запропонованих даних, після чого спробувати отримати рішення творчої задачі.
Ідеальне рішення завдання повинно містити: відповідь код, що відтворює цю відповідь, і опис того, що ви зробили. Рішення рекомендується надсилати на мові Python (2.7 або 3.4/3.5). Можна використовувати будь-які бібліотеки, якщо ви готові в розмові пояснити, як вони працюють. Якщо ви списуєте" (запозичаєте матеріали з інтернету) — будьте ласкаві послатися на джерело. Запозичення при зазначеному джерелі не карається, якщо ви здатні пояснити, що саме відбувається в коді і чому він вирішує ту задачу, для якої ви його використовуєте. Списування без вказівки джерела карається завжди.

Дані


Архів з даними можна скачати тут. Частина даних була анонимизирована, частина відсутня – в реальному світі сервера ламаються, дані пропадають. Приклад читання даних.
У ньому ви знайдете:
Вибірку про те, якому глядачеві які фільми сподобалися
train_likes.csvТаблиця з рядками виду user_id, item_id, channel, time.
  • user_id — ідентифікатор глядача
  • item_id — ідентифікатор фільму
  • channel — ідентифікатор каналу
  • time — час (timestamp)
Кожна така четвірка означає, що в момент {time} користувачу {user_id} сподобався фільм {item_id},
який йшов по каналу {channel}.
Описи фільмів
items.jsonМетадані про фільми у форматі json (відкривається будь-яким стандартним json модулем). Кожна строчка обов'язково містить:
  • id — ідентифікатор фільму
  • duration — коефіцієнт тривалості фільму
  • year — коефіцієнт року виробництва
  • genre — номер жанру (категорійна мінлива, всього 10 жанрів)
  • f_{номер} — додаткові ознаки (див. нижче).
Коефіцієнти duration та year — арифметичні перетворення тривалості фільму і року випуску, зроблені для того, щоб зберегти персональні дані.
Ознаки f_* — різні анонимизированные ознаки фільму. Приклади таких ознак — «Країна виробництва — США» або «Бюджет більше $100к» (так — 1, ні — 0 або не є).
Важливо. Рядки з описом є не у всіх фільмів: описано приблизно 2/3 фільмів, які були лайкнуты.
Розклад фільмів
schedule.csvТаблиця з рядками виду time_end, time_start, item_id, channel
  • time_end — час кінця передачі
  • time_start — час початку передачі
  • item_id — id фільму
  • channel — id каналу

Завдання 1

Не всі канали і не всі фільми однаково популярні. Для початку обчисліть, скільки в середньому користувальницьких лайків (
train_likes
) є у одного каналу. Також порахуйте кількість фільмів, у яких є хоча б 5 «лайків». Рекомендований формат виводу – одне дійсне число (середня кількість лайків на канал) і одне ціле (число фільмів з 5+ лайків).
Завдання 2

У глядачів зазвичай є свої жанрові уподобання, причому ці переваги можуть відрізнятися від каналу до каналу. Врахуйте, що не для всіх фільмів відомі їхні жанри — такі фільми доведеться порахувати окремо. Для початку розрахуйте суму лайків для кожного жанру і окремо — для фільмів, де жанр невідомий. Далі обчисліть таку ж суму лайків за жанрами для кожного з топ10 самих залайканных каналів.
Рекомендований формат виводу — рядок з чисел – кількість лайків кожного жанру за зростанням номери жанру, в кінці – кількість лайків для фільмів з невідомим жанром. Далі 10 таких же рядків для кожного з топ10 каналів по популярності. Потрібно пояснити, який саме канал показаний на кожній сходинці.
Завдання 3

Ваша основна мета – навчитися рекомендувати користувачам фільми так, щоб вони їм подобалися. Існує багато способів це зробити, використовуючи досить прості припущення. Наприклад:
  • Вам подобаються фільми схожі на ті, які ви вже полайкали. Якщо у вибірці є фільм, який за ознаками (
    items.json
    ) схожий на інші фільми, які вам сподобалися, то швидше всього цей фільм вам теж сподобається.
  • Схожим користувачам подобаються схожі фільми. Якщо користувачі, які лайкали ті ж фільми, що і ви, як правило лайкають ще 1 фільм, про який ви не знаєте, швидше за все, цей фільм вам сподобається.
  • Канали формують свої програми так, що в один час там йдуть програми, розраховані на приблизно одну і ту ж аудиторію.
  • І так далі

Напуття і допомога


Від Вас в першу чергу потрібно створити мінімальний працездатний рішення. Якщо ви раніше не використовували машинне навчання, можна спробувати використовувати інтуїтивні міркування вище і захардкоженный предсказательная алгоритм.
Далеко не всі такі ідеї виявляться працездатними, тому вам буде потрібно перевіряти, чи працює та чи інша гіпотеза. Наприклад, щоб перевірити, наскільки працює ідея "дивитися на схожих користувачів", можна скористатися метрикою MAP@K або NDCG.
Також ви можете запропонувати свою методику оцінки якості і розповісти нам, чому ви обрали саме її. Обов'язково описуйте всі свої спроби, удачі і невдачі у звіті: будемо знати, чому вас вчити. Ті, хто не зможе взяти участь у школі або старше 22 років, але хотів би спробувати, теж можуть надіслати нам рішення, надішлемо зворотний зв'язок і запросимо в гості.
Багато добра про коллаборативную фільтрацію під спойлером ↓
Baseline в допомогуtl;dr: https://github.com/goto-ru/2016.09-school-baseline.
Підготовлений нами baseline ґрунтується саме на другий ідеї – колаборативної фільтрації.
У нашому алгоритмі ми використовуємо тільки дані про лайки, забуваючи про ознаки фільму. Це дуже грубе припущення, напевно, внесення інформації про зміст фільму істотно поліпшить результат, спробуйте.
Ідея, що лежить в корені нашого методу, полягає в наступному:
  • користувачеві подобаються ті ж фільми, що і схожим на нього користувачам
  • фільм дивляться ті ж користувачі, що дивляться схожі на нього фільми
Іншими словами, у кожного користувача є деякий невідомий нам набір інтересів, який визначає, які фільми подобаються. Фільм, у свою чергу, теж є профіль, відповідальний за те, якою аудиторії він подобається. Ми не знаємо психологічний профіль кожного користувача аудиторію кожного фільму, але можемо відновити його за допомогою вищеописаних ідей.
Косинусні міра

Спочатку ми розглянемо інтуїтивний спосіб рішення задачі заснований на тому, наскільки користувач підходить під аудиторію фільму.
Уявімо дані в форматі
фільм -> подивилися користувачі
. Рекоммендованность фільму item користувачу user порахуємо так:
  • Для кожного фільму, полайканного користувачем user, знайдемо інших людей, яким сподобався фільм.
  • Складемо всіх таких «друзів по лайкам» разом і назвемо сусідами (neighborhood).
  • Для фільму item дізнаємося його аудиторію — безліч користувачів, які його лайкнули
  • Придатність фільму користувачеві, наскільки «друзям по лайкам» користувача подобається цей фільм.
Докладний опис алгоритму.
Цей спосіб, мабуть, краще випадкового ворожіння, однак він розглядає всіх "сусідів" користувача однаково, керуючись лише кількістю разів, коли вони дивилися однакові фільми.
Оскільки користувачі зазвичай дивляться зовсім небагато фільмів, часто буде надаватися, що два користувача з майже ідеально співпадаючими інтересами не мають "загальних" фільмів, хоча фільми одного користувача сподобалися б інакше, якби він про них знав.
SVD
Для того, щоб виправити цей недолік, спробуємо перейти від "користувачів, які дивилися фільми, переглянуті іншим користувачем" до явного отримання "інтересів користувача" і "аудиторії фільму". Цей хід неабияк поліпшить якість результату.
Отже, математика.

Багатий внутрішній світ користувача та художню глибину фільму потрібно закодувати, та ще так, щоб було легко зрозуміти, наскільки близькі два користувача, два фільми або наскільки фільм підходить користувачеві.
Робити це руками ми, мабуть, не захочемо, тому як всі нормальні математики скажімо, що душа користувача обмежується вектором з декількох чисел. Знаючи всю складність і багатогранність людської натури, відведемо під це аж 100 чиселок (будь-яких дійсних чисел). Що конкретно за числа – поки не знаємо.
Фільму для вірності поставимо у відповідність теж 100 чисел. Висловлюючись мовою математиків, ми тільки що ввели 2 вектора — вектор "інтересів користувача" і вектор "аудиторії фільму". Висловлюючись мовою програмістів, ми оголосили 2 масиву, ніяк їх не поставили і без приводу хизуємось.
Тепер давайте зрозуміємо, що ж ми хочемо від цих векторів.
Давайте будемо говорити, що вектора "схожі", якщо їх скалярний добуток велике. Наскільки велике це скалярний твір теж не скажемо – ми ж математики! Скажемо тільки, що в схожих користувачів нехай буде більше, ніж у несхожих. Те ж саме з фільмами – нехай схожі фільми мають скалярний добуток побільше, а несхожі — поменше.
Нарешті, найважливіше – у нас є вектор користувача, є вектор фільму. Давайте захочемо, щоб скалярний добуток вектора користувача на вектор фільму було як можна ближче до 1, якщо користувачеві подобається цей фільм, і до 0, якщо не подобається або не дивився.
Чому так – так от захотіли. Можна було захотіти, щоб якщо фільм не подобається, було -1, а якщо не дивилися — 0, але на жаль, у нас є тільки "лайки" користувачів — дизлайків у вибірці немає.
А тепер перейдемо на більший масштаб. У нас є кілька десятків тисяч користувачів і того більше – фільмів.
Ще ми знаємо, що такі-то користувачі лайкнули такий-то фільм.
Будемо щедрі, дамо по 100 чисел кожному користувачеві, і навіть кожного фільму. Зробити так ми цілком можемо — чиселка під float32 "важить" 4 байти, а нам таких чиселок потрібно за приблизними підрахунками (число користувачів + число фільмів) ~ 10^5.
Нам потрібно, щоб виконувалась головна умова: скалярний твір душі користувача на аудиторію фільму повинна бути ближче до 1, якщо користувач лайкнув фільм, і 0, якщо не лайкнув.
Назвемо вектор i-користувача U_{i}, вектор j-того фільму V_{j}. Для простоти позначень, U— всі користувачі, V— всі фільми.
Домогтися ідеального рівності швидше за все не вийде, причому чим менше чиселок ми дамо на душу/фільм, тим гірше буде наближення, однак нас влаштує, якщо скалярний добуток буде просто досить близько до правильного значення.
Мовою математиків така задача називається задачею оптимізації: ми хочемо підібрати такі вектора користувачів і фільмів, щоб помилка була мінімальною:
\sum_{i,j}((U_{i} ,V_{j})-like_{i,j})\to min,
like_{i,j}=1, якщо користувач U_{i}лайкнув V_{i}, інакше 0.
Нарешті, для підгонки під відомі математики методи, введемо для кожної з 100 компонент векторів "важливість" — єдину для всіх користувачів/фільмів. Формально це — вектор S, в якому знову-таки 100 чиселок.
\sum_{i,j}((U_{i} ,S,V_{j}--like_{i,j})\to min.
Градієнтний спускОдин із способів вирішення завдання можна описати так:
Спочатку ми запишемо в UVвсіх користувачів і фільмів випадкові числа.
Далі в циклі:
  • Вибираємо користувача U_{i}і фільм V_{i}.
  • Вважаємо скалярний добуток векторів USV.
  • Вважаємо "помилку", якщо ми недобрали (помилка негативна) — рухаємо чиселки U_{i}SV_{i}так, щоб скалярний добуток трохи збільшилася. Якщо ми переборщили (помилка позитивна), рухаємо ті ж чиселки у зворотний бік.
  • Нарешті, якщо помилка дорівнює нулю, нічого не міняємо.
    Тепер вибираємо наступного користувача і повторюємо процес до тих пір, поки U, S і V не усталяться приблизно в одних і тих же значеннях. За рахунок того, що ми кожного разу обираємо нового користувача і фільм, такі зменшення-збільшення в середньому за багато ітерацій будуть зменшувати нашу "помилку", і в найкращій мірі виконувати наші "хотілки". Таким чином, через багато ітерацій ми отримаємо-таки придатні для нашої задачі вектора.

Від того, що б навмисно обмежили кількість чиселок в векторах на 100, не даючи ідеально підігнати під всі лайки і не-лайки, нам тільки краще:
  • Ми навчаємо нашу модель на тих лайку, які є у вибірці. Якщо ми будемо давати ідеальні одиниці на полайканных фільмах і ідеальні нулі на неполайканных, ми не зможемо рекоммендовать користувачеві ніякі фільми крім тих, які він вже дивився.
  • Якщо ж наш алгоритм буде спеціально угрублен, то на якихось фільмах з числа неполайканных алгоритм буде давати велику скалярний твір — помилково. Інакше кажучи, начебто інтереси користувача підпадають під типову аудиторію фільму, але ось біда — насправді користувач не лайкнув цей фільм.
  • насправді це ніяка не помилка — якщо фільм так підходить користувачеві, але він його ще не лайкнув, то саме час порекомендувати користувачеві цей фільм, і з великою ймовірністю користувачеві він сподобається.
Переходячи від ідеї до реалізації і від концепції до конкретних методів і структур даних: в простому вигляді достатньо взяти лише пари
user_id <-> film_id
train_likes.csv
; кожна така пара означає, що користувач
user_id
дивився
film_id
(а ще в тому ж файлі є час і канал, що ми ігноруємо). Ми будуємо з цих зв'язків sparse-матрицю суміжності, до якої застосовуємо Truncated Singular Value Decomposition. Цей метод стискає вихідну матрицю, намагаючись знайти таке приховане простір фичей, де вектора фичей користувачів і подобаються їм фільмів близькі; ми отримуємо наближення k-го порядку. Після такого стиснення ми реконструюємо вихідну матрицю з певною помилкою. Саме завдяки цій помилці все і працює: так, фільми, які користувач не дивився, але які подобаються схожим на нього користувачам будуть тепер мати значення не
0
, а
0.4
, тому що ми не могли зберегти всі дані при стисненні, і користувач "змішався" зі схожими на себе.
Код за мотивами всього вищесказаного: матричні розкладання і reproducible-зошити дивитися безкоштовно без СМС.
Ще раз підкреслимо, що вище використовуються тільки мінімально можливі дані: дивився користувач фільм чи ні. Розглядаючи додаткові метадані (наприклад, жанр або час показу), можна значно поліпшити якість передбачення; комбінація методів колаборативної і контент-фільтрації (за допомогою инициализиции, наприклад, матриці ознаками фільмів, отриманими з метаданих) – наступний логічний крок на слизькій доріжці аналізу даних у вирішенні цього завдання.
Інтерфейс рішенняРекомендований інтерфейс – бажано, щоб у вашій програмі була функція, яка приймає параметри (id_пользователя, id_фильма, додаткова інформація) і повертає передбачену ймовірність лайка.
Головне, що буде впливати на оцінку – працездатність рішення (значимо краще, ніж навмання), обґрунтованість оцінки якості рішення, і тільки потім – фінальне якість. Просте працююче рішення, яке чесно проаналізовано, завжди краще, ніж божевільна суміш всього того, що ви знайшли в інтернеті, про яке не зрозуміло, як воно працює і завищена оцінка якості. Машинне навчання використовувати бажано, але не обов'язково.
Крім такої системи від вас хочеться отримати звіт у довільному форматі, з якого можна зрозуміти, що саме ви робили і чому, а також як ви оцінювали якість вашої рекомендаційної системи. Рекомендований максимальний обсяг звіту — 3000 символів, включаючи пробіли (assert len(u"""ваш звіт""") <=3000).
Чекаємо всі можливі рішення, і навіть з великим нетерпінням – рішення без застосування ML. Головне ж мотивація, а незнання ML – це вірна ознака того, що школа буде корисна.
Джерело: Хабрахабр

0 коментарів

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