% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
\PassOptionsToPackage{dvipsnames,svgnames*,x11names*}{xcolor}
%
\documentclass[
  11pt,
  french,
  ignorenonframetext,
  aspectratio=169,
  aspectratio=169]{beamer}
\usepackage{pgfpages}
\setbeamertemplate{caption}[numbered]
\setbeamertemplate{caption label separator}{: }
\setbeamercolor{caption name}{fg=normal text.fg}
\beamertemplatenavigationsymbolsempty

\RequirePackage{luatex85}

\usepackage{tikz}
\usepackage{pgffor}
\newcommand\mytikzmark[3][]{%
  \tikz[remember picture,baseline=(#2.base)]{\node(#2)[outer sep=0pt,#1]{#3};}%
}
%\usepackage{adjustbox}
\usepackage[export]{adjustbox}
\usepackage{bm}

\usepackage{pgfplots}
\usepgfplotslibrary{dateplot}


%%
%%% Definition of colors
%%% Source: https://latexcolor.com/
\definecolor{blanchedalmond}{rgb}{1.0, 0.92, 0.8}
\definecolor{blond}{rgb}{0.98, 0.94, 0.75}
%%% End of definition of colors
%%


\usepackage{float}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}


% Prevent slide breaks in the middle of a paragraph
\widowpenalties 1 10000
\raggedbottom
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math}
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \setmainfont[]{Overlock}
\setsansfont{Overlock} % cute !

\fi
\usetheme[]{metropolis}
\usefonttheme{serif} % use mainfont rather than sansfont for slide text
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\hypersetup{
  pdftitle={~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Calcul géométrique rapide ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .~~~~ ~~~~~~~~~~~~~~~~~~~~pour la vision et les sciences des données},
  pdfauthor={Jean Feydy},
  pdflang={fr},
  colorlinks=true,
  linkcolor=black,
  filecolor=Maroon,
  citecolor=Blue,
  urlcolor=blue,
  pdfcreator={LaTeX via pandoc}}
\urlstyle{same} % disable monospaced font for URLs
\newif\ifbibliography
\usepackage{listings}
\newcommand{\passthrough}[1]{#1}
\lstset{defaultdialect=sh}
\lstset{framexleftmargin=0mm, frame=trBL,backgroundcolor=\color{blanchedalmond!5},numbers=left,numberstyle=\scriptsize,basicstyle=\small}
\lstset{aboveskip=5mm,belowskip=5mm,xleftmargin=20pt,xrightmargin=5pt}
% \lstset{prebreak={\raisebox{0ex}[0ex][0ex]}}
% \lstset{postbreak={\raisebox{0ex}[0ex][0ex]\space}}
\lstset{breaklines=true,breakatwhitespace=true}
\usepackage{graphicx,grffile}
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi}
\def\maxheight{\ifdim\Gin@nat@height>\textheight\textheight\else\Gin@nat@height\fi}
\makeatother
% Scale images if necessary, so that they will not overflow the page
% margins by default, and it is still possible to overwrite the defaults
% using explicit options in \includegraphics[width, height, ...]{}
\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio}
% Set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering

%
% When using babel or polyglossia with biblatex, loading csquotes is recommended 
% to ensure that quoted texts are typeset according to the rules of your main language.
%
\usepackage{csquotes}




%
% blockquote
%
\definecolor{blockquote-border}{RGB}{221,221,221}
\definecolor{blockquote-text}{RGB}{89,89,89}
\usepackage{mdframed}
\newmdenv[rightline=false,bottomline=false,topline=false,linewidth=3pt,linecolor=blockquote-border,skipabove=\parskip]{customblockquote}
\renewenvironment{quote}{\begin{customblockquote}\list{}{\rightmargin=0em\leftmargin=0em}%
\item\relax\color{blockquote-text}\ignorespaces}{\unskip\unskip\endlist\end{customblockquote}}

%
% Source Sans Pro as the de­fault font fam­ily
% Source Code Pro for monospace text
%
% 'default' option sets the default 
% font family to Source Sans Pro, not \sfdefault.
%

\ifxetex
  % Load polyglossia as late as possible: uses bidi with RTL langages (e.g. Hebrew, Arabic)
  \usepackage{polyglossia}
  \setmainlanguage[]{french}
\else
  \usepackage[shorthands=off,main=french]{babel}
\fi

\title{\centering ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Calcul
géométrique rapide
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.~~~~ ~~~~~~~~~~~~~~~~~~~~pour la vision et les
sciences des données}
\author[shortname]{\centering Jean Feydy \\INRIA
Paris\\[.5cm]}
\date{\centering 17 septembre 2021}
%\date{\centering 17 sept 2021}
%%\institute{INRIA Paris}
%





\usepackage{booktabs}
\usepackage[scale=2]{ccicons}

\usepackage{changepage}

\usepackage[cache=false]{minted}

\usepackage{import}
\usepackage{mathtools}
\usepackage{subcaption}
\usepackage{hyperref}
\usepackage[normalem]{ulem}
\usepackage{makecell}
\usepackage{multirow}
\usepackage{xspace}
\usepackage{xstring}

\definecolor{x}{RGB}{8,8,153}
\definecolor{y}{RGB}{153,8,8}
\definecolor{c}{RGB}{0,100,0}
\definecolor{k}{RGB}{0,100,0}
\definecolor{q}{RGB}{60,60,200}
\definecolor{v}{RGB}{60,180,200}
\definecolor{p}{RGB}{30,140,210}
%\definecolor{phi}{RGB}{130,130,130}
\definecolor{phi}{RGB}{100,123,139}
%\definecolor{gamma}{RGB}{100,123,139}
\definecolor{gamma}{RGB}{80,103,120}
%\definecolor{otplan}{RGB}{204,230,255}
\definecolor{otplan}{RGB}{140,210,255}


\definecolor{dblue}{RGB}{0,0,200}
\definecolor{dred} {RGB}{200,0,0}
\definecolor{dgreen} {RGB}{0,150,0}
\definecolor{green} {RGB}{0,250,0}
\definecolor{b}{RGB}{0,0,255}
\definecolor{a} {RGB}{255,0,0}
\definecolor{grayish}{RGB}{150,150,150}

\definecolor{om}{RGB}{0,0,200}
\newcommand{\om}[1]{\textcolor{om}{#1}}

\newcommand{\xc}[1]{\textcolor{x}{#1}}
\newcommand{\yc}[1]{\textcolor{y}{#1}}

\renewcommand{\a}[1]{\textcolor{dred}{#1}}
\renewcommand{\b}[1]{\textcolor{dblue}{#1}}
\renewcommand{\v}[1]{\textcolor{dgreen}{#1}}
\newcommand{\p}[1]{\textcolor{phi}{#1}}
\newcommand{\g}[1]{\textcolor{gamma}{#1}}


\newcommand{\al}{\text{A}}
\newcommand{\be}{\text{B}}
\newcommand{\OT}{\text{OT}}
\newcommand{\D}{\text{D}}
\renewcommand{\S}{\text{S}}
\renewcommand{\C}{\text{C}}
\newcommand{\K}{\text{K}}



\renewcommand{\d}{\text{d}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
%\newcommand{\C}{\mathbb{C}}
\newcommand{\telque}{~|~}
\newcommand{\ilexiste}{\exists~}
\newcommand{\pourtout}{\forall~}
\newcommand{\non}{\neg\,}
\newcommand{\conv}{\star}
\renewcommand{\t}[1]{#1^{\mathsf{T}}}
\renewcommand{\phi}{\varphi}
\newcommand{\fou}[1]{\widehat{#1}}
\newcommand{\zp}[2][p]{%
  \!\IfStrEqCase{#1}{%
    {p}{\left(}%
    {c}{\:\left[}%
    {a}{\left\{}%
    {abs}{\left|}%
    {n}{\left\|}%
    {s}{\left<}%
    {i}{\left[\!\left[}%
  }[\left(]%
    #2%
  \IfStrEqCase{#1}{%
    {p}{\right)}%
    {c}{\right]}%
    {a}{\right\}}%
    {abs}{\right|}%
    {n}{\right\|}%
    {s}{\right>}%
    {i}{\right]\!\right]}%
  }[\right)]%
} 

\newcommand{\contexte}[1]{\textcolor{blue}{\textbf{#1}~~}}
\newcommand{\defi}[1]{\textcolor{red!65!black}{\textbf{#1}~~}}
\renewcommand{\solution}[1]{\textcolor{green!60!black}{\textbf{#1}~~}}

\theoremstyle{definition}
%\newtheorem{definition}{Définition}
\newtheorem{dfn}{Définition}

\theoremstyle{plain}
\newtheorem{theoreme}{Theorem}

\theoremstyle{remark}
\newtheorem{rque}{Remarque}

\renewcommand{\epsilon}{\text{\varepsilon}}


\definecolor{court}{RGB}{0,90,190}
\definecolor{moyen}{RGB}{190,0,0}
\definecolor{longterme}{RGB}{40,150,0}
\newcommand{\court}[1]{\textcolor{court}{\textbf{#1}}}
\newcommand{\moyen}[1]{\textcolor{moyen}{\textbf{#1}}}
\newcommand{\longterme}[1]{\textcolor{longterme}{\textbf{#1}}}


\metroset{subsectionpage=progressbar,
          progressbar=frametitle,
          block=fill}


\begin{document}
\frame{\titlepage}

\begin{frame}{CV : un parcours ``maths-info''
dirigé vers la médecine}
\protect\hypertarget{cv-un-parcours-maths-info-diriguxe9-vers-la-muxe9decine}{}
Formation en \textbf{mathématiques} et
\textbf{sciences des données} :

\vspace*{-.25cm}
\begin{description}
\setlength\itemsep{-.5em}
\item[2012--2016] ENS Paris, mathématiques.
\item[2014--2015] M2 mathématiques, vision, apprentissage à l'ENS Cachan.
\item[2016--2019] Thèse en \textcolor{red!80!black}{\textbf{imagerie médicale}} avec Alain Trouvé de l'ENS Cachan.
\item[2019--2021] \textcolor{red!80!black}{\textbf{\emph{Deep learning} géométrique}} avec Michael Bronstein de l'Imperial College.
\item[2021+] \textcolor{red!80!black}{\textbf{Analyse de données médicales}} dans l'équipe HeKA, INRIA Paris.
\end{description}
\vspace*{.4cm}

Liens étroits avec la
\textbf{\textcolor{red!80!black}{médecine}} :

\vspace*{-.25cm}
\begin{description}
\setlength\itemsep{-.5em}
\item[2015\phantom{+}] Débruitage d'images chez \textbf{Siemens Healthcare} à Princeton.
\item[2019+] MasterClass IA--Imagerie, pour les \textbf{internes de radio} à l'Université de Paris.
\item[2020+] Colloque sur l'\textbf{Imagerie médicale à l'heure de l'IA}, à l'Institut du Cerveau.
\end{description}
\end{frame}

\begin{frame}{Ma motivation: l'analyse de données
médicales}
\protect\hypertarget{ma-motivation-lanalyse-de-donnuxe9es-muxe9dicales}{}
\vspace*{.5cm}

\includegraphics[width=1\textwidth,height=\textheight]{images/pipeline/pipeline.png}

\vspace*{.25cm}

Trois \textbf{caractéristiques} :

\begin{itemize}
\tightlist
\item
  Données \textbf{hétérogènes} : parcours de soin,
  images, etc.
\item
  Petits échantillons stratifiés : 10 - 1 000
  patients par groupe.
\item
  La gestions des \textbf{\emph{outliers}} et de
  la \textbf{queue lourde} des distributions est
  une priorité.
\end{itemize}
\end{frame}

\begin{frame}{L'anatomie computationnelle
\cite{mammography_picture,ledig2018structural,chnafa2014image}}
\protect\hypertarget{lanatomie-computationnelle}{}
\vspace*{.5cm}

\begin{columns}[T]
\begin{column}{0.3\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=3cm]{images/anatomy_problems/breast.png}

Détecter un objet

\end{center}
\end{column}

\begin{column}{0.3\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=3cm]{images/anatomy_problems/brains.jpg}

Analyser une variation

\end{center}
\end{column}

\begin{column}{0.3\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=3cm]{images/anatomy_problems/blood_flow.jpg}

Recaler un modèle

\end{center}
\end{column}
\end{columns}

\vspace*{.25cm}

Quelques particularités, dans le contexte de la
vision par ordinateur :

\begin{itemize}
\tightlist
\item
  Prises de vues \textbf{standardisées}, sans
  occlusions.
\item
  Travail de \textbf{précision} (millimétrique).
\item
  Importance des \textbf{garanties} de robustesse
  et de régularité.
\end{itemize}
\end{frame}

\begin{frame}{Un domaine en mutation}
\protect\hypertarget{un-domaine-en-mutation}{}
\begin{columns}[T]
\begin{column}{0.7\textwidth}
\begin{center} \vspace*{.5cm} \contexte{Enjeu.}
Développer des modèles qui combinent\\
\textbf{expertise} médicale et jeux de
\textbf{données}.

\end{center}

\hfill\break
\defi{Défi.} Arrivée des \textbf{cartes
graphiques} (GPU):\\
\hspace*{0.333em}\\

\begin{itemize}
\tightlist
\item
  Excellent rapport \textbf{qualité-prix} :\\
  \(\qquad\) 1 000€ \(\simeq\) 1 000 cœurs
  \(\simeq\) \(\text{10}^{\text{12}}\)
  opérations/s.
\item
  \textbf{Difficulté} : contraintes sur la gestion
  des \textbf{registres}.
\end{itemize}

\vspace*{.5cm} \begin{center}

Écosystème Python ``grand public'' consolidé
autour\\
d'un \textbf{petit nombre d'opérations
élémentaires}.

\end{center}
\end{column}

\begin{column}{0.25\textwidth}
\begin{center}

\vspace*{1cm}

\includegraphics[width=\textwidth,height=6cm]{images/ampere.jpg}

\vspace*{.25cm}

\textbf{7,000 cœurs} en batterie sur un GPU.

\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{Mon projet : un investissement de
long terme dans les fondations du domaine}
\protect\hypertarget{mon-projet-un-investissement-de-long-terme-dans-les-fondations-du-domaine}{}
\begin{center}

\vspace*{.25cm} \solution{Solution.}
\textbf{Étendre la boîte à outils standard} en
sciences des données\\
pour répondre aux défis posés par le monde
médical.\\
~\\
\textbf{Faciliter} le développement de
\textbf{modèles avancés},\\
sans compromis sur les performances numériques.

\vspace*{.5cm} \end{center}

Un travail de
fond,~~~\solution{fondations}numériques
\(\longrightarrow\) applications de
\solution{haut niveau}: \vspace*{-.25cm}

\begin{enumerate}
\tightlist
\item
  Manipulation efficace de \textbf{matrices
  ``symboliques''} (distances, noyaux, etc.).
\item
  \textbf{Transport optimal} : méthodes de tri
  généralisées.
\item
  \textbf{\emph{Deep learning}} géométrique et
  applications \textbf{biomédicales}.
\end{enumerate}

\textbf{Avenir} de ces outils et
\textbf{perspectives cliniques}.
\end{frame}

\hypertarget{matrices-symboliques}{%
\section{1. Matrices
symboliques}\label{matrices-symboliques}}

\begin{frame}{Les outils de calcul scientifique
manipulent (surtout) des matrices}
\protect\hypertarget{les-outils-de-calcul-scientifique-manipulent-surtout-des-matrices}{}
\begin{columns}[T]
\begin{column}{0.7\textwidth}
\vspace*{.25cm} \contexte{Contexte.} \textbf{Accès
mémoires} contraignants sur GPU : \vspace*{.3cm}

\begin{itemize}
\item
  \textbf{Temps de transfert} vers les registres\\
  pénalisent l'utilisation de matrices
  \textbf{denses}.
\item
  Prime aux accès mémoires \textbf{contigus}\\
  pénalise l'utilisation de matrices
  \textbf{creuses}.
\end{itemize}

\hfill\break
\defi{Défi.} Pour atteindre des performances
optimales : \vspace*{.3cm}

\begin{itemize}
\item
  Se \textbf{restreindre} aux opérations
  supportées directement par le constructeur:
  convolutions, FFT, etc.
\item
  Développer soi-même de nouvelles routines
  numériques en C++/CUDA (FAISS, KPConv\ldots) :
  \textbf{plusieurs mois de travail}.
\end{itemize}
\end{column}

\begin{column}{0.25\textwidth}
\begin{center}

\begin{tikzpicture}[scale=.9]
    \draw[draw=black, fill=blue!20] (0,0) rectangle ++(3,3);
    \draw[step=.15, color=gray] (0,0) grid ++(3,3);
    \draw[draw=black, thick] (0,0) rectangle ++(3,3);
    \node[inner sep=3pt, anchor = mid, fill=blue!5, rounded corners=2] at (1.5,1.5) {{\normalsize M[\,i\,,\,j\,]}};
\end{tikzpicture}

\textbf{Matrice dense}

\vspace*{.5cm}

\begin{tikzpicture}[scale=.9]
    \draw[draw=black, thick] (0,0) rectangle ++(3,3);
    \node[inner sep=0pt, anchor = mid] at (1.5,1.5) {{\normalsize ($\text{i}_\text{n}$, $\text{j}_\text{n}$, $\text{M}_\text{n}$)}};
    \draw[fill=blue!20] (4*.15,1*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (15*.15,1*.15) rectangle ++(.15,.15);
    %
    \draw[fill=blue!20] (2*.15,2*.15) rectangle ++(.15,.15);
    %
    \draw[fill=blue!20] (9*.15,3*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (16*.15,3*.15) rectangle ++(.15,.15);
    %
    %\draw[fill=blue!20] (3*.15,4*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (6*.15,4*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (4*.15,6*.15) rectangle ++(.15,.15);
    %\draw[fill=blue!20] (14*.15,7*.15) rectangle ++(.15,.15);
    %\draw[fill=blue!20] (2*.15,7*.15) rectangle ++(.15,.15);
    %
    \draw[fill=blue!20] (18*.15,8*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (1*.15,9*.15) rectangle ++(.15,.15);
    %\draw[fill=blue!20] (16*.15,10*.15) rectangle ++(.15,.15);
    %
    \draw[fill=blue!20] (6*.15,13*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (16*.15,13*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (4*.15,14*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (12*.15,15*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (2*.15,16*.15) rectangle ++(.15,.15);
    \draw[fill=blue!20] (10*.15,17*.15) rectangle ++(.15,.15);
\end{tikzpicture}

\textbf{Matrice creuse}

\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{La bibliothèque KeOps: support
efficace des matrices symboliques}
\protect\hypertarget{la-bibliothuxe8que-keops-support-efficace-des-matrices-symboliques}{}
\begin{columns}[T]
\begin{column}{0.7\textwidth}
\solution{Solution.} KeOps --
\textcolor{blue}{\texttt{www.kernel-operations.io}}
: \vspace*{.2cm}

\begin{itemize}
\tightlist
\item
  Pour PyTorch, NumPy, Matlab et R sur \textbf{CPU
  et GPU}.
\item
  \textbf{Différentiation automatique}.
\item
  \textbf{Compilation} à la volée de
  \textbf{schémas optimisés} en C++,\\
  exécutés pour chaque \textbf{réduction} (somme,
  min, etc.).
\end{itemize}

\hfill\break
Si la formule ``F'' est simple (\(\leqslant\) 100
opérations arithmétiques):\\
\(\qquad\) calcul ``100k \(\times\)
100k''~~~\(\rightarrow\)~~10ms -- 100ms,\\
\(\qquad\) calcul ~~~``1M \(\times\) 1M''~~~
~~\(\rightarrow \phantom{\text{0m}}\) 1s -- 10s.

\vspace*{.5cm}

\begin{center}

Limite matérielle de \(\text{10}^{\text{12}}\)
opérations/s.\\
Exécution \textbf{10 à 100 fois plus rapide} /
code GPU standard\\
pour une large gamme de problèmes.

\end{center}
\end{column}

\begin{column}{0.25\textwidth}
\begin{center}

\begin{tikzpicture}[scale=.9]
    % Left border:
    \draw[draw=black, fill=red!20] (-.45,0) rectangle ++(.3,3);
    \draw[draw=black, fill=red!80] (-.45,9*.15) rectangle ++(.3,.15);
    \draw[step=.15, color=gray] (-.45,0) grid ++(.3,3);
    \draw[draw=black] (-.45,0) rectangle ++(.3,3);
    %
    % Top border:
    \draw[draw=black, fill=green!20] (0,3.15) rectangle ++(3,.3);
    \draw[draw=black, fill=green!80] (6*.15,3.15) rectangle ++(.15,.3);
    \draw[step=.15, color=gray] (0,3.15) grid ++(3,.3);
    \draw[draw=green!50!black] (0,3.15) rectangle ++(3,.3);
    %
    \draw[draw=black,thick] (0,0) rectangle ++(3,3);
    %
    \draw[->, thick, color=red!80!black] (.5*.15, 9.5*.15) -- (5*.15, 9.5*.15);
    \draw[->, thick, color=green!50!black] (6.5*.15, 19.5*.15) -- (6.5*.15, 11*.15);
    %
    \draw[fill=blue!40] (6*.15,9*.15) rectangle ++(.15,.15);
    \node[inner sep=0pt, anchor = mid, color=blue!50!black] at (1.95,1.4) {\normalsize{F(\,\textcolor{red!80!black}{$\text{x}_\text{i}$}\,,\,\textcolor{green!50!black}{$\text{y}_\text{j}$}\,)}};
\end{tikzpicture}

\textbf{Matrice symbolique}\\
Formules + données ~

\end{center} \vspace*{.5cm}

\begin{itemize}
\tightlist
\item
  Distances
  d(\textcolor{red!80!black}{$\text{x}_\text{i}$},\textcolor{green!50!black}{$\text{y}_\text{j}$}).
\item
  Noyaux
  k(\textcolor{red!80!black}{$\text{x}_\text{i}$},\textcolor{green!50!black}{$\text{y}_\text{j}$}).
\item
  Nombreuses transformées.
\end{itemize}
\end{column}
\end{columns}

\end{frame}

\begin{frame}[fragile]{Premier exemple : la recherche de plus proches voisins}

On crée de grands nuages de points avec \textbf{la syntaxe PyTorch standard}:
\vspace*{-.3cm}
\begin{minted}[bgcolor=blue!4,fontsize=\footnotesize,mathescape,tabsize=4,escapeinside=||]{python}
import torch
N, M, D = 10**6, 10**6, 50
x = torch.rand(N, 1, D).cuda()  # (1M,  1, 50) array
y = torch.rand(1, M, D).cuda()  # ( 1, 1M, 50) array
\end{minted}

%\pause
\vspace*{-.6cm}
On convertit les tableaux \textbf{denses} en matrices \textbf{symboliques} :
\vspace*{-.3cm}
\begin{minted}[bgcolor=blue!4,fontsize=\footnotesize,mathescape,tabsize=4,escapeinside=||,highlightlines={1-2}]{python}
from pykeops.torch import LazyTensor
x_i, y_j = LazyTensor(x), LazyTensor(y)
\end{minted}

%\pause
\vspace*{-.6cm}
On crée une grande \textbf{matrice symbolique} des distances au carré :
\vspace*{-.3cm}
\begin{minted}[bgcolor=blue!4,fontsize=\footnotesize,mathescape,tabsize=4,escapeinside=||]{python}
D_ij = ((x_i - y_j) ** 2).sum(dim=2)  # (1M, 1M) symbolique
\end{minted}

%\pause
\vspace*{-.6cm}
On utilise une \textbf{réduction} \texttt{.argmin()} pour chercher les plus proches voisins :
\vspace*{-.3cm}
\begin{minted}[bgcolor=blue!4,fontsize=\footnotesize,mathescape,tabsize=4,escapeinside=||]{python}
indices_i = D_ij.argmin(dim=1)  # -> tenseur torch standard
\end{minted}

\end{frame}


\begin{frame}[fragile]{La bibliothèque KeOps combine performances et flexibilité}

\begin{center}

Code précédent = méthode \textbf{compétitive}
avec\\
les implémentations C++/CUDA de référence
(\textbf{FAISS})\ldots{}\\
Et qui peut être utilisée avec \textbf{n'importe
quelle métrique} !

\end{center}

\begin{minted}[bgcolor=blue!4,fontsize=\footnotesize,mathescape,tabsize=4]{python}
D_ij = ((x_i - x_j) ** 2).sum(dim=2)     # Euclidienne
M_ij =  (x_i - x_j).abs().sum(dim=2)     # Manhattan
C_ij = 1 - (x_i | x_j)                   # Cosinus
H_ij = D_ij / (x_i[...,0] * x_j[...,0])  # Hyperbolique
\end{minted}

\vspace*{-.4cm}

KeOps supporte des \textbf{formules} et
\textbf{variables} arbitraires avec :

\begin{itemize}
\tightlist
\item
  \textbf{Réductions:} somme, log-sum-exp, K-min,
  produit matrice-vecteur, etc.
\item
  \textbf{Opérations:} \(+\), \(\times\), sqrt,
  exp, réseaux de neurones, etc.
\item
  \textbf{Schémas avancés:} calcul par batches,
  parcimonie par blocs, etc.
\item
  \textbf{Différentiation automatique:}
  intégration complète avec PyTorch.
\end{itemize}

\end{frame}

\begin{frame}{KeOps nous permet de tirer le meilleur parti de notre matériel, simplement}

\begin{center}
    Benchmark d'une \textbf{convolution} avec un noyau Gaussien,\\
    entre \textbf{nuages de N points 3D} sur un GPU RTX 2080 Ti. 
    %\vspace*{-.3cm}

    \resizebox{.85\linewidth}{!}{\input{images/benchmarks/benchmark_gaussianconv.tex}}
\end{center}
\end{frame}

\hypertarget{applications}{%
\section{Applications}\label{applications}}

\begin{frame}{KeOps facilite la recherche en
apprentissage machine}
\protect\hypertarget{keops-facilite-la-recherche-en-apprentissage-machine}{}
\begin{columns}[T]
\begin{column}{0.5\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=5cm]{images/applications/kmeans_2D.png}

\vspace*{.25cm} K-Means. \end{center}
\end{column}

\begin{column}{0.5\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=5cm]{images/applications/GMM.png}

\vspace*{.25cm} Mixtures de Gaussiennes.
\end{center}
\end{column}
\end{columns}

\begin{center}\vspace*{.3cm} KeOps est utilisable
avec la formule, distance ou noyau de
\textbf{votre choix} ! \end{center}
\end{frame}

\begin{frame}{KeOps facilite la recherche en
apprentissage machine}
\protect\hypertarget{keops-facilite-la-recherche-en-apprentissage-machine-1}{}
\begin{columns}[T]
\begin{column}{0.5\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=5cm]{images/applications/spectral.png}

\vspace*{.25cm} Analyse spectrale. \end{center}
\end{column}

\begin{column}{0.5\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=5cm]{images/applications/WordNet.png}

\vspace*{.25cm} UMAP dans un espace hyperbolique.
\end{center}
\end{column}
\end{columns}

\begin{center}\vspace*{.21cm} KeOps est utilisable
avec la formule, distance ou noyau de
\textbf{votre choix} ! \end{center}
\end{frame}

\begin{frame}{Applications au Krigeage, aux
splines, aux processus Gaussiens et aux noyaux}
\protect\hypertarget{applications-au-krigeage-aux-splines-aux-processus-gaussiens-et-aux-noyaux}{}
\textbf{Un outil standard pour la régression}
\cite{leclercq2018bayesian} :

\begin{center}

\includegraphics[width=\textwidth,height=3.5cm]{images/applications/GP_regression.png}

\end{center}

Sous le capot, on résout un \textbf{système
linéaire à noyaux} :

\vspace*{-.5cm}

\[ (\lambda \,\text{Id} + K_{xx}) \,a ~=~b 
\qquad\text{i.e.}\qquad
a ~\gets~(\lambda \,\text{Id} + K_{xx})^{-1} b \]

où \(~~\lambda \geqslant 0~~\) et
\(~~(K_{xx})_{i,j} = k(x_i,x_j)~~\) est une
matrice symétrique, définie positive.
\end{frame}

\begin{frame}{Applications au Krigeage, aux
splines, aux processus Gaussiens et aux noyaux}
\protect\hypertarget{applications-au-krigeage-aux-splines-aux-processus-gaussiens-et-aux-noyaux-1}{}
\textbf{Les tenseurs symboliques
\(~~(K_{xx})_{i,j} = k(x_i,x_j)~\):}

\begin{itemize}
\item
  Peuvent être interfacés avec des
  \textbf{solveurs standards}: SciPy, GPyTorch,
  etc.\\
\item
  GPyTorch sur le jeu de données 3DRoad (N = 278k,
  D = 3) :
  \centerline{\defi{\textbf{7h} avec 8 GPUs} $~~\rightarrow~~$ \solution{\textbf{15mn} avec 1 GPU.}}\\
  ~\\
\item
  Fournissent une \textbf{plateforme efficace et
  flexible} pour les projets de recherche :\\
  voir par exemple \emph{Kernel methods through
  the roof: handling \textbf{billions of points}
  efficiently},\\
  par G. Meanti, L. Carratino, L. Rosasco, A. Rudi
  (2020).
\end{itemize}
\end{frame}

\begin{frame}{KeOps permet aux chercheurs de se
concentrer sur leurs modèles}
\protect\hypertarget{keops-permet-aux-chercheurs-de-se-concentrer-sur-leurs-moduxe8les}{}
Quelques applications aux \textbf{systèmes
dynamiques}
\cite{degond2008continuum,degond2017alignment}\\
et aux \textbf{statistiques} \cite{CMC} avec A.
Diez, G. Clarté et P. Degond:

\begin{columns}[T]
\begin{column}{0.5\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=4cm]{images/applications/Vicsek_3D.png}

\vspace*{.25cm} Modèle de Vicsek orienté en 3D,\\
démo interactive avec 2k \textbf{oiseaux}.
\end{center}
\end{column}

\begin{column}{0.5\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=4cm]{images/applications/Vicsek_2D.png}

\vspace*{.25cm} Modèle de Vicsek 2D sur le tore,\\
en temps réel avec 100k \textbf{nageurs}.
\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{KeOps permet aux chercheurs de se
concentrer sur leurs modèles}
\protect\hypertarget{keops-permet-aux-chercheurs-de-se-concentrer-sur-leurs-moduxe8les-1}{}
\(\qquad\qquad\Longrightarrow~~\) On simule
plusieurs \textbf{millions d'agents} avec de
simples scripts Python.\\

\begin{columns}[T]
\begin{column}{0.5\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=4cm]{images/applications/packing.png}

\vspace*{.25cm} Problème de
\textbf{\emph{packing}}\\
avec 10k boules répulsives. \end{center}
\end{column}

\begin{column}{0.5\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=4cm]{images/applications/CMC_hyperbolic.png}

\vspace*{.25cm} \textbf{Échantillonnage} de Monte
Carlo Collectif\\
dans un espace hyperbolique. \end{center}
\end{column}
\end{columns}
\end{frame}

\hypertarget{transport-optimal}{%
\section{2. Transport
optimal}\label{transport-optimal}}

\begin{frame}{Le transport optimal (OT) généralise
le tri aux espaces de dimension D \(>\) 1}
\protect\hypertarget{le-transport-optimal-ot-guxe9nuxe9ralise-le-tri-aux-espaces-de-dimension-d-1}{}
\begin{columns}[T]
\begin{column}{0.7\textwidth}
\contexte{Contexte.}
Si~~\(\a{\text{A} = (\text{x}_\text{1}, \dots, \text{x}_\text{N})}\)~~et~~\(\b{\text{B} = (\text{y}_\text{1}, \dots, \text{y}_\text{N})}\)~~sont
deux nuages de N points dans
\(\mathbb{R}^\text{D}\), on définit :

\vspace*{-.3cm}
\begin{equation*}
\OT(\a{\text{A}},\b{\text{B}}) ~=~ \min_{\sigma \in \mathcal{S}_\text{N}}~ \frac{\text{1}}{\text{2N}} \sum_{\text{i\,=1}}^\text{N} \v{\|~\a{\text{x}_i} - \b{\text{y}_{\sigma(i)}}\|^2}
\end{equation*}
\vspace*{.2cm}

Généralise le \textbf{tri} aux espaces
métriques.\\
\textbf{Problème linéaire} sur la matrice de
permutation \(\g{\text{P}}\) :

\begin{equation*}
\OT(\a{\text{A}},\b{\text{B}}) ~=~ \min_{\g{\text{P}} \in \mathbb{R}^{\text{N}\times \text{N}} ~}
\frac{\text{1}}{\text{2N}} \sum_{\text{i, j\,=1}}^{\text{N}} \g{\text{P}_{i,j}} \cdot \v{ \|~ \a{\text{x}_i} - \b{\text{y}_j} \|^2 }~,
\end{equation*}
\vspace*{-.6cm}
\begin{align*}
&\text{s.t.} &
\g{ \text{P}_{i,j}} ~&\geqslant ~\text{0} &
\underbrace{\b{\textstyle\sum_j} \g{ \text{P}_{i,j}} ~=~ \a{\text{1}}}_{\text{Chaque point au départ\dots{}}}& &
\underbrace{\vphantom{\textstyle\sum_j}\a{\textstyle\sum_i} \g{ \text{P}_{i,j}} ~=~ \b{\text{1}}~.}_{\text{est transporté jusqu'à l'arrivée.}}
\end{align*}
\end{column}

\begin{column}{0.25\textwidth}
\begin{center}
    \begin{tikzpicture}[scale=.5,x=.7cm,y=-.7cm]
        %\node[anchor = east] at (0,4) {source};
        \draw[->,>=latex,thick,color=black]  (0,0)--(0,16.5);
        \node[circle,fill=red!80!black,inner sep=0pt,minimum size=7pt,label=left:{$\a{\text{x}_\text{1}}$}] (x1) at (0,1) {};
        \node[circle,fill=red!80!black,inner sep=0pt,minimum size=7pt,label=left:{$\a{\text{x}_\text{2}}$}] (x2) at (0,2) {};
        \node[circle,fill=red!80!black,inner sep=0pt,minimum size=7pt,label=left:{$\a{\text{x}_\text{3}}$}] (x3) at (0,3.5) {};
        \node[circle,fill=red!80!black,inner sep=0pt,minimum size=7pt,label=left:{$\a{\text{x}_\text{4}}$}] (x4) at (0,5) {};
        \node[circle,fill=red!80!black,inner sep=0pt,minimum size=7pt,label=left:{$\a{\text{x}_\text{5}}$}] (x5) at (0,7.5) {};


        %\node[anchor = east] at (0,0) {cible};
        \draw[->,>=latex,thick,color=black]  (4,0)--(4,16.5);
        \node[circle,fill=blue,inner sep=0pt,minimum size=7pt,label=right:{$\b{\text{y}_\text{3}}$}] (y1) at (4,5.5) {};
        \node[circle,fill=blue,inner sep=0pt,minimum size=7pt,label=right:{$\b{\text{y}_\text{5}}$}] (y2) at (4,7) {};
        \node[circle,fill=blue,inner sep=0pt,minimum size=7pt,label=right:{$\b{\text{y}_\text{2}}$}] (y3) at (4,8.5) {};
        \node[circle,fill=blue,inner sep=0pt,minimum size=7pt,label=right:{$\b{\text{y}_\text{4}}$}] (y4) at (4,12.5) {};
        \node[circle,fill=blue,inner sep=0pt,minimum size=7pt,label=right:{$\b{\text{y}_\text{1}}$}] (y5) at (4,15) {};

        \node[anchor = north, align=center, color=otplan!70!black] at (2,17) {{assignement}\\ ${\sigma:\zp[i]{1,5}\rightarrow \zp[i]{1,5}}$};

        \draw[color=otplan,very thick] (x1) -- (y1) (x2) -- (y2) (x3) -- (y3) (x4) -- (y4) (x5) -- (y5);

        %\onslide<2,3,4,6->{\draw[color=green!80!black,thick] (x3) -- (y3) (x4) -- (y4);}
        %\onslide<5>{\draw[color=green!80!black] (x4) -- (y3);
        %\draw[color=green!80!black, very thick] (x3) -- (y4);}

    \end{tikzpicture}
    \end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{Propriétés clés de cette distance
``à permutation près''}
\protect\hypertarget{propriuxe9tuxe9s-cluxe9s-de-cette-distance-uxe0-permutation-pruxe8s}{}
La distance de Wasserstein
\(\sqrt{\OT}(\a{\text{A}},\b{\be})\) est :

\begin{itemize}
\item
  \textbf{Symétrique} :
  \(\qquad\qquad\qquad \OT(\a{\text{A}},\b{\be}) = \text{OT}(\b{\be},\a{\text{A}})\,\).
\item
  \textbf{Positive} :
  \(\qquad\qquad\qquad\qquad \OT(\a{\text{A}},\b{\be}) \geqslant \text{0} \,\).
\item
  \textbf{Définie} :
  \(\qquad\qquad~~~~~~\OT(\a{\text{A}},\b{\be})=\text{0} \Longleftrightarrow \a{\text{A}} = \b{\be}\,\).
\item
  \textbf{Compatible avec les translations} :
  \(\OT(\a{\text{A}},\,\text{Translation}_{\v{\vec{v}}}(\a{\text{A}})\,) = \tfrac{1}{2}\|\, \v{\vec{v}}\,\|^2\,\).\\
\item
  Plus généralement, OT retrouve l'unique
  \textbf{gradient d'une fonction convexe}\\
  \(\text{T} = \nabla \phi\) qui envoie
  \(\a{\text{A}}\) sur \(\b{\be}\) :
\end{itemize}

\vspace*{-1cm}
\begin{alignat*}{10}
\text{En dimension~}&\text{1}, &\qquad& 
(\a{\text{x}_\text{i}} - \a{\text{x}_\text{j}})&~\cdot~& (\b{\text{y}_{\sigma(\text{i})}} - \b{\text{y}_{\sigma(\text{j})}}) 
~&&\geqslant~ \text{0}  \\
\text{En dimension~}&\D, && 
\langle\, \a{\text{x}_\text{i}} - \a{\text{x}_\text{j}} \,&~,~&\, \b{ \text{T}(\text{x}_\text{i}) } - \b{ \text{T}(\text{x}_\text{j})  } \,\rangle_{\R^\D}
~&&\geqslant~ \text{0} ~.
\end{alignat*}

%\vspace{-.5cm}
\begin{center}
$\Longrightarrow\qquad$ Généralisation attrayante de la notion d'\textbf{application croissante}.
\end{center}


\end{frame}

\begin{frame}{Un exemple simple en 2D}

    \vspace{.3cm}
    \begin{center}
        \includegraphics<1>[height=.8\textheight]{images/flows_2D/sinkhorn_multiscale_L2_001/000.png}%
        \includegraphics<2>[height=.8\textheight]{images/flows_2D/sinkhorn_multiscale_L2_001/025.png}%
        \includegraphics<3>[height=.8\textheight]{images/flows_2D/sinkhorn_multiscale_L2_001/050.png}%
        \includegraphics<4>[height=.8\textheight]{images/flows_2D/sinkhorn_multiscale_L2_001/100.png}%
        \includegraphics<5>[height=.8\textheight]{images/flows_2D/sinkhorn_multiscale_L2_001/500.png}%
        \includegraphics<6>[height=.8\textheight]{images/flows_2D/sinkhorn_multiscale_L2_001/1000.png}%
    \end{center}
    
    %\vspace{-.5cm}
    \hspace*{6cm}
    $\text{t} = $ %
    \only<1>{\texttt{.00}}%
    \only<2>{\texttt{.25}}%
    \only<3>{\texttt{.50}}%
    \only<4>{\texttt{1.00}}%
    \only<5>{\texttt{5.00}}%
    \only<6>{\texttt{10.00}}%

\end{frame}


\begin{frame}{Un modèle efficace... Mais attention aux déchirures !}
    \vspace*{1cm}

    \centerline{
    \begin{tabular}{ccc}
    \includegraphics<1>[height=6cm]{images/registration_2D/densities/000.png}%
    \includegraphics<2>[height=6cm]{images/registration_2D/crescents/000.png}%
    \includegraphics<3>[height=6cm]{images/registration_2D/worms/000.png}%
    \includegraphics<4>[height=6cm]{images/registration_2D/moons/000.png}%
    &\qquad&
    \includegraphics<1>[height=6cm]{images/registration_2D/densities/010.png}%
    \includegraphics<2>[height=6cm]{images/registration_2D/crescents/010.png}%
    \includegraphics<3>[height=6cm]{images/registration_2D/worms/010.png}%
    \includegraphics<4>[height=6cm]{images/registration_2D/moons/010.png}%
    \\
    Avant
    &&
    Après
    \end{tabular}
    }
\end{frame}

\begin{frame}{Solutions géométriques aux problèmes
des moindres carrés \cite{agueh_2011}}
\protect\hypertarget{solutions-guxe9omuxe9triques-aux-probluxe8mes-des-moindres-carruxe9s}{}
\vspace*{-.5cm}
\begin{align*}
    \text{Barycentre}~~\a{\al^*}
    ~=~\arg \min_{\a{\al}} 
    \sum_{i=1}^4 \,\lambda_i\,\text{Loss}(\,\a{\al}\,,\, \b{\be_i}\,)~.
\end{align*}

\begin{columns}[T]
\begin{column}{0.45\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=0.6\textheight]{images/wasserstein/linear_barycenters.png}

Barycentres \textbf{euclidiens}.\\
\(\text{Loss}(\a{\al},\b{\be}) = \|\a{\al}-\b{\be}\|^2_{L^2}\)

\end{center}
\end{column}

\begin{column}{0.45\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=0.6\textheight]{images/wasserstein/wasserstein_barycenters.png}

Barycentres de \textbf{Wasserstein}.\\
\(\text{Loss}(\a{\al},\b{\be}) = \OT(\a{\al},\b{\be})\)

\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{~Régularisation et biais entropique}
\protect\hypertarget{ruxe9gularisation-et-biais-entropique}{}
\begin{columns}[T]
\begin{column}{0.75\textwidth}
\begin{center}\vspace*{.25cm}

\defi{Défi.} Assignement linéaire : difficile à
résoudre en toute généralité.\\
\textbf{Structure} de la matrice des distances
\(\v{ \|\,\a{\text{x}_i} -\b{\text{y}_j} \| }\)\\
\(\Longrightarrow\) \textbf{Accélérer} les
calculs.\\
\hspace*{0.333em}

Outil fondamental : le \textbf{transport
régularisé}\\
\(\OT_\varepsilon(\a{\text{A}}, \b{\text{B}}) \simeq \OT(\a{\text{A}}, \b{\text{B}}) +\)
\textbf{pénalité entropique}
d'intensité~~\(\varepsilon > \text{0}\).\\
\hspace*{0.333em}

Approximation \textbf{lisse} et strictement
\textbf{convexe} : plus facile à étudier,\\
très populaire algorithme de \textbf{Sinkhorn} (ou
``\emph{SoftAssign}'').\\
\hspace*{0.333em}

En revanche, elle ne \textbf{vérifie pas les
axiomes d'une distance} :\\
\(\OT_\varepsilon(\b{\text{B}}, \b{\text{B}}) > \text{0}\).

\end{center}
\end{column}

\begin{column}{0.22\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=6cm]{images/bias/entropic_bias_vertical_gris.png}

\(\arg \min_{\a{\text{A}}} \OT_\varepsilon(\a{\text{A}}, \b{\text{B}})\).

\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{Solution théorique : garantie de
robustesse au biais entropique}
\protect\hypertarget{solution-thuxe9orique-garantie-de-robustesse-au-biais-entropique}{}
\begin{columns}[T]
\begin{column}{0.75\textwidth}
\begin{center}

\solution{Solution.} Les \textbf{divergences de
Sinkhorn} sont définies par :\\
\(\S_\varepsilon(\a{\al}, \b{\be}) = \OT_\varepsilon(\a{\al}, \b{\be}) - \tfrac{1}{2} \OT_\varepsilon(\a{\al}, \a{\al}) - \tfrac{1}{2} \OT_\varepsilon(\b{\be}, \b{\be})\)\\
afin de retrouver une valeur nulle lorsque
\(\a{\text{A}} = \b{\text{B}}\).

\end{center}

\vspace*{.25cm}

\begin{theorem}[~$\S_\varepsilon$ se prête bien à l'optimisation]
    \hspace*{5mm}Pour tous échantillons~~$\a{\al}$~~et~~$\b{\be}$~:
    \begin{center}\vspace{-.1cm}
        $\S_\varepsilon(\a{\al},\b{\be})~\geqslant~\text{0}$
        ~~~avec égalité ssi.~~~$\a{\al}=\b{\be}$~, \\[.1cm]
        $\a{\al}\mapsto \S_\varepsilon(\a{\al},\b{\be})$
        ~~est convexe au sens des mesures, \\
        différentiable et métrise la convergence en loi.\\[.3cm]
    \end{center}
    \hspace*{5mm}On généralise ce résultat aux \textbf{mesures} de Radon positives,\\
    \hspace*{5mm} à des \textbf{métriques} $\v{ \|\,\a{\text{x}_i} -\b{\text{y}_j} \| }$ générales et au cas ``\textbf{unbalanced}''.
    \vspace{.3cm}
\end{theorem}

\end{column}

\begin{column}{0.22\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=6cm]{images/bias/Seps_slope_gris.png}

\(\arg \min_{\a{\text{A}}} \S_\varepsilon(\a{\text{A}}, \b{\text{B}})\).

\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{En pratique, comment résoudre le
problème de transport optimal ?}
\protect\hypertarget{en-pratique-comment-ruxe9soudre-le-probluxe8me-de-transport-optimal}{}
Dates clés pour le transport optimal avec N points
:

\begin{itemize}
\tightlist
\item
  \cite{kantorovich1942translocation} : problème
  \defi{dual}de Kantorovitch.
\item
  \cite{kuhn1955hungarian} : algorithme
  \defi{hongrois}en \(O(\text{N}^3)\).
\item
  \cite{bertsekas79auction} : méthode des
  \textbf{enchères} en \(O(\text{N}^2)\).
\item
  \cite{kosowsky1994invisible} :
  \textbf{SoftAssign} = Sinkhorn + recuit simulé,
  en \(O(\text{N}^2)\).
\item
  \cite{gold1998new,TPSRPM} : \textbf{Robust Point
  Matching} = Sinkhorn comme fonction d'erreur.
\item
  \cite{CuturiSinkhorn} : utilisation des
  \contexte{GPUs.}
\item
  \cite{merigot2011multiscale,levy2015numerical,schmitzer2019stabilized}
  : solveurs \textbf{multi-échelles} en
  \(O(\text{N}\log \text{N})\).\\
  \(~\)
\item
  \solution{Solution,}aujourd'hui :
  \textbf{algorithme de Sinkhorn multi-échelles,
  sur GPU}.
\end{itemize}

\begin{center} \(\Longrightarrow~~~\) Algorithme
de \solution{tri rapide}généralisé. \end{center}
\end{frame}

\begin{frame}{Solution pratique : l'algorithme de
Sinkhorn multi-échelles}
\protect\hypertarget{solution-pratique-lalgorithme-de-sinkhorn-multi-uxe9chelles}{}
\begin{center} 
    Entre 2015 et 2020, l'état de l'art pour le transport
    optimal discret a été amélioré par \\
    \textbf{un à trois ordres de grandeur} -- selon le régime d'utilisation :
    
    Sinkhorn GPU
    $\xrightarrow{\times \text{10}}$
    + KeOps
    $\xrightarrow{\times \text{10}}$
    + Recuit simulé
    $\xrightarrow{\times \text{10}}$
    + Multi-échelle
    
    
    Résoudre un problème de transport avec une précision de 1\% :\\~
    \end{center}

    \vspace*{-.25cm}
    \begin{tabular}{cccc}
    \begin{minipage}{.2\linewidth}
    \begin{center}
    ~\\
    \texttt{pip install geomloss}\\
    +\\
    GPU récent\\ (1 000 €)
    \end{center}
    \end{minipage}
    &
    \begin{minipage}{.1\linewidth}
    ~\\
    $\Longrightarrow$
    \end{minipage}
    &
    \begin{minipage}{.3\linewidth}
    \includegraphics[height=3.5cm]{images/dragon_ball/lowres.png}
    \end{minipage}
    &
    \begin{minipage}{.3\linewidth}
    \includegraphics[height=3.5cm]{images/dragon_ball/highres.png}
    \end{minipage}
    \\
    &&
    10k points en 30-50ms
    &
    \textbf{100k points en 100-200ms}
    \end{tabular}
\end{frame}

\hypertarget{deep-learning-guxe9omuxe9trique}{%
\section{3. Deep learning
géométrique}\label{deep-learning-guxe9omuxe9trique}}

\begin{frame}{Concevoir des modèles entraînables
et adaptés aux experts}
\protect\hypertarget{concevoir-des-moduxe8les-entrauxeenables-et-adaptuxe9s-aux-experts}{}
\begin{columns}[T]
\begin{column}{0.75\textwidth}
\vspace*{.1cm} \contexte{Enjeu.} Modèles profonds
sur des \textbf{domaines non-euclidiens} (nuages
de points, surfaces, graphes, etc.), au-delà des
images 2D/3D.

\hfill\break
\defi{Défi.} En dépit d'un intérêt industriel
croissant,\\
ces modèles restent \textbf{mal supportés}
numériquement.\\
Le C++/CUDA reste (souvent) incontournable.

\hfill\break
\solution{Solution.} En quelques lignes de Python,
avec KeOps :

\begin{itemize}
\tightlist
\item
  Interactions \textbf{locales}: K-plus-proches
  voisins.
\item
  Interactions \textbf{globales}: convolutions
  généralisées.
\end{itemize}

\vspace*{.35cm}\begin{center}

\textbf{Liberté} de modélisation\\
\(\Longrightarrow\)~~\textbf{Spécificités} des
domaines étudiés.

\end{center}
\end{column}

\begin{column}{0.22\textwidth}
\begin{center}

\includegraphics[width=\textwidth,height=6cm]{images/applications/coordinates_gris.png}

Convolution quasi-géodésique sur un nuage de
points orientés.

\end{center}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{Benchmarks de quelques
``convolutions'' sur ShapeNet (N = 2,048 points
3D)}
\protect\hypertarget{benchmarks-de-quelques-convolutions-sur-shapenet-n-2048-points-3d}{}
\begin{center}

\vspace*{-.4cm}

\begin{align*}
\text{f}_\text{i} ~\gets~ 
\textcolor{red!65!black}{
\sum_{\text{x}_\text{j} \in \text{KNN}(\text{x}_\text{i})}
\text{Conv}(\text{x}_\text{i}, \text{x}_\text{j}, \text{f}_\text{j})}
\qquad
\text{ou}
\qquad
\textcolor{green!60!black}{
\sum_{\text{tous les}~\text{x}_\text{j}}
\exp(-\|\text{x}_\text{i} - \text{x}_\text{j}\|^2 / 2\sigma^2) \cdot
\text{Conv}(\text{x}_\text{i}, \text{x}_\text{j}, \text{f}_\text{j})}
\qquad
\end{align*}

\vspace*{-.3cm}

\hspace*{-.6cm}
\begin{tabular}{l@{\hskip .7cm}c@{\hskip .7cm}cc@{\hskip .7cm}cc}
    \toprule
    & PyTorch          & \multicolumn{2}{c}{JAX~~~~}        & \multicolumn{2}{c}{\textbf{KeOps}  }                                             \\
    Primitive $\text{Conv}(\text{x}_\text{i}, \text{x}_\text{j}, \text{f}_\text{j})$                     & \textcolor{red!65!black}{40-NN}            & \textcolor{red!65!black}{40-NN}                              & \textcolor{green!60!black}{Gaussien}                                 & \textcolor{red!65!black}{40-NN}                  & \textcolor{green!60!black}{Gaussien} \\
    \midrule
    % Spectral coordinates & \\
    Moyennes locales                   &
    686 \textmu{}s                 & 1,052 \textmu{}s & 469 \textmu{}s                     & 121 \textmu{}s                             & \textcolor{green!60!black}{\textbf{12 \textmu{}s}}              \\
    Matrices de covariances                  &
    700 \textmu{}s                 & 1,093 \textmu{}s & 1,259 \textmu{}s                   & 138 \textmu{}s                             & \textcolor{green!60!black}{\textbf{23 \textmu{}s}}              \\
    % Distance to tangent planes & \\
    \midrule
    MLP ($\mathrm{H}=\texttt{~8}$) &
    737 \textmu{}s                 & 1,180 \textmu{}s & 4,089 \textmu{}s                   & 192 \textmu{}s                             & \textcolor{green!60!black}{\textbf{75 \textmu{}s}}              \\
    MLP ($\mathrm{H}=\texttt{16}$) &
    775 \textmu{}s                 & 1,253 \textmu{}s & 7,043 \textmu{}s                   & \textcolor{red!65!black}{\textbf{240 \textmu{}s}}                    & 649 \textmu{}s~~                    \\
    %\midrule
    %Distance de chamfer                   & 374 \textmu{}s   & \multicolumn{2}{c}{130 \textmu{}s} & \multicolumn{2}{c}{\textbf{21 \textmu{}s}}                                       \\
    %Distance à noyaux                  & 486 \textmu{}s   & \multicolumn{2}{c}{378 \textmu{}s} & \multicolumn{2}{c}{\textbf{31 \textmu{}s}}                                       \\
    \bottomrule
\end{tabular}


\vspace*{-.3cm}

~\\
Les interactions \textcolor{green!60!black}{``entre tous les points''} deviennent \textbf{viables} :\\
nous ne sommes plus obligés de nous restreindre à des convolutions\\
très locales sur un graphe de \textcolor{red!65!black}{K-plus-proches voisins}.
\end{center}
\end{frame}

\begin{frame}{Application au \emph{docking} de protéines~\cite{dmasif}}
    \vspace*{.5cm}
    \begin{figure}
        \begin{subfigure}[t]{0.35\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/proteins/greenatoms_atoms.png}
            \caption{Données brutes : atomes en 3D.}
        \end{subfigure}
        \hfill
        \begin{subfigure}[t]{0.3\textwidth}
            \centering
            \includegraphics[width=.67\textwidth]{figures/proteins/mesh_no_edges.png}
            \caption{Interface observée.}
        \end{subfigure}
        \hfill
        \begin{subfigure}[t]{0.3\textwidth}
            \centering
            \includegraphics[width=.67\textwidth]{figures/proteins/output.png}
            \caption{Prédiction du modèle.}
        \end{subfigure}
        \vspace{.2cm}
    \end{figure}
\end{frame}



\begin{frame}{``Fast end-to-end learning on protein surfaces''~\cite{dmasif}}
    \vspace*{.5cm}
    \begin{center}
        %\includegraphics[width=1.0\linewidth]{figures/overview.pdf}
        {\scriptsize
            \def\svgwidth{\linewidth}\vspace{-2mm}
            \import{figures/}{overview.pdf_tex}
        }
    \end{center}
    \vspace{.5cm}
    
    \centerline{
    \begin{tabular}{ccc}
    \hspace*{2cm}
        \begin{minipage}{2cm}
            \includegraphics[width=\linewidth]{figures/nature_cover.png}
        \end{minipage}
        &{\huge $\longrightarrow$}
        &
        \begin{minipage}{7cm}
            $\times$100\,--$\times$1,000 plus rapide, léger\\
            \phantom{.}~et complètement différentiable.
        \end{minipage}
    \end{tabular}
    }
\end{frame}

\begin{frame}{Application à l'appariement de
poumons ``Expiration -- Inspiration''}
\protect\hypertarget{application-uxe0-lappariement-de-poumons-expiration-inspiration}{}
\begin{center}

\includegraphics[width=\textwidth,height=0.85\textheight]{images/applications/poumons.png}

\end{center}\vspace*{-.3cm}

Déformations \textbf{complexes}, haute
\textbf{résolution} (50k--300k points), haute
\textbf{précision} (\(<\) 1mm).
\end{frame}

\begin{frame}{Un recalage en trois temps}
\protect\hypertarget{un-recalage-en-trois-temps}{}
On combine :

\begin{enumerate}
\tightlist
\item
  Un \textbf{pré-recalage} global
  :~~~~~~~~~~~~~~~~~~~~~~~OT + déformation affine.
\item
  Un \textbf{recalage} ``au centimètre près'' :
  ~~réseau multi-échelles + difféomorphisme.
\item
  Un \textbf{affinage} ``au millimètre près'' :
  ~~~~~OT + régularisation spline.
\end{enumerate}

\hfill\break
Cette méthode \textbf{pragmatique} :

\begin{itemize}
\tightlist
\item
  Est \textbf{facile à entraîner} sur des données
  synthétiques.
\item
  Passe à l'échelle : 100k points en \(<\) 1s.
\item
  Donne d'excellents résultats : \textbf{KITTI}
  (\emph{scene flow}) et \textbf{DirLab}
  (poumons).
\end{itemize}
\end{frame}

\begin{frame}{Un recalage en trois temps}
\protect\hypertarget{un-recalage-en-trois-temps-1}{}
\begin{center}

\includegraphics[width=\textwidth,height=0.85\textheight]{images/applications/lung_registration/full.png}

\end{center}\vspace*{-.3cm}

\emph{Accurate point cloud registration with
\textbf{robust} optimal transport} : à paraître à
la fin du mois.
\end{frame}

\begin{frame}{Bilan : un investissement de long
terme qui porte ses fruits}
\protect\hypertarget{bilan-un-investissement-de-long-terme-qui-porte-ses-fruits}{}
Deux évolutions majeures:

\begin{itemize}
\tightlist
\item
  ``Gros'' problème géométrique :~~~~~N \(>\)
  \textbf{10k}~~~~\(\longrightarrow\)~~~~N \(>\)
  \textbf{1M}.
\item
  Transport optimal :~~~~~~~~~~~~\textbf{problème}
  linéaire ~~\(\,\,+\,\,\)~ ~~\textbf{tri rapide}
  généralisé.
\end{itemize}

\begin{center} \vspace*{.75cm}

\includegraphics[width=0.9\textwidth,height=\textheight]{images/projet/bilan.pdf}

\end{center}
\end{frame}

\hypertarget{avenir-de-ces-outils-contexte-scientifique}{%
\section{\texorpdfstring{Avenir de ces outils, \\
contexte
scientifique}{Avenir de ces outils,  contexte scientifique}}\label{avenir-de-ces-outils-contexte-scientifique}}

\begin{frame}{Un réel travail d'équipe}
\protect\hypertarget{un-ruxe9el-travail-duxe9quipe}{}
\vspace*{.5cm}

\centerline{
\begin{tabular}{cccc}
\includegraphics[height=2cm]{images/sourires/medaillons/Alain_2.png}
&
\includegraphics[height=2cm]{images/sourires/medaillons/Thibault_2.png}
&
\includegraphics[height=2cm]{images/sourires/medaillons/FX_2.png}
&
\includegraphics[height=2cm]{images/sourires/medaillons/Gabriel_2.png}
\\
Alain Trouvé
&
\textcolor{red!65!black}{Thibault Séjourné}
&
\textcolor{red!65!black}{F.-X. Vialard}
&
\textcolor{red!65!black}{Gabriel Peyré}
\\[.5cm]
\includegraphics[height=2cm]{images/sourires/medaillons/Benjamin_2.png}
&
\includegraphics[height=2cm]{images/sourires/medaillons/Joan_2.png}
&
\includegraphics[height=2cm]{images/sourires/medaillons/Freyr.png}
&
\includegraphics[height=2cm]{images/sourires/medaillons/Zhengyang.png}\\
\textcolor{blue!100!black}{Benjamin Charlier}
&
\textcolor{blue!100!black}{Joan Glaunès}
&
\textcolor{green!60!black}{Freyr Sverrisson}
&
\textcolor{green!60!black}{Shen Zhengyang}\\[.5cm]
\multicolumn{4}{c}{+ Marc Niethammer, Bruno Correia, Michael Bronstein\dots{}}
\end{tabular}
}


\end{frame}


\begin{frame}{Promouvoir des interactions entre domaines}
\vspace*{.2cm}

\begin{center}
    \includegraphics<1>[width=.75\linewidth]{images/interactions/labels.png}%
    \includegraphics<2>[width=.75\linewidth]{images/interactions/people_behind_labels.png}%
\end{center}
\end{frame}

\begin{frame}{La révolution Python}
\protect\hypertarget{la-ruxe9volution-python}{}
\begin{center}\vspace*{.3cm}

L'émergence d'une boîte à outils ouverte et
\solution{\textbf{modulaire}}\\
a été une \textbf{bénédiction} pour la
communauté.\\
~\\

Les bibliothèques de \emph{deep learning} ont mis
le \textbf{calcul sur GPU}\\
et la \textbf{différentiation automatique} à la
portée de tous.\\
(Incroyable !)\\
~\\

Ces logiciels sont soutenus par des acteurs
\textbf{industriels majeurs} (Google,
Facebook\ldots)\\
et ont permis à nos domaines \textbf{d'exploser}
au cours de la dernière décennie.\\
~\\

\solution{\textbf{Interagir}}avec d'autres
chercheurs, des médecins\\
et des ingénieurs n'a jamais été aussi
\textbf{facile}.

\end{center}
\end{frame}

\begin{frame}{La révolution Python}
\protect\hypertarget{la-ruxe9volution-python-1}{}
\begin{center}

Mais d'un autre côté, PyTorch et TensorFlow ont
aussi \defi{\textbf{biaisé}}la recherche\\
vers un \textbf{petit nombre} d'opérations
\textbf{bien supportées} :\\
convolutions et produits matrice-matrice. \\~

Ce focus n'est \textbf{pas} la conséquence d'une
limitation intrinsèque des GPUs :\\
notre matériel est parfaitement capable de
\textbf{simuler}\\
de vastes \textbf{environnements 3D} en temps réel
! \\~

En tant que chercheurs, nous devons travailler à
\solution{\textbf{ouvrir d'autres chemins.}}\\
Permettre le développement d'une gamme d'outils
\textbf{complète},\\
des méthodes convexes et \textbf{robustes}\\
aux modèles de \emph{deep learning}
\textbf{expressifs}.

\end{center}
\end{frame}

\begin{frame}{Notre contribution à la communauté}
\protect\hypertarget{notre-contribution-uxe0-la-communautuxe9}{}
KeOps et GeomLoss sont :

\begin{itemize}
\tightlist
\item
  \solution{\textbf{Rapides}}: 10 à 1,000 fois
  plus efficaces que des codes GPU standards.
\item
  \textbf{Économes en mémoire} : \(O(\text{N})\)
  et pas \(O(\text{N}^2)\).
\item
  \textbf{Versatiles}, avec une interface
  \textbf{transparente} : liberté !
\item
  \textbf{Puissantes et bien documentées} :
  pensées pour la recherche. \\~
\item
  \defi{\textbf{Lentes}}avec de \textbf{très
  grands vecteurs de \emph{features}} en dimension
  \(\text{D} > \text{100}\).
\end{itemize}

À venir cette année :

\begin{itemize}
    \item[$\rightarrow$] \textbf{Méthodes d'approximation} (Nyström, etc.) dans KeOps.
    \item[$\rightarrow$] Support optimal des \textbf{barycentres} et des \textbf{images} dans GeomLoss. 
\end{itemize}
\end{frame}

\begin{frame}{Un projet en pleine évolution}
\protect\hypertarget{un-projet-en-pleine-uxe9volution}{}
\begin{adjustwidth}{.5cm}{.2cm}
\begin{itemize}
    \setlength\itemsep{.8em}
    \item[2017--18] \defi{Preuve de concept}avec articles de conférences et codes en ligne.\\
                        Premiers retours de la communauté.

    \item[2019--21] \contexte{Bibliothèque stable}avec des théorèmes solides et une API bien documentée.\\
                        Backend KeOps pour des paquets de haut niveau. \\
                        \textbf{100k+ téléchargements} sur pip, etc.

    \item[2021--22] \solution{Bibliothèque mûre}avec des articles d'application concrets.\\
                        Fonctionne \emph{out-of-the-box} pour les étudiants et les ingénieurs.\\
                        $\Longrightarrow~~$ Refonte du moteur de compilation de KeOps pour la v1.6.\\
                        $\Longrightarrow~~$ GeomLoss comme backend pour POT v1.0.

    \item[2022+] \textbf{Une bibliothèque standard} avec de réelles applications cliniques ?
                    C'est l'objectif !
\end{itemize} 
\end{adjustwidth}
\end{frame}

\hypertarget{conclusion}{%
\section{Conclusion}\label{conclusion}}

\begin{frame}{Points clés}
\protect\hypertarget{points-cluxe9s}{}
\begin{itemize}
\tightlist
\item
  Les matrices \solution{symboliques}sont au ML
  \textbf{géométrique} ce que\\
  les matrices \textbf{creuses} sont au traitement
  de \textbf{graphes} :\\
  \(\longrightarrow~~\) KeOps:
  \textbf{accélération x30} vs.~PyTorch, TF et
  JAX.\\
  \(\longrightarrow~~\) Utiles pour de nombreux
  problèmes.\\
  ~\\
\item
  Transport optimal = \solution{tri généralisé}
  :\\
  \(\longrightarrow~~\) Appariement géométrique.\\
  \(\longrightarrow~~\) Solveurs très rapides en
  \(O(\text{N}\log \text{N})\).\\
  ~\\
\item
  Ces outils ouvrent de \textbf{nouveaux chemins}
  pour les géomètres et les statisticiens :\\
  \(\longrightarrow~~\) Les GPUs sont plus
  \textbf{versatiles} qu'on ne le croit.\\
  \(\longrightarrow~~\) Travail constant sur les
  \textbf{fondations numériques} de la
  recherche,\\
  \(\phantom{\longrightarrow}~~~\) au-delà de ce
  pourquoi Google et Facebook sont prêts à
  payer.\\
\end{itemize}
\end{frame}

\begin{frame}{Conclusion}
\protect\hypertarget{conclusion-1}{}
\textbf{KeOps} et \textbf{GeomLoss} stimulent la
recherche sur :

\begin{itemize}
\tightlist
\item
  Les méthodes de \textbf{clustering} : K-Means et
  EM rapides.
\item
  La \textbf{représentation} des données : UMAP,
  KNN rapides avec n'importe quelle métrique.
\item
  Les méthodes à \solution{noyaux}: matrices de
  noyaux.
\item
  Les \textbf{processus Gaussiens} : matrices de
  covariances. \\~
\item
  Le \solution{\emph{deep learning} géométrique}:
  convolutions sur les points.
\item
  L'imagerie \textbf{médicale} : anatomie
  computationnelle.
\item
  Les \textbf{statistiques géométriques} : au-delà
  des modèles Euclidiens.
\item
  Le traitement du \textbf{langage} :
  \emph{transformers} efficaces ?
\end{itemize}

\begin{center}\vspace*{.3cm} Qu'en pensez-vous ?
\end{center}
\end{frame}

\begin{frame}{Notre documentation et de nombreux
tutoriaux sont disponibles en ligne}
\protect\hypertarget{notre-documentation-et-de-nombreux-tutoriaux-sont-disponibles-en-ligne}{}
\begin{center}
$\Longrightarrow$\qquad \url{www.kernel-operations.io}\qquad $\Longleftarrow$
\vspace*{.15cm}

\includegraphics[width=.5\linewidth,frame]{images/geometric_data_analysis.png}

%\vspace*{.15cm}

\url{www.jeanfeydy.com/geometric_data_analysis.pdf}
\end{center}

\appendix
\end{frame}

\hypertarget{annexe}{%
\section{Annexe}\label{annexe}}



\begin{frame}[allowframebreaks]{References}
	\bibliography{biblio}
	\bibliographystyle{alpha}
\end{frame}


\end{document}
