\documentstyle[IEEEtran]{article}
\begin{document}
\tolerance 10000
\title{Data Processing Beyond Traditional Statistics:\\
Applications of
Interval Computations.\\ A Brief Introduction}
\author{V. Kreinovich}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ }

\maketitle

\begin{abstract}
This paper contains a brief survey of the application described in this
volume. 
\end{abstract} 
  
\auffil{The author is with 
Computer Science Department,
The University of Texas at El Paso,
El Paso, TX 79968,
email vladik@cs.utep.edu. 
This work was partially 
supported by NSF grant No. CDA-9015006 and NASA Research Grant No.
9-757.}

35 years ago, computational operations with intervals were first introduced
\cite{Moore 1959,Moore 1959a}. They were not introduced in a
theoretical journal, they appeared as 
Technical Reports of Lockheed Missile and Space Co., with the goal of
solving applied real-life problems. 

30 years ago, 
the first survey on
interval computations have appeared \cite{Moore 1964}. It describes several
different methods, and it also describes a
potential application: to compute the trajectory of a spaceship
going to the Moon. 

Since then, many exciting applications have appeared. 
Some of them use only operations with intervals, some use other
mathematical techniques as well. This survey is intended to provide a
guide to the applications presented in this workshop.

\section{Data Processing} 
One of the main functions of a computer is crunching numbers, or, to
use a more fancy term, {\it data processing}. This data comes either
from measurements, or from expert estimates, or from the results of
the previous processing. 
Expert estimates are often very important, but 
a computer can easily crunch (and does crunch) thousands and
millions numbers per second. There is not enough experts in the world
to supply that many expert estimates. Therefore, the majority of data
processing algorithms do not use expert estimates at all:
they either directly process the results of the measurements, or
process the results of pre-processing these results. In the second
case, we can consider the entire chain of processors starting from the
sensors and eventually producing the desired result as one huge data
processing algorithm. 
So, in the majority of cases, 
{\it data processing processes the results of measurements.}

\section{Why Do We Process Data At All?} 
\begin{itemize}
\item First of all, we want to {\it know} the world
that we live it. In particular, we want to know the characteristics
of the physical quantities that characterize this world. In a few
cases, we can simply measure them (e.g., body temperature, or weight).
But for more complicated characteristics, like an amount of oil in the
well, or a distance to a star, there is no way to measure them directly. 
So, we measure what we can and then, from the results of these
measurements, we try to reconstruct the desired value.

\item Second, we want to {\it change} this world: we want to
control the objects that already exist, or to change them, or even to
create ({\it synthesize}) new objects.
\end{itemize}

\section{Main Problem}
And here comes the problem. Measurements are never absolutely precise. The
result $\tilde x$ of measuring a physical quantity $x$ (e.g.,
temperature) may differ from the actual value of that quantity.
E.g., if you have weighed yourself, and the result is 125 pounds,
this does not mean that you weight equals exactly 125. If the scales have 
an accuracy $\pm 2$, then the actual weight can be any number from 
123(=125-2) to 127=(125+2). 

So, the {\it data} that we process are {\it not} absolutely {\it
precise}. This inaccuracy
leads to the inaccuracy in the {\it result} of data processing. The
problem is {\it to estimate the resulting inaccuracy.}

If we do not know this accuracy, then the result of data processing is
of little practical use: e.g., suppose that we estimated that 
a given location contains 100 million 
tons of oil, but we do not know the accuracy of this estimate. Then,
if this is $100\pm 5$, this location is worth developing, but if it is 
$100\pm 100$, then we need further analysis to decide what to do.

\section{In Many Cases, We Know Probabilities Of Errors} 
In many cases, the manufacturer of a measuring instrument provides us
with the probabilities of different values of a measurement error.
For such cases, there exist numerous methods that compute statistical
characteristics of the resulting error (see, e.g., \cite{Rabinovich 1993}).

\section{In Many Cases, We Do Not Know Probabilities} In many
other cases, however, the values of the probabilities are not known.
Instead, the manufacturer provides us with the guaranteed accuracy
$\Delta$, i.e., with a guaranteed upper bound
of the error $\Delta x=\tilde x-x$ 
(e.g., ``error cannot exceed 0.1''). 
If our measurement results is $\tilde x$, then the
possible values of $x=\tilde x-\Delta x$ form an {\it interval} $[\tilde
x-\Delta,\tilde x+\Delta]$ (
\cite{Fuller 1987,Artbauer 1988,Rabinovich 1993}.
\smallskip

\noindent{\it Historical comment.}
The first person to describe intervals as a result of 
measurement was Norbert Wiener: in \cite{Wiener 1914}, he applied intervals
to measuring distances, and in \cite{Wiener 1921}, to measuring time. 
\smallskip

Since we are dealing with
intervals, the entire area is called {\it interval computations.} 

In this case, our problem takes the following form:

\section{Main Problem (In Case We Do Not Know
Probabilities)} Suppose that we are interested in the value of a 
physical quantity $y$ that is difficult or impossible to measure
directly. To find the value of $y$, we 
measure several other quantities $x_1,...,x_n$ that
are related to $y$, and then we reconstruct the value of
$y$ from the results $\tilde x_i$ of measuring $x_i$. 
In other words, we have an algorithm $f$ that takes the values $\tilde
x_i$ and returns an estimate $\tilde y=f(\tilde x_1,...,\tilde x_n)$
(this estimate is called the {\it result of indirect measurement}).  

In some cases, this algorithm consists of simply applying known
formulas to $\tilde x_i$. In other cases, this algorithm implements a
numerical method for solving a system of equations that connect $x_i$
and $y$. These equations can be algebraic, differential, integral,
etc, and the resulting algorithm can be pretty complicated.

The problem is to estimate the error of the
estimate $\tilde y$:

\noindent{\it We know:} 
\begin{itemize}
 
\item $n$ intervals ${\bf x}_i=[\tilde x_i-\Delta_i,\tilde
x_i+\Delta_i]$ and 

\item an algorithm $f$ that transforms $n$ real numbers
$x_1,...,x_n$ into a real number $y=f(x_1,...,x_n)$.
\end{itemize}

\noindent{\it We are interested in:} estimating the interval
$$f({\bf x}_1,...,{\bf x}_n)=
\{f(x_1,...,x_n)\,|\, x_1\in
{\bf x}_1, ..., x_n\in {\bf x}_n\}.$$

This is the basic problem of interval computations with
which the entire area started (see, e.g., \cite{Moore 1966}). 
\newpage

\section{Where Does This Main Problem Fit Into Mathematics}
\begin{itemize}
\item For many algorithms $f$, methods of estimating the
accuracy of the result $\tilde y$ have been developed in {\it
numerical mathematics}. These methods often produce the {\it exact}
error bounds. 
\begin{itemize}

\item[]{\it Numerical mathematics does not always give us the solution
to our problem.} Error estimation methods of numerical mathematics  
are often very complicated, and
require difficult mathematical techniques. Because of that,
algorithms $f$ for which such methods are known form a small subset in
the set of all algorithms that are used for data processing. New data
processing problems appear every day, and new data processing
algorithms are being designed to solve these problems. For a
new data processing algorithm, for a 
reasonable period of time, no error estimation method is known. 
To handle these algorithms, we need a general tool that would, given
$f$, $\tilde x_i$, and $\Delta_i$, automatically estimate the error
bound for $y$.
\end{itemize}
\item
Problems that appear when we do not know the exact distribution,
but we know instead that a distribution belongs to a given {\it class}
$\cal P$ of distributions, are called problems of {\it robust
statistics} (\cite{Huber 1981}; \cite{Wadsworth 1990}, Ch. 16). So,
from statistical viewpoint, interval computations is a particular case
of robust statistics, in which $\cal P$ is the class of all
distributions located on a given interval.
\begin{itemize}
\item[]{\it Robust statistics does not always give us the solution
to our problem} because robust methods have been developed only for
some functions $f$.
\end{itemize}

\item The case when instead of a number, we have an interval
(or, more generally, a set) of possible values, has been developed in
mathematics under the name of {\it set-valued analysis} (see, e.g., 
\cite{Aubin 1990}). In particular, differential equations with the
uncertain (set-valued) right-hand side (called {\it differential
inclusions}) are used, e.g., in control problems
\cite{Aubin 1984,Aubin 1990}. 
\begin{itemize}
\item[]{\it Set-valued analysis does not always give us the solution
to our problem} because its methods have been developed only for
specific $f$, e.g., when $f$ is a solution of a differential or an
integral equation of a certain type.
\end{itemize}
\end{itemize}
\newpage

\section{Applications of the Main Problem}
In this volume, the following applications are presented:
\begin{itemize}
\item to computing the {\it diameter of the laser beam} \cite{Serrano};
\item to computing the stability times, in particular, for {\it
particle accelerators} \cite{Berz};
\item to processing {\it geophysical data} \cite{Doser,Morgenstein}.
\end{itemize}

If we have several variables, then in addition to the intervals of
possible values for each of them, we may have additional information
about the relationship between $x_i$. As a result, the set of possible
values of $(x_1,...,x_n)$ forms a {\it convex set} (not necessarily a
box). Applications of this approach to {\it civil engineering}
problems are presented in \cite{Elishakoff}. 

Special computational problems appear when the results $x_i$ of direct
measurements are obtained from measuring one and the same quantity in
the different moments of time. These problems are outlined in
\cite{Zrilic}. 

\section{Additional Problems}
As we have already mentioned, 
if we cannot measure $y$ directly, then we must do the following:
\begin{itemize}

\item first,
find a {\it relationship} between the desired quantity $y$
and the directly measurable 
quantities $x_i$;

\item second, 
use this relationship to design an {\it algorithm} $f$ that
transforms the results $\tilde x_i$ of direct measurements into an
estimate $\tilde y$ for $y$;

\item third, use the known accuracies $\Delta_i$ 
of measuring $x_i$ to
estimate the {\it accuracy} $\Delta$ of the final estimate $\tilde y$.
\end{itemize}

The main problem describes the case when 
we already have an
algorithm $f$. However, in some cases, we do not know $f$, and finding $f$
is part of the problem. Depending on what we know, we can consider two
different situations:
\begin{itemize}

\item We want to estimate the accuracy $\Delta$ of the
result of data processing, but the relationship between the directly
measurable quantities $x_i$ and the 
desired quantity $y$ is known only indirectly (not in the
form of an algorithm). 

\item We want to estimate the accuracy $\Delta$ of the
result of data processing, but 
the relationship between the directly measurable quantities $x_i$ and
the desired quantity $y$ has to be determined from the experimental
data (this is called an {\it identification problem}). 
\end{itemize}

\section{What If The Relationship Between The Directly
Measured Quantities $x_i$ And The Desired Quantity
$y$ Is Known Only Indirectly
(Not In The Form Of An Algorithm)}
In this case, if we want the results of our computations to be
guaranteed, then we need some method like interval computations.

\subsection{Explicit analytical expressions}
Mathematically, the simplest case is when we have an {\it explicit
analytical expression} for the dependency of $y$ on $x_i$ (but
computationally, we still have a problem). 
For this case, a computation method has been proposed in
\cite{Kraemer}.

\subsection{Equations and systems of equations}
A more complicated case is when we have an expression for the desired
function as a {\it sum of an infinite series} (it can be Fourier, Taylor
series, etc). This case is described in \cite{Solak}. 

Instead of an explicit expression, we may have an {\it equation} or a
{\it system of equations} that
describes the desired dependency: 
\begin{itemize}
\item It can be a system of {\it non-linear (algebraic) equations}; an
application for computer graphics is described in \cite{Caprani1}. 
\item It can be an {\it ordinary differential equation} (ODE), or a
system of ODE. This case is analyzed:
\begin{itemize}
\item[$\bullet$]in \cite{Zyuzin1,Zyuzin2}, with
applications to {\it airplane inertial navigation}, and
\item[$\bullet$]in \cite{Menshikov}, to compute a singularity 
point, with possible applications to equations that emerge in {\it
optimal control} theory.
\end{itemize}
\item It can be a {\it partial differential equation}
\cite{Dobronets}.
\item It can be an {\it integral equation} \cite{Caprani2}, with an
application to {\it astrophysics}. 
\item It can be a complicated equation described in terms of {\it
sets} \cite{Sommerer}, with an application to the description of a
{\it milling surface} and other {\it manufacturing processes}. 
\end{itemize}

\subsection{Systems of equations and inequalities}
Instead of a system of equations, we may have a {\it system of
equations and inequalities} (constraints). This case is considered in
\cite{Hyvonen1,Hyvonen2,Semenov}.

\subsection{Optimization problems}
The relationship between the known values $x_i$ and the desired value
$y$ can also be described in terms of some {\it optimization problem}.
In this case, we must get a guaranteed solution of the optimization
problem. A survey of such methods is presented in \cite{Kearfott}. 

In general, the global optimization problem is NP-hard (i.e.,
crudely speaking, every algorithm requires exponential time on at
least some of the cases). Therefore, 
these algorithms tend to take (sometimes) too
long to compute. Several
approaches have been used to speed up these computations:
\begin{itemize}
\item {\it neural networks} \cite{Murgu} (with an application to {\it
traffic control});
\item {\it genetic algorithms} \cite{Alander,Patil1};
\item {\it simulated annealing} \cite{Patil1};
\item {\it design of experiments} \cite{Alander};
\item {\it logic programming} \cite{Chen,Hyvonen1,Semenov}.
\end{itemize}

The combination of constraints and optimization is analyzed in
\cite{Chen,Hyvonen1,Semenov}. 

\section{What If The Relationship
Between Direct Measurements And The
Desired Value Has To Be Determined?
Identification Problem}

\subsection{General Case}
\ \ \ An application to determining the parameters of {\it learning curves}
(that describe how people learn manufacturing skills) is given in
\cite{Beruvides}. 

An application to {\it quality control} 
in manufacturing is described
in \cite{Hadj}. 

An application to finding the parameters of {\it time series} is
described in \cite{Campos}. 

In general, the interval identification problem is also NP-hard, so,
heuristic methods are used: e.g., {\it neural networks} are used in
\cite{Patil3}. 

\subsection{Linear Models}
\subsubsection{Why Linear Models}
If we cannot reconstruct the {\it exact} dependency, then, maybe, we
will be able to neglect some small terms, and solve the resulting
simplified system. For example, if the values $x_i$ are small, then we
can neglect quadratic and higher order terms in the expansion of the
function $f$, and approximate $y$ with a linear dependency: $y\approx
y_0+y_1x_1+...+y_nx_n$. In this case, after $N$ measurements, we get 
intervals ${\bf y}^{(k)}$ and ${\bf x}_i^{(k)}$, $1\le k\le N$, 
of possible values of $y$ and $x_i$, and {\it identification problem}
means that we must find the values $y_i$ that satisfy the following
system of equations:
$${\bf y}^{(k)}\approx y_0+y_1{\bf x}_1^{(k)}+...+ y_n{\bf x}_n^{(k)},\ 1\le
k\le N.\eqno{(1)}$$ 
In mathematical terms, we must find the values $y_i$ for
which for each $k$, the corresponding values can be equal (i.e., for
each $k$, 
the left- and the right-hand sides of the equation (1) have a
common point). 
In other words, we arrive at a problem of solving a {\it system of
interval linear algebraic equations}. 

\subsubsection{Two Possible Formulations Of Identification Problems}
From the computational viewpoint, this problem can be formulated in
two different ways:
\begin{itemize}
\item To find {\it some} values $y_i$ that are consistent with the
measurements (in the above sense).
\item To find {\it all} values $y_i$ that are consistent with the
given measurements. 
\end{itemize}

We may also have a situation in which each measurement result 
$$({\bf y}^{(k)},{\bf x}_1^{(k)},...,{\bf x}_n^{(k)})$$
may correspond not to a {\it single} observation, but to a {\it
series} of observations, and
may mean that every time when the inputs were in ${\bf x}_i^{(k)}$,
the results were in ${\bf y}^{(k)}$. In this case, $\approx$ in the
above formula means $\supseteq$. Different formulation are described
and compared in \cite{Shary}. 

\subsubsection{Even For Linear Models, Identification Problem Is In
General Intractable} 
Even for linear systems, the problem is still NP-hard
\cite{Lakeyev,Rohn}. 

\subsubsection{Efficient Algorithms For Particular Cases Of Linear Models}
For some particular cases of linear systems $${\bf A}x={\bf b},$$ 
efficient algorithms are possible:
\begin{itemize}
\item algorithms for computing an {\it inner estimation} for the
solution are proposed and described in
\cite{Kupriyanova,Lakeyev,Shary}; these algorithms are based on using
{\it Kaucher's arithmetic} (a generalization of interval arithmetic
that allows intervals $[a^-,a^+]$ with $a^->a^+$);  
\item for {\it symmetric} matrices, algorithms are described in 
$\bf A$ \cite{Alefeld};
\item for {\it $H-$matrices}, a new method is described in \cite{Chang}.
\item If input intervals are small enough, then there exists a
feasible algorithm that computes the exact solution in {it almost all}
cases \cite{Lak2}. 
\end{itemize}

\subsection{If Linear Models Do Not Work, Which Non-Linear Models
Should We Choose?}
For the cases when linear dependency does not work, \cite{Trejo}
advocates the use of {\it fractionally linear} models.

\subsection{Physics As Identification}
If we interpret the word ``identification'' broadly enough, as
determining the (unknown) dependency between physical quantities, then the
entire {\it theoretical physics} becomes a particular case of an
identification. In \cite{Korlyukov}, it is shown that if we take
measurement uncertainty into consideration, then some divergence
problems will disappear.  

\section{Synthesis, Design, Control, And Decision Making}
In the previous sections, we have described applications to {\it knowing} the
world. Let us now describe the related problems that appear when
we want to {\it change} it, i.e., problems of 
decision-making, design, and control. 

\subsection{Goal: find an element from a finite set}
The simplest (at least in formulation) decision-making problems are
when we must find all elements 
from a given finite set that satisfy certain
conditions. Two problems of this type are described in this volume:
\begin{itemize}
\item finding input variables whose
       influence on the 
       result is the largest \cite{Beltran}, with the application to
detecting defective stages in VLSI
manufacturing;
\item locating local extrema of a function of one 
 variable from interval measurement results \cite{Villaverde}, with
applications to {\it chemical spectral analysis}, {\it image
processing in radioastronomy}, {\it elementary particles}, and {\it
banking} \cite{Deboeck}. 
\end{itemize}

\subsection{Goal: find the values of finitely many parameters}
The next in complexity are problems in which the goal is to find one or
several continuous parameters. Such applications include:
\begin{itemize}
\item making decisions in {\it economy} \cite{Deboeck,Jerrell}, where interval
uncertainty has to be taken into account; 
\item {\it optimal design} in manufacturing \cite{Hadj}.
\end{itemize}

\subsection{Goal: find a function}
Finally, the most complicated problems are the ones in which one must
find a {\it function}: it may be the dependence of control parameters
on the input (i.e., {\it control strategy}), or the dependence of some
parameter on time, etc.
The examples of these applications include:
\begin{itemize}
\item control of  {\it mobile robot} \cite{Wu};
\item {\it congestion control of computer networks} \cite{Starks};
\item {\it robust stable} control \cite{Barmish};
\item multi-input multi-output control \cite{Akhmedjanov}, with
applications to the control of {\it airplane engines} and {\it power
plants}.
\end{itemize}
For control, optimization problems are often NP-hard \cite{Smith}
(even for linear systems with interval uncertainty), so,
in hard cases, it may be necessary to use {\it expert knowledge} to
produce the good control. 

\subsection{Holistic approach to design}
In real-life, mathematically formulated 
 design problems (that we have been talking
about) and more down-to-Earth problems (like: should we choose an 8-bit
or a 16-bit processor, and which of the three engines on the market
should we buy for our robot) are often
solved together. 
This idea is described in general terms in \cite{Glazunov}. A
practical example of this general design approach is given in
\cite{Bell}.

\section{Beyond Intervals}
Interval data processing 
methods have been designed for the case when the only information we
have about the error of a direct measurement is the guaranteed upper
bound $\Delta$ for this error. In this case, if the result of measuring a 
quantity $x$ is $\tilde x$, then the only thing that we know about the
actual value of $x$ is that this $x$ belongs to an {\it interval} 
$[\tilde x-\Delta, \tilde x+\Delta]$. 

In many cases, we have an {\it additional} information about the
error. This additional information can include:
\begin{itemize}
\item the probabilities of different values of error $\Delta
x=\tilde x-x$ (i.e., {\it statistical information}), and/or
\item {\it expert's knowledge} of the possibility of different
values of $\Delta x$.
\end{itemize}
In many of these cases, interval methods are still 
useful. Some of these cases are described in the present volume.

\section{Applications To Statistics} 
Depending on how much
knowledge we have about the probabilities, we can distinguish between
two types of situations:
\begin{itemize}

\item In some cases, we have enough information to determine the type
of the distribution (e.g., we know that it is a Gaussian
distribution), and we know the approximate values of the {\it parameters} of
this distribution. Statistical methods (based on
finite sample) are never absolutely precise, and besides, the
observations on which these estimates are made are also not precise. 
Therefore, instead of the precise values of the parameters, we only
have {\it intervals} that are guaranteed to contain these values. 
In this case, if we want to predict the values of the related
parameters, and we want to {\it guarantee} the results of the
computations, then we must use {\it interval computations}.
Such cases are described in \cite{Walster1,Wang}. 
\item[]In particular, for
{\it queuing models}, this approach is applied in \cite{Chong} to:
\begin{itemize}
\item [$\bullet$]
{\it communication networks};
\item [$\bullet$]{\it management of the engineering team projects}; 
\item [$\bullet$]{\it transportation systems};
\item [$\bullet$]{\it flexible
 manufacturing systems};
\item [$\bullet$]{\it service systems}; 
\end{itemize}

\item In some cases, we do not have enough information to determine
the family of distributions. Instead, we have {\it estimates} of
certain characteristics (e.g., of the moments, and/or of the distribution
function). Since these estimates come from observations, they are not
precise: e.g., we usually have an {\it interval} of possible values of the
moment. In this case, if we want to know some other statistical
characteristics of the same variable, or statistical characteristics
of the related variables (e.g., of $f(x_1,...,,x_n)$ when we have some
information about $x_i$), then,
we will also come up with {\it
intervals} of possible  values. Such methods are described in
\cite{Cheng,Kuznetsov1,Kuznetsov2,Shevlyakov1,Shevlyakov2}. 

\item In some cases \cite{Orlov}, natural requirements for a
characteristic are inconsistent if we are looking for a numerical one,
but there is an {\it interval-valued} characteristic that satisfies
all desired requirements. In \cite{Orlov}, applications to {\it
sociology} and to {\it quality control} are described.
\end{itemize}

\section{Applications 
Of Interval Methods To Expert Knowledge}
All the information about the real world comes from two sources:
\begin{itemize}
\item from measurements, and
\item from experts.
\begin{itemize}
\item[$\bullet$]
Expert knowledge is often {\it needed} because without such a knowledge,
e.g., the problems of optimal control are intractable \cite{Smith}. 
\item[$\bullet$]Moreover, the type of knowledge provided by the
experts is {\it optimal} (in some reasonable sense) \cite{Lea}.
So, in this sense, expert knowledge is {\it the best} way to handle
such situations.
\end{itemize}
\end{itemize}
We already know that interval methods are useful in
processing measurements data. In many cases, they are also useful in
processing expert's knowledge as well. 

Experts' knowledge is extremely important in many fields
like medicine, geology, economy (and even engineering), 
where we (often) do not have enough confirmed mathematically precise
models, but we still need to make decisions.

In order to describe different types of expert's knowledge (as opposed
to mathematically precise knowledge), let us briefly recall how
precise knowledge is described. This knowledge can be described by
formulas that are obtained from {\it elementary formulas} by using
logical connectives $\vee,\&$, etc, and quantifiers $\forall x$ and
$\exists x$. Since we are talking about the mathematically precise
knowledge, each formula is either true or false.

Expert's statements are rarely describable in these terms, because, 
the experts are often not 100\% sure about
their statements. They phrase it like ``If a patient has a fever, and
a sore throat, and a headache, then most probably, he has a fever''. 

Interval methods can be
used to process expert knowledge:
\begin{itemize}
\item A natural idea is to describe a 
{\it set} 
of possible degrees of belief to describe all the
intricacies of human beliefs. In this case, to describe the expert
knowledge about a certain value $x$, instead of a single interval of
possible values of $x$, we have {\it several} intervals that
corresponds to different degrees of possibility. This is a much more
adequate description of human knowledge \cite{Mantaras}. 

\item With many different degrees of
belief, we encounter the following additional problem: an expert may
be unable to precisely describe his degree of belief.
Therefore, instead of a single value that describes his degree of
belief, we will have an {\it interval} of possible values of degree of
belief \cite{Nguyen}. Even if we have the exact values of the 
expert's degree of belief in basic statements $E_i$ from the knowledge base,
still, we will have interval uncertainty if we are looking for the
degrees of belief in the queries that may be 
logical combinations of these statements $E_i$:
\begin{itemize}
\item[$\bullet$]The degree of belief $d(A\& B)$ 
in, say, $A\& B$ is not uniquely
determined by the degrees of belief $d(A)$ and $d(B)$ in $A$ and $B$: if the
statements $A$ and $B$ are independent, then we have one result, and
if they are correlated, we have another one. So, if we only know the
degrees of belief in $A$ and $B$, then we have an {\it interval} of
possible values of degree of belief in $A\& B$ \cite{Kohout}. 
\item[$\bullet$]Even if we fix a function that transform $d(A)$ and
$d(B)$ into a reasonable estimate for $d(A\& B)$, still, for more
complicated expressions, we will have an additional problem caused by
the fact that every expression, can be described in several different
ways in terms of the basic logical operations $\&$, $\vee$, and $\neg$
(CNF form, DNF form, etc). These expressions are equivalent in
2--valued logic, but if we use these expression to compute degrees of
belief, we end up with different results. So, for such an expression $F$,
instead of the {\it exact} value of $d(F)$, we end up with an {\it
interval} of possible values of $d(F)$ \cite{Turksen,Zuo2}.
\end{itemize}
\item[] If we know the intervals that represent the degrees of belief
in $A$ and $B$, how can we estimate the degree of belief in $A\& B$?
This question is analyzed in \cite{Zuo}. 
\end{itemize}

\section{Hardware And Software Support For Interval Computations}
Algorithms that provide {\it guaranteed estimates} for the results of
data processing are usually more complicated than traditional data
processing algorithm that simply provide us with an estimate (and give
no bound for this estimate). Since interval algorithms are more
complicated, they take much longer to compute than traditional ones. 
In real-life
situations, however, we are often under serious time pressure, and we cannot 
afford to spend any extra computation time. Therefore, we must {\it
speed up} interval computations. For that, we need special hardware and
software support \cite{Walster2}.

\subsection{Hardware support}
\begin{itemize}
\item The first natural idea is to use hardware speed-up 
that is already possible in the existing computers: 
\begin{itemize}
\item[$\bullet$]{\it parallelism}
\cite{Chang,Morgenstein};
\item[$\bullet$]hardware supported {\it operations with long machine
words} \cite{Cooke}.
\end{itemize}
\item Another possibility is to design {\it special hardware}
\cite{Schulte}. 
\end{itemize}

\subsection{Software support}
To provide software support for interval computations, we may use
software ideas that have already been shown to be useful in computing:
\begin{itemize}
\item {\it functional programming}, that enables to prove correctness
of the programs \cite{Lins};
\item {\it logic programming}, that enables us to describe the {\it
goal} of the program without having to always specify the algorithm
\cite{Chen};
\item {\it bag languages}, that describe the sequence of operations in
an easy-to-parallelize way \cite{Cooke};
\item {\it genetic programming}, that enables us to design a program
by directed stochastic search (that uses the ideas from the biological
evolution) \cite{Patil2}. 
\end{itemize}

\begin{thebibliography}{99}

\bibitem{Akhmedjanov}
F. Akhmedjanov, V. Krymsky,
``Robust design of control system for multi-input multi-output plant
 with interval uncertainty'',
{\it These Proceedings}.

\bibitem{Alander}
J. T. Alander, 
``On interval factorial genetic algorithm in global optimization'',
{\it These Proceedings}.

\bibitem{Alefeld}
 G. Alefeld, G. Mayer,
``Recent results on symmetric interval systems'',
{\it These Proceedings}.

\bibitem{Artbauer 1988}
O. Artbauer, ``Application of interval, statistical, and fuzzy
methods to the evaluation of measurements'', {\it Metrologia}, 1988, Vol. 25,
pp. 81--86. 

\bibitem{Aubin 1984}
J.-P. Aubin, A. Cellina, {\bf Differential inclusions},
Spinger-Verlag, Grundlehren der math. Wiss., Vol. 264, 1984. 

\bibitem{Aubin 1990}
J.-P. Aubin, H. Frankowska, {\bf Set-valued analysis}, Birkh\"auser,
Boston, MA, 1990.

\bibitem{Barmish}
 B. R. Barmish,
``Planar geometry problems motivated by robustness of linear systems'',
{\it These Proceedings}.

\bibitem{Bell}
 R. Bell,
``Aerodynamic aids to vehicle stability'',
{\it These Proceedings}.

\bibitem{Beltran}
 M. Beltran and V. Kreinovich,  
``How To Find Input Variables Whose
       Influence On The 
       Result Is The Largest, or, How To Detect Defective Stages In VLSI
Manufacturing?''
{\it These Proceedings}.

\bibitem{Beruvides}
 M. Beruvides et al,
``Interval approach to learning curves',
{\it These Proceedings}.

\bibitem{Berz}
M. Berz,
``Verified integration and generation of Poincare maps using
 Taylor models'',
{\it These Proceedings}.

\bibitem{Campos}
 M. A. Campos  and M. de B. Correia, 
``Interval and high accuracy results for parameter estimation 
 in time series models'', {\it These Proceedings}.

\bibitem{Caprani1}
 O. Caprani, L. Hvidegaard, 
 M. Mortensen, and Th. Schneider,
``Efficient and robust ray intersection'', {\it These Proceedings}.

\bibitem{Caprani2}
 O. Caprani, K. Madsen, and O. Stauning,
``Enclosing solutions of integral equations'', {\it These Proceedings}.

\bibitem{Chang}
 Da-Wei Chang,
``On the interval multisplitting AOR (IMAOR) method'', {\it These
Proceedings}.

\bibitem{Chen}
 H. M. Chen and M. H. van Emden,
``Adding interval constraints to the Moore-Skelboe global
 optimization algorithm'', {\it These Proceedings}.

\bibitem{Cheng}
 H. Cheng and D. Berleant,
``A Software Tool for Automatically Verified
 Reasoning with Intervals and Probability Distributions'', {\it These
Proceedings}.

\bibitem{Chong}
Huang Chongfu,
``Interval and fuzzy approaches to queuing systems'', {\it These
Proceedings}.

\bibitem{Cooke}
 D. E. Cooke, R. Duran, and A. Gates,
``Bag Language speeds up interval computations'', {\it These Proceedings}.

\bibitem{Deboeck}
 G. J. Deboeck et al, 
``Interval Methods for Presenting Performance of Financial Trading
Systems'', {\it These Proceedings}.

\bibitem{Dobronets}
 B. S. Dobronets, 
``A posteriori error estimation and corrected  solution
 of partial differential equation'', {\it These Proceedings}.

\bibitem{Doser}
 D. I. Doser et al, 
``Estimating uncertainties for geophysical tomography'', {\it These
Proceedings}.

\bibitem{Elishakoff}
 I. Elishakoff,
``Convex modeling - a generalization of interval analysis for
 nonprobabilistic treatment of uncertainty'', {\it These Proceedings}.

\bibitem{Fuller 1987}
W. A. Fuller, {\bf Measurement error models}, J. Wiley
\& Sons, New York, 1987.

\bibitem{Glazunov}
 N. M. Glazunov,
``Development of quality interval algorithms, software and systems'',
{\it These Proceedings}.

\bibitem{Hadj}
 S. Hadjihassan, E. Walter,
 and L. Pronzato,
``Quality improvement via the optimization of tolerance intervals during
 the design stage'', {\it These Proceedings}.

\bibitem{Huber 1981}
P. J. Huber, {\bf Robust statistics}, Wiley, N.Y., 1981. 

\bibitem{Hyvonen1}
 E. Hyvonen, S. De Pascale,
``C++ libraries for interval computations'', {\it These Proceedings}.

\bibitem{Hyvonen2}
 E. Hyvonen, S. De Pascale, 
``Interval constraint Excel'', {\it These Proceedings}.

\bibitem{Jerrell}
 M. E. Jerrell,
``Applications of interval computations to economic input-output models'',
{\it These Proceedings}.

\bibitem{Kearfott}
R. B. Kearfott, 
``A review of techniques in the verified solution of constrained global 
  optimization problems'', {\it These Proceedings}.

\bibitem{Kohout}
 L. J. Kohout,
``Fuzzy interval-valued inference system with para-consistent 
 and grey set extensions'', {\it These Proceedings}.

\bibitem{Korlyukov}
A. B. Korlyukov et al, ``Equations Of Physics Become Consistent 
If We Take Measurement Uncertainty Into Consideration'', 
{\it These Proceedings}.

\bibitem{Kraemer}
 W. Kraemer,
``Validated function evaluation using polynomial approximation from
 truncated Chebyshev series'', {\it These Proceedings}.

\bibitem{Kupriyanova}
 L. Kupriyanova,
``Inner estimation of the united solution set of interval linear
 algebraic system'', {\it These Proceedings}.

\bibitem{Kuznetsov1}
 V. P. Kuznetsov,
``Interval Methods For Processing Statistical
Characteristics'', {\it These Proceedings}.

\bibitem{Kuznetsov2}
 V. P. Kuznetsov,
``Auxiliary Problems of Statistical Data Processing: Interval
Approach'', {\it These Proceedings}.

\bibitem{Lakeyev}
A. V. Lakeyev,
``Linear algebraic equation in Kaucher arithmetic'',
{\it These Proceedings}.

\bibitem{Lak2}
A. V. Lakeyev and V. Kreinovich,
``If Input Intervals Are Small Enough, Then Interval Computations
Are Almost Always Easy'', {\it These Proceedings}.

\bibitem{Lea}
 R. N. Lea et al,
``Intelligent Control Makes Sense Even Without Expert Knowledge: an
 Explanation'', {\it These Proceedings}.

\bibitem{Lins}
 R. D. Lins, M. A. Campos, M. de B. Correia,
``Functional programming and interval arithmetic'', {\it These Proceedings}.

\bibitem{Mantaras}
 R. Lopez De Mantaras,
``From intervals to possibility distributions: adding flexibility to
 reasoning under uncertainty'', {\it These Proceedings}.

\bibitem{Menshikov}
 G. G. Menshikov,
``On application of interval approach to finding of the latent singular
 points of initial value problems'', {\it These Proceedings}.

\bibitem{Moore 1959} R. E. Moore, {\bf Automatic error analysis in digital
computation}, Lockheed Missiles and Space Co. Technical Report
LMSD-48421, Palo Alto, CA, 1959.

\bibitem{Moore 1959a} R. E. Moore, C. T. Yang, {\bf Interval analysis}, 
Lockheed Missiles and Space Co. Technical Report
LMSD-285875, Palo Alto, CA, 1959.

\bibitem{Moore 1964} 
R. E. Moore, ``The automatic analysis and control of error in
digital computation based on the use of interval numbers'', In: L. B.
Rall (ed.), {\it Error in Digital Computation. Proceedings of an
Advanced Seminar Conducted by the Mathematics Research Center, U.S.
Army, at the University of Wisconsin, Madison, October 5--7, 1964},
Vol. 1, John Wiley, N. Y., 1964, pp. 61--130.

\bibitem{Moore 1966}
R. E. Moore, {\bf Interval analysis}, Prentice Hall, Englewood Cliffs,
NJ, 1966. 

\bibitem{Morgenstein}
 D. Morgenstein and J. Murphy,
``An application of parallel interval techniques to geophysics'',
{\it These Proceedings}.

\bibitem{Murgu}
 A. Murgu,
``Implementable bounds for a neural networks algorithm in communication
 traffic control'', {\it These Proceedings}.

\bibitem{Nguyen}
 Hung T. Nguyen et al,
``Interval Fuzzy Data Processing: Case When Degree of Belief Is
Described by an Interval'', {\it These Proceedings}.

\bibitem{Orlov},
A. I. Orlov, ``Invariance Leads to the Interval Character of Ordinal
Statistical Characteristics'', {\it These Proceedings}. 

\bibitem{Patil1}
 R. B. Patil,
``Application of simulated annealing and genetic algorithms to verified
 global optimization'', {\it These Proceedings}.

\bibitem{Patil2}
  R. B. Patil,
``Interval genetic programming'', {\it These Proceedings}.

\bibitem{Patil3}
 R. B. Patil,
``Interval neural networks'', {\it These Proceedings}.

\bibitem{Rabinovich 1993}
S. Rabinovich, {\bf Measurement errors: theory and practice},
American Institute of Physics, N.Y., 1993. 

\bibitem{Rohn}
J. Rohn, ``Linear Interval Equations: Computing Sufficiently Accurate
Enclosures is NP-Hard'', {\it These Proceedings}.

\bibitem{Schulte}
 M. J. Schulte and E. E. Swartzlander, Jr.,
``Design and Applications for Variable-Precision, 
 Interval Arithmetic Coprocessors'', {\it These Proceedings}.

\bibitem{Semenov}
 A. L. Semenov,
``Solving optimization problems with the help of the UniCalc solver'',
{\it These Proceedings}.

\bibitem{Serrano}
 E. Serrano et al,
``Error Estimate of the Result of Measuring Laser Beam Diameter'', 
{\it These Proceedings}.

\bibitem{Shary}
 S. P. Shary,
``Linear static systems under interval uncertainty: algorithms to solve
 control and stabilization problems'', {\it These Proceedings}.

\bibitem{Shevlyakov1}
 G. L. Shevlyakov,
``On the choice of an optimization criterion under uncertainty in
 interval computations - nonstochastic approach'', {\it These Proceedings}.

\bibitem{Shevlyakov2}
 G. L. Shevlyakov, N. O. Vilchevskiy,
``Robust minimax adaptive approach to regression problems in interval
 computations'', {\it These Proceedings}.

\bibitem{Smith}
 S. Smith et al,
``In Case of Interval Uncertainty, 
 Optimal Control is NP-Hard Even for Linear Plants, so Expert Knowledge
 is Needed'', {\it These Proceedings}.

\bibitem{Solak}
 W. Solak,
``A remark on power series estimations via boundary corrections with
 parameter'', {\it These Proceedings}.

\bibitem{Sommerer}
 W. Sommerer and M. Kerbl,
``Rendering swept volumes using interval methods'', {\it These
Proceedings}.

\bibitem{Starks}
 S. Starks,
``An interval approach to congestion control in computer networks'',
{\it These Proceedings}.

\bibitem{Trejo}
R. Trejo and A. I. Gerasimov,
``Choosing interval functions to represent measurement inaccuracies:
group-theoretic approach'', {\it These Proceedings}. 

\bibitem{Turksen}
 I. B. Turksen,
``Interval valued fuzzy sets and measures'',
{\it These Proceedings}.

\bibitem{Villaverde}
 K. Villaverde et al, 
``Parallel algorithm that locates local extrema of a function of one
 variable from interval measurement results'', {\it These
Proceedings}.

\bibitem{Wadsworth 1990}
H. M. Wadsworth, Jr (editor). {\bf Handbook of statistical
methods for engineers and scientists}, McGraw-Hill Publishing Co.,
N.Y., 1990. 

\bibitem{Walster1}
 G. W. Walster,
``Connections between statistics, interval analysis and global
optimization'', {\it These Proceedings}.

\bibitem{Walster2}
 G. W. Walster,
``Stimulating hardware and software support for interval arithmetic'', 
{\it These Proceedings}.

\bibitem{Wang}
 M. C. Wang, K. Lin, and W. Kennedy,
``Self-validating computation for selected probability functions'',
{\it These Proceedings}.

\bibitem{Wiener 1914}
N. Wiener, ``A contribution to the theory of relative position'',
{\it Proc. Cambridge Philos. Soc.}, 1914, Vol. 17, pp. 441--449.

\bibitem{Wiener 1921}
N. Wiener, ``A new theory of measurement: a study in the logic of
mathematics'', {\it Proceedings of the London Mathematical Society}, 1921,
Vol. 19, pp. 181--205. 

\bibitem{Wu}
 Kung Chris Wu,
``Interval methods in mobile robot control'',
{\it These Proceedings}.

\bibitem{Zrilic}
 G. D. Zrilic,
``Computations based on delta-modulation representation of measurement
 results'',
{\it These Proceedings}.

\bibitem{Zuo}
Qiang Zuo, ``Description of Strictly Monotonic Interval 
AND/OR Operations'', {\it These Proceedings}.

\bibitem{Zuo2}
Qiang Zuo et al, ``In expert systems, even if we fix AND/OR operations, 
a natural answer to a composite query is the
interval of possible degrees of belief'', {\it These Proceedings}. 

\bibitem{Zyuzin1}
 V. S. Zyuzin, O. V. Mushtakova,
``A posteriori estimation of the solution of system of ordinary
 differential equations with the help of Taylor series'',
{\it These Proceedings}.

\bibitem{Zyuzin2}
 V. S. Zyuzin, E. A. Novikova,
``A method for estimating the solution of ordinary differential equation
 system by interval Taylor series'',
{\it These Proceedings}.

\end{thebibliography}

\end{document}