Почему?

Сейчас Relap.io генерирует 40 миллиардов рекомендаций в месяц на 2000 медиаплощадках Рунета. Почти любая рекомендательная система, рано или поздно, приходит к необходимости брать в расчет содержимое рекомендуемого контента, и довольно быстро упирается в необходимость как-то его классифицировать: найти какие-то кластеры или хотя бы понизить размерность для описания интересов пользователей, привлечения рекламодателей или еще для каких-то темных или не очень целей.

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

Для такого решения есть несколько причин, но основная из них была лень и нежелание ждать пока модели натренируются. Если говорить более серьезно, у нас есть довольно большой объем данных из многочисленных источников (сотни тысяч популярных и миллионы опубликованных статей) и проблема угадывания числа тем, на которые мы хотим все разбросать была совсем неочевидна (причем до такой степени, что мы даже не представляли порядок — 100 тем? 1000?). С такими вводными тренировать LDA модели или pLSA было бы весьма неэффективно, особенно принимая во внимание постоянно растущий корпус. Хотелось чего-то побыстрее, и, возможно, менее аккуратного, но способного разбросать хотя бы 70% документов по кучкам и заодно выяснить число и размер этих кучек, а потом и построить на их основе некую онтологию.

Как?

Как можно подойти к такой задаче: нам очевидно нужна некоторая генеративная модель, увязывающая как можно больше слов в некие темы (семантические поля).

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

Для того, чтобы понять что мы упростили, вспомним сначала, что такое LDA:


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


нам неизвестны ни , ни , а одинаково для всех документов, и напрямую мы посчитать ничего не можем. LDA оперирует предположением, что вектор документов порождается параметрическим распределением из семейства распределений Дирихле . Вот тут мы и набрели на первое ограничение, которое нам не нравится — у нас пока нет никаких мыслей по поводу , кроме тех, что оно, скорее всего, достаточно большое, а потому оптимизация по такой семье распределений будет довольно тяжелой вычислительно.

Что здесь можно упростить? Давайте посмотрим, что можно посчитать безо всяких ухищрений и какую пользу можно из этого извлечь?

Попробуем что-нибудь совсем примитивное, что такое , вероятность генерации слова темой? Если мы знаем тему текста, то можно угадать с какой вероятностью там встретится слово. Формулу Байеса всегда можно «поставить с ног на голову» и посчитать вероятность принадлежности слова к теме, а, вернее, вероятность присутствия темы в документе, содержащем слово.

Проблема в том, что у нас нет распределения тем, а есть только некоторая статистика по словам. Возможно, имеет смысл упростить наш взгляд на корпус и не думать о генерации документов (а это собственно основа «правильного» тематического анализа) и сконцентрироваться исключительно на «взаимоотношениях» слов.

В нашем случае тема — это просто набор слов с какими-то весами, которые встречаются вместе в документах, описывающих взаимосвязанные вещи. Можно ли проверить принадлежность двух слов к одной теме? Как нам кажется, можно, причем с помощью довольно простых вычислений. Похожий подход неплохо работает для вычленения коллокаций, однако на упорядоченных множествах, мы же не храним информации о порядке слов, но знаем частоту с которой слова встречаются в пределах одного документа. Совместное распределение пар слов внутри одного документа — это сравнительно много пар и большая часть из них будет совершенно бессмысленна.

Интуитивно, предположение о том, что два слова относящиеся к одной теме, скорее всего, встречаются вместе чаще чем два слова из разных тем, не вызывает особых сомнений. Сразу оговоримся, что мы рассуждаем о словах с ярко выраженной принадлежностью к более-менее четко очерченной теме: слова «шкворень» и «лада» вероятно встречаются в текстах на автомобильную тематику, а слова «карбюратор» и «майонез» вряд ли встретятся вместе (либо наша фантазия недостаточна, чтобы придумать пример). С другой стороны, большая часть глаголов и прилагательных вполне гармонично вписывается в текст на практически любую тематику:

Жителя города N убило при взрыве огромного шкворня

(автор знает, что шкворни обычно не взрываются и что города N в России нет) или

Гости были убиты наповал огромным пирогом с майонезом

Если как-то найти «семантически нагруженные» слова, то имеет смысл посмотреть, какие другие слова встречаются с ними вместе.

Давайте рассмотрим:

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

Слово является своеобразным генератором для слова , таким образом, если умно выбрать генераторы зависимых слов, то можно получить какие-то осмысленные наборы слов. Попробуем?

Вернемся к «семантически значимым» словам, голоса в голове начинают тихо, но настойчиво нашептывать: «tf-idf, tf-idf».

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

С другой стороны, мы сократили документы, но увеличили «ценность» слов с очень узким значением: если в корпусе встретилась одна статья подробно описывающая брачные повадки гуигнгнмов, слово «гуигнгнм» получит высокий вес в этой статье и станем кандидатом на свое собственное семантическое поле, которое несомненно имеет право на существование, но вряд ли сильно поможет в последующей классификации новых статей. Избежать этого можно, агрегировав tf-idf слов по всему корпусу и еще раз ранжировав слова, в этот раз не внутри документов, а по всему корпусу.

Что получилось?

Чтобы не быть голословными, посмотрим что получится если взять выборку из статей, которые читались за последние полчаса и отсортировать слова, как было нашептано демонами очевидности. Посмотрим сначала, что получится если мы сначала просто выберем слова со значимым tf-idf (без агрегации, значение tf-idf равно среднему по всем статьям, где слово встречалось):

латынин, leagoo, меланом, матрон, mатериал, полип, табл, ssd-накопител, двач, турнирн, fitch…

Слова неплохие, в том смысле, что они явно указывают на какие-то четко очерченные темы, однако непонятно действительно ли важны темы в нашем корпусе, который содержит примерно 280 тысяч коротких статей. Попробуем агрегировать и посмотрим, что получилось:

бортжурна, музыкальн, зайц, портал, скача, бесплатн, нов, так, лад, котор, сам…

Тут получается какая-то ерунда: часто встречающиеся слова даже с наказанием по частоте все равно “всплывают” наверх. Попробуем с этим бороться просто выбросив самые популярные слова из рассмотрения. Без особых размышлений, мы выбросили 300 слов с самым низким idf, вот, что получилось (для понятности вместо топ-10, выведем топ-30 слов).

улиц, удачн, критер, храм, тыс, lifan, полноцен, кр, бискв, подня, брит, цб, pres, признак, лид, включен, магнитн, бородин, дол, машин, взаимодейств, исключен, snow, педикюр, салфетк, твор, латынин, michael, est, компетенц, изнасилован…

Этот список уже более осмысленный: во-первых мы встречаем упоминание «латынин» (на нулевом месте первый раз и на 26-м в последнем списке), это явно фамилия, и видимо с данным персонажем произошло, что-то важное (скорее всего, это Юлия Латынина, но мы пока не можем этого гарантировать). Lifan, это марка автомобиля, чье присутствие ожидаемо — значительный процент трафика в этой выборке идет через автомобильные форумы. Остальные слова из списка тоже выглядят логично — в трафике всегда есть обсуждение рецептов («бискв»), экономики («цб») и тому подобное. Просто посмотрев на список, вряд ли можно с легкостью понять, что волнует читателей в данный момент, но уже можно заметить, что слова относятся к разным темам и событиям. Пока этого достаточно — мы же просто ищем с чего начать, не так ли?

Начнем собственно генерацию тем — пока что мы не задумываемся сколько тем получится а просто возьмем какую-то (большУю) часть получившегося списка и сгенерируем темы, а потом уже подумаем, что с ними делать.

Перед тем, как вывалить темы на всеобщее обозрение, потратим еще пару минут на обдумывание критерия того, какие слова сохранить в теме, а какие выбросить после того, как вероятности посчитаны. Ставить какую-то жесткую отсечку по абсолютному значению, не стоит — в зависимости от размера темы, условные вероятности могут разниться довольно сильно. Вместо этого попробуем отношение с наиболее вероятным словом в теме: где , зададим какой-то уровень отсечки и будем отбрасывать все слова отношение вероятности которых и максимальной вероятности слова в теме ниже:



Начнем с довольно расслабленного требования, поставим и посмотрим, что получится, для удобства чтения, мы взяли только начальные слова каждой темы (темы получаются довольно длинные, числа после слова — это вероятности):

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, наоборот, перемешивает несколько тем вместе (на самом деле это последние новости про Россию). Эту проблему нужно как-то решать.

Начнем с повторяющихся тем. Очевидным решением было бы слить вместе темы, в которых встречается много общих слов, единственное, с чем нужно определиться, это понимание того, что значит много и как это «много» оценить, можно просто использовать коэффициент Жаккара, можно вместо пересчета элементов складывать их вероятности и опять посчитать коэффициент Жаккара, главное, чтобы в результате похожие вещи можно было объединить.

Вспомним, что коэффициент Жаккара для конечных множеств и вычисляется по формуле:


напрямую применять его к темам не имеет смысла, поскольку даже для подмножества, если его кардинальность сильно меньше кардинальности бОльшего множества, коэффициент Жаккара будет сильно меньше единицы, что логично, но нам не годится. Вместо этого мы можем, например, отсортировать темы по длине и начать сравнивать самую короткую тему с темами большей длины, если больше половины слов темы совпадают со словами какой-то другой темы, их стоит слить. Посмотрим, что получилось (опять по 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, которая содержит непонятно что. Если присмотреться к ней поподробнее, то можно заметить, что многие слова в этой теме могут принадлежать к любой другой теме — от таких слов можно избавиться просто исключив слова, повторяющиеся больше, чем в тем, где подобранный каким-то образом параметр, также стоит удалить слова с низким idf, мы не использовали их как генераторы, но ничего не запрещает нам получить их при расчете вероятностей.

Вернемся немного назад и посмотрим на самый первый сгенерированный список — можно ли как-то использовать его? Естественно, что каждое слово сгенерирует что-то, и таких тем будет много и их придется сливать, что будет долго: сливание тем вместе занимает квадратичное время от числа тем. Можно ли получить большую тему из слов вроде «ssd-накопитель»? Демоны здравого смысла настаивают, что можно и периодически повторяют слова вроде «иерархия» и «онтология», нам только остается интерпретировать эти понятия максимально примитивно и опять подсунуть им формулу Байеса.

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

Посмотрим, что получилось?

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

тошнот = утр, изжог, dream, распространен, симптом, помога, вниз, сильн, жажд, рвот, редк, ролик, жизн, корм, тяжест, чувствова, моч, гестоз, изгаг, предвестник, недавн, проснула, белок, утрен, стран, головокружен, дне, тошнот

В принципе неплохо: «семга» сгенерировала тему про здоровое питание, а следущая тема о том, что что-то пошло не так. На самом деле темы длиннее, мы просто показываем небольшие кусочки. Eщё более интересный пример:

разгон = нив, газ, собол, баргузин, калин, 4х4, хэтчбек, приор, v8, urban, сектор, седа, универса, 5d, тестирован, разгон, 4x4, газел, 3d

Здесь одна из характеристик автомобиля генерирует поле об автомобилях в общем, увеличив число вызовов, мы сможем сгенерировать больше слов, когда таких полей много их можно слить вместе, как описано выше.

Немного посмотрев на пару формул и объяснения к ним, несложно заметить, что в результате, как обычно, получился наивный байесовский классификатор со всякими эмпирическими уловками для подбора параметров и без размеченного тренировочного корпуса. Последнее для нас важно: данных много, размечать что-то вручную или даже в полуавтоматическом режиме не хочется, а потому нужно обучение без учителя. Как ни странно, такой подход несмотря на свою простоту, неплохо работает на больших объемах документов и позволяет хоть как-то разложить их на кучки, а потом уже люто-бешено продавать памперсы молодым родителям, а моторные масла — автолюбителям!