Keywords: Best-in-class approach, ESG, Machine Learning, Portfolio Construction, Sustainable Investments Machine learning, Data mining, Interpretable models, Rule induction, Data-Dependent partitioning, Regression models

Enfin les remerciements, sans doute la partie la plus lue d'un manuscrit de thèse (à moins que je ne sois le seul à trouver cette littérature fascinante). Les gens qui m'ont entouré pendant cette thèse peuvent imaginer le soulagement que j'ai à écrire ces lignes. Ça y est, c'est terminé ! Je voulais d'abord grandement remercier mon directeur de thèse Olivier Wintenber et mon responsable industriel Christophe Geissler sans qui cette thèse n'aurait pas eu lieu. Merci à Olivier pour sa bienveillance, son soutien, ses encouragements et ses nombreuses relectures. Il a su me pousser lorsque c'était nécessaire et me rassurer dans les moments de doute. Merci à Christophe pour son soutien dans les creux de vagues et pour son enthousiasme dans les bons moments.

Je remercie également mes co-encradents Jean-Patrick Baudry et Frédéric Guilloux pour leur patience, leur disponibilité et leurs conseils. Merci à Jean-Patrick pour son sans du détail qui m'a poussé à beaucoup plus de rigueur. Et merci à Frédéric pour sa pédagogie pour m'expliquer en quoi ces détails étaient toujours importants.

Merci à Aurélien Garivier et Gilles Stoltz qui ont bien voulu rapporter cette thèse et qui, grâce à leurs remarques et questions, m'ont permis d'améliorer ce manuscrit et de préparer la soutenance dans d'excellentes conditions. Je tiens particulièrement à remercier Gilles pour m'avoir renvoyé mon manuscrit rempli d'annotations, remarques et questions ouvertes qui m'ont grandement servi.

Merci également à Gerard Biau et Madalina Olteanu d'avoir accepté de participer au jury de thèse. Merci pour leurs questions et remarques. J'espère qu'il y en aura d'autres.

J'aimerais, bien évidemment, remercier ma famille pour leurs encouragements et leurs soutiens sans failles et plus particulièrement ma femme, Camille, qui m'a soutenu tous les jours pendant cette thèse et sans qui je n'en serais pas là aujourd'hui.

Un très grand merci a tous mes amis. Merci à Clément et à Florian pour être toujours là en toutes circonstances et même le dimanche soir. Merci à François, Peupeu (non ce n'est pas son vrai nom), Pierre, Philippe-Alexandre (lui en revanche c'est son vrai nom) pour m'avoir donné le goût des mathématiques. Merci à Clémence et Anastasia pour leurs soutiens lors de ma soutenance, même si les mathématiques ne sont pas leur domaine.

Merci également à tous mes collègues d'Advestis Noureddine, Nicolas, David, William, Philippe et Adrien pour leurs encouragements. Un remerciement spécial pour Noureddine qui m'a supporté, sans jamais se plaindre, râler sans cesse sur le bureau d'en fasse.

Je voulais également remercier les personnes de l'ombre, ceux qui m'ont permi, sans même le savoir, d'entreprendre cette thèse. Julien Valletoux, mon responsable de stage de fin d'études, qui a cru en moi et m'avait conseillé d'aller chercher une thèse. Et Salim Khelifa, mon professer de topologie et de théorie de la mesure en L3, qui a été le premier enseignant à m'avoir montré ce que sont vraiment les mathématiques et à quel point elles pouvaient être belles.

Enfin je souhaite faire des non-remerciements à Reed Hastings et Marc Randolph (Netflix) ainsi qu'à François Theurel (le Fossoyeur de Films) et Renaud Jesionek (le Cap'tain du Nexus VI) qui m'ont pris beaucoup de temps mais ont quand même grandement contribué à enrichir ma culture cinématographique.

À partir de cette théorie, nous avons développé deux algorithmes. Le premier, Covering Algorithm (CA), est un algorithme rendant interprétable Random Forests (RF), un algorithme vu comme une boîte noire non-interprétable. L'algorithme extrait des règles obtenues par RF un recouvrement de règles significatives et insignifiantes. Le second, Rule Induction Covering Estimator (RICE), ne conçoit que des règles significatives et insignifiantes contrairement à (CA). RICE en sélectionne un petit ensemble pour former un recouvrement. Les règles significatives sont utilisées pour interpréter le modèle et le recouvrement permet de définir un estimateur de la fonction de régression qui, sous certaines conditions, est consistant. Enfin, une version open-source du code est disponible sur GitHub.

Résumé

Cette thèse a été motivée par la volonté de créer un algorithme interprétable en analyse de la régression. Dans un premier temps, nous nous sommes concentrés sur les algorithmes interprétables les plus courants : les algorithmes à bases de règles de décisions. Malheureusement, les conditions théoriques sur ces algorithmes engendrent une perte d'interprétabilité lorsque la dimension augmente. Partant du principe que moins il y a de règles, meilleure est l'interprétabilité, nous avons introduit une nouvelle famille d'algorithmes à base d'un petit nombre de règles dites significatives. Ce principe a été traduit en une mesure d'interprétabilité permettant la comparaison entre algorithmes générant des règles.

Nous avons ensuite introduit une nouvelle méthode pour générer des estimateurs interprétables de la fonction de régression. L'idée repose sur la notion de recouvrements des données. L'objectif est de construire à partir des données un recouvrement de l'espace des variables explicatives au lieu d'imposer une partition comme pour les algorithmes à bases de règles usuels. Chaque élément du recouvrement est sélectionné selon un critère de significativité ou d'insignifiance. Les éléments significatifs servent à décrire le modèle et les éléments insignifiants permettent d'obtenir un recouvrement. Une partition est construite à partir du recouvrement pour définir une prédiction. La méthode prédit la variable d'intérêt comme l'espérance conditionnelle empirique sur les cellules de la partition activées par les variables explicatives correspondantes. Ainsi, ces prédictions sont identiques à celles issues d'algorithmes de partitionnement dépendant des données et s'interprètent comme un minimiseur du risque empirique. Nous prouvons ainsi que de telles méthodes fournissent des estimateurs consistants de la fonction de régression sans utiliser la condition de rétrécissement des cellules qui apparaît dans la littérature. Ce faisant, nous réduisons le nombre d'éléments du recouvrement et nous améliorons l'interprétabilité du modèle obtenu.

Chapter 1 Introduction et contributions

En 1959 Arthur Samuel a défini le machine learning (ML) ou apprentissage automatique comme "The field of study that gives computers the ability to learn without being explicitly programmed." Le ML est une discipline charnière entre l'informatique pour la partie application et l'apprentissage statistique pour la partie théorique. Le but de cette discipline est de développer des algorithmes informatiques capables à partir d'un ensemble de données de prédire/décrire un phénomène. La construction et l'évaluation de ces algorithmes se fait en suivant des principes développés en théorie de l'apprentissage statistique. Les lecteurs curieux pourront consulter [50] pour une introduction et une revue des différentes techniques de ML et les ouvrages [START_REF] Vapnik | The nature of statistical learning theory[END_REF] et [START_REF] Hastie | The Elements of Statistical Learning[END_REF] pour des introductions détaillées de la théorie de l'apprentissage statistique.

Dans cette thèse nous nous intéressons à l'analyse de la régression : le statisticien dispose de données composées d'une variable d'intérêt Y à valeurs dans R et d'un ensemble de variables X ∈ R d , appelées variables explicatives, pouvant être utilisées pour expliquer la variable d'intérêt. L'objectif de cette analyse est d'être capable de prédire la valeur de la variable d'intérêt à partir de nouvelles observations des variables explicatives.

Le cadre général

Nous analysons la régression suivante : Soit (X, Y ) un couple de variables aléatoires de loi Q inconnue à valeurs dans

R d × R tel que Y = g * (X) + Z, (1.1)
avec E[Z] = 0, V(Z) = σ 2 > 0 et g * une fonction mesurable de R d dans R.

Nous faisons les hypothèses suivantes :

-Z est indépendante de X; L'objectif est d'être capable de prédire la variable Y sachant X. On note G l'ensemble des fonctions mesurables de R d dans R.

On observe un échantillon D n = ((X 1 , Y 1 ), . . . , (X n , Y n )), où les couples (X i , Y i ) sont indépendants et identiquement distribués (i.i.d) de loi Q. À partir de D n , on construit une fonction, appelée prédicteur,

g : (R d × R) n × R d → R D n ; x → g(D n , x).
Sauf ambiguïté, nous noterons, pour x ∈ R d , g n (x) = g(D n , x), g étant vue comme une fonction de G, aléatoire car dépendant de D n . La qualité d'un prédicteur est évaluée par la fonction de perte L : G → R définie par :

L(g) = E (X,Y )∼Q (g n (X) -Y ) 2 | D n (1.2)
Sauf ambiguïté, nous noterons E Q = E (X,Y )∼Q . L'objectif lors de la construction d'un prédicteur est qu'il ait la plus petite perte possible. Or on sait que le meilleur prédicteur, au sens de la perte (1.2) est la fonction de régression. En effet on a g * (X) = arg min

g∈G E Q (g(X) -Y ) 2 X = E [ Y | X] Q-p.s.
(1.3)

Pour plus de détail nous renvoyons à Hastie et al. [30, p. 18-22] ou encore Arlot and Celisse [2, p. 44]. Sachant que la perte minimale est atteinte pour g * il semble naturel d'introduire la notion d'excès de perte : G × G → R + . Elle est définie par (g * , g) = L(g) -L(g * ).

(1.4) L'utilisation de l'excès de perte permet de mettre en lumière le fait que vouloir construire le meilleur prédicteur et vouloir estimer la fonction de régression sont les mêmes objectifs. En effet nous avons la relation

(g * , g) = E Q (g(X) -g * (X)) 2
d'après le développement de la perte quadratique :

L (g) = E Q (g(X) -Y ) 2 = E Q (g(X) -g * (X) + g * (X) -Y ) 2 = E Q (g(X) -g * (X)) 2 + L(g * ) + 2E Q [(g(X) -g * (X)) (g * (X) -Y )] ,
le dernier terme de la somme étant nul car

E Q [(g(X) -g * (X)) (g * (X) -Y )] = E Q [E Q [(g(X) -g * (X)) (g * (X) -Y ) | X]] = E Q [(g(X) -g * (X)) (g * (X) -E Q [Y | X])] = 0 par (1.
3).

L'estimation de la fonction de régression

Pour construire un estimateur g n de g * à partir d'un échantillon D n , nous utilisons un algorithme statistique. L'échantillon et le choix de l'algorithme conditionnent la classe de fonctions G n ⊂ G à laquelle appartient l'estimateur g n . La qualité de l'algorithme est donc mesurée par la perte (1.2) de l'estimateur g n qu'il génère, et qui dépend de l'échantillon, mais également par le risque, notée R et défini par :

R (g * , g n ) = E Dn∼Q ⊗n [ (g * , g n )] .
(1.5)

Sauf ambiguïté, nous noterons E Q ⊗n = E Dn∼Q ⊗n .

L'estimateur peut être sélectionné dans G n comme étant le minimiseur de la perte empirique L n définie par

L n (g) = 1 n n i=1 (g(X i ) -Y i ) 2 . (1.6)
On a alors

g n ∈ arg min g∈Gn L n (g) (1.7)
Ce principe est appelé Empirical Risk Minimization (ERM) est a été introduit dans [START_REF] Vapnik | Estimation of Dependences Based on Empirical Data[END_REF]. Lorsque l'on étudie un estimateur on commence par s'assurer qu'il est universellement consistant, c'est-à-dire qu'il converge vers g * pour n → ∞ quelle que soit la loi Q. Nous rappelons les définitions de consistance d'un estimateur, présentées dans Györfi et al. [ Remarque 1. Ces deux définitions nous permettent de lier un des objectifs de l'estimation, la consistance, avec des objectifs de prédiction comme la minimisation du risque (dans la définition 1.1.1) ou la minimisation de l'excès de perte (dans la définition 1.1.2).

Algorithmes de régression

En statistique non-paramétrique une méthode usuelle pour construire un estimateur de la fonction de régression consiste à utiliser un algorithme par moyenne locale de la forme

g n (x) = n i=1
W n,i (x)Y i , avec W n,i (x) = W n,i (X 1 , . . . , X n ; x) ∈ R donne du poids aux indices i tels que X i est proche de x. On peut citer par exemple l'algorithme à noyau de Nadaraya-Watson [START_REF] Nadaraya | On estimating regression[END_REF] ou celui des k-plus proches voisins.

Dans cette thèse nous nous concentrons sur les algorithmes à partition. Ces algorithmes découpent, à chaque étape n, l'espace R d en une partition P n = {A 1,n , A 2,n , . . .} et l'estimateur généré peut s'écrire sous la forme précédente avec

W n,i (x) = 1 X i ∈An(x) n i=1 1 X i ∈An(x) , (1.8)
où A n (x) est la cellule de P n qui contient x.

Remarque 2. Cette idée peut être généralisée en relâchant l'hypothèse que la collection P n soit une partition : on peut considérer des collections P n de sous-ensembles de R d avec de possibles recouvrements et de possibles zones non couvertes. Dans ce cas, W n,i (x) peut ne pas être défini si aucune cellule ne contient x. On trouve souvent la convention 0/0 = 0. Cela peut se traduire par le fait qu'en l'absence d'information l'estimateur prédit 0. Mais cette convention peut être discutable. On pourrait se demander pourquoi ne pas prédire la moyenne empirique de Y si aucune cellule ne contient x ? Le problème de prédiction en l'absence d'information a été l'une des problématiques de cette thèse. La gestion des cas où les ensembles de P n se recouvrent mutuellement, en a été une autre.

Algorithme à partition indépendante des données

Un premier type d'algorithme à partition regroupe les algorithmes à partition ne tenant compte que de la taille n de l'échantillon D n . Le plus connu est le régressogramme [START_REF] Tukey | Curves as parameters, and touch estimation[END_REF]. Le théorème suivant, reposant sur les résultats de [START_REF] Stone | Consistent nonparametric regression[END_REF], donne des conditions suffisantes pour qu'un estimateur construit à partir d'un algorithme à partition soit faiblement universellement consistant. Ce théorème repose sur la notion de diamètre, notée diam et définie par :

diam(A) = sup{d(x, y); x ∈ A, x ∈ A}, où d est la distance euclidienne sur R d .

Théorème 1.1.1. Théorème de consistance faible, voir [28, Théorème 4.2] Soit g n un estimateur défini sur une partition P n = {A 1,n , A 2,n , . . .}. Si pour chaque sphère S centrée en l'origine on a :

• max

{j:A j,n ∩S =∅} diam(A j,n ) → 0 (n → ∞), (1.9)
• |{j : A j,n ∩ S = ∅}| n → 0 (n → ∞), (1.10)
alors R (g * , g n ) → 0 (n → ∞).

La première condition assure que les cellules de la partition tendent vers 0 dans un certain sens. Cette condition correspond à l'idée d'une estimation locale. La seconde traduit le fait que le nombre de cellules dans un ensemble borné est petit par rapport à n, ce qui permet d'assurer que chaque cellule contient plusieurs points de l'échantillon D n et ainsi d'avoir une meilleure estimation.

Exemple 1. Le régressogramme

Le régressogramme est un algorithme à partition où chaque cellule a un volume égal à (h n ) d une valeur dépendante de n mais indépendante de D n . La Figure 1.1 représente différentes partitions générées pour un échantillon D n de plus en plus grand. On remarque que cette partition a des cellules contenant un nombre de points très hétérogènes. Quid de la qualité de prédiction dans une cellule ne contenant qu'une seule observation ?

Néanmoins, d'après le théorème 1.1.1 la consistance d'un estimateur issu d'un régressogramme est vérifiée si h n vérifie que

h n → 0 (n → ∞) et n(h n ) d → ∞ (n → ∞).

Algorithmes à partition dépendant des données

Il existe un second type d'algorithmes qui construit une partition dépendant de D n . On parle alors d'estimation à partition dépendante des données [28,Chap 13]. Ces algorithmes permettent de construire un estimateur en utilisant deux fois l'échantillon D n . D'abord, pour construire une partition P n = P n (D n ) de l'espace des variables explicatives à partir des données. Puis, P n et D n sont utilisés pour construire l'estimateur g n en moyennant les Y i pour lesquels X i est proche de X, c'est-à-dire dans le même cellule de la partition (1.8).

Exemple 2. L'algorithme à partition cubique L'algorithme à partition cubique est comparable au régressogramme dans le sens où il partitionne l'espace des variables explicatives en cellules géométriquement identiques 1 . La différence est dans le fait que la taille des cellules est déterminée à partir de D n et d'un paramètre k.

Sans perdre de généralité nous supposons d = 2. L'algorithme partitionne un espace déterminé par un hyperrectangle [L n , R n ) 2 dépendant de D n . Soient k min (n) et k max (n) ∈ N * tels que k min (n) ≤ k max (n), dépendants uniquement de la taille de n. Le statisticien génère aléatoirement un k ∈ N tel que k min (n) ≤ k ≤ k max (n). L'algorithme fournit alors la partition suivante :

P n,k = R 2 \ [L n , R n ) 2 ∪ {[L n + i 1 h n,k , L n + (i 1 + 1)h n,k [×[L n + i 2 h n,k , L n + (i 2 + 1)h n,k [: i 1 , i 2 ∈ {0, . . . , k -1}} , avec h n,k = R n -L n k
la taille de la grille de la partition (voir la Figure 1.2). Exemple 3. L'algorithme à partition quantile L'algorithme à partition quantile est une variante de celui à partition cubique. Considérons le même jeux de données que pour l'exemple précédent. Tout comme l'algorithme à partition cubique, il partitionne un espace déterminé par un hyperrectangle [L n , R n ) 2 dépendant uniquement de n. Soit m n ∈ N choisi en fonction de n. L'algorithme construit une partition P n de [L n , R n ) 2 en utilisant les quantiles empiriques d'ordre m n de D n dans chaque dimension. On obtient alors une partition avec des hyperrectangles de taille variables (voir la Figure 1.3).

Exemple 4. L'algorithme à partition par blocs statistiquement équivalents

Le problème avec les partition précédentes c'est la possibilité d'avoir des cellules vides ce qui implique de devoir faire un choix pour la prédiction en l'absence d'information (cf la remarque 2). Pour palier à ce problème, on peut utiliser l'algorithme à partition par blocs statistiquement équivalents.

Considérons le même jeux de données que pour les exemples précédents. Soit k n ∈ N choisi en fonction de n. La partition P n construite par l'algorithme de partition par blocs statistiquement équivalents est telle que chaque cellule, sauf une, contient exactement k n points 2 . En pratique on utilise les quantiles empiriques pour identifier les intervalles (voir la Figure 1.4).

La complexité de l'algorithme peut être mesurée par une quantité combinatoire appelée nombre de partitionnement, introduit par [START_REF] Nobel | Histogram regression estimation using data-dependent partitions[END_REF] pour la régression et par [START_REF] Lugosi | Consistency of data-driven histogram methods for density estimation and classification[END_REF] pour la classification. Cette quantité est comparable à la fonction de croissance (ou coefficient de pulvérisation) présentée en 1971 par Vapnik et Chervonenkis pour les classes de sous-ensembles [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. Le nombre de partitionnement repose sur le nombre de partitions différentes qu'un algorithme peut générer indépendamment de D n . Pour cela on introduit Π n = P n ({(x 1 , y 1 ), . . . , (x n , y n )}) : (x 1 , y 1 ), . . . , (x n , y n ) ∈ R d × R , Définition 1.1.3. Soit Π n une famille de partitions de R d . Pour x n 1 = {x 1 , . . . , x n } ∈ (R d ) n on pose ∆(x n 1 , Π n ) le nombre de partitions distinctes de x n 1 engendrées par les éléments de Π n . Par distinctes on entend que l'ordre d'apparition n'importe pas. En d'autre terme ∆(x n 1 , Π n ) est égale au nombre des différentes partitions {x n 1 ∩ A : A ∈ P} de x n 1 pour P ∈ Π n . On a

∆(x n 1 , Π n ) = # {{x n 1 ∩ A : A ∈ P} : P ∈ Π n } .
Le nombre de partitionnement ∆ n (Π n ) est défini par :

∆ n (Π n ) = max {x 1 ,...,xn}∈(R d ) n ∆(x n 1 , Π n ).
Le nombre de partitionnement est le nombre maximum de partitions différentes de n'importe quel ensemble de n points, engendrées par les éléments de la partition issue de l'algorithme Π n .

Exemple 5. La partition quantile suite . . . Reprenons l'algorithme à partition quantile de l'exemple 3 et calculons M (Π n ) et ∆ n (Π n ). Chaque axe est découpée en m n parties. Ainsi, les partitions générées comportent au plus m 2 n cellules. Nous avons alors M (Π n ) = m 2 n . Le calcul de ∆ n (Π n ) est un peu plus délicat. Supposons d = 1 et soit x n 1 = (x 1 , . . . , x n ) ∈ R n . Sans perte de généralité nous supposons que x 1 < x 2 < • • • < x n . Pour avoir m n intervalles il faut m n -1 bornes. On note {b 1 , . . . , b mn-1 } ces bornes, telles que b 1 < b 2 < • • • < b mn-1 . On pose b 0 = -∞ et b mn = +∞. Nous allons compter le nombre de partitionnements différents de x n 1 avec p cellules non vides pour p ∈ {1, . . . , m n }. 1. Pour p = 1 il faut qu'il existe 0 ≤ j ≤ m n -1 tel que b j < x 1 et b j+1 > x n . Dans les deux cas le partitionnement de x n 1 sont les mêmes (tous les points dans une même cellule). Il y a donc une partition de x n 1 avec une cellule non vide. 2. Pour p = 2 nous obtenons le même partitionnement si pour un indice i ∈ {1, . . . , n-1} fixé il existe j ∈ {2, . . . , m n } tel que x i < b j < x i+1 . Il y a donc n -1 partitionnement de x n 1 avec 2 cellules non vides correspondant aux n -1 choix possibles du plus grand indice des points contenus dans le premier élément de la partition. 3. Suivons le même raisonnement pour un partitionnement avec p = 3 cellules non vides. Dans ce cas, il faut fixer un couple (i, j) avec 1 ≤ i < j ≤ n -1 tels que i soit le plus grand indice des points contenus dans le premier élément de la partition et j le plus grand indice des points contenus dans le second élément de la partition. On a n-1 2 partitionnement différents. 4. Et ainsi de suite pour p > 3 parties. En sommant les différents partitionnement de x n 1 avec 1 à m n cellules non vides on a

∆ n (Π n ) ≤ mn l=1 n -1 l -1 ,
où l représente le nombre de cellules non vides dans le partitionnement de x n 1 . Pour d > 1 on applique le même raisonnement suivant chaque axe et on obtient

∆ n (Π n ) ≤ mn l=1 n -1 l -1 d .
On remarque que cette borne n'est valable que pour une partition complète. Si les points peuvent n'appartenir à aucun élément de la partition alors seule la borne ∆ n (Π n ) ≤ n+mn mn d est valable.

Dans le théorème de consistance forte (voir Définition 1.1.2) pour les algorithmes à partition dépendante des données, présenté dans Nobel [START_REF] Nobel | Histogram regression estimation using data-dependent partitions[END_REF], on trouve deux conditions. La condition (1.12) requiert que la famille des partitions Π n , à laquelle appartient la partition utilisée pour g n , ne soit pas trop complexe. Cette complexité est contrôlée par le nombre maximal de cellules d'une partition de Π n et par le nombre de partitionnement ∆ n (Π n ) (cf. (1.12)). Et la condition (1.13) porte sur la partition choisie pour générer l'estimateur g n et impose que le diamètre des cellules rétrécisse et tende, d'une certaine façon, vers 0. Théorème 1.1.2. Théorème de consistance forte, voir Györfi et al. [28,Théorème 13.1] Si g n et Π n vérifient les conditions suivantes :

• M (Π n ) n ∨ log(∆ n (Π n )) n → 0 (n → ∞), (1.12)
• pour tout γ > 0 et δ ∈ (0, 1), inf

S:S⊂R d ,µ X (S)≥1-δ µ X ({x : diam(A n (x) ∩ S) > γ}) → 0 (n → ∞) p.s, (1.13)
avec µ X la marginal de X et A n (x) la cellule de la partition utilisée pour g n qui contient

x.

Alors (g * , g n ) → 0 (n → ∞) p.s.
Exemple 6. La partition quantile, suite et fin. Reprenons l'exemple 3, de l'algorithme à partition quantile. On note

L n ∈ R et R n ∈ R les bornes telles que [L n , R n ] 2 soit le plus petit hyperrectangle contenant les données. Si • R n → ∞, L n → -∞ (n → ∞), • m 2 n n → 0 (n → ∞), (1.14)
• log(n) m n → 0 (n → ∞), (1.15) • R n -L n m n → 0 (n → ∞), (1.16)
alors l'estimateur g n défini pour P n est universellement fortement consistant. La preuve est une application directe du théorème précédent. En effet il faut vérifier que l'estimateur, g n et P n vérifient les conditions. On sait, par l'exemple 5, que:

M (Π n ) = m 2 n , ∆(Π n ) ≤ n + m n m n 2 .
A partir de ces résultats et en utilisant (1.14) et (1.15), on peut montrer (1.12). En effet on a

∆ n (Π n ) ≤ n + m n m n 2 ≤ (n + m n ) 2mn ≤ (2n) 2mn .
Il reste donc (1.13) à montrer. Soit γ > 0 et δ ∈ (0, 1). Par (1.16) et pour n suffisamment grand on a

inf S:S⊂R 2 ,µ X (S)≥1-δ µ X ({x : diam(A n (x) ∩ S) > γ}) ≤ µ X x : diam(A n (x) ∩ [L n , R n ] 2 ) > γ ≤ µ X x : √ 2 R n -L n m n ≥ γ = µ X (∅) = 0.
Dans les deux théorèmes de consistance les conditions imposent un rétrécissement des cellules de la partition (la condition (1.9) pour le théorème 1.1.1 et la condition (1.13) pour le théorème 1.1.2). En d'autres termes, plus n augmente plus le nombre de cellules augmente. Sous ces conditions, les algorithmes à partition, conçus pour être simples à comprendre, génèrent de fait des estimateurs dont les cellules sont de moins en moins interprétables.

Remarques autour de la condition (1.13) 1. On peut remarquer dans un premier temps que cette condition est toujours vérifiée si X est une variable aléatoire discrète.

Preuve. Soit S ⊂ R d tel que µ X (S) ≥ 1 -δ. Étant donné que la condition est un infimum et que X est une variable aléatoire discrète on peut prendre S comme étant un singleton. Dans ce cas, quelque soit x ∈ R d on a que A n (x) ∩ S est égale, soit à S, soit à l'ensemble vide. Dans ces deux cas le diamètre de l'intersection est nul. Ce qui implique que l'ensemble {x : diam(A n (x) ∩ S) > γ} est l'ensemble vide, qui par définition est de mesure nulle.

2. La deuxième remarque consiste à faire le lien entre la condition (1.13) et la condition suivante:

diam(A n (x)) → 0 (n → ∞) p.s. (1.17)
Évidement on a (1.17) qui implique (1.13).

Preuve. Supposons (1.17) vraie et soit γ > 0. Alors:

(1.17) =⇒ ∀R ⊂ R d tel que µ X (R) > 0 p.s, diam(A n (x) ∩ R) → 0 (n → ∞) =⇒ ∀γ > 0 et ∀R ⊂ R d tel que µ X (R) > 0 p.s., {x : diam(A n (x) ∩ R) > γ} → ∅ (n → ∞) =⇒ ∀γ > 0 et ∀R ⊂ R d tel que µ X (R) > 0 p.s., µ X ({x : diam(A n (x) ∩ R) > γ}) → 0 (n → ∞).

De plus on a que pour tout

δ ∈ [0, 1], γ > 0 et R ⊂ R d tel que µ X (R) ≥ 1 -δ, inf S:S∈R d ,µ X (S)≥1-δ µ X ({x : diam(A n (x) ∩ S) > γ}) ≤ µ X ({x : diam(A n (x) ∩ R) > γ}) .
Donc si (1.17) est vraie, le terme de droite tend vers 0 donc (1.13) est vérifiée.

Ce qui est intéressant c'est de savoir dans quel cas (1.17) et (1.13) sont équivalentes. À la lumière de la preuve précédente on remarque que (1.17) et (1.13) sont équivalentes si et seulement si pour tout γ > 0 et δ ∈ (0, 1) on a :

inf S:S∈R d ,µ X (S)≥1-δ µ X ({x : diam(A n (x) ∩ S) > γ}) = inf S:S∈R d ,µ X (S)=1-δ µ X ({x : diam(A n (x) ∩ S) > γ}) p.s = µ X ({x : diam(A n (x) ∩ R) > γ}) p.s, quel que soit R ⊂ R d tel que µ X (R) = 1 -δ p.s.

Machine learning et interprétabilité

Il existe une légende urbaine dans le domaine du ML relaté dans [START_REF] Yudkowsky | Artificial intelligence as a positive and negative factor in global risk[END_REF]:

"Once upon a time, the US Army wanted to use neural networks to automatically detect camouflaged enemy tanks. The researchers trained a neural net on 50 photos of camouflaged tanks in trees, and 50 photos of trees without tanks. Using standard techniques for supervised learning, the researchers trained the neural network to a weighting that correctly loaded the training set -output "yes" for the 50 photos of camouflaged tanks, and output "no" for the 50 photos of a forest. This did not ensure, or even imply, that new examples would be classified correctly. The neural network might have "learned" 100 special cases that would not generalize to any new problem. Wisely, the researchers had originally taken 200 photos, 100 photos of tanks and 100 photos of trees. They had used only 50 of each for the training set. The researchers ran the neural network on the remaining 100 photos, and without further training, the neural network classified all remaining photos correctly. Success confirmed! The researchers handed the finished work to the Pentagon, which soon handed it back, complaining that in their own tests the neural network did no better than chance at discriminating photos.

It turned out that in the researchers' dataset, photos of camouflaged tanks had been taken on cloudy days, while photos of plain forest had been taken on sunny days. The neural network had learned to distinguish cloudy days from sunny days, instead of distinguishing camouflaged tanks from empty forest."

Le but de cette histoire (citée également dans [19,26]) est de mettre en garde contre l'utilisation d'algorithmes générant des modèles non interprétables tels que les algorithmes de type Support Vector Machines [START_REF] Vapnik | The nature of statistical learning theory[END_REF], Neural networks ou encore Random Forests [7]. Ces algorithmes sont souvent appelés black box dans la mesure ou il est très difficile, voir impossible, pour un statisticien de comprendre le modèle généré par l'algorithme. En dépit de leur manque d'interprétabilité, ces algorithmes sont le plus souvent très précis avec une perte (1.2) très faible. Ce qui conduit au compromis Interprétabilité-Précision.

Dans certains domaines comme la biologie, la médecine, la justice, la banque ou même la finance, être capable d'interpréter les modèles prédictifs est devenue un enjeu majeur. L'article [START_REF] Lipton | The mythos of model interpretability[END_REF] expose tous les enjeux et tout ce que l'on est susceptible d'attendre de l'interprétabilité d'un algorithme. La Figure 1.5 met en lumière l'intérêt croissant du phénomène dans le milieu scientifique. En effet de plus de plus d'articles statistiques traitant de l'interprétabilité sont publiés chaque année.

Malheureusement aujourd'hui encore, l'interprétabilité souffre d'un manque de rigueur dans sa définition. Dans [15], les auteurs la définissent de la façon suivante "Interpret means to explain or to present in understandable terms. In the context of ML systems, interpretability is the ability to explain or to present in understandable terms to a human."

Cette définition ne fournit pas un critère objectif pour évaluer l'interprétabilité d'un algorithme. Dans [START_REF] Murdoch | Interpretable machine learning: definitions, methods, and applications[END_REF] les auteurs donnent la définition suivante "We define interpretable machine learning as the use of machine-learning models for the extraction of relevant knowledge about domain relationships contained in data."

Leas auteurs proposent d'évaluer l'interprétabilité en utilisant le cadre PDR pour Predictive, Description and Revelant. Il s'agit des trois désidératas pour évaluer et concevoir un algorithme interprétable : la précision des prédictions, la qualité de la description du modèle et sa pertinence. Mais, là encore, les deux derniers désidératas sont évalués de façon subjective.

Finalement, même si l'on est capable de comprendre ces définitions il n'existe, à notre connaissance, aucune mesure ou définition formelle des capacités d'interprétabilité d'un algorithme statistique. Ce qui fait que nous ne sommes pas capable de comparer deux algorithmes en termes d'interprétabilité de façon objective.

Il existe deux grandes façons de construire un modèle considéré comme interprétable : la première est d'utiliser un modèle black-box puis de le résumer pour créer un algorithme interprétable dit post-hoc. De récentes recherches proposent d'utiliser des algorithmes d'explication tels que LIME [START_REF] Ribeiro | Why should i trust you?: Explaining the predictions of any classifier[END_REF], DeepLIFT [START_REF] Shrikumar | Learning important features through propagating activation differences[END_REF] ou encore SHAP [START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF] pour interpréter les modèles black-box. Ces algorithmes essayent de mesurer l'importance des variables explicatives sur le processus de prédiction (voir [26] ou [24] pour une présentation des méthodes existantes). Mais ces algorithmes ne fournissent que des informations partielles qui peuvent ne pas être suffisantes pour des décisions sensibles d'un point de vue moral ou à fort enjeu [START_REF] Rudin | Please stop explaining black box models for high stakes decisions[END_REF]. La seconde méthode consiste à utiliser des algorithmes intrinsèquement interprétables, c'est-à-dire des algorithmes générant des modèles interprétables. Il existe deux grandes familles d'algorithmes intrinsèquement interprétables : les arbres de décision et les ensembles de règles. Le processus de construction d'un arbre se fait par partition successive des données. Plus l'arbre est profond plus le nombre d'observations diminue. Il devient alors difficile d'identifier la meilleure coupure pour séparer les données en deux. Ce problème engendre souvent des arbres trop complexes expliquant très bien les données mais qui se généralisent mal dans le sens où les coupures dépendent des observations plus que de leur distribution.

Les arbres de décision

En d'autres termes cela signifie que l'algorithme a également appris le bruit. On appelle ce phénomène le sur-apprentissage. Pour palier ce défaut, les statisticiens ajoutent une étape de post-processing appelé élagage. L'idée consiste à transformer certains noeuds en feuilles et donc à supprimer les sous-arbres rattachés à ces noeuds.

La construction d'un arbre binaire optimal est un problème N P -complet [START_REF] Hyafil | Constructing optimal binary decision trees is npcomplete[END_REF]. Néanmoins, plusieurs méthodes d'optimisation ont été développées ces dernières années, notamment la méthode MIO [5] dont les résultats pratique sont les plus performants.

Les ensembles de règles

Une règle est une assertion du type If-Then de la forme

IF (X[1] ∈ c 1 ) And (X[2] ∈ c 2 ) And . . . And (X[d] ∈ c d ) (1.18) THEN g n (X) = p avec X[j] la j ème coordonnée de X et c j ⊆ R un intervalle.
Le nombre de c i = R est appelé la longueur d'une règle. La partie If de la règle, appelée condition de la règle, est composée de la conjonction de d tests vérifiant si une variable explicative (une coordonnée de X) vérifie une certaine condition. La partie Then de la règle, appelée conclusion, est la prédiction de la valeur de la variable d'intérêt Y quand la règle est active, c'est-à-dire lorsque sa condition est satisfaite. Remarque 3. Étant donné que chaque c i est un intervalle de R, l'ensemble r = d i=1 c i forme un hyperrectangle de R d . De plus, une règle étant entièrement déterminée par sa condition, l'ensemble r est aussi appelé règle par abus de langage. On définit alors la fonction qui donne la longueur d'une règle r, notée par :

(r) = d-#{1 ≤ j ≤ d; c j = R}.
Les règles sont des objets simples à comprendre et permettent de prendre une décision simple à interpréter tant que la longueur (r) des règles reste petite. Chaque décision issue de la prédiction de Y peut ainsi être expliquée par un ensemble de propriétés vérifiées par les données X. Le tableau 1.1 représente un ensemble de règles de longueur maximale 3 décrivant également les données Boston housing.

Arbres vs Ensemble de règles

Un arbre peut formellement être écrit sous la forme d'un ensemble de règles, mais la réciproque est fausse. En effet un ensemble de règles n'a pas forcément de noeud racine et ne forme par non plus une partition. Il a été montré, dans [START_REF] Quinlan | C4.5: Programs for machine learning[END_REF], que les modèles fondés sur des arbres, même élagués, sont souvent plus complexes et plus difficiles à interpréter que des modèles à base d'ensembles de règles.

De plus les arbres reposent sur une partition récursive de l'espace des variables explicatives. De ce fait il n'y a aucune intersection entre les règles. Cette contrainte entraîne souvent que des sous-arbres identiques sont appris à différents endroits de l'arbre. Ce problème appelé problème de la réplication des sous-arbres a été traité dans [3]. Un autre inconvénient est qu'une telle procédure est contraignante dans le processus de recherche. En effet de tels algorithmes ne peuvent pas être parallélisés puisque chaque étape dépend de la précédente.

A l'inverse les ensembles de règles ne font pas nécessairement de partition ce qui permet d'éviter ce problème de réplication. Malheureusement cela engendre une autre difficulté qui est de faire une prédiction lorsque plusieurs règles sont actives. De plus, en l'absence d'heuristique de parcours des données les algorithmes de génération de règles peuvent être très consommateurs de ressources. En effet il n'est absolument pas envisageable de générer toutes les règles possibles à cause du volume que cela représente.

Les algorithmes à ensemble

Pour éviter les problèmes liés à la contrainte de partition, évoqué ci-dessus, on peut également considérer des algorithmes à ensemble. Nous présentons ici quatre algorithmes à ensemble parmi les plus populaires.

Développée récemment, une idée est de considérer tous les noeuds (intérieurs et terminaux) d'un ensemble d'arbres comme des règles. Chaque prédiction sera alors une somme pondérée de plusieurs règles. L'algorithme RuleFit [20] génère un grand nombre de règles à partir d'arbres. Les activations de ces règles sont ensuite considérées comme des variables binaires valant 1 si la règle est active, 0 sinon. Ces nouvelles variables sont ajoutées à l'ensemble de variables explicatives pour une régression LASSO [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF]. Les règles avec un coefficient non nul forment un ensemble de règles sélectionnées auquel s'ajoute les relations linéaires. Le Tableau 1.2 représente les six règles les plus importantes décrivant les données Boston housing3 issues de RuleFit. On retrouve les même colonnes que le tableau 1.1 sauf que la colonne Value correspond aux coefficients issues de la régression LASSO et non pas au Then de la règle.

Toutefois, le nombre de règles dans le modèle final issu de RuleFit peut être très élevé. De plus, le signe du coefficient associé par la régression à la règle peut être différent de celui de la moyenne des Y dans cette règle, ce qui peut biaiser l'interprétabilité. L'algorithme Ender [12] génère un nombre de règles fixé à l'avance. Elles sont générées de façon récursives telles que chaque nouvelle règle ajoutée soit celle dont l'ajout à l'ensemble de règles minimise la perte empirique (1.6). Cet algorithme est un algorithme d'ensemble où chaque règle est considérée comme un modèle très simple car générée de petite longueur. L'ensemble de ces modèles (règles) est ensuite agrégé en une moyenne pondérée. Le problème de cet algorithme est qu'il génère également un grand nombre de règles (plus de 1000 pour décrire les données Boston housing) L'algorithme Node harvest de [START_REF] Meinshausen | Node harvest[END_REF], développé dans le cadre de la classification, considère également tous les noeuds (intérieurs et terminaux) d'un ensemble d'arbres comme des règles. Chaque règle se voit associer un poids positif ou nul ajusté pour minimiser la perte empirique (1.6). La résolution de ce problème d'optimisation convexe permet d'obtenir un petit ensemble de règles avec des poids non nuls.

Rule

Plus récemment, [4] propose l'algorithme SIRUS qui génère un grand nombre d'arbres de faibles profondeurs. Il extrait alors les chemins (arcs plus noeuds) dont la probabilité empirique d'apparition est supérieure à un certain seuil. Afin d'assurer la stabilité de l'algorithme, les variables explicatives sont discrétisées. Cet algorithme fournit un petit ensemble de règles très stable par rapport à l'échantillon et garde un bon pouvoir prédictif. Il ne s'applique pour le moment que dans le cadre de la classification.

La section suivante présente les méthodes usuelles pour apprendre une règle et construire un ensemble de règles. Tout au long de cette section nous dressons un état de l'art de ces algorithmes et concluons en présentant les problèmes liés à l'utilisation de tels algorithmes pour l'analyse de la régression.

L'apprentissage des ensembles de règles

L'apprentissage de règles est une composante basique du machine learning et du data mining, il est étudié depuis les années 1960. Il a été le premier type d'algorithme de machine learning utilisé dans un processus industriel. On peut citer GASOIL [START_REF] Slocombe | Engineering expert system applications[END_REF], BMT [START_REF] Hayes-Michie | Pragmatica: Bulletin of the inductive programming special interest group[END_REF] ou encore [START_REF] Leech | A rule-based process control method with feedback[END_REF] utilisé dans le processus de contrôle. Pour une introduction détaillée sur l'apprentissage de règles nous renvoyons les lecteurs à l'ouvrage [22].

L'apprentissage de règles est le domaine de ML qui se concentre sur l'extraction de règles à partir d'un jeu de données. Les deux domaines principaux sont l'apprentissage de règles d'associations et l'apprentissage de règles prédictives. Le premier cherche à trouver des informations ou des modèles en fonction du jeu de données donné. L'algorithme le plus emblématique de recherche de règles d'associations est APriori [1]. Pour une revue des algorithmes d'apprentissage de règles les plus connus pour la description nous renvoyons les lecteurs à [START_REF] Zhao | Association rule mining: A survey[END_REF].

L'apprentissage de règles prédictives vise une description du modèle, afin de faire des prédictions à partir de nouvelles observations. C'est ce domaine que nous traitons dans cette thèse. Pour une revue des algorithmes d'apprentissage de règles pour la prédiction nous renvoyons le lecteur à l'article [23].

Apprendre une règle

Il existe deux méthodes de recherche pour apprendre une règle : la méthode général à spécifique ou descendante (top-down) et la méthode spécifique à général ou ascendante (bottom-up).

La méthode descendante commence par une règle générique et tente de la spécifier de façon récursive. L'algorithme CART [8] est établie sur cette méthode. Par exemple, l'algorithme 1 part d'une règle toujours vérifiée qui prédit la moyenne de la variable d'intérêt sur un échantillon (ligne 1) et rétrécie les bornes de l'intervalle pour ne garder que les valeurs de Y les plus grandes. Par souci de simplicité on suppose que

d = 1 et Y ∈ [-1, 1] dans l'algorithme 1.
Inversement, la méthode ascendante part d'une règle spécifique et tente de la généraliser de façon récursive. La méthode d'élagage [8] est une méthode ascendante. Par exemple, l'algorithme 2 présenté ci-dessous, part d'une règle toujours très spécifique (définie sur un point de l'échantillon ligne 3) qui prédit le maximum de la variable d'intérêt sur un échantillon et élargit les bornes de l'intervalle pour ne garder que des Y positifs. Par souci de simplicité on suppose que On observe qu'en général la première méthode fournit des règles plus générales que la seconde, ce qui la rend plus adaptée à l'apprentissage sur des jeux de données bruités. Elle est également la plus utilisée dans les systèmes pratiques. En revanche la méthode ascendante est plus efficace lorsque le phénomène que l'on veut étudier s'est peu produit dans l'échantillon.

d = 1 et Y ∈ [-1, 1].
On peut remarquer que ces méthodes de raffinement d'une règle peuvent être très coûteuses en temps de calcul à mesure que n augmente si les variables explicatives sont continues. Comment trouve-t-on des bornes pour définir une condition dans (1.18) ? La méthode usuelle est de discrétiser les données. Soit par une méthode qualitative en choisissant des groupes usuels pour les professionnels du secteur (ex : poids ≤ 50, 50 < poids ≤ 60, etc.), soit en utilisant des méthodes quantitatives comme dans [18], [16], [START_REF] Srikant | Mining quantitative association rules in large relational tables[END_REF] ou encore l'algorithme BRL (Bayesian Rule Lists) [START_REF] Letham | Interpretable classifiers using rules and bayesian analysis: Building a better stroke prediction model[END_REF] et SIRUS [4] qui appliquent une discrétisation en utilisant les quantiles empiriques.

Apprendre un ensemble de règles

Pour définir un modèle à partir d'un apprentissage de règles, il existe deux familles de stratégies algorithmiques : Divide-and-Conquer, qui est une partition récursive de l'ensemble de données en optimisant un critère sur tous les noeuds successeurs [START_REF] Quinlan | Induction of decision trees[END_REF] et Separate-and-Conquer qui cherche les meilleures règles qui expliquent une partie du jeu de données puis supprime les points couverts et conquiert récursivement le jeu de données restant en apprenant plus de règles [21] .

La première stratégie ne conçoit pas de règles qui se chevauchent, évitant ainsi les conflits de prédictions lorsque deux ou plusieurs conditions de règles sont vérifiées. Dans ce cas, les règles peuvent être ordonnées, formant ainsi une liste de décision introduit dans [START_REF] Rivest | Learning decision lists[END_REF]. Les listes de décisions sont un ensemble de règles qui peuvent s'écrire sous la forme If-ThenIf-. . . -Then.

Dans la deuxième stratégie, on obtient un ensemble de règles et il faut gérer les chevauchements. Soit en transformant l'ensemble des règles en une liste de décisions, soit en utilisant l'une des méthodes suivantes : Frequency-Based, Naive Bayesian et Double Induction, pour une description de ces méthodes nous renvoyons le lecteur à [START_REF] Lindgren | Resolving rule conflicts with double induction[END_REF]. L'autre problème de cette stratégie est que la couverture n'est pas assurée. Cela signifie que pour les nouvelles données, il peut n'y avoir aucune règle active (c.f la remarque 2). Une solution courante consiste à prédire la classe majoritaire ou la moyenne, selon le scénario proposé par [START_REF] Van Laer | On multi-class problems and discretization in inductive logic programming[END_REF]. Une autre méthode proposée par [17] consiste à appliquer des règles qui garantissent un recouvrement.

Les problèmes liés à la régression

L'analyse de la régression à partir de règles n'a pas été particulièrement bien étudiée. Contrairement à la classification, il existe peu de solutions commerciales (on peut néanmoins citer Cubist 5 4 ). En fait, l'apprentissage des règles de régression pose de nombreux problèmes en plus de ceux liés à l'apprentissage des règles.

Premièrement, comme mentionné précédemment dans un scénario de régression, la variable d'intérêt prend ses valeurs dans R et l'objectif d'un algorithme prédictif est de prédire la valeur de la variable à partir de nouvelles données. Mais, on peut remarquer que la conclusion d'une règle, de la forme (1.18), est une valeur numérique constante, ce qui induit un biais lorsque la fonction de régression n'est pas constante.

Le deuxième problème concerne les critères d'arrêt. En effet, dans un problème de régression, le critère est la réduction de la variance autour de la prédiction de la règle. Les meilleures règles sont donc celles qui sont réduites à un point. Une solution courante consiste à imposer une limite minimale au taux de couverture des règles, c'est-à-dire au ratio du nombre de points dans la règle sur n. Par exemple l'algorithme FORS [START_REF] Karalič | First order regression[END_REF] utilise le principe de minimal description length (MDL) pour élaborer un élagage de règles. Ce qui peut s'interpréter comme une application du principe du rasoir d'Ockham "Pluralitas non est ponenda sine necessitate" 5 .

La technique la plus populaire pour l'apprentissage d'une règle de régression consiste à utiliser un algorithme d'arbre de décisions où les arbres appris sont transformés en listes de décision [START_REF] Rivest | Learning decision lists[END_REF]. Par exemple, l'algorithme M5 Rules [START_REF] Holmes | Generating rule sets from model trees[END_REF], propose d'utiliser des arbres de façon récursive sur l'ensemble de données. Tout d'abord, il extrait une seule règle d'un arbre, puis supprime toutes les données couvertes par cette règle, l'algorithme réitère le processus sur les données restantes jusqu'à ce que touts les points soient couverts. On a donc à faire à une stratégie Separate-and-Conquer avec une méthode descendante.

Une autre méthode répandue consiste à convertir le problème de régression en problème de classification et ainsi utiliser un algorithme d'apprentissage des règles pour un problème de classification. La première idée est de discrétiser la variable d'intérêt comme dans [START_REF] Weiss | Rule-based machine learning methods for functional prediction[END_REF] et [START_REF] Torgo | Regression using classification algorithms[END_REF]. Mais l'ensemble de règles d'apprentissage dépend trop du nombre d'éléments choisi pour la discrétisation. Un moyen d'éviter ce problème est présenté dans [START_REF] Indurkhya | Solving regression problems with rule-based ensemble classifiers[END_REF], [START_REF] Janssen | Heuristic rule-based regression via dynamic reduction to classification[END_REF]. Dans [START_REF] Langford | Predicting conditional quantiles via reduction to classification[END_REF] le problème de régression se transforme en un problème de classification binaire dont l'objectif est de prédire si la valeur de sortie est supérieure ou inférieure à un seuil choisi.

Enfin, une idée originale, présentée dans [START_REF] Torgo | Data fitting with rule-based regression[END_REF], consiste à construire un arbre de régression où chaque noeud terminal prédit un modèle linéaire (ajusté sur les données de l'échantillon dans la feuille) à la place d'une valeur constante.

4. http://www.rulequest.com/cubist-info.html 5. "Les multiples ne doivent pas êtres utilisés sans nécessité."

1.3.4 Estimateur à base de règles L'objectif des algorithmes d'apprentissage de règles prédictives est de générer un ensemble de règles P n . Cet ensemble est utilisé pour décrire le modèle appris et permet de faire des prédictions en fonction de nouvelles observations. D'après (1.7), si P n forme une partition de R d , c'est-à-dire toutes les règles r sont disjointes et r∈Pn r = R d alors l'estimateur de la fonction de régression s'écrit sous la forme

g n (x) = r∈Pn n i=1 Y i 1 X i ∈r n i=1 1 X i ∈r 1 x∈r , x ∈ R d . (1.19)
En effet, dans ce cas, la classe G n dans (1.7) est l'ensemble des fonctions constantes par morceaux sur les partitions P n :

G n = G c • Π n := g : R d → R : g = r∈Pn f r 1 r , P n ∈ Π n , f r ∈ G c ,
et la fonction constante qui minimise la perte empirique sur un ensemble r est l'espérance conditionnelle empirique de Y sachant X ∈ r.

Contributions

L'objectif de cette thèse est de présenter un algorithme interprétable, RICE pour Rule Induction Covering Estimator, qui génère et sélectionne un ensemble de règles pour construire un estimateur consistant de la fonction de régression.

Dans un premier temps, nous avons introduit un indice d'interprétabilité pour être en mesure de comparer les algorithmes dits interprétables (définition 1.4.1). Puis, partant du principe que moins il y a de règles, meilleure sera l'interprétabilité, nous avons mis en place un moyen efficace en terme de complexité de définir un estimateur à partir d'un recouvrement (proposition 1.4.1). Nous avons ainsi introduit une famille d'algorithmes dit à recouvrement dépendant des données. Enfin, nous avons prouvé qu'en générant un recouvrement composé de règles définies comme signifiantes et insignifiantes (définition 1.4.3), alors un algorithme à recouvrement dépendant des données génère un estimateur consistant de la fonction de régression (théorème 1.4.1).

Ce résultat, résumé dans la Proposition 1.4.3, repose sur les propriétés des classes Q-Donsker et sur la notion de probabilité extérieure. La preuve utilise les taux de convergence des estimateurs de l'espérance et de la variance conditionnelles. C'est le principal résultat technique de cette thèse.

Mesure de l'interprétabilité

RICE a été développé en se fondant sur le triptyque simplicité, stabilité et prédictivité présenté dans [START_REF] Yu | Three principles of data science: predictability, computability, and stability[END_REF]. La notion de prédictivité peut être facilement mesurée en calculant la perte (1.2) sur simulation et celle de stabilité a été traitée dans [77] et peut être évaluée en mesurant le taux de rotations des règles en fonction de l'échantillon comme dans [4]. Dans [START_REF] Yu | Three principles of data science: predictability, computability, and stability[END_REF] la simplicité fait référence à la complexité de l'algorithme utilisé. Mais nous proposons plutôt de mesurer la simplicité du modèle généré. A notre connaissance, il n'existe actuellement pas de moyen quantitatif d'évaluer la simplicité d'un modèle à base de règles. Pour être en mesure de comparer notre algorithme à ceux existants, nous introduisons l'indice d'interprétabilité qui permet de comparer n'importe quel type de modèle à base de règles.

L'interprétabilité pour un estimateur à base de règles est atteint lorsque la longueur k de chaque règle est petite. Considérant qu'un estimateur avec une règle de longueur k est aussi interprétable que celui avec les k règles correspondantes de longueur 1, la possibilité d'interprétation obtient naturellement la propriété d'additivité. Nous sommes alors en mesure de définir l'interprétabilité d'un modèle fondé sur un ensemble de règles P comme suit : (1.20)

Introduction d'un recouvrement

L'idée usuelle d'imposer que l'union des conditions des règles sélectionnées forme une partition est une condition trop contraignante. En effet, les règles deviennent interdépendantes et plus le nombre de règles sélectionnées augmente plus l'espace de recherche diminue. Nous avons donc mis en place une méthode permettant de travailler avec des règles qui se chevauchent en imposant que l'union des conditions des règles sélectionnées forme un recouvrement. En l'absence de cette contrainte le modèle généré n'explique qu'une partie du vrai modèle. Cette façon de procéder rend la recherche de chaque règle indépendante et permet de paralléliser l'algorithme et donc d'explorer plus de possibilité dans le même laps de temps. Afin de pouvoir garantir une prédiction unique le recouvrement est transformé en partition en utilisant le partitioning trick. Ainsi nous obtenons un estimateur de la forme (1.19) à partir d'un ensemble de règles.

Considérer un recouvrement permet d'avoir un ensemble de règles beaucoup plus petit pour décrire le modèle. Et le fait de définir l'estimateur sur la partition engendrée par ce recouvrement permet de garder de bonnes propriétés comme la consistance.

Transformation d'un recouvrement en partition

Formellement, nous définissons une partition générée pour une collection de sousensembles C en utilisant l'ensemble des parties de C, noté 2 C : Définition 1.4.2. Soit C une collection finie de sous-ensembles de R d et soit c = r∈C r.

On définit la fonction d'activation comme

ϕ C : R d → 2 C ; ϕ C (x) = {r ∈ C : x ∈ r}.
On définit P(C), la partition de c générée à partir de C, comme

P(C) := ϕ -1 C (Im(ϕ C )), où Im(ϕ C ) est l'image de ϕ C .
Nous illustrons la transformation de P sur un exemple à quatre éléments dans les Figures 1.7 À partir d'un recouvrement C de R d nous pouvons construire un estimateur g n défini par :

g n (x) = A∈P(C) n i=1 Y i 1 X i ∈A n i=1 1 X i ∈A 1 x∈A , x ∈ R d . (1.21)
Par construction, il y a, au plus, un élement de P(C) contenant x.

Le partitioning trick

Malheureusement, transformer un recouvrement C en partition P(C) est une opération complexe. En effet nous avons

#C ≤ #P(C) ≤ #C i=1 #C i .
Pour le voir il suffit de remarquer que pour C = {r 1 , . . . , r n } on a pour tout i ∈ {1, . . . , n} P (C) = {r i \ ∪ j =i r j : i ∈ {1, . . . , n}} {r i ∩ r j \ ∪ l =i,j r l : i ∈ {1, . . . , n}, j ∈ {i + 1, . . . , n}}

{r i ∩ r j ∩ r l \ ∪ h =i,h =j,h =l r h : i ∈ {1, . . . , n}, j ∈ {i + 1, . . . , n}, l ∈ {j + 1, . . . , n}} {. . .} {∩ n i=1 r i } .
L'astuce est de remarquer qu'il n'est pas nécessaire de connaître P(C) pour calculer g n (x), mais uniquement la cellule de P(C) qui contient x. Preuve. Il suffit de remarquer que g n (x) peut s'écrire sous la forme:

g n (x) = n j=1 y j k(x, x j , C) n j=1 k(x, x j , C) , avec k(x, x j , C) = R i=1
Lemme 1.4.1. Soit G n une classe de fonctions g : R d → [-L, L] dépendant d'un échan- tillon D n = ((X 1 , Y 1 ), . . . , (X n , Y n )). Si g n vérifie (1.7) alors (g * , g n ) ≤ 2 sup g∈Gn |L n (g) -L (g)| + inf g∈Gn E (g(X) -g * (X)) 2 .
Le premier terme est appelé erreur d'estimation. Il correspond à la distance entre la perte de l'estimation (1.6) et la perte (1.2) de la meilleure fonction de G n . Le second terme est appelé erreur d'approximation. Il mesure à quel point la fonction de régression g * peut être bien estimée par une fonction de G n .

Il est facile de remarquer que ces deux termes jouent des rôles opposés par rapport à la taille de G n . En effet, plus G n sera complexe, c'est-à-dire que l'algorithme construira des fonctions variées (linéaires, polynomiales, sinusoïdales, etc.) plus le terme d'erreur d'approximation sera faible. Mais le terme d'erreur d'estimation sera élevé. Il faut donc réaliser un compromis estimation/approximation.

Dans le cas de partitions indépendantes des données, l'erreur d'estimation est contrôlée automatiquement grâce à la mesurabilité de la fonction de régression et la loi forte des grands nombres. Les conditions du théorème 1.1.1 assurent quant à elles un contrôle de l'erreur d'approximation en imposant aux cellules de la partition un diamètre qui tend vers 0 pour n → ∞.

Dans le théorème 1.1.2, pour les partitions dépendantes des données, la condition (1.12) permet de contrôler l'erreur d'estimation en contrôlant la complexité de l'algorithme et la condition (1.13) permet, quant à elle, de contrôler l'erreur d'approximation. En effet, la complexité est mesurée avec le nombre de partitions, ∆ n (Π), que l'algorithme peut générer et donc la complexité de G n et en assurant un rétrécissement des cellules de la partition on assure une diminution de l'erreur d'approximation dans chacune d'elles.

Pour garantir la consistance et l'interprétabilité au sens de la définition 1.4.1 il faut pouvoir contrôler l'erreur d'approximation sans imposer un rétrécissement des cellules. Pour contrôler cette erreur en considérant des recouvrements nous introduisons la notion de suite acceptable de recouvrements dépendant des données.

On introduit les notations empiriques suivantes :

Q n (r × I) = 1 n n i=1 1 X i ∈r 1 Y i ∈I , E n [h(Y ) | X ∈ r] := n i=1 h(Y i )1 X i ∈r n i=1 1 X i ∈r et V n (Y | X ∈ r) := E n Y 2 | X ∈ r -E n [Y | X ∈ r] 2 .
Par souci de simplification d'écriture

Q n (r) au lieu de Q n (r × R) de même pour Q(r) au lieu de Q(r × R) pour tout r ⊆ R d .
En considérant la notation classique x + = max{x, 0} pour tout x ∈ R nous introduisons la définition suivante. Définition 1.4.3. Une suite (C n ) n≥1 de recouvrements de R d dépendants des données est acceptable si et seulement si elle vérifie les deux conditions suivantes :

1. la condition de couverture :

(H3)

∃ α ∈ [0, 1/2), ∀r ∈ C n , Q n (r) > n -α p.s.,
pour n suffisamment grand;

2. la condition de significativité : (H4) il existe deux suites β n → 0 et ε n → 0 telles que:

C n = C s n ∪ C i n p.s.,
pour n suffisamment grand, avec C s n le sous-ensemble significatif défini par

C s n := r ∈ C n : β n E n [Y |X ∈ r] -E n [Y ] ≥ (V n (Y |X ∈ r) -σ 2 ) + , (1.22)
le C i n sous-ensemble insignifiant défini par

C i n := r ∈ C n \ C s n : ε n ≥ (V n (Y |X ∈ r) -σ 2 ) + , (1.23)
et leurs redondances vérifient

M (C s n ) m(C s n ) = o P (β -2 n ∧ n 1/2-α ) et M (C i n ) m(C i n ) = o P (ε -2 n ∧ n 1/2-α ) , avec M (C) := max x∈c #{r ∈ C : x ∈ r}, m(C) := min x∈c #{r ∈ C : x ∈ r} et c = r∈C r.
Les éléments de C s n sont appelés éléments significatifs et ceux de C i n , éléments insignifiants.

La condition de couverture (H3) garantit la qualité des estimateurs de l'espérance et de la variance, conditionnellement à X ∈ r. En effet, il faut un nombre minimum de points pour être en mesure de garantir un bon taux de convergence. La condition de significativité (1.22) assure, d'une certaine façon, que la variance intra-groupe des éléments signifiants d'un recouvrement est contrôlée par la variance inter-groupe. La condition d'insignifiance (1.23) garantit que la variance conditionnelle d'un élément insignifiant tend vers la variance du bruit. Remarque 6. Il est intéressant de noter que la vérification des conditions (H3), (1.22) et (1.23) pour un élément du recouvrement ne nécessite pas de connaitre les autres éléments de ce recouvrement. Par conséquence, la recherche de tels éléments dans une base de données D n , peut être aisément parallélisée.

Taux de convergence des estimateurs conditionnels

La définition d'une suite acceptable de recouvrement est établie à partir de l'utilisation d'estimateurs plug-in des espérances et des variances conditionnelles. Mais, à notre connaissance, les seuls résultats théoriques sur le taux de convergence pour de tels estimateurs sont ceux issus des travaux de [25]. En s'inspirant de ces résultats, nous en proposons ici une version plus adaptée à notre cas qui repose sur les notions de processus empiriques, de classes Q-Donsker et de probabilité extérieure, P * , rappelées dans la Section 1.

P(M / ∈ K) < ε. ( 1
P * (M n / ∈ K δ ) < ε, (1.25) avec K δ = {y ∈ D : d(y, K) < δ}un δ-voisisnage de K pour tout K ⊂ D et δ > 0. Remarque 7. Si D = R, alors (M n ) est asymptotiquement tendu si et seulement si ∀ε > 0, ∃M > 0 lim sup n→∞ P * (|M n | > M ) < ε.
On note alors M n = O P * (1).

Nous rappelons le résultat suivant.

Proposition 1.4.2. Soit F une classe Q-Donsker de fonctions alors √ n Q n -Q F est asymptotiquement tendu, ce qu'on note : Q n -Q F ∈ O P * (n -1/2 ), en considérant la norme sup, v n F = sup f ∈F |v n (f )|. Remarque 8. Si C est une classe Q-Donsker alors : Q n -Q C ∈ O P * (n -1/2 ), en considérant la norme sup, v n C = sup A∈C |v n (A)|.

Taux de convergence de l'estimateur de l'espérance conditionnelle

On rappelle qu'on observe un échantillon

D n = ((X 1 , Y 1 ), . . . , (X n , Y n )) où les couples (X i , Y i ) sont indépendants et identiquement distribués de loi Q et à valeur dans S ⊆ R d+1 . On munit S d'une algèbre borélienne B S . Le résultat suivant est inspiré de [25, Proposition 3.2]. Proposition 1.4.3. Soient B ⊆ B S et F B := {f 1 A : f ∈ F, A ∈ B} où F est une classe de fonctions de L 1 (Q) uniformément bornées. Si B et F B sont des classes Q-Donsker alors pour tout α ∈ [0, 1/2) et avec B n := {A ∈ B, Q n (A) ≥ n -α }, sup f ∈F sup A∈Bn E n [f | A] -E [f | A] = O P * (n α-1/2 ). Preuve. Soit ε > 0. Avant tout, on sait que pour tout f ∈ F et A ∈ B n , étant donné que Q n (A) > 0 on a Q(A) > 0 et, |E n [f | A] -E [f | A]| = A f dQ n Q n (A) -A f dQ Q(A) = Q(A) A f dQ n -A f dQ + (Q(A) -Q n (A)) A f dQ Q(A)Q n (A) ≤ A f dQ n -A f dQ Q n (A) + (Q(A) -Q n (A)) A f dQ Q(A)Q n (A)
.

(1.26)

Or, d'après la proposition 1.4.2,

sup f ∈F , Ã∈B Ã f dQ n - Ã f dQ = O P * (n -1/2 ) et sup Ã∈B Q n ( Ã) -Q( Ã) = O P * (n -1/2 ).
Ainsi, d'après la remarque 7, il existe M > 0 tel que pour tout n suffisamment grand on a

P * sup f ∈F , Ã∈B Ã f dQ n - Ã f dQ > M n -1/2 < ε 2 et P * sup Ã∈B Q n ( Ã) -Q( Ã) > M n -1/2 < ε 2 c'est-à-dire P * (Ω n ) ≥ 1 -ε avec Ω n := sup f ∈F , Ã∈B Ã f dQ n - Ã f dQ ≤ M n -1/2 sup Ã∈B Q n ( Ã) -Q( Ã) ≤ M n -1/2 . Or sachant (1.26) et avec c := sup f ∈F ,x∈S |f (x)| < ∞, comme Q n (A) ≥ n -α , pour n suffisam- ment grand, dans l'événement Ω n , on a sup f ∈F ,A∈Bn E n [f | A] -E [f | A] ≤ M n α-1/2 (1 + c), puisque A f dQ Q(A) ≤ c. Finalement, on a prouvé que ∀ε > 0, ∃M > 0, ∃N ∈ N * /∀n ≥ N, P * sup f ∈F ,A∈Bn |E n [f | A] -E [f | A]| > M n α-1/2 < ε et donc ∀ε > 0, ∃M > 0 tels que lim sup n→∞ P * sup f ∈F ,A∈Bn |E n [f | A] -E [f | A]| > M n α-1/2 ≤ ε
qui, avec la remarque 7, prouvent la proposition.

Taux de convergence de l'estimateur de la variance conditionnelle

A partir de la proposition 1.4.3 il est facile de déduire le corollaire suivant :

Corollaire 1.4.1. Soit B ⊆ B S une classe Q-Donsker. Si Y est bornée alors pour tout i ∈ N * et pour tout α ∈ [0, 1/2), avec B n := {A ∈ B, Q n (A) ≥ n -α } on a sup A∈Bn E n Y i | (X, Y ) ∈ A -E Y i | (X, Y ) ∈ A = O P * (n α-1/2 ), (1.27) et sup A∈Bn |V n [Y | (X, Y ) ∈ A] -V [Y | (X, Y ) ∈ A]| = O P * (n α-1/2 ).
(1.28)

Preuve de (1.27). On note L = ess sup Y où ess sup désigne la borne supérieure essentielle

et soient i ∈ N, et f i ∈ L 1 (Q) définie par f i : R d × [-L, L] → [-L i , L i ] (x, y) → y i . f i est
V n [Y | (X, Y ) ∈ A] := E n Y 2 | (X, Y ) ∈ A -E n [Y | (X, Y ) ∈ A] 2 .

Théorème de consistance à partir d'un recouvrement

Le principal résultat théorique de cette thèse est un théorème de consistance pour un estimateur de la fonction de régression généré par un algorithme à recouvrement dépendant des données. Ce théorème s'appuie sur le partitioning trick (Section 1.4.2), la définition d'une suite acceptable de recouvrements (Section 1.4.3) et le résultat sur le taux de convergence des estimateurs de moments conditionnels (Section 1.4.4). Théorème 1.4.1. Supposons (H1) et (H2). Soit (C n ) une suite acceptable de recouvrements (i.e., vérifiant (H3) et (H4)) telle que :

M(Π n ) ∨ log(∆ n (Π n )) = o(n), avec Π n := P(C n ((x 1 , y 1 ), . . . , (x n , y n ))) : (x 1 , y 1 ), . . . , (x n , y n ) ∈ R d × R pour tout n ∈ N * ; (H5) ∀n ∈ N * , {c × R, c ∈ C n } ⊆ B, avec B une classe Q-Donsker. (H6)
Alors l'estimateur g n défini par (1.21) est faiblement consistant:

(g * , g n ) = o P (1).
(1.29)

La condition (H5) est la même que la condition (1.12) du théorème 1.1.2 pour la consistance des estimateurs issus d'un algorithme à partition dépendante des données. Comme expliqué précédemment, cette condition permet de contrôler l'erreur d'estimation en garantissant que la classe de fonction G n à laquelle appartient g n n'est pas trop complexe. L'originalité de ce théorème est dans le contrôle de l'erreur d'approximation par les conditions (H3), (H4) et (H6) au lieu d'une condition sur le diamètre des cellules ((1.9) et (1.13)). On peut également remarquer que dans ce théorème il n'y a aucune condition sur les cellules de la partition induite par le recouvrement sur lesquelles est défini l'estimateur g n . Cela permet d'avoir une plus grande richesse de partitions comme illustré dans la Figure 1.9.

Algorithmes à recouvrement interprétables

Nous avons présenté dans [START_REF] Margot | Rule induction partitioning estimator[END_REF] (chapitre 5) le premier algorithme générant un estimateur de la forme (1.21) à partir d'un recouvrement de règles. L'algorithme RIPE a été développé en se fondant sur le partitioning trick (voir Section 1.4.2). Il permet d'obtenir un ensemble de règles de petite taille pour décrire des modèles complexes tout en préservant la stabilité, grâce à une discrétisation des variables explicatives ainsi qu'un bon pouvoir prédictif.

Mais, bien que très interprétable, les propriétés statistiques du recouvrement de règles ne permettaient pas d'obtenir de résultat de consistance sur l'estimateur. L'algorithme Covering Algorithm a été développé pour illustrer la notion de règles signifiantes et insignifiante introduite dans le chapitre 2. Cet algorithme utilise un Random Forest comme générateur de règles. Il extrait un petit ensemble de règles signifiantes et insignifiantes en considérant toutes les feuilles et tous les noeuds de tous les arbres. Le problème est que pour assurer un recouvrement l'algorithme doit ajouter une "non-règle" qui s'active si aucune règle n'est active. L'absence de contrôle sur cette "non-règle" et sur la complexité du générateur de règle (au sens de la condition (H5)) ne permet pas d'assurer la consistance sans l'ajout d'hypothèses.

L'algorithme RICE, introduit dans le chapitre 3, est, en ce sens, une amélioration de RIPE et de Covering Algorithm. Il reprend l'algorithme RIPE pour la génération de règles et utilise l'algorithme de sélection de Covering Algorithm pour sélectionner une suite acceptable de recouvrements. La fusion de ces deux algorithmes nous permet d'avoir un algorithme interprétable et de nous placer dans les conditions du théorème de consistance 1.4.1, ce qui nous permet de prouver la consistance faible de l'estimateur de la fonction de régression généré par RICE.

De plus, pour chaque algorithme, un package Python a été développé et mis en ligne sur GitHub.

Rappels et heuristique de preuve

Dans cette section nous rappelons quelques propriétés asymptotiques des processus empiriques. Nous présentons également le Théorème 1.4.1 dans un contexte idéal afin de mettre en lumière les grands principes de la preuve.

Rappels sur les processus empiriques

Soit S 1 , S 2 , . . . une suite de variables aléatoires i.i.d de loi inconnue Q et prenant leurs valeurs dans un espace S ⊆ R d . On munit S d'une tribu borélienne B S . Avec la notation Qf := f dQ, on considère le processus empirique v n (f

) := n 1/2 (Q n f -Qf ), où Q n désigne la mesure empirique.
Le résultat théorique sur le taux de convergence des estimateurs d'espérances conditionnelles (Proposition 1.4.2) repose sur les propriétés des classes de fonctions de L 2 (Q) de S dans R dites Q-Donsker. À ce jour il n'existe pas de condition nécessaire et suffisante pour qu'une classe F soit Q-Donsker. Mais une condition suffisante est donnée par [START_REF] Van Der Vaart | Asymptotic statistics[END_REF]Theorem 19.4]. Ce théorème montre que pour qu'une classe de fonctions mesurables F soit Q-Donsker il suffit que son nombre de crochets N [ ] ( , F, L 2 (Q)) ne grossisse pas trop vite vers l'infini lorsque tend vers 0. Cette vitesse se mesure par l'entropie à crochet définie par

J [ ] (δ, F, L 2 (Q)) = δ 0 log N [ ] ( , F, L 2 (Q))d . Théorème 1.5.1. Toute classe F de fonctions mesurables vérifiant J [ ] (1, F, L 2 (Q)) < ∞ est une classe Q-Donsker.
La notion de limite en probabilité pour une suite de variable aléatoire doit être généralisée pour une suite d'applications à valeurs dans des espaces métriques qui ne sont pas des espaces euclidiens (dans ce cas les ensembles bornés et fermés ne sont pas nécessairement compacts) et la mesurabilité n'est pas garantie. Pour contourner la difficulté de mesurabilité, on introduit la notion de probabilité extérieure, notée P * , et on considère le taux de convergence en O P * au lieu de l'usuel O P . Définition 1.5.2. Soit (Ω, A, P) un espace de probabilité, alors pour tout B ⊆ Ω, la probabilité extérieure P * (B) est définie par

P * (B) := inf {P(A) : B ⊂ A, A ∈ A} .
P n . Si • M(Π n ) n ∨ log(∆ n (Π n )) n → 0 (n → ∞),
• P n forme une partition de R d ,

• Il existe deux suites β n → 0 et ε n → 0 telles que :

P n = P s n ∪ P i n p.s, avec P s n le sous-ensemble signifiant défini par

P s n := r ∈ P n : β n E[Y |X ∈ r] -E[Y ] ≥ (V(Y |X ∈ r) -σ 2 ) + , et P i n le sous-ensemble insignifiant défini par P i n := r ∈ P n \ P s n : ε n ≥ (V(Y |X ∈ r) -σ 2 ) + , alors (g * , g n ) → 0 (n → ∞) p.
G n = g : R d → R : g = A∈Pn f A 1 A , f A ∈ G c , où G c est l'ensemble des fonctions constante de R d dans [-L, L]. Pour tout g n ∈ G n on a inf g∈Gn E (g(X) -g * (X)) 2 ≤ E (g n (X) -g * (X)) 2 , et on pose W n := E (g n (X) -g * (X)) 2 .
L'idée de la preuve repose sur l'identification de l'erreur d'approximation comme étant une variance intra-groupe. En effet, soit gn ∈ G n définie par

gn (x) = E [Y |X ∈ A(x)] ,
pour tout x ∈ R d où A(x) ∈ P n désigne la cellule qui contient x. On a alors

W n := A∈Pn E (E [Y | X ∈ A] -g * (X)) 2 X ∈ A P (X ∈ A) ,
la variance intra-groupe des règles A ∈ P n . On pose

W s n := A∈P s n E (E [Y | X ∈ A] -g * (X)) 2 X ∈ A P (X ∈ A) et W i n := A∈P i n E (E [Y | X ∈ A] -g * (X)) 2 X ∈ A P (X ∈ A) .
Étant donné que P n = P s n ∪ P i n et que P s n ∩ P i n = ∅, on a

W n = W s n + W i n .
L'idée est d'utiliser les propriétés des sous-ensembles (in)signifiants pour montrer que W s n et W i n tendent vers 0.

Variance intra-groupe des insignifiantes : Il est facile de montrer que par hypothèse on a

W i n ≤ ε 2 n p.s ---→ n→∞ 0.
Variance intra-groupe des signifiantes : En utilisant la décomposition de variance on a

W s n ≤ V(g * (X)) -B s n , (1.30) avec B s n := A∈P s n (E [Y | X ∈ A] -E [Y ]) 2 P (X ∈ A) ,
la variance inter-groupe des signifiantes. Or, d'après la propriété de signifiance on a que

B s n ≥ A∈P s n β -2 n (V(Y |X ∈ A) -σ 2 )P (X ∈ A)
De plus, par indépendance de Z et X, on a

V(Y |X ∈ A) -σ 2 = E Y -E [Y | X ∈ A] 2 | X ∈ A -σ 2 = E E [Y | X ∈ A] -g * (X) 2 | X ∈ A .
On a donc

B s n ≥ β -2 n A∈P s n E E [Y | X ∈ A] -g * (X) 2 | X ∈ A P (X ∈ A) .
On reconnaît W s n dans le terme de droite. Donc, par hypothèse et d'après (1.30), nous pouvons conclure que

W s n ≤ V(g * (X)) 1 + β -2 n p.s ---→ n→∞ 0.
Erreur d'estimation: Il reste à montrer que l'erreur d'estimation tend vers 0 en utilisant la première condition du Théorème 1.4.1. On rappelle que G n est l'ensemble des fonctions constantes par morceaux à valeur dans [-L, L] sur les éléments de la partition P(D n ). En introduisant la notion de famille de partitions Π n définie par (1.11) on a

sup g∈Gn |L n (g) -L (g)| ≤ sup g∈Gc•Πn |L n (g) -L (g)| , avec G c • Π n := g : R d → R : g = A∈Pn f A 1 A , P n ∈ Π n , f A ∈ G c .
La suite de la preuve repose sur les mêmes arguments que celle du [28, Théorème 13.1] mais sera détaillée dans le chapitre 2.

"We think too much and feel too little" Charlie Chaplin.

Chapter 2

Consistent Regression using Data-Dependent Coverings

Introduction

Let (Ω, A, P) be a probability space and we consider the following regression setting:

(X, Y ) is a couple of random variables in R d × R of unknown distribution Q such that Y = g * (X) + Z, where E[Z] = 0, V(Z) = σ 2 and g * is a measurable function from R d to R.
We make the following common assumptions:

-

Z is independent of X and σ 2 ≥ 0 is known; (H7) - Y is bounded: Q(S) = 1 with S = R d × [-L, L], for some L > 0 (unknown). ( H8
)
Given a sample D n = ((X 1 , Y 1 ), . . . , (X n , Y n )), we aim at predicting Y conditionally on X. The observations (X i , Y i ) are independent and identically distributed (i.i.d.) from the distribution Q. The accuracy of a regression function g : R d → R is measured by its quadratic risk, defined as

L (g) = E Q (g(X) -Y ) 2 .
Thanks to Hypothesis (H7), we have

g * (X) = E [Y |X] = arg min g L (g) a.s, (2.1)
where the arg min is taken over the class of all measurable regression functions. The regression functions generated from the data D n by a learning algorithm are called estimators of g * . We consider a set of regression functions G n that contains all such estimators. Let Q n be the empirical distribution of the sample D n . We define the empirical risk, the empirical risk minimizer and the minimizer of the risk over G n as, respectively, (2.

L n (g) = 1 n n i=1 (g(X i ) -Y i ) 2 , g n =
2)

The aim of this chapter is to provide interpretable learning algorithms that generate G n so that the associated empirical risk minimizer g n is consistent, i.e., g n converges to g * as n → ∞. More precisely, we show the weak consistency of the estimator g n , i.e., its excess of risk

(g * , g n ) = L(g n ) -L(g * ) = E[(g n (X) -g * (X)) 2 ] = o P (1) .
As explained in [START_REF] Lipton | The mythos of model interpretability[END_REF], there are several meanings of interpretability depending on the users desiderata and the expected properties of algorithms. In this chapter, we use the definition of model interpretability from [6]: Interpretability is the degree to which an observer can understand the cause of a decision.

Rule-based algorithms using partitions and coverings

In this chapter we consider algorithms generating interpretable models that are rulebased, such as CART [8], ID3 [START_REF] Quinlan | Induction of decision trees[END_REF], C4.5 [START_REF] Quinlan | C4.5: Programs for machine learning[END_REF], FORS [START_REF] Karalič | First order regression[END_REF], M5 Rules [START_REF] Holmes | Generating rule sets from model trees[END_REF]. In these models, the regression function is explained by the realization of a simple condition, an If-Then statement of the form:

IF (X[i 1 ] ∈ c 1 ) And (X[i 2 ] ∈ c 2 ) And . . . And (X[i k ] ∈ c k ) (2.3) THEN g n (X) = p
where X[i] is the i th coordinate of X and c i ⊆ R is an interval. The If part, called the condition of the rule, or simply the rule, is composed of the conjunction of k ≤ d tests, each of which checking whether a feature (a coordinate of X) satisfies a specified property or not and k is called the length of the rule. The Then part, called the conclusion of the rule, is the estimated value when the rule is activated, i.e., when the condition in the If part is satisfied. The rules are easy to understand and allow an interpretable decision process when k is small. For a review of the best-known algorithms for descriptive and predictive rule learning, see [START_REF] Zhao | Association rule mining: A survey[END_REF] and [23].

Formally, the models generated by such algorithms are defined by a corresponding data-dependent partition P n of R d . Each element of the partition is named a cell and the empirical risk minimizer associated to P n satisfies

g n (x) = A∈Pn n i=1 Y i 1 X i ∈A n i=1 1 X i ∈A 1 x∈A , x ∈ R d . (2.4)
Those algorithms use the dataset D n twice; first, the partition P n = P n (D n ) is chosen according to the dataset, second, this partition and the data are used to compute g n (x) as in (2.4). Note that g n is the empirical risk minimizer among the class G n of all piecewise constant functions over P n denoted G c • P n . The major issue for these algorithms is the model interpretability, which requires a small value for the length k of the rule, whereas the consistency of the estimator is usually proved for conditions implying that k = d, i.e. a high model complexity.

In order to reduce the complexity of the model, we present a method of generating a partition. The idea is to generate a data-dependent covering C n = C n (D n ) of R d rather than a partition. To do so, the dataset D n is used to identify subsets of R d that fulfill some specific conditions (we detail them in the next section). As elements of coverings can overlap, the construction of the subsets fulfilling these conditions can be done separately, which is not doable for the cells of partitions. Using a covering instead of a partition we ensure consistency without a condition on shrinkage of the cells. Moreover, each subset of the covering defines a rule with a small length k. Thus, we obtain a regression function described by a covering formed by simple rules rather than a partition formed by complex rules:

IF (X ∈ r 1 ) And (X ∈ r 2 ) And . . . And (X ∈ r l ) THEN g n (X) = p
where, for j = 1, . . . , l

r j := x : (x[i j,1 ] ∈ c j,1 ) And (x[i j,2 ] ∈ c j,2 ) And . . . And (x[i j,k j ] ∈ c j,k j ) ,
with k j d. To estimate the value p, a partition P(C n ) is generated from the covering C n as an intermediate calculation. Formally, we define the partition generated from any collection of subsets C using the power set 2 C gathering all subsets of C:

ϕ C : R d → 2 C ; ϕ C (x) = {r ∈ C : x ∈ r}.
Then P(C), the partition of c generated from C, is defined as

P(C) := ϕ -1 C (Im(ϕ C )).
We provide a more explicit characterisation of P(C) in the following Proposition :

Proposition 2.1.1. Let C be a finite collection of sets of R d . Then P(C) = r∈ C r \ r∈C\ C r : C ⊆ C \ {∅}.
Proof. By the definition of ϕ C , for any

x ∈ R d , ϕ -1 C (ϕ C (x)) = r∈C:x∈r r\ r∈C:x / ∈r r. Thus A ∈ P(C) = ϕ -1 C (Im(ϕ C )) ⇐⇒ ∃x ∈ R d /A = ϕ -1 C (ϕ C (x)) = r∈C x∈r r \ r∈C x / ∈r r ⇐⇒ ∃ C ⊆ C/A = r∈ C r \ r∈C\ C r and A = ∅.
We have illustrated this transformation P on an example of five elements in Figures 1.7 and 1.8. By using this transformation on a data-dependent covering, C n , we get the partition P(C n ) and the associated estimator (2.4). The major difference compared to an estimator defined on a data-dependent partition is its interpretability. Moreover, using a partition from a data-dependent covering in place of a data-dependent partition generates a more complex partition where cells are not necessarily conjunctions of tests as in (2.3).

Remark 1. If C is a covering of R d , then P(C) is a partition of R d . The relation C = P(C) holds if and only if C is a partition of ∪ r∈C r.
As the construction of a partition from a covering is time consuming, it is important to note that the partition P(C n ) does not need to be constructed. The trick is to identify the unique cell of P(C n ) which contains some x ∈ R d used for calculating the prediction at x. By creating binary vectors of size #C n , whose value is 1 if x fulfilled the rule's condition and 0 otherwise, this cell identification becomes a simple sequence of vectorial operations. Figure 1.9 is an illustration of this process (see Chapter 5 for more details).

All the estimators generated by the data-dependent covering algorithm belong to the class

G n := G c • P(C n ) (2.5)
of piecewise constant functions on the partition

P(C n ) such that ∀g ∈ G n , ∀x ∈ R d , |g(x)| ≤ L.
Hence, from definitions (2.2) we have

g n (x) = A∈P(Cn) n i=1 Y i 1 X i ∈A n i=1 1 X i ∈A 1 x∈A , x ∈ R d , (2.6)
and the risk minimizer over G n is

gn (x) = A∈P(Cn) E[Y 1 X∈A ] P(X ∈ A) 1 x∈A , x ∈ R d . (2.7)
The functions g n and gn are indeed both in G n , although the latter is not computable from the data only.

Remark 4. The definition (2.6) of g n guarantees that ∀x ∈ R d , |g n (x)| ≤ L so that L does not need to be known.

In the following subsection we discuss the important notion of interpretability.

Interpretability

In many fields, such as healthcare, marketing or asset management, decision makers prefer interpretable models rather to models with better accuracy but uninterpretable. As mentioned in [START_REF] Lipton | The mythos of model interpretability[END_REF], there is no rigorous mathematical foundation of the concept. In this chapter, interpretability corresponds to parsimonious characterization of the estimators of g * generated by a given algorithm, i.e. the facility to describe the generated model in human words. Nowadays, the most popular and efficient algorithms for regression, such as Support Vector Machines, Neural networks, Random Forests,. . . are uninterpretable. The lack of interpretability comes from the complexity of the models they generate. We refer to them as black-box models. Usually, these black-box models have an optimal accuracy. We assert that the family of covering algorithms described here, can achieve a better Interpretability-Accuracy trade-off by reducing the complexity of the generated models keeping Accuracy guarantees, i.e., weak consistency.

There exist two ways of constructing interpretable models. The first one is to create black-box models and then to summarize them to create a so-called post-hoc interpretable algorithm. For example, recent researches propose to use explanation models, such as LIME [START_REF] Ribeiro | Why should i trust you?: Explaining the predictions of any classifier[END_REF], DeepLIFT [START_REF] Shrikumar | Learning important features through propagating activation differences[END_REF] or SHAP [START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF], to interpret black-box models. These explanation models try to measure the importance of a feature (a coordinate of X) on the prediction process (see [27] for a survey of existing methods). The second way to interpretability is to use intrinsic interpretable algorithms, it means algorithms that only generate interpretable models, such as rule-based algorithms.

The interpretability of the rule-based estimator is achieved when the length k of each rule is small and there is not too many rules. Considering that an estimate with one rule of length k is as interpretable as the one with the corresponding k rules of length 1, the interpretability gets naturally the additivity property. With this in mind, we are able to quantify the interpretability of an estimator g n generated by a set of rules C n . (2.8)

However in order to prove the consistency of the estimator g n , one usually applies results such as Theorem 13.1 in [28] under the condition of shrinkage of the cells (Condition 13.10 in [28]). Each rule (2.3) must have a length k = d in order to fulfill this sufficient condition without extra condition on the feature space. Then, for large d, the condition becomes uninterpretable. Moreover, as illustrated in Figure 2.1, the number of cells necessary to have an accurate model is very large as the more precise the partition, the more complex the model.

For an estimator defined on a data-dependent covering, each prediction is explained by a small set of fulfilled rules, which are easy to understand, see Table 2.3 in Section 2.4 for an example. Even if the partition generated may be finer and more complex than a classical data-dependent partition, the explanation of the prediction is given by the covering and not the partition, and it remains understandable by humans, as illustrated in Figure 1.9.

Despite the fact that the parsimony of the selected set of rules is not theoretically guaranteed, the redundancy conditions (2.11) and (2.12) described below are heading in the right direction.

We obtain a consistent estimator g n by carefully constructing the covering elements. We can apply none of the classical approaches based on Stone's theorem [START_REF] Stone | Consistent nonparametric regression[END_REF] because the covering is data-dependent nor based on Theorem 13.1 in [28] as Condition 13.10 in [28] forces rules to be complex (k = d). The key notion of this chapter is the notion of suitable data-dependent covering introduced in Section 2.2. Proposition 1.4.3 provides the main tool to prove the weak consistency of suitable data-dependent covering estimators stated in Theorem 2.2.1. Proposition 1.4.3 of independent interest is given in Section 2.3. Finally we apply our approach on covering elements using Random Forest as rule generator in Section 2.4.

Main result

We denote for any

r ⊆ R d such that Q n (r) = 1 n n i=1 1 X j ∈r > 0 E n [Y | X ∈ r] := 1 n n i=1 Y i 1 X i ∈r Q n (r) and V n (Y | X ∈ r) := E n Y 2 | X ∈ r -E n [Y | X ∈ r] 2 .
In the same way, we define

E[Y |X ∈ r] := E[Y 1 X∈r ] P(X∈r) and V[Y |X ∈ r] := E[Y 2 |X ∈ r] -(E[Y |X ∈ r]) 2 .

Significance and coverage conditions

We introduce some conditions on each element of the covering. We use the classical notation x + = max{x, 0} for any x ∈ R. Definition 2.2.1. We call a sequence (C n ) n≥1 of data-dependent coverings of R d suitable if it satisfies the two following conditions:

1. the coverage condition:

(H9)

∃ α ∈ [0, 1/2), ∀r ∈ C n , Q n (r) > n -α a.s., (2.9)
for n sufficiently large;

2. the significance condition: (H10) there exists two sequences β n → 0 and ε n → 0 such that:

C n = C s n ∪ C i n a.s., (2.10)
for n sufficiently large, where the significant subsets C s n are defined by

C s n := r ∈ C n : β n E n [Y |X ∈ r] -E n [Y ] ≥ (V n (Y |X ∈ r) -σ 2 ) + , (2.11)
the insignificant subsets C i n are defined by

C i n := r ∈ C n \ C s n : ε n ≥ (V n (Y |X ∈ r) -σ 2 ) + , (2.12)
and their redundancies satisfy

M (C s n ) m(C s n ) = o P (β -2 n ∧ n 1/2-α ) (2.13) and M (C i n ) m(C i n ) = o P (ε -2 n ∧ n 1/2-α ) . (2.14)
The coverage condition (H9) guarantees that the empirical within group expectation is a good estimation of the within group expectation. Up to our knowledge, the definitions of significant and insignificant elements of a covering in (H10) are new. An element fulfills the significance condition (2.11) if its conditional expectation is sufficiently different from the unconditional expectation. It ensures, in some sense, that the within-group variances of coverings with significant elements are controlled by the between-group variances. The insignificant condition (2.12) guarantees that the conditional variance of the insignificant elements shrinks to the noise variance. Both conditions (H9) and (H10) can be checked for each element of the covering separately. Thus the construction of such subsets can be parallelized, which allow designing algorithms less complex in comparison of usual ones. Remark 5. An easy way to ensure (2.13) and (2.14) is to avoid inclusion between elements of the covering. Let (C n ) be a sequence of coverings that fulfills (H9). We consider 1 ≤ i ≤ #C n any ordering of the covering. If

Q n r i 1≤j≤i-1 r j ≤ γ Q n (r i ) , 1 ≤ i ≤ #C n .
then the cardinality of C n is upper bounded by n α 1-γ for every n sufficiently large. Indeed, by the inclusion-exclusion principle we get

1 = Q n (C n ) = #Cn i=1 Q n (r i \ ∪ 1≤j≤i-1 r j ) ≥ #C n (1 -γ) n -α ,
Thus (2.13) and (2.14) can be checked for any α ∈ [0, 1/4), using the fact that M (C s n ) and M (C i n ) are smaller than n α 1-γ and setting

β n = o P (n -α/2 ) and ε n = o P (n -α/2
). Example 1. The significant condition (2.11) can hold for a subset r with arbitrary diameter that does not satisfy Condition 13.10 of [28]. For instance, consider the case g * = 1 A for some Borel set A such that 0 < P(X ∈ A) < 1. Then r = A is a significant subset as it satisfies the condition (2.11) with high probability for any β n such that n -1/4 = o(β n ) and n sufficiently large. Indeed, from the Strong Law of Large Numbers k n := #{X i ∈ A} ∼ nP(X ∈ A) a.s. as n → ∞. On the one hand, we obtain thanks to several applications of the Central Limit Theorem

E n [Y |X ∈ A] -E n [Y ] ≥ E n [Y |X ∈ A] -E n [Y ] = 1 - k n n + 1 k n n i=1 Z i 1 X i ∈A - 1 n n i=1 Z i = 1 -P(X ∈ A) + O P (n -1/2 ).
On the other hand, we obtain

(V n (Y |X ∈ A) -σ 2 ) + ≤ |V n (Y |X ∈ A) -σ 2 | = 1 k n n i=1 Z 2 i 1 X i ∈A - 1 k n n i=1 Z i 1 X i ∈A 2 -σ 2 = O P (n -1/2 ).
Then

β n E n [Y |X ∈ A] -E n [Y ] -(V n (Y |X ∈ A) -σ 2 ) + ≥ β n 1 -P(X ∈ A) + O P (n -1/2 ) + O P (β -1 n n -1/

Partitioning number

To control the complexity of families of partitions, some tools introduced in [53, Sec. 1.2] are recalled (see also [28,Def 13.1]). Definition 2.2.2. Let Π be a family of partitions of R d .

1. The maximal number of cells in a partition of Π is denoted by M(Π) := sup {#P : P ∈ Π} .

For a set x

n 1 = {x 1 , . . . , x n } ∈ (R d ) n , let ∆(x n 1 , Π) := # {x n 1 ∩ A : A ∈ P} : P ∈ Π
be the number of distinct partitions of x n 1 induced by elements of Π. 3. The partitioning number ∆ n (Π) of Π is defined by:

∆ n (Π) := max x n 1 ∈(R d ) n ∆(x n 1 , Π).
The partitioning number is the maximal number of different partitions of any n points set that can be induced by elements of Π.

Consistency of data-dependent covering algorithms

In the following, we use the classical notion of Donsker class that is discussed in details in Section 2.3.

Theorem 2.2.1. Assume that Q satisfies (H7) and (H8). Let (C n ) be a suitable datadependent covering sequence (i.e., it satisfies (H9) and (H10)) fulfilling the two following conditions:

M(Π n ) ∨ log(∆ n (Π n )) = o(n),
where

Π n := {P(C n (d n )) : d n ∈ S n } for any n ∈ N * ; (H11) ∀n ∈ N * , {c × R, c ∈ C n } ⊆ B,
where B is a Q-Donsker class.

(H12)

Then the estimator g n defined by (2.6) is weakly consistent:

(g * , g n ) = o P (1).
(2.15)

The proof of this theorem is postponed to Section 2.3. This theorem gives us conditions on data-dependent covering algorithms to ensure that the generated empirical risk minimizer g n converges in probability to the regression function g * defined in (2.1). The condition (H11) is a classical one (e.g. [28,Conditions (13.7) and (13.8)]) used to ensure that the family of partitions Π n is not too "complex". It means that the maximal number of cells in a partition, and the logarithm of the partitioning number, are small compared to the sample size. This condition guarantees that the estimation error tends to 0. The conditions (H9), (H10) and (H12) guarantee that the approximation error tends to 0 without any condition on the diameter of the cells.

Proof of Theorem 2.2.1

In order to prove the main theorem, we need some preliminary results based on notions of Q-Donsker class and outer probability.

The outer probability, defined for A ⊆ Ω by

P * (A) := inf P( Ã) : A ⊂ Ã, Ã ∈ A is introduced
: S → R in L 1 (Q), v n f := √ n(Q n f -Qf
) and consider the empirical process indexed by a set F of such functions:

{v n f : f ∈ F}. Definition 2.3.1. [70, Section 19.2] F is called Q-Donsker if the sequence of processes {v n f : f ∈ F} converges
in distribution to a tight limit process in the space ∞ (F).

The limit process is then a Q-Brownian bridge.

Definition 2.3.2. A class of sets B ⊆ B S is called Q-Donsker if I B := {1 A : A ∈ B} is a Q-Donsker class of functions.
We remind that, given two functions l and u, the bracket [l, u] is the set of all functions

f with l ≤ f ≤ u. An -bracket in L 2 (Q) is a bracket [l, u] with u -l L 2 (Q) < . The bracketing number N [ ] (ε, F, L 2 (Q))
is the minimum number of -brackets needed to cover F. (The bracketing functions l and u must have finite L 2 (Q)-norms but need not belong to F.) A simple condition for a class to be Q-Donsker is that N [ ] (ε, F, L 2 (Q)) do not grow too fast to infinity as ε tends to 0. The speed is measured in terms of the bracketing integral defined by

J [ ] (δ, F, L 2 (Q)) = δ 0 log N [ ] (ε, F, L 2 (Q))dε.
[ ] (1, F, L 2 (Q)) < ∞ is Q-Donsker.
A straightforward application of this theorem is the following result.

Lemma 2.3.1. Let C be the set of all hyperrectangles of R d :

C := [a, a + h] ⊆ R d : a ∈ R d , h ∈ R d + ∪ {∅}, then B := {c × R : c ∈ C} is a Q-Donsker class.
Proof. Let ε > 0 and consider the sequence {t i } i∈{0,..., 2d/ε } defined as follows: for any k ∈ {1, . . . , d},

   t 0,k = -∞ ∀i ∈ {1, . . . , 2d/ε }, t i,k = sup{t ∈ R : Q(R k-1 ×]t i-1,k , t[×R d-k × [-L, L]) < ε/2d} t 2d/ε ,k = +∞
From the definition of t i 's we have ∀k ∈ {1, . . . , d}, ∀i ∈ {1, . . . , 2d/ε },

Q R k-1 ×]t i-1,k , t i,k [×R d-k × [-L, L] ≤ ε/2d Q R k-1 ×]t i-1,k , t i,k ] × R d-k × [-L, L] ≥ ε/2d Q R k-1 ×]t 0,k , t i,k ] × R d-k × [-L, L] ≥ iε/2d Q R k-1 ×]t 0,k , t 2d/ε ,k ] × R d-k × [-L, L] ≥ 1 -ε/2d (since 2d/ε ≥ 2d/ε -1) Q R k-1 ×]t 2d/ε ,k , +∞[×R d-k × [-L, L] ≤ ε/2d
Hence, ∀i ∈ {1, . . . , 2d/ε } and ∀k ∈ {1, . . . , d} we have that

Q R k-1 ×]t i-1,k , t i,k [×R d-k × [-L, L] ≤ ε/2d.
Consider now the set of brackets defined by (see Fig 2 .2)

A := [1 d k=1 [t i k +1,k ,t j k -1,k ] , 1 d k=1 ]t i k ,k ,t j k ,k [ ], ∀k ∈ {1, . . . , d}, 0 ≤ i k < j k ≤ 2d/ε .
We have #A = ( 2d/ε ( 2d/ε + 1)/2) d and

d(1 d k=1 [t i k +1,k ,t j k -1,k ]×[-L,L] , 1 d k=1 ]t i k ,k ,t j k ,k [×[-L,L] ) = R d 1 d k=1 ]t i k ,k ,t j k ,k [×[-L,L] -1 d k=1 [t i k +1,k ,t j k -1,k ]×[-L,L] dQ ≤ R d d k=1 1 R k-1 ×(]t i k ,k ,t i k +1,k [∪]tj k -1,k ,t j k ,k [)×R d-k ×[-L,L] dQ ≤ d k=1 Q R k-1 × (]t i k ,k , t i k +1,k [ ∪ ]t j k -1,k , t j k ,k [) × R d-k × R ≤ d (ε/2d + ε/2d) ≤ ε.
The term after the first equality corresponds to the integration of the hatched area in Figure 2.2 and the term after the next inequality corresponds to the integration of the area delimited by the dotted lines. Thus, the L 1 (Q)-size of the brackets is not larger than ε. Since Qf 2 = Qf for every

f ∈ I C = {1 A : A ∈ C}, the L 2 (Q)-size of the brackets is not larger than √ ε. (]t i, 1 , t i + 1, 1 [) /4 t i, 1 t i + 1, 1 t j 1, 1 t j, 1 t i, 2 t i + 1, 2 t j 1, 2 t j, 2 Figure 2.2 -Example of bracket for d = 2. With l = 1 [t i+1,1 ;t j-1,1 ]×[t i+1,2 ;t j-1,2 ] and u = 1 [t i,1 ;t j,1 ]×[t i,2 ;t j,2 ] , for any rectangle A, 1 A ∈ [l, u] if and only if its boundary Ā \ Å is included in the hatched area. Let f ∈ I C . Then ∃ a ∈ R d , h ∈ R d + s.t. f = 1 [a,a+h]×[-L,L]
. We set, for any k ∈ {1, . . . , d}, i * k := max{ι ∈ {0, . . . , 2d/ε } : t ι,k < a k } j * k := min{ι ∈ {0, . . . , 2d/ε } : t ι,k > a k + h k }. There always exist j * k and i * k since the sets {ι ∈ {0, . . . , 2d/ε } : t ι,k < a k } and {ι ∈ {0, . . . , 2d/ε } : t ι,k > a k + h k } are not empty (they contain respectively 0 and 2d/ε ) and, by construction, j * k > i * k . Moreover,

1 d k=1 [t i * k +1 ,t j * k -1 ]×[-L,L] ≤ 1 [a,a+h]×[-L,L] ≤ 1 d k=1 ]t i * k ,t j * k [×[-L,L]
and

[1 d k=1 [t i * k +1 ,t j * k -1 ]×[-L,L] , 1 d k=1 ]t i * k ,t j * k [×[-L,L] ] ∈ A. Thus, ∀f ∈ I C , ∃[l, u] ∈ A such that l ≤ f ≤ u. It follows that N [ ] ( √ ε, I C , L 2 (Q)) ≤ 2d/ε ( 2d/ε +1) 2 d
. Hence,

J [ ] (1, I C , L 2 (Q)) < ∞.
According to Theorem 2.3.1, this guarantees that I C is a Q-Donsker class. Now, with Qf := f dQ and

Q n f := f dQ n , for any f ∈ L 1 (Q), if F is a Q-Donsker class of functions, then the empirical process (( √ n(Q n f -Qf )) f ∈F )
n∈N is asymptotically tight as a sequence of maps with values in ∞ (F) (this is a consequence of Prohorov's Theorem adapted to this framework -see Theorem 18.12 in [START_REF] Van Der Vaart | Asymptotic statistics[END_REF]). Keeping in mind that a compact set in ∞ (F) is bounded, we have: Theorem 18.12] Let F be a Q-Donsker class of functions. Then

Proposition 2.3.1. [70,
Q n -Q F = O P * (n -1/2 ),
where for any v :

F → R, v F = sup f ∈F |v(f )|. Remark 7. If B ⊆ B S is a Q-Donsker class of sets, where B S is the Borel set on S, then Q n -Q B = O P * (n -1/2 ),
where for any v :

B → R, v B = sup A∈B |v(A)|. Remark 8. It can be checked that if (Z n ) n∈N is a sequence of non-negative random vari- ables, (a n ) n∈N ∈ (R + ) N such that a n = o P (1) and (M n ) n∈N is a sequence of maps such that M n = O P * (1) and Z n ≤ a n M n for any n, then Z n P -→ n→+∞ 0.
The usual notion of boundedness in probability for sequences of random variables need be generalized because sequences of maps are to be considered, with values in metric spaces which are not Euclidean spaces (thus bounded and closed sets need not be compact) and which are not guaranteed to be measurable. We need involve the outer probability P * .

Empirical estimation of conditional expectations

We shall also use the following proposition, which is inspired by the work of [25]

(Proposition 3.2). Proposition 2.3.2. Let B ⊆ B S and let F B := {f 1 A : f ∈ F, A ∈ B} where F is a set of functions in L 1 (Q) uniformly bounded. If B and F B are Q-Donsker classes then for any α ∈ [0, 1/2) and with B n := {A ∈ B, Q n (A) ≥ n -α }, sup f ∈F sup A∈Bn E n [f | A] -E [f | A] = O P * (n α-1/2 ). Proof. Let ε > 0. First, for any f ∈ F and A ∈ B n , since Q n (A) > 0 and then Q(A) > 0, |E n [f | A] -E [f | A]| = A f dQ n Q n (A) -A f dQ Q(A) = Q(A) A f dQ n -A f dQ + (Q(A) -Q n (A)) A f dQ Q(A)Q n (A) ≤ A f dQ n -A f dQ Q n (A) + (Q(A) -Q n (A)) A f dQ Q(A)Q n (A)
.

(2.16)

Now, according to Proposition 2.3.1,

sup f ∈F , Ã∈B Ã f dQ n - Ã f dQ = O P * (n -1/2 )
and sup

Ã∈B Q n ( Ã) -Q( Ã) = O P * (n -1/2 ).
Thus, According to Remark 9, there exists M > 0 such that for any n large enough,

P * sup f ∈F , Ã∈B Ã f dQ n - Ã f dQ > M n -1/2 < ε 2
and

P * sup Ã∈B Q n ( Ã) -Q( Ã) > M n -1/2 < ε 2
so that P * (Ω n ) ≥ 1 -ε with Ω n := sup f ∈F , Ã∈B Ã f dQ n - Ã f dQ ≤ M n -1/2 sup Ã∈B Q n ( Ã) -Q( Ã) ≤ M n -1/2 .
Then (2.16) yields, with c := sup

f ∈F ,x∈S |f (x)| < ∞ and since Q n (A) ≥ n -α , for n large enough, in the event Ω n , sup f ∈F ,A∈Bn E n [f | A] -E [f | A] ≤ M n α-1/2 (1 + c), since A f dQ Q(A) ≤ c.
Finally, it has been proven that ∀ε > 0, ∃M > 0, ∃N ∈ N * /∀n ≥ N,

P * sup f ∈F ,A∈Bn |E n [f | A] -E [f | A]| > M n α-1/2 < ε
and then ∀ε > 0, ∃M > 0 such that

lim sup n→∞ P * sup f ∈F ,A∈Bn |E n [f | A] -E [f | A]| > M n α-1/2 ≤ ε
which, together with Remark 9 again, proves the proposition.

Corollary 2.3.1. Let B ⊆ B S be a Q-Donsker class. If Y is bounded then for any i ∈ N and any α ∈ [0, 1/2), with B n := {A ∈ B, Q n (A) ≥ n -α } we have sup A∈Bn E n Y i | (X, Y ) ∈ A -E Y i | (X, Y ) ∈ A = O P * (n α-1/2 ), (2.17)
and sup

A∈Bn |V n [Y | (X, Y ) ∈ A] -V [Y | (X, Y ) ∈ A]| = O P * (n α-1/2 ). (2.18)
Proof of (2.17). Let L = ess sup Y , i ∈ N, and f i ∈ L 1 (Q) be defined by

f i : R d × [-L, L] → [-L i , L i ] (x, y) → y i .
f i is bounded and {f i } is finite thus Donsker. The result is then a straightforward application of Proposition 2.3.2.

Proof of (2.18). This part follows from (2.18) since Y is bounded and

V n [Y | (X, Y ) ∈ A] := E n Y 2 | (X, Y ) ∈ A -E n [Y | (X, Y ) ∈ A] 2 .
It seems that the result of Corollary 2.3.1, which is of independent interest, does not appear as such in the existing literature. As a first application of Corollary 2.3.1, we show that any partition with shrinking cell diameters is a suitable covering. We define the diameter of a cell r as Diam(r) = sup x∈r, x ∈r x -x , where • is any norm of R d .

Proposition 2.3.3. Consider a sequence (P n ) n∈N of data-dependent partitions, that satisfies the coverage condition (2.9) and such that

n∈N * r∈Pn (r × R) is a.s. a Q-Donsker class. If
max r∈Pn |V n (Y |X ∈ r) -V(Y | X ∈ r)| = O P (n α-1/2 ). (2.20) Moreover V(Y | X ∈ r) = V(g * (X) | X ∈ r) + σ 2 .
Thus, as the redundancy condition (2.14) is automatically satisfied for cells of a partition, the desired result will follow if we check that

ε n := max r∈Pn (V n (Y |X ∈ r) -σ 2 ) + converges to 0.
From (2.20) we remark that

ε n ≤ max r∈Pn V(g * (X) | X ∈ r) + O P (n α/2-1/4 ) .
For all n, if r ∈ P n , then r × R ∈ B S . We denote X r and X r two independent variables distributed as X given that X ∈ r. We obtain 2 . Thus, if we denote w the modulus of continuity of g * , we get

V(g * (X) | X ∈ r) = V(g * (X r )) = 1 2 V g * (X r ) -g * (X r ) ≤ 1 2 E (g * (X r ) -g * (X r ))
V(g * (X) | X ∈ r) ≤ 2 -1/2 w(Diam(r)).
By uniform continuity, the condition (2.19) implies that

ε n ≤ 2 -1/2 max r∈Pn w(Diam(r)) + O P (n α/2-1/4 ) = o P (1) .
Thus, from (2.12), each cell which is not significant is insignificant and the corresponding covering sequence is suitable.

Remark 10. The condition of uniform continuity of g * in Proposition 2.3.3 may be simply raised. Indeed, from [28, Corollary A.1], g * can be approximated arbitrarily closely in

L 2 (Q X ) by functions of C ∞ 0 (R d )
where Q X is the marginal distribution of X.

Estimation-approximation decomposition

The excess loss (2.1) can be decomposed into two terms using the following lemma:

Lemma 2.3.2 (Lemma 10.1 of [28]). Let G n be a class of functions g :

R d → [-L, L] depending on the data D n = ((X 1 , Y 1 ), . . . , (X n , Y n )). If g n satisfies (2.2) then (g * , g n ) ≤ 2 sup g∈Gn |L n (g) -L (g)| + inf g∈Gn E (g(X) -g * (X)) 2 .
Hence, to prove (2.15) it is sufficient to prove that: The two terms have opposite behaviors. Indeed, if G n is not too complex the empirical loss will be close to the loss uniformly over G n . Thus, the error due to the minimization of the empirical loss instead of the loss will be small. On the other hand, the loss cannot be better than for the best function of G n . So, G n must be complex enough. It is the classical Approximation/Estimation trade-off.

sup g∈Gn |L n (g) -L(g)| = o P (1). ( 2

Approximation Error

In this subsection, we prove (2.22) using hypotheses (H7), (H8), (H9), (H10) and (H12).

P(C i\s n ) = r∈ C r \ r∈C i\s n \ C r : C ⊆ C i\s n = r∈ Ci (r \ c s n ) \ r∈C i n \ Ci (r \ c s n ) : Ci ⊆ C i n = r∈ Ci r \ r∈C i n \ Ci r \ c s n : Ci ⊆ C i n = A \ c s n : A ∈ P(C i n ) . ( 2
A∈P(C s n )∪P(C i\s n ) E[Y |X ∈ A]1 A ,
we have gn ∈ G n and

inf g∈Gn E (g(X) -g * (X)) 2 ≤ E (g n (X) -g * (X)) 2
Thus, to prove (2.22), it suffices to show that W n = o P (1) where

W n := E (g n (X) -g * (X)) 2 .
We will repeatedly make use of the following equalities:

E[g * (X) | X ∈ r] = E[Y | X ∈ r] , ∀r ⊆ R d . (2.24)
and

V(Y |X ∈ r) = V(g * (X)|X ∈ r) + σ 2 , ∀r ⊆ R d . (2.25)
Let us first remark that

W n = E     A∈P(C s n )∪P(C i\s n ) E [Y | X ∈ A] 1 A (X) -g * (X)   2   = A ∈P(C s n )∪P(C i\s n ) E     A∈P(C s n )∪P(C i\s n ) E [g * (X) | X ∈ A] 1 A (X) -g * (X)   2 1 A (X)   = A ∈P(C s n )∪P(C i\s n ) E (E [g * (X) | X ∈ A ] -g * (X)) 2 1 A (X) = A ∈P(C s n )∪P(C i\s n ) E (E [g * (X) | X ∈ A ] -g * (X)) 2 X ∈ A × P (X ∈ A ) (2.26)
which shows that W n is a within-group variance for the variable g * (X) and the groups P(C s n ) ∪ P(C i\s n ). According to the decomposition

W n = A∈P(C s n ) E (E [Y | X ∈ A] -g * (X)) 2 X ∈ A P (X ∈ A) W s n + A∈P(C i\s n ) E (E [Y | X ∈ A] -g * (X)) 2 X ∈ A P (X ∈ A) W i\s n , it is sufficient to prove that W s n P ---→ n→∞ 0 and W i\s n P ---→ n→∞ 0.
To deal with W s n , we start from the decomposition of the total variance into the within-group and the between-group variances:

W s n = E[(g * (X) -E[g * (X)]) 2 1 c s n (X)] -B s n ≤ V(g * (X) -B s n (2.27)
where

B s n := A∈P(C s n ) (E [g * (X) | X ∈ A] -E [g * (X)]) 2 P (X ∈ A) .
The between group variance B s n will be lower estimated by a function of W s n from which a lower bound of W s n will follow. The key point of this lower bound is to use the definition of C s n in (H4). To make the terms controlled by this significant condition appear, we lower bound B s n by a sum over the elements of C s n instead of elements of P(C s n ) and the expectations is replaced by empirical expectations. After applying the inequality provided by the significant condition we'll have to do the reverse operation to make W s n appear again.

Let us first lower bound B s n by a sum over the elements of C s n instead of elements of P(C s n ) and replace the expectations by empirical expectations:

B s n = r∈C s n A∈P C s n (r) 1 #ϕ C s n (A) (E [Y | X ∈ A] -E [g * (X)]) 2 P (X ∈ A) ≥ r∈C s n 1 M (C s n , r) A∈P C s n (r) (E [Y | X ∈ A] -E [g * (X)]) 2 P (X ∈ A) ≥ 1 M (C s n ) r∈C s n A∈P C s n (r) (E [Y | X ∈ A] -E [g * (X)]) 2 P (X ∈ A | X ∈ r) P (X ∈ r) ≥ 1 M (C s n ) r∈C s n   A∈P C s n (r) E [Y | X ∈ A] P (X ∈ A | X ∈ r) -E [g * (X)]   2 P (X ∈ r) = 1 M (C s n ) r∈C s n E [Y | X ∈ r] -E [g * (X)] 2 P (X ∈ r) ≥ 1 M (C s n ) r∈C s n V 2 n,r×R -∆ n P(X ∈ r) (2.28)
where we applied Jensen's inequality for the third to last inequality and where

∆ n := sup A∈Bn {V 2 n,A -U 2 A }
with for any A ∈ B,

U A := E [Y | (X, Y ) ∈ A] -E [g * (X)] V n,A := E n [Y | (X, Y ) ∈ A] -E n [Y ]
and

B n = {A ∈ B s.t. Q n (A) > n -α }.
Continuing (2.28) with the definition of C s n in (H4) in mind,

B s n ≥ 1 M (C s n ) r∈C s n β -2 n (V n (Y |X ∈ r) -σ 2 n -∆ n P(X ∈ r) ≥ 1 M (C s n ) r∈C s n β -2 n (V n (Y |X ∈ r) -σ 2 -β -2 n |σ 2 n -σ 2 | -∆ n P(X ∈ r). Since W s n = A∈P Cn (C s n ) V(g * (X)|X ∈ A)P (X ∈ A),
∆ n := sup A∈Bn V(Y |(X, Y ) ∈ A) -V n (Y |(X, Y ) ∈ A)
and write

B s n ≥ 1 M (C s n ) r∈C s n β -2 n (V(Y | X ∈ r) -σ 2 -∆ n ) -β -2 n |σ 2 n -σ 2 | -∆ n P(X ∈ r) = 1 M (C s n ) r∈C s n β -2 n (V(g * (X) | X ∈ r) -∆ n ) -β -2 n |σ 2 n -σ 2 | -∆ n P(X ∈ r) by (2.25) = β -2 n M (C s n ) × r∈C s n E E [Y | X ∈ r] -g * (X) 2 | X ∈ r -(∆ n + |σ 2 n -σ 2 | + β 2 n ∆ n ) P(X ∈ r) ≥ β -2 n M (C s n ) × r∈C s n A∈P C s n (r) E E [Y | X ∈ r] -g * (X) 2 | X ∈ A P(X ∈ A) -(β -2 n ∆ n + β -2 n |σ 2 n -σ 2 | + ∆ n ) since r∈C s n P(X ∈ r) ≤ M (C s n ) ≥ β -2 n M (C s n ) × r∈C s n A∈P C s n (r) E E [Y | X ∈ A] -g * (X) 2 | X ∈ A P(X ∈ A) -(β -2 n ∆ n + β -2 n |σ 2 n -σ 2 | + ∆ n ) ≥ β -2 n m(C s n ) M (C s n ) × A∈P(C s n ) E E [Y | X ∈ A] -g * (X) 2 | X ∈ A P(X ∈ A) -(β -2 n ∆ n + β -2 n |σ 2 n -σ 2 | + ∆ n ) = β -2 n m(C s n ) M (C s n ) W s n -(β -2 n ∆ n + β -2 n |σ 2 n -σ 2 | + ∆ n ).
Together with (2.27), this yields

W s n ≤ V(g * (X)) + β -2 n ∆ n + β -2 n |σ 2 n -σ 2 | + ∆ n 1 + β -2 n m(C s n ) M (C s n )
• Under (H6), Corollary 1.4.1 applies and we obtain

∆ n = sup A∈Bn {(V n,A -U A )(V n,A + U A )} ≤ sup A∈Bn E n [Y | (X, Y ) ∈ A] -E[Y | (X, Y ) ∈ A] + E[g * (X)] -E n [Y ] × 4L ≤ 4L × sup A∈Bn E n [Y |(X, Y ) ∈ A] -E[Y |(X, Y ) ∈ A] + E[g * (X)] -E[g * (X)] + E[g * (X)] E[Y ] -E n [Y ] ≤ 4L × O P * (n α-1/2 ) + O P (n -1/2 ) = O P * (n α-1/2 )
Corollary 1.4.1 also yields

∆ n = O P * (n α-1/2 ).
Since it is moreover assumed that |σ 2 n -σ 2 | = O P (n α-1 2 ), (2.13) of Condition (H10) and Remark 8 lead to

W s n P ---→ n→∞ 0.
To deal with W i\s n , remember (2.23) and write

W i\s n = A∈P(C i\s n ) E (E [Y | X ∈ A] -g * (X)) 2 1 A (X) = A∈P(C i n ) E (E [Y | X ∈ A \ c s n ] -g * (X)) 2 1 A\c s n (X) ≤ A∈P(C i n ) E (E [Y | X ∈ A] -g * (X)) 2 1 A\c s n (X) ≤ A∈P(C i n ) E (E [Y | X ∈ A] -g * (X)) 2 1 A (X) ≤ 1 m(C i n ) r∈C i n A∈P C i n (r) E (E [Y | X ∈ A] -g * (X)) 2 1 A (X) ≤ 1 m(C i n ) r∈C i n A∈P C i n (r) E (E [Y | X ∈ r] -g * (X)) 2 1 A (X) ≤ 1 m(C i n ) r∈C i n E (E [Y | X ∈ r] -g * (X)) 2 1 r (X) = 1 m(C i n ) r∈C i n E (E [Y | X ∈ r] -g * (X)) 2 X ∈ r P (X ∈ r) = 1 m(C i n ) r∈C i n V(Y |X ∈ r) -σ 2 P (X ∈ r) by (2.24) and (2.25) ≤ 1 m(C i n ) r∈C i n V n (Y |X ∈ r) -σ 2 n + |σ 2 n -σ 2 | + ∆ n P (X ∈ r) ≤ 1 m(C i n ) r∈C i n ε 2 n + |σ 2 n -σ 2 | + ∆ n P (X ∈ r) under (H4) ≤ M (C i n ) m(C i n ) ε 2 n + |σ 2 n -σ 2 | + ∆ n P ---→ n→∞ 0
under (2.14) of Condition (H10) and with Remark 8.

Estimation Error

In this subsection we prove (2.21) using hypotheses (H7), (H8) and (H11). Recall from (2.5) that G n is the set of piecewise constant functions with values in [-L, L] on the elements of the partition P(C n (D n )). Then, with the definition of Π n in (H11) in mind,

sup g∈Gn |L n (g) -L (g)| ≤ sup g∈Gc•Πn |L n (g) -L (g)| ,
where G c is the set of constant functions R d → [-L, L] and

G c • Π n := g : R d → R : g = A∈Pn f A 1 A , P n ∈ Π n , f A ∈ G c .
The following is based on the same idea as [28, Theorem 13.1].

According to [28, Theorem 9.1 and Problem 10.4] we have,

P sup g∈Gc•Πn |L n (g) -L (g)| > ε ≤ 8E N 1 ε 32L , G c • Π n , X n 1 exp -nε 2 128.(4L 2 ) 2 , (2.29) where X n 1 = {X 1 , . . . , X n }. Here N 1 (ε, G c • Π n , X n 1 )
is the random variable corresponding to the minimal number N ∈ N such that there exists functions g 1 , . . . , g N : R d → [-L, L] with the property that for every g ∈ G c • Π n there is a j ∈ {1, ..., N } such that

1 n n i=1 |g(X i ) -g j (X i )| ≤ ε.
This number is called the ε-covering number of G c • Π n . It can be interpreted as the complexity of the class. Then using [28,Lemma 13.1] we have

N 1 ε 32L , G c • Π n , X n 1 ≤ ∆(Π n ) sup z 1 ,...,zm∈{X 1 ,...,Xn},m≤n N 1 ε 32L , G c , z m 1 M(Πn)
,

According to [28, Lemma 9.2] for any set of function G and any sample z m 1 we have

N 1 ε 32L , G, z m 1 ≤ M 1 ε 32L , G, z m 1 ,
where

M 1 (ε, G, z m 1 ) is the maximal N ∈ N such that there exists functions g 1 , . . . , g N ∈ G with 1 n m i=1 |g j (z i ) -g k (z i )| ≥ ε, for all 1 ≤ j < k ≤ N . It is called L 1 ε-packing of G on z m 1 .
M 1 (ε, G c , z m 1 ) = 2L ε .
Finally, sup z 1 ,...,zm∈{X 1 ,...,Xn},m≤n

N 1 ε 32L , G c • Π n , z m 1 ≤ ∆(Π n ) 64L 2 ε M(Πn)
.

(2.30)

According to (2.29) and (2.30) we have:

P sup g∈Gn 1 n n i=1 |g(X i ) -Y i | 2 -E |g(X) -Y | 2 > ε ≤ 8∆ n (Π n ) 64L 2 ε M(Πn) exp - nε 2 128.(4L 2 ) 2 and since 8∆ n (Π n ) 64L 2 ε M(Πn) exp - nε 2 2048L 4 ≤ 8 exp log ∆ n (Π n ) + M(Π n ) log 64L 2 ε - nε 2 2048.L 4 ≤ 8 exp   - n L 4   ε 2 2048 - log ∆ n (Π n )L 4 n - M(Π n )L 4 log 64L 2 ε n     ,
this concludes the proof of (2.21) and of Theorem 2.2.1.

Illustrations

In this section we propose a simple algorithm to generate a suitable sequence of datadependent coverings using the Random Forests algorithm (RF) of [7] as rule generator. The interest is double; first, it shows that there exists a sequence of suitable datadependent coverings in practice as in Definition 2.2.1. Second, it proves the consistency of a rule-based estimator generated from RF as soon as the condition (H11) on the complexity of RF is satisfied. Until now there are few results about the consistency of an estimator generated by RF, we may cite [14,[START_REF] Scornet | Consistency of random forests[END_REF].

Let C be the set of all hyperrectangles of R d defined by

C := [a, a + h] ⊆ R d : a ∈ R d , h ∈ R d + ∪ {∅}.
Lemma 2.3.1 ensures that that any set of rules C n such that C n ⊆ C, which is the case of sets of rules generated by RF, fulfills (H12).

Covering Algorithm

The proposed algorithm generates an estimator using data-dependent coverings. It is decomposed into four steps.

1. Generation of RF with m tree trees with a maximal depth controlled by a fixed maximal number of rules generated by RF1 .

2. Extraction of all significant and insignificant rules according to (H9) and (H10) from all nodes and leaves of all trees generated by RF that have a length lower than or equal to k max ∈ {1, . . . , d} for a chosen α ∈ (0, 1/2),

β n = n α/2-1/4 , ε n = β n σ n (Y ),
where σ n (Y ) is the empirical standard deviation of Y .

3. Selection of a minimal set of rules using Algorithm 3. A rule is added to the current set of rules if and only if it has at least a rate γ ∈ (0, 1) of points not covered by the current set of rules. The smaller γ the smaller the number of rules #C n2 .

4. If the selected set of rules does not form a covering, generation of a unique no-rule that is one of the smallest hyperrectangles satisfying (H9) containing the remaining points.

Remark 11. We do not use step 4 in any of the examples treated below as we already obtain a covering at the third step. If the no-rule had to be added to ensure a covering, one should check that the no-rule is either a significant or an insignificant rule in order to obtain a consistent Covering Algorithm.

Algorithm 3: Selection of minimal set of rules Input:

-the rate 0 < γ < 1; -a set of significant rules S; -a set of insignificant rules I; Output:

-a minimal set of rules C n ;

1 C n ← arg max r∈S Q n (r); 2 S ← S \ C n ; 3 while r∈Cn Q n (r) < 1 do 4 r * ← arg max r∈S Q n (r); 5 if Q n (r * ∩ {∪ r∈Cn r}) ≤ γ Q n (r * ) then 6 C n ← C n ∪ r * ; 7 S ← S \ r * ; 8 if #S = 0 then 9 Break ; 10 end 11 if r∈Cn Q n (r) < 1 then 12 while r∈Cn Q n (r) < 1 do 13 r * ← arg min r∈I V n (Y |X ∈ r); 14 if Q n (r * ∩ {∪ r∈Cn r}) ≤ γ Q n (r * ) then 15 C n ← C n ∪ r * ; 16 I ← I \ r * ;

Artificial data

Here we consider the same data set as in [20]. We generate n = 5, 000 data following the regression setting Y = g * (X) + Z, where d = 100 (the dimension of X) and

g * (X) = 9 3 j=1 exp -3 (1 -X j ) 2 -0.8 exp (-2 (X 4 -X 5 )) + 2 sin 2 (π • X 6 ) -2.5 (X 7 -X 8 ) , (2.31)
and Z ∼ N (0, σ 2 ). The value of σ > 0 was chosen to produce a two-to-one signal-to-noise ratio. The variables were generated from a uniform distribution on {0/10, . . . , 9/10}. It is important to notice that only the first eight variables are informative; the 92 others are just noise. Coefficients multiplying each of the terms in g * were chosen to ensure that variables have approximately equal influence. In order to evaluate the error without including the error of the noise, we consider the following criterion

M SE * = E Q |g * (X) -g n (X)| 2 .
We approximate it using 50, 000 test observations sampled independently from Q.

Execution

We run M = 100 simulations. For each simulation we set the maximal number of rules generated by the Random Forest (RF) at 20, 000 and the number of trees at m tree = 100. The maximal length of a rule is fixed at k max = 3. And we set α = 1/2 -1/100 and γ = 0.95. We compare results with the ones of RF and RuleFit [20].

Results

We calculate the M SE * of each algorithm for each experience and sum up it in Figure 2.3. All results are described in Table 2.1.

Figures 2.4 and 2.5 display the frequency of occurrence of a variable in at least one rule of the selected set of rules and the average occurrence of a variable in the selected set of rules respectively. We emphasize that only the informative variables are involved in the selected rules (excepted X 41 which appears one time in 100 simulations). It means that the support of g * is well identified.

Nevertheless, the linear term in (2.31) cannot be well fitted by a finite set of rules. This setting is highly favorable to RuleFit that is the only tested algorithm including linear components. However, RuleFit involves at least 10 and up to 40 linear components (see Table 2.1). Its accuracy is high but many noise variables are included in its generated model. Hence the a posteriori analysis of the importances of the variables and rules of the generated model is crucial, see Section 9.1.2 of [20].

Real data

In this example we use the well-known Boston housing dataset. It consists in n = 506 neighborhoods in the Boston area and 14 statistics for each neighborhood describes in Table 2.2 (see Table IV

Execution

We set the maximal number of rules generated by the Random Forest (RF) at 20, 000 and the number of trees at m tree = 100. It generates 8, 490 rules and the RF estimator has an interpretability index of Int(g n ) = 29, 524 according to (2.8). Among these rules 4, 066 have a length lower than or equal to k max = 3. In this application the real value of σ 2 is unknown. We estimate it by σ 2 n the minimal variance of the rules fulfilling the covering condition (2.9). We have σ 2 n = 0.815. Considering σ 2 = σ 2 n and α = 1/2 -1/100, the Covering Algorithm described in Section 2.4.1 extracts 1, 306 rules that are significant according to (2.11) and 2.083 that are insignificant according to (2.12). Then, the selection process (Algorithm 3), with γ = 0.95, extracts a set of 6 significant rules, which cover 99% of the data, and adds 2 insignificant rules R4 and R7 to cover all data. The interpretability index obtained by the covering estimator is Int(g n ) = 20. We compare results with the ones of RF and RuleFit.

Results

Regarding the accuracy on the test set, RF has a M SE of 10. [START_REF] Margot | Consistent regression using data-dependent coverings[END_REF]

Comments

This application on real data emphasizes that data-dependent coverings are very efficient to generate an interpretable rule-based model. Using Table 2.2 we are able to translate in natural language the significant rules in Table 2.3, accordingly with the definition of interpretability of [6].

-Rules R1 and R2 indicate that the LST AT variable, which represents the percent of lower status population, is inversely related to the median house price. This relation is easily identified by the linear component of RuleFit, which corresponds to the unique variable LST AT (See Table 2.4). -Rules R3, R5 and R6 show that for LST AT close to the median, the number of rooms RM is determining the median house price. -Rule R8 can be interpreted by the fact that a very high proportion of non-retail business acres per town IN DU S has a negative influence on the median house price Y that cannot be offset by a percentage of the lower status LST AT and a pupil-teacher ratio P T RAT IO lower than the first quartile.

The variables DIS and CRIM seem superfluous as the associated rules R3, R5 and R6 cover most of their range.

Conclusion

In this chapter, we provide a general setting for studying the consistency of interpretable rule-based estimators. The novelty is to introduce the notion of covering composed by two kinds of sets, the significant and the insignificant ones. The significant sets are thought as interpretable sets by construction. The insignificant ones are thought as small sets in which variances tend to zero. We provide Covering Algorithm that extracts from any rule generator a suitable data-dependent covering. We apply it to RF and we compare its result with the ones of RF and RuleFit [20]. The loss of accuracy in the prediction is the cost to pay to have an interpretable model according to our definition of interpretability. Monte Carlo experiments in section 2.4.2 show that Covering Algorithm, seeking interpretability, is identifying the support of the regression function as a byproduct. The loss of accuracy of Covering Algorithm may be due to the conflict between model identification and regression estimation identified by [START_REF] Yang | Can the strengths of aic and bic be shared? a conflict between model identification and regression estimation[END_REF]. It is worthwhile to mention that despite its loss of accuracy, Covering Algorithm is still weakly consistent.

Our methodology based on coverings is very effective for generating interpretable models. The use of RF as the rule-generator of Covering Algorithm is questionable; in Section 2.4.2, we pointed out the possible negative effect of the randomization procedure in RF for identifying informative variables. In Section 2.4.3, we observed some rules generated by RF with length potentially artificially too high. In Chapter 3, we present an algorithm that generates significant, insignificant rules and a suitable sequence of data-dependent coverings satisfying (H11) on its own. The difficulty we encounter is to ensure that the generated rules cover all the data and the adaptation in cases of unknown variance estimated as in Section 2.4.3.

"Education is an admirable thing, but it is well to remember from time to time that nothing that is worth knowing can be taught." Oscar Wilde.

Chapter 3

Rule Induction Covering Estimator: A New Data Dependent Covering Algorithm

Introduction

The massive use of machine learning algorithms in current life and sensitive fields such as medicine, criminal justice system, autonomous cars, asset management, has caused users to ask questions on the used algorithms functionalities and how to understand their decisions. Indeed, as related in [START_REF] Yudkowsky | Artificial intelligence as a positive and negative factor in global risk[END_REF], using algorithms with incomprehensible models output may be risky even if they are very efficient. This kind of algorithms are called black-box models because their internal workings are unknown. To avoid these risks, some suggest to use interpretable algorithms. But, as explained in [START_REF] Lipton | The mythos of model interpretability[END_REF], there are several meanings of interpretability depending on the users desiderata and the expected properties of algorithms. For example an algorithm used in criminal justice system must be ethic as explain in [15]. In this chapter, we use the definition of model interpretability from [6]: Interpretability is the degree to which an observer can understand the cause of a decision.

There are two common solutions to generate an interpretable model: intrinsic interpretable algorithms and post-hoc interpretable algorithms. The post-hoc interpretability consists in considering a black-box algorithm and trying to interpret it using algorithms which measure the importance of each explanatory variables (features) in the decision. The most popular ones are LIME [START_REF] Ribeiro | Why should i trust you?: Explaining the predictions of any classifier[END_REF], DeepLIFT [START_REF] Shrikumar | Learning important features through propagating activation differences[END_REF] or SHAP [START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF]. See [27] for a survey of existing methods. The intrinsic interpretability, consisting in considering intrinsically interpretable algorithms. It means algorithms which output models easy to understand for humans. There are two common families of algorithms: tree-based algorithms, and rule-based algorithms. A tree may always be turned into a set of rules as in [Quinlan et al.] and [START_REF] Kramer | Structural regression trees[END_REF]. Hence, without loss of generality we focus on set of rules generator algorithms. On a feature space R d , a rule is an If-Then statement of the form:

IF x ∈ r (3.1) THEN Prediction = p
where r ⊂ R d . In this chapter all r considered are hyperrectangles:

r = c 1 × • • • × c d ,
where for all j, c j ⊆ R is an interval. The If part, called the condition of the rule r, is then composed of l ≤ d tests, each of which checking whether a feature (a coordinate of x) satisfies a specified property or not and k (the number of c j 's which are not R) is called the length of the rule and is denoted by (r):

(r) = d -#{1 ≤ j ≤ d; c j = R}. (3.2)
The Then part, called the conclusion of the rule, is the predicted value when the rule is activated, i.e., when the condition in the If part is satisfied. The rules are easy to understand and allow an interpretable decision process when l is small. For a review of the best-known algorithms for descriptive and predictive rule learning, see [START_REF] Zhao | Association rule mining: A survey[END_REF] and [23].

By an abuse of notation we do not distinguish between a rule and the hyperrectangle which defines its condition in the following.

The main issue is that a rule is interpretable only if the condition is easy to understand. For hyperrectangle cells, this means that each generated rule has few features implied in its condition. For instance, tree-based algorithms such as CART [8], ID3 [START_REF] Quinlan | Induction of decision trees[END_REF], C4.5 [START_REF] Quinlan | C4.5: Programs for machine learning[END_REF], are interpretable if their maximal depth is small. But theoretical results such as Stone's Theorem (65 or 28, Theorem 13.1) requires a shrinkage, in probability, of the cells of the generated partition. Then the depths of the trees have to equal the dimension of the feature space for large enough sample sizes. Thus, each rule has a condition implying all features and it is uninterpretable if the dimension is high. In order to make this argument rigorous, we define the interpretability index of a rule based algorithm as follows.

Definition 3.1.1. The interpretability index Int of a rule-based algorithm is the sum of the lengths of the rules involved in the predictor.

That one can construct cells implying all features by intersecting d rules of unit length motivates the definition of Int. We say that an algorithm is interpretable when Int remains reasonable. Tree-based algorithms that need many trees with shrinking diameters (in probability) cannot be interpretable according to our definition.

Using rule-based algorithms for a regression is challenging and not been well investigated. There are few algorithm and none of them has had a significant impact. We may cite FORS [START_REF] Karalič | First order regression[END_REF] or CUBIST. Most of rule-based algorithms used for a regression setting, discretize the variable Y to bring back to a classification setting. Recently the focus is on the ensemble techniques such as RuleFit [20], Ender [13].

In this chapter we present a deterministic predictive rule-based algorithm for regression settings that generates highly interpretable models and predictors that are accurate with theoretical guarantee as consistency. This algorithm is an update of the RIPE algorithm presented in Chapter 5 based on the data-dependent coverings introduced in Chapter 2. In Chapter 2 we have presented an extraction of rules generated by Random Forests [7].

Preliminaries

Regression setting

Let (Ω, A, P) be a probability space and let (X, Y ) be random variables in R d × R of unknown distribution Q. We consider the following regression setting

Y = g * (X) + Z,
where E[Z] = 0, V(Z) = σ 2 and g * is a measurable function from R d to R. We assume that Z is independent of X and Y is bounded in absolute value by some unknown L > 0. Contrary to the regression setting in Chapter 2 σ 2 is not assumed to be known.

Given a sample D n = ((X 1 , Y 1 ), . . . , (X n , Y n )) where the observations (X i , Y i ) are independent and identically distributed (i.i.d.) from the distribution Q, we aim at predicting Y conditionally on X.

To do so, we use a learning algorithm which provides from D n a random function g: R d → [-L, L] called a predictor. Its accuracy is measured by its quadratic risk, defined as

L (g) = E (g(X) -Y ) 2 . (3.3)
Its empirical risk is defined by

L n (g) = 1 n n i=1 (g(X i ) -Y i ) 2 . (3.4)
Learning algorithms use the Empirical Risk Minimization (ERM) principle [START_REF] Vapnik | Estimation of Dependences Based on Empirical Data[END_REF] to generate the predictor. It means that a predictor g n generated by a learning algorithm fulfills

g n ∈ arg min g L n (g) (3.5)
where the arg min is taken among the set of all predictors that the algorithm can generate from D n .

Regression based on coverings

Usually, interpretable predictive algorithms are based on splitting the feature space into a partition where each cell describes a local phenomenon. In other words, they generate a partition P n from the dataset D n and build an estimator using the empirical risk minimization. So, for a given partition P n the predictor is defined as

g n (x) = A∈Pn n i=1 Y i 1 X i ∈A n i=1 1 X i ∈A 1 x∈A , x ∈ R d . (3.6)
In Section 3.3, we discuss the case 0/0. In this chapter, we present an algorithm based on a data-dependent covering. The idea is to generate, from the dataset D n , a covering

C n = C n (D n ) of R d instead of a partition.
This covering is turned into a partition P(C n ) using Definition 2.1.1. We have illustrated this transformation P on a covering C of five rectangles in Figures 1.7 and 1.8.

Hence we have the predictor

g n (X) = A∈P(Cn) n i=1 Y i 1 X i ∈A n i=1 1 X i ∈A 1 X∈A , X ∈ R d , (3.7)
This definition is based on the ERM principle among the piecewise constant predictors on P(C n ). However the predictors from Random Forests (RF) and other random rule algorithms do not satisfy the ERM principle (3.5): these are based on the averaging of the activated rules at the point x. This averaging is justified empirically and theoretically as it lowers the variance of the prediction thanks to the independence of the random rules as explained by [7]. The averaging does not decrease the approximation error of the prediction. On the opposite, our prediction following the relation (3.7) is the empirical conditional expectation of the intersection of the activated rules. Under some conditions, the approximation error of the prediction is then decreased but not the variance. To control the variance, we only consider coverings of rules that are significant (see Definition 1.4.3 below) as in the RIPE algorithm of [START_REF] Margot | Rule induction partitioning estimator[END_REF]. But in this former work the significant test to select rules does not allow to control the approximation error. and Note that, in practice it is not guaranteed to obtain a complete covering of R d with (in)significant hyperrectangles only. Thus we add an extra assumption (hypothesis (H13)) requiring that at the limit the (in)significant hyperrectangles cover the support of the observations.

M ( Ĉi n ) m( Ĉi n ) = o P (ε -2 n ∧ n 1/2-α ) (3.

Prediction based on quasi-coverings by hyperrectangles

One practical drawback using prediction (3.6) instead of the averaging is when x ∈ A with A ∈ P( Ĉn ) such that n i=1 1 X i ∈A = 0. In Chapter 2, we tackle this issue by predicting arbitrarily 0 in this case as it is usually done by the rule 0/0 = 0 advocated in [28,Chapter 4]. However, for many A such that n i=1 1 X i ∈A = 0 we do not know how to interpret this arbitrary choice or any other arbitrary ones (such as E n [Y ] which seems more accurate). In this sense, we do not give a prediction in such a case.

We denote Ĉs n and Ĉi n the set of significant rules such that Ĉn = Ĉs n ∪ Ĉi n . In practice we predict as following with

A s n (x) = r∈ Ĉs n :x∈r r \ r / ∈ Ĉs n :x∈r r and A i n (x) =   r∈ Ĉi n :x∈r r \ r / ∈ Ĉi n :x∈r r   \ c s n ,
where c s n = ∪ r∈ Ĉs n r. 1. If there exists r ∈ Ĉs n such that x ∈ r, then we predict (a) If it exists i such that X i ∈ A s n (x), then

g n (x) = i:X i ∈A s n (x) Y i #{i : X i ∈ A s n (x)} , (b)
If not there is no prediction. 2. If for all r ∈ Ĉs n we have x / ∈ r and there exists r ∈ Ĉi n such that x ∈ r, then we predict (a) If it exists i such that X i ∈ A i n (x), then

g n (x) = i:X i ∈A i n (x) Y i #{i : X i ∈ A i n (x)}
, (b) If not we predict the "no-rule" i.e.,

g n (x) = i:X i / ∈∪ r∈ Ĉs n r Y i #{i : X i / ∈ ∪ r∈ Ĉs n r} , 3.
If for all r ∈ Ĉn x / ∈ r then there is no prediction.

Consistency of estimator based on quasi-coverings by hyperrectangles

Theorem 2.2.1 presents sufficient assumptions for an algorithm to generate a consistent estimator g n of g * based on a suitable sequence of coverings of hyperrectangles. We required extra conditions controlling the complexity of the family of finer partitions that permit to build by countable unions of cells all the partitions that the algorithm can generate. These conditions use are based on the concept of partitioning number introduced in [53, Sec. 1.2] (see also [28,Def 13.1]).

For a set x

n 1 = {x 1 , . . . , x n } ∈ (R d ) n , let ∆(x n 1 , Π) := # {x n 1 ∩ A : A ∈ P} : P ∈ Π
be the number of distinct partitions of x n 1 induced by elements of Π. 3. The partitioning number ∆ n (Π) of Π is defined by:

∆ n (Π) := max x n 1 ∈(R d ) n ∆(x n 1 , Π).
The partitioning number is the maximal number of different partitions of any n points set that can be induced by elements of Π.

Let Π n = {P(C n (D n )) : D n ∈ (R d × R) n
} be the family of partitions induced by the coverings C n (D n ) that can be generated by the algorithm. And let Π n the family of finer partitions P in the following sense: for any P ∈ Π n there exists a partition P ∈ Π n such that P can be expressed as a set of countable unions of cells of P .

We work under the assumption that there exists an intermediate sequence .14) We are now ready to state a slightly extended version of Theorem 2.2.1 that is applicable to RICE algorithm. Theorem 3.4.1. Consider an algorithm generating an approximately suitable sequence ( Ĉn ) n≥1 of data-dependent collections of sets of R d fulfilling the two following conditions:

m n = o(n 1/d ) such that M( Π n ) ≤ (m n ) d and ∆ n ( Π n ) ≤ mn l=1 n -1 l -1 d . ( 3
P r∈ Ĉn(Dn) {r × R} → 1 , n → ∞ . ( H13
)
Assume that Ĉn (D n ) can be completed with insignificant rules in order to constitute a covering of R d and that σ 2 n satisfies |σ 2 n -σ 2 | = O P (n α-1/2 ), then the estimator g n defined as (3.7) is universally weakly consistent,

E Q [(g n (X) -g * (X)) 2 ] = o P (1).
Proof. The proof is a straightforward extension of Theorem 2.2.1. This theorem asserts the weak consistency of predictors satisfying (3.7) for suitable coverings under two conditions

M(Π n ) ∨ log(∆ n (Π n )) = o(n), (H14) ∀n ∈ N * , {c × R, c ∈ C n } ⊆ B,
where B is a Q-Donsker class.

(H15)

Condition (H15) is fulfilled on hyperrectangles by an application of Lemma 2.3.1. Then, let us show that (3.14) is sufficient for (H5). We have that Example 5). And since

M( Π n ) ≤ (m n ) d and ∆ n ( Π n ) ≤ (4n) m d n (see
m n = o(n 1/d ) we have M( Π n ) ∨ log(∆ n ( Π n )) = o(n).
Finally, to control the estimation error we use the following inequality sup

g∈Gn |L n (g) -L (g)| ≤ sup g∈Gc•Πn |L n (g) -L (g)| ≤ sup g∈Gc• Πn |L n (g) -L (g)| ,
where G c is the set of constant functions R d → [-L, L] and

G c • Π n := g : R d → R : g = A∈Pn f A 1 A , P n ∈ Π n , f A ∈ G c .
The set of functions G c • Π n is defined similarly.

We are now discussing the extension of Theorem 2.1 of Chapter 2 under the approximation of σ 2 by σ 2 n in (3.12) and (3.13) and ((H13)) instead of a covering C n of R d . Indeed an inspection of the proof of Theorem 2.1 of Chapter 2 shows that σ 2 there always appears with an empirical approximation of the order

∆ n := sup r∈Cn V(Y |X ∈ r) -V n (Y |X ∈ r) = O P (n α-1/2
). Thus, the extra approximation of σ 2 with σ 2 n is harmless and the weak consistency of g n follows if Ĉn was a covering.

As we have no guarantee than Ĉn is a covering of R d , we consider ĉn = r∈ Ĉn r and R d \ ĉn , the subset of R d which is not covered by Ĉn . Let us show that the consistency of the estimator of g * can be extended to this case. We recall the approximation error term E[(g n (X)-g * (X)) 2 ] that was proved to be o P (1) Theorem 2.1 of Chapter 2 for any rule estimators based on covering on (approximatively) significant and insignificant rules only. We consider g c n the complete covering based on Ĉn completed with insignificant rules and P c n the induced partition of R d . Denoting Pn the partition induced by Ĉn over ĉn then we have

E Q [(g n (X) -g * (X)) 2 ] ≤ 2(E Q [(g n (X) -g c n (X)) 2 ] + E Q [(g c n (X) -g * (X)) 2 ]) ≤ 2E Q [(g n (X) -g c n (X)) 2 ] + o P (1) ≤ A∈P c n 2E Q [(g n (X) -g c n (X)) 2 |X ∈ A]P(X ∈ A) + o P (1) ≤ A∈P c n \ Pn 2E Q [(g n (X) -g c n (X)) 2 |X ∈ A]P(X ∈ A) + o P (1) ≤ 2L 2 A∈P c n \ Pn P(X ∈ A) + o P (1) ≤ 2L 2 P(X ∈ R d \ ĉn ) + o P (1).
Under ((H13)) and using the previous P negligibility result, we have

P(X ∈ R d \ ĉn ) = 1 -P X ∈ r∈ Ĉn(Dn)
r = o(1).

Discretization

Designing all rules when features are continuous variables, is too complex and too time-consuming to be feasible in practice. So, to increase speed by limiting the searching area, each variable of the feature space is discretized into m n classes with m n = o(n 1/d ).

As in Chapter 5 the empirical quantiles of each variable are considered (when it has more than m n distinct values). The algorithm is described in Algorithm 6. The algorithmic complexity of the discretization is O(ndm n ). After the discretization, each class for each variable covers approximately n/m n points of D n .

The discretization is interesting since it guarantees that a covering of the sample is a covering of the feature space. Indeed, if we have a covering of the sample then for any new observation we have at least one activated rule. Without the discretization process, the new observation may be a new extremmum for example.

Moreover, the discretization process ensures that any partition generated by RICE, Π n , can be expressed as a set of countable unions of cells of the quantile partition with the parameter m n , Π n . Hence Π n fulfills (3.14) (see for instance Example 6).

Using discretization is a common method when X ∈ R d , we may cite [18,16,[START_REF] Srikant | Mining quantitative association rules in large relational tables[END_REF] which use quantitative methods for discretization and the algorithms BRL (Bayesian Rule Lists) [START_REF] Letham | Interpretable classifiers using rules and bayesian analysis: Building a better stroke prediction model[END_REF] and SIRUS [4] which use the empirical quantiles.

Rules designing

The rule designing process is similar to the RIPE in Chapter 5 The rule designing is processed recursively on the rule length l defined in (3.2).

A rule, r, is completely defined by a binary vector of length n equal to 1 if X i ∈ r and 0 otherwise for i ∈ {1, . . . , n}. Hence, the complexity to design one rule is O(n).

Rules of length 1

RICE first designs all rules of length 1 which fulfill (3.8). Thanks to the discretization we have at most (mn+1)mn 2 rules by variables, so the number of rules of length 1, R 1 , is bounded by

#R 1 ≤ d (m n + 1)m n 2 .
From this bound it is easy to see that the complexity of evaluating all rules of length 1 is O(ndm 2 n ). This part is described as Algorithm 7.

Rules of length l

The design of rules of length l, corresponding to Algorithm 8, is made by intersections of rules of length 1 and of rules of length l -1. Some of these intersections can be of length smaller than l and are discarded. The intersections which do not fulfill the coverage condition (3.8) are discarded, too.

Formally, the design of rules of length l is made by a suitable intersection of rules of length 1 and rule of length l -1. Definition 3.5.1 (Def 2.3 Chapter 5 ). Let d n = (x i ) 1≤i≤n be a sequence of observation of X. Two rules r and s define a suitable intersection if and only if they satisfy the two following conditions:

1. Intersection condition:

{x ∈ r ∩ s; x ∈ d n } = ∅, {x ∈ r; x ∈ d n } ⊆ {x ∈ s; x ∈ d n } and {x ∈ s; x ∈ d n } ⊆ {x ∈ r; x ∈ d n }.
(3.15)

2. Length condition:

(r ∩ s) = (r) + (s). (3.16)
The intersection condition (3.15) ensures that the algorithm does not increase the length of a rules without adding information. It means that r and s must not be satisfied for the same observations of d n . The length condition (3.16) means that r and s have no marginal index in common. In other words r and s must satisfied that

{1 ≤ j ≤ d; c r j = R} ∩ {1 ≤ j ≤ d; c s j = R} = ∅.
Despite the discretization, the number of rules increases too fast with l to be all designed. So, to design rules of length l + 1 for l ≥ 2, RICE selects a given number k ∈ N * of rules of each length 1 and l. They are selected according to their empirical risks (3.4). These rules are called candidate rules.

Thus #R l+1 ≤ k 2 , ∀ l ∈ {1, . . . , d -1}.
(3.17)

These formula permits to have a control on the maximal number of generated rules. Let l max ∈ N * a given maximal length for the generated rules. For a given number of candidate k ∈ N * the maximal number R of generated rules is bounded by

R ≤ #R 1 + l max k 2 . (3.18)
From this bound, it is easy to see that the complexity of evaluating all rules of length l obtained from their intersections is O(nk 2 ).

Get (in)significant rules

To consider significant and insignificant rules in practice a (consistent) estimator σ 2 n of σ 2 is needed. It can be defined as follows, where R n is the set of rules designed as described in Section 3.5.2.

Definition 3.5.2. The estimator σ 2 n is the smallest empirical conditional variance over all the rules in R n :

σ 2 n = min rn∈Rn V n (Y | X ∈ r n ).
To select significant and insignificant rules, RICE applies a filtering of the rules. RICE selects S ⊆ R n the set of the significant rules by considering rules r ∈ R n which satisfied the following inequality

β n E n [Y |X ∈ r] -E n [Y ] ≥ (V n (Y |X ∈ r) -σ 2 n ) + ,
where

β n = n α/2-1/4 .
The set I ⊆ R n \ S of the insignificant rules is selected by considering rules r ∈ R n not in S which satisfied the following inequality

ε n ≥ (V n (Y |X ∈ r) -σ 2 n ) + ,
where n = β n V n (Y ).

Selection of rules

RICE then selects a subset Ĉn of the set of rules R n it has designed. First, it tries to create an empirical covering with significant rules of R n . To increase the chance to get a covering, the algorithm considers the rules by decreasing order of covering rates Q n (r) and adds them to the currently selected set of rules S, subject to the condition that

Q n r r ∈S r ≤ γQ n (r) , r ∈ R n \ S , 0 < γ < 1 . (3.19)
This condition guarantees that (3.12) and (3.13) are fulfilled (see Remark 5). The selection ends if the current selected set of rules S forms a covering or if S has browsed all significant rules.

In the latter case, the algorithm tries to form a covering by adding insignificant rules to the currently selected set of rules S, avoiding inclusion using the recursive condition that P n (r \ {∪ r ∈S r }) > 0. The insignificant rules are browsed by increasing order of empirical variance. This step is described in Algorithm 5.

Complexity and parallelization

As mentioned before the algorithm can be easily parallelized. Throughout the process, except for the selection, rules are designed in an independent way. Thus, each loop on rules may be done on different cores. Assume that we have an unlimited number of cores, then the complexity of RICE can be hugely decreased.

The discretization can be done on each dimension, each bin in {1, . . . , m n } and each i ∈ {1, . . . , n} at the same time. So, the complexity of Algorithm 6 is the same as the complexity of finding a quantile (line 7) which is O(n) on average [START_REF] Hoare | Algorithm 65: find[END_REF].

The complexity of the design of rules of length 1, Algorithm 7, may be reduced to

O(n) instead of O(ndm 2 n
). Indeed, we can do the designing of the d 2 (m n + 1)m n rules at the same time. Hence, the complexity of Algorithm 7 parallelized is the same as the design of a rule (line 5) which is O(n).

Finally, for Algorithm 8, loops on R 1 and R l-1 can be done at the same time. Thus, we have k 2 intersection operations that can be made in the same time. The complexity of Algorithm 8 parallelized becomes the same as the evaluation of a suitable intersection (lines 4 and 5) which is O(2n).

Unfortunately, Algorithm 5 cannot be parallelized. It complexity depends on n, the maximal number of designed rules (3.18) and the minimal coverage rate to be able to estimate an average number of rules to have a covering.

In conclusion, the dimension of the feature space is not an issue. The number of candidates k and the maximal length l max must be reasonably small (smaller than 500 and 5 respectively) to avoid an uncontrollable increase in the complexity of the select part.

Discussion

Adding insignificant rules to significant rules allows to ensure a covering without considering a no-rule as in Chapter 2 Section 2.4. The theoretical difficulty with the no-rule (the complementary of significant rules) is that it is not necessarily a hyperrectangle and it may not fulfill the coverage condition (3.8). Thus it is not clear whether it belongs to fixed Donsker class for any n ∈ N. To circumvent this issue one considers insignificant rules despite they do not improve the interpretation of the predictor as most of them predict around the mean E n [Y ]. Moreover, as we control drastically the number of rules Algorithm 5: Select Input:

-S the set of significant rules -I the set of insignificant rules γ the intersection rate Output:

-Ĉn the minimal set of rules thanks to the number of candidates k there is no guarantee that the union of the selected rules covers the sample X 1 , . . . , X n . Clearly the condition (H13) may not be satisfied and the weak consistency of the procedure is not guaranteed. In this case RICE algorithm provides a warning message with the total coverage ratio of the selected rule. In all our experiments with k = 150 RICE has always generated a covering of the feature space.

1 Ĉn ← arg max r∈S Q n (r); 2 if | Ĉn | > 1 then 3 Ĉn ← arg min r∈ Ĉn L n (r) where L n (r) := 1 n n i=1 (E n [Y |X ∈ r]1 X i ∈r -Y i ) 2 ; 4 S ← S \ Ĉn ; 5 while Q n (∪ r∈ Ĉn r) < 1 do 6 r * ← arg max r∈S Q n (r); 7 if |r * | > 1 then 8 r * ← arg min r∈r * L n (r); 9 if Q n r * ∩ (∪ r∈ Ĉn r) ≤ γ Q n (r * ) then 10 Ĉn ← Ĉn ∪ {r * }; 11 S ← S \ {r * }; 12 if #S = 0 then 13 Break ; 14 end 15 while Q n (∪ r∈ Ĉn r) < 1 do 16 r * ← arg min r∈I V n (Y |X ∈ r); 17 if Q n r * ∩ (∪ r∈ Ĉn r) < Q n (r * ) then

Estimation of the noise variance

We provide some natural conditions under which the estimator σ 2 n of σ 2 is consistent. Lemma 3.5.1. Assume that a rule r n can be chosen in R n for each n ∈ N * such that

V(g * (X) | X ∈ r n ) P ---→ n→∞ 0.
(3.20)

Then σ 2 n is a consistent estimator of σ 2 . Moreover if V(g * (X) | X ∈ r n ) = O P (n α-1/2 ) then |σ 2 -σ 2 n | = O P (n α-1/2
) and σ 2 n satisfies the condition in Theorem 3.4.1.

Thus, if we denote w the modulus of continuity of g * , we get

V(g * (X) | X ∈ r) ≤ 1 2 w(Diam P (r)) 2 .
The result follows by uniform continuity of g * .

Applications

We present several applications to present advantages and limits of using RICE algorithm. In the following, we denote by S * the support of Y , S n the support of the estimator g n . To measure the difference between the two supports we introduce the distance H defined by:

H(S n , S * ) = |S * \ S n | + |S n \ S * |.
For each application RICE has been used with its default parameters (see Table 3.1) and it has generated a covering of the feature space. Nevertheless, as mentioned before a new observation may be in a cell of the partition generated by RICE without any observation used during the rules-designing process. In this case, either RICE is not able to make prediction (case 1. (b)) or RICE predicts the "no-rule" (case 2. (b)). Observations for which RICE is not able to make a prediction have been removed in the calculation of M SE * . They represent a proportion between 1% and 3% of the test observations.

Artificial data

Here we consider the same data set as in [20] already used in Section 2.4.2. We generate n = 5, 000 data points following the regression setting Y = g * (X) + Z, where d = 100 (the dimension of X) and

g * (X) = 9 3 j=1 exp -3 (1 -X j ) 2 -0.8 exp (-2 (X 4 -X 5 )) + 2 sin 2 (π • X 6 ) -2.5 (X 7 -X 8 ) , (3.22)
and Z ∼ N (0, σ 2 ). The value of σ > 0 was chosen to produce a two-to-one signal-to-noise ratio. The variables were generated from a uniform distribution on {0/10, . . . , 9/10}. It is important to notice that only the first eight variables are informative; the 92 others are just noise. Coefficients multiplying each of the terms in g * were chosen to ensure that variables have approximately equal influence.

In order to evaluate the error without including the error of the noise, we consider the following error

M SE * = E Q |g * (X) -g n (X)| 2 .
We approximate the criteria M SE * using 50, 000 test observations sampled independently from Q.

Execution

We run M = 100 simulations. For each simulation we set the maximal number of rules generated by the Random Forest (RF) at 20, 000 and the number of trees at m tree = 100.

Results

According to Figure 3.1 RICE seems less accurate than RF and RuleFit. It was expected because it is the cost of interpretability. Indeed, from Table 3.2, the interpretability index of RICE is largely smaller than those of others. Moreover, RICE generates rules (significant and insignificant) implying only variables of the support of Y . This is confirmed by the following result ∀s ∈ {1, . . . , M } we have H(S s n , S * ) = 0, where S s n is the support of the estimator g n generated by RICE for the simulation s. The average occurrence of a variable in a selected set of rules is depicted in Figure 3.2. Variables X 7 and X 8 , corresponding to the linear relation, are the most representative variables. On another side, X 6 which corresponds to the sinusoidal relation is the less represented variable. This result makes sense because a sinusoidal signal is harder to explain with rules than a linear one. Indeed, a linear signal may be described with two rules: one greater than the mean and one less than the mean.

One can notice that the Covering Algorithm introduced in Section 2.4.1 seems better than RICE for this application. One reason might be the fact that Covering Algorithm uses a "no-rule" to be able to generate a covering. It permits to limit the number of selected rules but this algorithm cannot generate a consistent estimator of the regression function contrary to RICE. Moreover, RICE discretizes features which decreases the accuracy of the prediction but makes the algorithm less complex (see (

Random hyperrectangles

In this application we consider the following regression setting

Y = g * (X) + Z,
where g * is defined by a set of random rules generated by the Aglorithm 9 given in Appendix.

Execution 1

Let i, j ∈ {1, . . . , d} such that i < j, we set a rule

r * = i-1 k=1 R × [a i , b i ] × j-1 k=i+1 R × [a j , b j ] × d k=j+1 R such that 0.02 ≤ Q(r * × R) ≤ 0.05. Then we set g * (X) = 1 X∈r * .
We generate n = 2, 000 points to train the algorithms and test them on 20, 000. The aim of the first simulation is to show the behavior of the algorithms for d ∈ {10, 20, . . . , 200}. For each value of d we run 100 simulations.

Results

In this application, we test the stability of the algorithms when we add noninformative variables. The support of g * is composed of two variables. Figure 3.3 highlights the fact that RICE is invariant in dimension contrary to the others. This property comes from the sparse set of variables occurring in rules selected by RICE. Indeed, as shown in Table 3.3c, the support of the estimator generated by RICE is always composed of around 5 variables independently of the dimension of the feature space.

Execution 2

We set d = 100 and we simulate X ∼ U([0, 1], d). We generate n = 2000 points to train the algorithms. The aim of the second simulation is to show the behavior of the algorithms when the number of rules n rules ∈ {1, 2, . . . , 8} increases. And we set

g * (X) = n rules i=1 1 X∈r * i ,
where each r * i is generated as in 3.6.2. For each value of n rules we realize 100 simulations.

Results

In this application, we test the ability to identify a model more and more complex. As shown in Figure 3.4 the accuracy of all algorithm decrease with the complexity of the model. Moreover, one can notice that the gap between algorithms increases too.

Table 3.4 sums up results of each algorithm. One can notice that the more complex the model the less interpretable the output of algorithms. Nevertheless, RICE keeps an interpretability index largely lower than other algorithms.

Conclusion

In this chapter, we have introduced an interpretable algorithm, RICE, based on the notion of approximately suitable sequence of data-dependent covering. It is an empirical extension of that defined in Chapter 2. RICE is a rules-based algorithm thought to be deterministic to ensure stability of the output. It designs rules satisfying a coverage condition (3.8) and selects a sparse set of them, forming a covering (3.9) fulfilling approximately (in)significant conditions (3.10) and (3.11). This covering permits to generate a estimator of the regression function which is consistent under some conditions (see Theorem 3.4.1). RICE has been compared to the algorithms Random Forest [7] and RuleFit [20]. These applications spotlight a link between interpretable behavior and support detection. Indeed, according to our interpretability index (Definition 3.1.1) the fewer the number of variables involved in the estimator the better the interpretability. Hence, to be interpretable and accurate algorithms have to select rules involving only variables of the support. Unfortunately, as explained in [START_REF] Yang | Can the strengths of aic and bic be shared? a conflict between model identification and regression estimation[END_REF], an algorithm cannot generate a good estimator and identify the support at the same time.

The applications have shown that RICE is very efficient to identify the support of a simple model, as in Section 3.6.2, regardless of the dimension of the feature space. Its invariance to noise, its ability to identify informative variables and its theoretical results make it a promising algorithm.

Appendix: Algorithms of RICE Algorithm 6: Discretize Input:

-X the features m n the number of bins Output:

-X the discretized features Appendix: Algorithm for the generation of random hyperrectangles Algorithm 9: Random hyperrectangles generation Input:

1 for i = 1, . . . , d do 2 x ← X[i]; 3 if length(set(x)) > m n then 4 bins ← [ ]; 5 for j = 1, . . . , m n -1 do 6 p ← j/m n ; 7 b ← get_quantile(x, p);
d the dimension of features space; n rules the number of rules; l max the maximal length of a rule; c min the minimal coverage rate of a rule; c max the maximal coverage rate of a rule; Output:

-R a set of hyperrectangles; 1 R ← ∅; 2 for j in [0, . . . , n rules ] do

Conclusions and perspectives

In this thesis, we have introduced a family of rule-based algorithms generating a covering instead of an usual partition. The use of a covering makes it possible to decrease the number of selected rules needed to describe a model, thus creating a more interpretable output. We have introduced the notion of interpretability index to be able to compare the interpretable nature of algorithms.

Moreover, we have demonstrated that under some conditions on the selected rules forming a covering, we are able to get the weak consistency for the estimator based on the partition generated from this covering without any shrinkage condition on the diameter of the cells of the underlying partition. These conditions avoid an increasing number of selected rules when n tends to infinity. They are based on the notion of significant and insignificant rules, the significant rules being interpretable sets by construction and the insignificant rules being small sets with variances tending to zero.

During the last part of this thesis, we have developed an algorithm, RICE, with opensource code, based on the theory of covering algorithms. This algorithm designs rules and selects a sparse set of significant rules and completes the covering with insignificant rules. The significant rules are used to interpret the model and to identify the support. RICE makes an estimator defined on the partition generated from this covering which is, under some conditions, a consistent estimator of the regression function.

Nevertheless, the theoretical setting could be refined: unbounded Y may be considered by introducing a truncation operator as in [28], and strong consistency and rates of convergence of the data-dependent covering estimators may be established under slightly stronger assumptions. Furthermore, it could be interesting to have some conditions that would ensure a covering of the explanatory variables space. Finally, the scope could be broaden from the regression setting to the classification setting by adapting the significant condition accordingly.

The algorithm RICE could also be improved. The selection of k candidates necessary to increase the length of designing rules is based on the empirical risk, with the assumption that the intersection of two "good" rules should define a good rule-which is debatable. Indeed, two features could be noninformative individually taken but strongly explainable together. Conditions to guarantee a covering of the explanatory variables space would be an improvement too. Finally, the source code could be sharpen.

Finally, this thesis spotlights a link between interpretability and support detection. This link makes sense because the parsimony of variables involved in the prediction process is an important factor to be interpretable. Applications emphasize the interpretability property of RICE and thus its ability to detect the support.

Introduction

The relationship between corporate social (CSP) and financial performances (CFP) is fairly an old theme in the economic research. In its earlier stages, it has met quite deep skepticism and critics: Nobel prize-winning economist Milton Friedman wrote in the New York Times Magazine, back in the 1970', that "... there is one and only one social responsibility of business -to use its resources and engage in activities designed to increase its profits so long as it stays within the rules of the game, which is to say, engages in open and free competition without deception or fraud...." [11].

But the number of studies that highlights positive, or at least non-negative, relationship between social and financial performances has grown significantly since then, probably beginning with the initial work by [4] on the link between environmental virtue and financial performance. Fifty years latter the context has completely changed. The number of proponents of social and, more broadly, ESG integration in both corporate management and investors' choices has grown exponentially. And so has the number of financial products, funds and ETFs, that offer ESG versions of a large panel of investment strategies (mainly on equity and bonds).

The current approach now seems completely opposed to Friedman's one, and the most recent empirical literature highlights the link between ESG performance and alpha [7,12,28]. Nonetheless, the question regarding the relationship between CSP and CFP remains unanswered. Reviews of published paper (meta-analysis) highlight that the majority of empirical studies published on this theme reports non-negative or small positive relationship between CSP and CFP (see for example [20], [1], [27], [25], [17], [10]). Other researchers take a more optimistic view and report significant relationship between CSP and CFP [18,9,15] or at least that CSP is not detrimental to CFP as long as one manages to build the portfolio with care, even if there is no clear value added in ESG integration [16].

Although we do not share the very optimistic, and mostly overstated, enthusiasm about the direct relationship between ESG and financial performance, we do believe that there is a strong relationship between ESG and sustainability of corporate business. Therefore, ESG has an impact on financial performances and risks, but this does not come linearly. We welcome the efforts that investors are undertaking to include ESG criteria into their portfolio choices, and we clearly hope that this will trigger economic and cultural changes in corporate management. At the same time, we remain skeptic in front of the far too flaunted capability of basic ESG ratings to act as an alpha generator in a portfolio.

It remains true however that the very large set of ESG data, reports and analysis can contain useful information related to the strengths and weaknesses of corporations. Unfortunately, ESG ratings are, by construction, a composite measure that dramatically reduces this rich set of information.

Our contribution to the growing literature on this topic is to show that, empirically, there is no value added in portfolios based on simple ESG screenings. Although it usually comes with no harm to the performance, we do not find any alpha in such approaches. However, by recognizing the intrinsic value of the large panel of ESG indicators that are aggregated to form the ESG ratings, we show that it is possible to extract value from them, which, in turns, translates into real alpha. By exploring large data sets of specific ESG indicators, we are able to identify those who really have an impact on corporate financial performances. In a simplified example, we can agree on the fact that for a company in the utility sector, most likely, the environmental performance can be a discriminating criterion for financial performance; at the same time, governance can play an important role if we compare a utility company in Europe with one in an emerging country. Similarly, direct carbon emissions for banks are probably not as relevant as the exposures of these banks, through loans, to highly polluting companies would be. In short, aggregate measures as ESG ratings lose valuable information contained in the ESG indicators, which therefore lower their predictive power.

Searching for interesting patterns between specific ESG indicators and financial performance for a large set of companies remains out of reach for the standard tools available to econometricians. This search takes place in a very high-dimensional space and is not oriented by some a priori on these ESG features. To deal with this complexity, we developed a machine learning algorithm that allows us to identify features and patterns that are relevant to explain the link between CSP and CFP. The algorithm maps the regions in our high-dimensional space of ESG features that have been consistently associated with outperformance or underperformance. In the econometric parlance, we look at those regions for which the conditional expectation of each stock's forward return is statistically positive (or negative), given that its relevant ESG features fall in these regions. We say that these relevant ESG features "activate" the region. By observing the ESG features we then obtain a significant signal regarding the future financial performance of the stock.

This identification is done with a set of rules that take the form of If-Then statements. The If statement identifies the region in the ESG space: in other words, the values that some ESG features have to take in order to activate the rule. The Then statement produces a prediction of the excess return, over the benchmark, that we can expect from a stock whose ESG features fall in that region. The final prediction is the aggregation of the predictions made by these rules and is transformed into a score {-1, 0, +1}. We therefore focus on the sign of the prediction of excess return rather than on its value. This usually makes the estimation more robust. The aggregation method mimics a panel of experts, each of which is expert on a very specific ESG feature (ex. Environment, Independence of the Board, ESG Reporting Verification, Employee Incidents, etc.) and makes a prediction given the ESG behavior of the company. When the aggregated prediction is close to zero, i.e the panel of experts is split between optimistic and pessimist forecasters, the final prediction is set at 0. The algorithm is regularly trained over time so that it can react and readjust to the new observed data.

The algorithm is used to design a very simple strategy that screens the investment universe and selects all stocks with a positive score. The resulting portfolio is compared with a classic ESG best-in-class portfolio, which consists of all stocks in the investment universe whose ESG ratings are above a given threshold within their peer groups. Our empirical results show that the simple machine learning screened portfolio significantly outperforms the ESG best-in-class approach and the benchmark. This is in line with the economic belief that ESG data is valuable information to assess financial performance, but also confirms that aggregated ESG ratings are not suited to distinguish between outperformers and underperformers over the long run. Even if perfect distinction is out of reach, our results clearly point out the fact that there is alpha in the granular ESG data, but the relation between ESG and financial performance is definitely not linear. Furthermore, the predictive power of the scores vanishes with time. We proof indeed that regularly training the algorithm over time, and producing up-to-date sets of rules, are key components of the superior performance of the machine learning when it comes to stocks screening.

Data

The analyses in this paper are carried out on portfolios based on the investment universe defined by the capitalization-weighted MSCI World Index USD, that consists of the largest capitalization listed in the US, Canada, Western Europe, Japan, Australia, New Zealand, Hong Kong and Singapore. Portfolios are calculated in USD and net dividends are reinvested in the portfolio itself. Stock prices and dividends are taken from Thomson Reuters/Datastream. We reconstruct a proxy of the MSCI World Index by using end-of-month compositions as well as proxies for the US, Europe 5 and Asia Developed 6 benchmarks. We also consider sector portfolios derived from the MSCI World Index and the regional benchmarks by filtering on stocks that belong to the same sector: Consumer 5. Stocks in the MSCI World Index domiciled in Austria, Belgium, Denmark, Finland, France, Germany, Ireland, Italy, Netherlands, Norway, Portugal, Spain, Sweden, Switzerland and United Kingdom 6. Stocks in the MSCI World Index domiciled in Australia, Hong Kong, Japan, New Zealand and Singapore Staples (CS), Consumer Discretionary (CD), Energy (EN), Financials (FI), HealthCare (HC), Industrials (IN), Information Technology (IT), Materials (MA), Telecommunication Services (TL), Utilities (UT). For each company in the investment universe, we collect ESG ratings from Sustainalytics 7 . An ESG rating is a comprehensive measure based on three pillars, Environment, Social and Governance, that assesses the strengths and weaknesses of a company along these three directions. The pillars are themselves based on a large set of specific indicators. For the purposes of this study, the composite ESG rating is the arithmetic average of the three ratings Environment (E), Social (S) and Governance (G), each of which is itself the combination of roughly 50 narrower indicators. Finally, for each company, we consider its relative Peer Group, which consists of all companies with a similar business, hence comparable from a sustainability point of view.

The best-in-class approach

One of the most popular approaches to embed ESG criteria in the portfolio construction process is the so-called best-in-class approach. Given a threshold x, one excludes the stocks whose ESG ratings belong to the lowest x-quantile. The exclusion is usually carried across peer groups, i.e., groups of stocks with very similar characteristics. The reason behind this is twofold:

-Removing stocks with low ESG ratings within peer groups insures that the final economic mesh of the filtered universe remains similar to the initial investment universe. -ESG ratings have a structural, sector-driven bias which usually favor specific sectors (ex. IT or HealthCare sectors) while penalizing others (ex. Energy or Utilities). Given this bias, the filtering over peer groups makes comparisons of ESG ratings independent of the sectors.

For the purpose of this study, an ESG best-in-class portfolio derived from a capitalizationweighted portfolio removes, within each peer group, the stocks whose ratings belong to the lowest x-quantile. The portfolio is finally scaled to sum up to one. This approach, quite popular among investors, should not be thought of as a way to enhance performance. As Tables 4.1-4.4 show, ESG best-in-class filters applied to standard capitalization-weighted indexes do not bring outperformance. Except for Europe and relatively low threshold levels, we find small but negative excess returns and negative information ratios for the ESG best-in-class portfolios over their benchmarks with almost unchanged risks. Although the approach does not create outperformance per se, it does not carry structural under-performance either. Optimistically, one could accept the fact that embedding ESG objectives in a portfolio does not significantly modify its risk/return profile.

Our findings are not in contradiction with the large literature that finds positive links between ESG and financial performance. But the consistency and durability over time of the ESG factor has been questioned since the very beginning. [3] find no significant relationship between social responsibility and corporate profitability, and similar results were obtained in [5] and [14]. [13] report that correlation between financial performance and social performance depends on the measure used to distinguish between high and low 7. One of the largest provider of ESG ratings. social performers.

Our results are more in line with [21] for which "... the consideration of corporate social responsibility in stock market portfolios is neither a weakness nor a strength compared with conventional investments...". It should be noted that many fund managers and institutional investors surveys report that ESG is mostly looked as a risk mitigation tool in the first place [26], and eventually as a performance driver at longer horizon. We share the optimistic view of Nobel prize-winning economist Robert Shiller for which both society and the financial community would find the use of socially responsible practices mutually beneficial [22]. At the same time, we also believe that short to mid term financial performance is at best lowly correlated to ESG ratings, at least for such broad investment universes as the MSCI World Index (which contains more than 1,600 companies). We can list several reasons for this:

(i) The investment universes are relatively large and the aggregated ESG ratings have too little a signal-to-noise ratio to allow for an efficient selection of outperforming stocks.

(ii) ESG ratings are global metrics that embrace environmental, social and governance criteria. As such, they may be too reductive and we may lose a significant amount of information from the single indicator to the aggregated scores.

(iii) Granularity is key: As an example, it is likely that companies in specific sectors (ex. Energy) react differently to changes in the environment score (E) compared to the social score (S).

(iv) In the search for a rational economic theory behind ESG, some argue that by divesting low ESG rated companies, investors raise their cost of capital and, in turns, the return these companies have to offer to attract new investors. As such, in the short run, they may show higher performances, but over time, the level of return they have to offer becomes unsustainable. Said otherwise, the action of divesting may take time to materialize in both investors' portfolios and low ESG rated companies (see for example [2]).

(v) The period considered in this study spans from the earlier stages of the recovery in 2009 to March 2018. Therefore, we are considering key performance indicators over a period of strong equity market, characterized by high returns and historically lower levels of volatility. This market regime can potentially affect the overall strength of ESG filtered portfolios.

To illustrate item (iii), we consider sector portfolios derived from the MSCI World Index and from the three regional benchmarks (US, Europe, Asia) and we apply both ESG and single pillar E, S and G, 30% best-in-class filtering. Tables 4.5-4.8 collect the results. For the sake of simplicity, we only show annualized excess returns over the relative benchmark sector portfolios and information ratios. Overall, it is not straightforward to detect clear patterns between excess returns and ESG metrics conditionally to the regional benchmarks. But we can definitely detect specific triplets sector/region/metric that produce significant positive excess returns. Clearly, integrating ESG criteria in the Utilities sector enhances in-sample performances. But the right metric to use clearly depends on the geography: in the World Developed (Table 4.5) the best excess return for the Utilities sector is achieved when one uses the Governance (G) score only at 0.82%; in the US (Table 4.6) it is better to look at the composite ESG ratings which achieves 0.63%. In Europe (Table 4.7) it is the Environment score (E) that obtains the best result with 3.25% while in the Asia (Table 4.8) it is, once again, the composite ESG rating that achieves the highest excess return at 3.07%. More generally, there is no sector nor metric for which the excess return of the bestin-class filtered sector achieves positive excess return in all the regions. Similarly, there is no region nor sector for which all metrics produce positive excess returns. Finally, no sector achieves positive excess returns across all regions and metrics. In other words, finding performance drivers when integrating ESG criteria in a best-in-class fashion is out of reach.

From Tables 4.5-4.8, only 12 out of 40 sector/metric portfolios in the World Developed region turn out to have positive excess return, and half of them are obtained when one considers the Governance (G) score. In the US we find positive excess returns in 14 out of 40, with no clear indication on the best metric to use. We notice though that all the metrics seem to work in the Utilities sector.

In Europe, we count 25 out of 40 sector/metric pairs with positive excess returns. For 4 sectors (Consumer Discretionary, Materials, Telecommunication Services and Utilities) all metrics work accurately. In Asia, we have 16 out of 40 portfolios with positive excess returns with no clear patterns between sectors and metrics, except for the Energy sector for which all metrics produce positive excess returns, even if their magnitudes are relatively small. In conclusion, our empirical findings confirm that simple ESG filtering does not bring extra performance. Overall, it rather behaves as a small drag. Given the short period we consider, and the market regime that equity markets have experienced since 2009, we share the view that ESG best-in-class integration is, most likely, neutral to financial performance. Nevertheless, our results highlight the fact that geographies and sectors do not react to ESG criteria in the same way. But finding interesting and statistically significant patterns between ratings, pillars, their underlying narrow indicators (features) and financial performances, for more than 150 indicators on more than 1,600 companies in the MSCI World Index, over roughly 10 year, is out of reach for both human and linear statistic tools. Next section introduces other techniques that can overcome this complexity and exploit this huge set of data.

Machine learning

In this section we introduce a deterministic, easily understandable machine-learning prediction algorithm, aimed at finding consistent and statistically significant patterns between ESG ratings and financial performances. The algorithm explores a high-dimensional data-set of ESG granular indicators for all the companies in our investment universe.

The goal of the algorithm, which falls in the category of supervised machine learning, is to predict the (conditional) excess return of each company over the benchmark, given the specific values taken by some of its ESG indicators (the features). Stated differently, the algorithm identifies regions in the high-dimensional space of ESG features that are statistically related to financial outperformance or underperformance. Features include raw and derived ESG indicators 8 , sector and country classifications, company's size and controversy indicators. The regions are characterized by rules in the form If-Then, so that the algorithm finally consists of a set of such rules. The If statement is a list of conditions on the features x t ∈ X = X 1 × • • • × X d , where X i is the set of possible outcomes of the feature i and d = 447 is the total number of features 9 . Therefore, a rule defines a hyper-rectangle of X . The Then statement is the prediction of the 3-month forward excess return conditionally to the If statement. Since the rules correspond to hyper-rectangles in the feature space, we finally obtain relatively simple and understandable regions. Furthermore, to avoid over-fitting, the algorithm only selects a finite number of such rules. At each time t, the predictions of each rule are aggregated into one prediction, ŷt , through convex combination. The algorithm is calibrated (trained ) on the training set and the rules are used out-ofsample. The learning process works at two independent levels:

-At the end of year N + 1 we train the algorithm on an expanded data-set of features and stock total returns which contains the data-set used at the end of year N augmented of all the new observed data (features and stock total returns) from the end of year N to the end of year N + 1. To initialize the algorithm, we train it over 3 year of data (from 2009 to 2012). By expanding the data-set, the algorithm is able to access new data and explore new patterns, so that it can strengthen or nuance some rules that were previously discovered.

-On a daily basis, the algorithm can update the weights used to aggregate each rule's prediction, by over-weighting rules with a good prediction rate and underweighting the others. Therefore, following day predictions will benefit from the experience the algorithm is gaining on the rules and their predictive power. The weight of each rule can be viewed as a confidence index. Of course, this is possible because the algorithm is able to assess the goodness of its predictions by looking at the realized 3-month return.

To avoid threshold effects, we transform the final prediction for each stock into a score S ∈ {-1, 0, +1}, where +1 stands for significantly positive excess return prediction, -1 for negative prediction and 0 for an uncertain prediction. The case where S = 0 is usually related to stocks for which some of their ESG indicators would eventually signal financial outperformance, while other ESG indicators rather signal potential undeperformance. The picture is then nuanced, and the algorithm cannot make a precise prediction. This is a very common situation in finance, where different indicators can yield different forecasts, so that, in aggregate, the forecast turns out to be uninformative. The learning process is divided into two steps. Following [19] and [24], the training set D N at the end of year N is divided into two sub-datasets: D n the learning set and D t the aggregation set, with t >> n and n + t = N . The learning set D n is used to design and 8. For each raw indicator, as for example the environment score (E), we also look at the derived indicator relative to the peer-group and the sector. All of these transformations can potentially contain useful information. On the other side, the use of both raw and derived indicators rapidly increases the dimension of the feature space d. 9. We use 164 ESG raw indicators, from which we derive peer group and sector relative indicators and 3 valuation indicators. In total 164*3 + 3 = 495. From these indicators we remove 48 indicators for which either the sector or the peer group derived indicators are too close, or for which historical data is missing.

2. Significance condition.

|µ(r, D

n ) -µ(X , D n )| ≥ z(r, D n , α), (4.4.3)
for a chosen α ∈ [0, 1] and function z.

The coverage condition (4.4.2) excludes rules that are activated only on small sets (i.e with a low coverage rate, C min ) and rules that are too obvious (i.e with a high coverage rate, C max ). The threshold in the significance condition (4.4.3) is set such that the probability of falsely rejecting the null hypothesis µ(r, D n ) = µ(X , D n ) is less than α. The parameter α permits to control the number of suitable rules. The higher α, the higher the number of suitable rules. In what follows, we generate rules of complexity c ≥ 2 by a suitable intersection of rules of complexity 1 and rule of complexity c -1.

Definition 4.4.5. Two rules f i and f j defined on r i and r j respectively, form a suitable intersection if and only if they satisfy the two following conditions:

1. Intersection condition:

r i ∩ r j = ∅, n(r i ∩ r j , D n ) = n(r i , D n ), n(r i ∩ r j , D n ) = n(r j , D n ) (4.4.4) 2. Complexity condition: cp(r i ∩ r j ) = cp(r i ) + cp(r j ). (4.4.5)
The intersection condition (4.4.4) avoids adding a useless condition for a rule. In other words, to define a suitable intersection, r i and r j must not be satisfied by the same points in D n . The complexity condition (4.4.5) means that r i and r j have no marginal index in common.

Designing Suitable Rules The design of suitable rules is made recursively on their complexity. It stops at a complexity c if no rule is suitable or if the maximal complexity c = cp max is achieved.

Complexity 1: The first step is to find suitable rules of complexity 1. First notice that the complexity of evaluating all rules of complexity 1 is O(ndm 2 ). Rules of complexity 1 are the base of the algorithm search heuristic. So all rules are considered and only suitable ones are kept, i.e rules that satisfied the coverage condition (4.4.2) and the significance condition (4.4.3). Since rules are considered independently, the search can be parallelized.

Complexity c: Among the suitable rules of complexity 1 and c -1, we select M rules of each complexity (1 and c -1) according to a chosen criterion. Then it generates rules of complexity c by pairwise suitable intersection according to the Definition 4.4.5. The complexity of evaluating all rules of complexity c, obtained from their intersections, is O(nM 2 ). Here again, since rules are considered independently, the evaluation can be parallelized. The parameter M helps to control the computing time.

Selecting Suitable Rules We select a subset S from all suitable rules which maximizes the gains expected from rule in D n and such as their conditions form a covering of X .

Algorithm The calibration of the algorithm is structured in two parts: in the first one, it finds all suitable rules, and in the second one it retains only an optimal subset of it.

To avoid threshold effects, overfitting and to manage the numerical complexity, we discretize each feature in X into m classes with empirical quantiles (modalities) 10 . Thus, each modality of each variable covers about 100/m percent of the sample. In practice, m must be inversely related to d: The higher the dimension of the problem, the smaller the number of modalities.

The parameters of the algorithm are: m, the sharpness of the discretization; α ∈ [0, 1], which specifies the false rejecting rate of the test; z, the significance function of the test; -C max and C min the coverage bounds; cp max the maximal complexity of a rule; -and M ∈ N, the number of rules of complexity 1 and c -1 used to define the rules of complexity c.

Aggregation Let D t = ((x n+1 , y n+1 ), . . . , (x n+t , y n+t )) ∈ (X , R) t , where n + t = N be the aggregation set and let S be the set of R rules selected by the algorithm. At each time t, the predictions of each rule are aggregated into one prediction ŷt as follows:

ŷt = R i=1 π i,t f i (x t , D n ) R i=1 π i,t 1 xt∈r i (4.4.6)
with π i,1 = 1/R. When the realized value y t is known, the weights π .,t+1 are updated with the following formula

π i,t+1 = π i,t e -η (f i (xt,Dn),yt) R i=1 e -η (f i (xt,Dn),yt) , (4.4.7)
with η > 0 and a convex loss function.

Remark 13. One can notice that f i (x t , D n ) is not defined if x t / ∈ r i . In (4.4.6), ŷt is well defined for all t, since the set S is a covering of X . In (4.4.7) we follow the methodology of the sleeping expert aggregation from [8].

Once trained, the machine learning algorithm produces predictions of the excess returns which are transformed into a scores S ∈ {-1, 0, +1}, given the out-of-sample ESG features x t for each company. Table 4.9 shows some examples of rules taken from the learning process of the algorithm. The table lists three rules associated with positive predictions (opportunities) and five rules with negative predictions. Each rule consists of two features and two intervals. The "Relative To" properties indicate whether the feature must be calculated over all stocks in the universe (All), over a Sector, over a Peer Group, or whether we should look at the variations of the feature over time (Delta Score).

Whenever the values taken by the features for a given company fall in the given intervals (we say that the stock activates the rule) the algorithm makes a prediction on its excess return. It is important to remark that we aggregate all the predictions, and we transform the final aggregated prediction into a score {-1, 0, +1}, so that in the end we mainly look at the sign of the prediction rather than at its magnitude. We also remark that, while the set of rules remains unchanged for one year (until the next learning process), the output of the rules can change over time, because raw indicators can change and also because the aggregated weights of the rules change over time.

then the capitalization-weighting scheme of the benchmark)

Positive ML Screening Sector Matched: Same selection as for the Positive ML Screening portfolio, but the scaling of the weights is done in such a way that the final sector breakdown of the portfolio is matched to the benchmark's one.

Negative ML Screening: The portfolio selects all stocks in the investment universe whose scores are -1. The weights are finally scaled up to sum to one (maintaining then the capitalization-weighting scheme of the benchmark)

As before, the scores are taken four days before the review date. We consider the sector matched portfolio because the absolute screening usually introduces significant sector deviations with respect to the benchmark. Table 4.10 collects the main results for these portfolios since January 2013. Although we recognize that the period over which we can test the machine learning algorithm is relatively short (five years and three months), the results we obtain contain some interesting insights. First of all, the Positive ML Screening outperforms all the other portfolios: by 2.76% the benchmark on an annualized basis, by 2.94% the ESG best-inclass portfolio and by 4.77% the Negative ML Screening. And while the realized annual volatilities remain in the range 10.50% to 11.14%, there are significant differences in the realized maximum drawdowns: the Negative ML Screening shows a -22.47% loss from its peak, while the Positive ML Screening loss from its peak accounts for -14.99%.

These two combined results show that the machine learning algorithm is clearly able to distinguish between opportunity stocks (the ones with positive scores) from risky stocks (negative scores). Figure 4.1 shows the historical behavior of these two portfolios and the benchmark. We notice that the Positive ML Screening outperforms the Negative ML Screening over time, with the benchmark in between. Furthermore, in years when the benchmark shows very high performances with very low volatility, typically in bull market regimes, the differences between the two strategies are less pronounced. On the contrary, when the market is in bear regimes or it does not have clear trend, the Positive ML Screening clearly outperforms its negative counterpart, as shown in Table 4.11.

In years when the benchmark performance is very significant (2013 or 2017), the Positive ML Screening is still able to achieve some outperformance, but the spread with the Negative ML Screening is somehow lower than years when the market performance is negative or low (2014, 2015 and, most recently, 2018). Interestingly, the excess return of the sector matched version is also positive, even if lower in magnitude when compared to the Positive ML Screening. By neutralizing the sector component (because matched), the outperformance essentially comes from the stock picking.

For the Negative ML Screening, the excess return is always negative except for 2016. Finally, the best-in-class portfolio shows almost systematically small but negative excess returns, except in 2015 when it managed to outperform by 0.07%. Once again, our findings confirm the fact that for very large and diversified universes, the simple ESG filtering does not bring alpha, although it does not significantly reduce the performance with the best-in-class approach.

The effects of learning The machine learning algorithm is initially trained over three years of data and then yearly updated. During these regular updates, the algorithm learns from the new flow of data it can access: It can test its rules to confirm, nuance or remove some of them, and selects new rules linked to statistically significant patterns. This learning process is key in the final performance of the model (and for the Positive ML Screening portfolio built upon it). To measure this effect, we form four portfolios named LEARNING Y, where Y = 2012, 2013, 2014, 2015 as follows:

-For each year Y, we consider the set of rules related to the learning at the end of the year Y. -We calculate the scores for all stocks in the universe from the end of year Y to March 2018 with this set of rules. -LEARNING Y is built as Positive ML Screening, except that the underlying scores are calculated with the same, not updated set of rules calibrated at the end of year Y. Said differently, LEARNING Y uses a unique, static set of rules that is never updated (no learning). By construction, the portfolios Positive ML Screening and LEARNING Y coincide over the period January, 1 st , Y + 1 to December, 31 st , Y + 1, because, over this period, they use the same set of rules (hence the same scores) to screen the investment universe. Figure 4.2 shows the calendar excess returns of these portfolios together with the Positive ML Screening portfolio over the benchmark MSCI World Index. Since we only show out-of-sample results, the time frame of each LEARNING Y portfolio is different. In the majority of cases, we see that Positive ML Screening outperforms the LEARNING Y portfolios after the first year (since they are the same on the first year). Indeed, the excess return for the LEARNING Y portfolios usually shrinks to zero and 123 becomes even negative over time.

In other words, the predictive power of the scores vanishes over time, so that it is important to train the algorithm on the new observed data to update the set of rules.

Conclusion

The last few years have seen an increasing interest toward ESG investing and the integration of socially responsible principles at the portfolio construction level. Managers and investors are asked to complement pure financial objectives with extra-financial ones.

Our study brings some new ideas and insights onto the way investors could achieve ESG objectives in their investments. The literature on the theme is mixed: Initial studies were mostly skeptical on the benefit of ESG integration into the portfolio. Over time the mindset has evolved, and several studies have empirically proven that ESG integration in the portfolio does not lower performances. Most recently, the financial literature has gone one step further and claim that, indeed, ESG integration is a way to extract alpha or, at least, to reduce risks.

We do recognize the need for serious integration of ESG objectives alongside with classic financial ones, and that there exists an economic link between the ESG profile of a company and its financial performances over the long run. Nevertheless, we tend to agree with the pioneers of ESG research for which, at best, ESG integration does not significantly degrade financial performances, especially for large and diversified investment universes.

Because ESG profiles can impact financial performances in a non-linear way, and the impact can depend on the sector, the country or other specific characteristics of each company, we designed and implemented a sophisticated machine learning algorithm that identifies patterns between ESG profiles and performances, statistically robust across the universe and over time.

The algorithm produces a set of rules, each rule identifying a region in the highdimensional space of the ESG features, conditionally on which we can make a prediction on the stock's excess return. All the predictions are finally aggregated and transformed into a score taking values in {-1, 0, +1}, so that in the end we effectively look at the sign of the excess return rather than its magnitude.

With this algorithm, trained over time to keep it updated, we empirically proof that the link between ESG profiles and financial performances exists, but can only be accessed with non-linear techniques. Indeed a simple strategy that selects stocks whose scores are positive significantly outperforms the well known ESG best-in-class approach.

Introduction

To find an easy way to describe a complex model with a high accuracy is an important objective for machine learning. Many research fields such as medicine, marketing, or finance need algorithms able to give a reason for each prediction made. Until now, a common solution to achieve this goal has been to use induction rule to describe cells of a partition of the features space X . A rule is an If-Then statement which is understood by everyone and easily interpreted by experts (medical doctors, asset managers, etc.). We focus on rules with a If condition defined as a hyperrectangle of X .Sets of such rules have always been seen as decision trees, which means that there is a one-to-one correspondence between a rule and a generated partition cell. Therefore, algorithms for mining induction rules have usually been developed to solve the optimal decision tree problem [9]. Most of them use a greedy splitting technique [3,12,6,5] whereas others use an approach based on Bayesian analysis [4,10,13].

RIPE (Rule Induction Partitioning Estimator) has been developed to be a deterministic (identical output for an identical input) and easily understandable (simple to explain and to interpret) predictive algorithm. In that purpose, it has also been based on rule induction. But, on the contrary to other algorithms, rules selected by RIPE are not necessarily disjoint and are independently identified. So, this set of selected rules does not form a partition and it cannot be represented as a decision tree. This set is then turned into a partition. Cells of this partition are described by a set of activated rules which means that their If conditions are satisfied. So, a same rule can explain different cells of the partition. Thus, RIPE is able to generate a fine partition whose cells are easily described, which would usually require deeper decision tree and less and less understandable rules. Moreover, this way of partitioning permits to have cells which are not a hyperrectangles.

The simplest estimator is the constant one which predicts the empirical expectation of the target variable. From it, RIPE searches rules which are significantly different. To identify these, RIPE works recursively, searching more and more complex rules, from the most generic to the most specific ones. When it is not able to identify new rules, it extracts a set of rules by an empirical risk minimization. To ensure a covering of X , a no rule satisfied statement is added to the set. It is defined on the subset of X not covered by the union of the hyperrectangles of the extracted rules. At the end, RIPE generates a partition spanned by these selected rules and builds an estimator. But the calculation of a partition from a set of hyperrectangles is very complex. To solve this issue, RIPE uses what we called the partitioning trick which is a new algorithmic way to bypass this problem.

Framework

Let (X, Y ) ∈ X × R, where X = X 1 × • • • × X d , be a couple of random variables with unknown distribution P . 1. Any measurable function g : X → R is called a predictor and we denote by G the set of all the predictors.

2. The accuracy of g as a predictor of Y from X is measured by the quadratic risk, defined by L (g) = E (X,Y )∼P (g(X) -Y ) 2 .

(5.1.1)

From the properties of the conditional expectation, the optimal predictor is the regression function (see [1,7] for more details): 2) provides a link between prediction and estimation of the regression function. So, the purpose is to produce an estimator of g * based on a partition of X that provides a good predictor of Y . However, the partition must be simple enough to be understandable. 1 x∈r i 1 x j ∈r i + 1 x / ∈r i 1 x j / ∈r i . In (5.2.1), the complexity O(nR) appears immediately.

Independent Suitable Rules

Each dimension of X is discretized into m n classes such that

(m n ) d n → 0, n → ∞. ( 5

.2.2)

To do so empirical quantiles of each variable are considered (when it has more than m n different values). Thus, each class of each variable covers about 100/m n percent of the sample. This discretization is the reason why RIPE deals with continuous and ordered discrete variables only.

Real Data

In this section, we present a quick overview of the use of the alogirthm RIPE on the well-known Kaggle's 6 dataset: Titanic. It is a binary classification problem. The goal is to predict which passengers survived the tragedy. We have kept only 7 features. We have dropped features Name, Ticket Number, and Cabin Number which are considered irrelevant for a first study, and we haven't done data engineering.

The accuracy rate given by Kaggle for RIPE's predictions on the test set is 0.765, but the most interesting output is the description of the model.

This can be sum up in Table 5.5 and with the two following figures. Figure 5.3 shows that the most important feature is the fare which appears seven times in the set of selected rules. The figure 5.4 permits to be more specific. Indeed, we can notice that the cheaper the ticket, the higher the risk to die.

This example shows the kind of interpretation that RIPE could offer to a statistical study on an unknown dataset. Table 5.5 -Summary of selected rules with conditions interval express as modalities

Conclusion

In this paper we present an understandable predictive algorithm, named RIPE. Considering the regression function is the best predictor RIPE has been developed to be a simple and accurate estimator of the regression function. The algorithm identified a set of suitable rules, not necessary disjoint, of the form If-Then such as their If conditions are hyperrectangles of the features space X . Then, the estimator is built on the partition generated by the partitioning trick. Its computational complexity is linear in the data dimension O(dn).

RIPE is different from existing methods which are based on a space-partitioning tree. It is able to generate a fine partition from a set of suitable rules, reasonably quickly such that their cells are explained as a list of suitable rules. Whereas there is a one-to-one correspondence between a rule and a cell of a partition provided by a decision tree. So to have a finer partition decision trees must be deeper and rules become less and less understandable. Furthermore, on the contrary to decision trees, the partition generated by RIPE can have cells which are not hyperrectangles.

  H1) -Y est bornée : Q(S) = 1 avec S = R d ×[-L, L], pour L > 0 (inconnue). (H2)

  28, Def 1.1 et Def 1.2]. Définition 1.1.1. Un estimateur g n est dit universellement faiblement consistant si et seulement si pour toute loi Q telle que E [Y 2 ] < ∞, on a lim n→∞ R (g * , g n ) = 0 . Définition 1.1.2. Un estimateur g n est dit universellement fortement consistant si et seulement si pour toute loi Q telle que E [Y 2 ] < ∞, on a lim n→∞ (g * , g n ) = 0, Q ⊗n -p.s.

Figure 1 . 1 -

 11 Figure 1.1 -Représentation de la partition d'un régressogramme pour différents Dn.

Figure 1 . 2 -

 12 Figure 1.2 -Représentation de la partition cubique pour différent Dn.

4 Figure 1 . 3 -

 413 Figure 1.3 -Représentation de la partition quantile pour différent Dn.

(1. 11 ) 4 Figure 1 . 4 -

 11414 Figure 1.4 -Représentation de la partition par bloques statistiquement équivalents pour différent Dn.

Figure 1 . 5 -

 15 Figure 1.5 -Évolution du nombre de publications sur ArXiv avec le mot interprétabilité dans le résumé.

Définition 1 . 4 . 1 .

 141 L'indice d'interprétabilité d'un modèle fondé sur un ensemble de règles P est défini par Int(g) := r∈P (r).

  et 1.8.

Remarque 4 .

 4 Si C est un recouvrement de R d , alors P(C) est une partition de R d . De plus l'égalité C = P(C) est vérifiée si et seulement si C est composée de sous-ensemble disjoints. On définit également P C (r) pour tout élément r de C comme étant l'ensemble des cellules de P(C) contenues dans r : P C (r) := {A ∈ P(C) : A ⊆ r} .

Figure 1 . 7 -

 17 Figure 1.7 -Les cinqs éléments de C.

Figure 1 . 8 -

 18 Figure 1.8 -Les onze cellules de P(C).

  Pour ce faire, il faut d'abord identifier les règles activées par x, c'est-à-dire telles que x appartient à l'hyperrectangle défini par leurs conditions (Fig 1.9, en haut à gauche). Et nous calculons l'intersection des règles actives (Fig 1.9, en bas à gauche). Puis nous calculons l'union des règles inactives (Fig 1.9, en haut à droite). Enfin, nous calculons la différence entre l'intersection des règles actives et l'union des règles inactives (Fig 1.9, en bas à droite). Cet sous-ensemble est la cellule de P(C) qui contient x. Tout le processus est illustré dans le Figure 1.9.

Figure 1 . 9 -

 19 Figure 1.9 -Les différentes étapes du partitioning trick pour un ensemble de trois hyperrectangles {r 1 , r 2 , r 3 } de [0, 1] 2 et une nouvelle observation x = (0.1, 0.7). Il est important de noter que la cellule qui contient x, (r 1 ∩ r 2 ) \ r 3 , n'est pas un hyperrectangle et ne peut pas être vue comme une règle au sens de la définition (1.18).

5 . 1 .

 51 Ce résultat repose sur la notion d'application tendue et asymptotiquement tendue dont nous rappelons les définitions [70, Chapitre 18]. Définition 1.4.4. Soit (Ω, A, P) un espace de probabilité 1. Une application aléatoire M définie sur Ω et à valeur dans un espace métrique (D, d) est dite tendue si et seulement si ∀ > 0, ∃K ⊂ D compact tel que

Définition 1 . 5 . 1 .

 151 On dit que F est une classe Q-Donsker si et seulement si la suite {v n (f ) : f ∈ F} converge en loi vers G Q un Q-pont brownien. Remarque 9. Par abus de langage on dit qu'une classe d'ensemble C est Q-Donsker si la classe des fonctions caractéristiques de ses ensembles, I C := {1 A : A ∈ C}, est une classe Q-Donsker.

Définition 1 . 5 . 3 .

 153 On dit qu'une suite S 1 , S 1 , . . . est dans O P * (a n ) pour une suite de nombre positifs a 1 , a 2 , . . . si et seulement si pour tout > 0 il existe des constantes M > 0 et N ∈ N telles que pour tout n > N on a P * S n a n > M ≤ . 1.5.2 Heuristique de preuve du théorème 1.4.1 Nous présentons une preuve du théorème 1.4.1 dans le cas particulier d'une partition et dans un cadre où les espérances et variances conditionnelles sont connues. Théorème 1.5.2. Soit g n défini par (1.19) sur un ensemble de règles

  arg min g∈Gn L n (g) and gn = arg min g∈Gn L(g).

Definition 2 . 1 . 1 .

 211 Let C be a finite collection of subsets of R d and let c = r∈C r. We define the activation function as

Definition 2 . 1 . 2 .

 212 Let C be a covering of R d and C ⊆ C. The cells of P(C) wich are included in an element of C are gathered in P C (C ) : P C (C ) := {A ∈ P(C) : ∃r ∈ C , A ⊆ r}. Remark 2. By definition, we have the identity P C (C) = P(C).

Definition 2 . 1 . 3 .

 213 Let C be a finite collection of subsets of R d . We introduce the maximal (resp. minimal) redundancy of C on a subset r ⊆ R d : M (C, r) := max x∈r #ϕ C (x) m(C, r) := min x∈r #ϕ C (x). We shorten M (C, c) in M (C) and m(C, c) in m(C).

Remark 3 .

 3 If C is a partition then for any r ∈ C, we have P C (r) = {r} and M (C, r) = m(C, r) = 1.

Figure 2 . 1 -

 21 Figure 2.1 -Partitions generated by fully deployed decision tree algorithm, it means without pruning, for a maximal depth λ ∈ {1, 2, 3, 4}.

Definition 2 . 1 . 4 .

 214 The interpretability index of an estimator g n generated by a set of rules C n is defined by Int(g n ) := r∈Cn length(r).

Theorem 2 . 3 . 1 .

 231 [START_REF] Van Der Vaart | Asymptotic statistics[END_REF] Theorem 19.4] Every class F of measurable functions with J

  Definition 2.3.3. [70, Chapter 18] A sequence (M n ) n∈N of maps defined on Ω and with values in a metric space (D, d) is said to be asymptotically tight if ∀ε > 0, ∃K ⊂ D compact ∀δ > 0, lim sup n→∞ P * (M n / ∈ K δ ) < ε, with K δ = {y ∈ D : d(y, K) < δ} for any K ⊂ D and δ > 0. Remark 9. If D = R, (M n ) is asymptotically tight if and only if ∀ε > 0, ∃M > 0/ lim sup n→∞ P * (|M n | > M ) < ε.

  First, let us define C i\s n = {r \ c s n : r ∈ C i n } where c s n = ∪ r∈C s n r. Notice that P(C i\s n ) = A \ c s n : A ∈ P(C i n ) . Indeed, by Proposition 2.1.1:

See [ 28 ,

 28 Definition 9.4 (c)]. Now, from the definition of G c , sup z 1 ,...,zm∈{X 1 ,...,Xn},m≤n

Figure 2 . 3 -

 23 Figure 2.3 -Box-plot of the M SE * of each algorithm.

13 )

 13 where M (C) := max x∈R d #ϕ C (x) and m(C) := min x∈R d #ϕ C (x) are the maximal and minimal redundancies of C a collection of subsets of R d .

Definition 3 . 4 . 1 .

 341 Let Π be a family of partitions of R d . 1. The maximal number of cells in a partition of Π is denoted by M(Π) := sup {#P : P ∈ Π} .

18 Ĉn← 19 I

 1819 Ĉn ∪ {r * }; ← I \ {r * }; 20 if #I = 0 And Q n (∪ r∈ Ĉn r) < 1 then 21 Print "Warning: Covering is not completed!"; 22 Print "The covering ratio is:"; 23 Print Q n (∪ r∈ Ĉn r); 24 Break ; 25 end 26 return Ĉn ;

Figure 3 . 1 -

 31 Figure 3.1 -Box-plot of the M SE * of each algorithm.

Figure 3 . 3 -

 33 Figure 3.3 -Box-plot of the M SE * of each algorithm.

Figure 3 . 4 -

 34 Figure 3.4 -Box-plot of the M SE * of each algorithm.

8 bins 13 for b in bins do 14 if

 81314 ← append(bins, b); 9 low ← min(x); 10 up ← max(x); 11 for j = 1, . . . , n do 12 val ← 1; low ≤ x[j] < b then 15 x[j] ← val; 16 low ← b; 17 val ← val + 1; 18 if low ≤ x[j] ≤ up then 19 x[j] ← val; 20 X[i] ← x; 21 return X;

3 r ← 1 ; 4 index ← ∅; 5 l 8 while i in index do 9 i 20 c

 31458920 ← U([1, . . . , l max ]); 6 for k in [1, . . . , l] do 7 i = U([1, . . . , d]); ← U([1, . . . , d]); k ← 1 X i ∈[bmin,bmax] ;

Figure 4 . 1 -

 41 Figure 4.1 -Simulated strategy levels for the benchmark MSCI World Index, the capitalizationweighted selection filtered over positive scores from the ML algorithm (Positive ML Screening) and the one screened over negative scores (Negative ML Screening). Data in USD from January 2013 to March 2018. Base level = 100. Source MSCI, Datastream, Sustainalytics.

( a )

 a Learning end of 2012 (b) Learning end of 2013 (c) Learning end of 2014 (d) Learning end of 2015

Figure 4 . 2 -

 42 Figure 4.2 -Calendar excess returns of the Positive ML Screening and the four portfolios LEARNING 2012, LEARNING 2013, LEARNING 2014 and LEARNING 2015 over the MSCI World Index. Data is shown in USD from January 2013 to March 2018. Source MSCI, Datastream, Sustainalytics.

( a )

 a Positive vs. Negative (b) Simple vs. Complex

Figure 4 . 3 -

 43 Figure 4.3 -Number of rules at each update of the algorithm: (a) the split between rules that predict positive or negative excess returns (ER); (b) the split between rules that make use of one feature (Simple) or two features (Complex).

  -4.3 suggest that to extract alpha from the ESG features, one needs to regularly update the algorithm, and consider newly created set of rules to detect patterns between ESG profiles and financial performances.

g 2 ) 5 . 1 . 2 .Definition 5 . 1 . 3 .

 2512513 * := E [Y |X] = arg min g∈G L (g) a.s.(5.1.Definition Let D n = ((X 1 , Y 1 ), . . . , (X n , Y n ))be a sample of independent and identically distributed copies of (X, Y ). The empirical risk of a predictor g on D n is defined by: X i ) -Y i ) 2(5.1.3) Equation (5.1.

Figure 5 . 1 -

 51 Figure 5.1 -Different steps of the partitioning trick for a set of three hyperrectangles {r 1 , r 2 , r 3 } of [0, 1] 2 and a new observation x = (0.1, 0.7).It is important to notice that the cell containing x, (r 1 ∩ r 2 ) \ r 3 , is not a hyperrectangle so it does not define a rule.

Proof.

  It is sufficient to notice that µ(K n (x), D n ) can be express as follows:µ(K n (x), D n ) = n j=1 y j k(x, x j , S n ) n j=1 k(x, x j , S n ) , (5.2.1) with k(x, x j , S n ) = R i=1

Figure 5 . 3 -

 53 Figure 5.3 -Distribution of rules by variables

Figure 5 . 4 -

 54 Figure 5.4 -Sum of the prediction of rules for each quantitative variable by modalities Rule Conditions Coverage Prediction Z M SE R 0(2)+ Sex = f emale & P class ∈ [1.0, 2.0] 0.19 1.16 0.26 0.32 R 1(2)+ Sex = f emale & F are = 4.0 0.11 1.09 0.35 0.41 R 3(2)+ Sex = f emale & Embarked ∈ [C, Q] 0.12 0.93 0.32 0.42 R 2(1)+ P class = 1.0 0.24 0.51 0.21 0.43 R 5(1)-F are ∈ [0.0, 1.0] 0.38 -0.38 0.14 0.43 R 6(2)+ P class ∈ [1.0, 2.0] & F are = 4.0 0.18 0.63 0.25 0.43 R 4(2)-P class = 3.0 & F are ∈ [0.0, 2.0] 0.47 -0.27 0.13 0.44 R 7(2)+ F are ∈ [2.0, 4.0] & Embarked ∈ [C, N aN ] 0.15 0.54 0.27 0.45 R 8(2)+ F are ∈ [2.0, 4.0] & Embarked ∈ [C, Q] 0.17 0.45 0.25 0.45 R 9(1)-F are ∈ [1.0, 2.0] 0.41 -0.16 0.14 0.46 R 10 No rule activated 0.09 -0.40 0.28 0.47

  Un arbre de décision est un modèle structuré composé de noeuds et d'arcs. Chaque arc mène à un noeud représentant un test sur une variable explicative. Chaque suite de succès et d'échecs mène à des noeuds terminaux, appelés feuilles, représentant les valeurs prédites. Dans chaque feuille on calcule la perte empirique (1.6), aussi appelée M SE, le nombres de points dans la cellule, samples et l'espérance conditionnelle empirique de Y sachant qu'on est dans la cellule, value. On renvoie au tableau IV p96-97 de[START_REF] Harrison | Hedonic housing prices and the demand for clean air[END_REF] pour une explication des variables Y , RM , LST AT , etc.

			RM ≤ 6.645
			mse = 84.42
			samples = 506
			value = 22.533
			True	False
			LSTAT ≤ 18.279	LSTAT ≤ 9.518
			mse = 34.402	mse = 107.848
			samples = 387	samples = 119
			value = 19.36	value = 32.852
	LSTAT ≤ 16.499 mse = 24.237 samples = 299 value = 21.187	mse = 19.069 samples = 88 value = 13.152	PTRATIO ≤ 15.192 mse = 67.493 samples = 96 value = 36.032	mse = 57.88 samples = 23 value = 19.578
	mse = 22.984	mse = 9.967	mse = 65.414	mse = 50.143
	samples = 266	samples = 33	samples = 28	samples = 68
	value = 21.764	value = 16.53	value = 41.629	value = 33.728

Les algorithmes d'arbres les plus connus sont CART

[8]

, ID3

[START_REF] Quinlan | Induction of decision trees[END_REF]

, C4.5

[START_REF] Quinlan | C4.5: Programs for machine learning[END_REF]

et RIPPER

[10]

.

La Figure

1

.6 représente un arbre de régression décrivant les données Boston housing

[START_REF] Harrison | Hedonic housing prices and the demand for clean air[END_REF]

. Dans un souci d'illustration la profondeur de l'arbre a été fixée à 3 et le nombre de feuilles générées à 6. Figure 1.6 -Exemple d'arbre de décision.

  On retrouve le If dans la colonne Conditions et le Then dans la colonne Value. La colonne Samples est le nombre de points dans la règle. Il est important de noter qu'il y a des règles dont les conditions s'intersectent et peuvent donc s'activer en même temps (ex: R2 et R3 pour LST AT ∈ [7.76, 7.87]). La gestion de ces conflits possibles est un enjeux important.

	Rule	Conditions	Samples Value
	R1	LST AT ∈ [9.62, 37.97]	293	17.74
	R2	LST AT ∈ [1.73, 7.87]	157	32.31
		RM ∈ [3.86, 6.10]
	R3	LST AT ∈ [7.76, 37.97]	187	17.62
		DIS ∈ [1.20, 12.13]
		RM ∈ [6.42, 8.78]
	R4	LST AT ∈ [1.73, 14.40]	167	31.88
		DIS ∈ [1.20, 12.13]
		RM ∈ [6.09, 8.78]
	R5	LST AT ∈ [1.73, 9.98]	136	32.12
		CRIM ∈ [0.05, 88.98]
		LST AT ∈ [5.06, 37.97]
	R6	P T RAT IO ∈ [13.90, 22.0]	182	16.34
		IN DU S ∈ [15.01, 27.74]

Table 1 .

 1

1 -Exemple d'ensemble de règle.

Table 1 . 2

 12

-Exemple de règles les plus importantes de RuleFit

Algorithm 1 :

 1 Exemple d'algorithme top-down naïf Input: D n = (x i , y i ) i=1,...,n un échantillon; Output: r un intervale de R définissant une règle; 1 r = R; 2 bmin = min({x 1 , . . . , x n });

	3 bmax = arg max b∈r 4 bmin = arg min l∈r	n i=1 y i 1 x i ∈[bmin,b] ; n i=1 y i 1 x i ∈[l,bmax] ;
	5 r = [bmin, bmax];
	6 return r;
	Algorithm 2: Exemple d'algorithme bottom-up naïf
	Input: D n = (x i , y i ) i≤0 un échantillon;
	Output: r un interval de R définissant une règle;
	1 i max = arg max i∈{1,...,n} y i ;
	2 bmin = bmax = x imax ;
	3 r = [bmin, bmax];
	4 bmax = arg max b∈{x 1 ,...,xn} 5 bmin = arg min l∈{x 1 ,...,xn}	n i=1 y i 1 x i ∈[bmin,b] ; n i=1 y i 1 x i ∈[bmin,b] ;
	6 r = [bmin, bmax];
	7 return r;

  1 x∈r i 1 x j ∈r i + 1 x / ∈r i 1 x j / ∈r i . La complexité O(nR) apparait immédiatement, car il suffit de considérer les n+1 vecteurs (1 x∈r ) r∈C avec x ∈ {x 1 , . . . , x n , x}.

	1.4.3 Contrôle de l'erreur d'approximation sans contrainte sur le
	diamètre des cellules

L'excès de perte (1.4) peut être décomposé en deux termes grâce au Lemme 10.1

[28]

suivant :

  s. Remarque 10. On remarque que dans l'énoncé de ce théorème la condition de couverture (H3) n'est plus nécessaire puisque les conditions de signifiance et d'insignifiance ne portent pas sur des estimateurs des moments. De plus nous obtenons un résultat de consistance forte contrairement au Théorème 1.4.1.

Preuve. D'après le Lemme 1.4.1 un estimateur est consistant si les erreurs d'approximation et d'estimation tendent vers 0. Commençons par prouver que l'erreur d'approximation tend vers 0 en utilisant la seconde condition du Théorème 1.5.2.

Erreur d'approximation : Soit G n la classe des fonctions mesurables définies sur la partition P n

4 )

 4 Thus(2.11) holds for r = A with high probability for n sufficiently large. Note that for similar reasons (2.11) also holds with high probability for r = A c , n -1/4 = o(β n ) and n sufficiently large. Finally, conditions (2.9), (2.13) and (2.14) are easily checked on the partitions C

n = P n = {A, A c } that constitute a suitable coverings sequence with high probability for n large enough. Remark 6. The significant condition (2.11) does not follow from a condition on the diameter of the subset. On the opposite, the insignificant condition (2.12) can follow from a condition on the diameter of the subset, see Proposition 2.3.3.

  g * is uniformly continuous and if

	max r∈Pn	Diam(r) = o P (1)	(2.19)
	then the sequence (P

n ) is suitable.

Proof. Let us show that each cell is significant or insignificant. Thanks to Condition (2.9), Corollary 2.3.1 Eq. (2.18) and Remark 8,

  The estimation error (2.21) controls the distance between the best function in G n and g n . The approximation error (2.22) is the smallest error for a function of G n .

			.21)
	and
	inf g∈Gn	E (g(X) -g * (X)) 2 = o P (1).	(2.22)

Table 2 .

 2

		X8
		X7
		X5
		X2
	Variable	X3
		X4
		X1
		X6
		X41
		0.0	0.2	0.4	0.6	0.8	1.0

1 -Summary of the M experiences for each algorithm. Nb Rules is the number of rules, Nb Linear (for RuleFit) is the number of linear components in the generated model and Interpretability is the interpretability index. Figure 2.4 -Empirical probability of occurrence in at least one rule of the selected set of rules generated by the Covering Algorithm.

Table 2 . 2

 22 p96-97[START_REF] Harrison | Hedonic housing prices and the demand for clean air[END_REF] for more details about the variables). The regression model explains the median house price Y of each neighborhood by the d = 13 others statistics of this neighborhood. The data are randomly split into a training set and a test set, with a ratio of 70% / 30%, respectively.

			Y	CRIM ZN INDUS CHAS NOX RM
	mean 22.53 3.61 11.36 11.14	0.069 0.55 6.28
	std		9.19	8.60 23.32	6.86	0.25	0.11 0.70
	min		5.00 0.006	0.0	0.46	0.0	0.38 3.56
	25% 17.02 0.08		0.0	5.19	0.0	0.44 5.88
	50% 21.20 0.25		0.0	9.69	0.0	0.53 6.20
	75% 25.00 3.67 12.50 18.10	0.0	0.62 6.62
	max	50	88.97 100.0 27.74	1.0	0.87 8.78
			AGE DIS RAD TAX PTRATIO	B	LSTAT
	mean 68.57 3.79 9.54 408.23	18.45	356.67 12.65
	std	28.14 2.10 8.70 168.53	2.16	91.29	7.14
	min		2.90 1.12	1.0	187.0		12.6	0.32	1.73
	25% 45.02 2.10	4.0	279.0		17.40	375.37	6.95
	50% 77.50 3.20	5.0	330.0		19.0	391.44 11.36
	75% 94.07 5.18 24.0 666.0		20.20	396.22 16.95
	max 100.0 12.12 24.00 711.0		22.0	396.90 37.97

-Description of variables.

Table 2 .

 2 and Covering Algorithm has a M SE of 25.35. This loss of accuracy is the price of turning a black box model into an interpretable one. According to (2.8) we have Int(g n ) = 20 for the Covering Algorithm and Int(g n ) = 29524 for the RF, which is a huge improvement of the interpretability index. 3 -Summary of the selected rules generated by Covering Algorithm.

	Rule	Conditions	Coverage Prediction Variance
	R1	LST AT ∈ [9.62, 37.97]	0.58	17.74	26.03
	R2	LST AT ∈ [1.73, 7.87]	0.31	32.31	78.57
		RM ∈ [3.86, 6.10]
	R3	LST AT ∈ [7.76, 37.97]	0.37	17.62	22.52
		DIS ∈ [1.20, 12.13]
		RM ∈ [6.10, 6.54]
	R4	LST AT ∈ [1.73, 9.98]	0.12	23.39	4.62
		DIS ∈ [1.42, 12.13]
		RM ∈ [6.42, 8.78]
	R5	LST AT ∈ [1.73, 14.40]	0.33	31.88	72.88
		DIS ∈ [1.20, 12.13]
		RM ∈ [6.09, 8.78]
	R6	LST AT ∈ [1.73, 9.98]	0.27	32.12	76.50
		CRIM ∈ [0.05, 88.98]
		RM ∈ [3.86, 6.12]
	R7	LST AT ∈ [8.13, 14.40]	0.08	21.17	3.69
		T AX ∈ [187.0, 298.0]
		LST AT ∈ [5.06, 37.97]
	R8	P T RAT IO ∈ [13.90, 22.0]	0.36	16.34	35.70
		IN DU S ∈ [15.01, 27.74]
	Algorithm	Nb rules		Interpretability M SE
	Random Forest	8490		29524	10.47
	Covering Algorithm	8		20	25.35
	RuleFit	602 and 1 linear component	602	10.46

Table 2 .

 2

4 -Comparison between Random Forest, Covering Algorithm and RuleFit on real data.

  3.14)) while CoveringAlgorithm uses a Random Forest as rule generator.

			mean		12596.36	60870.42	0.95
			std			3.62	349.37		0.05
			min		12584.00	60060.00	0.86
			25%		12596.00	60640.50	0.92
			50%		12598.00	60851.00	0.94
			75%		12598.00	61126.50	0.98
			max		12600.00	61530.00	1.12
			RICE Nb rules Interpretability M SE *
			mean	63.58		180.89	2.81
			std		8.24		21.85	0.23
			min		51.00		148.00	2.29
			25%		58.00		166.00	2.66
			50%		62.00		174.50	2.82
			75%		67.25		191.50	2.95
		X7	max		99.00		264.00	3.33
		X8	RuleFit Nb rules Nb linear Interpretability M SE *
		X1	mean	184.43	24.89	451.70	0.07
			std	17.91	6.61	51.24		0.01
	Variable	X2 X5	min 25% 50%	145.00 170.75 184.00	11.00 20.00 24.50	343.00 411.75 456.50	0.06 0.07 0.07
		X3	75%	199.00	29.00	492.25	0.08
			max	234.00	42.00	568.00	0.10
		X4
		X6
		0	5	10		15	20	25	30	35
			Figure 3.2 -Average occurrence in the selected set of rules generated by RICE.

Table 3 .

 3 2 -Summary of the M = 100 experiences for each algorithm. Nb Rules is the number of rules, Nb Linear (for RuleFit) is the number of linear components in the generated model and Interpretability is the interpretability index.

Table 3 .

 3

3 -Average over the M = 100 simulations for each algorithm as a function of d.

Table 3 .

 3 4 -Average over the M = 100 simulations for each algorithm as a function of n rules , the number of rules used to create g

* .

Table 4 .

 4 Key performance indicators of the MSCI World Index and three capitalization-weighted regional benchmarks, together with ESG bestin-class filtered portfolios with different thresholds: 10%, 30% and 50%. Data is shown in USD from August 2009 to March 2018. Source MSCI, Datastream, Sustainalytics.

			1 -World Developed			Table 4.2 -US
			ESG best-in-class			ESG best-in-class
		Bench.	10%	30%	50%		Bench.	10%	30%	50%
	Ann. Performance	10.07%	10.01%	9.93%	9.51%	Ann. Performance	13.45%	13.25%	13.46%	13.2%
	Ann. Volatility	13.34%	13.31%	13.44%	13.82%	Ann. Volatility	14.61%	14.54%	14.49%	14.4%
	Sharpe Ratio	0.73	0.73	0.72	0.67	Sharpe Ratio	0.9	0.89	0.91	0.9
	Max. Drawdown	-21.91%	-21.79%	-22.02%	-22.57%	Max. Drawdown	-18.99%	-18.87%	-18.71%	-18.04%
	Information Ratio	0	-0.27	-0.25	-0.41	Information Ratio	0	-0.71	0.02	-0.18
		Table 4.3 -Europe			Table 4.4 -Asia
			ESG best-in-class			ESG best-in-class
		Bench.	10%	30%	50%		Bench.	10%	30%	50%
	Ann. Performance	6.37%	6.55%	6.47%	6.31%	Ann. Performance	6.83%	6.71%	6.41%	5.75%
	Ann. Volatility	19.25%	19.19%	19.19%	19.29%	Ann. Volatility	15.54%	15.71%	16%	16.2%
	Sharpe Ratio	0.32	0.33	0.32	0.31	Sharpe Ratio	0.42	0.41	0.38	0.34
	Max. Drawdown	-30.25%	-30.21%	-30.2%	-30.54%	Max. Drawdown	-24.8%	-24.95%	-25.27%	-25.8%
	Information Ratio	0	0.43	0.22	-0.11	Information Ratio	0	-0.21	-0.36	-0.46

Table 4 .

 4

			5 -World Developed
		ESG	E	S	G
	CS	-0.26%	-0.45%	-0.65%	0.62%
		(-0.26)	(-0.47)	(-0.59)	(0.53)
	CD	-0.33%	-0.46%	-0.65%	-1.22%
		(-0.3)	(-0.46)	(-0.4)	(-0.65)
	EN	-0.24%	-0.41%	-0.26%	0.86%
		(-0.13)	(-0.19)	(-0.17)	(0.31)
	FI	-0.51%	-0.46%	-0.87%	0.19%
		(-0.43)	(-0.42)	(-0.63)	(0.13)
	HC	-0.39%	-0.5% (-0.3)	-0.47%	-0.53%
		(-0.35)		(-0.4)	(-0.43)
	IN	-0.31%	-0.32%	-0.32%	-0.33%
		(-0.28)	(-0.27)	(-0.31)	(-0.19)
	IT	-0.13%	-0.44%	-1.53%	0.1%
		(-0.12)	(-0.45)	(-0.52)	(0.05)
	MA	-0.09%	-0.09%	-0.17%	0.32%
		(-0.05)	(-0.03)	(-0.08)	(0.18)
	TL	1.26%	1.17%	0.15%	0.73%
		(0.64)	(0.74)	(0.06)	(0.21)
	UT	0.16%	-0.94%	0.72%	0.82%
		(0.1)	(-0.39)	(0.43)	(0.32)

Table 4 .

 4

			6 -US
		ESG	E	S	G
	CS	-0.94%	-0.46%	-0.46%	-0.26%
		(-0.84)	(-0.43)	(-0.32)	(-0.12)
	CD	-1.95%	-0.48%	-0.91%	-2.92%
		(-0.82)	(-0.39)	(-0.55)	(-0.98)
	EN	-0.09%	-0.66%	0.01%	0.55%
		(-0.06)	(-0.44)	(0.01)	(0.16)
	FI	-0.22%	-0.11%	-0.2%	1.02%
		(-0.19)	(-0.11)	(-0.17)	(0.67)
	HC	-0.23%	0.19%	-0.55%	-0.58%
		(-0.22)	(0.15)	(-0.5)	(-0.37)
	IN	0.4%	0.25%	0.01%	-0.6%
		(0.54)	(0.32)	(0.01)	(-0.56)
	IT	-1.36%	-0.7%	-1.76%	-0.37%
		(-0.96)	(-0.75)	(-0.51)	(-0.11)
	MA	0.34%	0.72%	-0.76%	-0.14%
		(0.18)	(0.32)	(-0.32)	(-0.07)
	TL	-0.38%	-0.32%	-0.4% (-0.2)	1.32%
		(-0.37)	(-0.38)		(0.28)
	UT	0.63%	0.47%	0.7% (0.7)	0.13%
		(0.56)	(0.38)		(0.12)

Table 4 .

 4

				7 -Europe
		ESG	E	S	G
	CS	0.16%	0.03%	-0.01%	0.39%
		(0.14)	(0.03)	(-0.01)	(0.32)
	CD	0.51%	0.45%	0.18%	1.07%
		(0.32)	(0.29)	(0.14)	(0.68)
	EN	-1.2% (-0.3)	-2.01%	-0.5%	-1.05%
			(-0.38)	(-0.12)	(-0.27)
	FI	0.31%	0.04%	0.33%	-0.28%
		(0.18)	(0.03)	(0.17)	(-0.21)
	HC	-0.38%	-0.44%	-0.53%	-0.11%
		(-0.49)	(-0.55)	(-0.67)	(-0.18)
	IN	0.03%	0.03%	-0.39%	-0.67%
		(0.03)	(0.03)	(-0.35)	(-0.44)
	IT	-0.63%	-1.13%	0.01%	-0.71%
		(-0.29)	(-0.49)	(0.08)	(-0.43)
	MA	0.12%	0.23%	0.51%	0.6%
		(0.03)	(0.06)	(0.14)	(0.18)
	TL	1.81%	1.72%	1.82%	2.06%
		(0.67)	(0.63)	(0.62)	(0.71)
	UT	1.79%	3.25%	0.09%	0.41%
		(0.54)	(0.87)	(0.03)	(0.16)

Table 4 .

 4 Annualized excess returns (Information ratios) between capitalization-weighted sector portfolios and their ESG best-in-class filtered versions for the MSCI World Index and the derived regional benchmarks. In bold pairs sector/indicator for which the excess return is positive. Best-in-class filters are performed with the ESG rating together with the single pillars Environment (E), Social (S) and Governance (G) ratings. Data is shown in USD from August 2009 to March 2018. Source MSCI, Datastream, Sustainalytics.

			8 -Asia
		ESG	E	S	G
	CS	0.6%	0.37%	-0.3%	-0.18%
		(0.52)	(0.12)	(-0.28)	(-0.09)
	CD	-0.29%	-0.11%	0.09%	0.75%
		(-0.19)	(-0.11)	(0.04)	(0.37)
	EN	0.12%	0.34%	0.03%	0.25%
		(0.04)	(0.11)	(0.01)	(0.1)
	FI	-0.27%	-0.09%	-0.71%	-0.08%
		(-0.16)	(-0.06)	(-0.46)	(-0.05)
	HC	0.29%	-0.67%	0.14%	-0.03%
		(0.19)	(-0.27)	(0.08)	(-0.02)
	IN	-0.76%	-0.41%	-0.42%	-0.61%
		(-0.39)	(-0.22)	(-0.22)	(-0.35)
	IT	-1.32%	-0.92%	-1.01%	-0.96%
		(-0.59)	(-0.4)	(-0.43)	(-0.28)
	MA	-0.29%	0.04%	-0.58%	-0.07%
		(-0.26)	(0.03)	(-0.44)	(-0.05)
	TL	0.17%	-0.18%	-0.61%	1.83%
		(0.04)	(-0.11)	(-0.09)	(0.24)
	UT	3.07%	-3.57%	0.16%	2.6%
		(0.65)	(-0.87)	(0.04)	(0.55)

Table 4 .

 4 10 -Key performance indicators of the MSCI World Index (Bench.), the capitalization-weighted selection filtered over positive scores from the ML algorithm, the one with the sector allocation matched to the benchmark, the one screened over negative scores and the 30% ESG best-in-class filtered portfolios. Data is shown in USD from January 2013 to March 2018. Source MSCI, Datastream, Sustainalytics.

				ML Screening		ESG
						best-in-class
		Bench.	Positive	Positive	Negative	30%
				Sect. Matched
	Ann. Performance	10.32%	13.07%	11.66%	8.31%	10.13%
	Ann. Volatility	10.50%	11.14%	10.96%	10.95%	10.57%
	Sharpe Ratio	0.94	1.14	1.03	0.72	0.92
	Max. Drawdown	-18.07%	-14.99%	-16.46%	-22.47%	-17.91%
	Information Ratio	-	1.01	0.58	-0.54	-0.32
	Ann. Alpha	-	2.47%	1.15%	-1.81%	-0.24%

Table 4 .

 4 11 -Calendar year performances for the MSCI World Index (Bench.) and the excess returns for the Positive, Positive Sect. Matched and Negative ML Screening as well as for the ESG 30% best-in-class portfolio. Data is shown in USD from January 2013 to March 2018. Source MSCI, Datastream, Sustainalytics.

	Excess Return
	ML Screening	ESG best-in-class

Table 5 .

 5 Algorithm Parameters N M SE training N M SE test Nb of rules Complexity max 3 -Performance results of RIPE compared to two supervised learning algorithms: The Decision Tree (DT) and the Random Forests (RF).Variable X 976 X 298 X 336 X 163 X 945 X 565 X 733

	DT	/		0.0		0.46	350		14
	RF	m_tree =	0.04		0.39	128.25 5	21
		200
		m_try =
		d/3
	RIPE	M =300		0.13		0.30	14		2
		z:	see
		(5.5.2)
		α=0.05
		Count	10	5	2	1	1	1	1

Table 5 .

 5 4 -Count of variable occurencies in rules selected by RIPE.

En effet on a |P n | = k n /n donc il y a au plus une cellule qui ne vérifie pas cette condition.

On reprend ici le tableau [20, Table2].

The redundancies conditions (2.13) and (2.14) are automatically controlled by the fixed maximal number of rules generated by RF.

This step was already described in Remark 5 in order to control the redundancy. Here it is only used for controlling the number of rules as the redundancy is already controlled by the maximal number of rules generated by RF.

Of course such procedure is performed only on real-valued features with more than m different values. Categorical features are left unchanged.

Remerciements

Approximately suitable data-dependent coverings

In order to ensure the consistency of data-dependent covering algorithm, [START_REF] Margot | Consistent regression using data-dependent coverings[END_REF] have introduced the notion of suitable sequence of data-dependent coverings. This definition used the notations of empirical measures for any r ⊆ R d such that

To simplify the notation we use Q n (r) instead of Q n (r×R) when no ambiguity is possible.

We also define

1 X j ∈r the empirical conditional expectation and

the empirical conditional variance.

A suitable sequence of data-dependent coverings, Definition 2.2.1, satisfies the coverage and the significance conditions. The first one controls the minimal number of observations in a rule, ensuring that its prediction based on the empirical conditional expectation is accurate. The second one controls the variance of the rules in two different ways; the significant rules are predicting significantly differently than the average and may have a large variance, the insignificant rules are not significant and have a small variance.

The main drawback of Definition 2.2.1 relies on the use of the parameter σ 2 , which is unknown in practice. A simple solution is to replace σ 2 by any consistent estimator of σ 2 n in the definition of (in)significant rules (3.12) and (3.13). See Section 3.5.7 for such an estimator. Definition 3.2.1. We call a sequence ( Ĉn ) n≥1 of data-dependent collections of sets of R d approximately suitable if it satisfies the two following conditions:

1. the coverage condition:

∃α ∈ [0, 1/2), ∀r ∈ Ĉn , Q n (r) > n -α P -a.s, (3.8) for n sufficiently large;

2. the approximately significance condition: there exist two sequences β n → 0 and ε n → 0 such that:

for n sufficiently large, where the approximately significant subsets Ĉs n are defined by

the approximately insignificant subsets Ĉi n are defined by

where x + = max{x, 0}. Assume moreover that Ĉs n and Ĉi n satisfy

Thus one can consider that C n is a covering of R d and the weak consistency still holds

Remark 12. The safe strategy of prediction presented in Section 3.3 does not alter the asymptotic properties of the algorithms for any x in the support of the X i as such cases disappear P-a.s when n → ∞ under condition (H13). Indeed, under (H13) the case of no prediction 3. is asymptotically P-negligible.

RICE: the algorithm

The Rule Induction Covering Algorithm (RICE) aims at designing quasi-coverings satisfying (H13) based on hyperrectangles which are all either approximately significant or insignificant (Definition 3.2.1). We supply an open source code of RICE in Python on GitHub.

The algorithm's steps (see Algorithm 4) consist in designing a set of hyperrectangle rules (see Algorithms 7 and 8) on a discretization of the feature space (see Algorithm 6), and then to select (see Algorithm 5) among them a subset of the significant rules and a subset of the insignificant rules such that (3.12) and (3.13) are fulfilled with σ 2 n instead of σ 2 . There is no guarantee that these sets of rules together constitute a covering of the feature space and even not a covering of the sample: whether condition (H13) is satisfied will be discussed.

Name

Range Description Default value -C n the set of selected rules

Proof. First, for any rule r fulfilling (3.8) and with

we have

Thus we obtain σ 2 n ≥ σ 2 -∆ n . Now, since for any rule r fulfilling (3.8), A rule r n obviously fulfills (3.20) as soon as g * |rn is constant for any n large enough. Such rules can reasonably be expected to be generated by RICE when g * is a constant piecewise function (e.g. if g * is a rule or a set of rules).

Another case where (3.20) holds is provided by the following lemma. Notice that, although the assumption of shrinking diameter for all rules is not desirable, the assumption that there should exist at least one sequence of rules with shrinking diameter is much milder.

Let us denote for any r ⊂ R d and with X distributed as (and independent of) X,

.

By convention Diam

Lemma 3.5.2. Assume that g * is uniformly continuous and that a rule r n can be chosen in R n for each n such that Diam Q (r n ) = o P (1).

Proof. We denote r = r n for simplicity and X r and X r two independent variables distributed as X given that X ∈ r. We obtain

Algorithm 7: Calc_length_1 Input:

-X the discretized features α the coverage rate parameter m n the number of bins Output:

-R the set of all rules of length 1 satisfying (3.

-X the discretized features α the coverage rate parameter -R 1 the k candidate rules of length 1 -R l-1 the k candidate rules of length l -1 Output:

-R l a set of rules of length l satisfying (3.8) select the set of rules used by the algorithm to make predictions. The aggregation set is used to fit the coefficients of the convex combination, in line with the expert aggregation theory of [6] and [23].

Independent Suitable Rules Let D N = ((x 1 , y 1 ), . . . , (x N , y N )) ∈ (X × R) N be the training set. Here y i denotes the 3-month return for some stock and x i is the d-dimensional vector of its ESG features. The training set consists of a large but finite numbers of (d+1)vectors spanning all stocks in the investment universe and all available dates. The training set D n ⊆ D N includes the first n data points in D N and D t = ((x n+1 , y n+1 ), . . . , (x N , y N )), the order being induced by the time. Definition 4.4.1. For any set E ⊂ X , we define

, here, by convention, 0 0 = 0. The set-valued map µ represents the conditional excess return of a stock over the benchmark, given that its ESG features x belong to E.

The hyper-rectangle r is called the condition and µ(r, D n ) is called the prediction of the rule f . The event {x ∈ r} is called the activation conditions of the rule f .

A rule f is completely defined by its condition r. So, with an abuse of notation, we do not distinguish between a rule and its condition. We define two crucial numbers for a rule:

The algorithm does not consider all the possible rules, but only those with a given coverage and significance. We call these rules suitable, and their definition is given below.

with C min and C max are suitably chosen in the calibration step.

Machine learning application

We now test the predictive power of the machine learning algorithm developed in Section 4.4 compared with the classical best-in-class approach. More precisely, we try to assess whether filtering stocks over scores derived from the algorithm outperforms the standard filtering over ESG ratings (best-in-class). For the sake of simplicity, we only present the World Developed universe and, among the strategies presented in Section 4.3, we only consider the 30% best-in-class, as it is very close to what investors look at for their ESG portfolios. We recall that this strategy excludes, at each monthly review, the stocks whose ESG ratings are in the lower tercile within each peer group, and finally scale the weights so that their sum is one. To insure replicability of the portfolio, the ESG ratings are taken four days before the review date (which is end-of-month). At the monthly review, we also build three portfolios based on the scores calculated with the machine learning algorithm, with the rules calculated at the end of the year that precedes the review:

Positive ML Screening: The portfolio selects all stocks in the investment universe whose scores are +1. The weights are finally scaled up to sum to one (maintaining Chapter 5

Rule Induction Partitioning Estimator: Design of an interpretable prediction algorithm

RIPE is a deterministic and easily understandable prediction algorithm developed for continuous and discrete ordered data. It infers a model, from a sample, to predict and to explain a real variable Y given an input variable X ∈ X (features). The algorithm extracts a sparse set of hyperrectangles r ⊂ X , which can be thought of as rules of the form If-Then. This set is then turned into a partition of the features space X of which each cell is explained as a list of rules with satisfied their If conditions. The process of RIPE is illustrated on simulated datasets and its efficiency compared with that of other usual algorithms.

Rule Induction Partitioning Estimator

The RIPE algorithm is based on rules. Rules considered in this paper are defined as follows:

Definition 5.1.4. A rule is an If-Then statement such that its If condition is a hyperrectangle r = d k=1 I k , where each I k is an interval of X k . Definition 5.1.5. For any set E ⊂ X , the empirical conditional expectation of Y given

, where, by convention, 0 0 = 0. The natural estimator of g * on any r ⊂ X is the empirical conditional expectation of Y given X ∈ r. A rule is completely defined by its condition r. So, by an abuse of notation we do not distinguish between a rule and its condition.

A set of rules S n is selected based on the sample D n . Then S n is turned into a partition of X denoted by K(S n ) (see Section 5.2.1). To make sure to define a covering of the features space the no rule satisfied statement is added to the set of hyperrectangles. Definition 5.1.6. The no rule satisfied statement for a set or rules S n , is an If-Then statement such that its If condition is the subset of X not covered by the union of the hyperrectangles of S n .

One can notice that it is not a rule according to the definition 5.1.4 because it is not necessarily defined on a hyperrectangle.

Finally, an estimator ĝSn of the regression function g * is defined:

with K n (x) the cell of K(S n ) which contains x. The partition itself is understandable. Indeed, the prediction ĝSn (x, D n ) of Y is of the form "If rules . . . are satisfied, then Y is predicted by . . . " The cells of K(S n ) are explained by sets of satisfied rules, and the values µ(K n (x), D n ) are the predicted values for Y .

Fundamental Concepts of RIPE

RIPE is based on two concepts, the partitioning trick and the suitable rule.

Partitioning Trick

The construction of a partition from a set of R hyperrectangles is time consuming and it is an exponential complexity operation and this construction occurs several times in the algorithm. To reduce the time and complexity we have developed the partitioning trick.

First, we remark that to calculate µ(K n (x), D n ), it is not necessary to build the partition, it is sufficient to identify the cell which contains x. It is a theoretical condition. However, it indicates that m n must be inversely related to d: The higher the dimension of the problem, the smaller the number of modalities. It is a way to avoid overfitting. We first define two crucial numbers: (5.2.3)

We are now able to define a suitable rule.

Definition 5.2.2. A rule r is a suitable rule for a sample D n if and only if it satisfies the two following conditions:

for a chosen function z.

The coverage condition (5.2.5) ensures that the coverage ratio n(r, D n )/n of a rule tends toward 0 for n → ∞. It is a necessary condition to prove the consistency of the estimator which it is the purpose of a companion paper.

The threshold in the significance condition (5.2.6) is to ensure that the local estimators defined on subsets r is different than the simplest estimator which is the one who is identically equal to µ(X , D n ).

RIPE generates rules of complexity c ≥ 2 by a suitable intersection of rules of complexity 1 and rule of complexity c -1. Definition 5.2.3. Two rules r i and r j define a suitable intersection if and only if they satisfy the two following conditions:

1. Intersection condition:

Complexity condition:

cp(r i ∩ r j ) = cp(r i ) + cp(r j ).

(5.2.8)

The intersection condition (5.2.7) avoids adding a useless condition for a rule. In other words, to define a suitable intersection r i and r j must not be satisfied for the same observations of D n . And the complexity condition (5.2.8) means that r i and r j have no marginal index k; 1 k X k , in common of X .

RIPE Algorithm

We now describe the methodology of RIPE for designing and selecting rules. The Python code is available at https://github.com/VMargot/RIPE.

The main algorithm is described as Algorithm 10. The methodology is divided into two parts. The first part aims at finding all suitable rule and the second one aims at selecting a small subset of suitable rules that estimate accurately the objective g * .

The parameters of the algorithm are:

m n , the sharpness of the discretization, which must fulfill (5.2.2); α ∈ [0, 1], which specifies the false rejecting rate of the test; z, the significance function of the test; -and M ∈ N, the number of rules of complexity 1 and c -1 used to define the rules of complexity c.

Algorithm 10: Main

Global parameters: m n , α, z and M ; Input:

-(X, y) ∈ R n(d+1) : data Output:

-S: the set of selected rules

10 end 11 R ← Sort_by_risk(R, ( X, y)); 12 S ← Select(R, ( X, y)); 13 Return S;

Designing Suitable Rules

The design of suitable rules is made recursively on their complexity. It stops at a complexity c if no rule is suitable or if the maximal complexity c = d is achieved.

Complexity 1:

The first step is to find suitable rules of complexity 1. This part is described as Algorithm 11. First notice that the complexity of evaluating all rules of complexity 1 is O(ndm 2 n ). Rules of complexity 1 are the base of RIPE search heuristic. So all rules are considered and just suitable are kept, i.e rules that satisfied the coverage condition (5.2.5) and the significance condition (5.2.6). Since rules are considered regardless of each others, the search can be parallelized.

At the end of this step, the set of suitable rules is sorted by their empirical risk (5.1.3), L n (ĝ {r} ), with ĝ{r} the predictor based on exactly one rule r.

Algorithm 11: Calc_cp1

Global parameters: m n , α and z; Input:

-(X, y) ∈ R n(d+1) : data h n : parameter Output:

-R: the set of all suitable rules of complexity 1; 1 R ← ∅; Among the suitable rules of complexity 1 and c -1 sorted by their empirical risk (5.1.3), RIPE selects the M first rules of each complexity (1 and c -1). Then it generates rules of complexity c by pairwise suitable intersection according to the definition 5.2.3. It is easy to see that the complexity of evaluating all rules of complexity c obtained from their intersections is then O(nM 2 ).

The parameter M is to control the computing time and it is fixed by the statistician. This part is described as Algorithm 12.

Algorithm 12: Calc_cpc

Global parameters: α, z and M ; Input:

Selection of Suitable Rules

After designing suitable rules, RIPE selects an optimal set of rules. Let R n be the set of all suitable rules generated by RIPE. The optimal subset S * n ⊂ R n is defined by

is the empirical risk (5.1.3) of the predictor based on S.

Each computation of the empirical risk (5.3.1) requires the partition from the set S of rules, as described in Section 5.2.1. The complexity to solve (5.3.1) naively, comparing all the possible sets of rules, is exponential in the number of suitable rules.

To work around this problem, RIPE uses Algorithm 13, a greedy recursive version of the naive algorithm: it does not explore all the subsets of R n . Instead, it starts with a single rule, the one with minimal risk, and iteratively keeps/leaves the rules by comparing the risk of a few combinations of these rules. More precisely, suppose that r 1 , . . . , r N are the suitable rules, sorted by increasing empirical risk; r 1 , . . . , r k , k < N, have already been tested; j of them, say S ⊂ {r 1 , . . . , r k } have been kept, the k -j other being left. Then r k+1 is tested in the following way :

-Compute the risk of S, S ∪ {r k+1 } and of all S ∪ {r k+1 }\{r} for r ∈ S; -Keep the rules corresponding to the minimal risk; -Possibly leave once for all, the rule in {r 1 , . . . , r k+1 } which is not kept at this stage. Thus, instead of testing the 2 N subsets of rules, we make N steps and at the k th step we test at most k + 2 (and usually much less) subsets, which leads to a theoretical overall maximum of O(N 2 ) tested subsets. The heuristic of this strategy is that rules with low risk are more likely to be part of low risk subsets of rules; and the minimal risk is searched in subsets of increasing size.

Algorithm 13: Select

Input:

-R: set of rules sorted by increasing risk -(X, y) ∈ R n(d+1) : data Output:

-S: subset of selected rules approaching the argmin (5.3.1) over all subsets of R ; 1 Set S = {R(1)}; 2 for i = 2, . . . , len(R) do

Experiments

The experiments have been done with Python. To assure reproducibility the random seed has been set at 42. The codes of these experiments are available in GitHub with the package RIPE.

Artificial Data

The purpose here it is to understand the process of RIPE, and how it can explain a phenomenon. We generate a dataset of n = 5000 observations with d = 10 features. The target variable Y depends on two features X 1 and X 2 whose are identically distributed on [-1, 1]. In order to simulate features assimilated to white noise, the others variables follow a centered-reduced normal distribution N (0, 1). The model is the following

with i ∼ N (0, 1) and

The dataset is randomly split into training set D 1 m and test set D 2 l such as D 1 m represents 60% of the dataset. RIPE uses significance test based on (5.5.2) with a threshold α = 0.05 and m n = 5.

On Figure 5.2, we have on the left, the true model (5.4.2) according to X 1 and X 2 with the realization of Y not used during the learning. On the right, the model inferred by RIPE.

On Figure 5.1 we represent the set of selected rules. In this case rules form a covering of the features space. So it is not necessary to add the no rule satisfied statement (see Def 5.1.6).

High Dimension Simulation

In this simulation, we use the function make_regression, from the Python package sklearn ( [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]), to generate a random linear regression model with n observations and d variables. Among these variables, p are informative and the rest are gaussian centered noise. In this example we take n = 500, d = 1000 and p = 5 to simulate a noisy high dimensional problem. The data are randomly split into a training set and a test set, with a ratio of 60% \40%, respectively.

We use two others algorithms in this case: Decision Tree (DT) [3] without pruning and Random Forests (RF) [2], all from the package of python sklearn [11]. In order to evaluate the performance of our model, the normalized mean square error (N M SE) is computed.

Results are sum up in Table 5.3. Difference between the N M SE of the training and the N M SE of test indicates that Decision Tree and Random Forests overfit in this context. Conversely, RIPE infers a model which is more general (see Tab 5.3). Indeed, RIPE is able to describe the model with only 14 rules (see Tab 5.2) which have conditions on only seven variables from 1000. Among these selected variables only two are very important X 976 and X 298 (see Tab 5.4).

In this case, RIPE discretizes each variable in 5 modalities from 0 to 4. Table 5.2 presents the selected rules with their conditions. The rule R14 is the no rule satisfied statement (see Definition 5.1.6).

List of Figures

List of Tables