Pattern based learning and optimisation through pricing for bin packing problem

• URL: http://arxiv.org/abs/2409.04456v1
• Date: Tue, 27 Aug 2024 17:03:48 GMT
• Title: Pattern based learning and optimisation through pricing for bin packing problem
• Authors: Huayan Zhang, Ruibin Bai, Tie-Yan Liu, Jiawei Li, Bingchen Lin, Jianfeng Ren,
• Abstract summary: We argue that when problem conditions such as the distributions of random variables change, the patterns that performed well in previous circumstances may become less effective. We propose a novel scheme to efficiently identify patterns and dynamically quantify their values for each specific condition. Our method quantifies the value of patterns based on their ability to satisfy constraints and their effects on the objective value.
• Score: 50.83768979636913
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As a popular form of knowledge and experience, patterns and their identification have been critical tasks in most data mining applications. However, as far as we are aware, no study has systematically examined the dynamics of pattern values and their reuse under varying conditions. We argue that when problem conditions such as the distributions of random variables change, the patterns that performed well in previous circumstances may become less effective and adoption of these patterns would result in sub-optimal solutions. In response, we make a connection between data mining and the duality theory in operations research and propose a novel scheme to efficiently identify patterns and dynamically quantify their values for each specific condition. Our method quantifies the value of patterns based on their ability to satisfy stochastic constraints and their effects on the objective value, allowing high-quality patterns and their combinations to be detected. We use the online bin packing problem to evaluate the effectiveness of the proposed scheme and illustrate the online packing procedure with the guidance of patterns that address the inherent uncertainty of the problem. Results show that the proposed algorithm significantly outperforms the state-of-the-art methods. We also analysed in detail the distinctive features of the proposed methods that lead to performance improvement and the special cases where our method can be further improved.

Related papers

• Provably Better Explanations with Optimized Aggregation of Feature Attributions [36.22433695108499]
  Using feature attributions for post-hoc explanations is a common practice to understand and verify the predictions of opaque machine learning models. We propose a novel approach to derive optimal convex combinations of feature attributions that yield provable improvements of desired quality criteria.
  arXiv  Detail & Related papers  (2024-06-07T17:03:43Z)
• Globally-Optimal Greedy Experiment Selection for Active Sequential Estimation [1.1530723302736279]
  We study the problem of active sequential estimation, which involves adaptively selecting experiments for sequentially collected data. The goal is to design experiment selection rules for more accurate model estimation. We propose a class of greedy experiment selection methods and provide statistical analysis for the maximum likelihood.
  arXiv  Detail & Related papers  (2024-02-13T17:09:29Z)
• Mining a Minimal Set of Behavioral Patterns using Incremental Evaluation [3.16536213610547]
  Existing approaches to behavioral pattern mining suffer from two limitations. First, they show limited scalability as incremental computation is incorporated only in the generation of pattern candidates. Second, process analysis based on mined patterns shows limited effectiveness due to an overwhelmingly large number of patterns obtained in practical application scenarios.
  arXiv  Detail & Related papers  (2024-02-05T11:41:37Z)
• Consistent Explanations in the Face of Model Indeterminacy via Ensembling [12.661530681518899]
  This work addresses the challenge of providing consistent explanations for predictive models in the presence of model indeterminacy. We introduce ensemble methods to enhance the consistency of the explanations provided in these scenarios. Our findings highlight the importance of considering model indeterminacy when interpreting explanations.
  arXiv  Detail & Related papers  (2023-06-09T18:45:43Z)
• Best-Effort Adaptation [62.00856290846247]
  We present a new theoretical analysis of sample reweighting methods, including bounds holding uniformly over the weights. We show how these bounds can guide the design of learning algorithms that we discuss in detail. We report the results of a series of experiments demonstrating the effectiveness of our best-effort adaptation and domain adaptation algorithms.
  arXiv  Detail & Related papers  (2023-05-10T00:09:07Z)
• Better Understanding Differences in Attribution Methods via Systematic Evaluations [57.35035463793008]
  Post-hoc attribution methods have been proposed to identify image regions most influential to the models' decisions. We propose three novel evaluation schemes to more reliably measure the faithfulness of those methods. We use these evaluation schemes to study strengths and shortcomings of some widely used attribution methods over a wide range of models.
  arXiv  Detail & Related papers  (2023-03-21T14:24:58Z)
• Comparing Ordering Strategies For Process Discovery Using Synthesis Rules [0.5330240017302619]
  Process discovery aims to learn process models from observed behaviors. In this paper, we investigate the effect of different ordering strategies on the discovered models.
  arXiv  Detail & Related papers  (2023-01-04T16:17:52Z)
• Latent Variable Representation for Reinforcement Learning [131.03944557979725]
  It remains unclear theoretically and empirically how latent variable models may facilitate learning, planning, and exploration to improve the sample efficiency of model-based reinforcement learning. We provide a representation view of the latent variable models for state-action value functions, which allows both tractable variational learning algorithm and effective implementation of the optimism/pessimism principle. In particular, we propose a computationally efficient planning algorithm with UCB exploration by incorporating kernel embeddings of latent variable models.
  arXiv  Detail & Related papers  (2022-12-17T00:26:31Z)
• Characterizing Fairness Over the Set of Good Models Under Selective Labels [69.64662540443162]
  We develop a framework for characterizing predictive fairness properties over the set of models that deliver similar overall performance. We provide tractable algorithms to compute the range of attainable group-level predictive disparities. We extend our framework to address the empirically relevant challenge of selectively labelled data.
  arXiv  Detail & Related papers  (2021-01-02T02:11:37Z)
• Model-Augmented Actor-Critic: Backpropagating through Paths [81.86992776864729]
  Current model-based reinforcement learning approaches use the model simply as a learned black-box simulator. We show how to make more effective use of the model by exploiting its differentiability.
  arXiv  Detail & Related papers  (2020-05-16T19:18:10Z)

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.