A New Criterion for Comparing Fuzzy Logics for Uncertain Reasoning.
A new criterion is introduced for judging the suitability of various fuzzy logics for practical uncertain reasoning in a probabilistic world and the relationship of this criterion to several established criteria, and its consequences for truth functional belief, are investigated.
Introduction
It is a rather widespread assumption in uncertain reasoning, and one that we
shall make for the purpose of this paper, that a piece of uncertain knowledge
can be adequately captured by attaching a real number (signifying the degree of
uncertainty) on some scale to some unequivocal statement or conditional, and
that an intelligent agent's knowledge base consists of a large, but nevertheless
nite, set K of such expressions. Whether or not this is the correct picture for
animate intelligent agents such as ourselves is, perhaps, questionable, but it is
certainly the case that many expert systems (which one might feel should be
included under the vague title of 'intelligent agent') have, by design a knowledge
base which is precisely of this form.
Supported by an EPSRC Advanced Course Studentship, ref. 94416613
y Supported by EPSRC Research Assistantship, ref. GR/H/43045
Commonly the scale on which the uncertainty is measured runs between zero
and one where the two extremes represent, respectively, 'certainly not' and 'cer-
tainly' and intermediate values represent a qualied degree of condence, or be-
lief, or truth, depending on where they stand in relation to the categorical end-
points. So, for example, if an expert meterologist expressed in natural language
his 'knowledge' that
Rain tomorrow is doubtful
this might very well be represented in this form, with the expert's blessing, as
something like
Bel(Rain
where the gure 0.2, the 'belief', or `truth', value the expert gives to 'Rain to-
morrow', corresponds, in the expert's mind, to 'doubtful'.
A knowledge base K of this form where degrees of uncertainty are represented
by truth, or belief, values lying between the classical values one (i.e. true) and
zero (i.e. false) is, like a library, of little practical use without some method of
manipulating, or processing, the knowledge in order to infer truth values for other
statements as required. Whilst a multitude of methods for doing this in practical
expert systems have been tried, one commonly recurring assumption, or device,
(which dates back as far as MYCIN) is that the connectives 'and', `or', and 'not'
are, or at least may be treated as being, truth functional.
To be precise, let be a language for the propositional calculus,
so the p i are propositional variables, and let SL be the set of sentences formed
from L using the connectives ^; _; : as usual. For  2 SL let Bel() 2 [0; 1]
be the 'truth value' (whatever that means) of . So, formally Bel is a function
from SL into the interval [0; 1] and we are in the situation where our knowledge
base consists of the values of Bel on some  1 ; :::;  m , or more generally certain
relations between these values, and we want to use this knowledge to infer the
value of Bel on some other sentence .
The assumption of truth functionality of the function Bel is that there are
xed functions such that for all
Three particularly popular choices here are
_
_
_
often refered to, especially the rst of these, as Fuzzy Logic (or Logics). [We
hasten to add at this point that the term Fuzzy Logic is also used to describe
the logic, or logics, of vagueness. This paper has nothing to do with vagueness,
it is to do with the assumption of truth functionality in uncertain reasoning for
infering degrees of belief. For a discussion of the dierence between these two
qualities see, for example, [Kruse 1994] or [Dubois 1988]]
The use of fuzzy logic in reasoning with uncertainty raises two questions (at
least). One is why it is justied to assume truth functionality in the rst place,
and, related to this, what such truth values could mean in this case. The second
is, having decided in favour of truth functionality in a particular situation, what
choice of F should be made? On the former we shall have something
to say later, but turning rst to the second question { what choice should be
made of F { there are, to our knowledge, two main approaches to this
question in the literature.
The rst is to argue that F should satisfy certain desirable properties,
properties that we might feel the connectives 'and', `or', 'not' exhibit in everyday
usage. Taking the case of negation rst we might feel that F : should satisfy:
That is, (N1) is saying that the negation of a certainly false statement should
be certainly true and the negation of a certainly true statement certainly false.
(N2) says that increasing one's belief in  should decrease one's belief in :.
Finally (N3) says that two negations cancel each other out. In this case we have
the following rather satisfying result due to Trillas, [Trillas 1979], which justies
the choice of F : in F
3 , above.
Theorem 1 (N1-3) hold if and only if the rst order structure h[0;
isomorphic to h[0; 1]; 1 x; <i, i.e.
Proceeding similarly in the case of F ^ the following have been proposed as
desirable properties.
increasing (not necessarily strictly);
That is, (C1) is saying that the conjunction of a certainly false statement
with a certainly true statement, in either order, is certainly false, whilst the
conjunction of two certainly true statements is still certainly true. (C2) says
that the truth value of  ^  should not decrease if the truth value of one of the
conjuncts increases (whilst the other remains unaltered). (C3) says, in essence,
that microscopic changes in the truth values of  and, or,  should not produce a
macroscopic change in the truth value of the conjuction  ^. Finally (C4) might
be justied by arguing that in everday language we in no way insert 'parentheses'
when saying a multiple conjunction, suggesting that in pratice its truth value is
entirely independent of any way of 'bracketing' it.
In this case we have the following theorem which, appearing as it has in various
forms and fragments in the literature (the earliest known to us is [Ling 1965])
probably now simply deserves to be treated as folklore (see [Paris 1994a] for a
proof).
Theorem 2 Let F ^ satisfy (C1-4). Let 0  a < b
b: Then on [a; 1]  [0; a] and on [0; a]  [a;
isomorphic to F 2
(on [0; or to F 3
(on [0;
or
In other words this theorem says that (C1-4) force F ^ to look like a chimera
of F 1
and copies of F 2
and F 3
. Of course one might question why we should
stop at (C1-4), why not add in further desirable properties of conjuction? In
fact as Theorem 1 shows, one of the most obvious further properties, that F ^
is commutative, already follows from (C1-4) whilst adding the only remaining
clearly missing desirable property, idempotence (i.e. F ^
be F 1
min. If we were to combine both the desirable properties of negation
and conjunction, then in addition to (N1-3)+(C1-4)+idempotence certain other
natural laws seem to emerge, for example but since there is, by
the theorem, already only one choice for F ^ we no longer have any latitude in this
matter and natural laws such as the one cited may indeed have to be renounced.
[It is interesting to note here that whilst models of (N1-3)+(C1-4) may separately
have a negation isomorphic to 1 x and a conjuction isomorphic to a chimera
of F 1
it is only in the case where there is actually no contribution to this
mixture from F 2
that we can ensure that both isomorphisms coincide. (see
[Paris 1994a] for a proof)].
Exactly as for conjunction we can list some desirable properties of F _ as
(D2) F _ is increasing (not necessarily strictly);
F _ is continuous;
F _ is associative i:e: F _ (x; F _ (y;
and again prove a version of Theorem 1 with the subcript ^ replaced everywhere
by _ (and min by max).
Once the decision has been made to assume truth functionality these considerations
clearly distinguish the fuzzy logics F
3 (and especially F
leading candidates in the context of processing uncertain knowledge.
A second argument, this time for one particular choice for F ^ , has been given
by Krienovich et al in [Kreinovich 1988], [Kreinovich 1990]. The argument runs
as follows. Consider an expert giving belief values, or truth values if you prefer,
to certain statements today and then repeating the exercise tomorrow. Unless
he, or she, was prewarned that the exercise would be repeated it seems rather
unlikely that they would give exactly the same gures again, even if they had in
the meantime received no new information justifying a revision of their beliefs.
However it does seem much more reasonable to suppose that the ordering of
the values given to various statements would remain the same. [In a way we
are saying here that, apart from zero and one the actual gures given don't
mean very much, it is their relative sizes that matter.] Now if the expert was
interested simply in these statements it would not matter whether he or she was
using today's or tomorrow's values. However if the expert was combining, or
these statements truth functionally according to some F
then it would, or could, make a dierence if (which we assume are
xed) did not themselves also preserve this relative ordering.
Thinking of the drift in the expert's stated belief values between today and
tomorrow as an arbitrary rescaling, that is order preserving one to one onto map
g from [0; 1] to [0; 1] this preservation of relative ordering amongst sentences
behoves, in the case of conjunction, that
As Kreinovich et al show this requirement, for arbitrary rescalings, together with
(C1) and (C3) forces F ^ to be equal to F 1
i.e. to min: A similar argument
for disjunction forces F _ to be equal to F 1
_ , i.e. to max: Following this line of
reasoning then leads to distinguishing F 1
_
as particularly appropriate choices
_ in this context. [It should be added that in the case of negation and
assuming that F : satises (N1), (N2), the above argument yields a choice for F :
between the two functions 1 -(x); -(1 x), where -(x) takes value 1 for
and value 0 for 0  x < 1. However, both of these functions fail to satisfy (N3).]
Having described these arguments in favour of certain choices of F
under the assumption of truth functionality we now turn to examining this latter
assumption.
The most immediate criticism of this assumption is that, in requiring
no account is taken of any relationship between  and . Thus, to take an extreme
example, if
(and surely this could easily happen) then we should be led to
Bel(p _
whereas the average thinking man or woman might feel that the left hand side
expressions should be 0, 1 respectively and the two right hand side expressions
equal to Bel(p). Their problem here in accepting such conclusions, and the
rules from which they are derived, is that as they stand there appears to be no
semantics for belief which could possibly support them and still make sense within
the context. Indeed the lack, up to this time, of an accepted, or even acceptable,
semantics for truth functional belief, despite its frequent and continuing presence
in expert systems is, to say the least, 'unfortunate'. [We hasten to repeat that
we are talking here of belief not vagueness.]
On the other hand there is an alternative theory which does have a supporting,
and widely accepted semantics, namely probability theory. In our context this
amounts to assuming not that the function Bel
but that Bel is a probability function, that is it satises
This interpretation of belief, or truth, values certainly can be supported in a
wide range of contexts (for example in a medical expert system) with a suitable
semantics, namely by identifying these values with frequencies. In addition there
is the rather forceful Dutch Book argument for a rational agent's belief values
being probabilities which results from identifying belief with willingness to bet.
(See, for example [Paris 1994a].) Moreover, not only are there convincing arguments
for belief being identied with probability, but there is a widespread trust
(at least amongst statisticians) that uncertainties in the real world are themselves
explainable as probabilities. That being the case it might seem reasonable
to propose that, ideally, not only should the intelligent agent's belief values be
probabilities (in the sense that they satisfy (P1-2)), but moreover that, ideally,
they correspond to actual probabilities in the real world.
If we were to accept this thesis (as we henceforth do in this paper), that
ideally an intelligent agent's belief, or truth, values should be probabilities, and
furthermore correspond to real world probabilities (without wishing to enter the
mineeld of what exactly that means at this point), then it would seem that the
problem of infering the truth values of other statements from K would move
squarely into the realm of statistical inference.
However, despite the rather general sympathy for this thesis, there is, of
course, a major problem asssociated with attempting to go down this path,
namely maintaining computational tractability (even more so it would seem for
intelligent agents like ourselves with apparently very limited computational abil-
ities).
The key computational problem associated with working with probability
functions is that if Bel is a probability function dened on SL (where
as usual) then in order to specify Bel we need, in general, to know
the value of Bel on all except one of the 2 k atoms of L, i.e. sentences of L of the
i where the  i 2 f0; 1g and p  i
i is dened to be p i if  and to be
0: This su-ces because, by the disjunctive normal form theorem, for
each  2 SL there is a subset S  of the set At L (= of atoms of L
such that
so by (P2)
[Only are needed to specify Bel since for  a tautology S
by (P1)
in practical expert systems k would typically
be at least 40 it is clearly unreasonable, in general, to be able to specify Bel, nor
indeed would one expect that the 'knowledge' provided by the experts would by
itself be su-cient to determine Bel given only that Bel is a probability function.
On the other hand it is clear from (F1-3) that for truth functional Bel Bel(),
for  2 SL, is determined simply by the k values Bel(p 1 ); :::; Bel(p k ), which, in
general, will be directly available from the expert providing the knowledge base.
So, it would seem that if we accept the thesis, as we do in this paper, that
ideally an intelligent agent's belief, or truth, values should be probabilities, and
furthermore correspond to real world probabilities, then we have a choice between
moving away from probabilities, and getting the wrong answers, or sticking with
probabilities and not, in general, being able to come up with any answers at
all! [Of course this is an exaggeratedly pessimistic picture. There are, under
suitable assumptions and situatuations, honestly statistical expert systems which
have even be mooted as possible models for human uncertain reasoning (see for
example [Pearl 1988]). Overall, however, their current applicability is limited.]
Given this choice between no answer and the wrong (or, more accurately, an
unjustied) answer one would surely feel that the latter was preferable (after all
if an express train is thundering down the track towards you jumping either way
has got to be better than doing nothing). And, having made that choice, of going
for an answer which, necessarily, will sometimes be less than perfect, the next
step is clear, within the parameters left open to you minimise the error.
A new criterion
There are many ways, of course, of measuring the error resulting from using a
truth functional belief function to approximate a probability function. However
a natural rst attempt might be to take the sum of the squared dierences
where Bel() in this expression is determined, truth functionally, from F
and the Bel(p i and w is this probability function on SL representing
the 'state of nature'. Unfortunately this rst attempt fails to take into account
the practical considerations appropriate to the situation we have in mind (i.e.
of an intelligent agent reasoning in the real world). Worse still, except in very
special circumstances, this sum will not even be dened! This is because we
are summing over all the innitely many  2 SL and there is clearly no reason
why (Bel() w()) 2 should tend to zero as the length of  increases, indeed
quite the opposite, we would expect that as the length of  increased Bel() and
w() would become ever more unrelated so that any closeness in their values
would be simply by chance rather than by design. But clearly, from the agent's
point of view, long sentences  are very largely irrelevant because in the practical
business of reasoning in the real world the agent is only going to encounter very
short sentences involving rather few connectives.
This consideration leads us to take the sum in the error not over all of SL but
instead over the set ~
n of sentences formed from f using
exactly n binary connectives chosen from f^; _g. We are thinking here, of course,
of n being small, indeed in many of our results we shall limit ourselves to
in which case the sentences in ~
are just single conjunctions or disjunctions of
literals. On the other hand we would expect k to be very large, re
ecting the very
large number of (variable) features the agent would expect to encounter in any
real world situation involving uncertainty, and, apart from this, to be essentially
unknown to him. Indeed almost all our results will be given as assymptotic results
as k tends to innity. The reason for choosing this particular class ~
n to work
with is to some extent pragmatic, just as taking the square in the error term
it helps make the mathematics more tractable (as [Paris 1994b] demonstrates).
In practice one would hope that minor variations in the class of sentences whose
probabilities we are trying to approximate truth functionally would have a rather
marginal eect, a hope which is at least reasonably consistent with the results
we shall shortly be presenting.
Returning again to the appropriateness in this context of the error term E
(now with ~
n in place of SL) we could suppose that the intelligent agent we
have in mind would, like ourselves, not just hold beliefs in a few specialised areas
where there was some hope of knowing the underlying probability distribution,
but in a whole multitude of real situations, where, with maybe a small number
of exceptions, the agent would know little or nothing about the underlying
probabilities beyond (possibly) for those basic events which correspond to the
propositional variables in our formalisation. [In fact even most expert systems,
which one might have classed as 'very specialised', in practice actually approximate
to this situation.] These considerations now lead us to make two further
renements to (1).
Firstly we shall assume that Bel(p i ) is simply a xed, increasing, function,
That is we shall assume that the agent's belief in a basic event
(such as we have denoted by a propositional variable) is purely determined by
the probability of that event and that the more probable an event is the higher
the belief the agent attaches to it. [By our earlier remarks on the ineable nature
of k it seems unreasonable that Q n should also depend on this number.]
Secondly, in view of the agent's large scale ignorance of the probability function
w whose values s/he is endeavouring to approximate, it would seem perverse
of the agent to treat all probabilty functions s/he encountered in a uniform manner
as regards the choice of F Q. For that reason rather than take
the error as in (1) for a single probability function w we shall take a weighted
average of the error over all probability functions w on SL, weighted according
to the likelihood, G L (w), that the agent will encounter that probability function.
Precisely what we mean by this last italicised phrase is not a question we wish
to discuss at length in this paper. It is, in another guise, the problem of picking
a prior in Bayesian reasoning, and as such has already generated a voluminous
literature without, apparently, any great concensus emerging. The notion might
seem to make sense if we considered, say, the(?) probability distribution over all
diseases, symptoms, signs etc. in medicine and then considered how the set of all
restrictions (i.e. marginalizations) of this to a sublanguage with 3 propositional
variables, so given by an eight-tuple of the values of the atoms, were scattered
around in
But rather than indulge in any further philosophical discussion we shall henceforth
just talk of 'likelihood of being encountered', or as we shall call it 'nat-
uralness', of a probability function and leave the reader to interpret it as s/he
wishes.
With these renements in place our new criterion can now be formalised in
terms of minimising
Z
where the intention is that n is small, k is very large, Bel(p i
xed increasing function Q n and G L (w) is some measure of the 'naturalness' of w,
or of the 'likelihood of w being encountered', in the various real world situations
that the agent might inhabit.
We make explicit two assumptions about G L which, we believe, are quite reasonable
properties to require of a measure of naturalness of probability functions
w on SL. Firstly, we assume that G L satises weak renaming, that is, whenever
is a permutation of At L resulting from transposing p
, or from transposing
probability functions w on SL, where w is the probability function satisfying
Note that this simply amounts to saying it is
irrelevant which propositional variable we use to denote a particular proposition,
and whether or not it is used to denote that proposition or its negation. The
property of weak renaming holds for all specic choices of G L that we consider
in this paper. Secondly, we shall assume that for for every 1  i < j  k the
integral Z
G L (w)dw
is a non-zero, integrable function of ha; bi 2 [0; 1] 2 .
Beyond this we shall not struggle to say exactly what well-behavedness conditions
G L is to have, nor exactly how the integral is to be understood. Instead
we shall take it that all our results carry with them the implicit assumption that
all integrals appearing in the proofs are suitably well dened. In the particular
examples that we cite it will be clear that this is the case.
Returning now to the criterion of minimising the error E k
n in (2), once we have
xed n and G L we have various choices as to which of Q choose
to x and which we will allow to vary in attempting to minimise E k
n . In the next
two sections we consider two applications of this criterion. [See also [Paris 1994c],
[Bennett 1995] for earlier and related results along these lines.]
Belief values in fuzzy logic
In the introduction to this paper we provided arguments which, assuming belief
was truth functional, rather favoured the choice of F 1
(= min) for F ^ . Indeed, in
today's practical expert systems this choice is surely the most popular and is often
refered to as 'fuzzy logic' (although this is also used as a generic term for any truth
functional belief or logic of vagueness). Given its widespread use and popularity
it is then natural to ask what function Q
n , for a particular choice
of G L when we to be F 1
(i.e. min; max; 1 x) respectively.
One choice of G L for which Q n can be calculated explicitly is when G L is the
completely independent distribution. That is, if w treats the p i 2 L as completely
1 Note that this denition is similar but does not correspond exactly to the denition of
Weak Renaming for inference processes dened in [Paris 1994a] (where only the latter type of
transpose is allowed).
independent
i:e: w
then G L
otherwise. As a measure of naturalness this distribution could be 'justied' on the
grounds that in the wider world most events, or propositions, are independent. Of
course this is a gross simplication. In particular in the narrow areas of expertise
such as those covered by most expert systems we would certainly not expect,
or want, all the features to be independent. (Having said that however, even in
such situations it may not be so unreasonable to suppose that most small subsets
of L will, in practice, be completely independent.)
In this case we can show that (in the limit as k tends to innity) the Q n
exist and are increasing polynomials of degree 2n
x. [Proofs of the
results stated in this and the following two sections are given in the appendix.]
In particular we can derive a recursive formula for the Q n which for
yields
A surprising property of the Q 0 Q 15 that we have calculated explicitly is
how little they vary, and how rapidly they appear to be converging. For example
the maximum dierence between Q 0 and Q 1 is 0.093 whilst Q 7 and never
dier by more than 0.005. In consequence the actual reduction in the error
resulting from using these Q n is not staggering, an explicit calculation showing
that the improvement in square error per sentence from ~
n as k tends to innity
in using Q 1 rather than Q 0 (i.e. the identity function) is around 4% whilst the
average square error per sentence resulting from using Bel (with F 1
to approximate w is around 3%.
It is interesting to note that in a sense this gives a possible meaning, or se-
mantics, to belief values in F 1 (and for truth functional belief in general), namely
they are scaled probabilities, scaled so as to minimise the error.
Notice also what has happened here to our earlier objection to truth functional
belief that, for example, forces us to have
If we explain belief values in this way then such identities are no longer a problem,
all we need to say is that the approximations are rather poor in these cases.
Indeed since we are arguing for an agent's beliefs being truth functional on purely
practical, or pragmatic, grounds one might suppose that in simple cases like these
an intelligent agent would adopt an alternative, better, approximation strategy,
for example by simply setting
In fact as k tends to innity sentences containing a repeated propositional
variable account for an ever diminishing proportion of the sentences in ~
so
that in the limit they are essentially neglected. It might be argued that this
would not accurately re
ect the actual experience of the agent and that on the
contrary the agent would be disproportionately likely to meet such sentences.
As with the simple case mentioned above however, there would be nothing to
stop an intelligent agent in practice from adopting an alternative strategy in
such cases if s/he saw some value in doing so. For small n this need, as in the
example above, causes no problem because an intelligent agent might reasonably
be expected to recognise the necessary immediate simplication. For larger
however the problem with an agent attempting any sort of simplifying procedure
to a sentence prior to approximating its probability is that, except where this was
immediately recognisable, s/he would (apparently) risk a computationally very
expensive diversion with no guarantee of being any better of at the end of it (see
[Hopcroft 1979]).
In the above example we have taken the rather drastic step of identifying 'nat-
uralness' with `independence'. Whilst this may in some situations be a not unreasonable
assumption, it is patently rather wide of the mark in many real world situations
we could expect our intelligent agent to encounter, and these are completely
disregarded by our function G L in this case. So are there not alternatives which
might be prefered to the completely independent distribution? Unfortunately
the problem of picking a prior in situations such as these of, essentially, complete
ignorance, is one on which we continue to seek guidance from the statistics litera-
ture. [ See [Good 1965], [Jerey 1948], [Paris 1994b], [Paris 1991] for approaches
to the question in the univariate case and [Lawry 1994a], [Lawry 1994b] in the
multivariate case.]
The reader might wonder at this point why we do not simply assume that
all probability functions on SL are equally natural, equivalently, equally likely
to be encountered by our agent. In other words why not simply take G L to be
the Uniform Distribution (i.e. G L functions w on SL)?
Unfortunately such a distribution G L depends on L, or equivalently k, in a way
which is perhaps unexpected, and certainly undesirable, in our context. To see
the problem let us denote the language fp by Lm (so
A k+1
n . Then for xed (which, notice, do not depend on
the expected individual square errors
Z
or even the expected probabilities of ,
Z
w()G Lm (w)dw;
where G Lm (w) is identically 1, may dier according to whether
1. However from the point of view of our intelligent agent this seems counter
intuitive because, as we have already said, the agent would not know k in general,
nor, surely, would s/he consider its exact value at all relevant, beyond that it is
very large. (Indeed it is questionable whether it even makes sense from the agent's
standpoint to talk of 'the k'.) The underlying problem here is that if we take for
each nite language
G L to be the uniform distribution on the
probability functions on SL then the family does not satisfy marginality, that is
it does not satisfy that for L 0  L and w 0 a probability function on SL 0 ,
(w
Z
G L (w)dw:
If we wish to keep G L k as the uniform distribution and have marginality then
we must be prepared to use non-uniform distributions G L for other languages L.
One way that this can be achieved is to take the G L to be, up to normalizing
constants, the Dirichlet Priors, that is,
G
Y
for some xed  > 0, where and the  i run through the atoms of SL.
Taking (and indeed any G L with equal to the uniform
distribution but forces the G L to be non-uniform distributions whenever jLj 6= k.
Notice that these Dirichlet Priors do satisfy weak renaming. Unfortunately, when
does not fully satisfy the conditions we earlier imposed on G L .
As we shall see later (Theorem this family of priors has another unpleasant
failing that would seem to make a second serious dent in their credibility as
contenders for measures of naturalness (the rst dent, of course, being that we
were led to them in the rst place by the intuition that all probability functions
should be equally natural, whilst for all except possibly one value of k they fail
to achieve this).
We now see that in our context the problem of picking a prior actually involves
picking a marginalising family of priors, or distributions. Fortunately the
completely independent distributions do marginalise, which is the reason this
problem of marginalisation did not appear earlier.
Optimal choices for
As a second application of our criterion we consider optimum choices of
(which we shall denote by F opt
_ ) to
n in the limit as k !1
single conjunctions or disjunctions of literals) for a xed marginalizing
family of G L . (We may assume that Q n is the identity, i.e. Bel(p i
in this case since the Q n can be simply absorbed into the
Throughout we shall assume that the G L satisfy marginality and weak renaming

Having settled on some G L a rather vexing problem arises with specifying any
particular F opt
_ in that changing their values on a small number (or set)
of points will not alter the value of the error E k
1 . To be more precise if F : agrees
with F opt
on a  1 -measure 1 set and F agree with F opt
on a  2 -measure 1 set, where
Z
Z
then replacing F opt
_ by F in the error expression
will have no eect on its value. Having noted this problem we will however
henceforth talk about the F opt
_ , it being acknowledged here that we
mean almost everywhere (a.e.), that is to within a suitable -measure 0 set.
With the above assumptions in place
Theorem 3 Let 1. Then in the limit as k !1
F opt
F opt
R
R
Dx;y G L2 (w)dw
F opt
_
R
R
Dx;y G L 2 (w)dw
where yg. (Notice that by an earlier assumption
these denominators are non-zero.)
For proofs, see the Appendix (where (31) gives the limiting value of the resulting
mean square error). The result that F opt
completely in
agreement with the conclusion of Theorem 1 and seems to close the book on this
question. As we shall see later the situation with F ^ and F _ is not quite so clear.
Applying Theorem 3 in the case where G L is the completely independent
distribution we obtain, just as would have been expected, that
F opt
_
In other words F 2 is the optimal choice in this case.
If instead we take our G L to be the Dirichlet Priors with
the uniform distribution on the probability functions on disregarding
the ill-behaviour of the family members on SL k for k > 2 we obtain that
F opt
F opt
_
_In other words the F opt
_ in this case are the averages of their counterparts
in F
1 and F
3 .
If we now take instead the Dirichlet family with i.e. the uniform
distribution on probability functions on SL 1 (extending F opt
by continuity to
the boundary of [0;
comes out to be the value of an elliptic
integral. Much worse however is that F opt
arguments in (0; 1) 2 , not
even increasing!
Theorem 4 For the Dirichlet distribution with  < 4, F opt
fails to be monotone
non-decreasing.
Turning this observation on its head however, we certainly might be justied in
adding the requirement that F opt
^ be increasing (and more generally the property
of inferential monotonicity given in [Paris 1994c]) to the list of desiderata of a
family G L of measures of naturalness.
Returning for a moment to our earlier disappointment that we cannot have
the uniform distribution for more than one value of k unless we are willing to
marginality, it might at least be some comfort to observe that if we take a
Dirichlet family in which the uniform distribution appears for some very large k
(so  is also very large) then the exact value of this k makes very little dierence
to the G Lm for m small. In a sense then it could be argued that an agent who
adopted some such G Lm for m small could 'accommodate' the thought that for
a wide range of large k the corresponding G L k was the uniform distribution. In
such a case we might further argue that (assuming it exists) the agent should
take for his F ^ the limit of the F opt
for the Dirichlet families as k !1. In fact
by results in [Paris 1992] this limit of these functions does exist and on argument
hx; yi gives the value of the middle root of the cubic
d
dz
We now turn to stating some properties of the F opt
Theorem 5 For 0  x; y  1 and under the assumptions of Theorem 3
F opt
_
F opt
(v)
Notice that by using (iv) of this theorem we can obtain analogous results for
the function F opt
_ . As an immediate corollary of this result we have.
Corollary 6 For 0  x  1 and under the assumptions of Theorem 3
F opt
_ (0;
F opt
F opt
do not satisfy (ii) of Theorem 5 we also obtain
Corollary 7 Under the assumptions of Theorem 3, F 1
are never optimal
(for any such G L , with
On the other hand Theorem 5 elevates F 2
2 ) to a special status (see
Appendix for the proof).
Corollary 8 F 2
(i.e. multiplication) is the only F opt
which is associative and
continuous.
Our next result shows that in a sense the converse to Theorem 5 holds.
Theorem 9 If F ^ satises (i),(ii) of Theorem 5 then there is a marginalising
family of priors G L satisfying weak renaming for which F ^ is F opt
It should be noted here however that the G L constructed in the proof of this theorem
are rather contrived and certainly make no pretentions to being 'measures
of naturalness' !
In view of Theorem 9 it is interesting to compare the desirable properties
(C1-4) of F ^ on which Theorem 2 rests and those properties of F opt
emerging
in Theorem 5. By Corollary 6 F opt
although not necessarily (C2)
or (C4) (although the failure of (C2) should, as we have already said, be viewed
more as a question mark against the G L ).
In the other direction we have already seen that (ii) of Theorem 5 does not
follow from (C1-4) because it is not satised by either F 1
. On the other
hand by Theorem 2 commutativity does follow from (C1-4) since it holds for each
of F 1
Conclusion
In this paper we have argued that in a probabilistic world an intelligent agent,
with scant access to these probabilities and largely lacking the computational
power required to draw statistical, or probabilistic, conclusions, may be justied
in resorting to truth functional belief in order to function at all, and that in
such a case the agent should adopt those which satisfy the criterion of
minimising the resulting expected error.
In order to apply this criterion it is necessary to rst x on a 'measure of the
naturalness' of a probability distribution, that being identied with the likelihood
that the agent would encounter this probability distribution.
In this paper we have, without overwhelming enthusiasm, suggested two possible
choices for this measure, the completely independent distribution and the
Dirichlet families of priors. Other possibilities exist in the literature (see for example
[Solomono 1978], [Li 1993], [Fine 1973], [Paris 1994b]), but at this level
of generality the choice of a prior in a situation of, essentially, complete ignorance
remains problematic. It is interesting to observe that in practical applications
of statistical inference su-cient is usually known (or assumed ) about the situation
to severely restrict the possible probability distributions which might be
encountered and as a result the choice of prior is usually much less contentious.
[It should also be pointed out that the customary conditioning on the statistical
data tends to reduce the in
uence of the prior so that the particular prior chosen
is far less of an issue than in our case where we are not considering the possibility
that the agent might somehow update his/her prior, or measure of naturalness,
in the light of observations about probabilities in his/her world of experience.]
our criterion favours the choice of 1 x for F : , a result very much
in line with common practice and Trillas' earlier justication based on desirable
properties, see [Trillas 1979]. When it comes to F ^ and F _ however our criterion
as the only associative,
continuous optimal F whilst F
favoured in terms of
desirable properties is never optimal under these conditions. In view of the fact
that the case surely the most frequently encountered situation (apart
from which is irrelevant here) this seems, all other factors being equal, a
strong recommendation to use F
rather than the ubiquitous F
has to be resorted to. It would be pleasing, of course, to extend these results
to n > 1, especially if Theorems 3 and 5 still held, at least for a wide class
of measures G L . Unfortunately that appears, in general, to be a rather messy
problem.
A second generalisation of these results which we have not considered is the
inclusion of implication amongst our connectives. Clearly there is little further
interest in doing this if we are to view implication,  ! , materially, as the
equivalent of : _ . However, viewing implications as conditionals (and so
as the conditional probability of  given ) would appear to open up
an interesting new area for further investigation.
We close by mentioning that there is a rather natural generalisation (as it
turns out) of our criterion which, instead of attempting to minimise the expected
error incurred by using truth functional belief in place of the actual probabil-
ity, attempts instead to minimise the average error resulting from using truth
functional belief to determine truth values, on the basis of some knowledge base,
rather than by using a particular probabilistic inference process, such as the Maximum
Entropy Inference Process. Some preliminary results in this direction may
be found in [Bennett 1995].


Appendix


Calculation of the Q n for F 1 and the independent distribu-
tion
We seek an (increasing) function Q n (x) which is the limit as k ! 1 of the
increasing
n minimising the expected error
Z
-2f0;1g
completely independent probability function and
otherwise, and, in the second integral, w is the completely independent
probability function which gives p i value x i , the assertion X is true
and 0 otherwise, and  ' p -
i is true if
(equivalently value Q k
n is increasing) for k. Note that
appearing in  because we work with F 1 . In fact it
may hold for more than one
i with some  and ~x, and thus we may be counting
some terms more than once. However, the eect of this can be ignored since the
set of the w for which this can happen has measure 0. Since ~
n is invariant under
permuting the it is clearly su-cient here to minimise
For
let neg() be the result of transposing ^=_, p i =:p i for
Then neg ()  :, ~
n is invariant under neg and if  ' p -
1 .
It follows then that since
we obtain the same error if we use the (increasing) function 1 Q k
place
of
2 a
with equality just if y, we see that the error for2
at most that for Q k
(x). Since we are interested in the minimum error we may
assume
n (x) is already of this form, in which case it is easy to check that
and, using (5), that the expression in (4) is twice
where we can replace w(p 1 ) by x 1 .
However since we are interested in the case where k ! 1, rather than minimising
we shall instead rst attempt to minimise
n is the set of those  2 ~
n with no repeated variables, and return later
to the problem of minimising (6).
The function (not necessarily increasing) to minimise (7) (up to a set of measure
zero) is given by
To see this notice that if Q 0
other function disagreeing with Q
on a set of non-zero measure then substituting Q 0
subtracting (7) from it yields after some calculation
which is strictly positive. Of course we would now like to show that Q n
dened in (8) is increasing. Rather than do that at this point however we shall
set about giving a specic recurrence relation dening the Q
in fact. Once this is done it will be clear that Q n increasing.
In order to simplify what follows let C n be those  in B k
n in which the propositional
variables are p and, with the possible exception of p 1 , this is
the order in which they appear when reading  from left to right. Clearly
appears in
Let
So, by marginality of the completely independent prior, Q
Then, with the obvious abbreviations, for n > 0,
m=n j+2
is the set of those  in B
k in which the variables p n j+2 , p n
appear, and in that order. Taking the sum of the rst of these expressions within
the brackets we obtain, for a xed 1  j  n,X
m=n j+2
Using the fact that for such we see that this is equal
xn j+3;:::;x n+1 =0
is the set of sentences in C j 1 in which p n j+2
with the possible exception of p n j+2 , in that order when reading from left to
right, and this expression is now seen to equal
Considering now the sum of the second of the expressions within the brackets in
and noting that
equals
where   is the result of transposing p m and :pm throughout , we obtain similarly
to (11)
By similar arguments the third and fourth terms in (10) each yield
Summing these contributions yields
whilst directly from the denition, P 0
Repeating a similar argument with H n (x) gives
From this it follows that H n (x) is actually independent of x, so
and the solution to this is

[see [Paris 1994b], lemma 2.2].
By induction on n we can now show that P n
is a polynomial of degree at most 2n + 1. Consequently
and dividing (14) by H n (x) and simplifying gives
d n;j
where


Again by induction on n we can show that Q n (x) is increasing. It now follows
from earlier remarks that Q n (x) is the increasing function minimizing (7).
Turning back now to the original expression (6) suppose that Q k
n is increasing
and gives a value to (6) which cannot be improved by any other increasing
function to within more than 1. Recall that we may assume that Q k
Then, as in (9), for Q n as in (8) the expected error for
Z
when calculated using Q k
n exceeds that when using
Now by a straightforward induction on n for any x
distinct [i.e. a measure one set of w] the value of
is the same [since if
exactly one of p(^)
etc. Furthermore since for
we see that X
Hence the excess error in (18) is
By the assumed 'near minimality' of Q k
n the error (3) associated with using Q k
cannot exceed that by using Q n by more than 1, so certainly, using (20),
Z
where Bel is calculated using Q n . Since
(Bel
this yields
so
1: (21)
n is increasing and Q n continuous if 0 <   Q k
n (a) Q n (a) for some
a
depending only on Q n (and similarly if   Q n (a) Q k
n (a)). It therefore follows
from (21) that on (0,1) the Q k
tend pointwise to Q n (x) as required.
Concerning the improvement in the average error (per sentence in B k
resulting
from using the Q n (x) rather than simply the identity function, by
where D n is the set of
n in which, reading from left to right, the propositional
variables appear in that order. Since for  2 D n and measure one
set of ~x exactly one of  '
so (21) simplies to Z 1
which can now be readily calculated for small n. As earlier this is also the limiting
error with ~
n in place of B k
n as k !1.
As to the average error in using Q n , substituting (8) into (7) (which is clearly
times the average error for
simplifying yields
Dividing by jB k
using the value for H n previously shows
the average error over
n to be
d~x. Then by splitting up the cases where  2 D n is a
conjunction/disjunction we obtain that for n > 0 and d n;j as in (17),
d n;j
whilst
Since we know Q enables us to calculate the average error over
(and hence over ~
n in the limit as k !1), at least for small n.Proof of theorem 3
which give a value to
Z
which becomes arbitrarily close to the inmum (over all of values of
this expression as k !1. [Here F ()
and the identity if As
usual we shall start o by looking for to minimise the expression in
but with i 6= j. In this case, by the renaming and marginalising properties
of G, it su-ces to nd
Z
Now for w a probability function on L 2 and  1 ;  2 2 f0; 1g let  be the permutation
of At L2 such that for -
renaming G L 2 whilst
It follows then that
Z
Z
(w(p  1)); F
(w(p
Z
F
since
Z
(w(p  1)); F
(w(p
Now let
F  (x;
F
so
F
(w(p  1)); F
(w(p  2))):
and, trivially,
Hence replacing F  in the expression in (24) for
using the inequalityX
we see that E(F It follows then that in our search for
to minimise (23) we cannot do better than take
shall shortly show that, in fact, no other F : can do this well, but for the present
we shall only assume that F : our attention to F ^ .
then by (24) and this choice of F : we seek F ^ to minimise
Z
A minimising function here (which we shall already denote by F opt
F opt
R
R
Dx;y G L 2 (w)dw
where To see this suppose F ^ was any other
possible choice (with F :
Z
Z
Dx;y
Z
Dx;y
Z
Dx;y
G L2 (w)dwdxdy
Z
Dx;y
so if E(1
must be zero and F
must
agree on a  2 -measure 1 set, as required. An exactly similar argument applies
for F opt
_ .
Returning now to F opt
us suppose that
(so by earlier results equality must hold here). Now since equality holds in (25)
just if x that we must have the F ^
all equal (on a  2 measure 1 set of < w(p 1 the average of
would give E(1
a.e. and, since E(1
E(1
(notice by weak renaming that
theorem 4(ii) (whose proof does not depend on this theorem)
F opt
and adding (29) and (30) gives F :
We have now shown that F opt
_ as dened in the theorem
when the are further restricted to be distinct. To remove
this last assumption suppose that better, choice for
arbitrarily large k. Then, by (28) and the discussion leading up to it,
Z
Dx;y
Hence
Z
Dx;y
O
so since the right hand side can be made arbitrarily small (and by the assumptions
on G L (w)dw) we must have that F
Notice that from this discussion the expected square error incurred by approximating
w() for  2 ~
A kby Bel() with
tends to Z
as k !1, where F opt
^ is given by (27).
Proof of theorem 4
Let 0  a < b < 1and  < 4. We shall show that for the Dirichlet distribution
with this value of , F opt
aby Corollary 6).
1. Then from the denition of F opt
^ in this case,
F opt
Z a
y
a
Z aay
a
1 a
dy > 0
(by the change of variable y := y a)
Z a0
y
a
1 a
y
a
a
a
1 a
dy > 0
(by splitting
Z aainto
Z a0
aand making the change of variable y := y in the
latter)
Z a0
y
ay
where
a
1 a
1 a
Now since A 1 (y) A 2 (y). Hence, since  < 0,
and the result follows. 2
Proof of theorem 5
(i) follows easily using the weak renaming property of G L .
To show (ii) notice that
F opt
R
R
Dx;y G L (w)dw ;
where, as usual, D
R
R
Dx;y G L (w)dw
R
R
Dx;y G L (w)dw
Let  be the permutation of At L 2 such that for
. Then, since G L satises renaming
Z
Dx;y
Z
Z
Similarly Z
Dx;y
G
Z
G L (w)dw (34)
and (ii) follows from (32), (33), (34).
(iii) follows from
Z
Dx;y
Z
Dx;y
Z
Dx;y
G L (w)dw:
To show the rst part of (iv) (the second part is proved similarly) notice that
Z
Dx;y
Z
Dx;y
Z
Dx;y
Z
Dx;y
G L (w)dw
Z
by using the trick by which we derived (33). Again, as in (34),
Z
Dx;y
G
Z
G L (w)dw
and dividing both sides of (35) by this gives the required identity.
(v) follows easily from the denition of F opt
_ by noting that w(p 1
(or by straightforward manipulation using
Proof of corollary 8
Suppose that F opt
associative and continuous. We rst show by induction
on m that
F opt
For this is true by Corollary 6. Assume it is true for m. Then if
by Corollary 6 and the associativity of F opt
F opt
F opt
by the inductive hypothesis, whilst
F opt

; by the case i < 2 m above;
; as required:
Hence, since F opt
is continuous and agrees with multiplication on a dense set it
must agree with multiplication everywhere. 2
Proof of Theorem 9
First dene for
i;j;k to be the probability
function on SL k such that for  2 At L k ,
Notice that properties (i)(ii) of Theorem 5 ensure that
hence that w x;y
i;j;k is well dened, and that w x;y
Dene the probability functions w x
i;k , for 1  i  k, 0  x  1, and w k such
that for  2 At L k
on the probability functions
on SL k by
Now dene the prior G L k by
It is straightforward, albeit rather tedious, to check that the G L k marginalise,
renaming and give F opt



--R

Master's Thesis
An Introduction to Possibilistic and Fuzzy Logics
Theories of Probability
The Estimation of Probabilities
Introduction to automata theory


On the foundations of fuzzy formalism: Explaining formulas for union
Foundation of Fuzzy Systems
Doctoral Thesis


Representation of Associative Functions


The uncertain reasoner's companion - a mathematical perspective


Probabilistic reasoning in intelligent systems: Networks of plaussible inference

Sobre functiones de negacion en la teoria de con- junctos difusos
--TR

--CTR
Didier Dubois , Henri Prade, Possibility Theory, Probability Theory and Multiple-Valued Logics: A Clarification, Annals of Mathematics and Artificial Intelligence, v.32 n.1-4, p.35-66, August 2001
uncertain reasoning;truth functional belief;fuzzy logic;probability logic