Martin Sewell · 2008
VC dimension (for Vapnik Chervonenkis dimension) measures the capacity of a hypothesis space. Capacity is a measure of complexity and measures the expressive power, richness or flexibility of a set of functions by assessing how wiggly its members can be. The definitions below are taken from Vapnik (1999). Definition 1 The VC dimension of a set of indicator functions (Vapnik and Chervonekis 1968; Vapnik and Chervonenkis 1971) The VC dimension of a set of indicator functions Q(z, α), α ∈ Λ, is the maximum number h of vectors z1,..., zh that can be separated into two classes in all 2 h possible ways using functions of the set 1 (i.e., the maximum number of vectors that can be shattered by the set of functions). If for any n there exists a set of n vectors that can be shattered by the set Q(z, α), α ∈ Λ, then the VC dimension is equal to infinity. Definition 2 The VC dimension of a set of real functions (Vapnik 1979) Let A ≤ Q(z, α) ≤ B, α ∈ Λ, be a set of real functions bounded by constants A
Cited by 0
Thomas Zeugmann · Encyclopedia of Machine Learning and Data Mining · 2017
Cited by 0
Shai Shalev‐Shwartz, Shai Ben-David · Cambridge University Press eBooks · 2014
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Cited by 0
Sanjeev Kulkarni, Gilbert Harman · Wiley series in probability and statistics · 2011
This chapter presents, higher the Vapnik–Chervonenkis (VC) dimension of the hypothesis set C, the more likely it is that the best hypothesis in C approximates the Bayes error rate but also the longer it takes to attain probably approximately correct (PAC) learning. This reflects a trade-off between estimation error and approximation error, but rather harshly forces large approximation by requiring finite VC dimension. After seeing some labeled examples, the learner selects a hypothesis by suitably trading off the misfit to the data and the complexity of the hypothesis. One of the key choices is the way we measure the complexity, or equivalently, the simplicity, of the decision rules. This approach is related to a number of other learning methods based on simplicity known by various names such as Occam’s razor, minimum description length (MDL) principle, structural risk minimization, and Akaike’s information criterion (AIC). Controlled Vocabulary Terms Akaike information criterion; Bayes error rate
Cited by 0
Nicolas Bousquet · 2013
Cited by 0
O Teytaud · 2007
Families of finite VC-dimension are not able of ensuring a good asymptotic behavior for any distribution. We sum up and compare paradigms for working without finiteness of the VC-dimension and compare them.
Cited by 0
Sampath K Kannan, Volkan Isler, Kostas Daniilidis et al. · Scholarly Commons (University of Pennsylvania) · 2004
In this paper, we study the Vapnik-Chervonenkis (VC)-dimension of set systems arising in 2D polygonal and 3D polyhedral configurations where a subset consists of all points visible from one camera. In the past, it has been shown that the VC-dimension of planar visibility systems is bounded by 23 if the cameras are allowed to be anywhere inside a polygon without holes [1]. Here, we consider the case of exterior visibility, where the cameras lie on a constrained area outside the polygon and have to observe the entire boundary. We present results for the cases of cameras lying on a circle containing a polygon (VC-dimension= 2) or lying outside the convex hull of a polygon (VC-dimension= 5). The main result of this paper concerns the 3D case: We prove that the VC-dimension is unbounded if the cameras lie on a sphere containing the polyhedron, hence the term exterior visibility.
Cited by 0
Pascal Koiran · 2002
The main result of this paper is a /spl Omega/(n/sup 1/4/) lower bound on the size of a sigmoidal circuit computing a specific AC/sub 2//sup 0/ function. This is the first lower bound for the computation model of sigmoidal circuits with unbounded weights. We also give upper and lower bounds for the same function in a few other computation models: circuits of AND/OR gates, threshold circuits, and circuits of piecewise-rational gates.
Cited by 0
Samuel Tenka · Notices of the American Mathematical Society · 2021
Combinatorists and bakers alike know the sequence 1, 2, 4, 8, 16, by heart. It continues, of course, with 31, for its th element () counts the pieces obtained from a diskshaped cake by cutting along all ( 2 ) lines determined by generic points on the cake's boundary. Figure 1. Cakes for = 1 through 6. The = 4 cake (bottom left) has (4) = 8 pieces. Using colors to ease counting, we see that (6) is odd: the pieces besides the central yellow triangle partition into sets of six.
Cited by 0Open access
Noga Alon, Shay Moran, Amir Yehudayoff · arXiv (Cornell University) · 2015
This work studies the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is {three}. For $d=2$, this maximum is $\tildeΘ(N^{1/2})$. For $d >2$, similar but slightly less accurate statements hold. {The lower bounds improve over previous ones by Ben-David et al., and the upper bounds are novel.} The lower bounds are obtained by probabilistic constructions, using a theorem of Warren in real algebraic topology. The upper bounds are obtained using a result of Welzl about spanning trees with low stabbing number, and using the moment curve. The upper bound technique is also used to: (i) provide estimates on the number of classes of a given VC dimension, and the number of maximum classes of a given VC dimension -- answering a question of Frankl from '89, and (ii) design an efficient algorithm that provides an $O(N/\log(N))$ multiplicative approximation for the sign rank. We also observe a general connection between sign rank and spectral gaps which is based on Forster's argument. Consider the $N \times N$ adjacency matrix of a $Δ$ regular graph with a second eigenvalue of absolute value $λ$ and $Δ\leq N/2$. We show that the sign rank of the signed version of this matrix is at least $Δ/λ$. We use this connection to prove the existence of a maximum class $C\subseteq\{\pm 1\}^N$ with VC dimension $2$ and sign rank $\tildeΘ(N^{1/2})$. This answers a question of Ben-David et al.~regarding the sign rank of large VC classes. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem. We further describe connections to communication complexity, geometry, learning theory, and combinatorics.
Cited by 5Open access
Gabriel Conant, Anand Pillay · Journal of Mathematical Logic · 2020
We develop “local NIP group theory” in the context of pseudofinite groups. In particular, given a sufficiently saturated pseudofinite structure [Formula: see text] expanding a group, and left invariant NIP formula [Formula: see text], we prove various aspects of “local fsg” for the right-stratified formula [Formula: see text]. This includes a [Formula: see text]-type-definable connected component, uniqueness of the pseudofinite counting measure as a left-invariant measure on [Formula: see text]-formulas and generic compact domination for [Formula: see text]-definable sets.
Cited by 3Open access
Volkan Isler, S. Kannan, Kostas Daniilidis et al. · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2004
In this paper, we study the Vapnik-Chervonenkis (VC)-dimension of set systems arising in 2D polygonal and 3D polyhedral configurations where a subset consists of all points visible from one camera. In the past, it has been shown that the VC-dimension of planar visibility systems is bounded by 23 if the cameras are allowed to be anywhere inside a polygon without holes. Here, we consider the case of exterior visibility, where the cameras lie on a constrained area outside the polygon and have to observe the entire boundary. We present results for the cases of cameras lying on a circle containing a polygon (VC-dimension= 2) or lying outside the convex hull of a polygon (VC-dimension= 5). The main result of this paper concerns the 3D case: We prove that the VC-dimension is unbounded if the cameras lie on a sphere containing the polyhedron, hence the term exterior visibility.
Cited by 29
Olcay Taner Yıldız · Akademik Açık Erişim (Işık Üniversitesi) · 2014
In this paper, we give and prove lower bounds of the VC-dimension of the rule set hypothesis class where the input features are binary or continuous. The VC-dimension of the rule set depends on the VC-dimension values of its rules and the number of inputs.
Cited by 0Open access
Nicolas Bousquet · theses.fr (ABES) · 2013
Dans cette thèse, nous étudions des problèmes de transversaux d'un point de vue tant algorithmique que combinatoire. Etant donné un hypergraphe, un transversal est un ensemble de sommets qui touche toutes les hyperarêtes. Un packing est un ensemble d'hyperarêtes deux à deux disjointes. Alors que la taille minimale d'un transversal est au moins égale à la taille maximale d'un packing on ne peut pas dans le cas général borner la taille minimale d'un transversal par une fonction du packing maximal. Dans un premier temps, un état de l'art rappelle les différentes conditions qui assurent l'existence de bornes supérieures sur la taille des transversaux, en particulier en fonction de la taille d'un packing. La plupart d'entre elles sont valables lorsque la VC-dimension de Vapnik-Chervonenkis de l'hypergraphe, est bornée. L'originalité de la thèse consiste à utiliser ces outils d'hypergraphes pour obtenir des résultats sur des problèmes de graphes. Nous prouvons notamment une conjecture de coloration de Scott dans le cas des graphes sans-triangle maximaux; ensuite, nous généralisons un résultat de Chepoi, Estellon et Vaxès traitant de domination à grande distance; enfin nous nous attaquons à une conjecture de Yannakakis sur la séparation des cliques et des stables d'un graphe.Dans un second temps, nous étudions les transversaux d'un point de vue algorithmique. On se concentre plus particulièrement sur les problèmes de séparation de graphe où on cherche des transversaux à un ensemble de chemin. En combinant des outils de connexité, les séparateurs importants et le théorème de Dilworth, nous obtenons un algorithme FPT pour le problème Multicut paramétré par la taille de la solution.
Cited by 0Open access
Yohji Akamaa, Kei Irieb · 2016
Cited by 0
Léon Bottou, Corinna Cortes, Vladimir Vapnik · 1994
The very idea of an "Effective Vapnik Chervonenkis (VC) dimension" (Vapnik, Levin and Le Cun, 1993) relies on the hypothesis that the relation between the generalization error and the number of training examples can be expressed by a formula algebraically similar to the VC bound. This hypothesis calls for a serious discussion since the traditional VC bound widely overestimates the generalization error. In this paper we describe an algorithm and data dependent measure of capacity. We derive a confidence interval on the difference between the training error and the generalization error. This confidence interval is much tighter than the traditional VC bound. A simple change of the formulation of the problem yields this extra accuracy: our confidence interval bounds the error difference between a training set and a test set, rather than the error difference between a training set and some hypothetical grand truth. This "transductive" approach allows for deriving a data and algorithm depend...
Cited by 0
Yu. V. Malykhin · Mathematical Notes · 2012
We study the relationship between two characteristics of functional classes, pseudodimension and bracketing entropy. (Pseudodimension is a generalization of VC-dimension to classes of functions. Bracket entropy characterizes the L 1-error of one-sided approximation of a class by finite sets.) It is shown that classes of continuous functions with finite pseudodimension possess a finite bracketing ɛ-entropy for any ɛ > 0. We establish a general result concerning the relationship between the VC-dimension of classes of sets and their bracketing entropy.
Cited by 0
Pascal Koiran Lip, Pascal Koiran · 1995
The main result of this paper is a \\Omega\\Gamma n 1=4 ) lower bound on the size of a sigmoidal circuit computing a specific AC 0 2 function. This is the first lower bound for the computation model of sigmoidal circuits with unbounded weights. We also give upper and lower bounds for the same function in a few other computation models: circuits of AND/OR gates, threshold circuits, and circuits of piecewise-rational gates. 1 Introduction One of the main trends in circuit complexity has been to establish lower bounds for circuits made of increasingly powerful gates. Threshold circuits have been quite popular. Here we study generalizations of this computation model. A gate with p inputs x 1 ; : : : ; x p outputs y = OE( P p i=1 w i x i \\Gamma `) where OE : R ! R is a fixed real function. The numerical parameters w 1 ; : : : ; w p and ` are called weights (` is also often called a threshold). When OE is the sign function H , the threshold circuit model is recovered. Of particular inte...
Cited by 0
Linu Pinto, Sasi Gopalan, S. Sundararajan · 2018
In a supervised learning system the combination of fuzzy and neural network (NN) balancing the complexity of the network by the modification of membership functions and the hidden nodes. This paper presents a neural network for classification based on Vapnik Chervonenkis Dimensions (VC) for the structuring of hidden layers. A strong mathematical structure with a quartic equation is developed in this work to optimize the lower bound for the hidden nodes of the network. Experimentally it is analyzed with Thyroid dataset from UCI Machine Learning Repository using MATLAB R2018 (a) software.
Cited by 0
Sébastien Ratel · theses.fr (ABES) · 2019
Une partie des résultats de cette thèse sont initialement motivés par l'élaboration de schémas d'étiquetage permettant de réponde à l'adjacence, à la distance ou au routage. Ce document traite cependant de problèmes d'intérêt plus généraux tels que l'étude de bornes sur la densité de graphes, de la VC-dimension de familles d'ensembles, ou de propriétés métriques et structurelles.Nous établissons dans un premier temps des bornes supérieures sur la densité des sous-graphes de produits cartésien de graphes, puis des sous-graphes de demi-cubes. Pour ce faire, nous définissons des extensions du paramètre classique de VC-dimension. De ces bornes sur la densité, nous déduisons des bornes supérieures sur la longueur des étiquettes attribuées par un schéma d'adjacence à ces deux familles de graphes.Dans un second temps, nous nous intéressons à des schémas de distance et de routage pour deux familles importantes de la théorie métrique des graphes: les graphes médians et les graphes pontés. Nous montrons que la famille des graphes médians, sans cube, avec n sommets, admet des schémas de distance et de routage utilisant des étiquettes de O(\log^3 n). Ces étiquettes sont décodées en temps constant pour calculer, respectivement, la distance exacte entre deux sommets, ou le port vers un sommet rapprochant une source d'une destination. Nous décrivons ensuite un schéma de distances 4-approchées pour la famille des graphes pontés, sans K_4, avec n sommets, utilisant des étiquettes de O(\log^3 n) bits. Ces dernières peuvent être décodées en temps constant pour obtenir une valeur entre la distance exacte et quatre fois celle-ci.
Cited by 0Open access