检索结果-内蒙古大学图书馆

Decision-focused evaluation of worst-case distribution shift 24

学校读者我要写书评

暂无评论

Decision-focused evaluation of worst-case distribution shift

Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence

作者： Kevin Ren Yewon Byun Bryan Wilder Statistics and Data Science Dept. Carnegie Mellon University Pittsburgh Pennsylvania Machine Learning Dept. Carnegie Mellon University Pittsburgh Pennsylvania

Recent studies have shown that performance on downstream optimization tasks often diverges from standard accuracy-based losses, highlighting that the loss function of a predictive model should align with the decision task of the downstream optimizer [Wilder et al., 2019, Elmachtoub and Grigas, 2022]. Despite this observation, no work— to our knowledge—has yet examined the impact of this divergence for distribution shift. In this paper, we demonstrate that worst-case distribution shifts identified by traditional average accuracy-based metrics fundamentally differ from those for the downstream decision task at hand. We introduce a novel framework that employs a hierarchical model structure to identify worst-case distribution shifts in predictive resource allocation settings. This task is more difficult than in standard distribution shift settings because of combinatorial interactions, where decisions depend on the joint presence of individuals in the allocation task. We show that the problem can be reformulated as a submodular optimization problem, enabling efficient approximations, to capture shifts both within and across instances of the optimization problem. We apply our solution to real-world datasets in public service settings, providing empirical evidence that worst-case shifts for one metric often significantly diverge from worst-case distributions for other metrics.

关键词：

A Permutation-Free Kernel Independence Test

学校读者我要写书评

暂无评论

Journal of machine learning Research 2023年 24卷

作者： Shekhar, Shubhanshu Kim, Ilmun Ramdas, Aaditya Department of Statistics and Data Science Carnegie Mellon University PittsburghPA15213 United States Department of Statistics and Data Science Department of Applied Statistics Yonsei University Seodaemun-gu Seoul03722 Korea Republic of Department of Statistics and Data Science Machine Learning Department Carnegie Mellon University PittsburghPA15213 United States

In nonparametric independence testing, we observe i.i.d. data {(Xi,Yi)}in=1, where X ∈ X,Y ∈ Y lie in any general spaces, and we wish to test the null that X is independent of Y. Modern test statistics such as the kernel Hilbert–Schmidt Independence Criterion (HSIC) and Distance Covariance (dCov) have intractable null distributions due to the degeneracy of the underlying U-statistics. Hence, in practice, one often resorts to using permutation testing, which provides a nonasymptotic guarantee at the expense of recalculating the quadratic-time statistics (say) a few hundred times. In this paper, we provide a simple but nontrivial modification of HSIC and dCov (called xHSIC and xdCov, pronounced "cross" HSIC/dCov) so that they have a limiting Gaussian distribution under the null, and thus do not require permutations. We show that our new tests, like the originals, are consistent against fixed alternatives, and minimax rate optimal against smooth local alternatives. Numerical simulations demonstrate that compared to the permutation tests, our variants have the same power within a constant factor, giving practitioners a new option for large problems or data-analysis pipelines where computation, not sample size, could be the bottleneck. © 2023 Shubhanshu Shekhar, Ilmun Kim, and Aaditya Ramdas.

关键词： Gaussian distribution

Optimal bounds for p sensitivity sampling via 2 augmentation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Munteanu, Alexander Omlor, Simon Dortmund Data Science Center Faculties of Statistics and Computer Science TU Dortmund University Dortmund Germany Faculty of Statistics and Lamarr Institute for Machine Learning and Artificial Intelligence TU Dortmund University Dortmund Germany

data subsampling is one of the most natural methods to approximate a massively large data set by a small representative proxy. In particular, sensitivity sampling received a lot of attention, which samples points proportional to an individual importance measure called sensitivity. This framework reduces in very general settings the size of data to roughly the VC dimension d times the total sensitivity S while providing strong (1 ± Ε) guarantees on the quality of approximation. The recent work of Woodruff and Yasuda (2023c) improved substantially over the general Õ(Ε−2Sd) bound for the important problem of p subspace embeddings to Õ(Ε−2S2/p) for p ∈ [1, 2]. Their result was subsumed by an earlier Õ(Ε−2Sd1−p/2) bound which was implicitly given in the work of Chen and Derezinski (2021). We show that their result is tight when sampling according to plain p sensitivities. We observe that by augmenting the p sensitivities by 2 sensitivities, we obtain better bounds improving over the aforementioned results to optimal linear Õ(Ε−2(S + d)) = Õ(Ε−2d) sampling complexity for all p ∈ [1, 2]. In particular, this resolves an open question of Woodruff and Yasuda (2023c) in the affirmative for p ∈ [1, 2] and brings sensitivity subsampling into the regime that was previously only known to be possible using Lewis weights (Cohen and Peng, 2015). As an application of our main result, we also obtain an Õ(Ε−2µd) sensitivity sampling bound for logistic regression, where µ is a natural complexity measure for this problem. This improves over the previous Õ(Ε−2µ2d) bound of Mai et al. (2021) which was based on Lewis weights subsampling. Copyright © 2024, The Authors. All rights reserved.

关键词： Importance sampling

Turnstile p leverage score sampling with applications

学校读者我要写书评

暂无评论

arXiv 2024年

The turnstile data stream model offers the most flexible framework where data can be manipulated dynamically, i.e., rows, columns, and even single entries of an input matrix can be added, deleted, or updated multiple times in a data stream. We develop a novel algorithm for sampling rows ai of a matrix A ∈ n×d, proportional to their p norm, when A is presented in a turnstile data stream. Our algorithm not only returns the set of sampled row indexes, it also returns slightly perturbed rows ãi ≈ ai, and approximates their sampling probabilities up to Ε relative error. When combined with preconditioning techniques, our algorithm extends to p leverage score sampling over turnstile data streams. With these properties in place, it allows us to simulate subsampling constructions of coresets for important regression problems to operate over turnstile data streams with very little overhead compared to their respective offline subsampling algorithms. For logistic regression, our framework yields the first algorithm that achieves a (1 + Ε) approximation and works in a turnstile data stream using polynomial sketch/subsample size, improving over O(1) approximations, or exp(1/Ε) sketch size of previous work. We compare experimentally to plain oblivious sketching and plain leverage score sampling algorithms for p and logistic regression. Copyright © 2024, The Authors. All rights reserved.

关键词： Approximation algorithms

Revisiting Optimism and Model Complexity in the Wake of Overparameterized machine learning

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Patil, Pratik Du, Jin-Hong Tibshirani, Ryan J. Department of Statistics University of California Berkeley United States Department of Statistics and Data Science Carnegie Mellon University United States Machine Learning Department Carnegie Mellon University United States

Common practice in modern machine learning involves fitting a large number of parameters relative to the number of observations. These overparameterized models can exhibit surprising generalization behavior, e.g., "double descent" in the prediction error curve when plotted against the raw number of model parameters, or another simplistic notion of complexity. In this paper, we revisit model complexity from first principles, by first reinterpreting and then extending the classical statistical concept of (effective) degrees of freedom. Whereas the classical definition is connected to fixed-X prediction error (in which prediction error is defined by averaging over the same, nonrandom covariate points as those used during training), our extension of degrees of freedom is connected to random-X prediction error (in which prediction error is averaged over a new, random sample from the covariate distribution). The random-X setting more naturally embodies modern machine learning problems, where highly complex models, even those complex enough to interpolate the training data, can still lead to desirable generalization performance under appropriate conditions. We demonstrate the utility of our proposed complexity measures through a mix of conceptual arguments, theory, and experiments, and illustrate how they can be used to interpret and compare arbitrary prediction models. Copyright © 2024, The Authors. All rights reserved.

关键词： Prediction models

Domain adaptation under open set label shift 22

学校读者我要写书评

暂无评论

Domain adaptation under open set label shift

Proceedings of the 36th International Conference on Neural Information Processing Systems

作者： Saurabh Garg Sivaraman Balakrishnan Zachary C. Lipton Machine Learning Department Department of Statistics and Data Science Carnegie Mellon University

ISBN: (纸本)9781713871088

We introduce the problem of domain adaptation under Open Set Label Shift (OSLS) where the label distribution can change arbitrarily and a new class may arrive during deployment, but the class-conditional distributions p{x|y) are domain-invariant. OSLS subsumes domain adaptation under label shift and Positive-Unlabeled (PU) learning. The learner's goals here are two-fold: (a) estimate the target label distribution, including the novel class; and (b) learn a target classifier. First, we establish necessary and sufficient conditions for identifying these quantities. Second, motivated by advances in label shift and PU learning, we propose practical methods for both tasks that leverage black-box predictors. Unlike typical open set domain adaptation problems, which tend to be ill-posed and amenable only to heuristics, OSLS offers a well-posed problem amenable to more principled machinery. Experiments across numerous semi-synthetic benchmarks on vision, language, and medical datasets demonstrate that our methods consistently outperform open set domain adaptation baselines, achieving 10-25% improvements in target domain accuracy. Finally, we analyze the proposed methods, establishing finite-sample convergence to the true label marginal and convergence to optimal classifier for linear models in a Gaussian setup.

关键词：

Nonlinear Regression with Residuals: Causal Estimation with Time-varying Treatments and Covariates

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bates, Stephen Kennedy, Edward Tibshirani, Robert Ventura, Valérie Wasserman, Larry Departments of EECS and Statistics University of California Berkeley United States Department of Statistics & Data Science Carnegie Mellon University United States Departments of Biomedical Data Science and Statistics Stanford University United States Department of Statistics Data Science and Neuroscience Institute Carnegie Mellon University United States Departments of Statistics & Data Science and of Machine Learning Carnegie Mellon University United States

Standard regression adjustment gives inconsistent estimates of causal effects when there are time-varying treatment effects and time-varying covariates. Loosely speaking, the issue is that some covariates are post-treatment variables because they may be affected by prior treatment status, and regressing out post-treatment variables causes bias. More precisely, the bias is due to certain non-confounding latent variables that create colliders in the causal graph. These latent variables, which we call phantoms, do not harm the identifiability of the causal effect, but they render naive regression estimates inconsistent. Motivated by this, we ask: how can we modify regression methods so that they hold up even in the presence of phantoms? We develop an estimator for this setting based on regression modeling (linear, log-linear, probit and Cox regression), proving that it is consistent for a reasonable causal estimand. In particular, the estimator is a regression model fit with a simple adjustment for collinearity, making it easy to understand and implement with standard regression software. The proposed estimators are instances of the parametric g-formula, extending the regression-with-residuals approach to several canonical nonlinear models. © 2022, CC BY.

关键词： Phantoms

On the origins of linear representations in large language models 24

学校读者我要写书评

暂无评论

On the origins of linear representations in large language m...

Proceedings of the 41st International Conference on machine learning

作者： Yibo Jiang Goutham Rajendran Pradeep Ravikumar Bryon Aragam Victor Veitch Department of Computer Science University of Chicago Machine Learning Department Carnegie Mellon University Booth School of Business University of Chicago Department of Statistics and Data Science Institute University of Chicago

Recent works have argued that high-level semantic concepts are encoded "linearly" in the representation space of large language models. In this work, we study the origins of such linear representations. To that end, we introduce a simple latent variable model to abstract and formalize the concept dynamics of the next token prediction. We use this formalism to show that the next token prediction objective (softmax with cross-entropy) and the implicit bias of gradient descent together promote the linear representation of concepts. Experiments show that linear representations emerge when learning from data matching the latent variable model, confirming that this simple structure already suffices to yield linear representations. We additionally confirm some predictions of the theory using the LLaMA-2 large language model, giving evidence that the simplified model yields generalizable insights.

关键词：

Identifying general mechanism shifts in linear causal representations 24

学校读者我要写书评

暂无评论

Identifying general mechanism shifts in linear causal repres...

Proceedings of the 38th International Conference on Neural Information Processing Systems

作者： Tianyu Chen Kevin Bello Francesco Locatello Bryon Aragam Pradeep Ravikumar Department of Statistics and Data Sciences University of Texas at Austin Booth School of Business University of Chicago and Machine Learning Department Carnegie Mellon University Institute of Science and Technology Austria Booth School of Business University of Chicago Machine Learning Department Carnegie Mellon University

ISBN: (纸本)9798331314385

We consider the linear causal representation learning setting where we observe a linear mixing of d unknown latent factors, which follow a linear structural causal model. Recent work has shown that it is possible to recover the latent factors as well as the underlying structural causal model over them, up to permutation and scaling, provided that we have at least d environments, each of which corresponds to perfect interventions on a single latent node (factor). After this powerful result, a key open problem faced by the community has been to relax these conditions: allow for coarser than perfect single-node interventions, and allow for fewer than d of them, since the number of latent factors d could be very large. In this work, we consider precisely such a setting, where we allow a smaller than d number of environments, and also allow for very coarse interventions that can very coarsely change the entire causal graph over the latent factors. On the flip side, we relax what we wish to extract to simply the list of nodes that have shifted between one or more environments. We provide a surprising identifiability result that it is indeed possible, under some very mild standard assumptions, to identify the set of shifted nodes. Our identifiability proof moreover is a constructive one: we explicitly provide necessary and sufficient conditions for a node to be a shifted node, and show that we can check these conditions given observed data. Our algorithm lends itself very naturally to the sample setting where instead of just interventional distributions, we are provided datasets of samples from each of these distributions. We corroborate our results on both synthetic experiments as well as an interesting psychometric dataset. The code can be found at https://***/TianyuCodings/iLCS.

关键词：