Разбирая данные →
Системы рекомендаций: искусственные имунные системы и эффект идиотипов
Системы рекомендаций:
— Советы от машины
— Холодное начало
— Введение в гибридные системы
— Искусственные имунные системы и эффект идиотипов
Читая разные публикации про интеллектуальный анализ данных и системы рекомендаций я случайно наткнулся на один интереснейших подход к реализации таких систем. В его основе лежит концепция искусственной имунной системы (ИИС, Artificial immune system), согласно которой в компьютерной системе реализуются некоторые свойства имунной системы живых организмов, в том числе способность учиться и запоминать. В системах рекомендаций используется модель, которая описывает концентрацию антител, реагирующих на определенный антиген. Особенный интерес представляет так называемый эффект идиотипов (Idiotype), показывающий, что концентрация антител зависит не только от их сходства с антигеном, но и от сходств друг с другом.
Для тех, кто не знаком с биологией, коротко объясню суть дела. Антиген — это вещества, которые при попадании в организм вызывают ответную реакцию имунной системы. В ответ она вырабатывает антитела, определенный класс белков, которые используются для идентификации и нейтрализации раздражителей. В нашем случае, антиген — это пользователь, а антитела — объекты, с которыми вы его сравниваете. Чтобы это легче было представить, предлагаю считать, что мы рассматриваем систему коллективной фильтрации, где антителами являются другие пользователи.
Теперь перейдем к делу. Уравнение, описывающие концентрацию антител, предложил J. Doyne Farmer:
где:
mi — сходство между антигеном и антителом i,
xi и xj — концентрация антитела i и j соответственно,
y — концентрация антигена,
mij — сходство между антителами i и j,
k1 — коэффициент стимуляции,
k2 — коэффициент подавления,
k3 — коэффициент смертности,
N — число антител.
Рассмотрим каждое слагаемое по отдельности:
Алгоритм работы такой системы достаточно прост.
1. Берем из базы данных первое антитело и рассчитываем его концентрацию по описанной формуле.
2. Результат, очевидно, может быть и позитивным, и отрицательным, если он ниже определенного минимума — отбрасываем антитело и берем следующее.
3. Продолжаем этот цикл пока не закончатся антитела или система не стабилизируется, то есть если за последние плюс-минус десять итераций результат почти не изменится.
У ИИС есть два основных отличия от других систем рекомендаций:
По просьбе читателей приведу простой пример использования ИИС. Допустим, у нас полученная каким-то методом таблица корреляции пользователей A, B, C и Y. Наша система работает по принципу коллективной фильтрации, так что нам надо найти двух пользователей похожих на пользователя Y, и использовать их голоса для дальнейшего предсказания голоса пользователя Y. В этом примере я не буду рассматривать, как мы получили эту таблицу и как мы в дальнейшем используем результат. Рассмотрим только то, как эффект идиотипов повлияет на выбор нужных нам пользователей.
Для обычной системы очевидным выбором станут пользователи B и С, и они будут тоже правы.
Посмотрим, что предложит ИИС. Рассчитаем концентрацию для пользователей B и С. Пусть формула будет перед глазами:
Примем k1 = 0.3, k2 = 0.2, k3 = 0.1, y = 1, по скольку нам надо выбрать два пользователя, N = 2. Тогда:
%20-%200.1\cdot0.9%20=%200.1188)
 - 0.1\cdot0.85 = 0.1088)
Допустим, принятое нами минимальное значение концентрации равно 0.11. XC в него явно не вписывается, поэтому, нам надо поискать ему замену. Рассмотрим пользователя B:
%20-%200.1\cdot0.8%20=%200.1456)
Как видите, не смотря на то, что его сходство с пользователем Y немного меньше, чем пользователя C, его концентрация заметно больше, так-как B меньше похож на A чем C. Так-как мы заменили пользователя C на B, надо пересчитать и концентрацию пользователя A, так-как она зависит от других пользователей:
 - 0.1\cdot0.9 = 0.1656)
Рассчитав концентрацию, мы можем соответственно скорректировать сходство пользователей с пользователем Y:
По опубликованным результатам тестов ИИС действительно дают более точные результаты, чем другие системы, но причина их успеха не во влиянии какого-то отдельного фактора из рассмотренных выше, а в их взаимодействии. За подробностями советую заглянуть в источники:
1. Steve Cayzer и Uwe Aickelin "A Recommender System based on the Immune Network" (pdf)
2. Steve Cayzer и Uwe Aickelin "On the Effects of Idiotypic Interactions for Recommendation
Communities in Artificial Immune Systems" (pdf)
3. Q Chen и U Aickelin "Movie Recommendation Systems Using An Artificial Immune System" (pdf)
Оригинал на моем блоге
— Советы от машины
— Холодное начало
— Введение в гибридные системы
— Искусственные имунные системы и эффект идиотипов
Читая разные публикации про интеллектуальный анализ данных и системы рекомендаций я случайно наткнулся на один интереснейших подход к реализации таких систем. В его основе лежит концепция искусственной имунной системы (ИИС, Artificial immune system), согласно которой в компьютерной системе реализуются некоторые свойства имунной системы живых организмов, в том числе способность учиться и запоминать. В системах рекомендаций используется модель, которая описывает концентрацию антител, реагирующих на определенный антиген. Особенный интерес представляет так называемый эффект идиотипов (Idiotype), показывающий, что концентрация антител зависит не только от их сходства с антигеном, но и от сходств друг с другом.
Для тех, кто не знаком с биологией, коротко объясню суть дела. Антиген — это вещества, которые при попадании в организм вызывают ответную реакцию имунной системы. В ответ она вырабатывает антитела, определенный класс белков, которые используются для идентификации и нейтрализации раздражителей. В нашем случае, антиген — это пользователь, а антитела — объекты, с которыми вы его сравниваете. Чтобы это легче было представить, предлагаю считать, что мы рассматриваем систему коллективной фильтрации, где антителами являются другие пользователи.
Математическое описание
Теперь перейдем к делу. Уравнение, описывающие концентрацию антител, предложил J. Doyne Farmer:
где:
mi — сходство между антигеном и антителом i,
xi и xj — концентрация антитела i и j соответственно,
y — концентрация антигена,
mij — сходство между антителами i и j,
k1 — коэффициент стимуляции,
k2 — коэффициент подавления,
k3 — коэффициент смертности,
N — число антител.
Рассмотрим каждое слагаемое по отдельности:
- Стимуляция антител вопросов вызывать не должна. Это слагаемое увеличивает концентрацию антитела, если оно подходит к антигену.
- Подавление антител гораздо более интересно. Именно в этом слагаемом заключается упомянутый ранее эффект идиотипов. Для системы коллективной фильтрации он увеличивает результат, если пользователи, с которыми мы сравниваем нам антиген будут не только схожи с ним, но и мало похожи между собой. Это позволяет составить более разнообразный набор пользователей.
- Смертность уменьшает результат если абсолютные значения двух первых слагаемых примерно равны. Благодаря ему антитела, которые ни хорошие, ни плохи, отметаются сами собой.
Принципы работы
Алгоритм работы такой системы достаточно прост.
1. Берем из базы данных первое антитело и рассчитываем его концентрацию по описанной формуле.
2. Результат, очевидно, может быть и позитивным, и отрицательным, если он ниже определенного минимума — отбрасываем антитело и берем следующее.
3. Продолжаем этот цикл пока не закончатся антитела или система не стабилизируется, то есть если за последние плюс-минус десять итераций результат почти не изменится.
У ИИС есть два основных отличия от других систем рекомендаций:
- Другой принцип выбора сравниваемых объектов. Если в обычных системах коллективной фильтрации выбираются самые похожие пользователи, то ИИС добавляет еще и эффект идиотипов, благодаря которому конечная подборка получается разнообразнее. Этот эффект можно использовать не только для создания новой подборки, но и для улучшения уже существующих.
- Сам метод расчета рейтинга другой. Если в обычных системах это просто какой-то коэффициент корреляции, то в ИИС этот коэффициент умножается на полученную концентрацию.
Пример
По просьбе читателей приведу простой пример использования ИИС. Допустим, у нас полученная каким-то методом таблица корреляции пользователей A, B, C и Y. Наша система работает по принципу коллективной фильтрации, так что нам надо найти двух пользователей похожих на пользователя Y, и использовать их голоса для дальнейшего предсказания голоса пользователя Y. В этом примере я не буду рассматривать, как мы получили эту таблицу и как мы в дальнейшем используем результат. Рассмотрим только то, как эффект идиотипов повлияет на выбор нужных нам пользователей.
| A | B | C | Y | |
| A | 1 | 0.2 | 0.8 | 0.9 |
| B | 0.2 | 1 | 0.6 | 0.8 |
| C | 0.8 | 0.6 | 1 | 0.85 |
| Y | 0.9 | 0.8 | 0.85 | 1 |
Для обычной системы очевидным выбором станут пользователи B и С, и они будут тоже правы.
Посмотрим, что предложит ИИС. Рассчитаем концентрацию для пользователей B и С. Пусть формула будет перед глазами:
Примем k1 = 0.3, k2 = 0.2, k3 = 0.1, y = 1, по скольку нам надо выбрать два пользователя, N = 2. Тогда:
Допустим, принятое нами минимальное значение концентрации равно 0.11. XC в него явно не вписывается, поэтому, нам надо поискать ему замену. Рассмотрим пользователя B:
Как видите, не смотря на то, что его сходство с пользователем Y немного меньше, чем пользователя C, его концентрация заметно больше, так-как B меньше похож на A чем C. Так-как мы заменили пользователя C на B, надо пересчитать и концентрацию пользователя A, так-как она зависит от других пользователей:
Рассчитав концентрацию, мы можем соответственно скорректировать сходство пользователей с пользователем Y:
Заключение
По опубликованным результатам тестов ИИС действительно дают более точные результаты, чем другие системы, но причина их успеха не во влиянии какого-то отдельного фактора из рассмотренных выше, а в их взаимодействии. За подробностями советую заглянуть в источники:
1. Steve Cayzer и Uwe Aickelin "A Recommender System based on the Immune Network" (pdf)
2. Steve Cayzer и Uwe Aickelin "On the Effects of Idiotypic Interactions for Recommendation
Communities in Artificial Immune Systems" (pdf)
3. Q Chen и U Aickelin "Movie Recommendation Systems Using An Artificial Immune System" (pdf)
Оригинал на моем блоге
15.05.2009 01:07+0400