Abstract
Many tasks in natural language processing, ranging from machine translation to question answering, can be reduced to the problem of matching two sentences or more generally two short texts. We propose a new approach to the problem, called Deep Match Tree (DEEPMATCH$_{tree}$), under a general setting. The approach consists of two components: 1) a mining algorithm to discover patterns for matching two short-texts, defined in the product space of dependency trees, and 2) a deep neural network for matching short texts using the mined patterns, as well as a learning algorithm to build the network having a sparse structure. We test our algorithm on the problem of matching a tweet and a response in social media, a hard matching problem, and show that DEEPMATCH$_{tree}$ can outperform a number of competitor models including one without using dependency trees and one based on word-embedding, all with large margins.
Introduction
Matching short texts is a fundamental challenge in NLP, appearing in tasks like paraphrase identification, question answering, and automated dialogue. While modern embedding-based models are effective at finding word-level similarities, they often struggle with the structural nuances of language. For example, if someone says, "I have to work all night!", an appropriate response is "Have a good rest." A simple word-similarity model might fail here because "work" and "rest" are semantically distant or even opposites. To understand why they match, a system must recognize the structural relationship between the need for work and the necessity of rest. This paper bridges this gap by incorporating syntax—specifically dependency trees—into a deep learning framework.
Methodology: The DEEPMATCH$_{tree}$ Framework
The authors propose a three-stage pipeline to capture these structural interactions.
1. Direct Product of Graphs (PoG)
Instead of looking at sentences in isolation, the model represents the interaction between two sentences by taking the "direct product" of their dependency trees. This creates a complex graph where nodes represent pairs of words (one from each sentence) and edges represent shared grammatical relationships. This allows the model to explicitly model how the structure of a tweet interacts with the structure of a response.
2. Discriminative Pattern Mining and Abstraction
Because these product graphs are massive, an efficient mining algorithm is used to find "matching patterns"—specific sub-graphs that frequently appear in correctly matched pairs but rarely in mismatched ones. To improve generalization, the model employs Abstraction, which involves grouping similar words or identifying "Same Entities" (e.g., recognizing that "HK" in a question refers to the same entity as "HK" in a response).
3. Deep Matching Model
The mined patterns are converted into a sparse binary vector and fed into a Deep Neural Network (DNN). Given the high dimensionality of the input (often exceeding 10 million features), the framework utilizes a specialized "Architecture Learning" approach. This connects sparse input nodes to a dense hidden layer, enabling the network to learn complex, non-linear combinations of structural patterns.
Experimental Evaluation
The model was evaluated on two large-scale datasets from Weibo:
- DataOriginal: A dataset of 4.8 million (tweet, response) pairs. The task was to select the original response from 10 candidates (1v9 ranking).
- DataLabeled: A human-annotated dataset of 422 tweets with ~30 labeled responses each, testing performance in a retrieval-based conversation setting.
DEEPMATCH$_{tree}$ significantly outperformed several strong competitors, including standard translation models, word embeddings, and Convolutional Neural Networks (CNNs). In the 1v9 task, it achieved a 0.708 P@1 (Precision at 1), compared to 0.496 for a CNN-based model and 0.370 for a standard word-embedding model. On the human-labeled dataset, it achieved a 0.608 P@1, outperforming the baseline of 0.574.
Discussion and Conclusion
The success of DEEPMATCH$_{tree}$ highlights that syntax acts as a "skeleton" for meaning, exposing long-distance relationships that flat word sequences ignore. By prioritizing interaction-first modeling through the Direct Product of Graphs, the system captures semantic nuances that embedding-only models miss.
However, challenges remain. The model relies on mining millions of patterns, which incurs significant computational overhead. Furthermore, its performance is tied to the quality of the dependency parser; in informal social media settings, parsing errors can limit accuracy. Future work will involve testing the framework on other languages and refining the abstraction techniques to further improve robustness.
Summary updated