View Single Post
Old 09-09-2014, 07:19 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Exercise 1.12 - Failing to make Ein(g) small enough

Originally Posted by PhilW View Post
Let's say I run my machine learning algorithm for my friend, taking care to ensure Ein(g) and Eout(g) are close enough, but I find that my Ein(g) = .5 or something terrible like that. What are my options for continuing to solve the machine learning problem? Is there any way for me to go back and change my hypothesis set without losing the theoretical guarantees that Ein(g) is close to Eout(g)?
Let us say that {\mathcal H}_1 is the hypothesis set that didn't work, and you want now to try another hypothesis set {\mathcal H}_2. The theoretical guarantees would still hold, but for the equivalent hypothesis set {\mathcal H}_1 \cup {\mathcal H}_2.

Just because this uses a "hierarchy" of hypothesis sets (in this case the hierarchy being {\mathcal H}_1 followed by {\mathcal H}_1 \cup {\mathcal H}_2 upon failure of {\mathcal H}_1, folllowed by possibly other expansions if {\mathcal H}_1 \cup {\mathcal H}_2 failed), there is in general an additional theoretical price to pay, but it is low. Look at structural risk minimization if you are further interested.
Where everyone thinks alike, no one thinks very much
Reply With Quote