summaries: Authors propose to solve an order fulfillment problem with imitation learning backed by GNNs. The specific version of the fulfillment problem is nontrivial: discussed has a hierarchy in order (an order can be decomposed into sub-orders), and items become forbidden over time. SCIP package is used as the expert policy, and authors employ behavior cloning. The specific model they use is a Graph Attention Transformer on the tripartite graph of orders, items, and warehouses. Compared to a reasonable heuristic, Pointer Network, and GAT which ignores edge features, the propose method yields much lower inference latency.

summaries: A Graph Neural Network (GNN) model is designed to enable the supervised learning of optimal solutions for an order fulfillment problem in supply chain management. This is a problem that must be solved in real-time, making a GNN whose forward computations are quick an attractive option.  The proposed GNN model has three types of nodes corresponding to orders, items, and warehouses. Edges between the nodes of different types represent relationships between them (e.g., an item is in an order). Nodes and edges may have feature vectors representing additional information, e.g., the identity of a warehouse or certain costs on the edges. The GNN is designed to take these features into account.  The model is trained using optimal solutions as labels in a binary classification formulation. Predictions are post-processed to guarantee a feasible solution in the constraints of the order fulfillment problem.  Experimental results on randomly generated instances show that a GNN trained on small instances of this problem performs well even on larger instances, yielding near-optimal solutions in a short amount of time compared to simple GNN solutions, a non-ML heuristic, and an exact solver.

summaries: This paper presents a graph based deep learning model for solving the order fulfillment problem of assigning retail (sub-)orders to different warehouses for fulfilment. It formulates the problem as a Mixed Integer Problem (MIP, although I think it is fully integer) which can be solved using a (open-source) MIP solver such as SCIP. Following up on related work, the authors train a graph neural network, specifically designed to incorporate edge features and different types of nodes, to predict the optimal solution, using supervised learning on a dataset of 100.000 generated instances solved with SCIP. Empirically, on three different test problem sizes, the trained model provides solutions within 2-3% to the results found by SCIP, while being a 2-4 orders of magnitude faster.

summaries: This paper proposes a heuristic graph based machine learning model, which can be used to solve the class of order fulfillment problems. The original mixed integer programming problem is known to be NP-hard, and thus computationally intractable. The authors treat each instance of the order fulfillment problems as a tripartite graph, which serves as the input of the proposed model.   The proposed model consists of three parts: a graph attention network (GAT) to embed the features, a feed forward (FF) layer, and an assignment layer generating the output.

abstractText: The order fulfillment problem is one of the fundamental combinatorial optimization problems in supply chain management and it is required to be solved in realtime for modern online retailing. Such a problem is computationally hard to address by exact mathematical programming methods. In this paper, we propose a machine learning method to solve it in milliseconds by formulating a tripartite graph and learning the best assignment policy through the proposed edge-featureembedded graph attention mechanism. The edge-feature-embedded graph attention considers the high-dimensional edge features and accounts for the heterogeneous information, which are important characteristics of the studied optimization problem. The model is also size-invariant for problem instances of any scale, and it can address cases that are completely unseen during training. Experiments show that our model substantially outperforms the baseline heuristic method in optimality. The online inference time is milliseconds, which is thousands of times faster than the exact mathematical programming methods.

authors:
Jason Acimovic
Stephen C Graves

title: Making better fulfillment decisions on the fly in an online retail environment

venue: Manufacturing & Service Operations Management,

authors:
Alejandro Marcos Alvarez
Quentin Louveaux
Louis Wehenkel

title: A machine learning-based approximation of strong branching

venue: INFORMS Journal on Computing,

authors:
Irwan Bello
Hieu Pham
Quoc V. Le
Mohammad Norouzi
Samy Bengio

title: Neural combinatorial optimization with reinforcement learning

venue: In ICLR (Workshop),

authors:
Yoshua Bengio
Andrea Lodi
Antoine Prouvost

title: Machine learning for combinatorial optimization: a methodological tour d’horizon

venue: arXiv preprint arXiv:1811.06128,

authors:
Djork-Arné Clevert
Thomas Unterthiner
Sepp Hochreiter

title: Fast and accurate deep network learning by exponential linear units (elus)

venue: arXiv preprint arXiv:1511.07289,

authors:
Reuven Cohen
Liran Katzir
Danny Raz

title: An efficient approximation for the generalized assignment problem

venue: Information Processing Letters,

authors:
Hanjun Dai
Elias B. Khalil
Yuyu Zhang
Bistra Dilkina
Le Song

title: Learning combinatorial optimization algorithms over graphs

venue: Proceedings of the 31st International Conference on Neural Information Processing Systems,

authors:
Lu Duan
Haoyuan Hu
Yu Qian
Yu Gong
Xiaodong Zhang
Jiangwen Wei
Yinghui Xu

title: A multi-task selected learning approach for solving 3d flexible bin packing problem

venue: In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems,

authors:
Claudia D’Ambrosio
Silvano Martello
Michele Monaci

title: Lower and upper bounds for the nonlinear generalized assignment problem

venue: Computers & Operations Research,

authors:
Lisa Fleischer
Michel X. Goemans
Vahab S. Mirrokni
Maxim Sviridenko

title: Tight approximation algorithms for maximum general assignment problems

venue: In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm,

authors:
Ahmed Ghoniem
Tulay Flamand
Mohamed Haouari

title: Exact solution methods for a generalized assignment problem with location/allocation considerations

authors:
Ambros Gleixner
Leon Eifler
Tristan Gally
Gerald Gamrath
Patrick Gemander
Robert Lion Gottwald
Gregor Hendel
Christopher Hojny
Thorsten Koch
Matthias Miltenberger

title: The scip optimization suite

authors:
He He
Hal Daume Iii
Jason M Eisner

title: Learning to search in branch and bound algorithms

venue: In Advances in Neural Information Processing Systems 27,

authors:
Haoyuan Hu
Xiaodong Zhang
Xiaowei Yan
Longfei Wang
Yinghui Xu

title: Solving a new 3d bin packing problem with deep reinforcement learning

venue: method. ArXiv,

authors:
Wouter Kool
Max Welling

title: Attention solves your tsp

venue: arXiv preprint arXiv:1803.08475,

authors:
O. Erhun Kundakcioglu
Saed Alizamir

title: Generalized assignment problem, pp. 1153–1162

authors:
Zhuwen Li
Qifeng Chen
Vladlen Koltun

title: Combinatorial optimization with graph convolutional networks and guided tree search

venue: In Advances in Neural Information Processing Systems,

authors:
Hao Lu
Xingwen Zhang
Shuang Yang

title: A learning-based iterative method for solving vehicle routing problems

venue: In ICLR 2020 : Eighth International Conference on Learning Representations,

authors:
Qiang Ma
Suwen Ge
Danyang He
Darshan Thaker
Iddo Drori

title: Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning

venue: arXiv: Learning,

authors:
Lale Özbakir
Adil Baykasoğlu
Pınar Tapkan

title: Bees algorithm for generalized assignment problem

venue: Applied Mathematics and Computation,

authors:
Kanchana Sethanan
Rapeepan Pitakaso

title: Improved differential evolution algorithms for solving generalized assignment problem

venue: Expert Systems with Applications,

authors:
Thomas C. Sharkey
H. Edwin Romeijn

title: Greedy approaches for a class of nonlinear generalized assignment problems

venue: Discrete Applied Mathematics,

title: Attention is all you need

venue: In Advances in neural information processing systems,

authors:
Oriol Vinyals
Samy Bengio
Manjunath Kudlur

title: Order matters: Sequence to sequence for sets

venue: In ICLR 2016 : International Conference on Learning Representations

authors:
Wei Wu
Manuel Iori
Silvano Martello
Mutsunori Yagiura

title: Exact and heuristic algorithms for the interval min-max regret generalized assignment problem

venue: Computers & Industrial Engineering,

authors:
Ping Josephine Xu
Russell Allgor
Stephen C Graves

title: Benefits of reevaluating real-time order fulfillment decisions

heading: 1 INTRODUCTION

text:
The current decade has witnessed rapid development of online retailing, which generally has a very large operation scale and poses new challenges to supply chain management. One of the most important problems in the online retailing is the real-time order fulfillment decision, which aims to find the most cost-effective order-warehouse assignment after the customers place the orders online. The decisions are required to be made in real time, because the fulfillment system must complete hundreds of orders per second (Acimovic & Graves, 2015; Xu et al., 2009). A good fulfillment policy could reduce expenses by millions of dollars for large online retailers such as Alibaba and Amazon.
The order fulfillment problem in its most general form is as follows: There are a number of orders and a number of warehouses. Each order contains several items, which are at different inventory levels and have different sale-forbidden1 dates in these warehouses. Any warehouse can be assigned to serve any order, incurring delivery transportation cost and inventory management cost that vary depending on the locations of the orders and the types of items. An order can be split into multiple packages that are committed by different warehouses due to practical constraints, such as the shortage of inventory. A group of identical items in any order is defined as a suborder, which is the smallest assignment unit in this problem. The retailer seeks to find the optimal suborder-warehouse assignment policy that minimizes the overall cost in the order fulfillment.
The order fulfillment problem falls into the category of generalized assignment problems, which is an NP-hard combinatorial optimization (Kundakcioglu & Alizamir, 2009) (An extra note on generalized assignment problem is listed in the Appendix A.1). Traditional approaches to this problem can be divided into exact methods and heuristics. The exact methods guarantee finding optimal solutions by using a branch-and-bound search (B&B) with a mixed-integer programming formulation (MIP), but they generally require a long time to solve and are even computationally intractable for large-scale cases. Because the order fulfillment is a real-time decision task in the online retailing,
1The sale-forbidden date is usually months ahead of the expiration date. Any item going beyond the saleforbidden date can no longer be sold.
the exact methods are unable to meet the allowed maximum computation time (tens of milliseconds). The heuristics are typically a set of specialized rules and are currently used in the industry because of the low computational cost(Sethanan & Pitakaso, 2016; D’Ambrosio et al., 2020). As a trade-off, the optimality is sacrificed and once the conditions of the problem change, the rules must be re-designed carefully, which costs a lot of manpower.
Recently, machine learning (ML) has made much progress on solving combinatorial optimization problems (Bengio et al., 2018), e.g., using supervised or reinforcement learning to solve the travelling salesman problem (TSP) and the vehicle routing problem (VRP) in an end-to-end approach (Vinyals et al., 2015; Kool & Welling, 2018; Lu et al., 2020). According to the research, ML methods can achieve stronger policies than heuristics without requiring specialized human knowledge. The computational cost of ML inference is extremely low. The ML methods are also self-adaptive to the changes on the problem conditions, because they are end-to-end methods from the original data to the solutions. This progress motivates us to explore whether order fulfillment in the supply chain industry can be addressed by ML methods.
However, the nature of the order fulfillment problem is size-variant and contains heterogeneous information. Different scales of problem instances have varying numbers of orders, items and warehouses. How can we properly transform the combinatorial optimization problem into the input/output of an ML model? How can we design an ML model that can effectively solve the varying scales of problem instances? These questions pose great challenges to our work.
In this paper, we will for the first time apply ML to solve the real-time order fulfillment decision problem by developing a graph mapping solution framework. A size-invariant graph model is developed to learn the hidden information on the heterogeneous graph. A novel graph attention mechanism is proposed to consider the high-dimensional edge features in the represented optimization problem. The specific contributions are threefold: (1) formulate the real-time order fulfillment decision problem with constraints of the modern online retailing and supply chain industry; (2) propose a tripartite heterogeneous graph representation of the order fulfillment problem and develop an ML-based solution framework; and (3) propose size-invariant and edge-feature-embedded graph attention to learn the hidden information in the heterogeneous graph.

heading: 2 RELATED WORK AND GAPS

text:
Generally, applying ML on combinatorial optimization can be divided into two approaches. The first approach is to improve the branch-and-bound algorithm in the MIP formulation by using ML for variable branching (Alvarez et al., 2017), node selection (He et al., 2014) and so on. Although these methods can guarantee exact solutions by relying on the branch-and-bound approach, the acceleration is limited. Our focus is on the other type of method, the end-to-end learning approach (Bengio et al., 2018), which learns the optimization policy directly from the problem instances.
The end-to-end ML models for combinatorial optimization require careful design, because both of the problem input and output vary in size (Bengio et al., 2018). This circumstance means that the ML model must be able to address the data sizes that are completely unseen during training. To tackle this problem, the pointer network (Ptr-Net) is introduced based on the sequence-to-sequence model (Vinyals et al., 2015; Bello et al., 2017). The Ptr-Net directly uses an attention mechanism as a “pointer” to select a member of the input sequence as the output, regardless of the varying output dictionary sizes that depend on the problem instances. According to the experiments, the model performs well on the convex hull problem and TSP beyond the maximum sizes that they are trained on. Hu et al. (2017); Duan et al. (2019) further apply the Ptr-Net on the bin-packing problem to determine the optimal sequence in which the items are packed into bins. Apart from Ptr-Net, Kool & Welling (2018) solves the TSP based entirely on the attention mechanism similar to the Transformer architecture (Vaswani et al., 2017). The input data is the (x, y) coordinates of all of the nodes, and the model calculates the attention between every pair of nodes. Finally, a sequence of nodes is generated as the optimal result. However, current studies based on Ptr-Net are mainly designed for sequential decisions, which might not fit the pattern for the studied assignment problem. According to Vinyals et al. (2016); Hu et al. (2017), the use of the RNN as an encoder in Ptr-Net makes it difficult to represent long input sequences and suffers heavily from the order of the input data.
The graph-base models, e.g., the graph convolutional network (GCN) and graph attention network (GAT)(Veličković et al., 2018), have also been applied in several studies, because many optimization problems can be represented as a graph. Dai et al. (2017) attempts to solve the minimum vertex cover problem and TSP by embedding the graph with a structure2vec network and iteratively adding the best node to construct the solution using reinforcement learning. Ma et al. (2019) proposes the graph Ptr-Net by using graph embedding as the input of Ptr-Net to solve the TSP. Li et al. (2018) first uses a GCN to generate a large number of candidate solutions to the combinatorial optimization. Then, a guided tree search is performed to refine the solution. However, most mentioned studies address homogeneous graphs without high-dimensional edge features, such as the TSP and VRP problems, where the input is a set of (x, y) coordinates. In the studied problem, the features of orders, items and warehouses are heterogeneous and the relationships between them are important, such as the tiered pricing rules between orders and warehouses, and the inventory between items and warehouses with different sale-forbidden dates. Current studies lack proper consideration of these important highdimensional edge features and the heterogeneous information between different types of nodes and edges.

heading: 3 PROBLEM STATEMENT

text:
The mathematical formulation of the studied order fulfillment problem for modern online retailing is formulated in (1a)-(1h). Table 1 lists the notation. For better understanding, a brief introduction on the generalized assignment problem is given in Appendix A.1, which is the basics of the order fulfillment problem.
min zkl ∑ k∈K ∑ i∈I ( C (0) ki xki + C (1) ki wki ) + ∑ k∈K ∑ j∈J ∑ t∈T Pj + kjt (1a) s.t. zkl ≤ xki, ∀k ∈ K,∀i ∈ I,∀l ∈ L(i, ·), (1b)∑ k∈K
zkl = 1, ∀l ∈ L, (1c)∑ t∈T
dklt = Olzkl, ∀k ∈ K, l ∈ L, (1d)∑ l∈L(·,j) dklt ≤ Skjt, ∀k ∈ K,∀j ∈ J,∀t ∈ T, (1e) xkiD + wki ≥ ∑
l∈L(i,·) ( Wj ∑ t∈T dklt ) , ∀k ∈ K,∀j ∈ J,∀i ∈ I, (1f)
Fkjt + + kjt − − kjt = Skjt − ∑ l∈L(·,j) dklt, ∀k ∈ K,∀j ∈ J, t = 0, (1g)
Fkjt + + kjt − − kjt = Skjt − ∑ l∈L(·,j) dklt − −kjt−1, ∀k ∈ K,∀j ∈ J, t ≥ 1 (1h)
The objective of the optimization problem (1a) is to minimize the overall fulfillment cost, including the delivery cost and the inventory management cost, by making the optimal assignment between warehouses and suborders. The delivery cost consists of the first weight cost and additional unit cost according to the tiered pricing rule in the logistics. The inventory management cost denotes the loss of the cargo value , which is the result of the items that become sale-forbidden.
Constraint (1b) denotes that if warehouse k serves any suborder in order i, then xki = 1. Constraint (1c) denotes that any suborder should be served by one and only one warehouse.
Constraint (1d) denotes that the sum of the selected items before different sale-forbidden periods in warehouse k must equal the gross item quantity of the suborder l. Constraint (1e) means that any item j cannot be out-of-stock. Constraint (1f) represents the tiered pricing system in logistics, where the right-hand side of the equation is the total weight of the served part of order i by warehouse k. Constraints (1g)-(1h) represent the item picking sequence in the warehouse. Because any item going into sale-forbidden periods can no longer be sold, they must be picked from near to far.
1 Any suborder l ∈ L belongs to a unique order i ∈ I and has a group of identical item j ∈ J. 2 The package (k, i) denotes that part of or all the suborders in order i ∈ I are served by the warehouse k ∈ K and are delivered as one package.
Note that zkl is the key decision variable, and it represents the assignment between warehouses and suborders. When we make decision, two constraints are the most important: (1) Each suborder should be assigned to only one warehouse, represented by (1c); (2) The item inventory in the assigned warehouse must not be less than the demand of the suborder, represented by (1d)-(1e). Other variables and constraints are auxiliary. For example, dklt, +kjt, − kjt are used mainly to represent the item picking sequence; and xki, wki are used to represent the difference between the first weight and the additional weight in the tiered pricing rules.

heading: 4 SOLUTION FRAMEWORK

text:
In the proposed solution, we first map this problem into a tripartite heterogeneous graph as the input to the graph ML model, which has the advantage of being permutation-invariant to the input order. Then, we design the edge-feature-embedded graph attention to learn the hidden state of the graph. Last, we use the attention between the hidden state of the orders and warehouses to make the assignment, which can fit cases with varying sizes of orders, items and warehouses.
During the offline training, the exact B&B method is applied to solve the problem instances to generate the optimal assignment results as the training labels. In the stage of online inference, we directly predict the suborder-warehouse assignment through the graph ML model. Because the proposed graph ML model is size-invariant, it can generalize to cases of larger sizes that have never been seen during training.

heading: 4.1 TRIPARTITE GRAPH REPRESENTATION

text:
First, we novelly represent the order fulfillment problem with a tripartite graph in Figure 1a, where vectors h, e represent the features of nodes and edges, respectively. Compared to the sequential representation, the graph representation has the advantage of being permutation-invariant, which means that different input data orders correspond to the same graph. The three disjoint sets in the graph are the orders (decomposed into suborders), items and warehouses.
Different sets of nodes have different features. The feature hl ∈ RN , l ∈ L of suborder node l is an N -dimensional one-hot vector, representing the order that it belongs to. The suborders under the same order share the same feature. N denotes the maximum size of orders the model is designed to handle. The feature hk ∈ RM , k ∈ K of warehouse node k is an M -dimensional one-hot vector, representing the different warehouse identification codes (ids). M denotes the maximum size of the warehouses that the model is designed to handle. The feature hj = [Pj ,Wj ], j ∈ J of item node j is a two-dimensional vector that consists of the purchase price and weight of the corresponding item.
The edges between different set of nodes also represent different information. The feature ekl = [C
(0) ki , C (1) ki ], k ∈ K, l ∈ L(i, ·) between suborder l and warehouse k represents the tiered delivery cost. Note that the first weight and additional weight cost from one warehouse to the suborders under the same order are identical. The feature elj = [Ol], j ∈ J, l ∈ L(·, j) of the edges between suborder l and item j represents the quantity of items that each suborder contains. The feature ekj = [Skj0, Fkj0, ..., Skjt, Fkjt, ...], k ∈ K, j ∈ J of edges between warehouse k and item j is a vector with the length of 2× |T|, which represents the inventory and forecasted saleplan in different sale-forbidden dates.

heading: 4.2 THE GRAPH-BASED MACHINE LEARNING MODEL

text: To learn the hidden states from the original tripartite graph and to make an assignment, we propose a hierarchical graph-based machine learning model in Figure 1b. The model consists of three important components. The first component is the edge-feature-embedded GAT layer, which follows the work of Veličković et al. (2018) but uses a novel attention mechanism to learn the high-dimensional edge features and the heterogeneous information in the graph. Next, a feed forward (FF) layer makes a nonlinear transformation of the node and edge features. Last, an “assignment” layer generates the assignment between suborders and warehouses by computing the attention coefficients of each pair. It is worthwhile to note that the attention mechanism is used throughout the model and no transformation depends on the size of the graph, which makes the model able to address varying sizes of orders, items and warehouses.

heading: 4.2.1 EDGE-FEATURE-EMBEDDED GAT LAYER

text:
The input to the edge-feature-embedded GAT is a set of node feature vectors {hl,hj ,hk} and edge feature vectors {elj , elk, ekj}, ∀l ∈ L, j ∈ J, k ∈ K. Here, we will use the transformation of nodes that represent suborders hl,∀l ∈ L to illustrate how we properly embed the edge features.
First, we embed the edge features in the computation of the attention coefficients. For any node l ∈ L, we compute the attention coefficients between hl and hj ,hk as follows:
clj = score(hl,hj , elj) = σ ( V >JL(hl‖hj‖elj) ) ,∀j ∈ J (2)
clk = score(hl,hk, elk) = σ ( V >KL(hl‖hk‖elk) ) ,∀k ∈ K (3)
Here, the attention mechanism is a single feed-forward layer with the nonlinear activation function σ. VJL and VKL denote the weight vectors with respect to heterogenous node pairs. For any j ∈ J and k ∈ K, the weight vectors remain the same and thus are invariant to the sizes of the node sets. ‖ represents the concatenation operation. The attention coefficients indicate the importance between any two nodes considering the edge feature that links them and are computed only if the nodes are connected in the graph. The coefficients are then normalized across the same type of neighborhood nodes using the softmax function:
alj = softmaxj(clj) = exp(clj)∑ j∈J exp(clj) ,∀j ∈ J (4) alk = softmaxk(clk) = exp(clk)∑
k∈K exp(clk) ,∀k ∈ K (5)
Second, we embed the edge features into nodes using a linear combination by the attention coefficients to update hl,∀l ∈ L:
ĥl = hl ∥∥∥∥ [∑ k∈K alk(hk‖elk) ]∥∥∥∥ ∑ j∈J alj(hj‖elj)  (6) Two things should be noted in (6). First, the updated node feature is concatenated with three parts. The first part is the self-feature, while the others are the combination of the feature of items and warehouses. The reason is that the graph we address contains heterogeneous information and should be treated appropriately. Second, the edge feature is again concatenated with the node feature apart from that in (2)-(3). One special case can illustrate the necessity behind this step. Consider a node that has only one neighborhood. The attention coefficients will always be 1.0 for this neighborhood, regardless what the edge feature is. If we do not concatenate the edge feature according to the method of (6), we lose the information on the edge between them. For other cases, although (2)- (3) have already embedded the edge features, the concatenation of edge features in (6) can further strengthen the explicit representation of the edge information.
By applying the transformation method (2)-(6) on nodes hj ,∀j ∈ J and hk,∀k ∈ K, we obtain the updated node feature ĥj and ĥk, which, in combination with ĥl, forms the output of the layer.

heading: 4.2.2 FEED-FORWARD LAYER FOR NODES AND EDGES

text:
Note that the edge-feature-embedded GAT layer only makes a linear combination of features in equation (6). Therefore, we further use a feed-forward layer to transform the features of nodes and edges with nonlinearity. We still take the nodes that represent suborders as an example, of which the updated feature after the GAT layer is ĥl. The transformation through the feed-forward layer is as follows:
h̃l = σ ( WLĥl ) ,∀l ∈ L (7)
For the edges, the GAT layer does not make a transformation and thus we have the following transformation for the edges that connect any suborder l ∈ L:
ẽlj = σ (WJLelj) ,∀j ∈ J (8) ẽlk = σ (WKLelk) ,∀k ∈ K (9)
where WJL,WKL are the transformation matrices for the edges between suborders and items, suborders and warehouses. Note that for any suborder node and the connected edges, the weight matrix WL,WJL,WKL are the same and are thus invariant to the size of node set.
The outputs of FFN are {h̃l, h̃j , h̃k} and {ẽlj , ẽlk, ẽkj}, ∀l ∈ L, j ∈ J, k ∈ K. They formulate a new graph with the same topology as the input graph and will be used as the input for the next hierarchy for further transformation.

heading: 4.2.3 ASSIGNMENT LAYER

text:
To assign suborders to warehouses in size-variant cases, we again use the attention mechanism as a “pointer” Vinyals et al. (2015) to point each suborder to the appropriate warehouse. First, we calculate the attention coefficients on the output graph between each pair of suborder l and warehouse k using the dot product:
clk = score (hl,hk) = h>l hk,∀l ∈ L, k ∈ K (10)
Next, we apply the softmax function to normalize over all of the warehouses and, for any suborder node l ∈ L, we use the plk as a distribution over the warehouses.
plk = softmaxk(clk) = exp(clk)∑ k∈K exp(clk)
(11)
The largest probability argmaxk∈K plk is the selected suborder-warehouse assignment by the ML model. Note that in this step, there is no weight matrix to be trained and thus, the approach is invariant to the sizes of the suborders and warehouses.

heading: 4.3 OFFLINE MODEL TRAINING

text:
In the stage of offline model training, we use supervised learning. The cross-entropy is applied as the loss function. The total loss in an instance should account for all of the suborders as follows:
loss = − ∑ l∈L ∑ k∈K ylk log(plk) (12)
where ylk is the real label that denotes whether suborder l is assigned to warehouse k. Real labels are generated by using the exact B&B method to solve the MIP (1a)-(1j) under different input instances.

heading: 4.4 ONLINE MODEL INFERENCE

text: In the stage of online inference, each input case is formulated into the tripartite graph, and the offlinetrained graph-based model is directly used to compute the attention coefficients between each pair of suborders and warehouses. To guarantee the feasibility in the online order fulfillment decision, the most important constraints (1c)-(1e) must be satisfied. We use the following masking procedure in finding the largest probability argmaxk∈K plk: (1) Select the suborder l = argmaxlOl; (2) The warehouse node k ∈ K with insufficient inventory (Ol > ∑ t∈T Skjt) is not allowed to be visited; (3) Find the best warehouse k = argmaxk∈K plk and reduce the inventory of item j from the nearest sale-forbidden date until the quantity equals Ol.

heading: 5 EXPERIMENTS

heading: 5.1 DATASETS, BASELINES AND METRICS

text:
We generate one training and three testing datasets with varying scales. The ML model is trained only on the training set and then tested on the three test sets. The training dataset contains 100,000 instances of the order fulfillment problem with the optimal assignment results as labels, which are obtained by solving the MIP formulation (1a)-(1h) using the open-source SCIP optimization suite Gleixner et al. (2017). The problem size in the test cases is larger than that in the training dataset.
We report four baselines in the experiments. The first is the exact branch-and-bound (B&B) method. The second is the heuristic method that is currently applied in practice (The detailed algorithm is described in appendix A.2.) The third baseline is to use the Ptr-Net based on supervised learning, which is also our first attempt facing the order fulfillment problem. To compare the effect of considering the high-dimensional edge features and heterogeneous information in our model, we add the fourth baseline by replacing the edge-feature-embedded graph encoders with the original GAT network Veličković et al. (2018) in our solution framework.
The evaluation metrices are the computation time and the gap in the total cost between the model’s result and the optimal solution (obtained by SCIP with a time limit of 15 minutes). The total cost
is computed using equation (1a) based on the order fulfillment result. A smaller gap means a better assignment policy.
gap = costmodel − costMIP
costMIP (13)

heading: 5.2 ARCHITECTURE AND HYPERPARAMETERS

text: In the experiments, we apply N = 3 graph encoders, without using an extensive hyperparameter search and the multi-head mechanism. The nonlinear activation function in both the edge-featureembedded GAT layer and the FFN layer is the exponential linear unit (ELU) Clevert et al. (2015). During the training, we apply a dropout ratio of 0.1 to the FFN inputs. The model is trained with the Adam optimizer with a learning rate of 0.003 and a batch size of 256.

heading: 5.3 RESULTS

text:
The details of the datasets and the results of the experiments are summarized in Table 2 . Figure 2 compares the performance of all of the methods on the test datasets. Figure 3 gives an example of the model-predicted assignment result from the 3rd test case.
From the results, we note that our method achieves the smallest cost gap and substantially outperforms the heuristic method, Ptr-Net and the original GAT without embedded edge features. In Figure 2, we find that our method also has the smallest variance at the stage of inference, which means better robustness. In test sets 2 and 3, where the sizes of the problem instances are completely unseen during training, our method still has the best performance in extrapolating.
The inference time of these methods is also compared. We note that, although the heuristic method has the lowest computational cost because of its simple rules, our method is able to make inference in several milliseconds. Compared to directly solving MIP, our method achieves tens of thousands of times of acceleration in the computation time and meets the criteria for real-time applications. The reason behind this outcome is that the graph encoders compute the assignment results through matrix multiplications. In contrast, the exact B&B method iteratively searches the results in the feasible region and is thus much slower than our method.
The reason for the bad performance with the original GAT network is obvious, because the important high-dimensional edge features are ignored in the model. However, it is worthwhile to note that Ptr-Net does not perform well in the studied task. We think that three reasons might lead to this result. First, Ptr-Net uses an RNN to encode the input data, which is heavily influenced by the sequence order and length. For example, in the second test case, the length of the input sequence is approximately 800, which could be too long for the RNN to learn the hidden states. Second, the assignment problem is not a sequential decision problem that differs from TSP and VRP, which is incompatible with the structure of Ptr-Net. Third, the output of Ptr-Net is generated one-by-one, depending on the previous output sequence, which leads to a larger inference time.

heading: 6 CONCLUSIONS

text:
In this paper, we propose a machine learning framework to solve the order fulfillment problem—a special type of combinatorial optimization—for real-time decisions in online retailing. Experiments show that our method substantially outperforms the baseline heuristic method and the cost gap between MIP optimal solution is less than 5%. Our method also realizes thousands of times of acceleration compared with directly solving the MIP, which meets the criteria for real-time online decision in milliseconds. To meet the characteristics of the studied problem, the edge-feature-embedded graph encoder is developed, which takes the high-dimensional edge features and heterogeneous information into the graph attention mechanism and can address problem instances with varying input lengths and output dictionary sizes.
Apart from solving the studied order fulfillment problem, we envision that the edge-featureembedded heterogenous graph attention can be further applied in other combinatorial optimization problems such as the TSP, VRP and the generalized assignment problem, where our method can include consideration of the high-dimensional nonlinear route cost or other complex scenarios.

heading: A APPENDIX

text:
A.1 GENERALIZED ASSIGNMENT PROBLEM
The simplest form is called the assignment problem, in which the knapsack for items is uncapacitated. The assignment problem is a special case of the minimum cost flow problem and can be formulated as a linear programming problem without using integers. Several exact and fast algorithms have been developed such as the Hungarian method, the auction algorithm. Compared to the assignment problem, the generalized assignment problem has capacitated knapsacks and other real-world constraints, which make it vary difficult to solve.
The generalized assignment problem describes the assignments between items and bins, where the bins have a capacity limit. There could exist other complex constraints for the items and bins. The problem can be formulated as a mixed integer program:
min zij m∑ i=1 n∑ j=1 cijzij (14a)
s.t. n∑ j=1 wijzij ≤ ti, i = 1, ...,m, (14b)
m∑ i=1 zij = 1, j = 1, ..., n, (14c)
f(zij) ≤ 0, i = 1, ...,m, j = 1, ..., n, (14d) g(zij) = 0, i = 1, ...,m, j = 1, ..., n, (14e) zij ∈ {0, 1} i = 1, ...,m, j = 1, ..., n (14f)
In the above formulation, we have n items and m bins. For bin i, each item has a cost cij and a weight wij . A solution is an assignment from items to bins. The objective is to minimize the cost of the assignment. The constraint (14b) denotes that any bin i has a capacity ti. The constraint (14c) denotes that any item can only be assigned to one bin.The equation (14b)-(14c) are the fundamental constraints in the generalized assignment problem, while (14d)-(14e) represent other general constraints for the problem.
The explorations on the exact method to solve the generalized assignment problem are mainly based on decomposition techniques. Wu et al. (2018) applies Benders decomposition and Lagrangian relaxation to reduce the scale of the MIP problem. Ghoniem et al. (2016) considers the total space allocation constraints and modifies the branch-and-price method. According to the paper, it costs half an hour to reach a nearly-optimal solution with only 15 items and 25 knapsacks.
Several heuristics are developed for the generalized assignment problem as well. Sharkey & Romeijn (2010); Cohen et al. (2006) use greedy methods to translate the algorithm for the knapsack problem into an approximation method for a generalized assignment problem. Fleischer et al. (2006) further proves the performance of the proposed heuristics by justifying an optimal gap less than 1/e. Sethanan & Pitakaso (2016); Özbakir et al. (2010) use differential evolution and the bees algorithm respectively, with the help of local search techniques. An average optimality gap of 12.5% is achieved. The downside of heuristics is that the approach requires an enormous amount of human knowledge and might not reach the state-of-art performance.
A.2 HEURISTIC METHOD FOR THE ORDER FULFILLMENT PROBLEM
The algorithm below is the current heuristic method for the order fulfillment problem. The remaining inventory near sale-forbidden dates among different warehouses is the first priority, because the cargo value loss is usually larger than the delivery fee. Next, the delivery fee for each warehouse is compared, while considering the tiered pricing rule, and the relationships between the orders and suborders. Finally, the corresponding item inventory is reducted from the best selected warehouse.
Algorithm 1: Heuristic method for the order fulfillment problem Result: zkl I′ = I while I′ 6= ∅ do
K′ = ∅ wk = 0,∀k ∈ K i = argmaxi ∑ l∈L(i,·)Ol for l ∈ L(i, ·) do // Select the best warehouse if ∃t ∈ T(t 6= |T| − 1), s.t.Skjt > 0 then
k∗ = argmaxk ∑
t∈T Skjt else for k ∈ K, s.t. ∑
t∈T Skjt > Ol do if k ∈ K′ then
if wk +WjOl ≤ D then ckl = 0 else ckl = C (1) ki (wk +WjOl −D)
end else
if WjOl ≤ D then ckl = C (0) ki else ckl = C (0) ki + C (1) ki (WjOl −D)
end end
end k∗ = argmink ckl wk∗ = wk∗ +WjOl K′ = K′ ∪ k∗
end zk∗l = 1 // Reduct inventory rl = Ol for t ∈ T do
if 0 ≤ rl < Skjt then Skjt = Skjt − rl; rl = 0 else rl = rl − Skjt;Skjt = 0
end end
end I′ = I′ \ i
end


summaries: This paper introduces a new dialogue summarization task that requires summaries to mention new concepts that are not explicitly mentioned in -- but may be implied by -- the dialogue. The task, CODC, repurposes the VisDial dataset (itself based on the MSCOCO captioning dataset), which involved information-seeking question-and-answer dialogues about an image, where the dialogue participants were prompted by the image's caption. The captions frequently mention some concepts that are not mentioned in, but are implied by, the dialogue. In CoDC, the task is to produce the reference caption (which is treated as a dialogue summary) from the dialogue (without using the images). Summarization models are evaluated on standard text overlap with the references, as well as an WordNet-based F1 metric that measures whether the model's output has inferred concepts in the references which were not mentioned in the dialogue.

summaries: The authors introduce a new problem, inferencing Concepts Out of DIalogue Context (CODC) wherein a ML model is tasked with producing concepts that are not explicitly mentioned in the input. The authors define this problem concretely and introduce metrics to study it. Particularly they define concepts as noun phrases that follow a very specific set of rules within wordnet. The authors propose metrics and a model to test the ability of systems on these CODC problems.

summaries: The paper tackles the problem of dialogue summarization, where a generated summary should include concepts that are not literally mentioned in the dialogue but can be inferred based on one’s commonsense. The paper provides precise definition of such concepts (called CODC in the paper) and evaluation metrics. It then proposes a new model that retrieves relevant concepts from ConceptNet, and feeds them to the text generator. Experiments show small improvements over a range of baselines in automatic evaluation, CODC evaluation, and manual human evaluation.

abstractText: In human dialogues, utterances do not necessarily carry all the details. As pragmatics studies suggest [Grice, 1975], humans can infer meaning from the situational context even though the meaning is not literally expressed. It is crucial for natural language processing models to understand such an inference process. In this paper, we address the problem of inferring Concepts Out of the Dialogue Context (CODC) in the dialogue summarization task. We propose a novel framework comprised of a CODC inference module leveraging external knowledge from WordNet and a knowledge attention module aggregating the inferred knowledge into a neural summarization model. To evaluate the inference capability of different methods, we also propose a new evaluation metric based on CODC. Experiments suggest that current automatic evaluation metrics of natural language generation may not be enough to understand the quality of out-of-context inference in generation results, and our proposed summarization model can provide statistically significant improvements on both CODC inference and traditional automatic evaluation metrics, e.g., CIDEr. Human evaluation of the model’s inference ability also demonstrates the superiority of the proposed model. Codes and data are available at https://github.com/HKUST-KnowComp/CODC-Dialogue-Summarization.

authors:
Jacob Andreas
Dan Klein

title: Reasoning about pragmatics with neural listeners and speakers

venue: In EMNLP,

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

venue: In ICLR,

authors:
Siddhartha Banerjee
Prasenjit Mitra
Kazunari Sugiyama

title: Multi-document abstractive summarization using ilp based multi-sentence compression

venue: In IJCAI,

title: Lexical entrainment in spontaneous dialog

venue: In International Symposium on Spoken Dialogue,

title: A pragmatics-based approach to ellipsis resolution

venue: Computational Linguistics,

authors:
Jiaao Chen
Diyi Yang

title: Multi-view sequence-to-sequence models with conversational structure for abstractive dialogue summarization

venue: In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP),

authors:
Michael Auli
Alexander M. Rush

title: Abstractive sentence summarization

title: Empirical methods for artificial intelligence, volume 139

venue: In NAACL HLT,

authors:
Devi Parikh
Dhruv Batra

title: Visual Dialog

venue: In CVPR,

authors:
Daniel Fried
Jacob Andreas
Dan Klein

title: Unified pragmatic models for generating and

authors:
Mike Lewis
Denis Yarats
Yann Dauphin
Devi Parikh
Dhruv Batra

title: Deal or no deal? end-to-end learning of negotiation dialogues

title: ROUGE: A package for automatic evaluation of summaries

venue: In Text Summarization Branches Out,

authors:
Tsung-Yi Lin
Michael Maire
Serge J. Belongie
James Hays
Pietro Perona
Deva Ramanan
Piotr Dollár
C. Lawrence Zitnick

title: Microsoft COCO: common objects in context

venue: In ECCV,

authors:
Yang Liu
Mirella Lapata

title: Text summarization with pretrained encoders

venue: In EMNLPIJCNLP,

authors:
Minh-Thang Luong
Hieu Pham
Christopher D Manning

title: Effective approaches to attention-based neural machine translation

authors:
Junhua Mao
Jonathan Huang
Alexander Toshev
Oana Camburu
Alan L. Yuille
Kevin Murphy

title: Generation and comprehension of unambiguous object descriptions

authors:
Sameer Maskey
Julia Hirschberg

title: Comparing lexical, acoustic/prosodic, structural and discourse features for speech summarization

venue: In INTERSPEECH,

authors:
Tomas Mikolov
Ilya Sutskever
Kai Chen
Greg S Corrado
Jeff Dean

title: Distributed representations of words and phrases and their compositionality

venue: In NIPS,

title: Wordnet: a lexical database for english

venue: Communications of the ACM,

authors:
Will Monroe
Robert X.D. Hawkins
Noah D. Goodman
Christopher Potts

title: Colors in context: A pragmatic neural model for grounded language understanding

venue: TACL,

authors:
Ramesh Nallapati
Bowen Zhou
Ćıcero Nogueira dos Santos
cCaglar Gülccehre
Bing Xiang

title: Abstractive text summarization using sequence-to-sequence rnns and beyond

venue: In SIGNLL,

authors:
Ani Nenkova
Amit Bagga

title: Facilitating email thread access by extractive summary generation

venue: In RANLP,

authors:
Tatsuro Oya
Yashar Mehdad
Giuseppe Carenini
Raymond Ng

title: A template-based abstractive meeting summarization: Leveraging summary and source text relationships

venue: In INLG,

authors:
Haojie Pan
Junpei Zhou
Zhou Zhao
Yan Liu
Deng Cai
Min Yang

title: Dial2desc: End-to-end dialogue description generation

authors:
Kishore Papineni
Salim Roukos
Todd Ward
Wei-Jing Zhu

title: Bleu: a method for automatic evaluation of machine translation

venue: In ACL,

authors:
Romain Paulus
Caiming Xiong
Richard Socher

title: A deep reinforced model for abstractive summarization

authors:
Jeffrey Pennington
Richard Socher
Christopher D Manning

title: Glove: Global vectors for word representation

authors:
Korbinian Riedhammer
Benoit Favre
Dilek Hakkani-Tür

title: Long story short–global unsupervised models for keyphrase based meeting summarization

venue: Speech Communication,

title: Pragmatics in machine translation

venue: In COLING,

authors:
Alexander M. Rush
Sumit Chopra
Jason Weston

title: A neural attention model for abstractive sentence summarization

authors:
Abigail See
Peter J. Liu
Christopher D. Manning

title: Get to the point: Summarization with pointer-generator networks

authors:
Guokan Shang
Wensi Ding
Zekun Zhang
Antoine Tixier
Polykarpos Meladianos
Michalis Vazirgiannis
Jean-Pierre Lorré

title: Unsupervised abstractive meeting summarization with multi-sentence compression and budgeted submodular maximization

authors:
Sheng Shen
Daniel Fried
Jacob Andreas
Dan Klein

title: Pragmatically informative text generation

venue: In NAACL-HLT,

authors:
Dan Sperber
Deirdre Wilson

title: Relevance: Communication and Cognition

authors:
Ilya Sutskever
Oriol Vinyals
Quoc V Le

title: Sequence to sequence learning with neural networks

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N. Gomez
Lukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Ramakrishna Vedantam
C. Lawrence Zitnick
Devi Parikh

title: Cider: Consensus-based image description evaluation

authors:
Ramakrishna Vedantam
Samy Bengio
Kevin Murphy
Devi Parikh
Gal Chechik

title: Context-aware captions from context-agnostic supervision

authors:
Sida I. Wang
Percy Liang
Christopher D. Manning

title: Learning language games through interaction

authors:
Wenbo Wang
Yang Gao
He-Yan Huang
Yuxiang Zhou

title: Concept pointer network for abstractive summarization

venue: In EMNLP-IJCNLP,

authors:
Zhibiao Wu
Martha Palmer

title: Verbs semantics and lexical selection

authors:
Shasha Xie
Yang Liu
Hui Lin

title: Evaluating the effectiveness of features and sampling in extractive meeting summarization

venue: In SLT,

authors:
Kelvin Xu
Jimmy Ba
Ryan Kiros
Kyunghyun Cho
Aaron C. Courville
Ruslan Salakhutdinov
Richard S. Zemel
Yoshua Bengio

title: Show, attend and tell: Neural image caption generation with visual attention

title: Automatic generation of concise summaries of spoken dialogues in unrestricted domains

venue: In SIGIR,

authors:
Chenguang Zhu
William Hinthorn
Ruochen Xu
Qingkai Zeng
Michael Zeng
Xuedong Huang
Meng Jiang

title: Boosting factual correctness of abstractive summarization with knowledge

heading: 1. Introduction

text:
Automatically summarizing conversations in our daily lives can benefit users for better organizing and retrieving their historical information. There have been several approaches to conversation summarization, including extractive approaches [Xie et al., 2008, Riedhammer et al., 2010] and abstractive approaches [Oya et al., 2014, Shang et al., 2018]. While extractive approaches focus on using the seen words in a conversation to summarize it, abstractive approaches usually use a text generation model to perform summarization.
Different from news articles, in daily dialogues, it is common that a speaker’s utterance can suggest something that is not literally expressed but can be interpreted by a cooperative listener. For example, in Figure 1, if a dialogue mentions boat and ocean, the first impression of an ordinary person would be a boat sailing on the ocean. If, a modifier abandoned is added to boat, combined with ocean, the previous scene will be canceled and we will think of a beach or a shore because that is where the abandoned boat and ocean tend to cooccur. This kind of out-of-context inference is a language phenomenon in the field of pragmatics
ground truth summarizations.
[Grice, 1975]. To comprehensively understand a dialogue where some context is omitted by the speakers, both a thorough understanding of the context and necessary inference are required. However, to the best of our knowledge, neither evaluation metrics nor suitable methods are available for such kind of out-of-context inference currently, even if it is an easy task for human beings.
To study the phenomenon of out-of-context inference in dialogues, we narrow down the definition of out-of-context inference to a certain type so that we can automatically evaluate it. Here, we only focus on summarization’s new concepts that are suggested by existing concepts in the dialogue context. This is also related to lexical entrainment [Brennan, 1996] which studies the lexical variability in language use and lexical pragmatics in relevance theory [Sperber and Wilson, 1986], which studies how to identify and infer concepts from words via broadening and narrowing contexts. To formally define the inference of new concepts in summarization, we distinguish a new concept from existing concepts following three rules according to WordNet [Miller, 1995]: (1) It should not be a general concept. (2) It should not be a synonym of an existing concept. (3) It should not be a hypernym (or super-concepts) of an existing concept. In this way, we can distinguish out-of-context inference from logical entailment or synonym as much as we can. Specifically, we name them as the Concept Out of the Dialogue Context (CODC.) Current evaluation metrics are usually based on lexical similarities or overlaps, e.g., BLEU [Papineni et al., 2002], ROUGE-L [Lin, 2004], METEOR [Lavie and Agarwal, 2007], CIDEr [Vedantam et al., 2015], etc. Such lexical metrics usually do not care about the recall of the novel words, and are not precise at evaluating the precision of the out-of-context inference. To tackle these limitations, we propose and study a new evaluation metric that incorporates CODC for text generation.
Moreover, to improve the summarization results with the help of CODC inference, we propose an abstractive summarization framework that includes an out-of-context inference module to enhance the model’s inference ability. The two-step framework we proposed basically contains an inference module and an extendable knowledge attention model. In the inference part, we use word-relatedness features such as co-occurrence, embedding similarities, and WordNet relatedness features to distinguish whether a candidate word is a plausible out-of-context inference or not. While in the knowledge attention module, we aggregate the retrieved knowledge from the inference module and apply the attention mechanism to extract useful information in the decoding steps.
Our contributions are summarized as follows:
1. We address the problem of out-of-context inference in dialogue summarization for the first time, and provide an elaborative definition of the problem.
2. We design a related metric based on Concepts Out-of Dialogue Context (CODC) to evaluate neural models’ ability to infer plausible novel concepts.
3. We proposed Trans-KnowAttn, an abstractive dialogue summarization approach that incorporates an out-of-context inference (missing-link inference) module and a knowledge attention module to improve the inference capability in dialogue summarization.

heading: 2. Dialogue Summarization Task

text: We develop our dialogue summarization (DialSum) task based on the VisDial [Das et al., 2017] dataset. To construct their dataset, VisDial asks two workers on Amazon Mechanical Turk to chat with each other in real-time to discuss an image in the MSCOCO dataset [Lin et al., 2014]. The MSCOCO dataset contains human-annotated captions of about 120K images. Each image has five captions from five different annotators. A “questioner” sees the caption of the image and another person sees both the caption and the image. The questioner is asked to ask questions to “imagine the scene better”, and the annotators usually describe the most prominent concepts in an image. Thus, for each image, we have both a dialogue from the VisDial dataset and five captions from the MSCOCO dataset. We align a dialogue with five captions as five alternative summarizations of the dialogue. By nature, there are many out-of-context inference phenomena behind those utterances, as the speakers already have the image in mind as their context so that they don’t need to bring it up again in the dialogue. Assuming a gold summarization y is provided by an annotator, we evaluate models’ inference ability by how many novel concepts (i.e., noun phrases that do not appear in the dialogue) in y can be mentioned by ŷ, the generated summary, without introducing extra noisy concepts. The number of examples in the training, developing, and testing set are 98,256, 12,282, and 12,083, respectively.

heading: 3. CODC-based Evaluation Metric

heading: 3.1 Definition of CODC

text:
In this section, we introduce the new metric based on CODC for evaluating models’ conceptual inference ability. Here, by concept, we mean a noun word. As most examples in our dataset are general objects rather than specific named entities, we use WordNet [Miller, 1995] to check the relations among all the concepts.
For each example in DialSum, which contains a dialog x and a description y, we denote the concept sets extracted from x and y as Cx and Cy respectively. Then we define the set of concepts out of dialogue context as
Cy−x = {cy ∈ Cy|∀cx ∈ Cx, I1(cx, cy) = 1)}, (1)
where I1(cx, cy) is the function implementing the following three rules: • The least depth of all synsets containing cy is no less than δd, where we set δd = 4 empirically (1,790 synsets in total are filtered out.) This rule is to filter out very general concepts that may be inferred by anything, for example, “entity”. • The shortest path between any pair of synsets containing cx and cy is greater than 1. This rule is to filter out concepts that are synonyms of existing concepts in the dialogue.
• Any synset of cy is not a hypernym (super-concept) of any synset of cx. This rule is to avoid entailment for the new concepts as essentially abstractive summarization is able to perform conceptual abstraction.
To better understand the dataset, we show the distribution of the counts of CODC per dialogue in Figure 2 (a), for one set of the descriptions in the training set. We can find that for more than 80% of the training dialogues, one or more CODC should be inferred. In Figure 2 (b), we show a real example from the dataset, where we can infer the word sky from the dialogue even if the word is not literally expressed. These observations show that the out-of-context concepts are common in this dialogue summarization task and further prove the importance of understanding how well models can generate summarization with out-of-context concepts.

heading: 3.2 CODC Precision, Recall, and F1

text:
As a model with strong inference ability should be able to infer correct new concepts without introducing wrong ones, inspired by the F1 evaluation metric, we design F1 over CODC to evaluate models’ inference ability. Let X = {x(1), x(2), ..., x(N)} be all dialogues in the evaluation set, where N is the size of the dataset, and Y = {Y(1),Y(2), ...,Y(N)} be the set of ground-truth descriptions. Note that, for each image, we may have K ground-truth descriptions such that Y(i) = {y(i)1 , ..., y (i) K }. Denote the generated summary of the i-th dialogue as ŷ(i). We then define the precision, recall, and F1 over CODC as follows:
PCODC =
∑N i=1 maxk |h(x(i), y (i) k , ŷ
(i))|∑N i=1 |Cŷ (i)−x(i) | ,
RCODC =
∑N i=1 |h(x(i), y
(i) k∗i , ŷ(i))|∑N
i=1 |C y (i) k∗ i −x(i) |
,
F1CODC = 2PCODCRCODC PCODC +RCODC ,
(2)
where h(x, y, ŷ) and k∗i are defined as follows:
h(x, y, ŷ) = {cŷ ∈ Cŷ−x|∃cy ∈ Cy−x, I2(cy, cŷ) = 1}, (3)
k∗i = argmaxk∈{1,...,K} |h(x(i), y(i)k , ŷ(i))| |Cy (i) k −x(i) | , (4)
and I2(cy, cŷ) is the function to determine whether cy and cŷ are identical or entailed following either of two rules: • There exists one pair of synsets of cy and cŷ being identical. • There exists a synset of cŷ being a hypernym of a synset of cy.
Note that a summary can be considered as a plausible generation if it covers a reasonable amount of CODCs for one of the K descriptions. Based on this idea, for a certain dialogue, we only focus on the description where the generated sentence performs the best in precision or recall regarding the inference of CODC. In this case, max operation is selected in the calculation of precision and recall, which is different from the average operation that is typically used by previous automatic evaluation metrics in the setting of multi-reference. Also, by using the max operations, we argue that the theoretical upper bound for CODC precision, recall, and F1 are 1.0, as any ground-truth description will be scored 1.0 under the max operation.

heading: 4. Knowledge-aware Summarization

text: In this section, we present Trans-KnowAttn, a knowledge-aware summarization framework which consists of a missing-link inference module and a flexible knowledge attention module that can be applied to general encoder-decoder models. An overview of the model is shown in Figure 3.

heading: 4.1 Missing-link Inference Module

text:
The missing-link inference module infers plausible concepts closely related to the concepts mentioned in the dialogue, while being out of the dialogue context. For example, considering the dialogue and ground-truth description in Figure 1, given beach and boat that are
mentioned in the conversation, we find a list that potentially contains the concept beach. This process is different from simple Knowledge Base Completion in that we want to infer the missing links between a concept with a set of dialogue concepts.
Following the definitions in the CODC metric, we first build a bipartite knowledge graph G = (V,E), V = (D,C), that records the co-occurrence information of dialogue concepts and CODCs in the training set. Here D represents the set of concepts in all training dialogues, and C represents the set of concepts in CODCs. The weight of each vertex u(cx), cx ∈ D or u(cy), cy ∈ C is assigned by their total number of occurrences in the training set. An edge (cx, cy), cx ∈ D, cy ∈ C exists if there are at least one dialoguedescription pairs such that I1(cx, cy) = 1, as has been defined in Equation (1.) The weight of the corresponding edge u(cx, cy) is the number of co-occurrence of the concept pair in the training set. Based on the formulation of the co-occurrence graph, we formalize the inference process as follows: 1. Extract all concepts using rules defined in Section 3 from a dialogue as c (1) x , c (2) x , . . . , c (k) x , where k is the number of extracted concepts for dialogue x. 2. Get the set ∪i=1,...,kN(c (i) x ) as primitive knowledge candidates, where N(c (i) x ) is the set of neighbors of vertex c (i) x in G. 3. Calculate features of all candidates and train a classifier to determine whether a candidate is a plausible CODC or not. The ground-truth CODCs are calculated based on the definition in Section 3. 4. In the inference process, use the classifier from the above step and retrieve top m results ranked by the classifier, among the set ∪i=1,...,kN(c (i) x ).
The features we use are described as follow:
Co-occurrence. A simulated co-occurrence feature of a candidate n ∈ ∪i=1,...,kN(c (i) x ) given a set of dialogue concepts {c(1)x , . . . , c(k)x } is defined as : Pco(n|{c(1)x , . . . , c(k)x }) ∝∑k i=1 log[ u(n,c (i) x )
u(c (i) x )
] , which is an ad-hoc attribute that depicts the log probability that a
candidate concept n will co-occur given all dialogue concepts.
Pre-trained Word Embedding Similarities. We compute the average word embedding similarities of candidate concept n with all the dialogue concepts {c(1)x , . . . , c(k)x } as : 1 k ∑k i=1 e c (i) x ·en
||e c (i) x ||·||en|| , where ec(i)x
and en are embedding vectors of c (i) x and n obtained from
existing pretrained vectors such as Word2Vec [Mikolov et al., 2013] and Glove [Pennington et al., 2014].
WordNet Synset Relatedness. We choose some typical similarity measurements based on WordNet as an indicator of relatedness, Path Similarity, i.e., the inverse of the number of nodes visited in the path from one word to another via hypernym hierarchy, LCH Similarity [Leacock et al., 2002], and WuP Similarity [Wu and Palmer, 1994].

heading: 4.2 Knowledge Attention Network

text:
Treating the inferred candidate list as knowledge, we provide a knowledge attention mechanism that can be added to general encoder-decoder frameworks. We choose Transformer as the base architecture of the seq2seq model. To generate summaries, the decoder computes
the hidden states and attends to the knowledge embedding list step by step, adjusting the current decoder state with the help of the attended knowledge vector. Also, a copy mechanism is used for copying useful candidate words directly from the knowledge candidate list. The model differs from the standard attention encoder-decoder framework in that an extra layer of knowledge attention is added to the decoding part. More detailed formulations of the summarization model are provided in Appendix A.

heading: 5. Experiments

heading: 5.1 Baselines

text: We select S2S-Attn [See et al., 2017], PGN [See et al., 2017], Trans-Copy [Vaswani et al., 2017], PairEncoder [Pan et al., 2018], and BertSum [Liu and Lapata, 2019] as baseline models: S2S-Attn is a typical sequence-to-sequence model with attention mechanism [See et al., 2017], where the encoder is a single-layer bi-LSTM and the decoder is a single-layer unidirectional LSTM. PGN is a hybrid pointer-generator network that can copy words from the source text via pointing mechanism [See et al., 2017]. Trans-Copy uses the Transformer network [Vaswani et al., 2017], which incorporates the self-attention mechanism in both encoder and decoder, and uses the copy mechanism for the decoder. PairEncoder [Pan et al., 2018] is a model particularly developed for the same problem as ours, where a modified encoder based on the Transformer network is developed to emphasize the interaction between two speakers. BertSum [Liu and Lapata, 2019] uses the pre-trained BERT [Devlin et al., 2019] as the encoder, and Transformer as the decoder.

heading: 5.2 Experimental Settings

text:
Inference Module: In the inference module, a Random Forest classifier from sklearn 1 is used to distinguish whether a candidate word is a plausible CODC or not, and we select top m = 13 candidates ranked by the classifier as the knowledge that is fed into the knowledge
1. https://scikit-learn.org
attention module. Details of the ablation study of this classification task are shown in Section 5.5.
Knowledge Attention Summarization Model: For all models except for PairEncoder, the input sequences are concatenated dialogue text with marks of <q> and <a> to identity different turns with two speakers. For PairEncoder, the input is a list of utterance pairs. All five references are used in the training process. Each dialogue is used in five training instances accompanied with the corresponding five captions. For models except for BertSum, we use a vocabulary of 20K words out of in total 28K words. For all RNN-based models, 256-dimensional RNN hidden states and 256-dimensional word embeddings are applied for both knowledge word embeddings and encoder-decoder embeddings. For Trans-Copy, the dimension of word embeddings is set to be 256. For the BertSum model, we follow the same experimental setting as its original paper [Liu and Lapata, 2019].

heading: 5.3 Evaluation

text:
Automatic Evaluation: Besides CODC metrics, conventional lexical metrics BLEU [Papineni et al., 2002], ROUGE-L [Lin, 2004], METEOR [Lavie and Agarwal, 2007], and CIDEr [Vedantam et al., 2015] are used for evaluation.
Human Evaluation: To better understand the effects of the knowledge attention module, we conducted human annotation on the overall quality and the out-of-context inference (missing-link inference) ability for 100 randomly selected summaries, generated by TransCopy and Trans-KnowAttn, respectively. Each pair of summaries were evaluated by 5 annotators. We run the evaluation using workers from Amazon Mechanical Turk (AMT.) Workers were given full illustrations about the definition of out-of-context inference and were asked to judge which summarization is better in terms of overall abstraction quality and outof-context inference ability. The summaries were randomly shuffled to prevent unexpected bias. There was also a neutral option for the annotators if they find no difference between the two given summaries.

heading: 5.4 Results and Evaluation

text:
Results of conventional metrics and CODC metrics are shown in Table 1. For the main metric, CIDEr, there’s a 1.2 points improvement from Trans-Copy to Trans-KnowAttn. In addition, the improvements on the CODC Recall and F1 are also significant, indicating that the inferential ability of the model is improved by the inference module. We carry out
a statistical test using Randomization Test [Cohen, 1995]. All the improvements except for BLEU-4 and PCODC are statistically significant. The human evaluation results are presented in Table 2 (a), where the scores for each model are proportional to the number of times a model is considered superior to the other. The scores in each columns are normalized so that the sum equals 1. We show that Trans-KnowAttn brings consistent improvements in terms of both inference ability and overall summarization quality.

heading: 5.5 Ablations

text:
Inference Module: We check the importance of different features by removing each of them in the random forest classifier. As shown in Table 2 (b), we report the retrieval results on the validation set under top 10 retrieval, and the CODC scores are calculated on the retrieved knowledge. It shows that keeping one of the w2v or glove similarities would boost the retrieval performance. Also, the co-occurrence feature is the most prominent one among all. In the end, we select the -w2v setting for the summarization.
Summarization Results: We study the overall F1CODC and CIDEr scores of the generated summaries, given the number of retrieved knowledge words that are fed into the knowledge attention model, as shown in Figure 4 (a). When the number of retrieved words m exceeds 4, the overall CIDEr score can outperform the Trans-Copy baseline. For F1CODC , it reaches the maximum when m = 12.

heading: 5.6 Case Study

text: We show an example of the generated results in Figure 4 (b). We observed concepts such as “skater,” “skateboard,” and “skate park” from the dialogue, from which a human will easily infer a “ramp” from the context which is a common environment where people play skateboards. The Trans-Copy model fails to infer such a new but highly relevant concept while Trans-KnowAttn will successfully yield this inference. More case studies will be presented in the appendix.

heading: 6. Related works

text: We introduce the related work in two-fold: neural text summarization and pragmatics tasks in NLP.

heading: 6.1 Neural Text Summarization

text: Conversation summarization has been studied extensively. It can be extractive approaches [Zechner, 2001, Nenkova and Bagga, 2003, Maskey and Hirschberg, 2005, Xie et al., 2008, Riedhammer et al., 2010] and abstractive approaches [Oya et al., 2014, Banerjee et al., 2015, Shang et al., 2018]. Nowadays, more attention has been paid to neural-networkbased approaches due to the successful application of deep learning in natural language generation. Most of the neural-network-based approaches [Rush et al., 2015, Chopra et al., 2016, Nallapati et al., 2016, See et al., 2017, Paulus et al., 2018, Wang et al., 2019] follow the sequence-to-sequence framework [Sutskever et al., 2014]. Especially, attention mechanisms [Bahdanau et al., 2015] are widely used in the sequence-to-sequence framework to improve the generation quality [Luong et al., 2015, Rush et al., 2015, Xu et al., 2015]. Selfsupervised pretrained language models, such as BERT [Devlin et al., 2019], are also applied to natural language generation tasks including summarization. Liu and Lapata [2019] introduced a document-level encoder based on BERT which would better capture the semantics of a document. More recently, external knowledge in knowledge graphs and local semantic knowledge graphs are also used to improve the correctness of factual statements and quality in abstractive summarization [Zhu et al., 2020, Huang et al., 2020]. Also, multi-view seq2seq models are designed [Chen and Yang, 2020] by combining conversational structures from different views for better representation of human conversations.

heading: 6.2 Pragmatics

text:
Pragmatics [Grice, 1975] has been studied in both linguistics and natural language processing for a long time. It generally studies the ways in which the context contributes to the meaning. Early approaches only consider cases or rule-based methods to evaluate pragmatics in language understanding and generation problems such as machine translation or dialogue systems [Rothkegel, 1986, Carberry, 1989, Iida et al., 1990]. Recent research focuses on using computational methods and automatic evaluation metrics in language games to evaluate the ability to infer through context [Frank and Goodman, 2012], which is usually called Rational Speech Acts (RSA) model. Wang et al. [2016] developed another language game and found that pragmatics models may not help the people who use less precise and consistent languages, as the pragmatics model assumes that the human is cooperative and behaving rationally. Fried et al. [2018] showed that explicit inference can also help learning-based RSA models.
Besides typical RSA models that committed to Grice’s original target, there are also several other interesting directions to explore in computational ways. Kazemzadeh et al. [2014] introduced a way to evaluate pragmatics, where an image is used to identify an object inside. Then one player is asked to provide referring expression for the object while the other is asked to localize the object based on the expression. Many models have been developed for this task [Mao et al., 2016, Andreas and Klein, 2016, Monroe et al., 2017, Vedantam
et al., 2017]. In addition, Lewis et al. [2017] introduced a negotiation generation task that implicitly needs pragmatics inference in the learning system. Another data (or task) is called CommitmentBank, which evaluates the inference of a speaker’s commitment towards the content of the complement under different entailment-canceling environments [Jiang and de Marneffe, 2019a,b]. Recently, Shen et al. [2019] improves text generation with techniques of computational pragmatics, which are comprised of information preservation and explicit modeling of distractors.

heading: 7. Conclusion

text: In this paper, we address the problem of out-of-context inference in dialogue summarization for the first time, and proposed Trans-KnowAttn to improve the inference ability of dialogue summarization. Based on our observation, such kind of inference is required for most of the dialogues in the DialSum dataset. Experiments demonstrate that the proposed model can outperform the previous state-of-the-art in terms of both traditional lexical metrics, and our newly proposed F1CODC significantly. We argue that with the help of out-of-context inference, neural models can better understand the pragmatics in human dialogues and thus improve the overall quality of summarization.

heading: Acknowledgment

text: The authors of this paper were supported by the NSFC Fund (U20B2053) from the NSFC of China, the RIF (R6020-19 and R6021-20) and the GRF (16211520) from RGC of Hong Kong, the MHKJFS (MHP/001/19) from ITC of Hong Kong, and the Tencent AI Lab Rhino-Bird Focused Research Program.

heading: Appendix A. Details of the Summarization Model

text:
We present the details of the Knowledge Attention part of the knowledge-aware summarization model in this section.
Encoder Formulation. The encoder part is the same as what has been commonly used in previous neural summarization models. The input to the encoder is a sequence of dialogue word tokens D = [w1, w2, · · · , wn], and the encoder produces a sequence of hidden states {h1, · · · , ,hn}.
Decoder Formulation and Knowledge Attention. In the decoding process, we include two attention channels, a standard attention that attends to encoder hidden states [Luong et al., 2015, Bahdanau et al., 2015] and a knowledge attention that attends to the retrieved knowledge list. Note that we infer knowledge in the word level and top m candidates scored by the classifier will be retrieved. Thus we denote the list of knowledge word embeddings as K = {k1,k2, · · · ,km}. For the t-th step of the decoder hiddent state st, we use st to query the encoder hidden states as well as the list of knowledge vectors. Here we use βh(hi, st) and βk(ki, st) as scoring functions in the calculation of attention distribution for encoder hidden states and knowledge attention respectively, where β can be an MLP or general function as in [Bahdanau et al., 2015]. The two attention based context vectors h∗t and k∗t are calculated as:
h∗t = ∑ i atihi and k ∗ t = ∑ i vtiki, (5)
where the corresponding distributions are:
ati = softmaxt(exp(βh(hi, st))), (6) vti = softmaxt(exp(βk(ki, st))). (7)
The knowledge context vector can be regarded as a fixed-size representation of the knowledge that has been inferred from the input dialogue. The context vectors h∗t and k ∗ t are concatenated with the decoder state st to produce the probability distribution over the vocabulary:
PV = softmax(V ′(V [st,h ∗ t ,k ∗ t ] + b) + b ′), (8)
where V , V ′, b, and b′ are learnable parameters. We follow See et al. [2017] to use two linear layers in this formulation.
The generation probability of copying from the input text pg ∈ [0, 1] is calculated as See et al. [2017]. To better facilitate the effects of the knowledge, we also apply a generation probability of knowledge pk ∈ [0, 1] as an indicator of copying concepts from the knowledge list. pg and pk for step t is calculated from the encoder context vector h ∗ t , the knowledge context vector k∗t , the decoder state st, and the decoder input xt:
pg = σ(W T h∗h ∗ t + W T s st + W T x xt + bg), (9) pk = σ(W T kh∗h ∗ t + W T ksst
+ W Tkxxt + W T k k ∗ t + bk),
(10)
where matices Wh∗ , Ws, Wx, and bg are learnable parameters for pg, and Wkh∗ , Wks, Wkx, Wk, and bk are learnable parameters for pk. Here σ is the sigmoid function.
Finally, both pg and pk are used to determine the probability of the next word to be generated. They serve as soft choices among sampling from PV , copying a word from the input dialogue, or copying a word from the knowledge list, by sampling from the corresponding attention distribution:
P (w) = 1
2 ((1− pg)PV (w) + pg ∑ i:wi=w ati)
+ 1
2 ((1− pk)PV (w) + pk ∑ i:wi=w vti).
(11)
The loss function for time step t is the negative log likelihood of the target word w∗t :
losst = − logP (w∗t ), (12)
and the total loss for the input sequence is:
loss = 1
T T∑ t=1 losst, (13)
where T is the total number of generated words.

heading: Appendix B. Case Studies

text: More case studies are presented in Figure 5.

title: Do Boat and Ocean Suggest Beach? Dialogue Summarization with External Knowledge