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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



Латентно-семантический анализ (LSA от англ. Latent Semantic Analysis) - это теория и метод для извлечения контекстно-зависимых значений слов при помощи статистической обработки больших наборов текстовых данных. В течении нескольких последних лет этот метод не раз использовался как в области поиска информации, так и в задачах фильтрации и классификации.

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

Представления слова и абзаца с помощью метода LSA во многом моделируют восприятие текста человеком [Deerwester, S., Dumais, S.T., Furnas, G.W., Landauer, T.K. and Harshman, R.A. 1990. Indexing by Latent Semantic Analysis. Journal of the American Society for Information Science, 41: 391-407.]. Например, с его помощью можно оценить эссе на соответствие теме или сопоставить смыслы отрывков текста.

Впервые метод LSA был описан в работе [Landauer, T. K., Foltz, P., and Laham, D. 1998. An Introduction to Latent Semantic Analysis. DiscourseProcesses, 25: 259-284.] в настоящее время лидером в области применения LSA является компания Pearson Knowledge Technologies ([Веб-сайт Pearson Knowledge Technologies – http://www.k-a-t.com ]). Её коммерческие продукты позволяют убедиться в хорошей эффективности метода LSA. Однако конкретные алгоритмы реализации этого метода не опубликованы, поскольку представляют собой коммерческую тайну.

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

Следует отметить, что у метода LSA существуют некоторые ограничения. В нем не используется информация о порядке слов, и, следовательно, метод не учитывает синтаксические отношения, логику или морфологию. Несмотря на это, результаты метода достаточно достоверно отображают смысловые корреляции между словами и отрывками.

Существуют два основных отличия метода LSA от прочих статистических методов обработки текстов:

· в качестве исходных данных LSA использует частоту использования слов в отрывках текста, а не частоту совместного использования слов;

· метод собирает данные не о попарной совместной используемости слов, а об используемости множества слов в большом массиве отрывков.

Таким образом, метод рассматривает влияние выбора, а не порядка слов на смысл отрывка. Можно сказать, что LSA представляет значение слова как среднее значений отрывков, в которых оно встречается, а значение отрывка - как среднее значений всех слов, составляющих отрывок.

Опишем математическую модель LSA. В качестве исходной информации LSA использует матрицу термы-на-документы, описывающую используемый для обучения системы набор данных. Массиву документов D={di, i=1,...,n} ставится в соответствие матрица A размером mxn, строки которой соответствуют документам, а столбцы – весовым значениям термов (размер словаря термов - m). В качестве весовых значений используют частоты встречаемости данного терма в данном документе. Такой подход стандартен для всех семантических моделей.

После получения матрицы употребляемости требуется понизить ее ранг (т.е аппроксимировать ее матрицей с меньшем рангом). Это необходимо делать по нескольким причинам:

· из-за высокого ранга исходной матрицы вычисления с ней часто невозможны;

· исходная матрица содержит «шумы» - например «случайное» попадание в отрывок слова, несоответствующего смыслу отрывка. Понижение ранга позволяет снизить значимость таких случаев – то есть отчасти избавиться от «шумов»;

· предполагается, что исходная матрица слишком «разрежена» - она учитывает только слова, появляющиеся в отрывке - но не слова, связанные с отрывком (через синонимию).

Операция уменьшает влияние синонимии, так как понижение ранга «сливает» размерности, связанные со словами, имеющими близкие значения. Также уменьшается влияние полисемии: в случае, если многозначное слово имеет «правильное значение», то его элемент «сливается» с матричными элементами слов с таким же значением. Если же слово употреблено в «неправильном» значении, то соответствующий элемент будет уменьшен или отброшен.

Наиболее распространенный вариант понижения ранга основан на использовании разложения метода линейной алгебры - сингулярного разложения матрицы [Тыртышников Е.Е. Курс линейной алгебры. − М., 2004 ].

Сингулярным разложением матрицы A ранга r размерности mxn называется ее разложение вида A = USVT, где U и V ортогональные матрицы размерности mxr и rxn соответственно, а S - диагональная матрица, диагональные элементы которой неотрицательны. Диагональные элементы матрицы S называют сингулярными значениями матрицы A. Заметим, что матрица S, в отличие от матрицы, квадратная.

Приведенное выше разбиение матрицы A обладает тем свойством, что если в матрице S оставить только k наибольших сингулярных значений (обозначим такую матрицу как Sk), а в матрицах U и V только соответствующие этим значениям колонки (соответственно, матрицы UkVk), то матрица Ak=UkSkVkT будет наилучшей по Фробениусу аппроксимацией исходной матрицы A матрицей с рангом, не превышающим k.

Akопределяет k-мерное факторное пространство, на которое проецируются как документы (с помощью матрицы V), так и термины (с помощью матрицы U). В полученном факторном пространстве документы и термины группируются в массивы (кластеры), имеющие некоторый общий смысл, не заданный в явном виде, т.е. латентный. В этом и состоит основная идея LSA.

Таким образом, огромная исходная матрица разлагается во множество из k, обычно от 70 до 200, ортогональных матриц, линейная комбинация которых является неплохим приближением исходной матрицы. Полученная матрица, содержащая только k первых линейно независимых компонент, отражает основную структуру ассоциативных зависимостей, присутствующих в исходной матрице, и в то же время не содержит шума. Т.е. существует такой линейно независимый набор документов Db= {di1, …, dik}, что все остальные вектора документов выражаются как линейная комбинация векторов этого набора. Тогда можно взять множество Dbв качестве базиса; в таком базисе у каждого документа будет уже k координат. Таким образом каждый терм и документ представляются при помощи векторов в общем пространстве размерности k (так называемом пространстве гипотез). Близость между любой комбинацией термов и/или документов может быть легко вычислена при помощи скалярного произведения векторов.

Если ранг матрицы документов больше чем k, такого базиса найти нельзя. Но сингулярное разложение позволяет найти его приближённо. Для этого надо найти искомый базис Dbдля приближённой матрицы Ak. Каждый вектор документа, не лежащий в линейной оболочке множества Db, можно заменить на его проекцию. Точность такого приближения будет зависеть от выбора k.

Выбор наилучшей размерности k для LSA - открытая исследовательская проблема. В идеале, k должно быть достаточно велико для отображения всей реально существующей структуры данных, но в то же время достаточно мало чтобы не захватить случайные и маловажные зависимости. Если выбранное k слишком велико, то метод теряет свою мощь и приближается по характеристикам к стандартным векторным методам. Слишком маленькое k не позволяет улавливать различия между похожими словами или документами. Исследования показывают, что с ростом k качество сначала возрастает, а потом начинает падать.

В практике информационного поиска особое значение отводится матрицам Ukи VkT Как указывалось ранее, строки матрицы Ukрассматриваются как образы термов в k-мерном вещественном пространстве. Аналогично, столбцы матрицы VkT рассматриваются как образы документов в том же k-мерном пространстве. Иными словами, эти векторы задают искомое представление термов и документов в k-мерном пространстве скрытых факторов.

Существуют также методы инкрементного обновления всех значений, используемых в LSA. При пополнении новым документом d коллекции, для которой уже проведено сингулярное разложение, можно не выполнять разложение заново. Достаточно аппроксимировать его, вычисляя образ нового документа на основе ранее вычисленных образов термов и весов факторов. Пусть d вектор весов термов нового документа (новый столбец матрицы A), тогда его образ можно вычислить по формуле:

 

 

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

Метод LSA не нуждается в предварительной настройке на специфический набор документов, вместе с тем позволяет качественно выявлять скрытые факторы. К недостаткам метода можно отнести невысокую производительность (вычислительная сложность соответствует порядку O(m+n)2k), поэтому LSA применяется только для относительно небольших матриц, кроме того, LSA не предусматривает возможность пересечения кластеров, что противоречит практике.

LSA активно используется для формирования групп близких по значению слов на основе статистического анализа их сочетаемости с элементами контекста, однако отношение содержательной соотнесенности понимается при этом очень широко, и сейчас еще рано говорить об LSA как о точном инструменте семантического исследования.

Модификацией матричного LSA является метод вероятностного латентного семантического анализа (PLSA). PLSA построен на использовании вероятностного подхода и также предназначен для выявления скрытых факторов, присутствующих в информационном массиве и связанных с ними документов и слов.

Пусть D — коллекция документов, Т — множество термов, Z — множество скрытых факторов. Как и в предыдущем случае, предполагается, что существует k скрытых факторов z1,...,zk(число k задается заранее). Фактору ziсопоставляется вероятность P(zi) того, что случайно выбранный из данной коллекции документ наиболее точно характеризуется данным фактором ().

Обозначим через P(d|zi) вероятность того, что для выбранного фактора ziиз множества факторов Z, именно документ d из всего множества документов D лучше всего характеризуется этим фактором. Тогда А налогично обозначим через P(t|zi)вероятность того, что для выбранного фактора zi, из всех термов именно терм t из словаря системы T лучше всего характеризуется этим фактором zi. Тогда

Вероятность того, что при случайном выборе документа d и терма t, терм t встретится в документе d, можно определить с одной стороны как:

P(d,t)=p(d)P(t|d),

 

С другой стороны как:

 

 

Зафиксировав число скрытых факторов k, с помощью метода PLSA можно оценить следующие величины:

P(zi) - вероятность того, что случайно выбранный из коллекции документ в соответствует фактору zi;

P(dj|zi) - вероятность того, что документ djпопадет в группу документов, соответствующих фактору zi;

P(tj|zi) - вероятность того, что терм tj попадет в группу слов, связанных с фактором zi.

 

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

Упомянутые выше вероятности определяются исходя из условия максимизации функции максимального правдоподобия:

 

 

где внешняя сумма берется по всем документам, а внутренняя по всем термам словаря.

 

В PLSA используется алгоритм EM (Expectation Maximization – оценочной максимизации), в котором на каждой итерации выполняются два шага:

1) оценивание, при котором вычисляются и оцениваются послеопытные вероятности латентных переменных;

2) максимизация, в результате которой параметры изменяются.

 

На первом шаге оценивается:

 

 

После чего выполняется шаг максимизации L на основе вычисления:

 

,

,

 

Данный алгоритм обеспечивает сходимость функции L к некоторому локальному максимуму. Эксперименты показывают, что сходимость достигается после нескольких десятков итераций.

Покажем, как представить PLSA в виде матричной записи. Определим матрицы:

1) , элементами которой будут условные вероятности P(d(i)|zk),

2) , элементами которой будут условные вероятности P(tj|zk),

3) - диагональную матрицу ранга k, на диагонали которой будут размещены значения вероятностей P(zi).

Объединенная вероятностная модель P(z) аппроксимируется выражением . Сравнивая это разложение с сингулярным разложением матриц, можно заметить, что и в PLSA также независимы ввиду предположения независимости термов и документов. Хотя приведенное разложение не является сингулярным, вместе с тем, k наибольших компонент определяют правила кластеризации PLSA. Основное отличие PLSA от LSA заключается в выборе целевой функции L.

Баейсовской версией PLSA модели является модель, основанная на скрытом распределении Дирихле.



Поделиться:


Последнее изменение этой страницы: 2017-02-07; просмотров: 378; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.201.24.171 (0.052 с.)