On boosting kernel density methods for multivariate data: density estimation and classification

Statistical learning is emerging as a promising field where a number of algorithms from machine learning are interpreted as statistical methods and vice-versa. Due to good practical performance, boosting is one of the most studied machine learning techniques. We propose algorithms for multivariate density estimation and classification. They are generated by using the traditional kernel techniques as weak learners in boosting algorithms. Our algorithms take the form of multistep estimators, whose first step is a standard kernel method. Some strategies for bandwidth selection are also discussed with regard both to the standard kernel density classification problem, and to our 'boosted' kernel methods. Extensive experiments, using real and simulated data, show an encouraging practical relevance of the findings. Standard kernel methods are often outperformed by the first boosting iterations and in correspondence of several bandwidth values. In addition, the practical effectiveness of our classification algorithm is confirmed by a comparative study on two real datasets, the competitors being trees including AdaBoosting with trees.     

A classifier for multi-dimensional datasets based on Bayesian multiple kernel grouping learning

This paper proposes an algorithm for the classification of multi-dimensional datasets based on the conjugate Bayesian Multiple Kernel Grouping Learning (BMKGL). Using conjugate Bayesian framework improves the computation efficiency. Multiple kernels instead of a single kernel avoid the kernel selection problem which is also a computationally expensive work. Through grouping parameter learning, BMKGL can simultaneously integrate information from different dimensions and find the dimensions which contribute more to the variations of the outcome for the purpose of interpretable property. Meanwhile, BMKGL can select the most suitable combination of kernels for different dimensions so as to extract the most appropriate measure for each dimension and improve the accuracy of classification results. The simulation results illustrate that our learning process has better performance in prediction results and stability compared to some popular classifiers, such as k-nearest neighbours algorithm, support vector machine algorithm and naive Bayes classifier. BMKGL also outperforms previous methods in terms of accuracy and interpretation for the heart disease and EEG datasets.     

On the regularized Laplacian eigenmaps

To find an appropriate low-dimensional representation for complex data is one of the central problems in machine learning and data analysis. In this paper, a nonlinear dimensionality reduction algorithm called regularized Laplacian eigenmaps (RLEM) is proposed, motivated by the method for regularized spectral clustering. This algorithm provides a natural out-of-sample extension for dealing with points not in the original data set. The consistency of the RLEM algorithm is investigated. Moreover, a convergence rate is established depending on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers. Experiments are given to illustrate our algorithm.     

Learning rates of multi-kernel regression by orthogonal greedy algorithm

We investigate the problem of regression from multiple reproducing kernel Hilbert spaces by means of orthogonal greedy algorithm. The greedy algorithm is appealing as it uses a small portion of candidate kernels to represent the approximation of regression function, and can greatly reduce the computational burden of traditional multi-kernel learning. Satisfied learning rates are obtained based on the Rademacher chaos complexity and data dependent hypothesis spaces.     

Least-square regularized regression with non-iid sampling

We study the least-square regression learning algorithm generated by regularization schemes in reproducing kernel Hilbert spaces. A non-iid setting is considered: the sequence of probability measures for sampling is not identical and the sampling may be dependent. When the sequence of marginal distributions for sampling converges exponentially fast in the dual of a Hölder space and the sampling process satisfies a polynomial strong mixing condition, we derive learning rates for the learning algorithm.     

具有核化函数的部分线性模型及其应用

本文基于再生核希尔伯特空间中的再生核，将核技巧与高斯-赛责尔迭代算法相结合，提出了具有核化函数的部分线性模型（PLMKF）及其算法收敛性条件等相关内容，具体包括：（1）基于OLS的PLMKF；（2）基于岭估计的PLMKF；（3）基于GLS的PLMKF；（4）基于多核学习的PLMKF。它们构成了PLMKF家族，具有一定的相互转化关系。在数值模拟中，本文验证了各个算法的有效性，比较了基于OLS与GLS、单核与多核的PLMKF模拟结果。实际应用中，在大幅外推情景下，PLMKF仍保持了良好的泛化能力，预测精度高于PLM、GAM和SVR。     

A new algorithm for clustering based on kernel density estimation

In this paper, we present an algorithm for clustering based on univariate kernel density estimation, named ClusterKDE. It consists of an iterative procedure that in each step a new cluster is obtained by minimizing a smooth kernel function. Although in our applications we have used the univariate Gaussian kernel, any smooth kernel function can be used. The proposed algorithm has the advantage of not requiring a priori the number of cluster. Furthermore, the ClusterKDE algorithm is very simple, easy to implement, well-defined and stops in a finite number of steps, namely, it always converges independently of the initial point. We also illustrate our findings by numerical experiments which are obtained when our algorithm is implemented in the software Matlab and applied to practical applications. The results indicate that the ClusterKDE algorithm is competitive and fast when compared with the well-known Clusterdata and K-means algorithms, used by Matlab to clustering data.     

Encoding dissimilarity data for statistical model building

We summarize, review and comment upon three papers which discuss the use of discrete, noisy, incomplete, scattered pairwise dissimilarity data in statistical model building. Convex cone optimization codes are used to embed the objects into a Euclidean space which respects the dissimilarity information while controlling the dimension of the space. A “newbie” algorithm is provided for embedding new objects into this space. This allows the dissimilarity information to be incorporated into a smoothing spline ANOVA penalized likelihood model, a support vector machine, or any model that will admit reproducing kernel Hilbert space components, for nonparametric regression, supervised learning, or semisupervised learning. Future work and open questions are discussed. The papers are:     

Adaptive sequential Monte Carlo by means of mixture of experts

Appropriately designing the proposal kernel of particle filters is an issue of significant importance, since a bad choice may lead to deterioration of the particle sample and, consequently, waste of computational power. In this paper we introduce a novel algorithm adaptively approximating the so-called optimal proposal kernel by a mixture of integrated curved exponential distributions with logistic weights. This family of distributions, referred to as mixtures of experts, is broad enough to be used in the presence of multi-modality or strongly skewed distributions. The mixtures are fitted, via online-EM methods, to the optimal kernel through minimisation of the Kullback-Leibler divergence between the auxiliary target and instrumental distributions of the particle filter. At each iteration of the particle filter, the algorithm is required to solve only a single optimisation problem for the whole particle sample, yielding an algorithm with only linear complexity. In addition, we illustrate in a simulation study how the method can be successfully applied to optimal filtering in nonlinear state-space models.     

A Monte Carlo Markov chain algorithm for a class of mixture time series models

This article generalizes the Monte Carlo Markov Chain (MCMC) algorithm, based on the Gibbs weighted Chinese restaurant (gWCR) process algorithm, for a class of kernel mixture of time series models over the Dirichlet process. This class of models is an extension of Lo’s (Ann. Stat. 12:351–357, 1984) kernel mixture model for independent observations. The kernel represents a known distribution of time series conditional on past time series and both present and past latent variables. The latent variables are independent samples from a Dirichlet process, which is a random discrete (almost surely) distribution. This class of models includes an infinite mixture of autoregressive processes and an infinite mixture of generalized autoregressive conditional heteroskedasticity (GARCH) processes.     

EM algorithms for beta kernel distributions

The EM algorithm is employed to compute maximum-likelihood estimates for beta kernel distributions. Estimation is considered under two censoring schemes: the progressive Type-I censoring and progressive Type-II right censoring schemes. As an application, the EM algorithm is executed to obtain maximum-likelihood estimates for the beta Weibull distribution under the two censoring schemes. A simulation study and two real data sets are used to show the efficiency of the EM algorithm.     

MulticlusterKDE: a new algorithm for clustering based on multivariate kernel density estimation

In this paper, we propose the MulticlusterKDE algorithm applied to classify elements of a database into categories based on their similarity. MulticlusterKDE is centered on the multiple optimization of the kernel density estimator function with multivariate Gaussian kernel. One of the main features of the proposed algorithm is that the number of clusters is an optional input parameter. Furthermore, it is very simple, easy to implement, well defined and stops at a finite number of steps and it always converges regardless of the data set. We illustrate our findings by implementing the algorithm in R software. The results indicate that the MulticlusterKDE algorithm is competitive when compared to K-means, K-medoids, CLARA, DBSCAN and PdfCluster algorithms. Features such as simplicity and efficiency make the proposed algorithm an attractive and promising research field that can be used as basis for its improvement and also for the development of new density-based clustering algorithms.     

对支持向量机混合核函数方法的再评估

混合核函数方法并没有解决核函数的选择问题,只是将问题等价转换为权重参数的选择。同时该方法还需要分别为两个核函数确定参数,大大增加了算法的复杂程度,限制了支持向量机的泛化能力。事实上,调节核函数的参数对分类结果的影响要远大于选择什么类型的核函数,因此混合核函数方法实属“避轻就重”。实证分析表明,不同核函数对应的共同支持向量比例很高,存在很大程度的一致性,线性组合的意义并不大,这也是混合核函数方法无法有效提升分类性能的一个重要原因。     

Using pseudometrics in kernel density estimation

Common kernel density estimators (KDE) are generalised, which involve that assumptions on the kernel of the distribution can be given. Instead of using metrics as input to the kernels, the new estimators use parameterisable pseudometrics. In general, the volumes of the balls in pseudometric spaces are dependent on both the radius and the location of the centre. To enable constant smoothing, the volumes of the balls need to be calculated and analytical expressions are preferred for computational reasons. Two suitable parametric families of pseudometrics are identified. One of them has common KDE as special cases. In a few experiments, the proposed estimators show increased statistical power when proper assumptions are made. As a consequence, this paper describes an approach, where partial knowledge about the distribution can be used effectively. Furthermore, it is suggested that the new estimators are adequate for statistical learning algorithms such as regression and classification.     

Kernel density classification and boosting: an L2 analysis

Kernel density estimation is a commonly used approach to classification. However, most of the theoretical results for kernel methods apply to estimation per se and not necessarily to classification. In this paper we show that when estimating the difference between two densities, the optimal smoothing parameters are increasing functions of the sample size of the complementary group, and we provide a small simluation study which examines the relative performance of kernel density methods when the final goal is classification.A relative newcomer to the classification portfolio is boosting, and this paper proposes an algorithm for boosting kernel density classifiers. We note that boosting is closely linked to a previously proposed method of bias reduction in kernel density estimation and indicate how it will enjoy similar properties for classification. We show that boosting kernel classifiers reduces the bias whilst only slightly increasing the variance, with an overall reduction in error. Numerical examples and simulations are used to illustrate the findings, and we also suggest further areas of research.     

A Study on SMO Algorithm for Solving ϵ-SVR with Non-PSD Kernels

Sequential minimal optimization (SMO) algorithm is effective in solving large-scale support vector machine (SVM). The existing algorithms all assume that the kernels are positive definite (PD) or positive semi-definite (PSD) and should meet the Mercer condition. Some kernels, however, such as sigmoid kernel, which originates from neural network and then is extensively used in SVM, are conditionally PD in certain circumstances; in addition, practically, it is often difficult to prove whether a kernel is PD or PSD or not except some well-known kernels. So, the applications of the existing algorithm of SMO are limited. Considering the deficiency of the traditional ones, this algorithm of solving ?-SVR with nonpositive semi-definite (non-PSD) kernels is proposed. Different from the existing algorithms which must consider four Lagrange multipliers, the algorithm proposed in this article just need to consider two Lagrange multipliers in the process of implementation. The proposed algorithm simplified the implementation by expanding the original dual programming of ?-SVR and solving its KKT conditions, thus being easily applied in solving ?-SVR with non-PSD kernels. The presented algorithm is evaluated using five benchmark problems and one reality problem. The results show that ?-SVR with non-PSD provides more accurate prediction than that with PD kernel.     

基于核和灰度的灰色异构数据代数运算法则及其应用

为解决灰色异构数据的建模问题,应用"核和灰度"对灰色异构数据代数运算法则及其性质展开研究。将灰信息表征为"核和灰度",通过"核"将灰色异构数据代数运算转换为实数之间代数运算,根据灰度不减公理确定运算结果之灰度,在此基础上构建灰色异构数据的代数运算法则,并将该法则应用于灰色异构数据预测模型的构建及空气质量指数(AQI)的预测。研究成果对丰富与完善灰色系统基础理论具有积极意义。     

A new strategy for speeding Markov chain Monte Carlo algorithms

Markov chain Monte Carlo (MCMC) methods have become popular as a basis for drawing inference from complex statistical models. Two common difficulties with MCMC algorithms are slow mixing and long run-times, which are frequently closely related. Mixing over the entire state space can often be aided by careful tuning of the chain's transition kernel. In order to preserve the algorithm's stationary distribution, however, care must be taken when updating a chain's transition kernel based on that same chain's history. In this paper we introduce a technique that allows the transition kernel of the Gibbs sampler to be updated at user specified intervals, while preserving the chain's stationary distribution. This technique seems to be beneficial both in increasing efficiency of the resulting estimates (via Rao-Blackwellization) and in reducing the run-time. A reinterpretation of the modified Gibbs sampling scheme introduced in terms of auxiliary samples allows its extension to the more general Metropolis-Hastings framework. The strategies we develop are particularly helpful when calculation of the full conditional (for a Gibbs algorithm) or of the proposal distribution (for a Metropolis-Hastings algorithm) is computationally expensive. Partial financial support from FAR 2002-3, University of Insubria is gratefully acknowledged.     

Local likelihood density estimation for interval censored data

The authors propose a class of procedures for local likelihood estimation from data that are either interval‐censored or that have been aggregated into bins. One such procedure relies on an algorithm that generalizes existing self‐consistency algorithms by introducing kernel smoothing at each step of the iteration. The entire class of procedures yields estimates that are obtained as solutions of fixed point equations. By discretizing and applying numerical integration, the authors use fixed point theory to study convergence of algorithms for the class. Rapid convergence is effected by the implementation of a local EM algorithm as a global Newton iteration. The latter requires an explicit solution of the local likelihood equations which can be found by using the symbolic Newton‐Raphson algorithm, if necessary.