More Like this

1. On the (Complete) Reasons Behind Decisions

   https://doi.org/10.1007/s10849-022-09377-8  

   Darwiche, Adnan; Hirth, Auguste (August 2022, Journal of Logic, Language and Information)

   Abstract Recent work has shown that the input-output behavior of some common machine learning classifiers can be captured in symbolic form, allowing one to reason about the behavior of these classifiers using symbolic techniques. This includes explaining decisions, measuring robustness, and proving formal properties of machine learning classifiers by reasoning about the corresponding symbolic classifiers. In this work, we present a theory for unveiling thereasonsbehind the decisions made by Boolean classifiers and study some of its theoretical and practical implications. At the core of our theory is the notion of acomplete reason,which can be viewed as a necessary and sufficient condition for why a decision was made. We show how the complete reason can be used for computing notions such as sufficient reasons (also known as PI-explanations and abductive explanations), how it can be used for determining decision and classifier bias and how it can be used for evaluating counterfactual statements such as “a decision will stick even if ...because ... .” We present a linear-time algorithm for computing the complete reasoning behind a decision, assuming the classifier is represented by a Boolean circuit of appropriate form. We then show how the computed complete reason can be used to answer many queries about a decision in linear or polynomial time. We finally conclude with a case study that illustrates the various notions and techniques we introduced. 

   more » « less
2. Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making

   https://doi.org/10.1145/3564246.3585161  

   Liu, Qinghua; Netrapalli, Praneeth; Szepesvari, Csaba; Jin, Chi (June 2023, ACM, Proceedings of the 55th Annual ACM Symposium on Theory of Computing)

   This paper introduces a simple efficient learning algorithms for general sequential decision making. The algorithm combines Optimism for exploration with Maximum Likelihood Estimation for model estimation, which is thus named OMLE. We prove that OMLE learns the near-optimal policies of an enormously rich class of sequential decision making problems in a polynomial number of samples. This rich class includes not only a majority of known tractable model-based Reinforcement Learning (RL) problems (such as tabular MDPs, factored MDPs, low witness rank problems, tabular weakly-revealing/observable POMDPs and multi-step decodable POMDPs ), but also many new challenging RL problems especially in the partially observable setting that were not previously known to be tractable. Notably, the new problems addressed by this paper include (1) observable POMDPs with continuous observation and function approximation, where we achieve the first sample complexity that is completely independent of the size of observation space; (2) well-conditioned low-rank sequential decision making problems (also known as Predictive State Representations (PSRs)), which include and generalize all known tractable POMDP examples under a more intrinsic representation; (3) general sequential decision making problems under SAIL condition, which unifies our existing understandings of model-based RL in both fully observable and partially observable settings. SAIL condition is identified by this paper, which can be viewed as a natural generalization of Bellman/witness rank to address partial observability. This paper also presents a reward-free variant of OMLE algorithm, which learns approximate dynamic models that enable the computation of near-optimal policies for all reward functions simultaneously. 

   more » « less
3. Learning Relational Causal Models with Cycles through Relational Acyclification

   https://doi.org/10.1609/aaai.v37i10.26434  

   Ahsan, Ragib; Arbour, David; Zheleva, Elena (June 2023, Proceedings of the AAAI Conference on Artificial Intelligence)

   In real-world phenomena which involve mutual influence or causal effects between interconnected units, equilibrium states are typically represented with cycles in graphical models. An expressive class of graphical models, relational causal models, can represent and reason about complex dynamic systems exhibiting such cycles or feedback loops. Existing cyclic causal discovery algorithms for learning causal models from observational data assume that the data instances are independent and identically distributed which makes them unsuitable for relational causal models. At the same time, causal discovery algorithms for relational causal models assume acyclicity. In this work, we examine the necessary and sufficient conditions under which a constraint-based relational causal discovery algorithm is sound and complete for cyclic relational causal models. We introduce relational acyclification, an operation specifically designed for relational models that enables reasoning about the identifiability of cyclic relational causal models. We show that under the assumptions of relational acyclification and sigma-faithfulness, the relational causal discovery algorithm RCD is sound and complete for cyclic relational models. We present experimental results to support our claim. 

   more » « less
4. Provably efficient, succinct, and precise explanations

   Blanc, G.; Lange, J.; Tan, L. (January 2021, Conference on Neural Information Processing Systems (NeurIPS 2021))

   We consider the problem of explaining the predictions of an arbitrary blackbox model f: given query access to f and an instance x, output a small set of x's features that in conjunction essentially determines f(x). We design an efficient algorithm with provable guarantees on the succinctness and precision of the explanations that it returns. Prior algorithms were either efficient but lacked such guarantees, or achieved such guarantees but were inefficient. We obtain our algorithm via a connection to the problem of {\sl implicitly} learning decision trees. The implicit nature of this learning task allows for efficient algorithms even when the complexity of~f necessitates an intractably large surrogate decision tree. We solve the implicit learning problem by bringing together techniques from learning theory, local computation algorithms, and complexity theory. Our approach of “explaining by implicit learning” shares elements of two previously disparate methods for post-hoc explanations, global and local explanations, and we make the case that it enjoys advantages of both. 

   more » « less
5. SPASTC: a Spatial Partitioning Algorithm for Scalable Travel-time Computation

   https://doi.org/10.1080/13658816.2024.2326445  

   Michels, A C; Park, J; Kang, J-Y; Wang, S (May 2024, International Journal of Geographical Information Science)

   Travel-time computation with large transportation networks is often computationally intensive for two main reasons: 1) large computer memory is required to handle large networks; and 2) calculating shortest-distance paths over large networks is computing intensive. Therefore, previous research tends to limit their spatial extent to reduce computational intensity or resolve computational intensity with advanced cyberinfrastructure. In this context, this article describes a new Spatial Partitioning Algorithm for Scalable Travel-time Computation (SPASTC) that is designed based on spatial domain decomposition with computer memory limit explicitly considered. SPASTC preserves spatial relationships required for travel-time computation and respects a user-specified memory limit, which allows efficient and large-scale travel-time computation within the given memory limit. We demonstrate SPASTC by computing spatial accessibility to hospital beds across the conterminous United States. Our case study shows that SPASTC achieves significant efficiency and scalability making the travel-time computation tens of times faster. 

   more » « less