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.     

Linearly and Quadratically Separable Classifiers Using Adaptive Approach

This paper presents a fast adaptive iterative algorithm to solve linearly separable classification problems in R n.In each iteration,a subset of the sampling data (n-points,where n is the number of features) is adaptively chosen and a hyperplane is constructed such that it separates the chosen n-points at a margin and best classifies the remaining points.The classification problem is formulated and the details of the algorithm are presented.Further,the algorithm is extended to solving quadratically separable classification problems.The basic idea is based on mapping the physical space to another larger one where the problem becomes linearly separable.Numerical illustrations show that few iteration steps are sufficient for convergence when classes are linearly separable.For nonlinearly separable data,given a specified maximum number of iteration steps,the algorithm returns the best hyperplane that minimizes the number of misclassified points occurring through these steps.Comparisons with other machine learning algorithms on practical and benchmark datasets are also presented,showing the performance of the proposed algorithm.     

Classification of Parkinson's disease using feature weighting method on the basis of fuzzy C-means clustering

This study presents the application of fuzzy c-means (FCM) clustering-based feature weighting (FCMFW) for the detection of Parkinson's disease (PD). In the classification of PD dataset taken from University of California – Irvine machine learning database, practical values of the existing traditional and non-standard measures for distinguishing healthy people from people with PD by detecting dysphonia were applied to the input of FCMFW. The main aims of FCM clustering algorithm are both to transform from a linearly non-separable dataset to a linearly separable one and to increase the distinguishing performance between classes. The weighted PD dataset is presented to k-nearest neighbour (k-NN) classifier system. In the classification of PD, the various k-values in k-NN classifier were used and compared with each other. Also, the effects of k-values in k-NN classifier on the classification of Parkinson disease datasets have been investigated and the best k-value found. The experimental results have demonstrated that the combination of the proposed weighting method called FCMFW and k-NN classifier has obtained very promising results on the classification of PD.     

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.

     

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

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

Global convergence and limit cycle behavior of weights of perceptron.

In this paper, it is found that the weights of a perceptron are bounded for all initial weights if there exists a nonempty set of initial weights that the weights of the perceptron are bounded. Hence, the boundedness condition of the weights of the perceptron is independent of the initial weights. Also, a necessary and sufficient condition for the weights of the perceptron exhibiting a limit cycle behavior is derived. The range of the number of updates for the weights of the perceptron required to reach the limit cycle is estimated. Finally, it is suggested that the perceptron exhibiting the limit cycle behavior can be employed for solving a recognition problem when downsampled sets of bounded training feature vectors are linearly separable. Numerical computer simulation results show that the perceptron exhibiting the limit cycle behavior can achieve a better recognition performance compared to a multilayer perceptron.     

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.     

一种基于核函数的非线性感知器算法

为了提高经典Rosenblatt感知器算法的分类能力，该文提出一种基于核函数的非线性感知器算法，简称核感知器算法，其特点是用简单的迭代过程和核函数来实现非线性分类器的一种设计，核感知器算法能够处理原始属性空间中线性不可分问题和高维特征空间中线性可分问题。同时，文中详细分析了其算法与径向基函数神经网络、势函数方法和支持向量机等非线性算法的关系。人工和实际数据的计算结果表明：与线性感知器算法相比，核感知器算法可以有效地提高分类精度。     

Genetic classifiers for remotely sensed images: Comparison with standard methods

In this article the effectiveness of some recently developed genetic algorithm-based pattern classifiers was investigated in the domain of satellite imagery which usually have complex and overlapping class boundaries. Landsat data, SPOT image and IRS image are considered as input. The superiority of these classifiers over k-NN rule, Bayes' maximum likelihood classifier and multilayer perceptron (MLP) for partitioning different landcover types is established. Results based on producer's accuracy (percentage recognition score), user's accuracy and kappa values are provided. Incorporation of the concept of variable length chromosomes and chromosome discrimination led to superior performance in terms of automatic evolution of the number of hyperplanes for modelling the class boundaries, and the convergence time. This non-parametric classifier requires very little a priori information, unlike k-NN rule and MLP (where the performance depends heavily on the value of k and the architecture, respectively), and Bayes' maximum likelihood classifier (where assumptions regarding the class distribution functions need to be made).     

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

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

Large Margin Classification Using the Perceptron Algorithm

We introduce and analyze a new algorithm for linear classification which combines Rosenblatt's perceptron algorithm with Helmbold and Warmuth's leave-one-out method. Like Vapnik's maximal-margin classifier, our algorithm takes advantage of data that are linearly separable with large margins. Compared to Vapnik's algorithm, however, ours is much simpler to implement, and much more efficient in terms of computation time. We also show that our algorithm can be efficiently used in very high dimensional spaces using kernel functions. We performed some experiments using our algorithm, and some variants of it, for classifying images of handwritten digits. The performance of our algorithm is close to, but not as good as, the performance of maximal-margin classifiers on the same problem, while saving significantly on computation time and programming effort.     

A Microchoice Bound for Continuous-Space Classification Algorithms

Classifiers are often constructed iteratively by introducing changes sequentially to an initial classifier. Langford and Blum (COLT'99: Proceedings of the 12th Annual Conference on Computational Learning Theory, 1999, San Mateo, CA: Morgan Kaufmann, pp. 209–214) take advantage of this structure (the microchoice structure), to obtain bounds for the generalization ability of such algorithms. These bounds can be sharper than more general bounds. This paper extends the applicability of the microchoice approach to the more realistic case where the classifier space is continuous and the sequence of changes is not restricted to a pre-fixed finite set.Proving the microchoice bound in the continuous case relies on a conditioning technique that is often used in proving VC results. It is shown how this technique can be used to convert any learning algorithm over a continuous space into a family of algorithms over discrete spaces.The new continuous microchoice result is applied to obtain a bound for the generalization ability of the perceptron algorithm. The greedy nature of the perceptron algorithm, which generates new classifiers by introducing corrections based on misclassified points, is exploited to obtain a generalization bound that has an asymptotic form of O( ), where n is the training set size.     

Decision tree approach for classification and dimensionality reduction of electronic nose data

This paper presents a decision tree approach using two different tree models, C4.5 and CART, for use in the classification and dimensionality reduction of electronic nose (EN) data. The decision tree is a tree structure consisting of internal and terminal nodes which process the data to ultimately yield a classification. The decision tree is proficient at both maintaining the role of dimensionality reduction and at organizing optimally sized classification trees, and therefore it could be a promising approach to analyze EN data. In the experiments conducted, six sensor response parameters were extracted from the dynamic sensor responses of each of the four metal oxide gas sensors. The six parameters observed were the rising time (T_r), falling time (T_f), total response time (T_t), normalized peak voltage change (y_p,n), normalized curve integral (C_I), and triangle area (T_A). One sensor parameter from each metal oxide sensor was used for the classification trees, and the best classification accuracy of 97.78% was achieved by CART using the C_I parameter. However, the accuracy of CART was improved using all of the sensor parameters as inputs to the classification tree. The improved results of CART, having an accuracy of 98.89%, was comparable to that of two popular classifiers, the multilayer perceptron (MLP) neural network and the fuzzy ARTMAP network (accuracy of 98.89%, and 100%, respectively). Furthermore, as a dimensionality reduction method the decision tree has shown a better discrimination accuracy of 100% for the MLP classifier and 98.89% for the fuzzy ARTMAP classifier as compared to those achieved with principle component analysis (PCA) giving 81.11% and 97.78%, and a variable selection method giving 92.22% and 93.33% (for the same MLP and fuzzy ARTMAP classifiers). Therefore, a decision tree could be a promising technique for a pattern recognition system for EN data in terms of two functions; as classifier which is an optimally organized classification tree, and as dimensionality reduction method for other pattern recognition techniques.     

Adaptive Ho-Kashyap rules for perceptron training

Three adaptive versions of the Ho-Kashyap perceptron training algorithm are derived based on gradient descent strategies. These adaptive Ho-Kashyap (AHK) training rules are comparable in their complexity to the LMS and perceptron training rules and are capable of adaptively forming linear discriminant surfaces that guarantee linear separability and of positioning such surfaces for maximal classification robustness. In particular, a derived version called AHK II is capable of adaptively identifying critical input vectors lying close to class boundaries in linearly separable problems. The authors extend this algorithm as AHK III, which adds the capability of fast convergence to linear discriminant surfaces which are good approximations for nonlinearly separable problems. This is achieved by a simple built-in unsupervised strategy which allows for the adaptive grading and discarding of input vectors causing nonseparability. Performance comparisons with LMS and perceptron training are presented.     

Neural and Wavelet Network Models for Financial Distress Classification

This work analyzes the use of linear discriminant models, multi-layer perceptron neural networks and wavelet networks for corporate financial distress prediction. Although simple and easy to interpret, linear models require statistical assumptions that may be unrealistic. Neural networks are able to discriminate patterns that are not linearly separable, but the large number of parameters involved in a neural model often causes generalization problems. Wavelet networks are classification models that implement nonlinear discriminant surfaces as the superposition of dilated and translated versions of a single “mother wavelet” function. In this paper, an algorithm is proposed to select dilation and translation parameters that yield a wavelet network classifier with good parsimony characteristics. The models are compared in a case study involving failed and continuing British firms in the period 1997–2000. Problems associated with over-parameterized neural networks are illustrated and the Optimal Brain Damage pruning technique is employed to obtain a parsimonious neural model. The results, supported by a re-sampling study, show that both neural and wavelet networks may be a valid alternative to classical linear discriminant models.     

Recursive Partitioning Technique for Combining Multiple Classifiers

Various methods of reducing correlation between classifiers in a multiple classifier framework have been attempted. Here we propose a recursive partitioning technique for analysing feature space of multiple classifier decisions. Spectral summation of individual pattern components in intermediate feature space enables each training pattern to be rated according to its contribution to separability, measured as k-monotonic constraints. A constructive algorithm sequentially extracts maximally separable subsets of patterns, from which is derived an inconsistently classified set (ICS). Leaving out random subsets of ICS patterns from individual (base) classifier training sets is shown to improve performance of the combined classifiers. For experiments reported here on artificial and real data, the constituent classifiers are identical single hidden layer MLPs with fixed parameters.     

Constrained classifier: a novel approach to nonlinear classification

Simple classifiers have the advantage of more generalization capability with the side effect of less power. It would be a good idea if we could build a classifier which is as simple as possible while giving it the ability of classifying complex patterns. In this paper, a hybrid classifier called “constrained classifier” is presented that classifies most of the input patterns using a simple, for example, a linear classifier. It performs the classification in four steps. In the “Dividing” step, the input patterns are divided into linearly separable and nonlinearly separable groups. The patterns belonging to the first group are classified using a simple classifier while the second group patterns (named “constraints”) are modeled in the “Modeling” step. The results of previous steps are merged together in the “Combining” step. The “Evaluation” step tests and fine tunes the membership of patterns into two groups. The experimental results of comparison of the new classifier with famous classifiers such as “support vector machine”, k-NN, and “Classification and Regression Trees” are very encouraging.     

Relation Between Permutation-Test P Values and Classifier Error Estimates

Gene-expression-based classifiers suffer from the small number of microarrays usually available for classifier design. Hence, one is confronted with the dual problem of designing a classifier and estimating its error with only a small sample. Permutation testing has been recommended to assess the dependency of a designed classifier on the specific data set. This involves randomly permuting the labels of the data points, estimating the error of the designed classifiers for each permutation, and then finding the p value of the error for the actual labeling relative to the population of errors for the random labelings. This paper addresses the issue of whether or not this p value is informative. It provides both analytic and simulation results to show that the permutation p value is, up to very small deviation, a function of the error estimate. Moreover, even though the p value is a monotonically increasing function of the error estimate, in the range of the error where the majority of the p values lie, the function is very slowly increasing, so that inversion is problematic. Hence, the conclusion is that the p value is less informative than the error estimate. This result demonstrates that random labeling does not provide any further insight into the accuracy of the classifier or the precision of the error estimate. We have no knowledge beyond the error estimate itself and the various distribution-free, classifier-specific bounds developed for this estimate.     

Image Compression and Reconstruction Using pi<Subscript><Emphasis Type="Italic">t</Emphasis></Subscript>-Sigma Neural Networks

A high-order feedforward neural architecture, called pi _t -sigma (π _t σ) neural network, is proposed for lossy digital image compression and reconstruction problems. The π _t σ network architecture is composed of an input layer, a single hidden layer, and an output layer. The hidden layer is composed of classical additive neurons, whereas the output layer is composed of translated multiplicative neurons (π _t -neurons). A two-stage learning algorithm is proposed to adjust the parameters of the π _t σ network: first, a genetic algorithm (GA) is used to avoid premature convergence to poor local minima; in the second stage, a conjugate gradient method is used to fine-tune the solution found by GA. Experiments using the Standard Image Database and infrared satellite images show that the proposed π _t σ network performs better than classical multilayer perceptron, improving the reconstruction precision (measured by the mean squared error) in about 56%, on average.