Skip to main content
Erschienen in: Journal of Intelligent Information Systems 3/2018

09.10.2018

Extending expressivity and flexibility of abductive logic programming

verfasst von: Stefano Ferilli

Erschienen in: Journal of Intelligent Information Systems | Ausgabe 3/2018

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Real-world problems often require purely deductive reasoning to be supported by other techniques that can cope with noise in the form of incomplete and uncertain data. Abductive inference tackles incompleteness by guessing unknown information, provided that it is compliant with given constraints. Probabilistic reasoning tackles uncertainty by weakening the sharp logical approach. This work aims at bringing both together and at further extending the expressive power of the resulting framework, called Probabilistic Expressive Abductive Logic Programming (PEALP). It adopts a Logic Programming perspective, introducing several kinds of constraints and allowing to set a degree of strength on their validity. Procedures to handle both extensions, compatibly with standard abductive and probabilistic frameworks, are also provided.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Fußnoten
1
By extension, according to foundational literature (Kakas et al. 1992), literals built on abducible predicates are also called abducibles, meaning that they can be abduced. So, an abducible predicate is a kind of claims that may be abduced, while an abducible literal is a specific claim of that kind that may be abduced.
 
2
While generally defining ICs as formulas, with a few exceptions the discussion in Kakas et al. (1992) only considers ICs in the form of ‘plain’ denials or, using Truth Maintenance terminology, nogoods, i.e., negations of conjunctions of literals, possibly due to their straightforward representation as Logic Programming goals (\(\leftarrow l_{1},\dots ,l_{n},\neg l_{n + 1},\dots ,\neg l_{n+m}\)). As such, since goals are clauses, and FOL clauses are universally quantified, ICs are universally quantified in FOL, as well.
 
3
The original framework requires that abducible predicates have no definition in P. This requirement may be relaxed with a simple representational trick.
 
4
Note that the calls to the abductive derivation are meant to be executed non-deterministically; when successful, they return a suitable partial \({\Delta }_{O}\) which is combined to other partial \({\Delta }_{O}\)’s found in other derivation steps to give the overall \({\Delta }\) returned by a successful run of the complete algorithm.
 
5
Actually, this behavior is inefficient: if any literal in the nor constraint (say, \(l_{i}\)) was already known or abduced to be true before starting the consistency check on the constraint, all proofs based on the previous abduction of other literals \(l_{j}\) with \(j < i\) would fail when encountering \(l_{i}\), causing backtracking until the turn of \(l_{i}\) itself comes in the consistency check. This might be optimized by first checking if any literal in the xor constraint is already known or abduced to be true; if so and it is exactly one, then the constraint is automatically satisfied without any further abduction; if there are several such literals, then the constraint immediately fails; in the other cases the described procedure must be started. Anyway, as said, optimization of the proposed approach is not the subject of this paper.
 
6
We prefer calling it a ‘strength’, using a more neutral term than ‘likelihood’, because often these values express an intuitive degree of validity of the constraint, rather than a theoretically founded computation of its likelihood of being true. Indeed, as quite usual in the probabilistic logic programming setting, these values are manually set by the programmers of the logic theory. Of course, it might be possible to devise procedures that try to assess these values from the available data, but it is a line of research on its own and is outside of the scope of this paper, which focuses instead on the exploitation of the given values.
 
7
The assessment of the likelihood \(p(\delta )\) that abducible \(\delta \) is true is outside the scope of this paper. E.g., as a naive approach, one might assume that this is the a priori probability that the predicate on which \(\delta \) is built is true.
 
8
Using (3), the actual probability of an abductive explanation \(\overline {E} \in \mathcal {W}_{G}\) relative to the set \(\mathcal {W}_{G}\) of all possible worlds can be computed using the following normalization:
$$p^{\prime}(\overline{E}) = \frac{p(\overline{E})}{{\sum}_{E \in \mathcal{W}_{G}} p(E)}$$
Future work will deal specifically with the definition of a formal probability distribution for the assessment of the likelihood of possible worlds.
 
Literatur
Zurück zum Zitat Alberti, M., Bellodi, E., Cota, G., Lamma, E., Riguzzi, F., Zese, R. (2016). Probabilistic constraint logic theories. In Hommersom, A, & Abdallah, S (Eds.) Proceedings of the 3rd International Workshop on Probabilistic Logic Programming (PLP-2016), co-located with 26th International Conference on Inductive Logic Programming (ILP 2016), CEUR Workshop Proceedings, (Vol. 1661 pp. 15–28). Alberti, M., Bellodi, E., Cota, G., Lamma, E., Riguzzi, F., Zese, R. (2016). Probabilistic constraint logic theories. In Hommersom, A, & Abdallah, S (Eds.) Proceedings of the 3rd International Workshop on Probabilistic Logic Programming (PLP-2016), co-located with 26th International Conference on Inductive Logic Programming (ILP 2016), CEUR Workshop Proceedings, (Vol. 1661 pp. 15–28).
Zurück zum Zitat Arvanitis, A., Muggleton, S.H., Chen, J., Watanabe, H. (2006). Abduction with stochastic logic programs based on a possible worlds semantics. In Short Paper Proceedings of the 16th International Conference on Inductive Logic Programming (ILP-06), University of Coruña. Arvanitis, A., Muggleton, S.H., Chen, J., Watanabe, H. (2006). Abduction with stochastic logic programs based on a possible worlds semantics. In Short Paper Proceedings of the 16th International Conference on Inductive Logic Programming (ILP-06), University of Coruña.
Zurück zum Zitat Christiansen, H. (2008). Implementing probabilistic abductive logic programming with constraint handling rules. In Schrijvers, T., & Frühwirth, T. (Eds.) Constraint handling rules, lecture notes in computer science, vol 5388, springer (pp. 85–118).CrossRef Christiansen, H. (2008). Implementing probabilistic abductive logic programming with constraint handling rules. In Schrijvers, T., & Frühwirth, T. (Eds.) Constraint handling rules, lecture notes in computer science, vol 5388, springer (pp. 85–118).CrossRef
Zurück zum Zitat Clark, K.L. (1978). Negation as failure. In Gallaire, H., & Minker, J. (Eds.) Logic and Databases, Plenum Press (pp. 293–322).CrossRef Clark, K.L. (1978). Negation as failure. In Gallaire, H., & Minker, J. (Eds.) Logic and Databases, Plenum Press (pp. 293–322).CrossRef
Zurück zum Zitat De Raedt, L., & Kersting, K. (2008). Probabilistic inductive logic programming. In Probabilistic inductive logic programming, springer, lecture notes in artificial intelligence, (Vol. 4911 pp. 1–27). De Raedt, L., & Kersting, K. (2008). Probabilistic inductive logic programming. In Probabilistic inductive logic programming, springer, lecture notes in artificial intelligence, (Vol. 4911 pp. 1–27).
Zurück zum Zitat De Raedt, L., Kimmig, A., Toivonen, H. (2007). Problog: A probabilistic prolog and its application in link discovery. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07) (pp. 2462–2467). De Raedt, L., Kimmig, A., Toivonen, H. (2007). Problog: A probabilistic prolog and its application in link discovery. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07) (pp. 2462–2467).
Zurück zum Zitat Denecker, M., & Schreye, D.D. (1992). Sldnfa: An abductive procedure for normal abductive programs. In Proceedings of ICSLP, MIT Press (pp. 700–868). Denecker, M., & Schreye, D.D. (1992). Sldnfa: An abductive procedure for normal abductive programs. In Proceedings of ICSLP, MIT Press (pp. 700–868).
Zurück zum Zitat Fierens, D., Van den Broeck, G., Bruynooghe, M., De Raedt, L. (2012). Constraints for probabilistic logic programming. In Roy, D., Mansinghka, V., Goodman, N. (Eds.) Proceedings of the NIPS probabilistic programming workshop. Fierens, D., Van den Broeck, G., Bruynooghe, M., De Raedt, L. (2012). Constraints for probabilistic logic programming. In Roy, D., Mansinghka, V., Goodman, N. (Eds.) Proceedings of the NIPS probabilistic programming workshop.
Zurück zum Zitat Fung, T.H., & Kowalski, R.A. (1997). The IFF proof procedure for abductive logic programming. The Journal of Logic Programming, 33, 151–165.MathSciNetCrossRef Fung, T.H., & Kowalski, R.A. (1997). The IFF proof procedure for abductive logic programming. The Journal of Logic Programming, 33, 151–165.MathSciNetCrossRef
Zurück zum Zitat Getoor, L.C. (2002). Learning statistical models from relational data. PhD thesis, Stanford, CA, USA, aAI3038093. Getoor, L.C. (2002). Learning statistical models from relational data. PhD thesis, Stanford, CA, USA, aAI3038093.
Zurück zum Zitat Kakas, A., & Mancarella, P. (1990a). Abductive logic programming. In Proceedings of NACLP workshop on non-monotonic reasoning and logic programming. Kakas, A., & Mancarella, P. (1990a). Abductive logic programming. In Proceedings of NACLP workshop on non-monotonic reasoning and logic programming.
Zurück zum Zitat Kakas, A., & Mancarella, P. (1990b). Database updates through abduction. In Proceedings of the 16th VLDB, Morgan Kaufmann (pp. 650–661). Kakas, A., & Mancarella, P. (1990b). Database updates through abduction. In Proceedings of the 16th VLDB, Morgan Kaufmann (pp. 650–661).
Zurück zum Zitat Kakas, A.C., & Mancarella, P. (1990c). On the relation of truth maintenance and abduction. In Proceedings of the 1st pacific rim international conference on artificial intelligence. Kakas, A.C., & Mancarella, P. (1990c). On the relation of truth maintenance and abduction. In Proceedings of the 1st pacific rim international conference on artificial intelligence.
Zurück zum Zitat Kakas, A.C., Kowalski, R.A., Toni, F. (1992). Abductive logic programming. Journal of Logic and Computation, 2, 719–770.MathSciNetCrossRef Kakas, A.C., Kowalski, R.A., Toni, F. (1992). Abductive logic programming. Journal of Logic and Computation, 2, 719–770.MathSciNetCrossRef
Zurück zum Zitat Kate, R.J., & Mooney, R.J. (2009). Probabilistic abduction using markov logic networks. In Proceedings of the IJCAI-09 Workshop on Plan, Activity and Intent Recognition (PAIR-09), Pasadena, CA. Kate, R.J., & Mooney, R.J. (2009). Probabilistic abduction using markov logic networks. In Proceedings of the IJCAI-09 Workshop on Plan, Activity and Intent Recognition (PAIR-09), Pasadena, CA.
Zurück zum Zitat Lloyd, J. (1987). Foundations of Logic Programming, 2nd edn. Springer. Lloyd, J. (1987). Foundations of Logic Programming, 2nd edn. Springer.
Zurück zum Zitat Muggleton, S. (1996). Stochastic logic programs De Raedt, L. (Ed.), (Vol. 32. Muggleton, S. (1996). Stochastic logic programs De Raedt, L. (Ed.), (Vol. 32.
Zurück zum Zitat Poole, D. (1993). Probabilistic horn abduction and bayesian networks. Artificial Intelligence, 64(1), 81–129.CrossRef Poole, D. (1993). Probabilistic horn abduction and bayesian networks. Artificial Intelligence, 64(1), 81–129.CrossRef
Zurück zum Zitat Raghavan, S.V. (2011). Bayesian abductive logic programs: a probabilistic logic for abductive reasoning. In Walsh, T. (Ed.) Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11) (pp. 2840–2841). Raghavan, S.V. (2011). Bayesian abductive logic programs: a probabilistic logic for abductive reasoning. In Walsh, T. (Ed.) Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11) (pp. 2840–2841).
Zurück zum Zitat Richardson, M., & Domingos, P. (2006). Markov logic networks. Machine Learning, 62, 107–136.CrossRef Richardson, M., & Domingos, P. (2006). Markov logic networks. Machine Learning, 62, 107–136.CrossRef
Zurück zum Zitat Rotella, F., & Ferilli, S. (2013). Probabilistic abductive logic programming using possible worlds. In Proceedings of the 10th Italian Convention on Computational Logic (CILC-2013), Central Europe (CEUR) Workshop Proceedings, (Vol. 1068 pp. 131–145). Rotella, F., & Ferilli, S. (2013). Probabilistic abductive logic programming using possible worlds. In Proceedings of the 10th Italian Convention on Computational Logic (CILC-2013), Central Europe (CEUR) Workshop Proceedings, (Vol. 1068 pp. 131–145).
Zurück zum Zitat Sato, T. (2002). EM Learning for symbolic-statistical models in statistical abduction. In Progress in discovery science ,final report of the japanese discovery science project, Springer (pp. 189–200).CrossRef Sato, T. (2002). EM Learning for symbolic-statistical models in statistical abduction. In Progress in discovery science ,final report of the japanese discovery science project, Springer (pp. 189–200).CrossRef
Zurück zum Zitat Vennekens, J., Verbaeten, S., Bruynooghe, M. (2004). Logic programs with annotated disjunctions. In Demoen, B., & Lifschitz, V. (Eds.) Programming, Logic (pp. 431–445). Berlin: Springer.CrossRef Vennekens, J., Verbaeten, S., Bruynooghe, M. (2004). Logic programs with annotated disjunctions. In Demoen, B., & Lifschitz, V. (Eds.) Programming, Logic (pp. 431–445). Berlin: Springer.CrossRef
Metadaten
Titel
Extending expressivity and flexibility of abductive logic programming
verfasst von
Stefano Ferilli
Publikationsdatum
09.10.2018
Verlag
Springer US
Erschienen in
Journal of Intelligent Information Systems / Ausgabe 3/2018
Print ISSN: 0925-9902
Elektronische ISSN: 1573-7675
DOI
https://doi.org/10.1007/s10844-018-0531-6

Weitere Artikel der Ausgabe 3/2018

Journal of Intelligent Information Systems 3/2018 Zur Ausgabe