This paper presents an accurate, efficient, and scalable algorithm for minimizing a special family of convex functions, which have a lp loss function as an additive component. For this problem, well-known learning algorithms often have well-established results on accuracy and efficiency, but there exists rarely any report on explicit linear scalability with respect to the problem size. The proposed approach starts with developing a second-order learning procedure with iterative descent for general convex penalization functions, and then builds efficient algorithms for a restricted family of functions, which satisfy the Karmarkar's projective scaling condition. Under this condition, a light weight, scalable message passing algorithm (MPA) is further developed by constructing a series of simpler equivalent problems. The proposed MPA is intrinsically scalable because it only involves matrix-vector multiplication and avoids matrix inversion operations. The MPA is proven to be globally convergent for convex formulations; for nonconvex situations, it converges to a stationary point. The accuracy, efficiency, scalability, and applicability of the proposed method are verified through extensive experiments on sparse signal recovery, face image classification, and over-complete dictionary learning problems.

We propose a novel low-dimensional discriminative dictionary learning approach for multi-class classification tasks, Latent Structure based Discriminative Dictionary Learning (LS-DDL). Our approach first projects features and class labels onto a shared latent structure space, and then generates a discriminative and low-dimensional input to a discriminative dictionary learning framework. LS-DDL learns a more discriminative and lower-dimensional dictionary than existing dictionary learning methods. Therefore we obtain high recognition accuracy with a small number of low-dimensional dictionary atoms. The low dimensionality also improves the efficiency in storage and testing. In addition, the latent structure projection eliminates the classifier weighting parameter in existing discriminative dictionary learning approaches. We validate the effectiveness and efficiency of the proposed approach through a series of experiments on image-based face recognition and video-based activity recognition. Our results show that the proposed approach obtains much higher recognition accuracy with a small number of dictionary atoms, and costs much less computational time than state-of-the-art methods.

This paper introduces a minimax framework for multiclass classification, which is applicable to general data including, in particular, imagery and other types of high-dimensional data. The framework consists of estimating a representation model that minimizes the fitting errors under a class of distortions of interest to an application, and deriving subsequently categorical information based on the estimated model. A variety of commonly used regression models, including lasso, elastic net and ridge regression, can be regarded as special cases that correspond to specific classes of distortions. Optimal decision rules are derived for this classification framework. By using kernel techniques the framework can account for nonlinearity in the input space. To demonstrate the power of the framework we consider a class of signal-dependent distortions and build a new family of classifiers as new special cases. This family of new methods-minimax classification with generalized multiplicative distortions-often outperforms the state-of-the-art classification methods such as the support vector machine in accuracy. Extensive experimental results on images, gene expressions and other types of data verify the effectiveness of the proposed framework.

Subspace embedding is a powerful tool for extracting salient information from matrix, and it has numerous applications in image processing. However, its applicability has been severely limited by the computational complexity of O(N3) (N is the number of the points) which usually arises in explicitly evaluating the eigenvalues and eigenvectors. In this paper, we propose an implicit subspace embedding method which avoids explicitly evaluating the eigenvectors. Also, we show that this method can be seamlessly incorporated into the unsupervised multi-scale image segmentation framework and the resulted algorithm has a running time of genuine O(N). Moreover, we can explicitly determine the number of iterations for the algorithm by estimating the desired size of the subspace, which also controls the amount of information we want to extract for this unsupervised learning. We performed extensive experiments to verify the validity and effectiveness of our method, and we conclude that it only requires less than 120 seconds (CPU 3.2G and memory 16G) to cut a 1000∗1000 color image and orders of magnitude faster than original multi-scale image segmentation with explicit spectral decomposition while maintaining the same or a better segmentation quality.

Selecting features for multiclass classification is a critically important task for pattern recognition and machine learning applications. Especially challenging is selecting an optimal subset of features from high-dimensional data, which typically have many more variables than observations and contain significant noise, missing components, or outliers. Existing methods either cannot handle high-dimensional data efficiently or scalably, or can only obtain local optimum instead of global optimum. Toward the selection of the globally optimal subset of features efficiently, we introduce a new selector--which we call the Fisher-Markov selector--to identify those features that are the most useful in describing essential differences among the possible groups. In particular, in this paper we present a way to represent essential discriminating characteristics together with the sparsity as an optimization objective. With properly identified measures for the sparseness and discriminativeness in possibly high-dimensional settings, we take a systematic approach for optimizing the measures to choose the best feature subset. We use Markov random field optimization techniques to solve the formulated objective functions for simultaneous feature selection. Our results are noncombinatorial, and they can achieve the exact global optimum of the objective function for some special kernels. The method is fast; in particular, it can be linear in the number of features and quadratic in the number of observations. We apply our procedure to a variety of real-world data, including mid--dimensional optical handwritten digit data set and high-dimensional microarray gene expression data sets. The effectiveness of our method is confirmed by experimental results. In pattern recognition and from a model selection viewpoint, our procedure says that it is possible to select the most discriminating subset of variables by solving a very simple unconstrained objective function which in fact can be obtained with an explicit expression.

Regularization technique has become a principle tool for statistics and machine learning research and practice. However, in most situations, these regularization terms are not well interpreted, especially on how they are related to the loss function and data. In this paper, we propose a robust minimax framework to interpret the relationship between data and regularization terms for a large class of loss functions. We show that various regularization terms are essentially corresponding to different distortions to the original data matrix. This minimax framework includes ridge regression, lasso, elastic net, fused lasso, group lasso, local coordinate coding, multiple kernel learning, etc., as special cases. Within this minimax framework, we further gave mathematically exact definition for a novel representation called sparse grouping representation (SGR), and proved sufficient conditions for generating such group level sparsity. Under these sufficient conditions, a large set of consistent regularization terms can be designed. This SGR is essentially different from group lasso in the way of using class or group information, and it outperforms group lasso when there appears group label noise. We also gave out some generalization bounds in a classification setting.

Prepulse inhibition (PPI) refers to the reduction in startle reaction towards a startle-eliciting “pulse” stimulus when it is shortly preceded by a sub-threshold “prepulse” stimulus. PPI deficits have been seen in patients with schizophrenia and animal models of this mental disorder. The goal of this study was to provide an alternative method for the analysis of PPI data. The new method is expected to be more reliable and sensitive than the existing conventional method. We applied the Kernel density estimation (KDE) in the analysis of PPI data. KDE is a non-parametric method of estimating the probability density function of a random variable and is widely used in inferring population statistics based on limited, noisy samples of continuous random variables. Our results showed that the KDE method performed better than the conventional method and offered some advantages which are of significant in the post-session analysis of PPI data and in performing animal experiments.

Model-based intrusion detection and knowledge discovery are combined to cluster and classify P2P botnet traffic and other malignant network activity by using a self-organizing map (som) self-trained on denied Internet firewall log entries. The SOM analyzed new firewall log entries in a case study to classify similar network activity, and discovered previously unknown local P2P bot traffic and other security issues.

We propose a model for using firewall log entries of denied inbound Internet traffic for indirect discovery of local IP addresses that have security problems. This method is used successfully to discover two computers on the network of Southern Illinois University which were infected with malicious feral software, as well as two more IP addresses on the university network with other security problems.