Fabrizio Angiulli

AIJ Journal 2022 Journal Article

Graph-based construction of minimal models

• Fabrizio Angiulli
• Rachel Ben-Eliyahu-Zohary
• Fabio Fassetti
• Luigi Palopoli

Reasoning with minimal models is at the heart of many knowledge representation systems. Yet, it turns out that this task is formidable even when very simple theories are considered. It is, therefore, crucial to devise methods that attain good performances in most cases. To this end, a path to follow is to find ways to break the task at hand into several sub-tasks that can be solved separately and in parallel. And, in fact, we show that minimal models of positive propositional theories can be decomposed based on the structure of the dependency graph of the theories: this observation turns out to be useful for many applications involving computation with minimal models. In particular, we introduce a new algorithm for minimal model finding based on model decomposition. The algorithm temporal worst-case complexity is exponential in the size s of the largest connected component of the dependency graph, but the actual cost depends on the size of the largest component actually encountered at run time that can be far smaller than s, and on the class of theories to which components belong. For example, if all components reduce to either an Head Cycle Free or an Head Elementary-set Free theory, the algorithm is polynomial in the size of the theory.

IS Journal 2021 Journal Article

Guest Editorial: Non-IID Outlier Detection in Complex Contexts

• Guansong Pang
• Fabrizio Angiulli
• Mihai Cucuringu
• Huan Liu

Outlier detection, also known as anomaly detection, aims at identifying data instances that are rare or significantly different from the majority of instances. Due to its significance in many critical domains like cybersecurity, fintech, healthcare, public security, and AI safety, outlier detection has been one of the most active research areas in various communities, such as machine learning, data mining, computer vision, and statistics. Traditional outlier-detection techniques generally assume that data are independent and identically distributed (IID), which are significantly challenged in complex contexts where data are actually non-IID. These contexts are ubiquitous in not only graph data, sequence data, spatial data, temporal data, and streaming data, but also traditional multidimensional, textual, and image data. 4–6 This demands for advanced outlierdetection approaches to address those explicit or implicit non-IID data characteristics.

JMLR Journal 2018 Journal Article

On the Behavior of Intrinsically High-Dimensional Spaces: Distances, Direct and Reverse Nearest Neighbors, and Hubness

• Fabrizio Angiulli

Over the years, different characterizations of the curse of dimensionality have been provided, usually stating the conditions under which, in the limit of the infinite dimensionality, distances become indistinguishable. However, these characterizations almost never address the form of associated distributions in the finite, although high- dimensional, case. This work aims to contribute in this respect by investigating the distribution of distances, and of direct and reverse nearest neighbors, in intrinsically high-dimensional spaces. Indeed, we derive a closed form for the distribution of distances from a given point, for the expected distance from a given point to its $k$th nearest neighbor, and for the expected size of the approximate set of neighbors of a given point in finite high-dimensional spaces. Additionally, the hubness problem is considered, which is related to the form of the function $N_k$ representing the number of points that have a given point as one of their $k$ nearest neighbors, which is also called the number of $k$-occurrences. Despite the extensive use of this function, the precise characterization of its form is a longstanding problem. We derive a closed form for the number of $k$-occurrences associated with a given point in finite high- dimensional spaces, together with the associated limiting probability distribution. By investigating the relationships with the hubness phenomenon emerging in network science, we find that the distribution of node (in-)degrees of some real-life, large-scale networks has connections with the distribution of $k$-occurrences described herein. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

TCS Journal 2015 Journal Article

Restricted default theories: Expressive power and outlier detection tasks

• Fabrizio Angiulli
• Rachel Ben-Eliyahu-Zohary
• Luigi Palopoli

We study the tractability frontier of outlier detection problems, by analyzing it with respect to (i) the considered outlier detection problem, (ii) the reference default logic fragment, and (iii) the adopted notion of outlier. As for point (i), we shall consider three problems of increasing complexity, called Outlier-Witness Recognition, Outlier Recognition and Outlier Existence, respectively. As for point (ii), as we look for conditions under which outlier detection can be done efficiently, attention will be limited to subsets of Disjunction-free propositional default theories. As for point (iii), we shall refer to both the notion of outlier introduced in [3] and a new and more restrictive one, called strong outlier. We also present a polynomial time algorithm for enumerating all strong outliers of bounded size in a quasi-acyclic normal unary default theory. Some of our tractability results rely on the Incremental Lemma that provides conditions for a default logic fragment to have a monotonic behavior. Finally, in order to show that the simple fragments of DL we deal with are still rich enough to solve interesting problems and, therefore, that the tractability results that we prove are interesting not merely on the theoretical side, insights into the expressive capabilities of these fragments are provided, by showing that normal unary theories express all NL queries, hereby indirectly answering a question raised by Kautz and Selman [16].

AIJ Journal 2014 Journal Article

On the tractability of minimal model computation for some CNF theories

• Fabrizio Angiulli
• Rachel Ben-Eliyahu-Zohary
• Fabio Fassetti
• Luigi Palopoli

Designing algorithms capable of efficiently constructing minimal models of Conjunctive Normal Form theories (CNFs) is an important task in AI. This paper provides new results along this research line and presents new algorithms for performing minimal model finding and checking over positive propositional CNFs and model minimization over propositional CNFs. A CNF is positive if each of its clauses has at least a positive literal. An algorithmic schema, called the Generalized Elimination Algorithm (GEA) is presented, that computes a minimal model of any positive CNF. The schema generalizes the Elimination Algorithm (EA) [5], which computes a minimal model of positive head-cycle-free (HCF) CNF theories. While the EA always runs in polynomial time in the size of the input HCF CNF, the complexity of the GEA depends on the complexity of the specific eliminating operator invoked therein, which may in general turn out to be exponential. Therefore, a specific eliminating operator is defined by which the GEA computes, in polynomial time, a minimal model for a class of CNF that strictly includes head-elementary-set-free (HEF) CNF theories [14], which form, in their turn, a strict superset of HCF theories. Furthermore, in order to deal with the high complexity associated with recognizing HEF theories, an “incomplete” variant of the GEA (called IGEA) is proposed: the resulting schema, once instantiated with an appropriate elimination operator, always constructs a model of the input CNF, which is guaranteed to be minimal if the input theory is HEF. In the light of the above results, the main contribution of this work is the enlargement of the tractability frontier for the minimal model finding and checking and the model minimization problems.

AIJ Journal 2010 Journal Article

Outlier detection for simple default theories

• Fabrizio Angiulli
• Rachel Ben-Eliyahu-Zohary
• Luigi Palopoli

It was noted recently that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected properties. These observations are not explicitly provided in input (as it happens with abduction) but, rather, they are hidden in the given knowledge base. Unfortunately, in the two related formalisms for specifying defaults — Reiter's default logic and extended disjunctive logic programs — the most general outlier detection problems turn out to lie at the third level of the polynomial hierarchy. In this note, we analyze the complexity of outlier detection for two very simple classes of default theories, namely NU and DNU, for which the entailment problem is solvable in polynomial time. We show that, for these classes, checking for the existence of an outlier is anyway intractable. This result contributes to further showing the inherent intractability of outlier detection in default reasoning.

AIJ Journal 2008 Journal Article

Outlier detection using default reasoning

• Fabrizio Angiulli
• Rachel Ben-Eliyahu – Zohary
• Luigi Palopoli

Default logics are usually used to describe the regular behavior and normal properties of domain elements. In this paper we suggest, conversely, that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected semantical characteristics. These sets of literals are selected among those explicitly embodied in the given knowledge base. Hence, essentially we perceive outlier detection as a knowledge discovery technique. This paper defines the notion of outlier in two related formalisms for specifying defaults: Reiter's default logic and extended disjunctive logic programs. For each of the two formalisms, we show that finding outliers is quite complex. Indeed, we prove that several versions of the outlier detection problem lie over the second level of the polynomial hierarchy. We believe that a thorough complexity analysis, as done here, is a useful preliminary step towards developing effective heuristics and exploring tractable subsets of outlier detection problems.

ECAI Conference 2008 Conference Paper

Prototype-based Domain Description

• Fabrizio Angiulli

In this work a novel one-class classifier, namely the Prototype-based Domain Description rule (PDD), is presented. The PDD classifier is equivalent to the NNDD rule under the infinity Minkowski metric for a suitable choice of the prototype set. The concept of PDD consistent subset is introduced and it is shown that computing a minimum size PDD consistent subset is in general not approximable within any constant factor. A logarithmic approximation factor algorithm, called the CPDD algorithm, for computing a minimum size PDD consistent subset is then introduced. The CPDD algorithm has some parameters which allow to tune the trade off between accuracy and size of the model. Experimental results show that the CPDD rule sensibly improves over the CNNDD classifier in terms of size of the subset, while guaranteeing a comparable classification quality.

AAAI Conference 2006 Conference Paper

Clustering by Exceptions

• Fabrizio Angiulli

A density-based clustering algorithm, called OUTCLUST, is presented. The algorithm exploits a notion of local density in order to find homogeneous groups of objects as opposite to objects mostly deviating from the overall population. The proposed algorithm tries to simultaneously consider several features of real data sets, namely finding clusters of different shapes and densities in high dimensional data in presence of noise. It is shown that the method is able to identify very meaningful clusters, and experimental comparison with partitioning, hierarchial, and density-based clustering algorithms, is presented, pointing out that the algorithm achieves good clustering quality.

ICML Conference 2005 Conference Paper

Fast condensed nearest neighbor rule

• Fabrizio Angiulli

JELIA Conference 2004 Conference Paper

Discovering Anomalies in Evidential Knowledge by Logic Programming

• Fabrizio Angiulli
• Gianluigi Greco
• Luigi Palopoli 0001

Abstract The development of effective knowledge discovery techniques has become in the recent few years a very active research area due to the important impact it has in several relevant application areas. One interesting task thereof is that of singling out anomalous individuals from a given population, e. g. , to detect rare events in time-series analysis settings, or to identify objects whose behavior is deviant w. r. t. a codified standard set of “social” rules. Such exceptional individuals are usually referred to as outliers in the literature. Recently, outlier detection has also emerged as a relevant KR&R problem in the context of default logic [2]. For instance, detection algorithms can be used by rational agents to single out those observations that are anomalous to some extent w. r. t. their own, trustable knowledge about the world encoded in the form of a suitable logic theory. In this paper, we formally state the concept of outliers in the context of logic programming. Besides the novel formalization we propose which helps in shedding some lights on the real nature of outliers, a major contribution of the work lies in the exploitation of a minimality criteria in their detection. Moreover, the computational complexity of outlier detection problems arising in this novel setting is thoroughly investigated and accounted for in the paper as well. Finally, we also propose a rewriting algorithm that transforms any outlier problem into an equivalent answer set computation problem, thereby making outlier computation effective and realizable on top of any answer set engine.

TCS Journal 2004 Journal Article

On the complexity of inducing categorical and quantitative association rules

• Fabrizio Angiulli
• Giovambattista Ianni
• Luigi Palopoli

Inducing association rules is one of the central tasks in data mining applications. Quantitative association rules induced from databases describe rich and hidden relationships to be found within data that can prove useful for various application purposes (e. g. , market basket analysis, customer profiling, and others). Although association rules are quite widely used in practice, a thorough analysis of the related computational complexity is missing. This paper intends to provide a contribution in this setting. To this end, we first formally define quantitative association rule mining problems, which include boolean association rules as a special case; we then analyze computational complexity of such problems. The general problem as well as some interesting special cases are considered.

ECAI Conference 2004 Conference Paper

Outlier Detection Using Disjunctive Logic Programming

• Fabrizio Angiulli
• Rachel Ben-Eliyahu-Zohary
• Luigi Palopoli 0001