Эта статья была вдохновлена моим профессором Рэйчел Томас, и большая часть материала заимствована из ее курса по вычислительной линейной алгебре. Все ее уроки доступны на YouTube.
Я буду обновлять эту статью в течение нескольких недель по мере того, как буду получать лучшие результаты и обновления.
Почему именно СВД?
Разложение по сингулярным числам (SVD) - чрезвычайно полезный инструмент линейной алгебры, имеющий широкий спектр приложений.
- Машинное обучение: механизмы рекомендаций, уменьшение размерности, кластеризация и т. д.
- Статистика: уменьшение размерности , аппроксимация данных методом наименьших квадратов, многопараметрическое управление, аппроксимация матрицы.
- Обработка сигналов: СВД и обработка сигналов: алгоритмы, приложения и архитектуры
- Анализ главных компонентов: Какая интуитивная связь между SVD и PCA?
- квантовая информация: в форме, часто называемой разложением Шмидта.
- Совместная фильтрация, моделирование тем, удаление фона, удаление поврежденных данных: доступно на YouTube
- Сжатие данных и псевдо-обратное.
Математика, лежащая в основе SVD:
Для полного обзора линейной алгебры, лежащей в основе SVD, используйте главу книги Криса Мэннинга о матричной факторизации и LSI.
Почему рандомизированный SVD?
Короткий ответ - скорость. Хотя SVD дает нам чрезвычайно точные результаты по рассматриваемой проблеме, это требует больших вычислительных ресурсов. Для данной матрицы размерности M на N алгоритм SVD имеет следующую сложность:
При выборе или разработке алгоритма матричных вычислений следует учитывать четыре вещи:
- Использование памяти
- Скорость
- Точность
- Масштабируемость / распараллеливание
Если мы допустим некоторое снижение точности, то мы часто можем увеличить скорость на порядки (и / или уменьшить использование памяти), используя приблизительные алгоритмы. Эти алгоритмы обычно дают правильный ответ с некоторой вероятностью. Повторно запуская алгоритм несколько раз, вы, как правило, можете увеличить эту вероятность мультипликативно.
Нам редко требуется выполнять высокоточные вычисления матриц в большом масштабе. Фактически, мы часто используем машинное обучение, и менее точные подходы могут предотвратить переобучение.
Во многих случаях входные данные могут быть не такими точными, поэтому нет смысла стремиться к более высокому уровню точности наших расчетов, чем позволяют входные данные.
Пример сценария использования SVD: задан видеопоток изображений. Мы можем использовать SVD для выделения фона и переднего плана.
Нам нужно хранить только 15,3% данных, и мы можем сохранить точность до 1e-5! Замечательно!
Это моя первая попытка улучшить скорость нашего рандомизированного SVD.
Это было проверено на scikitlearn, fbpca, декомпозиция .randomsvd
Результаты:
Decomposition.randomsvd
Результаты не такие, как ожидалось, но есть луч света. Хотя похоже, что графический процессор не улучшает алгоритм быстрее, чем facebooks fbpca. Похоже, мы на правильном пути в отношении наших алгоритмов, поскольку randomized_svd (no cuda) очень хорошо идет в ногу со всеми другими, особенно с fbpca. Стабильность, конечно, является большой проблемой, которую мы должны рассмотреть, поэтому в следующем обновлении я буду делать сравнения стабильности, а также пытаюсь выяснить, почему графический процессор не увеличивает скорость нашего алгоритма.
Код можно найти здесь:
Https://github.com/smortezavi/Randomized_SVD_GPU/blob/master/pytorch_randomized_svd.ipynb
До следующего раза,
источники:
Https://nlp.stanford.edu/IR-book/pdf/18lsi.pdf
Https://arxiv.org/abs/1706.07191
Https://research.fb.com/fast-randomized-svd/
Https://en.wikipedia.org/wiki/Singular-value_decomposition
Https://math.stackexchange.com/questions/3869/what-is-the-intuitive-relationship-between-svd-and-pca
