Латентно-семантический анализ

Сюда перенаправляется запрос «Семантический анализ». На эту тему нужна отдельная статья.

Латентно-семантический анализ (ЛСА) — это метод обработки информации на естественном языке, анализирующий взаимосвязь между коллекцией документов и терминами в них встречающимися, сопоставляющий некоторые факторы (тематики) всем документам и терминам.

В основе метода латентно-семантического анализа лежат принципы факторного анализа, в частности, выявление латентных связей изучаемых явлений или объектов. При классификации / кластеризации документов этот метод используется для извлечения контекстно-зависимых значений лексических единиц при помощи статистической обработки больших корпусов текстов^[1].

История

ЛСА был запатентован в 1988 году ^[2] Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum и Lynn Streeter. В области информационного поиска данный подход называют латентно-семантическим индексированием (ЛСИ).

Впервые ЛСА был применен для автоматического индексирования текстов, выявления семантической структуры текста и получения псевдодокументов ^[3]. Затем этот метод был довольно успешно использован для представления баз знаний^[4] и построения когнитивных моделей ^[5].

В последние годы метод ЛСА часто используется для поиска информации (индексация документов), классификации документов ^[6], моделях понимания ^[7] и других областях, где требуется выявление главных факторов из массива информационных данных .

Описание работы ЛСА

ЛСА можно сравнить с простым видом нейросети, состоящей из трех слоев: первый слой содержит множество слов (термов), второй – некое множество документов, соответствующих определенным ситуациям, а третий, средний, скрытый слой представляет собой множество узлов с различными весовыми коэффициентами, связывающих первый и второй слои.

В качестве исходной информации ЛСА использует матрицу термы-на-документы, описывающую набор данных, используемый для обучения системы. Элементы этой матрицы содержат, как правило, веса, учитывающие частоты использования каждого терма в каждом документе и участие терма во всех документах (TF-IDF). Наиболее распространенный вариант ЛСА основан на использовании разложения диагональной матрицы по сингулярным значениям (SVD – Singular Value Decomposition). С помощью SVD-разложения любая матрица раскладывается во множество ортогональных матриц, линейная комбинация которых является достаточно точным приближением к исходной матрице.

Говоря более формально, согласно теореме о сингулярном разложении^[8], любая вещественная прямоугольная матрица может быть разложена на произведение трех матриц:

$\begin{matrix} A=U S V ^T \end{matrix}$ ,

где матрицы $\textbf{U}$ и $\textbf{V}$ – ортогональные, а $\textbf{S}$ – диагональная матрица, значения на диагонали которой называются сингулярными значениями матрицы $\textbf{A}$. Буква Т в выражении $\textbf{V} ^T$ означает транспонирование матрицы.

Такое разложение обладает замечательной особенностью: если в матрице $\textbf{S}$ оставить только $\textbf{k}$ наибольших сингулярных значений, а в матрицах $\textbf{U}$ и $\textbf{V}$ – только соответствующие этим значениям столбцы, то произведение получившихся матриц $\textbf{S}$ , $\textbf{U}$ и $\textbf{V}$ будет наилучшим приближением исходной матрицы $\textbf{A}$ к матрице $\hat\textbf{A}$ ранга $\textbf{k}$:

$\begin{matrix} \hat A \approx A = U S V ^T \end{matrix}$ ,

Основная идея латентно-семантического анализа состоит в том, что если в качестве матрицы $\textbf{A}$ использовалась матрица термы-на-документы, то матрица $\hat\textbf{A}$ , содержащая только $\textbf{k}$ первых линейно независимых компонент $\textbf{A}$, отражает основную структуру различных зависимостей, присутствующих в исходной матрице. Структура зависимостей определяется весовыми функциями термов.

Таким образом, каждый терм и документ представляются при помощи векторов в общем пространстве размерности $\textbf{k}$ (так называемом пространстве гипотез). Близость между любой комбинацией термов и/или документов легко вычисляется при помощи скалярного произведения векторов.

Как правило, выбор $\textbf{k}$ зависит от поставленной задачи и подбирается эмпирически. Если выбранное значение $\textbf{k}$ слишком велико, то метод теряет свою мощность и приближается по характеристикам к стандартным векторным методам. Слишком маленькое значение k не позволяет улавливать различия между похожими термами или документами.

Применение

Существуют три основных разновидности решения задачи методом ЛСА:

• сравнение двух термов между собой;
• сравнение двух документов между собой;
• сравнение терма и документа.

Достоинства и недостатки ЛСА

Достоинства метода:

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

Недостатки:

• Существенным недостатком метода является значительное снижение скорости вычисления при увеличении объема входных данных (например, при SVD-преобразовании). Как показано в ^[9], скорость вычисления соответствует порядку $\textbf {N}^{2*k}$, где $\textbf{N}=\textbf{N}_{doc} + \textbf{N}_{term}$ - сумма количества документов и термов , $\textbf{k}$ – размерность пространства факторов.
• Вероятностная модель метода не соответствует реальности. Предполагается, что слова и документы имеют Нормальное распределение, хотя ближе к реальности Распределение Пуассона. В связи с этим для практических применений лучше подходит Вероятностный латентно-семантический анализ, основанный на мультиномиальном распределении.

См. также

• Семантический анализ — статья в английской Википедии.

Примечания

1. ↑ Thomas Landauer, Peter W. Foltz, & Darrell Laham (1998). «Introduction to Latent Semantic Analysis» (PDF). Discourse Processes 25: 259–284. DOI:10.1080/01638539809545028.
2. ↑ U.S. Patent 4 839 853
3. ↑ Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman (1990). «Indexing by Latent Semantic Analysis» (PDF). Journal of the American Society for Information Science 41 (6): 391–407. DOI:10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9.
4. ↑ Thomas Landauer, Susan T. Dumais A Solution to Plato's Problem: The Latent Semantic Analysis Theory of Acquisition, Induction, and Representation of Knowledge 211–240 (1997). Архивировано из первоисточника 14 марта 2012. Проверено 2 июля 2007.
5. ↑ B. Lemaire, G. Denhière Cognitive Models based on Latent Semantic Analysis (2003).(недоступная ссылка — история)
6. ↑ Некрестьянов И.С. Тематико-ориентированные методы информационного поиска / Диссертация на соискание степени к. ф-м.н. СПбГУ, 2000.
7. ↑ Соловьев А.Н. Моделирование процессов понимания речи с использованием латентно-семантического анализа / Диссертация на соискание степени к.ф.н. СПбГУ, 2008.
8. ↑ Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: «Мир», 1999.
9. ↑ Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman (1990). «Indexing by Latent Semantic Analysis» (PDF). Journal of the American Society for Information Science 41 (6): 391–407. DOI:10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9.

Ссылки

1. http://www-timc.imag.fr/Benoit.Lemaire/lsa.html – Readings in Latent Semantic Analysis for Cognitive Science and Education. – Сборник статей и ссылок о ЛСА.

2. http://lsa.colorado.edu/ – сайт, посвященный моделированию ЛСА.

3. http://www.cs.utk.edu/%7Elsi/ – Latent Semantic Indexing (Латенто-семантическое индексирование).

4. http://lsi.research.telcordia.com/lsi/ – Telcordia Latent Semantic Indexing (LSI). Demo Machine – Демонстрационный сайт латентно-семантического индексирования.

5. http://cran.at.r-project.org/web/packages/lsa/index.html - Open Source LSA Package

6. http://alingva.ru/index.php/lingvosoft/17--lsa - программа для проведения латентно-семантического анализа текстовых данных - OS Windows, GUI, GPL.

Источники