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

On the Size and Width of the Decoder of a Boolean threshold Autoencoder

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2025年第2期36卷 3855-3862页

作者： Akutsu, Tatsuya Melkman, Avraham A. Kyoto Univ Bioinformat Ctr Inst Chem Res Kyoto 6110011 Japan Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

In this brief paper, we study the size and width of autoencoders consisting of Boolean threshold functions, where an autoencoder is a layered neural network whose structure can be viewed as consisting of an encoder, which compresses an input vector to a lower dimensional vector, and a decoder which transforms the low-dimensional vector back to the original input vector exactly (or approximately). We focus on the decoder part and show that Omega((Dn/d)(1/2)) and O(root Dn) nodes are required to transform n vectors in d-dimensional binary space to D-dimensional binary space. We also show that the width can be reduced if we allow small errors, where the error is defined as the average of the Hamming distance between each vector input to the encoder part and the resulting vector output by the decoder.

关键词： Autoencoders Boolean functions neural networks threshold functions

来源：评论

学校读者我要写书评

暂无评论

On the complexity of monotone circuits for threshold symmetric Boolean functions

引用

DISCRETE MATHEMATICS AND APPLICATIONS 2021年第5期31卷 345-366页

作者： Sergeev, Igor S. FSUE RDI Kvant Moscow Russia

The complexity of implementation of a threshold symmetric n-place Boolean function with threshold k = O(1) via circuits over the basis {boolean OR, boolean AND} is shown not to exceed 2 log(2) k . n + o(n). Moreover, the complexity of a threshold-2 function is proved to be 2n + Theta(root n), and the complexity of a threshold-3 function is shown to be 3n + O(log n), the corresponding lower bounds are put forward.

关键词： monotone circuits complexity symmetric Boolean functions threshold functions

来源：评论

学校读者我要写书评

暂无评论

Bounds on the Number of Pseudothreshold functions

引用

IEEE Transactions on Computers 1971年第12期C-20卷 1602-1605页

作者： Baugh, C.R. Department of Computer Science University of Illinois Urbana Ill United States

Upper and lower bounds are derived for the number of pseudothreshold functions of n variables. (Pseudothershold logic is a generalization of threshold logic.) It is shown that a lower bound on the number of pseudothreshold functions P(n) of exactly n variables realized by zero-free structures is The number of pseudothreshold functions Q(n) of n variables realized by nontrivial structures is bounded by It is also proven that is a lower bound on the number of positive functions of exactly n variables. © 1971, IEEE. All rights reserved.

关键词： Bounds positive functions pseudothreshold functions separable functions threshold functions threshold logic

来源：评论

学校读者我要写书评

暂无评论

Upper bounds on Fourier entropy

引用

THEORETICAL COMPUTER SCIENCE 2016年 654卷 92-112页

作者： Chakraborty, Sourav Kulkarni, Raghav Lokam, Satyanarayana V. Saurabh, Nitin Chennai Math Inst Madras Tamil Nadu India Ctr Quantum Technol Singapore Singapore Microsoft Res India Bangalore Karnataka India Inst Math Sci Madras Tamil Nadu India

Given a function f : (0,1}(n) -> {+1, -1), its Fourier Entropy is defined to be - Sigma(s) (f) over cap (S)(2) log (f) over cap (S)(2), where (f) over cap denotes the Fourier transform of f. In the analysis of Boolean functions, an outstanding open question is a conjecture of Friedgut and Kalai, 1996 [3], called the Fourier Entropy Influence (FEI) Conjecture, asserting that the Fourier Entropy of any Boolean function f is bounded above, up to a constant factor, by the total influence (= average sensitivity) of f. In this paper we give several upper bounds on the Fourier Entropy. We first give upper bounds on the Fourier Entropy of Boolean functions in terms of several complexity measures that are known to be bigger than the influence. These complexity measures include, among others, the logarithm of the number of leaves and the average depth of a parity decision tree. We then show that for the class of Linear threshold functions (LTF), the Fourier Entropy is O(root n). It is known that the average sensitivity for the class of LTF is Theta(root n). We also establish a bound of O-d(n(1-1/4d+6)) for general degree-d polynomial threshold functions. Our proof is based on a new upper bound on the derivative of noise sensitivity. Next we proceed to show that the FEI Conjecture holds for read-once formulas that use AND, OR, XOR, and NOT gates. The last result is independent of a result due to O'Donnell and Tan [1] for read-once formulas with arbitrary gates of bounded fan-in, but our proof is completely elementary and very different from theirs. Finally, we give a general bound involving the first and second moments of sensitivities of a function (average sensitivity being the first moment), which holds for real-valued functions as well. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Boolean functions Fourier entropy Noise sensitivity Influence Read-once formulas Decision trees threshold functions

来源：评论

学校读者我要写书评

暂无评论

A bound on the precision required to estimate a Boolean perceptron from its average satisfying assignment

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2006年第2期20卷 328-343页

作者： Goldberg, Paul W. Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

A Boolean perceptron is a linear threshold function over the discrete Boolean domain {0, 1}(n). That is, it maps any binary vector to 0 or 1, depending on whether the vector's components satisfy some linear inequality. In 1961, Chow showed that any Boolean perceptron is determined by the average or "center of gravity" of its "true" vectors ( those that are mapped to 1), together with the total number of true vectors. Moreover, these quantities distinguish the function from any other Boolean function, not just from other Boolean perceptrons. In this paper we go further, by identifying a lower bound on the Euclidean distance between the average satisfying assignment of a Boolean perceptron and the average satisfying assignment of a Boolean function that disagrees with that Boolean perceptron on a fraction epsilon of the input vectors. The distance between the two means is shown to be at least (epsilon/n)(O( log(n/epsilon) log(1/epsilon))). This is motivated by the statistical question of whether an empirical estimate of this average allows us to recover a good approximation to the perceptron. Our result provides a mildly superpolynomial upper bound on the growth rate of the sample size required to learn Boolean perceptrons in the " restricted focus of attention" setting. In the process we also find some interesting geometrical properties of the vertices of the unit hypercube.

关键词： Boolean functions threshold functions geometry inductive learning

来源：评论

学校读者我要写书评

暂无评论

Dual-tree complex wavelet transform technique-based optimal threshold tuning system to deliver denoised ECG signal

引用

TRANSACTIONS OF THE INSTITUTE OF MEASUREMENT AND CONTROL 2020年第4期42卷 854-869页

作者： Prashar, Navdeep Sood, Meenakshi Jain, Shruti Bahra Univ Dept Elect & Commun Engn Solan 173234 Himachal Prades India Jaypee Univ Informat Technol Dept Elect & Commun Engn Waknaghat Himachal Prades India

The primary output for any health monitoring system that offers telecardiology services is the recovery of the electrocardiographic (ECG) signal from the noised signal. The mechanized investigation of the ECG signal is the most inspiring challenge for accurate detection of cardiac disease. This could be accomplished by eliminating the various noises from the acquired signal. In this paper, a noise reduction approach employing DTCWT is executed on an ECG signal by proposing a noise estimator along with a detailed assessment of the effect of the choice of the threshold value, threshold algorithm and distribution function. The thresholding technique is executed by varying the threshold value (gamma) and its function (f(n)) applied to the proposed estimator (alpha*). The proposed estimator is scaled by 2(n) factor to study its impact on performance metrics and the nature of the reconstructed signal utilizing different distribution functions. The best combination of threshold function with threshold value selection has been chosen in this work from eight different sets of threshold value selection rules along with six distinct threshold functions. The experimental results show that the proposed noise reduction approach using a universal modified threshold level-dependent threshold with non-negative garrote threshold function for normal distribution with n = 3 delivers 80.72dB SNR with a subsequent reduction in MSE and PRD as compared with other standard techniques. An elaborate empirical analysis for selecting the distribution function for obtaining the best possible threshold function and technique is the prime objective and novelty of this research work.

关键词： threshold functions threshold values noise estimator distribution functions signal to noise ratio

来源：评论

学校读者我要写书评

暂无评论

Combining the perceptron algorithm with logarithmic simulated annealing

引用

NEURAL PROCESSING LETTERS 2001年第1期14卷 75-83页

作者： Albrecht, A Wong, CK Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule c(k)=Gamma /ln(k+2), where Gamma is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials w(1).x(1)(a+)...+w(n).x(n)(an)greater than or equal to theta, we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For n=256,..., 1024 and a(i)=3,..., 7, the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter Gamma was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.

关键词： cooling schedules neural networks perceptron algorithm simulated annealing threshold functions

来源：评论

学校读者我要写书评

暂无评论

Bounded-depth threshold circuits for computer-assisted CT image classification

引用

ARTIFICIAL INTELLIGENCE IN MEDICINE 2002年第2期24卷 179-192页

作者： Albrecht, A Hein, E Steinhöfel, K Taupitz, M Wong, CK CUHK Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China Humboldt Univ Fac Med Inst Radiol D-10117 Berlin Germany GMD Natl Res Ctr IT D-12489 Berlin Germany

We present a stochastic algorithm that computes threshold circuits designed to discriminate between two classes of computed tomography (CT) images. The algorithm employs a partition of training examples into several classes according to the average grey scale value of images. For each class, a sub-circuit is computed, where the first layer of the sub-circuit is calculated by a new combination of the Perceptron algorithm with a special type of simulated annealing. The algorithm is evaluated for the case of liver tissue classification. A depth-five threshold circuit (with preprocessing: depth-seven) is calculated from 400 positive (abnormal findings) and 400 negative (normal liver tissue) examples. The examples are of size n = 14,161 (119 x 119) with an 8 bit grey scale. On test sets of 100 positive and 100 negative examples (all different from the learning set) we obtain a correct classification close to 99%. The total sequential run-time to compute a depth-five circuit is about 75 h up to 230 h on a SUN Ultra 5/360 workstation, depending on the width of the threshold circuit at depth-three. In our computational experiments, the depth-five circuits were calculated from three simultaneous runs for depth-four circuits. The classification of a single image is performed within a few seconds. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： CT images perceptron algorithm simulated annealing logarithmic cooling schedule threshold functions focal liver tumour

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of the Clone Membership Problem

引用

THEORY OF COMPUTING SYSTEMS 2021年第5期65卷 839-868页

作者： Jerabek, Emil Czech Acad Sci Inst Math Zitna 25 Prague 11567 1 Czech Republic

We investigate the complexity of the Boolean clone membership problem (CMP): given a set of Boolean functions F and a Boolean function f, determine if f is in the clone generated by F, i.e., if it can be expressed by a circuit with F-gates. Here, f and elements of F are given as circuits or formulas over the usual De Morgan basis. Bohler and Schnoor (Theory Comput. Syst. 41(4):753-777, 2007) proved that for any fixed F, the problem is coNP-complete, with a few exceptions where it is in P. Vollmer (Theory Comput. Syst. 44(1): 82-90, 2009) incorrectly claimed that the full problem CMP is also coNP-complete. We prove that CMP is in fact Theta(P)(2)-complete, and we complement Bohler and Schnoor's results by showing that for fixed f, the problem is NP-complete unless f is a projection. More generally, we study the problem B-CMP where F and f are given by circuits using gates from B. For most choices of B, we classify the complexity of B-CMP as being Theta(P)(2)-complete (possibly under randomized reductions), coDP-complete, or in P.

关键词： Clone membership Boolean functions Polynomial hierarchy threshold functions

来源：评论

学校读者我要写书评

暂无评论

Inferring local transition functions of discrete dynamical systems from observations of system behavior

引用

THEORETICAL COMPUTER SCIENCE 2017年 679卷 126-144页

作者： Adiga, Abhijin Kuhlman, Chris J. Marathe, Madhav V. Ravi, S. S. Rosenkrantz, Daniel J. Stearns, Richard E. Virginia Tech Network Dynam & Simulat Sci Lab VBI Blacksburg VA USA SUNY Albany Dept Comp Sci Albany NY 12222 USA

We consider the problem of inferring the local transition functions of discrete dynamical systems from observed behavior. Our focus is on synchronous systems whose local transition functions are threshold functions. We assume that the topology of the system is known and that the goal is to infer a threshold value for each node so that the system produces the observed behavior. We show that some of these inference problems are efficiently solvable while others are NP-complete, even when the underlying graph of the dynamical system is a simple path. We identify a fixed parameter tractable problem in this context. We also consider constrained versions of threshold inference problems where the input includes a set of equality or inequality constraints (which specify pairs of nodes which must have the same threshold value or different threshold values). We present algorithmic and complexity results for several constrained threshold inference problems. (C) 2016 Elsevier B.V. All rights reserved.

关键词： threshold inference Computational complexity Synchronous dynamical systems threshold functions Phase space Trajectory Stable and unstable configurations Fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：