\slidehead{Outline \red \ } \bk
\bi
\item Why Machine Learning?
\item What is a well-defined learning problem?
\item An example: learning to play checkers
\item What questions should we ask about Machine Learning?
\ei

\slidehead{Why Machine Learning \red \ } \bk

\bi
\item Recent progress in algorithms and theory 
\item Growing flood of online data
\item Computational power is available
\item Budding industry
\ei

\bigskip
Three niches for machine learning:

\bi
\item Data mining : using historical data to improve decisions
\bi \item medical records $\ra$ medical knowledge \ei
\item Software applications we can't program by hand 
\bi \item autonomous driving \item speech recognition \ei
\item Self customizing programs 
\bi \item Newsreader that learns user interests \ei
\ei


\slidehead{Typical Datamining Task \red \ }
\bk

\vspace*{-.3in}

Data:
\vspace{.2in}

\centerline{\hbox{\psfig{file=./bookps/csec.ps,width=7in}}}

\bl \rule{\textwidth}{.2mm} \bk

Given:
\bi
\item
9714 patient records, each describing a pregnancy and birth

\item
Each patient record contains 215 features
\ei
 Learn to predict:
\bi
\item Classes of future patients at high risk for Emergency Cesarean Section
\ei



\slidehead{Datamining Result \red \ }
\bk

\vspace*{-.3in}

Data:
\vspace{.2in}

\centerline{\hbox{\psfig{file=./bookps/csec.ps,width=7in}}}

\bl \rule{\textwidth}{.2mm} \bk
One of 18 learned rules:

\begin{verbatim}
If   No previous vaginal delivery, and
     Abnormal 2nd Trimester Ultrasound, and
     Malpresentation at admission
Then Probability of Emergency C-Section is 0.6

 Over training data: 26/41 = .63, 
 Over test data: 12/20 = .60
\end{verbatim}



\slidehead{Credit Risk Analysis \red \ }
\bk

\vspace*{-.3in}

Data:
\vspace{.2in}

\centerline{\hbox{\psfig{file=./bookps/credit-outcomes.ps,width=7in}}}

\bl \rule{\textwidth}{.2mm} \bk
Rules learned from synthesized data:
\begin{verbatim}

If   Other-Delinquent-Accounts > 2, and
     Number-Delinquent-Billing-Cycles > 1
Then Profitable-Customer? = No
     [Deny Credit Card application]

If   Other-Delinquent-Accounts = 0, and
     (Income > $30k)  OR  (Years-of-Credit > 3)
Then Profitable-Customer? = Yes
     [Accept Credit Card application]
\end{verbatim}



\slidehead{Other Prediction Problems \red \ }
\bk

\vspace*{-.4in}

Customer purchase behavior:

\centerline{\hbox{\psfig{file=./bookps/customer-outcomes.ps,width=6.3in}}}

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

\vspace*{.1in}

Customer retention:

\vspace*{.1in}


\centerline{\hbox{\psfig{file=./bookps/bank-customer.ps,width=6.3in}}}

%  bank-customer.ps
%  customer-outcomes.ps

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

Process optimization:

\vspace*{.1in}


\centerline{\hbox{\psfig{file=./bookps/process-outcomes.ps,width=6.3in}}}


\slidehead{\normalsize Problems Too Difficult to Program by Hand \red \ }
\bk

ALVINN [Pomerleau] drives 70 mph on highways

\begin{picture}(469,410) %% a pt = 1/72 in
\put(70,-160){\psfig{file=./bookps/nl5-interior-front-color.ps,width=6in}}
\put(0,0){\psfig{file=./bookps/alvinn1.ps,width=2.5in}}
\put(205,40){\psfig{file=./bookps/alvinn2.ps,width=2.5in}}
\end{picture}


\slidehead{Software that Customizes to User \red \ } \bk


\centerline{\hbox{\psfig{file=./bookps/wisewire.ps,height=6.0in}}}
\centerline{http://www.wisewire.com}

\slidehead{Where Is this Headed? \red \ }\bk

Today: tip of the iceberg
\bi
\item First-generation algorithms: neural nets, decision trees, regression ...
\item Applied to well-formated database
\item Budding industry
\ei

\vspace*{.2in}

Opportunity for tomorrow: enormous impact
\bi
\item Learn across full mixed-media data
\item Learn across multiple internal databases, plus the web and newsfeeds
\item Learn by active experimentation
\item Learn decisions rather than predictions
\item Cumulative, lifelong learning
\item Programming languages with learning embedded?
\ei

\slidehead{Relevant Disciplines \red \ } \bk

\bi
\item Artificial intelligence

\item Bayesian methods

\item Computational complexity theory

\item Control theory

\item Information theory

\item Philosophy

\item Psychology and neurobiology

\item Statistics
\item $\ldots$
\ei

\slidehead{What is the Learning Problem? \red \ } \bk
\bigskip
\centerline{Learning = Improving with experience at some task}
\bi
\item Improve over task $T$,
\item with respect to performance measure $P$,
\item based on experience $E$.
\ei
\bigskip

E.g., Learn to play checkers
\bi
\item $T$: Play checkers
\item $P$: \% of games won in world tournament
\item $E$: opportunity to play against self
\ei

\slidehead{Learning to Play Checkers \red \ } \bk
\bi
\item $T$: Play checkers
\item $P$: Percent of games won in world tournament
\ei


\bi
\item What experience?
\item What exactly should be learned?
\item How shall it be represented?
\item What specific algorithm to learn it?
\ei

\slidehead{Type of Training Experience \red \ } \bk
\bi
\item Direct or indirect?
\item Teacher or not?
\ei

A problem: is training experience representative of performance goal?

\slidehead{Choose the Target Function \red \ } \bk
\bi
\item $ChooseMove: Board \ra Move$ \ ??
\item $V: Board \ra \Re$ \ ??
\item ...
\ei


\slidehead{Possible Definition for Target Function $V$ \red \ } \bk
\bi
\item if $b$ is a final board state that is won, then $V(b) = 100$

\item
 if $b$ is a final board state that is lost, then $V(b) = -100$

\item
 if $b$ is a final board state that is drawn, then $V(b) = 0$  

\item
if $b$ is a not a final state in the game, then $V(b) = V(b')$,
where $b'$ is the best final board state that can be achieved starting from
$b$ and playing optimally until the end of the game.
\ei


This gives correct values, but is not operational



\slidehead{Choose Representation for Target Function \red \ } \bk

\bi
\item collection of rules?
\item neural network ?
\item polynomial function of board features?
\item ...
\ei


\slidehead{A Representation for Learned Function \red \ } \bk
\[ w_{0} + w_{1}\cdot bp(b) + w_{2}\cdot rp(b) + w_{3}\cdot bk(b) + w_{4}\cdot rk(b) + w_{5}\cdot bt(b) + w_{6}\cdot rt(b) \]
\bi
\item
$bp(b)$: number of black pieces on board $b$

\item
$rp(b)$: number of red pieces on $b$

\item
$bk(b)$: number of black kings on $b$

\item
$rk(b)$: number of red kings on $b$

\item
$bt(b)$: number of red pieces threatened by black (i.e., which can be taken
on black's next turn)

\item
$rt(b)$:  number of black pieces threatened by red
\ei

\slidehead{Obtaining Training Examples \red \ } \bk

\bi
\item $V(b)$: the true target function
\item $\hat{V}(b)$ : the learned function
\item $V_{train}(b)$: the training value
\ei

\bigskip
One rule for estimating training values:
\bi
\item $V_{train}(b) \leftarrow \hat{V}(Successor(b))$
\ei

\slidehead{Choose Weight Tuning Rule \red \ } \bk

\begin{description} 
\item {\bf LMS Weight update rule:}
\end{description}

\begin{description} 
\item Do repeatedly:
\end{description}
\bi \item Select a training example $b$ at random
\be
\item Compute $error(b)$:
\[error(b) = V_{train}(b) - \hat{V}(b)\]

\item For each board feature $f_{i}$, update weight $w_{i}$:
\[w_{i} \leftarrow w_{i} + c \cdot f_{i} \cdot error(b) \]
\ee
\ei

$c$ is some small constant, say 0.1, to moderate the rate of learning

\slidehead{Design Choices \red \ } \bk
\hbox{\psfig{file=./bookps/intro-f1.epsf,height=6in}}

\slidehead{Some Issues in Machine Learning \red \ } \bk

\bi
\item
What algorithms can approximate functions well (and when)?
\item
How does number of training examples influence accuracy?
\item
How does complexity of hypothesis representation impact it?
\item
How does noisy data influence accuracy?
\item
What are the theoretical limits of learnability?
\item
How can prior knowledge of learner help?
\item
What clues can we get from biological learning systems?
\item
How can systems alter their own representations?
\ei
