Learning pairwise patterns in Community Question Answering

3.1 Generalizing lexical information: Distributional models of lexical semantics

The BoW model does not generalize lexical information and cannot match semantically related words, such as synonyms. For instance, a pure direct matching between words cannot capture any similarity between “buy a car” and “purchase an automobile”, and a lexical generalization is needed to capture the quasi-synonymic usage of car vs. automobile and buy vs. purchase. This kind of information can be extracted from large scale lexicons, e.g.,  WordNet [21, 40], but their coverage is usually not satisfactory. Moreover, some tasks require a domain-specific notion of similarity that lexicons, which are usually general-purpose, cannot provide. These limitations can be overcome by defining word representations, i.e.,  vectors embodying the semantics of words. These methods have a significant impact in a variety of applications, such as document classification [55], question answering [66], information retrieval [37], named entity recognition [68], and parsing [61].

Usually words are represented as vectors in a low dimensional space, such that similar, or semantically related concepts are close. In these semantic spaces, the notion of word similarity is captured through cosine similarity, inner product, or other vectorial operations.

In Computational Linguistic there is a wide literature regarding techniques for automatically generating word vectors. These methods rely on the Distributional Hypothesis, which has been synthesized by Firth (see [26]):

The underlying intuition behind Distributional Semantic Models is that the meaning of a word can be described by the set of textual contexts in which it appears. In fact, words appearing in similar contexts are semantically related by some type of semantic relation, either paradigmatic (e.g.,  synonymy, hyperonymy, antinomy) or syntagmatic (e.g.,  meronymy, conceptual and phrasal association), as observed in [53].

The two main approaches for generating word vectors differ in how the distributional hypothesis is exploited. In the classic count-vector-based models 6 , the word-context co-occurrences are globally counted from a large scale corpus; in the context-predicting models (more commonly known as neural language models), the vector estimation problem is treated as a learning task, in which the values of the word vectors have to be set in order to optimize a cost function defined on the available corpus. Obviously, in both approaches, a good approximation of the word distributional information can be achieved only if a sufficient amount of observations is gathered. Several large-scale corpora are available for English, e.g.,  the British National Corpus (BNC) [3] made of 100 million words, or the ukWaC corpus [6], made of 2 billions word.

A deep comparison of the effectiveness of different word embedding strategies on downstream tasks can be found in [7].

In this work, we will adopt Word2Vec [39], which is one of the most popular context-predicting models, thanks to its simplicity (the model is a neural network with a single hidden layer) and to the quality of the produced word embeddings.

3.2 Exploiting the syntactic information

Syntactic information is necessary for a complete understanding of the semantics of texts. For instance, two sentence having the same words can have opposite meaning, such as in Vettel passed Hamilton and Hamilton passed Vettel. In this case, a BoW model will result in two identical vectors, and only a syntactic analysis can clarify who is ahead.

A possible approach for capturing syntax can be the manual definition of an artificial feature set that should emphasize the syntactic and semantic aspects useful to solve a target problem. Referring to the previous examples, some informative features can be extracted from their syntactic parse trees in Fig. 2.

OPEN IN VIEWER

Fig. 2

Constituency trees of the sentences Vettel passed Hamilton and Hamilton passed Vettel.

For instance, an artificial feature can be the syntactic path between a given word and the predicate (i.e.,  the word evoking the underlying situation, in this case passed). The two sentences have different paths from the argument Vettel to the predicate passed, reflecting the different semantic roles of Vettel: he is ahead in Vettel passed Hamilton, and behind in Hamilton passed Vettel.

These kinds of features are basically the building blocks of the underlying rules characterizing an NLP problem, and the task of determining how to exploit these features to generate robust predictive models is left to the learning algorithm. Therefore, the feature engineering approach can be somehow considered a simplification of the development of the rule-based systems mentioned in Section 1. However, the definition of meaningful features is still a rather expensive and complicated process that requires a domain expert; moreover, every task has specific patterns that must be considered, making a manual feature engineering an extremely complex and not portable process.

Kernel methods [18, 52] are an elegant and efficient alternative to the manual definition of features, thanks to their capability to operate directly on structured data, such as sequences, trees or graphs. In NLP, sentences can be naturally represented through their syntactic parse trees. Then, instead of trying to design a synthetic feature space, tree kernels [17] can be employed to directly operate on the parse tree of sentences, evaluating the tree fragments shared by the input trees. This operation equals to a dot product in the implicit feature space of all possible tree fragments (which, of course, include most of the artificial features that can be engineered, such as the predicate-argument path, see for instance [28]). The dimensionality of such space is extremely large and an explicit representation is not viable due to computational and memory usage issues: the number of different sub-fragments in a tree is combinatorial in the number of tree nodes, therefore, even a small tree can generate up to thousands of billions of features. Tree kernels lead to state-of-the-art performance in several NLP tasks, where syntactic information is crucial, including Question Classification [19], Semantic Role Labeling [43], Paraphrase Identification and Recognizing Textual Entailment [25].

3.2.1 Tree Kernels for NLP

Tree Kernels (TKs) allow to estimate the similarity among texts, by directly comparing their parse trees.

The underlying idea is that the similarity between two trees T₁ and T₂ can be derived from the number of shared tree fragments. Let the set T = { t 1 , t 2 , … , t | T | } be the space of all the possible substructures and χ _i  (n _j ) be an indicator function that is equal to 1 if the target t _i is rooted at the node n _j and 0 otherwise. A tree-kernel function over T₁ and T₂ is defined as follows: TK ( T 1 , T 2 ) = ∑ n 1 ∈ N T 1 ∑ n 2 ∈ N T 2 Δ ( n 1 , n 2 ) ,(1) where N _{T 1} and N _{T 2} are the sets of nodes of T₁ and T₂ respectively, and Δ ( n 1 , n 2 ) = ∑ k = 1 | T | χ k ( n 1 ) χ k ( n 2 ) ,(2) which computes the number of common fragments rooted in the n₁ and n₂ nodes.

Different tree kernels can be defined according to the types of tree fragments considered in the evaluation of the matching structures. In the Subtree Kernel [71], valid fragments are subtrees, i.e., any node of a tree along with all its descendants. Subset trees are exploited by the Subset Tree Kernel [17], which is usually referred to as Syntactic Tree Kernel (STK); they are more general structures since their leaves can be non-terminal symbols. The subset trees satisfy the constraint that grammatical rules cannot be broken. For example, the constituency tree in Fig. 3a has [VP [VBD NP]] as a subset tree. Instead [VP [VBD]] is not a valid subset tree because the rule VP->VBD NP cannot be split. This strict constraint imposed by the STK may be problematic especially when the training dataset is small and only few syntactic tree configurations can be observed. The Partial Tree Kernel (PTK) relaxes this constraint considering partial trees, i.e.,  fragments generated by the application of partial production rules, and usually leads to higher accuracy, as shown in [42]. Examples of different kinds of tree fragments are illustrated in Fig. 3.

OPEN IN VIEWER

Fig. 3

a) Constituency parse tree for the sentence Vettel passed Hamilton, b) some subtrees, c) some subset trees, d) some partial trees.

Given a sentence s with |s| words, s [ I s → ] defines the subsequence of s that includes the words corresponding to the indices I s → = { i 1 s , … , i l ( I → ) s } , where 1 ≤ i 1 s < i 2 s < … < i l ( I → ) s ≤ | s | , and l ( I s → ) is the number of indices in I s → .

We define d ( I → ) = i l ( I → ) - i 1 as the length of the subsequence in the original sentence (i.e., gaps are included in this count). The PTK computation [42], is carried out by the following Δ _PTK function:

Δ P T K ( n 1 , n 2 ) = 0 , if the labels of n 1 and n 2 differ Δ P T K ( n 1 , n 2 ) = μ ( λ 2 + ∑ I → 1 , I → 2 : l ( I → 1 ) = l ( I → 2 ) λ d ( I → 1 ) + d ( I → 2 ) ∏ k = 1 l ( I → 1 ) Δ P T K ( c n 1 ( i k 1 ) , c n 2 ( i k 2 ) ) ) , otherwise(3)

where c _n  (k) is the k-th child of the node n, and λ and μ are decay factors in (0, 1] that penalize large child subsequences (that can include gaps) and deep partial trees, respectively.

The computational complexity of a PTK computation is O ( η δ 2 | N T 1 | | N T 2 | ) [42], where η is the largest subsequence of children to be considered, and δ is the maximal number of children observed in the two trees. However, the average running time tends to be linear in the number of nodes for natural language syntactic trees [42]. Moreover, it is worth noting that the number of nodes in a tree is bounded and much lower with respect to the combinatorial number of its possible sub-fragments.

4.1 A shallow intra-pair similarity approach

A very simple approach to Answer Selection consists of evaluating the similarity between the question and the answer. For instance, answer A₂ in Fig. 1 contains some relevant keywords appearing in the question, such as gold and sell.

The similarity between two sentences can be captured in different ways and at different levels (lexical, syntactic and semantic). Various similarity measures have been proposed in literature and many of them have been originally developed for the Semantic Textual Similarity task [1].

In the experiments reported in Section 5, we will adopt the following similarity measures:

Lexical Similarities: Cosine similarity, Jaccard coefficient [33] and containment measure [12] of n-grams of word lemmas (n = 1, 2, 3, 4 was used in all experiments); Longest common substring measure [29], Longest common subsequence measure [2], and Greedy String Tiling [76].

Each similarity generates a feature, so that each question-answer pair can be converted into a feature vector. Then supervised learning algorithm, such as SVM, can learn how to combine these features for solving the classification problem. We define LK _sim as a linear kernel operating on the above described intra-pair similarities. A system based on the direct comparison between question and answer provides a strong and efficient baseline. However, it has some inherent weaknesses that are evident if we consider the answer A₃ from Fig. 1: this comment is definitely good , although it does not contains words similar to the ones in the question.

4.2 Learning from sentence pairs

In question answering, many good question-answer pairs, can be generalized to some latent answering template. For instance, a very high-level generalization of the question in Fig. 1 could be Can I do something?; while valid answers can be Yes you can …, or No you cannot …, which match A₂ and A₃, respectively 8 .

In a general-purpose forum, such as Qatar Living, a large variety of these question-answering templates can be considered. Their manual definition through hand-coded rules is extremely complex and time-consuming, and probably it will lead to a poor and low-coverage solution.

With the assumption that the targeted question-answer templates characterize multiple examples in the dataset, we propose a kernel-based approach to automatically learn syntactic-semantic patterns from training data. These patterns can somehow correspond to the question-answering templates we aim at capturing. The intuition we follow is quite simple: an answer is probably valid for a given question if similar question-answer pairs are labeled as good  in the training set. For instance, the following question-answer pairs from the Qatar Living dataset have a very similar structure, although they treat completely different topics:

Good Question-Answer Pair 2

Q₂: Which is the best beach here in Qatar?

A ^{Q ₂} : Sealine Resort is the best option

Good Question-Answer Pair 3

Q₃: Which is the best bank around?

A ^{Q ₃} : CQB is the best option

This is a paradigmatic shift with respect to the similarity approach described in the previous section: sentences are not only compared with the other element of their pair, but inter-pair analysis is also performed.

4.3 Kernels on question-answer pairs

Pairs which can be associated with a common question-answering template share a similar syntactic structure, as illustrated in Fig. 4 (for the moment ignore the red REL prefixes). Therefore, high syntactic similarity between the two questions and between the two answers can be assumed to be a good indicator that the two pairs respect the same underlying template. We opted for a shallow parse tree representation, i.e.,  a tree where words have their POS tags as fathers, which are then grouped into chunks. In fact, the quality of more complex tree representation, such as full constituency trees, is largely affected by the noisy nature of the text in community Question Answering. Furthermore, sentences can be very long thus a full syntactic parse tree may result too large for a tree kernel computation. Finally, shallow parsing is significantly more efficient.

OPEN IN VIEWER

Fig. 4

Shallow trees of two question-answer pairs exhibiting the same answering structure.

The tree kernel methods described in Section 3.2 can effectively establish the syntactic similarity between two sentences. We can extend this evaluation to question-answer pairs using a simple tree kernel combination. In particular, given two pairs p _i  = 〈q _i , a _i 〉 and p _j  = 〈q _j , a _j 〉, and a tree kernel TK, such as the PTK, the following kernel on pairs can be defined 9 : TK + ( p i , p j ) = TK ( q i , q j ) + TK ( a i , a j ) ,(4)

which simply sums the tree kernel similarities between the two questions and between the two answers. It is worth noting that the core difference between the approach discussed in Section 4.1 and the proposed TK⁺ is that the former evaluates intra-pair similarities, i.e.,  questions are compared with their answers, while the latter performs an inter-pair analysis, i.e.,  questions are compared with questions and answers with answers.

As suggested in [25] the text pairs representations are enriched by using a special tag, i.e.,  the red REL prefix in Fig. 4, to mark the words appearing in both the texts of a pair. In order to involve the syntactic part of the trees, the REL tag is propagated to the father and grandfather of the matching words, i.e.,  the POS tag and chunk nodes. This is a simple yet effective strategy to establish intra-pair relations and to allow the learning algorithm to distinguish the words having a counterpart in the other element of its pair.

The proposed tree kernel combination implicitly generates a huge feature space that includes relational features, such as [S [NP-REL [JJ-REL] [NN]] [PP [IN]]], [S [NP [NNP]] [VP] [REL-NP [REL-JJS]]]. Those features are interesting pairwise patterns, which a kernel-based learning algorithm, such as SVM, can capture and exploit to create robust classification models.

An interesting aspect of kernel methods is that kernel can be easily combined to create more sophisticated models. In particular, we can combine TK⁺ with a kernel operating on the intra-pair similarity feature vectors described in Section 4.1, for instance a Linear Kernel (LK). This will result in a stronger kernel that can leverage both the intra-pair and inter-pair approaches.

The explicit similarity features proposed in Section 4.1, as well as the implicit tree kernel features described in Section 4.2 have a large applicability in other tasks such as Paraphrase Identification or Textual Entailment Recognition. Instead, in this section we will present some features, proposed in [8], which have been developed specifically for the cQA scenario.

In particular, forty-four Boolean features express whether a comment:

includes URLs or emails (2 feats.). In fact, exploring the training data, it is possible to notice that many good  comments suggest visiting a Web site or contacting an email address;

A particular aspect that characterizes Community Question Answering is that the comments in a thread typically reflect an underlying concrete discussion, which is more than a sequence of independent answers 11 . For instance, users replicate to each other, add additional information to someone else’s answers, ask for further details, or tease other users.

We modeled thread-level dependencies by designing specific features that are able to capture the dependencies between the answers in the same thread.

The following notation will be adopted: q is the question posted by user u _q , c is a comment from user u _c , in the comment thread.

Four features indicate whether c appears in the proximity of a comment by u _q . The assumption is that an acknowledgment or further questions by u _q in the thread could signal a good  answer. More specifically, they test if among the comments following c there is one by u _q (i)  containing an acknowledgment, (ii)  not containing an acknowledgment, (iii)  containing a question, and, (iv)  if among the comments preceding c there is one by u _q containing a question.

The value of these four features —a propagation of the information captured by the feature group 6 — depends on the distance k, in terms of the number of comments, between c and the closest comment by u _q :

f ( c ) = { max ( 0 , ThickSpace 1.1 - 0.1 k ) 0 if no comments by u q exist ,(5) that is, the closer the comment to c _q , the higher the value assigned to this feature 12 .

We define LK _qa as a linear kernel operating on the features specific to the task described above.

5.1 Evaluation measures

In the 2015 edition [44], the cQA challenge was a classification task where the official measure was the macro F₁ measure of the three classes, namely good, bad  and potential . Instead, in the 2016 and 2017 editions [45, 46], the organizers defined the task as a re-ranking problem where the participants had to provide a ranking of the comments in each QA thread. In this case, the official evaluation measure was the Mean Average Precision (MAP) and there was no distinction between the potential  and bad  classes. This change was partially motivated by the generally low performance observed in detecting the potential  comments. In fact, as discussed in [10], the boundaries of this intermediate class are not well defined. We performed experiments with the two class setting also on the 2015 edition. In addition to the MAP, we will also report the Mean Reciprocal Rank (MRR), and the Average Recall (AvgRec). In solving the task, we will use a point-wise approach, where the scores of a binary classifier are used to rank the comments. Thus, we will also provide the standard classification metrics, namely accuracy, precision, recall and F₁ w.r.t. the good  class.

Finally, to have a comparison with the 2015 challenge results, we will also run a 3-class setting experiment on the 2015 data. In this case we will report the accuracy and macro-F₁.

5.2 Text preprocessing

As we can observe in Fig. 1, the text is very informal and inherently noisy. It contains spelling errors, special characters, non-standard word forms, grammatical mistakes, usage of multilingual words, and so on. Standard NLP methods are usually affected by noise in text and there is a broad literature discussing text cleaning [62, 63] and the development of NLP algorithms robust to noise [5, 11].

In addition to general text normalization techniques, such as spelling correction and HTML tag removal, the forum setting requires some specific treatment.

Both questions and answers have a subject and a body. The subject can have three different forms:

it is a synthetic sentence summarizing the content of the post, as in Fig. 1 for Q;

Therefore, in the first case the subject is highly informative; in case (ii)  it is only a useless redundancy; in case (iii)  the subject introduces fake question-comment similarities, that can significantly impact the system accuracy. We used simple rules to detect cases (ii)  and (iii)  and remove the uninformative subjects.

Furthermore, several users put a signature at the final part of their posts. For instance, many comments from user U947 end with the following sentence:

User signatures are completely uncorrelated with the thread topic, and introduce a significant amount of noise in the data. In fact, they produce irrelevant lexical overlaps between different comments of a given author, and drastically reduce the similarity between related comments 13 . To detect and remove user signatures we applied a simple procedure. We grouped posts by user, and compared the post in each group to verify the presence of common final parts. Those parts can be considered signatures to be removed. Using this algorithm we discovered and removed a signature from about 10% of the comments.

A manual analysis on the retrieved user signatures showed that the proposed approach is extremely precise in detecting user signatures, i.e.,  no core part was erroneously considered a signature. When a signature is present in a single comment of the dataset, it cannot be detected with such a procedure. This problem can be partially mitigated removing the text appearing after some “signature separator” 14 in a comment.

5.3 Models and Parameterization

We train our models using the C-SVM algorithm [14] within KeLP 15 , a Kernel-based Machine Learning platform [24] that implements the tree kernels described in Section 3.2. In the 3-class setting we used a one-vs-all schema. With this setting, the data is rather imbalanced, as the potential  class occurs far less than the other classes. We took this into account by emphasizing the regularization parameter for the positive class, i.e.,  C p = # negatives # positives C , following [41].

In the 2-class setting, we used a binary SVM trained to recognize good  answers.

PTK was used with the default parameters, i.e.,  λ = μ = 0.4, while we selected the hyper-parameter C = 1 of SVM using a tuning stage on the 2015 dev. set.

We generated shallow trees from the question-answer pairs by using the OpenNLP 16 chunker.

To study the impact of the various features proposed in Section 4, we tested different kernels:

LK _sim is a Linear Kernel operating on the intra-pair features defined in Section 4.1;

Finally, we linearly combined these kernels to create a more robust approach.

When testing on the 2015 and 2016 test sets, we trained the models by using the training and development sets of the corresponding year. Instead, for the 2017 test set, we used all the 2016 datasets as training material.

5.4 Results

Table 2 shows the results on the 2015 test set in the 3 class setting. In the bottom part of the table we reported the results of the three best systems at SemEval-2015. The JAIST team [67] won the 2015 competition using an SVM operating on several features that include, intra-pair similarities, alignment-based features, topic-based features and some heuristics. HITSZ-ICRC [32] adopted a hierarchical classifier trained to firstly identify bad  comments and then to distinguish the good  answers from the potential  ones. They employed intra-pair similarities and several linguistic features, such as the counts of name entities, punctuation marks or specific POS in the comments. Finally, the QCRI system [48] used a preliminary version of the features described in sections 4.1 and 4.4.

All the proposed kernels are significantly above the Majority Baseline (i.e.,  always good).

The LK _sim model is the weakest model, it confirms the issue we highlighted at the end of Section 4.1, which justifies our inter-pair approach: many good  comments directly answer without repeating the words (and more in general the concepts) expressed in the question.

The LK _qa model, instead, is rather accurate; this is not surprisingly, as it is based on a set of manually defined features that have been specifically developed to capture some frequent phenomena appearing in general-purpose fora.

The TK⁺ model reaches similar results: this is very impressive considering it does not exploit task or domain specific features, but implements a general approach that can be used in every task defined on text pairs. Furthermore, this result is even more remarkable if we consider that the intra-pair reasoning, which represents the more straightforward approach to solve this problem, is basically neglected, as the TK⁺ model applies an intra-pair similarity only in establishing the REL tags on the parse trees of the question-answer pairs.

Finally, we defined kernels of increasing complexity, by linearly combining the individual kernels. The results are outstanding, demonstrating that the information provided by the different kernels is largely independent. Therefore, a joint learning model (i.e.,  an SVM equipping a kernel combination) can take the best by the these three different sources of information. The LK _sim +LK _qa is competitive with the best systems, while the LK _sim +LK _qa +TK⁺ achieves the new state-of-the-art on this dataset.

Similar results are obtained in the 2-class setting, reported in Table 3. According to MAP, the best individual kernel is TK⁺. Again, linearly combining the three kernels leads to state-of-the-art results, which largely outperform the best systems at SemEval-2015 17 Furthermore, our best model achieves higher accuracy and F₁ than MaxEnt+GraphCut [36] and FCCRF [35], which are two systems developed after the SemEval-2015 challenge. They both approach the answer selection in cQA as a graph task, where all the comments in a question thread should be globally classified.

Finally, Tables 4 and 5 report the official results of the 2016 and 2017 semEval challenges, respectively. We participated with the LK _sim +LK _qa +TK⁺ model under the pseudonym KeLP. In both occasions, we won the competition. In the 2016 edition 12 systems participated to the challenge and apart KeLP, the best two were ConvKN [9], which jointly used convolutional neural networks and kernel methods, and SemanticZ [38], which relied on several semantic similarity features based on fine-tuned word embeddings and topic similarities.

In the 2017 edition, there were 14 systems participating to the challenge, and the best systems apart KeLP were Beihang-MSRA and IIT-UHH. Beihang-MSRA [23] is based on a gradient boosted regression tree model that using several features including various NLP features, neural network based matching and task specific features. IIT-UHH [47] is an SVM based system that makes use of textual, domain-specific, word embedding and topic-modeling features.

The results obtained on the 2017 data are significantly higher than those derived on the other two years in terms of ranking metrics. This depends on the fact that there are many threads with mostly good  comments, or mostly bad  comments. Consequently, their re-ordering impact less on the initial MAP. This is also confirmed by the high results achieved by the chronological baseline. Instead, the accuracy is in line with the one observed in the previous years, demonstrating the consistency of the proposed model.

In order to get an intuition about the effect of the proposed inter-pair approach, we show a comparison between LK _sim and TK⁺ in Fig. 5. All the comments are classified correctly by the TK⁺ model, and incorrectly by the LK _sim . This confirms that the TK⁺ model effectively learned valid question-answer patterns, such as Q:“Is there any …?” A:“Try …”. In contrast, the intra-pair similarities cannot capture any useful information from these question-answer pairs, which are consequently all classified as bad .

OPEN IN VIEWER

Fig. 5

A real question–comments threads from the 2016 test set (ID Q386_R4). The class label before the arrow corresponds to the prediction provided by LK _sim , while the right-hand label is the prediction provided by TK⁺, which always provides the correct class.