Пополнение матрицы (Matrix Completion)
- Автор метода
- Emmanuel Candès & Benjamin Recht
- Год
- 2009
- Тип
- Convex low-rank recovery
- Семейство
- Missing data
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Пополнение матрицы — это метод восстановления низкоранговой матрицы по малой, возможно, случайной подвыборке её элементов.
Предложенный Эммануэлем Кандосом и Бенджамином Рехтом в 2009 году, он переформулирует задачу как минимизацию ядерной нормы — выпуклой суррогатной функции для минимизации ранга — и предоставляет теоретические гарантии того, что точное восстановление достижимо, когда элементы наблюдаются равномерно случайным образом, а матрица удовлетворяет условию некогерентности.
Интуиция метода
Представьте себе частично заполненную таблицу рейтингов пользователей и фильмов, где большинство ячеек пусты. Если исходные данные имеют простую структуру — скажем, вкусы объясняются всего несколькими латентными факторами, такими как предпочтение жанра и эпохи, — то знание даже малой доли рейтингов достаточно, чтобы с уверенностью заполнить остальные. Пополнение матрицы использует эту скрытую низкоразмерную структуру, подобно сборке пазла, когда вы знаете, что на картинке всего несколько различных форм.
История
Пополнение матрицы возникло из литературы по сжатому зондированию. Кандос и Рехт (2009) установили первую теорему о точном восстановлении с помощью минимизации ядерной нормы, за которой последовала работа Кандоса и Тао о силе некогерентности. Метод получил широкое общественное внимание благодаря конкурсу Netflix Prize, где низкоранговые методы коллаборативной фильтрации достигли наилучшей точности рекомендаций. Последующая работа Рехта, Фазеля и Паррилло связала минимизацию ядерной нормы с регуляризацией нормы следа в машинном обучении.
Когда применять
Используйте пополнение матрицы, когда данные могут быть организованы как матрица с систематически отсутствующими элементами, и есть основания полагать, что истинный сигнал имеет низкий ранг — например, в рекомендательных системах, геномике, анализе социальных сетей и восстановлении изображений. Ключевые предположения: элементы отсутствуют случайным образом, и матрица удовлетворяет условию некогерентности. Метод не подходит для матриц со структурированной или неслучайной пропущенностью, очень высокой ранговой структурой или когда предположение о низком ранге необоснованно. Альтернативы включают импутацию MICE для общих пропущенных данных и NMF, когда требуется неотрицательность.
Ограничения и замечания
- Вычислительная стоимость полудефинитного программирования плохо масштабируется с размерностью матрицы
- Предположение о некогерентности может не выполняться на реальных наборах данных со структурированной пропущенностью или выбросами
- Качество восстановления снижается, когда истинный ранг не намного меньше размерности матрицы
- Минимизация ядерной нормы может быть чувствительна к шуму; робастные варианты добавляют дополнительную сложность
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Доказуемое точное восстановление при мягких условиях с помощью выпуклой программы полиномиального времени
- Обрабатывает очень высокие уровни пропущенности, когда матрица действительно низкоранговая
- Предварительное знание ранга не требуется; минимизация ядерной нормы неявно находит его
- Сильные теоретические гарантии, основанные на теории случайных матриц и выпуклом анализе
Применение
- Коллаборативная фильтрация и рекомендательные системы (прогнозирование рейтингов пользователь-элемент)
- Геномика и биоинформатика (восстановление матриц экспрессии генов с пропущенными измерениями)
- Компьютерное зрение (восстановление (inpainting) изображений и вычитание фона видео)
- Локализация сенсорных сетей (восстановление матриц положений по частичным измерениям расстояний)
- Нейронаука (пополнение матриц функциональной связности по частичным наблюдениям fMRI)
Как это работает
Как это работает
Алгоритм начинается с матрицы M, элементы которой наблюдаются только на индексном множестве Omega. Эти наблюдаемые значения формируют ограничения для задачи восстановления. Предполагается, что шаблон разреженности выборки является равномерно случайным, что является теоретической установкой, в которой устанавливаются гарантии точного восстановления.
Формула
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}Поскольку прямая минимизация ранга матрицы является NP-трудной задачей, Кандос и Рехт предлагают минимизировать ядерную норму — сумму сингулярных значений — как выпуклую релаксацию. Ядерная норма играет ту же роль для матриц, что и L1-норма для векторов в сжатом зондировании: она способствует низкоранговым решениям, сохраняя при этом решаемость задачи с помощью полудефинитного программирования.
Формула
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\OmegaДля возможности восстановления сингулярные векторы истинной матрицы не должны быть слишком выровнены со стандартным базисом, что количественно определяется параметром некогерентности mu. Матрицы, концентрирующие свою энергию в небольшом количестве строк или столбцов, являются некогерентными; сильно локализованные матрицы нарушают это условие и не могут быть восстановлены из случайной выборки, поскольку слишком много информации закодировано в ненаблюдаемых элементах.
Формула
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}Когда количество наблюдаемых элементов превышает порог, пропорциональный mu, умноженному на ранг r и n log n, минимизатор задачи ядерной нормы с высокой вероятностью восстанавливает истинную матрицу точно. Этот результат показывает, что требуемый размер выборки лишь полилогарифмически больше внутренних степеней свободы матрицы ранга r, что делает подход информационно-теоретически почти оптимальным.
Формула
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}Частые ошибки
- Предположение о равномерной случайной пропущенности, когда реальные наблюдения выбраны пользователем или смещены (например, оцениваются только высоко оцененные элементы), что нарушает теоретическую модель выборки
- Игнорирование проверки условия некогерентности, что приводит к плохому восстановлению даже при достаточном количестве наблюдений
- Использование минимизации ядерной нормы без масштабирования или регуляризации в зашумленной среде, где формулировка точного восстановления неуместна
- Смешение пополнения матрицы с эвристиками матричной факторизации: чередующиеся наименьшие квадраты могут сходиться к локальным минимумам и не имеют гарантий восстановления, как минимизация ядерной нормы
Часто задаваемые вопросы
Является ли минимизация ядерной нормы единственным способом решения задачи пополнения матрицы?
Нет. Чередующиеся наименьшие квадраты (ALS) и градиентный спуск на факторизованных формах (например, SGD на U и V таких, что M ≈ UV^T) широко используются на практике для масштабируемости. Однако эти невыпуклые подходы не имеют гарантий точного восстановления, как минимизация ядерной нормы, и могут сходиться к локальным минимумам при отсутствии тщательной инициализации.
Сколько данных необходимо для точного восстановления?
Кандос и Рехт показали, что примерно C·mu·r·n·log(n) наблюдаемых элементов достаточно для n×n матрицы ранга r с параметром некогерентности mu. На практике это означает, что низкоранговая матрица часто может быть восстановлена по выборке, которая лишь в небольшое число раз превышает её внутренние степени свободы, равные r(2n−r) для n×n матрицы.
Что такое условие некогерентности и почему оно важно?
Некогерентность измеряет, насколько сингулярные векторы распределены по координатному базису. Матрица с концентрированными сингулярными векторами — например, матрица ранга 1, ненулевая только в одной строке — хранит большую часть своей информации в небольшом наборе элементов. Если эти элементы окажутся ненаблюдаемыми, восстановление будет невозможно, независимо от того, сколько других элементов известно.
Похожие методы
Источники
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.
Открыть ссылку DOIСкопировано.