Metric logic program explanations for complex separator functions

Srijan Kumar; Edoardo Serra; Francesca Spezzano; V. S. Subrahmanian

doi:10.1007/978-3-319-45856-4_14

Metric logic program explanations for complex separator functions

Srijan Kumar, Edoardo Serra, Francesca Spezzano^*, V. S. Subrahmanian

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

There are many classifiers that treat entities to be classified as points in a high-dimensional vector space and then compute a separator S between entities in class +1 from those in class −1. However, such classifiers are usually very hard to explain in plain English to domain experts. We propose Metric Logic Programs (MLPs) which are a fragment of constraint logic programs as a new paradigm for explaining S. We present multiple measures of quality of an MLP and define the problem of finding an MLP-Explanation of S and show that it - and various related problems - are NP-hard. We present the MLP Extract algorithm to extract MLP explanations for S. We show that while our algorithms provide more succinct, simpler, and higher fidelity explanations than association rules that are less expressive, our algorithms do require additional run-time.

Original language	English (US)
Title of host publication	Scalable Uncertainty Management - 10th International Conference, SUM 2016, Proceedings
Editors	Steven Schockaert, Pierre Senellart
Publisher	Springer Verlag
Pages	199-213
Number of pages	15
ISBN (Print)	9783319458557
DOIs	https://doi.org/10.1007/978-3-319-45856-4_14
State	Published - 2016
Externally published	Yes
Event	10th International Conference on Scalable Uncertainty Management, SUM 2016 - Nice, France Duration: Sep 21 2016 → Sep 23 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9858 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Conference on Scalable Uncertainty Management, SUM 2016
Country/Territory	France
City	Nice
Period	9/21/16 → 9/23/16

Funding

Parts of this work were supported by ONR grant N000141612739 and ARO grant W911NF1610342.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-45856-4_14

Cite this

Kumar, S., Serra, E., Spezzano, F., & Subrahmanian, V. S. (2016). Metric logic program explanations for complex separator functions. In S. Schockaert, & P. Senellart (Eds.), Scalable Uncertainty Management - 10th International Conference, SUM 2016, Proceedings (pp. 199-213). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9858 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-45856-4_14

Kumar, Srijan ; Serra, Edoardo ; Spezzano, Francesca et al. / Metric logic program explanations for complex separator functions. Scalable Uncertainty Management - 10th International Conference, SUM 2016, Proceedings. editor / Steven Schockaert ; Pierre Senellart. Springer Verlag, 2016. pp. 199-213 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0d94cd175f074226823f2cb5814921d1,

title = "Metric logic program explanations for complex separator functions",

abstract = "There are many classifiers that treat entities to be classified as points in a high-dimensional vector space and then compute a separator S between entities in class +1 from those in class −1. However, such classifiers are usually very hard to explain in plain English to domain experts. We propose Metric Logic Programs (MLPs) which are a fragment of constraint logic programs as a new paradigm for explaining S. We present multiple measures of quality of an MLP and define the problem of finding an MLP-Explanation of S and show that it - and various related problems - are NP-hard. We present the MLP Extract algorithm to extract MLP explanations for S. We show that while our algorithms provide more succinct, simpler, and higher fidelity explanations than association rules that are less expressive, our algorithms do require additional run-time.",

author = "Srijan Kumar and Edoardo Serra and Francesca Spezzano and Subrahmanian, {V. S.}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 10th International Conference on Scalable Uncertainty Management, SUM 2016 ; Conference date: 21-09-2016 Through 23-09-2016",

year = "2016",

doi = "10.1007/978-3-319-45856-4_14",

language = "English (US)",

isbn = "9783319458557",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "199--213",

editor = "Steven Schockaert and Pierre Senellart",

booktitle = "Scalable Uncertainty Management - 10th International Conference, SUM 2016, Proceedings",

}

Kumar, S, Serra, E, Spezzano, F & Subrahmanian, VS 2016, Metric logic program explanations for complex separator functions. in S Schockaert & P Senellart (eds), Scalable Uncertainty Management - 10th International Conference, SUM 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9858 LNAI, Springer Verlag, pp. 199-213, 10th International Conference on Scalable Uncertainty Management, SUM 2016, Nice, France, 9/21/16. https://doi.org/10.1007/978-3-319-45856-4_14

Metric logic program explanations for complex separator functions. / Kumar, Srijan; Serra, Edoardo; Spezzano, Francesca et al.
Scalable Uncertainty Management - 10th International Conference, SUM 2016, Proceedings. ed. / Steven Schockaert; Pierre Senellart. Springer Verlag, 2016. p. 199-213 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9858 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Metric logic program explanations for complex separator functions

AU - Kumar, Srijan

AU - Serra, Edoardo

AU - Spezzano, Francesca

AU - Subrahmanian, V. S.

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - There are many classifiers that treat entities to be classified as points in a high-dimensional vector space and then compute a separator S between entities in class +1 from those in class −1. However, such classifiers are usually very hard to explain in plain English to domain experts. We propose Metric Logic Programs (MLPs) which are a fragment of constraint logic programs as a new paradigm for explaining S. We present multiple measures of quality of an MLP and define the problem of finding an MLP-Explanation of S and show that it - and various related problems - are NP-hard. We present the MLP Extract algorithm to extract MLP explanations for S. We show that while our algorithms provide more succinct, simpler, and higher fidelity explanations than association rules that are less expressive, our algorithms do require additional run-time.

AB - There are many classifiers that treat entities to be classified as points in a high-dimensional vector space and then compute a separator S between entities in class +1 from those in class −1. However, such classifiers are usually very hard to explain in plain English to domain experts. We propose Metric Logic Programs (MLPs) which are a fragment of constraint logic programs as a new paradigm for explaining S. We present multiple measures of quality of an MLP and define the problem of finding an MLP-Explanation of S and show that it - and various related problems - are NP-hard. We present the MLP Extract algorithm to extract MLP explanations for S. We show that while our algorithms provide more succinct, simpler, and higher fidelity explanations than association rules that are less expressive, our algorithms do require additional run-time.

UR - http://www.scopus.com/inward/record.url?scp=84988014652&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988014652&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-45856-4_14

DO - 10.1007/978-3-319-45856-4_14

M3 - Conference contribution

AN - SCOPUS:84988014652

SN - 9783319458557

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 199

EP - 213

BT - Scalable Uncertainty Management - 10th International Conference, SUM 2016, Proceedings

A2 - Schockaert, Steven

A2 - Senellart, Pierre

PB - Springer Verlag

T2 - 10th International Conference on Scalable Uncertainty Management, SUM 2016

Y2 - 21 September 2016 through 23 September 2016

ER -

Kumar S, Serra E, Spezzano F, Subrahmanian VS. Metric logic program explanations for complex separator functions. In Schockaert S, Senellart P, editors, Scalable Uncertainty Management - 10th International Conference, SUM 2016, Proceedings. Springer Verlag. 2016. p. 199-213. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-45856-4_14

Metric logic program explanations for complex separator functions

Abstract

Publication series

Conference

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this