Итеративный масштабирующий SVD

И алгоритм svd, и данный алгоритм пытаются найти наименьший набор базисных векторов для пространства уменьшенной мерности. На входе данного метода [13] – терм-документная матрица. Из нее создаются базисные вектора для редуцированного пространства. Документные вектора с уменьшенной размерностью создаются из базисных векторов и терм-документной матрицы.

Пусть n – число документов и m – число термов. Вектора должны быть нормализованы по длине.

Отличие данного алгоритма от svd состоит в подходе к определению базисного вектора.

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

В этом методы аналогичны.

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

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

Матрица r инициализируется терм-документной матрицей. R-тые столбцы хранят информацию пока еще не представленную никаким базисным вектором (то есть эти столбцы – остаточные вектора). На каждой итерации каждый остаточный вектор масштабируется на размер своей собственной длины и первый собственный вектор (собственный вектор с i-тым наибольшим собственным значением есть i-тый собственный вектор) матрицы rs rst (где матрица rs – матрица масштабированных остаточных векторов) выбирается как следующий базисный вектор. В конце каждой итерации информация, полученная с помощью заново посчитанных базисных векторов вычитается из каждого остаточного вектора. Базисный вектор ортогонален, так как такое вычитание делает остаточные вектора перпендикулярными к предыдущим базисным векторам, и потому, что собственный вектор, вычисляемый следующим, есть линейная комбинация остаточных векторов.

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

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

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

В самом деле, данный метод весьма заманчив для обнаружения различий между малозначащими термами и «выбивающимися» документами, которые для svd неразличимы (вследствие симметричности).

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

Имеется интересная особенность: этот алгоритм приводит к потере ортогональности между правыми и левыми сингулярными векторами, находящимися в матрицах u и v соответственно, то есть к потере симметрии. В связи с этим, многие матричные операции, проводящиеся быстрее с условием ортогональности, будут неприменимы и придется использовать более общие медленные методы.

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

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

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