Asymptotic speed-ups in constructive solid geometry

We convert constructive solid geometry input to explicit representations of polygons, polyhedra, or more generallyd-dimensional polyhedra, in time and space 0(n^d), improving a previous0(n^d logn) time bound. We then show that any Boolean formula can be preprocessed in time0(n log n/log logn) and linear space so that the value of the formula can be maintained, as variables are changed one by one, in time O(log n/log logn) per change; this speeds up certain output-sensitive algorithms for constructive solid geometry.     

构造性覆盖下不完整数据修正填充方法

不完整数据处理是数据挖掘、机器学习等领域中的重要问题,缺失值填充是处理不完整数据的主流方法。当前已有的缺失值填充方法大多运用统计学和机器学习领域的相关技术来分析原始数据中的剩余信息,从而得到较为合理的值来替代缺失部分。缺失值填充大致可以分为单一填充和多重填充,这些填充方法在不同的场景下有着各自的优势。但是,很少有方法能进一步考虑样本空间分布中的邻域信息,并以此对缺失值的填充结果进行修正。鉴于此,本文提出了一种可广泛应用于诸多现有填充方法的框架用以提升现有方法的填充效果,该框架由预填充、空间邻域信息挖掘和修正填充三部分构成。本文对7种填充方法在8个UCI数据集上进行了实验,实验结果验证了本文所提框架的有效性和鲁棒性。     

CARVE-a constructive algorithm for real-valued examples

A constructive neural-network algorithm is presented. For any consistent classification task on real-valued training vectors, the algorithm constructs a feedforward network with a single hidden layer of threshold units which implements the task. The algorithm, which we call CARVE, extends the "sequential learning" algorithm of Marchand et al. (1990) from Boolean inputs to the real-valued input case, and uses convex hull methods for the determination of the network weights. The algorithm is an efficient training scheme for producing near-minimal network solutions for arbitrary classification tasks. The algorithm is applied to a number of benchmark problems including German and Sejnowski's sonar data, the Monks problems and Fisher's iris data. A significant application of the constructive algorithm is in providing an initial network topology and initial weights for other neural-network training schemes, and this is demonstrated by application to backpropagation.     

A PDP constructive algorithm for system modelling

A new constructive algorithm is presented for building neural networks that learn to reproduce output temporal sequences based on one or several input sequences. This algorithm builds a network for the task of system modelling, dealing with continuous variables in the discrete time domain. The constructive scheme makes it user independent. The network's structure consists of an ordinary set and a classification set, so it is a hybrid network like that of Stokbro et al. [6], but with a binary classification. The networks can easily be interpreted, so the learned representation can be transferred to a human engineer, unlike many other network models. This allows for a better understanding of the system structure than just its simulation. This constructive algorithm limits the network complexity automatically, hence preserving extrapolation capabilities. Examples with real data from three totally different sources show good performance and allow for a promising line of research.     

A generalized constructive algorithm using insertion-based heuristics

In this paper, a generalized constructive algorithm referred to as GCA is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework, referred to as PERMGEN, forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of GCA are identified. Features and benefits of the generalized algorithm are presented through the extension of the NEH heuristic, a successful heuristic solution approach of Nawaz, Enscore, and Ham for the permutation flowshop problem (PFSP). The goal of the experimental study is to improve the performance of the NEH heuristic on the PFSP. To achieve this goal, the space of algorithmic control arguments is searched for a combination of values that define an algorithm providing lower makespan solutions than NEH, in a linear increase of CPU time. Computational experiments on a set of 120 benchmark problem instances, originally proposed by Taillard, are performed to establish a more robust version of the original NEH constructive heuristic. The proposed procedures outperform NEH, preserving its efficiency and simplicity.     

DistAl: An inter-pattern distance-based constructive learning algorithm

Multi-layer networks of threshold logic units (TLU) offer an attractive framework for the design of pattern classification systems. A new constructive neural network learning algorithm (DistAl) based on inter-pattern distance is introduced. DistAl constructs a single hidden layer of hyperspherical threshold neurons. Each neuron is designed to determine a cluster of training patterns belonging to the same class. The weights and thresholds of the hidden neurons are determined directly by comparing the inter-pattern distances of the training patterns. This offers a significant advantage over other constructive learning algorithms that use an iterative (and often time consuming) weight modification strategy to train individual neurons. The individual clusters (represented by the hidden neurons) are combined by a single output layer of threshold neurons. The speed of DistAl makes it a good candidate for datamining and knowledge acquisition from large datasets. The paper presents results of experiments using several artificial and real-world datasets. The results demonstrate that DistAl compares favorably with other learning algorithms for pattern classification.     

A constructive algorithm for binary neural networks: the oil-spot algorithm.

This paper presents a constructive training algorithm for supervised neural networks. The algorithm relies on a topological approach, based on the representation of the mapping of interest onto the binary hypercube of the input space. It dynamically constructs a two-layer neural network by involving successively binary examples. A convenient treatment of real-valued data is possible by means of a suitable real-to-binary codification. In the case of target functions that have efficient halfspace union representations, simulations show the constructed networks result optimized in terms of number of neurons.     

An exact constructive algorithm for the knapsack sharing problem

In this paper, we study the knapsack sharing problem (KSP), a variant of the well-known NP-hard single knapsack problem. We propose an exact constructive tree search that combines two complementary procedures: a reduction interval search and a branch and bound. The reduction search has three phases. The first phase applies a polynomial reduction strategy that decomposes the problem into a series of knapsack problems. The second phase is a size reduction strategy that makes the resolution more efficient. The third phase is an interval reduction search that identifies a set of optimal capacities characterizing the knapsack problems. Experimental results provide computational evidence of the better performance of the proposed exact algorithm in comparison to KSPs best exact algorithm, to Cplex and to KSPs latest heuristic approach. Furthermore, they emphasize the importance of the reduction strategies.     

A constructive algorithm for training cooperative neural network ensembles

Presents a constructive algorithm for training cooperative neural-network ensembles (CNNEs). CNNE combines ensemble architecture design with cooperative training for individual neural networks (NNs) in ensembles. Unlike most previous studies on training ensembles, CNNE puts emphasis on both accuracy and diversity among individual NNs in an ensemble. In order to maintain accuracy among individual NNs, the number of hidden nodes in individual NNs are also determined by a constructive approach. Incremental training based on negative correlation is used in CNNE to train individual NNs for different numbers of training epochs. The use of negative correlation learning and different training epochs for training individual NNs reflect CNNEs emphasis on diversity among individual NNs in an ensemble. CNNE has been tested extensively on a number of benchmark problems in machine learning and neural networks, including Australian credit card assessment, breast cancer, diabetes, glass, heart disease, letter recognition, soybean, and Mackey-Glass time series prediction problems. The experimental results show that CNNE can produce NN ensembles with good generalization ability.     

基于知识规则的构造性优先排序神经网络算法

从高维空间样本点覆盖的角度,讨论了基于知识规则的构造性优先排序神经网络(PONN)算法的原理,提出了网络构造过程的一般算法以及基于随机取样规则和重心点规则的两个实例算法。实例算法对螺旋线识别和语种识别进行了仿真。实验结果证明了算法的有效性。语种识别实验结果也表明基于重心规则的PONN算法在一定条件下优于SVM。     

Asymptotic analysis of an optimized quicksort algorithm

Jon Bentley and Douglas McIlroy have implemented a fast quicksort for the C standard library in 1993. We consider here the average-case complexity in terms of number of comparisons of this algorithm, and give its asymptotic expansion up to the constant order.     

Node splitting: A constructive algorithm for feed-forward neural networks

A constructive algorithm is proposed for feed-forward neural networks which uses node-splitting in the hidden layers to build large networks from smaller ones. The small network forms an approximate model of a set of training data, and the split creates a larger, more powerful network which is initialised with the approximate solution already found. The insufficiency of the smaller network in modelling the system which generated the data leads to oscillation in those hidden nodes whose weight vectors cover regions in the input space where more detail is required in the model. These nodes are identified and split in two using principal component analysis, allowing the new nodes to cover the two main modes of the oscillating vector. Nodes are selected for splitting using principal component analysis on the oscillating weight vectors, or by examining the Hessian matrix of second derivatives of the network error with respect to the weights.     

A constructive algorithm to synthesize arbitrarily connected feedforward neural networks

In this work we present a constructive algorithm capable of producing arbitrarily connected feedforward neural network architectures for classification problems. Architecture and synaptic weights of the neural network should be defined by the learning procedure. The main purpose is to obtain a parsimonious neural network, in the form of a hybrid and dedicate linear/nonlinear classification model, which can guide to high levels of performance in terms of generalization. Though not being a global optimization algorithm, nor a population-based metaheuristics, the constructive approach has mechanisms to avoid premature convergence, by mixing growing and pruning processes, and also by implementing a relaxation strategy for the learning error. The synaptic weights of the neural networks produced by the constructive mechanism are adjusted by a quasi-Newton method, and the decision to grow or prune the current network is based on a mutual information criterion. A set of benchmark experiments, including artificial and real datasets, indicates that the new proposal presents a favorable performance when compared with alternative approaches in the literature, such as traditional MLP, mixture of heterogeneous experts, cascade correlation networks and an evolutionary programming system, in terms of both classification accuracy and parsimony of the obtained classifier.     

基于构造性形态学神经网络的一种提升算法

构造性形态学神经网络算法（CMNN）是一种数学形态学与传统的神经网络模型相结合的一种非线性神经网络,有较强的实用性。其训练算法根据形态学联想记忆而来,在测试过程中采用形态学算子将测试样本归类于训练得到的超盒之中。由于其测试过程无法正确地将落在超盒外的样本进行分类,后有人提出了一种基于模糊格的形态学神经网络（FL-CMNN）,该算法用样本与超盒的隶属度判断提高了原CMNN算法的分类效果,但增加了算法的复杂程度且分类效果不稳定。这里提出一种基于构造性形态学神经网络算法的提升算法（LCMNN）,该算法继承了原有的形态学算子运算速度快的优点且能够将落在超盒之外的样本进行准确地归类。数值实验表明,基于构造性形态学神经网络算法的提升算法（LCMNN）与其他几种算法相比,能够达到最好的分类效果,而且简单易行,计算时间少。     

Efficient MLP constructive training algorithm using a neuron recruiting approach for isolated word recognition system

This paper describes an efficient constructive training algorithm using a Multi Layer Perceptron (MLP) neural network dedicated for Isolated Word Recognition (IWR) systems. Incremental training procedure was employed and this approach was based on novel hidden neurons recruiting for a single hidden-layer. During Neural Network (NN) training phase, the number of pronunciation samples extracted from the Training Data (TD) was sequentially increased. Optimal structure of the NN classifier with optimized TD size was obtained using this proposed MLP constructive training algorithm.     

Improving learning and generalization capabilities of the C-Mantec constructive neural network algorithm

C-Mantec neural network constructive algorithm Ortega (C-Mantec neural network algorithm implementation on MATLAB. https://github.com/IvanGGomez/CmantecPaco, 2015) creates very compact architectures with generalization capabilities similar to feed-forward networks trained by the well-known back-propagation algorithm. Nevertheless, constructive algorithms suffer much from the problem of overfitting, and thus, in this work the learning procedure is first analyzed for networks created by this algorithm with the aim of trying to understand the training dynamics that will permit optimization possibilities. Secondly, several optimization strategies are analyzed for the position of class separating hyperplanes, and the results analyzed on a set of public domain benchmark data sets. The results indicate that with these modifications a small increase in prediction accuracy of C-Mantec can be obtained but in general this was not better when compared to a standard support vector machine, except in some cases when a mixed strategy is used.

     

Morphological perceptrons with competitive learning: Lattice-theoretical framework and constructive learning algorithm

A morphological neural network is generally defined as a type of artificial neural network that performs an elementary operation of mathematical morphology at every node, possibly followed by the application of an activation function. The underlying framework of mathematical morphology can be found in lattice theory.With the advent of granular computing, lattice-based neurocomputing models such as morphological neural networks and fuzzy lattice neurocomputing models are becoming increasingly important since many information granules such as fuzzy sets and their extensions, intervals, and rough sets are lattice ordered. In this paper, we present the lattice-theoretical background and the learning algorithms for morphological perceptrons with competitive learning which arise by incorporating a winner-take-all output layer into the original morphological perceptron model. Several well-known classification problems that are available on the internet are used to compare our new model with a range of classifiers such as conventional multi-layer perceptrons, fuzzy lattice neurocomputing models, k-nearest neighbors, and decision trees.