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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Начало статьи. Некоторая часть перекликается с материалом статьи тематическое моделирование. Кажется лучше сделать отдельные подробны)
(Начало раздела Максимизация правдоподобия)
Строка 24: Строка 24:
С учетом [[Гипотеза условной независимости|гипотезы условной независимости]] <tex>p(w|d,t) = p(w|t)</tex> по [[Формула полной вероятности|формуле полной вероятности]] получаем вероятностную модель порождения документа <tex>d</tex>:
С учетом [[Гипотеза условной независимости|гипотезы условной независимости]] <tex>p(w|d,t) = p(w|t)</tex> по [[Формула полной вероятности|формуле полной вероятности]] получаем вероятностную модель порождения документа <tex>d</tex>:
-
:: <tex>p(w|d) = \sum_{t \in T} p(w|d,t)p(t|d) = \sum_{t \in T}p(w|t)p(t|d)=\varphi_{wt}\theta_{td}</tex>
+
{{eqno|1}}
 +
:: <tex>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}</tex>
 +
 
 +
Введем следующие обозначения:
 +
:<tex>n_{dwt}</tex> - число троек <tex>(d,w,t)</tex> во всей коллекции. Другими словами, это число поялвений термина <tex>w</tex> в связи с темой <tex>t</tex> в документе <tex>d</tex>;
 +
 
 +
 
 +
:<tex>n_{dw} = \sum_{t \in T} n_{dwt}</tex> - число вхождений термина <tex>w</tex> в документ <tex>d</tex>;
 +
:<tex>n_{dt} = \sum_{w \in d} n_{dwt}</tex> - число вохждений всех терминов, связанных с темой <tex>t</tex> в документ <tex>d</tex>;
 +
:<tex>n_{wt} = \sum_{d \in D} n_{dwt}</tex> - число поялвений термина <tex>w</tex> в связи с темой <tex>t</tex> во всех документах коллеккции <tex>D</tex>;
 +
 
 +
 
 +
:<tex>n_{w} = \sum_{d \in D}\sum_{t \in T} n_{dwt}</tex> - число вхожений терина <tex>w</tex> в коллекцию;
 +
:<tex>n_{d} = \sum_{w \in d}\sum_{t \in T} n_{dwt}</tex> - длина документа <tex>d</tex>;
 +
:<tex>n_{t} = \sum_{d \in D}\sum_{w \in d} n_{dwt}</tex> - «длина темы» <tex>t</tex>, то есть число появления терминов в коллекции, связанных с темой <tex>t</tex>;
 +
:<tex>n = \sum_{d \in D}\sum_{w \in d}\sum_{t \in T} n_{dwt}</tex> - длина коллекции.
 +
 
 +
== Максимизация правдоподобия ==
 +
 
 +
Правдоподобие — это плотность распределения выборки <tex>D</tex>:
 +
:<tex>p(D)=\prod^n_{i=1}p_i(d,w)=\prod_{d \in D}\prod_{w \in d}p(d,w)^{n_{dw}}</tex>
 +
 
 +
Рассмотрим вероятностную тематическую модель <tex>p(D,\Phi,\Theta)</tex>, где
 +
:<tex>\Phi=(\varphi_{wt})_{W \times T}</tex> - искомая матрица терминов тем, <tex>\varphi_{wt} \equiv p(w|t)</tex>
 +
:<tex>\Theta=(\theta_{td})_{T \times D}</tex> - искомая матрица тем документов, <tex>\theta_{td}\equiv p(t|d)</tex>.
 +
 
 +
Запишем задачу максимизации правдоподобия
 +
:<tex>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}</tex>, где
 +
: <tex>C</tex> — нормировочный множитель, зависящий только от чисел <tex>n_{dw}</tex>
 +
С учетом {{eqref|1}} и того факта, что <tex>Cp(d)^{n_{dw}</tex> не зависит от параметров <tex>\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>.
-
== Максимизация правдоподобия ==
 
== Алгоритм ==
== Алгоритм ==

Версия 20:18, 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 прологарифмируем правдоподобие, получив задачу максимизации:

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 .


Алгоритм

Недостатки

Примечания


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