\batchmode
\documentstyle[jair,twoside,11pt,theapa]{article}
\makeatletter

\jairheading{4}{1996}{397-417}{12/95}{5/96}

\ShortHeadings{Further Experimental Evidence against the Utility of Occam's
Razor}{Webb}
\firstpageno{397}







\def\citeP#1{\citeauthor{#1}'s \citeyear{#1}}

\def\c#1{\multicolumn{1}{c|}{#1}}

\def\and{\;\&\linebreak[1]\;}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$^\prime$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline879: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$_2$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline885: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}

\begin{picture}(120,120)(-20,-10)

\put(0,0){\line(0,1){100}}
\multiput(10,-2)(10,0){10}{\line(0,1){2}}
\put(10,-8){\makebox(0,0){1}}
\put(20,-8){\makebox(0,0){2}}
\put(30,-8){\makebox(0,0){3}}
\put(40,-8){\makebox(0,0){4}}
\put(50,-8){\makebox(0,0){5}}
\put(60,-8){\makebox(0,0){6}}
\put(70,-8){\makebox(0,0){7}}
\put(80,-8){\makebox(0,0){8}}
\put(90,-8){\makebox(0,0){9}}
\put(100,-8){\makebox(0,0){10}}

\put(50,-20){\makebox(0,0){A}}

\put(0,0){\line(1,0){100}}
\multiput(-2,10)(0,10){10}{\line(1,0){2}}
\put(-5,10){\makebox(0,0)[r]{1}}
\put(-5,20){\makebox(0,0)[r]{2}}
\put(-5,30){\makebox(0,0)[r]{3}}
\put(-5,40){\makebox(0,0)[r]{4}}
\put(-5,50){\makebox(0,0)[r]{5}}
\put(-5,60){\makebox(0,0)[r]{6}}
\put(-5,70){\makebox(0,0)[r]{7}}
\put(-5,80){\makebox(0,0)[r]{8}}
\put(-5,90){\makebox(0,0)[r]{9}}
\put(-5,100){\makebox(0,0)[r]{10}}

\put(-20, 50){\makebox(0,0){B}}


\put(50,20){\makebox(0,0){+}}
\put(10,50){\makebox(0,0){+}}
\put(20,10){\makebox(0,0){+}}


\put(60,30){\makebox(0,0){--}}
\put(70,60){\makebox(0,0){--}}
\put(90,10){\makebox(0,0){--}}
\put(60,70){\makebox(0,0){--}}
\put(70,90){\makebox(0,0){--}}
\put(80,80){\makebox(0,0){--}}
\put(60,90){\makebox(0,0){--}}

\put(50,0){\dashbox{0.5}(0,14){}}
\put(50,26){\dashbox{0.5}(0,74){}}


\multiput(2,60)(10,0){5}{.}
\multiput(2,70)(10,0){5}{.}
\multiput(2,80)(10,0){5}{.}
\multiput(2,90)(10,0){5}{.}
\multiput(2,100)(10,0){5}{.}

\multiput(7,55)(10,0){5}{.}
\multiput(7,65)(10,0){5}{.}
\multiput(7,75)(10,0){5}{.}
\multiput(7,85)(10,0){5}{.}
\multiput(7,95)(10,0){5}{.}

\end{picture}

\end{center}


\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$0.3 \times 0.3 + 0.7 \times 0.7 = 0.58$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline927: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$max = \infty$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline967: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$min = -\infty$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline971: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{displaymath}\frac{P+1}{T+2}\end{displaymath}
}

{\newpage
\clearpage
\samepage \begin{figure}\rule{\textwidth}{.5mm}
\vbox spread -3ex {\small 
\vspace*{6pt}
Let $cases(n)$ denote the set of all training examples
that can reach node $n$.

\vspace*{2pt}
Let $value(a, x)$ denote the value of attribute $a$ for training
example
$x$.

\vspace*{2pt}
Let $pos(X, c)$ denote the number of objects of class $c$ in the
set of training examples $X$.

\vspace*{2pt}
Let $Laplace(X, c) = \frac{pos(X,c)+1}{|X|+2}$ where $X$ is a set
of training examples, $|X|$ is the number of training examples and $c$
is a class.

\vspace*{2pt}
Let $upperlim(n, a)$ denote the minimum value of a cut on attribute $a$
for an ancestor node of $n$ for which $n$ lies below a $<=$ branch.  If
there is no such cut, $upperlim(n, a) = \infty$.  This determines an upper bound
on the values for $a$ that may reach
$n$.

\vspace*{2pt}
Let $lowerlim(n, a)$ denote the maximum value of a cut on attribute
$a$ for an ancestor node of $n$ for which $n$ lies below a $>$
branch.  If there is no such cut, $lowerlim(n, a) = -\infty$.  This
determines a lower bound on the values for $a$ that may reach $n$.

\vspace*{5pt}
To post-process leaf $l$ dominated by class $c$
\begin{enumerate}\setlength{\itemsep}{.5\itemsep}
\item
Find values of
\begin{description}\item $n_a \!\!: n_a$ is an ancestor of $l$
\item $a_a \!\!: a_a$ is a continuous attribute
\item $v_a \!\!: \exists x \!\!: x \in cases(n_a) \and v_a = value(a_a, x)
\and v_a<= min(v \!\!: \exists y\!\!: y \in cases(l) \and v
= value(a_a,  y))
\and v_a > lowerlim(l, a_a)$
\item $c_a \!\!: c_a$ is a class
\end{description}
that maximize ${\cal L}_a = Laplace(\{x\!\!: x \in cases(n_a) \and value(a_a,
x)
<= v_a \and value(a_a, x) > lowerlim(l, a_a)\}, c_a)$.

\item
Find values of
\begin{description}\item $n_b \!\!: n_b$ is an ancestor of $l$
\item $a_b \!\!: a_b$ is a continuous attribute
\item $v_b \!\!: \exists x\!\!: x \in cases(n_b) \and v_b = value(a_b,  x)
\and v_b > max(v \!\!: \exists y\!\!: y \in cases(l) \and v = value(a_b, 
y))
\and v_b <= upperlim(l, a_b)$
\item $c_b \!\!: c_b$ is a class
\end{description}
that maximize ${\cal L}_b = Laplace(\{x\!\!: x \in cases(n_b) \and value(a_b,
x) > v_b \and value(a_b, x) <= upperlim(l, a_b)\}, c_b)$.

\item If ${\cal L}_a > Laplace(cases(l), c) \and
{\cal L}_a \ge {\cal L}_b$ then

  \begin{enumerate}\item if $c_a \neq c$

      \begin{enumerate}\item replace $l$ with a node $n$ with the test $a_a <= v_a$.
      \item set the $<=$ branch for $n$ to lead to a new leaf for class
            $c_a$.
      \item set the $>$ branch for $n$ to lead to $l$.
      \end{enumerate}
  \end{enumerate}

else if ${\cal L}_b >
         Laplace(cases(l), c)$
  \begin{enumerate}\item[(b)] if $c_b \neq c$

      \begin{enumerate}
      \item replace $l$ with a node $n$ with the test $a_b <= v_b$.
      \item set the $>$ branch for $n$ to lead to a new leaf for class $c_b$.
      \item set the $<=$ branch for $n$ to lead to $l$.
      \end{enumerate}
  \end{enumerate}
\end{enumerate}
}
\vspace*{-12pt}
\raise 6pt \hbox{\rule{\textwidth}{.5mm}}

\label{alg:post-process}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$n_a$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1151: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$n_b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1153: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a_a$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1155: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a_b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1157: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$v_a$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1159: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$v_b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1161: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\overline{x}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1167: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}\begin{center}

\begin{picture}(120,120)(-20,-10)

\put(0,0){\line(0,1){100}}
\multiput(10,-2)(10,0){10}{\line(0,1){2}}
\put(10,-8){\makebox(0,0){1}}
\put(20,-8){\makebox(0,0){2}}
\put(30,-8){\makebox(0,0){3}}
\put(40,-8){\makebox(0,0){4}}
\put(50,-8){\makebox(0,0){5}}
\put(60,-8){\makebox(0,0){6}}
\put(70,-8){\makebox(0,0){7}}
\put(80,-8){\makebox(0,0){8}}
\put(90,-8){\makebox(0,0){9}}
\put(100,-8){\makebox(0,0){10}}

\put(50,-20){\makebox(0,0){A}}

\put(0,0){\line(1,0){100}}
\multiput(-2,10)(0,10){10}{\line(1,0){2}}
\put(-5,10){\makebox(0,0)[r]{1}}
\put(-5,20){\makebox(0,0)[r]{2}}
\put(-5,30){\makebox(0,0)[r]{3}}
\put(-5,40){\makebox(0,0)[r]{4}}
\put(-5,50){\makebox(0,0)[r]{5}}
\put(-5,60){\makebox(0,0)[r]{6}}
\put(-5,70){\makebox(0,0)[r]{7}}
\put(-5,80){\makebox(0,0)[r]{8}}
\put(-5,90){\makebox(0,0)[r]{9}}
\put(-5,100){\makebox(0,0)[r]{10}}

\put(-20, 50){\makebox(0,0){B}}


\put(50,20){\makebox(0,0){+}}
\put(10,50){\makebox(0,0){+}}
\put(20,10){\makebox(0,0){+}}


\put(20,90){\makebox(0,0){--}}


\put(60,30){\makebox(0,0){--}}
\put(70,60){\makebox(0,0){--}}
\put(90,10){\makebox(0,0){--}}
\put(60,70){\makebox(0,0){--}}
\put(70,90){\makebox(0,0){--}}
\put(80,80){\makebox(0,0){--}}
\put(60,90){\makebox(0,0){--}}

\put(50,0){\dashbox{0.5}(0,14){}}
\put(50,26){\dashbox{0.5}(0,74){}}


\multiput(2,60)(10,0){5}{.}
\multiput(2,70)(10,0){5}{.}
\multiput(2,80)(10,0){5}{.}
\multiput(2,90)(10,0){5}{.}
\multiput(2,100)(10,0){5}{.}

\multiput(7,55)(10,0){5}{.}
\multiput(7,65)(10,0){5}{.}
\multiput(7,75)(10,0){5}{.}
\multiput(7,85)(10,0){5}{.}
\multiput(7,95)(10,0){5}{.}

\end{picture}

\end{center}


\label{fig:extended-attr-space}
\end{figure}
}

\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{section}

\end{document}
