Post date: May 06, 2017 2:51:32 AM
Dear all,
Here is my initial take on the subject. This is not a topic that I am an expert in but the idea of algorithms handling uncertainty (and in particular paragraph 17) rang the bell of a talk by Mark Girolami I attended some months ago. He and others are proposing what they call Probabilistic Numerics (PN). I documented myself on the subject to have a better understanding.
In a nutshell, PN concerns itself with designing algorithms that quantify computational uncertainty stemming from the loss of precision due to limitations in time or hardware. One of its main motivations is that the quantification of uncertainty through Probability Theory is well established when the subject of inference has a physical meaning. The question that PN attempts to answer is whether this inference can be extended to mathematical statements and computer code output. In doing so, it is important to distinguish this type of uncertainty from other types that are also present in computation, namely:
(i) Epistemic uncertainty arising from the modelling, rather than the computation itself,
(ii) Aleatory uncertainty arising from repeated computations, e.g. Monte Carlo,
(iii) Error estimation. This is usually employed for the purpose of establishing stopping criteria for an algorithm and cannot be interpreted as a general property (e.g. a statistic) of a probability distribution. Instead, error estimation is a diagnostic tool.
<<Scott says: Maybe we need some concrete examples. Is the uncertainty that comes from not being sure about your mesh size one of these uncertainties? Or the residual uncertainty you have from having picked a particular solution strategy over an alternative one? I wonder whether a small Monte Carlo replication number would count as the kind of uncertainty that PN is concerned with. It comes from a "limitation in time" and it generates ""epistemic uncertainty arising from the modeling" (although it comes, I would say, from the "computation itself"). I don't think statisticians have any doubt that probability theory can be extended to computer code output. It's one of the few domains where random sampling is actually believable as an assumption. They do that all the time.>>
Scott mentions at the beginning of the text that algorithms are formulas or decision processes to arrive at a computational answer. In addition, PN sees algorithms as inference rules used to reason about latent or hidden quantities using data. Numerical computations can therefore be viewed as inference problems which give rise to probabilistic numerical methods. Note that this is not entirely a new idea. The application of probabilistic methods to solve deterministic problems has been around for a long time. For example, estimating the value of Pi using Monte Carlo sampling (Buffon). The same principle can be applied to compute multidimensional integrals where nothing in the formulation is inherently stochastic. Another relevant example is the emulation of a computer model. This is the same as imposing a probability distribution on a space of functions, whereby the mean of the resulting predictive posterior is used as a surrogate for the original, expensive model. PN attempts to go further and investigate whether similar principles can be applied to the most fundamental numerical routines: the solution of linear systems, optimisation, numerical PDEs, amongst many others. These methodologies are at the core of the vast majority of algorithms. PN is an emerging field that might lay the foundation of a calculus for the propagation of uncertainty through computation.
If you think that what I've written above is not too off-topic, then I can dig deeper into the PN literature. Some of the papers are quite heavy, but I am interested in giving it a go.
Other aspects in which I feel I could contribute are the following:
Paragraph 8. The topic of publishing algorithms could be related to free and open source software (see Richard Stallman, an old but relevant idea in my opinion). It is also related to reproducibility (Neil Lawrence, from Amazon and Roger Peng & Jeff Leek, John Hopkins). They have published interesting work on this topic, although more focused on reproducibility of academic research.
Paragraph 11. I believe this is more related to a sampling problem rather than an algorithmic problem.
Let me know what you think!