Universal Perceptron and DNA-Like Learning Algorithm for Binary Neural Networks: LSBF and PBF Implementations

Universal perceptron (UP), a generalization of Rosenblatt's perceptron, is considered in this paper, which is capable of implementing all Boolean functions (BFs). In the classification of BFs, there are: 1) linearly separable Boolean function (LSBF) class, 2) parity Boolean function (PBF) class, and 3) non-LSBF and non-PBF class. To implement these functions, UP takes different kinds of simple topological structures in which each contains at most one hidden layer along with the smallest possible number of hidden neurons. Inspired by the concept of DNA sequences in biological systems, a novel learning algorithm named DNA-like learning is developed, which is able to quickly train a network with any prescribed BF. The focus is on performing LSBF and PBF by a single-layer perceptron (SLP) with the new algorithm. Two criteria for LSBF and PBF are proposed, respectively, and a new measure for a BF, named nonlinearly separable degree (NLSD), is introduced. In the sense of this measure, the PBF is the most complex one. The new algorithm has many advantages including, in particular, fast running speed, good robustness, and no need of considering the convergence property. For example, the number of iterations and computations in implementing the basic 2-bit logic operations such as and, or, and xor by using the new algorithm is far smaller than the ones needed by using other existing algorithms such as error-correction (EC) and backpropagation (BP) algorithms. Moreover, the synaptic weights and threshold values derived from UP can be directly used in designing of the template of cellular neural networks (CNNs), which has been considered as a new spatial-temporal sensory computing paradigm.     

基于闭凸包收缩的最大边缘线性分类器

SVM(support vector machines)是一种基于结构风险最小化原理的分类技术.给出实现结构风险最小化原理(最大边缘)的另一种方法.对线性可分情形,提出一种精确意义下的最大边缘算法,并通过闭凸包收缩的概念,将线性不可分的情形转化为线性可分情形.该算法与SVM算法及其Cortes软边缘算法异曲同工,但理论体系简单、严谨,其中的优化问题几何意义清楚、明确.     

Multi-objective optimization of QCA circuits with multiple outputs using genetic programming

Quantum-Dot Cellular Automata (QCA) is a promising nanotechnology that has been recognized as one of the top emerging technologies in future computers. Size density of several orders of magnitude smaller than Complementary Metal-Oxide Semiconductor, fast switching time and extremely low power, has caused QCA to become a topic of intense research. The majority gate and the inverter gate together make a universal set of Boolean primitives in QCA technology. Reducing the number of required primitives to implement a given Boolean function is an important step in designing QCA logic circuits. Previous research has shown how to use genetic programming to minimize the number of gates implementing a given Boolean function with one output. In this paper, we first show how to minimize the gates for the given Boolean truth tables with an arbitrary number of outputs using genetic programming. Then, another criterion, reduction of the delay of the implementing circuit is considered. Multi-objective genetic programming is applied to simultaneously optimize both objectives. The results demonstrate the proposed approach is promising and worthy of further research.     

基于相似压缩的近似线性SVM

为了解决模式识别中的近似线性可分问题,提出了一种新的近似线性支持向量机(SVM).首先对近似线性分类中的训练集所形成的两类凸壳进行了相似压缩,使压缩后的凸壳线性可分;基于压缩后线性可分的凸壳,再用平分最近点和最大间隔法求出最优的分划超平面.然后再通过求解最大间隔法的对偶问题,得到基于相似压缩的近似线性SVM.最后,从理论和实证分析两个方面,将该方法与线性可分SVM及推广的平分最近点法进行了对比分析,说明了该方法的优越性与合理性.     

Analysis of associative memories based on cellular neural networks with value-varying templates

ABSTRACT

In many research literatures, the dynamical behaviour of cellular neural networks (CNNs) is simplified by using cloning template. However, the flaws of cloning template are obvious, because the correlation between weights of cells in CNNs is enhanced. In order to overcome the shortcomings of cloning template, value-varying templates can be used in CNNs. In this paper, associative memories based on CNNs with value-varying templates are investigated. A criterion about stability of CNNs is presented. Then, the problem about obtaining parameters of CNNs can be translated into a problem of solving linear equations for each cell. A design procedure of associative memories is given by our theories and methods. From the procedure, the parameters of CNNs can be obtained. Finally, three examples are used to demonstrate the effectiveness of our theories and methods. And the results show that success rate of associative memories is higher than previous methods.     

带不确定协方差线性相关白噪声系统改进的鲁棒协方差交叉融合稳态Kalman 估值器

对于带有不确定协方差线性相关白噪声的多传感器系统, 利用Lyapunov 方程提出设计协方差交叉(CI) 融合极大极小鲁棒Kalman 估值器(预报器、滤波器、平滑器) 的一种统一方法. 利用保守的局部估值误差互协方差, 提出改进的CI 融合鲁棒稳态Kalman 估值器及其实际估值误差方差最小上界, 克服了用原始CI 融合方法给出的上界具有较大保守性的缺点, 改善了原始CI 融合器鲁棒精度. 跟踪系统的仿真例子验证了所提出方法的正确性和有效性.

     

多分类问题的凸包收缩方法

在最大边缘线性分类器和闭凸包收缩思想的基础上,针对二分类问题,通过闭凸包收缩技术,将线性不可分问题转化为线性可分问题。将上述思想推广到解决多分类问题中,提出了一类基于闭凸包收缩的多分类算法。该方法几何意义明确,在一定程度上克服了以往多分类方法目标函数过于复杂的缺点,并利用核思想将其推广到非线性分类问题上。     

An iterative structure for synthesizing symmetric functions using quantum-dot cellular automata

In recent years, majority-logic received significant attention as a synthesis approach for large Boolean functions. This logic is easily implemented in Quantum-dot cellular automata (QCA) technology which is emerging as an alternative to CMOS technology. In fact, majority logic gate serves as the basic logic unit in the digital design of QCA circuits. This paper introduces a synthesis technique for implementing totally symmetric Boolean functions using majority logic. First, a simple regular module is designed to synthesize unate symmetric functions. The structure uses 3-input majority gates. General symmetric Boolean functions are then realized following a unate decomposition method. We study the synthesis of some well known benchmark symmetric functions using the proposed method. Comparison with existing synthesis approaches confirms the efficacy of our method.     

Universal Perceptron and DNA-Like Learning Algorithm for Binary Neural Networks: Non-LSBF Implementation

Implementing linearly nonseparable Boolean functions (non-LSBF) has been an important and yet challenging task due to the extremely high complexity of this kind of functions and the exponentially increasing percentage of the number of non-LSBF in the entire set of Boolean functions as the number of input variables increases. In this paper, an algorithm named DNA-like learning and decomposing algorithm (DNA-like LDA) is proposed, which is capable of effectively implementing non-LSBF. The novel algorithm first trains the DNA-like offset sequence and decomposes non-LSBF into logic xor operations of a sequence of LSBF, and then determines the weight-threshold values of the multilayer perceptron (MLP) that perform both the decompositions of LSBF and the function mapping the hidden neurons to the output neuron. The algorithm is validated by two typical examples about the problem of approximating the circular region and the well-known $n$ -bit parity Boolean function (PBF).      

The greatest allowed relative error in weights and threshold of strict separating systems.

An important consideration when applying neural networks is the sensitivity to weights and threshold in strict separating systems representing a linearly separable function. Perturbations may affect weights and threshold so that it is important to estimate the maximal percentage error in weights and threshold, which may be allowed without altering the linearly separable function. In this paper, we provide the greatest allowed bound which can be associated to every strict separating system representing a linearly separable function. The proposed bound improves the tolerance that Hu obtained. Furthermore, it is the greatest bound for any strict separating system. This is the reason why we call it the greatest tolerance.     

An iterative algorithm learning the maximal margin classifier

A simple learning algorithm for maximal margin classifiers (also support vector machines with quadratic cost function) is proposed. We build our iterative algorithm on top of the Schlesinger-Kozinec algorithm (S-K-algorithm) from 1981 which finds a maximal margin hyperplane with a given precision for separable data. We suggest a generalization of the S-K-algorithm (i) to the non-linear case using kernel functions and (ii) for non-separable data. The requirement in memory storage is linear to the data. This property allows the proposed algorithm to be used for large training problems.The resulting algorithm is simple to implement and as the experiments showed competitive to the state-of-the-art algorithms. The implementation of the algorithm in Matlab is available. We tested the algorithm on the problem aiming at recognition poor quality numerals.     

Exploiting Functional Properties of Boolean Functions for Optimal Multi-Level Design by Bi-Decomposition

This paper introduces the theory of bi-decomposition of Boolean functions. This approach optimally exploits functional properties of a Boolean function in order to find an associated multilevel circuit representation having a very short delay by using simple two input gates. The machine learning process is based on the Boolean Differential Calculus and is focused on the aim of detecting the profitable functional properties availablefor the Boolean function. For clear understanding the bi-decomposition of completely specifiedBoolean functions is introduced first. Significantly better chance of successare given for bi-decomposition of incompletely specifiedBoolean functions, discussed secondly. The inclusion of the weak bi-decomposition allows to prove the the completeness of the suggested decomposition method. The basic task for machine learning consists of determining the decomposition type and dedicated sets of variables. Lean on this knowledge a complete recursive design algorithm is suggested. Experimental results over MCNC benchmarks show that the bi-decomposition outperforms SIS and other BDD-based decomposition methods interms of area and delay of the resulting circuits with comparableCPU time. By switching from the ON-set/OFF-set model of Boolean function lattices to their upper- and lower-bound model a new view to the bi-decomposition arises. This new form of the bi-decomposition theorymakes a comprehensible generalization of the bi-decomposition to multivalued function possible.     

一种基于L2范数的软核感知机

感知机只能解决线性可分问题。支持向量机中的L2范数软边缘算法可以将线性不可分问题转化为线性可分问题。基于这一事实,提出一种基于L2范数的软核感知机(SoftKernelPerceptron,SKP),将感知机算法直接用于求解L2范数软边缘算法决定的线性可分问题。通过使用核技巧,得到一种普适的非线性分类方法。实际数据库的测试结果表明,SKP算法能够有效地解决非线性问题,并且继承了感知机运算简单速度快的优点。     

Support Vector的几何解释及其在联想记忆中的应用

利用闭凸集上的投影解释support vector的几何意义，利用支持超平面讨论线性分类器的设计问题，对线性可分情形，Support vector由一类数据集合闭凸包在另一类数据集合闭凸包上投影的非零系数向量组成，SVM所决定的超平面位于两投影点关于各自数据集合支持超平面的中间，作为应用，文中给出一种设计理想联想记忆前馈神经网络的方法，它是FP算法的一般化。     

Saturated Perceptrons for Maximum Margin and Minimum Misclassification Error

This Letter discusses the application of gradient-based methods to train a single layer perceptron subject to the constraint that the saturation degree of the sigmoid activation function (measured as its maximum slope in the sample space) is fixed to a given value. From a theoretical standpoint, we show that, if the training set is not linearly separable, the minimization of an L _p error norm provides an approximation to the minimum error classifier, provided that the perceptron is highly saturated. Moreover, if data are linearly separable, the perceptron approximates the maximum margin classifier     

Maiorana-McFarland’s Bent函数零化子空间维数

在流密码和分组密码的设计中,所用布尔函数应该具有好的密码学性质来抵抗已知的各种有效攻击.布尔函数的低次零化子空间维数与其补函数低次零化子空间维数之和是评价该函数抵抗代数攻击能力的一个重要参数.根据Maiorana-McFarlands(M-M)Bent函数和布尔置换之间的一一对应关系,给出了一组布尔函数组并证明了它们是线性无关的.借助所给的线性无关布尔函数组和布尔置换中向量函数非零线性组合均是平衡函数的特性,给出了一类特殊M-M Bent函数低次零化子空间的维数与其补函数低次零化子空间的维数之和的一个上限.就这类特殊M-M Bent函数而言,该上限低于已知的限.进一步给出了适合所有M-M Bent函数的新上限.     

不确定系统鲁棒LQ设计的稳定裕度分析和工程应用研究

针对不确定线性系统, 研究鲁棒LQ设计的稳定裕度分析问题. 首先提出不确定系统α_0裕度稳定鲁棒界, 针对结构和非结构不确定系统, 分别给出了鲁棒LQ控制系统的鲁棒稳定裕度性分析方法, 进一步给出对结构不确定系统优化鲁棒界的算法. 最后是造纸打浆过程实例的鲁棒稳定裕度性分析以及相应仿真结果.     

复合4邻域圈提取CNN的鲁棒性设计

细胞神经网络（Cellular Neural Network,CNN）于1988年由L.O.Chua 等人提出,已经成为一种处理图像和视频信号、机器人技术、生物视觉、高级大脑功能的新工具。细胞神经网络模板的鲁棒性设计是CNN在实际应用中碰到的重要课题之一。目的是设计一种能够提取复合4邻域圈的CNN,并对其模板进行鲁棒性设计,给出满足相应功能CNN的鲁棒性定理。该定理提供了能达到预先指定的图像处理功能的CNN模板参数不等式。数值模拟例子说明了理论证明的有效性。     

Sufficient and necessary conditions for Boolean fuzzy systems as universal approximators

A formula is first presented to compute the lower upper bounds on the number of fuzzy sets to achieve pre-specified approximation accuracy for an arbitrary multivariate continuous function. The necessary condition for Boolean fuzzy systems as universal approximators with minimal system configurations is then discussed. Two examples are provided to demonstrate how to design a Boolean fuzzy system in order to approximate a given continuous function with a required approximation accuracy.     

一类严反馈非线性系统的神经网络控制

研究一类不确定严反馈非线性系统的跟踪控制问题.通过采用单一神经网络逼近系统的所有未知部分,提出一种新的鲁棒自适应控制设计方法.该方法能直接给出实际控制律和自适应律,有效地解决现有方法中存在的控制设计复杂和计算负担重等问题.稳定性分析表明,闭环系统所有信号是半全局一致最终有界的,并且通过调整控制参数可使跟踪误差任意小.仿真结果验证了所提出方法的有效性.