11institutetext: Bern University of Applied Sciences, Bern, Switzerland
<EMAIL_ADDRESS>
22institutetext: National Research University Higher School of Economics,
Russian Federation
<EMAIL_ADDRESS>
33institutetext: St. Petersburg Department of Steklov Mathematical Institute
of Russian Academy of Sciences, Russia

# On Interpretability and Similarity in Concept-Based Machine Learning

Léonard Kwuida and Dmitry I. Ignatov 112233

###### Abstract

Machine Learning (ML) provides important techniques for classification and
predictions. Most of these are black-box models for users and do not provide
decision-makers with an explanation. For the sake of transparency or more
validity of decisions, the need to develop explainable/interpretable ML-
methods is gaining more and more importance. Certain questions need to be
addressed:

  * •

How does an ML procedure derive the class for a particular entity?

  * •

Why does a particular clustering emerge from a particular unsupervised ML
procedure?

  * •

What can we do if the number of attributes is very large?

  * •

What are the possible reasons for the mistakes for concrete cases and models?

For binary attributes, Formal Concept Analysis (FCA) offers techniques in
terms of intents of formal concepts, and thus provides plausible reasons for
model prediction. However, from the interpretable machine learning viewpoint,
we still need to provide decision-makers with the importance of individual
attributes to the classification of a particular object, which may facilitate
explanations by experts in various domains with high-cost errors like medicine
or finance.

We discuss how notions from cooperative game theory can be used to assess the
contribution of individual attributes in classification and clustering
processes in concept-based machine learning. To address the 3rd question, we
present some ideas on how to reduce the number of attributes using
similarities in large contexts.

###### Keywords:

Interpretable Machine Learning, concept learning, formal concepts, Shapley
values, explainable AI

##  1 Introduction

In the notes of this invited talk, we would like to give the reader a short
introduction to Interpretable Machine Learning (IML) from the perspective of
Formal Concept Analysis (FCA), which can be considered as a mathematical
framework for concept learning, Frequent Itemset Mining (FIM) and Association
Rule Mining (ARM).

Among the variety of concept learning methods, we selected the rule-based JSM-
method named after J.S. Mill in its FCA formulation. Another possible
candidate is Version Spaces. To stress the difference between concept learning
paradigm and formal concept we used concept-based learning term in case of
usage of FCA as a mathematical tool and language.

We assume, that interpretation by means of game-theoretic attribute ranking is
also important in an unsupervised setting as well, and demonstrate its usage
via attribution of stability indices of formal concepts (concept stability is
also known as the robustness of closed itemset in the FIM community).

Being a convenient language for JSM-method (hypotheses learning) and Frequent
Itemset Mining, its direct application to large datasets is possible only
under a reasonable assumption on the number of attributes or data sparseness.
Direct computation of the Shapley value for a given attribute also requires
enumeration of almost all attribute subsets in the intent of a particular
object or concept. One of the possibilities to cope with the data volume is
approximate computations, while another one lies in the reduction of the
number of attributes or their grouping by similarity.

The paper is organised as follows. Section 2 observes several closely related
studies and useful sources on FCA and its applications. Section 3 is devoted
to concept-based learning where formal intents are used as classification
hypotheses and specially tailored Shapley value helps to figure out
contributions of attributes in those hypotheses when a particular (e.g.,
unseen) object is examined. Section 4 shows that the Shapley value approach
can be used for attribution to stability (or robustness) of formal concepts,
thus we are able to rank single attributes of formal intents (closed itemsets)
in an unsupervised setting. Section 5 sheds light on the prospects of usage
attribute-based similarity of concepts and attribute reduction for possibly
large datasets (formal contexts). Section 6 concludes the paper.

##  2 Related Work

Formal Concept Analysis is an applied branch of modern Lattice Theory suitable
for knowledge representation and data analysis in various domains [15]. We
refer the reader to a modern textbook on FCA with a focus on attribute
exploration and knowledge extraction [14], surveys on FCA models and
techniques for knowledge processing and representation [36, 53] as well as on
their applications [52]. Some of the examples in subsequent sections are also
taken from a tutorial on FCA and its applications [18].

Since we deal with interpretable machine learning, we first need to establish
basic machine learning terminology in FCA terms. In the basic case, our data
are Boolean object-attribute matrices or formal contexts, which are not
necessarily labeled w.r.t. a certain target attribute. Objects can be grouped
into clusters (concept extents) by their common attributes, while attributes
compose a cluster (concept intent) if they belong to a certain subset of
objects. The pairs of subsets of objects and attributes form the so-called
formal concepts, i.e. maximal submatrices (w.r.t. of rows and attribute
permutations) of an input context full of ones in its Boolean representation.
Those concepts form hierarchies or concept lattices (Galois lattices), which
provide convenient means of visualisation and navigation and enables usage of
suprema and infima for incomparable concepts.

The connection between well-known concept learning techniques (for example,
Version Spaces, and decision tree induction) from machine learning and FCA was
well established in [12, 31]. Thus Version Spaces studied by T. Mitchell [49]
also provides hierarchical means for hypotheses learning and elimination,
where hypotheses are also represented as conjunctions of attributes describing
the target concept. Moreover, concept lattices can be used for searching for
globally optimal decision trees in the domains where we should not care about
the trade-off between time spent for the training phase and reached accuracy
(e.g., medical diagnostics) but should rather focus on all valid paths in the
global search space [4, 25].

In case we deal with unsupervised learning, concept lattices can be considered
as a variant of hierarchical clustering where one has the advantage to use
multiple inheritance in both bottom-up and top-down directions [7, 66, 64, 6].
Another fruitful property of formal concepts allows one not only to receive a
cluster of objects without any clue why they are similar but to reveal
objects’ similarity in terms of their common attributes. This property allows
considering a formal concept as bicluster [48, 19, 27], i.e. a biset of two
clusters of objects and attributes, respectively.

Another connection between FCA and Frequent Itemset Mining is known for years
[51, 45]. In the latter discipline, transactions of attributes are mined to
find items frequently bought together [1]. The so-called closed itemsets are
used to cope with a huge number of frequent itemsets for large input
transaction bases (or contexts), and their definition coincides with the
definition of concept intents (under the choice of constraint on the concept
extent size or itemset support). Moreover, attribute dependencies in the form
of implications and partial implications [47] are known as association rules,
which appeared later in data mining as well [1]111One of the earlier
precursors of association rules can be also found in [17] under the name of
“almost true implications”.

This is not a coincidence that we discuss data mining, while stressed
interpretability and machine learning in the title. Historically, data mining
was formulated as a step of the Knowledge Discovery in Databases process that
is “the nontrivial process of identifying valid, novel, potentially useful,
and ultimately understandable patterns in data.” [10]. While understandable
patterns are a must for data mining, in machine learning and AI in general,
this property should be instantiated as something extra, which is demanded by
analysts to ease decision making as the adjectives explainable (AI) and
interpretable (ML) suggest [50].

To have a first but quite comprehensive reading on interpretable ML we suggest
a freely available book [50], where the author states that “Interpretable
Machine Learning refers to methods and models that make the behaviour and
predictions of machine learning systems understandable to humans”.

The definition of interpretability may vary from the degree to which a human
can understand the cause of a decision to the degree to which a human can
consistently predict the model’s result.

The taxonomy of IML methods has several aspects. For example, models can be
roughly divided into _intrinsic_ and _post hoc_ ones. The former include
simpler models like short rules or sparse linear models, while among the
latter black-box techniques with post hoc processing after their training can
be found. Some researchers consistently show that in case of the necessity to
have interpretable models, one should not use post hoc techniques for black-
box models but trust naturally interpretable models [57]. Another aspect is
the universality of the method, the two extremes are _model-specific_ (the
method is valid for only one type of models) and or _model-agnostic_ (all
models can be interpreted with the method). There is one more important
aspect, whether the method is suitable for the explanation of the model’s
predictions for a concrete object (_local method_) or it provides an
interpretable picture for the entire model (_global method_). Recent views on
state-of-the-art techniques and practices can be found in [8, 26].

FCA provides interpretable patterns a priori since it deals with such
understandable patterns as sets of attributes to describe both classes (by
means of classification rules or implications) and clusters (e.g., concept
intents). However, FCA theory does not suggest the (numeric) importance of
separate attributes. Here, a popular approach based on Shapley value from
Cooperative Game Theory [59] recently adopted by the IML community may help
[63, 46, 24].

The main idea of Shapley value based approaches in ML for ranking separate
attributes is based on the following consideration: each attribute is
considered as a player in a specific game-related to classification or
regression problem and attributes are able to form (winning) coalitions. The
importance of such a player (attribute) is computed over all possible
coalitions by a combinatorial formula taking into account the number of
winning coalitions where without this attribute the winning state is not
reachable.

One of the recent popular implementations is SHAP library [46], which however
cannot be directly applied to our concept-based learning cases: JSM-hypotheses
and stability indices. The former technique assumes that unseen objects can be
left without classification or classified contradictory when for an examined
object there is no hypothesis for any class or there are at least two
hypotheses from different classes [11, 38]. This might be an especially
important property for such domains as medicine and finance where wrong
decisions may lead to regrettable outcomes. We can figure out what are the
attributes of the contradictory hypotheses we have but which attributes have
the largest positive or negative impact on the classification is still unclear
without external means. The latter case of stability indices, which were
originally proposed for ranking JSM-hypotheses by their robustness to the
deletion of object subsets from the input contexts (similarly to cross-
validation) [37, 33], is considered in an unsupervised setting. Here,
supervised interpretable techniques like SHAP are not directly applicable. To
fill the gap we formulated two corresponding games with specific valuation
functions used in the Shapley value computations.

Mapping of the two proposed approaches onto the taxonomy of IML methods says
that in the case of JSM-hypotheses it is an intrinsic model, but applying
Shapley values on top of it is post hoc. At the same time, this concrete
variant is rather model-specific since it requires customisation. This one is
local since it explains the classification of a single object. As for
attribution of concept stability, this one is definitely post hoc, model-
specific, and if each pattern (concept) is considered separately this one is
rather local but since the whole set of stable concepts can be attributed it
might be considered as a global one as well.

It is important to note that one of the stability indices was rediscovered in
the Data Mining community and known under the name of the robustness of closed
itemsets [65, 34] (where each transaction/object is kept with probability
$\alpha=0.5$). So, the proposed approach also allows attribution of closed
itemsets.

Classification and direct computation of Shapley values afterwards might be
unfeasible for large sets of attributes [8]. So, we may think of approximate
ways to compute Shapley values [63] or pay attention to attribute selection,
clarification, and reduction known in the FCA community. We would like to draw
the reader’s attention to scale coarsening as feature selection tools [13] and
a comparative survey on FCA-based attribute reduction techniques [28, 29].
However, we prefer to concentrate on attribute aggregation by similarity
222Similarity between concepts is discussed in [9] as an attribute reduction
technique which will not allow us to leave out semantically meaningful
attributes even if they are highly-correlated and redundant in terms of extra
complexity paid for their processing otherwise.

The last note on related works, which is unavoidable when we talk about IML,
is the relation to Deep Learning (DL) where black-box models predominate [60].
According to the textbook [16], “Deep Learning is a form of machine learning
that enables computer to learn from experience and understand the world in
terms of a hierarchy of concepts.” The authors also admit that there is no
need for a human computer operator to formally specify all the knowledge that
the computer needs and obtained hierarchy of concepts allows the computer to
learn complicated concepts by building them out of simpler ones. The price of
making those concepts intelligible for the computer but not necessary for a
human is paid by specially devised IML techniques in addition to DL models.

Since FCA operates with concept hierarchies and is extensively used in human-
centric applications [52], the question “What can FCA do for DL?” is open. For
example, in [58] closure operators on finite sets of attributes were encoded
by a three-layered feed-forward neural network, while in [35] the authors were
performing neural architecture search based on concept lattices to avoid
overfitting and increase the model interpretability.

##  3 Supervised Learning: From Hypotheses to Attribute Importance

In this section, we discuss how interpretable concept-based learning for JSM-
method can be achieved with Shapley Values following our previous study on the
problem [20]. Let us start with a piece of history of inductive reasoning. In
XIX century, John Stuart Mill proposed several schemes of inductive reasoning.
Let us consider, for example, the Method of Agreement [23]: “If two or more
instances of the phenomenon under investigation have only one circumstance in
common, … [it] is the cause (or effect) of the given phenomenon.”

The JSM-method (after J.S. Mill) of hypotheses generation proposed by Viktor
K. Finn in the late 1970s is an attempt to describe induction in purely
deductive form [11]. This new formulation was introduced in terms of many-
valued many-sorted extension of the First Order Predicate Logic [32].

This formal logical treatment allowed usage of the JSM-method as a machine
learning technique [37]. While further algebraic redefinitions of the logical
predicates to express similarity of objects as an algebraic operation allowed
the formulation of JSM-method as a classification technique in terms of formal
concepts [39, 32].

###  3.1 JSM-hypotheses in FCA

In FCA, a formal concept consists of an extent and an intent. The intent is
formed by all attributes that describe the concept, and the extent contains
all objects belonging to the concept. In FCA, the JSM-method is known as rule-
based learning from positive and negative examples with rules in the form
“concept intent $\to$ class”.

Let a formal context $\mathbb{K}:=(G,M,I)$ be our universe, where the binary
relation $I\subseteq G\times M$ describes if an object $g\in G$ has an
attribute $m\in M$. For $A\subseteq G$ and $B\subseteq M$ the derivation (or
Galois) operators are defined by:

$A^{\prime}=\\{\,m\in M\mid\forall a\in A\,aIm\,\\}\text{ and
}B^{\prime}=\\{\,g\in G\mid\forall b\in B\,gIb\,\\}.$

A (formal) concept is a pair $(A,B)$ with $A\subseteq G$, $B\subseteq M$ such
that $A^{\prime}=B$ and $B^{\prime}=A$. We call $B$ its intent and $A$ its
extent. An implication of the form $H\to m$ holds if all objects having the
attributes in $H$ also have the attribute $m$, i.e. $H^{\prime}\subseteq
m^{\prime}$.

The set of all concepts of a given context $\mathbb{K}$ is denoted by
${\mathfrak{B}}(G,M,\mathrel{I})$; the concepts are ordered by the “to be a
more general concept” relation as follows: $(A,B)\geq(C,D)\iff C\subseteq A\
(\mbox{equivalently }B\subseteq D)$.

The set of all formal concepts ${\mathfrak{B}}(G,M,\mathrel{I})$ together with
the introduced relation form the _concept lattice_ , which line diagram is
useful for visual representation and navigation through the concept sets.

Let $w\notin M$ be a _target attribute_ , then $w$ partitions $G$ into three
subsets:

  * •

_positive examples_ : $G_{+}\subseteq G$ of objects known to satisfy $w$,

  * •

_negative examples_ : $G_{-}\subseteq G$ of objects known not to have $w$,

  * •

_undetermined examples_ : $G_{\tau}\subseteq G$ of objects for which it
remains unknown whether they have the target attribute or do not have it.

This partition gives rise to three subcontexts
$\mathbb{K}_{\varepsilon}:=(G_{\varepsilon},M,I_{\varepsilon})$ with
$\varepsilon\in\\{-,+,\tau\\}$.

  * •

The _positive context_ $\mathbb{K}_{+}$ and the _negative context_
$\mathbb{K}_{-}$ form the training set called by _learning context_ :

$\mathbb{K}_{\pm}=(G_{+}\cup G_{-},M\cup\\{w\\},I_{+}\cup I_{-}\cup
G_{+}\times\\{w\\}).$

  * •

The subcontext $\mathbb{K}_{\tau}$ is called the _undetermined context_ and is
used to predict the class of not yet classified objects.

The whole _classification context_ is the context

$\mathbb{K}_{c}=(G_{+}\cup G_{-}\cup G_{\tau},M\cup\\{w\\},I_{+}\cup I_{-}\cup
I_{\tau}\cup G_{+}\times\\{w\\}).$

The derivation operators in the subcontexts $\mathbb{K}_{\varepsilon}$ are
denoted by $(\cdot)^{+}$ $(\cdot)^{-}$, and $(\cdot)^{\tau}$, respectively.
The goal is to classify the objects in $G_{\tau}$ with respect to $w$.

To do so let us form the positive and negative hypotheses as follows. A
_positive hypothesis_ $H\subseteq M$ ($H\neq\emptyset$) is a intent of
$\mathbb{K}_{+}$ that is not contained in the intent of a negative example;
i.e. $H^{++}=H$ and $H^{\prime}\subseteq G_{+}\cup G_{\tau}$ ($H\to w$). A
_negative hypothesis_ $H\subseteq M$ ($H\neq\emptyset$) is an intent of
$\mathbb{K}_{-}$ that is not contained in the intent of a positive example;
i.e. $H^{--}=H$ and $H^{\prime}\subseteq G_{-}\cup G_{\tau}$
($H\to\overline{w}$).

An intent of $\mathbb{K}_{+}$ that is contained in the intent of a negative
example is called a _falsified (+)-generalisation_. A _falsified
(-)-generalisation _missing__ is defined in a similar way.

To illustrate these notions we use the credit scoring context in Table 1 [22].
Note that we use _nominal scaling_ to transform many-valued context to one-
valued context [15] with the following attributes, $Ma$, $F$ (for two
genders), $Y$, $MI$, $O$ (for young, middle, and old values of the two-valued
attribute Age , resp.), $HE$, $Sp$, $SE$ (for higher, special, and secondary
education, resp.), $Hi$, $L$, $A$ (for high, low, and average salary, resp.),
and $w$ and $\overline{w}$ for the two-valued attribute Target.

Table 1: Many-valued classification context for credit scoring G / M | Gender | Age | Education | Salary | Target
---|---|---|---|---|---
1 | Ma | young | higher | high | $+$
2 | F | middle | special | high | $+$
3 | F | middle | higher | average | $+$
4 | Ma | old | higher | high | $+$
5 | Ma | young | higher | low | $-$
6 | F | middle | secondary | average | $-$
7 | F | old | special | average | $-$
8 | Ma | old | secondary | low | $-$
9 | F | young | special | high | $\tau$
10 | F | old | higher | average | $\tau$
11 | Ma | middle | secondary | low | $\tau$
12 | Ma | old | secondary | high | $\tau$

$g_{3}$

$g_{2}$

$g_{1}$

$g_{4}$

L,SE

F, Mi

A

Sp

HE

Ma

Y

O

HS

$g_{8}$

$g_{5}$

$g_{6}$

$g_{7}$

HS

L,Ma

HE,Y

A,F

Mi

Sp

Se

O

Figure 1: The line diagrams of the lattice of positive context (left) and the
lattice of negative context (right).

For example, the intent of the red node labelled by the attribute $A$ in the
left line diagram (Fig. 1), is $\\{A,Mi,F,HE\\}$, and this is not contained in
the intent of any node labelled by the objects $g_{5},g_{6},g_{7}$, and
$g_{8}$. So we believe in the rule $H\to w$. Note that the colours of the
nodes in Fig. 1 represent different types of hypotheses: the red ones
correspond to minimal hypotheses (cf. the definition below), the see green
nodes correspond to negative hypotheses, while light grey nodes correspond to
non-minimal positive and negative hypotheses for the left and the right line
diagrams, respectively.

The undetermined examples $g_{\tau}$ from $G_{\tau}$ are classified according
to the following rules:

  * •

If $g^{\tau}_{\tau}$ contains a positive, but no negative hypothesis, then
$g_{\tau}$ is _classified positively_.

  * •

If $g^{\tau}_{\tau}$ contains a negative, but no positive hypothesis, then
$g_{\tau}$ is _classified negatively_.

  * •

If $g^{\tau}_{\tau}$ contains both negative and positive hypotheses, or if
$g^{\tau}_{\tau}$ does not contain any hypothesis, then this object
classification is _contradictory_ or _undetermined_ , respectively.

To perform classification by the aforementioned rules, it is enough to have
only _minimal hypotheses_ (w.r.t. $\subseteq$) of both signs.

Let $\mathcal{H}_{+}$ (resp. $\mathcal{H}_{-}$) be the set of minimal positive
(resp. minimal negative) hypotheses. Then,

$\displaystyle\mathcal{H}_{+}=\big{\\{}\\{F,Mi,HE,A\\},\\{HS\\}\big{\\}}\text{
and }\mathcal{H}_{-}=\big{\\{}\\{F,O,Sp,A\\},\\{Se\\},\\{Ma,L\\}\big{\\}}.$

We proceed to classify the four undetermined objects below.

  * •

$g_{9}^{\prime}=\\{F,Y,Sp,HS\\}$ contains the positive hypothesis $\\{HS\\}$,
and no negative hypothesis. Thus, $g_{9}$ is classified positively.

  * •

$g_{10}^{\prime}=\\{F,O,HE,A\\}$ does not contain neither positive nor
negative hypotheses. Hence, $g_{10}$ remains undetermined.

  * •

$g_{11}^{\prime}=\\{Ma,Mi,Se,L\\}$ contains two negative hypotheses:
$\\{Se\\}$ and $\\{Ma,L\\}$, and no positive hypothesis. Therefore, $g_{11}$
is classified negatively.

  * •

$g_{12}^{\prime}=\\{Ma,O,Se,HS\\}$ contains the negative hypothesis $\\{Se\\}$
and the positive hypothesis $\\{HS\\}$, which implies that $g_{12}$ remains
undetermined.

Even though we have a clear explanation of why a certain object belongs to one
of the classes in terms of contained positive and negative hypotheses, the
following question arises: Do all attributes play the same role in the
classification of certain examples? If the answer is no, then one more
question appears: How can we rank attributes with respect to their importance
in classifying examples, for example, $g_{11}$ with attributes $Ma,Mi,Se$, and
$L$? Game Theory offers several indices for such comparison: e.g., the Shapley
value and the Banzhaf index. For the present contribution, we concentrate on
the use of Shapley values.

###  3.2 Shapley values and JSM-hypotheses

To answer the question “What are the most important attributes for
classification of a particular object?” in our case, we follow to basic recipe
studied in [63, 46, 50].

To compute the Shapley value for an example $x$ and an attribute $m$, one
needs to define $f_{x}(S)$, the expected value of the model prediction
conditioned on a subset $S$ of the input attributes.

$\phi_{m}=\sum_{S\subseteq
M\setminus\\{m\\}}\frac{|S|!(|M|-|S|-1)!}{|M|!}\left(f_{x}(S\cup\\{m\\})-f_{x}(S)\right),$
(1)

where $M$ is the set of all input attributes and $S$ a certain coalition of
players, i.e. set of attributes.

Let $\mathbb{K}_{c}=(G_{+}\cup G_{-}\cup G_{\tau},M\cup\\{w\\},I_{+}\cup
I_{-}\cup I_{\tau}\cup G_{+}\times\\{w\\})$ be our classification context, and
$\mathcal{H_{+}}$ (resp. $\mathcal{H_{-}}$) the set of minimal positive (resp.
negative) hypotheses of $\mathbb{K}_{c}$.

Since we deal with hypotheses (i.e. sets of attributes) rather than compute
the expected value of the model’s prediction, we can define a valuation
function $v$ directly. For $g\in G$, the _Shapley value of an attribute_ $m\in
g^{\prime}$:

$\varphi_{m}(g)=\sum_{S\subseteq
g^{\prime}\setminus\\{m\\}}\frac{|S|!(|g^{\prime}|-|S|-1)!}{|g^{\prime}|!}\left(v(S\cup\\{m\\})-v(S)\right),$
(2)

where

$v(S)=\begin{cases}1,&\exists H_{+}\in\mathcal{H_{+}}:H_{+}\subseteq S\mbox{
and }\forall H_{-}\in\mathcal{H_{-}}:H_{-}\not\subseteq S,\\\ -1,&\exists
H_{-}\in\mathcal{H_{-}}:H_{-}\subseteq S\mbox{ and }\forall
H_{+}\in\mathcal{H_{+}}:H_{+}\not\subseteq S\\\
0,&\text{otherwise}\end{cases}$

The Shapley value $\varphi_{m}(g)$ is set to 0 for every $m\in M\setminus
g^{\prime}$. The Shapley vector for a given object $g$ is denoted by
$\varPhi(g)$. To differentiate between the value in cases when $m\in
M\setminus g^{\prime}$ and $m\in g^{\prime}$, we will use decimal separator as
follows, 0 and 0.0, respectively.

For the credit scoring context, the minimal positive and the negative
hypotheses are

$\displaystyle\mathcal{H}_{+}$ $\displaystyle=\\{\\{F,Mi,HE,A\\},\\{HS\\}\\};\
\mathcal{H}_{-}=\\{\\{F,O,Sp,A\\},\\{Se\\},\\{M,L\\}\\}.$

The Shapley values for JSM-hypotheses have been computed with our freely
available Python scripts333https://github.com/dimachine/Shap4JSM for the
objects in $G_{\tau}$:

  * •

$g_{9}^{\prime}=\\{F,Y,Sp,HS\\}\supseteq\\{HS\\}$, and $g_{9}$ is classified
positively. $\varphi_{\text{HS}}(g_{9})=1$ and and its Shapley vector is
$\varPhi(g_{9})=(0,0.0,0.0,0,0,0,0.0,0,1.0,0,0)\mbox{ .}$

  * •

$g_{10}^{\prime}=\\{F,O,HE,A\\}$ and $g_{10}$ remains undetermined. Its
Shapley vector is $\varPhi(g_{10})=(0,0.0,0,0,0.0,0.0,0,0,0,0.0,0)\mbox{ .}$

  * •

$g_{11}^{\prime}=\\{Ma,Mi,Se,L\\}\supseteq\\{Se\\},\ \\{Ma,L\\}$. Its Shapley
vector is
${\varPhi(g_{11})=(-1/6,0,0,0.0,0,0,0,-2/3,0,0,-1/6)}\mbox{ .}$

  * •

$g_{12}^{\prime}=\\{Ma,O,Se,HS\\}\supseteq\\{HS\\},\ \\{Se\\}$.
$\varphi_{\text{Se}}(g_{12})=-1$, $\varphi_{\text{HS}}(g_{12})=1$. Its Shapley
vector is $\varPhi(g_{12})=(0.0,0,0,0,0.0,0,0,-1.0,1.0,0,0)\mbox{ .}$

Let us examine example $g_{11}$. Its attribute $Mi$ has zero importance
according to the Shapley value approach since it is not in any contained
hypothesis used for the negative classification. The most important attribute
is $Se$, which is alone two times more important than the attributes $Ma$ and
$L$ together. It is so, since the attribute $Se$, which is the single
attribute of the negative hypothesis $\\{Se\\}$, forms more winning coalitions
$S\cup\\{Se\\}$ with $v(S\cup\\{Se\\})-v(S)=1$ than $Ma$ and $L$, i.e. six vs.
two. Thus,
$\\{Se\\}\uparrow\setminus\\{Ma,L\\}\uparrow=\\{\\{Se\\},\\{Ma,Se\\},\\{Mi,Se\\},\\{Se,L\\},\\{Mi,Se,L\\},$
$\\{Ma,Mi,Se\\}\\}$444$S\uparrow$ is the up-set of $S$ in the Boolean lattice
$(\mathcal{P}\\{Ma,Mi,Se,L\\},\subseteq)$ are such winning coalitions for
$Se$, while $\\{Ma,L\\}$, $\\{Ma,Mi,L\\}$, are those for $Ma$ and $L$.

The following properties hold:

######  Theorem 3.1 ([20])

The Shapley value, $\varphi_{m}(g)$, of an attribute $m$ for the JSM-
classification of an object $g$, fulfils the following properties:

  1. 1.

$\sum\limits_{m\in g^{\prime}}\varphi_{m}(g)=1$ if $g$ is classified
positively;

  2. 2.

$\sum\limits_{m\in g^{\prime}}\varphi_{m}(g)=-1$ if $g$ is classified
negatively.

  3. 3.

$\sum\limits_{m\in g^{\prime}}\varphi_{m}(g)=0$ if $g$ is classified
contradictory or undetermined.

The last theorem expresses the so-called _efficiency property_ or axiom [59],
where it is stated that the sum of Shapley values of all players in a game is
equal to the total pay-off of their coalition, i.e. $v(g^{\prime})$ in our
case.

It is easy to check $\varphi_{m}(g)=0$ for every $m\in g^{\prime}$ that does
not belong to at least one positive or negative hypothesis contained in
$g^{\prime}$. Moreover, in this case for any $S\subseteq
g^{\prime}\setminus\\{m\\}$ it also follows $v(S)=v(S\cup\\{m\\})$ and these
attributes are called _null_ or _dummy players_ [59].

We also performed experiments on the Zoo
dataset555https://archive.ics.uci.edu/ml/datasets/zoo, which includes 101
examples (animals) and their 17 attributes along with the target attribute (7
classes of animals). The attributes are binary except for the number of legs,
which can be scaled nominally and treated as categorical.

We consider a binary classification problem where _birds_ is our positive
class, while all the rest form the negative class.

There are 19 positive examples (birds) and 80 negative examples since we left
out two examples for our testing set, namely, chicken and warm. The hypotheses
are
$\mathcal{H}_{+}=\big{\\{}\\{feathers,eggs,backbone,breathes,legs_{2},tail\\}\big{\\}}$
and

$\displaystyle\mathcal{H}_{-}=$
$\displaystyle\big{\\{}\\{venomous\\},\\{eggs,aquatic,predator,legs_{5}\\},\\{legs_{0}\\},\\{eggs,legs_{6}\\},$
$\displaystyle\\{predator,legs_{8}\\},\\{hair,breathes\\},\\{milk,backbone,breathes\\},\\{legs_{4}\\},$
$\displaystyle\\{toothed,backbone\\}\big{\\}}.$

The intent
$aardvark^{\prime}=\\{hair,milk,predator,toothed,backbone,breathes,legs_{4},catsize\\}$
contains four negative hypotheses and no positive one.

The Shapley vector for the aardvark example is

$(-0.1,0,0,-0.0167,0,0,0.0,-0.1,-0.133,-0.133,0,0,-0.517,0,0,0,0,0,0,0,0.0)\mbox{
.}$

Backbone, breathes, and four legs are the most important attributes with
values -0.517, -0.133, and -0.133, respectively, while catsize is not
important in terms of Shapley value.

Figure 2: The Shapley vector diagram for the aardvark example

A useful interpretation of classification results could be an explanation for
true positive or true negative cases. However, in the case of our test set
both examples, chicken and warm, are classified correctly as bird and non-
bird, respectively. Let us have a look at their Shapley vectors. Our test
objects have the following intents:

$chicken^{\prime}=\\{feathers,eggs,airborne,backbone,breathes,legs_{2},tail,domestic\\}$

and

$warm^{\prime}=\\{eggs,breathes,legs_{0}\\}.$

Figure 3: The Shapley vector diagram for the chicken (left) and warm (right)
examples

Thus, for the chicken example all six attributes that belong to the single
positive hypothesis have equal Shapley values, i.e. 1/6. The attributes
airborne and domestic have zero importance. The warm example has only one
attribute with non-zero importance, i.e. the absence of legs with importance
-1. It is so since the only negative hypothesis, $\\{legs_{0}\\}$, is
contained in the object intent.

##  4 Unsupervised Learning: Contribution to Stability and Robustness

(Intensional) stability indices were introduced to rank the concepts (intents)
by their robustness under objects deletion and provide evidence of the non-
random nature of concepts [56]. The extensional stability index is defined as
the proportion of intent subsets generating this intent; it shows the
robustness of the concept extent under attributes deletion [56]. Our goal here
is to find out whether all attributes play the same role in the stability
indices. To measure the importance of an attribute for a concept intent, we
compare generators with this attribute to those without it. In this section,
we demonstrate how Shapley values can be used to assess attribute importance
for concept stability.

###  4.1 Stability indices of a concept

Let $\mathbb{K}:=(G,M,I)$ be a formal context. For any closed subset $X$ of
attributes or objects, we denote by $\mathrm{gen}(X)$ the set of generating
subsets of $X$. The _extensional stability index_ [56] of a concept $(A,B)$ is

$\displaystyle\sigma_{e}(A,B)$ $\displaystyle:=\frac{|\\{Y\subseteq B\mid
Y^{\prime\prime}=B\\}|}{2^{|B|}}=\frac{|\mathrm{gen}(B)|}{2^{|B|}}.$

We can also restrict to generating subsets of equal size. The extensional
stability index of the $k$-th level of $(A,B)$ is

$J_{k}(A,B):=|\\{Y\subseteq
B\mid|Y|=k,Y^{\prime\prime}=B\\}|\Big{/}\binom{|B|}{k}.$

###  4.2 Shapley vectors of intents for concept stability

Let $(A,B)$ be a concept of $(G,M,I)$ and $m\in B$. We define an indicator
function by

$v(Y)=1\mbox{ if }Y^{\prime\prime}=B\text{ and }\ Y\neq\emptyset,\mbox{ and
}v(Y)=0\text{ otherwise}.$

Using the indicator $v$, the Shapley value of $m\in B$ for the stability index
of the concept $(A,B)$ is defined by:

$\varphi_{m}(A,B):=\frac{1}{|B|}\sum\limits_{Y\subseteq
B\setminus\\{m\\}}\frac{1}{\binom{|B|-1}{|Y|}}\Big{(}v(Y\cup\\{m\\})-v(Y)\Big{)}.$
(3)

The Shapley vector of $(A,B)$ is then $\left(\varphi_{m}(A,B)\right)_{m\in
B}$. An equivalent formulation is given using upper sets of minimal generators
[21]. In fact, for $m\in X_{m}\in\mathrm{mingen}(B)$ and $m\notin
X_{\overline{m}}\in\mathrm{mingen}(B)$, we have

$\varphi_{m}(A,B)=\frac{1}{|B|}\sum\limits_{D\sqcup\\{m\\}\in\bigcup
X_{m}\uparrow\setminus\bigcup
X_{\overline{m}}\uparrow}\frac{1}{\binom{|B|-1}{|D|}},$

where $\sqcup$ denotes the disjoint union, $X_{m}$ and $X_{\overline{m}}$ the
minimal generators of $B$ with and without $m$, respectively.

Figure 4: Computing Shapley vectors for concept stability

To compute $\varphi_{m}$, additional simplifications are useful:

######  Theorem 4.1 ([21])

Let $(A,B)$ be a concept and $m\in B$.

  * (i)

$\varphi_{m}(A,B)=\sum\limits_{k=1}^{|B|}\frac{J_{k}(A,B)}{k}-\sum\limits_{D\subseteq
B\setminus\\{m\\}}\frac{1}{|D|\binom{|B|-1}{|D|}}v(D)$.

  * (ii)

If $m\in X_{m}\in\mathrm{mingen}(B)$ and $Y\subseteq B\setminus\\{m\\}$ with
$(A,B)\prec(Y^{\prime},Y)$ then

$\varphi_{m}(A,B)=\frac{1}{|B|}\sum\limits_{D\in\bigcup[X_{m}\setminus{\\{m\\}},Y]}\frac{1}{\binom{|B|-1}{|D|}}.$

  * (iii)

If $m\in X\in\mathrm{mingen}(B)$ and $|\mathrm{mingen}(B)|=1$, then

$\varphi_{m}(A,B)=\sum\limits_{k=1}^{|B|}\frac{J_{k}(A,B)}{k}=\frac{1}{|X|}\
.$ (4)

To illustrate the importance of attributes in concept stability, we consider
the the fruits context [31], where we extract the subcontext with the first
four objects (Table 2).

Table 2: A many-valued context of fruits |  G $\setminus$ M | color | firm | smooth | form
---|---|---|---|---|---
1 | apple | yellow | no | yes | round
2 | grapefruit | yellow | no | no | round
3 | kiwi | green | no | no | oval
4 | plum | blue | no | yes | oval

After scaling we get the binary context and its concept lattice diagram (Fig.
5).

Fruits | w | y | g | b | f | $\bar{f}$ | s | $\bar{s}$ | r | $\bar{r}$
---|---|---|---|---|---|---|---|---|---|---
1 apple |  | $\times$ |  |  |  | $\times$ | $\times$ |  | $\times$ |
2 grapefruit |  | $\times$ |  |  |  | $\times$ |  | $\times$ | $\times$ |
3 kiwi |  |  | $\times$ |  |  | $\times$ |  | $\times$ |  | $\times$
4 plum |  |  |  | $\times$ |  | $\times$ | $\times$ |  |  | $\times$

$g_{3}$

$g_{4}$

$g_{2}$

$g_{1}$

$\bar{f}$

f,w

$\bar{r}$

g

b

r,y

$\bar{s}$

s

Figure 5: A scaled fruits context and the line diagram of its concept lattice

For each concept, the stability index $\sigma_{e}$ and its Shapley vector
$\phi$ are computed.

Table 3: The concepts of fruits context and their stability indices along with
Shapley vectors

Concepts | $\sigma_{e}$ | $\Phi$
---|---|---
$(\\{4\\},\\{b,\bar{f},s,\bar{r}\\})$ | 0.625 | (2/3, 0.0, 1/6, 1/6)
$(\\{3\\},\\{g,\bar{f},\bar{s},\bar{r}\\})$ | 0.625 | (2/3, 0.0, 1/6, 1/6)
$(\\{3,4\\},\\{\bar{f},\bar{r}\\})$ | 0.5 | (0.0, 1.0)
$(\\{2\\},\\{y,\bar{f},\bar{s},r\\})$ | 0.375 | (1/6, 0.0, 2/3, 1/6)
$(\\{2,3\\},\\{\bar{f},\bar{s}\\})$ | 0.5 | (0.0, 1.0)
$(\\{1\\},\\{y,\bar{f},s,r\\})$ | 0.375 | (1/6, 0.0, 2/3, 1/6)
$(\\{1,4\\},\\{\bar{f},s\\})$ | 0.5 | (0.0, 1.0)
$(\\{1,2\\},\\{y,\bar{f},r\\})$ | 0.75 | (0.5, 0.0, 0.5)
$(\\{1,2,3,4\\},\\{\bar{f}\\})$ | 1 | (0.0)

$\sigma_{e}(\emptyset,\\{w,y,g,b,f,\bar{f},s,\bar{s},r,\bar{r}\\})=0.955$
---
$\Phi=(0.256,0.069,0.093,0.093,0.260,0.0,0.052,0.052,0.069,0.052)$

For the Zoo dataset we obtain 357 concepts in total. The top-3 most stable are
$c_{1},c_{2},c_{3}$ with extent stability indices:
$\sigma_{e}(G,\emptyset)=1$, $\sigma_{e}(\emptyset,M)=0.997$,
$\sigma_{e}(A,A^{\prime})=0.625$, respectively, where
$A^{\prime}=\\{feathers,eggs,backbone,breathes,legs_{2},tail\\}$ and

$A=\\{11,16,20,21,23,33,37,41,43,56,57,58,59,71,78,79,83,87,95,100\\}\ .$

Figure 6: The Shapley vector for concept $c_{2}=(\emptyset,M)$ (left) and
$c_{3}$ (right)

The most important attributes are six legs, eight legs, five legs, feathers,
and four legs for $c_{2}$, and feathers, eggs, and two legs for $c_{3}$,
w.r.t. to the Shapley vectors.

The demo is available on GitHub666https://github.com/dimachine/ShapStab/.
Shapley values provide a tool for assessing the attribute importance of stable
concepts. Comparison with other (not only Game-theoretic) techniques for local
interpretability is desirable. We believe that the attribute importance can be
lifted at the context level, via an aggregation, and by then offer a
possibility for attribute reduction, similar to the principal component
analysis (PCA) method.

##  5 Attribute Similarity and Reduction

Computation of attribute importance could lead to ranking the attributes of
the context, and by then classifying the attributes with respect to their
global importance, similar to principal component analysis. Therefore cutting
off at a certain threshold could lead to attribute reduction in the context.
Other methods leading to attributes reduction are based on their granularity,
an ontology or an is-a taxonomy, by using coarser attributes. Less coarse
attributes are then put together by going up in the taxonomy and are
considered to be similar. In the present section, we briefly discuss the
effect of putting attributes together on the resulting concept lattice. Doing
this leads to the reduction of the number of attributes, but not always in the
reduction of the number of concepts.

Before considering such compound attributes, we would like to draw the
readers’ attention to types of data weeding that often overlooked outside of
the FCA community [55, 28, 29], namely, clarification and reduction.

###  5.1 Clarification and reduction

A context $(G,M,I)$ is called _clarified_ [15], if for any objects $g,h\in G$
from $g^{\prime}=h^{\prime}$ it always follows that $g=h$ and, similarly,
$m^{\prime}=n^{\prime}$ implies $m=n$ for all $m,n\in M$. A clarification
consists in removing duplicated lines and columns from the context. This
context manipulation does not alter the structure of the concept lattice,
though objects with the same intents and attributes with the same extents are
merged, respectively.

The structure of the concept lattice remains unchanged in case of removal of
_reducible attributes_ and _reducible objects_ [15]; An attribute $m$ is
reducible if it is a combination of other attributes, i.e.
$m^{\prime}=Y^{\prime}$ for some $Y\subseteq M$ with $m\not\in Y$. Similarly,
an object $g$ is reducible if $g^{\prime}=X^{\prime}$ for some $X\subseteq G$
with $g\not\in X$. For example, full rows ($g^{\prime}=M$) and full columns
($m^{\prime}=G$) are always reducible.

However, if our aim is a subsequent interpretation of patterns, we may wish to
keep attributes (e.g. in aggregated form), rather than leaving them out before
knowing their importance.

###  5.2 Generalised attributes

As we know, FCA is used for conceptual clustering and helps discover patterns
in terms of clusters and rules. However, the number of patterns can explode
with the size of an input context. Since the main goal is to maintain a
friendly overview of the discovered patterns, several approaches have been
investigated to reduce the number of attributes without loss of much
information [55, 28]. One of these suggestions consists in using is-a
taxonomies. Given a taxonomy on attributes, how can we use it to discover
_generalised_ patterns in the form of clusters and rules? If there is no
taxonomy, can we (interactively) design one? We will discuss different
scenarios of grouping attributes or objects, and the need of designing
similarity measures for these purposes in the FCA setting.

To the best of our knowledge the problem of mining generalised association
rules was first introduced around 1995 in [61, 62], and rephrased as follows:
Given a large database of transactions, where each transaction consists of a
set of items, and a taxonomy (is-a hierarchy) on the items, the goal is to
find associations between items at any level of the taxonomy. For example,
with a taxonomy that says that jackets is-a outerwear and outerwear is-a
clothes, we may infer a rule that “people who buy outerwear tend to buy
shoes”. This rule may hold even if rules that “people who buy jackets tend to
buy shoes”, and “people who buy clothes tend to buy shoes” do not hold. (See
Fig. 7)

(a) Database $\mathcal{D}$ Transaction | Items bought
---|---
100 | Shirt
200 | Jacket, Hiking Boots
300 | Ski Pants, Hiking Boots
400 | Shoes
500 | Shoes
600 | Jacket

[.Clothes [.Outwear [.Jackets ] [.Ski Pants ] ] [.Shirts ]] [.Footwear [.Shoes
] [.Hiking Boots ]]

(b) Taxonomy $\mathcal{T}$

(c) Frequent itemsets Itemset | Support
---|---
Jacket | 2
Outwear | 3
Clothes | 4
Shoes | 2
Hiking Boots | 2
Footwear | 4
Outwear, Hiking Boots | 2
Clothes, Hiking Boots | 2
Outwear, Footwear | 2
Clothes, Footwear | 2

(d) Association rules Rule | Support | Confidence
---|---|---
Outwear $\to$ Hiking Boots | 1/3 | 2/3
Outwear $\to$ Footwear | 1/3 | 2/3
Hiking Boots $\to$ Outwear | 1/3 | 1
Hiking Boots $\to$ Clothes | 1/3 | 1

Figure 7: A database of transactions, taxonomies and extracted rules [61, 62]

A generalised association rule is a (partial) implication $X\to Y$, where
$X,Y$ are disjoint itemsets and no item in $Y$ is a generalisation of any item
in $X$ [61, 62]. We adopt the following notation:
$\mathcal{I}=\\{i_{1},i_{2},\cdots,i_{m}\\}$ is a set of items and
$\mathcal{D}=\\{t_{1},t_{2},\cdots,t_{n}\\}$ a set of transactions. Each
transaction $t\in\mathcal{D}$ is a subset of items $\mathcal{I}$. Let
$\mathcal{T}$ be a set of taxonomies (i.e directed acyclic graph on items and
generalised items). We denote by $(\mathcal{T},\leq)$ its transitive closure.
The elements of $\mathcal{T}$ are called “general items”. A transaction $t$
_supports_ an item $x$ (resp. a general item $y$) if $x$ is in $t$ (resp. $y$
is a generalisation of an item $x$ in $t$). A set of transactions $T$
_supports_ an itemset $X\subseteq\mathcal{I}$ if $T$ supports every item in
$X$.

In FCA setting, we build a generalised context
$(\mathcal{D},\mathcal{I}\cup\mathcal{T},I)$, where the set of objects,
$\mathcal{D}$, is the set of transactions (strictly speaking transaction-ID),
and the set of attributes, $M=\mathcal{I}\cup\mathcal{T}$, contains all items
($\mathcal{I}$) and general items ($\mathcal{T}$). The incidence relation
$I\subseteq\mathcal{D}\times M$ is defined by

$tIm\iff\begin{cases}m\in\mathcal{I}\text{ and }m\in t\\\
m\in\mathcal{T}\text{ and }\exists n\in\mathcal{I},n\in t\text{ and }n\leq
m.\end{cases}$

Below is the context associated to the example on Figure 7.

| Shirt | Jacket | Hiking Boots | Ski Pants | Shoes | Outerwear | Clothes | Footwear
---|---|---|---|---|---|---|---|---
100 | $\times$ |  |  |  |  |  | $\times$ |
200 |  | $\times$ | $\times$ |  |  | $\times$ | $\times$ | $\times$
300 |  |  | $\times$ | $\times$ |  | $\times$ | $\times$ | $\times$
400 |  |  |  |  | $\times$ |  |  | $\times$
500 |  |  |  |  | $\times$ |  |  | $\times$
600 |  | $\times$ |  |  |  | $\times$ | $\times$ |

The basic interestingness measures for a generalised rule $X\to Y$ are support
and confidence (see association rules in Fig. 7 (d)). Its _support_ $supp(X\to
Y)$ is defined as $\frac{|(X\cup Y)^{\prime}|}{|\mathcal{D}|}$, while its
_confidence_ $conf(X\to Y)$ is $\frac{|(X\cup Y)^{\prime}|}{|X^{\prime}|}$.

For some applications, it would make sense to work only with the subcontext
$(\mathcal{D},\mathcal{T},I\cap\mathcal{D}\times\mathcal{T})$ instead of
$(\mathcal{D},\mathcal{I}\cup\mathcal{T},I)$, for example if the goal is to
reduce the number of attributes, concepts or rules. Sometimes, there is no
taxon available to suggest that considered attributes should be put together.
However, we can extend the used taxonomy, i.e. put some attributes together in
a proper taxon, and decide when an object satisfies the grouped attributes.

###  5.3 Generalising scenarios

Let $\mathbb{K}:=(G,M,I)$ be a context. The attributes of $\mathbb{K}$ can be
grouped to form another set of attributes, namely $S$, whose elements are
called generalised attributes. For example, in basket market analysis, items
(products) can be generalised into product lines and then product categories,
and even customers may be generalised to groups according to specific features
(e.g., income, education). This replaces $(G,M,I)$ with a context $(G,S,J)$
where $S$ can be seen as an index set such that $\\{m_{s}\mid s\in S\\}$
covers $M$. How to define the incidence relation $J$, is domain dependent. Let
us consider several cases below [43, 44, 42]:

  * $(\exists)$

$gJs:\iff\exists m\in s,\,g\mathop{\mbox{\rm I}}m$. When companies are
described by the locations of their branches then cities can be grouped to
regions or states. A company $g$ operates in a state $s$ if $g$ has a branch
in a city $m$ which is in $s$.

  * $(\forall)$

$gJs:\iff\forall m\in s,\,g\mathop{\mbox{\rm I}}m$. For exams with several
components (e.g. written, oral, and thesis), we might require students to pass
all components in order to succeed.

  * $(\alpha\%)$

$gJs:\iff\frac{|\\{m\in s\ \mid\ gIm\\}|}{|s|}\geq\alpha_{s}$ with
$\alpha_{s}$ a threshold. In the case of exams discussed above, we could
require students to pass just some parts, defined by a threshold.

Similarly, objects can also be put together to get “generalised objects”. In
[54] the author described _general on objects_ as classes of individual
objects that are considered to be extents of concepts of a formal context. In
that paper, different contexts with general objects are defined and their
conceptual structure and relation to other contexts is analysed with FCA
methods. Generalisation on both objects and attributes can be carried out with
the combinations below, with $A\subseteq G$ and $B\subseteq M$:

  1. 1.

$AJB$ iff $\exists a\in A$, $\exists b\in B$ such that $a\mathop{\mbox{\rm
I}}b$ (i.e. some objects from $A$ are in relation with some attributes in
$B$);

  2. 2.

$AJB$ iff $\forall a\in A$, $\forall b\in B\ a\mathop{\mbox{\rm I}}b$ (i.e.
each object in $A$ has all attributes in $B$);

  3. 3.

$AJB$ iff $\forall a\in A$, $\exists b\in B$ such that $a\mathop{\mbox{\rm
I}}b$ (i.e. each object in $A$ has at least one attribute in $B$);

  4. 4.

$AJB$ iff $\exists b\in B$ such that $\forall a\in A$ $a\mathop{\mbox{\rm
I}}b$ (i.e. an attribute in $B$ is satisfied by all objects of $A$);

  5. 5.

$AJB$ iff $\forall b\in B$, $\exists a\in A$ such that $a\mathop{\mbox{\rm
I}}b$ ( i.e. each property in $B$ is satisfied by an object of $A$);

  6. 6.

$AJB$ iff $\exists a\in A$ such that $\forall b\in B\ a\mathop{\mbox{\rm I}}b$
(i.e. an object in $A$ has all attributes in $B$);

  7. 7.

$AJB$ iff $\frac{\left|\\{a\in A\mid\frac{|\\{b\in B\mid a\mathop{\mbox{\rm
I}}b\\}|}{|B|}\geq\beta_{B}\\}\right|}{|A|}\geq\alpha_{A}$ (i.e. at least
$\alpha_{A}\%$ of objects in $A$ have each at least $\beta_{B}\%$ of the
attributes in $B$);

  8. 8.

$AJB$ iff $\frac{\left|\left\\{b\in B\mid\frac{|\\{a\in A\mid
a\mathop{\mbox{\rm
I}}b\\}|}{|A|}\geq\alpha_{A}\right\\}\right|}{|B|}\geq\beta_{B}$ (i.e. at
least $\beta_{B}\%$ of attributes in $B$ belong altogether to at least
$\alpha_{A}\%$ of objects in the group $A$);

  9. 9.

$AJB$ iff $\frac{|A\times B\cap I|}{|A\times B|}\geq\alpha$ (i.e. the density
of the rectangle $A\times B$ is at least $\alpha$).

###  5.4 Generalisation and extracted patterns

After analysing several generalisation cases, including simultaneous
generalisations on both objects and attributes as above, the next step is to
look at the extracted patterns. From contexts, knowledge is usually extracted
in terms of clusters and rules. When dealing with generalised attributes or
objects, we coin the term “generalised” to all patterns extracted. An
immediate task is to compare knowledge gained after generalising with those
from the initial context.

New and interesting rules as seen in Figure 7 can be discovered [61, 62].
Experiments have shown that the number of extracted patterns quite often
decreases. Formal investigations are been carried out to compare these
numbers. For $\forall$-generalisations, the number of concepts does not
increase [42]. But for $\exists$-generalisations, the size can actually
increase [43, 44, 42, 40, 41].

In [3] the authors propose a method to control the structure of concept
lattices derived from Boolean data by specifying granularity levels of
attributes. Here a taxonomy is already available, given by the granularity of
the attributes. They suggest that granularity levels should be chosen by a
user based on his expertise and experimentation with the data. If the
resulting formal concepts are too specific and there is a large number of
them, the user can choose to use a coarser level of granularity. The resulting
formal concepts are then less specific and can be seen as resulting from a
zoom-out. Similarly, one may perform a zoom-in to obtain finer, more specific
formal concepts. Through all these precautions, the number of concepts can
still increase when attributes are coarser: “The issue of when attribute
coarsening results in an increase in the number of formal concepts needs a
further examination, as well as the possibility of informing automatically a
user who is selecting a new level of granularity that the new level results in
an increase in the number of concepts.” [3]

In [41] a more succinct analysis of $\exists$-generalisations presents a
family of contexts where generalising two attributes results in an exponential
increase in the number of concepts. An example of such context is given in the
Table 4 (left).

Table 4: A formal context (left) and its $\exists$-generalisation that puts
$m_{1}$ and $m_{2}$ together. The number of concepts increases from 48 to 64,
i.e. by 16.

| $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $m_{1}$ | $m_{2}$
---|---|---|---|---|---|---|---|---
$1$ |  | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ |
$2$ | $\times$ |  | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
$3$ | $\times$ | $\times$ |  | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
$4$ | $\times$ | $\times$ | $\times$ |  | $\times$ | $\times$ | $\times$ | $\times$
$5$ | $\times$ | $\times$ | $\times$ | $\times$ |  | $\times$ | $\times$ | $\times$
$6$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ |  |  | $\times$
$g_{1}$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ |  |

$\Longrightarrow$ $1$ $2$ $3$ $4$ $5$ $6$ $m_{12}$ $1$ $\times$ $\times$
$\times$ $\times$ $\times$ $\times$ $2$ $\times$ $\times$ $\times$ $\times$
$\times$ $\times$ $3$ $\times$ $\times$ $\times$ $\times$ $\times$ $\times$
$4$ $\times$ $\times$ $\times$ $\times$ $\times$ $\times$ $5$ $\times$
$\times$ $\times$ $\times$ $\times$ $\times$ $6$ $\times$ $\times$ $\times$
$\times$ $\times$ $\times$ $g_{1}$ $\times$ $\times$ $\times$ $\times$
$\times$ $\times$

Putting together some attributes does not always reduce the number of
extracted patterns. It’s therefore interesting to get measures that suggest
which attributes can be put together, in the absence of a taxonomy. The goal
would be to not increase the size of extracted patterns.

###  5.5 Similarity and existential generalisations

This section presents investigations on the use of certain similarity measures
in generalising attributes. A _similarity measure_ on a set $M$ of attributes
is a function $S:M\times M\to\mathbb{R}$ such that for all $m_{1},m_{2}$ in
$M$,

  * (i)

$S(m_{1},m_{2})\geq 0$, positivity

  * (ii)

$S(m_{1},m_{2})=S(m_{2},m_{1})$ symmetry

  * (iii)

$S(m_{1},m_{1})\geq S(m_{1},m_{2})$ maximality

We say that $S$ is _compatible_ with generalising attributes if whenever
$m_{1},m_{2}$ are more similar than $m_{3},m_{4}$, then putting $m_{1},m_{2}$
together should not lead to more concepts than putting $m_{3},m_{4}$ together
does. To give the formula for some known similarity measures that could be of
interest in FCA setting, we adopt the following notation for $m_{1},m_{2}$
attributes in $\mathbb{K}$:

$a=|m_{1}^{\prime}\cap m_{2}^{\prime}|,\quad d=|m_{1}^{\prime}\Delta
m_{2}^{\prime}|,\quad b=|m_{1}^{\prime}\setminus m_{2}^{\prime}|,\quad
c=|m_{2}^{\prime}\setminus m_{1}^{\prime}|.$

Table 5: Some similarity measures relevant in FCA Name | Formula | Name | Formula
---|---|---|---
Jaccard (Jc) | $\dfrac{a}{a+b+c}$ |  Sneath/Sokal (SS1) | $\dfrac{2(a+d)}{2(a+d)+b+c}$
Dice (Di) | $\dfrac{2a}{2a+b+c}$ |  Sneath/Sokal (SS2) | $\dfrac{0.5a}{0.5a+b+c}$
Sorensen (So) | $\dfrac{4a}{4a+b+c}$ | Sokal/Michener (SM) | $\dfrac{a+d}{a+d+b+c}$
Anderberg (An) | $\dfrac{8a}{8a+b+c}$ | Rogers/Tanimoto (RT) | $\dfrac{0.5(a+d)}{0.5(a+d)+b+c}$
Orchiai (Or) | $\dfrac{a}{\sqrt{(a+b)(a+c}}$ | Russels/Rao (RR) | $\dfrac{a}{a+d+b+c}$
Kulczynski (Ku) | $\dfrac{0.5a}{a+b}+\dfrac{0.5a}{a+c}$ | Yule/Kendall (YK) | $\dfrac{ad}{ad+bc}$

For the context left in Table 4, we have computed $S(m_{1},x),\
x=1,\ldots,6,m_{2}$. Although $m_{1}$ is more similar to $m_{2}$ than any
attribute $i<6$, putting $m_{1}$ and $m_{2}$ together increases the number of
concepts. Note that putting $m_{1}$ and $6$ together is equivalent to removing
$m_{1}$ from the context, and thus, reduces the number of concepts.

Table 6: The values of considered similarity measures $S(m,i)$ | Jc | Di | So | An |  SS2 | Ku | Or | SM | RT |  SS1 | RR
---|---|---|---|---|---|---|---|---|---|---|---
$i\in S_{5}$ | 0.57 | 0.80 | 0.89 | 0.94 | 0.50 | 0.80 | 0.80 | 0.71 | 0.56 | 0.83 | 0.57
$i=6$ | 0.83 | 0.91 | 0.95 | 0.97 | 0.71 | 0.92 | 0.91 | 0.75 | 0.75 | 0.92 | 0.71
$i=m_{2}$ | 0.67 | 0.80 | 0.89 | 0.94 | 0.50 | 0.80 | 0.80 | 0.71 | 0.56 | 0.83 | 0.57

Let $\mathbb{K}$ be a context $(G,M,I)$ with $a,b\in M$ and $\mathbb{K}_{00}$
be its subcontext without $a,b$. Below, $\mathop{\mbox{\rm
Ext}}(\mathbb{K}_{00}$) means all the extents of concepts of the context
$\mathbb{K}_{00}$. In order to describe the increase in the number of concepts
after putting $a,b$ together, we set

$\displaystyle\mathcal{H}(a)$ $\displaystyle:=\left\\{A\cap a^{\prime}\mid
A\in\mathop{\mbox{\rm Ext}}(\mathbb{K}_{00})\text{ and }A\cap
a^{\prime}\notin\mathop{\mbox{\rm Ext}}(\mathbb{K}_{00})\right\\}$
$\displaystyle\mathcal{H}(b)$ $\displaystyle:=\left\\{A\cap b^{\prime}\mid
A\in\mathop{\mbox{\rm Ext}}(\mathbb{K}_{00})\text{ and }A\cap
b^{\prime}\notin\mathop{\mbox{\rm Ext}}(\mathbb{K}_{00})\right\\}$
$\displaystyle\mathcal{H}(a\cup b)$
$\displaystyle:=\left\\{A\cap(a^{\prime}\cup b^{\prime})\mid
A\in\mathop{\mbox{\rm Ext}}(\mathbb{K}_{00}),\ A\cap(a^{\prime}\cup
b^{\prime})\notin\mathop{\mbox{\rm Ext}}(\mathbb{K}_{00})\right\\}$
$\displaystyle\mathcal{H}(a\cap b)$
$\displaystyle:=\left\\{A\cap(a^{\prime}\cap b^{\prime})\mid
A\in\mathop{\mbox{\rm Ext}}(\mathbb{K}_{00}),\ A\cap(a^{\prime}\cap
b^{\prime})\notin\mathop{\mbox{\rm Ext}}(\mathbb{K}_{00})\right\\}.$

The following proposition shows that the increase can be exponential.

######  Theorem 5.1 ([41])

Let $(G,M,\mathop{\mbox{\rm I}})$ be an attribute reduced context and $a,b$ be
two attributes such that their generalisation $s=a\cup b$ increases the size
of the concept lattice. Then
$|\mathfrak{B}(G,M,I)|=|\mathfrak{B}(G,M\setminus\\{a,b\\},I\subseteq G\times
M\setminus\\{a,b\\})|+|\mathcal{H}(a,b)|$, with

$\displaystyle|\mathcal{H}(a,b)|$
$\displaystyle=|\mathcal{H}(a)\cup\mathcal{H}(b)\cup\mathcal{H}(a\cap b)|\leq
2^{|a^{\prime}|+|b^{\prime}|}-2^{|a^{\prime}|}-2^{|b^{\prime}|}+1.$

This upper bound can be reached.

The difference $|\mathcal{H}(a,b)|$ is then used to define a compatible
similarity measure. We set

$\psi(a,b):=|\mathcal{H}(a\cup b)|-|\mathcal{H}(a,b)|$,
$\delta(a,b):=\begin{cases}1&\text{ if \ }\psi(a,b)\leq 0\\\ 0&\text{
else}\end{cases}$, and define

$S(a,b):=\dfrac{1+\delta(a,b)}{2}-\dfrac{|\psi(a,b)|}{2n_{0}}$ with
$n_{0}=\max\\{\psi(x,y)\mid x,y\in M\\}$. Then

######  Theorem 5.2 ([30])

$S$ is a similarity measure compatible with the generalisation.

$S(a,b)\geq\frac{1}{2}\iff\psi(a,b)\leq 0$

##  6 Conclusion

The first two parts contain a concise summary of the usage of Shapley values
from Cooperative Game Theory for interpretable concept-based learning in the
FCA playground with its connection to Data Mining formulations. We omitted
results related to algorithms and their computational complexity since they
deserve a separate detailed treatment.

The lessons drawn from the ranking attributes in JSM classification hypotheses
and those in the intents of stable concepts show that valuation functions
should be customised and are not necessarily zero-one-valued. This is an
argument towards that of Shapley values approach requires specification
depending on the model (or type of patterns) and thus only conditionally is
model-agnostic. The other lesson is about the usage of Shapley values for
pattern attribution concerning their contribution interestingness measures
like stability or robustness.

The third part is devoted to attribute aggregation by similarity, which may
help to apply interpretable techniques to larger sets of attributes or bring
additional aspects to interpretability with the help of domain taxonomies. The
desirable property of similarity measures to provide compatible generalisation
helps to reduce the number of output concepts or JSM-hypotheses as well. The
connection between attribute similarity measures and Shapley interaction
values [46], when the interaction of two or more attributes on the model
prediction is studied, is also of interest.

In addition to algorithmic issues, we would like to mention two more
directions of future studies. The first one lies in the interpretability by
means of Boolean matrix factorisation (decomposition), which was used for
dimensionality reduction with explainable Boolean factors (formal concepts)
[5] or interpretable “taste communities” identification in collaborative
filtering [22]. In this case, we are transitioned from the importance of
attributes to attribution of factors. The second one is a closely related
aspect to interpretability called fairness [2], where, for example, certain
attributes of individuals should not influence much to the model prediction
(disability, ethnicity, gender, etc.).

#### Acknowledgements.

The study was implemented in the framework of the Basic Research Program at
the National Research University Higher School of Economics and funded by the
Russian Academic Excellence Project ’5-100’. The second author was also
supported by Russian Science Foundation under grant 17-11-01276 at St.
Petersburg Department of Steklov Mathematical Institute of Russian Academy of
Sciences, Russia. The second author would like to thank Fuad Aleskerov, Alexei
Zakharov, and Shlomo Weber for the inspirational lectures on Collective Choice
and Voting Theory.

## References

  * [1] Agrawal, R., Imielinski, T., Swami, A.N.: Mining association rules between sets of items in large databases. In: Buneman, P., Jajodia, S. (eds.) Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, May 26-28, 1993. pp. 207–216. ACM Press (1993)
  * [2] Alves, G., Bhargava, V., Couceiro, M., Napoli, A.: Making ML models fairer through explanations: the case of limeout. CoRR abs/2011.00603 (2020)
  * [3] Belohlávek, R., Baets, B.D., Konecny, J.: Granularity of attributes in formal concept analysis. Inf. Sci. 260, 149–170 (2014)
  * [4] Belohlávek, R., Baets, B.D., Outrata, J., Vychodil, V.: Inducing decision trees via concept lattices. Int. J. Gen. Syst. 38(4), 455–467 (2009)
  * [5] Belohlávek, R., Vychodil, V.: Discovery of optimal factors in binary data via a novel method of matrix decomposition. J. Comput. Syst. Sci. 76(1), 3–20 (2010)
  * [6] Bocharov, A., Gnatyshak, D., Ignatov, D.I., Mirkin, B.G., Shestakov, A.: A lattice-based consensus clustering algorithm. In: Huchard, M., Kuznetsov, S.O. (eds.) Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications, Moscow, Russia, July 18-22, 2016. CEUR Workshop Proceedings, vol. 1624, pp. 45–56. CEUR-WS.org (2016)
  * [7] Carpineto, C., Romano, G.: A lattice conceptual clustering system and its application to browsing retrieval. Mach. Learn. 24(2), 95–122 (1996)
  * [8] Caruana, R., Lundberg, S., Ribeiro, M.T., Nori, H., Jenkins, S.: Intelligible and explainable machine learning: Best practices and practical challenges. In: Gupta, R., Liu, Y., Tang, J., Prakash, B.A. (eds.) KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020. pp. 3511–3512. ACM (2020)
  * [9] Eklund, P.W., Ducrou, J., Dau, F.: Concept similarity and related categories in information retrieval using Formal Concept Analysis. Int. J. Gen. Syst. 41(8), 826–846 (2012)
  * [10] Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P.: From data mining to knowledge discovery in databases. AI Magazine 17(3), 37–54 (1996)
  * [11] Finn, V.: On Machine-oriented Formalization of Plausible Reasoning in F.Bacon-J.S.Mill Style. Semiotika i Informatika (20), 35–101 (1983), (in Russian)
  * [12] Ganter, B., Kuznetsov, S.O.: Hypotheses and Version Spaces. In: de Moor, A., Lex, W., Ganter, B. (eds.) Conceptual Structures for Knowledge Creation and Communication, 11th International Conference on Conceptual Structures, ICCS 2003, Proceedings. LNCS, vol. 2746, pp. 83–95. Springer (2003)
  * [13] Ganter, B., Kuznetsov, S.O.: Scale Coarsening as Feature Selection. In: Medina, R., Obiedkov, S. (eds.) Formal Concept Analysis. pp. 217–228. Springer Berlin Heidelberg (2008)
  * [14] Ganter, B., Obiedkov, S.A.: Conceptual Exploration. Springer (2016)
  * [15] Ganter, B., Wille, R.: Formal Concept Analysis - Mathematical Foundations. Springer (1999)
  * [16] Goodfellow, I.J., Bengio, Y., Courville, A.C.: Deep Learning. Adaptive computation and machine learning, MIT Press (2016)
  * [17] Hájek, P., Havel, I., Chytil, M.: The GUHA method of automatic hypotheses determination. Computing 1(4), 293–308 (1966)
  * [18] Ignatov, D.I.: Introduction to formal concept analysis and its applications in information retrieval and related fields. In: Braslavski, P., Karpov, N., Worring, M., Volkovich, Y., Ignatov, D.I. (eds.) Information Retrieval - 8th Russian Summer School, RuSSIR 2014, Nizhniy, Novgorod, Russia, August 18-22, 2014, Revised Selected Papers. Communications in Computer and Information Science, vol. 505, pp. 42–141. Springer (2014)
  * [19] Ignatov, D.I., Kuznetsov, S.O., Poelmans, J.: Concept-Based Biclustering for Internet Advertisement. In: 12th IEEE International Conference on Data Mining Workshops, ICDM Workshops, Brussels, Belgium, December 10, 2012. pp. 123–130 (2012)
  * [20] Ignatov, D.I., Kwuida, L.: Interpretable concept-based classification with shapley values. In: Alam, M., Braun, T., Yun, B. (eds.) Ontologies and Concepts in Mind and Machine - 25th International Conference on Conceptual Structures, ICCS 2020, Bolzano, Italy, September 18-20, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12277, pp. 90–102. Springer (2020)
  * [21] Ignatov, D.I., Kwuida, L.: Shapley and banzhaf vectors of a formal concept. In: Valverde-Albacete, F.J., Trnecka, M. (eds.) Proceedings of the Fifthteenth International Conference on Concept Lattices and Their Applications, Tallinn, Estonia, June 29-July 1, 2020. CEUR Workshop Proceedings, vol. 2668, pp. 259–271. CEUR-WS.org (2020)
  * [22] Ignatov, D.I., Nenova, E., Konstantinova, N., Konstantinov, A.V.: Boolean Matrix Factorisation for Collaborative Filtering: An FCA-Based Approach. In: Agre, G., Hitzler, P., Krisnadhi, A.A., Kuznetsov, S.O. (eds.) Artificial Intelligence: Methodology, Systems, and Applications - 16th International Conference, AIMSA 2014, Varna, Bulgaria, September 11-13, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8722, pp. 47–58. Springer (2014)
  * [23] John, S.: Mill, A System of Logic, Ratiocinative and Inductive, Being a Connected View of the Principles of Evidence and the Methods of Scientific Investigation. Longmans, Green, and Co., London (1843)
  * [24] Kadyrov, T., Ignatov, D.I.: Attribution of customers’ actions based on machine learning approach. In: Proceedings of the Fifth Workshop on Experimental Economics and Machine Learning co-located with the Seventh International Conference on Applied Research in Economics (iCare7), Perm, Russia, September 26, 2019. CEUR-ws, vol. Vol-2479, pp. 77–88 (2019)
  * [25] Kashnitsky, Y., Kuznetsov, S.O.: Global Optimization in Learning with Important Data: an FCA-Based Approach. In: Huchard, M., Kuznetsov, S.O. (eds.) Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications, Moscow, Russia, July 18-22, 2016. CEUR Workshop Proceedings, vol. 1624, pp. 189–201. CEUR-WS.org (2016)
  * [26] Kaur, H., Nori, H., Jenkins, S., Caruana, R., Wallach, H.M., Vaughan, J.W.: Interpreting interpretability: Understanding data scientists’ use of interpretability tools for machine learning. In: Bernhaupt, R., Mueller, F.F., Verweij, D., Andres, J., McGrenere, J., Cockburn, A., Avellino, I., Goguey, A., Bjøn, P., Zhao, S., Samson, B.P., Kocielnik, R. (eds.) CHI ’20: CHI Conference on Human Factors in Computing Systems, Honolulu, HI, USA, April 25-30, 2020. pp. 1–14. ACM (2020)
  * [27] Kaytoue, M., Kuznetsov, S.O., Macko, J., Napoli, A.: Biclustering meets triadic concept analysis. Ann. Math. Artif. Intell. 70(1-2), 55–79 (2014)
  * [28] Konecny, J.: On attribute reduction in concept lattices: Methods based on discernibility matrix are outperformed by basic clarification and reduction. Inf. Sci. 415, 199–212 (2017)
  * [29] Konecny, J., Krajca, P.: On attribute reduction in concept lattices: Experimental evaluation shows discernibility matrix based methods inefficient. Inf. Sci. 467, 431–445 (2018)
  * [30] Kuitché, R.S., Temgoua, R.E.A., Kwuida, L.: A similarity measure to generalize attributes. In: Ignatov, D.I., Nourine, L. (eds.) Proceedings of the Fourteenth International Conference on Concept Lattices and Their Applications, CLA 2018, Olomouc, Czech Republic, June 12-14, 2018. CEUR Workshop Proceedings, vol. 2123, pp. 141–152. CEUR-WS.org (2018)
  * [31] Kuznetsov, S.O.: Machine Learning and Formal Concept Analysis. In: ICFCA 2004\. pp. 287–312 (2004)
  * [32] Kuznetsov, S.O.: Galois Connections in Data Analysis: Contributions from the Soviet Era and Modern Russian Research. In: Ganter, B., Stumme, G., Wille, R. (eds.) Formal Concept Analysis, Foundations and Applications. LNCS, vol. 3626, pp. 196–225. Springer (2005)
  * [33] Kuznetsov, S.O.: On stability of a formal concept. Ann. Math. Artif. Intell. 49(1-4), 101–115 (2007)
  * [34] Kuznetsov, S.O., Makhalova, T.P.: On interestingness measures of formal concepts. Inf. Sci. 442-443, 202–219 (2018)
  * [35] Kuznetsov, S.O., Makhazhanov, N., Ushakov, M.: On neural network architecture based on concept lattices. In: Kryszkiewicz, M., Appice, A., Slezak, D., Rybinski, H., Skowron, A., Ras, Z.W. (eds.) Foundations of Intelligent Systems. pp. 653–663. Springer International Publishing, Cham (2017)
  * [36] Kuznetsov, S.O., Poelmans, J.: Knowledge representation and processing with formal concept analysis. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 3(3), 200–215 (2013)
  * [37] Kuznetsov, S.: Jsm-method as a machine learning method. Method. Itogi Nauki i Tekhniki, ser. Informatika (15), 17–53 (1991), (in Russian)
  * [38] Kuznetsov, S.: Stability as an estimate of the degree of substantiation of hypotheses derived on the basis of operational similarity. Nauchn. Tekh. Inf. Ser. 2 (12), 217–29 (1991), (in Russian)
  * [39] Kuznetsov, S.: Mathematical aspects of concept analysis. Journal of Mathematical Science 80(2), 1654–1698 (1996)
  * [40] Kwuida, L., Kuitché, R., Temgoua, R.: On the size of $\exists$-generalized concepts. ArXiv:1709.08060 (2017)
  * [41] Kwuida, L., Kuitché, R.S., Temgoua, R.E.A.: On the size of $\exists$-generalized concept lattices. Discret. Appl. Math. 273, 205–216 (2020)
  * [42] Kwuida, L., Missaoui, R., Balamane, A., Vaillancourt, J.: Generalized pattern extraction from concept lattices. Ann. Math. Artif. Intell. 72(1-2), 151–168 (2014)
  * [43] Kwuida, L., Missaoui, R., Boumedjout, L., Vaillancourt, J.: Mining generalized patterns from large databases using ontologies. ArXiv:0905.4713 (2009)
  * [44] Kwuida, L., Missaoui, R., Vaillancourt, J.: Using taxonomies on objects and attributes to discover generalized patterns. In: Szathmary, L., Priss, U. (eds.) Proceedings of The Ninth International Conference on Concept Lattices and Their Applications, Fuengirola (Málaga), Spain, October 11-14, 2012\. CEUR Workshop Proceedings, vol. 972, pp. 327–338. CEUR-WS.org (2012)
  * [45] Lakhal, L., Stumme, G.: Efficient mining of association rules based on formal concept analysis. In: Ganter, B., Stumme, G., Wille, R. (eds.) Formal Concept Analysis, Foundations and Applications. Lecture Notes in Computer Science, vol. 3626, pp. 180–195. Springer (2005)
  * [46] Lundberg, S.M., Lee, S.I.: A Unified Approach to Interpreting Model Predictions. In: et al., I.G. (ed.) Advances in Neural Information Processing Systems 30, pp. 4765–4774. Curran Associates, Inc. (2017)
  * [47] Luxenburger, M.: Implications partielles dans un contexte. Mathématiques et Sciences Humaines 113, 35–55 (1991)
  * [48] Mirkin, B.: Mathematical Classification and Clustering. Kluwer Academic Publishers (1996)
  * [49] Mitchell, T.M.: Version Spaces: A Candidate Elimination Approach to Rule Learning. In: Reddy, R. (ed.) Proceedings of the 5th International Joint Conference on Artificial Intelligence. 1977. pp. 305–310. William Kaufmann (1977)
  * [50] Molnar, C.: Interpretable Machine Learning (2019), https://christophm.github.io/interpretable-ml-book/
  * [51] Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Efficient mining of association rules using closed itemset lattices. Information Systems 24(1), 25–46 (1999)
  * [52] Poelmans, J., Ignatov, D.I., Kuznetsov, S.O., Dedene, G.: Formal concept analysis in knowledge processing: A survey on applications. Expert Syst. Appl. 40(16), 6538–6560 (2013)
  * [53] Poelmans, J., Kuznetsov, S.O., Ignatov, D.I., Dedene, G.: Formal concept analysis in knowledge processing: A survey on models and techniques. Expert Syst. Appl. 40(16), 6601–6623 (2013)
  * [54] Prediger, S.: Formal concept analysis for general objects. Discret. Appl. Math. 127(2), 337–355 (2003)
  * [55] Priss, U., Old, L.J.: Data weeding techniques applied to roget’s thesaurus. In: Wolff, K.E., Palchunov, D.E., Zagoruiko, N.G., Andelfinger, U. (eds.) Knowledge Processing and Data Analysis. pp. 150–163. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)
  * [56] Roth, C., Obiedkov, S.A., Kourie, D.G.: Towards concise representation for taxonomies of epistemic communities. In: Yahia, S.B., Nguifo, E.M., Belohlávek, R. (eds.) Concept Lattices and Their Applications, Fourth International Conference, CLA 2006, Tunis, Tunisia, October 30 - November 1, 2006, Selected Papers. LNCS, vol. 4923, pp. 240–255. Springer (2006)
  * [57] Rudin, C.: Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence 1(5), 206–215 (2019)
  * [58] Rudolph, S.: Using FCA for encoding closure operators into neural networks. In: Priss, U., Polovina, S., Hill, R. (eds.) Conceptual Structures: Knowledge Architectures for Smart Applications, 15th International Conference on Conceptual Structures, ICCS 2007, Sheffield, UK, July 22-27, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4604, pp. 321–332. Springer (2007)
  * [59] Shapley, L.S.: A value for n-person games. Contributions to the Theory of Games 2(28), 307–317 (1953)
  * [60] Shrikumar, A., Greenside, P., Kundaje, A.: Learning important features through propagating activation differences. In: Precup, D., Teh, Y.W. (eds.) Proceedings of the 34th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 70, pp. 3145–3153. PMLR, International Convention Centre, Sydney, Australia (06–11 Aug 2017)
  * [61] Srikant, R., Agrawal, R.: Mining generalized association rules. In: Dayal, U., Gray, P.M.D., Nishio, S. (eds.) VLDB’95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. pp. 407–419. Morgan Kaufmann (1995)
  * [62] Srikant, R., Agrawal, R.: Mining generalized association rules. Future Gener. Comput. Syst. 13(2-3), 161–180 (1997)
  * [63] Strumbelj, E., Kononenko, I.: Explaining prediction models and individual predictions with feature contributions. Knowl. Inf. Syst. 41(3), 647–665 (2014)
  * [64] Stumme, G., Taouil, R., Bastide, Y., Lakhal, L.: Conceptual clustering with iceberg concept lattices. Proc. of GI-Fachgruppentreffen Maschinelles Lernen 1 (2001)
  * [65] Tatti, N., Moerchen, F.: Finding robust itemsets under subsampling. In: ICDM 2011\. pp. 705–714 (2011)
  * [66] Valtchev, P., Missaoui, R.: Similarity-based Clustering versus Galois lattice building: Strengths and Weaknesses. In: Huchard, M., Godin, R., Napoli, A. (eds.) Contributions of the ECOOP’00 Workshop, “Objects and Classification: a Natural Convergence”, European Conference on Object-Oriented Programming (2000). vol. Research Report LIRMM n.00095, p. w13 (2000)