For MAP queries in graphical models, we introduce another operation on factors called maximization.
Let X be a set of variables, a variable, and a factor. We define factor maximization of Y in to be a factor over the variables X such that the following occurs:
Let's take an example of factor maximization to make this clearer:
Therefore, in the preceding example of the A -> B network, we had .Also, another important property of maximization is that it can be inserted in equations if some of the factors don't involve the variable over which the maximization is being performed. More formally, for a variable :
This is a very important property of maximization as it allows us to push the maximization operation inside equations, as we used to push summation in the case of the variable elimination operation. This avoids the full joint distribution and allows us to operate on much smaller factors.
Let's now try a sample...