कंस्ट्रक्टिंग स्किल ट्री

कंस्ट्रक्टिंग स्किल ट्री (CST) एक पदानुक्रमित सुदृढीकरण सीखना एल्गोरिद्म है जो प्रदर्शन से प्राप्त नमूना समाधान प्रक्षेपवक्र के एक सेट से स्किल ट्री का निर्माण कर सकता है। CST प्रत्येक प्रदर्शन प्रक्षेपवक्र को कौशल में विभाजित करने और परिणामों को एक कौशल वृक्ष में एकीकृत करने के लिए एक वृद्धिशील MAP (अधिकतम एक पश्चवर्ती) परिवर्तन बिंदु पहचान एल्गोरिथ्म का उपयोग करता है। CST को 2010 में जॉर्ज कोनिडारिस, स्कॉट कुइंडर्स्मा, एंड्रयू बार्टो और रोड्रिट्ज़ समूह द्वारा प्रस्तुत किया गया था।

एल्गोरिथम

CST में मुख्य रूप से तीन भाग होते हैं; परिवर्तन बिंदु पहचान, संरेखण और विलय। सीएसटी का मुख्य फोकस ऑनलाइन चेंज-प्वाइंट डिटेक्शन है। चेंज-पॉइंट डिटेक्शन एल्गोरिदम का उपयोग डेटा को कौशल में विभाजित करने के लिए किया जाता है और रियायती इनाम के योग का उपयोग करता है $R_{t}$ लक्ष्य प्रतिगमन चर के रूप में। प्रत्येक कौशल को एक उपयुक्त सार सौंपा गया है। सीएसटी की कम्प्यूटेशनल जटिलता को नियंत्रित करने के लिए एक कण फिल्टर का उपयोग किया जाता है।

परिवर्तन बिंदु पहचान एल्गोरिदम निम्नानुसार कार्यान्वित किया गया है। समय के लिए डेटा $t\in T$ और मॉडल Q पूर्व के साथ $p(q\in Q)$ दिया जाता है। एल्गोरिदम को समय से एक खंड में फिट करने में सक्षम माना जाता है $j+1$ को t मॉडल का उपयोग करना q फिट होने की संभावना के साथ $P(j,t,q)_{}^{}$. गाऊसी शोर के साथ एक रेखीय प्रतिगमन मॉडल की गणना करने के लिए प्रयोग किया जाता है $P(j,t,q)$. गॉसियन शोर का मतलब शून्य होता है, और विचरण जो पश्चात में होता है $\mathrm {InverseGamma} \left({\frac {v}{2}},{\frac {u}{2}}\right)$. प्रत्येक वजन के लिए पूर्व इस प्रकार है $\mathrm {Normal} (0,\sigma ^{2}\delta )$.

फिट होने की संभावना $P(j,t,q)$ निम्नलिखित समीकरण द्वारा गणना की जाती है।

$P(j,t,q)={\frac {\pi ^{-{\frac {n}{2}}}}{\delta ^{m}}}\left|(A+D)^{-1}\right|^{\frac {1}{2}}{\frac {u^{\frac {v}{2}}}{(y+u)^{\frac {u+v}{2}}}}{\frac {\Gamma ({\frac {n+v}{2}})}{\Gamma ({\frac {v}{2}})}}$

फिर, CST समय पर परिवर्तन बिंदु की प्रायिकता की गणना करता है j मॉडल के साथ q, $P_{t}(j,q)$ और $P_{j}^{\text{MAP}}$ विटरबी एल्गोरिथ्म का उपयोग करना।

: : : : : : : : : : : : : : : : : : : : : : : : $P_{t}(j,q)=(1-G(t-j-1))P(j,t,q)p(q)P_{j}^{\text{MAP}}$

$P_{j}^{\text{MAP}}=\max _{i,q}{\frac {P_{j}(i,q)g(j-i)}{1-G(j-i-1)}},\forall j<t$

मापदंडों और चर का विवरण इस प्रकार है;

$A=\sum _{i=j}^{t}\Phi (x_{i})\Phi (x_{i})^{T}$

$\Phi (x_{i})$: एम आधार कार्यों का एक वेक्टर राज्य में मूल्यांकन किया गया $x_{i}$

$y=(\sum _{i=j}^{t}R_{i}^{2})-b^{T}(A+D)^{-1}b$

$b=\sum _{i=j}^{t}R_{i}\Phi (x_{i})$

$R_{i}=\sum _{j=i}^{T}\gamma ^{j-i}r_{j}$

𝛾: गामा समारोह

$n=t-j$

m: क्यू के आधार कार्यों की संख्या।

D: एम बाय एम मैट्रिक्स के साथ $\delta ^{-1}$ विकर्ण पर और शून्य कहीं और

कौशल की लंबाई l को पैरामीटर के साथ एक ज्यामितीय वितरण का पालन करने के लिए माना जाता है p

$g_{}^{}(l)=(1-p)^{l-1}p$

$G_{}^{}(l)=(1-(1-p)^{l})$

$p_{}^{}={\frac {1}{k}}$

k: अपेक्षित कौशल लंबाई

उपरोक्त विधि का उपयोग करके, CST डेटा को कौशल श्रृंखला में विभाजित कर सकता है। परिवर्तन बिंदु का पता लगाने की समय जटिलता है $O(NL)$ और स्टोरेज साइज है $O(Nc)$, कहाँ N कणों की संख्या है, L कंप्यूटिंग का समय है $P(j,t,q)$, और वहाँ है $O(c)$ अंक बदलें।

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

अंतिम चरण विलय कर रहा है। सीएसटी स्किल चेन को स्किल ट्री में मर्ज करता है। सीएसटी एक ही कौशल आवंटित करके प्रक्षेपवक्र खंडों की एक जोड़ी को मिला देता है। सभी प्रक्षेपवक्रों का एक ही लक्ष्य होता है और यह अपने अंतिम खंडों से प्रारंभ करके दो श्रृंखलाओं को मिला देता है। यदि दो खंड सांख्यिकीय रूप से समान हैं, तो यह उन्हें विलीन कर देता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि यह कौशल खंडों की एक जोड़ी को मर्ज करने में विफल नहीं हो जाती। $P(j,t,q)$ यह निर्धारित करने के लिए उपयोग किया जाता है कि क्या प्रक्षेपवक्र की एक जोड़ी को एक कौशल या दो भिन्न-भिन्न कौशल के रूप में उत्तम विधि से तैयार किया गया है।

स्यूडोकोड

निम्नलिखित स्यूडोकोड परिवर्तन बिंदु पहचान एल्गोरिथ्म का वर्णन करता है:

कण := [];
प्रत्येक आने वाले डेटा बिंदु को संसाधित करें
टी = 1 के लिए: टी करते हैं
    // सभी कणों के लिए फिट संभावनाओं की गणना करें
    p ∈ कणों के लिए
        p_tjq := (1 − G(t − p.pos − 1)) × p.fit_prob × model_prior(p.model) × p.prev_MAP
        p.MAP := p_tjq × g(t−p.pos) / (1 − G(t − p.pos − 1))
    अंत
     // यदि आवश्यक हो तो फ़िल्टर करें 
    यदि कणों की संख्या ≥ N तो
        कण: = कण_फ़िल्टर (पी.एमएपी, एम)
    अंत
    // विटरबी पथ निर्धारित करें
    टी = 1 के लिए करो
        मैक्स_पथ: = []
        max_MAP := 1/|Q|
    अन्य
        मैक्स_पार्टिकल: = maxp पी.एमएपी
        max_path := max_particle.path ∪ max_particle
        max_MAP: = max_particle.MAP
    अंत
    // समय टी पर एक परिवर्तन बिंदु के लिए नए कण बनाएं
    क्यू ∈ क्यू के लिए करते हैं
        new_p := create_particle(मॉडल=क्यू, स्थिति=टी, पिछला_एमएपी=मैक्स_एमएपी, पथ=मैक्स_पथ)
        पी := पी ∪ new_p
    अंत
    // सभी कणों को अपडेट करें
    p ∈ P के लिए
        कण := update_particle(current_state, current_reward, p)
    अंत
अंत
// अंतिम बिंदु पर सबसे संभावित पथ लौटाएं
वापसी max_path

फ़ंक्शन अपडेट_पार्टिकल (current_state, current_reward, कण) है
    पः=कण
    r_t_:= current_reward
    // इनिशियलाइज़ेशन
    यदि टी = 0 तो
        p.A.:= शून्य मैट्रिक्स (अपराह्न, अपराह्न)
        p.bp:= शून्य सदिश(p.m)
        p.z := शून्य सदिश (अपराह्न)
        p.sum rs:= 0
        p.tr1:= 0
        p.tr2 := 0
    यदि अंत
    // वर्तमान स्थिति के लिए आधार फ़ंक्शन वेक्टर की गणना करें
    Φt := p.Φ(currentstate)
    // पर्याप्त आंकड़े अपडेट करें
    p.A.:= p.A + Φ{{sub|t}पीएचआईT
t
    p.z:= 𝛾p.z + एफt
    p.bb:= p.b + rt p.z
    p.tr11:= 1 + 𝛾2 p.tr1
    p.sum rr:= योग p.r + r2
t p.tr1 + 2𝛾आरt p.tr2
    p.tr2:= 𝛾p.tr2 + आरt p.tr1
    p.fit_probb:= कंप्यूट_फिट_प्रोब (पी, वी, यू, डेल्टा, 𝛾)

अनुमान

सीटीएस मानता है कि प्रदर्शित कौशल एक पेड़ का निर्माण करते हैं, डोमेन इनाम समारोह ज्ञात है और कौशल की एक जोड़ी को विलय करने के लिए सबसे अच्छा मॉडल व्यक्तिगत रूप से दोनों का प्रतिनिधित्व करने के लिए चुना गया मॉडल है।

लाभ

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

उपयोग करता है

CST का उपयोग PinBall डोमेन में मानव प्रदर्शन से कौशल प्राप्त करने के लिए किया गया है। इसका उपयोग मोबाइल मैनिपुलेटर पर मानव प्रदर्शन से कौशल प्राप्त करने के लिए भी किया गया है।

यह भी देखें

• प्रीफ्रंटल कॉर्टेक्स बेसल गैन्ग्लिया वर्किंग मेमोरी
• स्टेट-एक्शन-इनाम-स्टेट-एक्शन
• सामन मानचित्रण

संदर्भ

• Konidaris, George; Scott Kuindersma; Andrew Barto; Roderic Grupen (2010). "Constructing Skill Trees for Reinforcement Learning Agents from Demonstration Trajectories". Advances in Neural Information Processing Systems 23.

• Konidaris, George; Andrew Barto (2009). "Skill discovery in continuous reinforcement learning domains using skill chaining". Advances in Neural Information Processing Systems 22.

• Fearnhead, Paul; Zhen Liu (2007). "On-line Inference for Multiple Change Points". Journal of the Royal Statistical Society.