Использования методологии PLSA для адаптивной корректировки модели пользователя

Потребность в компьютерных системах, осуществляющих автоматический поиск и фильтрацию информации в огромных по объему хранилищах документов (например в Интернете), привела к появлению целой области исследований, связанных с созданием поисковых интерфейсов пользователя [1].

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

Индивидуализация (персонализация) интерфейса пользователя благодаря алгоритмам идентификации позволяет учитывать его неявные интересы и использовать их в контексте текущего запроса. Тем самым еще на стадии обработки результатов запроса бо́ ль-шая часть нерелевантных документов отсеивается.

Один из распространенных подходов к представлению документов (и запросов) при извлечении информации из сети основан на понятии модели векторного гиперпространства [2], которое в методологии латентной семантической индексации заменяется представлением документа в латентном пространстве меньшей размерности [3]. В данной стате предлагается расширить понятие латентного семантического пространства с учетом текущих интересов пользователя.

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

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

Для разрешения проблемы поиска информации могут использоваться два подхода: с одной стороны – традиционный лингвистический подход, сторонники которого пытаются научить компьютер естественному языку, с другой – использование статистических методов, к которым и относится PLSA (Probabilistic Latent Semantic Analysis – вероятностный латентный семантический анализ).

Первоначально было введено понятие модели векторного пространства [2], в котором любой документ представлялся как вектор частот появления в нем определенных терминов. В этом подходе отношения между документами и терминами задавались в виде матрицы смежности A , элементом w ij которой является частота появления термина t j в документе d i .

Обозначим через m количество проиндексированных терминов в коллекции документов d , а через n – количество самих документов. В общем случае элементом w ij матрицы A является некоторый вес, поставленный в соответствие паре «документ–термин» ( d i , t j ). После того как все веса заданы, матрица A становится отображением коллекции документов в векторном гиперпространстве. Таким образом, каждый документ можно представить как вектор весов терминов:

A =

Г w_n

W 1

V ^w m 1

w 1 n

(t t1

w mn у

- ( d i

d n ) -

. (1)

V tm J

*Работа выполнена при финансовой поддержке ФЦП «Научные и научно-педагогические кадры инновационной России на 2009–2013 гг.» и ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007–2013 гг.», № 2011-1.9-519-005.

Подход LSA (Latent Semantic Analysis – латентный семантический анализ), предложенный в работе [3], заключается в отображении документа в латентное семантическое пространство, которое несет в себе основную смысловую нагрузку. Цель такого отображения состоит в том, чтобы отразить скрытую (латентную) связь между терминами и документами, что достигается использованием сингулярного (SVD) разложения матрицы A . Оценка схожести документов формируется по близости расположения точек латентного семантического пространства.

В основе методологии PLSA лежит идея, предложенная в LSA и описанная в [4], когда в латентное семантическое пространство вводятся понятия латентного класса:

z e Z = { z 1 , , Z k } , условных вероятностей среди документов:

deD = {di, .... dk}, и терминов we W = {wi, .... Wk}, а также предполагается, что распределение слов, принадлежащих данному классу, не зависит от документа и пары наблюдений «документ–термин» (d, w) не связаны между собой.

Распределение терминов в документе P ( w|d ) задается выпуклой комбинацией факторов P ( w|z ) и P ( z|d ):

P ( w | d ) = S P ( w\z ) P ( z\d ).         (2)

z e Z

Совместная вероятность документа и термина определяется соотношением

P ( d , w ) = P ( d ) P ( w | d ) = S P ( z ) P ( d | z ) P ( w | z ). (3) z e Z

Используя алгоритм максимизации математического ожидания (Expectation-Maximization, EM Аlgorithm), который состоит из этапов Е и М, можно оценить вероятности P ( w|z ) и P ( z|d ), максимизируя логарифмическую функцию правдоподобия:

L = S S n ( d , w )log P ( d , w ),         (4)

deD weW где n(d, w) – частота (количество) появлений термина w в документе d.

Вероятность того что появление термина w в документе d объясняется принадлежностью их к классу z , на этапе E оценивается следующим образом:

P ( z\d , w ) =    ^{P ( z} ) ^{P ( d | z} ) ^{P ( w | z} )    .       (5)

S P ( z ' ) P ( d | z ' ) P ( wlz ' ) z e z

На этапе М происходит переоценка вероятностей:

S n ( d , w ) P ( z | d , w )

P ( w | z ) = =4^---------------,

SS n ( d , w ‘ ) P ( z | d , w ‘ ) w ' d

S n ( d , w ) P ( z | d , w )

P ⁽ d ^{| z} ) = 2 w n ( d ' . w ) p ( z | d ' . w )^, d ', w

P ( z | d , w ) =

S n ( d , w ) P ( z | d , w ) d , w

S ^{n ( d} , ^w )

d , w

В работе [1] Т. Хофман предложил обобщенную модель для оценивания условной вероятности, которую он назвал ослабленной процедурой максимизации математического .ожидания (Tempered Expectation Maximization, TEM). При этом на этапе E в оценку условной вероятности вносится регуляризационный параметр p:

P (z)[ P (d\z) P (w|z )]в pe(z | d.w) = —----4.     (7)

S P (z ‘) [ p (d\z ‘) P (w\z ')]в z 'eZ

Согласно (2), любая условная вероятность P ( w|d ) может быть аппроксимирована полиномом, представляющим собой выпуклую комбинацию условных вероятностей P ( w|z ). Геометрической интерпретацией весовых коэффициентов P ( z d ) являются координаты документа в подпространстве, определяемом как латентное семантическое пространство [1].

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

Документы могут быть представлены как векторы латентного семантического пространства таким образом, как это показано выше. Однако для того чтобы следить и непрерывно анализировать возможные изменения интересов пользователя, необходимо ввести понятие временного измерения в латентном семантическом пространстве, рассматривая уже не само латентное семантическое пространство, а его модификацию – временное латентное семантическое пространство. Каждое измерение такого векторного пространства (за исключением временного, которое полагается равным нулю) представляет собой условные вероятности при заданном классе P(• |z), а документы являются векторами с весовыми коэффициентами (координатами) P(z|d).

Запросы, как и сами документы, также могут быть представлены в виде векторов во временном латентном семантическом пространстве. Кроме весов P ( z|Q ) у них имеется дополнительное (временное) измерение (текущий вес), первоначально равный некоторой положительной величине, уменьшающейся с течением времени, исходя из предположения о падении интереса пользователя к определенной тематике при отсутствии ее фигурирования в запросах продолжительное время. Если пользователь инициирует запрос, связанный с категорией из его текущего профиля, то вес данной категории может быть либо стабилизирован на некоторое время, либо увеличен.

Согласно геометрии латентного семантического пространства, запрос, состоящий из терминов, проецируется в латентное семантическое пространство [4]. Таким образом, гиперповерхность Si, образованная запросом Qi, является пересечением вероятностных поверхностей всех классов, которые введены в латентное семантическое пространство и в которых с определенной вероятностью фигурирует данный термин:

5 = П H k..

k

Алгоритм адаптивной коррекции профиля пользователя основан на неявной обратной связи с пользователем, которая реализуется исходя из истории его запросов. На вход алгоритма поступает запрос пользователя, на выход – одна или более троек (триплетов) вида ( C , , W , , a , ), где C , - категория интересов; W , - текущий вес; a ,- - уровень изменчивости (смысл данной величины состоит в том, чтобы отразить, насколько изменяются интересы пользователя в рамках текущего запроса по отношению к прошлым запросам).

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

Кино	Музыка	Квантовая физика	Спорт
95	85	35	70
0,60	0,45	0,20	0,15

Категория

Текущий вес

Уровень изменчивости

Краткосрочный профиль пользователя

Формально профиль в текущий момент описы- вается следующим образом:

Pr , = {( C j , W j , a ,) , , j= 1, k}.          (8)

При этом

Pr , = PrR , и PrL , ,                (9)

где PrR , = {( C j , W j , a , ), | V W j >  0, j= 1, k } - краткосрочный профиль; PrL , = {( C j , W j , a j ) , | V W j <  0, j= 1, k } -долгосрочный профиль.

Уровень изменчивости a , • рассчитывается как близость двух последовательных запросов Q i и Q i– 1 , представленных в пространстве частот их терминов:

E ^{n ( Q} , ^w ) ^{n ( Q} -i , w ) a i = , w                 =,

E n ( Q , , w ) 2 E n ( Q -i , w ) 2

где n(Q , , w ) - взвешенные частоты терминов.

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

Перед тем как передать запрос для работы алгоритму, этот запрос обрабатывается с целью выделения ключевых терминов. Далее производится пересчет взвешенных частот терминов в хранилище запросов Q с учетом нового запроса. Когда пользователь вводит очередной запрос, его ключевым словам (терминам) назначаются наибольшие веса. При поступлении запроса в хранилище выполняется проверка на наличие в нем терминов, присутствующих в данном запросе. Если термин встречается впервые, то при его занесении в хранилище вес остается без изменений; если же такой термин в хранилище уже существует (это означает, что пользователь когда-то уже использовал запрос, включающий в себя данный термин), то его весовой коэффициент пересчитывается. В результате происходит нормирование весовых коэффициентов. Категории интересов C для включения в текущий профиль пользователя извлекаются из хранилища с использованием методологии PLSA. Алгоритм непрерывной корректировки профиля пользователя состоит из 11 шагов и работает следующим образом.

Шаг 1 . Инициализировать хранилище запросов Q = { w 1 , w 2 , …, w k }, где w k – термины хранилища запросов, k = 1, …, M.

Шаг 2. Выделить набор ключевых терминов текущего запроса.

Шаг 3 . Скорректировать весовые коэффициенты терминов и произвести их нормировку с учетом нового запроса.

Шаг 4. Рассчитать уровень изменчивости a , .

Шаг 5 . Рассчитать условные вероятности классов, используя процедуру TEM:

P ( zQ) = P ( w_ti) P e ( z | Q , w_ti) =

= S P ( W k, ) ^{P ( z} ) [ ^{P ( Q} ,\ z ) ^{P (} w kA z ^{) ] в} .

W^      • E P (z ‘) [ P (Q,|z ‘) P (Wk,|z ‘)]e z'

Шаг 6. Рассчитать вероятность категории C для заданного класса латентного семантического пространства:

S n ( Q , , C , ,) P e ( z | Q , , C , ) p ( C I z ) = -^Q -----------------------.

^, s n ( c ; , q , ) P e ( zic ; , q , ) C i ^' , Q i ^'

Шаг 7 . Рассчитать вероятность включения категории C для текущего состояния хранилища запросов Q :

p ( C , I Q , ) = E p ( C , | z ) p ( z | Q , ).

z e Z

Шаг 8. Занести категорию в профиль пользователя, включив соответствующую тройку ( C i , W i , α i ) в профиль согласно схеме (см. рисунок).

Шаг 9 . Если уровень изменчивости α i >  α 0 , где α 0 – заданная величина, то увеличить текущий вес категории C i на величину Δ W i :

W i = W i + ΔW i .

Шаг 10 . Отсортировать последовательность троек ( C i , W i , α i ) в профиле по порядку убывания веса W i .

Шаг 11 . Сохранить получившийся профиль.

Таким образом, в данной статье был рассмотрен алгоритм непрерывной корректировки модели (профиля) пользователя. Для успешного построения алгоритма предложена схема организации профиля пользователя в виде множества троек вида (категория интересов Ci, текущий вес категории wi, уровень изменчивости αi). При этом профиль делится на две группы (два подпрофиля): краткосрочный и долгосрочный – для учета краткосрочных и долгосрочных интересов пользователя (в том числе неявных). Кроме того, было введено понятие временного измерения в латент- ном семантическом пространстве, что позволило адаптировать методологию PLSA для непрерывной оценки изменений интересов пользователя.

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