Pareto-Optimal Model Selection via SPRINT-Race.

In machine learning, the notion of multi-objective model selection (MOMS) refers to the problem of identifying the set of Pareto-optimal models that optimize by compromising more than one predefined objectives simultaneously. This paper introduces SPRINT-Race, the first multi-objective racing algorithm in a fixed-confidence setting, which is based on the sequential probability ratio with indifference zone test. SPRINT-Race addresses the problem of MOMS with multiple stochastic optimization objectives in the proper Pareto-optimality sense. In SPRINT-Race, a pairwise dominance or non-dominance relationship is statistically inferred via a non-parametric, ternary-decision, dual-sequential probability ratio test. The overall probability of falsely eliminating any Pareto-optimal models or mistakenly returning any clearly dominated models is strictly controlled by a sequential Holm's step-down family-wise error rate control method. As a fixed-confidence model selection algorithm, the objective of SPRINT-Race is to minimize the computational effort required to achieve a prescribed confidence level about the quality of the returned models. The performance of SPRINT-Race is first examined via an artificially constructed MOMS problem with known ground truth. Subsequently, SPRINT-Race is applied on two real-world applications: 1) hybrid recommender system design and 2) multi-criteria stock selection. The experimental results verify that SPRINT-Race is an effective and efficient tool for such MOMS problems. code of SPRINT-Race is available at https://github.com/watera427/SPRINT-Race.

Multi-Objective Model Selection via Racing.

Model selection is a core aspect in machine learning and is, occasionally, multi-objective in nature. For instance, hyper-parameter selection in a multi-task learning context is of multi-objective nature, since all the tasks' objectives must be optimized simultaneously. In this paper, a novel multi-objective racing algorithm (RA), namely S-Race, is put forward. Given an ensemble of models, our task is to reliably identify Pareto optimal models evaluated against multiple objectives, while minimizing the total computational cost. As a RA, S-Race attempts to eliminate non-promising models with confidence as early as possible, so as to concentrate computational resources on promising ones. Simultaneously, it addresses the problem of multi-objective model selection (MOMS) in the sense of Pareto optimality. In S-Race, the nonparametric sign test is utilized for pair-wise dominance relationship identification. Moreover, a discrete Holm's step-down procedure is adopted to control the family-wise error rate of the set of hypotheses made simultaneously. The significance level assigned to each family is adjusted adaptively during the race. In order to illustrate its merits, S-Race is applied on three MOMS problems: 1) selecting support vector machines for classification; 2) tuning the parameters of artificial bee colony algorithms for numerical optimization; and 3) constructing optimal hybrid recommendation systems for movie recommendation. The experimental results confirm that S-Race is an efficient and effective MOMS algorithm compared to a brute-force approach.

A Simple Method for Solving the SVM Regularization Path for Semidefinite Kernels.

The support vector machine (SVM) remains a popular classifier for its excellent generalization performance and applicability of kernel methods; however, it still requires tuning of a regularization parameter, C , to achieve optimal performance. Regularization path-following algorithms efficiently solve the solution at all possible values of the regularization parameter relying on the fact that the SVM solution is piece-wise linear in C . The SVMPath originally introduced by Hastie et al., while representing a significant theoretical contribution, does not work with semidefinite kernels. Ong et al. introduce a method improved SVMPath (ISVMP) algorithm, which addresses the semidefinite kernel; however, Singular Value Decomposition or QR factorizations are required, and a linear programming solver is required to find the next C value at each iteration. We introduce a simple implementation of the path-following algorithm that automatically handles semidefinite kernels without requiring a method to detect singular matrices nor requiring specialized factorizations or an external solver. We provide theoretical results showing how this method resolves issues associated with the semidefinite kernel as well as discuss, in detail, the potential sources of degeneracy and cycling and how cycling is resolved. Moreover, we introduce an initialization method for unequal class sizes based upon artificial variables that work within the context of the existing path-following algorithm and do not require an external solver. Experiments compare performance with the ISVMP algorithm introduced by Ong et al. and show that the proposed method is competitive in terms of training time while also maintaining high accuracy.

Multitask Classification Hypothesis Space With Improved Generalization Bounds.

This paper presents a pair of hypothesis spaces (HSs) of vector-valued functions intended to be used in the context of multitask classification. While both are parameterized on the elements of reproducing kernel Hilbert spaces and impose a feature mapping that is common to all tasks, one of them assumes this mapping as fixed, while the more general one learns the mapping via multiple kernel learning. For these new HSs, empirical Rademacher complexity-based generalization bounds are derived, and are shown to be tighter than the bound of a particular HS, which has appeared recently in the literature, leading to improved performance. As a matter of fact, the latter HS is shown to be a special case of ours. Based on an equivalence to Group-Lasso type HSs, the proposed HSs are utilized toward corresponding support vector machine-based formulations. Finally, experimental results on multitask learning problems underline the quality of the derived bounds and validate this paper's analysis.

Pareto-path multitask multiple kernel learning.

A traditional and intuitively appealing Multitask Multiple Kernel Learning (MT-MKL) method is to optimize the sum (thus, the average) of objective functions with (partially) shared kernel function, which allows information sharing among the tasks. We point out that the obtained solution corresponds to a single point on the Pareto Front (PF) of a multiobjective optimization problem, which considers the concurrent optimization of all task objectives involved in the Multitask Learning (MTL) problem. Motivated by this last observation and arguing that the former approach is heuristic, we propose a novel support vector machine MT-MKL framework that considers an implicitly defined set of conic combinations of task objectives. We show that solving our framework produces solutions along a path on the aforementioned PF and that it subsumes the optimization of the average of objective functions as a special case. Using the algorithms we derived, we demonstrate through a series of experimental results that the framework is capable of achieving a better classification performance, when compared with other similar MTL approaches.

Efficient revised simplex method for SVM training.

Existing active set methods reported in the literature for support vector machine (SVM) training must contend with singularities when solving for the search direction. When a singularity is encountered, an infinite descent direction can be carefully chosen that avoids cycling and allows the algorithm to converge. However, the algorithm implementation is likely to be more complex and less computationally efficient than would otherwise be required for an algorithm that does not have to contend with the singularities. We show that the revised simplex method introduced by Rusin provides a guarantee of nonsingularity when solving for the search direction. This method provides for a simpler and more computationally efficient implementation, as it avoids the need to test for rank degeneracies and also the need to modify factorizations or solution methods based upon those rank degeneracies. In our approach, we take advantage of the guarantee of nonsingularity by implementing an efficient method for solving the search direction and show that our algorithm is competitive with SVM-QP and also that it is a particularly effective when the fraction of nonbound support vectors is large. In addition, we show competitive performance of the proposed algorithm against two popular SVM training algorithms, SVMLight and LIBSVM.

GFAM: evolving Fuzzy ARTMAP neural networks.

This paper focuses on the evolution of Fuzzy ARTMAP neural network classifiers, using genetic algorithms, with the objective of improving generalization performance (classification accuracy of the ART network on unseen test data) and alleviating the ART category proliferation problem (the problem of creating more than necessary ART network categories to solve a classification problem). We refer to the resulting architecture as GFAM. We demonstrate through extensive experimentation that GFAM exhibits good generalization and is of small size (creates few ART categories), while consuming reasonable computational effort. In a number of classification problems, GFAM produces the optimal classifier. Furthermore, we compare the performance of GFAM with other competitive ARTMAP classifiers that have appeared in the literature and addressed the category proliferation problem in ART. We illustrate that GFAM produces improved results over these architectures, as well as other competitive classifiers.

Gap-based estimation: choosing the smoothing parameters for probabilistic and general regression neural networks.

Probabilistic neural networks (PNN) and general regression neural networks (GRNN) represent knowledge by simple but interpretable models that approximate the optimal classifier or predictor in the sense of expected value of the accuracy. These models require the specification of an important smoothing parameter, which is usually chosen by cross-validation or clustering. In this article, we demonstrate the problems with the cross-validation and clustering approaches to specify the smoothing parameter, discuss the relationship between this parameter and some of the data statistics, and attempt to develop a fast approach to determine the optimal value of this parameter. Finally, through experimentation, we show that our approach, referred to as a gap-based estimation approach, is superior in speed to the compared approaches, including support vector machine, and yields good and stable accuracy.

Experiments with Safe muARTMAP : effect of the network parameters on the network performance.

Fuzzy ARTMAP (FAM) is currently considered to be one of the premier neural network architectures in solving classification problems. One of the limitations of Fuzzy ARTMAP that has been extensively reported in the literature is the category proliferation problem. That is, Fuzzy ARTMAP has the tendency of increasing its network size, as it is confronted with more and more data, especially if the data are of the noisy and/or overlapping nature. To remedy this problem a number of researchers have designed modifications to the training phase of Fuzzy ARTMAP that had the beneficial effect of reducing this category proliferation. One of these modified Fuzzy ARTMAP architectures was the one proposed by Gomez-Sanchez, and his colleagues, referred to as Safe muARTMAP. In this paper we present reasonable analytical arguments that demonstrate of how we should choose the range of some of the Safe muARTMAP network parameters. Through a combination of these analytical arguments and experimentation we were able to identify good default parameter values for some of the Safe muARTMAP network parameters. This feat would allow one to save computations when a good performing Safe muARTMAP network is needed to be identified for a new classification problem. Furthermore, we performed an exhaustive experimentation to find the best Safe muARTMAP network for a variety of problems (simulated and real problems), and we compared it with other best performing ART networks, including other ART networks that claim to resolve the category proliferation problem in Fuzzy ARTMAP. These experimental results allow one to make appropriate statements regarding the pair-wise comparison of a number of ART networks (including Safe muARTMAP).

Pipelining of Fuzzy ARTMAP without matchtracking: correctness, performance bound, and Beowulf evaluation.

Fuzzy ARTMAP neural networks have been proven to be good classifiers on a variety of classification problems. However, the time that Fuzzy ARTMAP takes to converge to a solution increases rapidly as the number of patterns used for training is increased. In this paper we examine the time Fuzzy ARTMAP takes to converge to a solution and we propose a coarse grain parallelization technique, based on a pipeline approach, to speed-up the training process. In particular, we have parallelized Fuzzy ARTMAP without the match-tracking mechanism. We provide a series of theorems and associated proofs that show the characteristics of Fuzzy ARTMAP's, without matchtracking, parallel implementation. Results run on a BEOWULF cluster with three large databases show linear speedup as a function of the number of processors used in the pipeline. The databases used for our experiments are the Forrest CoverType database from the UCI Machine Learning repository and two artificial databases, where the data generated were 16-dimensional Gaussian distributed data belonging to two distinct classes, with different amounts of overlap (5% and 15%).

Learning tactical human behavior through observation of human performance.

It is widely accepted that the difficulty and expense involved in acquiring the knowledge behind tactical behaviors has been one limiting factor in the development of simulated agents representing adversaries and teammates in military and game simulations. Several researchers have addressed this problem with varying degrees of success. The problem mostly lies in the fact that tactical knowledge is difficult to elicit and represent through interactive sessions between the model developer and the subject matter expert. This paper describes a novel approach that employs genetic programming in conjunction with context-based reasoning to evolve tactical agents based upon automatic observation of a human performing a mission on a simulator. In this paper, we describe the process used to carry out the learning. A prototype was built to demonstrate feasibility and it is described herein. The prototype was rigorously and extensively tested. The evolved agents exhibited good fidelity to the observed human performance, as well as the capacity to generalize from it.

Boosted ARTMAP: modifications to fuzzy ARTMAP motivated by boosting theory.

In this paper, several modifications to the Fuzzy ARTMAP neural network architecture are proposed for conducting classification in complex, possibly noisy, environments. The goal of these modifications is to improve upon the generalization performance of Fuzzy ART-based neural networks, such as Fuzzy ARTMAP, in these situations. One of the major difficulties of employing Fuzzy ARTMAP on such learning problems involves over-fitting of the training data. Structural risk minimization is a machine-learning framework that addresses the issue of over-fitting by providing a backbone for analysis as well as an impetus for the design of better learning algorithms. The theory of structural risk minimization reveals a trade-off between training error and classifier complexity in reducing generalization error, which will be exploited in the learning algorithms proposed in this paper. Boosted ART extends Fuzzy ART by allowing the spatial extent of each cluster formed to be adjusted independently. Boosted ARTMAP generalizes upon Fuzzy ARTMAP by allowing non-zero training error in an effort to reduce the hypothesis complexity and hence improve overall generalization performance. Although Boosted ARTMAP is strictly speaking not a boosting algorithm, the changes it encompasses were motivated by the goals that one strives to achieve when employing boosting. Boosted ARTMAP is an on-line learner, it does not require excessive parameter tuning to operate, and it reduces precisely to Fuzzy ARTMAP for particular parameter values. Another architecture described in this paper is Structural Boosted ARTMAP, which uses both Boosted ART and Boosted ARTMAP to perform structural risk minimization learning. Structural Boosted ARTMAP will allow comparison of the capabilities of off-line versus on-line learning as well as empirical risk minimization versus structural risk minimization using Fuzzy ARTMAP-based neural network architectures. Both empirical and theoretical results are presented to enhance the understanding of these architectures.

Data-partitioning using the Hilbert space filling curves: effect on the speed of convergence of Fuzzy ARTMAP for large database problems.

The Fuzzy ARTMAP algorithm has been proven to be one of the premier neural network architectures for classification problems. One of the properties of Fuzzy ARTMAP, which can be both an asset and a liability, is its capacity to produce new nodes (templates) on demand to represent classification categories. This property allows Fuzzy ARTMAP to automatically adapt to the database without having to a priori specify its network size. On the other hand, it has the undesirable side effect that large databases might produce a large network size (node proliferation) that can dramatically slow down the training speed of the algorithm. To address the slow convergence speed of Fuzzy ARTMAP for large database problems, we propose the use of space-filling curves, specifically the Hilbert space-filling curves (HSFC). Hilbert space-filling curves allow us to divide the problem into smaller sub-problems, each focusing on a smaller than the original dataset. For learning each partition of data, a different Fuzzy ARTMAP network is used. Through this divide-and-conquer approach we are avoiding the node proliferation problem, and consequently we speedup Fuzzy ARTMAP's training. Results have been produced for a two-class, 16-dimensional Gaussian data, and on the Forest database, available at the UCI repository. Our results indicate that the Hilbert space-filling curve approach reduces the time that it takes to train Fuzzy ARTMAP without affecting the generalization performance attained by Fuzzy ARTMAP trained on the original large dataset. Given that the resulting smaller datasets that the HSFC approach produces can independently be learned by different Fuzzy ARTMAP networks, we have also implemented and tested a parallel implementation of this approach on a Beowulf cluster of workstations that further speeds up Fuzzy ARTMAP's convergence to a solution for large database problems.

Category regions as new geometrical concepts in Fuzzy-ART and Fuzzy-ARTMAP.

In this paper we introduce novel geometric concepts, namely category regions, in the original framework of Fuzzy-ART (FA) and Fuzzy-ARTMAP (FAM). The definitions of these regions are based on geometric interpretations of the vigilance test and the F2 layer competition of committed nodes with uncommitted ones, that we call commitment test. It turns out that not only these regions have the same geometrical shape (polytope structure), but they also share a lot of common and interesting properties that are demonstrated in this paper. One of these properties is the shrinking of the volume that each one of these polytope structures occupies, as training progresses, which alludes to the stability of learning in FA and FAM, a well-known result. Furthermore, properties of learning of FA and FAM are also proven utilizing the geometrical structure and properties that these regions possess; some of these properties were proven before using counterintuitive, algebraic manipulations and are now demonstrated again via intuitive geometrical arguments. One of the results that is worth mentioning as having practical ramifications is the one which states that for certain areas of the vigilance-choice parameter space (rho,a), the training and performance (testing) phases of FA and FAM do not depend on the particular choices of the vigilance parameter. Finally, it is worth noting that, although the idea of the category regions has been developed under the premises of FA and FAM, category regions are also meaningful for later developed ART neural network structures, such as ARTEMAP, ARTMAP-IC, Boosted ARTMAP, Micro-ARTMAP, Ellipsoid-ART/ARTMAP, among others.

Order of Search in Fuzzy ART and Fuzzy ARTMAP: Effect of the Choice Parameter.

This paper focuses on two ART architectures, the Fuzzy ART and the Fuzzy ARTMAP. Fuzzy ART is a pattern clustering machine, while Fuzzy ARTMAP is a pattern classification machine. Our study concentrates on the order according to which categories in Fuzzy ART, or the ART(a) model of Fuzzy ARTMAP are chosen. Our work provides a geometrical, and clearer understanding of why, and in what order, these categories are chosen for various ranges of the choice parameter of the Fuzzy ART module. This understanding serves as a powerful tool in developing properties of learning pertaining to these neural network architectures; to strengthen this argument, it is worth mentioning that the order according to which categories are chosen in ART 1 and ARTMAP provided a valuable tool in proving important properties about these architectures. Copyright 1996 Elsevier Science Ltd.