检索结果-内蒙古大学图书馆

linear threshold functions in decision lists, decision trees, and depth-2 circuits

INFORMATION PROCESSING LETTERS 2024年 183卷

作者： Dahiya, Yogesh Vignesh, K. Mahajan, Meena Sreenivasaiah, Karteek CI Homi Bhabha Natl Inst Inst Math Sci CIT Campus Chennai 600113 Tamil Nadu India Indian Inst Technol Hyderabad Hyderabad 502285 Telangana India

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF o LTF. An intermediate construct is polynomial-size decision lists that query a conjunction of a constant number of linear threshold functions (LTFs);we show that these are equivalent to polynomial-size exact linear decision lists (ELDLs) i.e. decision lists querying exact threshold functions (ELTFs).& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Computational complexity linear threshold functions Decision trees Depth-2 circuits Tree rank

来源：评论

学校读者我要写书评

暂无评论

Monotone Boolean formulas can approximate monotone linear threshold functions

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期142卷 181-187页

作者： Servedio, RA Columbia Univ Dept Comp Sci New York NY 10027 USA

We show that any monotone linear threshold function on n Boolean variables can be approximated to within any constant accuracy by a monotone Boolean formula of poly(n) size. (C) 2004 Elsevier B.V. All rights reserved.

关键词： linear threshold functions Boolean formulas monotone computation

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm for learning noisy linear threshold functions

引用

ALGORITHMICA 1998年第1-2期22卷 35-52页

作者： Blum, A Frieze, A Kannan, R Vempala, S Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA

In this paper we consider the problem of learning a linear threshold function (a half-space in n dimensions, also called a "perceptron"). Methods for solving this problem generally fall into two categories. In the absence of noise, this problem can be formulated as a linear Program and solved in polynomial time with the Ellipsoid Algorithm or Interior Point methods. Alternatively, simple greedy algorithms such as the Perceptron Algorithm are often used in practice and have certain provable noise-tolerance properties;but their running time depends on a separation parameter, which quantifies the amount of "wiggle room" available for a solution, and can be exponential in the description length of the input. In this paper we show how simple greedy methods can be used to find weak hypotheses (hypotheses that correctly classify noticeably more than half of the examples) in polynomial time, without dependence on any separation parameter. Suitably combining these hypotheses results in a polynomial-time algorithm for learning linear threshold functions in the PAC model in the presence of random classification noise. (Also, a polynomial-time algorithm for learning linear threshold functions in the Statistical Query model of Kearns.) Our algorithm is based on a new method for removing outliers in data. Specifically, for any set S of points in R-n, each given to b bits of precision, we show that one can remove only a small fraction of S so that in the remaining set T, for every vector v max(x epsilon T) (v . x)(2) less than or equal to poly(n, b)E-x epsilon T (v . x)(2);i.e., for any hyperplane through the origin, the maximum distance (squared) from a point in T to the plane is at most polynomially larger than the average. After removing these outliers, we are able to show that a modified version of the Perceptron Algorithm finds a weak hypothesis in polynomial time, even in the presence of random classification noise.

关键词： computational learning theory linear threshold functions perceptron algorithm learning with noise

来源：评论

学校读者我要写书评

暂无评论

On the Approximation Resistance of Balanced linear threshold functions 2019

On the Approximation Resistance of Balanced Linear Threshold...

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Potechin, Aaron Univ Chicago Chicago IL 60637 USA

In this paper, we show that there exists a balanced linear threshold function (LTF) which is unique games hard to approximate, refuting a conjecture of Austrin, Benabbas, and Magen. We also show that the almost monarc... 详细信息

ISBN: (纸本)9781450367059

关键词： constraint satisfaction problems hardness of approximation linear threshold functions

来源：评论

学校读者我要写书评

暂无评论

Polynomial regression under arbitrary product distributions

引用

MACHINE LEARNING 2010年第2-3期80卷 273-294页

作者： Blais, Eric O'Donnell, Ryan Wimmer, Karl Carnegie Mellon Univ Pittsburgh PA 15213 USA Duquesne Univ Pittsburgh PA 15219 USA

In recent work, Kalai, Klivans, Mansour, and Servedio (2005) studied a variant of the "Low-Degree (Fourier) Algorithm" for learning under the uniform probability distribution on {0, 1}(n). They showed that the L-1 polynomial regression algorithm yields agnostic (tolerant to arbitrary noise) learning algorithms with respect to the class of threshold functions-under certain restricted instance distributions, including uniform on {0, 1}(n) and Gaussian on R-n. In this work we show how all learning results based on the Low-Degree Algorithm can be generalized to give almost identical agnostic guarantees under arbitrary product distributions on instance spaces X-1 x ... x X-n. We also extend these results to learning under mixtures of product distributions. The main technical innovation is the use of (Hoeffding) orthogonal decomposition and the extension of the "noise sensitivity method" to arbitrary product spaces. In particular, we give a very simple proof that threshold functions over arbitrary product spaces have d-noise sensitivity O(root delta), resolving an open problem suggested by Peres (2004).

关键词： Agnostic learning Polynomial regression linear threshold functions Noise sensitivity

来源：评论

学校读者我要写书评

暂无评论

EXPLICIT DIMENSION REDUCTION AND ITS APPLICATIONS

引用

SIAM JOURNAL ON COMPUTING 2012年第1期41卷 219-249页

作者： Karnin, Zohar S. Rabani, Yuval Shpilka, Amir Technion Israel Inst Technol Fac Comp Sci IL-32000 Haifa Israel Hebrew Univ Jerusalem Rachel & Selim Benin Sch Comp Sci & Engn IL-91904 Jerusalem Israel Microsoft Res Cambridge MA 02142 USA

We construct a small set of explicit linear transformations mapping R-n to R-t, where t = O(log(gamma(-1))epsilon(-2)), such that the L-2 norm of any vector in R-n is distorted by at most 1 +/- epsilon in at least a fraction of 1 - gamma of the transformations in the set. Albeit the tradeoff between the size of the set and the success probability is suboptimal compared with probabilistic arguments, we nevertheless are able to apply our construction to a number of problems. In particular, we use it to construct an epsilon-sample (or pseudorandom generator) for linear threshold functions on Sn-1 for epsilon = o(1). We also use it to construct an epsilon-sample for spherical digons in Sn-1 for epsilon = o(1). This construction leads to an efficient oblivious derandomization of the Goemans-Williamson Max-Cut algorithm and similar approximation algorithms (i.e., we construct a small set of hyperplanes such that for any instance we can choose one of them to generate a good solution). Our technique for constructing an epsilon-sample for linear threshold functions on the sphere is considerably different than previous techniques that rely on k-wise independent sample spaces.

关键词： dimension reduction pseudorandom generator linear threshold functions Max-Cut Johnson Lindenstrauss digons

来源：评论

学校读者我要写书评

暂无评论

A ROBUST KHINTCHINE INEQUALITY, AND ALGORITHMS FOR COMPUTING OPTIMAL CONSTANTS IN FOURIER ANALYSIS AND HIGH-DIMENSIONAL GEOMETRY

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2016年第2期30卷 1058-1094页

作者： De, Anindya Diakonikolas, Ilias Servedio, Rocco A. Univ Calif Berkeley Berkeley CA 94720 USA Univ Edinburgh Edinburgh EH8 9YL Midlothian Scotland Columbia Univ Dept Comp Sci New York NY 10027 USA

This paper makes two contributions towards determining some well-studied optimal constants in Fourier analysis of Boolean functions and high-dimensional geometry. It has been known since 1994 [C. Gotsman and N. Linial, Combinatorica, 14 (1994), pp. 35-50] that every linear threshold function (LTF) has a squared Fourier mass of at least 1/2 on its degree-0 and degree-1 coefficients. Let the minimum such Fourier mass be W-<= 1[LTF], where the minimum is taken over all n-variable LTFs and all n >= 0. Benjamini, Kalai, and Schramm [Publ. Math. Inst. Hautes Etudes Sci., 90 (1999), pp. 5-43] conjectured that the true value of W-<= 1[LTF] is 2/pi. We make progress on this conjecture by proving that W-<= 1[LTF] >= 1/2 + c for some absolute constant c > 0. The key ingredient in our proof is a "robust" version of the well-known Khintchine inequality in functional analysis, which we believe may be of independent interest. Let W-<= 1[LTFn] denote the minimum squared Fourier mass on the degree-0 and degree-1 coefficients of any n-variable LTF. We prove that for every eta > 0, there is a value K = K(eta) = poly(1/eta)such that W-<= 1[LTF] <= W-<= 1[LTFK] <= W-< 1[LTF] + eta. This easily yields an algorithm that runs in time 2(poly(1/eta)) and determines the value of W= 1[LTF] up to an additive error of +/-eta. We give an analogous structural result, and a similar 2(poly(1/eta))-time algorithm, to determine Tomaszewski's constant to within an additive error of +/-eta;this is the minimum (over all origin-centered hyperplanes H) fraction of points in {-1, 1}(n) that lie within a Euclidean distance 1 of H. Tomaszewski's constant is conjectured to be 1/2;lower bounds on it have been given by Holzman and Kleitman [Combinatorica, 12 (1992), pp. 303-316] and independently by Ben-Tal, Nemirovski, and Roos [SIAM J. Optim., 13 (2002), pp. 535-560]. Our structural results combine tools from anticoncentration of sums of independent random variables, Fourier analysis, and Hermite analysis of L

关键词： linear threshold functions halfspaces hyperplanes Khintchine inequality Fourier analysis

来源：评论

学校读者我要写书评

暂无评论

PAC analogues of perceptron and winnow via boosting the margin

引用

MACHINE LEARNING 2002年第2-3期47卷 133-151页

作者： Servedio, R Harvard Univ Div Engn & Appl Sci Cambridge MA 02138 USA

We describe a novel family of PAC model algorithms for learning linear threshold functions. The new algorithms work by boosting a simple weak learner and exhibit sample complexity bounds remarkably similar to those of known online algorithms such as Perceptron and Winnow, thus suggesting that these well-studied online algorithms in some sense correspond to instances of boosting. We show that the new algorithms can be viewed as natural PAC analogues of the online p-norm algorithms which have recently been studied by Grove, Littlestone, and Schuurmans (1997, Proceedings of the Tenth Annual Conference on Computational Learning Theory (pp. 171-183) and Gentile and Littlestone (1999, Proceedings of the Twelfth Annual Conference on Computational Learning Theory (pp. 1-11). As special cases of the algorithm, by taking p = 2 and p = infinity we obtain natural boosting-based PAC analogues of Perceptron and Winnow respectively. The p = infinity case of our algorithm can also be viewed as a generalization (with an improved sample complexity bound) of Jackson and Craven's PAC-model boosting-based algorithm for learning "sparse perceptrons" (Jackson & Craven, 1996, Advances in neural information processing systems 8, MIT Press). The analysis of the generalization error of the new algorithms relies on techniques from the theory of large margin classification.

关键词： probably approximately correct learning boosting linear threshold functions

来源：评论

学校读者我要写书评

暂无评论

ON THE WEIGHT OF HALFSPACES OVER HAMMING BALLS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2014年第3期28卷 1035-1061页

作者： Long, Philip M. Servedio, Rocco A. Google Mountain View CA 94043 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

For S subset of {0, 1}(n), a Boolean function f : S -> {-1, 1} is a halfspace over S if there exist w is an element of R-n and theta is an element of R such that f(x) = sign(w . x - theta) for all x is an element of S. We give bounds on the size of integer weights w(1),..., w(n) is an element of Z that are required to represent halfspaces over Hamming balls S = {x is an element of {0, 1}(n) : x(1) + ... + x(n) <= k}. Such weight bounds for halfspaces over Hamming balls have immediate consequences for the performance of learning algorithms in the common scenario of learning from very high-dimensional categorical examples which are such that only a small number of features are active in each example. We give upper and lower bounds on weight both for exact representation (when sign(w . x - theta) must equal f(x) for every x is an element of S) and for epsilon-approximate representation (when sign(w . x - theta) may disagree with f(x) for up to an e fraction of points x. S). Our results show that extremal bounds for exact representation are qualitatively rather similar whether the domain is all of {0, 1}(n) or the Hamming ball {0, 1}(<= k)(n), but extremal bounds for approximate representation are qualitatively very different between these two domains.

关键词： linear threshold functions halfspaces Boolean functions Boolean hypercube

来源：评论

学校读者我要写书评

暂无评论

The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant

引用

ARTIFICIAL INTELLIGENCE 1997年第1-2期97卷 325-343页

作者： Kivinen, J Warmuth, MK Auer, P Graz Univ Technol Inst Theoret Comp Sci A-8010 Graz Austria Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Univ Calif Santa Cruz Santa Cruz CA 95064 USA

We give an adversary strategy that forces the Perceptron algorithm to make Omega(kN) mistakes in learning monotone disjunctions over N variables with at most k literals. In contrast, Littlestone's algorithm Winnow makes at most O(klog N) mistakes for the same problem. Both algorithms use thresholded linear functions as their hypotheses. However, Winnow does multiplicative updates to its weight vector instead of the additive updates of the Perceptron algorithm, In general, we call an algorithm additive if its weight vector is always a sum of a fixed initial weight vector and some linear combination of already seen instances. Thus, the Perceptron algorithm is an example of an additive algorithm, We show that an adversary can force any additive algorithm to make (N + k - 1)/2 mistakes in learning a monotone disjunction of at most k literals. Simple experiments show that for k much less than N, Winnow clearly outperforms the Perceptron algorithm also on nonadversarial random data. (C) 1997 Elsevier Science B.V.

关键词： linear threshold functions perceptron algorithm relevant variables multiplicative updates mistake bounds

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：