Я уже пару раз писал про счётчики и про то, как убирать из них смещение. Но так и не затронул некоторые важные технические моменты. А именно — что счётчики занимают место в профилях пользователей и объектов. (Профиль объекта — это вся накопленная информация про объект; он не обязательно должен быть физически одной структурой.) И это значит, что мы не можем хранить бесконечное число счётчиков. Например, если профиль пользователя занимает 1 Мб, то с этим уже довольно сложно работать в realtime-системе.

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

Но бывают случаи, когда такой стратегии недостаточно. Например, когда пользователи листают ленту рекомендаций и мы хотим запомнить все показы, чтобы не рекомендовать их ещё раз. У наиболее активных пользователей могут набраться десятки тысяч показов. Счётчики тут — не самое эффективное средство.

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

Кстати, в нашей платформе в Яндексе мы сделали более эффективную по месту реализацию фильтра — quotient filter.

По сравнению со счётчиками, фильтры занимают меньше места, но у них есть два недостатка:
1) они выдают только бинарное значение,
2) элементы в фильтре нельзя перечислить, а можно только спросить про каждый конкретный элемент, есть ли он в фильтре. В частности, по фильтрам нельзя делать генерацию кандидатов или составлять более сложные фичи.

А можно ли избавиться от первого недостатка? Можно ли сделать структуру, которая будет хранить небинарные значения, как у счётчиков, но делать это приближенно (нам же это для фичей в основном нужно) и за счёт этого — более компактно?

Можно! Это называется count-min sketch, и это простое обобщение фильтра Блума (counting Bloom filter) с той же самой идеей использовать несколько хеш-функций. И, кстати, с экспоненциальным затуханием прекрасно совмещается.

К сожалению, у меня нет практического опыта с этим, чтобы сказать — эффективнее ли для фичей использовать count-min sketch или обычное обрезание счётчиков.

Невероятно.

Разработчик Алексей рассказал в комментах, что Стихолюб до сих пор жив!

Попав в Яндекс, мы получили проект от Ильи Сегаловича. Илья умел очень классно делиться идеями и объяснять суть. Он нам рассказал, что на самом деле Гугл в своё время выиграл у всех предыдущих поисковиков за счёт хорошо сделанных сниппетов. А теперь для нас самое главное — сделать так, чтобы поисковые результаты не были сплошь одинаковыми. Надо бороться с полу-дублями.

Только сделать это у нас не удалось. Зато мне удалось получить свою первую психологическую травму на работе.

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

Когда нужно было разобраться в каком-то куске поискового кода, Макс сказал:
— Ну давай посмотрим, кто автор этого кода... Ага, некий Антон с ником pg@. Просто сходи и спроси у него, что здесь происходит.

Я сходил и спросил. Антон с ником pg@ ответил мне, чтобы я просто прочитал код.

Прочитать и понять код у меня не получилось. А так как работали мы на четверть ставки, то в следующий раз мы с Максом встретились примерно через неделю. Узнав, что прогресса особо нет, Макс сказал:
— Нет, ну так дело не пойдёт. Пойдём вместе сходим и спросим.

Сходили и спросили. На что Антон с ником pg@ просто накричал на нас обоих: какого чёрта какие-то стажёры его отвлекают и не могут даже за неделю самостоятельно прочитать код?!

С тех пор ни я, ни Макс уже больше никогда не хотели работать в Яндекс.Поиске.

#lifestories

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

Но, на удивление, ни там, ни там не было настоящего работающего механизма feature selection.

Уточню, что я называю «настоящим». Все градиентные бустинги предоставляют feature importance — насколько они каждый признак использовали и насколько это помогло оптимизации лосса. Также бывают SHAP values. Но все грамотные ML-инженеры знают, что всё это совсем не настоящая полезность фичей. Их нужно использовать так: если importance нулевая (или очень маленькая), то фича бесполезная, ее можно убрать. Но не в обратную сторону.

В Яндексе был (есть) настоящий feature evaluation — убрать фичи и посмотреть, как меняется качество, да еще и стат-тест запустить. И даже была (есть) более дешевая приближенная модификация.

Но вот именно полноценного feature selection не было. Точнее, при мне даже была попытка его сделать, но вроде как большого успеха (распространения) она не достигла. Может быть, спрос на этот инструмент был недостаточным, а может, сделать его эффективным очень сложно. Задача же нетривиальная — есть N (тысячи) фичей, нужно среди 2^N наборов выбрать оптимальный (с точки зрения качества и какого-то понятия стоимости — например, количества фичей). А протестировать каждый набор может занимать часы.

Год назад я над этим размышлял-размышлял... И подумал, что можно это попробовать сделать сильно более эффективно с помощью Random Forest. Предлагаю вам оценить. (Я уже с бустингами перестал работать и вряд ли буду тестировать.) Сразу оговорюсь, что я никогда ничего про feature selection для random forest не читал и не слышал. Вполне вероятно, что уже давным-давно придумали либо то же самое (тогда почему не используют? не работает?), либо что-то ещё получше. Расскажите в комментах, если знаете.

Итак, идея:
- Предположим, что для отбора фичей можно временно заменить бустинг на random forest. (Это слишком сильное предположение?)
- Обучим random forest на всех фичах с раз в сто большим количеством деревьев. (Его же обучать дешевле, чем бустинг, он очень легко параллелится.)
- Затем запускаем любой стандартный алгоритм отбора фичей. И когда тестируем очередной набор, то не обучаем модель заново, а просто выбираем те деревья, которые не используют выкинутых фичей.
- Обычно нас интересуют наборы, в которых большая часть фичей не выкинуты, поэтому таких деревьев должно быть не слишком мало. И можно оценить, какое качество будет у модели с ровно M такими деревьями.
- ...
- Profit.

Что думаете?

Хотя и не все соглашаются с таким подходом, но я считаю, что в рекомендациях надо исходить из того, что главная цель любой рекомендательной системы — оптимизация суммарного value. Это value может измеряться разными метриками. Главные четыре типа, которые я видел: DAU, time spent, транзакции (GMV) и подпиcки. Кроме того, иногда это value не только обычных потребляющих пользователей, но и других сторон — провайдеров контента.

Как я писал в предыдущем посте, основная часть рекомендательной системы — это engagement-модель E(engagement | item, user, context), которая предсказывает это самое value (или какое-то его осмысленное упрощение) для одного порекомендованного объекта. И можно строить рекомендации, просто сортируя по предсказаниям этой модели, не обращая внимания ни на что другое. Назовём этот бейзлайн циничным ранжированием.

Циничное ранжирование не является оптимальным для заявленной цели оптимизации суммарного value. Вы часто можете услышать про разные "beyond accuracy" аспекты рекомендаций вроде exploration, diversity, novelty, serendipity. Давайте переведём эти понятия с языка ощущений и "продуктового видения" на язык оптимизации суммарного value.

В этом посте начнём с exploration. Все слышали о дилемме exploration vs. exploitation. Это о том, что зачастую выгодно пожертвовать value (наградой) в текущем моменте ради того, чтобы узнать что-то новое и в будущем действовать более оптимально.

Довольно важно разделять user exploration и system exploration, потому что работать с ними надо по-разному. В первом случае мы жертвуем value пользователя в моменте ради него же самого, чтобы узнать о нём больше. Проверить, насколько хорошо нам это удаётся, можно с помощью обычных A/B-тестов. Только иногда нужно увеличивать их длительность, чтобы уловить более долгосрочные эффекты.

В system exploration же мы хотим узнать больше о всей системе. Одним важным частным случаем является item exploration — узнать больше про недоисследованные объекты (особенно недавно появившиеся в системе). Также можно исследовать разные области в пространстве признаков любой из использующихся моделей (model exploration). Про это уже был пост от Саши.

В отличие от user exploration, в system exploration всё сильно сложнее с замерами. Мы приносим пользователя в жертву ради остальных, а остальные могут оказаться в другой выборке A/B-теста.

При этом какие-то простые и полезные метрики item exploration всё же можно использовать: доля объектов, которые получают не меньше X показов/кликов за первые Y часов, — как метрика на дашборде, и доли кликов и показов на такие "недоисследованные" (новые с малым числом показов) объекты — как метрики в A/B. Эти метрики позволяют сравнить уровень exploration, но не отвечают на вопрос, какой уровень был бы оптимальным.

У YouTube есть попытки более принципиального подхода, но нельзя назвать эту область решённой.

Telegram

Wazowski Recommends

Персонализация и popularity bias Распространённая проблема в рекомендательных системах — недостаток персонализации, когда показываются в основном популярные и не очень релевантные пользователю документы. В сообществе есть известная проблема popularity bias.…

Персонализация и popularity bias

Распространённая проблема в рекомендательных системах — недостаток персонализации, когда показываются в основном популярные и не очень релевантные пользователю документы.

В сообществе есть известная проблема popularity bias. Но что это в точности такое? Bias — это системное смещение. А где здесь смещение? И есть ли оно вообще?

Если общими словами, то под popularity bias понимается ситуация "the rich get richer", когда популярные документы рекомендуются системой непропорционально чаще непопулярных. Причины у этого могут быть разные, и в литературе освещаются разные аспекты этого явления. Важно разделять эти причины, потому что это сильно помогает дебажить систему.

В работе над рекомендациями очень полезно выделять два важных шага:
1) Обучение модели предсказания отклика пользователя на рекомендованный объект. В простом случае это просто вероятность клика, в более общем — E(engagement | item, user, context).
2) Собственно, построение рекомендаций с помощью этой модели. Простое ранжирование по предсказаниям — не самый оптимальный, хотя и хороший бейзлайн.

Во многих случаях, говоря о popularity bias, подразумевают неоптимальность шага 2. То есть, даже если более популярный объект вызовет у пользователя с большей вероятностью позитивный отклик, может быть лучше порекомендовать ему менее популярный объект. Причин тут тоже может быть несколько — как пользователецентричные (долгосрочно клик на популярный объект менее ценен для этого пользователя, чем клик на непопулярный), так и с точки зрения всей экосистемы (этому пользователю станет чуть хуже, но зато мы выровняем распределение потребления по всей базе объектов). Это, в целом, разумные мысли, но надо честно себе признаться: мы жертвуем engagement-ом в момент конкретного запроса ради светлого будущего.

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

В других же случаях popularity bias относят к первому пункту: дисбаланс объектов мешает нам хорошо обучить модель E(engagement | item, user, context). В частности, она может плохо учитывать пользовательские фичи и, по сути, просто выучить E(engagement | item), тесно связанную с популярностью (кстати, в этом посте я тоже иногда под популярностью имею в виду не P(item), а E(engagement | item)). Вот это уже очень ощутимая проблема. Хотя я не очень понимаю, почему её называют баисом.

Тут советы зависят от конкретной модели. Вот несколько:
- Убедитесь, что у модели есть информативные персональные фичи.
- Введите отдельный член внутри модели, отвечающий за популярность, чтобы оставшаяся часть модели могла сфокусироваться на специфичности.
- Если модель выучивает эмбеддинги объектов, проверьте, хорошо ли они выучились. Например, посмотрев на самые похожие объекты на данный.
- Если используется negative sampling, то учитывайте в нём популярность. Только не забудьте при применении обратно умножить на неё, чтобы получить E(engagement | ...), как обсуждали в том же посте.
- Ну и просто проверьте, что модель нормально выучилась. Да, это не так-то просто. Это часть довольно сложной, но критически важной темы ML Debugging.

Кстати про "непропорционально чаще". Никто ведь не обещал, что при простом ранжировании вероятность быть порекомендованным будет пропорциональна популярности или CTR документа. Это совсем не так. Может быть, поэтому это и называют bias-ом?

На моей же практике было очень много случаев, когда команды
а) не задумываются, что именно они называют popularity bias-ом и в чём его причины,
б) имеют проблемы с недостатком персонализации просто из-за плохо обученной модели E(engagement | ...).

Очень важно понимать — это мир так устроен, что у популярных, но менее релевантных объектов действительно в среднем лучше отклики, или просто мы модель плохо обучили.

Намного чаще popularity bias — это просто популярный миф, скрывающий баги системы.

Не стоит недооценивать важность хорошей engagement-модели.