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

From Vigyanwiki
(Created page with "निर्देशांक तरीका एक अनुकूलन एल्गोरिथ्म है जो किसी फ़ंक्शन के न...")
 
No edit summary
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>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>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>x_i</math> का <math>\mathbf{x}</math>, के लिए <math>i</math> 1 से <math>n</math>.


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


Line 17: Line 18:


:<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 23: Line 24:
[[File:Coordinate descent.svg|center|500px]]
[[File:Coordinate descent.svg|center|500px]]


=== अलग मामला ===
=== अलग स्थिति ===
एक निरंतर भिन्न कार्य के मामले में {{mvar|F}}, एक समन्वय वंश एल्गोरिथ्म [[स्यूडोकोड]] के रूप में हो सकता है:{{r|wright}}
एक निरंतर भिन्न कार्य के स्थिति में {{mvar|F}}, एक समन्वय वंश एल्गोरिथ्म [[स्यूडोकोड]] के रूप में हो सकता है:{{r|wright}}
<div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >
<div स्टाइल = मार्जिन-लेफ्ट: 35px; चौड़ाई: 600 पीएक्स >
{{framebox|blue}}
{{framebox|blue}}
Line 35: Line 36:
</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 55: Line 56:
* [[गणितीय अनुकूलन]]
* [[गणितीय अनुकूलन]]
* अनुकूलन में न्यूटन की विधि | न्यूटन की विधि
* अनुकूलन में न्यूटन की विधि | न्यूटन की विधि
* [[स्टोचैस्टिक ग्रेडिएंट डिसेंट]] - एक समन्वय के बजाय एक समय में एक उदाहरण का उपयोग करता है
* [[स्टोचैस्टिक ग्रेडिएंट डिसेंट|स्टोचैस्टिक प्रवणता डिसेंट]] - एक समन्वय के अतिरिक्त एक समय में एक उदाहरण का उपयोग करता है


==संदर्भ==
==संदर्भ==

Revision as of 12:59, 16 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=91910’