Машинное обучение вики
Advertisement
Добавьте ссылок.png
Эта статья плохо повышает индекс цитируемости
авторов других статей этой вики.


Вы можете помочь, добавив навигационные ссылки.

О чем речь?[]

Пусть дана матрица . Пусть есть сингулярное разложение , где , , , где — множество ортогональных матриц соответствующей размерности (т. е. ), (ОБРАЩАЮ ВНИМАНИЕ: в отличие от лекций Китова неравенство с нулем СТРОГОЕ, потому что так правильнее, пруф), — транспонирование матрицы . Более подробно можно прочитать тут.

Пусть мы хотим построить низкоранговое приближение ранга для матрицы, то есть . Усечённое сингулярное разложение — такое, в котором отбросили часть меньших сингулярных чисел (и отбросили столбцы в ). Итак, усечённое сингулярное разложение порядка : , где .

Оптимальность с точки зрения нормы Фробениуса[]

Норма Фробениуса для матрицы : .

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

Todo.png

Докажем это. К сожалению, так вышло, что все, что я перенабирал, кануло в лету, сил у меня больше нет, и читатель отсылается сюда, страница 13, за разъяснениями (ОБРАТИТЕ ВНИМАНИЕ: в пункте 2.2 доказательства у Китова опечатка: неравенство противоположное (не , а )). Основная идея такова: с рангом все более-менее ясно:

(следует из того, что ранг произведения не превосходит ранга каждого из сомножителей, а также неравенства Фробениуса: ), мдауш; вторая часть базируется на связи SVD-разложения и PCA.

Выбор K[]

Пусть, как и прежде, матрица , где . Ее усечённое сингулярное разложение порядка представим в виде , где . Тогда ошибка аппроксимации записывается следующим образом: , где . Используя теорему о том, что (познакомиться с ней и ее доказательством поближе можно тут на страницах 16-18), легко получаем критерий выбора оптимального : выбирать нужно таким образом, чтобы относительная ошибка аппроксимации была меньше некоторого порога , т.е. .

Ссылки[]

Неплохое доказательство тут, страница 7

Лекции Китова, страница 11

Advertisement