Рекомендаційні системи в онлайн-освіті. Продовження

Ми продовжуємо розповідати про системі адаптивного навчання на Stepic.org. Першу вступну частину цієї серії можна почитати тут.
У даній статті ми розповімо про побудову рекомендаційної системи (яка і лежить в основі адаптивності). Розповімо про зборі та обробці даних, про графах переходів, хендлерах, оцінці реакції користувача, формуванні видачі.
Згадаємо про лінійну регресію, регуляризацию і навіть зрозуміємо, чому в нашому випадку краще використовувати гребневую регресію, а не яку-небудь ще.


Загальні слова
Рекомендаційна система на Stepic.org пропонує користувачеві нові уроки (освітній контент) на підставі того, що він цікавився раніше. Вона використовує для цього різноманітні способи знайти контент, чимось схожий на той, який користувач вже вивчав, або ж не настільки схожий, але в цілому цікавий.
Кожен з таких способів оформлений у вигляді окремої функції (хендлера), яка витягує список уроків по закладеному в нього принципом і розмічає їх вагами в залежності від того, наскільки вони підходять користувачеві. Докладний опис цих функцій-хендлеров буде нижче.
Рекомендаційна система може застосовуватися в різних ситуаціях. Два основних випадки:
  • звичайна рекомендація для конкретного користувача, яка показується йому на головній сторінці і у вкладці «Рекомендовані уроки», а також час від часу надсилається на пошту;
  • контекстна рекомендація, яка показується користувачеві після проходження уроку поза курсу (тобто уроку, для якого немає фіксованого наступного за ним), як підказка, що подивитися далі.
Разом з рекомендацією користувачеві також показується інформація про те, чому йому був запропонований саме цей урок. Цю інформацію легко витягти завдяки тому, що в кожну функцію-хендлер закладена якась інтуїція, так що можна відновити причину рекомендації.
дані
У процесі навчання Stepic.org користувач залишає значний цифровий слід. Крім інформації про його прогрес зберігаються також відомості про те, коли він відвідував різні кроки (крок — елементарна одиниця контенту; кроки об'єднуються в більш великі уроки), коли намагався вирішувати завдання і з яким результатом, і навіть як він дивився відео: які встановив швидкість і гучність, де зупиняв і де перемотував.
Найбільш цікаві для базової рекомендаційної системи такі відомості: теги (тобто галузі знань, якими протегированы уроки), якими цікавився, уроки, на які він заходив, уроки, які він вивчив, а також, якщо рекомендація контекстна, поточний урок.
Крім інформації про конкретного користувача, збережені дані можна розглядати як відомості про взаємодію користувачів з контентом. Одним із способів агрегувати і використовувати ці відомості виявилися графи переходів, про які розповімо докладніше.
Графи переходів
Часто буває корисно дізнатися, як користувачі вивчають контент, що вони дивляться частіше, що рідше, які матеріали проскакують, на які повертаються, і, що важливо, в якому порядку їх дивляться. Використовуючи логи про дії користувачів, нескладно дати відповіді на ці питання. Ми використовували для цього граф переходів process map), тобто такий орієнтований граф, в якому вершинами будуть одиниці контенту (наприклад, кроки або уроки), а ваги дуг будуть показувати кількість переходів між цими одиницями контенту.
У кожного користувача в балці є тимчасова мітка. Дії також бувають різних типів, наприклад, "viewed" (відкрив крок), "succeeded attempt" (вирішив задачу) або "commented" (залишив коментар). Нас будуть цікавити дії користувача по відношенню до кроків, які потім легко узагальнити на уроки, до яких ці кроки належать, і навіть на теги, якими позначені уроки.
Візуально граф переходів можна уявити собі як послідовність вершин-матеріалів (наприклад, кроків), між деякими з яких є дуги. Наявність дуги між двома кроками означає, що існують користувачі, які переглянули їх один за одним. Кожна дуга має міткою, що містить число таких користувачів. Приклад графа переходів для кроків одного уроку всередині курсу:

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

З цього фрагменту видно, що крок з теорією Т4 пропускають частіше звичайного і переходять до наступного за ним.
Далі ми стали будувати графи переходів не тільки по кроках, але також по урокам і тегам, щоб використовувати це в рекомендаційній системі. Граф переходів по урокам будується за тим же принципом, що і для кроків, просто дії над кроками розглядаються як дії над уроками, до яких ці кроки належать. Для тегів аналогічний процес: дії з кроками переводяться в дії з їх тегами.
Хендлеры
Тут ми перерахуємо функції-хендлеры, кожна з яких реалізує свій спосіб рекомендацій. Хендлер приймає в якості параметрів користувача, і, якщо рекомендація контекстна, то урок, на якому користувач знаходиться в даний момент. Хендлер повертає для користувача imageсписок уроків, кожному з яких відповідає вага від 0 до 1. Чим більше вага, тим краще рекомендація: image.
Нехай ми хочемо порекомендувати користувачеві imageуроки по конкретному тегу, для якого частка пройдених користувачем уроків становить image. У разі, якщо за нього немає графа переходів, всі його уроки отримують вага image. Якщо ж граф є, то для кожного уроку ця вага ділиться на відстань у графі до найближчого попереднього уроку, пройденого користувачем image. Таким чином реалізується ідея, що може бути цікаво проходити матеріали, розташовані у графі переходів недалеко від вже вивчених ним.
  • Уроки з цікавими користувачеві тегами — хендлер рекомендує уроки, позначені тегами, які користувач уже вивчав. Для цього використовується описана вище рекомендація по тегам, вага уроку imageдля користувача imageскладатиме image.
  • Незакінчені уроки — рекомендуються уроки, які користувач починав і не закінчив, з вагою тим більшим, чим більшу частину уроку користувач вивчив: image, частка уроку image, пройденого користувачем image.
  • Популярні уроки — хендлер не використовує інформацію про користувача, а рекомендує просто найпопулярніші за останній тиждень уроки на платформі. Вага прямо пропорційний популярності: image, де image— номер уроку imageу списку популярних уроків.
  • Шляхи по урокам — використовуються шляху, містять уроки, які користувач проходив, рекомендуються уроки слідом за пройденими, з вагою тим меншим, чим далі урок від вже пройдених: image, де image— відстань від уроку imageдо найближчого передує в дорозі уроку, пройденого користувачем image.
  • Граф переходів по тегам — рекомендуються уроки з тегами, які вивчають після тегів, які цікавлять користувача. Ваги залежать від прогресу користувача по тегам, а також від відносних частот переходів між тегами. Нехай image— частота переходу від тега, уроки якого користувач вивчав, до деякого тегу image. Тоді для уроку image, позначеного тегом image, вага рекомендації користувачу imageimage.
  • Уроки по тегам від схожих користувачів (коллаборативная фільтрація) — на основі цікавлять користувача тегів виявляються користувачі з схожими на його інтересами, і рекомендуються уроки з тегами, які вони самі вивчають. Нехай у поточного користувача imageзнайшовся схожий на нього користувач image, причому міра схожості між ними — image(лежить між 0 і 1, чим вона більше, тим більше схожі користувачі). Тоді урок image, позначені тегом, який вивчав image, будуть рекомендуватися з вагою image.
  • Граф переходів з уроків (тільки при контекстних рекомендаціях) — хендлер рекомендує уроки, наступні за поточним у графі переходів, вага залежить від відносної частоти переходу між поточним уроком і рекомендованим. Якщо перехід з поточного уроку в урок imageвчиняється з відносною частотою imageimage.
  • Шляхи по урокам (тільки при контекстних рекомендаціях) — рекомендуються уроки, наступні за поточним у будь-яких шляхах, ваги обернено пропорційні відстані між уроками: image, де image— відстань від уроку imageдо поточного уроку.
  • Якщо всі попередні хендлеры в сукупності порекомендували менше уроків, ніж було потрібно, рекомендації додаються випадкові уроки, вага таких уроків дорівнює 0.
Розібралися? Добре, йдемо далі.
стартруперы
Оцінка реакції користувача
Щоб зрозуміти, наскільки успішною виявилася рекомендація, після її показу ми фіксуємо, перейшов користувач за посиланням, а також яку частину від уроку користувач у результаті вивчив (значення від 0 до 1). У той же час у користувача є можливість дізнатися, чому урок був посоветован (варіанти відповідають хендлерам), і позначити рекомендацію як не йому цікаву.
В результаті кожної показаної рекомендації ми можемо зіставити деяке число: imageвідповідає відмови від рекомендацій, image1— переходу по посиланню без вивчення уроку image2— переходу по посиланню і повного вивчення уроку, значення image1image2— неповного вивчення уроку, а image0— відсутності реакції.
Формування видачі
Отже, ми отримали списки уроків від декількох хендлеров, в яких кожного уроку зіставлений вага від 0 до 1. Чим більше, тим більш вдалою оцінює хендлер цю рекомендацію. Постає питання, як їх краще всього комбінувати?
Можна було б просто для кожного уроку скласти або перемножити ваги хендлеров, які його порадили. Але це означало б, що ми вважаємо різні хендлеры однаково корисними, що, взагалі кажучи, може бути зовсім не так. Хотілося б оцінити кожен хендлер коефіцієнтом корисності, використовуючи при цьому реакції користувачів на рекомендації. Таким вимогам задовольняє проста лінійна регресія.

Регресійна модель навчається з використанням накопичених даних про те, як рекомендації різних хендлеров були оцінені користувачем. Виходячи з цього, модель формує вектор ваг для хендлеров. Далі, коли нам потрібна щось порекомендувати учневі, то регресійна модель для кожного уроку скалярно примножує ваги запропонували його хендлеров з навченим вектором параметрів, і видає результуючий вагу для кожного рекомендованого уроку.
Раз вже ми так заглибилися в матчастину, то давайте опишемо формально регресійну модель. Якщо ви добре знаєте, що таке лінійна регресія, то сміливо пропускайте наступний розділ.
Лінійна регресія
Нехай у нас є матриця image, рядки якої imageназиваються спостереженнями, а стовпці факторами, і стовпець значень цільової або залежною змінної image. Регресійна модель image, де image— параметри моделі, а image— випадкова помилка, що називається лінійної, якщо залежність цільової змінної від факторів є лінійної, image.
Зазвичай для зручності imageконстанту вносять під знак суми, додавши в матрицю спостережень стовпець з одиниць: imageдля всіх image.
image
Використовуючи ці позначення, лінійну регресійну модель можна виписати image. Рішенням цієї задачі будемо вважати стовпець image, який мінімізує суму квадратів відхилень передбачаються значень від реальних, тобто image.
Такий спосіб апроксимації називається методом найменших квадратів ordinary least squares) та є найбільш широко застосовуваним у контексті розв'язання задачі лінійної регресії.
У нашому випадку ми можемо розглядати в якості спостережень, тобто рядків матриці image, рекомендовані уроки, в якості факторів цих спостережень ваги, які хендлеры призначили уроку, а в якості значень цільової змінної — оцінку рекомендації користувачем.
Таким чином, для уроків image, посоветованных користувачам imageвідповідно, і для хендлеров imageматриця спостережень imageі стовпець значень цільової змінної (реакції користувача) imageбудуть виглядати наступним чином:
image
Вектор image, який дає мінімальну помилку передбачення реакції користувача, містить індивідуальний вага для кожного з хендлеров, на який потрібно домножать його рекомендації. Якщо вага якогось з хендлеров відносно великий, значить, цей хендлер вносить позитивний внесок у рекомендації, і навпаки.
Для роботи рекомендаційної системи регресійна модель регулярно перенавчається на даних про реакцію користувачів на рекомендації. Ми використовуємо бібліотеки SciPy для вирішення цієї задачі та знаходження стовпця image. У цій бібліотеці вже реалізовано рішення задачі лінійної регресії.
Розібралися? Відмінно, залишилося трохи.
котики
Регуляризация
Після реалізації рекомендаційної системи з лінійною регресією, яка знаходила стовпець ваг для хендлеров image, що мінімізує квадрат відхилень реальної реакції користувача від передбаченої (image), ми помітили, що поступово вага одного хендлера необмежено зростає, в той час як інші зменшуються, що в підсумку призвело до формування видачі практично тільки з результатів цього хендлера. Такий ефект називається позитивним зворотним зв'язком, і характеризується тим, що відхилення в результатах роботи системи впливає на її подальшу роботу, причому чим далі, тим більше результати зсуваються в бік цього відхилення.
Крім цього, так як хендлеры можуть використовувати дуже схожу інформацію про активність користувача в наших даних також може бути проблема мультиколінеарності факторів, що тягне за собою слабку відособленість матриці imageі, як наслідок, нестабільність рішення.
В результаті ми отримуємо рішення, яке дає маленьку помилку на даних, на яких вона навчається, і велику на реальних даних. Ця ситуація називається перенавчанням overfitting) моделі.
В якості вирішення проблеми перенавчання можна розглянути регуляризацию. Згідно книзі The Elements of Statistical Learning, основні способи регуляризації — це ласо (LASSO, least absolute shrinkage and selection operator) і гребневая регресія (резуляризация Тихонова, ridge regression). Обидва цих методу змінюють вираз, який ми мінімізуємо в процесі пошуку рішення регресії, додаючи до нього штраф на норму вектора image.
У разі ласо-регуляризації використовується image-норма і рішення знаходиться як

У разі ж гребеневої регресії використовується image-норма і рішення виглядає як

В обох випадках параметр imageпідбирається в процесі оптимізації.
Використання регуляризації методом ласо зменшує всі ваги image, а ті, що й так були відносно невеликими, стають рівними нулю. Таким чином, метод ласо добре підходить для вибору значущих факторів (feature selection).
Метод гребеневої регресії також зменшує ваги факторів, але при цьому ніколи не зводить їх до нуля, якщо тільки не image.
Згідно роботі Andrew Ng, ласо-регуляризация працює краще гребеневої в ситуації, коли кількість факторів значно перевершує число навчальних спостережень. У зворотній ситуації більш доречна гребневая регресія.
Відповідно, для нашого випадку краще підходить гребневая регресія. Її реалізація також присутня в бібліотеці SciPy, що нас дуже потішило.
Висновок
У цій статті ми з вами розібралися з тим, як реалізована рекомендаційна система для освітнього контенту на Stepic.org. Іноді, напевно, доводилося нелегко, але вам вдалося! (якщо ви, звичайно, не просто прокрутили до цього місця, тоді радимо повернутися і прочитати)
Переглянути рекомендовану систему у дії можна на https://stepic.org/explore/lessons – там перераховані рекомендовані вам уроки для вивчення. Але якщо ви вперше зайшли на платформу, то рекомендації можуть бути не особливо релевантні.
У наступній і заключній статті цього циклу ми розглянемо безпосередньо адаптивну систему на Стэпике і обговоримо результати виконаної роботи: точність передбачення, уподобання користувачів, оцінимо статистику.
І наостанок хочеться запитати: чи вірите ви в адаптивне онлайн-освіта? Витіснить воно традиційні курси? Чи може сама інтелектуальна рекомендаційна система порадити людині освітній контент так само добре і навіть краще, ніж живий викладач?
Джерело: Хабрахабр

0 коментарів

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