क्रॉस-एन्ट्रॉपी विधि: Difference between revisions

Latest revision as of 12:30, 28 July 2023

क्रॉस-एन्ट्रॉपी (सीई) विधि आवश्यक प्रतिदर्श और अनुकूलन के लिए एक मोंटे कार्लो विधि है। यह स्थिर या शोर वाले उद्देश्य के साथ संयुक्त और निरंतर दोनों समस्याओं पर लागू होता है।

यह विधि द्विचरणीय तकनीक का उपयोग करके उत्तम आवश्यक प्रतिदर्श प्राक्कलन कर्त्ता का अनुमान लगाता है:^[1]

संभाव्यता वितरण से एक प्रतिदर्श बनाएं।
अगले पुनरावृत्ति में उत्तम प्रतिदर्श तैयार करने के लिए इस वितरण और लक्ष्य वितरण के बीच क्रॉस-एन्ट्रॉपी को कम करें।

रूवेन रुबिनस्टीन ने यह विधि द्विपक्षीय घटना अनुकरण के सन्दर्भ में विकसित की, जहां अत्यंत कम प्रायिकता को अनुमानित किया जाना आवश्यक होता है। उदाहरण के लिए नेटवर्क विश्वसनीयता विश्लेषण, कतारीय मॉडल, या दूरसंचार प्रणालियों के प्रदर्शन विश्लेषण में छोटे प्रायिकत्वों का अनुमान लगाना आवश्यक होता है।।

यह विधि ट्रैवलिंग सेल्समैन की समस्या, द्विघात असाइनमेंट समस्या, डीएनए अनुक्रम संरेखण, मैक्सकट, और बफर आवंटन समस्याओं पर भी लागू की गई है।

आवश्यक प्रतिदर्श के माध्यम से अनुमान

मात्रा का अनुमान लगाने की सामान्य समस्या पर विचार करें

$\ell =\mathbb {E} _{\mathbf {u} }[H(\mathbf {X} )]=\int H(\mathbf {x} )\,f(\mathbf {x} ;\mathbf {u} )\,{\textrm {d}}\mathbf {x}$ ,

यहां, $H$ कोई प्रदर्शन फलन है और $f(\mathbf {x} ;\mathbf {u} )$ कुछ पैरामीट्रिक समूह के विशेषज्ञ वितरण है। आवश्यक प्रतिदर्श का उपयोग करके इस मात्रा का अनुमान लगाया जा सकता है।

${\hat {\ell }}={\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{g(\mathbf {X} _{i})}}$ ,

यहां, $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ $g,$ से एक यादृच्छिक प्रतिदर्श है। ध्यान दें कि $H$ सकारात्मक है। सैद्धांतिक रूप से, इष्टतम आवश्यक प्रतिदर्श घनत्व (पीडीएफ) निम्नलिखित रूप में दिया गया है:

$g^{*}(\mathbf {x} )=H(\mathbf {x} )f(\mathbf {x} ;\mathbf {u} )/\ell$ .

यद्यपि , यह अज्ञात $\ell$ पर निर्भर करता है। सीई विधि का उद्देश्य इष्टतम पीडीएफ को अनुमानित करना है, जिसमें पैरामीट्रिक समूह के सदस्यों का चयन समांतर रूप से किया जाता है जो इष्टतम पीडीएफ $g^{*}$ से सबसे नजदीक होते हैं।

सामान्य सीई कलन विधि

आरंभिक पैरामीटर वेक्टर $\mathbf {v} ^{(0)}$ चुनें; t को 1 से सेट करें।.
$f(\cdot ;\mathbf {v} ^{(t-1)})$ से एक यादृच्छिक प्रतिदर्श $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ उत्पन्न करें।
$\mathbf {v} ^{(t)}$ के लिए समस्या का हल करें, जहां
$\mathbf {v} ^{(t)}=\mathop {\textrm {argmax}} {\mathbf {v} }{\frac {1}{N}}\sum {i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}}\log f(\mathbf {X} _{i};\mathbf {v} )$
यदि संघटन तक पहुंचा जाता है, तो रुकें; अन्यथा, t को 1 बढ़ाएं और पुनः चरण 2 से दोहराएं।

अन्य स्थितियों में, चरण 3 का समाधान विश्लेषणात्मक रूप से पाया जा सकता है। जिन स्थितियों में ऐसा होता है वे हैं

जब $f,$ प्राकृतिक घातीय परिवार का भाग है।
जब $f,$ एक विकल्पिक वितरण है जिसमें समर्थन सीमित होता है।
जब यदि $H(\mathbf {X} )=\mathrm {I} _{\mathbf {x} \in A}$ है और $f(\mathbf {X} _{i};\mathbf {u} )=f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})$ है, तो $\mathbf {v} ^{(t)}$ वह अधिकतम योग्यता अनुमानकर्ता है जो उन $\mathbf {X} _{k}\in A$ पर आधारित है।.

सतत अनुकूलन—उदाहरण

एक समान सीई एल्गोरिदम का उपयोग अनुमान नहीं करने, बल्कि अनुकरण के लिए किया जा सकता है। मान लें समस्या है कि किसी फ़ंक्शन $S$ को अधिकतम बनाने के लिए है। उदाहरण के रूप में,

 $S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}$ .

सीई को लागू करने के लिए, पहले संबंधित यादृच्छिक समस्या का ध्यान दिया जाता है जो एक दिए गए स्तर $\mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )$ और पैरामीट्रिक समूह $\gamma \,$ ,के लिए $\left\{f(\cdot ;{\boldsymbol {\theta }})\right\}$ , का अनुमान लगाने का प्रयास करता है। उदाहरण के लिए 1-आयामी गौसियन वितरण, जिसका अर्थ होता है कि एक आयामी यादृच्छिक समूह इसका अर्थ $\mu _{t}\,$ और परिवर्तन $\sigma _{t}^{2}$ से पैरामीटराइज़ किया गया है इसका अर्थ ${\boldsymbol {\theta }}=(\mu ,\sigma ^{2})$ है।

इसलिए, एक दिए गए स्तर $\gamma \,$ ,के लिए, लक्ष्य होता है कि ऐसे ${\boldsymbol {\theta }}$ को खोजा जाए जिससे KL डाइवर्जेंस $D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})$ को कम से कम किया जा सके, इसे समस्त प्रतिदर्श संस्करण के साथ एक प्रकार की केएल विचलन न्यूनतमीकरण समस्या के समाधान के रूप में किया जाता है, जैसा कि ऊपर स्टेप 3 में दिखाया गया है।

यह सिद्ध हुआ है कि इस चयनित लक्ष्य वितरण और पैरामीट्रिक परिवार के लिए स्टोकेस्टिक संबंधी को न्यूनतम करने वाले पैरामीटर वे नमूने हैं जिनके उद्देश्य फलन का मान $\geq \gamma$ . है

फिर विशिष्ट नमूनों में से सबसे खराब को अगले पुनरावृत्ति के लिए स्तर पैरामीटर के रूप में उपयोग किया जाता है। यह निम्नलिखित यादृच्छिक एल्गोरिदम उत्पन्न करता है जो वितरण एल्गोरिदम के तथाकथित अनुमान मल्टीवेरिएट नॉर्मल एल्गोरिदम (ईएमएनए) के साथ मेल खाता है।

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

छद्मकोड

// Initialize parameters                                                                                                       μ := −6
σ2 := 100
t := 0
maxits := 100
N := 100
Ne := 10
// While maxits not exceeded and not converged
while t < maxits and σ2 > ε do
    // Obtain N samples from current sampling distribution
    X := SampleGaussian(μ, σ2, N)
    // Evaluate objective function at sampled points
    S := exp(−(X − 2) ^ 2) + 0.8 exp(−(X + 2) ^ 2)
    // Sort X by objective function values in descending order
    X := sort(X, S)
    // Update parameters of sampling distribution                  
    μ := mean(X(1:Ne))
    σ2 := var(X(1:Ne))
    t := t + 1
// Return mean of final sampling distribution as solution

यह भी देखें

क्रॉस एन्ट्रापी
कुल्बैक-लीब्लर विचलन
यादृच्छिक एल्गोरिदम
आवश्यक प्रतिदर्श करण

जर्नल पेपर्स

डी बोअर, पी-टी., क्रोसे, डी.पी., मैन्नोर, एस. और रुबिनस्टीन, आर.वाई. (2005)। क्रॉस-एन्ट्रॉपी विधि पर एक ट्यूटोरियल। एनल्स ऑफ ऑपरेशंस रिसर्च, '134' (1), 19-67।[1]
रुबिनस्टीन, आर.वाई. (1997)। दुर्लभ घटनाओं के साथ कंप्यूटर सिमुलेशन मॉडल का अनुकूलन, यूरोपियन जर्नल ऑफ ऑपरेशनल रिसर्च, '99', 89-112।

सॉफ़्टवेयर कार्यान्वयन

संदर्भ

↑ Rubinstein, R.Y. and Kroese, D.P. (2004), The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, Springer-Verlag, New York ISBN 978-0-387-21240-1.

[1] Rubinstein, R.Y. and Kroese, D.P. (2004), The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, Springer-Verlag, New York ISBN 978-0-387-21240-1.

[1]

@@ Line 1: / Line 1: @@
-'''क्रॉस-एन्ट्रॉपी (सीई) विधि''' [[महत्व नमूनाकरण|आवश्यक   प्रतिदर्श]] और अनुकूलन के लिए एक मोंटे कार्लो विधि है। यह स्थिर या शोर वाले उद्देश्य के साथ संयुक्त और निरंतर दोनों समस्याओं पर लागू होता है।
+'''क्रॉस-एन्ट्रॉपी (सीई) विधि''' [[महत्व नमूनाकरण|आवश्यक प्रतिदर्श]] और अनुकूलन के लिए एक मोंटे कार्लो विधि है। यह स्थिर या शोर वाले उद्देश्य के साथ संयुक्त और निरंतर दोनों समस्याओं पर लागू होता है।
 यह विधि द्विचरणीय तकनीक का उपयोग करके उत्तम आवश्यक   [[महत्व नमूनाकरण|प्रतिदर्श]] प्राक्कलन कर्त्ता का अनुमान लगाता है:<ref>Rubinstein, R.Y. and  Kroese, D.P. (2004), The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, Springer-Verlag, New York {{ISBN|978-0-387-21240-1}}.</ref>
@@ Line 10: / Line 10: @@
-==आवश्यक   प्रतिदर्श के माध्यम से अनुमान==
+==आवश्यक प्रतिदर्श के माध्यम से अनुमान==
 मात्रा का अनुमान लगाने की सामान्य समस्या पर विचार करें
@@ Line 25: / Line 25: @@
 यद्यपि , यह अज्ञात <math>\ell</math> पर निर्भर करता है। सीई विधि का उद्देश्य इष्टतम पीडीएफ को अनुमानित करना है, जिसमें पैरामीट्रिक समूह  के सदस्यों का चयन समांतर रूप से किया जाता है जो  इष्टतम पीडीएफ <math>g^*</math> से सबसे नजदीक होते हैं।
-[[Category:Created On 10/07/2023]]
-[[Category:Heuristics]]
-[[Category:Machine Translated Page]]
-[[Category:Pages with script errors]]
-[[Category:Templates Vigyan Ready]]
-[[Category:अनुकूलन एल्गोरिदम और विधियाँ]]
-[[Category:मोंटे कार्लो विधियाँ]]
-[[Category:यंत्र अधिगम]]
 == सामान्य सीई कलन विधि ==
@@ Line 46: / Line 46: @@
 * जब यदि <math>H(\mathbf{X}) = \mathrm{I}_{{\mathbf{x}\in A}}</math> है और <math>f(\mathbf{X}_i;\mathbf{u}) = f(\mathbf{X}_i;\mathbf{v}^{(t-1)})</math> है, तो <math>\mathbf{v}^{(t)}</math> वह [[अधिकतम योग्यता|अधिकतम योग्यता अनुमानकर्ता]] है जो उन <math>\mathbf{X}_k \in A</math> पर आधारित है।.
-[[Category:Created On 10/07/2023]]
-[[Category:Heuristics]]
-[[Category:Machine Translated Page]]
-[[Category:Pages with script errors]]
-[[Category:Templates Vigyan Ready]]
-[[Category:अनुकूलन एल्गोरिदम और विधियाँ]]
-[[Category:मोंटे कार्लो विधियाँ]]
-[[Category:यंत्र अधिगम]]
 == सतत अनुकूलन—उदाहरण==
@@ Line 70: / Line 70: @@
 ===छद्मकोड===
-  //प्रारंभिक पैरामीटर
+  ''// Initialize parameters''                                                                                                       μ := −6
- μ�:= −6
+  σ2 := 100
-  σ2�:= 100
+  t := 0
-  टी�:= 0
+  maxits := 100
-  अधिकतम�:= 100
+  N := 100
-  एन�:= 100
+  Ne := 10
-  ने�:=10
+  ''// While maxits not exceeded and not converged''
-  // जबकि अधिकतम सीमा पार नहीं हुई है और अभिसरण नहीं हुई है
+  '''while''' t < maxits '''and''' σ2 > ε '''do'''
-  'जबकि' t < अधिकतम 'और' σ2 > ε 'करें'
+      ''// Obtain N samples from current sampling distribution''
-      // वर्तमान प्रतिदर्श     वितरण से एन नमूने प्राप्त करें
+      X := SampleGaussian(μ, σ2, N)
-      एक्स�:= प्रतिदर्श    गौसियन(μ, σ2, एन)
+      ''// Evaluate objective function at sampled points''
-      // प्रतिदर्श     बिंदुओं पर वस्तुनिष्ठ फ़ंक्शन का मूल्यांकन करें
+      S := exp(−(X − 2) ^ 2) + 0.8 exp(−(X + 2) ^ 2)
-      S�:= exp(-(X − 2) ^ 2) + 0.8 exp(-(X + 2) ^ 2)
+      ''// Sort X by objective function values in descending order''
-      // वस्तुनिष्ठ फ़ंक्शन मानों के आधार पर X को अवरोही क्रम में क्रमबद्ध करें
+      X := sort(X, S)
-      एक्स := सॉर्ट करें (एक्स, एस)
+      ''// Update parameters of sampling distribution''
-      // प्रतिदर्श     वितरण के अद्यतन पैरामीटर
+      μ := mean(X(1:Ne))
-      μ�:= माध्य(X(1:Ne))
+      σ2 := var(X(1:Ne))
-      σ2X:= var(X(1:Ne))
+      t := t + 1
-      टी1:= टी + 1
+  ''// Return mean of final sampling distribution as solution''
-  // समाधान के रूप में अंतिम प्रतिदर्श     वितरण का रिटर्न माध्य
- 'वापसी' μ
+== संबंधित विधियाँ ==
-==संबंधित विधियाँ==
+* [[तैयार किए हुयी धातु पे पानी चढाने की कला|सिम्युलेटेड ऐनलिंग]]
-* [[तैयार किए हुयी धातु पे पानी चढाने की कला]]
 *[[आनुवंशिक एल्गोरिदम]]
-*सद्भाव खोज
+*हार्मनी सर्च
 *वितरण एल्गोरिदम का अनुमान
-*[[तब्बू सर्च]]
+*[[तब्बू सर्च|ताबू सर्च]]
 *[[प्राकृतिक विकास रणनीति]]
@@ Line 105: / Line 102: @@
 *कुल्बैक-लीब्लर विचलन
 *यादृच्छिक एल्गोरिदम
-*आवश्यक   प्रतिदर्श    करण
+*आवश्यक प्रतिदर्श करण
 ==जर्नल पेपर्स==
@@ Line 117: / Line 114: @@
 ==संदर्भ==
 {{reflist}}
-[[Category: heuristics]]
-[[Category: अनुकूलन एल्गोरिदम और विधियाँ]]
-[[Category: मोंटे कार्लो विधियाँ]]
-[[Category: यंत्र अधिगम]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 10/07/2023]]
+[[Category:Heuristics]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:अनुकूलन एल्गोरिदम और विधियाँ]]
+[[Category:मोंटे कार्लो विधियाँ]]
+[[Category:यंत्र अधिगम]]

Anonymous

Search

क्रॉस-एन्ट्रॉपी विधि: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 12:30, 28 July 2023

Contents

आवश्यक प्रतिदर्श के माध्यम से अनुमान

सामान्य सीई कलन विधि

सतत अनुकूलन—उदाहरण

छद्मकोड

संबंधित विधियाँ

यह भी देखें

जर्नल पेपर्स

सॉफ़्टवेयर कार्यान्वयन

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

क्रॉस-एन्ट्रॉपी विधि: Difference between revisions

Latest revision as of 12:30, 28 July 2023

आवश्यक प्रतिदर्श के माध्यम से अनुमान

सामान्य सीई कलन विधि

सतत अनुकूलन—उदाहरण

छद्मकोड

संबंधित विधियाँ

यह भी देखें

जर्नल पेपर्स

सॉफ़्टवेयर कार्यान्वयन

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories