4
$\begingroup$

I was reading the following paper and it talked about improper learning. I wasn't 100% what it rigorously meant but they do mention:

enter image description here

I am not sure what "representation independent" means, but as far as I am concerned, the learning algorithm is allowed to choose functions that might not be exactly within the restriction of the concept class $C$ that it is trying to learn. i.e. it might be trying to learn some specific type of function from samples (say trying to learn a half-space $\mathcal{H}_{n,k}$) but we allow it to choose functions of not that type, with the restriction that its error is not very far from the best of the original class in consideration.

I guess the intuition is more or less clear, but was wondering if this interpretation is correct and whether there is a more precise/rigorous way to define what improper learning is.

$\endgroup$
6
$\begingroup$

In statistical learning theory, the standard batch learning problem is defined in terms of a distribution $P$ over some space $\mathcal{Z}$ belonging to some set of distributions $\mathcal{P}$, a hypothesis class $\mathcal{H}$ and a loss function $\ell$, which assigns a (say) nonnegative real ("a loss") to pairs $(P,h)$ of distributions and hypotheses (i.e., $\ell: \mathcal{P} \times \mathcal{H} \to [0,\infty)$). Then, one is given a sequence of $n$ points $D_n = (Z_1,\dots,Z_n)\in \mathcal{Z}^n$, sampled in an iid fashion from $P$ and the job of the learning algorithm is to come up with a hypothesis $h_n\in \mathcal{H}$ based on $D_n$ that achieves a small (say) expected loss $\mathbb{E}[\ell(P,h_n)]$ (the random quantity in the above expression is $h_n$: $h_n$ depends on the data $D_n$, which is random, hence $h_n$ is also random).

In terms of the goal of learning, one criterion for evaluating the power of a learning algorithm is how fast the excess expected loss $\mathbb{E}[\ell(P,h_n)]-\inf_{h\in \mathcal{H}} \ell(P,h)$ (or excess risk) decreases with $n\to \infty$.

Improper learning changes this metric slightly to evaluate success by $\mathbb{E}[ \ell(P,h_n) ] - \inf_{h\in \mathcal{H}_0 } \ell(P,h)$ for some $\mathcal{H}_0\subset \mathcal{H}$. Intuitively, when $\mathcal{H}_0$ is a true subset of $\mathcal{H}$, competing with the best hypothesis from $\mathcal{H}_0$ should be easier.

Where is this coming from? Learning is all about guessing the right bias. The bias here is expressed in terms of $\mathcal{H}_0$. The designer of the algorithm makes a guess on $\mathcal{H}_0$; the guess concerns that there will be a hypothesis in $\mathcal{H}_0$ which achieves a small loss. Next, the problem is to design an algorithm. However, does it make sense to require the algorithm to output hypotheses from $\mathcal{H}_0$? Unless some specific circumstances require this, why would we make this restriction? By allowing the learning algorithm to produce hypotheses in a larger class $\mathcal{H}_1$ which is in between $\mathcal{H}_0$ and $\mathcal{H}$, the algorithm designer's flexibility is increased and hence potentially lower excess risk over the best hypothesis in $\mathcal{H}_0$ can be achieved. Why not allow then $\mathcal{H}_1 = \mathcal{H}$? The answer to this depends on how the learning algorithm uses $\mathcal{H}_1$. If it really just uses a (potentially small) subset of it, then it won't hurt to have $\mathcal{H}_1 = \mathcal{H}$. However, many learning algorithms are designed to use the full hypothesis space that they are given and they slow down (will be more conservative) when used with a larger hypothesis class. With such algorithms it makes sense to use a proper subset of $\mathcal{H}$ as $\mathcal{H}_1$.

$\endgroup$
  • $\begingroup$ In terms of the algorithm alone, $\mathcal{H}$ doesn't play any role, right? Only $\mathcal{H}_1$ and $\mathcal{H}_0$ affect the algorithm and its evaluation, right? If so, having $\mathcal{H}$ in the picture made the explanation more confusing, for me at least. $\endgroup$ – guillefix Nov 1 '17 at 15:36
  • 1
    $\begingroup$ It is true that only $\mathcal{H}_0$ and $\mathcal{H}_1$ matter. I guess a standard choice for $\mathcal{H}$ (from the point of view of improper learning) would be the set of all hypotheses (modulo measurability) and then any(!) learning algorithm is a map $\mathcal{A}$ from $\mathcal{Z}^n$ to $\mathcal{H}$, and $\mathcal{H}_1$ is the range space of $\mathcal{A}$: $\mathcal{H}_1 = \{ \mathcal{A}(d)\,:\, d\in \mathcal{Z}^n\}$. Hopefully this will make some sense. $\endgroup$ – Csaba Nov 3 '17 at 21:09

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.