Given a class of hypothesis $\mathcal{H}$ representing the set of all consistent hypotheses with the examples seen so far, how to compute the region of uncertainty? The region of uncertainty is defined as all points where there are two or more hypotheses disagree on its labelling. I am representing $\mathcal{H}$ as two hypotheses: most specific (MS) and most general (MG) (as described here ). $\mathcal{H}$ consists of these two and anything in between. Clearly, enumerating all possible hypotheses is infeasible due to the size of $\mathcal{H}$. To put it in one word, how to compute disagreements in practice?  EDIT: sorry for not being specific. I am trying to learn a graphical model similar to bayesian networks but instead of probabilities I have order relation.  I have a set of variables $V=\{v_1,v_2,...,v_n\}$ where each variable has a set of possible values (its domain). $V$ defines an outcome space $\mathcal{O}$ (the set of all possible assignments over $V$ from their domain values). For example, if $A=\{1,2\}$ and $B=\{3,4\}$ we have $\mathcal{O}=\{(1,3),(1,4),(2,3),(2,4)\}$. The input space $X$ is the set of all pairs of outcomes from $\mathcal{O}$. Each example $x$ consist of pairs of outcomes $a$,$b\in \mathcal{O}$ (denoted as $x[a]$,$x[b]$ respectively). The target function is a strict order relation $\succ$ over $\mathcal{O}$. I am adopting the active learning paradigm. I first choose $\mathcal{U}$ unlabelled examples, then ask the oracle to label an example $x\in \mathcal{U}$. $h(x)=+$ if $x[a]$ is better than $x[b]$ otherwise $-$. The hypothesis class $\mathcal{H}$ is the set of all possible strict (partial/total) orders consistent with the examples seen so far.  My main concern is how to select representative hypotheses from $\mathcal{H}$ 
How to compute the disagreement between hypotheses
machine learning
One major task of computational learning theory is to try to handle questions like this for specific classes.  In general, if you assume no structure on the hypothesis space, you basically have no choice but to look at each hypotheses individually.  On the other hand, if there is a lot of structure, eg. if you assume the hypotheses are linear separators, say in $\mathcal{R}^2$, you can see that it's possible to be quite efficient even though there are infinitely many linear separators!The same thing happens for trying to find the ERM (empirical risk minimizing) hypothesis in a class.  This is important for PAC learning. Sometimes it's easy, sometimes it's not.