Scalable Sampling for High Utility Patterns

• URL: http://arxiv.org/abs/2410.22964v1
• Date: Wed, 30 Oct 2024 12:22:54 GMT
• Title: Scalable Sampling for High Utility Patterns
• Authors: Lamine Diop, Marc Plantevit,
• Abstract summary: We propose a novel high utility pattern sampling algorithm and its on-disk version for large quantitative databases. Our approach ensures both the interactivity required for user-centered methods and strong statistical guarantees through random sampling. To demonstrate the interest of our approach, we present a compelling use case involving archaeological knowledge graph sub-profiles discovery.
• Score: 1.2154569665167423
• License:
• Abstract: Discovering valuable insights from data through meaningful associations is a crucial task. However, it becomes challenging when trying to identify representative patterns in quantitative databases, especially with large datasets, as enumeration-based strategies struggle due to the vast search space involved. To tackle this challenge, output space sampling methods have emerged as a promising solution thanks to its ability to discover valuable patterns with reduced computational overhead. However, existing sampling methods often encounter limitations when dealing with large quantitative database, resulting in scalability-related challenges. In this work, we propose a novel high utility pattern sampling algorithm and its on-disk version both designed for large quantitative databases based on two original theorems. Our approach ensures both the interactivity required for user-centered methods and strong statistical guarantees through random sampling. Thanks to our method, users can instantly discover relevant and representative utility pattern, facilitating efficient exploration of the database within seconds. To demonstrate the interest of our approach, we present a compelling use case involving archaeological knowledge graph sub-profiles discovery. Experiments on semantic and none-semantic quantitative databases show that our approach outperforms the state-of-the art methods.

Related papers

• Adaptive teachers for amortized samplers [76.88721198565861]
  Amortized inference is the task of training a parametric model, such as a neural network, to approximate a distribution with a given unnormalized density where exact sampling is intractable. Off-policy RL training facilitates the discovery of diverse, high-reward candidates, but existing methods still face challenges in efficient exploration. We propose an adaptive training distribution (the Teacher) to guide the training of the primary amortized sampler (the Student) by prioritizing high-loss regions.
  arXiv  Detail & Related papers  (2024-10-02T11:33:13Z)
• DISCOVER: A Data-driven Interactive System for Comprehensive Observation, Visualization, and ExploRation of Human Behaviour [6.716560115378451]
  We introduce a modular, flexible, yet user-friendly software framework specifically developed to streamline computational-driven data exploration for human behavior analysis. Our primary objective is to democratize access to advanced computational methodologies, thereby enabling researchers across disciplines to engage in detailed behavioral analysis without the need for extensive technical proficiency.
  arXiv  Detail & Related papers  (2024-07-18T11:28:52Z)
• DiscoveryBench: Towards Data-Driven Discovery with Large Language Models [50.36636396660163]
  We present DiscoveryBench, the first comprehensive benchmark that formalizes the multi-step process of data-driven discovery. Our benchmark contains 264 tasks collected across 6 diverse domains, such as sociology and engineering. Our benchmark, thus, illustrates the challenges in autonomous data-driven discovery and serves as a valuable resource for the community to make progress.
  arXiv  Detail & Related papers  (2024-07-01T18:58:22Z)
• Model-Free Active Exploration in Reinforcement Learning [53.786439742572995]
  We study the problem of exploration in Reinforcement Learning and present a novel model-free solution. Our strategy is able to identify efficient policies faster than state-of-the-art exploration approaches.
  arXiv  Detail & Related papers  (2024-06-30T19:00:49Z)
• The Battleship Approach to the Low Resource Entity Matching Problem [0.0]
  We propose a new active learning approach for entity matching problems. We focus on a selection mechanism that exploits unique properties of entity matching. An experimental analysis shows that the proposed algorithm outperforms state-of-the-art active learning solutions to low resource entity matching.
  arXiv  Detail & Related papers  (2023-11-27T10:18:17Z)
• On the Universal Adversarial Perturbations for Efficient Data-free Adversarial Detection [55.73320979733527]
  We propose a data-agnostic adversarial detection framework, which induces different responses between normal and adversarial samples to UAPs. Experimental results show that our method achieves competitive detection performance on various text classification tasks.
  arXiv  Detail & Related papers  (2023-06-27T02:54:07Z)
• Actively Discovering New Slots for Task-oriented Conversation [19.815466126158785]
  We propose a general new slot task in an information extraction fashion to realize human-in-the-loop learning. We leverage existing language tools to extract value candidates where the corresponding labels are leveraged as weak supervision signals. We conduct extensive experiments on several public datasets and compare with a bunch of competitive baselines to demonstrate our method.
  arXiv  Detail & Related papers  (2023-05-06T13:33:33Z)
• Towards Sequence Utility Maximization under Utility Occupancy Measure [53.234101208024335]
  In the database, although utility is a flexible criterion for each pattern, it is a more absolute criterion due to neglect of utility sharing. We first define utility occupancy on sequence data and raise the problem of High Utility-Occupancy Sequential Pattern Mining. An algorithm called Sequence Utility Maximization with Utility occupancy measure (SUMU) is proposed.
  arXiv  Detail & Related papers  (2022-12-20T17:28:53Z)
• GAN-based Tabular Data Generator for Constructing Synopsis in Approximate Query Processing: Challenges and Solutions [0.0]
  Approximate Query Processing (AQP) is a technique for providing approximate answers to aggregate queries based on a summary of the data (synopsis) This study explores the novel utilization of Generative Adversarial Networks (GANs) in the generation of tabular data that can be employed in AQP for synopsis construction. Our findings demonstrate that advanced GAN variations exhibit a promising capacity to generate high-fidelity synopses, potentially transforming the efficiency and effectiveness of AQP in data-driven systems.
  arXiv  Detail & Related papers  (2022-12-18T05:11:04Z)
• Cluster-level pseudo-labelling for source-free cross-domain facial expression recognition [94.56304526014875]
  We propose the first Source-Free Unsupervised Domain Adaptation (SFUDA) method for Facial Expression Recognition (FER) Our method exploits self-supervised pretraining to learn good feature representations from the target data. We validate the effectiveness of our method in four adaptation setups, proving that it consistently outperforms existing SFUDA methods when applied to FER.
  arXiv  Detail & Related papers  (2022-10-11T08:24:50Z)
• Batch Active Learning at Scale [39.26441165274027]
  Batch active learning, which adaptively issues batched queries to a labeling oracle, is a common approach for addressing this problem. In this work, we analyze an efficient active learning algorithm, which focuses on the large batch setting. We show that our sampling method, which combines notions of uncertainty and diversity, easily scales to batch sizes (100K-1M) several orders of magnitude larger than used in previous studies.
  arXiv  Detail & Related papers  (2021-07-29T18:14:05Z)

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.