  Measuring Sentence Textual Similarity (STS) is a classic task that can be
applied to many downstream NLP applications such as text generation and
retrieval. In this paper, we focus on unsupervised STS that works on various
domains but only requires minimal data and computational resources.
Theoretically, we propose a light-weighted Expectation-Correction (EC)
formulation for STS computation. EC formulation unifies unsupervised STS
approaches including the cosine similarity of Additively Composed (AC) sentence
embeddings, Optimal Transport (OT), and Tree Kernels (TK). Moreover, we propose
the Recursive Optimal Transport Similarity (ROTS) algorithm to capture the
compositional phrase semantics by composing multiple recursive EC formulations.
ROTS finishes in linear time and is faster than its predecessors. ROTS is
empirically more effective and scalable than previous approaches. Extensive
experiments on 29 STS tasks under various settings show the clear advantage of
ROTS over existing approaches. Detailed ablation studies demonstrate the
effectiveness of our approaches.
