Based on the intuitive idea that sets of objects or entities can be categorized in very different ways, and that some ways to categorise objects are better than others, depending on the purpose of the categorization, in this paper, a formal framework is introduced for parametrically generating a space of possible categorizations of a set of objects, based on the features which individual agents or groups thereof regard as relevant (formally encoded in the notion of interrogative agenda ). This formal framework accounts both for two-valued (crisp), and for many-valued (fuzzy) judgments about the relevance of given features, and introduces ways to aggregate individual agendas to group agendas. As an application on this framework, we discuss a machine-learning meta-algorithm for outlier detection and classification which provides local and global explanations of its results. • Parametric framework to generate categorization systems aligned with agent goals and knowledge stance. • Formal model of interrogative agendas with crisp and fuzzy importance judgments for feature relevance. • Operators to aggregate individual agendas into coherent group-level prioritization of categories. • FCA-based foundation for hierarchical, explainable, and uncertainty-aware categorization structures. • Meta-algorithm that learns agendas for classification, outlier detection, and explainable decision-making.

Categorization is one of the basic tasks in machine learning and data analysis. Building on formal concept analysis (FCA), the starting point of the present work is that different ways to categorize a given set of objects exist, which depend on the choice of the sets of features used to classify them, and different such sets of features may yield better or worse categorizations, relative to the task at hand. In their turn, the (a priori) choice of a particular set of features over another might be subjective and express a certain epistemic stance (e.g. interests, relevance, preferences) of an agent or a group of agents, namely, their interrogative agenda. In the present paper, we represent interrogative agendas as sets of features, and explore and compare different ways to categorize objects w.r.t. different sets of features (agendas). We first develop a simple unsupervised FCA-based algorithm for outlier detection which uses categorizations arising from different agendas. We then present a supervised meta-learning algorithm to learn suitable (fuzzy) agendas for categorization as sets of features with different weights or masses. We combine this meta-learning algorithm with the unsupervised outlier detection algorithm to obtain a supervised outlier detection algorithm. We show that these algorithms perform at par with commonly used algorithms for outlier detection on commonly used datasets in outlier detection. These algorithms provide both local and global explanations of their results.

The present paper establishes systematic connections among the first-order correspondents of Sahlqvist modal reduction principles in various relational semantic settings, including crisp and many-valued Kripke frames, and crisp and many-valued polarity-based frames (aka enriched formal contexts). Building on unified correspondence theory, we aim at introducing a theoretical environment which makes it possible to: (a) compare and inter-relate the various frame correspondents (in different relational settings) of any given Sahlqvist modal reduction principle; (b) recognize when first-order sentences in the frame-correspondence languages of different types of relational structures encode the same “modal content”; (c) meaningfully transfer and represent well known relational properties such as reflexivity, transitivity, symmetry, seriality, confluence, density, across different semantic contexts. These results can be understood as a first step in a research program aimed at making correspondence theory not just (methodologically) unified, but also (effectively) parametric.

The best known modal logics are axiomatized by Sahlqvist axioms, i.e., axioms of a syntactic shape which guarantees these formulas to have such excellent properties as canonicity and elementarity. Recently, the definition of Sahlqvist formulas has been generalized and extended from formulas in classical modal logic to inequalities (sequents) in a wide family of logics known as LE-logics. We introduce an algorithm which checks if a given inequality is generalized Sahlqvist in polynomial time.

Abstract We define LE- $$\mathcal {ALC}$$ , a generalization of the description logic $$\mathcal {ALC}$$ based on the propositional logic of general (i.e. not necessarily distributive) lattices, and semantically interpreted on relational structures based on formal contexts from Formal Concept Analysis (FCA). The description logic LE- $$\mathcal {ALC}$$ allows us to formally describe databases with objects, features, and formal concepts, represented according to FCA as Galois-stable sets of objects and features. We describe ABoxes and TBoxes in LE- $$\mathcal {ALC}$$ , provide a tableaux algorithm for checking the consistency of LE- $$\mathcal {ALC}$$ knowledge bases with acyclic TBoxes, and show its termination, soundness and completeness. Interestingly, consistency checking for LE- $$\mathcal {ALC}$$ with acyclic TBoxes is in PTIME, while the complexity of the consistency checking of classical $$\mathcal {ALC}$$ with acyclic TBoxes is PSPACE-complete.

Abstract In a first-order theory $\varTheta $, the decision problem for a class of formulae $\varPhi $ is solvable if there is an algorithmic procedure that can assess whether or not the existential closure $\varphi ^{\exists }$ of $\varphi $ belongs to $\varTheta $, for any $\varphi \in \varPhi $. In 1988, Parlamento and Policriti already showed how to tailor arguments à la Gödel to a very weak axiomatic set theory, referring them to the class of $\varSigma _{1}$-formulae with $(\forall \exists \forall )_{0}$-matrix, i.e. existential closures of formulae that contain just restricted quantifiers of the forms $(\forall x \in y)$ and $(\exists x \in y)$ and are writable in prenex form with at most two alternations of restricted quantifiers (the outermost quantifier being a ‘$\forall $’). While revisiting their work, we show slightly less weak theories under which incompleteness for recursively axiomatizable extensions holds with respect to existential closures of $(\forall \exists )_{0}$-matrices, namely formulae with at most one alternation of restricted quantifiers.