Test and realization of linearly separable switching functions†

A switching function is said to be linearly separable if the weighted sum of the input variables of the logical element realizing the function equals or exceeds a threshold. The weights and threshold are all real numbers. All switching functions are not linearly separable. A test and realization procedure for linearly separable switching functions using the decimal number representation of the input variable combinations only is presented here. The test process uses the 2-asummability property of linearly separable switching functions and is usable for switching functions of eight or lesser number of variables. A slide-rule device is described where the test can be mechanically done promptly. The realization technique is iterative and gives integral solutions directly. The method is straightforward and is very useful, particularly for a small number of variables.     

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

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

A constructive design method for two-layer perceptrons and its applicatio to the design of modular neural networks

Abstract: A multilayer perceptron is known to be capable of approximating any smooth function to any desired accuracy if it has a sufficient number of hidden neurons. But its training, based on the gradient method, is usually a time consuming procedure that may converge toward a local minimum, and furthermore its performance is greatly influenced by the number of hidden neurons and their initial weights. Usually these crucial parameters are determined based on the trial and error procedure, requiring much experience on the designer's part.
In this paper, a constructive design method (CDM) has been proposed for a two-layer perceptron that can approximate a class of smooth functions whose feature vector classes are linearly separable. Based on the analysis of a given data set sampled from the target function, feature vectors that can characterize the function'well'are extracted and used to determine the number of hidden neurons and the initial weights of the network. But when the classes of the feature vectors are not linearly separable, the network may not be trained easily, mainly due to the interference among the hyperplanes generated by hidden neurons. Next, to compensate for this interference, a refined version of the modular neural network (MNN) has been proposed where each network module is created by CDM. After the input space has been partitioned into many local regions, a two-layer perceptron constructed by CDM is assigned to each local region. By doing this, the feature vector classes are more likely to become linearly separable in each local region and as a result, the function may be approximated with greatly improved accuracy by MNN. An example simulation illustrates the improvements in learning speed using a smaller number of neurons.     

NXOR- or XOR-based robust template decomposition for cellular neural networks implementing an arbitrary Boolean function via support vector classifiers

Robust template design for cellular neural networks (CNNs) implementing an arbitrary Boolean function is currently an active research area. If the given Boolean function is linearly separable, a single robust uncoupled CNN can be designed preferably as a maximal margin classifier to implement the Boolean function. On the other hand, if the linearly separable Boolean function has a small geometric margin or the Boolean function is not linearly separable, a popular approach is to find a sequence of robust uncoupled CNNs implementing the given Boolean function. In the past research works using this approach, the control template parameters and thresholds are usually restricted to assume only a given finite set of integers. In this study, we try to remove this unnecessary restriction. NXOR- or XOR-based decomposition algorithm utilizing the soft margin and maximal margin support vector classifiers is proposed to design a sequence of robust templates implementing an arbitrary Boolean function. Several illustrative examples are simulated to demonstrate the efficiency of the proposed method by comparing our results with those produced by other decomposition methods with restricted weights.

     

Solving the XOR and parity <Emphasis Type="Italic">N</Emphasis> problems using a single universal binary neuron

A universal binary neuron (UBN) operates with complex-valued weights and a complex-valued activation function, which is the function of the argument of the weighted sum. The activation function of the UBN separates a whole complex plane onto equal sectors, where the activation function is equal to either 1 or −1 depending on the sector parity (even or odd, respectively). Thus, the UBN output is determined by the argument of the weighted sum. This makes it possible the implementation of the nonlinearly separable (non-threshold) Boolean functions on a single neuron. Hence, the functionality of UBN is incompatibly higher than the functionality of the traditional perceptron. In this paper, we will consider a new modified learning algorithm for the UBN. We will show that classical nonlinearly separable problems XOR and Parity n can be easily solved using a single UBN, without any network. Finally, it will be considered how some other important nonlinearly separable problems may be solved using a single UBN.     

Incorporating fuzzy membership functions into the perceptron algorithm

The perceptron algorithm, one of the class of gradient descent techniques, has been widely used in pattern recognition to determine linear decision boundaries. While this algorithm is guaranteed to converge to a separating hyperplane if the data are linearly separable, it exhibits erratic behavior if the data are not linearly separable. Fuzzy set theory is introduced into the perceptron algorithm to produce a ``fuzzy algorithm' which ameliorates the convergence problem in the nonseparable case. It is shown that the fuzzy perceptron, like its crisp counterpart, converges in the separable case. A method of generating membership functions is developed, and experimental results comparing the crisp to the fuzzy perceptron are presented.     

On System Functions with the Property of Separability†

This paper considers linear differential (time-varying) systems which may be described by either of two system functions based on a specified integral transform. In particular, those systems are discussed for which at least one of the aforementioned system functions is separable in its two arguments. Physical interpretations of separable system functions are given and two theorems are proved which yield sufficient conditions for the presence of this property. It is also proved that the so-called ‘bi-frequency’ function of Zadeh must be Separable for linear differential systems. Finally, the problem of approximately representing a given system by a separable system function based on the Laplace transform is discussed.     

Neural classifiers using one-time updating

The linear threshold element, or perceptron, is a linear classifier with limited capabilities due to the problems arising when the input pattern set is linearly nonseparable. Assuming that the patterns are presented in a sequential fashion, we derive a theory for the detection of linear nonseparability as soon as it appears in the pattern set. This theory is based on the precise determination of the solution region in the weight spare with the help of a special set of vectors. For this region, called the solution cone, we present a recursive computation procedure which allows immediate detection of nonseparability. The algorithm can be directly cast into a simple neural-network implementation. In this model the synaptic weights are committed. Finally, by combining many such neural models we develop a learning procedure capable of separating convex classes.     

二进神经网络中汉明球突的判定及其逻辑意义

在布尔空间中,汉明球突表达了一类结构清晰的布尔函数, 由于其特殊的几何特性,存在线性可分与线性不可分两种空间结构. 剖析汉明球突的逻辑意义对二进神经网络的规则提取十分重要, 然而,从线性可分的汉明球突中提取具有清晰逻辑意义的规则, 以及如何判定非线性可分的汉明球突,并得到其逻辑意义,仍然是二进神经网络研究中尚未很好解决的问题. 为此,本文首先根据汉明球突在汉明图上的几何特性, 采用真节点加权高度排序的方法, 提出对于任意布尔函数是否为汉明球突的判定算法;然后, 在此基础上利用已知结构的逻辑意义, 将汉明球突分解为若干个已知结构的并集,从而得到汉明球突的逻辑意义; 最后,通过实例说明判定任意布尔函数是否为汉明球突的过程, 并相应得到汉明球突的逻辑表达.     

Classification of linearly nonseparable patterns by linearthreshold elements

Learning and convergence properties of linear threshold elements or perceptrons are well understood for the case where the input vectors (or the training sets) to the perceptron are linearly separable. Little is known, however, about the behavior of the perceptron learning algorithm when the training sets are linearly nonseparable. We present the first known results on the structure of linearly nonseparable training sets and on the behavior of perceptrons when the set of input vectors is linearly nonseparable. More precisely, we show that using the well known perceptron learning algorithm, a linear threshold element can learn the input vectors that are provably learnable, and identify those vectors that cannot be learned without committing errors. We also show how a linear threshold element can be used to learn large linearly separable subsets of any given nonseparable training set. In order to develop our results, we first establish formal characterizations of linearly nonseparable training sets and define learnable structures for such patterns. We also prove computational complexity results for the related learning problems. Next, based on such characterizations, we show that a perceptron does the best one can expect for linearly nonseparable sets of input vectors and learns as much as is theoretically possible.     

Evolutionary training of hardware realizable multilayer perceptrons

The use of multilayer perceptrons (MLP) with threshold functions (binary step function activations) greatly reduces the complexity of the hardware implementation of neural networks, provides tolerance to noise and improves the interpretation of the internal representations. In certain case, such as in learning stationary tasks, it may be sufficient to find appropriate weights for an MLP with threshold activation functions by software simulation and, then, transfer the weight values to the hardware implementation. Efficient training of these networks is a subject of considerable ongoing research. Methods available in the literature mainly focus on two-state (threshold) nodes and try to train the networks by approximating the gradient of the error function and modifying appropriately the gradient descent, or by progressively altering the shape of the activation functions. In this paper, we propose an evolution-motivated approach, which is eminently suitable for networks with threshold functions and compare its performance with four other methods. The proposed evolutionary strategy does not need gradient related information, it is applicable to a situation where threshold activations are used from the beginning of the training, as in “on-chip” training, and is able to train networks with integer weights.     

Optimization of the correct operation probability of ann-input threshold element in presence of noise

This work deals with a method of determining the acceptable ranges of the weights in a threshold element, and evaluating the optimum set of a class of symmetric linearly separable functions. This set maximizes the correct operation probability of ann-input threshold element in presence of noise. Lavoro sviluppato presso il Laboratorio di Elettronica del CSN della Casaccia.     

The separating capacity of a multithreshold threshold element

In answer to what represents the intrinsic information-processing capability of the pattern classification system, Cover [1] has defined the separating capacity, and has derived it for the linear machine and the so-called ? machine. In this paper, the separating capacity of a multithreshold classification element is obtained. It is shown that the capacity of a multithreshold threshold element with k thresholds-k-threshold element-in n-dimensional space is 2(n + k). A linear machine is a special case in the k-threshold element with k = 1; therefore, its capacity becomes 2(n + 1) from the above result. Further, although it is intuitively apparent that the larger the number of thresholds, the more powerful the information-processing capability of the k-threshold element, using the capacity as a measure of this capability, we may now state that the separating power of the k-threshold element increases linearly with respect to k.     

A kernel optimization method based on the localized kernel Fisher criterion

It is widely recognized that whether the selected kernel matches the data determines the performance of kernel-based methods. Ideally it is expected that the data is linearly separable in the kernel induced feature space, therefore, Fisher linear discriminant criterion can be used as a cost function to optimize the kernel function. However, the data may not be linearly separable even after kernel transformation in many applications, e.g., the data may exist as multimodally distributed structure, in this case, a nonlinear classifier is preferred, and obviously Fisher criterion is not a suitable choice as kernel optimization rule. Motivated by this issue, we propose a localized kernel Fisher criterion, instead of traditional Fisher criterion, as the kernel optimization rule to increase the local margins between embedded classes in kernel induced feature space. Experimental results based on some benchmark data and measured radar high-resolution range profile (HRRP) data show that the classification performance can be improved by using the proposed method.     

一种新的阈函数的分析框架及有关结论

引入加权Ｈａｍｍｉｎｇ距离球（ＷＨＤＳ）分析阈函数。首先提出并证明加权Ｈａｍｍｉｎｇ球与阈函数完全等价,然后以有向图的形式表示加权Ｈａｍｍｉｎｇ距离球并给出几个重要性质。最后由加权Ｈａｍｍｉｎｇ距离球的分析得到几个阈函数判别及构造的几个结构。     

An iterative method for training multilayer networks with thresholdfunctions

Concerns the problem of finding weights for feed-forward networks in which threshold functions replace the more common logistic node output function. The advantage of such weights is that the complexity of the hardware implementation of such networks is greatly reduced. If the task to be learned does not change over time, it may be sufficient to find the correct weights for a threshold function network off-line and to transfer these weights to the hardware implementation. This paper provides a mathematical foundation for training a network with standard logistic function nodes and gradually altering the function to allow a mapping to a threshold unit network. The procedure is analogous to taking the limit of the logistic function as the gain parameter goes to infinity. It is demonstrated that, if the error in a trained network is small, a small change in the gain parameter will cause a small change in the network error. The result is that a network that must be implemented with threshold functions can first be trained using a traditional back propagation network using gradient descent, and further trained with progressively steeper logistic functions. In theory, this process could require many repetitions. In simulations, however, the weights have be successfully mapped to a true threshold network after a modest number of slope changes. It is important to emphasize that this method is only applicable to situations for which off-line learning is appropriate.     

二进神经网络中SP函数的一般判别和构造方法

SP函数是一类具有明确逻辑意义的线性可分结构系,PSP函数是SP函数的特殊子集. 文中讨论了二进神经元对SP函数和PSP函数的表达问题,通过研究PSP函数分类超平面的某 些性质,建立了SP函数和PSP函数的一般判别和构造方法.     

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

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

Threshold behaviour of the maximum likelihood method in population decoding

We study the performance of the maximum likelihood (ML) method in population decoding as a function of the population size. Assuming uncorrelated noise in neural responses, the ML performance, quantified by the expected square difference between the estimated and the actual quantity, follows closely the optimal Cramer-Rao bound, provided that the population size is sufficiently large. However, when the population size decreases below a certain threshold, the performance of the ML method undergoes a rapid deterioration, experiencing a large deviation from the optimal bound. We explain the cause of such threshold behaviour, and present a phenomenological approach for estimating the threshold population size, which is found to be linearly proportional to the inverse of the square of the system's signal-to-noise ratio. If the ML method is used by neural systems, we expect the number of neurons involved in population coding to be above this threshold.     

Characterization of the Sonar Signals Benchmark

We study the classification of sonar targets first introduced by Gorman & Sejnowski (1988). We discovered that not only the training set and the test set of this benchmark are both linearly separable, although by different hyperplanes, but that the complete set of patterns, training and test patterns together, is also linearly separable. The distances of the patterns to the separating hyperplane determined by learning with the training set alone, and to the one determined by learning the complete data set, are presented.