In spite of many successful applications of deep learning (DL) networks, theoretical understanding of their generalization capabilities and limitations remains limited. We present analysis of generalization performance of DL networks for classification under VC-theoretical framework. In particular, we analyze the so-called "double descent" phenomenon, when large overparameterized networks can generalize well, even when they perfectly memorize all available training data. This appears to contradict conventional statistical view that optimal model complexity should reflect an optimal balance between underfitting and overfitting, i.e., the bias-variance trade-off. We present VC-theoretical explanation of double descent phenomenon, under classification setting. Our theoretical explanation is supported by empirical modeling of double descent curves, using analytic VC-bounds, for several learning methods, such as support vector machine (SVM), least squares (LS), and multilayer perceptron classifiers. The proposed VC-theoretical approach enables better understanding of overparameterized estimators during second descent.

We describe new methodology for supervised learning with sparse data, i.e., when the number of input features is (much) larger than the number of training samples (n). Under the proposed approach, all available (d) input features are split into several (t) subsets, effectively resulting in a larger number (t*n) of labeled training samples in lower-dimensional input space (of dimensionality d/t). This (modified) training data is then used to estimate a classifier for making predictions in lower-dimensional space. In this paper, standard SVM is used for training a classifier. During testing (prediction), a group of t predictions made by SVM classifier needs to be combined via intelligent post-processing rules, in order to make a prediction for a test input (in the original d-dimensional space). The novelty of our approach is in the design and empirical validation of these post-processing rules under Group Learning setting. We demonstrate that such post-processing rules effectively reflect general (common-sense) a priori knowledge (about application data). Specifically, we propose two different post-processing schemes and demonstrate their effectiveness for two real-life application domains, i.e., handwritten digit recognition and seizure prediction from iEEG signal. These empirical results show superior performance of the Group Learning approach for sparse data, under both balanced and unbalanced classification settings.

We introduce the notion of learning from contradictions, a.k.a Universum learning, for multiclass problems and propose a novel formulation for multiclass universum SVM (MU-SVM). We show that learning from contradictions (using MU-SVM) incurs lower sample complexity compared to multiclass SVM (M-SVM) by deriving the Natarajan dimension for sample complexity for PAC-learnability of MU-SVM. We also propose an analytic span bound for MU-SVM and demonstrate its utility for model selection resulting in $\sim 2-4 \times$ faster computation times than standard resampling techniques. We empirically demonstrate the efficacy of MU- SVM on several real world datasets achieving $>$ 20\% improvement in test accuracies compared to M-SVM. Insights into the underlying behavior of MU-SVM using a histograms-of-projections method are also provided.

This paper extends the idea of Universum learning to regression problems. We propose new Universum-SVM formulation for regression problems that incorporates a priori knowledge in the form of additional data samples. These additional data samples, or Universum samples, belong to the same application domain as the training samples, but they follow a different distribution. Several empirical comparisons are presented to illustrate the utility of the proposed approach.

Donor selection for Hematopoietic Stem Cell Transplant often requires physicians to manually select 3 to 5 donors from a list of 100s of genetically compatible donors as identified by HLA-based matching algorithms. The decision process is complicated by a lack of strict guidelines governing a "secondary" selection process, which is based upon non-HLA donor attributes. Our research is aimed at modeling this "secondary" decision process which can help physicians choose the right donors, based on donor attributes and historical choice behavior. Proposed black box models will help in improving selection consistency.

There is a growing interest in data-analytic modeling for prediction and/or detection of epileptic seizures from EEG recording of brain activity [1-10]. Even though there is clear evidence that many patients have changes in EEG signal prior to seizures, development of robust seizure prediction methods remains elusive [1]. We argue that the main issue for development of effective EEG-based predictive models is an apparent disconnect between clinical considerations and dataanalytic modeling assumptions. We present an SVM-based system for seizure prediction, where design choices and performance metrics are clearly related to clinical objectives and constraints. This system achieves very accurate prediction of preictal and interictal EEG segments in dogs with naturally occurring epilepsy. However, our empirical results suggest that good prediction performance may be possible only if the training data set has sufficiently many preictal segments, i.e. at least 6-7 seizure episodes.

Many machine learning applications involve analysis of high-dimensional data, where the number of input features is larger than/comparable to the number of data samples. Standard classification methods may not be sufficient for such data, and this provides motivation for nonstandard learning settings. One such new learning methodology is called learning through contradiction or Universum-support vector machine (U-SVM). Recent studies have shown U-SVM to be quite effective for sparse high-dimensional data sets. However, all these earlier studies have used balanced data sets with equal misclassification costs. This paper extends the U-SVM formulation to problems with different misclassification costs, and presents practical conditions for the effectiveness of this cost-sensitive U-SVM. Several empirical comparisons are presented to validate the proposed approach.

Survival data is common in medical applications. The challenge in applying predictive data-analytic methods to survival data is in the treatment of censored observations, since the survival times for these observations are unknown. This paper presents formalization of the analysis of survival data as a binary classification problem. For this binary classification setting, we propose a strategy for encoding censored data, leading to the SVM+/LUPI formulations. Further, we present empirical comparison of the new method and the classical Cox modeling approach for predictive modeling of survival data. These comparisons suggest that for data sets with large amount of censored data, the proposed method consistently yields better predictive performance than classical statistical modeling.

Many applications of machine learning involve analysis of sparse high-dimensional data, where the number of input features is larger than the number of data samples. Standard classification methods may not be sufficient for such data, and this provides motivation for non-standard learning settings. One such new learning methodology is called Learning through Contradictions or Universum support vector machine (U-SVM) [1, 2]. Recent studies [2-10] have shown U-SVM to be quite effective for such sparse high-dimensional data settings. However, these studies use balanced data sets with equal misclassification costs. This paper extends the U-SVM for problems with different misclassification costs, and presents practical conditions for the effectiveness of the cost sensitive U-SVM. Finally, several empirical comparisons are presented to illustrate the utility of the proposed approach.

Exploiting additional information to improve traditional inductive learning is an active research area in machine learning. In many supervised-learning applications, data can be naturally separated into several groups, or tasks, and incorporating this information into learning may improve generalization. There are many Multi-Task Learning (MTL) techniques for classification recently proposed in machine learning. This paper focuses on analysis and comparison of the two recent SVM-based MTL techniques: regularized MTL (rMTL) and SVM+ based MTL (SVM+MTL). In particular, our analysis shows how these two methods can be implemented using standard SVM software. Further, we present extensive empirical comparisons between these two methods, which relates advantages/limitations of each method to statistical characteristics of the training data.

Exploiting additional information to improve traditional inductive learning is an active research area in machine learning. In many supervised-learning applications, training data can be naturally separated into several groups, and incorporating this group information into learning may improve generalization. Recently, Vapnik proposed a general approach to formalizing such problems, known as "learning with structured data" and its support vector machine (SVM) based optimization formulation called SVM+. Liang and Cherkassky showed the connection between SVM+ and multitask learning (MTL) approaches in machine learning, and proposed an SVM-based formulation for MTL called SVM+MTL for classification. Training the SVM+MTL classifier requires the solution of a large quadratic programming optimization problem which scales as O(n(3)) with sample size n. So there is a need to develop computationally efficient algorithms for implementing SVM+MTL. This brief generalizes Platt's sequential minimal optimization (SMO) algorithm to the SVM+MTL setting. Empirical results show that, for typical SVM+MTL problems, the proposed generalized SMO achieves over 100 times speed-up, in comparison with general-purpose optimization routines.

Currently many commercial buildings are not continuously monitored for energy consumption, especially small buildings which constitute 90% of all such buildings. However, readily available data from the electric meters can be used for monitoring and analyzing energy consumption. Efficient utilization of available historical data (from these meters) can potentially improve energy efficiency, help to identify common energy wasting problems, and, in the future, enable various Smart Grid programs, such as demand response, real-time pricing etc. This paper describes application of computational intelligence techniques for prediction of electric power consumption. The proposed approach combines regression and clustering methods, in order to improve the prediction accuracy of power consumption, as a function of time (of the day) and temperature, using real-life data from several commercial and government buildings. Empirical comparisons show that the proposed approach provides an improvement over the currently used bin-based method for modeling power consumption.

This paper describes data-analytic modeling of the Minnesota soil chemical data produced by the 2001 metro soil survey. The chemical composition of the soil is characterized by the concentration of many metal and non-metal constituents, resulting in high-dimensional data. This high dimensionality and possible unknown (nonlinear) correlations in the data make it difficult to analyze and interpret using standard statistical techniques. This paper applies Self Organizing Map (SOM), to present the high-dimensional soil data in a 2D format suitable for human understanding and interpretation. This SOM representation enables analysis of the soil chemical concentration trends within the Twin Cities Metropolitan area of Minnesota. These trends are important for various Minnesota regulatory agencies concerned with the concentration of polluting chemical elements due to human activities.

Many applications of machine learning involve analysis of sparse high-dimensional data, in which the number of input features is larger than the number of data samples. Standard inductive learning methods may not be sufficient for such data, and this provides motivation for nonstandard learning settings. This paper investigates a new learning methodology called learning through contradictions or Universum support vector machine (U-SVM). U-SVM incorporates a priori knowledge about application data, in the form of additional Universum samples, into the learning process. This paper investigates possible advantages of U-SVM versus standard SVM, and describes the practical conditions necessary for the effectiveness of the U-SVM. These conditions are based on the analysis of the univariate histograms of projections of training samples onto the normal direction vector of (standard) SVM decision boundary. Several empirical comparisons are presented to illustrate the practical utility of the proposed approach.

Exploiting additional information to improve traditional inductive learning is an active research area in machine learning. In many supervised-learning applications, training data can be naturally separated into several groups, and incorporating this group information into learning may improve generalization. Recently, Vapnik proposed general approach to formalizing such problems, known as learning with structured data (LWSD) and its SVM-based optimization formulation called SVM+. Liang and Cherkassky showed empirical validation of SVM+ for classification, and its connections to multi-task learning (MTL) approaches in machine learning. This paper builds upon this recent work and describes a new methodology for regression problems, combining Vapnik's SVM+ regression and the MTL classification setting, for regression problems. We also show empirical comparisons between standard SVM regression, SVM+, and proposed SVM+MTL regression method. Practical implementation of new learning technologies, such as SVM+, is often hindered by their complexity, i.e. large number of tuning parameters (vs standard inductive SVM regression). To this end, we provide a practical scheme for model selection that combines analytic selection of parameters for SVM regression and resampling-based methods for selecting model parameters specific to SVM+ and SVM+MTL.

Many applications of machine learning involve sparse and heterogeneous data. For example, estimation of predictive (diagnostic) models using patients' data from clinical studies requires effective integration of genetic, clinical and demographic data. Typically all heterogeneous inputs are properly encoded and mapped onto a single feature vector, used for estimating (training) a predictive model. This approach, known as standard inductive learning, is used in most application studies. More recently, several new learning methodologies have emerged. In particular, when training data can be naturally separated into several groups (or structured), we can view learning (estimation) for each group as a separate task, leading to Multi-Task Learning framework. Similarly, a setting where training data is structured, but the objective is to estimate a single predictive model (for all groups), leads to Learning with Structured Data and SVM+ methodology recently proposed by Vapnik. This paper demonstrates advantages and limitations of these new data modeling approaches for modeling heterogeneous data (relative to standard inductive SVM) via empirical comparisons using several publicly available medical data sets.

We present an empirical study of gender classification of human faces, using new learning methodology called inference through contradictions, introduced in . This approach allows to incorporate a priori knowledge in the form of additional (unlabeled) samples, called the Universum, into the supervised learning process. Application of this methodology to gender classification shows that using this approach enables better generalization over standard SVM classification (using labeled data alone).

Exploiting additional information to improve traditional inductive learning is an active research in machine learning. When data are naturally separated into groups, SVM+[7] can effectively utilize this structure information to improve generalization. Alternatively, we can view learning based on data from each group as an individual task, but all these tasks are somehow related; so the same problem can also be formulated as a multi-task learning problem. Following the SVM+ approach, we propose a new multi-task learning algorithm called svm+MTL, which can be thought as an adaptation of SVM+ for solving MTL problem. The connections between SVM+ and svm+MTL are discussed and their performance is compared using synthetic data sets.

This paper investigates a new learning setting recently introduced by Vapnik [8] that takes into account a known structure of the training data to improve generalization performance. This setting is a special case of a new inference technology known aslearning with hidden information[8]suitable for many real-life applications with sparse high-dimensional data. We first briefly describe an extension of SVM called SVMγ+ [8] that is associated with this new learning setting, and verify its effectiveness using a synthetic data set. Then we demonstrate the effectiveness of SVMγ+ on a difficult real-life problem: detection of cognitive states from fMRI images obtained from different subjects. These empirical results show that the SVMγ+ approach achieves improved inter-subject generalization vs standard SVM technology.

We study the joint feature selection problem when learning multiple related classification or regression tasks. By imposing an automatic relevance determination prior on the hypothesis classes associated with each of the tasks and regularizing the variance of the hypothesis parameters, similar feature patterns across different tasks are encouraged and features that are relevant to all (or most) of the tasks are identified. Our analysis shows that the proposed probabilistic framework can be seen as a generalization of previous result from adaptive ridge regression to the multi-task learning setting. We provide a detailed description of the proposed algorithms for simultaneous model construction and justify the proposed algorithms in several aspects. Our experimental results show that this approach outperforms a regularized multi-task learning approach and the traditional methods where individual tasks are solved independently on synthetic data and the real-world data sets for lung cancer prognosis.

Classical Linear Discriminant Analysis (LDA) is not applicable for small sample size problems due to the singularity of the scatter matrices involved. Regularized LDA (RLDA) provides a simple strategy to overcome the singularity problem by applying a regularization term, which is commonly estimated via cross-validation from a set of candidates. However, cross-validation may be computationally prohibitive when the candidate set is large. An efficient algorithm for RLDA is presented that computes the optimal transformation of RLDA for a large set of parameter candidates, with approximately the same cost as running RLDA a small number of times. Thus it facilitates efficient model selection for RLDA. An intrinsic relationship between RLDA and Uncorrelated LDA (ULDA), which was recently proposed for dimension

Several kernel algorithms have recently been proposed for nonlinear discriminant analysis. However, these methods mainly address the singularity problem in the high dimensional feature space. Less attention has been focused on the properties of the resulting discriminant vectors and feature vectors in the reduced dimensional space. In this paper, we present a new formulation for kernel discriminant analysis. The proposed formulation includes, as special cases, kernel uncorrelated discriminant analysis (KUDA) and kernel orthogonal discriminant analysis (KODA). The feature vectors of KUDA are uncorrelated, while the discriminant vectors of KODA are orthogonal to each other in the feature space. We present theoretical derivations of proposed KUDA and KODA algorithms. The experimental results show that both KUDA and KODA are very competitive in comparison with other nonlinear discriminant algorithms in terms of classification accuracy.

This paper presents a methodology for estimating net asset value (NAV) of domestic mutual funds, using major stock market indices as inputs in a statistical model. The results of this study suggest that such an accurate estimation is possible, and this raises questions about the effectiveness of restrictions on frequent trading (aka market timing) introduced in the mutual fund industry.

This paper describes application of Support Vector Machines (SVM) methodology for fMRI activation detection. Whereas SVM methods have been successfully used for standard predictive learning settings (i.e., classification and regression), the goal of activation detection, strictly speaking, is not achieving improved prediction accuracy. We relate the problem of activation detection in fMRI to the problem feature selection in machine learning, and describe various multivariate supervised-learning formulations for this application. Due to extreme ill-posedness of typical fMRI data sets, the quality of activation detection will be greatly affected by (a) incorporating a priori knowledge into SVM formulations, and (b) using proper encoding for training data. We analyze these issues separately, and introduce (a) novel spatial SVM formulation (reflecting a priori knowledge about local spatial correlations in fMRI data) and (b) two new encoding schemes for fMRI data that incorporate the effects of the brain dynamics (i.e., its Hemodynamic Response Function, or HRF). The effectiveness of these modifications is clearly demonstrated using benchmark simulated and real-life fMRI data sets.

Summary form only given. This special session has been motivated by the growing importance of data-driven modeling in Earth sciences, climate modeling, meteorological and oceanographic applications, geophysical data processing, and hydrology. Of particular interest are the methodological aspects of learning methods, with the clarification of the advantages and limitations of learning techniques in the context of specific applications. This panel includes informal presentations by the session co-chairs followed by questions and answers from the audience. Topics of discussion include the following: 1) to identify major types of problems encountered in this field; 2) how to estimate the quality of data-driven models; 3) what are specific characteristics of data sets in climate modeling/Earth sciences that make them different from other applications; and 4) try to come to an agreement on possible benchmark data sets in this field.

This paper provides new characterization of data complexity for margin-based methods also known as SVMs, kernel methods etc. Under the predictive learning setting, the complexity of a given data set is directly related to model complexity, i.e. the flexibility of a set of admissible models used to describe this data. There are two distinct approaches to model complexity control: traditional model-based where complexity is controlled via parameterization of admissible models, and margin-based where complexity is controlled by the size of margin (in a specially designed empirical loss function). This paper emphasizes the role of margin for complexity control, and proposes a simple index for data complexity suitable for classification and regression problems.

This paper describes a new large margin classifier, named SVM/LDA. This classifier can be viewed as an extension of support vector machine (SVM) by incorporating some global information about the data. The SVM/LDA classifier can be also seen as a generalization of linear discriminant analysis (LDA) by incorporating the idea of (local) margin maximization into standard LDA formulation. We show that existing SVM software can be used to solve the SVM/LDA formulation. We also present empirical comparisons of the proposed algorithm with SVM and LDA using both synthetic and real world benchmark data.

This paper presents a new learning formulation for multiple model estimation (MME). Under this formulation, training data samples are generated by several (unknown) statistical models. Hence, most existing learning methods (for classification or regression) based on a single model formulation are no longer applicable. We describe a general framework for MME. Then we introduce a constructive support vector machine (SVM)-based methodology for multiple regression estimation. Several empirical comparisons using synthetic and real-life data sets are presented to illustrate the proposed approach for multiple model regression formulation.

This paper addresses selection of the loss function for regression problems with finite data. It is well-known (under standard regression formulation) that for a known noise density there exist an optimal loss function under an asymptotic setting (large number of samples), i.e. squared loss is optimal for Gaussian noise density. However, in real-life applications the noise density is unknown and the number of training samples is finite. For such practical situations, we suggest using Vapnik's /spl epsiv/-insensitive loss function. We use practical method for setting the value of /spl epsiv/ as a function of known number of samples and (known or estimated) noise variance (V. Cherkassky and Y. Ma, (2004), (2002)). We consider commonly used noise densities (such as Gaussian, Uniform and Laplacian noise). Empirical comparisons for several representative linear regression problems indicate that Vapnik's /spl epsiv/-insensitive loss yields more robust performance and improved prediction accuracy, in comparison with squared loss and least-modulus loss, especially for noisy high-dimensional data sets.

This paper describes multiple model estimation for motion analysis and segmentation (aka spatial partitioning), from point correspondences in two successive images. In motion analysis applications, available (training) data is generated by several unknown models (motions). However, the correspondence between data samples and different models (motions) is unknown. Hence, the goal of learning (motion estimation) is two-fold, i.e. estimation (learning) of unknown motions (models) and separation (segmentation) of available data into several subsets corresponding to different motions. We present the mathematical formulation for multiple motion estimation, as a problem of learning several (regression) mappings, from a single data set, and then show a constructive (SVM-based) learning algorithm developed for this setting. Experimental results show potential advantages of the proposed method.

Linear Discriminant Analysis (LDA) is a well-known method for fea- ture extraction and dimension reduction. It has been used widely in many applications such as face recognition. Recently, a novel LDA algo- rithm based on QR Decomposition, namely LDA/QR, has been proposed, which is competitive in terms of classification accuracy with other LDA algorithms, but it has much lower costs in time and space. However, LDA/QR is based on linear projection, which may not be suitable for data with nonlinear structure. This paper first proposes an algorithm called KDA/QR, which extends the LDA/QR algorithm to deal with nonlin- ear data by using the kernel operator. Then an efficient approximation of KDA/QR called AKDA/QR is proposed. Experiments on face image data show that the classification accuracy of both KDA/QR and AKDA/QR are competitive with Generalized Discriminant Analysis (GDA), a gen- eral kernel discriminant analysis algorithm, while AKDA/QR has much lower time and space costs. 1 Introduction Linear Discriminant Analysis [3] is a wellknown method for dimension reduction. It has been used widely in many applications such as face recognition [2]. Classical LDA aims to find optimal transformation by minimizing the within-class distance and maximizing the between-class distance simultaneously, thus achieving maximum discrimination. The optimal transformation can be readily computed by computing the eigen-decomposition on the scatter matrices. Although LDA works well for linear problems, it may be less effective when severe non- linearity is involved. To deal with such a limitation, nonlinear extensions through kernel functions have been proposed. The main idea of kernel-based methods is to map the input data to a feature space through a nonlinear mapping, where the inner products in the feature space can be computed by a kernel function without knowing the nonlinear mapping explic- itly [9]. Kernel Principal Component Analysis (KPCA) [10], Kernel Fisher Discriminant Analysis (KFDA) [7] and Generalized Discriminant Analysis (GDA) [1] are, respectively, kernel-based nonlinear extensions of the well known PCA, FDA and LDA methods. To our knowledge, there are few efficient algorithms for general kernel based discriminant algorithms -- most known algorithms effectively scale as O(n3) where n is the sample size. In [6, 8], S. Mika et al. made a first attempt to speed up KFDA through a greedy approximation technique. However the algorithm was developed to handle the binary clas- sification problem. For multi-class problem, the authors suggested the one against the rest scheme by considering all two-class problems. Recently, an efficient variant of LDA, namely LDA/QR, was proposed in [11, 12]. The essence of LDA/QR is the utilization of QR-decomposition on a small size matrix. The time complexity of LDA/QR is linear in the size of the training data, as well as the number of dimensions of the data. Moreover, experiments in [11, 12] show that the classification accuracy of LDA/QR is competitive with other LDA algorithms. In this paper, we first propose an algorithm, namely KDA/QR1, which is a nonlinear exten- sion of LDA/QR. Since KDA/QR involves the whole kernel matrix, which is not scalable for large datasets, we also propose an approximation of KDA/QR, namely AKDA/QR. A distinct property of AKDA/QR is that it scales as O(ndc), where n is the size of the data, d is the dimension of the data, and c is the number of classes. We apply the proposed algorithms on face image datasets and compare them with LDA/QR, and Generalized Discriminant Analysis (GDA) [1], a general method for kernel discrim- inant analysis. Experiments show that: (1) AKDA/QR is competitive with KDA/QR and GDA in classification; (2) both KDA/QR and AKDA/QR outperform LDA/QR in classifi- cation; and (3) AKDA/QR has much lower costs in time and space than GDA.

This paper describes a novel application of Statistical Learning Theory (SLT) to single motion estimation and tracking. The problem of motion estimation can be related to statistical model selection, where the goal is to select one (correct) motion model from several possible motion models, given finite noisy samples. SLT, also known as Vapnik-Chervonenkis (VC), theory provides analytic generalization bounds for model selection, which have been used successfully for practical model selection. This paper describes a successful application of an SLT-based model selection approach to the challenging problem of estimating optimal motion models from small data sets of image measurements (flow). We present results of experiments on both synthetic and real image sequences for motion interpolation and extrapolation; these results demonstrate the feasibility and strength of our approach. Our experimental results show that for motion estimation applications, SLT-based model selection compares favorably against alternative model selection methods, such as the Akaike's fpe, Schwartz' criterion (sc), Generalized Cross-Validation (gcv), and Shibata's Model Selector (sms). The paper also shows how to address the aperture problem using SLT-based model selection for penalized linear (ridge regression) formulation.

We discuss an analytic model selection for k-nearest neighbors regression method using VC generalization bounds. Whereas existing implementations of k-nn regression estimate the model complexity as n/k, where n is the number of samples, we propose a new model complexity estimate. The proposed new complexity index used as the VC-dimension in VC bounds yields a new analytic method for model selection. Empirical results for low dimensional and high dimensional data sets indicate that the proposed model selection approach provides accurate model selection that is consistently better than the previously used complexity measure. In fact, prediction accuracy of the proposed analytic method is similar to resampling (cross-validation) approach for optimal selection of k.

We propose a new method for nonlinear classification using several simple (linear) classifiers. The approach is based on a new formulation of the learning problem called multiple model estimation [V. Cherkassky and Y. Ma, 2002]. The paper describes practical implementation of this approach using an appropriate modification of standard SVM classification algorithm. Several empirical comparisons presented in this paper indicate that the proposed multiple model classification (MMC) method (using linear component models) yields better (or similar) prediction accuracy than standard nonlinear SVM classifiers. However, the main practical advantage of MMC method is that it does not require heuristic tuning of nonlinear SVM parameters (such as selection of kernel type, regularization parameter) in order to achieve good classification accuracy.

We discuss empirical comparison of analytical methods for model selection. Currently, there is no consensus on the best method for finite-sample estimation problems, even for the simple case of linear estimators. This article presents empirical comparisons between classical statistical methods - Akaike information criterion (AIC) and Bayesian information criterion (BIC) - and the structural risk minimization (SRM) method, based on Vapnik-Chervonenkis (VC) theory, for regression problems. Our study is motivated by empirical comparisons in Hastie, Tibshirani, and Friedman (2001), which claims that the SRM method performs poorly for model selection and suggests that AIC yields superior predictive performance. Hence, we present empirical comparisons for various data sets and different types of estimators (linear, subset selection, and k-nearest neighbor regression). Our results demonstrate the practical advantages of VC-based model selection; it consistently outperforms AIC for all data sets. In our study, SRM and BIC methods show similar predictive performance. This discrepancy (between empirical results obtained using the same data) is caused by methodological drawbacks in Hastie et al. (2001), especially in their loose interpretation and application of SRM method. Hence, we discuss methodological issues important for meaningful comparisons and practical application of SRM method. We also point out the importance of accurate estimation of model complexity (VC-dimension) for empirical comparisons and propose a new practical estimate of model complexity for k-nearest neighbors regression.

This paper describes a new approach for asset allocation and risk management called funds exchange. The funds exchange approach generically describes short-term trading of (broadly-based) mutual funds or indices based on statistical strategies aimed at achieving improved returns and, at the same time, reducing market risk (i.e., market exposure). Unlike many statistically-based trading and advisory systems trying to predict and benefit from the major (big) changes in the stock market, the funds exchange approach tries to capitalize on the short-term (daily) market volatility, i.e. small daily changes. This paper describes concepts and assumptions underlying this approach, and mathematical formulation of the funds exchange approach as a problem of predictive learning. Finally we show empirical evidence that the proposed approach can indeed provide improved returns and reduce market risk for SP 500 mutual funds.

This paper describes wavelet thresholding for image denoising under the framework provided by statistical learning theory a.k.a. Vapnik-Chervonenkis (VC) theory. Under the framework of VC-theory, wavelet thresholding amounts to ordering of wavelet coefficients according to their relevance to accurate function estimation, followed by discarding insignificant coefficients. Existing wavelet thresholding methods specify an ordering based on the coefficient magnitude, and use threshold(s) derived under Gaussian noise assumption and asymptotic settings. In contrast, the proposed approach uses orderings better reflecting the statistical properties of natural images, and VC-based thresholding developed for finite sample settings under very general noise assumptions. A tree structure is proposed to order the wavelet coefficients based on its magnitude, scale and spatial location. The choice of a threshold is based on the general VC method for model complexity control. Empirical results show that the proposed method outperforms Donoho's (1992, 1995) level dependent thresholding techniques and the advantages become more significant under finite sample and non-Gaussian noise settings.

VC-dimension is the measure of model complexity (capacity) used in VC-theory. The knowledge of the VC-dimension of an estimator is necessary for rigorous complexity control using analytic VC generalization bounds. Unfortunately, it is not possible to obtain the analytic estimates of the VC-dimension in most cases. Hence, a recent proposal is to measure the VC-dimension of an estimator experimentally by fitting the theoretical formula to a set of experimental measurements of the frequency of errors on artificially generated data sets of varying sizes (Vapnik, Levin, & Le Cun, 1994). However, it may be difficult to obtain an accurate estimate of the VC-dimension due to the variability of random samples in the experimental procedure proposed by Vapnik et al. (1994). We address this problem by proposing an improved design procedure for specifying the measurement points (i.e., the sample size and the number of repeated experiments at a given sample size). Our approach leads to a nonuniform design structure as opposed to the uniform design structure used in the original article (Vapnik et al., 1994). Our simulation results show that the proposed optimized design structure leads to a more accurate estimation of the VC-dimension using the experimental procedure. The results also show that a more accurate estimation of VC-dimension leads to improved complexity control using analytic VC-generalization bounds and, hence, better prediction accuracy.

This paper presents a method for computing the skeleton of planar shapes and objects which exhibit sparseness (lack of connectivity), within their image regions. Such sparseness in images may occur due to poor lighting conditions, incorrect thresholding or image subsampling. Furthermore, in document image analysis, sparse shapes are characteristic of texts faded due to aging and/or poor ink quality. Due to the lack of pixel level connectivity, conventional skeletonization techniques perform poorly on such (sparse) shapes. Given the pixel distribution for a shape, the proposed method involves an iterative evolution of a piecewise-linear approximation of the shape skeleton by using a minimum spanning tree-based self-organizing map (SOM). By constraining the SOM to lie on the edges of the Delaunay triangulation of the shape distribution, the adjacency relationships between regions in the shape are detected and used in the evolution of the skeleton. The SOM, on convergence, gives the final skeletal shape. The skeletonization is invariant to Euclidean transformations. The potential of the method is demonstrated on a variety of sparse shapes from different application domains.

The support vector machine (SVM) is a new learning methodology based on Vapnik-Chervonenkis (VC) theory (Vapnik, 1982, 1995). SVM has recently attracted growing research interest due to its ability to learn classification and regression tasks with high-dimensional data. The SVM formulation uses kernel representation. The existing algorithm leaves the choice of the kernel type and kernel parameters to the user. This paper describes an important extension to the SVM method: the multiresolution SVM (M-SVM) in which several kernels of different scales can be used simultaneously to approximate the target function. The proposed M-SVM approach enables 'automatic' selection of the 'optimal' kernel width. This usually results in better prediction accuracy of SVM models.

Multilayer perceptron (MLP) network has been successfully applied to many practical problems because of its nonlinear mapping ability. However, there are many factors, which may affect the generalization ability of MLP networks, such as the number of hidden units, the initial values of weights and the stopping rules. These factors, if improperly chosen, may result in poor generalization ability of MLP networks. It is important to identify, these factors and their interaction in order to control effectively the generalization ability of MLP network. In this paper, we have empirically identified the factors that affect the generalization ability of MLP network, and compared their relative effect on the generalization performance.

It is well known that for a given sample size there exists a model of optimal complexity corresponding to the smallest prediction (generalization) error. Hence, any method for learning from finite samples needs to have some provisions for complexity control. Existing implementations of complexity control include penalization (or regularization), weight decay (in neural networks), and various greedy procedures (aka constructive, growing, or pruning methods). There are numerous proposals for determining optimal model complexity (aka model selection) based on various (asymptotic) analytic estimates of the prediction risk and on resampling approaches. Nonasymptotic bounds on the prediction risk based on Vapnik-Chervonenkis (VC)-theory have been proposed by Vapnik. This paper describes application of VC-bounds to regression problems with the usual squared loss. An empirical study is performed for settings where the VC-bounds can be rigorously applied, i.e., linear models and penalized linear models where the VC-dimension can be accurately estimated, and the empirical risk can be reliably minimized. Empirical comparisons between model selection using VC-bounds and classical methods are performed for various noise levels, sample size, target functions and types of approximating functions. Our results demonstrate the advantages of VC-based complexity control with finite samples.

Presents a method for computing the shape skeleton of planar objects in presence of noise occurring inside the image regions. Such noise may be due to poor control of lighting conditions, incorrect thresholding or image subsampling. Binary images of objects with such noise exhibit sparseness (lack of connectivity), within their image regions. Such non-contiguity may also be observed in thresholded images of objects which consist of regions having varying albedo. The problem of obtaining the skeletal description of sparse shapes is ill posed in the sense of conventional skeletonization techniques. We propose a skeletonization method which is based on obtaining the shape skeleton by evolving an approximation of the principal curve of the shape distribution. Our method is implemented as a batch mode Kohonen self-organizing map algorithm and involves iterating the following two steps: (1) Voronoi tessellation of the data, (2) kernel smoothing on the Voronoi centroids. Adjacency relationships between the Voronoi regions are obtained by computing a Delaunay triangulation of the centroids. The Voronoi centroids are connected by a minimum spanning tree after each iteration. The final shape skeleton is obtained by joining centroids which are disjoint in the spanning tree, but have adjacent Voronoi regions. The skeletal descriptions obtained with the method are invariant to translation, rotation, and scale changes of the shape. The potential of the method is demonstrated on industrial objects having varying shape complexity under different imaging conditions.

The problem of estimating an unknown function from a finite number of noisy data points has fundamental importance for many applications. This problem has been studied in statistics, applied mathematics, engineering, artificial intelligence, and, more recently, in the fields of artificial neural networks, fuzzy systems, and genetic optimization. In spite of many papers describing individual methods, very little is known about the comparative predictive (generalization) performance of various methods. We discuss subjective and objective factors contributing to the difficult problem of meaningful comparisons. We also describe a pragmatic framework for comparisons between various methods, and present a detailed comparison study comprising several thousand individual experiments. Our approach to comparisons is biased toward general (nonexpert) users. Our study uses six representative methods described using a common taxonomy. Comparisons performed on artificial data sets provide some insights on applicability of various methods. No single method proved to be the best, since a method's performance depends significantly on the type of the target function, and on the properties of training data.

Kohonen's self-organizing map, when described in a batch processing mode, can be interpreted as a statistical kernel smoothing problem. The batch SOM algorithm consists of two steps. First, the training data are partitioned according to the Voronoi regions of the map unit locations. Second, the units are updated by taking weighted centroids of the data falling into the Voronoi regions, with the weighing function given by the neighborhood. Then, the neighborhood width is decreased and steps 1, 2 are repeated. The second step can be interpreted as a statistical kernel smoothing problem where the neighborhood function corresponds to the kernel and neighborhood width corresponds to kernel span. To determine the new unit locations, kernel smoothing is applied to the centroids of the Voronoi regions in the topological space. This interpretation leads to some new insights concerning the role of the neighborhood and dimensionality reduction. It also strengthens the algorithm's connection with the Principal Curve algorithm. A generalized self-organizing algorithm is proposed, where the kernel smoothing step is replaced with an arbitrary nonparametric regression method.

Kohonen maps have been successfully applied for data reduction and density approximation. Unfortunately, the choice of the neighborhood function and the learning rate in the Kohonen model remains empirical. We present a new statistically motivated approach to determine the contribution of each data presentation during training on the final position of the units of the trained map. Experimental results show that employing the commonly used learning rates leads to unit locations which are overly influenced by the later presentations (i.e., last 20% of data points in the finite training set). Better learning rate schedules and neighborhood functions are then determined which allow more uniform contributions of the training data on the unit locations. These improved rates are shown to be a suitable generalization of the standard rates given by stochastic approximation theory for a self-organizing map of units.

Enterprise serving with client-server as the underlying computing paradigm has become the computing model for organizations. In enterprise serving, an interconnected set of specialized and heterogeneous servers provide the computational and storage needs of client workstations, all in a transparent fashion. Asynchronous transfer mode (ATM) has the promise of capturing the total network upon which enterprise serving operates. That is, ATM can be deployed from the workstation all the way to the server. Current servers are not designed for handling high bandwidth multimedia traffic and effectively delivering the high bandwidth of the ATM network to the processor boards where applications reside. It is feasible that extending ATM into the server as the interconnect fabric and communication architecture will be a solution. This solution is further analyzed and simulation results are reported.>

Rapid evolution in the field of communication networks requires high speed switching technologies. This involves a high degree of parallelism in switching control and routing performed at the hardware level. The multistage crossbar networks have always been attractive to switch designers. In this paper a neural network approach to controlling a three-stage Clos network in real time is proposed. This controller provides optimal routing of communication traffic requests on a call-by-call basis by rearranging existing connections, with a minimum length of rearrangement sequence so that a new blocked call request can be accommodated. The proposed neural network controller uses Paull's rearrangement algorithm, along with the special (least used) switch selection rule in order to minimize the length of rearrangement sequences. The functional behavior of our model is verified by simulations and it is shown that the convergence time required for finding an optimal solution is constant, regardless of the switching network size. The performance is evaluated for random traffic with various traffic loads. Simulation results show that applying the least used switch selection rule increases the efficiency in switch rearrangements, reducing the network convergence time. The implementation aspects are also discussed to show the feasibility of the proposed approach.

Multistage interconnection networks (MINs) have long been studied for use in switching networks. Since they have a unique path between source and destination and the intermediate nodes of the paths are shared, internal blocking can cause very poor throughput. This paper proposes a high throughput ATM switch consisting of an Omega network with a new form of input queues called bypass queues. We also improve the switch throughput by partitioning the Input buffers into disjoint buffer sets and multiplexing several sets of nonblocking cells within a time slot, assuming that the routing switch operates only a couple of times faster than the transmission rate. A neural network model is presented as a controller for cell scheduling and multiplexing in the switch. Our simulation results under uniform traffic show that the proposed approach achieves almost 100% of potential switch throughput.>

The performance of two commonly used linear models of associative memories, generalized inverse (GI) and correlation matrix memory (CMM) is studied analytically in the presence of a new type of noise (training noise due to noisy training patterns). Theoretical expressions are determined for the S/N ratio gain of the GI and CMM memories in the auto-associative and hetero-associative modes of operation. It is found that the GI method performance degrades significantly in the presence of training noise while the CMM method is relatively unaffected by it. The theoretical expressions are plotted and compared with the results obtained from Monte Carlo simulations and the two are found to be in excellent agreement.>

The authors present an analytic evaluation of saturation and noise performance for a large class of associative memories based on matrix operations. The importance of using standard linear algebra techniques for evaluating noise performance of associative memories is emphasized. The authors present a detailed comparative analysis of the correlation matrix memory and the generalized inverse memory construction rules for auto-associative memory and neural classifiers. Analytic results for the noise performance of neural classifiers that can store several prototypes in one class are presented. The analysis indicates that for neural classifiers the simple correlation matrix memory provides better noise performance than the more complex generalized inverse memory.>

A novel analog computational network is presented for solving NP-complete constraint satisfaction problems, i.e. job-shop scheduling. In contrast to most neural approaches to combinatorial optimization based on quadratic energy cost function, the authors propose to use linear cost functions. As a result, the network complexity (number of neurons and the number of resistive interconnections) grows only linearly with problem size, and large-scale implementations become possible. The proposed approach is related to the linear programming network described by D.W. Tank and J.J. Hopfield (1985), which also uses a linear cost function for a simple optimization problem. It is shown how to map a difficult constraint-satisfaction problem onto a simple neural net in which the number of neural processors equals the number of subjobs (operations) and the number of interconnections grows linearly with the total number of operations. Simulations show that the authors' approach produces better solutions than existing neural approaches to job-shop scheduling, i.e. the traveling salesman problem-type Hopfield approach and integer linear programming approach of J.P.S. Foo and Y. Takefuji (1988), in terms of the quality of the solution and the network complexity.

The generalized inverse of a matrix is an extension of the ordinary square matrix inverse which applies to any matrix (e.g., singular, rectangular). The generalized inverse has numerous important applications such as regression analysis, filtering, optimization and, more recently, linear associative memories. In this latter application known as Distributed Associative Memory, stimulus vectors are associated with response vectors and the result of many associations is spread over the entire memory matrix, which is calculated as the generalized inverse. Addition/deletion of new associations requires recalculation of the generalized inverse, which becomes computationally costly for large systems. A better solution is to calculate the generalized inverse recursively. The proposed algorithm is a modification of the well known algorithm due to Rust et al. [2], originally introduced for nonrecursive computation. We compare our algorithm with Greville's recursive algorithm and conclude that our algorithm provides better numerical stability at the expense of little extra computation time and additional storage.

The authors present a novel analog computational network for solving NP-complete constraint-satisfaction problems, i.e. job-shop scheduling. In contrast to most neural approaches to combinatorial optimization based on quadratic energy cost functions, the authors propose to use linear cost functions. As a result, the network complexity (number of neurons and the number of resistive interconnections) grows only linearly with problem size, and large-scale implementations become possible. It is shown how to map a job-shop scheduling problem onto a simple neural net, where the number of neural processors equals the number of subjobs (operations) and the number of interconnections grows linearly with the total number of operations. Simulations show that the proposed approach produces better solutions than the traveling-salesman-problem-type Hopfield approach and the integer linear programming approach of Y.P. Foo and Y. Takefuji (1988) in terms of the quality of the solution and the network complexity

A multicomputer network, called rectangular CC-banyan, is presented and formally defined. A graph-theoretic approach is used to study this network's permuting and partitioning properties. It is shown that a CC-banyan has a modular structure and hence can be recursively defined. A method for evaluation of the total number of permutations in CC-banyans is presented. Using this method, the analytical expressions for the number of permutations in CC-banyans with fan-outs of two and three are derived.>

The real-time facilities of existing local area networks (LANs) which primarily address the needs of non-real-time data traffic are reviewed. An architecture called Instanet is introduced to support the needs of distributed real-time systems. Instanet incorporates a logically separate channel to arbitrate on the access rights of different priorities of traffic. An overview of the Instanet architecture is given, and analytical and simulation results of its performance under different traffic loadings are presented.>

The distributed associative memory (DAM) model is proposed for distributed and fault-tolerant computation related to retrieval tasks. The fault tolerance is with respect to noise in the input key data and/or local and global failures in the memory itself. Working models for fault-tolerant image reconfiguration and database information retrieval have been developed and backed up by experimental results that show the feasibility of such an approach.>

The performance is considered of unbuffered packet-switching nonrectangular multistage interconnection networks. Performance analysis is based on a simplified model for resolution of packet contention. An approximate closed-form analytical expression for the probability of packet acceptance is derived. Blocking characteristics of nonrectangular networks are analyzed and it is shown that for large nonrectangular networks, the probability of packet acceptance does not degrade with growth of network size.>

This correspondence analyzes the permuting properties of a reconfigurable multicomputer architecture based on a regular rectangular SW-banyan interconnection network with arbitrary fan-out and an arbitrary number of stages. An analytical expression for the total number of distinct permutations performable by a rectangular SW-banyan (in one pass) is derived. It is shown how the combinatorial power of a rectangular SW-banyan increases with the growth of its fan-out. It is also shown that a two-pass (unidirectional) rectangular SW-banyan network can be made rearrangeable by a proper choice of the feedback connection.