Метод SDD

Рассмотрим метод sdd (semi-discrete decomposition) – метод полудискретной декомпозиции.

В общем случае, при хранении, матрица а_k, получаемая в результате svd, может занимать больше места, чем исходная матрица а (это происходит в связи с тем, что а сильно разреженная). Естественно, что и обработка запросов требует большего времени. Чтобы не терять производительности, был предложен метод sdd [11].

Этот метод похож на svd. Матрица a_k также представляется в виде декартового произведения трех матриц, a_k = u_k å_k v_k^t , однако здесь m-ные вектора u_i и n-ные вектора v_i содержат значения из диапазона {-1,0,1}, скаляр s_i – любое положительное число. Матрицы u_k, å_k, v_k сформированы из этих векторов таким же образом, как и в методе svd.

В этом случае матрица a_k не так точно восстанавливает исходную матрицу а, зато число хранимых значений и скорость их обработки увеличиваются существенно. Уменьшается число бит, отводимое под каждое хранимое значение – естественно, хранить элементы, большинство из которых входят в диапазон {-1,0,1} гораздо проще, чем элементы из произвольного диапазона. В таблице 2 приведена сравнительная характеристика:

Таблица 2 - Сравнение методов SVD и SDD

Таким образом, при вычислении svd используются числа большой длины для того, чтобы обеспечить высокую точность результата и не потерять информации более, чем теряется. В методе sdd эти высокоточные числа заменяются особым образом на {-1,0,1}. Учитывая, что в неаппроксимированной матрице а содержится более чем достаточно информации, при полудискретной декомпозиции те слабые взаимосвязи, где роль играют сотые, тысячные доли будут утеряны. Это может оказаться полезным при наличии слишком большого шума, но может быть и наоборот. Безусловно, экономия во времени и пространстве есть, но нужно относиться к ней осторожно, так как имеется и потеря качества.

Что касается скорости, то при равном количестве измерений sdd показывает на порядок большую скорость и примерно 60% экономию места. В то же время, пик скорости у sdd по сравнению с svd приходится на мерность пространства порядка 120. Это неплохой результат, однако современные исследователи сходятся на том, что 120-ти измерений мало для оптимального представления модели. В данный момент лучшее число измерений колеблется около 300 для наиболее общих размеров корпусов текстов. Время же декомпозиции улучшается примерно на 25%.

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