
\slidehead{Evaluating Hypotheses}

\centerline{[Read Ch. 5]}
\centerline{[Recommended exercises: 5.2, 5.3, 5.4]}


\bi
\item Sample error, true error
\item Confidence intervals for observed hypothesis error
\item Estimators
\item Binomial distribution, Normal distribution, Central Limit Theorem
\item Paired $t$ tests
\item Comparing learning methods
\ei

\slidehead{\large Two Definitions of Error}

The {\bf true error} of hypothesis $h$ with respect to target function $f$ and
distribution $\cal{D}$ is the probability that $h$ will misclassify an
instance drawn at random according to $\cal{D}$.
\[error_{\cal{D}}(h) \equiv \Pr_{x \in \cal{D}}[f(x) \neq h(x)] \]

\vspace*{.5in}
The {\bf sample error} of $h$ with respect to target function $f$ and data
sample $S$ is the proportion of examples $h$ misclassifies
\[error_{S}(h) \equiv \frac{1}{n}\sum_{x \in S}\delta(f(x) \neq h(x)) \]
Where $\delta(f(x) \neq h(x))$ is 1 if $f(x) \neq h(x)$, and 0 otherwise.

\vspace*{.5in}

How well does $error_{S}(h)$ estimate $error_{\cal{D}}(h)$?

\slidehead{\large Problems Estimating Error}

\be
\item
{\em Bias:}
If $S$ is training set, $error_{S}(h)$ is optimistically biased

\[bias \equiv E[ error_{S}(h)] - error_{\cal{D}}(h) \]

For unbiased estimate, $h$ and $S$ must be chosen independently


\item
{\em Variance:} Even with unbiased $S$, $error_{S}(h)$ may still {\em vary}
from $error_{\cal{D}}(h)$
\ee

\slidehead{\large Example}

Hypothesis $h$ misclassifies 12 of the 40 examples in $S$

\[ error_{S}(h) = \frac{12}{40} = .30 \]

What is $error_{\cal{D}}(h)$?

\slidehead{\large Estimators}

Experiment:
\be
\item choose sample $S$ of size $n$ according to distribution $\cal{D}$

\item measure $error_{S}(h)$
\ee

$error_{S}(h)$ is a random variable (i.e., result of an experiment)

\bigskip
$error_{S}(h)$ is an unbiased {\em estimator} for $error_{\cal{D}}(h)$

\bigskip
Given observed $error_{S}(h)$ what can we conclude about $error_{\cal{D}}(h)$?


\slidehead{\large Confidence Intervals}

If
\bi
\item
$S$ contains $n$ examples, drawn independently of $h$ and each other

\item
$n \geq 30$
\ei
Then
\bi
\item
With approximately 95\% probability, $error_{\cal{D}}(h)$ lies in interval
\[ error_{S}(h) \pm 1.96 \sqrt{\frac{error_{S}(h) (1 - error_{S}(h))}{n}} \]
\ei

\slidehead{\large Confidence Intervals}

If
\bi
\item
$S$ contains $n$ examples, drawn independently of $h$ and each other

\item
$n \geq 30$
\ei
Then
\bi
\item
With approximately N\% probability, $error_{\cal{D}}(h)$ lies in interval
\[ error_{S}(h) \pm z_{N} \sqrt{\frac{error_{S}(h) (1 - error_{S}(h))}{n}} \]
where

\begin{center}
\begin{tabular}{|c|ccccccc|} \hline
 $N\%$: & 50\% & 68\% & 80\% & 90\% & 95\% & 98\% & 99\% \\
 $z_{N}$: & 0.67 & 1.00 & 1.28 & 1.64 & 1.96 & 2.33 & 2.58 \\ \hline
\end{tabular}
\end{center}
\ei

\slidehead{\large $error_{S}(h)$ is a Random Variable}

Rerun the experiment with different randomly drawn $S$ (of size $n$)
\bigskip

Probability of observing $r$ misclassified examples:

{\center \hbox{\psfig{file=./bookps/binom40-0.3.eps,width=5in}}}

\[P(r)  = \frac{n!}{r!(n-r)!}\ error_{\cal{D}}(h)^{r}
(1-error_{\cal{D}}(h))^{n-r} \]


\slidehead{\large Binomial Probability Distribution}


{\center \hbox{\psfig{file=./bookps/binom40-0.3.eps,width=5in}}}

\[P(r)  = \frac{n!}{r!(n-r)!}\ p^{r} (1- p)^{n-r} \]

Probability $P(r)$ of $r$ heads in $n$ coin flips, if $p = \Pr(heads)$

\bi
\item
Expected, or mean value of $X$, $E[X]$, is
\[ E[X] \equiv  \sum_{i=0}^{n} i P(i) = np \]

\item
Variance of $X$ is
\[ Var(X) \equiv E[(X - E[X])^{2}] = np(1-p) \]

\item
 Standard deviation of $X$, $\sigma_{X}$, is
\[ \sigma_{X} \equiv  \sqrt{E[(X - E[X])^{2}]} = \sqrt{np(1-p)} \]

\ei

\slidehead{\large Normal Distribution Approximates Binomial}

$error_{S}(h)$ follows a {\em Binomial} distribution, with

\bi
\item
mean $\mu_{error_{S}(h)} = error_{\cal{D}}(h)$

\item
standard deviation $\sigma_{error_{S}(h)}$
\[\sigma_{error_{S}(h)} = \sqrt{\frac{error_{\cal{D}}(h) 
(1 - error_{\cal{D}}(h))}{n}} \]

\ei

\vspace*{.7in}

Approximate this by a {\em Normal} distribution with

\bi
\item
mean $\mu_{error_{S}(h)} = error_{\cal{D}}(h)$

\item
standard deviation $\sigma_{error_{S}(h)}$
\[\sigma_{error_{S}(h)} \approx \sqrt{\frac{error_{S}(h) 
(1 - error_{S}(h))}{n}} \]
\ei


\slidehead{\large Normal Probability Distribution}


{\center{\hbox{\psfig{file=./bookps/gaussian.eps,width=4in}}}}

\[ p(x) = \frac{1}{\sqrt{2 \pi \sigma^{2}}} e^{-\frac{1}{2}(\frac{x -
\mu}{\sigma})^{2}}\]

The probability that $X$ will fall into the interval $(a,b)$ is given by
\[ \int_{a}^{b} p(x) dx \]

\bi
\item
Expected, or mean value of $X$, $E[X]$, is
\[ E[X] = \mu \]

\item
Variance of $X$ is
\[ Var(X) = \sigma^{2} \]

\item
 Standard deviation of $X$, $\sigma_{X}$, is
\[ \sigma_{X} = \sigma  \]

\ei

\slidehead{\large Normal Probability Distribution}

{\center{\hbox{\psfig{file=./bookps/g2.eps,width=4in}}}}

80\% of area (probability) lies in $\mu \pm 1.28 \sigma$

\bigskip

N\% of area (probability) lies in $\mu \pm z_{N} \sigma$

\bigskip

\begin{center}
\begin{tabular}{|c|ccccccc|} \hline
 $N\%$: & 50\% & 68\% & 80\% & 90\% & 95\% & 98\% & 99\% \\
 $z_{N}$: & 0.67 & 1.00 & 1.28 & 1.64 & 1.96 & 2.33 & 2.58 \\ \hline
\end{tabular}
\end{center}
\slidehead{\large Confidence Intervals, More Correctly}

If
\bi
\item
$S$ contains $n$ examples, drawn independently of $h$ and each other

\item
$n \geq 30$
\ei
Then
\bi
\item
With approximately 95\% probability, $error_{S}(h)$ lies in interval
\[ error_{\cal{D}}(h) \pm 1.96 \sqrt{\frac{error_{\cal{D}}(h) (1 - error_{\cal{D}}(h))}{n}} \]
\ei

\vspace*{.1in}
equivalently, $error_{\cal{D}}(h)$ lies in interval
\[ error_{S}(h) \pm 1.96 \sqrt{\frac{error_{\cal{D}}(h) (1 - error_{\cal{D}}(h))}{n}} \]

\vspace*{.1in}
which is approximately
\[ error_{S}(h) \pm 1.96 \sqrt{\frac{error_{S}(h) (1 - error_{S}(h))}{n}} \]


\slidehead{\large Central Limit Theorem}

Consider a set of independent, identically distributed random variables $Y_{1}
\ldots Y_{n}$, all governed by an arbitrary probability distribution with mean
$\mu$ and finite variance $\sigma^{2}$.  Define the sample mean,
\[\bar{Y}\equiv\frac{1}{n}\sum_{i=1}^{n}Y_{i} \]

\vspace{1in}

{\bf Central Limit Theorem.}  As $n \ra \infty$, the distribution governing
$\bar{Y}$ approaches a Normal distribution, with mean $\mu$ and variance
$\frac{\sigma^{2}}{n}$.

%The Central Limit Theorem states that the sum of a large number of
%independent, identically distributed random variables follows a distribution
%that is approximately Normal.

\slidehead{\large Calculating Confidence Intervals}

\be
\item
Pick parameter $p$ to estimate 
\bi \item $error_{\cal{D}}(h)$ \ei

\item
Choose an estimator 
\bi \item $error_{S}(h)$ \ei

\item
Determine probability distribution that governs estimator
\bi \item  $error_{S}(h)$ governed by Binomial distribution, approximated by
Normal when $n \geq 30$ \ei

\item
Find interval ($L, U$) such that N\% of probability mass falls in the interval
\bi \item Use table of $z_{N}$ values \ei
\ee


\slidehead{\large Difference Between Hypotheses}

Test $h_{1}$ on sample $S_{1}$, test $h_{2}$ on $S_{2}$
\be
\item
Pick parameter to estimate 
\[ d \equiv error_{\cal{D}}(h_{1}) - error_{\cal{D}}(h_{2}) \]

\item
Choose an estimator
\[ \hat{d} \equiv error_{S_{1}}(h_{1}) - error_{S_{2}}(h_{2}) \]

\item
Determine probability distribution that governs estimator
\[\small \sigma_{\hat{d}} \approx \sqrt{\frac{error_{S_{1}}(h_{1})(1 - error_{S_{1}}(h_{1}))}{n_{1}} + \frac{error_{S_{2}}(h_{2})(1 - error_{S_{2}}(h_{2}))}{n_{2}}}\]

\item
Find interval ($L, U$) such that N\% of probability mass falls
in the interval \ee
\[ \hat{d} \pm z_{N} \sqrt{\frac{error_{S_{1}}(h_{1})(1 -
error_{S_{1}}(h_{1}))}{n_{1}} + \frac{error_{S_{2}}(h_{2})(1 -
error_{S_{2}}(h_{2}))}{n_{2}} } \]


\slidehead{\large Paired $t$ test to compare $h_{A}$,$h_{B}$}

\be
\item
Partition data into $k$ disjoint test sets $T_{1}, T_{2},
\ldots, T_{k}$ of equal size, where this size is at least 30.
\item
For $i$ from 1 to $k$, do
\bi
\item[]
$\delta_{i} \la error_{T_{i}}(h_{A}) - error_{T_{i}}(h_{B})$
\ei
\item[]\hspace*{-.3in}

\item
Return the value $\bar{\delta}$, where
\[\bar{\delta} \equiv \frac{1}{k}\sum_{i=1}^{k} \delta_{i}\]
\ee

\rule{\textwidth}{.2mm}\vskip -3mm

$N$\% confidence interval estimate for $d$:
\[ \bar{\delta} \pm t_{N,k-1} \ s_{\bar{\delta}} \]
\[  s_{\bar{\delta}} \equiv \sqrt{\frac{1}{k(k-1)} \sum_{i=1}^{k}(\delta_{i} -
\bar{\delta})^{2}} \]

{\em Note $\delta_{i}$ approximately Normally distributed}

\slidehead{\large Comparing learning algorithms $L_{A}$ and $L_{B}$}

What we'd like to estimate:

\[ E_{S \subset \cal{D}}[ error_{\cal{D}}(L_{A}(S)) -
error_{\cal{D}}(L_{B}(S))] \]
where $L(S)$ is the hypothesis output by learner $L$ using training set $S$

\bigskip

i.e., the expected difference in true error between hypotheses output by
learners $L_A$ and $L_B$, when trained using randomly selected training sets
$S$ drawn according to distribution $\cal{D}$.


\vspace*{.5in}
But, given limited data $D_0$, what is a good estimator?

\bi
\item could partition $D_0$ into training set $S$ and training set $T_0$, and
measure
\[ error_{T_{0}}(L_{A}(S_{0})) - error_{T_{0}}(L_{B}(S_{0})) \]
\item even better, repeat this many times and average the results (next slide)
\ei

\slidehead{\large Comparing learning algorithms $L_{A}$ and $L_{B}$}

\be
\item
Partition data $D_{0}$ into $k$ disjoint test sets $T_{1}, T_{2},
\ldots, T_{k}$ of equal size, where this size is at least 30.
\item
For $i$ from 1 to $k$, do
\bi
\item[]\hspace*{-.3in}
{\em use $T_{i}$ for the test set, and the remaining data for training set
$S_{i}$}
\item $S_{i} \la \{D_{0} - T_{i}\}$
\item
$h_{A} \la L_{A}(S_{i})$
\item
$h_{B} \la L_{B}(S_{i})$
\item
$\delta_{i} \la error_{T_{i}}(h_{A}) - error_{T_{i}}(h_{B})$
\ei
\item
Return the value $\bar{\delta}$, where
\[\bar{\delta} \equiv \frac{1}{k}\sum_{i=1}^{k} \delta_{i}\]
\ee

\slidehead{\large Comparing learning algorithms $L_{A}$ and $L_{B}$}

Notice we'd like to use the paired $t$ test on $\bar{\delta} $ to obtain a
confidence interval

\bigskip

but not really correct, because the training sets in this algorithm are not
independent (they overlap!)

\bigskip

more correct to view algorithm as producing an estimate of 

\[E_{S \subset D_{0}}[ error_{\cal{D}}(L_{A}(S)) - error_{\cal{D}}(L_{B}(S))]
\]

instead of 

\[ E_{S \subset \cal{D}}[ error_{\cal{D}}(L_{A}(S)) -
error_{\cal{D}}(L_{B}(S))] \]

\bigskip
but even this approximation is better than no comparison
