Mining Potentially Explanatory Patterns via Partial Solutions

• URL: http://arxiv.org/abs/2404.04388v2
• Date: Tue, 9 Jul 2024 12:36:12 GMT
• Title: Mining Potentially Explanatory Patterns via Partial Solutions
• Authors: GianCarlo Catalano, Alexander E. I. Brownlee, David Cairns, John McCall, Russell Ainslie,
• Abstract summary: We present an algorithm that assembles a collection of Partial Solutions chosen to strike a balance between high fitness, simplicity and atomicity. Experiments with standard benchmarks show that the proposed algorithm is able to find Partial Solutions which improve explainability at reasonable computational cost without affecting search performance.
• Score: 39.58317527488534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Genetic Algorithms have established their capability for solving many complex optimization problems. Even as good solutions are produced, the user's understanding of a problem is not necessarily improved, which can lead to a lack of confidence in the results. To mitigate this issue, explainability aims to give insight to the user by presenting them with the knowledge obtained by the algorithm. In this paper we introduce Partial Solutions in order to improve the explainability of solutions to combinatorial optimization problems. Partial Solutions represent beneficial traits found by analyzing a population, and are presented to the user for explainability, but also provide an explicit model from which new solutions can be generated. We present an algorithm that assembles a collection of Partial Solutions chosen to strike a balance between high fitness, simplicity and atomicity. Experiments with standard benchmarks show that the proposed algorithm is able to find Partial Solutions which improve explainability at reasonable computational cost without affecting search performance.

Related papers

• EXALT: EXplainable ALgorithmic Tools for Optimization Problems [2.1184929769291294]
  This project proposes a novel approach to developing explainable algorithms by starting with optimization problems. The developed software library enriches basic algorithms with human-understandable explanations through four key methodologies.
  arXiv  Detail & Related papers  (2025-02-28T10:28:20Z)
• Coherent Local Explanations for Mathematical Optimization [0.0]
  We introduce Coherent Local Explanations for Mathematical Optimization (CLEMO) CLEMO provides explanations for multiple components of optimization models, the objective value and decision variables, which are coherent with the underlying model structure. Our sampling-based procedure can provide explanations for the behavior of exact and exact solution algorithms.
  arXiv  Detail & Related papers  (2025-02-07T11:18:04Z)
• Un-evaluated Solutions May Be Valuable in Expensive Optimization [5.6787965501364335]
  We propose a strategic approach that incorporates high-quality, un-evaluated solutions predicted by surrogate models during the selection phase. This approach aims to improve the distribution of evaluated solutions, thereby generating a superior next generation of solutions.
  arXiv  Detail & Related papers  (2024-12-05T04:06:30Z)
• Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems [0.0]
  Graph Neural Networks (GNNs) show promise for researchers in solving Combinatorial optimization (CO) problems. This study investigates the effectiveness of GNNs in solving the maximum independent set (MIS) problem.
  arXiv  Detail & Related papers  (2024-11-06T09:12:31Z)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• Feature-Based Interpretable Surrogates for Optimization [0.8437187555622164]
  In this work, we investigate how we can use more general optimization rules to increase interpretability. The proposed rules do not map to a concrete solution but to a set of solutions characterized by common features. In particular, we demonstrate the improvement in solution quality that our approach offers compared to existing interpretable surrogates for optimization.
  arXiv  Detail & Related papers  (2024-09-03T13:12:49Z)
• Large Language Model-Aided Evolutionary Search for Constrained Multiobjective Optimization [15.476478159958416]
  We employ a large language model (LLM) to enhance evolutionary search for solving constrained multi-objective optimization problems. Our aim is to speed up the convergence of the evolutionary population.
  arXiv  Detail & Related papers  (2024-05-09T13:44:04Z)
• Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and Optimization [59.386153202037086]
  Predict-Then- framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This approach can be inefficient and requires handcrafted, problem-specific rules for backpropagation through the optimization step. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by predictive models.
  arXiv  Detail & Related papers  (2023-11-22T01:32:06Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• A Mutual Information Maximization Approach for the Spurious Solution Problem in Weakly Supervised Question Answering [60.768146126094955]
  Weakly supervised question answering usually has only the final answers as supervision signals. There may exist many spurious solutions that coincidentally derive the correct answer, but training on such solutions can hurt model performance. We propose to explicitly exploit such semantic correlations by maximizing the mutual information between question-answer pairs and predicted solutions.
  arXiv  Detail & Related papers  (2021-06-14T05:47:41Z)
• PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective Optimization Problems [0.0]
  The proposed algorithm is based on solving a set of surrogate problems defined by models of the real one. Our algorithm also performs a meta-search for optimal surrogate models and navigation strategies for the optimization landscape.
  arXiv  Detail & Related papers  (2021-03-19T11:18:03Z)

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.