%% for Latex-2e
\documentclass[11pt]{article}
\usepackage{a4wide}

%\setlength{\textwidth}{6.8in}
%\setlength{\oddsidemargin}{-0.2in}
%\setlength{\topmargin}{-0.5in}
%\setlength{\textheight}{9.4in}


\newcounter{bean}
\newenvironment{tightenumerate}{
                \begin{list}{
                  {\mbox {\it
		      \arabic{bean}.\/}}}{\usecounter{bean}
                      \setlength{\itemsep}{0pt}\setlength{\topsep}{0pt}}}{
                \end{list}}

\newcommand{\andsign}{\land}

\newcommand{\link}{\mbox{$\rightarrow$}}          % constraint link
\newcommand{\Link}{\mbox{$\; \Rightarrow \;$}}    % channel link
\newcommand{\impl}{\mbox{$\supset$}}                     % implication
\newcommand{\refines}{\mbox{$\; \preceq \; $}}
\newcommand{\rrefines}{\mbox{$\; \succeq \; $}}
\newcommand{\seqcomp}{\mbox{$\, ; \,$}}              % sequential compostion
\newcommand{\parcomp}{\mbox{$\, \parallel \, $}}     % parallel
                                                     % composition
\newcommand{\parmeet}{\mbox{$\, \bigtriangleup \, $}}      % parallel meet
\newcommand{\parjoin}{\mbox{$\, \bigtriangledown \, $}}    % parallel join
\newcommand{\contra}[1]{\mbox{$#1^{*}$}}
\newcommand{\dparcomp}{\mbox{$\; \Join \; $}}    % double parallel compositn
\newcommand{\slink}{\mbox{$\stackrel{\mbox{!}}{\rightarrow}$}} % absolute link
\newcommand{\abslink}{\mbox{$\stackrel{\mbox{!}}{\rightarrow}$}} %
                                                         % absolute link
\newcommand{\tuple}[1]{\mbox{$\langle #1 \rangle $}}     % tuples
\newcommand{\subtype}{\mbox{$\subseteq $}}               % subtype
\newcommand{\entails}{\mbox{$\; \geq \;$}}               % entails
\newcommand{\signals}[3]{\mbox{$ #2 \stackrel{#1}{\mapsto} #3 $}}

\newcommand{\carries}{\mbox{$\; \mid\!\vdash \; $}}  % carries info ||-
\newcommand{\supports}{\mbox{$\; \models \;$}}
\newcommand{\notsupports}{\mbox{$\; \not\models \;$}}
\newcommand{\restrict}[2]{\mbox{$#1 \downarrow #2$}}
\newcommand{\dual}[1]{\mbox{$\overline{ #1 }$}}
\newcommand{\infon}[1]{\mbox{$\ll #1 \gg$}}
%\newcommand{\1}[1]{\mbox{{\em 1\/}}}
\newcommand{\ldown}[2]{\mbox{$left(#1)^{\orsign}(#2)$}}
\newcommand{\rdown}[2]{\mbox{$right(#1)^{\orsign}(#2)$}}
\newcommand{\lup}[2]{\mbox{$left(#1)^{\andsign}(#2)$}}
\newcommand{\rup}[2]{\mbox{$right(#1)^{\andsign}(#2)$}}
\newcommand{\linkup}[1]{\mbox{$#1^{\andsign}$}}
\newcommand{\linkdown}[1]{\mbox{$#1^{\orsign}$}}
\newcommand{\bifunct}{\mbox{$\; \stackrel{\rightarrow}{\rightarrow} \;$}}

%% Following used in qualification.tex and causation.tex

\newcommand{\subclass}{\mbox{$\; \sqsubseteq \;$}}      % subclassification
\newcommand{\strsubclass}{\mbox{$\; \sqsubset \;$}}     % strict subclass
\newcommand{\restriction}{\mbox{$\; \angle \;$}}           % restriction
\newcommand{\subchannel}[1]{\mbox{$\; \sqsubseteq_{#1} \;$}} % subchannel
\newcommand{\strsubchannel}[1]{\mbox{$\; \sqsubset_{#1} \;$}} % strict subchanl
\newcommand{\sublink}[1]{\mbox{$\; \preceq_{#1} \;$}}   % sublink
\newcommand{\typeord}[1]{\mbox{$\; \leq_{#1} \;$}}      % type-ordering
\newcommand{\contains}{\geq}
\newcommand{\sigs}[1]{\signals{}{#1}{#1}}
\newcommand{\condseq}{\, ; \,}
\newcommand{\condpar}{\, \parallel \,}
\newcommand{\consq}{\mid\sim}
\newcommand{\bottom}{\, \bot \,}
\newcommand{\suchthat}{\mbox{$~\mid~$}}



\newcommand{\HV}{H\&V}
\newcommand{\BS}{B\&S}
\newcommand{\calig}[1]{\mbox{${\cal #1}$}}
\newenvironment{definition}{\noindent {\bf Definition\/}\begin{em}}{\end{em}}
\newenvironment{myquote}{\begin{list}{}{\setlength{\topsep}{0pt}}
                          \item
                       }{\end{list}}
\newcommand{\SB}{{\em S\&B\/}}

\newenvironment{tightitemize}{
                \begin{list}{$\bullet$}{
                    \setlength{\itemsep}{0pt}}{\setlength{\topsep}{0pt}}}{
                \end{list}}


\title{A Channel Theoretic Model of Situated Default Reasoning \\
  (extended abstract)}
\author{Lawrence Cavedon\\ \\
  Department of Computer Science\\
  Royal Melbourne Institute of Technology\\
  GPO Box 2476V\\
  Melbourne 3001\\
  Australia\\ \\
  Email: {\tt cavedon@cs.rmit.edu.au}\\
  Fax: (+61 3) 9662-1617}


\parskip .1 in
\parindent 0.0 in

\begin{document}

\thispagestyle{empty}
\maketitle



\newpage
\setcounter{page}{1}

\pagestyle{plain}
\pagenumbering{arabic}

\input{transfig}


\noindent
\Large {\bf A Channel Theoretic Model of Situated Default
  Reasoning}\footnote{Much of the work described here was performed
  during the author's time as a student in the Centre for Cognitive
  Science, University of Edinburgh and has greatly benefited from
  discussions with Robin Cooper.}


\bigskip
\large
{\sc Lawrence Cavedon}\\
Dept. of Computer Science, R.M.I.T.\\
LaTrobe St, Melbourne Australia\\
{\tt cavedon@cs.rmit.edu.au}


\normalsize



\section{Introduction}


Defeasible reasoning is a central topic in Artificial Intelligence
(AI), and has also received much recent attention in philosophy and
formal semantics. Typically, this process involves reasoning with {\em
  incomplete information\/}---an agent leaps to some conclusion based
on the information she has, whereas a different conclusion would be
reached if more information about her situation was known. Procedures
for default reasoning often involve some form of ``internal
consistency check''---the potential conclusion is accepted only if it
is consistent with the information the agent has available to her. For
example, if the agent knows that Tweety is a bird, then (in the
absence of information to the contrary) the agent will conclude that
Tweety can fly; if on the other hand she knows additionally that
Tweety is a penguin, then she will instead be led to the conclusion
that Tweety {\em cannot\/} fly.


In this abstract, we outline a process whereby such defeasible
reasoning is grounded in {\em situated\/} regularities. Such a
regularity is one which is not applicable (i.e. cannot be relied upon)
in all situations, but rather is only reliable in certain
circumstances. The defeasible inference process involves an agent
choosing an appropriate regularity as carefully as possible (given
certain information) and drawing conclusions based on this. For
example, when reasoning about a general bird, an agent may choose to
use the regularity ``Birds fly''; however, when reasoning about a
penguin, then a more appropriate regularity is ``Birds which aren't
penguins fly''.\footnote{There may be other even more appropriate
  regularities.  This particular choice reflects the specific
  behaviour of the model described below.}


In order to model this process, we use Barwise and Seligman's
\cite{barwise-seligman,maths-info} (henceforth \BS) {\em channel
  theory,\/} a recent mathematical theory of information flow that
models many important features of information, such as the fallibility
and situation-dependence of natural regularities. These natural
regularities underly information-flow and, consequently, inference.
Previous work \cite{cavedon-glasbey-hungary,cavedon-glasbey-acten} has
investigated the use of channel theory as a semantic model for generic
sentences, which are clearly related to the default reasoning process.
Further, the particular model described below is founded on a channel
theoretic model of conditional logic \cite{cavedon-cond}---this model
involves modifying \BS's operations on channels so as to account for a
regularity's ``implicit background assumptions'' in such a way that
does not require such assumptions to be represented in the channel
supporting that regularity.


This new perspective on defeasible reasoning seems to offer the
possibility of significant computational advantages. The consistency
checking is the source of major computational complexity in standard
default reasoning methods. The methodology outlined below allows the
agent to reason {\em monotonically\/} using approximate rules. The
problem then shifts to choosing the most appropriate version of a rule
(i.e. based on the situation the agent finds itself in). The
computational issues are outlined below---such issues are discussed
further in the full paper, as is an application of the methodology to
AI's {\em qualification problem\/} (i.e. the problem of specifying
implicit assumptions behind rules for reasoning about the effects of
actions).\footnote{Bouquet and Giunchiglia \cite{giun-qualification}
  have formulated a related approach to the qualification problem.}




\section{Channel Theory}


In this section, I briefly review the basics of {\em channel
  theory,\/} \BS's theory of information flow; see
\cite{barwise-seligman,maths-info} for further details.  Channel
theory is concerned with {\em natural regularities,\/} informational
relationships between entities and types which give structure to the
world.\footnote{Channel theory evolved from an attempt to rectify
  problems with the situation theoretic account of {\em conditional
    constraints.\/}} A somewhat problematic property for such
regularities is that they can be both ``reliable'' (i.e. useful for
inference) yet fallible (i.e. may admit exceptions). Such properties
are, of course, required of the semantic objects used to model generic
sentences. \BS\/ resolve the problem by ensuring that relationships
between the tokens of the theory play an important role---i.e. it is
not just the regularity between types that counts, but also the
connections between individuals that are classified by those types,
and the way in which these connections are classified as instances of
the general regularities.


These (fallible) regularities underly inference performed by an agent.
However, by shifting the fallibility onto the regularities themselves,
we obtain a different perspective on default reasoning---i.e. each of
the default regularities are {\em bona fide\/} regularities, even
though they allow exceptions. (This is an important consideration when
discussing the semantic content of generic sentences.\footnote{The
  channel theoretic view of generics provides other benefits, as
  discussed by Cavedon and Glasbey
  \cite{cavedon-glasbey-hungary,cavedon-glasbey-acten}.}) This differs
from the usual view of default reasoning, by which it is an {\em
  agent\/} that is fallible---the agent only uses approximations of
``true'' inference rules, based on her information. The channel
theoretic view more closely conforms to a notion of situated
cognition, whereby the agent makes use of regularities that best suit
her embedding circumstances.


\subsection{Classifications}


A classification is a structure that carves up (part of) the world
into {\em tokens\/} and assigns various {\em types\/} to these tokens.


\begin{definition}
  A {\em classification\/} $A$ is a structure
  \tuple{tok(A),typ(A),:_A^+,:_A^-} consisting of a set of {\em
    tokens\/} $tok(A)$, a set of {\em types\/} $typ(A)$ and relations
  $:_A^+ , :_A^-$ on $tok(A) \times typ(A)$. For $t \in tok(A)$ and
  $\phi \in typ(A)$, we say $t$ is {\em classified positively (resp.,
    negatively) by $\phi$ in $A$\/} if $t :_A^+ \phi$ (resp., $t :_A^-
  \phi$) holds.\footnote{I will usually drop the subscripts $A$ when
    this causes no confusion.}
\end{definition}


The tokens of a classification may be objects, individuals,
situations, or even other classifications, while the types are
properties appropriate for classifying (along some dimension) these
tokens. A classification can be seen as a representation of
information of a particular sort. This representation is highly
relativistic---intuitively, one could view a classification as being
relativised to a specific agent, epistemic state, point of view, or
perspective on the world.


I assume throughout that the set of types of a classification $A$ has
internal structure: in particular, $typ(A)$ is closed under
type-conjunction, type-disjunction, and type-negation operations,
denoted $\land , \lor , \neg$ respectively. I assume these
operations to satisfy certain standard properties. Since for each
$\phi \in typ(A)$ there is a corresponding $\neg\phi \in typ(A)$
satisfying $t :^+ \neg\phi$ iff $t :^- \phi$, I write $t :^+ \phi$
simply as $t : \phi$ and $t :^- \phi$ as $t : \neg\phi$. The types are
ordered under a {\em type-entailment\/} relation $\typeord{A}$,
satisfying some obvious properties with respect to the type
operations.  Type-entailment constrains the classification relation in
the following way: if $t : \phi$ and $\psi \typeord{A} \phi$ then $t :
\psi$.  There is also a {\em type-conflict\/} relation $\bottom_A$ on
$typ(A)$, involving the expected associated interaction with the
classification relation and with type-entailment (e.g.: if $\phi
\bottom_A \psi$ then not both $a : \phi$ and $a : \psi$ hold; $\phi
\bottom_A \neg\phi$).\footnote{All these concepts are more fully
  defined in the full paper. See also Seligman and Barwise
  \cite{maths-info}.}



\subsection{Channels}


A channel \calig{C} is basically a link between two classifications
$A$ and $B$, licensing the flow of information of some particular
sort.  Formally, a channel is itself a classification---the tokens of
\calig{C} are {\em connections\/} (each linking tokens of $A$ and
$B$).\footnote{Seligman and Barwise define a channel as consisting of
  a classification plus two functions that map the tokens and types to
  their ``endpoints'', i.e. tokens and types of the linked
  classifications. In general, one should not identify the tokens and
  types of a channel with the pairs of tokens and types from the
  linked classifications, as I do here---for example, there may be two
  distinct connections involving the same tokens. This problem is
  amplified in the presence of serial composition, below.  However,
  this abuse leads to significant simplification and abbreviation of
  the presentation. The full paper treats this matter more
  rigorously.}


\begin{definition}
  Let $A$ and $B$ be classifications. A channel $\calig{C} : A \Link
  B$ linking $A$ and $B$ is a classification
  \tuple{tok(\calig{C}),typ(\calig{C}),:}.\footnote{There should of
    course be two classification relations here; however, I do not
    make use of the negative classification relation here, so I will
    ignore it.} The tokens of \calig{C} are {\em connections\/},
  denoted \signals{}{s}{s'}, with $s \in tok(A)$ and $s' \in tok(B)$.
  The types of \calig{C} are {\em constraints\/}, denoted
  $\phi\link\psi$, with $\phi \in typ(A)$ and $\psi \in typ(B)$. \\
  I sometimes refer to \signals{}{}{} and $\link$ as {\em
    signalling\/} and {\em indicating\/} relations,
  respectively. Given a constraint $\gamma = \phi\link\psi$,
  $ante(\gamma)$ denotes $\phi$ and $succ(\gamma)$ denotes $\psi$.
\end{definition}


Intuitively, a channel $\calig{C} : A \Link B$ regulates the flow of
information between $A$ and $B$. The type-token distinction allows a
characterisation of different sorts of ``erroneous'' information
flow.


\begin{definition}
  Let $\calig{C} : A \Link B$ be a channel and $s$ a token such that
  $(s : \phi)$ holds in $A$. $s$ is a {\em pseudo-signal\/} if there
  is no connection $(\signals{}{s}{s'}) \in tok(\calig{C})$.
  Alternatively, if there {\em is\/} a connection $(\signals{}{s}{s'})
  \in tok(\calig{C})$ and a constraint $(\phi\link\psi) \in
  typ(\calig{C})$ such that $(\signals{}{s}{s'} : \phi\link\psi)$ does
  {\em not\/} hold in \calig{C}, then $\signals{}{s}{s'}$ is said to
  be an {\em exception\/} in \calig{C}.
\end{definition} 


Pseudo-signals and exceptions are two different ways in which we can
model the failure of a channel to support ``expected'' information
flow. These concepts are discussed in more detail in the full paper.


\subsection{Operations on channels}


There are various operations that can be applied to channels,
resulting in more complex channels that supports more complex
information flow. Given channels $\calig{C}_1 : A \Link B$ and
$\calig{C}_2 : B \Link C$, we can {\em serially compose\/} them to
obtain a channel that classifies information flow from $A$ to
$C$.\footnote{Serial composition is the channel-theoretic concept
  supporting Dretske's {\em Xerox Principle\/} \cite{dretske-info}.}


\begin{definition}
  Given connections $\signals{}{s}{s'} ,
  \signals{}{s'}{s''}$ and constraints $\phi\link\psi ,
  \psi\link\tau$, let $(\signals{}{s}{s'} \seqcomp
  \signals{}{s'}{s''})$ be the connection \signals{}{s}{s''} and
  $(\phi\link\psi \seqcomp \psi\link\tau)$ be the constraint
  $\phi\link\tau$. The (standard) {\em serial composition\/} of
  channels $\calig{C}_1 : A \Link B$ and $\calig{C}_2 : B \Link C$ is
  the channel $(\calig{C}_1 \seqcomp \calig{C}_2) : A \Link C$ such
  that
  \begin{tightenumerate}
  \item $tok(\calig{C}_1 \seqcomp \calig{C}_2) = \{ (\signals{}{s}{s'}
    \seqcomp \signals{}{s'}{s''}) \suchthat \signals{}{s}{s'} \in
    tok(\calig{C}_1) \mbox{ and } \signals{}{s'}{s''} \in
    tok(\calig{C}_2) \}$;
  \item $typ(\calig{C}_1 \seqcomp \calig{C}_2) = \{ (\phi\link\psi
    \seqcomp \psi\link\tau) \suchthat \phi\link\psi \in
    typ(\calig{C}_1) \mbox{ and } \psi\link\tau \in typ(\calig{C}_2)
    \}$;
  \item the classification relation of $(\calig{C}_1 \seqcomp
  \calig{C}_2)$ is the smallest relation such that\\
  \indent
  $~~~~~~~(\signals{}{s}{s'} \seqcomp \signals{}{s'}{s''}) : (\phi\link\psi
    \seqcomp \psi\link\tau)$ holds in $(\calig{C}_1 \seqcomp \calig{C}_2)$
    if\\
  \indent
  $~~~~~~~\signals{}{s}{s'} : \phi\link\psi$ holds in $\calig{C}_1$ and
    $\signals{}{s'}{s''} : \psi\link\tau$ hold in
    $\calig{C}_2$.\footnote{This last case can be stated a lot more
      succinctly in the absence of the aforementioned conflation
      between a connection and the pair of tokens it connects.}
  \end{tightenumerate}
\end{definition}


Serial composition is the only channel operation defined in this
abstract. The full paper considers other operations, namely {\em
  parallel composition\/} and {\em contraposition\/} (see
\cite{barwise-sta3}). These operations lead to a calculus which can be
used to model complex patterns of reasoning. (This is expanded upon in
the full paper.)


Cavedon \cite{cavedon-cond} has shown that the standard channel
operations are unsuitable for some tasks. In particular, Cavedon shows
that to obtain a suitable logic of conditionals, the channel
operations must be modified so as to take account of the ``implicit
background assumptions'' of a channel. Cavedon achieves this via a
{\em subchannel\/} relation: channels are related by an ordering under
which $\calig{C}_1$ is a subchannel of $\calig{C}_2$ if $\calig{C}_2$
is somehow ``more reliable'' than $\calig{C}_1$, in that it has fewer
exceptions. The central definitions are the following:


\begin{definition}
  Classification\footnote{Recall that each classification $A$ has a
    type-entailment ordering $\typeord{A}$ associated with its
    types---$\phi\typeord{A}\psi$ if $\psi$ entails $\phi$.} $A$ is a
  {\em subclassification\/} of classification $B$, written $A
  \subclass B$, iff $tok(A) \subseteq tok(B)$, $typ(A) \subseteq
  typ(B)$, $\typeord{B}$ agrees with $\typeord{A}$ when restricted to
  $typ(A)$, and for each $a \in tok(A)$ and $\phi \in typ(A)$, $a :
  \phi$ holds in $A$ iff $a : \phi$ holds in $B$.
\end{definition}


\begin{definition}
  Let $\phi\link\psi , \phi'\link\psi'$ be constraints contained in
  channels $\calig{C} : A \Link B$ and $\calig{C'} : A' \Link B'$,
  respectively. We write $\phi\link\psi \typeord{(A',B')}
  \phi'\link\psi'$, {\em wrt \calig{C} and \calig{C'}\/},\footnote{I
    drop the reference to the specific channels when this causes no
    confusion.} if:
  \begin{tightenumerate}
  \item $A \subclass A', B \subclass B'$,
  \item $\phi \typeord{A'} \phi'$, and
  \item $\psi' \typeord{B'} \psi$.
  \end{tightenumerate}
\end{definition}


\begin{definition}
  Let $\calig{C} : A \Link B$ and $\calig{C'} : A' \Link B'$ be
  channels, and $f$ a function from $typ(\calig{C})$ to
  $typ(\calig{C'})$.  We say \calig{C} is a {\em
    $\typeord{(A',B')}$--subchannel\/} of \calig{C'} {\em wrt $f$\/},
  written $\calig{C} \subchannel{(f,A',B')} \calig{C'}$, if
  \begin{tightenumerate}
  \item $A \subclass A' , B \subclass B'$;
  \item $tok(\calig{C}) \subseteq tok(\calig{C'})$;
%  \item for all $c \in tok(\calig{C'})$,
%    $left(\calig{C'})^{\orsign}(c) = left(\calig{C})^{\orsign}(c)$ and
%    $right(\calig{C'})^{\orsign}(c) = right(\calig{C})^{\orsign}(c)$;
  \item for all $c \in tok(\calig{C})$ and $\gamma \in
    typ(\calig{C})$, if $c : \gamma$ in \calig{C} then $c :
    f(\gamma)$ in \calig{C'};
  \item for all $\gamma \in typ(\calig{C})$,
    $\gamma \typeord{(A',B')} f(\gamma)$ wrt \calig{C} and
    \calig{C'}.
  \end{tightenumerate}
  We write $\calig{C} \subchannel{(A',B')} \calig{C'}$ if there exists
  an $f$ such that $\calig{C} \subchannel{(f,A',B')} \calig{C'}$.
\end{definition}


In the above definition, \calig{C'} (i.e. the superchannel) is meant
to be seen as a sort of ``refinement'' of \calig{C}, in that
\calig{C'} deals with the same sort of information flow as \calig{C},
but is ``more discriminatory'' (in that it deals with a richer set of
types---this is modelled by the requirement that $A$ and $B$ are
subclassifications of $A'$ and $B'$) and therefore more reliable.
Note that the definition ensures that exception-hood is preserved
downward---any connection that is an exception in \calig{C'} {\em
  must\/} be an exception in \calig{C} (so long as that connection is
a token in \calig{C}).


The subchannel ordering allows the background assumptions of a channel
\calig{C} to be captured {\em without\/} representing them within
\calig{C} itself. Rather, such assumptions are represented in the
relationship between \calig{C} and other channels. Further,
\calig{C}'s assumptions need not be completely represented in any
single channel---they are distributed throughout a hierarchy of
channels ordered by subchannel.  (See
\cite{cavedon-cond,cavedon-thesis} for other properties of the
subchannel ordering.) Given a subchannel hierarchy that encodes the
background assumptions of the channels therein, the operations on
channels can be modified so as to take these background assumptions
into account. For example, serial composition is modified as follows:


\begin{definition}
  Suppose we have channels $\calig{C}_1 : A \Link B$ and $\calig{C}_2
  : B \Link C$, with $\phi\link\psi \in typ(\calig{C}_1)$ and
  $\psi\link\tau \in typ(\calig{C}_2)$. The {\em conditional serial
    composition\/} of $\calig{C}_1$ and $\calig{C}_2$, denoted
  $(\calig{C}_1 \condseq \calig{C}_2)$, is the same as the standard
  serial composition of $\calig{C}_1$ and $\calig{C}_2$ except
  that $\phi\link\tau \not\in typ(\calig{C}_1 \condseq \calig{C}_2)$
  if there exist $\calig{C'}_1 , \calig{C'}_2$ such that
  \begin{tightenumerate}
  \item $\calig{C}_1 \subchannel{f_1} \calig{C'}_1$, $\calig{C}_2
    \subchannel{f_2} \calig{C'}_2$; and
  \item $ante({f_1}(\phi\link\psi))$ $\bottom$
    $ante({f_2}(\psi\link\tau))$.\footnote{For simplicity, we assume
      here that any background assumptions are represented in
      antecedents of superchannels. In general, this assumption is not
      necessary (see \cite{cavedon-thesis}).}
  \end{tightenumerate}
\end{definition}


By ensuring that a channel hierarchy satisfies certain weak
conditions, a channel theoretic logic of conditionals that satisfies
many important properties and supports powerful patterns of reasoning
is obtained (see \cite{cavedon-cond,cavedon-thesis} for details).



\section{Representing default rules in channel theory}


Our channel theoretic model of default reasoning uses constraints to
represent default rules. For example, the rule ``(by default) birds
fly'' is represented by a constraint of the form $bird \link flies$,
where $bird$ is a type that classifies birds and $flies$ is a type
that classifies things that can fly. Such a constraint is supported by
a channel \calig{C}, where \calig{C} contains a set of connections at
the token level. Some of these connections may be exceptions. Further,
there may be some tokens which are pseudo-signals and which therefore
are not involved in any connection. Pseudo-signals and exceptions in
\calig{C} represent birds which are in some way exceptional with
respect to the given default rule.


What the simple channel theoretic representation of fallible rules
does not impose is a sense of ``maximal normality'', i.e. that an
individual is assumed to be a ``normal'' representative unless there
is information to the contrary. For example, if we are told that
Tweety is a bird (and told nothing else) then we may conclude by
default that Tweety can fly. We need to define a suitable {\em maximal
  normality\/} condition that channels (arranged in a hierarchy) are
assumed to satisfy; i.e. we need a condition that minimises the
exceptions and pseudo-signals in a set of channels.


(In \cite{cavedon-thesis}, it is {\em information
  links\/}---structures that are based on but have less internal
structure than channels---that are assumed to be maximally normal (see
\cite{maths-info} for the definition of links; they are also discussed
in the full paper). In that model, it is the information links which
are used to model an agent's reasoning and so it is more natural to
modify the signalling relations of links rather than channels so as to
match an agent's ``expectations''. This is discussed in the full
paper, but we simplify the abstract by ignoring this issue in the
current setting.)


The maximal normality condition defined below interacts with a given
channel hierarchy. A particular channel hierarchy which is suitable
for reasoning about generics is defined in \cite{cavedon-thesis}---the
definition is reproduced in the appendix below. Briefly, this
definition constructs a channel hierarchy from a given collection of
channels (supporting constraints which represent default rules) by
checking for type-conflicts in consequents and inserting the duals of
the corresponding antecedents as implicit background assumptions. For
example, the consequents of $bird \link flies$ and $penguin \link \neg
flies$ conflict. Hence, $\neg penguin$ is inserted as a background
assumption to $bird \link flies$---this is achieved by creating a
channel \calig{C'}, supporting $bird \land \neg penguin \link flies$,
and inserting \calig{C'} into the channel hierarchy so that $\calig{C}
\subchannel{} \calig{C'}$, where \calig{C} supports $birds \link
flies$.\footnote{This construction has some similarities to Pollock's
  use of {\em rebutting defeaters\/} \cite{pollock-default}.} The
basic hierarchy thus obtained is illustrated in Figure
\ref{fig:penguin-ex}. The definition biases against inserting $\neg
bird$ as a background assumption of $penguin \link \neg flies$ because
a token's ``penguin-ness'' informationally implies its
``bird-ness''.\footnote{This is captured by the presence of a channel
  supporting $penguin \link bird$.} Using the channel operations
(modified to account for background assumptions), a powerful logic of
generics is obtained.



\begin{figure}[htb]
  \begin{center}
    \ \hrulefill\ 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% INPUT FIGURE HERE (penguin-ex.tex)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\mbox{\beginpicture
\setcoordinatesystem units < 1.000cm, 1.000cm>
\unitlength= 1.000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\plot  3.461 21.939  2.826 23.368 /
%
% arrow head
%
\plot  2.987 23.162  2.826 23.368  2.871 23.110 /
%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{rm}$\calig{C}_1 : bird \link flies$} [lB] at  2.350 21.463
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{rm}$\calig{C}_2 : penguin \link bird$} [lB] at  5.048 22.098
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{rm}$\calig{C}_3 : penguin \link \neg flies$} [lB] at  7.429 21.463
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{rm}$\calig{C'}_1 : (bird \andsign \neg penguin) \link flies$} [lB] at  1.556 23.527
\linethickness=0pt
\putrectangle corners at  1.556 23.940 and  7.429 21.463
\endpicture}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    \caption{Channel Hierarchy for Simple Penguin Example}
    \label{fig:penguin-ex}
    \ \hrulefill\ 
  \end{center}
\end{figure}



Having obtained a logic of generics, a logic for defeasibly reasoning
about the individuals (i.e. tokens) is obtained by defining a maximal
normality condition on the signalling relations of the channels of a
hierarchy\footnote{As pointed out above, this should really be on the
  signalling relations of the corresponding information links.} so as
to limit the number of possible pseudo-signals and exceptions. Such a
normality condition is defined with respect to a set $\Psi$ of
initially given information (i.e. a set of {\em Austinian\/}
propositions of the form $(t : \phi)$). To ensure {\em maximal\/}
normality, the only time that a pseudo-signal/exception should be
permitted is when one of the following conditions holds:
\begin{tightenumerate}
\item the given information conflicts with the information that would
  otherwise be inferred;
\item inheritance from separate premises would conflict.
\end{tightenumerate}
The second case is taken care of by referring to the channel hierarchy
since conflicting consequents lead to encoded background assumptions.
This leads to the following definitions. For simplicity, we assume we
are dealing only with channels that relate a classification to itself
(otherwise, the second case below is not needed).


\begin{definition}
  Let $\calig{C} : A \Link A$ be a channel (which is part of a channel
  hierarchy) supporting a constraint $\phi\link\psi$, $\Psi$ a
  collection of Austinian propositions (formed from the tokens and
  types of $A$), and $t \in tok(A)$ a token such that $(t : \phi) \in
  \Psi$. The connection \signals{}{t}{t} is said to be {\em
    inappropriate in \calig{C} wrt $\Psi$\/} if either:
  \begin{tightenumerate}
  \item $(t : \psi') \in \Psi$ and $\psi \bottom \psi'$, or
  \item there exists a channel \calig{C'} such that $\calig{C}
    \subchannel{f} \calig{C'}$, where $\phi\link\psi \in
    typ(\calig{C})$ and $f(\phi\link\psi) = \phi'\link\psi'$ and $(t
    : \tau) \in \Psi$, where $\tau \bottom \phi'$.
  \end{tightenumerate}
\end{definition}


To illustrate the second case, if $\Psi$ contains $(tweety : penguin)$
then \signals{}{tweety}{tweety} will be inappropriate in $\calig{C}_1$
of Figure \ref{fig:penguin-ex} since this information conflicts with
the antecedent of the constraint in $\calig{C'}_1$. On the other hand,
$tweety$ will be ``normal'' in $\calig{C}_3$ and $(tweety : \neg
flies)$ can be inferred via this channel.


\begin{definition}
  A collection \calig{L} of channels arranged in a subchannel
  hierarchy is said to be {\em maximally normal wrt $\Psi$\/} (a
  collection of Austinian propositions) if for each channel $\calig{C}
  : A \Link A$ in \calig{L} and each token $t \in tok(A)$,
  \signals{}{t}{t} is a non-exceptional connection in $tok(\calig{C})$
  if and only if \signals{}{t}{t} is not inappropriate in
  \calig{C}.\footnote{Actually, we will assume that there are some
    channels, called {\em logical\/} channels, supporting logical
    relationships (e.g. $\phi\land\psi\link\psi$) which contain {\em
      no\/} exceptions or pseudo-signals.}
\end{definition}


Maximal normality ensures that the {\em only\/} exceptional tokens are
those that are inappropriate, given a channel hierarchy and some
initially given information. Notice that the definitions of
inappropriateness and maximal normality are both ``static''---unlike
in Default Logic \cite{reiter-default} or Commonsense Entailment
\cite{morreau-thesis}, there is no need to define anything
``iteratively''. This is because the channel hierarchy is assumed to
have been closed under the channel operations. This effectively
partitions the default reasoning process into two stages---(i)
defining the channel hierarchy and closing it under the operations,
and (ii) imposing the normality condition. An advantage of this
process is that (i) is only concerned with the type-level constraints
(which represent default rules) and not with the tokens or the
observed information at all. The second stage (i.e. definition of
maximal normality) is the only part of the process that varies with
different initial observed information.


Having imposed the maximal normality condition on a channel hierarchy,
a channel theoretic system of default inference can be obtained. (This
will be defined more completely in the full paper.) This system of
default inference can be shown to satisfy many important properties.
For example, it satisfies the principle of Specificity (as
demonstrated by the ``penguin'' example),\footnote{This principle
  tends to be an important benchmark for nonmonontonic logics. Systems
  of default reasoning which are based on a conditional logic
  foundation tend to satisfy this principle. Note that the described
  system handles {\em full\/} Specificity---some systems (e.g. that of
  Morreau \cite{morreau-thesis}) give unintuitive results when the
  subtype relationship (e.g. $penguin$ is a subtype of $bird$) is
  itself defeasible.} Graded Normality (i.e. individuals can be
``abnormal'' in some respects while being ``normal'' in others), and
other important general properties of default reasoning. Cavedon
\cite{cavedon-thesis} shows that (under a slight extension) the
channel theoretic system of default reasoning effectively defines a
{\em preferential consequence relation\/} in the sense of Kraus et al.
\cite{KLM}.\footnote{Cavedon conjectures that the system defines a
  {\em rational\/} consequence relation \cite{KLM-2} but has not yet
  proved this.}



\section{A methodology for situated default reasoning}


The previous section outlined a channel theoretic model of defeasible
reasoning, based on a maximal normality condition defined with respect
to a channel hierarchy and some initially given information. Channel
theory is intended to capture certain notions of situated
cognition---in particular, the regularities which an agent relies upon
to carry information about its world are reliable only within certain
contexts, when certain conditions are in place.


A channel hierarchy contains (moving up the hierarchy) increasingly
reliable regularities; i.e. channels which contain fewer exceptions as
we move up the hierarchy. Two channels which are related by the
subchannel relation are concerned with similar sorts of information
flow, with the superchannel being a more reliable
version.\footnote{Even though this discussion seems to suggest that
  superchannels are somehow more ``correct'' than their subchannels,
  it should be stressed that each channel is to be seen as supporting
  {\em bona fide\/} regularity. While the subchannels are less
  reliable, they are {\em not\/} to be seen as simply approximations
  to ``correct'' versions.} However, the subchannels tend to be more
efficient to use, since they deal with simpler types and a more
restricted view of the world. Efficient cognitive agents are designed
to use the regularities that are best suited (i.e. strike a balance
between reliability and efficiency) to their environment. In the
channel theoretic model, this involves choosing the level in a
hierarchy which is most appropriate to the particular circumstances in
which the agent finds itself.


As a simple illustration, consider again the penguin example. If an
agent is reasoning about an arbitrary bird $b$, then the most
appropriate level in the hierarchy of Figure \ref{fig:penguin-ex} is
$\calig{C}_1$---no information which the agent has available warrants
it reasoning about the ``penguin-ness'' of $b$ and therefore it should
not do so. However, if the agent is reasoning about a penguin $p$,
then it should not be led to the conclusion that $p$ can fly.  This is
achieved if the appropriate level of the hierarchy is taken to be
$\calig{C'}_1$---since the ``penguin-ness'' of $p$ {\em is\/} relevant
at this stage, then a channel that considers this information is the
more appropriate one. Use of channel $\calig{C}_3$ then results in the
desired conclusion $p : \neg flies$.


The process of choosing the appropriate level of the hierarchy is
reflected in the definition of inappropriateness given earlier:
\signals{}{p}{p} is inappropriate in $\calig{C}_1$ but
\signals{}{b}{b} is not. Alternatively, the choice of appropriate
channel is made by considering what information is available: this
is captured by the following definition of {\em adequacy.\/}


\begin{definition}
  Given a collection $\Psi$ of Austinian propositions, a channel
  $\calig{C} : A \Link A$ is {\em adequate\/} with respect to $\Psi$
  if for each $(t : \phi) \in \Psi$, $t \in tok(A)$ and $\psi \in
  typ(A)$.
\end{definition}


A channel \calig{C} is adequate with respect to a collection $\Psi$ of
propositions if the associated classification $A$ contains all the
types and tokens that are used in the propositions in
$\Psi$---effectively, the ``language'' of $A$ is rich enough to
represent all the information in $\Psi$. To ensure that the simplest
channel is chosen, the appropriate channel for a given inference
should be a minimal adequate one for the propositions in question.


The notion of adequacy of a channel in a hierarchy suggests an
efficient method for defeasible reasoning which corresponds to the
semantic model described in the previous section. The shift in
emphasis from standard default reasoning is significant and seems to
more naturally correspond to the sort of cognitive process we
undertake. This is well illustrated by application of the approach to
AI's {\em qualification problem\/} (the application is discussed in
the full paper; see also \cite{cavedon-thesis}): when I attempt to
start my car, I don't (usually) consider what {\em may\/} cause it to
fail to start and, having no information that any such conditions
hold, assume that everything is OK; I simply turn the ignition-key and
expect the car to start. There is no process of explicitly reasoning
about the lack of information regarding the background conditions in
place; yet the usual default logic approach reflects such a process.
The channel theoretic model, on the other hand, reflects a process
whereby an agent uses the simple (yet fallible) regularity that suits
the normal circumstances.\footnote{Of course, if this regularity fails
  then the agent may need to revise its thinking---see
  \cite{cavedon-thesis}.}


The advantages of this methodology, from a computational point of
view, is that much of the processing can be performed
``off-line''---as pointed out earlier, the construction of the channel
hierarchy is concerned only with the type-level constraints and does
not depend on any circumstantial information. When inference is called
for, the agent uses constraints which are as simple as its embedding
circumstances allow. The potential complexity of the methodology
involves the choice of appropriate level. However, it seems that the
channel hierarchy itself can be embellished with information which
makes this choice simpler. An algorithm for constructing an
appropriate hierarchy and for performing defeasible reasoning (and the
formal properties of it) is currently being investigated (initial
results are described in the full paper).




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% BIBLIOGRAPHY

\small

%\bibliography{../../bib/st,../../bib/defaults,../../bib/logic,../../bib/cond,../../bib/context}
%\bibliographystyle{abbrv}

\begin{thebibliography}{10}

\bibitem{barwise-sta3}
J.~Barwise.
\newblock Constraints, channels and the flow of information.
\newblock In P.~Aczel, D.~Israel, Y.~Katagiri, and S.~Peters, editors, {\em
  Situation Theory and its Applications {III}}. {CSLI} Lecture Notes 37,
  Stanford: {CSLI} Publications, 1993.

\bibitem{barwise-seligman}
J.~Barwise and J.~Seligman.
\newblock The rights and wrongs of natural regularity.
\newblock In J.~Tomberlin, editor, {\em Philosophical Perspectives, Vol. 8}.
  Ridgeview, California, 1994.

\bibitem{giun-qualification}
P.~Bouquet and F.~Giunchiglia.
\newblock Reasoning about theory adequacy: a new solution to the qualification
  problem.
\newblock 1994.
\newblock To appear in {\em Fundamenta Informaticae.\/} Also available by ftp
  as {\tt ftp.mrg.dist.unige.it:pub/mrg-ftp/9406-13.ps.Z}.

\bibitem{cavedon-cond}
L.~Cavedon.
\newblock A {C}hannel-{T}heoretic model for conditional logics (extended
  abstract).
\newblock In {\em Conference on Information-Oriented Approaches to Logic,
  Language and Computation}, Moraga, CA, 1994.
\newblock To appear in {\em {CSLI} Lecture Notes} series.

\bibitem{cavedon-thesis}
L.~Cavedon.
\newblock {\em A Channel Theoretic Approach to Conditional Reasoning}.
\newblock PhD thesis, Centre for Cognitive Science, University of Edinburgh,
  1995.

\bibitem{cavedon-glasbey-hungary}
L.~Cavedon and S.~Glasbey.
\newblock Outline of an information-flow model of generics.
\newblock In {\em Fifth Symposium on Logic and Language}, Hungary, 1994.
\newblock Revised version to appear in special issue of {\em Acta Linguistica}.

\bibitem{cavedon-glasbey-acten}
L.~Cavedon and S.~Glasbey.
\newblock The role of context in the interpretation of generics.
\newblock In {\em Tenth Amsterdam Colloquium on Logic and Language}, 1995.

\bibitem{dretske-info}
F.~Dretske.
\newblock {\em Knowledge and the Flow of Information}.
\newblock Cambridge: {MIT} Press, 1981.

\bibitem{KLM-2}
M.~Freund, D.~Lehmann, and P.~Morris.
\newblock Rationality, transitivity and contraposition.
\newblock {\em Artificial Intelligence}, 52, 1991.

\bibitem{KLM}
S.~Kraus, D.~Lehmann, and M.~Magidor.
\newblock Nonmonotonic reasoning, preferential models and cumulative logics.
\newblock {\em Artificial Intelligence}, 44(1), 1990.

\bibitem{morreau-thesis}
M.~Morreau.
\newblock {\em Conditionals in Philosophy and Artificial Intelligence}.
\newblock PhD thesis, Department of Philosophy, University of Amsterdam, 1992.

\bibitem{pollock-default}
J.~L. Pollock.
\newblock Defeasible reasoning.
\newblock {\em Cognitive Science}, 11, 1987.

\bibitem{reiter-default}
R.~Reiter.
\newblock A logic for default theory.
\newblock {\em Artificial Intelligence}, 13, 1980.

\bibitem{maths-info}
J.~Seligman and J.~Barwise.
\newblock {{\em Channel {T}heory: {T}owards a {M}athema\-tics of {I}mperfect
  {I}nformation {F}low} (draft)}.
\newblock Available by ftp as {\tt phil.indiana.edu:/pub/SelBar93.ps\/}, 1993.

\end{thebibliography}



%%% END BIB
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\normalsize

\appendix


\section{A channel hierarchy for reasoning about generics}


This section contains the definition of a particular channel hierarchy
that seems well-suited to reasoning about generics. Given an initial
collection of channels (representing generics or default rules), a
hierarchy is constructed according to the definition below. The
channel operations (revised so that they take account of the
hierarchy) are then applied to infer new channels (i.e. new generics).


\begin{definition}
  Let \calig{S} be a collection of channels. Let
  $\calig{T}(\calig{S})$ be the collection of channels obtained by
  closing \calig{S} under the standard channel
  operations.\footnote{There is no circularity in this
    requirement---the {\em standard\/} channel operations do not take
    account of the encoded background assumptions.} The {\em default
    channel hierarchy for \calig{S}\/} is the smallest hierarchy
  \calig{K} of channels containing \calig{S} such that:
  \begin{myquote}
    for each channel $\calig{C}_1 : \phi\link\psi$ in \calig{S} and
    each channel $\calig{C}_2 : \tau\link\psi'$ in
    $\calig{T}(\calig{S})$ such that $\psi \bottom \psi'$,
    $\calig{K}$ contains a channel $\calig{C'}_1 :
    (\phi\andsign\neg\tau) \link \psi$, where $\calig{C}_1
    \subchannel{f} \calig{C'}_1$ and $f(\phi\link\psi) =
    (\phi\andsign\neg\tau) \link \psi$; {\em unless\/} either
    \begin{tightenumerate}
    \item there is a channel $\calig{C} : \phi\link\tau$ in
      $\calig{T}(\calig{S})$; {\em or\/}
    \item $\calig{C}_2$ is formed by a composition involving a channel
      $\calig{C'} : \phi\link\sigma$, for some $\sigma$.
    \end{tightenumerate}
  \end{myquote}
\end{definition}


This choice of channel hierarchy ensures that powerful patterns of
reasoning are supported by the resulting logic of generics---see
\cite{cavedon-thesis} for an informal discussion of the intuitions
behind this particular definition. Note the reasoning process does not
in any way depend on the particular vagaries of the specific channel
hierarchy chosen---the channel operations simply assume the existence
of {\em some\/} channel hierarchy. The above definition simply happens
to define a particular hierarchy that ensures powerful patterns of
reasoning are satisfied.



\end{document}
 
%%%%%%%%%%%%%%% END %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
