Розклад невід'ємних матриць

Шаблон:Машинне навчання Розклад невід'ємних матриць (NMF(Non-negative matrix factorization)) це група алгоритмів багатовимірного аналізу та лінійної алгебри, де матриця V розкладається в, зазвичай, дві матриці W, H, враховуючи, що жодна з трьох матриць немає від'ємних елементів. Завдяки невід'ємності результуючі матриці легко перевіряються. Крім того, в таких програмах, як обробка аудіо спектрограм даним притаманна ця невід'ємність. Так як проблема немає точних розв'язків, в загальному випадку, зазвичай, знаходять числове наближення.

V=W*H

NMF застосовується в таких областях, як машинне бачення, кластеризація документів, хемометрика, обробка аудіо сигналів і рекомендаційні системи.

Історія

У хемометриці розклад невід'ємних матриць має довгу історію під назвою «крива самостійного моделювання».У рамках цього фреймворку вектори у правій матриці представляють неперервні криві, а не дискретні вектори. Також ранню роботу з розкладу невід'ємних матриць проводила група фінських вчених в середині 1990-х, під назвою «позитивної матричної факторизації». Він став широко відомим як факторизація невід'ємних матриць після того, як Лі і Сунг дослідили властивості алгоритму і опублікували кілька простих і корисних алгоритмів для двох типів факторизацій(множників).

Теорія

Нехай матриця V є добутком матриці W і H

$𝐕=𝐖𝐇.$

Множення матриць може бути реалізоване як обчислення вектор-стовпчиків матриці V,у вигляді лінійної комбінації вектор-стовпчиків матриці W використовуючи коефіцієнти, що відповідають векторам-рядкам матриці H.Тобто, кожен стовпець V може бути обчислено таким чином:

${𝐯}_i=𝐖{𝐡}_i,$

де v_i — і-ий вектор-стовпчик матриці V, a h_i — і-ий вектор-стовпчик матриці H.

При множенні матриць, розміри матриць-множників можуть бути значно меншими від розмірів матриці-результата і саме ця властивість формує основну властивість NMF-алгоритму. Тобто, NMF генерує матриці-множники, які набагато менші в порівнянні з вихідною матрицею. Наприклад, коли V розміру m×n, W — m×p, a H — p×n, то p може бути значно меншим від n i m.

Приклад на основі текстового аналізу: •Нехай матриця V має 10000 рядків і 500 стовпчиків, де слова є в рядках, а документи- стовпчиками. Тобто є 500 проіндексованих документів по 100000 слів. •Припустимо, нам потрібно знайти алгоритм, що дає 10 можливостей для того, щоб генерувати матриці W з 10000 рядків і 10 стовпців і коефіцієнти матриці H з 10 рядків і 500 стовпців. •Добуток W на H має розмірність 10000 на 500 і, якщо розклад спрацював правильно, елементи якого приблизно рівні елементам вихідної матриці V. •З цього випливає, що кожен стовпчик з матриці WH є лінійною комбінацією векторів 10 стовпців W і відповідних рядків з матриці H.

Цей останній пункт є основою NMF, тому що ми можемо розглядати кожен вихідний документ у нашому прикладі, який будується з невеликого набору прихованих функцій. NMF генерує ці функції.

Інколи корисно розглядати вектор стовпчик з властивостей матриці W як архетип документа, що містить набір слів, де значення комірки кожного слова визначає ранг даного слова у функції: чим вище значення слова, тим вище ранг слова в функції. Стовпчик в коефіцієнтах матриці H представляє оригінальний документ зі значенням, що визначає значення документа у функції. Це виконується, бо кожен рядок матриці H представляє функцію(властивість). Тепер ми можемо відновити документ (стовпчик вектор) з заданої матриці лінійною комбінацією властивостей (вектори- стовпчики в W ,де кожне значення рівне значенню клітинки із стовпчика документу у H.

Типи

Наближений розклад невід'ємних матриць

Зазвичай кількість стовпців у Wі к-сть рядків у H у NMF вибирається так, щоб WH було наближенням до V. Повний розклад V є двома невід'ємними матрицями W і H а також залишкової U, тобто : V = WH + U.Елементи залишкової матриці можуть бути як від'ємними, так і додатними.

Якщо W іHє меншими, ніж V , то їх легше зберігати і ними маніпулювати. Ще одна причина розкладу V на менші матриці W іH, якщо можна представити елементи V набагато меншою кількістю даних, то можна уявити структури, заховані у цих даних з набагато меншими втратами.

Опуклий розклад невід'ємних матриць

В стандартному NMF, фактор матриця $W\in \underset{+}{\overset{m\times k}{\mathrm{\Re }}}$， i.e., W може бути чим завгодно з цього простору. Опуклий NMF обмежує $W$ до опуклої комбінації векторів вхідних даних $(v_1,\cdots ,v_n)$.Це значно підвищує якість представлених даних W. Крім того, результат фактор матриці H стає більш розрідженим і ортогональним.

Невід'ємний ранг розкладу

Якщо невід'ємний ранг V рівний рангу, V=WH, то він називається невід'ємним рангом розкладу . Проблемою у відшуканні NRF для V,є те що така проблема є NP-повною.

Різновиди функцій втрат і регуляризації

Є різні типи розкладу невід'ємних матриць. Різні типи виникають із використанням різних функцій втрат для вимірювання різниці між V іWH і, можливо, із регуляризацією матриці W і/абоH .

Дві прості функції вивчені Лі і Сунгом — це квадрат помилки (або Фробеніусова норма) і розширення відмінності додатних матриць Кулбека-Лейблера. Кожна відмінність призводить до іншого алгоритму NMF, зазвичай мінімузуючого відмінність за допомогою ітеративного процесу.

Проблема факторизації у випадку NMF з квадратом помилки може записуватись так: Дано матрицю $𝐕$ знайти невід'ємні матриці W і H, що мінімізують функцію

$F(𝐖,𝐇)=\Vert 𝐕-𝐖𝐇{\Vert }_F^2$

Ще один тип NMF для зображень базується на нормі повної варіації.

Online NMF

Багато стандартних алгоритмів NMF аналізують всі дані разом, тобто вся матриця доступна з самого початку. Це може бути незадовільним в додатках, де є занадто багато даних, щоб поміститися в пам'яті або де дані представлені в потоковому вигляді. Прикладом таких може бути колаборативна фільтрація у рекомендаційній системі, де може бути багато користувачів і багато предметів, для рекомендацій, і це було б неефективно перерахувати все, коли один користувач або один елемент буде додано в систему. Функція втрат для оптимізації в таких випадках може або не може бути такою ж, як і для стандартного NMF, але алгоритми повинні бути досить різні.

Алгоритми

Є кілька способів знаходження W and H :правило мультиплікативного оновлення Лі і Сунга, було популярним методом з простою реалізацією. З того часу було розроблено ще кілька інших алгоритмів.

Кілька вдалих алгоритмів базуються на невід'ємних найменших квадратах non-negative least squares: на кожному кроці цього алгоритму, спочатку H є фіксованою, а W знаходиться методом невід'ємних найменших квадратів, тодіW стає фіксованою, а H знаходиться аналогічно. Процедура знаходження W і H може бути такою ж або відмінною, від варіанту регуляризації у NMF одної з W іH. Конкретні підходи включають Метод найшвидшого спуску, метод активної множини, а також метод повороту головного блоку.

Алгоритми, що доступні зараз є не зовсім оптимальними, бо вони можуть тільки гарантувати знаходження локального мінімуму, порівняно з глобольним мінімумом у функції втрат. Швидше за все оптимальний алгоритм навряд чи буде знайдено в найближчому майбутньому, так як проблема узагальнює проблему K-засобів кластеризації, яка, як відомо єNP-повною. Проте, в багатьох додатках з добування даних, локальний мінімум є корисним.

Точний NMF

Точний розв'язок для варіантів NMF можна очікувати (за поліноміальний час) коли на матрицю V накладаються додаткові обмеження. Поліноміальний алгоритм для знаходження невід'ємного рангу факторизації, якщо V містить одночлен субматрицю рангу, рівного за рангом даній(Кемпбелл і Пул в 1981 році). Kalofolias and Gallopoulos (2012) вирішити симетричний аналог цієї проблеми, де V симетрична і містить діагональ основної субматриці рангу г. Їх алгоритм виконується зі складністю O(rm²) при високій щільності. Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu, & Zhu (2013) продемонстрували точний поліноміальний алгоритм NMF, який працює у випадку, де один з факторів W задовольняє умову роздільності.

Додатково

• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journalШаблон:Недоступне посилання
• Шаблон:Cite arXiv
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journalШаблон:Недоступне посилання