# Modeling a Classification Problem with an Undirected Graphical Model

I have an undirected graphical model problem which I'm looking for some help on.

So, the goal is to perform multivariate classification: based on a set of observations, I want to predict the correct class. Let us first consider that there are four observations, $a,b,c,d$:

Now, for each pair of observations, I have trained a classifier which outputs a class probability distribution based on these two observations. For example, for observations $a$ and $b$, I know $p(y|a,b)$:

What I now want to enforce, is that all observations are actually from the same class. So, I want $p(y|a,b)$ to be high for one class, and $p(y|c,d)$ to also be high for that class, as well as $p(y|b,c)$, and so on. In this way, I could represent each pair of observations as a single node in a graphical model, and make the model fully connected:

My questions is: How do I find the most likely class, $\hat{y}$? Formally, I want to solve the following:

$\hat{y} = \text{argmax}_y \text{ } p(y\text{ }|\text{ }p(y|a,b), p(y|b,c), p(y|c,d), p(y|a,d), p(y|a,c), p(y|b,d)\text{ })$

So I basically want to take a set of "weak" classifiers, and create a "strong" classifier. By modeling it as a graphical model, the "energy" of the model could be represented by (i) the probability distributions for each pair of observations, and (ii) the pairwise terms which enforce that all observations are assigned to the same class.

Any ideas on how to do this? It reminds me of a Markov Random Field, except that (i) it is fully connected, and (ii) the pairwise cost for having different class assignments is infinite.

Thanks for any help!

• Could you clarify your question? Do you want to use a graphical model for classification or do you want to understand the specific modeling technique you proposed in the question? From what I've seen, we don't usually model things the way you've described. – Vimal Oct 14 '15 at 12:18
• Yes, I do want to use the graphical model for classification. However, I have already trained a classifier to output a probability for each pair of observations (that is just a core part of the problem that I cannot change). So I basically want to take a set of "weak" classifiers, and create a "strong" classifier, and I thought that modeling it as a graphical model, might make sense? In this way, the "energy" of the model is represented by both the probability distributions for each pair of observations, and the pairwise terms which enforce that all observations are assigned to the same class. – Karnivaurus Oct 14 '15 at 12:27
• I understand better now. You are looking at each weak classifier output as a random variable and want to design a method to combine these individual class probabilities (with appropriate weights). The general class of methods of combining a weak classifier to get a strong classifier is called "ensemble methods." This might be a useful reference: en.wikipedia.org/wiki/Boosting_(machine_learning). – Vimal Oct 14 '15 at 12:37
• Also, you might not want to heavily penalise individual classifier outputs if they are different from each other (i.e., at least one of them makes a mistake). – Vimal Oct 14 '15 at 12:38
• Thanks. But doesn't a Markov Random Field do something like this? From my understanding of MRF's, you have a unary term, and a pairwise term. So the unary terms would be the outputs of my weak classifiers, and the pairwise terms would enforce some smoothness. The smoothness here would ensure that all nodes are assigned to the same class. Why is my problem not suited to this? – Karnivaurus Oct 14 '15 at 12:41