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

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

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

Обзор

Продолжительность: 19 секунд. 0:19

Анимация процесса обнаружения темы в матрице документ-слово. Каждый столбец соответствует документу, каждая строка — слову. В ячейке хранится вес слова в документе (например, по tf-idf ), темные ячейки указывают на высокий вес. LSA группирует как документы, содержащие похожие слова, так и слова, встречающиеся в аналогичном наборе документов. Полученные шаблоны используются для обнаружения скрытых компонентов.

Матрица вхождений

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

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

Понижение ранга

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

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

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

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

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

Вывод

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

${\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}}$

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

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

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

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

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

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

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

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

${\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}}$

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

${\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}}$

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

Коммерческие приложения

LSA использовался для оказания помощи в по известному уровню техники поиске патентов .

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

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

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

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

Выполнение

SVD подхода , обычно вычисляется с использованием методов больших матриц (например, методов Ланцоша ), но также может вычисляться постепенно и со значительно меньшими ресурсами с помощью подобного нейронной сети , который не требует хранения большой матрицы полного ранга в память. Недавно был разработан быстрый инкрементный алгоритм SVD с малым объемом памяти и большой матрицей. МАТЛАБ и Питон доступны реализации этих быстрых алгоритмов. В отличие от стохастической аппроксимации Горрелла и Уэбба (2005), алгоритм Брэнда (2003) обеспечивает точное решение. В последние годы был достигнут прогресс в снижении вычислительной сложности SVD; например, используя параллельный алгоритм ARPACK для выполнения параллельного разложения по собственным значениям, можно ускорить затраты на вычисления SVD, обеспечивая при этом сопоставимое качество прогнозирования.

Ограничения

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

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

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

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

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

произойдет. Это приводит к результатам, которые могут быть оправданы на математическом уровне, но не имеют непосредственного очевидного значения на естественном языке. Однако составляющая (1,3452 * автомобиль + 0,2828 * бутылка) может быть оправдана тем, что и бутылки, и автомобили имеют прозрачные и непрозрачные части, изготовлены человеком и с высокой вероятностью содержат на своей поверхности логотипы/слова; таким образом, во многих отношениях эти два понятия «разделяют семантику». То есть в рассматриваемом языке может не быть легкодоступного слова, которое можно было бы присвоить, и объяснимость становится задачей анализа, в отличие от простой задачи присвоения слова/класса/концепции.

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

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

Семантическое хеширование

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

Скрытая семантическая индексация

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

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

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

Преимущества ЛСИ

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

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

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

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

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

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

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

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

График работы LSI

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

Математика БИС

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

Матрица терминодокументов

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

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

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

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

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

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

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

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

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

Разложение сингулярных значений с пониженным рангом

с пониженным рангом Разложение по сингулярным значениям выполняется для определения закономерностей во взаимоотношениях между терминами и понятиями, содержащимися в тексте. SVD составляет основу LSI. Он вычисляет векторные пространства терминов и документов путем аппроксимации одной матрицы частот терминов, $A$, на три другие матрицы — m на r. векторную матрицу терминов и понятий размером $T$, r x r матрица сингулярных значений $S$и n на r , векторная матрица концептуального документа $D$, которые удовлетворяют следующим соотношениям:

$A\approx TSD^{T}$

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

$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 соответственно. Операция SVD, наряду с этим сокращением, позволяет сохранить наиболее важную семантическую информацию в тексте, одновременно уменьшая шум и другие нежелательные артефакты исходного A. пространства Этот сокращенный набор матриц часто обозначается модифицированной формулой, например:

А ≈ А _k знак равно T _k S _k D _k ^Т

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

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

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

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

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

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

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

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

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

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

• Обнаружение информации ( eDiscovery , Правительство/разведывательное сообщество, Издательство)
• Автоматизированная классификация документов (обнаружение электронных данных, правительственное/разведывательное сообщество, публикации)
• Обобщение текста (обнаружение электронных данных, публикация)
• Открытие отношений (Правительство, разведывательное сообщество, социальные сети)
• Автоматическое создание диаграмм связей отдельных лиц и организаций (Правительство, Разведывательное сообщество)
• Согласование технических документов и грантов с рецензентами (Правительство)
• Онлайн-поддержка клиентов (Управление клиентами)
• Определение авторства документа (Образование)
• Автоматическое аннотирование изображений по ключевым словам
• Понимание исходного кода программного обеспечения (Программная инженерия)
• Фильтрация спама (Системное администрирование)
• Визуализация информации
• Оценка эссе (Образование)
• Открытие на основе литературы
• Прогноз доходности акций
• Анализ содержания сновидений (психология)

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

Проблемы LSI

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

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

См. также

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

Дальнейшее чтение

• Ландауэр, Томас ; Фольц, Питер В.; Лахам, Даррелл (1998). «Введение в латентно-семантический анализ» (PDF) . Дискурсивные процессы . 25 (2–3): 259–284. CiteSeerX   10.1.1.125.109 . дои : 10.1080/01638539809545028 . S2CID   16625196 .
• Дирвестер, Скотт ; Дюмэ, Сьюзен Т .; Фурнас, Джордж В .; Ландауэр, Томас К .; Харшман, Ричард (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 г. Оригинальная статья, где модель впервые была выставлена.
• Берри, Майкл ; Дюмэ, Сьюзен Т.; О'Брайен, Гэвин В. (1995). «Использование линейной алгебры для интеллектуального поиска информации» . (PDF) Архивировано 23 ноября 2018 г. в Wayback Machine . Иллюстрация применения LSA для поиска документов.
• Чикко, Д; Массероли, М (2015). «Программный пакет для прогнозирования аннотаций генов и белков и поиска сходства» . Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 12 (4): 837–843. дои : 10.1109/TCBB.2014.2382127 . hdl : 11311/959408 . ПМИД   26357324 . S2CID   14714823 .
• «Скрытый семантический анализ» . ИнфоВис. Архивировано из оригинала 18 февраля 2020 г. Проверено 1 июля 2005 г.
• Фридолин Уайлд (23 ноября 2005 г.). «Пакет LSA с открытым исходным кодом для R» . КРАН . Проверено 20 ноября 2006 г.
• Томас Ландауэр , Сьюзен Т. Дюмэ . «Решение проблемы Платона: теория скрытого семантического анализа приобретения, индукции и представления знаний» . Проверено 2 июля 2007 г.

Внешние ссылки

Статьи о ЛСА

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

Переговоры и демонстрации

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

Реализации

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

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