PE : A Poincare Explanation Method for Fast Text Hierarchy Generation (2024)

Abstract: The black-box nature of deep learning models in NLP hinders their widespread application. The research focus has shifted to Hierarchical Attribution (HA) for its ability to model feature interactions. Recent works model non-contiguous combinations with a time-costly greedy search in Eculidean spaces, neglecting underlying linguistic information in feature representations. In this work, we introduce a novel method, namely Poincare Explanation (PE), for modeling feature interactions with hyperbolic spaces in a time efficient manner.Specifically, we take building text hierarchies as finding spanning trees in hyperbolic spaces. First we project the embeddings into hyperbolic spaces to elicit inherit semantic and syntax hierarchical structures. Then we propose a simple yet effective strategy to calculate Shapley score. Finally we build the the hierarchy with proving the constructing process in the projected space could be viewed as building a minimum spanning tree and introduce a time efficient building algorithm. Experimental results demonstrate the effectiveness of our approach. Our code is available at https://anonymous.4open.science/r/PE-747B.

## introduction deep learning models have been ubiquitous in natural language processing (nlp) areas accompanied by the explosion of the parameters, leading to increased opaqueness. consequently, a series of interpretability studies have emerged @xcite @xcite , among them feature attribution methods stand out owing to fidelity and loyalty axioms and straightforward applicability @xcite . previous feature-based works are limited to single words or phrases @xcite . @xcite point out that lime's @xcite performance on simple models is not plausible 1 . to model feature 2020 ) with bert and lstm on sst-2 and yelp datasets. a higher correlation coefficient indicates a stronger ability of the method to identify important words. however, building feature hierarchies is not a trivial thing. existing methods have three following problems. p-1: detecting contiguous text spans to replace all possible interactions @xcite . only using spans might lose long-range dependencies in text @xcite . for example, in the positive example "even in moments of sorrow, certain memories can evoke happiness", ("even", "sorrow") is vital and nonadjacent. p-2: current algorithms estimating the importance of feature combinations are accompanied by lengthy optimization processes @xcite . for example, he @xcite estimates the importance of words using lime algorithm and then enumerates word combinations to construct the hierarchy, with a cubic time complexity foot_1 . asiv @xcite uses directional shapley value to model the direction of feature interactions, while estimating shapley value requires exponential time. p-3: previous methods cannot model the linguistic information including syntax and semantic information. syntax and semantics can help to construct a hierarchical tree. for syntax, @xcite build hierarchies directly on dependency parsing trees (dpt) and compute pearson correlation (i.e.ρ). the results in figure 1 demonstrate syntax could contribute to building explainable hierarchies by reaching a higher correlation. for semantic, we take figure 2 as an example, the hierarchy in hyperbolic space has already achieved preliminary interpretability with the proximity corresponding the polarity. as the input text length continues to increase, efficiently modeling the interaction of noncontiguous features has become a key challenge in promoting ha. building a hierarchical attribution tree based on the input text is essentially a hierarchical clustering problem. the definition is as follows: given words and their pairwise similarities, the goal is to construct a hierarchy over clusters (word groups). pe approaches this problem by following three steps. first, to model linguistic hierarchical information, we project word embeddings into hyperbolic spaces to uncover hidden semantics and syntax structures. next, inspired by cooperative game theory @xcite , we regard words as players and clusters as coalitions and introduce a simple yet effective strategy to estimate the shapley score contribution. finally we calculate pairwise similarities and propose an algo-rithm that conceptualizes the bottom-up clustering process as generating a minimum spanning tree. our contributions are summarized as follows: ## related work feature importance explanation methods mainly assign attribution scores to features @xcite @xcite . methods can be classified into two categories: single-feature explanation type and multifeature explanation type. ## background we first give a review of hyperbolic geometry. poincare ball a common representation model in hyperbolic space is the poincare ball, denoted as (b m c , g b x ), where c is a constant greater than 0. b m @xmath0, and g b cooperative game theory we use n to denote a set of players (i.e. token set). a game is a pair γ = (n, v) and v : 2 @xmath1. a coalition is any subset of n . in a cooperative game, players can form coalitions, and each coalition s ⊆ n has a value v(s). ## methodology this section provides a detailed introduction to the three parts of pe. first, we need to score each feature; then, based on these scores, we construct a hierarchy. in section 4.1, we consider semantic and syntax factors. besides we facilitate feature shapley contribution calculation in section 4.2. in section 4.3, we combine these factors to score each feature and propose a fast algorithm for constructing the hierarchy. ## analysis of time complexity in this section, we delve into the time complexity associated with ha methods, which can be divided into two parts: the complexity of generating attribution scores, denoted as o attr , and the complexity of generating the hierarchy from the scores, denoted as o hierarchy . as shown in ## conclusion in this paper, we introduce pe, a computationally efficient method employing hyperbolic geometry for modeling feature interactions. more concretely, we use two hyperbolic projection matrices to embed the semantic and syntax information and devise a simple strategy to estimate the contributions of feature groups. finally we design an algorithm to decode the hierarchical tree in an o(n 2 logn) time complexity. based on the experimental results of three typical text classification datasets, we demonstrate the effectiveness of our method.