Professor Massih-Reza Amini

Assistant Professor Yury Maximov

In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. To demonstrate the empirical efficiency of the proposed approaches we investigate their applications for decision making in recommender systems and energy systems domains.

For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed approach consists in minimizing pairwise ranking loss over blocks constituted by a sequence of non-clicked items followed by the clicked one for each user. We also explore the influence of long memory on the accurateness of predictions. SAROS shows highly competitive and promising results based on quality metrics and also it turn out faster in terms of loss convergence than stochastic gradient descent and batch classical approaches.

Regarding power systems, we propose an algorithm for faulted lines detection based on focusing of misclassifications in lines close to the true event location. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach based on convolutional neural networks for faults detection in power grid.

Résumé

Dans cette thèse, nous nous intéressons à l'étude des algorithmes d'apprentissage qui fournissent un ordonnancement personnalisé en s'adaptant au contexte. Pour démontrer l'efficacité empirique des approches proposées, nous étudions leurs applications pour la prise de décision dans les domaines des systèmes de recommandation et des systèmes énergétiques.

Pour notre étude concernant les systèmes de recommandation, nous proposons un nouvel algorithme appelé SAROS qui prend en compte les deux types de retours utilisateurs pour apprendre leurs appétances. L'approche proposée consiste à minimiser la perte d'ordonnancement par paires de produits dans des blocs d'interactions constitués d'une séquence d'éléments avec un retour négatif (ou non cliqués) suivis d'un produit avec un retour positif pour chaque utilisateur. Nous explorons également l'influence de la mémoire longue sur la précision des prédictions. Notre algorithme montre des résultats hautement compétitifs et prometteurs basés sur des métriques de qualité et il s'avère également plus rapide en termes de convergence par rapport à la descente de gradient stochastique et les approches classiques par lots.

En ce qui concerne les réseaux électriques, nous proposons un algorithme de détection des lignes défaillantes basé sur la focalisation des erreurs de classification dans les lignes proches du véritable emplacement de l'événement. L'idée proposée de prendre en compte les lignes voisines montre des résultats statistiquement significatifs par rapport à l'approche initiale basée sur les réseaux de neurones convolutifs pour la détection des défauts dans le réseau électrique. [START_REF] Grbovic | E-commerce in your inbox: Product recommendations at scale[END_REF].

Nomenclature

General Introduction

The various scientific communities such as computer scientists and statisticians have been interested for many years in the problems of data analysis. The different currents from these communities focused on a set of specific issues and created scientific fields that quickly evolved independently. This is for example the case of Information Retrieval (IR), Information Extraction, or in the case of statisticians, data science, etc. In recent years, the field of data analysis has undergone a rapid evolution, with in particular the development of large-scale collections. The boundaries that had been drawn between the different traditional domains of data analysis are currently largely redrawn to create a large domain that we designate here by information access. New problems appear, to which the various communities try to provide answers by adapting the existing tools, or by developing new tools. In particular, it has become important to be able to process huge amounts of data, to provide diversified solutions to new user demands, and to automate the tools that make it possible to exploit textual or image information.

More recently, the rapid development of techniques for the acquisition and storage of digital information has favored the explosion of the quantities of information to be processed, but also the diversity of their content. Thus, information to be processed takes forms as diverse as sequences of interactions, textual documents, images, music videos or even music. User needs have also evolved. Information systems must not only help them find the information they are looking for, but also advise them or make new suggestions. This is the main purpose of recommendation systems, which suggest to their users items likely to interest them: books, films, music albums, etc.

Machine learning offers a range of tools to move in these directions. It is within this framework that our work is situated, which aims to explore the potential of learning techniques to meet the needs of users and to detect fault lines in energy systems. In the case of textual information retrieval, for example, machine learning models are based on the assumption that it is possible to perform many textual information processing tasks by fairly crude analyzes of the text. Thus, any learning algorithm works from an initially known and fixed data representation. It is common to pre-process the data in order to modify this initial representation. The learning algorithm is then used on the new representation obtained. Learning about this new representation has several advantages: gains in algorithmic complexity and memory space, as well as the possibility of interpreting or visualizing the data. On the other hand, the influence of the new representation on the performance in prediction is more difficult to analyze. In the ideal case, we of course want the new representation to improve the prediction performance of the learning algorithms. In recommender systems for example, the new representation of users and items should make it possible to order higher items that are of the interest of users with respect to the others using the dot product in the latent learned space. In supervised learning, the new representation of the data should make it possible to make fewer prediction errors. The choice of the new representation, and therefore the choice of the method used to modify the initial representation, thus seems essential in learning.

Contributions

In this thesis we first propose to learn the palatability of users for items by exploiting their sequences of interactions using ranking models that take into account both positive and negative feedback. Most of the state-of-the-art systems consider only the items in the sequence of interactions for which a user has provided positive feedback. The incentive of using not only positive feedback is that it difficult to understand which items a user really likes and determine the characteristics of his or her consumption/action based only on the information about the clicks/purchases/likes/views etc. We suggest to avoid this problem and to increase the quality of the ranking by considering also negative interactions of user with the system. The proposed approach hence constructs a ranking model by taking user' negative and positive sequence of interactions.

We tackle this problem from a learning to rank perspective, which involves sorting instances in relation to a demand. In any case, we are all confronted with task ranking in our everyday lives. We make decisions all of the time by intuitively constructing a scale of preferences for ourselves, based on which we choose one instance over another. For example, we may go to the automobile service for maintenance and then decide, based on the outcome, whether we would repair everything the service personnel suggests or only the most urgent problems at the time, given our budget. There are many different types of ranking systems that we encounter, such as document search engines or recommender systems.

Companies may offer individualized and relevant suggestions using a properly set ranking model. Because a consumer spends the least amount of time searching for the right things and getting what he wants, his loyalty to the platform increases when he spends the least amount of time searching for the right things and getting what he wants with their help, the search time for the necessary items is reduced, and the likelihood of performing related targeted actions increases.

At the same time, development of a personalized large-scale ranking system is a serious and complex task. Formally, as in any supervised machine learning task, we need to build a function that fit the data in the best way. The input data for the training such function are the features of the system. For example, in case of fault detection problem in power systems, voltage information could be used to detect a location of contingencies, if any exists. Considering recommender system task, its possible to apply the user description or item descriptions to identify relevant items.

The important factors that affect the quality of ranking are how to take into account the features extracted for training. That is why its crucial to define what kind of feedback or characteristics of system to use. Another key point for building relevant ranking model is time. To provide fast predictions for ranking especially for predicting abnormal/dangerous behavior of the system is critical.

The detection of faults in power networks is the second subject we looked at in this thesis. In this scenario, we show that by utilizing grid's topology, significant characteristics for forecasting faults in its line may be deduced.

In resume the applications we studied in this thesis are

• Recommender systems: We proposed an algorithm that learns user and item representation over time while taking into account users' negative and positive feedback. As a result, the suggested method constructs blocks over the input sequence of feedbacks, which is composed of a series of negative items followed by positive items. We proved the convergence of the algorithm in the general case of non-convex loss functions and showed its efficiency compared to the state-of-the-art models over six large-scale benchmarks. A hybrid technique was also presented to speed up the algorithm in practice, including pre-filtering of input users.

• Power grids: We also considered the problem of faults detection in power grids. The idea to improve the quality of predictions lies on taking into account the structure or the topology of the power grid.

Thesis Structure

This thesis is organized in two parts. In the first part, we present state-of-the-art frameworks and approaches related to our study. In the second part, we present our contributions.

The first part of this thesis consists of two chapters.

* In chapter 2, we present the main statistical supervised learning frameworks which are classification and ranking. For each learning framework, we present the important concepts and algorithms that will be useful to us in the second part of the thesis.

* In chapter 3, we present recent approaches in recommender systems.

The second part of this thesis consists of three chapters.

* In chapter 4, we present SAROS which is a sequential ranking algorithm for recommendation. Based on the assumption that users are shown a set of items sequentially, and that positive feedback convey relevant information for the problem in hand, the proposed algorithm updates the weights of a scoring function whenever an active user interacts with the system, by clicking on a shown item. We prove that these sequential updates of the weights converge to the global minimal of a convex surrogate ranking loss estimated over the total set of users who interacted with the system.

* In chapter 5, we propose a unified framework for convergence analysis of SAROS, in the general case of non-convex ranking losses. Furthermore, we study the effect of non-stationarities and memory in the learnability of a sequential recommender system that exploits user's implicit feedback.

* In chapter 6 we present our work for the problem of fault detection in power grids. The main idea is first to characterize a power grid by exploiting its topology then to learn a prediction function by minimizing a loss where the errors that are farther away from the true location are penalized more than errors that are nearer to the true location. This is done by considering additional terms in the loss function that take into account the neighbours of the faulted line. Finally, using the statistical Mann-Whitney U-test we show the efficiency of the proposed approach.

Finally, in chapter 7 we conclude our work and present directions for future work.

Corresponding articles

The contributions of this manuscript are based on the following articles, prepared in scope of the research made during this Ph.D. As all the papers are published with a large number of co-authors, it should be noticed that the personal contribution to the papers includes all the experimental parts, except memory estimation in Chapter 5 as well as the partial contribution in the theoretical parts under the supervision of Yury Maximov, Marianne Clausel and Massih-Reza Amini.

Chapter 4 is based on the paper [4] published at the European Conference in Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD 2019)

In this paper, we proposed a theoretically founded sequential strategy for training large-scale Recommender Systems (RS) over implicit feedback mainly in the form of clicks. The proposed approach consists in minimizing pairwise ranking loss over blocks of consecutive items constituted by a sequence of non-clicked items followed by a clicked one for each user. Parameter updates are discarded if for a given user the number of sequential blocks is below or above some given thresholds estimated over the distribution of the number of blocks in the training set. This is to prevent from updating the parameters for an abnormally high number of clicks over some targeted items, mainly due to bots; or very few user interactions. Both scenarios affect the decision of RS and imply a shift over the distribution of items that are shown to the users. We provide a proof of convergence of the algorithm to the minimizer of the ranking loss, in the case where the latter is convex. Furthermore, experimental results on five large-scale collections demonstrate the efficiency of the proposed algorithm concerning the state-of-the-art approaches, both regarding different ranking measures and computation time.

Chapter 5, is based on two papers published respectively in Journal of Artificial Intelligence Research (JAIR 2022) [START_REF] Burashnikova | Learning over no-preferred and preferred sequence of items for robust recommendation[END_REF] and the European Confernence in Information Retrieval (ECIR 2022) [START_REF] Burashnikova | Recommender systems: when memory matters[END_REF].

The journal paper is a continuation of the paper [4]. Here, additionally to the gradient-based strategy proposed in SAROS, we present the momentum method for updating the parameters. Furthermore, we provide a convergence analysis of both algorithms for the general case, when ranking loss is non-convex, whereas in [4] we made it just for the convex loss function. The set of benchmarks also was extended by RecSys'16, that is a fairly large dataset and completely satisfy the task we are solving. The set of baselines algorithms also was increased by powerful graph-neural network based approach for impartial comparison of our algorithm with "fresh" state-of-the-arts.

In [START_REF] Burashnikova | Recommender systems: when memory matters[END_REF] we studied the effect of long memory over the user interactions in large-scale recommender systems. In essence, the paper proposes the idea of filtering the training data based on the concept of memory. Our finding led to an improvement of the empirical results, that confirmed our idea about the redundancy of information in the input data affecting the learning process.

Chapter 6 is supposed to be submitted at IEEE Control Systems Letters soon.

Climate change increases the number of extreme weather events (wind and snowstorms, heavy rains, wildfires) that compromise power system reliability and lead to multiple equipment failures. Real-time and accurate detecting of potential line failures is the first step to mitigating the extreme weather impact, followed by activating emergency controls. Power balance equations non-linearity, increased uncertainty in renewable generation, and lack of grid observability compromise the efficiency of traditional data-driven failure detection methods. At the same time, modern problem-oblivious machine learning methods based on neural networks require a large amount of data to detect an accident, especially in a time-changing environment. In this paper, we propose a Topology-Aware Line failure Detector (TALD) that leverages grid topology information to reduce sample and time complexities and improve localization accuracy. Finally, we illustrate superior empirical performance of our approach compared to state-ofthe-art method over various IEEE test cases.

Part I

State-of-the-art

Chapter 2

Supervised Learning

Introduction

In this chapter, we present the two main frameworks in supervised learning which are classification and ranking. For each of these two frameworks, we present the important concepts and the algorithms that will be useful to us for the rest of our work.

In supervised learning, the goal is to learn the probabilistic relation (or joint distribution) between the examples (mostly in vector form) 𝑥 ∈ 𝒳 and their outputs 𝑦 ∈ 𝒴. This training is done using a training set which contains labeled examples {(𝑥 𝑖 , 𝑦 𝑖 ) | 𝑖 = 1, ..., 𝑚} that are supposed to be identically and independently distributed with respect to a joint probability 𝒟 𝒳 ,𝒴 . In classification and ranking, the output set 𝒴 is discrete and they have two distinct goals. In classification, the aim is to predict the class label of an example, while in ranking the aim is to rank examples with respect to their outputs.

We note another important framework in supervised learning that is not covered here and which is regression. The main difference between regression and the two aforementioned frameworks is that the output set is, in the case of regression, continuous (i.e. 𝒴 ⊂ R).

Currently, a large number of algorithms for supervised learning have been developed for solving both classification and ranking problems, each of them has its own strengths and weaknesses. That goes without saying that the most of the recent proposed stateof-the-art approaches are based on neural networks.

This chapter is composed of three sections. We start by briefly presenting the supervised learning theory in section 2.2. Following that, we present classification in section 2.4, and then ranking in section 2.5. Note that this chapter is not an exhaustive description of the algorithms developed in these two frameworks. We therefore focus our presentation on the concepts and algorithms that we will need in our contributions (see part II).

A brief presentation of the learning theory

A supervised learning algorithm learns a prediction function from a set of examples, called training set. Each example is composed of a pair (observation, output). The goal of learning is to find a prediction function able of predicting the outputs associated with new examples, i.e. examples that do not belong to the training set.

In practice, a loss function measures the (dis)agreement between prediction and desired output (also called label ). The smaller the error, the better the prediction. Thus, the learning algorithm chooses the prediction function that minimizes the average error on the training examples, called empirical risk. This is the Empirical Risk Minimization (ERM) principle. By minimizing the empirical risk, we hope that the prediction function will have a low generalization error, i.e it will make few errors on average on new examples. The underlying assumption is that the new examples are identical, in one way or another, to the training examples that were used to find the prediction function. The study of the link between empirical error and error in generalization is at the heart of the theory of statistical learning [Vapnik, 2000]. The main result of this study is that learning is a compromise between a low empirical error and a high complexity of the class of functions where the prediction function is to be found. This is called the Structural Risk Minimization (SRM) principle. In the following we will describe in detail these notions.

Definitions and notations

We begin by giving some definitions and notations that we will use in the remainder of this thesis. An example is a pair consisting of an observation and a desired output. Observations have a numerical representation in a vector space 𝒳 , typically 𝒳 ⊂ R 𝑑 for fixed 𝑑. The response will be called the desired output, and it is assumed to be part of an output set 𝒴. A pair (𝑥, 𝑦) will designate an element of 𝒳 × 𝒴.

Central Assumption

The fundamental assumption of statistical learning theory is that all examples are independently and identically distributed (i.i.d.) by a fixed but unknown probability distribution 𝒟 . Thus for any set 𝑆, the examples (𝑥 𝑖 , 𝑦 𝑖 ) ∈ 𝑆 are generated i.i.d; according to 𝒟. We then say that 𝑆 is a i.i.d. sample following 𝒟. Informally, this hypothesis defines the notion of representativeness of a training set or test in relation to the problem: the training examples, as well as future observations and their desired output, come from a given source.

Loss functions

The second fundamental notion in learning is the notion of error, also called risk or loss. Given a prediction function 𝑓 , the agreement between the prediction 𝑓 (𝑥) and the desired output 𝑦 for a pair (𝑥, 𝑦) is measured using a function ℓ 𝑐 : 𝒴 × 𝒴 → R + . Intuitively, ℓ 𝑐 (𝑓 (𝑥), 𝑦) measures the similarity between the predicted and the desired output. It is therefore generally a distance over the set of outputs 𝒴. In classification, the error generally considered is the 0/1 loss:

ℓ 𝑐 (𝑓 (𝑥), 𝑦) = 1 𝑓 (𝑥)̸ =𝑦 .
Where 1 𝜋 is 1 if the predicate 𝜋 is true and 0 otherwise. In other words the loss of a prediction error on the label of an example 𝑥 is worth 1.

In bipartite ranking, which consists in assigning a higher score to a relevant observation 𝑥 (i.e. having a positive output 𝑦 = +1) than to an irrelevant one (i.e. having a negative output 𝑦 = -1), a classical ranking loss ℓ 𝑟 : (𝒴 × 𝒴) 2 → R + is to count an error when the ordering induced by a scoring function 𝑓 : 𝒳 → R is reversed. Hence ℓ 𝑟 ((𝑓 (𝑥), 𝑦), (𝑓 (𝑥 ′ ), 𝑦 ′ ) = 1 (𝑦-𝑦 ′ )(𝑓 (𝑥)-𝑓 (𝑥 ′ ))≤0 .

Generalization error and empirical error

We are now able to give the definition of the error associated with a prediction function 𝑓 on all examples (𝑥, 𝑦) from (𝒳 × 𝒴). This quantity is called generalization error which in the case of classification can be written as:

ℒ(𝑓 ) = E 𝒟 [ℓ(𝑓 (𝑥), 𝑦)] = ∫ 𝒳 ×𝒴 ℓ(𝑓 (𝑥), 𝑦)𝑑𝒟(𝑥, 𝑦) (2.1)
The function 𝑓 that is of interest is the one that makes the fewest prediction errors on new examples, it is therefore the one that minimizes ℒ(𝑓 ). However, as the probability distribution 𝒟 is unknown, this error in generalization cannot be directly estimated. [Vapnik, 2000] has shown that the search for the function 𝑓 can be done in a consistent way by optimizing the average error of 𝑓 on a training set 𝑆 = ((𝑥 𝑖 , 𝑦 𝑖 )) 1≤𝑖≤𝑚 . This quantity is an unbiased estimator of generalization error and is commonly called the empirical risk of 𝑓 on 𝑆:

L𝑚 (𝑓, 𝑆) = 1 𝑚 𝑚 ∑ 𝑖=1 ℓ(𝑓 (𝑥 𝑖 ), 𝑦 𝑖 ) (2.2)
Vapnik's ERM principle as well as the concepts mentioned above will be explained in the following paragraphs.

Learning algorithm and ERM principle

𝑓 𝑆 = arg min 𝑓 ∈ℱ 1 𝑚 ∑ (𝑥 𝑖 ,𝑦 𝑖 )∈𝑆 ℓ(𝑓 (𝑥 𝑖 ), 𝑦 𝑖 ) (2.3)
Generalization and consistency of a learning algorithm Let us underline that the minimization of the empirical error is not an end in itself, what interests us being the minimization of generalization error. Thus, the ERM algorithm is of no use to us if the function learned 𝑓 𝑆 has a low empirical error and a high generalization error. We will therefore expect from the ERM algorithm that it generalizes, ie that the empirical error of 𝑓 𝑆 is a good estimator of its generalization error. If this property of generalization holds, then we know that if ERM returns the low empirical error function 𝑓 𝑆 , then its generalization error will probably be low too.

Let us also insist on the fact that the ERM algorithm works in a known and fixed space of functions ℱ. The functions considered for the search for the lowest generalization error are elements of ℱ. Thus, a second naturally desirable property of the ERM algorithm is that it eventually finds the best function of ℱ (for error in generalization) provided it has enough examples to learn from. This property is called the consistency.

For learning to have meaning, the ERM algorithm must therefore verify the two previous properties. However, studies show that generalization and consistency are closely linked to the notion of complexity of the class of functions ℱ considered.

Overfitting and complexity of a class of functions Let us first focus on the generalization property of the ERM algorithm. For certain classes of functions ℱ whose empirical error of the learned function 𝑓 𝑆 is not a good estimator of its generalization error. We guess that it is better to avoid that the learned function is too complex compared to the training samples. Indeed it is easy to find a function having a null empirical loss on a training set, and arbitrarily a high generalization error. This phenomenon is called overfitting and is illustrated in figure 2-1.

Figure 2-1: Illustration of the overfitting phenomena on a classification problem where the aim is to separate between blue and red points. A complex model will fit exactly the data on the training set (square middle) by having an empirical error equal to 0, but on other points outside the square (test points) it does a lot of mistake.

So we want the ERM algorithm to learn simple functions. A way to impose simplicity is to constrain the class of functions ℱ to contain only simple functions (the notion of simplicity remains to be defined). By doing so, it is possible to show that for ERM, the properties of generalization and consistency are equivalent: by limiting the complexity of the class of functions ℱ, we therefore guarantee the generalization and the consistency of the ERM algorithm.

On the other hand, if ℱ is too simple compared to the distribution 𝒟, then the learned function will probably not have good performance in generalization. Both its empirical error and its error in generalization will be high. We thus see that the choice of the space of hypotheses ℱ is crucial: it must be neither too complex to avoid the problem of overfitting, nor too simple in order to avoid the problem of underfitting and to achieve good performance in generalization anyway. This trade-off between low empirical error and a complex class of functions, also known as the bias-variance trade-off, is fundamental in machine learning. This tradeoff is illustrated in figure 2 The prediction error is displayed with regard to the complexity of the class of hypotheses in this illustration of the bias-variance trade-off. Both the generalization error and the empirical error are large for a class of hypotheses with little complexity. This is referred to as underfitting. When the complexity of the class of functions grows, both the empirical and true errors decline until a point at which the generalization error starts to increase while the empirical error continues to fall. This is referred to as overfitting. On the class of hypotheses with the lowest generalization error, the best model may be identified.

VC Dimension

We now know that in learning it is crucial to be able to limit the complexity of the class of functions considered. For this, we must first define a way to define this complexity. In the case of binary classification, a fundamental measure of the generalization capacity developed by [Vapnik, 2000] is the Vapnik-Chervonenkis dimension; or the VC dimension in short.

Let ℱ be a class of functions from 𝒳 into 𝒴 = {-1, 1} and 𝑋 = (𝑥 1 , . . . , 𝑥 𝑚 ) a set observations in 𝒳 . Consider

𝒮 = {((𝑥 1 , 𝑦 1 ), . . . , (𝑥 𝑚 , 𝑦 𝑚 )) |(𝑦 1 , . . . , 𝑦 𝑚 ) ∈ 𝒴 𝑚 }
in other terms 𝒮 is the set of observations with all possible labelings. The class of functions ℱ shatters the set of observations 𝑋 if whatever the set of examples 𝑆 ∈ (𝒳 × 𝒴) 𝑚 , there is a classifier 𝑓 ∈ ℱ able to correctly classify all examples of 𝑆. The VC dimension of ℱ is the maximum number of points such that the function class can generate all possible classifications on this set of points. We then say that the set is shattered by ℱ. The notion of complexity of a class of functions defined by its dimension VC is therefore linked to this notion of shattering: the more a class of functions is capable of shattering a large number of points, the more complex it is.

Rademacher complexity Another classical measure of the complexity of a class of functions is the Rademacher complexity [START_REF] Bartlett | Rademacher and gaussian complexities: Risk bounds and structural results[END_REF]. This measure estimates how well a class of functions ℱ = {𝑓 : 𝒳 → {-1, +1}} can learn over a randomly noisy training set. Consider 𝜎 = {𝜎 1 , . . . , 𝜎 𝑚 } a set of 𝑚 binary random variables where each 𝜎 𝑖 ∈ 𝜎, called the Rademacher variable, takes a value -1 or +1 with probability 1 2 ; i.e. ∀𝑖 ∈ {1, . . . , 𝑚}; P(𝜎 𝑖 = -1) = P(𝜎 𝑖 = -1) = 1 2 . Then the empirical Rademacher complexity of ℱ over a training set 𝑆 = (𝑥 𝑖 , 𝑦 𝑖 ) 1≤𝑖≤𝑚 of size 𝑚 is defined as:

F𝑚 (ℱ, 𝑆) = 2 𝑚 E 𝜎 [ 𝑠𝑢𝑝 𝑓 ∈ℱ ⃒ ⃒ ⃒ ⃒ ⃒ 𝑚 ∑ 𝑖=1 𝜎 𝑖 𝑓 (𝑥 𝑖 ) ⃒ ⃒ ⃒ ⃒ ⃒ ] ,
Hence the higher the Rademacher complexity, the higher the ability of the class of function ℱ to fit random (Rademacher) noise. The corresponding Rademacher complexity is then defined as

F 𝑚 (ℱ) = E 𝑆 [ F𝑚 (ℱ, 𝑆)].
The main difference between VC diemension and the Rademacher complexity is that the latter can be easily upper-bounded for some class of functions.

Generalization bounds

The study of the relationship between empirical error, error in generalization and complexity of the class of functions is at the heart of the statistical learning theory. Most of these works take the form of probabilistic error bounds providing an upperbound of the generalization error that holds with high probability with respect to the empirical error, the complexity of the considered class of an some residual term that controls the precision of the bound; as the following Rademacher generalization bound.

Theorem 1 (Generalization bound [START_REF] Bartlett | Rademacher and gaussian complexities: Risk bounds and structural results[END_REF]) Let 𝒳 ∈ R 𝑑 be a vectorial space and 𝒴 = {-1, +1} an output space. Suppose that the pairs of examples (𝑥, 𝑦) ∈ 𝒳 × 𝒴 are generated i.i.d. with respect to the distribution probability 𝒟. Let ℱ be a class of functions having values in 𝒴 and ℓ : 𝒴 × 𝒴 → [0, 1] a given instantaneous loss. Then for all 𝛿 ∈]0, 1], we have with probability at least 1 -𝛿 the following inequality :

∀𝑓 ∈ ℱ, ℒ(𝑓 ) ≤ L𝑚 (𝑓, 𝑆) + F 𝑚 (ℓ ∘ ℱ) + √ ln 1 𝛿 2𝑚 (2.4)
Using the same steps we can also show that with probability at least 1 -𝛿

ℒ(𝑓 ) ≤ L𝑚 (𝑓, 𝑆) + F𝑚 (ℓ ∘ ℱ, 𝑆) + 3 √ ln 2 𝛿 2𝑚 (2.5)
Where ℓ ∘ ℱ = {(𝑥, 𝑦) ↦ → ℓ(𝑓 (𝑥), 𝑦) | 𝑓 ∈ ℱ}. It is therefore clear that to have a low risk, the two terms on the right of these inequalities (2.4) or (2.5) must be low: the empirical error which depends on the prediction function 𝑓 , and the second term which depends on the complexity of the class of functions ℱ. To have a theoretical guarantee on the error in generalization, it is therefore not only necessary to minimize the empirical error, it is also necessary to choose a class of functions that is not too complex (having a high complexity term). But it should not be too simple, otherwise the empirical error will be high. We therefore find the bias-variance trade-off, which we have already highlighted previously. We also mention some theoretical results in multi-class (extreme) classification establishing state-of-the-art bounds [Maximov andReshetova, 2016, Yin et al., 2019]. Another line of research proposes reduction from multi-class to binary classification [Joshi et al., 2017, Rifkin and[START_REF] Rifkin | [END_REF]. We also mention a few extensive surveys on semi-supervised classification [START_REF] Amini | Self-training: A survey[END_REF], Van Engelen and Hoos, 2020, Maximov et al., 2018] and co-training [START_REF] Amini | Self-training: A survey[END_REF].

Structural risk minimization

We previously underlined that the main difficulty in supervised learning resides in the choice of the class of functions, because it is this choice that implements the bias-variance trade-off. However, the previous generalization bound suggests a simple strategy to determine the adequate class of functions. Consider several classes of candidate functions ℱ 1 , . . . , ℱ 𝑁 whose Rademacher complexity we know. For each class, we can find a function by the ERM algorithm, then calculate the value of the bound on the generalization error. The class of functions which minimizes this bound obtains the best theoretical guarantee on the error in generalization among the classes of candidate functions. It is therefore naturally this one that we want to select. This is exactly the principle of structural risk minimization (SRM) [Vapnik, 2000].

The two principles of empirical risk minimization and risk minimization structural risk are at the origin of a large number of learning algorithms, and can explain the algorithms that existed before the establishment of this theory. This is particularly the case of support vector machines (SVM), whose empirical success could be justified after the fact thanks to the SRM principle.

First-order methods

Minimization problems related to the ERM or SRM principles are solved using optimization techniques, whose development is sometimes strongly tied to those of the Machine Learning field. Without doubt, the Gradient Descent (GD) algorithm is the most widely used of the several optimization techniques employed in Machine Learning. GD is a first-order optimisation procedure that iteratively finds the (local) minimum of a convex differentiable surrogate function of the (regularized) 0/1 loss.

The algorithm is based on the observation that if the loss function L to be minimized is defined and differentiable in a neighborhood of a weight vector 𝑤 (𝑡) then the loss decreases if one goes from the actual value of the loss L(𝑤 (𝑡) ), one step 𝜂 𝑡 ∈ R +called the learning rate, following a descente direction p 𝑡 defined as p ⊤ 𝑡 ∇ L(𝑤 (𝑡) ) ≤ 0. It then comes that for a small learning rate 𝜂 𝑡 if we define the new weight vector 𝑤 (𝑡+1) as

𝑤 (𝑡+1) = 𝑤 (𝑡) + 𝜂 𝑡 p 𝑡 , (2.6)
then L(𝑤 (𝑡+1) ) ≤ L(𝑤 (𝑡) ).

(2.7)

It is obvious that if 𝜂 𝑡 is too small then the decreasing condition (2.7) does not guarantee to reach a local minima, or the true minimum, of L. At each iteration of GD, the following sufficient conditions, known as Wolfe conditions [Wolfe, 1969], have been proposed in order to ensure the convergence of the algorithm.

• The decreasing of L should not be too small with respect to the length of the jumps. Hence for a given 𝛼 ∈ (0, 1),

∀𝑡 ∈ N * , L(𝑤 (𝑡) + 𝜂 𝑡 p 𝑡 ) L(𝑤 (𝑡) ) + 𝛼𝜂 𝑡 p ⊤ 𝑡 ∇ L(𝑤 (𝑡) ) (2.8)
This is known as the Armijo condition.

• There should be a change in the curvature of the loss function after each update.

Or equivalently the slope has decreased sufficiently; i.e. ∃𝛽 ∈ (𝛼, 1) such that

∀𝑡 ∈ N * , p ⊤ 𝑡 ∇ L(𝑤 (𝑡) + 𝜂 𝑡 p 𝑡 ) 𝛽p ⊤ 𝑡 ∇ L(𝑤 (𝑡) ) (2.9)
This is known as the curvature condition.

These conditions are shown in Figure 2-3 which for a given weight 𝑤 (𝑡) and a descent direction p 𝑡 depicts the loss L(𝑤 (𝑡) + 𝜂p 𝑡 ) with respect to the learning rate 𝜂 𝑡 . At 𝑤 (𝑡) , the objective is to find a learning rate 𝜂 𝑡 which guarantees that the decreasing of L is not too small with respect to the length of the jumps of the update; and that the slope has been reduced sufficiently. At L(𝑤 (𝑡) ) (i.e. 𝜂 𝑡 = 0) the equation of the tangent to the loss with respect to 𝜂 is 𝜂 ↦ → L(𝑤 (𝑡) ) + 𝜂p ⊤ 𝑡 ∇ L(𝑤 (𝑡) ). For 𝛼 ∈ (0, 1) , the line 𝜂 ↦ → L(𝑤 (𝑡) ) + 𝛼𝜂p ⊤ 𝑡 ∇ L(𝑤 (𝑡) ) has a slope smaller in absolute value than the one of the tangent; hence providing an upper bound on the value of admissible learning rate. The Armijo condition stipulates that the value of 𝜂 should be lower than this upper-bound. For a given 𝛽 ∈ (𝛼, 1); the slope 𝛽p ⊤ 𝑡 ∇ L(𝑤 (𝑡) ) will be between p ⊤ 𝑡 ∇ L(𝑤 (𝑡) ) and 𝛼p ⊤ 𝑡 ∇ L(𝑤 (𝑡) ) in absolute value. The curvature condition then ensures that the curvature of the loss on the new weight vector should be smaller than 𝛽p ⊤ 𝑡 ∇ L(𝑤 (𝑡) ). In practice, a line search method is used to determine the learning rate at each iteration. It entails starting with a large value of the learning rate 𝜂 0 and then shrinking it iteratively by multiplying the current value with a factor 1 > 𝑎 > 0 (i.e., backtracking) until the Armijo condition is met.

In the case where the loss function is convex and differentiable and that its gradient is Lipschitz continuous with parameter 𝐿 > 0 defined as:

Definition 1 The gradient of L is Lipschitz continuous with parameter 𝐿 > 0 if ∀𝑤, 𝑤 ′ ; ‖∇ L(𝑤) -∇ L(𝑤 ′ )‖ 2 ≤ 𝐿‖𝑤 -𝑤 ′ ‖ 2
(2.10) Then the gradient descent algorithm is ensured to converge to the local minima of L as stated in the following theorem.

Theorem 2 ( [Zoutendijk, 1966]) Let L be a differentiable objective function with a Lipschtiz continuous gradient and lower bounded. Suppose that the GD algorithm generates (𝑤 (𝑡) ) 𝑡∈N defined by ∀𝑡 ∈ N, 𝑤 (𝑡+1) = 𝑤 (𝑡) + 𝜂 𝑡 p 𝑡 ; where p 𝑡 is a descent direction of L and 𝜂 𝑡 a learning rate verifying both Wolfe conditions (2.8) and (2.9). By considering the angle 𝜃 𝑡 between the descent direction p 𝑡 and the direction of the gradient cos(𝜃 𝑡 ) =

p ⊤ 𝑡 ∇ L(𝑤 (𝑡) )
||∇ L(𝑤 (𝑡) )||×||p𝑡|| ; the following series is convergent

∑ 𝑡 cos 2 (𝜃 𝑡 )||∇ L(𝑤 (𝑡) )|| 2
Various improvements to the gradient approach have recently been developed. The group of accelerated gradient methods is made up of these approaches, which the most popular ones are:

• Classical Momentum [Polyak, 1964] Instead of using the true gradient this technique accumulates the gradients with the decaying parameter 𝜇 into momentum vector:

𝑔 𝑡 = ∇ L(𝑤 (𝑡-1) )
(2.11)

𝑚 𝑡 = 𝜇𝑚 𝑡-1 + 𝑔 𝑡 (2.12) 𝑤 (𝑡) = 𝑤 (𝑡-1) -𝜂𝑚 𝑡 (2.13)
• Nesterov's accelerated gradient [Nesterov, 1983] By plugging (2.12) into (2.13) we get that 𝑤 (𝑡) = 𝑤 (𝑡-1) -𝜂𝜇𝑚 𝑡-1 -𝜂𝑔 𝑡 . Nesterov momentum suggests the computation of the gradient immediately at the point 𝑤 (𝑡-1) -𝜂𝜇𝑚 𝑡-1 .

𝑔 𝑡 = ∇ L(𝑤 (𝑡-1) -𝜂𝜇𝑚 𝑡-1 )

𝑚 𝑡 = 𝜇𝑚 𝑡-1 + 𝑔 𝑡 𝑤 (𝑡) = 𝑤 (𝑡-1) -𝜂𝑚 𝑡 (2.14)
• AdaGrad [START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF] Another modified gradient descent algorithm with per-parameter learning rate is adaptive gradient algorithm (AdaGrad). Informally, this strategy raises the learning rate for sparser parameters while decreasing the rate for less sparse ones.

In situations when data is sparse and sparse parameters are more useful, like in Natural language processing and image recognition applications, this technique often outperforms ordinary gradient descent in terms of convergence.

𝑔 𝑡 = ∇ L(𝑤 (𝑡-1) )

𝑤 (𝑡) = 𝑤 (𝑡-1) - 𝜂 ‖𝑔 𝑡 ‖ 𝑔 𝑡 (2.15)
• RMSProp [Hinton, 2020] Root Mean Square Propagation (RMSProp) is another method in which the learning rate is adjusted for each parameter. The aim is to divide a weight's learning rate by a running average of recent gradient magnitudes for that weight. As a result, the running average is first calculated in terms of the square root of the means.

𝑔 𝑡 = ∇ L(𝑤 (𝑡-1) )

𝑛 𝑡 = 𝜈𝑛 𝑡-1 + (1 -𝜈)𝑔 ⊤
𝑡 𝑔 𝑡 where, 𝜈 is the forgetting factor. And the parameters are updated as,

𝑤 (𝑡) = 𝑤 (𝑡-1) - 𝜂 √ 𝑛 𝑡 + 𝜖 𝑔 𝑡 (2.16)
Here 𝜖 is a small scalar in the order of 10 -8 used to prevent division by 0.

• Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] The RMSProp optimizer has been updated with Adam (for Adaptive Moment Estimation). Running averages of both the gradients and the second moments of the gradients are used in this optimization process: -1) )

𝑔 𝑡 = ∇ L(𝑤 (𝑡
𝑚 𝑡 = 𝜇𝑚 𝑡-1 + (1 -𝜇)𝑔 𝑡 m𝑡 = 𝑚 𝑡 1 -𝜇 𝑛 𝑡 = 𝜈𝑛 𝑡-1 + (1 -𝜈)𝑔 ⊤ 𝑡 𝑔 𝑡 n𝑡 = 𝑛 𝑡 1 -𝜈 𝑤 (𝑡) = 𝑤 (𝑡-1) - 𝜂 √ n𝑡 + 𝜖 m𝑡 (2.17)
where 𝜇 and 𝜈 are the forgetting factors for gradients and second moments of gradients, respectively.

Classification

In this section, we present SVMs in the case of binary classification and neural networks. Both classifiers are undoubtedly the most popular classification algorithms in the field of Machine Learning, mainly due to the theoretical justifications for SVMs, and, their wide applications in different problems for neural networks. In Section 2.4.1, we begin by presenting the notions of hyperplane separator of a set of examples and kernels, then the principle of support vector machines [Vapnik, 2000], which allows one to find a separating hyperplane thanks to a method which can be interpreted as a minimization of the structural risk presented in the previous section. We then describe neural networks in Section 2.4.2.

Support Vector machines

Consider an input space 𝒳 ⊂ R 𝑑 ; a linear classifier is a function from R 𝑑 into {-1, 1} of the form 𝑓 (𝑥) = sgn(⟨𝑤, 𝑥⟩ + 𝑤 0 ) with 𝑤 ∈ R 𝑑 and 𝑤 0 ∈ R, and sgn(𝑡) = 1 if 𝑡 > 0, -1 otherwise. We notice that the hyperplane ℎ(𝑥) = ⟨𝑤, 𝑥⟩ + 𝑤 0 divides 𝒳 into two subspaces which are the sets {𝑥 ∈ 𝒳 |⟨𝑤, 𝑥⟩ + 𝑤 0 < 0} and {𝑥 ∈ 𝒳 |⟨𝑤, 𝑥⟩ + 𝑤 0 > 0}.

Let us now consider a classifier ℎ(𝑥) = ⟨𝑤, 𝑥⟩ + 𝑤 0 that correctly classifies all the examples of 𝑆. In this case, there exists then a scalar such that the examples (𝑥 𝑖 , 𝑦 𝑖 ) closest to the hyperplane satisfy |⟨𝑤, 𝑥⟩ + 𝑤 0 | =1. Now consider two observations 𝑥 1 and 𝑥 2 of different classes, such that ⟨𝑤, 𝑥 1 ⟩ + 𝑤 0 = +1 and ⟨𝑤, 𝑥 2 ⟩ + 𝑤 0 = -1. The margin is defined as the distance between these two points, measured perpendicular to the hyperplane. In other words, the margin is

⟨ 𝑤 |𝑤 0 | , (𝑥 1 -𝑥 2 )⟩ = 2
‖𝑤‖ . This notion of margin is illustrated in the figure 234.

Hard margin SVM We have seen previously that provided that the examples closest to the hyperplane satisfy |⟨𝑤, 𝑥⟩ + 𝑤 0 | = 1, then the margin is related to ‖𝑤‖ . This result therefore suggests minimizing the norm of 𝑤 in order to determine a maximum margin hyperplane. Noting that the constraints |⟨𝑤, 𝑥⟩ + 𝑤 0 | = 1 can be written 𝑦(⟨𝑤, 𝑥⟩ + 𝑤 0 ) = 1 for the examples close to the hyperplane, this amounts to solving the following optimization problem:

min 𝑤∈R 𝑑 ,𝑤 0 ∈R 1 2 ‖𝑤‖ 2 s.c. ∀𝑖, 𝑦 𝑖 (⟨𝑤, 𝑥⟩ + 𝑤 0 ) ≥ 1
We recognize a quadratic optimization problem with linear constraints. In general we will not try to solve this problem directly, but rather we will be interested in the dual problem [START_REF] Ferris | Interior-point methods for massive support vector machines[END_REF]:

max (𝛼 1 ,...,𝛼𝑚)∈R 𝑚 𝑚 ∑ 𝑖=1 𝛼 𝑖 - 1 2 𝑚 ∑ 𝑖=1 𝑚 ∑ 𝑗=1 𝑦 𝑖 𝑦 𝑗 𝛼 𝑖 𝛼 𝑗 𝑥 ⊤ 𝑖 𝑥 𝑗 s.c. 𝑚 ∑ 𝑖=1 𝑦 𝑖 𝛼 𝑖 = 0 ∀𝑖, 𝛼 𝑖 ≥ 0
This formulation has the advantage of expressing the vector 𝑏 solution of the optimization problem initial in the following form:

𝑤 = 𝑚 ∑ 𝑖=1 𝑦 𝑖 𝛼 𝑖 𝑥 𝑖
where (𝛼 1 , ..., 𝛼 𝑚 ) is an optimal solution of the dual problem. Moreover, it can be shown that 𝛼 𝑖 > 0 if and only if 𝑦 𝑖 (⟨𝑤, 𝑥⟩ + 𝑤 0 ) = 1. Thus, the normal vector of the optimal hyperplane can be decomposed as a linear combination of the input vectors which are at the minimum distance from this hyperplane. These input vectors are called the support vectors. Thus, the maximum-margin hyperplane has the property of only depending on a subset of examples. These examples lie exactly on the margin and are called the support vectors. The other examples could be anywhere outside the margin without changing the solution. We would therefore find the same solution if the training set 𝑆 contained only these support vectors.

Theoretical justification Support vector machines have been used successfully in many fields, but it is not immediately clear how good they perform from a theoretical point of view. [Vapnik, 2000] provides an explanation by linking the notion of separation margin to that of VC dimension. In particular, he proves the following theorem:

Theorem 3 ( [Vapnik, 2000]) Let 𝑤 ∈ R 𝑑 be such that ‖𝑤‖ = 1, 𝑐 𝑤,𝑤 0 ,𝛾 the classifier defined by the following relation:

𝑐 𝑤,𝑤 0 ,𝛾 (𝑥) = 1 if ⟨𝑤, 𝑥⟩ + 𝑤 0 ≥ 𝛾, and 𝑐 𝑤,𝑤 0 ,𝛾 (𝑥) = -1 if ⟨𝑤, 𝑥⟩ + 𝑤 0 ≤ -𝛾.
This classifier is called a 𝛾-margined separator hyperplane. In cases where 𝑥 does not match any of the two conditions, we consider it to be ignored. Then, if the space of observations 𝒳 is included in a ball of radius 𝐵, the dimension VC of the set of margin separator hyperplanes 𝛾 over 𝒳 is less than ⌈𝑅 2 /𝛾 2 ⌉ + 1, where ⌈𝑡⌉ is the upper integer part of 𝑡.

The separation margin is therefore related to the VC dimension: the more one separating hyperplane achieves a wide separation margin on a training set 𝑆, the more it can be considered as part of a set of low-dimensional VC functions. However, we have seen that the principle of structural risk minimization suggests favoring low-dimensional VC binary classifiers. Thus by maximizing the margin, support vector machines minimize the VC dimension and can therefore be seen as implementations of the structural risk minimization principle.

Soft Margin SVM The hard-margin SVM presented in the previous section can only apply when 𝑆 is linearly separable. In practice this is rarely the case, in particular because of noise problems (𝑆 contains examples whose observed class is not the true class), or quite simply because the problem is not linearly separable. An example of a nonlinearly separable classification problem is given in figure 2345. To be able to use SVM on such data, it must therefore be made capable of accepting the misclassification of certain examples. A simple way to allow classification errors is to relax the constraints on the margin by introducing slack variables. To an example of 𝑆 is associated a slack variable, which allows us to associate a cost each time the corresponding example violates the constraint on the margin. The new SVM thus defined is then said to soft margin. The new objective of the soft-margin SVM is therefore twofold: to maximize the margin and to minimize the number of examples violating the constraint on the margin. In other words, we will minimize the norm of 𝑤 and the sum of the costs associated with the spring variables. The new optimization problem is written:

min 𝑤∈R 𝑑 ,𝑤 0 ∈R 1 2 ‖𝑤‖ 2 + 𝐶 𝑚 ∑ 𝑖=1 𝜉 𝑖 u.c. ∀𝑖, 𝑦 𝑖 (𝑤 ⊤ 𝑥 𝑖 + 𝑤 0 ) ≥ 1 -𝜉 𝑖 ∀𝑖, 𝜉 𝑖 ≥ 0
where the 𝜉 𝑖 are the slack variables, 𝐶 > 0 a real to choose from. When we have 𝜉 𝑖 > 0, then the corresponding constraint is violated. The cost associated with this violation is worth 𝐶𝜉 𝑖 , which we can compensate by decreasing the norm of 𝑤. If 𝐶 is large, then the slightest constraint violation will have a large cost, and the solution will therefore favor hyperplanes with a small margin but with few margin constraint violations. Conversely, a low 𝐶 will allow more classification errors and will favor large-margin hyperplanes. We thus see that 𝐶 allows to parameterize the compromise between the maximization of the margin and the violations of the constraints on the margin. In practice, the 𝐶 coefficient will be chosen by standard model selection methods such as cross-validation.

Hinge loss and regularization

We will now interpret soft-margin SVMs from the perspective of regularization. An optimization problem is said to be regularized when the optimized function is the sum of two errors: the cost function that really interests us (the classification error for example), and a regularization term. This regularization term is used either to stabilize the solution (i.e. to ensure that it does not vary too much), or to incorporate a priori knowledge of the problem (i.e. to introduce a bias).

Many learning algorithms can be interpreted as regularized problems. We will see that this is particularly the case for soft-margin SVMs.

For this we define the loss function ℓ(𝑓 (𝑥), 𝑦) = max(0, 1 -𝑦ℎ(𝑥)), called Hinge loss. This function is shown in figure 23456. We can now rewrite the previous optimization problem without the constraints:

min 𝑤∈R 𝑑 ,𝑤 0 ∈R 1 2 ‖𝑤‖ 2 + 𝐶 𝑚 ∑ 𝑖=1 max ( 0, 1 -𝑦 𝑖 (𝑤 ⊤ 𝑥 𝑖 + 𝑤 0 ) )
If we divide the loss function by the constant 𝐶, we recognize a regularization term and the empirical error:

L(𝑤, 𝑤 0 ) = 𝑚 ∑ 𝑖=1 max ( 0, 1 -𝑦 𝑖 (𝑤 ⊤ 𝑥 𝑖 + 𝑤 0 ) ) ⏟ ⏞ empirical error + 1 2𝐶 ‖𝑤‖ 2 ⏟ ⏞ regularization term
Thus the soft-margin SVM can be seen as a regularized learning problem, where the regularization function introduces a bias towards large-margin hyperplanes. Note that with this regularized learning interpretation, the empirical error is not the 0/1 error that initially interested us but the surrogate Hinge loss. In [START_REF] Bartlett | Rademacher and gaussian complexities: Risk bounds and structural results[END_REF] it is shown that the minimizer of any surrogate loss of the 0/1 loss, in which the associated instantaneous loss ℓ : (𝑦, ℎ(𝑥)) ↦ → ℓ(𝑦, ℎ(𝑥)) is continuous and passes through 1 when 𝑦ℎ(𝑥) = 0, is likewise the minimizer of the 0/1 classification error.

Neural network approaches

Artificial neural networks, are perhaps the most popular learning systems nowadays whose design were originally schematically inspired by the functioning of biological neurons discovered by [Ramon y [START_REF] Ramon Y Cajal | Les nouvelles idées sur la structure du système nerveux chez l'homme et chez les vertébrés[END_REF].

Dendrites are the connections through which the neuron receives impulses, whereas an axon is the link through which the neuron transmits the impulse. Each neuron has one axon. Dendrites and axons have a complicated branching structure. A synapse is a connection between the axon and the dendrite. A neuron's primary purpose is to carry information from the dendrites to the axon. Distinct dendritic signals, on the other hand, can have different effects on the signal in the axon. If the overall impulse surpasses a specific threshold, the neuron will send out a signal. The neuron will not respond to the impulse if this happens, and no signal will be sent to the axon.

From this discovery, the concept of artificial neural networks was proposed in [START_REF] Mcculloch | A logical calculus of the ideas immanent in nervous activity[END_REF], where the two researchers presented their theory that the activation of neurons is the basic unit of brain activity and described the formal neuron which mimics the functioning of a biological neuron as shown in Figure 234567).

For a given input 𝑥 = (𝑥 1 , . . . , 𝑥 𝑑 ) ⊤ ∈ R 𝑑 , each characteristic 𝑥 𝑗 is supposed to be a real valued signal which arrives (from a dentrite) to a computing unit (i.e. the nucleus). This unit estimates a weighted sum of the all characteristics:

∑ 𝑑 𝑗=1 𝑤 𝑗 𝑥 𝑗 and compares the sum to a bias 𝑤 0 . The output of the neuron is then computed using an activation function (see below) over a linear combination of the input: 𝑎 : 𝑥 ↦ → 𝑎(𝑤 ⊤ 𝑥 + 𝑤 0 ) [Rosenblatt, 1957] invented Perceptron which is the oldest machine learning algorithm, designed to perform complex pattern recognition tasks. It is this algorithm that will later allow machines to learn to recognize objects in images. The activation function of Perceptron is the identity function and the weights of the model are learned per example at each time that the model makes an error on the class of an example in input. The weights are updated using a stochastic version of the gradient algorithm by minimising the distance of the misclassified example to the current hyperplane.

At that time, neural networks were limited by technical resources. For example, computers were not powerful enough to process the data needed to run neural networks. This is the reason why research in the field of Neural Networks has remained dormant for many years. It took until the early 2010s, with the rise of Big Data and massively parallel processing, for Data Scientists to have the data and computing power needed to run complex neural networks. In 2012, during a competition organized by ImageNet, a Neural Network managed for the first time to surpass a human in image recognition. This is why this technology is again at the heart of the concerns of scientists. Nowadays, artificial neural networks are constantly improving and evolving day by day.

Activation functions

The term activation function comes from the biological equivalent "activation potential", the stimulation threshold which, once reached, triggers a neuron response. The activation function is often a nonlinear function. An example of an activation function is the Heaviside function, which always returns 1 if the input signal is positive, or 0 if it is negative.

The main activation functions are the following.

• ReLU: ReLU has the following formula 𝑎(𝑧) = 𝑚𝑎𝑥(0, 𝑧) and implements a simple threshold transition at zero point. The use of ReLU significantly increases the speed of training, but ReLU has one significant drawback -neurons could "die" during the training. It means that they could come into a state where the output will always be 0.

• Leaky ReLU:Leaky ReLU is one of the attempts to solve the problem of dead neurons in ReLU described above. The usual ReLU gives a zero on the interval 𝑧 < 0, while Leaky ReLU (LReLU) has a small negative value on this interval. That is, the function for LReLU has the form 𝑎(𝑧) = 𝛽𝑧 for 𝑧 < 0 and 𝑎(𝑧) = 𝑧 for 𝑧 ≥ 0, where 𝛽 is a small constant.

• Randomized ReLU: For a randomized ReLU (RReLU), the angular coefficient on the negative interval is randomly generated from the specified interval during training, and remains constant during testing. It also is noticed [START_REF] Xu | Empirical evaluation of rectified activations in convolutional network[END_REF] that RReLU allowed to reduce the overfitting due to their element of randomness.

These activation functions are shown below. Other classicical activation function with smooth derivatives are:

• Sigmoid: The sigmoid is expressed by the following formula 𝜎(𝑧) = 1 (1+𝑒 -𝑧 ) . This function takes an arbitrary real number at the input, and gives a real number in the range from 0 to 1 at the output. In particular, large negative numbers turn into zero, and large positive ones turn into one.

• Softmax: This is a generalization of the sigmoid function for the multidimensional case. The function 𝜎(𝑧 𝑖 ) = 𝑒 𝑧 𝑖 ∑ 𝐾 𝑘=1 𝑒 𝑧 𝑘 converts a real number 𝑧 𝑖 (element of the vector 𝑧 with dimension 𝐾) into a real number from the interval [0, 1] and the resulting sum of the coordinates of the vector 𝑧 is 1.

• Hyperbolic Tangent: The hyperbolic tangent 𝑡𝑎𝑛ℎ(𝑧) takes an arbitrary real number at the input, and gives a real number in the range from -1 to 1 at the output.

Multi-Layer Perceptron

The multilayer perceptron (MLP) is a sort of artificial neural network composed of many layers in which information flows directly from the input layer to the output layer. Each layer has a different amount of neurons, with the neurons in the last layer (known as "output") serving as the entire system's outputs. Layers between the input and the output layers are called hidden layers.

The two types of neural networks most studied in the literature are recurrent networks, where there are loops between the different hidden layers and also between units of these layers, and forward propagation networks (or feed forward ) without a loop, which we consider in the following. They are usually organized into layers of neural units each similar to the one described previously.

In feed forward neural network, the information is propagated as follows: Given an input example 𝑥 and its desired output 𝑦. The signal is propagated forward in the layers of the neural network:

• 𝑥 (𝑛-1) 𝑘 ↦ → 𝑥 (𝑛)
𝑗 , where 𝑛 is the layer number.

• Forward propagation is calculated using the activation function 𝑎, the aggregation function ℎ (often a dot product between the weights and the inputs of the neuron) and synaptic weights 𝑤 𝑗𝑘 between neuron 𝑥 (𝑛-1) 𝑘 and the neuron 𝑥

(𝑛) 𝑗 . 𝑥 (𝑛) 𝑗 = 𝑎 (𝑛) (ℎ (𝑛) 𝑗 ) = 𝑎 (𝑛) ( ∑ 𝑘 𝑤 (𝑛) 𝑗𝑘 𝑥 (𝑛-1) 𝑘 + 𝑤 𝑗0 )
When forward propagation is complete, the output is ŷ. We then calculate the error between the output given by the network ŷ and the desired output vector 𝑦. :

Loss functions The loss function can be calculated in a variety of ways, depending on the task formulation. For example, if the task is regression, the most relevant losses are Mean squared error (MSE) or Mean absolute error (MAE):

ℓ 𝑀 𝑆𝐸 (𝑦, ŷ) = 𝐾 ∑ 𝑘=1 (𝑦 𝑘 -ŷ𝑘 ) 2 ℓ 𝑀 𝐴𝐸 (𝑦, ŷ) = 𝐾 ∑ 𝑘=1 |𝑦 𝑘 -ŷ𝑘 |
If the task is a classification task, the most popular loss is the cross-entropy error

ℓ 𝐶𝐸 (𝑦, ŷ) = - 𝐾 ∑ 𝑘=1 𝑦 𝑘 log(ŷ 𝑘 )
where

𝑦 𝑘 ∈ {0, 1} and ŷ𝑘 = 1 1+𝑒 -ℎ (𝑁 ) 𝑘
is the predicted output using a sigmoid activation.

Back-propagation of the gradient The weights of a neural network are updated by minimizing the loss layer per layer, from the output to the input layer, throughout training. This sequential update of the weights is called the back-propagation of the gradient.

The gradient descent algorithm is in general used in this update.

𝑤 (𝑛) 𝑗𝑘 = 𝑤 (𝑛) 𝑗𝑘 -𝜂 𝜕ℓ(𝑦, ŷ) 𝜕𝑤 (𝑛) 𝑗𝑘
The chain rule is used to calculate the derivative of a loss with regard to a weight:

𝜕ℓ(𝑦, ŷ) 𝜕𝑤 (𝑛) 𝑗𝑘 = 𝜕ℓ(𝑦, ŷ) 𝜕ℎ (𝑛) 𝑗 𝜕ℎ (𝑛) 𝑗 𝜕𝑤 (𝑛) 𝑗𝑘 2.

Ranking

The task of classification described above is arguably one of the most studied task in the literature. However, there are numerous situations where ranking the observations rather than assigning them to a class is more appropriate. The most typical example in information retrieval is search engines such, which give the user with a list of documents sorted by relevance, rather than a collection of papers all deemed relevant and presented in no particular order. Another example is recommendation systems that we will present in depth in the next chapter. The goal of these systems is to propose items that are likely to interest a user. Sorting items in order of relevance seems more acceptable from a recommendation standpoint than predicting a score or class for each item.

The task of ordering a set of objects with respect to a fixed information request is called instance ranking (or ranking in short). More precisely, a ranking problem is defined by an ordering relation on the space of instances 𝒳 , allowing to order 𝑥 1 and 𝑥 2 for any pair of instances (𝑥 1 , 𝑥 2 ) in 𝒳 .

A simpler and more natural way to model the order relation is to use a function 𝑓 : 𝒳 → R which assigns an actual score to any example 𝑥 ∈ 𝒳 . The order between the instances is then deduced from the comparison of the values of 𝑓 . So 𝑓 (𝑥

1 ) > 𝑓 (𝑥 2 ) means that 𝑥 1 is ranked above 𝑥 2 .
By modeling the order relation in this way, we formulate the ranking of examples as the learning of a score function, as in classification. On the other hand, let us underline an important difference: in classification, the learned functions directly give the expected predictions. In ranking, learned functions return scores whose absolute values are not important per se. Indeed, these values are only used to compare the examples with each other. It is therefore the relative values of the scores that are important.

Ordering induced by scores

Given a set of examples 𝑆 = (𝑥 1 , ..., 𝑥 𝑚 ), we assume that the desired ordering is induced by scores 𝑌 = (𝑦 1 , ..., 𝑦 𝑚 ). These scores induce a strict partial order on the set of inputs 𝑆: 𝑥 𝑖 is ordered above 𝑥 𝑗 if 𝑦 𝑖 > 𝑦 𝑗 . This is also the case in collaborative filtering (CF), where each user can attribute to each item a value expressing his or her preferences on a rating scale: 𝑦 = 5 if (s)he liked it a lot, and, 𝑦 = 1 the reverse. In this case, items with different scores can be ordered relative to each other.

We assume that a part of the examples (𝑥 𝑖 , 𝑦 𝑖 ) is known and available for training. The purpose of instance ordering is to learn a score function which must retrieve a desired order from the training examples. We therefore find a task similar to classification, where the goal is to learn a function from a few examples in order to find the outputs for new observations. On the other hand, our goal is no longer to predict the scores of the unobserved examples, but to predict the order between the instances. To take this difference into account, we must adapt the notions of learning error and error in generalization to the framework of ranking.

Ranking error on crucial pairs

A ranking loss is a function of the form ℒ 𝑟 : R 𝑚 × R 𝑚 → R + . It takes two vectors of scores as input: the vector of desired scores, and the vector of predicted scores. It returns a positive real which measures the error between the vector of desired scores and the vector of predictions. Note the difference with the error functions used in classification, which compares the value of a desired output with its prediction. In ranking, the value of an output does not matter, it is its relative value in relation to the other outputs that matters. This is why the error functions consider score vectors and not individual scores.

We call crucial pairs the pairs of observations (𝑥 𝑖 , 𝑥 𝑗 ) such that 𝑦 𝑖 > 𝑦 𝑗 . We expect a prediction function 𝑓 to make few prediction errors on crucial pairs, ie it satisfies 𝑓 (𝑥 𝑖 ) > 𝑓 (𝑥 𝑗 ). This leads us to define the ranking loss on crucial pairs:

ℒ 𝑟 (𝑓 (𝑠), 𝑌 ) = 1 ∑ 𝑖,𝑗 1 𝑦 𝑖 >𝑦 𝑗 ∑ 𝑦 𝑖 >𝑦 𝑗 1 𝑓 (𝑥 𝑖 )≤𝑓 (𝑥 𝑗 ) (2.18)
where 𝑓 (𝑠) = (𝑓 (𝑥 1 ), ..., 𝑓 (𝑥 𝑚 )) and 𝑌 = (𝑦 1 , ..., 𝑦 𝑚 ). The denominator is simply the number of crucial pairs that can be generated from the score vector 𝑌 . At the numerator, we recognize the number of crucial pairs on which the order predicted by 𝑓 is not the desired order. The ranking loss on the crucial pairs, which serves as our empirical error, is therefore simply the proportion of crucial pairs incorrectly predicted by 𝑓 .

Other ranking approaches

There are two other Learning-to-Rank approaches which are pointwise and listwise ranking techniques [Liu, 2009].

In Pointwise approaches, ranking is formulated as a regression problem, in which the rank value of each example is estimated as an absolute quantity to be found. In the case where relevance judgments are given as pairwise preferences (rather than relevance degrees), it is usually not straightforward to apply these algorithms for learning. Moreover, pointwise techniques do not consider the inter dependency among examples, so that the position of examples in the final ranked list is missing in the regression-like loss functions used for learning.

On the other hand, listwise approaches take the entire ranked list of examples as a training instance. As a direct consequence, these approaches are able to consider the position of examples in the output ranked list at the training stage. Listwise techniques aim to directly optimize a ranking measure, so they generally face a complex optimization problem dealing with non-convex, non-differentiable and discontinuous functions.

In terms of models, perhaps the first ranking based model is RankProp, originally proposed by [START_REF] Caruana | Using the future to "sort out" the present: Rankprop and multitask learning for medical risk evaluation[END_REF]. RankProp is a pointwise approach that alternates between two phases of learning the desired real outputs by minimizing a Mean Squared Error (MSE) objective, and a modification of the desired values themselves to reflect the current ranking given by the net. Later on [START_REF] Burges | Learning to rank using gradient descent[END_REF] proposed RankNet, a pairwise approach, that learns a preference function by minimizing a cross entropy cost over the pairs of relevant and irrelevant examples. SortNet proposed in [START_REF] Rigutini | Sortnet: Learning to rank by a neural preference function[END_REF]] also learns a preference function by minimizing a ranking loss over the pairs of examples that are selected iteratively with the overall aim of maximizing the quality of the ranking. A complete survey on the complexity of the Google PageRank problem [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF]], a core of many modern algorithms, is given in [START_REF] Anikin | Efficient numerical methods to solve sparse linear equations with application to pagerank[END_REF].

Conclusion

In this chapter we have provided a brief overview of supervised learning by focusing on classification and ranking tasks. The two main other frameworks that are not covered are unsupservised learning [START_REF] Hinton | Unsupervised Learning: Foundations of Neural Computation[END_REF] and semi-supervised learning. In unsupervised learning, the aim is to find similar groups from a set of examples for which we do not have desired outputs. Unsupservised learning approaches exploit the structure of data to find these clusters and have been applied in many applications, such as Information Retrieval [START_REF] Pessiot | Improving document clustering in a learned concept space[END_REF], or image segmentation [START_REF] Xia | W-net: A deep model for fully unsupervised image segmentation[END_REF]. Semi-supervised learning, on the other hand, tries to take use of both label information in a small collection of labeled data and data structure in a large quantity of unlabeled data for learning [START_REF] Chapelle | [END_REF].

The presentation given in this chapter aims to pave the way for the introduction of recommender systems that are the main application task that we considered in this thesis.

Chapter 3 Recommender Systems

Introduction

With the development of e-commerce, Internet users are offered a growing choice of products and services online. To guide them, most sites use recommendation systems. Their goal is to generate personalized recommendations, ie to determine for each user the products or articles most likely to interest him. To achieve this, the most effective implementations to date use the preferences of other users to generate these recommendations: this is the principle of collaborative filtering. Collaborative filtering is particularly suitable for recommending cultural products such as films, books or music, and is used successfully by commercial online recommendation systems such as Amazon.com or CDnow.com. Collaborative filtering techniques have in particular given rise to a large number of recommendation systems on the Internet, for example for films (MovieLens1 , ymdb.com, ...), or for web pages (Del.icio.us2 ) through bookmark pooling [START_REF] Pessiot | Learning to rank for collaborative filtering[END_REF]. They are also the basis of the personalized proposals for items to buy that are made on commercial sites such as Amazon.com or CDNow.com. The development of highperformance collaborative filtering systems therefore presents significant economic challenges. Different approaches have been proposed for collaborative filtering; the most popular ones rely on matrix factorization which intends to factorize the sparse matrix of users and items where each cell of the matrix is either a note or a binary value corresponding for example to a click, into the multiplication of two matrices each corresponding to a latent representation of respectively users and items. The main challenges of matrix factorization approaches for recommender systems are how to tackle the great sparsity of the original matrix and how to make the models scalable?

To address these points, ranking models for recommendation have attracted many interest in both the industry and the academic research community in recent years. Given a system (set of users, customers etc.), the goal here is to provide a ranking of objects (items, products, adverts etc.), based on the information about the interaction of these objects with the system and their individual characteristics.

Common examples of applications include the recommendation of movies (Netflix, Amazon Prime Video), music (Pandora), videos (Youtube), news content (Outbrain) or advertisements (Google).

Feedback provided by the system and exploited to learn ranking scores can be explicit, presented mostly by ratings; or implicit that include clicks, browsing over an item or listening to a song. Such implicit feedback is readily available in abundance but is more challenging to take into account as it does not clearly translate the preference of a user for an item. The idea here is that even a clicked item does not necessarily express the preference of a user for that item, it has much more value than a set of unclicked items for which no action has been made. In most of these approaches, the objective is to rank the clicked item higher than the unclicked ones by finding a suitable representation of users and items in a way that for each user the ordering of the clicked items over unclicked ones is respected by dot product in the joint learned space. One common characteristic of publicly available collections for recommendation systems is the huge unbalance between positive (click) and negative feedback (no-click) in the set of items displayed to the users, making the design of an efficient online RS extremely challenging. Some works propose to weight the impact of positive and negative feedback directly in the objective function [START_REF] Pan | One-class collaborative filtering[END_REF] to improve the quality. Another approach is to sample the data over a predefined buffer before learning [START_REF] Liu | Large-scale recommender system with compact latent factor model[END_REF], but these approaches do not model the shift over the distribution of positive and negative items, and the system's performance on new test data may be affected.

In this chapter, we will review main approaches proposed for recommender systems by focusing on learning-to-rank setting for this task that have been developed for the off-line case. This problem differs from the problem of personalized recommendation where the goal is to perform the recommendation online. The process of the latter is as follows: a user comes into the systems and is displayed some ads based on his or her previous interactions with the systems. At this time, we assume that the user is starting a new session. Then, he or she starts to interact with the displayed ads. A traditional off-line approach will have to wait for the end of the session in order to learn potential new recommendations for the next visit of this user. However, in the on-line setting, the aim is to develop a model which can adapt the recommendation within the same session. Therefore, the parameters of the model will be updated online. Providing high-quality online ranking is a challenging task for several reasons:

• It is strongly time-dependent: the set of relevant items for each user changes over time and the relevance of the items depends on the preferences of a particular user at a specific instant of time.

• The number of positive feedback, for instance clicks, are very rare (i.e. the data are sparse).

• It is difficult to provide recommendations for new users and/or new items (cold-start).

We will come over these points on the next chapters. In the reminder, we will first present in Section 3.2 matrix factorization and ranking-based models for recommender systems, then in Section 3.3 we will describe classical measures that have been used to evaluate these systems.

Different approaches

Two main approaches have been proposed to solve the problem of ranking. The first one, referred to as Content-Based recommendation techniques (CBF) [START_REF] Pazzani | Content-based recommendation systems[END_REF]] make use of existing contextual information about the items (e.g. textual description, meta-data) for recommendation. The second approach, referred to as collaborative filtering (CF) and undoubtedly the most popular one [START_REF] Su | A survey of collaborative filtering techniques[END_REF], relies on the past interactions and recommends items to users based on the feedback provided by similar other users. In the followings, we are interested in predicting if a user will prefer an item over another, rather than predicting a real-value (such as a rating for instance). This task is tackled by ranking based approaches where the goal is to learn a list of items ordered according to their degree of relevance for a given user.

Matrix Factorization

CF methods operate with a huge matrix of users-objects (each row corresponds to a user, and each column is an item). To solve this problem, many methods use a matrix decomposition [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF], which shows good results. Let's give some mathematics key-points regarding this approach. Suppose 𝒰 -the set of all users, ℐ -the set of items and 𝑅 is a matrix of size |ℐ| × |𝒰| which contains all ratings that users have given to the items. Assume, that we consider 𝐾 latent variables, then the goal is to find two matrices 𝑃 and 𝑄 such that their product approximates the matrix 𝑅:

𝑅 ≈ R = 𝑃 × 𝑄 𝑇 , (3.1)
where 𝑃 is a |𝒰|×|𝐾| matrix, and 𝑄 is a |𝐾|×|ℐ| matrix. As a result, the factorization gives us a low dimensional numerical representation of users and items. In the case of the stated problem, we want to build the regression model r𝑢,𝑖 , that predicts the missing values in the matrix 𝑅 for any arbitrary pair (𝑢, 𝑖) ∈ |𝒰| × |ℐ| :

r𝑢,𝑖 = 𝑝 𝑇 𝑢 𝑞 𝑖 = 𝐾 ∑ 𝑘=1 𝑝 𝑢,𝑘 𝑞 𝑘,𝑖 , (3.2)
where 𝑝 𝑇 𝑢 is the 𝑢 -𝑡ℎ row of 𝑃 and 𝑞 𝑖 is the 𝑖 -𝑡ℎ column of 𝑄. The error function between the estimated and real ratings can be calculated as

ℒ(𝑃, 𝑄, 𝑅) = ∑ (𝑢,𝑖)∈Θ (𝑟 𝑢,𝑖 -r𝑢,𝑖 ) 2 + 𝜆 ( ∑ 𝑢∈𝒰 ‖𝑝 𝑢 ‖ 2 + ∑ 𝑖∈ℐ ‖𝑞 𝑖 ‖ 2 ) , (3.3)
where Θ is the set of all user-item pairs, that have marks in matrix 𝑅, 𝒰 is the full set of users and ℐ is the full set of items. The second term of the equation is the regularization part which allow to avoid overfitting. We also notice, that a non-convex regulrization in Eq. 3.3 may improve the quality of factorization [START_REF] Pogodin | Efficient rank minimization to tighten semidefinite programming for unconstrained binary quadratic optimization[END_REF], Krechetov et al., 2018]; however, computations often become harder.

The regression approach rely on the idea of providing the predictions that will as close as possible from the true score, so the problem leads to the prediction of ratings for each single pair user-item. It is important to note that the prediction of ratings is only an intermediate step towards recommendation, and that other directions are possible. In particular, given the typical use of recommender systems where the system presents each user with the top 𝑁 items without showing the associated ratings, we believe that ordering the items correctly is more important than correctly predicting their ratings. Although these two objectives are close, they are not equivalent from the point of view of the recommendation. Indeed, any method that correctly predicts all ratings will also correctly order all items. On the other hand, with equal performances in terms of rating prediction, two methods can have different performances in terms of order prediction. This phenomenon is illustrated in Figure 3-1.

Neural Language Models

Ranking-based approaches for RS, like matrix factorization techniques, rely on the learning of latent representations for users and items. The main difference is that these techniques primarily use neural networks for representation learning and follow the basic idea of traditional Natural Language Processing (NLP) approaches, which tackled the difficult task of finding the best representations of words to reflect their similarities and differences.

Using the skip-gram training method (SG, implemented in the word2vec software package3 ) encouraging results were obtained by encoding words as embedding vectors [Mikolov et al., 2013a[START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]. Similarly, [START_REF] Levy | Neural word embedding as implicit matrix factorization[END_REF] proposed new opportunities to extend the word representation learning [Mikolov et al., 2013a[START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF], Shazeer et al., 2016] to characterise more complicated piece of information. Indeed, the authors of this paper showed the equivalence of the SG model with negative sampling and implicit factorization of a point-wise mutual information (PMI) matrix. Furthermore, they demonstrated that word embedding may be used to a variety of data kinds (not only words) if a suitable context matrix can be created.

Since then, this idea has been successfully applied to recommendation systems, where different approaches attempted to learn representations of items and users. In [START_REF] Liang | Factorization meets the item embedding: Regularizing matrix factorization with item co-occurrence[END_REF], the authors proposed a model that relies on the intuitive idea that pairs of items scored the same way by different users are similar. The approach reduces to finding both the latent representations of users and items, with the traditional Matrix Factorization (MF) approach, and simultaneously learning item embeddings using a co-occurrence Shifted Positive Pointwise Mutual Information (SPPMI) matrix defined by items and their context.

In [START_REF] Grbovic | E-commerce in your inbox: Product recommendations at scale[END_REF] the authors proposed Prod2Vec, which embeds items using the word2vec technique, by modelling the sequence of user purchases as a sentence and products within the sentence as words. More precisely, Prod2Vec (see figure 3-2) trains the product embedding using the Skip-Gram (SG) model by maximizing the likelihood over the entire set of products with the number of unique products 𝑀 and with the length of the context 𝑐.

P(𝑝 𝑖+𝑗 |𝑝 𝑖 ) = exp(𝑣 𝑇 𝑝 𝑖 , 𝑣 ′ 𝑝 𝑖+𝑗 ) ∑ 𝑀 𝑝=1 exp(𝑣 𝑇 𝑝 𝑖 , 𝑣 ′ 𝑝 ) (3.5)
This model was then extended in [START_REF] Vasile | Meta-prod2vec: Product embeddings using side-information for recommendation[END_REF] who, by defining appropriate context matrices, proposed to learn embedding for meta information available in the system. In addition, they demonstrated that the improvement obtained was mainly the result of the ability of their approach to deal with item cold-start. Inspired by the concept of sequence of words; the approach proposed by [START_REF] Guàrdia-Sebaoun | Latent trajectory modeling: A light and efficient way to introduce time in recommender systems[END_REF] defined the consumption of items by users as trajectories. Then, the embedding of items is learned using the SG model and the users embedding is further inferred as to predict the next item in the trajectory.

Deep Neural Networks architectures for recommmendation

Different topologies of Deep Neural Networks could be used to handle the challenge of employing context information while taking into consideration the time over interactions in the system. The advantage of neural network design over traditional ranking models is its extensibility. It is easy to start with a simple model and then demonstrate the approach's effectiveness; as it is possible to define what will be effective in a specific task during the experiments. In the following, we will present the most popular neural network based approaches for recommender systems.

• Autoencoders

The network first creates a low-dimensional representation of the user from the data, removing all except the most important information, then decoding the data in its original dimension. As a consequence, a noise-free, averaged representation is created, from which any item's preference may be estimated.

Deep AutoEncoder [START_REF] Kuchaiev | Training deep autoencoders for collaborative filtering[END_REF], might be used as an example of an autoencoder model in a ranking problem. During training, sparse vector of rates is taken as the input of the model because there are no users in reality that can estimate all set of items. The model's output is dense, which indicates that the network predicts all of the user's future ratings.

• Convolutional Neural Networks (CNN)

The principle behind convolutional neural networks is that convolutional layers are alternated with non-linear and fully-connected layers. Initially, CNN was used to do effective image recognition, but it currently now performs well in other areas such as ranking problems.

Convolutional neural networks work on the basis of filters (see figure 3-3) that are engaged in recognizing certain image characteristics (for example, straight lines). A filter is an ordinary matrix of weights, which are trained. The filter moves along the image and determines whether some desired characteristic is present in a specific part of it, by applying convolution operation, which is the sum of the products of the filter elements and the input signal matrix.

When potential factors cannot be obtained from user feedback, CNN is used to extract potential factors from images, audio data [START_REF] Chen | Learning audio embeddings with user listening data for content-based music recommendation[END_REF], Nguyen et al., 2017]. One of the cases is to use CNN to extract hidden features from an image and map them with user preferences in the same hidden space. Thus, speaking about recommender systems, CNN is mainly used to extract additional characteristics from the data. It is worth noting that this model doesn't apply for feature extraction from some additional data (images, audio) as it was discussed before. The main idea of the model comes from the image recognition field, considering embedding matrix for items as the image and passing the horizontal and vertical convolution filters for searching the local features. As the input the model takes 𝐿 clicked items for each user 𝑢 we and their next 𝑇 (𝑇 is the parameter) items as the targets.

To make the recommendations for a user 𝑢 at time step 𝑡 using trained Caser, latent user embedding and matrix of trained embeddings for the user's last 𝐿 interactions are taken as the input to predict 𝑁 next items.

The motivation of Caser was to provide accurate recommendations, referring to the suggestion that the sequential patterns, where more recent items in a sequence have a larger impact on the next item, play an important role in the predictions. As the results it provides a unified and flexible network structure for capturing both general preferences and sequential patterns.

• Recurrent Neural Networks (RNN)

Inside the RNN the basic recurrent cell is located. The model takes input data and pass it through RNN, which has a hidden internal state. This state is updated each time when new data is received in the RNN. Often the task requires that RNN generates some output at each time interval, therefore, after reading the input data and updating the hidden state, the RNN will create the output data. Inside the green box, figure 3-5, the recurrence relation is calculated:

ℎ 𝑡 = 𝑓 𝑊 (ℎ 𝑡-1 , 𝑥 𝑡 ) (3.6)
To find the new state ℎ 𝑡 , the previous hidden state ℎ 𝑡-1 and the current input 𝑥 𝑡 are taken. When the next input data come to the model, the received hidden state ℎ 𝑡 is passed through the same function 𝑓 𝑊 , and the whole process is repeated. If there are sufficiently long input sequences, the network could face with the problem of forgetting the information about remote input objects. But in some cases, there is a necessity for the network to "remember" information about the objects located at the beginning of the sequence. To solve this problem, the modifications of RNN, such as GRU and LSTM were proposed.

The recommender system uses RNN to integrate the current browsing history and order of views to provide more accurate recommendations. For example, [Hidasi et al., 2016a, Hidasi and[START_REF] Hidasi | [END_REF] used RNN to represent temporal and contextual aspects of user behavior that finally came them to more accurate recommendations. Compared to matrix factorization approach, RNN has a positive effect on the coverage of recommendations and short-term forecasts. This success stems from the evolution of RNN according to the taste of users and the calculation of the joint evolution between users and the potential characteristics of the items.

The authors of the GRU4Rec [START_REF] Hidasi | Recurrent neural networks with top-k gains for session-based recommendations[END_REF] adapt the idea of using recurrent neural networks for session-based recommendations. The main motivation of the work is to apply the long-sessions (full user's history) for building recommendations by suggesting that it could provide a more complete picture on the user's preferences.

Because of the different session size for each user (the difference is even stronger then for the sentences in texts) and the concept of strong time dependency between the interactions inside the session, classical sliding window used over the sentences for building mini-batches seems not relevant for recommender systems.

That is why authors suggest the new strategy for creating mini-batches. First mini-batch is represented by the first event for the first 𝑋 sessions from the full set of time-ordered sessions. For the second mini-batch the second events are used and so on. When any of the session ends, the next available session is taken. Since the sessions are assumed to be independent, the hidden state is resetted when the new session is taken for mini-batch. So called session-parallel mini-batches are presented on the figure 3-6. As the result, authors adapted the GRU model to the recommender systems setting by focusing on the session-based direction. Their strategy of building mini-batches in parallel sessions significantly outperformed popular baselines that are used for this task.

• Graph Neural Networks (GNN)

The idea lying behind Graph Neural Networks (GNN) is to learn a mapping that represents nodes or entire (sub)graphs as points in a low-dimensional vector space. The goal is to optimize this mapping so that the geometric relations in this studied space display the structure of the original graph. For example the recommender system could be modeled as a bipartite graph. In such a graph we are dealing with the nodes of two types as it's represented on the right part of figure 3-7 with "red" and blue" nodes. The logic of graph construction is such that edges connect only nodes of different types. So, in case of recommender systems, sets of users 𝑈 and items 𝑉 could be considered as two class of nodes (left part of the figure 34567), where ones the user interacts with the item, appropriate edge connects these two nodes, otherwise there is no edge between user and item. Proposed by [START_REF] He | LightGCN: Simplifying and powering graph convolution network for recommendation[END_REF] LightGCN for recommendations consists of the graph convolution with the discarded feature transformation and nonlinear activation operations (see figure 345678). The normalized sum of neighbor embeddings of LightGCN is taken towards next layer. In layer combination part, the final embedding of the node is constructed as the weighted sum of its embeddings on all layers. These models have demonstrated their ability to handle complicated contextual information, such as item summaries generated by extrative summarization approaches [START_REF] Amini | A contextual query expansion approach by term clustering for robust text summarization[END_REF]].

• Transformers

The architecture of Transformers also was designed to process sequences as RNN's. But unlike RNN's, transformers do not require processing sequences consecutively. For example, if the input data is text, then the transformer does not need to process the end of the text after processing its beginning. Due to this, transformers are parallelized more easily than RNN's and can be trained faster The main distinctive feature of transformers is in calculating attention, that consists in transforming the embedding vector into three vectors: query, key and value vectors. These vectors are created by multiplying embedding into three matrices that are trained during the training process. As a result, 𝑧 vector is calculated (see figure 3456789) and then it is transmitted further through forward path of the neural network.

Evaluation metrics

In order to choose the best model from the whole variety of algorithms and approaches, it is necessary to be able to assess their quality quantitatively. In this section, we will present the most common ranking metrics used to evaluate recommender systems.

Consider 𝑁 users 𝑈 = {𝑢 𝑖 } 𝑁 𝑖=1 and 𝑀 items 𝐸 = {𝑒 𝑗 } 𝑀 𝑗=1 . The result of the ranking algorithm is the mapping, which assigns to each item 𝑒 ∈ 𝐸 the weight 𝑟(𝑒), which characterizes the degree of relevance of this item to the particular user 𝑢 ∈ 𝑈 (the greater the weight, the more relevant the object). That is why the set of weights determines the permutation 𝜋 on the set of items based on their sorting in descending order.

To estimate the quality of the ranking, it is necessary to have some ground true with which the results of the algorithm can be compared. Suggest 𝑟 𝑡𝑟𝑢𝑒 ∈ [0, 1] is the reference relevance characterizes the real relevance of items for a given user (𝑟 𝑡𝑟𝑢𝑒 = 1 item is ideal, 𝑟 𝑡𝑟𝑢𝑒 = 0 -completely irrelevant), 𝜋 𝑡𝑟𝑢𝑒 is the corresponding permutation of 𝑟 𝑡𝑟𝑢𝑒 (𝑒).

It is worth noting that when 𝑟 𝑡𝑟𝑢𝑒 takes only extreme values: 0 and 1, the permutation 𝜋 𝑡𝑟𝑢𝑒 is usually not considered and only the set of relevant items for which 𝑟 𝑡𝑟𝑢𝑒 = 1 is taken into account. So, the purpose of the metric is to determine how well the relevance obtained by the algorithm and the corresponding permutation 𝜋 to the true relevance values 𝑟 𝑡𝑟𝑢𝑒 . In the next subsections the main metrics would be considered.

Mean Average Precision

Mean average precision at K (MAP@𝐾) is one of the most frequently used ranking metrics. Precision measures are used in binary problem, where relevance accepted two values: 0 and 1.

MAP@𝐾 = 1 𝑁 𝑁 ∑ 𝑢=1 AP@𝐾.
Here the Average Precision at rank 𝐾, AP@𝐾, is defined as :

AP@𝐾 = 1 𝐾 𝐾 ∑ 𝑘=1 𝑟 𝑘 𝑃 𝑟(𝑘),
where, 𝑃 𝑟(𝑘) is the precision at rank 𝑘 of the relevant items and 𝑟 𝑘 = 1 if the item at rank 𝑘 is preferred or clicked, and 0 otherwise. The idea of MAP@𝐾 is to calculate AP@𝐾 for each user and then take the average. The idea is quite reasonable, assuming that all users are equally important. In case if it's necessary to differ between the objects, then instead of a simple averaging, it's possible to use a weighted sum by multiplying the AP@𝐾 of each object by its corresponding weight.

Normalized Discounted Cumulative Gain

There is another popular metric NDCG@𝐾, that could be applied for ranking. To compute NDCG@𝐾, the term called DCG@𝐾 is calculated taking into account the order of the items in the list by multiplying the relevance of the item by a weight equal to the inverse logarithm of the position number.

DCG@𝐾 = 𝐾 ∑ 𝑘=1 2 𝑟 𝑘 -1 log 2 (1 + 𝑘) .
In contrast to MAP@𝐾, 𝑟 𝑘 here can also be used in the case of non-binary values of the reference relevance. The use of the logarithm as a discount function can be explained by the following intuitive considerations: the positions at the beginning of the ranking differ much more than the positions at the end of it. It means that for a user it is more important to have accurate ranking at the first positions, like 1 to 10, and almost not important how correctly items will be distributed between 50 and 60 positions. Normalized version of DCG@𝐾 is called NDCG@𝐾 and computed below:

NDCG@𝐾 = 1 𝑁 𝑁 ∑ 𝑢=1 DCG@𝐾 IDCG@𝐾 ,
where IDCG@𝐾 is DCG@𝐾 with an ideal ordering equals to ∑ 𝐾 𝑘=1 1 log 2 (1+𝑘) .

Mean reciprocal rank

Another popular metric MRR@𝐾 define at which position of ranking customer find the first useful recommendation.

MRR@𝐾 = 1 𝑁 𝑁 ∑ 𝑢=1 RR@𝐾, RR@𝐾 the value equal to the inverse rank of the first correctly predicted item:

RR@𝐾 = 1 min{𝑘 ∈ 1, .., 𝐾 : 𝑟 𝑘 = 1}
.

MRR@𝐾 varies in the range [0, 1] and takes into account only the first correctly predicted position, not paying attention to all the subsequent ones.

Rank Correlation based metrics

The rank correlation coefficient takes into account not the values of element's relevances, but only their rank. Below the two most common rank correlation coefficients, the Spearman and Kendall, are presented.

• Kendall correlation coefficient:

Consider {(𝑥 1 , 𝑦 1 ), ..., (𝑥 𝑘 , 𝑦 𝑘 )} be a set of observations of the joint random variables 𝑋 and 𝑌 . Based on the calculation of concordant (and discordant) pairs -pairs of elements to which the permutations have assigned the same (different) order.

𝜏 = |concordant pairs| -|discordant pairs| 𝐾(𝐾 -1)/2 ,
where concordant pairs are satisfy the condition: both 𝑥 𝑖 > 𝑥 𝑗 and 𝑦 𝑖 > 𝑦 𝑗 hold or both 𝑥 𝑖 < 𝑥 𝑗 and 𝑦 𝑖 < 𝑦 𝑗 hold; otherwise the pairs are discordant.

• Spearman correlation coefficient:

The Spearman correlation coefficient is defined as the Pearson correlation coefficient between the rank variables.

𝑟 𝑆 = 𝜌(𝜋, 𝜋 𝑡𝑟𝑢𝑒 ) = 𝑐𝑜𝑣(𝜋, 𝜋 𝑡𝑟𝑢𝑒 ) 𝜎 𝜋 , 𝜎 𝜋 𝑡𝑟𝑢𝑒 , 𝜌 denotes the usual Pearson correlation coefficient, but applied to the rank variables.

The quality metrics defined by rank correlation coefficient do not take into account the position of elements and the correlation is calculated for all elements simultaneously, not just for the top-K elements with the highest rank. Therefore, in practice these metrics are applied extremely rarely.

Area Under (ROC) Curve

Area Under (ROC) Curve (AUC) shows the probability that a randomly selected pair of products with different ratings will be ranked correctly; it means that those items that user likes will be higher in the output ranking than those that user doesn't like. The ROC curve is shown below on the figure 3-11. AUC is not often used in ranking systems, as its main advantage is more related to the task of classification, where it is important to understand the difference between the two classes.

Conclusion

In this chapter we provided an overview of work on Recommender Systems (RS) that provide personalized recommendations to users by adapting to their taste. The study of RS has become an active area of research these past years, especially since the Netflix Prize [START_REF] Bennett | The netflix prize[END_REF]. One characteristic of online recommendation is the huge unbalance between the available number of products and those shown to the users. Another aspect is the existence of bots that interact with the system by providing too many feedback over some targeted items; or many users that do not interact with the system over the items that are shown to them. In this context, the main challenges concern the design of a scalable and an efficient online RS in the presence of noise and unbalanced data. These challenges have evolved in time with the continuous development of data collections released for competitions or issued from e-commerce4 . New approaches for RS now primarily consider implicit feedback, mostly in the form of clicks, that are easier to collect than explicit feedback which is in the form of scores. Implicit feedback is more challenging to deal with as they do not depict the preference of a user over items, i.e., (no)click does not necessarily mean (dis)like [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF]. For this case, most of the developed approaches are based on the Learning-to-rank paradigm and focus on how to leverage the click information over the unclick one without considering the sequence of users' interactions.

Part II

Contribution

Chapter 4

Sequential Learning over Implicit Feedback for Robust Large-Scale Recommender Systems

Introduction

In this chapter, we propose our first contribution which is a new SequentiAl Rec-Ommender System for implicit feedback (called SAROS), that updates the model parameters user per user over blocks of items constituted by a sequence of unclicked items followed by a clicked one. The parameter updates are discarded for users who interact very little or a lot with the system. For other users, the update is done by minimizing the average ranking loss of the current model that scores the clicked item below the unclicked ones in a corresponding block. Recently, many other approaches that model the sequences of users feedback have been proposed, but they all suffer from a lack of theoretical analysis formalizing the overall learning strategy. In this work, we analyze the convergence property of the proposed approach and show that in the case where the global ranking loss estimated over all users and items is convex; then the minimizer found by the proposed sequential approach converges to the minimizer of the global ranking loss. Experimental results conducted on five large publicly available datasets show that our approach is highly competitive compared to the state-of-the-art models and, it is significantly faster than both the batch and the online versions of the algorithm. The results of this chapter were presented at the European Conference in Machine Learning & Principles ans Practices in Knowledge Discovery (ECML-PKDD) in 2019 [4] and Conférence sur l'Apprentissage Automatique (CAp) in 2021 [START_REF] Burashnikova | Apprentissage séquentiel de préférence utilisateurs pour les systèmes de recommandation[END_REF].

The rest of this chapter is organized as follows. Section 4.2 relates our work to previously proposed approaches. Section 4.3 introduces the general ranking learning problem that we address. Then, in Section 4.4, we present the SAROS algorithm and provide an analysis of its convergence. Section 4.5 presents the experimental results that support this approach. Finally, in Section 4.6, we discuss the outcomes of this study and give some pointers to further research.

Sequential learning for recommender systems

Many new approaches tackle the sequential learning problem for RS by taking into account the temporal aspect of interactions directly in the design of a dedicated model and are mainly based on Markov Models (MM), Reinforcement Learning (RL) and Recurrent Neural Networks (RNN) [START_REF] Donkers | Sequential userbased recurrent neural network recommendations[END_REF]. Recommender systems based on Markov Models, consider the sequential interaction of users as a stochastic process over discrete random variables related to predefined user behavior. These approaches suffer from some limitations mainly due to the sparsity of the data leading to a poor estimation of the transition matrix [START_REF] Shani | An MDPbased recommender system[END_REF]. Various strategies have been proposed to leverage the impact of sparse data, for example by considering only the last frequent sequences of items and using finite mixture models [START_REF] Shani | An MDPbased recommender system[END_REF], or by combining similarity-based methods with high-order Markov Chains [START_REF] Ruining | Fusing similarity models with markov chains for sparse sequential recommendation[END_REF]. Although it has been shown that in some cases the proposed approaches can capture the temporal aspect of user interactions but these models suffer from high complexity and generally they do not pass the scale. Some other methods consider RS as a Markov decision process (MDP) problem and solve it using reinforcement learning (RL) [Moling et al., 2012, Tavakol and[START_REF] Tavakol | [END_REF]. The size of discrete actions bringing the RL solver to a larger class of problems is also a bottleneck for these approaches. Very recently Recurrent neural networks such as GRU or LSTM, have been proposed for personalized recommendations [START_REF] Hidasi | Recurrent neural networks with top-k gains for session-based recommendations[END_REF], Tang and Wang, 2018a, Kang and McAuley, 2018], where the input of the network is generally the current state of the session, and the output is the predicted preference over items (probabilities for each item to be clicked next).

Our proposed strategy differs from other sequential based approaches in the way that the model parameters are updated, at each time a block of unclicked items followed by a clicked one is constituted; and by controlling the number of blocks per user interaction. If for a given user, this number is below or above two predefined thresholds found over the distribution of the number of blocks, parameter updates for that particular user are discarded. Ultimately, we provide a proof of convergence of the proposed approach.

Framework and Problem Setting

Throughout, we use the following notation. For any positive integer 𝑛, [𝑛] denotes the set [𝑛] . = {1, . . . , 𝑛}. We suppose that ℐ . = [𝑀 ] and 𝒰 . = [𝑁 ] are two sets of indexes defined over items and users. Further, we assume that each pair constituted by a user 𝑢 and an item 𝑖 is identically and independently distributed according to a fixed yet unknown distribution 𝒟 𝒰 ,ℐ .

At the end of his or her session, a user 𝑢 ∈ 𝒰 has reviewed a subset of items ℐ 𝑢 ⊆ ℐ that can be decomposed into two sets: the set of preferred and non-preferred items denoted by ℐ + 𝑢 and ℐ - 𝑢 , respectively. Hence, for each pair of items (𝑖, 𝑖 ′ ) ∈ ℐ + 𝑢 × ℐ - 𝑢 , the user 𝑢 prefers item 𝑖 over item 𝑖 ′ ; symbolized by the relation 𝑖 ≻ u 𝑖 ′ . From this preference relation a desired output 𝑦 𝑢,𝑖,𝑖 ′ ∈ {-1, +1} is defined over the pairs (𝑢, 𝑖) ∈ 𝒰 × ℐ and

ℐ = [𝑀 ]

The set of item indexes

𝒰 = [𝑁 ]

The

𝑢

The set of all positive items for user 𝑢 ℐ -

𝑢

The set of all negative items for user 𝑢 ℓ 𝑢,𝑖,𝑖 ′ (𝜔)

Instantaneous loss for user 𝑢 and a pair of items (𝑖, 𝑖 ′ ) L𝑢 (𝜔)

Empirical ranking loss with respect to user 𝑢 L𝑢 (𝜔) =

Proposed Approach

Our objective here is to minimize an expected error penalizing the misordering of all pairs of interacted items 𝑖 and 𝑖 ′ for a user 𝑢. Commonly, this objective is given under the Empirical Risk Minimization (ERM) principle, by minimizing the empirical ranking loss estimated over the items and the final set of users who interacted with the system :

L𝑢 (𝜔) = 1 |ℐ + 𝑢 ||ℐ - 𝑢 | ∑ 𝑖∈ℐ + 𝑢 ∑ 𝑖 ′ ∈ℐ - 𝑢 ℓ 𝑢,𝑖,𝑖 ′ (𝜔), (4.1)
and

ℒ(𝜔) = E 𝑢 [ L𝑢 (𝜔) ]
, where E 𝑢 is the expectation with respect to users chosen randomly according to the uniform distribution, and L𝑢 (𝜔) is the pairwise ranking loss with respect to user 𝑢's interactions. As in other studies, we represent each user 𝑢 and each item 𝑖 respectively by vectors U 𝑢 ∈ R 𝑘 and V 𝑖 ∈ R 𝑘 in the same latent space of dimension 𝑘 [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. The set of weights to be found 𝜔 = (U, V), are then matrices formed by the vector representations of users

U = (U 𝑢 ) 𝑢∈[𝑁 ] ∈ R 𝑁 ×𝑘 and items V = (V 𝑖 ) 𝑖∈[𝑀 ] ∈ R 𝑀 ×𝑘 .
The minimization of the ranking loss above in the batch mode with the goal of finding user and item embeddings, such that the dot product between these representations in the latent space reflects the best the preference of users over items, is a common approach. Other strategies have been proposed for the minimization of the empirical loss (4.1), among which the most popular one is perhaps the Bayesian Personalized Ranking (BPR) model [START_REF] Rendle | BPR: Bayesian personalized ranking from implicit feedback[END_REF]. In this approach, the instantaneous loss, ℓ 𝑢,𝑖,𝑖 ′ , is the surrogate regularized logistic loss for some hyperparameter 𝜇 ≥ 0:

ℓ 𝑢,𝑖,𝑖 ′ (𝜔) = log ( 1 + 𝑒 -𝑦 𝑖,𝑢,𝑖 ′ U ⊤ 𝑢 (V 𝑖 -V 𝑖 ′ ) ) + 𝜇(‖U 𝑢 ‖ 2 2 + ‖V 𝑖 ‖ 2 2 + ‖V 𝑖 ′ ‖ 2 2 ) (4.2)
The BPR algorithm proceeds by first randomly choosing a user 𝑢, and then repeatedly selecting two pairs (𝑖, 𝑖 ′ ) ∈ ℐ 𝑢 × ℐ 𝑢 .

In the case where one of the chosen items is preferred over the other one (i.e. 𝑦 𝑢,𝑖,𝑖 ′ ∈ {-1, +1}), the algorithm then updates the weights using the stochastic gradient descent method over the instantaneous loss (4.2). In this case, the expected number of rejected pairs is proportional to 𝑂(|ℐ 𝑢 | 2 ) [Sculley, 2009] which may be time-consuming in general. Another drawback is that user preference over items depend mostly on the context where these items are shown to the user. A user may prefer (or not) two items independently one from another, but within a given set of shown items, he or she may completely have a different preference over these items. By sampling items over the whole set of shown items, this effect of local preference is unclear.

Algorithm SAROS

Another particularity of online recommendation which is not explicitly taken into account by existing approaches is the bot attacks in the form of excessive clicks over some target items. They are made to force the RS to adapt its recommendations toward these target items, or a very few interactions which in both cases introduce biased data for the learning of an efficient RS. In order to tackle these points, our approach updates the parameters whenever the number of constituted blocks per user is lower and upper-bounded (Figure 4-1).

In this case, at each time a block ℬ 𝑡 𝑢 = N 𝑡 𝑢 ⊔ Π 𝑡 𝑢 is formed; weights are updated by minimizing the ranking loss corresponding to this block :

Lℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 ) = 1 |Π 𝑡 𝑢 ||N 𝑡 𝑢 | ∑ 𝑖∈Π 𝑡 𝑢 ∑ 𝑖 ′ ∈N 𝑡 𝑢 ℓ 𝑢,𝑖,𝑖 ′ (𝜔 𝑡 𝑢 ). (4.3)
The surrogate part is the same as defined in the Eq. 4.2. The pseudo-code of SAROS is shown in the following. Starting from initial weights 𝜔 0 1 chosen randomly for the first user. For each current user 𝑢, having been shown 𝐼 𝑢 items, the sequential update rule consists in updating the weights, block by block where after 𝑡 updates; where the (𝑡 + 1) 𝑡ℎ update over the current block ℬ 𝑡 𝑢 = N 𝑡 𝑢 ⊔ Π 𝑡 𝑢 corresponds to one gradient descent step over the ranking loss estimated on these sets and which with the current weights 𝜔 𝑡 𝑢 writes,

𝜔 𝑡+1 𝑢 ← 𝜔 𝑡 𝑢 -𝜂∇ Lℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 ) (4.4)
To prevent from a very few interactions or from bot attacks, two thresholds 𝑏 and 𝐵 are fixed over the parameter updates. For a new user 𝑢 + 1, the parameters are initialized as the last updated weights from the previous user's interactions in the case where the corresponding number of updates 𝑡 was in the interval [𝑏, 𝐵]; i.e. 𝜔 0 𝑢+1 = 𝜔 𝑡 𝑢 . On the contrary case, they are set to the same previous initial parameters; i.e., 𝜔 0 𝑢+1 = 𝜔 0 𝑢 .

Convergence analysis

We provide proofs of convergence for the SAROS algorithm under the typical hypothesis that the system is not instantaneously affected by the sequential learning of the weights. This hypothesis stipulates that the generation of items shown to users is independently and identically distributed with respect to some stationary in time underlying distribution 𝒟 ℐ , and constitutes the main hypothesis of almost all the existing studies. Furthermore, we make the following technical assumption.

Assumption 1 Let the loss functions ℓ 𝑢,𝑖,𝑖 ′ (𝜔) and ℒ(𝜔), 𝜔 ∈ R 𝑑 be such that for some absolute constants 𝛾 ≥ 𝛽 > 0 and 𝜎 > 0 :

1. ℓ 𝑢,𝑖,𝑖 ′ (𝜔) is non-negative for any user 𝑢 and a pair of items (𝑖, 𝑖 ′ );

N 𝑡 𝑢 ← N 𝑡 𝑢 ∪ {𝑖 𝑘 } else Π 𝑡 𝑢 ← Π 𝑡 𝑢 ∪ {𝑖 𝑘 } end if if N 𝑡 𝑢 ̸ = ∅ and Π 𝑡 𝑢 ̸ = ∅ and 𝑡 ≤ 𝐵 then 𝜔 𝑡+1 𝑢 ← 𝜔 𝑡 𝑢 - 𝜂 |N 𝑡 𝑢 ||Π 𝑡 𝑢 | ∑ 𝑖∈Π 𝑡 𝑢 ∑ 𝑖 ′ ∈N 𝑡 𝑢 ∇ℓ 𝑢,𝑖,𝑖 ′ (𝜔 𝑡 𝑢 ) 𝑡 = 𝑡 + 1, N 𝑡 𝑢 = ∅, Π 𝑡 𝑢 = ∅ end if end while end for if 𝑡 ≥ 𝑏 then 𝜔 0 𝑢+1 = 𝜔 𝑡 𝑢 else 𝜔 0 𝑢+1 = 𝜔 0 𝑢 end if
(𝜔 ′ )‖ 2 ≤ 𝛾‖𝜔 -𝜔 ′ ‖ 2 , as well as ‖∇ℒ(𝜔) -∇ℒ(𝜔 ′ )‖ 2 ≤ 𝛽‖𝜔 -𝜔 ′ ‖ 2 ,.

Variance of the empirical loss is bounded

E 𝒟 ⃦ ⃦ ⃦∇ L𝑢 (𝜔) -∇ℒ(𝜔) ⃦ ⃦ ⃦ 2 2 ≤ 𝜎 2 .
Moreover, there exist some positive lower and upper bounds 𝑏 and 𝐵, such that the number of updates for any 𝑢 is within the interval [𝑏, 𝐵] almost surely.

Prior to the proof of the theorems, we first prove the following lemma Lemma 1 Let a sequence of items (𝑖 1 , . . . , 𝑖 𝑚 ) be generated i.i.d. according to a distribution 𝒟 𝑢 over items for a given user 𝑢. Then for any sequence of blocks {ℬ 1 𝑢 , . . . , ℬ 𝑘 𝑢 } generated by algorithm SAROS for that user we have,

E 𝒟𝑢 [ 1 𝑘 𝑘 ∑ 𝑡=1 ∇ ̂ ℒ ℬ 𝑡 𝑢 (𝜔) ] = ∇ ̂ ℒ 𝑢 (𝜔), with ̂ ℒ 𝑢 (𝜔) = 1 |ℐ + 𝑢 ||ℐ - 𝑢 | ∑ 𝑖∈ℐ + 𝑢 ∑ 𝑖 ′ ∈ℐ - 𝑢 ℓ 𝑢,𝑖,𝑖 ′ (𝜔), (4.5)
where

̂ ℒ ℬ 𝑡 𝑢 (𝜔) = 1 |Π 𝑡 𝑢 ||N 𝑡 𝑢 | ∑ 𝑖∈Π 𝑡 𝑢 ∑ 𝑖 ′ ∈N 𝑡 𝑢 ℓ 𝑢,𝑖,𝑖 ′ (𝜔),
and Π 𝑡 𝑢 , 𝑁 𝑡 𝑢 are the sets of positive (resp. negative) interactions in the block ℬ 𝑡 𝑢 . In other words, the expected gradient of empirical loss, taken over random blocks ℬ 𝑡 𝑢 , . . . , ℬ 𝑘 𝑢 generated by the SAROS algorithm for a user 𝑢, equals to the expected loss over 𝑢. Moreover, if for any (𝑢, 𝑖, 𝑖 ′ ) one has ‖∇𝑙 𝑢,𝑖,𝑖 ′ (𝜔)‖ 2 2 ≤ 𝛾 2 , then

E 𝒟𝑢 ⃦ ⃦ ⃦ ⃦ ∇ ̂ ℒ 𝑢 (𝜔) - 1 𝑘 𝑘 ∑ 𝑡=1 ∇ ̂ ℒ ℬ 𝑡 𝑢 (𝜔) ⃦ ⃦ ⃦ ⃦ 2 2 ≤ 3 𝛾 2 𝑘 .
Proof. Consider the expectation of the gradient of the empirical loss over a user 𝑢, ∇ℒ ℬ 𝑡 𝑢 (𝜔), taken with respect to a block ℬ 𝑡 . For a fixed block, ℬ 𝑡 , the value of

|𝑁 𝑡 𝑢 | • |Π 𝑡 𝑢 | is a constant.
Thus, due to the linearity of expectation, for the sum of random ℓ 𝑢,𝑖,𝑖 ′ (𝜔) we have

E 𝒟 ℬ 𝑡 𝑢 ∇ ̂ ℒ ℬ 𝑡 𝑢 (𝜔) =E 𝒟 ℬ 𝑡 𝑢 ⎡ ⎣ 1 |Π 𝑡 𝑢 ||N 𝑡 𝑢 | ∑ 𝑖∈Π 𝑡 𝑢 ∑ 𝑖 ′ ∈N 𝑡 𝑢 ∇ℓ 𝑢,𝑖,𝑖 ′ (𝜔) ⎤ ⎦ = 1 |Π 𝑡 𝑢 ||N 𝑡 𝑢 | ∑ 𝑖∈Π 𝑡 𝑢 ∑ 𝑖 ′ ∈N 𝑡 𝑢 ∇ ̂ ℒ 𝑢 (𝜔) = ∇ ̂ ℒ 𝑢 (𝜔) (4.6)
where the first sum consists of a non-zero number of addends as each block contains at least one positive and one negative item. Thus, by the law of total expectation, E 𝜓 𝑓 (𝜓) = E 𝜂 E 𝜓|𝜂 𝑓 (𝜓) for any properly defined random variables 𝜓, 𝜂 and a function 𝑓 , we have

E 𝒟𝑢 [ 1 𝑘 𝑘 ∑ 𝑡=1 ∇ ̂ ℒ ℬ 𝑡 (𝜔) ] = 1 𝑘 E 𝒟𝑢 [ 𝑘 ∑ 𝑡=1 ∇ ̂ ℒ ℬ 𝑡 (𝜔) ] = 1 𝑘 𝑘 ∑ 𝑡=1 E 𝒟 ℬ 𝑡 𝑢 𝑢 E 𝒟 ℬ 𝑡 𝑢 [ ∇ ̂ ℒ ℬ 𝑡 𝑢 (𝜔) ⃒ ⃒ ⃒ ⃒ ℬ 𝑡 𝑢 ] = 1 𝑘 𝑘 ∑ 𝑡=1 E 𝒟 ℬ 𝑡 𝑢 𝑢 ∇ ̂ ℒ 𝑢 (𝜔) = ∇ ̂ ℒ 𝑢 (𝜔)
where the last equality is due to Eq. (4.6).

To proof the bound on variance, recall, that SAROS constructs the blocks sequentially, so that the number of positive and negative items in any block ℬ 𝑡 𝑢 is affected only by the previous and the next block. Thus, any block after the next to ℬ 𝑡 𝑢 and before the previous to ℬ 𝑡 𝑢 are conditionally independent for any fixed ℬ 𝑡 𝑢 . Then if

𝑉 2 = E 𝒟 ℬ 𝑡 𝑢 ‖∇ ̂ ℒ ℬ 𝑡 𝑢 (𝜔) -∇ ̂ ℒ 𝑢 (𝜔)‖ 2
2 one has:

E 𝒟 ℬ 1 𝑢 ,...,...,𝒟 ℬ 𝑘 𝑢 ⃦ ⃦ ⃦ ⃦ 1 𝑘 𝑘 ∑ 𝑗=1 ( ∇ ̂ ℒ ℬ 𝑗 𝑢 (𝜔) -∇ ̂ ℒ 𝑢 (𝜔) ) ⃦ ⃦ ⃦ ⃦ 2 2 = E 𝒟 ℬ 1 𝑢 ,...,...,𝒟 ℬ 𝑘 𝑢 ⎡ ⎣ 1 𝑘 2 𝑘 ∑ 𝑖,𝑗=1 ( ∇ ̂ ℒ ℬ 𝑖 𝑢 (𝜔) -∇ ̂ ℒ 𝑢 (𝜔) )( ∇ ̂ ℒ ℬ 𝑗 𝑢 (𝜔) -∇ ̂ ℒ 𝑢 (𝜔) ) ⊤ ⎤ ⎦ = E 𝒟 ℬ 2 𝑢 E 𝒟 ℬ 1 𝑢 ,𝒟 ℬ 3 𝑢 ...,𝒟 ℬ 𝑘 𝑢 |ℬ 2 𝑢 ⎡ ⎣ 1 𝑘 2 𝑘 ∑ 𝑖,𝑗=1 ( ∇ ̂ ℒ ℬ 𝑖 𝑢 (𝜔) -∇ ̂ ℒ 𝑢 (𝜔) )( ∇ ̂ ℒ ℬ 𝑗 𝑢 (𝜔) -∇ ̂ ℒ 𝑢 (𝜔) ) ⊤ ⃒ ⃒ ⃒ ⃒ ℬ 2 ⎤ ⎦ ≤ 3𝑉 2 𝑘 2 + 1 𝑘 2 E 𝒟 ℬ 1 𝑢 ,𝒟 ℬ 3 𝑢 ,...,𝒟 ℬ 𝑘 𝑢 𝑘 ∑ 𝑖,𝑗=1 𝑖,𝑗̸ =2 ( ∇ ̂ ℒ ℬ 𝑖 𝑢 (𝜔) -∇ ̂ ℒ 𝑢 (𝜔) )( ∇ ̂ ℒ ℬ 𝑗 𝑢 (𝜔) -∇ ̂ ℒ 𝑢 (𝜔) ) ⊤ ≤ 3𝑉 2 𝑘
To conclude the proof it remains to note that

𝑉 2 ≤ 𝛾 2 as 𝑉 2 ≤ E 𝒟 ℬ 𝑡 𝑢 ‖∇ ̂ ℒ ℬ 𝑡 𝑢 ‖ 2 2 .
Our main result in this chapter is the following theorem which provides a bound over the deviation of the ranking loss with respect to the sequence of weights found by the SAROS algorithm and its minimum in the case where the latter is convex. Theorem 4 ([4]) Let ℓ 𝑢,𝑖,𝑖 ′ (𝜔) and ℒ(𝜔) satisfy Assumption 1. Then for any constant step size 𝜂, verifying 0 < 𝜂 ≤ min{1/(𝛽𝐵), 1/ √ 𝑁 𝐵(𝜎 2 + 3𝛾 2 /𝑏)}, and any set of users 𝒰 = {1, . . . , 𝑁 }; algorithm SAROS iteratively generates a sequence {𝜔 0 𝑗 } 𝑢∈𝒰 such that

1 𝛽 E 𝒟 ‖∇ℒ(𝜔 0 𝑢 )‖ 2 2 ≤ 𝛽𝐵∆ 2 ℒ 𝑁 + 2∆ ℒ √ 𝐵𝜎 2 + 3𝐵𝛾 2 /𝑏 𝑁 , ∆ 2 ℒ = 2 𝛽 (ℒ(𝜔 0 ) -ℒ(𝜔 * ))
where the expectation is taken with respect to users chosen randomly according to the uniform distribution 𝑝 𝑢 = 1 𝑁 . Furthermore, if the ranking loss ℒ(𝜔) is convex, then for any ω𝑢 = ∑ 𝑗≤𝑢 𝜔 0 𝑗 we have

ℒ(ω 𝑢 ) -ℒ(𝜔 * ) ≤ 𝛽𝐵∆ 𝜔 2 𝑁 + 2∆ 𝜔 √ 𝐵𝜎 2 + 3𝐵𝛾 2 /𝑏 𝑁 , ∆ 2 𝜔 = ‖𝜔 0 -𝜔 * ‖ 2 2 .
Proof of the theorem is mainly based on the randomized stochastic gradient descent analysis [START_REF] Ghadimi | Stochastic first-and zerothorder methods for nonconvex stochastic programming[END_REF]. Proof. Let 𝑔 𝑡 𝑢 be a gradient of the loss function taken for user 𝑢 over block ℬ 𝑡 𝑢 :

𝑔 𝑡 𝑢 = 1 |𝑁 𝑡 𝑢 ||Π 𝑡 𝑢 | ∑ 𝑖∈𝑁 𝑡 𝑢 ,𝑖 ′ ∈Π 𝑡 𝑢 ∇ℓ 𝑢,𝑖,𝑖 ′ (𝜔 𝑡-1 𝑢 ),
By Lemma 1 we have E 𝒟 ℬ 𝑡 𝑢 𝑔 𝑡 𝑢 = ∇ L𝑢 (𝜔). In the notation of Algorithm SAROS,

𝜔 𝑡+1 𝑢 = 𝜔 𝑡 𝑢 -𝜂𝑔 𝑡 𝑢 , 𝜔 0 𝑢+1 = 𝜔 |ℬ𝑢| 𝑢 , 𝜔 0 𝑢+1 -𝜔 0 𝑢 = 𝜂 ∑ 𝑡∈ℬ𝑢 𝑔 𝑡 𝑢 .
Let 𝛿 𝑡 𝑢 = 𝑔 𝑡 𝑢 -∇ℒ(𝜔 0 𝑢 ), and let ℬ 𝑢 be a set of all blocks corresponding to user 𝑢. Using the smoothness of the loss function implied by Assumption 1 one has for 𝜔 0 𝑢+1 :

ℒ(𝜔 0 𝑢+1 ) ≤ ℒ(𝜔 0 𝑢 ) -⟨∇ℒ(𝜔 0 𝑢 ), 𝜔 0 𝑢+1 -𝜔 0 𝑢 ⟩ + 𝛽 2 𝜂 2 ⃦ ⃦ ⃦ ⃦ ⃦ ∑ 𝑡∈ℬ𝑢 𝑔 𝑡 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ 2 2 = ℒ(𝜔 0 𝑢 ) -𝜂 ∑ 𝑡∈ℬ𝑢 ⟨∇ℒ(𝜔 0 𝑢 ), 𝑔 𝑡 𝑢 ⟩ + 𝛽 2 𝜂 2 ⃦ ⃦ ⃦ ⃦ ⃦ ∑ 𝑡∈ℬ𝑢 𝑔 𝑡 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ 2 2 = ℒ(𝜔 0 𝑢 ) -𝜂|ℬ 𝑢 |‖∇ℒ(𝜔 0 𝑢 )‖ 2 2 -𝜂 ∑ 𝑡∈ℬ𝑢 ⟨∇ℒ(𝜔 0 𝑢 ), 𝛿 𝑡 𝑢 ⟩ + 𝛽 2 𝜂 2 [ |ℬ 𝑢 | 2 ‖∇ℒ(𝜔 0 𝑢 )‖ 2 2 + 2|ℬ 𝑢 | ∑ 𝑡∈ℬ𝑢 ⟨∇ℒ(𝜔 0 𝑢 ), 𝛿 𝑡 𝑢 ⟩ + ∑ 𝑡∈ℬ𝑢 ‖𝛿 𝑡 𝑢 ‖ 2 ] = ℒ(𝜔𝑢 0 ) - ( η𝑢 - 𝛽 2 η2 𝑢 ) ‖∇ℒ(𝜔 0 𝑢 )‖ 2 2 -(η 𝑢 -𝛽 η2 𝑢 ) ∑ 𝑡∈ℬ𝑢 ⟨ ∇ℒ(𝜔 0 𝑢 ), 𝛿 𝑡 𝑢 |ℬ 𝑢 | ⟩ + 𝛽 2 η2 𝑢 ∑ 𝑡∈ℬ𝑢 ⃦ ⃦ ⃦ ⃦ 𝛿 𝑡 𝑢 |ℬ 𝑢 | ⃦ ⃦ ⃦ ⃦ 2 2
where η𝑢 = |ℬ 𝑢 |𝜂.

Then re-arranging and summing up, we have

𝑁 ∑ 𝑢=1 ( η𝑢 - 𝛽 2 η2 𝑢 ) ‖∇ℒ(𝜔 𝑢 )‖ 2 2 ≤ ℒ(𝜔 0 ) -ℒ(𝜔 * ) - 𝑁 ∑ 𝑢=1 (η 𝑢 -𝛽 η2 𝑢 ) ⟨ ∇ℒ(𝜔 𝑢 ), ∑ 𝑡∈ℬ𝑢 𝛿 𝑡 𝑢 |ℬ 𝑢 | ⟩ + 𝛽 2 𝑁 ∑ 𝑢=1 η2 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ ∑ 𝑡∈ℬ𝑢 𝛿 𝑡 𝑢 |ℬ 𝑢 | ⃦ ⃦ ⃦ ⃦ ⃦ 2 2
By Lemma 1, the stochastic gradient taken with respect to a block of items gives an unbiased estimate of the gradient, thus

E 𝒟𝑢 [⟨ ∇ℒ(𝜔 𝑢 ), ∑ 𝑡∈ℬ𝑢 𝛿 𝑡 𝑢 |ℬ 𝑢 | ⟩⃒ ⃒ ⃒ ⃒ 𝜉 𝑢 ] = 0,
where 𝜉 𝑢 is a set of users preceding 𝑢. As in the conditions of the theorem 𝑏 ≤ ℬ 𝑢 almost surely, one has by Lemma 1 and the law of total variation, Var 𝜓 = E[Var(𝜓|𝜂)] +

Var [E[𝜓|𝜂]]:

E 𝒟𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ ∑ 𝑡∈ℬ𝑢 𝛿 𝑡 𝑢 |ℬ 𝑢 | ⃦ ⃦ ⃦ ⃦ ⃦ 2 2 ≤ 𝜎 2 + 3𝛾 2 𝑏 (4.7)
where the first attend on the right-hand side of Eq. ( 4.7) comes from Assumption 1, and the second term is due to Lemma 1. Finally, one obtains

𝑁 ∑ 𝑢=1 ( η𝑢 - 𝛽 2 η2 𝑢 ) E 𝜉 𝑁 ‖∇ℒ(𝜔 𝑢 )‖ 2 2 ≤ ℒ(𝜔 0 ) -ℒ(𝜔 * ) + 𝛽(𝜎 2 𝑏 + 3𝛾 2 ) 2𝑏 𝑁 ∑ 𝑢=1 η2 𝑢 . Condition 𝛽𝜂𝐵 ≤ 1 implies η𝑢 -𝛽 η2 𝑢 /2 ≥ η𝑢 /2, thus 1 𝛽 E 𝒟 ‖∇ℒ(𝜔)‖ 2 2 ≤ 1 ∑ 𝑁 𝑢=1 η𝑢 [ 2(ℒ(𝜔 0 ) -ℒ(𝜔 * )) 𝛽 + ( 𝜎 2 + 3 𝛾 2 𝑏 ) 𝑁 ∑ 𝑢=1 η2 𝑢 ] Taking 𝜂 = min {𝜂 1 , 𝜓𝜂 2 } , 𝜂 1 = 1 𝛽𝐵 , 𝜂 2 = 1 √ 𝑁 𝐵(𝜎 2 + 3𝛾 2 /𝑏) for some 𝜓 > 0. Let 𝐷 ℒ = √ 2(ℒ(𝜔 0 ) -ℒ(𝜔 * ))/𝛽, then 1 𝛽 E 𝒟 ‖∇ℒ(𝜔)‖ 2 2 ≤ 𝐷 2 ℒ 𝑁 min{𝜂 1 , 𝜓𝜂 2 } + ( 𝜎 2 + 3 𝛾 2 𝑏 ) ∑ 𝑁 𝑢=1 η2 𝑢 ∑ 𝑁 𝑢=1 η𝑢 ≤ 𝐷 2 ℒ 𝑁 𝜂 1 + 𝐷 2 ℒ 𝑁 𝜓𝜂 2 + ( 𝜎 2 + 3 𝛾 2 𝑏 ) 𝐵𝜓𝜂 2 ≤ 𝛽𝐵𝐷 2 ℒ 𝑁 + √ 𝐵𝜎 2 + 3𝐵𝛾 2 /𝑏 𝑁 ( 𝒟 2 ℒ 𝜓 + 𝜓 ) ≤ 𝛽𝐵𝐷 2 ℒ 𝑁 + 2𝒟 ℒ √ 𝐵𝜎 2 + 3𝐵𝛾 2 /𝑏 𝑁
To conclude the proof it remains to provide a bound in the case of convex loss function.

Due to the smoothness of the loss function:

1 𝛽 ‖∇ℒ(𝜔 𝑢 )‖ 2 2 ≤ ⟨∇ℒ(𝜔 𝑢 ), 𝜔 𝑢 -𝜔 * ⟩ (4.8) Denote 𝜑 𝑢 = 𝜔 0 𝑢 -𝜔 * , then 𝜑 2 𝑢+1 = ⃦ ⃦ ⃦ ⃦ ⃦ 𝜔 𝑢 -𝜂 𝑢 ∑ 𝑡∈ℬ𝑢 𝑔 𝑡 𝑢 -𝜔 * ⃦ ⃦ ⃦ ⃦ ⃦ 2 2 = 𝜑 2 𝑢 -2𝜂 𝑢 ∑ 𝑡∈ℬ𝑢 ⟨𝑔 𝑡 𝑢 , 𝜔 𝑢 -𝜔 * ⟩ + 𝜂 2 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ ∑ 𝑡∈ℬ𝑢 𝑔 𝑡 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ 2 2 = 𝜑 2 𝑢 -2𝜂 𝑢 ∑ 𝑡∈ℬ𝑢 ⟨∇ℒ(𝜔 𝑢 ) + 𝛿 𝑡 𝑢 , 𝜔 𝑢 -𝜔 * ⟩ + 𝜂 2 𝑢 ⎛ ⎝ ℬ 2 𝑢 ‖∇ℒ(𝜔 𝑢 )‖ 2 2 + 2ℬ 𝑢 ∑ 𝑡∈ℬ𝑢 ⟨∇ℒ(𝜔 𝑢 ), 𝛿 𝑡 𝑢 ⟩ + ⃦ ⃦ ⃦ ⃦ ⃦ ∑ 𝑡∈ℬ𝑢 𝛿 𝑡 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ 2 2 ⎞ ⎠
Combining it with the smoothness condition, Eq. ( 4.8), we have

𝜑 2 𝑢+1 -𝜑 2 𝑢 ≤ -(2|ℬ 𝑢 |𝜂 𝑢 -𝛽|ℬ 𝑢 | 2 𝜂 2 𝑢 )[ℒ(𝜔 𝑢 ) -ℒ(𝜔 * )] -2𝜂 𝑢 ∑ 𝑡∈ℬ𝑢 ⟨𝜔 𝑢 -𝜔 * -𝜂 𝑢 ∇ℒ(𝜔 𝑢 ), 𝛿 𝑡 𝑢 ⟩ + 𝜂 2 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ ∑ 𝑡∈ℬ𝑢 𝛿 𝑡 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ 2 2 (4.9)
Summing up the Inequalities (4.9) above for all 𝑢, we have

𝑁 ∑ 𝑢=1 ( η𝑢 - 𝛽 2 η2 𝑢 ) (ℒ(𝜔 𝑢 ) -ℒ(𝜔 * )) ≤ 𝒟 2 𝜔 -2 𝑁 ∑ 𝑢=1 ∑ 𝑡∈ℬ𝑢 𝜂 𝑢 ⟨𝜔 𝑢 -𝜂 𝑢 ∇ℒ(𝜔 𝑢 ) -𝜔 * , 𝛿 𝑡 𝑢 ⟩ + 𝑁 ∑ 𝑢=1 𝜂 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ ∑ 𝑡∈ℬ𝑢 𝛿 𝑡 𝑢 ⃦ ⃦ ⃦ ⃦ ⃦ 2 2
The rest of the proof exactly follow along the lines of that of first part and hence the details are omitted. This result implies that the loss over a sequence of weights (𝜔 0 𝑢 ) 𝑢∈𝒰 generated by the algorithm converges to the true minimizer of the ranking loss ℒ(𝜔) with a rate proportional to 𝑂(1/ √ 𝑢). The stochastic gradient descent strategy implemented in the Bayesian Personalized Ranking model (BPR) [START_REF] Rendle | BPR: Bayesian personalized ranking from implicit feedback[END_REF]] also converges to the minimizer of the ranking loss ℒ(𝜔) with the same rate. However, the main difference between BPR and SAROS is their computation time. As stated previously, the expected number of rejected random pairs sampled by algorithm BPR before making one update is 𝑂(|ℐ 𝑢 | 2 ) while with SAROS, blocks are created sequentially as and when users interact with the system. For each user 𝑢, weights are updated whenever a block is created, with the overall complexity of 𝑂(max

𝑡 (|Π 𝑡 𝑢 | × |N 𝑡 𝑢 |)), with max 𝑡 (|Π 𝑡 𝑢 | × |N 𝑡 𝑢 |) ≪ |ℐ 𝑢 | 2 .

Experimental Setup and Results

In this section, we provide an empirical evaluation of our optimization strategy on some popular benchmarks proposed for evaluating RS. All subsequently discussed components were implemented in Python3 using the TensorFlow library1 and computed on Skoltech CDISE HPC cluster "Zhores" [START_REF] Zacharov | Zhorespetaflops supercomputer for data-driven modeling, machine learning and artificial intelligence installed in Skolkovo Institute of Science and Technology[END_REF]. We first proceed with a presentation of the general experimental set-up, including a description of the datasets and the baseline models.

Datasets. We report results obtained on five publicly available datasets, for the task of personalized Top-N recommendation on the following collections :

• ML-1M [START_REF] Harper | The movielens datasets: History and context[END_REF] and Netflix [START_REF] Bennett | The netflix prize[END_REF] consist of user-movie ratings, on a scale of one to five, collected from a movie recommendation service and the Netflix company. The latter was released to support the Netflix Prize competition [START_REF] Bennett | The netflix prize[END_REF]. For both datasets, we consider ratings greater or equal to 4 as positive feedback, and negative feedback otherwise.

• We extracted a subset out of the Outbrain dataset from of the Kaggle challenge2 that consisted in the recommendation of news content to users based on the 1,597,426 implicit feedback collected from multiple publisher sites in the United States.

• Kasandr3 dataset [START_REF] Sidana | KASANDR: A Large-Scale Dataset with Implicit Feedback for Recommendation[END_REF] contains 15,844,717 interactions of 2,158,859 users in Germany using Kelkoo's (http://www.kelkoo.fr/) online advertising platform.

• Pandor4 is another publicly available dataset for online recommendation [START_REF] Sidana | Learning to recommend diverse items over implicit feedback on PANDOR[END_REF] provided by Purch (http://www.purch.com/). The dataset records 2,073,379 clicks generated by 177,366 users of one of the Purch's high-tech website over 9,077 ads they have been shown during one month. for the test. Table 4.3 presents the size of the training and the test sets as well as the percentage of positive feedback (preferred items) for all collections ordered by increasing training size. The percentage of positive feedback is inversely proportional to the size of the training sets, attaining 3% for the largest, Kasandr collection. We also analyzed the distributions of the number of blocks and their size for different collections. shows boxplots representing the logarithm of the number of blocks through their quartiles for all collections. From these plots, it comes out that the distribution of the number of blocks on Pandor, Netflix and Kasandr are heavy-tailed with more than the half of the users interacting no more than 10 times with the system. Furthermore, we note that on Pandor the average number of blocks is much smaller than on the two other collections; and that on all three collections the maximum numbers of blocks are 10 times more than the average. These plots suggest that a very small number of users (perhaps bots) have an abnormal interaction with the system generating a huge amount of blocks on these three collections. To have a better understanding, Figure 4-2 (right) depicts the number of blocks concerning their size on Kasandr. The distribution of the number of blocks follows a power law distribution and it is the same for the other collections that we did not report for the sake of space. In all collections, the number of blocks having more than 5 items drops drastically. As the SAROS does not sample positive and negative items for updating the weights, these updates are performed on blocks of small size, and are made very often. Compared approaches.

To validate the sequential approach described earlier, we compared the proposed SAROS algorithm5 with the following methods:

• MostPop is a non-learning based approach which consists in recommending the same set of popular items to all users.

• Matrix Factorization (MF) [Koren, 2008], is a factor model which decomposes the matrix of user-item interactions into a set of low dimensional vectors in the same latent space, by minimizing a regularized least square error between the actual value of the scores and the dot product over the user and item representations.

• BPR [START_REF] Rendle | BPR: Bayesian personalized ranking from implicit feedback[END_REF]] corresponds to the model described in the problem statement above, a stochastic gradient-descent algorithm, based on bootstrap sampling of training triplets, and BPR 𝑏 the batch version of the model which consists in finding the model parameters 𝜔 = (U, V) by minimizing the global ranking loss over all the set of triplets simultaneously (Eq. 4.1).

• Prod2Vec [START_REF] Grbovic | E-commerce in your inbox: Product recommendations at scale[END_REF], learns the representation of items using a Neural Networks based model, called word2vec [Mikolov et al., 2013a], and performs next-items recommendation using the similarity between the representations of items.

• GRU4Rec+ [START_REF] Hidasi | Recurrent neural networks with top-k gains for session-based recommendations[END_REF] is an extended version of GRU4Rec [Hidasi et al., 2016a] adopted to different loss functions, that applies recurrent neural network with a GRU architecture for session-based recommendation. The approach considers the session as the sequence of clicks of the user that depends on all the previous ones for learning the model parameters by optimizing a regularized approximation of the relative rank of the relevant item which favors the preferred items to be ranked at the top of the list.

• Caser [Tang and Wang, 2018a] is a CNN based model that embeds a sequence of interactions into a temporal image and latent spaces and find local characteristics of the temporal image using convolution filters.

• SASRec [START_REF] Kang | Self-attentive sequential recommendation[END_REF] uses an attention mechanism to capture long-term semantics and then predicts the next item to present based on a user's action history.

Hyper-parameters of different models and the dimension of the embedded space for the representation of users and items; as well as the regularisation parameter over the norms of the embeddings for BPR, BPR 𝑏 , MF, Caser and SAROS approaches were found by cross-validation. We fixed 𝑏 and 𝐵, used in SAROS, to respectively the minimum and the average number of blocks found on the training set of each corresponding collection. With the average number of blocks being greater than the median on all collections, the motivation here is to consider the maximum number of blocks by preserving the model from the bias brought by the too many interactions of the very few number of users. For more details regarding the exact values for the parameters, see the Table 4 These results suggest that the local ranking between preferred and no-preferred items present in the blocks of the training set reflects better the preference of users than the ranking of random pairs of items or their global ranking without this contextual information. Furthermore, as in SAROS updates occur after the creation of a block, and that the most of the blocks contain very few items (Figure 4-2 -right), weights are updated more often than in BPR or BPR 𝑏 . This is depicted in Figure 4-3 which shows the evolution of the training error over time for BPR 𝑏 , BPR and SAROS on all collections. As we can see, the training error decreases in all cases, and theoretically, the three approaches converge to the same minimizer of the ranking loss (Eq. 4.1). However, the speed of convergence is much faster with SAROS. We also compare the performance of all the approaches on the basis of the common ranking metrics, which are the Mean Average Precision at rank 𝐾 (MAP@K) over all users defined as MAP@K = 1 𝑁 ∑ 𝑁 𝑢=1 AP@K(𝑢), where AP@K(𝑢) is the average precision of preferred items of user 𝑢 in the top 𝐾 ranked ones; and the Normalized Discounted Cumulative Gain at rank 𝐾 (NDCG@K) that computes the ratio of the obtained ranking to the ideal case and allow to consider not only binary relevance as in Mean Average Precision, NDCG@K = 1 𝑁 ∑ 𝑁 𝑢=1 DCG@K(𝑢) IDCG@K(𝑢) , where DCG@K(𝑢) = 1+𝑖) , 𝑟𝑒𝑙 𝑖 is the graded relevance of the item at position 𝑖; and IDCG@K(𝑢) is DCG@K(𝑢) with an ideal ordering equals to et al., 2008]. Table 4.6: Comparison between MostPop, Prod2Vec, MF, BPR 𝑏 , BPR, GRU4Rec+, SASRec, Caser and SAROS approaches in terms of MAP@5 and MAP@10(top), and NDCG@5 and NDCG@10(down). Best performance is in bold and the second best is underlined.

∑ 𝐾 𝑖=1 2 𝑟𝑒𝑙 𝑖 -1 log 2 (
∑ 𝐾 𝑖=1 1 log 2 (1+𝑖) for 𝑟𝑒𝑙 𝑖 ∈ [0, 1] [Schutze
Table 4.6 presents MAP@5 and MAP@10 (top), and NDCG@5 and NDCG@10 (down) of all approaches over the test sets of the different collections. The non-machine learning method, MostPop, gives results of an order of magnitude lower than the learning based approaches. Moreover, the factorization model MF which predicts clicks by matrix completion is less effective when dealing with implicit feedback than ranking based models especially on large datasets where there are fewer interactions. We also found that embeddings found by ranking based models, in the way that the user preference over the pairs of items is preserved in the embedded space by the dot product, are more robust than the ones found by Prod2Vec. When comparing GRU4Rec+ with BPR that also minimizes the same surrogate ranking loss, the former outperforms it in case of Kasandr with a huge imbalance between positive and negative interactions. This is mainly because GRU4Rec+ optimizes an approximation of the relative rank that favors interacted items to be in the top of the ranked list while the logistic ranking loss, which is mostly related to the Area under the ROC curve [START_REF] Usunier | A datadependent generalisation error bound for the auc[END_REF], pushes up clicked items for having good ranks in average. However, the minimization of the logistic ranking loss over blocks of very small size pushes the clicked item to be ranked higher than the no-clicked ones in several lists of small size and it has the effect of favoring the clicked item to be at the top of the whole merged lists of items. Moreover, it comes out that SAROS is the most competitive approach, performing better than other approaches over all collections. It also should be noticed the effectiveness of the usage of both kind of feedback information, where both SAROS and BPR outperformed even such as last published popular approaches Caser, GRU4Rec+ and SASRec that used only positive feedback in training the predictions.

Conclusion

In this chapter, we first proposed SAROS, a novel learning framework for large-scale Recommender Systems that sequentially updates the weights of a ranking function user by user over blocks of items ordered by time where each block is a sequence of negative items followed by a last positive one. The main hypothesis of the approach is that the preferred and no-preferred items within a local sequence of user interactions express better the user preference than when considering the whole set of preferred and no-preferred items independently one from another. The approach updates the model parameters user per user over blocks of items constituted by a sequence of unclicked items followed by a clicked one. The parameter updates are discarded for users who interact very little or a lot with the system. The second contribution is a theoretical analysis of the proposed approach which bounds the deviation of the ranking loss concerning the sequence of weights found by the algorithm and its minimum in the case where the loss is convex. Empirical results conducted on five real-life implicit feedback datasets support our founding and show that the proposed approach is significantly faster than the common batch and online optimization strategies that consist in updating the parameters over the whole set of users at each epoch, or after sampling random pairs of preferred and no-preferred items. The approach is also shown to be highly competitive concerning state of the art approaches on MAP and NDCG measures.

The rest of this chapter is organized as follows. Section 5.2 introduces the general ranking learning problem that we address in this study. Then, in Section 5.2.2, we present both versions of the SAROS algorithm, SAROS 𝑏 and SAROS 𝑚 , and provide an analysis of their convergence. Section 5.4 presents experimental results that support our approach. In Section 5.3 we introduce a strategy to filter the dataset with respect to homogeneity of the behavior in the users when interacting with the system, based on the concept of memory. Finally, in Section 5.5, we discuss the outcomes of this study and give some pointers to further research.

Framework and Problem Setting

A key point in recommendation is that user preferences for items are largely determined by the context in which they are presented to the user. A user may prefer (or not) two items independently of one another, but he or she may have a totally different preference for these items within a given set of shown items. This effect of local preference is not taken into account by randomly sampling triplets formed by a user and corresponding clicked and unclicked items over the entire set of shown items to the user. Furthermore, triplets corresponding to different users are non uniformly distributed, as interactions vary from one user to another one, and for parameter updates; triplets corresponding to low interactions have a small chance to be chosen. In order to tackle these points; in chapter 4 SAROS was suggested to update the parameters sequentially.

Two strategies of SAROS

Note that this is different from session-based recommendations [START_REF] Wang | A survey on session-based recommender systems[END_REF] in which each session is also made up of a series of user-item interactions that take place over a period of time. However, session-based recommendations approaches capture both user's short-term preference from recent sessions and the preference dynamics representing the change of preferences from one session to the next by using each session as the basic input unit, which is not the case in our study.

We propose two strategies for the minimization of (Eq. 4.3, ch. 4) and the update of weights. In the first one, referred to as SAROS 𝑚 , the aim is to carry out an effective minimization of the ranking loss (4.3) by lessening the oscillations of the updates through the minimum. This is done by defining the updates as the linear combination of the gradient of the loss of (Eq. 4.3), ∇ ̂ ℒ ℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 ), and the previous update as in the momentum technique at each iteration 𝑡 :

𝑣 𝑡+1 𝑢 = 𝜇 • 𝑣 𝑡 𝑢 + (1 -𝜇)∇ ̂ ℒ ℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 ) (5.1) 𝜔 𝑡+1 𝑢 = 𝜔 𝑡 𝑢 -𝛼𝑣 𝑡+1 𝑢 (5.2)
where 𝛼 and 𝜇 are hyperparameters of the linear combination. In order to explicitly take into account bot attacks -in the form of excessive clicks over some target items

Convergence Analysis

The proofs of algorithms' convergence are given under a common hypothesis that the sample distribution is not instantaneously affected by learning of the weights, i.e. the samples can be considered as i.i.d. More precisely, we assume the following hypothesis. for some parameters 𝜎 > 0 and 𝑎 ∈ [0, 1/2) independent of 𝑢 and 𝑡.

The first assumption is common in stochastic optimization and it implies consistency of the sample average approximation of the gradient. However, this assumption is not sufficient to prove the convergence because of interdependency of different blocks of items for the same user.

The second assumption implies that in the neighborhood of the optimal point, we have ∇ℒ(𝜔 𝑡 𝑢 ) ⊤ ∇ Lℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 ) ≈ ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 , which greatly helps to establish consistency and convergence rates for both variants of the methods. In particular, if an empirical estimate of the loss over a block is unbiased, e.g. E ℬ 𝑡 𝑢 ∇ Lℬ 𝑡 𝑢 (𝜔) = ∇ℒ(𝜔), the second assumption is satisfied with 𝑎 = 0.

The following theorem establishes the convergence rate for the SAROS 𝑏 algorithm.

Theorem 5 Let ℓ be a (possibly non-convex) 𝛽-smooth loss function. Assume, moreover, that the number of interactions per user belongs to an interval [𝑏, 𝐵] almost surely and assumption 2 is satisfied with some constants 𝜎 2 and 𝑎, 0 < 𝑎 < 1/2. Then, for a step-size policy 𝜂 𝑡 𝑢 ≡ 𝜂 𝑢 with 𝜂 𝑢 ≤ 1/(𝐵𝛽) for any user 𝑢, one has

min 𝑢: 1≤𝑢≤𝑁 E‖∇ℒ(𝜔 0 𝑢 )‖ 2 2 ≤ 2(ℒ(𝜔 0 1 ) -ℒ(𝜔 0 𝑢 )) + 𝛽𝜎 2 ∑ 𝑁 𝑢=1 ∑ |ℬ𝑢| 𝑡=1 (𝜂 𝑡 𝑢 ) 2 ∑ 𝑁 𝑢=1 ∑ |ℬ𝑢| 𝑡=1 𝜂 𝑡 𝑢 (1 -𝑎 2 -𝛽𝜂 𝑡 𝑢 (1/2 -𝑎 2 ))
.

(5.4)

In particular, for a constant step-size policy

𝜂 𝑡 𝑢 = 𝜂 = 𝑐/ √ 𝑁 satisfies 𝜂𝛽 ≤ 1, one has min 𝑡,𝑢 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 ≤ 2 𝑏(1 -4𝑎 2 ) 2(ℒ(𝜔 0 1 ) -ℒ(𝜔 * ))/𝑐 + 𝛽𝑐𝜎 2 𝐵 √ 𝑁 .
Proof. Since ℓ is a 𝛽 smooth function, we have for any 𝑢 and 𝑡:

ℒ(𝜔 𝑡+1 𝑢 ) ≤ ℒ(𝜔 𝑡 𝑢 ) + ⟨∇ℒ(𝜔 𝑡 𝑢 ), 𝜔 𝑡+1 𝑢 -𝜔 𝑡 𝑢 ⟩ + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 ‖∇ Lℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 )‖ 2 2 = ℒ(𝜔 𝑡 𝑢 ) -𝜂 𝑡 𝑢 ⟨∇ℒ(𝜔 𝑡 𝑢 ), ∇ Lℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 )⟩ + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 ‖∇ Lℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 )‖ 2 2
Following [Lan, 2020]; by denoting 𝛿 𝑡 𝑢 = ∇ Lℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 ) -∇ℒ(𝜔 𝑡 𝑢 ), we have:

ℒ(𝜔 𝑡+1 𝑢 ) ≤ ℒ(𝜔 𝑡 𝑢 ) -𝜂 𝑡 𝑢 ⟨∇ℒ(𝜔 𝑡 𝑢 ), ∇ℒ(𝜔 𝑡 𝑢 ) + 𝛿 𝑡 𝑢 ⟩ + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 ‖∇ℒ(𝜔 𝑡 𝑢 ) + 𝛿 𝑡 𝑢 ‖ 2 2 = ℒ(𝜔 𝑡 𝑢 ) + 𝛽(𝜂 𝑡 𝑢 ) 2 2 ‖𝛿 𝑡 𝑢 ‖ 2 2 - ( 𝜂 𝑡 𝑢 - 𝛽(𝜂 𝑡 𝑢 ) 2 2 ) ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 - ( 𝜂 𝑡 𝑢 -𝛽(𝜂 𝑡 𝑢 ) 2 ) ⟨∇ℒ(𝜔 𝑡 𝑢 ), 𝛿 𝑡 𝑢 ⟩ (5.5)
Our next step is to take the expectation on both sides of inequality (5.5). According to Assumption 2, one has for some 𝑎 ∈ [0, 1/2):

( 𝜂 𝑡 𝑢 -𝛽(𝜂 𝑡 𝑢 ) 2 ) ⃒ ⃒ E⟨∇ℒ(𝜔 𝑡 𝑢 ), 𝛿 𝑡 𝑢 ⟩ ⃒ ⃒ ≤ ( 𝜂 𝑡 𝑢 -𝛽(𝜂 𝑡 𝑢 ) 2 ) 𝑎 2 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 ,
where the expectation is taken over the set of blocks and users seen so far.

Finally, taking the same expectation on both sides of inequality (5.5), it comes:

ℒ(𝜔 𝑡+1 𝑢 ) ≤ ℒ(𝜔 𝑡 𝑢 ) + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 E‖𝛿 𝑡 𝑢 ‖ 2 2 -𝜂 𝑡 𝑢 (1 -𝛽𝜂 𝑡 𝑢 /2 -𝑎 2 |1 -𝛽𝜂 𝑡 𝑢 |)‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 ≤ ℒ(𝜔 𝑡 𝑢 ) + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 E‖𝛿 𝑡 𝑢 ‖ 2 2 -𝜂 𝑡 𝑢 (1 -𝑎 2 -𝛽𝜂 𝑡 𝑢 (1/2 -𝑎 2 )) ⏟ ⏞ :=𝑧 𝑡 𝑢 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 = ℒ(𝜔 𝑡 𝑢 ) + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 E‖𝛿 𝑡 𝑢 ‖ 2 2 -𝜂 𝑡 𝑢 𝑧 𝑡 𝑢 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 ≤ ℒ(𝜔 𝑡 𝑢 ) + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 𝜎 2 -𝜂 𝑡 𝑢 𝑧 𝑡 𝑢 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 , ( 5
∑ |ℬ𝑢| 𝑡=1 (𝜂 𝑡 𝑢 ) 2 𝜎 2 ∑ 𝑁 𝑢=1 ∑ |ℬ𝑢| 𝑡=1 𝜂 𝑡 𝑢 (1 -𝑎 2 -𝛽𝜂 𝑡 𝑢 (1/2 -𝑎 2 ))
Where, 𝜔 * is the optimal point. Then, using a constant step-size policy, 𝜂 𝑡 𝑢 = 𝜂, and the bounds on a block size, 𝑏 ≤ |ℬ 𝑢 | ≤ 𝐵, we get:

min 𝑡,𝑢 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 ≤ ℒ(𝜔 0 1 ) -ℒ(𝜔 * ) + 𝛽𝜎 2 2 𝐵 ∑ 𝑁 𝑢=1 𝜂 2 𝑏 ∑ 𝑁 𝑢=1 𝜂(1 -𝑎 2 -𝛽𝜂(1/2 -𝑎 2 )) ≤ 4ℒ(𝜔 0 1 ) -4ℒ(𝜔 * ) + 2𝛽𝜎 2 𝐵 ∑ 𝑁 𝑢=1 𝜂 2 𝑏(1 -4𝑎 2 ) ∑ 𝑁 𝑢=1 𝜂 ≤ 2 𝑏(1 -4𝑎 2 ) { 2ℒ(𝜔 0 1 ) -2ℒ(𝜔 * ) 𝑁 𝜂 + 𝛽𝜎 2 𝐵𝜂 } .
Taking 𝜂 = 𝑐/ √ 𝑁 so that 0 < 𝜂 ≤ 1/𝛽, one has

min 𝑡,𝑢 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 ≤ 2 𝑏(1 -4𝑎 2 ) 2(ℒ(𝜔 0 1 ) -ℒ(𝜔 * ))/𝑐 + 𝛽𝑐𝜎 2 𝐵 √ 𝑁 .
If 𝑏 = 𝐵 = 1, this rate matches up to a constant factor to the standard 𝑂(1/ √ 𝑁 ) rate of the stochastic gradient descent.

Note that the stochastic gradient descent strategy implemented in the Bayesian Personalized Ranking model (BPR) [START_REF] Rendle | BPR: Bayesian personalized ranking from implicit feedback[END_REF]] also converges to the minimizer of the ranking loss ℒ(𝜔) (Eq. 2.18) with the same rate.

The analysis of momentum algorithm SAROS 𝑚 is slightly more involved. We say that a function 𝑓 (𝑥) satisfies the Polyak-Łojsievich condition [Polyak, 1963, Lojasiewicz, 1963, Karimi et al., 2016] if the following inequality holds for some 𝜇 > 0:

1 2 ‖∇𝑓 (𝑥)‖ 2 2 ≥ 𝜇(𝑓 (𝑥) -𝑓 * ),
where 𝑓 * is a global minimum of 𝑓 (𝑥).

From this definition, we can derive an analysis on the convergence of SAROS 𝑚 stated below.

ℒ(𝜔 𝑡+1 𝑢 ) -ℒ(𝜔 * ) ≤ exp(-𝜇𝜂𝑁 )(ℒ(𝜔 0 1 ) -ℒ(𝜔 * )) + 𝛽𝜎 2 𝜂 2 2(1 -𝜇/𝛽) , 𝜂𝛽 ≤ 1.
where the estimation is uniform for all 𝑎, 0 ≤ 𝑎 < 1/2.

In particular, if 𝜂 = 𝑐/ √ 𝑁 , under the same conditions one has

ℒ(𝜔 𝑡 𝑢 ) -ℒ(𝜔 * ) ≤ exp(-𝜇𝑐 √ 𝑁 )(ℒ(𝜔 0 1 ) -ℒ(𝜔 * )) + 𝛽𝜎 2 𝑐 2 2(1 -𝜇/𝛽)𝑁 .
Proof. Similarly to the Theorem 5, From Ineq. (5.6) we have:

ℒ(𝜔 𝑡+1 𝑢 ) ≤ ℒ(𝜔 𝑡 𝑢 ) + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 𝜎 2 -𝜂 𝑡 𝑢 𝑧 𝑡 𝑢 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 for 𝑧 𝑡 𝑢 = 1 -𝑎 2 -𝛽𝜂 𝑡 𝑢 (1/2 -𝑎 2 ) > 0.
Further, using the Polyak-Lojasievich condition, it comes:

-𝜂 𝑡 𝑢 𝑧 𝑡 𝑢 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 ≤ -2𝜇𝜂 𝑡 𝑢 𝑧 𝑡 𝑢 (ℒ(𝜔 𝑡 𝑢 ) -ℒ(𝜔 * )), and
ℒ(𝜔 𝑡+1 𝑢 ) -ℒ(𝜔 * ) ≤ ℒ(𝜔 𝑡 𝑢 ) -ℒ(𝜔 * ) + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 𝜎 2 -2𝜇𝜂 𝑡 𝑢 𝑧 𝑡 𝑢 (ℒ(𝜔 𝑡 𝑢 ) -ℒ(𝜔 * )) ≤ (ℒ(𝜔 𝑡 𝑢 ) -ℒ(𝜔 * ))(1 -2𝜇𝜂 𝑡 𝑢 𝑧 𝑡 𝑢 ) + 𝛽 2 (𝜂 𝑡 𝑢 ) 2 𝜎 2 ≤ ∏ 𝑢 ∏ 𝑡 (1 -2𝜇𝜂 𝑡 𝑢 𝑧 𝑡 𝑢 )(ℒ(𝜔 0 1 ) -ℒ(𝜔 * )) + 𝛽𝜎 2 2 ∑ 𝑣≤𝑢 (𝜂 𝑡 𝑣 ) 2 ∏ 𝑣 ∏ 𝑡 (1 -2𝜇𝜂 𝑡 𝑣 𝑧 𝑡 𝑣 )
Finally, for a constant step-size policy, 𝜂 𝑡 𝑢 = 𝜂, one has 𝑧 𝑡 𝑢 = 𝑧 = 1-𝑎 2 -𝛽𝜂(1/2-𝑎 2 ) and

ℒ(𝜔 𝑡+1 𝑢 ) -ℒ(𝜔 * ) ≤ (1 -2𝜇𝜂𝑧) 𝑁 (ℒ(𝜔 0 1 ) -ℒ(𝜔 * )) + 𝛽𝜎 2 𝜂 2 2(1 -2𝜇𝜂𝑧) ,
where the last term is given by summing the geometric progression. As 𝛽𝜂 ≤ 1 and 𝑎 < 1/2 one has 𝑧 ≥ 1/2. Thus

ℒ(𝜔 𝑡+1 𝑢 ) -ℒ(𝜔 * ) ≤ (1 -𝜇𝜂) 𝑁 (ℒ(𝜔 0 1 ) -ℒ(𝜔 * )) + 𝛽𝜎 2 𝜂 2 2(1 -𝜇/𝛽) ≤ exp(-𝜇𝜂𝑁 )(ℒ(𝜔 0 1 ) -ℒ(𝜔 * )) + 𝛽𝜎 2 𝜂 2 2(1 -𝜇/𝛽) , 𝜂𝛽 ≤ 1.
Taking 𝜂 = 𝑐/ √ 𝑁 for some positive 𝑐 guarantees a rate of convergence 𝑂(1/𝑁 ). With a different choice of the step-size policy, rates almost up to 𝑂(1/𝑁 2 ) are possible; however, these rates imply 𝑂(1/𝑁 ) convergence for the norm of the gradient which matches the standard efforts of stochastic gradient descent under the Polyak-Lojasievich condition [START_REF] Karimi | Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition[END_REF].

Recommender systems: when memory matters

In this section, we put in evidence (𝑎) the impact of homogeneous user/items interactions for prediction, after removal of non-stationarities and (𝑏) the need of designing specific strategies to remove non-stationarities due to a specificity of RS, namely the presence of memory in user/items interactions. Thereafter, we turn this preliminary study into a novel and successful strategy combining sequential learning per blocks of interactions and removing user with non-homogeneous behavior from the training.

In the following, we present the mathematical framework, used to model stationarity in RS data. Thereafter, we explain that in the case, where we have presence of longmemory in the data removing non-stationarites is specially tricky. We present our novel strategy combining the efficiency of sequential learning per block of interactions and the knowledge of the memory behavior of each user to remove non-stationarities. We then illustrate that memory is intrinsically present in RS user/items interactions and that we have to take it into account to remove non-stationarities and improve generalization. We then prove through experiments on different large-scale benchmarks the effectiveness of our approach.

Stationarity

Our claim is that all user/items interactions may not be equally relevant in the learning process. We prove in the sequel that we can improve the learning process, considering only the subset of users whose interactions with the system are homogeneous in time, meaning that the user feedback is statistically the same, whatever the time period is. Unfortunately, non-stationarities are not easy to detect, since we have to take into account another additional effect in RS, which is long-range dependence. Indeed, in RS the choice of a given user may be influenced not only by its near past but by the whole history of interactions. We propose to model these two natural characteristics of user feedbacks, using two mathematical notions introduced for sequential data analysis : stationarity and memory. We recall that a time series 𝑋 = {𝑋 𝑡 , 𝑡 ∈ Z}, here the sequence of user's feedback, is said to be (wide-sense) stationary (see Section 2.4 in [Brillinger, 2001]) if its two first orders moments are homogeneous with time: ∀𝑡, 𝑘, 𝑙 ∈ Z, E[𝑋 𝑡 ] = 𝜇, and 𝐶𝑜𝑣(𝑋 𝑘 , 𝑋 𝑙 ) = 𝐶𝑜𝑣(𝑋 𝑘+𝑡 , 𝑋 𝑙+𝑡 )

(5.7)

Under such assumptions the autocovariance of a stationary process only depends on the difference between the terms of the series ℎ = 𝑘 -𝑙. We set 𝛾(ℎ) = 𝐶𝑜𝑣(𝑋 0 , 𝑋 ℎ ).

Our other concept of interest, memory arouses in time series analysis to model memory that can be inherently present in sequential data. It provides a quantitative measure of the persistence of information related to the history of the time series in the long-run and it can be related to presence of non-stationarities in the data. Its definition is classically done in the Fourier domain and is based on the so-called spectral density. The spectral density is the discrete Fourier transform of the autocovariance function : .8) and reflects the energy contains at each frequency 𝜆 if the times series. A time series 𝑋 admits memory parameter 𝑑 ∈ R iff its spectral density satisfies :

𝑓 (𝜆) = 1 2𝜋 +∞ ∑ ℎ=-∞ 𝛾(ℎ)𝑒 -𝑖ℎ𝜆 , 𝜆 ∈ (-𝜋, 𝜋]. ( 5
𝑓 (𝜆) ∼ 𝜆 -2𝑑 as 𝜆 → 0 .

(5.9)

Memory

In the time domain, the memory parameter is related to the decay of the autocovariance function. The more it is large, the more the past of the time series has an impact on its next future. Interestingly, when the memory parameter is large, the time series tends to have a sample autocorrelation function with large spikes at several lags which is well known to be the signature of non-stationarity for many practitioners. It can then be used as a measure of non-stationarity.

In order to infer this memory parameter, we use one of the most classical estimators of the memory parameter, the GPH estimator introduced in [START_REF] Geweke | The estimation and application of long memory time series model[END_REF]. It consists of a least square regression of the log-periodogram of 𝑋. One first defines a biased estimator of the spectral density function, the periodogram 𝐼(𝜆) and evaluate it on the Fourier frequencies 𝜆 𝑘 = 2𝜋𝑘 𝑁 where 𝑁 is the length of the sample :

𝐼 𝑁 (𝜆 𝑘 ) = 1 𝑁 ⃒ ⃒ ⃒ ⃒ ⃒ 𝑁 ∑ 𝑡=1 𝑋 𝑡 𝑒 𝑖𝑡𝜆 𝑘 ⃒ ⃒ ⃒ ⃒ ⃒ 2 (5.10)
The estimator of the memory parameter is therefore as follows : .11) where

d(𝑚) = ∑ 𝑚 𝑘=1 (𝑌 𝑘 -Ȳ ) log(𝐼(𝜆 𝑘 )) ∑ 𝑚 𝑘=1 (𝑌 𝑘 -Ȳ ) 2 , ( 5
𝑌 𝑘 = -2 log |1 -𝑒 𝑖𝜆 𝑘 |, Ȳ = ( ∑ 𝑚 𝑘=1 𝑌 𝑘 )/𝑚
and 𝑚 is the number of used frequencies.

We then classify the time series as non-stationary if 𝑑 ≥ 1/2, and as stationary otherwise.

The inclusion of the Memory-Aware step of our algorithm, allowing to include stationarity in the pipeline (called MOSAIC), can be carried out in two steps. In the first step we train SAROS on the full dataset. Thereafter we remove non-stationary embeddings, using a preliminary estimation of the memory parameter of each time series. Finally we train once more this filtered dataset and return the last updated weights.

Experimental Setup and Results

The group of the experiments was expanded to a new dataset RecSys'16compared to the one of the chapter 4. The dataset represents a sample based on historic XING data provided 6,330,562 feedback given by 39,518 users on the job posting items and the items generated by XING's job recommender system. Updated statistics for RecSys'16 are represented in table 5 Compared Approaches.

To estimate both strategies of sequential learning approach SAROS 𝑚 and SAROS 𝑏 , we compared them with the same state-of-the-art approaches suggested in chapter 4, section 4.5. The set of baselines was extended by the modern graph-convolution-based model LightGCN proposed by [START_REF] He | LightGCN: Simplifying and powering graph convolution network for recommendation[END_REF]. This graph convolution network learns user and item embedding by linearly propagating them on the user-item interaction graph. The final representations are the weighted sum of the embeddings learned at all layers.

Hyper-parameters of LightGCN and the dimension of the embedded space for the representation of users and items; as well as the regularisation parameter over the norms of the embeddings for all approaches were found using grid search on the validation set as before for the remains benchmarks. Supplemented information with the adjusted number of blocks and learnig rate involving the new RecSys'16 is summarized below in the table 5 As we can see, the training error decreases in all cases and the three approaches converge to the same minimizer of the ranking loss (Eq. 2.18). This is an empirical evidence of the convergence of SAROS 𝑏 and SAROS 𝑚 , showing that the sequence of weights found by the proposed algorithm allows to minimize the general ranking loss (Eq. 2.18) as it is stated in Theorems 1 and 2.

To estimate the importance of the maximum number of blocks (𝐵) for SAROS 𝑏 , we explore the dependency between quality metrics MAP@K and NDCG@K on ML-1M and Pandor collections (Figure 5-2). The latter records the clicks generated by users on one of Purch's high-tech website and it was subject to bot attacks [START_REF] Sidana | Learning to recommend diverse items over implicit feedback on PANDOR[END_REF]. For this collection, large values of 𝐵 affects MAP@K while the measure reaches a plateau on ML-1M. The choice of this hyperparameter may then have an impact on the results. As future work, we are investigating the modelling of bot attacks by studying the effect of long memory in the blocks of no-preferred and preferred items in small and large sessions with the aim of automatically fixing this threshold 𝐵. Table 5.5 presents full set of results for NDCG@5 and NDCG@10, and MAP@5 and MAP@10 of all approaches over the test sets including RecSys'16 of the different collections.

With respect to the updated table 5.5, results justify the power of the proposed approach. Even the comparison of SAROS with modern LightGCN shows very promising results. LightGCN also is trained on the triplets but it sampled negative interactions from all set of items for positive interactions, that's why in case of very imbalanced Table 5.5: Comparison between MostPop, Prod2Vec, MF, BPR 𝑏 , BPR, GRU4Rec+, SASRec, Caser, and SAROS approaches in terms of NDCG@5 and NDCG@10(top), and MAP@5 and MAP@10(down). Best performance is in bold and the second best is underlined. dataset, such as Kasandr, the model has so big improvement under SAROS (because when the number of positive interactions is very small we almost for sure will sample negative). But if the data is not so imbalanced with respect to the number of positive/negative interactions, our approach is better because the sampling in LightGCN for this case will bring the noise to the data.

Identifying stationary users. We keep only users whose embeddings have four stationary components, using a preliminary estimation of the memory parameter. In table 5.6 it could be found that the output subset is much smaller for Kassandr and Pandor than the full dataset whereas for ML-1M and Outbrain we succeed in keeping a large part of the full dataset. Our filtering approach is then expected to be more successful on the latter. 5.7: Comparison of different models in terms of MAP@5 and MAP@10(top), and NDCG@5 and NDCG@10(down).

Data

sequence models behave generally better. Furthermore, compared to Caser and GRU4Rec which only consider the positive feedback; our approach which takes into account positive interactions with respect to negative ones performs better.

Furthermore, as suspected results on Outbrain and ML are better with MOSAIC than SAROS in these collections than the two other ones due to the fact that we have more LRD users. Keeping only in the dataset, stationary users, for which the behavior is consistent with time, is an effective strategy in learning recommender systems. The predictable nature of the behavior of stationary users makes the sequence of their interactions much exploitable than those of generic users, who may be erratic in their feedback and add noise in the dataset.

Conclusion

In this chapter, we presented two variants of the SAROS approach presented in chapter 4; in the first model parameters are updated user per user over blocks of items constituted by a sequence of unclicked items followed by a clicked one. The parameter updates are discarded for users who interact very little or a lot with the system. The second variant, is based on the momentum technique as a means of damping oscillations. The second contribution is a theoretical analysis of the proposed approach which bounds the deviation of the ranking loss concerning the sequence of weights found by both variants of the algorithm and its minimum in the general case of non-convex ranking loss. Empirical results conducted on six real-life implicit feedback datasets support our founding and show that the proposed approach is significantly faster than the common batch and online optimization strategies that consist in updating the parameters over the whole set of users at each epoch, or after sampling random pairs of preferred and no-preferred items. The approach is also shown to be highly competitive concerning state of the art approaches on MAP and NDCG measures.

In addition, we introduced a strategy to filter the dataset with respect to homogeneity of the behavior in the users when interacting with the system, based on the concept of memory. From our results, it comes out that taking into account the memory in the case where the collection exhibits long range dependency allows to enhance the predictions of the proposed sequential model. As future work, we propose to encompass the analysis of LRD and the filtering phase in the training process.

Chapter 6

Faulted Lines Detection with ranking-based approach

Introduction

The climate change and global warming results in an increased number of extreme weather events [START_REF] Sillmann | Indices for extreme events in projections of anthropogenic climate change[END_REF] that compromises security and reliability of critical infrastructure (power and gas grids, telecommunications, transportation systems) [START_REF] Birkmann | Extreme events, critical infrastructures, human vulnerability and strategic planning: Emerging research issues[END_REF]. According to the recent statistics of the National Center for Environmental Information1 , the total cost of 310 recent major weather events exceeds $2.155 trillion dollars and projected to increase in the near future [START_REF] Smith | Us billion-dollar weather and climate disasters: data sources, trends, accuracy and biases[END_REF]. Power grids are responsible for a substantial part of this cost [START_REF] Stern | The economics of climate change: the Stern review[END_REF].

One of the major challenges in protecting a grid from impending a cascading blackout after a line failure is a real-time localization of the faulted line followed activating emergency controls [START_REF] Begovic | Wide-area protection and emergency control[END_REF][START_REF] Zhang | Remedial action schemes and defense systems[END_REF]. Traditional data-driven methods for fault localization, such as travelling-wave [START_REF] Parsi | Wavelet based fault location on power transmission lines using real-world travelling wave data[END_REF] and impedance based ones [START_REF] Aucoin | High impedance fault detection implementation issues[END_REF], require high grid observability and sampling rates that are technically challenging and expensive for bulky systems [START_REF] Sundararajan | Survey on synchrophasor data quality and cybersecurity challenges, and evaluation of their interdependencies[END_REF] or even known distribution of renewables [START_REF] Owen | Importance sampling the union of rare events with an application to power systems analysis[END_REF], Lukashevich et al., 2021, Lukashevich and Maximov, 2021]. Another line of algorithms leverages deep neural networks capabilities [START_REF] Li | Real-time faulted line localization and pmu placement in power systems through convolutional neural networks[END_REF], Li and Deka, 2021a, Zhang et al., 2020a, Misyris et al., 2020]; however, these methods suffer from high requirements on the amount of phasor-measurement unit data. The latter lead to inability to make a accurate and timely detection in time-changing environment that is intrinsic for extreme weather events and, therefore, compromises power grid security.

The chapter addresses power grid reliability during extreme events, such as wildfires, hurricanes and extreme winds, when multiple line failures may happen. The latter failures must be detected in real-time to preserve secure and reliable operations and prevent the grid from impending energy blackout. The most common failure type is a line failure, when power supply through a specific line (lines) is interrupted for a few seconds or permanently.

Contribution. Our contribution is as follows. First, we propose Topology-Aware failure Localization Detector (TALD), a neural-network based algorithm for detecting line faults in real-time. A particular advantage of our approach, that lead to a higher detection accuracy and lower data requirements, is leveraging grid topology information.

Second, the algorithm estimates the conditional probability that the fault has happened on this line. This allows not only estimate the detection confidence, but also efficiently utilize prior information on line vulnerability. The latter is often accessible for power grid operators as a result of earlier failures or maintenance information.

Finally, we provide empirical support for TALD showing its superior performance over simulated data.

Chapter structure. The chapter is organized as follows. Section 6.2 contains problem setup and provides necessary background information. Section 6.3 provides empirical results and discussion about it's role. Short conclusion is given in Section 6.4.

Problem Statement

Notation.

Let 𝐸, |𝐸| = 𝑚, be a set of lines and 𝑉 , |𝑉 | = 𝑛, is a set of buses in a power grid 𝐺 = ⟨𝑉, 𝐸⟩. Let 𝑝, 𝑞 ∈ R 𝑛 be vectors of active and reactive power, 𝑣 ∈ R 𝑛 be a vector of voltage magnitudes, and 𝜃 ∈ R 𝑛 be a vector of voltage phases. We denote phase angle differences as 𝜃 𝑖𝑗 , (𝑖, 𝑗) ∈ 𝐸. Power grid buses consist of PQ (load) buses, PV (generation) buses, and a slack bus that often stands for the largest and slowest generator in the grid. We assume below that the phase angle 𝜃 𝑖 = 0 for the slack bus 𝑖. given below at the Eq. 6.2:

𝐸

𝐶𝐸(𝑦, 𝑓 (𝜓)) = 𝑛 ∑ 𝑖=1 𝑦 𝑖 • log ( exp 𝑓 𝑖 (𝜓) ∑ 𝑛 𝑖=1 exp 𝑓 𝑖 (𝜓)
) (6.2)

Figure 6-1: Architecture of the applied model proposed in [START_REF] Li | Real-time fault localization in power grids with convolutional neural networks[END_REF].

Then, we could express the loss function more formally by the next Eq. 6.3:

𝐿𝑜𝑠𝑠(𝑦, ŷ, 𝑓 (𝜓)) = 𝐶𝐸(𝑦, 𝑓 (𝜓)) • (1 -𝜖) + 𝐶𝐸(ŷ, 𝑓 (𝜓)) • 𝜖 (6.
3)

The architecture of the baseline model presented on the Fig. 6-1 is described in details in the paper of authors [START_REF] Li | Real-time fault localization in power grids with convolutional neural networks[END_REF]]. It's suggested to use the convolutionbased neural network with the information about the bus voltages and prepared features with a physical interpretation to make the predictions about fault location. To make the model more interpretable and to improve the output accuracy we modified the loss function to the explained in the equation 6.3 by including the network topology in the model and then provide empirical evaluation of both approaches presented in section 6.3.

Experimental part

Dataset

To estimate the approaches we apply two benchmarks: SIM_LARGE and SIM_SMALL. SIM_SMALL was provided us by authors of [START_REF] Li | Real-time fault localization in power grids with convolutional neural networks[END_REF] for 68-bus power system. The second dataset SIM_LARGE we simulated in the power system toolbox, based on nonlinear models [START_REF] Chow | A toolbox for power system dynamics and control engineering education and research[END_REF], a three-phase short circuit fault lasting 0.2 seconds at the line 5-6 also in the IEEE 68-bus power system as in the SIM_SMALL. The main differences between two benchmarks are the number of samples simulated for train, test and validation sets, where the new simulated set is about 10 times bigger. The second point is that the test set for SIM_LARGE is generated simultaneously for all fault types, as the train set for both datasets, whereas in SIM_SMALL benchmark there are separate test sets for each fault. This new simulation allows us to estimate the generalization property of the model to distinguish between different fault types. Also it let us to avoid the overfitting of the model on one particular class.

The feature vector 𝜓 is computed based on the idea lies in the baseline approach [START_REF] Li | Real-time fault localization in power grids with convolutional neural networks[END_REF]. Represented by the feature vectors faulted lines in power grid are then labeled by their locations; in case of 𝑚 lines in the power grid, the number of output classes are equal to 𝑚 + 1, where additional class is for the normal condition, that means there are no faults in the system. Below the statistics regarding the size of simulated data for train, test and validation evaluations are represented in the table 6 The fault-cases provided in data are simulated by changing the line impedance, depending on the type. For simulation we consider a power grid of 𝑛 buses with a single line fault that may either be one of the following: three-phase short circuit (TP), line to ground (LG), double line to ground (DLG) and line to line (LL) faults for SIM_SMALL and LG, DLG and LL for SIM_LARGE. To characterize the location of the faults in power grid, the authors of [START_REF] Li | Real-time fault localization in power grids with convolutional neural networks[END_REF] propose to apply the substitution theory [START_REF] Jiang | An efficient pmu-based fault-location technique for multiterminal transmission lines[END_REF] for deriving the equations related to pre-and during-fault system variables to express feature vector. The feature vector 𝜓 ∈ 𝐶 𝑛×1 based on the substitution theory is defined then in terms of the bus voltages variations ∆𝑈 before and during the faults and the admittance matrix 𝑌 0 before the faults: 𝜓 = Δ𝑈 • 𝑌 0 (6.4) Admittance matrix is an 𝑛 × 𝑛 matrix describing a linear power system with 𝑛 buses. It represents the nodal admittance of the buses in a power system, where admittance is a measure of how easily a circuit or device will allow a current to flow. The general mathematical expression of each element of the admittance matrix 𝑌 𝑖𝑗 is represented as following: Where 𝑦 𝑖𝑘 is the admittance between the bus 𝑖 and another bus 𝑘 connected to 𝑖. The term 𝑦 𝑖 accounts for the admittance of linear loads connected to bus 𝑖 as well as the admittance-to-ground at bus 𝑖. To understand the distribution of generated data, we provide the statistics with respect to the size of groups regarding the number of neighbours over lines. The results of the calculated statistics are introduced in the Fig. 6-4: The ratio of SNR can take zero, positive or negative values. An SNR over 0 dB indicates that the signal level is greater than the noise level. The higher the ratio, the better the signal quality. The SNR of PMU measurements in different regions can vary. We additionally explore this parameter over the test evaluations in subsection 6.3.3 of present chapter.

Empirical Evaluation

The proposed model was trained using RMSProp optimizer and for early-stopping criteria was suggested the next one: validation loss is computed over all validation data, then if min over last 100 validation losses < best loss, where the best loss is the minimum between the current best loss and the average over the last validation losses for 100 steps, then we continue to train, otherwise -stop. All the parameters such as learning rate, batch size, ratio that responsible for how many information about the neighbours we take during the training and the remains parameters are set using cross-validation method. To estimate the model we apply accuracy measure that is defined as the relation between the number of correctly detected faulted lines and total number of faults. The first experiments are done on the small SIM_SMALL dataset over the full and partial observability cases. The partial measures are range between 15% and 30% of buses and estimated over 4 test sets for each particular fault class. The analysis of the results for two models could be find in the table 6 Based on the experiments it could be said that more measured buses improve the predictability of fault locations. Also it should be noticed that information about the grid topology also improve the final results on 2%-18% in comparison the case without taking into account the neighbours during training in the loss function.

The results of the estimation the generalisation property to distinguish the faults over different types are done on SIM_LARGE dataset and presented on the table 6.5 for range of train samples between 10 and 100 percentages with step 10. For the most cases we could see the profit for the model with neighbours topology. This results support the property of the generalisation the fault classes. For SIM_LARGE data we also provide the experiments for partial bus observations as it was done for SIM_SMALL. The results are presented in the table 6.6. What could be seen from here is that as in the table 6.4, the tendency between ratio of measured buses and accuracy is preserved; it means that more observations usually provide more accurate predictions of faulted line locations that could be explained by the bigger amount of input information provided for the model. Regarding the comparison between two models, for all ratio values topology-based model outperform the second one, that proves it's less sensitivity to the lack of information, where for the topology-based model the result sank around on 9%, where for another model it sank on 13%.

LG The test evaluations over SNR parameter are done by ranging approximation value of noise from 40dB to 100dB with the step size 10. The Gaussian noise of the same SNR was added both to the training and testing parts of datasets. The structure of the CNN was kept the same but the hyperparameter as ratio 𝜖 in Eq. 6.3 was additionally set up in the noisy regime. Other parameters are the same. Results in Fig. 6-5 indicate that the sensitivity of both models to noise is different, and that model based on neighbours topology is relatively more robust to the noise.

U-Mann-Whitney Test

Because of some instability in results from table 6.5, we suggest to compare them on the basis of statistical criterion of Mann-Whitney-Wilcoxon. The distributions of the output samples of accuracy's are illustrated on the Fig. 6-6. This U-criterion is used to assess the differences between two independent samples by the level of a feature measured quantitatively. This method determines whether the zone of overlapping values between two rows is small enough. The lower the value of the criterion, it is more likely that the differences between the parameter values in the samples are significant. U-Mann-Whitney test step-by-step:

• To make a single ranked series from both compared samples, placing their elements according to the degree of increase and assigning a lower rank to a lower value with number of elements in the first sample 𝑛 1 and 𝑛 2 in the second one.

• Divide a single ranked series into two, consisting of units of the first and second samples, respectively. Calculate separately the sum of ranks for each sample 𝑅 1 and 𝑅 2 , then calculate:

𝑈 1 = 𝑛 1 • 𝑛 2 + 𝑛 1 • (𝑛 1 + 1) 2 -𝑅 1 (6.7) 𝑈 2 = 𝑛 1 • 𝑛 2 + 𝑛 2 • (𝑛 2 + 1) 2 -𝑅 2 (6.8)
• Determine the value of the Mann-Whitney U-statistics by the formula 𝑈 = max{𝑈 1 , 𝑈 2 }.

• Using the table for the selected level of statistical significance, determine the critical value of the criterion for the data. If the resulting value of 𝑈 is greater than or equal to the tabular one, then it is recognized that there is a significant difference between the samples and an alternative hypothesis is accepted. If the resulting value of 𝑈 is less than the table value, the null hypothesis is accepted.

In our case, as null hypothesis we consider the equivalence of the mean for both samples, as alternative hypothesis we suggest that the mean of the model that takes into accounts the neighbours topology is greater than of the second one. The statistical significance, also denoted as 𝛼, is the threshold probability of rejecting the null hypothesis when it is true. 𝑝 𝑣𝑎𝑙𝑢𝑒 -is actual probability (calculated from the resulting value of 𝑈 ) of rejecting the null hypothesis when it is true. So when 𝑝 𝑣𝑎𝑙𝑢𝑒 < 𝛼, we assume that we reject the null hypothesis correctly.

The result of Mann-Whitney statistical test is presented on the Fig. 6-7 for 60% of training samples from SIM_BIG data (for all the remains ratios of the training data the test was provided by analogy and the results were the same). For the comparison, a critical region of 2𝜎 is given. The Fig. 6-7 shows that the value of p-value is significantly less than alpha, so, we reject the null hypothesis. Therefore, the mean of the model that takes into account the topology among neighbour lines in power grid exceeds the mean of the baseline model, and then we could consider obtained results as statistically significant.

For power systems operational practice, it might be beneficial to present the solution in a simple logical form [START_REF] Boros | An implementation of logical analysis of data[END_REF], Hammer and Bonates, 2006, Maximov, 2012a, Maximov, 2013[START_REF] Maximov | Simple disjunctive normal forms of boolean functions with a restricted number of zeros[END_REF] conventional for interpretation by a power system operator.

Conclusion

The problem of predicting power grid faults with a convolutional neural network is discussed in this chapter. Simulated datasets SIM_SMALL and SIM_BIG containing four and three types of errors, respectively, were used to address the problem. By improving the loss function of the previously presented model [START_REF] Li | Real-time fault localization in power grids with convolutional neural networks[END_REF], we were able to achieve the gains in the accuracy measure. We added an additional term accounting neighbor information to the loss function to account for the neighbors of the line with a failure throughout the learning phase. To evaluate the statistical significance of the suggested technique, we used a statistical Mann-Whitney test to corroborate our findings. The test validated the approach's static significance. Also the modified model demonstrates its better robustness to the noise conditions and partial observability. A similar approach can be used for analysis of power generation reliability [START_REF] Stulov | Learning model of generator from terminal data[END_REF], Mikhalev et al., 2020].

Chapter 7

Conclusion and Future Perspectives

Concluding remarks

In this thesis, the problem of ranking was considered in relation to different fields, in particular, to recommender systems and power systems. The first part and the main contribution of the thesis is devoted to recommender systems. As a solution to the problem regarding effective recommendations in the case of implicit feedback, we propose an approach SAROS [4] for effective sequential training of hidden representations of users and objects that take into account their interactions in the system. The approach uses both types of feedback, positive and negative, organized in blocks so that, according to our assumption, the algorithm pays more attention to positive interactions during training. The proposed algorithm has proven itself in practice relative to other popular approaches, where the most of them use only one type of feedback. This confirmed the importance of using both types of interaction's output, as well as the effectiveness of the proposed block structure of training. And also provided ways to improve it and speed it up. It is important to note that the proposed algorithm was theoretically justified. First we proved its convergence for the case of a convex loss function, and then we extend the theory of convergence on the general case [START_REF] Burashnikova | Learning over no-preferred and preferred sequence of items for robust recommendation[END_REF].

We also suggest the ways to speed up the algorithm in conditions of preserving the quality of predictions [START_REF] Burashnikova | Recommender systems: when memory matters[END_REF]. The proposed method considers the time series of user interactions with objects and filters out those objects that do not keep the long memory. The experiments showed that the effective part of the training data keeps memory. Thus, by filtering out users with short memory, we have preserved the high quality of the model, slashed the size of the input data, and reduced the time for processing and training them.

The second part of the thesis is mostly devoted on the practical application of ranking model in engineering systems with the contribution on the improvement of the existing model for ranking the faulted lines in power grids. We proposed to take into account the network topology and changed the loss function by adding the term that takes into account the neighbors of the broken line. By adapting this idea, we slightly improved the baseline results. Moreover, according to the Mann-Whitney statistical test, our results are statistically significant.

Future perspectives

Recommender Systems. Generally speaking, it is a quite difficult task to adapt recommendations to different data. Everything that we proposed to do on open-source data may not work in reality. This may be a problem from two sides. The first reason are users, as because their behavior may not be the same as that of those users on whom we configured the algorithm. Another side is time: even if we recommend good objects, then users will see and click only those objects that we recommend to them and it will be more profitable for the company to recommend the same objects (feedback loop task, [START_REF] Mansoury | Feedback loop and bias amplification in recommender systems[END_REF], Sinha et al., 2016]). Therefore, it would be interesting to try to run the proposed algorithm on some real data and adapt the approach to it.

Power Systems. As for power grids, it would be interesting to try graph neural networks for more advanced work with the network topology. Recently, graph neural networks have shown impressive results in the power systems tasks [START_REF] Liao | A review of graph neural networks and their applications in power systems[END_REF] due to their ability to capture dependencies in the graph-structured systems.

Chapters 4- 5 𝒟 6 𝜃

 56 Joint distribution over users and items ℐ = [𝑀 ] The set of item indexes 𝒰 = [𝑁 ] The set of user indexes ℓ 𝑢,𝑖,𝑖 ′ (𝜔) Instantaneous loss for user 𝑢 and a pair of items (𝑖, 𝑖 ′ ) ℐ - 𝑢 The set of all negative items for user 𝑢 Π 𝑡 𝑢 Positive items in block 𝑡 for user 𝑢 ℐ + 𝑢 The set of all positive items for user 𝑢 N 𝑡 𝑢 Negative items in block 𝑡 for user 𝑢  ℒ 𝑢 (𝜔) Empirical ranking loss with respect to user 𝑢 ℬ 𝑡 𝑢 𝑡-th block considered for user 𝑢 𝒟 ℬ 𝑢 Conditional distribution of blocks of positive/negative items for a fixed user 𝑢 𝒟 𝑢 Conditional distribution of items for a fixed user 𝑢 𝒟 ℬ𝑢 Conditional distribution of items for a fixed user 𝑢 and block ℬ ℒ(𝜔) Expected ranking loss of the classifier  ℒ ℬ 𝑡 𝑢 (𝜔) Empirical ranking loss with respect to a block of items Chapter Phase angles, 𝜃 ∈ R 𝑛 𝑝, 𝑞 Vector of active/reactive power injections 𝑣 Bus voltages, 𝑣 ∈ R 𝑛 nb 𝐸 (•), nb 𝑉 (•) List of adjacent edges, vertices

3 - 3

 33 The principle of convolve operation; the figure is taken from https: //classic.d2l.ai. . . . . . . . . . . . . . . . . . . . . . . . . . . . .[START_REF] Burashnikova | Apprentissage séquentiel de préférence utilisateurs pour les systèmes de recommandation[END_REF][4] The network architecture of Caser; the figure is taken from[Tang and Wang, 2018a]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-5 The principle of RNN work. The information is spread from the input to the output with some recursion on the connections between the nodes. The figure is taken from https://colah.github.io/. . . . . 3-6 Mini batches for GRU4Rec; the figure is taken from [Hidasi and Karatzoglou, 2018]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-7 The examples of bipartite graph; the figure is taken from https:// habr.com. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-8 LightGCN architecture; the figure is taken from [He et al., 2020]. . . . 3-9 The transformer architecture; the figure is taken from https:// jalammar.github.io/illustrated-transformer/. . . . . . . . . . . 3-10 SASRec training structure; the figure is taken from [Kang and McAuley, 2018]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-11 ROC curve; the figure is taken from https://medium.datadriveninvestor. com. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-1 Sequential update strategy . . . . . . . . . . . . . . . . . . . . . . . . 4-2 Statistics of Kasandr dataset . . . . . . . . . . . . . . . . . . . . . . 4-3 Loss BPR 𝑏 , BPR and SAROS as a function of time . . . . . . . . . . . . 5-1 Training loss statistics for BPR 𝑏 , BPR and SAROS . . . . . . . . . . . . 5-2 Loss dependence on the number of blocks . . . . . . . . . . . . . . . . 6-1 Convolutional Network Architecture . . . . . . . . . . . . . . . . . . . 6-2 Dataset SIM_SMALL . . . . . . . . . . . . . . . . . . . . . . . . . . 6-3 Dataset SIM_LARGE . . . . . . . . . . . . . . . . . . . . . . . . . . 6-4 Number of objects for corresponding group with the amount of neighbours for faulted line . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-5 SNR for various datasets . . . . . . . . . . . . . . . . . . . . . . . . . 6-6 Normalized histogram for samples distributions . . . . . . . . . . . . 6-7 The Mann-Whitney Statistics . . . . . . . . . . . . . . . . . . . . . . Chapter 1

   The prediction error is displayed with regard to the complexity of the class of hypotheses in this illustration of the bias-variance trade-off. Both the generalization error and the empirical error are large for a class of hypotheses with little complexity. This is referred to as underfitting. When the complexity of the class of functions grows, both the empirical and true errors decline until a point at which the generalization error starts to increase while the empirical error continues to fall. This is referred to as overfitting. On the class of hypotheses with the lowest generalization error, the best model may be identified.

Figure 2 - 3 :

 23 Figure 2-3: Depiction of Wolfe conditions and the backtracking line-search strategy.

Figure 2 - 4 :

 24 Figure 2-4: Illustration of the linear hyperplane serparator (in bold) perfectly separating the examples of the positive class (circle) and the negative class (square) as well as the margin.

Figure 2 - 5 :

 25 Figure 2-5: Illustration of a non-linearly separable classification problem. Support vectors are circled.

Figure 2 -

 2 Figure 2-6: 0/1 loss (blue), Hinge loss (green), and logistic loss (red)

Figure 2 -

 2 Figure 2-7: Structure of a biological (top) and a formal (down) neuron.

Figure 2 -

 2 Figure 2-8: ReLU based activation functions; the figure is taken from https://www. programmersought.com.

Figure 3 - 1 :

 31 Figure 3-1: Let[START_REF] Burashnikova | Learning over no-preferred and preferred sequence of items for robust recommendation[END_REF][START_REF] Burashnikova | Apprentissage séquentiel de préférence utilisateurs pour les systèmes de recommandation[END_REF] be the ratings of two items A and B, 𝑟 1 = [2.5, 3.6] and𝑟 2 = [2.5, 2.4] two vectors of predictions obtained by two different methods. Although 𝑟 1 and 𝑟 2 are equivalent in terms of squared error (the two are equal to 0.5 2 + 0.6 2 ), only 𝑟 1 predicts the order correctly, since the score it assigns to B is greater than that of A.

Figure 3 - 2 :

 32 Figure 3-2: Prod2Vec skip-gram model; the figure is taken from [Grbovic et al., 2015].

Figure 3 - 3 :

 33 Figure 3-3: The principle of convolve operation; the figure is taken from https: //classic.d2l.ai.

Figure 3 - 4 :

 34 Figure 3-4: The network architecture of Caser; the figure is taken from [Tang and Wang, 2018a].

Figure 3 - 5 :

 35 Figure 3-5: The principle of RNN work. The information is spread from the input to the output with some recursion on the connections between the nodes. The figure is taken from https://colah.github.io/.

Figure 3 - 6 :

 36 Figure 3-6: Mini batches for GRU4Rec; the figure is taken from [Hidasi and Karatzoglou, 2018].

Figure 3 - 7 :

 37 Figure 3-7: The examples of bipartite graph; the figure is taken from https://habr. com.

Figure 3 - 8 :

 38 Figure 3-8: LightGCN architecture; the figure is taken from [He et al., 2020].

Figure 3 - 9 :

 39 Figure 3-9: The transformer architecture; the figure is taken from https://jalammar. github.io/illustrated-transformer/.

Figure 3 -

 3 Figure 3-10: SASRec training structure; the figure is taken from [Kang and McAuley, 2018].

Figure 3

 3 Figure 3-11: ROC curve; the figure is taken from https://medium. datadriveninvestor.com.

Figure 4 - 1 :

 41 Figure 4-1: The sequential updates of weights (𝜔 𝑡 𝑢 ) 1≤𝑡≤𝐵 for a user 𝑢 ∈ 𝒰. The horizontal axis represents the sequence of interactions over items ordered by time. Each update of weights 𝜔 𝑡 𝑢 ; 𝑡 ∈ {𝑏, . . . , 𝐵} occurs whenever the corresponding sets of negative interactions, N 𝑡 𝑢 , and positive ones, Π 𝑡 𝑢 , exist. For a new user 𝑢 + 1, the initial weights 𝜔 0 𝑢+1 = 𝜔 𝐵 𝑢 .

Figure 4 - 2 :

 42 Figure 4-2: (a) Boxplots depicting the logarithm of the number of blocks through their quartiles for all collections. The median (resp. mean) is represented by the band (resp. diamond) inside the box. The ends of the whiskers represent the minimum and the maximum of the values. (b) Distributions of negative feedback over the blocks in the training set on Kasandr. Compared approaches.To validate the sequential approach described earlier, we compared the proposed SAROS algorithm 5 with the following methods:

Figure 4 - 3 :

 43 Figure 4-3: Evolution of the loss on training sets for both BPR 𝑏 , BPR and SAROS as a function of time in minutes for all collections.

Theorem 6

 6 Let ℒ(𝜔) be a (possibly non-convex) 𝛽-smooth function which satisfies the Polyak-Lojasievich condition with a constant 𝜇 > 0. Moreover, assume the number of interactions per user belongs to an interval [𝑏, 𝐵] almost surely for some positive 𝑏 and 𝐵, and Assumption 2 is satisfied with some 𝜎 2 and 𝑎. Then, for 𝑁 = ∑ 𝑁 𝑢=1 |ℬ 𝑢 | and a constant step-size policy 𝜂 𝑡 𝑢 = 𝜂 with 𝜂𝛽 ≤ 1, one has

Figure 5 -

 5 Figure5-1 shows the evolution of the training error over time for BPR 𝑏 , BPR, SAROS 𝑚 and SAROS 𝑏 on Kasandr, Pandor, Outbrain and Netflix. As we can see, the training error decreases in all cases and the three approaches converge to the same minimizer of the ranking loss (Eq. 2.18). This is an empirical evidence of the convergence of SAROS 𝑏 and SAROS 𝑚 , showing that the sequence of weights found by the proposed algorithm allows to minimize the general ranking loss (Eq. 2.18) as it is stated in Theorems 1 and 2.To estimate the importance of the maximum number of blocks (𝐵) for SAROS 𝑏 , we explore the dependency between quality metrics MAP@K and NDCG@K on ML-1M and Pandor collections (Figure5-2). The latter records the clicks generated by users on one of Purch's high-tech website and it was subject to bot attacks[START_REF] Sidana | Learning to recommend diverse items over implicit feedback on PANDOR[END_REF]. For this collection, large values of 𝐵 affects MAP@K while the measure reaches a plateau on ML-1M. The choice of this hyperparameter may then have an impact on the results. As future work, we are investigating the modelling of bot attacks by

Figure 5 - 1 :

 51 Figure 5-1: Evolution of the loss on training sets for both BPR 𝑏 , BPR and SAROS as a function of time in minutes for all collections.

Figure 5 - 2 :

 52 Figure 5-2: Evolution of MAP@5 with respect to largest number of allowed blocks, 𝐵.

  ..,𝑛;𝑘̸ =𝑖 𝑦 𝑘𝑖 i=j -𝑦 𝑖𝑗 𝑖 ̸ = 𝑗

Figure 6 Figure 6 - 4 :

 664 Figure 6-2: SIM_SMALL Figure 6-3: SIM_LARGE Figure 6-4: Number of objects for corresponding group with the amount of neighbours for faulted line

Figure 6 - 5 :

 65 Figure 6-5: Estimation of SNR approximation over the approaches on SIM_LARGE dataset. The results are provided for both models: with and without neighbours topology term in loss function

Figure 6 - 6 :

 66 Figure 6-6: Normalized histogram for samples distributions. The histogram provide information about output accuracy for two models for different randomization.

Figure 6 -

 6 Figure 6-7: Computed Mann-Whitney Statistics for normal distribution.

  Overfitting in classification . . . . . . . . . . . . . . . . . . . . . . . . 2-2 The phenomenon of overfitting . . . . . . . . . . . . . . . . . . . . . . 2-3 Depiction of Wolfe conditions and the backtracking line-search strategy. 2-4 Linear separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	𝑑		Number of PMUs
	𝐸		Set of lines
	𝑚		Number of lines
	𝑛 List of Figures Number of buses
	𝑡		Time index
	𝑉 𝑉 𝑑	2-1	Set of buses Set of nodes with PMUs
	𝑥 𝑡 = ({𝜃 𝑡 𝑖 , 𝑣 𝑡 𝑖 } 𝑑 𝑖=1 ) A set of PMU measurements at time 𝑡
	𝑦 𝑡 𝑖		Failure indicator at time 𝑡 at line 𝑖

2-5 Non-linearly separable problems . . . . . . . . . . . . . . . . . . . . . 2-6 The Hinge loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-7 Structure of a biological (top) and a formal (down) neuron. . . . . . . 2-8 ReLU based activation functions; the figure is taken from https:// www.programmersought.com. . . . . . . . . . . . . . . . . . . . . . . 3-1 Item ranking illustration . . . . . . . . . . . . . . . . . . . . . . . . . 3-2 Prod2Vec skip-gram model; the figure is taken from

  To minimize the generalization error, we will therefore minimize the empirical error on a given training set 𝑆. Given an error function ℓ : 𝒴 ×𝒴 → R + , a training set 𝑆 containing 𝑚 examples and a class of functions ℱ, the ERM principle returns then the function 𝑓 𝑆 verifying:

A learning algorithm takes as input a training set 𝑆, and returns a prediction function 𝑓 𝑆 : 𝒳 → 𝒴 . In formal terms, a learning algorithm is a function 𝒜 that looks for the function 𝑓 𝑆 inside a set of functions ℱ; called a class of functions. Intuitively, the ERM algorithm is understood as follows. If the training examples contained in 𝑆 are sufficiently representative of the distribution 𝒟, then (under certain conditions to be specified) the empirical error L𝑚 (𝑓, 𝑆) is a good estimate of the generalization error ℒ(𝑓 ).

  Algorithm SAROS: SequentiAl RecOmmender System Input: A time-ordered sequence (user and items) {(𝑢, (𝑖 1 , . . . , 𝑖 |𝐼𝑢| )} 𝑁 𝑢=1 drawn i.i.d. from 𝒟 𝒰 ,ℐ Input: maximal 𝐵 and minimal 𝑏 number of blocks allowed per user 𝑢 𝑡 𝑢 = ∅ be the sets of positive and negative items, counter 𝑡 = 0 for 𝑖 𝑘 ∈ ℐ 𝑢 do ◁ Consider all items displayed to user 𝑢 while 𝑡 ≤ 𝐵 do if 𝑢 provides a negative feedback on item 𝑖 𝑘 then

	Input: number of epochs 𝐸
	Input: initial parameters 𝜔 0 1 , and (possibly non-convex) surrogate loss function
	ℓ(𝜔)
	for 𝑒 ∈ 𝐸 do
	for 𝑢 ∈ 𝒰 do
	Let N 𝑡 𝑢 = ∅, Π

2. ℓ 𝑢,𝑖,𝑖 ′ (𝜔) is twice continuously differentiable, with a continuous Lipschitz gradient for both instantaneous loss and the ranking loss (Chapter 2 definition 1). That is Algorithm 1 *

  𝑢for any user 𝑢 and a pair of items (𝑖, 𝑖 ′ ) we have ‖∇ℓ 𝑢,𝑖,𝑖 ′ (𝜔) -∇ℓ 𝑢,𝑖,𝑖 ′

	end for
	end for
	Return: ω𝑁 =	∑ 𝑢∈𝒰 𝜔 0

Table 4 .

 4 2 presents some detailed statistics about each collection. Among these, we report the average number of positive (click, like) feedback and the average number of negative feedback. As we see from the table, Outbrain, Kasandr, and Pandor datasets are the most unbalanced ones in regards to the number of preferred and non-preferred items.To construct the training and the test sets, we discarded users who did not interact over the shown items and sorted all interactions according to time-based on the existing time-stamps related to each dataset. Furthermore, we considered 80% of each user's first interactions (both positive and negative) for training, and the remaining

	Data	|𝒰|	|ℐ|	Sparsity	Avg. # of +	Avg. # of -
	ML-1M	6,040	3,706	.9553	95.2767	70.4690
	Outbrain	49,615	105,176	.9997	6.1587	26.0377
	Pandor	177,366	9,077	.9987	1.3266	10.3632
	Netflix	90,137	3,560	.9914	26.1872	20.2765
	Kasandr 2,158,859 291,485	.9999	2.4202	51.9384

Table 4 .

 4 2: Statistics on the # of users and items; as well as the sparsity and the average number of + (preferred) and -(non-preferred) items on ML-1M, Netflix, Outbrain, Kasandr and Pandor collections after preprocessing.

	Dataset	|𝑆 𝑡𝑟𝑎𝑖𝑛 |	|𝑆 𝑡𝑒𝑠𝑡 |	𝑝𝑜𝑠 𝑡𝑟𝑎𝑖𝑛	𝑝𝑜𝑠 𝑡𝑒𝑠𝑡
	ML-1M	797,758	202,451	58.82	52.39
	Outbrain 1,261,373	336,053	17.64	24.73
	Pandor	1,579,716	493,663	11.04	12.33
	Netflix	3,314,621	873,477	56.27	56.70
	RecSys'16 5,048,653 1,281,909	17.07	13.81
	Kasandr	12,509,509 3,335,208	3.36	8.56

Table 4 .

 4 3: Number of interactions used for train and test on each dataset, and the percentage of positive feedback among these interactions.

Table 4 . 4 :

 44 .4. SAROS parameters values.Evaluation setting and results. We begin our comparisons by testing BPR 𝑏 , BPR and SAROS approaches over the logistic ranking loss (Eq. 4.2) which is used to train them. Results on the test, after training the models 30 minutes and at convergence are shown in Table4.5. BPR 𝑏 (resp. SAROS) techniques have the worse (resp. best) test loss on all collections, and the difference between their performance is larger for bigger size datasets.

	Parameter	ML Outbrain Pandor Netflix Kasandr
	𝐵	78	5	2	22	5
	𝑏	1	2	1	1	1
	Learning rate .05	.05	.05	.05	.4
			Test Loss, Eq. (4.1)
	Dataset		30 min		At convergence
		BPR 𝑏	BPR	SAROS BPR 𝑏	BPR	SAROS
	ML-1M	0.751	0.678	0.623 0.744	0.645	0.608
	Outbrain	0.753	0.650	0.646 0.747	0.638	0.635
	Pandor	0.715	0.671	0.658 0.694	0.661	0.651
	Netflix	0.713	0.668	0.622 0.694	0.651	0.614
	Kasandr	0.663	0.444	0.224 0.631	0.393	0.212

Table 4 .

 4

5: Comparison between BPR, BPR 𝑏 and SAROS approaches in terms on test loss after 30 minutes of training and at convergence.

  80-we propose a second variant of this strategy, referred to as SAROS 𝑏 . This variant consists in fixing two thresholds 𝑏 and 𝐵 over the parameter updates. For a new user 𝑢, model parameters are updated if and only if the number of blocks of items constituted for this user is within the interval [𝑏, 𝐵].The pseudo-code of SAROS 𝑏 is shown in Algorithm SAROS of chapter 4. The sequential update rule, for each current user 𝑢 consists in updating the weights by making one step towards the opposite direction of the gradient of the ranking loss estimated on the current block, ℬ 𝑡 𝑢 = N 𝑡 𝑢 ⊔ Π 𝑡 𝑢 :For a given user 𝑢, parameter updates are discarded if the number of blocks (ℬ 𝑡 𝑢 ) 𝑡 for the current user falls outside the interval [𝑏, 𝐵].

	𝜔 𝑡+1 𝑢	= 𝜔 𝑡 𝑢 -	𝜂 𝑢 ||Π 𝑡 |N 𝑡 𝑢 |	𝑖∈Π 𝑡 𝑢 ∑	𝑢 𝑖 ′ ∈N 𝑡 ∑	∇ℓ 𝑢,𝑖,𝑖 ′ (𝜔 𝑡 𝑢 )	(5.3)

  Assumption 2 For an i.i.d. sequence of user and any 𝑢, 𝑡 ≥ 1, we have

	1. E (𝑢,ℬ 𝑡 𝑢 ) ‖∇ℒ(𝜔 𝑡 𝑢 ) -∇ Lℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 )‖ 2 2 ≤ 𝜎 2 ,
	2. For any 𝑢,	⃒ ⃒ ⃒E ℬ 𝑡 𝑢 |𝑢 ⟨∇ℒ(𝜔 𝑡 𝑢 ), ∇ℒ(𝜔 𝑡 𝑢 ) -∇ Lℬ 𝑡 𝑢 (𝜔 𝑡 𝑢 )⟩ ⃒ ⃒ ⃒ ≤ 𝑎 2 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2

  .6) where the second inequality is due to |𝜂 𝑡 𝑢 𝛽| ≤ 1. Also, as |𝜂 𝑡 𝑢 𝛽| ≤ 1 and 𝑎 2 ∈ [0, 1/2) one has 𝑧 𝑡 𝑢 > 0 for any 𝑢, 𝑡. Rearranging the terms, one has

	and
	min 𝑡,𝑢	‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 ≤	ℒ(𝜔 0 1 ) -ℒ(𝜔 * ) + 𝛽 2 ∑ 𝑁 𝑢=1 ∑ |ℬ𝑢| ∑ 𝑁 𝑢=1 𝑡=1 𝜂 𝑡 𝑢 𝑧 𝑡 ∑ |ℬ𝑢| 𝑡=1 (𝜂 𝑡 𝑢 ) 2 𝜎 2 𝑢
				≤	ℒ(𝜔 0 1 ) -ℒ(𝜔 * ) + 𝛽 2	∑ 𝑁 𝑢=1
	𝑁 ∑ 𝑢=1	|ℬ𝑢| ∑ 𝑡=1	𝜂 𝑡 𝑢 𝑧 𝑡 𝑢 ‖∇ℒ(𝜔 𝑡 𝑢 )‖ 2 2 ≤ ℒ(𝜔 0 1 ) -ℒ(𝜔 * ) +	𝛽𝜎 2 2	𝑁 𝑢=1 ∑	|ℬ𝑢| 𝑡=1 ∑ (𝜂 𝑡 𝑢 ) 2 .

Table 5 .

 5 .1. 1: Statistics on the number of users and items; as well as the sparsity and the average number of + (preferred) and -(non-preferred) items on ML-1M, Netflix, Outbrain, Kasandr, Pandor and RecSys'16 collections after preprocessing.RecSys'16 also is included into the group of the most unbalanced datasets, such as Kasandr, Pandor and Outbrain. Table with the sizes of the train/test parts and percentages of positive/negative feedback in the benchmarks also was updated and displayed in the table5.2.

	Data	|𝒰|	|ℐ|	Sparsity	Avg. # of +	Avg. # of -
	ML-1M	6,040	3,706		.9553	95.2767	70.4690
	Outbrain	49,615	105,176		.9997	6.1587	26.0377
	Pandor	177,366	9,077		.9987	1.3266	10.3632
	Netflix	90,137	3,560		.9914	26.1872	20.2765
	Kasandr	2,158,859 291,485		.9999	2.4202	51.9384
	RecSys'16	39,518	28,068		.9943	26.2876	133.9068
		Dataset	|𝑆 𝑡𝑟𝑎𝑖𝑛 |		|𝑆 𝑡𝑒𝑠𝑡 |	𝑝𝑜𝑠 𝑡𝑟𝑎𝑖𝑛	𝑝𝑜𝑠 𝑡𝑒𝑠𝑡
		ML-1M	797,758		202,451	58.82	52.39
		Outbrain 1,261,373	336,053	17.64	24.73
		Pandor	1,579,716	493,663	11.04	12.33
		Netflix	3,314,621	873,477	56.27	56.70
		Kasandr	12,509,509 3,335,208	3.36	8.56
		RecSys'16 5,048,653 1,281,909	17.07	13.81

Table 5 .

 5 2: Number of interactions used for train and test on each dataset, and the percentage of positive feedback among these interactions.

Table 5 .

 5 .3. 3: Hyperparameter values of SAROS 𝑏 .Evaluation Setting and Results. All the experimental steps suggested for the practical part of chapter 4 were repeated on the additional new benchmark RecSys'16, baseline LightGCN and SAROS 𝑚 . For the first results, the testing BPR 𝑏 , BPR and SAROS approaches over the logistic ranking loss after training the models till the convergence are shown inTable 5.4.

	Parameter	ML Outbrain Pandor Netflix Kasandr RecSys'16
	𝐵	78	5	2	22	5	22
	𝑏	1	2	1	1	1	1
	Learning rate .05	.05	.05	.05	.4	.3
		Dataset	Test loss at convergence, Eq. (2.18)
			BPR 𝑏	BPR	SAROS 𝑏 SAROS 𝑚
		ML-1M	0.744	0.645	0.608	0.637
		Outbrain	0.747	0.638	0.635	0.634
		Pandor	0.694	0.661	0.651	0.666
		Netflix	0.694	0.651	0.614	0.618
		Kasandr	0.631	0.393	0.212	0.257
		RecSys'16	0.761	0.644	0.640	0.616

Table 5 .

 5 4: Comparison between BPR, BPR 𝑏 and SAROS approaches in terms of test loss at convergence.

Table 5 .

 5 7 presents the comparison of MOSAIC with BPR, Caser and SAROS. These results suggest that compared to BPR which does not model the sequence of interactions,

		|𝑈 |	|𝑆𝑡𝑎𝑡_𝑈 |
	Kassandr 2,158,859	26,308
	Pandor	177,366	9,025
	ML-1M	6,040	5,289
	Outbrain	49,615	36,388
	Table 5.6: Statistics on datasets before and after filtering. Among these, the remaining
	number of users after filtering based on stationarity in embeddings is denoted as
	|𝑆𝑡𝑎𝑡_𝑈 |

Table 6 .

 6

		set of lines		𝑉	set of buses
	𝑚	number of lines	𝑛	number of buses
	𝑣	bus voltages, 𝑣 ∈ R 𝑛 𝜃	phase angles, 𝜃 ∈ R 𝑛
	𝑝, 𝑞	vector of active/reactive power injections
	𝑑	number of PMUs	𝑉 𝑑 set of nodes with PMUs
	𝑡	time index
	𝑦 𝑡 𝑖	failure indicator at time 𝑡 at line 𝑖
	𝑥 𝑡 = ({𝜃 𝑡 𝑖 , 𝑣 𝑡 𝑖 } 𝑑 𝑖=1 ) a set of PMU measurements at time 𝑡
	nb 𝐸 (•), nb 𝑉 (•)	list of adjacent edges, vertices
	nb 𝑘 𝐸 (•), nb 𝑘 𝑉 (•)	nb 𝑘 𝐸 (•) = nb 𝐸 ((. . . nb 𝐸 (•)) , nb 𝑘 𝑉 (•) = nb 𝑉 (. . . nb 𝑉 (•))
		⏟	⏞ 𝑘 times		⏟	⏞ 𝑘 times
			1: Chapter notation.

Table 6 . 2

 62

: Timeline of events in a power grid.

Table 6 .

 6 .3: 3: Size of the train, test and validation parts.

	Dataset	Set	Size
		Train	1210
		TP -Test	71
	SIM_SMALL	DLG -Test LG -Test	71 70
		LL -Test	71
		Validation	1210
		Train	14413
	SIM_LARGE	Test	994
		Validation	1207

Table 6 .

 6 .4. 4: Comparison of the approaches based on the partial observability, SIM_SMALL data

		TP fault		DLG fault		LG fault		LL fault
	% buses No-neigbhbors With-neighbors No-neigbhbors With-neighbors No-neigbhbors With-neighbors No-neigbhbors With-neighbors
	100	98.59	100.0	100.0	100.0	100.0	100.0	100.0	100.0
	30	91.55	97.18	95.77	98.59	97.14	97.14	98.59	100.0
	25	78.87	92.96	92.96	97.18	94.29	97.14	95.77	98.59
	20	91.55	94.36	90.14	97.18	84.29	94.29	95.77	95.77
	15	73.24	88.73	95.77	97.18	88.57	92.86	88.73	90.14

Table 6 .

 6 .86 93.66 92.76 95.07 88.33 91.44 93.16 89.03 85.11 with neighbors 95.57 95.27 95.07 95.47 94.67 91.95 90.74 94.16 88.63 89.64 5: Estimation for different sizes of training set on SIM_LARGE data

	+/-neighbors 100 % 90%	80 % 70 % 60 % 50 % 40 % 30 % 20 % 10 %
	no neighbors	95.07 93

Table 6 .

 6 6: Comparison of the approaches based on partial observability on SIM_LARGE dataset

		fault
	% buses No-neigbhbors With-neighbors
	100	95.07	95.57
	30	85.41	87.32
	25	78.27	82.09
	20	79.48	80.28
	15	71.93	76.25

http://www.movielens.org

http://del.icio.us/

https://radimrehurek.com/gensim/models/word2vec.html

https://www.kaggle.com/c/outbrain-click-prediction

https://www.tensorflow.org/.

https://www.kaggle.com/c/outbrain-click-prediction

https://archive.ics.uci.edu/ml/datasets/KASANDR

https://archive.ics.uci.edu/ml/datasets/PANDOR

The code is available on https://github.com/SashaBurashnikova/SAROS.

https://www.ncdc.noaa.gov/billions/

I hereby declare that the work presented in this thesis was carried out by myself according to joint agreement between Skolkovo Institute of Science and Technology (Moscow) and University Grenoble Alpes

List of Tables

 Chapter 5Learning over No-Preferred and Preferred Sequence of Items for Robust Recommendation

Introduction

In this chapter, we consider two variants of the SAROS strategy presented in chapter 4. The first variant, referred to as SAROS 𝑚 , updates the model parameters at each time a block of unclicked items followed by a clicked one is formed after a user's interaction. Parameters' updates are carried out by minimizing the average ranking loss of the current model that scores the clicked item below the unclicked ones using a momentum method [Polyak, 1963, Nesterov, 1983, Nesterov, 2018]. The second strategy, which we refer to as SAROS 𝑏 , is the same approach described in chapter 4, where model parameters are updated by minimizing a ranking loss over the same blocks of unclicked items followed by a clicked one using a gradient descent approach; with the difference that parameter updates are discarded for users who interact very little or a lot with the system. The results of this chapter were published at the Journal of Artificial Intelligence Research (JAIR) in 2021, [START_REF] Burashnikova | Learning over no-preferred and preferred sequence of items for robust recommendation[END_REF] and the European Conference in Information Retrieval (ECIR) in 2022 [START_REF] Burashnikova | Recommender systems: when memory matters[END_REF].

Our main contributions here are,

• We propose a unified framework in which we study the convergence properties of both versions of SAROS in the general case of non-convex ranking losses. This is an extension of our earlier results [4], where only the convergence of SAROS 𝑏 was studied in the case of convex ranking losses.

• Furthermore, we provide empirical evaluation over six large publicly available datasets showing that both versions of SAROS are highly competitive compared to the state-of-the-art models in terms of quality metrics and, that are significantly faster than both the batch and the online versions of the algorithm.

• Finally, we show the impact of homogeneous user/items interactions for prediction, after removal of non-stationarities

The chapter notation is summarized in Table 6.1.

Background.

Phasor Measurement Units (PMUs) enable high-resolution situational awareness of power grid state by providing information about voltage magnitude 𝑣 𝑖 , 𝑖 ∈ 𝑉 and phase angle 𝜃 𝑖𝑗 , (𝑖, 𝑗) ∈ 𝐸 using a common time source for synchronization. Often PMUs are required at tap-changing transformers, complex loads, and PV (generation) buses. Despite of wide-spread of PMUs and their role in grid monitoring, power grids remain covered only in part because of privacy and budget limitations.

For notation simplicity, we assume w.l.o.g. that PMUs are places at the first 𝑑 buses 𝑉 𝑑 of the grid, 𝑉 𝑠 ⊆ 𝑉 , and this placement does not change during the observation time. We refer 𝑉 𝑑 as a set of observable buses. Furthermore, we receive a set of PMUs measurements 𝑥 𝑡 = ({𝜃 𝑡 𝑖 , 𝑣 𝑡 𝑖 } 𝑑 𝑖=1 ) for each time 𝑡, 0 ≤ 𝑡 ≤ 𝑇 . Let 𝑦 𝑡 ∈ R 𝑛 be a an indicator of faulted lines, e.g. 𝑦 𝑡 𝑖𝑗 = 1 iff line (𝑖, 𝑗) is faulted at time 𝑡, 0 ≤ 𝑡 ≤ 𝑇 . The ability of PMU to measure the voltage phasor at the installed bus and the current phasor of all the branches connected to the PMU installed bus can help determine the remaining parameters to use for indirect measurements.

A particular advantage of PMU technology is high sampling rate that dramatically increase situational awareness and allows to detect grid failures in nearly real-time. For instance, for 60 Hz systems, PMUs must deliver between 10 and 30 synchronous reports per second depending on the application. The timeline of the events in a power grid is described in the Table 6.2.

To consider the topology of power grid we transform the binarized targets (fault or non-fault), that we used during training into two vectors: the first one includes the information about the faulted line and the second one consists of the information about the neighbours of the faulted line. In more details, suggest we have a sample (𝜓, 𝑦) with the features 𝜓 ∈ 𝑅 𝑑 , where 𝜓 is some transformation over measurements 𝑥 𝑡 and known parameters in power grid. Then the first vector of targets is defined as

where in case of faulted line at the location 𝑗, 𝑦 𝑗 = 1 and 𝑦 𝑖 = 0 for 𝑖! = 𝑗. For the second vector of targets, let 𝑛𝑏 𝐸 (𝑗) denote the neighborhood of the 𝑗th line, including the lines connected with 𝑗, and then ŷ𝑖 = 1/nb 𝐸 (𝑗) only if 𝑖 ∈ nb 𝐸 (𝑗). The definition of ŷ is formalized at the equation defined at the Eq. 6.1: For the remains line target is equal to zero. Then the loss function 𝐿𝑜𝑠𝑠(𝑓 (𝜓), 𝑦, ŷ) for the proposed model (architecture is presented on the Fig. 6-1) over the samples (𝜓, 𝑦), where 𝑓 (𝜓) are the predicting probabilities of the proposed model is defined as the sum of two terms of cross-entropy functions (here CE). The definition of CE is