Bullo, Francesco
Firing Rate Models as Associative Memory: Excitatory-Inhibitory Balance for Robust Retrieval
Betteti, Simone, Baggio, Giacomo, Bullo, Francesco, Zampieri, Sandro
Firing rate models are dynamical systems widely used in applied and theoretical neuroscience to describe local cortical dynamics in neuronal populations. By providing a macroscopic perspective of neuronal activity, these models are essential for investigating oscillatory phenomena, chaotic behavior, and associative memory processes. Despite their widespread use, the application of firing rate models to associative memory networks has received limited mathematical exploration, and most existing studies are focused on specific models. Conversely, well-established associative memory designs, such as Hopfield networks, lack key biologically-relevant features intrinsic to firing rate models, including positivity and interpretable synaptic matrices that reflect excitatory and inhibitory interactions. To address this gap, we propose a general framework that ensures the emergence of re-scaled memory patterns as stable equilibria in the firing rate dynamics. Furthermore, we analyze the conditions under which the memories are locally and globally asymptotically stable, providing insights into constructing biologically-plausible and robust systems for associative memory retrieval.
Input-Driven Dynamics for Robust Memory Retrieval in Hopfield Networks
Betteti, Simone, Baggio, Giacomo, Bullo, Francesco, Zampieri, Sandro
The Hopfield model provides a mathematically idealized yet insightful framework for understanding the mechanisms of memory storage and retrieval in the human brain. This model has inspired four decades of extensive research on learning and retrieval dynamics, capacity estimates, and sequential transitions among memories. Notably, the role and impact of external inputs has been largely underexplored, from their effects on neural dynamics to how they facilitate effective memory retrieval. To bridge this gap, we propose a novel dynamical system framework in which the external input directly influences the neural synapses and shapes the energy landscape of the Hopfield model. This plasticity-based mechanism provides a clear energetic interpretation of the memory retrieval process and proves effective at correctly classifying highly mixed inputs. Furthermore, we integrate this model within the framework of modern Hopfield architectures, using this connection to elucidate how current and past information are combined during the retrieval process. Finally, we embed both the classic and the new model in an environment disrupted by noise and compare their robustness during memory retrieval.
Learning Neural Contracting Dynamics: Extended Linearization and Global Guarantees
Jaffe, Sean, Davydov, Alexander, Lapsekili, Deniz, Singh, Ambuj, Bullo, Francesco
Global stability and robustness guarantees in learned dynamical systems are essential to ensure well-behavedness of the systems in the face of uncertainty. We present Extended Linearized Contracting Dynamics (ELCD), the first neural network-based dynamical system with global contractivity guarantees in arbitrary metrics. The key feature of ELCD is a parametrization of the extended linearization of the nonlinear vector field. In its most basic form, ELCD is guaranteed to be (i) globally exponentially stable, (ii) equilibrium contracting, and (iii) globally contracting with respect to some metric. To allow for contraction with respect to more general metrics in the data space, we train diffeomorphisms between the data space and a latent space and enforce contractivity in the latent space, which ensures global contractivity in the data space. We demonstrate the performance of ELCD on the $2$D, $4$D, and $8$D LASA datasets.
Multiplayer Homicidal Chauffeur Reach-Avoid Games: A Pursuit Enclosure Function Approach
Yan, Rui, Duan, Xiaoming, Zou, Rui, He, Xin, Shi, Zongying, Bullo, Francesco
This paper presents a multiplayer Homicidal Chauffeur reach-avoid differential game, which involves Dubins-car pursuers and simple-motion evaders. The goal of the pursuers is to cooperatively protect a planar convex region from the evaders, who strive to reach the region. We propose a cooperative strategy for the pursuers based on subgames for multiple pursuers against one evader and optimal task allocation. We introduce pursuit enclosure functions (PEFs) and propose a new enclosure region pursuit (ERP) winning approach that supports forward analysis for the strategy synthesis in the subgames. We show that if a pursuit coalition is able to defend the region against an evader under the ERP winning, then no more than two pursuers in the coalition are necessarily needed. We also propose a steer-to-ERP approach to certify the ERP winning and synthesize the ERP winning strategy. To implement the strategy, we introduce a positional PEF and provide the necessary parameters, states, and strategies that ensure the ERP winning for both one pursuer and two pursuers against one evader. Additionally, we formulate a binary integer program using the subgame outcomes to maximize the captured evaders in the ERP winning for the pursuit task allocation. Finally, we propose a multiplayer receding-horizon strategy where the ERP winnings are checked in each horizon, the task is allocated, and the strategies of the pursuers are determined. Numerical examples are provided to illustrate the results.
IDKM: Memory Efficient Neural Network Quantization via Implicit, Differentiable k-Means
Jaffe, Sean, Singh, Ambuj K., Bullo, Francesco
Compressing large neural networks with minimal performance loss is crucial to enabling their deployment on edge devices. (Cho et al., 2022) proposed a weight quantization method that uses an attention-based clustering algorithm called differentiable $k$-means (DKM). Despite achieving state-of-the-art results, DKM's performance is constrained by its heavy memory dependency. We propose an implicit, differentiable $k$-means algorithm (IDKM), which eliminates the major memory restriction of DKM. Let $t$ be the number of $k$-means iterations, $m$ be the number of weight-vectors, and $b$ be the number of bits per cluster address. IDKM reduces the overall memory complexity of a single $k$-means layer from $\mathcal{O}(t \cdot m \cdot 2^b)$ to $\mathcal{O}( m \cdot 2^b)$. We also introduce a variant, IDKM with Jacobian-Free-Backpropagation (IDKM-JFB), for which the time complexity of the gradient calculation is independent of $t$ as well. We provide a proof of concept of our methods by showing that, under the same settings, IDKM achieves comparable performance to DKM with less compute time and less memory. We also use IDKM and IDKM-JFB to quantize a large neural network, Resnet18, on hardware where DKM cannot train at all.
RoSSO: A High-Performance Python Package for Robotic Surveillance Strategy Optimization Using JAX
John, Yohan, Hughes, Connor, Diaz-Garcia, Gilberto, Marden, Jason R., Bullo, Francesco
To enable the computation of effective randomized patrol routes for single- or multi-robot teams, we present RoSSO, a Python package designed for solving Markov chain optimization problems. We exploit machine-learning techniques such as reverse-mode automatic differentiation and constraint parametrization to achieve superior efficiency compared to general-purpose nonlinear programming solvers. Additionally, we supplement a game-theoretic stochastic surveillance formulation in the literature with a novel greedy algorithm and multi-robot extension. We close with numerical results for a police district in downtown San Francisco that demonstrate RoSSO's capabilities on our new formulations and the prior work.
How social influence affects the wisdom of crowds in influence networks
Tian, Ye, Wang, Long, Bullo, Francesco
A long-standing debate is whether social influence improves the collective wisdom of a crowd or undermines it. This paper addresses this question based on a naive learning setting in influence systems theory: in our models individuals evolve their estimates of an unknown truth according to the weighted-average opinion dynamics. A formal mathematization is provided with rigorous theoretical analysis. We obtain various conditions for improving, optimizing and undermining the crowd accuracy, respectively. We prove that if the wisdom of finite-size group is improved, then the collective estimate converges to the truth as group size increases, provided individuals' variances are finite. We show that whether social influence improves or undermines the wisdom is determined by the social power allocation of the influence system: if the influence system allocates relatively larger social power to relatively more accurate individuals, it improves the wisdom; on the contrary, if the influence system assigns less social power to more accurate individuals, it undermines the wisdom. At a population level, individuals' susceptibilities to interpersonal influence and network centralities are both crucial. To improve the wisdom, more accurate individuals should be less susceptible and have larger network centralities. Particularly, in democratic influence networks, if relatively more accurate individuals are relatively less susceptible, the wisdom is improved; if more accurate individuals are more susceptible, the wisdom is undermined, which is consistent with the reported empirical evidence. Our investigation provides a theoretical framework for understanding the role social influence plays in the emergence of collective wisdom.
Modeling Human-AI Team Decision Making
Ye, Wei, Bullo, Francesco, Friedkin, Noah, Singh, Ambuj K
AI and humans bring complementary skills to group deliberations. Modeling this group decision making is especially challenging when the deliberations include an element of risk and an exploration-exploitation process of appraising the capabilities of the human and AI agents. To investigate this question, we presented a sequence of intellective issues to a set of human groups aided by imperfect AI agents. A group's goal was to appraise the relative expertise of the group's members and its available AI agents, evaluate the risks associated with different actions, and maximize the overall reward by reaching consensus. We propose and empirically validate models of human-AI team decision making under such uncertain circumstances, and show the value of socio-cognitive constructs of prospect theory, influence dynamics, and Bayesian learning in predicting the behavior of human-AI groups.
Robust Implicit Networks via Non-Euclidean Contractions
Jafarpour, Saber, Davydov, Alexander, Proskurnikov, Anton V., Bullo, Francesco
Implicit neural networks, a.k.a., deep equilibrium networks, are a class of implicit-depth learning models where function evaluation is performed by solving a fixed point equation. They generalize classic feedforward models and are equivalent to infinite-depth weight-tied feedforward networks. While implicit models show improved accuracy and significant reduction in memory consumption, they can suffer from ill-posedness and convergence instability. This paper provides a new framework to design well-posed and robust implicit neural networks based upon contraction theory for the non-Euclidean norm $\ell_\infty$. Our framework includes (i) a novel condition for well-posedness based on one-sided Lipschitz constants, (ii) an average iteration for computing fixed-points, and (iii) explicit estimates on input-output Lipschitz constants. Additionally, we design a training problem with the well-posedness condition and the average iteration as constraints and, to achieve robust models, with the input-output Lipschitz constant as a regularizer. Our $\ell_\infty$ well-posedness condition leads to a larger polytopic training search space than existing conditions and our average iteration enjoys accelerated convergence. Finally, we perform several numerical experiments for function estimation and digit classification through the MNIST data set. Our numerical results demonstrate improved accuracy and robustness of the implicit models with smaller input-output Lipschitz bounds.
A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
Cisneros-Velarde, Pedro, Bullo, Francesco
Problem statement and motivation There has been a recent interest in studying systems of ODEs that solve an optimization problem -- also known as optimization flows -- with the understanding that their study can lead to the analysis and design of discrete-time solvers of optimization problems - also known as optimization algorithms. This interest is motivated by the fact that analyzing a system of ODEs can be much simpler than analyzing a discrete system. Indeed, the ambitious goal of this research area is to find a "general theory mapping properties of ODEs into corresponding properties for discrete updates" -- as quoted from the seminal work [20]. Our paper aims to provide a solution to this problem. Ideally, the desired pipeline is to first design an optimization flow -- using all the machinery of dynamical systems analysis -- with good stability and convergence properties, and then formulate a principled way of guaranteeing such good properties translate to its associated optimization algorithm through discretization. A first problem in the literature is that the analysis of the optimization algorithm is commonly done separately or independently from the analysis of its associated optimization flow (e.g., see [24, 25, 17, 26, 18, 12]), instead of the former analysis following directly as a consequence of the latter one. For example, separate Lyapunov analyses have been made for optimization flows and their associated algorithms. This problem diminishes one of the very first motivations of analyzing a system of ODEs, namely, that its analysis should directly establish properties of its associated discretization.