%-*-mode: text-*-
\documentstyle[12pt]{article}
\pagestyle{empty}

\setlength{\unitlength}{0.1in}
\setlength{\oddsidemargin}{0.375in}
\setlength{\evensidemargin}{0.375in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.9in}
\setlength{\textwidth}{5.15in}
\setlength{\parindent}{2em}

\newcommand{\pla}{{\sc pla}}
\newcommand{\Pla}{{\sc Pla}}
\newcommand{\qs}{{\sc qs}}
\newcommand{\Qs}{{\sc Qs}}
\newcommand{\qmr}{{\sc qmr}}
\newcommand{\Qmr}{{\sc Qmr}}
\newcommand{\bounder}{{\sc bounder}}
\newcommand{\Bounder}{{\sc Bounder}}

\begin{document}
\vspace*{1.22in}
\begin{flushleft}
QUALITATIVE SKETCHING OF PARAMETERIZED FUNCTIONS\\
\vspace{.13in}
Elisha Sacks\\
\vspace{.13in}
Laboratory for Computer Science, Massachusetts Institute of Technology, 
545 Technology square, Cambridge, MA 02139, USA.

\end{flushleft}
\vspace{.12in}

\section{ABSTRACT}

This paper describes a qualitative sketcher called \qs\ that draws
families of parameterized real univariate functions.  It is useful
because sketches provide better insight into global behavior than verbal
or other descriptions.  Existing graphics packages cannot plot
parameterized functions because they require exact numerical values.
Also, they cannot recognize discontinuities, singularities, and
asymptotes or graph infinite domains.  \Qs\ avoids these limitations by
constructing and manipulating global models of functions.  It can sketch
functions that arise in pharmacokinetics, probability theory, circuit
analysis, and other domains.

\section{ACKNOWLEDGMENT}

This research was supported (in part) by National Institutes of Health
Grant No. R01 LM04493 from the National Library of Medicine and National
Institutes of Health Grant No. R24 RR01320 from the Division of Research
Resources.

\section{INTRODUCTION}

This paper describes a qualitative sketcher called \qs\ that draws
families of parameterized real univariate functions.  Qualitative
sketching focuses on the high-level attributes of functions, such as
extrema and discontinuities, without specifying exact values at every
point.  At this level of abstraction, a few sketches generally suffice
to describe entire families of parameterized functions.  For example,
the family $f_a(x)=e^{ax}$ requires the three sketches shown in
Figure~\ref{f-exp}, corresponding to $a$ negative, zero, and positive.
\Qs\ helps its users understand the global behavior of parameterized
functions by generating all possible sketches.

\begin{figure}[htbp]
\vspace{2in}
\caption{The qualitative sketches of $e^{ax}$}\label{f-exp}
\end{figure}

\Qs\ can plot a much wider class of functions than conventional graphics
packages.  It handles parameterized functions with infinite domains and
unbounded values, whereas conventional plotting programs require bounded
numeric functions on finite domains.  Also, \qs\ explicitly recognizes
discontinuities, singularities, asymptotes, and periodicity.  To sketch
a parameterized function with a conventional graphics package, one must
plot it for several values of each parameter and inspect the results for
possible asymptotes, discontinuities, and singularities.  The user must
guarantee that his choices of specific parameter values generate all
qualitatively distinct cases and that his choice of domain includes all
interesting behaviors.  He must also decide what ranges of parameter
values produce the same abstract behavior.  Sketching a parameterized
function with \qs\ is equivalent to sketching all of its infinitely many
instances and collapsing the results into qualitatively equivalent
sets.

The next section contains a brief overview of the mathematical reasoner
that the sketcher uses.  In the following two sections, I describe the
sketching algorithm and discuss applications in pharmacokinetics,
probability theory, utility theory, and circuit analysis.  The
final section consists of a summary, a discussion of related work, and
proposed extensions.

\section{THE MATHEMATICAL REASONER}

The qualitative sketcher uses the \qmr\ mathematical
reasoner\cite{sacks85} to derive the properties of parameterized
functions.  \Qmr\ handles a large class of functions on the real
numbers, including the {\it extended elementary functions:} polynomials
and compositions of exponentials, logarithms, trigonometric functions,
inverse trigonometric functions, absolute values, maxima, and minima.
It infers their {\it qualitative properties:} signs of the first and
second derivatives, discontinuities, singularities, and asymptotes,
which it records in data structures called {\it Q-behaviors}.  For
example, the Q-behavior for the function $(x-a)^{-1}$ appears in
Table~\ref{t-behavior}.

\begin{table}[htbp]
\caption{The Q-behavior of $f(x)=(x-a)^{-1}$}\label{t-behavior}
\vspace{1ex}
\begin{tabular}{rl}
\mbox{\boldmath $f(x)$} & $(x-a)^{-1}$\\
\mbox{\bf\boldmath sign of $f'(x)$} & negative on $(-\infty, a)$ and $(a,\infty)$\\[1ex]
\mbox{\bf\boldmath sign of $f''(x)$} & negative on $(-\infty, a)$; 
                                    positive on $(a,\infty)$\\[1ex]
{\bf discontinuities} & $f(a)$ undefined; 
                        $\displaystyle\lim_{x\rightarrow a^-}f(x)=-\infty$;
                        $\displaystyle\lim_{x\rightarrow a^+}f(x)=\infty$\\[1ex]
{\bf singularities} & $f'(a)$ undefined;
                      $\displaystyle\lim_{x\rightarrow a}f'(x)=-\infty$
\end{tabular} 
\end{table}

\Qmr\ can either analyze simple functions from first principles of
calculus or match them against stored patterns.  It analyzes complex
functions by recursively analyzing their constituents and combining the
results.  Three combination algorithms suffice because each complex
function must consist of a sum, product, or functional composition of
its constituents.  \Qmr\ may produce several alternate Q-behaviors,
depending on algebraic relations between parameters.  For example,
composing $e^x$ with $ax$ produces a decreasing, constant, or increasing
function, depending on $a$'s sign, as shown in Figure~\ref{f-exp}.

\Qmr\ invokes the \bounder\ inequality prover\cite{sacks87} to resolve
inequalities over sets of constraints.  Given the constraint $a<b$, for
example, \bounder\ can prove $e^a<e^b$ and refute $b-a<0$, but can
neither prove nor refute $a^2<b^2$.  It can also derive upper and lower
bounds for symbolic expressions over constraint sets.  When \bounder\
pronounces an inequality ambiguous, \qmr\ constructs a Q-behavior for
each possibility.  This strategy certainly derives all possible
Q-behaviors for any input, but may produce spurious ones as well.  These
arise when \bounder\ fails to prove valid inequalities.  This is a
fundamental limitation because no program can prove all inequalities
between arbitrary extended elementary functions, as shown by
Richardson.\cite{richardson68}  However, \bounder\ can handle all the
examples in this paper as well as many more complicated inequalities. 

\section{THE SKETCHING ALGORITHM}

\Qs\ sketches a function by invoking \qmr\ to construct its Q-behaviors
and sketching each of them separately.  It chooses a set of interesting
points for each Q-behavior, picks an appropriate scale, lays out the
points on the plane, and connects them with smooth curves.  The
interesting points for a Q-behavior consist of its boundaries, extrema,
inflection points, discontinuities, singularities, and any additional
points designated by the user.  \Qmr\ can infer every type of
interesting point (except for user designated ones) directly from
Q-behaviors.

\subsection{Qualitative scales}

A \qs\ scale is a function from symbolic expressions to real numbers
that preserves inequalities and bounds derivable by \bounder.  Put
symbolically, if $s$ is a scale, $a$ and $b$ expressions, and $C$ a
set of constraints then
\begin{eqnarray}
\label{e-sc1} a\stackrel{\scriptscriptstyle C}{<}b\Rightarrow s(a)<s(b)\\
\label{e-sc2} a\stackrel{\scriptscriptstyle C}{\leq}b\Rightarrow s(a)\leq s(b)\\
\label{e-sc3} \mbox{\sc inf}_C(a)\leq s(a)\leq\mbox{\sc sup}_C(a)
\end{eqnarray}
where $a\stackrel{\scriptscriptstyle C}{<}b$ or
$a\stackrel{\scriptscriptstyle C}{\leq}b$ holds iff \bounder\ can
deduce $a<b$ or $a\leq b$ from $C$ and $\mbox{\sc inf}_C(a)$ and 
$\mbox{\sc sup}_C(a)$ denote \bounder's bounds on $a$ given $C$.  Since
a number is its own lower and upper bound, equation~(\ref{e-sc3})
implies that scales map numbers to themselves.  Scales also preserve
linear relations whenever possible, that is 
\begin{equation}\label{e-sc4}
a\stackrel{*}{=}mb+n\Rightarrow s(a)=m\left[s(b)\right]+n
\end{equation}
where $x\stackrel{*}{=}y$ means that \qs\ can prove $x$ equal to $y$,
$m$ and $n$ denote numbers, and $a$ and $b$ denote symbolic expressions.
Equation~(\ref{e-sc4}) cannot be strengthened by substituting $=$ for
$\stackrel{*}{=}$ because equality between arbitrary extended
elementary functions is undecidable, as shown by
Richardson.\cite{richardson68}  Nonetheless, the powerful {\sc macsyma}
algebraic simplifier,\cite{macs83} which \qs\ uses, recognizes all
straightforward equalities and many more subtle ones.  As a special
case, each scale maps $-\infty$ to a very small number and $\infty$ to a
very large number.  These numbers satisfy equations~(\ref{e-sc1})
and~(\ref{e-sc2}), but violate equations~(\ref{e-sc3}) and~(\ref{e-sc4}).

Equations~(\ref{e-sc1}--\ref{e-sc4}) guarantee that scaling preserves
known relations between interesting points.  Other relations between
scaled values reflect arbitrary decisions.  For example, consider
the Q-behavior of $(x-a)(x-b)$ with zeros at $a$ and $b$.  When no
constraints exist, \qs\ must arbitrarily draw $a$ greater than $b$ or
$b$ greater than $a$, even though either relation could hold.  Sketches
cannot express partial orders.

\subsection{Sketching}

After choosing a scale for the interesting points $\{x_1,\ldots,x_n\}$ of
a behavior and a scale for their images $\{f(x_1),\ldots,f(x_n)\}$, \qs\
prints each $x_i$ at its scaled location on the $x$ axis and each
$f(x_i)$ at its scaled location on the $y$ axis.  However, it does not
print large expressions because they would obscure the sketch.  It
chooses a new label ($x_i$ for the independent variable $x$ and $y_i$ for
the dependent variable), attaches it to the expression, and prints it.
Next, \qs\ fills in the sketch.  All discontinuities, singularities,
extrema, and inflection points are interesting points, so the function
must be continuous, differentiable, monotone, and of fixed convexity on
the intervals between them.  This enables \qs\ to capture the portion of
a function between adjacent interesting points with a smooth curve.
Since we are only interested in qualitative behavior, the exact path
of the curve is unimportant, as long as it has the correct end points
and convexity.  \Qs\ uses a modified cubic spline, but any curve with
four degrees of freedom would serve. 

For the sake of brevity and clarity, the following discussion refers to
points even though the program manipulates their scaled values.  Let $p$
and $q$ be two finite adjacent interesting points.  If $f$ is continuous
at $p$ and $q$, \qs\ draws a smooth curve between the pairs $(p,f(p))$
and $(q,f(q))$ with initial derivative $f'(p)$ and final derivative
$f'(q)$.  If $f$ is discontinuous and bounded at $p$ or $q$, \qs\ uses
the left or right limit respectively in place of the (possibly
undefined) value.  Similarly, it substitutes the left and right
derivatives for $f'(p)$ and $f'(q)$ at sharp points and cusps.  An
unbounded discontinuity at $p$ is asymptotic to the line $x=p$.  \Qs\
extends the sketch to the top of the $y$ axis when the limit is $\infty$
and to the bottom when it is $-\infty$.  It marks the asymptote with a
dashed line.  Infinite interesting points are treated analogously to
unbounded finite ones.  \Qs\ extends the sketch to the left end of the
$x$ axis for $-\infty$ and the right end for $\infty$.  If the limit is
a finite number {\it lim}, it marks the asymptote $y=\mbox{\it lim}$
with a dashed line.

Figure~\ref{f-hyp} illustrates these ideas with two sketches.  All
constants are declared positive in these examples and throughout the
rest of the paper.  The left-hand figure contains the sketch of
$x^3-3ax$; its interesting points are: boundaries at $\pm\infty$,
extrema at $\pm\sqrt{a}$, and an inflection point at 0.  The right-hand
figure contains the sketch of $\frac{x-a}{x-3a}$ with interesting
points: $-\infty, a, 3a$ and $\infty$.  The sketch includes $(a, 0)$
because zero crossings have been designated interesting.   There is 
a vertical asymptote at $x=3a$ and a horizontal one at $y=1$.

\begin{figure}[htbp]
\begin{picture}(50,32)
\put(12.5,0){\makebox(0,0){$x^3-3ax$}}
\put(40,0){\makebox(0,0){$\displaystyle\frac{x-a}{x-3a}$}}
\end{picture}
\caption{Sample \qs\ sketches}\label{f-hyp}	
\end{figure}

All the functions discussed so far have a finite number of interesting
points.  They are continuous and monotone for all sufficiently large and
small values.  \Qmr\ can also represent periodic functions with
infinitely many extrema and discontinuities, although it cannot
represent functions with infinitely many extrema in a finite region,
such as $\sin 1/x$.  The algorithm described thus far would fail on
periodic functions, since it could not lay out an infinite number of
points.  Instead \qs\ uses this basic algorithm to sketch one period of
the function, marks it with a broken line, and prints its length.
Figure~\ref{f-periodic} contains the sketches of $\sin(ax)$ which has a
period of $2\pi/a$ and $\tan(ax)$ which has a period of $\pi/a$.  The
tangent has asymptotes at $\pm\pi/2a$ indicated, as usual, by dashed
lines.

\begin{figure}[htbp]
\begin{picture}(50,25)
\put(12.5,0){\makebox(0,0){$\sin(ax)$}}
\put(40,0){\makebox(0,0){$\tan(ax)$}}
\end{picture}
\caption{Two periodic functions}\label{f-periodic}
\end{figure}

\section{APPLICATIONS}

Qualitative sketching applies to systems describable by univariate real
functions.  These arise in many domains, including pharmacokinetics,
probability theory, utility theory, and circuit analysis.

\subsection{Pharmacokinetics}

Pharmacokinetics is the study of how drug concentrations vary over time
in the body.  Wagner\cite[ch.\ 1--6]{wagner1} analyzes several
pharmacokinetic models and plots the results.  In a typical example,
reproduced in Figure~\ref{f-wagner}a, he plots the function
\begin{equation}\label{e-wagner}
f_E(f_u)= \frac{f_u p_u}{1+f_u p_u}
\end{equation}
for several specific values of the parameter $p_u$.  \Qs\ summarizes all
the instances of~(\ref{e-wagner}) in a single sketch, shown in
Figure~\ref{f-wagner}b.  Unlike the numeric plots, this sketch
establishes that {\it every} instance of equation~(\ref{e-wagner}) has
the same form: each increases monotonically, passes through the origin,
approaches 1 asymptotically as $f_u$ increases toward $\infty$, and is
concave.  In this case, the \qs\ sketch is too abstract to serve
Wagner's purpose, finding combinations of $f_u$ and $p_u$ that produce
specific $f_E$ values.  He could either use \qs\ to sketch $f_E$ for
specific numeric values of $p_u$, or invoke the \qmr\ utility that
calculates inverses.

\begin{figure}[htbp]
\begin{picture}(50,26)
\put(13,0){\makebox(0,0){(a)}}
\put(39,0){\makebox(0,0){(b)}}
\end{picture}
\caption{(a) Wagner's graph of $f_E$ (b) The \qs\ sketch}\label{f-wagner}
\end{figure}

\subsection{Probability theory}

Qualitative sketches can help probability theorists and statisticians
derive the properties of continuous probability distributions.  For
example, Freund\cite[sec.\ 5.3]{freund1} discusses the four important
probability distributions that appear in Table~\ref{t-dist} and
constructs their qualitative sketches by hand.  \Qs\ can sketch all four
of them.  The uniform distribution has a trivial sketch consisting of a
line segment, while the exponential distribution is a scaled version of
the left-hand sketch in Figure~\ref{f-exp}.  Figure~\ref{f-freund}
reproduces Freund's sketch of the gamma distribution for several values
of $a$ and $b$ and Figure~\ref{f-gamma} shows the \qs\ version.  This
example demonstrates that qualitative sketches can be more informative
and general than multiple numerical plots.  Figure~\ref{f-normal}
contains the \qs\ sketch of the normal distribution. 

\begin{table}[htbp]
\caption{Four important probability distributions}\label{t-dist}
\vspace{1ex}
\begin{tabular}{ll}
{\bf uniform} & $\displaystyle\frac{1}{b-a}$ on the interval $[a,b]$ 
                and 0 elsewhere\\[1.5ex]
{\bf exponential} & $\displaystyle \frac{1}{\theta}e^{-x/\theta}$
                    for $x>0$ and 0 elsewhere\\[1.5ex]
{\bf gamma} & $\displaystyle \frac{1}{b^a \Gamma(a)} x^{a-1}e^{-x/b}$ 
              for $x>0$ and 0 elsewhere\\[2ex]
{\bf normal} & $\displaystyle \frac{1}{s\sqrt{2\pi}}
               e^{-\frac{1}{2} \left(\frac{x-m}{s}\right)^2}$
\end{tabular}
\end{table}

\begin{figure}[htbp]
\vspace{2.75in}
\caption{Freund's sketch of the gamma distribution}\label{f-freund}
\end{figure}

\begin{figure}[htbp]
\vspace{3.5in}
\caption{The \qs\ sketch of the gamma distribution}\label{f-gamma}
\end{figure}

\begin{figure}[htbp]
\vspace{2.5in}
\caption{The \qs\ sketch of the normal distribution}\label{f-normal}
\end{figure}

\subsection{Utility theory}
Wellman\cite[chap.\ 3]{wellman1} uses \qmr\ to analyze
single-attribute utility functions $u(x)$ and their risk functions: 
\begin{equation}
r(x)=-\frac{u''(x)}{u'(x)}
\end{equation}
The utility functions are extended elementary functions, as are their
risk functions.  Figure~\ref{f-power} contains the sketch of a typical
utility function: $u(x)=x^{1-c}$.  Other common utility functions that
\qs\ can handle include linear functions, exponentials, and logarithms.
Wellman tested \qmr\ on all the examples and exercises appearing in the
unidimensional utility theory chapter of Keeney and Raiffa's
text\cite[chap.\ 4]{Keeney-Raiffa}.  It analyzed 17 out of the
18 cases correctly, enabling \qs\ to sketch them.

\begin{figure}[htbp]
\vspace{2.1in}
\caption{The \qs\ sketch of $u(x)=x^{1-c}$}\label{f-power}
\end{figure}

\subsection{Circuit analysis}

Graphic reasoning plays a significant role in circuit analysis.  For
example, electrical engineers infer the characteristics of a linear
system by sketching the magnitude and phase of its transfer function
$H(j\omega)$ against the frequency $\omega$.  The most common format,
called a {\it Bode plot,} plots the quantities $20\log_{10}|H(j\omega)|$
and $\angle H(j\omega)$ in a logarithmic scale.  \Qs\ can sketch
the Bode plot of any transfer function that it can factor, including
all numeric functions and many containing symbolic parameters.  For
example, Figure~\ref{f-bode} contains the magnitude plot of
\begin{equation}\label{e-bode}
H(j\omega)=\frac{j\omega-a}{(j\omega-2a)(j\omega-3a)}
\end{equation}
with $a$ real and positive.  The Bode plot of a symbolic transfer
function expresses the characteristics common to all its instances.
Engineers can observe them directly with \qs\ instead of plotting
several instances and generalizing the results.

\begin{figure}
\vspace{3in}
\caption{The Bode plot of equation~(\protect\ref{e-bode})}\label{f-bode}
\end{figure}
	
\section{CONCLUSIONS}

This paper has described a qualitative sketcher for parameterized
univariate functions on the real numbers.  Its sketches capture
the significant properties of functions better than verbal
descriptions such as ``f increases between 0 and 1'' or mathematical
descriptions such as $\lim_{x\rightarrow\infty}f(x)=2$.  \Qs\ can sketch
any function that the \qmr\ mathematical reasoner can analyze.  As the
previous section illustrates, this class includes interesting models
from diverse fields.

Qualitative sketching seems to be a new idea.  The only related system
that I found appears in Kuipers.\cite{kuipers85a}  His system plots the
qualitative values of a function at discrete qualitative time points and
connects the results with straight lines.  It marks increasing values
with an ascending arrow, decreasing values with a descending arrow and
steady values with a horizontal line.  Although adequate for Kuipers's
purposes, this algorithm ignores many important properties of functions,
including convexity, discontinuities, singularities, asymptotes, and
periodicity.

Many interesting models, including most nonlinear ones, cannot be
solved in closed form.  \Qs\ cannot sketch these models because \qmr\ is
unable to construct their Q-behaviors.  I am developing a new technique
called piecewise linear abstraction (\pla) for analyzing systems
describable by finite sets of ordinary differential equations.  \Pla\
constructs and analyzes piecewise linear approximations of complicated
models instead of solving them directly.  It uses a phase space
representation to derive the behavior of a piecewise linear system over
its entire domain from its local behavior on linear subregions.  The
resulting phase diagram provides extensive insight into the qualitative
behavior of the system.  For example, Figure~\ref{f-phase} contains the
phase diagram for the system of equations
\begin{equation}
\left[\begin{array}{c}
   z_1'\\
   z_2'
\end{array}\right]
=
\left[\begin{array}{cc}
      -\mu & 0\\
       0  & \lambda
       \end{array}\right]
\left[\begin{array}{c}
       z_1\\
       z_2
\end{array}\right]
 \;\; {\rm with} \;\lambda,\mu > 0
\end{equation}
appearing in Brauer and Nohel\cite[p.\ 172]{brauer1}.  It is clear from
the figure that solutions starting on the $z_1$ axis approach the origin
asymptotically; solutions starting above it approach $(0, \infty)$; and
solutions starting below it approach $(0,-\infty)$.  \Pla\ will include
an extended version of \qs\ that can sketch phase diagrams. 

\begin{figure}[htbp]
\vspace{3.25in}
\caption{A phase diagram}\label{f-phase}
\end{figure}

\raggedright
\bibliography{}
\bibliographystyle{plain}
\end{document}
