ИСПОЛЬЗОВАНИЯ МЕТОДОЛОГИИ PLSA ДЛЯ АДАПТИВНОЙ КОРРЕКТИРОВКИ МОДЕЛИ ПОЛЬЗОВАТЕЛЯ

Аннотация

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

Полный текст

Потребность в компьютерных системах, осуществляющих автоматический поиск и фильтрацию информации в огромных по объему хранилищах документов (например в Интернете), привела к появлению целой области исследований, связанных с созданием поисковых интерфейсов пользователя [1]. В настоящее время основными инструментами поиска информации в сети являются поисковые сервисы. Поиск информации, как правило, начинается с введения запроса в одном из поисковых сервисов, в ответ на который поисковый сервис в большинстве случаев выдает тысячи документов, после чего полученная информация делится на релевантную (значимую для пользователя) и нерелевантную. Не нарушая общности, здесь и далее будем считать, что информация представляется пользователю в виде текстовых документов. Индивидуализация (персонализация) интерфейса пользователя благодаря алгоритмам идентификации позволяет учитывать его неявные интересы и использовать их в контексте текущего запроса. Тем самым еще на стадии обработки результатов запроса большая часть нерелевантных документов отсеивается. Один из распространенных подходов к представлению документов (и запросов) при извлечении информации из сети основан на понятии модели векторного гиперпространства [2], которое в методологии латентной семантической индексации заменяется представлением документа в латентном пространстве меньшей размерности [3]. В данной стате предлагается расширить понятие латентного семантического пространства с учетом текущих интересов пользователя. Методология PLSA в области извлечения информации. Проблема поиска (извлечения) текстовой информации из ее обширных хранилищ (репозитариев) приобрела особую актуальность в связи с появлением всемирной сети Интернет. В настоящее время каждый пользователь, имеющий доступ в Интернет, может обратиться ко всем источникам информации, представленным в нем. Казалось бы, что теперь своевременное получение необходимой информации по интересующей тематике обеспечиваться без особых затруднений. Однако на деле оказывается, что качество поиска информации при всей ее доступности очень низкое. В поисковых сервисах отсутствуют эффективные алгоритмы поиска релевантной информации, т. е. набора релевантных документов, отражающих суть запроса. И в ответ на запрос такой сервис может выдать сколь угодно большое количество документов, либо отдаленно отражающих сферу интересов пользователя, либо вовсе не имеющих никакой связи с запросом. Для разрешения проблемы поиска информации могут использоваться два подхода: с одной стороны -традиционный лингвистический подход, сторонники которого пытаются научить компьютер естественному языку, с другой - использование статистических методов, к которым и относится PLSA (Probabilistic Latent Semantic Analysis - вероятностный латентный семантический анализ). Первоначально было введено понятие модели векторного пространства [2], в котором любой документ представлялся как вектор частот появления в нем определенных терминов. В этом подходе отношения между документами и терминами задавались в виде матрицы смежности A, элементом w j которой является частота появления термина tj в документе d. Обозначим через m количество проиндексированных терминов в коллекции документов d, а через n -количество самих документов. В общем случае элементом wj матрицы A является некоторый вес, поставленный в соответствие паре «документ-термин» (d„ tj). После того как все веса заданы, матрица A становится отображением коллекции документов в векторном гиперпространстве. Таким образом, каждый документ можно представить как вектор весов терминов: A = ' w11 • • w1n ' • • • • • • w V m1 • • w mn J — (d1 dn ) — V tm . (1) Подход LSA (Latent Semantic Analysis - латентный семантический анализ), предложенный в работе [3], заключается в отображении документа в латентное семантическое пространство, которое несет в себе основную смысловую нагрузку. Цель такого отображения состоит в том, чтобы отразить скрытую (латентную) связь между терминами и документами, что достигается использованием сингулярного (SVD) разложения матрицы A. Оценка схожести документов формируется по близости расположения точек латентного семантического пространства. В основе методологии PLSA лежит идея, предложенная в LSA и описанная в [4], когда в латентное семантическое пространство вводятся понятия латентного класса: zeZ = {Z1 , ..., zk}, условных вероятностей среди документов: deD = {d1, ..., dk}, и терминов weW = {w1, ..., wk}, а также предполагается, что распределение слов, принадлежащих данному классу, не зависит от документа и пары наблюдений «документ-термин» (d, w) не связаны между собой. Распределение терминов в документе P(w|d) задается выпуклой комбинацией факторов P(w|z) и P(z|d): P(w I d) = X P(w I z)P(z I d). (2) zeZ Совместная вероятность документа и термина определяется соотношением P(d, w) = P(d)P(w | d) = X P(z)P(d | z)P(w | z). (3) zeZ Используя алгоритм максимизации математического ожидания (Expectation-Maximization, EM Algorithm), который состоит из этапов Е и М, можно оценить вероятности P(w|z) и P(z|d), максимизируя логарифмическую функцию правдоподобия: L = X X n(d, w)log P(d, w), (4) deD weW где n(d, w) - частота (количество) появлений термина w в документе d. Вероятность того что появление термина w в документе d объясняется принадлежностью их к классу z, на этапе E оценивается следующим образом: P(z)P(d | z)P(w | z) P(z | d, w) = X P(z')P(d | z')P(w | z') ' z'eZ (5) На этапе М происходит переоценка вероятностей: X n(d, w)P(z | d, w) P(w | z) = d -, XXn(d, w')P(z | d, w') P(d|z) = X n(d, w)P(z | d, w) w_ X n(d', w)P(z | d', w)" d ',w (6) P( z|d, w) =: X n(d, w)P(z | d, w) Xn(d, w) d ,w В работе [1] Т. Хофман предложил обобщенную модель для оценивания условной вероятности, которую он назвал ослабленной процедурой максимизации математического .ожидания (Tempered Expectation Maximization, TEM). При этом на этапе E в оценку условной вероятности вносится регуляризационный параметр р: Pp(z | d,w) =- P(z) [P(d | z)P(w | z)] P iP' (7) X P(z') [P(d | z')P(w | z')]P z'eZ Согласно (2), любая условная вероятность P(w|d) может быть аппроксимирована полиномом, представляющим собой выпуклую комбинацию условных вероятностей P(w|z). Геометрической интерпретацией весовых коэффициентов P(z d) являются координаты документа в подпространстве, определяемом как латентное семантическое пространство [1]. Модель (профиль) пользователя. Рассмотрим схему моделирования интересов пользователя, основанную на инициализации начального профиля и его последовательной корректировке в процессе работы. Документы могут быть представлены как векторы латентного семантического пространства таким образом, как это показано выше. Однако для того чтобы следить и непрерывно анализировать возможные изменения интересов пользователя, необходимо ввести понятие временного измерения в латентном семантическом пространстве, рассматривая уже не само латентное семантическое пространство, а его модификацию - временное латентное семантическое пространство. Каждое измерение такого векторного пространства (за исключением временного, которое полагается равным нулю) представляет собой условные вероятности при заданном классе P(^|z), а документы являются векторами с весовыми коэффициентами (координатами) P(z|d). Запросы, как и сами документы, также могут быть представлены в виде векторов во временном латентном семантическом пространстве. Кроме весов P(z|Q) у них имеется дополнительное (временное) измерение (текущий вес), первоначально равный некоторой положительной величине, уменьшающейся с течением времени, исходя из предположения о падении интереса пользователя к определенной тематике при отсутствии ее фигурирования в запросах продолжительное время. Если пользователь инициирует запрос, связанный с категорией из его текущего профиля, то вес данной категории может быть либо стабилизирован на некоторое время, либо увеличен. Согласно геометрии латентного семантического пространства, запрос, состоящий из терминов, проецируется в латентное семантическое пространство [4]. Таким образом, гиперповерхность S, образованная запросом Qu является пересечением вероятностных поверхностей всех классов, которые введены 25 Математика, механика, информатика в латентное семантическое пространство и в которых с определенной вероятностью фигурирует данный термин: S; = П НШ . k Алгоритм адаптивной коррекции профиля пользователя основан на неявной обратной связи с пользователем, которая реализуется исходя из истории его запросов. На вход алгоритма поступает запрос пользователя, на выход - одна или более троек (триплетов) вида (C;, W, а;), где С; - категория интересов; W; - текущий вес; а; - уровень изменчивости (смысл данной величины состоит в том, чтобы отразить, насколько изменяются интересы пользователя в рамках текущего запроса по отношению к прошлым запросам). Итак, профиль пользователя представляет собой набор троек, организованный таким образом, что интересы пользователя разделены на два типа: краткосрочные (краткосрочный профиль) и долгосрочные (долгосрочный профиль). Как правило, емкость долгосрочного профиля больше емкости краткосрочного. Структуру профиля можно представить таблицей (см. рисунок). При этом считается, что тройки, у которых величина текущего веса положительная, относятся к краткосрочному профилю, а если величина этого веса отрицательная, то к долгосрочному профилю. При этом для троек, находящихся в краткосрочном профиле, текущий вес уменьшается линейно, а для троек, находящихся в долгосрочном профиле, снижение весов экспоненциально. Категория Текущий вес Уровень изменчивости Краткосрочный профиль пользователя Формально профиль в текущий момент ; описывается следующим образом: РГ; = {(С,, Wj, а,);, j=1, k }. (8) При этом РГ; = PrR; U PrL;, (9) где PrR; = {(С,, Wj, aj)i | V W, > 0, j=1, k} - краткосрочный профиль; PrLj = {(Cj, Wj, aj); | V Wj < 0, j=1, k} -долгосрочный профиль. Уровень изменчивости а; рассчитывается как близость двух последовательных запросов Q; и Q-1, представленных в пространстве частот их терминов: X n(Q;, w)n (Q;-^ w) a. = w , (10) X n(Q;, w)2 X n(Q;-1, w)2 \ w' d где n(Q;, w) - взвешенные частоты терминов. Алгоритм непрерывной корректировки профиля пользователя. Данный алгоритм в своей работе использует хранилище предыдущих запросов пользователя. В текущий момент времени i пользователь вводит новый запрос, который после соответствующей обработки помещается в хранилище запросов. Обновленное (или дополненное) в момент времени i текущим запросом хранилище запросов будем обозначать Qi . Перед тем как передать запрос для работы алгоритму, этот запрос обрабатывается с целью выделения ключевых терминов. Далее производится пересчет взвешенных частот терминов в хранилище запросов Qi с учетом нового запроса. Когда пользователь вводит очередной запрос, его ключевым словам (терминам) назначаются наибольшие веса. При поступлении запроса в хранилище выполняется проверка на наличие в нем терминов, присутствующих в данном запросе. Если термин встречается впервые, то при его занесении в хранилище вес остается без изменений; если же такой термин в хранилище уже существует (это означает, что пользователь когда-то уже использовал запрос, включающий в себя данный термин), то его весовой коэффициент пересчитывается. В результате происходит нормирование весовых коэффициентов. Категории интересов Ci для включения в текущий профиль пользователя извлекаются из хранилища с использованием методологии PLSA. Алгоритм непрерывной корректировки профиля пользователя состоит из 11 шагов и работает следующим образом. Шаг 1. Инициализировать хранилище запросов Qi = {w1;, w2i, ..., wki }, где wki - термины хранилища запросов, k = 1, ., M. Шаг 2. Выделить набор ключевых терминов текущего запроса. Шаг 3. Скорректировать весовые коэффициенты терминов и произвести их нормировку с учетом нового запроса. Шаг 4. Рассчитать уровень изменчивости ai. Шаг 5. Рассчитать условные вероятности классов, используя процедуру TEM: P(z | Qi ) = P(wfa. )Pp (z | Qi , wki ) = = X P(wfa) P( z) tP(Qi|z) P( wk|z) ]PB. wkiX P(z') [P(Q;|z')P(Wki.|z')]P z' Шаг 6. Рассчитать вероятность категории с. для заданного класса латентного семантического пространства: У^П(а1 , С; ,)Pp ( z | Q; , C; ) P(C | z)=^Q-. ; x«(c; , Q;)Pp (z|c;, Q;) c'„q, Шаг 7. Рассчитать вероятность включения категории Ci для текущего состояния хранилища запросов Qi: P(C;\Q; ) =X P(C; | z)P(z | Q; ). zeZ Кино Музыка Квантовая физика Спорт 95 85 35 70 0,60 0,45 0,20 0,15 26 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Шаг 8. Занести категорию в профиль пользователя, включив соответствующую тройку (С;, W, а;) в профиль согласно схеме (см. рисунок). Шаг 9. Если уровень изменчивости а; > а0, где а0 - заданная величина, то увеличить текущий вес категории С; на величину Д W; : W, = W, + ДWI . Шаг 10. Отсортировать последовательность троек (С, W, а;) в профиле по порядку убывания веса W; . Шаг 11. Сохранить получившийся профиль. Таким образом, в данной статье был рассмотрен алгоритм непрерывной корректировки модели (профиля) пользователя. Для успешного построения алгоритма предложена схема организации профиля пользователя в виде множества троек вида (категория интересов C;, текущий вес категории w;, уровень изменчивости а.). При этом профиль делится на две группы (два подпрофиля): краткосрочный и долгосрочный -для учета краткосрочных и долгосрочных интересов пользователя (в том числе неявных). Кроме того, было введено понятие временного измерения в латент ном семантическом пространстве, что позволило адаптировать методологию PLSA для непрерывной оценки изменений интересов пользователя. Применение предложенного алгоритма для подстройки модели в процессе ее работы с использованием неявной обратной связи, приближает нас к созданию высококачественных и эффективных поисковых систем с персонализированным интерфейсом.