सुचारु विश्लेषण

बेतरतीब ढंग से उत्पन्न बिटमैप सामान्य चित्रों जैसा नहीं होता है।

एक सामान्य चित्र किसी यादृच्छिक बिटमैप जैसा नहीं होता.

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

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

यद्यपि सबसे खराब स्थिति का विश्लेषण कई एल्गोरिदम के व्यावहारिक प्रदर्शन को समझाने में व्यापक रूप से सफल रहा है, विश्लेषण की यह शैली कई समस्याओं के लिए भ्रामक परिणाम देती है। सबसे खराब स्थिति की जटिलता किसी भी इनपुट को हल करने में लगने वाले समय को मापती है, हालांकि हल करने में मुश्किल इनपुट व्यवहार में कभी नहीं आ सकते हैं। ऐसे मामलों में, सबसे खराब स्थिति में चलने का समय व्यवहार में देखे गए चलने के समय से कहीं अधिक खराब हो सकता है। उदाहरण के लिए, सिम्प्लेक्स एल्गोरिथ्म का उपयोग करके एक रैखिक कार्यक्रम को हल करने की सबसे खराब स्थिति जटिलता घातीय है,हालाँकि व्यवहार में चरणों की देखी गई संख्या मोटे तौर पर रैखिक है।सिम्पलेक्स एल्गोरिथ्म वास्तव में व्यवहार में दीर्घवृत्ताकार विधि की तुलना में बहुत तेज़ है, हालांकि उत्तरार्द्ध में कमजोर बहुपद|बहुपद-समय की सबसे खराब स्थिति वाली जटिलता है।

औसत-केस विश्लेषण सबसे पहले सबसे खराब-केस विश्लेषण की सीमाओं को दूर करने के लिए पेश किया गया था। हालाँकि, परिणामी औसत-मामले की जटिलता इनपुट पर चुने गए संभाव्यता वितरण पर बहुत अधिक निर्भर करती है। व्यवहार में वास्तविक इनपुट और इनपुट का वितरण विश्लेषण के दौरान बनाई गई धारणाओं से भिन्न हो सकता है: एक यादृच्छिक इनपुट एक विशिष्ट इनपुट से बहुत भिन्न हो सकता है। डेटा मॉडल की इस पसंद के कारण, सैद्धांतिक औसत-मामले का परिणाम एल्गोरिदम के व्यावहारिक प्रदर्शन के बारे में बहुत कम कह सकता है।

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

इतिहास

संगणक तंत्र संस्था और ईएटीसीएस ने सुचारू विश्लेषण विकसित करने के लिए डेनियल स्पीलमैन और शांग ड्रा टी को 2008 गोडेल पुरस्कार से सम्मानित किया। स्मूथेड एनालिसिस नाम एलन एडेलमैन द्वारा गढ़ा गया था।2010 में स्पीलमैन को सुचारु विश्लेषण विकसित करने के लिए नेवानलिन्ना पुरस्कार मिला। स्पीलमैन और टेंग का जेएसीएम पेपर एल्गोरिदम का सहज विश्लेषण: सिम्प्लेक्स एल्गोरिदम आमतौर पर बहुपद समय क्यों लेता है, गणितीय प्रोग्रामिंग सोसायटी (एमपीएस) और अमेरिकन गणितीय सोसाइटी (एएमएस) द्वारा संयुक्त रूप से प्रायोजित 2009 फुलकर्सन पुरस्कार के तीन विजेताओं में से एक था।

उदाहरण

रैखिक प्रोग्रामिंग के लिए सिंप्लेक्स एल्गोरिदम

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

गड़बड़ी मॉडल के लिए, हम मानते हैं कि इनपुट डेटा गाऊसी वितरण से शोर से परेशान है। सामान्यीकरण उद्देश्यों के लिए, हम अप्रभावित डेटा मानते हैं ${\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n},\mathbf {c} \in \mathbb {R} ^{d}$ संतुष्ट $\|({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})\|_{2}\leq 1$ सभी पंक्तियों के लिए $({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})$ मैट्रिक्स का $({\bar {\mathbf {A} }},{\bar {\mathbf {b} }}).$ ये शोर $({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})$ माध्य के साथ गाऊसी वितरण से नमूना की गई स्वतंत्र प्रविष्टियाँ हैं $0$ और मानक विचलन $\sigma$. हमलोग तैयार हैं $\mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }}+{\hat {\mathbf {b} }}$. सुचारू इनपुट डेटा में रैखिक प्रोग्राम शामिल होता है

अधिकतम करें

$\mathbf {c^{T}} \cdot \mathbf {x}$

का विषय है

$\mathbf {A} \mathbf {x} \leq \mathbf {b}$.

यदि डेटा पर हमारे एल्गोरिदम का चलने का समय $\mathbf {A} ,\mathbf {b} ,\mathbf {c}$ द्वारा दिया गया है $T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )$ तो सिंप्लेक्स विधि की सहज जटिलता है

$C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}[T({\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},{\bar {\mathbf {b} }}+{\hat {\mathbf {b} }},\mathbf {c} )]={\rm {poly}}(d,\log n,\sigma ^{-1}).$

यह सीमा एक विशिष्ट धुरी नियम के लिए है जिसे छाया शीर्ष नियम कहा जाता है। शैडो वर्टेक्स नियम आमतौर पर उपयोग किए जाने वाले धुरी नियमों जैसे कि डेंटज़िग नियम या सबसे तेज किनारे वाले नियम की तुलना में धीमा हैलेकिन इसमें ऐसे गुण हैं जो इसे संभाव्य विश्लेषण के लिए बहुत उपयुक्त बनाते हैं।

संयुक्त अनुकूलन के लिए स्थानीय खोज

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

समस्या उदाहरणों का एक वर्ग दिया जा सकता है $n$ बॉक्स में अंक $[0,1]^{d}$, जहां उनकी जोड़ीदार दूरियां एक नॉर्म (गणित) से आती हैं। पहले से ही दो आयामों में, 2-ऑप्ट अनुमान स्थानीय इष्टतम खोजने तक तेजी से कई पुनरावृत्तियों को ले सकता है। इस सेटिंग में, कोई व्यक्ति गड़बड़ी मॉडल का विश्लेषण कर सकता है जहां कोने $v_{1},\dots ,v_{n}$ संभाव्यता घनत्व फ़ंक्शन के साथ संभाव्यता वितरण के अनुसार स्वतंत्र रूप से नमूना लिया जाता है $f_{1},\dots ,f_{n}:[0,1]^{d}\rightarrow [0,\theta ]$. के लिए $\theta =1$, अंक समान रूप से वितरित किए जाते हैं। कब $\theta >1$ बड़ा होने पर, प्रतिद्वंद्वी के पास कठिन समस्या की संभावना को बढ़ाने की अधिक क्षमता होती है। इस गड़बड़ी मॉडल में, 2-ऑप्ट हेयुरिस्टिक के पुनरावृत्तियों की अपेक्षित संख्या, साथ ही परिणामी आउटपुट के अनुमानित अनुपात, के बहुपद कार्यों से बंधे हैं $n$ और $\theta$.

एक अन्य स्थानीय खोज एल्गोरिदम जिसके लिए सुचारू विश्लेषण सफल रहा, वह है k-मीन्स क्लस्टरिंग#Standard_algorithm_(naive_k-means)|k-मीन्स विधि। दिया गया $n$ में अंक $[0,1]^{d}$, एक ही क्लस्टर में बिंदुओं के बीच छोटी जोड़ीदार दूरी वाले समूहों में एक अच्छा विभाजन ढूंढना एनपी-कठिन है। लॉयड का एल्गोरिदम व्यापक रूप से उपयोग किया जाता है और व्यवहार में बहुत तेज़ है, हालाँकि इसमें समय लग सकता है $e^{\Omega (n)}$ सबसे खराब स्थिति में स्थानीय स्तर पर इष्टतम समाधान खोजने के लिए पुनरावृत्तियाँ। हालाँकि, यह मानते हुए कि बिंदुओं का स्वतंत्र गाऊसी वितरण है, प्रत्येक में अपेक्षा है $[0,1]^{d}$ और मानक विचलन $\sigma$, एल्गोरिथ्म के पुनरावृत्तियों की अपेक्षित संख्या एक बहुपद से घिरी हुई है $n$, $d$ और $\sigma$.

यह भी देखें

• औसत-मामले की जटिलता
• छद्म-बहुपद समय
• सबसे खराब स्थिति जटिलता