Скрытый семантический анализ

Скрытый семантический анализ ( LSA ) - это метод обработки естественного языка , в частности распределительной семантики , анализа отношений между набором документов и содержащимися в них терминами путем создания набора концепций, связанных с документами и терминами. LSA предполагает, что близкие по значению слова встречаются в похожих частях текста ( гипотеза распределения ). Матрица, содержащая количество слов в документе (строки представляют уникальные слова, а столбцы представляют каждый документ), строится из большого фрагмента текста и математического метода, называемого разложением по сингулярным значениям.(SVD) используется для уменьшения количества строк при сохранении структуры сходства между столбцами. Затем документы сравниваются путем определения косинуса угла между двумя векторами (или скалярного произведения между нормализацией двух векторов), образованного любыми двумя столбцами. Значения, близкие к 1, представляют очень похожие документы, а значения, близкие к 0, представляют очень разные документы. ^[1]

Метод поиска информации, использующий скрытую семантическую структуру, был запатентован в 1988 году ( патент США 4839853 , срок действия которого истек) Скоттом Дирвестером , Сьюзен Думейс , Джорджем Фурнасом , Ричардом Харшманом , Томасом Ландауэром , Карен Лохбаум и Линн Стритер . В контексте приложения к поиску информации его иногда называют скрытым семантическим индексированием ( LSI ). ^[2]

Обзор [ править ]

Матрица вхождений [ править ]

LSA может использовать матрицу «документ-термин», которая описывает вхождения терминов в документы; это разреженная матрица , строки которой соответствуют терминам, а столбцы - документам. Типичным примером взвешивания элементов матрицы является tf-idf (частота терминов – обратная частота документа): вес элемента матрицы пропорционален количеству раз, когда термины встречаются в каждом документе, где редкие термины перевешиваются, чтобы отразить их относительную важность.

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

Понижение ранга [ править ]

После построения матрицы вхождений LSA находит приближение низкого ранга ^[4] к матрице терм-документ . У этих приближений могут быть разные причины:

• Предполагается, что исходная матрица термин-документ слишком велика для вычислительных ресурсов; в этом случае приближенная матрица низкого ранга интерпретируется как приближение («наименьшее и необходимое зло»).
• Исходная матрица терминов и документов считается зашумленной : например, отдельные экземпляры терминов должны быть исключены. С этой точки зрения приближенная матрица интерпретируется как очищенная от шумов матрица (лучшая матрица, чем исходная).
• Исходная матрица термин-документ считается слишком разреженной по сравнению с «истинной» матрицей терм-документ. То есть в исходной матрице перечислены только слова, фактически содержащиеся в каждом документе, тогда как нас могут интересовать все слова, относящиеся к каждому документу - как правило, гораздо больший набор из-за синонимии .

Следствием понижения ранга является то, что некоторые параметры объединяются и зависят от более чем одного члена:

{(автомобиль), (грузовик), (цветок)} -> {(1,3452 * автомобиль + 0,2828 * грузовик), (цветок)}

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

Вывод [ править ]

Пусть будет матрицей, где элемент описывает появление термина в документе (это может быть, например, частота). будет выглядеть так:${\ displaystyle X}$${\ displaystyle (я, j)}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle X}$

${\displaystyle {\begin{matrix}&{\textbf {d}}_{j}\\&\downarrow \\{\textbf {t}}_{i}^{T}\rightarrow &{\begin{bmatrix}x_{1,1}&\dots &x_{1,j}&\dots &x_{1,n}\\\vdots &\ddots &\vdots &\ddots &\vdots \\x_{i,1}&\dots &x_{i,j}&\dots &x_{i,n}\\\vdots &\ddots &\vdots &\ddots &\vdots \\x_{m,1}&\dots &x_{m,j}&\dots &x_{m,n}\\\end{bmatrix}}\end{matrix}}}$

Теперь строка в этой матрице будет вектором, соответствующим термину, определяющему его отношение к каждому документу:

${\displaystyle {\textbf {t}}_{i}^{T}={\begin{bmatrix}x_{i,1}&\dots &x_{i,j}&\dots &x_{i,n}\end{bmatrix}}}$

Точно так же столбец в этой матрице будет вектором, соответствующим документу, с указанием его отношения к каждому термину:

${\displaystyle {\textbf {d}}_{j}={\begin{bmatrix}x_{1,j}\\\vdots \\x_{i,j}\\\vdots \\x_{m,j}\\\end{bmatrix}}}$

Теперь скалярное произведение между двумя векторами терминов дает корреляцию между терминами по набору документов. Матрица продукт содержит все эти точечные продукты. Элемент (который равен элементу ) содержит скалярное произведение ( ). Кроме того, матрица содержит точечные продукты между всеми векторами документов, давая их корреляцию над условиями: .${\displaystyle {\textbf {t}}_{i}^{T}{\textbf {t}}_{p}}$ ${\displaystyle XX^{T}}$${\displaystyle (i,p)}$${\displaystyle (p,i)}$${\displaystyle {\textbf {t}}_{i}^{T}{\textbf {t}}_{p}}$${\displaystyle ={\textbf {t}}_{p}^{T}{\textbf {t}}_{i}}$${\displaystyle X^{T}X}$${\displaystyle {\textbf {d}}_{j}^{T}{\textbf {d}}_{q}={\textbf {d}}_{q}^{T}{\textbf {d}}_{j}}$

Теперь, из теории линейной алгебры, существует разложение таких, что и являются ортогональными матрицами и являются диагональной матрицей . Это называется разложением по сингулярным значениям (SVD):${\displaystyle X}$${\displaystyle U}$${\displaystyle V}$${\displaystyle \Sigma }$

${\displaystyle {\begin{matrix}X=U\Sigma V^{T}\end{matrix}}}$

Матричные продукты, дающие нам корреляции терминов и документов, затем становятся

${\displaystyle {\begin{matrix}XX^{T}&=&(U\Sigma V^{T})(U\Sigma V^{T})^{T}=(U\Sigma V^{T})(V^{T^{T}}\Sigma ^{T}U^{T})=U\Sigma V^{T}V\Sigma ^{T}U^{T}=U\Sigma \Sigma ^{T}U^{T}\\X^{T}X&=&(U\Sigma V^{T})^{T}(U\Sigma V^{T})=(V^{T^{T}}\Sigma ^{T}U^{T})(U\Sigma V^{T})=V\Sigma ^{T}U^{T}U\Sigma V^{T}=V\Sigma ^{T}\Sigma V^{T}\end{matrix}}}$

Так и диагональные мы видим , что должны содержать собственные векторы о , в то время как должны быть собственные векторы . Оба продукта имеют одинаковые ненулевые собственные значения, заданные ненулевыми элементами или, в равной степени, ненулевыми элементами . Теперь разложение выглядит так:${\displaystyle \Sigma \Sigma ^{T}}$${\displaystyle \Sigma ^{T}\Sigma }$${\displaystyle U}$${\displaystyle XX^{T}}$${\displaystyle V}$${\displaystyle X^{T}X}$${\displaystyle \Sigma \Sigma ^{T}}$${\displaystyle \Sigma ^{T}\Sigma }$

${\displaystyle {\begin{matrix}&X&&&U&&\Sigma &&V^{T}\\&({\textbf {d}}_{j})&&&&&&&({\hat {\textbf {d}}}_{j})\\&\downarrow &&&&&&&\downarrow \\({\textbf {t}}_{i}^{T})\rightarrow &{\begin{bmatrix}x_{1,1}&\dots &x_{1,j}&\dots &x_{1,n}\\\vdots &\ddots &\vdots &\ddots &\vdots \\x_{i,1}&\dots &x_{i,j}&\dots &x_{i,n}\\\vdots &\ddots &\vdots &\ddots &\vdots \\x_{m,1}&\dots &x_{m,j}&\dots &x_{m,n}\\\end{bmatrix}}&=&({\hat {\textbf {t}}}_{i}^{T})\rightarrow &{\begin{bmatrix}{\begin{bmatrix}\,\\\,\\{\textbf {u}}_{1}\\\,\\\,\end{bmatrix}}\dots {\begin{bmatrix}\,\\\,\\{\textbf {u}}_{l}\\\,\\\,\end{bmatrix}}\end{bmatrix}}&\cdot &{\begin{bmatrix}\sigma _{1}&\dots &0\\\vdots &\ddots &\vdots \\0&\dots &\sigma _{l}\\\end{bmatrix}}&\cdot &{\begin{bmatrix}{\begin{bmatrix}&&{\textbf {v}}_{1}&&\end{bmatrix}}\\\vdots \\{\begin{bmatrix}&&{\textbf {v}}_{l}&&\end{bmatrix}}\end{bmatrix}}\end{matrix}}}$

Значения называются сингулярными значениями и левым и правым сингулярными векторами. Обратите внимание, что единственная часть, которая вносит вклад, - это строка. Позвольте этому вектору-строке называться . Точно так же единственная часть, которая вносит свой вклад, - это столбец . Это не собственные векторы, но они зависят от всех собственных векторов.${\displaystyle \sigma _{1},\dots ,\sigma _{l}}$${\displaystyle u_{1},\dots ,u_{l}}$${\displaystyle v_{1},\dots ,v_{l}}$${\displaystyle U}$${\displaystyle {\textbf {t}}_{i}}$${\displaystyle i{\textrm {'th}}}$${\displaystyle {\hat {\textrm {t}}}_{i}^{T}}$${\displaystyle V^{T}}$${\displaystyle {\textbf {d}}_{j}}$${\displaystyle j{\textrm {'th}}}$${\displaystyle {\hat {\textrm {d}}}_{j}}$

Оказывается, что когда вы выбираете наибольшие сингулярные значения и соответствующие им сингулярные векторы из и , вы получаете приближение ранга к с наименьшей ошибкой ( норма Фробениуса ). Это приближение имеет минимальную ошибку. Но что более важно, теперь мы можем рассматривать термин и векторы документа как «семантическое пространство». Вектор "термин" строка затем имеет записи, отображающие его в размерность пространства меньшей размерности. Эти новые измерения не относятся ни к каким понятным концепциям. Они представляют собой приближение более низкой размерности к пространству более высокой размерности. Точно так же вектор «документа» является приближением в этом пространстве меньшей размерности. Запишем это приближение как${\displaystyle k}$${\displaystyle U}$${\displaystyle V}$${\displaystyle k}$${\displaystyle X}$${\displaystyle {\hat {\textbf {t}}}_{i}^{T}}$${\displaystyle k}$${\displaystyle {\hat {\textbf {d}}}_{j}}$

${\displaystyle X_{k}=U_{k}\Sigma _{k}V_{k}^{T}}$

Теперь вы можете сделать следующее:

• Посмотрите, как связанные документы и находятся в низкоразмерном пространстве, сравнив векторы и (обычно по косинусному сходству ).${\displaystyle j}$${\displaystyle q}$${\displaystyle \Sigma _{k}\cdot {\hat {\textbf {d}}}_{j}}$${\displaystyle \Sigma _{k}\cdot {\hat {\textbf {d}}}_{q}}$
• Сравнивая термины и сравнивая векторы и . Обратите внимание, что теперь это вектор-столбец.${\displaystyle i}$${\displaystyle p}$${\displaystyle \Sigma _{k}\cdot {\hat {\textbf {t}}}_{i}}$${\displaystyle \Sigma _{k}\cdot {\hat {\textbf {t}}}_{p}}$${\displaystyle {\hat {\textbf {t}}}}$
• Документы и векторные представления терминов можно кластеризовать с использованием традиционных алгоритмов кластеризации, таких как k-среднее, с использованием таких мер сходства, как косинус.
• Получив запрос, просмотрите его как мини-документ и сравните его с вашими документами в низкоразмерном пространстве.

Чтобы сделать последнее, вы должны сначала перевести свой запрос в низкоразмерное пространство. Тогда интуитивно понятно, что вы должны использовать то же преобразование, которое вы используете в своих документах:

${\displaystyle {\hat {\textbf {d}}}_{j}=\Sigma _{k}^{-1}U_{k}^{T}{\textbf {d}}_{j}}$

Обратите внимание, что обратная диагональная матрица может быть найдена путем инвертирования каждого ненулевого значения в матрице.${\displaystyle \Sigma _{k}}$

Это означает, что если у вас есть вектор запроса , вы должны выполнить перевод, прежде чем сравнивать его с векторами документа в низкоразмерном пространстве. Вы можете сделать то же самое для векторов псевдотерм:${\displaystyle q}$${\displaystyle {\hat {\textbf {q}}}=\Sigma _{k}^{-1}U_{k}^{T}{\textbf {q}}}$

${\displaystyle {\textbf {t}}_{i}^{T}={\hat {\textbf {t}}}_{i}^{T}\Sigma _{k}V_{k}^{T}}$

${\displaystyle {\hat {\textbf {t}}}_{i}^{T}={\textbf {t}}_{i}^{T}V_{k}^{-T}\Sigma _{k}^{-1}={\textbf {t}}_{i}^{T}V_{k}\Sigma _{k}^{-1}}$

${\displaystyle {\hat {\textbf {t}}}_{i}=\Sigma _{k}^{-1}V_{k}^{T}{\textbf {t}}_{i}}$

Приложения [ править ]

Новое низкоразмерное пространство обычно можно использовать для:

• Сравните документы в низкоразмерном пространстве ( кластеризация данных , классификация документов ).
• Найдите похожие документы на разных языках после анализа базового набора переведенных документов ( поиск информации на разных языках ).
• Найдите отношения между терминами ( синонимия и многозначность ).
• Получив запрос терминов, переведите его в низкоразмерное пространство и найдите соответствующие документы ( поиск информации ).
• Найдите максимальное сходство между небольшими группами терминов семантическим способом (то есть в контексте корпуса знаний), как, например, в модели ответов MCQ на вопросы с несколькими вариантами ответов. ^[5]
• Расширьте функциональное пространство систем машинного обучения / интеллектуального анализа текста ^[6]
• Анализировать словесные ассоциации в корпусе текста ^[7]

Синонимия и многозначность - фундаментальные проблемы обработки естественного языка :

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

Коммерческие приложения [ править ]

LSA использовался для помощи в поиске патентов известного уровня техники . ^[8]

Приложения в человеческой памяти [ править ]

Использование скрытого семантического анализа было распространено при изучении человеческой памяти, особенно в областях свободного припоминания и поиска в памяти. Существует положительная корреляция между семантическим сходством двух слов (измеренным с помощью LSA) и вероятностью того, что слова будут вспоминаться одно за другим в задачах свободного отзыва с использованием учебных списков случайных нарицательных существительных. Они также отметили, что в этих ситуациях время взаимных ответов между похожими словами было намного быстрее, чем между разными словами. Эти результаты называются эффектом семантической близости . ^[9]

Когда участники совершали ошибки при вспоминании изученных элементов, эти ошибки, как правило, были элементами, которые были более семантически связаны с желаемым элементом и были обнаружены в ранее изученном списке. Эти вторжения из предыдущего списка, как их стали называть, похоже, конкурируют с элементами текущего списка за отзыв. ^[10]

Другая модель, называемая Пространства ассоциаций слов (WAS), также используется в исследованиях памяти путем сбора данных о свободных ассоциациях из серии экспериментов, которые включают меры родства слов для более чем 72 000 различных пар слов. ^[11]

Реализация [ править ]

СВД , как правило , вычисляются с использованием больших матричных методов (например, методов Ланцоша ) , но также может быть вычислено постепенно и со значительно сниженными ресурсами с помощью нейронной сети -подобного подхода, который не требует большой, полный ранг матрицы , которые будут проходить в объем памяти. ^[12] Недавно был разработан быстрый инкрементный алгоритм SVD с большой матрицей и малым объемом памяти. ^[13] MATLAB и Pythonдоступны реализации этих быстрых алгоритмов. В отличие от стохастической аппроксимации Горрелла и Уэбба (2005), алгоритм Брэнда (2003) дает точное решение. В последние годы был достигнут прогресс в уменьшении вычислительной сложности SVD; например, используя параллельный алгоритм ARPACK для выполнения параллельного разложения на собственные значения, можно ускорить стоимость вычислений SVD, обеспечивая при этом сопоставимое качество предсказания. ^[14]

Ограничения [ править ]

Некоторые из недостатков LSA включают:

• Полученные размеры может быть трудно интерпретировать. Например, в

{(автомобиль), (грузовик), (цветок)} ↦ {(1,3452 * автомобиль + 0,2828 * грузовик), (цветок)}

компонент (1,3452 * автомобиль + 0,2828 * грузовик) можно интерпретировать как «транспортное средство». Однако весьма вероятно, что случаи, близкие к

{(машина), (бутылка), (цветок)} ↦ {(1,3452 * машина + 0,2828 * бутылка ), (цветок)}

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

• LSA может только частично фиксировать многозначность (т. Е. Множественные значения слова), потому что каждое вхождение слова рассматривается как имеющее одно и то же значение из-за того, что слово представлено как единственная точка в пространстве. Например, появление слова «председатель» в документе, содержащем «Председатель Правления», и в отдельном документе, содержащем слово «председатель правления», считается одним и тем же. Такое поведение приводит к тому, что векторное представление представляет собой среднее значение всех различных значений слова в корпусе, что может затруднить сравнение. ^[15] Однако эффект часто уменьшается из-за того, что слова имеют преобладающий смысл во всем корпусе (т.е. не все значения одинаково вероятны).
• Ограничения модели мешка слов (BOW), где текст представлен как неупорядоченный набор слов. Чтобы устранить некоторые ограничения модели мешка слов (BOW), можно использовать многограммный словарь для поиска прямых и косвенных ассоциаций, а также совпадений более высокого порядка между терминами. ^[16]
• Вероятностная модель НУА не соответствует наблюдаемым данным: LSA предполагает , что слова и документы образуют совместную Gaussian модели ( эргодическая гипотеза ), в то время как распределение Пуассона наблюдается. Таким образом, более новой альтернативой является вероятностный латентно-семантический анализ , основанный на полиномиальной модели, который, как сообщается, дает лучшие результаты, чем стандартный LSA. ^[17]

Альтернативные методы [ править ]

Семантическое хеширование [ править ]

В семантическом хешировании ^[18] документы отображаются в адреса памяти с помощью нейронной сети таким образом, что семантически похожие документы располагаются по соседним адресам. Глубокая нейронная сеть по сути строит графическую модель векторов подсчета слов, полученных из большого набора документов. Документы, похожие на документ запроса, затем можно найти, просто обратившись ко всем адресам, которые отличаются всего на несколько бит от адреса документа запроса. Этот способ повышения эффективности хэш-кодирования для приблизительного сопоставления намного быстрее, чем хеширование с учетом местоположения , которое является самым быстрым из существующих методов. ^{[ требуется разъяснение ]}

Скрытое семантическое индексирование [ править ]

Скрытое семантическое индексирование ( LSI ) - это метод индексации и поиска, который использует математический метод, называемый разложением по сингулярным значениям (SVD), для выявления закономерностей во взаимосвязях между терминами и концепциями, содержащимися в неструктурированном наборе текста. LSI основан на том принципе, что слова, которые используются в одном контексте, имеют сходные значения. Ключевой особенностью LSI является его способность извлекать концептуальное содержание основного текста путем установления ассоциаций между теми терминами, которые встречаются в аналогичных контекстах . ^[19]

LSI также представляет собой приложение анализа соответствий , многомерного статистического метода, разработанного Жан-Полем Бенцекри ^[20] в начале 1970-х годов, для таблицы непредвиденных обстоятельств, построенной на основе количества слов в документах.

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

Преимущества LSI [ править ]

LSI помогает преодолеть синонимию, увеличивая отзывчивость , одно из наиболее проблемных ограничений логических запросов по ключевым словам и моделей векторного пространства. ^[15] Синонимия часто является причиной несоответствий в лексике, используемой авторами документов и пользователями информационно-поисковых систем. ^[21] В результате логические запросы или запросы по ключевым словам часто возвращают нерелевантные результаты и пропускают релевантную информацию.

LSI также используется для автоматической категоризации документов . Фактически, несколько экспериментов продемонстрировали, что существует ряд корреляций между тем, как LSI и люди обрабатывают и классифицируют текст. ^[22] Категоризация документов - это отнесение документов к одной или нескольким предопределенным категориям на основе их сходства с концептуальным содержанием категорий. ^[23] LSI использует примердокументы, устанавливающие концептуальную основу для каждой категории. Во время обработки категоризации концепции, содержащиеся в классифицируемых документах, сравниваются с концепциями, содержащимися в примерах элементов, и категория (или категории) присваивается документам на основе сходства между концепциями, которые они содержат, и концепциями, которые они содержат. в примерах документов.

Динамическая кластеризация на основе концептуального содержания документов также может выполняться с помощью LSI. Кластеризация - это способ группировки документов на основе их концептуального сходства друг с другом без использования примеров документов для создания концептуальной основы для каждого кластера. Это очень полезно при работе с неизвестным набором неструктурированного текста.

Поскольку он использует строго математический подход, LSI по своей сути не зависит от языка. Это позволяет LSI извлекать семантическое содержание информации, написанной на любом языке, без необходимости использования вспомогательных структур, таких как словари и тезаурусы. LSI также может выполнять кросс-лингвистический поиск концепций и категоризацию на основе примеров. Например, запросы могут быть выполнены на одном языке, таком как английский, и будут возвращены концептуально похожие результаты, даже если они составлены на совершенно другом языке или на нескольких языках. ^{[ необходима цитата ]}

LSI не ограничивается работой только со словами. Он также может обрабатывать произвольные строки символов. Любой объект, который может быть выражен как текст, может быть представлен в векторном пространстве LSI. Например, тесты с рефератами из MEDLINE показали, что LSI может эффективно классифицировать гены на основе концептуального моделирования биологической информации, содержащейся в заголовках и отрывках из ссылок MEDLINE. ^[24]

LSI автоматически приспосабливается к новой и меняющейся терминологии и, как было показано, очень устойчив к шуму (например, к ошибкам в написании слов, типографским ошибкам, нечитаемым символам и т. Д.). ^[25] Это особенно важно для приложений, использующих текст, полученный с помощью оптического распознавания символов (OCR) и преобразования речи в текст. LSI также эффективно работает с разреженными, неоднозначными и противоречивыми данными.

Чтобы LSI была эффективной, текст не обязательно должен быть в форме предложения. Он может работать со списками, заметками произвольной формы, электронной почтой, веб-контентом и т. Д. Если набор текста содержит несколько терминов, LSI можно использовать для выявления закономерностей во взаимосвязях между важными терминами и концепциями, содержащимися в текст.

LSI оказался полезным решением ряда концептуальных проблем сопоставления. ^{[26] [27]} Было показано, что этот метод позволяет собирать ключевую информацию о взаимосвязях, включая причинно-следственную, целевую и таксономическую информацию. ^[28]

Хронология LSI [ править ]

• Середина 1960-х - впервые описана и протестирована методика факторного анализа (Х. Борко и М. Берник).
• 1988 - Опубликована заключительная статья по технике LSI ^[19]
• 1989 - Выдан оригинальный патент ^[19]
• 1992 - Первое использование LSI для назначения статей рецензентам ^[29]
• 1994 - Получен патент на межъязыковое применение LSI (Ландауэр и др.)
• 1995 - Первое использование LSI для оценки эссе (Фольц и др., Ландауэр и др.)
• 1999 - Первое внедрение технологии LSI для разведывательного сообщества для анализа неструктурированного текста ( SAIC ).
• 2002 - предложение продуктов на базе LSI для правительственных агентств, основанных на разведке (SAIC)

Математика LSI [ править ]

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

Матрица курьерских документов [ править ]

LSI начинает с построения матрицы термин-документ , чтобы идентифицировать вхождения уникальных терминов в коллекции документов. В матрице Термин документа, каждый член представлен ряд, и каждый документ представлен столбцом, с каждой ячейке матрицы, первоначально представляющий число раз ассоциированный член появляется в указанном документе, . Эта матрица обычно очень большая и очень разреженная.${\displaystyle A}$${\displaystyle m}$${\displaystyle n}$${\displaystyle a_{ij}}$${\displaystyle \mathrm {tf_{ij}} }$

После построения матрицы терм-документ к ней могут быть применены локальные и глобальные весовые функции для кондиционирования данных. Весовые функции преобразования каждой ячейки, из того , чтобы быть продуктом местного термина веса, , который описывает относительную частоту термина в документе, и глобальный вес, , который описывает относительную частоту термина в пределах всей коллекции документов.${\displaystyle a_{ij}}$${\displaystyle A}$${\displaystyle l_{ij}}$${\displaystyle g_{i}}$

Некоторые общие локальные весовые функции ^[30] определены в следующей таблице.

Двоичный		${\displaystyle l_{ij}=1}$ если термин существует в документе, или иначе ${\displaystyle 0}$
Срок		${\displaystyle l_{ij}=\mathrm {tf} _{ij}}$, количество появлений термина в документе${\displaystyle i}$${\displaystyle j}$
Бревно		${\displaystyle l_{ij}=\log(\mathrm {tf} _{ij}+1)}$
Augnorm		${\displaystyle l_{ij}={\frac {{\Big (}{\frac {\mathrm {tf} _{ij}}{\max _{i}(\mathrm {tf} _{ij})}}{\Big )}+1}{2}}}$

Некоторые общие глобальные весовые функции определены в следующей таблице.

Двоичный		${\displaystyle g_{i}=1}$
Обычный		${\displaystyle g_{i}={\frac {1}{\sqrt {\sum _{j}\mathrm {tf} _{ij}^{2}}}}}$
GfIdf		${\displaystyle g_{i}=\mathrm {gf} _{i}/\mathrm {df} _{i}}$, где - общее количество раз, когда термин встречается во всей коллекции, и - это количество документов, в которых встречается термин .${\displaystyle \mathrm {gf} _{i}}$${\displaystyle i}$${\displaystyle \mathrm {df} _{i}}$${\displaystyle i}$
Idf (обратная частота документов)		${\displaystyle g_{i}=\log _{2}{\frac {n}{1+\mathrm {df} _{i}}}}$
Энтропия		${\displaystyle g_{i}=1+\sum _{j}{\frac {p_{ij}\log p_{ij}}{\log n}}}$, где ${\displaystyle p_{ij}={\frac {\mathrm {tf} _{ij}}{\mathrm {gf} _{i}}}}$

Эмпирические исследования с LSI показывают, что функции взвешивания журнала и энтропии хорошо работают на практике со многими наборами данных. ^[31] Другими словами, каждый элемент из вычисляется как:${\displaystyle a_{ij}}$${\displaystyle A}$

${\displaystyle g_{i}=1+\sum _{j}{\frac {p_{ij}\log p_{ij}}{\log n}}}$

${\displaystyle a_{ij}=g_{i}\ \log(\mathrm {tf} _{ij}+1)}$

Разложение по сингулярным числам с пониженным рангом [ править ]

Разложение по сингулярным значениям с пониженным рангом выполняется в матрице для определения закономерностей в отношениях между терминами и понятиями, содержащимися в тексте. СВД составляет основу LSI. ^[32] Он вычисляет срок и векторные пространства документа путем аппроксимации единой матрицы Термина частоты, на три другие matrices- м на г Термина-концепция векторной матрицы , г на г сингулярных значений матрицы , а п с помощью г концепции -документная векторная матрица, удовлетворяющая следующим соотношениям:${\displaystyle A}$${\displaystyle T}$${\displaystyle S}$${\displaystyle D}$

${\displaystyle A\approx TSD^{T}}$

${\displaystyle T^{T}T=I_{r}\quad D^{T}D=I_{r}}$

${\displaystyle S_{1,1}\geq S_{2,2}\geq \ldots \geq S_{r,r}>0\quad S_{i,j}=0\;{\text{where}}\;i\neq j}$

В формуле A - это предоставленная взвешенная матрица m на n частот терминов в наборе текста, где m - количество уникальных терминов, а n - количество документов. T - это вычисляемая матрица векторов термов размером m на r, где r - ранг A - мера его уникальных размерностей ≤ min ( m, n ) . S - это вычисляемая диагональная матрица убывающих сингулярных значений r на r , а D - вычисляемая n на r матрица векторов документов.

Затем SVD усекается, чтобы уменьшить ранг, сохраняя только наибольшие k «  r диагональных элементов в матрице S сингулярных значений , где k обычно имеет порядок от 100 до 300 измерений. Это эффективно уменьшает размеры матрицы термина и вектора документа до m на k и n на k соответственно. Операции СВД, наряду с этим сокращением, имеет эффект сохранения наиболее важной семантической информации в тексте при одновременном снижении шума и других нежелательных артефактов исходного пространства A . Этот сокращенный набор матриц часто обозначается модифицированной формулой, например:

A ≈ A _k = T _k S _k D _k ^T

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

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

Запрос и расширение векторных пространств LSI [ править ]

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

Те же шаги используются для поиска векторов, представляющих текст запросов и новых документов в пространстве документов существующего индекса LSI. Путем простого преобразования уравнения A = TSD ^T в эквивалентное уравнение D = A ^T TS ^{−1 можно} создать новый вектор d для запроса или нового документа, вычислив новый столбец в A и затем умножив новый столбец на TS ⁻¹ . Новый столбец в A вычисляется с использованием первоначально полученных глобальных весов терминов и применения той же локальной весовой функции к терминам в запросе или в новом документе.

Недостатком такого способа вычисления векторов при добавлении новых доступных для поиска документов является то, что термины, которые не были известны на этапе SVD для исходного индекса, игнорируются. Эти термины не будут иметь никакого влияния на глобальные веса и усвоенные корреляции, полученные из исходного набора текста. Однако вычисленные векторы для нового текста по-прежнему очень важны для сравнений схожести со всеми другими векторами документа.

Такой процесс увеличения векторных пространств документов для индекса LSI новыми документами называется сворачиванием . Хотя процесс свертывания не учитывает новое семантическое содержание нового текста, добавление значительного количества документов таким образом по-прежнему будет обеспечивать хорошие результаты для запросов, если термины и концепции, которые они содержат, хорошо представлены в LSI. индекс, в который они добавляются. Когда термины и концепции нового набора документов необходимо включить в индекс LSI, необходимо пересчитать либо матрицу термин-документ, либо SVD, либо использовать метод инкрементного обновления (например, описанный в ^[13] ). необходим.

Дополнительное использование LSI [ править ]

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

LSI используется во множестве приложений для поиска информации и обработки текста, хотя его основное применение - поиск концепций и автоматическая категоризация документов. ^[33] Ниже приведены некоторые другие способы использования LSI:

• Обнаружение информации ^[34] ( eDiscovery , правительство / разведывательное сообщество, публикации)
• Автоматическая классификация документов (eDiscovery, правительство / разведывательное сообщество, публикации) ^[35]
• Обобщение текста ^[36] (eDiscovery, Publishing)
• Обнаружение отношений ^[37] (правительство, разведывательное сообщество, социальные сети)
• Автоматическое создание диаграмм связей отдельных лиц и организаций ^[38] (правительство, разведывательное сообщество)
• Согласование технических документов и грантов с рецензентами ^[39] (Правительство)
• Онлайн-поддержка клиентов ^[40] (Управление клиентами)
• Определение авторства документа ^[41] (Образование)
• Автоматическое аннотирование изображений по ключевым словам ^[42]
• Понимание исходного кода программного обеспечения ^[43] (Разработка программного обеспечения)
• Фильтрация спама ^[44] (Системное администрирование)
• Визуализация информации ^[45]
• Оценка эссе ^[46] (Образование)
• Открытие, основанное на литературе ^[47]
• Прогноз доходности акций ^[6]
• Анализ содержания сновидений (психология) ^[7]

LSI все чаще используется для обнаружения электронных документов (eDiscovery), чтобы помочь предприятиям подготовиться к судебным разбирательствам. В eDiscovery очень важна возможность кластеризации, категоризации и поиска в больших коллекциях неструктурированного текста на концептуальной основе. Поиск на основе концепций с использованием LSI был применен к процессу обнаружения электронных данных ведущими поставщиками еще в 2003 году ^[48].

Проблемы LSI [ править ]

Первые вызовы LSI были связаны с масштабируемостью и производительностью. LSI требует относительно высокой вычислительной производительности и памяти по сравнению с другими методами поиска информации. ^[49] Однако с внедрением современных высокоскоростных процессоров и доступностью недорогой памяти эти соображения в значительной степени были преодолены. Реальные приложения, включающие более 30 миллионов документов, которые были полностью обработаны с помощью матрицы, и вычисления SVD распространены в некоторых приложениях LSI. Полностью масштабируемая (неограниченное количество документов, онлайн-обучение) реализация LSI содержится в пакете программного обеспечения gensim с открытым исходным кодом. ^[50]

Другой проблемой для LSI была предполагаемая сложность определения оптимального количества измерений для использования при выполнении SVD. Как правило, меньшее количество измерений позволяет проводить более широкие сравнения концепций, содержащихся в коллекции текста, в то время как большее количество измерений позволяет проводить более конкретные (или более релевантные) сравнения концепций. Фактическое количество измерений, которые можно использовать, ограничено количеством документов в коллекции. Исследования показали, что около 300 измерений обычно обеспечивают наилучшие результаты для коллекций документов среднего размера (сотни тысяч документов) и, возможно, 400 измерений для более крупных коллекций документов (миллионы документов). ^[51] Однако недавние исследования показывают, что от 50 до 1000 измерений подходят в зависимости от размера и характера коллекции документов. ^[52] Проверка доли сохраненной дисперсии, аналогичная PCA или факторному анализу , для определения оптимальной размерности не подходит для LSI. Использование теста синонимов или прогнозирования пропущенных слов - два возможных метода определения правильной размерности. ^[53] Когда темы LSI используются в качестве функций в контролируемых методах обучения, можно использовать измерения ошибок прогнозирования, чтобы найти идеальную размерность.

См. Также [ править ]

• Coh-Metrix
• Обработка сложных терминов
• Распределительная семантика
• Явный семантический анализ
• Скрытое семантическое отображение
• Индексирование скрытой семантической структуры
• Анализ основных компонентов
• Вероятностный латентно-семантический анализ
• Спамдексинг
• Слово вектор
• Тематическая модель
  • Скрытое размещение Дирихле

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Ландауэр, Томас ; Фольц, Питер В .; Лахам, Даррелл (1998). «Введение в скрытый семантический анализ» (PDF) . Дискурсивные процессы . 25 (2–3): 259–284. CiteSeerX  10.1.1.125.109 . DOI : 10.1080 / 01638539809545028 .
• Дирвестер, Скотт ; Дюмэ, Сьюзен Т .; Фурнас, Джордж У .; Ландауэр, Томас К .; Харшман, Ричард (1990). «Индексирование с помощью скрытого семантического анализа» (PDF) . Журнал Американского общества информационных наук . 41 (6): 391–407. CiteSeerX  10.1.1.33.2447 . DOI : 10.1002 / (SICI) 1097-4571 (199009) 41: 6 <391 :: AID-ASI1> 3.0.CO; 2-9 . Архивировано из оригинального (PDF) 17 июля 2012 года. Оригинальная статья, в которой впервые была представлена ​​модель.
• Берри, Майкл ; Dumais, Susan T .; О'Брайен, Гэвин В. (1995). «Использование линейной алгебры для интеллектуального поиска информации» . Cite journal requires |journal= (help) (PDF) . Иллюстрация применения LSA для поиска документов.
• «Скрытый семантический анализ» . InfoVis.
• Фридолин Вайлд (23 ноября 2005 г.). «Пакет LSA с открытым исходным кодом для R» . КРАН . Проверено 20 ноября 2006 года .
• Томас Ландауэр , Сьюзан Т. Дюмэ . «Решение проблемы Платона: теория скрытого семантического анализа приобретения, индукции и представления знаний» . Проверено 2 июля 2007 .

Внешние ссылки [ править ]

Статьи о LSA [ править ]

• Скрытый семантический анализ , научная статья о LSA, написанная Томом Ландауэром, одним из создателей LSA.

Беседы и демонстрации [ править ]

• Обзор LSA , доклад профессора Томаса Хофманна, описывающий LSA, его приложения в поиске информации и его связи с вероятностным скрытым семантическим анализом .
• Полный пример кода LSA на C # для Windows . Демонстрационный код включает в себя перечисление текстовых файлов, фильтрацию стоп-слов, выделение корней, создание матрицы документов и терминов и SVD.

Реализации [ править ]

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

• Sense Clusters , реализация LSA на языке Perl, ориентированная на поиск информации
• S-Space Package , ориентированная на компьютерную лингвистику и когнитивную науку Java-реализацию LSA
• Semantic Vectors применяет случайную проекцию, LSA и отражающее случайное индексирование к матрицам терминов Lucene.
• Infomap Project , NLP-ориентированная реализация LSA на языке C (заменена проектом semanticvectors)
• Генератор текста в матрицу , набор инструментов MATLAB для создания матриц терминов-документов из текстовых коллекций с поддержкой LSA
• Gensim содержит реализацию LSA на Python для матриц размером больше ОЗУ.