SVD на низкоранговых-плюс-шифт матрицах

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

ата = низкоранговая матрица + набор идентичных матриц (3)

Или ата/m » uåvt + s2 in , где s – вариация шума.

Там же показано, что для модели лси матрица терм-документ приблизительно удовлетворяет этому условию.

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

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

Далее возникает вопрос: как обеспечить монотонность хвоста?

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

Существуют различные методы работы с такими матрицами.

Один из них - метод инкремента, где используются техники для разделения набора документов на несколько групп: начинаем с первой группы и считаем k-ранговый svd для нее, потом добавляем вторую группу, используя алгоритм обновления для получения новой k-ранговой аппроксимации; повторяем последовательность до конца.

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

Второй подход – разделяй-и-властвуй. Здесь коллекция документов сразу разделяется на несколько частей, для которых считается по отдельности k-ранговый svd, после чего результаты складываются. Однако для каждой выделенной группы мы можем выделить еще группы внутри нее и считать k-ранговый svd для них.

Таким образом, имеется несколько известных алгоритмов вычисления svd. Многие из них – разновидности алгоритма ланкоша [20]. Если известна структура матрицы, если она хороша – это дает большие преимущества в машинном времени для вычислений. Описанная структура позволяет экономить на процедурах обновления, которые проводятся быстрее при наличии у матриц такой структуры.

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

Далее, будет ли большая выгода от совмещения этого подхода для обновления матриц и каких-либо других подходов для обновления удалением, обработки запросов?

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

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