Кіріспе

Факторлық график – функцияның факторлануын көрсететін екі бөлікті график. Ықтималдық теориясы және оның қолданбаларында факторлық графиктер ықтималдық үлестіру функциясының факторлануын көрсету үшін пайдаланылады, бұл сома-көбейту алгоритмі арқылы шеттік үлестірулерді есептеу сияқты тиімді есептеулерді мүмкін етеді. Факторлық графиктер мен сома-көбейту алгоритмінің маңызды жетістіктерінің бірі – LDPC және турбо кодтар сияқты сыйымдылыққа жақындаған қателерді түзету кодтарын декодтау. Факторлық графиктер шектеу графиктерін жалпылайды. Мәні 0 немесе 1 болатын фактор шектеу деп аталады. Шектеу графигі – барлық факторлары шектеулер болатын факторлық график. Факторлық графиктер үшін максималды көбейту алгоритмін шектеулерді өңдеу үшін доғалық үйлесімділік алгоритмінің жалпыланған түрі деп қарастыруға болады.

Факторлық графиктерде хабар беру

Факторлық графиктердегі танымал хабар алмасу алгоритмі – бұл функцияның жеке айнымалыларының барлық маргиналдарын тиімді есептейтін алгоритм. Атап айтқанда, айнымалының маргиналды былай анықталады:

мұндағы белгілеу барлық айнымалылар бойынша қосындылауды білдіреді, бірақ . Сома-көбейту алгоритмінің хабарлары түйіндерде есептеліп, жиектер арқылы беріледі. Айнымалы түйінінен немесе оған жіберілген хабар әрқашан сол айнымалының функциясы болады. Мысалы, егер айнымалы екілік болса, сәйкес түйінге келіп түсетін жиектердегі хабарларды ұзындығы 2-ге тең вектор ретінде көрсетуге болады: бірінші элемент – 0-де есептелген хабар, екінші элемент – 1-де есептелген хабар. Егер айнымалы нақты сандар жиынына жатса, хабарлар кез келген функциялар болуы мүмкін, және оларды көрсетуде ерекше сақтық қажет. Іс жүзінде сома-көбейту алгоритмі статистикалық қорытындыларға қолданылады, мұнда – бірлескен үлестірім немесе бірлескен ықтималдық функциясы болып табылады, ал факторлау айнымалылар арасындағы шартты тәуелсіздіктерге байланысты. Хаммерсли-Клиффорд теоремасы басқа ықтималдық модельдерді, мысалы, Байес желілерін және Марков желілерін факторлық графиктер ретінде көрсетуге болатынын көрсетеді; соңғы көрсету мұндай желілерде сенім таратуды қолдана отырып қорытынды жасау кезінде жиі қолданылады. Екінші жағынан, Байес желілері генеративтік модельдер үшін табиғирақ сәйкес келеді, өйткені олар модельдің себептік байланыстарын тікелей көрсете алады.