PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonparametric inference of interaction laws in systems of agents from trajectory data

Fei Lu, Mauro Maggioni, Sui Tang, Ming Zhong

arXiv:1812.06003v4cs.LGstat.ML

TL;DR

Inferring interaction laws from observations is challenging where controlled experiments and canonical models are scarce. This paper learns distance-based interaction kernels from trajectories, reporting optimal dimension-independent rates and examples of reliable model selection.

  • Problem

    In complex agent systems, controlled experiments and canonical interaction models are scarce, and interaction forms are often chosen a priori within small parametric families.

    Source: §1 · p. 1

  • Method

    A regularized Least Squares estimator learns a non-parametric interaction kernel from trajectories under the assumption that interactions depend on pairwise distances.

    Source: §1 · p. 2

  • Results

    The estimator has an optimal one-dimensional-regression convergence rate independent of state-space dimension, and examples reliably identify system order and energy- versus alignment-type interactions.

    Source: §1 · p. 2, §6 · p. 15

  • Takeaways & Limitations

    The statistical guarantees can help researchers formulate and test conjectures about models underlying observed systems.

    Source: §6 · p. 15

    The convergence rate depends on the number of random samples M, not the number of pairwise distances available across trajectories.

    Source: §3.3 · p. 8

Abstract

from arXiv · show

Inferring the laws of interaction between particles and agents in complex dynamical systems from observational data is a fundamental challenge in a wide variety of disciplines. We propose a non-parametric statistical learning approach to estimate the governing laws of distance-based interactions, with no reference or assumption about their analytical form, from data consisting trajectories of interacting agents. We demonstrate the effectiveness of our learning approach both by providing theoretical guarantees, and by testing the approach on a variety of prototypical systems in various disciplines. These systems include homogeneous and heterogeneous agents systems, ranging from particle systems in fundamental physics to agent-based systems modeling opinion dynamics under the social influence, prey-predator dynamics, flocking and swarming, and phototaxis in cell dynamics.

1 Introduction

The paper addresses how to infer interaction laws in diverse agent systems when controlled experiments and canonical interaction models are scarce. It proposes non-parametric learning from trajectories and reports dimension-independent optimal convergence rates for its estimator.

1 Introduction

  • Interacting-agent systems span physics, biology, ecology, neurobiology, social sciences, and economics, with agents ranging from particles and cells to people and opinions.Source: §1 · p. 1
  • For complex organisms, controlled experiments and canonical interaction choices are scarce, while models often assume a small parametric family and target qualitative patterns rather than quantitative agreement.Source: §1 · p. 1
  • The proposed approach learns interaction laws non-parametrically from trajectories, assuming the interaction kernel depends only on pairwise distances, and uses a regularized Least Squares estimator.Source: §1 · p. 2
  • The estimator achieves an optimal convergence rate as in one-dimensional regression, independent of state-space dimension, and can be implemented in a streaming fashion for large datasets.Source: §1 · p. 2

2 Learning interaction kernels

The section estimates a distance-based interaction kernel from agent trajectories and evaluates both kernel error and trajectory prediction. It develops sampling-regime considerations and illustrates the approach on the Lennard-Jones system.

2 Learning interaction kernels

  • Each agent’s velocity superposes interactions with other agents, weighted by pairwise distance; the estimator learns the one-variable kernel from trajectory observations.The learning setup treats observed positions along trajectories as data and uses finite differences to approximate velocities.Source: §2 · pp. 2–3
  • For Hölder-s kernels, the kernel error has rate Õ(M^-s/(2s+1)), with an exponent and constants independent of state-space dimension and agent count under the stated assumptions.The error is measured in L2(ρT), and informative error requires ρT to have wide support.Source: §2 · p. 3

2.1 Different sampling regimes, and randomness

  • The sample size in the main results is M, the number of random initial conditions; long trajectories can provide repeated effective samples in ergodic systems after mixing.With very few initial conditions or concentrated initial-state distributions, the problem approaches a fixed-design inverse problem requiring sufficiently varied pairwise distances.Source: §2.1 · pp. 4–5

2.2 Example: interacting particles with the Lennard-Jones potential

  • Increasing both trajectory count M and length L reduces relative kernel error roughly with their product, but one long trajectory does not suffice in the reported setting.The reported pattern applies when M and L are not too small; the authors link the single-trajectory limitation to limited information in a trajectory.Source: Figure 3 · p. 5, §2.2 · p. 6
  • The learned Lennard-Jones kernel predicts trajectories accurately on the training and prediction intervals, including for a system with 4N agents after training on N agents.The reported prediction intervals extend beyond training, and the transfer example uses the same type of system with more agents.Source: §2 · p. 4, §2.2 · p. 6
  • The Lennard-Jones estimation error decays at about 0.36, close to the theoretical optimal rate of 0.4.The authors attribute the difference partly to an empirical approximation of ρT and to the kernel’s singularity at zero, which is outside the theorem’s admissible class.Source: §2.2 · p. 6

3 Learning Theory

The learning theory measures kernel error over distances explored by the dynamics, then establishes conditions for learnability, convergence rates, and trajectory prediction. Under stated assumptions, the rate matches one-dimensional regression despite indirect trajectory observations.

3 Learning Theory

  • The learning objective minimizes a dynamics-based error over bounded, differentiable, finite-range kernels; the finite-range restriction may be relaxed to suitable decay.Boundedness and derivative bounds ensure global well-posedness of the system.Source: §3 · p. 6

3.1 Probability measures adapted to the dynamics

  • The measures ρT and ρL describe which pairwise-distance regions the dynamics explore, so estimation error is assessed where the system supplies distance samples.ρT depends on the initial-condition distribution and time scale; ρL also depends on the observation-time sampling scheme.Source: §3.1 · p. 6

3.2 Learnability: the coercivity condition

  • The coercivity condition ensures a unique limiting error minimizer and supports estimator convergence; it holds under exchangeable Gaussian initial conditions when L=1, with a constant independent of N.Numerical tests suggest the condition holds more broadly when the distance measure is nondegenerate, but the authors conjecture it does not always hold.Source: §3.2 · p. 7

3.3 Optimal rates of convergence

  • The estimator attains the optimal regression rate for regular kernels from trajectory data, although the rate depends on the number of trajectories rather than all observed pairwise distances.The rate matches the minimax rate for observing kernel values directly; increasing observation times may improve performance only up to the information in a single trajectory.Source: §3.3 · p. 8

3.4 Trajectory-based Performance Measures

  • The L2(ρT) kernel error also bounds trajectory prediction error, both for individual trajectories and on average over initial conditions.The trajectory bound assumes the estimated interaction kernel is Lipschitz; its constant depends on the time horizon and Lipschitz constant.Source: §3.4 · pp. 8–9

4 Extensions: Heterogeneous agent systems, first and second order

The framework extends to systems with multiple agent types and interaction kernels, including first- and second-order dynamics. These extensions retain convergence guarantees, and the opinion-dynamics example reports accurate kernel and trajectory predictions.

4 Extensions: Heterogeneous agent systems, first and second order

  • The extensions cover multiple agent types, second-order equations, and interactions with an environment, spanning a broad range of interacting-agent applications.The paper names prey-predator, leader-follower, and cars-pedestrian models as examples within the second-order family.Source: §4 · p. 9, §4.2 · p. 10

4.1 First Order Heterogeneous Agents Systems

  • For first-order heterogeneous systems, the estimator retains optimal convergence rates and provides similar control over predicted-trajectory error as in the single-type setting.The model assumes agent types are known and estimates kernels for each ordered pair of types.Source: §4.1 · p. 9

4.2 Second order heterogeneous agent systems

  • Second-order heterogeneous systems combine energy- and alignment-type interactions across agent types, with environmental response modeled through an auxiliary variable.The least-squares estimator uses a structured matrix to learn dependent interaction kernels jointly; the model assumes these kernels are the only unknowns.Source: §4.2 · pp. 10–11
  • The opinion-dynamics example reports a relative kernel error of 1.6 · 10−1 ± 2.3 · 10−3 across 10 runs and small trajectory errors, including predictions of cluster number and location.The figure compares true and estimated kernels and shows trajectories on training and future prediction intervals.Source: Figure 4 · p. 11, §4.2 · p. 11

5 Examples

The examples test kernel estimation and trajectory prediction across opinion, predator-swarm, and phototaxis systems, and use prediction errors to select between dynamical models. The estimates generally recover kernels and trajectories well, including under noisy observations and when transferring to systems with more agents.

5 Examples

  • For phototaxis, the same true kernel is learned from two different data pairs, and sparse large-distance data makes estimates taper early despite strong trajectory reproduction.The two data pairs are (r, ṙ) and (r, ξ).Source: §5 · p. 13
  • Across opinion, predator-swarm, and phototaxis examples, interaction kernels and trajectories are reported as accurately estimated and predicted.For predator-swarm systems, kernel estimates are especially close where occupancy is high; trajectory errors grow over time and can increase when predators and prey approach more closely than in training.Source: §5 · pp. 11–13
  • A learned kernel predicts trajectories for the same system with four times as many agents as in training.The paper describes the kernel as a latent variable that enables transfer across related systems.Source: §5 · p. 13
  • For energy-based models, the ˆφE norm is 18.8 ± 0.4 versus 6.5 ± 0.3 for ˆφA; for alignment-based models, the ˆφA norm is 27.6 ± 0.7 versus 2.4 · 10^-2 ± 0.1 for ˆφE.The figure reports that these estimators correctly identify each model type; its y-axes use different scales.Source: §5 · p. 14, Figure 7 · p. 14
  • First- versus second-order model selection correctly identifies the system order across 250 train-test runs using trajectory errors.The table caption describes mean and standard deviation over random initial conditions and says errors on the scale M^-2/5 indicate the correct model.Source: Table 1 · p. 14
  • The approach is reported robust to the hypothesis-space choice when the space satisfies the coercivity condition.The paper also notes that well-conditioned bases can control the least-squares problem’s condition number.Source: §5 · p. 14
  • Under multiplicative observation noise with σ = 0.1 in positions and velocities, kernel estimates are minimally affected, with changes mainly where occupancy is small.Similar noise-robustness results are reported for the other systems considered.Source: §5 · p. 14, Figure 8 · p. 15

6 Discussion and Conclusion

The discussion presents a non-parametric estimator tested across varied agent systems and observation regimes, with theoretical guarantees for first-order systems. It identifies model order and interaction type in two model-selection examples, while pointing to stochastic systems and interactions beyond pairwise distance dependence as future generalizations.

6 Discussion and Conclusion

  • The estimator covers first- and second-order systems, single- and multiple-type agents, simple environments, and several trajectory-sampling regimes.The regimes include many short trajectories, one long trajectory, and intermediate timescales.Source: §6 · p. 15
  • For first-order systems, the non-parametric approach has optimal convergence rates independent of state-space dimension and does not require a hypothesis dictionary.The paper connects its statistical guarantees to trust in data-driven models and their use in formulating and testing model conjectures.Source: §6 · p. 15
  • Two model-selection examples show reliable identification of system order and energy- versus alignment-type interactions.Generalizations to stochastic dynamics and interactions beyond pairwise distance-based kernels are identified as future directions.Source: §6 · p. 15

7 Learning Theory

The learning theory builds an error functional and a pairwise-distance measure to estimate interaction kernels from trajectories, then studies when the estimator is learnable and how accurately it predicts trajectories. Coercivity supports convergence, while approximation-space choice shapes convergence rates.

7 Learning Theory

  • The interaction kernel depends on pairwise distances, but its values are unobserved and the observed distances are dependent and potentially redundant.The admissible finite-range assumption represents interactions supported within a maximum distance.Source: §7 · p. 16

7.2 Measures on the pairwise distance space

  • The expected empirical measure of pairwise distances is a natural accuracy measure that accounts for initial-condition randomness, system evolution, and distance abundance.The resulting distance measures are probability measures and are absolutely continuous when the initial-condition distribution is absolutely continuous.Source: §7 · p. 16, §7.2 · p. 17

7.1 The Error functional and estimators

  • The estimator minimizes a nonnegative quadratic error functional over a hypothesis space; truncating the minimizer at the admissible upper bound cannot increase error.Weights can be chosen to target different L2 performance measures.Source: §7.1 · pp. 16–17

7.3 Learnability: the coercivity condition

  • Coercivity makes the true kernel the unique minimizer of the limiting error functional and controls estimator error, yielding convergence under the stated conditions.The convergence theorem considers expanding compact convex hypothesis spaces and increasing sample size.Source: §7.3 · p. 18

7.4 Optimal rate of convergence of the estimator

  • Larger hypothesis spaces reduce approximation bias, while smaller covering numbers limit variance; the propositions connect this trade-off and approximation quality to convergence rates.The rate theorem assumes coercivity and bounds the hypothesis space; the supplied passages do not state its full rate expression.Source: §7.4 · p. 19

7.5 Trajectory-based Performance Measures

  • With a Lipschitz estimated interaction law, trajectory prediction error is bounded trajectory-wise and in mean square by the kernel estimation error.The mean-square bound is with respect to the initial-condition distribution.Source: §7.5 · pp. 20–21

8 Algorithm

The algorithm estimates interaction kernels by assembling and solving least-squares normal equations from trajectory observations. It extends from homogeneous first-order systems to heterogeneous and second-order systems, with coercivity supporting matrix conditioning.

8 Algorithm

  • The algorithm is presented for homogeneous first-order systems, then heterogeneous first-order systems, and finally heterogeneous second-order systems.The estimator is built from trajectory observations and empirical error minimization.Source: §8 · p. 21, §8.1 · p. 21

8.1 First Order Homogeneous Agent Systems

  • For homogeneous first-order systems, the estimator minimizes empirical error using a finite-dimensional basis and solves the resulting least-squares normal equations.When only positions are observed, backward differences approximate velocities, with an O(T/L) bias under the stated sampling condition.Source: §8.1 · pp. 21–22

8.2 Well-conditioning from coercivity

  • Coercivity bounds the smallest singular value of the normal matrix for large sample sizes, when the basis is well-conditioned, supporting a well-conditioned positive-definite least-squares problem.The coercivity constant also controls the condition number of the regularized problem.Source: §8.2 · p. 22

8.3 First Order Heterogeneous Agent Systems

  • For first-order heterogeneous systems, the algorithm fits separate interaction kernels for agent-type pairs using pair-indexed basis functions.The learning-matrix columns are partitioned by ordered type pair.Source: §8.3 · p. 23

8.4 Second Order Heterogeneous Agent Systems

  • For second-order heterogeneous systems, inference separates interactions on the agents’ velocities from interactions on their ξ variables, with the kernel problems formulated as least squares.The energy- and alignment-based interaction kernels use corresponding learning matrices.Source: §8.4 · pp. 23–24

8.5 The Final Algorithm

  • The final algorithm selects interaction radii and basis functions, assembles normal equations in parallel, and solves for kernel coefficients for first- or second-order systems.For second-order systems, the procedure can also construct and solve for ξ-interaction coefficients.Source: §8.5 · p. 25

8.6 Computational Complexity

  • Computational effort is dominated by assembling normal equations from trajectories; solving the final linear system takes comparatively little time.Trajectory-wise quantities can be constructed one trajectory at a time and in parallel.Source: §8.6 · p. 25

9 Examples

This section presents examples evaluating how well the learning approach recovers interaction laws and trajectories across opinion dynamics, Lennard-Jones particles, predator-swarm, and phototaxis systems. The examples also examine error trends, noisy observations, trajectory coverage, and model selection using learned interactions or predicted-trajectory errors.

9 Examples

  • Experiments use relatively few observations, compare kernel and trajectory errors across training and prediction conditions, and test additive and multiplicative observation noise.For noisy observations, positions and velocities are both perturbed by independent Unif.([-σ, σ]) samples; velocities are observed directly because finite differences can amplify position noise.Source: §9 · pp. 26–27
  • Estimator error decreases as L and M increase; for opinion dynamics, M = 1 appears insufficient regardless of L.Across experiments, error decreases with L, a trend not captured by the stated theoretical estimate. In opinion dynamics the error falls roughly with the product ML when M and L are not too small, but a single trajectory lacks sufficient information.Source: §9 · p. 27, Figure 11 · p. 29

9.1 Opinion Dynamics

  • Opinion dynamics yields a faithful kernel approximation near its discontinuity and compact support, with learned trajectories predicting clusters even for 4N agents.The estimate also performs well near 0 despite the equations providing no information about φ(0); with additive noise of σ = 0.1 in observed positions and velocities, learned kernels are minimally affected, mostly where ρL_T is small and near 0.Source: Figure 9 · p. 27, §9.1 · p. 28, Figure 10 · p. 28

9.2 Interacting Particles in Lennard-Jones Potential

  • Lennard-Jones learning is accurate where pairwise-distance data are abundant, and its coercivity constants are close to the theoretical lower bound across tested conditions.Observations must avoid both the singularity at zero distance and the rapidly reached steady state; the restriction of the kernel to the support of ρL_T is smooth, and the numerical learning rate is almost optimal. The coercivity validation spans N = 5 to 30, three initial distributions, and different observation intervals.Source: §9.2 · pp. 30–32
  • The Lennard-Jones estimator’s relative error scales around M^-0.36, close to the theoretical M^-0.4 rate.The authors attribute the small difference to the interaction kernel’s singularity at 0, which makes it inadmissible under their learning theory.Source: §9.2 · p. 31

9.3 Predator-Swarm system

  • Predator-swarm learning recovers all four interactions where pairwise-distance data are abundant, but not near zero where observations are scarce.The predator-to-prey and prey-to-predator kernels are learned over the same pairwise-distance data and are not simply negatives of each other; the predator-to-predator kernel is learned as zero despite no predator-pair observations.Source: §9.3 · p. 33
  • Predator-swarm predictions capture predator movement and most prey movement from new initial conditions, and learned kernels perform similarly with a B-splines basis.The reported B-spline relative L2(ρT) errors are 6.6·10^-2 for prey-on-prey, 6.1·10^-3 for predator-on-prey, 3.6·10^-2 for prey-on-predator, and 0 for predator-on-predator interactions.Source: §9.3 · p. 34, Figure 16 · p. 34
  • Predator-prey first- and second-order systems use similar interaction kernels but produce substantially different pairwise-distance distributions and trajectories.For the second-order case, the paper reports estimator errors and visually accurate predicted trajectories, including tests with new agents.Source: §9.3 · p. 35, Figure 18 · p. 36, Table 14 · p. 36
  • For Predator-Swarm, estimator error decreases with both L and M, roughly with their product, while accurate kernel inference appears to require M ≫ 1 regardless of L.Small-M trajectories do not explore enough configurations for estimation; the reported zero-error case reflects that both the true kernel and its estimator are identically zero when there is only one predator.Source: §9.3 · p. 37, Figure 20 · p. 37

9.4 Phototaxis Dynamics

  • Phototaxis kernels are accurately recovered where pairwise-distance data are abundant, including agent-environment interactions, but estimates worsen near the sparsely sampled upper interaction-range endpoint.With multiplicative observation noise, the estimated kernel for position dynamics is minimally affected, whereas larger-scale additive noise severely affects learning the excitation interaction.Source: §9.4 · pp. 38, 40, Figure 23 · p. 40

9.5 Model Selection

  • Learned interaction kernels distinguish energy-driven from alignment-driven systems, while trajectory errors identify the correct order in both heterogeneous-system cases.For energy-versus-alignment selection, the inactive interaction estimate is small or almost zero; for order selection, the smaller trajectory-error column corresponds to the true system order.Source: §9.5 · pp. 41, 43, Table 22 · p. 43, Table 23 · p. 43
Loading 1812.06003v4…