Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces

• URL: http://arxiv.org/abs/2008.11990v2
• Date: Sun, 4 Apr 2021 15:36:05 GMT
• Title: Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces
• Authors: Yatin Nandwani, Deepanshu Jindal, Mausam and Parag Singla
• Abstract summary: We argue that being oblivious to the presence of multiple solutions can severely hamper their training ability. We present a generic learning framework that adapts an existing prediction network for an RL problem to handle solution multiplicity.
• Score: 20.101005623256626
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Towards a Generic Representation of Combinatorial Problems for Learning-Based Approaches [2.2526069385327316]
  In recent years, there has been a growing interest in using learning-based approaches for solving problems. The challenge lies in encoding the targeted problems into a structure compatible with the learning algorithm. Many existing works have proposed problem-specific representations, often in the form of a graph, to leverage the advantages of textitgraph neural networks This paper advocates for a fully generic representation of problems for learning-based approaches.
  arXiv  Detail & Related papers  (2024-03-09T22:28:46Z)
• PMGDA: A Preference-based Multiple Gradient Descent Algorithm [12.600588000788214]
  It is desirable in many multi-objective machine learning applications, such as multi-task learning, to find a solution that fits a given preference of a decision maker. This paper proposes a novel predict-and-correct framework for locating a solution that fits the preference of a decision maker.
  arXiv  Detail & Related papers  (2024-02-14T11:27:31Z)
• OFA$^2$: A Multi-Objective Perspective for the Once-for-All Neural Architecture Search [79.36688444492405]
  Once-for-All (OFA) is a Neural Architecture Search (NAS) framework designed to address the problem of searching efficient architectures for devices with different resources constraints. We aim to give one step further in the search for efficiency by explicitly conceiving the search stage as a multi-objective optimization problem.
  arXiv  Detail & Related papers  (2023-03-23T21:30:29Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  We propose L2Dive to learn specific diving structurals with graph neural networks. We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions.
  arXiv  Detail & Related papers  (2023-01-24T12:01:45Z)
• AMS-Net: Adaptive Multiscale Sparse Neural Network with Interpretable Basis Expansion for Multiphase Flow Problems [8.991619150027267]
  We propose an adaptive sparse learning algorithm that can be applied to learn the physical processes and obtain a sparse representation of the solution given a large snapshot space. The information of the basis functions are incorporated in the loss function, which minimizes the differences between the downscaled reduced order solutions and reference solutions at multiple time steps. More numerical tests are performed on two-phase multiscale flow problems to show the capability and interpretability of the proposed method on complicated applications.
  arXiv  Detail & Related papers  (2022-07-24T13:12:43Z)
• Improved Training of Physics-Informed Neural Networks with Model Ensembles [81.38804205212425]
  We propose to expand the solution interval gradually to make the PINN converge to the correct solution. All ensemble members converge to the same solution in the vicinity of observed data. We show experimentally that the proposed method can improve the accuracy of the found solution.
  arXiv  Detail & Related papers  (2022-04-11T14:05:34Z)
• What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
  We present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. We also conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. We show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values.
  arXiv  Detail & Related papers  (2022-01-25T17:37:34Z)
• Discovering Diverse Solutions in Deep Reinforcement Learning [84.45686627019408]
  Reinforcement learning algorithms are typically limited to learning a single solution of a specified task. We propose an RL method that can learn infinitely many solutions by training a policy conditioned on a continuous or discrete low-dimensional latent variable.
  arXiv  Detail & Related papers  (2021-03-12T04:54:31Z)
• Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
  Previous neural solvers of math word problems (MWPs) are learned with full supervision and fail to generate diverse solutions. We introduce a textitweakly-supervised paradigm for learning MWPs. Our method only requires the annotations of the final answers and can generate various solutions for a single problem.
  arXiv  Detail & Related papers  (2020-12-19T03:10:21Z)
• Pareto Multi-Task Learning [53.90732663046125]
  Multi-task learning is a powerful method for solving multiple correlated tasks simultaneously. It is often impossible to find one single solution to optimize all the tasks, since different tasks might conflict with each other. Recently, a novel method is proposed to find one single Pareto optimal solution with good trade-off among different tasks by casting multi-task learning as multiobjective optimization.
  arXiv  Detail & Related papers  (2019-12-30T08:58:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.