Алговики - Вклад [ru]

Участник:Kruglikov/PLSA

2017-11-02T20:28:48Z

Kruglikov: /* Математическое описание алгоритма */

Общая схема описания алгоритмов имеет следующий вид:

== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Задача тематического моделирования заключается в том, чтобы выделить в коллекции текстовых документов скрытые структуры, называемые ''темами''. Неформально под ''темой'' понимается семантически однородное множество документов. Более формально, темой называется условное распределение на множестве терминов <math>p(w|t)</math>, а ''тематикой документа'' называется условное распределение <math>p(t|d)</math>. Переменная <math>t</math> является скрытой. Таким образом, задача тематического моделирования — оценить вероятности <math>p(w|t)</math> и <math>p(t|d)</math> по наблюдаемым частотам <math>p(w|d)</math> слов в документах.

Задачу восстановления скрытого распределения можно решать, максимизируя правдоподобие выборки ''EM-алгоритмом''. В применении к тематическому моделированию такой подход называется ''probabilistic latent semantic analysis'' — PLSA.

=== Математическое описание алгоритма ===

====Обозначения====
Пусть <math>D</math> — конечное множество документов, <math>W</math> — конечное множество терминов, <math>T</math> — конечное множество тем.

<math>(d_i, w_i, t_i)_{i=1}^n \subset D \times W \times T</math> — коллекция текстовых документов.

Тематическая модель коллекции: <math>p(w|d) = \sum_{t \in T} p(w|t)p(t|d) = \sum_{t \in T} \phi_{wt} \theta_{td}</math>

Задача состоит в том, чтобы найти параметры <math>\phi_{wt}</math> и <math>\theta_{td}</math>

Введём набор счётчиков:

<math>n_{dwt} = \sum_{i=1}^n [d_i = d][w_i = w][t_i = t]</math> — частота <math>(d_i, w_i, t_i)</math> в коллекции;

<math>n_{wt} = \sum_{d} n_{dwt}</math> — частота термина <math>w</math> в теме <math>t</math>;

<math>n_{td} = \sum_{w} n_{dwt}</math> — частота терминов темы <math>t</math> в документе <math>d</math>;

<math>n_{t} = \sum_{d, w} n_{dwt}</math> — частота терминов темы <math>t</math> коллекции;

<math>n_{dw} = \sum_{t} n_{dwt}</math> — частота термина <math>w</math> в документе <math>d</math>;

<math>n_{w} = \sum_{d, t} n_{dwt}</math> — частота термина <math>w</math> в коллекции;

<math>n_{d} = \sum_{w, t} n_{dwt}</math> — длина документа <math>d</math>;

<math>n = \sum_{d, w, t} n_{dwt}</math> — длина коллекции.

====EM-алгоритм в PLSA====
В модели PLSA предлагается максимизировать правдоподобие

<math>\mathcal{L}(\Phi, \Theta) = \sum_{d \in D} \sum_{w \in d} n_{dw} \ln \sum_{t \in T} \phi_{wt} \theta_{dw} \to \max_{\Phi, \Theta}</math>

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

<math>\phi_{wt} \le 0; \sum_{w \in W} \phi_{wt} = 1; \theta_{td} \le 0; \sum_{t \in T} = 1.</math>

Утверждается, что точка максимума правдоподобия удовлетворяет системе уравнений

<math>
\begin{cases}
n_{dwt} & = & n_{dw} \frac{\phi_{wt}\theta_{td}}{\sum_s \phi_{ws} \theta{ws}}; & \text{(E-шаг)} \\
\phi_{wt} & = & \frac{n_{wt}}{n_t}; n_{wt} = \sum_{d \in D} n_{dwt}; n_t = \sum_w n_{wt}; & \text{(M-шаг)} \\
\theta_{td} & = & \frac{n_{td}}{n_d}; n_{td} = \sum_{w \in d} n_{dwt}; n_d = \sum_t n_{wt} .
\end{cases}
</math>

Эту систему можно решить EM-алгоритмом, применяя последовательно E- и M-шаги до сходимости.

== Программная реализация алгоритма ==

== Литература ==
<references />
[http://www.machinelearning.ru/wiki/images/2/20/Voron-PTM-1.pdf Воронцов К. В. Вероятностные тематические модели. Лекция 1. Введение (слайды)]

[[en:Description of algorithm properties and structure]]

Участник:Kruglikov/PLSA

2017-11-02T20:27:03Z

Kruglikov: /* Математическое описание алгоритма */

Общая схема описания алгоритмов имеет следующий вид:

== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Задача тематического моделирования заключается в том, чтобы выделить в коллекции текстовых документов скрытые структуры, называемые ''темами''. Неформально под ''темой'' понимается семантически однородное множество документов. Более формально, темой называется условное распределение на множестве терминов <math>p(w|t)</math>, а ''тематикой документа'' называется условное распределение <math>p(t|d)</math>. Переменная <math>t</math> является скрытой. Таким образом, задача тематического моделирования — оценить вероятности <math>p(w|t)</math> и <math>p(t|d)</math> по наблюдаемым частотам <math>p(w|d)</math> слов в документах.

Задачу восстановления скрытого распределения можно решать, максимизируя правдоподобие выборки ''EM-алгоритмом''. В применении к тематическому моделированию такой подход называется ''probabilistic latent semantic analysis'' — PLSA.

=== Математическое описание алгоритма ===
Пусть <math>D</math> — конечное множество документов, <math>W</math> — конечное множество терминов, <math>T</math> — конечное множество тем. <math>(d_i, w_i, t_i)_{i=1}^n \subset D \times W \times T</math> — коллекция текстовых документов.

Тематическая модель коллекции: <math>p(w|d) = \sum_{t \in T} p(w|t)p(t|d) = \sum_{t \in T} \phi_{wt} \theta_{td}</math>

Задача состоит в том, чтобы найти параметры <math>\phi_{wt}</math> и <math>\theta_{td}</math>

Введём набор счётчиков:

<math>n_{dwt} = \sum_{i=1}^n [d_i = d][w_i = w][t_i = t]</math> — частота <math>(d_i, w_i, t_i)</math> в коллекции;

<math>n_{wt} = \sum_{d} n_{dwt}</math> — частота термина <math>w</math> в теме <math>t</math>;

<math>n_{td} = \sum_{w} n_{dwt}</math> — частота терминов темы <math>t</math> в документе <math>d</math>;

<math>n_{t} = \sum_{d, w} n_{dwt}</math> — частота терминов темы <math>t</math> коллекции;

<math>n_{dw} = \sum_{t} n_{dwt}</math> — частота термина <math>w</math> в документе <math>d</math>;

<math>n_{w} = \sum_{d, t} n_{dwt}</math> — частота термина <math>w</math> в коллекции;

<math>n_{d} = \sum_{w, t} n_{dwt}</math> — длина документа <math>d</math>;

<math>n = \sum_{d, w, t} n_{dwt}</math> — длина коллекции.

В модели PLSA предлагается максимизировать правдоподобие

<math>\mathcal{L}(\Phi, \Theta) = \sum_{d \in D} \sum_{w \in d} n_{dw} \ln \sum_{t \in T} \phi_{wt} \theta_{dw} \to \max_{\Phi, \Theta}</math>

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

<math>\phi_{wt} \le 0; \sum_{w \in W} \phi_{wt} = 1; \theta_{td} \le 0; \sum_{t \in T} = 1.</math>

Утверждается, что точка максимума правдоподобия удовлетворяет системе уравнений

<math>
\begin{cases}
n_{dwt} & = & n_{dw} \frac{\phi_{wt}\theta_{td}}{\sum_s \phi_{ws} \theta{ws}}; & \text{(E-шаг)} \\
\phi_{wt} & = & \frac{n_{wt}}{n_t}; n_{wt} = \sum_{d \in D} n_{dwt}; n_t = \sum_w n_{wt}; & \text{(M-шаг)} \\
\theta_{td} & = & \frac{n_{td}}{n_d}; n_{td} = \sum_{w \in d} n_{dwt}; n_d = \sum_t n_{wt} .
\end{cases}
</math>

Эту систему можно решить EM-алгоритмом, применяя последовательно E- и M-шаги.

== Программная реализация алгоритма ==

== Литература ==
<references />
[http://www.machinelearning.ru/wiki/images/2/20/Voron-PTM-1.pdf Воронцов К. В. Вероятностные тематические модели. Лекция 1. Введение (слайды)]

[[en:Description of algorithm properties and structure]]

Участник:Kruglikov/PLSA

2017-11-02T20:26:29Z

Kruglikov: /* Математическое описание алгоритма */

Общая схема описания алгоритмов имеет следующий вид:

== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Задача тематического моделирования заключается в том, чтобы выделить в коллекции текстовых документов скрытые структуры, называемые ''темами''. Неформально под ''темой'' понимается семантически однородное множество документов. Более формально, темой называется условное распределение на множестве терминов <math>p(w|t)</math>, а ''тематикой документа'' называется условное распределение <math>p(t|d)</math>. Переменная <math>t</math> является скрытой. Таким образом, задача тематического моделирования — оценить вероятности <math>p(w|t)</math> и <math>p(t|d)</math> по наблюдаемым частотам <math>p(w|d)</math> слов в документах.

Задачу восстановления скрытого распределения можно решать, максимизируя правдоподобие выборки ''EM-алгоритмом''. В применении к тематическому моделированию такой подход называется ''probabilistic latent semantic analysis'' — PLSA.

=== Математическое описание алгоритма ===
Пусть <math>D</math> — конечное множество документов, <math>W</math> — конечное множество терминов, <math>T</math> — конечное множество тем. <math>(d_i, w_i, t_i)_{i=1}^n \subset D \times W \times T</math> — коллекция текстовых документов.

Тематическая модель коллекции: <math>p(w|d) = \sum_{t \in T} p(w|t)p(t|d) = \sum_{t \in T} \phi_{wt} \theta_{td}</math>

Задача состоит в том, чтобы найти параметры <math>\phi_{wt}</math>и <math>\theta_{td}</math>

Введём набор счётчиков:

<math>n_{dwt} = \sum_{i=1}^n [d_i = d][w_i = w][t_i = t]</math> — частота <math>(d_i, w_i, t_i)</math> в коллекции;

<math>n_{wt} = \sum_{d} n_{dwt}</math> — частота термина <math>w</math> в теме <math>t</math>;

<math>n_{td} = \sum_{w} n_{dwt}</math> — частота терминов темы <math>t</math> в документе <math>d</math>;

<math>n_{t} = \sum_{d, w} n_{dwt}</math> — частота терминов темы <math>t</math> коллекции;

<math>n_{dw} = \sum_{t} n_{dwt}</math> — частота термина <math>w</math> в документе <math>d</math>;

<math>n_{w} = \sum_{d, t} n_{dwt}</math> — частота термина <math>w</math> в коллекции;

<math>n_{d} = \sum_{w, t} n_{dwt}</math> — длина документа <math>d</math>;

<math>n = \sum_{d, w, t} n_{dwt}</math> — длина коллекции.

В модели PLSA предлагается максимизировать правдоподобие

<math>\mathcal{L}(\Phi, \Theta) = \sum_{d \in D} \sum_{w \in d} n_{dw} \ln \sum_{t \in T} \phi_{wt} \theta_{dw} \to \max_{\Phi, \Theta}</math>

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

<math>\phi_{wt} \le 0; \sum_{w \in W} \phi_{wt} = 1; \theta_{td} \le 0; \sum_{t \in T} = 1.</math>

Утверждается, что точка максимума правдоподобия удовлетворяет системе уравнений

<math>
\begin{cases}
n_{dwt} & = & n_{dw} \frac{\phi_{wt}\theta_{td}}{\sum_s \phi_{ws} \theta{ws}}; & \text{(E-шаг)} \\
\phi_{wt} & = & \frac{n_{wt}}{n_t}; n_{wt} = \sum_{d \in D} n_{dwt}; n_t = \sum_w n_{wt}; & \text{(M-шаг)} \\
\theta_{td} & = & \frac{n_{td}}{n_d}; n_{td} = \sum_{w \in d} n_{dwt}; n_d = \sum_t n_{wt} .
\end{cases}
</math>

Эту систему можно решить EM-алгоритмом, применяя последовательно E- и M-шаги.

== Программная реализация алгоритма ==

== Литература ==
<references />
[http://www.machinelearning.ru/wiki/images/2/20/Voron-PTM-1.pdf Воронцов К. В. Вероятностные тематические модели. Лекция 1. Введение (слайды)]

[[en:Description of algorithm properties and structure]]

Участник:Kruglikov/PLSA

2017-10-31T21:14:58Z

Kruglikov: /* Математическое описание алгоритма */

Общая схема описания алгоритмов имеет следующий вид:

== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Задача тематического моделирования заключается в том, чтобы выделить в коллекции текстовых документов скрытые структуры, называемые ''темами''. Неформально под ''темой'' понимается семантически однородное множество документов. Более формально, темой называется условное распределение на множестве терминов <math>p(w|t)</math>, а ''тематикой документа'' называется условное распределение <math>p(t|d)</math>. Переменная <math>t</math> является скрытой. Таким образом, задача тематического моделирования — оценить вероятности <math>p(w|t)</math> и <math>p(t|d)</math> по наблюдаемым частотам <math>p(w|d)</math> слов в документах.

Задачу восстановления скрытого распределения можно решать, максимизируя правдоподобие выборки ''EM-алгоритмом''. В применении к тематическому моделированию такой подход называется ''probabilistic latent semantic analysis'' — PLSA.

=== Математическое описание алгоритма ===
Пусть <math>D</math> — конечное множество документов, <math>W</math> — конечное множество терминов, <math>T</math> — конечное множество тем. <math>(d_i, w_i, t_i)_{i=1}^n \subset D \times W \times T</math> — коллекция текстовых документов.

Тематическая модель коллекции: <math>p(w|d) = \sum_{t \in T} p(w|t)p(t|d) = \sum_{t \in T} \phi_{wt} \theta_{td}</math>

Задача состоит в том, чтобы найти параметры <math>\phi_{wt}</math>и <math>\theta_{td}</math>

Введём набор счётчиков:

<math>n_{dwt} = \sum_{i=1}^n [d_i = d][w_i = w][t_i = t]</math> — частота <math>(d_i, w_i, t_i)</math> в коллекции;

<math>n_{wt} = \sum_{d} n_{dwt}</math> — частота термина <math>w</math> в теме <math>t</math>;

<math>n_{td} = \sum_{w} n_{dwt}</math> — частота терминов темы <math>t</math> в документе <math>d</math>;

<math>n_{t} = \sum_{d, w} n_{dwt}</math> — частота терминов темы <math>t</math> коллекции;

<math>n_{dw} = \sum_{t} n_{dwt}</math> — частота термина <math>w</math> в документе <math>d</math>;

<math>n_{w} = \sum_{d, t} n_{dwt}</math> — частота термина <math>w</math> в коллекции;

<math>n_{d} = \sum_{w, t} n_{dwt}</math> — длина документа <math>d</math>;

<math>n = \sum_{d, w, t} n_{dwt}</math> — длина коллекции.

== Программная реализация алгоритма ==

== Литература ==
<references />
[http://www.machinelearning.ru/wiki/images/2/20/Voron-PTM-1.pdf Воронцов К. В. Вероятностные тематические модели. Лекция 1. Введение (слайды)]

[[en:Description of algorithm properties and structure]]

Участник:Kruglikov/PLSA

2017-10-28T20:29:59Z

Kruglikov: /* Литература */

Общая схема описания алгоритмов имеет следующий вид:

== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
Задача тематического моделирования заключается в том, чтобы выделить в коллекции текстовых документов скрытые структуры, называемые ''темами''. Неформально под ''темой'' понимается семантически однородное множество документов. Более формально, темой называется условное распределение на множестве терминов <math>p(w|t)</math>, а ''тематикой документа'' называется условное распределение <math>p(t|d)</math>. Переменная <math>t</math> является скрытой. Таким образом, задача тематического моделирования — оценить вероятности <math>p(w|t)</math> и <math>p(t|d)</math> по наблюдаемым частотам <math>p(w|d)</math> слов в документах.

Задачу восстановления скрытого распределения можно решать, максимизируя правдоподобие выборки ''EM-алгоритмом''. В применении к тематическому моделированию такой подход называется ''probabilistic latent semantic analysis'' — PLSA.

=== Математическое описание алгоритма ===
Пусть <math>D</math> — конечное множество документов, <math>W</math> — конечное множество терминов, <math>T</math> — конечное множество тем. <math>(d_i, w_i, t_i)_{i=1}^n \subset D \times W \times T</math> — коллекция текстовых документов.

Введём набор счётчиков:

<math>n_{dwt} = \sum_{i=1}^n [d_i = d][w_i = w][t_i = t]</math> — частота <math>(d_i, w_i, t_i)</math> в коллекции;

<math>n_{wt} = \sum_{d} n_{dwt}</math> — частота термина <math>w</math> в теме <math>t</math>;

<math>n_{td} = \sum_{w} n_{dwt}</math> — частота терминов темы <math>t</math> в документе <math>d</math>;

<math>n_{t} = \sum_{d, w} n_{dwt}</math> — частота терминов темы <math>t</math> коллекции;

<math>n_{dw} = \sum_{t} n_{dwt}</math> — частота термина <math>w</math> в документе <math>d</math>;

<math>n_{w} = \sum_{d, t} n_{dwt}</math> — частота термина <math>w</math> в коллекции;

<math>n_{d} = \sum_{w, t} n_{dwt}</math> — длина документа <math>d</math>;

<math>n = \sum_{d, w, t} n_{dwt}</math> — длина коллекции.

== Программная реализация алгоритма ==

== Литература ==
<references />
[http://www.machinelearning.ru/wiki/images/2/20/Voron-PTM-1.pdf Воронцов К. В. Вероятностные тематические модели. Лекция 1. Введение (слайды)]

[[en:Description of algorithm properties and structure]]

Участник:Kruglikov/PLSA

2017-10-28T20:27:35Z

Kruglikov: /* Математическое описание алгоритма */

Участник:Kruglikov/PLSA

2017-10-28T20:05:57Z

Kruglikov: /* Свойства и структура алгоритмов */

Участник:Kruglikov/PLSA

2017-10-28T19:42:24Z

Kruglikov: Структура

Общая схема описания алгоритмов имеет следующий вид:

== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===

=== Математическое описание алгоритма ===

== Программная реализация алгоритма ==

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]