### Credal trees under irrelevance

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

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

Geoff Cumming in Mind your confidence interval: how statistics skew research results. To get started on the slippery slope (upwards, I hope) …

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.

I have always had trouble imagining what that could mean, until I saw this close-up of Ettore Ferrari‘s bronze statue of Giordano Bruno, in Stephen Greenblatt‘s `The Swerve: How The World Became Modern’.

Look for a picture of the statue in its entirety: the contrast is very interesting.

Sarah Bakewell’s *How to Live: A Life of Montaigne in One Question and Twenty Attempts at An Answer* has turned out to be a very interesting read, indeed. It has made me consider going back to Nietzsche, and picking up the volume of collected works that I failed to get enthusiastic about and consequently put down, so many years ago: I must have been far too young and reckless and mindless to appreciate gems like this one:

Unter die kleinen, aber zahllos häufigen und deshalb sehr wirkungsvollen Dinge, auf welche die Wissenschaft mehr Acht zu geben hat, als auf die großen seltenen Dinge, ist auch das Wohlwollen zu rechnen; ich meine jene Äußerungen freundlicher Gesinnung im Verkehr, jenes Lächeln des Auges, jene Händedrücke, jenes Behagen, von welchem für gewöhnlich fast alles menschliche Tun umsponnen ist. Jeder Lehrer, jeder Beamte bringt diese Zutat zu dem, was für ihn Pflicht ist, hinzu; es ist die fortwährende Betätigung der Menschlichkeit, gleichsam die Wellen ihres Lichtes, in denen Alles wächst; namentlich im engsten Kreise, innerhalb der Familie, grünt und blüht das Leben nur durch jenes Wohlwollen. Die Gutmütigkeit, die Freundlichkeit, die Höflichkeit des Herzens sind immerquellende Ausflüsse des unegoistischen Triebes und haben viel mächtiger an der Kultur gebaut, als jene viel berühmteren Äußerungen desselben, die man Mitleiden, Barmherzigkeit und Aufopferung nennt. Aber man pflegt sie geringzuschätzen, und in der Tat: es ist nicht gerade viel Unegoistisches daran. Die Summe dieser geringen Dosen ist trotzdem gewaltig, ihre gesamte Kraft gehört zu den stärksten Kräften. — Ebenso findet man viel mehr Glück in der Welt, als trübe Augen sehen: wenn man nämlich richtig rechnet, und nur alle jene Momente des Behagens, an welchen jeder Tag in jedem, auch dem bedrängtesten Menschenleben reich ist, nicht vergisst.

Thanks, Sarah, for making me go back and reconsider.

So good: “Unofficial title sequence for ‘The Adventures of Tintin‘, featuring elements from each of the 24 books.” by James Curran.

Via @khoi.

Kiva is “a non-profit organization with a mission to connect people through lending to alleviate poverty. Leveraging the internet and a worldwide network of microfinance institutions, Kiva lets individuals lend as little as $25 to help create opportunity around the world.”

I like what they do, and how they go about it.

But go and have a look at their website, and decide for yourself whether what they do is useful or relevant.

What would you think if I insisted on repeating the same infuriatingly patronizing line each and every time I spoke to you?

I like Sarah Bakewell’s article on Lucretius’ *De Rerum Natura* in the New York Times Sunday Book Review, perhaps because my thinking about life and its meaning have been deeply influenced by both Lucretius and Michel de Montaigne. Bakewell’s biography of Montaigne, *How to Live: A Life of Montaigne in One Question and Twenty Attempts at An Answer,* is apparently well reviewed, and definitely next on my reading list.

Every year, I find delight in annoying my engineering students by reading aloud, in Lucretius’~~s~~ beautiful Latin, a number of lines relevant to Brownian motion during my lectures on probability:

contemplator enim, cum solis lumina cumque

inserti fundunt radii per opaca domorum:

multa minuta modis multis per inane videbis

corpora misceri radiorum lumine in ipso

et velut aeterno certamine proelia pugnas

edere turmatim certantia nec dare pausam

conciliis et discidiis exercita crebris, …

Annoying, well perhaps not, my hope is that at least some feel the attraction of the sounds and cadence, and the lure of ideas barely making it through the centuries, to be taken up and given new vigor when the time is right for them.

Update: I’m thinking “Lucretius’s” to be one of those cases where the “s” in “s’s” should be dropped, because it really sounds too ugly.

I am about to cough and sneeze myself through an invited talk (here’s the abstract) at the Statistische Woche, a five-day event organized in Leipzig, Germany to celebrate the 100th birthday of the Deutsche Statistische Gesellschaft.

I have just finished giving a plenary talk at NLMUA 2011, the first international conference on Nonlinear Mathematics for Uncertainty and Its Applications, held in Beijing. My aim was to convince people that recent advances in imprecise probabilities could lead to an interesting approach to stochastic processes using imprecise probability models, and that some of the underlying ideas are already being used to good advantage in imprecise Markov chains, credal networks, and in particular imprecise Hidden Markov models.

Jacqui Cheng at Ars Technica, while explaining what’s wrong with RSS:

Making a conscious (or unconscious, as the case may be) decision to scan through 20-something RSS items a few times per hour means that you’re constantly interrupting what you were doing in order to perform another task. Even if it’s a brief task, the very act of breaking your concentration means it will impact the focus and flow of whatever got shoved to the background, and it takes longer to resume that task later when you’re done with the RSS scan.

Don’t believe me? There have been numerous studies that have shown that humans are notoriously bad at multitasking in this way. Research scientist Eric Horvitz found in 2007 that Microsoft employees took an average of 15 minutes to return to the task they were working on after being interrupted by a phone call, e-mail, or instant message. A 2009 report in Proceedings of the National Academies of Science said that heavy multitaskers tended to be more readily distracted by extraneous information than their more focused peers. And a report published in Science in 2010 confirmed that single-taskers could perform work just fine, double-taskers had to split their brain processes to monitor things separately, and three or more tasks simply caused hell to break loose.

I guess we knew this all along, right?

Federico Vittici at MacStories:

It’s that feeling of times changing, of you and your friends growing older and perhaps with a better understanding of things — it’s watching what you took for granted be upgraded to something new you think will be fine eventually, but you’re still not completely used to.

Go have a look:

This might be good news about Sigur Rós, but there is very little of it, apart from this teaser.

Update: it’s about a double live album, and a film.

Here is the PDF-file for the plenary lecture I gave on 26 July 2011 during the ISIPTA’11 session devoted to Bruno de Finetti.

Later that same day, all ISIPTA participants went to the house in Innsbruck where de Finetti was born, to unveil a plaque (photo by Inés Couso, cropped):

Daring Fireball‘s John Gruber (@gruber) tweeted this quote from Stanley Kubrick:

Je hebt ons verlaten, totaal onverwacht, en ik weet nog altijd niet goed hoe ik daarmee om moet. Ik zal later wellicht kunnen nadenken over wat het voor mij betekent, nu wil ik gewoon nog even met je praten. Ik geloof niet in leven na de dood, dus praten lijkt allicht een zinloze oefening. Maar ik wil je nu bij me houden, in mijn hoofd.

Ik zag je voor het eerst op een maandag in 1987, je kwam net aan uit China, en ik heb je toen een beetje opgevangen. Opgevangen zoals een jongen van 22, die nog nooit voor iemand heeft gezorgd, dat doet, onhandig en met veel goede bedoelingen, zo goed en zo kwaad als dat gaat. Ik herinner me lessen Chinees, wandelingen in mijn geboortedorp, spaghetti bolognaise met een beetje mayonaise om je te plagen, nachtelijke trektochten door Gent, lange, lange middagen in de Overpoort, je eerste kerstavond in Gent met teveel wijn bij mijn grootvader: je kon er niet tegen, en ik heb me toen echt zorgen om je gemaakt.

Na je promotie zijn we elkaar een beetje uit het oog verloren, elk zijn leven, zoals dat soms gaat, blijkbaar. Tot ik vorig jaar in Shanghai het voorrecht had om samen met je familie, Etienne Kerre en Andrea De Kegel, en Dirk Aeyels je vijftigste verjaardag te vieren (het opvangen is toen door jou gedaan, en je was er zoveel beter in). Waarom denken we toch altijd dat we nog alle tijd van de wereld hebben?

Je was een ingoede man, en een goede wetenschapper: daar kan ik met enige kennis van zaken over spreken. En wat ik me steeds van je zal blijven herinneren (en ik ben zeker dat ik niet de enige hierin ben), Da, is hoe elke keer dat je me zag, hoe lang het ook geleden was dat we elkaar hadden gezien, je gezicht en je ogen begonnen te stralen, en je mij het gevoel gaf dat ik bijzonder voor je was.

Da, je was een schitterende kerel, en ik vond het een voorrecht dat ik je mijn vriend mocht noemen.

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.

Kirby Ferguson has just released Part 3 of his web video series Everything is a Remix.

“The act of creation is surrounded by a fog of myths. Myths that creativity comes via inspiration. That original creations break the mold, that they’re the products of geniuses, and appear as quickly as electricity can heat a filament. But creativity isn’t magic: it happens by applying ordinary tools of thought to existing materials.”

He is not suggesting that being creative is easy, or trivial, or unworthy of recognition. He is saying there is nothing magical or mysterious about it. Unweaving the rainbow …

Via Daring Fireball.

**Conglomerable natural extension** (preprint pdf)

by Enrique Miranda, Marco Zaffalon and Gert de Cooman

*Abstract*: We study the weakest conglomerable model that is implied by desirability or probability assessments: the conglomerable natural extension. We show that taking the natural extension of the assessments while imposing conglomerability—the procedure adopted in Walley’s theory—does not yield, in general, the conglomerable natural extension (but it does so in the case of the marginal extension). Iterating this process produces a sequence of models that approach the conglomerable natural extension, although it is not known, at this point, whether it is attained in the limit. We give sufficient conditions for this to happen in some special cases, and study the differences between working with coherent sets of desirable gambles and coherent lower previsions. Our results indicate that it might be necessary to re-think the foundations of Walley’s theory of coherent conditional lower previsions for infinite partitions of conditioning events.

**Independent natural extension for sets of desirable gambles** (preprint pdf)

by Gert de Cooman and Enrique Miranda

*Abstract*: We investigate how to combine a number of marginal coherent sets of desirable gambles into a joint set using the properties of epistemic irrelevance and independence. We provide formulas for the smallest such joint, called their independent natural extension, and study its main properties. The independent natural extension of maximal sets of gambles allows us to define the strong product of sets of desirable gambles. Finally, we explore an easy way to generalise these results to also apply for the conditional versions of epistemic irrelevance and independence.

**State sequence prediction in imprecise hidden Markov models** (preprint pdf)

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.

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.

**Independent natural extension **(preprint pdf)

by Gert de Cooman, Enrique Miranda and Marco Zaffalon

*Abstract: *There is no unique extension of the standard notion of probabilistic independence to the case where probabilities are indeterminate or imprecisely specified. Epistemic independence is an extension that formalises the intuitive idea of mutual irrelevance between different sources of information. This gives epistemic independence very wide scope as well as appeal: this interpretation of independence is often taken as natural also in precise-probabilistic contexts. Nevertheless, epistemic independence has received little attention so far. This paper develops the foundations of this notion for variables assuming values in finite spaces. We define (epistemically) independent products of marginals (or possibly conditionals) and show that there always is a unique least-committal such independent product, which we call the independent natural extension. We supply an explicit formula for it, and study some of its properties, such as associativity, marginalisation and external additivity, which are basic tools to work with the independent natural extension. Additionally, we consider a number of ways in which the standard factorisation formula for independence can be generalised to an imprecise-probabilistic context. We show, under some mild conditions, that when the focus is on least-committal models, using the independent natural extension is equivalent to imposing a so-called strong factorisation property. This is an important outcome for applications as it gives a simple tool to make sure that inferences are consistent with epistemic independence judgements. We discuss the potential of our results for applications in Artificial Intelligence by recalling recent work by some of us, where the independent natural extension was applied to graphical models. It has allowed, for the first time, the development of an exact linear-time algorithm for the imprecise probability updating of credal trees.

When my daughter told me she needed my iPhone to record one of her funny science experiment assignments, I thought I’d take the opportunity to learn about iMovie, and how to use it on my Mac and iPad (it’s not a shiny new iPad2, so I had to use the iPhone Configuration Utility to get iMovie to install).

Here’s mine for this week:

Libra

Everyone will think you’re just making a hilarious reference, undermining your efforts to warn everyone that the alien manifesto is, in fact, actually a cookbook.

So astonishingly accurate. Scary.

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 »

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 »