Empirical risk minimization

Empirical risk minimization (ERM) is a principle in statistical learning theory which defines a family of learning algorithms and is used to give theoretical bounds on their performance. The core idea is that we cannot know exactly how well an algorithm will work in practice (the true "risk") because we don't know the true distribution of data that the algorithm will work on, but we can instead measure its performance on a known set of training data (the "empirical" risk). Consider the following situation, which is a general setting of many supervised learning problems. We have two spaces of objects and and would like to learn a function (often called hypothesis) which outputs an object , given . To do so, we have at our disposal a training set of examples where is an input and is the corresponding response that we wish to get from . To put it more formally, we assume that there is a joint probability distribution over and , and that the training set consists of instances drawn i.i.d. from . Note that the assumption of a joint probability distribution allows us to model uncertainty in predictions (e.g. from noise in data) because is not a deterministic function of , but rather a random variable with conditional distribution for a fixed . We also assume that we are given a non-negative real-valued loss function which measures how different the prediction of a hypothesis is from the true outcome The risk associated with hypothesis is then defined as the expectation of the loss function: A loss function commonly used in theory is the 0-1 loss function: . The ultimate goal of a learning algorithm is to find a hypothesis among a fixed class of functions for which the risk is minimal: For classification problems, the Bayes classifier is defined to be the classifier minimizing the risk defined with the 0–1 loss function. In general, the risk cannot be computed because the distribution is unknown to the learning algorithm (this situation is referred to as agnostic learning).

Learning embeddings: efficient algorithms and applications

Cijo Jose

Learning to embed data into a space where similar points are together and dissimilar points are far apart is a challenging machine learning problem. In this dissertation we study two learning scenarios that arise in the context of learning embeddings and one scenario in efficiently estimating an empirical expectation. We present novel algorithmic solutions and demonstrate their applications on a wide range of data-sets. The first scenario deals with learning from small data with large number of classes. This setting is common in computer vision problems such as person re-identification and face verification. To address this problem we present a new algorithm called Weighted Approximate Rank Component Analysis (WARCA), which is scalable, robust, non-linear and is independent of the number of classes. We empirically demonstrate the performance of our algorithm on 9 standard person re-identification data-sets where we obtain state of the art performance in terms of accuracy as well as computational speed. The second scenario we consider is learning embeddings from sequences. When it comes to learning from sequences, recurrent neural networks have proved to be an effective algorithm. However there are many problems with existing recurrent neural networks which makes them data hungry (high sample complexity) and difficult to train. We present a new recurrent neural network called Kronecker Recurrent Units (KRU), which addresses the issues of existing recurrent neural networks through Kronecker matrices. We show its performance on 7 applications, ranging from problems in computer vision, language modeling, music modeling and speech recognition. Most of the machine learning algorithms are formulated as minimizing an empirical expectation over a finite collection of samples. In this thesis we also investigate the problem of efficiently estimating a weighted average over large data-sets. We present a new data-structure called Importance Sampling Tree (IST), which permits fast estimation of weighted average without looking at all the samples. We show successfully the evaluation of our data-structure in the training of neural networks in order to efficiently find informative samples.

EPFL2018

Learning embeddings: efficient algorithms and applications

Cijo Jose

École Polytechnique Fédérale de Lausanne2018

Learning embeddings: efficient algorithms and applications

Cijo Jose

École Polytechnique Fédérale de Lausanne2018

Learning embeddings: efficient algorithms and applications

Cijo Jose

EPFL2018

Learning embeddings: efficient algorithms and applications

Learning embeddings: efficient algorithms and applications

GKW representation theorem and linear BSDEs under restricted information. An application to risk-minimization.

GKW representation theorem and linear BSDEs under restricted information. An application to risk-minimization.

Learning embeddings: efficient algorithms and applications

Learning embeddings: efficient algorithms and applications