Коллаборативная фильтрация

Ярослав Карасев 5 Октябрь, 2008

Введение
Коллаборативная фильтрация, Совместная фильтрация (collaborative filtration) — метод, дающий автоматические прогнозы (фильтрацию) относительно интересов пользователя по собранной информации о вкусах множества пользователей (сотрудничающих между собой). – Wikipedia

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

Мой тезис: Рекомендательные системы на базе коллаборативной фильтрации не приносят ожидаемых от них результатов. Коллаборативная фильтрация – это фильтр, призванный «обрезать», а не рекомендовать. Рекомендовать должны люди!

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

Проблема: Есть событие, а есть шум, который им создаётся.
Вопрос. Если событие имеет ценность, а шум – нет, то как найти первоисточник и отфильтровать информационный шум?

Проблема: Есть «Длинный Хвост», в котором совершенно невозможно ориентироваться (огромное количество контента, который лежит в сети, но внимание к нему сейчас по каким-то причинам равно нулю)
Вопрос. Как найти то, что тебе действительно интересно?

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

Я полагаю, что эти три вопроса – лишь вершина айсберга, но они весьма наглядно показывают, что всю информацию, которая гуляет в сети нужно как минимум фильтровать, а в идеале рекомендовать.

Есть и еще проблемы, присущие нашей эпохе постмодернизма. Проблемы эти очень хорошо сформулированы в книге «Экономика символического обмена», написанной Александром Долгиным, профессором ВШЭ и президентом фонда «Прагматика культуры». Среди проблем выделю две:
1. Деньги на рынке культуры не являются на текущий момент адекватным мерилом ценности произведения. (И как следствие, тот факт, что отсутствие ценовой дифференциации не позволяет экономически навигировать на культурном рынке, поскольку на других рынках цены сигнализируют о качестве товаров)
2. Ситуация «ухудшающего отбора» (ситуация, в которой некачественная продукция становится нормой, а качественная постепенно исчезает)

У двух этих проблем есть общий вопрос, который мы можем задать:
Как и откуда получать информацию о качестве культурного артефакта?

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

Вот тут и приходит нам на помощь коллаборативная фильтрация. Вот ее общее, ненаучное определение:

Коллаборативная фильтрация – это все те методы, которые позволяют нам получать информацию о качестве объектов от большого количества людей, и, таким образом, сегментировать их (объекты) по критерию качества.

Коллаборативная фильтрация существует в интернете давно. Практически любой пользовательский рейтинг или чарт можно считать коллаборативной фильтрацией – есть массы людей, которые судят о качестве объекта. Лучшие попадают в так называемые ТОП. Ну, чем не фильтр? Мы можем судит о качестве людей на базе их «кармы» (оценки другими людьми), мы можем судить, например, о качестве фильма по его нахождению в ТОПе, мы можем судить о качестве блога по количеству ссылок на него другими пользователями. Всё это очень простая и уже очень давно используемая в сети коллаборативная фильтрация. Разбираться же с более сложной коллаборативной фильтрацией мы будем в следующем разделе.

Методология и терминология
Мне хочется понять: пригодна ли фильтрация для построения рекомендательной системы?

Коллаборативная фильтрация (КФ) – это процесс фильтрации информации или паттернов, используя техники совмещения большого количества агентов, точек зрения и различных источников данных (мой вольный перевод термина с английской Википедии). Собственно, синонимом для этого словосочетания будет понятие «совместная фильтрация».

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

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

Daniel Lemire и Anna Maclachlan, исследователи этого метода пошли ещё дальше. На базе этой модели коллаборативной фильтрации они создали рекомендательную (прогнозирующую) систему, известную как «Slope One». Если есть статистика по оценкам или действиям пользователей, то можно найти недостающую оценку на базе других. Для этого используется корреляция между объектами на базе простой регрессии с одним свободным параметром (F(x)=x+b). Это даже проще, чем линейная регрессия (F(x)=аx+b).Для тех, для кого это все сложная математическая дребедень, рассмотрим этот метод на примере.

Шаг 1: Между двумя объектами разница в оценке юзера А составит 0,5=1,5-1
Шаг 2: Для юзера B справедлива эта же разница, то есть предсказание его оценки 2,5=2+0,5

Эта простота может усложняться и развиваться в разные стороны. Понятно, что чем больше оценок, тем более арифметически точное значение корреляции двух объектов мы получим. А если добавить коэффициент похожести пользователей, то его можно использовать в формуле в качестве веса той или иной получаемой оценки.

Активная коллаборативная фильтрация – это наиболее используемый сейчас метод фильтрации в сети. Как я уже говорил, если на каком-то сайте собрались пользователи с одним интересом, то по отношению к этому интересу их можно считать равными (каждому даётся 1 балл оценки на 1 объект), а значит, любой оцениваемый объект, чем больше оценок получит, тем больше интереса у этих людей он вызвал. Таким образом, попав на сайт, любой пользователь может легко отфильтровать по рейтингу интересные объекты от неинтересных. О недостатках коллаборативной фильтрации у меня будет целый раздел, но тут важно отметить недостаток этого типа фильтрации. Если количество объектов велико, то объекты с высокими оценками будут оцениваться еще больше, в отличие от тех, которые будут с низкими оценками (они потенциально могли бы вырасти, но люди просто не будут уделять им внимание, поскольку это «подвал ТОПа»).

Пассивная коллаборативная фильтрация – это потенциально очень прогрессивный метод, который связан с со сбором статистики по неявным (implicit) действиям пользователя в сети. К таким действиям можно относить:
1. Покупка через интернет
2. Повторения в использовании, сохранение, распечатывание на принтере
3. Ссылка на что-то
4. Отправка запросов

Пока еще трудно преодолеть технические ограничения этого метода,  но эти методы будут всё более и более популярными в бдущем (Semantic Web), когда браузеры или специальное программное обеспечение будет собирать и хранить персональную информацию о действиях пользователя в сети.

И вообще, коль скоро речь зашла о явных (explicit) и неявных (implicit)  действиях в сети, то стоит упомянуть, что и коллаборативная фильтрация в зависимости от этого делится на явную и неявную. Коллекция явных действий в сети подразумевает наличие оценочного механизма и явного проставления оценок пользователем. При неявной КФ у пользователей не спрашивают их мнение напрямую, но подразумевается, что их действия выражают их мнение (если скачал файл, то есть как минимум интерес).

Примеры и работающие модели
Прежде чем начать рассматривать реальные обзоры из практики КФ, хочется еще раз коротенько озвучить, почему этот метод является ценным:

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

Начну с сервиса социальных закладок, как с самого простенького примера. Допустим это www.memori.ru. Если я хочу найти интересные сайты по теме «коллаборативная фильтрация», то я открываю соответствующий тег и вижу: 30 закладок по этой теме (имплицитное действие пользователей: сохранение ссылки на сайт), отсортированные по количеству сохранений, оцененные, и самое главное – это было сделано не одним человеком, а СОВМЕСТНО, несколькими пользователями. То, что тег работает как фильтр для меня, надеюсь объяснять не надо.

Далее, пример посложнее. Рекомендательный сервис www.IMHOnet.ru . Первым шагом в модели определяется корреляция твоих вкусов со вкусами остальных пользователей. Формально, там могут быть различия в методике, но мы понимаем, что находятся оцененные объекты, сравнивается оценка по ним и выводится похожесть пользователя на меня. Выражается она в процентах. Второй шаг в модели – прогнозирование твоих оценок на другие фильмы, которые не отмечены тобой. На основе топа пользователей, с которыми ты совпадаешь больше остальных по вкусам, в их списках ищутся совпадения по другим фильмам и этот список выдается в качестве рекомендаций. Оценка для тебя прогнозируется исходя из их оценки (а в качестве веса берётся показатель похожести).

Что ж, метод имеет право на существование, но отвечает ли он на вопросы, на которые я хочу получить ответ (например, по кино):
1. Чем этот список рекомендаций лучше топа на IMDB?
2. В списке попадаются фильмы, которые я уже смотрел и прогнозируемая оценка по ним отличается от моих реальных ощущений. Как же так?
3. Из всех перечисленных фильмов какой фильм мне прямо сейчас стоит посмотреть?

Это не самый полный список вопросов, и пусть проблемы рекомендательного сервиса видны невооруженным глазом, но в качестве фильтра этот сайт весьма интересен. Он довольно эффективно отсекает огромный массив фильмов, которые мне смотреть не надо! Другими словами, если ошибка первого рода велика (рекомендует неинтересное), то ошибка второго рода (отсекает интересное) на порядок ниже, что важно для фильтра в принципе. А еще, на мой взгляд, тут ценна попытка межкультурного механизма фильтрации, когда по совпадению вкусов по книгам можно делать фильтрацию для фильмов и стихов.

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

И еще один пример коллаборативной фильтрации я хочу рассмотреть. Это аггрегатор персональных потоков информации www.friendfeed.com. Начнем с того, что на сайте есть большое количество пользователей и поток информации от них огромен. Для меня лично ещё важно, что на сайте «сидит» тусовка узкоспециализированная и мне по специализации интересная. Подписавшись на потоки моих друзей, я в качестве фильтра коллаборативной фильтрации использую их экспертизу. То есть, в мой поток попадают записи, которые вызывают мой интерес уже потому, что они вызывают интерес моих друзей, а мне важно «чем живут» мои друзья. Таким образом, два фильтра (оценочный в виде «like» и персональный в виде подписок а интересных людей) в массовом сервисе порождают коллаборативную фильтрацию, которая весьма адекватно направляет моё внимание на интересные информационные потоки. Причём, даже сузив свой круг до 5-6 подписок я смогу получать полноценный и качественный информационный поток, за счет того, что в зону внимания моих друзей попадает много больше усреднено менее качественного контента, но они, пропуская эти потоки через себя, улучшают для меня их качество, выполняя роль человеческого фильтра.

Недостатки и критика коллаборативной фильтрации
Проблем у КФ на самом деле гораздо больше, чем это может показаться на первый взгляд. Критиковать можно глобальные недостатки, но ведь есть еще и узкий прикладной сегмент для этого инструмента, в котором проблемы намного серьёзнее, хотя в данном случае их можно назвать локальными. Обо всех недостатках стоит задуматься и почти к каждому логически придумывается ответ, как можно от недостатка избавиться, но вот ведь проблема: обходные пути не решают реально существующих проблем, а лишь смягчают их. Начнём с проблем глобальных.

Проблема первого рейтинга (First-rater problem). Это ситуация в коллаборативной фильтрации, в которой невозможно сделать никаких прогнозов для объекта, который ещё не оценен никем. Объект может быть вполне качественным, но если с ним никто не познакомился, то его нельзя будет ни рекомендовать, ни прогнозировать отношение к нему, ни делать сегментацию на основе его качества.

Проблема избирательного внимания. Ситуация очень часто встречаемая. Коллаборативно созданный рейтинг объектов на основе личных оценок, так или иначе, приходит к тому, что в зону внимания конкретного человека попадает, например, 10 объектов из 100. И оценивает он соответственно только их. Таким образом, оценки первых десяти объектов растут, так как они всё время под вниманием и их оценивают всё новые люди, а например оценка уже 12 объекта в рейтинге будет расти не так, поскольку лишь 50% пользователей уделяет ему внимание. И хотя разница в качестве 10 и 12 объекта топа невелика, а может даже 12 объект качественно лучше, в оценках эта разница будет увеличиваться с течением времени. (Кажется в истории есть что-то подобное, когда богатые всё больше богатеют, так как могут преумножать свой капитал, а средний класс богатеть не может и всё это только исходя из первоначальных условий распределения богатства и никакие способности тут не помогут)

Проблема холодного старта (Cold-start problem). Холодный старт – это такая ситуация в фильтрации, когда система не может осуществить для тебя фильтрацию, поскольку ещё недостаточно ознакомилась с твоими интересами. Рекомендательные сервисы, построенные на коллаборативной фильтрации частенько этим грешат: рекомендацию ты получишь не раньше, чем проставишь оценки 5 (10,100, 1000) объектов. Пока система не помёт, на кого ты «похож», для неё твои оценки не имеют смысла. И чем сложнее спроектирована система, тем больше условный порог холодного старта.

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

Проблема больших чисел. Усреднение результатов и в коллаборативной фильтрации имеет место. Тут я позволю себе процитировать часть разговора на эту тему с моим другом на эту тему: «Топ imdb очень даже хороший, но с ним одна проблема – так как он хороший для всех – он не точный, что при возрастающем количестве информации – чистой воды зло». Что всё это значит?  Это значит, что при большом количестве оценок два человека будут на 86% похожи по вкусам на тебя, но между собой они при этом могут быть ни капли не похожи. А соответственно, рекомендаций от этих двух человек были бы разными, если бы каждый рекомендовал по отдельности, а в среднем получается общий и весьма усреднённый результат.

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

Проблема большой оценочной шкалы. Чем больше для человека оценочная шкала, тем лучше работает модель фильтрации, но с появлением большой шкалы человек не всегда может оценить своё отношение к объекту (это весьма часто является проблемой для фильмов, спектаклей, книг и других артефактов культуры).

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

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

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

Мой тезис: Коллаборативная фильтрация – это, прежде всего, фильтр! Если мы хотим рекомендовать на базе фильтрации, то систему рекомендаций придётся научить разбираться с недостатками коллаборативной фильтрации. Иначе грош цена таким рекомендациям, в которых не решена проблема избирательности внимания, когнитивного диссонанса, непохожести на себя и зависимости оценок от условий знакомства с объектами (и прочие, прочие, прочие).

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

Для того, чтобы сделать хорошую рекомендательную систему на сайте, хорошо бы познакомиться с другими методами выдачи рекомендаций, помимо коллаборативной фильтрации. Даже при первом рассмотрении можно выделить несколько других, нежели КФ, подходов к решению этой задачки:
1. Рейтинги и чарты на базе объективных критериев (например, на базе бокс-оффиса фильма)
2. Неявная коллаборативная фильтрация (в отличие от явной она намного сложнее технологически, и нет пока готовых моделей, либо они держатся в секрете)
3. Сегментационная фильтрация (когда объекты сегментируются по объективным показателям, и происходит фильтрация по различным сегментам)
4. Генерация рекомендательных списков людьми (спросил у людей, они тебе ответили)
5. Концепция коллективного разума (модель получения знаний и решений, которая основывается на совместной деятельности соревнующихся индивидов)

И если спросить моего мнения, то я отвечу, как это было сказано в теории игр: оптимальное решение находится в смешанных, а не в чистых стратегиях. Рекомендательная система делается при смешении нескольких подходов, которые максимально позволяют элиминировать недостатки этих подходов и достигать синергии от их использования.
Использованные в работе источники:

1. Критика «Экономики символического обмена» А. Долгина
2. Коллаборативная фильтрация на Википедии (англ.)
3. Комьюнити в ЖЖ ru_preference
4. Сайт НФИ «Прагматика культуры»
5. Статья на Вебпланете про коллаборативную фильтрацию
6. Сайты на Мемори.ру

Исследования, Тренды и теория  |  8 комментариев

© 2008. ООО «Инвенчур». Все права защищены.