Латентно-семантическое индексирование

Это перевод. Оригинал: Latent semantic indexing

 

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

Но сперва нам нужно обосновать такую аппроксимацию. Вспомним представление документов и запросов в векторном пространстве, введённое в Разделе 6.3 (страница). Это представление в векторном пространстве имеет множество преимуществ, таких как единообразное обращение к запросам и документам как к векторам, вычисление оценки, основанное на косинусном сходстве, способность взвешивать разные слова по-разному, а также его расширяемость за рамки получения документов с целью кластеризации и классификации. Впрочем, представление в векторном пространстве не умеет справляться с двумя классическими проблемами, возникающими в естественных языках: синонимичность и многозначность. Синонимичность - это случаи, когда два разных слова (например машина и автомобиль) имеют одинаковое значение. Представление в векторном пространстве не  имеет связи между синонимичными словами, такими как машина и автомобиль - и размещает их в разных измерениях векторного пространства. Вследствие этого вычисляемое сходство между запросом (например “машина”) и документом , содержащим оба слова “машина” и “автомобиль”, не учитывает реальное сходство, которое увидел бы человек. Многозначность же являет собой случаи, когда одно слово, например “лист”, имеет несколько значений, из-за чего вычисляемое сходство получается выше, чем воспринимаемое человеком. Можем ли мы использовать появление слов в разном контексте (например слово “лист”, встречающееся в документе о деревьях, и в документе о фанере) чтобы уловить латентно-семантические ассоциации между словами и решить эти проблемы?

 

Даже у набора скромного размера матрица документов и слов C скорее всего будет иметь несколько десятков тысяч строк и столбцов, а также ранг в несколько десятков тысяч. При латентно-семантическом индексировании (иногда называемом латентно-семантическим анализом (ЛСА)) мы используем сингулярное разложение матрицы для создания низкоранговой аппроксимации  Ck терм-документной матрицы, со значением k, значительно меньшим оригинального ранга матрицы C. В экспериментальной работе, описываемой ниже в этом разделе, значение k принимается в районе 100. Далее мы присваиваем каждую строку/каждый столбец (соответственно слову/документу) k-мерному пространству; это пространство определяется k собственными векторами (соответственно самым большим собственным значениям) и . Заметим, что матрица Ck сама по себе по-прежнему остаётся матрицей , независимо от k.

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

 

(244)

 

Теперь мы можем воспользоваться мерой косинусного сходства как в Разделе 6.3.1 (страница) чтобы вычислить сходство между запросом и документом, между двумя документами или между двумя словами. Отметим, что формула 244 никоим образом не зависит от того, что был запросом; это просто вектор в пространстве слов. Это означает, что если у нас есть LSI-представление набора документов, то новый документ может быть “вложен” в это представление с помощью Формулы 244. Это позволяет нам пошагово добавлять документы в LSI-представление. Разумеется, такое пошаговое добавление не учитывает смежность новых добавленных документов (и даже игнорирует любые новые слова, которые в них содержатся). Вследствие этого качество LSI-представления будет деградировать при добавлении всё новых и новых документов и со временем потребует перевычисления LSI-представления.

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

 

Рабочий пример. Создадим матрицу документов и слов  

 

 

$d_1$

$d_2$

$d_3$

$d_4$

$d_5$

$d_6$

 

 

ship

1

0

1

0

0

0

 

 

boat

0

1

0

0

0

0

 

 

ocean

1

1

0

0

0

0

 

 

voyage

1

0

0

1

1

0

 

 

trip

0

0

0

1

0

1

 
 

В результате сингулярного разложения этой матрицы, получаем 3 матрицы, приведённые ниже. Первой идёт , которая в этом примере выглядит так:

 

 

 

1

2

3

4

5

 

 

ship

$-0.44$

$-0.30$

$0.57$

$0.58$

$0.25$

 

 

boat

$-0.13$

$-0.33$

$-0.59$

0.00

0.73

 

 

ocean

$-0.48$

$-0.51$

$-0.37$

0.00

$-0.61$

 

 

voyage

$-0.70$

0.35

0.15

$-0.58$

0.16

 

 

trip

$-0.26$

0.65

$-0.41$

0.58

$-0.09$

 
 

При сингулярном разложении считается матрицей слов сингулярного разложения. Сингулярные значения ∑= 

 

2.16

0.00

0.00

0.00

0.00

0.00

1.59

0.00

0.00

0.00

0.00

0.00

1.28

0.00

0.00

0.00

0.00

0.00

1.00

0.00

0.00

0.00

0.00

0.00

0.39
 

Наконец, у нас есть , которая в контексте матрицы слов и документов известна как сингулярно разложенная матрица документов:

 

 

$d_1$

$d_2$

$d_3$

$d_4$

$d_5$

$d_6$

 

 

1

$-0.75$

$-0.28$

$-0.20$

$-0.45$

$-0.33$

$-0.12$

 

 

2

$-0.29$

$-0.53$

$-0.19$

0.63

0.22

0.41

 

 

3

0.28

$-0.75$

0.45

$-0.20$

0.12

$-0.33$

 

 

4

0.00

0.00

0.58

0.00

$-0.58$

0.58

 

 

5

$-0.53$

0.29

0.63

0.19

0.41

$-0.22$

 
 

 

“Обнулив” все, кроме двух самых больших сингулярных значений ∑, мы получим ∑2=

2.16

0.00

0.00

0.00

0.00

0.00

1.59

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00
 

На основе этого мы вычисляем С2 =

 

 

 

$d_1$

$d_2$

$d_3$

$d_4$

$d_5$

$d_6$

 

 

1

$-1.62$

$-0.60$

$-0.44$

$-0.97$

$-0.70$

$-0.26$

 

 

2

$-0.46$

$-0.84$

-0.30

1.00

0.35

0.65

 

 

3

0.00

0.00

0.00

0.00

0.00

0.00

 

 

4

0.00

0.00

0.00

0.00

0.00

0.00

 

 

5

0.00

0.00

0.00

0.00

0.00

0.00

 
 

Заметьте, что низкоранговая аппроксимация, в отличие от оригинальной матрицы C, может иметь отрицательные значения. Конец рабочего примера.

 

Рассмотрение C2 и ∑2 в показывает, что последние три строки обеих матриц были заполнены нулями. Это означает, что результат сингулярного разложения в Формуле 241 может быть вычислен только для первых двух строк в представлениях ∑2 и ; после чего мы можем заменить эти матрицы их усечёнными версиями ∑'2  и . Например, усечённая матрица документов сингулярного разложения  в данном примере выглядит так:

 

 

 

$d_1$

$d_2$

$d_3$

$d_4$

$d_5$

d6

 

 

1

$-1.62$

$-0.60$

$-0.44$

$-0.97$

$-0.70$

$-0.26$

 

 

2

$-0.46$

$-0.84$

$-0.30$

1.00

0.35

0.65

 
 

Рисунок 18.3 иллюстрирует документы в в двух измерениях. Отметим, что C2 является плотным относительно C.

Рис. 18.3: Документы из Примера 18.4, спроецированные в двумерном пространстве в .

 

В общем случае мы можем рассматривать низкоранговую аппроксимацию C к Ck как задачу ограниченной оптимизации: ограничением является то, что Ck имеет максимальный ранг k, мы ищем представление слов и документов, составляющих C с низкой нормой Фробениуса при допустимой погрешности (comprising $\lsimatrix$ with low Frobenius norm for the error $\lsimatrix-\lsimatrix_k$). При ужатии (forced to sqeeze) слов/документов в k-мерное пространство, сингулярное разложение сведёт вместе слова, встречающиеся в похожих случаях. Данная логика предполагает, что качество результатов не слишком пострадает от уменьшения мерности, но на деле может стать лучше.

 

Dumais (1993) и Dumais (1995) проводили эксперименты с LSI на документах и задачах TREC, используя широко применяемый алгоритм Ланцоша для вычисления сингулярного разложения. Во время их работы в ранние 90-е LSI-обработка десятков тысяч документов занимала примерно день на одной машине. В своих экспериментах они достигли точности аналогичной или более высокой среднего уровня участников TREC (median TREC participant). Примерно в 20% тем TREC их система имела наивысшую оценку, и чуть-чуть лучше средней, чем стандартные векторные пространства LSI в 350 измерениях. Вот некоторые выводы об LSI, первоначально сделанные из их работы, и после подтверждённые многими другими экспериментами.

  • Затраты на вычисление сингулярного разложения велики; на момент написания мы не знаем ни об одном успешном эксперименте с более чем одним миллионом документов. Это было самым большим препятствием для широкого внедрения LSI. Как способ решения, можно построить LSI-представление случайно выбранного подмножества документов в наборе, после чего остальные документы “вкладываются”, как описано в Формуле 244.

  • При уменьшении k уменьшается и отзывчивость (recall), что ожидаемо.

  • Что удивительно, значение k порядка ста может увеличить точность в некоторых тестах. Это предполагает, что при подходящем значении k LSI решает задачи синонимичности.

  • LSI лучше всего работает в случаях, где между запросами и документами малое пересечение.

 

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

LSI можно рассматривать в качестве мягкой кластеризации, принимая каждое измерение уменьшенного пространства за кластер, а значение, которое документ имеет на этом пространстве - за его частичное членство в этом кластере.

 

Это перевод. Оригинал: Latent semantic indexing

Автор перевода: Максим Евмещенко.

Ссылки по теме

Раздел: 
SEO