# Approche Tenseur-Train pour l'inférence dans les modèles à blocs stochastiques, application à la caractérisation de la biodiversité

Mohamed Anwar Abouabdallah

► To cite this version:

Mohamed Anwar Abouabdallah. Approche Tenseur-Train pour l'inférence dans les modèles à blocs stochastiques, application à la caractérisation de la biodiversité. Mathématiques générales [math.GM]. Université de Bordeaux, 2023. Français. NNT: 2023BORD0023 . tel-04198646

HAL Id: tel-04198646

https://theses.hal.science/tel-04198646

Submitted on 7 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
Université
de BORDEAUX

INRAE

Inria

THÈSE PRÉSENTÉE

POUR OBTENIR LE GRADE DE

DOCTEUR
DE L'UNIVERSITÉ DE BORDEAUX

École doctorale Mathématiques et Informatique

Mathématiques appliquées et calcul scientifique

Par **Mohamed Anwar Abouabdallah**

Approche Tenseur-Train pour l'inférence dans les modèles à blocs
stochastiques, application à la caractérisation de la biodiversité

Sous la direction de : **Olivier COULAUD**

Co-directrice : **Nathalie PEYRARD**

Soutenue le 02 février 2023

Membres du jury :

<table><tr><td>Mme Sophie DONNET</td><td>Chargée de recherche</td><td>INRAE</td><td>Rapportrice</td></tr><tr><td>M. Jean-René POIRIER</td><td>Maître de conférences</td><td>INP-ENSEEIHT</td><td>Rapporteur</td></tr><tr><td>Mme Agnès BOUCHEZ</td><td>Directrice de recherche</td><td>INRAE</td><td>Examinatrice</td></tr><tr><td>M. Pierre-Henri WUILLEMIN</td><td>Maître de conférences</td><td>Lip6</td><td>Examenateur</td></tr><tr><td>M. Olivier COULAUD</td><td>Directeur de recherche</td><td>INRIA</td><td>Directeur de thèse</td></tr><tr><td>Mme Nathalie PEYRARD</td><td>Directrice de recherche</td><td>INRAE</td><td>Directrice de thèse</td></tr><tr><td>M. Alain FRANC</td><td>Directeur de recherche</td><td>INRAE/INRIA</td><td>Invité</td></tr></table>
# Approche Tenseur-Train pour l'inférence dans les modèles à blocs stochastiques, application à la caractérisation de la biodiversité

## Résumé :

Le modèle à blocs stochastiques (SBM, Stochastic Block Model) est un modèle graphique particulier permettant de classer des individus sur la base de leurs distances deux à deux. Il construit des groupes d'individus partageant les mêmes profils de distance intra et inter groupe. L'estimation des paramètres d'un SBM se fait classiquement par l'algorithme EM (Expectation-Maximisation) qui à chaque itération demande le calcul des marginales unaires et binaires de la loi jointe conditionnelle des groupes des individus. Une manière de faire ce calcul est de passer par une approximation champ moyen du modèle où les marginales binaires sont calculées comme produit des marginales unaires. C'est ce qui est mis en œuvre dans l'algorithme Variational EM. Cet algorithme conduit à des estimateurs de bonne qualité, cependant, on peut espérer améliorer l'inférence des marginales binaires. L'objectif de ces travaux de thèse est de proposer une approche plus précise pour le calcul des marginales binaires faisant appel à l'algèbre tensorielle, par une approche de type Tensor Train (TT), en étendant l'approche de Novikov & al, 2014 sur le calcul de la constante de normalisation d'un modèle graphique.

Dans un premier temps, afin de motiver ce travail méthodologique sur les SBM, nous avons réalisé un clustering de matrices de distances génétiques dans un échantillon de marqueurs génétiques d'une placette expérimentale d'arbres guyanais. Nous avons montré les similitudes et complémentarités entre les classifications obtenues par SBM et par les méthodes plus classiques de Classification Ascendante Hiérarchique. Ce travail a également permis de clarifier le lien entre la taxonomie botanique et la diversité moléculaire présentes dans un échantillon.

Ensuite, pour développer l'approche TT, nous considérons la loi jointe conditionnelle du SBM comme les éléments d'un tenseur. Nous l'approchons par un tenseur de format TT, développé par Oseledets & al., 2011 où chaque élément est obtenu par produit de matrices. Cette écriture mène naturellement à la simplification des calculs de marginalisation par distributivité et séparation des variables, où les marginales sont calculées par des produits matriciels. Cependant, l'approche TT appliquée au SBM débouche sur des calculs matriciels en très grande dimension conduisant à une complexité exponentielle avec le nombre d'individus. Nous avons utilisé le format TT-matrix pour les calculs matriciels, et avons traité les difficultés suivantes apparues lors des calculs : (i) éviter des nombres trop petits par une procédure d'homothétie (ii) contrôler le rang des TT-matrices par un choix des paramètres à l'entrée de l'algorithme du «rounding» proposée par Oseledets sans perdre en précision. (iii) limiter l'ordre des TT-matrice par une agrégation de ces cores.

Ainsi, les contributions de la thèse sont les suivantes : (i) une écriture exacte de la loi jointe conditionnelle d'un modèle SBM comme un tenseur au format TT, sans approximations, en tirant parti du fait que les facteurs sont au plus binaires, cette approche peut s'appliquer plus généralement à tout modèle graphique dont les facteurs sont au plus binaires ; (ii) un algorithme de type programmation dynamique pour le calcul des marginales binaires ; (iii) une procédure opérationnelle qui intègre quelques solutions aux verrous numériques présentés plus haut.

Enfin, nous avons comparé sur une grande variété de modèles SBM la précision du calcul des marginales unaires et binaires, et les temps du calcul obtenus par l'approche TT et par trois autres méthodes : simple énumération, échantillonneurs de Gibbs, approximation par champ moyen. L'approche TT est plus précise que l'approximation par champ moyen et plus rapide que l'échantillonneur de Gibbs sans perdre en précision.

**Mots-clés** : Modèle à bloc stochastique, calcul haute performance, algèbre linéaire.
# Tensor-Train approach for inference in stochastic block models, application to biodiversity characterisation

## Abstract:

The Stochastic Block Model (SBM) is a particular graphical model for clustering individuals on the basis of their pairwise distances. It builds groups such as individuals in a given group have the same pattern of connections to the other groups and to their own group. The estimation of the parameters of a SBM is classically done by the EM (Expectation-Maximisation) algorithm which at each iteration requires the computation of the unary and binary marginals of the conditional joint distribution of the groups of individuals. One way of doing this computation is to use a mean field approximation of the model where the binary marginals are computed as the product of the unary marginals. This is what is implemented in the Variational EM algorithm. This algorithm leads to good quality estimators. However, one can hope to improve the inference of the binary marginals. The objective of this thesis work is to propose a more accurate approach to the computation of binary marginals using tensor algebra, by a Tensor Train (TT) approximation, extending the approach of Novikov & al, 2014 on the computation of the partition function of a graphical model. As a first step, in order to motivate this methodological work on SBMs, we performed a clustering of genetic distance matrices in a sample of genetic markers from a Guianese tree experimental plot. We showed the similarities and complementarities between the classifications obtained by SBM and by the more classical methods of Agglomerative Hierarchical Clustering (AHC). This work allowed us to clarify the link between botanical taxonomy and the molecular diversity present in a sample. Then, to develop the TT approach, we consider the conditional joint law of the SBM as the elements of a tensor. We approximate it by the TT format tensor, developed by Oseledets & al., 2011 where each element is obtained by a product of matrices. This format naturally leads to simplification of marginalization computations by distributivity and separation of variables, where the marginals are computed by matrix products. However, the TT approach applied to SBM leads to very high dimensional matrix computations leading to an exponential complexity according to the number of individuals. We used the TT-matrix format for the matrix computations, and dealt with the following difficulties that arose during the computations: (i) avoiding too small numbers by a homothetic procedure (ii) control the rank of the TT-matrix by a choice of parameters at the input of the rounding algorithm proposed by Oseledets without losing precision (iii) to limit the order of the TT-matrix by an aggregation of these cores.

Thus, the contributions of the thesis are the following: (i) an exact writing of the conditional joint law of a SBM model as a tensor in TT format, without approximations, taking advantage of the fact that the factors are at most binary. This approach can be applied more generally to any graphical model whose factors are at most binary; (ii) a dynamic programming type algorithm for the computation of binary marginals in this context; (iii) an operational procedure that integrates some solutions to the numerical problems presented above.

Finally, we have compared the accuracy of the computation of unary and binary marginals, and the computation times obtained by the TT approach and by three other methods: simple enumeration, Gibbs samplers, mean-field approximation, on a large variety of SBM models. The TT approach is more accurate than the mean field approximation and faster than the Gibbs sampler without losing accuracy.

**Keywords:** Stochastic block model, high performance computing, linear algebra
# Remerciements

Cette thèse est la suite d'un stage de master 2 avec comme titre "Identification d'OTU par clustering par les modèles à blocs stochastiques" encadré par Nathalie Peyrard et Alain Franc.
Ce stage s'est poursuivi par le dépôt d'un projet de thèse Inrae/Inria encadré par Alain Franc, Nathalie Peyrard et Olivier Coulaud qui a été accepté.

Et après un peu plus de trois ans d'aventure, où j'ai travaillé au sein de l'unité Miat de l'INRAE Toulouse (première année) et au sein de l'équipe projet commune (EPC) l'INRAE, Biogeco/INRIA, BSO Pléiade, j'ai pu finaliser ma thèse.

Dans un premier lieu, je tiens à exprimer mes sincères remerciements à mes directeurs de thèse : Olivier Coulaud et Nathalie Peyrard pour leur soutien continu et leur engagement passionné tout au long de mon parcours de recherche. Leurs conseils avisés, leurs discussions stimulantes et leur encouragement constant ont joué un rôle déterminant dans la réalisation de cette thèse. Je souhaite aussi rendre grâce à Alain Franc, qui avait assuré l'encadrement de cette thèse du 1er octobre 2019 au 30 Avril 2021 avant de prendre sa retraite le 1er mai 2021. Je souhaite aussi le remercier pour son implication dans l'équipe d'encadrement jusqu'à la fin de ma thèse conformément à sa mission Inrae/Inria. Sa disponibilité pour discuter de mes idées, résoudre les problèmes et orienter mes recherches a été un atout précieux qui a façonné la qualité de ce travail.

Je tiens à exprimer mes sincères remerciements aux membres éminents de mon comité de thèse pour leur expertise, leur temps précieux et leurs précieuses contributions à l'évaluation de ce travail de recherche.

Je suis honoré(e) d'avoir bénéficié de la supervision, des commentaires et des conseils de Mme Sophie DONNET, M. Jean-René POIRIER, Mme Agnès BOUCHEZ et M. Pierre-Henri WUILLEMIN. Leurs réflexions perspicaces et leurs observations constructives ont grandement enrichi ma recherche, m'aidant à améliorer la pertinence de mon travail.

Je tiens ensuite à remercier mon ancien co-bureau et chef d'équipe Jean-Marc Frigerio à la fois pour les discussions que nous avons eues ainsi que l'aide qu'il m'avait apporté.

Je souhaite également exprimer ma reconnaissance envers mes collègues, qui ont enrichi mon expérience de thèse grâce à leur collaboration et leur camaraderie. Pour cela, je commencerai par remercier par collègues à la fois pour nos discussions à midi, les différentes soirées que nous avons fait ainsi que les parties de tarot et de flag-rugby.

Leur enthousiasme collectif et leur désir de réussir ont créé un environnement stimulant où l'apprentissage et l'échange d'idées étaient encouragés.

Je tiens aussi à remercier l'ensemble des équipes, des départements ainsi que les différents directeurs d'unité, pour leur soutien logistique et administratif. Leur dévouement discret, mais essentiel, a rendu mon parcours de recherche plus fluide et plus agréable.
Je tiens à exprimer ma plus profonde gratitude envers mes parents et ma sœur pour leur soutien inconditionnel tout au long de cette aventure académique. Votre amour, vos encouragements et vos sacrifices ont été les piliers qui m'ont permis d'atteindre ce moment important de ma vie. En somme, ma réussite dans ce projet de thèse est le fruit de l'amour, du soutien et de la patience que ma famille a investie en moi. Votre présence dans ma vie a illuminé chacune de mes journées, et je suis profondément reconnaissant d'avoir une famille aussi exceptionnelle. Que ces lignes de remerciement soient le reflet de ma gratitude éternelle envers vous tous.
Je souhaite également adresser mes remerciements à ma famille élargie et à mes proches amis, dont le soutien indéfectible et les encouragements tout au long de cette aventure ont été une source de réconfort.

Je tiens à adresser mes remerciements les plus chaleureux à ma copine, Élodie Guionet, pour son soutien inébranlable et sa présence aimante qui ont été des éléments essentiels qui ont rendu ce voyage possible.
<figure><img src="image_1.png" /></figure>
# Table des matières

<table><tr><td>Liste des tableaux</td><td>2</td></tr><tr><td>Table des figures</td><td>5</td></tr><tr><td>Liste des algorithmes</td><td>7</td></tr><tr><td>1 Introduction générale</td><td>9</td></tr><tr><td>1.1 Contexte scientifique</td><td>10</td></tr><tr><td>1.2 Intérêt et verrous dans l'inférence des marginales conditionnelles d'un SBM</td><td>11</td></tr><tr><td>1.3 Objectifs de la thèse et approches choisies</td><td>13</td></tr><tr><td>1.4 Thèse pluridisciplinaire</td><td>14</td></tr><tr><td>1.5 Structure du manuscrit</td><td>14</td></tr><tr><td>2 Prérequis sur les modèles à blocs stochastiques</td><td>16</td></tr><tr><td>2.1 Introduction</td><td>17</td></tr><tr><td>2.2 SBM pondérés par les distances</td><td>18</td></tr><tr><td>2.3 Algorithme EM pour l'estimation des paramètres d'un modèle SBM</td><td>20</td></tr><tr><td>2.4 Conclusion</td><td>23</td></tr><tr><td>3 Accord entre les classifications botaniques et moléculaires pour des niveaux taxonomiques élevés</td><td>25</td></tr><tr><td>3.1 Introduction</td><td>26</td></tr><tr><td>3.2 Matériel et méthode</td><td>27</td></tr><tr><td>3.3 Résultats</td><td>29</td></tr><tr><td>3.4 Conclusion</td><td>33</td></tr><tr><td>4 Approche "Tenseur-Train" pour la séparation des variables dans les modèles graphiques</td><td>34</td></tr><tr><td>4.1 Introduction</td><td>35</td></tr><tr><td>4.2 Rappel de quelques bases d'algèbre linéaire</td><td>35</td></tr><tr><td>4.3 Format "Tenseur Train"</td><td>38</td></tr><tr><td>4.4 Format TT-matrices</td><td>43</td></tr><tr><td>4.5 Intuition de l'approche TT appliquée au calcul des marginales dans un modèle graphique</td><td>51</td></tr><tr><td>4.6 Résumé de l'approche TT pour calculer les marginales d'un modèle graphique</td><td>54</td></tr><tr><td>4.7 Conclusion</td><td>57</td></tr><tr><td>5 Approche de type Tenseur Train pour le calcul des marginales binaires dans un modèle à blocs stochastiques</td><td>58</td></tr><tr><td>5.1 Introduction</td><td>59</td></tr><tr><td>5.2 Approche TT appliquée sur un modèle SBM</td><td>59</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>5.3</td>
      <td>Méthode de calcul des marginales via une mutualisation des calculs</td>
      <td>69</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Conclusion</td>
      <td>72</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Évaluation numérique des calculs des marginales d'un modèle SBM par l'approche TT</td>
      <td>74</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Introduction</td>
      <td>76</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Méthodes de calcul des marginales</td>
      <td>77</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Les six structures de réseaux à utiliser pour générer les graphes</td>
      <td>84</td>
    </tr>
    <tr>
      <td>6.4</td>
      <td>Protocole pour l'évaluation de l'approche TT</td>
      <td>87</td>
    </tr>
    <tr>
      <td>6.5</td>
      <td>Comparaison pour un nombre d'individus égale à 9</td>
      <td>89</td>
    </tr>
    <tr>
      <td>6.6</td>
      <td>Comparaison pour un nombre d'individus égal à 18</td>
      <td>98</td>
    </tr>
    <tr>
      <td>6.7</td>
      <td>Discussion</td>
      <td>106</td>
    </tr>
    <tr>
      <td>6.8</td>
      <td>Conclusion</td>
      <td>108</td>
    </tr>
    <tr>
      <td>7</td>
      <td>Vers le passage à l'échelle de l'approche TT</td>
      <td>109</td>
    </tr>
    <tr>
      <td>7.1</td>
      <td>Introduction</td>
      <td>110</td>
    </tr>
    <tr>
      <td>7.2</td>
      <td>Procédure d'homothétie</td>
      <td>112</td>
    </tr>
    <tr>
      <td>7.3</td>
      <td>Changement de paramètres dans la compression par l'algorithme du rounding</td>
      <td>116</td>
    </tr>
    <tr>
      <td>7.4</td>
      <td>Réduction des dimensions de TT-matrices de rang 1 par fusion des cores</td>
      <td>126</td>
    </tr>
    <tr>
      <td>7.5</td>
      <td>Conclusion du chapitre</td>
      <td>138</td>
    </tr>
    <tr>
      <td>8</td>
      <td>Conclusion et perspectives</td>
      <td>140</td>
    </tr>
    <tr>
      <td>8.1</td>
      <td>Rappel des contributions</td>
      <td>141</td>
    </tr>
    <tr>
      <td>8.2</td>
      <td>Perspectives</td>
      <td>141</td>
    </tr>
    <tr>
      <td colspan="2">Appendices</td>
      <td>145</td>
    </tr>
    <tr>
      <td colspan="2">A Complément des résultats sur les méthodes de passage à l'échelle de l'approche TT</td>
      <td>146</td>
    </tr>
    <tr>
      <td colspan="2">B Précision des calculs des marginales et la constante de normalisation</td>
      <td>151</td>
    </tr>
    <tr>
      <td>B.1</td>
      <td>Compression d'une TT-matrice par le rounding</td>
      <td>151</td>
    </tr>
    <tr>
      <td>B.2</td>
      <td>Errore relative dans le calcul des marginales et la constante de normalisation</td>
      <td>152</td>
    </tr>
  </tbody>
</table>
# Table des figures

<table><tbody><tr><td>3.1</td><td>Exemple de taxon choisi pour les réplicats</td><td>28</td></tr><tr><td>3.2</td><td>Accord entre les classifications botaniques et moléculaires selon le niveau taxonomique, axe x : niveaux taxonomiques, axe y : NMI entre la classification basée sur les molécules et la classification botanique. Dans la figure de gauche : distances Smith-Waterman. Dans la figure de droite : distances basées sur les kmers.</td><td>31</td></tr><tr><td>3.3</td><td>Diagramme de Sankey des correspondances entre les partitions issues la CAH avec Ward (colonne de gauche), la classification botanique (colonne centrale) et SBM (colonne de droite) pour les ordres.</td><td>32</td></tr><tr><td>3.4</td><td>Diagramme de Sankey des correspondances entre les partitions issues la classification botanique (colonne de gauche) et la CAH avec SL (colonne de droite) pour les ordres.</td><td>32</td></tr><tr><td>4.1</td><td>Représentation Tensor network d'un produit matriciel</td><td>42</td></tr><tr><td>4.2</td><td>Représentation Tensor network de type Tenseur Train</td><td>42</td></tr><tr><td>4.3</td><td>Tensor networks (figure issue de https://tensornetwork.org/)</td><td>43</td></tr><tr><td>4.4</td><td>Tensor network d'un TT-vecteur X</td><td>44</td></tr><tr><td>4.5</td><td>Tensor network d'une TT-matrice A</td><td>45</td></tr><tr><td>4.6</td><td>Tensor network d'une TT-matrice A (format avec contractions)</td><td>46</td></tr><tr><td>4.7</td><td>Tensor network de la TT-matrice Y résultante du produit de TT-matrices TT-vecteurs (format avec contraction)</td><td>47</td></tr><tr><td>4.8</td><td>Tensor network de la TT-matrice C résultante d'un produit TT-matrices (format avec contraction)</td><td>48</td></tr><tr><td>4.9</td><td>Exemple de modèle graphique</td><td>52</td></tr><tr><td>5.1</td><td>Décomposition en valeurs singulières d'un facteur</td><td>61</td></tr><tr><td>5.2</td><td>Décomposition des calculs des parties centrales de l'expression des marginales binaires</td><td>71</td></tr><tr><td>5.3</td><td>Décomposition des calculs de la partie Gauche (L<sub>i</sub>) en bleu et la partie droite (R<sub>j</sub>) en orange de l'expression des marginales binaires</td><td>72</td></tr><tr><td>6.1</td><td>Compromis précision/temps de calcul pour les quatre méthodes testées pour l'inférence de la loi de Z sachant D</td><td>76</td></tr><tr><td>6.2</td><td>Marginales unaires (structure associative (n=9))</td><td>89</td></tr><tr><td>6.3</td><td>Marginales binaires (structure associative (n=9))</td><td>90</td></tr><tr><td>6.4</td><td>Marginales unaires (structure hiérarchique (n=9))</td><td>91</td></tr><tr><td>6.5</td><td>Marginales binaires (structure hiérarchique (n=9))</td><td>91</td></tr><tr><td>6.6</td><td>Marginales unaires (structure ordonné (n=9))</td><td>92</td></tr><tr><td>6.7</td><td>Marginales binaires (structure ordonné (n=9))</td><td>92</td></tr><tr><td>6.8</td><td>Marginales unaires (structure dissociative (n=9))</td><td>93</td></tr><tr><td>6.9</td><td>Marginales binaires (structure dissociative (n=9))</td><td>94</td></tr><tr><td>6.10</td><td>Marginales unaires (structure Cores periphery (n=9))</td><td>95</td></tr></tbody></table>
<table>
  <tbody>
    <tr>
      <td>6.11 Marginales binaires (structure Cores periphery (n=9))</td>
      <td>95</td>
    </tr>
    <tr>
      <td>6.12 Marginales unaires (structure hiérarchique 2 (n=9))</td>
      <td>96</td>
    </tr>
    <tr>
      <td>6.13 Marginales binaires (structure hiérarchique 2 (n=9))</td>
      <td>96</td>
    </tr>
    <tr>
      <td>6.14 Marginales unaires (structure associative (n=18))</td>
      <td>98</td>
    </tr>
    <tr>
      <td>6.15 Marginales binaires (structure associative (n=18))</td>
      <td>99</td>
    </tr>
    <tr>
      <td>6.16 Marginales unaires (structure hiérarchique (n=18))</td>
      <td>100</td>
    </tr>
    <tr>
      <td>6.17 Marginales binaires (structure hiérarchique (n=18))</td>
      <td>100</td>
    </tr>
    <tr>
      <td>6.18 Marginales unaires (structure ordonné (n=18))</td>
      <td>101</td>
    </tr>
    <tr>
      <td>6.19 Marginales binaires (structure ordonné (n=18))</td>
      <td>101</td>
    </tr>
    <tr>
      <td>6.20 Marginales unaires (structure dissociative (n=18))</td>
      <td>102</td>
    </tr>
    <tr>
      <td>6.21 Marginales binaires (structure dissociative (n=18))</td>
      <td>103</td>
    </tr>
    <tr>
      <td>6.22 Marginales unaires (structure Cores periphery (n=18))</td>
      <td>104</td>
    </tr>
    <tr>
      <td>6.23 Marginales binaires (structure Cores periphery (n=18))</td>
      <td>104</td>
    </tr>
    <tr>
      <td>6.24 Marginales unaires (structure hiérarchique 2 (n=18))</td>
      <td>105</td>
    </tr>
    <tr>
      <td>6.25 Marginales binaires (structure hiérarchique 2 (n=18))</td>
      <td>105</td>
    </tr>
    <tr>
      <td>7.1 Evolution de -log(W) par rapport au nombre de liens selon une structure de distance associative (à droite) et hiérarchique (à gauche).</td>
      <td>110</td>
    </tr>
    <tr>
      <td>7.2 Évolution de rang dans le calcul de W en fonction de l'itération.</td>
      <td>112</td>
    </tr>
    <tr>
      <td>7.3 Standard IEEE 754 pour la double précision.</td>
      <td>113</td>
    </tr>
    <tr>
      <td>7.4 Évolution des rangs des cores dans un calcul sans rounding pour n = 7.</td>
      <td>118</td>
    </tr>
    <tr>
      <td>7.5 Évolution des rangs des cores dans un calcul avec rounding à ϵ = 0.05 pour n = 7.</td>
      <td>118</td>
    </tr>
    <tr>
      <td>7.6 Évolution des rangs des cores dans un calcul avec compression avec l'algorithme du rounding à ϵ = 5 × 10<sup>-2</sup> pour un modèle SBM avec n = 22.</td>
      <td>119</td>
    </tr>
    <tr>
      <td>7.7 Comparaison des marginales unaires calculées avec rounding R<sub>1</sub> et R<sub>3</sub> pour le cas associative.</td>
      <td>125</td>
    </tr>
    <tr>
      <td>7.8 Comparaison des marginales binaires calculées avec rounding R<sub>1</sub> et R<sub>3</sub> pour le cas associative.</td>
      <td>125</td>
    </tr>
    <tr>
      <td>7.9 Comparaison des marginales unaires avec rounding R<sub>1</sub> et R<sub>3</sub> pour le cas dissociative</td>
      <td>125</td>
    </tr>
    <tr>
      <td>7.10 Comparaison des marginales binaires avec rounding R<sub>1</sub> et R<sub>3</sub> pour le cas dissociative</td>
      <td>125</td>
    </tr>
    <tr>
      <td>7.11 Répartition uniforme en 6 paquets des m cores</td>
      <td>129</td>
    </tr>
    <tr>
      <td>7.12 Évolution du nombre de cores par rapport à l'évolution de i l'indice des TT-matrices A<sub>i</sub>[z<sub>i</sub>] pour un modèle SBM avec n = 60 (m = 1770)</td>
      <td>130</td>
    </tr>
    <tr>
      <td>7.13 Répartition des cores dans les paquets de volumes uniformes de cores</td>
      <td>132</td>
    </tr>
    <tr>
      <td>7.14 Volumes des cores des A<sub>i</sub>[z<sub>i</sub>] sans fusion (n = 15 et m = 105)</td>
      <td>134</td>
    </tr>
    <tr>
      <td>7.15 Volumes des cores des B<sub>i</sub> sans fusion (n = 15 et m = 105)</td>
      <td>134</td>
    </tr>
    <tr>
      <td>7.16 Volumes des cores des A<sub>i</sub>[z<sub>i</sub>] pour la fusion par un nombre uniforme de cores (n = 15 et d = 35)</td>
      <td>134</td>
    </tr>
    <tr>
      <td>7.17 Volumes des cores des B<sub>i</sub> pour la fusion par un nombre uniforme de cores (n = 15 et d = 35)</td>
      <td>134</td>
    </tr>
    <tr>
      <td>7.18 Volumes des cores des A<sub>i</sub>[z<sub>i</sub>] avec fusion par un volume uniforme de cores (n = 15 et d = 58)</td>
      <td>134</td>
    </tr>
    <tr>
      <td>7.19 Volumes des cores des B<sub>i</sub> avec fusion par un volume uniforme de cores (n = 15 et d = 58)</td>
      <td>134</td>
    </tr>
    <tr>
      <td>7.20 Évolution des rangs des cores en fonction des itérations de l'algorithme 1 pour les 3 procédures (n = 15, ϵ = 5 × 10<sup>-2</sup> et r<sub>max</sub> = 27)</td>
      <td>136</td>
    </tr>
    <tr>
      <td>7.21 Évolution des rangs des cores en fonction des itérations de l'algorithme 1 pour les 3 procédures (n = 33, ϵ = 5 × 10<sup>-2</sup> et r<sub>max</sub> = 27)</td>
      <td>136</td>
    </tr>
  </tbody>
</table>
# Liste des tableaux

<table>
  <tbody>
    <tr>
      <td>3.1</td>
      <td>Caractéristiques des sous échantillons</td>
      <td>28</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>NMI entre la classification botanique (en familles ou en genres) et les quatre classifications à base moléculaire (ligne) pour deux distances (colonne) et selon que l'on cherche l'accord sur les familles dans les ordres ou sur les genres dans les familles.</td>
      <td>30</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>Statistiques sur la distribution de l'information mutuelle normalisée (NMI) calculée entre chaque classification moléculaire et la classification botanique. Résultats obtenus en utilisant la distance de Smith-Waterman.</td>
      <td>30</td>
    </tr>
    <tr>
      <td>3.4</td>
      <td>Statistiques sur la distribution de l'information mutuelle normalisée (NMI) calculée entre chaque paire de classifications à base moléculaire. Les statistiques sont calculées sur les NMIs obtenues sur 30 réplicats (10 classifications en familles et 20 en genres).</td>
      <td>31</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Tableau présentant les temps de calcul des marginales unaires et binaires, pour n = 9.</td>
      <td>97</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Tableau présentant les temps de calcul des marginales unaires et binaires, pour n = 18.</td>
      <td>106</td>
    </tr>
    <tr>
      <td>7.1</td>
      <td>Constante de normalisation pour différentes valeurs de ε dans le cas d'une structure associative</td>
      <td>117</td>
    </tr>
    <tr>
      <td>7.2</td>
      <td>Temps de calcul de la constante de normalisation pour différentes valeurs de ε dans le cas d'une structure associative</td>
      <td>117</td>
    </tr>
    <tr>
      <td>7.3</td>
      <td>Tableau présentant les rangs des cores des TT-matrices obtenues à chaque itération</td>
      <td>118</td>
    </tr>
    <tr>
      <td>7.4</td>
      <td>Tableau des abréviations pour différentes méthodes de rounding.</td>
      <td>121</td>
    </tr>
    <tr>
      <td>7.5</td>
      <td>Constante de normalisation calculée ainsi que le r<sub>max</sub> observé pour la méthode R<sub>1</sub> dans le cas associative.</td>
      <td>121</td>
    </tr>
    <tr>
      <td>7.6</td>
      <td>Temps de calcul en secondes pour W dans le cas associative.</td>
      <td>122</td>
    </tr>
    <tr>
      <td>7.7</td>
      <td>Constante de normalisation calculée ainsi que le r<sub>max</sub> observé pour la méthode R<sub>1</sub> dans le cas cores periphery.</td>
      <td>122</td>
    </tr>
    <tr>
      <td>7.8</td>
      <td>Temps de calcul en secondes pour W dans le cas cores periphery.</td>
      <td>123</td>
    </tr>
    <tr>
      <td>7.9</td>
      <td>Tableau des abréviations pour différentes méthodes de rounding 2.</td>
      <td>123</td>
    </tr>
    <tr>
      <td>7.10</td>
      <td>Résultats pour les calculs de la constante de normalisation pour de 50 matrices de distances par structure de SBM avec un nombre d'individus n = 20.</td>
      <td>124</td>
    </tr>
    <tr>
      <td>7.11</td>
      <td>Résultats pour les calculs de la constante de normalisation pour de 50 matrices de distances par structure de SBM avec un nombre d'individus n = 30.</td>
      <td>124</td>
    </tr>
    <tr>
      <td>7.12</td>
      <td>Temps de calcul des marginales en secondes pour un calcul avec rounding R<sub>3</sub> comparé à un calcul avec rounding R<sub>1</sub></td>
      <td>125</td>
    </tr>
    <tr>
      <td>7.13</td>
      <td>Tableau présentant les résultats de la constante de normalisation avec et sans fusion</td>
      <td>137</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>A.1</td>
      <td>Tableau des abréviations pour différentes méthodes de rounding.</td>
      <td>146</td>
    </tr>
    <tr>
      <td>A.2</td>
      <td>Temps de calcul en secondes pour la constante de normalisation dans le cas Hiérarchique</td>
      <td>146</td>
    </tr>
    <tr>
      <td>A.3</td>
      <td>Temps de calcul en secondes pour la constante de normalisation dans le cas Hiérarchique</td>
      <td>147</td>
    </tr>
    <tr>
      <td>A.4</td>
      <td>Constante de normalisation calculées ainsi que les r<sub>max trouvé</sub> dans le cas ordonnés</td>
      <td>147</td>
    </tr>
    <tr>
      <td>A.5</td>
      <td>Temps de calcul en secondes pour la constante de normalisation dans le cas ordonnée</td>
      <td>148</td>
    </tr>
    <tr>
      <td>A.6</td>
      <td>Constante de normalisation calculées ainsi que les r<sub>max trouvé</sub> dans le cas dissociative</td>
      <td>148</td>
    </tr>
    <tr>
      <td>A.7</td>
      <td>Temps de calcul en secondes pour la constante de normalisation dans le cas dissociative</td>
      <td>149</td>
    </tr>
    <tr>
      <td>A.8</td>
      <td>Constante de normalisation calculées ainsi que les r<sub>max trouvé</sub> dans le cas hiérarchique 2</td>
      <td>149</td>
    </tr>
    <tr>
      <td>A.9</td>
      <td>Temps de calcul en secondes pour la constante de normalisation dans le cas hiérarchique 2</td>
      <td>150</td>
    </tr>
  </tbody>
</table>
# List of Algorithms

1 Calcul de W 111
# Chapitre 1

# Introduction générale

<table><caption>Table des matières</caption><tr><td>1.1 Contexte scientifique</td><td>10</td></tr><tr><td>1.2 Intérêt et verrous dans l'inférence des marginales conditionnelles d'un SBM</td><td>11</td></tr><tr><td>1.2.1 Intérêt en écologie</td><td>11</td></tr><tr><td>1.2.2 Estimation des SBM</td><td>12</td></tr><tr><td>1.2.3 Coût du calcul des marginales</td><td>12</td></tr><tr><td>1.3 Objectifs de la thèse et approches choisies</td><td>13</td></tr><tr><td>1.3.1 Tenseur de la loi jointe d'un SBM</td><td>13</td></tr><tr><td>1.3.2 Format "Tenseur-Train" de la loi jointe</td><td>13</td></tr><tr><td>1.4 Thèse pluridisciplinaire</td><td>14</td></tr><tr><td>1.5 Structure du manuscrit</td><td>14</td></tr></table>
## 1.1 Contexte scientifique

Les interactions (similarités, relations, amitiés, connaissances, collaborations, flux d'informations et communications ...) entre des entités (individus, objets, organisations, pays ...) peuvent être modélisées par des graphes mathématiques où chaque entité est représentée par un sommet et chaque interaction entre des sommets est représentée par une arête. Ces interactions peuvent être binaires ou pondérées par une distance. Dans ce cas, nous sommes dans le cadre de graphes pondérés (weighted graph [FHP91]), dans lequel un nombre (poids) est attribué à chaque arête. La représentation en graphe a vu le jour en 1736 dans un article publié par Leonhard Euler [BLW86] avant que l'appellation graphe ne soit initialement introduite en 1878 par Joseph Sylvester dans un article publié dans la revue Nature [Syl].

Presque un demi-siècle plus tard, Paul Erdős and Alfréd Rényi ont introduit des méthodes probabilistes en théorie des graphes dans leur article [ER59] paru en 1959. Depuis, avec le développement des outils de calcul et des méthodes statistiques, plusieurs chercheurs se sont intéressés aux graphes et ont développé des algorithmes et des méthodes permettant d'étendre les applications des graphes dans des domaines variés tels que l'écologie [JBO02], la biologie [Les06], l'épidémiologie [BMD20], l'économie [MB09], le traitement d'images [LMZ+20], ou les sciences sociales [TL10] ...

Dans la littérature, nous pouvons trouver plusieurs types de graphes. Nous en citons deux : les graphes orientés où les liens entre les sommets possèdent une orientation et les graphes non orientés où les liens entre les sommets ne possèdent pas d'orientation. Dans cette thèse, nous nous intéressons au cas de graphes non orientés pondérés, c'est à dire où les liens possèdent un poids. Nous présentons ci-dessous un exemple de graphe non orienté pondéré pour représenter les interactions entre cinq individus selon une matrice de distance entre les individus deux à deux.

<figure><img src="image_2.png" /><figcaption>Représentation en graphe</figcaption></figure>

<figure><img src="image_3.png" /></figure>

Dans cette représentation, l'épaisseur des liens est proportionnelle à la distance entre les individus.

La popularité croissante des graphes vient de leur capacité à permettre une visualisation des interactions entre des entités de manière très concise. De plus, ils permettent de trouver la structure communautaire entre des entités, ce que nous appelons partitionnement ou clustering des sommets : il s'agit de regrouper *n* sommets en *Q* classes selon certaines propriétés d'homo-généité à partir des informations qui se trouvent dans une matrice de distances $D \in \mathbb{R}^{n \times n}$ entre individus.

Une façon de faire le partitionnement est de considérer chaque individu comme une variable aléatoire et chaque lien est dépendent de ces variables. Un modèle graphique [Bis06] décrit alors la loi de la distribution jointe entre les variables aléatoires.

C'est le cas des modèles à blocs stochastiques (Stochastic Block Model, SBM), un cas particulier
de modèles graphiques où chaque facteur n'implique que deux individus. Ces modèles ont été initialement introduits dans le domaine des réseaux sociaux en 1983 dans l'article de Holland et al [HLL83]. Ils permettent de modéliser des interactions par paires d'entités. Ces interactions sont représentées par des facteurs binaires. Ils trouvent actuellement des applications dans plusieurs autres domaines comme les sciences sociales [KN11, BDLBH15], la biologie [FYZS18] ou l'écologie [CLBD22].

Ces modèles sont plus flexibles que d'autres approches de partitionnement étant donné qu'ils construisent des classes d'individus partageant les mêmes comportements : les distances entre individus d'une même classe suivent une même loi, et les distances entre paires d'individus appartenant à une classe $q$ et une classe $q'$ suivent une même loi également, fonction de $q$ et $q'$, mais sans à priori sur les distances intra et inter classe, elles peuvent être faibles ou élevées. Pour inférer les classes d'un SBM, il faut estimer ses paramètres : une matrice de distances entre classes et un vecteur de probabilités d'appartenance aux classes.

## 1.2 Intérêt et verrous dans l'inférence des marginales conditionnelles d'un SBM

Dans le cadre des SBM, le calcul des marginales unaires et binaires de la loi jointe des états des sommets du graphe (Z) sachant les distances (D) s'avère utile pour des données en écologie. Nous présentons ici deux exemples. Puis nous expliquons la complexité du calcul des marginales.

### 1.2.1 Intérêt en écologie

En écologie, nous pouvons être amenés à calculer des marginales unaires et binaires dans ces cas de figure.

On suppose qu'on dispose d'une communauté composée de plusieurs individus eux même regroupés en taxons où nous n'avons pas accès aux interactions (prédations, parasitisme, compétition ...) entre les différents taxons.

Une manière de quantifier la possibilité d'interactions est de travailler sur les co-occurences entre taxons. Étant donnés deux taxons i et j, les marginales binaires $p_{ij}(z_i, z_j)$ où $z_i$ (resp. $z_j$) sont la présence / absence du taxon i (resp. j) représentent la loi de co-occurence des deux taxons. L'existence d'interactions peut être une hypothèse en cas d'écart par rapport à l'hypothèse neutre [Hub01] où cette marginale binaire est le produit des deux marginales unaires : $p_{ij}(z_i, z_j) \approx p_i(z_i)p_j(z_j)$. Le modèle neutre stipule que les interactions n'interviennent pas dans la diversité et la distribution des taxons, qui dépendent uniquement des processus démographiques (taux de mortalité, natalité, immigration). Nous calculons donc

$$ \delta_{i,j}(z_i, z_j) = p_{ij}(z_i, z_j) - p_i(z_i)p_j(z_j) $$

S'il n'y a aucune interaction entre les deux taxons, alors

$$ \delta_{i,j} \approx 0 $$

S'il y a des interactions entre les individus, alors, par exemple

- si $\delta_{i,j}(1,1) > 0$, nous pouvons faire l'hypothèse d'une interaction mutualiste

- si $\delta_{i,j}(1,1) < 0$, nous pouvons faire l'hypothèse d'une interaction compétitive

- si $\delta_{i,j}(1,0) > 0$, nous pouvons faire l'hypothèse que i est prédateur ou parasite de j

- ...
Afin de faire une classification non supervisée d'individus en OTUs sur une base moléculaire avec un SBM [APF22] comme nous avons montré dans le chapitre 3. Nous sommes amenés à calculer la probabilité que deux individus soient dans le même bloc sachant la matrice de distance. En effet, l'estimation des paramètres d'un SBM se fait via l'algorithme Expectation-Maximisation (EM [DLR77]) où le calcul de ces marginales constitue l'étape expectation de chaque itération de cet algorithme comme nous l'expliquons dans la section 1.2.2 et le chapitre 2. C'est l'étape la plus coûteuse en temps vu qu'elle nécessite un nombre de sommes exponentiel par rapport au nombre d'individus si le calcul est fait de manière brutale.

## 1.2.2 Estimation des SBM

Une première méthode d'estimation des paramètres d'un SBM a été proposée en 1997 par Snijders et Nowicki dans l'article [Sni97]. Dans leur article, ils l'ont fait pour des SBM avec deux classes et pour des matrices *D* de petites tailles par l'intermédiaire d'une approximation de l'algorithme Expectation-Maximisation (EM) développé par Dempster et Al. [DLR77] en 1977. Dans l'algorithme EM, chaque itération se décompose en deux étapes : une étape de calcul d'espérance (E) et une étape de maximisation (M). Dans l'étape E, il faut calculer des marginales unaires et binaires de la loi jointe conditionnelle des individus comme nous l'expliquons dans le chapitre 2.

Cette étape est très coûteuse car pour un SBM avec *n* individus et *Q* classes, chaque marginale nécessite d'effectuer $Q^n$ sommes, nous devons calculer de l'ordre de $\frac{n^2Q^2}{2}$ marginales binaires. Donc si *n* est grand ce calcul devient impossible.

J.-J. Daudin & Al. ont proposé dans l'article [DPR08] paru en en 2008 une méthode pour faire du EM approché pour l'estimation des SBM, elle consiste à procéder par une approximation champ moyen du modèle qui repose sur l'hypothèse de l'indépendance des classes des sommes sachant la matrice de distances *D* pour approcher la distribution de la loi jointe d'un SBM connaissant les distances par une distribution plus simple à calculer. Ainsi, les marginales binaires sont calculées comme produit des marginales unaires. Cela conduit à l'algorithme Variational EM (VEM). Cet algorithme mène à des estimateurs de bonne qualité.

D'autres méthodes probabilistes existent, comme par exemple l'approche proposée par Snijders et Nowicki dans l'article [NS01a], qui repose sur l'utilisation de l'échantillonneur de Gibbs pour calculer la loi jointe puis de l'utiliser pour calculer les marginales ou l'algorithme Bayes variationnel EM (VBEM [LBA12, LR13]).

## 1.2.3 Coût du calcul des marginales

Dans la section précédente, nous avons expliqué l'intérêt du calcul des marginales. Nous présentons dans cette section le coût d'un calcul de marginale pour un SBM avec *n* individus et *Q* classes. La loi jointe conditionnelle de ce modèle connaissant les distances *D* peut s'exprimer comme une fonction multivariée :

$$ 
\begin{gathered}
\Psi : \llbracket 1, Q \rrbracket^n \xrightarrow{\Psi} \mathbb{R} \\
(z_1, \dots, z_n) \longrightarrow \Psi[z_1, \dots, z_n] = \prod_{i=1,n} \prod_{j=i+1,n} \psi_{i,j}(z_i, z_j)
\end{gathered}
\qquad (1.2.1)
$$

Avec $\psi_{i,j}$ le facteur associé au lien entre *i* et *j*. $z_k$ l'état du sommet *k*.

Les marginales unaires de ce modèle s'expriment :

$$ p_i(z_i) = \sum_{z_1, \dots, z_{i-1}, z_{i+1}, \dots, z_n} \Psi(z_1, z_2, \dots, z_n) \qquad (1.2.2) $$
Les marginales binaires s'expriment :

$$p_i(z_i, z_j) = \sum_{z_1, \dots, z_{i-1}, z_{i+1}, \dots, z_{j-1}, z_{j+1}, \dots, z_n} \Psi(z_1, z_2, \dots, z_n) \quad (1.2.3)$$

Le calcul d'une marginales unaire nécessite $Q^{n-1}$ sommes et celui d'une marginale binaire nécessitent $Q^{n-2}$ sommes. Ces calculs deviennent difficiles dès lors qu'on augmente le nombre de classes ou le nombre d'individus.

## 1.3 Objectifs de la thèse et approches choisies

L'objectif de cette thèse est d'améliorer l'inférence des marginales binaires d'un SBM. Pour cela, nous proposons de considérer la loi jointe conditionnelle du SBM comme les éléments d'un tenseur et de réaliser l'inférence des marginales binaires par l'intermédiaire de calculs algébriques. Nous prenons le choix d'un format algébrique particulier pour exprimer ce tenseur, le format "Tenseur Train" (Tensor Train TT [Ose09, OTZ11, Ose11]) qui permet une séparation des variables $z_i$, donc permet le calcul des marginales. Cependant, si l'écriture algébrique est exacte, les objets (matrices, tenseurs) manipulés sont d'ordres ou de dimensions élevés, et il faudra examiner attentivement les obstacles au passage à l'échelle d'un point de vue numérique.

### 1.3.1 Tenseur de la loi jointe d'un SBM

La loi jointe conditionnelle d'un SBM avec $n$ individus ($m$ liens) et $Q$ classes s'exprime :

$$\Psi[z_1, \dots, z_n] = \prod_{i=1,n} \prod_{j=i+1,n} \psi_{i,j}(z_i, z_j) \quad (1.3.1)$$

Elle peut être vue comme une fonction multivariée comme dans la formule (1.2.1). Si nous considérons les $z_i$ comme des indices sur $[1, Q]$ alors $\psi$ définie un tableau multidimensionnel $\Psi \in (\mathbb{R}^Q)^{\otimes n}$ tel que,

$$\Psi[z_1, \dots, z_n] \in \mathbb{R} \quad (1.3.2)$$

$\Psi$ est un tenseur, un objet mathématique très étudié issu de l'algèbre multilinéaire. Nous mobiliserons donc les concepts algébriques et des opérations tensorielles [Hac19, KB09, Fra22a] pour manipuler la loi jointe.

### 1.3.2 Format "Tenseur-Train" de la loi jointe

Les tenseurs de la loi jointe $\Psi \in (\mathbb{R}^Q)^{\otimes n}$ sont de tailles exponentielles par rapport à $n$, ils sont donc difficilement manipulables. Si nous prenons un exemple de SBM avec un nombre d'individus $n = 40$ et de classes $Q = 3$, nous nous retrouvons avec des tenseurs de tailles $1.22 \times 10^{19}$. Oseledets & al. ont proposé un format "Tenseur Train" dans les articles [Ose09] et [OTZ11]. Il s'agit d'une approche qui permet de les approcher par des tenseurs de rang très faibles. Ce format présente de nombreux avantages. Premièrement, il permet de faire un stockage des tenseurs avec moins d'espace mémoire : $nQr^2$ au lieu de $Q^n$. Il permet de faire des opérations efficaces directement au format "Tenseur Train" (produits, sommes ...) et permet de faire la séparation des variables, ce qui facilite le calcul des marginales.

Il a été utilisé dans de nombreux articles, par exemple dans [ZYO+15] pour simuler de manière hiérarchique certains circuits/systèmes stochastiques difficiles. Dans l'article [NPOV15b], l'auteur utilise ce format pour le stockage des lawyers dans les réseaux de neurones. Dans l'article [DBNW20], les auteurs présentent une représentation pour approcher les fonctions potentiels d'un modèle graphique complexe.
Novikov & al, ont utilisé ce format dans un article [NROV14] pour le calcul de la constante de normalisation et des marginales unaires d'un modèle graphique. L'objectif de cette thèse est d'étendre ce format pour le calcul des marginales binaires d'un SBM.

## 1.4 Thèse pluridisciplinaire

Cette thèse s'inscrit dans un cadre pluridisciplinaire. La première partie combine le barcoding et les statistiques, elle porte sur une application des SBM pour faire une classification non supervisée sur des données moléculaires issues d'arbres de Guyane [CMS+19b]. L'objectif de ce travail est double, dans un premier temps, nous cherchons à savoir si les classifications SBM apportent des informations supplémentaires vis-à-vis des classifications CAH quand nous les comparons à la classification botanique. D'autre part, ce travail a pour objectif de clarifier le lien entre la taxonomie botanique et la diversité moléculaire présentes dans un échantillon.

La deuxième partie de cette thèse combine de l'algèbre tensorielle et les statistiques pour appliquer l'approche présentée par Novikov [NROV14] pour calculer les marginales binaires d'un SBM. Cette approche TT appliquée au SBM débouche sur des calculs matriciels en très grande dimension conduisant à une complexité exponentielle avec le nombre d'individus. Nous avons utilisé le format TT-matrix pour les calculs matriciels ce qui nous a conduit à aborder les difficultés suivantes.

1. apparition de nombres trop petits dans les calculs des marginales ou de la constante de normalisation.

2. évolution exponentielle des rangs des TT-matrices lors des calculs intermédiaires.

3. Augmentation quadratique par rapport au nombre d'individus de l'ordre des TT-matrices.

Afin de valider empiriquement la méthode, nous avons comparé les marginales unaires et binaires obtenues par l'approche TT avec celles obtenues avec la méthode de calcul exacte par énumération qui consiste à construire le tenseur de la loi jointe puis faire le calcul des marginales par sommation, à une approche de type Méthode de Monte-Carlo par chaîne de Markov [And01] (MCMC) et à la méthode variationnelle basée sur l'approximation en champ moyen [DPR08] de la loi de Z sachant D. Nous faisons ces comparaisons sur six structures de distances.

## 1.5 Structure du manuscrit

Ce manuscrit est structuré en sept chapitres.

Dans le chapitre 2 (Prérequis pour les modèles à blocs stochastiques), nous présentons des prérequis sur les SBM, qui seront utilisés tout au long de ce manuscrit. Nous explicitons les différents types de SBM utilisés, leurs hypothèses, leurs paramètres et comment inférer les paramètres de ces modèles.

Dans le chapitre 3 (Accord entre les classifications botaniques et moléculaires pour des niveaux taxonomiques élevés), nous présentons une synthèse de l'article [APF22] (disponible dans l'annexe C) où nous avons appliqué les SBM dans le contexte du barcoding. Nous commençons par une mise en contexte où nous expliquons le choix des SBM, le protocole expérimental et les résultats de comparaison avec la CAH et la botanique.

Le chapitre 4 (Approche "Tenseur-Train" pour la séparation des variables dans les modèles
graphiques) est structuré en deux parties. La première partie est consacrée à l'explication des formats algébriques que nous utilisons tout au long de ce manuscrit. Cette partie se subdivise en trois sections : dans la section 4.2, nous donnons quelques rappels d'algèbre linéaire. Dans la section 4.3 nous présentons le TT-format d'une loi jointe et sa représentation à l'aide de contraction dans le format Tensor Network. Dans la section 4.4, nous présentons les formats TT-matrice et TT-vecteur qui seront utilisés dans les chapitres 5 et 7.

La deuxième partie se subdivise en deux sections. La section 4.5 présente la mise au format TT d'une loi jointe. La section 4.6 présente un résumé de l'approche de Novikov [NROV14] pour le calcul des marginales d'un modèle graphique.

Dans le chapitre 5 (Approche de type Tenseur-Train pour le calcul des marginales binaires dans un modèle à blocs stochastiques), nous commençons par faire une adaptation de l'approche de Novikov aux cas des SBM dans la section 5.2. Nous présentons ensuite dans la section 5.3 un algorithme de type programmation dynamique qui met en oeuvre cette méthode de calcul des marginales binaires. Il repose sur une mutualisation des calculs basée sur une organisation des calculs sur un arbre.

Dans le chapitre 6 (Évaluation numérique des calculs des marginales d'un SBM par l'approche TT), nous présenterons quatre méthodes pour le calcul des marginales dans la section 6.2, les structures de distances simulées dans la section 6.3, le protocole pour le calcul des marginales sur les six structures dans la section 6.4, les résultats numériques dans les sous-sections 6.5 et 6.6 et enfin une discussion dans la section 6.7.

Dans le chapitre 7 (Vers le passage à l'échelle de l'approche TT), nous présentons trois verrous numériques rencontrés lors de la déclinaison de la procédure de Novikov sur les SBM et les solutions apportées. Nous commençons par expliquer la procédure d'homothétie qui permet d'éviter les problèmes des petites valeurs dans la section 7.2. Ensuite, nous présenterons une procédure de changement de paramètres dans la compression par l'algorithme du rounding dans la section 7.3. Enfin, nous expliquons une procédure de réduction des dimensions de TT-matrices de rang 1 par fusion des cores dans la section 7.4. Pour chacune des procédures, nous présentons la motivation, la mise en œuvre et des résultats numériques.

Nous clôturons ce manuscrit par le chapitre 8 qui comporte une conclusion générale dans laquelle nous présentons un résumé des chapitres de ce manuscrit et des contributions de cette thèse. Enfin, nous proposons quelques perspectives de poursuite de cette thèse.

Les chapitres 2 et 4 présentent l'état de l'art respectivement pour l'inférence des SBM et l'approche TT pour le calcul des marginales unaires d'un modèle graphique. Les chapitres 5, 6 et 7 présentent chacun une contribution de ce travail au calcul des marginales binaires d'un SBM.
# Chapitre 2

## Prérequis sur les modèles à blocs stochastiques

### Table des matières

<table><tr><td>2.1</td><td>Introduction</td><td>17</td></tr><tr><td>2.2</td><td>SBM pondérés par les distances</td><td>18</td></tr><tr><td>2.2.1</td><td>Hypothèses, paramètres et loi jointe des SBM</td><td>18</td></tr><tr><td>2.2.1.1</td><td>Hypothèses des modèles</td><td>18</td></tr><tr><td>2.2.1.2</td><td>Loi jointe des SBM</td><td>18</td></tr><tr><td>2.2.1.3</td><td>Deux exemples de paramétrisation d'un SBM pondéré</td><td>19</td></tr><tr><td>2.2.1.4</td><td>Loi jointe des SBM Poisson</td><td>20</td></tr><tr><td>2.3</td><td>Algorithme EM pour l'estimation des paramètres d'un modèle SBM</td><td>20</td></tr><tr><td>2.3.1</td><td>E-step</td><td>21</td></tr><tr><td>2.3.2</td><td>Difficulté de l'algorithme EM et alternative</td><td>23</td></tr><tr><td>2.4</td><td>Conclusion</td><td>23</td></tr></table>
## 2.1 Introduction

Supposons que nous disposons de $n \in \mathbb{N}$ individus et d'un tableau de distances (ou de dissimilarités) $D \in \mathbb{R}^{n \times n}$ entre les individus pris deux à deux. Nous souhaitons regrouper ces individus en $Q$ classes à partir des informations dans cette matrice. Une manière de grouper les individus dans des classes consiste à procéder par une classification non supervisée (clustering) qui consiste à attribuer la même classe à des individus proches les uns des autres et, idéalement, loin des autres classes. Ces classifications, comme la Classification Ascendante Hiérarchique (CAH [Wis69]), reposent sur le principe suivant : "*qui se ressemble s'assemble*". Ainsi, si nous appliquons ces méthodes sur la matrice de distances $D$, nous aurons une partition avec des classes contenant des individus proches.

Une autre manière de regrouper les individus est d'utiliser les modèles à blocs stochastiques [HLL83, NS01b, FH82, LW19, WW87]. Basés sur un modèle statistique, ils construisent des classes d'individus partageant les mêmes comportements. Un SBM est plus flexible qu'une CAH car les individus d'une même classe ne sont pas nécessairement proches les uns des autres.

Pour résumer, les SBM permettent de regrouper les individus en fonction de leur profil de distances et non par leur proximité avec les individus appartenant à la même classe : en d'autres termes, les SBM produisent des classes et non des communautés. Nous présentons deux structures de distances que peuvent modéliser les SBM pour trois classes.

**Associative [KBKK]**

$$ \Lambda_{\text{asso}} = \begin{pmatrix} 2 & 10 & 10 \\ 10 & 3 & 10 \\ 10 & 10 & 4 \end{pmatrix} \quad (2.1.1) $$

**Dissociative [KBKK]**

$$ \Lambda_{\text{diss}} = \begin{pmatrix} 8 & 3 & 3 \\ 3 & 10 & 3 \\ 3 & 3 & 9 \end{pmatrix} \quad (2.1.2) $$

Les coefficients des matrices $\Lambda_{\text{diss}}$ et $\Lambda_{\text{asso}}$ représentent la distance moyenne entre deux individus selon leurs classes.

Nous remarquons que dans la structure de distances (2.1.1), les individus ont une faible distance (forte connexion) avec ceux qui appartiennent à leur classe et une forte distance (faible connexion) avec les individus qui n'appartiennent pas à la même classe. Il s'agit du cas où les méthodes classiques de classification non supervisées donnent de bons résultats.

Dans la structure de distances (2.1.2), les individus ont une forte distance (faible connexion) avec ceux qui appartiennent à leur classe et une faible distance (forte connexion) avec les individus qui n'appartiennent pas à la même classe. Il s'agit du cas où les méthodes classiques de classification non supervisées ne sont pas adaptées pour trouver les classes. Les SBM arrivent à trouver ces deux structures.

Ces modèles sont utilisés dans divers domaines comme la détection de communautés dans les science sociales [KN11, BLZ16, LBA11, BDLBH15], par exemple, l'article [BDLBH15] présente une application de ces modèles pour modéliser les interactions des chercheurs français sur le cancer par l'intermédiaire des connexions directes entre eux ou les connexions via leurs laboratoires de recherche. Ces modèles trouvent également une utilisation dans des domaines comme la biologie, l'article [FYZS18] présente les composants fonctionnels dans les réseaux d'interaction protéine-protéine. Ils peuvent aussi être utilisés en écologie : l'article [CLBD22] présente une utilisation dans la modélisation des réseaux d'interactions écologiques bipartites. Un autre cas d'usage pour les SBM est la génération de topologies Internet et IP synthétiques [KBKK]. Dans la littérature, nous pouvons distinguer deux types de SBM :

* les SBM binaires [DPR08, BDLBH15, KBCG12] (binary SBM) où les tableaux distances représentent la présence/absence de liens entre deux individus. Cette distance est la réalisation d'une loi de Bernoulli;
• les SBM pondérés par les distances [JZS09, MRV10] (weighted SBM).

Nous nous intéressons aux SBM pondérés par les distances. Nous expliquons leurs hypothèses et nous décrivons leurs paramètres, leurs lois jointes, l'estimation des paramètres de ces modèles par l'intermédiaire de l'algorithme Expectation-Maximisation (EM [DLR77]) ainsi que les difficultés de cet algorithme.

## 2.2 SBM pondérés par les distances

### 2.2.1 Hypothèses, paramètres et loi jointe des SBM

Nous disposons d'un nombre $n \in \mathbb{N}$ individus et d'une matrice $D \in \mathbb{R}^{n \times n}$ de distances entre individus deux à deux. Nous souhaitons regrouper les individus en $Q \in [1, n]$ classes à partir des informations contenues dans la matrice $D$.

L'appartenance de chaque individu $i$ à chaque classe $q$ est représentée par une variable latente $Z = (Z_1, ..., Z_n)$ avec $\forall i = 1, ..., n, Z_i \in [1, Q]$. Cela se note également selon une matrice $n \times Q$ avec :

$$ \begin{cases} Z_{i,q} = 1 & \text{Si, } Z_i = q \\ Z_{i,q} = 0 & \text{Sinon} \end{cases} \qquad (2.2.1) $$

$(z_{i,q} = 1 \text{ si l'élément } i \text{ est dans la classe } q \text{ et } 0 \text{ sinon}).$

Par construction,

$$ \forall i, \quad \sum_{q=1}^{Q} z_{i,q} = 1 \qquad (2.2.2) $$

Nous nous intéresserons dans la suite de cette section aux SBM pondérés avec des distances suivant une loi de Poisson et une loi gaussienne.

#### 2.2.1.1 Hypothèses des modèles

Les SBM repose sur deux hypothèses :

• $H_1$ les distances sont indépendantes sachant $Z$ et ne dépendent que des classes des individus. La distance entre deux individus est tirée d'une distribution dépendant des classes de ces deux individus, c'est-à-dire :

$$ D_{i,j} | Z_i = q, Z_j = q' \sim \text{Distribution}(\xi_{q,q'}) \qquad (2.2.3) $$

où la distribution est soit Gaussienne soit Poisson et $\xi_{q,q'}$ est un paramètre. Nous notons $\xi = \{\xi_{q,q'}\}_{q,q'}$.

• $H_2$ les variables latentes $Z_i$ sont indépendantes et identiquement distribuées (iid) selon une distribution $\alpha = (\alpha_1, ..., \alpha_Q)$ avec

$$ \forall q \in [1, ..., Q], \quad \alpha_q = \mathbb{P}_{\alpha}(Z_{i,q} = 1) \qquad (2.2.4) $$

$\alpha$ représente les probabilités d'appartenance aux classes.

#### 2.2.1.2 Loi jointe des SBM

Nous posons $\theta = (\xi, \alpha)$ les paramètres du modèle et nous appliquons le théorème Bayes. La loi jointe de $Z$ et $D$ s'exprime :

$$ \mathbb{P}_{\theta}(Z, D) = \mathbb{P}_{\xi}(D | Z) \mathbb{P}_{\alpha}(Z) \qquad (2.2.5) $$
Nous utilisons la première hypothèse ($\mathbf{H}_1$) pour exprimer la loi jointe comme :

$$ \mathbb{P}_{\theta}(Z, D) = \prod_{i=1}^{n} \prod_{i>j} \mathbb{P}_{\xi}(D_{i,j} | Z) P_{\alpha}(Z) \qquad (2.2.6) $$

$$ \mathbb{P}_{\theta}(Z, D) = \prod_{i=1}^{n} \prod_{i>j} \left( \sum_{q=1}^{Q} \sum_{q'=1}^{Q} \mathbb{P}_{\xi}(D_{i,j} | z_{i,q} = 1, z_{j,q'} = 1) \mathbb{1}(z_{i,q} = 1, z_{j,q'} = 1) \right) \mathbb{P}_{\alpha}(z) \qquad (2.2.7) $$

Nous constatons que $\mathbb{1}(z_{i,q} = 1, z_{j,q'} = 1)$ vaut 1 si les individus $i$ et $j$ appartiennent aux classes $q$ et $q'$. Donc

$$ \mathbb{1}(Z_{i,q} = 1, Z_{j,q'} = 1) = z_{i,q} \times z_{j,q'} \qquad (2.2.8) $$

Nous injectons la formule (2.2.8) dans la formule (2.2.7) et nous obtenons :

$$ \mathbb{P}_{\theta}(Z, D) = \prod_{i=1}^{n} \prod_{i>j} \left( \sum_{q=1}^{Q} \sum_{q'=1}^{Q} \mathbb{P}_{\xi}(D_{i,j} | Z_{i,q} = 1, Z_{j,q'} = 1) z_{i,q} \times z_{j,q'} \right) \mathbb{P}_{\alpha}(z) \qquad (2.2.9) $$

L'hypothèse ($\mathbf{H}_2$) et la formule (2.2.4) nous permet d'écrire $\mathbb{P}_{\alpha}(z)$ de la sorte :

$$ \mathbb{P}_{\alpha}(z) = \prod_{i=1}^{n} \prod_{q=1}^{Q} \mathbb{P}(Z_{i,q} = 1)^{Z_{i,q}} = \prod_{q=1}^{Q} \alpha_{q}^{z_{i,q}} \qquad (2.2.10) $$

La loi jointe s'exprime :

$$ \mathbb{P}_{\theta}(Z, D) = \prod_{i=1}^{n} \prod_{i>j} \left( \sum_{q=1}^{Q} \sum_{q'=1}^{Q} \mathbb{P}_{\xi}(D_{i,j} | Z_{i,q} = 1, Z_{j,q'} = 1) z_{i,q} \times z_{j,q'} \right) \prod_{q=1}^{Q} \alpha_{q}^{z_{i,q}} \qquad (2.2.11) $$

**Facteurs binaires et unaires** : nous notons $\phi_i(z_i)$ les facteurs unaires et $\psi_{i,j}(z_i, z_j)$ les facteurs binaires de la loi jointe :

$$ \phi_i(z_i) = \prod_{q=1}^{Q} \alpha_q^{z_{i,q}} \qquad (2.2.12) $$

$$ \psi_{i,j}(z_i, z_j) = \sum_{q=1}^{Q} \sum_{q'=1}^{Q} \mathbb{P}_{\xi}(D_{i,j} | Z_{i,q} = 1, Z_{j,q'} = 1) z_{i,q} \times z_{j,q'} \qquad (2.2.13) $$

La loi jointe des SBM peut s'exprimer :

$$ \mathbb{P}_{\theta}(Z, D) = \left[ \prod_{i=1}^{n} \prod_{j>i} \psi_{i,j}(z_i, z_j) \right] \left[ \prod_{i=1}^{n} \phi_i(z_i) \right] \qquad (2.2.14) $$

### 2.2.1.3 Deux exemples de paramétrisation d'un SBM pondéré

Les paramètres sont les proportions des individus dans les classes $\alpha$ et le paramètre $\xi$. Ce dernier dépend de la loi par laquelle nous modélisons les distances.

**Matrice de connectivité des SBM pondérés pour des distances suivant une loi gaussienne** : la probabilité conditionnelle de la distance entre deux individus sachant leurs classes suit une loi gaussienne :

$$ D_{i,j} | Z_i = q, Z_j = q' \sim \mathcal{N}(\mu_{q,q'}, \sigma^2) $$

Dans ce cas, $\xi = \{\mu_{q,l}\}$. Nous notons la matrice de connectivité $M \in \mathbb{R}^{Q \times Q}$ et ses coefficients $\mu_{q,q'}$.
Matrice de connectivité des SBM pondérés pour des distances suivant une loi de Poisson :

$$
D_{i,j} | Z_i = q, Z_j = l \sim \text{Poisson}(\lambda_{q,q'}) \qquad (2.2.15)
$$

Dans ce cas, $\xi = \{\lambda_{q,l}\}$. Nous notons la matrice de connectivité $\Lambda \in \mathbb{R}^{Q \times Q}$ et ses coefficients $\lambda_{q,q'}$.

2.2.1.4 Loi jointe des SBM Poisson

Nous appliquons (2.2.11) dans le cas Poisson, car c'est sur ce modèle que nous avons travaillé
dans cette thèse. Nous posons $\theta = (\Lambda, \alpha)$ les paramètres du modèle. Comme la distance entre
deux individus suit une loi de Poisson, alors $\mathbb{P}_{\Lambda}$ s'exprime :

$$
\mathbb{P}_{\Lambda}(D_{i,j} | z_{i,q} = 1, z_{j,q'} = 1) = \frac{\lambda_{q,q'}^{D_{i,j}}}{D_{i,j}!} \exp(-\lambda_{q,q'}) z_{i,q} \times z_{j,q'} \quad (2.2.16)
$$

Enfin, à partir de (2.2.16) et (2.2.10), la loi jointe d'un modèle SBM Poisson s'exprime :

$$
\mathbb{P}_{\theta}(Z, D) = \prod_{i=1}^{n} \prod_{i>j} \left( \sum_{q=1}^{Q} \sum_{q'=1}^{Q} \frac{\lambda_{q,q'}^{D_{i,j}}}{D_{i,j}!} \exp(-\lambda_{q,q'}) z_{i,q} \times z_{j,q'} \right) \prod_{i=1}^{n} \prod_{q=1}^{Q} \alpha_{q}^{z_{i,q}} \quad (2.2.17)
$$

**Facteurs binaires et unaires** Les facteurs s'expriment dans le cadre d'un SBM Poisson :

$$
\phi_i(z_i) = \prod_{q=1}^{Q} \alpha_q^{z_{i,q}} \qquad (2.2.18)
$$

$$
\psi_{i,j}(z_i, z_j) = \sum_{q=1}^{Q} \sum_{q'=1}^{Q} \frac{\lambda_{q,q'}^{D(i,j)}}{D(i,j)!} \exp(-\lambda_{q,q'}) z_{i,q} \times z_{j,q'} \quad (2.2.19)
$$

2.3 Algorithme EM pour l'estimation des paramètres d'un mo-
dèle SBM

L'estimateur du maximum de vraisemblance du modèle $\hat{\theta}_{MV}$ est défini par :

$$
\hat{\theta}_{MV} = \operatorname{argmax}(\mathbb{P}_{\theta}(D)) \qquad (2.3.1)
$$

Pour l'obtenir, il faut calculer la vraisemblance du modèle :

$$
\mathbb{L}(D, \theta) = \mathbb{P}_{\theta}(D) = \sum_{z} \mathbb{P}_{\theta}(D, Z = z) \qquad (2.3.2)
$$

où $Z = (Z_1, \dots, Z_n)$.

Soit dans le cas d'un modèle SBM Poisson :

$$
\mathbb{L}(D, \theta) = \sum_z \prod_{i=1}^{n} \prod_{i>j} \left( \sum_{q=1}^{Q} \sum_{q'=1}^{Q} \frac{\lambda_{q,q'}^{D_{i,j}}}{D_{i,j}!} \exp(-\lambda_{q,q'}) z_{i,q} \times z_{j,q'} \right) \prod_{i=1}^{n} \prod_{q=1}^{Q} \alpha^{z_{i,q}} \quad (2.3.3)
$$

Une manière de trouver $\hat{\theta}_{MV}$ est de trouver les paramètres qui annulent la dérivée de la vraisemblance (2.3.3). Dériver cette quantité n'est pas très difficile, mais trouver toutes les valeurs qui l'annulent est compliqué, en particulier parce qu'il y a $Q^n$ sommes.
Un algorithme classique qui permet de trouver le maximum de la vraisemblance dans le cas des modèles à variables latentes est l’algorithme espérance-maximisation (expectation-maximisation EM [DLR77]) qui procède de manière itérative.

Comme son nom l'indique, chaque itération de cet algorithme se décompose en deux étapes : une étape de calcul d'espérance (E-step) et une étape de maximisation (M-step).

L'algorithme EM consiste à :

1. **Initialisation** : choisir une valeur initiale pour les paramètres : $(\alpha^0, \lambda^0) = \theta^0$.

2. **Alternance des étapes E et M** jusqu'à ce que le critère d'arrêt soit vérifié. Supposons que la valeur courante soit $\theta^t$, à l'itération $t+1$ :

— **Étape E** : Calcul de toutes les marginales binaires conditionnelles (les $\mathbb{P}_{\theta^t}(Z_i, Z_j | D)$ pour tous les couples $Z_i, Z_j$ avec $i < j$) et unaires (les $\mathbb{P}_{\theta^t}(Z_i | D)$ pour tout $i$) de $\mathbb{P}_{\theta^t}(Z | D)$ pour la valeur courante des paramètres.

— **Étape M** : mise à jour des paramètres, i.e. calcul de $\theta^{t+1}$,

$$ \theta^{t+1} = \arg\max_{\theta} \mathcal{Q}(\theta, \theta^t) \qquad (2.3.4) $$

avec,

$$ \mathcal{Q}(\theta, \theta^t) = \sum_{i=1}^{n} \sum_{j>i}^{n} \sum_{z_i=1}^{Q} \sum_{z_j=1}^{Q} \log(\mathbb{P}_{\theta^t}(D_{i,j} | z_i, z_j)) \mathbb{P}_{\theta^t}(z_i, z_j | D) + \sum_{i=1}^{n} \sum_{b=1}^{Q} \sum_{z_{i,b}} \mathbb{P}_{\theta^t}(z_{i,b} | D) z_{i,b} \log(\alpha_b) \qquad (2.3.5) $$

Cela donne les formules de mises à jours suivantes :

$$ \alpha_b^{t+1} = \frac{1}{n} \sum_{i=1}^{n} \mathbb{P}_{\theta^t}(Z_{i,b} = 1 | D) \qquad (2.3.6) $$

$$ \lambda_{b,b'}^{t+1} = \frac{\sum_{i=1}^{n} \sum_{j \neq i} D(i,j) \mathbb{P}_{\theta^t}(Z_i = b, Z_j = b' | D)}{\sum_{i=1}^{n} \sum_{j \neq i} \mathbb{P}_{\theta^t}(Z_i = b, Z_j = b' | D)} \qquad (2.3.7) $$

3. **Un critère d'arrêt possible** est lorsque la somme des valeurs absolues des écarts relatifs entre les paramètres est plus petite que $\epsilon$ :

$$ \sum_{q=1}^{Q} \frac{|\alpha_q^t - \alpha_q^{t+1}|}{\alpha_q^{t+1}} + \sum_{q=1}^{Q} \sum_{q'=q}^{Q} \frac{|\lambda_{q,q'}^t - \lambda_{q,q'}^{t+1}|}{\lambda_{q,q'}^{t+1}} < \epsilon $$

Á la fin de cet algorithme, nous obtenons $\hat{\theta}$ l'estimateur de $\theta$ qui est un maximum local de la vraisemblance.

### 2.3.1 E-step

Nous détaillons la E-step afin de montrer pourquoi dans le cadre des SBM, cela revient à calculer les marginales unaires et binaires conditionnellement à D. Pour cela, nous commençons par définir la quantité suivante $\mathcal{Q}(\theta, \theta^t)$ :

$$ \mathcal{Q}(\theta, \theta^t) = \mathbb{E}_Z[\log \mathbb{P}_{\theta}(D, Z) | \theta^t, D] \qquad (2.3.8) $$

À partir de la propriété de l'espérance $\mathbb{E}(\phi(X)) = \sum_{x_i} \phi(x_i) \mathbb{P}(x_i)$, nous avons :

$$ \mathcal{Q}(\theta, \theta^t) = \sum_z \mathbb{P}_{\theta^t}(z | D) \log(\mathbb{P}_{\theta}(D, z)) \qquad (2.3.9) $$
À partir du théorème de Bayes

$$
\mathbb{Q}(\theta, \theta^t) = \sum_z \mathbb{P}_{\theta^t}(z | D) \log(\mathbb{P}_{\theta}(D|z) \mathbb{P}_{\theta}(z)) \quad (2.3.10)
$$

Ensuite, à partir de la propriété du logarithme

$$
\mathbb{Q}(\theta, \theta^t) = \sum_z \log(\mathbb{P}_{\theta}(D|z))\mathbb{P}_{\theta^t}(z|D) + \sum_z \log(\mathbb{P}_{\theta}(z))\mathbb{P}_{\theta^t}(z|D) \quad (2.3.11)
$$

Nous remarquons que $\mathbb{P}_{\theta}(z)$ ne dépend que de $\alpha$ et que $\mathbb{P}_{\theta}(D|z)$ ne dépend que de $\Lambda$. Nous pouvons donc définir les deux quantités suivantes :

$$
\mathbb{Q}(\Lambda, \theta^t) = \sum_z \log(\mathbb{P}_{\theta}(D|z)) \mathbb{P}_{\theta^t}(z|D) \quad (2.3.12)
$$

$$
\mathbb{Q}(\alpha, \theta^t) = \sum_z \log(\mathbb{P}_{\alpha}(z)) \mathbb{P}_{\theta^t}(z | D) \quad (2.3.13)
$$

Nous détaillons l’expression de chacune :

**Calcul de Q(Λ, θ^t)** : Nous avons

$$
\mathbb{Q}(\Lambda, \theta^t) = \sum_z \mathbb{P}_{\Lambda^t}(z | D) \log \prod_{i=1}^n \prod_{j>i}^n \mathbb{P}_{\Lambda}(D_{i,j} | z_i, z_j) \quad (2.3.14)
$$

$$
= \sum_z \mathbb{P}_{\theta^t}(z | D) \sum_{i=1}^{n} \sum_{j>i}^{n} \log(\mathbb{P}_{\Lambda}(D_{i,j} | z_i, z_j)) \quad (2.3.15)
$$

Nous remarquons que $\sum_z$ peut être développée de cette manière :

$$
\forall i, j = 1, \dots, n, \quad \sum z = \sum z_1 + \sum z_2 + \dots + \sum z_n
$$

Alors,

$$
\mathbb{Q}(\Lambda, \theta^t) = \sum_{i=1}^{n} \sum_{j>i}^{n} \sum_{z_i} \sum_{z_j} \log(\mathbb{P}_{\theta^t}(D_{i,j} | z_i, z_j)) \mathbb{P}_{\theta^t}(z_i, z_j | D) \quad (2.3.16)
$$

La probabilité $\mathbb{P}_{\theta}^t(z_i, z_j | D)$ représente la marginale binaire conditionnellement à $D$. Dans la suite, nous les noterons $p_{ij}(z_i, z_j)$.

**Calcul de Q(α, θ^t)** : Nous avons,

$$
\mathbb{Q}(\alpha, \theta^t) = \sum_z \log \mathbb{P}_{\alpha}(z) \mathbb{P}_{\theta^t}(z | D) \quad (2.3.17)
$$

$$
= \sum_z \mathbb{P}_{\theta^t}(z | D) \log \prod_{i=1}^{n} \prod_{b=1}^{Q} \alpha_b^{z_{i,b}} \quad (2.3.18)
$$

Nous utilisons la propriété du logarithme :

$$
\mathbb{Q}(\alpha, \theta^t) = \sum_{i=1}^{n} \sum_{b=1}^{Q} \sum_{z} \mathbb{P}_{\theta^t}(z | D) \log \alpha_b^{z_{i,b}} \quad (2.3.19)
$$

Ensuite,

$$
\mathbb{Q}(\alpha, \theta^t) = \sum_{i=1}^{n} \sum_{b=1}^{Q} \mathbb{E}_z [ (\log(\alpha_b^{z_{i,b}})) | \theta_t, D ] \quad (2.3.20)
$$
Nous constatons que dans la formule (2.3.20), la quantité $(\log(\alpha_b^{z_{i,b}}))$ ne dépend que de $z_{i,b}$ alors, nous pouvons redévelopper la formule (2.3.20)

$$ \mathbb{Q}(\alpha, \theta^t) = \sum_{i=1}^{n} \sum_{b=1}^{Q} \mathbb{E}_{z_{i,b}} [ (\log(\alpha_b^{z_{i,b}})) | \theta_t, D ] \qquad (2.3.21) $$

Ainsi,

$$ \mathbb{Q}(\alpha, \theta^t) = \sum_{i=1}^{n} \sum_{b=1}^{Q} \sum_{z_{i,b}} \mathbb{P}_{\theta^t}(z_{i,b} | D) z_{i,b} \log(\alpha_b) \qquad (2.3.22) $$

La probabilité $\mathbb{P}_{\theta^t}(z_{i,b} | D)$ représente la marginale unaire. Dans la suite, nous les noterons $p_i(z_i)$.

**Calcul de $\mathbb{Q}(\theta, \theta^t)$ :**

$$ \mathbb{Q}(\theta, \theta^t) = \mathbb{Q}(\lambda, \theta^t) + \mathbb{Q}(\alpha, \theta^t) \qquad (2.3.23) $$

$$ \mathbb{Q}(\theta, \theta^t) = \sum_{i=1}^{n} \sum_{j>i}^{n} \sum_{z_i} \sum_{z_j} \log(\mathbb{P}_{\theta^t}(D_{i,j} | z_i, z_j)) \mathbb{P}_{\theta^t}(z_i, z_j | D) + \sum_{i=1}^{n} \sum_{b=1}^{Q} \sum_{z_{i,b}} \mathbb{P}_{\theta^t}(z_{i,b} | D) z_{i,b} \log(\alpha_b) \qquad (2.3.24) $$

L'étape de maximisation consiste à trouver $\hat{\theta}$ les paramètres qui maximisent (2.3.24).

## 2.3.2 Difficulté de l'algorithmme EM et alternative

L'algorithmme Expectation-Maximisation (EM) est un algorithme très précis pour l'estimation des paramètres d'une SBM. Cependant, l'étape Expectation est très coûteuse : En effet, le calcul d'une marginale unaire nécessite $Q^{n-1}$ sommes et celui d'une marginale binaire nécessite $Q^{n-2}$ sommes.

De plus, il faudrait calculer toutes les marginales unaires $p_i(z_i)$ et binaires $p_{ij}(z_i, z_j)$. Dans un SBM, il y a $m$ paires $(i, j)$ possibles :

$$ m = \sum_{i=1}^{n} \sum_{j=i+1}^{n} 1 = \frac{n(n-1)}{2} \qquad (2.3.25) $$

Comme $m$ est quadratique par rapport à $n$, nous aurons besoin de calculer $O(n^2)$ marginales binaires à chaque itération.

Il existe plusieurs alternatives à l'algorithmme EM, parmi ces alternatives, nous pouvons citer l'algorithme Variationnel EM (VEM [DPR08]) qui est basé sur l'approximation en champ moyen de la loi de Z sachant $D$ : c'est une méthode basée sur une hypothèse d'indépendance où les marginales binaires sont obtenues comme le produit des unaires.

Dans cet algorithme, l'étape E consiste à résoudre une équation du point fixe pour obtenir les marginales unaires, puis à faire le produit des marginales unaires pour obtenir les marginales binaires. Nous détaillons cette étape dans la section 6.2.4.

## 2.4 Conclusion

Dans ce chapitre, nous avons présenté les SBM pondérés par des distances, nous avons expliqué leurs hypothèses, leurs paramètres, leurs lois jointes ainsi que l'estimation des paramètres de ces modèles par l'intermédiaire de l'algorithme Expectation-Maximisation. Nous avons ensuite
présenté la limite de cet algorithme qui vient du fait que nous devons calculer un très grand nombre de marginales durant l'étape E en plus de la difficulté de calculer une marginale.

Dans ce qui va suivre, nous présentons dans le chapitre 3 et l'article [APF22] une comparaison de classifications par SBM et différentes classifications ascendantes hiérarchiques (avec trois critères) sur des tableaux de distances moléculaires entre 1500 arbres de Guyane (voir [CMS+19b] pour les données).

Ensuite, nous résumons dans le chapitre 4 une approche algébrique basée sur la procédure de Novikov [NROV14] qui repose sur des tenseurs pour calculer les marginales par séparation des variables. Nous étendons cette approche aux SBM dans le chapitre 5. Dans le chapitre 6 nous comparons les résultats de cette approche avec les méthodes classiques de calcul des marginales.

Enfin, dans le chapitre 7, nous proposons différentes procédures pour faire le passage à l'échelle de cette approche.
# Chapitre 3

## Accord entre les classifications botaniques et moléculaires pour des niveaux taxonomiques élevés

<table><caption>Table des matières</caption><tr><td>3.1</td><td>Introduction</td><td>26</td></tr><tr><td>3.2</td><td>Matériel et méthode</td><td>27</td></tr><tr><td>3.2.1</td><td>Jeu de données</td><td>27</td></tr><tr><td>3.2.2</td><td>Les deux types d'expériences</td><td>27</td></tr><tr><td>3.2.3</td><td>Protocole</td><td>28</td></tr><tr><td>3.3</td><td>Résultats</td><td>29</td></tr><tr><td>3.3.1</td><td>Résultats des comparaisons des 30 échantillons</td><td>30</td></tr><tr><td>3.3.1.1</td><td>Comparaison entre les classifications moléculaires et botaniques</td><td>30</td></tr><tr><td>3.3.1.2</td><td>Comparaison entre les SBM et les trois classifications CAH</td><td>30</td></tr><tr><td>3.3.2</td><td>Jeu de donnée complet</td><td>31</td></tr><tr><td>3.3.2.1</td><td>Accord entre la classification moléculaire et la classification botanique selon le niveau taxonomique</td><td>31</td></tr><tr><td>3.3.2.2</td><td>Diagramme de Sankey</td><td>32</td></tr><tr><td>3.4</td><td>Conclusion</td><td>33</td></tr></table>
Dans ce chapitre, nous présentons une partie de l'article "Does clustering of dna barcodes agree with botanical classification directly at high taxonomic levels? trees in french guiana as a case study" [APF22] que nous mettons dans les annexes.

**3.1 Introduction**

L'un des problèmes majeurs qui se posent dans le cadre de la classification basée sur la mor-
phologie est que la majeure partie de la diversité reste encore inconnue. Dans l'article [LK15],
l'auteur explique qu'entre 33% et 91% de toute la biodiversité marine est encore inconnue. En
revanche cette classification est connue en botanique, cela nous a conduit à utiliser la botanique
comme référence.

L'identification des unité taxonomique opérationnelle<fnref n="1" /> (Operational Taxonomic Unit, OTU) dans un échantillon environnemental (ensemble de séquences) et l'organisation de la diversité moléculaire en tant que fréquence d'OTUs est une alternative à la classification botanique pour caractériser la biodiversité. Pour faire cette caractérisation, il existe deux familles d'approches :

*   **Apprentissage supervisé** : Une approche classique qui consiste à construire des OTUs et à les mapper sur des bases de données de référence qui contiennent des barcodes de référence, comme fait dans l'outil BLAST [AGM<sup>+</sup>90] (Basic Local Alignment Search Tool). Cette approche est très efficace lorsque les bases de référence existent. Cependant, dès lors que ces bases sont inexistantes où incomplètes, une telle comparaison devient impossible. De plus, la plupart des classifications supervisées sont réalisées à un grain souvent beaucoup plus grossier (ordre/familles) que le niveau du genre/espèce.

*   **Apprentissage non supervisé** : Cela consiste à l'attribution des taxons (aux individus en regroupant les individus dont les séquences sont proches dans une même classe par l'intermédiaire de dendrogrammes ou d'arbres.

Notre objectif dans ce chapitre et l'article [APF22] est d'étudier si la classification moléculaire par apprentissage non supervisé sur des matrices de distance en séquences deux à deux et la classification botanique convergent vers les mêmes partitions des individus, c'est à dire qu'une classe correspond à un taxon. Et, si oui, avec quelle précision.

Les méthodes classiques pour faire un apprentissage non supervisé sur des distances sont les méthodes de Classification Ascendante Hiérarchique CAH qui crée des classes d'individus similaires. Un premier objectif de notre étude serait d'utiliser la CAH avec trois critères d'agréation : Single Linkage, Complete Linkage et Ward [Mur83] [Mü13].

Nous souhaitons aussi savoir si nous pouvons regrouper les séquences ADN avec une approche plus flexible qui consistera à regrouper dans la même classes les séquences qui ont le même profil de distances. Pour cela, nous utiliserons les SBM.

Dans cette étude nous abordons les questions suivantes :

* Est-ce qu'il y a un accord entre la classification moléculaire et la classification botanique au niveau des espèces, genres, des familles et des ordres ?

* Est-ce que les SBM donnent les mêmes résultats que la CAH ? Ou bien apportent-ils une autre information ?

<footnote n="1">1. définition qui consiste à regrouper les individus par proximité génétiquement.</footnote>
## 3.2 Matériel et méthode

### 3.2.1 Jeu de données

Nous avons mené cette étude sur un jeu de données constitué d'arbres de la parcelle expérimentale située dans la "Piste de Saint-Elie" en Guyane rassemblées pour l'étude publiée dans [CMS<sup>+</sup>19a]. Parmi ces données, nous avons sélectionné 1458 arbres. Pour chacun d'entre eux, nous disposons du nom botanique tel que donné par les botanistes de terrain et une séquence du marqueur chloroplastique trnH-psbA.

Ce jeu de données est composé de trois fichiers (voir [FCS<sup>+</sup>21] pour plus de détails) :

* un fichier csv des noms botaniques de chaque arbre pour l'ordre, la famille, le genre et l'espèce;

* un fichier de séquences pour chaque arbre;

* un fichier csv de distances par paires : Il a été construit par l'algorithme de Smith-Waterman pour l'alignement local des séquences [SW81]. Cette méthode est la plus précise des mesures de distances génétiques entre les séquences, mais son calcul nécessite beaucoup de temps;

* un fichier csv des distances par paires basées sur la comparaison des histogrammes des tétramères (même format que les distances de Smith-Waterman) : Il a été construit à partir de la distance entre distributions de kmers. Nous avons choisi des kmer courts avec $k = 4$ (il y a $4^4 = 64$ tétramères différents : GTAG, TAGA, AGAG, GAGC, AGCT, GCTG, CTGT ...);

Nous travaillons donc sur les fichiers de distances qui représentent des matrices $D \in \mathbb{R}^{1458 \times 1458}$, chaque élément est la distance entre séquences.

### 3.2.2 Les deux types d'expériences

Dans notre étude, nous comparons les classifications botaniques et moléculaires sur deux ensembles de données de natures différentes. Nous expliquons ci-dessous la procédure de sélection des échantillons qui est la même que ce soit pour la distance kmer ou Smith-Waterman.

**Comparaison sur le jeu de données complet :** Le but est de faire une classification pour trouver les taxons d'un niveau de donné dans le jeu de donnée. Nous nous intéressons aux quatre niveaux taxonomiques : ordres, familles, genres et espèces afin de voir si l'accord entre les deux classifications dépend du niveau taxonomique et nous faisons notre choix de séquences de cette manière :

1. nous choisissons le niveau taxonomique.

2. nous sélectionnons les taxons de ce niveau pour lesquels nous avons un nombre raisonnable de séquences : nous avons fixé cette taille à 15 pour les ordres, 10 pour les familles et les genres et 5 pour les espèces.

3. nous construisons la sous-matrice de distance $D$ à partir des séquences appartenant aux taxons sélectionnés.

Nous construirons donc quatre matrices de distances, une par niveau taxonomique. Si nous choisissons par exemple les familles, nous aurons une matrice de distance $D \in \mathbb{R}^{1349 \times 1349}$, un nombre de classes $Q = 30$ et pour chaque taxon un nombre minimal d'individus égal à 10. Dans le tableau 3.1, nous présentons pour chaque niveau taxonomique, le nombre de séquences (taille de la matrice) dans les échantillons, le nombre de taxons et les tailles minimales des
<table><caption>TABLE 3.1 – Caractéristiques des sous échantillons</caption><thead><tr><td>Niveau taxonomique</td><td>Nombre de séquences</td><td>Nombre de taxons</td><td>Taille minimale</td></tr></thead><tbody><tr><td>Espèces</td><td>313</td><td>55</td><td>5</td></tr><tr><td>Genres</td><td>845</td><td>36</td><td>10</td></tr><tr><td>Familles</td><td>1349</td><td>30</td><td>10</td></tr><tr><td>Ordres</td><td>1357</td><td>11</td><td>15</td></tr></tbody></table>

taxons qui constituent les échantillons.

**Comparaison sur 30 réplicats :** Le but de ces expériences est de capter la variabilité dans les résultats de comparaison en travaillant sur les réplicats. Pour cela, nous essayons avec les SBM et la CAH de chercher les familles dans les ordres et les genres dans les familles

1. Nous choisissons le niveau taxonomique (ordre ou famille).

2. Nous sélectionnons les taxons du niveau choisi selon deux critères : Un effectif suffisant, c'est-à-dire au moins dix individus et un nombre de descendants (familles dans les ordres et genres dans les familles) qui permettrait de faire une classification (supérieur où égal à deux). Nous présentons un exemple de taxon choisi pour le niveau taxonomique ordre. Dans le jeu de données sont présentes trois familles de l'ordre des Ericales.

<figure><img src="image_4.png" /><figcaption>FIGURE 3.1 – Exemple de taxon choisi pour les réplicats</figcaption></figure>

Dans cet exemple, l'échantillon a un effectif égal à 229 et un nombre de descendants égale à 3. Ainsi, nous construirons une matrice de distances $D \in \mathbb{R}^{229 \times 229}$ et les classifications SBM et CAH seront construite pour un nombre de classes $Q = 3$.

À la fin de cette phase, nous obtenons 30 sous-échantillons : 10 ordres avec des effectifs variant entre 322 et 13 individus puis 20 familles dont les effectifs varient entre 127 et 15 individus.

### 3.2.3 Protocole

Afin de comparer la classification moléculaire et la classification botanique puis les classifications moléculaires entre elles, nous avons adopté le même protocole pour les deux distances (kmers et Smith-Waterman) et pour les deux types d'expériences (sur le jeu de données complet et sur les 30 réplicats). Ce protocole se décline en quatre étapes :
**Étape 1 : Sélection des sous-échantillons** Nous sélectionnons les sous-échantillons comme présenté dans 3.2.2.

**Étape 2 : Construction des partitions** Pour chaque sous-échantillon et chaque matrice de distance, nous construisons des partitions des séquences à la fois avec la CAH selon trois critères d'agrégation, Ward, Complete Linkage (CL) et Single Linkage (SL) (que nous présentons dans le supplementary information (SI) de l'article [APF22]) et avec SBM.
Le nombre de clusters à trouver est *Q* est fourni par la classification botanique des individus du sous-échantillon. À la fin de l'étape 2, nous obtenons cinq partitions différentes pour chaque sous-échantillon.

**Étape 3 : comparaison des partitions** nous comparons les partitions, deux par deux, pour chaque paire possible de classifications (10 paires au total). Nous utilisons un outil visuel pour l'analyse de l'accord entre deux classifications, avec les diagrammes de Sankey<fnref n="2" />.
Nous avons également calculé un indice pour quantifier l'accord entre les classifications, pour cela, nous avons choisi l'information mutuelle normalisée (Normalized Mutual Information NMI [PLP09]) que nous rappelons dans le supplementary information de l'article. Nous avons choisi cet indice car il repose une base solide dans la théorie de l'information, contrairement aux indices basés sur le comptage de paires d'éléments qui peuvent être non symétriques ou non bornés ou même dépendre de *Q* ou *n*, rendant la comparaison difficile. Le NMI est normalisé et varie entre 0 et 1, ce qui facilite l'interprétation et la comparaison des indices. Un NMI de 0 indique l'indépendance entre les deux classifications, tandis qu'un NMI de 1 indique un accord total.

**Étape 4 : analyse des indices** Nous analysons les distributions des indices obtenus pour les dix paires de classifications afin d'étudier les tendances de l'accord. Nous utilisons d'abord des représentations : histogramme, pairplots et boxplots. Ensuite, nous calculons les statistiques sur la distribution des indices (moyenne, médiane ...) que nous présentons dans les tableaux 3.3 et 3.2.

**Mise en oeuvre pratique :** Pour la classification SBM nous avons utilisé le package R `blockmodels` [Leg16] développé par Jean-Benoist & al. Leger qui permet de faire l'inférence des paramètres d'un modèle SBM par l'intermédiaire de l'algorithme VEM basé sur une approximation champs moyen.
Nous avons utilisé le package `fastcluter` [Mü13] disponible en R et Python pour réaliser les classifications ascendantes hiérarchiques.

## 3.3 Résultats

Dans cette section, nous présentons deux ensembles de résultats. Les premiers résultats portent sur les 30 sous-échantillons. Nous présentons les résultats de comparaison entre les classifications moléculaires et la classification botanique. Ensuite, nous présentons des résultats de comparaison entre les trois classifications de type CAH et la classification SBM.
Les seconds résultats sont sur le jeu de donnée complet. Pour cela, nous commençons par présenter un tracé des indices NMI selon le niveau taxonomique puis les diagrammes de Sankey.

<footnote n="2">2. Un diagramme de Sankey est un diagramme dans lequel la largeur d'une flèche est proportionnelle au flux. Par exemple, s'il y a $n_{kk'}$ séquences qui sont dans la classe *k* pour la classification botanique et *k'* pour une classification numérique, il y a un flux d'intensité $n_{kk'}$ entre ces deux clusters.</footnote>
Nous présentons seulement certains résultats, l'ensemble des résultats sont présentés dans l'article [APF22] disponible dans l'annexe C.

### 3.3.1 Résultats des comparaisons des 30 échantillons

#### 3.3.1.1 Comparaison entre les classifications moléculaires et botaniques

Dans le tableau 3.2, nous présentons les médianes des indices NMI calculées sur les paires de partitions. À chaque fois, l'une des partitions et la classification botanique. Dans ce tableau, SW signifie Smith-Waterman et kmers les distances basées sur kmer calculées avec des kmers de longueur $k = 4$.

La première colonne contient les résultats pour les familles sont des valeurs médianes sur dix échantillons, la deuxième colonne contient les résultats pour les genres sont des valeurs médianes sur vingt échantillons et la troisième colonne contient les résultats sur les 30 réplicats.

<table><caption>TABLE 3.2 – NMI entre la classification botanique (en familles ou en genres) et les quatre classifications à base moléculaire (ligne) pour deux distances (colonne) et selon que l'on cherche l'accord sur les familles dans les ordres ou sur les genres dans les familles.</caption><thead><tr><th rowspan="2">Méthode</th><th rowspan="2"></th><th colspan="2">Familles</th><th colspan="2">Genres</th><th colspan="2">30 réplicats</th></tr><tr><th>SW</th><th>kmers</th><th>SW</th><th>kmers</th><th>SW</th><th>kmers</th></tr></thead><tbody><tr><td rowspan="3">CAH</td><td>Ward</td><td>1</td><td>0.61</td><td>0.83</td><td>0.73</td><td>0.87</td><td>0.71</td></tr><tr><td>SL</td><td>0.88</td><td>0.54</td><td>0.75</td><td>0.59</td><td>0.76</td><td>0.58</td></tr><tr><td>CL</td><td>0.85</td><td>0.63</td><td>0.75</td><td>0.71</td><td>0.75</td><td>0.67</td></tr><tr><td>SBM</td><td></td><td>0.57</td><td>0.52</td><td>0.82</td><td>0.66</td><td>0.68</td><td>0.63</td></tr></tbody></table>

Dans le tableau 3.3, nous présentons des statistiquessur les NMIs. Ces statistiques sont calculées sur 30 sous-échantillons (10 ordres et 20 familles).

<table><caption>TABLE 3.3 – Statistiques sur la distribution de l'information mutuelle normalisée (NMI) calculée entre chaque classification moléculaire et la classification botanique. Résultats obtenus en utilisant la distance de Smith-Waterman.</caption><thead><tr><th>Paires des méthodes</th><th>Min.</th><th>1st Qu.</th><th>médiane</th><th>moyenne</th><th>3rd Qu.</th><th>Max.</th></tr></thead><tbody><tr><td>SL vs. botanique</td><td>0.013</td><td>0.27</td><td>0.76</td><td>0.64079</td><td>1.00</td><td>1.00</td></tr><tr><td>Ward vs. botanique</td><td>0.05</td><td>0.40</td><td>0.87</td><td>0.73</td><td>1.00</td><td>1.00</td></tr><tr><td>CL vs. botanique</td><td>0.03</td><td>0.47</td><td>0.75</td><td>0.68</td><td>1.00</td><td>1.00</td></tr><tr><td>SBM vs. botanique</td><td>0.10</td><td>0.33</td><td>0.68</td><td>0.64</td><td>0.98</td><td>1.00</td></tr></tbody></table>

Dans nos résultats, nous observons une tendance commune aux 30 échantillons : quelle que soit le niveau taxonomique ou la distance, les partitions issues de la CAH avec le critère d'agrégation de Ward sont plus proches de la classification botanique. Les autres méthodes se classent différemment en fonction de ces deux variables, mais donnent des partitions assez proches de celles obtenues par la classification botanique. L'accord est meilleur lorsque la classification est faite sur des distances calculées par SW.

#### 3.3.1.2 Comparaison entre les SBM et les trois classifications CAH

Dans le tableau 3.4, nous présentons les statistiques des indices NMI calculés sur les pairs des partitions obtenues par les différentes classifications moléculaires. Dans nos résultats nous montrons une grande proximité entre les six paires de méthodes à part entre SBM et SL. Nous révélons que les SBM donnent des partitions proches de Ward même dans le pire des cas, le NMI minimal est de 0.31.
<table><caption>TABLE 3.4 – Statistiques sur la distribution de l'information mutuelle normalisée (NMI) calculée entre chaque paire de classifications à base moléculaire. Les statistiques sont calculées sur les NMIs obtenues sur 30 réplicats (10 classifications en familles et 20 en genres).</caption><thead><tr><th>Paires des méthodes</th><th>Min.</th><th>1st Qu.</th><th>Median</th><th>Mean</th><th>3rd Qu.</th><th>Max.</th></tr></thead><tbody><tr><td>SBM Vs SL</td><td>0.039</td><td>0.30</td><td>0.65</td><td>0.59</td><td>0.98</td><td>1.00</td></tr><tr><td>SBM vs. Ward</td><td>0.31</td><td>0.52</td><td>0.74</td><td>0.74</td><td>1.00</td><td>1.00</td></tr><tr><td>SBM vs. CL</td><td>0.11</td><td>0.47</td><td>0.65</td><td>0.67</td><td>0.91</td><td>1.00</td></tr><tr><td>SL vs. Ward</td><td>0.04</td><td>0.34</td><td>0.78</td><td>0.69</td><td>1.00</td><td>1.00</td></tr><tr><td>SL vs. CL</td><td>0.05</td><td>0.56</td><td>0.84</td><td>0.74</td><td>1.00</td><td>1.00</td></tr><tr><td>Ward vs CL</td><td>0.05</td><td>0.70</td><td>0.86</td><td>0.80</td><td>1.00</td><td>1.00</td></tr></tbody></table>

### 3.3.2 Jeu de donnée complet

#### 3.3.2.1 Accord entre la classification moléculaire et la classification botanique selon le niveau taxonomique

Dans la figure 3.2, nous présentons l'accord entre les classifications botaniques et moléculaires selon le niveau taxonomique. Chaque courbe correspond à une classification à base moléculaire. Les NMI sont calculées pour les classifications des échantillons associés aux différents niveaux taxonomique.

<figure><img src="image_5.png" /><figcaption>FIGURE 3.2 – Accord entre les classifications botaniques et moléculaires selon le niveau taxonomique, axe *x* : niveaux taxonomiques, axe *y* : NMI entre la classification basée sur les molécules et la classification botanique. Dans la figure de gauche : distances Smith-Waterman. Dans la figure de droite : distances basées sur les kmers.</figcaption></figure>

Nous montrons dans nos résultats que dans un premier temps les NMI dépendent du niveau taxonomique niveau taxonomique choisi : plus nous nous approchons des espèces plus les indices sont élevés. Nous révélons ensuite que les trois classifications via SBM et CAH avec Ward et CL sont très proches entre elles et que les quatre méthodes donnent des partitions similaires au niveau des espèces.
### 3.3.2.2 Diagramme de Sankey

Afin de comprendre les différences de NMI observés sur la figure 3.2, nous regardons en détail les partitions associés à ces classifications. Pour cela, nous utilisons les diagrammes de Sankey que nous traçons dans les graphiques 3.3 et 3.4, un flux entre deux classes signifie qu'elles partagent des séquences en commun et la largeur d'un flux entre deux classes est proportionnelle au nombre de séquences appartenant à ces deux classes.

<figure><img src="image_6.png" /><figcaption>FIGURE 3.3 – Diagramme de Sankey des correspondances entre les partitions issues la CAH avec Ward (colonne de gauche), la classification botanique (colonne centrale) et SBM (colonne de droite) pour les ordres.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>FIGURE 3.4 – Diagramme de Sankey des correspondances entre les partitions issues la classification botanique (colonne de gauche) et la CAH avec SL (colonne de droite) pour les ordres.</figcaption></figure>
Sur la figure 3.3, un ordre est divisé en plusieurs classes dans les classifications Ward ou SBM ou, au contraire, une classe Ward ou SBM est composé d'individus issus de plusieurs classes botaniques. Ce dernier cas est plus problématique lors de l'interprétation des classifications basées sur les distances moléculaires.

Sur la figure 3.4, nous observons que l'une des classes SL est formée par presque tous les ordres présents dans l'ensemble de données. Cela explique le faible NMI pour SL pour une classification au niveau des ordres.

## 3.4 Conclusion

Dans ce chapitre, nous avons comparé les méthodes de classifications moléculaires entre elles et avec la classification botanique pour des niveaux taxonomiques élevés et nous avons montré qu'il y a un bon accord entre les deux. De plus, nous avons montré que la classification SBM permet de détecter, par le biais de la distribution estimée des distances intra-classe, des situations où les classifications moléculaires peuvent être en désaccord avec la classification botanique parce que la matrice de distance n'est pas clairement structurée en communautés. Un autre avantage des SBM comparés à la CAH est qu'en plus de nous fournir les partitions, les SBM produisent la matrice de distances inter et intra classes Λ. Cette matrice fournis une information très importante comme présenté dans l'introduction.
# Chapitre 4

## Approche "Tenseur-Train" pour la séparation des variables dans les modèles graphiques

<table><caption>Table des matières</caption><tr><td>4.1 Introduction</td><td>35</td></tr><tr><td>4.2 Rappel de quelques bases d'algèbre linéaire</td><td>35</td></tr><tr><td>4.3 Format "Tenseur Train"</td><td>38</td></tr><tr><td>4.3.1 La loi jointe d'un modèle SBM comme un tenseur</td><td>38</td></tr><tr><td>4.3.2 Contraction des tenseurs</td><td>38</td></tr><tr><td>4.3.3 Formalisme "Tenseur-Train"</td><td>39</td></tr><tr><td>4.3.3.1 Expression d'un tenseur sous format "Tenseur-Train"</td><td>39</td></tr><tr><td>4.3.3.2 Avantage de ce format</td><td>40</td></tr><tr><td>4.3.4 Tensor Network</td><td>41</td></tr><tr><td>4.4 Format TT-matrices</td><td>43</td></tr><tr><td>4.4.1 Notions de multiplexage et de démultiplexage</td><td>43</td></tr><tr><td>4.4.2 Définitions de base</td><td>44</td></tr><tr><td>4.4.3 Opérations élémentaires</td><td>46</td></tr><tr><td>4.4.3.1 Sommes de TT-matrices</td><td>46</td></tr><tr><td>4.4.3.2 Produits de TT-matrices TT-vecteurs</td><td>47</td></tr><tr><td>4.4.3.3 Produits de TT-matrices</td><td>48</td></tr><tr><td>4.4.4 Compression des TT-matrices : utilisation du rounding</td><td>49</td></tr><tr><td>4.5 Intuition de l'approche TT appliquée au calcul des marginales dans un modèle graphiques</td><td>51</td></tr><tr><td>4.5.1 Modèles graphiques</td><td>51</td></tr><tr><td>4.5.2 Intuition de l'approche TT</td><td>51</td></tr><tr><td>4.6 Résumé de l'approche TT pour calculer les marginales d'un modèle graphique</td><td>54</td></tr><tr><td>4.7 Conclusion</td><td>57</td></tr></table>
## 4.1 Introduction

Dans ce chapitre, nous rappelons quelques notions d'algèbre [Str19, HJ12, Ste93] puis nous décrivons l'approche de présentée par Novikov [NROV14] pour l'approximation d'une loi jointe d'un modèle graphique par un tenseur au format "Tenseur-Train". L'avantage de cette approche est de conduire naturellement à la séparation des variables. Le tenseur est simplement le tableau multivarié des probabilités indexées par les différents états de la loi jointe du modèle graphique. Nous montrerons dans le chapitre 5 que si les liens sont au plus binaires dans le modèle graphique, comme dans un modèle SBM, alors le tenseur peut être écrit exactement dans un format "Tenseur-Train". Nous utiliserons cette approche pour le calcul des marginales d'un modèle à blocs stochastiques.

## 4.2 Rappel de quelques bases d'algèbre linéaire

Durant cette section, nous rappelons quelques définitions d'algèbre linéaire que nous utiliserons dans les sections 4.4.4 et 7.3.

**Norme de Frobenius.** Soit $A \in \mathbb{R}^{p \times q}$ une matrice de coefficients $(a_{i,j})_{i,j \in [1,p] \times [1,q]}$. La norme de Frobenius est définie comme :

$$ \|A\|_F = \sqrt{\sum_{i=1}^{p} \sum_{j=1}^{q} a_{i,j}^2} \qquad (4.2.1) $$

Pour alléger les notations, nous notons la norme de Frobenius $\|\cdot\|_F$.

**Produit de Kronecker.** Soient deux matrices $A \in \mathbb{R}^{n,m}$ et $B \in \mathbb{R}^{p,q}$. Le produit de Kronecker noté $\otimes_k$ entre $A$ et $B$ est une matrice de taille $np \times mq$ dont les coordonnées sont :

$$ A \otimes_k B = \begin{pmatrix} a_{11}B & a_{12}B & \dots & \dots & a_{1m}B \\ a_{21}B & \ddots & \dots & \dots & \vdots \\ \vdots & \dots & \ddots & \dots & \vdots \\ \vdots & \dots & a_{ij}B & \dots & \vdots \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n1}B & \vdots & \vdots & \vdots & a_{nm}B \end{pmatrix} \qquad (4.2.2) $$

Le produit de Kronecker $\otimes_k$ vérifie les deux propriétés suivantes :

* $\mathbf{P}_1$: "Mixed-product property" : Si $A, B, C$ et $D$ sont quatre matrices de tailles telles que les produits $AC$ et $BD$ ont un sens, alors :

$$ AC \otimes_k BD = (A \otimes_k B)(C \otimes_k D) \qquad (4.2.3) $$

* $\mathbf{P}_2$: Si $x, y \in \mathbb{R}$ alors $x \otimes_k y \in \mathbb{R}$ et :

$$ x \otimes_k y = xy \qquad (4.2.4) $$

qui seront utilisées dans ce chapitre.
**Matrices orthogonales** : Soit $n \in \mathbb{N}$ et $A \in \mathbb{R}^{n \times n}$

A est une matrice orthogonale si :

$$A^T A = AA^T = \mathbb{I}_n \qquad (4.2.5)$$

On distingue une matrice orthogonale qui est carrée d'une matrice rectangulaire dont les colonnes sont orthogonales.

**Factorisation QR** [Gen98] Soit une matrice $A \in \mathbb{R}^{p \times q}$. La décomposition QR de cette matrice est l'écriture de $A$ sous-forme d'un produit d'une matrices $Q$ dont les colonnes sont orthogonales et d'une matrice $R$ triangulaire supérieure selon :

$$A = QR \qquad (4.2.6)$$

**Remarque** : Dans le cas où $A$ est une "Fat Matrix" [Bay13], c'est-à-dire son nombre de lignes $p$ est inférieur à son nombre de colonnes $q$, nous définissons une décomposition $LQ$ où : $Q$ est une matrice dont les colonnes sont orthogonales et $L$ est une matrice triangulaire inférieure. Cette décomposition sera utilisée durant la phase d'orthogonalisation des cores dans l'algorithme du rounding présenté dans la section 4.4.4.

**Décomposition en valeur singulière** (singular value decomposition en anglais, d'où l'abbréviation SVD) [WRR03, Str19, HJ12].

Soient $p, q \in \mathbb{N}$ avec $p \ge q$, $A \in \mathbb{R}^{p \times q}$, alors, il existe $U \in \mathbb{R}^{p \times q}$ et $V \in \mathbb{R}^{q \times q}$ dont les colonnes sont orthogonales et $\Sigma \in \mathbb{R}^{q \times q}$ une matrice diagonale telle que :

$$A = U\Sigma V^T \qquad (4.2.7)$$

la matrice $\Sigma$ s'exprime comme $\Sigma = \text{diag}(\sigma_1, \sigma_2, ..., \sigma_q)$. $\sigma_i$ ses éléments vérifient : $\sigma_1 \ge \sigma_2 \ge ... \ge \sigma_p \ge 0$

Cette décomposition est exacte comme expliquée dans l'article [MIR60].

Soit,

$$A = U\Sigma V^T$$

Nous rappelons que

$$\|A\|^2 = \text{Tr}(A^T A)$$

d'où

$$\|A\|^2 = \text{Tr}(V\Sigma U^T U\Sigma V^T)$$

Comme les matrices $U$ et $V$ sont orthogonales, $U^T U = I_p$, et nous avons

$$\text{Tr}(V\Sigma U^T U\Sigma V^T) = \text{Tr}(V\Sigma^2 V^T) = \text{Tr}(\Sigma^2)$$

car la trace est invariante par rotation. Nous en déduisons,

$$\|A\|^2 = \text{Tr}(\Sigma^2) = \sum_{k=1}^{q} \sigma_k^2$$
**Approximation de rang faible :** Soit $r < q$. Nous pouvons séparer la somme $\sum_{k=1}^{q} \sigma_k^2$ en deux parties :

$$ \|A\|^2 = \sum_{k=1}^{r} \sigma_k^2 + \sum_{k=r+1}^{q} \sigma_k^2 \qquad (4.2.8) $$

Si nous retenons les $r$ premières valeurs singulières, nous pouvons définir $\Sigma_r$ comme, $\Sigma_r = \text{diag}(\sigma_1, \sigma_2, ..., \sigma_r)$. Puis nous retenons les $r$ premières colonnes $(u_1, ..., u_r)$ (resp. $(v_1, ..., v_r)$) de $U$ (resp. de $V$) pour définir les matrices $U_r \in \mathbb{R}^{p \times r}$ (resp. $V_r \in \mathbb{R}^{q \times r}$). Ensuite, nous définissons :

$$ A_r = U_r \Sigma_r V_r^T \qquad (4.2.9) $$

La norme de $A_r$ s'exprime :

$$ \|A_r\|^2 = \sum_{k=1}^{r} \sigma_k^2 \qquad (4.2.10) $$

Le théorème d'Eckart-Young [EY36] stipule que la matrice $A_r$ est la matrice de rang $r$ qui minimise $\|A - A_r\|$ selon la norme de Frobenius. C'est-à-dire :

$$ \|A - A_r\| = \min_{B \in \mathbb{R}^{p \times q}, \text{rang}(B) = r} (\|A - B\|) \qquad (4.2.11) $$

Il est possible de faire une approximation de la matrice $A$ par la meilleure approximation de rang faible ("best low rank approximation" (BLRA) [HJ12,Ste93]) de deux manières :

**Approximation de rang faible à rang prescrit :** Cette approche consiste à fixer le rang $r$ et calculer $A_r$. La précision de $A_r$ est donnée par le théorème d'Eckart-Young. Nous injectons l'expression de la norme de $A_r$ (4.2.10) dans la formule (4.2.8) et nous obtenons :

$$ \|A\|^2 = \sum_{k=1}^{r} \sigma_k^2 + \sum_{k=r+1}^{q} \sigma_k^2 = \|A_r\|^2 + \sum_{k=r+1}^{q} \sigma_k^2 \qquad (4.2.12) $$

Ainsi, l'erreur de l'approximation à rang prescrit $r$ s'exprime :

$$ \|E\|^2 = \|A\|^2 - \|A_r\|^2 = \sum_{k=r+1}^{q} \sigma_k^2 \qquad (4.2.13) $$

**Approximation à précision prescrite $\epsilon$ :** Cette approche consiste à trouver le rang $r$ minimal tel que si $A_r$ est la meilleure approximation de $A$ de rang $r$, alors l'erreur vérifie : $\|E\| \le \epsilon \|A\|$. Soit,

$$ \sum_{k=r+1}^{q} \sigma_k^2 \le \epsilon \left( \sum_{k=1}^{q} \sigma_k^2 \right) \qquad (4.2.14) $$

Ensuite, nous calculons :

$$ A_r = U_r \Sigma_r V_r^T \qquad (4.2.15) $$

Lorsque nous faisons un SVD à précision prescrite, nous ne pouvons pas contrôler le rang de la matrice $A_r$. Quand nous faisons une SVD avec un rang prescrit, nous ne pouvons pas contrôler l'erreur d'approximation.
## 4.3 Format "Tenseur Train"

Un objet d'étude dans cette thèse est la loi jointe d'un modèle SBM avec $n$ individus écrite sous forme d'un tenseur d'ordre $n$, pour utiliser des résultats de calcul tensoriel et proposer de nouveaux algorithmes pour le calcul des marginales. Pour cela, nous montrerons que la loi jointe d'un modèle SBM conditionnellement aux distances peut s'écrire exactement comme un tenseur en format Tenseur-Train (TT). Aussi, nous rappelons dans cette section quelques résultats connus sur ce format. Nous adoptons les notations présentées par Oseledets dans les articles [OD12] et [OTZ11].

### 4.3.1 La loi jointe d'un modèle SBM comme un tenseur

Les tenseurs sont définis algébriquement comme des formes multilinéaires [Fra22b]. Ils peuvent être aussi considérés de façon moins abstraite comme des tableaux multidimensionnels, c'est-à-dire des généralisations des scalaires, des vecteurs et des matrices. Un tel tableau est l'écriture d'un tenseur dans une base choisie pour chacun des espaces vectoriels sur lesquels la forme multilinéaire opère.

Un tenseur d'ordre $n \in \mathbb{N}$ est un tableau $n$ dimensionnel tel que chaque coefficient s'exprime avec $n$ indices. Nous pouvons ainsi écrire la loi jointe $\Psi[i_1, \dots, i_n] \in \mathbb{R}$, d'un SBM comme un tenseur $\Psi$, où $\Psi[i_1, \dots, i_n] \in \mathbb{R}$, est l'élément d'indice $(i_1, \dots, i_n)$ de $\Psi$ (indice $n$-dimensionnel). Dans ce cas :

* $n$ est appelé l'ordre du tenseur $\Psi$.

* les rangs des indices $(1, \dots, n)$ sont les modes du tenseur

* $i_k$ est l'indice pour le mode $k$

* si $i_k \in [1, q_k]$, alors $q_k$ est la dimension du tenseur pour l'ordre $k$. La dimension multilinéaire du tenseur est $(q_1, \dots, q_n)$.

Dans notre cas, pour un tenseur associé à un SBM :

* toutes les dimensions $q_k$ sont égales à $Q$.

* le nombre d'individus, $n$, est l'ordre du tenseur,

* chaque individu définit un mode.

* $Q$, le nombre de classes, est la dimension de chaque mode

Notons que, souvent, dans la littérature, le mot dimension peut désigner l'ordre. Nous utiliserons le mot ordre dans ce document.

### 4.3.2 Contraction des tenseurs

Dans cette section, nous rappelons sur quelques exemples la définition d'une contraction entre deux tenseurs. Un exemple de contraction est le produit matriciel, où chaque matrice est lue comme un tenseur d'ordre 2 : si $C = AB$, alors

$$ \left. \begin{array}{l} A = [a_{ij}]_{i,j} \\ B = [b_{jk}]_{j,k} \end{array} \right\} \implies C = [c_{ik}]_{i,k} \quad \text{avec} \quad c_{ik} = \sum_j a_{ij} b_{jk} \qquad (4.3.1) $$

Chaque matrice a deux modes, repérés par leurs indices : $i, j$ pour $A$, $j, k$ pour $B$. Il y a un mode commun : $j$. La contraction est simplement la somme des produits des coefficients de $A$ et $B$ selon le mode commun $k$. Cela se généralise à plus de deux modes, avec sur un exemple qui reste simple : soit $A = [a_{ijk}]_{i,j,k}$ un tenseur d'ordre 3 d'éléments $a_{ijk}$ et $B = [b_{k\ell}]_{k,\ell}$ un tenseur
d'ordre 2 d'éléments $b_{k\ell}$. Les tenseurs **A** et **B** partagent un indice commun $k$ et l'opération de contraction est la somme des produits des coefficients sur cet indice. Elle est notée $\bullet_k$. Aussi

$$ \mathbf{A} = [a_{ijk}]_{i,j,k}, \quad \mathbf{B} = [b_{k\ell}]_{k,\ell} \quad \Rightarrow \quad \mathbf{C} = \mathbf{A} \bullet_k \mathbf{B} = \left[ \sum_k a_{ijk} b_{k\ell} \right]_{i,j,\ell} \qquad (4.3.2) $$

Le tenseur contracté **C** résultant est d'ordre 3. Cette formule se généralise aisément pour la contraction de deux tenseurs d'ordre quelconques sur leurs modes communs (il peut y en avoir plus d'un, comme par exemple dans

$$ c_{ijmpq} = \sum_{k,\ell} a_{ijk\ell m} b_{pk\ell q} $$

)

### 4.3.3 Formalisme "Tenseur-Train"

Ce format a été proposé par l'équipe d'Oseledets & al. dans les articles [Ose09, OTZ11, OD12].

#### 4.3.3.1 Expression d'un tenseur sous format "Tenseur-Train"

Une manière efficace de représenter $\Psi$ est de l'écrire avec le formalisme tenseur train lorsque c'est possible. Lorsque ce n'est pas possible, nous recherchons la meilleure approximation de $\Psi$ par un tenseur $\tilde{\Psi}$ en format Tenseur-Train avec un rang donné. Dans le format TT, chaque coefficient de $\Psi$ est décomposé comme un produit de matrices. Nous le montrons d'abord sur un petit exemple pour un tenseur d'ordre 4. Ses quatre modes sont représentés par les indices $i, j, k, \ell$. Chaque coefficient sera un produit de quatre matrices, une par mode, selon

$$ \Psi[i,j,k,\ell] = G_1(i) \cdot G_2(j) \cdot G_3(k) \cdot G_4(\ell) \quad \text{avec} \quad \left\{ \begin{array}{l} G_1(i) \in \mathbb{R}^{1 \times r_1} \\ G_2(j) \in \mathbb{R}^{r_1 \times r_2} \\ G_3(k) \in \mathbb{R}^{r_2 \times r_3} \\ G_4(\ell) \in \mathbb{R}^{r_3 \times 1} \end{array} \right. \qquad (4.3.3) $$

Les entiers $r_1, r_2, r_3$ sont appelés les TT-rangs du format TT. Le plus grand des trois est appelé le TT-rang maximal de $\Psi$ au format TT [NROV14].

On peut noter que, par exemple, $G_1(i)$ pour $\Psi[i, j, k, \ell]$ ne dépend ni de $j$, ni de $k$, ni de $\ell$. Par exemple, nous avons également

$$ \Psi[i, j', k', \ell'] = G_1(i) \cdot G_2(j') \cdot G_3(k') \cdot G_4(\ell') \qquad (4.3.4) $$

Les premier et dernier éléments sont des vecteurs et les autres sont des matrices. Dans cette écriture, chaque coefficient du tenseur $\Psi$ est obtenu par des produits matriciels où un vecteur horizontal ($G_1(i)$) est une matrice à une ligne et un vecteur vertical ($G_4(\ell)$) est une matrice à une colonne. L'expression de chaque coefficient comme un produit de matrices peut s'illustrer selon

$$ \Psi[i, j, k, \ell] = \underset{\sim}{\Box} \cdot \underset{\sim}{\Box} \cdot | $$

Il est possible de regrouper par exemple l'ensemble des matrices $(G_2(j))_j$ comme tranches d'un tenseur d'ordre 3 noté $G_2$, avec trois modes de dimensions respectives $r_1, Q, r_2$. Donc
$G_2 \in \mathbb{R}^{r_1 \times Q \times r_2}$. Cela peut se faire pour chaque mode, pour donner :

$$
\left\{
\begin{array}{l}
\mathbf{G}_1 \in \mathbb{R}^{1 \times Q \times r_1} \\
\mathbf{G}_2 \in \mathbb{R}^{r_1 \times Q \times r_2} \\
\mathbf{G}_3 \in \mathbb{R}^{r_2 \times Q \times r_3} \\
\mathbf{G}_4 \in \mathbb{R}^{r_3 \times Q \times 1}
\end{array}
\right.
\qquad (4.3.5)
$$

les tenseurs **G**<sub>1</sub>, **G**<sub>2</sub>, **G**<sub>3</sub>, **G**<sub>4</sub> sont applés les "cores" du format TT du tenseur **Ψ**.

À partir du format tensoriel des cores présenté dans la formule (4.4.7), nous pouvons écrire la
formule (4.3.3) en remplaçant les produits matriciels par des contractions de tenseurs **G**<sub>*k*</sub> :

$$
\mathbf{\Psi} = \mathbf{G}_1 \bullet_{\alpha} \mathbf{G}_2 \bullet_{\beta} \mathbf{G}_3 \bullet_{\gamma} \mathbf{G}_4 \quad (4.3.6)
$$

soit, en développant

$$
\mathbf{\Psi}[i,j,k,l] = \sum_{\alpha=1}^{r_1} \sum_{\beta=1}^{r_2} \sum_{\gamma=1}^{r_3} \mathbf{G}_1(i, \alpha) \mathbf{G}_2(\alpha, j, \beta) \mathbf{G}_3(\beta, k, \gamma) \mathbf{G}_4(\gamma, l) \quad (4.3.7)
$$

Les formules (4.3.3) et (4.3.7) se généralisent pour des tenseurs $\mathbf{\Psi}$ d'ordres supérieurs à 4.

4.3.3.2 Avantage de ce format

Le format TT présente plusieurs avantages. Nous les détaillons dans cette section.

**Séparation des variables :** Dans $\mathbf{\Psi}[i,j,k,l]$, $G_1(i)$ ne dépend que de $i$, $G_2(j)$ ne dépend que de $j$ ... Cela conduit naturellement à la séparation des variables. En effet : la constante de normalisation s'écrit, sur cet exemple :

$$
\begin{align*}
W &= \sum_{i,j,k,l} \mathbf{\Psi}[i,j,k,l] \\
&= \sum_{i,j,k,l} G_1(i) \cdot G_2(j) \cdot G_3(k) \cdot G_4(\ell) \tag{4.3.8} \\
&= \left(\sum_i G_1(i)\right) \left(\sum_j G_2(j)\right) \left(\sum_k G_3(k)\right) \left(\sum_\ell G_4(\ell)\right)
\end{align*}
$$

car la multiplication est distributive vis à vis de l'addition dans l'anneau des matrices. C'est
l'écriture de W en séparant les variables i,j,k,ℓ. Nous utiliserons cette séparation des variables
plus généralement dans la suite pour le calcul de différentes marginales.

**Réduction du stockage :** Stocker le tenseur $\mathbf{\Psi}$ nécessite un stockage de $Q^n$ éléments. Si $n$ est grand, le stockage de ce tenseur devient impossible. L'utilisation du format tenseur train avec le produit matriciel, par exemple ici pour $n = 4$, permet de stocker les éléments sous forme de $2Q$ matrices $r \times r$ (en supposant que $r_1 = r_2 = r_3 = r$), $Q$ matrices $G_2(j)$ pour $1 \le j \le Q$ et $Q$ matrices $G_3(k)$ pour $1 \le k \le Q$ d'une part, et de $2Q$ vecteurs de $\mathbb{R}^r$ d'autres parts. Au total, cela donne $2Qr + 2Qr^2 = 2Qr(r+1)$ éléments soit en $O(2Qr^2)$, au lieu de $Q^4$. Le coût du stockage en format TT pour un tenseur d'ordre quelconque $n$ se généralise facilement en $\approx O(nQr^2)$. Grâce à ce format, nous passons d'un stockage exponentiel en $n$ des tenseurs à un stockage linéaire en $n$.
**Opérations élémentaires dans le format TT :** Les opérations tensorielles élémentaires (sommes, produits, multiplication par un scalaire ...) peuvent être exprimées de manière exacte dans le format TT sans avoir à explicitier les coefficients du tenseur comme présenté dans [Ose11]. Nous présentons dans la section 4.4 une adaptation de ce format vers des objets appelés TT-matrices et TT-vecteurs, et les opérations plus complexes de produit matrice × matrice ou matrice × vecteur dans ce format.

Par exemple, si $n = 3$, nous donnons deux tenseurs en format TT selon

$$ egin{cases} 
\mathbf{A}[i,j,k] = G_1^\mathbf{A}(i) \cdot G_2^\mathbf{A}(j) \cdot G_3^\mathbf{A}(k) \\ 
\mathbf{B}[i,j,k] = G_1^\mathbf{B}(i) \cdot G_2^\mathbf{B}(j) \cdot G_3^\mathbf{B}(k) 
\end{cases} 
\qquad (4.3.9) $$

Alors, leur somme $\mathbf{D} = \mathbf{A} + \mathbf{B}$ s'exprime en format TT selon

$$ \mathbf{D}[i,j,k] = G_1^\mathbf{D}(i) \cdot G_2^\mathbf{D}(j) \cdot G_3^\mathbf{D}(k) \qquad (4.3.10) $$

avec

$$ egin{cases} 
G_1^\mathbf{D}(i) = (G_1^\mathbf{A}(i) \quad G_1^\mathbf{B}(i)) \\ 
G_2^\mathbf{D}(j) = \begin{pmatrix} G_2^\mathbf{A}(j) & 0 \\ 0 & G_2^\mathbf{B}(j) \end{pmatrix} \\ 
G_3^\mathbf{D}(k) = \begin{pmatrix} G_3^\mathbf{A}(k) \\ G_3^\mathbf{B}(k) \end{pmatrix} 
\end{cases} 
\qquad (4.3.11) $$

comme nous pouvons le vérifier en effectuant les produits matriciels :

$$ D[i,j,k] = G_1^\mathbf{A}(i) \cdot G_2^\mathbf{A}(j) \cdot G_3^\mathbf{A}(k) + G_1^\mathbf{B}(i) \cdot G_2^\mathbf{B}(j) \cdot G_3^\mathbf{B}(k) \qquad (4.3.12) $$

Cette formule peut se généraliser pour des tenseurs d'ordre $n \in \mathbb{N}$ : Si $\mathbf{A}$ et $\mathbf{B}$ sont des tenseurs d'ordre $n$ dont les cores respectifs sont $G_k^\mathbf{A}(i_k)$ et $G_k^\mathbf{B}(i_k)$, alors $\mathbf{D} = \mathbf{A} + \mathbf{B}$ s'exprime en format TT selon :

$$ \mathbf{D}[i_1, i_2, \dots, i_d] = G_1^\mathbf{D}(i_1) \cdot G_2^\mathbf{D}(i_2) \cdot \dots \cdot G_n^\mathbf{D}(i_n) \qquad (4.3.13) $$

avec

$$ egin{cases} 
k = 1 & \mathbf{G}_1^\mathbf{D}(i_1) = (\mathbf{G}_1^\mathbf{A}(i_1) \quad \mathbf{G}_1^\mathbf{B}(i_1)) \\ 
\forall k \in [2, n-1] & \mathbf{G}_k^\mathbf{D}(i_k) = \begin{pmatrix} \mathbf{G}_k^\mathbf{A}(i_k) & 0 \\ 0 & \mathbf{G}_k^\mathbf{B}(i_k) \end{pmatrix} \\ 
k = n & \mathbf{G}_n^\mathbf{D}(i_n) = \begin{pmatrix} \mathbf{G}_n^\mathbf{A}(i_n) \\ \mathbf{G}_n^\mathbf{B}(i_n) \end{pmatrix} 
\end{cases} 
\qquad (4.3.14) $$

Nous expliquerons dans la section 4.4.3.2 comment faire les produits matriciels dans ce format.

### 4.3.4 Tensor Network

Les "Tensor network" sont une famille de contractions sur un ensemble de tenseurs qui partagent certains modes. Il s'agit de factorisations de très grands tenseurs en réseau de plus petits tenseurs.

Prenons l'exemple d'un produit matriciel. Soit $A \in \mathbb{R}^{n \times p}$ et $B \in \mathbb{R}^{p \times m}$. Le produit matriciel $C = A \cdot B$ s'exprime $c_{ik} = \sum_{j=1}^{p} a_{ij} b_{jk}$. Ce produit peut être représenté en tenseur Network selon
<figure><img src="image_8.png" /><figcaption>FIGURE 4.1 – Représentation Tensor network d'un produit matriciel</figcaption></figure>

le schéma 4.1 : Les nœuds représentent les matrices A et B, le lien entre eux est l'indice commun j sur lequel nous faisons la somme. Les indices i (resp. k) propre à la matrice A (resp. B) sont les liens vers l'extérieur.

Nous pouvons exprimer ce produit matriciel comme une contraction selon l'indice j :

$$C = A \bullet_j B \qquad (4.3.15)$$

Nous nous intéressons à la représentation Tensor Network d'un "Tenseur Train" [LC15] où nous représentons le tenseur $\Psi$ exprimé dans la formule (4.3.3) dans le schéma 4.2 :

<figure><img src="image_9.png" /><figcaption>FIGURE 4.2 – Représentation Tensor network de type Tenseur Train</figcaption></figure>

Dans ce schéma, les nœuds représentent les cores $(G_k)_{k \in [1,n]}$ dans l'expression au format TT de $\Psi$. Les liens entre deux nœuds $(\alpha_k)_{k \in [1,n-1]}$ représentent les indices partagés entre deux cores. Enfin, les liens vers le haut représentent les indices libres des cores.

Cette représentation visualise l'écriture algébrique

$$\Psi = G_1 \bullet_{\alpha_1} G_2 \bullet_{\alpha_2} \cdots \bullet_{\alpha_{n-1}} G_n \qquad (4.3.16)$$

Cette visualisation sera utilisée dans le cadre des TT-vecteurs (dans le paragraphe 4.4.2) et des TT-matrices (dans le paragraphe 4.4.2).

En plus des Tenseur Trains, il existe dans la littérature plusieurs autres types de Tensor Network, représentés sous forme de graphes. Parmi les tenseurs networks connus, nous pouvons citer : Matrix Product State / Tenseur Train, Tree Tensor Network / Hierarchical Tucker, PEPS, MERA ... Dans le schéma 4.3, nous montrons la représentation de ces différents types de Tensor Network :
<figure><img src="image_10.png" /><figcaption>FIGURE 4.3 – Tensor networks (figure issue de https://tensornetwork.org/)</figcaption></figure>

Les articles [Cic14], [Orú14] et [Orú19], détaillent les différents formalismes Tensor Network. À noter que les Tenseur Train sont des cas particuliers de Three tensor Network.

## 4.4 Format TT-matrices

Dans cette section, nous précisons la notion de multiplexage, donnons ensuite les définitions des objets TT-matrices/TT-vecteurs, présentons les opérations dans ce format, et enfin nous expliquerons comment faire la compression des TT-matrices grâce à l'algorithme du TT-rounding.

### 4.4.1 Notions de multiplexage et de démultiplexage

Soient $n_1, \dots, n_d \in \mathbb{N}$ et $n \in \mathbb{N}$ avec $n = \prod_{k=1}^d n_k$. Nous notons :

$$I_N = \llbracket 1, n \rrbracket, \quad \forall k, I_k = \llbracket 1, n_k \rrbracket \qquad (4.4.1)$$

Le multiplexage est défini comme une fonction bijective $\rho$ qui fait correspondre un indice unique $i$ à un multi indice $\mathbf{i}$ :

$$\mathbf{i} = (i_1, \dots, i_d) \in I_1 \times \dots \times I_d \xrightarrow{\rho} i \in I_N \qquad (4.4.2)$$

On note

$$\left\{ \begin{array}{ll} \mathbf{i} = (i_1, \dots, i_d) & \in I_1 \times \dots \times I_d \quad \text{Forme démultiplexée} \\ i = \rho(\mathbf{i}) = i_d + \sum_{k=1}^{d-1} n_k (i_k - 1) & \in I_N \quad \text{Forme multiplexée} \end{array} \right. \qquad (4.4.3)$$

La formule (4.4.3) peut se démontrer par une récurrence.

Nous utiliserons ces notions pour faire la correspondance entre les matrices et les tenseurs dans les différentes définitions qui vont suivre. L'indice unique $i$ correspondra aux indices des lignes et colonnes d'une TT-matrice, et chaque indice $i_k$ du multi-indice $\mathbf{i}$ à un mode d'un tenseur qui lui est équivalent.
### 4.4.2 Définitions de base

Dans cette section, nous expliquons comment faire le passage des matrices et vecteurs au format TT grâce au multiplexage. Nous considérons $n, m \in \mathbb{N}$ et $d \in \mathbb{N}$.

**TT-vecteurs** Soient $r_0, \dots, r_d \in \mathbb{N}^d$, $n_1, \dots, n_d \in \mathbb{N}^d$, et $n = \prod_{k=1}^d n_k$. Un vecteur $X \in \mathbb{R}^n$ est exprimé dans le format TT-vecteur [NPOV15a] sachant

$$i = \rho(i_1, \dots, i_d) \tag{4.4.4}$$

si

$$\forall i \in [1, n], \quad X[i] = \mathbf{X}[i_1, \dots, i_d] = G_1(i_1) \cdot G_2(i_2) \dots G_d(i_d) \\ \text{avec } \left\{ \begin{array}{ll} k=1 & \Rightarrow G_1(i_1) \in \mathbb{R}^{r_0 \times r_1} \\ 1 < k < d & \Rightarrow G_k(i_k) \in \mathbb{R}^{r_{k-1} \times r_k} \\ k=d & \Rightarrow G_d(i_d) \in \mathbb{R}^{r_d \times r_d} \end{array} \right. \tag{4.4.5}$$

avec $r_0 = r_d = 1$. Dans cette formule, la correspondance entre un vecteur $X$ et un tenseur $\mathbf{X}$ est faite par démultiplexage : $X$ (TT-vecteur) est la forme multiplexée et $\mathbf{X}$ (tenseur) est la forme démultiplexée. Par extension, il est convenu d'appeler également le tenseur $\mathbf{X}$ TT-vecteur. Nous appelons $(r_0, \dots, r_d)$ le rang multilinéaire ou TT-rang du TT-vecteur $\mathbf{X}$ et $r^{\mathbf{X}} = \max(r_1, \dots, r_{d-1})$ son TT-rang maximal.

Ce TT-vecteur est un tensor network selon la figure 4.4 :

<figure><img src="image_11.png" /><figcaption>FIGURE 4.4 – Tensor network d'un TT-vecteur $\mathbf{X}$</figcaption></figure>

Les figures 4.4 et 4.2 sont similaires. Elles représentent la représentation d'un TT-vecteur sous format démultiplexé. En développant les contractions des cores, nous obtenons :

$$\mathbf{x}[i_1, \dots, i_d] = \sum_{\alpha_1=1}^{r_1} \dots \sum_{\alpha_{d-1}=1}^{r_{d-1}} \mathbf{G}_1(i_1, \alpha_1) \mathbf{G}_2(\alpha_1, i_2, \alpha_2) \dots \mathbf{G}_d(\alpha_{d-1}, i_d) \tag{4.4.6}$$

Comme pour les tenseurs en format TT, nous pouvons regrouper les $(G_k(i_k))_{i_k \in [1, n_k]}$ dans un tenseur

$$\left\{ \begin{array}{ll} k=1 & \Rightarrow \mathbf{G}_1 \in \mathbb{R}^{1 \times n_1 \times r_1} \\ 1 < k < d & \Rightarrow \mathbf{G}_k \in \mathbb{R}^{r_{k-1} \times n_k \times r_k} \\ k=d & \Rightarrow \mathbf{G}_d \in \mathbb{R}^{r_d \times n_d \times 1} \end{array} \right. \tag{4.4.7}$$

Ce format permet de stocker un vecteur de taille $\prod_{k=0}^d n_k$ en $\sum_{k=1}^d n_k r_k r_{k-1}$. Si $n_0 = \dots = n_d = Q$ et $r_1 = \dots = r_{d-1} = r$, le stockage sera en $O((d-2)Qr^2)$ au lieu de $Q^d$.

**TT-matrices** Soient $r_0, \dots, r_d \in \mathbb{N}^d$, $n_0, \dots, n_d \in \mathbb{N}^d$ et $m_0, \dots, m_d \in \mathbb{N}^d$ avec $n = \prod_{k=1}^d n_k$ et $m = \prod_{k=1}^d m_k$. Une matrice $A \in \mathbb{R}^{n \times m}$ est exprimée dans un format TT-matrice [OTZ11], sachant

$$i = \rho(i_1, \dots, i_d), \quad j = \rho(j_1, \dots, j_d) \tag{4.4.8}$$
si

$$
\forall i \in [1,n], j \in [1,m], \quad A[i,j] = \mathbf{A}[i_1, \dots, i_d; j_1, \dots, j_d] = \mathbf{G}_1(i_1, j_1) \mathbf{G}_2(i_2, j_2) \dots \mathbf{G}_d(i_d, j_d)
$$

$$
\text{avec } \left\{
\begin{array}{lll}
k=1 & \Rightarrow & \mathbf{G}_1(i_1,j_1) \in \mathbb{R}^{r_0 \times r_1} \\
1<k<d & \Rightarrow & \mathbf{G}_k(i_k,j_k) \in \mathbb{R}^{r_{k-1} \times r_k} \\
k=d & \Rightarrow & \mathbf{G}_d(i_d,j_d) \in \mathbb{R}^{r_{d-1} \times r_d}
\end{array}
\right.
\quad (4.4.9)
$$

Avec $r_d = r_0 = 1$. Dans cette formule, la correspondance entre une matrice $A$ et un tenseur $\mathbf{A}$ avec double indexage est faite par démultiplexage : $A$ est la forme multiplexée et $\mathbf{A}$ est la forme démultiplexée. Par extension, nous appelons le tenseur $\mathbf{A}$ TT-matrice. Nous pouvons passer de $\mathbf{A}$ (resp. $\mathbf{X}$) à $A$ (resp. $X$) par un reformatage (reshape).

Oseledets a prouvé l'existence de cette décomposition pour toute matrice de taille $2^d \times 2^d$ dans l'article [Ose10]. Il est possible de généraliser cette écriture pour des matrices quelconques, cependant cela conduira à des cores de rangs fort. En effet, si nous considérons que les cores $\mathbf{G}_k(i_k, j_k)$ sont tous de rang $r$, ce sont des matrices de tailles $r \times r$. Nous aurons $n$ matrices de tailles $r \times r$ et comme chaque indice $i_k$ où $j_k$ varie entre 1 et $Q$ alors nous aurons $nr^2Q^2$ termes. Donc,

$Q^{2n} = nr^2 Q^2$

Alors : $r = \frac{Q^{n-1}}{\sqrt{n}}$.

**TT-rang maximal d'une TT-matrice** Nous appelons TT-rang maximal d'une TT-matrice **A**
le maximum des TT-rangs de ses cores, c'est-à-dire :

$$
\max \text{TT-rang}(\mathbf{A}) = \max(r_1, \dots, r_{d-1}) \qquad (4.4.10)
$$

Par soucis de simplification, nous noterons par la suite $r^A$ le maximum des TT-rang d'une
TT-matrice $\mathbf{A}$.

Nous pouvons réécrire une TT-matrice sous forme de contractions de tenseurs :

$$
\mathbf{A} = \mathbf{G}_1(i_1, j_1) \bullet_{\alpha_1} \mathbf{G}_2(i_2, j_2) \bullet_{\alpha_2} \dots \bullet_{\alpha_{d-2}} \mathbf{G}_{d-1}(i_{d-1}, j_{d-1}) \bullet_{\alpha_{d-1}} \mathbf{G}_d(i_d, j_d) \quad (4.4.11)
$$

Cette TT-matrice est un tensor network selon la figure 4.5 :

<figure><img src="image_12.png" /><figcaption>FIGURE 4.5 – Tensor network d’une TT-matrice A</figcaption></figure>

Comme pour les TT-vecteurs, nous pouvons exprimer une TT-matrice sous forme de contraction
de tenseurs $\mathbf{G}_k$ équivalents aux matrices $\mathbf{G}_k(i_k, j_k)$ pour $i_k \in [1, n_k]$, $j_k \in [1, m_k]$ :

$$
\mathbf{A} = \mathbf{G}_1 \bullet_{\alpha_1} \mathbf{G}_2 \bullet_{\alpha_2} \dots \bullet_{\alpha_{d-2}} \mathbf{G}_{d-1} \bullet_{\alpha_{d-1}} \mathbf{G}_d \quad (4.4.12)
$$

soit, en développant

$$
\mathbf{A}[i_1, \dots, i_d; j_1, \dots, j_d] = \sum_{\alpha_1=1}^{r_1} \dots \sum_{\alpha_{d-1}=1}^{r_{d-1}} \mathbf{G}_1(i_1, j_1, \alpha_1) \mathbf{G}_2(\alpha_1, i_2, j_2, \alpha_2) \dots \mathbf{G}_d(\alpha_{d-1}, i_d, j_d) \tag{4.4.13}
$$

Ainsi, **A** peut être représentée selon un tenseur network

$\forall [1, n]$, $\mathbf{G}_k \in \mathbb{R}^{r_{k-1} \times n_k \times m_k \times r_k}$ sont appelés "cores" de la TT-matrice $\mathbf{A}$. $\mathbf{A}$ peut s'exprimer sous forme d'un tenseur d'ordre $n$.
<figure><img src="image_13.png" /><figcaption>FIGURE 4.6 – Tensor network d'une TT-matrice A (format avec contractions)</figcaption></figure>

**Remarque importante :** ces deux formalismes, un coefficient comme produit de matrices (schéma 4.5) ou une contraction de tenseurs d'ordre 4 le long d'un Tensor Network (schéma 4.6) sont équivalents. Nous poursuivons le développement avec des contractions de tenseurs d'ordre 4 étant donné que c'est le formalisme à la base de plusieurs Toolbox pour l'approche TT comme la TT-toolbox [Ose11] où T3F [NIK$^{+}$20]. L'article [DH19] présente les formats des cores des TT-matrices dans librairie T3F qui est similaire à celui dans la TT-toolbox.

### 4.4.3 Opérations élémentaires

Dans la section 4.3, nous avons expliqué le TT-format et dans la section 4.4.2, nous avons présenté les objets TT-vecteurs et TT-matrices qui permettent d'écrire de vecteurs et les matrices dans le format TT. Nous expliquons dans cette section comment se font les opérations élémentaires (additions 4.4.3.1, produits TT-matrice/TT-vecteur 4.4.3.2 et produits de TT-matrices 4.4.3.3) dans ce format. Nous présentons aussi des propriétés sur les TT-rang des objets.

On note pour cette section $\mathbf{X}$ un TT-vecteur, $\mathbf{A}$ et $\mathbf{B}$ deux TT-matrices selon :

$$ 
\begin{align*}
\mathbf{X}[j_1, j_2, \dots, j_d] &= \mathbf{G}_1^{\mathbf{X}}(j_1) \cdot \mathbf{G}_2^{\mathbf{X}}(j_2) \cdots \mathbf{G}_d^{\mathbf{X}}(j_d) \\
\mathbf{A}[j_1, i_2, \dots, i_d; j_1, j_2, \dots, j_d] &= \mathbf{G}_1^{\mathbf{A}}(i_1, j_1) \cdot \mathbf{G}_2^{\mathbf{A}}(i_2, j_2) \cdots \mathbf{G}_d^{\mathbf{A}}(i_d, j_d) \\
\mathbf{B}[i_1, i_2, \dots, i_d; j_1, j_2, \dots, j_d] &= \mathbf{G}_1^{\mathbf{B}}(i_1, j_1) \cdot \mathbf{G}_2^{\mathbf{B}}(i_2, j_2) \cdots \mathbf{G}_d^{\mathbf{B}}(i_d, j_d)
\end{align*}
$$

#### 4.4.3.1 Sommes de TT-matrices

Soit $\mathbf{D} = \mathbf{A} + \mathbf{B}$. Alors, $\mathbf{D}$ s'exprime :

$$ \mathbf{D}[i_1, i_2, \dots, i_d; j_1, j_2, \dots, j_d] = \mathbf{G}_1^{\mathbf{D}}(i_1, j_1) \cdot \mathbf{G}_2^{\mathbf{D}}(i_2, j_2) \cdots \mathbf{G}_d^{\mathbf{D}}(i_d, j_d) $$

avec :

$$ 
\left\{ 
\begin{array}{l}
\mathbf{G}_1^{\mathbf{D}}(i_1, j_1) = (\mathbf{G}_1^{\mathbf{A}}(i_1, j_1) \quad \mathbf{G}_1^{\mathbf{B}}(i_1, j_1)) \\
\mathbf{G}_d^{\mathbf{D}}(i_d, j_d) = (\mathbf{G}_d^{\mathbf{A}}(i_d, j_d) \quad \mathbf{G}_d^{\mathbf{B}}(i_d, j_d)) \\
\forall k \in [2, d-1], \quad \mathbf{G}_k^{\mathbf{D}}(i_k, j_k) = (\mathbf{G}_k^{\mathbf{A}}(i_k, j_k) \quad 0 \quad \mathbf{G}_k^{\mathbf{B}}(i_k, j_k))
\end{array}
\right. 
\qquad (4.4.14) $$

Les tailles des cores de $\mathbf{D}$ sont :

$$ 
\left\{ 
\begin{array}{ll}
k = 1 & \Rightarrow \mathbf{G}_1^{\mathbf{C}}(i_1, j_1) \in \mathbb{R}^{(1 \times (r_1^{\mathbf{A}} + r_1^{\mathbf{B}}))} \\
1 < k < d & \Rightarrow \mathbf{G}_k^{\mathbf{C}}(i_k, j_k) \in \mathbb{R}^{(r_{k-1}^{\mathbf{A}} + r_{k-1}^{\mathbf{B}}) \times (r_k^{\mathbf{A}} + r_k^{\mathbf{B}})} \\
k = d & \Rightarrow \mathbf{G}_d^{\mathbf{C}}(i_d, j_d) \in \mathbb{R}^{((r_{d-1}^{\mathbf{A}} + r_{d-1}^{\mathbf{B}}) \times 1)}
\end{array}
\right. 
\qquad (4.4.15) $$

**Proposition 1.** Rang de la décomposition TT d'une somme de TT-matrice Soient $\mathbf{r}^{\mathbf{A}}$ et $\mathbf{r}^{\mathbf{B}}$ les rangs maximaux de la décomposition TT de $\mathbf{A}$ et $\mathbf{B}$. Alors, le rang maximal de $\mathbf{D}$ au format TT vérifie :

$$ \mathbf{r}^{\mathbf{D}} \le \mathbf{r}^{\mathbf{A}} + \mathbf{r}^{\mathbf{B}} \qquad (4.4.16) $$
### 4.4.3.2 Produits de TT-matrices TT-vecteurs

Soit $\mathbf{Y} = \mathbf{A} \cdot \mathbf{X}$. $\mathbf{Y}$ est un TT-vecteur qui s'écrit sous forme de tensor network :

<figure><img src="image_14.png" /><figcaption>FIGURE 4.7 – Tensor network de la TT-matrice $\mathbf{Y}$ résultante du produit de TT-matrices TT-vecteurs (format avec contraction)</figcaption></figure>

Pour le voir, nous développons les contractions des produits des cores de $\mathbf{A}$ et $\mathbf{X}$ pour obtenir :

$$ 
\begin{aligned}
\mathbf{Y}[i_1, i_2, \dots, i_d] &= \sum_{j_1, j_2, \dots, j_d} \left( \sum_{\alpha_1} \dots \sum_{\alpha_{d-1}} \mathbf{G}_1^\mathbf{A}(i_1, j_1)[1, \alpha_1] \mathbf{G}_2^\mathbf{A}(i_2, j_2)[\alpha_1, \alpha_2] \dots \mathbf{G}_d^\mathbf{A}(i_d, j_d)[\alpha_{d-1}, 1] \right) \\
&\quad \left( \sum_{\alpha_1} \dots \sum_{\beta_{d-1}} \mathbf{G}_1^\mathbf{X}(j_1)[1, \beta_1] \mathbf{G}_2^\mathbf{X}(j_2)[\beta_1, \beta_2] \dots \mathbf{G}_d^\mathbf{X}(j_d)[\beta_{d-1}, 1] \right) \\
&= \sum_{j_1, j_2, \dots, j_d} \sum_{\alpha_1, \alpha_2, \dots, \alpha_{d-1}} \sum_{\beta_1, \beta_{d-1}} \left( \mathbf{G}_1^\mathbf{A}(i_1, j_1)[1, \alpha_1] \mathbf{G}_1^\mathbf{X}(j_1)[1, \beta_1] \right) \cdot \\
&\quad \left( \mathbf{G}_2^\mathbf{A}(i_2, j_2)[\alpha_1, \alpha_2] \mathbf{G}_2^\mathbf{X}(j_2)[\beta_1, \beta_2] \right) \\
&\quad \dots \left( \mathbf{G}_d^\mathbf{A}(i_d, j_d)[\alpha_{d-1}, 1] \mathbf{G}_d^\mathbf{X}(j_d)[\beta_{d-1}, 1] \right) \quad (4.4.17)
\end{aligned}
$$

Alors, le TT-vecteur $\mathbf{Y}$ résultant s'exprime :

$$ \mathbf{Y}[i_1, i_2, \dots, i_d] = \mathbf{G}_1^\mathbf{Y}(i_1) \cdot \mathbf{G}_2^\mathbf{Y}(i_2) \dots \mathbf{G}_d^\mathbf{Y}(i_d) $$

Avec :

$$ 
\left\{
\begin{array}{ll}
k=1 & \Rightarrow \mathbf{G}_1^\mathbf{Y}(i_1)[\alpha_1, \beta_1] = \sum_{j_1} \mathbf{G}^\mathbf{A}(i_1, j_1)[1, \alpha_1] \mathbf{G}^\mathbf{X}(j_1)[\beta_1, 1] \\
1<k<d & \Rightarrow \mathbf{G}_k^\mathbf{Y}(i_k)[\alpha_{k-1}, \alpha_k, \beta_{k-1}, \beta_k] = \sum_{j_k} \mathbf{G}^\mathbf{A}(i_k, j_k)[\alpha_{k-1}, \alpha_k] \mathbf{G}^\mathbf{X}(j_k)[\beta_{k-1}, \beta_k] \\
k=d & \Rightarrow \mathbf{G}_d^\mathbf{Y}(i_d)[\alpha_d, \beta_d] = \sum_{j_d} \mathbf{G}_d^\mathbf{A}(i_d, j_d)[\alpha_{d-1}, 1] \mathbf{G}_d^\mathbf{X}(j_d)[\beta_{d-1}, 1]
\end{array}
\right.
\qquad (4.4.18)
$$

Nous notons $r_k^\mathbf{A}$, les rangs des cores de $\mathbf{A}$ et $r_k^\mathbf{X}$, les rangs des cores de $\mathbf{X}$.

$$ 
\left\{
\begin{array}{ll}
k=1 & \Rightarrow \mathbf{G}_1^\mathbf{Y}(i_1) \in \mathbb{R}^{(1 \times (r_1^\mathbf{A} \times r_1^\mathbf{X}))} \\
1<k<d & \Rightarrow \mathbf{G}_k^\mathbf{Y}(i_k) \in \mathbb{R}^{(r_{k-1}^\mathbf{A} \times r_{k-1}^\mathbf{X}) \times (r_k^\mathbf{A} \times r_k^\mathbf{X})} \\
k=d & \Rightarrow \mathbf{G}_d^\mathbf{Y}(i_d) \in \mathbb{R}^{((r_{d-1}^\mathbf{A} \times r_{d-1}^\mathbf{X}) \times 1)}
\end{array}
\right.
\qquad (4.4.19)
$$
**Proposition 2.** *Á partir de la formulation de $\mathbf{Y}$, nous pouvons déduire :*

* $\mathbf{Y}$ est un TT-vecteur (tenseur d'ordre d) et son TT-rang maximal est borné par :

$$r^{\mathbf{Y}} \leq r^{\mathbf{A}} \times r^{\mathbf{X}} \qquad (4.4.20)$$

* Si $\mathbf{A}$ est une TT-vecteur, alors $\mathbf{Y} = \mathbf{A} \cdot \mathbf{X}$ est une TT-matrice qui peut être transformée en scalaire par une contraction sur ses cores.

#### 4.4.3.3 Produits de TT-matrices

Soit,

$$C = A \cdot B$$

La TT-matrice $C$ est un tensor network qui s'exprime selon la figure 4.8 :

<figure><img src="image_15.png" /><figcaption>FIGURE 4.8 – Tensor network de la TT-matrice C résultante d'un produit TT-matrices (format avec contraction)</figcaption></figure>

En développant les contractions des produits des cores de $\mathbf{A}$ et $\mathbf{B}$, nous obtenons :

$$ 
\begin{aligned}
C[i_1, i_2, \dots, i_d; j_1, j_2, \dots, j_d] &= \sum_{l_1, l_2, \dots, l_d} \left( \sum_{\alpha_1} \dots \sum_{\alpha_{d-1}} \mathbf{G}_1^\mathbf{A}(i_1, l_1)[1, \alpha_1] \mathbf{G}_2^\mathbf{A}(i_2, l_2)[\alpha_1, \alpha_2] \dots \mathbf{G}_d^\mathbf{A}(i_d, l_d)[\alpha_{d-1}, 1] \right) \\
&\quad \left( \sum_{\alpha_1} \dots \sum_{\beta_{d-1}} \mathbf{G}_1^\mathbf{B}(l_1, j_1)[1, \beta_1] \mathbf{G}_2^\mathbf{B}(l_2, j_2)[\beta_1, \beta_2] \dots \mathbf{G}_d^\mathbf{B}(l_d, j_d)[\beta_{d-1}, 1] \right) \\
&= \sum_{l_1, l_2, \dots, l_d} \sum_{\alpha_1, \alpha_2, \dots, \alpha_{d-1}} \sum_{\beta_1, \beta_{d-1}} \left( \mathbf{G}_1^\mathbf{A}(i_1, l_1)[1, \alpha_1] \mathbf{G}_1^\mathbf{B}(l_1, j_1)[1, \beta_1] \right) \\
&\quad \left( \mathbf{G}_2^\mathbf{A}(i_2, l_2)[\alpha_1, \alpha_2] \mathbf{G}_2^\mathbf{B}(l_2, j_2)[\beta_1, \beta_2] \right) \\
&\quad \dots \left( \mathbf{G}_d^\mathbf{A}(i_d, l_d)[\alpha_{d-1}, 1] \mathbf{G}_d^\mathbf{B}(i_d, j_d)[\beta_{d-1}, 1] \right) \quad (4.4.21)
\end{aligned}
$$

Alors, la TT-matrice $C$ s'exprime :

$$C[i_1, i_2, \dots, i_d; j_1, j_2, \dots, j_d] = \mathbf{G}_1^\mathbf{C}(i_1, j_1) \cdot \mathbf{G}_2^\mathbf{C}(i_2, j_2) \dots \cdot \mathbf{G}_d^\mathbf{C}(i_d, j_d)$$

Soit $\forall k \in [1, d]$, nous notons $r_k^\mathbf{A}$, les rangs des cores de $\mathbf{A}$ et $r_k^\mathbf{B}$, les rangs des cores de $\mathbf{B}$. Alors les cores de $\mathbf{C}$ s'expriment :
$$
\left\{
\begin{array}{ll}
k=1 & \Rightarrow \mathbf{G}_1^C(i_1,j_1)[\alpha_1, \beta_1] = \sum_{l_1} \mathbf{G}^A(i_1, l_1)[1, \alpha_1] \mathbf{G}^B(l_1, j_1)[\beta_1, 1] \\
1 < k < d & \Rightarrow \mathbf{G}_k^C(i_k, j_k)[\alpha_{k-1}, \alpha_k, \beta_{k-1}, \beta_k] = \sum_{l_k} \mathbf{G}^A(i_k, l_k)[\alpha_{k-1}, \alpha_k] \mathbf{G}^B(l_k, j_k)[\beta_{k-1}, \beta_k] \\
k=d & \Rightarrow \mathbf{G}_d^C(i_d, j_d)[\alpha_d, \beta_d] = \sum_{l_d} \mathbf{G}_d^A(i_d, l_d)[\alpha_{d-1}, 1] \mathbf{G}_d^B(l_d, j_d)[\beta_{d-1}, 1]
\end{array}
\right.
\qquad (4.4.22)
$$

Nous notons $r_k^A$, les rangs des cores de $\mathbf{A}$ et $r_k^B$, les rangs des cores de $\mathbf{B}$. et

$$
\left\{
\begin{array}{ll}
k=1 & \Rightarrow \mathbf{G}_1^C(i_1,j_1) \in \mathbb{R}^{(1 \times (r_1^A \times r_1^B))} \\
1 < k < d & \Rightarrow \mathbf{G}_k^C(i_k,j_k) \in \mathbb{R}^{(r_{k-1}^A \times r_{k-1}^B) \times (r_k^A \times r_k^B)} \\
k=d & \Rightarrow \mathbf{G}_d^C(i_d,j_d) \in \mathbb{R}^{((r_{d-1}^A \times r_{d-1}^B) \times 1)}
\end{array}
\right.
\qquad (4.4.23)
$$

**Proposition 3.** *Á partir de la formulation de C, nous pouvons déduire que C est une TT-matrice (tenseur d'ordre d) et le rang maximal de sa décomposition TT est borné par :*

$$
r^{\mathbf{C}} \leq r^{\mathbf{A}} \times r^{\mathbf{B}} \qquad (4.4.24)
$$

**Remarque :** D'autres opérations sur les TT-matrices sont possibles : l'article [LC18] en présente certaines comme la contraction totale, le produits d'Hadamard ...

4.4.4 Compression des TT-matrices : utilisation du rounding

Nous avons vu dans la section précédente que le produit de deux TT-matrices augmente les
rangs maximaux des cores de la TT-matrice résultante, selon $r^{\mathbf{C}} \le r^{\mathbf{A}} \times r^{\mathbf{B}}$ si $\mathbf{C} = \mathbf{A.B}$. Une
manière de réduire ces rangs est de faire une compression de la TT-matrice résultante en l'ap-
prochant au mieux par une TT-matrice de rang plus faible. Cette démarche se réalise selon
la procédure dite de "rounding", proposé par Oseledets [Ose11] pour approcher un tenseur en
format TT par un tenseur en format TT de rang plus faible, et étendue ensuite à l'approxima-
tion de TT-vecteurs et aux TT-matrices. Nous utiliserons dans ce document essentiellement le
rounding sur des TT-matrices et TT-vecteurs.

Il s'agit simplement une TT-SVD d'un tenseur qui est déjà dans le format format TT. Les
détails de sa mise en oeuvre sont cependant très techniques, et ne seront pas repris intégrale-
ment ici. Si

$$
\mathbf{A}[i_1, i_2, \dots, i_d; j_1, j_2, \dots, j_d] = \mathbf{G}_1(i_1, j_1) \cdot \mathbf{G}_2(i_2, j_2) \cdot \dots \cdot \mathbf{G}_d(i_d, j_d)
$$

l'algorithme du rounding prend en entrée une TT-matrice **A** et une erreur $\epsilon$ ou un rang prescrit $r$. Comme dans la TT-toolbox que nous avons utilisée, la précision prescrite est favorisée, nous expliquons la version de cet algorithme avec précision prescrite. L'algorithme retourne alors $\overline{\mathbf{A}}$ en format TT de rang le plus faible tel que

$$
\| \mathbf{A} - \bar{\mathbf{A}} \| \le \epsilon \| \mathbf{A} \|
$$

Le rounding se fait en deux phases :

• Phase d'orthogonalisation :

Elle consiste à parcourir séquentiellement les *d* cores de **A** de la droite vers la gauche (c'est-à-dire du *d*-ième core au premier) et réaliser une décomposition LQ de la matrice de chaque core.
• **Phase de compressions :**

Consiste à parcourir séquentiellement les *d* cores orthogonaux de la gauche vers la droite en appliquant des décompositions SVD avec une erreur *ε* prescrite ou un rang *r* prescrit de chaque core.

Cet algorithme est décrit de manière détaillée dans l'article d'Oseledets [Ose11] dans le cadre des Tenseurs au format TT et exprimé pour les TT matrices dans l'article [DBNW20] auxquels nous renvoyons pour les détails. Le rounding comme l'approximation de rang faible de matrices par la SVD peut se faire à précision prescrite $\epsilon$ ou à rang prescrit $r$. Ces deux possibilités sont offertes par les toolbox que nous avons utilisées : la TT-toolbox [Ose11] ou T3F [NIK$^+$20].
## 4.5 Intuition de l'approche TT appliquée au calcul des marginales dans un modèle graphique

### 4.5.1 Modèles graphiques

Soit $n, m \in \mathbb{N}$,

**Un graphe** $G = (V, E)$ est composé d'un ensemble de nœuds $V$ et d'un ensemble d'arêtes $E$ :

* $V = (1, ..., n)$ représente l'ensemble fini des nœuds (vertices) de $G$.

* $E \subset V \times V$ représente un ensemble fini d'arêtes (edges). Chacune d'entre elles représente la connexion entre deux nœuds.

**Modèle graphique** [Bis06] Soit $G = (V, E)$ un graphe où l'état de chaque nœud $i \in V$ est une variable aléatoire notée $Z_i$. Nous nous intéressons à la loi jointe $P(Z_1, ..., Z_n)$. Nous considérons un ensemble $\mathcal{A}$ de $m$ parties de $V$

$$ \mathcal{A} = (A_1, ..., A_m), \quad A_\ell \subset V $$

Nous notons $Z_{A_\ell}$ ou plus simplement $Z^\ell$ l'ensemble

$$ Z_{A_\ell} = (Z_{i_1}, ..., Z_{i_\ell}) $$

si

$$ A_\ell = (i_1, ..., i_{m_\ell}), \quad m_\ell = |A_\ell|. $$

Alors, $Z = (Z_1, ..., Z_n)$ suit un modèle graphique s'il existe des fonctions réelles $\psi_\ell$ pour chaque partie $A_\ell$ telles que

$$ \mathbb{P}(z_1, ..., z_n) \propto \prod_{\ell=1}^{m} \psi_{\ell}(z_{A_{\ell}}) \qquad (4.5.1) $$

Les fonctions $\psi_{A_\ell}$ sont appelées les facteurs du modèle graphique. Nous appelons hyperlien un élément $A_\ell \subset V$, et la paire $H = (V, \mathcal{A})$ est appelée un hypergraphe.

Nous introduisons alors la constante de normalisation

$$ W = \sum_z \left( \prod_{\ell=1}^{m} \psi_{\ell}(z_{A_{\ell}}) \right) $$

Nous avons alors,

$$ \mathbb{P}(z_1, ..., z_n) = \frac{1}{W} \prod_{\ell=1}^{m} \psi_{\ell}(z_{A_{\ell}}) \qquad (4.5.2) $$

### 4.5.2 Intuition de l'approche TT

Commençons par présenter l'idée qui motive l'approche Tenseur Train et par la comparer avec le champ moyen. Tout d'abord ces deux approches sont des approximations avec séparation de variables dans un modèle graphique, ce qui facilite la marginalisation. Utilisons un modèle graphique simple comme présenté dans la figure 5.1 comme support :
<figure><img src="image_16.png" /><figcaption>FIGURE 4.9 – Exemple de modèle graphique</figcaption></figure>

Soit $n$ le nombre d'individus dans ce modèle, $Q$ le nombre d'états de chaque individu et $m$ le nombre d'hyperliens. Soit $\Psi$ une fonction qui exprime le modèle graphique présenté dans la figure 4.9,

$$ \Psi[z_1, \dots, z_7] = \prod_{\ell=1,\dots,3} \psi_{A_\ell}(z_{A_\ell}) $$

Les différents hyperliens de ce modèle sont : $A_1 = (z_1, z_2, z_3)$, $A_2 = (z_3, z_5, z_6)$ et $A_3 = (z_1, z_4, z_7)$. On en déduit,

$$ \Psi[z_1, \dots, z_7] = \psi_{A_1}(z_1, z_2, z_3) \psi_{A_2}(z_3, z_5, z_6) \psi_{A_3}(z_1, z_4, z_7) $$

* À partir de cette fonction, les marginales s'écritent comme :

$$ \forall i \in [1, 7], \quad p_i(z_i) = \sum_{z_1, z_2, \dots, z_{i-1}, z_{i+1}, \dots, z_7} \Psi[z_1, \dots, z_7] $$

Le calcul de la constante de normalisation se fait ainsi :

$$ W = \sum_{z_1, \dots, z_7} \Psi(z_1, z_2, \dots, z_7) $$

On développe cette formule et on obtient :

$$ W = \sum_{z_1=1}^{Q} \sum_{z_2=1}^{Q} \sum_{z_3=1}^{Q} \sum_{z_4=1}^{Q} \sum_{z_5=1}^{Q} \sum_{z_6=1}^{Q} \sum_{z_7=1}^{Q} \psi_{A_1}(z_1, z_2, z_3) \psi_{A_2}(z_3, z_5, z_6) \psi_{A_3}(z_1, z_4, z_7) $$

On réorganise cette formule :

$$ W = \sum_{z_3=1}^{Q} \sum_{z_5=1}^{Q} \sum_{z_6=1}^{Q} \psi_{A_3}(z_3, z_5, z_6) \left[ \sum_{z_1=1}^{Q} \sum_{z_2=1}^{Q} \psi_{A_1}(z_1, z_2, z_3) \left( \sum_{z_4=1}^{Q} \sum_{z_7=1}^{Q} \psi_{A_3}(z_1, z_4, z_7) \right) \right] \quad (4.5.3) $$

Nous constatons que ce calcul nécessite $3Q^3$ sommes. Pour les marginales unaires, le calcul nécessite $2Q^3 + Q^2$ sommes.

Une solution pour y remédier est d'approcher $\psi$ par une fonction avec séparation des variables : d'où l'approche champ moyen.
• Procédé pour la séparation des variables :

Soit,

$$
\psi(z_1, z_2, \dots, z_n) = f_1(z_1) f_2(z_2) \dots f_n(z_n)
$$

alors, par exemple,

$$
p_1(z_1) = f_1(z_1) \left[ \sum_{z_2} f_2(z_2) \right] \dots \left[ \sum_{z_n} f_n(z_n) \right]
$$

Cette formulation nécessite (n − 1)Q sommes.

Grâce à la séparation des variables, nous réduisons considérablement le nombre de sommes.

• Le champ moyen : consiste en une approximation de la loi jointe par une distribution qui est le produit des facteurs unaires pour laquelle les marginales sont plus simples à calculer.

En effet,

$$
\text{si} \qquad x_{ij} = a_i b_j
$$

$$
\text{alors,} \quad \sum_{n^2 \text{sommes}} x_{ij} = \sum_{i,j} a_i b_j = \sum_{n \text{ sommes}} a_i \sum_j b_j
$$

Nous recherchons une approximation optimale au sens de la divergence Kullback-Leibler.

• Tenseur Train : l'approche Tenseur Train est une généralisation de l'approche champ moyen.

On se donne une matrice $X \in \mathbb{R}^{n \times n}$ d'éléments $x_{ij} \in \mathbb{R}$, alors $\mathbf{w} = \sum_{i,j} x_{ij}$ nécessite $n^2$ sommes. Nous supposons maintenant qu'il existe deux familles de vecteurs $(\mathbf{a}_i)_i, (\mathbf{b}_j)_j$ telles que :

$$
\forall i,j \quad x_{ij} = \mathbf{a}_i \mathbf{b}_j \quad \left\{ \begin{array}{ll} \mathbf{a}_i & \in \mathbb{R}^{1 \times n} \\ \mathbf{b}_j & \in \mathbb{R}^{n \times 1} \end{array} \right. \qquad (4.5.4)
$$

On considère que $\mathbf{a}_i$ est une matrice $1 \times n$ (horizontale) et $\mathbf{b}_j$ est une matrice $n \times 1$
(verticale), donc $x_{ij}$ est un produit de matrices. Nous pouvons donc écrire :

$$
\sum_{i,j} x_{ij} = \sum_{i,j} \mathbf{a}_i \mathbf{b}_j = (\sum_i \mathbf{a}_i) \cdot (\sum_j \mathbf{b}_j)
$$

avec 2n sommes de matrices et un produit matriciel.

L'approche TT pour le calcul de $w = \sum_{i,j} x_{ij}$ pour $X$ (matrice quelconque) consiste à trouver la matrice $X'$ de termes $x'_{ij} = \mathbf{a}_i \cdot \mathbf{b}_j$ la plus proche de $X$ au sens de la norme de Frobenius et calculer $w(X')$.

Dans l'approche champ moyen, la loi avec variables séparées choisie est la plus proche de $\psi$
au sens de la divergence Kullback-Leibler alors que pour l'approche TT, la distance est liée
à la norme de Frobenius. De façon plus générale, nous approchons la loi jointe d'un modèle
graphique par le produit matriciel suivant :

$$
\tilde{\psi}[z_1, \dots, z_n] = u(z_1) \cdot G_2(z_2) \cdots \cdot G_{n-1}(z_{n-1}) \cdot v(z_n)
\begin{cases}
u(z_1) & \in \mathbb{R}^{1 \times r} \\
G_i(z_i) & \in \mathbb{R}^{r \times r} \\
v(z_n) & \in \mathbb{R}^{r \times 1}
\end{cases}
\quad (4.5.5)
$$

qui est une forme de séparation des variables (chaque coefficient $\psi'[z_1, \dots, z_n]$ est un produit de
matrices qui dépendent chacune d'une variable uniquement).
## 4.6 Résumé de l'approche TT pour calculer les marginales d'un modèle graphique

On prend le cas d'un modèle graphique avec $n \in \mathbb{N}$ nœuds, $Q \in \mathbb{N}$ états et $\Lambda = \llbracket 1, Q \rrbracket$ l'espace des états (c'est-à-dire que $\forall i \in \mathbb{N}, z_i \in \Lambda$). Soit $z$ l'ensemble des états du modèle. Sa loi jointe s'exprime :

$$ \psi : \Lambda^n \xrightarrow{\psi} \mathbb{R} \\ (z_1, \dots, z_n) \longrightarrow \psi(z) \tag{4.6.1} $$

Nous notons $z^\ell$ le tuple des états des nœuds intervenant dans l'hyperlien $A_\ell$ et $\psi_{A_\ell}(z^\ell)$ les facteurs associés à cet hyperlien. Alors, la loi jointe peut s'exprimer :

$$ \psi(z_1, \dots, z_n) = \prod_{\ell=1}^{m} \psi_{A_\ell}(z^\ell) \tag{4.6.2} $$

Pour alléger nos formules, nous simplifions certaines notations : $\psi_{A_\ell}$ devient $\psi^\ell$ et $z = (z_1, \dots, z_n)$. Ainsi la formule (4.6.2) s'exprime :

$$ \psi(z) = \prod_{\ell} \psi^{\ell}(z^{\ell}) \tag{4.6.3} $$

Ensuite, comme $\forall \ell \in \llbracket 1, m \rrbracket$, $\psi^\ell(z^\ell) \in \mathbb{R}$, nous utilisons la propriété $P_2$ pour réécrire la formule (4.6.3) avec un produit de Kronecker.

$$ \psi(z) = \psi^1(z^1) \otimes_k \psi^2(z^2) \otimes_k \dots \otimes_k \psi^m(z^m) \tag{4.6.4} $$

Cela nous permettra d'utiliser la propriété du produit mixte ($P_1$ "mixed-product property") plus tard.

* **Étape 1 : approximation des facteurs $\psi_\ell$, $\forall \ell = 1, \dots, m$ au format TT.** Cette étape se décompose en deux parties :

Soit $i_1, \dots, i_{m_\ell} \in \llbracket 1, n \rrbracket^{m_\ell}$, $A_\ell = \{i_1, \dots, i_{m_\ell}\}$ les noeuds intervenant dans $(A_\ell)$ de cardinal $m_\ell = \text{card}(A_\ell)$. Nous notons $z_{if}$ l'état du noeud $if$ et $z^\ell$ les états des noeuds intervenant dans $(A_\ell)$.

**Mise des facteurs sous format tensoriel.** Pour chaque hyperlien $\ell = 1, \dots, m$, nous associons un tenseur indexé par $z^\ell$: $\psi^\ell$ d'ordre $m_\ell$, de modes $i_1, \dots, i_{m_\ell}$ et de dimensions $Q^{m_\ell}$.

**TT-SVD.** Nous faisons une TT-SVD des tenseurs associés aux facteurs $\psi^\ell$: l'approximation TT du facteur $\ell$ se décompose selon :

$$ \psi^{\ell}(z_{i_1}, \dots, z_{i_{m_{\ell}}}) = G_{i_1}^{\ell}(z_{i_1}) \cdot G_{i_2}^{\ell}(z_{i_2}) \cdots \cdot G_{i_{m_{\ell}}}^{\ell}(z_{i_{m_{\ell}}}) \tag{4.6.5} $$

$G_{i_1}^\ell(z_{i_1}), \dots, G_{i_{m_\ell}}^\ell(z_{i_{m_\ell}})$ sont appelés les cores de l'approximation TT des facteurs. Ils sont de tailles : $G_{i_1}^\ell(z_{i_1}) \in \mathbb{R}^{1 \times r_1}$, $G_{i_{m_\ell}}^\ell(z_{i_{m_\ell}}) \in \mathbb{R}^{r_{i_{m_\ell}} \times 1}$ et $\forall k \in \llbracket 1, m_\ell \rrbracket$, $G_{i_k}^\ell(z_{i_k}) \in \mathbb{R}^{r_{k-1} \times r_k}$ où $r$ est le rang maximal de au format TT du facteur comme nous l'avons expliqué dans l'état de l'art sur les tenseurs.

Nous voyons apparaître la séparation des variables via le format TT pour chaque facteur. La suite de la démarche est de construire une séparation des variables de type format TT pour la loi jointe (produit de tous les facteurs). cela se fait via un "trick" proposé par Novikov & al. (2014) : l'ajout de variables non essentielles
• Étape 2 : Ajout des dimensions non essentielles. Deux facteurs $\ell_1$ et $\ell_2$ différent selon les variables dans $A_\ell$. Nous présenterons un exemple simple pour $n=4$ et $m=2$ :

$$ \psi(z) = \psi^1(z_1, z_2, z_3)\psi^2(z_2, z_3, z_4) $$

Nous avons :

$$ \psi^1(z_1, z_2, z_3) = G_1^1(z_1)G_1^2(z_2)G_1^3(z_3) $$

$$ \psi^2(z_2, z_3, z_4) = G_2^2(z_2)G_2^3(z_3)G_2^4(z_4) $$

Nous rajoutons les variables dites non essentielles par Novikov [NROV14] de telle façon que les nouveaux facteurs dépendent des mêmes variables. Nous écrivons :

$$ \bar{\psi}^1(z_1, z_2, z_3) = G_1^1(z_1)G_1^2(z_2)G_1^3(z_3)G_1^4(z_4) $$

avec $G_1^4(z_4) = 1 \in \mathbb{R}$

$$ \bar{\psi}^2(z_2, z_3, z_4) = G_2^1(z_1)G_2^2(z_2)G_2^3(z_3)G_2^4(z_4) $$

avec $G_2^1(z_1) = 1 \in \mathbb{R}$

Il est possible de montrer [NROV14] que ce complément est toujours possible, avec des choix $\forall k \in [1, n]$, $G_k^\ell(z_k) = 1$ ou $\mathbb{I}_r$ pour les variables non essentielles selon la règle : Si

$$ \psi^\ell(z_{i_1}, \dots, z_{i_{m_\ell}}) = \prod_{k=1}^{i_{m_\ell}} G_k^\ell(z_k) \qquad (4.6.6) $$

Nous l'exprimons en fonction de tous les individus :

$$ \overline{\psi^\ell}(z^\ell) = \prod_{k=1}^{n} \varphi_k^\ell(z_k) \qquad (4.6.7) $$

Avec

$$
\left|
\begin{array}{lll}
k < i_1 & \Rightarrow & \varphi_k^\ell(z_k) = 1 \quad \in \mathbb{R}^{1 \times 1} \\
k = i_1 & \Rightarrow & \varphi_k^\ell(z_k) = G_{i_1}^\ell(z_{i_1}) \quad \in \mathbb{R}^{1 \times r_{i_1}} \\
i_1 < k < i_{m_\ell}, k \notin A_\ell & \Rightarrow & \varphi_k^\ell(z_k) = \mathbb{I}_{Q, Q} \quad \in \mathbb{R}^{r_{k-1} \times r_k} \\
i_1 < k < i_{m_\ell}, k \in A_\ell & \Rightarrow & \varphi_k^\ell(z_k) = G_k^\ell(z_k) \quad \in \mathbb{R}^{r_{k-1} \times r_k} \\
k = i_{m_\ell} & \Rightarrow & \varphi_k^\ell(z_k) = G_{i_{m_\ell}}^\ell(z_{i_{m_\ell}}) \quad \in \mathbb{R}^{r_{i_{m_\ell}}-1 \times 1} \\
k > i_{m_\ell} & \Rightarrow & \varphi_k^\ell(z_k) = 1 \quad \in \mathbb{R}^{1 \times 1}
\end{array}
\right.
\qquad (4.6.8)
$$

**Remarque 4.** $\overline{\psi^\ell(z^\ell)}$ ne dépend que de $z_{i_1}, \dots, z_{i_{m_\ell}}$ et pas des $z_k$ pour $k \notin A_\ell$ qui sont des variables muettes donc :

$$ \psi^\ell(z_{i_1}, \dots, z_{i_{m_\ell}}) = \overline{\psi^\ell(z^\ell)} $$

• Étape 3 : Écriture de $\psi(z)$ avec rajout des dimensions non essentielles. Cette écriture repose sur la propriété "Mixed-product property". et utilise la formule (4.6.7) afin de réécrire la formule (4.6.4) de cette manière :

$$
\begin{align}
\psi(z) &= \psi_1(z) \otimes_k \psi_2(z) \otimes_k \dots \otimes_k \psi_m(z) \nonumber \\
&= (\varphi_1^1(z_1) \cdot \varphi_2^1(z_2) \cdots \varphi_n^1(z_n)) \otimes_k \tag{4.6.9} \\
&\quad (\varphi_1^2(z_1) \cdot \varphi_2^2(z_2) \cdots \varphi_n^2(z_n)) \otimes_k \nonumber \\
&\quad \dots \otimes_k (\varphi_1^m(z_1) \cdot \varphi_2^m(z_2) \cdots \varphi_n^m(z_n)) \nonumber
\end{align}
$$
Ensuite, nous utilisons la Mixed-product property ($P_2$) pour exprimer $\psi(z)$ :

$$
\begin{align*}
\psi(z) ={}& (\varphi_1^1(z_1) \otimes_k \varphi_1^2(z_1) \otimes_k \cdots \otimes_k \varphi_1^m(z_1)) \cdot \\
& (\varphi_2^1(z_2) \otimes_k \varphi_2^2(z_2) \otimes_k \cdots \otimes_k \varphi_2^m(z_2)) \cdot \tag{4.6.10} \\
& \cdots (\varphi_n^1(z_n) \otimes_k \varphi_n^2(z_n) \otimes_k \cdots \otimes_k \varphi_n^m(z_n))
\end{align*}
$$

• Étape 4 : Séparation des variables. Nous notons :

$$
A_i[z_i] = \otimes_{k \ell=1}^{m} \varphi_i^{\ell}(z_i) \qquad (4.6.11)
$$

À partir de la formule (4.6.10) et (4.6.11) nous avons :

$$
\psi(z) = \prod_{i=1}^{n} A_i[z_i] \qquad (4.6.12)
$$

Cette écriture dans un format de produit matriciel est une écriture de $\psi(z)$ avec une séparation des variables $z_i$. C'est l'écriture en format TT du tenseur associé à la loi jointe $\psi(z)$.

• Étape 5 : Marginalisation. Grâce à la séparation des variables,nous pouvons calculer faci-
lement différentes marginalisations comme la constante de normalisation, des marginales
unaires et binaires qu'on présente ci-dessous :

• Constante de normalisation :

$$
W = \sum_z \psi(z)
$$

On utilise la propriété de distributivité du produit sur les sommes pour développer
notre calcul et nous obtenons :

$$
W = \sum_{z_1} \dots \sum_{z_n} \left( \prod_{i=1}^{n} A_i[z_i] \right) = \sum_{z_1} \dots \sum_{z_n} A_1[z_1] \dots A_2[z_2] \dots \dots A_n[z_n]
$$

Ainsi, la constante de normalisation s'exprime :

$$
W = \left( \sum_{z_1} A_1[z_1] \right) \cdot \left( \sum_{z_2} A_2[z_2] \right) \cdots \left( \sum_{z_n} A_n[z_n] \right) \quad (4.6.13)
$$

On pose :

$$
B_i = \sum_{z_i} A_i[z_i]
$$

On peut transformer la formule (4.6.13) et exprimer la constante de normalisation
de cette manière :

$$
W = B_1 B_2 \cdots B_n \tag{4.6.14}
$$

• Marginales unaires :

$$
\forall i \in [1,n], \quad p_i(z_i) = \sum_{z_1, z_2, \dots, z_{i-1}, z_{i+1}, \dots, z_n} \psi(z)
$$

On redéveloppe cette formule de la même manière (nous notons × le produit matri-
ciel).

$$
p_i(z_i) = \left( \sum_{z_1} A_1[z_1] \right) \cdot \left( \sum_{z_2} A_2[z_2] \right) \cdots \left( \sum_{z_{i-1}} A_{i-1}[z_{i-1}] \right) \cdot A_{i+1}[z_{i+1}] \cdot \left( \sum_{z_{i+1}} A_{i+1}[z_{i+1}] \right) \cdots \left( \sum_{z_n} A_n[z_n] \right) \tag{4.6.15}
$$

$$
p_i(z_i) = B_1 \dots B_{i-1} A_i[z_i] B_{i+1} \dots B_n \quad (4.6.16)
$$
• Marginales binaires : De la même manière que pour les marginales unaires, nous faisons le calcul des marginales binaires :

$$
\forall i, j \in [1, n]^2, \quad p_{ij}(z_i, z_j) = \sum_{z_1, z_2, \dots, z_{i-1}, z_{i+1}, \dots, z_{j-1}, z_{j+1}, \dots, z_n} \psi(z)
$$

$$
p_{i,j}(z_i, z_j) = B_1 \dots B_{i-1} A_i[z_i] B_{i+1} \dots B_{j-1} A_j[z_j] B_{j+1} \dots B_n \quad (4.6.17)
$$

4.7 Conclusion

Dans ce chapitre, nous avons présenté les concepts algébriques derrière le format Tenseur Train
et la procédure de Novikov appliquée aux modèles graphiques.

Ce chapitre est divisé en deux parties. La première présente le format Tenseur Train que nous
utilisons tout au long de ce manuscrit. Pour cela, nous avons commencé par faire quelques
rappels d'algébre linéaire dans la section 4.2. Nous avons ensuite présenté TT-format d'une loi
jointe et sa représentation à l'aide de contraction dans le format Tensor Network dans la section
4.3. Enfin, dans la section 4.4, nous avons présenté le format TT-matrice et TT-vecteur qui
sera utilisé dans les chapitres 5 et 7.

La deuxième partie de ce chapitre porte sur la procédure de Novikov. Elle est subdivisée en
deux sections : une première 4.5 où la mise au format TT d'une loi jointe est développée. Puis,
une seconde section 4.6 où est développée l'approche de Novikov [NROV14] pour le calcul des
marginales d'un modèle graphique.

Dans le chapitre 5 qui suit, nous utilisons les concepts présentés dans la première partie de
ce chapitre pour transposer et expliciter l'approche de Novikov sur les SBM.
# Chapitre 5

## Approche de type Tenseur Train pour le calcul des marginales binaires dans un modèle à blocs stochastiques

<table><caption>Table des matières</caption><tr><td>5.1 Introduction</td><td>59</td></tr><tr><td>5.2 Approche TT appliquée sur un modèle SBM</td><td>59</td></tr><tr><td>5.2.1 Rappels sur les SBM</td><td>59</td></tr><tr><td>5.2.2 Calcul des facteurs des modèles</td><td>60</td></tr><tr><td>5.2.3 SVD sur les facteurs binaires et séparation des variables</td><td>61</td></tr><tr><td>5.2.4 Calcul des matrices intermédiaires A<sub>i</sub>[z<sub>i</sub>] et B<sub>i</sub>:</td><td>62</td></tr><tr><td>5.2.5 Tailles des matrices intermédiaires A<sub>i</sub>[z<sub>i</sub>] et B<sub>i</sub></td><td>63</td></tr><tr><td>5.2.6 Réécriture de la procédure dans le format tenseur train</td><td>65</td></tr><tr><td>5.2.7 Implémentation de l'approche:</td><td>68</td></tr><tr><td>5.3 Méthode de calcul des marginales via une mutualisation des calculs</td><td>69</td></tr><tr><td>5.3.1 Calcul des marginales unaires</td><td>69</td></tr><tr><td>5.3.2 Calcul des marginales binaires</td><td>70</td></tr><tr><td>5.3.3 Organisation des calculs sur un arbre</td><td>70</td></tr><tr><td>5.4 Conclusion</td><td>72</td></tr></table>
## 5.1 Introduction

Dans le chapitre précédant, nous avons expliqué l'approche Tenseur Train pour la séparation des variables et son application dans la procédure de Novikov et al. [NROV14] pour le calcul des marginales unaires dans le cadre d'un modèle graphique. Dans ce chapitre :

* nous avons dans un premier temps présenté une déclinaison de la procédure présentée par Novikov et al. [NROV14] pour le calcul des marginales d'un modèle SBM. Nous avons ensuite présenté les difficultés calculatoires derrière cette approche ainsi qu'une réécriture de cette procédure dans le format tenseur train ;

* ensuite, nous avons présenté une organisation des calculs des marginales sur un arbre ainsi que la complexité de cette organisation des calculs.

## 5.2 Approche TT appliquée sur un modèle SBM

Nous avons présenté les SBM dans le chapitre 2 comme un cas particulier de modèles graphiques où les facteurs ne concernent que des paires d'individus, et pour toutes les paires. Nous pouvons donc parler de liens au lieu d'hyperliens. Cela aura pour effet la simplification de la procédure de Novikov et plus précisément l'étape 1 : En effet, les facteurs sont binaires donc nous pouvons utiliser des matrices au lieu des tenseurs pour les stocker. De plus, la TT-SVD se transforme en une simple SVD.

De plus, dans le cadre des SBM, chaque individu est connecté avec tous les autres. Le niveau d'interaction est une clique. Il s'agit du cas le plus difficile pour l'inférence dans les modèles graphiques avec des facteurs binaires. L'impact de cela et que nous devons traiter m facteurs binaires et n facteurs unaires avec m qui s'exprime :

$$m = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1 = \frac{n(n-1)}{2}$$

Nous allons faire la présentation de la méthode de calcul des marginales dans le cadre d'un modèle SBM Poisson. Cette procédure pourra se généraliser pour les SBM pondérés par des distances.

### 5.2.1 Rappels sur les SBM

**Paramètres des modèles** : Un modèle SBM prend en entrée une matrice de distances $n \times n$ si le nombre d'individus est $n \in \mathbb{N}$.

Il prend comme paramètres : un nombre de classes $Q \in \mathbb{N}$, une matrice de distance $D \in \mathbb{M}_{n,n}(\mathbb{N})$, un vecteur de proportions des individus dans les classes $\alpha \in [0, 1]^Q$ et une structure des distances entre les classes $\Lambda \in \mathbb{M}_{Q,Q}(\mathbb{R})$. Il utilise ces paramètres afin d'exprimer la loi jointe.

L'ensemble des paramètres est désigné par $\theta = (Q, \alpha, \lambda)$.

**Loi jointe** : Soit $\mathbb{P}_{\theta}(z_1, \dots, z_n | D)$ la fonction qui exprime la loi jointe conditionnellement aux données du modèle. Alors,

$$\mathbb{P}_{\theta}(z_1, \dots, z_n | D) = \frac{1}{W} \left[ \prod_{i=1}^{n} \prod_{j>i} \psi_{i,j}(z_i, z_j) \right] \left[ \prod_{i=1}^{n} \phi_i(z_i) \right] \quad (5.2.1)$$

avec $\psi_{i,j}(z_i, z_j)$ le facteur binaire entre l'individu i et l'individu j et $\phi_i(z_i)$ le facteur unaire de l'individu i.
Dans la formule (5.2.1), il s'agit de la loi jointe conditionnelle, le lien avec la formule (2.2.17) peut être fait par la formule de Bayes.

$$ \mathbb{P}(z_1, \dots, z_n | D) = \frac{\mathbb{P}(z, D)}{\mathbb{P}(D)} \qquad (5.2.2) $$

La constante de normalisation de $\mathbb{P}(z_1, \dots, z_n | D)$ est égale à $W = \mathbb{P}(D)$.

## 5.2.2 Calcul des facteurs des modèles

**Facteurs** Nous commençons par rappeler les formules des facteurs unaires puis binaires du modèle que nous avons présenté dans les formules (2.2.19) et (2.2.18) de la section 2.2.1.4 :

$$ \phi_i(z_i) = \prod_{q=1}^{Q} \alpha_q^{z_{i,q}} \qquad (5.2.3) $$

$$ \psi_{i,j}(z_i, z_j) = \sum_{q=1}^{Q} \sum_{q'=1}^{Q} \frac{\lambda_{q,q'}^{D(i,j)}}{D(i,j)!} \exp(-\lambda_{q,q'}) z_{i,q} \times z_{j,q'} \qquad (5.2.4) $$

avec $z_i$ représente l'état du nœud $i$ et $z_{i,q}$ s'exprime :

$$ \left\{ \begin{array}{l} z_{i,q} = 1 (i \in q) \\ \sum_{q=1}^{Q} z_{i,q} = 1 \end{array} \right. $$

**Nouvelle réécriture des facteurs :** Nous décidons de rattacher le facteur unaire $\phi_i(z_i)$ au facteur binaire $\psi_{i,j}(z_i, z_j)$ pour former de nouveaux facteurs binaires. Cela se fait ainsi :

$$ \left| \begin{array}{lcl} \psi'_{i,i+1}(z_i, z_{i+1}) & = & \psi_{i,i+1}(z_i, z_{i+1})\phi_i(z_i) \quad \forall 1 \le i \le n-2 \\ \psi'_{i,j}(z_i, z_j) & = & \psi_{i,j}(z_i, z_j) \quad \text{si } j \ne i+1 \\ \psi'_{n-1,n}(z_{n-1}, z_n) & = & \psi_{n-1,n}(z_{n-1}, z_n)\phi_{n-1}(z_{n-1})\phi_n(z_n) \end{array} \right. \qquad (5.2.5) $$

En faisant cette transformation, la loi jointe conditionnellement aux données s'exprime :

$$ \mathbb{P}_{\theta}(z_1, \dots, z_n | D) = \frac{1}{W} \prod_{i=1}^{n} \prod_{j>i} \psi'_{ij}(z_i, z_j | \theta, D) \qquad (5.2.6) $$

Dans ce qui va suivre, pour être en accord avec la section ??, où les facteurs n'ont qu'un seul indice, nous noterons les tuples $\{i, j\} = \ell$, ainsi, $\ell = 1, \dots, m$ avec $m = \frac{n(n-1)}{2}$.

**Correspondance entre $\ell$ et $i, j$ :** Nous définissons une bijection entre $(i, j)$ et $\ell$ selon la fonction $\zeta$ suivante :

$$ \zeta : \llbracket 1, n-1 \rrbracket \times \llbracket i+1, n \rrbracket \xrightarrow{\zeta} \llbracket 1, m \rrbracket \qquad (5.2.7) \\ (i, j) \qquad \longrightarrow (i-1)(n-\frac{i}{2}) + j - i $$

Nous prenons un exemple où $n=6$, si nous choisissons $i=1, j=2$. Nous aurons $\ell=1$ et pour $i=3, j=5$ nous aurons $\ell=11$. Cette correspondance sera utilisée pour le reste du chapitre. Nous exprimons la loi jointe conditionnelle avec la nouvelle notation :

$$ \mathbb{P}_{\theta}(z_1, \dots, z_n, D) = \frac{1}{W} \prod_{\ell=1}^{m} \psi'_{\ell}(z^{\ell} | \theta, D) \qquad (5.2.8) $$
### 5.2.3 SVD sur les facteurs binaires et séparation des variables

Soit un tuple d'individus $(i, j) \in [1, n-1] \times [i+1, n]$. Le facteur binaire associé est $\psi'_{i,j} \in \mathbb{R}^{Q \times Q}$.

Avec $\forall z_i, z_j \in [1, Q]^2$, les états des individus i et j nous avons $\psi'_{i,j}(z_i, z_j) \in \mathbb{R}$.

Nous faisons une décomposition en valeurs singulières (présentée dans la section 4.2) de $\psi'_{i,j}$ :

$$ \underbrace{\psi'_{i,j}}_{\mathbb{R}^{Q \times Q}} = \underbrace{U^{i,j} \Sigma^{i,j}}_{G_i^{ij}} \underbrace{(V^{i,j})^T}_{G_j^{ij}} \quad (5.2.9) $$

$$ \text{avec, } \begin{cases} G_i^{ij} \in \mathbb{R}^{Q \times r} \\ G_j^{ij} \in \mathbb{R}^{r \times Q} \end{cases} $$

$\Sigma^{i,j}$ est une matrice diagonale qui s'exprime :

$$ \Sigma^{i,j} = \begin{pmatrix} \sigma_1 & 0 & \cdots & \cdots \\ 0 & \sigma_2 & \cdots & \vdots \\ \vdots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & \sigma_Q \end{pmatrix} $$

Cette décomposition peut se faire de manière exacte avec une SVD complète comme présenté dans la définition 4.2 ou avec une approximation de rang faible comme présenté dans la formule (4.2.9).

Ainsi,

<figure><img src="image_17.png" /><figcaption>FIGURE 5.1 – Décomposition en valeurs singulières d'un facteur</figcaption></figure>

Aussi :

$$ \psi'_{i,j}[z_i, z_j] = \sum_{s=1}^{r} G_i^{i,j}[z_i, s] G_j^{i,j}[s, z_j] $$

Si nous posons :

$$ g_i^{i,j}[z_i] = (G_i^{i,j}[z_i, 1] \quad G_i^{i,j}[z_i, 2] \quad \dots \quad G_i^{i,j}[z_i, r]) \quad (5.2.10) $$

Et,

$$ g_j^{i,j}[z_j] = \begin{pmatrix} G_j^{i,j}[z_j, 1] \\ G_j^{i,j}[z_j, 2] \\ \vdots \\ G_j^{i,j}[z_j, r] \end{pmatrix} \quad (5.2.11) $$
Ainsi,

$$ \underbrace{\psi'_{i,j}(z_i, z_j)}_{\in \mathbb{R}} = \underbrace{g_i^{i,j}[z_i]}_{\in \mathbb{R}^{1 \times r}} \cdot \underbrace{g_j^{i,j}[z_j]}_{\in \mathbb{R}^{r \times 1}} $$

**Remarque :** Nous indiquons dans la figure 5.1 que grâce à la SVD, nous pouvons décomposer les matrices des facteurs $\psi'_{i,j}$ en un produit de deux matrices, $G_i^{ij}$ où chacune ne dépend que de $i$ ou de $j$. Cela est une séparation des variables pour les facteurs binaires, et sera exploité dans la suite de ce travail pour le calcul de la constante de normalisation et des marginales d'un modèle SBM.

### 5.2.4 Calcul des matrices intermédiaires $A_i[z_i]$ et $B_i$ :

* **Étape 1 : SVD sur les matrices des nouveaux facteurs binaires** Pour chaque facteur binaire $\psi'_{i,j} \in \mathbb{R}^{Q \times Q}$ associé à l'arête entre deux individus $i$ et $j$ nous faisons une SVD au rang $r$ :

$$ \psi'_{i,j} = U^{i,j} \Sigma^{i,j} (V^{i,j})^T + E^{i,j} \quad (5.2.12) $$

Avec $U^{i,j} \in \mathbb{R}^{Q \times r}$, $\Sigma^{i,j} \in \mathbb{R}^{r \times r}$ et $(V^{i,j})^T \in \mathbb{R}^{r \times Q}$ où $r \in [1, Q]$ le rang de l'approximation de la matrice $\psi'_{i,j}$ avec une erreur $E^{i,j} \in \mathbb{R}^{Q \times Q}$. En particulier, $||E^{i,j}||_F = 0$ si $r = Q$.

Nous notons :

$$ G_i^{i,j} = U^{i,j} \Sigma^{i,j} \quad (5.2.13) $$

Et,

$$ G_j^{i,j} = (V^{i,j})^T \quad (5.2.14) $$

Avec $G_i^{i,j} \in \mathbb{R}^{Q \times r}$ et $G_j^{i,j} \in \mathbb{R}^{r \times Q}$.

Donc,

$$ \psi'_{i,j} = G_i^{i,j} G_j^{i,j} + E^{i,j} \quad (5.2.15) $$

* **Étape 2 : Ajout des dimensions non essentielles :** Les SBM sont des modèles graphiques où les liens sont binaires. Alors, chaque facteur ne dépend que de deux individus $i, j \in [1, n]$. Nous devrons donc rajouter $n-2$ dimensions non essentielles.

Nous notons $\overline{\psi'_{i,j}[z_i, z_j]}$ l'expression sur les facteurs $\psi'_{i,j}[z_i, z_j]$ avec les dimensions non essentielles.

Alors la formule (4.6.7) s'exprime :

$$ \overline{\psi'_{i,j}[z_i, z_j]} = \underbrace{G_1^{i,j}[z_1] \dots G_{i-1}^{i,j}[z_{i-1}]}_{1} \underbrace{G_i^{i,j}[z_i]}_{\in \mathbb{R}^{1,r}} \underbrace{G_{i+1}^{i,j}[z_{i+1}] \dots G_{j-1}^{i,j}[z_{j-1}]}_{\mathbb{I}_r} \underbrace{G_j^{i,j}[z_j] G_{j+1}^{i,j}[z_{j+1}] \dots G_n^{i,j}[z_n]}_{\in \mathbb{R}^{r,1}} \quad (5.2.16) $$

où __ désigne un vecteur horizontal et | un vecteur vertical. Ainsi, (4.6.8) peut être formulée :

$$ \left| \begin{array}{lll} k < i & \Rightarrow & G_k^{i,j}[z_k] = 1 \quad \in \mathbb{R}^{1 \times 1} \\ k = i & \Rightarrow & G_k^{i,j}[z_k] = G_i^{i,j}[z_i] \quad \in \mathbb{R}^{1 \times r} \\ i < k < j & \Rightarrow & G_k^{i,j}[z_k] = \mathbb{I}_{r,r} \quad \in \mathbb{R}^{r \times r} \\ k = j & \Rightarrow & G_k^{i,j}[z_k] = G_j^{i,j}[z_j] \quad \in \mathbb{R}^{r \times 1} \\ k > i & \Rightarrow & G_k^{i,j}[z_k] = 1 \quad \in \mathbb{R}^{1 \times 1} \end{array} \right. \quad (5.2.17) $$
* **Étape 4 : Séparation des variables** : Nous calculons les matrices intermédiaires $A_i[z_i]$ et $B_i$ comme nous l'avons fait durant l'étape 4 du procédé de Novikov. Pour cela, nous utiliserons les matrices calculées à la fin des deux premières étapes pour construire la matrice $A_i[z_i]$ de cette manière :

<table><thead><tr><th></th><th>i = 1</th><th>i = 2</th><th>...</th><th>i = n</th></tr></thead><tbody><tr><td>ψ'<sub>1,2</sub></td><td>G<sup>1,2</sup><sub>1</sub>[z<sub>1</sub>]</td><td>G<sup>1,2</sup><sub>2</sub>[z<sub>2</sub>]</td><td>...</td><td>G<sup>1,2</sup><sub>n</sub>[z<sub>n</sub>]</td></tr><tr><td>ψ'<sub>1,3</sub></td><td>G<sup>1,3</sup><sub>1</sub>[z<sub>1</sub>]</td><td>G<sup>1,3</sup><sub>2</sub>[z<sub>2</sub>]</td><td>...</td><td>G<sup>1,3</sup><sub>n</sub>[z<sub>n</sub>]</td></tr><tr><td>⋮</td><td></td><td></td><td>⋮</td><td></td></tr><tr><td>ψ'<sub>i,j</sub></td><td>G<sup>i,j</sup><sub>1</sub>[z<sub>1</sub>]</td><td>G<sup>i,j</sup><sub>2</sub>[z<sub>2</sub>]</td><td>...</td><td>G<sup>i,j</sup><sub>n</sub>[z<sub>n</sub>]</td></tr><tr><td>⋮</td><td></td><td></td><td>⋮</td><td></td></tr><tr><td>ψ'<sub>n-1,n</sub></td><td>G<sup>n-1,n</sup><sub>1</sub>[z<sub>1</sub>]</td><td>G<sup>n-1,n</sup><sub>2</sub>[z<sub>2</sub>]</td><td>...</td><td>G<sup>n-1,n</sup><sub>n</sub>[z<sub>n</sub>]</td></tr><tr><td>⇒</td><td>A<sub>1</sub>[z<sub>1</sub>]</td><td>A<sub>2</sub>[z<sub>2</sub>]</td><td>...</td><td>A<sub>n</sub>[z<sub>n</sub>]</td></tr></tbody></table>

Avec,

$$A_i[z_i] = G_i^{1,2}[z_i] \otimes_k G_i^{1,3}[z_i] \otimes_k \dots \otimes_k G_i^{n-1,n}[z_i] \quad (5.2.18)$$

où $\otimes_k$ désigne le produit de Kronecker.

On appelle les $\forall \ell \in [1, n]$, $k \in [\ell+1, n]$ $G_i[z_i]$ les cores de la matrice $A_i[z_i]$.

Puis, les matrices $B_i$ s'expriment :

$$B_i = \sum_{z_i} A_i[z_i] \quad (5.2.19)$$

### 5.2.5 Tailles des matrices intermédiaires $A_i[z_i]$ et $B_i$

Dans cette section, nous présenterons quelques propriétés des matrices $A_i[z_i]$ et $B_i$ et les problèmes d'implémentation que leur manipulation pourrait engendrer.

**Proposition 5.** Soit $i \in [1, n]$, la matrice $A_i[z_i]$ est calculée à partir de

* $P_1 : i-1$ cores de tailles $r \times 1$

* $P_2 : n-i$ cores de tailles $1 \times r$

* $P_3 : (i-1)(n-i)$ cores de tailles $r \times r$

* $P_4 : \frac{(n-1)(n-2)}{2} - (i-1)(n-i)$ cores de tailles $1 \times 1$

**Démonstration.** Soit $n \in \mathbb{N}$, $m = \frac{n(n-1)}{2}$ et $i \in [1, n]$. La matrice $A_i[z_i]$ s'exprime :

$$A_i[z_i] = G_i^{1,2}[z_i] \otimes_k G_i^{1,3}[z_i] \otimes_k \dots \otimes_k G_i^{n-1,n}[z_i]$$

Cette matrice est formée par le produit de Kronecker de $m$ cores qui sont soit des scalaires, soit des vecteurs soit des matrices.

Nous nous intéressons maintenant aux tailles des cores.

Le nœud $i$ apparaît dans les liens suivants :

* Par la droite : $1 \to i, 2 \to i, \dots, i-1 \to i$

* Par la gauche : $i \to i+1, i \to i+2, \dots, i \to n$
On utilise la formule (5.2.17) pour déterminer la taille des cores :

$$
A_i[z_i] = G_i^{1,2}[z_i] \otimes_k G_i^{1,3}[z_i] \otimes_k \dots \otimes_k G_i^{n-1,n}[z_i]
$$
$$
\text{avec,}
$$
$$
\left|
\begin{array}{rcll}
i < k & \Rightarrow & G_i^{k,l}[z_i] = 1 & \in \mathbb{R}^{1 \times 1} \\
i = k & \Rightarrow & G_i^{k,l}[z_i] = G_i^{i,l}[z_i] & \in \mathbb{R}^{1 \times r} \\
k < i < \ell & \Rightarrow & G_i^{k,\ell}[z_i] = \mathbb{I}_{r,r} & \in \mathbb{R}^{r \times r} \\
i = \ell & \Rightarrow & G_i^{k,\ell}[z_i] = G_i^{k,i}[z_i] & \in \mathbb{R}^{r \times 1} \\
i > \ell & \Rightarrow & G_i^{k,\ell}[z_i] = 1 & \in \mathbb{R}^{1 \times 1}
\end{array}
\right|
\qquad (5.2.20)
$$

* Quand $i$ apparaît à droite d'une connexion : Cela donne des cores de tailles $r \times 1$ : Nous remarquons que nous avons $i-1$ connexion par la droite et donc $i-1$ cores de tailles $r \times 1$. ($P_1$)

* Quand $i$ apparaît à gauche d'une connexion : Cela donne des cores de tailles $1 \times r$ : Comme nous avons $n-i$ connexion à gauche donc $n-i$ cores de tailles $1 \times r$. ($P_2$)
Á partir des deux premières propriétés, nous savons que nous avons $m-(n-1) = \frac{(n-1)(n-2)}{2}$ cores scalaires ou identités

Nous utilisons la formule (5.2.20) pour constater que les cores identités sont :

$$
\underbrace{G_i^{1,i+1}[z_i], G_i^{1,i+2}[z_i], \dots, G_i^{1,n}[z_i]}_{n-i}, \underbrace{G_i^{2,i+1}[z_i], G_i^{2,i+2}[z_i], \dots, G_i^{2,n}[z_i]}_{n-i}, \dots \underbrace{G_i^{i-1,i+1}[z_i], \dots, G_i^{i-1,n}[z_i]}_{n-i}
$$

Donc, il y aurait tout simplement $(i-1)(n-i)$ cores identités. ($P_3$)

* Á partir de $P_1$, $P_2$ et $P_3$, nous aurons $\frac{(n-1)(n-2)}{2} - i(n-i)$ cores de tailles $1 \times 1$. $P_4$

☐

Á partir de cette propriété, nous pouvons déduire les tailles des matrices.

**Corollaire 6.** *Les matrices $A_i[Z_i]$ et $B_i$ sont de tailles $r^{(i-1)(n-i+1)} \times r^{(i)(n-i)}$.*

Démonstration. On utilise la proposition 9 pour déterminer la taille des matrices $A_i[z_i]$. En
effet, comme ces matrices sont formées par les produits de $i-1$ cores de tailles $1 \times r$, $n-i$ cores
de tailles $r \times 1$ et $(i-1)(n-i)$ cores de tailles $r \times r$.

Alors la taille de $A_i[z_i]$ est :

$$
r^{(i-1)+(i-1)(n-i)} \times r^{(n-i)+(i-1)(n-i)}
$$

Ainsi, les $A_i[z_i]$ sont de tailles $r^{(i-1)(n-i+1)} \times r^{(i)(n-i)}$.

Donc, comme $B_i = \sum z_i A_i[z_i]$,
Alors $B_i$ sont de tailles $r^{(i-1)(n-i-1)} \times r^{(i)(n-i)}$.

☐

**Remarque 7.** *Quelques remarques par rapport aux tailles des matrices :*

* $A_1[z_1]$ et $B_1$ sont des vecteurs de tailles $1 \times r^{(n-1)}$.

* $A_n[z_n]$ et $B_n$ sont des vecteurs de tailles $r^{(n-1)} \times 1$.

* Les matrices $A_i[z_i]$ et $B_i$ sont de tailles exponentielles, il est donc difficile de les stocker et les manipuler.
### 5.2.6 Réécriture de la procédure dans le format tenseur train

Une manière possible de traiter ce type de matrices est de les traiter comme des matrices creuses [GVL96], cependant les tailles de ces matrices restent imenses.

Oseledets [Ose11] a développé les méthodes pour manipuler ces matrices grâce à la tensorisation (quantisation) qui permet de les écrire sous la forme de TT-matrices que nous avons présentées dans la définition 4.4.2 dans la section 4.4.2. Cette méthode nous permet de stocker ces matrices de tailles $O(r^n \times r^n)$ en $O(n^2Qr^2)$.

Dans ce qui va suivre, nous expliquerons comment faire les calculs dans ce format.

**NB** : Dans cette section, nous allons suivre la même numérotation des étapes que les sections précédentes. De plus, nous noterons les tenseurs en gras et en majuscule.

À partir de l'étape 4, nous manipulerons les matrices $A_i[z_i]$ sous format TT (TT-matrices) que nous avons présenté dans la définition 4.4.2.

**Objectif** : Passage du format matriciel de $A_i[z_i]$ à un format TT matrice. C'est-à-dire l'écriture de ces matrices sous la forme que nous avons définie durant la section 4.4.2

$$ \begin{gathered} \forall \mathbf{i} \in [1, r^{(i-1)(n-i+1)}] = (i_1, \dots, i_m), \quad \mathbf{j} \in [1, r^{i(n-i)}], \quad h \in [1, m] = (j_1, \dots, j_m), \\ A_i[z_i](\mathbf{i}, \mathbf{j}) = A_i[z_i](i_1, \dots, i_m; j_1, \dots, j_m) = \mathbf{G}_i^{1,2}[z_i](i_1, j_1) \mathbf{G}_i^{1,3}[z_i](i_2, j_2) \dots \mathbf{G}_i^{n-1,n}[z_i](i_m, j_m) \end{gathered} $$

Nous utilisons la fonction définie dans la formule (5.2.7) et nous exprimons $e$ comme la solution de :

$$ e = \zeta(k, \ell) $$

Alors,

$$ \left| \begin{array}{llll} i < k & \Rightarrow & \mathbf{G}_i^{k,l}[z_i](i_e, j_e) = 1 & \in \mathbb{R} & i_e = 1, \dots, r \\ i = k & \Rightarrow & \mathbf{G}_i^{k,l}[z_i](i_e, j_e) = G_i^{i,l}[z_i] & \in \mathbb{R}^{1 \times r} & i_e = 1, \dots, r \\ k < i < \ell & \Rightarrow & \mathbf{G}_i^{k,l}[z_i](i_e, j_e) = \mathbb{I}_{r,r} & \in \mathbb{R}^{r \times r} & i_e = 1, \dots, r, j_e = 1, \dots, r \\ i = l & \Rightarrow & \mathbf{G}_i^{k,l}[z_i](i_e, j_e) = G_i^{k,l}[z_i] & \in \mathbb{R}^{r \times 1} & i_e = 1, \dots, r, j_e = 1 \\ i > \ell & \Rightarrow & \mathbf{G}_i^{k,l}[z_i](i_e, j_e) = 1 & \in \mathbb{R} & i_e = 1, \dots, r, j_e = 1 \end{array} \right. \quad (5.2.21) $$

Si nous écrivons chaque coefficient de cette TT-matrice comme une contraction de tenseurs $\mathbf{G}_i^{k,l}[z_i]$ d'ordre 4 comme présenté dans 4.4.2 (les deux formes, matricielles et tensorielles, sont équivalents), nous obtenons :

$$ \mathbf{A}_i[z_i] = \mathbf{G}_i^{1,2}[z_i] \bullet_{\alpha_1} \mathbf{G}_i^{1,3}[z_i] \bullet_{\alpha_2} \dots \bullet_{\alpha_{d-2}} \mathbf{G}_i[z_i]^{n-2,n} \bullet_{\alpha_{d-1}} \mathbf{G}_i[z_i]^{n-1,n} \quad (5.2.22) $$

En le développant selon les quatre indices, nous obtenons pour chaque coefficient :

$$ \mathbf{A}[z_i][i_1, \dots, i_d; j_1, \dots, j_d] = \sum_{\alpha_1=1}^{r_1} \dots \sum_{\alpha_{d-1}=1}^{r_{d-1}} \mathbf{G}_i^{1,2}[z_i](1, i_1, j_1, \alpha_1) \mathbf{G}_i^{1,3}[z_i](\alpha_1, i_2, j_2, \alpha_2) \dots \mathbf{G}_i[z_i]^{n-2,n}(\alpha_{m-2}, i_{m-1}, j_{m-1}, \alpha_{m-1}) \mathbf{G}_i[z_i]^{n-1,n}(\alpha_{m-1}, i_m, j_m, 1) \quad (5.2.23) $$

$$ \text{Avec,} \quad \left| \begin{array}{llll} i < k & \Rightarrow & \mathbf{G}_i^{k,l}[z_i] = 1 & \in \mathbb{R}^{1 \times 1 \times 1 \times 1} \\ i = k & \Rightarrow & \mathbf{G}_i^{k,l}[z_i] = G_i^{i,l}[z_i] & \in \mathbb{R}^{1 \times 1 \times r \times 1} \\ k < i < \ell & \Rightarrow & \mathbf{G}_i^{k,l}[z_i] = \mathbb{I}_{r,r} & \in \mathbb{R}^{1 \times r \times r \times 1} \\ i = l & \Rightarrow & \mathbf{G}_i^{k,l}[z_i] = G_i^{k,l}[z_i] & \in \mathbb{R}^{1 \times 1 \times r \times 1} \\ i > \ell & \Rightarrow & \mathbf{G}_i^{k,l}[z_i] = 1 & \in \mathbb{R}^{1 \times 1 \times 1 \times 1} \end{array} \right. \quad (5.2.24) $$
Ces TT-matrices $A_i[z_i]$ sont de rang 1.

* **Étape 1 : Tensorisation des quantités $G_i^{i,j}$ et $G_j^{i,j}$** : Cette étape s'appuie sur l'étape 1 de la section 5.2.4. En effet, après le calcul de la SVD, nous obtenons $G_i^{i,j} \in \mathbb{R}^{Q \times r}$ et $G_j^{i,j} \in \mathbb{R}^{r \times Q}$.

Durant cette étape, nous faisons la transformation de ces matrices en tenseur afin de créer les premiers cores des TT-matrices $A_i[z_i]$ comme nous avons expliqué dans la section 4.4.2.

$$ G_i^{i,j} \in \mathbb{R}^{1 \times Q \times r \times 1} \quad \text{et} \quad G_j^{i,j} \in \mathbb{R}^{1 \times r \times Q \times 1} \qquad (5.2.25) $$

Avec,

$$ G_i^{i,j}[z_i] \in \mathbb{R}^{1 \times 1 \times r \times 1} \quad \text{et} \quad G_j^{i,j}[z_j] \in \mathbb{R}^{1 \times r \times 1 \times 1} \qquad (5.2.26) $$

Dans ce format,

$$ \overbrace{\psi'_{i,j}[z_i, z_j]}^{\in \mathbb{R}} = \underbrace{G_i^{i,j}(1, z_i, \cdot, 1)}_{\in \mathbb{R}^{1,r}} \underbrace{G_j^{i,j}(1, \cdot, z_j, 1)}_{\in \mathbb{R}^{r,1}} \qquad (5.2.27) $$

* **Étape 2 : Tensorisation des dimensions non essentielles** : L'implémentation de la manière avec laquelle se fait le rajout des dimensions non essentielles s'appuie sur l'étape 2 de la section 5.2.4 où nous faisons l'ajout des dimensions non essentielles. Puis, pour tous les tuples $\{i,j,k\} \in [1,n]^3$, nous transformons les matrices $G_k^{ij}$ en tenseurs $G_k^{ij}$.

Ainsi, nous aurons :

$$ \overline{\psi'_{i,j}}(z_i, z_j) = \prod_{k=1}^{n} G_k^{i,j}(z_k) \qquad (5.2.28) $$

Á partir de la formule (5.2.24), nous obtenons les dimensions des cores :

$$ \overbrace{\overline{\psi'_{i,j}}(z_i, z_j)}^{\in \mathbb{R}} = \underbrace{G_1^{ij}(1, 1, z_1, 1)}_{\in \mathbb{R}} \dots \underbrace{G_{i-1}^{ij}(1, 1, z_{i-1}, 1)}_{\in \mathbb{R}} \underbrace{G_i^{i,j}(1, z_i, \cdot, 1)}_{\in \mathbb{R}^{1,r}} \\ \underbrace{\mathbf{I}_{1,r,Q,r}(1, \cdot, z_{i+1}, \cdot)}_{\mathbb{R}^{r \times r}} \dots \underbrace{\mathbf{I}_{1,r,r,Q}(1, \cdot, z_{j-1}, \cdot)}_{\mathbb{R}^{r \times r}} \underbrace{G_j^{i,j}(1, \cdot, z_j, 1)}_{\in \mathbb{R}^{r,1}} \underbrace{G_{j+1}^{ij}(1, z_{j+1}, 1, 1)}_{\in \mathbb{R}} \dots \underbrace{G_n^{ij}(1, z_n, 1, 1)}_{\in \mathbb{R}} \qquad (5.2.29) $$

Avec,

$$ \mathbf{I}_{1,r,Q,r}(1, \cdot, Z_i = k, \cdot) = \mathbb{I}_{r,r} \qquad (5.2.30) $$

Les transformations en tenseurs des matrices $G_k^{ij}$ présentées dans (5.2.17) s'exprime :

$$ \left| \begin{array}{ll} k < i & \Rightarrow \mathbf{G}_k^{ij} = \underbrace{(1, \dots, 1)}_{\text{Q lignes}} \in \mathbb{R}^{1 \times 1 \times Q \times 1} \\ k = i & \Rightarrow \mathbf{G}_i^{ij} = \mathbf{G}_i^{ij} \in \mathbb{R}^{1 \times Q \times r \times 1} \\ i < k < j & \Rightarrow \mathbf{G}_k^{ij} = \mathbf{I}_{1,r,Q,r} \in \mathbb{R}^{1 \times r \times Q \times r} \\ k = j & \Rightarrow \mathbf{G}_j^{ij} = \mathbf{G}_j^{ij} \in \mathbb{R}^{1 \times r \times Q \times 1} \\ k > j & \Rightarrow \mathbf{G}_k^{ij} = \underbrace{(1, \dots, 1)}_{\text{Q lignes}} \in \mathbb{R}^{1 \times Q \times 1 \times 1} \end{array} \right. \qquad (5.2.31) $$

* **Étape 4 : Calcul des TT-matrices intermédiaires $A_i[z_i]$ et $B_i$** : Durant l'étape 4 de la section 5.2.4, nous avons exprimé les $A_i[z_i]$ sous format matriciel. Dans cette étape, nous
allons les exprimer sous format tensoriel. Pour chaque individu $i \in [1,n]$, nous construisons les TT-matrices $A_i[z_i]$ à partir des $m$ cores $[G^{1,2}[z_i]G^{1,3}[z_i]\dots G^{n-1,n}[z_i]]$

Ainsi, les TT-matrices s'expriment :

$$A_i[z_i](i_1, \dots, i_m; j_1, \dots, j_m) = G^{1,2}[z_i](i_1, j_1)G^{1,3}[z_i](i_2, j_2)\dots G^{n-1,n}[z_i](i_m, j_m) \quad (5.2.32)$$

Ce format nous permettrait de stocker les matrices $A_i[z_i]$ dont les tailles $r^{(i-1)(n-i-1)} \times r^{(i)(n-i)}$ présentées lors du corollaire en $mQr^2$.

Enfin, les $B_i$ s'expriment :

$$B_i = \sum_{z_i} A_i[z_i] \qquad (5.2.33)$$

### Remarques :

* Les TT-matrices $A_i[z_i]$ et $B_i$ sont des tenseurs d'ordres m.

* $A_1[z_1]$ et $A_n[z_n]$ sont des TT-vecteurs de rang 1.

* $B_1$ et $B_n$ sont des TT-vecteurs de rang $Q$.

* Les TT-matrices $(A_i[z_i])_{i=2,\dots,n-1}$ sont des TT-matrice de rang 1.

* Les TT-matrices $(B_i)_{i=2,\dots,n-1}$ sont les sommes des $A_i[z_i]$, elles sont des TT-matrices de rang $Q$ comme expliqué dans la propriété 3 de la section 4.1.2 du chapitre 4.

* **Étape 5 : Calcul de la constante de normalisation et des marginales :** Les calculs des trois quantités suivantes se font par produits de TT-matrices d'ordre $m$. Comme nous l'avons présenté dans la propriété 2 de la section 4.1.2 du chapitre 4, les résultats des marginales et de la constante de normalisation sont TT-matrices d'ordres $m$.

* **Constante de normalisation :**

$$W = B_1 \dots B_n$$

* **Marginales unaires :** $\forall i \in [1,n]$, $i \neq j$

$$p_i(z_i) = B_1 \dots B_{i-1} A_i[z_i] B_{i+1} \dots B_n$$

* **Marginales binaires :** $\forall i, j \in [1,n]^2$,

$$p_{i,j}(z_i, z_j) = B_1 \dots B_{i-1} A_i[z_i] B_{i+1} \dots B_{j-1} A_j[z_j] B_{j+1} \dots B_n$$

* **Étape 6 : Passage du format TT aux formats adéquats :** nous avons précisé dans la remarque 10 que $A_1[z_1]$ et $A_n[z_n]$ $B_1$ et $B_n$ sont des TT-vecteurs. Alors, tous les calculs présentés lors de l'étape 5 seront des produits matrices vecteurs. Nous notons :

$$W^i = B_1 \dots B_i$$

Comme $B_1$ est un TT-vecteur, alors $W^i$ sera un TT-vecteur. Si nous faisons une généralisation, $W^{n-1}$ sera un TT-vecteur.

On a :

$$W = W^{n-1}B_n$$

Comme $B_n$ est un TT-vecteur, alors $W$ est un TT-vecteur de rang 1 comme présenté dans les propositions sur les TT-vecteurs.

Nous pouvons donc l'exprimer comme la formule (4.4.5) qu'on a expliqué dans la section 4.1.2 du chapitre 4. Ainsi,

$$W[i_1, \dots, i_m] = G_1^W(i_1) \dots G_m^W(i_m)$$
De plus, comme **W** est de TT-rang 1, alors : $\forall k \in [1, m]$, $i_k = 1$. Et donc **W** est un tenseur d'ordre *m* avec un seul élément. En effet, nous pouvons réaliser que :

$$ \mathbf{W}[i_1, \dots, i_m] = \mathbf{W}[1, \dots, 1] = \underbrace{\mathbf{G}_1^\mathbf{W}(1)}_{\in \mathbb{R}^{1 \times 1 \times r_1 \times 1}} \cdot \underbrace{\mathbf{G}_2^\mathbf{W}(1) \dots \mathbf{G}_{m-1}^\mathbf{W}(1)}_{\in \mathbb{R}^{1 \times r_{k-1} \times r_k \times 1}} \cdot \underbrace{\mathbf{G}_m^\mathbf{W}(1)}_{\in \mathbb{R}^{1 \times r_{m-1} \times 1 \times 1}} $$

Donc, nous pouvons exprimer la constante de normalisation comme un réel. Cette procédure peut se généraliser pour les marginales unaires et binaires.

### 5.2.7 Implémentation de l'approche :

**Nécessité du rounding pour les calculs :** Les calculs des marginales ou la constante de normalisation nécessitent un produit de TT-matrices TT-vecteurs. Or, nous avons expliqué durant 2 que le rang de la TT-matrices résultante augmente.

Comme nous faisons *n* produit de ce type, les rangs augmenteront de manière exponentielle. Il est donc nécessaire de faire une recompression du résultat à chaque itération via une procédure de compression par le rounding présentée dans la sous-section rounding.
Les calculs se feront de cette manière :

$$ \mathbf{W} = \text{rounding}(\text{rounding}(\dots \text{rounding}(\mathbf{B}_1 \times \mathbf{B}_2, \epsilon) \times \dots \times \mathbf{B}_{n-1}, \epsilon) \times \mathbf{B}_n, \epsilon) $$

Dans ce cas, le calcul de la constante de normalisation est calculée de cette manière :

* $\mathbf{W}_1 = \mathbf{B}_1$

* Pour $i = 2, \dots, n$ :

* $\mathbf{W}_i = \mathbf{W}_{i-1} \times \mathbf{B}_i$

* $\mathbf{W}_i = \text{rounding}(\mathbf{W}_i, \epsilon)$

* $\mathbf{W} = \mathbf{W}_n$

**Implémentation des calculs de droite à gauche :** Les librairies permettant le calcul via des Tenseurs Trains sont plus adaptés pour des calculs TT-matrices-TT-vecteurs que pour des calculs TT-vecteurs-TT-matrices.

Nous avons donc adapté notre implémentation des calculs en partant de la droite vers la gauche.
C'est-à-dire :

$$ \mathbf{W} = \text{rounding}(\mathbf{B}_1 \times \text{rounding}(\mathbf{B}_2 \times \dots \times \text{rounding}(\mathbf{B}_{n-1} \times \mathbf{B}_n, \epsilon), \epsilon), \epsilon) $$

Dans ce cas, le calcul de la constante de normalisation est calculée de cette manière :

* $\mathbf{W}_n = \mathbf{B}_n$

* Pour $i = n-1, \dots, 1$ :

* $\mathbf{W}_i = \mathbf{B}_i \times \mathbf{W}_{i+1}$

* $\mathbf{W}_i = \text{rounding}(\mathbf{W}_i, \epsilon)$

* $\mathbf{W} = \mathbf{W}_1$
## 5.3 Méthode de calcul des marginales via une mutualisation des calculs

Dans la librairie TT-MRF, Novikov et al. [NROV14] utilisent le message passing [YFW03] qui consiste à calculer l'ensemble des produits : $\forall i \in [1, n]$, $\mathbf{B}_{i+1} \times \dots \times \mathbf{B}_n$ et $\mathbf{B}_1 \times \dots \times \mathbf{B}_{i-1}$ puis les utilisent pour le calcul des marginales unaires.

Dans ce qui va suivre, nous présentons une approche similaire pour le calcul des marginales binaires. Nous rappelons auparavant l'approche pour le calcul des marginales unaires.

### 5.3.1 Calcul des marginales unaires

Soit un modèle SBM de paramètres $n$, $\Lambda$, $\alpha$ et $Q$. Nous appliquons la procédure de l'approche TT et nous obtenons les TT-matrices $\forall i \in [1, n]$, $\mathbf{A}_i[z_i]$ et $\mathbf{B}_i$.

Nous prenons par exemple $i \in [1, n-2]$. Le calcul des marginales unaires de $i$, $i+1$ et $i+2$ s'exprime ainsi :

$$ 
\begin{align} 
\mathbf{p}_i(z_i) &= \mathbf{B}_1 \times \dots \times \mathbf{B}_{i-1} \times \mathbf{A}_i[z_i] \times \mathbf{B}_{i+1} \times \dots \times \mathbf{B}_n \nonumber \\
\mathbf{p}_{i+1}(z_{i+1}) &= \mathbf{B}_1 \times \dots \times \mathbf{B}_i \times \mathbf{A}_{i+1}[z_{i+1}] \times \mathbf{B}_{i+2} \times \dots \times \mathbf{B}_n \tag{5.3.1} \\
\mathbf{p}_{i+2}(z_{i+2}) &= \mathbf{B}_1 \times \dots \times \mathbf{B}_{i+1} \times \mathbf{A}_{i+2}[z_{i+2}] \times \mathbf{B}_{i+3} \times \dots \times \mathbf{B}_n \nonumber
\end{align} 
$$

Les calculs de ces trois marginales unaires pour les individus $i$, $i+1$ et $i+2$ font appels aux deux mêmes ensembles de produits de matrices : $\mathbf{L}_i = \mathbf{B}_1 \times \dots \times \mathbf{B}_{i-1}$ et $\mathbf{R}_{i+2} = \mathbf{B}_{j+3} \times \dots \times \mathbf{B}_n$. Nous pouvons réécrire les calculs (5.3.1) comme :

$$ 
\begin{align} 
\mathbf{p}_i(z_i) &= \mathbf{L}_i \mathbf{A}_i[z_i] \mathbf{B}_{i+1} \mathbf{B}_{i+2} \mathbf{R}_{i+2} \nonumber \\
\mathbf{p}_{i+1}(z_{i+1}) &= \mathbf{L}_i \mathbf{B}_i \mathbf{A}_{i+1}[z_{i+1}] \mathbf{B}_{i+2} \mathbf{R}_{i+2} \tag{5.3.2} \\
\mathbf{p}_{i+2}(z_{i+2}) &= \mathbf{L}_i \mathbf{B}_i \mathbf{B}_{i+1} \mathbf{A}_{i+2}[z_{i+2}] \mathbf{R}_{i+2} \nonumber
\end{align} 
$$

Il est donc inutile de calculer trois fois les produits $\mathbf{L}_i$ et $\mathbf{R}_{i+2}$. Plus généralement, chaque marginale unaire se décompose en un produit de matrices avec une partie droite et une partie gauche :

$$ \forall i \in [1, n], \quad \mathbf{p}_i(z_i) = \underbrace{\mathbf{B}_1 \times \dots \times \mathbf{B}_{i-1}}_{\text{left}} \mathbf{A}_i[z_i] \underbrace{\mathbf{B}_{i+1} \times \dots \times \mathbf{B}_n}_{\text{right}} \quad (5.3.3) $$

On peut donc exprimer les marginales unaires de cette manière :

$$ \mathbf{p}_i(z_i) = \mathbf{L}_i \times \mathbf{A}_i[z_i] \times \mathbf{R}_i \quad (5.3.4) $$

Les parties gauches $\mathbf{L}_i$ et droites $\mathbf{R}_i$ peuvent chacune se calculer par récurrence pour tout $i \in [1, n]$ selon les schémas :

$$ \left\{ \begin{array}{l} \mathbf{L}_1 = 1 \in \mathbb{R} \\ \mathbf{L}_{i+1} = \mathbf{L}_i \mathbf{B}_i \quad \forall i \in [2, n] \end{array} \right. \quad (5.3.5) $$

et

$$ \left\{ \begin{array}{l} \mathbf{R}_n = 1 \\ \mathbf{R}_i = \mathbf{B}_{i+1} \mathbf{R}_{i+1} \quad \forall i \in [1, n-1] \end{array} \right. \quad (5.3.6) $$
Nous remarquons alors que le calcul de toutes les matrices $\mathbf{L}_i$ et $\mathbf{R}_i$ pour $i \in [1, n]$ permet le calcul de toutes les marginales unaires selon la formule 5.3.4 et nécessite $2(n-1)$ produits matriciels seulement. Il en faut donc $2(n-1)+2nQ \sim 2nQ$ pour le calcul de toutes les marginales unaires.

Cette organisation des calculs est connue sous le nom de "message passing", et est efficace dans un cadre plus large de calcul simultané de toutes les marginales pour des lois jointes de modèles graphiques dont le graphe est un arbre [YFW03].

Nous étendons cette approche au calcul de toutes les marginales binaires d'un modèle SBM.

### 5.3.2 Calcul des marginales binaires

Nous prenons par exemple le couple $(i, j)$. Les calculs des marginales binaires de manière directe s'expriment :

$$ \mathbf{p}_{i,j}(z_i, z_j) = \mathbf{B}_1 \times \dots \times \mathbf{B}_{i-1} \times \mathbf{A}_i[z_i] \times \mathbf{B}_{i+1} \times \dots \times \mathbf{B}_{j-1} \mathbf{A}_j[z_j] \mathbf{B}_{j+1} \times \dots \times \mathbf{B}_n \quad (5.3.7) $$

Nous constatons que chaque marginale binaire se décompose en une partie droite, une partie centrale et une partie gauche : $\forall i, j \in [1, n]^2 \forall z_i, z_j \in [1, Q]^2$

$$ \mathbf{p}_{i,j}(z_i, z_j) = \underbrace{\mathbf{B}_1 \times \dots \times \mathbf{B}_{i-1}}_{\text{left}} \times \mathbf{A}_i[z_i] \times \underbrace{\mathbf{B}_{i+1} \times \dots \times \mathbf{B}_{j-1}}_{\text{center}} \times \mathbf{A}_j[z_j] \times \underbrace{\mathbf{B}_{j+1} \times \dots \times \mathbf{B}_n}_{\text{right}} \quad (5.3.8) $$

Il existe une partie droite $\mathbf{R}_j$ qui ne dépend que de $j$, une partie gauche $\mathbf{L}_i$ qui ne dépend que de $i$ et une partie centrale $\mathbf{C}_{i,j}$ qui dépend du couple $(i, j)$.

$$ \mathbf{p}_{i,j}(z_i, z_j) = \mathbf{L}_i \times \mathbf{A}_i[z_i] \times \mathbf{C}_{i,j} \times \mathbf{A}_j[z_j] \times \mathbf{R}_j \quad (5.3.9) $$

Les parties gauches $\mathbf{L}_i$ et droites $\mathbf{R}_i$ peuvent chacune se calculer par récurrence pour tout $i \in [1, n]$ selon les schémas (5.3.5) et (5.3.6). La partie centrale s'exprime :

$$ \forall i \in [1, n-2], j \in [i+2, n] \quad \mathbf{C}_{i,j} = \mathbf{B}_{i+1} \times \dots \times \mathbf{B}_{j-1} \quad (5.3.10) $$

### 5.3.3 Organisation des calculs sur un arbre

Le calcul indépendant de tous les $C_{ij}$ selon la formule (5.3.10) est très coûteux en termes de produits matriciels. Cependant, si nous connaissons par exemple $\mathbf{C}_{1,4}$, il est simple de calculer $\mathbf{C}_{1,5}$ avec un seul produit matriciel car $\mathbf{C}_{1,5} = \mathbf{C}_{1,4} \times \mathbf{B}_5$. Nous présentons dans ce qui suit une systématisation de cette propriété pour optimiser les calculs de toutes les marginales binaires. Pour cela, nous définissons les quantités $\mathbf{G}$ :

$$ \forall i \in [1, n-1], j \in [i+1, n], \quad \mathbf{G}_{i,j} = \mathbf{B}_i \times \mathbf{B}_{i+1} \times \dots \times \mathbf{B}_{j-1} \times \mathbf{B}_j \quad (5.3.11) $$

Ces quantités permettront de calculer simultanément les parties $\mathbf{R}_i$, $\mathbf{L}_j$ et $\mathbf{C}_{i,j}$ en organisant la récurrence des calculs sur un arbre. Un tel arbre est illustré dans la figure 5.2 dans le cas $n=5$.
<figure><img src="image_18.png" /><figcaption>FIGURE 5.2 – Décomposition des calculs des parties centrales de l’expression des marginales binaires</figcaption></figure>

**Explication de l'arbre** : Chaque nœud interne de cet arbre représente une matrice $G_{i,j}$, les feuilles sont les matrices $B_i$. Chaque nœud $G_{i,j}$ a deux parents : $G_{i,j-1}$ et $B_j$. Il est alors le produit de ses parents. Le calcul sur l'ensemble de l'arbre se fait par récurrence en partant des feuilles. Nous représentons la succession des calculs sur la figure 5.2 par des couleurs : les calculs se font dans l'ordre noir, orange, jaune et bleue. In fine, la racine de l'arbre représente la constante de normalisation $W$.

La récurrence selon le parcours de l'arbre des feuilles à la racine s'écrit :

$$ \left\{ \begin{array}{ll} \mathbf{G}_{i,i} = \mathbf{B}_i & \forall i \in [1, n-1] \\ \mathbf{G}_{i,j+1} = \mathbf{G}_{i,j} \times \mathbf{B}_{j+1} & \forall j \in [i+1, n] \end{array} \right. \qquad (5.3.12) $$

qui permet le calcul de toutes les parties centrales de l'expression des marginales binaires. En effet, à partir de (5.3.10) et (5.3.11), nous pouvons exprimer les parties centrales $C_{i,j}$ à partir de $G_{i,j}$ selon

$$ \forall i \in [1, n-1], j \in [i+1, n] \qquad \mathbf{C}_{i,j} = \mathbf{G}_{i+1,j-1} \qquad (5.3.13) $$

De plus, nous obtenons les parties gauches $L_i$ et droites $R_i$ des formules (5.3.9) et (5.3.4) selon :
<figure><img src="image_19.png" /><figcaption>FIGURE 5.3 – Décomposition des calculs de la partie Gauche ($\mathbf{L}_i$) en bleu et la partie droite ($\mathbf{R}_j$) en orange de l’expression des marginales binaires</figcaption></figure>

soit,

$$ egin{cases} 
\mathbf{L}_1 = 1 \in \mathbb{R} \\
\mathbf{L}_2 = \mathbf{B}_1 \\
\mathbf{L}_{i+1} = \mathbf{G}_{1,i} \quad \forall i \in [3, n-1] 
\end{cases} 
\quad (5.3.14) $$

$$ egin{cases} 
\mathbf{R}_n = 1 \in \mathbb{R} \\
\mathbf{R}_{n-1} = \mathbf{B}_n \\
\mathbf{R}_{n-j} = \mathbf{G}_{j,n} \quad \forall i \in [2, n-1] 
\end{cases} 
\quad (5.3.15) $$

**Complexité des calculs sur l'arbre** Nous généralisons l'arbre de la figure 5.2 pour $n \in \mathbb{N}$ individus pour le calcul de tous les nœuds de l'arbre. Il faut calculer $n-1$ produits matriciels pour la première itération, $n-2$ produits matriciels pour la seconde itération, ... et un produit matriciel pour la dernière itération. Une itération $i \in [1, n-1]$ donnée nécessite le calcul de $n-i$ produits matriciels. Donc, l'ensemble des calculs nécessite $\pi_n$ produits matriciels, avec :

$$ \pi_n = \sum_{i=1}^{n-1} (n-i) = \frac{n(n-1)}{2} $$

Les marginales binaires se calculent selon :

$$ p_{i,j}(z_i, z_j) = \underbrace{\mathbf{L}_i \times \mathbf{A}_i[Z_i] \times \mathbf{C}_{i,j} \times \mathbf{A}_j[Z_j] \times \mathbf{R}_j}_{4 \text{ produits matriciels}} $$

Connaissant $\mathbf{L}_i$, $\mathbf{C}_{i,j}$ et $\mathbf{R}_j$, le calcul de l'ensemble des marginales binaires nécessite $2 \times n(n-1) \times Q^2$ produits matriciels.

Ainsi, le calcul de toutes les marginales nécessite $S_n$ produits matriciels, avec

$$ S_n = 2 \times n(n-1) \times Q^2 + \frac{n(n-1)}{2} = n(n-1) \left( 2Q^2 + \frac{1}{2} \right) \approx 2n(n-1)Q^2 \sim \mathcal{O}(n^2 Q^2) \quad (5.3.16) $$

## 5.4 Conclusion

Dans ce chapitre, nous avons en premier lieu présenté une déclinaison de la procédure présentée par Novikov et al. [NROV14] pour le calcul des marginales d'un modèle SBM. Ensuite, nous
avons présenté une procédure basée sur l'organisation des calculs de ces marginales sur un arbre
pour le calcul des marginales d'un SBM et qui peut se généraliser pour n'importe quel modèle
graphique avec des liens au plus binaires.

Dans le chapitre 6, nous calculerons des marginales unaires et binaires par l'intermédiaire de
l'approche TT avec l'organisation sur un arbre pour un modèle SBM avec des distances que
nous simulerons.

Nous évaluerons cette approche en comparant les résultats obtenus avec des résultats obtenus
par d'autres approches plus classiques.
# Chapitre 6

## Évaluation numérique des calculs des marginales d'un modèle SBM par l'approche TT

<table><caption>Table des matières</caption><tr><td>6.1</td><td>Introduction</td><td>76</td></tr><tr><td>6.2</td><td>Méthodes de calcul des marginales</td><td>77</td></tr><tr><td>6.2.1</td><td>Expression de la loi jointe</td><td>77</td></tr><tr><td>6.2.2</td><td>Méthode exacte par énumération</td><td>78</td></tr><tr><td>6.2.3</td><td>Échantillonneur de Gibbs</td><td>78</td></tr><tr><td>6.2.3.1</td><td>Principe de l'échantillonneur de Gibbs pour le calcul des marginales</td><td>78</td></tr><tr><td>6.2.3.2</td><td>Préparation</td><td>79</td></tr><tr><td>6.2.3.3</td><td>Mise en œuvre</td><td>79</td></tr><tr><td>6.2.4</td><td>Champ moyen</td><td>80</td></tr><tr><td>6.2.4.1</td><td>Principe du champ moyen</td><td>80</td></tr><tr><td>6.2.4.2</td><td>Mise en œuvre du champ moyen</td><td>80</td></tr><tr><td>6.3</td><td>Les six structures de réseaux à utiliser pour générer les graphes</td><td>84</td></tr><tr><td>6.4</td><td>Protocole pour l'évaluation de l'approche TT</td><td>87</td></tr><tr><td>6.4.1</td><td>Simulation des matrices de distances</td><td>87</td></tr><tr><td>6.4.2</td><td>Paramètres des méthodes</td><td>87</td></tr><tr><td>6.4.3</td><td>Visualisation des résultats</td><td>88</td></tr><tr><td>6.4.4</td><td>Présentation des résultats</td><td>88</td></tr><tr><td>6.5</td><td>Comparaison pour un nombre d'individus égal à 9</td><td>89</td></tr><tr><td>6.5.1</td><td>Associative</td><td>89</td></tr><tr><td>6.5.2</td><td>Hiérarchique</td><td>90</td></tr><tr><td>6.5.3</td><td>Ordonné</td><td>91</td></tr><tr><td>6.5.4</td><td>Dissociative</td><td>93</td></tr><tr><td>6.5.5</td><td>Cores periphery</td><td>94</td></tr><tr><td>6.5.6</td><td>Hiérarchique 2</td><td>95</td></tr><tr><td>6.5.7</td><td>Remarques sur le temps de calcul</td><td>97</td></tr><tr><td>6.6</td><td>Comparaison pour un nombre d'individus égal à 18</td><td>98</td></tr><tr><td>6.6.1</td><td>Associative</td><td>98</td></tr><tr><td>6.6.2</td><td>Hiérarchique</td><td>99</td></tr><tr><td>6.6.3</td><td>Ordonné</td><td>100</td></tr></table>
<table><tr><td>6.6.4</td><td>Dissociative</td><td>102</td></tr><tr><td>6.6.5</td><td>Cores periphery</td><td>103</td></tr><tr><td>6.6.6</td><td>Hiérarchique 2</td><td>104</td></tr><tr><td>6.6.7</td><td>Remarque sur le temps de calcul</td><td>106</td></tr><tr><td>6.7</td><td>Discussion</td><td>106</td></tr><tr><td>6.7.1</td><td>Résumé des résultats</td><td>106</td></tr><tr><td>6.7.2</td><td>Cohérence entre les différentes méthodes de calculs des marginales</td><td>107</td></tr><tr><td>6.7.3</td><td>Temps de calculs/ Précision :</td><td>108</td></tr><tr><td>6.7.4</td><td>Influence de la structure de distance :</td><td>108</td></tr><tr><td>6.8</td><td>Conclusion</td><td>108</td></tr><tr><td>6.8.1</td><td>Qualité de l'approche TT</td><td>108</td></tr><tr><td>6.8.2</td><td>Perspectives</td><td>108</td></tr></table>