# Workshop

"Greedy methods meet multiview learning"

22th of september 2014

### Program

9.00 | Welcome | |

9.30 | François-Xavier Dupé | The Multi-Task Learning View of Multimodal Data
Abstract. |

Abstract
We study the problem of learning from multiple views using kernel methods in a su- pervised setting. We approach this problem from a multi-task learning point of view and illustrate how to capture the interesting multimodal structure of the data using multi-task kernels. Our analysis shows that the multi-task perspective offers the flexibility to design more efficient multiple-source learning algorithms, and hence the ability to exploit multiple descriptions of the data. In particular, we formulate the multimodal learning framework using vector-valued reproducing kernel Hilbert spaces, and we derive specific multi-task kernels that can operate over multiple modalities. Finally, we analyze the vector-valued regularized least squares algorithm in this context, and demonstrate its potential in a series of experiments with a real-world multimodal data set. |
||

10.00 | Ludmila Kuncheva | Are we still talking about diversity in classifier ensembles? Abstract. |

Abstract
Don't we already know everything about ensemble diversity? A decade of debate has brought clarity and confusion alike. There are many diversity measures (too many?) trying to quantify a naturally unclear concept. Playing devil's advocate, I will show that many more diversity measures have not yet been "discovered". There must be a simpler way! We will look at the relationship between diversity and the ensemble margin, and identify two roles of diversity - beneficial (good diversity) and detrimental (bad diversity). While the talk will not give the missing answers, it will hopefully contribute to developing a more critical and systematic approach to studying ensemble diversity. |
||

10.50 | Coffee | |

11.10 | Victor Chepoi | Matroids, greedy algorithms, and submodularity Abstract. |

Abstract
The talk will present a brief introduction to matroids and submodular functions, and to the maximization of submodular functions with matroids constraints. |
||

12.00 | Lunch | |

14.00 | Laurent Daudet | Randomized greedy decompositions. Abstract. |

Abstract
Randomized greedy decompositions (with Manuel Moussallam, Gaël Richard, Alexandre Gramfort) Greedy algorithms are a class of algorithms that are popular for sparse approximation problems, due to their simplicity and efficiency, especially for large-scale problems. They rely on an atom selection step that requires the calculation of numerous projections, which can be computationally costly for large dictionaries and burdens their competitiveness in coding applications. Here, we investigate the use of a non adaptive random sequence of subdictionaries in the decomposition process, thus parsing a large dictionary in a probabilistic fashion with no additional projection cost nor parameter estimation. A theoretical modeling based on order statistics has been investigated, and gives some insight on the performance of the algorithm. Two applications have been studied. First, this approach has been applied for audio signal compression with multiscale time-frequency dictionaries. Second, we used this approach for signal denoising, in situations where we assume that the signal on in a given dictionary has a distribution that is more heavy-tailed than the noise. This hypothesis leads to a stopping criterion for greedy pursuit algorithms which is independent from the noise level. This leads to a new denoising procedure leveraging upon randomly subsampled dictionaries, called Blind Random Pursuit Denoising (BIRD). We offer a generalization to multidimensional signals, with a structured sparse model (S-BIRD). The relevance of this approach is demonstrated on synthetic and experimental MEG signals. References : - Manuel Moussallam, Laurent Daudet and Gaël Richard ; Matching Pursuits with Random Sequential Subdictionaries ; Signal Processing, 92 pp. 2532-2544 (2012) - Manuel Moussallam, Alexandre Gramfort, Laurent Daudet, and Gaël Richard ; Blind Denoising with Random Greedy Pursuits ; IEEE Signal Processing Letters, 21(11), pp. 1341-1345 (Nov 2014) |
||

14.50 | Isabelle Guyon | Results of the ChaLearn Looking at People Challenge 2014 Abstract. |

Abstract
The ChaLearn Looking at People 2014 challenge is the third challenge of a series ChaLearn has organized on the theme of gesture and activity recognition. This year's edition was split into three independent tracks: human pose recovery from RGB data, action and interaction spotting from RGB data sequences, and multi-modal gesture spotting from RGB-Depth sequences. For all the tracks, the goal was to perform user-independent recognition in continuous image sequences using the overlapping Jaccard index as the evaluation measure. Two large novel data sets were made publicly available and the Microsoft Codalab platform was used to manage the competition. This presentation will review the results and methods used by the participants and put them in perspective looking at past and future challenges. This is work performed by Sergio Escalera, Xavier Baro, Jordi Gonzalez, Miguel A. Bautista, Meysam Madadi, Miguel Reyes, Victor Ponce, Hugo J. Escalante, Jamie Shotton, and Isabelle Guyon. |
||

15.40 | Coffee | |

16.00 | Xavier Bresson | Matrix Completion on Graphs
Abstract. |

Abstract
The problem of finding the missing values of a matrix given a few of its entries, called matrix completion, has gathered a lot of attention in the recent years. Although the problem is NP-hard, Cand\`es and Recht showed that it can be exactly relaxed if the matrix is low-rank and the number of observed entries is sufficiently large. In this work, we introduce a novel matrix completion model that makes use of proximity information about rows and columns by assuming they form communities. This assumption makes sense in several real-world problems like in recommender systems, where there are communities of people sharing preferences, while products form clusters that receive similar ratings. Our main goal is thus to find a low-rank solution that is structured by the proximities of rows and columns encoded by graphs. We borrow ideas from manifold learning to constrain our solution to be smooth on these graphs, in order to implicitly force row and column proximities. Our matrix recovery model is formulated as a convex non-smooth optimization problem, for which a well-posed iterative scheme is provided. We study and evaluate the proposed matrix completion on synthetic and real data, showing that the proposed structured low-rank recovery model outperforms the standard matrix completion model in many situations. This is a joint work with Vassilis Kalofolias, Michael Bronstein, Pierre Vandergheynst. |
||

16.50 | Antoine Bonnefoy | A Dynamic Screening Principle for the Lasso. Abstract. |

Abstract
The Lasso is an optimization problem devoted to finding a sparse representation of some signal with respect to a predefined dictionary. An original and computationally-efficient method is proposed here to solve this problem, based on a dynamic screening principle. It makes it possible to accelerate a large class of optimization algorithms by iteratively reducing the size of the dictionary during the optimization process, discarding elements that are provably known not to belong to the solution of the Lasso. The iterative reduction of the dictionary is what we call dynamic screening. As this screening step is inexpensive, the computational cost of the algorithm using our dynamic screening strategy is lower than that of the base algorithm. Numerical experiments on synthetic and real data support the relevance of this approach. |
||

17.20 | Discussions and conclusion | |

18.00 | End of the workshop |