Байесовские сети могут использовать порядок исключения переменных из-за встроенных предположений условной независимости.
В частности, представьте, что у вас есть совместное распределение P (a, b, c, d) и вы хотите знать маргинальный P (a). Если вы ничего не знали об условной независимости, вы можете рассчитать ее, суммируя по b, c и d. Если у них есть k-арные домены, вам нужно выполнить O (k ^ 3) операций.
С другой стороны, предположим, что у вас есть байесовская сеть, где A - корень, B - дочерний элемент A, C - дочерний элемент B, а D - дочерний элемент C. Затем вы можете переписать соединение как P (a | b) P (b | c) P (c | d) P (d) и распределите ваши три суммирования как можно дальше справа от уравнения. Когда вы действительно хотите вычислить P (a), вы можете предварительно вычислить значение sum_d P (d) и сохранить эту функцию. Аналогично, вы можете предварительно вычислить значение P (c | d) * sum_d P (d) и сохранить его.
Таким образом, вы заканчиваете тем, что выполняете работу O (k ^ w * + 1), где W * - наибольшее число дочерних элементов, которое имеет любой узел в вашей байесовской сети. В этом случае мы выполняем O (k ^ 2) работу, которая также является размером самой большой таблицы условных вероятностей, которую мы должны хранить в памяти. Обратите внимание, что это лучше, чем наш исходный результат O (k ^ 3), и было бы еще лучше, если бы у нас было больше переменных.
Короче говоря, условная независимость BN позволяет более эффективно изолировать переменные. Другое объяснение этому можно найти на http://www.cs.uiuc.edu/class/sp08/cs440/notes/varElimLec.pdf.