1992
	First Sections of Washington University Technical Report

	PROCESS AND POLICY:  RESOURCE-BOUNDED NON-DEMONSTRATIVE REASONING





Abstract

This paper investigates the appropriateness of formal dialectics as a
basis for non-monotonic reasoning and defeasible reasoning that takes
computational limits seriously.  Rules that can come into conflict 
should be regarded as policies, which are inputs to deliberative
processes.  Dialectical protocols are appropriate for such deliberations
when resources are bounded and search is serial.

AI, it is claimed here, is now perfectly positioned to correct many 
misconceptions about reasoning that have resulted from mathematical
logic's enormous success in this century:  among them, (1) that all
reasons are demonstrative, (2) that rational belief is constrained,
not constructed, (3) that process and disputation are not essential
to reasoning.  AI mainly provides new impetus to formalize the alternative
(but older) conception of reasoning, and AI provides mechanisms with which
to create compelling formalism that describes the control of processes.

The technical contributions here are:  the partial justification of 
dialectic based on controlling search; the observation that non-monotonic
reasoning can be subsumed under certain kinds of dialectics; the portrayal
of inference in knowledge bases as policy reasoning; the review of logics of
dialogue and proposed extensions; and the pre-formal and initial formal
discussion of aspects and variations of dialectical systems with
non-demonstrative reasons.

Acknowledgements

This work was supported under NSF R9008012.  I am grateful for the
invitations to talk at Linkoeping, Vrije Universiteit, SLU, Southwestern Bell
TRI, St. Louis SIGART, and Rochester, which helped me organize this material.  

Jon Doyle and Michael Loui, Gerard Vreeswijk, Patrick Doherty, and John-Jules
Charles Meyer have been especially supportive.  I thank Peter Ladkin for
listening to these ideas at KR89 Toronto.

Correspondence with N. Rescher, J. van Bentham, D. Makinson,
D. Walton, J. MacKenzie, H. A. Simon, and W. V. Quine on these ideas has 
been useful and encouraging.

1.  Arguments and Demonstration.

Sometimes there is proof; mostly there are arguments.  A proof demonstrates
its claim once and for all.  An argument, in contrast, produces warrant
for its claim only when it is effective, in a context of counterarguments,
rebuttal, and further counterargument.  It produces warrant as a result of
a process which subjects the claim to dispute.

This distinction between argument and proof is historically upheld:  there is
demonstrative reasoning and there is non-demonstrative reasoning.

Mathematical proof is the model of demonstration.  Demonstrative reasoning
has been the basis of mathematically satisfying formal languages.  For
non-demonstrative reasoning, formal linguistic systems have been developing
more slowly in this century.

Major historical figures have written about this distinction:  from Aristotle,
who introduced the study of both; to Thomas Aquinas, whose discussions of
argument occurred during a time when, reversing current thought, 
non-demonstrative reasoning dwarfed demonstrative reasoning as a topic
of intellection; to the unsuccessful admonitions of John Maynard Keynes
against Russell and Whitehead as they were conscripted under Hilbert's
reductionist mathematicism; to Karl Popper's attempt to distinguish respectable
study of disputation from Hegelian dialectical metaphysics; to Alonzo Church's
infamous claim of dialectic's intrinsic incompatibility with formalism.

FN:  For a discussion of Aristotle and dialectics, see Hogan.  For a discussion
of Keynes, see Carabelli.  For Aquinas, see Byrne.  

PS:  This paper is largely a discovery of ideas that have lived in a world
apart from the world of formalists.  Since the original paper has been used
by several authors, I have chosen to leave it intact as originally
conceived.  Henry Kyburg suggested treating Pollock's work explicitly.  
If it were to be altered further, it should treat the work of H.L.A. Hart
and Chaim Perelman in detail, and would surely mention
Juergen Habermas and Ludwig Wittgenstein.

AI's interest in this decade in non-monotonic reasoning forces a return to
the non-demonstrative paradigm.  Formalists in AI, especially those of
the knowledge representation milieux, have not yet acknowledged that their
work connects to a longer tradition.  Applied AI research in law, discourse,
and uncertainty have shown better understanding and better scholarship on
this matter.

2.  Reasons and Policies.

Reasoning begins not only with claims, but also with reasons.  Chaining 
reasons forms arguments for further claims.

Some take the relation of one claim being reason for another claim to be
primitive; others feel that reasons can be derived from other reasons,
or warranted by argument, particularly statistical argument.

In the long tradition of logical thought, the reason relation has been
thought to have many nuances.  This century's logical mainstream departs
from the longer intellectual tradition at Russell.  He insisted on a
narrow formulation of reasons.  Reasons were to be treated uniformly as
mere (disjunctive) claims.  Inductive logicians distinguish themselves
by their conviction that all reasons derive from probabilistic considerations.
Assimilating reasons as subjunctive conditionals has been popular recently.
All three are reductionist programmes that construe reasons too narrowly.

The defeasible reason, as studied principally by John Pollock in the past
three decades, is a serious alternative to the narrow and reductionist
views of reasons.  Where Pollock has focused on the logic of defeasible
reasons, [], [], [], the present discussion focuses on the processes in
which those reasons participate.

Represented knowledge can include knowledge about how to conduct reasoning
about that knowledge.  Reasons are that kind of knowledge:  a kind of 
meta-knowledge.  Representing object-level knowledge has been well-studied.
Representing certain transformations of knowledge has also been well-studied,
but under the assumption that the only transformations are those that 
rewrite the object-level knowledge.  "Inference rules" define, solely as
a function of asserted sentences, a set of sentences as theorems, which
are the result of transformations.  Legitimate transformations are only
those "sound" or "truth-preserving" transformations that rewrite the meanings
of what is already asserted.  The transformations define a shorthand system in 
which sentences are succinct ways of writing all of their entailments.  This 
is true of inductive entailments and non-monotonic entailments, as well as
deductive entailments.

A representer who conveys knowledge as "p" and "if p then q" also conveys
as knowledge "q", implicitly.  This is what is meant by using both sentences
"p" and "if p then q" in a propositional language, PC.  Both Jon Doyle [] and
I [] have recently written at length about this view of implicit knowledge
and its alternatives.  Philosophers have called "non-ampliative" all 
inferences that merely rewrite meanings of sentences.  Any consequence 
relation that is a function only of sentences can be viewed as merely
providing meanings for those sentences in a system of representation.  Thus,
the consequences are non-ampliative.

The ampliative alternative is to construct knowledge using meta-knowledge,
and to let a process mediate explicit sentences, explicit reasons, and
their implicit (or constructible) consequences.  Such a process would utilize
reason relations between claims as if they were knowledge about
how the process may proceed.

AI already widely recognizes procedural meta-knowledge.  But it has not yet
recognized reasons as one kind of procedural meta-knowledge.  Default rules,
non-monotonic rules, expert system rules, and inheritance links are knowledge
about how to construct knowledge:  they are more like heuristics in a 
theorem-prover than they are like assertions that are input to the 
theorem-prover.

Reasons are policies.  They are policies for constructing arguments.

Sometimes the grounds for adopting a policy can be represented:  for example, 
the game-theoretic justification of the policy "castle early in chess"
might be representable as a cache of analyzed positions; the statistical
arguments that justify a policy "arguments for something being a bird
can be extended to arguments for that something being able to fly" might be
represented as the summary of sampling together with the description of 
sampling procedure.

Most policies are adopted simply on the grounds that they come from
authority:  legislative bodies, for example, can create policy by fiat.
This is the situation with rule-based programs and knowledge-representers,
or with inheritance systems and their authors.  Grounds for policies are
not represented.  If for some policies, grounds are represented, while
for others, they are not, this forces policy-based reasoning.  Policy
reasoning is the common denominator for processing reasons adopted
on different grounds.  Conflict among policies forces a deliberation
upon the dispute.  Ideally, policies do not conflict and can be compiled
into decision tables.  But in reality, policies are twisted and piecemeal,
have multiple sources, and are inconsistent:  it is often unclear what
are their collective pronouncements.  Because policies are defeasible
rules, their individual pronouncements are relevant only inasmuch as they
contribute to collective pronouncements.

FN:  This is exactly the common observation that defeasible reasoning is
non-local, non-modular, or holistic.  This holism separates (syntactic)
non-monotonic systems from modular inferential systems.

Policies do not share many of the behaviors of demonstrative reasons.
Many non-monotonic reasoning research programmes have formed expectations
for the behavior of defeasible reasons based on behaviors of deductive
or probabilistic entailment relations.  Researchers even take these
expectations as uncriticized axioms of their non-demonstrative systems.
These aims are regrettable.  Even a probabilistic account of policies is
misdirected since not all policies have probabilistic grounds.

FN:  Though Pearl [] for example, explains why behaviors motivated by other
kinds of reasoning, such as axioms from epsilon-semantics, may still be
interesting as guides in the choice of communication convention:  "The quest
for probabilistic semantics is motivated by the assumption that the
conventions of discourse are not totally arbitrary, but rather, respect
certain universal norms of coherence, norms that reflect the empirical
origins of these conventions."

Consider the following pair of policies pertaining to motor vehicle accidents:

being rear-ended is reason for not being liable;

being rear-ended after an abrupt elective stop is reason for being liable.

These do not contrapose, do not survive logical strengthening of the
referent (the first of the objects related, the "left-side"), nor
weakening of the relatum (the second of the objects related, the "right-side").
Arguments that make use of a policy might allow weakening of that policy's
claims (thus, deriving a weaker argument from an argument), but altering
the policy itself by weakening the relata (thus, deriving a policy from 
a policy) violates the spirit of a policy.  These policies can also be
embedded in a system of rules wherein it strains intuition to admit reasoning
by cases, or to create new policies by chaining, as if the reason relation
were transitive [].

3.  Meaning and Process.

Part of the meaning of a policy is the policy-maker's understanding that 
the policy will be used eristically, that is, in processes of disputation
where arguments are based on policies.  

That policies can conflict is clear:  so clear, that the dialectician's
song of "synthesis from conflicting thesis and antithesis" is banal.
More interesting is that disputations based on policy often warrant
conclusions because of the particular way in which the disputation
occurred.  Repeating the disputation under similar conditions is not
guaranteed to produce the same outcome.  Nevertheless, the conclusion
is warranted.  Indeed it is odd to say that we accept an outcome even
though we would have accepted the opposite, had it occurred as the outcome
instead.

This non-determinism

FN:  It is not an indeterminate result, nor is it necessarily probabilistic;
however, the rule for acceptance differs for that for non-deterministic
models of computation.

is the main difference between ampliative inference and mere expansion of
shorthand.  Consequences depend on non-deterministic choices that are input
to the process, and on the protocol for the process.  The function that maps
represented knowledge to constructed inferences not only depends on the
entire set of claims, but also must be indexed by a particular process:  its
individuating features, such as particular non-deterministic choices, and the
context of the process, such as resource bounds that were imposed and the
regimen distributing those resources.

Another difference is non-monotonicity in computation:  had the process 
continued, a different result might have emerged.  Note that this
non-monotonicity is not a property of syntax:  syntactically non-monotonic
systems

FN:  defined in the familiar way in terms of non-monotonic growth of
theorems with respect to axioms:  i.e., there exist S and T s.t. Thm(S u T)
does not contain Thm(S).

do not necessarily define results for partial computations.  It is the
non-monotonicy dynamics of partial computations that deserves attention:
the phenomenon that more computation could cause retraction of conclusions.
Mere non-monotonicity of syntax is less interesting.

Inference is constructed through process.  Policies do not demonstrate
conclusions; they are ingredients to a process that warrants conclusions.
In general there is no ideal process,

FN:  Perhaps we should say there is no ideal tokening of the process type.

no correct outcome of the process.  There is sometimes a natural termination:
for instance, when the set of arguments is finite and can be exhausted,
or when protocol leads to deadlock.  The outcome at a natural point of
process-termination (which still may be a non-deterministic outcome) may be
desirable.  But this is because we prefer processes that terminate at
natural points of termination over those that terminate ungraciously.  
We need not insist on an ideal; not every process computes an approximation 
of some ideal.  We may prefer unbounded computations over bounded ones, 
but not necessarily because they produce results that are ideal by
some independent standard.  

Constructing belief non-deterministically is anathema to mathematical logic.
The idea, however, has been successful elsewhere.  In mathematical
statistics, for example, the dominant view is that hypotheses undergo
testing.  What makes a statistical hypothesis acceptable is the process by
which it is conceived and tested, not just the relation it bears to other
statistical assertions.  The testing could have returned a different answer,
and we are bound (at least until further hearing) to the outcome no matter
what it is.  This Neyman-Pearson view has dominated the Bayesian alternative.
Data are most important to acceptability, but are not the sole arbiters.

Since Popper, Lakatos, and Kuhn, the constructivist view of scientific
theory-formation is mainstream, not the Carnapian view based on theory's
probabilistic relation to data.  In decision theory, the works of Simon and
of Shafer and Tversky use constructivism to address Savage's and von
Neumann-Morgenster's non-constructivist shortcomings.  Heuristic approaches
to optimization, including the outputs of connection networks that attempt
to minimize energy functions, but settle in local minima, are almost always
constructive.

Not all constructions are heuristic.  Some properties, especially social
properties, are defined to hold by construction.  What makes a deserving
Supreme Court Justice is the positive outcome in a confirmation process.
What makes political mandate is the fairness of the election.  What makes
a championship sports team is its prevailing in the playoffs.  Most footprints
in the sand are not the right size and shape, but are caused by feet and
subjected to the right erosive processes.

There is nothing odd about having both a constructivist and a constraint-based
view of what makes something what it is.  What makes a belief rational, in
one sense, is the relation it bears to other beliefs.  This is a constraint 
imposed on claims of rationality.  But a constructivist conception is also
possible.  What makes beliefs rational could be the way in which they are
constructed:  they are the outcomes of the right kind of deliberative process.

The distinction is not merely one of statics versus dynamics.  Axiomatic
theories of belief-revision and axiomatic theories of time-attitudes
toward preference seek to impose constraints on the dynamics of belief,
but do not thereby advocate a constructive view.  What marks constructivism
is the non-determinism (and to a lesser extent, the non-monotonicity) of
the construction.

Sometimes it is possible to have both constructive and constraint-based
grounds for a claim.  For example, at the completion of a Solovay and Strassen
[] probabilistic primality test, the conclusion has both been vindicated
by a test of the right kind and is highly probable given the data.  In that 
case, the propriety of the test has probabilistic origins.

In a trite sense, all beliefs are the result of some metaphysical 
non-determinism:  the world could have differed from what it was.  A rational
agent could have come to believe p instead of not-p, by whatever
means of belief-formation.  Furthermore, this belief is revisable,
which is a kind of non-monotonicity.  Is this construction?  We are interested
only in constructions that are based upon a fixed set of claims.  Even
for a fixed set of background beliefs, there is disagreement about inference.
Constraint-based, non-ampliative, rewriting, demonstrative, Russellian
inference gives one answer:  only one construction is permissible; while
constructivist, ampliative, dewriting, non-demonstrative, Keynesian
inference gives another answer:  many constructions are permissible.

4.  Dialectic and Protocol.

The importance of process is widely recognized in many intellectual fields.
Computer science has the additional responsibility of specifying the 
process. 

One of the right kinds of process for constructing rational belief is
dialectic.  

Dialectic refers to one form of disputation in which a serializable resource
is distributed so that one party's use of that resource is informed by
the result of the other party's (or parties') prior use of resource.  That is,
disputation that is dialectical involves response.  The serialized resource is
typically either search for arguments or time for presentation of arguments,
but could also be the adjudicator's sequential consideration of arguments.

Dialectics can be immediate-response or not.  If response is immediate, then 
satisfaction of some condition, such as the changing of adjudicator's
current opinion, or the mere presentation of an argument, causes a switch
in control of resource.  Most evolved systems of disputation are dialectical,
but not immediate-response.

I doubt that the protocol of disputation must be dialectical in order for
the outcome to be rational, constructed belief.  Still, dialectical protocols
satisfy certain desiderata having to do with effectiveness and fairness
of the process.

Lobbying protocols are inappropriate.  Policies conflict and lead to
conflicting arguments.  Producing arguments for one side of a dispute is
too easy when reasons abound.  Goal-directed search for arguments must
admit search-targets from both sides.

Consider the example of negation-as-failure in logic programming or default
reasoning, where search for counterargument is restricted to demonstrative
counterargument.  Suppose two default rules (as in Reiter []):

1.  A : B / B

and

2.  A : not-B / not-B .

Given A, try to use the first rule.  In order non-demonstratively to conclude
B, show demonstratively that B is consistent.  This is undecidable if B is
a sentence of a sufficiently expressive language, or computationally expensive
in any case; so to show this, try to prove not-B and fail.  Fail by consuming
all resources on the attempted proof.  Therefore, B.  Note that the opposing
rule would not be considered.  A much better strategy would be to take

1.  A to be reason for B; 

also

2.  A to be reason for not-B.

Given A, pro advances the argument for B.

FN:  If time does not remain at this point, the same answer, B, might be
allowed, but for very different reasons.

If time remains, con advances the argument for not-B.  If time still remains,
one side tries to resolve the dispute in its favor.  This last search is the 
one that fails because of exhausted resource.

This is a bit unfair as a portrayal of resource-bounded default reasoning.
The form of the default rule requires resource-exhaustion in order to
advance an argument.  The attempt to prove not-B is an invitation for
counterargument, with which we agree.  The problem is that the counterargument
must be demonstrative.  Surely a better implementation awaits the clever
deployer of resource-bounded defaults.  Still, the negation-as-failure
example illustrates how non-monotonic reasoning, in its early forms, 
ignores dialectical ideas, resource distribution, and the considerations
of fairness under resource-bounded construction that leads to dialectical
ideas.

An even more extreme example of lobbying protocol starts with the latter
pair of defeasible rules.  The argument for B is advance.  Then search
continues to target the construction of arguments for B until resources
are exhausted.  The results of deliberation based on such a protocol
are clearly unacceptable.

The fairer the protocol of a disputation, and the better the strategic
play, and the more effective the expenditure of resource, the better
warranted the outcome.  Dialectic ensures two properties that bear on
fairness and effectiveness:

1.  when one side is losing, it gets resources;

this is fair in at least one sense.  And

2.  when an opinion results, maximum resources were spent attempting
criticism, and failing;

this is effective.

Nicholas Rescher (whose monograph is the most sensible disquisition to
date on the subject) justified dialectic by claiming that knowledge is social,
hence, the formation of knowledge must meet social standards.

QU:  The root issue in probative rationality is that of "building up a
good case" to enlist the conviction of one's fellows.  Accordingly, probative
standards are person-indifferent; they are inherently public and communal.
... The very conception of duly validated knowledge claims relates to publicly
established and interpersonally operative standards.  [p. 60]

A different justification is possible, by referring to fairness, effectiveness,
and the need to adjudicate resource-bounded disputes.  

FN:  Compare this to to Herbert Simon's call for procedural rationality, 
heuristics, and satisficing.  

Fairness demands maximal opportunity for response, and effectiveness demands
maximal information about what are the aims of response.  Fair protocol and
effective advocacy are required of a dispute for rational believers to accede
to a process's outcome.

When resources are unbounded and arguments exhaustible (which is impossible
if arguments are infinite), or when search is completely parallelizable and
strategies for adjudication can cope with unserialized argumentation, then
perhaps dialectic is unnecessary even in disputational deliberations.  There 
are other criteria of fairness, such as equivalent expenditure of resource,
which then dominate the selection of protocol.