{'fraction_non_alphanumeric': 0.03202201933404941, 'fraction_numerical': 0.010405477980665951, 'mean_word_length': 4.483710657095528, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Matching Questions and Answers in Dialogues from Online Forums

Matching question-answer relations between two turns in conversations is not only the first step in analyzing dialogue structures, but also valuable for training dialogue systems. This paper presents a QA matching model considering both distance information and dialogue history by two simultaneous attention mechanisms called mutual attention. Given scores computed by the trained model between each non-question turn with its candidate questions, a greedy matching strategy is used for final predictions. Because existing dialogue datasets such as the Ubuntu dataset are not suitable for the QA matching task, we further create a dataset with 1,000 labeled dialogues and demonstrate that our proposed model outperforms the state-of-the-art and other strong baselines, particularly for matching long-distance QA pairs.


Introduction
Question motivated dialogues are very common in daily life and they are rich sources for question-answer (QA) pairs. For example, in an online forum for health consultations, both the doctor and the patient tend to ask and answer questions to narrow down the information gap and reach the final diagnosis or recommendations. Matching QA pairs can help track the final answers from the doctor to the original patient question and is valuable for the medical domain.
QA matching is an important part of analyzing discourse structures for dialogue comprehension. Asher et. al [2] shows that in online dialogues where participants are prompted to communicate with others to achieve their goals, 24.1% of the relations between elementary discourse units are QA pairs. Questions and answers are the main components of dialogue acts [31], providing key features for dialogue summarization and decision detection [15]. Besides, figuring out the QA relations between these utterances can provide question answering models [19,33,9] with high-quality QA pairs and contribute to the exploration of proactive questioning [38].
However, many challenges exist. While it is relatively easy to distinguish between questions and non-questions 3 , the non-questions may contain not only valid answers, but also chit-chats and other informative statements. It is also a common phenomenon that a long and complete answer is broken up into several turns such as {U5,U6,U8,U10} in Figure 1. Due to factors such as the network delay and different typing speed, the dialogue sequences are always mix-matched. Moreover,"personalized" orthography, ellipses, abbreviations, and missing punctuations are all difficulties for QA matching. 1   In this work, we focus on the task of matching questions and answers in two-party multi-turn dialogues. We found that the distance between the question and its answers is not only caused by the mixmatching and fragmentation mentioned above, but also by the very nature of the question. Some questions can be answered directly based on personal knowledge, such as U3, while others can not. For instance, when a patient asks questions such as "what's wrong with me" or "what should I do" just like U1, the doctor often has to ask follow-up questions {U2,U3} to seek additional information in order to give the final diagnosis or recommendation (U11). This often has to be done with several rounds of communication. We call this kind of QA pairs incremental QA. Such QA pairs often form the main idea of a dialogues or sub-dialogue, critical for dialogue comprehension. The answers are inherently far from the question (distance ≥ 3 4 ), aggravating the difficulty of matching such pairs. Roughly, we can categorize QA pairs according to the distance between them. When distance ≤ 3, we call them short-distance QA pairs (SQA); otherwise, long-distance QA pairs (LQA). It is obvious that matching LQAs is more difficult than SQAs. We assume that a two-party multi-turn dialogue contains two types of turns, questions (Q) and non-questions (NQ), which are labeled in advance 5 . Our task is to identify all answers from the set of NQs to a given Q.
Previous methods [10,12,20] on the task suffer from a major weaknesses: while classifying a pair of turns, they ignore the con-text of the turns in the dialogue. Meanwhile, their pre-defined features such as question words and answer words, are already implied by the Q and NQ labels in our definition and hence are not suitable for our task. He et al. [18] improves the above methods with a recurrent pointer network (RPN) model which takes the whole dialogue as an input. Their model was evaluated on a close-source customer service dialogue dataset. Although their model makes use of the context, they treat every utterance in the context equally with RNN-based networks which fails to capture the influences between turns especially with long distance. Besides, it encodes the distance information implicitly which downplays the effect of distance between the utterances. According to our experiments, none of the above approaches perform well on LQA pairs.
In this paper, we bring the dialogue context into the above simple models. For a given pair of Q and NQ to be matched, the context is defined as history, refering to the utterances between the Q and NQ. The critical part of our model is two simultaneous attention mechanisms that combine the history in a mutual way. Existing dialogue datasets, such as the Ubuntu dataset, do not contain the QA matching labels. Moreover, they are either not two-party dialogues, or do not contain long distance QA pairs. Therefore, we develop a new dataset based on a Chinese online medical forum. We conducted experiments both on this dataset and the part of labeled Ubuntu dataset 6 .
Our main contributions are as follows: • We aggregate dialogue history and distance information into a new deep neural QA matching model. We show that distance is an important feature when encoded explicitly, and that utterances between Q and A can be effectively captured by a mutual attention mechanism (Section 3). • Since there is no open source dialogue datasets designed for QA matching task, especially for LQAs, we construct a reasonably sized dataset and release it to the research community (Section 4). • The experimental results show that our proposed method outperforms other strong baselines, especially on LQAs. The techniques developed here are generic and can be applied to other types of online dialogues (Section 6).

Problem Definition
Our work aims at identifying the response turns to a question turn in a multi-turn, two-party dialogue. Given a dialogue sequence with T turns: where R denotes the role, identifying which party utters the turn. L ∈ {Q, N Q}, and U is a sequence of words in natural language. Our job is to match each (Q, Ui) with corresponding (N Q, Uj), where: The distance of a Q-NQ pair (Ui, Uj) is j−i. We define the history as the turns {Ui+1, Ui+2..., Uj−1} which are located between the Q and NQ. The intuition will be explained in Section 3.2.
Recent work by He et al. [18] considers a slightly different QA alignment problem where one answer can be matched with multiple questions. However, in this paper, we assume that if a question is asked repeatedly, the answer should be matched to the nearest question and all earlier ones are disregarded. In our definition, a Q can match nothing (U9) or several NQs (U2). From the viewpoint of a NQ, it is either matched, or not matched, with a Q (such as U7). When a NQ is matched to a Q, it is considered as an answer (A). Otherwise, it's considered as others(O).

Approach
We propose an attention-based neural network model for QA matching in multi-turn dialogues between two parties. The model consists of four components (shown in Figure 2): Sentence Encoder transforms the natural language turns into sentence-level embeddings. Mutual Attention combines history turns based on two simultaneous attention mechanisms. Match-LSTM is used to compare the processed sentence pair word by word. Prediction Layer incorporates the distance information and calculates the matching probability. After calculating the probability for all Q-NQ pairs in a dialogue, a greedy matching algorithm is employed to match each NQ to zero or one Q.

Sentence Encoder
Given an input turn as a sequence of words in natural language, we generate a neural representation using an LSTM [16]. The sentence encoder consists of pretrained word embeddings which are fed into a single LSTM layer. The output of all the hidden states or the last hidden state can both be regarded as the sentence-level embedding for this turn.
With the sentence encoder, we can get the neural representations for a Q-NQ pair and its history as follows: where the number of words in Q and N Q are N and M respectively. hi represents the hidden state of each word. HRQ and HRNQ represent the history turns with the same role label as Q and N Q respectively. A and B are the number of turns in HRQ and HRNQ, and dt is the last hidden state of each turn. Superscripts p and q are used to distinguish Q and N Q. Here, we divide the history turns into two parts to support the idea of mutual attention between Q and NQ in the following subsection. The intuition for using different granularity of sentence embeddings is that we hope to keep more information for more important turns. Therefore, in order to calculate the matching score between a Q-NQ pair, we preserve all the hidden states for Q and NQ. The last hidden state of each turn in history is used to provide auxiliary information.

Mutual Attention
To improve the prediction for each Q-NQ pair, naturally we take advantage of the dialogue history, especially the turns between Q and NQ. This idea comes from two considerations: i) if Q has been partially answered by another NQ in the history, then we should further explore whether the current NQ is a supplementary answer; ii) if there exists another Q which is closer to the NQ in both distance Besides, it should be noted that the question and matched answers should definitely be uttered by different parties. In other words, the QA relations in a dialogue is focusing on the process of narrowing down the information gap between two parties, where the information interaction between parties is critical. So, we further divide the history into two parts: HRQ and HRNQ by different role labels as mentioned above. Q is expected to interact with HRNQ while N Q is expected to interact with HRQ.
Borrowing the idea from Wang et al. [36], we use two attention mechanisms to incorporate the history information into Q and NQ individually in a unified manner. For example, when dealing with the Q-NQ pair {U 2, U 10}, HRQ = {U 3, U 7, U 9} and HRNQ = {U 4, U 5, U 6, U 8}. The neural representation of U 2 attends to HRNQ and U 10 attends to HRQ simultaneously. In other words, Q and NQ "mutually" attend to each other's history. Mathematically, as for Q and HRNQ: the Q containing historical information can be obtained via soft alignment of words in the question Q = [h q 1 , h q 2 , ..., h q N ] and history turns HRNQ = {d p 1 , d p 2 , ..., d p B } as follows (see Part I in Figure 2): where c q i = att(h q i , HRNQ) is an attention-pooling vector of the whole history(HRNQ), and v and W are the weights: Each word representation in Q dynamically incorporates aggregated matching information from the history HRNQ.
The final representations of the question and the non-question after mutual attention are Q = [u q 1 , u q 2 , ..., u q N ] and N Q = [u p 1 , u p 2 , ..., u p M ]. Each vector in Q and N Q not only represents the original turn meaning but also contains dialogue context. The effects of different choices of turns in history and the ways of aggregating the history will be discussed later.

Match-LSTM
We follow the work of Wang and Jiang [35] and adopt match-LSTM to capture the features between the processed Q and N Q word by word.
As Part II of Figure 2 shows, a one-layer LSTM is used to better fuse the history information at different steps. We thus obtain We introduce a series of attention-weighted combinations of the hidden states of the question, where each combination is for a particular word in the non-question. The sentence-pair representation P = {pi} M i=1 is calculated with attention mechanism as follows.
where ci = att(Q, f p i , pi−1) is an attention-pooling vector of the whole question(Q): Finally, we use pM to represent the whole Q-NQ pair which is used for predicting the final matching score.

Prediction Layer
At the last step, we use a fully-connected (FC) layer with softmax to do binary classification, which indicates whether this pair of turns has QA relation.
Driven by the intuition that distance is a critical feature for matching QA pairs, we explicitly add the distance at the end of our model to preserve its effectiveness. The distance d is defined as a 10dimensional one-hot vector, where the position of 1 is equal to the distance. For example, if the distance is 4, then the 4th dimension of the vector is set to 1. If d ≥ 10, then the 10th dimension is set to 1.
Finally, the probability is calculated as follows: In sum, the input of our model is a Q and NQ with associated information (history and distance), and the output of model is the probability which indicates if the Q is the matched question of the NQ. Hence, the loss function is the cross entropy between the predicted probability P (Q, N Q) and the ground truth. The model can be seen as a binary classification model and all the parameters are trained altogether except the pretrained word embeddings.

Greedy QA Matching
Based on the trained model, every NQ now has a matching probability with every Q before it in the dialogue sequence. The greedy algorithm matches the NQ with the Q with maximum probability if that probability exceeds 0.5. The threshold is set to 0.5 because our model is actually a two-class classifier.

Dataset Construction
Previous QA datasets are in the form of independent QA pairs [39] and do not provide surrounding dialogue context. Although He et al. [18] solved a similar problem, their customer service dataset is not open to public due to privacy concerns. Wei et al. [37] published their dialogue dataset collected from an online forum. However, their work focuses on the dialogue policy learning and the data doesn't preserve the original utterances.
There are also no published qualified dialogue datasets for the QA matching task. The IRC dataset [13] and Reddit dataset [20] are both multi-party dialogues instead of two-party dialogues. Twitter Triple Corpus [30] and Sina Weibo [27] are not multi-turn dialogues with only two or three turns. MultiWOZ 2.0 [4], CamRest676 [26], and Stanford Dialog Dataset [14] are multi-turn dialogues with dialogue act annotations but these QA pairs appear next to each other. If we shuffle the well-ordered dataset randomly or by some rules, it's unnatural and incorrect because the original dialogue context is destroyed as shown in Table 1. The two-party Ubuntu dataset [23] meets these requirements and we annotated 1000 dialogue sessions. However, the statistics and experiments show that the Ubuntu dataset is not a good QA matching dataset especially for long distance QAs, given the limited manpower for annotation. More details will be shown in Section 6. Hence, we create a new dataset suitable for this task. Nearly 160,000 distinct dialogues are collected from an online health forum 7 . All the personal information was removed in advance by the website. After some basic data cleaning methods, we labeled 1000 randomly selected two-party multi-turn dialogues with Q (question), A (answer) and O (others) labels. A small amount of turns (0.24%) 7 An dialogue example online: https://www.120ask.com/shilu/ 0cjdemaflhj6oyw9.html are considered by the annotators to be both a question and an answer, and these are treated as questions uniformly. We reconstructed the labeled dialogues into Q-NQ pairs with distance, history and binary golden label used for our models. A NQ from a party is paired with every earlier Q from the other party. If the pair is a QA pair, it is labeled as True(T). Otherwise, it is labeled as False(F). The distribution of positive and negative data on three datasets is shown in Table 3.   Label   Dataset  Train  Development  Test   True  7540  1226  2116  False  80631  14889 23893 Table 3. The distribution of positive and negative Q-NQ pairs on three datasets.

Experiment Setup
In this section, we first list the baselines and the ablations of our full model. Next, we define the evaluation metrics. Finally, we show the details of hyperparameters in our model.

Baselines
We mainly have the following four types of baselines.
• Greedy strategy (GD) A simple baseline Greedy is that, when a question is posed by RQ, we can directly match the following several NQs said by RQ as the answers. It stops when meeting another Q or a turn said by RQ. There are a few variants in this methods. GD1 selects only one satisfying answer, and GDN selects multiple satisfying answers. The methods with Jump (J) skip the non-question turns uttered by RQ when matching the NQs.
• Distance A simple model takes a 10-dimensional one-hot distance vector as the input of a fully-connected layer and outputs the score for each Q-NQ pair. • Word-by-word match LSTM (mLSTM) This model is proposed by Wang et al. [35], used for natural language inference. It performs word-by-word matching based on an attention mechanism, with the aim of predicting the relation between two sentences. • Recurrent Pointer Network (RPN) The model proposed by He et al. [18] is the previous state-of-the-art method for a similar task, and is implemented with some modifications to fit our task. We use two parallel RPN to distinguish questions from two parties. Comparing the classification loss and regression loss proposed in this paper, we choose the one that performs best on our test set.

Our Models
By disabling some of its components, our model comes in three main variants: • Distance Model (DIS) removes the mutual attention. It directly puts Q and NQ with the distance into Part II of the full model in Figure 2.

Evaluation Metrics
Once we have identified all of the QA pairs, we count the true positive, false positive and false negative for each question. To measure the quality of the matched QA pairs, micro-averaging precision (P), recall (R) and F1-score (F1) are calculated, with all questions in test dataset treated equally. Another metric, accuracy (Acc), is used when evaluating QA pairs matched with a specific distance. Accuracy is calculated by the percentage of ground truth QA pairs that are predicated positive by the models.

Implementation Details
We use Jieba 9 to do Chinese word segmentation and pre-train the 100 dimentional word embeddings with Skip-gram model [24] on all of the dialogues (including the unlabeled ones) we have collected online. For our proposed models, we use LSTM with hidden state size of 128 and 256 for Part I and Part II of the model respectively. We adopt Adam optimizer with 0.001 learning rate and 0.3 dropout. Learning rate decay is 0.95 and the training process terminates if the loss stops reducing for 3 epochs. All experimental results are averaged over three runs.

Results and Analysis
In this section, we show the end-to-end results and ablation tests for the specific architectural decisions.

Overall Performance
The main results of different models are shown in  Table 4. The end-to-end performance of all methods on test dataset. Scores marked with are statistically significantly better than the RPN with p < 0.01. this task. Note that human performance is not perfect due to inherent ambiguities in dialogues.
The results of the rule-based methods are not bad, which indicates that questions are actually followed by their answers in many cases. The GDN increases the F1-score to 69.57% compared with Greedy-1 because it can solve the case of simple fragmented answers. For GDN+J, the recall is the best among all the methods while precision and F1-score suffer. The reason is that GDN tends to match NQ with Q as much as possible, so many chit chats will be regarded as answers, which reduces the precision.
Model mLSTM underperforms because it is difficult to solve the QA matching problem with only two short texts without history. The word distribution between the questions and answers are quite different and maybe unrelated without background knowledge. Distance achieves good scores which shows that the distance is a very important factor when identifying QA relations in dialogues. People tend to answer a question the moment they see it except in the case of incremental QAs. RPN achieves competitive results. It mainly benefits from taking the dialogue session as a whole which contains all the information in a session.
Our proposed models achieve the best results compared with above models. The HDM improves the F1-score to 77.43%, significantly better than RPN by t-test with p < 0.01. Although the recall of HDM is not better than GDN+J and the precision is lower than DIS, the overall quantity and quality of QA pairs identified are the best, shown by the highest F1-score. In addition, the comparable results achieved by HTY demonstrate that QA matching not only depends on the distance but also relies on the history information. This shows that HDM model successfully combines both the distance and history information.

Variable Distance Matching
According to the results above, we can find that the model Distance, RPN, DIS, HTY and HDM are competitive. Thus, we further analyze the accuracy of these five models on variable distances.  Table 5 shows that Distance and DIS work well on SQAs but deteriorate rapidly as the distance grows, indicating that relying solely on the distance information is insufficient. On the other hand, using dialog context, the matching accuracy of RPN and HTY is generally lower on SQAs but higher on LQA. Our full model (HDM) is actually a good trade-off by incorporating both distance and history information. This also accords with the decision process made by human annotators.
We also conduct a Z-test on the results to show that the improvements on the LQAs are statistically significant even with a small sample size.

Ablation Tests
We justify the design of our model in the following two aspects.

Different definitions of history
To show the effectiveness of using the turns between Q and NQ as history, we devise variants on the HDM model for comparison: • Q-history Model (QH) has the same structure as HDM where the history is all the turns before Q. • A-history Model (AH) has the same structure as HDM where the history is all the turns before NQ.
The main results with different choices of history are shown in Table 6. Our final model (HDM) outperforms QH and AH, indicating that the turns between Q and NQ are significant when figuring out the relation of a Q-NQ pair. The turns before Q is actually not that important for matching Q and NQ. Although there is an overlap between the history we defined and the turns before NQ, the turns before Q brings more noises than benefits for the end-to-end performance. This suggests that our definition of history as the turns between Q and NQ is reasonable and effective.

Different ways of attending to the history
To evaluate the effectiveness of mutual attention for aggregating the history, we devise variants of the HDM model for comparison: • Non-mutual Model (NM) has the same structure of HDM where Q attends to HRQ and N Q attend to HRNQ. • Identical history model (ID) has the same structure of HDM where Q and N Q attend to the same history HRQ HRNQ.
The main result in Table 7 reveals that our choice of separating the history by role label and mutually attending to each other does work. The full model (HDM) consistently outperforms both NM and ID.
For the ablation test on different ways of attending to the history, we conclude that NM is better than ID. It's due to better understanding on individual speakers which can help the understanding of the dialogue, similar to the idea in Shi and Huang's work [28]. Our work targets the QA relations in dialogues which are more related to the interactions between speakers. As a result, our full model is better than NM.
The difference between our full model HDM and ID is that in ID both Q and NQ attend to all turns in the history regardless of who uttered those turns, whereas HDM employs a mutual attention mechanism that distinguishes turns by their speakers. Specifically, the Q only attends to those turns uttered by the NQ speaker, while the NQ attends to those turns by the Q speaker. This resembles to some extent the firm attention in Amplayo's paper [1]. This will help the model to focus on the interactions between speakers.

Example Outputs
To provide a better understanding of the behavior of our models, we include an example output in Table 8. It contains both LQAs and SQAs. In this case both HYD and HDM predict QA relations better than the baseline RPN. As for SQAs, all of the models perform well. However, the DIS model is obviously not capable of matching LQA pairs. It indicates that the distance information sometimes hurts the performance of HDM on matching LQA pairs.

Results on the Ubuntu Dialogue Corpus
The Ubuntu dataset [23] is a large unannotated dialogue corpus designed for next utterance classification and dialogue generation. It is extracted from multi-party dialogues, while conversation disentanglement is still an unsolved problem. Therefore, many dialogues in this dataset don't make much sense because the two parties are not actually talking to each other (they were talking to a third party whose utterances were removed). It maybe a good dialogue resource with 930,000 dialogues, but it is impossible to label such large amount of dialogues.
We randomly sampled 1000 dialogues each with more than 10 turns. Then we annotated the extracted corpus with (Q, A, O) labels as mentioned above. If the current dialogue contains no Q-NQ pairs, it is replaced by a new dialogue with similar number of turns. Finally, we collected 1000 annotated dialogues. The QAs in Ubuntu corpus mainly focus on step-by-step operations and the dialogues are lack of LQAs. The results are showed in Table 9.
The results of Distance and GDN achieve the top-2 highest F1 score, which is consistency with the fact that 41.95% of questions have no answers and 79.55% of the QA pairs are consecutive in the dialogue. However, it still shows the effectiveness of our full model HDM, which achieves the competitive results to the best results.

Related Work
Detection of QA pairs from online discussions has been widely researched these years. Shrestha and Mckeown [29] learned rules using Ripper for detecting QA pairs in email conversations. Ding et al. [10], Kim et al. [21] and Catherine et al. [6] applied the supervised learning method including conditional random field and support vector machine. Cong et al. [8] proposed an unsupervised method combining graph knowledge to solve the task. Catherine et al. [5] proposed semi-supervised approaches which require little training data. He et al. [18]  customer service. However, the tasks mentioned above are all different from ours. We identify QA pairs from two-party dialogues on online discussion forum, and focus especially on long-distance QA pairs. Besides, our dialogue is constrained between two roles who can both utter questions and answers.
There exists several methods on other tasks which can be adapted to our QA matching problem. Feature-based method is popular for solving many NLP problems. In the work of Ding et al. [10], Wang et al. [34] and Du et al. [12], they examined lexical and semantic features in two sentences for QA matching. However, the features such as common question words and roles have already been explicitly annotated in our data. Besides, other features such as special word occurrence or time stamp are unavailable here. According to the data, we considered the distance as the most important feature and implemented this feature-based method as one baseline. Recent researches using deep neural networks have increased a lot. He and Lin [17] and Liu et al. [22] used the sentence pair interaction approach which takes word alignment and interactions between the sentence pair into account. Attention mechanism was also added for performance improvement [25,35,7]. We also use word alignment and interactions to calculate the QA similarity. Specially, we adopt attention mechanism to solve the LQA cases.
There are other kinds of alignment problems such as temporal sequences alignment. Video-text alignment is one of the temporal assignment or sequence alignment problems. Previous work automatically provided a time (frame) stamp for every sentence to align the two modalities such as [3] and [11]. Bojanowski et al. [3] extended prior work by including the alignment of actions with verbs and aligned text with complex videos. Dynamic time warping (DTW) is anothor algorithm for measuring similarity between two temporal sequences. It's also widely used in video-text alignment task [11], speech recognition task [32].

Conclusion
In this paper, we focus on identifying QA pairs in two-party multiturn online dialogues based on turns with Q or NQ labels. Our proposed models achieve the best accuracy overall, and perform particularly well on LQAs. We also discuss the model decisions of using two attention mechanisms in a mutual way and the definition of history. Our future work will focus on more discourse relations in dialogues. Utilizing out-of-domain knowledge is another research direction for utterances matching task, especially for health-related dialogues.