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

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

来源：评论

学校读者我要写书评

暂无评论

Properties of Boolean networks and methods for their tests

引用

EURASIP JOURNAL ON BIOINFORMATICS AND SYSTEMS BIOLOGY 2013年第1期2013卷 1-1页

作者： Klotz, Johannes Georg Feuer, Ronny Sawodny, Oliver Bossert, Martin Ederer, Michael Schober, Steffen Univ Ulm Inst Commun Engn Albert Einstein Allee 43 D-89081 Ulm Germany Univ Stuttgart Inst Syst Dynam D-70569 Stuttgart Germany

Transcriptional regulation networks are often modeled as Boolean networks. We discuss certain properties of Boolean functions (BFs), which are considered as important in such networks, namely, membership to the classes of unate or canalizing functions. Of further interest is the average sensitivity (AS) of functions. In this article, we discuss several algorithms to test the properties of interest. To test canalizing properties of functions, we apply spectral techniques, which can also be used to characterize the AS of functions as well as the influences of variables in unate BFs. Further, we provide and review upper and lower bounds on the AS of unate BFs based on the spectral representation. Finally, we apply these methods to a transcriptional regulation network of Escherichia coli, which controls central parts of the E. coli metabolism. We find that all functions are unate. Also the analysis of the AS of the network reveals an exceptional robustness against transient fluctuations of the binary variables.(a)

关键词： Regulatory Boolean networks Boolean networks linear threshold functions Unate functions Canalizing function Sensitivity Average sensitivity Restricted functions Escherichia coli

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Active Property Testing

Active Property Testing

引用

IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

作者： Balcan, Maria-Florina Blais, Eric Blum, Avrim Yang, Liu Georgia Inst Technol Sch Comp Sci Atlanta GA 30332 USA Carnegie Mellon Univ Pittsburgh Sch Comp Sci Pittsburgh PA USA

ISBN: (纸本)9781467343831

One motivation for property testing of boolean functions is the idea that testing can provide a fast preprocessing step before learning. However, in most machine learning applications, it is not possible to request for labels of arbitrary examples constructed by an algorithm. Instead, the dominant query paradigm in applied machine learning, called active learning, is one where the algorithm may query for labels, but only on points in a given (polynomial-sized) unlabeled sample, drawn from some underlying distribution D. In this work, we bring this well-studied model to the domain of testing. We develop both general results for this active testing model as well as efficient testing algorithms for several important properties for learning, demonstrating that testing can still yield substantial benefits in this restricted setting. For example, we show that testing unions of d intervals can be done with O(1) label requests in our setting, whereas it is known to require Omega(d) labeled examples for learning (and Omega(root d) for passive testing [22] where the algorithm must pay for every example drawn from D). In fact, our results for testing unions of intervals also yield improvements on prior work in both the classic query model (where any point in the domain can be queried) and the passive testing model as well. For the problem of testing linear separators in R-n over the Gaussian distribution, we show that both active and passive testing can be done with O(root n) queries, substantially less than the Omega(n) needed for learning, with near-matching lower bounds. We also present a general combination result in this model for building testable properties out of others, which we then use to provide testers for a number of assumptions used in semi-supervised learning. In addition to the above results, we also develop a general notion of the testing dimension of a given property with respect to a given distribution, that we show characterizes (up to constant factors) th

关键词： Property testing Active learning Boolean functions linear threshold functions Unions of intervals

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

TESTING HALFSPACES

引用

SIAM JOURNAL ON COMPUTING 2010年第5期39卷 2004-2047页

作者： Matulef, Kevin O'Donnell, Ryan Rubinfeld, Ronitt Servedio, Rocco A. MIT Dept Math Cambridge MA 02142 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA MIT CSAIL Cambridge MA 02139 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e., a function of the form f(x) = sgn(w . x - theta). We consider halfspaces over the continuous domain R-n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}(n) (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are epsilon-far from any halfspace using only poly(1/epsilon) queries, independent of the dimension n. Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: The first gives an exact relationship between the expected value of a halfspace f and the sum of the squares of f's degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube {-1, 1}(n) (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over {-1, 1}(n) poses significant additional complications and requires other ingredients. These include "cross-consistency" versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds;new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces;and algorithmic techniques from recent work on testing juntas [E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pp. 103-112].

关键词： Fourier analysis halfspaces linear threshold functions property testing

来源：评论

学校读者我要写书评

暂无评论

Halfspace matrices

引用

COMPUTATIONAL COMPLEXITY 2008年第2期17卷 149-178页

作者： Sherstov, Alexander A. Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

We introduce the notion of a halfspace matrix, which is a sign matrix A with rows indexed by linear threshold functions f, columns indexed by inputs x is an element of {-1, 1}(n), and the entries given by A(f,x) = f (x). We use halfspace matrices to solve the following problems. In communication complexity, we exhibit a Boolean function f with discrepancy Omega(1/n(4)) under every product distribution but O(root n/2(n/4)) under a certain non-product distribution. This partially solves an open problem of Kushilevitz and Nisan (1997). In learning theory, we give a short and simple proof that the statistical-query (SQ) dimension of halfspaces in n dimensions is less than 2(n + 1)(2) under all distributions. This improves on the n(O(1)) estimate from the fundamental paper of Blum et al. (1998). We show that estimating the SQ dimension of natural classes of Boolean functions can resolve major open problems in complexity theory, such as separating PSPACE(cc) and PHcc. Finally, we construct a matrix A is an element of {-1, 1}(NxNlog N) with dimension complexity logN but margin complexity Omega(N-1/4/root log N). This gap is an exponential improvement over previous work. We prove several other relationships among the complexity measures of sign matrices, complementing work by Linial et al. (2006, 2007). Keywords. linear threshold functions, communication complexity, complexity measures of sign matrices, complexity of learning.

关键词： linear threshold functions communication complexity complexity measures of sign matrices complexity of learning

来源：评论

学校读者我要写书评

暂无评论

Halfspace matrices

Halfspace matrices

引用

22nd Annual IEEE Conference on Computational Complexity

作者： Sherstov, Alexander A. Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

ISBN: (纸本)0769527809

关键词： linear threshold functions communication complexity complexity measures of sign matrices complexity of learning

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Every linear threshold function has a low-weight approximator

引用

COMPUTATIONAL COMPLEXITY 2007年第2期16卷 180-209页

作者： Servedio, Rocco A. Columbia Univ Dept Comp Sci New York NY 10027 USA

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 epsilon fraction of inputs and has integer weights each of magnitude at most root n . 2((O) over tilde (1/epsilon 2)). We show that the construction is optimal in terms of its dependence on n by proving a lower bound of Omega(root 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 +/-epsilon. 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 epsilon by estimates of its Chow parameters (degree 0 and 1 Fourier coefficients) which are accurate to within an additive +/- 1/(n . 2((O) over tilde (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.

关键词： Boolean functions linear threshold functions Chow parameters computational learning theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：