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 ; 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
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}