We give a polynomial-time algorithm for learning latent-state linear dynamical systems without system identification, and without assumptions on the spectral radius of the system's transition matrix. The algorithm extends the recently introduced technique of spectral filtering, previously applied only to systems with a symmetric transition matrix, using a novel convex relaxation to allow for the efficient identification of phases.

Machine learning has played an important role in information retrieval (IR) in recent times. In search engines, for example, query keywords are accepted and documents are returned in order of relevance to the given query; this can be cast as a multi-label ranking problem in machine learning. Generally, the number of candidate documents is extremely large (from several thousand to several million); thus, the classifier must handle many labels. This problem is referred to as extreme multi-label classification (XMLC). In this paper, we propose a novel approach to XMLC termed the Sparse Weighted Nearest-Neighbor Method. This technique can be derived as a fast implementation of state-of-the-art (SOTA) one-versus-rest linear classifiers for very sparse datasets. In addition, we show that the classifier can be written as a sparse generalization of a representer theorem with a linear kernel. Furthermore, our method can be viewed as the vector space model used in IR. Finally, we show that the Sparse Weighted Nearest-Neighbor Method can process data points in real time on XMLC datasets with equivalent performance to SOTA models, with a single thread and smaller storage footprint. In particular, our method exhibits superior performance to the SOTA models on a dataset with 3 million labels.

Photovoltaic systems have been widely deployed in recent times to meet the increased electricity demand as an environmental-friendly energy source. The major challenge for integrating photovoltaic systems in power systems is the unpredictability of the solar power generated. In this paper, we analyze the impact of having access to weather information for solar power generation prediction and find weather information that can help best predict photovoltaic power.

We consider the problem of model-free reinforcement learning for infinite-horizon discounted Markov Decision Processes (MDPs) with a continuous state space and unknown transition kernels, when only a single sample path of the system is available. We focus on the classical approach of Q-learning where the goal is to learn the optimal Q-function. We propose the Nearest Neighbor Q-Learning approach that utilizes nearest neighbor regression method to learn the Q function. We provide finite sample analysis of the convergence rate using this method. In particular, we establish that the algorithm is guaranteed to output an $\epsilon$-accurate estimate of the optimal Q-function with high probability using a number of observations that depends polynomially on $\epsilon$ and the model parameters. To establish our results, we develop a robust version of stochastic approximation results; this may be of interest in its own right.

Model-based methods for recommender systems have been studied to provide more precise results. In systems with large corpus, the amount of calculation for learnt model to predict all user-item pairs' preferences is tremendous, which makes the model difficult to be directly employed in recommendation candidate generation stage. To overcome the calculation barrier, models like matrix factorization can resort to inner product form (i.e., use the inner product of user and item's latent factors as the preference) and index like hashing to perform efficient approximate k-nearest neighbor search. However, other more expressive interaction forms between user and item features, e.g., interactions through advanced deep neural networks, are still prevented from large corpus recommendation because of the amount of calculation. In this paper, we focus on the problem how arbitrary advanced models can be introduced to generate recommendations from large corpus. We propose a novel tree-based method which can provide logarithmic complexity prediction w.r.t. corpus size with more expressive deep neural networks. The main idea of tree-based model is to predict user interests coarse-to-fine, by traversing tree nodes top-down and making decisions whether to pick up each node to user. Furthermore, we show that the tree structure can also be jointly learnt towards better compatible with user interests' distribution, to facilitate both training and prediction. Experiments in two large-scale real-world datasets indicate that the proposed model significantly outperforms traditional methods. And online A/B test results in Taobao display advertising platform prove the effectiveness of the tree-based deep model in production.

We propose a new blind source separation algorithm based on mixtures of alpha-stable distributions. Complex symmetric alpha-stable distributions have been recently showed to better model audio signals in the time-frequency domain than classical Gaussian distributions thanks to their larger dynamic range. However, inference of these models is notoriously hard to perform because their probability density functions do not have a closed-form expression in general. Here, we introduce a novel method for estimating mixture of alpha-stable distributions based on characteristic function matching. We apply this to the blind estimation of binary masks in individual frequency bands from multichannel convolutive audio mixes. We show that the proposed method yields better separation performance than Gaussian-based binary-masking methods.

In real-world applications, it is conceivable that only positive and unlabeled (PU) data are available for training a classifier. For instance, in land-cover image classification, images of urban regions can be easily labeled, while images of non-urban regions are difficult to annotate due to high diversity of non-urban regions containing, e.g., forest, seas, grasses, and soil (Li et al., 2011). To cope with such situations, PU classification has been actively studied (Letouzey et al., 2000; Elkan and Noto, 2008; du Plessis et al., 2015), and the state-of-the-art method allows us to systematically train deep neural networks only from PU data (Kiryo et al., 2017). However, existing PU classification methods typically require an estimate of the class-prior probability, and their performance is sensitive to the quality of class-prior estimation (Kiryo et al., 2017). Although various class-prior estimation methods from PU data have been proposed so far (du Plessis and Sugiyama, 2014; Ramaswamy et al., 2016; Jain et al., 2016; du Plessis et al., 2017; Northcutt et al., 2017), accurate estimation of the class-prior is still highly challenging particularly for high-dimensional data.

Distributionally Robust Supervised Learning (DRSL) is necessary for building reliable machine learning systems. When machine learning is deployed in the real world, its performance can be significantly degraded because test data may follow a different distribution from training data. Previous DRSL explicitly considers the worst-case distribution shift by minimizing the adver-sarially reweighted training loss. In this paper, we theoretically analyze the previous DRSL in a classification scenario. We reveal a rather surprising fact that the previous DRSL ends up giving classifiers optimal for the training distribution even though it is designed to be robust to change from the training distribution. Motivated by our analysis, we also propose novel DRSL that overcomes this limitation. We establish its convergence property and demonstrate its effectiveness through experiments.

It has been suggested that adversarial examples cause deep learning models to make incorrect predictions with high confidence. In this work, we take the opposite stance: an overly confident model is more likely to be vulnerable to adversarial examples. This work is one of the most proactive approaches taken to date, as we link robustness with non-calibrated model confidence on noisy images, providing a data-augmentation-free path forward. The adversarial examples phenomenon is most easily explained by the trend of increasing non-regularized model capacity, while the diversity and number of samples in common datasets has remained flat. Test accuracy has incorrectly been associated with true generalization performance, ignoring that training and test splits are often extremely similar in terms of the overall representation space. The transferability property of adversarial examples was previously used as evidence against overfitting arguments, a perceived random effect, but overfitting is not always random.

A major challenge in understanding the generalization of deep learning is to explain why (stochastic) gradient descent can exploit the network architecture to find solutions that have good generalization performance when using high capacity models. We find simple but realistic examples showing that this phenomenon exists even when learning linear classifiers --- between two linear networks with the same capacity, the one with a convolutional layer can generalize better than the other when the data distribution has some underlying spatial structure. We argue that this difference results from a combination of the convolution architecture, data distribution and gradient descent, all of which are necessary to be included in a meaningful analysis. We provide a general analysis of the generalization performance as a function of data distribution and convolutional filter size, given gradient descent as the optimization algorithm, then interpret the results using concrete examples. Experimental results show that our analysis is able to explain what happens in our introduced examples.