О сервисе WebGround

Ваша тема


Новости сайта

Литература

обложка книгиИнтернетика. Навигация в сложных сетях: модели и алгоритмы
Большакова Е.И., Клышинский Э.С., Ландэ Д.В., Носков А.А., Пескова О.В., Ягунова Е.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистикаАвтоматическая обработка текстов на естественном языке и компьютерная лингвистика (pdf)
Ягунова Е.В., Макарова О.Е., Антонова А.Ю., Соловьев А.Н. Разные методы компрессии в исследовании понимания новостного текстаРазные методы компрессии в исследовании понимания новостного текста (pdf)
Крылова И.В, Пивоварова Л.М., Савина А.В., Ягунова Е.В. Исследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистовИсследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистов (pdf)
Ягунова Е.В. Исследование перцептивной устойчивости фонем как элементов речевой цепиИсследование перцептивной устойчивости фонем как элементов речевой цепи (pdf)
Ягунова Е.В. Вариативность структуры нарратива и разнообразие стратегий пониманияВариативность структуры нарратива и разнообразие стратегий понимания (pdf)
Ягунова Е.В., Пивоварова Л.М. Экспериментально-вычислительные исследования художественной прозы Н.В. ГоголяЭкспериментально-вычислительные исследования художественной прозы Н.В. Гоголя (pdf)
Ягунова Е.В. Вариативность стратегий восприятия звучащего текстаВариативность стратегий восприятия звучащего текста (pdf)
Ягунова Е.В. Спонтанный нарратив у детей и у взрослыхСпонтанный нарратив у детей и у взрослых (pdf)
Ягунова Е.В. Исследование избыточности русского звучащего текстаИсследование избыточности русского звучащего текста (pdf)
Ягунова Е.В. Фонетические признаки опорных сегментов и восприятие русского текстаФонетические признаки опорных сегментов и восприятие русского текста (pdf)
Ягунова Е.В. Коммуникативная и смысловая структура текста и его восприятиеКоммуникативная и смысловая структура текста и его восприятие (pdf)
Ягунова Е.В. Где скрывается смысл бессмысленного текста?Где скрывается смысл бессмысленного текста? (pdf)
Ягунова Е.В. Эксперимент в психолингвистике: Конспекты лекций и методические рекомендацииЭксперимент в психолингвистике: Конспекты лекций и методические рекомендации (pdf)
Ягунова Е.В. Теория речевой коммуникацииТеория речевой коммуникации (pdf)
Антонова А.Ю., Клышинский Э.С., Ягунова Е.В. Определение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемостиОпределение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемости (pdf)
Ягунова Е.В. Эксперимент и вычисления в анализе ключевых слов художественного текстаЭксперимент и вычисления в анализе ключевых слов художественного текста (pdf)
Ягунова Е.В. Ключевые слова в исследовании текстов Н.В. ГоголяКлючевые слова в исследовании текстов Н.В. Гоголя (pdf)
Пивоварова Л.М., Ягунова Е.В. Информационная структура научного текста. Текст в контексте коллекцииИнформационная структура научного текста. Текст в контексте коллекции (pdf)
Савина А.Н., Ягунова Е.В. Исследование коллокаций с помощью экспериментов с информантамиИсследование коллокаций с помощью экспериментов с информантами (pdf)
Ягунова Е.В., Пивоварова Л.М. От коллокаций к конструкциямОт коллокаций к конструкциям (pdf)
Пивоварова Л.М., Ягунова Е.В. Извлечение и классификация терминологических коллокаций на материале лингвистических научных текстовИзвлечение и классификация терминологических коллокаций на материале лингвистических научных текстов (pdf)
Julia Kiseleva. Grouping Web Users based on Query LogGrouping Web Users based on Query Log (pdf)
Julia_Kiseleva_Unsupervised_Query_Segmentation_Using_Click_Data_and_Dictionaries_Information.pdfUnsupervised Query Segmentation Using Click Data and Dictionaries Information (pdf)
Четыре лекции о методе
Начала предметного анализа методов (на примере метода Ф.Бэкона)
Вариативность стратегий восприятия звучащего текста
Извлечение и классификация коллокаций на материале научных текстов. Предварительные наблюдения
Природа коллокаций в русском языке. Опыт автоматического извлечения и классификации на материале новостных текстов
Войтишек А. Повторы. Лирические рефреныПовторы. Лирические рефрены (pdf)
Войтишек А. Новое. Лирические рефреныНовое. Лирические рефрены (pdf)
Войтишек А. Всё об одном и том жеВсё об одном и том же. 500 лирических рефренов к 50-летию (pdf)
Войтишек А. Тысяча-часть-1Тысяча-часть-1 (pdf)
Войтишек А. Тысяча-часть-2Тысяча-часть-2 (pdf)
Войтишек А. АлфавитАлфавит (pdf)

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

 

5.1.1. Матричный латентно-семантический анализ

 

Метод кластерного анализа LSA/LSI (от англ. Latent Semantic Analysis/Indexing - метод латентно-семантического анализа/индексирования) [106] базируется на сингулярном разложении матриц (SVD) [93]. Пусть массиву документов  ставится в соответствие матрица , строки которой соответствуют документам, а столбцы – весовым значениям термов (размер словаря термов - ). Сингулярным разложением матрицы   ранга   размерности  называется ее разложение вида , где  и  ортогональные матрицы размерности   и , соответственно, а  диагональная матрица, диагональные элементы которой неотрицательны (). Диагональные элементы матрицы  называют сингулярными значениями матрицы . Заметим, что матрица , в отличие от матрицы , квадратная.

Приведенное выше разбиение матрицы  обладает тем свойством, что если в матрице  оставить только  наибольших сингулярных значений (обозначим такую матрицу как ), а в матрицах  и  только соответствующие этим значениям колонки (соответственно, матрицы ), то матрица  будет наилучшей по Фробениусу аппроксимацией исходной матрицы  матрицей с рангом, не превышающим . Напомним, что норма матрицы размерности по Фробениусу определяется выражением:

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

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

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

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

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

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

Если  вектор запроса,  i-й элемент которого равен 1, когда терм с номером  входит в запрос, и 0 - в противном случае, то  образ запроса  в пространстве латентных факторов будет иметь вид:  

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

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

Метод LSA широко применяется при ранжировании выдачи информационно-поисковых систем, основанных на цитировании. Это алгоритм HITS (Hyperlink Induced Topic Search) – один из двух самых известных в области информационного поиска. Метод LSA не нуждается в предварительной настройке на специфический набор документов, вместе с тем позволяет качественно выявлять скрытые факторы. К недостаткам метода можно отнести невысокую производительность. Скорость вычисления SVD соответствует порядку  где  множество документов,  множество термов,  размерность пространства факторов.

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

 

5.1.2. Вероятностный латентно-семантический анализ

 

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

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

         Обозначим через  вероятность того, что для  выбранного фактора  из множества фактов , именно документ  из всего множества документов  лучше всего характеризуется этим фактором. Тогда  Аналогично обозначим через  вероятность того, что для выбранного фактора , из всех термов именно терм  из словаря системы  лучше всего характеризуется этим фактором . Тогда

Вероятность того, что при случайном выборе документа  и терма ,  терм  встретится в документе , можно определить с одной стороны (рис. 19 a, ассиметричная параметризация), как:

С другой стороны, эта же вероятность при симметричной параметризации представляется (рис. 19 б) как:

 

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

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

 вероятность того, что документ  попадет в группу документов, соответствующих фактору ;

  вероятность того, что терм  попадет в группу слов, связанных с фактором .

ris19a

ris19b

а)

б)

Рис. 19. Графическое представление модели: а) - ассиметричная; б) - симметричная параметризация

 

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

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

 

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

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

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

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

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

Покажем, как представить PLSA в виде матричной записи. Определим матрицы: 1) , элементами которой  будут условные вероятности  ,  2) , элементами которой  будут условные вероятности  , 3)  - диагональную матрицу ранга , на диагонали которой будут размещены значения вероятностей . Объединенная вероятностная модель  аппроксимируется выражением  . Сравнивая это разложение с SVD, можно заметить, что   и  в PLSA также независимы ввиду предположения независимости термов и документов. Хотя приведенное разложение не является сингулярным, вместе с тем,   наибольших компонент  определяют правила кластеризации PLSA. Основное отличие PLSA от LSA заключается в выборе целевой функции .

 

Турник пресс брусья Проект СТАНКИ-БУ.РФ.