Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces
Authors: Yatin Nandwani
Deepanshu Jindal
Mausam .
Parag Singla
Venue: ICLR 2021 Poster (2021)
Keywords: Neuro symbolic
constraint satisfaction
reasoning

Abstract: Recent research has proposed neural architectures for solving combinatorial problems in structured output spaces. In many such problems, there may exist multiple solutions for a given input, e.g. a partially filled Sudoku puzzle may have many completions satisfying all constraints. Further, we are often interested in finding any "one" of the possible solutions, without any preference between them. Existing approaches completely ignore this solution multiplicity. In this paper, we argue that being oblivious to the presence of multiple solutions can severely hamper their training ability. Our contribution is two-fold. First, we formally define the task of learning one-of-many solutions for combinatorial problems in structured output spaces, which is applicable for solving several problems of interest such as N-Queens, and Sudoku. Second, we present a generic learning framework that adapts an existing prediction network for a combinatorial problem to handle solution multiplicity. Our framework uses a selection module, whose goal is to dynamically determine, for every input, the solution that is most effective for training the network parameters in any given learning iteration. We propose an RL based approach to jointly train the selection module with the prediction network. Experiments on three different domains, and using two different prediction networks,  demonstrate that our framework significantly improves the accuracy in our setting, obtaining up to 21 pt gain over the baselines.


Published as a conference paper at ICLR 2021
NEURAL LEARNING OF ONE-OF-MANY SOLUTIONS FOR COMBINATORIAL PROBLEMS IN STRUCTURED OUTPUT SPACES
Yatin Nandwani Deepanshu Jindal', Mausam & Parag Singla
Department of Computer Science, Indian Institute of Technology Delhi, INDIA (yatin. nandwani, deepanshu. sindal.calle mausam, parags) ) @cse. witd.ac......................... in
ABSTRACT
Recent research has proposed neural architectures for solving combinatorial prob- lems in structured output spaces. In many such problems, there may exist multiple solutions for a given imput, e-g. a partially filled Sudoku puzzle may have many completions satisfying all constraints. Further, we are often interested in finding any one of the possible solutions, without any preference between them. Existing approaches completely ignore this solution multiplicity. In this paper, argue that being oblivious to the presence of multiple solutions can severely hamper their training ability. Our contribution is two fold. First, we formally define the task of learning one-of-many solutions for combinatorial problems in structured output spaces, which is applicable for solving several problems of interest such N- Queens, and Sudoku. Second, we present a generic learning framework that adapts existing prediction network for combinatorial problem to handle solution multiplicity. Our framework uses selection module, whose goal is to dynamically determine, for every imput, the solution that is most effective for training the net- work parameters in any given learning iteration. We propose an RL based approach to jointly train the selection module with the prediction network. Experiments on three different domains, and using two different prediction networks, demonstrate that our framework significantly improves the accuracy in our setting, obtaining up to 21 pt gain over the baselines.
INTRODUCTION
Neural networks have become the de-facto standard for solving perceptual tasks over low level
representations, such pixels in an image audio signals. Recent research has also explored their application for solving symbolic reasoning tasks, requiring higher level inferences, such as neural theorem proving (Rocktäschel et al.
2015 Evans & Grefenstette 2018 Minervini et al., (020), and playing blocks world (Dong et al. 2019). The advantage of neural models for these tasks is that it will create unified, end-to-end trainable representation for integrated Al systems that combine perceptual and high level reasoning, Our paper focuses on one such high level reasoning task - solving combinatorial problems in structured output spaces, c.g., solving Sudoku or N-Queens puzzle. These can be thought of as Constraint Satisfaction problems (CSPs) where the underlying constraints are not explicitly available, and need to be learned from training data. We focus on learning such constraints by a non-autoregressive neural model where variables in the structured output space decoded simultaneously (and therefore independently). Notably, most the current state-of-the-art neural models for solving combinatorial problems, e.g., SATNET (Wang et al.) 2019), RRN (Palm) ct al. 2018). NLM (Dong et al. 2011), work with non autoregressive architectures because of their high efficiency of training and inference, since they do not have to decode the solution sequentially.
One of the key characteristics of such problems solution multiplicity there could be many correct solutions for any given input, even though may be interested in finding any one of these solutions. For example, in a game of Sudoku with only 16 digits filled, there are always multiple correct solutions (McGuire al. 2012), and obtaining any one of them suffices for solving Sudoku. Unfortunately, existing literature has completely ignored solution multiplicity, resulting in sub-optimally trained
"Equal contribution. Work done while IIT Delhi. Current email: deepanshu.jinda @ dolummi.iitd.a...

---

Published as a conference paper at ICLR 2021
networks. Our preliminary analysis of a state-of-the-an neural Sudoku solver PPlm et al. 2018 which trains and tests on instances with single solutions, showed that it achieves a high accuracy of 96% on instances with single solution, but the accuracy drops to less than 25%, when tested on imputs that have multiple solutions. Intuitively, the challenge comes from the fact that (a) there could be a very large number of possible solutions for a given input, and (b) the solutions may be highly varied. For example, a 16-givens Sudoku puzzle could have as many as 10,000 solutions, with maximum hamming distance between any two solutions being 61. Hence, we argue that an explicit modeling effort is required to represent this solution multiplicity.
As the first contribution of our work, we formally define the novel problem of One-of-Mann Man- Learning (1oML). It is given training data of the form {xx, xx,),, where Yx, denotes subset of all correct outputs Y's, associated with input x;- The goal of 1oML. is to learn a function f such that, for any input x, fxx) = y for some y E J'x. We show that naïve strategy that uses separate loss terms for each Yi)) pair where Yu E Xx, can result in a bad likelihood objective. Next, we introduce a multiplicity aware loss (CC-Loss) and demonstrate its limitations for non-autoregressive models on structured output spaces. In response, we present our first-cut approach, MINLOSS, which picks up the single Yuj closest the prediction ý; based on the current parameters of prediction network (base architecture for function f). and uses it to compute and back- propaagtee the loss for that training sample x;. Though significantly better than na've training, through simple example, demonstrate that MINLOSS can be sub-optimal in certain scenarios, due to its inability to pick a Yij based on global characteristics of solution space.
To alleviate the issues with MINLOSS, we present two exploration based techniques, I-EXPLR and SELECTR, that select Yú in non-greedy fashion, unlike MINLOSS. Both techniques are generic in the sense that they can work with any prediction network for the given problem. I-EXPLR relies on the prediction network itself for selecting Yij. whereas SELECTR is an RL based learning framework which uses a selection module to decide which Yij should be picked for a given input X,, for pack-propagating the loss in the next iteration. The SELECTR'S selection module trained jointly along with the prediction network using reinforcement learning, thus allowing us to trade-off exploration and exploitation in selecting the optimum Yu by learning a probability distribution over the space of possible yu's 's for any given input X1.
We experiment on three CSPs: N-Queens, Futoshiki, and Sudoku. Our prediction networks for the first two problems are constructed using Neural Logic Machines (Dong et al. 2019), and for Sudoku, we use a of-th-of-theart neural solver based on Recurrent Relational Networks (Palm et al. 2018). In all three problems, our experiments demonstrate that SELECTR vastly outperforms naïve baselines by up to 21 pts, underscoring the value of explicitly modeling solution multiplicity. SELECTR also consistently improves other multiplicity aware methods, viz. CC-Loss, MINLOSs, and I-ExPI.R.
BACKGROUND AND RELATED WORK
Related ML Models: There are a few learning scenarios within weak supervision which may appear similar to the setting of 1oML, but are actually different from it. We first discuss them briefly. 'aartial Label Learning' (PLL) (iin & Ghahramani] 2002; Cour et al.) [011 Xu al.] [019 Feng & An 2019 Cabannes et al.) 2020) involves learning from the training data where, for each input, a noisy set of candidate labels given amongst which only one label is correct. This is different from 1oML. in which there is no training noise and all the solutions in the solution set Y, for given are correct. Though some of the recent approaches to tackle ambiguity in PLL (Cabannes et al. 2020) may be similar to our methods, i.c., MINLoSS by the way of deciding which solution in the target set should be picked next for training, the motivations are quite different. Similarly, in the older work by (Jin & Ghahramani 2002), the EM model, where the loss for each candidate is weighted by the probability assigned to that candidate by the model itself, can be seen as a naive exploration based approach, applied to a very different setting. In PLL, the objective is select the correct label out of many incorrect ones to reduce training noise, whereas in loML, selecting only one label for training provably improves the learnability and there no question of reducing noise as all the labels are correct. Further, most of the previous work on PLL considers classification over a discrete output space with, say, L. labels, where as in loMI. we work with structured output spaces, e-g.. an r dimensional vector space where each dimension represents a discrete space of I, labels. This
Available https: ///ata//aaaaaaa/ dg1 a /mode1 s w/wrr//rreeee sudoku.pppppoooo 1p1
2

---

Published as a conference paper at ICLR 2021
exponentially increases the size of the output space, making it intractable to enumerate all possible solutions as is typically done in existing approaches for PLL (Jin & Ghahramani 2002).
Within weak supervision, the work on 'Multi Instance Learning' (MIL) approach for Relation Extraction (RE) employs a selection module to pick a set of sentences to be used for training a relation classifier, given set of noisy relation labels (Feng al. 2018 Qin et al.. 2018). This is different from us where multiplicity is associated with any given input, not with a class (relation).
Other than weak supervision, 1oML should also not be confused with the problems in the space of multi-label learning (Tsoumakas & Katakis 2007). In multi-label learning, given a solution set Yx for each input x, the goal to correctly predict each possible solution in the set Yx for x. Typically, a classifier is learned for each of the possible labels separately. On the other hand, in 1oML, the objective to learn any one of the correct solutions for a given input, and single classifier is learned. The characteristics of the two problems are quite different, and hence, also the solution approaches. As we show later, the two settings lead to requirements for different kinds of generalization losses.
Solution Multiplicity in Other Settings: There is some prior work related to our problem of solution multiplicity, albeit in different settings. An example is the task of andeo-prediction, where there can be multiple next frames (yij) for given partial video (Henaff et al. 2017 Denton & Fergus 2018). The multiplicity of solutions here arises from the underlying uncertainty rather than as a inherent characteristic of the domain itself. Current approaches model the final prediction as combination of the deterministic part oblivious to uncertainty, and a non-determinstie part caused by uncertainty. There is no such separation in our case since each solution is inherently different from others.
Another line of work, which comes close to ours is the task of Neural Program Synthesis (Devlin et al. 2017; [Bunel et al.) 2018). Given set of Imput-Outpu (IO) pairs, the goal is to generate valid program conforming to the IO specifications. For a given 10 pair, there could be multiple valid programs, and often, training data may only have one (or few) of them. Bunel et al. (2018) propose a solution where they define an alternate RL based loss using the correctness of the generated program on a subset of held out IO pairs as reward. In our setting, in the absence of the constraints (or rules) of the CSP, there is no such additional signal available for training outside the subset of targets x for an input x.
It would also be worthwhile to mention other tasks such as Neural Machine translation (Bahdanau al. 2013 Sutskever et al. 2014). Summarization (Nallapati et al.) 2017 Paulus et al., (0188). Image Captioning (Vinyals et al. 2017 You et al.) 2016) etc., where one would expect to have multiple valid solutions for any given input. E.g., for a given sentence language A, there could be multiple valid translations in language B. To the best of our knowledge, existing literature ignores solution multiplicity in such problems, and simply trains on all possible given labels for any given input.
Models for Symbolic Reasoning:
Our work follows the line of recent research, which proposes neural architectures for implicit symbolic and relational reasoning problems (Santoro et al., 2018 2019:
al. 2019).. We experiment with two architectures base prediction networks: Neural Logic Machines (NI.M5) (Dong et al., 2019), and Recurrent Relational Networks (RRNs) (Palm et al. 2018). NLMs allow learning of first-order logic rules expressed as Horn Clauses over a set of predicates, making them amenable to transfer over different domain sizes. The rules are instantiated over a given set of objects, where the groundings are represented as tensors in the neural space over which logical rules operate. RRNs use a graph neural network to learn relationships between symbols represented as nodes in the graph, and have been shown to be good at problems that require multiple steps of symbolic reasoning.
Palm et al. 2018 Waag et al.
3 THEORY AND ALGORITHM
3.1 PROBLEM DEFINITION
Each possible solution (target) for an input (query) x is denoted by an r-dimensional vector y E Vr, where each element of y takes values from a discrete space denoted by V. Let y = V", and let 3'x denote the set of all solutions associated with input x. We will use the term solution multiplicity to refer to the fact that there could be multiple possible solutions y for a given input x. In our setting, the solutions in Ddx span structured combinatorial subspace of V", and can be thought of as representing solutions to an underlying Constraint Satisfaction Problem (CSP). For example in N- N-Queens, x would denote a partially filled board, and y denote solution for the input board.
Notation:
3

---

Published as a conference paper at ICLR 2021
Given a set of imputs x; along with subset of associated solutions Yx S Dxx, i.e., given set of (xi, Yx,) pairs, we are interested in learning a mapping from x to any one y among many possible solutions for x. Formally, we define the One-of-Many- Maaninng (1oML) problem as follows.
Definition 1. Given training data DD of the form, { {(x, Y Yx,) )im where Xx, denotes a subset of solutions associated with input Xs, and m is the size of training dataset, One-of-Many-Loon (1oML) is defined as the problem of learning a function I such that, for any inpul x, f(x) - y for some y E Vx where Yx is the set of all solutions associated with
We use parameterized neural networks represent our mapping function. We use Me denote a autoregressivee network M with associated set of parameters + We use ýi (ÿ) to denote the network output corresponding to input x; (x), i.e. ý; (ÿ) is the arg max of the learnt conditional distribution over the output space y given the input (x). We are interested in finding a O that solves the 1oMI. problem as defined above. Next, we consider various formulations for the same.
3.2 OBJECTIVE FUNCTION
x; = [yi), Vi, the standard method to train such models is to minimize the total loss, I(O)= = Σ ( where ( y1) is the loss between the prediction ý1 and the unique target y1 for the input x We find the optimal O* as argming L(O). A Naïve extension of this for loML would be to sum the loss over all targets in Yx, i.e., minimize the following loss function: m
Naïve Objective: In the absence of solution multiplicity, i.e. when target set Y
L(
Σ
yu))
m
I-1 YUEYY
We observe that loss function in eq. ① would unnecessarily penalize the model when dealing with solution multiplicity. Even when is correctly predicting one of the targets for an input x;, the loss with respect to the other targets in Yx, could be rather high, hence misguiding the training process. Example| below demonstrates such a case. For illustration, we will use the cross-entropy loss, i.e. 1e(ý,y) y) Σx E, [y(k) ei) log( P(y [k] vz)), where in E V varies over the elements of V, and l indices over dimensions in the solution space. y(k] denotes the 1tth element of y
Example 1. Consider a learning problem over a discrete (Boolean) input space X = {0. 1) and Boolean target space in two dimensions, i.e., y = V {0, 1)². Let this be trivial learning problem where Vx, the solution set is Yx = {(, 1), 0)). Then, given a set of examples {xi, Y Yx
the Naive objective (with le as cross entropy) will be minimized, when P(ji[k] 0) P(yi(k] 1) = 0.5, for & E {1,2}, Vi. which can not recover either of the desired solutions: (0, 1) or (1,0).
The problem arises from the fact that when dealing with loML, the training loss defined in eq. is no longer a consistent predictor of the generalization error as formalized below.
Lemma 1. The training loss ((O) as defined in eq. ① is an inconsistent estimator of generalization error for 1oML, when le is a zero-one loss, i.e., ( Yij) 15; + yig]- (Proof in Appendix).
For the task of PIIL,, Jin & Ghahramani (2002) propose a modification of the cross entropy loss to
tackle multiplicity of labels in the training data. Instead of adding the log probabilities, it maximizes the log of total probability over the given target set. Inspired by |Fng al. (2020), we call it CC-
Loss: (9) - -. Em log (Ereey,, Pr (yulxi; @)). However, in the case of structured prediction. optimizing Loe requires careful implementation due to its numerical instability (see Appendix). Moreover, for non-autoregressive models, CC-L.Oss also suffers from the same issues Illustrated in example naive objective.
New Objective: We now motivate better objective function based on an unbiased estimator. In general, we would like Me to learn conditional probability distribution Pr(y] x;; +) over the output space y' such that the entire probability mass is concentrated on the desired solution set Yx,, iee, Eygey,, (r(y))x;; +) = 1, Vi. such a conditional distribution is learnt, then we can easily sample Yu E Yx, from it. CC-Loss is indeed trying to achieve this. However, ours being a structured output space, it is intractable to represent all possible joint distributions over the possible solutions in Y Yx,, especially for non-autoregresssvve model
2 AAtoreeresssve models may have the capacity to represent certain class of non-trivial joint distributions. e.g., Pr(v [1], l/2 could be modeled as Pr(v(1]>>) Pr())(())(())))) (r[[[]]b[1]] but requires sequential decoding during inference. Studying the impact of solution multiplicity on autoregressive models is heyond the current scope.
4

---

Published as a conference paper at ICLR 2021
Hence, we instead design loss function which forces the model learn distribution in which the probability mass is concentrated on any one of the targets Yuj E Yx.- We call such distributions as one-hot. To do this, introduce Yx, number of new learnable Boolean parameters, Wi, for each query Xj in the training data, and correspondingly define the following loss function:
I (o, w)
"yyle
I= YUEYx,
Here, wij E {0, } and Σj Wij 1. vi, where j indices over solutions Yij E x;. The last constraint over Boolean variables wy enforces that exactly one of the weights in wi is 1 and all others are zero.
Lemma 2. Under the assumption Xx,- Vx,, Vi. the loss L'()) minw L (O, w). defined as the minimum value of ( w) (defined in eq. (2) with respect to w, is a consistent estimator of generalization error for loMI, when le is a zero-one loss, i.e,, le (y), = 1 (y: # yu).
We refer to Appendix for details. Next, we define our new objective as:
min L (O, w) s.t. Waj [0, Vi, Vj and 8,w
Wij
1, = 1...m
(3)
3.3 GREEDY FORMULATION: MINLOSS
In this section, present one possible way optimize desired objective mine,w Lw I w) alternates between optimizing over the θ parameters, and optimizing over w parameters. While + parameters are optimized using SGD, the weights each iteration, i.e., it assigns a non-zero weight to the solution corresponding to the minimum loss amongst all the possible Yij E Yx; for each i 11... m.
selected greedily for given @ O at
Yij = argmin lem (5 . yeYx,
Vi = 1...m
(4)
This can be done by computing the loss with respect to each target, and picking the one which has the minimum loss. We refer to this approach as MINLOSS. Intuitively, for a given set of (()) parameters, MINLOSS greedily picks the weight vector (t) and uses them to get the next set of (t++l) parameters using SGD update.
( (t) ae ae Vel (O, w (0=)(") ww
(5)
One significant challenge with MINLOSS is the fact that it chooses the current set of w parameters independently for each example based on current θ values. While this way of picking the w parameters is optimal if θ has reached the optima, i.e. θ = O", it can lead to sub aub-optimal choices when both θ and w are being simultaneously trained. Following example illustrates this.
Ply=1)<033 Ply= 0.5
-0.55
Figure 1: Decision Boundary learnt by logistic regression guided by MINLoss. Green line at x = 0 is the initial decision boundary and black vertical line at x -0.55 is the decision boundary convergence.
Example 2. Consider a simple task with one-dimensional continuous input space
X C R, and target space y {0. 1). Consider learning with 10 examples, given as (x= 1, Yx = (5 examples), -1, optimal decision hypothesis is given as: = 1(x > for a < 22, or 1(x < 3), for 3 1. Assume learning this with logistic regression using MINLOSS as the training algorithm optimizing the objective in eq. (3). If we initialize the parameters of logistic such that the starting hypothesis given by y 1(x > 0} (logistic parameters: 0, 0.1, 6g 0). MINLOSS will greedily pick the target y 0 for samples with x -1, repeatedly. This will result in the learning algorithu converging the decision hypothesis y = 1(x > 0.55), which is sub-optimal since the input with x -2 is incorrectly classified (fig. [ see Appendix for detailed discussion).
(0,1)) (4 examples), (x = 2,
= (1}) (1 example). The Y. -2
MINLOSs is not able to achieve the optimum since it greedily picks the target for each query x; based on current set of parameters and gets stuck in local mimima. This is addressed in the next section.
5

---

Published as a conference paper at ICLR 2021
3.4 REINFORCEMENT LEARNING FORMULATION: SELECTR
In this section, we will design a training algorithm that fixes some of the issues observed with MINLOSS. Considering the Example abooe, the main problem with MINLOSS is its inability to consider alternate targets which may not be greedily optimal at the current set of parameters. A better strategy will try to explore alternative solutions as a way of reaching better optima, e.g., in example 2 we could pick, for the imput x = -1, the target = with some non-zero probability, to come out of the local optima. In the above case, this also happens to be the globally optimal strategy. This the key motivation for our RL-based strategy proposed below.
natural questions arises: how should we assign the probability of picking particu- lar target? A naive approach would use the probability assigned by the underlying Me network as a way of deciding the amount of exploration on each target y. We call it I-EXPLR. We argue below why this may not always be optimal choice.
Expected Reward R
R(g Vy EY2
x
Yx
Pro
x,yx-
M
G
My EYx
Me x
w,8
Loss
Selection Module S.
Lw
We note that the amount of exploration re- quired may depend in complex ways the global solution landscape, as well as the current set of parameters. Therefore, we propose strategy, which makes use of a separate selection module (a neural network), which takes as input, the current example (x), Y Yx).. and outputs the probability of picking each target for training θ in the next iteration. Our strategy RL-based since, we can think of choosing each target (for given input) as an action that our selection module needs to take. Our selection module is trained using reward that captures the quality of selecting the corresponding target for training the prediction network. We next describe its details.
Figure 2: Flow-diagram for our RL Framework
Selection Module (Sa): This an RL. agent or a policy network where the action is to select target, Yu E Yx,, for each X1. Given training sample, (x,, Yx,), it first internally predicts y1_ = (Me_(x)), using a past copy of the parameters O_. This prediction is then fed as an input along with the target set, Y Yx,, to latent model, Gs. which outputs probability distribution (yy), Vyjj E Yx,, s.t. Σy,, Pro(yu) = 1. So then picks a target yi E Yx, based on the distribution Prş(yu) and returns a W; such that vi, Wij- 1 if yıj Vi, and Wij O otherwise.
Update of á Parameters: The job of the selection module is to pick one target, Vi E Yx, for each input x,, for training the prediction network Me. If we were given oracle to tell us which yi is most suited for training Me. we would have trained the selection module S. to match the oracle. In train Sy using a reward scheme. Intuitively, Yi would be good
the absence of such oracle, choice for training Me. if it is "easier" for the model to learn to predict Vi- In our reward design, measure this degree of case using hamming distance between y; and Me 's prediction ýi, iee. Vi) = E 1
(y; [k] [k]]) We note that there are other choices as well for the reward, e.g., binary reward, which gives positive reward of only if the prediction model Me has learnt to predict the selected target yi. Our reward scheme is granular proxy of this binary reward and makes easier get a partial reward even when the binary reward would be 0.
The expected reward for RL can then be written as:
R(0)= - Pro (Vi)) R V))
(6)
i= yuEYY
We make use of policy gradient to compute the derivative of the expected reward with respect to the é parameters. Accordingly. update equation for & can be written as:
g ((++1) + (t()) + a V R (Ø) lo=مt))
(7)
Update of θ Parameters: Next step is to use the output of the selection module, w; corresponding
to the sampled target Vi. Vi, to train the Me network. The update equation for updating the θ parameters during next learning iteration can be written as:
(((+1) + ( ae VeLw (9, w) "elee"",
(8)
Instead of backpropagating the loss gradient at a sampled target Vi. one could also backpropagate the gradient of the expected loss given the distribution Prş(y)). In our experiments, we backpropagate

---

Published as a conference paper at ICLR 2021
through the expected loss since action space for the selection module Sg is tractable. Figure represents the overall framework. In the diagram, gradients for updating & flow back through the red line and gradients for updating ø flow back through the green line.
3.5 TRAINING ALGORITHM
We put all the update equations together and describe the key components of our training algorithm below. Algorithm presents detailed pseudocode.
Pre-training: It is common strategy in many RL based approaches to first pre-train the net- work weights using a simple strategy. Accord- ingly, we pre-train both the Me and So net- works before going into joint training. First, we pre-train Mo. In our experiments, we ob- serve that in some cases, pre-training Me us- ing only those samples from training data ID for which there is only a unique solution, ie.. { ((x, Yx,) E D s.t. YYxl 1) gives bet- ter performance than pre-training with MIN- Loss. Therefore, we pre-train using both the approaches and select the better one based on their performance on a held out dev set. Once the prediction network is pre-trained, a copy of given to the selection module initialize Me_. Keeping è and θ_ fixed and identical to each other, the latent model, Go, the selection module is pre-trained using the rewards given by the pre-trained Me and the internal predictions given by Me_.
Algorithm 1 Joint Training of Prediction Network Me & Selection Module Sh
Ou < Pre-train θ using eq. (4 and eq.
5
In Selection Module (SM): 6_ + Ou
Φ t
Pre-trriin & using rewards from Me eq.
Initialize: 0
while not converged do
B 4- Randomly fetch mini-batch
for do
Get weights: wi < Sy((x;, Yx,), (,), +.)
Get model predictions: y1 +- Mar (xi)
10
Get rewards: < [R()). Vyu Yx,]
end
Update d: Use eq. to get ((++1)
11
12
Update O: Use eq.
8 to get ((++1)
Update θ_ ( P/copyitr (in SM)
14
Increment +++
end
After pre-training, both prediction network Me and selection module Sş are trained jointly. In each iteration selection module first computes the weights, w for each sample in the mini-batch. The prediction network computes the prediction ff and rewards
Joint Training:
Vyy E Yx The parameters o' and O' are updated simultaneously using eq. ( and eq. (8) respectively. The copy of the prediction network within selection module, i.e., Me_ in Sg. is updated with the latest parameters O after every copystr updates where copyitr hyper-parameter
4 EXPERIMENTS
The main goal of our experiments to evaluate the four multiplicity aware methods: CC-LOss, MINLOSs, informed exploration (I-EXPLR) and RL based exploration (SELECTR), when compared to baseline approaches that completely disregard the problem of solution multiplicity. We also wish to assess the performance gap, if any, between queries with unique solution and those with many possible solutions. To answer these questions, we conduct experiments on three different tasks (N-Queenn Futoshiki & Sudoku), trained over two different prediction networks, as described below
4.1 DATASETS AND PREDICTION NETWORKS
N- N-Queens: Given a query, i.e., a chess-board of size N N and a placement of k < N non-attacking queens on it, the task of N Queens is to place the remaining N - k queens, such that no two queens are attacking each other. We train a Neural Logic Machine (NLM) model (Dong et al. 2019) as the prediction network Me for solving queries for this task. To model N N-Queens within NLM, we represent a query x and the target y as 2 dimensional Boolean vectors with 1 at locations where Queen is placed. We use another smaller NLM architecture as the latent model G
We train our model on 10-Queens puzzles and test on 11-Queens puzzles, both with placed queens. This lize-invariance in training and test is key strength of NI.M architecture, which we exploit in our experiments. To generate the train data, we start with all possible valid 10-Queens board configurations and randomly mask any 5 queens, and then check for all possible valid completions to
Further details of software environments, hyperparameters and dataset generation in the appendix.
7

---

Published as a conference paper at ICLR 2021
generate potentially multiple solutions for an input. Test data is also generated similarly. Training and testing on different board sizes ensures that no direct information leaks from test to train. Queries with multiple solutions have 2-6 solutions,
choose Yx; =>x,, VX,,
This is a logic puzzle in which we are given a grid of size x N, and the goal is to fill the grid with digits from {1 (1...N) such that no digit is repeated in row or a column. & out of N2 positions are already filled in the input query x and the remaining N - k positions need to be filled. Further, inequality constraints are specified between some pairs of adjacent grid positions, which need to be honored in the solution. Our prediction network, and latent model use NLM, and the details (described in Appendixx are very similar to that of N Queens.
Futoshiki:
Similar to N-Queens, we do size-invariant training - we train our models on 5 x 5 puzzles with 14 missing digits and test on 6 x puzzles with 20 missing digits. Similar N-Queens, we generate all possible valid grids and randomly mask out the requisite number of digits to generate train and test data. For both train and test queries we keep up to five inequality constraints of each type: > and <.
Sudoku: We also experiment on Sudoku, which has been used as the task of choice for many recent neural reasoning works (Palm et al. 2018 Wang et al. 2019). We use Relational Recurrent Networks (RRN) (Palm et al. 2018) as the prediction network since it has recently shown state-of-the-art performance on the task. We use a 5 layer CNN as our latent model Gg. Existing Sudoku datasets (Royle] 2014 Park 2018). do not expose the issues with solution multiplicity. In response, generate our own dataset by starting with a collection of Sudoku puzzles with unique solutions that have 17 digits filled. We remove one of the digits, thus generating puzzle, which is guaranteed to have solution multiplicity. We then randomly add 1 to 18 of the digits back from the solution of the original puzzle, while ensuring that the query continues to have more than I solution. This generates our set of multi-solution queries with a uniform distribution of filled digits from 17 to 34. We mix an equal number of unique solution queries (with same filled distribution). Because some X1S may have hundreds of solutions, we randomly sample 5 of them from Vx i.e., Yxx S 5 in the train set. For each dataset, we generate a devset in a manner similar to the test set.
Table I: Statistics of datasets. 'Train', "Test' and task names are abbreviated. Devset similar to test,
N-Qu (Tr)
N-Qu (Tst)
Futo. (Tr)
Futo. (Tst)
Sud. (Tr)
Sud. (Tst)
of queries
165,744
10,000 16.67%
10,000
10,000
20,000
10,000
Sage of MS queries
7.04%
17.05%
24.95%
50% 50%
Avg solns per MS query
2.1
2.2
2.2
2.4
13.8
13.7
4.2 BASELINES AND EVALUATION METRIC
Our comparison baselines include: (1) Naive: backpropagating L(9) through each solution indepen- dently using Equation L1. (2) Unique:
computing 1.(@) only over the subset of training examples that have a unique solution, and (3) Random: backpropagating L(O) through one arbitrarily picked solution y1 Y x; for every X1 in the train data, and keeping this choice fixed throughout the training.
We separately report performance on two mutually exclusive subsets of test data: OS: queries with a unique solution, and MS: those with multiple solutions. For all methods, we tune various hyperparameters (and do early stopping) based on the devset performance. Additional parameters for the four multiplicity aware methods include the ratio of OS and MS examples in training I-ExPLR and SELECTR also select the pre- pre-training strategy as described in Section 3.5 For all tasks, we consider the output of a prediction network as correct only it is valid solution for the underlying CSP. No partial credit is given for guessing parts of the output correctly.
4.3 RESULTS AND DISCUSSION
We report the accuracies across all tasks and models in Table 2 For each setting, we report the mean over three random runs (with different seeds), and also the accuracy via the devset (in the parentheses). We first observe that Naive and Random perform significantly worse than Unique in all the tasks, not only MS, but on OS as well. This suggests that, loML models that explicitly handle solution multiplicity, even if by simply discarding multiple solutions, are much better than those that do not recognize it at all.
the best of these runs selected
'Futoshiki and N- N-Queens training datasets have significant OS-MS imbalance (see Table T. necessitating managing this ratio by undersampling OS. This is similar standard approach in class imbalance problems.
8

---

Published as a conference paper at ICLR 2021
Table 2: Mean (Max) test accuracy over three runs for multiplicity aware methods compared with baselines. OS: test queries with only one solution, MS: queries with more than one solution.
Natve
Random
Unique
CC-Loss
MINLoss
I-EXPLR
SELECTR
Futoshiki N-Queens
OS
70.59 (70.56)
72.91 (73.86)
75.09 (75.76)
75.31 (76.19)
77.29 (78.00)
77.35 (79.01)
79.73 (80.12)
MS
55.34 (60.97)
61.13 (61.81)
66.85 (69 48)
75.76 (75.36)
77.22 (77.82)
79:46 (81.95) .95)
79.68 (82.37)
Overall
68.04 (68.96)
70.94 (71.85)
73.72 (74,71)
75.39 (76.05)
77.28 (77.97)
77.7 (79.50)
79.72 (80.50)
OS
65.59 (66.8)
65.49 (65.22)
67.63 (69.49)
77.68 (78.36)
76.78 (78.24)
78.15 (77.96)
78.01 (78.36)
MSS
14.99 (18.04)
14.22 (18.84)
19.13 (23.33)
69.3 (68.62)
70.35 (69.066
70.88 (73.71)
71.57 (72.42)
Overall
52.96 (54.63)
52.7 (53.65)
55.53 (57.97)
75.59 (75.933
75.18 (75.95)
76.33 (76.90)
76.4 (76.88)
Sudoku
OS
87.85 (89.08)
87.53 (86.24)
89.19 (90.24)
88.26 (86.78)
88 25.25 (88.22)
88.73 (89.62)
88.69 (87.94)
MS
09.13 (10.59)
13.65 (16.07)
66.39 (70.20)
76.58 (78.38)
76.93 (78.94)
80.19 (81 (5)
81.73 (85.45)
Overall
48.49 (49.84)
50.59 (51.15)
77.79 (80.22)
82.42 (82.58)
82.59 (83.58)
84.46 (85.54)
85.21 (86.70)
Predictably, all multiplicity aware methods vastly improve upon the performance of naive baselines, with dramatic 13-52 pt gains between Unique and SELECTR on queries with multiple solutions.
Comparing MINLOSS and SELECTR, we find that our RL-based approach outperforms MIN- Loss consistently, with p-values (computed using McNemar's 's test for the best models se- lected based on validation set) of 1.00e-16, 0.03, and 1.69e-18 for NQueens, Futoshiki and Sudoku respectively (see [Appendix] for seed- wise comparisons of gains across tasks). On the other hand, informed exploration technique, I-ExPL.. though improves over MINLOSS two out of three tasks, it performs worse than SELECTR in all the domains. This highlights the value of RL based exploration on top of the greedy target selection of MINLOSS as well as over the simple exploration of I-EXPLR. We note that this is due more exploratory power of SELECTR over I-EXPLR. See Ace(Appediix for more discussion and experiments comparing the two exploration techniques.
Figure 3: Accuracy vs size of query's 's solution set (with 95% confidence interval)
100
Rolling mean of Accuracy
80
60
SelectR
MinLoss Unique
10
20
30
40
# solutions of test query
Recall that Sudoku training set has no more than 5 solutions for query, irrespective of the actual number of solutions - i.e, for many X4. Yx, Dx,- Despite incomplete solution set, significant improvement over baselines is obtained, indicating that our formulation handles solution multiplicity even with incomplete information. Furthermore, the large variation in the size of solution set (Dxx ) in Sudoku allows us to assess its effect on the overall performance. We find that all models get worse as D increases (fig. 3) even though SELECTR remains the most robust (see Appendix for details).
5 CONCLUSION AND FUTURE WORK
In this paper, we have defined 1oML: the task of learning one of many solutions for combinatorial problems in structured output spaces. We have identified solution multiplicity an important aspect of the problem, which if not handled properly, may result in sub-optimal models. As first cut solution, we proposed greedy approach: MINLOSS formulation. We identified certain shortcomings with the greedy approach and proposed two exploration based formulations: I-ExPLR and an RL formulation, SELECTR, which overcomes some of the issues in MINLOSS by exploring the locally sub-optimal choices for better global optimization.
Experiments three different tasks using two different prediction networks demonstrate the effec- tiveness of our approach in training robust models under solution multiplicity
It is interesting note that for traditional CSP solvers, e.g. (Selman et al. 1993 Mahajan et al. 2004 a problem with many solutions will be considered an easy problem, whereas for neural models, such problems appear much harder (Figure T.. As future work, it will be interesting combine symbolic CSP solvers with SELECTR to design much stronger neuro-symbolic reasoning model.
'll the code and datasets are available at: http://str...oooo..ommmmeeeeetar

---

Published as a conference paper at ICLR 2021
LEGNONTEDGEMENT
We thank ITT Delhi HPC facility for computational resources. We thank anonymous reviewers for their insightful comments and suggestions, particular AnonReviewers for suggesting simple yet effective informed exploration strategy (I-EXPLR). Mausam is supported by grants from Google, Bloomberg, 1MG and Jai Gupta chair fellowship by IIT Delhi. Parag Singla is supported by the DARPA Explainable Artificial Intelligence (XAI) Program with number N66001-17-2-40333 Both Mausam and Parag Singla are supported by the Visvesvaraya Young Faculty Fellowships by Govt. of India and IBM SUR awards. Any opinions, findings, conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views or official policies, either expressed or implied, of the funding agencies.
REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: http://axxvvv..o orq/ abs/ 1445//473000733
Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In 6th International Conference
Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3. 2018, net/
Conference Track Proceedings. OpenReview.net, 2018. URL Corum?id=Hi Xw62kRZ
Vivien Cabannes, Alessandro Rudi, and Francis Bach. Structured prediction with partial labelling through the infimum loss. CoRR, abs/2003.00920, 2020. URL htttps://arxiv.rrrgr//// abs/ 7003000920
Timothée Cour, Benjamin Sapp, and Ben Taskar. Learning from partial labels. J. Mach. Learn. Res., 12:1501-1536, 2011. URLhttp://dd acm. org/ cetpg/cciaiiionn wwteaattoo...cmmiimm 1d=mm2d1=22203
Emily Denton and Rob Fergus. Stochastic video generation with a learned prior. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1182-1191 PMLR, 2018. URL h
//proceedings.. ml mww..ress.rpp...emmmmmmmmmmm
press b wwt.////////nnnneeeeeeeee html
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 990-998. PMLR, 2017. URL http: http:://roceediieg ottp://ciiinnaaiapppeeee//////// peress//70/deviiiine
mlrr
html
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans. LA. USA, May 6-9, 2019. OpenReview.net, 2019. URL
net forum?
10=B1xy-hRete
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. J. Artif. Intell. Res., 61:1-64, 2018. doi: 10. 3/1.r.44.1. URL. httpps://doi http//do.oorg///// www./or...... 1tt.//.1..61111110 5714
Jun Feng, Minlie Huang, Li Zhao, Yang Yang, and Xiaoyan Zhu. Reinforcement learning for relation classification from noisy data. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI- 18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 5779-5786. AAAI Press, 2018. URL https://www.cr aaai. org/ ocs index. httppe/pppppppaaaaaaaaaaaaaa /
http://soopprrooopttttigiiiiaitc
10

---

Published as a conference paper at ICLR 2021
Lei Feng and Bo An. Partial label learning with self- self-guided retraining. In The Thirty- Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty- Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, FAAI 2019, Honolulu, Hawaïi, USA, January 27 - February 1, 2019, pp. 3542 3549. AAAI Press, 2019. doi: org/10 1609.1609/60000 aaai. http://aaaavv3333... v33101 33013544
(6009/aai.v33300 330153.33 URLhttpss dooi
Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Provably consistent partial-label learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrlPS 2020, December 6-12, 2020, virtual, 2020. URL /tttpss:/pprceeeeinggg neurips............e............ ctpos.cccpppee cttppppppppccc.///////// hash/7bd28 Srao23214444fffff666666666666333
html
Mikael Henaff, Junbo Jake Zhao, and Yann LeCun, Prediction under uncertainty with error-encoding networks. CoRR, abs/171 /ttp//11..049999 104994, 2017. URL http:
Rong Jin and Zoubin Ghahramani. Learning with multiple labels. In Suzanna Becker, Sebastian Thrun, and Klaus Obermayer (eds.), Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, NIPS 2002, December 9-14, 2002, Vancouver, British Columbia, Canada), pp. 897-904. MIT Press, 2002. URL http:://ppppeeeee mips cc/
paper 2aper/2234-11 earni ng wi th- tiple labels
Yogesh S. Mahajan, Zhaohui Fu, and Sharad Malik. Zchaft2004: An efficient SAT solver. In Holger H. Hoos and David G. Mitchell (eds.), Theory and Applications of Satisfiability Testing, 7th International Conference, SAT 2004, Vancouver, BC. Canada, May 10-13, 2004, Revised Selected Papers, volume 3542 of Lecture Notes in Computer Science, pp. -750-77,.00 Springer, 2004. doi: 10.1007/1 1527695 URL TRL.https:///cc /ttttps://doi..o org.10..011..000 007 1111111227765777
Gary McGuire, Bastian Tugemann, and Gilles Civario. There is 16-clue sudoku: Solving the sudoku minimum number of clues problem via hitting set enumeration. Experimental Mathematics, 23:190-217,,011
Pasquale Minervini, Matko Bošnjak, Tim Rocktäschel, Sebastian Riedel, and Edward Grefenstette. Differentiable reasoning on large knowledge bases and natural language. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. AAAI Press, 2020.
Ramesh Nallapati, Feifei Zhai, and Bowen Zhou. Summarunner: A recurrent neural network based sequence model for extractive summarization of documents. In Satinder P. Singh and Shaul Markovitch (eds.), Proceedings of the Thirty- First AAAI Conference Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pp. 3075-308111111 AAAI Press, 2017. URL /1463
http:// aaai. orgg wtgg/cs////eooooooo//////////o// innex.ndxx.///// phpp AAAI Aww.A1//aaae//////a.aa
Rasmus Berg Palm, Ulrich Paquet, and Ole Winther. Recurrent relational networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò -isnchi, and Roman Gareet (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pp. 3372-3382, 2018. 7597 hetp//recurreetteeeee relationaa onal networks
pttttp:/paapes... www.ssiiiss...mmm ccc /aper/ wtt.scccsccppprr/
Kyubyong Park. Can convolutional neural networks crack sudoku puzzles? https://github: com/ Kyubyong/sudoki 2018.
Romain Paulus, Caiming Xiong, and Richard Socher. A deep reinforced model for abstractive sum- marization. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL wwtp///www...ecccccpppppee. / net/ forum? 11=HHAACIgA--
htttps://gtt
Pengda Qin, Weiran Xu, and William Yang Wang. Robust distant supervision relation extrac- tion via deep reinforcement learning. In Iryna Gurevych and Yusuke Miyao (eds.), Pro- ceedings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL 2018, Melbourne, Australia, July 15-20, 2018 Volume 1: Long Papers, pp. 2137-2147. As- sociation for Computational Linguistics, 2018. doi: 10. 10.18653/v1/P18- 1199. URL https 7/www. ac web. web. weaebborg//ntttho ogy/ 119977
11

---

Published as a conference paper at ICLR 2021
Tim Rocktäschel, Sameer Singh, and Sebastian Riedel. Injecting logical background knowledge
into embeddings for relation extraction. In NAACL HLT 2015, The 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language
Technologies, Denver, Colorado, USA, May 31- June 5, 2015, pp- 1119-1129, 2015. URL
http:// web. org/ aetgg/anto... Togy /N/ N/N 5/N15-118.1
Gordon Royle. Minimum sudoku. Sttps://staffee wwm.. uwa. edu at..
sudokumin php. 2014.
Adam Santoro, Ryan Faulkner, David Raposo, Jack W. Rae, Mike Chrzanowski, Theophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy P. Lillicrap. Relational recurrent neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Sesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pp. 7310-7321, 2018. Utt.tttp://// /tap::://paers..../ n nips. cc/ /aper/ 7960- relat ional recurrent neural networks
Bart Selman, Henry A. Kautz, and Bram Cohen. Local search strategies for satisfiability testing. In David S. Johnson and Michael A. Trick (eds.), Cliques, Coloring, and Satisfiability, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 11-3,, 1993, volume 26 of DIMACS Series in Discrete Mathematics and T'heoretical Computer Science, pp. 521 531.. DIMACS/AMS, 1993. doi: 10.1090/dimmcs/0226755 URL
dimacs 026/25
Iya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence sequence learning with neural networks. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q Weinberger (eds.), Advances in Neural Information Processing Systems 27: An- nual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Mon- treal, Quebec, Canada, pp. 3104-31101 2014. URL /paperss nww.. /aper/
Grigorios Tsoumakas and Ioannis Katakis. Multi-label classification; An overview. IJDWM, 3(3): 1-13, 2007. doi: 10.4018/jdmm URL 20C7070101
Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: Lessons learned from the 2015 MSCOCO image captioning challenge. IEEE Trans. Pattern Anal. Mach. Intell., 39(4):652-663, 2017. doi: 10. 21110//TAAM.22211255557777 1109/ P.A9I 2016 2587640
URL httpt:tt/////m /tops://doi.. org/10 10
Po-Wei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6545-6554. PMLR, 2019. URL http: htte:://proceeding
mlr.. prwss / v97 2ts///aaggll0 9e html
Ning Xu, Jiaqi Lv, and Xin Geng. Partial label learning via label enhancement. In The Thirty- AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-Firsi Innovative Applications of Artificial Intelligence Conference, TAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February wt009//aaai.3331.33333333333 7/doi org/ 0. 609/aaai... aaai:aaa....... v331 01 3301355555 5557
2029019 pp. 5557-5564 AAAI Press, 2019. doi:
URL https
Quanzeng You, Hailin Jin, Zhaowen Wang, Chen Fang, and Jiebo Luo. Image captioning with semantic attention. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 4651-4659. IEEE Computer Society, 2016. doi: 10.1 (09/C/PR.200...50
//tp:::///oo...o /tctpp:://ol..org10..11111 CVPR. 2016.502
12

---

Published as a conference paper at ICLR 2021
APPENDIX
THEORY AND ALGORITHM
3.2 OBJECTIVE FUNCTION
Lemma 1. The training loss L(O) as defined in eq. 1 is an inconsistent estimator of gemeralization error loML, when le is a zero-one loss, i.e. (i. 1(51 + yug) (Proof in Appendix).
Proof. Let D represent the distribution using which samples (x, 3'x) are generated. In our setting, gen- eralization error e( (M)) for prediction network Me can be written as: (MM)) = [(x.)())<l {ý & }/)),, where Me x). i.e. the prediction of the network on unseen example sampled from the underlying data distribution. Assume scenario when Yx; = Dx,, vi, i.e. for each input all the cor- responding solutions are present in the training data. Then, an unbiased estimator &D (Me) of the gen- eralization error, computed using the training data is written as: (D
> ( & Yx.). Clearly, the estimator obtained using L(O) (Naive Objective), when the loss function (Vi. Vu) is replaced by zero-one loss {ý: j YuJ. is not consistent estimator for the generalization error. This can be easily seen by considering a case when ýi E Yx, and Y > 1.
OPTIMIZATION ISSUES WITH CC-LOSS
For the task of PLL. Jin & Ghahramani (2022 propose modification of the cross entropy loss to tackle multiplicity of labels in the training data. Instead adding the log probabilities, it maximizes the log of total probability over the given target set. Inspired by Feng et al. (2020), call it CC-Loss:
m
(0)
log
Σ Pr(yulx;
m71
YUEYY,
However, in the of structured prediction, optimizing Lee suffers from numerical instability.
We illustrate this with an example. Consider solving 9 9 sudoku puzzle, x; The prohabilty of
particular target board, Yı,, is a product of = g2 81 individual probabilities over the discrete space V = {1 ..- 9} of size 9, i.e. Pr(yu X;; θ) = I - (r[yukk]e [x; θ). In the beginning of the training process, the network outputs nearly uniform probability over V for each the r dimensions, making Pr(y [";;;; Q) very small (= 9 9-81 ~ 5.09c-788 78). The derivative of log of such small quantity becomes numerically unstable.
This issue is circumvented in the case of naïve loss by directly working with log probabilities and log-sum-exp trick ? However, in the case of CC-Loss, we need to sum the probabilities over the target set Yx, before taking log, and computing Pr(yulxx Q) makes it numerically unstable. Motivated by log-sum-exp trick, we use the following modifications which involves computing only log probabilities. For simplicity of notation, we will use Pr(yu) to denote Pr(yu|x;; θ) and Li to denote the CC Loss for the 1th training sample.
L! oc
= log
Σ
Pr(yu)
YOEY
Multiply and divide by mazpi = maxyyeY, Pr(yu):
Pr(yu)
Li log
marpi
maxpi
Y
13

---

Published as a conference paper at ICLR 2021
Use the identity: exp(log(a)):
Pr(yi) marps
Lec
log(maxpi)) - log
Σ yuEX,;
exp
log
log(mazpp)) log
Σ
exp (log (Pr(yu)) log (mazpi))
YuEYx,
In the above equations, we first separate out the max probability target (similar to log-sum-exp trick), and then exploit the observation that the ratio of (small) probabilities more numerically stable than the individual (small) probabilities. Further, we compute this ratio using the difference of individual log probabilities.
Lemma 2. Under the assumption Yx; = Y',, vi, the loss L'(@) minw ( w), defined as the minimum value of (G, w) (defined in eq. (2) with respect to w, a consistent estimator of generalization error for loML, when lg is zero-one loss, i.e., (1i))y 1 1ý: # Yuj-
Proof. Let D represent the distribution using which samples Vx) are generated. In our setting, generalization error (MM) for a prediction network Me is:
e <MM) (xxx)))>D(( $ D())
where (x)x), i.e. the prediction of the network on unseen example sampled from the underlying data distribution. Assume scenario when Yx, = Vx vi, i.e., for each input all the corresponding solutions are present in the training data. Then, an unbiased estimator é of the generalization error, computed using the training data is written as:
(
Σ i=1
1 Yx
Now, consider the objective function
m
L'(0) min
Law ( w) min w
Σ
wi yu)
w
m
i=1 YIJY
1
min
whj 1(; + yij
m
YUEY,;
Yx
s.t. wy {0, 11 Vi, Vj and
wi = 1, Vi = 1...m
For any x,, if the prediction ý; is correct, i.e., Byij* E Yx, s.t. yıs then 1() * yij*] = and 1 ( # Yu) 1, Vyij E Yx,: Vij + yij.. Now minimizing over w; ensures ubj* and Wy = 0 Vyu E Yu. F Vij* Thus, the contribution to the overall loss from this example x zero. On the other hand if the prediction is incorrect then 1 ( + yuj 1, Vyj Yx thus making the loss from this example to be irrespective of the choice of wi. As result, L'(O) is exactly equal (MM) and hence it is consistent estimator for generalization error.
3.3 GREEDY FORMULATION: MINLOSS
Example 2. Consider simple task with one-dimensional continuous input space X' C R, and target space y = 1). Consider learning with 10 examples, given as (x 1, Y,Yx = {1}) examples), (x -1, Yx {0, 1)) (4 examples), (x -2, Y.Y., === {1}) (1 example). The optimal decision hypothesis given as: y = 1(x > a}. for a I -2, or = 1(x < for 3 2 1. Assume learning this with logistic regression using MINLOSS the training algorithm optimizing
14

---

Published as a conference paper at ICLR 2021
the objective in eq. (3). If we initialize the parameters of logistic such that the starting hypothesis given by y = 1(x > 0} (logistic parameters: 81 = 0.1, 8g = 0). MINLOSS will greedily pick the target y for samples with x -1, repeatedly. This will result in the learning algorithm converging to the decision hypothesis = 11 { > 0.55), which is sub-optimal since the input with Appendix for detailed discussion).
-2 is incorrectly classified (fig.
P(y=1) <0.
P(y=1) 0.5
X
-0555
-2
-1
2
Figure Decision Boundary learnt by logistic regression guided by MINLoSS.. Green vertical line is the initial decision boundary and black vertical line at x -0.55 is the decision boundary at convergence.
For logistic regression, when input x is one dimensional, probability of the prediction being I for any given point x = [z] is given as:
P(y = o 0o) where (2)
1 R
The decision boundary is the hyperplane on which the probability of the two classes, and 1, is same, i.e. the hyperplane corresponding P(y 0) P(y 1) 0.5 or 0 x +
Initially, 01 = 0.1 and 0g = 0 implies that decision boundary lies at x = 0 (shown in green). All the points on the left of decision boundary are predicted to have label while all the points on the right have 1 label. For all the dual label points (x = 1), P(y = 1) < 0.5, thus MINLOSs greedily picks the label 0 for all these points. This choice by MINLOSS doesn't 't change unless the decision boundary goes beyond- -1.
However, we observe that with gradient descent using sufficiently small learning rate, logistic regression converges boundary is sub-optimal since we can define linear decision boundary (y = 1(x >> a), for a S -2, y 1(x < B). for 3 > 1) that classifies all the points with label and achieves 100% accuracy.
-0.55 with MINL.OSS never flipping its choice. Clearly, this decision
4 EXPERIMENTS
All the experiments are repeated thrice using different seeds. Hyperparameters are selected based on the held out validation set performance.
Hardware Architecture: Each experiment is run on a 12GB NVIDIA K40 GPU with 2880 CUDA cores and 4 cores of Intel E5-2680 V3 2.5GHz CPUs.
We use Adam as our optimizer in all our experiments. Initial learning rate is set to 0.005 for NLM (Dong et al. 2019) experiments while it is kept at 0.001 for RRN (Palm al. 2018) experiments. Learning rate for RL. phase is kept at 0.1 times the initial learning rate. We reduce learning rate by factor of 0.2 whenever the performance the dev set plateaus.
Optimizer:
4.1 DETAILS FOR N-QURENS EXPERIMENT
Data Generation: To generate the train data, we start with all possible valid 10- 10-Queens board configurations. We then generate queries by randomly masking any 5 queens. We check for all
15

---

Published as conference paper at ICLR 2021
possible valid completions to generate potentially multiple solutions for any given query. Test data also generated similarly. Training and testing on different board sizes ensures that no direct information leaks from the test dataset to the train dataset. Queries with multiple solutions have small number of total solutions (2-6), hence we choose Yx; Vx,, Vxi.
VIW
SALE
WW
MELL
W!
WW
WML
W
Figure 5: 8- 8-Queens query along with its possible solution
Architecture Details for Prediction Network Mg: We use Neural Logic Machines (NLM) Dong ctt al. 2019) as the base prediction network for this task. NLM consists series of basic blocks, called 'Logic Modules', stacked top of each other with residual connections. Number of blocks in an NLM architecture referred to as its depth. Each block takes grounded predicates as input and learns to represent M intermediate predicates as its output. See (Dong al. (019) for further details. We chose an architecture with M = and depth = 30. We keep the maximum arity of intermediate predicates learnt by the network be 2.
Input Output for Prediction Network: Input to NLM is provided in terms of grounded unary and binary predicates and the architecture learns to represent an unknown predicate terms of the input predicates. Each cell on the board acts as an atomic variable over which predicates are defined.
To indicate the presence of Queen on cell in the input, we use unary predicate, 'HasQueenPrior' It is represented as Boolean tensor of size N2 with on k out of N cells indicating the presence of Queen. The output y the network is also a unary predicate 'HassQeen' which indicates the final position of the queens board.
Unary Predicates:
We use binary predicates to indicate if two cells are same row, same column, same diagonal or same off-diagonal. The binary predicates are a constant for all board configurations for given size and hence can also be thought of as part of network architecture instead of input.
Binary Predicates:
Architecture Details for Selection Module Sg:: use another NLM as our latent model G within the selection module Sg. We fix depth and M 10 for the latent model.
Input Output for Gs: Input to Ge is provided in terms of grounded unary and binary predictates represented as tensors just like the prediction network. G takes 1 unary predicate input, repre- sented as an N sized vector, Yij y1_. where ýi_ is the prediction from its internal copy of the prediction network (Me_) given the query x;. For each yij E Yx,- Go returns score which is converted into probability distribution Pro(Yu) over Yx, using softmax layer.
Hyperparameters:
The list below enumerates the various hyper- pprrmmtrrreetrrs with brief description (whenever required) and the set its values that we experiment with. Best value of a hyper-parameter is selected based on performance on held out validation set.
Data Sampling: Since number of queries with multiple solutions is underrepresented in the training data, we up-sample them and experiment with different ratios of multi-solution
Imagee Source: on o.t.rea....oo.....//./////./..on
taken from: http:///t.////tttt.o..oooo//o///
nes
16

---

Published as a conference paper at ICLR 2021
queries in the training data. Specifically, experiment with the ratios of 0.5 and 0.25 in addition to the two extremes of selecting queries with only unique or only multiple solutions. Different data sampling may be used during pre-training and RL fine tuning phases.
2. Batch Size: We batch size of 4. We selected the maximum batch size that can be accommodated in 12GB GPU memory.
3. copyitr: We experiment with two extremes of copying the prediction network after every update and copying after every 2500 updates.
4. Weight Decay in Optimizer: We experiment with different weight decay factors of 1F-4, IE-5 and 0.
5. Pretraining o: We pretrain Go for 250 updates.
Training Time: Pre-training takes 10 - 12 hours while RL fine-tuning take roughly 6 hours using the hardware mentioned in the beginning of the section.
4.1 DETAILS FOR FUTOSIIKKI EXPERIMENT
Data Generation: We start with generating all the possible ways in which we can fill a N x N grid such that no number appears twice in row or column. For generating query we sample any solution and randomly mask out positions on it. Also we enumerate all the GreaterThar and LessT han relations between adjacent pair of cells in the chosen solution and randomly add q of these relations to the query. We check for all possible valid completions to generate potentially multiple solutions for any given query. Test data is also generated similarly. Training and testing on different board sizes ensures that no direct information leaks from the test dataset to the training data. Queries with multiple solutions have a small number of total solutions (2-6), so we choose
x; = Vx. Vxi.
Architecture Details for Prediction Network Me: Same as N-Queens experiment.
Input Output for Prediction Network:
Just like N-Queens experiment, the input the network is a set of grounded unary and binary predicates. We define grid cell along with the digit to be filled in it as an atomic variable. There are 2 cells in the grid and each cell can take N values, thus we have 3 atomic variables over which the predicates are defined.
To indicate the presence of value in cell in the input, we use unary predicate. 'IsPresenPPrior. It is represented as Boolean tensor x of size 3 with on k positions indicating the presence of digit in a cell. The output y of the network is also unary predicate IsPresent' which indicates the final prediction of grid. Additionally, there are two more unary predicates which represent the inequality relations that need be honoured. Since inequality relations are defined only between pair of adjacent cells we can represent them using unary predicates.
Unary Predicates:
We use binary predicates to indicate if two vairables are in same row, same column, or same grid cell. The binary predicates are a constant for all board configurations for a given size N.
Binary Predicates:
Architecture Details for Selection Module Szt Same as N-Queens experiment.
Input Output for GZ: Same as N-Queens experiment except for the addition of two more unary predicates corresponding to the inequality relations. First unary predicate is yu Pi_ which is augmented with the inequality predicates.
Hyperparameters: Same as N-Queens experiment.
Training Time: Pre-training takes roughly 12 hours while RI. fine-tuning takes 7 hours.
4.1 DETAILS FOR SUDOKU EXPERIMENT
DATA GENERATION FOR SUDOKU
We start with the dataset proposed by Palm et al. (2018). It has 180k queries with only unique solution and the number of givens are uniformly distributed in the range from 17 to 34. 10 For the
Available http:///aaaaaaaaaaaaaaa/aaaaaaaa
17

---

Published as a conference paper at ICLR 2021
queries with unique solution, we randomly sample 10000 queries from their dataset, keeping their train, val and test splits. Using the queries with 17-givens from the entire dataset of size 180k, we use the following procedure to create queries with multiple solutions:
We know that for Sudoku puzzle to have a unique solution must have 17 or more givens (McGuire eet al. 2012). So we begin with the set of 17-givens puzzles having unique solution and randomly remove 1 of the givens, giving us a 16-givens puzzle which necessarily has more than correct solution. We then randomly add 1 to 18 of the digits back from the solution of the original puzzle, while ensuring that the query continues to have more than I solution. II] This procedure gives us multi-solution queries with givens in the range of 17 to 34, just as the original dataset of puzzles with only unique solution. We also observed that often there are queries which have very large number of solutions (> 100). We found that such Sudoku queries are often too poorly defined to be of any interest. So we filter out all queries having more than 50 solutions. To have the same uniform distribution of number of givens as in the original dataset of puzzles with unique solution, we sample queries from this set of puzzles with multiple solutions such that we have a uniform distribution of number of givens in our dataset.
We repeat this procedure to generate our validation and test data by starting from validation and test datasets from Palm et al. (0118).
Architecture Details for Prediction Network Me: We use Recurrent Relational Network (RRN) (Palm et al. 2018 as the prediction network for this task. RRN uses a message passing based inference algorithm on graph objects. We use the same architecture used by PPalm al. (2018) for their Sudoku experiments. Each cell in grid is represented as a node in the graph. All the cells in the same row, column and box are connected in the graph. Each inference involves 32 steps of message passing between the nodes in the graph and the model outputs a prediction at each step.
Input Output for Prediction Network: Input the prediction network is represented as 81 10 matrix with each of the 81 cell represented as a one-hot vector representing the digits (0-9, 0 if not given). Output of the prediction network is 81 10 x 32 tensor formed by concatenating the prediction of network at each of the 32 steps of message passing. The prediction at the last step is used for computing accuracy.
Architecture Details for Selection Module Sg: We use CNN as the latent model Gg. The network consists of four convolutional layers followed by a fully connected layer. The four layers have 100, 64, 32 and 32 filters respectively. Each filter has a size of 3 x 3 with stride of length 1.
Input Output for Gs= Similar to the other two experiments, the input to Go is the output ýi_ from the selection module's internal copy Me_ along with Yij- Since the prediction network gives an output at each step of message passing, we modify the Ge and the rewards for S., accordingly to be computed from prediction at each step instead of relying only on the final prediction.
Hyperparameters:
1. Data Sampling:
Since number of queries with multiple solutions and queries with unique solution are in equal proportion, we no longer need to upsample multi-solution queries.
2. Batch Size: We use a batch size of 32 for training the baselines, while for RL based training we use a batch size of 16.
3. copyitr: We experiment with copyitr = 1 i.e. copying Me to Me_ after every update.
4. Weight Decay in Optimizer: We experiment with weight decay factor of IE-4 (same as Palm al. (2018))
5. Pretraining 6: We pretrain G for 1250 updates, equivalent one pass over the train data.
Comparison with pretrained SOTA Model: We also evaluate the performance of pretrained state-of-the-art neural Sudoku solver (Palm et al. [2018]] [3 on our dataset. This model trains and tests on instances with single solution. The training set used by this model is a super-set of the
"We all solutions to http://ttaa///t.aaooooo/////a///
12Code taken from:
Available at: http:://aaa..aaaaaaaaccca/////aa
18

---

Published as a conference paper at ICLR 2021
Table Mean test accuracy (#standard error) over three runs for multiplicity aware methods compared with baselines. OS: test queries with only one solution, MS: queries with more than one solution.
Naive
Random
Unique
CC-Loss
MINLoss
I-EXPLR
SELECTR
N-Queees
OS
70.59 0.09
75.09 + 0.33
72.91 = 0.65
75.31 = 0.45
77.29 0.38
77.35 + 1.07
79.73 + 0.34
55.34
1,13
75.76
1.60
77.22
1.35
Overall
68.04 0.46
73.72 +: 0.59
70.94 + 0.71
75.39 + 0.47
77.28
0.48
77.70 + 1.40
79.72 +: 0.46
Sudoku Futoshiki
OS
65.59 :: 0.62
67.63 +:
65.49 = 0.28
77.68
0.34
76.78
0.81
78.15
78.01 +
MS
14.99 + 2.17
19.13 +: 3.14
14.22 = 2.77
69.30 = 1.76
70.35
1.16
70.88 + 1.48
71.57 : 1.02
Overall
52.96 0.96
55.53 + 1.44
52.70 = 0.74
75.59
0.46
0.64 75.18
76.33
0.65
76.4 + 0.36
OS
87.85 + 0.84
89.19 + 1.12
87.53 + 0.82
88.26 + 0.88
88.25
0.35
88.73 + 0.68
88.69 + 0.55
MS
09.13 0.89
66.39 2.82
13.65
1.79
76.58
1.63
76.93
1.50
80.19 1.51
81.73 :: 2,00
Overall
48.49 0.86
77.79 + 1.96
50.59 = 0.49
82.42
0.45
82.59 0.62
84.46 0.69
85.21 + 0.76
unique solution queries in our training data and contains 180,000 queries. This model achieves a high accuracy of 94.32% on queries having unique solution (OS) in test data which is random sample from their test data only, but the accuracy drop to 24.48% when tested on subset of our test data having only queries that have multiple solutions (MS). We notice that the performance worse than Unique baseline, even though both are trained using queries with only unique solution. This is because the pretrained model overfits on the the queries with unique solution whereas the Unique baseline early stops based on performance on a dev set having queries with multiple solutions as well, hence avoiding overfitting on unique solution queries.
MS is
Training Time: Pre-training the RRN takes around 20 - 22 hours whereas RL fine-tuning starting with the pretrained model takes around 10- 12 hours.
4.3 RESULTS AND DISCUSSIONS
Table reports the mean test accuracy along with the standard error over three runs for different baselines and three approaches. Note that the standard errors reported here over variations in the choice of different random seeds and it is difficult to do large number of such experiments (with varying seeds) due high computational complexity. Below, we compare the performance gains for each of the seed separately.
Seed-wist Comparison for Gains of SELECTR over MINLOSS
In Table we see that SELECTR performs better than MINLOSS for each of the three random seeds independently in all the experiments. We note that starting with the same seed in our implementation leads to identical initialization of the prediction network parameters.
Table 4: Seed wise gains of SELECTR over MINLoSs across different random seeds and experiments
Seed
NQueens Sudoku
Futoshiki
42
3.12%
3.40%
0.69%
1729
2.75%
2.53%
1.21% %
3120
1.98%
1.39%
1.77%
Avg. Gain
2.61%
2.44%
1.22%
Details of the Analysis Depicted in Figure
The large variation in the size of solution set ([)x in Sudoku allows to assess its effect on the overall performance. To do so, we divide the test data into different bins based on the number of possible solutions for each test input (x₂) and compare the performance of the best model obtained in the three settings: Unique, MINLOSS and SELECTR.
19

---

Published as a conference paper at ICLR 2021
By construction, the number of test points with a unique solution is equal to the total number of test points with more than one solution. Fur- ther, while creating the puzzles with more than one solution, ensured uniform distribution of number of filled cells from 17 to 34, as is done
Figure 6: #givens and #datapoints vs size of query's s solution set
30
Givens (left)
# Queries (right)
Nggroee #Givens
# queries
in (Palm al. 2018) for creating puzzles with unique solutions in their paper. Hence, the num- ber of points across different bins (representing solution count) may not be the same. Figure 6 shows the average size of each bin and the aver- age number of filled cells for multiple solution queries in a bin. As we move to the right in graph (i.e., increase the number of solutions for a given problem), the number of filled cells in the corresponding Sudoku puzzles decreases, re- sulting in harder problems. This is also demonstrated by the corresponding decrease in performance of all the models in Figure 3 SELECTR most robust this decrease in performance.
400
24
22
122
200
60
20
30
40
# salutions of a test query (multiple solution queries only)
Discussion on Why SELECTR is better than I-EXPLR?
In this section, argue why SELECTR is more powerful than I-EXPLR, even though the reward structure for training the RI. agent is such that eventually the G in the RI. agent will learn to pick the target closest the current prediction (to maximize reward), and hence Sy will be reduced to I-EXPLR.
We two reasons why SELECTR is better than I-EXPLR.
First, recall that the I-EXPLR strategy gives the model an exploration probability based on its current prediction. But note that this is "only one" of the possible exploration strategies. For example, another strategy could be to explore based on a fixed epsilon probability. There could be several other such possible exploration strategies that could be equally justified. Instead of hard coding them, as done for I-EXPLR, our G& network gives the ability to learn the best exploration strategy, which may depend in complex ways on the global reward landscape (i.e., simultaneously optimizing reward over all the training examples). Hence we use neural module for this.
Second, note that I-EXPLR is parameter- free and fully dependent on Me. thus, has limited represen- tational power of its own to explore targets. This is not the case with G Its output y and and the target (y.) closest Me prediction ý may differ i.e. y # Ye (see next paragraph for an experiment on this). When this happens, the gradients will encourage change in θ so that y moves towards y, and simultaneously encourage change in á so that y moves towards y.- That is, stable alignment between the two models could be either of the two, y. or This, we believe, increases the overall exploration of the model. Which of yc or y get chosen depends on how strongly the global landscape (other data points) encourage one versus the other. Such flexibility is not available I-ExPLR where only O parameters are updated. We believe that this flexibility to explore more could enable SELECTR jump off early local optima, thus achieving better performance compared to I-EXPL..
We provide preliminary experimental evidence that supports that SELECTR explores more. For every training data point q, we check if the arg max of G probability distribution (i.e., highest probability y) and y. differ from each other. We name such data points "exploratory". We analyze the fraction of exploratory data points as a function of training batches. See fig. 7 We observe that in the initial several batches, SELECTR has 3 10% of training data exploratory. This number is, by definition, 0% for I-EXPLR since chooses y based on model probabilities. This experiment suggests that SELECTR may indeed explore more early on.
20

---

Published as a conference paper at ICLR 2021
Figure 7: Fraction of training samples for which arg max of Gø probability distribution different from the target closest model prediction. For I-EXPLR, this fraction is 0%
N-Queens
Futoshiki
Sudoku
argmarlGviizz Loss))
35-
Fraction over last
250 upcates
2.0
Fractioo over last 250 upcates
10
1000 updates
Fraction ever last
Rolling mean
Rolling mean
Rolling meann
3.0
2.5
2.5
2.0
Fractio
2.00
1.5
2.5
1.0-
0.5-
0.5
0.0
0.0
15
updates thousands
updates thousands
updattss thousands
21


Reviews:
[{"review_id": "sLWZe_cBWS4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\t1. Summary & contributions\nThis paper formalizes the 'one-of-many-learning' problem and proposes a method for solving this problem.\n\nThe paper first defines the one-of-many-learning problem, where a model must learn to map an input x to one of many possible targets y, where all possible y or only a subset may be given, in particular in a combinatorial setting. The paper explains failures of naïve approaches such as summing the loss over all possible y or only taking into account the y which has the lowest loss for the current model.\n\nThe paper then introduces the 'SelectR' framework where a separate neural network model (the selection module) is trained to predict which of the targets should be used for training the main model. The models are trained jointly using RL, where the selection module is trained to match the prediction of the main model and the main model minimizes the loss on the target selected by the selection module.\n\nThe authors demonstrate improved results compared to different (relatively simple) baselines in three different constraint satisfaction problems: N-Queens, Futoshiki and Sudoku.\n\n\t2. Strengths & weaknesses\nThis paper addresses an interesting problem which is well motivated, well defined and clearly and extensively related to other problem settings from the literature. The paper explains the problem clearly and gives good examples of failure modes of naïve approaches, motivating an alternate approach.\n\nThe paper shows that indeed performance improvements can be achieved by using such an alternate approach which explicitly considers the one-of-many-learning problem, by training a selection module to select the target used for training dynamically, in a joint fashion using RL.\n\nThe main weakness of the paper is that the specific proposed solution/framework (training a selection module using RL) is in my opinion not well motivated. The motivating problem (with the naïve MinLoss strategy) seems to be (lack of) exploration: can't this be addressed simply by adding some randomness (e.g. sampling target proportional to loss or model probability). Why is a separate neural network module needed?\n\nAlso, I do not understand the reward structure (# predicted variables equal to main model). It seems that the selection module is trained to basically match the prediction of the main model, and the paper states that this is 'since we do not know a-priori which y is optimal for defining the loss'. How does training a separate model to match the main model prediction help overcome this problem?\n\nWhile the results do show the benefit of the 'SelectR' framework, I would like to see them compared to a simple (informed) strategy such as sampling a target according to model probability / loss / MinLoss with some epsilon probability of using a random target. The results may help in answering above questions.\n\nAlthough I like the writing in general, I think the paper uses too much math notation and formalism. For example, the concepts of MinLoss and SelectR are relatively simple, but the notation in terms of one-hot w_ij makes things unnecessarily hard(er) to read and complicated. I think also the Lemma's and examples would be better explained with words than with heavy math, to help understanding. As a bonus, removing a lot of the math would allow for very helpful Algorithm 1 and maybe Figure 3 of the Appendix to be included in the main text.\n\n\t3. Recommendation\nMy current assessment is that the paper is marginally below the acceptance threshold.\n\n\t4. Arguments for recommendation\nThe paper addresses a well motivated and well explained problem and the results obtained using SelectR improve over the baselines, but it does not convince (enough) that such a (relatively complicated) approach is actually beneficial from a practical point of view as simpler alternatives are underexplored (see strengths & weaknesses). Additionally, I think the paper should use less formal notation as that will make the paper easier to read without losing the content.\n\n\t5. Questions to authors\nSee also strengths & weaknesses\n- Do I understand correctly (from the formula for the cross entropy loss function) that Example 1 assumes a model which predicts y_1 and y_2 independently? I can imagine an autoregressive (structured) model which has p(y_1 = 1) = 0.5 and p(y_2 = 1|y1=1) = 0 and p(y_2 = 1|y_1 = 0) = 1 so p(1,0)=p(0,1)=0.5, which is optimal. It seems to me that the problem arises because of the independence structure of the variables in the model combined with the loss function (i.e. summing the log-probs for all targets).\n- Why does Lemma 1, which is posed as a formalization of the problem arising in Example 1, consider a zero-one loss whereas Example 1 is based on a cross-entropy loss? This is confusing to me.\n- The paper repeatedly mentions a 'prediction y^hat' as output of the main model. How is this defined? The model outputs a (structured) probability distribution but y^hat seems a vector. Is this vector a sample/argmax solution?\n\n\n\t6. Additional feedback\n\nMinor comments/suggestions:\n- The paper claims that compared to Neural Program Synthesis (NPS), where a generated program can be verified, in the setting considered in the paper there is no such additional signal available. However, the experiments all consist of problems where a solution can be  verified easily, even if it is outside the target set, so this does seem similar to NPS.\n- It seems that forcing all probability mass to concentrate on one target can be helpful for some models (i.e. Example 1 if we assume independence of the variables), but may also be (unnecessarily) restrictive for other models which could more easily divide the probability mass. Maybe this would be interesting to discuss/investigate.\n- The paper notes that 'one could also backpropagate the gradient of the expected loss given Pr(y_ij)'. This seems preferred to sampling, so a bit more discussion on why this was or was not used would be interesting.\n- I would not consider the parameters of the main model as 'input' for the selection module. I would just say it takes as input the prediction from the main model.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "m8hJ8HiDALB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe authors work in the domain of applying neural networks to combinatorial problems with structured output space, such as sudoku and n-queens. They notice how models currently performing well at this task encounter difficulties when there are multiple possible solutions. They formalize the task of learning any of multiple given (and possibly quite different) labels and propose an RL based approach to solve that task. They show improvements over selected baselines. \n\nGreat:\n* The discussion of why the task is different from other instances of multiple labels is well argued and clear.\n* Numerical examples are very helpful in following the description of the algorithms.\n* The evaluation setting is well thought of: utilizing the state of the art model and comparing it to reasonable baselines (one of which is indeed current SoTA). The experiments seem reproducible, given the detailed descriptions in the appendix.\n\n\nCould be improved:\n* Table 2 is perhaps misleading. Table 3 with the same results with standard deviation gives a less clear answer on whether SelectR is actually always better than MinLoss (careful with significant digits, the standard deviation can’t have more than one!).\n* The experiment depicted in figure 2 isn’t discussed, it doesn’t report confidence intervals, the distribution of training samples is not discussed (are there significantly less training examples with 50+ solutions, that could justify the drop in performance? A sudoku with this many solutions is likely to be quite sparse, does that affect performance?).\n\n\nIn summary, the paper introduces and formalizes an interesting novel task in the context of combinatorial problems with structured output space. While aspects in the evaluation could be clarified, the paper is clear and interesting. I recommend an accept, and would be willing to increase the score if my concerns are addressed.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "OAyWxwJV_gD", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The quality and clarity of the paper is good overall. In my opinion the presentation is clear, the goal of the work, and the proposed solutions are presented cleanly. Authors give a few examples of the issues raised by learning from many correct solutions, which is appreciated.\n\nIn terms of significance. I believe the theory is not surprising at all, it is straightforward to see that eq.(1) will not be a consistent loss function for generalization. Now, in Lemma 2, given the definition of eq.(2), it is also not surprising to see that it is a consistent estimator, and in fact, the proofs are rather trivial. Thus, from the theoretical viewpoint these issues undermine the paper.\nFrom the practical viewpoint, authors show that their proposed method SelectRL is better than other baselines, and my main concern in the practicality of the algorithm is that I don't see a strong case where SelectRL is significantly better than MinLoss, at least not statistically. Thus, my question here is, can authors claim that SelectRL is better than MinLoss from the experiments? If so, the gain seems small, and computationally speaking training an RL agent to select a solution seems an overkill.\n\nAnother question is: in the Random baseline, was the solution being picked uniformly at random? If so, wouldn't a distribution that is concentrated around a solution be better? I would've liked to see this in the experiments. If authors can comment on this question would be appreciated.", "extra_scores": {}, "extra_text": {}}, {"review_id": "MEb4VqJsdpb", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims at devising a targeted approach that takes into account the specific structure of combinatorial problems with multiple solutions. The proposed approach leverages RL to select the best targets among the solution sets at each iteration. SelectR convincingly outperforms both the naive and a cleverer baseline, showcasing the applicability of the method.\n\nOriginality\nThe problem of interest is relevant to a number of machine learning applications but has largely been ignored by the community up until now, as is made clear in the very complete related works section of the paper. Notably, the question of selecting the best target for learning is, as far as I am aware, novel. Consequently, so is both the approach and the baselines it is compared against.\n\nSignificance\nAs ML practitioners try their hand at more and more complex problems, this approach will become more and more relevant. \nFurther, since this paper is the first to define the one-of-many problem, sets out to define the general framework, and defines reasonable baseline, it is very relevant.\nThe effort made to link the problem of interest with existing other problems mean that it's easier for readers to draw parallels, and helps bolster the paper's significance. For instance, the experimental results tend to show that naively using multiple possible solutions is worse than ignoring these data points. This is in direct contradiction with the general consensus for tasks such as machine translation, where multi-solution datasets are not available, but are longed for.\n\nClarity\nOverall, the paper is well-written and easy to follow. A couple of things might be made clearer, though, including:\n- the description of the pretraining regimen, which is a bit convoluted. It would probably help to refer to the internal M for the selection module as a target network, which it seems to be.\n- the description of the reward for the selection module is a bit complicated too, and the the fact that solutions can be split into r components could be reminded here.\nIt would also be helpful to give more insight into why this reward was chosen (I imagine this partial-reward makes it easier to 'see' some reward than a reward for exact matching, but I'm speculating here), and what the consequences of this choice are (aside from improved performance). Does the selection module opt for the 'easiest' targets to predict? Do the targets chance as training goes along? Could the selection module be trained at a meta-level rather than at the transition-level?\n\n\nOverall, this is a nicely-written paper offering a novel approach to a significant problem, and showcasing its performance improvements. It would make a nice addition to this year's ICLR.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are enthusiastic about this work, and the few comments that they had were appropriately addressed by the reviewers.
Decision: Accept (Poster)