Прост итеративен алгоритъм за разлагане на сингулярна стойност
Материал от MachineLearning.
Прост итеративен алгоритъм за разлагане на матрици по сингулярна стойностпозволява проста силно паралелна (включително невронна мрежа) реализация. Разлагането на сингулярни стойности на матрици е необходимо за решаване на много проблеми на анализа на данни. По-специално, анализът на главните компоненти се свежда до декомпозиция на сингулярна стойност на матрица от центрирани данни.
Съдържание
Идеята за декомпозиция на сингулярна стойност на матрица с данни
Ако е матрица, съставена от редови вектори от центрирани данни, тогава примерната ковариационна матрица и проблемът за спектралното разлагане на ковариационната матрица се превръщат в проблем заединичното разлаганена матрицата с данни.
Едно число се наричаединично числона матрица, ако и само ако имадесен и ляв сингулярни вектори: такъв -мерен редов вектор и -мерен колонен вектор (и двата с единична дължина), за които са валидни две равенства:
Нека е рангът на матрицата с данни.Разлагане на сингулярна стойностна матрица с данни е нейното представяне във формата
където 0" alt= "\sigma_l > 0" /> е сингулярна стойност, е съответният десен сингулярен вектор на колона и е съответният ляв сингулярен вектор на ред ( ). Дясните сингулярни вектори на колона, участващи в това разширение, са основните компонентни вектори и собствени вектори на емпиричната ковариационна матрица, съответстваща на положителни собствени стойности 0 " alt= " \lambda_l=\frac\sigma_l^ 2 > ; 0 "/>.
Въпреки че формално проблемите на сингулярното разлагане на матрицата с данни и спектралното разлагане на ковариационната матрица съвпадат, алгоритмите за директно изчисляване на сингулярната стойност, без изчисляване на спектъра на ковариационната матрица, са по-ефективни и стабилни [1] . Това следва отче проблемът с разлагането на матрица с сингулярна стойност е по-добре обусловен от проблема с разлагането на матрица: за ненулеви собствени стойности и сингулярни стойности
Теорията на сингулярната стойност е създадена от J. J. Sylvester през 1889 г. и е представена във всички подробни ръководства по теория на матриците [1] .
Прост итеративен алгоритъм за разлагане на сингулярна стойност
Основната процедура е да се намери най-доброто приближение на произволна матрица чрез матрица от формата (където е -мерен вектор и е -мерен вектор) чрез метода на най-малките квадрати:
Решението на този проблем се дава чрез последователни итерации, използващи изрични формули. За фиксиран вектор стойностите, които осигуряват минимума на формуляра, се определят еднозначно и изрично от равенствата:
По същия начин за фиксиран вектор се определят следните стойности:
Като първоначално приближение на вектора вземаме случаен вектор с единична дължина, изчисляваме вектора , след това изчисляваме вектора за този вектор и т.н. Всяка стъпка намалява стойността на . Малката стойност на относителното намаление на стойността на минимизирания функционал за стъпка на итерация ( ) или малката стойност на самата стойност се използва като критерий за спиране.
В резултат на това матрицата беше най-добре апроксимирана от матрица на формата (тук горният индекс обозначава номера на итерацията). Освен това изваждаме получената матрица от матрицата и за получената матрица на отклонение отново търсим най-доброто приближение от същия тип и така нататък, докато например нормата стане достатъчно малка. В резултат на това получихме итеративна процедура за разлагане на матрица като сума от матрици от ранг 1, т.е. Ние приемаме и нормализираме векторите: В резултат на това се получава приближение на сингулярни числа и сингулярни вектори (дясно - и ляво -).
Предимствата на този алгоритъм включват неговата изключителна простота испособността да се прехвърлят почти непроменени към данни с пропуски [1], както и претеглени данни.
Има различни модификации на основния алгоритъм, които подобряват точността и стабилността. Например, векторите на главните компоненти за различни трябва да бъдат ортогонални „по конструкция“, но с голям брой итерации (голям размер, много компоненти) се натрупват малки отклонения от ортогоналността и може да се наложи специална корекция на всяка стъпка, осигуряваща нейната ортогоналност спрямо предварително откритите главни компоненти.
За квадратни симетрични положително-определени матрици описаният алгоритъм се превръща в директен итерационен метод за намиране на собствени вектори.
Сингулярно разлагане на тензори и метод на главната компонента на тензора
Често векторът на данни има допълнителната структура на правоъгълна таблица (например плоско изображение) или дори многомерна таблица - тоест тензор: , . В този случай също така е ефективно да се използва разлагането на сингулярна стойност. Дефиницията, основните формули и алгоритми се прехвърлят практически без промени: вместо матрица с данни имаме стойност на индекс, където първият индекс е номерът на точката от данни (тензор).
Основната процедура е да се намери най-доброто приближение на тензора чрез тензор от формата (където - -дименсионален вектор ( - брой точки от данни), - дименсионен вектор при 0" alt = "l>0" />) по метода на най-малките квадрати:
Решението на този проблем се дава чрез последователни итерации, използващи изрични формули. Ако всички факторни вектори са дадени с изключение на един, тогава този останал се определя изрично от достатъчни минимални условия.
Като първоначално приближение на векторите ( 0" alt= "l>0" />), вземаме произволни вектори с единична дължина, изчисляваме вектора, след това изчисляваме вектора за този вектор и тези вектори и т.н.(цикъл през индекси) Всяка стъпка намалява стойността на . Алгоритъмът очевидно се сближава. Малката стойност на относителното намаление на стойността на функционала, който трябва да бъде минимизиран за цикъл, или малката стойност на самата стойност се използва като критерий за спиране. Освен това изваждаме полученото приближение от тензора и за остатъка отново търсим най-доброто приближение от същия тип и така нататък, докато например нормата на следващия остатък стане достатъчно малка.