गैर-ऋणात्मक न्यूनतम वर्ग: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Regression bar}} | {{Regression bar}} | ||
[[गणितीय अनुकूलन]] में, गैर- | [[गणितीय अनुकूलन]] में, गैर-ऋणात्मक न्यूनतम वर्ग की समस्या (एनएनएलएस) प्रकार की प्रतिबंधित न्यूनतम वर्ग समस्या है जहां गुणांक को ऋणात्मक बनने की अनुमति नहीं है। अर्थात आव्यूह दिया गया है {{math|'''A'''}} और प्रतिक्रिया चर का (कॉलम) सदिश {{math|'''y'''}}, लक्ष्य खोजना है<ref name="chen"/> | ||
:<math>\operatorname{arg\,min}\limits_\mathbf{x} \|\mathbf{Ax} - \mathbf{y}\|_2^2</math> का विषय है {{math|'''x''' ≥ 0}}. | :<math>\operatorname{arg\,min}\limits_\mathbf{x} \|\mathbf{Ax} - \mathbf{y}\|_2^2</math> का विषय है {{math|'''x''' ≥ 0}}. | ||
यहाँ {{math|'''x''' ≥ 0}} का अर्थ है कि | यहाँ {{math|'''x''' ≥ 0}} का अर्थ है कि सदिश का प्रत्येक घटक {{math|'''x'''}} गैर-ऋणात्मक होना चाहिए, और {{math|‖·‖<sub>2</sub>}} [[यूक्लिडियन मानदंड]] को दर्शाता है। | ||
गैर- | गैर-ऋणात्मक न्यूनतम वर्ग समस्याएं [[मैट्रिक्स अपघटन|आव्यूह अपघटन]] में उप-समस्याओं के रूप में सामने आती हैं, उदाहरण के लिए [[सीपी अपघटन]] के लिए कलन में<ref name="bro"/>और गैर-ऋणात्मक आव्यूह गुणनखंडन या गैर-ऋणात्मक आव्यूह/टेंसर गुणनखंडन।<ref>{{Cite journal | last1 = Lin | first1 = Chih-Jen| title = गैर-ऋणात्मक मैट्रिक्स गुणनखंडन के लिए प्रक्षेपित ग्रेडिएंट विधियाँ| doi = 10.1162/neco.2007.19.10.2756 | journal = [[Neural Computation]]| volume = 19 | issue = 10 | pages = 2756–2779 | year = 2007 | pmid = 17716011| url = http://www.csie.ntu.edu.tw/~cjlin/papers/pgradnmf.pdf| citeseerx = 10.1.1.308.9135}}</ref><ref>{{cite journal |title=गैर-नकारात्मक न्यूनतम-वर्ग समस्या के लिए यादृच्छिक अनुमान|first1=Christos |last1=Boutsidis |first2=Petros |last2=Drineas |journal=Linear Algebra and Its Applications |volume=431 |issue=5–7 |year=2009 |pages=760–771 |doi=10.1016/j.laa.2009.03.026|arxiv=0812.4547 }}</ref> उत्तरार्द्ध को एनएनएलएस का सामान्यीकरण माना जा सकता है।<ref name="chen"/> | ||
एनएनएलएस का और सामान्यीकरण परिबद्ध-परिवर्तनीय न्यूनतम वर्ग (बीवीएलएस) है, जिसमें साथ ऊपरी और निचली सीमाएं होती हैं {{math|α''<sub>i</sub>'' ≤ '''x'''''<sub>i</sub>'' ≤ β''<sub>i</sub>''}}.{{r|lawson}}{{rp|291}}<ref>{{cite journal |last1=Stark |first1=Philip B. |first2=Robert L. |last2=Parker |title=Bounded-variable least-squares: an algorithm and applications |journal=Computational Statistics |volume=10 |year=1995 |pages=129 |url=http://digitalassets.lib.berkeley.edu/sdtr/ucb/text/394.pdf}}</ref> | एनएनएलएस का और सामान्यीकरण परिबद्ध-परिवर्तनीय न्यूनतम वर्ग (बीवीएलएस) है, जिसमें साथ ऊपरी और निचली सीमाएं होती हैं {{math|α''<sub>i</sub>'' ≤ '''x'''''<sub>i</sub>'' ≤ β''<sub>i</sub>''}}.{{r|lawson}}{{rp|291}}<ref>{{cite journal |last1=Stark |first1=Philip B. |first2=Robert L. |last2=Parker |title=Bounded-variable least-squares: an algorithm and applications |journal=Computational Statistics |volume=10 |year=1995 |pages=129 |url=http://digitalassets.lib.berkeley.edu/sdtr/ucb/text/394.pdf}}</ref> | ||
| Line 15: | Line 15: | ||
:<math>\operatorname{arg\,min}\limits_\mathbf{x \ge 0} \left(\frac{1}{2} \mathbf{x}^\mathsf{T} \mathbf{Q}\mathbf{x} + \mathbf{c}^\mathsf{T} \mathbf{x}\right),</math> | :<math>\operatorname{arg\,min}\limits_\mathbf{x \ge 0} \left(\frac{1}{2} \mathbf{x}^\mathsf{T} \mathbf{Q}\mathbf{x} + \mathbf{c}^\mathsf{T} \mathbf{x}\right),</math> | ||
कहाँ {{math|'''Q'''}} = {{math|'''A'''<sup>T</sup>'''A'''}} और {{math|'''c'''}} = {{math|−'''A'''<sup>T</sup> '''y'''}}. यह समस्या [[उत्तल अनुकूलन]] है, जैसे {{math|'''Q'''}} [[सकारात्मक-अर्धनिश्चित मैट्रिक्स]] है और गैर- | कहाँ {{math|'''Q'''}} = {{math|'''A'''<sup>T</sup>'''A'''}} और {{math|'''c'''}} = {{math|−'''A'''<sup>T</sup> '''y'''}}. यह समस्या [[उत्तल अनुकूलन]] है, जैसे {{math|'''Q'''}} [[सकारात्मक-अर्धनिश्चित मैट्रिक्स|सकारात्मक-अर्धनिश्चित आव्यूह]] है और गैर-ऋणात्मकता बाधाएं उत्तल व्यवहार्य समुच्चय बनाती हैं।<ref name="sca">{{cite book|doi=10.1007/11556121_50|title=गैर-नकारात्मक न्यूनतम वर्ग समस्या के लिए अनुक्रमिक समन्वय-वार एल्गोरिदम|journal=Computer Analysis of Images and Patterns|volume=3691|pages=407–414|series=Lecture Notes in Computer Science|year=2005|last1=Franc|first1=Vojtěch|last2=Hlaváč|first2=Václav|last3=Navara|first3=Mirko|isbn=978-3-540-28969-2}}</ref> | ||
== | ==कलन == | ||
इस समस्या को हल करने के लिए पहला व्यापक रूप से उपयोग किया जाने वाला | इस समस्या को हल करने के लिए पहला व्यापक रूप से उपयोग किया जाने वाला कलन [[सक्रिय-सेट विधि|सक्रिय-समुच्चय विधि]] है जिसे लॉसन और हैनसन ने अपनी 1974 की पुस्तक न्यूनतम वर्ग समस्याओं का समाधान में प्रकाशित किया है।<ref name="lawson">{{cite book |last1=Lawson |first1=Charles L. |last2=Hanson |first2=Richard J. |title=न्यूनतम वर्ग समस्याओं का समाधान|year=1995 |publisher=SIAM |url=https://epubs.siam.org/doi/abs/10.1137/1.9781611971217.ch23 |chapter=23. Linear Least Squares with Linear Inequality Constraints |pages=161}}</ref>{{rp|291}} [[ छद्मकोड |छद्मकोड]] में, यह कलन इस प्रकार दिखता है:{{r|chen}}<ref name="bro">{{Cite journal |doi=10.1002/(SICI)1099-128X(199709/10)11:5<393::AID-CEM483>3.0.CO;2-L |title=एक तेज़ गैर-नकारात्मकता-विवश न्यूनतम वर्ग एल्गोरिथ्म|journal=Journal of Chemometrics |volume=11 |issue=5 |pages=393 |year=1997 |last1=Bro |first1=Rasmus |last2=De Jong |first2=Sijmen}}</ref> | ||
{{framebox|blue}} | {{framebox|blue}} | ||
| Line 51: | Line 51: | ||
{{frame-footer}} | {{frame-footer}} | ||
यह | यह कलन किसी समाधान तक पहुंचने के लिए सीमित संख्या में कदम उठाता है और जैसे-जैसे आगे बढ़ता है, अपने उम्मीदवार समाधान को सुचारू रूप से उत्तम बनाता है (जिससे कि यह उचित संख्या में पुनरावृत्तियों में कट जाने पर अच्छे अनुमानित समाधान पा सके), लेकिन व्यवहार में यह बहुत धीमा है, जिसका मुख्य कारण मूर-पेनरोज़ स्यूडोइनवर्स की गणना है। {{math|(('''A'''<sup>P</sup>)<sup>T</sup> '''A'''<sup>P</sup>)<sup>−1</sup>}}.{{r|chen}} इस कलन के प्रकार [[MATLAB|मैट लैब]] में रूटीन के रूप में उपलब्ध हैं {{mono|लसक्नोनग}}<ref>{{cite web |url=https://www.mathworks.com/help/matlab/ref/lsqnonneg.html |title=lsqnonneg|website=MATLAB Documentation |access-date=October 28, 2022}}</ref><ref name="chen">{{cite conference |author-link2=Robert J. Plemmons |last1=Chen |first1=Donghui |first2=Robert J. |last2=Plemmons |title=संख्यात्मक विश्लेषण में गैर-नकारात्मकता बाधाएँ|conference=Symposium on the Birth of Numerical Analysis |date=2009 |citeseerx = 10.1.1.157.9203}}</ref> और [[SciPy]] में के रूप में {{mono|ऑप्टिमाइज़.एनएनएलएस}}.<ref>{{cite web |url=http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.nnls.html |title=scipy.optimize.nnls|website=SciPy v0.13.0 Reference Guide |access-date=25 January 2014}}</ref> | ||
<!-- TODO cite the R package nnls as well --> | <!-- TODO cite the R package nnls as well --> | ||
1974 के बाद से कई | 1974 के बाद से कई उत्तम कलन का सुझाव दिया गया है।{{r|chen}} फास्ट एनएनएलएस (एफएनएनएलएस) लॉसन-हैनसन कलन का अनुकूलित संस्करण है।{{r|bro}} अन्य कलन में लैंडवेबर पुनरावृत्ति की [[ ढतला हुआ वंश |ढतला हुआ वंश]] विधि के प्रकार सम्मिलित हैं<ref>{{Cite journal | doi = 10.1016/j.mcm.2005.12.010| title = पर्यवेक्षित शिक्षण के मॉडल के लिए तिरछी-प्रक्षेपित लैंडवेबर विधि का अनुप्रयोग| journal = Mathematical and Computer Modelling| volume = 43| issue = 7–8| pages = 892| year = 2006| last1 = Johansson | first1 = B. R. | last2 = Elfving | first2 = T. | last3 = Kozlov | first3 = V. | last4 = Censor | first4 = Y. | last5 = Forssén | first5 = P. E. | last6 = Granlund | first6 = G. S. | doi-access = free }}</ref> और उपरोक्त द्विघात प्रोग्रामिंग समस्या के आधार पर समन्वय अवतरण या समन्वय-वार अनुकूलन करता है।{{r|sca}} | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[एम-मैट्रिक्स]] | * [[एम-मैट्रिक्स|एम-आव्यूह]] | ||
* पेरोन-फ्रोबेनियस प्रमेय | * पेरोन-फ्रोबेनियस प्रमेय | ||
Revision as of 19:42, 4 August 2023
| एक श्रृंखला का हिस्सा |
| प्रतिगमन विश्लेषण |
|---|
| मॉडल |
| अनुमान |
| पार्श्वभूमि |
|
|
गणितीय अनुकूलन में, गैर-ऋणात्मक न्यूनतम वर्ग की समस्या (एनएनएलएस) प्रकार की प्रतिबंधित न्यूनतम वर्ग समस्या है जहां गुणांक को ऋणात्मक बनने की अनुमति नहीं है। अर्थात आव्यूह दिया गया है A और प्रतिक्रिया चर का (कॉलम) सदिश y, लक्ष्य खोजना है[1]
- का विषय है x ≥ 0.
यहाँ x ≥ 0 का अर्थ है कि सदिश का प्रत्येक घटक x गैर-ऋणात्मक होना चाहिए, और ‖·‖2 यूक्लिडियन मानदंड को दर्शाता है।
गैर-ऋणात्मक न्यूनतम वर्ग समस्याएं आव्यूह अपघटन में उप-समस्याओं के रूप में सामने आती हैं, उदाहरण के लिए सीपी अपघटन के लिए कलन में[2]और गैर-ऋणात्मक आव्यूह गुणनखंडन या गैर-ऋणात्मक आव्यूह/टेंसर गुणनखंडन।[3][4] उत्तरार्द्ध को एनएनएलएस का सामान्यीकरण माना जा सकता है।[1]
एनएनएलएस का और सामान्यीकरण परिबद्ध-परिवर्तनीय न्यूनतम वर्ग (बीवीएलएस) है, जिसमें साथ ऊपरी और निचली सीमाएं होती हैं αi ≤ xi ≤ βi.[5]: 291 [6]
द्विघात प्रोग्रामिंग संस्करण
एनएनएलएस समस्या द्विघात प्रोग्रामिंग समस्या के बराबर है
कहाँ Q = ATA और c = −AT y. यह समस्या उत्तल अनुकूलन है, जैसे Q सकारात्मक-अर्धनिश्चित आव्यूह है और गैर-ऋणात्मकता बाधाएं उत्तल व्यवहार्य समुच्चय बनाती हैं।[7]
कलन
इस समस्या को हल करने के लिए पहला व्यापक रूप से उपयोग किया जाने वाला कलन सक्रिय-समुच्चय विधि है जिसे लॉसन और हैनसन ने अपनी 1974 की पुस्तक न्यूनतम वर्ग समस्याओं का समाधान में प्रकाशित किया है।[5]: 291 छद्मकोड में, यह कलन इस प्रकार दिखता है:[1][2]
- इनपुट:
- एक वास्तविक-मूल्यवान मैट्रिक्स A आयाम का m × n,
- एक वास्तविक-मूल्यवान वेक्टर y आयाम का m,
- एक वास्तविक मूल्य ε, रुकने की कसौटी के लिए सहनशीलता।
- आरंभ करें:
- तय करना P = ∅.
- तय करना R = {1, ..., n}.
- तय करना x आयाम के एक सर्व-शून्य वेक्टर के लिए n.
- तय करना w = AT(y − Ax).
- होने देना wR आर से इंडेक्स के साथ उप-वेक्टर को निरूपित करें
- मुख्य लूप: जबकि R ≠ ∅ और max(wR) > ε:
- होने देना j में R का सूचकांक हो max(wR) में w.
- जोड़ना j को P.
- निकालना j से R.
- होने देना AP होना A में शामिल चर तक ही सीमित है P.
- होने देना s के समान लंबाई का वेक्टर बनें x. होने देना sP पी से इंडेक्स के साथ उप-वेक्टर को निरूपित करें, और चलो sR आर से इंडेक्स के साथ उप-वेक्टर को निरूपित करें।
- तय करना sP = ((AP)T AP)−1 (AP)Ty
- तय करना sRशून्य करने के लिए
- जबकि min(sP) ≤ 0:
- होने देना α = min xi/xi − si for i in P where si ≤ 0.
- तय करना x को x + α(s − x).
- करने के लिए कदम R सभी सूचकांक j में P ऐसा है कि xj ≤ 0.
- तय करना sP = ((AP)T AP)−1 (AP)Ty
- तय करना sRशून्य करने के लिए.
- तय करना x को s.
- तय करना w को AT(y − Ax).
- आउटपुट: एक्स
यह कलन किसी समाधान तक पहुंचने के लिए सीमित संख्या में कदम उठाता है और जैसे-जैसे आगे बढ़ता है, अपने उम्मीदवार समाधान को सुचारू रूप से उत्तम बनाता है (जिससे कि यह उचित संख्या में पुनरावृत्तियों में कट जाने पर अच्छे अनुमानित समाधान पा सके), लेकिन व्यवहार में यह बहुत धीमा है, जिसका मुख्य कारण मूर-पेनरोज़ स्यूडोइनवर्स की गणना है। ((AP)T AP)−1.[1] इस कलन के प्रकार मैट लैब में रूटीन के रूप में उपलब्ध हैं लसक्नोनग[8][1] और SciPy में के रूप में ऑप्टिमाइज़.एनएनएलएस.[9] 1974 के बाद से कई उत्तम कलन का सुझाव दिया गया है।[1] फास्ट एनएनएलएस (एफएनएनएलएस) लॉसन-हैनसन कलन का अनुकूलित संस्करण है।[2] अन्य कलन में लैंडवेबर पुनरावृत्ति की ढतला हुआ वंश विधि के प्रकार सम्मिलित हैं[10] और उपरोक्त द्विघात प्रोग्रामिंग समस्या के आधार पर समन्वय अवतरण या समन्वय-वार अनुकूलन करता है।[7]
यह भी देखें
- एम-आव्यूह
- पेरोन-फ्रोबेनियस प्रमेय
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Chen, Donghui; Plemmons, Robert J. (2009). संख्यात्मक विश्लेषण में गैर-नकारात्मकता बाधाएँ. Symposium on the Birth of Numerical Analysis. CiteSeerX 10.1.1.157.9203.
- ↑ 2.0 2.1 2.2 Bro, Rasmus; De Jong, Sijmen (1997). "एक तेज़ गैर-नकारात्मकता-विवश न्यूनतम वर्ग एल्गोरिथ्म". Journal of Chemometrics. 11 (5): 393. doi:10.1002/(SICI)1099-128X(199709/10)11:5<393::AID-CEM483>3.0.CO;2-L.
- ↑ Lin, Chih-Jen (2007). "गैर-ऋणात्मक मैट्रिक्स गुणनखंडन के लिए प्रक्षेपित ग्रेडिएंट विधियाँ" (PDF). Neural Computation. 19 (10): 2756–2779. CiteSeerX 10.1.1.308.9135. doi:10.1162/neco.2007.19.10.2756. PMID 17716011.
- ↑ Boutsidis, Christos; Drineas, Petros (2009). "गैर-नकारात्मक न्यूनतम-वर्ग समस्या के लिए यादृच्छिक अनुमान". Linear Algebra and Its Applications. 431 (5–7): 760–771. arXiv:0812.4547. doi:10.1016/j.laa.2009.03.026.
- ↑ 5.0 5.1 Lawson, Charles L.; Hanson, Richard J. (1995). "23. Linear Least Squares with Linear Inequality Constraints". न्यूनतम वर्ग समस्याओं का समाधान. SIAM. p. 161.
- ↑ Stark, Philip B.; Parker, Robert L. (1995). "Bounded-variable least-squares: an algorithm and applications" (PDF). Computational Statistics. 10: 129.
- ↑ 7.0 7.1 Franc, Vojtěch; Hlaváč, Václav; Navara, Mirko (2005). गैर-नकारात्मक न्यूनतम वर्ग समस्या के लिए अनुक्रमिक समन्वय-वार एल्गोरिदम. pp. 407–414. doi:10.1007/11556121_50. ISBN 978-3-540-28969-2.
{{cite book}}:|journal=ignored (help) - ↑ "lsqnonneg". MATLAB Documentation. Retrieved October 28, 2022.
- ↑ "scipy.optimize.nnls". SciPy v0.13.0 Reference Guide. Retrieved 25 January 2014.
- ↑ Johansson, B. R.; Elfving, T.; Kozlov, V.; Censor, Y.; Forssén, P. E.; Granlund, G. S. (2006). "पर्यवेक्षित शिक्षण के मॉडल के लिए तिरछी-प्रक्षेपित लैंडवेबर विधि का अनुप्रयोग". Mathematical and Computer Modelling. 43 (7–8): 892. doi:10.1016/j.mcm.2005.12.010.
