The Experts below are selected from a list of 312 Experts worldwide ranked by ideXlab platform
Rocco A Servedio - One of the best experts on this subject based on the ideXlab platform.
-
Improved Approximation of Linear Threshold Functions
computational complexity, 2012Co-Authors: Ilias Diakonikolas, Rocco A ServedioAbstract:We prove two main results on how arbitrary linear Threshold Functions $${f(x) = {\rm sign}(w \cdot x - \theta)}$$ over the n-dimensional Boolean hypercube can be approximated by simple Threshold Functions. Our first result shows that every n-variable Threshold Function f is $${\epsilon}$$ -close to a Threshold Function depending only on $${{\rm Inf}(f)^2 \cdot {\rm poly}(1/\epsilon)}$$ many variables, where $${{\rm Inf}(f)}$$ denotes the total influence or average sensitivity of f. This is an exponential sharpening of Friedgut's well-known theorem (Friedgut in Combinatorica 18(1):474---483, 1998), which states that every Boolean Function f is $${\epsilon}$$ -close to a Function depending only on $${2^{O({\rm Inf}(f)/\epsilon)}}$$ many variables, for the case of Threshold Functions. We complement this upper bound by showing that $${\Omega({\rm Inf}(f)^2 + 1/\epsilon^2)}$$ many variables are required for $${\epsilon}$$ -approximating Threshold Functions. Our second result is a proof that every n-variable Threshold Function is $${\epsilon}$$ -close to a Threshold Function with integer weights at most $${{\rm poly}(n) \cdot 2^{\tilde{O}(1/\epsilon^{2/3})}.}$$ This is an improvement, in the dependence on the error parameter $${\epsilon}$$ , on an earlier result of Servedio (Comput Complex 16(2):180---209, 2007) which gave a $${{\rm poly}(n) \cdot 2^{\tilde{O}(1/\epsilon^{2})}}$$ bound. Our improvement is obtained via a new proof technique that uses strong anti-concentration bounds from probability theory. The new technique also gives a simple and modular proof of the original result of Servedio (Comput Complex 16(2):180---209, 2007) and extends to give low-weight approximators for Threshold Functions under a range of probability distributions other than the uniform distribution.
-
Improved Approximation of Linear Threshold Functions
arXiv: Computational Complexity, 2009Co-Authors: Ilias Diakonikolas, Rocco A ServedioAbstract:We prove two main results on how arbitrary linear Threshold Functions $f(x) = \sign(w\cdot x - \theta)$ over the $n$-dimensional Boolean hypercube can be approximated by simple Threshold Functions. Our first result shows that every $n$-variable Threshold Function $f$ is $\eps$-close to a Threshold Function depending only on $\Inf(f)^2 \cdot \poly(1/\eps)$ many variables, where $\Inf(f)$ denotes the total influence or average sensitivity of $f.$ This is an exponential sharpening of Friedgut's well-known theorem \cite{Friedgut:98}, which states that every Boolean Function $f$ is $\eps$-close to a Function depending only on $2^{O(\Inf(f)/\eps)}$ many variables, for the case of Threshold Functions. We complement this upper bound by showing that $\Omega(\Inf(f)^2 + 1/\epsilon^2)$ many variables are required for $\epsilon$-approximating Threshold Functions. Our second result is a proof that every $n$-variable Threshold Function is $\eps$-close to a Threshold Function with integer weights at most $\poly(n) \cdot 2^{\tilde{O}(1/\eps^{2/3})}.$ This is a significant improvement, in the dependence on the error parameter $\eps$, on an earlier result of \cite{Servedio:07cc} which gave a $\poly(n) \cdot 2^{\tilde{O}(1/\eps^{2})}$ bound. Our improvement is obtained via a new proof technique that uses strong anti-concentration bounds from probability theory. The new technique also gives a simple and modular proof of the original \cite{Servedio:07cc} result, and extends to give low-weight approximators for Threshold Functions under a range of probability distributions beyond just the uniform distribution.
-
IEEE Conference on Computational Complexity - Improved Approximation of Linear Threshold Functions
2009 24th Annual IEEE Conference on Computational Complexity, 2009Co-Authors: Ilias Diakonikolas, Rocco A ServedioAbstract:We prove two main results on how arbitrary linear Threshold Functions $f(x) = \sign(w\cdot x - \theta)$ over the $n$-dimensional Boolean hypercube can be approximated by simple Threshold Functions. Our first result shows that every $n$-variable Threshold Function $f$ is $\eps$-close to a Threshold Function depending only on $\Inf(f)^2 \cdot \poly(1/\eps)$ many variables, where $\Inf(f)$ denotes the total influence or average sensitivity of $f.$ This is an exponential sharpening of Friedgut's well-known theorem \cite{Friedgut:98}, which states that every Boolean Function $f$ is $\eps$-close to a Function depending only on $2^{O(\Inf(f)/\eps)}$ many variables, for the case of Threshold Functions. We complement this upper bound by showing that $\Omega(\Inf(f)^2 + 1/\epsilon^2)$ many variables are required for $\epsilon$-approximating Threshold Functions. Our second result is a proof that every $n$-variable Threshold Function is $\eps$-close to a Threshold Function with integer weights at most $\poly(n) \cdot 2^{\tilde{O}(1/\eps^{2/3})}.$ This is a significant improvement, in the dependence on the error parameter $\eps$, on an earlier result of \cite{Servedio:07cc} which gave a $\poly(n) \cdot 2^{\tilde{O}(1/\eps^{2})}$ bound. Our improvement is obtained via a new proof technique that uses strong anti-concentration bounds from probability theory. The new technique also gives a simple and modular proof of the original \cite{Servedio:07cc} result, and extends to give low-weight approximators for Threshold Functions under a range of probability distributions beyond just the uniform distribution.
-
every linear Threshold Function has a low weight approximator
Computational Complexity, 2007Co-Authors: Rocco A ServedioAbstract:Given any linear Threshold Function f on n Boolean variables, we construct a linear Threshold Function g which disagrees with f on at most an ? fraction of inputs and has integer weights each of magnitude at most $${\sqrt{n}\cdot}2^{{\tilde{O}}(1/ \epsilon^{2})}$$ We show that the construction is optimal in terms of its dependence on n by proving a lower bound of $$\Omega(\sqrt{n})$$ on the weights required to approximate a particular linear Threshold Function. We give two applications. The first is a deterministic algorithm for approximately counting the fraction of satisfying assignments to an instance of the zero-one knapsack problem to within an additive ? ?. The algorithm runs in time polynomial in n (but exponential in $${1}/{\epsilon^{2}}$$ ). In our second application, we show that any linear Threshold Function f is specified to within error ? by estimates of its Chow parameters (degree 0 and 1 Fourier coefficients) which are accurate to within an additive $$\pm{1}/({n}\cdot 2^{{\tilde{O}}(1/ \epsilon^{2})})$$ . This is the first such accuracy bound which is inverse polynomial in n, and gives the first polynomial bound (in terms of n) on the number of examples required for learning linear Threshold Functions in the "restricted focus of attention" framework.
-
every linear Threshold Function has a low weight approximator
Conference on Computational Complexity, 2006Co-Authors: Rocco A ServedioAbstract:Given any linear Threshold Function f on n Boolean variables, we construct a linear Threshold Function g which disagrees with f on at most an epsiv fraction of inputs and has integer weights each of magnitude at most radicn middot 2Omacr(1/epsiv2). We show that the construction is optimal in terms of its dependence on n by proving a lower bound of Omega(radicn) on the weights required to approximate a particular linear Threshold Function. We give two applications. The first is a deterministic algorithm for approximately counting the fraction of satisfying assignments to an instance of the zero-one knapsack problem to within an additive plusmnepsiv. The algorithm runs in time polynomial in n (but exponential in 1/epsiv2). In our second application, we show that any linear Threshold Function f is specified to within error epsiv by estimates of its Chow parameters (degree 0 and 1 Fourier coefficients) which are accurate to within an additive error of plusmn1/(nmiddot2 Omacr(1/epsiv2). This is the first such accuracy bound which is inverse polynomial in n (previous work of Goldberg gave a 1/quasipoly(n) bound), and gives the first polynomial bound (in terms of n) on the number of examples required for learning linear Threshold Functions in the "restricted focus of attention" framework
Zeng Qin-ning - One of the best experts on this subject based on the ideXlab platform.
-
Heart Sound Signal De - noising Based on a New Wavelet Threshold Function
Computer Simulation, 2010Co-Authors: Zeng Qin-ningAbstract:Wavelet transform has the characteristics of multi-resolution analysis and time-frequency localization analysis and has been widely used for the de-noising of medicinal signal such as heart sound signal,but conventional wavelet Threshold Functions have some defects and influence the performance of de-noising.Through discussing the advantages and shortcomings of soft and hard Threshold Functions and several existing improved Threshold Functions,a new Threshold Function with two adjustable paramerers is introduced.It is easy to adjust and suitable for some kinds of mathematical disposal.What is more,it has a transition better adapted to continuity of natural signal.The simulation results for heart sound signal show that the new Threshold Function can suppress the noise effectively.In terms of SNR and RMSE,it is superior to Threshold Functions mentioned in this paper and has high practical value.
Dai Wen-zhan - One of the best experts on this subject based on the ideXlab platform.
-
Signal de-noising in wavelet based on new Threshold Function
Journal of Computer Applications, 2006Co-Authors: Dai Wen-zhanAbstract:A new Threshold Function based on the wavelet Threshold de-nosing was presented.It overcame the shortcoming of the hard Threshold with discontinuous Function and solved the problem of the permanent bias in soft Threshold Function.At the same time,the new Function didn't need to choose parameters.Simulation result indicates that the new Threshold Function is effective and predominant than other Threshold Functions.
Theodore W Berger - One of the best experts on this subject based on the ideXlab platform.
-
an algorithm for real time extraction of population epsp and population spike amplitudes from hippocampal field potential recordings
Journal of Neuroscience Methods, 2004Co-Authors: Ghassan Gholmieh, Spiros Courellis, Angelika Dimoka, Jack Wills, Jeff Lacoss, John J Granacki, V Z Marmarelis, Theodore W BergerAbstract:Abstract A new method is presented for extracting the amplitude of excitatory post synaptic potentials (EPSPs) and spikes in real time. It includes a low pass filter (LPF), a differentiator, a Threshold Function, and an intelligent integrator. It was applied to EPSP and population spike data recorded in the Dentate Gyrus and the CA1 hippocampus in vitro. The accuracy of the extraction algorithm was evaluated via the extraction normalized mean square error (eNMSE) and was found to be very high (eNMSE
Elena Zamaraeva - One of the best experts on this subject based on the ideXlab platform.
-
Asymptotics of the number of 2-Threshold Functions.
arXiv: Combinatorics, 2020Co-Authors: Elena Zamaraeva, Jovisa ZunicAbstract:A $k$-Threshold Function on a rectangular grid of size $m \times n$ is the conjunction of $k$ Threshold Functions on the same domain. In this paper, we focus on the case $k=2$ and show that the number of two-dimensional 2-Threshold Functions is~$\dfrac{25}{12\pi^4} m^4 n^4 + o(m^4n^4)$.
-
specifying a positive Threshold Function via extremal points
arXiv: Combinatorics, 2017Co-Authors: Vadim V Lozin, Igor Razgon, Victor Zamaraev, Elena Zamaraeva, Nikolai Yu ZolotykhAbstract:An extremal point of a positive Threshold Boolean Function $f$ is either a maximal zero or a minimal one. It is known that if $f$ depends on all its variables, then the set of its extremal points completely specifies $f$ within the universe of Threshold Functions. However, in some cases, $f$ can be specified by a smaller set. The minimum number of points in such a set is the specification number of $f$. It was shown in [S.-T. Hu. Threshold Logic, 1965] that the specification number of a Threshold Function of $n$ variables is at least $n+1$. In [M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying Boolean Functions by labelled examples. Discrete Applied Mathematics, 1995] it was proved that this bound is attained for nested Functions and conjectured that for all other Threshold Functions the specification number is strictly greater than $n+1$. In the present paper, we resolve this conjecture negatively by exhibiting Threshold Boolean Functions of $n$ variables, which are non-nested and for which the specification number is $n+1$. On the other hand, we show that the set of extremal points satisfies the statement of the conjecture, i.e., a positive Threshold Boolean Function depending on all its $n$ variables has $n+1$ extremal points if and only if it is nested. To prove this, we reveal an underlying structure of the set of extremal points.
-
On teaching sets of k-Threshold Functions
Information and Computation, 2016Co-Authors: Elena ZamaraevaAbstract:In this paper we study teaching sets of k-Threshold Functions, i.e. Functions that can be represented as a conjunction of k Threshold Functions. We reveal a connection between essential points of k Threshold Functions and essential points of the corresponding k-Threshold Function. We show that in two-dimensional case the number of minimal teaching sets of a 2-Threshold Function can grow as ź ( n 2 ) . We also consider the class of polytopes with vertices in the d-dimensional cube. Each polytope from this class can be defined by a k-Threshold Function for some k. We prove that such a polytope has a unique minimal teaching set which is equal to the set of its essential points. For d = 2 we describe structure of the minimal teaching set of a polytope and show that its cardinality is either ź ( n 2 ) or O ( n ) and depends on the perimeter and the minimum angle of the polytope.
-
On teaching sets of k-Threshold Functions
arXiv: Combinatorics, 2015Co-Authors: Elena ZamaraevaAbstract:Let $f$ be a $\{0,1\}$-valued Function over an integer $d$-dimensional cube $\{0,1,\dots,n-1\}^d$, for $n \geq 2$ and $d \geq 1$. The Function $f$ is called Threshold if there exists a hyperplane which separates $0$-valued points from $1$-valued points. Let $C$ be a class of Functions and $f \in C$. A point $x$ is essential for the Function $f$ with respect to $C$ if there exists a Function $g \in C$ such that $x$ is a unique point on which $f$ differs from $g$. A set of points $X$ is called teaching for the Function $f$ with respect to $C$ if no Function in $C \setminus \{f\}$ agrees with $f$ on $X$. It is known that any Threshold Function has a unique minimal teaching set, which coincides with the set of its essential points. In this paper we study teaching sets of $k$-Threshold Functions, i.e. Functions that can be represented as a conjunction of $k$ Threshold Functions. We reveal a connection between essential points of $k$ Threshold Functions and essential points of the corresponding $k$-Threshold Function. We note that, in general, a $k$-Threshold Function is not specified by its essential points and can have more than one minimal teaching set. We show that for $d=2$ the number of minimal teaching sets for a 2-Threshold Function can grow as $\Omega(n^2)$. We also consider the class of polytopes with vertices in the $d$-dimensional cube. Each polytope from this class can be defined by a $k$-Threshold Function for some $k$. In terms of $k$-Threshold Functions we prove that a polytope with vertices in the $d$-dimensional cube has a unique minimal teaching set which is equal to the set of its essential points. For $d=2$ we describe structure of the minimal teaching set of a polytope and show that cardinality of this set is either $\Theta(n^2)$ or $O(n)$ and depends on the perimeter and the minimum angle of the polytope.
