Explaining decisions is at the heart of explainable AI. We investigate the computational complexity of providing a formally-correct and minimal explanation of a decision taken by a classifier. In the ...case of threshold (i.e. score-based) classifiers, we show that a complexity dichotomy follows from the complexity dichotomy for languages of cost functions. In particular, submodular classifiers allow tractable explanation of positive decisions, but not negative decisions (assuming P≠NP). This is an example of the possible asymmetry between the complexity of explaining positive and negative decisions of a particular classifier. Nevertheless, there are large families of classifiers for which explaining both positive and negative decisions is tractable, such as monotone or modular (e.g. linear) classifiers. We extend the characterisation of tractable cases to constrained classifiers (when there are constraints on the possible input vectors) and to the search for contrastive rather than abductive explanations. Indeed, we show that tractable classes coincide for abductive and contrastive explanations in the constrained or unconstrained settings. We show the intractability of returning a set of k diverse explanations even for linear classifiers and k=2. Finding a minimum-cardinality explanation is tractable for the family of modular classifiers, i.e. when the score function is the sum of unary functions, but becomes intractable when any non-modular function is also allowed.
•Research highlight 1: a characterisation of tractable languages when finding a minimal explanation for a decision taken by a classifier.•Research highlight 2: this characterisation shows the importance of properties such as monotonicity or submodularity.•Research highlight 3: this study of tractable languages highlights the asymmetry between explaining positive and negative decisions.•Research highlight 4: a study of tractable languages for the problem of finding a minimum-cardinality explanation.•Research highlight 5: a proof that there are no non-trivial tractable classes for the problem of finding a set of diverse explanations.
We study multiagent epistemic planning with a simple epistemic logic whose language is a restriction of that of standard epistemic logic. Its formulas are boolean combinations of observability atoms: ...sequences of ‘knowing whether’ operators followed by propositional variables. This compares favourably with other restricted languages where formulas are boolean combinations of epistemic literals: sequences of ‘knowing that’ epistemic operators and negations followed by propositional variables; or in other terms: epistemic formulas without conjunctions or disjunctions. The reason is that our language enables a richer theory of mind: we can express statements such as “I don't know whether p, but I know that you know whether p” which are important in communication and more generally in interaction and which cannot be expressed with epistemic literals. Going beyond previous work, we also introduce a ‘common knowledge whether’ operator. We show that satisfiability is nevertheless NP-complete. We then define simple epistemic planning tasks as generalisations of classical planning tasks: action descriptions have sets of observability atoms as add- and delete-lists, initial states are sets of observability atoms, and goals are boolean combinations of observability atoms. We show that simple epistemic planning tasks can be polynomially translated into classical planning tasks. It follows that checking solvability of simple epistemic planning tasks is PSpace-complete. We present some application examples such as the gossip problem and some experimental results and clarify the relationship with Dynamic Epistemic Logic-based planning.
Even though the Constraint Satisfaction Problem (CSP) is NP-complete, many tractable classes of CSP instances have been identified. After discussing different forms and uses of tractability, we ...describe some landmark tractable classes and survey recent theoretical results. Although we concentrate on the classical CSP, we also cover its important extensions to infinite domains and optimisation, as well as #CSP and QCSP.
Sedentarism is a common problem that can affect human health and wellbeing. Predicting sedentary behaviour is an emerging area that can benefit from data collected from sensors available in ...ubiquitous devices, such as wearables and smartphones. In this paper, we present an approach aiming at predicting the sedentary behaviour of a user from data collected from sensors installed in wearable/mobile devices. We compare personal and impersonal models using a real-life dataset consisting of sensing data of 48 users during 10 weeks. We found that impersonal models using Deep Neural Networks were able to accurately predict the subject’s future sedentary behaviour.
Explaining the outcome of programs has become one of the main concerns in AI research. In constraint programming, a user may want the system to explain why a given variable assignment is not feasible ...or how it came to the conclusion that the problem does not have any solution. One solution to the latter is to return to the user a sequence of simple reasoning steps that lead to inconsistency. Arc consistency is a well-known form of reasoning that can be understood by a human. We consider explanations as sequences of propagation steps of a constraint on a variable (i.e. the ubiquitous revise function in arc-consistency algorithms) that lead to inconsistency. We characterize several cases for which providing a shortest such explanation is easy: For instance when constraints are binary and variables have maximum degree two. However, these polynomial cases are tight. For instance, providing a shortest explanation is NP-hard when constraints are binary and the maximum degree is three, even if the number of variables is bounded. It remains NP-hard on trees, despite the fact that arc consistency is a decision procedure on trees. The problem is not even FPT-approximable unless the FPT
≠
W2 hypothesis is false.
A binary CSP instance satisfying the broken-triangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the ...BTP allows the merging of domain values in arbitrary instances of binary CSP, thus providing a novel polynomial-time reduction operation. Extensive experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity and we investigate the theoretical relationship with resolution in SAT. A directional version of general-arity BTP-merging then allows us to extend the BTP tractable class previously defined only for binary CSP. We investigate the complexity of several related problems including the recognition problem for the general-arity BTP class when the variable order is unknown, finding an optimal order in which to apply BTP merges and detecting BTP-merges in the presence of global constraints such as AllDifferent.
Summary
For dryland rivers globally, understanding hydro‐ecological function is fundamental to informing trade‐offs between consumptive water use and aquatic ecosystem integrity. The Barwon–Darling ...is an Australian dryland river system recognised for its hydrological variability, which is considered a primary driver of the riverine ecosystem. Emphasis has been placed on extremes of zero flow and flood but examining low flow hydrology and hydraulics – through historical and modern droughts – demonstrates that under natural conditions, the river system also exhibits persistent and predictable flow characteristics. From 1885 to 1950, prior to flow regulation, the Barwon–Darling flowed 92% of the time, and throughout severe droughts (1895–1903 and 1939–1945) the river system was characterised by: near‐perennial flows (85% of the time), with lotic (flowing water) habitats; and near‐annual, in channel, flow pulses. Furthermore, evidence of lotic biota is found consistently in Aboriginal middens dating over the past 15,000 years, thus indicating the long‐term persistence of lotic conditions. We propose these consistent hydrological and hydrodynamic features have shaped the ecology of aquatic biota in the Barwon–Darling River but are now experiencing unprecedented change. Flow storage and diversion have increased the frequency and duration of zero flows in some reaches, but arguably the most substantial impacts, along the entire river, are on: (i) low flows, which are now frequently below lotic thresholds, and (ii) the magnitude of near‐annual flow pulses, which are reduced by over 90%. Consequently, in modern droughts, the river becomes predominantly lentic (still‐water), an impact that is exacerbated by weirpools which create artificial lentic conditions for approximately 1000 km (40%) of river. The ecological impacts of these changes are increasingly apparent, with the loss of lotic biota and a reduction in biodiversity. An ecohydraulic perspective explains present impacts, provides new directions and some immediate solutions for river management, and clarifies choices for stakeholders.
The best-characterized Toll-like receptor 4 (TLR4) ligands are lipopolysaccharide (LPS) and its chemically modified and detoxified variant, monophosphoryl lipid A (MPL). Although both molecules are ...active for human TLR4, they demonstrate a potency preference for mouse TLR4 based on data from transfected cell lines and primary cells of both species. After a high throughput screening process of small molecule libraries, we have discovered a new class of TLR4 agonist with a species preference profile differing from MPL. Products of the 4-component Ugi synthesis reaction were demonstrated to potently trigger human TLR4-transfected HEK cells but not mouse TLR4, although inclusion of the human MD2 with mTLR4 was able to partially recover activity. Co-expression of CD14 was not required for optimal activity of Ugi compounds on transfected cells, as it is for LPS. The species preference profile for the panel of Ugi compounds was found to be strongly active for human and cynomolgus monkey primary cells, with reduced but still substantial activity for most Ugi compounds on guinea pig cells. Mouse, rat, rabbit, ferret, and cotton rat cells displayed little or no activity when exposed to Ugi compounds. However, engineering the human versions of TLR4 and MD2 to be expressed in mTLR4/MD2 deficient mice allowed for robust activity by Ugi compounds both in vitro and in vivo. These findings extend the range of compounds available for development as agonists of TLR4 and identify novel molecules which reverse the TLR4 triggering preference of MPL for mouse TLR4 over human TLR4. Such compounds may be amenable to formulation as more potent human-specific TLR4L-based adjuvants than typical MPL-based adjuvants.
Although the CSP (constraint satisfaction problem) is NP-complete, even in the case when all constraints are binary, certain classes of instances are tractable. We study classes of binary CSP ...instances defined by excluding subproblems. This approach has recently led to the discovery of novel tractable classes. The complete characterisation of all tractable classes defined by forbidding patterns (where a pattern is simply a compact representation of a set of subproblems) is a challenging problem. We demonstrate a dichotomy in the case of forbidden patterns consisting of either one or two constraints. This has allowed us to discover several new tractable classes including, for example, a novel generalisation of 2SAT. We then extend this dichotomy to existential patterns which are only forbidden on specific domain values.
Variable Elimination in Binary CSPs Cooper, Martin C.; El Mouelhi, Achref; Terrioux, Cyril
The Journal of artificial intelligence research,
01/2019, Letnik:
66
Journal Article
Recenzirano
Odprti dostop
We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We study variable-elimination rules based on the ...language of forbidden patterns enriched with counting and quantification over variables and values. We propose new rules and compare them, both theoretically and experimentally. We give optimised algorithms to apply these rules and show that each define a novel tractable class. Using our variable-elimination rules in preprocessing allowed us to solve more benchmark problems than without.
PDF
