Robust Differentiable SVD | EPFL Graph Search

Eigendecomposition of symmetric matrices is at the heart of many computer vision algorithms. However, the derivatives of the eigenvectors tend to be numerically unstable, whether using the SVD to compute them analytically or using the Power Iteration (PI) method to approximate them. This instability arises in the presence of eigenvalues that are close to each other. This makes integrating eigendecomposition into deep networks difficult and often results in poor convergence, particularly when dealing with large matrices. While this can be mitigated by partitioning the data into small arbitrary groups, doing so has no theoretical basis and makes it impossible to exploit the full power of eigendecomposition. In previous work, we mitigated this using SVD during the forward pass and PI to compute the gradients during the backward pass. However, the iterative deflation procedure required to compute multiple eigenvectors using PI tends to accumulate errors and yield inaccurate gradients. Here, we show that the Taylor expansion of the SVD gradient is theoretically equivalent to the gradient obtained using PI without relying in practice on an iterative process and thus yields more accurate gradients. We demonstrate the benefits of this increased accuracy for image classification and style transfer.

Mean-Field methods for Structured Deep-Learning in Computer Vision

Pierre Bruno Baqué

In recent years, Machine Learning based Computer Vision techniques made impressive progress. These algorithms proved particularly efficient for image classification or detection of isolated objects. From a probabilistic perspective, these methods can predict marginals, over single or multiple variables, independently, with high accuracy. However, in many tasks of practical interest, we need to predict jointly several correlated variables. Practical applications include people detection in crowded scenes, image segmentation, surface reconstruction, 3D pose estimation and others. A large part of the research effort in today's computer-vision community aims at finding task-specific solutions to these problems, while leveraging the power of Deep-Learning based classifiers. In this thesis, we present our journey towards a generic and practical solution based on mean-field (MF) inference. Mean-field is a Statistical Physics-inspired method which has long been used in Computer-Vision as a variational approximation to posterior distributions over complex Conditional Random Fields. Standard mean-field optimization is based on coordinate descent and in many situations can be impractical. We therefore propose a novel proximal gradient-based approach to optimizing the variational objective. It is naturally parallelizable and easy to implement. We prove its convergence, and then demonstrate that, in practice, it yields faster convergence and often finds better optima than more traditional mean-field optimization techniques. Then, we show that we can replace the fully factorized distribution of mean-field by a weighted mixture of such distributions, that similarly minimizes the KL-Divergence to the true posterior. Our extension of the clamping method proposed in previous works allows us to both produce a more descriptive approximation of the true posterior and, inspired by the diverse MAP paradigms, fit a mixture of mean-field approximations. We demonstrate that this positively impacts real-world algorithms that initially relied on mean-fields. One of the important properties of the mean-field inference algorithms is that the closed-form updates are fully differentiable operations. This naturally allows to do parameter learning by simply unrolling multiple iterations of the updates, the so-called back-mean-field algorithm. We derive a novel and efficient structured learning method for multi-modal posterior distribution based on the Multi-Modal Mean-Field approximation, which can be seamlessly combined to modern gradient-based learning methods such as CNNs. Finally, we explore in more details the specific problem of structured learning and prediction for multiple-people detection in crowded scenes. We then present a mean-field based structured deep-learning detection algorithm that provides state of the art results on this dataset.

EPFL2018

Object Classification and Detection in High Dimensional Feature Space

Charles Dubout

Object classification and detection aim at recognizing and localizing objects in real-world images. They are fundamental computer vision problems and a prerequisite for full scene understanding. Their difficulty lies in the large number of possible object positions and the appearance variations of object classes. This thesis improves upon several classical machine learning algorithms, enabling large computational gains in high dimensional feature space. A common trend in machine learning and computer vision research is to go large scale. In particular, the advent of huge datasets mined from the Internet, and the combination of multiple feature sources have considerably broadened the applications of computer vision. Tasks which were thought impossible a few years ago, such as human action recognition or pose estimation, automatic outdoor navigation, etc., now seem within reach. This dissertation is divided into two parts. The first one deals with the efficient training of a classifier or detector based on a large number of feature extractors, outside the control of the learning algorithm, and therefore of unknown suitability to the task at hand. More precisely, this part presents two kinds of strategies to accelerate the training of Boosting algorithms in such a context: (a) a method to better deal with the increasingly common case where features come from multiple sources (e.g. color, shape, texture, etc., in the case of images) and therefore can be partitioned into meaningful subsets; (b) new algorithms which balance at every Boosting iteration the number of weak learners and the number of training examples to look at in order to maximize the expected loss reduction. Experiments in image classification and object recognition on four standard computer vision datasets show that the adaptive techniques we propose outperform both basic sampling and state-of-the-art bandit methods. The second part deals with linear object detectors, currently the most popular class of detection systems, encompassing template matching, deformable part models, poselets, convolutional neural networks (which internally use linear filters), etc. The main bottleneck of many of those systems is the computational cost of the convolutions between the multiple rescalings of the image to process and the linear filters. We make use of properties of the Fourier transform and clever implementation strategies to obtain a speedup factor proportional to the filter size, both while training and at test time. We also introduce a few modifications to the original Deformable Part Model (DPM) of Felzenszwalb et al. improving its detection accuracy. The gains in performance are demonstrated on the well-known Pascal VOC benchmark, where an increase by one order of magnitude in the speed of said convolutions, and an average improvement of 15% in the accuracy of the detector are established.

Programme doctoral en Informatique, Communications et Information2013

Eigendecomposition-free Training of Deep Networks with Zero Eigenvalue-based Losses

Zheng Dang, Pascal Fua, Yinlin Hu, Mathieu Salzmann, Fei Wang, Kwang Moo Yi

Many classical Computer Vision problems, such as essential matrix computation and pose estimation from 3D to 2D correspondences, can be solved by ﬁnding the eigenvector corresponding to the smallest, or zero, eigenvalue of a matrix representing a linear system. Incorporating this in deep learning frameworks would allow us to explicitly encode known notions of geometry, instead of having the network implicitly learn them from data. However, performing eigendecomposition within a network requires the ability to diﬀerentiate this operation. While theoretically doable, this introduces numerical instability in the optimization process in practice. In this paper, we introduce an eigendecomposition-free approach to training a deep network whose loss depends on the eigenvector corresponding to a zero eigenvalue of a matrix predicted by the network. We demonstrate on several tasks, including keypoint matching and 3D pose estimation, that our approach is much more robust than explicit diﬀerentiation of the eigendecomposition. It has better convergence properties and yields state-of-the-art results on both tasks.