कारक ग्राफ

Not to be confused with Graph factorization.

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

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

परिभाषा

फ़ैक्टर ग्राफ़ एक द्विदलीय ग्राफ़ है जो किसी फ़ंक्शन के फ़ैक्टराइज़ेशन का प्रतिनिधित्व करता है। किसी फ़ंक्शन का गुणनखंडन दिया गया है $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}$. सम-उत्पाद एल्गोरिथ्म के संदेशों को वैचारिक रूप से शीर्षों में गणना की जाती है और किनारों के साथ पारित किया जाता है। किसी वेरिएबल शीर्ष से या उसके लिए एक संदेश हमेशा उस विशेष वेरिएबल का एक फ़ंक्शन (गणित) होता है। उदाहरण के लिए, जब कोई वैरिएबल बाइनरी होता है, तो messages संबंधित शीर्ष पर किनारों की घटना को लंबाई 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