5.1 Naïve inference

This representation scheme immediately suggests an algorithm for inference—although in fact it is a bad one, as we shall see. Naïvely, we can represent the joint distribution simply as the product of all the conditionals, and then collapse over (marginalize out) all the variables not of interest:

Now think about how many operations were carried out by the single call to sum: In short, $2^{8}$ numbers (the tabular representation of the joint distribution) were reduced to $2^{1}$ numbers by addition, so $2^{8}-2$ additions were carried out. In general, the costs of such a reduction will be¹¹ 1 This cost could surely be called $2^{8}$, but for consistency with what follows, we will use the glass-half-full $2^{7}$, the reduction across the first axis dominating all subsequent ones. $\mathcal{O}({K}^{N-1})$, with ${K}$ the number of states a single discrete random variable can take on, and $N$ the number of such variables—in a word, exponentially expensive in the number of variables. In a graph with hundreds of variables, such an approach to inference is infeasible.