Seeded Hierarchical Clustering for Expert-Crafted Taxonomies (2022)

Abstract: Practitioners from many disciplines (e.g., political science) use expert-crafted taxonomies to make sense of large, unlabeled corpora. In this work, we study Seeded Hierarchical Clustering (SHC): the task of automatically fitting unlabeled data to such taxonomies using a small set of labeled examples. We propose HierSeed, a novel weakly supervised algorithm for this task that uses only a small set of labeled seed examples in a computation and data efficient manner. HierSeed assigns documents to topics by weighing document density against topic hierarchical structure. It outperforms unsupervised and supervised baselines for the SHC task on three real-world datasets.

## introduction practitioners across a diverse set of domains that include web mining, political science and social network analysis rely on machine learning techniques to understand large, unlabeled corpora @xcite @xcite . in particular, they often need to fit this data to taxonomies (i.e., hierarchies) constructed by nontechnical domain experts using only a few labeled examples. in this work, we formalize this task, seeded hierarchical clustering (shc), and propose a novel algorithm, hierseed, for it. consider a researcher analyzing social media to track public feeling around a hierarchy of wellbeing indicators (see figure 1 ). working with such taxonomies can be challenging. since they are hand-crafted by domain experts to explore a particular area of focus, they may be unbalanced (with subtopics that over-represent one aspect of their parent topic) or incomplete (with subtopics that are only partially enumerated). moreover, these hierarchies may not fully explain every document in large, diverse corpora. finally, given their domain specificity, producing many labeled examples for each topic in such taxonomies can be expensive. shc incorporates these challenges as constraints: given only a user-defined topic hierarchy and a few labeled examples, the task is to assign documents from a much larger corpus to the individual topics. while many unsupervised techniques and their hierarchical extensions automatically discover latent structure within text corpora, they are difficult to integrate with user-defined taxonomies (e.g. @xcite ; @xcite ; @xcite ). moreover, as these methods often rely on centroids, density metrics and maximum likelihood objectives to discover dataset partitions, they may produce clusters that favor the denser, semantically more coherent regions of an unbalanced taxonomy at the expense of the sparser but more diverse regions. although supervised hierarchical methods avoid these issues, they are usually very data intensive. to address these challenges, we propose hi-erseed, a weakly supervised hierarchical method for fitting a large unlabeled corpus to a user-defined taxonomy. it assigns documents to topics by weighing document density against a topic's local hierarchical structure. to accommodate imbalance or incompleteness, hierseed constructs and uses topic representations that account for subtopic density (degree of semantic coherence) and spread (degree of semantic divergence) around each topic. as it uses only a few labeled seed examples to optimize its objective in a non-parametric fashion, it is both data and computationally efficient. we evaluate hierseed on three real-world newswire and scientific datasets and show that it outperforms state-of-the-art unsupervised and supervised baselines on this new, difficult task. our contributions are: (1) we formalize the task of seeded hierarchical clustering, (2) we present hierseed, a novel algorithm that uses only a few labeled examples to efficiently fit a large corpus to a user-defined hierarchy (even if it is unbalanced or incomplete), (3) we show it outperforms existing methods on three real-world datasets from different figure 1 : a researcher wants to track public well-being using a large, unlabeled social media corpus. she creates a taxonomy of relevant topics (0) -it does not cover every document in her dataset. moreover, as it is hand-crafted, it is unbalanced and incomplete. she can't annotate a large number of examples. with only a few labeled seed examples for each topic (1) and her large unlabeled fitting set (2), hierseed efficiently identifies the documents related to every topic via an iterative discriminative algorithm that balances their density against their spread (3). ## related work unsupervised methods like lda and k-means @xcite @xcite are flat clustering techniques that have been successfully extended to hierarchies @xcite . while both we and @xcite apply k-means iteratively, they rely on hierarchical clustering to discover the number of topics at each level. none of these methods can detect a user-defined hierarchy. there is work on taxonomy construction and expansion @xcite @xcite though it cannot be used for document assignment. supervised hierarchical classification techniques can be categorized into flat, local and global approaches @xcite . flat approaches @xcite ignore the hierarchy, whereas local approaches @xcite rely on multiple local classifiers, propagating errors down the hierarchy. global approaches @xcite encode the entire hierarchy and predict all labels at once. @xcite generate their own text embeddings while directly embedding the hierarchy information into their encoder using contrastive learning for downstream classification. this leads to better performance and has become common for this task. nevertheless, these approaches require a large number of labeled training examples for good performance, making them difficult to use in data-scarce scenarios. semi-supervised hierarchical methods require much less labeled data @xcite @xcite . josh @xcite uses a tree and text embedding model to jointly embed a taxonomy and a corpus in a spherical space, using category names to mine words relevant to each topic. weakly-supervised classifiers like taxoclass @xcite and hclass @xcite leverage provided keywords and documents for each topic to generate a set of pseudo documents for pretraining, then self-train on unlabeled data. despite their strengths, these methods require more labeled data and expensive finetuning. moreover, they work best if the labeled dataset represents all categories and documents. however, in some domains (e.g., figure 1 ) knowledge of relevant categories is incomplete. in contrast to this prior work, seeded clustering may be preferable as it first uses a small labeled seed set to bias the search space towards a desirable region and then leverages the representative latent structure of a larger unlabeled fitting set to improve the clustering @xcite . we propose one such technique, hierseed, which takes any taxonomy (unbalanced or incomplete) and a few labeled seeds and learns a discriminative hierarchical repre- algorithm 1: hierseed input: a corpus d; seeds s and taxonomy t of height n ; pivot level ρ. output: learned topic representations for all c @xmath0; set of relevant documents δ i ⊂ d for each c i . 1 initialize topics c @xmath1, l from n -1 to ρ: 4 update c @xmath2. 1 5 extend taxonomy, ∀c i add "other" topic to ch(c i ) (eq. 2) 6 e-at-level-ρ, for each c @xmath3: 7 calc. topic threshold τ (c i ) ( §3.3.2) 8 identify documents δ i (eq. 3) 9 m-top-down, l from ρ to n , c @xmath4: 10 run k-means on δ i , @xmath5, l from ρ to n , c @xmath6: 13 set δ i to k-means clusters sentation that allows assigning relevant documents to each of its component topics. ## methodology we propose hierseed, a weakly-supervised algorithm for seeded hierarchical clustering that uses document embeddings and their latent structure to represent topics in the same embedding space ( §3.1). we initialize the representation for each topic using its seed documents ( §3.2) and then update the representation in a bottom-up manner by considering both a topic's children and the density of documents around it ( §3.3). finally, we balance the hierarchy and assign documents to each topic in a top-down manner (while also updating its representation). we repeat this iteratively until convergence (see algorithm 1, figure 1 (3)). ## conclusion and future work in this paper, we formalize the task of seeded hierarchical clustering: fitting a large, unlabeled corpus to a user-defined taxonomy (that may be unbalanced or incomplete) using only a small number of labeled examples. we propose a novel, discriminative weakly supervised algorithm, hierseed, for it which outperforms both unsupervised and (weakly) supervised state-of-the-art techniques on three real-world datasets from different domains. in the future, we aim to jointly learn and finetune task specific embeddings, develop a generative variant of hierseed and explore non-euclidean representation spaces. while hierseed is non-parametric and outperforms both unsupervised and supervised baselines for the shc task on the three real-world datasets evaluated here, it relies on a few choices and assumptions. first, the algorithm requires selecting a pivot level below which all computations are performed. the pivot level is determined by identifying a level above which the taxonomy is well defined. for complex or incomplete taxonomies this can be hard to recognize, making the root (or a higher level) the easier choice. however, since most clustering mistakes occur at the pivot level, having a high pivot level will decrease recall at the following levels (due to error propagation) while a low pivot level will decrease precision at preceding levels as the lower levels tend to be more specific. another limitation is that since hierseed depends on external document embeddings (used to compute initial topic representations from the seeds), the clusters are sensitive to both the informativeness of the topic seeds and the richness of the embeddings. additionally, computing representations of topics having a diverse set of subtopics is intrinsically more difficult than computing representations of topics and subtopics in a specific domain (owing to their semantic closeness). the top-down nature of topic assignment makes it crucial to start off with informative document representations to avoid error propagation. however, semantically close topics also pose a challenge as their representations become difficult to distinguish, leading to errors in topic assignment. the form of expectation maximization used by hierseed assumes that all clusters are similarly sized and have the same variance. in practice, this may not always be the case. the use of euclidean distance as the similarity metric, and variance as a measure of cluster scatter (as in k-means) limits the usability in the more general non-euclidean cases. additionally, hierseed may not be suitable for identifying clusters with non-convex shapes at each level of the hierarchy as it relies on k-means which cannot separate nonconvex clusters. however, the overall identified hierarchy may be non-convex as it is a union of multiple convex sets.