Вероятностный латентный семантический анализ

Материал из MachineLearning.

(Различия между версиями)

Версия 05:59, 9 марта 2014

Вероятностный латентный семантический анализ (англ. Probabilistic Latent Semantic Analysis, PLSA) - вероятностная тематическая модель представления текста на естественном языке. Модель называется латентной, так как предполагает введение скрытого (латентного) параметра - темы. Модель предложена Томасом Хофманном в 1999 году^[1]. Применяется в задаче тематического моделирования.

Содержание

1 Формальная постановка задачи
2 Максимизация правдоподобия
- 2.1 Интерпретация 1
- 2.2 Интерпретация 2
3 Аналитическое решение
4 Алгоритм
5 Недостатки
6 Оценка качества тематических моделей
- 6.1 Перплексия
7 Примечания

Формальная постановка задачи

Основная статья: Тематическое моделирование

Пусть $D$ — множество (коллекция) текстовых документов, $W$ — множество (словарь) всех употребляемых в них терминов (слов или словосочетаний). Каждый документ $d \in D$ представляет собой последовательность $n_d$ терминов ( $w_1, . . . , w_n_d$ ) из словаря W. Термин может повторяться в документе много раз.

Пусть существует конечное множество тем $T$ , и каждое употребление термина $w$ в каждом документе $d$ связано с некоторой темой $t \in T$ , которая не известна. Формально тема определяется как дискретное (мультиномиальное) вероятностное распределение в пространстве слов заданного словаря $W$ ^[1].

Введем дискретное вероятностное пространство $D \times W \times T$ . Тогда коллекция документов может быть рассмотрена как множество троек $(d, w, t)$ , выбранных случайно и независимо из дискретного распределения $p(d, w, t)$ . При этом документы $d \in D$ и термины $w \in W$ являются наблюдаемыми переменными, тема $t \in T$ является латентной (скрытой) переменной.

Требуется найти распределения терминов в темах $p(w|t) \equiv \varphi_{wt}$ для всех тем $t \in T$ и распределения тем в документах $p(t|d) \equiv \theta_{td}$ для всех документов $d \in D$ . При этом делается ряд допущений.

С учетом гипотезы условной независимости $p(w|d,t) = p(w|t)$ по формуле полной вероятности получаем вероятностную модель порождения документа $d$ :

(1)

$p(w|d) = \sum_{t \in T} p(w|d,t)p(t|d) = \sum_{t \in T}p(w|t)p(t|d)=\sum_{t \in T}\varphi_{wt}\theta_{td}$

Введем следующие обозначения:

$n_{dwt}$ - число троек $(d,w,t)$ во всей коллекции. Другими словами, это число поялвений термина $w$ в связи с темой $t$ в документе $d$ ;

$n_{dw} = \sum_{t \in T} n_{dwt}$ - число вхождений термина $w$ в документ $d$ ;

$n_{dt} = \sum_{w \in d} n_{dwt}$ - число вохждений всех терминов, связанных с темой $t$ в документ $d$ ;

$n_{wt} = \sum_{d \in D} n_{dwt}$ - число поялвений термина $w$ в связи с темой $t$ во всех документах коллеккции $D$ ;

$n_{w} = \sum_{d \in D}\sum_{t \in T} n_{dwt}$ - число вхожений терина $w$ в коллекцию;

$n_{d} = \sum_{w \in d}\sum_{t \in T} n_{dwt}$ - длина документа $d$ ;

$n_{t} = \sum_{d \in D}\sum_{w \in d} n_{dwt}$ - «длина темы» $t$ , то есть число появления терминов в коллекции, связанных с темой $t$ ;

$n = \sum_{d \in D}\sum_{w \in d}\sum_{t \in T} n_{dwt}$ - длина коллекции.

Максимизация правдоподобия

Правдоподобие — это плотность распределения выборки $D$ :

$p(D)=\prod^n_{i=1}p_i(d,w)=\prod_{d \in D}\prod_{w \in d}p(d,w)^{n_{dw}}$

Рассмотрим вероятностную тематическую модель $p(D,\Phi,\Theta)$ , где

$\Phi=(\varphi_{wt})_{W \times T}$ - искомая матрица терминов тем, $\varphi_{wt} \equiv p(w|t)$

$\Theta=(\theta_{td})_{T \times D}$ - искомая матрица тем документов, $\theta_{td}\equiv p(t|d)$ .

Запишем задачу максимизации правдоподобия

$p(D,\Phi,\Theta)=C\prod_{d \in D}\prod_{w \in d}p(d,w)^{n_{dw}}=\prod_{d \in D}\prod_{w \in d}p(d|w)^{n_{dw}}Cp(d)^{n_{dw}} \to \max_{\Phi,\Theta}$ , где

$C$ — нормировочный множитель, зависящий только от чисел $n_{dw}$

С учетом (1) и того факта, что $Cp(d)^{n_{dw}$ не зависит от параметров $\Phi,\Theta$ прологарифмируем правдоподобие, получив задачу максимизации:

(2)

$L(D,\Phi,\Theta)=\sum_{d \in D}\sum_{w \in d}n_{dw}\ln\sum_{t \in T}\varphi_{wt}\theta_{td} \to \max_{\Phi,\Theta}$

при ограничениях неотрицательности и нормировки

$\varphi_{wt} \geq 0, \; \theta_{td} \geq 0, \; \sum_{w \in W} \varphi_{wt} = 1, \; \sum_{t \in T} \theta_{td} = 1$ .

Задача (2) может быть интерпретирована двумя способами:

Интерпретация 1

Выражение (2) есть минимизация суммарной (по $d \in D$ ) дивергенции Кульбака–Лейблера между тематическими $p(w|d)$ и униграммными $\hat{p}(w|d) = \frac{n_{dw}}{n_d}$ моделями:

$KL(\hat{p}||p) =\sum_{d \in D} n_d \sum_{w \in d}\hat{p}(w|d)\ln\frac{\hat{p}(w|d)}{p(w|d)} \to \min$

Интерпретация 2

Выражение (2) стохастическое матричное разложение:

$\left \| F - \Phi\Theta \right \|_{KL} \to \min_{\Phi,\Theta}$ , где

$F=(\hat{p}(w|d))_{W \times D}$ — известная матрица исходных данных;

$\left \|F - \Phi\Theta \right \|_{KL}$ - норма Кульбака–Лейблера.

Аналитическое решение

Для нахождения аналитического решения задачи максимизации (2) запишем лагранжиан задачи. При этом учтем ограничения нормировки, но проигнорируем ограничения неотрицательности. Позже убедимся, что решение действительно всегда является неотрицательным.

$\mathcal {L}(\Phi,\Theta) = \sum_{d \in D}\sum_{w \in d}n_{dw}\ln\sum_{t \in T}\varphi_{wt}\theta_{td} - \sum_{t \in T}\lambda_t(\sum_{w \in d}\varphi_{wt}-1) - \sum_{d \in D}\mu_d(\sum_{t \in T}\theta_{td} -1)$

Продифференцируем лагранжиан по $\varphi_{wt}$ и приравняем к нулю производную, получим:

$\lambda_t = \sum_{d \in D}n_{dw}\frac{\theta_{td}}{p(w|d)}$ .

Домножив обе части на $\varphi_{wt}$ , получим:

$\lambda_t \varphi_{wt}= \sum_{d \in D}n_{dw} \frac{\varphi_{wt}\theta_{td}}{p(w|d)}$ .

Обозначим $H_{dwt} \equiv p(t|d,w)$ - вероятность того, что поялвение термина $w$ в документе $d$ связано с темой $t$ . Тогда по формуле Байеса справедливо:

$H_{dwt} \equiv p(t|d,w) = \frac {p(w|t)p(t|d)} {p(w|d)} = \frac {\varphi_{wt}\theta_{td}} {p(w|d)} = \frac {\varphi_{wt}\theta_{td}} {\sum_s\varphi_{ws}\theta_{sd}}$

Заменив выражение в правой части на $H_{dwt}$ имеем:

(3)

$\lambda_t \varphi_{wt}= \sum_{d \in D}n_{dw} H_{dwt}$ .

Просуммируем (3) по всем $w \in W$ . получим:

$\lambda_t\sum_{w \in W} \varphi_{wt}= \sum_{w \in W} \sum_{d \in D} n_{dw}H_{dwt}$ .

В соответствии с условием нормировки $\sum_{w \in W} \varphi_{wt} = 1$ получаем:

$\lambda_t = \sum_{w \in W} \sum_{d \in D}n_{dw} H_{dwt}$

Выразив из (3) $\varphi_{wt}$ и подставив найденное значение $\lambda_t$ получаем решение:

(4)

$\varphi_{wt} = \frac {\sum_{d \in D}n_{dw} H_{dwt} } {\sum_{w' \in W} \sum_{d \in D} n_{dw'}H_{dw't} }$

Для нахождения значения $\theta_{td}$ поступаем аналогично. После приравнивания производной по $\theta_{td}$ к 0 и домнажения на $\theta_{td}$ получаем выражение:

$\mu_d \theta_{td}= \sum_{w \in d}n_{dw} H_{dwt}$ .

Суммируя по всем темам с учетом условия нормировки $\sum_{t \in T} \theta_{td} = 1$ , находим $\mu_d$ :

$\mu_d= \sum_{t \in T} \sum_{w \in d} n_{dw} H_{dwt}$ .

Выражаем $\theta_{td}$ :

(5)

$\theta_{td} = \frac {\sum_{w \in d}n_{dw} H_{dwt} } { \sum_{w \in d} n_{dw} \sum_{t' \in T} H_{dwt'} }$

Видно, что выражения (4) и (5) всегда удовлетворяют условию неотрицательности.

Алгоритм

Для вычисления значений $\varphi_{wt}$ и $\theta_{td}$ используется EM-алгоритм

E-шаг

На E-шаге, используя текущие значения параметров $\varphi_{wt}$ и $\theta_{td}$ по формуле Байеса вычисляется значение условных вероятностей $H_{dwt} \equiv p(t|d,w)$ для всех тем $T \in t$ для каждого термина $w \in d$ для всех документов $d \in D$ :

$H_{dwt} \equiv p(t|d,w) = \frac {p(w|t)p(t|d)} {p(w|d)} = \frac {\varphi_{wt}\theta_{td}} {\sum_s\varphi_{ws}\theta_{sd}}$

M-шаг

На M-шаге решается обратная задача: по условным вероятностям тем $H_{dwt}$ вычисляются новые приближения $\varphi_{wt}$ и $\theta_{td}$ .

Можно заметить, что величина $\hat{n}_{dwt}=n_{dw}p(t|d,w)=n_{dw}H_{dwt}$ оценивает число $n_{dwt}$ вхождений термина $w$ в документ $d$ , связанных с темой $t$ . При этом оценка не всегда является целым числом. Просуммировав $\hat{n}_{dwt}$ по документам $d$ и по терминам $w$ получим оценки:

$\hat{n}_{wt}=\sum_{d \in D}\hat{n}_{dwt}, \; \hat{n}_t = \sum_{w \in W}\hat{n}_{wt}$

$\hat{n}_{dt}=\sum_{w \in d}\hat{n}_{dwt}, \; \hat{n}_d = \sum_{t \in T}\hat{n}_{dt}$

В соответствии с формулами (4) и (5) вычисляются частотные оценки условных вероятностей $\varphi_{wt}$ и $\theta_{td}$ :

$\varphi_{wt}=\frac{\hat{n}_{wt}}{\hat{n}_t}$

$\theta_{td} = \frac{\hat{n}_{dt}}{\hat{n}_{d}}$

Формирование начальных приближений

Начальные приближения $\varphi_{t}$ и $\theta_{d}$ можно задавать нормированными случайными векторами из равномерного распределения. Другой вариант заключается в проходе по всей коллекции, выборе для каждой пары $(d,w)$ случайной темы и вычислении частотных оценок $\varphi_{wt}=\frac{n_{wt}}{n_t}, \; \theta_{td} = \frac{n_{dt}}{n_{d}}$ для всех $d \in D, w \in W, t \in T$ .

Частичное обучение

В ряде случаев темы документов могут быть известны заранее или могут иметься дополнительные данные о привязке некоторых документов или терминов к темам. Учёт этих данных позволяет улучшить интерпретируемость тем.

Если известно, что документ $d$ относится к подмножеству тем $T_d \subset T$ , то в качестве начального $\theta_{td}$ можно взять равномерное распределение на этом подмножестве:

$\theta^0_{td}=\frac{1}{|T_d|}[t \in T_d]$

Если известно, что подмножество терминов $W_t \subset W$ относится к теме $t$ , то в качестве начального $\varphi_{wt}$ можно взять равномерное распределение на $W_t$

$\varphi^0_{wt}=\frac{1}{|W_t|}[w \in W_t]$

Если известно, что подмножество документов $D_t \subset D$ относится к теме $t$ , то можно взять эмпирическое распределение слов в объединённом документе:

$\varphi^0_{wt}=\frac{\sum_{d \in D_t} n_{dw}}{\sum_{d \in D_t} n_{d}}$

Если для всех тем известны начальные приближения $\varphi^0_{wt}$ , то первая итерация ЕМ-алгоритма при равномерном распределении $\theta^0_{td}$ даёт ещё одну интуитивно очевидную формулу инициализации:

$\theta_{td}=\frac{1}{n_d}\sum_{w \in d}n_{dw}H_{dwt}=\sum_{w \in d}\frac{n_{dw}}{n_d}\frac{\varphi_{wt}}{\sum_s\varphi_{ws}}=\sum_{w \in d}\hat{p}(w|d)\hat{p}(w|t)$ .

Здесь распределение тем в документе $d$ оценивается путём усреднения распределений тем $p(t|w)$ по словам документа $d$ , вычисленных по формуле Байеса.

Недостатки

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

Основными недостатками PLSA являются:

Медленная сходимость на больших коллекциях, так как матрицы $\Phi$ и $\Theta$ в базовом варианте обновляются после прохода всей коллекции, а также необходимость хранить трехмерную матрицу $H_{dwt}$ . Эти проблемы могут быть решены принудительным более частым обновлениям $\Phi$ и $\Theta$ и внесением E-шага внутрь M-шага алгоритма. Развитие этой идеи приводит к рациональному, стохастическому и онлайн алгоритмам PLSA.
Для алгоритма PLSA характерно переобучение, а также неединственность и неустойчивость решения. Это связано с большим числом параметров $\varphi_{wt}$ и $\theta_{td}$ ( $|W|\cdot|T|+|T|\cdot|D|$ ) и на них не накладывается никаких ограничений регуляризации. Кроме того, алгоритм PLSA неверно оценивает вероятность новых слов. Так, если $n_w=0$ , то $\hat{p}(w|t)=0$ для всех $t \in T$ . Последний недостаток особо заметен в том случае, когда в контрольной выборке присутствует большое число новых терминов. Для устранения этой проблемы в алгоритм вводят регуляризации: сглаживание, разреживание,учёт дополнительной внешней информации.
Алгоритм не выделяет нетематические слова. В реальном тексте приличествуют термины, которые не относятся явно ни к одной из тем. Учет таких терминов возможен с помощью робастных тематических моделях, в которые добавляется шумовая и фоновая составляющие.
Алгоритм PLSA не позволяет управлять разреженностью. Действительно, если в начале работы алгоритма $\varphi_{wt} = 0$ или $\theta_{td} = 0$ , то и после завершения работы алгоритма значения этих параметров останется равным 0. Для борьбы с этим недостатком используют регуляризацию и постепенное разреживание.

Оценка качества тематических моделей

Критерии качества тематических моделей делятся на две основные группы: внутренние и внешние. Внутренние критерии оценивают качество модели по той же коллекции документов, по которой эта модель строилась. Внешние критерии используют дополнительную информацию и показывают, насколько хорошо тематическая модель справляется с решением прикладной задачи классификации, категоризации или поиска текстовых документов^[1].

Перплексия

Наиболее распространён внутренний критерий перплексии (perplexity), используемый для оценивания моделей языка в компьютерной лингвистике. Это мера несоответствия или «удивлённости» модели $p(w | d)$ терминам $w$ , наблюдаемым в документах $d$ коллекции $D$ , определяемая через логарифм правдоподобия: