3.1 CQA-MD: a medical arabic corpus for cQA

We used data from the medical domain, which is largely ignored for Arabic.Footnote ⁴We extracted data from three popular Arabic medical websites that allow visitors to post questions related to health and medical conditions, and to get answers by professional doctors within days for free. In particular, we collected 1,531 QA pairs from WebTeb,Footnote ⁵ 69,582 pairs from Al-Tibbi,Footnote ⁶ and 31,714 pairs from the medical corner of Islamweb.Footnote ⁷

In order to generate our collection, we used the 1,531 questions from WebTeb as our original questions, and we looked to find related QA pairs from the other two websites that can answer these questions.

We collected over 100,000 QA pairs in total from the other two websites, we indexed them in Solr,Footnote ⁸ and we searched them trying to find answers to the WebTeb questions.

We used several different query/document formulations to perform twenty-one retrieval runs, and we merged the retrieved results, ranking them according to the reciprocal rank fusion algorithm (Cormack, Clarke and Buettcher Reference Cormack, Clarke and Buettcher2009). Finally, we truncated the resulting list to the thirty top-ranked QA pairs, which yielded 45,164 QA pairsFootnote ⁹ for the 1,531 original questions.

Note that the maximum number of candidates to be reranked, namely thirty, does not follow a precise rule or best practice. However, we considered two main factors that led us to select thirty candidates. First, while for the English cQA task, there is a large percentage of questions having at least one correct answer in the first ten candidates retrieved by a search engine, for our Arabic cQA dataset, this percentage was much lower. Second, in the field of passage retrieval, which is similar to our task, it has been observed that even powerful rerankers fail to push relevant candidates to the top if they occur too low in the original retrieval list. Therefore, the number thirty comes from a trade-off between (i) the need to have at least some candidates to rerank (otherwise, the task would not be interesting and the difference between the participating systems would just depend on a small number of questions), and (ii) the awareness that too long lists would have not positively impacted the accuracy of the participating systems. In contrast, having many more candidates would have caused inefficiency for both training and testing. Although, we did not systematically study the distribution of correct questions with respect to the length of the retrieved candidates list, we practically observed that with thirty candidates, we could obtain relevant (Direct and Relevant) answers for most of our questions.

Next, we used the CrowdFlowerFootnote ¹⁰ crowdsourcing annotation platform to obtain judgments about the relevance of these QA pairs with respect to the original question using the following labels:

• • ‘D’ (Direct): The QA pair contains a direct answer to the original question such that if the user is searching for an answer to the original question, the proposed QA pair would be satisfactory and there would be no need to search any further.

• • ‘R’ (Related): The QA pair contains an answer to the original question that covers some of the aspects raised in the original question, but this is not sufficient to answer it directly. With this QA pair, it would be expected that the user will continue the search to find a direct answer or more information.

• • ‘I’ (Irrelevant): The QA pair contains an answer that is irrelevant to the original question.

We controlled the quality of annotation using a hidden set of fifty test questions. We had three judgments per example, which we combined using the CrowdFlower mechanism, i.e., using majority voting and annotator confidence to assign the final label. The average inter-annotator agreement was eighty-one per cent.

We should note that the medical domain complicates the annotation task for Turkers, especially with respect to distinguishing between the classes ‘D’ and ‘R’, where the main difference is that the former satisfies the information need completely, while the latter does so only partially. This difference is about understanding the completeness of an answer, and thus can be often detected without a background in the medical domain. Another important factor to consider is that Turkers see the correct answer by a physician during annotation, and thus they can try to match such content. Moreover, the questions are asked by common people, and are about general medical topics, expressed in an informal and colloquial format; so, are the physicians’ answers. Finally, note that ultimately we merge ‘D’ and ‘R’ for the purpose of the challenge and of our study; thus, even if these two classes happen to be confused, this would not really matter.

Finally, we divided the data into training, development and testing datasets, based on confidence, where the examples in the test dataset were those with the highest annotation confidence. A well-trained native speaker of Arabic double-checked and manually corrected some of the annotations for the development and the testing datasets. The objective was to provide higher-quality development and testing datasets for parameter tuning and for testing, respectively.

Figure 1 shows part of the XML file we generated. It illustrates some challenges for Arabic cQA, such as long introductions, use of English words for medical terms, lack of capitalization for named entities, sloppy punctuation, spelling mistakes, etc. In the example, the original question is about a desire for pregnancy given menstrual cycle disorders and side effects for a certain medicine. The related question is about the reasons for menstrual cycle disorders in the case of taking contraceptive pills and how this can negatively affect pregnancy. In the related answer, after a long greeting, the physician explains that contraceptive pills can impact women differently, and describes some general effects of such pills on menstrual cycle and pregnancy.

Fig. 1.

Annotated question from the Arabic CQA-MD corpus.

We can further see that the XML file includes information about the confidence of annotation. This information is available for the training and the development datasets only, but not for the test dataset. It allows systems to trust less training examples with lower agreement.

Table 1 shows some statistics about the dataset size and the distribution of the three classes in the CQA-MD corpus.

Table 1.

Statistics about the CQA-MD corpus

3.2 Challenges in arabic cQA

Below, we discuss some characteristics of Arabic online content that make Arabic cQA difficult in general, and we provide some statistics and examples from our CQA-MD corpus.

• • Use of dialects: A typical feature of Web forums is the use of dialectal Arabic instead of MSA. In many cases, dialectal words are incorrectly recognized as Out-Of-Vocabulary words by Arabic morphological analyzers, which in turn affects syntactic parsing and general language understanding as most tools for Arabic processing are tailored for MSA. In particular, we calculated that in our test dataset about twenty per cent of the questions contained some dialectal words, while at the same time all answers were in MSA as they were written by professional physicians. This means that there is some mismatch between the language variety (dialect versus MSA) used in the question and in the answer, and this causes further issues when comparing the text of a question to the text of an answer. This is especially important at the syntactic level as most dialectal words are function words. However, in our data this is less important at the semantic level as terminology covering diseases and body parts are in MSA, i.e., word embeddings might be more robust with respect to dialectal variance.

• • Sloppy punctuation: The informal, dialectal text in Web forums often neglects punctuation, unlike proper MSA text. Yet, the proper use of punctuation can be crucial for some NLP processing steps such as sentence segmentation and syntactic parsing. In particular, we considered the fact that, on average, the original questions, the related questions, and the related answers have a punctuation mark after every twelve, eighteen, and thirteen words, respectively. Yet, in a proper newswire text, such as a 100M-word 10-year AljazeeraFootnote ¹¹ archive, there is a punctuation mark after seven words on the average.

• • Spelling errors: Forum texts are written in an informal setting, and thus are not carefully edited as a newswire text would be; as a result, they often contain spelling errors. Our analysis shows that in our test dataset, eighty per cent of the questions and forty per cent of the answers had at least one typo. Most of these typos consist in omitting the hamza symbols on top and below the bare Alef symbol or missing the dots for the letters ya and ta marbuta, which turns them into alef maqsura and ha, respectively. These problems are somewhat easy to solve using normalization and consulting a large LM to select the best candidate in a given context; yet, this is a bit more complicated for dialectal texts as LMs are not so reliable for them. Other spelling mistakes involve missing letters, swapped letters, or concatenated/split words.

• • Long preambles and introductions: It is common in Arabic to start a question with a religious greeting or introduction, and to end it with an acknowledgment or a prayer. Our analysis shows that fifty-eight per cent of the questions and of the answers in our dataset have such starting introductions, e.g., ‘Peace be upon you and God’s mercy and blessings. . .’ and ‘In the name of God the most gracious the most merciful dear brother/sister. . .’Also, fifty per cent of the questions and of the answers end with a salutation or a prayer such as ‘and thanks’, or ‘May God bless/reward you’. This requires extra efforts to recognize the important parts of the questions and of the answers and potentially to ignore such introductory/ending parts.

Figure 2 shows an example that illustrates some of the difficulties described above: different types of spelling mistakes, no punctuation marks, as well as long introduction and acknowledgments that surround the core part of the question. Figure 3 shows two other cases: using English words inside Arabic questions, and complex medical terms and medicines. All these difficulties negatively affect automatic parsing and understanding.

Fig. 2.

Challenges for question analysis: typos, punctuation, and preambles.

Fig. 3.

More challenges for question analysis: English words and medical terms.

Below are some additional challenges we face that are specific for our particular corpus, mostly due to its medical nature:

• • Use of complex medical terms: As our corpus is from the medical domain, it is common to find in the questions and in the answers complex medical terms (e.g., Progesterone in Arabic), names of medicines (e.g., Ortho-Cyclen in Arabic), sometimes even complex medical terms in English, e.g., Keratoplasty and Zyprexa. We found that about forty-one per cent of the questions and seventy-seven per cent of the answers contained complex medical terms (we did not consider as complex terms words such as heart attack and bleeding that are in everyday use or are generally understood by Arabic speakers), while in the remaining cases the users described their cases in a simple language; physicians also tried to simplify their way of expression in order to make their response more comprehensible.

• • Sensitive and socially embarrassing medical questions: An important characteristic of our medical data is the abundance of questions that are arguably socially embarrassing. As people feel uneasy to talk about them face-to-face to a physician, they preferred to pose them online, hiding behind the anonymity that an Internet forum seemingly offers. In some cases, users tended to anonymously describe their cases in a lot of detail, using vocabulary that is not known to standard NLP tools, as such terms are not frequent in newswire texts that are typically used to train Arabic NLP tools. Figure 4 shows that, in our test dataset, the two most-commonly mentioned diseases, accounting for thirty-seven per cent combined, are indeed related to obstetrics and gynaecology, along with genital and urinary system diseases.Footnote ¹²

• • Detailed questions and answers: In forty-eight per cent of the questions, people were asking about general issues (e.g., what are the symptoms of a certain disease?), while in fifty-two per cent of the questions, they were asking about very specific cases (e.g., ‘I am xx years old, this is my medical history. I take this medicine and I have certain symptoms, etc.’). Because users want to write everything in one question without knowing exactly what the important details from a physician’s perspective are, they describe their cases with a lot of detail in terms of numbers, treatments, medical history, etc. Also, physicians reply by giving the medical description and analysis of their cases, with general and specific instructions and prescriptions. Some questions are answered by more than one physician, when the question is related to more than one medical specialty (e.g., dermatology and psychology). This makes questions and answers very long and adds extra complexity to the linguistic analysis, but also for manual annotation of the gold labels, as long questions and answers are difficult to understand. For example, the average lengths of the questions and of the answers are 40 and 119 words, respectively.

• • Short answers: For some questions, after a long description and lot of detail about a patient’s case, we have short answers like: ‘Yes’, ‘This is normal’, or ‘For two years’, etc. Sometimes, a physician’s reply is not a real answer to the question like: ‘Send more details’, ‘This question was answered before’, ‘Unclear question’, or ‘Consult your doctor’. These kinds of short answers with almost no lexical overlap with the questions are challenging for systems that try to learn from data and to find syntactic or semantic relations between questions and answers. We think of annotating these answers differently in the future.

Fig. 4.

The most frequently mentioned diseases in our test dataset.

4.1 Task setting

The SemEval task can be defined as follows: given an original question q _o and k candidate QA pairs 〈q _s, a _s〉, 1 ⩽ s ⩽ k (retrieved by a search engine), the task is to rank them with respect to their relevance to q _o. In our setting, we used k = 30 QA pairs associated with each q _o, where a _s is the correct answer to q _s provided by a professional physician. Operationally, the task can be defined as ranking Direct and Relevant answers above the Irrelevant ones (see Section 3.1). Note that the former two are considered Relevant in terms of the official task evaluation.

Metrics. We used Mean Average Precision (MAP) as the primary metric. MAP is a well-established measure in IR. We further report the results for two secondary ranking measures: Mean Reciprocal Rank (MRR) and Average Recall (AvgRec).

MAP is calculated over a set of query questions Q, as the mean of the average precision (AveP) values computed on all questions:

$$\mathrm{MAP} = \frac{1}{|Q|}\sum _{q_o \in Q}AveP(q_o) $$

where AveP(·) is the average of the precision value obtained for the set of the top QA pairs 〈q _s, a _s〉 computed after each relevant QA pair is retrieved.

MRR is computed as follows:

$$\mathrm{MRR} = \frac{1}{|Q|} \sum _{q_o \in Q} \frac{1}{rank(q_o)} $$

where rank(q _o) is the position of the first relevant QA pair in the list of candidates for q _o.

Computed over a set of query questions Q, AvgRec is the mean of the AveR over all questions q _o in the test dataset:

$$\mathrm{AvgRec} = \frac{1}{|Q|}\sum _{q_o \in Q}AveR(q_o) $$

where AveR is the mean of the recall values obtained for the set of top questions, computed after each QA pair is retrieved.

4.2 Descriptions of the participating systems

Many methods can be applied to solve a ranking task, which is about defining a scoring function $r:{\mathcal Q} \times {\mathcal Q}\times {\mathcal A} \rightarrow \mathbb {R}$, for ranking 〈q _s, a _s〉 pairs with respect to q ₀, where ${\mathcal Q}$ and ${\mathcal A}$ are the set of questions and answers, respectively.

Almost all participating systems, i.e., SLS, ConvKN, RDI, and UPC_USMBA, modeled r as a linear function:

(1) \begin{equation} r(q_{o},q_{s}, a_{s})=\vec{w}\cdot \phi (q_{o},q_{s}, a_{s}) \end{equation}

$\vec{w}$

$\vec{w}$

SLS (MIT-CSAIL)

This SLS system by Mohtarami et al. (Reference Mohtarami, Belinkov, Hsu, Zhang, Lei, Bar, Cyphers and Glass2016) applied SVMs to the following concatenation of a lexical-based and of an embedding-based feature vector:

$$\phi (q_{o},q_{s},a_{s}) = \left[ \phi _{\mathrm{lex}}(q_{o},q_{s},a_{s}), \phi _{\mathrm{emb}}(q_{o},q_{s},a_{s}) \right] $$

The feature vector ϕ_lex(q _o, q _s, a _s) is in turn a concatenation of two feature vectors

$$\phi _{\mathrm{lex}}(q_{o},q_{s},a_{s}) = \left[ \phi _{\mathrm{lex}}(q_{o},q_{s}), \phi _{\mathrm{lex}}(q_{o},a_{s})\right] $$

where ϕ_lex(x, y) is a vector whose coordinates correspond to twenty different types of textual similarity between x and y as described in (Nicosia et al. Reference Nicosia, Filice, Barrón-Cedeño, Saleh, Mubarak, Gao, Nakov, Da San Martino, Moschitti, Darwish, Màrquez, Joty and Magdy2015), including greedy string tiling (Wise Reference Wise1996), longest common sub-sequence (Allison and Dix Reference Allison and Dix1986), and Jaccard coefficient (Jaccard Reference Jaccard1901) over [1,4]-grams.

The vector ϕ_emb(q _o, q _s, a _s) is a concatenation of two scalar products

$$\phi _{\mathrm{emb}}(q_{o},q_{s},a_{s}) = \left[v(q_{o}) \cdot v(q_{s}), v(q_{o}) \cdot v(a_{s}) \right] $$

where the vectors v(q _o), v(q _s), and v(a _s) are embedding representations of q _o, q _s, and a _s, respectively; these question/answer embeddings are the average of the embeddings of the words they are made of

$$v(X)=\sum _{w \in X} w2v(w) $$

where w is a word-token from the text of X, and w2v(w) maps w to a word embedding.

The SLS team used two different embeddings trained using word2vec (Mikolov, Yih and Zweig Reference Mikolov, Yih and Zweig2013) on: (i) a raw domain-specific corpus of 26 millions tokens provided with the SemEval task, and (ii) an out-of-domain corpus, Arabic Gigaword,Footnote ¹³ which includes over a billion words, and 120,000 word types after lemmatization. These two types of embeddings, together with some text shrinking approach using TextRank by Mihalcea and Tarau (Reference Mihalcea and Tarau2004), were used to generate the primary and the contrastive submissions of SLS. More details can be found in (Barrón-Cedeño et al. Reference Barrón-Cedeño, Bonadiman, Martino, Joty, Moschitti, Al Obaidli, Romeo, Tymoshenko and Uva2016; Belinkov et al. Reference Belinkov, Mohtarami, Cyphers and Glass2015).

Another important characteristic of the SLS system is that they used a sentence-level vector rather than a vector based on the entire question or answer text, i.e., they calculated the scalar products for the pair of sentence vectors from q _o, q _s, and a _s (instead of using the entire text), and they retained the highest score only. The idea is that the questions and the answers in our dataset are often rather large and noisy, and thus it makes sense to focus on the best matching pairs of sentences only.

ConvKN (Qatar Computing Research Institute)

This system by Barrón-Cedeño et al. (Reference Barrón-Cedeño, Bonadiman, Martino, Joty, Moschitti, Al Obaidli, Romeo, Tymoshenko and Uva2016) combined different features with complex convolutional kernels such as TKs (Moschitti Reference Moschitti2006). They used the following representation for each 〈q _s, a _s〉 pair:

$$\phi (q_{o},q_{s}, a_{s}) = \phi _{\mathrm{lex}}(q_{o},q_{s}, a_{s}) + \phi _{\mathrm{tk}}(q_{o},q_{s}) $$

where ϕ_lex(q _o, q _s, a _s) is the same as in SLS, while ϕ_tk(q _o, q _s) is a vector encoding the syntactic structure of the question pairs 〈q _o, q _s〉, e.g., as shown in Figure 5. Discussion on the use of such syntactic models can be found in Section 6.2 below.

Fig. 5.

Arabic trees of two questions connected by REL links.

As generating ϕ_tk(q _o, q _s) explicitly requires complex feature engineering, ConvKN opted for an implicit representation applying the following kernel to two general examples, 〈q _o, q _s, a _s〉 and 〈q′_o, q′_s, a′_s〉:

\begin{equation*} \begin{aligned} K\big (\langle q_{o},q_{s}, a_{s} \rangle, \langle q^{\prime }_o,q^{\prime }_s, a^{\prime }_s\rangle \big ) = \phi (q_{o},q_{s}, a_{s}) \cdot \phi (q^{\prime }_o,q^{\prime }_s, a^{\prime }_s)=\\ & = \phi _{\mathrm{tk}}(q_{o},q_{s}) \cdot \phi _{\mathrm{tk}}(q^{\prime }_o, q^{\prime }_s) + \phi _{\mathrm{lex}}(q_{o},q_{s}, a_{s}) \cdot \phi _{\mathrm{lex}}(q^{\prime }_o,q^{\prime }_s, a^{\prime }_s) \end{aligned} \end{equation*}

where (TK is a tree kernel function)

$$\phi _{\mathrm{tk}}(q_{o},q_{s}) \cdot \phi _{\mathrm{tk}}(q^{\prime }_o, q^{\prime }_s) = TK(t(q_{o},q_s),t(q^{\prime }_{o},q^{\prime }_s)) + TK(t(q_s,q_{o}),t(q^{\prime }_{s},q^{\prime }_{o})) $$

This way, there was no need to extract explicit syntactic feature vectors from the text pairs. The function t(x, y) is a string transformation that returns the syntactic tree from the text x, enriching it with the REL tags (see Section 6.2) computed with respect to the syntactic tree of y. ConvKN used the Arabic Stanford Constituency Parser (Green and Manning Reference Green and Manning2010) for generating the syntactic tree for text x and a simple annotator to mark the tree nodes with the REL tags. The latter were added on the internal nodes each time a terminal node matches a word in the text y. The REL tags were then also propagated to the parent nodes (up to two levels up). See Figure 5 for an example. Finally, the ConvKN team used the partial TK by Moschitti (Reference Moschitti2006), which measures the similarity between trees.

RDI (Research Development International)

The RDI team developed a system (Magooda et al. Reference Magooda, Gomaa, Mahgoub, Ahmed, Rashwan, Raafat, Kamal and Al Sallab2016), which used (i) external corpora (EC) crawled from www.altibbi.com to compute the probability of 〈q _s, a _s〉 to be relevant to q _o, (ii) a LM trained on the annotated CQA-MD dataset; and (iii) the Arabic Wikipedia to boost the weights of medical terms.

RDI did not use supervised learning for modeling the ranking function r, and thus there is no w. Instead, they model the function r directly, which is expressed by a weighted sum of three terms as follows:

\begin{equation*} \begin{aligned} r(q_{o},q_{s}, a_{s}) & = \alpha \times {\mathcal P}\Big ( {\phi (q_{o}) \cdot \phi ^{+}_{tf \times idf}(q_{s}, a_{s})},{\phi (q_{o}) \cdot \phi ^{-}_{tf \times idf}(q_{s},a_{s})}\Big )+\\ & + \beta \times \phi _{LM}(q_{o}) \cdot \phi _{LM}(q_{s},a_{s}) + \gamma \times \phi _{wp}(q_{o}) \cdot \phi _{wp}(q_{s},a_{s}) \end{aligned} \end{equation*}

where α, β, and γ are parameters (tuned on the development dataset), which control the impact of each of the three components.

The first component is the relevancy probability of the candidate pair 〈q _s, a _s〉 computed by the function ${\mathcal P}$Footnote ¹⁴ using the two scalar products, $\phi (q_{o}) \cdot \phi ^{+}_{tf \times idf}(q_{s}, a_{s})$ and $\phi (q_{o}) \cdot \phi ^{-}_{tf \times idf}(q_{s},a_{s})$, where

1. (i) ϕ(q _o) is simply a binary vector representing the terms of q _o;

2. (ii) $\phi ^{+}_{tf \times idf}$ is a TF×IDF vector of the terms in 〈q _s, a _s〉 with IDF values computed using a set of pseudo-positive QA pairs extracted from EC;Footnote ¹⁵

3. (iii) $\phi ^{-}_{tf \times idf}$ is a similar vector as above but using pseudo-negative pairs from EC.

The second component is the scalar product of two embedding vectors, ϕ_LM(q _o) and ϕ_LM(q _s, a _s), computed using the LM approach by Mikolov et al. (Reference Mikolov, Kombrink, Burget, Černocký and Khudanpur2011). The latter is applied to a corpus constituted by the candidate pairs, 〈q _s, a _s〉, augmented by the pairs 〈q _o, a _s〉, for each q _o and its related q _s in CQA-MD.

The third component is a scalar product between ϕ_wp(q _o) and ϕ_wp(q _s, a _s), where the vectors are constituted by n-grams, whose weights are increased if they match terms in the medical categorization system of the Arabic Wikipedia. The set of used medical terms contains about 250,000 medical subcategories extracted from the main medical category. Matching unigrams has a weight of 1.5, whereas all the other matching n-grams have a weight of 2.

5.1 Measuring the potential of system combination

In this first experiment, we combine the first n systems, n ∈ {2, 3, . . ., 13}, as ordered in Table 2, in a meta-classifier. The combination approach is very simple: given an original question q _o, we compute a score s(q _o, q _s, a _s) for each QA pair 〈q _s, a _s〉, and then we sum these scores for the n systems being combined as follows:

$$r(q_o, q_{s}, a_{s}) = \sum _{i=1}^{n} s_i(q_o, q_{s}, a_{s}) $$

where s _i(q _o, q _s, a _s) is the score for the ith system in the combination.

We experimented with three versions of s _i(q _o, q _s, a _s): (i) reciprocal rank, (ii) arithmetic rank, and (iii) min–max normalized score.

The reciprocal rank score is defined as follows:

$$s_i^{\mathrm{rr}}(q_o, q_{s}, a_{s}) = \frac{1}{\mathrm{rank}_i(q_o, q_{s}, a_{s})} $$

where rank_i(q _o, q _s, a _s) is the rank that the ith system assigned to the QA pair 〈q _s, a _s〉 with respect to the original question q _o.

We also tried a scoring function based on arithmetic ranks, which do not decrease as fast as the reciprocal rank:

$$s_i^{\mathrm{ar}}(q_o, q_{s}, a_{s}) = 1 - \frac{\mathrm{rank}_i(q_o, q_{s}, a_{s}) - 1}{30} $$

but it did not improve over using the reciprocal rank.

We further tried a scoring function based on the actual numerical score, after min–max normalization:

$$s_i^{\mathrm{sum}}(q_o, q_{s}, a_{s}) = \frac{r_i(q_o, q_{s}, a_{s}) - \min }{\max - \min } $$

where r _i(q _o, q _s, a _s) is the score that the ith system gave to the QA 〈q _s, a _s〉, and min and max are the minimum and the maximum value of the scores it produced for all pairs 〈q _s, a _s〉 with respect to the original question q _o.

Using this latter score yielded slightly worse results, probably due to the different systems operating on different scales when providing the real-valued scores, which the min–max normalization could not quite fix. In contrast, using the reciprocal ranks works as a simple scale-invariant calibration of the scores of the individual systems (Severyn et al. Reference Severyn, Moschitti, Tsagkias, Berendsen and de Rijke2014).

The results for this system combination using the sum of reciprocal ranks are presented in Figure 6. On the x-axis, we show the number of systems combined, and on the y-axis, we show MAP, AvgRec, and MRR scores. We also display, as the baselines for the comparison, the scores of the best individual system on each evaluation measure.

Fig. 6.

MAP, MRR, and AvgRec for the simple combination of thirteen systems outputs.

We can see that the best results are achieved when combining the top-five systems, where the improvements over the best individual system are sizable: over three points in terms of MAP and MRR, and over four AvgRec points, absolute. In most cases, the combined system performed better than the best individual system, which shows that there is clearly room for further improvement for the individual systems.

Note that this combination uses information about which system performs best in the test set when deciding which n systems to combine. Of course, this information would not be available in a real combination scenario. Consequently, we are not claiming that the best results from Figure 6 can generalize to unseen datasets. This experiment merely allowed us to show that the outputs of the systems are uncorrelated to the extent of allowing sizable improvements when combined appropriately. The next subsection deals with learning a more realistic meta-classifier.

5.2 Tuned combination

The systems that participated in the competition are obviously not equally good, and thus it might be a good idea to learn different weights for different systems. Therefore, we performed another experiment where: (i) we combined all thirteen systems rather than just the top n, (ii) we weighted the relative contributions of each system (we learned the best weights automatically using cross-validation), and (iii) we used both the system’s scores and the corresponding ranks as features (based on the three scores from the previous section).

In particular, we trained a meta-classifier with an SVM-based learning-to-rank algorithm (SVM-rank), which, given two QA pairs that answer the same question, predicts which pair is a better answer, i.e., should be ranked higher. We train and evaluate the model using five-fold cross-validation on the test set. As we do not have access to the individual systems that participated in the competition, we could not generate predictions for the training or for the development datasets. Thus, we opted for cross-validation on the testing dataset, which allowed us to compare our results to those of the participating systems, as well as to the results in the previous experiment. We extracted and used three features from each of the thirteen systems we were combining, namely the three scores from above $s_i^{\mathrm{rr}}(q_o, q_{s}, a_{s})$, $s_i^{\mathrm{ar}}(q_o, q_{s}, a_{s})$, and $s_i^{\mathrm{sum}}(q_o, q_{s}, a_{s})$ for each system i. This yields 13 × 3 = 39 features, to which we further add three more features, namely the sums of each of the three scores, calculated over all thirteen systems that are being combined.

The results are shown in Table 3. The first two lines show baselines: the best individual system, and the simple uniform combination for all thirteen systems from before. The following lines show the results for the tuned combination using (a) the 3×13 features only, and (b) the 3×13 features plus the three sums. We can see 2.5+ points of absolute improvement in terms of MAP, 3.5+ in terms of AvgRec, and 1.5+ in terms of MRR (the three extra sums seem to have minor effect overall).

Table 3.

Results from the tuned system combination experiments

Overall, the results of the above two experiments show that the systems provide uncorrelated scores and rankings, which are in turn based on potentially uncorrelated features and learning algorithms, and thus that there is a large space for further improvement, i.e., the task is far from being solved.

6.1 Analysis of difficult cases

We manually analyzed some examples that were especially hard for the individual systems. In order to select the examples, we divided the test cases into positive (i.e., Direct or Related QA pairs, according to the gold standard annotation) and negative (i.e., Irrelevant QA pairs, according to the gold standard). We then sorted all test examples in the positive and in the negative sets by a measure of difficulty, and a native speaker of Arabic who has strong linguistic background studied the top twenty examples in each list. The difficulty measure for a particular example is simply the number of systems, from the set of thirteen in Table 2, that got it wrong. Note that this is not a classification task but a ranking task. Thus, ‘getting a positive example wrong’ means that the system ranked it too low in the list of thirty QA candidates. For a negative example, it is just the opposite, i.e., the system ranked the example too high. The position in the rank that defines the border between low and high is the number of positive examples, according to the gold standard, in the set of thirty QA candidate pairs.

We conducted the analysis separately for the two sets below. For completeness, Table 4 (in appendix) contains the list and the classification of all positive and of all negative examples that we manually analyzed in this study.

Table 4.

IDs of the most difficult examples that were manually analyzed. They are grouped according to the discussion in Section 6

6.2 Contribution of syntactic information

The system results presented in Section 4.3 showed that ConvKN can improve the basic accuracy of word features by 5.52 MAP points using syntactic information (see rows 2 and 7 in Table 4.3). In this section, we analyze and provide an explanation of such remarkable impact on the reranker. For this purpose, we studied correct examples that were ranked in the top position by ConvKN when using TKs, i.e., using the ϕ_bow(q _o, q _s, a _s) + ϕ_tk(q _o, q _s) representation and, at the same time, ranked low by the ConvKN basic system, i.e., ϕ_bow(q _o, q _s, a _s), which corresponds to the ConvKN Contrastive 1 submission.

Below, we present an example in which the related question q _s is correctly ranked on top by ConvKN, but very low by ConvKN contrastive 1(rank position 21). This is the same example displayed in Figure 5

At first glance, the example would not look complicated to be solved with standard BOW-based approaches using lexical similarities, as the two questions share several terms: treatment, acne, effect, monthly, cycle, etc., i.e., all non-stop words are matched except for Roaccutane and Curacne. However, the number of question/answer pairs these words occur in (a sort of document frequency) are very high: (treatment) 5,996 occurrences, (acne) 372, (youth) 349, (cycle) 4,757, (monthly) 3,435, and (effect) 841, also relatively to the total number of pairs, i.e., 30,411. Therefore, according to the fundamental findings in IR regarding the low indexing capacity of highly frequent terms, they produce low similarity scores, which are not enough for the ranker to assign a higher position to such an example.

Basically, the learning algorithm will observe that such features have high score for both positive and negative examples, which would preventing it from learning useful model parameters from such examples. In contrast, a syntactic approach can intuitively measure the example similarity in terms of the syntactic structure of the two questions, thus creating precise patterns that can detect the difference between two potentially related questions. In particular, the algorithm can find specific patterns in the related questions that are distributed differently between positive and negative examples even if the terms are uniformly distributed. In the following, we explain in more detail the syntactic model used by ConvKN, analyzing the patterns it can capture to better support our hypothesis above.

Why the syntactic model works

As stated before, Figure 5 shows the syntactic trees of the original and the candidate questions discussed in the previous subsection. These parse trees are automatically obtained with the Stanford Arabic syntactic parser. The red arrows indicate a matching between words from the two questions (e.g., Does, treatment, or effect), whereas the blue arrows are drawn to connect entire noun phrases or clauses that are partially matched (e.g., REL-NP, REL-PP). The labels of these tree constituents are augmented with the prefix ‘REL-’ to mark the connection between the syntactic trees. The two syntactic trees with the links between words and constituents form a directed acyclic graph.

Graph kernels (Vishwanathan et al. Reference Vishwanathan, Schraudolph, Kondor and Borgwardt2010) can measure the similarity between the graph in Figure 5 and any other graph from the training or test pairs. Thus, the kernel can use any subpart of the graph as rich, structured features, e.g., the lexico-syntactic patterns in Figure 7. Note that the structures that result from removing the lexical nodes, as well as any subtree, are more general patterns that are also used by the graph kernel as features. The more general structures help generalize the features, and provide the kernel-based learning with a back-off mechanism, from specific to more general features.

Fig. 7.

Some patterns extracted from both parse trees of Figure 5: any pair of such fragments is a pattern for a pair of questions.

These structurally-rich features are rather useful to solve the problem of high frequency terms, which are not handled correctly by the non-syntactic version of ConvKN. For example, the following question, which is unrelated to our q ₀:

1. q _s:

   

2. q _s: The question peace be upon you and God’s mercy and blessings. I have read many consultations related to what’s called hirsutism. I suffer from the same problem but lightly. . . But I don’t suffer from acne and my monthly cycle is regular. Please advise for any treatment and thanks

match many terms of q _o and q _s but they do not have the same syntactic patterns and thus according to the syntactic models are different.

It should be noted that, as explained in Section 4.2, the kernel we used is not a graph kernel, it is a summation of separate TK applied to the original and candidate trees, respectively. We applied this solution because TKs are much more efficient than graph kernels, which are computationally too expensive in our problem setting. As shown in related work on question answering, the ‘REL-’ extended labels can work as a good surrogate of the red and blue edges connecting the two trees in the graph (Severyn and Moschitti Reference Severyn and Moschitti2012, Reference Severyn and Moschitti2013; Tymoshenko and Moschitti Reference Tymoshenko and Moschitti2015). These labels can signal when a node is connected to another node. Although this information does not entirely replace the graph edges between trees, it has been shown to be rather effective. Additionally, TKs were shown to outperform the approximate versions of graph kernels that can be applied in practice, such as incomplete graph kernels (Filice, Da San Martino and Moschitti Reference Filice, Da San Martino and Moschitti2015).

Robustness of the syntactic model

One common concern arising when parsing Web text is the robustness of the parser. Clearly, non-conventional and disfluent language can impact the parser performance dramatically. Indeed, the syntactic trees shown in Figure 5 are only partially correct. For example, the syntactic tree for q _o should look like the tree depicted in Figure 8.

Fig. 8.

Correct parse tree of the question q _o in Section 6.2. Compare with the incorrect upper tree in Figure 5.

The main reason for the parser to fail was: (i) the informal language used by the forum users, and (ii) the flexibility of Arabic grammar, which allows free word order. In particular, the word effect, which in English would have been placed close to the auxiliary does, occurs far from it. This makes detecting the syntactic dependencies with the word effect very challenging. Indeed, the dependency was mistaken for both questions, q _o, and q _s.

The last observation is important as it suggests that the same types of difficult cases, probably occurring in similar sentences, tend to generate the same types of incorrect parse trees. Systematic errors can be still useful for a kernel model as they correspond to patterns that can correctly discriminate related versus unrelated questions. In the example above, effect is mistakenly connected with youth acne, leading to the wrong phrase ‘youth acne effect’, in both trees. Still, the fact that the error is repeated in both trees helps the algorithm to establish that such questions are related. In other words, the syntactic approach used with TKs, which explore all possible patterns, is also rather robust: (i) among many patterns, the learning algorithm can select those that are useful for characterizing positive versus negative examples, and (ii) even if the patterns are not exactly those observed in correct parse trees, the approach is still able to use the information from partially correct parse trees, as similar errors tend to generate similar structures.