स्मूथ्द एनालिसिस

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

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

सैद्धांतिक कंप्यूटर विज्ञान में, स्मूथ्द एनालिसिस एल्गोरिदम के एनालिसिस को मापने की एक विधि है। 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-ऑप्ट अनुमानी है। स्थानीय रूप से इष्टतम समाधान मिलने तक इसमें तेजी से कई पुनरावृत्तियां हो सकती हैं, चूँकि अभ्यास में चलने का समय वेर्टिसस की संख्या में सबक्वाड्रैटीक है। अप्प्रोक्सिमेसन रेश्यो, जो एल्गोरिदम के आउटपुट की लंबाई और इष्टतम समाधान की लंबाई के बीच का अनुपात है, अभ्यास में अच्छा होता है किंतु सैद्धांतिक रूप से वर्स्ट केस में भी व्यर्थ हो सकता है।

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

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

यह भी देखें

• एवरेज केस कॉम्पलेक्ससिटी
• सूडो -पालीनोमिअल टाइम
• वर्स्ट केस कॉम्पलेक्ससिटी