समन्वय वंश: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[निर्देशांक तरीका|निर्देशांक विधि]] एक [[अनुकूलन एल्गोरिथ्म]] है जो किसी फलन के न्यूनतम को खोजने के लिए क्रमिक रूप से समन्वयित दिशाओं को कम करता है। प्रत्येक पुनरावृत्ति पर, एल्गोरिथ्म एक समन्वय प्रणाली को निर्धारित करता है या एक समन्वय चयन नियम के माध्यम से समन्वय ब्लॉक करता है, फिर अन्य सभी निर्देशांक या समन्वय ब्लॉकों को ठीक करते समय संबंधित समन्वय हाइपरप्लेन पर ठीक या गलत विधि से कम करता है। उपयुक्त चरण आकार निर्धारित करने के लिए समन्वय प्रणाली दिशा के साथ एक लाइन खोज वर्तमान पुनरावृति पर की जा सकती है। समन्वय अवरोहण अलग-अलग और व्युत्पन्न-मुक्त दोनों संदर्भों में प्रयुक्त होता है।
[[निर्देशांक तरीका|समन्वय वंश]] [[अनुकूलन एल्गोरिथ्म|अनुकूलन कलनविधि]] है जो किसी फलन के न्यूनतम को खोजने के लिए क्रमिक रूप से समन्वयित दिशाओं को कम करता है। प्रत्येक पुनरावृत्ति पर, कलनविधि समन्वय प्रणाली को निर्धारित करता है या समन्वय चयन नियम के माध्यम से समन्वय ब्लॉक करता है, फिर अन्य सभी निर्देशांक या समन्वय ब्लॉकों को ठीक करते समय संबंधित समन्वय हाइपरप्लेन पर ठीक या अनुचित विधि से कम करता है। उपयुक्त चरण आकार निर्धारित करने के लिए समन्वय प्रणाली दिशा के साथ लाइन खोज वर्तमान पुनरावृति पर की जा सकती है। समन्वय अवरोहण अलग-अलग और व्युत्पन्न-मुक्त दोनों संदर्भों में प्रयुक्त होता है।


== विवरण ==
== विवरण ==
समन्वय वंश इस विचार पर आधारित है कि एक बहुभिन्नरूपी कार्य का न्यूनीकरण <math>F(\mathbf{x})</math> इसे एक समय में एक दिशा में कम से कम करके प्राप्त किया जा सकता है, अर्थात, एक लूप में यूनीवेरिएट (या कम से कम बहुत सरल) अनुकूलन समस्याओं का समाधान करना।<ref name="wright">{{Cite journal |last=Wright |first=Stephen J. |title=Coordinate descent algorithms |journal=Mathematical Programming |volume=151 |issue=1 |year=2015 |pages=3–34 |arxiv=1502.04759 |doi=10.1007/s10107-015-0892-3|s2cid=15284973 }}</ref> चक्रीय समन्वय अवतरण के सबसे सरल स्थिति में, एक समय में एक दिशा के माध्यम से चक्रीय रूप से पुनरावृत्ति करता है, एक समय में प्रत्येक समन्वय दिशा के संबंध में उद्देश्य समारोह को कम करता है। यही है, प्रारंभिक चर मानों से प्रारंभ करना
समन्वय वंश इस विचार पर आधारित है कि बहुभिन्नरूपी कार्य का न्यूनीकरण <math>F(\mathbf{x})</math> इसे एक समय में एक दिशा में कम से कम करके प्राप्त किया जा सकता है, अर्थात, लूप में अविभाज्य (या कम से कम बहुत सरल) अनुकूलन समस्याओं का समाधान करना।<ref name="wright">{{Cite journal |last=Wright |first=Stephen J. |title=Coordinate descent algorithms |journal=Mathematical Programming |volume=151 |issue=1 |year=2015 |pages=3–34 |arxiv=1502.04759 |doi=10.1007/s10107-015-0892-3|s2cid=15284973 }}</ref> चक्रीय समन्वय अवतरण के सबसे सरल स्थिति में, एक समय में एक दिशा के माध्यम से चक्रीय रूप से पुनरावृत्ति करता है, समय में प्रत्येक समन्वय दिशा के संबंध में उद्देश्य समारोह को कम करता है। यही है, प्रारंभिक चर मानों से प्रारंभ करना


: <math>\mathbf{x}^0 = (x^0_1, \ldots, x^0_n)</math>,
: <math>\mathbf{x}^0 = (x^0_1, \ldots, x^0_n)</math>,


गोल <math>k+1</math>  <math>\mathbf{x}^{k+1}</math> से <math>\mathbf{x}^k</math> को एकल चर अनुकूलन समस्याओं को क्रमिक रूप से समाधान करके परिभाषित करता है '''<math>\mathbf{x}^{k+1}</math> से <math>\mathbf{x}^k</math> एकल चर अनुकूलन समस्याओं को क्रमिक रूप से समाधान करके'''
गोल <math>k+1</math>, <math>\mathbf{x}^{k+1}</math> से <math>\mathbf{x}^k</math> को एकल चर अनुकूलन समस्याओं को क्रमिक रूप से समाधान करके परिभाषित करता है  


:<math>x^{k+1}_i = \underset{y\in\mathbb R}{\operatorname{arg\,min}}\; f(x^{k+1}_1, \dots, x^{k+1}_{i-1}, y, x^k_{i+1}, \dots, x^k_n)</math><ref>https://www.cs.cmu.edu/~ggordon/10725-F12/slides/25-coord-desc.pdf {{Bare URL PDF|date=March 2022}}</ref>
<math>x^{k+1}_i = \underset{y\in\mathbb R}{\operatorname{arg\,min}}\; f(x^{k+1}_1, \dots, x^{k+1}_{i-1}, y, x^k_{i+1}, \dots, x^k_n)</math><ref>https://www.cs.cmu.edu/~ggordon/10725-F12/slides/25-coord-desc.pdf {{Bare URL PDF|date=March 2022}}</ref>
प्रत्येक चर के लिए <math>x_i</math> का <math>\mathbf{x}</math>, के लिए <math>i</math> 1 से <math>n</math>.


इस प्रकार, एक प्रारंभिक अनुमान के साथ प्रारंभ होता है <math>\mathbf{x}^0</math> स्थानीय न्यूनतम के लिए <math>F</math>, और एक क्रम प्राप्त करता है
प्रत्येक चर <math>x_i</math> का <math>\mathbf{x}</math> के लिए, <math>i</math> 1 से <math>n</math>.


<math>\mathbf{x}^0, \mathbf{x}^1, \mathbf{x}^2, \dots</math> पुनरावृत्त रूप से।
इस प्रकार, प्रारंभिक अनुमान के साथ प्रारंभ होता है <math>\mathbf{x}^0</math> स्थानीय न्यूनतम के लिए <math>F</math>, और अनुक्रम <math>\mathbf{x}^0, \mathbf{x}^1, \mathbf{x}^2, \dots</math> पुनरावृत्त रूप से प्राप्त करता है


प्रत्येक पुनरावृत्ति में लाइन खोज करने से, एक स्वचालित रूप से होता है
प्रत्येक पुनरावृत्ति में लाइन खोज करने से, स्वचालित रूप से होता है


:<math>F(\mathbf{x}^0)\ge F(\mathbf{x}^1)\ge F(\mathbf{x}^2)\ge \dots.</math>
:<math>F(\mathbf{x}^0)\ge F(\mathbf{x}^1)\ge F(\mathbf{x}^2)\ge \dots.</math>
यह दिखाया जा सकता है कि इस अनुक्रम में समान अभिसरण गुण हैं जैसे कि सबसे तेज वंश। समन्वय दिशाओं के साथ लाइन खोज के एक चक्र के बाद कोई संशोधन नहीं होने का अर्थ है कि एक स्थिर बिंदु तक पहुंच गया है।
यह दिखाया जा सकता है कि इस अनुक्रम में समान अभिसरण गुण हैं जैसे कि सबसे तेज वंश। समन्वय दिशाओं के साथ लाइन खोज के चक्र के बाद कोई संशोधन नहीं होने का अर्थ है कि स्थिर बिंदु तक पहुंच गया है।


यह प्रक्रिया नीचे सचित्र है।
यह प्रक्रिया नीचे सचित्र है।
Line 25: Line 24:


=== अलग स्थिति ===
=== अलग स्थिति ===
एक निरंतर भिन्न कार्य के स्थिति में {{mvar|F}}, एक समन्वय वंश एल्गोरिथ्म [[स्यूडोकोड]] के रूप में हो सकता है:{{r|wright}}
निरंतर भिन्न कार्य {{mvar|F}} के स्थिति में, समन्वय वंश कलनविधि को इस रूप में [[स्यूडोकोड|स्केच]] किया जा सकता है:{{r|wright}}
<div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >
<div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >
{{framebox|blue}}
{{framebox|blue}}
* प्रारंभिक पैरामीटर वेक्टर चुनें {{math|'''x'''}}.
* प्रारंभिक पैरामीटर सदिश चुनें {{math|'''x'''}}.
* जब तक अभिसरण नहीं हो जाता, या पुनरावृत्तियों की कुछ निश्चित संख्या के लिए:
* जब तक अभिसरण नहीं हो जाता, या पुनरावृत्तियों की कुछ निश्चित संख्या के लिए:
** एक इंडेक्स चुनें {{mvar|i}} से {{math|1}} को {{mvar|n}}.
** एक सूचकांक चुनें {{mvar|i}} से {{math|1}} को {{mvar|n}}.
** कदम का आकार चुनें {{mvar|α}}.
** कदम का आकार चुनें {{mvar|α}}.
** अद्यतन {{mvar|x<sub>i</sub>}} को {{math|''x<sub>i</sub>'' − {{mvar|α}}{{sfrac|∂''F''|∂''x<sub>i</sub>''}}('''x''')}}.
** अद्यतन {{mvar|x<sub>i</sub>}} को {{math|''x<sub>i</sub>'' − {{mvar|α}}{{sfrac|∂''F''|∂''x<sub>i</sub>''}}('''x''')}}.
Line 36: Line 35:
</div>
</div>


चरण आकार को विभिन्न विधियों से चुना जा सकता है, उदाहरण के लिए, स्पष्ट मिनिमाइज़र के लिए समाधान करके {{math|''f''(''x<sub>i</sub>'') {{=}} ''F''('''x''')}} (अर्थात।, {{mvar|F}} लेकिन सभी चर के साथ {{mvar|x<sub>i</sub>}} फ़िक्स्ड), या पारंपरिक लाइन खोज मानदंड द्वारा।{{r|wright}}
चरण आकार को विभिन्न विधियों से चुना जा सकता है, उदाहरण के लिए, स्पष्ट न्यूनतम के लिए समाधान करके {{math|''f''(''x<sub>i</sub>'') {{=}} ''F''('''x''')}} (अर्थात, {{mvar|F}} लेकिन सभी चर के साथ {{mvar|x<sub>i</sub>}} फ़िक्स्ड), या पारंपरिक लाइन खोज मानदंड द्वारा।{{r|wright}}




== सीमाएं ==
== सीमाएं ==
समन्वय वंश में दो समस्याएं हैं। उनमें से एक गैर-चिकनापन बहुभिन्नरूपी कार्य कर रहा है। निम्नलिखित चित्र से पता चलता है कि यदि किसी फलन के स्तर वक्र सुचारू नहीं हैं, तो समन्वय वंश पुनरावृत्ति एक गैर-[[स्थिर बिंदु]] पर अटक सकती है। मान लीजिए कि एल्गोरिदम बिंदु {{math|(-2, -2)}} पर है; फिर दो अक्ष-संरेखित दिशाएँ हैं जिन पर वह एक कदम उठाने के लिए विचार कर सकता है, जो लाल तीरों द्वारा इंगित किया गया है। चूँकि, इन दो दिशाओं के साथ हर कदम उद्देश्य समारोह के मूल्य में वृद्धि करेगा (न्यूनतमकरण समस्या मानते हुए), इसलिए एल्गोरिदम कोई कदम नहीं उठाएगा, तथापि दोनों कदम एक साथ एल्गोरिदम को इष्टतम के निकट लाएंगे। चूँकि इस उदाहरण से पता चलता है कि समन्वय वंश आवश्यक रूप से इष्टतम के लिए अभिसरण नहीं है, उचित परिस्थितियों में औपचारिक अभिसरण दिखाना संभव है।<ref>{{cite journal |last=Spall |first=J. C. |year=2012 |title=Cyclic Seesaw Process for Optimization and Identification |journal=Journal of Optimization Theory and Applications |volume=154 |issue=1 |pages=187–208 |doi=10.1007/s10957-012-0001-1 |s2cid=7795605 }}</ref>
समन्वय वंश में दो समस्याएं हैं। उनमें से गैर-चिकनापन बहुभिन्नरूपी कार्य कर रहा है। निम्नलिखित चित्र से पता चलता है कि यदि किसी फलन के स्तर वक्र सुचारू नहीं हैं, तो समन्वय वंश पुनरावृत्ति गैर-[[स्थिर बिंदु]] पर अटक सकती है। मान लीजिए कि कलनविधि बिंदु {{math|(-2, -2)}} पर है; फिर दो अक्ष-संरेखित दिशाएँ हैं जिन पर वह कदम उठाने के लिए विचार कर सकता है, जो लाल तीरों द्वारा इंगित किया गया है। चूँकि, इन दो दिशाओं के साथ हर कदम उद्देश्य समारोह के मूल्य में वृद्धि करेगा (न्यूनतमकरण समस्या मानते हुए), इसलिए कलनविधि कोई कदम नहीं उठाएगा, तथापि दोनों कदम एक साथ कलनविधि को इष्टतम के निकट लाएंगे। चूँकि इस उदाहरण से पता चलता है कि समन्वय वंश आवश्यक रूप से इष्टतम के लिए अभिसरण नहीं है, उचित परिस्थितियों में औपचारिक अभिसरण दिखाना संभव है।<ref>{{cite journal |last=Spall |first=J. C. |year=2012 |title=Cyclic Seesaw Process for Optimization and Identification |journal=Journal of Optimization Theory and Applications |volume=154 |issue=1 |pages=187–208 |doi=10.1007/s10957-012-0001-1 |s2cid=7795605 }}</ref>


[[File:Nonsmooth coordinate descent.svg|center|500px]]दूसरी समस्या समांतरता में कठिनाई है। चूंकि समन्वय वंश की प्रकृति दिशाओं के माध्यम से चक्रित करना है और प्रत्येक समन्वय दिशा के संबंध में उद्देश्य समारोह को कम करना है, इसलिए समन्वय वंश बड़े पैमाने पर समानता के लिए एक स्पष्ट प्रत्याशी नहीं है। हाल के शोध कार्यों से पता चला है कि बड़े पैमाने पर समानता प्रत्येक समन्वय दिशा के संबंध में उद्देश्य समारोह के परिवर्तन को सुविधा से समन्वयित करने के लिए प्रयुक्त होती है।<ref>{{Cite journal|last1=Zheng|first1=J.|last2=Saquib|first2=S. S.|last3=Sauer|first3=K.|last4=Bouman|first4=C. A.|date=2000-10-01|title=Parallelizable Bayesian tomography algorithms with rapid, guaranteed convergence|journal=IEEE Transactions on Image Processing|volume=9|issue=10|pages=1745–1759|doi=10.1109/83.869186|pmid=18262913|issn=1057-7149|bibcode=2000ITIP....9.1745Z|citeseerx=10.1.1.34.4282}}</ref><ref>{{Cite journal|last1=Fessler|first1=J. A.|last2=Ficaro|first2=E. P.|last3=Clinthorne|first3=N. H.|last4=Lange|first4=K.|date=1997-04-01|title=Grouped-coordinate ascent algorithms for penalized-likelihood transmission image reconstruction|journal=IEEE Transactions on Medical Imaging|volume=16|issue=2|pages=166–175|doi=10.1109/42.563662|pmid=9101326|issn=0278-0062|hdl=2027.42/86021|s2cid=1523517|hdl-access=free}}</ref><ref>{{Cite book|last1=Wang|first1=Xiao|last2=Sabne|first2=Amit|last3=Kisner|first3=Sherman|last4=Raghunathan|first4=Anand|last5=Bouman|first5=Charles|last6=Midkiff|first6=Samuel|date=2016-01-01|title=High Performance Model Based Image Reconstruction|journal=Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming|series=PPoPP '16|location=New York, NY, USA|publisher=ACM|pages=2:1–2:12|doi=10.1145/2851141.2851163|isbn=9781450340922|s2cid=16569156|url=https://zenodo.org/record/895136}}</ref>
[[File:Nonsmooth coordinate descent.svg|center|500px]]दूसरी समस्या, समांतरता में कठिनाई है। चूंकि समन्वय वंश की प्रकृति दिशाओं के माध्यम से चक्रित करना है और प्रत्येक समन्वय दिशा के संबंध में वस्तुनिष्ठ कार्य को कम करना है, इसलिए समन्वय वंश बड़े पैमाने पर समानता के लिए स्पष्ट प्रत्याशी नहीं है। हाल के शोध कार्यों से पता चला है कि बड़े पैमाने पर समानता प्रत्येक समन्वय दिशा के संबंध में वस्तुनिष्ठ कार्य के परिवर्तन को सुविधा से समन्वयित करने के लिए प्रयुक्त होती है।<ref>{{Cite journal|last1=Zheng|first1=J.|last2=Saquib|first2=S. S.|last3=Sauer|first3=K.|last4=Bouman|first4=C. A.|date=2000-10-01|title=Parallelizable Bayesian tomography algorithms with rapid, guaranteed convergence|journal=IEEE Transactions on Image Processing|volume=9|issue=10|pages=1745–1759|doi=10.1109/83.869186|pmid=18262913|issn=1057-7149|bibcode=2000ITIP....9.1745Z|citeseerx=10.1.1.34.4282}}</ref><ref>{{Cite journal|last1=Fessler|first1=J. A.|last2=Ficaro|first2=E. P.|last3=Clinthorne|first3=N. H.|last4=Lange|first4=K.|date=1997-04-01|title=Grouped-coordinate ascent algorithms for penalized-likelihood transmission image reconstruction|journal=IEEE Transactions on Medical Imaging|volume=16|issue=2|pages=166–175|doi=10.1109/42.563662|pmid=9101326|issn=0278-0062|hdl=2027.42/86021|s2cid=1523517|hdl-access=free}}</ref><ref>{{Cite book|last1=Wang|first1=Xiao|last2=Sabne|first2=Amit|last3=Kisner|first3=Sherman|last4=Raghunathan|first4=Anand|last5=Bouman|first5=Charles|last6=Midkiff|first6=Samuel|date=2016-01-01|title=High Performance Model Based Image Reconstruction|journal=Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming|series=PPoPP '16|location=New York, NY, USA|publisher=ACM|pages=2:1–2:12|doi=10.1145/2851141.2851163|isbn=9781450340922|s2cid=16569156|url=https://zenodo.org/record/895136}}</ref>




== अनुप्रयोग ==
== अनुप्रयोग ==
समन्वय वंश एल्गोरिथम अपनी सरलता के कारण चिकित्सकों के बीच लोकप्रिय हैं, लेकिन इसी गुण ने अनुकूलन शोधकर्ताओं को अधिक रोचक (जटिल) विधियों के पक्ष में बड़े पैमाने पर उनकी उपेक्षा करने के लिए प्रेरित किया है।{{r|wright}} कंप्यूटेड टोमोग्राफी के क्षेत्र में समन्वय वंश अनुकूलन का एक प्रारंभिक अनुप्रयोग था<ref>{{cite journal|last1=Sauer|first1=Ken|last2=Bouman|first2=Charles|title=A Local Update Strategy for Iterative Reconstruction from Projections|journal= IEEE Transactions on Signal Processing|date=February 1993|volume=41|issue=2|pages=534–548|doi=10.1109/78.193196|url=https://engineering.purdue.edu/~bouman/publications/orig-pdf/sp2.pdf|bibcode=1993ITSP...41..534S|citeseerx=10.1.1.135.6045}}</ref> जहां यह शीघ्रता से अभिसरण पाया गया है<ref>{{cite journal|last1=Yu|first1=Zhou|last2=Thibault|first2=Jean-Baptiste|last3=Bouman|first3=Charles|last4=Sauer|first4=Ken|last5=Hsieh|first5=Jiang|title=Fast Model-Based X-ray CT Reconstruction Using Spatially Non-Homogeneous ICD Optimization|journal=IEEE Transactions on Image Processing|date=January 2011|volume=20|issue=1|pages=161–175|doi=10.1109/TIP.2010.2058811|pmid=20643609|url=https://engineering.purdue.edu/~bouman/publications/orig-pdf/tip28.pdf|bibcode=2011ITIP...20..161Y|s2cid=9315957}}</ref> और बाद में क्लिनिकल मल्टी-स्लाइस हेलिकल स्कैन सीटी पुनर्निर्माण के लिए उपयोग किया गया।<ref>{{cite journal|last1=Thibault|first1=Jean-Baptiste|last2=Sauer|first2=Ken|last3=Bouman|first3=Charles|last4=Hsieh|first4=Jiang|title=A Three-Dimensional Statistical Approach to Improved Image Quality for Multi-Slice Helical CT|journal=Medical Physics|date=November 2007|volume=34|issue=11|pages=4526–4544|doi=10.1118/1.2789499|pmid=18072519|url=https://engineering.purdue.edu/~bouman/publications/orig-pdf/medphys1.pdf|bibcode=2007MedPh..34.4526T}}</ref> प्रोटीन संरचना भविष्यवाणी में एक चक्रीय समन्वय वंश एल्गोरिथ्म (सीसीडी) प्रयुक्त किया गया है।<ref>{{Cite journal|last1=Canutescu|first1=AA|last2=Dunbrack|first2=RL|title=Cyclic coordinate descent: A robotics algorithm for protein loop closure.|periodical=Protein Science|year=2003|volume=12|issue=5|pages=963–72|pmid=12717019|doi=10.1110/ps.0242703|pmc=2323867}}</ref> इसके अतिरिक्त, मशीन सीखने में बड़े पैमाने पर समस्याओं के आगमन के साथ समन्वय वंश के उपयोग में रुचि बढ़ गई है, जहां रैखिक [[समर्थन वेक्टर यंत्र]] को प्रशिक्षित करने जैसी समस्याओं पर प्रयुक्त होने पर समन्वय वंश को अन्य विधियों के लिए प्रतिस्पर्धी दिखाया गया है।<ref>{{Cite book | last1 = Hsieh | first1 = C. J. | last2 = Chang | first2 = K. W. | last3 = Lin | first3 = C. J. | last4 = Keerthi | first4 = S. S. | last5 = Sundararajan | first5 = S. | doi = 10.1145/1390156.1390208 | chapter = A dual coordinate descent method for large-scale linear SVM | title = Proceedings of the 25th international conference on Machine learning - ICML '08 | pages = 408 | year = 2008 | isbn = 9781605582054 | s2cid = 7880266 | chapter-url = http://ntu.csie.org/~cjlin/papers/cddual.pdf}}</ref> ([[LIBLINEAR|लिब्लिनियर]] और [[गैर-नकारात्मक मैट्रिक्स गुणनखंड|गैर-नकारात्मक मैट्रिक्स गुणनखंडन]] देखें)।<ref>{{Cite conference | last1 = Hsieh | first1 = C. J. | last2 = Dhillon | first2 = I. S. | doi = 10.1145/2020408.2020577 | title = Fast coordinate descent methods with variable selection for non-negative matrix factorization | conference = Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11 | pages = 1064| year = 2011 | isbn = 9781450308137 | url = http://www.cs.utexas.edu/~cjhsieh/nmf_kdd11.pdf}}</ref> वे उन समस्याओं के लिए आकर्षक हैं जहां प्रवणता की गणना करना संभव नहीं है, संभवतया इसलिए कि ऐसा करने के लिए आवश्यक डेटा कंप्यूटर नेटवर्क में वितरित किया जाता है।<ref>{{cite journal |last=Nesterov |first=Yurii |author-link=Yurii Nesterov |title=Efficiency of coordinate descent methods on huge-scale optimization problems |journal=SIAM J. Optim. |volume=22 |issue=2 |year=2012 |pages=341–362 |url=http://www.ulouvain.be/cps/ucl/doc/core/documents/coredp2010_2web.pdf |doi=10.1137/100802001|citeseerx=10.1.1.332.3336 }}</ref>
समन्वय वंश कलनविधि अपनी सरलता के कारण चिकित्सकों के बीच लोकप्रिय हैं, लेकिन इसी गुण ने अनुकूलन शोधकर्ताओं को अधिक रोचक (जटिल) विधियों के पक्ष में बड़े पैमाने पर उनकी उपेक्षा करने के लिए प्रेरित किया है।{{r|wright}} परिकलित टोमोग्राफी के क्षेत्र में समन्वय वंश अनुकूलन का प्रारंभिक अनुप्रयोग था<ref>{{cite journal|last1=Sauer|first1=Ken|last2=Bouman|first2=Charles|title=A Local Update Strategy for Iterative Reconstruction from Projections|journal= IEEE Transactions on Signal Processing|date=February 1993|volume=41|issue=2|pages=534–548|doi=10.1109/78.193196|url=https://engineering.purdue.edu/~bouman/publications/orig-pdf/sp2.pdf|bibcode=1993ITSP...41..534S|citeseerx=10.1.1.135.6045}}</ref> जहां यह शीघ्रता से अभिसरण पाया गया है<ref>{{cite journal|last1=Yu|first1=Zhou|last2=Thibault|first2=Jean-Baptiste|last3=Bouman|first3=Charles|last4=Sauer|first4=Ken|last5=Hsieh|first5=Jiang|title=Fast Model-Based X-ray CT Reconstruction Using Spatially Non-Homogeneous ICD Optimization|journal=IEEE Transactions on Image Processing|date=January 2011|volume=20|issue=1|pages=161–175|doi=10.1109/TIP.2010.2058811|pmid=20643609|url=https://engineering.purdue.edu/~bouman/publications/orig-pdf/tip28.pdf|bibcode=2011ITIP...20..161Y|s2cid=9315957}}</ref> और बाद में नैदानिक बहु-स्लाइस हेलिकल स्कैन सीटी पुनर्निर्माण के लिए उपयोग किया गया।<ref>{{cite journal|last1=Thibault|first1=Jean-Baptiste|last2=Sauer|first2=Ken|last3=Bouman|first3=Charles|last4=Hsieh|first4=Jiang|title=A Three-Dimensional Statistical Approach to Improved Image Quality for Multi-Slice Helical CT|journal=Medical Physics|date=November 2007|volume=34|issue=11|pages=4526–4544|doi=10.1118/1.2789499|pmid=18072519|url=https://engineering.purdue.edu/~bouman/publications/orig-pdf/medphys1.pdf|bibcode=2007MedPh..34.4526T}}</ref> प्रोटीन संरचना भविष्यवाणी में चक्रीय समन्वय वंश कलनविधि (सीसीडी) प्रयुक्त किया गया है।<ref>{{Cite journal|last1=Canutescu|first1=AA|last2=Dunbrack|first2=RL|title=Cyclic coordinate descent: A robotics algorithm for protein loop closure.|periodical=Protein Science|year=2003|volume=12|issue=5|pages=963–72|pmid=12717019|doi=10.1110/ps.0242703|pmc=2323867}}</ref> इसके अतिरिक्त, मशीन सीखने में बड़े पैमाने पर समस्याओं के आगमन के साथ समन्वय वंश के उपयोग में रुचि बढ़ गई है, जहां रैखिक [[समर्थन वेक्टर यंत्र|समर्थन सदिश यंत्र]] को प्रशिक्षित करने जैसी समस्याओं पर प्रयुक्त होने पर समन्वय वंश को अन्य विधियों के लिए प्रतिस्पर्धी दिखाया गया है।<ref>{{Cite book | last1 = Hsieh | first1 = C. J. | last2 = Chang | first2 = K. W. | last3 = Lin | first3 = C. J. | last4 = Keerthi | first4 = S. S. | last5 = Sundararajan | first5 = S. | doi = 10.1145/1390156.1390208 | chapter = A dual coordinate descent method for large-scale linear SVM | title = Proceedings of the 25th international conference on Machine learning - ICML '08 | pages = 408 | year = 2008 | isbn = 9781605582054 | s2cid = 7880266 | chapter-url = http://ntu.csie.org/~cjlin/papers/cddual.pdf}}</ref> ([[LIBLINEAR|लिब्लिनियर]] और [[गैर-नकारात्मक मैट्रिक्स गुणनखंड|गैर-नकारात्मक आव्यूह गुणनखंडन]] देखें)।<ref>{{Cite conference | last1 = Hsieh | first1 = C. J. | last2 = Dhillon | first2 = I. S. | doi = 10.1145/2020408.2020577 | title = Fast coordinate descent methods with variable selection for non-negative matrix factorization | conference = Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11 | pages = 1064| year = 2011 | isbn = 9781450308137 | url = http://www.cs.utexas.edu/~cjhsieh/nmf_kdd11.pdf}}</ref> वे उन समस्याओं के लिए आकर्षक हैं जहां प्रवणता की गणना करना संभव नहीं है, संभवतया इसलिए कि ऐसा करने के लिए आवश्यक डेटा कंप्यूटर नेटवर्क में वितरित किया जाता है।<ref>{{cite journal |last=Nesterov |first=Yurii |author-link=Yurii Nesterov |title=Efficiency of coordinate descent methods on huge-scale optimization problems |journal=SIAM J. Optim. |volume=22 |issue=2 |year=2012 |pages=341–362 |url=http://www.ulouvain.be/cps/ucl/doc/core/documents/coredp2010_2web.pdf |doi=10.1137/100802001|citeseerx=10.1.1.332.3336 }}</ref>




Line 56: Line 55:
* [[गणितीय अनुकूलन]]
* [[गणितीय अनुकूलन]]
* अनुकूलन में न्यूटन की विधि | न्यूटन की विधि
* अनुकूलन में न्यूटन की विधि | न्यूटन की विधि
* [[स्टोचैस्टिक ग्रेडिएंट डिसेंट|स्टोचैस्टिक प्रवणता डिसेंट]] - एक समन्वय के अतिरिक्त एक समय में एक उदाहरण का उपयोग करता है
* [[स्टोचैस्टिक ग्रेडिएंट डिसेंट|स्टोचैस्टिक प्रवणता डिसेंट]] - समन्वय के अतिरिक्त एक समय में एक उदाहरण का उपयोग करता है


==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}
<!--- After listing your sources please cite them using inline citations and place them after the information they cite. Please see http://en.wikipedia.org/wiki/Wikipedia:REFB for instructions on how to add citations. --->
*{{Citation
*{{Citation
  | last1=Bezdek
  | last1=Bezdek
Line 145: Line 142:


{{Optimization algorithms}}
{{Optimization algorithms}}
[[Category: ग्रेडिएंट तरीके]]


[[Category: Machine Translated Page]]
[[Category:All articles with bare URLs for citations]]
[[Category:Articles with PDF format bare URLs for citations]]
[[Category:Articles with bare URLs for citations from March 2022]]
[[Category:Collapse templates]]
[[Category:Created On 13/02/2023]]
[[Category:Created On 13/02/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:ग्रेडिएंट तरीके]]

Latest revision as of 10:40, 21 February 2023

समन्वय वंश अनुकूलन कलनविधि है जो किसी फलन के न्यूनतम को खोजने के लिए क्रमिक रूप से समन्वयित दिशाओं को कम करता है। प्रत्येक पुनरावृत्ति पर, कलनविधि समन्वय प्रणाली को निर्धारित करता है या समन्वय चयन नियम के माध्यम से समन्वय ब्लॉक करता है, फिर अन्य सभी निर्देशांक या समन्वय ब्लॉकों को ठीक करते समय संबंधित समन्वय हाइपरप्लेन पर ठीक या अनुचित विधि से कम करता है। उपयुक्त चरण आकार निर्धारित करने के लिए समन्वय प्रणाली दिशा के साथ लाइन खोज वर्तमान पुनरावृति पर की जा सकती है। समन्वय अवरोहण अलग-अलग और व्युत्पन्न-मुक्त दोनों संदर्भों में प्रयुक्त होता है।

विवरण

समन्वय वंश इस विचार पर आधारित है कि बहुभिन्नरूपी कार्य का न्यूनीकरण इसे एक समय में एक दिशा में कम से कम करके प्राप्त किया जा सकता है, अर्थात, लूप में अविभाज्य (या कम से कम बहुत सरल) अनुकूलन समस्याओं का समाधान करना।[1] चक्रीय समन्वय अवतरण के सबसे सरल स्थिति में, एक समय में एक दिशा के माध्यम से चक्रीय रूप से पुनरावृत्ति करता है, समय में प्रत्येक समन्वय दिशा के संबंध में उद्देश्य समारोह को कम करता है। यही है, प्रारंभिक चर मानों से प्रारंभ करना

,

गोल , से को एकल चर अनुकूलन समस्याओं को क्रमिक रूप से समाधान करके परिभाषित करता है

[2]

प्रत्येक चर का के लिए, 1 से .

इस प्रकार, प्रारंभिक अनुमान के साथ प्रारंभ होता है स्थानीय न्यूनतम के लिए , और अनुक्रम पुनरावृत्त रूप से प्राप्त करता है

प्रत्येक पुनरावृत्ति में लाइन खोज करने से, स्वचालित रूप से होता है

यह दिखाया जा सकता है कि इस अनुक्रम में समान अभिसरण गुण हैं जैसे कि सबसे तेज वंश। समन्वय दिशाओं के साथ लाइन खोज के चक्र के बाद कोई संशोधन नहीं होने का अर्थ है कि स्थिर बिंदु तक पहुंच गया है।

यह प्रक्रिया नीचे सचित्र है।

Coordinate descent.svg

अलग स्थिति

निरंतर भिन्न कार्य F के स्थिति में, समन्वय वंश कलनविधि को इस रूप में स्केच किया जा सकता है:[1]

  • प्रारंभिक पैरामीटर सदिश चुनें x.
  • जब तक अभिसरण नहीं हो जाता, या पुनरावृत्तियों की कुछ निश्चित संख्या के लिए:
    • एक सूचकांक चुनें i से 1 को n.
    • कदम का आकार चुनें α.
    • अद्यतन xi को xi − α∂F/∂xi(x).

चरण आकार को विभिन्न विधियों से चुना जा सकता है, उदाहरण के लिए, स्पष्ट न्यूनतम के लिए समाधान करके f(xi) = F(x) (अर्थात, F लेकिन सभी चर के साथ xi फ़िक्स्ड), या पारंपरिक लाइन खोज मानदंड द्वारा।[1]


सीमाएं

समन्वय वंश में दो समस्याएं हैं। उनमें से गैर-चिकनापन बहुभिन्नरूपी कार्य कर रहा है। निम्नलिखित चित्र से पता चलता है कि यदि किसी फलन के स्तर वक्र सुचारू नहीं हैं, तो समन्वय वंश पुनरावृत्ति गैर-स्थिर बिंदु पर अटक सकती है। मान लीजिए कि कलनविधि बिंदु (-2, -2) पर है; फिर दो अक्ष-संरेखित दिशाएँ हैं जिन पर वह कदम उठाने के लिए विचार कर सकता है, जो लाल तीरों द्वारा इंगित किया गया है। चूँकि, इन दो दिशाओं के साथ हर कदम उद्देश्य समारोह के मूल्य में वृद्धि करेगा (न्यूनतमकरण समस्या मानते हुए), इसलिए कलनविधि कोई कदम नहीं उठाएगा, तथापि दोनों कदम एक साथ कलनविधि को इष्टतम के निकट लाएंगे। चूँकि इस उदाहरण से पता चलता है कि समन्वय वंश आवश्यक रूप से इष्टतम के लिए अभिसरण नहीं है, उचित परिस्थितियों में औपचारिक अभिसरण दिखाना संभव है।[3]

Nonsmooth coordinate descent.svg

दूसरी समस्या, समांतरता में कठिनाई है। चूंकि समन्वय वंश की प्रकृति दिशाओं के माध्यम से चक्रित करना है और प्रत्येक समन्वय दिशा के संबंध में वस्तुनिष्ठ कार्य को कम करना है, इसलिए समन्वय वंश बड़े पैमाने पर समानता के लिए स्पष्ट प्रत्याशी नहीं है। हाल के शोध कार्यों से पता चला है कि बड़े पैमाने पर समानता प्रत्येक समन्वय दिशा के संबंध में वस्तुनिष्ठ कार्य के परिवर्तन को सुविधा से समन्वयित करने के लिए प्रयुक्त होती है।[4][5][6]


अनुप्रयोग

समन्वय वंश कलनविधि अपनी सरलता के कारण चिकित्सकों के बीच लोकप्रिय हैं, लेकिन इसी गुण ने अनुकूलन शोधकर्ताओं को अधिक रोचक (जटिल) विधियों के पक्ष में बड़े पैमाने पर उनकी उपेक्षा करने के लिए प्रेरित किया है।[1] परिकलित टोमोग्राफी के क्षेत्र में समन्वय वंश अनुकूलन का प्रारंभिक अनुप्रयोग था[7] जहां यह शीघ्रता से अभिसरण पाया गया है[8] और बाद में नैदानिक बहु-स्लाइस हेलिकल स्कैन सीटी पुनर्निर्माण के लिए उपयोग किया गया।[9] प्रोटीन संरचना भविष्यवाणी में चक्रीय समन्वय वंश कलनविधि (सीसीडी) प्रयुक्त किया गया है।[10] इसके अतिरिक्त, मशीन सीखने में बड़े पैमाने पर समस्याओं के आगमन के साथ समन्वय वंश के उपयोग में रुचि बढ़ गई है, जहां रैखिक समर्थन सदिश यंत्र को प्रशिक्षित करने जैसी समस्याओं पर प्रयुक्त होने पर समन्वय वंश को अन्य विधियों के लिए प्रतिस्पर्धी दिखाया गया है।[11] (लिब्लिनियर और गैर-नकारात्मक आव्यूह गुणनखंडन देखें)।[12] वे उन समस्याओं के लिए आकर्षक हैं जहां प्रवणता की गणना करना संभव नहीं है, संभवतया इसलिए कि ऐसा करने के लिए आवश्यक डेटा कंप्यूटर नेटवर्क में वितरित किया जाता है।[13]


यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 Wright, Stephen J. (2015). "Coordinate descent algorithms". Mathematical Programming. 151 (1): 3–34. arXiv:1502.04759. doi:10.1007/s10107-015-0892-3. S2CID 15284973.
  2. ↑ https://www.cs.cmu.edu/~ggordon/10725-F12/slides/25-coord-desc.pdf[bare URL PDF]
  3. ↑ Spall, J. C. (2012). "Cyclic Seesaw Process for Optimization and Identification". Journal of Optimization Theory and Applications. 154 (1): 187–208. doi:10.1007/s10957-012-0001-1. S2CID 7795605.
  4. ↑ Zheng, J.; Saquib, S. S.; Sauer, K.; Bouman, C. A. (2000-10-01). "Parallelizable Bayesian tomography algorithms with rapid, guaranteed convergence". IEEE Transactions on Image Processing. 9 (10): 1745–1759. Bibcode:2000ITIP....9.1745Z. CiteSeerX 10.1.1.34.4282. doi:10.1109/83.869186. ISSN 1057-7149. PMID 18262913.
  5. ↑ Fessler, J. A.; Ficaro, E. P.; Clinthorne, N. H.; Lange, K. (1997-04-01). "Grouped-coordinate ascent algorithms for penalized-likelihood transmission image reconstruction". IEEE Transactions on Medical Imaging. 16 (2): 166–175. doi:10.1109/42.563662. hdl:2027.42/86021. ISSN 0278-0062. PMID 9101326. S2CID 1523517.
  6. ↑ Wang, Xiao; Sabne, Amit; Kisner, Sherman; Raghunathan, Anand; Bouman, Charles; Midkiff, Samuel (2016-01-01). High Performance Model Based Image Reconstruction. pp. 2:1–2:12. doi:10.1145/2851141.2851163. ISBN 9781450340922. S2CID 16569156. {{cite book}}: |journal= ignored (help)
  7. ↑ Sauer, Ken; Bouman, Charles (February 1993). "A Local Update Strategy for Iterative Reconstruction from Projections" (PDF). IEEE Transactions on Signal Processing. 41 (2): 534–548. Bibcode:1993ITSP...41..534S. CiteSeerX 10.1.1.135.6045. doi:10.1109/78.193196.
  8. ↑ Yu, Zhou; Thibault, Jean-Baptiste; Bouman, Charles; Sauer, Ken; Hsieh, Jiang (January 2011). "Fast Model-Based X-ray CT Reconstruction Using Spatially Non-Homogeneous ICD Optimization" (PDF). IEEE Transactions on Image Processing. 20 (1): 161–175. Bibcode:2011ITIP...20..161Y. doi:10.1109/TIP.2010.2058811. PMID 20643609. S2CID 9315957.
  9. ↑ Thibault, Jean-Baptiste; Sauer, Ken; Bouman, Charles; Hsieh, Jiang (November 2007). "A Three-Dimensional Statistical Approach to Improved Image Quality for Multi-Slice Helical CT" (PDF). Medical Physics. 34 (11): 4526–4544. Bibcode:2007MedPh..34.4526T. doi:10.1118/1.2789499. PMID 18072519.
  10. ↑ Canutescu, AA; Dunbrack, RL (2003). "Cyclic coordinate descent: A robotics algorithm for protein loop closure". Protein Science. 12 (5): 963–72. doi:10.1110/ps.0242703. PMC 2323867. PMID 12717019.
  11. ↑ Hsieh, C. J.; Chang, K. W.; Lin, C. J.; Keerthi, S. S.; Sundararajan, S. (2008). "A dual coordinate descent method for large-scale linear SVM" (PDF). Proceedings of the 25th international conference on Machine learning - ICML '08. p. 408. doi:10.1145/1390156.1390208. ISBN 9781605582054. S2CID 7880266.
  12. ↑ Hsieh, C. J.; Dhillon, I. S. (2011). Fast coordinate descent methods with variable selection for non-negative matrix factorization (PDF). Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11. p. 1064. doi:10.1145/2020408.2020577. ISBN 9781450308137.
  13. ↑ Nesterov, Yurii (2012). "Efficiency of coordinate descent methods on huge-scale optimization problems" (PDF). SIAM J. Optim. 22 (2): 341–362. CiteSeerX 10.1.1.332.3336. doi:10.1137/100802001.
  • Bezdek, J. C.; Hathaway, R. J.; Howard, R. E.; Wilson, C. A.; Windham, M. P. (1987), "Local convergence analysis of a grouped variable version of coordinate descent", Journal of Optimization Theory and Applications, Kluwer Academic/Plenum Publishers, vol. 54, no. 3, pp. 471–477, doi:10.1007/BF00940196, S2CID 120052975
  • Bertsekas, Dimitri P. (1999). Nonlinear Programming, Second Edition Athena Scientific, Belmont, Massachusetts. ISBN 1-886529-00-0.
  • Luo, Zhiquan; Tseng, P. (1992), "On the convergence of the coordinate descent method for convex differentiable minimization", Journal of Optimization Theory and Applications, Kluwer Academic/Plenum Publishers, vol. 72, no. 1, pp. 7–35, doi:10.1007/BF00939948, hdl:1721.1/3164, S2CID 121091844.
  • Wu, TongTong; Lange, Kenneth (2008), "Coordinate descent algorithms for Lasso penalized regression", The Annals of Applied Statistics, Institute of Mathematical Statistics, vol. 2, no. 1, pp. 224–244, arXiv:0803.3876, doi:10.1214/07-AOAS147, S2CID 16350311.
  • Richtarik, Peter; Takac, Martin (April 2011), "Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function", Mathematical Programming, Springer, vol. 144, no. 1–2, pp. 1–38, arXiv:1107.2848, doi:10.1007/s10107-012-0614-z, S2CID 16816638.
  • Richtarik, Peter; Takac, Martin (December 2012), "Parallel coordinate descent methods for big data optimization", ArXiv:1212.0873, arXiv:1212.0873.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

| below =

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

| below =* सॉफ्टवेयर

}}

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=समन्वय_वंश&oldid=92609’