A hierarchical clustering corresponds to recursively dividing a dataset into increasingly smaller groups. The fundamental assumption of this approach is that the visible structures in the data depends on the chosen scale of observation. This hypothesis has been confirmed, in theory and in practice, on many complex data such as social networks, electrical networks, actor networks, computer networks, cortical brain networks, linguistic networks, etc. Building high quality hierarchical representations is therefore an important step in the analysis and in the understanding of these data. The hierarchical clustering methods used today are essentially unsupervised and are based on heuristic algorithms: therefore, the hierarchical clustering obtained does not correspond to the optimization of an explicit criterion. These limitations are due to difficulties in solving optimization problems on these structures, as they are generally NP-hard. In this project, we propose to study the problem of optimizing hierarchical clusterings from the angle of optimizing ultrametrics which are a dual and continuous representation of hierarchical clusterings. In topology, an ultrametric distance is obtained by replacing the triangular inequality by the ultrametric inequality, which requires that any triplet of points forms an isosceles triangle where the two equal sides are at least as large as the third side. This ultrametric inequality imposes a new non-convex constraint which is difficult to manage. We can nevertheless reformulate the problem of optimization of ultrametrics to make this constraint implicit. It then becomes possible to optimize ultrametrics with gradient descent algorithms. This project aims to develop this possibility to obtain supervised learning methods for hierarchical clustering working on large datasets. In other words, we will formulate the problem of supervised hierarchical clusterings learning on the continuous space of ultrametrics, hence the name of the project: ULTRA-LEARN. This progress will be based on two main ingredients. The first one is the development of ultrametric networks, i.e. models which can be trained, and which will yield ultrametrics. An ultrametric network will itself be made up of two elements, a multilayer neural network for the extraction of characteristics and an ultrametric layer which will be able to produce an ultrametric from the characteristics provided by the neural network. This ultrametric layer will be differentiable: this will allow us to learn the parameters of the network end-to-end. The second ingredient of the method will be the definition of cost functions to measure the dissimilarity effectively and differentially between two ultrametrics. All these elements will also benefit from algorithmic developments to operate on highly parallel hardware such as GPUs to allow the processing of large datasets. The ultrametric networks developed will be applied on three problems. We will propose an ultrametric network to estimate hierarchical segmentations of images, i.e. the complete decomposition of an image into objects and the iterative refinement of these objects into parts. The second application will aim at the development of a classifier taking advantage of a class ontology known a priori, for example we know that a cat and a dog are both mammals and that they are semantically closer than a bird. Finally, the third application considered is the semi-supervised hierarchical clustering of data; in this case, we will seek to construct an optimal hierarchical clustering based on partial information given a priori by an expert.

Recent developments in image processing brings the need for solving optimization problems with increasingly large sizes, pushing traditional techniques to their limits. New optimization algorithms need to be designed, paying attention to computational complexity, scalability, and robustness issues. Majorization-Minimization (MM) approaches have become increasingly popular recently, in both signal/image processing and machine learning fields. The MM framework provides simple, elegant and flexible ways to construct optimization algorithms that benefit from solid theoretical foundations and show great practical efficiency. The MAJIC project aims to propose a new generation of MM algorithms that remain efficient in the context of “big data” processing, thanks to the integration of parallel, distributed, and online computing strategies. Two challenging applications will be addressed: on-the-fly image reconstruction, and fast deep neural network learning.

Combinatorial maps, which are graphs embedded on 2D surfaces (and which can be naturally related to triangulations of such surfaces), have been successfully studied in various domains of computer science. The purpose of this proposal is to study 3D maps, seen as a natural generalization of 2D combinatorial maps. While combinatorial maps are canonically associated to the so-called random matrix models, 3D maps are, in the same way, canonically associated to tensor models. The proposal is divided into three main objectives. The first objective is focused on the study of combinatorial properties of particular tensor models which were recently shown to play a crucial role in theoretical physics. The second objective deals with the involved problematics of counting 3D triangulations – finding, for example, natural subfamilies of 3D triangulations which are exponentially bounded. Our third objective focuses on the search of analytically controlled random metric spaces of dimension 3.

The central theme of this project is the study of geometric and combinatorial structures related to surfaces and their moduli. Even though they work on common themes, there is a real gap between communities working in geometric topology and computational geometry and SoS aims to create a long lasting bridge between them. Beyond a common interest, techniques from both ends are relevant and the potential gain in perspective from long-term collaborations is truly thrilling. In particular, SoS aims to extend the scope of computational geometry, a field at the interface between mathematics and computer science that develops algorithms for geometric problems, to a variety of unexplored contexts. During the last two decades, research in computational geometry has gained wide impact through CGAL, the Computational Geometry Algorithms Library. In parallel, the needs for non-Euclidean geometries are arising, e.g., in geometric modeling, neuromathematics, or physics. Our goal is to develop computational geometry for some of these spaces and make these developments readily available for users in academy and industry. To reach this aim, SoS will follow an interdisciplinary approach, gathering researchers whose expertise cover a large range of mathematics, algorithms and software. A mathematical study of the objects considered will be performed, together with the design of algorithms when applicable. Algorithms will be analyzed both in theory and in practice after prototype implementations, which will be improved whenever it makes sense to target longer-term integration into CGAL. Our main objects of study will be Delaunay triangulations and circle patterns on surfaces, polyhedral geometry, and systems of disjoint curves and graphs on surfaces. Concerning the closely related notions of Delaunay triangulations and circle packings, we intend to study the cases of non-compact surfaces and general hyperbolic surfaces. We will explore the possibility to unify their study and to design algorithms for surfaces equipped with a complex projective structure. We will study isometric embeddings into Euclidean spaces of a cell complex endowed with a compatible metric structure. In the area of combinatorial structures on surfaces and moduli spaces, we intend to develop efficient algorithms in coordination with a deeper understanding of the core objects. For example, we will consider shortest graphs with given topological properties on a given surface and shortest paths between triangulations. Moreover we also intend to improve the mathematical understanding of the relations between combinatorial structures such as curve, pants and flips graphs and related continuous objects such as Teichmüller and moduli spaces. We have ambitious mathematical goals (such as proving expander type properties for moduli spaces and their combinatorial analogues) as well as plans for software which will allow us to discover new directions of research.

The CorVis project aims to develop cutting-edge sign language translation techniques, based on recent advances in artificial intelligence, in particular in the fields of computer vision and machine translation. Sign language analysis from video data is understudied in computer vision despite its great impact on the society, among which is enhancing hearing-deaf communication. This project, therefore, will make a step towards translating the video signal into spoken language, by learning data-driven representations suitable for the task, through deep learning. There will be two inter-related directions focusing on: (1) the visual input representation, i.e., how to embed a continuous video sequence to capture the signing content, (2) the model design for outputting text given video representations, i.e., how to find a mapping between the sign and spoken languages.