THE GEOMETRY OF UNCERTAINTY PDF

Preview

Summary

THE GEOMETRY OF UNCERTAINTY SCHOOL OF COMPUTING AND MATHEMATICS, UNIVERSITY OF ULSTER 1 Dr Fabio Cuzzolin Artificial Intelligence and Vision research group Oxford Brookes University December 10, 2014 A BIT ABOUT MYSELF FIRST!  Master s thesis o gesture re og itio at the University of Padua, Italy ...

Description

THE GEOMETRY OF UNCERTAINTY SCHOOL OF COMPUTING AND MATHEMATICS, UNIVERSITY OF ULSTER

1

Dr Fabio Cuzzolin Artificial Intelligence and Vision research group Oxford Brookes University December 10, 2014

A BIT ABOUT MYSELF FIRST! 

Master’s thesis on gesture recognition at the University of Padua, Italy



Visiting student, ESSRL, Washington University in St.

Louis 

Ph.D. thesis “Vision of a Generalized Probability Theory”



Researcher at Politecnico di Milano



Postdoc at the University of California at Los Angeles, UCLA Vision Lab



Marie Curie fellow at INRIA Rhone-Alpes, Grenoble, France



Reader at Oxford Brookes, Department of Computing



Head of AI and Vision group there

2

MY RESEARCH INTERESTS 

Computer Vision and Machine Learning Action and gesture recognition  Human-robot interaction  Autonomous vehicles  Manifold and distance learning 



Uncertainty Theory Belief functions, possibility theory  Geometry of uncertainty measures  Generalisation of total probability  Decision making 



Combinatorics and Discrete Mathematics

3

BELIEF 2014 EXPANDING THE BELIEF FUNCTIONS COMMUNITY 

chaired the 3rd International Conference on Belief Functions (BELIEF 2014) last September



still a lot of work to do:  expanding the community via a moderated mailing list  organising special issues on IJAR and IEEE Fuzzy Systems  linking up with wider AI, UAI and FUSION conferences  targeting real-world problems (CC, policy making)

4

THE GEOMETRY OF UNCERTAINTY TREATING UNCERTAINTY MEASURES AS GEOMETRIC ENTITIES 

 



belief functions can be seen as a point of a simplex probabilities are part of the border of this simples possibility and fuzzy measures too -> unified geometric approach to uncertainty measures problems that can be approached there:   

Conditioning belief functions Decision making with belief functions lots of open problems

5

THE GEOMETRY OF UNCERTAINTY

BELIEF FUNCTIONS AND OTHER UNCERTAINTY MEASURES A GEOMETRIC APPROACH TO UNCERTAINTY GEOMETRY OF COMBINATION RULES TRANSFORMING MEASURES DECISION FRAMEWORKS COMPLEXES OF POSSIBILITY MEASURES

GEOMETRIC CONDITIONING 6

APPLICATIONS FURTHER DEVELOPMENTS

WHY A MATHEMATICS OF UNCERTAINTY? RATIONALE

o

o

o

o

o

probabilities do not represent well ignorance and lack of data evidence is normally limited, rather than infinite as assumed by (frequentist) probability expert knowledge needs often to be combined with hard evidence in extreme cases (rare events or farfuture predictions) very little data bottom line: not enough evidence to determine the actual probability describing the problem 7

UNCERTAINTY MEASURES INTERVALS, CREDAL SETS, AND BELIEF FUNCTIONS



a number of models have been proposed to extend or replace classical probability -> uncertainty theories



[Zadeh,De Finetti, Shafer, Walley, Dubois]

examples: second-order distributions, monotone capacities, rough sets, imprecise probabilities, coherent lower precisions ..



interval probabilities: [Moral] have an interval of probability values for each element



credal sets: [Levi] convex sets of probability distributions

8

BELIEF FUNCTIONS AS GENERALISED PROBABILITIES 

belief functions proposed by Dempster and Shafer in late Sixties



rationale: evidence is typically available in support of events/propositions directly rather then single, individual outcomes



(e.g. a witness strongly supports that a certain event has happened)



this can be translated into a distribution over all events (a random set)



BFs can be fused by Dempster’s rule, a generalisation of Bayes’ rule



the theory of belief function generalises classical Bayesian reasoning, as 

BFs have classical probabilities as special case



Bayes’ updating is a special case of Dempster’s rule of combination

9

BELIEF FUNCTIONS MASS ASSIGNMENT, EXAMPLES  

original formulation on finite domains (frames of discernment) a belief function is completely defined by a distribution over all events: a mass assignment m

 

b1: m({x1}) = 0.7, m({x1 ,x2}) = 0.3 b1({x1,x3}) = m(x1) = 0.7

 

x1

x3 x2

x4

b2: m() = 0.1, m({x2 ,x3 ,x4}) = 0.9 b2({x3,x4}) = 0 10

BELIEF FUNCTIONS AS RANDOM SETS MASS ASSIGNMENTS 

a belief function is completely determined by a non-negative, normalised mass assignment m for each event B  



e.g.: on  = {x,y} the mass assignments are m(x), m(y) AND m(x,y)



m() represents the ignorance about the problem



given a mass assignment, the corresponding unique belief function is given

by the total probability of its subsets:



dually, the plausibility function measures the evidence “not against”

events A

11

BELIEF FUNCTIONS AS LOWER PROBABILITIES 

common interpretation: a belief function provides a constraint on the values of some unknown, ‘true’ probability)



in particular, the belief values b(A) of an event is the lower bound to the possible values of the underlying, unknown probability the plausibility value pl(A) is the upper bound to the possible values of the underlying, unknown probability



b(A)  p(A)  pl(A)  

for classical probabilities they are the same -> “precise” probabilities in Dempster’s original works b and pl are called “lower” and “upper probabilities”

12

BELIEF FUNCTIONS AS CREDAL SETS OF ‘CONSISTENT’ PROBABILITY DISTRIBUTIONS 

another view: mass m(A) can “float” inside A



all probabilities obtained by distributing the mass of each focal element among its singleton elements are called “consistent” with the original BF



they form a whole convex set of probability distributions (a credal set)



examples:

13

THE GEOMETRY OF UNCERTAINTY

BELIEF FUNCTIONS AND OTHER UNCERTAINTY MEASURES A GEOMETRIC APPROACH TO UNCERTAINTY GEOMETRY OF COMBINATION RULES TRANSFORMING MEASURES DECISION FRAMEWORKS COMPLEXES OF POSSIBILITY MEASURES

GEOMETRIC CONDITIONING 14

APPLICATIONS FURTHER DEVELOPMENTS

THE BELIEF SPACE (BINARY CASE) BELIEF FUNCTIONS AS POINTS OF A SIMPLEX 

 

if  = {x,y}, a BF b is completely specified by two belief values: b(x) and b(y)‫‏‬ (this is because b() = 0 and b() = 1 for all possible belief functions) belief functions can thus be seen as points of a plane

15

BELIEF FUNCTIONS AS CREDAL SETS CONVEX SETS OF CONSISTENT PROBABILITIES 

a belief function can be seen as the lower bound to a convex set of “consistent” probabilities

16

A GEOMETRIC APPROACH TO UNCERTAINTY BASED ON THE BELIEF SPACE 

belief space: the space of all the belief functions on a given frame



In a general frame  it is a higher-dim triangle, a simplex it is the convex closure of all the ‘categorical’ BFs



m(A)=1, m(B) = 0 for all B  A



 

has dimension 2n-2, where n = || IEEE Tr. SMC-C '08, Ann. Combinatorics ‘14, FSS ‘10, SMC-B 04, TFS 2014

17

A GEOMETRIC APPROACH TO UNCERTAINTY IMPLICATIONS



Dempster’s sum (and other rules) can be given a geometric construction



belief functions, probabilities and possibilities (fuzzy sets) are all points of the same Cartesian space -> unified geometry of uncertainty



the geometry of possibilities, necessities can be described



uncertainty measures can be transformed into each other by projection



decision frameworks based on these transforms can be devised



conditioning can be performed geometrically



the total belief theorem can be posed in geometric terms

18

THE GEOMETRY OF UNCERTAINTY

BELIEF FUNCTIONS AND OTHER UNCERTAINTY MEASURES A GEOMETRIC APPROACH TO UNCERTAINTY GEOMETRY OF COMBINATION RULES TRANSFORMING MEASURES DECISION FRAMEWORKS COMPLEXES OF POSSIBILITY MEASURES

GEOMETRIC CONDITIONING 19

APPLICATIONS FURTHER DEVELOPMENTS

DEMPSTER’S COMBINATION OF BELIEF FUNCTIONS THE ORTHOGONAL SUM 

several aggregation or elicitation operators proposed [Denoeux AIJ 2009]



original proposal: Dempster’s rule, comes from the original definition of belief functions in terms of multi-valued maps [Dempster68]



basically, each belief function is induced by a prob distribution somewhere



assumes conditional independence of the bodies of evidence

20

DEMPSTER’S RULE OF COMBINATION A SIMPLE EXAMPLE



b1:

x1

m({x1})=0.7, m({x1 ,x2})=0.3



b2:

x3 x2

x4

m()=0.1, m({x2 ,x3 ,x4})=0.9

b1  b2 : m({x1}) = 0.7*0.1/0.37 = 0.19 m({x2}) = 0.3*0.9/0.37 = 0.73 m({x1 ,x2}) = 0.3*0.1/0.37 = 0.08

21

CONVEX FORM OF DEMPSTER’S SUM COMMUTATIVITY PROPERTY 

need to understand its behavior w.r.t. convex or affine combinations



Dempster's sum of affine combinations of BFs yields affine combinations



consequence: Dempster’s sum commutes with convex closure in the belief space

b    i  bi   i  b  bi i

i

i i i   j  j j



… and can be decomposed in terms of Bayes' rule

b  b' 



A  , A  

mb ' ( A) plb ( A)  b  bA  mb' ( B) plb ( B)

B

22

THE POINTWISE GEOMETRY OF DEMPSTER’S RULE IN THE BELIEF SPACE 

Dempster’s sum intersection of linear spaces! [IEEE SMC-B04]



can be given a geometric construction

23

THE GLOBAL GEOMETRY OF DEMPSTER’S RULE IN THE BELIEF SPACE 

conditional subspace: set of possible “futures” of b after Dempster’s combination 

conditional subspace

b  b’ b’

b

  

other operators have been proposed by Smets, Denoeux etc their geometric behavior? -> future work commutativity with respect to affine operator?

24

THE GEOMETRY OF UNCERTAINTY

BELIEF FUNCTIONS AND OTHER UNCERTAINTY MEASURES A GEOMETRIC APPROACH TO UNCERTAINTY GEOMETRY OF COMBINATION RULES TRANSFORMING MEASURES DECISION FRAMEWORKS COMPLEXES OF POSSIBILITY MEASURES

GEOMETRIC CONDITIONING 25

APPLICATIONS FURTHER DEVELOPMENTS

TRANSFORMING UNCERTAINTY MEASURES BELIEF FUNCTIONS TO PROBABILITIES OR POSSIBILITIES 

 





working (naively) with belief functions can be expensive (exponential) various solutions: Monte-Carlo [Wilson], hierarchical evidence .. popular solution: transform into a less complex uncertainty measure (e.g. Bayesian, possibility) this can be done geometrically, for probabilities, fuzzy sets, possibilities are all special cases of b.f.s

IEEE Tr. SMC-B '07, SMC-B 2010, AMAI ‘2010, IEEE Tr. Fuzzy Systems 2014

26

PROBABILITY TRANSFORMATION COMMON APPROACHES 



 

 

finding the probability which is the “closest” to a given belief function different criteria can be chosen: pignistic function [Smets] obeys ‘rationality’ axioms

plausibility transform [Voorbraak’89] commutes with Dempster’s rule! 27

GEOMETRIC PROBABILITY TRANSFORMATIONS ORTHOGONAL PROJECTION AND INTERSECTION PROBABILITY



the transformation problem can be posed in the geometric approach [IEEE SMC-B07] pignistic function BetP is the barycenter of P[b]



two new transformations:



orthogonal projection [b]



intersection probability p[b]



28 28

THE INTERSECTION PROBABILITY FOR PROBABILITY INTERVALS 



although it was derived from geometric arguments [IEEE SMC-B07].. .. it is inherently associated with probability intervals

b(x)‫‏‬



pl(x)‫ ‏‬b(y)‫‏‬

pl(y)‫ ‏‬b(z)‫‏‬

pl(z)‫‏‬

it is the unique probability such that [AIJ under review] for all x p(x) = b(x) + (pl(x) - b(x))‫‏‬ 29

TWO FAMILIES OF TRANSFORMATIONS AFFINE VERSUS EPISTEMIC TRANSFORMATIONS 

Affine family – commute with affine combination of belief functions



Pignistic function Orthogonal projection [SMC-B 2007, 2009] Intersection probability [SMCB 2007, 2009]







Epistemic family – commute with Dempster’s sum



Relative plausibility [AMAI2010] Relative belief [IJAR2012]

 

30

THE GEOMETRY OF UNCERTAINTY

BELIEF FUNCTIONS AND OTHER UNCERTAINTY MEASURES A GEOMETRIC APPROACH TO UNCERTAINTY GEOMETRY OF COMBINATION RULES TRANSFORMING MEASURES DECISION FRAMEWORKS COMPLEXES OF POSSIBILITY MEASURES

GEOMETRIC CONDITIONING 31

APPLICATIONS FURTHER DEVELOPMENTS

PROBABILITY INTERVALS AS PAIRS OF CREDAL SETS   

 



we know the geometry of probability transforms in the belief space their geometry in the probability simplex? each belief function is associated with an interval probability

interval probabilities correspond to pairs of credal sets: a “lower” simplex T1 and an “upper” simplex Tn-1

so we have 3 polytopes associated with a belief function in the probability simplex: (P, T1, Tn-1)‫‏‬

32

THE FOCUS OF A PAIR OF SIMPLICES 

different probability transforms of belief functions can be seen as foci of a pair of simplices



focus = point with the same simplicial coordinates in the two simplices when interior to both it is the intersection of the lines joining corresponding vertices



33

PROBABILITY TRANSFORMATIONS AS FOCI IN THE PROBABILITY SIMPLEX 

relative belief = focus of (P, T1)‫‏‬



relative plausibility = focus of (P, Tn-1)‫‏‬



intersection probability = focus of (T1, Tn-1)‫‏‬



[IEEE SMC-B 2010]‫‏‬

34

FOCI AND A RATIONALITY PRINCIPLE SIMILAR TO THE PIGNISTIC FUNCTION’S



the pignistic function adhere to sensible rationality principles



as a consequence it has a clean geometrical interpretation as center of mass of the credal set associated with a belief function b



the geometric notion of focus amounts to adopting the single probability

distribution which meets both constraints in exactly the same way 

rationality principle: the transformation has to have homogenous behaviour in the two sets of constraints 35

DECISION FRAMEWORKS ALTERNATIVE TO THE TBM BASED ON ALTERNATIVE TRANSFORMS 

Transferable Belief Model: belief are represented as credal sets, decisions made after pignistic transformation [Smets]



decision frameworks similar to the TBM can be envisaged...



... in which upper, lower, and interval constraints are represented as appropriate pairs of credal sets ...



... while decisions are made after resorting to the appropriate transformation, supported by last slide’s rationality principle 36

THE RELATIVE BELIEF TRANSFORM DUAL OF THE PLAUSIBILITY TRANSFORM 

dual of the plausibility transform [Voorbraak]



maps each belief function to the corresponding relative belief of singletons [Daniel 2006]



its geometry and that of the plausibility transform studied by the author in [AMAI 2010]



have a utility interpretation in an adversarial game scenario, inspired by Strat’s expected utility approach to decision making with belief functions

37

STRAT’S CARNIVAL WHEEL SCENARIO 





  



by paying a fixed fee c, people get the chance to spin a carnival wheel divided into a number of sectors labelled, say, they get an amount r(x) which varies with the label x of the sector that stops at the top the gain or “utility” of each outcome for the player is u(x) = r (x) - c their loss l(x) = - u(x) = c - r (x) this amounts to a “lottery” (distribution), in which the probability of each outcome is proportional to its area on the wheel a rational player’s behaviour: computing their expected utility 𝑥𝑝



𝑥 𝑢(𝑥) and play if the latter is positive lacking any uncertainty, decision is trivial

38

CLOAKED CARNIVAL WHEEL

 





the fair’s manager covers part of wheel new situation: set of possible lotteries, described as a belief function area of hidden sector = mass of the whole decision space the manager can pick any probability distribution consistent with b to damage the player

39

RELATIVE BELIEF AND PLAUSIBILITIES AS SAFEST BETTING STRATEGIES 



 



modified scenario in which players are (after paying the usual fee c) asked to bet on a single outcome … … and maximize their worst case expected utility p(x)u(x), under the uncertainty given by the counter-move by the fair’s manager which outcome (singleton) should they pick? naturally described by Wald’s maximin model [Wald’50] conclusion: in both the maximin and the minimax scenarios, relative belief and plausibility of singletons determine the safest betting strategy in an adversarial game in which the decision maker has to minimize their maximal expected loss/maximize their minimal expected return under uncertainty representable as a belief function, interpreted as a set of 40 lower/upper bounds to probability values

THE GEOMETRY OF UNCERTAINTY

BELIEF FUNCTIONS AND OTHER UNCERTAINTY MEASURES A GEOMETRIC APPROACH TO UNCERTAINTY GEOMETRY OF COMBINATION RULES TRANSFORMING MEASURES DECISION FRAMEWORKS GEOMETRY OF POSSIBILITY

GEOMETRIC CONDITIONING 41

APPLICATIONS FURTHER DEVELOPMENTS

CONSONANT BELIEF FUNCTIONS THE COUNTERPARTS OF NECESSITY MEASURES

focal elements = events of non-zero mass  consonant belief function =...