Decomposing Co-occurrence Matrices into Interpretable Components as Formal Concepts (2024)

Abstract: This study addresses the interpretability of word representations through an investigation of a count-based co-occurrence matrix. Employing the mathematical methodology of Formal Concept Analysis, we reveal an underlying structure that is amenable to human interpretation. Furthermore, we unveil the emergence of hierarchical and geometrical structures within word vectors as consequences of word usage. Our experiments on the PPMI matrix demonstrate that the formal concepts that we identified align with interpretable categories, as shown in the category completion task.

## introduction word vector representations are central to natural language processing, as they capture semantic and syntactic features @xcite . their significance has been amplified in recent times, as they are used as input for transformer-based language models @xcite , where static embeddings are contextualized. their effectiveness has been explained by the distributional hypothesis @xcite linking similar semantics and similar distribution @xcite . however, the interpretability of their dimensions remains an active research topic @xcite . @xcite found neural word embeddings to be uninterpretable while acknowledging that sparse vectors capture some latent topics. @xcite , among others, pioneered efforts to interpret dynamic embeddings in gpt-2 @xcite by projecting them into the vocabulary space, though a systematic approach to interpret dimensions of embeddings remains an open issue. many preceding studies have investigated the semantic properties of word embeddings and revealed that word vectors in a vector space capture relational meanings. the most well-known example is the parallelogram formed in the vector space by the embeddings of words in analogical relations (e.g. king:queen::man:woman) @xcite . other semantic relationships also exhibit geometrical counterparts, such as semantic composition with vector addition @xcite , hypernymy captured by linear projection @xcite , and polysemy as a linear combination of vectors @xcite . regarding the theoretical analysis of embeddings, @xcite suggested that word2vec @xcite is equivalent to the factorization of a word co-occurrence matrix. @xcite proposed a generative model in which pmi-based word embeddings exhibit linear structures. these related studies collectively hint that the latent structure in the co-occurrence matrix reflects linguistic regularities and is inherently embedded within vector representations. therefore, understanding the word co-occurrence matrix represents a cornerstone in elucidating the interpretability of word representations. in this study, we directly address the mathematical structure of a word co-occurrence matrix to uncover underlying linguistic patterns and to interpret the dimensions of word embeddings. we claim that a formal concept, as mathematically defined in the matrix, corresponds to human-interpretable categories. we substantiate our claim through the category completion task. specifically, we used formal concept analysis (fca), a field of applied mathematics @xcite , to formally characterize the internal structure of a matrix. we define a group of words as interpretable if it can be descriptively labeled. furthermore, we demonstrate that a hierarchical structure of formal concepts emerges as a geometric formation in the vector space, which explains why relational meanings are captured by word embeddings. our contributions are threefold. first, we propose two methods that apply fca to real-valued data: binarization by varying thresholds and fuzzi-fication of fca. second, we empirically show that the formal concepts in the co-occurrence matrix coincide with interpretable categories. third, we present a novel algorithm to detect formal concepts, which is capable of disambiguating polysemous words. to our knowledge, this is the first study to apply fca to a word-word co-occurrence matrix. our study offers a new approach to uncover latent linguistic structures in co-occurrence matrices. fca is related to order theory and abstract algebra. it mathematizes concepts and conceptual hierarchy @xcite . a concept comprises a pair of its extents (objects) and its intents (attributes). concepts can form a hierarchy known as a lattice. fca has been empirically applied for data mining and ontology @xcite , especially in bioinformatics @xcite . a formal context k := (g, m, i) consists of two sets g, m and a binary relation i ⊆ g × m . the elements of g and m are called objects and attributes, respectively. for @xmath0, a relation (g, m) ∈ i means that the object g has the attribute m. we define two derivation operators; ↑ : 2 @xmath1, and its reverse ↓ : 2 @xmath2. a↑ ⊆ m is the set of attributes common to all objects in a, whereas b↓ ⊆ g is the set of objects that possess all the attributes in b. it can be shown that a ⊆ b↓ ⇔ b ⊆ a↑, which is a structure-preserving (order-reversing) correspondence between ordered sets known as a galois connection @xcite . a formal concept of the context (g, m, i) is defined as a pair (a, b) ∈ 2 g × 2 m where both a↑ = b and b↓ = a hold. a and b are considered the extent and intent, respectively, of the formal concept (a, b). the compositions of two derivation operators ↑↓ : 2 @xmath3: 2 @xmath4, with a formal concept defined as the fixed point of these operations. if a formal context is represented as a binary matrix, it corresponds to a maximal rectangular (submatrix) with all ones in its entries when the rows and columns are appropriately reordered. a formal concept can also be equated with a maximal biclique, i.e., a complete subgraph of a bipartite graph @xcite . all elements of a and b are completely connected within that subgraph. ## experiment 1: fca by binarization we now demonstrate that formal concepts can be defined on actual word co-occurrence data and correspond to both semantic and syntactic categories. ## related studies several studies demonstrated that sparse embeddings are interpretable. @xcite and @xcite applied nonnegative matrix factorization with a sparsity constraint to worddocument co-occurrence data and discovered topics. other studies @xcite @xcite investigated word embeddings to restore interpretability by using sparsity. we mathematically formalized the latent structure in the word co-occurrence matrix, which prior studies might have empirically detected. fca has been applied in linguistics @xcite , primarily for ontology. @xcite applied fca for the automatic acquisition of taxonomies from a corpus. moraes and lima (2012) built a semantic structure by setting the s-v-c tuples of the annotated corpora as a formal context. @xcite used fca by binarizing sparse word embedding for hypernymy discovery. in contrast to these studies, we deployed fca to explore the structure of the matrix itself, which revealed the underlying structure of word-word co-occurrence matrices. gastaldi (2021) delved into the underlying mechanism of word embeddings from a linguisticphilosophical perspective and pointed out simultaneous codetermination or bi-duality between terms and contexts as a significant feature of language, which we believe to have successfully formalized via fca. our mathematical approach to interpreting co-occurrence data may shed light on the structure of language, as @xcite frames language in category theory. ## summary this study establishes a mathematical characterization of semantic relations represented as geometrical formations in a vector space, employing fca to investigate a word co-occurrence matrix. our experiments demonstrate that identified formal concepts align with interpretable categories. using synthetic data, we also illustrated the emergence of hierarchical structures from word usage. subsequent challenges include theoretical sophistication in applying fca, exploring generative modeling, and delving into cognitive inquiries.