Не ми такі — життя таке: Тематичний аналіз для самих нетерплячих

bayesian

— Чому?
Зараз Relap.io генерує 40 мільярдів рекомендацій в місяць на 2000 медиаплощадках Рунета. Майже будь-яка рекомендаційна система, рано чи пізно, приходить до необхідності брати в розрахунок вміст рекомендованого контенту, і досить швидко впирається в необхідність як його класифікувати: знайти якісь кластери або хоча б знизити розмірність для опису інтересів користувачів, залучення рекламодавців або ще для якихось темних чи не дуже цілей.

Завдання звучить досить очевидно і існує чимало добре зарекомендували себе алгоритмів та їх реалізацій: Латентний розміщення Діріхле (LDA), Імовірнісний латентно-семантичний аналіз (pLSA), явний семантичний аналіз (ESA), список можна продовжити. Однак, ми вирішили спробувати придумати що-небудь більш просте, але разом з тим, життєздатне.

Для такого рішення є кілька причин, але основна з них була лінь і небажання чекати поки моделі натренируются. Якщо говорити більш серйозно, у нас є досить великий обсяг даних з численних джерел (сотні тисяч популярних і мільйони опублікованих статей) і проблема вгадування числа тих, на які ми хочемо все розкидати була досить очевидною (причому до такої міри, що ми навіть не уявляли порядок — 100 тем? 1000?). З такими вступними тренувати LDA моделі або pLSA було б досить неефективно, особливо беручи до уваги постійно зростаючий корпус. Хотілося чого-то швидше, і можливо менш акуратного, але здатного розкидати хоча б 70% документів по купках і заодно з'ясувати кількість і розмір цих купок, а потім і побудувати на їх основі певну онтологію.

— Як?
Як можна підійти до такої задачі: нам очевидно потрібна деяка генеративна модель, погоджує як можна більше слів в якісь теми (семантичні поля).

Незважаючи на бажання замінити велосипед свежеизобретенным самокатом, від основних принципів тематичного аналізу ми не відмовляємося, тобто так само надаємо документи у вигляді невпорядкованих «мішків зі словами» (bag of words), причому вважаємо навіть не власне слова, а леми, які ми отримали прогнавши всі тексти через стеммер Портера. Ми не знімаємо омонимию і не зберігаємо ніякої граматичної інформації. Вибірка складається з коротких новин (публікацій — насправді тільки заголовок і перший абзац). Ми також знаємо, наскільки часто читалася кожна публікація (таке знання може бути корисно для ранжирування власне статей за важливістю/релевантності ітп).

Для того, щоб зрозуміти що ми спростили, пригадаємо спочатку, що таке LDA:


де inline_formula— це імовірність появи пари «документ-слово», вона складається із суми по всіх темах (inline_formula— безліч тем) і твори власне ймовірності документа (обчислюється як відношення довжини документа до довжини корпусу), ймовірності появи слова в темі і ваги теми у документі (вірніше ймовірності присутності теми у документі). Всі складові елементи в сумі можна порахувати за допомогою формули Байєса, проблема полягає в тому, що нам невідомі апріорні розподілу ні для тих, ні для слів. Більше того, документи у нас приблизно однієї довжини, оскільки ми зберігаємо тільки шматочки приблизно однієї довжини, достатні для анотації і тому inline_formulaдля нас нерелевантно, воно не містить ніякої інформації. Іншими словами, в формулах:


нам невідомі ні inline_formulaні inline_formulainline_formulaоднаково для всіх документів, і безпосередньо ми порахувати нічого не можемо. LDA оперує припущенням, що вектор документів inline_formulaпороджується параметричним розподілом з сімейства розподілів Діріхле inline_formula. Ось тут ми і набрели на перше обмеження, що нам не подобається — у нас поки немає ніяких думок з приводу inline_formula, крім тих, що воно, швидше за все, досить велика, а тому оптимізація по такій сім'ї розподілів буде досить важкою обчислювально.

Що тут можна спростити? Давайте подивимося, що можна порахувати без всяких хитрувань і яку користь можна з цього отримати?

Спробуємо що-небудь зовсім примітивне, що таке inline_formula, ймовірність генерації слова темою? Якщо ми знаємо тему тексту, то можна вгадати з якою ймовірністю там зустрінеться слово. Формулу Байєса завжди можна «поставити з ніг на голову» і порахувати ймовірність приналежності слова до теми, а, вірніше, ймовірність присутності теми у документі, що містить слово.
Проблема в тому, що у нас немає розподілу тем, а є лише деяка статистика по словами. Можливо, має сенс спростити наш погляд на корпус і не думати про генерації документів (а це власне основа «правильного» тематичного аналізу) і сконцентруватися виключно на «взаємини» слів.

У нашому випадку тема — це просто набір слів з якимись терезами, які зустрічаються разом в документах, що описують взаємопов'язані речі. Чи можна перевірити належність двох слів до однієї теми? Як нам здається, можна, причому з допомогою досить простих обчислень. Схожий підхід непогано працює для вичленення коллокаций, однак на впорядкованих множинах, ми ж не зберігаємо інформації про порядок слів, але знаємо частоту з якою слова зустрічаються в межах одного документа. Спільне розподіл пар слів всередині одного документа — це порівняно багато пар і велика частина з них буде абсолютно безглузда.

Інтуїтивно, припущення про те, що два слова відносяться до однієї теми, швидше за все, зустрічаються разом частіше ніж два слова з різних тем, не викликає особливих сумнівів. Відразу обмовимося, що ми міркуємо про слова з яскраво вираженою приналежністю до більш-менш чітко окресленої теми: слова «шворінь» і «лада» ймовірно зустрічаються в текстах на автомобільну тематику, а слова «карбюратор» і «майонез» навряд чи зустрінуться разом (або наша фантазія недостатня, щоб придумати приклад). З іншого боку, велика частина дієслів і прикметників цілком гармонійно вписується в текст на практично будь-яку тематику:
Жителя міста N вбило при вибуху величезної шкворня
(автор знає, що шворні зазвичай не вибухають і що міста N в Росії немає) або
Гості були вбиті наповал величезним пирогом з майонезом
Якщо як знайти «семантично навантажені» слова, то має сенс подивитися, які інші слова зустрічаються з ними разом.

Давайте розглянемо:

це ймовірність присутності слова inline_formulaв документі, якщо відомо що там є слово inline_formula, порахувати подібні речі можна безпосередньо з корпусу, однак якщо брати до уваги всі можливі пари ми знову приходимо до необхідності порахувати inline_formulaймовірностей, де inline_formula, тобто розмір нашого словника (словник мови Пушкіна становив близько 40 тисяч вводів, проте новини опубліковані нашими паблишерами за годину містять більше 200 тисяч лем, від висновків, ми точно поки утримаємося).

Слово inline_formulaє своєрідним генератором для слова inline_formulaтаким чином, якщо розумно вибрати генератори залежних слів, то можна отримати якісь осмислені набори слів. Спробуємо?

Повернемося до «семантично значущим» словами, голоси в голові починають тихо, але наполегливо нашіптувати: «tf-idf, tf-idf».

Не будемо боротися з демонами очевидності і спробуємо зрозуміти, як можна використовувати tf-idf для з'ясування того, які з слів важливіше інших. Порахуємо tf-idf в межах кожного документа, скоротимо документи до розумного числа ключових слів (просто відсортувавши слова з їх значеннями tf-idf і зберігши потрібне число слів з найбільшими значеннями). Є надія, що словник зменшиться і розібратися в ньому буде простіше.

З іншого боку, ми скоротили документи, але збільшили «цінність» слів з дуже вузьким значенням: якщо в корпусі зустрілася одна стаття докладно описує шлюбні звички гуигнгнмов, слово «гуигнгнм» отримає високий вагу в цій статті і станемо кандидатом на своє власне семантичне поле, яке безперечно має право на існування, але навряд чи сильно допоможе в подальшій класифікації нових статей. Уникнути цього можна, агрегировав tf-idf слів по всьому корпусу і ще раз ранжирувавши слова, в цей раз не всередині документів, а по всьому корпусу.

Що вийшло?
Щоб не бути голослівними, подивимося що вийде якщо взяти вибірку з статей, які читалися за останні півгодини і відсортувати слова, як було нашептано демонами очевидності. Подивимося спочатку, що вийде якщо ми спочатку просто виберемо слова зі значущим tf-idf (без агрегації, значення tf-idf дорівнює середньому по всім статтям, де слово зустрічалося):
латинін, leagoo, меланом, матрон, матеріал, поліп, табл., ssd-накопител, двач, турнирн, fitch…
Слова непогані, в тому сенсі, що вони явно вказують на якісь чітко окреслені теми, однак незрозуміло дійсно важливі теми в нашому корпусі, який містить приблизно 280 тисяч коротких статей. Спробуємо агрегувати і подивимося, що вийшло:
бортжурна, музыкальн, зайц портал, скачучи, бесплатн, нов, так, лад, котор, сам…
Тут виходить якась нісенітниця: часто зустрічаються слова навіть з покаранням за частотою все одно «спливають» наверх. Спробуємо з цим боротися, просто викинувши найпопулярніші слова з розгляду. Без особливих роздумів, ми викинули 300 слів з найнижчим idf, ось, що вийшло (для зрозумілості замість топ-10, виведемо топ-30 слів).
вулиць, удачн, критер, храм, тис, lifan, повноцінного, кр, бискв, підняли, брит, цб, pres, ознака, лід, включений, магнитн, бородін, дол, машин, взаимодейств, виключений, snow, педикюр, салфетк, твор, латинін, michael, est, компетенц, згвалтований…
Цей список вже більш осмислений: по-перше ми зустрічаємо згадку «латинін» (на нульовому місці перший раз і на 26-му в останньому списку), це явно прізвище, і мабуть з даним персонажем сталося, щось важливе (швидше за все, Юлія Латиніна, але ми поки не можемо гарантувати). Lifan, це марка автомобіля, чия присутність логічно — значний відсоток трафіку в цій вибірці йде через автомобільні форуми. Інші слова зі списку теж виглядають логічно — трафіку завжди є обговорення рецептів («бискв»), економіки (цп) тощо. Просто подивившись на список, навряд чи можна з легкістю зрозуміти, що хвилює читачів в даний момент, але вже можна помітити, що слова відносяться до різних тем і подій. Поки цього достатньо — ми просто шукаємо з чого почати, чи не так?

Почнемо власне генерацію тим — поки що ми не замислюємося скільки тим вийде а просто візьмемо якусь (більшу) частину отриманого списку і згенеруємо теми, а потім вже подумаємо, що з ними робити.

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



Почнемо з досить розслабленого вимоги, поставимо inline_formulaі подивимося, що вийде, для зручності читання, ми взяли тільки початкові слова кожної теми (теми виходять досить довгі, числа після слова — це ймовірності):
0 = "(бортжурна,List((бортжурна,1.0), (mazda,0.02639662123248224),
(mercedes-benz,0.025020797337940742), (subaru,0.02498880143341652),
(пріор,0.024668842388174312), (octavia,0.024380879247456324),
(передн,0.024316887438407882), (sedan,0.02098931336788891),
(калин,0.01785371472451526)…

1 = "(музыкальн,List((музыкальн,1.0), (feat,0.031221582297665956),
(пісня,0.016469637263817317), (dj,0.013438415681519652),
(олександр,0.012630089926240274), (ірин,0.012326967768010509),
(володимир,0.011417601293321209), (коло,0.008992624027483076),
(миха,0.008487420430433464), (серг,0.008386379711023543),
(григір,0.007982216833383854), (каспійськ,0.007780135394564009),
(віктор,0.007780135394564009), (вантаж,0.007679094675154087),
(лепс,0.0072749317975143975)…

2 = "(зайц,List((зайц,1.0), (feat,0.03158217497955847),
(пісня,0.01655764513491415), (dj,0.013593622240392478),
(олександр,0.012775960752248568), (ірин,0.012367130008176616),
(володимир,0.011549468520032708), (коло,0.009096484055600982),
(миха,0.00848323793949305), (серг,0.008381030253475062),
(григір,0.008074407195421096), (каспійськ,0.007869991823385119),
(віктор,0.007869991823385119), (вантаж,0.0077677841373671305),
(лепс,0.0073589533932951765)…

3 = "(портал,List((портал,1.0), (feat,0.031572494124859504),
(пісня,0.01655256973536324), (dj,0.013589455400020435),
(олександр,0.012772044548891385), (ірин,0.012363339123326864),
(володимир,0.011443751915806682), (коло,0.009093695718810668),
(миха,0.008480637580463881), (серг,0.008378461224072748),
(григір,0.008071932154899356), (каспійськ,0.007867579442117094),
(віктор,0.007867579442117094), (вантаж,0.007765403085725963),
(лепс,0.007356697660161438)…

4 = "(скачучи,List((скачучи,1.0), (feat,0.028736234923964345),
(пісня,0.01688515993707394), (торрент,0.016255899318300997),
(ігор,0.014263240692186683), (олександр,0.012690089145254328),
(ірин,0.012480335605663346), (володимир,0.01101206082852648),
(dj,0.01101206082852648), (коло,0.009229155742003147),
(миха,0.008495018353434716), (серг,0.008390141583639224)…

5 = "(бесплатн,List((бесплатн,1.0), (feat,0.028751311647429174),
(пісня,0.016684155299055613), (ірин,0.01280167890870934),
(олександр,0.012591815320041973), (володимир,0.011017838405036727),
(dj,0.010912906610703044), (коло,0.009233997901364114),
(миха,0.008604407135362015), (серг,0.008289611752360966),
(григір,0.0080797481636936), (каспійськ,0.007869884575026232),
(віктор,0.007869884575026232), (вантаж,0.00776495278069255),
(лепс,0.007345225603357817)…

6 = "(нов,List((нов,1.0), (выбер,0.04891791522602125),
(комплектація ліні,0.04046612882571392), (событ,0.028812908182865922),
(телекана,0.026892047637341526), (відгук,0.02650787552823665),
(tut,0.02612370341913177), (подмосков,0.025995646049430145),
(адреса,0.023306441285695992), (html,0.021641695479574848),
(news,0.02087335126136509), (вчер,0.020745293891663463),
(свіжий,0.02023306441285696), (област,0.019592777564348827),
(поставши,0.0145985401459854), (інформаційного,0.014342425406582149),
(гродн,0.013317966448969137)…

17 = (росс,List((росс,1.0), (сборн,0.0731070496083551),
(єдиний,0.04960835509138382), (президент,0.03953748601268183),
(путін,0.029093621782916825), (праймеріз,0.023125699365908244),
(хокк,0.01939574785527788), (володимир,0.019022752704214847),
(країн,0.0175307720999627), (тренер,0.0175307720999627),
(голів,0.01566579634464752), (рф,0.015292801193584483),
(чемпіонат,0.014546810891458413)…


Як нескладно помітити, теми з 1 по 5 насправді описують одне і теж, а тема 17, навпаки, перемішує кілька тим разом (насправді це останні новини про Росію). Цю проблему потрібно якось вирішувати.

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

Згадаймо, що коефіцієнт Жаккара для кінцевих множин inline_formulainline_formulaобчислюється за формулою:


безпосередньо застосовувати його до тем не має сенсу, оскільки навіть для підмножини, якщо його кардинальність сильно менше кардинальність більшого безлічі, коефіцієнт Жаккара буде сильно менше одиниці, що логічно, але нам не годиться. Замість цього ми можемо, наприклад, відсортувати теми по довжині і почати порівнювати саму коротку тему з темами більшої довжини, якщо більше половини слів теми збігаються зі словами іншої теми, їх варто злити. Подивимося, що вийшло (знову по 10 слів на початку кожної теми):
0 = "(бортжурна,List((бортжурна,1.0), (mazda,0.02639662123248224), (mercedes-benz,0.025020797337940742), (subaru,0.02498880143341652), (пріор,0.024668842388174312), (octavia,0.024380879247456324), (передн,0.024316887438407882), (sedan,0.02098931336788891), (калин,0.01785371472451526), (astra,0.017789722915466818)…

1 = "(музыкальн,List((скачучи,1.0), (зайц,1.0), (портал,1.0), (бесплатн,1.0), (музыкальн,1.0), (feat,0.030372759594695493), (пісні,0.016629833474044852), (торрент,0.016255899318300997), (ігор,0.014263240692186683), (олександр,0.012691999938535306), (dj,0.012509292152232418), (ірин,0.012467890282777335),

2 = "(нов,List((нов,1.0), (відгук,0.5132539377641183), (выбер,0.2469259179654335), (комплектація ліні,0.24270002476527985), (событ,0.028812908182865922), (телекана,0.026892047637341526), (tut,0.02612370341913177), (подмосков,0.025995646049430145), (адреса,0.023306441285695992), (html,0.021641695479574848), (news,0.02087335126136509), (вчер,0.020745293891663463),

3 = "(так,List((так,1.0), (лат,0.046851128840604314), (грец,0.035817348497708366), (см,0.03513834663045323), (сущ,0.02987608215922594), (синонім,0.025123069088439993), (чоловік,0.021728059752164318), (мн,0.01952130368358513), (кількість,0.018842301816329992), (дружин,0.01850280088270243), (ср,0.01850280088270243), (термін,0.01782379901544729),

4 = "(лад,List((лад,1.0), (пріор,0.5873114649209881), (хетчбек,0.43989485258120614), (седа,0.4370012256029478), (калин,0.4247207293150209), (універсальні., 0.13181770509728907), (4x4,0.08554572271386432), (грант,0.0830172777075432), (3d,0.0777496839443742), (спорт,0.07026217566672686),

5 = "(котор,List((котор,1.0), (вещ,0.04718016238753566), (сто,0.028966425279789335), (книг,0.023041474654377878), (допоможуть,0.021724818959842), (ваш,0.017774851876234364), (факт,0.015141540487162607), (полезн,0.014702655255650647), (зірок,0.013385999561114768), (зрад,0.013385999561114768), (хоче,0.01294711432960281), (дівчину,0.01163045863506693), (слів,0.01141101601931095), (подборк,0.01141101601931095), (знаменитост,0.01097213078779899), (місць,0.010752688172043012),

20 = (рецепт,List((рецепт,1.0), (приготовлений,0.1684643040575244), (пошагов,0.13405238828967642), (кулинарн,0.11145351823317926), (салат,0.1027221366204417), (страв,0.04982023626091423), (підготувати,0.044170518746789934), (торт,0.0421160760143811), (пиріг,0.04006163328197227), (суп,0.03543913713405239), (курей,0.03338469440164355), (швидкий,0.029275808936825888),

Нарешті! Григорій Лепс знаходиться тільки в одній темі, російський автопром відокремився від абстрактних автомобільних розмов, а курка потрапила в одну купку з супом, пирогом і прикметником швидкий! На тлі загального благорастворения виділяється тема 2, яка містить незрозуміло що. Якщо придивитися до неї докладніше, то можна помітити, що багато слів у цій темі можуть належати до будь-якої іншої теми — від таких слів можна позбутися просто виключивши слова, повторювані більше, ніж в inline_formula, де inline_formulaпідібраний якимось чином параметр, також варто видалити слова з низьким idf, ми не використовували їх як генератори, але нічого не забороняє нам отримати їх при розрахунку ймовірностей.

Повернемося трохи назад і подивимося на самий перший згенерований список — чи можна якось використовувати його? Природно, що кожне слово згенерує щось, і таких буде багато і їх доведеться зливати, що буде довго: зливання тим разом займає квадратичне час від числа тим. Чи можна отримати велику тему з слів на кшталт «ssd-накопичувач»? Демони здорового глузду наполягають, що можна і періодично повторюють слова на кшталт «ієрархія» і «онтологія», нам тільки залишається інтерпретувати ці поняття максимально примітивно і знову підсунути їм формулу Байєса.

Спробуємо наступне — подумаємо про ієрархію як про дерево, де найбільш загальні поняття знаходяться в корені, а найбільш вузькі за значенням слова — в листі. В такому випадку «ssd-накопичувач» це лист дерева, корені якого сидить «комп'ютер», або «технології», або щось подібне, якщо ми зможемо відновити хоча б частину цього дерева, у нас вийде непогана, хоча й неповна тема. Спробуємо, псевдо-рекурсію на таких генераторах. Термін псевдо-рекурсія, був придуманий тільки що і під ним ми розуміємо виклик генерації тим для кожного згенерованого слова в свежепридуманной темі, таку операцію (після нормалізації) можна викликати до тих пір, поки ми не почнемо отримувати слова про які не годяться для класифікації (ми вже знайшли подібні слова, перевіривши їх idf).

Подивимося, що вийшло?
семг = томат, яск, parmalat, малосольн, мус, прощ, соус, зелений, царск, сливочн, гарнір, пір, канап, перепелин, праздничн, закуск, наивкусн, солений, грат, привіт, любител, рулетик, запеканк, рыбн, голів, семг, сніданок, суп, хоче, картофельн, равиол, засолений, бородинск, духовк, крем-сир, ух, узятий, ка, салат, горбуш, смак, сол, пакет, замечательн, стейк, легк, готовий, медальйон, рулет, приготований…

тошнот = утр, печії, dream, поширений симптом, допомага, вниз, сильн, жажд, блювоти, рідко, ролик, життя, корм, тяжест, чувствова, може, гестоз, изгаг, провісник, недавньому брифінгу підт, проснула, білок, утрен, країн, головокружен, дні, тошнот
В принципі непогано: «сьомга» згенерувала тему про здорове харчування, а наступна тема про те, що щось пішло не так. Насправді теми довше, ми просто показуємо невеликі шматочки. Ще більш цікавий приклад:
розгін = нів, газ, собол, баргузин, калин, 4х4, хетчбек, пріор, v8, urban, сектор, седа, універсальні., 5d, тестований, розгін, 4x4, газел, 3d
Тут одна з характеристик автомобіля генерує поле про автомобілі загалом, збільшивши число викликів, ми зможемо згенерувати більше слів, коли таких полів багато їх можна злити разом, як описано вище.

Трохи подивившись на пару формул та пояснення до них, нескладно помітити, що в результаті, як завжди, вийшов наївний байєсовський класифікатор зі всякими емпіричними прийомами для підбору параметрів і без розміченого тренувального корпусу. Останнє для нас важливо: багато, розмічати щось вручну або навіть в напівавтоматичному режимі не хочеться, а тому потрібно навчання без вчителя. Як не дивно, такий підхід незважаючи на свою простоту, непогано працює на великих обсягах документів і дозволяє хоч якось розкласти їх на купки, а потім вже люто-скажено продавати памперси молодим батькам, а моторні масла — автолюбителям!
Джерело: Хабрахабр

0 коментарів

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