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

{{Машинне навчання|Знижування розмірності}}
'''Розклад невід'ємних матриць'''<ref>{{cite journal|last1=Tandon|first1=Rashish|author2=Suvrit Sra|title=Sparse nonnegative matrix approximation: new formulations and algorithms|year=2010|series=TR|url=ftp://ftp.kyb.tuebingen.mpg.de/pub/mpi-memos/pdf/nmftr.pdf}}</ref> (NMF(Non-negative matrix factorization)) це група алгоритмів багатовимірного аналізу та [[Лінійна алгебра|лінійної алгебри]], де матриця V розкладається в, зазвичай, дві матриці W, H, враховуючи, що жодна з трьох матриць немає від'ємних елементів. Завдяки невід'ємності результуючі матриці легко перевіряються. Крім того, в таких програмах, як обробка аудіо спектрограм даним притаманна ця невід'ємність. Так як проблема немає точних розв'язків, в загальному випадку, зазвичай, знаходять числове наближення.
[[Файл:NMF.png|міні|'''V=W*H''']]

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

== Історія ==
У хемометриці розклад невід'ємних матриць має довгу історію під назвою «крива самостійного моделювання»<ref>{{Cite journal
 | author1 = William H. Lawton
 | author2 = Edward A. Sylvestre
 | title= Self modeling curve resolution
 | journal = [[Technometrics]]
 | volume = 13
 | issue = 3
 | year = 1971
 | page = 617+
 | authorlink1 = William H. Lawton
 | authorlink2 = Edward A. Sylvestre
 | doi=10.2307/1267173
}}</ref>.У рамках цього фреймворку вектори у правій матриці представляють неперервні криві, а не дискретні вектори. Також ранню роботу з розкладу невід'ємних матриць проводила група фінських вчених в середині 1990-х, під назвою «позитивної матричної факторизації».<ref>{{Cite journal
 | author = P. Paatero, U. Tapper
 | title = Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values
 | journal = [[Environmetrics]]
 | volume = 5
 | pages = 111–126
 | year = 1994
 | doi = 10.1002/env.3170050203
 | issue = 2
}}</ref><ref>{{Cite journal
 | author = [[Pia Anttila]], [[Pentti Paatero]], Unto Tapper, Olli Järvinen
 | title = Source identification of bulk wet deposition in Finland by positive matrix factorization
 | url = https://archive.org/details/sim_atmospheric-environment_1995-07_29_14/page/1705
 | journal = [[Atmospheric Environment (journal)|Atmospheric Environment]]
 | volume = 29
 | issue = 14
 | pages = 1705&ndash;1718
 | year = 1995
 | doi = 10.1016/1352-2310(94)00367-T
}}</ref> Він став широко відомим як факторизація невід'ємних матриць після того, як Лі і Сунг дослідили властивості алгоритму і опублікували кілька простих і корисних алгоритмів для двох типів факторизацій(множників).<ref name="lee-seung">{{Cite journal
 | author = Daniel D. Lee and [[Sebastian Seung|H. Sebastian Seung]]
 | year = 1999
 | title = Learning the parts of objects by non-negative matrix factorization
 | journal = [[Nature (journal)|Nature]]
 | volume = 401
 | issue = 6755
 | pages = 788&ndash;791
 | doi = 10.1038/44565
 | pmid = 10548103
}}</ref><ref name="lee2001algorithms">{{Cite conference
 | author = Daniel D. Lee and H. Sebastian Seung
 | year = 2001
 | url = http://www.nips.cc/Web/Groups/NIPS/NIPS2000/00papers-pub-on-web/LeeSeung.ps.gz
 | title = Algorithms for Non-negative Matrix Factorization
 | conference = Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference
 | pages = 556&ndash;562
 | publisher = [[MIT Press]]
 }}{{Недоступне посилання|date=червень 2019 |bot=InternetArchiveBot }}</ref>

== Теорія ==
Нехай матриця '''V''' є добутком матриці '''W''' і '''H'''
: <math>\mathbf{V} = \mathbf{W} \mathbf{H} \,.</math>

[[Множення матриць]] може бути реалізоване як обчислення вектор-стовпчиків матриці '''V''',у вигляді лінійної комбінації вектор-стовпчиків матриці '''W''' використовуючи коефіцієнти, що відповідають векторам-рядкам матриці '''H'''.Тобто, кожен стовпець '''V''' може бути обчислено таким чином:
: <math>\mathbf{v}_i = \mathbf{W} \mathbf{h}_{i} \,,</math>
де '''v'''<sub>''i''</sub>&nbsp;— і-ий вектор-стовпчик матриці '''V''', a '''h'''<sub>''i''</sub>&nbsp;— і-ий вектор-стовпчик матриці '''H'''.

При множенні матриць, розміри матриць-множників можуть бути значно меншими від розмірів матриці-результата і саме ця властивість формує основну властивість NMF-алгоритму. Тобто, NMF генерує матриці-множники, які набагато менші в порівнянні з вихідною матрицею. Наприклад, коли '''V''' розміру m×n, '''W'''&nbsp;— m×p, a '''H'''&nbsp;— 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, фактор матриця <math> W \in \Re^{m \times k}_{+} </math>， i.e., '''W''' може бути чим завгодно з цього простору. Опуклий NMF<ref name="ding">C Ding, T Li, MI Jordan, Convex and semi-nonnegative matrix factorizations, IEEE Transactions on Pattern Analysis and Machine Intelligence, 32, 45-55, 2010</ref> обмежує <math> W </math> до опуклої комбінації векторів вхідних даних <math> (v_1, \cdots, v_n) </math>.Це значно підвищує якість представлених даних '''W'''. Крім того, результат фактор матриці '''H''' стає більш розрідженим і ортогональним.

=== Невід'ємний ранг розкладу ===
Якщо невід'ємний ранг '''V''' рівний рангу, '''V=WH''', то він називається невід'ємним рангом розкладу .<ref name=BermanPlemmons74>{{cite journal|last=Berman|first=A.|author2=R.J. Plemmons |title=Inverses of nonnegative matrices|journal=Linear and Multilinear Algebra|year=1974|volume=2|pages=161–172|doi=10.1080/03081087408817055}}</ref><ref name=BermanPlemmons94>{{cite book|last=A. Berman, R.J. Plemmons|title=Nonnegative matrices in the Mathematical Sciences|year=1994|publisher=SIAM|location=Philadelphia}}</ref><ref name=Thomas74>{{cite journal|last=Thomas|first=L.B.|title=Problem 73-14, Rank factorization of nonnegative matrices|journal=SIAM rev.|year=1974|volume=16|issue=3|pages=393–394|doi=10.1137/1016064}}</ref> Проблемою у відшуканні NRF для '''V''',є те що така проблема є NP-повною.<ref name=Vavasis09>{{cite journal|last=Vavasis|first=S.A.|title=On the complexity of nonnegative matrix factorization|journal=SIAM J. Optim.|year=2009|volume=20|pages=1364–1377|doi=10.1137/070709967}}</ref>

=== Різновиди функцій втрат і регуляризації ===
Є різні типи розкладу невід'ємних матриць.
Різні типи виникають із використанням різних функцій втрат для вимірювання різниці між '''V''' і'''WH''' і, можливо, із регуляризацією матриці '''W''' і/або'''H''' .<ref name="dhillon">{{Cite conference | author = [[Inderjit S. Dhillon]], [[Suvrit Sra]] | url = http://books.nips.cc/papers/files/nips18/NIPS2005_0203.pdf | format = PDF | title = Generalized Nonnegative Matrix Approximations with Bregman Divergences | conference = [[Conference on Neural Information Processing Systems|NIPS]] | year = 2005 | accessdate = 2 червня 2015 | archive-date = 7 серпня 2011 | archive-url = https://web.archive.org/web/20110807201748/http://books.nips.cc/papers/files/nips18/NIPS2005_0203.pdf }}</ref>

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

Проблема факторизації у випадку NMF з квадратом помилки може записуватись так: Дано матрицю <math>\mathbf{V}</math> знайти невід'ємні матриці W і H, що мінімізують функцію
: <math>F(\mathbf{W},\mathbf{H}) = \|\mathbf{V} - \mathbf{WH}\|^2_F</math>

Ще один тип NMF для зображень базується на нормі повної варіації.<ref>{{cite doi|10.1016/j.neucom.2008.01.022}}</ref>

=== Online NMF ===
Багато стандартних алгоритмів NMF аналізують всі дані разом, тобто вся матриця доступна з самого початку. Це може бути незадовільним в додатках, де є занадто багато даних, щоб поміститися в пам'яті або де дані представлені в потоковому вигляді. Прикладом таких може бути [[колаборативна фільтрація]] у [[Рекомендаційна система|рекомендаційній системі]], де може бути багато користувачів і багато предметів, для рекомендацій, і це було б неефективно перерахувати все, коли один користувач або один елемент буде додано в систему. Функція втрат для оптимізації в таких випадках може або не може бути такою ж, як і для стандартного NMF, але алгоритми повинні бути досить різні.<ref>{{Cite web |url=http://www.ijcai.org/papers07/Papers/IJCAI07-432.pdf |title=Архівована копія |accessdate=2 червня 2015 |archive-date=24 вересня 2015 |archive-url=https://web.archive.org/web/20150924033456/http://www.ijcai.org/papers07/Papers/IJCAI07-432.pdf }}</ref><ref>http://portal.acm.org/citation.cfm?id=1339264.1339709</ref>

== Алгоритми ==
Є кілька способів знаходження '''W''' and '''H''' :правило мультиплікативного оновлення Лі і Сунга,<ref name="lee2001algorithms"/> було популярним методом з простою реалізацією. З того часу було розроблено ще кілька інших алгоритмів.

Кілька вдалих алгоритмів базуються на невід'ємних найменших квадратах [[non-negative least squares]]: на кожному кроці цього алгоритму, спочатку '''H''' є фіксованою, а '''W''' знаходиться методом невід'ємних найменших квадратів, тоді'''W''' стає фіксованою, а '''H''' знаходиться аналогічно. Процедура знаходження '''W''' і '''H''' може бути такою ж<ref name="lin07"/> або відмінною, від варіанту регуляризації у NMF одної з '''W''' і'''H'''.<ref name="hoyer02"/> Конкретні підходи включають [[Метод найшвидшого спуску]],<ref name="lin07">{{cite doi|10.1162/neco.2007.19.10.2756}}</ref><ref>{{cite doi|10.1109/TNN.2007.895831}}</ref> метод активної множини,<ref name="gemulla"/><ref name="kim2008nonnegative">{{Cite journal
 | author = Hyunsoo Kim and Haesun Park
 | title = Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method
 | journal = [[SIAM Journal on Matrix Analysis and Applications]]
 | volume = 30
 | issue = 2
 | year = 2008
 | pages = 713&ndash;730
 | url = http://www.cc.gatech.edu/~hpark/papers/simax-nmf.pdf
 | doi = 10.1137/07069239x
 | accessdate = 2 червня 2015
 | archive-date = 13 жовтня 2015
 | archive-url = https://web.archive.org/web/20151013121949/http://www.cc.gatech.edu/~hpark/papers/simax-nmf.pdf
 }}</ref> а також метод повороту головного блоку.<ref name="kim2011fast">
{{Cite journal
 | author = Jingu Kim and Haesun Park
 | title = Fast Nonnegative Matrix Factorization: An Active-set-like Method and Comparisons
 | journal = [[SIAM Journal on Scientific Computing]]
 | volume = 33
 | issue = 6
 | year = 2011
 | pages = 3261&ndash;3281
 | url = http://www.cc.gatech.edu/~jingu/docs/2011_paper_sisc_nmf.pdf
 | doi = 10.1137/110821172
 }}{{Недоступне посилання|date=квітень 2019 |bot=InternetArchiveBot }}
</ref>

Алгоритми, що доступні зараз є не зовсім оптимальними, бо вони можуть тільки гарантувати знаходження локального мінімуму, порівняно з глобольним мінімумом у функції втрат. Швидше за все оптимальний алгоритм навряд чи буде знайдено в найближчому майбутньому, так як проблема узагальнює проблему K-засобів кластеризації, яка, як відомо є[[NP-повна задача|NP-повною]].<ref>{{Cite journal
  | title = On the equivalence of nonnegative matrix factorization and spectral clustering
  | author = Ding, C. and He, X. and Simon, H.D.,
  | journal = Proc. SIAM Data Mining Conf
  | volume = 4
  | pages = 606&ndash;610
  | year = 2005
  | doi=10.1137/1.9781611972757.70
}}</ref> Проте, в багатьох додатках з [[добування даних]], локальний мінімум є корисним.

=== Точний NMF ===
Точний розв'язок для варіантів NMF можна очікувати (за поліноміальний час) коли на матрицю '''V''' накладаються додаткові обмеження. Поліноміальний алгоритм для знаходження невід'ємного рангу факторизації, якщо '''V''' містить одночлен субматрицю рангу, рівного за рангом даній(Кемпбелл і Пул в 1981 році).<ref name=CampbellPoole81>{{cite journal|last=Campbell|first=S.L.|author2=G.D. Poole |title=Computing nonnegative rank factorizations.|journal=Linear Algebra Appl.|year=1981|volume=35|pages=175–182|doi=10.1016/0024-3795(81)90272-x}}</ref> Kalofolias and Gallopoulos (2012)<ref name=KalofoliasGallopoulos2012>{{cite journal|last=Kalofolias|first=V.|author2=Gallopoulos, E.|title=Computing symmetric nonnegative rank factorizations|journal=Linear Algebra Appl|year=2012|volume=436|pages=421–435|url=http://www.sciencedirect.com/science/article/pii/S0024379511002199#|doi=10.1016/j.laa.2011.03.016|accessdate=2 червня 2015|archive-date=24 вересня 2015|archive-url=https://web.archive.org/web/20150924154638/http://www.sciencedirect.com/science/article/pii/S0024379511002199}}</ref> вирішити симетричний аналог цієї проблеми, де '''V''' симетрична і містить діагональ основної субматриці рангу г. Їх алгоритм виконується зі складністю O(rm²) при високій щільності. Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu, & Zhu (2013) продемонстрували точний поліноміальний алгоритм NMF, який працює у випадку, де один з факторів W задовольняє умову роздільності.<ref name=Arora2013>{{Cite conference
| last1 = Arora
| first1 = Sanjeev
| last2 = Ge
| first2 = Rong
| last3 = Halpern
| first3 = Yoni
| last4 = Mimno
| first4 = David
| last5 = Moitra
| first5 = Ankur
| last6 = Sontag
| first6 = David
| last7 = Wu
| first7 = Yichen
| last8 = Zhu
| first8 = Michael
| title = A practical algorithm for topic modeling with provable guarantees
| url = http://jmlr.csail.mit.edu/proceedings/papers/v28/arora13.html
| arxiv = 1212.4777
| conference = Proceedings of the 30th International Conference on Machine Learning
| year = 2013
| accessdate = 2 червня 2015
| archive-date = 2 квітня 2015
| archive-url = https://web.archive.org/web/20150402235406/http://jmlr.csail.mit.edu/proceedings/papers/v28/arora13.html
}}</ref>

== Посилання ==
{{Reflist|refs=<ref name="hoyer02">{{cite conference |last=Hoyer |first=Patrik O. |title=Non-negative sparse coding |conference=Proc. IEEE Workshop on Neural Networks for Signal Processing |year=2002 |arxiv=cs/0202009 }}{{ref-en}} Наведено за англійською вікіпедією.</ref>
<ref name="gemulla">{{cite conference |author=Rainer Gemulla |author2=Erik Nijkamp |author3=Peter J Haas |author4=Yannis Sismanis |title=Large-scale matrix factorization with distributed stochastic gradient descent |conference=Proc. ACM SIGKDD Int'l Conf. on Knowledge discovery and data mining |url=<!-- http://www.mpi-inf.mpg.de/~rgemulla/publications/rj10481rev.pdf --><!--removing dead link--> |year=2011 |pages=69–77 }}{{ref-en}} Наведено за англійською вікіпедією.</ref>
|2}}

== Додатково ==
{{refbegin}}
* {{Cite journal
 | author = J. Shen, G. W. Israël
 | title = A receptor model using a specific non-negative transformation technique for ambient aerosol
 | url = https://archive.org/details/sim_atmospheric-environment_1989_23_10/page/2289
 | journal = [[Atmospheric Environment (journal)|Atmospheric Environment]]
 | volume = 23
 | issue = 10
 | pages = 2289&ndash;2298
 | year = 1989
 | doi = 10.1016/0004-6981(89)90190-X
}}
* {{Cite journal
 | author = [[Pentti Paatero]]
 | title = Least squares formulation of robust non-negative factor analysis
 | journal = [[Chemometrics and Intelligent Laboratory Systems]]
 | volume = 37
 | issue = 1
 | pages = 23&ndash;35
 | year = 1997
 | doi = 10.1016/S0169-7439(96)00044-5
}}
* {{Cite journal
 | author = Raul Kompass
 | title = A Generalized Divergence Measure for Nonnegative Matrix Factorization
 | journal = [[Neural Computation]]
 | volume = 19
 | issue = 3
 | year = 2007
 | pages = 780&ndash;791
 | pmid = 17298233
 | doi = 10.1162/neco.2007.19.3.780
}}
* {{Cite journal
|  title=Nonnegative Matrix Factorization and its applications in pattern recognition
|  author=Liu, W.X. and Zheng, N.N. and You, Q.B.
|  journal=[[Chinese Science Bulletin]]
|  volume=51
|  pages=7&ndash;18
|  year=2006
|  url=http://www.springerlink.com/index/7285V70531634264.pdf
|  doi=10.1007/s11434-005-1109-6
|  issue=17&ndash;18
}}{{Недоступне посилання}}
* {{Cite arXiv
 | author = Ngoc-Diep Ho, Paul Van Dooren and Vincent Blondel
 | title = Descent Methods for Nonnegative Matrix Factorization
 | year = 2008
 | eprint = 0801.3199
 | class = cs.NA
}}
* {{Cite journal
 | author = [[Andrzej Cichocki]], Rafal Zdunek and [[Shun-ichi Amari]]
 | title = Nonnegative Matrix and Tensor Factorization
 | journal = [[IEEE Signal Processing Magazine]]
 | volume = 25
 | issue = 1
 | year = 2008
 | pages = 142&ndash;145
 | doi = 10.1109/MSP.2008.4408452
}}
* {{Cite journal
 | title = Nonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis
 | author = Cédric Févotte, Nancy Bertin, and Jean-Louis Durrieu
 | journal = [[Neural Computation]]
 | volume = 21
 | issue = 3
 | year = 2009
| pmid=18785855
 | doi=10.1162/neco.2008.04-08-771
 | pages=793–830
}}
* {{Cite journal
 | author = Ali Taylan Cemgil
 | title = Bayesian Inference for Nonnegative Matrix Factorisation Models
 | journal = [[Computational Intelligence and Neuroscience]]
 | volume = 2009
 | issue = 2
 | year = 2009
 | doi = 10.1155/2009/785152
 | url = http://www.hindawi.com/journals/cin/2009/785152.abs.html
 | pages = 1
 | pmid = 19536273
 | pmc = 2688815
 }}{{Недоступне посилання}}
{{refend}}
[[Категорія:Лінійна алгебра]]
[[Категорія:Теорія матриць]]
[[Категорія:Алгоритми машинного навчання]]