Второе важное семейство алгоритмов аппроксимации основано на алгоритме Перла передачи сообщений в полидереве [1186]. Как указал Перл [1191], этот алгоритм может применяться к сетям общего типа. Иногда результаты оказываются неправильными, или же не удается добиться нормального завершения работы алгоритма, но во многих случаях полученные значения близки к истинным значениям. Так называемый подход с распространением оценок степени уверенности (или с циклическим распространением) привлекал мало внимания до тех пор, пока Макэлис и др. [1027] не обнаружили, что передача сообщений в многосвязной байесовской сети полностью аналогична вычислениям, выполняемым в алгоритме турбодекодирования (turbo decoding) [115], который оказался крупным научным прорывом в области разработки эффективных кодов коррекции ошибок. Из этого следует вывод, что способ циклического распространения быстро и точно работает в очень крупных и тесно связанных сетях, используемых для декодирования, и поэтому может найти более широкое применение. В [1105] представлены результаты эмпирического исследования областей использования этого алгоритма. В [1630] подробно описаны связи между методом циклического распространения и идеями статистической физики.

Связь между вероятностными методами и языками первого порядка была впервые исследована Карнапом [225]. В [513] и [1373] определен язык, в котором вероятности могут быть объединены с высказываниями первого порядка и для которого моделями являются вероятностные показатели в возможных мирах. В рамках искусственного интеллекта эта идея была разработана Нильссоном для пропозициональной логики [1144] и Халперном для логики первого порядка [607]. Результаты первого обширного исследования проблем представления знаний в таких языках были опубликованы в [51], а в [1577] приведен обзор первых подходов к реализации этих способов представления на основе формирования эквивалентных пропозициональных байесовских сетей. В дальнейшем исследователи пришли к пониманию важности полных баз знаний, т.е. баз знаний, в которых, как и в байесовских сетях, определяется уникальное совместное распределение по всем возможным мирам. Методы осуществления этого были основаны на вероятностных версиях логического программирования [1226], [1352] или на семантических сетях [823]. Реляционные вероятностные модели такого типа, описанные в данной главе, были глубоко исследованы Пфеффером [1210]. В [1179] приведены результаты исследования проблем реляционной неопределенности и неопределенности идентичности в рамках моделей RPM, а также результаты использования вероятностного вывода с помощью алгоритма МСМС.