Abstract Recent years have witnessed the rise of accurate but obscure classification models that hide the logic of their internal decision processes. Explaining the decision taken by a black-box classifier on a specific input instance is therefore of striking interest. We propose a local rule-based model-agnostic explanation method providing stable and actionable explanations. An explanation consists of a factual logic rule, stating the reasons for the black-box decision, and a set of actionable counterfactual logic rules, proactively suggesting the changes in the instance that lead to a different outcome. Explanations are computed from a decision tree that mimics the behavior of the black-box locally to the instance to explain. The decision tree is obtained through a bagging-like approach that favors stability and fidelity: first, an ensemble of decision trees is learned from neighborhoods of the instance under investigation; then, the ensemble is merged into a single decision tree. Neighbor instances are synthetically generated through a genetic algorithm whose fitness function is driven by the black-box behavior. Experiments show that the proposed method advances the state-of-the-art towards a comprehensive approach that successfully covers stability and actionability of factual and counterfactual explanations.

There is a fast-growing literature in addressing the fairness of AI models (fair-AI), with a continuous stream of new conceptual frameworks, methods, and tools. How much can we trust them? How much do they actually impact society? We take a critical focus on fair-AI and survey issues, simplifications, and mistakes that researchers and practitioners often underestimate, which in turn can undermine the trust on fair-AI and limit its contribution to society. In particular, we discuss the hyper-focus on fairness metrics and on optimizing their average performances. We instantiate this observation by discussing the Yule's effect of fair-AI tools: being fair on average does not imply being fair in contexts that matter. We conclude that the use of fair-AI methods should be complemented with the design, development, and verification practices that are commonly summarized under the umbrella of trustworthy AI.

Artificial Intelligence (AI) has come to prominence as one of the major components of our society, with applications in most aspects of our lives. In this field, complex and highly nonlinear machine learning models such as ensemble models, deep neural networks, and Support Vector Machines have consistently shown remarkable accuracy in solving complex tasks. Although accurate, AI models often are “black boxes” which we are not able to understand. Relying on these models has a multifaceted impact and raises significant concerns about their transparency. Applications in sensitive and critical domains are a strong motivational factor in trying to understand the behavior of black boxes. We propose to address this issue by providing an interpretable layer on top of black box models by aggregating “local” explanations. We present GLocalX, a “local-first” model agnostic explanation method. Starting from local explanations expressed in form of local decision rules, GLocalX iteratively generalizes them into global explanations by hierarchically aggregating them. Our goal is to learn accurate yet simple interpretable models to emulate the given black box, and, if possible, replace it entirely. We validate GLocalX in a set of experiments in standard and constrained settings with limited or no access to either data or local explanations. Experiments show that GLocalX is able to accurately emulate several models with simple and small models, reaching state-of-the-art performance against natively global solutions. Our findings show how it is often possible to achieve a high level of both accuracy and comprehensibility of classification models, even in complex domains with high-dimensional data, without necessarily trading one property for the other. This is a key requirement for a trustworthy AI, necessary for adoption in high-stakes decision making applications.

Black box AI systems for automated decision making, often based on machine learning over (big) data, map a user’s features into a class or a score without exposing the reasons why. This is problematic not only for lack of transparency, but also for possible biases inherited by the algorithms from human prejudices and collection artifacts hidden in the training data, which may lead to unfair or wrong decisions. We focus on the urgent open challenge of how to construct meaningful explanations of opaque AI/ML systems, introducing the local-toglobal framework for black box explanation, articulated along three lines: (i) the language for expressing explanations in terms of logic rules, with statistical and causal interpretation; (ii) the inference of local explanations for revealing the decision rationale for a specific case, by auditing the black box in the vicinity of the target instance; (iii), the bottom-up generalization of many local explanations into simple global ones, with algorithms that optimize for quality and comprehensibility. We argue that the local-first approach opens the door to a wide variety of alternative solutions along different dimensions: a variety of data sources (relational, text, images, etc.), a variety of learning problems (multi-label classification, regression, scoring, ranking), a variety of languages for expressing meaningful explanations, a variety of means to audit a black box.

We present a framework for the analysis of corporate governance problems using network science and graph algorithms on ownership networks. In such networks, nodes model companies/shareholders and edges model shares owned. Inspired by the widespread pyramidal organization of corporate groups of companies, we model ownership networks as layered graphs, and exploit the layered structure to design feasible and efficient solutions to three key problems of corporate governance. The first one is the long-standing problem of computing direct and indirect ownership (integrated ownership problem). The other two problems are introduced here: computing direct and indirect dividends (dividend problem), and computing the group of companies controlled by a parent shareholder (corporate group problem). We conduct an extensive empirical analysis of the Italian ownership network, which, with its 3.9M nodes, is 30× the largest network studied so far.

Ontologies allow us to represent knowledge and data in implicit and explicit ways. Implicit knowledge can be derived by means of several deductive logic-based processes. This paper introduces a new way for extracting implicit knowledge from ontologies by means of a link analysis of the T-box of the ontology integrated with a data mining step on the A-box. The implicit knowledge extracted is in the form of "Influence Rules" i.e. rules structured as: if property p1 of concept c1 has value v1, then property p2 of concept c2 has value v2 with probability π. The technique is completely general and applicable to whatever domain. The Influence Rules can be used to integrate existing knowledge or to support any other data mining process. A case study about an ontology that describes intrusion detection is used to illustrate how the method works.

With the support of the legally-grounded methodology of situation testing, we tackle the problems of discrimination discovery and prevention from a dataset of historical decisions by adopting a variant of k-NN classification. A tuple is labeled as discriminated if we can observe a significant difference of treatment among its neighbors belonging to a protected-by-law group and its neighbors not belonging to it. Discrimination discovery boils down to extracting a classification model from the labeled tuples. Discrimination prevention is tackled by changing the decision value for tuples labeled as discriminated before training a classifier. The approach of this paper overcomes legal weaknesses and technical limitations of existing proposals.

Discrimination discovery in databases consists in finding unfair practices against minorities which are hidden in a dataset of historical decisions. The DCUBE system implements the approach of [5], which is based on classification rule extraction and analysis, by centering the analysis phase around an Oracle database. The proposed demonstration guides the audience through the legal issues about discrimination hidden in data, and through several legally-grounded analyses to unveil discriminatory situations. The SIGMOD attendees will freely pose complex discrimination analysis queries over the database of extracted classification rules, once they are presented with the database relational schema, a few ad-hoc functions and procedures, and several snippets of SQL queries for discrimination discovery.

Abstract With the spreading of XML sources, mining XML data can be an important objective in the near future. This paper presents a project focussed on designing a general‐purpose query language in support of mining XML data. In our framework, raw data, mining models and domain knowledge are represented by way of XML documents and stored inside native XML databases. Data mining (DM) tasks are expressed in an extension of XQuery. Special attention is given to the frequent pattern discovery problem, and a way of exploiting domain‐dependent optimizations and efficient data structures as deeper as possible in the extraction process is presented. We report the results of a first bunch of experiments, showing that a good trade‐off between expressiveness and efficiency in XML DM is not a chimera. Copyright © 2009 John Wiley & Sons, Ltd.

In the context of civil rights law, discrimination refers to unfair or unequal treatment of people based on membership to a category or a minority, without regard to individual merit. Discrimination in credit, mortgage, insurance, labor market, and education has been investigated by researchers in economics and human sciences. With the advent of automatic decision support systems, such as credit scoring systems, the ease of data collection opens several challenges to data analysts for the fight against discrimination. In this article, we introduce the problem of discovering discrimination through data mining in a dataset of historical decision records, taken by humans or by automatic systems. We formalize the processes of direct and indirect discrimination discovery by modelling protected-by-law groups and contexts where discrimination occurs in a classification rule based syntax. Basically, classification rules extracted from the dataset allow for unveiling contexts of unlawful discrimination, where the degree of burden over protected-by-law groups is formalized by an extension of the lift measure of a classification rule. In direct discrimination, the extracted rules can be directly mined in search of discriminatory contexts. In indirect discrimination, the mining process needs some background knowledge as a further input, for example, census data, that combined with the extracted rules might allow for unveiling contexts of discriminatory decisions. A strategy adopted for combining extracted classification rules with background knowledge is called an inference model. In this article, we propose two inference models and provide automatic procedures for their implementation. An empirical assessment of our results is provided on the German credit dataset and on the PKDD Discovery Challenge 1999 financial dataset.

Automatic Decision Support Systems (DSS) are widely adopted for screening purposes in socially sensitive tasks, including access to credit, mortgage, insurance, labor market and other benefits. While less arbitrary decisions can potentially be guaranteed, automatic DSS can still be discriminating in the socially negative sense of resulting in unfair or unequal treatment of people. We present a reference model for finding (prima facie) evidence of discrimination in automatic DSS which is driven by a few key legal concepts. First, frequent classification rules are extracted from the set of decisions taken by the DSS over an input pool dataset. Key legal concepts are then used to drive the analysis of the set of classification rules, with the aim of discovering patterns of discrimination. We present an implementation, called LP2DD, of the overall reference model integrating induction, through data mining classification rule extraction, and deduction, through a computational logic implementation of the analytical tools.

Discrimination in social sense (e.g., against minorities and disadvantaged groups) is the subject of many laws worldwide, and it has been extensively studied in the social and economic sciences. We tackle the problem of determining, given a dataset of historical decision records, a precise measure of the degree of discrimination suffered by a given group (e.g., an etnic minority) in a given context (e.g., a geographic area) with respect to the decision (e.g. credit denial). In our approach, this problem is rephrased in a classification rule based setting, and a collection of quantitative measures of discrimination is introduced, on the basis of existing norms and regulations. The measures are defined as functions of the contingency table of a classification rule, and their statistical significance is assessed, relying on a large body of statistical inference methods for proportions. Based on this basic method, we are then able to address the more general problems of: (1) unveiling all discriminatory decision patterns hidden in the historical data, combining discrimination analysis with association rule mining, (2) unveiling discrimination in classifiers that learn over training data biased by discriminatory decisions, and (3) in the case of rule-based classifiers, sanitizing discriminatory rules by correcting their confidence. Our approach is validated on the German credit dataset and on the CPAR classifier.

The problem of providing small and medium enterprises (SMEs) with good self-assessment tools is becoming more and more urgent every day, not only because of increasing market competition, but also because of new rules for credit granting, as for example the ones referred to as Basel II.One of the critical issues in designing supporting tools is the quality of the knowledge embedded in them. We maintain that a better quality of decisions can be obtained by exploiting not only quantitative information but also qualitative information and expert knowledge. Here we present a system able to classify the quality of innovation plans of SMEs by exploiting both quantitative and qualitative knowledge embedded in ontology. The ontological approach allows representing qualitative knowledge in a very natural way and, as a consequence, we are able to elicit it by means that are natural for SME officers, as for example questionnaires.

In the context of civil rights law, discrimination refers to unfair or unequal treatment of people based on membership to a category or a minority, without regard to individual merit. Rules extracted from databases by data mining techniques, such as classification or association rules, when used for decision tasks such as benefit or credit approval, can be discriminatory in the above sense. In this paper, the notion of discriminatory classification rules is introduced and studied. Providing a guarantee of non-discrimination is shown to be a non trivial task. A naive approach, like taking away all discriminatory attributes, is shown to be not enough when other background knowledge is available. Our approach leads to a precise formulation of the redlining problem along with a formal result relating discriminatory rules with apparently safe ones by means of background knowledge. An empirical assessment of the results on the German credit dataset is also provided.

Clinical databases store large amounts of information about patients and their medical conditions. Data mining techniques can extract relationships and patterns holding in this wealth of data, and thus be helpful in understanding the progression of diseases and the efficacy of the associated therapies. A typical structure of medical data is a sequence of observations of clinical parameters taken at different time moments. In this kind of contexts, the temporal dimension of data is a fundamental variable that should be taken in account in the mining process and returned as part of the extracted knowledge. Therefore, the classical and well established framework of sequential pattern mining is not enough, because it only focuses on the sequentiality of events, without extracting the typical time elapsing between two particular events. Time-annotated sequences (IAS), is a novel mining paradigm that solves this problem. Recently defined in our laboratory together with an efficient algorithm for extracting them, IAS are sequential patterns where each transition between two events is annotated with a typical transition time that is found frequent in the data. In this paper we report a real-world medical case study, in which the IAS mining paradigm is applied to clinical data regarding a set of patients in the follow-up of a liver transplantation. The aim of the data analysis is that of assessing the effectiveness of the extracorporeal photopheresis (ECP) as a therapy to prevent rejection in solid organ transplantation. For each patient, a set of biochemical variables is recorded at different time moments after the transplantation. The IAS patterns extracted show the values of interleukins and other clinical parameters at specific dates, from which it is possible for the physician to assess the effectiveness of the ECP therapy. We believe that this case study does not only show the interestingness of extracting IAS patterns in this particular context but, more ambitiously, it suggests a general methodology for clinical data mining, whenever the time dimension is an important variable of the problem in analysis.

Abstract KDDML‐G is a middleware language and system for knowledge discovery on the grid. The challenge that motivated the development of a grid‐enabled version of the ‘standalone’ KDDML (Knowledge Discovery in Databases Markup Language) environment was on one side to exploit the parallelism offered by the grid environment, and on the other side to overcome the problem of data immovability, a quite frequent restriction on real‐world data collections that has principally a privacy‐preserving purpose. The last question is addressed by moving the code and ‘mining’ the data ‘on the place’, that is by adapting the computation to the availability and localization of the data. Copyright © 2007 John Wiley & Sons, Ltd.

We propose a formalism and a programming environment in which sophisticated spatio-temporal reasoning can be performed, while keeping the capabilities of manipulating and presenting large amounts of geographical data, typical of commercial Geographical Information Systems (GISs). The spatio-temporal knowledge representation language, named MuTACLP+, is based on constraint logic programming and is integrated via a middleware of commands and translation features with a commercial GIS. The paper presents the language, the architecture of the environment, and a few examples of its use in the field of event planning.

We present a way of exploiting domain knowledge in the design and implementation of data mining algorithms, with special attention to frequent patterns discovery, within a deductive framework. In our framework, domain knowledge is represented by way of deductive rules, and data mining algorithms are specified by means of iterative user-defined aggregates and implemented by means of user-defined predicates. This choice allows us to exploit the full expressive power of deductive rules without loosing in performance. Iterative user-defined aggregates have a fixed scheme, in which user-defined predicates are to be added. This feature allows the modularization of data mining algorithms, thus providing a way to integrate the proper domain knowledge exploitation in the right point. As a case study, we present how user-defined aggregates can be exploited to specify and implement a version of the a priori algorithm. Some performance analyzes and comparisons are discussed in order to show the effectiveness of the approach.

An XML based environment for Knowledge Discovery in Databases is presented. The aim is to develop an environment in which several kinds of knowledge extraction operations can be combined, in order to describe and solve complex knowledge extraction problems. Knowledge extraction problems and their results are specified by means of XML documents, and the environment allows the user to follow the extraction process in an interactive way. The expressiveness and the flexibility of the environment is illustrated by presenting an example where clustering and classification are combined. The open architecture of the environment makes it easy to extend it in order to support the entire KDD process.

We present a knowledge representation framework where a collection of logic programs can be combined together by means of meta-level program composition operations. Each object-level program is composed of a collection of extended clauses, equipped with a time interval representing the time period in which they hold. The interaction between program composition operations and time yields a powerful knowledge representation language in which many applications can be naturally developed. The language is given a meta-level semantics which also provides an executable specification. Moreover, we define an abstract semantics by extending the immediate consequence operator from a single logic program to compositions of logic programs and taking into account time intervals. The operational, meta-level semantics is proven sound and complete with respect to the abstract bottom-up semantics. The approach is further extended in order to cope with the problem of reasoning over joined intervals of time. Three applications in the field of business regulations are shown.

The program composition approach can be fruitfully applied to combine general logic programs, that is, logic programs possibly containing negative premises. We show how the introduction of a basic set of (meta-level) composition operations over general programs increases the knowledge representation capabilities of logic programming for non-monotonic reasoning. Examples of modular programming, hierarchical reasoning, constraints and rules with exceptions will be illustrated. The semantics of programs and program compositions is defined in terms of three-valued logic by extending the three-valued semantics for logic programs proposed by Fitting. A computational interpretation of program compositions is formalized by means of an equivalence preserving syntactic transformation of arbitrary program compositions into standard general programs. Key words: Logic programming, program composition, non-monotonic reasoning, three-valued logic

A simple extension of logic programming consists of introducing a set of basic program composition operations, which form an algebra of logic programs with interesting properties for reasoning about programs and program compositions. From a programming perspective, the operations enhance the expressive power of the logic programing paradigm by supporting a wealth of programming techniques, ranging from software engineering to artificial intelligence applications. This paper focuses on the semantics of program composition operations. It is shown that the immediate consequence operator T(P) properly characterises the intended meaning of a program P when considering compositions of programs. More precisely, it is shown that the T(P) semantics is both compositional and fully abstract w.r.t. the set of composition operations of the algebra. This implies that the T(P) semantics induces the coarsest equivalence relation on programs (subsumption-equivalence) and that any other semantics of programs must induce the same equivalence relation to be both compositional and fully abstract w.r.t. the whole set of operations of the algebra. The T(P) semantics is then related to other well known semantics for logic programs which induce coarser equivalence relations. In particular, three equivalence relations, originally studied by Maher (1988), are considered: Weak subsumption-equivalence, logical equivalence and least Herbrand model equivalence. It is shown that the chain of equivalence relations composed by weak subsumption-equivalence, logical equivalence and least Herbrand model equivalence coincides with the chain of fully abstract compositional equivalence relations for proper subsets of the operations of the algebra, obtained by dropping one operation at a time from the set of compositions.

Meta-programming is a powerful technique for extending and modifying the semantics of an existing object language. Along with the expressiveness, however, meta-programming puts forth some subtle semantic problems, among which the most critical is bound to the representation of object programs at the meta-level. We propose a semantic justification for a simple representation technique in the field of a generalised notion of meta-programming in logic. The generalisation consists in specifying the meta-programs with respect to object programs defined by program expressions. The expressions are defined via a rich suite of operations on logic programs. The technique allows one to build straightforward and concise meta-programs via the representation of object level variables by meta-level variables.>

Modularity is a key issue in the design of modern programming languages. When designing modular features for declarative languages in general, and for logic programming languages in particular, the challenge lies in avoiding the superimposition of a complex syntactic and semantic structure over the simple structure of the basic language. The modular framework defined here for logic programming consists of a small number of operations over modules which are (meta-) logically defined and semantically justified in terms of the basic logic programming semantics. The operations enjoy a number of algebraic properties, thus yielding an algebra of modules. Despite its simplicity, the suite of operations is shown capable of capturing the core features of modularization: information hiding, import/export relationships, and construction of module hierarchies. A metalevel implementation and a compilation-oriented implementation of the operations are provided and proved sound with respect to the semantics. The compilation-oriented implementation is based on manipulation of name spaces and provides the basis for an efficient implementation.

RSF is a formalism for specifying and prototyping systems with time constraints. Specifications are given via a set of transition rules. The application of a transition rule is dependent upon certain events. The occurrence times of the events and the data associated with them must satisfy given properties. As a consequence of the application of a rule, some events are generated and others are scheduled to occur in the future, after given intervals of time. Specifications can be queried, and the computation of answers to queries provides a generalized form of rapid prototyping. Executability is obtained by mapping the RSF rules into logic programming. The rationale, a definition of the formalism, the execution techniques which support the general notion of rapid prototyping and a few examples of its use are presented.>

A class of transformations of functional programs based on symbolic execution and simplification of conditionals is presented. The operational symbolic semantics of a family of functional languages is defined exploiting a set-theoretic notion of symbolic constants. An effective transformation able to simplify a functional program via removal of conditionals is discussed. Finally, it is shown that a structural approach, based on abstract data type specifications, provides a suitable representation for symbolic constants.

article Free Access Share on Magma2: a language oriented toward experiments in control Author: Franco Turini Univ. di Pisa, Pisa, Italy Univ. di Pisa, Pisa, ItalyView Profile Authors Info & Claims ACM Transactions on Programming Languages and SystemsVolume 6Issue 4Oct. 1984 pp 468–486https://doi.org/10.1145/1780.1784Published:01 October 1984Publication History 8citation277DownloadsMetricsTotal Citations8Total Downloads277Last 12 Months18Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF