Меня зовут Василий, уже более трех месяцев, как я работаю математиком в компании Surfingbird.
Первая серьезная задача, с которой я столкнулся, работая в компании — это решение проблемы холодного старта. В этой статье я опишу суть проблемы и основные направления ее решения.
Постановка задачи рекомендательной системы уже описана Сергеем Николенко в статье Рекомендательные системы: постановка задачи.
В основе большинства рекомендательных систем лежат так называемые методы коллаборативной фильтрации. Наша рекомендательная система не исключение. Все алгоритмы коллаборативной фильтрации опираются только на информацию о рейтингах, проставляемых пользователями, и не анализируют контент ресурсов (в нашем случае веб-страниц). Поэтому, эти алгоритмы работают при достаточно большом количестве рейтингов, как правило это 10-20 рейтингов. Задача выдачи релевантных рекомендаций для новых пользователей и для новых сайтов называется проблемой холодного старта.
Итак, проблема холодного старта делится на холодный старт для пользователей (что показывать новым пользователям?) и холодный старт для сайтов (кому рекомендовать вновь добавленные сайты?). Начнем по порядку.
Холодный старт для пользователей возможен на основе демографических данных, которые сами пользователи указывают при регистрации.В рассматриваемой задаче рекомендаций веб-страниц о пользователе известны пол, дата рождения и местоположение. Эти характеристики мы и возьмем за базовые. Однако, демографических данных может быть получено и больше. С помощью API социальных сетей мы можем узнать уровень образования, социальный статус и прочие характеристики.
Существуют два основных подхода к применению в рекомендациях демографической информации о пользователе:
— Экспертным образом составляются стереотипы для различных демографических категорий. То есть эксперт сам определяет что на холодном старте показывать каждой из категорий. Очевидным минусом такого подхода является необходимость работы эксперта, при этом пользователю будут рекомендоваться только популярные сайты субъективно подобранные экспертом. Объем экспертной работы существенно возрастает с ростом числа категорий.
— Демографические категории определяются автоматически путем выявления кластеров пользователей со схожими интересами. Рекомендации строятся на основе того, какие рейтинги проставляли пользователи из той же категории, то есть того же возраста, пола, местоположения и т. д.
Второй подход не требует привлечения экспертов и предоставляет возможность создания неограниченного числа кластеров, поэтому остановлюсь на нем более подробно.
Для построения демографических категорий естественно использовать методы кластеризации. Объекты кластеризации x — это пользователи. Признаки (или характеристики) объектов — это отнормированные демографические данные пользователя: пол, возраст, местоположение, образование и другие.
Для кластеризации по демографическим данным естественно использовать метод k-средних, так как в этом случае каждый кластер определяется точкой своего центра и, в следствии этого, хорошо интерпретируется. Расстояние от объекта (пользователя) до центра кластера можно определять, вообще говоря, бесконечным числом способов. Принято использовать евклидову метрику в пространстве признаков.
Однако, в нашей задаче необходимо учесть данные о рейтингах, а не только демографические данные.
Ситуацию спасает наличие рассчитанных для всех сайтов топиков алгоритма SVD, которые можно также добавить как признаки объектов при кластеризации. В этом случае, расстояние между сайтами будет рассчитываться исходя как из сходства демографических данных, так и рейтингов пользователей.
После того, как кластеры пользователей получены и для каждого нового пользователя, указавшего свои демографические данные, мы знаем кластер, к которому он относится, мы можем улучшить рекомендации на холодном старте с помощью групповых рекомендаций или фильтр-ботов. Об этом чуть подробнее.
Наиболее естественным является метод групповых рекомендаций (group recommendation to individual user), название которго говорит само за себя: мы подбираем новому пользователю такие рекомендации, которые нравятся большинству пользователей в его демографической категории.
Существует ряд различных стратегий, как агрегировать рейтинги разных пользователей в групповую рекомендацию. Например, групповой рейтинг можно рассчитывать так:
GR= П r_i^w_i,
где r_i – рейтинг i-го пользователя, w_i – вес i-го пользователя. Произведение берется по всем пользователям или по выделенной группе по какому-то критерию (например, возраст-пол).
Весам w_i для пользователей с тем же возрастом, полом и местоположением мы даем большее значение, остальным меньшее (подбираются вручную).
Альтернативным подходом являются фильтр-боты (filterbots), которые генерируют дефолтные рейтинги для нового пользователя. То есть при регистрации фильтр-боты автоматически сгенерируют несколько рейтингов для пользователя на основе его демографических данных, которые будут использованы алгоритмами коллаборативной фильтрации на холодном старте. Плюсом такого подхода является простота реализации и отсутствие необходимости менять существующие алгоритмы.
Кроме того, фильтр-боты и групповые рекомендации можно использовать совместно: тогда за дефолтные рейтинги фильтр-ботов берутся групповые рейтинги.
Для решения проблемы холодного старта для новых веб-страниц применяются различные методы анализа текста и другого контента страницы (картинки, видео, flash, ссылки и т.д.).
Основные методы семантического анализа текста, на которых я хотел бы остановиться – это LDA и relevance feedback.
Общая схема рекомендаций на основе текстового контента страницы приблизительно такова. Сначала по всем сайтам собирается полезный контент (отбрасывается реклама, меню и т.д.). Слова в тексте проходят предварительную обработку, то есть отбрасываются стоп-слова и производится лемматизация. Далее составляется единый словарь слов и таблица встречаемости слов в текстах веб-страниц (контент-профили страниц). Слова взвешиваются по TF-IDF и для слишком длинных текстов оставляется только top N самых весомых слов.
Алгоритм relevance feedback составляет профиль тегов (то есть ключевых слов) для каждого пользователя по контент-профилям страниц, которые лайкал этот пользователь.
Новые сайты рекомендуются тем пользователям, прифили тегов которых наиболее коррелируют с контент-профилем вновь добавленной страницы.
Алгоритм LDA действует по-другому. Слова из словаря слов в результате обучения вероятностной модели группируются по фиксированному количеству топиков (например, 100). Для каждой веб-страницы строится вероятностное распределение по топикам (то есть вектор из 100 фич, каждая из которых характеризует, в какой степени данная страница соответствует топику). Для предсказания вероятности лайка для каждого пользователя обучается логистическая регрессия на LDA-фичах страниц, которые смотрел пользователь, в результате чего у каждого пользователя тоже появляется вектор весов по всем LDA-топикам. При добавлении нового сайта для него сначала рассчитываются LDA-фичи, а затем он рекомендуется пользователям с максимальной предсказанной вероятностью лайка, которая легко вычисляется по известным фичам пользователя и веб-страницы.
Каждый из упомянутых в этой цепочке алгоритмов заслуживает отдельной статьи с практическими примерами, но это в будущем…
Первая серьезная задача, с которой я столкнулся, работая в компании — это решение проблемы холодного старта. В этой статье я опишу суть проблемы и основные направления ее решения.
Постановка задачи рекомендательной системы уже описана Сергеем Николенко в статье Рекомендательные системы: постановка задачи.
В основе большинства рекомендательных систем лежат так называемые методы коллаборативной фильтрации. Наша рекомендательная система не исключение. Все алгоритмы коллаборативной фильтрации опираются только на информацию о рейтингах, проставляемых пользователями, и не анализируют контент ресурсов (в нашем случае веб-страниц). Поэтому, эти алгоритмы работают при достаточно большом количестве рейтингов, как правило это 10-20 рейтингов. Задача выдачи релевантных рекомендаций для новых пользователей и для новых сайтов называется проблемой холодного старта.
Итак, проблема холодного старта делится на холодный старт для пользователей (что показывать новым пользователям?) и холодный старт для сайтов (кому рекомендовать вновь добавленные сайты?). Начнем по порядку.
Холодный старт для пользователей
Холодный старт для пользователей возможен на основе демографических данных, которые сами пользователи указывают при регистрации.В рассматриваемой задаче рекомендаций веб-страниц о пользователе известны пол, дата рождения и местоположение. Эти характеристики мы и возьмем за базовые. Однако, демографических данных может быть получено и больше. С помощью API социальных сетей мы можем узнать уровень образования, социальный статус и прочие характеристики.
Существуют два основных подхода к применению в рекомендациях демографической информации о пользователе:
— Экспертным образом составляются стереотипы для различных демографических категорий. То есть эксперт сам определяет что на холодном старте показывать каждой из категорий. Очевидным минусом такого подхода является необходимость работы эксперта, при этом пользователю будут рекомендоваться только популярные сайты субъективно подобранные экспертом. Объем экспертной работы существенно возрастает с ростом числа категорий.
— Демографические категории определяются автоматически путем выявления кластеров пользователей со схожими интересами. Рекомендации строятся на основе того, какие рейтинги проставляли пользователи из той же категории, то есть того же возраста, пола, местоположения и т. д.
Второй подход не требует привлечения экспертов и предоставляет возможность создания неограниченного числа кластеров, поэтому остановлюсь на нем более подробно.
Для построения демографических категорий естественно использовать методы кластеризации. Объекты кластеризации x — это пользователи. Признаки (или характеристики) объектов — это отнормированные демографические данные пользователя: пол, возраст, местоположение, образование и другие.
Для кластеризации по демографическим данным естественно использовать метод k-средних, так как в этом случае каждый кластер определяется точкой своего центра и, в следствии этого, хорошо интерпретируется. Расстояние от объекта (пользователя) до центра кластера можно определять, вообще говоря, бесконечным числом способов. Принято использовать евклидову метрику в пространстве признаков.
Однако, в нашей задаче необходимо учесть данные о рейтингах, а не только демографические данные.
Ситуацию спасает наличие рассчитанных для всех сайтов топиков алгоритма SVD, которые можно также добавить как признаки объектов при кластеризации. В этом случае, расстояние между сайтами будет рассчитываться исходя как из сходства демографических данных, так и рейтингов пользователей.
После того, как кластеры пользователей получены и для каждого нового пользователя, указавшего свои демографические данные, мы знаем кластер, к которому он относится, мы можем улучшить рекомендации на холодном старте с помощью групповых рекомендаций или фильтр-ботов. Об этом чуть подробнее.
Наиболее естественным является метод групповых рекомендаций (group recommendation to individual user), название которго говорит само за себя: мы подбираем новому пользователю такие рекомендации, которые нравятся большинству пользователей в его демографической категории.
Существует ряд различных стратегий, как агрегировать рейтинги разных пользователей в групповую рекомендацию. Например, групповой рейтинг можно рассчитывать так:
GR= П r_i^w_i,
где r_i – рейтинг i-го пользователя, w_i – вес i-го пользователя. Произведение берется по всем пользователям или по выделенной группе по какому-то критерию (например, возраст-пол).
Весам w_i для пользователей с тем же возрастом, полом и местоположением мы даем большее значение, остальным меньшее (подбираются вручную).
Альтернативным подходом являются фильтр-боты (filterbots), которые генерируют дефолтные рейтинги для нового пользователя. То есть при регистрации фильтр-боты автоматически сгенерируют несколько рейтингов для пользователя на основе его демографических данных, которые будут использованы алгоритмами коллаборативной фильтрации на холодном старте. Плюсом такого подхода является простота реализации и отсутствие необходимости менять существующие алгоритмы.
Кроме того, фильтр-боты и групповые рекомендации можно использовать совместно: тогда за дефолтные рейтинги фильтр-ботов берутся групповые рейтинги.
Холодный старт для веб-страниц
Для решения проблемы холодного старта для новых веб-страниц применяются различные методы анализа текста и другого контента страницы (картинки, видео, flash, ссылки и т.д.).
Основные методы семантического анализа текста, на которых я хотел бы остановиться – это LDA и relevance feedback.
Общая схема рекомендаций на основе текстового контента страницы приблизительно такова. Сначала по всем сайтам собирается полезный контент (отбрасывается реклама, меню и т.д.). Слова в тексте проходят предварительную обработку, то есть отбрасываются стоп-слова и производится лемматизация. Далее составляется единый словарь слов и таблица встречаемости слов в текстах веб-страниц (контент-профили страниц). Слова взвешиваются по TF-IDF и для слишком длинных текстов оставляется только top N самых весомых слов.
Алгоритм relevance feedback составляет профиль тегов (то есть ключевых слов) для каждого пользователя по контент-профилям страниц, которые лайкал этот пользователь.
Новые сайты рекомендуются тем пользователям, прифили тегов которых наиболее коррелируют с контент-профилем вновь добавленной страницы.
Алгоритм LDA действует по-другому. Слова из словаря слов в результате обучения вероятностной модели группируются по фиксированному количеству топиков (например, 100). Для каждой веб-страницы строится вероятностное распределение по топикам (то есть вектор из 100 фич, каждая из которых характеризует, в какой степени данная страница соответствует топику). Для предсказания вероятности лайка для каждого пользователя обучается логистическая регрессия на LDA-фичах страниц, которые смотрел пользователь, в результате чего у каждого пользователя тоже появляется вектор весов по всем LDA-топикам. При добавлении нового сайта для него сначала рассчитываются LDA-фичи, а затем он рекомендуется пользователям с максимальной предсказанной вероятностью лайка, которая легко вычисляется по известным фичам пользователя и веб-страницы.
Каждый из упомянутых в этой цепочке алгоритмов заслуживает отдельной статьи с практическими примерами, но это в будущем…
