A Neural CRF -based Hierarchical Approach for Linear Text Segmentation (2023)

Abstract: We consider the problem of segmenting unformatted text and transcripts linearly based on their topical structure. While prior approaches explicitly train to predict segment boundaries, our proposed approach solves this task by inferring the hierarchical segmentation structure associated with the input text fragment. Given the lack of a large annotated dataset for this task, we propose a data curation strategy and create a corpus of over 700K Wikipedia articles with their hierarchical structures. We then propose the first supervised approach to generating hierarchical segmentation structures based on these annotations. Our method, in particular, is based on a neural conditional random field (CRF), which explicitly models the statistical dependency between a node and its constituent child nodes. We introduce a new data augmentation scheme as part of our model training strategy, which involves sampling a variety of node aggregations, permutations, and removals, all of which help capture fine-grained and coarse topical shifts in the data and improve model performance. Extensive experiments show that our model outperforms or achieves competitive performance when compared to previous state-of-the-art algorithms in the following settings: rich-resource, cross-domain transferability, few-shot supervision, and segmentation when topic label annotations are provided.

## introduction text segmentation @xcite , an important task in information retrieval, is defined as the process of dividing unstructured text into topically coherent segments. because it recovers topical structure from unformatted text, it can be used as a pre-processing step for several downstream tasks such as text summarization @xcite , question answering @xcite and discourse analysis @xcite . most prior works on text segmentation @xcite @xcite attempted to address this task by explicitly predicting the segment boundaries, with the assumption that any given text can be decomposed into contiguous, nonoverlapping, indivisible segments, based on topical themes. the discourse segmentation theory @xcite , however, asserts that the outcome may not always be strictly decompositional, i.e., a segment may have sub-segments within it, and segments may overlap with each other. following this theory, we hypothesize that explicitly training to infer the hierarchical topic structure of the underlying text leads to better linear segmentation, as it forces the models to examine text at multiple levels to extract coarse-grained to fine-grained topical segments. further, this allows inference of linear segments of varying granularity that can be used for various downstream applications. previous works on hierarchical segmentation are largely unsupervised @xcite due to the unavailability of large labelled datasets with hierarchical structure information. in this paper, we propose to leverage the hierarchical structures in a supervised manner, given the superior performances of supervised models across several language processing tasks @xcite @xcite , and propose a data curation strategy to obtain the hierarchical segmentation structures for wikipedia articles. specifically, we leverage the available html tag annotations foot_0 and use them to identify section and sub-section information with their hierarchical level, which are then leveraged to obtain the associated ground truth hierarchical structure. further, because these are extracted from wikipedia dump, they cover a wide range of topics unlike prior/existing datasets @xcite . 2 our approach is based on a recent crf-based constituency chart parsing technique @xcite , which offers efficient algorithms for super-vised training and precise inference. this framework explicitly models the relationships between nodes and their offspring in binary trees, and thus can enable hierarchical segmentation inference by utilising the relationships between coarse segments and their fine-grained sub-segments. however, there are three challenges to directly adapt this method to hierarchically segment text: (a) in contrast to the abundant labelled resources available for constituency parsing @xcite , there is no large-scale labelled dataset for this task. (b) this method can only infer binarized hierarchical structures; it cannot be extended to infer general hierarchical structures with nodes having any number of children, as training and inference become infeasible. (c) while the existing method processes a sequence of tokens, the input in our case would be a sequence of sentences. we propose a framework for linear text segmentation using the hierarchical structures of the underlying text. specifically, our work makes four main contributions: (1) we design an algorithm to obtain the hierarchical structures for wikipedia articles in html format, and curate a large labelled dataset for hierarchical text segmentation. 3 (2) we present an algorithm based on the chomsky normal form (cnf) @xcite @xcite theory to convert the hierarchical structures to binarized form -which makes the computation of the tree-structure crf objective tractable. (3) we propose a transformer-based architecture @xcite to encode the input sequence's sentences, which uses a lot fewer parameters than previous state-of-the-art bertbased @xcite approaches @xcite . (4) we further propose a data augmentation technique involving random node aggregations, removals and permutation, which results in significant performance improvement. finally, we demonstrate our method's efficacy by comparing its performance against prior unsupervised and supervised linear text segmentation approaches. ## related works prior works for linear text segmentation can be divided into unsupervised and supervised methods, both of which can be further categorized into locally and globally-informed ones. locally3 the code to curate dataset is available at https: //github.com/inderjeetnair/hierarchical_ text_segmentation_data informed methods find segment boundaries by estimating the extent of topical shift using local cues @xcite @xcite . while these methods enjoy quick inference and low memory constraints as they only utilize local features, they can result in erroneous predictions when met with short inconsequential digressions @xcite . globally-informed methods, on the other hand, utilize the complete context in optimizing an objective to find the locations of topical shift @xcite @xcite @xcite . as they consider the entire global context in inference, these methods have higher memory constraints and time requirements. more recently, @xcite introduced a large-scale dataset for linear text segmentation, which has resulted in the application of supervised neural models to predict the segment boundaries for unstructured text @xcite @xcite . these models not only achieve better performance but also are endowed with high inference speed, owing to parallelized computing with modern gpu architectures. owing to the success of supervised methods for linear text segmentation, we design a globallyinformed supervised neural model for predicting segment boundaries. however, unlike previous works which address segment boundary prediction explicitly, ours first hierarchically segments the text, and then leverages the resulting structures to predict the linear segment boundaries. to enable the supervised training of our proposed approach, we curate a large labelled dataset consisting of wikipedia articles along with their hierarchical structures automatically. further, our proposed method requires significantly fewer parameters that prior sota globally-informed methods while achieving better performances. to the best of our knowledge, ours is the first work to leverage hierarchical structures to predict segment boundaries, and show that this results in improved performances for the task of linear text segmentation. ## problem formulation here, we briefly outline the objectives of linear and hierarchical text segmentation tasks. given an article s composed of n sentences, @xmath0, s 1 , . . . , s n-1 , the goal of linear segmentation is to obtain a contiguous partition @xmath1: transformation of a sequence of linear segmentations to a hierarchical tree. l 0 , l 1 , . . . , l k-1 such that joining the elements of l i in the same order reconstructs s and l i ∩ l @xmath2. each segment l i in l is associated with a topical theme which can be used for downstream tasks such as summarization, information retrieval, etc. hierarchical segmentation (mcfee et al., 2017) aims to infer a sequence of linear segmentations, @xmath3, l 1 , . . . , l m-1 , where l i is coarser than l j for @xmath4. each element of l is thus a refinement of all its preceding elements, to satisfy this coarse-to-fine grained constraint. the refinement condition for @xmath5: ∀@xmath6: l ⊆ l ′ . that is, every segment in l j is a subset of a segment in l i . in this paper, we represent the information contained in l using a hierarchical tree (fig. 1 ), where each node (other than the leaf nodes) represents a topical theme. the nodes near the root represent general / coarser topics, and those near the leaves indicate specific / fine-grained topics. in our approach, the inferred hierarchical segmentation is in the form of a tree. after converting this tree to a sequence of linear segmentations, we return an appropriate element from the sequence as our inferred linear segmentation. ## dataset curation to train our proposed method in a supervised manner, we collect hierarchical segmentation structure annotations for the wikipedia articles in wiki-727k dataset @xcite . as done in @xcite , the articles in the html form are preprocessed using wikiextractor 4 to remove (a) non-text elements such as tables and figures, and (b) very short sections and sub-sections spanning fewer than three sentences. the markup tags (<h1>,..., <@xmath7. we leverage this markup information to obtain the hierarchical structure among the various segments. we thus obtain a sequence of html elements for each article. in the next sub-section, we describe our algorithm to obtain the hierarchical structures associated with these sequences. we obtain the hierarchical structure annotations only for the train split articles of the wiki-727k dataset; our approach can be applied to larger document collections to obtain more datapoints. ## experiments and results we assess our method's performance in various settings when compared to sota linear segmentation techniques. the tree inference from the model is converted to a sequence of linear segmentations (fig. 1 ). as the position of an element in this sequence indicates the extent of segmentation, we select an appropriate position (constant for a dataset, obtained through validation for supervised methods, and second position for unsupervised methods due to how coarsely grained the topical shifts are in them) and return the corresponding segmentation. we call our method variants hiercrf and hiercrf-aug, where the former and latter are trained without and with data augmentation. we compare our models to supervised methods trained on wiki-727k augmented with our hierarchical structure annotations ( §6.1). unsupervised methods @xcite ) require a significant amount of time for inference as they are computationally intensive and do not take advantage of gpu parallelization for efficiency. hence, we do not compare their performance for wiki-727k, which contains a large number of datapoints in the test split. in §6.2, we look at how our model transfers knowledge from one domain to another and investigate efficacy in a low-resource setting. here, we compare our method to unsupervised as well as some supervised methods. finally, we evaluate how our model utilises topic label information for segmentation using wikisection @xcite . ## conclusion we curated a dataset with hierarchical structures and introduced an approach for linear segmentation by inferring the hierarchies. we illustrated the effectiveness of our approach against prior supervised and unsupervised methods for several datasets. our method, when exposed to a small fraction of the data for fine-tuning, achieves superior performance when evaluated on other datasets for this task. unlike prior unsupervised methods, ours without any hyperparameter tuning achieved competitive results. while we focussed on predicting segment boundaries, our method could also be applied to yield hierarchical segmentation. however, the challenges specific to dataset size and memory persist. we will study these aspects in our future work.