F ast KASSIM : A Fast Tree Kernel-Based Syntactic Similarity Metric (2023)

Abstract: Syntax is a fundamental component of language, yet few metrics have been employed to capture syntactic similarity or coherence at the utterance- and document-level. The existing standard document-level syntactic similarity metric is computationally expensive and performs inconsistently when faced with syntactically dissimilar documents. To address these challenges, we present FastKASSIM, a metric for utterance- and document-level syntactic similarity which pairs and averages the most similar constituency parse trees between a pair of documents based on tree kernels. FastKASSIM is more robust to syntactic dissimilarities and runs up to to 5.32 times faster than its predecessor over documents in the r/ChangeMyView corpus. FastKASSIM’s improvements allow us to examine hypotheses in two settings with large documents. We find that syntactically similar arguments on r/ChangeMyView tend to be more persuasive, and that syntax is predictive of authorship attribution in the Australian High Court Judgment corpus.

## introduction syntax, the form of language, plays a crucial role in all aspects of natural language and communication, whether explicitly or implicitly. in storytelling, writers often have their own styles rooted in different syntactic tendencies @xcite , allowing syntax to become indicators in prediction tasks such as gender @xcite and authorship @xcite attribution. syntax also has social connotations in different cultures -for example, in russia, different social and demographic groups tend to use different syntactic patterns @xcite . such examples makes syntactic consistency crucial to capture in tasks such as machine translation and dialogue generation so that social conventions are not lost. yet, recent research focuses primarily on evaluating similarity and coherence in terms of dimensions like semantics, the meaning behind language, (with approaches such as bert embeddings @xcite ), or lexical overlap (e.g., bleu @xcite ) -even in work which uses syntax as an input to improve translation quality @xcite . a lack of work on syntax can be partially attributed to the absence of a practical, efficient metric that specifically compares syntax at the utterance level. the current standard metric is cas-sim @xcite , but cassim uses a computationally expensive distance metric and can yield inconsistencies when comparing syntactically dissimilar documents (e.g., figure 1 ). to address this issue, we introduce fastkassim, a fast tree kernel-based syntactic similarity metric foot_0 , an improved metric for syntactic similarity at the utterance-and document-level. like its predecessor, cassim, fastkassim computes the constituency parse tree of each sentence in a pair of documents, and the similarity between each pair of parse trees. but, while cassim used edit distance @xcite for similarity, we propose using a label-based tree kernel (henceforth ltk), our more syntactically thorough implementation of the fast tree kernel @xcite . we evaluate fastkassim against @xcite ; @xcite ). we find that fastkassim is more robust in cases of dissimilarities between documents and is generally more agreeable with human perception of differences in syntax. additionally, the runtime of ltk is much faster than that of edit distance; it scales linearly with the number of node pairs with the same label in a pair of parse trees. we empirically show large improvements in runtime with fastkassim. previously, it was difficult to observe the role of syntax in behavioral phenomena at scale due to runtime constraints. here, we contribute a study of hypotheses in two sets of applications. first, we examine the relationship between the persuasiveness of online arguments and syntactic similarity, and second, we observe the viability of syntax as an indicator in authorship attribution. fastkas-sim unlocks potential for evaluatory use in more contexts where it is important to preserve syntactic consistency and writing style, e.g., style transfer, machine translation, and story generation. ## related work a few early studies focused solely on capturing syntactic structures. @xcite sought to cluster words by syntactic similarity. in order to establish a distance metric, they computed the cosine distance between vector representations of their unique constituency parses. other approaches have used liwc @xcite . @xcite took a probabilistic approach to measure symmetry and influence of linguistic style. other early analytical work found that people will adjust their syntax to match dialog systems' syntactic @xcite and lexical @xcite choices. @xcite found that individual syntactic productions would repeat at low "distances" across utterances in both task-oriented and "spontaneous" dialog. for instance, @xcite found that syntactic priming was predictive of success on the hcrc map task @xcite . @xcite similarly discussed the use of syntactic similarity and overall linguistic style synchrony as an indicator of trust and cohesion in teamwork settings, and @xcite used syntactic similarity in modeling cognitive alignment. syntactic features have been shown to improve prediction performance in downstream tasks, e.g., authorship attribution @xcite @xcite and gender attribution @xcite . in each case, the studies found significant performance gains from models that included syntax features. despite interest in syntax and clear improvements in prediction performance, the vast majority of recent work primarily focuses on semantic, or even lexical similarities/differences. this ranges from traditional methods such as tfidf or jaccard similarity to modern approaches including bert embeddings @xcite @xcite and amr kernels @xcite . some approaches use syntactic features specific to certain domains such as twitter @xcite or web documents @xcite . other metrics include "syntactic elements" which take on various forms of parts-of-speech aggregation @xcite . a syntactic similarity metric should appropriately consider differences in syntactic structure at the word-, utterance-, and document-level, as opposed to aggregating parts-of-speech or relying on domain-specific features. to our knowledge, cas-sim is the only metric to do this and has been proposed as a solution in applications ranging from measuring communicative alignment @xcite to evaluating stylistic creativity in language learning @xcite to clustering text @xcite . however, cassim relies on the expensive edit distance metric, and occasionally assigns high similarity scores to documents that appear syntactically dissimilar. an improved syntactic similarity metric would afford new opportunities, from creating novel syntax feature vectors for classification tasks (e.g. authorship and gender attribution), to measuring syntactic coherence in machine translation. cassim @xcite was the first metric to compute syntactic similarity at the documentlevel. their original algorithm uses the stanford parser @xcite to compute the parse tree for each sentence in a pair of documents, before computing the edit distance @xcite between each parse tree pairing. then, they construct a bipartite graph and use the hungarian algorithm for minimum cost assignment @xcite to pair each tree in one document to the lowest distance tree in the second document. they finally average the edit distances of the minimal cost pairings. when there are different numbers of sentences, the number of assignments will correspond to the number of sentences in the document with fewer sentences. each of that document's sentences will get paired with the most similar sentence in the second document, and the least similar sentences in the second document will remain unpaired. the final edit distance between a pair of parse trees p 1 , p 2 is normalized as editdistance size(p 1 )+size(p 2 )- foot_1 , where size(p ) is the number of nodes in p . an important advantage of cassim is that it is generalizable to any corpus; it does not represent syntax using platform-specific features like alnajran (2019); @xcite . however, the cost of exhaustively using a metric such as edit distance is rather penalizing, as its implementations range in asymptotic time complexity from θ(mn) @xcite ) to o(s × min(m, n)) @xcite , where m and n are the string lengths, and s is the maximal edit distance. algorithm 2 delta lb function (∆ lb ) 1: tree nodes n 1 , n 2 ; cache 2: decay λ; subtree/subset tree indicator σ 3: if n 1 , n 2 is cached then ## evaluating fastkassim in this section, we first demonstrate fastkas-sim's overall ability to differentiate between simi-figure 4 : runtime comparison between fastkassim and cassim. on the cmv corpus, fastkassim runs 2.42 times to 5.32 times faster on average, depending on document size. lar and dissimilar documents. then, we correlate its scores with cassim and lsm. finally, we discuss fastkassim's advantages by explaining discrepancies in scoring. ## applications fastkassim is a more accurate and efficient syntactic similarity metric than the current state-of-theart, opening the possibility for investigating new hypotheses in data-heavy fields with large corpora. existing applications use syntax metrics for classification (e.g. posadas-duran et al. ( 2014 )) as well as analytically to measure hypotheses (e.g. @xcite ). here, we use syntax as a linguistic style indicator in authorship attribution, and measure syntactic similarity to study communication accommodation in persuasive arguments. ## conclusion we have introduced fastkassim, which has runtime improvements that scale significantly with document sizes and achieves better agreement with human perception of syntactic differences compared to standard syntax metrics. these improvements are possible due to our label-based tree kernel, which has an improved asymptotic runtime complexity and a corrected normalization. fastkassim also allowed us to verify hypotheses regarding the importance of syntax both in authorship attribution and social dynamics such as persuasion. these findings motivate further applications of syntax.