Латентно-семантический анализ
Латентно-семанти́ческий ана́лиз (ЛСА) — это метод обработки информации на естественном языке, анализирующий взаимосвязь между коллекцией документов и терминами в них встречающимися, сопоставляющий некоторые факторы (тематики) всем документам и терминам.
В основе метода латентно-семантического анализа лежат принципы факторного анализа, в частности выявление латентных связей изучаемых явлений или объектов. При классификации/кластеризации документов этот метод используется для извлечения контекстно-зависимых значений лексических единиц при помощи статистической обработки больших корпусов текстов[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], любая вещественная прямоугольная матрица может быть разложена на произведение трех матриц:
<math> \begin{matrix} A=U S V ^T \end{matrix} </math> ,
где матрицы <math>\textbf{U}</math> и <math>\textbf{V}</math> – ортогональные, а <math>\textbf{S}</math> – диагональная матрица, значения на диагонали которой называются сингулярными значениями матрицы <math>\textbf{A}</math>. Буква Т в выражении <math>\textbf{V} ^T</math> означает транспонирование матрицы.
Такое разложение обладает замечательной особенностью: если в матрице <math>\textbf{S}</math> оставить только <math>\textbf{k}</math> наибольших сингулярных значений, а в матрицах <math>\textbf{U}</math> и <math>\textbf{V}</math> – только соответствующие этим значениям столбцы, то произведение получившихся матриц <math>\textbf{S}</math> , <math>\textbf{U}</math> и <math>\textbf{V}</math> будет наилучшим приближением исходной матрицы <math>\textbf{A}</math> к матрице <math>\hat\textbf{A}</math> ранга <math>\textbf{k}</math>:
<math> \begin{matrix} \hat A \approx A = U S V ^T \end{matrix} </math> ,
Основная идея латентно-семантического анализа состоит в том, что если в качестве матрицы <math>\textbf{A}</math> использовалась матрица термы-на-документы, то матрица <math>\hat\textbf{A}</math> , содержащая только <math>\textbf{k}</math> первых линейно независимых компонент <math>\textbf{A}</math>, отражает основную структуру различных зависимостей, присутствующих в исходной матрице. Структура зависимостей определяется весовыми функциями термов.
Таким образом, каждый терм и документ представляются при помощи векторов в общем пространстве размерности <math>\textbf{k}</math> (так называемом пространстве гипотез). Близость между любой комбинацией термов и/или документов легко вычисляется при помощи скалярного произведения векторов.
Как правило, выбор <math>\textbf{k}</math> зависит от поставленной задачи и подбирается эмпирически. Если выбранное значение <math>\textbf{k}</math> слишком велико, то метод теряет свою мощность и приближается по характеристикам к стандартным векторным методам. Слишком маленькое значение <math>\textbf{k}</math> не позволяет улавливать различия между похожими термами или документами.
Применение
Существуют три основных разновидности решения задачи методом ЛСА:
- сравнение двух термов между собой;
- сравнение двух документов между собой;
- сравнение терма и документа.
Достоинства и недостатки ЛСА
Достоинства метода:
- метод является наилучшим для выявления латентных зависимостей внутри множества документов;
- метод может быть применен как с обучением, так и без обучения (например, для кластеризации);
- используются значения матрицы близости, основанной на частотных характеристиках документов и лексических единиц;
- частично снимается полисемия и омонимия.
Недостатки:
- Существенным недостатком метода является значительное снижение скорости вычисления при увеличении объема входных данных (например, при SVD-преобразовании). Как показано в [9], скорость вычисления соответствует порядку <math>\textbf {N}^{2*k}</math>, где <math> \textbf{N}=\textbf{N}_{doc} + \textbf{N}_{term}</math> - сумма количества документов и термов , <math>\textbf{k}</math> – размерность пространства факторов.
- Вероятностная модель метода не соответствует реальности. Предполагается, что слова и документы имеют Нормальное распределение, хотя ближе к реальности Распределение Пуассона. В связи с этим для практических применений лучше подходит Вероятностный латентно-семантический анализ, основанный на мультиномиальном распределении.
Примечания
- ↑ Thomas Landauer, Peter W. Foltz, & Darrell Laham (1998). «[lsa.colorado.edu/papers/dp1.LSAintro.pdf Introduction to Latent Semantic Analysis]» (PDF). Discourse Processes 25: 259–284. DOI:10.1080/01638539809545028.
- ↑ [www.google.com/patents/US4,839,853 U.S. Patent 4 839 853]
- ↑ Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman (1990). «[lsi.research.telcordia.com/lsi/papers/JASIS90.pdf 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.
- ↑ Thomas Landauer, Susan T. Dumais. [www.welchco.com/02/14/01/60/96/02/2901.HTM A Solution to Plato's Problem: The Latent Semantic Analysis Theory of Acquisition, Induction, and Representation of Knowledge] 211–240 (1997). Проверено 2 июля 2007. [www.webcitation.org/669WP3Drm Архивировано из первоисточника 14 марта 2012].
- ↑ B. Lemaire, G. Denhière. [membres-timc.imag.fr/Benoit.Lemaire/activites/tutorialLSA.pdf Cognitive Models based on Latent Semantic Analysis](недоступная ссылка — история) (2003).
- ↑ Некрестьянов И.С. Тематико-ориентированные методы информационного поиска / Диссертация на соискание степени к. ф-м.н. СПбГУ, 2000.
- ↑ Соловьев А.Н. Моделирование процессов понимания речи с использованием латентно-семантического анализа / Диссертация на соискание степени к.ф.н. СПбГУ, 2008.
- ↑ Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: «Мир», 1999.
- ↑ Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman (1990). «[lsi.research.telcordia.com/lsi/papers/JASIS90.pdf 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.
Ссылки
- www-timc.imag.fr/Benoit.Lemaire/lsa.html – Readings in Latent Semantic Analysis for Cognitive Science and Education. – Сборник статей и ссылок о ЛСА.
- lsa.colorado.edu/ – сайт, посвященный моделированию ЛСА.
- lingurus.net/soft.html - Латентно-семантический анализ: программы для создания моделей и визуализации результатов ЛСА.