\documentstyle[IEEEtran]{article}
\begin{document}
\tolerance 10000
\title{Choosing Interval Functions To Represent Measurement
Inaccuracies: Group-Theoretic Approach}
\author{Raul Trejo$^1$ and Andrei I. Gerasimov$^2$} 

\pagestyle{myheadings}

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

\maketitle

\auffil{The authors are with 
$^1$Sistemas de Informacion,
Division de Ingeneria y Ciencias,
ITESM (Instituto Technologico de Monterrey),
Campus Estado de Mexico,
Apdo. Postal 2,
Modulo de Servicio Postal,
Atizapan, Mexico 52926,
email rtrejo@campus.cem.itesm.mx, and with 
$^2$Penza State Technical University, Penza, Russia.}

\section{Formulation of the Problem}
\subsection{We Need Error Estimates}
Measurements are not 100\% accurate. The manufacturer of a measuring
instrument usually supplies us with the guaranteed upper bound
$\Delta$ on the measurement error. As a result, if the measurement
result is $\tilde x$, then we are guaranteed that the actual value $x$
of the measured quantity lies in the {\it interval} 
${\bf x}=[\tilde x-\Delta,\tilde x+\Delta]$. 

The bound may be applicable for all $\tilde x$, or different measurement
error bounds may be described for different values $x$ of the measured
quantity: $\Delta=\Delta(\tilde x)$. In this case, we have an {\it
interval function} ${\bf x}(\tilde x)=[\tilde x-\Delta(\tilde x),
\tilde x+\Delta(\tilde x)]$. 

In some cases, we also know the {\it probabilities} of different
values of error (and therefore, of different values inside the
interval $\bf y$). However, in many real-life cases, we do not know
these probabilities, and the interval is the only information that we
have. 

\subsection{How Are Error Bounds Determined?} 
From the viewpoint of the user, as soon as the dependency
$\Delta(\tilde x)$
is supplied, the problem of describing the possible error 
is thus solved. But the manufacturer still needs to determine it,
i.e., to {\it calibrate} his measuring instrument. 

To calibrate an instrument, we must measure the same set of quantities
by using two different measuring instruments:
\begin{itemize}
\item the calibrated one, and
\item a more precise one that is used as a {\it standard}.
\end{itemize}
If the second instrument is much more accurate than the calibrated
one, then we can neglect the measurement errors of the second
instrument, and treat the results of its measurements as the actual
values of $x$. Then, the difference between the results of
measuring the same quantity by these two instruments can be treated as
the measurement error of the first instrument $\Delta x=\tilde x-x$.
For the same input value, if we repeat the measurements many times,
with varying conditions, then we will get several possible values of
error $\Delta x$. If we have made sufficiently many calibrating
measurements, that lead to different values $\Delta x_1,...,\Delta
x_N$, then we can safely take the largest value $\max|\Delta x_i|$ as
the desired estimate $\Delta(\tilde x)$. 

\subsection{The Problem}
Ideally, we should repeat this procedure for every $\tilde x$, and get
the desired function. In reality, however, 
we can only do it for finitely many values $\tilde x_1,...,\tilde
x_n$. 
Therefore, we
only get finitely many value $\Delta(\tilde x_1), ..., \Delta(\tilde
x_n)$.  From finitely many values, we
can only determine finitely many numerical characteristics of the 
desired function $\Delta(\tilde x)$. 
If we do not restrict our class of functions a
priori, we will not be able to determine the desired interval function
uniquely, because one needs {\it infinitely many} parameters to
determine a function (in mathematical terms, the set of all functions
is {\it infinite-dimensional}). 

So, in order to complete the calibration, 
we need to choose a {\it finite-dimensional}
family of interval functions. Then, we will determine its parameters
from the measurement results. 
Therefore, we arrive at the following 
problem: {\it to choose a finite-dimensional family
of interval functions.}

\section{Main Idea: Describing Measurement Transformations}
To choose an appropriate family of interval functions, we will use two
ideas:
\begin{itemize}
\item First, an interval function can be viewed as a {\it set} of
functions: $${\bf f}(x)=[f^-(x),f^+(x)]=$$ $$\{f(x)\,|\,f(x)\in
[f^-(x),f^+(x)]{\rm \ for\ all \ }x\}.$$ 
So, to describe interval functions, we will first describe
the elements functions. 
\item To describe these possible functions, we will 
take into consideration the fact that inside the
measuring instrument, there usually is a sequence of {\it measurement
transformations}: e.g., from temperature, we go to current, and then
from current, to numbers; usually, there are more stages (this idea
was first described and used in \cite{Gerasimov 1989}).  
\end{itemize}
So, the desired function is a {\it composition} of several measurement
transformation functions.

The class $F$ of all possible measurement transformations must thus have
the following properties:
\begin{itemize}
\item If a function 
$a \rightarrow r(a)$ is a measurement transformation (from a stage 
$A$ to some other stage $B$), and a function $b \rightarrow s(b)$ is
a measurement transformation, then we can combine these two
transformation and get a measurement transformation that is equal to
the composition of $r$ and $s$. 
So, it is reasonable to demand that 
the class $F$ of all measurement 
transformations must be closed under composition.
\item Suppose that $a \rightarrow r(a)$ is a non-trivial 
measurement transformation. The goal of the measurement is to
reconstruct the original value $a$. Therefore, in order to use the
transformation $a\to r(a)$ in the measuring instruments, we must 
be able to reconstruct $a$ from the result of the transformation. In
other words, we must have an {\it inverse} transformation $r^{-1}$
that transforms $r(a)$ back into $a$ in our
family $F$. 
\smallskip

\item[]{\it Comment.} Thus, the family $F$ must contain the inverse of
every function that belongs to it, and the composition of every two
functions from $F$. In mathematical terms, it means that $F$ must
be a {\it transformation group}.  
\smallskip

\item We have already mentioned that we want the family of
transformations $F$ to depend on finitely many parameters.
In mathematics, the
notion of a group whose elements are continuously depending on
finitely many parameters is formalized as the notion of a
(connected) {\it Lie group}. So, we conclude that measurement
transformations must form a connected Lie group. 

\item There are example of reasonable measurement transformations:
\begin{itemize}
\item[$\bullet$]In many cases, we need an 
{\it amplification} of the input signal is $a\to ka$
for a constant $k$;
\item[$\bullet$]In many real-life situations, there is a constant
additive noise. To get rid of this noise, we must {\it subtract} its
value from the signal. The corresponding measurement transformation is
$a\to a+C$ for some constant $C$.
\end{itemize}
So, the set of measurement transformations must contain all 
functions of the type $a\to ka$ and $a\to a+C$. 
\end{itemize}

So, the set $F$ of all measurement transformations is a finite-dimensional
Lie group that contains all function of the type $a\to ka$ and $a\to
a+C$ (since $F$ is a group, it will also contain all linear
transformation $a\to ka+l$ for $k>0$). 

Such sets have been described in mathematics. 
Namely, the problem of classifying all 
finite-dimensional transformation groups of an $n$-dimensional
space $R^n$ (where $n=1,2,3,...$) that include a sufficiently big
family of linear transformations, was formulated by N. Wiener
(see, e.g., \cite{Wiener 1962}). Wiener also formulated a hypothesis that was
confirmed in \cite{Guillemin 1964} and \cite{Singer 1965}. 
It turned out that for $n=1$, only
two groups are possible: 
\begin{itemize}
\item the group of all linear transformations
and 
\item the group of all fractionally linear transformations $$a\to
{k_1a+l_1\over k_2a+l_2}.$$ 
\end{itemize}
In both cases, all elements from $F$ are fractionally linear. So, we
can conclude that {\it every measurement transformation from a class
$F$ is fractionally linear}. 
\smallskip

\noindent{\it Comments.}

1. A
simplified proof of the general theorem 
for $n=1$ is given in \cite{Kreinovich 1987}. 

2. In \cite{G1,G2,Gerasimov 1989}, we have shown that fractionally-linear
transformations are indeed a good description of measurement
transformation of the actual sensors (at least locally).

3. This result can be viewed as a {\it limit theorem} for
transformation functions \cite{Gerasimov 1989} 
(similar to limit theorems from mathematical
statistics cite{G54,AZ88}). Indeed:
\begin{itemize}
\item In statistics, we describe random variables that
can be represented as a sum of many small components. 
\item Here, we want to describe transformations that can be
represented as a composition of many transformations that are small in
the sense that they practically do not change the value $f(x)\approx
x$.
\end{itemize}
In statistics, to describe the desired class of variables, we consider
probability distributions that are {\it infinitely divisible}, i.e.,
that can be represented as a sum of arbitrarily 
small components. 
Similarly, we want to describe the limit family of the transformations that can
be this represented in the above-described composition form 
with component transformations that are arbitrarily close to 0. 
The classification only makes
sense if we have a {\it finite-dimensional} family of limit
transformations. It is easy to argue that 
this limit family must be invariant w.r.t.
composition and inversion, and that it must contain linear
transformations. So, this limit family must be a finite-dimensional
Lie transformation group that contains linear transformations. Hence, 
due to the above-mentioned result, this family
must consist of fractionally linear transformations only.  

4. For other
applications of this result, see 
\cite{Kreinovich 1990,Corbin 1991,Kreinovich 1991,Kreinovich 1991a,Kreinovich 1992a}. 

\section{Final Result: Describing Interval Functions}
Now that we know how to describe {\it individual} 
measurement transformations, we can
describe {\it sets} of these transformations, i.e., desired {\it
interval functions.}

The main idea here is that the only information that we have about the
errors are the intervals. We do not know anything about the possible
correlation between the intervals that correspond to different values
of $\tilde x$. So, if for some value $\tilde x$, the error takes the
largest possible value $\Delta(\tilde x)$, it is still possible that
for other value of the input signal, the error will also take the
largest possible value. In other words, we assume that the function
$f^+(\tilde x)=
\tilde x+\Delta(\tilde x)$ is a {\it possible measurement transformation}. 

Similar arguments lead us to a conclusion that the function 
$f^-(\tilde x)=\tilde x-\Delta(\tilde x)$ (that describes the largest possible
{\it negative} errors) is also 
a {\it possible measurement transformation}. 

So, the desired interval function ${\bf x}(\tilde x)$ has the form 
$[f^-(\tilde x),f^+(\tilde x)],$ where $f^\pm$ are measurement
transformations. 

We already know that measurement transformations are
fractionally-linear functions. So, we arrive at the following
conclusion:
{\it measurement inaccuracies must be described by the interval
functions of the type $[f^-(\tilde x),f^+(\tilde x)],$ where both
functions $f^\pm$ are fractionally linear}.

This result is in good accordance with the experimental data about
sensors. 

\begin{thebibliography}{99}

\bibitem{AZ88} T. V. Arak, A. Yu. Zaitsev, {\bf Uniform limit theorems for
sums of independent random variables}
(Proceedings of the Steklov Institute of
Mathematics, Vol. 174), American Mathematical Society,
Providence, RI, 1988.

\bibitem{Corbin 1991}
J. Corbin and V. Kreinovich, {\bf Dynamic tuning of
communication network parameters: why fractionally linear formulas
work well,} University of Texas at El Paso, Computer Science
Department, Technical Report UTEP-CS-91-4, June 1991. 

\bibitem{G1} A. I. Gerasimov and V. Kreinovich, {\bf Piecewise-
fractionally-linear approximation}, Leningrad Polytechnical
University and
National Research Institute for Scientific and Technical
Information (VINITI), 1988, 15 pp. (in Russian) 

\bibitem{G2} A. I. Gerasimov and V. Kreinovich, {\bf On the
problem of optimal approximation choice for
metrological characteristics}, 
Leningrad
Polytechnical University and National Research Institute for
Scientific and Technical Information (VINITI), 1988, 13 pp. (in
Russian). 

\bibitem{Gerasimov 1989}
A. I. Gerasimov and V. Kreinovich, {\bf On the foundations of scaling
theory}, Leningrad Technical University and National Research
Institute for Scientific and Technical Information (VINITI), 1989,
Publication No. 7661-B89, 51 pp. (in Russian).


\bibitem{G54} B. V. Gnedenko and A. N. Kolmogorov, {\bf Limit distributions
for sums of independent random variables}, Addison-Wesley, Cambridge,
1954. 

\bibitem{Guillemin 1964}
V. M. Guillemin and S. Sternberg, ``An algebraic model of
transitive differential geometry'', {\it Bull. Amer. Math. Soc.}, 1964,
Vol. 70, No. 1, pp. 16--47. 

\bibitem{Kreinovich 1990} 
V. Kreinovich and S. Kumar, ``Optimal choice of
$\&$- and $\vee$-operations for expert
values,'' {\it Proceedings of the 3rd
University of New Brunswick Artificial Intelligence Workshop,}
Fredericton, N.B., Canada, 1990, pp. 169--178.

\bibitem{Kreinovich 1991} 
V. Kreinovich and S. Kumar. ``How to help
intelligent systems with different
uncertainty representations communicate with each other,'' 
{\it Cybernetics and Systems: International
Journal}, 1991, Vol. 22, No. 2, pp. 217--222. 

\bibitem{Kreinovich 1991a} 
V. Kreinovich and C. Quintana, ``Neural networks: what
non-linearity to choose?'', {\it Proceedings of the 4th University of New
Brunswick Artificial Intelligence Workshop}, Fredericton, N.B.,
Canada, 1991, pp. 627--637.

\bibitem{Kreinovich 1992a}
V. Kreinovich, C. Quintana, R. Lea, O.
Fuentes, A. Lokshin, S. Kumar, I. Boricheva, and L.
Reznik, ``What non-linearity to choose? Mathematical foundations of
fuzzy control,'' {\it Proceedings of the 1992 International
Conference on Fuzzy Systems and Intelligent Control,} Louisville,
KY, 1992, pp. 349--412.

\bibitem{Kreinovich 1987}
I. N. Krotkov, V. Kreinovich, and V. D. Mazin,
``General form of measurement transformations which admit
the computational methods of metrological analysis of measuring-
testing and measuring-computing systems,'' {\it Izmeritelnaya
Tekhnika}, 1987, No. 10, pp. 
8--10 (in Russian); English translation: {\it Measurement
Techniques}, 1987, Vol. 30, No. 10, pp. 936--939.

\bibitem{Singer 1965} 
I. M. Singer and S. Sternberg, ``Infinite groups of Lie
and Cartan, Part 1'', {\it Journal d'Analyse Mathematique}, 1965, Vol. XV,
pp. 1--113.

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

\bibitem{Wiener 1962}
 N. Wiener, {\bf Cybernetics, or Control and Communication in
the animal and the machine}, MIT Press, Cambridge MA, 1962.    

\end{thebibliography}
\end{document}