A complete characterization of statistical query learning with applications to evolvability

Statistical query (SQ) learning model of Kearns is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the examples but cannot see the examples themselves (Kearns, 1998 [29]). We describe a new and simple characterization of the query complexity of learning in the SQ learning model. Unlike the previously known bounds on SQ learning (Blum, et al., 1994; Bshouty and Feldman, 2002; Yang, 2005; Balcázar, et al., 2007; Simon, 2007 [9], [11], [42], [3], [37]) our characterization preserves the accuracy and the efficiency of learning. The preservation of accuracy implies that our characterization gives the first characterization of SQ learning in the agnostic learning framework of Haussler (1992) [23] and Kearns, Schapire and Sellie (1994) [31]. The preservation of efficiency is achieved using a new boosting technique and allows us to derive a new approach to the design of evolution algorithms in Valiant?s model of evolvability (Valiant, 2009 [40]). We use this approach to demonstrate the existence of a large class of monotone evolution algorithms based on square loss performance estimation. These results differ significantly from the few known evolution algorithms and give evidence that evolvability in Valiant?s model is a more versatile phenomenon than there had been previous reason to suspect.     

A new feature selection method for Gaussian mixture clustering

With the wide applications of Gaussian mixture clustering, e.g., in semantic video classification [H. Luo, J. Fan, J. Xiao, X. Zhu, Semantic principal video shot classification via mixture Gaussian, in: Proceedings of the 2003 International Conference on Multimedia and Expo, vol. 2, 2003, pp. 189-192], it is a nontrivial task to select the useful features in Gaussian mixture clustering without class labels. This paper, therefore, proposes a new feature selection method, through which not only the most relevant features are identified, but the redundant features are also eliminated so that the smallest relevant feature subset can be found. We integrate this method with our recently proposed Gaussian mixture clustering approach, namely rival penalized expectation-maximization (RPEM) algorithm [Y.M. Cheung, A rival penalized EM algorithm towards maximizing weighted likelihood for density mixture clustering with automatic model selection, in: Proceedings of the 17th International Conference on Pattern Recognition, 2004, pp. 633-636; Y.M. Cheung, Maximum weighted likelihood via rival penalized EM for density mixture clustering with automatic model selection, IEEE Trans. Knowl. Data Eng. 17(6) (2005) 750-761], which is able to determine the number of components (i.e., the model order selection) in a Gaussian mixture automatically. Subsequently, the data clustering, model selection, and the feature selection are all performed in a single learning process. Experimental results have shown the efficacy of the proposed approach.     

A multicriteria optimization model for cloud service provider selection in multicloud environments

Multicloud computing is a strategy that helps customers to reduce reliance on any single cloud provider (known as the vendor lock-in problem). The value of such strategy increases with proper selection of qualified service providers. In this paper, a constrained multicriteria multicloud provider selection mathematical model is proposed. Three metaheuristics algorithms (simulated annealing [SA], genetic algorithm [GA], and particle swarm optimization algorithm [PSO]) were implemented to solve the model, and their performance was studied and compared using a hypothetical case study. For the sake of comparison, Taguchi's robust design method was used to select the algorithms' parameters values, an initial feasible solution was generated using analytic hierarchy process (AHP)—as the most used method to solve the cloud provider selection problem in the literature, all three algorithms used that solution and, in order to avoid AHP limitations, another initial solution was generated randomly and used by the three algorithm in a second set of performance experiments. Results showed that SA, GA, PSO improved the AHP solution by 53.75%, 60.41%, and 60.02%, respectively, SA and PSO are robust because of reaching the same best solution in spite of the initial solution.     

Tackling the supervised label ranking problem by bagging weak learners

Preference learning is the branch of machine learning in charge of inducing preference models from data. In this paper we focus on the task known as label ranking problem, whose goal is to predict a ranking among the different labels the class variable can take. Our contribution is twofold: (i) taking as basis the tree-based algorithm LRT described in [1], we design weaker tree-based models which can be learnt more efficiently; and (ii) we show that bagging these weak learners improves not only the LRT algorithm, but also the state-of-the-art one (IBLR [1]). Furthermore, the bagging algorithm which takes the weak LRT-based models as base classifiers is competitive in time with respect to LRT and IBLR methods. To check the goodness of our proposal, we conduct a broad experimental study over the standard benchmark used in the label ranking problem literature.     

Realization of a Stochastic Model by Automata

In this paper, which continues [1] and [2], we shall construct a sequence of probabilistic automata that approximate a stochastic learning model. The construction is based on the replacement of a continual automaton (the learning model) by a finite automaton. That such a replacement is possible (and the estimate of the error involved) follows from Theorems 3.1 and 4.1 of [2], which also gives the definition of a perceptron, of a stochastic learning model (BM) and of a particular case of this model (LBM), as well as the proofs of all the theorems cited below.     

基于类比的学习式搜索算法AMO,CLSA

本文首先给出了学习式搜索的一个问题模型,然后在[5]中GLS搜索解题系统的基础上,本文描述了一个多目标学习搜索算法MO.GLSA,并对该算法作出了性能评价。最后,文中给出了一个基于类比的学习搜索算法AMO.GLSA。     

Generalized Competitive Learning of Gaussian Mixture Models

When fitting Gaussian mixtures to multivariate data, it is crucial to select the appropriate number of Gaussians, which is generally referred to as the model selection problem. Under regularization theory, we aim to solve this model selection problem through developing an entropy regularized likelihood (ERL) learning on Gaussian mixtures. We further present a gradient algorithm for this ERL learning. Through some theoretic analysis, we have shown a mechanism of generalized competitive learning that is inherent in the ERL learning, which can lead to automatic model selection on Gaussian mixtures and also make our ERL learning algorithm less sensitive to the initialization as compared to the standard expectation-maximization algorithm. The experiments on simulated data using our algorithm verified our theoretic analysis. Moreover, our ERL learning algorithm has been shown to outperform other competitive learning algorithms in the application of unsupervised image segmentation.      

Realization issues,tuning, and testing of a distributed predictive control algorithm

A non-iterative, non-cooperative distributed state-feedback control algorithm based on neighbor-to-neighbor communication, named distributed predictive control (DPC), has been recently proposed in the literature for constrained linear discrete-time systems, see  [15], [14], [2], [4]. The theoretical properties of DPC, such as convergence and stability, its extensions to the output feedback and tracking problems, and applications to simulated plants have been investigated in these papers. However, for a practical use of DPC some realization issues are still open, such as the automatic selection of some tuning parameters, the initialization of the algorithm, or its response to unexpected disturbances which could lead to the lack of the recursive feasibility, a fundamental property for any model predictive control (MPC) technique.This paper presents novel solutions to all these issues, with the goal to make DPC attractive for industrial and practical applications. Three realistic simulation examples are also discussed to evaluate the proposed numerical algorithms and to compare the performances of DPC to those of a standard centralized MPC algorithm.     

DNA sequencing and string learning

In laboratories the majority of large-scale DNA sequencing is done following theshotgun strategy, which is to sequence large amount of relatively short fragments randomly and then heuristically find a shortest common superstring of the fragments [26]. We study mathematical frameworks, under plausible assumptions, suitable for massive automated DNA sequencing and for analyzing DNA sequencing algorithms. We model the DNA sequencing problem as learning a string from its randomly drawn substrings. Under certain restrictions, this may be viewed as string learning in Valiant's distribution-free learning model and in this case we give an efficient learning algorithm and a quantitative bound on how many examples suffice. One major obstacle to our approach turns out to be a quite well-known open question on how to approximate a shortest common superstring of a set of strings, raised by a number of authors in the last 10 years [9], [29], [30]. We give the firstprovably good algorithm which approximates a shortest superstring of lengthn by a superstring of lengthO(n logn). The algorithm works equally well even in the presence of negative examples, i.e., when merging of some strings is prohibited. Some of the results presented in this paper appeared in theProceedings of the 31st IEEE Symposium on the Foundations of Computer Science, pp. 125–134, 1990 [21]. The first author was supported in part by NSERC Operating Grant OGP0046613. The second author was supported in part by NSERC Operating Grants OGP0036747 and OGP0046506.     

Nonlinear model structure design and construction using orthogonal least squares and D-optimality design

A very efficient learning algorithm for model subset selection is introduced based on a new composite cost function that simultaneously optimizes the model approximation ability and model robustness and adequacy. The derived model parameters are estimated via forward orthogonal least squares, but the model subset selection cost function includes a D-optimality design criterion that maximizes the determinant of the design matrix of the subset to ensure the model robustness, adequacy, and parsimony of the final model. The proposed approach is based on the forward orthogonal least square (OLS) algorithm, such that new D-optimality-based cost function is constructed based on the orthogonalization process to gain computational advantages and hence to maintain the inherent advantage of computational efficiency associated with the conventional forward OLS approach. Illustrative examples are included to demonstrate the effectiveness of the new approach.     

The influence of the radial basis function training strategy on the performance of a neural gripper

In this article, a neural network-based grasping system that is able to collect objects of arbitrary shape is introduced. The grasping process is split into three functional blocks: image acquisition and processing, contact point estimation, and contact force determination. The paper focuses on the second block, which contains two neural networks. A competitive Hopfield neural network first determines an approximate polygon for an object outline. These polygon edges are the input for a supervised neural network model [radial basis function (RBF) or multilayer perceptions], which then defines the contact points. Tests were conducted with objects of different shapes, and experimental results suggest that the performance of the neural gripper and its learning rate are significantly influenced by the choice of supervised training model and RBF learning algorithm.     

BYY Harmony Learning on Finite Mixture: Adaptive Gradient Implementation and A Floating RPCL Mechanism

In tackling the learning problem on a set of finite samples, Bayesian Ying-Yang (BYY) harmony learning has developed a new learning mechanism that makes model selection implemented either automatically during parameter learning or in help of evaluating a new class of model selection criteria. In this paper, parameter learning with automated model selection has been studied for finite mixture model via an adaptive gradient learning algorithm for BYY harmony learning on a specific bidirectional architecture (BI-architecture). Via theoretical analysis, it has shown that the adaptive gradient learning implements a mechanism of floating rival penalized competitive learning (RPCL) among the components in the mixture. Also, the simulation results are demonstrated well for the adaptive gradient algorithm on the sample data sets from Gaussian mixtures with certain degree of overlap. Moreover, the adaptive gradient algorithm is applied to classification of the Iris data and unsupervised color image segmentation.     

支持向量机最优模型选择的研究

通过对核矩阵的研究,利用核矩阵的对称正定性,采用核校准的方法提出了一种SVM最优模型选择的算法——OMSA算法．利用训练样本不通过SVM标准训练和测试过程而寻求最优的核参数和相应的最优学习模型,弥补了传统SVM在模型选择上经验性强和计算量大的不足．采用该算法在UCI标准数据集和FERET标准人脸库上进行了实验,结果表明,通过该算法找到的核参数以及相应的核矩阵是最优的,得到的SVM分类器的错误率最小．该算法为SVM最优模型选择提供了一种可行的方法,同时对其他基于核的学习方法也具有一定的参考价值．     

Decision tree based light weight intrusion detection using a wrapper approach

The objective of this paper is to construct a lightweight Intrusion Detection System (IDS) aimed at detecting anomalies in networks. The crucial part of building lightweight IDS depends on preprocessing of network data, identifying important features and in the design of efficient learning algorithm that classify normal and anomalous patterns. Therefore in this work, the design of IDS is investigated from these three perspectives. The goals of this paper are (i) removing redundant instances that causes the learning algorithm to be unbiased (ii) identifying suitable subset of features by employing a wrapper based feature selection algorithm (iii) realizing proposed IDS with neurotree to achieve better detection accuracy. The lightweight IDS has been developed by using a wrapper based feature selection algorithm that maximizes the specificity and sensitivity of the IDS as well as by employing a neural ensemble decision tree iterative procedure to evolve optimal features. An extensive experimental evaluation of the proposed approach with a family of six decision tree classifiers namely Decision Stump, C4.5, Naive Baye’s Tree, Random Forest, Random Tree and Representative Tree model to perform the detection of anomalous network pattern has been introduced.     

Deep convolutional learning for general early design stage prediction models

Designers rely on performance predictions to direct the design toward appropriate requirements. Machine learning (ML) models exhibit the potential for rapid and accurate predictions. Developing conventional ML models that can be generalized well in unseen design cases requires an effective feature engineering and selection. Identifying generalizable features calls for good domain knowledge by the ML model developer. Therefore, developing ML models for all design performance parameters with conventional ML will be a time-consuming and expensive process. Automation in terms of feature engineering and selection will accelerate the use of ML models in design.Deep learning models extract features from data, which aid in model generalization. In this study, we (1) evaluate the deep learning model’s capability to predict the heating and cooling demand on unseen design cases and (2) obtain an understanding of extracted features. Results indicate that deep learning model generalization is similar to or better than that of a simple neural network with appropriate features. The reason for the satisfactory generalization using the deep learning model is its ability to identify similar design options within the data distribution. The results also indicate that deep learning models can filter out irrelevant features, reducing the need for feature selection.     

Evolutionary extreme learning machine

Extreme learning machine (ELM) [G.-B. Huang, Q.-Y. Zhu, C.-K. Siew, Extreme learning machine: a new learning scheme of feedforward neural networks, in: Proceedings of the International Joint Conference on Neural Networks (IJCNN2004), Budapest, Hungary, 25-29 July 2004], a novel learning algorithm much faster than the traditional gradient-based learning algorithms, was proposed recently for single-hidden-layer feedforward neural networks (SLFNs). However, ELM may need higher number of hidden neurons due to the random determination of the input weights and hidden biases. In this paper, a hybrid learning algorithm is proposed which uses the differential evolutionary algorithm to select the input weights and Moore-Penrose (MP) generalized inverse to analytically determine the output weights. Experimental results show that this approach is able to achieve good generalization performance with much more compact networks.     

An Approximation Algorithm for Circular Arc Colouring

We consider the problem of colouring a family of n arcs of a circle. This NP-complete problem, which occurs in routing and network design problems, is modelled as a 0-1 integer multicommodity flow problem. We present an algorithm that routes the commodities in the network by augmenting the network with some extra edges which correspond to extra colours. The algorithm, which relies on probabilistic techniques such as randomized rounding and path selection, is a randomized approximation algorithm which has an asymptotic performance ratio of 1+1/e (approximately 1.37) except when the minimum number of colours required is very small (O(\ln n) ). This is an improvement over the best previously known result [7], which is a deterministic approximation algorithm with a performance ratio of 3/2. The substantial improvement is valuable, for instance in wavelength allocation strategies in communication networks where bandwidth is a precious resource. Received October 25, 1998; revised August 26, 1999, and April 17, 2000.     

Image deblurring with filters learned by extreme learning machine

Image deblurring is a basic and important task of image processing. Traditional filtering based image deblurring methods, e.g. enhancement filters, partial differential equation (PDE) and etc., are limited by the hypothesis that natural images and noise are with low and high frequency terms, respectively. Noise removal and edge protection are always the dilemma for traditional models.In this paper, we study image deblurring problem from a brand new perspective—classification. And we also generalize the traditional PDE model to a more general case, using the theories of calculus of variations. Furthermore, inspired by the theories of approximation of functions, we transform the operator-learning problem into a coefficient-learning problem by means of selecting a group of basis, and build a filter-learning model. Based on extreme learning machine (ELM) [1], [2], [3] and [4], an algorithm is designed and a group of filters are learned effectively. Then a generalized image deblurring model, learned filtering PDE (LF-PDE), is built.The experiments verify the effectiveness of our models and the corresponding learned filters. It is shown that our model can overcome many drawbacks of the traditional models and achieve much better results.     

支持向量学习的多参数同时调节

模型选择是支持向量学习的关键问题.已有模型选择方法采用嵌套的双层优化框架,内层执行支持向量学习,外层通过最小化泛化误差的估计进行模型选择.该框架过程复杂,计算效率低.简化传统的双层优化框架,提出一个支持向量学习的多参数同时调节方法,在同一优化过程中实现模型选择和学习器训练.首先,将支持向量学习中的参数和超参数合并为一个参数向量,利用序贯无约束极小化技术(sequential unconstrained minimization technique,简称SUMT)分别改写支持向量分类和回归的有约束优化问题,得到多参数同时调节模型的多元无约束形式定义;然后,证明多参数同时调节模型目标函数的局部Lipschitz连续性及水平集有界性.在此基础上,应用变尺度方法(variable metric method,简称VMM)设计并实现了多参数同时调节算法.进一步地,基于多参数同时调节模型的性质,证明了算法收敛性,对比分析了算法复杂性.最后,实验验证同时调节算法的收敛性,并实验对比同时调节算法的有效性.理论证明和实验分析表明,同时调节方法是一种坚实、高效的支持向量模型选择方法.     

最大熵和l2,0范数约束的无监督特征选择算法

无监督特征选择可以降低数据维数,提高算法的学习性能,是机器学习和模式识别等领域中的重要研究课题。和大多数在目标函数中引入稀疏正则化解决松弛问题的方法不同,提出了一种基于最大熵和l2,0范数约束的无监督特征选择算法。使用具有唯一确定含义的l2,0范数等式约束,即选择特征的数量,不涉及正则化参数的选取,避免调整参数。结合谱分析探索数据的局部几何结构并基于最大熵原理自适应的构造相似矩阵。通过增广拉格朗日函数法,设计了一种交替迭代优化算法对模型求解。在四个真实数据集上与其他几种无监督特征选择算法的对比实验,验证了所提算法的有效性。