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 “"vc dimension"”.
-
On The Combinatorics of Sample Compression Schemes
… a sample compression scheme of size equal to the VC dimension of a concept class C exists then C can be PAC learned by some learning algorithm. Although it is already known that any concept class of nite VC dimension is PAC learnable, the existence of a sample compression scheme of size equal to …
-
Definable families of finite Vapnik Chervonenkis dimension
Vapnik Chervonenkis dimension is a basic combinatorial notion with applications in machine learning, stability theory, and statistics. We explore what effect model theoretic structure has on the VC dimension of formulas, considered as parameterized families of sets, with respect to long …
-
Relationship between classifier performance and distributional complexity for small samples
… available. Classifier study in terms of the VC dimension of a learning machine is also discussed.
-
Eccentric sets
… the Hartogs–Lindenbaum spectrum in models of SVC before constructing a model of ZF with maximal Hartogs–Lindenbaum spectrum (that is, the universe is as eccentric as possible). Chapter 4. From [Rya24a]. Within this chapter I examine maximal θ-independent families (where θ is a cardinal): …
-
DEEP NEURAL NETWORK APPROXIMATION VIA FUNCTION COMPOSITIONS
… engineering, especially for large-scale and high-dimensional learning problems. This thesis focuses on the approximation theory of deep neural networks. We provide (nearly optimal) approximation error estimates in terms of the width and depth when constructing ReLU networks, via the idea of …
-
Weighted inequalities via dyadic operators and a learning theory approach to compressive sensing
… in one-bit sensing. We effectively estimate the VC-dimension of hemispheres relative to sparse vectors, which allows us to employ learning theory techniques to control an empirical process. This control yields the (1-bit) Restricted Isometry Property with high probability. With these methods, we …
-
Low rank is in the eye of the beholder
… approximations to extract structure from high-dimensional data. Yet determining when a matrix is well approximated by one of lower rank—and selecting appropriate rank and approximation error thresholds—is inherently context-dependent: the answer may depend not only on the matrix dimensions but …
-
A Graph-Theoretic View of Teaching
… teaching complexity. We show that the teaching dimension of a concept, i.e., the minimum number of examples required for teaching that concept, is lower bounded by the degree of the corresponding vertex in the one-inclusion graph. Furthermore, we prove that for concepts in shortest-path-closed …
-
Error and f -Divergence Analysis of Generative Adversarial Network
… The new class of functions is uniformly bounded, VC type, with bounded envelope function and Vapnik–Chervonenkis (VC) dimension dimension which makes it possible to apply Talagrand inequality. A tight convergence rate is derived for the error of GAN after applying the Talagrand inequality and …
-
Inherent Limitations of Dimensions for Characterizing Learnability
… binary classification with the finiteness of the VC dimension. Motivated by these foundational results, this work explores whether similar characterizations of learnability and sample complexity can be defined through dimensions in other learning models. We introduce the concept of a …
-
Supervised Topic Modeling for Scientific Texts: Bayesian Shrinkage Methods and Domain-Specific Applications in Forensics and Online Aggression Sciences
… and theoretical generalization analysis using VC-dimension bounds, confirming their practical and statistical utility. Together, these contributions offer a robust framework for interpretable and predictive topic modeling in applied scientific domains. Our work advances both the methodological …
-
A new approach of top-down induction of decision trees for knowledge discovery
… inductions.;Quinlan used information gains via VC-dimension (Vapnik-Chevonenkis; Vapnik, 1995) for clustering the experimental values for each numerical attribute. However, many researchers have discovered the weakness of the use of VC-dim analysis. Bennett (1997) sophistically applies support …
-
Centralized and distributed learning methods for predictive health analytics
… convergence of the method and characterize its VC dimension. Last, we develop a decentralized cluster Primal-Dual Splitting (cPDS) method for large-scale problems, that is computationally efficient and privacy-aware. Such a distributed learning scheme is relevant for multi-institutional …
-
Pareto multi-objective evolution of legged embodied organisms
… nature of the locomotion behavior and capacity (VC-dimension) of the ANN controller generated, (3) the effciency of the proposed approach against more conventional methods of evolutionary optimization in terms of computational cost and quality of solutions, (4) a multi-objective approach towards …
-
On generalized adaptive neural filter
… determined before a training scheme is executed; VC dimension (VCdim) theory can be applied to determine the number of training samples; the algorithm presented in configuring GANFs is effective and robust.
-
Theoretical Expressivity of Self-Attention as a Model of Binary Sequence-To-Sequence Functions and Other Explorations
… non-trivial case to analyze. We find, using VC dimension and the Sauer-Shelah lemma, that in the limit of long sequences, almost all binary seq2seq functions cannot be implemented by self-attention. We further demonstrate that every such function that self-attention cannot implement contains …
-
Uncertainty management in the activated sludge process: Innovative applications of computational learning theory.
… model denoted M . The Vapnik-Chervonenkis (VC) dimension of this model is estimated and two uncertainty models are developed for the activated sludge process (ASP). These two uncertainty models are compared and the differences between them accounted for. The following result is established: …
-
Tensile strength estimation of lumber
… the suitability of a regression estimator (VC-dimension) was developed in order to select the best model in a class of models. The ASEC learning model was developed in order to find the best set of new features from the given feature set by using the known dependencies. Different learning …
-
Complexity Parameters for Learning Multi-Label Concept Classes,
… examined in this work is the Vapnik-Chervonenkis-dimension (VCD) and its previously studied analogues for multi-label concept classes such as the Graph-dimension, Pollard's pseudo-dimension and the Natarajan dimension. This thesis also extends the study of sample compression schemes to multi-label …
-
Measurability Aspects of the Compactness Theorem for Sample Compression Schemes
In 1998, it was proved by Ben-David and Litman that a concept space has a sample compression scheme of size $d$ if and only if every finite subspace has a sample compression scheme of size $d$. In the compactness theorem, measurability of the hypotheses of the created sample compression scheme is …
Page 1 of 2