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

Principal Component Analysis in Space Forms

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Tabaghi, Puoya Khanzadeh, Michael Wang, Yusu Mirarab, Siavash The Halıcıoglu Data Science Institute UCSD United States The Computer Science and Engineering Department UCSD United States The Electrical and Computer Engineering Department UCSD United States

Principal Component Analysis (PCA) is a workhorse of modern data science. While PCA assumes the data conforms to Euclidean geometry, for specific data types, such as hierarchical and cyclic data structures, other spaces are more appropriate. We study PCA in space forms;that is, those with constant curvatures. At a point on a Riemannian manifold, we can define a Riemannian affine subspace based on a set of tangent vectors. Finding the optimal low-dimensional affine subspace for given points in a space form amounts to dimensionality reduction. Our Space Form PCA (SFPCA) seeks the affine subspace that best represents a set of manifold-valued points with the minimum projection cost. We propose proper cost functions that enjoy two properties: (1) their optimal affine subspace is the solution to an eigenequation, and (2) optimal affine subspaces of different dimensions form a nested set. These properties provide advances over existing methods, which are mostly iterative algorithms with slow convergence and weaker theoretical guarantees. We evaluate the proposed SFPCA on real and simulated data in spherical and hyperbolic spaces. We show that it outperforms alternative methods in estimating true subspaces (in simulated data) with respect to convergence speed or accuracy, often both. © 2023, CC BY.

关键词： Principal component analysis

Do PAC-Learners Learn the Marginal Distribution?

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Hopkins, Max Kane, Daniel M. Lovett, Shachar Mahajan, Gaurav Department of Computer Science and Engineering UCSD California CA92092 United States Department of Computer Science and Engineering Department of Mathematics UCSD California CA92092 United States

We study a foundational variant of Valiant and Vapnik and Chervonenkis' Probably Approximately Correct (PAC)-Learning in which the adversary is restricted to a known family of marginal distributions P. In particular, we study how the PAC-learnability of a triple (P, X, H) relates to the learners ability to infer distributional information about the adversary's choice of D ∈ P. To this end, we introduce the 'unsupervised' notion of TV-Learning, which, given a class (P, X, H), asks the learner to approximate D from unlabeled samples with respect to a natural class-conditional total variation metric. In the classical distribution-free setting, we show that TV-learning is equivalent to PAC-Learning: in other words, any learner must infer near-maximal information about D. On the other hand, we show this characterization breaks down for general P, where PAC-Learning is strictly sandwiched between two approximate variants we call 'Strong' and 'Weak' TV-learning, roughly corresponding to unsupervised learners that estimate most relevant distances in D with respect to H, but differ in whether the learner knows the set of well-estimated events. Finally, we observe that TV-learning is in fact equivalent to the classical notion of uniform estimation, and thereby give a strong refutation of the uniform convergence paradigm in supervised *** Codes 68Q32 © 2023, CC BY.

关键词：

Enhancing size generalization in graph neural networks through disentangled representation learning 24

学校读者我要写书评

暂无评论

Enhancing size generalization in graph neural networks throu...

Proceedings of the 41st International Conference on Machine Learning

作者： Zheng Huang Qihui Yang Dawei Zhou Yujun Yan Department of Computer Science Dartmouth College Hanover NH Electrical and Computer Engineering UCSD San Diego Department of Computer Science Virginia Tech Blacksburg VA

Although most graph neural networks (GNNs) can operate on graphs of any size, their classification performance often declines on graphs larger than those encountered during training. Existing methods insufficiently address the removal of size information from graph representations, resulting in sub-optimal performance and reliance on backbone models. In response, we propose DISGEN, a novel and model-agnostic framework designed to disentangle size factors from graph representations. DISGEN employs size- and task-invariant augmentations and introduces a decoupling loss that minimizes shared information in hidden representations, with theoretical guarantees for its effectiveness. Our empirical results show that DISGEN outperforms the state-of-the-art models by up to 6% on real-world datasets, underscoring its effectiveness in enhancing the size generalizability of GNNs. Our codes are available at: https://***/GraphmindDartmouth/DISGEN.

关键词：

Chernoff Bounds and Reverse Hypercontractivity on HDX

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dikstein, Yotam Hopkins, Max Institute for Advanced Study United States Department of Computer Science and Engineering UCSD CA92092 United States

We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let X be a k-dimensional HDX. We show for any i ≤ k and function f : X(i) → [0, 1]: (Formula Presented) . Using this fact, we prove that high dimensional expanders are reverse hypercontractive, a powerful functional inequality from discrete analysis implying that for any sets A, B ⊂ X(k), the probability a ρ-correlated pair passes between them is at least (Formula Presented) Our results hold under weak spectral assumptions on X. Namely we prove exponential concentration of measure for any complex below the ‘Trickling-Down Threshold’ (beyond which concentration may be arbitrarily poor), and optimal concentration for √k-skeletons of such complexes. We also show optimal bounds for the top dimension of stronger HDX among other settings. We leverage our inequalities to prove several new agreement testing theorems on high dimensional expanders, including a new 99%-regime test for subsets, and a variant of the ‘Z-test’ achieving inverse exponential soundness under the stronger assumption of ∞-expansion. The latter gives rise to the first optimal testers beyond the complete complex and products, a stepping stone toward the use of HDX in strong soundness PCPs. We also give applications within expansion, analysis, combinatorics, and coding theory, including a proof that two-sided HDX have optimal geometric overlap (giving the first explicit bounded-degree construction), near-optimal double samplers, new super-exponential degree lower bounds for certain HDX, distance-amplified list-decodable and locally testable codes, a Frankl–Rödl Theorem, and more. © 2024, CC BY.

关键词： Inverse problems

Enhancing Size Generalization in Graph Neural Networks through Disentangled Representation Learning

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Huang, Zheng Yang, Qihui Zhou, Dawei Yan, Yujun Department of Computer Science Dartmouth College HanoverNH United States Electrical and Computer Engineering UCSD San Diego United States Department of Computer Science Virginia Tech BlacksburgVA United States

关键词： Graph neural networks

Improved classical shadows from local symmetries in the Schur basis

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Grier, Daniel Liu, Sihan Mahajan, Gaurav Department of Computer Science and Engineering Department of Mathematics UC San Diego United States Department of Computer Science and Engineering UCSD California CA92092 United States Institute for Foundations of Data Science Yale University Connecticut CT06511 United States

We study the sample complexity of the classical shadows task: what is the fewest number of copies of an unknown state you need to measure to predict expected values with respect to some class of observables? Large joint measurements are likely required in order to minimize sample complexity, but previous joint measurement protocols only work when the unknown state is pure. We present the first joint measurement protocol for classical shadows whose sample complexity scales with the rank of the unknown state. In particular we prove O(√rB/ǫ2) samples suffice, where r is the rank of the state, B is a bound on the squared Frobenius norm of the observables, and ϵ is the target accuracy. In the low-rank regime, this is a nearly quadratic advantage over traditional approaches that use single-copy measurements. We present several intermediate results that may be of independent interest: a solution to a new formulation of classical shadows that captures functions of non-identical input states;a generalization of a "nice" Schur basis used for optimal qubit purification and quantum majority vote;and a measurement strategy that allows us to use local symmetries in the Schur basis to avoid intractable Weingarten calculations in the analysis. © 2024, CC BY.

关键词：

Sampling Equilibria: Fast No-Regret Learning in Structured Games

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Beaglehole, Daniel Hopkins, Max Kane, Daniel Liu, Sihan Lovett, Shachar Department of Computer Science and Engineering UCSD CA92092 United States Department of Mathematics UCSD CaliforniaCA92092 United States

Learning and equilibrium computation in games are fundamental problems across computer science and economics, with applications ranging from politics to machine learning. Much of the work in this area revolves around a simple algorithm termed randomized weighted majority (RWM), also known as "Hedge" or "Multiplicative Weights Update," which is well known to achieve statistically optimal rates in adversarial settings (Littlestone and Warmuth'94, Freund and Schapire'99). Unfortunately, RWM comes with an inherent computational barrier: it requires maintaining and sampling from a distribution over all possible actions. In typical settings of interest the action space is exponentially large, seemingly rendering RWM useless in practice. In this work, we refute this notion for a broad variety of structured games, showing it is possible to efficiently (approximately) sample the action space in RWM in polylogarithmic time. This gives the first efficient no-regret algorithms for problems such as the (discrete) Colonel Blotto game, matroid congestion, matroid security, and basic dueling games. As an immediate corollary, we give a polylogarithmic time meta-algorithm to compute approximate Nash Equilibria for these games that is exponentially faster than prior methods in several important settings. Further, our algorithm is the first to efficiently compute equilibria for more involved variants of these games with general sums, more than two players, and, for Colonel Blotto, multiple resource types. © 2022, CC0.

关键词： computer games

LLMs-based Few-Shot Disease Predictions using EHR: A Novel Approach Combining Predictive Agent Reasoning and Critical Agent Instruction

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Cui, Hejie Shen, Zhuocheng Zhang, Jieyu Shao, Hui Qin, Lianhui Ho, Joyce C. Yang, Carl Department of Computer Science Emory University AtlantaGA United States School of Computer Science & Engineering University of Washington SeattleWA United States Department of Computer Science & Engineering UCSD San DiegoCA United States Rollins School of Public Health Emory University AtlantaGA United States School of Medicine Emory University AtlantaGA United States

Electronic health records (EHRs) contain valuable patient data for health-related prediction tasks, such as disease prediction. Traditional approaches rely on supervised learning methods that require large labeled datasets, which can be expensive and challenging to obtain. In this study, we investigate the feasibility of applying Large Language Models (LLMs) to convert structured patient visit data (e.g., diagnoses, labs, prescriptions) into natural language narratives. We evaluate the zero-shot and few-shot performance of LLMs using various EHR-prediction-oriented prompting strategies. Furthermore, we propose a novel approach that utilizes LLM agents with different roles: a predictor agent that makes predictions and generates reasoning processes and a critic agent that analyzes incorrect predictions and provides guidance for improving the reasoning of the predictor agent. Our results demonstrate that with the proposed approach, LLMs can achieve decent few-shot performance compared to traditional supervised learning methods in EHR-based disease predictions, suggesting its potential for health-oriented applications. Copyright © 2024, The Authors. All rights reserved.

关键词： Forecasting

Eigenstripping, Spectral Decay, and Edge-Expansion on Posets

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Gaitonde, Jason Hopkins, Max Kaufman, Tali Lovett, Shachar Zhang, Ruizhe Department of Computer Science Cornell University United States Department of Computer Science and Engineering UCSD CA92092 United States Department of Computer Science Bar-Ilan University Department of Computer Science UT Austin Austria

We study the relationship between the underlying structure of posets and the spectral and combinatorial properties of their higher-order random walks. While fast mixing of random walks on hypergraphs (simplicial complexes) has led to myriad breakthroughs throughout theoretical computer science in the last five years, many other important applications (e.g. to locally testable codes, 2-2 games) rely on the more general non-simplicial structure of posets. These works make it clear that the global expansion properties of posets depend strongly on their underlying architecture (e.g. simplicial, cubical, linear algebraic), but the overall phenomenon remains poorly understood. In this work, we quantify the advantage of different poset architectures, highlighting how structural regularity controls the spectral decay and edge-expansion of corresponding random walks. In particular, we show that the spectra of walks on expanding posets (Dikstein, Dinur, Filmus, Harsha RANDOM 2018) concentrate in strips around a small number of approximate eigenvalues controlled by the regularity of the underlying poset. This gives a simple condition to identify poset architectures (e.g. the Grassmann) that exhibit fast (exponential rate) decay of eigenvalues, versus architectures like hypergraphs whose eigenvalues decay slowly (linear rate)-a crucial distinction in applications to hardness of approximation and agreement testing such as the recent proof of the 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead to a tight variance-based characterization of edge-expansion on expanding posets generalizing (Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay special attention to the case of the Grassmann where we show our results are tight for a natural set of sparsifications of the Grassmann graphs. We note for clarity that our results do not recover the characterization used in the proof of the 2-2 Games Conjecture which relies on 8 rather than 2-structure. ©

关键词： Eigenvalues and eigenfunctions