Участник:MelLain/ЕМ-алгоритм (Тематическое моделирование): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === '''Тематическое модели…»)
 
Строка 9: Строка 9:
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
  
В большинстве тематических моделей коллекция текстов рассматривается в виде "мешка слов", т.е. модель учитывает только статистическую встречаемость слов в документах и никак не использует информацию об их взаимном расположении внутри документа. Вероятностная модель PLSA имеет следующий вид:
+
В большинстве тематических моделей коллекция текстов рассматривается в виде "мешка слов", т.е. модель учитывает только статистическую встречаемость слов в документах и никак не использует информацию об их взаимном расположении внутри документа.  
 +
 
 +
Вероятностная модель PLSA имеет следующий вид:
  
 
:<math>
 
:<math>
Строка 19: Строка 21:
 
Здесь <math>F</math> - это матрица исходных данных размера <math>|W| \times |D|</math>, где <math>D</math> - это множество документов, а <math>W</math> - словарь коллекции, т.е. множество всех уникальных слов, встретившихся в документах.  
 
Здесь <math>F</math> - это матрица исходных данных размера <math>|W| \times |D|</math>, где <math>D</math> - это множество документов, а <math>W</math> - словарь коллекции, т.е. множество всех уникальных слов, встретившихся в документах.  
  
<math>\Phi</math> - это матрица параметров модели
+
<math>\Phi</math> - это матрица параметров модели размера <math>|W| \times |T|</math>, где  <math>T</math> - это множество тем, которые мы хотим извлечь из коллекции. Под темой в бытовом смысле смысле понимается набор слов, характеризующих её. Формально говоря, тема - это вероятностное распределение на множестве слов <math>W</math>, поэтому матрица <math>\Phi</math> является стохастической, т.е. столбцы её неотрицательны и суммируются в единицу.
 +
 
 +
<math>\Theta</math> - матрица результатов кластеризации обучающей коллекции по полученным темам размера <math>|T| \times |D|</math>, в ней столбцы также являются вероятностными распределениями, на этот раз документов на множестве тем.
 +
 
 +
Фактически, PLSA есть ни что иное, как задача приближённого стохастического матричного разложения, в ходе которой производится мягкая бикластеризация (мягкая - потому что объекты распределяются по классам не строго, а с некоторой вероятностью, би - потому что производится одновременная кластрезация слов по темам, и тем - по документам).
  
Фактически, PLSA есть ни что иное, как задача приближённого стохастического матричного разложения. В данной статье будут расматриваться только плотные матрицы (хотя при определённых условиях можно эффективно использовать разреженные).
+
В данной статье будут расматриваться только плотные матрицы (хотя при определённых условиях можно эффективно использовать разреженные).
  
 
== Литература ==
 
== Литература ==

Версия 22:54, 22 сентября 2016

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

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

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

Существует множество разновидностей ЕМ-алгоритмов, ориентированных на учёт тех или иные аспектов решаемой задачи. Наиболее простым вариантом является т.н. оффлайновый алгоритм, непригодный для работы с большими текстовыми данными в силу значительных требований к потребляемой оперативной памяти. Существует ряд модернизаций этого алгоритма, позволяющих избавить его от ряда недостатков. Наилучшей из них является онлайновый вариант алгоритма. Тем не менее, в силу относительно высокой сложности его эффективной параллельной реализации, в данной статье будет рассматриваться гибридный вариант алгоритма, избавленный от большинства недостатков оффлайнового, но имеющий меньшую скорость сходимости, чем онлайновый.

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

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

Вероятностная модель PLSA имеет следующий вид:

[math] \begin{align} F \approx \Phi \times \Theta \end{align} [/math]

Здесь [math]F[/math] - это матрица исходных данных размера [math]|W| \times |D|[/math], где [math]D[/math] - это множество документов, а [math]W[/math] - словарь коллекции, т.е. множество всех уникальных слов, встретившихся в документах.

[math]\Phi[/math] - это матрица параметров модели размера [math]|W| \times |T|[/math], где [math]T[/math] - это множество тем, которые мы хотим извлечь из коллекции. Под темой в бытовом смысле смысле понимается набор слов, характеризующих её. Формально говоря, тема - это вероятностное распределение на множестве слов [math]W[/math], поэтому матрица [math]\Phi[/math] является стохастической, т.е. столбцы её неотрицательны и суммируются в единицу.

[math]\Theta[/math] - матрица результатов кластеризации обучающей коллекции по полученным темам размера [math]|T| \times |D|[/math], в ней столбцы также являются вероятностными распределениями, на этот раз документов на множестве тем.

Фактически, PLSA есть ни что иное, как задача приближённого стохастического матричного разложения, в ходе которой производится мягкая бикластеризация (мягкая - потому что объекты распределяются по классам не строго, а с некоторой вероятностью, би - потому что производится одновременная кластрезация слов по темам, и тем - по документам).

В данной статье будут расматриваться только плотные матрицы (хотя при определённых условиях можно эффективно использовать разреженные).

2 Литература