कारक ग्राफ

Not to be confused with ग्राफ़ गुणनखंडन.

कारक ग्राफ़ एक द्विदलीय ग्राफ है जो किसी फलन के गुणनखंडन का प्रतिनिधित्व करता है। संभाव्यता सिद्धांत और उसके अनुप्रयोगों में कारक ग्राफ़ का उपयोग संभाव्यता वितरण फलन के गुणनखंडन का प्रतिनिधित्व करने के लिए किया जाता है, जो कुशल गणना को सक्षम करता है, जैसे कि योग-उत्पाद एल्गोरिथ्म के माध्यम से सीमांत वितरण की गणना कारक ग्राफ़ और योग-उत्पाद एल्गोरिदम की महत्वपूर्ण सफलता की कहानियों में से एक एलडीपीसी और टर्बो कोड जैसे क्षमता-अनुमोदन त्रुटि-सुधार कोड का डिकोडिंग है।

कारक ग्राफ बाधा ग्राफ को सामान्यीकृत करते हैं। वह कारक जिसका मान या तो 0 या 1 हो, बाधा कहलाता है। बाधा ग्राफ एक कारक ग्राफ है जहां सभी कारक बाधाएं हैं। कारक ग्राफ़ के लिए अधिकतम-उत्पाद एल्गोरिदम को बाधा प्रसंस्करण के लिए आर्क-स्थिरता एल्गोरिदम के सामान्यीकरण के रूप में देखा जा सकता है।

परिभाषा

कारक ग्राफ़ एक द्विदलीय ग्राफ़ है जो किसी फलन के गुणनखंडन का प्रतिनिधित्व करता है। किसी फलन $g(X_{1},X_{2},\dots ,X_{n})$ का गुणनखंडन दिया गया है।

$g(X_{1},X_{2},\dots ,X_{n})=\prod _{j=1}^{m}f_{j}(S_{j}),$

जहां $S_{j}\subseteq \{X_{1},X_{2},\dots ,X_{n}\}$, संबंधित कारक ग्राफ $G=(X,F,E)$ में वेरिएबल शीर्ष $X=\{X_{1},X_{2},\dots ,X_{n}\}$ कारक शीर्ष $F=\{f_{1},f_{2},\dots ,f_{m}\}$सम्मिलित हैं , और किनारे $E$. किनारे इस प्रकार गुणनखंडन पर निर्भर करते हैं: कारक शीर्ष $f_{j}$ और वेरिएबल शीर्ष $X_{k}$ यदि $X_{k}\in S_{j}$. के बीच एक अप्रत्यक्ष किनारा है। फलन को गुप्त रूप से वास्तविक-मूल्यवान $g(X_{1},X_{2},\dots ,X_{n})\in \mathbb {R}$ माना जाता है।

फलन $g(X_{1},X_{2},\dots ,X_{n})$ की कुछ विशेषताओं, जैसे सीमांत वितरण की कुशलतापूर्वक गणना करने के लिए कारक ग्राफ़ को संदेश पासिंग एल्गोरिदम के साथ जोड़ा जा सकता है।

उदाहरण

एक उदाहरण कारक ग्राफ

एक फलन पर विचार करें जो निम्नानुसार गुणनखंड करता है:

$g(X_{1},X_{2},X_{3})=f_{1}(X_{1})f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})f_{4}(X_{2},X_{3})$,

दाईं ओर दिखाए गए संबंधित कारक ग्राफ़ के साथ उपस्थित है ध्यान दें कि कारक ग्राफ़ में एक चक्र होता है। यदि हम $f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})$ को एक एकल कारक में मिलाते हैं, तो परिणामी कारक ग्राफ एक पेड़ (ग्राफ सिद्धांत) होगा। यह एक महत्वपूर्ण अंतर है, क्योंकि संदेश भेजने वाले एल्गोरिदम समान्यत: पेड़ों के लिए स्पष्ट होते हैं, किंतु चक्र वाले ग्राफ़ के लिए केवल अनुमानित होते हैं।

कारक ग्राफ़ पर संदेश भेजना

कारक ग्राफ़ पर एक लोकप्रिय संदेश पासिंग एल्गोरिदम योग-उत्पाद एल्गोरिदम है, जो फलन के व्यक्तिगत वेरिएबल के सभी मार्जिन की कुशलतापूर्वक गणना करता है। विशेष रूप से, वेरिएबल $X_{k}$ के सीमांत को इस प्रकार परिभाषित किया गया है

$g_{k}(X_{k})=\sum _{X_{\bar {k}}}g(X_{1},X_{2},\dots ,X_{n})$

जहां अंकन $X_{\bar {k}}$ का अर्थ है कि योग $X_{k}$ को छोड़कर सभी वेरिएबल पर जाता है। सम-उत्पाद एल्गोरिथ्म के संदेशों को वैचारिक रूप से शीर्षों में गणना की जाती है और किनारों के साथ पारित किया जाता है। किसी वेरिएबल शीर्ष से या उसके लिए एक संदेश सदैव उस विशेष वेरिएबल का एक फलन होता है। उदाहरण के लिए, जब एक वैरिएबल बाइनरी होता है, तो किनारों पर संबंधित शीर्ष पर आने वाले संदेशों को लंबाई 2 के सदिश के रूप में दर्शाया जा सकता है: पहली प्रविष्टि 0 में मूल्यांकन किया गया संदेश है, दूसरी प्रविष्टि 1 में मूल्यांकन किया गया संदेश है। वेरिएबल वास्तविक संख्याओं के क्षेत्र से संबंधित है, संदेश इच्छानुसार कार्य हो सकते हैं, और उनके प्रतिनिधित्व में विशेष देखभाल की आवश्यकता होती है।

वास्तव में, योग-उत्पाद एल्गोरिथ्म का उपयोग सांख्यिकीय अनुमान के लिए किया जाता है, जिससे $g(X_{1},X_{2},\dots ,X_{n})$ एक संयुक्त वितरण या एक संयुक्त संभावना फलन है, और कारककरण वैरिएबल के बीच नियमनुसार स्वतंत्रता पर निर्भर करता है।

हैमरस्ले-क्लिफ़ोर्ड प्रमेय से पता चलता है कि अन्य संभाव्य मॉडल जैसे बायेसियन नेटवर्क और मार्कोव नेटवर्क को कारक ग्राफ़ के रूप में दर्शाया जा सकता है; विश्वास प्रसार का उपयोग करके ऐसे नेटवर्क पर अनुमान लगाते समय बाद वाले प्रतिनिधित्व का अधिकांशत: उपयोग किया जाता है। दूसरी ओर बायेसियन नेटवर्क जेनरेटिव मॉडल के लिए स्वाभाविक रूप से अधिक उपयुक्त हैं क्योंकि वे सीधे मॉडल के कारणों का प्रतिनिधित्व कर सकते हैं।

यह भी देखें

• विश्वास प्रचार
• बायेसियन अनुमान
• बायेसियन प्रोग्रामिंग
• नियमनुसार संभाव्यता
• मार्कोव नेटवर्क
• बायेसियन नेटवर्क
• हैमरस्ले-क्लिफोर्ड प्रमेय

बाहरी संबंध

• Loeliger, Hans-Andrea (January 2004), "An Introduction to Factor Graphs]" (PDF), IEEE Signal Processing Magazine, 21 (1): 28–41, Bibcode:2004ISPM...21...28L, doi:10.1109/MSP.2004.1267047, S2CID 7722934
• dimple an open-source tool for building and solving factor graphs in MATLAB.
• Loeliger, Hans-Andrea (2008), An introduction to Factor Graphs (PDF)

संदर्भ

• Clifford (1990), "Markov random fields in statistics", in Grimmett, G.R.; Welsh, D.J.A. (eds.), Disorder in Physical Systems, J.M. Hammersley Festschrift (postscript), Oxford University Press, pp. 19–32, ISBN 9780198532156
• Frey, Brendan J. (2003), "Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models", in Jain, Nitin (ed.), UAI'03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence, Morgan Kaufmann, pp. 257–264, arXiv:1212.2486, ISBN 0127056645
• Kschischang, Frank R.; Frey, Brendan J.; Loeliger, Hans-Andrea (2001), "Factor Graphs and the Sum-Product Algorithm", IEEE Transactions on Information Theory, 47 (2): 498–519, CiteSeerX 10.1.1.54.1570, doi:10.1109/18.910572.
• Wymeersch, Henk (2007), Iterative Receiver Design, Cambridge University Press, ISBN 978-0-521-87315-4