×

Rethinking defeasible reasoning: a scalable approach. (English) Zbl 1472.68191

Summary: Recent technological advances have led to unprecedented amounts of generated data that originate from the Web, sensor networks, and social media. Analytics in terms of defeasible reasoning – for example, for decision making – could provide richer knowledge of the underlying domain. Traditionally, defeasible reasoning has focused on complex knowledge structures over small to medium amounts of data, but recent research efforts have attempted to parallelize the reasoning process over theories with large numbers of facts. Such work has shown that traditional defeasible logics come with overheads that limit scalability. In this work, we design a new logic for defeasible reasoning, thus ensuring scalability by design. We establish several properties of the logic, including its relation to existing defeasible logics. Our experimental results indicate that our approach is indeed scalable and defeasible reasoning can be applied to billions of facts.

MSC:

68T27 Logic in artificial intelligence
68T30 Knowledge representation

Software:

DLV2; WebPIE; DELORES
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Antoniou, G., Batsakis, S., Mutharaju, R., Pan, J. Z., Qi, G., Tachmazidis, I., Urbani, J. and Zhou, Z.2018. A survey of large-scale reasoning on the web of data. The Knowledge Engineering Review 33, e21.
[2] Antoniou, G., Billington, D., Governatori, G. and Maher, M. J.1999. On the modelling and analysis of regulations. In Proceedings of the Australasian Conference on Information Systems, 20-29.
[3] Antoniou, G., Billington, D., Governatori, G. and Maher, M. J.2000. A flexible framework for defeasible logics. In AAAI/IAAI. AAAI Press/The MIT Press, 405-410.
[4] Antoniou, G., Billington, D., Governatori, G. and Maher, M. J.2001. Representation results for defeasible logic. ACM Transactions on Computational Logic 2, 2, 255-287. · Zbl 1171.68740
[5] Armbrust, M., Xin, R. S., Lian, C., Huai, Y., Liu, D., Bradley, J. K., Meng, X., Kaftan, T., Franklin, M. J., Ghodsi, A. and Zaharia, M.2015. Spark sql: Relational data processing in spark. In Proceedings of the 2015 ACM SIGMOD Conference. ACM, 1383-1394.
[6] Billington, D., Antoniou, G., Governatori, G. and Maher, M. J.2010. An inclusion theorem for defeasible logics. ACM Transactions on Computational Logic 12, 1, 6. · Zbl 1351.68261
[7] Cheng, L., Van Dongen, B. and Van Der Aalst, W.2019. Scalable discovery of hybrid process models in a cloud computing environment. IEEE Trans. Services Computing.
[8] Condie, T., Das, A., Interlandi, M., Shkapsky, A., Yang, M. and Zaniolo, C.2018. Scaling-up reasoning and advanced analytics on BigData. TPLP 18, 5-6, 806-845. · Zbl 1452.68064
[9] Cook, S. and Nguyen, P.2010. Logical Foundations of Proof Complexity. Cambridge University Press. · Zbl 1206.03051
[10] Dantsin, E., Eiter, T., Gottlob, G. and Voronkov, A.2001. Complexity and expressive power of logic programming. ACM Computing Surveys 33, 3, 374-425.
[11] Dowling, W. F. and Gallier, J. H.1984. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. The Journal of Logic Programming 1, 3, 267-284. · Zbl 0593.68062
[12] Gelder, A. V., Ross, K. A. and Schlipf, J. S.1991. The well-founded semantics for general logic programs. Journal of ACM 38, 3, 620-650. · Zbl 0799.68045
[13] Goodman, E. L., Jimenez, E., Mizell, D., Al-Saffar, S., Adolf, B. and Haglin, D. J.2011. High-Performance Computing Applied to Semantic Databases. In ESWC (2), 31-45.
[14] Governatori, G. and Maher, M. J.2017. Annotated defeasible logic. TPLP 17, 5-6, 819-836. · Zbl 1422.68219
[15] Governatori, G., Milosevic, Z. and Sadiq, S. W.2006. Compliance checking between business processes and business contracts. In Tenth IEEE International Enterprise Distributed Object Computing Conference (EDOC 2006), 221-232.
[16] Governatori, G., Olivieri, F., Rotolo, A. and Scannapieco, S.2013. Computing strong and weak permissions in defeasible logic. Journal of Philosophical Logic 42, 6, 799-829. · Zbl 1286.03058
[17] Governatori, G. and Pham, D. H.2009. DR-CONTRACT: An architecture for e-contracts in defeasible logic. IJBPIM 4, 3, 187-199.
[18] Governatori, G. and Rotolo, A.2008. BIO logical agents: Norms, beliefs, intentions in defeasible logic. Autonomous Agents and Multi-Agent Systems 17, 1, 36-69.
[19] Grosof, B. N., Labrou, Y. and Chan, H. Y.1999. A declarative approach to business rules in contracts: courteous logic programs in XML. In Proceedings of the First ACM Conference on Electronic Commerce (EC-99), Denver, CO, USA, November 3-5, 1999, 68-77.
[20] Hashmi, M., Governatori, G., Lam, H. and Wynn, M. T.2018. Are we done with business process compliance: state of the art and challenges ahead. Knowledge and Information Systems 57, 1, 79-133.
[21] Heino, N. and Pan, J. Z.2012. RDFS reasoning on massively parallel hardware. In The Semantic Web - ISWC 2012 - 11th International Semantic Web Conference, Boston, MA, USA, November 11-15, 2012, Proceedings, Part I,Cudré-Mauroux, P., Heflin, J., Sirin, E., Tudorache, T., Euzenat, J., Hauswirth, M., Parreira, J. X., Hendler, J., Schreiber, G., Bernstein, A., and Blomqvist, E., Eds. LNCS, vol. 7649. Springer, 133-148.
[22] Islam, M. B. and Governatori, G.2018. RuleRS: A rule-based architecture for decision support systems. Artificial Intelligence and Law 26, 4, 315-344.
[23] Kim, J. and Park, Y.2015. Scalable owl-horst ontology reasoning using SPARK. In 2015 International Conference on Big Data and Smart Computing, BIGCOMP 2015, Jeju, South Korea, February 9-11, 2015, 79-86.
[24] Leone, N., Allocca, C., Alviano, M., Calimeri, F., Civili, C., Costabile, R., Fiorentino, A., Fuscà, D., Germano, S., Laboccetta, G., Cuteri, B., Manna, M., Perri, S., Reale, K., Ricca, F., Veltri, P. and Zangari, J.2019. Enhancing DLV for large-scale reasoning. In Logic Programming and Nonmonotonic Reasoning - 15th International Conference, LPNMR 2019, Philadelphia, PA, USA, June 3-7, 2019, Proceedings,Balduccini, M., Lierler, Y., and Woltran, S., Eds. LNCS, vol. 11481. Springer, 312-325. · Zbl 07115983
[25] Liu, C., Qi, G., Wang, H. and Yu, Y.2011. Large Scale Fuzzy pD* Reasoning Using MapReduce. In 10th International Semantic Web Conference, Bonn, Germany, October 23-27. LNCS, vol. 7031. Springer, 405-420.
[26] Maher, M. J.2001. Propositional defeasible logic has linear complexity. TPLP 1, 6, 691-711. · Zbl 1066.68530
[27] Maher, M. J.2012. Relative expressiveness of defeasible logics. TPLP 12, 4-5, 793-810. · Zbl 1260.68065
[28] Maher, M. J.2013. Relative expressiveness of defeasible logics II. TPLP 13, 4-5, 579-592. · Zbl 1286.68052
[29] Maher, M. J., Antoniou, G. and Billington, D.1998. A study of provability in defeasible logic. In Proc. 11th Australian Joint Conference on Artificial Intelligence. LNCS, vol. 1502. Springer, 215-226. · Zbl 0928.03029
[30] Martinez-Angeles, C. A., De Castro Dutra, I., Costa, V. S. and Buenabad-Chávez, J.2013. A datalog engine for GPUs. In Declarative Programming and Knowledge Management - Declarative Programming Days, KDPD 2013, Unifying INAP, WFLP, and WLP, Kiel, Germany, September 11-13, 2013, Revised Selected Papers, Hanus, M. and Rocha, R., Eds. LNCS, vol. 8439. Springer, 152-168.
[31] Mutharaju, R., Hitzler, P., Mateti, P. and Lécué, F.2015. Distributed and scalable OWL EL reasoning. In The Semantic Web. Latest Advances and New Domains - 12th European Semantic Web Conference, ESWC 2015, Portoroz, Slovenia, May 31 - June 4, 2015. Proceedings, Gandon, F., Sabou, M., Sack, H., D’Amato, C., Cudré-Mauroux, P., and Zimmermann, A., Eds. LNCS, vol. 9088. Springer, 88-103.
[32] Oren, E., Kotoulas, S., Anadiotis, G., Siebes, R., Ten Teije, A. and Van Harmelen, F.2009. Marvin: Distributed reasoning over large-scale Semantic Web data. J. Web Sem. 7, 4, 305-316.
[33] Prakken, H.1997. Logical Tools for Modelling Legal Argument: A Study of Defeasible Reasoning in Law. Kluwer Academic Publishers.
[34] Skylogiannis, T., Antoniou, G., Bassiliades, N., Governatori, G. and Bikakis, A.2007. DR-NEGOTIATE - A system for automated agent negotiation with defeasible logic-based strategies. Data & Knowledge Engineering 63, 2, 362-380.
[35] Tachmazidis, I.2015. Large-scale reasoning with nonmonotonic and imperfect knowledge through mass parallelization. Ph.D. thesis, University of Huddersfield, UK.
[36] Tachmazidis, I. and Antoniou, G.2013. Computing the stratified semantics of logic programs over big data through mass parallelization. In Theory, Practice, and Applications of Rules on the Web - 7th International Symposium, RuleML 2013, Seattle, WA, USA, July 11-13, 2013. Proceedings, Morgenstern, L., Stefaneas, P. S., Lévy, F., Wyner, A. Z., and Paschke, A., Eds. LNCS, vol. 8035. Springer, 188-202.
[37] Tachmazidis, I., Antoniou, G. and Faber, W.2014. Efficient computation of the well-founded semantics over big data. TPLP 14, 4-5, 445-459. · Zbl 1307.68024
[38] Tachmazidis, I., Antoniou, G., Flouris, G. and Kotoulas, S.2012a. Towards parallel nonmonotonic reasoning with billions of facts. In Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10-14, 2012, Brewka, G., Eiter, T., and Mcilraith, S. A., Eds. AAAI Press.
[39] Tachmazidis, I., Antoniou, G., Flouris, G., Kotoulas, S. and Mccluskey, L.2012b. Large-scale parallel stratified defeasible reasoning. In ECAI 2012 - 20th European Conference on Artificial Intelligence. Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track, Montpellier, France, August 27-31, 2012, Raedt, L. D., Bessière, C., Dubois, D., Doherty, P., Frasconi, P., Heintz, F., and Lucas, P. J. F., Eds. Frontiers in Artificial Intelligence and Applications, vol. 242. IOS Press, 738-743. · Zbl 1327.68260
[40] Urbani, J., Kotoulas, S., Maassen, J., Van Harmelen, F. and Bal, H. E.2012. Webpie: A web-scale parallel inference engine using mapreduce. Journal of Web Semantics, 10, 59-75.
[41] Zhou, Z., Qi, G., Liu, C., Hitzler, P. and Mutharaju, R.2013. Scale reasoning with fuzzy-EL+ ontologies based on MapReduce. In Proceedings of the IJCAI-2013 Workshop on Weighted Logics for Artificial Intelligence, WL4AI-2013, Beijing, China, August 2013, 87-93. · Zbl 1327.68292
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.