Матричное приближение в потоке данных

Matrix approximation in data streaming

Приблизить матрицу, не имея все ее строки

Источник изображения: unsplash.com

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

Часть контента этой статьи взята из моей лекции в курсе “CS246” в Стэнфордском университете. Надеюсь, вы найдете это полезным. Полный контент можно найти здесь.

Данные как матрица

Большинство данных, созданных веб-сайтами, могут быть представлены в виде матрицы, где каждая строка матрицы является точкой данных. Например, в маршрутизаторах каждый пакет, отправленный по сети, является точкой данных, которая может быть представлена в виде строки в матрице всех точек данных. В розничной торговле каждая сделка – это строка в матрице всех операций.

Рисунок 1: Данные как матрица — Изображение автора

В то же время, почти все данные, создаваемые веб-сайтами, являются потоковыми; то есть данные создаются внешним источником со скоростью, которую мы не контролируем. Подумайте о поисковых запросах пользователей в поисковой системе Google каждую секунду. Мы называем эти данные потоковыми, потому что они поступают как поток.

Некоторые примеры типичных потоковых данных веб-масштаба:

Рисунок 2: Размер типичных потоковых данных веб-масштаба — Изображение автора

Представьте потоковые данные как матрицу A, содержащую n строк в пространстве размерности d, где обычно n >> d. Часто n имеет порядок миллиардов и растет.

Модель потоковых данных

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