\documentclass[twoside,11pt]{article}
\usepackage{jmlr2e}			%JMLR style

%\documentclass{llncs} %COLT submission
%\documentclass{acm_proc_article-sp} %KDD submission
%\usepackage{nips01e} %nips submission
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{makeidx}
\usepackage{multicol}
%\usepackage{subeqn}  %messes amsmath package
\usepackage{amsfonts}
\usepackage{amsmath}

%\setlength{\voffset}{-0.5in}

%\usepackage{crop}
%\crop
\makeindex

\usepackage{here}
\usepackage{psfrag}
\usepackage{colordvi}
\usepackage{color}

\newcommand{\bi} {\begin{itemize}}
\newcommand{\ei} {\end{itemize}}
\newcommand{\be} {\begin{enumerate}}
\newcommand{\ee} {\end{enumerate}}
%\newcommand{\mm} { \bf}		%uncomment to show additions in bold
\newcommand{\mm} {}		%uncomment to show additions in plain type
%\newcommand{\mmm} { \bf}		%uncomment to show additions in bold
\newcommand{\mmm} {}            %uncomment to show additions in plain type
%\newcommand{\mmmm} {\bf}		%uncomment to show additions in bold
\newcommand{\mmmm} {}		%uncomment to show additions in plain type
%\newcommand{\bq} {\begin{equation}} %Does NOT work 
%\newcommand{\eq} {\end{equation}}   %Does NOT work 
\newcommand{\lb} {\label}
\newcommand{\dpl} {\displaystyle}

\newtheorem{mytheorem}{Theorem}[section]
\newtheorem{myprop}[mytheorem]{Proposition}
\newtheorem{myproblem}[mytheorem]{Problem}
\newtheorem{myremark}[mytheorem]{Remark}
\newtheorem{mylemma}[mytheorem]{Lemma}
\newtheorem{mycorollary}[mytheorem]{Corollary}
\newtheorem{myalgorithm}[mytheorem]{Algorithm}
\newtheorem{mydefinition}[mytheorem]{Definition}
\newtheorem{myexample}[mytheorem]{Example}
\newtheorem{mykernel}[mytheorem]{Kernel}
\newtheorem{mycode}[mytheorem]{Code}

%To Boldface changes, comment next line and uncomment the following one
\newcommand{\modi}{}
%\newcommand{\modi}{\bf}
%boldface does not work with jmlr2e package

% Heading arguments are {volume}{year}{pages}{submitted}{published}{authors}

\jmlrheading{5}{2004}{1127--1141}{12/03; Revised 7/04}{9/04}{Olvi L. Mangasarian, Jude W. Shavlik and Edward W. Wild}
\ShortHeadings{Knowledge-Based Kernel Approximation}{Mangasarian, Shavlik 
and Wild}
\firstpageno{1127}
%\pagestyle{empty}
\begin{document}
%\pagestyle{headings}

\title{Knowledge-Based Kernel Approximation}

\author{\name Olvi L. Mangasarian  \email olvi@cs.wisc.edu\\
	\name Jude W. Shavlik  \email shavlik@cs.wisc.edu\\
	\name Edward W. Wild  \email wildt@cs.wisc.edu\\
	\addr Computer Sciences Department\\
         University of Wisconsin\\
         1210 West Dayton Street\\
         Madison, WI 53706, USA}

\editor{John Shawe-Taylor}

\maketitle

\begin{abstract}
Prior knowledge, in the form of linear inequalities that need to be
satisfied over multiple polyhedral sets, is incorporated into a
function approximation generated by a linear combination of linear or
nonlinear kernels.  In addition, the approximation needs to satisfy
conventional conditions such as having given exact or inexact function
values at certain points.  Determining such an approximation leads to
a linear programming formulation. By using nonlinear kernels and
mapping the prior polyhedral knowledge in the input space to one
defined by the kernels, the prior knowledge translates into nonlinear
inequalities in the original input space. Through a number of
computational examples, including a real world breast cancer prognosis
dataset, it is shown that prior knowledge can significantly improve
function approximation.
\end{abstract}

\begin{keywords} function approximation, regression, prior knowledge, 
support vector machines, linear programming
\end{keywords}

\section{Introduction}
\label{section:1}
Support vector machines (SVMs) play a major role in classification
problems \citep{vap:00,cm:98,olm:98}. More recently, prior knowledge has
been incorporated into SVM classifiers, both to improve the classification 
task and to handle problems where conventional data may be few or not 
available \citep{sssv:98,fms:01a,fms:03}. Although SVMs have also been 
extensively used for regression 
\citep{dbksv:97,ss:98,epp:00a,mm:99a},
prior knowledge on properties of the function to be approximated 
has not been incorporated into the SVM function approximation as has been done 
for an SVM classifier \citep{fms:01a,fms:03}. In this work, we introduce
prior knowledge in the form of linear inequalities to be satisfied
by the function on polyhedral regions of the
input space for linear kernels, and on similar regions of 
the feature space for nonlinear
kernels.  These inequalities,
unlike point-wise inequalities or general convex constraints
that have already been treated in approximation 
theory
\citep{olmlls:69,olmlls:71,mu:88,fd:01}, are inequalities that need 
to be satisfied over 
specific polyhedral sets. Such ``prior knowledge" does not seem to
have been treated in the extensive approximation theory literature.

We outline the contents of the paper now.  In Section \ref{section:2}
we define the prior knowledge formulation for a linear kernel
approximation in the input space of the problem which leads to a
linear programming formulation in that space.  In Section
\ref{section:3} we approximate the function by a linear combination of
nonlinear kernel functions and explicitly map the polyhedral prior
knowledge in the input space to one defined by the kernel functions.
This leads to a linear programming formulation in that space.  In
Section \ref{section:4} we demonstrate the utility of our results on a
number of synthetic approximation problems as well as a real world
breast cancer prognosis dataset where we show that prior knowledge can
improve the approximation.  Section \ref{section:5} concludes the
paper with a brief summary and some possible extensions and
applications of the present work.

We describe our notation now.
All vectors will be column vectors unless transposed to a row
vector by a prime $'$.  
The scalar (inner) product of two vectors $x$ and $y$ in the 
$n$-dimensional real space
$R^n$ will be denoted by $x' y$.
%For a vector $x \in R^n$, $x_+$ denotes the vector in $R^n$ with
%all of its negative components set to zero.
%For a vector $x \in R^n$, $x_*$ denotes
%the vector in $R^n$ with components $(x_*)_i = 1$ if $x_i > 0$ and 0
%otherwise (i.e. $x_*$ is the result of applying the step function
%component-wise to $x$).  The base of the natural logarithm will be denoted by
%$\varepsilon$, and for a vector $y \in R^m,\; \varepsilon^{-y}$ will
%denote a vector in $R^m$ with components
%$\varepsilon^{-y_i},\;i=1,\ldots,m$. 
%For $x \in R^n$ the $1$-norm and the $\infty$-norm are defined as follows:
%$\|x\|_1 = \displaystyle{\sum_{j=1}^n
%|x_j|},\;\|x\|_{\infty} = \max_{1\le j \le n} |x_j|.$
%$\frac{1}{p}+\frac{1}{q}=1$.
For $x \in R^n$, $\|x\|_1$ denotes the $1$-norm: $\dpl{\sum_{i=1}^n}|x_i|$.
The notation $A \in R^{m \times n}$ will
signify a real $m \times n$ matrix.  For such a matrix, $A'$ will
denote the transpose  of $A$, $A_i$ will denote the $i$-th row of $A$
and $A_{\cdot j}$ the $j$-th column of $A$.
A vector of ones in a real space of arbitrary dimension will be
denoted by $e$. Thus for $e\in R^m$ and $y\in R^m$ the notation
$e'y$ will denote the sum of the components of $y$.
A vector of zeros in a real space of arbitrary
dimension will be denoted by $0$.
%The identity matrix of arbitrary dimension will be denoted by $I$.
%A {\em separating plane},
%with respect to two given point sets
%${\mathcal A}$ and ${\mathcal B}$ in $R^n$, is a plane that attempts
%to separate $R^n$ into two halfspaces such that each open halfspace
%contains points mostly of ${\mathcal A}$ or ${\mathcal B}$.
%A {\em bounding plane} to the set ${\mathcal A}$ is a plane that
%places ${\mathcal A}$ in one of the two closed halfspaces that the
%plane generates. 
%The abbreviation ``s.t." stands for
%``such that".
For $ A \in R^{m \times n}$ and $B \in R^{n \times k},$ 
a {\em kernel} $K(A,B)$ maps
$R^{m \times n} \times R^{n \times k}$ into $R^{m \times k}$. In particular, if $x$ and $y$ are column
vectors in $R^n$ then, $K(x', y)$ is a real number, $K(x', A')$ is a row vector in $R^m$ and $K(A, A')$ is
an $m \times m$ matrix. We shall make no assumptions on our kernels other
than symmetry, that is $K(x', y)'=K(y',x)$, and in particular we shall
not assume or make use of Mercer's positive semidefiniteness condition
\citep{vap:00,ss:02}.
The base of the natural logarithm will be denoted by $\varepsilon$.
A frequently used kernel in nonlinear classification is 
the Gaussian kernel \citep{vap:00,cm:98,olm:98} whose $ij$th element,
$i=1\ldots,m,\;j=1\ldots,k$, is given by:
$(K(A,B))_{ij}=\varepsilon^{-\mu\|{A_i}'-B_{\cdot j}\|^2}$,
where $A\in R^{m\times n}$, $B\in R^{n\times k}$ and $\mu$ is a positive constant. Approximate equality is denoted by $\approx$, while the abbreviation
``s.t." stands for ``subject to". The symbol $\wedge$ denotes the logical
``and" while $\vee$ denotes the logical ``or''.

%\newpage
\section{Prior Knowledge for a Linear Kernel Approximation}
\label{section:2}
We begin with a linear kernel model and show how to introduce prior
knowledge into such an approximation. 
We consider an unknown function $f$ from $R^n$ to $R$
for which approximate or exact function values are given on
a dataset of $m$ points in 
$R^n$ denoted by the matrix $A\in R^{m\times n}$. Thus,
corresponding to each point $A_i$ we are given an exact or inexact value 
of $f$, denoted by a real number $y_i$,
$i=1,\ldots,m$. We wish to approximate $f$
by some linear or nonlinear function of the matrix $A$ with 
unknown linear parameters. We  first consider
the simple linear approximation
\begin{equation}\label{2.1}
f(x)\approx w'x+b,
\end{equation}
for some unknown weight vector $w\in R^n$ and constant 
$b\in R$ which is determined by
minimizing some error criterion that leads to
\begin{equation}\label{2.2}
Aw+be-y \approx 0.
\end{equation}
If we consider $w$ to be a linear
combination of the rows of A, i.e. $w=A'\alpha$, $\alpha\in R^m$,
which is similar to the dual representation in a linear support vector machine 
for the weight $w$ \citep{olm:98,ss:02}, we then have
\begin{equation}\label{2.3}
AA'\alpha+be-y \approx 0.
\end{equation}
This immediately suggests the much more general idea of replacing
the linear kernel
$AA'$ by some arbitrary nonlinear kernel $K(A,A'):R^{m\times n} \times
R^{n\times m}\longrightarrow R^{m\times m}$ that leads to
the following approximation, which is nonlinear in $A$ but linear
in $\alpha$:
\begin{equation}\label{2.4}
K(A,A')\alpha+be-y \approx 0.
\end{equation}
We will measure the error in (\ref{2.4}) componentwise
by a vector $s\in R^m$ defined
by
\begin{equation}\label{2.5}
-s\le K(A,A')\alpha+be-y\le s.
\end{equation}
We now drive this error down by minimizing the 1-norm
of the error $s$ together with
the 1-norm of $\alpha$ for complexity reduction or stabilization.
This leads to the following constrained optimization problem
with positive parameter $C$ that determines the relative weight
of exact data fitting to complexity reduction:
\begin{equation}\label{2.6}
\begin{array}{lrcccl}
&&&\dpl{\min_{(\alpha,b,s)}}\;\;\|\alpha\|_1+C
\|s\|_1\\
\mbox{s.t.}&-s&\le& K(A,A')\alpha+be-y&\le& s,\\
\end{array}
\end{equation}
which can be represented as the following linear program:
\begin{equation}\label{2.7}
\begin{array}{lrcccl}
&&&\dpl{\min_{(\alpha,b,s,a)}}\;\;e'a+C e's\\
\mbox{s.t.}&-s&\le& K(A,A')\alpha+be-y&\le& s,\\
           &            -a &\le&                \alpha &\le&a.
\end{array}
\end{equation}
We note that the $1$-norm formulation employed here leads to a linear
programming formulation without regard to whether the kernel $K(A,A')$
is positive semidefinite or not. This would not be the case if we used
a kernel-induced norm on $\alpha$ that would lead to a quadratic
program. This quadratic program would be more difficult to solve than
our linear program especially when it is nonconvex, which would be an
NP-hard problem, as is the case when the kernel employed is not
positive semidefinite.

We now introduce prior knowledge for a linear kernel as follows. 
Suppose that it is known that the function $f$ represented by (\ref{2.1})
satisfies the following condition.
For all points $x\in R^n$, not necessarily in the training set but
lying in the nonempty polyhedral set determined by the linear inequalities
\begin{equation}
\label{2.8}
Bx\le d,
\end{equation}
for some $B\in R^{k\times n}$, 
the function $f$, and hence its linear
approximation $w'x+b$,
must dominate a given linear function $h'x+\beta$,
for some user-provided $(h,\beta)\in R^{n+1}$. 
That is,
for a {\em fixed} $(w,b)$ we have the implication
\begin{equation} \label{2.9}
Bx\le d\;\Longrightarrow\; w'x+b\ge h'x+\beta,
\end{equation}
or equivalently in terms of $\alpha$, where $w=A'\alpha$:
\begin{equation} \label{2.9a}
Bx\le d\;\Longrightarrow\; \alpha'Ax+b\ge h'x+\beta.
\end{equation}
Thus, 
the implication (\ref{2.9a}) needs to be added to the constraints of the
linear program (\ref{2.7}). To do that we make use of the following
equivalence relationship that converts the implication (\ref{2.9a})
to a set of linear constraints that can be appended to the linear
program (\ref{2.7}). A similar technique was used in 
\cite[Proposition 2.1]{fms:01a} to incorporate prior knowledge
into linear classifiers.
\begin{myprop}
\label{prop:2.1}
{\bf Prior Knowledge Equivalence.} Let the set $\{x\; | \; Bx\le d\}$
be nonempty. Then for a fixed $(\alpha,b,h,\beta)$,
the implication (\ref{2.9a}) is equivalent to the following system
of linear inequalities having a solution $u\in R^k$: 
\begin{equation} 
\label{2.10}
B'u+A'\alpha-h=0,\;-d'u+b-\beta\ge0,u\ge 0.
\end{equation}
\end{myprop}
{\bf Proof} The implication (\ref{2.9a})
is equivalent to the following
system having no solution $(x,\zeta)\in R^{n+1}$:
\begin{equation}
\label{2.11}
Bx-d\zeta\le0,\;(\alpha'A-h')x+(b-\beta)\zeta<0,\;-\zeta<0.
\end{equation}
By the Motzkin theorem of the alternative \cite[Theorem 2.4.2]{man:69a} we have 
that (\ref{2.11}) is equivalent to the following system of inequalities having
a solution $(u,\eta,\tau)$:
\begin{equation}
\label{2.12}
B'u+(A'\alpha-h)\eta=0,\;-d'u+(b-\beta)\eta-\tau=0,\;u\ge0,\;0\neq(\eta,\tau)\ge 0.
\end{equation}
If $\eta=0$ in (\ref{2.12}), then we contradict the nonemptiness
of the knowledge set $\{x\;|\;Bx\le d\}$. Because, for
$x\in\{x\;|\;Bx\le d\}$ and $(u,\tau)$ that solve (\ref{2.12}) 
with $\eta=0$, we obtain the
contradiction
\begin{equation}
\label{2.13}
0\ge u'(Bx-d)=x'B'u-d'u=-d'u=\tau>0.  \end{equation}
Hence $\eta>0$ in (\ref{2.12}). Dividing (\ref{2.12}) by $\eta$
and redefining $(u,\alpha,\tau)$ as 
$(\frac{u}{\eta},\frac{\alpha}{\eta},\frac{\tau}{\eta})$
we obtain (\ref{2.10}).
$\Box$

Adding the constraints (\ref{2.10}) to the linear programming formulation
(\ref{2.7}) with a linear kernel $K(A,A')=AA'$, we obtain our desired linear
program that incorporates the prior knowledge implication (\ref{2.9a}) into
our approximation problem: 
\begin{equation}\label{2.14}
\begin{array}{lrcccl}
&&&\dpl{\min_{(\alpha,b,s,a,u\ge0)}}\;\;e'a+C e's\\
\mbox{s.t.}&-s&\le& AA'\alpha+be-y&\le& s,\\
           &            -a &\le&                \alpha &\le&a,\\
           &               &   &A'\alpha+B'u           &  = & h,\\
	   &               &   &         -d'u           &\ge & \beta-b.
\end{array}
\end{equation}

Note that in this linear programming formulation with a linear kernel 
approximation, both the approximation
$w'x+b=\alpha'Ax+b$ to the unknown function $f$ as well as the prior 
knowledge are linear in the input data $A$ of the problem.
This is somewhat restrictive, and therefore 
we turn now to our principal concern in this work, which is the incorporation
of prior knowledge into a {\em nonlinear} kernel approximation.

\section{Knowledge-Based Nonlinear Kernel
Approximation}\label{section:3}

In this part of the paper we will incorporate prior knowledge by
using a nonlinear kernel in {\em both} the linear programming formulation
(\ref{2.7}) as well as in the prior knowledge implication
(\ref{2.9a}). We begin with the latter, the linear prior knowledge
implication (\ref{2.9a}). If we again consider $x$ as a linear
combination of the rows of $A$, that is
\begin{equation}
\label{3.1}
x=A't,
\end{equation}
then the implication (\ref{2.9a}) becomes
\begin{equation} \label{3.2} 
BA't\le d\;\Longrightarrow\; \alpha'AA't+b\ge h'A't+\beta,
\end{equation}
for a given fixed $(\alpha,b)$. The assumption (\ref{3.1}) is not
restrictive for the many problems where a sufficiently large number of
training data points are available so that any vector in input space
can be represented as a linear combination of the training data
points.

If we now "kernelize" the various 
matrix products in the above implication, we have the implication
\begin{equation} \label{3.3}
K(B,A')t\le d\;\Longrightarrow\; \alpha'K(A,A')t+b\ge h'A't+\beta.
\end{equation}
We note that the two kernels appearing in (\ref{3.3}) need not be the
same and neither needs to satisfy Mercer's positive semidefiniteness
condition. In particular, the first kernel of (\ref{3.3}) could be a
linear kernel which renders the left side of the implication of
(\ref{3.3}) the same as that of (\ref{3.2}).  We note that for a
nonlinear kernel, implication (\ref{3.3}) is nonlinear in the input
space data, but is linear in the implication variable $t$.  We have thus
mapped the polyhedral implication (\ref{2.9}) into a nonlinear one
(\ref{3.3}) in the input space data.  Assuming for simplicity that the
kernel $K$ is symmetric, that is $K(B,A')'=K(A,B')$, it follows
directly by Proposition \ref{prop:2.1} that the following equivalence
relation holds for implication (\ref{3.3}).
\begin{myprop}
\label{prop:3.1}
{\bf Nonlinear Kernel Prior Knowledge Equivalence.} Let the set\\ 
$\{t\; | \; K(B,A')t\le d\}$
be nonempty. Then for a given $(\alpha,b,h,\beta)$,
the implication (\ref{3.3}) is equivalent to the following system
of linear inequalities having a solution $u\in R^k$:
\begin{equation}
\label{3.4}
K(A,B')u+K(A,A')\alpha-Ah=0,\;-d'u+b-\beta\ge 0,u \ge 0.
\end{equation}
\end{myprop}
We now append the constraints (\ref{3.4}), which are
equivalent to the nonlinear kernel
implication (\ref{3.3}), to the linear programming formulation
(\ref{2.7}). This gives the following linear program
for approximating a given function with 
prior knowledge using a nonlinear kernel:
\begin{equation}\label{3.5}
\begin{array}{lrcccl}
&&&\dpl{\min_{(\alpha,b,s,a,u\ge0)}}\;\;e'a+C e's\\
\mbox{s.t.}&-s&\le& K(A,A')\alpha+be-y&\le& s,\\ 
           &            -a &\le&                \alpha &\le&a,\\
           &               &   &K(A,B')u+K(A,A')\alpha &  = & Ah,\\
           &               &   &         -d'u           &\ge & \beta-b.
\end{array}
\end{equation}
Since we are not certain that the prior knowledge implication
(\ref{3.3}) is satisfiable, and since we wish to balance the influence
of prior knowledge with that of fitting conventional data points,
we need to introduce error variables $z$ and $\zeta$
associated with the last two constraints of the linear
program (\ref{3.5}). These error variables are then driven down by a modified 
objective function as follows:
\begin{equation}\label{3.6}
\begin{array}{lrcccl}
&&&\dpl{\min_{(\alpha,b,s,a,z,(u,\zeta)\ge0)}}\;\;e'a+C e's+\mu_1e'z+\mu_2\zeta\\
\mbox{s.t.}&-s&\le& K(A,A')\alpha+be-y&\le& s,\\
           &            -a &\le&                \alpha &\le&a,\\
           &            -z &\le&K(A,B')u+K(A,A')\alpha-Ah &  \le & z,\\
           &               &   &         -d'u +\zeta          &\ge & \beta-b,
\end{array}
\end{equation}
where $(\mu_1,\mu_2)$ are some positive parameters.
This is our final linear program for a single prior knowledge implication.
If we have more than one such implication, then the last two sets
of constraints are repeated for each implication. For the
sake of simplicity we omit these details. The values of the parameters
$C$, $\mu_1$, and $\mu_2$ are chosen so as to balance fitting conventional
numerical data versus the given prior knowledge. One way to choose these
parameters is to set aside a ``tuning set" of data points
and then choose the parameters so as to give a best fit of
the tuning set. We also note that all three kernels appearing in
(\ref{3.6}) could possibly be distinct kernels from each other and none 
needs to be positive semidefinite. In fact, the kernel $K(A,B')$ 
could be the linear kernel $AB'$ which was was actually tried in some
of our numerical experiments without a noticeable change from
using a Gaussian kernel.

%\begin{myremark}\label{rem:1}{\bf Data-Based and Knowledge-Based Approximation}
%If we set $\mu_1=\mu_2=0$, then the linear program (\ref{3.6})
%degenerates to (\ref{2.7}), the linear program
%associated with an ordinary data-based nonlinear kernel SVM. 
%We can also make the linear program (\ref{3.6}), which
%generates a nonlinear approximation, {\bf only knowledge-based} 
%and not dependent on any specific numerical data {\bf if} we replace
%the matrix $A$ appearing everywhere in (\ref{3.6}) by a random sample of points
%that satisfy the implication of the prior knowledge (\ref{3.3}).
%This might
%be a useful paradigm for situations where conventional numerical datasets
%are not easily available, but prior knowledge such as expert knowledge
%is more readily available. In fact, using this idea of making $A$ and $y$
%random samples satisfying the implication of prior knowledge (\ref{3.3}), 
%the linear programming
%formulation (\ref{3.6}) {\bf as is} can be made  {\bf totally} dependent on prior 
%knowledge only.
%\end{myremark}

We now turn to our numerical experiments.

\section{Numerical Experiments} \label{section:4}
The focus of this paper is mainly theoretical. However, in order to
illustrate the power of the proposed formulation, we tested our
algorithm on three synthetic examples and one real world example with
and without prior knowledge.  Two of the synthetic examples are based
on the ``sinc" function which has been extensively used for kernel
approximation testing \citep{vgs:97,ba:01}, while the third synthetic
example is a two-dimensional hyperboloid. All our results indicate
significant improvement due to prior knowledge.  The parameters for
the synthetic examples were selected using a combination of exhaustive
search and a simple variation on the Nelder-Mead simplex algorithm
\citep{nm:65} that uses only reflection, with average error as the
criterion.  The chosen parameter values are given in the captions of
relevant figures.

\subsection{One-Dimensional Sinc Function}
\label{ex:1}
We consider the one-dimensional sinc function
\begin{equation} \label{4.1}
f(x)=sinc(x)=\frac{sin \pi x}{\pi x}.
\end{equation}
Given data for the sinc function includes approximate
function values for 52 points on the intervals $-3 \leq x \leq -1.4303$ and
$1.4303 \leq x \leq 3$.  The endpoints $\pm 1.4303$ are
approximate local minima of the sinc function. The given approximate
function values for $sinc(x)$ are
normally perturbed around the true values, 
with mean 0 and standard deviation 0.5.  
In addition, there are
also three given values at $x = 0$.  One of these values is 1, which
is the 


%$\alpha_i\neq 0$ in the solution
%of the nonlinear Gaussian kernel approximation (\ref{4.2})  of (\ref{3.6})
%for $f(x)$.
%{\mmm The approximation in Figure \ref{fig:2} has an average error of
%$0.0901$ computed over a grid of 100 equally spaced
%points on $[-3, 3]$.} {\mm The prior knowledge used to approximate the 
\pagebreak
%\thispagestyle{empty}
\begin{figure}[H]
\begin{center}
\includegraphics[width=3.5in,height=2.3in,angle=0]{sinc-059-mod-no-knowledge.eps}   
\end{center}\vspace{-.1in}
\caption{ \label{fig:1}{
The one-dimensional sinc function $sinc(x)=\frac{sin \pi x}{\pi x}$
(dashed curve) and its Gaussian kernel approximation {\em without} prior knowledge based on the 55 points shown by diamonds. The nine solid
diamonds depict the ``support" points used by the nonlinear Gaussian kernel
in generating the approximation of $sinc(x)$. That is, they are the
rows $A_i$ of $A$ for which $\alpha_i\neq 0$ in the solution
of the nonlinear Gaussian kernel approximation  of (\ref{2.7}) for $f(x)$:
$f(x)\approx K(x',A')\alpha+b$.  
\noindent{\mmm The approximation has an average error of $0.3113$ over a grid of
100 points in the interval $[-3,3]$. Parameter values used: $\mu=7,C=5$.}
}}
%\end{figure}
%\begin{figure}[H]
\begin{center}
\includegraphics[width=3.5in,height=2.3in,angle=0]{sinc-059-mod-with-knowledge.eps}   
\end{center}\vspace{-.1in}
\caption{ \label{fig:2}{
The one-dimensional sinc
function $sinc(x)=\frac{sin \pi x}{\pi x}$ (dashed curve) and 
its Gaussian kernel approximation {\em with} prior knowledge based
on 55 points, shown by diamonds, which are the same as those of
Figure \ref{fig:1}. The seven solid diamonds depict the ``support"
points used by the nonlinear Gaussian kernel in generating the
approximation of $sinc(x)$.  The prior knowledge consists of the implication
$-\frac{1}{4} \leq x \leq \frac{1}{4}
\Rightarrow f(x) \geq \frac{\sin(\pi / 4)}{\pi / 4}$, 
which is implemented by replacing $f(x)$ by
its nonlinear kernel approximation (\ref{4.2}).
{\mmm The approximation has an average error of $0.0901$ over a grid of
100 points in the interval $[-3,3]$,
which is less than $\frac{1}{3.4}$ times the error of Figure \ref{fig:1}.
Parameter values used: $\mu=1, C=13,\mu_1=5,\mu_2=450$.}
}}
\end{figure}
%\vspace{-9mm}
\pagebreak
%\thispagestyle{empty}
\begin{figure}[H]
\begin{center}
\includegraphics[width=2.9in,height=1.8in,angle=0]{product-sinc-exact.eps}
\end{center}
\vspace{-3mm}
\caption{\label{fig:3}{
The exact product sinc function 
$f(x_1, x_2)=\frac{sin \pi x_1}{\pi x_1}\frac{sin \pi x_2}{\pi x_2}$.
}}
%\end{figure}
%\begin{figure}[H]
\begin{center}
\includegraphics[width=2.9in,height=1.8in,angle=0]{product-sinc-no-knowledge.eps}
\end{center}
\vspace{-3mm}
\caption{\label{fig:4}{
Gaussian kernel approximation of the product sinc function 
$f(x_1, x_2)=\frac{sin \pi x_1}{\pi x_1}\frac{sin \pi x_2}{\pi x_2}$ 
based on 211 exact function values plus 2 incorrect function values, but 
{\em without} prior knowledge.
{\mmm The approximation has an average error of $0.0501$ 
over a grid of 2500 points in the set $\{[-3,3]\times[-3,3]\}$.
Parameter values used: $\mu=0.2, C=10^6$.
}
}}
%\end{figure}
%\begin{figure}[H]
\begin{center}
\includegraphics[width=2.9in,height=1.8in,angle=0]{product-sinc-with-knowledge.eps}
\end{center}
\vspace{-3mm}
\caption{\label{fig:5}{ Gaussian kernel approximation of the product
sinc function based on the same 213 function values as Figure
\ref{fig:4} {\em plus} prior knowledge consisting of $(x_1, x_2) \in
\{[-0.1, 0.1] \times [-0.1, 0.1]\}\} \Rightarrow f(x_1, x_2) \geq
(\frac{sin(\pi / 10)}{\pi / 10})^2$.  {\mmm The approximation has an
average error of $0.0045$ over a grid of 2500 points in the set
$\{[-3,3]\times[-3,3]\}$, which is less than $\frac{1}{11.1}$ times
the error of Figure \ref{fig:4}.  Parameters are $\mu=1,
C=16000,\mu_1=15000,\mu_2=5\cdot 10^6$.}  }}
\end{figure}
\noindent actual limit of the sinc function at 0.  The other values at
$x = 0$ are 0 and $-1$ which are intended to be misleading to the
approximation.

Figure \ref{fig:1} depicts $sinc(x)$ by a dashed curve and its approximation
{\em without} prior knowledge by
a solid curve based on the 55 points shown by diamonds. The nine solid diamonds depict ``support" points, that is rows $A_i$ of $A$ for which $\alpha_i\neq 0$ in the solution
of the nonlinear Gaussian kernel approximation  of (\ref{2.7}) for $f(x)$:
\begin{equation} \label{4.2}
f(x)\approx K(x',A')\alpha+b.
\end{equation}

\noindent The approximation in Figure \ref{fig:1} has an average error of
$0.3113$.  This error is computed by averaging over a grid of 100 equally spaced
points in the interval $[-3, 3]$.

Figure \ref{fig:2} depicts $sinc(x)$ by a dashed curve and its much better
approximation
{\em with} prior knowledge by
a solid curve based on the 55 points shown, which are the same as those of Figure 
\ref{fig:1}. The seven
solid diamond  points are ``support"
points, that is rows $A_i$ of $A$ for which 
$\alpha_i\neq 0$ in the solution
of the nonlinear Gaussian kernel approximation (\ref{4.2})  of (\ref{3.6})
for $f(x)$.
{\mmm The approximation in Figure \ref{fig:2} has an average error of
$0.0901$ computed over a grid of 100 equally spaced
points on $[-3, 3]$.} {\mm The prior knowledge used to approximate the 
one-dimensional sinc
function is $-\frac{1}{4} \leq x \leq \frac{1}{4} \Rightarrow f(x)
\geq \frac{sin(\pi / 4)}{\pi / 4}$. The value $\frac{sin(\pi /
4)}{\pi / 4}$ is the minimum of $sinc(x)$ on the knowledge interval
$[-\frac{1}{4},\frac{1}{4}]$.  This prior knowledge is implemented by replacing $f(x)$
by its nonlinear kernel approximation (\ref{4.2}) and then using the
implication (\ref{3.3})} as follows:
\begin{equation}
K(I,A')t\le\frac{1}{4}\;\wedge\;K(-I,A')t\le\frac{1}{4}\Longrightarrow
\alpha'K(A,A')t+b\ge  \frac{sin(\pi / 4)}{\pi / 4}.
\end{equation}

\subsection{Two-Dimensional Sinc Function}
\label{ex:2}
Our second example is the two-dimensional $sinc(x)$ function for $x\in R^2$:
\begin{equation} \label{4.3}
f(x_1, x_2)=sinc(x_1)sinc(x_2)=\frac{sin \pi x_1}{\pi x_1}\frac{sin \pi x_2}{\pi x_2}.
\end{equation}
The given data for the two-dimensional sinc function includes 210
points in the region $\{(x_1, x_2) | (-3 \leq x_1 \leq -1.4303 \vee
1.4303 \leq x_1 \leq 3) \wedge (-3 \leq x_2 \leq -1 \vee 1 \leq x_2
\leq 3)\}$.  This region excludes the largest bump in the function
centered at $(x_1, x_2) = (0, 0)$.  The given values are exact
function values.  There are also three values given at $(x_1,
x_2) = (0, 0)$, similar to the previous example with the one
dimensional sinc.  The first value is the actual limit of the function
at $(0, 0)$, which is 1.  The other two values are 0 and $-1$.  These last two
values are intended to mislead the approximation.

Figure \ref{fig:3} depicts the two-dimensional sinc function of
(\ref{4.3}).
Figure \ref{fig:4} depicts  an approximation of $sinc(x_1)sinc(x_2)$ 
{\em without} prior knowledge by
a surface based on the 213 points described above. 
{\mmm The approximation in Figure \ref{fig:4} has an average error of
$0.0501$.  This value is computed by averaging over a grid of 2500 equally spaced
points in $\{[-3, 3] \times [-3, 3]\}$.}

Figure \ref{fig:5} depicts  a much better approximation of $sinc(x_1)sinc(x_2)$
{\em with} prior knowledge by
a surface based on the same 213 points.
{\mmm The approximation in Figure \ref{fig:5} has an average error of
$0.0045$.  This value is computed by averaging over 2500 equally spaced
points in 
\pagebreak

\begin{figure}[H]
\begin{center}
\includegraphics[width=2.9in,height=1.8in,angle=0]{xy_exact.eps}
\end{center}\vspace{-.1in}
\caption{\label{fig:6}{
The exact hyperboloid function $f(x_1, x_2)=x_1x_2$.
}}
%\end{figure}
%\begin{figure}[H]
\begin{center}
\includegraphics[width=2.9in,height=1.8in,angle=0]{xy_no_knowledge.eps}
\end{center}\vspace{-.1in}
\caption{\label{fig:7}{Gaussian kernel approximation
of the hyperboloid function $f(x_1, x_2)=x_1x_2$ based on 11 exact
function values along the line $x_2 = x_1, x_1 \in \{-5, -4, \ldots,
4, 5\}$, but {\em without} prior knowledge.  {\mmm The approximation
has an average error of $4.8351$ over 2500 points in the set
$\{[-5,5]\times[-5,5]\}$.  Parameter values used: $\mu=0.361,
C=145110$.} }}
%\end{figure}
%\begin{figure}[H]
\begin{center}
\includegraphics[width=2.9in,height=1.8in,angle=0]{xy_with_knowledge_01.eps}
\end{center}\vspace{-.1in}
\caption{\label{fig:8}{Gaussian kernel approximation of the hyperboloid function $f(x_1, x_2)=x_1x_2$ based
on the same 11 function values as of Figure \ref{fig:7} {\em plus} 
prior knowledge 
consisting of the implications (\ref{4.5}) and (\ref{4.6}).
{\mmm The approximation has an average error of $0.2023$ 
over 2500 points in the set $\{[-5,5]\times[-5,5]\}$,
which is less than $\frac{1}{23.9}$ times the error of Figure \ref{fig:7}.}
Parameter values used: $\mu=0.0052, C=5356,\mu_1=685,\mu_2=670613$.}}
\end{figure}
%\thispagestyle{empty}
\noindent $\{[-3, 3] \times [-3, 3]\}$.} 
The prior knowledge consists of the implication $$(x_1, x_2) \in
\{[-0.1, 0.1] \times [-0.1, 0.1]\} \Rightarrow f(x_1, x_2) \geq
(\frac{sin(\pi / 10)}{\pi / 10})^2.$$  The value $(\frac{sin(\pi /
10)}{\pi / 10})^2$ is equal to the minimum value of
$sinc(x_1)sinc(x_2)$ on the knowledge set $\{[-0.1, 0.1] \times [-0.1, 0.1]\}$.  
This prior knowledge is implemented by replacing $f(x_1, x_2)$ by its nonlinear
kernel approximation (\ref{4.2}) and then using the implication
(\ref{3.3}).  

\subsection{Two-Dimensional Hyperboloid  Function}
\label{ex:3}
Our third example is the two-dimensional hyperboloid function
\begin{equation} \label{4.4}
f(x_1, x_2)=x_1x_2.
\end{equation}

For the two-dimensional hyperboloid function, the given data consists
of 11 points along the line $x_2 = x_1, x_1 \in \{-5, -4, \ldots, 4,
5\}$.  The given values at these points are the actual function values.

Figure \ref{fig:6} depicts the two-dimensional hyperboloid function of
(\ref{4.4}).
Figure \ref{fig:7} depicts  an approximation of the hyperboloid function, 
{\em without} prior knowledge, by
a surface based on the 11 points described above.
{\mmm The approximation in Figure \ref{fig:7} has an average error of
$4.8351$ computed over a grid of 2500 equally spaced
points in $\{[-5, 5] \times [-5, 5]\}$.}

Figure \ref{fig:8} depicts  a much better approximation of 
the hyperboloid function by a nonlinear surface  
based on the same 11 points above {\em plus} prior knowledge.
{\mmm The approximation in Figure \ref{fig:8} has an average error of
$0.2023$ computed over a grid of 2500 equally spaced
points in $\{[-5, 5] \times [-5, 5]\}$.}
The prior knowledge consists of {\mm the following two implications: 

\begin{equation} \label{4.5}
(x_1, x_2) \in \{(x_1, x_2) | {-\frac{1}{3}x_1} \leq x_2 \leq -\frac{2}{3}x_1\} 
\Rightarrow f(x_1, x_2) \leq 10x_1
\end{equation}
and
\begin{equation} \label{4.6}
(x_1, x_2) \in \{(x_1, x_2) | {-\frac{2}{3}x_1} \leq x_2 \leq -\frac{1}{3}x_1\} 
\Rightarrow f(x_1, x_2) \leq 10x_2.
\end{equation}
These implications are implemented by replacing $f(x_1, x_2)$ by
its nonlinear kernel approximation (\ref{4.2}) and then using the
implication (\ref{3.3}).  The regions on which the knowledge is given are
cones on which $x_1x_2$ is negative.  Since the two
implications are analogous, we explain (\ref{4.5}) only.  This
implication is justified on the basis that $x_1x_2 \leq 10x_1$ 
over the knowledge cone $\{(x_1, x_2) | {-\frac{1}{3}x_1} \leq x_2 \leq -\frac{2}{3}x_1\}$ for sufficiently large $x_2$, that is $x_2 \ge 10$.
This is intended to capture coarsely
the global shape of $f(x_1, x_2)$ and succeeds in generating a more
accurate overall approximation of the function.}

\subsection{Predicting Lymph Node Metastasis}

We conclude our numerical results with a potentially useful
application of knowledge-based approximation to breast cancer
prognosis \citep{msw:94,wshm:95a,lmw:01}. An important prognostic
indicator for breast cancer recurrence is the number of metastasized
lymph nodes under a patient's armpit, which could be as many as 30. To
determine this number, a patient must undergo optional surgery in
addition to the removal of the breast tumor. {\mmmm If the predicted
number of metastasized lymph nodes is sufficiently small, then
the oncological surgeon may decide not to perform the  additional
surgery.}
Thus, it is
useful to approximate the number of metastasized lymph nodes as a
function of thirty available cytological features and one histological
feature. The cytological features are obtained from a fine needle
aspirate during the diagnostic procedure while the histological
feature is obtained during surgery.  Our proposed knowledge-based
approximation can be used to improve the determination of such a
function, $f:R^{31}\longrightarrow R$, that predicts the number of
metastasized lymph nodes. For example, in certain polyhedral regions of
$R^{31}$, past training data indicate the existence of a substantial
number of metastasized lymph nodes, whereas certain other regions
indicate the unlikely presence of any metastasis. This knowledge can
be applied to obtain a hopefully more accurate lymph node function $f$
than that based on numerical function approximation alone.

We have performed preliminary experiments with the Wisconsin
Prognostic Breast Cancer (WPBC) data available from \citep{irvine}.
In our experiments we reduced $R^{31}$ to $R^4$ and predicted the
number of metastasized lymph nodes based on three cytological
features: mean cell texture, worst cell smoothness, and worst cell
area, as well as the histological feature tumor size.  The tumor size
is an obvious histological feature to include, while the three other
cytological features were the same as those selected for breast cancer
diagnosis in \citep{olm:01d}.  Thus, we are approximating a function
$f:R^4 \longrightarrow R$.  Note that the online version of the WPBC
data contains four entries with no lymph node information which were
removed for our experiments.  {\mmmm After removing these entries, we
were left with $194$ examples in our dataset.  

To simulate the
procedure of an expert obtaining prior knowledge from past data we
used the following procedure.  First we took a random $20\%$ of the
dataset to analyze as ``past data''.  Inspecting this past data, we
choose the following background knowledge:
\begin{equation} \label{4.7}
x_1 \ge 22.4 \; \wedge \; x_2 \ge 0.1 \; \wedge \; x_3 \ge 1458.9 \; \wedge \; x_4 \ge 3.1 
  \; \Longrightarrow \;
  f(x_1, x_2, x_3, x_4) \ge 1,
\end{equation}
where $x_1, x_2, x_3,$ and $x_4$ denote mean texture, worst
smoothness, worst area, and tumor size respectively.  This prior
knowledge is based on a typical oncological surgeon's advice that
larger values of the variables are likely to result in more
metastasized lymph nodes.  The constants in (\ref{4.7}) were chosen by
taking the average values of $x_1, \ldots, x_4$ for the entries in the
past data with at least one metastasized lymph node.  

We used ten-fold
cross validation to compare the average absolute error between an
approximation without prior knowledge and an approximation with the
prior knowledge of Equation (\ref{4.7}) on the $80\%$ of the
data that was not used as ``past data'' to generate the constants in (\ref{4.7}).}
%We used ten-fold cross validation to
%compare the average absolute error between an approximation without
%prior knowledge and an approximation using the following prior
%knowledge:
%\begin{equation} \label{4.7}
%x_1 \ge 20 \; \wedge \; x_2 \ge 0.13 \; \wedge \; x_3 \ge 2000 \; \wedge \; x_4 \ge 2 
%  \; \Longrightarrow \;
%  f(x_1, x_2, x_3, x_4) \ge 2.8333
%\end{equation}
%where $x_1, x_2, x_3, x_4$ denote mean texture, worst smoothness,
%worst area, and tumor size respectively.  This prior knowledge
%simulates a doctor's decision that larger values of the variables are
%likely to result in more metastasized lymph nodes.  {\mmmm The constants
%in (\ref{4.7}) were selected to reflect this by inspecting the dataset
%and choosing reasonably high values of the variables.}  
Parameters in (\ref{3.6}) using a Gaussian kernel were chosen using
the Nelder-Mead algorithm on a tuning set taken from the training data
for each fold.  
{\mmmm The average absolute error of the function
approximation with no prior knowledge was $3.75$ while the average
absolute error with prior knowledge was $3.35$, a $10.5\%$
reduction.  The mean function value of the data used in the
ten-fold cross validation experiments is $3.30$, so neither approximation is accurate.}
However, these results indicate that adding prior knowledge does
indeed improve the function approximation substantially.  Hopefully
more sophisticated prior knowledge, based on a more detailed analysis
of the data and consultation with domain experts, will further reduce
the error.

%%%%% Rewrite of Shavlik & Maclin's paragraph:
We close this section with a potential application to a reinforcement
learning task \citep{sutton.book1998}, where the goal is to predict the
value of taking an action at a given state.  Thus, the domain of the
function to be approximated is the Cartesian product of the set of
states and the set of actions.  In particular, we plan to use the {\it
Keep-Away} subtask of the soccer game developed in
\citep{stone.icml2001}.  The state description includes measurements
such as distance to each of the opposing players, distance to the
soccer ball, distances to the edges of the field, etc.  Actions
include holding the ball and attempting a pass to a teammate.  It has
been demonstrated that providing prior knowledge can improve the
choice of actions significantly
\citep{kuhlman.aaaiworkshop2004,maclin.mlj96}.  One example of advice
(that is, prior knowledge) that has been successfully used in this
domain is the simple advice that ``if no opponent is within 8 meters,
holding the ball is a good idea.''  In our approach we approximate a
value function $v$ as a function of states and actions.  Advice can be
stated as the following implication, assuming two opponents:
\begin{equation}
d_1\ge 8\;\wedge\;d_2\ge 8\;\wedge\;a=h\;\Longrightarrow\;v\ge c,
\end{equation}
where $d_1$ denotes the distance to Opponent 1, $d_2$ the distance to
Opponent 2, $a=h$ the action of holding the ball, $v$ the predicted
value, and $c$ is some constant. It is hoped that this ``advice" can
help in generating an improved value function $v$ based on the current
description of the state of the soccer game.

%%%%% Shavlik & Maclin's paragraph revised by Ted follows:
%Our second potential application is to a reinforcement learning task
%\citep{sutton.book1998}.  In particular, we plan to use the {\it
%Keep-Away} subtask of soccer that Stone and Sutton developed
%\citep{stone.icml2001}. In reinforcement learning, one common approach
%is to learn to predict a value that estimates the sum of the future
%rewards that an agent will receive after executing an action at a
%given state.  In {\it Keep-Away} the state description includes
%measurements such as the distance to each of the opposing players,
%distance to the soccer ball, distances to the edges of the field, etc.
%Learning in such a domain is difficult \citep{stone.icml2001}.
%However, it has been demonstrated that providing advice can result in
%significant performance improvements
%\citep{kuhlman.aaaiworkshop2004,maclin.mlj96}.  One example of advice
%that has been successfully used in this domain is the simple advice
%that ``if no opponent is within 8 meters, holding the ball is a good
%idea.''  For our approach, this advice can be stated as the following
%implication, assuming two opponents:
%\begin{equation}
%d_1\ge 8\;\wedge\;d_2\ge 8\;\Longrightarrow\;vh\ge c,
%\end{equation}
%where $d_1$ denotes the distance to Opponent 1, $d_2$ the distance to
%Opponent 2, $vh$ the predicted value for holding the ball, and $c$ is
%some constant. It is hoped that this ``advice" can help in generating
%an improved value function based on current descriptions of the state
%of the soccer game.

%%%%% Shavlik & Maclin's original paragraph (edited by Olvi) follows:
%Our second potential application is to a reinforcement learning task
%\citep{sutton.book1998} based on the RoboCup simulated soccer domain
%\citep{noda.aai98}.  In particular, we plan to use the {\it Keep-Away} subtask
%of soccer that Stone and Sutton developed \citep{stone.icml2001}. In
%reinforcement learning, one common approach is to learn to predict 
%accurately a value that estimates the sum of the future (numeric) rewards
%that an agent will receive after executing an action at a given state.
%The agent then uses these predictions to choose its actions.
%The predictions are based on the
%current description of the state of soccer game, which includes measurements such as the
%distance to each of the opposing players, distance to the soccer ball, distances
%to the edges of the field, etc.
%Learning in such a domain is difficult \citep{stone.icml2001}.  However,
%it has been demonstrated that
%providing advice to such a problem solver can result in significant
%performance improvements \citep{kuhlman.aaaiworkshop2004,maclin.mlj96}.
%One example of advice that has been successfully used in this domain is
%the simple advice that ``if no opponent is within 8 meters, holding the
%ball is a good idea.''  For our approach, this advice can be stated as the
%following implication, assuming that there are two opponents:
%\begin{equation}
%d_1\ge 8\;\wedge\;d_2\ge 8\;\Longrightarrow\;vh\ge c,
%\end{equation}
%where $d_1$ denotes the distance to Opponent 1, $d_2$ the distance to 
%Opponent 2, $vh$ the predicted value for holding the ball, and $c$
%is some constant. It is hoped that this ``advice" can help in
%generating an improved value function based on current descriptions
%of the state of the soccer game.

\section{Conclusion and Outlook} \label{section:5}
We have presented a knowledge-based formulation of a nonlinear kernel
SVM approximation. The approximation is obtained using a linear
programming formulation with any nonlinear symmetric kernel and with
no positive semidefiniteness (Mercer) condition assumed.  The issues
associated with sampling the knowledge sets in order to generate
function values (that is, a matrix $A$ and a corresponding vector $y$)
in situations where there are no conventional data points constitute
an interesting topic for future research.  Additional future work
includes refinement of prior knowledge and applications to medical
problems, computer vision, microarray gene classification, and
efficacy of drug treatment, all of which have prior knowledge
available.
\acks{We are grateful to our colleagues Rich Maclin and Dave
Musicant for constructive comments.  Research described in this UW
Data Mining Institute Report 03-05, October 2003, was supported by NSF
Grants CCR-0138308, and IRI-9502990, by NLM Grant 1 R01 LM07050-01, by
DARPA ISTO Grant HR0011-04-0007, by PHS Grant 5 T15 LM07359-02 and by
Microsoft.}

\bibliography{mangasarian04a}
%\bibliography{temp}

\end{document}
