Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
Submit Manuscript
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2019 Volume 34
Article Contents
Next Previous
ORIGINAL RESEARCH   Open Access    

Predictive models and abstract argumentation: the case of high-complexity semantics

  • 1.

    School of Computing & Engineering

  • 2.

    School of Computer Science & Informatics

  • 3.

    Dipartimento di Ingegneria dell’Infomazione

More Information
  • Abstract: In this paper, we describe how predictive models can be positively exploited in abstract argumentation. In particular, we present two main sets of results. On one side, we show that predictive models are effective for performing algorithm selection in order to determine which approach is better to enumerate the preferred extensions of a given argumentation framework. On the other side, we show that predictive models predict significant aspects of the solution to the preferred extensions enumeration problem. By exploiting an extensive set of argumentation framework features—that is, values that summarize a potentially important property of a framework—the proposed approach is able to provide an accurate prediction about which algorithm would be faster on a given problem instance, as well as of the structure of the solution, where the complete knowledge of such structure would require a computationally hard problem to be solved. Improving the ability of existing argumentation-based systems to support human sense-making and decision processes is just one of the possible exploitations of such knowledge obtained in an inexpensive way.
  • 加载中
  • Audemard G. & Simon L. 2014. Lazy clause exchange policy for parallel sat solvers. In Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT), 197–205. Springer.

    Google Scholar

    Barabasi A. & Albert R. 1999. Emergence of scaling in random networks. Science 286(5439), 509–512.

    Google Scholar

    Baroni P., Caminada M. & Giacomin M. 2011. An introduction to argumentation semantics. Knowledge Engineering Review 26(4), 365–410.

    Google Scholar

    Baroni P., Cerutti F., Dunne P. & Giacomin M. 2013. Automata for infinite argumentation structures. Artificial Intelligence 203, 104–150.

    Google Scholar

    Baroni P., Dunne P. E. & Giacomin M. 2010. On extension counting problems in argumentation frameworks. In Proceedings of the 3rd International Conference on Computational Models of Argument (COMMA), 216, 63–74. IOS Press.

    Google Scholar

    Baroni P. & Giacomin M. 2007. On principle-based evaluation of extension-based argumentation semantics. Artificial Intelligence (Special issue on Argumentation in A.I.) 171(10/15), 675–700.

    Google Scholar

    Baroni P., Giacomin M. & Guida G. 2005. SCC-recursiveness: a general schema for argumentation semantics. Artificial Intelligence 168(1–2), 165–210.

    Google Scholar

    Baumann R. & Strass H. 2014. On the maximal and average numbers of stable extensions. In Proceedings of the 2nd International Workshop on Theory and Applications of Formal Argumentation (TAFA), 111–126. Springer.

    Google Scholar

    Besnard P. & Hunter A. 2014. Constructing argument graphs with deductive arguments: a tutorial. Argument & Computation 5(1), 5–30.

    Google Scholar

    Bistarelli S., Rossi F. & Santini F. 2015a. A comparative test on the enumeration of extensions in abstract argumentation. Fundamenta Informaticae 140(3–4), 263–278.

    Google Scholar

    Bistarelli S., Rossi F. & Santini F. 2015b. Testing credulous and sceptical acceptance in smallworld networks. In Proceedings of the 22nd RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA), 39–46.

    Google Scholar

    Brewer E. A. 1994. Portable High-Performance Supercomputing: High-Level Platform-Dependent OptiMization. PhD thesis, MIT.

    Google Scholar

    Cabrio E. & Villata S. 2014. Node: A benchmark of natural language arguments. In Proceedings of the Fifth International Conference on Computational Models of Argument (COMMA), 449–450. IOS Press.

    Google Scholar

    Cerutti F., Dunne P., Giacomin M. & Vallati M. 2013. Computing preferred extensions in abstract argumentation: a SAT-based approach. In Proceedings of the 2nd International Workshop on Theory and Applications of Formal Argumentation (TAFA), 176–193. Springer.

    Google Scholar

    Cerutti F., Giacomin M. & Vallati M. 2014a. Algorithm selection for preferred extensions enumeration. In Proceedings of the 5th International Conference on Computational Models of Argument (COMMA), 221–232. IOS Press.

    Google Scholar

    Cerutti F., Giacomin M. & Vallati M. 2014b. Generating challenging benchmark AFs. In Proceedings of the 5th International Conference on Computational Models of Argument (COMMA), 457–458. IOS Press.

    Google Scholar

    Cerutti F., Giacomin M., Vallati M. & Zanella M. 2014c. A SCC recursive meta-algorithm for computing preferred labellings in abstract argumentation. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR). AAAI Press.

    Google Scholar

    Cerutti F., Vallati M. & Giacomin M. 2017. An efficient Java-based solver for abstract argumentation frameworks: jArgSemSAT. International Journal on Artificial Intelligence Tools 26(2), 1750002.

    Google Scholar

    Cerutti F., Vallati M. & Giacomin M. 2018. On the impact of configuration on abstract argumentation automated reasoning. International Journal of Approximate Reasoning 92, 120–138.

    Google Scholar

    Dung P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming, and n-person games. Artificial Intelligence 77(2), 321–357.

    Google Scholar

    Dunne P. & Wooldridge M. 2009. Complexity of abstract argumentation. In Argumentation in Artificial Intelligence, 85–104. Springer.

    Google Scholar

    Dunne P. E. 2007. Computational properties of argument systems satisfying graph-theoretic constraints. Artificial Intelligence 171(10–15), 701–729.

    Google Scholar

    Dunne P. E., Dvořák W., Linsbichler T. & Woltran S. 2015. Characteristics of multiple viewpoints in abstract argumentation. Artificial Intelligence 228, 153–178.

    Google Scholar

    Dvořák W., Gaggl S., Wallner J. & Woltran S. 2011. Making use of advances in answer-set programming for abstract argumentation systems. In Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management (INAP), 114–133. Springer.

    Google Scholar

    Dvorák W., Järvisalo M., Wallner J. P. & Woltran S. 2015. Cegartix v0. 4: A SAT-based counterexample guided argumentation reasoning tool. In System Descriptions of the First International Competition on Computational Models of Argumentation (ICCMA15), 12.

    Google Scholar

    Dvořák W., Pichler R. & Woltran S 2012. Towards fixed-parameter tractable algorithms for abstract argumentation. Artificial Intelligence 186, 1–37.

    Google Scholar

    Erdös P. & Rényi A. 1959. On random graphs. I. Publicationes Mathematicae Debrecen 6, 290–297.

    Google Scholar

    Fawcett C., Vallati M., Hutter F., Hoffmann J., Hoos H. & Leyton-Brown K. 2014. Improved features for runtime prediction of domain-independent planners. In Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS), 355–359. AAAI Press.

    Google Scholar

    Gebser M., Kaminski R., Kaufmann B., Schaub T., Schneider M. T. & Ziller S. 2011. A portfolio solver for answer set programming: preliminary report. In Proceedings of the 11th International Conference Logic Programming and Nonmonotonic Reasoning (LPNMR), 352–357. Springer.

    Google Scholar

    Gebser M., Kaufmann B., Neumann A. & Schaub T. 2007. clasp: A conict-driven answer set solver. In Proceedings of the 9th International Conference Logic Programming and Nonmonotonic Reasoning (LPNMR), 260–265. Springer.

    Google Scholar

    Gomes C. P., Sabharwal A. & Selman B. 2009. Model counting. In Handbook of Satisfiability, Biere, A., Heule, M., van Maaren, H. & Walsh, T. (eds). 633–654. IOS Press.

    Google Scholar

    Hall M., Frank E., Holmes G., Pfahringer B., Reutemann P. & Witten I. 2009. The WEKA data mining software: an update. SIGKDD Explorations 11(1), 10–18.

    Google Scholar

    Hall M. A. 1998. Correlation-Based Feature Subset Selection for Machine Learning. PhD thesis, University of Waikato, Department of Computer Science, Hamilton, New Zealand.

    Google Scholar

    Holmes G., Hall M. & Prank E. 1999. Generating Rule Sets from Model Trees. Springer.

    Google Scholar

    Hoos H., Lindauer M. T. & Schaub T. 2014. claspfolio 2: Advances in algorithm selection for answer set programming. Theory and Practice of Logic Programming 14(4–5), 569–585.

    Google Scholar

    Hutter F., Xu L., Hoos H. & Leyton-Brown K. 2014. Algorithm runtime prediction: methods & evaluation. Artificial Intelligence 206, 79–111.

    Google Scholar

    Kohavi R. 1995. The power of decision tables. In 8th European Conference on Machine Learning, 174–189. Springer.

    Google Scholar

    Kröll M., Pichler R. & Woltran S 2017. On the complexity of enumerating the extensions of abstract argumentation frameworks. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI, 1145–1152.

    Google Scholar

    Leyton-Brown K., Nudelman E. & Shoham Y. 2009. Empirical hardness models: methodology and a case study on combinatorial auctions. Journal of the ACM 56(4), 1–52.

    Google Scholar

    Luo J. & Magee C. L. 2011. Detecting evolving patterns of self-organizing networks by flow hierarchy measurement. Complexity 16(6), 53–61.

    Google Scholar

    Maratea M., Pulina L. & Ricca F. 2014. A multi-engine approach to answer-set programming. Theory and Practice of Logic Programming 14(6), 841–868.

    Google Scholar

    Marquardt D. W. & Snee D. 1975. Ridge regression in practice. The American Statistician 29(1), 3–20.

    Google Scholar

    Matos P., Planes J., Letombe F. & Marques-Silva J. 2008. A MAX-SAT algorithm portfolio. In Proceedings of the 18th European Conference on Artificial Intelligence (ECAI), 911–912. IOS Press.

    Google Scholar

    Miller G. A. 1956. The magical number seven, plus or minus two: some limits on our capacity for processing information. Psychological Review 63, 81.

    Google Scholar

    Nofal S., Atkinson K. & Dunne P. 2014. Algorithms for decision problems in argument systems under preferred semantics. Artificial Intelligence 207, 23–51.

    Google Scholar

    Nudelman E., Leyton-Brown K., Devkar A., Shoham Y. & Hoos H. 2004. Understanding random SAT: Beyond the clauses-to-variables ratio. In Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming (CP), 438–452. Springer.

    Google Scholar

    Pulina L. & Tacchella A. 2007. A multi-engine solver for quantified Boolean formulas. In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP), 574–589. Springer.

    Google Scholar

    Sideris A. & Dimopoulos Y. 2010. Constraint propagation in propositional planning. In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS), 153–160. AAAI Press.

    Google Scholar

    Smith-Miles K., van Hemert J. & Lim X. 2010. Understanding TSP difficulty by learning from evolved instances. In Proceedings of the 4th International Conference on Learning and Intelligent Optimization (LION), 266–280. Springer.

    Google Scholar

    Tamani N., Mosse P., Croitoru M., Buche P., Guillard V., Guillaume C. & Gontard N. 2015. An argumentation system for eco-efficient packaging material selection. Computers and Electronics in Agriculture 113, 174–192.

    Google Scholar

    Thimm M. & Villata S. 2017. The first international competition on computational models of argumentation: results and analysis. Artificial Intelligence 252, 267–294.

    Google Scholar

    Thimm M., Villata S., Cerutti F., Oren N., Strass H. & Vallati M. 2016. Summary report of the first international competition on computational models of argumentation. AI Magazine 37(1), 102.

    Google Scholar

    Toniolo A., Norman T. J., Etuk A., Cerutti F., Ouyang R. W., Srivastava M., Oren N., Dropps T., Allen J. A. & Sullivan P. 2015. Agent support to reasoning with different types of evidence in intelligence analysis. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 781–789. ACM.

    Google Scholar

    Valiant L. 1979. The complexity of computing the permanent. Theoretical Computer Science 8(2), 189–201.

    Google Scholar

    Vallati M., Cerutti F. & Giacomin M. 2014. Argumentation frameworks features: an initial study. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), 1117–1118. IOS Press.

    Google Scholar

    Watts D. J. & Strogatz S. H. 1998. Collective dynamics of 'small-world’ networks. Nature 393(6684), 440–442.

    Google Scholar

    Wyner A., Bench-Capon T., Dunne P. & Cerutti F. 2015. Senses of argument in instantiated argumentation frameworks. Argument & Computation 6(1), 50–72.

    Google Scholar

    Xu L., Hutter F., Hoos H. & Leyton-Brown K. 2008. SATzilla: portfolio-based algorithm selection for SAT. Journal of Artificial Intelligence Research 32, 565–606.

    Google Scholar

  • Cite this article

    Mauro Vallati, Federico Cerutti, Massimiliano Giacomin. 2019. Predictive models and abstract argumentation: the case of high-complexity semantics. The Knowledge Engineering Review 34(1), doi: 10.1017/S0269888918000036
    Mauro Vallati, Federico Cerutti, Massimiliano Giacomin. 2019. Predictive models and abstract argumentation: the case of high-complexity semantics. The Knowledge Engineering Review 34(1), doi: 10.1017/S0269888918000036
    shu
Download PDF

Article Metrics

Article views(56) PDF downloads(46)

Other Articles By Authors

ORIGINAL RESEARCH   Open Access    

Predictive models and abstract argumentation: the case of high-complexity semantics

  • 1.

    School of Computing & Engineering

  • 2.

    School of Computer Science & Informatics

  • 3.

    Dipartimento di Ingegneria dell’Infomazione

  • Published online: 18 April 2019
The Knowledge Engineering Review  34,  2019, 34(1)  |  Cite this article

Abstract: Abstract: In this paper, we describe how predictive models can be positively exploited in abstract argumentation. In particular, we present two main sets of results. On one side, we show that predictive models are effective for performing algorithm selection in order to determine which approach is better to enumerate the preferred extensions of a given argumentation framework. On the other side, we show that predictive models predict significant aspects of the solution to the preferred extensions enumeration problem. By exploiting an extensive set of argumentation framework features—that is, values that summarize a potentially important property of a framework—the proposed approach is able to provide an accurate prediction about which algorithm would be faster on a given problem instance, as well as of the structure of the solution, where the complete knowledge of such structure would require a computationally hard problem to be solved. Improving the ability of existing argumentation-based systems to support human sense-making and decision processes is just one of the possible exploitations of such knowledge obtained in an inexpensive way.

    HTML

    Acknowledgments

    • The authors would like to acknowledge the use of the University of Huddersfield Queensgate Grid in carrying out this work. The authors also thank the anonymous reviewers for their helpful comments.

    • In this paper, we consider only finite sets of arguments: see Baroni et al. (2013) for a discussion on infinite sets of arguments.

    • In the case of σ=PR, this is equivalent to write ${\cal E}_{{{\rm PR}}} ({\rm \Gamma })\,\notin\,\{ \{ \emptyset \} \} $, because the existence of a preferred extensions is always guaranteed, and thus it cannot be the case that ${\cal E}_{{{\rm PR}}} ({\rm \Gamma })\,{\equals}\,\emptyset $.

    • This class of problems was introduced by Valiant (1979).

    • For the sake of readability, the complete list of features is provided in Appendix A.

    • Aspartix has been executed with gringo version 3.0.3 and claspD version 1.1.4.

    • ArgTools's implementation is available at https://sourceforge.net/projects/argtools/files/?source=navbar

    • http://ipc.informatik.uni-freiburg.de/

    • Inspired by well-known results from psychological investigations (Miller, 1956), experimental results in the following consider $\bar{\chi }\,{\equals}\,7$.

    • An interested reader can find in Wyner et al. (2015) a discussion on the relations between preferred extensions and models of the original logical formulae.

    • Average number of extensions: 1024.2; variance: 1989.8.

    Rights and permissions
    • © Cambridge University Press, 2019 2019Cambridge University Press
References (58)
  • About this article
    Cite this article
    Mauro Vallati, Federico Cerutti, Massimiliano Giacomin. 2019. Predictive models and abstract argumentation: the case of high-complexity semantics. The Knowledge Engineering Review 34(1), doi: 10.1017/S0269888918000036
    Mauro Vallati, Federico Cerutti, Massimiliano Giacomin. 2019. Predictive models and abstract argumentation: the case of high-complexity semantics. The Knowledge Engineering Review 34(1), doi: 10.1017/S0269888918000036
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return