Principal component analysis (PCA) is one of the most commonly used statistical procedures with a wide range of applications. Consider the points $X_1, X_2,..., X_n$ are vectors drawn i.i.d. from a distribution with mean zero and covariance $\Sigma$, where $\Sigma$ is unknown. Let $A_n = X_nX_n^T$, then $E[A_n] = \Sigma$. This paper consider the problem of finding the least eigenvalue and eigenvector of matrix $\Sigma$. A classical such estimator are due to Krasulina\cite{krasulina_method_1969}. We are going to state the convergence proof of Krasulina for the least eigenvalue and corresponding eigenvector, and then find their convergence rate.

Discovering and clustering subspaces in high-dimensional data is a fundamental problem of machine learning with a wide range of applications in data mining, computer vision, and pattern recognition. Earlier methods divided the problem into two separate stages of finding the similarity matrix and finding clusters. Similar to some recent works, we integrate these two steps using a joint optimization approach. We make the following contributions: (i) we estimate the reliability of the cluster assignment for each point before assigning a point to a subspace. We group the data points into two groups of "certain" and "uncertain", with the assignment of latter group delayed until their subspace association certainty improves. (ii) We demonstrate that delayed association is better suited for clustering subspaces that have ambiguities, i.e. when subspaces intersect or data are contaminated with outliers/noise. (iii) We demonstrate experimentally that such delayed probabilistic association leads to a more accurate self-representation and final clusters. The proposed method has higher accuracy both for points that exclusively lie in one subspace, and those that are on the intersection of subspaces. (iv) We show that delayed association leads to huge reduction of computational cost, since it allows for incremental spectral clustering.

In the field of statistics and machine learning, the sums-of-squares, commonly referred to as \emph{ordinary least squares}, can be used as a convenient choice of cost function because of its many nice analytical properties, though not always the best choice. However, it has been long known that \emph{ordinary least squares} is not robust to outliers. Several attempts to resolve this problem led to the creation of alternative methods that, either did not fully resolved the \emph{outlier problem} or were computationally difficult. In this paper, we provide a very simple solution that can make \emph{ordinary least squares} less sensitive to outliers in data classification, by \emph{scaling the augmented input vector by its length}. We show some mathematical expositions of the \emph{outlier problem} using some approximations and geometrical techniques. We present numerical results to support the efficacy of our method.

This letter is concerned with a recently developed paradigm of population-based optimization, termed particle filter optimization (PFO). In contrast with the commonly used meta-heuristics based methods, the PFO paradigm is attractive in terms of coherence in theory and easiness in mathematical analysis and interpretation. However, current PFO algorithms only work for single-objective optimization cases, while many real-life problems involve multiple objectives to be optimized simultaneously. To this end, we make an effort to extend the scope of application of the PFO paradigm to multi-objective optimization (MOO) cases. An idea called path sampling is adopted within the PFO scheme to balance the different objectives to be optimized. The resulting algorithm is thus termed PFO with Path Sampling (PFOPS). Experimental results show that the proposed algorithm works consistently well for three different types of MOO problems, which are characterized by an associated convex, concave and discontinuous Pareto front, respectively.

One way to interpret neural model predictions is to highlight the most important input features---for example, a heatmap visualization over the words in an input sentence. In existing interpretation methods for NLP, a word's importance is determined by either input perturbation---measuring the decrease in model confidence when that word is removed---or by the gradient with respect to that word. To understand the limitations of these methods, we use input reduction, which iteratively removes the least important word from the input. This exposes pathological behaviors of neural models: the remaining words appear nonsensical to humans and are not the ones determined as important by interpretation methods. As we confirm with human experiments, the reduced examples lack information to support the prediction of any label, but models still make the same predictions with high confidence. To explain these counterintuitive results, we draw connections to adversarial examples and confidence calibration: pathological behaviors reveal difficulties in interpreting neural models trained with maximum likelihood. To mitigate their deficiencies, we fine-tune the models by encouraging high entropy outputs on reduced examples. Fine-tuned models become more interpretable under input reduction without accuracy loss on regular examples.

With the tremendous generation of data, there are more and more situations where observations are described by more than one view. This is for example the case with multilingual documents that convey the same information in different languages or images that are naturally described according to different set of features (for example SIFT, HOG, CNN etc). In this paper, we study the related machine learning problem that consists in finding an efficient classification model from different information sources that describe the observations. This topic, called multiview learning Atrey et al. [2010], Sun [2013], has been expanding over the past decade, spurred by the seminal work of Blum and Mitchell on co-training Blum and Mitchell [1998] (with only two views). The aim is to learn a classifier which performs better than classifiers trained over each view separately (called view-specific classifier).

We present SetExpander, a corpus-based system for expanding a seed set of terms into a more complete set of terms that belong to the same semantic class. SetExpander implements an iterative end-to-end workflow. It enables users to easily select a seed set of terms, expand it, view the expanded set, validate it, reexpand the validated set and store it, thus simplifying the extraction of domain-specific finegrained semantic classes. SetExpander has been used successfully in real-life use cases including integration into an automated recruitment system and an issues and defects resolution system.

Sparse component analysis (SCA) is the following problem: Given an input matrix $M$ and an integer $r$, find a dictionary $D$ with $r$ columns and a sparse matrix $B$ with $r$ rows such that $M \approx DB$. A key issue in SCA is identifiability, that is, characterizing the conditions under which $D$ and $B$ are essentially unique (that is, they are unique up to permutation and scaling of the columns of $D$ and rows of $B$). Although SCA has been vastly investigated in the last two decades, only a few works have tackled this issue in the deterministic scenario, and no work provides reasonable bounds in the minimum number of data points (that is, columns of $M$) that leads to identifiability. In this work, we provide new results in the deterministic scenario when the data has a low-rank structure, that is, when $D$ has rank $r$, drastically improving with respect to previous results. In particular, we show that if each column of $B$ contains at least $s$ zeros then $\mathcal{O}(r^3/s^2)$ data points are sufficient to obtain an essentially unique decomposition, as long as these data points are well spread among the subspaces spanned by $r-1$ columns of $D$. This implies for example that for a fixed proportion of zeros (constant and independent of $r$, e.g., 10\% of zero entries in $B$), one only requires $O(r)$ data points to guarantee identifiability.

Finding meaningful representations in data is a core challenge in modern machine learning as the performance in many goal-directed frameworks such as reinforcement learning or supervised learning is directly and strongly influenced by the quality of the former. Usually, features are either provided (e.g. by expert knowledge) or acquired through learning. Most currently successful approaches for either deep supervised learning [1] or reinforcement learning [2] rely on a training signal, i.e., a classification label or reward signal, to provide sufficient indication which features of the input data should be extracted to increase performance. However, in most real-world scenarios labels have to be acquired by expert knowledge and reward signals are sparse. In unsupervised representation learning one tries to find and apply a principle by which to extract meaning from data without assuming the availability of any goal-driven metrics. Examples for such principles are based on reconstruction error (principal component analysis, autoencoder networks [3]), statistical dependence of extracted features 1 (independent component analysis [4]), indistinguishability of synthetically generated data from samples of the input distribution (generative adversarial nets [5]), fitting the probability distribution of input data (variational autoencoders [6]), (graph-)neighborhood preservation (locally-linear embedding [7], Laplacian eigenmaps [8]), and temporal coherence (slow feature analysis [9], regularized slowness optimization [10]).

Several recent papers investigate Active Learning (AL) for mitigating the data dependence of deep learning for natural language processing. However, the applicability of AL to real-world problems remains an open question. While in supervised learning, practitioners can try many different methods, evaluating each against a validation set before selecting a model, AL affords no such luxury. Over the course of one AL run, an agent annotates its dataset exhausting its labeling budget. Thus, given a new task, an active learner has no opportunity to compare models and acquisition functions. This paper provides a large scale empirical study of deep active learning, addressing multiple tasks and, for each, multiple datasets, multiple models, and a full suite of acquisition functions. We find that across all settings, Bayesian active learning by disagreement, using uncertainty estimates provided either by Dropout or Bayes-by Backprop significantly improves over i.i.d. baselines and usually outperforms classic uncertainty sampling.