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

Еще один класс моделей направлен на формирование представлений текстов с помощью латентных (скрытых) тематик коллекции. Формирование таких представлений осуществляется путем факторизации матрицы «документы-на-термины»¹.

Наиболее популярным методом факторизации является сингулярное разложение, представляющее произвольную числовую матрицу А размерности т? п (т > п) в виде произведения трех матриц^[1][2] (рис. 9.2):

где U и V — ортогональные матрицы размерностей т? п и п • п соответственно (столбцы этих матриц называют левыми и правыми сингулярными векторами), 5 — диагональная матрица размерности т? п (ее диагональные элементы называют сингулярными числами).

Рис. 9.2. Сингулярное разложение произвольной матрицы.

Согласно теореме Эккарта — Янга, сингулярное разложение позволяет снизить шум и разреженность исходной матрицы, заменяя ее матрицей той же размерности, но меньшего ранга, в которой сохранена только самая значимая информация^[3]. Более формально эта теорема звучит следующим образом.

Пусть дана матрица А размерности т? п, для которой известно сингулярное разложение А = IJSV^Т и которую требуется аппроксимировать матрицей А_к с заданным рангом k Если в матрице S оставить k наибольших сингулярных значений, а остальные заменить нулями, то разложение.

даст наилучшее приближение исходной матрицы А ранга k в смысле нормы Фробениуса.

Если при этом элементы матрицы 5 отсортированы по убыванию Sj > s₂ > s_n > 0, то формула (9.1) может быть записана в другой форме:

где U_k и V_k — это матрицы, полученные выделением первых к столбцов из матриц U и V соответственно (рис. 9.3).

Рис. 9.3. Экономная форма сингулярного разложения.

Таким образом, в латентной семантической модели каждый текст и каждый термин могут быть представлены при помощи векторов в редуцированном пространстве размерности к — пространстве тематик (рис. 9.4).

Рис. 9.4. Латентный семантический анализ.

Сингулярное разложение, представленное равенством (9.2), называется экономным, поскольку в случае, когда к намного меньше, чем т и п, оно позволяет произвести существенное сжатие исходной информации. Сжатие понимается в том смысле, что часть информации, передаваемой исходной матрицей, теряется, а сохраняется только самая важная (доминантная) информация. Коэффициент сжатия исходной информации нетрудно определить исходя из следующих соображений. Для хранения исходной матрицы требуется т • п чисел, а для сжатой матрицы m-k + k-k + + k • п чисел. Таким образом, коэффициент сжатия равен:

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

С прагматической точки зрения данный вывод очень полезен. В частности, если исходная матрица содержит большое количество «слабых» значений, то потеря или уменьшение этих значений скорее пойдут во благо, чем во вред, поскольку таким способом будет произведено очищение матрицы от информационного шума. Именно эта идея и сформировала идейный базис метода латентного семантического анализа {latent semantic analysis — LCA), предназначенного для выявления скрытых (глубинных) семантических связей, существующих в коллекции текстов^[4] [36].

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

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

где 7j, Tj — это вектор-столбцы матрицы «документы-на-термины», соответствующие i-му и j-му терминам соответственно (/ и j пробегают весь список терминов), — это значение близости, элемент матрицы семантических связей (рис. 9.5).

Рис. 9.5. Переход от матрицы «документы-на-термины» к матрице семантических связей «термины-на-термины».

Определение косинуса в первом квадранте декартовых координат позволяет утверждать, что максимально возможное значение близости между терминами равно 1, а минимально возможное — 0.

Другим способом факторизации (разложения) исходной матрицы «документы-на-термины» является неотрицательная матричная факторизация {nonnegative matrix factorization — NMF)^[5]. В этой модели вместо сингулярного разложения используется разложение матрицы в произведение двух неотрицательных матриц: «документы-на-тематики» и «тематики-на-термины» (рис. 9.6).

Рис. 9.6. Неотрицательная матричная факторизация.

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

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

Запустите R. Создайте новый скрипт. Установите пакеты Isa и igraph с помощью команды install. packages (с («Isa», «igraph»)) и подключите их. Создайте матрицу буквы Е. Выведите ее изображение на экран.

library (Isa).

library (igraph) е <- matrix (с.

• (1, 1, 1, 1, 1, 1, 1,
• 1, О, О, 1, О, О, 1,
• 1, О, О, 1, О, О, 1,
• 1, О, О, 1, О, О, 1,
• 1, О, О, О, О, О, 1), 7, 5)

image (t (е), axes = FALSE, col = grey (seq (1, 0, length = 256))).

Puc. 9.7. Растровое изображение буквы E и се матрица Выполните сингулярное разложение матрицы. Просмотрите получившиеся матрицы. У вас должны получиться матрицы, символически изображенные на рис. 9.8 (произведено округление до двух знаков).

г <- svd (e) s <- diag (r$d) s.

u <- r$u u.

v <- r$v t (v).

Puc. 9.8. Сингулярное разложение матрицы, соответствующей изображению буквы Е Из сингулярного разложения следует, что сжатие информации без какой-либо потери возможно при k > 3, так как у данной матрицы существует всего три ненулевых сингулярных значения: 3,81, 1,70, 0,76. Чтобы убедиться в этом, можно просто перемножить три матрицы, обрезав (редуцировав) каждую из них сначала с глубиной к = 3, затем к = 2 и, наконец, к = 1. Запустите скрипт, показанный ниже, и проанализируйте три изображения буквы Е, полученные в результате редукции.

reduce <-function (u, s, v, k).

(.

us <- as. matrix (u [, 1: k]) vs <- as. matrix (v [, 1: k]) ss <- as. matrix (s [1: k, 1: k]) return (us %*% ss%*% t (vs)).

}.

e3<-reduce (u, s, v, 3).

e3.

image (t (e3), axes = FALSE, col = grey (seq (1, 0,.

length = 256))) e2<-reduce (u, s, v, 2).

e2.

image (t (e2), axes = FALSE, col = grey (seq (1, 0,.

length = 256))) el<-reduce (u, s, v, l).

el.

image (t (el), axes = FALSE, col = grey (seq (1, 0,.

length = 256))).

При к = 3 имеем e₃ = u₃s₃v⁷₃ = e. У вас должна получиться матрица e_:i, символически представленная на рис. 9.9 (произведено округление до двух знаков). Потеря информации, если не считать погрешности вычислений, отсутствует.

Рис. 9.9. Аппроксимация исходной матрицы изображения матрицей ранга к = 3.

А вот при значениях к < 3 (особенно при k = 1) уже наблюдается существенная потеря информации. Сравните рис. 9.10 и 9.11 (произведено округление до двух знаков).

Это хорошо заметно и по самим изображениям буквы, построенным на основе приближенных матриц е₃, е₂, ер при к = 3 потери качества нет, при k = 2 качество изображения несколько хуже, но букву можно распознать, при k = 2 букву распознать практически невозможно (рис. 9.12). Таким образом, как и отмечалось выше, замена исходной матрицы приближенной матрицей меньшего ранга позволяет сократить количество хранимой информации, но при этом часть информации теряется. То, насколько критична потеря части информации, определяется условиями конкретной задачи.

Рис. 9.10. Аппроксимация исходной матрицы изображения матрицей ранга k = 2.

Рис. 9.11. Аппроксимация исходной матрицы изображения матрицей ранга k = 1.

Рис. 9.12. Постепенная потеря качества изображения при уменьшении k.

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

Анализ матриц е₃, е₂, е_{ позволяет выделить в качестве доминантных сигналов элементы [1,1], [4,1], [7,1]. При первой аппроксимации значения этих элементов были равны 1, а при последней аппроксимации увеличились. Данный факт легко поддается геометрической интерпретации: указанные элементы матрицы являются системообразующими в изображении буквы Е, так как представляют собой точки пересечения образующих эту букву линий.

Теперь мы проиллюстрируем, как работает метод латентного семантического анализа на коллекции текстов. Откройте скрипт, созданный ранее при обработке коллекции текстов про Китай и Японию. Включите библиотеку Isa. Выполните ту часть команд, которая формирует корпус документов, очищает его от стоп-слов, пунктуационных знаков, чисел, преобразует символы в нижний регистр и формирует матрицу «документы-на-термины», состоящую из 6 документов и 55 слов.

Для анализа, который мы хотим выполнить в данном примере, нам не потребуются все 55 слов. Мы будем оперировать только следующими словами-геонимами: China, Beijing, Shanghai, Масаи, Tokyo, Japan, Yokohama. Поэтому из полной матрицы «документына-термины» нужно выделить ее фрагмент, ограниченный соответствующими столбцами (табл. 9.7).

geonyms <-с («china» ," beijing" ," shanghai" ," macau" ," to.

kyo", «japan» ," yokohama").

dtm<-dtm [, geonyms].

a<-as.matrix (dtm).

a.

Таблица 9.7

Матрица «документы-на-термины», составленная из терминов-геонимов.

Теперь можно определить семантические связи между терминами, т. е. от матрицы «документы-на-термины» перейти к матрице «термины-на-термины». Для такого перехода нужно рассчитать косинусную меру между всеми столбцами матрицы «документына-термины» и сформировать из полученных значений новую матрицу «термины-на-термины» (табл. 9.8). Можно обнулить в полученной матрице слабые семантические связи, т. е. те элементы, значения которых меньше 0,5.

relations C-cosine (a) relations.

relations [ relations< = 0.5 ] <- 0.

Таблица 9.8

Матрица семантических связей «термины-на-термины».

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

Рис. 9.13. Граф семантических связей между терминами.

Из рис. 9.13 видно, что семантически связной оказалась только группа японских геонимов Yokohama, Japan, Tokyo и примкнувший к ним китайский геоним China. Однако ясно, что существует еще одна связная группа терминов (китайских), но эти связи плохо выражены (скрыты). Чтобы породить более мощную матрицу связей и выделить скрытые (латентные) семантические связи, нужно вместо исходной матрицы «документы-на-термины» использовать ее сжатый образ, полученный с помощью сингулярного разложения. Будем формировать сжатый образ на основе первых двух сингулярных чисел, т. е. с глубиной 2. Затем нужно снова перейти от полученной сжатой матрицы к матрице «термины-на-термины», обнулить слабые связи и визуализировать граф (рис. 9.14).

г <- svd (a) s <- diag (r$d) u <- r$u v <- r$v s.

reduce <-function (u, s, v, k).

{.

us <- as. matrix (u [, 1: k]).

vs <- as. matrix (v [, 1: k]).

ss <- as. matrix (s [1: k, 1: k]).

return (us %*% ss%*% t (vs)).

}.

a2<-reduce (u, s, v, 2) colnames (a2) <-geonyms.

relations2 <-cosine (a2) relations2 [relations3<=0.5] <- 0.

relations2.

net2=graph.adjacency (adjmatrix=relations2, mode= «undirected», weighted = TRUE, diag = FALSE) plot (net2, vertex. size = 12, vertex.label.dist = 1, vertex.label.degree = 0, edge.arrow.size = 0).

Сравнение двух графов семантических связей на рисунках 9.13 и 9.14 позволяет говорить о большей информативности второго графа, который получен в результате аппроксимации с параметром k = 3. Второй граф содержит больше связей, и эти связи очевидны: как мы видим, все китайские термины объединились в один подграф, а японские термины — в другой. Таким образом, новая матрица связей получилась более мощной, и она теперь отображает все связи коллекции — и явные, и скрытые (латентные).

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

• [1] См.: Indexing by Latent Semantic Analysis / S. C. Deerwester, S. T. Dumais, T. K. Landauer [et al.] // JAsIs. 1990. № 6 (41); Xu IF., Liu X., Gong Y. DocumentClustering Based on Non-Negative Matrix Factorization // Proceedings of the 26thAnnual International ACM SIGIR Conference on Research and Development inInformation Retrieval. Toronto: ACM, 2003.
• [2] Cm.: Eckart C., Young G. The Approximation of One Matrix by Another of LowerRank // Psychometrika. 1936. № 3(1).
• [3] См.: Eckart С., Young G. The Approximation of One Matrix by Another of LowerRank.
• [4] См.: Indexing by Latent Semantic Analysis / S. C. Deerwester, S. T. Dumais, T. K. Landauer [ct al.].
• [5] Xu W. t Liu X., Gong Y. Document Clustering Based on Non-Negative MatrixFactorization.