Guided Bottom-Up Interactive Constraint Acquisition

• URL: http://arxiv.org/abs/2307.06126v1
• Date: Wed, 12 Jul 2023 12:25:37 GMT
• Title: Guided Bottom-Up Interactive Constraint Acquisition
• Authors: Dimos Tsouros, Senne Berden, Tias Guns
• Abstract summary: Constraint Acquisition (CA) systems can be used to assist in the modeling of constraint satisfaction problems. Current interactive CA algorithms suffer from at least two major bottlenecks. We present two novel methods that improve the efficiency of CA.
• Score: 10.552990258277434
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constraint Acquisition (CA) systems can be used to assist in the modeling of constraint satisfaction problems. In (inter)active CA, the system is given a set of candidate constraints and posts queries to the user with the goal of finding the right constraints among the candidates. Current interactive CA algorithms suffer from at least two major bottlenecks. First, in order to converge, they require a large number of queries to be asked to the user. Second, they cannot handle large sets of candidate constraints, since these lead to large waiting times for the user. For this reason, the user must have fairly precise knowledge about what constraints the system should consider. In this paper, we alleviate these bottlenecks by presenting two novel methods that improve the efficiency of CA. First, we introduce a bottom-up approach named GrowAcq that reduces the maximum waiting time for the user and allows the system to handle much larger sets of candidate constraints. It also reduces the total number of queries for problems in which the target constraint network is not sparse. Second, we propose a probability-based method to guide query generation and show that it can significantly reduce the number of queries required to converge. We also propose a new technique that allows the use of openly accessible CP solvers in query generation, removing the dependency of existing methods on less well-maintained custom solvers that are not publicly available. Experimental results show that our proposed methods outperform state-of-the-art CA methods, reducing the number of queries by up to 60%. Our methods work well even in cases where the set of candidate constraints is 50 times larger than the ones commonly used in the literature.

Related papers

• Improved Diversity-Promoting Collaborative Metric Learning for Recommendation [127.08043409083687]
  Collaborative Metric Learning (CML) has recently emerged as a popular method in recommendation systems. This paper focuses on a challenging scenario where a user has multiple categories of interests. We propose a novel method called textitDiversity-Promoting Collaborative Metric Learning (DPCML)
  arXiv  Detail & Related papers  (2024-09-02T07:44:48Z)
• On Speeding Up Language Model Evaluation [48.51924035873411]
  Development of prompt-based methods with Large Language Models (LLMs) requires making numerous decisions. We propose a novel method to address this challenge. We show that it can identify the top-performing method using only 5-15% of the typically needed resources.
  arXiv  Detail & Related papers  (2024-07-08T17:48:42Z)
• Learning to Learn in Interactive Constraint Acquisition [7.741303298648302]
  In Constraint Acquisition (CA), the goal is to assist the user by automatically learning the model. In (inter)active CA, this is done by interactively posting queries to the user. We propose to use probabilistic classification models to guide interactive CA to generate more promising queries.
  arXiv  Detail & Related papers  (2023-12-17T19:12:33Z)
• SQLNet: Scale-Modulated Query and Localization Network for Few-Shot Class-Agnostic Counting [71.38754976584009]
  The class-agnostic counting (CAC) task has recently been proposed to solve the problem of counting all objects of an arbitrary class with several exemplars given in the input image. We propose a novel localization-based CAC approach, termed Scale-modulated Query and Localization Network (Net) It fully explores the scales of exemplars in both the query and localization stages and achieves effective counting by accurately locating each object and predicting its approximate size.
  arXiv  Detail & Related papers  (2023-11-16T16:50:56Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  We consider the example-scarce regime, where each user has only a few examples, and obtain the following results. For approximate-DP, we give a generic transformation of any item-level DP algorithm to a user-level DP algorithm. We present a simple technique for adapting the exponential mechanism [McSherry, Talwar FOCS 2007] to the user-level setting.
  arXiv  Detail & Related papers  (2023-09-21T21:51:55Z)
• Logic-Based Benders Decomposition in Answer Set Programming for Chronic Outpatients Scheduling [2.370481325034443]
  In Answer Set Programming (ASP) the user can define declaratively a problem and solve it with efficient solvers. In other research areas, Logic-Based Benders Decomposition (LBBD) proved effective. In this paper, we apply for the first time LBBD to ASP, exploiting an application in health care as case study.
  arXiv  Detail & Related papers  (2023-05-19T19:34:47Z)
• The Minority Matters: A Diversity-Promoting Collaborative Metric Learning Algorithm [154.47590401735323]
  Collaborative Metric Learning (CML) has recently emerged as a popular method in recommendation systems. This paper focuses on a challenging scenario where a user has multiple categories of interests. We propose a novel method called textitDiversity-Promoting Collaborative Metric Learning (DPCML)
  arXiv  Detail & Related papers  (2022-09-30T08:02:18Z)
• Solve Optimization Problems with Unknown Constraint Networks [13.896724650508089]
  We propose a method to solve optimization problems with known objective function and unknown constraint network. It uses an active constraint acquisition algorithm which learns the unknown constraints and computes boundaries for the optimal solution.
  arXiv  Detail & Related papers  (2021-11-23T13:39:41Z)
• Efficient Multiple Constraint Acquisition [1.3706331473063877]
  Constraint acquisition systems such as QuAcq and MultiAcq can assist non-expert users to model their problems as constraint networks. We present a technique that boosts the performance of constraint acquisition by reducing the number of queries significantly. We then turn our attention to query generation which is a significant but rather overlooked part of the acquisition process.
  arXiv  Detail & Related papers  (2021-09-13T12:42:16Z)
• Partial Queries for Constraint Acquisition [40.280429279882]
  We learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QUACQ, that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example.
  arXiv  Detail & Related papers  (2020-03-14T14:43:45Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

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.