%% Kluwer Small Journal Article Sample File
%% June 20, 1994
%% Use one of these two commands:
%\documentstyle{smjrnl} % For Computer Modern Fonts, or
\documentstyle[smjfonts]{smjrnl} % for PostScript fonts
\begin{document}
\begin{article}
%%%%% To be entered at Kluwers: =====>>
\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 smjrnl.doc 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}