Method curates cost-effective, high-quality datasets using AI models.
problem Costly manual labeling of datasets.
method Probably Approximately Correct Labels (PACL) method.
result Curates high-quality datasets with low overall labeling error.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “probably approximately correct labels”
Proposes PA-DSL for correcting noisy human labels in automated data labeling.
problem Noisy human labels in automated data labeling.
method Uses adjudicated cases to correct noisy human labels and debias analyses.
result Maintains nominal coverage and reduces RMSE by 10-17% relative to using only adjudicated labels.
PPI uses predictions and weighting to infer from partially labeled data.
problem Valid inference with partially labeled data.
method Combines model-based predictions with bias correction from labeled data, using Horvitz-Thompson and Hájek corrections.
result IPW-adjusted PPI with estimated propensities performs similarly to known-probability case.
New framework learns from partial feedback in multi-label tasks.
problem Learning from one-sided feedback in multi-label tasks.
method Probably Approximately Correct (PAC) framework for set functions.
result Achieves optimal sample complexity in realizable case, multiplicative approximation guarantees in agnostic case.
Survey on learning Boolean functions in computational theory.
problem Learning Boolean function classes in computational theory.
method Overview of known results in PAC and related models.
result Discussion of various learning results for Boolean functions.
Label shift refers to the phenomenon where the prior class probability p(y) changes between the training and test distributions, while the conditional probability p(x|y) stays fixed. Label shift arises in settings like medical diagnosis, where a classifier trained to predict disease given symptoms must be adapted to sc…
Classification from Positive and Biased Negative Data with Skewed Labeled Posterior Probabilitystat.ME
New method corrects skewed confidence for PbN classification.
problem Weakly supervised binary classification with biased negative data.
method Corrects skewed confidence in negative data to improve classifier.
result Reduces distortion in posterior probability for PbN classification.
Theorem ensures superior learning outcomes for authorized learners with quantum label encoding.
problem Ensuring data security for authorized learners in machine learning.
method Quantum label encoding and PAC learning framework.
result Authorized learners achieve superior learning outcomes while eavesdroppers do not.
Unified approach for multicalibration in weakly supervised learning.
problem Existing multicalibration methods require clean input-label pairs, which are unavailable in weakly supervised learning.
method Developed estimators and post-hoc correction methods for multicalibration under weak supervision.
result Unified framework for estimating and correcting multicalibration under weak supervision with finite-sample guarantees.
SJS model predicts label shifts in multinomial datasets.
problem Predicting label shifts in multinomial datasets.
method Sparse joint shift model for dataset shift.
result Valid predictions and class prior probabilities estimates.
We present a theoretically grounded approach to train deep neural networks, including recurrent networks, subject to class-dependent label noise. We propose two procedures for loss correction that are agnostic to both application domain and network architecture. They simply amount to at most a matrix inversion and mult…
ECBMs unify concept-based interpretations in deep learning models.
problem Suboptimal final accuracy and lack of concept interaction and conditional dependencies.
method ECBMs use a set of neural networks to define joint energy, enabling concept correction and conditional dependency quantification.
result ECBMs achieve higher accuracy and richer concept interpretations compared to state-of-the-art methods.
We consider the problem of Probably Approximate Correct (PAC) learning of a binary classifier from noisy labeled examples acquired from multiple annotators (each characterized by a respective classification noise rate). First, we consider the complete information scenario, where the learner knows the noise rates of all…
We introduce the SaaS Algorithm for semi-supervised learning, which uses learning speed during stochastic gradient descent in a deep neural network to measure the quality of an iterative estimate of the posterior probability of unknown labels. Training speed in supervised learning correlates strongly with the percentag…
Leveraging weak or noisy supervision for building effective machine learning models has long been an important research problem. Its importance has further increased recently due to the growing need for large-scale datasets to train deep learning models. Weak or noisy supervision could originate from multiple sources i…
PACC Discovery improves causal inference from limited data.
problem Inferring causal relationships from finite data.
method Extends PAC learning principles to causal inference.
result Theoretical guarantees for various causal methods.
Study computable multiclass learning within PAC framework.
problem Computable multiclass learnability in finite label space.
method Proposed computable version of Natarajan dimension and generalized to distinguishers.
result Characterizes CPAC learnability for certain dimensions and embeddings.
In learning with noisy labels, for every instance, its label can randomly walk to other classes following a transition distribution which is named a noise model. Well-studied noise models are all instance-independent, namely, the transition depends only on the original label but not the instance itself, and thus they a…
Submodular function maximization finds application in a variety of real-world decision-making problems. However, most existing methods, based on greedy maximization, assume it is computationally feasible to evaluate F, the function being maximized. Unfortunately, in many realistic settings F is too expensive to evaluat…
Improved speech recognition model with better performance.
problem Speech recognition accuracy on Librispeech.
method Integrates an external language model with an internal LM correction.
result Over 14% relative improvement in performance.
Study approximates operators on labelled conditional distributions for non-exchangeable systems.
problem Approximating operators on constrained probability measures for non-exchangeable systems.
method Combines cylindrical approximations and DeepONet-type neural architecture for finite-dimensional representations.
result Establishes a universal approximation theorem for continuous operators on .
Anytime-valid confirmation of label-shift corrections
problem Small-batch scientific deployments with scarce labeled outcomes
method Conditional e-value and martingale-based rule
result Nonnegative martingale and anytime-valid confirmation rule
Efficiently learns from partial labels using variational inference.
problem Learning from noisy and ambiguous partial labels in crowdsourcing.
method Amortized variational inference for probabilistic posterior approximation.
result Achieves state-of-the-art performance in accuracy and efficiency.
The paper establishes risk bounds for PU learning with label noise.
problem Finding a classifier in PU learning with label noise.
method Establishes risk bounds under the assumption of label selection randomness.
result Proves that the upper bound on minimax risk is almost optimal.
Classifier chains are popular and effective method to tackle a multi-label classification problem. The aim of this paper is to study the asymptotic properties of the chain model in which the conditional probabilities are of the logistic form. In particular we find conditions on the number of labels and the distribution…
Proposes a progressive label correction method for feature-dependent label noise.
problem Real-world large-scale datasets often suffer from heterogeneous, feature-dependent label noise.
method A progressive label correction algorithm that iteratively refines the model.
result A classifier trained with this strategy converges to be consistent with the Bayes classifier for various noise patterns.
Distillation improves simple models by approximating complex labels.
problem Why does distillation improve simple models?
method Statistical perspective on distillation, connecting to extreme multiclass retrieval.
result Distillation helps by approximating underlying class-probabilities, reducing bias and variance.
Label smoothing improves model performance even with noisy labels.
problem Mitigating label noise in deep learning models.
method Examined label smoothing as a technique to cope with label noise and compared it to loss-correction methods.
result Label smoothing is competitive with loss-correction techniques under label noise and beneficial for distillation from noisy data.
The paper explores how machine learning models can be learnable despite label shifts.
problem Learnability of binary classification models in the presence of label shifts.
method Developed a performative empirical risk function that is an unbiased estimate of the true risk on the shifted distribution.
result PAC-learnable hypothesis spaces remain PAC-learnable for performative scenarios.
In display advertising, predicting the conversion rate, that is, the probability that a user takes a predefined action on an advertiser's website, such as purchasing goods is fundamental in estimating the value of displaying the advertisement. However, there is a relatively long time delay between a click and its resul…
Proposes a method to evaluate classifiers with missing labels using multiple imputation.
problem Missing labels during model evaluation can introduce bias, especially in Missing Not At Random (MNAR) data.
method Develops a multiple imputation technique to estimate and provide predictive distributions for metrics like precision, recall, and ROC-AUC.
result The predictive distribution's location and shape are generally correct, even in the MNAR regime.
Logistic regression can handle noisy labels effectively when labels are imperfectly assigned by multiple experts.
problem Label noise in supervised classification due to manual labelling by multiple experts.
method Using approximate posterior probabilities of class membership from multiple experts to train logistic regression models.
result Logistic regression can be robust to label noise when classification difficulty is the only source of errors.
The study analyzes group testing algorithms for identifying defective items with high confidence.
problem Identifying defective items from a population using group testing with high confidence.
method Formulated as a function learning problem using the PAC framework, analyzed three algorithms: column matching, combinatorial basis pursuit, and definite defectives.
result Derived bounds on the number of tests needed for approximate set identification, comparing with existing bounds and simulating performance.
In this work, we addressed the issue of applying a stochastic classifier and a local, fuzzy confusion matrix under the framework of multi-label classification. We proposed a novel solution to the problem of correcting label pairwise ensembles. The main step of the correction procedure is to compute classifier- specific…
Improved multi-class AdaBoost algorithm with stronger weak learnability condition.
problem Multi-class classification problem with at least two labels.
method Recursive ensemble algorithm inspired by SAMME, strengthening weak learnability condition.
result Final hypothesis converges to correct label with probability 1 and generalization error bounds exponentially.
This paper improves deep learning model consistency through ensemble methods.
problem Consistency and correct-consistency issues in deep learning models.
method Formal definition of consistency and correct-consistency, proving ensemble improvement, proposing dynamic snapshot ensemble method.
result Ensemble methods can improve correct-consistency of deep learning models.
New algorithm FLUTE achieves uniform-PAC convergence in RL with linear approx.
problem RL with linear function approximation lacks uniform-PAC guarantees.
method FLUTE algorithm with minimax value function estimator and multi-level partition scheme.
result Uniform-PAC convergence to optimal policy with high probability.
Develops methods to correct bias in AI feedback for more accurate alignment.
problem Systematic bias in AI feedback compared to human labels.
method Two debiased alignment methods: DDPO and DIPO.
result Methods improve alignment efficiency and performance close to human-labeled data.
The paper compares one-hot encoding to Naïve Bayes for categorical variables.
problem Incorrect one-hot encoding affects Naïve Bayes performance.
method Mathematical and experimental analysis of PoB vs. categorical Naïve Bayes.
result Posterior probabilities are usually greater in the PoB case, but agree on the maximum a posteriori class label.
We propose and analyze an alternate approach to off-policy multi-step temporal difference learning, in which off-policy returns are corrected with the current Q-function in terms of rewards, rather than with the target policy in terms of transition probabilities. We prove that such approximate corrections are sufficien…
High-probability sample complexities for policy evaluation with linear function approximationstat.ML
The paper analyzes the sample complexities for policy evaluation with linear function approximation.
problem Policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes.
method Investigates sample complexities for two policy evaluation algorithms: TD and TDC.
result Establishes high-probability sample complexity bounds for policy evaluation algorithms.
We present a formal proof in Lean of probably approximately correct (PAC) learnability of the concept class of decision stumps. This classic result in machine learning theory derives a bound on error probabilities for a simple type of classifier. Though such a proof appears simple on paper, analytic and measure-theoret…
Gradient descent learns a neuron in noisy data.
problem Learning a single neuron with adversarial label noise.
method Gradient descent on the -loss.
result Efficient approximate learners for various distributions and activations.
An Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theorystat.ML
In this paper, the problem of one-bit compressed sensing (OBCS) is formulated as a problem in probably approximately correct (PAC) learning. It is shown that the Vapnik-Chervonenkis (VC-) dimension of the set of half-spaces in generated by -sparse vectors is bounded below by and above by…
Develops a comprehensive theory of corruption in supervised learning.
problem Widespread corruption in data collection affects supervised learning problems.
method Introduces a general theory of corruption using Markov kernels, distinguishing and comparing corruption types.
result Establishes a unified framework for corruption types and develops mitigation strategies.
Efficient algorithm approximates discrete random variables with minimal Kolmogorov distance.
problem Estimating the probability of missing deadlines in series-parallel schedules.
method An efficient algorithm that computes a random variable with minimal Kolmogorov distance to a given discrete random variable.
result The algorithm efficiently approximates the probability of missing deadlines with minimal Kolmogorov distance.
Sequence probability predicts correctness in LLMs, but not for repeated prompts
problem Predicting correctness in large language models
method Quantifying sequence probability and correctness across different levels
result Higher sequence probability often predicts correctness across prompt-answer pairs
The paper improves PCS approximation for ranking and selection under limited simulation budgets.
problem Improving finite sample performance in Ranking and Selection.
method Develops a Bahadur-Rao type expansion for PCS, proposes a novel FCBA policy.
result FCBA policy achieves superior PCS performance compared to traditional methods.