How to compute the disagreement between hypotheses

Question

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}$

Answer 1

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.

Answer 2

Given your edit, the question now looks trivial. The structure on $\mathcal{O}$ is irrelevant. Basically, you are given a set $\mathcal{O}$ and a set of pairs $a_i,b_i$ with the promise that $a_i < b_i$ for some total order $<$. You want to find all pairs $a',b'$ such that there exists some total orders $<_1,<_2$ that are consistent with all the examples and such that $a' <_1 b'$ and $a' >_2 b'$.

Assuming I've got all that right, that's an easy problem to solve, computationally. Basically, build a DAG with an edge $a_i \to b_i$ for each $i$. Compute the transitive closure of the DAG. Now, if there's an edge $a' \to b'$ in the transitive closure, then you know $a' < b'$ in all possible orders. On the other hand, for any pair of vertices $a',b'$ that are not connected by an edge in the transitive closure, you could have either $a' < b'$ or $a' > b'$. So, that's the region of uncertainty: the set of pairs of vertices $a',b'$ that are not connected by an edge in the transitive closure of this DAG.

If I haven't got all that right, you might need to provide a clearer statement of the problem in the question.