Towards Establishing Guaranteed Error for Learned Database Operations

• URL: http://arxiv.org/abs/2411.06243v1
• Date: Sat, 09 Nov 2024 17:53:18 GMT
• Title: Towards Establishing Guaranteed Error for Learned Database Operations
• Authors: Sepanta Zeighami, Cyrus Shahabi,
• Abstract summary: We present the first known lower bounds on the model size required to achieve the desired accuracy for key database operations. Our results bound the required model size for given average and worst-case errors in performing database operations. Our established guarantees pave the way for the broader adoption and integration of learned models into real-world systems.
• Score: 5.14420675727793
• License:
• Abstract: Machine learning models have demonstrated substantial performance enhancements over non-learned alternatives in various fundamental data management operations, including indexing (locating items in an array), cardinality estimation (estimating the number of matching records in a database), and range-sum estimation (estimating aggregate attribute values for query-matched records). However, real-world systems frequently favor less efficient non-learned methods due to their ability to offer (worst-case) error guarantees - an aspect where learned approaches often fall short. The primary objective of these guarantees is to ensure system reliability, ensuring that the chosen approach consistently delivers the desired level of accuracy across all databases. In this paper, we embark on the first theoretical study of such guarantees for learned methods, presenting the necessary conditions for such guarantees to hold when using machine learning to perform indexing, cardinality estimation and range-sum estimation. Specifically, we present the first known lower bounds on the model size required to achieve the desired accuracy for these three key database operations. Our results bound the required model size for given average and worst-case errors in performing database operations, serving as the first theoretical guidelines governing how model size must change based on data size to be able to guarantee an accuracy level. More broadly, our established guarantees pave the way for the broader adoption and integration of learned models into real-world systems.

Related papers

• Privacy-Preserving Model and Preprocessing Verification for Machine Learning [9.4033740844828]
  This paper presents a framework for privacy-preserving verification of machine learning models, focusing on models trained on sensitive data. It addresses two key tasks: binary classification, to verify if a target model was trained correctly by applying the appropriate preprocessing steps, and multi-class classification, to identify specific preprocessing errors. Results indicate that although verification accuracy varies across datasets and noise levels, the framework provides effective detection of preprocessing errors, strong privacy guarantees, and practical applicability for safeguarding sensitive data.
  arXiv  Detail & Related papers  (2025-01-14T16:21:54Z)
• Developing a Dataset-Adaptive, Normalized Metric for Machine Learning Model Assessment: Integrating Size, Complexity, and Class Imbalance [0.0]
  Traditional metrics like accuracy, F1-score, and precision are frequently used to evaluate machine learning models. A dataset-adaptive, normalized metric that incorporates dataset characteristics like size, feature dimensionality, class imbalance, and signal-to-noise ratio is presented.
  arXiv  Detail & Related papers  (2024-12-10T07:10:00Z)
• Combining Retrieval and Classification: Balancing Efficiency and Accuracy in Duplicate Bug Report Detection [2.522333180723133]
  We propose a transformer-based system designed to strike a balance between time efficiency and accuracy performance. Our system maintains accuracy comparable to a classification model, significantly outperforming it in time efficiency and only slightly behind a retrieval model in time.
  arXiv  Detail & Related papers  (2024-04-23T10:06:19Z)
• Exploring validation metrics for offline model-based optimisation with diffusion models [50.404829846182764]
  In model-based optimisation (MBO) we are interested in using machine learning to design candidates that maximise some measure of reward with respect to a black box function called the (ground truth) oracle. While an approximation to the ground oracle can be trained and used in place of it during model validation to measure the mean reward over generated candidates, the evaluation is approximate and vulnerable to adversarial examples. This is encapsulated under our proposed evaluation framework which is also designed to measure extrapolation.
  arXiv  Detail & Related papers  (2022-11-19T16:57:37Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  Real-world machine learning deployments are characterized by mismatches between the source (training) and target (test) distributions. In this work, we investigate methods for predicting the target domain accuracy using only labeled source data and unlabeled target data. We propose Average Thresholded Confidence (ATC), a practical method that learns a threshold on the model's confidence, predicting accuracy as the fraction of unlabeled examples.
  arXiv  Detail & Related papers  (2022-01-11T23:01:12Z)
• Evaluating State-of-the-Art Classification Models Against Bayes Optimality [106.50867011164584]
  We show that we can compute the exact Bayes error of generative models learned using normalizing flows. We use our approach to conduct a thorough investigation of state-of-the-art classification models.
  arXiv  Detail & Related papers  (2021-06-07T06:21:20Z)
• ALT-MAS: A Data-Efficient Framework for Active Testing of Machine Learning Algorithms [58.684954492439424]
  We propose a novel framework to efficiently test a machine learning model using only a small amount of labeled test data. The idea is to estimate the metrics of interest for a model-under-test using Bayesian neural network (BNN)
  arXiv  Detail & Related papers  (2021-04-11T12:14:04Z)
• Confidence Estimation via Auxiliary Models [47.08749569008467]
  We introduce a novel target criterion for model confidence, namely the true class probability ( TCP) We show that TCP offers better properties for confidence estimation than standard maximum class probability (MCP)
  arXiv  Detail & Related papers  (2020-12-11T17:21:12Z)
• Meta-Learned Confidence for Few-shot Learning [60.6086305523402]
  A popular transductive inference technique for few-shot metric-based approaches, is to update the prototype of each class with the mean of the most confident query examples. We propose to meta-learn the confidence for each query sample, to assign optimal weights to unlabeled queries. We validate our few-shot learning model with meta-learned confidence on four benchmark datasets.
  arXiv  Detail & Related papers  (2020-02-27T10:22:17Z)

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.