Research topics
XAI

The multi-population replicator dynamics (RD) is a dynamic approach to coevolving populations and multi-player games. In general, not every equilibrium is a Nash equilibrium of the underlying game, and convergence is not guaranteed. In particular, no interior equilibrium can be asymptotically stable in the multi-population RD, resulting, e.g., in cyclic orbits around a single interior NE. We introduce a new notion of equilibria of RD, called mutation limits, which is invariant under the specific choice of mutation parameters. We prove the existence of mutation limits for a large class of games, and consider a particularly interesting subclass, called attracting mutation limits, which offer approximate solution even if the original dynamic is not convergent. Thus, mutation stabilises the system in certain cases and makes attracting mutation limits near-attainable. We observe that mutation limits have some similarity to Q-learning in multi-agent reinforcement learning. We are interested in investigating such relationship in the context of variational principles.

Featured publication:

Bauer, J., Broom, M. and Alonso, E. (2019). The stabilization of equilibria in evolutionary game dynamics through mutation: mutation limits in evolutionary games. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 475(2231). doi:10.1098/rspa.2019.0355.

We are interested in studying the problem of solving parity games. Solving parity games is equivalent to do model-checking on some fixpoint logics which in turn is used for computer systems verification. A long-standing open problem on parity games asks whether they can be solved in polynomial time. Recent exciting breakthroughs have achieved quasi-polynomial time. Together with researchers from the University of Warwick, the University of Warsaw (Poland) and the University of Bordeaux (France), we have proved that many of the recently introduced quasi-polynomial algorithms to solve parity games can be put under a common framework and that under this framework, no one can hope to reach a better bound than quasi-polynomial time. This shows that new techniques still need to be developed in the quest of a polynomial time algorithm for solving parity games.

Featured publication:

W. Czerwiński, L. Daviaud, N. Fijalkow, M. Jurdziński, R. Lazić, P. Parys (2019). Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. Proceedings of SODA 2019.

We develop methods to infer and quantify the distribution of information among sets of multivariate data. Understanding how sets of features contain information with respect to a task-relevant output variable has implications for data compression, model selection, and to determine the transferability of predictions across domains. Given the existence of interactions between the features, these methods are useful for feature selection considering a trade-off between information extraction and privacy or fairness. The characterization of the distribution of information in multivariate variables is also increasingly applied to explain the nature of encoding within and across layers in deep networks, hence advancing towards more explainable algorithms.

We contributed to an information-theoretic framework that identifies redundant, unique, and synergistic pieces of information that can be extracted from a multivariate data set, or from lower dimensional features. We study how the nature of information is transformed when only subsets of data are available, in the presence for example of latent variables. We haved developed refined estimators using convex optimization techniques and we used benchmark data to investigate the sensitivity of measures of synergy and redundancy.

Featured publications:

Makkeh A, Chicharro D, Theis DO, Vicente R. (2019) Maxent3D_PID: An estimator for the maximum-entropy trivariate partial information decomposition. Entropy 21(9):862.

Chicharro D, Pica G, Panzeri S. (2018) The identity of information: how deterministic dependencies constrain information synergy and redundancy. Entropy 20(3):169

We study how to infer the causal structure that underlies observational data. While traditionally the identification of the causal structure has relied on the analysis of independencies between observed variables, this approach is limited in the presence of hidden variables or selection bias, which can induce ubiquitous confounding dependencies.

We have combined dimensionality reduction techniques and nonlinear regression methods to infer latent factors within multivariate data and use them to obtain additional information about the causal structure. Furthermore, we study how to use low dimensional mediating variables as tools to estimate the effect of interventions that modify the structure of a system. We have developed algorithms of causal learning with an increased inferential power, which can be used to refine model design or for causal representation learning, namely informing the selection of architectures that embed the causal structure underlying the data. This promises to provide more robust transferrable representations, by capturing the invariance properties associated with the generative mechanisms underlying the data.

Featured publications:

Chicharro D, Besserve M, Panzeri S. Causal learning with sufficient statistics: an information bottleneck approach (arXiv:2010.05375)

Chicharro D, Panzeri S, Shpitser I. Conditionally-additive-noise models for structure learning. (arXiv:1905.08360)