Sentence Similarity Learning by Lexical Decomposition and Composition
Zhiguo Wang
Haitao Mi
Abraham Ittycheriah
IBM T.J. Watson Research Center
Yorktown Heights
NY
USA
{\tt \{zhigwang
hmi
abei\
Author 1
Address line
...
Address line % \And ... \And % Author n
Address line
...
Address line
Author 1
Address line
...
Address line % \AND % Author 2
Address line
...
Address line \And % Author 3
Address line
...
Address line
% come back to abs. latter. %Most previous methods assess the sentence similarity by focusing on the similar parts of a sentence pair, whereas the dissimilar parts did not get as much attention. Most conventional sentence similarity methods only focus on similar parts of two input sentences, and simply ignore the dissimilar parts, which usually give us some clues and semantic meanings about the sentences. In this work, we propose a model to take into account both the similarities and dissimilarities by decomposing and composing lexical semantics over sentences. The model represents each word as a vector, and calculates a semantic matching vector for each word based on all words in the other sentence. Then, each word vector is decomposed into a similar component and a dissimilar component based on the semantic matching vector. After this, a two-channel CNN model is employed to capture features by composing the similar and dissimilar components. Finally, a similarity score is estimated over the composed feature vectors. Experimental results show that our model gets the state-of-the-art performance on the answer sentence selection task, and achieves a comparable result on the paraphrase identification task.
main.tex
%
% File naaclhlt2016.tex
%

\documentclass[11pt,letterpaper]{article}
\usepackage{naaclhlt2016}
\usepackage{times}
\usepackage{latexsym}
\usepackage[english]{babel}

\usepackage{graphicx} % Required for including images
\graphicspath{{figures/}} % Directory in which figures are stored

\usepackage{amsmath} % for equation change new line
\newcommand{\argmax}{\operatornamewithlimits{argmax}}


\usepackage{booktabs}
\usepackage{multirow}
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}}

\naaclfinalcopy % Uncomment this line for the final submission
\def\naaclpaperid{***} %  Enter the naacl Paper ID here

% To expand the titlebox for more authors, uncomment
% below and set accordingly.
\addtolength\titlebox{-.35in}    

\newcommand\BibTeX{B{\sc ib}\TeX}


\title{Sentence Similarity Learning by Lexical Decomposition and Composition}

% Author information can be set in various styles:
% For several authors from the same institution:
 \author{Zhiguo Wang \and Haitao Mi \and Abraham Ittycheriah \\
          IBM T.J. Watson Research Center \\ Yorktown Heights, NY, USA \\ {\tt \{zhigwang, hmi, abei\}@us.ibm.com}}
% if the names do not fit well on one line use
%         Author 1 \\ {\bf Author 2} \\ ... \\ {\bf Author n} \\
% For authors from different institutions:
% \author{Author 1 \\ Address line \\  ... \\ Address line
%         \And  ... \And
%         Author n \\ Address line \\ ... \\ Address line}
% To start a seperate ``row'' of authors use \AND, as in
% \author{Author 1 \\ Address line \\  ... \\ Address line
%         \AND
%         Author 2 \\ Address line \\ ... \\ Address line \And
%         Author 3 \\ Address line \\ ... \\ Address line}
% If the title and author information does not fit in the area allocated,
% place \setlength\titlebox{<new height>} right after
% at the top, where <new height> can be something larger than 2.25in
\date{}
\begin{document}

\maketitle
%\vspace{-6cm}
\begin{abstract}
% come back to abs. latter.
%Most previous methods assess the sentence similarity by focusing on the similar parts of a sentence pair, whereas the dissimilar parts did not get as much attention. 
Most conventional sentence similarity methods only focus on similar parts of two input sentences,
and simply ignore the dissimilar parts, 
which usually give us some clues and semantic meanings about the sentences. 
In this work, we propose a model to take into account both the similarities and dissimilarities 
by decomposing and composing lexical semantics over sentences. 
The model represents each word as a vector, 
and calculates a semantic matching vector for each word based on all words in the other sentence. 
Then, each word vector is decomposed into a similar component and a dissimilar component based on the semantic matching vector. 
After this, a two-channel CNN model is employed to capture features 
by composing the similar and dissimilar components. 
Finally, a similarity score is estimated over the composed feature vectors. 
Experimental results 
show that 
our model gets the state-of-the-art performance on the answer sentence selection task, 
and achieves a comparable result on the paraphrase identification task.
\end{abstract}

\section{Introduction}
Sentence similarity is a fundamental metric to measure the degree of likelihood between a pair of sentences. 
It plays an important role for a variety of tasks in both NLP and IR communities. 
For example, in paraphrase identification task, 
sentence similarity is used to determine whether two sentences are paraphrase or not~\cite{yin2015convolutional,he2015multi}. 
For question answering and information retrieval tasks, 
sentence similarities between query-answer pairs are used for assessing the relevance 
and ranking all the candidate answers~\cite{severyn2015learning,wang2015faq}.

%TODO: the using of E_6 and E_7 come too late, we must merge them with E_1 and E_2.
\begin{table}[t]
\setlength{\tabcolsep}{0pt}
\hspace{-0.5cm}
\centering
\small
\begin{tabular}{l}
\hline
%$E_1$ The research is relevant to sockeye. \\ 
%$E_2$ The study is related to red salmon. \\ 
$E_1$ The research is [irrelevant] to sockeye. \\ 
$E_2$ The study is [not related] to salmon. \\ 
\hline \hline
$E_3$ The research is relevant to salmon. \\ 
$E_4$ The study is relevant to sockeye, $\langle$instead of coho$\rangle$. \\ 
$E_5$ The study is relevant to sockeye, $\langle$rather than flounder$\rangle$. \\ 
\hline
%$E_6$ The research is irrelevant to sockeye. \\ 
%$E_7$ The study is not relevant to salmon. \\ 
%\hline
\end{tabular}
%\vspace{0.5cm}
\caption{Examples for sentence similarity learning. 
``coho'' and ``sockeye'' are in the salmon family, while ``flounder'' is not.}
\label{tab:example}
\end{table}

However, sentence similarity learning %is a very challenging task. 
has following issues:
\begin{enumerate}
\item there is a lexical gap between semantically equivalent sentences. 
%For example, in Table \ref{tab:example}, 
%E1 has the similar meaning with E2, but they are represented with different words.  
Take the $E_1$ and $E_2$ in Table~\ref{tab:example} for example, 
they have the similar meaning but with different lexicons. 
\item semantic similarity should be measured at different levels of granularity (word-level, phrase-level and syntax-level). 
E.g., ``not related'' in $E_2$ is an indivisible phrase when matching with ``irrelevant'' in $E_1$ 
(shown in square brackets). 
% emphise the improtance of dissimilarity.
\item the dissimilarity (shown in angle brackets) between two sentences is also a significant clue 
\cite{qiu2006paraphrase}. 
For example, by judging the dissimilar parts, we can easily identify 
that $E_3$ and $E_5$ share the similar meaning ``The study is about salmon", because ``sockeye" belongs to the salmon family, and ``flounder" does not. 
Whereas the meaning of $E_4$ is quite different from $E_3$, which emphasizes ``The study is about red (a special kind of) salmon", because both ``sockeye" and ``coho" are in the salmon family.
How can we extract and utilize those information becomes another issue.
\end{enumerate}


In order to handle the issues above, researchers have been working on  sentence similarity algorithms for a long time.
%During the past decades, several methods were proposed to deal with these challenges. 
% simple word-embedding approach?
To bridge the lexical gap (issue 1), some word similarity metrics were proposed to 
match different but semantically related words. 
Examples include knowledge-based metrics~\cite{resnik1995using} 
and corpus-based metrics~\cite{jiang1997semantic,yin2015convolutional,he2015multi}. 
To measure sentence similarity from various granularities (issue 2), 
researchers have explored features extracted from $n$-grams, continuous phrases, 
discontinuous phrases, and parse trees~\cite{yin2015convolutional,he2015multi,heilman2010tree}. 
%However, most approaches only focused on the similarity of shared contents, and the clues from dissimilar parts are rarely emphasized. \newcite{qiu2006paraphrase} is the only work to explore the dissimilarity, but the performance is below the state of the art.
The third issue did not get much attention in the past, 
the only related work of \newcite{qiu2006paraphrase} 
explored the dissimilarity between sentences in a pair for paraphrase identification task, 
but they require human annotations in order to train a classifer,
and their performance is still below the state of the art.


%\newcite{qiu2006paraphrase} is the only work to explore the dissimilarity for paraphrase identification task. They trained a classifier to classify the dissimilar parts of two sentences into two categories: significant and non-significant. If the dissimilar parts are significant, the two sentences are not paraphrase of each other, otherwise they are paraphrase.

In this paper, we propose a novel model to tackle all these challenges jointly 
by decomposing and composing lexical semantics over sentences. 
Given a sentence pair, the model represents each word as a low-dimensional vector (issue 1), 
and calculates a semantic matching vector for each word based on all words in the other sentence (issue 2). 
Then based on the semantic matching vector, each word vector is decomposed into two components: 
a similar component and a dissimilar component (issue 3). 
We use similar components of all the words to represent the similar parts of the sentence pair, 
and dissimilar components of every word to model the dissimilar parts explicitly. 
After this, a two-channel CNN operation is performed to compose the similar and dissimilar components into a feature vector (issues 2 and 3). 
Finally, the composed feature vector is utilized to predict the sentence similarity. 
%We evaluated our model on both the answer sentence selection and the paraphrase identification tasks. 
Experimental results on two tasks show that 
our model the state-of-the-art performance on the answer sentence selection task, 
and achieves a comparable result on the paraphrase identification task.

%The remainder of this paper is organized as follows: Section 2 gives an overview of our model. Section 3 describes an end-to-end implementation of the model. We discuss and analyze our experimental results in Section 4. Section 5 discusses related work. Finally, we conclude this paper in Section 6.
In following parts, we start with a brief overview of our model (Section~\ref{sec:overview}), 
followed by the details of our end-to-end implementation (Section~\ref{sec:details}).
Then we evaluate our model on answer sentence selection 
and paraphrase identifications tasks (Section~\ref{sec:exps}).

\section{Model Overview}
\label{sec:overview}

%Given a pair of sentence, our task is to assess a similarity score for them. As already mentioned, there are several challenges for this task. We propose a model to tackle all these challenges in one shot by decomposing and composing lexical semantics.

%Figure \ref{fig:model-overall} illustrates an overview of our model. Given a pair of sentences $S$ and $T$, our model calculates a similarity $sim(S,T)$ through the following phases:

Figure~\ref{fig:model-overall} shows an overview of our sentence similarity model.
Given a pair of sentences $S$ and $T$, our task is to calculate a similarity score $sim(S,T)$ 
in following steps:

% refine the flow chart
\begin{figure}[tbp]
\begin{center}
\includegraphics[width=0.5\textwidth]{overall.pdf}
\end{center}
\caption{Model overview.}
\label{fig:model-overall}
\end{figure}

\textbf{Word Representation}. 
%The lexical gap makes the traditional lexical matching methods less effective, 
%because different but semantically related words cannot be matched. % and influence the final similarity score. 
%An effective solution is to map each word into a semantic space. 
Word embedding of \newcite{mikolov2013efficient} is an effective way to 
handle the lexical gap issue in the sentence similarity task,
as it represents each word with a distributed vector, 
%In our model, we represent each word with a distributional vector, 
%which is acquired from a corpus based on the assumption that 
and words appearing in similar contexts tend to have similar meanings~\cite{mikolov2013efficient}. 
With those pre-trained embeddings, we transform $S$ and $T$ into sentence matrixes 
$S=[s_1,...,s_i,...,s_m]$ and $T=[t_1,...,t_j,...,t_n]$, 
where $s_i$ and $t_j$ are \emph{d}-dimension vectors of the corresponding words, 
and $m$ and $n$ are sentence length of $S$ and $T$ respectively.

\textbf{Semantic Matching}. In order to judge the similarity between two sentences, 
we need to check whether each semantic unit in one sentence is covered by the other sentence, or vice versa.
For example, in Table~\ref{tab:example}, to check whether $E_2$ is a paraphrase of $E_1$, 
we need to know the single word ``irrelevant'' in $E_1$ is matched or covered
by the phrase ``not related'' in $E_2$. 
In our model, we treat each word as a primitive semantic unit,  
and calculate a semantic matching vector $\hat{s_i}$ for each word $s_i$ by composing part or full word vectors in the other sentence $T$.
In this way, we can match a word $s_i$ to a word or phrase in $T$. 
Similarly, for the reverse direction, 
we also calculate all semantic matching vectors $\hat{t_j}$ in $T$. %with function $f_{match}$:
% for each word $t_j \in T$ based on word vectors in $S$. 
%Formally, we equip this phase with the following equations:
\begin{equation}
\begin{split}
\hat{s_i} = f_{match}(s_i, T) \hspace{10mm} \forall s_i \in S \\
\hat{t_j} = f_{match}(t_j, S) \hspace{10mm} \forall t_j \in T
\end{split}
\label{equ:match}
\end{equation}
We explore different $f_{match}$ functions latter in Section~\ref{sec:details}.

\textbf{Decomposition}. 
After the semantic matching phase, 
%each word $s_i$ (or $t_j$) acquired a matching vector $\hat{s_i}$ (or $\hat{t_j}$). 
we have the semantic matching vectors of $\hat{s_i}$ and $\hat{t_j}$.
We interpret $\hat{s_i}$ (or $\hat{t_j}$) as %an abstraction of the semantic coverage
a semantic coverage of word $s_i$ (or $t_j$) by the sentence $T$ (or $S$).
%to cover the semantics of word $s_i$ (or $t_j$). 
However, it is not necessary that 
all the semantics of $s_i$ (or $t_j$) are fully covered by $\hat{s_i}$ (or $\hat{t_j}$). 
Take the $E_1$ and $E_2$ in Table~\ref{tab:example} for example, 
the word ``sockeye'' in $E_1$ is only partially matched by the word ``salmon'' (the similar part) in $E_2$, 
as the full meaning of ``sockeye'' is ``red salmon'' (the semantic meaning of ``red'' is the dissimilar part). 
%% still don't get it. (E_3 and E_4 will be easier?)
%% similar: salmon
%% dissimilar: red ? 
%% what's the relationship: sockeye <--> red?
Motivated by this phenomenon, 
our model further decomposes word $s_i$ (or $t_j$), based on its semantic matching vector $\hat{s_i}$ (or $\hat{t_j}$), 
into two components: similar component $s_i^+$ (or $t_j^+$) and dissimilar component $s_i^-$ (or $t_j^-$). 
Formally, we define the decomposition function as:
\begin{equation}
\begin{split}
[s_i^+;s_i^-] = f_{decomp}(s_i, \hat{s_i}) \hspace{10mm} \forall s_i \in S \\
[t_j^+;t_j^-] = f_{decomp}(t_j, \hat{t_j}) \hspace{10mm} \forall t_j \in T
\end{split}
\label{equ:decomp}
\end{equation}

\textbf{Composition}. 
%As shown in Figure \ref{fig:model-overall}, a sentence matrix $S$ (or $T$) is decomposed 
%into two matrixes after the decomposition phase: 
Given a similar component matrix $S^+=[s_1^+, ..., s_m^+]$ (or $T^+=[t_1^+,...,t_n^+]$) 
and a dissimilar component matrix $S^-=[s_1^-, ..., s_m^-]$ (or $T^-=[t_1^-,...,t_n^-]$),
our goal in this step is how to utilize those information.
Besides the suggestion from \newcite{qiu2006paraphrase} %revealed that 
that the significance of the dissimilar parts alone between two sentences has a great effect of their similarity,
we also think that the dissimilar and similar components % is also affected by the similar component. 
have strong connections.
For example, in Table \ref{tab:example}, 
if we only look at the dissimilar or similar part alone, 
it is hard to judge which one between $E_4$ and $E_5$ is more similar to $E_3$.
%But when considering the similar and dissimilar parts together, 
We can easily identify that $E_5$ is more similar to $E_3$, when we consider both the similar and dissimilar parts. 
Therefore, %the similar component and dissimilar component 
%should interact with each other to assess the sentence similarity. 
our model composes the similar component matrix and dissimilar component matrix 
into a feature vector $\vec{S}$ (or $\vec{T}$) with the composition function:
\begin{equation}
\begin{split}
\vec{S} = f_{comp}(S^+, S^-) \\
\vec{T} = f_{comp}(T^+, T^-)
\end{split}
\label{equ:comp}
\end{equation}

\textbf{Similarity assessing}. 
In the final stage, %composition phase, we get two feature vectors $\vec{S}$ and $\vec{T}$, which imply interactive information from the similar and dissimilar components. 
we concatenate the two feature vectors ($\vec{S}$ and $\vec{T}$) and predict the final similarity score:
\begin{equation}
sim(S,T) = f_{sim}(\vec{S}, \vec{T})
\label{equ:sim}
\end{equation}


\section{An End-to-End Implementation}
\label{sec:details}
Section~\ref{sec:overview} gives us a glance of our model. 
In this section, we describe details of each phase.

\subsection{Semantic Matching Functions}
\label{subsec:wordmatch}
This subsection describes our specifications for the semantic matching function $f_{match}$ in Eq. (\ref{equ:match}). 
The goal of $f_{match}$ is to generate a semantic matching vector $\hat{s_i}$ for $s_i$ by composing the vectors from $T$. 

For a sentence pair $S$ and $T$, we first calculate a similarity matrix $A_{m\times n}$,
where each element $a_{i,j} \in A_{m\times n}$ computes the cosine similarity 
between words $s_i$ and $t_j$ as
\begin{equation}
a_{i,j}= \frac{s_i^Tt_j}{\|s_i\|\cdot\|t_j\|} \hspace{10mm} \forall s_i \in S, \forall t_j \in T.
\label{equ:cosine}
\end{equation}
%with Eq. (\ref{equ:cosine}). 
Then, %based on the similarity matrix, 
we define three different semantic matching functions %in Eq.~(\ref{equ:match2}) 
over $A_{m \times n}$: 
%\emph{global}, \emph{max} and \emph{local-l}.
\begin{equation}
f_{match}(s_i, T)=
\begin{cases}
%\begin{align}
\frac{\sum_{j=0}^n a_{i,j}t_j} {\sum_{j=0}^n a_{i,j}} &\emph{global}\\
\frac{\sum_{j=k-w}^{k+w} a_{i,j}t_j} {\sum_{j=k-w}^{k+w} a_{i,j}} &\emph{local-w}\\
t_k &\emph{max}\\
%\end{align}
\end{cases}
%\hspace{10mm} k=\argmax_j a_{i,j}
\label{equ:match2}
\end{equation}
where $k=\argmax_j a_{i,j}$.
%Eq. (\ref{equ:match2}) lists all the three specifications. 
The idea of the \emph{global} function is to consider all word vectors $t_j$ in $T$. %for matching each word $s_i$. 
A semantic matching vector $\hat{s_i}$ is a weighted sum vector of all words $t_j$ in $T$,
where each weight is the normalized word similarity $a_{i, j}$.
%It computes the matching vector $\hat{s_i}$ %by the weighed average of %all the word vectors, 
%and the weight of each word vector $t_j$ is the word similarity $a_{i,j}$. 
The \emph{max} function moves to the other extreme. 
It generates the semantic matching vector by selecting the most similar word vector $t_k$ from $T$.
The \emph{local-w} function takes a compromise between \emph{global} and \emph{max}, 
where $w$ indicates the size of the window to consider centered at $k$ (the most similar word position).
%It first selects the most similar word position $k$, 
%and calculates the matching vector by the weighted average of a window size of $2l+1$ words around the $k$-th word.
So the semantic matching vector is a weighted average vector from $t_{k-w}$ to $t_{k+w}$. 

% \begin{equation}
% k=\argmax_j a_{i,j}
% \label{equ:align}
% \end{equation}

\subsection{Decomposition Functions}
This subsection describes the implementations for the decomposition function $f_{decomp}$ in Eq. (\ref{equ:decomp}). 
The intention of $f_{decomp}$ is to decompose a word vector $s_j$ based on its semantic matching vector $\hat{s_j}$ 
into a similar component $s_i^+$ and a dissimilar component $s_i^-$, 
where $s_i^+$ indicates the semantics of $s_i$ covered by $\hat{s_i}$ 
and $s_i^-$ indicates the uncovered part. 
We implement three types of decomposition function: \emph{rigid}, \emph{linear} and \emph{orthogonal}.

The \emph{rigid} decomposition only adapts to the \emph{max} version of $f_{match}$. 
First, it detects whether there is an exactly matched word in the other sentence, or $s_i$ equal to $\hat{s_i}$. 
If yes, the vector $s_i$ is dispatched to the similar component $s_i^+$, 
and the dissimilar component is assigned with a zero vector \textbf{0}. 
Otherwise, the vector $s_i$ is assigned to the dissimilar component $s_i^-$. 
Eq. ({\ref{equ:rigid}}) gives the formal definition:
\begin{equation}
\begin{split}
[s_i^+ = s_i; \ s_i^- = \textbf{0}] \hspace{10mm} & if \ s_i = \hat{s_i}\\
[s_i^+ = \textbf{0}; \ s_i^- = s_i] \hspace{10mm} & otherwise \\
\end{split}
\label{equ:rigid}
\end{equation}

The motivation for the \emph{linear} decomposition is that the more similar between $s_i$ and $\hat{s_i}$, 
the higher proportion of $s_i$ should be assigned to the similar component.
First, we calculate the cosine similarity $\alpha$ between $s_i$ and $\hat{s_i}$. 
Then, we decompose $s_i$ linearly based on $\alpha$. 
Eq. (\ref{equ:linear}) gives the corresponding definition:

\begin{equation}
\begin{split}
&\alpha = \frac{s_i^T\hat{s_i}}{\|s_i\|\cdot\|\hat{s_i}\|} \\
&s_i^+ = \alpha s_i \\
&s_i^- = (1-\alpha) s_i \\
\end{split}
\label{equ:linear}
\end{equation}

The \emph{orthogonal} decomposition is to decompose a vector in the geometric space. 
Based on the semantic matching vector $\hat{s_i}$, our model decomposes $s_i$ into a parallel component 
and a perpendicular component. 
Then, the parallel component is viewed as the similar component $s_i^+$, 
and perpendicular component is taken as the dissimilar component $s_i^-$. 
Eq. ({\ref{equ:orthogonal}}) gives the concrete definitions.
\begin{equation}
\begin{split}
&s_i^+ = \frac{s_i \cdot \hat{s_i}} {\hat{s_i} \cdot \hat{s_i}} \hat{s_i} \hspace{10mm} parallel \\
&s_i^- = s_i - s_i^+ \hspace{10mm} perpendicular \\
\end{split}
\label{equ:orthogonal}
\end{equation}

\subsection{Composition Functions}
The aim of the composition function $f_{comp}$ in Eq. (\ref{equ:comp})
is to extract features from both the similar component matrix and the dissimilar component matrix. 
We also want to acquire similarities and dissimilarities of various granularity during the composition phase. 
Inspired from \newcite{kim2014convolutional}, we utilize a two-channel convolutional neural networks (CNN) 
and design filters based on various order of $n$-grams, e.g., unigram, bigram and trigram.

The CNN model involves two sequential operations: 
\emph{convolution} and \emph{max-pooling}. 
For the \emph{convolution} operation, we define a list of filters \{\textbf{$w_o$}\}. 
The shape of each filter is $d\times h$, where $d$ is the dimension of word vectors and $h$ is the window size. 
Each filter is applied to two patches (a window size $h$ of vectors) from both similar and dissimilar channels, 
and generates a feature. Eq. (\ref{equ:convolution}) expresses this process.

\begin{equation}
c_{o,i} = f(w_o\ast S^+_{[i:i+h]}+w_o\ast S^-_{[i:i+h]}+b_o)
\label{equ:convolution}
\end{equation}
where the operation $A \ast B$ sums up all elements in $B$ with the corresponding weights in $A$, $S^+_{[i:i+h]}$ 
and $S^-_{[i:i+h]}$ indicate the patches from $S^+$ and $S^-$, $b_o$ is a bias term 
and $f$ is a non-linear function (we use \emph{tanh} in this work). 
We apply this filter to all possible patches, and produce a series of features 
$\vec{c_o}=[c_{o,1}, c_{o,2},...,c_{o,O}]$. 
The number of features in $\vec{c_o}$ depends on the shape of the filter $w_o$ and the length of the input sentence. 
To deal with variable feature size, 
we perform a \emph{max-pooling} operation over $\vec{c_o}$ by selecting the maximum value $c_o=max \ \vec{c_o}$. 
Therefore, after these two operations, each filter generates only one feature. 
We define several filters by varying the window size and the initial values. 
Eventually, a vector of features is captured by composing the two component matrixes, 
and the feature dimension is equal to the number of filters.

\subsection{Similarity Assessment Function}
The similarity assessment function $f_{sim}$ in Eq. (\ref{equ:sim}) 
predicts a similarity score by taking two feature vectors as input. 
We employ a linear function to sum up all the features and apply a \emph{sigmoid} function 
to constrain the similarity within the range [0, 1]. 

\subsection{Training}
%So far, we have described all the mathematical expressions for the sentence similarity model. To assess a reasonable similarity score for each sentence pair, 
We train our sentence similariy model by maximizing the likelihood on a training set. 
Each training instance in the training set is represented as a triple ($S_i$, $T_i$, $L_i$), 
where $S_i$ and $T_i$ are a pair of sentences, and $L_i \in \{0,1\}$ indicates the similarity between them. 
We assign $L_i=1$ if $T_i$ is a paraphrase of $S_i$ for the paraphrase identification task, 
or $T_i$ is a correct answer for $S_i$ for the answer sentence selection task. 
Otherwise, we assign $L_i=0$. 
We implement the mathematical expressions with Theano~\cite{Bastien-Theano-2012} 
and use Adam~\cite{kingma2014adam} for optimization.

\section{Experiment}
\label{sec:exps}
\subsection{Experimental Setting}
We evaluate our model on two tasks: answer sentence selection and paraphrase identification. The answer sentence selection task is to rank a list of candidate answers based on their similarities to a question sentence, and the performance is measured by mean average precision (MAP) and mean reciprocal rank (MRR). We experiment on two datasets: \emph{QASent} and \emph{WikiQA}. Table \ref{tab:qa-statistics} summarises the statistics of the two datasets, where \emph{QASent} \cite{wang2007jeopardy} was created from the TREC QA track, and \emph{WikiQA} \cite{yang2015wikiqa} is constructed from real queries of Bing and Wikipedia. The paraphrase identification task is to detect whether two sentences are paraphrases based on the similarity between them. The metrics include the accuracy and the positive class $F_1$ score. We experiment on the Microsoft Research Paraphrase corpus (MSRP) \cite{dolan2004unsupervised}, which includes 2753 true and 1323 false instances in the training set, and 1147 true and 578 false instances in the test set. We build a development set by randomly selecting 100 true and 100 false instances from the training set. In all experiments, we set the size of word vector dimension as $d=$300, and pre-train the vectors with the \emph{word2vec} toolkit \cite{mikolov2013efficient} on the English Gigaword (LDC2011T07).

\begin{table}[tbp]
\centering
\begin{tabular}{c|crr}
    \toprule
    & Set   & Questions & QA Pairs \\
    \midrule
    \multirow{3}{*}{QASent} & train & 1,229     & 53,417  \\
                        & dev   & 65        & 1,117   \\
                        & test  & 68       & 1,442   \\
    \midrule
    \multirow{3}{*}{WikiQA} & train & 2,118     & 20,360     \\
                        & dev   & 296       & 2,733   \\
                        & test  & 633       & 6,165   \\ 
    \bottomrule
\end{tabular}
\caption{Statistics of answer sentence selection data sets.}
\label{tab:qa-statistics}
\end{table}

\subsection{Model Properties}
There are several alternative options in our model, e.g., the semantic matching functions, the decomposition operations, and the filter types. The choice of these options may affect the final performance. In this subsection, we present some experiments to demonstrate the properties of our model, and find a good configuration that we use to evaluate our final model. All the experiments in this subsection were performed on the \emph{QASent} dataset and evaluated on the development set.

First, we evaluated the effectiveness of various semantic matching functions. We switched the semantic matching functions among \{\emph{max}, \emph{global}, \emph{local-l}\}, where $l \in$ \{1, 2, 3, 4\}, and fixed the other options as: the \emph{linear} decomposition, the filter types including \{unigram, bigram, trigram\}, and 500 filters for each type. Figure \ref{fig:alignment-types} presents the results. We found that the \emph{max} function worked better than the \emph{global} function on both MAP and MRR. By increasing the window size, the \emph{local-l} function acquired progressive improvements when the window size is smaller than 4. But after we enlarged the window size to 4, the performance dropped. The \emph{local-3} function worked better than the \emph{max} function in term of the MAP, and also got a comparable MRR. Therefore, we use the \emph{local-3} function in the following experiments.

\begin{figure}[tbp]
\begin{center}
\includegraphics[width=0.5\textwidth]{alignment-figure.pdf}
\end{center}
\caption{Influence of semantic matching functions.}
\label{fig:alignment-types}
\end{figure}

Second, we studied the effect of various decomposition operations. We varied the decomposition operation among \{\emph{rigid}, \emph{linear}, \emph{orthogonal}\}, and kept the other options unchanged. Figure \ref{fig:decomposition-types} shows the performance. We found that the \emph{rigid} operation got the worst result. This is reasonable, because the \emph{rigid} operation decomposes word vectors by exactly matching words. The \emph{orthogonal} operation got a similar MAP as the \emph{linear} operation, and it worked better in term of MRR. Therefore, we choose the \emph{orthogonal} operation in the following experiments. 

\begin{figure}[tbp]
\begin{center}
\includegraphics[width=0.5\textwidth]{decomposition-figure.pdf}
\end{center}
\caption{Influence of decomposition functions.}
\label{fig:decomposition-types}
\end{figure}

Third, we tested the influence of various filter types. We constructed 5 groups of filters: \emph{win-1} contains only the unigram filters, \emph{win-2} contains both unigram and bigram filters, \emph{win-3} contains all the filters in \emph{win-2} plus trigram filters, \emph{win-4} extends filters in \emph{win-3} with 4-gram filters, and \emph{win-5} adds 5-gram filters into \emph{win-4}. We generate 500 filters for each filter type (with different initial values). Experimental results are shown in Figure \ref{fig:filter-types}. At the beginning, adding higher-order ngram filters was helpful for the performance. The performance reached to the peak, when we used the \emph{win-3} filters. After that, adding more complex filters decreased the performance. Therefore, the trigram is the best granularity for our model. In the following experiments, we utilize filter types in \emph{win-3}.

\begin{figure}[tbp]
\begin{center}
\includegraphics[width=0.5\textwidth]{filter-type-figure.pdf}
\end{center}
\caption{Influence of filter types in the composition function.}
\label{fig:filter-types}
\end{figure}

%Fourth, we checked the effect of the number of filters (for each filter type). We varied the number of filters among \{50, 100, 300, 500, 800, 1000, 1500, 2000\}. Figure \ref{fig:filter-nums} describes the trend. The best MRR and MAP occurred at 500. Therefore, in the following experiments, we generate 500 filters for each filter type.
\iffalse
\begin{figure}[tbp]
\begin{center}
\includegraphics[width=0.45\textwidth]{num-filter-figure.pdf}
\end{center}
\caption{Influence of the number of filters.}
\label{fig:filter-nums}
\end{figure}
\fi

\subsection{Comparing with State-of-the-art Models}
In this subsection, we evaluated our model on the test sets of \emph{QASent}, \emph{WikiQA} and \emph{MSRP}.

\textbf{\emph{QASent} dataset.}  Table \ref{tab:qasent} presents the performances of the state-of-the-art systems and our model, where the performances were evaluated with the standard trec\_eval-8.0 script \footnote{http://trec.nist.gov/trec\_eval/}. Given a pair of sentences, \newcite{severyn2015learning} employed a CNN model to compose each sentence into a vector separately, and joined  the two sentence vectors to compute the sentence similarity. Because only the sentence-level granularity was used, the performance is much lower (the second row of Table \ref{tab:qasent}). After adding some word overlap features between the two sentences, the performance was improved significantly (the third row of Table \ref{tab:qasent}). Therefore, the lower-level granularity is an indispensable factor for a good performance. \newcite{wang2015faq} conducted word alignment for a sentence pair based on word vectors, and measured the sentence similarity based on a couple of word alignment features. They got a slightly better performance (the fourth row of Table \ref{tab:qasent}), which indicates that the vector representation for words is helpful to bridging the lexical gap problem. Our model makes use of all these useful factors and also considers the dissimilarities of a sentence pair. We can see that our model got a significantly better performance than all the other work (the last row).


\begin{table}[tbp]
\centering
\begin{tabular}{l|cc}
    \toprule
    Models & MAP    & MRR    \\
    \midrule
    \begin{tabular}[c]{@{}l@{}}\newcite{severyn2015learning} \\ (CNN only)\end{tabular}              & 0.6709 & 0.7280 \\
    \midrule
    \begin{tabular}[c]{@{}l@{}}\newcite{severyn2015learning}\\  (CNN + sparse features)\end{tabular} & 0.7459 & 0.8078 \\
    \midrule
    \newcite{wang2015faq} & 0.7460 & 0.8200 \\
    \midrule
    \midrule
    This work & \textbf{0.7714} & \textbf{0.8447} \\
    \bottomrule
\end{tabular}
\caption{Experimental results on the QASent dataset from the state-of-the-art models and our proposed model.}
\label{tab:qasent}
\end{table}

\textbf{\emph{WikiQA} dataset.} Table \ref{tab:wikiqa} presents the results of our model and several state-of-the-art models. \newcite{yang2015wikiqa} constructed the dataset and reimplemented several baseline models. The best performance (shown at the second row of Table \ref{tab:wikiqa}) was acquired by a bigram CNN model combining with the word overlap features. \newcite{miao2015neural} models the sentence similarity by enriching LSTMs with a latent stochastic attention mechanism. The corresponding performance is given at the third row of Table \ref{tab:wikiqa}. \newcite{yin2015abcnn} introduced the attention mechanism into the CNN model, and captured the best performance (the fourth row of Table \ref{tab:wikiqa}). The semantic matching phase in our model is similar to the attention mechanism. But different from the previous models, our model  utilizes both the similarity and dissimilarity simultaneously. The last row of Table \ref{tab:wikiqa} shows that our model is more effective than the other models.

\begin{table}[tbp]
\centering
\begin{tabular}{l|cc}
\toprule
Models            & MAP    & MRR    \\
    \midrule
    \begin{tabular}[c]{@{}l@{}}\newcite{yang2015wikiqa} \\ (2-gram CNN)\end{tabular} & 0.6520 & 0.6652 \\
    \midrule
    \begin{tabular}[c]{@{}l@{}}\newcite{miao2015neural} \\ (Attention-based LSTM)\end{tabular} & 0.6886 & 0.7069 \\
    \midrule
    \begin{tabular}[c]{@{}l@{}}\newcite{yin2015abcnn} \\ (Attention-based CNN)\end{tabular} &  0.6921 & 0.7108 \\
    \midrule
    \midrule
This work & \textbf{0.7058} & \textbf{0.7226} \\
    \bottomrule
\end{tabular}
\caption{Experimental results on the WikiQA dataset from the state-of-the-art models and our proposed model.}
\label{tab:wikiqa}
\end{table}


\textbf{\emph{MSRP} dataset.} Table \ref{tab:paraphrase} summarized the results from our model and several state-of-the-art models. \newcite{yin2015convolutional} employed a CNN model to learn sentence representations on multiple level of granularity and modeled interaction features at each level for a pair of sentences. They obtained their best performance by pretraining the model on a language modeling task (the 3rd row of Table  \ref{tab:paraphrase}). However, their model heavily depends on the pretraining strategy. Without pretraining, they got a much worse performance (the second row of Table  \ref{tab:paraphrase}). \newcite{he2015multi} proposed a similar model to \newcite{yin2015convolutional}. Similarly, they also used a CNN model to extract features at multiple levels of granularity. Differently, they utilized some extra annotated resources, e.g., embeddings from part-of-speech (POS) tags and PARAGRAM vectors trained from the Paraphrase Database \cite{ganitkevitch2013ppdb}. Their model outperformed \newcite{yin2015convolutional} without the need of pretraining (the sixth row of Table \ref{tab:paraphrase}). However, the performance was reduced after removing the extra resources (the fourth and fifth rows of Table \ref{tab:paraphrase}). \newcite{yin2015abcnn} applied their attention-based CNN model on this dataset. By adding a couple of sparse features and using a layerwise training strategy, they got a pretty good performance. Comparing to these neural network based models, our model obtained a comparable performance (the last row of Table \ref{tab:paraphrase}) without using any sparse features, extra annotated resources and specific training strategies. However, the best performance so far on this dataset is obtained by \newcite{ji2013discriminative}. In their model, they just utilized several hand-crafted features in a Support Vector Machine (SVM) model. Therefore, the deep learning methods still have a long way to go for this task.

\begin{table}[tbp]
\centering
\begin{tabular}{l|cc}
\toprule
Models & Acc  & F1    \\
\midrule
\begin{tabular}[c]{@{}l@{}} \newcite{yin2015convolutional} \\ (without pretraining)\end{tabular} & 72.5 & 81.4  \\
\midrule
\begin{tabular}[c]{@{}l@{}} \newcite{yin2015convolutional} \\ (with pretraining)\end{tabular} & 78.4 & 84.6  \\
\midrule
\begin{tabular}[c]{@{}l@{}} \newcite{he2015multi} \\ (without POS embeddings)\end{tabular} & 77.8 & N/A   \\
\midrule
\begin{tabular}[c]{@{}l@{}}\newcite{he2015multi}\\ (without Para. embeddings)\end{tabular} & 77.3 & N/A   \\
\midrule
\begin{tabular}[c]{@{}l@{}}\newcite{he2015multi}\\ (POS and Para. embeddings)\end{tabular} & 78.6 & 84.7 \\
\midrule
\begin{tabular}[c]{@{}l@{}} \newcite{yin2015abcnn} \\ (with sparse features)\end{tabular} & 78.9 & 84.8  \\
\midrule
\newcite{ji2013discriminative} & \textbf{80.4} & \textbf{86.0}  \\
\midrule
\midrule
This work & 78.4 & 84.7 \\
\bottomrule
\end{tabular}
\caption{Experimental results for paraphrase identification on MSRP corpus.}
\label{tab:paraphrase}
\end{table}
\section{Related Work}
The semantic matching functions in subsection~\ref{subsec:wordmatch} are inspired from the attention-based neural machine translation \cite{bahdanau2014neural,luong2015effective}. However, most of the previous work using the attention mechanism in only LSTM models. Whereas our model introduces the attention mechanism into the CNN model. A similar work is the attention-based CNN model proposed by \newcite{yin2015abcnn}. They first build an attention matrix for a sentence pair, and then directly take the attention matrix as a new channel of the CNN model. Differently, our model uses the attention matrix (or similarity matrix) to decompose the original sentence matrix into a similar component matrix and a dissimilar component matrix, and then feeds these two matrixes into a two-channel CNN model. The model can then focus much on the interactions between similar and dissimilar parts of a sentence pair.

\section{Conclusion}
In this work, we proposed a model to assess sentence similarity by decomposing and composing lexical semantics. To bridge the lexical gap problem, our model represents each word with its context vector. To extract features from both the similarity and dissimilarity of a sentence pair, we designed several methods to decompose the word vector into a similar component and a dissimilar component. To extract features at multiple levels of granularity, we employed a two-channel CNN model and equipped it with multiple types of ngram filters. Experimental results show that our model is quite effective on both the answer sentence selection task and the paraphrase identification task .
\section*{Acknowledgments}


% include your own bib file like this:
\bibliographystyle{naaclhlt2016}
\bibliography{qa}

\end{document}

main.bbl
\begin{thebibliography}{}

\bibitem[\protect\citename{Bahdanau \bgroup et al.\egroup
  }2014]{bahdanau2014neural}
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.
\newblock 2014.
\newblock Neural machine translation by jointly learning to align and
  translate.
\newblock {\em arXiv preprint arXiv:1409.0473}.

\bibitem[\protect\citename{Bastien \bgroup et al.\egroup
  }2012]{Bastien-Theano-2012}
Fr{\'{e}}d{\'{e}}ric Bastien, Pascal Lamblin, Razvan Pascanu, James Bergstra,
  Ian~J. Goodfellow, Arnaud Bergeron, Nicolas Bouchard, and Yoshua Bengio.
\newblock 2012.
\newblock Theano: new features and speed improvements.
\newblock Deep Learning and Unsupervised Feature Learning NIPS 2012 Workshop.

\bibitem[\protect\citename{Dolan \bgroup et al.\egroup
  }2004]{dolan2004unsupervised}
Bill Dolan, Chris Quirk, and Chris Brockett.
\newblock 2004.
\newblock Unsupervised construction of large paraphrase corpora: Exploiting
  massively parallel news sources.
\newblock In {\em Proceedings of the 20th international conference on
  Computational Linguistics}, page 350. Association for Computational
  Linguistics.

\bibitem[\protect\citename{Ganitkevitch \bgroup et al.\egroup
  }2013]{ganitkevitch2013ppdb}
Juri Ganitkevitch, Benjamin Van~Durme, and Chris Callison-Burch.
\newblock 2013.
\newblock Ppdb: The paraphrase database.
\newblock In {\em HLT-NAACL}, pages 758--764.

\bibitem[\protect\citename{He \bgroup et al.\egroup }2015]{he2015multi}
Hua He, Kevin Gimpel, and Jimmy Lin.
\newblock 2015.
\newblock Multi-perspective sentence similarity modeling with convolutional
  neural networks.
\newblock In {\em Proceedings of the 2015 Conference on Empirical Methods in
  Natural Language Processing}, pages 1576--1586.

\bibitem[\protect\citename{Heilman and Smith}2010]{heilman2010tree}
Michael Heilman and Noah~A Smith.
\newblock 2010.
\newblock Tree edit models for recognizing textual entailments, paraphrases,
  and answers to questions.
\newblock In {\em Human Language Technologies: The 2010 Annual Conference of
  the North American Chapter of the Association for Computational Linguistics},
  pages 1011--1019. Association for Computational Linguistics.

\bibitem[\protect\citename{Ji and Eisenstein}2013]{ji2013discriminative}
Yangfeng Ji and Jacob Eisenstein.
\newblock 2013.
\newblock Discriminative improvements to distributional sentence similarity.
\newblock In {\em EMNLP}, pages 891--896.

\bibitem[\protect\citename{Jiang and Conrath}1997]{jiang1997semantic}
Jay~J Jiang and David~W Conrath.
\newblock 1997.
\newblock Semantic similarity based on corpus statistics and lexical taxonomy.
\newblock {\em arXiv preprint cmp-lg/9709008}.

\bibitem[\protect\citename{Kim}2014]{kim2014convolutional}
Yoon Kim.
\newblock 2014.
\newblock Convolutional neural networks for sentence classification.
\newblock In {\em Proceedings of the 2014 Conference on Empirical Methods in
  Natural Language Processing}, pages 1746--1751.

\bibitem[\protect\citename{Kingma and Ba}2014]{kingma2014adam}
Diederik Kingma and Jimmy Ba.
\newblock 2014.
\newblock Adam: A method for stochastic optimization.
\newblock In {\em International Conference on Learning Representation (ICLR)}.

\bibitem[\protect\citename{Luong \bgroup et al.\egroup
  }2015]{luong2015effective}
Minh-Thang Luong, Hieu Pham, and Christopher~D Manning.
\newblock 2015.
\newblock Effective approaches to attention-based neural machine translation.
\newblock {\em arXiv preprint arXiv:1508.04025}.

\bibitem[\protect\citename{Miao \bgroup et al.\egroup }2015]{miao2015neural}
Yishu Miao, Lei Yu, and Phil Blunsom.
\newblock 2015.
\newblock Neural variational inference for text processing.
\newblock {\em arXiv preprint arXiv:1511.06038}.

\bibitem[\protect\citename{Mikolov \bgroup et al.\egroup
  }2013]{mikolov2013efficient}
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.
\newblock 2013.
\newblock Efficient estimation of word representations in vector space.
\newblock {\em arXiv preprint arXiv:1301.3781}.

\bibitem[\protect\citename{Qiu \bgroup et al.\egroup }2006]{qiu2006paraphrase}
Long Qiu, Min-Yen Kan, and Tat-Seng Chua.
\newblock 2006.
\newblock Paraphrase recognition via dissimilarity significance classification.
\newblock In {\em Proceedings of the 2006 Conference on Empirical Methods in
  Natural Language Processing}, pages 18--26. Association for Computational
  Linguistics.

\bibitem[\protect\citename{Resnik}1995]{resnik1995using}
Philip Resnik.
\newblock 1995.
\newblock Using information content to evaluate semantic similarity in a
  taxonomy.
\newblock {\em arXiv preprint cmp-lg/9511007}.

\bibitem[\protect\citename{Severyn and Moschitti}2015]{severyn2015learning}
Aliaksei Severyn and Alessandro Moschitti.
\newblock 2015.
\newblock Learning to rank short text pairs with convolutional deep neural
  networks.
\newblock In {\em Proceedings of the 38th International ACM SIGIR Conference on
  Research and Development in Information Retrieval}, pages 373--382. ACM.

\bibitem[\protect\citename{Wang and Ittycheriah}2015]{wang2015faq}
Zhiguo Wang and Abraham Ittycheriah.
\newblock 2015.
\newblock Faq-based question answering via word alignment.
\newblock {\em arXiv preprint arXiv:1507.02628}.

\bibitem[\protect\citename{Wang \bgroup et al.\egroup }2007]{wang2007jeopardy}
Mengqiu Wang, Noah~A Smith, and Teruko Mitamura.
\newblock 2007.
\newblock What is the jeopardy model? a quasi-synchronous grammar for qa.
\newblock In {\em EMNLP-CoNLL}, volume~7, pages 22--32.

\bibitem[\protect\citename{Yang \bgroup et al.\egroup }2015]{yang2015wikiqa}
Yi~Yang, Wen-tau Yih, and Christopher Meek.
\newblock 2015.
\newblock Wikiqa: A challenge dataset for open-domain question answering.
\newblock In {\em Proceedings of the Conference on Empirical Methods in Natural
  Language Processing}.

\bibitem[\protect\citename{Yin and Sch{\"u}tze}2015]{yin2015convolutional}
Wenpeng Yin and Hinrich Sch{\"u}tze.
\newblock 2015.
\newblock Convolutional neural network for paraphrase identification.
\newblock In {\em Proceedings of the 2015 Conference of the North American
  Chapter of the Association for Computational Linguistics: Human Language
  Technologies}, pages 901--911.

\bibitem[\protect\citename{Yin \bgroup et al.\egroup }2015]{yin2015abcnn}
Wenpeng Yin, Hinrich Sch{\"u}tze, Bing Xiang, and Bowen Zhou.
\newblock 2015.
\newblock Abcnn: Attention-based convolutional neural network for modeling
  sentence pairs.

\end{thebibliography}
