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

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

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

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

${\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^{*}$ से सबसे नजदीक होते हैं।

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

1. आरंभिक पैरामीटर वेक्टर $\mathbf {v} ^{(0)}$ चुनें; t को 1 से सेट करें।.
2. $f(\cdot ;\mathbf {v} ^{(t-1)})$ से एक यादृच्छिक प्रतिदर्श $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ उत्पन्न करें।
3. $\mathbf {v} ^{(t)}$ के लिए समस्या का हल करें, जहां
4. $\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} )$
5. यदि संघटन तक पहुंचा जाता है, तो रुकें; अन्यथा, 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।

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

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