In the rapidly evolving realm of machine learning, algorithm effectiveness often faces limitations due to data quality and availability. Traditional approaches grapple with data sharing due to legal and privacy concerns. The federated learning framework addresses this challenge. Federated learning is a decentralized approach where model training occurs on client sides, preserving privacy by keeping data localized. Instead of sending raw data to a central server, only model updates are exchanged, enhancing data security. We apply this framework to Sparse Principal Component Analysis (SPCA) in this work. SPCA aims to attain sparse component loadings while maximizing data variance for improved interpretability. Beside the l1norm regularization term in conventional SPCA, we add a smoothing function to facilitate gradient-based optimization methods. Moreover, in order to improve computational efficiency, we introduce a least squares approximation to original SPCA. This enables analytic solutions on the optimization processes, leading to substantial computational improvements. Within the federated framework, we formulate SPCA as a consensus optimization problem, which can be solved using the Alternating Direction Method of Multipliers (ADMM). Our extensive experiments involve both IID and non-IID random features across various data owners. Results on synthetic and public datasets affirm the efficacy of our federated SPCA approach.

Nowadays, machine learning performs astonishingly well in many different fields. In general, the more data we have, our machine learning methods will show better results. However, in many situations, the data owners may not want to or not allow to share their data because of legal issues or privacy concerns. However, if we can pool all the data together as the training data for the machine learning task we will have a better result. In the other situation, we encounter an extremely large dataset, which is difficult to store in a single machine. We may utilize more computing units to solve it. To deal with these two problems, we propose the distributed consensus reduced support vector machine (DCRSVM), which is a nonlinear model for binary classification. We apply the ADMM, Alternating Direction Method of Multipliers, to solve the DCRSVM. In each iteration, the local worker will update their model by incorporating the information shared by the master. The local workers only share their models in each iteration but never share their data. The master will fuse the local models reported by the local workers. At the end, the master will generate the consensus model that almost identical to the model generated by pooling all data together. Pooling all data together is not allowed in many real world applications.

Active Learning (AL) is a machine learning framework that aims to efficiently select a limited labeled data to construct an effective model given huge amount of unlabeled data on the side. Most studies in AL focus on how to select the unlabeled data to be labeled by a human oracle in order to maximize the performance gain of the model with as little labeling effort as possible. In this work, however, we focus not only on how to select appropriate data instances but also how to select informative features, more specifically, categorical features to be labeled by the oracle in a unified manner. The unification means that we select the best choice of item to label where the item can be either a feature or an instance on each iteration given a unified scoring function to make the decision. The method that we propose is by synthesizing new instances that represent a set of features. By utilizing synthesized instances, we can treat this set of features as if they are regular instances. Therefore they could be compared on an equal ground when the model tries to select which instances to be labeled by the oracle. The features used to build the synthesized instances need to be carefully selected so the resulting synthesized instances could improve the model and not introducing any contradicting information. We utilize hierarchical clustering in order to group features that own similar content. This is done first by picking clusters whose label purity are estimated to be high. Then we score a feature based on how common the feature is in the cluster and how related the feature is to the estimated majority label. The top scoring features will then be used to synthesize instances. We demonstrate the effectiveness of the proposed method through a few data sets that consist of only categorical features where the feature labeling makes more sense to labeling oracles. The experiment results show that adopting the unified approach creates clear benefit to model construction, especially in the early stage where we can efficiently obtain an effective model through only a few iterations, compared to the one using only instance labeling for model construction.

Active learning is a common strategy to deal with large-scale data with limited labeling effort. In each iteration of active learning, a query is ready for oracle to answer such as what the label is for a given unlabeled data. Given the method, we can request the labels only for those data that are essential and save the labeling effort from oracle. We focus on pool-based active learning where a set of unlabeled data is selected for querying in each run of active learning. To apply pool-based active learning to massive high-dimensional data, especially when the unlabeled data set is much larger than the labeled set, we propose the APRAL and MLP strategies so that the computation for active learning can be dramatically reduced while keeping the model power more or less the same. In APRAL, we avoid unnecessary data re-ranking given an unlabeled data selection criteria. To further improve the efficiency, with MLP, we organize the unlabeled data in a multi-layer pool based on a dimensionality reduction technique and the most valuable data to know their label information are more likely to store in the top layers. Given the APRAL and MLP strategies, the active learning computation time is reduced by about 83% if compared to the traditional active learning ones; at the same time, the model effectiveness remains.

The time series classification has been studied for various applications in the last decades. In the time series classification problem, we decide the class information based on a small piece of the time series inputs. In general, the approaches to time series classification can be categorized into three types, distance-based, model-based, and feature-based approaches. In this research, we focus on the feature-based methods, which represent time series as a set of characterized values. It is quite often the case that features generated by existing representation techniques are not transparent to domain experts and the feature that are selected for classification are not completely interpretable. We aim to propose a novel time series representation, called Envelope to solve the problem. The proposed supervised feature extraction method transforms time series into simple 1/0/-1 values. A heuristic is introduced to determine the most appropriate representation which includes the features that are the best to discriminate data of different labels. Moreover, this new representation enjoys the characteristic of sparsity which is an essential property when we need to apply compressed sensing techniques. With this advantage, we can benefit from high transmission efficiency, the reduction of required storage and model complexity. We conduct a series of tests on various benchmark time series data to show the effectiveness of the proposed method. Other than the classification effectiveness, we demonstrate how to visualize the similarity between time series of the same and different kinds from the proposed Envelope method.

Drivers dream of foreseeing traffic condition to enjoy efficient driving experience at all times. Given the historical patterns for different locations and different time, people should be able to guess the possible traffic speed in a near future moment. What is difficult and interesting for this task is that we need to filter the useful data that could help us for the next moment traffic speed prediction from a massive amount of historical data. On the other hand, the traffic condition could be highly dynamic and we can only give a reliable traffic prediction by using the most updated model for prediction. This implies that frequent retraining is necessary. To conquer the task, we propose a lazy learning approach for traffic speed prediction given massive historical data. The approach integrates the kNN and Gaussian process regression for efficient and robust traffic speed prediction. kNN can help us to select the most informative data for Gaussian process Regression using a big data framework. Thanks for the most recent progress of big data research, the processing of massive data for prediction in close to real time has become possible now compared to any time in the past. We aim at using a Hadoop framework for the prediction given heterogeneous data including traffic data such as speed, flow, occupancy, and weather data.

Malicious URLs have become a channel for Internet criminal activities such as drive-by-download, spamming and phishing. Applications for the detection of malicious URLs are accurate but slow (because they need to download the content or query some Internet host information). In this paper we present a novel lightweight filter based only on the URL string itself to use before existing processing methods. We run experiments on a large dataset and demonstrate a 75% reduction in workload size while retaining at least 90% of malicious URLs. Existing methods do not scale well with the hundreds of millions of URLs encountered every day as the problem is a heavily-imbalanced, large-scale binary classification problem. Our proposed method is able to handle nearly two million URLs in less than five minutes. We generate two filtering models by using lexical features and descriptive features, and then combine the filtering results. The on-line learning algorithms are applied here not only for dealing with large-scale data sets but also for fitting the very short lifetime characteristics of malicious URLs. Our filter can significantly reduce the volume of URL queries on which further analysis needs to be performed, saving both computing time and bandwidth used for content retrieval.

Anomaly detection has been an important research topic in data mining and machine learning. Many real-world applications such as intrusion or credit card fraud detection require an effective and efficient framework to identify deviated data instances. However, most anomaly detection methods are typically implemented in batch mode, and thus cannot be easily extended to large-scale problems without sacrificing computation and memory requirements. In this paper, we propose an online oversampling principal component analysis (osPCA) algorithm to address this problem, and we aim at detecting the presence of outliers from a large amount of data via an online updating technique. Unlike prior principal component analysis (PCA)-based approaches, we do not store the entire data matrix or covariance matrix, and thus our approach is especially of interest in online or large-scale problems. By oversampling the target instance and extracting the principal direction of the data, the proposed osPCA allows us to determine the anomaly of the target instance according to the variation of the resulting dominant eigenvector. Since our osPCA need not perform eigen analysis explicitly, the proposed framework is favored for online applications which have computation or memory limitations. Compared with the well-known power method for PCA and other popular anomaly detection algorithms, our experimental results verify the feasibility of our proposed method in terms of both accuracy and efficiency.

Along with the growth of cloud computing and mobile devices, the importance of client device identity concern over cloud environment is emerging. To provide a lightweight yet reliable method for device identification, an application layer approach based on clock skew fingerprint is proposed. The developed experimental platform adapts AJAX technology to collect the timestamps of client devices in the cloud server during connection time, then calculate the clock skews of client devices. Few methods based on linear regression and piecewise minimum algorithm are developed to optimize the precision and shorten timestamp collection process. A jump point detection scheme is also proposed to resolve the offset drifting problem, which is usually caused by switching network or temporary disconnection. Finally, two experiments are conducted to study the effectiveness of clock skew fingerprint, and the results illustrate that the false positive rate and the false negative rate, in the worst case, are both no more than 8% when the tolerance threshold is set appropriately.

Malicious URL detection has drawn a significant research attention in recent years. It is helpful if we can simply use the URL string to make precursory judgment about how dangerous a Web site is. By doing that, we can save efforts on the Web site content analysis and bandwidth for content retrieval. We propose a detection method that is based on an estimation of the conditional Kolmogorov complexity of URL strings. To overcome the incomputability of Kolmogorov complexity, we adopt a compression method for its approximation, called conditional Kolmogorov measure. As a single significant feature for detection, we can achieve a decent performance that can not be achieved by any other single feature that we know. Moreover, the proposed Kolmogorov measure can work together with other features for a successful detection. The experiment has been conducted using a private dataset from a commercial company which can collect more than one million unclassified URLs in a typical hour. On average, the proposed measure can process such hourly data in less than a few minutes.

This paper presents a novel sparse representation for robust face recognition. We advance both group sparsity and data locality and formulate a unified optimization framework, which produces a locality and group sensitive sparse representation (LGSR) for improved recognition. Empirical results confirm that our LGSR not only outperforms state-of-the-art sparse coding based image classification methods, our approach is robust to variations such as lighting, pose, and facial details (glasses or not), which are typically seen in real-world face recognition problems.

It has been established that the second-order stochastic gradient descent (2SGD) method can potentially achieve generalization performance as well as empirical optimum in a single pass (i.e., epoch) through the training examples. However, 2SGD requires computing the inverse of the Hessian matrix of the loss function, which is prohibitively expensive. This paper presents Periodic Step-size Adaptation (PSA), which approximates the Jacobian matrix of the mapping function and explores a linear relation between the Jacobian and Hessian to approximate the Hessian periodically and achieve near-optimal results in experiments on a wide variety of models and tasks.

It has been established that the second-order stochastic gradient descent (SGD) method can potentially achieve generalization performance as well as empirical optimum in a single pass through the training examples. However, second-order SGD requires computing the inverse of the Hessian matrix of the loss function, which is prohibitively expensive for structured prediction problems that usually involve a very high dimensional feature space. This paper presents a new second-order SGD method, called Periodic Step-size Adaptation (PSA). PSA approximates the Jacobian matrix of the mapping function and explores a linear relation between the Jacobian and Hessian to approximate the Hessian, which is proved to be simpler and more effective than directly approximating Hessian in an on-line setting. We tested PSA on a wide variety of models and tasks, including large scale sequence labeling tasks using conditional random fields and large scale classification tasks using linear support vector machines and convolutional neural networks. Experimental results show that single-pass performance of PSA is always very close to empirical optimum.

Sliced inverse regression (SIR) is a renowned dimension reduction method for finding an effective low-dimensional linear subspace. Like many other linear methods, SIR can be extended to nonlinear setting via the ldquokernel trick.rdquo The main purpose of this paper is two-fold. We build kernel SIR in a reproducing kernel Hilbert space rigorously for a more intuitive model explanation and theoretical development. The second focus is on the implementation algorithm of kernel SIR for fast computation and numerical stability. We adopt a low-rank approximation to approximate the huge and dense full kernel covariance matrix and a reduced singular value decomposition technique for extracting kernel SIR directions. We also explore kernel SIR's ability to combine with other linear learning algorithms for classification and regression including multiresponse regression. Numerical experiments show that kernel SIR is an effective kernel tool for nonlinear dimension reduction and it can easily combine with other linear algorithms to form a powerful toolkit for nonlinear data analysis.

In dealing with large data sets, the reduced support vector machine (RSVM) was proposed for the practical objective to overcome some computational difficulties as well as to reduce the model complexity. In this paper, we study the RSVM from the viewpoint of sampling design, its robustness, and the spectral analysis of the reduced kernel. We consider the nonlinear separating surface as a mixture of kernels. Instead of a full model, the RSVM uses a reduced mixture with kernels sampled from certain candidate set. Our main results center on two major themes. One is the robustness of the random subset mixture model. The other is the spectral analysis of the reduced kernel. The robustness is judged by a few criteria as follows: 1) model variation measure; 2) model bias (deviation) between the reduced model and the full model; and 3) test power in distinguishing the reduced model from the full one. For the spectral analysis, we compare the eigenstructures of the full kernel matrix and the approximation kernel matrix. The approximation kernels are generated by uniform random subsets. The small discrepancies between them indicate that the approximation kernels can retain most of the relevant information for learning tasks in the full kernel. We focus on some statistical theory of the reduced set method mainly in the context of the RSVM. The use of a uniform random subset is not limited to the RSVM. This approach can act as a supplemental algorithm on top of a basic optimization algorithm, wherein the actual optimization takes place on the subset-approximated data. The statistical properties discussed in this paper are still valid.

A new smoothing strategy for solving /spl epsi/-support vector regression (/spl epsi/-SVR), tolerating a small error in fitting a given data set linearly or nonlinearly, is proposed in this paper. Conventionally, /spl epsi/-SVR is formulated as a constrained minimization problem, namely, a convex quadratic programming problem. We apply the smoothing techniques that have been used for solving the support vector machine for classification, to replace the /spl epsi/-insensitive loss function by an accurate smooth approximation. This will allow us to solve /spl epsi/-SVR as an unconstrained minimization problem directly. We term this reformulated problem as /spl epsi/-smooth support vector regression (/spl epsi/-SSVR). We also prescribe a Newton-Armijo algorithm that has been shown to be convergent globally and quadratically to solve our /spl epsi/-SSVR. In order to handle the case of nonlinear regression with a massive data set, we also introduce the reduced kernel technique in this paper to avoid the computational difficulties in dealing with a huge and fully dense kernel matrix. Numerical results and comparisons are given to demonstrate the effectiveness and speed of the algorithm.

An algorithm is proposed which generates a nonlinear kernel-based separating surface that requires as little as 1% of a large dataset for its explicit evaluation. To generate this nonlinear surface, the entire dataset is used as a constraint in an optimization problem with very few variables corresponding to the 1% of the data kept. The remainder of the data can be thrown away after solving the optimization problem. This is achieved by making use of a rectangular m × kernel K(A, Ā′) that greatly reduces the size of the quadratic program to be solved and simplifies the characterization of the nonlinear separating surface. Here, the m rows of A represent the original m data points while the rows of Ā represent a greatly reduced data points. Computational results indicate that test set correctness for the reduced support vector machine (RSVM), with a nonlinear separating surface that depends on a small randomly selected portion of the dataset, is better than that of a conventional support vector machine (SVM) with a nonlinear surface that explicitly depends on the entire dataset, and much better than a conventional SVM using a small random sample of the data. Computational times, as well as memory usage, are much smaller for RSVM than that of a conventional SVM using the entire dataset.