Pierre-Xavier Loeffel
email: pierre-xavier.loeffel@lip6.fr

Vincent Lemaire
email: vincent.lemaire@orange.com

Christophe Marsala
email: christophe.marsala@lip6.fr

Marcin Detyniecki
email: marcin.detyniecki@lip6.fr

Improving the Prediction Cost of Drift Handling Algorithms by Abstaining

The problem considered in this paper is regression with a constraint on the precision of each prediction in the framework of data streams subject to concept drifts (when the hidden distribution which generates the observations can change over time). Concept drifts can diminish the reliability of the predictions over time and it might not be possible to output a prediction which satisfies the constraints on the precision. In this case, we claim that if the costs associated with a good and with a bad prediction are known beforehand, the overall prediction cost can be improved by allowing the regressor to abstain. To this end, we propose a generic method, compatible with any regressor, which uses an ensemble of reliability estimators to estimate whether the constraints on the precision of a given prediction can be met or not. In the later case, the regressor is allowed to abstain. Empirical results on 30 datasets including different types of drifts back our claim.

I. INTRODUCTION

The interest for machine learning algorithms able to learn on a stream of data has grown very rapidly during the last few years. Human-machine interactions, autonomous driving or prediction of stock prices constitute examples of applications domain where an open-ended stream of data must be processed by a learning algorithm. However, data streams are often subject to concept drifts, when the hidden distribution which generates the data changes over time. As a consequence, the reliability of the predictions given by algorithms learning on such streams can be significantly deteriorated. This is an issue, especially when there is a constraint on the level of precision expected for each prediction; a scenario which can appear in cost-sensitive applications of machine learning such as medicine or financial forecasting.

In this paper, we show in the regression setting that the overall cost achieved by a predictor learning on a data stream subject to concept drifts can be significantly improved by allowing it to abstain. Sometimes, it is not possible to output a prediction with the desired level of precision and instead of outputting a wrong prediction; it might be worth allowing the predictor to abstain. Therefore, we propose a generic method, compatible with any regressor, which uses an ensemble of reliability estimators to estimate whether the constraints on the precision of a given prediction can be met or not. In the later case, the regressor is allowed to abstain.

The paper is organized as follows: Section II describes the framework and the proposed method. Section III goes through the related works and section IV describes the experimental protocol. The results on the synthetic and real life datasets are given in sections V and VI respectively. Finally section VII concludes.

II. FRAMEWORK AND PROPOSED METHOD

In this section, we lay down the framework, introduce our problem with a real life example and propose a generic method aimed at improving the performance of any regression algorithm able to learn on a stream of data subject to concept drifts. We also discuss the choices made for the parameters and how we constrain the suitable abstention costs.

A. Framework

In the supervised regression setting, the goal is to learn a predictor h : X → Y, (with X the input space and Y ∈ R the output space) capable of generating accurate output predictions ŷ = h (x) ∈ R for any unlabeled observation x∈ X . Each observation z ∈ Z (with Z = X × Y) is generated by a stream which starts emitting observations {z t1 , z t2 , ...} at time t 0 . Each observation z t is generated according to a hidden distribution D t over Z. The distribution D t (also referred as concept) can change over time and we will say that the concept D t that the predictor is trying to learn, has drifted at time t if D t-1 = D t . When the concept is stable, the observations are assumed to be i.i.d. realizations of a single concept whereas when the concept is drifting they are only assumed independent from each other.

The regressor h is further allowed to abstain from prediction, a framework commonly known as selective regression [START_REF] Wiener | Pointwise Tracking the Optimal Regression Function[END_REF]. In this case, the regressor h is associated with a selection function g : A → {0, 1} (where the input space A can change from one selection function to the other) whose meaning is as follows:

(h, g) (x t ) = ∅ if g (a t ) = 0 h (x t ) if g (a t ) = 1
where ∅ denotes an abstention on the unlabeled observation x t and where a t ∈ A.

The problem considered here is to produce a predictor h (or a predictor associated with a selection function (h, g)) that minimizes the expected cost from prediction on the n observations received so far: C : (Y ∪ ∅)×Y → [0; 1] is a cost function) under the constraint of a required precision threshold . Formally, we define the -tube cost function presented in [START_REF] Kégl | Robust regression by boosting the median[END_REF] as:

1 n n i=1 C (h (x i ) , y i ) (where
C 0-d-1 (ŷ, y) =    0 if |y -ŷ| ≤ and g (a) = 1 1 if |y -ŷ| > and g (a) = 1 d > 0 if g (a) = 0
where is a threshold determined by the problem at hand and d is the cost associated with an abstention.

Note:

The problem considered here shares some similarities with the task of giving predictions intervals [START_REF] Khosravi | Comprehensive review of neural network-based prediction intervals and new advances[END_REF]. The difference is that, in the case of a prediction interval, the goal is to estimate the interval into which the observation will fall with a given probability in order to quantify the uncertainty in the point forecasts whereas here, the interval is constrained by the requirements of the problem at hand. In both cases though, the performance of the underlying algorithm is assessed by checking whether the observation falls into the predicted interval.

B. Real life example

In order to illustrate the problem, we describe the case of an investor which is betting on a "Binary Tunnel Option". A Binary Tunnel Option is a financial product that rewards the buyer of the product if he manages to accurately forecast whether the price of the underlying asset will be in a given range at the maturity date of the option.

For instance, assume that the current price of stock S is 129C (see the left hand side of Fig. 1). Based on his machine learning algorithm, an investor predicts that the price of stock S will be ŷ = 132.5 C in 20 days. He can then call a broker and ask him to create a Binary Tunnel Option for which the thresholds are for instance ŷ -= 130C and ŷ + = 135C (thus, in this case, = 2.5). If the broker manages to find another investor willing to sell this option, the first investor can buy the option for a price p (1C for instance) and will get a profit (for instance 10C) only if the price of stock S is within the 130 C-135 C range at the closing price in 20 days. Otherwise, if the price of stock S at the maturity date is outside this range, the investor loses his initial investment (1 C). The payoff of the option in this particular example is shown on the right hand side of Fig. 1.

Algorithm 1 Generic Method

Inputs: unlabeled observation: x t , predictor learned at previous step: h t-1 , ensemble of reliability estimator: RE 1 , ..., RE m , ensemble of confidence thresholds: q 1 , ..., q m , ensemble of inputs specific to each reliability estimator: Q 1 , ..., Q m , selection function:

g 01: ŷt ← h t-1 (x t ) 02: rt ← Compute REs RE 1 , ..., RE m , Q 1 , ..., Q m 03: a t ← Apply T hresholding rt , q 1 , ..., q m 04: if g (a t ) = 0 then 05: ∅ ← (h, g) (x t ) Abstain 06: else 07: ŷt ← (h, g) (x t ) Predict 08: end if 09: h t ← U pdate (h t-1 , x t )
Update the learned model

C. Proposed method

The underlying idea of the proposed method is that by allowing a predictor to abstain, it is possible to achieve better performances at the cost of a smaller coverage (the proportion of observations for which a non-empty prediction is given). Therefore, we propose a generic method which assess whether the constraint on the required precision can be met. When this is not the case, the predictor is allowed to abstain in order to avoid a costly error.

Note: For the rest of this paper, "reliability estimate" is used to refer to an estimate of the prediction error.

Method:

The full method is detailed in Algorithm 1 and is described here: at time t, upon reception of x t , the predictor h t-1 learned at time t -1 outputs an estimated prediction ŷt . The estimate ŷt is then set aside. A set of m reliability estimators RE i , i = 1, ..., m then associates reliability estimates rt = r1 t , ..., rm t ∈ (R + ) m to ŷt where small values of ri t indicate that the reliability estimator is confident that the prediction ŷt is close to the target value y t , and large values of ri t indicate a lack of confidence.

For each reliability estimator, a confidence threshold q i is set and if ri t ≤ q i , the prediction is deemed as reliable according to this reliability estimator. The final decision of each RE a t = a 1 t , ..., a m t is then aggregated through a selection function g and the prediction ŷt is used if the selection function assessed the prediction as reliable. Otherwise, ŷt is discarded and the predictor abstains for this observation. Indeed concept drifts can diminish the reliability of the predictions over time and when the reliability of a given prediction is too small, it might not be possible to output a prediction which satisfies the constraints on precision required by the problem at hand. In such cases, abstaining should be considered as a way to improve the overall expected cost.

One major advantage of this method is that the REs do not depend on a particular predictor and thus can be used with any base algorithm, as long as it is able to deal with concept drift on a stream. There are, however, some constraints on the REs, as they must be able to operate on-line, use limited memory, have a low processing time and be able to cope with non-stationary distribution.

Another advantage of our approach is it relies on an ensemble of REs: Previous empirical evaluations of existing reliability estimates showed that the best RE depends on the regressor and on the dataset [START_REF] Toplak | Assessment of machine learning reliability methods for quantifying the applicability domain of QSAR regression models[END_REF][9] [START_REF] Briesemeister | No Longer Confidential: Estimating the Confidence of Individual Regression Predictions[END_REF]. These results are of particular interest in the framework of concept drift, where the characteristics of the dataset can evolve over time. To tackle this issue, several studies have been carried showing the interest of ensemble approaches [8][9] for the estimation of the reliability of individual prediction. We proposed here to use a simple majority vote but a different aggregating technique could have been used [START_REF] Bosnić | Automatic selection of reliability estimates for individual regression predictions[END_REF]. Rather than the choice of a specific ensemble method, the emphasis here is put on being able to reject prediction estimates with low reliability regardless of the base regressor used and of the characteristics of the dataset considered.

Building up on these previous findings, the contribution of the proposed method is to show the necessity to allow abstention when learning on a data stream subject to concept drifts.

Note: At this point, it should be emphasized that the generic method previously proposed has no impact on the update of the hypothesis h. Whether the selection function g choses to abstain or predict, the hypothesis h learned after update with the latest observation, is the same as the one obtained without the selection function.

D. Setting the values of the parameters associated with the proposed method

Many of the REs used require to set some parameters. In the framework of concept drift, setting an appropriate value for the parameter of an algorithm is a difficult task as a given parameter would only be optimal at a given time [START_REF] Krempl | Open Challenges for Data Stream Mining Research -in SIGKDD Explorations[END_REF], for a given concept, on a given dataset and for a given algorithm. Consequently, we chose to use non optimized parameters which are set to default values regardless of the datasets or the base learner and the task of optimally setting parameters is left for future work.

We also applied the same principle for the numerical confidence threshold q of each RE. As previously stated, each RE is an estimate of the prediction error and thus, because they evaluate the same value, the same threshold q was used for all the linear REs (ŷ -y) whereas q 2 was used for the REs with a quadratic form (ŷ -y) 2 . Finally, a value also had to be given to the confidence threshold q which also depends on the problem at hand. Because each RE is an estimate of the prediction error, we chose to set = q for all the experiments. Indeed, when is small, the problem considered requires a lot of precision and thus the requirement for being confident on a particular observation should be tougher. On the other hand, if gets larger, the need for precision decreases and thus the requirements on the confidence estimators should also be looser.

E. Defining which abstention costs are suitable

Ultimately, the value of d depends on the problem at hand, however, for the remainder of this paper, we will set d = 1 2 which is the "worst" abstention cost that we will consider. Indeed, regardless of the algorithm considered, if d ∈ 0; 1 2 , there exist some cases where abstaining can improve the performances. Conversely, if d > 1 2 , there are some algorithms for which abstaining will never improve the performances. For this reason, we restrict our framework to d ∈ 0; 1 2 and we will choose to never abstain if d > 1 2 . Proof: The use of the -tube cost function transforms a regression problem into a binary classification problem where the goal at each observation is to predict ŷ ∈ A := [y -; y + ].

In the binary classification setting, regardless of the problem at hand, the Bayes rule equipped with the true posterior probabilities, will always minimize the probability of misclassification [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF]. For instance, on a given observation x, if the true posterior probabilities are P (Y = A/X = x) = 0.6 and P Y = Ā/X = x = 0.4 then, the Bayes rule will always predict the class associated with the highest posterior probability. In this particular example, the expected cost from prediction is 0.6 × 0 + 0.4 × 1 = 0.4 and abstaining should be considered only if d ≤ 0.4 (the expected cost from abstaining is always known and is equal to d). More generally, the worst expected prediction cost is achieved if P (Y = A/X = x) = P Y = Ā/X = x and is 0.5. Thus, regardless of the dataset considered, if d > 1 2 then the Bayes rule should never abstain. Because any algorithm will have a worse misclassification rate than the Bayes rule with the true posterior rule, the cases where abstaining improves the expected prediction cost of the Bayes rule will also improve the expected prediction cost of any other algorithm. For this reason, we restrict our framework to d ∈ 0; 1 2 and more particularly to the "worst" case d = 1 2 .

F. Choosing a selection function

For the choice of selection function g, we used a simple majority vote which chooses to use the initial prediction ŷ only if an absolute majority of reliability estimators marked the prediction as reliable. Here again, the performances can be enhanced by a wiser choice of selection function.

III. RELATED WORK

We start this section by reviewing state of the art regression algorithms, able to adapt to concepts change, process observations upon reception and use limited computer memory. We then review regression algorithms which can abstain when a prediction is deemed unreliable. Finally, we discuss why these algorithms are not suitable to tackle our problem.

A. Regression algorithms for data stream subject to concept drift

The overwhelming majority of the algorithms able to handle drifting concepts have been designed to predict in the classification setting. However, a few algorithms have been devised for the regression setting. Shaker and Hullermeier [START_REF] Shaker | IBLStreams: A system for instance-based classification and regression on data streams[END_REF] proposed IBLStreams, an instance-based algorithm able to learn under the classification and regression settings. The algorithm is able to autonomously optimize the composition and the size of the case base. The latest observation is first added to the case base and then, the algorithm checks whether some of the past observations should be removed, either because they have become redundant, either because they are outliers. The recent observations, however, are excluded from removal.

Ikonomovska et al. [START_REF] Ikonomovska | Learning model trees from evolving data streams[END_REF] developed FIMT-DD, an incremental algorithm for learning regression trees from data streams. The algorithm is equipped with mechanisms for adaptation and drift detection which allow the local update of the tree if necessary. In order to constrain the consumption of memory, a method for disabling bad split points is included.

In [START_REF] Almeida | Adaptive Model Rules from Data Streams[END_REF], Almeida et al. devised AMRules, a rule learning algorithm for regression problems on data streams where each rule is created as a linear combination of attribute values. Each rule uses the Page-Hinkley test [START_REF] Page | Continuous inspection schemes[END_REF] to detect changes and model adaptation happens by pruning the rule set. The algorithm also allows to differentiating the importance of the training observation by the use of weights.

Duarte and Gama [START_REF] Duarte | Ensembles of Adaptive Model Rules from High-Speed Data Streams[END_REF] proposed Random AMRules, an online ensemble method that combines a set of rules created by the AMRules algorithm. A mechanism prevents the base models from being correlated by randomly choosing the set of attributes considered for each base rule. The final prediction of the model is a simple linear combination of the predictions produced by the base models where the weight of each model can be set either uniformly, either according to the performance of the base model.

Note: These 4 algorithms are used as a baseline later in the experimental section.

B. Regression with a reject option

The issue of selective prediction has been abundantly addressed in the classification setting, however, similarly to the algorithms developed for data streams, only a few models were devised for the regression setting.

El-Yaniv and Wiener [START_REF] Wiener | Pointwise Tracking the Optimal Regression Function[END_REF] developed a strategy for learning selective regressors which are guaranteed to achieve -pointwise optimality (when the regressor is able to achieve results which are arbitrarily close the optimal regressor in hindsight, on the set of observations for which a prediction is given) under the assumption that the observations are i.i.d. realizations of a static concept D.

Kegl [START_REF] Kégl | Robust regression by boosting the median[END_REF] devised MedBoost, a boosting algorithm for regression that uses the weighted median of base regressors as final regressor. The special case where the base regressors as well as the final decision abstain is briefly considered.

In [START_REF] Strehl | Online linear regression and its application to model-based reinforcement learning[END_REF], a special type of on-line linear regression (Know What It Knows Linear Regression) is introduced by Strehl and Littman. The authors devised 2 uncertainty measures for the least-squares estimate and allow the algorithm to abstain from prediction when the confidence in this estimate is not high enough. Unfortunately, despite its on-line learning ability, the algorithm isn't suited to deal with drifting concepts as it assumes that the concept doesn't change over time.

The case for abstention in the regression setting also appears within the framework of conformal prediction [START_REF] Gammerman | Hedging predictions in machine learning[END_REF] [START_REF] Balasubramanian | Conformal Prediction for Reliable Machine Learning[END_REF].

In this framework, it is possible to give guarantees on the accuracy of an algorithm under the assumption that the observations are i.i.d. realizations of a static concept D. Unfortunately, this assumption doesn't hold in the framework of concept drifts.

C. Shortfalls of the related works

On the one hand, the existing regressors suited to learn on a data stream subject to concept drift never abstain from prediction in their current form. On the other hand, the state of the art algorithms for regression with a reject option have not been devised to operate under a stream of data subject to concept drifts. Therefore, we propose to improve the performances of drift handling algorithms by allowing them to abstain.

IV. EXPERIMENTAL PROTOCOL

In this section, we describe the reliability estimators used, characterize the types of concept drifts reproduced in the synthetics datasets, describe the experimental protocol as well as the success metrics.

A. Description of the On-line Reliability Estimators

We chose to implement 7 of the reliability estimators (REs) presented in the work of Rodrigues et al. [START_REF] Rodrigues | Online reliability estimates for individual predictions in data streams[END_REF] as they are well suited for data streams. Here, rather than the particular reliability estimates used, the emphasis is on creating a diversified set of REs, suited to operate on a data stream subject to concept drifts. A brief description of the reliability estimators is given below the interested reader is referred to the original paper for further details.

• Similarity-based reliability estimate: The underlying idea of this estimate is to use temporal similarity: Given the ordered arrival of observations, it can be argued that the latest observation x t should be more similar to the "recent" observations {x t-1 , x t-2 , ..., x t-k } than the older ones {x t-k-1 , x t-k-2 , ...}. Thus, if the mean squared error has been low on a sliding window of recent observations, the RE is confident that the prediction error at time t will also be low. Formally, the RE is defined as follows:

R M SE = t∈B (ŷt-yt) 2

|B|

, where B is the set of the |B| = k most recent observations.

• Local Sensitivity: The principle of this RE is to perturb the label associated with the latest observation and assess to which extent the prediction of the algorithm learned with the perturbed observation is modified. If there is little difference in the prediction, the RE is confident that the initial prediction is good. Formally: at time t, upon reception of an unlabeled observation x t , the algorithm outputs an initial prediction h t-1 (x t ) = ŷ0 . Two artificial observations are then created by modifying the estimated label by a value δ 1 > 0: {(x t , ŷ0 + δ 1 ) , (x t , ŷ0 -δ 1 )}. Two copies h 1 t-1 and h 2 t-1 of the algorithm h t-1 are then created. The first copy is trained with the first artificial observation whereas the second uses the second one. Then each copy computes a prediction ŷδ1 = h 1 t-1 (x t ) and ŷ-δ1 = h 2 t-1 (x t ) for the unlabeled observation x t initially received. This process is repeated k times with different values of δ, resulting in a set of 2k predictions A = {ŷ δ1 , ŷ-δ1 , ..., ŷδ k , ŷ-δ k }. The 2 REs derived from these predictions are:

R 1 LSA = k i=1 (ŷδ i -ŷ -δ i ) k and R 2 LSA = j∈A ŷj 2k -ŷ0
• Dual Perturb and Combine: Conversely to Local Sensitivity Analysis, the idea is to perturb the attribute values of the latest observation and assess to which extent the prediction of the algorithm changes. Formally: the algorithm outputs an initial prediction h t-1 (x t ) = ŷ0 . A set of k artificial unlabeled observations is then created: ∀i = 1, ..., k : x i t = x t + δ i with δ i the vector of modifiers δ ij , one for each attribute dimension j and with δ ij ∼ N 0, σ 2 j . A prediction ŷi is then generated for each artificial observation by computing h t-1 x i t = ŷi . The 2 REs derived from these predictions are:

R 1 DP C = k i=1 ( ŷi-ȳ) 2 k
where ȳ is the average of all the perturbed predictions ŷi , i = 1, ..., k and the original prediction ŷ0 .

R 2 DP C = k i=1 ( ŷi-ŷ0) k .
• On-line Bagging Sensitivity: Here, the idea is to compare the prediction of the base model trained with all the observations to the predictions of k multiple versions of the base model trained with different subsets of the observations seen so far.

R 1 BAG = k i=1 ( ŷi-ȳ) 2 k
where ȳ is the average of all the predictions ŷi , i = 1, ..., k given by the k models and ŷ0 is the prediction obtained with the base model.

R 2 BAG = k i=1 ( ŷi-ŷ0) k .
Values of k and δ: As explained in section II-D, we chose to use a fixed set of parameters, regardless of the base learner or the dataset. The chosen values are roughly in line with the values used in the paper of Rodrigues et al. Table I summarizes the choices made for each parameter.

B. Characterizing concept drifts

For the remainder of this paper, we will use the recent drifts characterization of Webb et al. [START_REF] Webb | Characterizing Concept Drift[END_REF] that we briefly summarize thereafter.

We start by defining the magnitude of a drift between times t -1 and t as: M agnitude := H (D t-1 , D t ) where H (., .) ∈ [0; 1] is the Hellinger distance [START_REF] Hoens | Heuristic Updatable Weighted Random Subspaces for non-stationary environments[END_REF] between D t-1 and D t . H = 0 indicates that the 2 distributions are identical whereas H = 1 is achieved when D t-1 assigns probability 0 to every set to which D t assigns a positive probability and vice versa.

Let z D Q tstart be the first observation received and z

D Q t end be the last observation received of the Q th stable concept in the stream (a concept D Q is deemed as stable if t D Q end -t D Q start ≥ 2).
Let {D A , D B , ...} be the succession of stable concepts encountered since the stream started to emit observations at t 0 .

We will say that an abrupt drift occurred if:

t D R start -t D Q
end = 1 (where D Q and D R are 2 consecutive stable concepts). Conversely, we will say that a gradual drift occurred if:

t D R start -t D Q end > 1.
In other words, a gradual drift is a drift that last more than one observation.

We will say that a local drift occurred if the distribution D changes only over a constrained region of Z and that a global drift occurred if D changed on the whole region Z.

C. Experimental protocol

We used the Java platform MOA [START_REF] Bifet | MOA: Massive Online Analysis[END_REF] which provides an environment for running experiments in the framework of data streams subject to concept drifts. We used 4 regressors (described in section III-A) which were already implemented in the platform (with the exception of IBLStream which was developed as an add-on 1 ). The confidence estimators were directly implemented in MOA 2 .

Similarly to the parameters of the reliability estimates, we chose to use the default values (set in MOA) of the parameters of each regressor, regardless of the dataset. The underlying idea remains the same: as we are not allowed to make any kind of assumption regarding the type of drift encountered, there would be little point in optimizing a set of parameters that would only be relevant at a given time, on a particular dataset and for a particular concept.

In the case of (the value associated with the tube cost function), it was previously stated that is a threshold set before the algorithm is ran and which depends on the problem at hand. Therefore, in order to simulate different requirements on the precision level, 2 thresholds were tested on the synthetic datasets:

• The first threshold was assumed to be "low" (i.e. a good prediction is hard to achieve as the -tube is small).

• The second threshold was assumed to be "high" (i.e. it is easier to output a prediction which is within the -tube considered).

The 2 thresholds for were determined with hindsight by computing the variance of the target variable on the whole dataset and using a different multiple of this number for each threshold.

D. Success Metrics

In order to assess the benefits from abstention, we have computed the percentage of improvement in the overall cost between each regressor and its abstaining version. Formally, for a given dataset with n observations, we started by computing the absolute difference between the 2 overall costs achieved:

abs diff = n i=1 C 0-d-1 (h base (x i ) , y i ) - Ĉ0-d-1 [(h, g) (x i ) , y i ]
1 The code for their add-on can be recovered from this link: https://www.unimarburg. de where h base is the base version (without a selection function) of the algorithm that predicts all the time, (h, g) is the abstaining version of the algorithm described in section II-C and

Ĉ0-d-1 [(h, g) (x i ) , y i ] = 1 10 10 j=1 C 0-d-1 (h, g) j (x i
) , y i is used to denote the average cost achieved by the 10 copies of the abstaining regressor (this point is explained thereafter) on the particular observation (x i , y i ).

Recall that both abstaining and base versions of the algorithm are updated in the same way and will thus result in the same hypothesis h learned, regardless of the output of the selection function g. Thus, the 10 copies of the abstaining regressor will have learned exactly the same hypothesis h but might output different predictions from each other. This is the case because there is an element of randomness associated with some of the reliability estimators which we chose to overcome by averaging the results of the 10 copies.

The percentage of improvement from the fully predicting version to the abstaining version was then computed as:

improvement = - abs diff × 100 n i=1 C 0-d-1 (h base (x i ) , y i )
Thus, on each dataset, a negative value (e.g. -10.3) indicates that the algorithm that was allowed to abstain managed to achieve an overall cost which is lower (in this case 10.3% lower) than the base algorithm. Conversely, a positive number indicates that the base algorithm managed to over-perform the abstaining version.

Note: Because we are comparing the difference of performance of one base algorithm to his abstaining version, we are guaranteed that this difference can only be attributed to the decision to abstain (or not) and not by the underlying ability of a particular algorithm to learn on a given dataset.

V. SYNTHETIC DATASETS

We start by presenting each synthetic dataset and explain why it was used. We then present and discuss the results achieved. Synthetic datasets are useful to experiment in an environment where the type of drift can be controlled.

A. Presentation of the synthetic datasets

• Drifts of controlled magnitude: 2 batches of 10 datasets have been created to assess the effects of drifts with gradually increasing magnitudes and to "force" local drifts on the feature's joint density (commonly known as covariate shift). For each dataset, the dimension of the feature space was set to 2 and the number of observations generated to 1000. A unique drift was introduced at time t 501 .

For the first batch, we generated 10 datasets for which H (D t500 , D t501 ) = {0.12, 0.2, ..., 0.99} respectively. This was achieved by randomly generating 10 000 pairs of multivariate normal distributions, computing the Hellinger distance for each pair and retaining the 10 pairs which had the closest value to the desired magnitudes. The first multivariate normal distribution was then used to generate the first 500 observations whereas the second one was used for the rest of the dataset.

For the second batch, we generated 10 datasets such as

H (f t500 (X) , f t501 (X)) = {0.1, 0.2, ..., 0.98}, with f t (X)
the joint density of the features at time t. This was done by generating a random multivariate normal distribution as the joint law of (X, Y ) before the drift and deducing the laws 3 of X and (Y /X). We then randomly generated another multivariate normal distribution for the law of X after the drift and the Hellinger distance was computed between the laws of X before and after the drift. This process was also repeated 10 000 times and the 10 pairs which had the closest value to the desired magnitudes were kept. We then obtained the joint density 4 of (X, Y ) after the drift by multiplying the original conditional density Y /X with the new joint density of X. The observations after the drift were then generated with a simple rejection sampling algorithm.

• Drifts of controlled type, frequency and area of effect: In comparison to the 2 batches of datasets described previously, these 3 datasets (based on the Friedman's function [START_REF] Friedman | Multivariate Adaptive Regression Splines[END_REF]) are useful to assess the effect on the performances of different types of drifts (gradual, abrupt, local and global) and of different drift frequencies (several drifts appear on the same dataset).

In this case, there are 10 continuous attributes and their values are independently distributed with uniform distribution on [0, 1]. The first 5 attributes are used to compute the target value whereas the last 5 are useless. The basic target value is computed as follows: y = 10sin (πx 1 x 2 ) + 20 (x 3 -0.5)

2 + 10x 4 +5x 5 +σ with σ ∼ N (0, 1) a random number. 3 datasets of 1000 observations were implemented, following the work of Ikonomovska [START_REF] Ikonomovska | Algorithms for Learning Regression Trees and Ensembles on Evolving Data Streams[END_REF]:

Local expending abrupt drift: In this dataset, 3 local drifts are introduced at times, t 251 , t 501 and t 751 . From t 1 to t 250 , the goal is to learn the initial Friedman's function. A local drift is then introduced at time t 251 such as ∀x ∈ R 1 = {x 2 < 0.3 ∧ x 3 < 0.3 ∧ x 4 > 0.7 ∧ x 5 < 0.3}, y R1 = 10x 1 x 2 + 20 (x 3 -0.5) + 10x 4 + 5x 5 + σ. If x / ∈ R 1 , the target value is unchanged. At time t 501 , a second local drift is introduced on R 2 , such as ∀x ∈ R 2 = {x 2 > 0.7 ∧ x 3 > 0.7 ∧ x 4 < 0.3}, y R2 = 10cos (x 1 x 2 ) + 20 (x 3 -0.5) + e x4 + 5x 2 5 + σ and R 1 is further expended by removing the last inequality from its definition (x 5 < 0.3). Finally, at time t 751 , a third local drift is introduced by further expending R 1 and R 2 . In both cases, the last inequalities from their modified definitions are removed (x 4 > 0.7 and x 4 < 0.3 respectively).

Global reoccurring abrupt drift: In this dataset, the drifts appear over the whole input space X . There are 2 drifts at times, t 501 and t 751 . The new target function after the first drift is y gl = 10sin (πx 4 x 5 ) + 20 (x 2 -0.5)

2 + 10x 1 + 5x 3 + σ whereas it reverts to the initial target function after the second drift.

Global and slow gradual drift: Here, two gradual drifts are introduced at times t 501 and t 751 . In order to simulate a gradual drift, the observations are generated in parallel according to 2 different concepts and the sigmoid function is used for the probability of selecting one concept over the other. At time t 501 , a new target function is introduced • Comparison between stable and drifting concept: Here the goal was to assess which performances could be achieved when the concept remains stable and to compare the difference in performance when a drift is introduced on this same dataset.

To this end, 2 datasets based on the regression version of the hyperplane generator (Shaker and Hullermeier [START_REF] Shaker | IBLStreams: A system for instance-based classification and regression on data streams[END_REF]) have been created. This generator randomly creates a d-dimensional hyperplane in a unit hyper-cube. The goal here is to predict the distance of each observation received to the hyperplane. In our experiment, both datasets have a feature space of dimension 8 and holds 1000 observations. The first dataset has been generated according to a single stable concept whereas the second one is strictly identical (i.e. it has exactly the same observations), up to time t 501 where a single abrupt drift is introduced. The drift was introduced by generating another random hyperplane in the hypercube.

B. Results achieved on the synthetic datasets

The improvements (as defined in section IV-D) achieved on each dataset and by each learner are presented in Fig. 2. As previously stated, a negative value indicates that globally the performances of the learners were improved by abstaining whereas a positive value indicates that the performances of the base versions were better. The values used for the -tube cost function, the confidence thresholds, the size of each dataset and the number of drifts included in them are given in table II.

• Influence of the drift's type on the performances: Despite the large variety of drifts (global, local, abrupt, gradual, different magnitudes ...) reproduced, the results of the experiments globally indicate that the proposed method is able to significantly improve the performances of the underlying algorithm (up to -43% on the hyperplane dataset) regardless of the type of the drift. This further indicates that abstaining should be considered when dealing with data streams subject to concept drifts.

Mixed results were achieved when there was no drift at all (on the hyperplane dataset with no drift), with 3 learners out Fig. 2. Percentage of reduction in the overall cost gained by allowing the algorithm to abstain. The upper plot is for a low whereas the lower plot is for a high . of 4 for which the performance was significantly improved in the case of a small and only 2 learners out of 4 had better results when was high.

• Analysis of the results against the learner used:

The improvement in the overall performance can change widely from one learner to the other (when the dataset and are fixed), especially for a small . For instance, on the hyperplane dataset with one drift, for a small , the abstaining version of IBLStream managed to improve the performances by 43% whereas the performances were only improved by 3% for AMRulesRegressor. Overall, despite their drift handling capabilities, the proposed method managed to improve the performances of the 4 algorithms by allowing them to abstain. The algorithm which in general, benefited the most from abstention was IBLStream whereas the one that benefited the least was RandomRules.

• Analysis of the results against the value of used: Intuitively, when is small, it is harder for the learner to predict within the -tube and thus the number of wrong predictions increases. The results suggest that in this case, the REs globally managed to filter some of the predictions that would not have met the precision constrain as the abstaining version overperformed the fully predicting version on most of the datasets (an overall increase in the cost would have suggested that the predictions filtered by the REs met the precision constrain). On the other hand, when is large, the confidence threshold increases and most of the predictions are not filtered by the REs anymore. This leads to overall performances which are globally equal to the performances obtained when predicting all the time.

In order to further assess the effect that the required precision threshold has on the performance of the proposed method, we have conducted an in depth analysis on the Hyperplane Regression dataset with one drift using different thresholds ( = {0.02, 0.04, 0.06, 0.08, 0.1, 0.15, 0.2, 0.3}). For each , the improvement (defined in section IV-D) was computed.

We also added the best (respectively worst) improvement for each learner, which was computed using the abstaining copy of the learner which achieved the smallest (respectively largest) overall cost with hindsight. In other words, when computing the value of abs diff (defined in IV-D),

Ĉ0-d-1 [(h, g) (x i ) , y i ]
was replaced by C 0-d-1 (h, g) j (x i ) , y i where the j th copy verifies: ∀k ∈ {1, ..., 10} :

n i=1 C 0-d-1 (h, g) j (x i ) , y i ≤ n i=1 C 0-d-1 [(h, g) k (x i ) , y i ]
(respectively ≥).

The shape of the curves obtained in Fig. 3, further proves that the interest for abstaining is correlated to the value of . The results also show that for half of the tested algorithms, abstaining never led to worse performances (regardless of the value of ) whereas for the other half, there is only a limited range of values for which the averaged overall cost increased (the worst case is 3.78% for = 0.1 with IBLStream). Finally, apart from AMRulesRegressor for which the variability between the abstaining copies was the largest (for = 0.02, the best abstaining copy reduced the overall cost by 9.9% whereas the worst copy increased the overall cost by 8%), the variability observed within the abstaining versions of the other learners remained globally limited.

• Evolution of the improvement over time: We also studied the evolution of the difference in performances over time between the base and the abstaining version of an algorithm. Because of the lack of space, we only show here the evolution of the results in the case of the RandomRules algorithm on the 0.9-(X) and Fried Global Reoccurring Abrupt Drift datasets (respectively upper and lower plot of Fig. 4) with a small .

To obtain these plots, we started by computing the summed costs of each version of the algorithm on a rolling (but non overlapping) window of 10 observations. In the case of the abstaining version, we further averaged the sum. The plots show that there are periods of time where abstaining clearly improves the performance and periods of time where it makes no difference.

Each RE has its own strengths and weaknesses and is designed to estimate a particular aspect of what makes a prediction reliable. For instance, the similarity-based reliability estimate will efficiently discard observations leading to a large prediction error when the recent observations also had a large prediction error whereas the local sensitivity reliability estimate will use the estimated "flatness" of the values taken by target variable on a small area to decide whether to abstain or not. Thus, periods of over-performance of the abstaining algorithm are difficult to explain because they are the result of a combination of factors that led the ensemble of REs to accurately filter the predictions that would have led to a prediction error larger than the -tube.

These factors can appear under a stationary concept (for instance, between t 250 and t 400 on the 0.9-X dataset5 ) and will not necessarily appear because the concept has drifted (for instance, on the Fried G.R.A. dataset, the gradual drift introduced at t 501 left the performances of the base and abstaining version exactly similar up to t 650 ). However, the plots back our claim that when the concept drifts, allowing the algorithm to abstain can improve the performances and therefore that it should be considered as a performance enhancing technique.

Fig. 1 .

 1 Fig. 1. Target range (left) and payoff function (right) of a Binary Option Tunnel

Fig. 3 .

 3 Fig. 3. Comparison of the average percentage of reduction in the overall cost as a function of the value of . Error bars indicate the performance achieved with the best (respectively worst) copy of the abstaining algorithm.

  Formally: s base k := k×10 i=(k-1)×10+1 C 0-d-1 (h base (x i ) , y i ) and ŝabs k k,j , with k = {1, 2, ..., 100}, s abs k,j the summed cost of the j th copy of the abstaining algorithm on the observations {(k -1) × 10 + 1, ..., k × 10}. The values shown on each plot are s base k -ŝabs k . Thus, a positive number indicates that the cost of the abstaining algorithm is lower than the base version whereas a negative number indicates that the base overperformed the abstaining version.

TABLE I .

 I

	PARAMETERS USED FOR THE RELIABILITY ESTIMATORS
		k	δ
	R M SE	10	-
	R LSA	5	δ ∼ N (0, 0.1)
	R DP C	10	∀i, j : δi,j ∼ N (0, 0.1)
	R BAG	10	-

In this case, X is also a multivariate normal distribution.

Note that in this case, the joint density (X, Y ) is not necessarily a multivariate normal distribution. Consequently, there is more diversity in the set of joint densities considered than in the first batch.

Remember that this dataset has an unique and abrupt drift at time t 500 and that the concept is stable before and after.

VI. REAL LIFE DATASETS WITH CONCEPT DRIFTS

Following up on our introductory real life example presented in section II-B, we ran a batch of experiments on several financial datasets. These datasets were chosen because they provide real life examples of streams subject to concept drifts.

A. Presentation of the real datasets

Each dataset is based on a particular financial asset (a stock, an index of stocks, a precious metal an exchange rate between 2 currencies) and has 7 attributes. The first 5 attributes are based on the observation of the opening price, highest price, lowest price, closing price and volume of transaction for that asset on a given day. For the last 2 attributes, we have added the average as well as the variance computed with the closing prices of the last 10 days.

Our framework assumes that the observations are independent realizations of a single hidden concept (when the concept is stable) or independent realizations of a set of concepts (when the concept drift). In both cases, the observations are assumed to be independent from each other. Unfortunately, this assumption clearly doesn't hold in the case of time series where the value of an observation at time t depends on its value at time t -1. Therefore, we chose to transform the time series of the 7 attributes into series of returns which can be assumed to be independent from each other.

The transformation was done as follows: for a given time series {p t1 , ..., p tn }, we have computed the return:

for each time t ∈ {t 2 , ..., t n }, where p t is the value of the time series at time t. Thus, at time t, the learner receives an observation

B. Results achieved on the real datasets

We give the results achieved on the real life datasets with a small (see Fig. 5) which is in line with the goal of the investor (the narrower the tube, the larger the expected payout of the option). All the results indicate that allowing abstention led to an improvement of the performances and tend to confirm what was observed on synthetic datasets. This good performance is explained by the increased difficulty to accurately predict on extremely noisy datasets subject to a wide range of drifts.

In order to concretely describe what these results mean for our investor, we calculate the amount of money that he would have saved by allowing his machine learning algorithm (IBLStream) to abstain on the stock of Apple. To this end, we chose to use a cost function which attributes fixed values to the price and the payout of the created binary tunnel option as well as the cost of abstaining. In real life, the true price of such option would be calculated with complicated formulas which depends on many factors (such as the volatility and price of the underlying asset, the time until expiration, the selected boundaries, ...) and which we omit for the sake of simplicity.

Therefore and without loss of generality, assume that the investor has an initial capital of 10 000C, that the price of the option is always equal to 1C (the amount of money lost if the prediction is wrong), that the payout (i.e. the amount of money received if the prediction is correct) is always 1 C and that if the investor chooses to abstain, he will leave the money at the bank which will charge him a fixed 0.1 C overnight. Thus, the cost function is then given by:

In this case the version of the algorithm which predicts all the time managed to output 1483 good predictions and 7437 wrong predictions. This results in a final capital of 4046 C. On the other hand, the abstaining version of the algorithm gave 533 wrong predictions, 162 good predictions and abstained on 8225 observations resulting in a final capital of 8806.5 C. Thus, by allowing its algorithm to abstain, the investor managed to save almost 50% of its initial capital (note that the performance is better than the -37.4% achieved in the experiment because the cost of abstention in this illustration is smaller).

VII. CONCLUSION

Learning on a data stream subject to concept drifts is a challenging task. Drifting concepts can significantly diminish the performance of a learner over time and undermine the confidence in the outputted predictions. This is an issue, especially in the regression setting when there are requirements on the expected precision level associated with each prediction.

In this paper, we claim that when costs can be associated with good and bad predictions, allowing a predictor to abstain must be considered in order to reduce the overall prediction cost. To this end, we propose a generic method which can be used with any regressor and which filters the predictions that would not have met the precision constraint.

We experimented this strategy on 30 datasets including different types of drifts, with 4 state of the art algorithms and with 2 levels of expected precision. We assessed the performance of our method by comparing the overall prediction cost of the base version of an algorithm (which predicts all the time) to the performance of the same algorithm equiped with the proposed method (which allows it to abstain when the confidence is not high enough). Globally, the results indicate that when the need for precision is high, allowing the algorithm to abstain significantly improves the overall prediction cost whereas when the need for precision is low, the overall prediction cost is the same as the one achieved by predicting all the time. Furthermore, the evolution of the difference in performance over time between the base version and the abstaining version of each regressor showed that, concept drifts can be the cause of an over-performance of the abstaining version and therefore that abstaining must be considered as an enhancing method to reduce the overall prediction cost. Indeed, when the required precision level cannot be achieved, allowing the algorithm to abstain based on an ensemble of reliability estimators acts as an automatic way to "disconnect" the algorithm during some of these adverse periods.

In future works we will investigate whether the performances can be further improved by abstaining to update the learned model with the observations for which the prediction has been rejected.


Tommaso Lorenzi

Alexander Lorz
email: alexander.lorz@upmc.fr

Benoît Perthame
email: benoit.perthame@upmc.fr

ON INTERFACES BETWEEN CELL POPULATIONS WITH DIFFERENT MOBILITIES

Keywords: 2010 Mathematics Subject Classification. 35C07, 35B35, 35B36, 92C10 Cell populations, Tissue growth, Cancer invasion, Interfaces, Travelling waves, Pattern formation

Partial differential equations describing the dynamics of cell population densities from a fluid mechanical perspective can model the growth of avascular tumours. In this framework, we consider a system of equations that describes the interaction between a population of dividing cells and a population of non-dividing cells. The two cell populations are characterised by different mobilities. We present the results of numerical simulations displaying two-dimensional spherical waves with sharp interfaces between dividing and non-dividing cells. Furthermore, we numerically observe how different ratios between the mobilities change the morphology of the interfaces, and lead to the emergence of finger-like patterns of invasion above a threshold. Motivated by these simulations, we study the existence of one-dimensional travelling wave solutions.

1. Introduction. Partial differential equations (PDE) describing the dynamics of cell population densities from a fluid mechanical perspective can model the growth of avascular tumours [START_REF] Araujo | A history of the study of solid tumour growth: the contribution of mathematical modelling[END_REF][START_REF] Preziosi | Cancer modelling and simulation[END_REF][START_REF] Roose | Mathematical models of avascular tumor growth[END_REF]. These models rely on the observation that, when in mechanical contact with other cells, proliferating cells exert a pressure on their neighbours. This pressure results in a mechanical form of cell motion (i.e. neighbouring cells are pushed and forced to move) and, above a certain threshold, it can also induce quiescence due to competition for space [START_REF] Brú | The universal dynamics of tumor growth[END_REF][START_REF] Drasdo | Modeling the impact of granular embedding media, and pulling versus pushing cells on growing cell clones[END_REF][START_REF] Ranft | Fluidization of tissues by cell division and apoptosis[END_REF].

Such PDEs can be used to investigate possible mechanisms that underlie cancer invasion, such as: the effects of local pressure gradients which are generated by proliferation and competition for space and resources; conditions for preserving the initial radial symmetry of the tumour, and conditions for developing irregular shapes and invading the surrounding tissue [START_REF] Ambrosi | On the mechanics of a growing tumor[END_REF][START_REF] Baratchart | Computational modelling of metastasis development in renal cell carcinoma[END_REF][START_REF] Byrne | Individual-based and continuum models of growing cell populations: a comparison[END_REF][START_REF] Byrne | Modelling solid tumour growth using the theory of mixtures[END_REF][START_REF] Byrne | Growth of necrotic tumors in the presence and absence of inhibitors[END_REF]. Moreover, it is now known that models of this type are equivalent, in the incompressible limit, to models of tumour growth which are formulated as free boundary problems [START_REF] Perthame | Derivation of a hele-shaw type system from a cell model with active motion[END_REF][START_REF] Perthame | The hele-shaw asymptotics for mechanical models of tumor growth[END_REF].

In this framework, we consider a PDE model describing the time dynamics of a population of dividing cells and a population of non-dividing cells, coupled by pressure forces. The two populations are characterised, respectively, by the local density of dividing cells m and the local density of non-dividing cells n, governed by the following system of equations:

   ∂ t m -µ div(m ∇p) = G p m, ∂ t n -ν div(n ∇p) = 0. (1)
The second terms on the left hand sides model the tendency of cells to move down pressure gradients, and rely on the definition of the cell velocity fields through Darcy's law [START_REF] Byrne | Modelling the role of cell-cell adhesion in the growth and development of carcinomas[END_REF][START_REF] Greenspan | On the growth and stability of cell cultures and solid tumors[END_REF]. The parameters µ > 0 and ν > 0 stand for the mobility (i.e. the quotient of permeability and viscosity) of dividing cells and non-dividing cells, respectively. In the compressible description, the pressure p is given by a constitutive relation whose desirable properties are discussed, for instance, in [START_REF] Ciarletta | The radial growth phase of malignant melanoma : muti-phase modelling, numerical simulation and linear stability[END_REF]. For simplicity, we follow the lines of [START_REF] Byrne | Individual-based and continuum models of growing cell populations: a comparison[END_REF] and [START_REF] Perthame | The hele-shaw asymptotics for mechanical models of tumor growth[END_REF], and we use the constitutive relation

p := K γ (n + m) γ , K γ := γ + 1 γ , (2)
where the parameter γ ≥ 1 controls the stiffness of the pressure law. Finally, the net growth rate G satisfies

G • < 0, G P M = 0. (3)
Assumptions (3) mean that competition for space decreases the cell division rate according to the local pressure. The parameter P M > 0 models the threshold pressure above which dividing cells are entering a quiescent state (i.e. the so-called homeostatic pressure) [START_REF] Byrne | Individual-based and continuum models of growing cell populations: a comparison[END_REF][START_REF] Ranft | Fluidization of tissues by cell division and apoptosis[END_REF].

It is worth noting that, if we use m for the local density of cancer cells within a solid tumour and n for the concentration of cells in homeostatic equilibrium that surround the solid tumour, the case µ > ν is the most biologically relevant one. In fact, the loss of junctional contacts, such as the loss of E-cadherin mediated adhesion induced by the nuclear up-regulation of soluble β-catenin [START_REF] Ramis-Conde | Modeling the influence of the e-cadherin-β-catenin pathway in cancer cell invasion: a multiscale approach[END_REF], endows cancer cells with a much higher mobility compared to the cells of the surrounding tissues.

Also, some biological scenarios are not captured by the system of equations under study. For instance, there are other PDE models for the dynamics of dividing and non-dividing cells which allow cells to pass from one state to the other, and include a death term for non-dividing cells as well. We refer the interested reader to [START_REF] Friedman | A hierarchy of cancer models and their mathematical challenges[END_REF][START_REF] Sherratt | A new mathematical model for avascular tumour growth[END_REF], and references therein.

Our work follows earlier papers that are devoted to study the existence of travelling wave solutions with composite shapes and discontinuities for cell-density models of avascular tumour growth [START_REF] Perthame | Derivation of a hele-shaw type system from a cell model with active motion[END_REF][START_REF] Perthame | The hele-shaw asymptotics for mechanical models of tumor growth[END_REF][START_REF] Tang | Composite waves for a cell population system modeling tumor growth and invasion[END_REF]. These papers consider one single nonlinear PDE, while we deal with a nonlinear strongly-coupled system of PDEs. This represents a novel fundamental difficulty, and the current literature still lacks a systematic characterisation of such systems of equations, with the exception of semilinear cooperative systems. In this respect, it has been speculated that the system (1) could exhibit various behaviours depending on the values of the parameters µ and ν [START_REF] Drasdo | Modeling the impact of granular embedding media, and pulling versus pushing cells on growing cell clones[END_REF]. A first observation is that segregation can occur: dividing and non-dividing cells remain well separated through a sharp interface. Phenomena of this type have already been analyzed for related parabolic systems [START_REF] Dancer | Spatial segregation limit of a competition-diffusion system[END_REF][START_REF] Mimura | Reaction diffusion modelling of bacterial colony patterns[END_REF]. Furthermore, twodimensional spherical waves could be stable in the case when µ < ν, while they could become unstable for µ > ν. The rationale behind this intuition is that, since mobility is inversely proportional to viscosity, the case µ > ν corresponds to the situation where one "less viscous fluid" (dividing cells) expand into a "more viscous fluid" (non-dividing cells). This might trigger the emergence of patterns that would be reminiscent of the viscous fingering resulting from Saffman-Taylor-like instabilities [START_REF] Saffman | The penetration of a fluid into a porous medium or heleshaw cell containing a more viscous liquid[END_REF], i.e. those instabilities that can be observed when a less viscous fluid is injected into a more viscous fluid in a radial Hele-Shaw cell.

The aforementioned intuitions are supported by our numerical simulations which we report in Section 2. They display sharp interfaces and show that two-dimensional spherical waves are stable for µ < ν and can be unstable for µ > ν. Motivated by these results, our goal here is to investigate the profile of one-dimensional travelling waves for the system (1) by using numerical simulations and qualitative analyses.

One-dimensional travelling waves may provide a tractable way to explain both segregation and the profiles of two-dimensional spherical waves through, for instance, transversal instability [START_REF] Kowalczyk | Transversal instability for the thermodiffusive reaction-diffusion system[END_REF]. They are solutions of the form m(x, t) = m(x -σ t) and n(x, t) = n(x -σ t), where the constant σ > 0 represents the travelling wave velocity. Substituting these travelling wave ansatz into equations [START_REF] Ambrosi | On the mechanics of a growing tumor[END_REF] gives

-σm -µ (m p ) = G(p) m, (4)
-σn -ν (n p ) = 0.

An observation we will use throughout our analysis is that, since p vanishes at ±∞, equation ( 5) gives

(σ + ν p ) n = σ n ∞ , n -→ x→±∞ n ∞ . (6)
In Section 3, we construct travelling wave solutions such that, in (6), we have n ∞ = 0 for all values of µ and ν. These solutions have compact support in n, and they display a remarkable qualitative difference between the cases µ < ν (when they exhibit a segregation effect) and µ > ν (when stable mixing occurs). Notice that any two functions m and n such that K γ (n + m) γ = P M are solutions in the case where σ = 0. In Section 4, we extend the construction to the case where n ∞ > 0. In this setting, travelling wave solutions still exist but they are numerically unstable objects, and a numerical constraint has to be imposed to capture them.

2. Numerical observations. Based on numerical simulations, we first investigate the behaviour of two-dimensional spherical waves that, as mentioned before, can be unstable for µ > ν. To this end, we numerically solve the mathematical problem defined by completing (1) with zero Neumann boundary conditions and the following initial conditions, which mimic a biological scenario where dividing cells expand in an embedding medium made of non-dividing cells: m(x, y, t = 0) := a m e -bm (x 2 +y 2 ) and n(x, y, t = 0) := a n e -bn (x 2 +y 2 ) ,

with

a m = 0.1, a n = 0.8, b m = 5 × 10 -1 , b n = 5 × 10 -7 .
Moreover, in view of the considerations drawn in [START_REF] Drasdo | Modeling the impact of granular embedding media, and pulling versus pushing cells on growing cell clones[END_REF][START_REF] Tang | Composite waves for a cell population system modeling tumor growth and invasion[END_REF], and to satisfy assumptions (3), we use the following definition for the net growth rate G:

G p := 200 π arctan 4 (P M -p) + , P M = 30. ( 8
)
Finally, in line with the ideas presented in [START_REF] Perthame | Derivation of a hele-shaw type system from a cell model with active motion[END_REF][START_REF] Perthame | The hele-shaw asymptotics for mechanical models of tumor growth[END_REF], we choose γ = 30 (i.e. we focus on the incompressible limit γ → ∞).

Numerical computations are performed in Matlab. We select a uniform discretisation consisting of 450 2 points on the square [-L, L] × [-L, L], with L = 45, as the spatial domain. The method for calculating numerical solutions is based on a time splitting scheme between the conservative parts and the reaction term. A finite volume method is used for solving the conservative parts. Convection terms are approximated through an upwind scheme, and the cell edge states are calculated by means of a high order extrapolation procedure [START_REF] Leveque | Finite volume methods for hyperbolic problems[END_REF].

The numerical results are summarised in Fig. 1 and Fig. 2. These results highlight how variations in the parameters µ and ν can lead to major changes in the morphology of the interface between dividing cells and non-dividing cells. Both figures show that the additional mass generated by cell divisions induces a pressure gradient that moves the dividing-cell population against non-dividing cells. On the one hand, when µ < ν, we observe the emergence of a spherical wave of dividing cells pushing the surrounding non-dividing cells (see left panel in Fig. 2), and the creation of an invasive front made of non-dividing cells that are induced to move by the expansion of dividing cells (see right panel in Fig. 1). On the other hand, when µ > ν, the non-dividing cells cannot move away with the same speed as the growth front. This triggers the formation of dendrites made of dividing cells that protrude through and dislocate the surrounding non-dividing cells. As a result, finger-like patterns of invasion emerge (see Fig. 2). Theorem 3.1. For all values of µ, ν and for M > 0 given, there are a speed σ and a width r > 0 such that a solution of (4)-( 5), ( 9) exists, with m non-increasing, discontinuous at x = 0, and such that n satisfies r 0 n(x)dx = M > 0 (given mass).

The pressure has a kink at x = 0 with sgn(p (0)) = sgn([p ]) = sgn(ν -µ). The construction gives a limit as γ → ∞ (Hele-Shaw or incompressible limit), and the speed satisfies

0 < σ < νP M M .
The numerical solution obtained for µ < ν is shown in Fig. 4. If µ > ν, this travelling wave solution is unstable, as it can be seen very intuitively by using the proof below. Take a small perturbation of n near x = 0, for which n > 0 in region II. Such perturbation will move with a velocity close to -νp (0 + ) < -νp (0 -) (see condition [START_REF] Leveque | Finite volume methods for hyperbolic problems[END_REF]). This means that the perturbation will further separate from the main core rather than join it. The numerical solution obtained for µ > ν is presented in Fig. 5. This figure displays a transient regime after which n is left behind and m propagates alone (see also Supplementary Movie S1) with a profile analogous to that observed in the case where n = 0. Such a profile resembles that of travelling wave solutions to combustion models with non-linear diffusion which has been previously presented by Berestycki et al. [START_REF] Berestycki | Traveling wave solutions to combustion models and their singular limits[END_REF].

Proof. As depicted in Fig. 3, we work on two regions: region I that coincides with [0, r] = Supp(n), and region II that is defined as (-∞, 0]. We use a shooting argument for the parameter σ that we fix at the beginning.

Step 1. Since we are considering the case n ∞ = 0, (6) implies (σ + νp )n = 0. In region I, as n > 0, this leads to

p = - σ ν , p(x) = σ ν (r -x), 0 ≤ x ≤ r; (10)
and therefore,

p(0) = σr ν . (11)
The mass conservation gives the value of r by

r 0 n(x)dx = r 0 1 K γ p(x) 1/γ dx = 1 K γ 1/γ σ ν 1/γ γ γ + 1 r 1+γ γ = M. (12)
Step 2. Adding equations ( 4) and ( 5), we obtain

-σ(m + n) -((µm + νn)p ) = mG(p). (13)
Moreover, in region II, since n ≡ 0, we can rewrite equation ( 4) as

-σp -µ(p 2 + γpp ) = γpG(p), (14)
and the solution has to satisfy p(-∞) = P M [START_REF] Kowalczyk | Transversal instability for the thermodiffusive reaction-diffusion system[END_REF] and boundary condition ( 11) at x = 0. By the maximum principle p cannot have a local minimum therefore p (x) < 0 for x < 0. So the solution p is larger than p(0) on (-∞, 0) and the equation ( 14) is non-degenerate. Therefore the solution p is continuous on (-∞, 0) and there is a point x 0 < 0 such that p (x 0 ) > -∞.

Multiplying equation ( 13) by p and integrating over a bounded interval (x 0 , r) gives

r x0 (µm + νn) p 2 dx ≤ r x0 m G(p) pdx -(µm + νn)pp (x 0 ) < ∞,
since m and p are bounded. Therefore, p ∈ L 2 loc (x 0 , r) and so p is continuous; as a consequence, m + n is continuous as well. This also means that m(0 -) = n(0 + ).

Step 3. Integrating equation ( 13), we obtain

-σ(m + n)(x) -((µm + νn)p )(x) = r x G(p) mdy.
Using (10) and step 2, and by the continuity of p and m + n, we deduce the jump condition at 0 by

((µm + νn)p )(0 -) = ((µm + νn)p )(0 + ), p (0 -) = ν µ p (0 + ) = - σ µ . (16)
Step 4. Here we want to show monotonicity of p in σ. To this end, let us define F (p) := pG(p) and q := ∂p ∂σ . Deriving equation ( 14) w.r.t. σ we obtain -σq -µ(2p q + γqp + γpq ) = γ dF dp q + p (17) with q(-∞) = 0 and q (0) = -1 µ .

Deriving equation ( 14) w.r.t. x we obtain

-σ(p ) -µ(2p (p ) + γ(p )p + γp(p ) ) = γ dF dp p (18)
with p (-∞) = 0 and p (0) = -σ µ .

We rewrite equations ( 17) and ( 18) as -σq -µ(a 1 q + a 2 q + a 3 q ) = a 4 q + p and -σ(p ) -µ(a

1 (p ) + a 2 (p ) + a 3 (p ) ) = a 4 (p ),
where the coefficients a i are implicitly defined. So we view the equations ( 17) and [START_REF] Perthame | Derivation of a hele-shaw type system from a cell model with active motion[END_REF] as linear in q and p , respectively. Now, the function 1 σ p satisfies the boundary condition of equation [START_REF] Mimura | Reaction diffusion modelling of bacterial colony patterns[END_REF]. Since there is the additional negative term p on the right-hand side of the equation on q, we have ∂p ∂σ = q ≤ 1 σ p ≤ 0. With this monotonicity it follows that the overdetermined problem at hand has a unique solution for a single value σ. More precisely, we choose a σ and solve equation [START_REF] Greenspan | On the growth and stability of cell cultures and solid tumors[END_REF] with the boundary conditions ( 15) and ( 16) to obtain p. Then we rewrite equation [START_REF] Drasdo | Modeling the impact of granular embedding media, and pulling versus pushing cells on growing cell clones[END_REF] as

r = M γ 1+γ C γ σ ν -1 1+γ ,
where we implicitly define the constant C γ . Plugging this expression for r in condition [START_REF] Dancer | Spatial segregation limit of a competition-diffusion system[END_REF] we obtain

p(0) = M γ 1+γ C γ σ ν γ 1+γ . (19)
In order to find (σ, p) such that also this condition is satisfied, we use that the right-hand side of ( 19) is increasing in σ and that p(0) is strictly decreasing in σ.

In this way we obtain a unique solution (σ, p).

Step 5. One can go further in the Hele-Shaw (incompressible) limit γ → ∞. In fact, equation ( 14) is then reduced to find a solution of

-µp σ = G(p σ ), p σ (-∞) = P M , p σ (0) = σ ν M, (20)
which we have to match with the condition p σ (0) = -σ µ . Now we show that such a value of σ is unique.

The above semilinear elliptic problem is standard and there is a unique solution of [START_REF] Preziosi | Cancer modelling and simulation[END_REF]. By the comparison principle (which holds true because G (•) < 0), we know that, for σ 1 < σ 2 , we have p σ1 < p σ2 . Additionally, as p σ < 0, we deduce that p σ < 0, and thus we conclude that the profile is decreasing. Furthermore, by integration

p σ (0) = 0 -∞ p σ dx = - 1 µ 0 -∞ G(p σ ) dx.
From the monotonicity in σ of p σ and because G ≤ 0, we deduce that p σ (0) is an increasing function of σ, while σ → -σ µ is decreasing. This proves a unique possible match.

Finally, for σ * ν M = P M , we have p σ * ≡ P M , and thus p σ * (0) = 0. For σ = 0, we have p σ (0) < 0, and this allows us to conclude that there exists a value σ such that p σ (0) = -σ µ .

4. An extension with n ∞ = 0. We now provide a case where segregation does not hold but a sharp interface is still present. In particular, we consider the case where n does not vanish at infinity, that is, we impose the conditions

n(x) -→ x→±∞ n ∞ , p(-∞) = P M , Supp(m) = (-∞, 0], Supp(n -n ∞ ) = [0, r], (21)
with n ∞ > 0.

Theorem 4.1. Let µ, ν, n ∞ with K γ n γ ∞ < P M and M > 0 be given. There are speeds σ and cell densities n 0 > n ∞ such that the solution of (4)-( 5) exists, satisfies the boundary conditions [START_REF] Ramis-Conde | Modeling the influence of the e-cadherin-β-catenin pathway in cancer cell invasion: a multiscale approach[END_REF], with m non-increasing, and such that n satisfies

n(x) > n ∞ ∀x > 0, ∞ 0 [n(x) -n ∞ ]dx = M > 0 (given mass).
The pressure has a kink at x = 0 with sgn(p (0)) = sgn([p ]) = sgn(ν -µ).

Proof. We use the same notations as in Section 3. In region I i.e. [0, ∞), we can rewrite equation [START_REF] Byrne | Growth of necrotic tumors in the presence and absence of inhibitors[END_REF] as

νp = νγn γ-1 n = σ n ∞ n -1 . (22)
Therefore, starting from a value n(0) = n 0 > n ∞ , n is decreasing to n ∞ with exponential decay.

Notice that we can write n(x) = N σ ν x with N the (parameter independent) solution of

N = n ∞ -N γN γ , N (0) = n 0 .
By an immediate monotonicity argument, we can fix uniquely n 0 through the mass condition

M = ∞ 0 N σ ν x dx = ν σ ∞ 0 N (x)dx, ∞ 0 N (x)dx = σ ν M.
In other words, there is a function N 0 such that

n 0 := N 0 M σ ν , and
d dz N 0 (z) > 0, N 0 (z) -→ z→∞ ∞, N 0 (0) = n ∞ .
As before, we complete in region II for x < 0. Since m(0 -) = n 0 -n ∞ (no jump on p and on m + n), we can find again the jump condition on p (0) and thus achieve, see condition [START_REF] Friedman | A hierarchy of cancer models and their mathematical challenges[END_REF], Therefore, thanks to [START_REF] Ranft | Fluidization of tissues by cell division and apoptosis[END_REF], we find

(µm + νn)p (0) = 0, p (0 -) p (0 + ) = µm + νn (0 + ) µm + νn (0 -) = νN 0 M σ ν µ N 0 M σ ν -n ∞ + νn ∞ .
p (0 -) = - σ µ 1 - νn ∞ µ N 0 M σ ν -n ∞ + νn ∞ . (24)
Then, it remains to solve the equation for m, or equivalently p since n = n ∞ , that is [START_REF] Greenspan | On the growth and stability of cell cultures and solid tumors[END_REF]. It comes with the overdetermined conditions p(-∞) = P M , p(0) = K γ N 0 M σ ν γ and [START_REF] Saffman | The penetration of a fluid into a porous medium or heleshaw cell containing a more viscous liquid[END_REF]. The monotonicity argument remains true and thus the solution is again unique and m is decreasing.

For µ > ν, we have

p (0 -) p (0 + ) ≤ νN 0 M σ ν ν N 0 M σ ν -n ∞ + νn ∞ = 1.
The travelling wave solution of Theorem 4.1 is highly numerically unstable, and we have to impose a numerical constraint to capture it, that is, we solve

   ∂ t m -µ div(m ∇p) = G p m, ∂ t n -ν div(n ∇p) = n -n ∞ + , (25)
instead of solving [START_REF] Ambrosi | On the mechanics of a growing tumor[END_REF]. The numerical solution obtained for µ < ν is shown in Fig. 6. If µ > ν, the numerical results summarised in Fig. 7 suggest that the travelling wave solution becomes unstable, and the sharp interface of Theorem 4.1 cannot propagate.

Figure 1 .

 1 Figure 1. Numerical observations in the case µ < ν. Plots of the computed m (left panel) and n (right panel) at time t = 1 for ν = 2 and µ = 1. We observe the emergence of a spherical wave of dividing cells pushing the surrounding non-dividing cells (left panel), and an invasive front made of non-dividing cells that are induced to move by the expansion of dividing cells (right panel).

Figure 2 .

 2 Figure 2. Numerical observations in the case µ > ν. Plots of the computed m (left panel) and n (right panel) at time t = 1 for ν = 1 and µ = 2. We observe the appearance of numerical instabilities which result in finger-like patterns of dividing cells (left panel) that protrude through and dislocate the surrounding nondividing cells (right panel).

3 . 9 )Figure 3 .

 393 Figure 3. The profile of p for the travelling wave when n has a finite support that coincides with [0, r].

Figure 4 .

 4 Figure 4. Travelling waves of Theorem 3.1 for µ < ν. Profiles of p (left panel), and m (right panel, red curve) and n (right panel, blue curve) for the travelling wave in the case where n has a compact support and µ < ν. The dashed line in the left panel highlights the value of P M , while the dashed line in the right panel highlights the value of P M /K γ 1/γ .

Figure 5 .

 5 Figure 5. Transient regime of Theorem 3.1 for µ > ν. Profiles of p (left panel), and m (right panel, red curve) and n (right panel, blue curve) in the case where n has a compact support and µ > ν. The dashed line in the left panel highlights the value of P M , while the dashed line in the right panel highlights the value of P M /K γ 1/γ . This figure shows a transient regime after which n is left behind and m propagates alone (see also Supplementary Movie S1).

Figure 6 .

 6 Figure 6. Travelling waves of Theorem 4.1 for µ < ν. Profiles of p (left panel), and m (right panel, red curve) and n (right panel, blue curve) for the travelling wave in the case where n does not vanish at infinity and µ < ν. The dashed line in the left panel highlights the value of P M , while the dashed line in the right panel highlights the value of P M /K γ 1/γ .

Figure 7 .

 7 Figure 7. Transient regime of Theorem 4.1 for µ > ν. Profiles of p (left panel), and m (right panel, red curve) and n (right panel, blue curve) in the case where n does not vanish at infinity and µ > ν. The dashed line in the left panel highlights the value of P M , while the dashed line in the right panel highlights the value of P M /K γ 1/γ .