Learn The Big Picture: Representation Learning for Clustering (2021)

Abstract: Existing supervised models for text clustering find it difficult to directly optimize for clustering results. This is because clustering is a discrete process and it is difficult to estimate meaningful gradient of any discrete function that can drive gradient based optimization algorithms. So, existing supervised clustering algorithms indirectly optimize for some continuous function that approximates the clustering process. We propose a scalable training strategy that directly optimizes for a discrete clustering metric. We train a BERT-based embedding model using our method and evaluate it on two publicly available datasets. We show that our method outperforms another BERT-based embedding model employing Triplet loss and other unsupervised baselines. This suggests that optimizing directly for the clustering outcome indeed yields better representations suitable for clustering.

## introduction text clustering is a well-studied problem which finds its application in a wide range of tasks: organizing documents in cluster-based information retrieval @xcite , representation of search results @xcite , analyzing different opinions about a subject @xcite among many others. each of these applications may focus on text contents of different granularities (e.g. words, sentences, passages, articles) but all of them follow a common high-level approach to clustering: represent the documents in form of vectors and then cluster them based on vector similarities. although clustering is typically employed in an unsupervised setting, many semi-supervised deep learning models have been proposed recently. many of these approaches formulate this as a representation space learning prob-lem @xcite that projects initial document vectors into a latent vector space which is more suitable for the clustering task and generate clusters similar to some ground truth. however, most of these algorithms do not directly optimize for a clustering evaluation metric during training. instead, they optimize for a different criterion that approximates the global clustering error. semi-supervised clustering approaches @xcite cast the clustering problem into binary classification by learning pairwise constraints extracted from the available training examples: mustlinks for sample pairs sharing the same cluster and cannot-links for different clusters. however, clustering problems with numerous small clusters produce only a few must-links among all possible links, leading to highly unbalanced training data. consequently, the trained model is biased towards predicitng cannot-links. learning triplet-based constraints @xcite that combine a positive and a negative sample in a single triplet, mitigate such bias towards negative samples. however, the sample complexity @xcite (number of samples required to cover all interactions in a dataset) grows more rapidly compared to paired samples. also, such approximation of the original clustering problem may lead to unsatisfactory results because the optimization criterion does not always correspond with the clustering quality. these observations motivate us to hypothesize the following: to test our hypotheses, we propose an alternative training strategy that directly draws its supervision signal from an evaluation metric that measures clustering quality to train a representation model for text documents. during training, it consumes a complete clustering example of a set of data points as a single training sample in form of an interaction matrix. due to this, we experiment with clustering datasets containing numerous small clustering examples instead of a single instance of a large clustering problem. it is challenging to derive training signals directly from the clustering ground truth or a clustering evaluation metric because the clustering process is discrete. in other words, a function that estimates the clustering quality of a random partition of the input data is not continuous and hence nondifferentiable. as most supervised algorithms rely on gradient-based optimization algorithms, it is difficult for them to orchestrate a useful training process without proper gradient. so far some continuous approximation of the clustering problem is used as discussed earlier to bypass the core optimization issue. recently a novel gradient approximation method, blackbox backpropagation @xcite is proposed for combinatorial problems that finds solution in a discrete space. we leverage their findings by molding the clustering problem into a combinatorial problem. this allows us to derive meaningful gradients out of the clustering process and to train a representation model by directly optimizing for a clustering evaluation metric. our contribution: we make the following contributions through this work. traditionally, text clustering is achieved by employing a distance-based clustering algorithm (e.g. kmeans) on vector representations of documents such as tf-idf @xcite . recent works focus on learning text representaions suitable for clustering @xcite @xcite . alternatively, they explore different similarity metrics between the vectors that govern the clustering algorithm through pairwise binary constraints @xcite . in this work, we focus on the former -representation learning of documents, suitable for text clustering. deep clustering @xcite is an active field of research that utilizes recent advancements of deep learning techniques to improve supervised clustering. the primary focus is to learn a suitable representation space that optimizes some clustering criterion (e.g. cluster assignment loss) along with a representation criterion (e.g. reconstruction loss) @xcite @xcite . it has also been shown that clustering criterions alone are sufficient to train such representation space @xcite . however, none of these approaches attempt to receive direct supervision from a clustering evaluation metric. motivated by earlier works that learn a representation model under pairwise binary constraints, @xcite envisions the clustering task as a binary classification task of paired data samples and achieves state-of-the-art results on multiple image clustering datasets. @xcite propose sentence-bert which trains a bert-based sentence embedding model by employing triplet loss @xcite that uses triples of sentences as training samples where exactly two of them are from the same section of wikipedia. although both of these approaches are supervised, each training sample only consists of a fraction of the whole clustering instance. hence, during training, these methods mostly ignore the overall relationships between multiple data samples and how they form clusters. the main hindrance of drawing a supervision signal directly from a clustering evaluation metric is the combinatorial nature of the clustering problem. some research introduce differentiable building blocks for special cases of combinatorial algorithms such as satisfiability (sat) problems @xcite . @xcite use a differentiable variant of the k-means algorithm to approximate a harder combinatorial problem (e.g. graph optimization). such relaxations of the original combinatorial problem may lead to sub-optimal results. recently, @xcite proposed a novel technique of differentiating combinatorial solvers as a blackbox without any relaxation that allows us to use an optimal combinatorial algorithm as a component of a deep representation learning model and optimize it end-to-end. we give a brief background of their approach in the following section. ## methodology our text clustering method works in two steps: 1. train a text representation model directly from example clusters of text snippets, 2. cluster the trained embedding vectors using hierarchical agglomerative clustering (hac). our primary con-tribution lies in the training strategy of step 1 which we refer here as clustering optimization as blackbox (cob). we describe cob in the following sections. ## experimental results in this section, we describe the datasets used for our experiments, discuss our evaluation paradigm and present experimental results that demonstrate efficacy of the representation model trained using our proposed training strategy over our baseline models. ## conclusion in this work, we propose an alternative training strategy to train a representation model, for clustering. our training strategy, cob (clustering optimization as blackbox), directly optimizes the rand index, a clustering evaluation metric. using our method, we train sbert cob, a bert-based text representation model. we empirically show that sbert cob significantly outperforms other supervised and unsupervised text embedding model on two separate datasets in terms of ri, ari and nmi, indicating better cluster quality. visual representations of the resulting vectors also confirm that sbert cob learns to holistically distinguish clusters of different topics. moreover, each epoch in sbert cob training loop is about 100 times faster when compared to sbert triplet, our best performing baseline method. this leads to a significant decrease in overall training time even though sbert cob requires more iterations to converge than sbert triplet. this makes sbert cob suitable for applications that require clustering models to be updated on a regular basis as new training samples become available. lastly, although we have conducted experiments with a specific clustering algorithm (hac) and a clustering metric to optimize (rand index), our model is independent of the particular choice of algorithm or the metric.