ग्राफ़ सिद्धांत - इष्टतम पथ

Question

खोजने के लिए लागत फ़ंक्शन सीखें यह एक पर्यवेक्षित सीखने की समस्या है।

मेरे पास एक निर्देशित विश्वकोश ग्राफ (डीएजी) है। प्रत्येक किनारे में एक्स एक्स के वेक्टर होते हैं, और प्रत्येक नोड (वर्टेक्स) में लेबल 0 या 1 होता है। कार्य लागत फ़ंक्शन डब्ल्यू (एक्स) ढूंढना है, ताकि नोड्स की किसी भी जोड़ी के बीच सबसे छोटा पथ उच्चतम अनुपात हो 1 से 0 एस (न्यूनतम वर्गीकरण त्रुटि)।

समाधान को सामान्यीकृत करना चाहिए। मैंने लॉजिस्टिक रिग्रेशन की कोशिश की, और सीखा लॉजिस्टिक फ़ंक्शन एक आने वाले किनारे की विशेषताओं को देने वाले नोड के लेबल को काफी अच्छी तरह से भविष्यवाणी करता है। हालांकि, ग्राफ के टोपोलॉजी को उस दृष्टिकोण से ध्यान में नहीं रखा जाता है, इसलिए पूरे ग्राफ में समाधान गैर-इष्टतम है। दूसरे शब्दों में, तर्कवादी कार्य ऊपर समस्या समस्या को देखते हुए एक अच्छा वजन समारोह नहीं है। http://en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work

यहां कुछ और जानकारी कर रहे हैं::

1. प्रत्येक सुविधा सदिश एक्स एक घ है

   हालांकि मेरी समस्या सेटअप ठेठ द्विआधारी वर्गीकरण समस्या सेटअप नहीं है, यहाँ यह करने के लिए एक अच्छा परिचय है वास्तविक संख्या की आयामी सूची।

2. प्रत्येक किनारे में सुविधाओं का वेक्टर होता है। यही है, किनारों का सेट ई = {ई 1, ई 2, .. एन} और फीचर वैक्टर एफ = {एक्स 1, एक्स 2 ... एक्सएन} का सेट दिया गया है, फिर एज ईई वेक्टर शी से जुड़ा हुआ है।
3. फ़ंक्शन एफ (एक्स) के साथ आना संभव है, ताकि f (Xi) संभावना है कि किनारे ईआई को 1 लेबल वाले नोड पर इंगित किया गया है। ऐसे फ़ंक्शन का एक उदाहरण है जिसका मैंने उल्लेख किया है उपरोक्त, रसद प्रतिगमन के माध्यम से मिला। हालांकि, जैसा कि मैंने उपरोक्त उल्लेख किया है, ऐसा कार्य गैर-इष्टतम है।

तो सवाल यह है: , (न्यूनतम ग्राफ, एक शुरू करने नोड और एक खत्म नोड, मैं इष्टतम लागत समारोह डब्ल्यू (एक्स) के बारे में जानने है को देखते हुए इतना है कि 0s को नोड्स 1s के अनुपात बड़ा किया गया है वर्गीकरण त्रुटि)?

Answer 1

यह ऐसी समस्या की तरह दिखता है जहां आनुवंशिक एल्गोरिदम में उत्कृष्ट क्षमता है। यदि आप वांछित फ़ंक्शन को उदा। (लेकिन इतनी ही सीमित नहीं है) सुविधाओं के एक रैखिक संयोजन (आप वर्गबद्ध शब्द, फिर घन, विज्ञापन inifititum जोड़ सकते हैं), तो जीन गुणांक के वेक्टर है। म्यूटेटर उचित सीमा के भीतर एक या अधिक गुणांक की यादृच्छिक ऑफसेट हो सकता है। मौजूदा उत्परिवर्तन के अनुसार सभी जोड़ों के लिए मूल्यांकन कार्य केवल 1 से 0 के औसत अनुपात के साथ औसत अनुपात है। प्रत्येक पीढ़ी में, अगली पीढ़ी बनाने के लिए पूर्वजों के रूप में सर्वश्रेष्ठ कुछ जीन चुनें और उत्परिवर्तित करें। जब तक उबर जीन हाथ में न हो जाए तब तक दोहराएं।

Answer 2

यह वास्तव में एक उत्तर नहीं है, लेकिन हमें इस प्रश्न को स्पष्ट करने की आवश्यकता है। हालांकि मैं बाद में एक संभावित उत्तर के लिए वापस आ सकता हूं।

नीचे एक उदाहरण डीएजी है।

मान लीजिए लाल नोड शुरू करने नोड है, और पीले एक छोर नोड है। आप

0s को 1s के उच्चतम अनुपात (न्यूनतम वर्गीकरण त्रुटि) के मामले में कम से कम पथ कैसे परिभाषित करते हैं?

संपादित: मैं प्रत्येक नोड और शीर्ष दो किनारों के लिए दो उदाहरण नाम के लिए नाम जोड़ने।

ऐसा लगता है कि आप ऐसे लागत समारोह को नहीं सीख सकते हैं जो फीचर वैक्टर को इनपुट के रूप में लेता है और जिसका आउटपुट (एज वजन? या जो कुछ भी) आपको ग्राफ टोपोलॉजी पर विचार करने वाले किसी भी नोड की ओर एक छोटा रास्ता लेने के लिए मार्गदर्शन कर सकता है। कारण नीचे दिया गया है:

• मान लीजिए कि आपके पास फीचर वैक्टर नहीं हैं।ऊपर दिए गए ग्राफ को देखते हुए, यदि आप 1 से 0 एस के अनुपात के साथ सभी जोड़ी-शॉर्ट-पथ खोजना चाहते हैं, तो Bellman equation या अधिक विशेष रूप से Dijkastra प्लस उचित हेरिस्टिक फ़ंक्शन (उदाहरण के लिए, 1 का प्रतिशत) का उपयोग करना सही है। पथ में एस)। एक और संभावित मॉडल-मुक्त दृष्टिकोण q-learning का उपयोग करना है जिसमें हमें नोड और -1 पर जाने के लिए 0 नोड पर जाने के लिए इनाम +1 मिलता है। हम एक समय में प्रत्येक लक्ष्य नोड के लिए एक लुकअप क्यू-टेबल सीखते हैं। आखिर में हमारे पास सभी जोड़ी-सबसे कम-पथ होते हैं जब सभी नोड्स को लक्ष्य नोड्स के रूप में माना जाता है।

• अब मान लीजिए, आपने जादुई रूप से फीचर वैक्टर प्राप्त किए हैं। चूंकि आप उन वैक्टरों के बिना इष्टतम समाधान ढूंढने में सक्षम हैं, इसलिए जब वे मौजूद होते हैं तो वे कैसे मदद करेंगे?

• एक संभावित शर्त है कि आप फीचर वेक्टर का उपयोग लागत लागत को सीखने के लिए कर सकते हैं जो किनारों के वजन को अनुकूलित करता है, यानी, फीचर वेक्टर ग्राफ टोपोलॉजी पर निर्भर हैं (नोड्स के बीच संबंध और 1 की स्थिति और 0 एस)। लेकिन मुझे आपके विवरण में यह निर्भरता बिल्कुल नहीं दिखाई दे रही थी। तो मुझे लगता है कि यह अस्तित्व में नहीं है।

Answer 3

मेरा मानना ​​है कि आपका प्रश्न इनवर्क्स सुदृढीकरण लर्निंग के क्षेत्र के बहुत करीब है, जहां आप इष्टतम पथों के कुछ "विशेषज्ञ प्रदर्शन" लेते हैं और लागत योजना सीखने की कोशिश करते हैं जैसे कि आपका प्लानर (ए * या कुछ सुदृढ़ीकरण सीखने वाला एजेंट) विशेषज्ञ प्रदर्शन के समान पथ आउटपुट करता है। यह प्रशिक्षण एक पुनरावृत्ति तरीके से किया जाता है। मुझे लगता है कि आपके मामले में, विशेषज्ञ प्रदर्शन आपके द्वारा बनाए गए पथ बनने के लिए बनाए जा सकते हैं जो अधिकतम 1 लेबल वाले किनारों से गुजरते हैं। यहां एक अच्छे पेपर का लिंक दिया गया है: Learning to Search: Functional Gradient Techniques for Imitation Learning। यह रोबोटिक्स समुदाय से है जहां गति योजना आमतौर पर ग्राफ-खोज समस्या के रूप में सेट की जाती है और वांछित व्यवहार का प्रदर्शन करने के लिए सीखने की लागत कार्य आवश्यक है।