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_formula, а inline_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 и сохранив нужное число слов с наибольшими значениями). Ecть надежда, что словарь уменьшится и разобраться в нем будет попроще.

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

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


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

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

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

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

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

Перед тем, как вывалить темы на всеобщее обозрение, потратим еще пару минут на обдумывание критерия того, какие слова сохранить в теме, а какие выбросить после того, как вероятности посчитаны. Ставить какую-то жесткую отсечку по абсолютному значению, не стоит — в зависимости от размера темы, условные вероятности могут разниться довольно сильно. Вместо этого попробуем отношение с наиболее вероятным словом в теме: inline_formula где inline_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_formula и inline_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, распространен, симптом, помога, вниз, сильн, жажд, рвот, редк, ролик, жизн, корм, тяжест, чувствова, моч, гестоз, изгаг, предвестник, недавн, проснула, белок, утрен, стран, головокружен, дне, тошнот

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

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

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

Комментарии (17)


  1. Mugik
    27.05.2016 02:00

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


    1. edwardoid
      27.05.2016 09:38

      Та же история только у меня вместе с LDA был PA. И у меня такое же желание вернуться «в эту муть» :)


  1. evnuh
    27.05.2016 02:31

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


    1. recompileme
      27.05.2016 11:25
      +1

      Из эксперимента проведенного автором статьи неизвестно об объеме трафика и стандартном отклонении для изменения объема трафика.
      Однако автор сообщает, что для него изменение глубины просмотра по сегментам на 2,2 и 2,5% попадает в стат. ошибку.
      Если предположить, что изменения трафика происходит по нормальному закону и вспомнить правило 3х сигм, то стандартное отклонение будет около 0,8%. По нашему опыту столь высокими показателями стандартного отклонения обладают как правило площадки с не очень большим объемом трафика 100-500 уников в день. Что вобщем косвенно подтверждают скриншоты, приведенные автором: http://z-force.info/wp-content/uploads/2015/09/kolichestvo-klikov-v-bloke-pohozhih-zapisey-685x270.jpg

      При таких объемах трафика к сожалению все еще довольно много шумов и рекомендации тут пока не могут иметь ключевое значение для посетителя. Ни о семантическом анализе ни о коллаборативной фильтрации при таком объеме трафика говорить не приходится и скорее всего здесь отработал алгоритм популярное, что косвенно подтверждают скриншоты http://z-force.info/wp-content/uploads/2015/09/primer-blokov-600x301.jpgВедущими факторами лояльности посетителя к площадке будут полезность контента, удобство дизайна и уже потом наличие рекомендаций. Возможно автор статьи не совсем корректно сделал выводы о результатах работы рекомендательного блока.


      1. recompileme
        27.05.2016 11:46

        Нашли домен, о котором по всей видимости пишет автор, количество статей на сайте -14, количество посетителей в день на ближайшем в рейтинге li сайте- 118 на 300 просмотров (на оригинальном домене статистика скрыта). Опять же, судя по скриншотам, блок дал порядка 40 дополнительных кликов в/день. Не так уж плохо для подобного сайта, наверное.


    1. recompileme
      27.05.2016 11:34

      С результатами внедрения блока на более крупных площадках можно ознакомиться на нашем сайте: relap.io — в разделе кейсы.


      1. cynovg
        27.05.2016 11:50

        На Мегамозге была недавно статья, счас уже на Хабр попала: https://habrahabr.ru/company/surfingbird/blog/300120/


  1. elingur
    27.05.2016 10:21

    Помниться, на одном из семинаров по кластеризации соц.медиа, докладчик убедительно демонстрировал, что больше всего в интернете «говорят» о кулинарии. Однако, это не так. Дело в том, что тема «кулинария» отлично кластеризуется (всегда образует четкий кластер), как, кстати, и «авто». Поэтому появление этих тем в топе как раз не удивительно. Вот все остальное кластеризовать труднее, приходится придумывать всякие «костыли».
    Я бы рекомендовал запихать в bag of words би- и триграммы (не все, а верх частотного распределения), потому что при вашей нормализации, например, «грант» может быть очень далеко от «лады», если есть новости по, скажем, президентским грантам.
    А вообще вопрос, долго ли строиться матрица tfidf на получасовом потоке? Ведь ее размер сотни тысяч на сотни тысяч, причем сильно разряженных данных. Обычно это занимает значительное время.


    1. diourinski
      27.05.2016 16:16

      Хорошее замечание — даже наивный Байес хорошо вылавливает кулинарию или автомобили, и делает это лучше чем с более абстрактными темами.

      Мое упоминание автомобилей, как большой части трафика, однако, базируется не на том, что мы смогли отнести к этой теме много урлов (про классификацию и распределение по темам мы поговорим позже), а на том, что мы знаем какие сайты посвящены автомобильной тематике (не выученные данные, а знания об окружающем мире собранные у менеджеров по продажам). Для иллюстрации пропорций: за 26 мая у нас залогировано 113 989 677 прочтений страниц, из которых 7 114 967 гарантировано по автотематике.

      Примером производительности может служить пересчет на последних 30 минутах:

      got 3265319 hits
      on 502801 urls
      выгребло из базы и лемматизировало за 5 мин
      из этого оно за пару минут нагенерировало 159 тем (изначально выбирали 300 “верхних” слов)

      Мы не составляем полную матрицу tf-idf, считаем их внутри каждого документа, то есть обсчитывает 500 000 документов на словаре в примерно 140 000 вводов (на данной выборке).

      Внизу пример менее очевидной темы (не рецепты или автомобили):
      (термин 0.5097457251705502), (существ 0.3412614732147765), (греч, 0.03721095065119164), (см, 0.03721095065119164), (сущ, 0.03464162310622841), (синоним, 0.032603880570567914), (муж, 0.027996810489944186), (кол, 0.024009922920173656), (жен, 0.02365553291397183), (словар, 0.021351997873659965), (мн, 0.017453707805439887), (прил, 0.01647913528838487), (англ, 0.016124745282183044), (русск, 0.015150172765128025), (разг, 0.01408700274652255), (ср, 0.01311243022946753), (нареч, 0.011517675201559318), (слов, 0.01001151767520156), (употр, 0.009834322672100647), (франц, 0.009479932665898822), (совер, 0.008239567644192435), (толков, 0.008062372641091522), (общ, 0.007885177637990608), (книжн, 0.007885177637990608)…

      Как несложно заметить, это тема про изучение языков, грамматику и тому подобное.

      Собственно классификация всего трафика и распределение по темам, равно как и степень покрытия придуманного классификатора и улучшения от учета n-грам — это тема следующего поста — stay tuned!


  1. AStek
    27.05.2016 10:44

    На scala расчитывали?


    1. recompileme
      27.05.2016 12:01

      Да, и мы как раз ищем скаловика)


  1. Rogvold91
    27.05.2016 19:16

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


    1. diourinski
      27.05.2016 19:32

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


    1. elingur
      30.05.2016 10:13

      ИМХО сверточные сети не лучший выбор для NLP. Для распознавания изображений — да, а вот для текста их применение не оправдывает себя: статистические методы неплохо справляются со многими задачами обработки текста, при этом и в обучении, и в настройке проще. Я бы смотрел в сторону Марковских сетей, графических моделей.


      1. diourinski
        30.05.2016 13:16

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


  1. sim0nsays
    30.05.2016 06:50

    Спасибо за пост! Читается очень увлекательно, прям не оторваться, хоть я совсем мало понимаю в LDA и прочем.
    Немного вопросов, если позволите.
    — После того, как выбрали только топовые слова и резко сократили словарь и документы, LDA все равно не получается делать? Почему?
    — А как потом это все используется собственно в таргетинге? Вот есть эти «темы», порожденные словами, как они используются дальше?


    1. diourinski
      30.05.2016 13:20

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