Shapley and Banzhaf Vectors of a Formal Concept

Abstract

We propose the usage of two power indices from cooperative game theory and public choice theory for ranking attributes of closed sets, namely intents of formal concepts (or closed itemsets). The introduced indices are related to extensional concept stability and based on counting generators, especially those that contain a selected attribute. The introduction of such indices is motivated by the so-called interpretable machine learning, which supposes that we do not only have the class membership decision of a trained model for a particular object, but also a set of attributes (in the form of JSM-hypotheses or other patterns) along with individual importance of their single attributes (or more complex constituent elements). We characterise computation of Shapley and Banzhaf values of a formal concept in terms of minimal generators and their order filters, provide the reader with their properties important for computation purposes, and show experimental results.

Keywords

• Shapley value
• Banzhaf value
• Interpretable Machine Learning
• formal concepts
• closed itemsets

-

Concept stability indices were introduced to assess robustness of JSM-hypotheses in [ 13 ] under deletion of subsets of objects. JSM-method is known as a logical rule-based classification method named after John Stuart Mill [ 5 ], which had was later formulated in terms of Formal Concept Analysis (FCA) [ 14 ]. In FCA terms, each JSM-rule is an implication of the form “concept intent”→ “target attribute”, where the target attribute corresponds to a predicted class4.

Concept stability indices allow to rank those intents (or hypotheses) by their robustness under objects deletion and provide the evidence of their non-random nature similarly to bootstrap estimation [ 15 ] and swap-permutations [ 7 ]. Later on, the notion of stability was rediscovered under the name of robustness of 4 Usually, each left-hand side includes only a minimal intent with minsup = 2 that is not included in the intents of examples of other classes. closed itemsets [ 23 ]. On the one hand the authors of the robustness of itemsets considered a more general case, namely, they covered itemsets, closed itemsets (concept intents), and free itemsets (intent generators), but on the other hand they even assumed Bernoullian character of object deletion with a fixed probability α. In [ 11 ], by means of M¨obius function, it is shown that robustness and stability are analytically equivalent for α = 0.5.

However, JSM-hypotheses are not atomic patterns, and even if we know that a certain hypothesis is stable, we cannot judge the importance of each attribute for making the hypothesis stable. To fill the gap, we addressed the Shapley value importance of attributes from Interpretable Machine Learning (IML) [ 19 ]. The Shapley value, a notion from Collaborative Game Theory [ 21 ], is used to provide a fair payoff to players, which are actually the attributes of an object under classification in our case. By means of the payoff value we can rank the attributes and judge what the contribution or importance of each attribute is for the classification of this object to the predicted class. Being model-agnostic, however this technique assumes a probabilistic output p(class|object) of a classifier and each attribute’s payoff is computed as conditional expectation of a related value function over all the subsets of attributes with and without a selected attribute.

Here, we assume that attributes are players of the game where the (extent) stability of a concept is shared between them using the classic Shapley value formula. It has several important properties: efficiency, symmetry, linearity, null or dummy player. For example, efficiency means the sum of the Shapley values of all players equals the value of their coalition, so that the total payoff is distributed among the agents. Another variants of power (importance) indices from Coalition Game Theory are possible, for example, the Banzhaf index [ 2 ], though without fulfilling all the mentioned properties.

In this paper, we would like to explain how the Shapley values of individual attributes in a formal concept intent can be computed by means of a Boolean valuation function related to extent stability of the considered formal concept. Moreover, we would like to characterise the Shapley vector of a formal concept in order-theoretic terms and find its relationship with stability indices.

The paper is organised as follows. In Section 2, related work on interpretable machine learning and Shapley values from Game Theory is summarised. Section 3 recalls basics of FCA and concept stability indices. Section 4 illustrates how to use Shapley values to estimate the importance of separate attributes related to stability indices, and introduces the weak Banzhaf index. Section 5 is devoted to machine experiments with model and real machine learning data. 2 2.1

Shapley value in IML and FCA communities

Interpretable Machine Learning In early 90’s, the discipline of Data Mining emerged as a step of Knowledge Discovery in Databases (KDD) process, which was defined as follows: “KDD is the nontrivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data” [ 4 ]. Recently, machine learning researchers realised the necessity of interpretation for a wide variety of black-box models and even for ensemble rule-based methods when many attributes are involved [ 16 ]5.

The author of a book [ 19 ] on interpretable machine learning notes that there is no mathematical definition of interpretability. In [ 8 ] interpretability is understood as “the degree to which a human can consistently predict the model’s results”. Thus, machine learning models can be ranked according to their interpretability: “A model is better interpretable than another model if its decisions are easier for a human to comprehend than decisions from the other model” [ 19 ].

Among the family of approaches, [ 19 ] poses global vs. local interpretations. Thus, the global interpretability “is about understanding how the model makes decisions, based on a holistic view of its features and each of the learned components such as weights, other parameters, and structures”, while the local interpretability is focused on “a single instance and examine what the model predicts for this input, and explain why” [ 19 ]. From this point of view, JSM-rules provides local interpretations when we deal with a particular classification example.

The Shapley value attribution is a model-agnostic method and produces ranking of individual attributes by their importance for classification of a particular example, i.e. it provides a decision maker with local interpretations. Indeed, this attribution methodology is equivalent to the Shapely value solution to value distribution in Cooperative Game Theory [ 21 ]. Strumbelj and Kononenko [ 22 ] consistently show that the Shapley value is the only solution for the problem of single attribute importance (or attribution problem) measured via the difference between model’s prediction with and without this particular attribute across all possible subsets of attributes.

Lundberg and Lee [ 17 ] extend this approach further under the name SHAP (Shapley Additive explanation) values [ 17 ]. To compute SHAP value for an example x and an attribute m the authors define fx(S), the expected value of the model prediction conditioned on a subset S of the input attributes, which can be approximated by integrating over samples from the training dataset.

SHAP values combine these conditional expectations with the classic Shapley values from game theory to assign φm value to each attribute: φm =

X S⊆M\{m} |S|!(|M | − |S| − 1)! |M |! (fx(S ∪ {m}) − fx(S)) , (1) where M is the set of all input attributes, S is a certain coalition of players, i.e. subset of attributes S ⊆ M .

In our study, we will follow classical definition of the Shapley value [ 21 ], where a monotone Boolean function is used instead of expected value fx(S). Thus, we evaluate the contribution of each attribute with respect to extent stability rather than find its importance for a certain example classified by JSM-hypotheses. 5 The workshops on Interpretable Machine Learning: https://sites.google.com/ view/whi2018 and https://sites.google.com/view/hill2019

Shapley value in FCA community In [ 3 ], the authors introduced cooperative games on concept lattices. Any game of this type induces a game on the set of objects, and a game on the set of attributes. In these games the notion of Shapley value naturally arises as a rational solution for distributing the total worth of the cooperation among the players. The authors of [ 18 ] studied algorithms to compute the Shapley value for a cooperative game on a lattice of closed sets given by an implicational system; the main computational advantage of the proposed algorithms is based on maximal chains and product of chains of fixed length. 3

FCA basics and concept stability indices Let K := (G, M, I) be a formal context; that is a triple of sets such that I ⊆ G × M . We call G the set of objects and M the set of attributes. For A ⊆ G and B ⊆ M , we define the derivation operation by:

A0 := {m ∈ M | ∀a ∈ A : (a, m) ∈ I} and B0 := {g ∈ G | ∀b ∈ B : (g, b) ∈ I}. A pair (A, B) is called a formal concept of K if A0 = B and B0 = A. In that case, A is called the extent and B the intent of the concept (A, B). Let (A, B) be a formal concept of K with | | = l, and |B| = n. To define the stability indices as

A in [ 13,10,20,12 ], we first recall the notion of generator.

Definition 1. A generator of the concept intent B is any Y ⊆ B such that Y 00 = B. A set X ⊆ B is a minimal generator of B iff X00 = B and no proper subset of X is a generator of B. The sets of all generators (resp. all minimal generators) of B will be denoted by gen(B) (resp. mingen(B)).

Definition 2. In [ 10 ], the stability index Jk(A, B) (or simply Jk(B)) of the k-th level is defined as follows:

Extensional and intensional stability indices σi(A, B) and σe(A, B) were introduced in [ 20,12 ], as variations of integral stability from [ 10 ]. Here the proportions are taken over all subsets, instead of subsets of size k.

Definition 3. The intensional stability index of a concept (A, B) is defined by: σi(A, B) := |{Z ⊆ A such2lthat Z0 = B}| = |{Z ⊆ A 2|lZ00 = A}| = |gen2(lA)| . Similarly the extensional stability index of a concept (A, B) is defined by: σe(A, B) := |{Y ⊆ B such2nthat Y 0 = A}| = |{Y ⊆ B 2| nY 00 = B}| = |gen2(nB)| .

We call Jk(C) the intensional stability index of the k-th level, while the extensional stability index of the k-th level is defined similarly.

Definition 4. The extensional stability index of the k-th level: n Jk(A) = |{Y ⊆ B | |Y | = k, Y 0 = A}|/ k . 4

Shapley values for attribute importance in terms of concept stability indices Let us consider the extent stability index σe(A, B) as in Definition 3. Its numerator induces a monotone Boolean function vB : 2B → {0, 1}, which may play a role of the value function of any Y ⊆ B considered as a coalition of players, i.e. attributes in our case: v(Y ) = (1, if Y 0 = A and Y 6= ∅ .

0, otherwise We will omit B as a lower index of v if it does not result in notation collisions. Note that σe(A, B) = P v(Y ) + [∅0 = B] /2|B|, where [P ] is the Iverson

Y ⊆B notation for the value of a predicate P 6.

Definition 5. The Shapley value of m ∈ B for a concept (A, B) is defined by:

The vector of Shapley values for all the attributes from B is called the (reduced) Shapley vector of (A, B), and its extension to all attributes (ϕm(A, B) = 0 for m ∈/ B) is called the extended Shapley vector of (A, B).

Since minimal generators are important coalitions and the function v(·) is inspired by the stability indices, we would like to study their interconnection. The Shapley values of attributes in case of extent stability can be expressed with the help of only minimal generators.

Theorem 1. Let m ∈ Xm ∈ mingen(B) and m ∈/ Xm ∈ mingen(B).7 Then 6 [P ] = 1 if P is true and [P ] = 0 otherwise 7 t is disjoint union, Xm and Xm are minimal generators of B with and without m, respectively. v(D ∪ {m}) v(D) v(D ∪ {m}) − v(D) 0 0 0 1 0 1 1 1 0 1. When D and D ∪ {m} are not generators of B, we have the first case (first row of the table); they do not contribute to ϕm(A, B). In this case those sets are generators of less general concepts with intents included in B. 2. When D ∈/ gen(B) and D ∪ {m} ∈ gen(B) hold, then we have second case. By definition each generator of B is in an interval formed by a minimal generator and B, i.e. X↑ = [X, B], where X ∈ mingen(B). We are interested in all S t {m} ∈ gen(B) such that S ∈/ gen(B). If S ∈/ gen(B), then (S0, S00) > (A, B). Since all D ∈ [S, S00] are not generators of B, then v(D) = 0. On the other hand, S t {m} ⊆ D t {m}, then D t {m} ∈ gen(B) and v(D t {m}) = 1.

If S t {m} ∈ Xm↑, then Xm ⊆ S and v(S) = 1. Thus we need not to consider all S t {m} from S Xm ↑, the set of order ideals of minimal generators not containing m.

(a) (b) 3. In the last case D and D ∪ {m} are both generators of B and thus do not contribute to ϕm(A, B).

Summing it up, the only contributors are generators of B in the form D∪{m} with v(D ∪ {m}) = 1 and v(D) = 0, which finishes the proof. Corollary 1. For m ∈ Xm ∈ mingen(B), Y ⊆ B \ {m} with (Y 0, Y ) ≥ (A, B) and there is no Z ⊆ B \ {m} such that (Y 0, Y ) > (Z0, Z) > (A, B) we have Proof. By Theorem 1, since each minimal satisfying set (in terms of set inclusion) is S t {m} = Xm ∈ mingen(B), then all candidates D ⊇ S for the summation over them lie in the intervals [Xm \ {m}, B \ {m}]. However, Theorem 1 implies that we also need to eliminate each D in the upper set of a minimal generator without m, D ∈ Xm ↑, since v(D) = 1. Thus, we need to consider all maximal sets Y ⊆ B \ {m} that are not minimal generators of B, i.e. each largest intent of more general concepts for (A, B) that do not contain m fulfils the requirement. Theorem 2. Let (A, B) be a concept and m ∈ M , then ϕm(A, B) = X|B| Jk(A)

k k=1

1

X −

D⊆B\{m} |D| |B| D|−|1 v(D) .

Proof. Let us consider an alternative representation of Shapley value formula as in the original paper [ 21 ]. We set s = |S| and get ϕm(A, B) = X

(v(S) − v(S \ m)) 1 k

1 |B| = X

S⊆B |S| ||BS|| k=1 k |Bk | |SS⊆|=Bk: = X|B| Jk(A) k=1 −

X

S⊆B\{m} X v(S) −

S⊆B X (s − 1)!(n − s)! n!

v(S \ {m}) (s − 1)!(n − s)! n!

s!(n − s − 1)! + n! v(S).

The identity (s−1)!(n−s)! + s!(n−s−1)! = (s−1)!(n−s−1)! finishes the proof.

n! n! (n−1)! Corollary 2. If {m} ⊆ X ∈ mingen(B) and |mingen(B)| = 1, then ϕm(A, B) = X|B| Jk(A) =

k k=1 1 |X| .

Another important power index from Choice Theory and Cooperative Game Theory is the so-called Banzhaf power index, which shows how many coalitions that contain a given player are winning, while the same coalitions without that player are not [ 2 ]. It is also known that the Banzhaf index is well-correlated with Shapley vector [ 1 ]. So, for comparison purposes, let us introduce the weak Banzhaf index of a formal concept where we count all the winning coalitions with the considered player. (2) (3) Definition 6. The weak Banzhaf index of an attribute m ∈ B for the concept (A, B) is defined as follows:

P

vB(D ∪ {m}) βm(A, B) = D⊆B\{m2}|B\{m}| = |{D ⊆ B \ {m}|(D ∪ m)0 = A}| .

2|B\{m}|

One may note that the weak Banzhaf index of a formal concept is very similar to the extent stability index of a formal concept. In fact, we eliminate contributions of subsets not containing the attribute m from both the numerator and the denominator of the extent stability index and use its computational advantage in our experiments. 5

Machine Experiments

All the experiments in this section have been performed in the interactive environment by means of iPython notebook8. To illustrate the differences between the Shapley index and the weak Banzhaf index, we use three contexts of size 3 × 3 for known elementary scales [ 6 ] (Fig. 2) and a positive context describing fruits with binary or scaled attributes from [ 9 ] (Fig. 3).

a b c 1 × × × 2 × × 3 ×

a b c Here, the only non-zero components of the Shapley vectors are given to the attributes that are not contained in the intents of less general concepts, while in the weak Banzhaf indices they have the largest values among other non-zero components. 8 The iPython script with a related demo can found at https://github.com/ dimachine/ShapStab/ For the context of nominal scale, the Shapley and weak Banzhaf vectors are equal for all concepts except the top one. As expected, if the intent of a concept of nominal scale consists only of a single attribute, it takes 1 as its importance value. For the top concept, all the values are equally distributed among the attributes, but differ from the values of their counterpart of another index. For the context of the contranominal scale, the Shapley and weak Banzhaf vectors are equal except ones for the top concept. If an intent has only one attribute, it takes 1 as its importance value, while it has 0.5 if the intent has exactly two attributes. The values of attributes for the top concept are equally distributed, but the weak Banzhaf index has lower values than those for the top concept of the considered nominal scale since it has only one generator, which coincides with the intent.

As we can see from examples of concepts with fruits like ({1, 4}, {f¯, s}) or ({2, 3}, {f¯, s¯}), attributes that are not contained in minimal generators do not contribute to the Shapley vectors, while their counterparts for weak Banzhaf values do (cf. the importance values of f¯).

To experiment with real data, we selected the Zoo dataset (101 examples (animals) and 17 attributes excluding its target attribute) from UCI Machine

Fruits 1 apple 2 grapefruit 3 kiwi 4 plum w y g b f f¯ s s¯ r r¯ × × × × × × × × × ×

× × × × × × r¯ g g3 s¯ b g4 ({4}, {b, f¯, s, r¯}) ({3}, {g, f¯, s¯, r¯}) ({3, 4}, {f¯, r¯}) ({2}, {y, f¯, s¯, r}) ({2, 3}, {f¯, s¯}) ({1}, {y, f¯, s, r}) ({1, 4}, {f¯, s}) ({1, 2}, {y, f¯, r}) ({1, 2, 3, 4}, {f¯}) Learning Repository9. All the attributes are binary except of a single numerical one, the number of legs, which can be treated as categorical and scaled nominally.

This context has 357 concepts in total. We consider the top-3 most stable concepts: c1, c2, c3 along with their extent Stability indices: σe(G, ∅) = 1, σe(∅, M ) = 0.997, σe(A, {1, 2, 8, 9, 14, 18}) = 0.625 respectively, where A = {11, 16, 20, 21, 23, 33, 37, 41, 43, 56, 57, 58, 59, 71, 78, 79, 83, 87, 95, 100} .

For the top concept, c1, with empty intent we have zero importance vectors. The attribute names are hair, feathers, eggs, milk, airborne, aquatic, predator, toothed, backbone, breathes, venomous, fins, legs (4), legs (0), legs (2), legs (6), legs (8), legs (5), tail, domestic, and catsize. So, for concept c2 we can note that 9 https://archive.ics.uci.edu/ml/datasets/zoo components of the weak Banzhaf vector are nearly ones, while the five largest components of Shapley vector are legs (6), legs (8), legs (5), feathers, and legs (4) (see, Fig. 4). This is the bottom concept with empty extent.

The concepts with empty intent or extent are not very interesting in terms of food for interpretation since they do not describe a discernible class of objects, while concept c3 looks more attractive with that respect. Even though we have ignored the target attribute with seven classes in the input context, the intent of c3 describes the class of birds since it consists of the following attributes: feathers, eggs, backbone, breathes, eggs, legs(2) and tail. Among the objects in its intent are chicken, crow, dove, etc. The most important attributes are feathers, eggs and two legs, according to the Shapley vector. They are also the most important ones according to the weak Banzhaf index though it has three remaining attributes with rather high importance values contrary to the Shapley vector.

Conclusion

We have introduced the Shapley value and the weak Banzhaf index of a formal concept (or concept intent, more precisely) to rank the attributes of formal concepts based on the associated monotonic Boolean function showing whether a particular set of attributes is a generator of a given concept intent. A similar function is used for the stability indices of formal concepts or JSM-hypotheses [ 10 ].

This ranking allows us to order attributes by their importance; in case of the Shapley value, the induced ranking reflects (up to the scaling binomial coefficient) how many times a particular attribute was in a generator of a given concept, while this generator minus the attribute is not a generator of the concept. As we can see from the examples with both toy and real data, these importance values are different from their counterparts in the weak Banzhaf vectors. Thus, they are zeros for all attributes that are not among the attributes of minimal generators.

As we could see from the concept or hypothesis for the bird class in the Zoo dataset, the Shapley value can be used for interpretation purposes selecting the most important attributes of a given hypothesis.

In our further studies we would like to pay special attention to scalability algorithmic issues of this approach (related to reduced contexts) as well as to its comparison with other importance indices [ 1 ] from Cooperative Game Theory and Collective Choice with a focus on their interpretability properties for real applications. The detailed discussion on the algorithmic complexity of the related problems will appear in an extended paper version.

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 first 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 first author would like to thank Prof. Fuad Aleskerov for the inspirational lectures on Collective Choice.

References

1. Aleskerov , F.T. , Habina , E.L. , Swartz , D.A. : Binary Relations, Graphs, and Collective Decisions . Fizmatlit ( 2012 )

2. Banzhaf , J.C. : Weighted voting doesn't work: a mathematical analysis . Rutgers Law Review 19 , 317 - 343 ( 1965 )

3. Faigle , U. , Grabisch , M. , Jim´enez- Losada , A. , Ordo´n˜ez, M.: Games on concept lattices: Shapley value and core . Discrete Applied Mathematics 198 , 29 - 47 ( 2016 )

4. Fayyad , U.M. , Piatetsky-Shapiro , G. , Smyth , P. : From Data Mining to Knowledge Discovery in Databases . AI Magazine 17 ( 3 ), 37 - 54 ( 1996 )

5. Finn , V.: On Machine-oriented Formalization of Plausible Reasoning in F . BaconJ.S.Mill Style. Semiotika i Informatika (20) , 35 - 101 ( 1983 ), (in Russian)

6. Ganter , B. , Wille , R.: Formal Concept Analysis - Mathematical Foundations . Springer ( 1999 )

7. Gionis , A. , Mannila , H. , Mielika¨inen, T., Tsaparas , P. : Assessing data mining results via swap randomization . ACM Transactions on KDD 1 ( 3 ), 14 ( 2007 )

8. Kim , B. , Koyejo , O. , Khanna , R.: Examples are not enough, learn to criticize! Criticism for Interpretability . In: NIPS 2016 . pp. 2280 - 2288 ( 2016 )

9. Kuznetsov , S.O. : Machine Learning and Formal Concept Analysis . In: ICFCA 2004 . pp. 287 - 312 ( 2004 )

10. Kuznetsov , S.O. : On stability of a formal concept . Ann. Math. Artif. Intell . 49 ( 1-4 ), 101 - 115 ( 2007 )

11. Kuznetsov , S.O. , Makhalova , T.P. : On interestingness measures of formal concepts . Inf. Sci . 442 - 443 , 202 - 219 ( 2018 )

12. Kuznetsov , S.O. , Obiedkov , S.A. , Roth , C. : Reducing the representation complexity of lattice-based taxonomies . In: ICCS 2007 . pp. 241 - 254 ( 2007 )

13. 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)

14. Kuznetsov , S. : Mathematical aspects of concept analysis . Journal of Mathematical Science 80 ( 2 ), 1654 - 1698 ( 1996 )

15. Lallich , S. , Teytaud , O. , Prudhomme , E.: Association Rule Interestingness: Measure and Statistical Validation, pp. 251 - 275 . Springer Berlin Heidelberg ( 2007 )

16. Lipton , Z.C. : The mythos of model interpretability . Commun. ACM 61 ( 10 ), 36 - 43 ( Sep 2018 )

17. Lundberg , S.M. , Lee , S.: A unified approach to interpreting model predictions . In: NIPS 2017 . pp. 4765 - 4774 ( 2017 )

18. Maafa , K. , Nourine , L. , Radjef , M.S. : Algorithms for computing the Shapley value of cooperative games on lattices . Discr. Appl . Math. 249 , 91 - 105 ( 2018 )

19. Molnar , C.: Interpretable Machine Learning ( 2019 ), https://christophm.github. io/interpretable-ml-book/

20. Roth , C. , Obiedkov , S.A. , Kourie , D.G. : Towards concise representation for taxonomies of epistemic communities . In: CLA 2006 . pp. 240 - 255 ( 2006 )

21. Shapley , L.S.: A value for n-person games . Contributions to the Theory of Games 2 ( 28 ), 307 - 317 ( 1953 )

22. Strumbelj , E., Kononenko, I.: Explaining prediction models and individual predictions with feature contributions . Knowl. Inf. Syst . 41 ( 3 ), 647 - 665 ( 2014 )

23. Tatti , N. , Moerchen , F. : Finding robust itemsets under subsampling . In: ICDM 2011 . pp. 705 - 714 ( 2011 )