Personal homepage Johan Kwisthout

I am internationally recognized as one of the experts on computational complexity aspects of Bayesian networks, which was also the topic of my PhD research. After my PhD period I specialized in the complexity of approximating the most probable explanation for observed variables in such networks. I proposed a new heuristic, so-called Most Frugal Explanation, for this computationally intractable problem. In addition, I proposed new parameterized complexity classes that capture the notion of efficient randomized computations. In contrast to the traditional parameterized complexity class FPT, these new classes parameterize the probability of answering correctly, rather than computation time.

Later, I became interested in (resource-bounded) probabilistic inferences in the brain, in particular in the context of the "Predictive Processing" account in neuroscience. Together with researchers at the Donders Institute for Brain, Cognition, and Behaviour, I contributed computational models and mathematical formalizations to this account. In particular, I identified the level of detail of predictions and the trade-off between making precise predictions and predictions that are likely to be correct as crucial aspects of the theory. I also contributed computational models of various mechanisms of prediction error minimization and studied the computational complexity of sub-processes in the Predictive Processing account. In our group we studied how how the generative models are developed in infancy and how the Bayesian Brain hypothesis can be tractable.

Currently, my focus is on Probabilistic Graphical Models for Decision Support Systems and on Foundations of Stochastic Computing. The first line will focus on explainability, trustworthiness, maintainability, online or federated learning etc. in Bayesian networks and other PGM models, particularly with an application in clinical decision support systems. Key project in this line is in the Personalised Care in Oncology consortium of which I am programme leader. Furthermore, I am work package co-lead in the Healthy Data initiative. The second research line will focus on topics such as approximate Bayesian inference, (parameterized) complexity classes for stochastic computing, and realization of probability distributions and computations on them in novel materials and computing architectures. More particularly, we study the parameterized tractability of approximate Bayesian inferences, we search for novel approximation techniques, and the study how to formalize the extension of PGMs with new variables or values of variables. A novel interest is in implementing resource-bounded stochastic computations in novel materials and in brain-inspired neuromorphic systems. Our fundamental work in this area is in particular in formalizing a novel computational complexity theory for neuromorphic hardware, designing neuromorphic algorithms, and implementing Bayesian inferences in neuromorphic hardware. A new project in this line is in designing new MCMC algorithms using covarying random bits realised in magnetic fields.

Physicists have discovered new ways to store information in magnetic fields, allowing for representing and adjusting bits (0/1) at ultra-high speeds with ultra-low energy costs. However, at this microscopic level, it is difficult to manipulate bits without potentially disturbing neighbouring bits, for example due to quantum effects. In this project we investigate how this so-called stochastic covariance can be used to make more (energy-) efficient algorithms, and contribute to our understanding of how non-fully independent random bits can be seen as a computational resource. We focus at Markov chain Monte Carlo algorithms that quickly explore a state space by sampling. This technique is often used in intensive computing simulations like climate change modelling that we want to make more efficient.

This project is funded by an NWO Emerging Key Technologies competition grant awarded to a consortium (funding three PhDs) with Johan Mentink as main applicant and Johan Kwisthout as one of the co-applicants.

The diagnosis, treatment, and follow-up of cancer patients is mostly focused on standardized medical knowledge and protocols, with little attention for the patient's expectations about their quality of life during and after treatment. Important reasons for the lack of patient-focused care are the current limitations of clinical decision support systems. These tools combine a statistical clinical model with personal data to advise on the best possible next step; however, their lack of good explanation and justification methods, static nature, and weak embedding in the clinical work flow hinders the optimal employment of these AI tools. In the Personalised Care in Oncology programme we develop the next generation of clinical decision support systems that allow for shared decision making about personalized care.

See our website www.personalisedcareinoncology.nl.

This project is funded by an Ministry of EZK and NWO Perspectief competition grant awarded to a consortium with Johan Kwisthout as main applicant. Natan T'Joens is postdoc in our group funded on this project.

In scientific computing, AI techniques are often used to approximate otherwise infeasible computations. A well-known AI technique to sample a large state space is Markov chain Monte Carlo (MCMC) sampling. In the search for smaller, faster, and more efficient ways of storing and manipulating bits of information in physical structures of a few nanometres (e.g., in skyrmion dynamics), physicists have met increased difficulties to mitigate fluctuations and co-varying state transitions. Engineering fully random noise at the nano-level is challenging as these fluctuations lead to cross-correlations and introduce covariance in random bit streams. This project takes a radically different approach: rather than trying to mitigate covariance, we turn this challenge into an opportunity and use this covarying random noise for free. In this project we develop and analyse new MCMC algorithms that exploit conditional independence in the multivariate distribution to reduce the amount of fully random bit generators needed. This anticipates the future availability of energy-efficient, high-density, covarying computing elements.

This project is partially funded by an AINed XS Europa grant awarded to Johan Kwisthout (applicant), and by an NWO Emerging Key Enabling Technologies grant awarded to a consortium with Johan Kwisthout as co-applicant .

Bayesian inference is an intractable (NP-hard) problem even when only an approximate solution is sought, implying that well-known approximation techniques for Bayesian inference include variational Bayes, Metropolis-Hasting sampling, and likelihood weighting only work well on a subset of problem instances, and cannot give a guaranteed quality of approximation in general. This limits the applicability of Bayesian networks for real world applications.

In this PhD project we investigate a new approach towards approximate Bayesian inference, i.e., we translate an inference problem to a weighted satisability instance, apply approximation strategies to give an approximate count of the (weighted) number of models of the instance, and then translate the solution back to the inference problem. This approach may open up new avenues as it allows for a new class of approximation strategies based on hashing rather than sampling or model simplification to approximately count models. Currently, however, the state-of-the-art techniques are not yet well suited for the instances that arise from the translation from a Bayesian network to a weighted satisability problem. In this project we study how this translation can adjusted such that hashing approaches work, and study both experimentally and by formal parameterized complexity analysis whether this allows for a novel sub-set of Bayesian inference problems that can be tractably approximated.

This project is funded by an NWO exact sciences M1 open competition grant awarded to Johan Kwisthout (M21.136).

In traditional (Von Neumann) computer architectures computation and memory are physically separated by a (relatively slow) data bus, requiring excessive data transfer with every instruction cycle and high energy consumption as a consequence. This has accelerated the development of so-called neuromorphic architectures that, inspired by the structure of the brain, co-locate computation and memory in artificial (spiking) neural networks. This allows for a new way of thinking about algorithms and data and designing energy-efficient algorithms that encode information in time-dependent spiking behaviour. Theory, however, is now seriously lagging behind hardware innovations. We do not yet fully understand and utilize the potential and limitations of these new architectures. In this research project we lay the foundations for an urgently needed computational complexity framework for neuromorphic hardware focusing on energy as a vital resource. Foundational complexity-theoretical work is augmented by a parallel project, supported by Intel, where we translate abstract algorithms on generic computing devices to actual implementations on Intel's new Loihi architecture, allowing us to validate and refine the theoretical models. Theoretical and practical research together will lay a firm foundation for the further development of energy-efficient computing to help reducing carbon footprints.

This project is partially funded by an Intel Neuromorphic Research Community grant awarded to Johan Kwisthout (applicant).

Computing posterior and marginal probabilities constitutes the backbone of almost all inferences in Bayesian networks. These computations are known to be intractable in general; moreover, it is known that approximating these computations is also NP-hard. These theoretical results are in stark contrast with common experience in practical randomized approximation algorithms that often -but not always!- are able to approximate large-scale inferences. Our understanding of when, why, and how randomized approximate inference can be tractable in Bayesian networks is currently still limited.

This is even more problematic as this hinders progress in other scientific disciplines, in particular cognitive science and neuroscience. The influential `Predictive Processing' account of cortical processes in neuroscience is explicitly built on the formal machinery of approximate Bayesian computations. There is an urgent need for a deeper theoretical understanding of these computations and the constraints that need to be imposed on their inputs such as to ensure tractability - a crucial prerequisite for neuronal implementation. However, recent advances in the area of parameterized complexity theory, where recently a randomized analogue of fixed-parameter tractability has been proposed, allow us to now tackle these questions.

In this project our goal is to thoroughly study these computations from different perspectives: studying structural properties of fixed-error randomized tractability ("Fundamentals"); designing and analysing efficient and predictable approximation algorithms that allow to trade off sampling and marginalizing in inference ("Engineering"); and studying the neuroscientific claim that predicting inputs based on generative models allows for efficient approximate computations by the brain ("Reverse Engineer").

This project is funded by an NWO exact sciences TOP grant awarded to Johan Kwisthout (612.001.601).

An influential theoretical position in cognitive neuroscience is that the brain is a 'prediction machine' that uses internal generative models to guide perception and action. Integrating new information with existing internal models is a crucial 'operation' that underlies learning and education, but also development, behaviour change, creativity, incident recovery, and drug rehabilitation. When cast into Bayesian terms (e.g., predictive coding) this integration translates into (non-parametric) changes to the structure of existing models, such as the introduction of new variables, the conditioning of an existing variable on a new contextual dependence, or the re-allocation of probability mass over variables. There is currently no formal framework that systematically addresses these operations, which seriously constrains scientists that aim to use Bayesian computational models to describe (neuro-)cognitive phenomena (and interpret data) that require structure changes in internal models. In this project we will develop such a formal framework to remedy this omission.

This project was funded by an internal DCC PhD-grant awarded to Johan Kwisthout (main applicant) and Iris van Rooij (co-applicant).

The Predictive Processing account in neuroscience is becoming increasingly popular as a unifying explanation of the brain's modus operandi. Despite its empirical and theoretical successes, the Predictive Processing account is still lacking one key ingredient: A computational explanation of how the generative models (that allow for making predictions) are formed, shaped, and adapted to reflect new experiences in the world. What is studied in Predictive Processing is typically the adult brain, not the brain under development in infancy. How prediction errors shape the generative models that are assumed in this account is currently a major gap in our knowledge.

In this project we will address this 'developability' issue and provide insights in the computational mechanisms that allow for learning and development in Predictive Processing, using a combination of computational formal modeling, behavioral infant research, and developmental robotics. We will study when and how generative models are updated, revised, and refined; how these distinct mechanisms interact in development, and what mechanistic explanations can account for individual differences in infant learning strategies. This 'enrichment' of Predictive Processing will pave the way for a solid theoretical framework for infant research and will provide valuable insights in how learning might be facilitated.

This project was funded by an internal DCC PhD-grant awarded to Johan Kwisthout and Sabine Hunnius (joint applicants).

According to a prominent hypothesis in cognitive neuroscience, known as the Bayesian Brain hypothesis, the brain's cognitive prowess can be explained by assuming that it can perform a variety of probabilistic (a.k.a. Bayesian) inference. The Bayesian brain hypothesis seems descriptively powerful enough to characterize the cognitive competence of the human brain. Yet, it raises a theoretical challenge for explaining its computational efficiency. The reason is that, in current theory, even only approximately computing Bayesian inferences can take years or centuries for the non-trivial situations that humans effortlessly deal with in their everyday life. In contrast, cognitive brain processing occurs in practice on a timescale of seconds or milliseconds. How can this paradox between theory and practice be resolved?

In this project, we set out to answer this question by developing a new theory that can explain how a brain can efficiently approximate Bayesian inference for a wide range of situations. Using an innovative approach that combines formal modeling with complexity analysis, we will identify parameters of a computational architecture that can make a Bayesian brain computationally efficient. The newly developed theory will be an important contribution to cognitive neuroscience as it will (a) deepen our understanding of the brain's remarkable cognitive inferential abilities as well as its intrinsic computational limitations; (b) serve to bring more computational rigor to philosophical discussions about the viability of Bayesian, optimal and rational explanations; and (c) yield novel predictions about the brain's architecture and cognitive performance that can guide future empirical research in cognitive neuroscience.

This project was funded by an internal DCC PhD-grant awarded to Iris van Rooij (first applicant) and Johan Kwisthout (co-applicant).