Louis-Claude Canon

Aurélie Kong

Win Chang

Yves Robert

Frédéric Vivien

Scheduling independent stochastic tasks under deadline and budget constraints Extended Version

Keywords: independent tasks, stochastic cost, scheduling, budget, deadline, cloud platform tâches indépendantes, coût stochastique, stochastic cost, ordonnancement, budget, date d'échéance, cloud platform

This paper discusses scheduling strategies for the problem of maximizing the expected number of tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The execution times of tasks follow IID probability laws. The main questions are how many processors to enroll and whether and when to interrupt tasks that have been executing for some time. We provide complexity results and an asymptotically optimal strategy for the problem instance with discrete probability distributions and without deadline. We extend the latter strategy for the general case with continuous distributions and a deadline and we design an efficient heuristic which is shown to outperform standard approaches when running simulations for a variety of useful distribution laws.

Ordonnancement de tâches stochastiques indépendantes avec contraintes de budget et d'échéance Version étendue

Résumé : Ce rapport présente des stratégies d'ordonnancement pour le problème suivant: maximiser l'espérance du nombre de tâches indépendantes exécutées sur une plate-forme de type cloud computing, avec une double contrainte de budget et de date d'échéance. Les temps d'exécution des tâches suivent une même loi de probabilité, discrète ou continue. Il faut décider combien de processeurs mettre en oeuvre, et quand interrompre les tâches qui se sont déjà exécutées pendant une certaine durée. Nous donnons des résultats de complexité pour l'instance du problème sans échéance et avec distribution discrète, et proposons une stratégie asymptotiquement optimale. Nous étendons cette stratégie au cas général des distributions continues et avec échéance, et définissons une heuristique qui surpasse les approches usuelles pour une vaste gamme de distributions usuelles.

Ce rapport est une version étendue du rapport RR-9178 qui porte le même titre.

Introduction

This paper deals with the following problem: given an infinite bag of stochastic tasks, and an infinite set of available Virtual Machines (VMs, or processors 1 ), how to successfully execute as many tasks as possible in expectation, under both a budget and a deadline constraint? The execution times of the tasks are IID (independent and identically distributed) random variables that follow a common probability distribution. The amount of budget spent during the execution of a given task is proportional to the length of its execution. At each instant, the scheduler can decide whether to continue the execution (until success) or to interrupt the task and start a new one. Intuitively, the dilemma is the following: (i) continuing execution means spending more budget, and taking the risk of waiting very long until completion, but it capitalizes on the budget already spent for the task; (ii) interrupting the task wastes the budget already spent for the task, but enables starting afresh with a new, hopefully shorter task. Of course there is a big risk here, since the new task could turn out to have an even longer execution than the interrupted one.

In addition to deciding which tasks to interrupt and when, the scheduler must also decide how many processors to enroll (this is the resource provisioning problem). There is again a trade-off here. On the one hand, enrolling many processors is mandatory when the deadline is small and the budget is large, and it allows us to make better scheduling decisions, because we can dynamically observe many events taking place in parallel2 . On the other hand, enrolling too many processors increases the risk of having many unfinished tasks when budget runs out and/or when deadline strikes.

This difficult scheduling problem naturally arises with many applications in the context of cloud computing and data mining (see Section 2 for a detailed discussion). Informally, the goal is to extract as much information as possible from some big data set, by launching analysis tasks whose execution time strongly depends upon the nature of the data sample being processed. Not all data sample must be processed, but the larger the number of data samples successfully processed, the more accurate the analysis.

The main contribution of this work are the following: • We provide a comprehensive set of theoretical results for the problem instance with discrete distributions and no deadline. These results show the difficulty of the general scheduling problem under study, and lay the foundations for its analysis;

• We design an asymptotically optimal scheduling strategy for the above problem instance (discrete distribution, no deadline); • We design an efficient heuristic, OptRatio, for the general problem. This heuristic extends the asymptotically optimal scheduling strategy for discrete distributions to continuous ones, and accounts for the deadline constraint by enrolling the adequate number of processors. The heuristic computes a threshold at which tasks should be interrupted, which we compute for a variety of standard probability distributions (exponential, uniform, beta, gamma, inverse-gamma, Weibull, half-normal, and lognormal); • We report a set of simulation results for three widely used probability distributions (exponential, uniform, and lognormal) that demonstrate both the superiority of the OptRatio heuristic over other approaches, and its good performance with short deadlines.

Related work

This work falls under the scope of cloud computing since it targets the execution of sets of independent tasks on a cloud platform under a deadline and a budget constraints. However, because we do not assume to know in advance the execution time of tasks (we are in a non-clairvoyant setting), this work is also closely related to the scheduling of bags of tasks. We survey both topics in Sections 2.1 and 2.2. Finally, in Section 2.3, we survey task models that are closely related to our model.

Cloud computing

There exists a huge literature on cloud computing, and several surveys review this collection of work [START_REF] Bokhari | A survey on cloud computing[END_REF][START_REF] Singh | Cloud resource provisioning: survey, status and future research directions[END_REF][START_REF] Singh | A survey on resource scheduling in cloud computing: Issues and challenges[END_REF]. Singh and Chana published a recent survey devoted solely to cloud ressource provisioning [START_REF] Singh | Cloud resource provisioning: survey, status and future research directions[END_REF], that is, the decision of which resources should be enrolled to perform the computations. Resource provisioning is often a separate phase from resource scheduling. Resource scheduling decides which computations should be processed by each of the enrolled resources and in which order they should be performed.

Resource provisioning and scheduling are key steps to the efficient execution of workflows on cloud platforms. The multi-objective scheduling problem that consists in meeting deadlines and either respecting a budget or minimizing the cost (or energy) has been extensively studied for deterministic workflows [START_REF] Abrishami | Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds[END_REF][START_REF] Arabnejad | Budget distribution strategies for scientific workflow scheduling in commercial clouds[END_REF][START_REF] Byun | Cost optimized provisioning of elastic resources for application workflows[END_REF][START_REF] Calheiros | Meeting deadlines of scientific workflows in public clouds with tasks replication[END_REF][START_REF] Fard | A truthful dynamic workflow scheduling mechanism for commercial multicloud environments[END_REF][START_REF] Gao | An energy and deadline aware resource provisioning, scheduling and optimization framework for cloud systems[END_REF][START_REF] Malawski | Cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[END_REF][START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[END_REF][START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF], but has received much less attention in a stochastic context. Indeed, most of the studies assume a clairvoyant setting: the resource provisioning and task scheduling mechanisms know in advance, and accurately, the execution time of all tasks. A handful of additional studies also consider that tasks may fail [START_REF] Liu | A compromisedtime-cost scheduling algorithm in swindew-c for instance-intensive costconstrained workflows on a cloud computing platform[END_REF][START_REF] Poola | Robust scheduling of scientific workflows with deadline and budget constraints in clouds[END_REF]. Among these articles, Poola et al. [START_REF] Poola | Robust scheduling of scientific workflows with deadline and budget constraints in clouds[END_REF] differ as they assume that tasks have uncertain execution times. However, they assume they know these execution times with a rather good accuracy (the standard deviation of the uncertainty is 10% of the expected execution time). They are thus dealing with uncertainties RR n°9257 rather than a true non-clairvoyant setting. The work in [START_REF] Caniou | Budgetaware scheduling algorithms for scientific workflows with stochastic task weights on heterogeneous iaas cloud platforms[END_REF] targets stochastic tasks but is limited to taking static decisions (no task interruption). Some works are limited to a particular type of application like MapReduce [START_REF] Hwang | Minimizing cost of virtual machines for deadline-constrained mapreduce applications in the cloud[END_REF][START_REF] Tian | Towards optimal resource provisioning for running mapreduce programs in public clouds[END_REF]. For instance, Tian and Chen [START_REF] Tian | Towards optimal resource provisioning for running mapreduce programs in public clouds[END_REF] consider MapReduce programs and can either minimize the financial cost while matching a deadline or minimize the execution time while enforcing a given budget.

Bags of tasks

A bag of tasks is an application comprising a set of independent tasks sharing some common characteristics: either all tasks have the same execution time or they are instances coming from a same distribution. Several works devoted to bag-of-tasks processing explicitly target cloud computing [START_REF] Grekioti | Scheduling bag-of-tasks applications to optimize computation time and cost[END_REF][START_REF] Oprescu | Stochastic tail-phase optimization for bag-of-tasks execution in clouds[END_REF]. Some of them consider the classical clairvoyant model [START_REF] Grekioti | Scheduling bag-of-tasks applications to optimize computation time and cost[END_REF] (while [START_REF] Casanova | Non-clairvoyant scheduling of multiple bag-of-tasks applications[END_REF] targets a non-clairvoyant setting). A group of authors including Oprescu and Kielmann have published several studies focusing on budget-constrained makespan minimization in a non clairvoyant settings [START_REF] Oprescu | Bag-of-tasks scheduling under budget constraints[END_REF][START_REF] Oprescu | Budget estimation and control for bag-of-tasks scheduling in clouds[END_REF][START_REF] Oprescu | Stochastic tail-phase optimization for bag-of-tasks execution in clouds[END_REF]. They do not assume they know the distribution of execution times but try to learn it on the fly [START_REF] Oprescu | Bag-of-tasks scheduling under budget constraints[END_REF][START_REF] Oprescu | Budget estimation and control for bag-of-tasks scheduling in clouds[END_REF]. This work differs from ours as these authors do not consider deadlines. For instance, in [START_REF] Oprescu | Stochastic tail-phase optimization for bag-of-tasks execution in clouds[END_REF], the objective is to try to complete all tasks, possibly using replication on faster machines, and, in case the proposed solution fails to achieve this goal, to complete as many tasks as possible. The implied assumption is that all tasks can be completed within the budget. We implicitly assume the opposite: there are too many tasks to complete all of them by the deadline, and therefore we attempt to complete as many as possible; we avoid replication, which would be a waste of ressources.

Vecchiola et al. [START_REF] Vecchiola | Deadline-driven provisioning of resources for scientific applications in hybrid clouds with aneka[END_REF] consider a single application comprising independent tasks with deadlines but without any budget constraints. In their model tasks are supposed to have different execution times but they only consider the average execution time of tasks rather than its probability distribution (this is left for future work). Moreover, they do not report on the amount of deadline violations; their contribution is therefore hard to assess. Mao et al. [START_REF] Mao | Cloud auto-scaling with deadline and budget constraints[END_REF] consider both deadline and budget constrained provisioning and assume they know the tasks execution times up to some small variation (the largest standard deviation of a task execution time is at most 20% of its expected execution time). Hence, this work is more related to scheduling under uncertainties than to non-clairvoyant scheduling.

Task model

Our task model assumes that some tasks may not be executed. This model is very closely related to imprecise computations [START_REF] Amirijoo | Specification and management of qos in real-time databases supporting imprecise computations[END_REF][START_REF] Chung | Scheduling periodic jobs that allow imprecise results[END_REF][START_REF] Liu | Algorithms for scheduling imprecise computations[END_REF], particularly in the context of real-time computations. In imprecise computations, it is not necessary for all tasks to be completely processed to obtain a meaningful result.

Most often, tasks in imprecise computations are divided into a mandatory and an optional part: our work then perfectly corresponds to the optimization of the processing of the optional parts. Among domains where tasks may have optional parts (or some tasks may be entirely optionals), one can cite recognition and mining applications [START_REF] Meng | Best-effort parallel execution framework for recognition and mining applications[END_REF], robotic systems [START_REF] Hassan | Flexible real-time mobile robotic architecture based on behavioural models[END_REF], speech processing [START_REF] Feng | An extended imprecise computation model for time-constrained speech processing and generation[END_REF], and [START_REF] Kobayashi | Rt-frontier: a real-time operating system for practical imprecise computation[END_REF] also cites multimedia processing, planning and artificial intelligence, and database systems. Our task model also corresponds to the overload case of [START_REF] Buttazzo | Handling overload conditions in real-time systems[END_REF] where jobs can be skipped or aborted. Another, related model, is that of anytime tasks [START_REF] Jumel | Management of anytime tasks in real time applications[END_REF] where a task can be interrupted at any time, with the assumption that the longer the running, the higher the quality of its output. Such a model requires a function relating the time spent to a notion of reward. Finally, we note that the general problem related to interrupting tasks falls into the scope of optimal stopping, the theory which consists in selecting a date to take an action, in order to optimize a reward [START_REF] Ferguson | Optimal stopping and applications[END_REF].

Altogether, the present study appears to be unique because it is nonclairvoyant and assumes an overall deadline in addition to a budget constraint.

Problem definition

This section details the framework and scheduling objective.

Tasks. We aim at scheduling a set of independent tasks whose execution times are IID (independent and identically distributed) random variables. The common probability distribution of the execution time is denoted as D. We consider both discrete and continuous distributions in this work. Discrete distributions are used to better understand the problem. Continuous distributions are those typically used in the literature, namely exponential, uniform, and lognormal.

Platform. The execution platform is composed of identical VMs, or processors. Without loss of generality, we assume unit speed and unit cost for each VM, and we scale the task execution times when we aim at changing granularity. Execution time and budget are expressed in seconds. There is an unlimited number of VMs that can be launched by the user.

Constraints and optimization objective. The user has a limited budget b and an execution deadline d. The optimization problem is to maximize the expected number of tasks that can be completed until: (i) the deadline is reached; and (ii) the totality of the budget is spent. More precisely:

• The scheduler decides how many VMs to launch and which VMs to stop at each second;

• Each VM executes a task as soon as it is started;

• Each VM is interrupted as soon as the deadline or the budget is exceeded, whichever comes first; • Each task can be deleted by the scheduler at any second before completion; • The execution of each task is non-preemptive, except in Section 4.2 that summarizes complexity results. In a non-preemptive execution, interrupted tasks cannot be relaunched, and the time/budget spent computing until interruption is completely lost. On the contrary, in a preemptive execution, a task can be interrupted temporarily (e.g., for the execution of another task, or until some event on another VM) and resumed later on.

Discrete distributions

This section provides theoretical results when execution times follow a discrete probability distribution D = {(p i , w i )} 1≤i≤k . There are k possible execution times w 1 < w 2 < • • • < w k (expressed in seconds) and a task has an execution time w i with probability p i , where k i=1 p i = 1. The w i are also called thresholds, because they represent instants at which we should take decisions: if the current task did not complete successfully, then either we continue its execution (if the remaining budget allows for it), or we interrupt the task and start a new one. Of course the discrete distribution of the thresholds is somewhat artificial: in practice, we have continuous distributions for the execution times of the tasks. With continuous distributions, at any instant, we do not know for sure that the task will continue executing until some fixed delay. On the contrary with discrete distributions, we know that the execution will continue (at least) until the next threshold. However, any continuous distribution can be approximated by a discrete distribution, and the more threshold values, the more accurate the approximation. In Section 5, we use the results obtained for discrete distributions to design efficient strategies for continuous distributions.

In this section, we further assume that there is no scheduling deadline d, or equivalently, that the deadline is equal to the budget: d = b. We reintroduce deadlines when dealing with continuous distributions in Section 5. To help the reader apprehend the difficulty of the problem, we start with an example in Section 4.1. We discuss problem complexity without deadline in Section 4.2, providing pseudo-polynomial optimal algorithms and comparing three scenarios: sequential, sequential with preemption, and parallel. Then in Section 4.3, we focus on cases where the budget is large and design an asymptotically optimal strategy. This strategy determines the optimal threshold at which to interrupt all yet unsuccessful tasks. This result is key to the design of an efficient heuristic for continuous distributions in Section 5.1.

Example

We consider the following example with k = 3 thresholds: D = {(0.4, 2), (0.15, 3), (0.45, 7)}. In other words, with a probability of 40% the execution time of a task is 2 seconds, with a probability of 15% it is 3 seconds, and with a probability of 45% it is 7 seconds. We assume that we have a total budget b = 6 (and recall that there is no deadline, or equivalently d = 6). Because b = 6 < w 3 = 7, no task will ever be executed up to its third threshold. We first define and evaluate the optimal policy with a single processor. Then, we exhibit a policy for two processors that achieves a better performance.

With a single processor. Let E(b) denote the optimal expected number of completed tasks when the total budget is equal to b. To define the optimal policy for a budget of 6, we first compute E(b) for the lower values of b that will appear recursively in the expression of E(6):

• E(1) = 0, because w 1 = 2. • E(2) = p 1 × 1 + (p 2 + p 3 ) × 0 = 0.4:
when the budget is equal to 2, the only thing we can do is run the task for two units of time and check whether it completed, which happens with probability p 1 . Otherwise, no task is completed.

• E(3) = (p 1 + p 2 ) × 1 + p 3 × 0 = 0.55. Once again, we execute the task for two units of time. If it has not succeeded, it would be pointless to kill it because the remaining budget is 1 and E(1) = 0 (and if it has succeeded, we cannot take advantage of the remaining budget). Hence, if the task has not completed after two units of time, we continue its computation for the remaining unit of time and check whether it has succeeded.

• E(4) = max{p 1 + E(2), p 1 (1 + E(2)) + p 2 (1 + E(1)) + p 3 (0 + E(1))} = 2p 1 = 0.8.
Here, two policies can be envisioned. Either, we decide to kill the first task if it has not completed by time 2 or, if it has not completed, we let it continue up to time 3 where we kill it if it has not completed (we do not have the budget to let it run up to w 3 ). In the second case, we distinguish two sub-cases depending on the actual task duration. The reasoning will be the same for E [START_REF] Byun | Cost optimized provisioning of elastic resources for application workflows[END_REF].

• E(6) = max{p 1 + E(4), p 1 (1 + E(4)) + p 2 (1 + E(3))} = 3p 1 = 1.2.
Once again, two policies can be envisionned. Either, we decide to kill the first task if it has not completed by time 2 or, if it has not completed, we let it pursue up to time 3 where we kill it if it has not completed (we do not have the budget to let it run up to w 3 ). Therefore, the optimal expectation with a single processor is to complete 1.2 tasks. The principle used to design the optimal policy will be generalized to obtain Algorithm 1.

With two processors. We consider the following policy: (i) we start two tasks in parallel; (ii) if none of them completes by time 2, we let them run up to time 3; (iii) otherwise, we kill at time 2 any not-yet completed task and start a new task instead. The following case analysis displays the expected number of completed tasks for each case of execution time of the two tasks initially started:

w 1 w 2 w 3 w 1 2 + p 1 1 + p 1 1 + p 1 w 2 1 + p 1 2 1 w 3 1 + p 1 1 0
For instance, the square at the intersection of the column w 1 and the row w 2 corresponds to the case where the task on the first processor completes in two units of time, where the task on the second processor would have needed 3 units of time. Because of our policy, this second task is killed and at time 2 and we have completed a single task. There remain 2 units of time and we start a third task, which will complete in this budget with probability p 1 . Therefore, the total expected number of completed task in this configuration is 1 + p 1 , and this configuration happens with probability p 1 p 2 . The total expected number of completed tasks is:

E = p 2 1 (2 + p 1 ) + 2p 1 (p 2 + p 3 )(1 + p 1 )
+ 2p 2 2 + 2p 2 p 3 = 1.236. Therefore, this two-processor policy is more efficient than the optimal single processor policy! Even in the absence of deadline parallelism may help to achieve better performance.

This example helps comprehend the difficulty of the scheduling problem under study. The reader may feel frustrated that in the above example, the performance is only improved by 3%. In fact, one of the conclusions of our work is that, in the absence of deadlines, using several processors only marginally improves performance.

Complexity results

This section is the only one in the paper where we allow preemption. We compare the performance of sequential scheduling, without or with preemption, to that of parallel scheduling, for the problem instance without deadline.

We first present optimal algorithms to solve in pseudo-polynomial time the sequential case without preemption (Algorithm 1) and with preemption (Algorithm 2), as well as an exponential algorithm to solve the parallel case (Algorithm 3). We then show (Lemma 4) that the performance of the first two algorithms bound the performance of the optimal parallel algorithm.

Algorithm 1 is a dynamic programming algorithm that computes in pseudo-polynomial time the expected number of tasks that can be completed on a single processor (without preemption) for a given budget. To ease its writing (and that of Algorithm 2 for the case with preemption), we choose to present it as a recursive algorithm without memoization. Nevertheless, it can easily be transformed into a classical dynamic programming algorithm.

Lemma 1. Algorithm 1 computes the optimal expected number of tasks that can be completed on a single processor (without preemption) for a given budget b in time O(kb).

Proof. The main property guiding the design of Algorithms 1 and 2 is that the only times at which knowledge is gained is when the execution time of a task reaches one of its k thresholds w 1 , ..., w k . (Note that, by definition, a task can only complete at one of these thresholds.) Therefore, it can never be beneficial to stop a non-completed task when its execution time is not equal to a threshold. Therefore, without loss of generality, we focus on algorithms that kill non-completed tasks only at threshold times. Then, the only decision that such an algorithm can take is, when a task reaches a threshold without completing, whether to kill it and start a new task, or continue its execution until the next threshold, where either the task will succeed or a new decision will have to be taken. This is exactly what Algorithm 1 encodes. This algorithm contains at most kb different calls to the function SeqSched; hence, the complexity. Algorithm 2 is a generalization of Algorithm 1 to the case with preemption. In this context, algorithms no longer kill non-completed tasks, but can preempt them with the possibility to restart them later (or not). In the writing of this algorithm, when S is an array, the notation "S + a1 s " means "add a to the entry s of array S". Algorithm 2 has a pseudo-polynomial complexity only if the maximum number of thresholds, k, is fixed. Lemma 2. Algorithm 2 computes the optimal expected number of tasks that can be completed on a single processor with preemption for a given budget b

in time O k-1 s=1 1 + b ws .
Proof. The proof of correctness and optimality of Algorithm 2 both come directly from that of Algorithm 1. A task preempted at threshold s was executed for a time w s and, therefore, there can be at most b ws such tasks in an execution. Therefore, there are at most k-1 s=1 1 + b ws possible values for the array S (a task always completes when it reaches the threshold k). Hence, the complexity.

RR n°9257

Algorithm 1: Dynamic programming algorithm to compute the optimal expected number of tasks completed within the budget b on a single processor without preemption.

Function SeqSched(β, s) Data: The budget β

The threshold s at which the last executed task stopped (s = 0 if the execution was sucessful) bestExpectation ← 0 /* If the budget allows it, we can attempt to start a new task

*/ if β ≥ w 1 then bestExpectation ← p 1 (1+SeqSched(β -w 1 , 0))+(1-p 1 )(SeqSched(β -w 1 , 1))
/* If there was a task preempted at threshold s and if the budget allows it, we can try to continue executing this task */ if s > 0 and w s+1 -

w s ≤ β then if s = k -1 then expectation ← 1 + SeqSched(β -(w s+1 -w s ), 0) else expectation ← p s+1 1-s i=1 ps (1 + SeqSched(β -(w s+1 -w s ), 0)) + 1-p s+1 1-s i=1 ps (SeqSched(β -(w s+1 -w s ), s + 1)) bestExpectation ← max{bestExpectation, expectation} return bestExpectation return SeqSched(b, 0) RR n°9257
Algorithm 2: Dynamic programming algorithm to compute the optimal expected number of tasks completed within the budget b on a single processor with preemption.

Function

if β ≥ w 1 then bestExpectation ← p 1 (1 + PSeqSched(β -w 1 , S)) + (1 - p 1 )(PSeqSched(β -w 1 , S + 1 1 )) for s = 1 to k -1 do /*
-w s ≤ β then if s = k -1 then expectation ← (1 + PSeqSched(β -w s+1 , S -1 s )) else expectation ← p s+1 1-s i=1 ps (1 + PSeqSched(β -w s+1 , S -1 s )) + 1-p s+1 1-s i=1 ps (PSeqSched(β -w s+1 , S -1 s + 1 s+1 )) bestExpectation ← max{bestExpectation, expectation}
return bestExpectation Let S be an array of size k -1 with S[i] = 0 for all i return PSeqSched(b, S)

RR n°9257

Algorithm 3 computes for parallel machines the optimal expected number of tasks that can be completed within the budget, without premeption. We call progress of a task the total execution time so far of that task. Let ParSchedDecision(β, T 1 , T 2 ) be the expected number of tasks that can be completed with a budget β, knowing the progress of the tasks in the task sets T 1 and T 2 where 1) tasks belonging to T 1 may be interrupted, 2) tasks belonging to T 2 cannot be interrupted at this time step, and 3) if the progress of a task is equal to a threshold, that task did not complete at that threshold. Let ParSchedJump(β, T ) be the expected number of tasks that can be completed with a budget β, knowing the progress of the tasks in the task set T . Finally, let ParSchedState(β, T 1 , T 2 ) be the expected number of tasks that can be completed with a budget β, knowing the progress of the tasks in the task sets T 1 and T 2 , where 1) the progress of each task in T 1 is equal to a threshold where the task may have succeeded (we have not yet looked whether this is the case), and 2) the progress of a task in T 2 can only be equal to a threshold if the task failed to complete at that threshold. Intuitively, ParSchedDecision specifies whether to continue, stop or start tasks, while ParSchedJump advances the progress of the tasks, and ParSchedState determines which tasks succeed when a threshold is reached. Lemma 3. Algorithm 3 computes the optimal expected number of tasks that can be completed on parallel processors without preemption for a given budget

b in time O((b + k)b 3 w b k ).
Proof. The proof of correctness and optimality of Algorithm 3 also comes from that of Algorithm 1. Any time a threshold is reached, ParSchedState is called and determines which tasks succeed or not. Then, ParSchedDecision decides which tasks to continue and whether new tasks must be started. There are at most q = b/w 1 concurrent running tasks. Thus, ParSchedDecision can be called with bq 2 w q k different arguments. Each call requires q calls to ParSchedJump, which can take bqw q k different arguments and takes qk operations. Finally, ParSchedState costs less than ParSchedDecision. Hence, the time complexity is b(q

+ k)q 2 w q k = O((b + k)b 3 w b k ) and the space complexity is bq 2 w q k = O(b 3 w b k ).

Relations between problems

Lemma 4 formally states that any algorithm for p processors (using or not preemption) can be simulated on a single processor with preemption. From this property, it immediately follows that the performance of the optimal parallel algorithm on p processors (Algorithm 3) is upper bounded by the performance of Algorithm 2 and lower bounded by the performance of Algorithm 1.

Algorithm 3: Dynamic programming algorithm to compute the optimal expected number of tasks completed within the budget b in parallel.

Function ParSchedDecision(β, T 1 , T 2 ) Data: The budget β A set T 1 : T 1 [i]
is the progress of a task that may be interrupted A set

T 2 : T 2 [i] is the progress of a task that cannot be interrupted if β = 0 then return 0 if T 1 = ∅ then q ← β/
∪ {0} i ) else /* Task 1 in T 1 is either interrupted or not */ return max(ParSchedDecision(β, T 1 \ {T 1 [1]}, T 2 ), ParSchedDecision(β, T 1 \ {T 1 [1]}, T 2 ∪ {T 1 [1]})) Function ParSchedJump(β, T ) Data: The budget β A set T : T [i]
-d × |T |, {T [i] + d} 1≤i≤|T |,∃l s.t.T [i]+d=w l , {T [i] + d} 1≤i≤|T |, ∃l s.t.T [i]+d=w l ) Function ParSchedState(β, T 1 , T 2 ) Data: The budget β A set T 1 : T 1 [i]
is the progress of a task that has just reached a threshold and may complete A set T 2 : T 2 [i] is the progress of a task, the progress is either not equal to a threshold or it is equal to one but the task did not complete at that threshold if

T 1 = ∅ then return ParSchedDecision(β, T 2 , ∅) else Let l be such that w l = T 1 [1] /* Either task 1 succeeds or not */ return p l 1-l-1 i=1 p i (1 + ParSchedState(β, T 1 \ {T 1 [1]}, T 2 )) + (1 - p l 1-l-1 i=1 p i ) ParSchedState(β, T 1 \ {T 1 [1]}, T 2 ∪ {T 1 [1]}) return ParSchedDecision(b, ∅, ∅) RR n°9257
Lemma 4. Any algorithm designed to be executed on p processors with or without preemption can be simulated on a single processor with preemption with the same performance.

Proof. Consider any algorithm A designed to be executed on p processors with preemption. As already stated in the proof of Lemma 1, any meaningful algorithm only takes decisions when a task reaches a threshold. Of course, in a parallel algorithm, a task may be stopped in between two of its thresholds if, at that time, another task reaches one of its own thresholds. On the contrary, no knowledge is gained at a time when no task reaches a threshold, and it is thus suboptimal to kill or to preempt a task at such a time. Without loss of generality, we thus assume that A only kills or preempts tasks at their thresholds.

Without loss of generality, we also assume that all thresholds are integers (otherwise, we just scale the thresholds). Then, we simulate A as follows to obtain a sequential algorithm A * . Assume we have simulated A from time 0 to t. Then A * ran from time 0 to t * (where 0 ≤ t * ≤ t × p) and spent the same amount of time processing the very same tasks than A. We now simulate the work of A for the time-interval [t; t + 1]. Let P 1 , ..., P p be the p ≤ p processors, numbered arbitrarily, that process some work under A during the interval [t; t + 1]. Let T be the task processed by P i during that time under A. Then A * processes T during [t * + (i -1); t * + i]. A * can take this decision because at time t * , A * has processed the exact same work than A at time t. Therefore, at time t * + (i -1), A * has all the necessary knowledge. At time t * + p , A * has processed the exact same work than A at time t + 1 and we can conclude by an immediate induction.

Note that the proof also holds if the parallel algorithm is allowed to start using some new processors in the middle of the computation, or is allowed to restart a processor that it previously left idle.

Lemma 5. ParSched is never worse than SeqSched, and can achieve strictly better performance on some problem instances.

Proof. Given Lemma 4, ParSched is least as good as SeqSched. A sequential execution without preemption on a single processor is a special case of a parallel execution where the number of processors is one. Thus, ParSched is at least as good as SeqSched. Now, consider the instance D = {(0.4, 2), (0.15, 3), (0.45, 7)}. The optimal expected number of tasks that can be completed on a single processor with b = 6 is 1.2 without preemption, whereas it is 1.236 on multiple processors. This result was obtained through the study in Section 4.1 and can be checked using Algorithms 1 and 2 on the instance. Hence, there exist instances where ParSched is strictly better than SeqSched.

RR n°9257

Lemma 6. PSeqSched is never worse than ParSched, and can achieve strictly better performance on some problem instances.

Proof. Given Lemma 4, PSeqSched is always as least as good as ParSched. Consider the instance D = {(0.15, 1), (0.6, 2), (0.15, 3), (0.1, 5)}. The optimal expected number of tasks that can be completed on multiple processors with b = 6 is 2.4372 without preemption, whereas it is 2.4497 with preemption. This result is obtained by executing Algorithms 2 and 3 on the instance.

Asymptotic behavior

In this section, we derive an asymptotically optimal strategy when letting the budget tend to infinity. Because the scheduling strategy described below is applied independently on each processor, we can assume that p = 1 throughout this section without loss of generality. As stated earlier, recall that we assume that there is no deadline. Note that a fixed deadline would make no sense when b → +∞ and p = 1. We first describe the strategy in Section 4.3.1. We show its asymptotic optimality in Sections 4.3.2 and 4.3.3. More precisely, we show the asymptotic optimality among a restricted set of strategies in Section 4.3.2, and then among all possible strategies in Section 4.3.3. The idea is to use Section 4.3.2 as an introduction to the technical proof of Section 4.3.3. Throughout this section, we are given a discrete distribution D = {(p i , w i )} 1≤i≤k .

Optimal fixed-threshold strategy

Consider a discrete distribution D = {(p i , w i )} 1≤i≤k . For 1 ≤ i ≤ k, the i-th fixed-threshold strategy, or FTS i , interrupts every unsuccessful task at threshold w i , i.e., when the task has been executing for w i seconds without completing. There are k such strategies, one per threshold. Informally, our criterion to select the best one is to maximize the ratio R = expected number of tasks completed budget = expected number of tasks completed total time spent Indeed, this ratio measures the success rate per time unit, or equivalently, per budget unit (since we have unit execution speed). Formally, we would like to compute

R i (b) = N i (b) b (1)
where N i (b) is the expected number of tasks that are successfully completed when using strategy FTS i that interrupts all unsuccessful tasks after w i seconds, and proceeds until the budget b has been spent. It turns out that we can compute the limit R i of R i (b) when the budget b tends to infinity:

Proposition 1. lim b→∞ R i (b) = R i def = i j=1 p j i j=1 p j w j + (1 -i j=1 p j )w i
Proof. Consider an execution using strategy FTS i and with budget b. We execute n tasks during at most w i seconds until there remains some budget, and maybe there exists a last task that is truncated due to budget exhaustion before it completes. Let b left be the sum of the unused budget and of the budget spent for the truncated task (if any). The execution of the n tasks lasts b -b left seconds, where 0 ≤ b left ≤ w i . For 1 ≤ j ≤ i, let n j denote the number of tasks that have completed successfully in exactly w j seconds.

Then n -i j=1 n j tasks have been unsuccessful and interrupted, and we have

b -b left = n 1 w 1 + • • • + n i w i + (n - i j=1 n j )w i .
Note that n, n j for 1 ≤ j ≤ i, and b left are random variables here. With the notation of Equation 1, we have N i (b) = E( i j=1 n j ) and we aim at showing the existence of the limit lim b→∞ N i (b) b and at computing its value.

When the budget b tends to infinity, so does n, because n ≥ b w i . We now show that n 1 n converges almost surely to the value p 1 : we write n 1 n a.s.

→ p 1 . This means that the convergence to that limit is true, except maybe over a set of measure zero. To see this, for the i-th task, let X

(1) i be the random variable whose value is 1 if the task completes in w 1 seconds, and 0 otherwise. By definition

n 1 = X (1) 1 + X (1) 2 + • • • + X (1) n . The X (1) i are IID and have expectation E(X (1) i ) = 1.p 1 + 0.(1 -p 1 ) = p 1 , hence X (1) 1 + X (1) 2 + • • • + X (1) n n a.s.
→ p 1 according to the strong law of large numbers [START_REF] Nelson | Probability, stochastic processes, and queueing theory: the mathematics of computer performance modeling[END_REF], hence the result. We prove similarly that n j n a.s. → p j for 1 ≤ j ≤ i. Then, we have:

i j=1 n j b = i j=1 n j i j=1 n j w j + (n -i j=1 n j )w i + b left RR n°9257 = i j=1 n j n i j=1 n j n w j + (1 -i j=1 n j n )w i + b left n a.s. → R i (where R i is defined in Proposition 1), because n j n a.s. → p j for 1 ≤ j ≤ i, b left n a.s.
→ 0 (that convergence is even deterministic because b left is bounded by a constant), and the finite union of sets of measure zero has measure zero. A fortiori when taking the expectations, we have deterministic convergence:

R i (b) = E( i j=1 n j ) b → R i ,
which concludes the proof.

The optimal fixed-threshold strategy FTS opt is defined as the strategy FTS i whose ratio R i is maximal. If several strategies FTS i achieve the maximal ratio R opt , we pick the one with smallest w i (to improve success rate when the budget is limited and truncation must occur). Formally: Definition 1. FTS opt is the strategy FTS i 0 where i 0 = min 1≤i≤k {i R i = min 1≤j≤k R j }.

To conclude this section, we work out a little example. Consider a distribution D = {(p i , w i )} 1≤i≤3 with 3 thresholds. We have

R 1 = p 1 w 1 , R 2 = p 1 + p 2 p 1 w 1 + (1 -p 1 )w 2
, and

R 3 = p 1 + p 2 + p 3 p 1 w 1 + p 2 w 2 + (1 -p 1 -p 2 )w 3 = 1 p 1 w 1 + p 2 w 2 + p 3 w 3 •
We pick the largest of these three values to derive FTS opt .

Asymptotic optimality of FTS opt among mixed-threshold strategies

A scheduling strategy makes the following decisions for each task: when a new threshold is reached, and if the task is not successful at this point, decide whether either to continue execution until the next threshold, or to interrupt the task. In the most general case, these decisions may depend upon the remaining available budget. However, when the budget is large, it makes sense to restrict to strategies where such decisions are taken independently of the remaining budget, independently to past history, and either deterministically or non-deterministically but according to some fixed probabilities.

We formally define such strategies as follows:

Definition 2. A mixed-threshold strategy MTS (q 1 , q 2 , . . . , q k-1 ), where 0 ≤ q j ≤ 1 for 1 ≤ j ≤ k -1 are fixed probabilities, makes the following decision when the execution of a task reaches threshold w i , for 1 ≤ i ≤ k -1, without success: it decides randomly to continue execution until the next threshold with probability q i , and to interrupt the task otherwise, hence with probability 1 -q i .

Of course, the fixed-threshold strategy FTS i coincides with MTS (1, . . . , 1, 0, . . . , 0) where the last 1 is in position i -1: q j = 1 for j < i et q j = 0 for j ≥ i. In this section, we prove our main result for discrete distributions: Theorem 1. FTS opt is asymptotically optimal among all mixed-threshold strategies.

Proof. Theorem 1 applies to any fixed number of processors p, but recall that we assume p = 1 w.l.o.g. in this section, because the rate per time/budget unit is computed independently for each processor. Given an arbitrary strategy MTS (q 1 , q 2 , . . . , q k-1 ), consider an execution with budget b and where we execute n tasks according to the strategy until the last seconds, i.e., until some instant b -b left , where 0 ≤ b left ≤ w k . As before, when the budget b tends to infinity, so does n, because n ≥ b w k . In the execution, let n i be the number of tasks whose execution has lasted w i seconds, let m i be the number of tasks whose execution was successful and lasted w i seconds; scaling by n, let α i = n i n and β i = m i n for 1 ≤ i ≤ k. As in the proof of Proposition 1, using the strong law of large numbers, we prove the following:

β 1 a.s. → β ∞ 1 = p 1 β 2 a.s. → β ∞ 2 = p 2 1-p 1 (1 -α ∞ 1 ) β 3 a.s. → β ∞ 3 = p 3 1-p 1 -p 2 (1 -α ∞ 1 -α ∞ 2 ) . . . β k-1 a.s. → β ∞ k-1 = p k-1 1-k-2 j=1 p j (1 -k-2 j=1 α ∞ j ) β k a.s. → β ∞ k = p k 1-k-1 j=1 p j (1 -k-1 j=1 α ∞ j ) and α 1 a.s. → α ∞ 1 = p 1 + (1 -p 1 )(1 -q 1 ) α 2 a.s. → α ∞ 2 = p 2 1-p 1 + (1 -p 2 1-p 1 )(1 -q 2 ) (1 -α ∞ 1 ) α 3 a.s. → α ∞ 3 = p 3 1-p 1 -p 2 + (1 - p 3 1-p 1 -p 2 )(1 -q 3 ) (1 -α ∞ 1 -α ∞ 2 ) . . . α k-1 a.s. → α ∞ k-1 = p k-1 1-k-2 j=1 p j + (1 - p k-1 1-k-2 j=1 p j ) (1 -q k-1 ) × (1 -k-2 j=1 α ∞ j ) α k a.s. → α ∞ k = 1 -k-1 j=1 α ∞ j RR n°9257
We also prove just as before that b n

a.s. → k j=1 α ∞ j w j
so that the success rate per budget unit does have the following limit when the budget tends to infinity:

k j=1 β j k j=1 α j w j b→∞ → R(α ∞ 1 , α ∞ 2 , . . . , α ∞ q-1 ) def = k j=1 β ∞ j k j=1 α ∞ j w j
The rest of the proof is pure algebra: we have to show that the maximum

value of R(α ∞ 1 , α ∞ 2 , . . . , α ∞ q-1 ) over all values 0 ≤ α ∞ j ≤ 1 for 1 ≤ j ≤ k -1, is R opt , obtained
when the strategy is some FTS i (i.e., when there exists i with α ∞ j = 1 if j < i and α ∞ j = 0 if j ≥ i). Note that below, to ease the writing, we simply use α j instead of α ∞ j 's of the above equations, and we obtain:

Problem Pb[k](D) : Maximize R(α 1 , α 2 , . . . , α k-1 ) = k i=1 p i 1-i-1 j=1 p j (1-i-1 j=1 α j ) k-1 i=1 α i w i +(1-k-1 i=1 α i )w k Subject to          p 1 ≤ α 1 ≤ 1 p 2 1-p 1 (1 -α 1 ) ≤ α 2 ≤ 1 . . . p k-1 1-k-2 j=1 p j (1 -k-2 j=1 α j ) ≤ α k-1 ≤ 1 and k i=1 p i ≤ 1 (2)
We proceed by induction on k to show that the maximum value of the optimization problem Pb[k](D) is R opt . Note that we do not assume that

k i=1 p i = 1 when stating Pb[k](D) but only k i=1 p i ≤ 1.
For the base case k = 1, we have a single value p 1 w 1 , which is the ratio R opt of FTS 1 . For the case k = 2, we have a single variable α 1 , where p 1 ≤ α 1 ≤ 1, and R(α 1 ) =

p 1 + p 2 1-p 1 (1-α 1 ) α 1 w 1 +(1-α 1 )w 2 .
We note that the derivative of the function x → f (x) = ax+b cx+d has constant sign (that of ad -bc); hence, the maximum of R(α 1 ) is obtained for one of the two bounds, either α 1 = p 1 , with value

p 1 +p 2 p 1 w 1 +(1-p 1 )w 2 , or α 1 = 1, with value p 1 w 1 .
The first value is the ratio R 2 of FTS 2 , and the second value is the ratio R 1 of FTS 1 , which concludes the proof for k = 2.

Assume that we have shown the result for Pb[k ](D ) for 2 ≤ k ≤ k -1 and all distributions D' with k thresholds, and consider the problem Pb[k](D). First we fix the values of α j , 1 ≤ j ≤ k -2, and view RR n°9257 R(α 1 , α 2 , . . . , α k-1 ) as a function of α k-1 . It is again of the form x → f (x) = ax+b cx+d ; hence, the maximum is obtained for one of the two bounds, either

α k-1 = p k-1 1-k-2 j=1 p j (1 -k-2 j=1 α j ), or α k-1 = 1 -k-2 j=1 α j . First case If α k-1 = p k-1 1-k-2 j=1 p j (1 -k-2 j=1 α j ), then, 1 -k-1 j=1 α j = (1 - p k-1 1-k-2 j=1 p j )(1-k-2 j=1 α j ). Hence, p k 1-k-1 j=1 p j (1-k-1 j=1 α j ) = p k 1-k-2 j=1 p j (1- k-2 j=1 α j ). Thus R(α 1 , α 2 , . . . , α k-2 , p k-1 1 -k-2 j=1 p j (1 - k-2 j=1 α j )) = k-1 i=1 p i 1-i-1 j=1 p j (1-i-1 j=1 α j )+ p k 1-k-1 j=1 p j (1-k-1 j=1 α j ) k-2 i=1 α i w i +(1-k-2 j=1 α j ) p k-1 w k-1 +(1-k-1 j=1 p j )w k 1-k-2 j=1 p j . Consider the distribution D = {p i , w i } 1≤i≤k-1 such that p i = p i and w i = w i for 1 ≤ i ≤ k -2, p k-1 = p k-1 + p k and w k-1 = p k-1 w k-1 +(1-k-1 j=1 p j )w k 1-k-2 j=1 p j . The distribution D' has k -1 thresholds. The optimization problem Pb[k -1](D ) writes Maximize R (α 1 , α 2 , . . . , α k-2 ) = k-1 i=1 p i 1-i-1 j=1 p j (1-i-1 j=1 α j ) k-2 i=1 α i w i +(1-k-2 i=1 α i )w k-1
.

Subject to

p i 1-i-1 j=1 p j (1 -i-1 j=1 α j ) ≤ α i ≤ 1, ∀i ∈ {1, . . . , k -2} and k-1 i=1 p i ≤ 1 Replacing p k-1 and w k-1 by their values, we see that Pb[k](D) when α k-1 = p k-1 1-k-2 j=1 p j (1 -k-2 j=1 α j ) reduces to Pb[k -1](D )
. By induction hypothesis, Pb[k -1](D ) achieves its maximum for some fixedthreshold strategy FTS i , where 1 ≤ i ≤ k -1. The task-to-budget ratios R i for D' are the following:

• R i = R i for 1 ≤ i ≤ k -2 • R k-1 = k-1 j=1 p j k-2 j=1 p j w j +(1-k-2 j=1 p j )w k-1 = k-2 j=1 p j +p k-1 +p k k-2 j=1 p j w j +p k-1 w k-1 +(1-k-1 j=1 p j )w k = R k .
This is the desired result and concludes the analysis for the first case.

Second case If α k-1 = 1 -k-2 j=1 α j , then R(α 1 , α 2 , . . . , α k-2 , 1 - k-2 j=1 α j ) = k-1 i=1 p i 1-i-1 j=1 p j (1 -i-1 j=1 α j ) k-2 i=1 α i w i + (1 -k-2 j=1 α j )w k-1
.

Consider the distribution D = {p i , w i } 1≤i≤k-1 such that p i = p i and

w i = w i for 1 ≤ i ≤ k -1. The distribution D' has k -1 thresholds. The optimization problem Pb[k](D) when α k-1 = 1-k-2 j=1 α j directly reduces to Pb[k -1](D ). By induction hypothesis, Pb[k -1](D )
achieves its maximum for some fixed-threshold strategy FTS i , where 1 ≤ i ≤ k -1. The task-to-budget ratios for D' are the same as for D: R i = R i for 1 ≤ i k -2. This is the desired result and concludes the analysis for the second case.

Altogether, we have solved the optimization problem Pb[k](D). This concludes the proof of the theorem.

Asymptotic optimality of FTS opt

In this section, we extend Theorem 1 to arbitrary strategies and show a much stronger result: Theorem 2. FTS opt is asymptotically optimal among all possible strategies.

Proof. The proof of this theorem is quite technical and the reader may want to skip it. We deal with all scheduling strategies that never interrupt a task before it reaches its first state w 1 , because such strategies are obviously dominant. We define an outcome in the sample space as an infinite sequence of execution times for the tasks associated to an infinite sequence of decisions for the scheduling strategy, and we introduce the following random variables:

•

NS (b) = S 1 (b) + . . . + S k (b) b ≤ S 1 (b) + . . . + S k (b) N 1 (b)w 1 + . . . + N k (b)w k RR n°9257
Convergence of NS (b). We know that the probability of success of any task at state i knowing that there was no termination until this state is Pr[success at state i|no termination until i-1 included] =

p i 1-i-1 j=1 p j
. There are S i (b) such successes out of N (b) -i-1 j=0 N j (b) tasks. Thus, by strong law of large numbers:

Pr lim N (b)-i-1 j=0 N j (b)→∞ S i (b) N (b)-i-1 j=0 N j (b) = p i 1-i-1 j=1 p j = 1 (3)
Thus Pr ∀ > 0, ∃n 0 , ∀N (b) -i-1 j=0 N j (b) ≥ n 0 , S i (b) N (b) < p i 1-i-1 j=1 p j (1 -i-1 j=0 N j (b)/N (b)) + = 1 because 1 -i-1 j=0 N j (b)/N (b) ≤ 1 (by definition of N (b))
, which is thus bounded.

We now show that

Pr [∀ > 0, ∃b 0 , ∀b ≥ b 0 , S i (b) N (b) < p i 1-i-1 j=1 p j (1 -i-1 j=0 N j (b)/N (b)) + = 1
Indeed, assume by contradiction that it is false, then

Pr [∃ > 0, ∀b 0 , ∃b ≥ b 0 , S i (b) N (b) ≥ p i 1-i-1 j=1 p j (1 -i-1 j=0 N j (b)/N (b)) + = 0 (4)
Let Ω be the subset of the sample space where the previous event occurs (Pr[Ω ] = 0). For any given outcome ω ∈ Ω , let b (l) be a sequence of b such that

S i (b) N (b) ≥ p i 1-i-1 j=1 p j (1 -i-1 j=0 N j (b)/N (b)) + . This gives ∃l 0 , ∀l ≥ l 0 , S i (b (l) ) N (b (l) ) ≥ p i 1-i-1 j=1 p j (1 -i-1 j=0 N j (b (l) )/N (b (l) )) + for a given nonzero . For any outcome, lim b→∞ N (b) = ∞ because N (b) = k i=0 N i (b) ≥ b w k . Thus, for any outcome ω ∈ Ω , lim l→∞ S i (b (l) ) = ∞. With S i (b) ≤ N i (b) ≤ N (b) -i-1 j=0 N j (b), we have lim l→∞ N (b (l) ) -i-1 j=0 N j (b (l) )
= ∞ for any outcome ω ∈ Ω . By the contradiction assumption (Equation 4), for any outcome ω ∈ Ω , we know that

S i (b) N (b) -i-1 j=0 N j (b) ≥ p i 1 -i-1 j=1 p j + RR n°9257
This contradicts the previous result from the strong law of large numbers (Equation 3). Finally, we obtain:

Pr [∀ > 0, ∃b 0 , ∀b ≥ b 0 , N S(b) < k i=1 p i 1-i-1 j=1 p j (1-i-1 j=0 α j (b)) k i=1 α i (b)w i + = 1 Bounding α i (b). With S i (b) ≤ N i (b) ≤ N (b) -i-1 j=0 N j (b), we have: S i (b) N (b) -i-1 j=0 N j (b) (1 - i-1 j=0 α j (b)) ≤ α i (b)
and

α i (b) ≤ 1 - i-1 j=0 α j (b)
We look for an asymptotic deterministic lower bound for α i (b). From the strong law of large numbers (similar to above):

Pr ∀ > 0, ∃n 0 , ∀N (b) -i-1 j=0 N j (b) ≥ n 0 , S i (b) N (b) > p i 1-i-1 j=1 p j (1 -i-1 j=0 α j (b)) -= 1
which we can rewrite as:

Pr ∀ > 0, ∃n 0 , ∀N (b) -i-1 j=0 N j (b) ≥ n 0 , p i 1-i-1 j=1 p j (1 -i-1 j=0 α j (b)) < α i (b) + = 1 because N i (b) ≥ S i (b) and thus α i (b) ≥ S i (b) N (b) . We now show that Pr [∀ > 0, ∃b 0 , ∀b ≥ b 0 , p i 1-i-1 j=1 p j (1 -i-1 j=0 α j (b)) < α i (b) + = 1
Indeed, assume by contradiction that it is false, then

Pr [∃ > 0, ∀b 0 , ∃b ≥ b 0 , p i 1-i-1 j=1 p j (1 -i-1 j=0 α j (b)) ≥ α i (b) + = 0
We use a similar reasoning as before. Let b (l) be the sequence of b such that

p i 1-i-1 j=1 p j (1 -i-1 j=0 α j (b)) ≥ α i (b) + . This gives ∃l 0 , ∀l ≥ l 0 , p i 1-i-1 j=1 p j (1 - i-1 j=0 α j (b (l) )) ≥ α i (b (l)
)+ , which can also be written ∃l 0 , ∀l ≥ l 0 ,

p i 1-i-1 j=1 p j N (b (l) )-i-1 j=0 N j (b (l) ) N (b (l) ) ≥ α i (b (l) ) + . Since lim b→∞ N (b) = ∞ (because N (b) = k i=0 N i (b) ≥ b w k ), we have lim j→∞ N (b (l) )-i-1 j=0 N j (b (l) ) = ∞,
which contradicts the previous result from the strong law of large numbers.

Summing up. In the previous paragraphs, we have showed that

Pr [∀ > 0, ∃b 0 , ∀b ≥ b 0 , N S(b) < k i=1 p i 1-i-1 j=1 p j (1-i-1 j=0 α j (b)) k i=1 α i (b)w i + = 1 (5)
α i (b) ≤ 1 - i-1 j=0 α j (b) (6)
Pr [∀ > 0, ∃b 0 , ∀b ≥ b 0 ,

p i 1-i-1 j=1 p j (1 -i-1 j=0 α j (b)) < α i (b) + = 1 (7)
We introduce the notation

f ({α i }) = k i=1 p i 1-i-1 j=1 p j (1 -i-1 j=0 α j (b)) k i=1 α i (b)w i
and put together Equations ( 5) to [START_REF] Calheiros | Meeting deadlines of scientific workflows in public clouds with tasks replication[END_REF] as follows:

Pr [∀ 1 > 0, ∀ 2 > 0, ∃b 0 , ∀b ≥ b 0 , N S(b) < f ({α i }) + 1 , p i 1-i-1 j=1 p j (1 -i-1 j=0 α j (b)) -2 < α i (b), α i (b) ≤ 1 -i-1 j=0 α j (b) = 1
For any event ω, 1 , 2 and b ≥ b 0 , every α i (b) can be replaced by a scalar term a i . Therefore, for any event ω, we have:

N S(b) < f ({a i }) + 1 p i 1 -i-1 j=1 p j (1 - i-1 j=0 a j ) -2 < a i ≤ 1 - i-1 j=0 a j
The α i s are defined over a compact set because k i=0 a i = 1 and 0 ≤ a i ≤ 1. Therefore, for any event ω, we have:

N S(b) < max f ({a i }) + 1 p i 1-i-1 j=1 p j (1-i-1 j=0 a j )-2 ≤a i ≤1-i-1 j=0 a j 1≤i≤k-1
Because we restricted on strategies that let tasks reach at least the first state, we have α j (b) = 0 for some j > 0, and the denominator of f ({α i }) is never null. Therefore, f ({a i }) is uniformly continuous and:

∀ 0 > 0, ∃δ 0 > 0, ∀{a i }, ∀{a i }, d({a i }, {a i }) < δ 0 ⇒ d 2 (f ({a i }), f ({a i })) < 0
By taking 0 = 2 = /2 and 1 = θ 0 , we get that for any event ω, , and b ≥ b 0 :

N S(b) < max f ({a i }) + p i 1-i-1 j=1 p j (1-i-1 j=0 a j )≤a i ≤1-i-1 j=0 a j 1≤i≤k-1
Using the fact that α 0 (b) = 0, we end up with:

Pr [∀ > 0, ∃b 0 , ∀b ≥ b 0 , N S(b) < max p i 1-i-1 j=1 p j ≤ a i (b) 1-i-1 j=1 a j (b) ≤1 1≤i≤k-1 k i=1 p i 1-i-1 j=1 p j (1-i-1 j=1 a j ) k i=1 a i w i +   = 1
Maximum. We see that this last maximum is exactly problem Pb[k](D) introduced in the proof of Theorem 1. This maximum is achieved by FTS opt , swhich concludes the proof.

Continuous distributions

In this section, we build upon the previous results and deal with continuous distributions. We do assume we have a fixed budget and a deadline. Thus, in contrast to Section 4, the distribution D is now continuous and has expected value µ D and variance σ 2 D . Let F (x) be its cumulative distribution function and f (x) its probability density function. The objective remains to execute as many tasks as possible given a budget b, a deadline d and a potentially unlimited number of processors.

We start by designing several heuristics in Section 5.1 and then we assess their efficiency through experiments in Section 5.2. The code and scripts used for the simulations and the data analysis are publicly available online [START_REF] Canon | Code for scheduling independent stochastic tasks under deadline and budget constraints[END_REF].

Heuristics

We present below different heuristics, among which an extension of the asymptotically optimal greedy strategy of Section 4.3 to the continuous case. In all cases, we enroll b d machines. The rationale for this choice is that this is the maximum number of machines that can work in parallel and continuously, up to the deadline. We have three main classes of heuristics:

• MeanVariance(x) is the family of heuristics that kill a task as soon as its execution time reaches µ D + xσ D , where x is some positive or negative constant. • Quantile(x) is the family of heuristics that kill a task when its execution time reaches the x-quantile of the distribution D with 0 ≤ x ≤ 1.

U (0, 1) Exp( 1 Figure 1: Efficiency (ratio R of number of tasks successfully executed per budget unit) for different probability distributions. Some distributions have an optimal finite cutting threshold depicted with a vertical red line.

• OptRatio is the heuristic inspired by the asymptotically optimal strategy for discrete distributions. OptRatio interrupts all (unsuccessful) tasks at time l = arg max l R(l) where

R(l) = F (l) l 0 xf (x)dx + l(1 -F (l))
.

The idea behind OptRatio is that it maximizes the ratio of the probability of success (namely F (l)) to the expected amount of budget spent for a single task when the task is interrupted at time l (i.e., l 0 xf (x)dx for the cases when the task terminates sooner than l and ∞ l lf (x)dx = l(1 -F (l)) otherwise). This is a continuous extension of the approach proposed in Section 4.3, and we expect OptRatio to perform well for large budgets.

We now analyze OptRatio with some classical probability distributions defined on nonnegative values (task execution times need to be nonnegative). For the exponential distribution, which is memoryless, R(l) = λ where λ is the rate of the distribution. In this case, any l can be chosen and the tasks may be interrupted at any moment with OptRatio without modifying the performance. For the uniform distribution (between a and b), R(l) = 2 l-a -l 2 +2bl-a 2 , which takes its maximum value for l = b (R(b) = 2 a+b ). In this case, tasks should never be interrupted to maximize performance. We established these results for exponential and uniform distributions through simple algebraic manipulations.

In addition to the exponential and uniform distributions, Table 1 presents other standard distributions. For these distributions, we provide some code [START_REF] Canon | Code for scheduling independent stochastic tasks under deadline and budget constraints[END_REF] to numerically compute the optimal time l at which tasks should be interrupted. Note that there exist many relations between probability distributions. For instance, the beta distribution with both shape parameters equal Beta

x α-1 (1-x) β-1 B(α,β) Gamma 1 Γ(k)θ k x k-1 e -x θ Weibull k θ k x k-1 e -( x θ ) k
Inverse-gamma

θ k Γ(k) x -k-1 e -θ x RR n°9257
to one is the same as the uniform distribution, whereas it has a U-shape with both equal to 0.5, and a bell-shape with both equal to 2. Also, the exponential distribution is a special case of the gamma and Weibull distributions when their shape parameter is one.

Figure 1 shows how R(l) varies as a function of the cutting threshold l, for the probability distributions shown in Table 1. Recall that OptRatio will select the threshold l for which R(l) is maximum. For instance, this threshold is l = 1 for the uniform distribution, meaning that we should never interrupt any task. The threshold can be any value of l for the exponential distribution, and this is due to the memoryless property: we can interrupt a task at any moment, without any expected consequence. The threshold is l = ∞ for the half-normal distribution, meaning again that we should never interrupt any task, just as for uniform distributions. Note that the expected value of all distributions is not the same overall, because we use standard parameters in Figure 1, hence ratio values are not comparable across distributions.

We remark that the lognormal distribution, which presents a fast increase followed by a slow decrease with an heavy tail, exhibits an optimal cutting threshold during the execution of a task: on Figure 1, we see that the optimal threshold is l ≈ 1.73 (we computed this value numerically) for the distribution Lognormal(0, 1). We make a similar observation for the inverse-gamma distributions, where the optimal threshold is l ≈ 0.7 for Inv-Gamma(1.5, 0.5) and l ≈ 2.32 for Inv-Gamma [START_REF] Arabnejad | Budget distribution strategies for scientific workflow scheduling in commercial clouds[END_REF][START_REF] Amirijoo | Specification and management of qos in real-time databases supporting imprecise computations[END_REF]. These lognormal and inverse-gamma distributions share the following properties: the density is close to zero for small costs and has a steep increase. On the contrary, the bell-shape beta distribution Beta(2, 2) has a small density for small costs but does not have a steep increase, and tasks should never be interrupted (in other words, the optimal cutting threshold is l = 1 for Beta(2, 2)).

Finally, we observe that three distributions are the most efficient when the cutting threshold tends to zero (Beta(0.5, 0.5), Gamma(0.5, 2) and Weibull(0.5, 1/Γ(3))). This is a surprising result, and we experimentally confirm it in Figures 5 and6. We point out that it is unlikely that such distributions would model actual execution times in practice.

Experiments

The following experiments make use of three standard distributions: exponential, uniform, and lognormal. The first two distributions are very simple and easy to use, while the latter has been advocated to model file sizes [START_REF] Feitelson | Workload modeling for computer systems performance evaluation[END_REF], and we assume that task costs could naturally obey this distribution too. Moreover, the lognormal distribution is positive, it has a tail that extends to infinity and the logarithm of the data values are normally distributed. Also, this distribution leads to a non-trivial cutting threshold, contrarily to exponential (interrupt anywhere) or uniform (never interrupt), thereby allowing for a complete assessment of our approach. In all experiments, we submit tasks steadily until the budget and/or the deadline is exhausted.

Figure 2 shows the number of successfully executed tasks for each heuristic with three distributions (lognormal, uniform, exponential) of same expected value µ = 1, with a budget and deadline b = d = 100. Note that to ensure a given expected value and standard deviation for the lognormal distribution, we set its parameters as follows: α = log(µ) -log(σ 2 /µ 2 + 1)/2 and β = log(σ 2 /µ 2 + 1). Note also that using a standard deviation σ = 3 for the lognormal distribution corresponds to a high level of heterogeneity. To see this intuitively, take a discrete distribution with 11 equally probable costs, 10 of value 0.1 and 1 of value 10: its expected value is µ = 1 while its standard deviation is σ ≈ 2.85. Finally, we note that Figure 2 confirms that tasks with exponentially distributed costs can be interrupted at any time and that tasks with uniformly distributed costs should never be interrupted.

Next, we focus on the lognormal distribution. First, in Figure 3, we assess the impact of three important parameters: the standard deviation, the budget and the deadline, respectively. The expected value is always µ = 1. By default, the standard deviation is σ = 3, and the budget and deadline are set to 100 (b = d = 100), which means that a single machine is enrolled. When we vary the standard deviation (first row in Figure 3), we keep b = d = 100. When we vary the budget (second row in Figure 3), we maintain the equality b = d. When we vary the deadline (third row in Figure 3), we keep b = 100, hence more VMs are enrolled (10 VMs when d = 10 and 100 VMs when d = 1). Each heuristic is run 100,000 times for

(0) MV(-0.3) Q(0.8) Q(0.6) Q(0.4) Q(0.2) OR MV(0.3) MV(0) MV(-0.3) Q(0.8) Q(0.6) Q(0.4) Q(0.2) OR MV(0.3) MV(0) MV(-0.3) Q(0.8) Q(0.6) Q(0.4) Q(0.2)

Successful tasks

Heuristics Methods On Figure 3, we see that the higher the standard deviation, the larger the gain of every approach. With a low standard deviation, all approaches perform similarly. Increasing the budget tends to decrease the variability when running several times the same approach (the error bars are narrower with large budgets, which makes the approaches more predictable). This is a consequence of the law of large numbers. However, the expected efficiency (around 2.5 tasks per unit of time) remains similar even for a low budget of 30. Finally, decreasing significantly the deadline prevents some strategies from letting tasks run a long time. Long running tasks are then forced to be interrupted early, which is similar to the behavior of the more efficient approaches. In all tested situations, the OptRatio algorithm with the optimal threshold achieved the best results.

Quantile (Q) MeanVariance (MV) OptRatio (OR)
Next, Figure 4 depicts the efficiency of OptRatio with small deadlines. Even though our approach extends a strategy that is asymptotically optimal when both the budget and the deadline are large, it does perform well with small deadlines, as long as d is not lower than the cutting threshold. In the settings of Figure 4, where the average execution time of a task is equal to 1, this means that as soon as the deadline is equal to 0.1, OptRatio achieves its asymptotic performance! (The reader can compare the performance of OptRatio for deadlines of 100 and 0.1 on Figures 2 and4.) Finally note that on Figure 4 cessors for a deadline d = 0.1. This confirms that neither the budget, nor the deadline need to be large for OptRatio to reach its best efficiency, and that this heuristic is extremely robust. Finally, recall that some distributions such as Beta(0.5, 0.5), and Gamma(0.5, 2) have a cutting threshold tending to zero. We confirm this observation in Figures 5 and6. Figure 5 shows that a low threshold = 0.01 enables Op-tRatio to dramatically outperform the other heuristics. Figure 6 further studies the impact of the cutting threshold. For = 0.001, we start more than 100,000 tasks during b = d = 100 seconds, since we kill each of them after one millisecond if it did not succeed before that; still, we complete over 2,000 tasks, many more than using higher cutting thresholds (let alone other heuristics). Again, such distributions are not expected to model actual execution times in practice!

Conclusion

This paper deals with scheduling strategies to successfully execute the maximum number of a bag of stochastic tasks on VMs (Virtual Machines) with a finite budget and under a deadline constraint. We first focused on the problem instance with discrete probability distributions and no deadline. We proposed three optimal dynamic programming algorithms for different scenarios, depending upon whether tasks may be preempted or not, and whether multiple VMs may be enrolled or only a single one. We also introduced an asymptotically optimal method that computes a cutting threshold that is independent of the remaining budget. Then, we extended this approach to the continuous case and with deadline. We designed OptRatio, an efficient heuristic which we validated through simulations with classical distributions such as exponential, uniform, and lognormal. Tests with several values of the deadline, leading to enroll different numbers of VMs, also confirm the relevance and robustness of our proposition. Future work will be dedicated to considering heterogeneous tasks (still with stochastic costs), as well as heterogeneous VMs. Typically, cloud providers provide a few different categories of VM with different computer power and nominal cost, and it would be interesting (albeit challenging) to extend our study to such a framework. Another interesting direction would be to take into account start-up costs when launching a VM, thereby reducing the amount of parallelism, because fewer VMs will likely be deployed.

  NS (b): number of successful tasks per unit of budget for a given b • S i (b): random variable, number of successful tasks at state i for a given b • N i (b): number of terminating tasks between state i (included) and state i + 1 (excluded) for a given b • N (b) = k j=0 N i (b): number of started tasks for a given b • α i (b) = N i (b)/N (b): proportion of tasks terminating between state i (included) and state i + 1 (excluded) for a given b For any such outcome, we have:

Figure 2 :

 2 Figure2: Number of successfully executed tasks for each heuristic with three distributions (lognormal, uniform, exponential) of same expected value µ = 1, with a budget and deadline b = d = 100 (which means that a single machine is enrolled). Each heuristic is run 100,000 times for each scenario. The error bars are computed with the mean plus/minus two standard deviations of the number of successes. The lognormal distribution has parameters α ≈ -1.15 and β ≈ 1.52 to have an expected value µ = 1 and a standard deviation σ = 3, and the optimal cutting threshold for OptRatio is l ≈ 0.1). The exponential distribution has shape λ = 1 and the cutting threshold is arbitrarily set to l = 2. The uniform distribution has parameters a = 0 and b = 2, and the cutting threshold is l = 2.

Figure 3 :

 3 Figure 3: Number of successfully executed tasks for each heuristic, with lognormal costs and expected value µ = 1. Unless otherwise specified, the standard deviation is σ = 3, and the budget and deadline are b = d = 100. Each heuristic is run 100,000 times for each scenario. The error bars are computed with the mean plus/minus two standard deviations of the number of successes. The lognormal distribution has parameters α ≈ -1.15 and β ≈ 1.52 by default (to have µ = 1 and σ = 3) (the cutting threshold for OptRatio is l ≈ 0.1). They are α ≈ -0.35 and β ≈ 0.83 when σ = 1 (l ≈ 2.1) and α ≈ -0.8 and β ≈ 1.27 when σ = 2 (l ≈ 0.34).

Figure 4 :

 4 Figure 4: Number of successfully executed tasks for OptRatio with a budget b = 100 and optimal cutting threshold l ≈ 0.1. OptRatio is run 100,000 times for each deadline. The error bars are computed with the mean plus/minus two standard deviations of the number of successes. The lognormal distribution has parameters α ≈ -1.15 and β ≈ 1.52 to have an expected value µ = 1 and a standard deviation σ = 3.

Figure 5 :

 5 Figure 5: Here b = d = 100. For Beta(0.5,0.5) (left), we have µ = 0.5. For Gamma(0.5,2) (right), we have µ = 1. The cutting threshold is = 0.01 for OptRatio in both plots.

Figure 6 :

 6 Figure 6: Here b = d = 100. For Beta(0.5,0.5) (left), we have µ = 0.5. For Gamma(0.5,2) (right), we have µ = 1. The cutting threshold for OptRatio varies from 0.1 down to 0.001in both plots.

Table 1 :

 1 Probability distributions with their Probability Distribution Function (PDF) and density graph. Supports are [0, ∞) for all distributions except for Uniform, where it is [a, b] and Beta, where it is [0, 1].

	Note that

Throughout the text, we use both terms VM and processor indifferently.

See the examples of Section 4.1 for an illustration. RR n°9257

RR n°9257

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgements

A shorter version of this work has been published in the proceedings of SBAC-PAD'18 [9].


Nicolas Turpault

Romain Serizel

Emmanuel Vincent

SEMI-SUPERVISED TRIPLET LOSS BASED LEARNING OF AMBIENT AUDIO EMBEDDINGS

Keywords: Semi-supervised learning, triplet loss, audio tagging, audio embedding

Deep neural networks are particularly useful to learn relevant representations from data. Recent studies have demonstrated the potential of unsupervised representation learning for ambient sound analysis using various flavors of the triplet loss. They have compared this approach to supervised learning. However, in real situations, it is common to have a small labeled dataset and a large unlabeled one. In this paper, we combine unsupervised and supervised triplet loss based learning into a semi-supervised representation learning approach. We propose two flavors of this approach, whereby the positive samples for those triplets whose anchors are unlabeled are obtained either by applying a transformation to the anchor, or by selecting the nearest sample in the training set. We compare our approach to supervised and unsupervised representation learning as well as the ratio between the amount of labeled and unlabeled data. We evaluate all the above approaches on an audio tagging task using the DCASE 2018 Task 4 dataset, and we show the impact of this ratio on the tagging performance.

INTRODUCTION

Sound carries a lot of information that humans can interpret even unconsciously. However, building a system that is able to automatically recognize sounds in real environments is far from trivial. In the recent years, there has been a growing interest for research in ambient sound analysis [START_REF] Virtanen | Computational Analysis of Sound Scenes and Events[END_REF] motivated by applications in various domains including surveillance, smart cities or home assisted living. Audio tagging is a particular task of ambient sound analysis that consists of detecting the sound event classes that occur in an audio clip regardless of their start and end times. In the following, we aim to detect and classify domestic sounds in 10-second clips from the DCASE 2018 Task 4 dataset [START_REF] Serizel | Large-Scale Weakly Labeled Semi-Supervised Sound Event Detection in Domestic Environments[END_REF].

State-of-the-art methods for audio tagging rely on deep neural networks (DNNs), such as convolutional neural networks (CNNs) [START_REF] Jeong | Audio tagging system for DCASE 2018: focusing on label noise, data augmentation and its efficient learning[END_REF][START_REF] Dorfer | Training general purpose audio tagging networks with noisy labels and iterative self-verification[END_REF], recurrent neural networks (RNNs) [START_REF] Sharath Adavanne | Sound event detection in multichannel audio using spatial and harmonic features[END_REF], or a combination of both usually referred to as CRNNs [START_REF] Xu | Large-scale weakly supervised audio classification using gated convolutional neural network[END_REF][START_REF] Iqbal | Stacked convolutional neural networks for generalpurpose audio tagging[END_REF]. These methods learn a discriminative representation of the data called an embedding which helps the classification. The embedding may be learned jointly with the classifier by minimizing a classification cost, or separately by methods such as siamese networks [START_REF] Bromley | Signature Verification using a "Siamese" Time Delay Neural Network[END_REF] or triplet networks [START_REF] Wang | Learning Fine-Grained Image Similarity with Deep Ranking[END_REF] which rely This work was made with the support of the French National Research Agency, in the framework of the project LEAUDS "Learning to understand audio scenes" (ANR-18-CE23-0020) and the French region Grand-Est. Experiments presented in this paper were carried out using the Grid5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

on different costs. Triplet networks have been used for images [START_REF] Ming | Simple Triplet Loss Based on Intra/Inter-Class Metric Learning for Face Verification[END_REF], speech [START_REF] Bredin | TristouNet: Triplet loss for speaker turn embedding[END_REF], and music [START_REF] Lu | Deep ranking: Triplet MatchNet for music metric learning[END_REF] and recently for ambient sounds [START_REF] Jansen | Unsupervised Learning of Semantic Audio Representations[END_REF]. They are trained on triplets of data points consisting of an anchor, a positive sample, and a negative sample. All the above methods are supervised learning methods. Therefore they highly depend on the amount of labeled data. Annotating data is a tedious task. The availability of labeled datasets is usually the bottleneck that hinders the application of ambient sound analysis to real world problems.

Recently, there have been efforts to collect substentially larger datasets. Audioset [START_REF] Jort | Audio Set: An ontology and humanlabeled dataset for audio events[END_REF] is an audio dataset including clips with overlapping events in real environments but labels are not carefully verified and often unreliable [START_REF] Jort | Audio Set: An ontology and humanlabeled dataset for audio events[END_REF]. Freesound [START_REF] Fonseca | Freesound datasets: a platform for the creation of open audio datasets[END_REF] is an open source platform that provides more reliable labels and can be used to build meaningful tagging datasets [START_REF] Fonseca | Generalpurpose Tagging of Freesound Audio with AudioSet Labels: Task Description, Dataset, and Baseline[END_REF]. However, most clips in Freesound contain isolated events and little or no background noise. Therefore, the applicability of systems trained on Freesound to real-world applications is limited. Soundscape synthesis and data transformation [START_REF] Salamon | Scaper: A library for soundscape synthesis and augmentation[END_REF] can be used to simulate more realistic environments or create large synthetic datasets from smaller labeled datasets.

In this paper, we use the DCASE 2018 Task 4 dataset which is a subset of Audioset where some labels have been manually verified and the others have been discarded. One solution to exploit a dataset without annotations is to use unsupervised learning approaches based on generative DNNs [START_REF] Lee | Unsupervised feature learning for audio classification using convolutional deep belief networks[END_REF][START_REF] Xu | Unsupervised Feature Learning Based on Deep Models for Environmental Audio Tagging[END_REF], dimension reduction and clustering [START_REF] Salamon | Unsupervised feature learning for urban sound classification[END_REF][START_REF] Komatsu | Acoustic event detection method using semisupervised non-negative matrix factorization with mixtures of local dictionaries[END_REF], or triplet networks [START_REF] Jansen | Unsupervised Learning of Semantic Audio Representations[END_REF]. Jansen et al. proposed to train a triplet network with different unsupervised triplet sampling1 strategies making use of data transformation and compared them to a fully supervised sampling strategy. They demonstrated that an unsupervised sampling strategy can achieve 84% of the mean average precision achieved by a supervised sampling strategy for ambient sound analysis task on Audioset. This approach does not take labels into account during the learning process.

Semi-supervised learning is a combination of supervised and unsupervised learning approaches that allows the exploitation of both labeled and unlabeled data [START_REF] Oliver | Realistic Evaluation of Deep Semi-Supervised Learning Algorithms[END_REF]. It has usually been applied to ambient sound analysis by annotating new data recursively during consecutive passes through a supervised system [START_REF] Zhang | Semi-supervised learning helps in sound event classification[END_REF][START_REF] Pedro | An experimental study of semi-supervised EM algorithms in audio classification and speaker identification[END_REF]. This pseudo-labeling approach provides a slight performance improvement. However clips that are given labels with low confidence in the early passes tend to remain with low confidence as training progresses through the passes. Recently, a task in the DCASE challenge has targeted semi-supervised approaches [START_REF] Serizel | Large-Scale Weakly Labeled Semi-Supervised Sound Event Detection in Domestic Environments[END_REF]. The winner used a mean-teacher system [START_REF] Jiakai | Mean teacher convolution system for DCASE 2018 task 4[END_REF] which makes use of two networks. However, to the best of our knowledge, semi-supervised learning of triplet networks has not yet been studied.

In this paper we propose semi-supervised sampling strategies to create triplets and study their application to audio tagging. Sampling strategies have already been discussed for siamese networks [START_REF] Riad | Sampling strategies in Siamese Networks for unsupervised speech representation learning[END_REF].

Here we start from the sampling strategies used by Jansen et al. [START_REF] Jansen | Unsupervised Learning of Semantic Audio Representations[END_REF]. We then propose a new way of selecting the positive sample in a triplet and combine it with the semi-supervised sampling strategy.

We first describe the problem in Section 2 then we explain the proposed solution in Section 3. The experimental setup is described in Section 4 before drawing some conclusions in Section 5.

PROBLEM DESCRIPTION

The problem of audio tagging consists of identifying which ambient sound classes are present in an audio clip regardless of their position in time. Let C be a set of C classes. We have a small set of labeled data D L = {(x l , y l )} L l=1 and a large set of unlabeled data D U = {(xu)} U u=1 where x i , i ∈ {u, l}, is a time-frequency representation of the input data and y l = [e1, ..., eC ] is a vector containing the labels with ec ∈ {0, 1} indicating whether event class c is present in the clip or not. Note that the vector of labels can contain multiple classes. Let D = {D L , D U } denote the set containing both labeled and unlabeled data. In the following, we aim to learn embeddings of both unlabeled and labeled data using the triplet loss.

Triplet loss

The aim of the triplet loss [START_REF] Wang | Learning Fine-Grained Image Similarity with Deep Ranking[END_REF] is to find meaningful embeddings of the data that bring the anchor and the positive example closer than the negative example and the anchor. In the following, (x a , x p , x n ) is a triplet defined by (anchor, positive, negative) samples and the cost function to be minimized is:

x i ∈D N ||f (x a i ) -f (x p i )|| 2 2 -||f (x a i ) -f (x n i )|| 2 2 + δ + (1)
where + is the hinge loss, ||.||2 is the L2 norm and δ is the margin. f (x) is the embedding of x. This cost function differs from the pairbased costs used in siamese networks by ensuring a balanced number of negative and positive examples.

Supervised sampling strategy

Different triplet sampling strategies have been proposed in the literature, which exploit the data and the available labels. Different sampling strategies result in different embeddings. The simplest strategy tested by Jansen et al. [START_REF] Jansen | Unsupervised Learning of Semantic Audio Representations[END_REF] relies on labeled data only. In this strategy, the positive and negative samples are randomly chosen under the constraints that the positive sample has at least one label in common with the anchor and the negative sample has no label in common with the anchor.

Transformation-based unsupervised sampling strategy

Jansen et al. [START_REF] Jansen | Unsupervised Learning of Semantic Audio Representations[END_REF] also proposed an unsupervised sampling strategy, which does not make use of any label. In this strategy, a transformed version of the anchor is used as the positive sample and semi-hard mining is employed to obtain the negative sample. Semi-hard mining consists of choosing the negative sample that is closest to the anchor in the embedding space while being further away than the positive sample [START_REF] Schroff | FaceNet: A Unified Embedding for Face Recognition and Clustering[END_REF]. We describe below the different transformations used to obtain the positive sample.

Gaussian noise: The positive sample is created by adding Gaussian noise with a standard deviation of σ to the anchor.

Time and frequency translation: The positive sample is created by circularly shifting the anchor sample in time by an integer number of frames sampled uniformly from [0, T -1], where T is Temporal proximity: The positive sample is a sample from the same audio clip as the anchor sample with a time difference inferior to ∆t between them.

Example mixing: The positive sample is a mix of the anchor and the negative samples using

x p = x a + α[E(x a )/E(x n )]x n
where E means the energy. The negative sample is taken randomly in the dataset.

PROPOSED SEMI-SUPERVISED SAMPLING STRATEGIES

The supervised sampling strategy proposed by Jansen et al. [START_REF] Jansen | Unsupervised Learning of Semantic Audio Representations[END_REF] uses labeled data only, while their other approaches are fully unsupervised and discard the labels. By contrast, we propose two semisupervised sampling strategies where labeled and unlabeled triplets are both used during training. Our strategies differ by the choice of the positive sample when dealing with unlabeled data.

Semi supervised strategy

In the semi-supervised setting, we use the supervised strategy when the label is available and the unsupervised strategy when the sample is unlabeled. The following unsupervised strategies to choose the positive sample are always combined with semi-hard mining to choose the negative sample in our experiments (See table 1).

Positive sample: transformed anchor

This strategy consists of generating the positive sample by transforming the anchor sample as above.

Positive sample: nearest sample

This strategy consists of taking the nearest sample in the input space.

x a ∈ D U x p ∈ {xi ∈ D|xi = argminx i (||xi -x a || 2 2 )}
The idea is to use the sparsity and repartition of the data. Previous work has used it to regularize the embedding [START_REF] Thulasidasan | Acoustic classification using semi-supervised Deep Neural Networks and stochastic entropy-regularization over nearest-neighbor graphs[END_REF]. A transformed data sample can be seen as a close point in the input space. Therefore taking the nearest point in the input space is implicitly assuming these points should also be close in the representation space.

As can be seen in Fig. 1, our motivation is to search beyond the space spanned by the transformed data to create the embedding.

Sampling strategies

Unsupervised

Semisupervised Supervised Indeed, when we have many samples in a small space, taking a transformed version of the anchor as the positive sample can make sense, but when the data points are sparse, it is interesting to take the nearest sample to enlarge the space spanned by positive samples in the input space. Figure 1 represents this latter case. However, it can happen that the nearest sample is closer than some transformed samples.

S1 [13] S2 S3 S4 S5 Positive Label X X X X Trans X X Nearest X Negative Label X X X S-hard X X X X

EXPERIMENTAL SETUP

Experimental description

In this work we are comparing 5 sampling strategies and a baseline system. Each sampling strategy differs from the others by the selection of the positive and the negative sample. The positive sample can be the nearest sample in the input space, a sample with a common label with the anchor a transformed version of the anchor. The negative sample can be a sample wich does not have a common label with the anchor or chosen thanks to semi-hard mining [START_REF] Schroff | FaceNet: A Unified Embedding for Face Recognition and Clustering[END_REF]. The different strategies are summarized in Table 1: strategy 1 (S1) is the unsupervised sampling strategy suggested by Jansen et al. using data transformation, strategy 2 (S2) is a semi-supervised sampling strategy that uses transformations when no label is available, strategy 3 (S3) is a proposed sampling strategy which uses the nearest sample as positive when the anchor is unlabeled, strategy 4 (S4) uses labels to select the positive sample and semi-hard-mining to select the negative sample and strategy 5 (S5) relies on labels for both the positive and the negative sample selection.

Dataset

We use the dataset from DCASE 2018 task 4 [START_REF] Serizel | Large-Scale Weakly Labeled Semi-Supervised Sound Event Detection in Domestic Environments[END_REF]. It is composed of 10-second audio clips. Ten different classes of events are considered.

The training set is composed of a labeled set and an unlabeled set. The labeled set is composed of 1,578 human-labeled audio clips. The unlabeled set contains 14,412 clips. These clips were annotated in Audioset, but since the labels have not been verified they have been discarded in this dataset. However, the clips in Audioset have been choosen so they should contain on of the ten classes considered and the distribution per class of sound event should be close to the distribution in the labeled set. Since the labels in Audioset can be very noisy, the distribution might not be exactly similar. The test set contains 288 labeled clips and the evaluation set contains 880 labeled clips. Both of these subsets have a similar distribution as the labeled training set and time coded labels. We are comparing audio tagging performance, therefore these labels are converted to clip-level labels (an event is present or not during the clip). We use the test set to validate our training and the evaluation set to perform the evaluation of the system.

Features

The audio signals are mono-channel and sampled at 44,100 Hz. From this we compute a fast Fourier transform on 25 ms windows and a step size of 10ms. We then compute log-mel spectrograms features with 64 filters. Every 10-seconds segment is then divided in 0.96 s subsegments during training as in Jansen et al. [START_REF] Jansen | Unsupervised Learning of Semantic Audio Representations[END_REF]. We assume that each 0.96 s subsegment has the same label as the full 10-seconds clip. However, this might be an issue for some classes which correspond to short events. The data transformation settings are similar to Jansen et al. [START_REF] Jansen | Unsupervised Learning of Semantic Audio Representations[END_REF] (σ = 0.5, S = 10, α = 0.25 and ∆t = 10s).

Model architecture

The baseline is a CRNN inspired by DCASE 2018 task 4. The CNN is composed of 3 convolutional layers with 64 3x3 filters, a pooling of 4 in frequency and no pooling in time. The RNN is a one layer bidirectional gated recurrent unit (BiGRU) with 64 cells followed by a fully connected layer with 10 cells to tag the audio clips, the final prediction is the average over the frames. The classification loss is the binary cross entropy.

In the case of embedding computation, a CNN similar to the baseline is trained using the triplet loss. The triplet loss margin is set to 1 for all models. We train a classifier using the embeddings as input. The classifier is a RNN using two layers of bidirectional gated recurrent unit (BiGRU) with 64 cells followed by a fully connected layer with 10 cells to tag the audio clips, the final prediction is the average over the frames. A single RNN layer was not enough parameters to be optimized to perform the classification on embeddings, two layers have been choosen which stays a small network. Note that this 2 layers configuration we tried with the baseline but it did not perform as well as a single RNN layer in that case.

All classifiers are trained on the 1,578 labeled files from DCASE 2018 task 4 training set.

Metric

The audio tagging performance is evaluated with F1-score at clip level [START_REF] Wang | Learning Fine-Grained Image Similarity with Deep Ranking[END_REF] computed class-wise over the whole evaluation set:

F 1c = 2T Pc 2T Pc + F Pc + F Nc
where T Pc, F Pc and F Nc are the number of true positives, false positives and false negative for a given class of event c over the whole evaluation set, respectively. The final score is the F1-score averaged over class regardless of the number of events per class (macro averaged):

F 1macro = c∈C F 1c C
where C is the classes ensemble and C the number of classes.

Results

The first experiment compare the performance of the different strategies depending on the amount of unlabeled data. In the first case we use 31,560 triplets. For S1, S2, S3 it corresponds using the same number of labeled and unlabeled triplets and taking each sample as an anchor once. For systems S4 and S5 we use each sample twice In Figure 2 we show different embeddings learned with the different sampling strategies. For simplicity, we chose to show only the 3 more distinctive classes for each strategy on the graph. This figure presents embeddings obtained with systems trained using 31,560 triplets. We can make a correlation between the difference of results between systems obtain in Table 2 and embeddings in the graph.

All cases in Table 2 show the benefit of semi-supervised triplet sampling. Indeed, we can see that semi-supervised sampling using data transformation outperforms unsupervised sampling using data transformation. It means that labels bring meaningful information to obtain embeddings that are suitable for classification. In all cases it is better to take the transformed version of the data as positive sample than the nearest sample. This can be due to the lack of variability, to overcome this problem, we could take one of the nearest samples. S4 shows semi-hard mining does not seem suitable when taking a labeled positive sample. In the first case, we use only twice the same sample to create triplets, we are in a scenario where the supervised embedding makes sense. The second and third cases allow us to compare the different approaches and how to deal with more unlabeled data. Indeed, we see that sampling strategy S2 benefits from unlabeled data to a certain point. However, all other systems seem to be less adapted to the task when using more unlabeled data. The unsupervised data transformation sampling strategy can be seen as a way of having a general embedding of the data, it is a good regularizer to be able to generalize in a task, and that can explain the performance of the semi-supervised data transformation sampling strategy. In the case of taking the nearest sample to create the positive, more data means closer samples. It can explain the reduction of performance when we gradually add unlabeled data. Indeed, in this case, the nearest sample can be closer to the anchor than a transformed sample. To overcome this problem, we can think about taking the nearest sample of the anchor with a constraint of being further away than transformed data samples. Results of S5 can be explained by an overfitting of the training and validation set because we see each anchor many times when we increase the number of triplets. We can also notice that most of the experiments outperform the baseline and the best experiment uses a semi-supervised setting with transformed data (S2) but without using all the unlabeled data.

In Table 3 we study the impact of the ratio between labeled and unlabeled data. We take 31,560 triplets with different proportions of labeled and unlabeled data. We can see the importance of labeled data in this experiment. S3 is much more sensitive to the number of labeled data than S2. We can see that when we do not have enough labeled data, performance completely drops. The amount of labeled data needed for a class seems to depend on the number, duration and overlap with other classes. When using more labeled data, performance is close to the supervised case with a small regularization from the unlabeled data, which can explain the best performance.

CONCLUSION

In this paper, we introduced semi-supervised sampling strategies to create triplets. We compared their performance and analyze the impact of different strategies to select the positive and negative samples. Semi-supervised sampling strategies were shown to outperform both supervised and unsupervised strategies. The ratio between labeled and unlabeled data can then have a great impact on the final performance. In the next step we could further investigate the interactions between the different methods to select positive and negative samples and explore their combination to improve the embeddings. This work could also be extended to a semi-supervised learning algorithm which can combine the triplet loss and the classification loss in order to benefit from both the embedding learning aspect and the classification targeting learning.

Fig. 1 :

 1 Fig. 1: Illustration of triplet sampling.

Fig. 2 :

 2 Fig. 2: Class separation for different embeddings (t-sne)

U 7 Table 3 :

 73 Macro f-score on the evaluation set with varying number of labeled (L) and unlabeled (U) triplets for strategies 2 and 3. Experiences have been launched 3 times to get 95% confidence score.

Table 1 :

 1 Sampling strategies for the different systems. Trans means transformation and S-hard means semi-hard mining

Table 2 .

 2 , the baseline has a macro F1-score of 49.61% and the classifier applied on log-mel spectrograms has a macro F1-score of 35.29%.

	Sampling strategy	S1	S2	S3	S4	S5
	/ Nb triplets
	31,560	52.32 54.35 50.96 42.47 53.59
	85,780	51.44 54.57 46.13 42.72 51.85
	159,900	51.62 52.27 38.59 42.19 49.95

Table 2 :

 2 Macro f-score on the evaluation set

In this paper, statistical sampling, not signal processing sampling