Alberto Abbondandolo
email: alberto.abbondandolo@rub.de

Marco Mazzucchelli
email: marco.mazzucchelli@ens-lyon.fr

THE MONOTONICITY OF THE SYSTOLE OF CONVEX RIEMANNIAN TWO-SPHERES

Throughout this note, the notion of convexity must be understood in the differentiable sense: A compact three-ball B ⊂ R 3 with smooth boundary is strictly convex when there exists a smooth function F : R 3 → [0, ∞) with positive definite Hessian at every point and such that ∂B = F -1 (1). Equivalently, the boundary sphere M = ∂B, which will always be equipped with the Riemannian metric g that is the restriction of the ambient Euclidean metric, has strictly positive Gaussian curvature. The systole sys(M ) > 0 is the length of the shortest closed geodesic of (M, g). Our main result answers in dimension 3 a question that was posed to us by Yaron Ostrover: Theorem 0.1. Let B 1 ⊆ B 2 be two compact strictly convex three-balls in R 3 with smooth boundary. Then sys(∂B 1 ) ≤ sys(∂B 2 ).

The main ingredient of the proof is the observation that the systole of positively curved Riemannian two-spheres coincides with the classical Birkhoff min-max, as we will now prove. Let (M, g) be a Riemannian two-sphere. We denote the energy functional on the W 1,2 free loop space by

E : ΛM = W 1,2 (S 1 , M ) → [0, ∞), E(ζ) = S 1 ζ(t) 2 g dt.
Here and in the following, we denote by S 1 = R/Z the 1-periodic circle. We consider the unit sphere S 2 ⊂ R 3 . For each z ∈ [-1, 1], we denote by γ z : S 1 → S 2 the parallel at latitude z, parametrized as

γ z (t) = 1 -z 2 cos(2πt), 1 -z 2 sin(2πt), z .
For each continuous map u : [-1, 1] → ΛM such that E(u(0)) = E(u(1)) = 0 there exists a unique continuous map ũ :

S 2 → M such that u(z) = ũ • γ z for each z ∈ [-1, 1].
We denote by U the space of such maps u whose associated ũ has degree 1. The Birkhoff min-max value bir(M, g) = inf

u∈U max z∈[-1,1] E(u(z)) 1/2
is the length of some closed geodesic of (M, g).

Date: October 24, 2020. 1991 Mathematics Subject Classification. 53C22, 58E10.

Lemma 0.2. On every positively curved closed Riemannian two-sphere (M, g), we have bir(M, g) = sys(M, g).

Proof. Let γ : S 1 → M be a shortest closed geodesic of (M, g) parametrized with constant speed, so that E(γ) = L(γ) 2 = sys(M, g) 2 . A theorem of Calabi-Cao [START_REF] Calabi | Simple closed geodesics on convex surfaces[END_REF] implies that γ is simple, that is, an embedding γ : S 1 → M . We fix an orientation on M , and consider the corresponding complex structure of (M, g).

Namely, for every non-zero v ∈ T x M , the tangent vector Jv ∈ T x M is obtained by rotating v in the positive direction of an angle π/2. We consider the vector field ν(t) = J γ(t) orthogonal to γ(t). Notice that ν is a parallel vector field, since the complex structure J is parallel. If K g denotes the Gaussian curvature of (M, g), we have

d 2 E(γ)[ν, ν] = S 1 ∇ t ν 2 g -K g γ 2 g ν 2 g dt = - S 1 K g γ 4 g dt < 0. (0.1)
We now consider Morse's finite dimensional approximation of the free loop space (see, e.g., [START_REF] Milnor | Morse theory[END_REF]). We fix a positive integer k that is large enough so that

d(ζ(t 0 ), ζ(t 1 )) < injrad(M, g) for all ζ ∈ ΛM with E(ζ) ≤ E(γ) = sys(M, g) 2 and for all t 0 , t 1 ∈ R with |t 1 -t 0 | < 1/k.
Here, d denotes the Riemannian distance on (M, g). We consider the open finite dimensional manifold

Λ k M = x = (x 0 , ..., x k-1 ) ∈ M × ... × M d(x i , x i+1 ) < injrad(M, g) ∀i ∈ Z k .
Such a manifold admits an embedding

ι : Λ k M → ΛM, ι(x) = γ x ,
where each restriction γ x | [i/k,(i+1)/k] is the shortest geodesic parametrized with constant speed joining x i and x i+1 . We denote the restricted energy functional by

E k = E • ι : Λ k M → [0, ∞), E k (x) = k i∈Z k d(x i , x i+1 ) 2 .
Let x := ι -1 (γ). We consider the tangent vector v := (v 0 , ..., v k-1 ) ∈ T x (Λ k M ) such that v i = ν(i/k) for all i ∈ Z k . Inequality (0.1) readily implies that dι(x)v lies in the negative cone of the Hessian d 2 E(γ), since

d 2 E k (x)[v, v] = d 2 dz 2 z=0 E(ι(exp x (zv)) ≤ d 2 dz 2 z=0 E(exp γ(•) (zν(•))) = d 2 E(γ)[ν, ν] < 0. (0.2)
Here, the exponential map in Λ k M is the one associated with the natural Riemannian metric g ⊕ ... ⊕ g.

The complement M \ γ has two connected components B + and B -, each one diffeomorphic to a two-ball. The vector field ν points into one of them, say B + . We define the continuous map

w : [-1/3, 1/3] → Λ k M, w(z) = exp x (z v).
Notice that w(0) = x. We fix > 0 small enough so that, for all z ∈ (0, 1/3], the loop ι(w(±z)) is entirely contained in the open ball B ± , and by Equation (0.2) we have

E k (w(z)) < E k (w(0)) = sys(M, g) 2 , ∀z ∈ [-1/3, 1/3] \ {0}.

THE MONOTONICITY OF THE SYSTOLE OF CONVEX RIEMANNIAN TWO-SPHERES 3

We now consider the open subspaces U + , U -⊂ Λ k M given by

U ± = Λ k M ∩ (B ± × ... × B ± ).
We have w(±1/3) ∈ U ± . The flow φ s of the anti-gradient -∇E k is complete in positive time s in the sublevel set E -1 k ([0, sys(M, g) 2 ]). We claim that φ s (w(±1/3)) ∈ U ± , ∀s ≥ 0.

Indeed, assume by contradiction that there exists s 0 > 0 such that φ s0 (w(±1/3)) ∈ ∂U ± , and take s 0 to be the minimal such time. If y := φ s0 (w(±1/3)), the components of the anti-gradient vector z := -∇E k (y) are given by

z i = 2( γy ( i k + ) -γy ( i k -)), ∀i ∈ Z k .
Since y ∈ ∂U ± , at least one of its components y i must belong to ∂B ± . Assume that all the y i 's belong to ∂B ± , and therefore they are of the form y i = γ(t i ) for some t i ∈ S 1 . In this case, we have z i = λ i γ(t i ) for some λ i ∈ R; but this is impossible, since it would imply that all the components of φ s (w(±1/3)) belong to ∂B ± for all s ∈ R, and thus that φ s (w(±1/3)) belong to ∂U ± for all s ∈ R. Therefore at least one component y i ∈ ∂B ± is adjacent to a component in the interior y i-1 ∈ B ± . However, this implies that the vector z i points inside B ± , and therefore φ s0-δ (w(±1/3)) ∈ U ± for all δ > 0 small enough, contradicting the minimality of s 0 . We set δ := min{injrad(M, g), sys(M )/(4k)}. Since E k (φ s (w(±1/3))) < sys(M, g) 2 for all s ≥ 0, and since sys(M, g) 2 is the smallest positive critical value of E k , we can fix a large enough s > 0 such that E k (φ s (w(±1/3))) < δ 2 . We extend w to a map w : [-2/3, 2/3] → Λ k M by setting w(±z) = φ (3z-1)s (w(±1/3)),

∀z ∈ [1/3, 2/3].

Notice that w(±z) ∈ U ± for all z ∈ (0, 2/3], and E k (w(±2/3)) < δ 2 . We set y ± = (y ± 0 , ..., y ± k-1 ) := w(±2/3). For each r ∈ [0, 1], we define y ± (r) = (y ± 0 (r), ..., y ± k-1 (r)) by

y ± i (r) := exp y ± 0 ((1 -r) exp -1 y ± 0 (y ± i )).
Notice that y ± (0) = y ± , y ± (r) ∈ U ± , and

E k (y ± (r)) = k i∈Z k d(y ± i (r), y ± i+1 (r)) 2 < 4k 2 δ 2 ≤ sys(M, g) 2 , ∀r ∈ [0, 1], E k (y ± (1)) = 0.
We extend w to a continuous map w :

[-1, 1] → Λ k M by setting w(±z) = y ± (3z -2), ∀z ∈ [2/3, 1].
Finally, we define u := ι • w : [-1, 1] → ΛM . Notice that the associated continuous map ũ : S 2 → M has degree 1; indeed, the preimage u -1 (γ(t)) is a singleton for every t ∈ S 1 , and the restriction of u to a neighborhood of u -1 (γ) is a homeomorphism onto its image. Therefore u ∈ U, and bir(M, g) ≤ max

z∈[-1,1] E(u(z)) 1/2 = E(u(0)) 1/2 = sys(M, g).
On the other hand, bir(M, g) 2 is a positive critical value of E, and therefore bir(M, g) ≥ sys(M, g).

Proof of Theorem 0.1. We set M i := ∂B i , i = 1, 2. Since the regions B 1 ⊂ B 2 are strictly convex, for each x ∈ M 2 there exists a unique π(x) ∈ M 1 such that

x -π(x) = min y∈M1

x -y .

The map π : M 2 → M 1 is a 1-Lipschitz homeomorphism with respect to the Riemannian metrics g i on M i that are restriction of the ambient Euclidean metric. In particular, for every W 1,2 curve γ 2 : S 1 → M 2 , if we denote by γ 1 := π • γ 2 its image in M 1 , we have E(π • u(z)) 1/2 ≥ bir(M 1 ).

This, together with Lemma 0.2, implies that sys(M 2 ) ≥ sys(M 1 ).

S1

  γ2 (t) 2 dt ≥ S1 γ1 (t) 2 dtWe denote by U 1 and U 2 the family of maps involved in the definition of the Birkhoff min-max values of M 1 and M 2 respectively. Notice that π • u ∈ U 1 for all u ∈ U 2 . Therefore, if we denote the energy of W 1,2 loops γ : S 1 → R 3 by E(γ) =


Zilong Zhao

Sophie Cerf

Bogdan Robu

Nicolas Marchand

Event-Based Control for Online Training of Neural Networks

Keywords: Event Based Control, Gradient Methods, Neural Networks

Convolutional Neural Network (CNN) has become the most used method for image classification tasks. During its training the learning rate and the gradient are two key factors to tune for influencing the convergence speed of the model. Usual learning rate strategies are time-based i.e. monotonous decay over time. Recent state-of-the-art techniques focus on adaptive gradient algorithms i.e. Adam and its versions. In this paper we consider an online learning scenario and we propose two Event-Based control loops to adjust the learning rate of a classical algorithm E (Exponential)/PD (Proportional Derivative)-Control.

The first Event-Based control loop will be implemented to prevent sudden drop of the learning rate when the model is approaching the optimum. The second Event-Based control loop will decide, based on the learning speed, when to switch to the next data batch. Experimental evaluation is provided using two state-ofthe-art machine learning image datasets (CIFAR-10 and CIFAR-100). Results show the Event-Based E/PD is better than the original algorithm (higher final accuracy, lower final loss value), and the Double-Event-Based E/PD can accelerate the training process, save up to 67% training time compared to state-of-theart algorithms and even result in better performance.

I. INTRODUCTION

Convolutional Neural Network (CNN) is a popular machine learning algorithm for image classification because it outperforms any other network architecture on visual data. In this paper, we focus on an online learning scenario where data used for training the CNN comes in batches over time [START_REF] Tien Nguyen | Applications of Online Deep Learning for Crisis Response Using Social Media Information[END_REF], [START_REF] Hong | Online tracking by learning discriminative saliency map with convolutional neural network[END_REF]. A CNN model is a neural network structure with a set of weights which are iteratively learned from training data using methods such as Stochastic Gradient Descent (SGD). The SGD algorithm is parametrized with a learning rate λ. A large λ helps the model to converge faster but increases the risk of diverging [START_REF] Bengio | Practical recommendations for gradient-based training of deep architectures[END_REF]. A small λ slows the convergence but may lead to a local minimum.

There are two main learning rate evolution strategies: timebased or adaptive. In most time-based learning rate strategies, λ decreases following a predefined decay function [START_REF] An | Exponential decay sine wave learning rate for fast deep neural network training[END_REF]. Cyclical strategies have also been developed, where two boundaries are defined and λ cyclically varies between them. The disadvantage of these algorithms is that the learning rate path is fixed before training, it cannot be adjusted when necessary.

Adaptive learning rate algorithms such as Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF], Nadam (Adam with Nesterov momentum) [START_REF] Dozat | Incorporating Nesterov momentum into Adam[END_REF] and AMSGrad [START_REF] Reddi | On the convergence of Adam and beyond[END_REF] are recent state-of-the-art algorithms which mainly focus on the convergence speed. Different from SGD which uses only the current value of the gradient to update weights, these algorithms use squared gradient to scale the learning rate and take advantage of momentum by using moving average of the gradients. Nevertheless, Wilson et al. [START_REF] Wilson | The marginal value of adaptive gradient methods in machine learning[END_REF] suggested that 1 Univ. Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, 38000 Grenoble, France firstname.lastname@gipsa-lab.fr adaptive gradient methods do not generalize as well as SGD. These methods tend to perform well in the initial portion of training but are outperformed by SGD at later stages of training [START_REF] Shirish Keskar | Improving Generalization Performance by Switching from Adam to SGD[END_REF]. To address this issue, AdaBound [START_REF] Luo | Adaptive gradient methods with dynamic bound of learning rate[END_REF] employs dynamic bounds on learning rates to achieve a gradual and smooth transition from adaptive methods to SGD.

Up to our knowledge, E (Exponential)/PD (Proportional Derivative) control [START_REF] Zhao | Feedback control for online training of neural networks[END_REF] is the first adaptive learning rate algorithm which uses control theory to dynamically adapt the learning rate during the learning process. It uses only current gradient as in SGD, but its learning rate λ is dynamically calculated based on the loss value. During the E phase, that corresponds to the beginning of the training when the loss value is continuously decreasing, λ is increased each time step by a factor of two. Once the loss stops decreasing, the PD phase takes over and, considering CNN as a dynamic system, computes the control input (i.e. λ) based on the CNN's output (i.e. the loss value).

The above-mentioned algorithms are time-based, in the sense of a periodic computation of the control law regardless its utility. In this paper, we propose two event-based control strategies to reduce the time CNN spends learning "inefficiently" from data, as well as an extensive evaluation. Moreover, while using event-based mechanisms we should expect for a reduction in the use of resources [START_REF] Aström | Event based control[END_REF], [START_REF] Durand | Further results on event-based PID controller[END_REF], without degrading performances [START_REF] Lunze | A state-feedback approach to event-based control[END_REF] and with stability and robustness guarantees [START_REF] Marchand | A general formula for event-based stabilization of nonlinear systems[END_REF]. Numerous Event-Based control strategies in the literature are focusing on stability and performance guarantees. Most event-based PID controllers are based on level-crossing triggering of some measuring error (see for instance [START_REF] Durand | Further results on event-based PID controller[END_REF], [START_REF] Årzén | A simple event-based PID controller[END_REF]) or more generally rely on an event-function based on Lyapunov functions (see for instance [START_REF] Marchand | A general formula for event-based stabilization of nonlinear systems[END_REF], [START_REF] Velasco | On Lyapunov sampling for eventdriven controllers[END_REF]).

The two introduced Event-Based control algorithms are: (i) Event-Based Learning Rate control, which will be implemented to prevent sudden drop of the learning rate when the model is approaching the optimum; (ii) Event-Based Learning Epochs control, which will decide based on the learning speed when to switch to the next data batch.

Our algorithm is evaluated on two classical machine learning image datasets CIFAR-10 and CIFAR-100 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF]. The results are compared with four best state-of-the-art algorithms: Adam, Nadam, AMSGrad and AdaBound. Our results show that the E/PD combined with the two introduced Event-Based control not only outperforms original E/PD but also converges faster than any other state-of-the-art counterpart.

The article is organised as follows: after a brief introduction of the problem in Section I, we detail the scenario and the system to be controlled (i.e. a CNN) with its input and output metrics in Section II. The contribution, i.e., the two eventbased mechanisms, is described in Section III.Section IV contains the experimental setup, results and analysis. The article ends with a conclusion and perspectives for further work in Section V.

II. BACKGROUND

A. Classical Online Learning Scenario

We consider a dataset T with a total number of training instances T , each one belonging to a class c :

Z + → [1, C].
The whole dataset is composed of B subsets (i.e. batches), T i is the i th batch where i : Z + → [1, B]. Each batch equally contains S data instances and will be used to train the model for N epochs (i.e. N times). At the reception of a new batch, the learning rate algorithm is reset with initial values. Classical online learning scenario is illustrated in Fig. 1.

B. Convolutional Neural Network and Gradient

Convolutional Neural Network (CNN) is the state-of-theart learning mechanism for image classification [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]. CNN neurons functions are parameterized with weights and, eventually, bias. The objective of the learning phase is to make iterative adjustments to these biases and weights to better fit the data. These weights in the CNN are usually updated using Stochastic Gradient Descent techniques (SGD):

θ j = θ j-1 -λ ∂L ∂θ
where vector θ j represents the weights vector computed at j th discrete time instant, λ is positive and denotes the learning rate. L is the loss function. As we are always trying to minimize the loss function, we suppose that there exists an optimal solution of parameters θ * j .

C. Performance Metrics

There exists many metrics to evaluate the performance of a CNN model [START_REF] Li | Performance analysis of Gpu-based convolutional neural networks[END_REF], we used two of the most classical: classification accuracy and loss value.

For evaluating, machine learning researchers typically prepare a testing dataset which will not be used during the training process. At the end of each training phase (called from now on epoch), the testing dataset is used to evaluate the model by measuring the classification accuracy and the loss value. Accuracy is defined as: Accuracy =

Number of correct prediction

Total number of prediction [START_REF] Tien Nguyen | Applications of Online Deep Learning for Crisis Response Using Social Media Information[END_REF] The loss L is defined as the difference between the predicted value by the model and the true value. The most common definition of L used for classification problems is crossentropy [START_REF] Rubinstein | The cross-entropy method for combinatorial and continuous optimization[END_REF]:

L = - 1 V V p=1 C q=1
y p,q log(ŷ p,q ) + (1 -y p,q ) log(1 -ŷp,q )

(2

)
where V is the size of testing dataset and C is the total number of classes and also the length of the prediction vector which is a probability vector. ŷp,q denotes the q th bit value of prediction vector for data sample p while y p,q is the ground truth, indicating if data p belongs to class q (y p,q = 1) or not (y p,q = 0).

III. EVENT-BASED CONTROL LAWS

In [START_REF] Zhao | Feedback control for online training of neural networks[END_REF], an E/PD control of the learning rate is proposed consisting of an increasing phase followed by a PD phase. However, if an increase of the performance can be achieved on both the loss and the accuracy, the learning rate is progressively decreased by the E/PD control in the PD phase, even though a larger value of learning rate would be more efficient in term of performance. Since event-based PID have shown to be more efficient in terms of convergence [START_REF] Durand | Further results on event-based PID controller[END_REF], we propose here to implement an event-based E/PD controller to control the learning rate. [START_REF] Zhao | Feedback control for online training of neural networks[END_REF] also shows that significant improvements in terms of accuracy and loss only occurred at the first epochs of training each data batch, so after this stage there is no limited interest into continuing the learning on further epochs. Therefore, we propose a second event-based control to adapt the data batch loading process. A recall of the E/PD Control algorithm from [START_REF] Zhao | Feedback control for online training of neural networks[END_REF] is schematicly presented in Fig. 2. We suggest to look at a CNN training as a dynamical system with the learning rate as controlled input and the loss as measurable output. Initial weights of the CNN are chosen randomly and the initial learning rate λ(0) is fixed. E/PD learning rate strategy is defined as:

A. Event-Based Learning Rate

λ(k + 1) = 2λ(k) (3)
as long as L(k) < L(k -1) (E phase) and

λ(k + 1) = K P L(k) L(0) -K D L(k) -L(k -1) L(0) (4)
from the first instant k = k * when L(k * ) > L(k * -1) to the end of learning process for the data batch (i.e. the PD phase).

For the sake of simplicity the loss values are normalized with respect to the initial epoch loss value L(0). K P and K D are the proportional and derivative gain detailed in [START_REF] Zhao | Feedback control for online training of neural networks[END_REF]. On top of the PD phase we consider the following event base mechanism where instead of letting the PD-Control compute the rate each time (which might be lowering the learning rate), we propose to update the learning rate only if the loss value increases during the PD-Control phase.

Let us define the event function e 1 : R + → {0, 1} by:

e 1 k = 1 if L(k) -L(k -1) > 0 0 otherwise (5)
The proposed PD event-triggered control output λ(k + 1) at time k + 1 is then:

λ(k+1)=      K P L(k) L(0) -K D L(k)-L(k-1) L(0) if e1 k = 1 λ(k) otherwise ( 6
)
where λ(k + 1) is the calculated learning rate for epoch k + 1, L(k) is the corresponding loss for epoch k.

Note that the stability of CNN is ensured by E/PD, whose stability analysis is provided in [START_REF] Zhao | Feedback control for online training of neural networks[END_REF]. Proposed event-based control does not introduce any instability because if e 1 = 0, which means the loss is decreasing, model is converging, and if e 1 = 1, the learning rate strategy returns to E/PD.

B. Event-Based Learning Epochs

1) Controller Design: As observed in [START_REF] Zhao | Feedback control for online training of neural networks[END_REF], significant improvement in the learning only occurs at the beginning when loading a new batch, the accuracy and loss value evolve slowly afterwards. This motivates the use of an event-based strategy on the loss value record.

Consider a maximum of N training epochs within each batch. Let X k vector contains the latest m epochs numbers and Y k vector contains the m latest corresponding normalized loss values:

X k = k -m • • • k -2 k -1 k Y k = L(k-m) L(0) • • • L(k-2) L(0) L(k-1) L(0) L(k) L(0)
where k ∈ [1, N -1]. One can use least squares estimation to fit a regression line with X k and Y k :

Y k = α k X k + β k (7)
The purpose of this is that if the training process goes well the loss value should always decrease, therefore α k should always be negative. Even with the presence of loss variations during the training, as long as the decreasing trend doesn't change, α k should still be negative. Nevertheless, in the moment the loss trend becomes flat or even is increasing, α k will become 0 or positive. We define the event mechanism by the event function e 2 : R + → {0, 1} by:

e 2 k =
call new batch if α k >α thld or k=N remain on same batch if α k ≤α thld and k<N [START_REF] Wilson | The marginal value of adaptive gradient methods in machine learning[END_REF] which enables to switch to new data batch when the learning speed is too low, i.e. the training is not efficient anymore.

The threshold α thld can be adjusted in order to control the efficiency of learning. This threshold should never be positive as an increasing curve of the loss value is not desirable. With enough computing resources and no time constraints, the threshold can be set close to 0, and the training will last even though it makes very small improvement. Nevertheless, for online learning the time interval between two data batches can be short compared to the training time and we could encounter the scenario when before we finish the current training epochs the next data batch is already available. In this case, cutting off some useless training can be very useful. Therefore α thld should also be chosen depending on the frequency of batch arrival. The choice of m is based on the constraints imposed by the CNN (or the application using CNN). A large value of m would imply a long time of inactivity as the controller would react only after m epochs (consecutive tests). A small value of m would imply that the algorithm is very sensitive to each epoch thus if m = 0 the event based algorithm becomes a time based one.

2) Online Learning Scenario: Recall the online learning scenario defined in Sec. II-A and Fig. 1, the difference for Event-Based Learning Epochs is that the training epochs for each batch could be varied but no larger than N , but the total training epochs are the same for both scenario for all the experiments of the same dataset. So here we could cyclically learn the data batches until it reaches the total epochs limit. The online learning arrangement for Event-Based Learning Epochs is illustrated in Fig. 3.

IV. EXPERIMENTAL EVALUATION A. Experimental Setup

The experiments are implemented on two state of the art machine learning datasets: 1) CIFAR-10 (a natural image data set with 10 categories) and 2) CIFAR-100 (a natural image data set with 100 categories) [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] with 3 different initial learning rate. The characteristics of the two data-sets are given in Table I. As the CIFAR-100 dataset has more classes, we use a deeper CNN: ResNet [START_REF] He | Deep residual learning for image recognition[END_REF] than the one used for CIFAR-10 VGG [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]. Due to the computational resource limitation, for ResNet with CIFAR-100, we train 30 epochs per data batch instead of 60 for CIFAR-10.

All the experiments are implemented with Keras [START_REF] Chollet | Deep Learning with Python[END_REF] and are carried out on Google Cloud Compute-Engine using 8 virtual CPU with 30 GB memory and one P100 GPU. Each experiment is repeated 5 times.

The parameters α thld and m are selected through a process of cross validation on a subset of CIFAR-10. As a small value for m leads to high sensitivity and a large m slows down

B. Evaluation Metrics

The final loss and final validation accuracy (hereinafter referred to as FVA) reveal the performance of the final model. Nevertheless, stability metrics are also important: if accuracy curve experiences a big variance near the end of training process, even we could have a good final result, we could not assure that we always get this result. Thus, in our evaluation, we include standard deviation of the accuracy of the last 10% training epochs [START_REF] Minaee | 20 popular machine learning metrics. part 1: Classification & regression evaluation metrics[END_REF] (hereinafter referred to as FASD (Final Accuracy Standard Deviation)). Convergence speed of accuracy is another metric to evaluate the performance, as we will focus on online learning scenario, the interval between two batch data can be short. With a limited time, a faster accuracy convergence could lead to a better model performance comparing to other algorithms. Therefore, we will report the first epoch when the experiment reaches the 95% of best final accuracy among all the experiments.

C. Evaluation of Event-Based E/PD

Event-Based E/PD (hereinafter referred to as EB E/PD) refers to the E/PD control combined with Event-Based Learning Rate control (Sec. III-A). We implement the online training experiments with E/PD and EB E/PD on CIFAR-10. From Fig. 5 we can first see the comparison between EB E/PD and original E/PD (only yellow and dotted blue line for now). For the first 60 epochs, we can see that EB E/PD is more stable than E/PD, then their curves are quite overlapped. The averaged comparison results are showed in Table . II. EB E/PD performs better than E/PD in almost all metrics for all initial learning rate group. Even though EB E/PD has a higher FASD under 0.01 and 0.05 initial learning rate, but the minimum value of FVA(±FASD) range of EB E/PD is higher than the maximum value of the range of E/PD.

For the sake of visibility, we zoom into the 60th to 90th training epochs from our two experiment runs and show the evolution of the loss value and learning rate in Fig. 4. According to the learning rate curve, we know that E phase ends at 62th epoch for E/PD-Control curve, and at 64th epoch for EB E/PD. E/PD-Control curve clearly shows the problem we mentioned above, we can observe that from 62th epoch, the loss of E/PD is continuously decreasing until 70th epoch, and its learning rate is also decreasing during this period. If the learning rate could stay constant during these 9 epochs, its loss would decrease sharply and that would improve the convergence speed. In contrast, EB E/PD keeps the learning rate when the loss continuously decreases which helps to accelerate the convergence. We can also notice that with the drop of the loss, each time when we update the learning rate for EB E/PD, its trend is also decreasing which will guarantee the stability of EB E/PD near the optimum. -B). To ensure the need of the Event-Based Learning Rate control, we implemented E/PD with only Event-Based Learning Epochs control; results showed that Double Event-Based E/PD always has a better performance in Final loss and FVA. Due to the page limitation, we exclude these results from the main manuscript, however they are available online as appendices.

D-EB E/PD-Control has been tested on CIFAR-10 and CIFAR-100 and compared with 4 best state-of-the-art adaptive optimization algorithms: Adam, Nadam, AMSGrad and AdaBound. For these 4 learning rate strategies, except varying initial learning rate, all the other parameters remain as default as they mentioned in their paper or coded in Keras. As we adopt Event-Based Learning Epochs control into D-EB E/PD, the training epochs for each data batch is not fixed, we may also iterate each data batch several times. Therefore, we will not only report the results at the end of whole training process, but also the results after first round training (i.e. the training process iterates, for the first time, all the data batches, refer to Fig. 3).

Experimental results on CIFAR-10 are showed in Fig. 5, all the curves are generated with the same initial learning More detail of results on CIFAR-10 is reported in Table . III. D-EB E/PD reaches a higher final accuracy and lower final loss no matter λ(0). Even though D-EB E/PD has a higher FASD than AdaBound with λ(0) = 0.01 and λ(0) = 0.05, the FVA(±FASD) range of D-EB E/PD is always higher than the range of AdaBound. Additionally it only takes about 32 to 38 epochs to reach 95% best accuracy in any group. All the indicators are very stable across different groups for D-EB E/PD. One can also note that for all the 4 state-of-theart algorithms, they all perform very bad with λ(0) = 0.05, they cannot even reach the 95% best accuracy. We also implemented the same experiments with λ(0) = 0.25. Except our algorithm, no other one reaches a reasonable accuracy value, which can be explained by the fact that during the PD phase of E/PD control our learning rate can decrease to a low level while the counterparts can not. Those results are available as appendices.

CIFAR-100 results are reported in Table . IV. According to the FVA, we know that all the algorithms did not totally converge in the end of training process, but that does not influence our conclusion of analysis. D-EB E/PD outperforms other algorithms in almost all the metrics, when its FASD is higher than others in certain groups, its FVA(±FASD) range is always higher than others. As the algorithms are not totally converged, the trend of accuracy curve is still increasing, therefore, the higher the initial learning rate, the faster the 1st epoch to reach 95% best accuracy.

Table . V shows the results of D-EB E/PD in the end of first round learning. All the final loss after first round learning in this table is lower than all the state-of-the-art algorithms in their end of whole training process comparing to their own group. Except CIFAR-100 for λ(0) = 0.002, all the FVA after first round learning in this table exceed the 95% best accuracy in Table . III and Table . IV, respectively. As the learning process on CIFAR-100 is not totally converged, we can notice that the ending epoch of their first round is near the end of whole training process, our event-based control did not cut off many epochs. But for CIFAR-10, event-based control helps to massively cut off around 62% to 67% training epochs meanwhile guarantee a very good result.

E. Trade-offs and limitations

The addition of event-based mechanisms improves the performance in terms of final accuracy and loss, however at the cost of two sacrifices: (i) Event-Based Learning Epochs accelerate the speed of learning each data batch. However, if we are not allowed to keep in cache any data batch locally, i.e. only allowed to learn each data batch once, the performance of Double Event-Based E/PD after first round is slightly worse than the performance after all the training epochs. (ii) Double Event-Based E/PD will cyclically learn all data batches, and it will need to load and unload data batch more times than classical online learning setting. Loading (unloading) data into (from) memory needs time. These are extra costs for Double Event-Based E/PD, however negligible compared to the computing intensity of CNNs.

Regarding the limitation of the presented D-EB E/PD, we identified one potential case for which our algorithm will fail: if the training data contains mislabeled data. These data will lead the model to converge to a wrong optimum, and as the algorithm minimizes faster the loss function, it will be faster over-fitting to the noisy data than other algorithms. However, this fail is caused by poor data selection, and is not specific to our algorithm. Due to the limitation of computing resource or short interval time between two data batches, convergence speed of the loss and accuracy becomes especially important for online learning. E/PD control is a powerful learning rate algorithm when training neural network on an online learning scenario.

Based on E/PD, this paper proposes two algorithms: (i) Event-Based Learning Rate algorithm and (ii) Event-Based Learning Epochs algorithm.

The new algorithm firstly introduces an Event-Based control on PD phase of E/PD, when the loss continuously decreases, we prevent the learning rate to decrease during this period. Second Event-Based control is implemented to inspect the record of the loss value. If the loss record has the tendency to increase, showing little learning efficiency, we will drop the rest learning epochs for current data batch.

Results show that Double-Event-Based E/PD can massively cut off training epochs, and even results in a lower loss value. For instance with CIFAR-10 dataset, it could save up to 67% training epochs.

As the Event-Based Learning Epochs control is independent from learning rate algorithm and dataset, this work could be further extended by implementing this control with language, image and numeric datasets on time-based decay SGD, Adam, Nadam, AMSGrad and AdaBound learning rate algorithms, to prove that by simply adding this event-based control, all the learning rate algorithms on any dataset can improve their performance on online learning scenario.

Fig. 1 :

 1 Fig. 1: Classical Online Learning Scenario.

Fig. 2 :

 2 Fig. 2: E/PD Control Structure.A recall of the E/PD Control algorithm from[START_REF] Zhao | Feedback control for online training of neural networks[END_REF] is schematicly presented in Fig.2. We suggest to look at a CNN training as a dynamical system with the learning rate as controlled input and the loss as measurable output. Initial weights of the CNN are chosen randomly and the initial learning rate λ(0) is fixed. E/PD learning rate strategy is defined as:λ(k + 1) = 2λ(k)(3)

Fig. 3 :

 3 Fig. 3: Event-Based Learning Epochs Online Learning Scenario.IV. EXPERIMENTAL EVALUATION A. Experimental SetupThe experiments are implemented on two state of the art machine learning datasets: 1) CIFAR-10 (a natural image data set with 10 categories) and 2) CIFAR-100 (a natural image data set with 100 categories)[START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] with 3 different initial learning rate. The characteristics of the two data-sets are given in TableI. As the CIFAR-100 dataset has more classes, we use a deeper CNN: ResNet[START_REF] He | Deep residual learning for image recognition[END_REF] than the one used for CIFAR-10 VGG[START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]. Due to the computational resource limitation, for ResNet with CIFAR-100, we train 30 epochs per data batch instead of 60 for CIFAR-10.All the experiments are implemented with Keras[START_REF] Chollet | Deep Learning with Python[END_REF] and are carried out on Google Cloud Compute-Engine using 8 virtual CPU with 30 GB memory and one P100 GPU. Each experiment is repeated 5 times.The parameters α thld and m are selected through a process of cross validation on a subset of CIFAR-10. As a small value for m leads to high sensitivity and a large m slows down

Fig. 4 :

 4 Fig. 4: Performances of E/PD and EB E/PD on CIFAR-10 D. Evaluation of Double-Event-Based E/PD Double-Event-Based E/PD-Control (hereinafter referred to as D-EB E/PD) refers to the E/PD control combined with Event-Based Learning Rate control (Sec. III-A) and Event-Based Learning Epochs control (Sec. III-B). To ensure the need of the Event-Based Learning Rate control, we implemented E/PD with only Event-Based Learning Epochs control; results showed that Double Event-Based E/PD always has a better performance in Final loss and FVA. Due to the page limitation, we exclude these results from the main manuscript, however they are available online as appendices.D-EB E/PD-Control has been tested on CIFAR-10 and CIFAR-100 and compared with 4 best state-of-the-art adaptive optimization algorithms: Adam, Nadam, AMSGrad and AdaBound. For these 4 learning rate strategies, except varying initial learning rate, all the other parameters remain as default as they mentioned in their paper or coded in Keras. As we adopt Event-Based Learning Epochs control into D-EB E/PD, the training epochs for each data batch is not fixed, we may also iterate each data batch several times. Therefore, we will not only report the results at the end of whole training process, but also the results after first round training (i.e. the training process iterates, for the first time, all the data batches, refer to Fig.3).Experimental results on CIFAR-10 are showed in Fig.5, all the curves are generated with the same initial learning

Fig. 5 :

 5 Fig. 5: Performance comparison on CIFAR-10 with λ(0) = 0.01 initial learning rate. Compact view of the results in Table III. rate 0.01. Between 25th and 60th epoch, D-EB E/PD largely outperforms all the counterparts. The vertical line with arrow at 104th epoch indicates that our D-EB E/PD algorithm has finished its first round learning of the whole 5 batches after this epoch. There are two reasons that we can achieve this performance: (i) EB E/PD converges very fast, (ii) during these epochs, our D-EB E/PD algorithm have trained with later batches data, while other 4 algorithms, they are still working on the first batch data. Diversity of training data helps to reach better performance.More detail of results on CIFAR-10 is reported in Table.III. D-EB E/PD reaches a higher final accuracy and lower final loss no matter λ(0). Even though D-EB E/PD has a higher FASD than AdaBound with λ(0) = 0.01 and λ(0) = 0.05, the FVA(±FASD) range of D-EB E/PD is always higher than the range of AdaBound. Additionally it only takes about 32 to 38 epochs to reach 95% best accuracy in any group. All the indicators are very stable across different groups for D-EB E/PD. One can also note that for all the 4 state-of-theart algorithms, they all perform very bad with λ(0) = 0.05, they cannot even reach the 95% best accuracy. We also implemented the same experiments with λ(0) = 0.25. Except our algorithm, no other one reaches a reasonable accuracy value, which can be explained by the fact that during the PD phase of E/PD control our learning rate can decrease to a low level while the counterparts can not. Those results are available as appendices.CIFAR-100 results are reported in Table.IV. According to the FVA, we know that all the algorithms did not totally converge in the end of training process, but that does not influence our conclusion of analysis. D-EB E/PD outperforms other algorithms in almost all the metrics, when its FASD is higher than others in certain groups, its FVA(±FASD) range is always higher than others. As the algorithms are not totally converged, the trend of accuracy curve is still increasing, therefore, the higher the initial learning rate, the faster the 1st epoch to reach 95% best accuracy.Table.V shows the results of D-EB E/PD in the end of first round learning. All the final loss after first round learning in this table is lower than all the state-of-the-art algorithms in their end of whole training process comparing to their own group. Except CIFAR-100 for λ(0) = 0.002, all the FVA after first round learning in this table exceed the 95% best accuracy in Table.III and Table.IV, respectively. As the learning process on CIFAR-100 is not totally converged, we can notice that the ending epoch of their first round is near the end of whole training process, our event-based control did not cut off many epochs. But for CIFAR-10, event-based control helps to massively cut off around 62% to 67% training epochs

TABLE I :

 I Experiments configuration

	Use case	CIFAR-10	CIFAR-100
	#data instances to train T	50,000	50,000
	#data instances to test V	10,000	10,000
	#classes C	10	100
	data batch size S	10000	10000
	total batches B	5	5
	#trainng epochs per batch N	60	30
	the detection of the situation, we predefined a reasonable list
	of choice m ∈ [4; 5; 6; 7; 8]. Due to similar consideration
	of sensibility, we also predefined a list for the learning
	rate threshold α thld ∈ [-0.1; -0.01; -0.001; -0.0001]. Each
	possible pair from these two lists is tested, a good compromise
	between reactivity and noise sensitivity was found for m = 4
	and α thld = -0.001.

TABLE II :

 II Experiments with varying initial learning rate λ(0) on CIFAR-10. Mean value over 5 runs are reported.

	Algorithm	λ(0)	Final loss	FVA 1 (± FASD 2 ) (%)	1st epoch to 81.66% 3
	E/PD	0.002	0.58	83.17(±0.08)	124/300
	EB E/PD	0.002	0.56	83.81(±0.03)	93/300
	E/PD	0.01	0.55	84.35(±0.07)	88/300
	EB E/PD	0.01	0.54	84.91(±0.10)	75/300
	E/PD	0.05	0.56	85.06(±0.12)	73/300
	EB E/PD	0.05	0.50	85.96(±0.26)	63/300
	1. FVA: Final Validation Accuracy
	2. FASD: Final Accuracy Standard Deviation
	3. 81.66%: 85.96%(best final accuracy among all the experiments)×95%

TABLE III :

 III Double-Event-Based E/PD algorithm experiments with varying initial learning rate λ(0) on CIFAR-10. Mean value over 5 runs are reported.

	Algorithm	λ(0)	Final loss	FVA ±FASD	1st epoch to 80.94% 1
	D-EB E/PD	0.002	0.58	84.50(±0.59)	38/300
	Adam	0.002	0.73	84.14(±1.34)	64/300
	Nadam	0.002	0.71	83.29(±1.11)	66/300
	AMSGrad	0.002	0.67	84.21(±1.65)	65/300
	AdaBound	0.002	0.81	84.31(±0.96)	75/300
	D-EB E/PD	0.01	0.61	84.83(±1.29)	37/300
	Adam	0.01	0.79	83.98(±1.58)	64/300
	Nadam	0.01	0.75	84.15(±1.29)	65/300
	AMSGrad	0.01	0.65	84.21(±1.50)	72/300
	AdaBound	0.01	0.84	79.22(±1.21)	-
	D-EB E/PD	0.05	0.60	85.20(±3.14)	32/300
	Adam	0.05	5.98	48.93(±14.06)	-
	Nadam	0.05	7.74	42.27(±13.95)	-
	AMSGrad	0.05	2.69	59.74(±12.43)	-
	AdaBound	0.05	1.03	71.49(±1.65)	-
	1. 80.94%: 85.20%(best final accuracy among all the experiments)×95%

TABLE IV :

 IV Double-Event-Based E/PD algorithm experiments with varying initial learning rate λ(0) on CIFAR-100. Mean value over 5 runs are reported

	Algorithm	λ(0)	Final loss	FVA (±FASD) (%)	1st epoch to 46.56% 1
	D-EB E/PD	0.002	2.59	45.69(±1.94)	-
	Adam	0.002	3.40	31.29(±3.23)	-
	Nadam	0.002	3.18	35.66(±3.35)	-
	AMSGrad	0.002	3.13	35.38(±4.02)	-
	AdaBound	0.002	3.29	39.87(±4.42)	-
	D-EB E/PD	0.01	2.41	48.14(±3.34)	111/150
	Adam	0.01	4.94	8.11(±2.04)	-
	Nadam	0.01	4.55	9.70(±2.32)	-
	AMSGrad	0.01	4.79	8.16(±0.50)	-
	AdaBound	0.01	3.51	30.98(±3.08)	-
	D-EB E/PD	0.05	2.38	49.01(±10.52)	100/150
	Adam	0.05	4.72	2.64(±0.58)	-
	Nadam	0.05	4.74	1.88(±0.79)	-
	AMSGrad	0.05	4.68	1.98(±0.56)	-
	AdaBound	0.05	3.69	19.03(±2.42)	-
	1. 46.56%: 49.01%(best final accuracy among all the experiments)×95%

TABLE V :

 V Double Event-Based E/PD experiments on CIFAR-10 and CIFAR-100 in the End of First Round. Mean value over 5 runs are reported. EE of FR: End Epoch of First Round 2. FL after FR: Final loss after First Round 3. FVA after FR: Final Validation Accuracy after First Round V. CONCLUSION AND FUTURE WORK

	Dataset	λ(0)	EE of FR 1	FL after FR 2	FVA after FR 3 (%)
	CIFAR10	0.002	99/300	0.60	82.47
	CIFAR10	0.01	104/300	0.62	82.36
	CIFAR10	0.05	113/300	0.62	82.75
	CIFAR100	0.002	148/150	2.61	44.98
	CIFAR100	0.01	148/150	2.44	48.04
	CIFAR100	0.05	146/150	2.41	48.95
	1.


Dimitri Zhukov

Jean-Baptiste Alayrac

Ivan Laptev

Josef Sivic

Learning Actionness via Long-range Temporal Order Verification

Keywords: temporal order, action localization, video recognition

Current methods for action recognition typically rely on supervision provided by manual labeling. Such methods, however, do not scale well given the high burden of manual video annotation and a very large number of possible actions. The annotation is particularly difficult for temporal action localization where large parts of the video present no action, or background. To address these challenges, we here propose a self-supervised and generic method to isolate actions from their background. We build on the observation that actions often follow a particular temporal order and, hence, can be predicted by other actions in the same video. As consecutive actions might be separated by minutes, differently to prior work on the arrow of time, we here exploit long-range temporal relations in 10-20 minutes long videos. To this end, we propose a new model that learns actionness via a self-supervised proxy task of order verification. The model assigns high actionness scores to clips which order is easy to predict from other clips in the video. To obtain a powerful and action-agnostic model, we train it on the large-scale unlabeled HowTo100M dataset with highly diverse actions from instructional videos. We validate our method on the task of action localization and demonstrate consistent improvements when combined with other recent weakly-supervised methods.

Introduction

Learning from web videos is becoming increasingly popular in computer vision as such videos are available in large quantities, and cover diverse activities and scenes. In particular, instructional videos have been recently explored as a rich source for many tasks and goal-driven sequences of actions [START_REF] Alayrac | Unsupervised learning from narrated instruction videos[END_REF][START_REF] Huang | Finding "it": Weakly-supervised reference-aware visual grounding in instructional video[END_REF][START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF][START_REF] Tang | Coin: A large-scale dataset for comprehensive instructional video analysis[END_REF]40,41]. While the quantity and diversity of video data appears crucial for training current recognition models [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF][START_REF] Miech | End-toend learning of visual representations from uncurated instructional videos[END_REF][START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF], the manual annotation of actions in large-scale video data requires large efforts [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] and may not scale well to the large number of possible actions. This is particularly true for the task of temporal action localization where sparse actions should be isolated in video streams from the large portion of "background" with no actions. For example, action frames in Fig. 1. We show pairs of action frames and background frames from the same video. Can you predict the order of frames within each pair? While the order is relatively easy to guess for actions, the same task is more difficult for the background. We use this observation and exploit the predictability of temporal order as a measure of actionness the CrossTask dataset [41] with typical instructional videos represent only 25.9% of the total video length.

In our work we address the above challenges and aim to develop a selfsupervised approach for separating a large and diverse set of actions from their background. We observe that actions typically do not happen in isolation and are often surrounded by other related actions. Moreover, action sequences often demonstrate a consistent order (taking off a car wheel should be preceded by lifting the car), hence, many actions can be identified by the predictability of their order with respect to other actions in the same video. On the contrary, the order of background frames is often hard to predict, hence, the low predictability for the order could be used to signify the background. We illustrate this idea with a quiz in Figure 1.

Temporal order has been explored as a supervisory signal by a number of recent works [START_REF] Fernando | Self-supervised video representation learning with odd-one-out networks[END_REF][START_REF] Misra | Shuffle and learn: Unsupervised learning using temporal order verification[END_REF][START_REF] Wei | Learning and using the arrow of time[END_REF]39]. The goal of such methods, however, is to learn video representations by verifying the order for a short range of consequtive frames. We here address a different task and learn actionness [START_REF] Chen | Actionness ranking with lattice conditional ordinal random fields[END_REF] by exploiting longrange relations between video clips on the scale of minutes. To this end, we propose a new model and a method to learn actionness scores via a self-supervised proxy task of order verification. The model assigns high actionness scores to clips which order is easy to predict from other clips in the video. Our method is selfsupervised and requires no manual annotation. Given this property, we use a very large HowTo100M dataset [START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF] with diverse and unlabeled instructional videos to learn an action-agnostic model for actionness. We show interesting insights of our method and demonstrate improved performance of action localization when combining our model with recent weakly-supervised approaches. Contributions. This work makes the following contributions: [START_REF] Agrawal | Learning to see by moving[END_REF] We develop a new model for action-agnostic action/background classification and propose to learn it via a self-supervised proxy task of long-range order verification. (2) We demonstrate a successful application of our method to the tasks of frame-wise action/background classification and action proposal generation evaluated on datasets with instructional videos COIN [START_REF] Tang | Coin: A large-scale dataset for comprehensive instructional video analysis[END_REF] and CrossTask [41]; (3) We further demonstrate the benefit of our model for action localization by combining it with recent weakly-supervised methods of step localization on the CrossTask dataset; and (4) We provide ablation studies that give insights about our approach.

2 Related work

Self-supervised learning

Our work exploits the natural source of supervision in videos: the temporal order between frames. The proposed method is, hence, related to a large body of recent work on self-supervised learning, where the supervisory signal is obtained directly from the data and does not require manual annotation. The variety of recently proposed self-supervised tasks in the image domain include prediction of image rotation [START_REF] Gidaris | Unsupervised representation learning by predicting image rotations[END_REF], spotting artifacts [START_REF] Jenni | Self-supervised feature learning by learning to spot artifacts[END_REF], image colorization [START_REF] Zhang | Colorful image colorization[END_REF][START_REF] Larsson | Colorization as a proxy task for visual understanding[END_REF], cross-channel prediction [37], inpainting [START_REF] Pathak | Context encoders: Feature learning by inpainting[END_REF] and prediction relative position of patches [START_REF] Doersch | Unsupervised visual representation learning by context prediction[END_REF][START_REF] Noroozi | Unsupervised learning of visual representations by solving jigsaw puzzles[END_REF]. In the video domain, motion has been used as a cue for learning video representations in [START_REF] Agrawal | Learning to see by moving[END_REF][START_REF] Pathak | Learning features by watching objects move[END_REF][START_REF] Wang | Unsupervised learning of visual representations using videos[END_REF][START_REF] Dwibedi | Temporal cycleconsistency learning[END_REF]. More related to our work, previous methods [START_REF] Fernando | Self-supervised video representation learning with odd-one-out networks[END_REF][START_REF] Lee | Unsupervised representation learning by sorting sequences[END_REF][START_REF] Misra | Shuffle and learn: Unsupervised learning using temporal order verification[END_REF][START_REF] Wei | Learning and using the arrow of time[END_REF][START_REF] Xu | Self-supervised spatiotemporal learning via video clip order prediction[END_REF] explore the temporal order, either by predicting the exact order of consecutive frames [START_REF] Lee | Unsupervised representation learning by sorting sequences[END_REF][START_REF] Xu | Self-supervised spatiotemporal learning via video clip order prediction[END_REF] or verifying their partial order [START_REF] Fernando | Self-supervised video representation learning with odd-one-out networks[END_REF][START_REF] Misra | Shuffle and learn: Unsupervised learning using temporal order verification[END_REF][START_REF] Wei | Learning and using the arrow of time[END_REF]. Our work builds on these ideas but brings two important innovations. First, in contrast to previous work that exploits temporal order to learn local video representations, we address a different task of action/background classification. As actions are often separated by minutes, our task requires reasoning about longrange temporal order, as opposed to short-range frame permutations explored by previous methods. Our second innovation is, hence, a new method that exploits long-range order verification for video clips and enables to model relations between actions in 10-20 minutes long videos.

Learning from instructional videos

Instructional videos have recently been in the focus of numerous works in the context of action localization [START_REF] Alayrac | Unsupervised learning from narrated instruction videos[END_REF][START_REF] Sener | Unsupervised learning and segmentation of complex activities from video[END_REF]41], joint learning of object states and actions [START_REF] Alayrac | Joint discovery of object states and manipulation actions[END_REF], joint modeling of video and language [START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF][START_REF] Sun | Videobert: A joint model for video and language representation learning[END_REF] and visual reference resolution [START_REF] Huang | Unsupervised visual-linguistic reference resolution in instructional videos[END_REF][START_REF] Huang | Finding "it": Weakly-supervised reference-aware visual grounding in instructional video[END_REF]. Some of this work exploits specific properties of instructional videos, such as the approximate temporal alignment between narrations and the visual content [START_REF] Alayrac | Unsupervised learning from narrated instruction videos[END_REF][START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF][START_REF] Sun | Videobert: A joint model for video and language representation learning[END_REF]41], and the order consistency [START_REF] Alayrac | Unsupervised learning from narrated instruction videos[END_REF][START_REF] Sener | Unsupervised learning and segmentation of complex activities from video[END_REF]41]. Similarly, we rely on the partial order between actions. Our novelty is to use the order verification as a proxy task to discover most relevant parts of the video. To demonstrate the value of our approach, we combine it with the previous methods [START_REF] Miech | End-toend learning of visual representations from uncurated instructional videos[END_REF][START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF]41] for the task of weakly-supervised step localization in instructional videos and demonstrate consistent improvements.

Action proposals

We apply our method to generate action proposals. Action proposals is an essential part of many methods for action detection, explored by a number of recent papers [START_REF] Escorcia | Daps: Deep action proposals for action understanding[END_REF][START_REF] Gao | Ctap: Complementary temporal action proposal generation[END_REF][START_REF] Ji | Learning temporal action proposals with fewer labels[END_REF][START_REF] Lin | Bmn: Boundary-matching network for temporal action proposal generation[END_REF][START_REF] Lin | Bsn: Boundary sensitive network for temporal action proposal generation[END_REF][START_REF] Liu | Multi-granularity generator for temporal action proposal[END_REF]38]. A popular approach to generate action proposals is to estimate an actionness score for each temporal unit and then apply some sort of temporal grouping and non-maxima suppression. The notion of actionness was first introduced in [START_REF] Chen | Actionness ranking with lattice conditional ordinal random fields[END_REF] as a confidence measure of intentional bodily movement of biological agents. Most works [START_REF] Liu | Multi-granularity generator for temporal action proposal[END_REF][START_REF] Lin | Bmn: Boundary-matching network for temporal action proposal generation[END_REF][START_REF] Lin | Bsn: Boundary sensitive network for temporal action proposal generation[END_REF][START_REF] Gao | Ctap: Complementary temporal action proposal generation[END_REF]38] address actionness with supervised methods based on manual annotation of a known and limited set of action classes. This is done by training a binary classifier for estimating actionness score as first proposed in the context of spatial action detection [START_REF] Wang | Actionness estimation using hybrid fully convolutional networks[END_REF]. Contrary to this approach, we aim to learn an actionness score without manual supervision by relying on generic assumptions about action order. Our definition of actions is narrower than in [START_REF] Chen | Actionness ranking with lattice conditional ordinal random fields[END_REF]. In particular, we only consider goal-oriented actions, necessary to perform specific manipulation tasks. This definition excludes actions such as gesticulation and conversations.

Unsupervised learning of actionness score

Given a large corpus of instructional videos depicting complex tasks, our goal is to automatically discover which segments of the videos are the most relevant for the successful completion of the tasks. We refer to these relevant segments as actions. Example of a complex task would be "building a shelve" and a relevant action would be "drilling a hole". Formally, we learn an actionness scoring function S that takes as input a video clip x ∈ R T ×H×W ×3 containing T frames of height H and width W and outputs a score S(x) ∈ R that is high when x corresponds to a relevant action and is low otherwise, e.g. on background scenes that are not relevant for completing the task.

We propose to learn S in a self-supervised manner through the pretext task of long range temporal order verification, which consists in predicting whether or not a set of video clips spanning a long temporal interval are in the correct order. The intuition is that one needs to isolate the relevant segments of the video that allow to best identify the correct ordering of events to be able to solve that task. We use that observation to train our actionness model S.

This section formally describes our method for joint order verification and actionness prediction. Section 3.1 introduces the model used. Section 3.2 details the training procedure, that allows to train the actionness score S via order verification.

Models for actionness and order verification

We represent each video clip x by a d-dimensional feature vector h = f (x) ∈ R d obtained from a pre-trained video network f that we keep fixed throughout the work. In practice we use averaged pooled I3D representation [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] pretrained in [START_REF] Miech | End-toend learning of visual representations from uncurated instructional videos[END_REF], with d = 1024. For simplicity, we only refer to the feature vector h in the following (implicitly assuming h is associated with a video clip x). The actionness score S(x) is estimated by a linear function on h, i.e., S(x) = w h + b, where w ∈ R d and b ∈ R are learnt weights and biases, respectively. To predict the order of clips, we also introduce a model F that takes as input two clips x and x and outputs the confidence F (x, x ) ∈ R that x happens before x . We force F to be antisymmetric (i.e., F (x,

x ) = -F (x , x)), by defining F (x, x ) = a (h -h ),
where a ∈ R d and h = f (x ). Our choice of simple linear models is practicaly motivated by the fact that in our experiments we did not see improvements from using more complex models. Next, we describe the training strategy used to train S and F using order verification.

Training with ordering verification

Actionness through order verification. Our goal is to learn actionness score in an unsupervised manner. As explained earlier we believe that actions contain more information than background in terms of predicting what happens before or what may come next in instructional videos as they carry more information about the global temporal structure of the video than the background. In this section, we use that observation to automatically differentiate actions from background. In short, the idea is to train a network to predict if a set of clips are in the correct order, a task for which it's trivial to get free supervision as correct ordering is naturally present in the video. In order to do so, we allow the model to softly select which pairs of clips from the set are best to perform that prediction, i.e., those that are most informative in terms of their relative order in the video. Hence, by learning to predict order through weighted relative ordering of pairs of clips, we expect the model to pay more attention on important actions and therefore learn a good actionness score S. Details are given next. Order verification task. As illustrated in Figure 2, given a sequence X of M video clips X = (x i ) M i=1 randomly sampled from the same video, the task of order verification is to predict whether or not the clips in X are in the correct order, i.e., the same order as the original video. Ground truth generation. We create positives and negatives for the verification task by simply randomly sampling M clips from a video and either (i) create a positive sequence by sorting clips in the order of their appearence in the video (label y = 1) or (ii) reverse completely the original sequence (negative label y = 0). Order verification prediction. We seek to predict if the sequence X is in the correct order through our pairwise model F that can predict the relative ordering of a given pair of clips (x i , x j ). To make a more accurate prediction, it is better to aggregate scores over many pairs from the entire sequence X. For this reason, we predict the confidence G(X) that X = (x i ) M i=1 is in the correct order as a weighted average of all pair-wise predictions:

G(X) = i<j W ij F (x i , x j ).
(1)

Note that the sum indices i < j are to make sure that (i) we only compare pairs in the order given by the sequence and (ii) we don't compare a clip to itself. Finally the weights W ij are defined with a softmax over all pairs of clips:

W ij = exp(S(x i ) + S(x j )) i <j exp(S(x i ) + S(x j )) , (2)
where S(x i ) and S(x j ) are the actionness score of our model for clips x i and x j , respectively. Because of the softmax (2) we have i<j W ij = 1 and W ij ≥ 0.

Hence the weights W ij can be seen as a way to softly select the contribution of every individual pair (x i , x j ) since they control the contribution of the individual order pairwise prediction F (x i , x j ) in the global order score G(X) (see [START_REF] Agrawal | Learning to see by moving[END_REF]). This contribution to G(X) is proportional to the sum S(x i )+S(x j ) of actionness score of both clips x i and x j . This is to match our intuition that both clips should be depicting a relevant action to facilitate the order prediction. By learning G we will therefore indirectly learn S as described by the training objective below.

Training objective. Given a sequence X and associated label y indicating whether or not the sequence of clips is in the correct order, we use the binary cross-entropy loss L as follows

L(X, y) = -y log(σ(G(X))) -(1 -y) log(1 -σ(G(X))), (3)
where σ is the sigmoid function. This loss will enforce that when X is in the correct order (i.e., y = 1), then G(X) should be maximized. To do so, the actionness model S needs to be high on clips x i and x j from which it's easier to predict their correct ordering (meaning high value of F (x i , x j )) so that their contribution in G(X) will be maximal. Conversely, when X is in the incorrect order (i.e., y = 0), then G(X) should be minimized. Again, to do so the actionness model S needs to be high on clips x i and x j from which it's easier to predict their incorrect ordering (meaning low value of F (x i , x j )) so that their contribution in G(X) will be maximal. Following the standard procedure, we minimize the expected loss L on our training dataset.

Experiments

The experimental setup is described in Section 4.1. We then provide in Section 4.2 an ablation study of highlighting the most important components of our method. Finally, in Section 4.3, we show how we can use our learned actionness score for applications such as action proposals or weakly supervised action localization.

Experimental setup

Input processing. Given a clip x containing T frames, we extract h(x) using the I3D backbone from [START_REF] Miech | End-toend learning of visual representations from uncurated instructional videos[END_REF], pre-trained on HowTo100M for the task of joint embedding of videos and subtitles. We extract the features at Mixed 5c in a fully convolutional manner and perform a global average pooling to have a single feature vector h(x) of dimension 1024. Note that this network was trained without requiring manual annotations. To reduce computation cost during training, we pre-extract these features and directly work in feature space. In particular, this means that we do not finetune the I3D backbone for our task.

Training dataset. Due to the large variety of actions in instructional videos, the variety of their visual appearance as well as the order in which they are performed in videos, we require a large amount of data for our self-supervised task. For this reason, we train our model on HowTo100M [START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF], a large dataset containing more than 1.2 million videos depicting around 23, 000 different tasks and was collected without manual annotation.

Training details. We optimize the objective (3) using the Adam optimizer [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] on a single GPU with batch size 1024, initial learning rate of 10 -4 that we decay by a factor 0.9 at every epoch. We train for a total of 15 epochs. In addition, since HowTo100M is biased towards some specific domains (e.g. 40% of videos are cooking), we resample the data, using the task taxonomy of HowTo100M. Precisely, we consider all subcategories of depth 3, i.e., subcategories of the principal categories, such as Food and Cars, and sample equal number of videos from each subcategory. We also remove subcategories with less than 3000 videos. Evaluation datasets. We use two instructional video datasets, COIN [START_REF] Tang | Coin: A large-scale dataset for comprehensive instructional video analysis[END_REF] and CrossTask [41]. Both datasets contain untrimmed videos that have been temporally annotated with action labels corresponding to the different steps of the task. In the following, time intervals without any action labels are considered as background. We use the official COIN test subset of 2797 videos for evaluation. Since there is no official test subset of CrossTask, we randomly split it into a training (2062 videos) and test sets (688 videos). In addition, we made sure to discard all COIN and CrossTask videos from our training set. Evaluation tasks. We use three different tasks for evaluation, detailed next. Background vs. action classification. In this task, videos from the respective test sets are split into non overlapping 0.2s segments. For each segment we assign a binary label: positive (action) if the segment overlaps with an annotated action interval and negative (background) otherwise. The goal is to classify each segment as an action or a background. We use average precision (AP) as an evaluation metric for this task.

Action temporal proposal generation. The task is to generate a set of proposals, that overlap well with ground truth action intervals. To generate proposals from the outputs of the network S(x), we use the Temporal Actionness Grouping (TAG) method [38]. We set the Intersection over Union (IoU) threshold for nonmaximum suppression to 0.8. We follow the evaluation protocol of [START_REF] Lin | Bsn: Boundary sensitive network for temporal action proposal generation[END_REF] using the implementation provided in [START_REF] Lin | Bmn: Boundary-matching network for temporal action proposal generation[END_REF] to compute Average Recall (AR) at multiple IoU thresholds: [0.5 : 0.05 : 0.95]. Finally, we report AR as a function of the Average Number (AN) of proposals per video AR@AN as done in [START_REF] Lin | Bsn: Boundary sensitive network for temporal action proposal generation[END_REF]. Action step localization. Third task is step localization on CrossTask. Given an ordered list of actions for a video, the goal is to assign each action to exactly one frame. We use the same evaluation protocol as in [41] and report average recall.

Ablations studies

This section ablates the important components of our method. We report performance using background vs action classification task on COIN and CrossTask. Video trimming. When first training our method, we notice that the model could learn to be good at the self-supervised ordering task by putting high score on intro and outro segments of videos. This can be intuitively explained by the fact that the beginning and end of instructional videos are distinctive: they start with some typical introduction and often finish with credits. This effect is demonstrated on the left part of Figure 3: when trained on untrimmed videos, the actionness score S(x) is high for beginning and end of videos simply because the model can easily discriminate if a frame is from intro (beginning) or outro (end) and hence can safely select these frames to predict relative ordering of pairs. Top scoring frames illustrate that the model picks up on typical credit frames. This led to bad performance as these segments do not contain relevant actions. To alleviate this effect, we employ a simple but effective strategy: during training we trim off 30% of frames in the beginning and 30% of frames in the end of the video. Note we only do that at training and do not trim test videos to keep the evaluation protocol consistent. Figure 3 shows that the temporal distribution of scores that we obtain by this technique better matches the ground truth one, as expected. In particular it's interesting to note that our model is still able to assign frames to actions even for frames that are in the beginning or the end when relevant (i.e., this trimming did not handicaped the model for true actions that happen early or late in the video). Finally, the table in Figure 3 demonstrates the effectiveness of this approach on our two evaluation datasets. Long vs. short range order verification. The driving hypothesis of this work is that learning actionness score S is possible thanks to the long range order consistency between actions in instructional videos. We claim that this is not true for short-term ordering between frames as used in previous work [START_REF] Misra | Shuffle and learn: Unsupervised learning using temporal order verification[END_REF], as in that case order verification can be done via low level visual cues regardless of whether images depict actions or background. We verify that claim by training our model at different temporal scales. Formally, we set d to be the temporal window length in which we are going to sample M = 5 segments of length d/10. In other words, d corresponds to the maximum distance we can have between two clips from X, and is a good measure of the range at which we perform the order verification task. Figure 4 (left) shows the results for different values of d.

For small values of d, the model shows poor performance, compared to larger values. This demonstrates that our method works better on the scale of several minutes (long range), rather than 10-20 seconds (short range). Number of segments per video. In Figure 4 (right), we study the effect on performance when training our model with different number of segments M per video. Results are given for M ≥ 3 (M = 2 makes training of S impossible since there are no pairs to select from). We observe that overall the method is not too sensitive to M . However, only sampling 3 segments per video may often lead to a situation where all selected segments are background, hence selecting larger value for M leads to better results. Figure 4 also shows a decline in precision for M > 5 on both datasets. This can be explained by the fact that for large values of M there is a high probability of having at least one pair of segments, for which the temporal order is easy to guess. This may decrease the ability of our model to learn temporal order for other more subtle pairs. Based on that study, we use M = 5 in all of our other experiments.

Actionness score for practical applications

Action vs. Background classification. In Table 1, we compare against five methods: (i) chance baseline, (ii) chance baseline with trimming, (iii) hand detector, (iv) optical flow and (v) a supervised model. (i) simply assigns random uniform action scores to segments in the video. Following our observation from Section 4.2 about trimming, (ii) does the same as (i) but also assigns to background the segments that occur in the first and last 30% portion of the video.

(iii) assigns the actionness score to the maximum score of a hand detector [START_REF] Shan | Understanding human hands in contact at internet scale[END_REF] computed for each frame. This baseline is based on the assumption that the actions correlate with the appearance of hands. (iv) assumes that the actions correlate with motion and estimates an actionness score as an average magnitude of optical flow at each frame. Finally for the supervised topline (v), we train in a supervised manner a linear layer on top of our feature representation h(x) for the binary action vs. background classification task. As we also use a linear layer for S, (v) provides an upper bound of performance, that can possibly be achieved with our approach. Methods (ii-iv) provide simple, yet meaningful baselines in the absence of existing unsupervised methods for the considered task. The results are shown in Table 1. Baselines (ii-iv) show only a marginal improvement over Chance, which illustrates the difficulty of the task. (ii) provides the strongest baseline on both COIN and CrossTask, highlighting the importance of intro and outro segments for action vs. background classification. Our method shows an improvement over the baselines on both datasets.

Temporal Action Proposals. Following the evaluation protocol described in Section 4.1, we compare to 4 different methods: (i) chance baseline, (ii) chance baseline with trimming, (iii) hand detector, (iv) optical flow, (v) supervised and (vi) temporal prior. (i-v) are the same as for the Action vs. Background classification task. For (vi), we use a temporal prior to generate action segments: it consists in sampling proposal start and length from a prior distribution, obtained from ground truth action intervals. In details, we compute the empirical distribution of the normalized start time of actions as well as their duration. We then randomly sample segments from that distribution by first sampling a start time and then a duration. Note that this baseline has access to more annotation than our proposed approach, since we don't have access to any temporal annotation. Figure 5 shows the average recall for CrossTask and COIN, as a function of average number of proposals per video (AN). On both datasets we outpeform baselines (i-iv) for most values of AN. More interestingly, we also significantly outpeform the temporal prior (vi) approach despite using less annotation information. Finally it is worth noting that the gap between our method and the supervised (v) topline is not large (less than between our method and (vi)).

Step localization. In this experiment, we explore how our actionness model can improve weakly supervised action localization. This task is particularly relevant since presence of background is one of the main challenges for weakly supervised action localization methods. To do so, we augment various action localization methods from [41], [START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF] and [START_REF] Miech | End-toend learning of visual representations from uncurated instructional videos[END_REF] with our actionness score S(x) and evaluate on the CrossTask dataset following the protocol described in [41]. These methods work in a similar way, described next. First, step classifiers are applied to every frame of the video. Then, each step is assigned to exactly one short clip, using a dynamic programming to solve: where f k (x t ) is the output of the step classifier k for the t-th input clip x t , and t 1 , ..., t K are the clips ids assigned to steps 1, ..., K, respectively. [41], [START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF] and [START_REF] Miech | End-toend learning of visual representations from uncurated instructional videos[END_REF] differ only in the form of the classifier f k (x). We augment these methods with our actionness score by simply adding it to the objective during inference:

(t * 1 , ..., t * K ) = arg max t1<...<t K T t=1 K k=1 f k (x t ),
(t * 1 , ..., t * K ) = arg max t1<...<t K T t=1 (1 -α) K k=1 f k (x t ) + αS(x t ) , (4)
where S(x t ) is the actionness score of our model for clip x t and α is a combination parameter. Intuitively, the role of our score is to lower the confidence of background clips and increase the score on foreground action clips.

Results are provided in Table 2. α is selected independently for each method, which equals 0.1 for [START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF] and 0.8 for other methods. We use the same value of α for all test tasks. Combining the baseline method with our score improves the performance in every case. The gap in performance is particularly large for the method from Zhukov et al. [41]. This can be in part attributed to the fact that this method does not try to model the background for a given frame (indeed a simple constraint imposes that the score should sum to one across time for all actions without trying to explicitly lower score on detected background frames). Adding our score to the outputs of the model resolves this problem and leads to a large improvement (+4.6% recall). Other methods in Table 2 rely instead on a joint video and text embedding pretrained on the large scale HowTo100M dataset to score every segment of the video against the text embeddings of the action description. These text-video embeddings approach lead to much stronger base model. However, given a frame, there is no guarantee that the model will explicitly be looking for actions as scores can still be high if its visual content partially matches the description of an action. For example, if the action is season steak, the presence of a steak and the object salt in the frame can increase the similarity score even if the action is not visible. Interestingly, combining these much stronger base models with our score still improves performance by

Qualitative results

To provide more insight about the kind of signal captured by our model S, we provide clips from HowTo100M with high and low actionness scores in Figure 6. In order to obtain these examples, we run our model on 50,000 randomly sampled videos from HowTo100M. To show the variety of different tasks, we illustrate the top 10 highest scoring clips within each of the four largest HowTo100M categories: Food and Entertaining, Home and Garden, Hobbies and Craft and Cars & Other Vehicles. Finally, we also give the 10 lowest scoring clips across all categories to illustrate the type of background discovered by our model.

Conclusion

In this paper, we have presented a self-supervised method that can separate actions from background without resorting to any form of manual annotation. It does so by leveraging the assumption that frames that depict key actions are more informative when it comes to predict what may come next or what happens in the past. Equipped with our method, we managed to improve the state-of-the-art on a challenging action localization benchmark. As future work we notably plan to investigate if our method would generalize to broader domains than instructional videos. Another potential direction would be to jointly discriminate background and actions while also clustering similar actions together, thus paving the way for unsupervised action discovery.

Fig. 2 .

 2 Fig. 2. Given a sequence of clips X = (x1, x2, ..., xM ) extracted from the same video as input, our model produces two types of outputs: confidence S(xi) that video clip xi displays an action, and confidence F (xi, xj) that xi occurs before xj in the original video. We combine these scores together to produce an order score G(X) that reflects the model confidence that the sequence X is displayed in the correct order. We generate training data for G for free by simply maintaining or reverting order of videos. By doing so, the model automatically learns to put more weight Wij ∝ exp(S(xi) + S(xj)) to clips from which it is easy to predict whether clip xi has happened before clip xi. We argue that clips with such properties are more likely to be actions that allow S to become an actionness score. Top. Architecture for producing the actionness score S and its training. Bottom. Evolution of the learnt actionness score S throughout a video. Note how the model learned to put higher weights to frames that correspond to actions such as adding suggar (x2) or pouring (x4) and low score on clips that are not relevant to the completion of the task (i.e., background ) such as a man standing still (x1) or a clip only showing empty glasses (x3)

Fig. 3 .

 3 Fig. 3. Actionness scores at different temporal locations of COIN videos test set. (left) scores of the actionness model S, trained on untrimmed videos. (center) scores of the model S, trained on trimmed videos. (right) Distribution of actions in the videos. When trained on untrimmed videos, the score concentrates in the beginning and in the end of the video. When trained on untrimmed videos, the score distribution is closer to the ground truth action label distribution which leads to significant increase in background vs. action classification performance

Fig. 4 .

 4 Fig. 4. Left: long vs. short range. Action vs. background average precision of our model on COIN (top) and on CrossTask (bottom) as a function of the range d (in seconds) spanned by the sequence X. Duration of each sampled clip equals d/10. Performance increases with the range used for the order prediction task, confirming our hypothesis that long range action dependencies are better to learn about actionness. Right: number of segments. Average precision of our model on COIN and CrossTask for different number of segments M sampled per video

Fig. 5 .

 5 Fig. 5. Action proposal. Average recall versus average number of proposals per video

  Acknowledgements. This work was partially supported by the European Regional Development Fund under project IMPACT (reg. no. CZ.02.1.01/0.0/0.0/15 003/0000468), Louis Vuitton ENS Chair on Artificial Intelligence, the MSR-Inria joint lab, and the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). Highest scoring clips (Food and Entertainment) Highest scoring frames (Home and Garden) Highest scoring frames (Hobbies and Craft) Highest scoring frames (Cars & Other Vehicles) Lowest scoring frames (all categories)

Fig. 6 .

 6 Fig. 6. First four rows show highest actionness scoring clips from the top 4 categories of HowTo100M: Food and Entertaining, Home and Garden, Hobbies and Craft and Cars & Other Vehicles. Bottom row illustrates the lowest scoring clips according to our actionness score S (see Supplementary material for more examples).

Table 1 .

 1 Action vs. Background. Frame-wise average precision of background separation on COIN and CrossTask datasets

	Dataset	(i) Chance (ii) Chance (trim@0.3) (iii) Hand Detector (iv) Optical Flow	Ours (v) Supervised
	COIN	45.6%	53.5%	50.6%	47%	59.0%	70.7%
	CrossTask	27.5%	32.6%	28.4%	30.3%	47.6%	56.2%

Table 2 .

 2 Step localization results on CrossTask with and without our actionness score a significant margin (+1.2% recall and +0.7% recall for the best S3D model), hence setting a new state-of-the-art on the CrossTask benchmark[41].