Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 21 for “"PAC Learning"”.

  1. Efficient pac-learning for episodic tasks with acyclic state spaces and the optimal node visitation problem in acyclic stochastic digaphs.

    … implementable Probably Approximately Correct (PAC)-learning algorithms for episodic tasks over acyclic state spaces. The defining characteristic of our algorithms is that they take explicitly into consideration the acyclic structure of the underlying state space and the episodic nature of the …

    gatech Repository record for Efficient pac-learning for episodic tasks with acyclic state spaces and the optimal node visitation problem in acyclic stochastic digaphs. (opens in a new tab)

  2. Topics in computational learning theory and graph algorithms

    "The distribution-independent model of concept learning from examples (""PAC-learning"") due to Valiant is investigated. It has previously been shown that the existence of an Occam algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class. (An Occam …

    uiuc Repository record for Topics in computational learning theory and graph algorithms (opens in a new tab)

  3. On learning from lower bounds

    … between circuit lower bounds and algorithms for learning circuits. In particular, we present ways of converting Nisan's method of communication-complexity-based circuit lower bounds to algorithms for learning circuits with threshold gates. From this we obtain: A generic transformation of any …

    bu Repository record for On learning from lower bounds (opens in a new tab)

  4. Application of learning theory in neural modeling of dynamic systems

    … newly introduced Probably Approximately Correct (PAC) learning theory addresses the issue of testing-training balance. However, conventional PAC learning only allows static modeling and cannot be applied to dynamic models. In this thesis, PAC learning is extended to more general learning schemes …

    ubc Repository record for Application of learning theory in neural modeling of dynamic systems (opens in a new tab) Download PDF for Application of learning theory in neural modeling of dynamic systems (opens in a new tab)

  5. Characterizing Algorithmic Efficiencies through Concentration

    … is probabilistically approximately correct (PAC) learning. I chose this domain since it allows us to approach the important subject of supervised learning in a rigorous and principled manner. For PAC learning, I propose a quantum algorithm to learn the class of concentrated Boolean functions …

    rice Repository record for Characterizing Algorithmic Efficiencies through Concentration (opens in a new tab)

  6. Learning queries under description logic ontologies

    … description logic (DL) ontologies. We focus on learning in the sense of Angluin’s exact learning and of probably approximately correct (PAC) learning, and on description logics of the EL and DL-Lite-core families, which underlie the OWL 2 EL and QL profiles, respectively. In both models of …

    qucosa-diss

  7. Learning discrete Hidden Markov Models from state distribution vectors

    … dissertation, we develop several new efficient learning algorithms for learning HMM parameters. First, we propose a new polynomial-time algorithm for supervised learning of the parameters of a first order HMM from a state probability distribution (SD) oracle. The SD oracle provides the learner …

    lsu-thes Repository record for Learning discrete Hidden Markov Models from state distribution vectors (opens in a new tab)

  8. EFFECTIVE CONCEPT CLASSES OF PAC AND PACi INCOMPARABLE DEGREES, JOINS AND EMBEDDING OF DEGREES

    The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples. We construct two effective concept classes of incomparable PAC degrees to show that there exist incomparable PAC degrees, analogous to incomparable Turing degrees. The …

    siu-theses Repository record for EFFECTIVE CONCEPT CLASSES OF PAC AND PACi INCOMPARABLE DEGREES, JOINS AND EMBEDDING OF DEGREES (opens in a new tab)

  9. A Proposed Algorithm Toward Uniform-distribution Monotone DNF Learning

    … model of Probably Approximately Correct (PAC) learning from random examples and brought up the problem of whether polynomial-size DNF functions are PAC learnable in polynomial time. It has been about twenty years that the DNF learning problem has been widely regarded as one of the most …

    duquesne Repository record for A Proposed Algorithm Toward Uniform-distribution Monotone DNF Learning (opens in a new tab)

  10. Refining the sample complexity of comparative learning

    The PAC (Probably Approximately Correct) framework is a well-established theoretical framework for analyzing the statistical (and sometimes computational) complexity of machine learning tasks. Comparative learning is a recently introduced variation of the PAC framework that interpolates between the …

    york Repository record for Refining the sample complexity of comparative learning (opens in a new tab)

  11. Prospective Learning and Control

    Learning involves updating decision rules based on past experience to improve future performance. The prevailing theoretical framework for studying machine learning, probably approximately correct (PAC) learning, assumes that future data will be drawn from the same fixed distribution as past data. …

    jhu Repository record for Prospective Learning and Control (opens in a new tab)

  12. Efficient Replicable Learning: Parity Functions under Product Distributions and Heavy-Mass Subspace Recovery

    … trust and safety concerns in high-stakes machine learning. While stricter than standard PAC learning, replicability often requires prohibitive computation or restrictive distributional assumptions. This thesis advances replicable learning through three core contributions: First, we establish a …

    jhu Repository record for Efficient Replicable Learning: Parity Functions under Product Distributions and Heavy-Mass Subspace Recovery (opens in a new tab)

  13. Naive Bayes Data Complexity and Characterization of Optima of the Unsupervised Expected Likelihood

    … a baseline, for both supervised and unsupervised learning. With a latent class variable it is one of the simplest latent variable models, and is often used for clustering. The estimation of its parameters by maximum likelihood (e.g. using gradient ascent, expectation maximization) is subject to …

    waterloo Repository record for Naive Bayes Data Complexity and Characterization of Optima of the Unsupervised Expected Likelihood (opens in a new tab)

  14. Essays On Algorithms, Markets, And Society

    … theory, the Probably Approximately Correct (PAC) Learning framework, no-regret learning algorithms, equilibrium analysis, smoothness, differential privacy, and quantitative fairness. In addition to theoretical analysis, we implement various algorithms and mechanisms and perform empirical …

    penn Repository record for Essays On Algorithms, Markets, And Society (opens in a new tab)

  15. On efficient learning algorithms for neural networks.

    Inductive Inference Learning can be described in terms of finding a good approximation to some unknown classification rule f, based on a pre-classified set of training examples $\langle$x,f(x)$\rangle.$ One particular class of learning systems that has attracted much attention recently is the class …

    ottawa-retro Repository record for On efficient learning algorithms for neural networks. (opens in a new tab)

  16. Practical learning in a private and noisy world

    … two fundamental settings in theoretical machine learning where worst-case formulations impose sharp computational hardness barriers: learning under privacy constraints and learning under noise. In both settings, we show that carefully chosen relaxations of the standard models, reflecting …

    bu Repository record for Practical learning in a private and noisy world (opens in a new tab)

  17. On computationally efficient learning for stabilizers and beyond

    Artificial intelligence, big data, machine learning, neural networks – look up any recent research proposal and with good probability at least one of these phrases will appear. It’s no secret that learning has taken this era of computer science by storm in our attempt to create software that …

    texas Repository record for On computationally efficient learning for stabilizers and beyond (opens in a new tab)

  18. Quantum Compression and Quantum Learning via Information Theory

    … of two parts: quantum compression and quantum learning theory. A common theme between these problems is that we study them through the lens of information theory. We first study the task of visible compression of an ensemble of quantum states with entanglement assistance in the one-shot …

    waterloo Repository record for Quantum Compression and Quantum Learning via Information Theory (opens in a new tab)

  19. Cardinality Learning under Practical Constraints: Principled Theory and Empirical Design

    … been formulated as a \emph{query-driven machine learning (ML) problem}, in which the system learns from observed queries and their cardinalities to make predictions for future queries. Such methods have shown strong potential because they can better capture data correlations and skewness. Despite …

    penn Repository record for Cardinality Learning under Practical Constraints: Principled Theory and Empirical Design (opens in a new tab)

  20. On the Sample Complexity of Privately Learning Gaussians and their Mixtures

    … complexity upper bounds for semi-agnostically learning multivariate Gaussians under the constraint of approximate differential privacy. These are the first finite sample upper bounds for general Gaussians which do not impose restrictions on the parameters of the distribution. Our bounds are …

    mcmaster Repository record for On the Sample Complexity of Privately Learning Gaussians and their Mixtures (opens in a new tab)

Page 1 of 2