We study the interpretability issue of task-oriented dialogue systems in this paper. Previously, most neural-based task-oriented dialogue systems employ an implicit reasoning strategy that makes the model predictions uninterpretable to humans. To obtain a transparent reasoning process, we introduce neuro-symbolic to perform explicit reasoning that justifies model decisions by reasoning chains. Since deriving reasoning chains requires multihop reasoning for task-oriented dialogues, existing neuro-symbolic approaches would induce error propagation due to the one-phase design. To overcome this, we propose a two-phase approach that consists of a hypothesis generator and a reasoner. We first obtain multiple hypotheses, i.e., potential operations to perform the desired task, through the hypothesis generator. Each hypothesis is then verified by the reasoner, and the valid one is selected to conduct the final prediction. The whole system is trained by exploiting raw textual dialogues without using any reasoning chain annotations. Experimental studies on two public benchmark datasets demonstrate that the proposed approach not only achieves better results, but also introduces an interpretable decision process. Code and data: https://github. com/shiquanyang/NS-Dial . Neural task-oriented dialogue systems have enjoyed a rapid progress recently (Peng et al., 2020; Hosseini-Asl et al., 2020; Wu et al., 2020), achieving strong empirical results on various benchmark datasets such as SMD (Eric et al., 2017) and MultiWOZ (Budzianowski et al., 2018). However, most existing approaches suffer from the lack of explainability due to the black-box nature of neural networks (Doshi-Velez and Kim, 2017; Lipton, 2018; Bommasani et al., 2021), which may hurt the trustworthiness between the users and the system. For External Knowledge Base (KB) Cityroom Price_range Moderate Chadstone Located_in Leichhardt Cityroom Next_to Palm_Lawn Gonville_Hotel Price_range Expensive Palm_Lawn Located_in Chadstone Gonville_Hotel Located_in Moorabbin User : Can you recommend me a hotel located in Leichhardt ? instance, in Figure 1, a user is asking for a hotel recommendation at a given location. The system performs reasoning on a knowledge base (KB) and incorporates the correct entity in the response. However, when the system fails to provide the correct entities, it would be difficult for humans to trace back the issues and debug the errors due to its intrinsic implicit reasoning nature. As a result, such system cannot be sufficiently trusted to be deployed in real-world products. To achieve trustworthy dialogue reasoning, we aim to develop an interpretable KB reasoning as it's crucial for not only providing useful information (e.g., locations in Figure 1) to users, but also essential for communicating options and selecting target entities. Without interpretability, it's difficult for users to readily trust the reasoning process and the returned entities. To tackle this challenge, we present a novel N euroS ymbolic Dial ogue framework ( NS-Dial ) which combines representation capacities of neural networks and explicit reasoning nature of symbolic approaches (e.g., rule-based expert systems). Existing neuro-symbolic approaches (Vedantam et al., 4918 2019; Chen et al., 2020) mostly employ a one-phase procedure where a tree-structured program composed of pre-defined human interpretable neural modules (e.g., attention and classification modules in Neural Module Networks (Andreas et al., 2016)) is generated to execute to obtain the final predictions. However, since the KB reasoning task involves a reasoning process spanning over multiple triplets in a diverse and large-scale KB, only generating and following a single program (i.e., a reasoning chain formed by KB triplets) is prone to error propagation where a mistake in one step could lead to a failure of the subsequent reasoning process and may result in sub-optimal performances. To address this, we propose a two-phase procedure to alleviate the effects of error propagation by first generating and then verifying multiple hypotheses. Here, a hypothesis is in the form of a triplet containing an entity mentioned in dialogue context and an entity within KB, and their corresponding relation. The valid (i.e., correct) hypothesis is the one that contains the entity mentioned in the ground-truth response. Once we obtain multiple hypothesis candidates during the generation phase, we employ a reasoning engine for verifying those hypotheses. For instance in Figure 1, given the user query  Can you recommend me a hotel located in Leichhardt? , in order to find the valid hypothesis, the hypothesis generator obtains multiple candidates e.g., [Cityroom, Located_in, Leichhardt] and [Gonville_Hotel, Located_in, Leichhardt] . The reasoning engine will then construct proof trees to verify them, e.g., for the first hypothesis [Cityroom, Located_in, Leichhardt] , it can be verified with the following reasoning chain in the KB: [Cityroom, Next_to, Palm_Lawn]  [Palm_Lawn, Located_in, Chadstone]  [Chadstone, Located_in, Leichhardt] . The whole framework is trained end-to-end using raw dialogues and thus does not require additional intermediate labels for either the hypothesis generation or verification modules. To summarize, our contributions are as follows:  We introduce a novel neuro-symbolic framework for interpretable KB reasoning in task-oriented dialogue systems. We propose a two-phase generating-and-verifying approach which generates multiple hypotheses and verifies them via reasoning chains to mitigate the error-propagation issue. two benchmark datasets to verify the effectiveness of our proposed model. By analyzing the generated hypotheses and the verifications, we demonstrate our model's interpretability. Task-Oriented Dialogue Traditionally, task-oriented dialogue systems are built via pipeline-based approaches where task-specific modules are designed separately and connected to generate system responses (Chen et al., 2016; Zhong et al., 2018; Wu et al., 2019a; Chen et al., 2019a; Huang et al., 2020). In another spectrum, many works have started to shift towards end-to-end approaches to reduce human efforts (Bordes et al., 2017; Lei et al., 2018; Madotto et al., 2018; Moon et al., 2019; Jung et al., 2020). Lei et al. (2018) propose a two-stage sequence-to-sequence model to incorporate dialogue state tracking and response generation jointly in a single sequence-to-sequence architecture. Zhang et al. (2020) propose a domain-aware multi-decoder network (DAMD) to combine belief state tracking, action prediction and response generation in a single neural architecture. Most recently, the success of large-scale pre-trained language models (e.g., BERT, GPT-2) (Devlin et al., 2018; Radford et al., 2019) has spurred a lot of re-cent dialogue studies starting to explore large-scale pre-trained language model for dialogues (Wolf et al., 2019; Zhang et al., 2019). In task-oriented dialogue, Budzianowski and Vulic (2019) use GPT-2 to fine-tune on MultiWOZ dataset for dialogue response generation. Peng et al. (2020) and Hosseini-Asl et al. (2020) employed a single unified GPT-2 model jointly trained for belief state prediction, system action and response generation in a multi-task fashion. However, most existing approaches cannot explain why the model makes a specific decision in a human understandable way. We aim to address this limitation and introduce interpretability for dialogue reasoning in this study. Neuro-Symbolic Reasoning Neuro-Symbolic reasoning has attracted a lot of research attentions recently due to its advantage of exploiting the representational power of neural networks and the compositionality of symbolic reasoning for more robust and interpretable models (Andreas et al., 2016; Hu et al., 2017; Hudson and Manning, 2018; Vedantam et al., 2019; Chen et al., 2019b; Vedantam et al., 2019; van Krieken et al., 2022). The main difference between neuro-symbolic vs. pure 4919 neural networks lies in how the former combines basic rules or modules to model complex functions. Rocktschel and Riedel (2017) propose a neuro-symbolic model that can jointly learn sub-symbolic representations and interpretable rules from data via standard back-propagation. In visual QA, Andreas et al. (2016) propose neural module networks to compose a chain of differentiable modules wherein each module implements an operator from a latent program. Yi et al. (2018) propose to discover symbolic program trace from the input question and then execute the program on the structured representation of the image for visual question answering. However, these approaches cannot be easily adapted to task-oriented dialogues due to the error propagation issue caused by multihop reasoning on large-scale KBs. Thus, we aim to bridge this gap by developing a neuro-symbolic approach for improving task-oriented dialogues. In this work, we focus on the problem of task-oriented dialogue response generation with KBs. Formally, given the dialogue history X and knowledge base B , our goal is to generate the system responses Y word-by-word. The probability of the generated responses can be written as: p ( Y | X, B ) = n (cid:89) t =1 p ( y t | X, B, y 1 , y 2 , ..., y t  1 ) (1) where y t is the t-th token in the response Y . The overall architecture is shown in Figure 2. We start by introducing the standard modules in our system and then explain the two novel modules afterward. We employ pre-trained language model BERT (De-vlin et al., 2019) as the backbone to obtain the distributed representations for each token in the dialogue history. Specifically, we add a [ CLS ] token at the start of the dialogue history to represent the overall semantics of the dialogue. The hidden states H enc = ( h CLS , h 1 , ..., h M ) for all the input tokens X = ( [ CLS ] , x 1 , ..., x M ) are computed using: H enc = BERT enc (  emb ( X )) (2) where M is the number of tokens in the dialogue history,  emb is the embedding layer of BERT. To generate the system response, we first utilize a linear layer to project H enc to H  enc = ( h  CLS , h  1 , ..., h  M ) that are in the same space of the decoder. We initialize the decoder with h  CLS . During decoding timestep t , the model utilizes the hidden state h dec,t to attend H  enc to obtain an attentive representation h  dec,t via standard attention mechanism. We then concatenate h dec,t and h  dec,t to form a context vector C and project it into the vocabulary space V : C = [ h dec,t , h  dec,t ] (3) P vocab,t = Softmax ( U 1 C ) (4) where U 1 is a learnable linear layer, P vocab,t is the vocabulary distribution for generating the token y t . Next, we aim to estimate the KB distribution P kb,t , i.e., the probability distribution of entities in the KB, in an interpretable way and fuse P vocab,t and P kb,t for generating the final output tokens. We follow See et al. (2017) and employ a soft-switch mechanism to fuse P vocab,t and P kb,t to generate output token y t . Specifically, the generation probability p gen  [0,1] is computed from the attentive representation h  dec,t and the hidden state h dec,t : p gen =  ( U 2 ([ h  dec,t , h dec,t ])) (5) where  is sigmoid function, U 2 is a linear layer. The output token y t is generated by greedy sampling from the probability distribution P ( w ) : P ( w ) = p gen P vocab,t + (1  p gen ) P kb,t (6) We next describe how to obtain the KB distribution P kb,t in details using the two novel modules we proposed, i.e., hypothesis generator and hierarchical reasoning engine. To compute the KB distribution P kb,t , we present two novel modules: hypothesis generator (HG) and hierarchical reasoning engine (HRE). We take the context vector C (Equation 3) as the input of HG module and generate K hypotheses H , each of which are then fed into the HRE module to generate the logical reasoning chains and their belief scores. The estimated belief scores are then served as P kb,t , giving us a distribution over the entities in the KB. Next, we describe how each component works in detail and explain how they interact with each other for generating P kb,t . Let a hypothesis be a 3-tuple of the form  [ H, R, T ] , where H and T are the head and tail entities, and R is the relation between entities. In this paper, we are interested in three types of hypotheses including the H-Hypothesis, T-Hypothesis, and R-Hypothesis. The H-Hypothesis is the structure where the tail entity T and relation R are inferred from the context and the head entity H is unknown (which needs to be answered using the KB), and it takes the form  [ , R, T ] . In a similar vein, the T-Hypothesis and R-Hypothesis have unknown tail entity T and relation R , respectively. The goal of the Hypothesis Generator module is to generate hypotheses in this triple format which will later be verified by the Hierarchical Reasoning Engine. Intuitively, a hypothesis can be determined by its content and structure. The structure indicates the template form of the hypothesis while the content fills up the template. For instance, the H-Hypothesis has its template form of  [ , R, T ]  and the content that needs to be realised includes candidate entities (i.e.,   ), and query states (i.e., the tail  T  and relation entities  R ). To this end, we employ a divide-and-conquer strategy to jointly learn three sub-components: structure prediction, query states prediction, and candidates prediction. Next, we describe each sub-component in details. Structure Prediction (SP) The goal of the structure prediction module is to determine the structure of the hypothesis (i.e., H/T/R-Hypothesis) based on the context. For example in Figure 1, one might expect an H-Hypothesis at timestep 0 . Specifically, SP uses a shared-private architecture to predict the hypothesis type. It first takes the context vector C (Equation 3) as input and utilizes a shared transformation layer between all the three sub-components to learn task-agnostic feature h share : h share = W 2 ( LeakyReLU ( W 1 C )) (7) where W 1 and W 2 are learnable parameters (shared by the structure prediction, query states prediction and candidate prediction components) and LeakyReLU is the activation function. The shared layer can be parameterised with complicated neural architectures. However, to keep our model simple, we use linear layers which we found to perform well in our experiments. SP next uses a private layer on top of the shared layer to learn task-specific features for structure prediction: h spprivate = W 4 ( LeakyReLU ( W 3 h share )) (8) where W 3 and W 4 are learnable parameters. For ease of presentation, we define the private feature transformation function as: F  : h share  h private (9) where  denotes any of the three sub-components. To obtain the predicted hypothesis structure, a straightforward approach is to apply softmax on h spprivate . However, this will break the differentiability of the overall architecture since we perform sampling on the outcome and pass it to the neural networks. To avoid this, we utilize the Gumbel-Softmax trick (Jang et al., 2017) over h spprivate to get the sampled structure type: I sp = Gumbel-Softmax ( h spprivate )  R 3 (10) where I sp is a one-hot vector and the index of one element can be viewed as the predicted structure. In this paper, we define 0 as H-Hypothesis, 1 as T-Hypothesis and 2 as R-Hypothesis. Query States Prediction (QSP) Query states are the tokens in hypothesis that need to be inferred from the dialogue history. For example, one might want to infer relation R = Located_in and tail 4921 T = Leichhardt based on the history in Figure 1. Therefore, the goal of the query states prediction is to estimate the state information (e.g., T and R in H-Hypothesis) of hypothesis. Specifically, QSP takes the shared feature h share as the input and next applies the private feature transformation function followed by Gumbel-Softmax to obtain the state tokens of hypothesis using: h qsp,kprivate = F qsp,k ( h share ) (11) I kqsp = Gumbel-Softmax ( h qsp,kprivate )  R n (12) where n is the number of tokens (entities and relations) in the KB, k  {0,1}, I 0 qsp and I 1 qsp are two one-hot vectors where their corresponding tokens in KB serve as the state tokens of the hypothesis. Candidates Prediction (CP) To generate the final hypotheses, we need multiple candidates to instantiate the structure of the hypothesis except the state tokens, e.g., Cityroom or Gonville_Hotel as candidate head entities H in Figure 1. To this end, we utilize an embedding layer  embcp to convert all the tokens in the KB to vector representations. We then compute a probability distribution over all the KB tokens using: P i = Sigmoid (  embcp ( K i )  h share ) (13) where K i is the i -th token in KB,  embcp is the embedding layer of CP, P i is the probability of the i -th token to be candidate,  denotes inner-product. We use sigmoid instead of softmax as we find that softmax distribution is too sharp making the probability between different tokens are hard to differentiate for sampling multiple reasonable candidates. Hypothesis Synthesizing The final hypotheses H are composed by combining the outputs of the three sub-components as follows: (i) We generate the hypothesis template according to the predicted structure type. For example, if SP predicts a structure type 0 which denotes H-Hypothesis, the model will form a template of  [ , R, T ] ; (ii) We next instantiate the state tokens in the hypothesis sequentially by using the outputs of QSP module. For example, if the output tokens of QSP are  Located_in  ( k =0) and  Leichhardt  ( k =1), the hypothesis will become [ , Located_in , Leichhardt ] ; (iii) Finally, we instantiate the candidate (i.e.,  ) with the top-K ( K = 5 in our best-performing version) entities selected from P. If the top-2 highest probability tokens are Cityroom and Gonville_Hotel , the model will instantiate two hypotheses [Cityroom, Located_in, Leichhardt] , [Gonville_Hotel, Located_in, Leichhardt] . With the hypotheses generated by HG module, we next aim to verify them via logical reasoning chains. Inspired by Neural Theorem Provers (Rocktschel and Riedel, 2017), we develop chain-like logical reasoning with following format: , ( H, R, T )  ( H, R n , Z n )      ( Z 1 , R 1 , T ) (14) where  is a weight indicating the belief of the model on the target hypothesis [ H, R, T ] , and the right part of the arrow is the reasoning chain used to prove that hypothesis, and R i and Z i are relations and entities from the KB. The goal is to find the proof chain and the confidence  for a given hypothesis. To this end, we introduce a neural-network based hierarchical reasoning engine (HRE) that learns to conduct chain-like logical reasoning. At a high level, HRE recursively generates multiple levels of sub-hypotheses using neural networks that form a tree structure as shown in Figure 2. Next, we describe how this module works in details. The module takes the output hypotheses from the HG module as input. Each hypothesis serves as one target hypothesis. To generate the reasoning chain in Equation 14, the module first finds sub-hypotheses of the same format as the target in the hypothesis space. The sub-hypotheses can be viewed as the intermediate reasoning results to prove the target. One straightforward approach is to use neural networks to predict all the tokens in the sub-hypotheses (2 heads, 2 tails and 2 relations). However, this can lead to extremely large search space of triples and is inefficient. Intuitively, subhypotheses inherit from the target hypothesis and sub-hypotheses themselves are connected by bridge entities. For example, [Uber,office_in,USA] can be verified by two sub-hypotheses [Uber,office_in,Seattle] and [Seattle,a_city_of,USA] , Uber and USA are inherited from the target and Seattle is the bridge entity between sub-hypotheses. Motivated by this, we propose to reduce the triple search complexity by constraining the sub-hypotheses. Specifically, given target [ H, R, T ] , we generate sub-hypotheses of the format [ H, R 1 , Z ] , [ Z, R 2 , T ] , where Z is the bridge entity, R 1 and R 2 are relations to be predicted. Therefore, the goal of the neural networks has been reduced to predict three tokens (2 relations and 1 bridge entity). Formally, HRE predicts the vector representation of bridge entity as follows: 4922 h H , h R , h T =  embcp ( H ) ,  embcp ( R ) ,  embcp ( T ) (15) h Z = W 6 ( LeakyReLU ( W 5 [ h H , h R , h T ])) (16) where [ h H , h R , h T ] are the concatenation of the representations of tokens in target hypothesis, h Z is the vector representation of bridge entity Z . The prediction of h R 1 and h R 2 uses the same architecture in Equation 16 and the difference is that they use different linear layers for the feature transformation. Note that h Z denotes a KB token in the embedding space. We can decode the token by finding the nearest KB token to h Z in vector space. More details on the token decoding can be found in Appendix A. Upon obtaining h Z , h R 1 , h R 2 , the module generates the two sub-hypotheses in vector representations. Next, the module iteratively takes each of the generated sub-hypothesis as input and extend the proof process by generating next-level sub-hypotheses in a depth-first manner until the maximum depth D has been reached. Belief Score To model confidence in different reasoning chains, we further measure the semantic similarities between each triple of the leaf node and triples in the KB, and compute the belief score  m of the m-th hypothesis H m :  m = min  i  U max  j  V e  d j ( Leaf i ,KB j ) (17) where Leaf i is the representation (concatenation of H, R, T ) of the i-th leaf node in the proof tree (DFS manner), KB j is the representation of the j-th triple in KB, U =[0,..., u -1], V =[0,..., v -1] where u and v are the number of leaf nodes and KB triples correspondingly, d is the distance metric. In general, any distance function can be applied and we adopt Euclidean distance in our implementation since we found that it worked well in our experiments. All the triples in the leaf nodes form the reasoning chain for the input hypothesis as in Equation 14. The hypotheses H coupled with the belief  form our KB distribution P kb,t . More details can be found in Appendix B. Intuitively, the belief score can be viewed as the likelihood of the hypothesis contains the correct entity. If the hypothesis is valid (i.e., contains the correct answer entity), it should have a high likelihood and thus encourage to generate more proper reasoning chains based on the triples stored in the KB. Training We apply two loss functions to train the whole architecture end-to-end. The first loss function L gen is for the final output. We use a cross-entropy loss over the ground-truth token and the Dataset Domains Train Dev Test SMD Navigate,Weather,Schedule 2425 302 304 MultiWOZ 2.1 Restaurant,Attraction,Hotel 1839 117 141 Table 1: Statistics of SMD and MultiWOZ 2.1. generated token from the final distribution P ( w ) . The second loss L cp is for the candidates prediction (CP) module in the hypotheses generator. We apply binary cross-entropy loss over the output distribution for each KB token (Equation 13) and their corresponding labels. The labels for each KB token are computed as follows: Label i = (cid:26) 1 , K i = y t 0 , K i  = y t (18) where K i is the i -th token in the KB and y t is the ground-truth output at timestep t. The final loss L is calculated by: L =  g  L gen +  c  L cp (19) where  g and  c are hyper-parameters and we set them to 1 in our experiments. To evaluate the effectiveness and demonstrate the interpretability of our proposed approach, we conduct experiments on two public benchmark datasets for task-oriented dialogue in this paper, SMD (Eric et al., 2017) and MultiWOZ 2.1 (Budzianowski et al., 2018). We use the partitions created by Eric et al. (2017); Madotto et al. (2018) and Qin et al. (2020) for SMD and MultiWOZ, respectively. Statistics of the datasets are presented in Table 1. In the Appendix E, we present several additional results on a large-scale synthetic dataset to demonstrate our model's multi-hop reasoning capability under complex KB reasoning scenarios. We compare our model with the following state-of-the-art baselines on KB reasoning in task-oriented dialogues: (1) Mem2Seq (Madotto et al., 2018): employs memory networks to store the KB and combine pointer mechanism to either generate tokens from vocabulary or copy from memory; (2) GLMP (Wu et al., 2019b): uses a global-to-local pointer mechanism to query the KB during decoding; (3) DF-Net (Qin et al., 2020): employs shared-private architecture to capture both domain-specific and domain-general knowledge to improve the model transferability; (4) GraphDialog (Yang et al., 2020): incorporates graph structural information obtained from sentence dependency parsing results for improving KB reasoning accuracy and response generation quality. Detailed experimental settings are included in Appendix C. 5.3 Main Results Following prior work (Eric et al., 2017; Madotto et al., 2018; Wu et al., 2019b), we adopt the BLEU and Entity F1 metrics to evaluate the performance of our framework. The results on the two datasets are shown in Table 2. As we can see, our framework consistently outperforms all the previous state-of-the-art baselines on all datasets across both metrics. Specifically, on MultiWOZ dataset, our model achieves more than 2% absolute improvement in Entity F1 and 1.2% improvement in BLEU over baselines. The improvement in Entity F1 indicates that our model enhances KB reasoning, while the increase in BLEU suggests that the quality of the generated responses has been improved. The same trend has also been observed on SMD dataset. This indicates the effectiveness of our proposed framework for task-oriented dialogue generation. To demonstrate our framworks's interpretability, we investigate the inner workings of our framework. As shown in Figure 3, given the dialogue history  Can you recommend me a restaurant near Palm_Beach? , the generated response is  There is a Golden_House. . During the 3rd timestep, our model has successfully predicted an appropriate H-Hypothesis with Located_in and Palm_Beach as its state tokens. Our model further instantiates five concrete hypotheses and computes their belief scores leveraging the reasoning engine, respectively. As we can see from the table, our model successfully generates five reasonable hypotheses and scores them correctly (with highest score for the oracle KB entity Golden_House ). The proof process for the highest score hypothesis is shown in Figure 3. The verification procedure generated by the HRE module has a depth of 3 and the reasoning chaining used to verify the target hypothesis is: [Golden_House, Next_to, Preston_Market]  [Pre-ston_Market, Located_in, Williamstown]  [Williamstown, Located_in, Herb_Garden]  [Herb_Garden, Located_in, Palm_Beach] . This indicates that our framework has successfully utilized the KB information to support the reasoning process explicitly to reach a correct conclusion. More examples and error analyses can be found in the Appendix (Appendix E.4 and F). We ablate each component in our framework to study their effectiveness on both datasets. The results are shown in Table 3. Specifically, 1) w/o HRE denotes that we simply use the probability in candidates prediction (CP) module (Equation 13) as the KB distribution without using the scores from the reasoning engine. 2) w/o BERT denotes that we use standard GRU as encoder instead of BERT. 3) w/o Soft-switch denotes that we simply sum the KB distribution and vocabulary distribution without using a soft gate. As we can see from the table, all the individual components have notably contributed to the overall performance of 4924 Dialogue history : Can you recommend me a restaurant near Palm_Beach? Leichhardt Located_in Leichhardt #3, Belief Score: 1.00 Sub-hypothesis KB: Cityroom Price_range Moderate Cityroom Stars 3 Cityroom Next_to Palm_Lawn Palm_Lawn Located_in Chadstone Chadstone Located_in Leichhardt Gonville_Hotel Price_range Expensive Gonville_Hotel Stars 4 Gonville_Hotel In_district Moorabbin ...... Cityroom Next_to Palm_Lawn Palm_Lawn Located_in Chadstone Chadstone Located_in Leichhardt Cityroom Located_in Leichhardt Reasoning Chain: Figure 1: Proof tree generated by the hierarchical reasoning module for the highest score hypothesis  [Gold_House, Located_in, Palm_Beach]  in Table 1. Our model performs 4-hop reasoning to arrive at the correct conclusion. All the leaf nodes predicted by HRE have a belief score of 1.0 as they are exactly supported by the external KB. In the original dataset released by prior works, the entity overlap ratio between the train and test split is 78% and 15.3% for MultiWOZ 2.1 and SMD, respectively. To simulate unseen scenario, we construct a new dataset split that reduces the entity overlap ratio to 30% for MultiWOZ 2.1 and 2% for SMD between the train and test split, which is a more challenging setting for all the models. More details of the construction process can be found in Appendix D. We re-run all the baselines with their released codes and our model on the new data split and report the results in Table 4. As we can see, the performance drops significantly for all systems on both datasets. However, our model degrades less compared to other systems, showing that it has better generalisation capability under unseen scenarios. This also verifies that neuro-symbolic approach has the advantage of better generalisation ability which has also been confirmed by many other studies (An-dreas et al., 2016; Rocktschel and Riedel, 2017; Minervini et al., 2020). our framework. Specifically, when removing HRE module, the performance has decreased substantially (more than 5% absolute drop), which confirms that the effectiveness of the proposed hierarchical reasoner module. We further investigate the generalization ability of our model under unseen settings. Following prior work (Qin et al., 2020), we also conduct human evaluations for our framework and baselines from three aspects: Correctness , Fluency , and Humanlikeness . Details about the scoring criterions can be found in Appendix H. We randomly select 300 different dialogue samples from the test set and ask human annotators to judge the quality of the responses and score them according to the three metrics ranging from 1 to 5. We train the annotators by showing them examples to help them 4925 Model Correct Fluent Humanlike GLMP 4.01 3.78 3.25 GraphDialog 4.15 4.19 3.40 DF-Net 4.16 4.25 3.54 Ours (Full model) 4.41 4.28 3.59 Human 4.83 4.65 4.57 Agreement 75% 69% 71% Table 5: Human evaluation results. understand the criteria and employ Fleiss' kappa (Fleiss, 1971) to measure the agreement across different annotators. The results are shown in Table 5. As we can see, our model outperforms all baselines across all the three metrics, consistent with our previous observations using automatic evaluations. In this paper, we propose an explicit and interpretable Neuro-Symbolic KB reasoning framework for task-oriented dialogue generation. The hypothesis generator employs a divide-and-conquer strategy to learn to generate hypotheses, and the reasoner employs a recursive strategy to learn to generate verification for the hypotheses. We evaluate our proposed framework on two public benchmark datasets including SMD and MultiWOZ 2.1. Extensive experimental results demonstrate the effectiveness of our proposed framework, as well being more interpretable. For the human evaluation in this paper, we recruit several annotators on Amazon Mechanical Turk from English-speaking countries. We pay the annotators USD$0.15 for each annotation task. Each task can be finished on average in 1 minute, which amounts to $9.0 per hour that is above the US fed-eral minimum wage ($7.25). To ensure the quality of the human evaluation results, we perform quality control in a few ways. First, the annotators will be shown our scoring standards (Appendix H) before their tasks, and are asked to follow them. If the task is not done properly, either as determined by expert judgements (we recruit 3 native English speakers to validate the results of the Turkers' annotations) or there are obvious patterns such as constantly giving the same score for all tasks, we remove their annotations. We also compute agreement score to check for the consistency among the annotators.
method abstain result abstain objective objective abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain objective abstain objective abstain abstain objective abstain abstain result abstain abstain abstain objective objective objective objective other other other other other other other other objective other other other other other other objective method abstain abstain abstain abstain method abstain abstain method abstain method abstain abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain other abstain abstain abstain method abstain method method method abstain abstain other method method abstain abstain method abstain method abstain method abstain other abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain other abstain abstain abstain abstain abstain method abstain abstain method abstain abstain method abstain method abstain abstain method abstain abstain abstain abstain abstain other abstain result result result result abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result abstain result objective abstain objective objective abstain abstain abstain abstain abstain abstain method