%% Kluwer Small Journal Article Sample File 
%% November 29, 1995
     
%%   Use one of these two commands: 
\documentstyle{kbsjrnl} % For Computer Modern Fonts, or
% \documentstyle[kbsfonts]{kbsjrnl} % for PostScript fonts
     
\begin{document}
\begin{article}
     
%%%%% To be entered at Kluwers: =====>>
     
%% Enter each date on its own line, and write in correct dates:
   \begin{kluwerdates}
     Received Date
     Accepted Date
     Final Manuscript Date
   \end{kluwerdates}
     
     
\journame{Small Journal Name}
\volnumber{9}
\issuenumber{4}
\issuemonth{October}
\volyear{1992}
     
%% Do not delete either of the following two commands. 
%% Please supply facing curly brackets for the part you 
%% are not using for this article.
%\received{May 1, 1991}\revised{}
     
\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 
category. 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 the world) 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.
\newpage
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}
     
This is an example of a split equation, 
moving the top half to the left
and the bottom to the right.
\begin{splitmath}
\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{splitmath}
     
\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}
     
     
\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}
     
\newpage
\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{Unusual Tables}
There are three cases in which authors have felt the need to 
make a table other than the plain `tabular' table in this style. 
These more unusual tables are: tables with vertical lines; 
tables that do not use `tabular'; and tables that have
a number of `tabular's nested. In this section we will show 
how to make these tables.
     
\subsubsection{Vertical Lines}
Notice in the previous examples that no vertical lines were used. 
If at all possible to make your meaning clear without vertical 
lines, please leave them out. However, if you really must use 
vertical lines, you must use \verb+\savehline+ instead of 
\verb+\hline+ and
you must add another letter to the preamble.
     
For instance, this is the effect we usually want; 
horizontal lines extending to
the edge of the text in the column:
     
     
\begin{table}[h]
\begin{tabular}{c}\hline
 A         \\ \hline
 B         \\ \hline
\end{tabular}
\end{table}
     
     
Since we usually do not want vertical
lines in tables and we do want the horizontal lines to extend 
exactly to the left and right of text, 
we must go to some extra efforts to get the vertical lines 
to extend to the top and bottom of the column and to not
have extra horizontal space to the right of the vertical line 
in the last column.
Remember to
use \verb+\savehline+ and to
to add another column entry to the table preamble 
and then not to use that column, as seen below:
     
\begin{table}[h]
\begin{tabular}{|c|c}\savehline
 A         \\ \savehline
 B         \\ \savehline
\end{tabular}
\end{table}
     
\newpage
     
\subsubsection{Table Made Without `tabular'}
Here is an example of a table made without `tabular.' Notice 
the caption must be written above the table.
     
\begin{specialtable}[h]
\caption{Training a Thermal Linear Machine.} 
\label{thermal-alg}
\hrule
\vskip3pt
\begin{enumerate}
  \item Initialize $\beta$ to $2$.
     
  \item If linear machine is correct for all instances or 
$emag/lmag < \alpha$ for the last $2*n$ instances, then return 
($n =$ the number of features).
     
  \item Otherwise, pass through the training instances once, and for each 
instance ${\bf Y}$ that would be misclassified by the linear machine and 
for which $k < \beta$, immediately
 \begin{enumerate}
   \item Compute correction $c = \frac{\beta^{2}}{\beta+k}$, and update
${\bf W}_{i}$ and  ${\bf W}_{j}$.
     
   \item If the magnitude of the linear machine decreased on this
  adjustment, but increased on the previous adjustment, then 
  anneal $\beta$ to $a \beta - b$. 
 \end{enumerate}
     
  \item Go to step 2.
\end{enumerate}
\vskip1pt
\hrule
\end{specialtable}
     
     
\subsubsection{Nesting `Tabular's}
The table macros are made to automatically format the 
caption so that it is the width of the table and the caption 
appears at the top of the table. This works fine as long
as you use the normal \verb+\begin{tabular}..+ 
to make your
table, and you don't nest another \verb+\begin{tabular}..+ with it. 
However, if you want to use some other way of formatting
your table, or if you want to nest one or more tabulars within
the table, you must start with \verb+\begin{specialtable}+, as you 
see in the example below.
Notice that the caption is given at the top of the table.
     
     
\begin{specialtable}[h]
\caption{Quantitative and qualitative descriptions} 
\begin{tabular}{ccc}& Quantitative & Qualitative \\ \hline & & \\(a) & 
    \begin{tabular}{rr} {\it Time} &
     {\it Level}\\ \hline 3 sec. & 0.01 m\\ 4 sec. & 0.23 m\\ 5 sec. & 
     0.31 m\\ \hline
    \end{tabular} & 
           \begin{tabular}{c}$ Level(between(t_1, t_2)) = $\\ \ \ \ \ $
              (between(zero,top), increasing)$\\
           \end{tabular}\\& & \\(b) & $ Amount = 2.5 * 
                    Level + 0.7 * Level ^2 $ & $ Amount =M^+(Level) $\\ 
                    & & \\  \hline
\end{tabular}
\label{tabqq}
\end{specialtable}
     
     
     
\section{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{} 
% Please supply facing curly brackets if there is only one appendix. 
% Supply a letter if you are using a number of appendices;
%% i.e., \appendix{A} ...\appendix{B}. 
     
\appendixtitle{Sample Appendix Title} % optional appendix title
     
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, 1987) 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 kbsjrnl.ins for documentation on 
using Bibtex.
     
     
     
%% Volume Table of Contents:
     
\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}
     
     
%%%%  Issue Table of Contents %%%%
     
% \international % <== This command makes `An International Journal' appear 
\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 %%%%
     
\end{article}
\end{document}
     
     
