о нас
персоналии
сми о нас


проекты
издательство
кафедра


книга
термины
Имхонет


исследования
аналитика
ссылки

Статья из The Economist о коллаборативной фильтрации

United we find, The Economist, Mar 10th 2005

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

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

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

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

Идея о коллаборативной фильтрации возникла около 15 лет назад. Первые её прототипы появились в начале 90-х в исследовательском центре Xerox PARC, в Пало Альто, Калифорния. Но задержка между возникновением идеи и её широким внедрением оказалась достаточно долгой, по двум причинам. Во-первых, успешно работающая система коллаборативной фильтрации требует проведения множества вычислений, а по мере роста числа пользователей эта потребность ещё больше увеличивается. Система-прототип могла иметь несколько тысяч пользователей, и это вполне контролируемо, но система мирового масштаба будет иметь миллионы пользователей – и разница в масштабе порождает новые проблемы, которые были решены только недавно.

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

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

Скажи мне, что я хочу

Коллаборативная фильтрация начинается со сбора информации о индивидуальных предпочтениях. Это может быть явно выраженный процесс, когда пользователь оценивает книгу, компакт-диск или ресторан, присваивая им баллы, обычно с 1 до 5. Также это может быть неявно выраженный процесс оценивания – например, покупка – это точный указатель того, что человек заинтересован в данной вещи. Но неявно выраженные параметры также могут быть более «тонкими»; например, продолжительность времени просмотра конкретной веб-страницы, или даже последовательность кликов по ссылкам, т.е. в какой последовательности пользователь переходил по ссылкам, бродя по Сети. Эти различные методы могут быть либо агрегированы и выражены единым баллом, либо они могут храниться отдельно для более детального анализа. И иногда потребителей будут просить оценить один и тот же объект с разных сторон – например, что один думает о еде в ресторане, и что думает другой о качестве обслуживания в нём.

Результатом этого является гора информации, размер которой – главная проблема, когда необходимо обнаружить в ней особенности и систему. Но такому положению вещей некоторую помощь оказывает «разреженность» информации. Подавляющему большинству объектов явно или не явно выраженные баллы никем не присвоены. Даже самые занятые пользователи редко ранжируют более 1% объектов. Например, Amazon через свой Интернет-магазин продаёт более 2 млн. книг. Разреженность информации – это спасительная отсрочка, так как она даёт возможность внедрить различные математические методы для ускорения процесса генерирования рекомендаций.

Существует 2 различных способа генерирования рекомендаций. Первая идея была предложена в 1992 г. Дейвом Голдбергом (Dave Goldberg) и его коллегами из Xerox PARC, которые и ввели термин «коллаборативная фильтрация». Их подход заключался в том, чтобы рекомендовать человеку объекты на основании его сходства с другими пользователями. Если мне понравилась книга и тебе понравилась та же книга, тогда вероятно мне нравятся те же вещи, что и тебе. Однако, коллаборативная фильтрация, устроенная по принципу «потребитель-потребитель», начинает демонстрировать очень скромные успехи, когда численность её пользователей доходит до нескольких миллионов. Проблема заключается в том, что взаимосвязи между пользователями системы должны постоянно пересчитываться, что требует больших затрат на компьютерную обработку.

Вот почему Бадрул Сарвар (Badrul Sarwar) и его коллеги из Университета Миннеаполиса разработали в 2001 г. систему коллаборативной фильтрации, устроенной по принципу «объект-объект». (Другие группы, включая Amazon, приблизительно в то же время имели похожие идеи). Пообъектная фильтрация работает за счёт фиксирования состояния всех оценок, выставленных объекту пользователями системы. Затем система анализирует сходство между объектами. Например, такого как книга, она устанавливает все другие объекты, получившие от многих людей сходную с оригинальным объектом оценку (см. рисунок).


(user-user filtering—фильтрация « пользовыатель пользователь » item-item filtering—фильтрация « объект-объект »)

Фильтрация «пользователь-пользователь»

Рекомендации выдаются посредством обнаружения пользователей системы с похожими вкусами. Tom и Dick похоже имеют одинаковые вкусы, так как им обоим нравится объект B и обоим не нравится объект C. В целом, предполагается, что Dick согласится с Tom-ом. Так, Dick-у будет рекомендован объект A. Проблема этого подхода заключается в том, что взаимосвязи должны постоянно пересчитываться, и это становится практически невозможно, если системой будут пользоваться миллионы людей.

Фильтрация «объект-объект»

Рекомендации выдаются посредством обнаружения объектов, одинаково привлекательных для многих пользователей. Рассмотрим объект D. Двум пользователям, которым понравился объект D, Harry и Jane, также понравился объект A. Можно предположить, что, в общем, людям, которым нравится объект D, также понравится объект А. Таким образом, Dick-у будет рекомендован объект А. Этот метод может быть распространён на миллионы объектов и миллионы пользователей.


Детали того, что понимается под «сходством», варьируются от системы к системе. В действительности, единственным аспектом получения хорошо работающей системы рекомендаций является наличие соответствующего математического определения сходства. Простейший подход, при котором измеряется средняя разница в оценках, работает достаточно хорошо. Существуют различные приёмы, которые могут использоваться для улучшения качества работы системы, например, такие как введение систематической погрешности против очень популярных объектов: нет особой ценности в рекомендовании людям явных бестселлеров, таких как «Код Да Винчи», так как вполне вероятно, что они о нём слышали.

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

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

Это только один из затронутых аспектов проблемы прайвеси, вызывающей большую озабоченность, когда речь заходит о коллаборативной фильтрации: дело в том что, чтобы вырабатывать рекомендации, необходимо собрать в центральном хранилище информацию о большом числе людей. Но есть и другие аспекты. В действительности, схема, предложенная Джоном Кэнни (John Canny) из Университета Калифорнии в Беркли, показывает, что вполне возможно объединить мнения группы людей и вырабатывать для них рекомендации, при этом не раскрывая их собственных персональных предпочтений перед другими.

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

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

Заклинивание фильтров

Второй момент, вызывающий озабоченность в контексте коллаборативной фильтрации, заключается в том, что по мере того, как растёт важность таких систем, люди всё чаще могут пытаться манипулировать ими: например, издатели могли бы начать рекомендовать свои собственные книги. В ноябре 2004 г. Майкл О’Махони (Michael OMahony) из Университета Дублина опубликовал работу, демонстрирующую, что даже сегодняшние самые усовершенствованные системы коллаборативной фильтрации не достаточно устойчивы к проискам злоумышленников, ищущих возможность нарушить нормальную работу их системы ранжирования. Ни одна из существующих систем не разрабатывается в расчёте на предотвращение их использования злоумышленниками. Можно ли предотвратить такой «рекомендационный спам»?

Нолан Миллер (Nolan Miller) и его коллеги из Kennedy School of Government при Гарвардском Университете уверены, что можно, обрисовав, как это сделать. Их схема использует пробалистические методы установления того, является ли присвоенный балл «честным», через обнаружение необычно выглядящего характера выставления оценок. Например, за один и тот же день были созданы десятки потребительских профилей (аккаунтов), в каждом из которых бестселлер и новая книга имеют высокий балл. Это может быть организованной попыткой издателя направить потребителей по нужному следу. Честные пользователи награждаются, а нечестные наказываются, например, через систему очков, похожую на систему построения лояльности, так что честные пользователи могут заработать скидки или кредит.

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

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

Недавнее исследование Джонатана Херлокера (Jonathan Herlocker) из государственного Университета Орегона и его коллеги оценили несколько систем по рекомендации фильмов, построенных по методу коллаборативной фильтрации. С использованием 5-балльной шкалы проводилось сравнение оценок, которые пользователи должны были бы поставить конкретным фильмам, исходя из указанных ими предпочтений, с оценками, которые они реально выставили. Прогнозируемые и реальные оценки отличались минимум на 0.73 пункта. Д-р Херлокер делает предположение, что это могло бы являться свидетельством фундаментального ограничения на показатель точности работы систем рекомендаций, основанных на методе коллаборативной фильтрации. По его мнению, нет смысла стараться выдавать максимально точные прогнозы, так как они всё равно не сравнимы по точности с вариантами собственных мнений людей. Возможно, д-р Херлокер прав, или технологиям ещё есть куда развиваться.

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


in english
контакты

ИСКАТЬ

Оплата и Доставка цветов по кемерово и Юрге среди-цветов.ру.