From oljlemon@cogsci.ed.ac.uk Sun Dec 17 13:55:24 1995
Received: from deacon.cogsci.ed.ac.uk by moose.cs.indiana.edu
	(8.7.1/IUCS.1.39) id NAA08179; Sun, 17 Dec 1995 13:55:09 -0500 (EST)
Received: from burns.cogsci.ed.ac.uk (burns.cogsci.ed.ac.uk [129.215.144.4]) by deacon.cogsci.ed.ac.uk (8.6.10/8.6.12) with SMTP id SAA13138 for <ITALLC96@cs.indiana.edu>; Sun, 17 Dec 1995 18:55:01 GMT
Date: Sun, 17 Dec 95 18:54:55 GMT
Message-Id: <24721.9512171854@burns.cogsci.ed.ac.uk>
From: Oliver Lemon <oljlemon@cogsci.ed.ac.uk>
Subject: ITALLC96 Submission
To: ITALLC96@cs.indiana.edu
Status: RO

\documentclass[epsf,twoside,makeidx,harvard]{article}
\usepackage{palatino}
\usepackage{fancyheadings}
\pagestyle{myheadings}
\markboth{ITALLC'96 abstract: Oliver Lemon \& Ian Pratt: ``Putting Channels on the Map'' }{ITALLC'96 abstract: Oliver
  Lemon \& Ian Pratt: ``Putting Channels on the Map''} 

% top margin0.75 in, botton margin 1.5 in
\textheight=9.75in
\topmargin=-0.2in


% left margin 1.5 in, right margin 1 in
\textwidth=6.3in
\oddsidemargin=-0.1in 
\evensidemargin=0.2in 
\marginparwidth=0.85in

%\textwidth=14cm
%\textheight=23cm

\newcommand{\ewh}[3]{\setlength{\epsfxsize}{#2}\setlength{\epsfysize}{#3}
  \epsfbox{#1}}
\newcommand{\ew}[2]{\setlength{\epsfxsize}{#2}\epsfbox{#1}}
\newcommand{\eh}[2]{\setlength{\epsfysize}{#2}\epsfbox{#1}}
\input{epsf}

\title{{\sc ITALLC '96 abstract:}\\ Putting Channels on the Map:
  \\imperfect information flow in a formal
  semantics of (Geo)graphical Information Systems\footnote{ This research is supported by the Leverhulme Trust.     The ``map semantics'' homepage can be found at : http://www.cs.man.ac.uk/ai/oliver/mapsem.html
 }}


\author{Oliver Lemon:  lemonoj@cs.man.ac.uk\\Ian Pratt:  ipratt@cs.man.ac.uk\\ http://www.cs.man.ac.uk/ai/oliver/mapsem.html\\ Department of Computer Science\\
  University of Manchester, Oxford Road,\\ Manchester M13 9PL\\ Tel:
  0161-275-6178 }
\date{}

\begin{document}

\maketitle
\newcommand{\wthen}{\;\mbox{then}\;}
\newcommand{\wor}{\;\mbox{or}\;}
\newcommand{\wand}{\;\mbox{and}\;}
\newcommand{\wsuchthat}{\;\mbox{such that}\;}
\newtheorem{thm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{ex}{Example}
\newtheorem{fact}{Fact}


{\bf Keywords}: map-like representations, formal semantics, channel
theory, versimilitude, error, Geographical Information Systems (GIS)

\begin{abstract} This paper falls into two parts.  First, a formal
  semantics for a wide class of graphical representations, exhibiting
  error and approximation, is given in
  terms of  Channel Theory (suitably modified).  The second part of the paper
  applies this formal framework to the semantic analysis of
  representations and algorithms in an actual information processing
  system: the  ``{\sc
  Arc/Info}'' Geographical Information System\footnote{ The first
 author would like to thank Carl Vogel and Rodger Kibble for helpful discussions.}.\end{abstract}

 A systematic  account is sought of the  ways in which graphical information systems represent the world. 
A formal semantics of graphical representations requires a full
understanding of representational systems in general -- a theory of representation. The specific type of graphical representation under scrutiny is that of 
``map-like representations'' (MLRs).    MLRs  exhibit  concrete and
complex phenomena for which   a theory of representation should
  account.  The special characteristics of MLRs  are outlined, and a variety of possible
formal semantics for them is  investigated.  Two central issues are
raised in this context:  the ``nearness to truth'' (verisimilitude) or
approximation behaviour of MLRs and the variety of errors that they
can exhibit.  An ``approximation'' semantics for MLRs is provided,
which relies on a formal account of error based on Channel Theory as a
theory of representation.
Channel theory is argued to be  the
most promising current formal framework  in which to
discuss such complex representations, and  consideration of MLRs
brings about some modifications and enhancements of the theory.
A novel variety of semantics is constructed, which incorporates the
``approximation'' behaviour of MLRs  as well as a variety of
error phenomena.  It is argued that such a ``qualitative'' semantics is not only 
applicable to MLRs, but also to some cases of linguistic representation. 
 

In contrast to some some related research into graphical
systems(see eg: \cite{allbar93})
(which concentrate on abstract formal systems) we focus upon a specfic practical application of such representations:
the  Geographical Information System ``{\sc Arc/Info}''.  Actual
map-processing algoritms are described in terms of the formal
framework constructed in the first part of the paper, and classified
with respect to their effect on the verisimiltude and error properties
of the
resulting representations.

\section{Graphical Representation and Imperfect Information
  Flow}

Representational systems  are a focus  of  study in  the search for an
understanding of the ``logic'' of imperfect information flow.  Systems
exhibit imperfections in  information flow when the  conventions which
allow  them to  be  informative are also able to   admit of exceptions, whence
mis-information.  Real representations,  in particular maps, are often
(in fact, nearly always)  imperfect, but they are  more often than not
good {\it enough} for most  purposes.  Just because,  say, a map  puts
one  tree out of place, that does  not render it useless;  so to dismiss all
maps   as  misrepresentations would be    rash.  A suitable  theory of
representation  will describe such imperfections and exceptions,
and account for the superiority  of some representations over
others. 

Graphical representations differ  from other  representational systems
(for example, Natural  Languages)  in that they are  non-ambiguous, in
the   sense that they do  not  admit of  any vagueness.  As argued in
\cite{stenob92}, for example,  graphical
systems exhibit {\it specificity}.


\subsection{Map-like Representations (MLRs)} Maps
and map-like representations differ from other graphical systems, such
as diagrams, in the following characteristic ways:
\begin{enumerate}
\item Referentiality: maps typically have  parts of the actual
  world as their subject matter.

\item Totality:  MLRs are complete -- they do  not
  support  partial  information\footnote{There  are partial  maps,  of
  course, but they are not the object of study here.}.
\item Errors/exceptions:    maps  exhibit a   wide   variety of  error
  phenomena.
\item Approximation   to  truth   (verisimilitude):  maps   are rarely
  actually  true of  any region, but  are  more or  less similar to
  it.

\item Negation by omission:  lack of a  symbol at a  certain location
  supports  negative information  about  that location\footnote{Again,
  this is  due to a  restriction to  total maps.  Partial  maps do not
  have this property.}.
\end{enumerate}

  \begin{defn} A
 MLR
 consists of a set of typed and  located symbols (icons, points, areas, shapes,
 lines).  MLRs are total, and may exhibit representation errors with
 respect to some regions under some interpretations. \end{defn}  

  MLRs constitute rich and
 complex representational   systems.   As    such they exhibit    many
 interesing phenomena for any candidate theory of representation to cover.


MLRs are also interesting  in virtue of the types  of information
which they  do {\it  not}  explicitly carry:   universal, conditional,
negative, and disjunctive information are all either implicit in a map
(ie: an  agent has to reason about  the map to derive such statements;
one cannot draw a map  of ``All the houses  are on the north island'',
for  example),  or are completely  absent.   This  is  really  due to  the
specificity  property of graphical representations;  one is forced, in
conveying any information at all, to make  a specfic committment about
the location of a particular type of  object.

Of  the above properties, the  imperfect information flow phenomena of
error and approximation are the focus  of this paper, since they raise
a challenge for  any  candidate theory   of representation.   The first of the above  properties (referentiality)
brings to  light the 
importance  of a  {\it  semantics}  for MLRs; they   are  one  of  the  most
commonplace   and effective  ways    by  which  agents  convey and manipulate
information about their environments.  A semantics for MLRs and their
processing allows the {\it correctness} and {\it completeness} of map-processing algorithms in
Geographical Information Systems (GISs) to be evaluated.


\subsection{Verisimilitude}
Map-like representations are seldom completely faithful to the
structures which they are intended to represent.  Nevertheless, they
approximate those structures closely enough to be useful for a wide
range of practical purposes.  \\
 
The semantics for such representations should, then, reflect the fact
that they approximate ``the truth'' (also treated as a representation) to differing degrees.  In order to
give such a grade of ``versimilitude'' it is necessary to quantify
over the various  types of {\it errors} in a representation.  Those
representations 
with less errors, relative to the structure to be represented, obviously
exhibit greater verisimilitude.


\subsection{Seven types of Error}

Maps commonly exhibit  the following  kinds of errors\footnote{Sources
  of error are  temporal change, scaling, digitising, initial measurement error,
  projection.} (for some   literature  on map error,  see  \cite{hs91,ecsd}):

\begin{enumerate}
\item Depiction of non-existent objects;  eg: a tree is depicted where
  there is not one in reality.
\item  Non-depiction of (existing) objects; eg: the  non-appearance of
  secret government installations on maps.
\item ``Thematic'' error (incorrect taxonomy); eg: a castle depicted as
  a church.
\item Locative error; eg: an  object depicted as  being in a different
  place to that which it actually inhabits.
\item  Plan error (incorrect depiction  of  shape); eg: depiction of a
  square house as circular.
\item Overgeneralisation   (depiction of  a group   of objects  as one
  object); eg: depiction of a group of trees as a forest region.
\item Undergeneralisation (depiction of one  object as a collection of
  objects); eg: depiction of a city as a group of buildings.
\end{enumerate}  This classification of error is, as yet, non-formal.
It is not  clear, for  example, whether  or not there  is some overlap
beteeen the categories  given above (3 could  be seen as a combination
of 1 and 2, for example).  Indeed, a satisfactory taxonomy of error in
MLRs can only be given on the basis of a formal theory of representation.  

 Errors  are measured  with respect  to some   geographical region, of
 which  it is assumed  there is a  correct  precise description, under
 some taxonomy.  Thus, the measurement of error in a representation is
 relative to  a  ``world  state'' 
 which is treated  as another representation (the ``true description''
 of a region.)

Having  given some account of the  nature of map-like representations,
and   the   particular   problems encountered  in   formulating  their
semantics,  it seems  that a  clear  understanding of representational
systems in general is required.  But what requirements  ought a good theory of
representation to meet? 

\section{Desiderata on a Theory of Representation}
A good theory of representation, which is  the basis of a semantics of
maps and other graphical representation systems, should have at least
the following qualities.  A theory of representation should:
\begin{enumerate}

\item Describe the relationship between a representation,
  interpretational conventions, and the structure which is being
  represented.
 
\item  Account for the full variety of errors that are possible in a
  given 
  class of representation.

\item  Account for the stability of representational systems under error.

\item Account for the different quality of different representations under different interpretations.
\item Be sufficiently formal to admit of logical and mathematical analysis.
\end{enumerate}

Bearing these issues in mind, in the full paper the range of current varieties of formal
semantics is explored, with regard to their putative application in  a
semantics of map-like representations.

\section{Towards a Formal Semantics of MLRs}
Could there be a  ``cartographic semantics'' --  a theory which would
 set out and  systematize  the  principles  according to which    maps
 represent the  world?   A  formal semantics    of maps and   map-like
 representations was the subject of the pilot study \cite{mapsem}.  That project is
 enhanced by the insistence that a formal semantics of maps needs to be   built    upon a  general  account   of
 information and  representation, and in particular, the notions of
 verisimilitude and error which are crucial for a measure of representation quality. \\ A
 semantics of maps\footnote{To begin with, two candidate approaches can be ruled out fairly
quickly; the theory of semiotics, perhaps best represented in relation
to graphics by \cite{bertin}, and the theory of ``qualitative spatial
representations'' currently espoused by \cite{hern94}, amongst others.
Both of 
these approaches are criticized for their lack of semanticity; that
is, they are not truly semantical systems in the first place, in that
they fail to describe any systematic relationship between
representations and reality.}
  operates at the point  where each token object has
 been associated with some type; that  is, where each object in the map
 is classified  as  being a  symbol  of some  type (eg:  church, lake,
 road.)  Thus, as far as a semantics is concerned, {\it abstract maps}
 (ie:  maps where   each symbol token  is    typed) are  the  focus of
 attention.  The  process of  map interpretation  whereby  each symbol
 becomes typed is an interesting one, but not one  which is the task
 of      a semantics (this    is    a  lower-level  problem of   image
 interpretation,  see   eg: \cite{rm89}).     


\subsection{A ``Naive'' approach: truth-conditional semantics}
Systems already exist whereby the
meaning of a graphical representation (commonly, a geometric or
set-theoretic diagram) is given by its truth-conditions
with respect to a model.  In this case  the set of claims made by a
MLR would be
taken to constitute a complete ``theory'' in the logical sense; a deductively
closed set of sentences.  A complete theory is true with respect to a
particular model (or ``possible world'') which supports the
propositions in the theory (see eg:\cite{worboys}).  \\
The systems of the collection  \cite{allbar93}, for example,  are  distinctly in
this vein, concentrating on truth-conditional semantics of geometric
systems.  Note that all of the systems considered in that collection
have entirely abstract semantics, in that they do not have any
real-world situations as their subject matter.\\
In \cite{rm89}, for example,  simple maps are   treated as sets of sentences in first-order logic, along with specific background knowledge axioms which embody map information constraints\footnote{For example,\\
$\forall x,y (river(x) \wedge river(y) \Rightarrow \neg cross(x,y))$
\\
$\forall x (shore(x)  \Rightarrow loop(x))$}.


A simple map semantics takes each map to be a set of claims about a
region, expressed as a set of propositions.  The map is true if and
only if  all its claims are true.  Thus the {\it meaning} of a map (on
this construal) is
the ``way the region would be like'' if the map were true, so that  the content of a map is its truth-conditions.

Using this approach, the semantics of maps is exactly that of sets of
sentences in predicate logic.  There is nothing characteristically
``graphical'' about the semantics; the problem reduces to that of  a translation task.  
Given the earlier discussion, it seems clear that such approaches fail
to address the issues of error and approximation which are central to
a semantics of MLRs.

Various alternatives (eg: Situation Semantics) to the strictly
classical approach are explored in the full paper, and are shown to
lack the resources with which to deal with error and verisimilitude.


\subsection{Approximation semantics}
What has been found lacking in the above accounts is any way of dealing with
the two central issues in map semantics: approximation to the truth
(or verisimilitude), and error.  An ``approximation
semantics\footnote{see \cite{phd} for a similar approach in relation
  to Revisable Paraconsistent theories.}'', where
representations are graded in virtue of their ``closeness to the
truth'',  is
developed in order to tackle the first of these issues. However, the
issue of error is implicit in such a semantics, for  in order to
give a verisimilitude measure for representations a systematic account of error becomes
essential.
 
There follows a basic map semantics (see figure \ref{mlr}), in which measures of completeness
and accuracy of a representation are evaluated.\\
\begin{figure}
         \begin{center}
         \leavevmode
         \epsfbox{mlr.eps}
         \end{center}
         \caption{MLR approximation semantics }
\label{mlr}
\end{figure}
The system takes map-points $ X$ and symbols/icons $S$ as primitives;
a map $M$ is a subset of $\langle X, S \rangle$\\
A function $l:S \rightarrow {\cal P} (X)$ locates each symbol in the map (symbols
can overlap).\\

Models are of the form $\langle  L, D, \Gamma \rangle$, 
where $ L$ is a set of real locations, \\
$D$ is a domain of real objects (a region under some geographical
classification), and 
$\Gamma: D \rightarrow L$ locates each individual in the region
(individuals may overlap)\footnote{Think of FOL domains where all individuals have a location.}\\

$I$ is an interpretation function such that:\\
$I:S \rightarrow {\cal P} (D)$\\
$I:X \rightarrow L$\\

The semantic value of a map $M$ under interpretation  $I$ is given by; \begin{defn}

${\rm Val} (M, I)= min_{\pi \in \Pi} {\rm Val}(M, I, \Pi)$ \\

where $\Pi$ is a set of functions $\pi: S \rightarrow D \cup \{\omega\}$

and  $ \omega$ is an  ``undefined'' individual (dealing with non-existent objects in
the representation).\\
 ${\rm Val}(M, I, \Pi)$ is a parameterized set of error measures on the
map $M$ under the interpretation $I$:
\\


 ${\rm Val}(M, I, \Pi)= \alpha\Sigma_{s \in S  / D} d(s) + \beta
 \Sigma_{s \in D / S} d(s) + \gamma 
 \Sigma_{s \in S} d(s, \pi (s) )$\\

The function $d(s)$ returns the size\footnote{The radius.} of the omitted or non-existent
symbol $s$, while $d(s,t)$ gives the distance between two symbols.
$\alpha, \beta, \gamma $ are parameters allowing the importance of
certain types of error to be varied according to context.
\end{defn}

  These error measures quantify over
mistakes of omission, mistakes of non-existence, and mistakes in
location.  Thge best interpretation of the map can thus be evaluated
as the one which provides the least error measure.   The semantic value of the
representation is then the error value of the minimally mistaken mapping of map objects ($S$)
to individuals in the model ($D$).

Thus the representation $M$  is evaluated  under different interpretations (different associations of symbols with real objects, and map locations with real locations).

The ``errors of omission'' measure provides a way of evaluating the
quality of the representation with respect to its completeness.
The quantity of individuals in the model (the ``represented world'') which are not
associated with any symbol provides a measure of how well the map
covers its subject matter.

The above account requires supplementation by  a rigorous account of
errors in representation systems.  Just such an account is provided,
in part, by description of representation systems provided by Channel
Theory.

\section{Channel Theory as a Theory of Representation}
Channel Theory is a general mathematical account of the types of
 information flow which occur in all kinds of contexts: logics,
 languages, and representation systems as diverse as X-rays, radar
 screens, thermometers, photographs, and maps.

 Channels are taken to connect {\it
  classification domains} (parts of the world under certain
taxonomies) to other classification domains.  A ``map channel'' is an example of a representational
channel (see eg: \cite{barsel94}, page 23.)  Classifications $C= \langle S, T, \models
\rangle$, consist of typed tokens, while  ``channels'' link types and
tokens across these classifications, by way of ``indicating'' and
``signalling'' relations respectively.

The formal tools of CT allow a rigorous taxonomy of error in
representational systems in general.  CT's account of exceptions to
regular information flow is seen to underwrite the approximation
semantics given above (in the sense that a verisimilitude measure must
be based upon a rigorous theory of error in representations).  \\
``Channels'' link situation types by  supporting constraints between
situations.  There are, presumably, a variety of  ``mapping'' channels
$c_m$, linking maps (map-type situations) $M$  with regions
(geographical situations) $R$ by way of ``mapping constraints''.
Token symbols $m \in M $ are called  ``signals''  for  token objects
$r \in R$, relative to a channel $c$, and the tokens $r$  are called
``targets''  for the symbols $m$.  Thus,   tokens (symbols) in $m$ indictate tokens (geographical objects) in $r$. 

\begin{defn}  A representational system is a structure $\langle C_1, c, C_2
\rangle$, consisting of two ``classifications'' $(C_1, C_2)$  and a
``channel'' ($c$). 
\end{defn}

\begin{defn}
A classification domain $\langle S, T, \models \rangle$ is a set $T$
of types, $S$ of tokens, and a classification relation $\models$
between them. 
  
\end{defn}
\begin{defn}A channel consists of indicating relations $\Rightarrow$
  between types $T_n \in T$,
  and signalling relations $\mapsto$ between tokens (or ``sites'')
  $s_n \in S$\end{defn}



 Thus  $s_1 \models T_1$ states that token $s_1$ is of type $T_1$; for example
 ``Symbol-x is a castle-symbol''.  Channels are typed by indicating relations, so that $c \models T_1 \Rightarrow T_2$ states that channel $c$ is of the type which supports that constraint.\\
Signalling relations are relativised to channels, so that $s_1
\mapsto_c s_2$ states that site/token $s_1$ is a signal for $s_2$ (the
``target'') relative to channel $c$.

 
 Think of these  classifications as
``representing'' and ``represented'' worlds respectively, and the
channel as a set of interpretational conventions (indicating
relations) and an interpretation (signalling relations: an association of representing  tokens with represented tokens).
Thus, keeping conventions (the indicating relations) static, different interpretations of the
representation can be given by varying the way its tokens are
associated with those of the represented world (varying the signalling
relations).  On the other hand,
keeping the represented and representing worlds static, different
interpretational conventions (channels) can be evaluated.

\subsection{A Channel Theoretic Approximation Semantics of MLRs} The first classification in a 
semantics of MLRs is  an image  interpretation taxonomy:
associating token 
marks-on-paper with symbol types.  The ``map channel'' associates
token icons with objects in the region, and icon types with
(geographical) object types.  Thus the second classification is of
objects in a region by geographical type.  Each of these
classifications  is {\it total} (tokens which are not positively typed for some
type are negatively typed for it; if a symbol is not classified as a
castle-symbol then it is typed as a non-castle symbol.)  Each token is
allowed to have one and only one positive type.

Here the account of error provided by standard CT is extended in order
to deal with the range of errors occurring in real map-like
representations.  Later it will be shown that this framework provides
a semantics for actual map-processing algorithms in a GIS.\\
Maps
are specifically mentioned (along with blueprints, photographs,
x-rays,   and radar screens) as imperfect information systems, in
\cite{selbar93}. 

For example,
\begin{quote}
``Consider the radar screen with one blip caused by a sunspot.  The positions of the other blips correctly indictate the position of planes in the sky, so there is a sense in which the radar screen is [a] reasonably good representation of the sky, despite the errant blip.  Likewise, the photo of Claire's yard represents the area as being  hilly and wooded, and it is right; but it shows a tree which has been removed since the photo was taken.  It would be quite wrong to say that the photo no longer represents the yard, or even that it is a misrepresentation.'' (page 22, \cite{barsel94})
\end{quote}
Here it is shown that an  account of error based on  CT as a 
provides a detailed approximation semantics for MLRs.

 Thinking about the types of errors which crop up in a semantics of maps brings to light new issues for the taxonomy of exceptions in Channel Theory.
The idea of ``approximation semantics'' is to quantify over the number
of pseudo-signals and other errors that a map contains and give a
measure of MLR quality. 

  The following error definitions are
routine from CT (see eg: \cite{bar92}):
\begin{defn}\\

Channel $c \models T_1 \Rightarrow T_2$ has a  ``pseudo-signal'' $s_1$ iff  $s_1 \models T_1$ but there is no $s_2$ such that $s_1 \mapsto_c s_2$.\\
\end{defn}

\begin{defn}
Channel $c \models T_1 \Rightarrow T_2$ has a  ``multi-signal'' $s_1$ iff  $s_1 \models T_1$ and there is more than one  $s_i$ such that $s_1 \mapsto_c s_i$.\\
\end{defn}
\begin{defn}
Channel $c \models T_1 \Rightarrow T_2$ has a  ``clear signal'' $s_1$
iff  $s_1 \models T_1$ and there is a unique $s_i$ such that $s_1
\mapsto_c s_i$.


\end{defn}

These definitions correspond to (1) a map which can  depict non-existent
objects, (2) a map exhibiting  a symbol which refers to a variety of
different objects (under-specification), and (3) a map with a symbol which refers to one and
only one object in the world.  In other words, these definitions cover
the cases of non-existent objects, ambiguity of symbol interpretation,
and an ``ideal'' symbol respectively.
\begin{ex}Take the channel $c$ and the region $R= \langle S_R, T_R, \models_R \rangle$ to be constant, and consider different MLRs  $m=\langle S_m, T_m, \models_m \rangle$.\\

$s_1 \models_m T_1$ states that icon $s_1$ is of type $T_1$, for
example that icon 1 is a castle-type icon.  Assume that $c$ supports
that $T_1 \Rightarrow T_2$ and $ s_1 \mapsto_c s_2$, and that $s_2 \models_R T_2$, ie: castle-type icons are linked to castle-type objects, and that icon 1 is linked to object 2, and that object 2 is a castle-type object.  \\

Imagine now that icon 3 is also a castle-type icon, but that it is not
the signal of any target ie: that it is not associated with any
object-token in the region.  Then, $s_3 \models T_1$, but there is no
$s_4 \wsuchthat s_3 \mapsto_c s_4$.  Then $s_3$ is an exception in the
map, or a pseudo-signal. \end{ex}


However, consideration of map errors brings to light the following new
definitions, covering errors of taxonomy, object ommission, and 
under-generalisation (over-specificity):

\begin{defn}
Channel $c \models T_1 \Rightarrow T_2$ has a  ``null-signal'' $s_2$
iff  $s_2 \models T_1$ but there is no $s_1$ such that $s_1 \mapsto_c
s_2$
\end{defn}
\begin{defn}
Channel $c \models T_1 \Rightarrow T_2$ has a  ``classification
error'' $s_2 \models T_2$ iff  $s_1 \models T_1$ and  $s_1 \mapsto_c
s_2$ and $T_1 \Rightarrow T_2$ but $s_2 \not \models T_2$
\end{defn}
\begin{defn}
Channel $c \models T_1 \Rightarrow T_2$ has a  ``multi-target'' $s_2$ iff  $s_2 \models T_2$ and there is more than one  $s_i$ such that $s_i \mapsto_c s_2$

\end{defn}
 

  Note that all the errors  accounted for so far here are {\it
  non-locative} (5 of the 7 types of error mentioned above have been formulated).  The modification of CT so as to model such errors
  will be presented shortly.

Table \ref{errs} summarises:
\begin{center}
\begin{tabular}{||r|l||}
\hline
{\bf MLR errors}  & {\bf Channel exceptions} \\
\hline\hline
non-existent objects & pseudo-signals\\\hline
object ommission & null-signals\\\hline
under-specification & multi-signals\\\hline
over specification & multi-targets\\\hline
thematic error & classification error\\
\hline

\end{tabular}
\label{errs}
\end{center}


Channel Theory can easily be extended so as to deal with the phenomena
of locative and ``plan'' errors.  The modification constitutes a
non-trival addition to the CT armory of semantical devices.

\subsection{Locative Error Detection in Channel Theory}

In order to record locative error (and its close cousin, plan error)
in CT, furnish channels with structured sets of types\footnote{It
  would be interesting to explore this in relation to Seligman's  ``perspectives''.} for locations.

Thus denote the set of location types in the ``representing world'' or
MLR by  $l_1
\ldots l_n$.  Denote the set of location types in the geographical
classification by $L_1 \ldots L_N$.

Then $s_1 \models l_1$ states that symbol/site $s_1$ is classfied as
being at location $l_1$.  Now assume that a ``Map Channel'' contains
indicating reltions which systematically connect location
types in the MLR to location types in the geographical
classification.  In the simplest case, assume that $n=N$ (the map and
 ``world'' classification contain the same number of locations), and
 that there is a 1-1 mapping between them which preserves the topology
 of the spaces in the obvious way (eg: if $L_1$ is right of $L_2$ and
 $c: l_1 \Rightarrow L_1$ and $c: l_2 \Rightarrow L_2$, then $l_1$ is
 right of $l_2$)\footnote{One could imagine some strange variations
   here, possibly corresponding to certain projections.}.    This
 highlights the point that the location types have to be structured in
 a certain way, so that topology can be manipulated. 

Now measure locative error in the following way:
impose a distance metric $\delta(L_1, L_2)$ between location types internal to
classifications.  This function can be defined in respect of the
toplogical structure on the types (ie: assuming that all locations are
connected,  count the locations in the
shortest path between $L_$ and $L_2$.).

Then define the locative error of a signal $s_1$ to be the distance
between its location and the map-location of the target for which it is a
signal.  \begin{defn}
Where $s_i \models $l_i$ , $s_i
\mapsto s_x$,\\ $c: l_i \Rightarrow L_i$,\\ $c: l_x \Rightarrow L_x$, and
$s_x \models L_x$\\

$Loc-error_c s_i = \delta (l_i, l_x)$

\end{defn}

Locative error is thus a quantitative kind of classification error,
where the degree of error is measured with respect to the (topological)
structure on
the types.  See diagram \ref{lect}.  Plan errors can also be accounted
for in this way.
\begin{figure}
         \begin{center}
         \leavevmode
         \epsfbox{lect.eps}
         \end{center}
         \caption{Locative error in Channel Theory }
\label{lect}
\end{figure}



\section{Information  Quality}
The approximation semantics requires that maps can be judged more or
less ``good'' maps of a given region, relative to a given channel.  In
other words, the quality of each representation as a representation of
a region under certain interpretation   conventions, can be measured.



The quality of a representation $M$, with respect to a channel $c$  of interpretive conventions and the classification $R$ which it is a representation of, is given below:
\begin{defn}(Information Quality)\\where $M$ is a classification, $c$
  a channel, and $R$ a classification.\\The error of $M$ with respect to
 $ R$ under $ c$  is given by: \\

$error(M, c, R) = \alpha_1 ps(M) + \alpha_2  ns(M) + 
\alpha_3  ce(M) + \alpha_4  ms(M) + \alpha_5  mt(M) + \alpha_6 le(M)$\\

where $ps(M)$ gives the number of pseudo-signals in $M$ (with respect
to $c \wand R$), $ns(M)$ gives the number of null-signals in $M$, and
so on for classification errors ($ce(M)$), multi-signals ($ms(M)$),
and multi-targets ($mt(M)$) in
$M$.  Finally, $le(M) $ gives the sum of all locative errors in $M$.\\


$\alpha_1 \ldots \alpha_6$ are natural numbers, taken as  parameters
reflecting practical importance of certain types of error relative to
task.  Assume for now that $\alpha_1 = \ldots =\alpha_6 = 1$ \\

then,  $IQ(M,c,R)= \frac{ 1 }{ 1 + error(M,c,R)}$
\end{defn}
Note that $0 < IQ(M,c,R) \leq 1$\\
Representations (classifications) can  then be ordered with respect to
how well they represent a given classification under a certain
metric.  An {\it optimal representation} (non-unique) is given by the 
minimization of all errors over representations with respect to one
channel.
The best interpretation of a given representation is given by the
minimization over errors relative to different channels (where both
signalling and indicating relations are changeable.)



It is now  shown  that notions from CT, involving the ``dynamics''
of classifications and channels,
 prove useful in the semantical analysis of actual map processing
algorithms  in a current GIS.

\section{Application: The ``{\sc Arc/Info} '' Geographical Information System}
Maps figure among the wide variety of representations processed by computer
systems. In particular, map-like representations play a central role in
geographical information systems (GISs), which are now used for a wide range
of commercial and scientific purposes.  Centrally, a GIS is a system for
storing and processing spatially related data, of which cartographic
information (in the form of electronic maps) is an important part.
 The computer processing of
map-like representations is also important within AI and
robotics.
 As attempts are made to integrate different
spatial reasoning algorithms (e.g. algorithms for map-acquisition,
map-updating and route-planning) into such autonomous systems, methods for
assessing the individual effectiveness and reliability of those algorithms
will become crucial.




{\sc Arc/Info} is a GIS which processes information, computed from
digitised maps,  in the form of  toplogical relations between arcs,
points and regions (polygons consisting of arcs) representing
geographical regions.  The system performs map-processing  algorithms which
manipulate information contained in  collections of such structures.  Representations consist of points (nodes)
and  lines (arcs)  between them (these are the ``sites'' or tokens of
the MLR), along with their topology (the location structure on the types).  The data structures employed also
incorporate ``thematic'' information about what type of feature the
particular nodes and arcs represent (the unstructured types of the
MLR).     Many 
of 
the 7 types of errors discussed
above are actually exhibited in the ARC/INFO system. \\
  The system employs the following
map processing algorithms, which (informally) have the following effects:

\begin{itemize}
\item CLEAN: creates topology for arcs, polygons, and arc
  intersections.   Removes certain errors from the map (deletes ``dangles''
  and fills ``gaps'' in arcs by creating new points).
\item OVERLAY: superimposes two maps by combining their  topology in a
  composite map\footnote{There are 3 types of overlay: UNION,
  INTERSECT, and IDENTITY.  The first two have their intuitive
  meanings, while IDENTITY restricts the superimposition to the
  boundary of the smaller map.}.

\item APPEND: integrates separately digitised adjacent maps.

\item  RESELECT: restricts the map to representing only certain types of features.

\item BUFFER: restricts the map to representing features only within a
  specified distance of some point, arc, or region.

\item RECLASSIFICATION: assigns a new attribute value (type) to  specified features.

\item DISSOLVE: removes boundaries between regions of the same type.  
\end{itemize}
Various combinations of these processes can be used to
perform complex  analytical operations on maps.  A formal semantics for these
processes describes how they affect the accuracy of the resulting
MLRs.

Some of these  algorithms can be described  as changes in classification
domains under a constant channel, while others are describable in
terms of operations over channels themselves (combining different
channels in particular ways).

Different types of error can be removed in different ways.  For
example, (some) non-existent objects are removed by CLEAN simply by removal
of the offending nodes and arcs (CLEAN removes those arcs which ``dangle''
a certain specified small  amount over other arcs).  In terms of CT this
algorithm 
can be described as removal of certain tokens from the representing
classification.   CLEAN also removes some errors of omission from
maps, by filling in gaps between points which are below a specified
distance apart.    Classification errors can be corrected by the
RECLASSIFY and DISSOLVE algorithms.  The  CLEAN
algorithm also computes the topology of a map (the structure on the
location types of tokens) from the positions of points and arcs in the
digitisation.  These operations, then, actually construct the
classifications (the MLRs) in which we are interested.  In this sense,
they actually perform a lower-level process of classification, or
representations, construction.  However, CLEAN also has other virtues,
which can be described at the level of transformations over
classifications (``Classification Dynamics'').  Other operations
can be described as computing  functions over channels too.  The table
\ref{ctarc} summarizes some of these operations.

 \begin{center}
\begin{tabular}{||r|l|}
\hline
{\bf ARC/INFO algorithms}  & {\bf Channel and Classification dynamics}
\\
\hline\hline
CLEAN & deletion of pseudo-signals and null-signals \\\hline
APPEND& token, type, and location-type  extension of map
classification \\\hline
OVERLAY& parallel channel composition  \\\hline
BUFFER & removal of tokens with respect to location-type  \\\hline
RECLASSIFY & changing the classification relation within the classification       \\\hline
DISSOLVE & removal of tokens with respect to topology\\\hline
RESELECT & removal of  tokens with respect to their type in map classification
\\
\hline

\end{tabular}
\label{ctarc}
\end{center}
In the full paper
these algorithms are further classified by their effect on the
information quality measure (IQ)
of the resulting representations.  For example, OVERLAY invokes
parallel composition of two MLRs (unioning the sets of types, tokens, and
indicating and signalling relations with respect to an identity
relation on location types), and  combines the
errors in both the MLRs over which it operates, thus increasing the
error of the new representation.  However, it is shown that this error
this error is bounded by
the sum of the errors of the two original MLRs.  Thus the Channel
Theoretic Approximation Semantics provides a way of checking the
{\it correctness and completeness} of map-processing algorithms\footnote{A semantics based on the ideas in this paper has been shown to
preserve accuracy of route planning algorithms in maps consisting of
convex objects, subject to the types of error discussed above (Pratt
and Lemon 
in preparation).}. 

\section{Concluding remarks}
Maps have specfic characteristics  which make them an interesting  test-bed for any
candidate theory of representation.  A variety of systems for a semantics for maps are
appraised with respect to two crucial properties of graphical
representations: verisimilitude and error.
An approximation version of modified CT is developed and a formal semantics of
MLRs is  developed.   The approximation and error semantics developed here may
well have implications for semantics of other types of
representations; specifically those employed in NL discourse (it seems
clear that linguistic representations exhibit approximation and error phenomena).  
The issues raised in the paper are:
\begin{itemize}
\item The nature of (carto)graphic representations.
\item The links between semantics, imperfect information flow, and
  real  representation systems .
\item Approximation and error measures  in formal semantics.

\item developments and modifications of Channel Theory. 
\item The application of a formal theory of information flow to an actual information
  processing system.
\item The validation of algorithms employed in GIS using a channel
  theoretic semantics.
\end{itemize}


\bibliographystyle{harvardbib}
\bibliography{map}

\end{document}