, high-level concepts that are easily comprehensible to human beings. The use of such concepts constitutes a subfield of interpretability methods known as concept-based explanations. This work uses concept-based explanations to build an intrinsically interpretable document classifier using a combination of Formal Concept Analysis (FCA) and approaches from applied graph theory. FCA is used to formalize the vague notion of concepts in terms of the formal concepts found in the concept lattices of various document classes. The graph of the lattice covering relation helps to utilize the topological information present in the document-class concept lattices for classifying documents. Finally, the formal concepts that made the strongest contributions to the predictions of the document classifier are revealed, along with their intents; thereby making their contribution more comprehensible to human beings.
With respect to the field of XAI, this work can be further categorized as belonging to the subifeld of concept-based explanations. The fundamental principle of concept-based explanations is that the explanations regarding the predictions of a DNN are best comprehended if they are framed in terms of abstract, high-level concepts. This principle is akin to the process of human reasoning, whereby concepts are informally related to groupings of examples according to the similarity of their descriptions.
Earlier works concerning concept-based explanations can be categorized as post hoc interpretability methods, meaning that they explain the predictions of a DNN after it has finished training. However, more recent concept-based explanation methods belong to the category of intrinsic interpretability methods, wherein a DNN is interpretable because of its design and not due to any post training steps.
The main reason of preferring intrinsic interpretability methods to post hoc interpretability
methods is that interpretability is neither an inevitable result of the discriminative power of a
DNN, nor a prerequisite for it as demonstrated in [
This work aims to prove that Formal Concept Analysis (FCA) can be an efective method to discover the concepts that the intrinsically interpretable document classifier should learn so as to be able to explain its predictions. This is achieved by mapping the ambiguous idea of a concept to the mathematically defined notion of a formal concept, thereby allowing the creation of a conceptual hierarchy that is expressed via a concept lattice.
The intrinsically interpretable document classifier cannot directly utilize the hierarchical order information present in the concept lattices of document classes for its training, which necessitates the mapping of the formal concepts in a concept lattice to a graph topological space. The formal concepts of the concept lattices of each class of documents are treated as vertices of a directed, acyclic graph whose components are the concept lattices themselves. The vertices of the graph correspond to diferent formal concepts that belong to various classes, with the edges between vertices denoting the subconcept/superconcept relation. A binary classifier that is trained to detect the presence of edges among the formal concept vertices of document-class concept lattices, can be used to classify a test document by predicting if/where potential edges connect the test document vertex to the formal concept vertices found within the document-class concept lattices.
Finally, the formal concepts that have contributed the most toward the classification of a test document as belonging to a particular document class are determined by the number of edges that are predicted to connect between them and the test documents. The intents of such formal concepts reveal attributes that are more comprehensible to human beings.
The final aim of this work is to create a document classifier that is both highly interpretable
and possesses relatively high classification performance. Such a model seeks to overcome
the trade-of between model interpretability and performance, which asserts that predictive
performance of an ML model is usually sacrificed for interpretability and vice versa; as stated
in [
The idea of concept-based explanations was first introduced in the seminal work of [
The original work while revolutionary for introducing the notion of concept-based
explanations, still has some flaws. It could not inherently point toward important concepts, but could
only respond to queries from the user about the significance of concepts, that must be supplied
by the user themselves. The awareness and availability of well-defined concepts also afects the
performance of the TCAV method, as deficiencies in either area lead to the possibility of there
being a possibly infinite space of concepts from which to query. These flaws were addressed in
the work of [
Since it is dificult to exactly define a concept, the work of [
Both of the previously mentioned concept-based explanation methods can be classified as post
hoc interpretability methods. For reasons mentioned in Section 1, more recent concept-based
explanation methods tend to belong to the class of intrinsic interpretability methods. One
noteworthy example of such a concept-based explanation method is the work of [
The work of [
ii the ℎ dimension of the latent representation z aligns with concept
An example of using FCA for interpreting a DNN is the work of [
FCA is a branch of applied lattice theory that deals with deriving a concept hierarchy from a collection of objects and their attributes. The scope of the applicability of FCA to the coinciding attributes of the complete concepts extracted from ML models trained on tabular, text or sequential data can be best understood by first formally defining what a formal context, formal concept and a concept lattice are.
Definition 3.1 : A formal context K := (, , ) consists of two sets and and a relation between and . The elements of are called the objects and the elements of are called the attributes of the context. An object that is in a relation with an attribute is written as .
Definition 3.2 : For a set ⊆ of objects, the derivation operator is defined as ′ := { ∈ | for all ∈ } (the set of attributes common to the objects in ). Correspondingly, for a set of attributes, the derivation operator is defined as
′ := { ∈ | for all ∈ }
Definition 3.3 : A formal concept of the context (, , ) is a pair (, ) with ⊆ , ⊆ , ′ = and ′ = . is called the extent and is called the intent of the concept (, ). B(, , ) denotes the set of all concepts of the context (, , ).
Definition 3.4 : If (1, 1) and (2, 2) are concepts of a context, (1, 1) is called a subconcept of (2, 2), provided that 1 ⊆ 2 (which is equivalent to 2 ⊆ 1). In this case (2, 2) is the superconcept of (1, 1) and it is possible to state that (1, 1) ≤ (2, 2). The relation ≤ is called the hierarchial order ( or simply order) of the concepts. The set of all concepts of (, , ) ordered in this way is denoted by B(, , ) and is called the concept lattice of the context (, , ).
The methodology of this work consists of the following parts:
• Extracting the keywords from the training documents, to be used as attributes for building
the training formal contexts for each document class.
• Building the concept lattice for each document class to be used for training the intrinsically
interpretable document classifier.
• Validating the concept lattice built for each document class using a lazy FCA document
classifier, which is similar to the one in [
The relevant components of the methodology are illustrated via the toy example in Fig. 1.
The classification performance of the intrinsically interpretable document classifier can only be reasonable if the formal contexts that are obtained for each class of the training data used to create the document-class concept lattices can adequately capture the underlying dependencies of the data, with minimum information loss. This can be validated by first testing the performance of a lazy FCA document classifier that uses the same document-class concept lattices that the intrinsically interpretable document classifier will use for training.
Each individual document is considered to be an object and a combined list of keywords extracted from all of the classes separately are considered to be its attributes. The keywords are extracted using the YAKE! algorithm [9], which was chosen because of its superior performance when compared to its contemporaries; as well as other conceptual scaling methods for text data. At test time, a test document is transformed into a formal context object with its attributes being the combined list of keywords extracted from all of the classes separately for all of the training documents.
The aim of the lazy FCA document classifier is to classify test documents by calculating a set of classification scores { } for each test document. Each document-class concept lattice is built using the formal context obtained from the training documents of the ℎ document class. A test document is classified as belonging to the class that has the highest classification score . The classification scores of a lazy FCA document classifier can be defined in many diferent ways, this particular work uses the following classification score:
|()| ∈() = 1 ∑︁ | ⊓ | × | ext()|[︁| ⊓ | ≥ 0.5 × | | ]︁ (1) where and stand for intent and extent, respectively. The score first checks if the number of attributes present in the intersection of the attributes for an intent of a formal concept and the attributes for an intent of the test document formal context object exceed a threshold that is greater than or equal to half of the total number of attributes present in the intent of . If the aforementioned condition (written in the Iverson bracket of equation (1)) is satisfied, the number of attributes in the intersection that satisfy the condition is weighted by the extent of the formal concept , which is used here as its interestingness measure [10].
This operation is done and the sum incremented for every formal concept that belongs to the set (). The threshold function that is applied to a document-class concept lattice is defined as () = { ∈ | () ≤ } ( being a hyperparameter). The function is defined for a formal concept as () = |{ | ∈ }|; with training documents ({}, {}), called “counterexamples”, belonging to any class other than the one that the formal concept belongs to. The function therefore, finds the number of counterexamples that a formal concept has.
The functioning of the intrinsically interpretable document classifier is explained with reference to the toy example illustrated in Fig. 1. Each of the documents belong to a class , where ∈ {red, yellow, blue}. For the purpose of training the intrinsically interpretable document classifier, similar to the process in Section 4.2; three document-class concept lattices are built for each class using their respective training documents.
Referring to Fig. 1, there are three document-class concept lattices: , and . Each formal concept that belongs to the ℎ document-class concept lattice , has its own extent and intent pair ({ }, { }), where is a set of documents and is a set of keywords that are present in all of the documents that constitute its respective extent , e.g., ({train_doc_1, train_doc_2, train_doc_3}, {keyword_1, keyword_2}).
With reference to Fig. 1, the three document-class concept lattices corresponding to the three classes can be considered as three components of a single, acyclic, directed, training graph = (, ). Each training vertex of is a formal concept = ({ }, { }) that belongs to class . A training edge ∈ (depicted in black) that connects the vertices to each other is considered equivalent to an (implied) arc that connects two elements in a lattice diagram. Thus, the training graph maintains the order relation, i.e., the superconcept/subconcept relation, among its training vertices (which represent the formal concepts ).
A test document (depicted in grey) belonging to an unknown class , is first converted to a test vertex with its own extent and intent pair ({}, {}) by means of the same formal context creation process described in Section 4.1. It is important to note that new keywords are not generated from the test documents so as to be used as the attributes of , rather the keywords obtained from the training documents during the training phase are used as the attributes of . Consequently, of a singular test document is just a singleton, consisting of its own object id (file name). Thus, the extent and intent pair of a test document is of the form ({test_doc_id}, {keyword_1, keyword_2, keyword_3, keyword_4,...}).
Using the topology of the training graph ; as well as the concepts related to its vertices , it is possible to predict all of the potential edges (depicted in green) between the test vertex and the training vertices . This is done in order to infer the class of the test vertex , based on the particular formal concepts (represented by the training vertices ) that the potential edges of may connect to.
A DNN is trained as a binary classifier on the concatenated intents of pairs of training vertices in order to predict whether an edge either exists between them or not. Then for predicting if/where the possible edges of a test vertex may connect to, the DNN takes as input concatenated intents of all pairs of training vertices and the test vertex .
The specific architecture of the DNN used in this work is comprised of 6 fully connected layers with 192, 128, 64, 32, 16 and 1 neuron(s). Batch normalization is used after the second and fourth layers during the training phase. Dropout is used after the third and fifth layers during the training phase with respective probabilities of 0.3 and 0.2. The ReLU activation function is used after every layer. The DNN has a weight decay of 5e-4, uses a binary cross-entropy loss function and is optimized via the Adam optimization algorithm [11]; having a learning rate of 0.001 and a learning rate decay multiplicative factor of 0.1.
The aggregation function computes a score for every document-class concept lattice and infers the class of the test vertex as belonging to the document class whose concept lattice has the highest aggregate score .
where (, ) = = 1
∑︁ (, ) × ( ) || ∈ {︃0, if no edge exists between and 1, if an edge exists between and (2) 1 and ( ) = ()+1
The function ( ) counts the number of counterexamples of the formal concept , was previously defined in Section 4.2 and is a part of the penalty function .
The rationale for creating such an aggregate score for each document-class concept lattice, in which the function (, ) is an essential component can be stated as follows: 1. It is not possible to accurately predict the exact training vertex that the predicted edge should connect to, in order to maintain the hierarchical order of formal concepts within the corresponding document-class concept lattice. This is particularly important for reasons of generating explanations as further elaborated in point 3. 2. Since a relatively simple method of representing attributes of the intents is used in this work, i.e., presence or absence of keywords, many pairs of the training vertices and the test vertex can have the exact same set of intents. Thus, it is beneficial to maximize the number of edge prediction tasks for both the training (as a form of auxiliary training data) and the testing of the intrinsically interpretable document classifier (in order to bolster the aggregate scoring function ). 3. It is necessary to find those training vertices that may connect to that text vertex in order to quantify the contribution of a formal concept toward classifying as belonging to a particular class. This is illustrated by the use of the function (, ) in computing the metric ( ).
The contribution of a formal concept toward classifying test documents as belonging to a particular document class can quantified by measuring the contribution of any predicted edges between them toward the aggregate score and is defined as ( ) = ∑︀∈test (, ) × ( ).
The chosen dataset [12] for use in this work is a subset of a larger dataset consisting of newsgroup documents [13]. There are a total of 1000 documents, which are divided into 10 classes; with each class having 100 documents. The classes are disjoint, which means that they are no documents that belong to more than one class. After the formal context creation step specified in Section 4.1, each document has a set of attributes that denote the presence or absence of 96 unique keywords.
The relatively small size of the dataset having only 1000 documents necessitates the need of using more data for training as compared to testing. Thus all experiments will be conducted with a 90:10 training to test split ratio. There will be 90 training documents for each class and 10 test documents for each class. The table below describes some characteristics of the training set after creating the document-class concept lattices.
As demonstrated by the table below, the lazy FCA document classifier demonstrates reasonable classification performance, across nearly all classes; with only certain classes showing poor performance. This means that the document-class concepts lattices were able to reasonably capture the underlying data dependencies in each class and map it to the conceptual hierarchy found in the concept lattices of each class. It is important to note that without this happening, there would be no reason to believe that the intrinsically interpretable document classifier would have good classification performance. The lazy FCA document classifier was run using hyperparameter value = 20.
.
The table above lists the formal concepts that have the maximum value for ( ) for a document class . The attributes of the intents of such formal concepts are intuitively logical and appear in at least half of all but one of the test documents of each class.
An intrinsically interpretable document classifier with moderately high classification performance that uses properties of the graph of the covering relation of a concept lattice (lattice diagram) was proposed. The intrinsically interpretable document classifier is able to quantify which formal concepts contributed the most toward the classification of a test document. Future work can focus on using more advanced methods for representing complex data such as pattern structures [14, 15] as well as using more sophisticated methods to take into account the assortativity of the graph vertices.
The work of Sergei O. Kuznetsov was supported by the Russian Science Foundation under grant 22-11-00323 and performed at HSE University, Moscow, Russia. [9] R. Campos, V. Mangaravite, A. Pasquali, A. Jorge, C. Nunes, A. Jatowt, Yake! keyword extraction from single documents using multiple local features, Inf. Sci. 509 (2020) 257–289.
URL: https://doi.org/10.1016/j.ins.2019.09.013. doi:10.1016/j.ins.2019.09.013. [10] S. O. Kuznetsov, T. P. Makhalova, Concept interestingness measures: a comparative study, in: S. B. Yahia, J. Konecny (Eds.), Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, Clermont-Ferrand, France, October 13-16, 2015, volume 1466 of CEUR Workshop Proceedings, CEUR-WS.org, 2015, pp. 59–72. URL: http://ceur-ws.org/Vol-1466/paper05.pdf. [11] D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, in: Y. Bengio, Y. LeCun (Eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL: http://arxiv.org/abs/ 1412.6980. [12] J. Baxter, (10)dataset text document classification, 2020. URL: https://www.kaggle.com/ datasets/jensenbaxter/10dataset-text-document-classification. [13] T. Mitchell, 20 newsgroups, 1999. URL: http://kdd.ics.uci.edu/databases/20newsgroups/ 20newsgroups.html. [14] B. Ganter, S. O. Kuznetsov, Pattern structures and their projections, in: H. S. Delugach, G. Stumme (Eds.), Conceptual Structures: Broadening the Base, 9th International Conference on Conceptual Structures, ICCS 2001, Stanford, CA, USA, July 30-August 3, 2001, Proceedings, volume 2120 of Lecture Notes in Computer Science, Springer, 2001, pp. 129–142.
URL: https://doi.org/10.1007/3-540-44583-8_10. doi:10.1007/3-540-44583-8\_10. [15] S. O. Kuznetsov, Scalable knowledge discovery in complex data with pattern structures, in: P. Maji, A. Ghosh, M. N. Murty, K. Ghosh, S. K. Pal (Eds.), Pattern Recognition and Machine Intelligence - 5th International Conference, PReMI 2013, Kolkata, India, December 10-14, 2013. Proceedings, volume 8251 of Lecture Notes in Computer Science, Springer, 2013, pp. 30–39. URL: https://doi.org/10.1007/978-3-642-45062-4_3. doi:10.1007/978-3-642-45062-4\_3.