Не мы такие — жизнь такая: Тематический анализ для самых нетерпеливых
Сейчас Relap.io генерирует 40 миллиардов рекомендаций в месяц на 2000 медиаплощадках Рунета. Почти любая рекомендательная система, рано или поздно, приходит к необходимости брать в расчет содержимое рекомендуемого контента, и довольно быстро упирается в необходимость как-то его классифицировать: найти какие-то кластеры или хотя бы понизить размерность для описания интересов пользователей, привлечения рекламодателей или еще для каких-то темных или не очень целей.
Задача звучит довольно очевидно и существует немало хорошо зарекомендовавших себя алгоритмов и их реализаций: Латентное размещение Дирихле (LDA), Вероятностный латентно-семантический анализ (pLSA), явный семантический анализ (ESA), список можно продолжить. Однако, мы решили попробовать придумать что-нибудь более простое, но вместе с тем, жизнеспособное. Для такого решения есть несколько причин, но основная из них была лень и нежелание ждать пока модели натренируются. Если говорить более серьезно, у нас есть довольно большой объем данных из многочисленных источников (сотни тысяч популярных и миллионы опубликованных статей) и проблема угадывания числа тем, на которые мы хотим все разбросать была совсем неочевидна (причем до такой степени, что мы даже не представляли порядок — 100 тем? 1000?). С такими вводными тренировать LDA модели или pLSA было бы весьма неэффективно, особенно принимая во внимание постоянно растущий корпус. Хотелось чего-то побыстрее, и, возможно, менее аккуратного, но способного разбросать хотя бы 70% документов по кучкам и заодно выяснить число и размер этих кучек, а потом и построить на их основе некую онтологию.
Как можно подойти к такой задаче: нам очевидно нужна некоторая генеративная модель, увязывающая как можно больше слов в некие темы (семантические поля).
Несмотря на желание заменить велосипед свежеизобретенным самокатом, от основных принципов тематического анализа мы не отказываемся, то есть все так же представляем документы в виде неупорядоченных «мешков со словами» (bag of words), причем считаем даже не собственно слова, а леммы, которые мы получили прогнав все тексты через стеммер Портера. Мы не снимаем омонимию и не храним никакой грамматической информации. Выборка состоит из коротких новостей (публикаций — на самом деле только заголовок и первый абзац). Мы также знаем, насколько часто читалась каждая публикация (такое знание может быть полезно для ранжирования собственно статей по важности/релевантности итп).
Для того, чтобы понять что мы упростили, вспомним сначала, что такое LDA:
где — это вероятность появления пары «документ-слово», она состоит из суммы по всем темам ( — множество тем) и произведения собственно вероятности документа (вычисляемая как отношение длины документа к длине корпуса), вероятности появления слова в теме и веса темы в документе (вернее вероятности присутствия темы в документе). Все составные элементы в сумме можно посчитать с помощью формулы Байеса, проблема состоит в том, что нам неизвестны априорные распределения ни для тем, ни для для слов. Более того, документы у нас примерно одной длины, поскольку мы храним только кусочки примерно одной длины, достаточные для аннотации и поэтому для нас нерелевантно, оно не содержит никакой информации. Иными словами, в формулах:
нам неизвестны ни , ни , а одинаково для всех документов, и напрямую мы посчитать ничего не можем. LDA оперирует предположением, что вектор документов порождается параметрическим распределением из семейства распределений Дирихле . Вот тут мы и набрели на первое ограничение, которое нам не нравится — у нас пока нет никаких мыслей по поводу , кроме тех, что оно, скорее всего, достаточно большое, а потому оптимизация по такой семье распределений будет довольно тяжелой вычислительно.
Что здесь можно упростить? Давайте посмотрим, что можно посчитать безо всяких ухищрений и какую пользу можно из этого извлечь?
Попробуем что-нибудь совсем примитивное, что такое , вероятность генерации слова темой? Если мы знаем тему текста, то можно угадать с какой вероятностью там встретится слово. Формулу Байеса всегда можно «поставить с ног на голову» и посчитать вероятность принадлежности слова к теме, а, вернее, вероятность присутствия темы в документе, содержащем слово.
Проблема в том, что у нас нет распределения тем, а есть только некоторая статистика по словам. Возможно, имеет смысл упростить наш взгляд на корпус и не думать о генерации документов (а это собственно основа «правильного» тематического анализа) и сконцентрироваться исключительно на «взаимоотношениях» слов.
В нашем случае тема — это просто набор слов с какими-то весами, которые встречаются вместе в документах, описывающих взаимосвязанные вещи. Можно ли проверить принадлежность двух слов к одной теме? Как нам кажется, можно, причем с помощью довольно простых вычислений. Похожий подход неплохо работает для вычленения коллокаций, однако на упорядоченных множествах, мы же не храним информации о порядке слов, но знаем частоту с которой слова встречаются в пределах одного документа. Совместное распределение пар слов внутри одного документа — это сравнительно много пар и большая часть из них будет совершенно бессмысленна.
Интуитивно, предположение о том, что два слова относящиеся к одной теме, скорее всего, встречаются вместе чаще чем два слова из разных тем, не вызывает особых сомнений. Сразу оговоримся, что мы рассуждаем о словах с ярко выраженной принадлежностью к более-менее четко очерченной теме: слова «шкворень» и «лада» вероятно встречаются в текстах на автомобильную тематику, а слова «карбюратор» и «майонез» вряд ли встретятся вместе (либо наша фантазия недостаточна, чтобы придумать пример). С другой стороны, большая часть глаголов и прилагательных вполне гармонично вписывается в текст на практически любую тематику:
Если как-то найти «семантически нагруженные» слова, то имеет смысл посмотреть, какие другие слова встречаются с ними вместе.
это вероятность присутствия слова в документе, если известно что там есть слово , посчитать подобные вещи можно напрямую из корпуса, однако если принимать во внимание все возможные пары мы опять приходим к необходимости посчитать вероятностей, где , то есть размер нашего словаря (словарь языка Пушкина составлял около 40 тысяч вводов, однако новости опубликованные нашими паблишерами за час содержат больше 200 тысяч лемм, от выводов, мы точно пока воздержимся).
Слово является своеобразным генератором для слова , таким образом, если умно выбрать генераторы зависимых слов, то можно получить какие-то осмысленные наборы слов. Попробуем?
Вернемся к «семантически значимым» словам, голоса в голове начинают тихо, но настойчиво нашептывать: «tf-idf, tf-idf».
Не будем бороться с демонами очевидности и попробуем понять, как можно использовать tf-idf для выяснения того, какие из слов важнее других. Посчитаем tf-idf в пределах каждого документа, сократим документы до разумного числа ключевых слов (просто отсортировав слова по их значениям tf-idf и сохранив нужное число слов с наибольшими значениями). Ecть надежда, что словарь уменьшится и разобраться в нем будет попроще.
С другой стороны, мы сократили документы, но увеличили «ценность» слов с очень узким значением: если в корпусе встретилась одна статья подробно описывающая брачные повадки гуигнгнмов, слово «гуигнгнм» получит высокий вес в этой статье и станем кандидатом на свое собственное семантическое поле, которое несомненно имеет право на существование, но вряд ли сильно поможет в последующей классификации новых статей. Избежать этого можно, агрегировав tf-idf слов по всему корпусу и еще раз ранжировав слова, в этот раз не внутри документов, а по всему корпусу.
Что получилось?
Этот список уже более осмысленный: во-первых мы встречаем упоминание «латынин» (на нулевом месте первый раз и на 26-м в последнем списке), это явно фамилия, и видимо с данным персонажем произошло, что-то важное (скорее всего, это Юлия Латынина, но мы пока не можем этого гарантировать). Lifan, это марка автомобиля, чье присутствие ожидаемо — значительный процент трафика в этой выборке идет через автомобильные форумы. Остальные слова из списка тоже выглядят логично — в трафике всегда есть обсуждение рецептов («бискв»), экономики («цб») и тому подобное. Просто посмотрев на список, вряд ли можно с легкостью понять, что волнует читателей в данный момент, но уже можно заметить, что слова относятся к разным темам и событиям. Пока этого достаточно — мы же просто ищем с чего начать, не так ли?
Начнем собственно генерацию тем — пока что мы не задумываемся сколько тем получится а просто возьмем какую-то (большУю) часть получившегося списка и сгенерируем темы, а потом уже подумаем, что с ними делать.
Перед тем, как вывалить темы на всеобщее обозрение, потратим еще пару минут на обдумывание критерия того, какие слова сохранить в теме, а какие выбросить после того, как вероятности посчитаны. Ставить какую-то жесткую отсечку по абсолютному значению, не стоит — в зависимости от размера темы, условные вероятности могут разниться довольно сильно. Вместо этого попробуем отношение с наиболее вероятным словом в теме: где , зададим какой-то уровень отсечки и будем отбрасывать все слова отношение вероятности которых и максимальной вероятности слова в теме ниже:
Начнем с довольно расслабленного требования, поставим и посмотрим, что получится, для удобства чтения, мы взяли только начальные слова каждой темы (темы получаются довольно длинные, числа после слова — это вероятности):
0 (музыкальн,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.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.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 http://tex.s2cms.ru/svg/%5Cinline%20A" alt="inline_formula"/> и вычисляется по формуле:
напрямую применять его к темам не имеет смысла, поскольку даже для подмножества, если его кардинальность сильно меньше кардинальности бОльшего множества, коэффициент Жаккара будет сильно меньше единицы, что логично, но нам не годится. Вместо этого мы можем, например, отсортировать темы по длине и начать сравнивать самую короткую тему с темами большей длины, если больше половины слов темы совпадают со словами какой-то другой темы, их стоит слить. Посмотрим, что получилось (опять по 10 слов в начале каждой темы): 0 (музыкальн,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.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.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, которая содержит непонятно что. Если присмотреться к ней поподробнее, то можно заметить, что многие слова в этой теме могут принадлежать к любой другой теме — от таких слов можно избавиться просто исключив слова, повторяющиеся больше, чем в тем, где подобранный каким-то образом параметр, также стоит удалить слова с низким idf, мы не использовали их как генераторы, но ничего не запрещает нам получить их при расчете вероятностей.
Вернемся немного назад и посмотрим на самый первый сгенерированный список — можно ли как-то использовать его? Естественно, что каждое слово сгенерирует что-то, и таких тем будет много и их придется сливать, что будет долго: сливание тем вместе занимает квадратичное время от числа тем. Можно ли получить большую тему из слов вроде «ssd-накопитель»? Демоны здравого смысла настаивают, что можно и периодически повторяют слова вроде «иерархия» и «онтология», нам только остается интерпретировать эти понятия максимально примитивно и опять подсунуть им формулу Байеса.
Попробуем следущее — подумаем об иерархии как о дереве, где наиболее общие понятия находятся в корне, а наиболее узкие по значению слова — в листьях. В таком случае «ssd-накопитель» это лист дерева, в корне которого сидит «компьютер», или «технологии», или что-то подобное, если мы сможем восстановить хотя бы часть этого дерева, у нас получится неплохая, хотя и неполная тема. Попробуем, псевдо-рекурсию на подобных генераторах. Термин псевдо-рекурсия, был придуман только что и под ним мы понимаем вызов генерации тем для каждого сгенерированного слова в свежепридуманной теме, такую операцию (после нормализации) можно вызывать до тех пор, пока мы не начнем получать слова о которые не годятся для классификации (мы уже нашли подобные слова, проверив их idf).
Посмотрим, что получилось?
семг = томат, ярк, parmalat, малосольн, мусс, прощ, соус, зелен, царск, сливочн, гарнир, пор, канап, перепелин, праздничн, закуск, наивкусн, солен, грат, привет, любител, рулетик, запеканк, рыбн, голов, семг, завтрак, суп, хочет, картофельн, равиол, засолен, бородинск, духовк, крем-сыр, ух, взят, картофел, салат, горбуш, вкус, сол, пакет, замечательн, стейк, легк, готов, медальон, рулет, приготовлен…
тошнот = утр, изжог, dream, распространен, симптом, помога, вниз, сильн, жажд, рвот, редк, ролик, жизн, корм, тяжест, чувствова, моч, гестоз, изгаг, предвестник, недавн, проснула, белок, утрен, стран, головокружен, дне, тошнот
Здесь одна из характеристик автомобиля генерирует поле об автомобилях в общем, увеличив число вызовов, мы сможем сгенерировать больше слов, когда таких полей много их можно слить вместе, как описано выше.
Немного посмотрев на пару формул и объяснения к ним, несложно заметить, что в результате, как обычно, получился наивный байесовский классификатор со всякими эмпирическими уловками для подбора параметров и без размеченного тренировочного корпуса. Последнее для нас важно: данных много, размечать что-то вручную или даже в полуавтоматическом режиме не хочется, а потому нужно обучение без учителя. Как ни странно, такой подход несмотря на свою простоту, неплохо работает на больших объемах документов и позволяет хоть как-то разложить их на кучки, а потом уже люто-бешено продавать памперсы молодым родителям, а моторные масла — автолюбителям!