Algorithms for Complex Explanation Queries

Simple item page
dc.contributor.advisorGogate, Vibhav
dc.contributor.advisorHayenga, Heather
dc.contributor.committeeMemberNatarajan, Sriraam
dc.contributor.committeeMemberRuozzi, Nicholas
dc.contributor.committeeMemberIyer, Rishabh
dc.creatorRouhani, Sara
dc.date.accessioned2023-02-21T22:47:33Z
dc.date.available2023-02-21T22:47:33Z
dc.date.created2021-12
dc.date.issued2021-12-01T06:00:00.000Z
dc.date.submittedDecember 2021
dc.date.updated2023-02-21T22:47:34Z
dc.description.abstractRecently, there has been growing interest in developing machine learning systems that are robust to minor perturbations in input and are explainable in that they are able explain why they made a particular decision to a user. In this dissertation, we focus on a widely used graph-based probabilistic representation called probabilistic graphical models (PGMs) and propose a new unified constrained optimization task called constrained most probable explanation (CMPE) problem over them. We show that in addition to the two aforementioned tasks, making models robust and explainable, many real-world tasks over PGMs can be reduced to CMPE. We thoroughly analyze the computational complexity of CMPE and develop specialized, practical algorithms for solving it. Specifically, we show that CMPE is strongly NP-hard in general and thus unlikely to admit an efficient, polynomial time algorithm. However, it is only weakly NP-hard when the PGM exhibits certain structural properties such as small k-separators. To solve CMPE and upper bound its optimal value, we present novel efficient approaches that combine graph-based partitioning techniques with approximation algorithms developed in literature on the multiple choice knapsack problem (MCKP), number partitioning problem and subset sum problem (SSP). We derive approximation and complexity guarantees for our new algorithms and demonstrate via a large scale experimental evaluation on several benchmark graphical models that compared to baselines such as random sampling and local search, our new algorithms are more accurate. We also encode CMPE as a mixed integer linear program (MILP) and show that our approach is superior to open-source MILP solvers such as SCIP.
dc.format.mimetypeapplication/pdf
dc.identifier.uri
dc.identifier.urihttps://hdl.handle.net/10735.1/9606
dc.language.isoen
dc.subjectComputer Science
dc.subjectArtificial Intelligence
dc.titleAlgorithms for Complex Explanation Queries
dc.typeThesis
dc.type.materialtext
thesis.degree.collegeSchool of Engineering and Computer Science
thesis.degree.departmentComputer Science
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.namePHD

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
ROUHANI-PRIMARY-2022-1.pdf
Size:
15.91 MB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
5.84 KB
Format:
Plain Text
Description:
Download

Collections

UTD Theses and Dissertations