TL;DR
This paper introduces "Lifted Marginal Filtering" (LiMa), a novel Bayesian filtering algorithm designed for complex dynamic systems described by Multiset Rewriting Systems (MRSs). By decomposing multiset states into structures and values, LiMa exploits symmetries (exchangeability) to dramatically reduce the computational complexity of tracking multiple interacting entities, leading to significant efficiency gains and improved accuracy in approximate inference.
What Problem Does This Paper Address?
Tracking and understanding dynamic systems with multiple interacting entities is a fundamental challenge in AI. When these systems are modeled using Multiset Rewriting Systems (MRSs), which naturally capture the behavior of multiple objects or agents, the number of possible states can explode combinatorially. This makes traditional Bayesian filtering (BF) computationally infeasible due to the need to explicitly track every single state. The paper addresses this by developing a "lifted" representation that groups similar entities, exploiting their exchangeable properties to represent the system's state more compactly and efficiently.
Methods
The core of the paper's contribution lies in its novel "lifted state representation" and the LiMa algorithm that operates on it.
- Decomposition: The key idea is to decompose a multiset state $x$ into a structure $s$ (which entities exist and their types) and a value sequence $v$ (the specific values of their properties). This decomposition allows for a more efficient representation of the probability distribution $p(x)$ as $p(s, v) = p(s)p(v|s)$.
- Exploiting Exchangeability: The paper assumes that the distribution over value sequences $p(v|s)$ can be factorized into independent components based on "distribution types." Crucially, it assumes exchangeability within these components, meaning the order of values for similar entities doesn't matter. This allows for a much more compact representation than enumerating all possible value combinations.
- Lifted States: A "lifted state" $l = (s, \gamma)$ combines a structure $s$ with a "context" $\gamma$, which represents the distributions of exchangeable value sequences for that structure. This lifted state compactly represents a distribution over many ground states that share the same structure.
- Lifted Marginal Filtering (LiMa): The paper introduces the LiMa algorithm, which performs prediction and update steps directly on these lifted states. This involves:
- Splitting: A crucial operation to handle situations where constraints are indeterminate for some groundings within a lifted state. Splitting decomposes a lifted state into multiple new lifted states, each representing a partition of the original ground states where constraints are consistently satisfied or not. This is done systematically for multinomial and hypergeometric distributions.
- Prediction: Applying MRS transition rules to lifted states, which is equivalent to applying them to all ground states represented by the lifted state.
- Update: Incorporating observations using constraint-based observation models, also applied to lifted states.
- Approximate Inference: LiMa naturally supports approximate inference through pruning, similar to ground marginal filtering, by limiting the number of lifted states maintained.
Datasets
The paper evaluates its approach on three application scenarios:
- Office: A simulated scenario with 1-6 agents performing activities in an office, using floor pressure sensor data.
- Tracking: A real-world scenario with 1-7 persons moving in an environment, using simulated presence sensor data based on real motion trajectories.
- Kitchen: A large-scale, real-world scenario involving activity and context recognition in a kitchen, using data from instrumented participants.
The paper notes that the office and tracking scenarios were aggregated to involve the same number of agents for evaluation.
Key Insights and Ideas
- Symmetry is Key: The core insight is that many dynamic systems exhibit symmetries (exchangeability) in how entities behave or are observed. Exploiting these symmetries is the primary driver of computational efficiency.
- Decomposition for Tractability: Breaking down complex multiset states into structural and value components is essential for applying efficient probabilistic representations.
- Lifted States as Distributions: A lifted state isn't just a single state but a compact representation of a distribution over many ground states, enabling more efficient representation and manipulation.
- Splitting for Indeterminacy: The "splitting" mechanism is a clever way to handle situations where system dynamics or observations are ambiguous for certain groups of entities, allowing the algorithm to maintain tractability without losing information.
- Efficiency Gains are Real: The empirical results demonstrate that this lifted approach can lead to significant reductions in computational complexity and improved accuracy, especially in scenarios with high symmetry.
Key Results
- Representation Efficiency: LiMa achieved a significant reduction in the number of states required for exact filtering, often by orders of magnitude, especially in scenarios with more agents (e.g., office and tracking). For instance, in the office scenario with 4 agents, the ground representation needed ~2842 times more states than the lifted representation.
- Approximate Inference Quality: In approximate filtering (with pruning), LiMa achieved significantly lower RMSE (tracking) and higher accuracy (kitchen) compared to ground filtering, particularly when the number of available states was limited. The lifted approach also showed lower variance in RMSE.
- General Applicability: The framework is designed to be general, applicable to any system that can be formalized as an MRS, though efficiency gains depend on the presence of exploitable symmetries.
Limitations and Future Work
- Symmetry Dependence: The efficiency gains of LiMa are directly tied to the presence of exchangeability in the filtering distribution. In the worst case, where no exchangeability can be exploited, LiMa degenerates to ground marginal filtering.
- Splitting Complexity: While splitting is crucial for handling indeterminacy, it can lead to a combinatorial explosion in the number of lifted states in complex cases.
- Future Work:
- Developing more general methods for identifying and projecting onto sufficiently similar symmetric distributions to handle situations where symmetries are broken.
- Learning observation models that preserve symmetries.
- Learning action weights or even actions themselves.
- Exploring alternative representation formalisms for value distributions, such as Sum-Product Networks or Exchangeable Variable Models.
- Combining LiMa with Data Association methods for efficiency in less symmetrical cases.
Summary updated