Імовірнісні моделі: від наївного Байеса до LDA, частина 1

    Продовжуємо розмову. Минула стаття була перехідною від попереднього циклу про графічних моделях взагалі (частина 1 , частина 2 , частина 3 , частина 4 ) до нового міні-циклу про тематичному моделюванні: ми поговорили про Семплірування як методі виводу в графічних моделях. А тепер ми починаємо шлях до моделі латентного розміщення Дирихле (latent Dirichlet allocation) і до того, як всі ці чудові алгоритми семплювання застосовуються на практиці. Сьогодні — частина перша, в якій ми зрозуміємо, куди є сенс узагальнювати наївний байесовский класифікатор, і заодно трохи поговоримо про кластеризації.
 
 
 
 
 Класифікація: наївний Байес
Тематичне моделювання вирішує класичну задачу аналізу текстів — як створити вірогідну модель великої колекції текстів, яку потім можна буде використовувати, наприклад, для інформаційного пошуку (information retrieval), класифікації або, як у нашому випадку, для рекомендацій контенту. Ми вже говорили про одну з найпростіших моделей, що намагаються вирішити це завдання — про широко відомий наївному байесовском класифікаторі. Можна, звичайно, класифікувати тексти і по-іншому — за допомогою методу опорних векторів, наприклад, або логістичної регресії, або будь-якого іншого класифікатора — однак наївний Байес буде нам зараз найбільш корисний як приклад для подальшого узагальнення.
 
У моделі наївного байєсівського класифікатора кожному документу присвоюється прихована змінна, відповідна його темі (взятої з заздалегідь визначеного дискретного набору, наприклад «фінанси», «культура», «спорт»), і слова умовно незалежні один з одним при даній темі. Кожній темі відповідає дискретний розподіл на словах, з якого вони породжуються; ми просто припускаємо, що слова умовно незалежні за умови теми:
 
У результаті кожна тема представляє собою дискретний розподіл на словах. Можна уявити собі величезний нечесний кубик, який ви кидаєте, щоб отримати наступне слово, або мішок слів, в який ви не дивлячись запускаєте руку, щоб витягнути наступне. Нечесний мішок, правда, важче уявити — ну, скажімо, кожне слово на камушках в мішку зустрічається по кілька разів, причому різні слова по-різному (вся ця інтуїція нам ще знадобиться, bear with me for a moment). У вас є один мішок, на якому написано «фінанси», другий — «Культура», третій — «Спорт»:
 
І коли ви «генеруєте» з цих мішків новий документ в наївному Байес, ви спочатку вибираєте мішок (кидаючи кубик), а потім з цього мішка починаєте вибирати слова одне за іншим:
 
 
 
Графічна модель цього процесу виглядає дуже просто (про те, як читати ці картинки, ми говорили в першій частині попереднього циклу, а під другій частині навіть був приклад саме наївного байєсівського класифікатора). Зліва — графічна модель повністю, в центрі — модель одного документа з плашкою, яка приховує повторювані однакові змінні, а праворуч — та ж модель, але для всього датасета, з явно виділеними змінними α і β, які містять параметри всіх цих дискретних розподілів:
 
 
 
Вона теж показує, що наївний Байес складається з одного дискретного розподілу (кубика), яким визначається порівняльний «вагу» тим, і декількох дискретних розподілів (мішків), за кількістю тем, які показують ймовірності випадання того чи іншого слова в темі.
 
А щоб навчити наївний Байес (та й будь-який інший класифікатор, тут вже нікуди не дінешся), потрібно мати розмічений набір текстів, на яких можна буде навчати ці розподілу:
 
 
 
При навчанні наївного Байеса ми для кожного документа знаємо його тему, і залишається навчити тільки розподіл слів у кожній темі окремо і ймовірності випадання тем:
 
 
Для цього достатньо просто підрахувати, скільки разів те чи інше слово зустрілося в тій чи іншій темі (і скільки разів теми зустрічаються в датасете), а результат згладити по Лапласа.
 
У наївного байєсівського класифікатора видно відразу два напрямки, за якими його можна було б розширити і поліпшити:
     
  • наскільки необхідно мати розмічений датасет? розмічати датасет руками дуже дорого, а датасет потрібен досить великий, тому що ми навчаємо розподіл всіх слів у даній темі; може бути, можна як-небудь так, без міток, якщо уміючи?
  •  
  • в реальних датасетах хіба що твіти будуть мати одну добре певну тему; наприклад, новину «захисник« Челсі »і збірної Бразилії Давид Луїс був проданий в« ПСЖ »більш ніж за 40 мільйонів фунтів стерлінгів » неабияк зіпсує нашу модель, адже тут поєднуються слова про спорт і про фінанси, і в результаті або спортивна тема отримає «контамінацію» з фінансових слів, або навпаки; чи можна зробити так, щоб у одного документа було кілька тем?
  •  
Ці розширення і приведуть нас поступово до моделі LDA.
 
 Від класифікації до кластеризації
Почати буде логічно з першого напряму, про те, як перейти до обробки датасетов без міток, адже навіть якщо ми зробимо модель, в якій у кожного документа кілька тем, розмітити великий датасет руками, та ще й на кілька тем для одного документа, буде вкрай скрутно. Отже, давайте уявимо, що у нас є датасет, що складається з текстів, і ми припускаємо, як і в наївному Байес, що кожен документ був породжений з однієї-єдиної теми. Різниця тільки в тому, що тепер ми не знаємо, з якої саме, і завдання для нас виглядає так:
 
 
 
Давайте припускати (ми і в LDA будемо так робити; щоб від цього позбутися, потрібні непараметричні методи, до яких нам ще далеко), що число потенційних категорій (різних мішків зі словами) нам відомо, невідомо тільки їх зміст. Таким чином, імовірнісна модель виглядає точно так само:
 ,
і розподілу в ній все ті ж. Різниця тільки в тому, що раніше ми при навчанні знали для кожного документа його тему, а тепер не знаємо. Інакше кажучи, спільний розподіл, з якого породжуються документи, все те ж: якщо позначити через w вектор слів і через c категорію документа D , його загальний правдоподібність буде
 
де β c — це розподіл в мішку слів, відповідному категорії c ; а загальне правдоподібність, яке потрібно максимізувати при навчанні — це, відповідно,
 
і максимізувати його треба як і раніше по α і β c . Але якщо раніше ми робили це при відомих c , і завдання максимізації розбивалася з окремих тем і була по суті тривіальної, то тепер треба максимізувати при невідомих c , тобто фактично взявши очікування по них:
 
Як це зробити?
 
Те, що у нас вийшло, насправді є абсолютно стандартної завданням кластеризації : є багато об'єктів (текстів) в багатовимірному просторі (слів), і потрібно розбити їх на окремі класи так, щоб тексти в одному класі були б якомога більше схожі один на одного і при цьому якомога менше схожі на тексти в інших класах. Так що тут може допомогти стандартний інструмент навчання моделей кластеризації — EM-алгоритм (від слів Expectation-Maximization, зараз зрозумієте чому). EM-алгоритм призначений для ситуацій, коли в моделі є приховані змінні (як у нас c ), і потрібно максимізувати правдоподібність моделі по її параметрах (у нас це α і β), але в очікуванні по прихованим змінним. EM-алгоритм спочатку ініціалізує модель якимись початковими значеннями, а потім итеративно повторює два кроки:
     
  • E-крок — знайти очікування (expectation) прихованих змінних при даній моделі;
  •  
  • M-крок — максимізувати правдоподібність (maximization), вважаючи змінні рівними своїм очікуванням, знайденим на E-кроці.
  •  
У нашому випадку на Е-кроці ми просто знаходимо ймовірності того, що кожен документ належить різним категоріям, при фіксованих α і β:
 
А потім на М-кроці вважаємо ці ймовірності приналежності фіксованими і оптимізуємо α і β (краще зі згладжуванням α 0 і β 0 , відповідним певним апріорним розподілом на параметри α і β):
 
Потім це все потрібно повторити доти, поки α і β зійдуться; це і є ЕМ-алгоритм для кластеризації, застосований до випадку дискретних атрибутів (слів в документах).
 
Загальна ідея того, чому EM-алгоритм, власне, працює, така: на кожному Е-кроці EM-алгоритм фактично будує допоміжну функцію від параметрів моделі, яка в поточному наближенні стосується функції правдоподібності і при цьому скрізь залишається менше неї (мінорізует функцію правдоподібності). Ось картинка з одного з джерел на цю тему (чесно зізнаюся, забув, з якого саме):
 
А потім на М-кроці ЕМ-алгоритм знаходить параметри, максимизирующие цю допоміжну функцію. Очевидно, що при цьому ми переходимо в точку, в якій загальна правдоподібність збільшується. Я не буду зараз докладно заглиблюватися в доказ того, що EM-алгоритм дійсно це все робить і дійсно коректно працює, нам важлива тільки загальна ідея.
 
 Що далі
Сьогодні ми зробили перший з двох кроків на шляху від наївного байєсівського класифікатора до LDA: перейшли від завдання класифікації, в якій у кожного документа в навчальному датасете повинна бути фіксована категорія, до задачі кластеризації, в якій документи не обов'язково повинні бути розмічені за категоріями. Відзначимо, до речі, що якщо у вас все-таки розмічена частина документів (це називається semi-supervised learning), це дуже легко додати в вийшла модель. Потрібно просто зафіксувати відповідні змінні c i (D ), зробити їх рівними одиниці в розміченій темі і нулю у всіх інших, і в рамках EM-алгоритму лише навчати ці змінні, залишаючи їх значення фіксованими. Такий «пасивний датасет» буде, до речі, дуже корисний для подальшого навчання моделі.
 
Наступного разу ми зробимо другий крок на шляху до латентного розміщенню Дирихле: від категорій, що присвоюються всьому тексту цілком, перейдемо до тем, яких у кожному документі може бути кілька.
    
Джерело: Хабрахабр

0 коментарів

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