Просмотр

Материал из MachineLearning.

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

== Неотрицательное матричное разложение == '''Неотрицательное матричное разложение''' — это метод приближённого представления неотрицательной матрицы в виде произведения двух неотрицательных матриц меньшего размера. Обычно задача записывается так: <tex> F\approx GU^T. </tex> Здесь <tex>F</tex> — исходная матрица данных, <tex>G</tex> и <tex>U</tex> — искомые матрицы меньшей размерности. Главное ограничение метода состоит в том, что все элементы матриц должны быть неотрицательными: <tex> f_{ij}\geq 0,\qquad g_{it}\geq 0,\qquad u_{jt}\geq 0. </tex> Из-за этого неотрицательное матричное разложение часто даёт более интерпретируемое представление данных, чем обычные матричные разложения. Объект описывается не через взаимную компенсацию положительных и отрицательных коэффициентов, а как сумма неотрицательных компонент. == Матричная постановка задачи == Пусть дана матрица <tex> F=(f_{ij})_{\ell\times n}. </tex> Строки этой матрицы соответствуют объектам, а столбцы — признакам. Например, объектами могут быть пользователи, документы, изображения или товары. Признаками могут быть покупки, слова, пиксели, оценки или другие измеряемые характеристики. Необходимо найти две матрицы: <tex> G=(g_{it})_{\ell\times m}, </tex> <tex> U=(u_{jt})_{n\times m}, </tex> где <tex> m\ll n. </tex> Матрица <tex>G</tex> задаёт новое описание объектов через <tex>m</tex> скрытых факторов. Матрица <tex>U</tex> показывает, как эти скрытые факторы связаны с исходными признаками. Приближённое восстановление исходной матрицы имеет вид: <tex> \widehat F=GU^T. </tex> Для отдельного элемента матрицы: <tex> \widehat f_{ij}=\sum_{t=1}^{m} g_{it}u_{jt}. </tex> Задача состоит в том, чтобы восстановленная матрица <tex>\widehat F</tex> была как можно ближе к исходной матрице <tex>F</tex>. == Критерий качества == Один из стандартных критериев качества — сумма квадратов ошибок восстановления: <tex> Q(G,U)=\|GU^T-F\|^2\to\min_{G,U}. </tex> С учётом неотрицательности задача записывается так: <tex> Q(G,U)=\|GU^T-F\|^2\to\min_{G,U}, \qquad G\geq 0,\quad U\geq 0. </tex> В развернутом виде: <tex> Q(G,U)= \sum_{i=1}^{\ell}\sum_{j=1}^{n} \left( \sum_{t=1}^{m}g_{it}u_{jt}-f_{ij} \right)^2 \to\min_{G,U}. </tex> Если в матрице известны не все элементы, то сумма берётся только по множеству наблюдаемых пар: <tex> \Omega\subseteq \{1,\ldots,\ell\}\times\{1,\ldots,n\}. </tex> Тогда критерий имеет вид: <tex> Q(G,U)= \sum_{(i,j)\in\Omega} \left( \sum_{t=1}^{m}g_{it}u_{jt}-f_{ij} \right)^2 \to\min_{G,U}. </tex> Такая постановка особенно важна в рекомендательных системах, потому что пользователь обычно оценивает или покупает только малую часть всех товаров. == Смысл скрытых факторов == Неотрицательное матричное разложение можно понимать как поиск скрытой структуры в данных. Каждый объект описывается не исходными признаками, а набором скрытых факторов: <tex> g_i=(g_{i1},\ldots,g_{im}). </tex> Каждый исходный признак также получает описание через эти факторы: <tex> u_j=(u_{j1},\ldots,u_{jm}). </tex> Если <tex>g_{it}</tex> велико, это означает, что объект <tex>i</tex> сильно связан с фактором <tex>t</tex>. Если <tex>u_{jt}</tex> велико, это означает, что признак <tex>j</tex> сильно связан с тем же фактором. Например, в рекомендательной системе скрытый фактор может соответствовать интересу к фантастике, спорту, технике или образовательному контенту. Эти факторы заранее не задаются вручную. Они находятся по данным. == Пример с рекомендательной системой == Пусть матрица <tex>F</tex> описывает взаимодействия пользователей с товарами. Элемент <tex> f_{ij} </tex> может означать: * оценку пользователя <tex>i</tex> товару <tex>j</tex>; * факт покупки; * лайк; * просмотр; * вероятность интереса к товару. Тогда строка матрицы <tex>G</tex> задаёт латентный вектор интересов пользователя: <tex> g_i=(g_{i1},\ldots,g_{im}). </tex> Строка матрицы <tex>U</tex> задаёт латентный вектор свойств товара: <tex> u_j=(u_{j1},\ldots,u_{jm}). </tex> Прогноз интереса пользователя <tex>i</tex> к товару <tex>j</tex> вычисляется как скалярное произведение этих векторов: <tex> \widehat f_{ij}=\sum_{t=1}^{m}g_{it}u_{jt}. </tex> Если значение <tex>\widehat f_{ij}</tex> большое, система может рекомендовать товар пользователю. == Отличие от метода главных компонент == Метод главных компонент также ищет низкоразмерное представление данных. В нём исходная матрица приближённо восстанавливается через произведение матриц: <tex> F\approx GU^T. </tex> Однако в методе главных компонент компоненты могут иметь как положительные, так и отрицательные значения. В неотрицательном матричном разложении вводится дополнительное ограничение: <tex> G\geq 0,\qquad U\geq 0. </tex> Из-за этого NMF обычно хуже подходит для точного ортогонального разложения, но лучше подходит для задач, где данные по смыслу неотрицательны и должны складываться из неотрицательных частей. Например, изображение можно рассматривать как сумму частей лица, документ — как смесь тем, а пользователя — как смесь интересов. == Интерпретируемость разложения == Главное достоинство неотрицательного разложения — интерпретируемость. Если разрешены отрицательные коэффициенты, то один фактор может увеличивать значение признака, другой уменьшать, и итог получается как результат компенсации. Это усложняет объяснение модели. В NMF используется только сложение неотрицательных вкладов: <tex> \widehat f_{ij}= g_{i1}u_{j1}+ g_{i2}u_{j2}+ \ldots+ g_{im}u_{jm}. </tex> Поэтому каждый фактор можно понимать как отдельную часть объекта. Например: * изображение лица может раскладываться на глаза, нос, рот и контуры; * текстовый документ — на темы; * музыкальные предпочтения — на жанры; * поведение пользователя — на группы интересов. Такое объяснение не всегда идеально, но оно часто понятнее, чем абстрактные ортогональные компоненты. == Метод чередующихся наименьших квадратов == Одним из способов решения задачи NMF является метод чередующихся наименьших квадратов. Идея состоит в том, чтобы по очереди оптимизировать одну из матриц, считая другую фиксированной. Сначала фиксируется <tex>U</tex> и ищется <tex>G</tex>. Затем фиксируется <tex>G</tex> и ищется <tex>U</tex>. Эти шаги повторяются много раз: <tex> G\to U\to G\to U\to\ldots </tex> Такой подход не гарантирует нахождение глобального минимума, потому что задача NMF в общем случае невыпуклая. Однако на практике он часто даёт полезное приближённое решение. == Покомпонентная идея ALS == Пусть разложение записано как сумма ранговых компонент: <tex> GU^T=\sum_{t=1}^{m}g_tu_t^T. </tex> Здесь <tex>g_t</tex> и <tex>u_t</tex> — столбцы матриц <tex>G</tex> и <tex>U</tex>. Для обновления одной компоненты можно временно исключить её из суммы и рассмотреть остаточную матрицу: <tex> F_t=F-\sum_{s\neq t}g_su_s^T. </tex> Тогда задача для одной компоненты имеет вид: <tex> \|g_tu_t^T-F_t\|^2\to\min. </tex> При фиксированном <tex>u_t</tex> обновление <tex>g_t</tex> можно записать так: <tex> g_t= \left( \frac{F_tu_t}{u_t^Tu_t} \right)_+. </tex> При фиксированном <tex>g_t</tex> обновление <tex>u_t</tex> имеет вид: <tex> u_t= \left( \frac{F_t^Tg_t}{g_t^Tg_t} \right)_+. </tex> Обозначение <tex>(z)_+</tex> означает положительную срезку: <tex> (z)_+=\max(z,0). </tex> Она нужна для выполнения условия неотрицательности. == Разреженные данные == Во многих реальных задачах матрица <tex>F</tex> является разреженной. Это означает, что большая часть её элементов неизвестна или равна нулю. Например, в рекомендательной системе пользователь видит только небольшую часть товаров. Поэтому матрица оценок пользователей почти всегда заполнена не полностью. Если известные элементы задаются множеством <tex>\Omega</tex>, то обучать модель нужно только по ним: <tex> (i,j)\in\Omega. </tex> Такой подход позволяет не требовать полной матрицы данных и одновременно восстанавливать пропущенные значения. После обучения можно вычислить прогноз для неизвестной пары <tex>(i,j)</tex>: <tex> \widehat f_{ij}=\sum_{t=1}^{m}g_{it}u_{jt}. </tex> Именно это делает матричные разложения полезными для рекомендаций. == Регуляризация == В прикладных задачах модель может переобучаться. Это означает, что она хорошо восстанавливает известные элементы матрицы, но плохо предсказывает неизвестные. Для борьбы с переобучением добавляют регуляризацию: <tex> Q(G,U)= \sum_{(i,j)\in\Omega} \left( \sum_{t=1}^{m}g_{it}u_{jt}-f_{ij} \right)^2 + \lambda\|G\|^2+ \mu\|U\|^2 \to\min. </tex> Параметры <tex>\lambda</tex> и <tex>\mu</tex> управляют силой регуляризации. Если они слишком малы, модель может переобучиться. Если они слишком велики, модель станет слишком грубой и не сможет хорошо описать данные. == Выбор числа факторов == Число факторов <tex>m</tex> — важный параметр модели. Если <tex>m</tex> слишком мало, модель не сможет описать сложную структуру данных. Если <tex>m</tex> слишком велико, модель может начать запоминать шум и случайные особенности обучающей выборки. Обычно <tex>m</tex> выбирают по качеству на отложенной выборке. В рекомендательной системе можно скрыть часть известных оценок, обучить модель на остальных и проверить, насколько хорошо она предсказывает скрытые значения. == Применения == Неотрицательное матричное разложение применяется в задачах, где данные естественно неотрицательны. Основные примеры: * рекомендательные системы; * тематическое моделирование текстов; * обработка изображений; * анализ звуковых сигналов; * биоинформатика; * выделение скрытых факторов в таблицах данных; * восстановление пропущенных значений. В текстах матрица <tex>F</tex> может содержать частоты слов в документах. Тогда скрытые факторы можно интерпретировать как темы. В изображениях матрица может содержать яркости пикселей. Тогда скрытые факторы могут соответствовать частям изображения. В рекомендациях матрица содержит действия пользователей. Тогда скрытые факторы описывают интересы пользователей и свойства товаров. == Преимущества метода == К преимуществам NMF относятся: * снижение размерности данных; * возможность работать с неотрицательными признаками; * интерпретируемость скрытых факторов; * применимость к разреженным матрицам; * возможность восстанавливать пропущенные значения; * связь с рекомендательными системами и тематическим моделированием. == Ограничения метода == У метода есть и ограничения. Во-первых, задача NMF обычно невыпуклая. Поэтому разные начальные приближения могут приводить к разным решениям. Во-вторых, результат зависит от выбора числа факторов <tex>m</tex>. В-третьих, неотрицательность полезна не для всех данных. Если признаки по смыслу могут быть отрицательными, обычные методы вроде PCA или SVD могут быть более естественными. В-четвёртых, интерпретируемость факторов не гарантируется автоматически. Иногда факторы действительно соответствуют понятным темам или группам признаков, а иногда их смысл приходится дополнительно анализировать. == Связь с обучаемой векторизацией == NMF можно рассматривать как один из способов обучаемой векторизации данных. Исходный объект сначала задан длинным вектором признаков: <tex> x_i=(f_{i1},\ldots,f_{in}). </tex> После разложения он получает более короткое представление: <tex> g_i=(g_{i1},\ldots,g_{im}). </tex> Если <tex> m\ll n, </tex> то новое представление компактнее исходного. Такое представление можно использовать для дальнейших задач: классификации, кластеризации, поиска похожих объектов или рекомендаций. == Вывод == Неотрицательное матричное разложение — это метод поиска скрытых факторов в неотрицательных данных. Его основная идея состоит в приближении исходной матрицы произведением двух неотрицательных матриц: <tex> F\approx GU^T. </tex> Метод полезен тогда, когда данные можно понимать как сумму неотрицательных частей. Поэтому NMF применяется в рекомендательных системах, обработке текстов, изображений и других задачах анализа данных. Главное преимущество NMF — более понятная интерпретация факторов по сравнению с разложениями, где разрешены отрицательные коэффициенты. Главное ограничение — сложность оптимизации и зависимость результата от выбора числа факторов и начального приближения. == Литература == * D. D. Lee, H. S. Seung. Learning the parts of objects by non-negative matrix factorization // Nature, 1999. * A. Cichocki, R. Zdunek, S. Amari. Hierarchical ALS algorithms for nonnegative matrix and 3D tensor factorization, 2007. * G. Takacs, I. Pilaszy, B. Nemeth, D. Tikk. Scalable collaborative filtering approaches for large recommendation systems // JMLR, 2009. * К. В. Воронцов. Обучаемая векторизация данных. Лекция курса «Философия. Введение в ИИ», 2026.

Возврат к странице Неотрицательное матричное разложение.