APPLICATION OF PLSA METHODOLOGY FOR ADAPTIVE CORRECTION OF USER MODEL

Abstract

The paper considers the algorithm of the continuous model (profile) correction. The initial data are the initial profile and the previous inquiry history. The PLSA (Probabilistic Latent Semantic Analysis) methodology is used in the algorithm. To achieve the object in view, the term temporary latent semantic space is introduced.

Full Text

Потребность в компьютерных системах, осуществляющих автоматический поиск и фильтрацию информации в огромных по объему хранилищах документов (например в Интернете), привела к появлению целой области исследований, связанных с созданием поисковых интерфейсов пользователя [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 для непрерывной оценки изменений интересов пользователя. Применение предложенного алгоритма для подстройки модели в процессе ее работы с использованием неявной обратной связи, приближает нас к созданию высококачественных и эффективных поисковых систем с персонализированным интерфейсом.