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:
MetaBayes: Bayesian Meta-Interpretative Learning Using Higher-Order Stochastic Refinement Read chapter Read first chapter

2014 | OriginalPaper | Chapter

A BDD-Based Algorithm for Learning from Interpretation Transition

Authors : Tony Ribeiro, Katsumi Inoue, Chiaki Sakama

Published in: Inductive Logic Programming

Publisher: Springer Berlin Heidelberg

Log in

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

search-config
loading …

Abstract

In recent years, there has been an extensive interest in learning the dynamics of systems. For this purpose, a new learning method called learning from interpretation transition has been proposed recently [1]. However, both the run time and the memory space of this algorithm are exponential, so a better data structure and an efficient algorithm have been awaited. In this paper, we propose a new learning algorithm of this method utilizing an efficient data structure inspired from Ordered Binary Decision Diagrams. We show empirically that using this representation we can perform the same learning task faster with less memory space.

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 Learning Through Hypothesis Refinement Using Answer Set Programming
next chapter Accelerating Imitation Learning in Relational Domains via Transfer by Initialization
Appendix
Available only for authorised users
Literature
1.
2.
Muggleton, S., De Raedt, L., Poole, D., Bratko, I., Flach, P., Inoue, K., Srinivasan, A.: Ilp turns 20. Mach. Learn. 86(1), 3–23 (2012)MathSciNetCrossRefMATH
3.
Inoue, K.: Logic programming for boolean networks. In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, vol. 2, pp. 924–930. AAAI Press (2011)
4.
Inoue, K., Sakama, C.: Oscillating behavior of logic programs. In: Erdem, E., Lee, J., Lierler, Y., Pearce, D. (eds.) Correct Reasoning. LNCS, vol. 7265, pp. 345–362. Springer, Heidelberg (2012) CrossRef
5.
Van Emden, M.H., Kowalski, R.A.: The semantics of predicate logic as a programming language. J. ACM (JACM) 23(4), 733–742 (1976)CrossRefMATH
6.
Apt, K.R., Blair, H.A., Walker, A.: Towards a theory of declarative knowledge. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, pp. 89–149. Morgan Kaufmann, Los Altos (1988)CrossRef
7.
Akers, S.B.: Binary decision diagrams. IEEE Trans. Comput. 100(6), 509–516 (1978)CrossRef
8.
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 100(8), 677–691 (1986)CrossRef
9.
Aloul, F.A., Mneimneh, M.N., Sakallah, K.A.: Zbdd-based backtrack search sat solver. In: Proceedings of the International Workshop on Logic Synthesis, Lake Tahoe, California (2002)
10.
Minato, S., Arimura, H.: Frequent closed item set mining based on zero-suppressed bdds. Inf. Media Technol. 2(1), 309–316 (2007)
11.
De Raedt, L., Kimmig, A., Toivonen, H.: Problog: A probabilistic prolog and its application in link discovery. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence, pp. 2468–2473 (2007)
12.
Simon, L., Del Val, A.: Efficient consequence finding. In: International Joint Conference on Artificial Intelligence, vol. 17, pp. 359–370. Lawrence Erlbaum Associates Ltd. (2001)
13.
Inoue, K., Sato, T., Ishihata, M., Kameya, Y., Nabeshima, H.: Evaluating abductive hypotheses using an em algorithm on bdds. In: Proceedings of the 21st International Jont Conference on Artifical Intelligence, pp. 810–815. Morgan Kaufmann Publishers Inc. (2009)
14.
Bryant, R.E., Meinel, C.: Ordered binary decision diagrams. In: Hassoun, S., Sasao, T. (eds.) Logic Synthesis and Verification, pp. 285–307. Springer, New York (2002)CrossRef
15.
Bryant, R.E.: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv. (CSUR) 24(3), 293–318 (1992)CrossRef
16.
Minato, S.: Zero-suppressed bdds for set manipulation in combinatorial problems. In: 30th Conference on Design Automation, pp. 272–277. IEEE (1993)
17.
Plotkin, G.D.: A note on inductive generalization. Mach. Intell. 5(1), 153–163 (1970)
18.
Dubrova, E., Teslenko, M.: A sat-based algorithm for finding attractors in synchronous boolean networks. IEEE/ACM Trans. Comput. Biol. Bioinform. (TCBB) 8(5), 1393–1399 (2011)CrossRef
19.
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers, San Rafael (2012)
20.
Groote, J.F., Tveretina, O.: Binary decision diagrams for first-order predicate logic. J. Logic Algebraic Program. 57(1), 1–22 (2003)MathSciNetCrossRefMATH
21.
Liaw, H.T., Lin, C.S.: On the obdd-representation of general boolean functions. IEEE Trans. Comput. 41(6), 661–664 (1992)MathSciNetCrossRef
Metadata
Title
A BDD-Based Algorithm for Learning from Interpretation Transition
Authors
Tony Ribeiro
Katsumi Inoue
Chiaki Sakama
Copyright Year
2014
Publisher
Springer Berlin Heidelberg
Book
Inductive Logic Programming

Print ISBN: 978-3-662-44922-6

Electronic ISBN: 978-3-662-44923-3

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-662-44923-3_4

Premium Partner

    Image Credits