Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Employing a Restricted Set of Qualitative Relations in Recognizing Plain Sketches Read chapter Read first chapter

2017 | OriginalPaper | Chapter

LiMa: Sequential Lifted Marginal Filtering on Multiset State Descriptions

Authors : Max Schröder, Stefan Lüdtke, Sebastian Bader, Frank Krüger, Thomas Kirste

Published in: KI 2017: Advances in Artificial Intelligence

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Maintaining the a-posteriori distribution of categorical states given a sequence of noisy and ambiguous observations, e.g. sensor data, can lead to situations where one observation can correspond to a large number of different states. We call these states symmetrical as they cannot be distinguished given the observation. Considering each of them during the inference is computationally infeasible, even for small scenarios. However, the number of situations (called hypotheses) can be reduced by abstracting from particular ones and representing all symmetrical in a single abstract state. We propose a novel Bayesian Filtering algorithm that performs this abstraction. The algorithm that we call Lifted Marginal Filtering (LiMa) is inspired by Lifted Inference and combines techniques known from Computational State Space Models and Multiset Rewriting Systems to perform efficient sequential inference on a parametric multiset state description. We demonstrate that our approach is working by comparing LiMa with conventional filtering.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Complexity-Aware Generation of Workflows by Process-Oriented Case-Based Reasoning
next chapter A Priori Advantages of Meta-Induction and the No Free Lunch Theorem: A Contradiction?
Footnotes
1
We use the term density to refer to densities over continuous domains as well as probability distributions over finite domains.
 
2
A multiset over some set S is defined as a partial map from S to \(\mathbb {N}\). We use \([\![\, n_1s_1,n_2s_s,n_3s_3 \,]\!]\) to denote the multiset containing \(s_1,s_2\) and \(s_3\) with the corresponding cardinalities. We use \(\mathcal {M}(S)\) to refer to the set of all multisets over S.
 
Literature
1.
Ahmadi, B., Kersting, K., Sanner, S.: Multi-evidence lifted message passing, with application to pagerank and the kalman filter. In: Proceedings-International Joint Conference on Artificial Intelligence, p. 1152 (2011)
2.
Baker, C.L., Saxe, R., Tenenbaum, J.B.: Action understanding as inverse planning. Cognition 113(3), 329–349 (2009)CrossRef
3.
Barbuti, R., Levi, F., Milazzo, P., Scatena, G.: Maximally parallel probabilistic semantics for multiset rewriting. Fundam. Inform. 112(1), 1–17 (2011)MathSciNetMATH
4.
Berry, G., Boudol, G.: The chemical abstract machine. In: POPL, pp. 81–94. ACM, San Francisco(1990)
5.
Bistarelli, S., Cervesato, I., Lenzini, G., Marangoni, R., Martinelli, F.: On representing biological systems through multiset rewriting. In: Moreno-Díaz, R., Pichler, F. (eds.) EUROCAST 2003. LNCS, vol. 2809, pp. 415–426. Springer, Heidelberg (2003). doi:10.​1007/​978-3-540-45210-2_​38 CrossRef
6.
Boutilier, C., Reiter, R., Price, B.: Symbolic dynamic programming for first-order MDPs. In: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, vol. 1, pp. 690–700 (2001)
7.
Choi, J., Amir, E., Xu, T., Valocchi, A.J.: Learning relational kalman filtering. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 2539–2546 (2015)
8.
Choi, J., Hill, D.J., Amir, E.: Lifted inference for relational continuous models. In: Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI 2010, pp. 126–134. AUAI Press (2010)
9.
Fox, V., Hightower, J., Liao, L., Schulz, D., Borriello, G.: Bayesian filtering for location estimation. IEEE Pervasive Comput. 2(3), 24–33 (2003)CrossRef
10.
Geier, T., Biundo, S.: Approximate online inference for dynamic Markov logic networks. In: 23rd IEEE International Conference on Tools with Artificial Intelligence, pp. 764–768. IEEE (2011)
11.
Huang, J., Guestrin, C., Jiang, X., Guibas, L.: Exploiting probabilistic independence for permutations. In: AISTATS, Clearwater, USA, pp. 248–255 (2009)
12.
Kersting, K., Ahmadi, B., Natarajan, S.: Counting belief propagation. In: UAI, Montreal, Canada, pp. 277–284 (2009)
13.
Kersting, K.: Lifted probabilistic inference. In: 20th European Conference on Artificial Intelligence, ECAI 2012. Frontiers in Artificial Intelligence and Applications, vol. 242. IOS Press (2012)
14.
15.
16.
Kondor, R., Howard, A., Jebara, T.: Multi-object tracking with representations of the symmetric group. In: AISTATS, vol. 2, pp. 211–218 (2007)
17.
Krüger, F., Nyolt, M., Yordanova, K., Hein, A., Kirste, T.: Computational state space models for activity and intention recognition. A feasibility study. PLOS ONE 9(11), e109381 (2014)CrossRef
18.
Poole, D.: First-order probabilistic inference. In: IJCAI, pp. 985–991 (2003)
19.
Ramírez, M., Geffner, H.: Goal recognition over POMDPs: inferring the intention of a POMDP agent. In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, pp. 2009–2014, July 2011
20.
21.
22.
Schröder, M., Lüdtke, S., Bader, S., Krüger, F., Kirste, T.: Abstracting from observation-equivalent entities in human behavior modeling. In: AAAI Workshop: Plan, Activity, and Intent Recognition, February 2017
23.
Van Den Broeck, G., Taghipour, N., Meert, W., Davis, J., De Raedt, L.: Lifted probabilistic inference by first-order knowledge compilation. In: IJCAI, pp. 2178–2185 (2011)
24.
Venugopal, D., Gogate, V.: Evidence-based clustering for scalable inference in Markov logic. In: Calders, T., Esposito, F., Hüllermeier, E., Meo, R. (eds.) ECML PKDD 2014. LNCS, vol. 8726, pp. 258–273. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44845-8_​17
25.
Wilson, D.H., Atkeson, C.: Simultaneous tracking and activity recognition (STAR) using many anonymous, binary sensors. In: Gellersen, H.-W., Want, R., Schmidt, A. (eds.) Pervasive 2005. LNCS, vol. 3468, pp. 62–79. Springer, Heidelberg (2005). doi:10.​1007/​11428572_​5 CrossRef
Metadata
Title
LiMa: Sequential Lifted Marginal Filtering on Multiset State Descriptions
Authors
Max Schröder
Stefan Lüdtke
Sebastian Bader
Frank Krüger
Thomas Kirste
Copyright Year
2017
Book
KI 2017: Advances in Artificial Intelligence

Print ISBN: 978-3-319-67189-5

Electronic ISBN: 978-3-319-67190-1

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-67190-1_17

Premium Partner

    Image Credits