गैर-ऋणात्मक न्यूनतम वर्ग: Difference between revisions
From Vigyanwiki
(Created page with "{{Regression bar}} गणितीय अनुकूलन में, गैर-नकारात्मक न्यूनतम वर्ग की समस्या (...") |
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}}. | ||
| Line 8: | Line 8: | ||
गैर-नकारात्मक न्यूनतम वर्ग समस्याएं [[मैट्रिक्स अपघटन]] में उप-समस्याओं के रूप में सामने आती हैं, उदाहरण के लिए [[सीपी अपघटन]] के लिए एल्गोरिदम में<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"/> | गैर-नकारात्मक न्यूनतम वर्ग समस्याएं [[मैट्रिक्स अपघटन]] में उप-समस्याओं के रूप में सामने आती हैं, उदाहरण के लिए [[सीपी अपघटन]] के लिए एल्गोरिदम में<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> | ||
| 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 53: | Line 53: | ||
यह एल्गोरिदम किसी समाधान तक पहुंचने के लिए सीमित संख्या में कदम उठाता है और जैसे-जैसे आगे बढ़ता है, अपने उम्मीदवार समाधान को सुचारू रूप से बेहतर बनाता है (ताकि यह उचित संख्या में पुनरावृत्तियों में कट जाने पर अच्छे अनुमानित समाधान पा सके), लेकिन व्यवहार में यह बहुत धीमा है, जिसका मुख्य कारण मूर-पेनरोज़ स्यूडोइनवर्स की गणना है। {{math|(('''A'''<sup>P</sup>)<sup>T</sup> '''A'''<sup>P</sup>)<sup>−1</sup>}}.{{r|chen}} इस एल्गोरिथम के वेरिएंट [[MATLAB]] में रूटीन के रूप में उपलब्ध हैं {{mono|lsqnonneg}}<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|optimize.nnls}}.<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> | यह एल्गोरिदम किसी समाधान तक पहुंचने के लिए सीमित संख्या में कदम उठाता है और जैसे-जैसे आगे बढ़ता है, अपने उम्मीदवार समाधान को सुचारू रूप से बेहतर बनाता है (ताकि यह उचित संख्या में पुनरावृत्तियों में कट जाने पर अच्छे अनुमानित समाधान पा सके), लेकिन व्यवहार में यह बहुत धीमा है, जिसका मुख्य कारण मूर-पेनरोज़ स्यूडोइनवर्स की गणना है। {{math|(('''A'''<sup>P</sup>)<sup>T</sup> '''A'''<sup>P</sup>)<sup>−1</sup>}}.{{r|chen}} इस एल्गोरिथम के वेरिएंट [[MATLAB]] में रूटीन के रूप में उपलब्ध हैं {{mono|lsqnonneg}}<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|optimize.nnls}}.<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 के बाद से कई बेहतर एल्गोरिदम का सुझाव दिया गया है।{{r|chen}} फास्ट एनएनएलएस (एफएनएनएलएस) लॉसन-हैनसन एल्गोरिदम का | 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:14, 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] इस एल्गोरिथम के वेरिएंट MATLAB में रूटीन के रूप में उपलब्ध हैं lsqnonneg[8][1] और SciPy में के रूप में optimize.nnls.[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.
