The Experts below are selected from a list of 4377 Experts worldwide ranked by ideXlab platform
Jun Wang - One of the best experts on this subject based on the ideXlab platform.
-
a support vector machine with a hybrid kernel and minimal vapnik chervonenkis Dimension
IEEE Transactions on Knowledge and Data Engineering, 2004Co-Authors: Ying Tan, Jun WangAbstract:We present a mechanism to train support vector machines (SVMs) with a hybrid kernel and minimal Vapnik-Chervonenkis (VC) Dimension. After describing the VC Dimension of sets of separating hyperplanes in a high-Dimensional feature space produced by a mapping related to kernels from the input space, we proposed an optimization criterion to design SVMs by minimizing the upper bound of the VC Dimension. This method realizes a structural risk minimization and utilizes a flexible kernel function such that a superior generalization over test data can be obtained. In order to obtain a flexible kernel function, we develop a hybrid kernel function and a sufficient condition to be an admissible Mercer kernel based on common Mercer kernels (polynomial, radial basis function, two-layer neural network, etc.). The nonnegative combination coefficients and parameters of the hybrid kernel are determined subject to the minimal upper bound of the VC Dimension of the learning machine. The use of the hybrid kernel results in a better performance than those with a single common kernel. Experimental results are discussed to illustrate the proposed method and show that the SVM with the hybrid kernel outperforms that with a single common kernel in terms of generalization power.
-
a support vector machine with a hybrid kernel and minimal vapnik chervonenkis Dimension
IEEE Transactions on Knowledge and Data Engineering, 2004Co-Authors: Jun WangAbstract:We present a mechanism to train support vector machines (SVMs) with a hybrid kernel and minimal Vapnik-Chervonenkis (VC) Dimension. After describing the VC Dimension of sets of separating hyperplanes in a high-Dimensional feature space produced by a mapping related to kernels from the input space, we proposed an optimization criterion to design SVMs by minimizing the upper bound of the VC Dimension. This method realizes a structural risk minimization and utilizes a flexible kernel function such that a superior generalization over test data can be obtained. In order to obtain a flexible kernel function, we develop a hybrid kernel function and a sufficient condition to be an admissible Mercer kernel based on common Mercer kernels (polynomial, radial basis function, two-layer neural network, etc.). The nonnegative combination coefficients and parameters of the hybrid kernel are determined subject to the minimal upper bound of the VC Dimension of the learning machine. The use of the hybrid kernel results in a better performance than those with a single common kernel. Experimental results are discussed to illustrate the proposed method and show that the SVM with the hybrid kernel outperforms that with a single common kernel in terms of generalization power.
Peter L Bartlett - One of the best experts on this subject based on the ideXlab platform.
-
nearly tight VC Dimension and pseudoDimension bounds for piecewise linear neural networks
arXiv: Learning, 2017Co-Authors: Peter L Bartlett, Nicholas J A Harvey, Christopher Liaw, Abbas MehrabianAbstract:We prove new upper and lower bounds on the VC-Dimension of deep neural networks with the ReLU activation function. These bounds are tight for almost the entire range of parameters. Letting $W$ be the number of weights and $L$ be the number of layers, we prove that the VC-Dimension is $O(W L \log(W))$, and provide examples with VC-Dimension $\Omega( W L \log(W/L) )$. This improves both the previously known upper bounds and lower bounds. In terms of the number $U$ of non-linear units, we prove a tight bound $\Theta(W U)$ on the VC-Dimension. All of these bounds generalize to arbitrary piecewise linear activation functions, and also hold for the pseudoDimensions of these function classes. Combined with previous results, this gives an intriguing range of dependencies of the VC-Dimension on depth for networks with different non-linearities: there is no dependence for piecewise-constant, linear dependence for piecewise-linear, and no more than quadratic dependence for general piecewise-polynomial.
-
almost linear VC Dimension bounds for piecewise polynomial networks
Neural Information Processing Systems, 1998Co-Authors: Peter L Bartlett, Vitaly Maiorov, Ron MeirAbstract:We compute upper and lower bounds on the VC Dimension and pseudoDimension of feedforward neural networks composed of piecewise polynomial activation functions. We show that if the number of layers is fixed, then the VC Dimension and pseudo-Dimension grow as W log W, where W is the number of parameters in the network. This result stands in opposition to the case where the number of layers is unbounded, in which case the VC Dimension and pseudo-Dimension grow as W2 . We combine our results with recently established approximation error rates and determine error bounds for the problem of regression estimation by piecewise polynomial networks with unbounded weights.
Ron Meir - One of the best experts on this subject based on the ideXlab platform.
-
almost linear VC Dimension bounds for piecewise polynomial networks
Neural Information Processing Systems, 1998Co-Authors: Peter L Bartlett, Vitaly Maiorov, Ron MeirAbstract:We compute upper and lower bounds on the VC Dimension and pseudoDimension of feedforward neural networks composed of piecewise polynomial activation functions. We show that if the number of layers is fixed, then the VC Dimension and pseudo-Dimension grow as W log W, where W is the number of parameters in the network. This result stands in opposition to the case where the number of layers is unbounded, in which case the VC Dimension and pseudo-Dimension grow as W2 . We combine our results with recently established approximation error rates and determine error bounds for the problem of regression estimation by piecewise polynomial networks with unbounded weights.
Laurent Viennot - One of the best experts on this subject based on the ideXlab platform.
-
diameter computation on h minor free graphs and graphs of bounded distance VC Dimension
Symposium on Discrete Algorithms, 2020Co-Authors: Guillaume Ducoffe, Michel Habib, Laurent ViennotAbstract:Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted graphs cannot be computed in truly subquadratic time. Nevertheless there are several graph classes for which this can be done such as bounded-treewidth graphs, interval graphs and planar graphs, to name a few. We propose to study unweighted graphs of constant distance VC-Dimension as a broad generalization of many such classes - where the distance VC-Dimension of a graph G is defined as the VC-Dimension of its ball hypergraph: whose hyper-edges are the balls of all possible radii and centers in G. In particular for any fixed H, the class of H-minor free graphs has distance VC-Dimension at most |V(H)| − 1. • Our first main result is a Monte Carlo algorithm that on graphs of distance VC-Dimension at most d, for any fixed k, either computes the diameter or concludes that it is larger than k in time [MATH HERE], where ed ∈ (0; 1) only depends on d. We thus obtain a truly subquadratic-time parameterized algorithm for computing the diameter on such graphs. • Then as a byproduct of our approach, we get the first truly subquadratic-time randomized algorithm for constant diameter computation on all the nowhere dense graph classes. The latter classes include all proper minor-closed graph classes, bounded-degree graphs and graphs of bounded expansion. • Finally we show how to remove the dependency on k for any graph class that excludes a fixed graph H as a minor. More generally, our techniques apply to any graph with constant distance VC-Dimension and polynomial expansion (or equivalently having strongly sublinear balanced separators). As a result for all such graphs one obtains a truly subquadratic-time randomized algorithm for computing their diameter. We note that all our results also hold for radius computation. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-Dimension. We show how to compute such paths efficiently by combining known algorithms for the stabbing number problem with a clever use of e-nets, region decomposition and other partition techniques.
-
diameter computation on h minor free graphs and graphs of bounded distance VC Dimension
arXiv: Data Structures and Algorithms, 2019Co-Authors: Guillaume Ducoffe, Michel Habib, Laurent ViennotAbstract:We propose to study unweighted graphs of constant distance VC-Dimension as a broad generalization of many graph classes for which we can compute the diameter in truly subquadratic-time. In particular for any fixed $H$, the class of $H$-minor free graphs has distance VC-Dimension at most $|V(H)|-1$. Our first main result is that on graphs of distance VC-Dimension at most $d$, for any fixed $k$ we can either compute the diameter or conclude that it is larger than $k$ in time $\tilde{\cal O}(k\cdot mn^{1-\varepsilon_d})$, where $\varepsilon_d \in (0;1)$ only depends on $d$. Then as a byproduct of our approach, we get the first truly subquadratic-time algorithm for constant diameter computation on all the nowhere dense graph classes. Finally, we show how to remove the dependency on $k$ for any graph class that excludes a fixed graph $H$ as a minor. More generally, our techniques apply to any graph with constant distance VC-Dimension and polynomial expansion. As a result for all such graphs one obtains a truly subquadratic-time algorithm for computing their diameter. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-Dimension. We show how to compute such paths efficiently by combining the best known approximation algorithms for the stabbing number problem with a clever use of $\varepsilon$-nets, region decomposition and other partition techniques.
Suk Andrew - One of the best experts on this subject based on the ideXlab platform.
-
Bounded VC-Dimension Implies the Schur-Erd?s Conjecture
LIPIcs - Leibniz International Proceedings in Informatics. 36th International Symposium on Computational Geometry (SoCG 2020), 2020Co-Authors: Fox Jacob, Suk AndrewAbstract:In 1916, Schur introduced the Ramsey number r(3;m), which is the minimum integer n > 1 such that for any m-coloring of the edges of the complete graph K_n, there is a monochromatic copy of K?. He showed that r(3;m) ? O(m!), and a simple construction demonstrates that r(3;m) ? 2^?(m). An old conjecture of Erd?s states that r(3;m) = 2^?(m). In this note, we prove the conjecture for m-colorings with bounded VC-Dimension, that is, for m-colorings with the property that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-Dimension
-
Erdős-Hajnal Conjecture for Graphs with Bounded VC-Dimension
'Springer Science and Business Media LLC', 2019Co-Authors: Fox Jacob, Pach János, Suk AndrewAbstract:The Vapnik-Chervonenkis Dimension (in short, VC-Dimension) of a graph is defined as the VC-Dimension of the set system induced by the neighborhoods of its vertices. We show that every n-vertex graph with bounded VC-Dimension contains a clique or an independent set of size at least e(logn)1-o(1). The dependence on the VC-Dimension is hidden in the o(1) term. This improves the general lower bound, eclogn, due to Erds and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erds-Hajnal conjecture, according to which one can always find a clique or an independent set of size at least e(logn). Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovasz-Szegedy and Alon-Fischer-Newman, which is called the ultra-strong regularity lemma for graphs with bounded VC-Dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be (1/epsilon)O(d), improving the original bound of (1/epsilon)O(d2) in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an O(nk)-time algorithm for finding a partition meeting the requirements. Finally, we establish tight bounds on Ramsey-Turan numbers for graphs with bounded VC-Dimension
-
Bounded VC-Dimension implies the Schur-Erdos conjecture
2019Co-Authors: Fox Jacob, Pach János, Suk AndrewAbstract:In 1916, Schur introduced the Ramsey number $r(3;m)$, which is the minimum integer $n$ such that for any $m$-coloring of the edges of the complete graph $K_n$, there is a monochromatic copy of $K_3$. He showed that $r(3;m) \leq O(m!)$, and a simple construction demonstrates that $r(3;m) \geq 2^{\Omega(m)}$. An old conjecture of Erd\H os states that $r(3;m) = 2^{\Theta(m)}$. In this note, we prove the conjecture for $m$-colorings with bounded VC-Dimension, that is, for $m$-colorings with the property that the set system $\mathcal{F}$ induced by the neighborhoods of the vertices with respect to each color class has bounded VC-Dimension
-
Erdos-Hajnal conjecture for graphs with bounded VC-Dimension
2017Co-Authors: Fox Jacob, Pach János, Suk AndrewAbstract:The Vapnik-Chervonenkis Dimension (in short, VC-Dimension) of a graph is defined as the VC-Dimension of the set system induced by the neighborhoods of its vertices. We show that every $n$-vertex graph with bounded VC-Dimension contains a clique or an independent set of size at least $e^{(\log n)^{1 - o(1)}}$. The dependence on the VC-Dimension is hidden in the $o(1)$ term. This improves the general lower bound, $e^{c\sqrt{\log n}}$, due to Erdos and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdos-Hajnal conjecture, according to which one can always find a clique or an independent set of size at least $e^{\Omega(\log n)}$. Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lov\'asz-Szegedy and Alon-Fischer-Newman, which is called the "ultra-strong regularity lemma" for graphs with bounded VC-Dimension. We extend this lemma to $k$-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be $(1/\varepsilon)^{O(d)}$, improving the original bound of $(1/\varepsilon)^{O(d^2)}$ in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an $O(n^k)$-time algorithm for finding a partition meeting the requirements. Finally, we establish tight bounds on Ramsey-Tur\'an numbers for graphs with bounded VC-Dimension
-
Erdos-hajnal conjecture for graphs with bounded VC-Dimension
Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2017Co-Authors: Fox Jacob, Pach János, Suk AndrewAbstract:The Vapnik-Chervonenkis Dimension (in short, VC-Dimension) of a graph is defined as the VC-Dimension of the set system induced by the neighborhoods of its vertices. We show that every n-vertex graph with bounded VC-Dimension contains a clique or an independent set of size at least e(log n)1-σ(1). The dependence on the VC-Dimension is hidden in the o(1) term. This improves the general lower bound, ec√log n due to Erdos and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdos-Hajnal conjecture, according to which one can always find a clique or an independent set of size at least eΩ(log n). Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovász-Szegedy and Alon-Fischer-Newman, which is called the "ultra-strong regularity lemma" for graphs with bounded VC-Dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be (1/ϵ)O(d) improving the original bound of (1/ϵ) O(d2) in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an O(nk)-time algorithm for finding a partition meeting the requirements in the k-uniform setting. © Jacob Fox, János Pach, and Andrew Suk