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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Начало раздела Максимизация правдоподобия)
(Максимизация правдоподобия продолжение)
Строка 54: Строка 54:
: <tex>C</tex> — нормировочный множитель, зависящий только от чисел <tex>n_{dw}</tex>
: <tex>C</tex> — нормировочный множитель, зависящий только от чисел <tex>n_{dw}</tex>
С учетом {{eqref|1}} и того факта, что <tex>Cp(d)^{n_{dw}</tex> не зависит от параметров <tex>\Phi,\Theta</tex> прологарифмируем правдоподобие, получив задачу максимизации:
С учетом {{eqref|1}} и того факта, что <tex>Cp(d)^{n_{dw}</tex> не зависит от параметров <tex>\Phi,\Theta</tex> прологарифмируем правдоподобие, получив задачу максимизации:
 +
{{eqno|2}}
::<tex>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}</tex>
::<tex>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}</tex>
при ограничениях неотрицательности и нормировки
при ограничениях неотрицательности и нормировки
: <tex>\varphi_{wt} \geq 0, \; \theta_{td} \geq 0, \; \sum_{w \in W} \varphi_{wt} = 1, \; \sum_{t \in T} \theta_{td} = 1 </tex>.
: <tex>\varphi_{wt} \geq 0, \; \theta_{td} \geq 0, \; \sum_{w \in W} \varphi_{wt} = 1, \; \sum_{t \in T} \theta_{td} = 1 </tex>.
 +
Задача {{eqref|2}} может быть интерпретирована двумя способами:
 +
 +
=== Интерпретация 1 ===
 +
Выражение {{eqref|2}} есть минимизация суммарной (по <tex>d \in D</tex>) [[Дивергенция Кульбака–Лейблера|дивергенции Кульбака–Лейблера]] между тематическими <tex>p(w|d)</tex> и униграммными <tex>\hat{p}(w|d) = \frac{n_{dw}}{n_d}</tex> моделями:
 +
::<tex>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</tex>
 +
 +
=== Интерпретация 2 ===
 +
Выражение {{eqref|2}} стохастическое матричное разложение:
 +
::<tex>\left \| F - \Phi\Theta \right \|_{KL} \to \min_{\Phi,\Theta}</tex>, где
 +
:<tex>F=(\hat{p}(w|d))_{W \times D}</tex> — известная матрица исходных данных;
 +
:<tex>\left \|F - \Phi\Theta \right \|_{KL} </tex> - норма Кульбака–Лейблера.
 +
 +
== Аналитическое решение ==
 +
Для нахождения аналитического решения задачи максимизации {{eqref|2}} запишем [[лагранжиан]] задачи. При этом учтем ограничения нормировки, но проигнорируем ограничения неотрицательности. Позже убедимся, что решение действительно всегда является неотрицательным.
 +
::<tex>\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) </tex>
== Алгоритм ==
== Алгоритм ==

Версия 21:47, 27 февраля 2014

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

Содержание

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

Пусть 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)

Алгоритм

Недостатки

Примечания


Личные инструменты