PaperlayerView exact revision on arXiv

Source-linked AI summary

Match-SRNN: Modeling the Recursive Matching Structure with Spatial RNN

Shengxian Wan, Yanyan Lan, Jun Xu, Jiafeng Guo, Liang Pang, Xueqi Cheng

arXiv:1604.04378v1cs.CLcs.AIcs.LGcs.NE

TL;DR

Semantic matching requires determining how well two texts correspond, while existing interaction mechanisms remain difficult to interpret. Match-SRNN models global interaction recursively with a tensor and spatial RNN, approximates LCS dynamics, and outperforms existing deep methods on semantic-matching tasks. The paper also visualizes the learned matching structure.

  • Problem

    Semantic matching must determine the matching degree between two texts, while existing methods lack a clear mechanism for generating complicated interactions.

  • Method

    Match-SRNN constructs word-level interactions with a neural tensor network, integrates them recursively with a gated spatial RNN, and scores the global interaction.

  • Results

    Match-SRNN approximates the dynamic-programming process of LCS and significantly outperforms existing deep learning methods on semantic-matching tasks.

  • Takeaways & Limitations

    The recursive structure provides an interpretable account of global interaction generation and supports visualization of learned matching paths.

  • Takeaways & Limitations

    The interaction representation uses a neural tensor network rather than a simpler similarity score such as cosine.

Abstract

from arXiv · show

Semantic matching, which aims to determine the matching degree between two texts, is a fundamental problem for many NLP applications. Recently, deep learning approach has been applied to this problem and significant improvements have been achieved. In this paper, we propose to view the generation of the global interaction between two texts as a recursive process: i.e. the interaction of two texts at each position is a composition of the interactions between their prefixes as well as the word level interaction at the current position. Based on this idea, we propose a novel deep architecture, namely Match-SRNN, to model the recursive matching structure. Firstly, a tensor is constructed to capture the word level interactions. Then a spatial RNN is applied to integrate the local interactions recursively, with importance determined by four types of gates. Finally, the matching score is calculated based on the global interaction. We show that, after degenerated to the exact matching scenario, Match-SRNN can approximate the dynamic programming process of longest common subsequence. Thus, there exists a clear interpretation for Match-SRNN. Our experiments on two semantic matching tasks showed the effectiveness of Match-SRNN, and its ability of visualizing the learned matching structure.

1 Introduction

Semantic matching must capture interactions between two texts despite vocabulary mismatch and limited interpretability in existing approaches. Match-SRNN models these interactions recursively, connects to LCS, and improves semantic-matching performance in experiments.

  • Semantic matching supports information retrieval, question answering, and paraphrase identification, but traditional exact-matching methods suffer from vocabulary mismatch.
  • Existing deep models address vocabulary mismatch but often represent texts independently or compose local interactions hierarchically, leaving interaction generation difficult to interpret.
  • Match-SRNN recursively composes prefix interactions with the current word-level interaction to model both nearby and long-distance dependencies.
  • Match-SRNN uses a similarity tensor, spatial RNN, gated factors, and a linear scorer to produce the global matching score.
  • Match-SRNN can approximate LCS dynamics and produce interpretable matching paths through gate backtracking.
  • Experiments on question answering and paper citation tasks showed significant improvement over existing deep models and visualized learned matching paths.

2 Related Work

Related semantic-matching methods either encode texts separately or directly model their interaction. The latter group commonly builds hierarchical matching structures, but the interaction-generation mechanism remains difficult to interpret.

  • Existing deep semantic-matching methods fall into two groups: separate text encoding and direct interaction modeling.
  • Separate-encoding methods compute matching from dense-vector similarity, but compact representations make complicated cross-text interactions difficult to model.
  • Direct-interaction methods integrate interaction representations to produce matching scores, often through hierarchical composition of local interactions.

3 The Recursive Matching Structure

The paper defines semantic matching recursively: each prefix interaction combines three smaller prefix interactions with the current word-level interaction, yielding an interpretable matching structure.

  • 3 The Recursive Matching Structure: The recursive formulation addresses the interpretability difficulty of existing semantic-matching methods by decomposing global interactions into recursively defined subproblems.The paper motivates recursion as a way to handle complicated matching mechanisms.
  • 3 The Recursive Matching Structure: Recursive Matching Structure defines the interaction between two prefixes as a composition of sub-prefix interactions and their current word-level interaction.For prefixes S1[1:i] and S2[1:j], the interaction h_ij combines three prefix interactions with s(w_i, v_j).
  • 3 The Recursive Matching Structure: For the example h34, the model combines h24, h33, h23, and the word-level interaction between “sat” and “balls”.The most important prefix interaction is h33, which compares the two prefixes ending at “sat” and “played”.

4 Match-SRNN

Match-SRNN constructs word-level interactions, integrates them with a gated spatial RNN, and converts the final global representation into a matching score.

  • 4 Match-SRNN: Match-SRNN has three components: a neural tensor network, a spatial RNN, and a linear scoring function.The tensor captures word-level interactions, the spatial RNN obtains the global interaction, and the linear function produces the final score.
  • 4.1 Neural Tensor Network: The neural tensor network represents each word as a distributed vector and maps each word pair to a vector of interactions.Its nonlinear function uses rectification, F(z) = max(0, z).
  • 4.2 Spatial RNN: Spatial RNN recursively combines representations from three neighboring prefix directions with the current word-level interaction.The model uses representations from (i−1,j), (i,j−1), and (i−1,j−1), matching the recursive structure.
  • 4.2 Spatial RNN: GRU gates control how information is propagated, reset, and combined across the spatial directions.Spatial GRU extends sequence GRU with four update gates and three reset gates.
  • 4.2 Spatial RNN: The final representation h_mn at the right-bottom corner summarizes the global interaction and is passed through a linear function to obtain the matching score.Different tasks use task-appropriate losses, including square loss for regression and hinge loss for ranking.
  • 4 Match-SRNN: All model parameters are jointly trained with backpropagation and stochastic gradient descent using AdaGrad.The jointly trained parameters include word embeddings, the neural tensor network, and the spatial RNN.

5 Discussion

Match-SRNN has a direct connection to the LCS dynamic-programming process: its recursive spatial computation can approximate LCS, and its gates recover the corresponding matching path.

  • LCS connection: LCS computes each prefix score from three neighboring prefix scores and the current word match.The recurrence uses c[i−1,j], c[i,j−1], c[i−1,j−1], and the match indicator for x_i and y_j.
  • LCS connection: After degeneration to exact matching, Match-SRNN uses a one-dimensional spatial GRU with disabled reset gates to accumulate past histories.The neural tensor is replaced by an indicator function, and the hidden dimension is set to 1.
  • LCS connection: The spatial-GRU terms correspond to the three LCS recurrence terms, while SoftmaxByRow gates approximate the recurrence’s max operation.The diagonal contribution can also approximate the addition of the previous diagonal score and the current match indicator.
  • Simulation results: Match-SRNN produces scores identical to LCS in simulation, revealing the relationship between the model and LCS.The simulation compares scores at each position for the two methods.
  • Simulation results: Backtracking the largest gates yields a path identical to dynamic programming, explaining how local interactions compose into the global interaction.At each position, the path follows the direction associated with the largest gate value.

6 Experiments

Experiments evaluate Match-SRNN on question answering and paper citation, showing strong performance against established baselines and visualizing learned matching interactions.

  • Effectiveness of Match-SRNN: The experiments evaluate Match-SRNN on question answering and paper citation tasks against deep models and BM25.The comparison includes ARC-I, ARC-II, CNTN, LSTM-RNN, MultiGranCNN, MV-LSTM, MatchPyramid, and a bidirectional variant.
  • Experimental setup: The QA task uses ranking metrics, while the paper-citation task is treated as binary classification evaluated by accuracy.QA uses P@1 and MRR; PC uses a softmax layer, cross-entropy training, and Acc.
  • Effectiveness of Match-SRNN: 36.4% improvement in QA P@1 over BM25 demonstrates Match-SRNN’s reported advantage over the strongest traditional baseline.The paper also reports a 3.1% improvement over MV-LSTM and at least 3.4% over ARC-II and MatchPyramid.
  • Effectiveness of Match-SRNN: Match-SRNN achieves the best results on the paper-citation task, although its improvements are smaller than on question answering.The authors attribute the smaller gains to the relative ease of the paper-citation task.
  • Effectiveness of Match-SRNN: The two matching paradigms have comparable reported results on QA: MV-LSTM reaches 0.766/0.869, while MatchPyramid reaches 0.764/0.867.These values are presented as the previous best results for dense-vector and interaction-based paradigms, respectively.
  • Visualization: A visualization shows that strong word-level matches strengthen surrounding interactions, with brightness representing interaction strength.The example highlights the bigram “memory, stick” and the keyword “error.”

7 Conclusions

The paper proposes Match-SRNN as a recursive architecture for semantic matching, connects it to LCS, and reports improved performance with visualized matching structure.

  • Conclusion: Match-SRNN models semantic matching recursively through word-level interactions, spatial-RNN global composition, and linear scoring.The architecture contains a neural tensor network, a spatial RNN, and a linear scoring function.
  • Conclusion: The analysis reveals an interesting connection between Match-SRNN and longest common subsequence.The paper also reports that experiments outperform existing deep learning methods and visualize the learned structure.
Loading 1604.04378v1…