4
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ I think your problem is too general. You need to give more specification on the properties of your hypothesis characterization, and your inputs $\endgroup$ – Daniel Nov 28 '13 at 19:26
  • $\begingroup$ @Daniel I have edited the question. $\endgroup$ – seteropere Nov 28 '13 at 21:03
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I am learning a DAG model (similar to Bayesian Networks). So each hypothesis represents a possible DAG. I should look deeply in finding an efficient method to this. Thanks! $\endgroup$ – seteropere Nov 25 '13 at 17:11
  • $\begingroup$ is it valid practice to choose $m$ hypotheses from $\mathcal{H}$ to compute the region of uncertainty? I am making up a representative measure for choosing them $\endgroup$ – seteropere Nov 25 '13 at 21:12
  • 1
    $\begingroup$ In general no. Imagine your class has $n-1$ hypotheses that completely agree and $1$ that's very different. Via sampling, before you even see any data, you are likely to think there is no region of uncertainty, whereas the reality could be very different. But whether this is a good strategy or not heavily depends on your goal. For instance, if for a given point, you want to measure how "uncertain" hypotheses are about it, and you're okay with some error, then sampling is fine. These are of course two extremes... $\endgroup$ – Lev Reyzin♦ Nov 25 '13 at 21:46
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The target order may be partial. I do exactly what you stated. My issue is in how to choose a set of representative hypotheses from the set of all possible DAGs consistent with the current examples. I can create the representative hypotheses artificially but I am not sure whether its a valid practice. $\endgroup$ – seteropere Nov 29 '13 at 19:15
  • $\begingroup$ @seteropere, you asked how to compute the region of uncertainty. I've answered that question: I've described a way to do that. (You don't need to choose a set of representative hypotheses to compute the region of uncertainty. I've answered the question you asked, so if what you asked isn't what you really wanted, you might need to edit the question?) $\endgroup$ – D.W. Nov 29 '13 at 19:50
  • $\begingroup$ It seems I am missing something obvious here. I thought I cannot compute disagreements without choosing a subset of hypotheses. $\endgroup$ – seteropere Nov 29 '13 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.