क्रॉस-एन्ट्रॉपी विधि

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

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

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

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

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

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

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

$\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} )$ कुछ पैरामीट्रिक परिवार के विशेषज्ञ वितरण है। अहमद सैंपलिंग (Importance Sampling) का उपयोग करके इस मात्रा का अनुमान लगाया जा सकता है।

${\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$ पॉज़िटिव है। सिद्धांती रूप से, आनुचित अहमद सैंपलिंग घनत्व (PDF) निम्नलिखित रूप में दिया गया है:

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

यह, हालांकि, अज्ञात $\ell$ पर निर्भर करता है। सीई विधि का उद्देश्य है ऑप्टिमल PDF को अनुमानित करना, जिसमें पैरामीट्रिक परिवार के सदस्यों का चयन समांतर रूप से किया जाता है जो ऑप्टिमल PDF $g^{*}$ से सबसे नजदीक (Kullback-Leibler दृष्टि से) होते हैं।

जेनेरिक सीई एल्गोरिदम

1. प्रारंभिक पैरामीटर वेक्टर चुनें $\mathbf {v} ^{(0)}$; सेट टी = 1.
2. एक यादृच्छिक नमूना उत्पन्न करें $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ से $f(\cdot ;\mathbf {v} ^{(t-1)})$
3. के लिए हल $\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} )$
4. अगर सहमति बन जाए तो रुक जाओ; अन्यथा, 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 }}$ ताकि $D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})$ न्यूनतम किया गया है. यह केएल विचलन न्यूनीकरण समस्या के नमूना संस्करण (स्टोकेस्टिक समकक्ष) को हल करके किया जाता है, जैसा कि ऊपर चरण 3 में है। यह पता चला है कि पैरामीटर जो लक्ष्य वितरण की इस पसंद के लिए स्टोकेस्टिक समकक्ष को कम करते हैं और पैरामीट्रिक परिवार विशिष्ट नमूनों के अनुरूप नमूना माध्य और नमूना विचरण हैं, जो वे नमूने हैं जिनका उद्देश्य फ़ंक्शन मान है $\geq \gamma$. फिर विशिष्ट नमूनों में से सबसे खराब को अगले पुनरावृत्ति के लिए स्तर पैरामीटर के रूप में उपयोग किया जाता है। यह निम्नलिखित यादृच्छिक एल्गोरिदम उत्पन्न करता है जो वितरण एल्गोरिदम के तथाकथित अनुमान मल्टीवेरिएट नॉर्मल एल्गोरिदम (ईएमएनए) के साथ मेल खाता है।

छद्मकोड

//प्रारंभिक पैरामीटर
μ := −6
σ2 := 100
टी := 0
अधिकतम := 100
एन := 100
ने :=10
// जबकि अधिकतम सीमा पार नहीं हुई है और अभिसरण नहीं हुई है
'जबकि' t < अधिकतम 'और' σ2 > ε 'करें'
    // वर्तमान नमूना वितरण से एन नमूने प्राप्त करें
    एक्स := नमूनागौसियन(μ, σ2, एन)
    // नमूना बिंदुओं पर वस्तुनिष्ठ फ़ंक्शन का मूल्यांकन करें
    S := exp(-(X − 2) ^ 2) + 0.8 exp(-(X + 2) ^ 2)
    // वस्तुनिष्ठ फ़ंक्शन मानों के आधार पर X को अवरोही क्रम में क्रमबद्ध करें
    एक्स := सॉर्ट करें (एक्स, एस)
    // नमूना वितरण के अद्यतन पैरामीटर
    μ := माध्य(X(1:Ne))
    σ2 := var(X(1:Ne))
    टी := टी + 1
// समाधान के रूप में अंतिम नमूना वितरण का रिटर्न माध्य
'वापसी' μ

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

• तैयार किए हुयी धातु पे पानी चढाने की कला
• आनुवंशिक एल्गोरिदम
• सद्भाव खोज
• वितरण एल्गोरिदम का अनुमान
• तब्बू सर्च
• प्राकृतिक विकास रणनीति

यह भी देखें

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

जर्नल पेपर्स

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

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

• CEoptim R पैकेज
• नोवाक्टा.एनालिटिक्स .NET लाइब्रेरी