gertekoo

Category: research

Conference paper, presentation, and poster: Computable randomness is inherently imprecise

Computable randomness is inherently imprecise
Gert de Cooman and Jasper De Bock
Proceedings of Machine Learning Research, vol. 62, pp. 133–144, 2017

A conference version of one of the papers I am perhaps most proud of. Research for this paper started with discussions between Philip Dawid and myself about what prequential interval forecasting would look like, during a joint stay at Durham University in late 2014. Jasper who joined in late 2015, and I wrote an early prequential version of the present paper during a joint research visit to the Universities of Strathclyde and Durham in May 2016, trying to extend results by Volodya Vovk to make them allow for interval forecasts. In an email exchange, Volodya pointed out a number of difficulties with our approach, which we were able to resolve by letting go of its prequential emphasis, at least for the time being. This was done during research visits of mine to Jasper at IDSIA in late 2016 and early 2017.

Abstract: We use the martingale-theoretic approach of game-theoretic probability to incorporate imprecision into the study of randomness. In particular, we define a notion of computable randomness associated with interval, rather than precise, forecasting systems, and study its properties. The richer mathematical structure that thus arises lets us better understand and place existing results for the precise limit. When we focus on constant interval forecasts, we find that every infinite sequence of zeroes and ones has an associated filter of intervals with respect to which it is computably random. It may happen that none of these intervals is precise, which justifies the title of this paper. We illustrate this by showing that computable randomness associated with non-stationary precise forecasting systems can be captured by a stationary interval forecast, which must then be less precise: a gain in model simplicity is thus paid for by a loss in precision.

This paper was presented at the ISIPTA 2017 symposium in Lugano, Switzerland. Besides the actual paper, you can also download our presentation, and our poster.

Advertisements

Jasper De Bock’s PhD defense

Jasper De Bock publicly defended his PhD dissertation at Ghent University on May 13, 2015. With great success.Title page

As his promoter, I closed the ceremony with a short laudatio in Dutch:

Beste Jasper

Zo’n vijf jaar geleden stapte je voor het eerst m’n kantoor binnen, en ik weet niet of je toen iets heb horen piepen, of kraken, of misschien wel scheuren: je leven is die dag onherroepelijk gekanteld van bouwkunde naar waarschijnlijkheid.

Je kwam toen, vergezeld door en op aanraden van Arthur, kijken welke masterproeven ik voor jullie in petto had.

De tweede keer dat ik je zag, hadden jullie beiden ervoor gekozen om bij mij een masterproef te doen. Je vroeg dan maar meteen of je mij “Gert” kon noemen. Nu ja, vragen, het leek eerder een vaststelling … Van Arthur wist ik meteen dat ik hem leuk ging vinden. Bij jou dacht ik dat dat misschien wel zou lukken.

Wist ik veel.

Na drie maanden had je een algoritme geschreven dat ik revolutionair vond, en nog steeds vind. Na vier maanden was je FWO-aanvraag binnen. Na vijf maanden reden we met een mini-Cooper door de bergen rond Lugano omdat ik dacht dat een aantal experten daar je ideeën wel zouden kunnen smaken.

Het was de eerste van een aantal gezamenlijke reizen naar conferenties en buitenlandse universiteiten. We noemen ze road-trips, en ook Arthur en Stavros waren en zijn vaste compagnons. Samen werken aan slides, mekaar ‘s nachts van hotelkamer naar hotelkamer sms’en met scans van bewijzen, van de grote teen naar de knieholte van Italië rijden, heel vroeg gaan zwemmen in de Adriatische Zee, en vis, man, die vis die er zo lekker is.

We hebben ook veel onderzoek met z’n tweeën gedaan: of samen aan het bord, of jij telkens weer op de glazen tafel waarvan ik je elke keer weer moest vragen om er niet op te gaan zitten omdat ik zeker was dat je erdoor zou zakken, of allebei in een zetel, of ergens nagenoeg ondersteboven op een trap, of gewoon op de vloer. Jij bent de enige onderzoeker die ik ken die ondersteboven nadenkt omdat er dan meer zuurstof naar je hersenen vloeit.

Er zijn zo een aantal artikels waarop ik echt wel trots ben, en twee daarvan hebben we samen geschreven; samen genoeg voor meer dan 150 bladzijden. Dat was soms wroeten, dan weer spelen, en af en toe verhitte tweekamp. Maar het voelde vaak aan als voetbal, de perfecte combinatie, waarbij het niet uitmaakte wie die verrassende dieptepas gaf, en wie voor het doel afwerkte na een niet te anticiperen schijnbeweging.

Je bent, zonder een schijn van concurrentie, de meest luidruchtige jongen die ik ken. Je maakt ongeveer bij alles lawaai. En dat kan bij mij, bij wie indrukken soms nogal hard binnenkomen, hoe zal ik het zeggen, al eens een hevige reactie opwekken. Vandaar de aankoop van een lawaaionderdrukkende BOSE-hoofdtelefoon, een van mijn beste investeringen van de laatste vier jaar.

Maar weet je wat, gast? Dat is helemaal niet erg. Al dat lawaai is jouw reactie op die toverdoos van indrukken die de wereld voor jou is: het beeld van de jongen in de speelgoedwinkel is voor jou uitgevonden. Ik ben blij dat we in een maatschappij leven waarin universiteiten bestaan die aan mensen zoals jij de kans geven om ideeën met passie achterna te zitten, ze kritisch te fileren, en ze met vuur aan anderen over te brengen.

Ik ben blij dat je hier nu bent beland vandaag, ik ben trots dat ik je hierbij heb mogen gidsen en helpen, en ik ben vol vertrouwen dat je het hierna verder schitterend gaat doen.

Gert de Cooman, Gent, 13 mei 2015.

Predictive inference under exchangeability and the Imprecise Dirichlet Multinomial Model

Invited plenary lecture (with video) at the 12th Brazilian Meeting on Bayesian Statistics (EBEB 2014) in Atibaia SP, Brazil on 10 March 2014.

This talk (and the extremely long paper to go with it) marks the happy end of a spontaneous and informal research project that started in 2004, branched off in a surprising number of directions, and taught me so much about mathematics in general, and the foundations of probability theory in particular. Along the way, I needed all the help I could get, and got it from Enrique Miranda, Erik Quaeghebeur, Jasper De Bock and Márcio Diniz.

Here’s the abstract: Coherent reasoning under uncertainty can be represented in a very general manner by coherent sets of desirable gambles. In this framework, and for a given finite category set, coherent predictive inference under exchangeability is represented using Bernstein coherent cones of multivariate polynomials on the simplex generated by this category set. This is a powerful generalisation of de Finetti’s representation theorem allowing for both imprecision and indecision. We define an inference system as a map that associates a Bernstein coherent cone of polynomials with every finite category set. Many inference principles encountered in the literature can then be interpreted, and represented mathematically, as restrictions on such maps. We discuss two important inference principles: representation insensitivity—a strengthened version of Walley’s representation invariance—and specificity. We show that there is an infinity of inference systems that satisfy these two principles, amongst which we discuss in particular the inference systems corresponding to (a modified version of) Walley and Bernard’s imprecise Dirichlet multinomial models (IDMMs) and the Haldane inference system.

A game-theoretic ergodic theorem for imprecise Markov chains

Invited plenary lecture at the Fifth Workshop on Game-Theoretic Probability and Related Topics (GTP2014), held in Guanajuato, Mexico, 10-13 November 2014.

Based on research I’ve done in the past year with Jasper De Bock and Stavros Lopatatzidis. I had been trying to prove an ergodic theorem in an imprecise probabilities context ever since I started work in the field. These things take time and patience, especially in imprecise probabilities, because many of the tools present in the precise counterpart are simply not available yet. Or take surprisingly different forms.

Here’s the abstract: We prove a game-theoretic version of the strong law of large numbers for submartingale differences, and use this to derive a pointwise ergodic theorem for discrete-time Markov chains with finite state sets, when the transition probabilities are imprecise, in the sense that they are only known to belong to some convex closed set of probability measures.

Lecture at the SIPTA School 2014 in Montpellier

I have just finished lecturing at the SIPTA 2014 School in Montpellier, the 6th installment of a series of summer schools on imprecise probabilities, held at the beautiful location of the Institut de Botanique.

The "salle de conférences" at the Institut de Botanique in Montpellier

The “salle des actes” at the Institut de Botanique in Montpellier

Erik Quaeghebeur and I presented a joint lecture on inference. You can download our slides for the joint presentation, lecture notes for Erik’s general discussion of inference and his additional examples for binomial sampling, and lecture notes for my discussion of symmetry and exchangeability.

SIPTA School 2014 Participants

SIPTA School 2014 Participants

New edited book: Introduction to Imprecise Probabilities

And the goodies keep coming in: this morning I received advance copies for another Wiley book, Introduction to Imprecise Probabilities, edited by Thomas Augustin, Frank Coolen, Matthias Troffaes and me, but this one took us only about five years to finish.

Introduction to Imprecise Probabilities

To quote from the book description:


In recent years, the theory [of Imprecise Probabilities] has become widely accepted and has been further developed, but a detailed introduction is needed in order to make the material available and accessible to a wide audience. This will be the first book providing such an introduction, covering core theory and recent developments which can be applied to many application areas. All authors of individual chapters are leading researchers on the specific topics, assuring high quality and up-to-date contents.

An Introduction to Imprecise Probabilities provides a comprehensive introduction to imprecise probabilities, including theory and applications reflecting the current state if the art. Each chapter is written by experts on the respective topics, including: Sets of desirable gambles; Coherent lower (conditional) previsions; Special cases and links to literature; Decision making; Graphical models; Classification; Reliability and risk assessment; Statistical inference; Structural judgments; Aspects of implementation (including elicitation and computation); Models in finance; Game-theoretic probability; Stochastic processes (including Markov chains); Engineering applications.

Essential reading for researchers in academia, research institutes and other organizations, as well as practitioners engaged in areas such as risk analysis and engineering.

New book: Lower previsions

This morning I received advance copies from Wiley of the book Lower Previsions that Matthias Troffaes and I have been working on for the past eight years. I am really excited that it is finally here, and I hope that our effort will help other people extend and apply the theory of imprecise probabilities.

Lower Previsions

I hope Wiley won’t mind if I quote here from our own Preface, I certainly don’t:

Lower Previsions is an overview of, and reference guide to, the mathematics of lower previsions. Starting from first principles—acceptability—, we derive their mathematical properties and relate them to a wide range of other uncertainty models—belief functions, Choquet capacities, possibility measures—and mathematical concepts—including filters, limits, propositional logic, integration and many other constructs from functional and convex analysis. The material of the book is advanced and aimed at researchers, postgraduate students and lecturers. It will be of interest to statisticians, probabilists, mathematicians and anyone whose field of interest includes some form of uncertainty modelling, both from a practical and a theoretical point of view.

Work on this book started about 8 years ago. The idea was, at that time, to turn the most important results in Matthias’s PhD thesis, supervised by Gert, into a coherent and more or less self-contained research monograph. Our initial plan was to focus on two things: first, the relationship between natural extension and integration and second, the discussion of lower previsions defined on unbounded gambles. It soon became clear that, in order to make the book more self-contained, we needed to include much more material on lower previsions themselves. At the same time, we gathered from conversations with close colleagues that there was a definite interest in—given the perceived lack of—a comprehensive treatment of the existing theory of lower previsions. And so we decided to include, besides our own, a number of contributions from other people, amongst whom in particular are Peter Williams, Peter Walley, Sebastian Maass, Dieter Denneberg and Enrique Miranda. The present book, therefore, differs significantly from the one we started out with. While initially, the book was mostly focused on Matthias’s PhD work, in its present form, it contains much more material and both authors have contributed to it on an equal footing.

In the first part of this book, we expose and expand on the main ideas behind the theory that deals exclusively with bounded gambles. We also discuss a wide variety of special cases that may be of interest when implementing these ideas in practical problems. In doing so, we demonstrate the unifying power behind the concept of coherent lower previsions, for uncertainty modelling as well as for functional analysis. In the second part of this book, we extend the scope of the theory of lower previsions by allowing it to deal with real gambles that are not necessarily bounded. In that part, we also deal with conditioning and provide practical constructions for extending lower previsions to unbounded gambles.

[…]

We have tried to make this book as self-contained as possible.  This means, amongst other things, that we have tried to at least provide an explicit formulation—if not an actual proof—of most results that we use. We have relegated to a number of appendices supporting material that did not fit nicely into the main storyline.

If you are used to a measure-theoretic approach to probability, you may initially feel somewhat lost in this book, because we do not start out with measurability at all. Indeed, the foundations of lower previsions, for arbitrary spaces, do not rely on any notion of measurability. This may come as a surprise to some people who think that using measurability is natural and should come first. Instead, our discussion of lower previsions is founded on a notion of acceptability of gambles, which has a direct behavioural interpretation. In other words, rather than posing laws of probability, we pose laws of acceptability, from which laws of probability are derived.

As often as possible, we give detailed accounts of most steps in the proofs, with explicit references to other results that are being used. This may appear to be pedantic—or even worse, condescending—to some, but we thought it better to be too specific rather than incur the risk of explaining too little: as this is not a small book, we cannot expect any reader to remember every little result we have proved or mentioned earlier.

[…]

We hope that you will enjoy reading and working with this book as much as we have enjoyed researching and writing it.

New arXiv note: Continuity of imprecise Markov chains with respect to the pointwise convergence of monotone sequences of gambles

Continuity of imprecise Markov chains with respect to the pointwise convergence of monotone sequences of gambles (arXiv page)

by Jasper De Bock and Gert de Cooman

Abstract: The aim of these notes is to study the conditions under which the natural extension of an imprecise Markov chain is continuous with respect to the pointwise convergence of monotone (either non-decreasing or non-increasing) sequences of gambles that are n-measurable, with n a natural number. The framework in which we do this is that of the theory of imprecise random processes currently being developed in (De Cooman, 2014). We find that for non-decreasing sequences, continuity is always guaranteed if the state space of the Markov chain is finite. We find a similar result for non-increasing sequences, under the extra condition that the joint model is constructed using the Ville-Vovk-Shafer natural extension rather than the Williams natural extension. We also discuss the extent to which these results apply to general random processes.

More information?
This is a note containing the proofs of two useful continuity results for monotone adapted processes in imprecise Markov chains. We intend to include them, or rely on them, in forthcoming papers on Markov processes, and on stochastic processes using imprecise probabilities. I will post more bibliographic details on my UGent website as they come in.

Inference using sets of desirable gambles

Invited plenary lecture at the 12th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2013) in Utrecht, The Netherlands on 10 July 2013.

Even kort wat ik denk over de publicatiecultuur

Gisteren is het debat over publicatiedruk en overheidsfinanciering van de academische wereld op gang gebracht door de publicatie van een open brief, gekoppeld aan een petitie, die ik intussen heb ondertekend:

Afbeelding

Naar aanleiding van een aantal reacties hierop in de pers en andere media, denk ik dat het belangrijk is om een duidelijke lijn te trekken tussen een aantal verschillende vragen en thema’s:

  1. Is het aantal (gereviewde en gepubliceerde) artikels een goede graadmeter voor de kwaliteit van het geleverde onderzoek? Hierop past een genuanceerd antwoord, dat rekening houdt met de publicatiecultuur in het vakgebied, met het aantal auteurs per artikel, met hun lengte—sommigen verdelen resultaten over vele kortere en snellere artikels, anderen publiceren ze liever in langere werkstukken die een vollediger verhaal vertellen. Maar ook andere publicaties, zoals boeken (textbooks zowel als research monographs) kunnen een zeer grote didactische zowel als wetenschappelijke waarde hebben. En de kwaliteit van publicaties beoordeelt men nog altijd het beste door ze te lezen, niet door ze te tellen.
  2. Is het nodig om als wetenschapper/onderzoeker een meer dan gewone inzet te tonen, die zich uit in veel, lang en hard werken? Mijn antwoord hierop is een ongenuanceerd “ja”. De boutade op Twitter van een collega ‘Alsof coureurs die Tour de France rijden, klagen over het feit dat er bergen in het parcours zijn.’ lijkt mij daarom aan de kwestie voorbij te gaan. Het is ook een “if you can’t stand the heat, get out of the kitchen”-argument dat negeert dat grote hitte niet noodzakelijk tot de beste gerechten leidt. Dit brengt mij bij het derde thema.
  3. Is de sterke klemtoon op het publiceren van wetenschappelijke resultaten in artikels op lange termijn bevorderlijk voor het wetenschappelijk bedrijf? Dit is een erg interessante vraag, die meer discussie en studie verdient. Ik ben er niet zo zeker van dat het antwoord erop een onverdeeld “ja” zal zijn. Publiceren is een middel om resultaten te communiceren, maar niet het doel van wetenschap. Toch zie ik doctorandi en collega’s die meer op publiceren dan op het onderzoeken zelf gefocust zijn—ik ervaar bij mezelf dat het moeite vraagt om die vaak onbewuste neiging te onderdrukken. En mijn ervaringen als reviewer en redacteur leren dat de druk om veel te publiceren vaak duidelijk zichtbaar is in de kwaliteit van de artikels die ik onder ogen krijg—gesprekken met collega’s geven aan dat die ervaringen zeker niet uniek zijn.

Hoe en of het beter kan: een vraag die aandacht verdient. Ze wordt beter niet weggemoffeld of weggelachen door schampere tweets als “Hypothese: hoe minder toppublicaties een academicus heeft, hoe harder hij zich verzet tegen de publicatiedruk.”

This is what makes me think I am a mathematician

You begin with something, a problem that is horribly complicated and dense and opaque, and you don’t know how to even start dealing with it, or thinking about it. You push it, shove it, shake it, tear at it, turn it around constantly in your mind, look at it from different sides. You manage to peel away a few layers, but it remains complicated and dense and opaque. You put it aside, and think about something else for a few months …

You repeat this several times, sometimes for several years on end.

And then, one day, often when you’re not thinking about it at all, there is a … what? A hunch, a flash, a suspicion, a hint at an extremely simple idea that brings about an uneasy feeling, a vague sense of excitement. The excitement rises, and you decide to look at the problem again, because all of a sudden you have this crazy absolute certainty that this will work, even though you’d never be able to explain rationally why it should. It just seems to fit. It is simple and crazy and surprising enough to fit.

And yes, the problem starts to unravel, to fall apart into manageable pieces, and while you are working on it continuously for days and often weeks, your motivation and concentration are sustained by a strong feeling of satisfaction, because you are experiencing pure unmitigated beauty, simplicity, elegance, necessity.

You’ve solved the problem. You’re happy and satisfied.

You can’t face looking at it again for months and months. You feel you’re done with it.

But you have to tell other people about it, explain it, teach about it. And sometimes, the excitement comes back, because you see that the simple and crazy idea you had, manages to seduce other people as well.

Surprised ...

… when something you wrote down at 4am still makes sense at 9am.

A link between Game-Theoretic Probability and Imprecise Probabilities

Lecture at the Fourth Workshop on Game-Theoretic Probability and Related Topics (GTP2012), held in Tokyo, Japan, 12-14 November 2012.

Based on research I’ve done during the past few years (and for the last part in particular during the last few months) with Filip Hermans, Jasper De Bock and Enrique Miranda.

Here’s the abstract: In game-theoretic probability (GTP) there is a fundamental formula (which we will call the Shafer-Vovk-Ville, or SVV, formula) for expressing lower and upper prices for a variable defined on the terminal situations of an event tree associated with a game. In GTP it is used as a given: a starting point for much of the development of the theory. In earlier work, we have shown how, for event trees that are bounded, this formula can be derived on a behavioral approach and with a different interpretation, in the context of the theory of imprecise probabilities (IP), from two rationality requirements: coherence and cut conglomerability. In the present talk, we discuss how something similar, but more involved, can also be done for unbounded event trees: besides coherence, we impose two additional rationality axioms, bounded cut conglomerability and bounded cut continuity. Interestingly, our approach shows that in deriving the SVV formula, two types of infinity have a part, and can be treated separately: bounded cut conglomerability tries to cope with infinity in the width of the event tree, and bounded cut continuity with infinity in its depth. These additional requirements only need to be invoked when going from local to global modes: it concerns the global uncertainty models in the tree—the uncertainty about paths—, whereas for the local models—the uncertainty about the next move in a situation—we only need to impose coherence, nothing more. We explore a number of aspects and consequences of this connection between GTP and IP.

New arXiv paper preprint: Accept & Reject Statement-Based Uncertainty Models

Accept & Reject Statement-Based Uncertainty Models (arXiv page)

by Erik Quaeghebeur, Gert de Cooman and Filip Hermans

Abstract: We develop a framework for modelling and reasoning with uncertainty based on accept and reject statements about gambles. It generalises the frameworks found in the literature based on statements of acceptability, desirability, or favourability and clarifies their relative position. Next to the statement-based formulation, we also provide a translation in terms of preference relations, discuss—as a bridge to existing frameworks—a number of simplified variants, and show the relationship with prevision-based uncertainty models. We furthermore provide an application to modelling symmetry judgements.

More information?
I will post more bibliographic details on my UGent website as they come in.

New arXiv paper preprint: An efficient algorithm for estimating state sequences in imprecise hidden Markov models

An efficient algorithm for estimating state sequences in imprecise hidden Markov models (arXiv page)

by Jasper De Bock and Gert de Cooman

Abstract: We present an efficient exact algorithm for estimating state sequences from outputs (or observations) in imprecise hidden Markov models (iHMM), where both the uncertainty linking one state to the next, and that linking a state to its output, are represented using coherent lower previsions. The notion of independence we associate with the credal network representing the iHMM is that of epistemic irrelevance. We consider as best estimates for state sequences the (Walley–Sen) maximal sequences for the posterior joint state model conditioned on the observed output sequence, associated with a gain function that is the indicator of the state sequence. This corresponds to (and generalises) finding the state sequence with the highest posterior probability in HMMs with precise transition and output probabilities (pHMMs). We argue that the computational complexity is at worst quadratic in the length of the Markov chain, cubic in the number of states, and essentially linear in the number of maximal state sequences. For binary iHMMs, we investigate experimentally how the number of maximal state sequences depends on the model parameters. We also present a simple toy application in optical character recognition, demonstrating that our algorithm can be used to robustify the inferences made by precise probability models.

More information?
I will post more bibliographic details on my UGent website as they come in.

Recent developments in imprecise probabilities and probabilistic graphical models

Invited talk in the Frontiers in AI track at ECAI 2012, held in Montpellier, France, 27-31 August 2012.

An Operational Approach to Graphical Uncertainty Modelling: PhD Thesis by Filip Hermans

My student Filip Hermans defended his PhD thesis in May of this year. Thus far, I haven’t had time to blog or brag about it, but it is time I made up for that. I believe that what he has done is really worth taking a good look at, especially if you are interested in imprecise probabilities, the foundations of probabilistic inference, or stochastic processes.

There are, besides the Introduction and Conclusion, four main chapters in the thesis. The first deals with acceptability of gambles, and constitutes a valiant attempt at providing a foundation for (imprecise-)probabilistic inference based on weak and strict preference relations. It is the basis for a more recent and more detailed analysis that Erik Quaeghebeur, Filip and I have been working during over the last year (and which I will have occasion to talk about later). All other chapters are built on this framework. The second deals with (imprecise-)probabilistic inference associated with event trees, and provides the foundations for a theory of (discrete-time) stochastic processes using imprecise probabilities. In the third chapter, this is applied in particular to Markov processes. The fourth chapter extends the arguments of the previous two even further to allow for inference in credal networks with a tree structure.

And, following the tradition started by Erik Quaeghebeur in his PhD thesis, there is, of course, a blonde footnote dedicated to Enrique Miranda:

Afbeelding

Credal trees under irrelevance

Lecture at the Fifth SIPTA School on Imprecise Probabilities, held in Pescara, Italy, 16-20 July 2012.

Irrelevance, independence and coherence

Lecture at the Fifth SIPTA School on Imprecise Probabilities, held in Pescara, Italy, 16-20 July 2012.

Desirable symmetry: a few open questions about desirability and symmetry

In early November, there was a Workshop on Geometry of Imprecise Probability and related Statistical Methods (GEOMIP-11) at Durham University. I gave a talk there about some geometrical aspects of modeling symmetry in imprecise probabilities, using the sets of desirable gambles model: I used the example of finite exchangeability to identify a number of interesting research problems in this area.

ISIPTA ’11 in Innsbruck

The accepted papers for the upcoming ISIPTA ’11 (Seventh International Symposium on Imprecise Probability: Theories and Applications, Innsbruck, Austria, 25-28 July 2011) are now available online, and can be downloaded.

I was the local organiser for the first ISIPTA, in Ghent in 1999, with Peter Walley, Serafin Moral, and Fabio Cozman as co-organisers. And I have been quite closely involved in most of the biennial follow-ups. It is one of my favourite conferences, and the best venue to meet people who take indecision, imprecision and indeterminacy in probability theory seriously.

This year’s edition has a special session in honour of Bruno de Finetti, who was born in Innsbruck in 1906. As will be discussed by Teddy Seidenfeld and Paolo Vicig, de Finetti’s attitude towards imprecision in probability theory was only lukewarm, to put it mildly. Nevertheless, many of his ideas have played a central part in the development of recent accounts of imprecise probabilities, and can be formulated quite elegantly using some its mathematical languages, notably coherent lower previsions and sets of desirable gambles. That will be one of the topics I intend to touch upon in my contribution to the special session. I’ll post the slides for my presentation here in due course.

Master’s theses by Jasper De Bock and Arthur Van Camp

I have been telling you about work Jasper De Bock and I have done on state sequence prediction in imprecise hidden Markov Models, leading to the development of the EstiHMM algorithm. Now, Jasper’s master’s thesis (written in Dutch with an English extended abstract) on this subject has been submitted, and is available for download. We have submitted a paper about this to the ISIPTA 2011 conference.

Arthur Van Camp has been working on applying the MePiCTIr algorithm to inference in imprecise Hidden Markov models, with a simple but interesting application in earthquake rate prediction. Hidden in his text is an interesting idea about the interplay between quantisation (or discretisation) and imprecision I have been toying with for some time now, and hope to be able to work on with him in the coming year. Arthur has submitted an abstract for poster presentation at ISIPTA 2011. His master’s thesis (written in Dutch with an English extended abstract) on this subject has been submitted, and is available for download too.

Read the rest of this entry »

EstiHMM: heat plots for the number of maximal sequences

In a previous post, I mentioned an efficient algorithm for predicting the maximal state sequences for a given output sequence in an imprecise hidden Markov model (iHMM). Jasper De Bock and I have since given this algorithm a name, EstiHMM, and have written an implementation in Python that we intend to make public as soon as possible, also via this channel. We also hope to be able to present our work at the coming ISIPTA’11 conference in Innsbruck.

We now know that EstiHMM’s complexity is cubic in the number of states for the hidden variables, quadratic in the number of hidden variables, and linear in the number of maximal sequences. This is comparable to Viterbi’s algorithm, if we take into account that Viterbi resolves ties arbitrarily, something we are not allowed to do for iHMMs.

While a linear complexity in the number of sequences is probably as good as it gets, we see that we can only hope to find all maximal sequences efficiently provided their number is reasonably small. Should it, say, tend to increase exponentially with the length of the chain, then no algorithm, however cleverly designed, could overcome this hurdle.

Because this number of maximal sequences is so important, we decided to study its behaviour in more detail.
Read the rest of this entry »

An efficient exact algorithm for state sequence estimation in imprecise hidden Markov models

Jasper De Bock is one of the master’s students whose work I supervise at Ghent University. With a little help from us as his friends, he has devised a truly ingenious and very efficient exact algorithm for estimating state sequences from outputs (or observations) in imprecise hidden Markov models (iHMM), where both the uncertainty linking one state to the next, and that linking a state to its output, are represented using coherent lower previsions.
Read the rest of this entry »

New journal paper: Exchangeability and sets of desirable gambles

Exchangeablity and sets of desirable gambles (preprint pdf)
by Gert de Cooman and Erik Quaeghebeur

Abstract: Sets of desirable gambles constitute a quite general type of uncertainty model with an interesting geometrical interpretation. We give a general discussion of such models and their rationality criteria. We study exchangeability assessments for them, and prove counterparts of de Finetti’s finite and infinite representation theorems. We show that the finite representation in terms of count vectors has a very nice geometrical interpretation, and that the representation in terms of frequency vectors is tied up with multivariate Bernstein (basis) polynomials. We also lay bare the relationships between the representations of updated exchangeable models, and discuss conservative inference (natural extension) under exchangeability and the extension of exchangeable sequences.

Read the rest of this entry »

Perhaps one of our better posters

Markov Trees Poster

Poster presented at ISIPTA 2009, won the Best Poster Award. Graphics design by Filip Hermans, with a little bit of help from the others.

New journal paper: Epistemic irrelevance in credal nets: the case of imprecise Markov trees

Epistemic irrelevance in credal nets: The case of imprecise Markov trees (doi:10.1016/j.ijar.2010.08.011, preprint pdf)
by Gert de Cooman, Filip Hermans, Marco Zaffalon and Alessandro Antonucci

Abstract: We focus on credal nets, which are graphical models that generalise Bayesian nets to imprecise probability. We replace the notion of strong independence commonly used in credal nets with the weaker notion of epistemic irrelevance, which is arguably more suited for a behavioural theory of probability. Focusing on directed trees, we show how to combine the given local uncertainty models in the nodes of the graph into a global model, and we use this to construct and justify an exact message-passing algorithm that computes updated beliefs for a variable in the tree. The algorithm, which is linear in the number of nodes, is formulated entirely in terms of coherent lower previsions, and is shown to satisfy a number of rationality requirements. We supply examples of the algorithm’s operation, and report an application to on-line character recognition that illustrates the advantages of our approach for prediction. We comment on the perspectives, opened by the availability, for the first time, of a truly efficient algorithm based on epistemic irrelevance.

Read the rest of this entry »

New journal paper: Exchangeable lower previsions

Exchangeable lower previsions (pdf)
by Gert de Cooman, Erik Quaeghebeur and Enrique Miranda

Abstract: We extend de Finetti’s [Ann. Inst. H. Poincaré 7 (1937) 1-68] notion of exchangeability to finite and countable sequences of variables, when a subject’s beliefs about them are modelled using coherent lower previsions rather than (linear) previsions. We derive representation theorems in both the finite and countable cases, in terms of sampling without and with replacement, respectively.

Read the rest of this entry »

De Monty Hall-puzzel

In de Monty Hall-televisieshow wordt een spel gespeeld met drie deuren. Achter een van de deuren bevindt zich een auto, en achter elk van de andere twee staat een geit verborgen. De speler duidt een van deze deuren aan. Gastheer Monty opent een andere deur, met een geit erachter. En dan mag jij een van de twee ongeopende deuren openen, waarbij je wint wat erachter staat. Welke deur kies je het beste: die die je het eerst koos, of de overblijvende? Dus: blijf je bij je eerste keuze, of verander je?

Read the rest of this entry »

Reaction to Lotfi Zadeh’s `What is probability?’

The following is a post I published elsewhere in a previous version of my blog, on 28 March 2009.

Dear Professor Zadeh,

This piece is intended as a comment on recent posts about probability theory to the BISC mailing list, in reaction to your initial post of 18 March 2009, called `What is probability?’. You clarified and revised the text a bit in your message of 25 March 2009.

You and I have argued, both in private and in public, about the issues raised there a few times before. Since I have never really summed up my point of view to you, I thought this might be a good opportunity.

If I try to reduce what you say in your message to its bare essentials, I come up with the following:

Consider (some person’s assessment of) the probability of an event. Then, first of all, this probability need not be a precise number, and we need a theory to deal with this. And, secondly, probability theory has always considered events to belong to the realm of two-valued logic: they either occur or they don’t, tertium non datur. And, so you argue, we need to be able to deal with what you call fuzzy events, which may occur to some degree.

The work that many people, including me, have been doing in what I shall call Imprecise Probabilities for want of a commonly accepted name (see Peter Walley’s book [5] for a good starting point, SIPTA may also be of interest) is related to the first observation: probability need not be a precise number. I shall try and deal with this first, before turning to your second point, probabilities of fuzzy events.

Read the rest of this entry »