%% August 10, 1993

\documentstyle{smjrnl}

\begin{document}


%% To be entered at Kluwers: ==>>

\journame{Small Journal Name}
\volnumber{9}
\issuenumber{4}
\issuemonth{October}
\volyear{1992}

%%%%  Issue Table of Contents %%%%

\begin{issuetoc}
\TOCarticle{Explorations of an Incremental, Bayesian Algorithm for 
Categorization}{John R. Anderson and Michael Matessa}{275}

\TOCarticle{A Bayesian Method for the Induction of Probabilistic Networks
from Data}{Gregory F. Cooper and Edward Herskovits}{309}

\TOCarticle{Learning Boolean Functions in an Infinite Attribute Space}
{Avrim Blum}{373}

\TOCarticle{Technical Note: First Nearest Neighbor Classification on Frey 
and Slate's Letter Recognition Problem}{Terence C. Fogarty}{387}

\end{issuetoc}

%%%% End of Issue Table of Contents %%%%


%% Individual article commands:

\begin{article}

\authorrunninghead{J.R. Anderson and M. Matessa}
\titlerunninghead{An Incremental, Bayesian Algorithm for Categorization}

\setcounter{page}{275} %% This command is optional. 
                       %% May set page number only for first page in
                       %% issue, if desired.

%% <<== End of commands to be entered at Kluwers 


%%  Authors, start here ==>>

\title{Explorations of an Incremental, Bayesian Algorithm
for Categorization}

\authors{John R. Anderson and Michael Matessa}
\email{ja\o s@andrew.cmu.edu}

\affil{Department of Psychology, Carnegie Mellon University, Pittsburgh,
PA 15213}

\editor{Dennis Kibler}

\abstract{An incremental categorization algorithm is described which, at each step, assigns the next instance to the most probable catagory. Etc.
}

\keywords{Bayesian inference, concept learning, human learning, 
incremental algorithms}


\section{Introduction}
We have been engaged in a project to understand human categorization which
has let us to develop a machine learning algorithm. Our research began as an
exploration of the issue of whether human categorization can be considered
optimal.

To pursue the issue of whether human cognition is optimal requires
specifying two things. First we need a definition of optimality.
second, we need a specification of the structure of the environment
so we can determine what behavior is optimal in that environment.


\subsection{Preliminary definition of optimization}
Our assumption has been that the goal of categorization is to predict
unknown features of various objects that we encounter.

\subsubsection{The structure of the environment}
Our theory of the structure of the environment has been focused the
structure of living things (arguably, the largest portion of the
objects in theworld) because of the aid biology gives in objectively
specifying the organization of these objects.


Formally, this amounts to calculating:
\begin{equation}
g_i(y|f)=\sum_x P(x|F_n)f_i(y|x)
\end{equation}
where $g_i(y|F_n)$ is the function specifying the probability an object will
display a value $y$ on a dimension $i$ given $F_n$ the observed feature
structure of all the objects.

Here is an example of a wide equation:
\begin{wideequation}
\begin{equation}
\sum_k P(k) \sum_i \sum_y f_i(y|k)^2
\sum_k P(k) \sum_i \sum_y f_i(y|k)^2
\end{equation}
\end{wideequation}

In this wide equation the `array' command is used to split 
the math into two lines, moving the top half to the left
and the bottom to the right.
\begin{wideequation}
\begin{equation}
\begin{array}{lr}
\sum_k P(k) \sum_i \sum_y f_i(y|k)^2\\
&\sum_k P(k) \sum_i \sum_y f_i(y|k)^2
\sum_k P(k) \sum_i \sum_y f_i(y|k)^2
\end{array}
\end{equation}
\end{wideequation}

\subsection{Footnote example}
Here is some text with footnotes in it.
Here is some text with footnotes in it.
Here is some text with footnotes in it.\footnote{This is a footnote.}

More text.\footnote{This is a second footnote.
This is a second footnote.
This is a second footnote.
This is a second footnote.
This is a second footnote.
This is a second footnote.} 
More text.\footnote{This is yet another footnote.
This is yet another footnote.
This is yet another footnote.
This is yet another footnote.
This is yet another footnote.
This is yet another footnote.}

\subsection{Indented text}
In an example satisfies the seed of a clause, then it satisfies the clause
as well. In addition, seeds have the following property:

\begin{itemize}
\item[] 
If a seed of clause $c_T$, and example {\bf x} satisfies $c_T$ but
not $c$, then {\bf x} has at least one attibute in $c_T$ that
is not in $c$.\hfill({\tt*})
\end{itemize}
The procedure below...

\subsection{Bulleted List}
Here is an example of a bulleted list:
\begin{itemize}
\item
Some text here. Some text here. Some text here. Some text here. Some text here.
Some text here. Some text here. Some text here. Some text here.

\item
Some text here. Some text here. Some text here.
\end{itemize}

\newpage
\subsection{Numbered List}
Here is an example of a numbered list:
\begin{enumerate}
\item
Some text here. Some text here. Some text here. Some text here.

Some text here. Some text here. Some text here. Some text here. Some text here.

\item
Some text here. Some text here. Some text here.
\begin{enumerate}
\item
Some text here. Some text here. Some text here. Some text here. Some text here.
Some text here. Some text here. Some text here. Some text here.

\item
Some text here. Some text here. Some text here.
\begin{enumerate}
\item
Some text here. Some text here. Some text here. Some text here. Some text here.
Some text here. Some text here. Some text here. Some text here.

\item
Some text here. Some text here. Some text here.
\end{enumerate}
\end{enumerate}
\end{enumerate}


\subsection{To Illustrate an Algorithm}

This is the command to use when you want to illustrate an algorithm
with some pseudo code. A backslash followed with a space will
indent the line. Every line will be printed
as it is seen on the screen. Blank lines will be preserved.
Math and font changes may be used. 

The command
\verb+\bit+ will produce bold italics if you are using PostScript fonts, 
boldface in Computer Modern. \verb+\note{}+ will position the
note on the right margin. A backslash followed by a space
will provide a space a bit wider than the width of 2 `M's.

\begin{algorithm}
{\bit Evaluate-Single-FOE} ({\bf x$_f$, I$_0$, I$_1$}):
\ {\bf I}+ := {\bf I}$_1$;
\ ($\phi,\theta$) := (0,0);
\ {\it repeat}\note{/*usually only 1 interation required*/}
\ \ (s$_{opt}${\bf E}$_\eta$) := {\bit Optimal-Shift} ({\bf I$_0$,I$^+$,I$_0$,x$_f$});
\ \ ($\phi^+$, $\theta^+$) := {\bit Equivalent-Rotation} ({\bf s}$_{opt}$);
\ \ ($\phi$, $\theta$) := ($\phi$, $\theta$) + ($\phi^+$, $\theta^+$);
\ \ {\bf I}$^+$:= {\bit Derotate-Image} ({\bf I}$_1$, $\phi$, $\theta$);
\ \ {\it until} ($|\phi^+|\leq\phi_{max}$ \& $|\theta^+|\leq\theta_{max}$);
\ {\it return} ({\bf I}$^+$, $\phi$, $\theta$, E$_\eta$).
End pseudo-code.
\end{algorithm}


\subsection{Figures}
Here is an example of a figure with .5 inch space left for
the illustration:
\begin{figure}[h]
\vspace*{.5in}
\caption{This is a figure caption.
This is a figure caption.
This is a figure caption.}
\end{figure}

\section{Making Tables}
Use caption on top of the table. 
Use \verb+\hline+ at the top of the table, underneath the column headers
and at the end of the table.

You are discouraged from using vertical lines in tables, but
it you must include vertical lines, you must also use 
\verb+\savehline+ instead of \verb+\hline+ or there will be a
gap between the vertical and horizontal lines.
(\verb+\hline+ has been redefined to add some vertical space above and
below it.)

The following form will spread out to the width of the page:

\begin{table}[h]
\caption{This is an example table caption. As you can
see, it will be as wide as the table that it captions.}
\begin{tabular*}{\textwidth}{@{\extracolsep{\fill}}lcr}
\hline
$\alpha\beta\Gamma\Delta$ One&Two&Three\cr
\hline
one&two&three\cr
one&two&three\cr
\hline
\end{tabular*}
\end{table}



\begin{table}[h]
\caption{This is a table caption and will fit
the width of the table that it is captioning.}
\begin{tabular}{lcr}
\hline
$\alpha\beta\Gamma\Delta$ One&Two&Three\cr
\hline
one&two&three\cr
one&two&three\cr
\hline
\end{tabular}
\end{table}


\subsection{Theorems, Proofs, Examples, etc.}

\begin{example}
Consider an example in which $B_S$ is the structure...

The term $P(B_X)$ is our probability---prior to observing the data
in database $D$---that the data-generating process is a belief network with
structure $B_{S1}$.
\end{example}


\begin{proclaim}{Theorem 1}LEARN-MONOTONE-K-CNF makes at most
$(n+1)^K$ mistakes on any monotone K-CNF formula. (Recall that
n is the size of the largest example seen.
\end{proclaim}

\begin{proof}
Thus on each mistake, we decrease the cost by at least 1, and since the 
cost is never negative, the algorithm makes less than $(n+1)^K$
mistakes total.

The running time of this algorithm is clearly polynomial in 
{\bf size}$(f_T)$ and the length of the longest example seen.
\end{proof}


\begin{proof}
Thus on each mistake, we decrease the cost by at least 1, and since the 
cost is never negative, the algorithm makes less than $(n+1)^K$
mistakes total.

The running time of this algorithm is clearly polynomial in 
{\bf size}$(f_T)$ and the length of the longest example seen.

\[
\alpha\beta\Gamma\Delta\inmathqed
\]
\end{proof}

\begin{proof}[Proof of Theorem A.1]
This is a proof with a particular term. Call for the
particular term after `proof', i.e., 
\verb+\begin{proof}[Proof of Theorem A.1]+.
\end{proof}


In this section, we present an efficient formula for computing $P(B_X, D)$.
We do so by first introducing four assumptions.

\begin{demo}{Assumption 1}
The database variables, which we denote as $Z$, are discrete.
\end{demo}

As this assumption states...



\acknowledgements
We would like to thank....

Trying `cite', \cite{jacobs}, \cite{francis}.

\appendix
This is an appendix.
\begin{equation}
\sum_k P(k) \sum_i \sum_y f_i(y|k)^2
\end{equation}


\begin{references}
\bibitem{jacobs}Jacobs, E., ``Design Method Optimizes Scanning
 Phased Array,'' Microwaves, April 1982, pp.\ 69--70.

\bibitem{francis} Francis, M., ``Out-of-band response of array 
 antennas,'' Antenna Meas.  Tech. Proc., September 28--October 2,
1987, Seattle, p.~14.
\end{references}

For alphabetical references:

Maude Francis, (Francis, 87) showed important new results
with array antennas.

\begin{alphareferences}
Francis, M., ``Out-of-band response of array 
antennas,'' Antenna Meas.  Tech. Proc., September 28--October 2,
1987, Seattle, p.~14.

Jacobs, E., ``Design Method Optimizes Scanning
Phased Array,'' Microwaves, April 1982, pp.\ 69--70.
\end{alphareferences}

\vskip12pt
You can also use Bibtex. See smjrnl.doc for documentation on 
using Bibtex.

\end{article}

\begin{volumetoc}
\tocnumberline{Number 1}

\tocnumberline{Numbers 2/3 (Special Issue on Computational Learning
Theory)}

\tocnumberline{Number 4}

\TOCarticle{Explorations of an Incremental, Bayesian Algorithm for 
Categorization}{John R. Anderson and Michael Matessa}{275}

\TOCarticle{A Bayesian Method for the Induction of Probabilistic Networks
from Data}{Gregory F. Cooper and Edward Herskovits}{309}

\TOCarticle{Learning Boolean Functions in an Infinite Attribute Space}
{Avrim Blum}{373}

\TOCarticle{Technical Note: First Nearest Neighbor Classification on Frey 
and Slate's Letter Recognition Problem}{Terence C. Fogarty}{387}
\end{volumetoc}

\end{document}