ab , B. Iooss M Lamboni

A.-L Popelin

F Gamboa

Derivative-based global sensitivity measures: general links with Sobol' indices and numerical tests

Keywords: Boltzmann measure, Derivative based global sensitivity measure, Global sensitivity analysis, Log-concave measure, Poincaré inequality, Sobol' indices

The estimation of variance-based importance measures (called Sobol' indices) of the input variables of a numerical model can require a large number of model evaluations. It turns to be unacceptable for high-dimensional model involving a large number of input variables (typically more than ten). Recently, Sobol and Kucherenko have proposed the Derivative-based Global Sensitivity Measures (DGSM), defined as the integral of the squared derivatives of the model output, showing that it can help to solve the problem of dimensionality in some cases. We provide a general inequality link between DGSM and total Sobol' indices for input variables belonging to the class of Boltzmann probability measures, thus extending the previous results of Sobol and Kucherenko for uniform and normal measures. The special case of log-concave measures is also described. This link provides a DGSM-based maximal bound for the total Sobol indices. Numerical tests show the performance of the bound and its usefulness in practice.

Introduction

With the advent of computing technology and numerical methods, computer models are now widely used to make predictions on little-known physical phenomena, to solve optimization problems or to perform sensitivity studies. These complex models often include hundreds or thousands uncertain inputs, whose uncertainties can strongly impact the model outputs (De Rocquigny et al . [START_REF]Uncertainty in industrial practice[END_REF], Kleijnen [START_REF] Kleijnen | Design and analysis of simulation experiments[END_REF], Patelli et al . [START_REF] Patelli | Monte Carlo gradient estimation in high dimensions[END_REF]). In fact, it is well known that, in many cases, only a small number of input variables really act in the model (Saltelli et al . [START_REF]Sensitivity analysis, Wiley Series in Probability and Statistics[END_REF]). This number is referred to the notion of the effective dimension of a function (Caflish et al . [START_REF] Caflisch | Valuation of mortgage backed securities using brownian bridges to reduce effective dimension[END_REF]), which is a useful way to deal with the curse of dimensionality in practical applications.

Global Sensitivity Analysis (GSA) methods (Sobol [20], Saltelli et al . [START_REF]Sensitivity analysis, Wiley Series in Probability and Statistics[END_REF]) are used to quantify the influence of model input variables (and their interaction effects) on a model reponse. It is also an objective way to determine the effective dimension by using the model simulations (Kucherenko et al . [START_REF] Kucherenko | The identification of model effective dimensions using global sensitivity analysis[END_REF]). A first class of GSA methods, called "screening" methods, aim at dealing with a large number of input variables (from tens to hundreds). An example of screening method is the Morris' method (Morris [START_REF] Morris | Factorial sampling plans for preliminary computational experiments[END_REF]), which allows a coarse estimation of the main effects using only a few model evaluations. While taking into account the interactions between the indices, the basic form of the Morris method did not compute precise sensitivity indices associated to the interactions between inputs. The second class of GSA methods are the popular quantitative methods, mainly based on the decomposition of the model output variance, which leads to the so-called variance-based methods and Sobol' sensitivity indices. It allows computing the main and total effects (called first order and total Sobol' indices) of each input variable, as well as interaction effects. However, for functions with non linear and interaction effects, the estimation procedures become particularly expensive in terms of number of required model evaluations. Hence, for this kind of model, variance-based methods can only be applied to a limited number of input variables (less than tens).

Recently, Sobol and Kucherenko [START_REF] Sobol | Derivative based global sensitivity measures and the link with global sensitivity indices[END_REF][START_REF] Sobol | A new derivative based importance criterion for groups of variables and its link with the global sensitivity indices[END_REF] have proposed the so-called Derivativebased Global Sensitivity Measures (DGSM), which can be seen as a kind of generalization of the Morris screening method. DGSM seem computationally more tractable than variance-based measures, specially for high-dimensional models. They also theoretically proved an inequality linking DGSM to total Sobol' indices in the case of uniform or Gaussian input variables.

In this paper, we investigate this close relationship between total Sobol' indices and DGSM, by extending this inequality to a large class of Boltzmann probability measures. We also obtain result for the class of log-concave measures. The paper is organized as follows: Section 2 recalls some useful definitions of Sobol' indices and DGSM. Section 3 establishes an inequality between these indices for a large class of Boltzmann (resp. log-concave) probability measures. Section 4 provides some numerical simulations on two test models, illustrating how DGSM can be used in practice. We conclude in Section 5.

Global sensitivity indices definition

Variance-based sensitivity indices

Let Y = f (X) be a model output with d random input variables X = (X 1 , . . . , X d ).

If the input variables are independent (assumption A1) and E (f 2 (X)) < +∞ (assumption A2), we have the following unique Hoeffding decomposition (Efron and Stein [START_REF] Efron | The jacknife estimate of variance[END_REF]) of f (X):

f (X) = f 0 + d j f j (X j ) + d i<j f ij (X i , X j ) + . . . + f 1...d (X 1 , . . . , X d ) (2.1) = u⊂{1,2,...d} f u (X u ), (2.2)
where

f 0 = E [f (X)] corresponds to the empty subset; f j (X j ) = E [f (X)|X j ] -f 0 and f u (X u ) = E [f (X)|X u ] - v⊂u f v (X v ) for any subset u ⊂ {1, 2, . . . , d} .
By regrouping all the terms in equation (2.1) that contain the variable X j (j = 1, 2, . . . , d) in the function called g(•):

g(X j , X ∼j ) = u∋j f u (X u ) , (2.3)
we have the following decomposition:

f (X) = f 0 + g(X j , X ∼j ) + h(X ∼j ), (2.4)
where X ∼j denotes the vector containing all variables except X j and h(

•) = f (•) - f 0 -g(•).
Notice that this decomposition is also unique under assumptions A1 and A2. The function g(•), itself, suffices to compute the total sensitivity indices. Indeed, it contains all information relating f (X) to X j .

Definition 2.1. Assume that A1, A2 hold, let µ(X) = µ(X 1 , . . . , X d ) be the distribution of the input variables. For any non empty subset u ⊆ {1, 2, . . . , d}, set first

D = f 2 (x)dµ(x) -f 2 0 , D u = f 2 u (x u )dµ(x u ) , D tot u = v⊇u f 2 v (x v )dµ(x v ) . (2.5)
Further, the first order Sobol sensitivity indices (Sobol [20]) of X u is

S u = D u D , (2.6)
The total sensitivity Sobol index of X u (Homma and Saltelli [START_REF] Homma | Importance measures in global sensitivity analysis of non linear models[END_REF]) is

S Tu = D tot u D . (2.7)
The following proposition gives another way to compute the total sensitivity indices.

Proposition 2.1. Under assumptions A1 and A2, the total sensitivity indices of variable X j (j = 1, 2, . . . , d) is obtained by the following formulas:

D tot j = g 2 (x j , x ∼j )dµ(x) (2.8)
and

D tot j = 1 2 f (x) -f (x ′ j , x ∼j ) 2 dµ(x)dµ(x ′ j ) .
(2.9)

Proof 2.1. The first formula is an obvious consequence of equation (2.4), and it is obtained by using the orthogonality of the summands in equation (2.1). Indeed,

D tot j = v⊇j f 2 v (x v )dµ(x v ) = v⊇j f v (x v ) 2 dµ(x) = g 2 (x j , x ∼j )dµ(x).
The later formula is proved in Sobol [START_REF] Sobol | Global sensitivity indices for non linear mathematical models and their Monte Carlo estimates[END_REF].

Derivative-based sensitivity indices

Derivative-based global sensitivity method uses the second moment of model derivatives as importance measure. This method is motivated by the fact that a high value of the derivative of the model output with respect to some input variable means that a big variation of model output is expected for a variation of the variable.

This method extends the Morris method (Morris [START_REF] Morris | Factorial sampling plans for preliminary computational experiments[END_REF]). Indeed, it allows to capture any small variation of the model output due to input variables.

DGSM have been first proposed in Sobol and Gresham [START_REF] Sobol | On an alternative global sensitivity estimators[END_REF]. Then, they have been largely studied in Kucherenko et al . [START_REF] Kucherenko | Monte Carlo evaluation of derivative-based global sensitivity measures[END_REF], Sobol and Kucherenko [START_REF] Sobol | Derivative based global sensitivity measures and the link with global sensitivity indices[END_REF][START_REF] Sobol | A new derivative based importance criterion for groups of variables and its link with the global sensitivity indices[END_REF] and Patelli et al . [START_REF] Patelli | Global sensitivity of structural variability by random sampling[END_REF]. From now on, we assume that the function f is differentiable.

Two kind of DGSM are defined below: Definition 2.2. Assume that A1 holds and that ∂f (X) ∂x j is square-integrable (assumption A3). Then, for j = 1, 2, . . . d, we define the DGSM indices by:

ν j = E ∂f (X) ∂x j 2 (2.10) = ∂f (x) ∂x j 2 dµ(x) .
Let w(•) is be a bounded measurable function. A weighted version of the last indices is:

τ j = ∂f (x) ∂x j 2 w(x j )dµ(x).
(2.11)

Remark 2.1. Sobol and Kucherenko [START_REF] Sobol | A new derivative based importance criterion for groups of variables and its link with the global sensitivity indices[END_REF] showed that, for a specific weighting function w(x j ) = 1 -3x j + 3x

ν j = ∂g(x) ∂x j 2 dµ(x) .
(2.12) A5). In other words, a twice differentiable probability density function ρ(x) is said to be log-concave if, and only if,

τ j = ∂g(x) ∂x j 2 w(x j )dµ(x), (2.13
d 2 dx 2 [log ρ(x)] ≤ 0 . (3.14)
Note that the probability measure of uniform density on a finite interval is not continuous on R. So it cannot be considered in the class of log-concave probability measure, nor in the class of Boltzmann probability measures.

The two following propositions give the formal link between Sobol' indices and derivative-based sensitivity indices.

Theorem 3.1. Under assumptions A1, A2, A3 and A4, we have:

D tot j ≤ C(µ j )ν j (3.15) with C(µ j ) = 4C 2 1 and C 1 = sup x∈R min(F j (x), 1 -F j (x)) ρ j (x) the Cheeger constant, F j (•)
the cumulative probability function of X j and ρ j (•) the density of X j .

We recall the four assumptions:

• A1: independence between inputs X 1 , X 2 , . . . , X d , • A2: f ∈ L 2 (R), • A3: ∂f ∂x j ∈ L 2 (R),
• A4: the distribution of X j is a Boltzmann probability measure.

D tot j ≤ [exp(v(m))] 2 ν j , (3.16
)

with C 1 = exp(v(m)) 2
the Cheeger constant and m the median of the measure µ j (such that µ(X j ≤ m) = µ(X j > m)).

We recall the assumption A5: the distribution of X j is a log-concave probability measure.

Proof 3.2. See proof 3.1.

1

Table 1 shows Cheeger constant for some log-concave probability distributions 2 that are used in practice for uncertainty and sensitivity analyses. We also give 8 [START_REF] Ané | Sur les inégalités de Sobolev logarithmiques[END_REF]). .

9 Distribution v(x) m C 1 Normal N (µ, σ 2 ) (x -µ) 2 2σ 2 + log(σ) µ σ 2 Exponential E(λ), λ > 0 λx -log(λ) log 2 λ 1 λ Beta B(α, β), α, β ≥ 1 log x 1-α (1 -x) 1-β No expression - Gamma Γ(α, β), scale α ≥ 1, shape β > 0 log x 1-α Γ(α) + x β + α log β No expression - Gumbel G(µ, β), scale β > 0 x -µ β + log β + exp - x -µ β µ -β log(log 2) β log 2 Weibull W(k, λ), shape k ≥ 1, scale λ > 0 log λ k + (1 -k) log x λ + x λ k λ(log 2) 1/k λ(log 2) (1-k)/k k

Numerical tests

Derivative sensitivity indices estimates

A classical estimator for the DGSM is the empirical one and is given below:

ν j = 1 n n i=1 ∂f (X (i) ) ∂x j 2 .
(4.17)

Experimental convergence properties of this estimator are given in Sobol and Kucherenko [START_REF] Sobol | Derivative based global sensitivity measures and the link with global sensitivity indices[END_REF].

From definition (2.4), we know that ∂f (X (i) ) ∂x j = ∂g(X (i) ) ∂x j . Estimator of D tot j (see equation (2.8)) and estimator (4.17 Pradlwarter [START_REF] Patelli | Monte Carlo gradient estimation in high dimensions[END_REF] proposed a Monte Carlo estimation of gradient in high dimension.

They used an unbiased estimator for gradients and have shown that the number of Monte Carlo evaluations n ≤ d is sufficient for gradient computations. In the worst case, their procedure requires the same number of model evaluations than the finite difference method. The method is very efficient when the model has a low effective dimension.

In the following Sections, we compare the estimates of the Sobol indices (S j and S T j ) and the upper bound of S T j (see inequality (3.15)). let denote Υ j , the total sensitivity upper bound:

Υ j = C ν j D , (4.18)
where D is the variance of the model output f (X) and C = 4C 2 1 . The goal of our numerical tests is just to compare the differences in terms of ranking and not to study the speed of convergence of the estimates.

Test on the Morris function

As a first test, we consider the Morris function (Morris [START_REF] Morris | Factorial sampling plans for preliminary computational experiments[END_REF]) that includes 20 independent and uniform input variables. The Morris function is defined by the following equation:

y = β 0 + 20 i=1 β i w i + 20 i<j β i,j w i w j + 20 i<j<l β i,j,l w i w j w l + 20 i<j<l<s β i,j,l,s w i w j w l w s , (4.19)
where

w i = 2 x i - 1 2
except for i = 3, 5, 7 where w i = 2 1.1

x i x i + 1 - 1 2
. The coefficient values are:

β i = 20 for i = 1, 2, . . . , 10,
β i,j = -15 for i, j = 1, 2, . . . , 6, i < j β i,j,l = -10 for i, j, l = 1, 2, . . . , 5, i < j < l and β 1,2,3,4 = 5.

The remaining first and second order coefficients were generated independently from the normal distribution N (0, 1) and the remaining third and fourth coefficient were set to 0.

We replace the uniform distributions associated with several input variables by different log-concave measures of the Table 1 in order to show how the bounds can be used in practical sensitivity analysis. Table 2 shows the probability distributions associated to each input of the Morris function.

We have performed some simulations that allow computing the DGSM indices and the Sobol' indices for the 20 independent factors. Sobol' indices S j and S T j are mates the total Sobol' index S T j for X3, X4 and X5. However, for X 4 , we have Υ 4 < 1 and this coarse information is still usefull. For the three other inputs, the bound is relevant.

For two inputs (X3 and X5), results can be judged as strongly unsatisfactory as the bound is useless (larger than 1 which is the maximal value for a sensitivity index). We suspect that these results come from:

• the model non linearity with respect to these inputs (see equation (4.19)),

• the input distributions (exponential and Weibull).

The second explanation seems to be the more convincing as these types of distribution can provide larger values during Monte Carlo simulations. In this case, departures from the central part of the input domain leads to uncontrolled derivative values of the Morris function. Indeed, it can be seen that ν j is particularly large for X3 and X5, because of high derivative values in the estimation samples. Moreover, we have no observed the same results for X 1 , X 2 and X 4 .

As a conclusion of this first test, we argue that the bound Υ j is well-suited for a screening purpose. Moreover, coupling Υ j interpretation with first order Sobol' indices S j (estimated at low cost using a smoothing technique or a metamodel, see [START_REF]Sensitivity analysis, Wiley Series in Probability and Statistics[END_REF][START_REF] Iooss | Revue sur l'analyse de sensibilité globale de modèles numériques[END_REF]) can bring useful information about the presence or absence of interaction.

For inputs following uniform, normal and exponential distributions,the bound is extremely efficient. In these particular cases, the bound is the best one and cannot be improved.

A case study: a flood model

To illustrate how the Cheeger constant can be used for factors prioritization, when we use the DGSM, we consider a simple application model that simulates the height of a river compared to the height of a dyke. When the height of a river is over the height of the dyke, flooding occurs. This academic model is used as a pedagogical example in Iooss [START_REF] Iooss | Revue sur l'analyse de sensibilité globale de modèles numériques[END_REF]. The model is based on a crude simplification of the 1D hydro-dynamical equations of SaintVenant under the assumptions of uniform and constant flowrate and large rectangular sections. It consists of an equation that involves the characteristics of the river stretch:

S = Z v + H -H d -C b with H =   Q BK s Zm-Zv L   0.6 , (4.20)
with S the maximal annual overflow (in meters) and H the maximal annual height of the river (in meters).

The model has 8 input variables, each one follows a specific probability distribution (see Table 4). Among the input variables of the model, H d is a design parameter.

The randomness of the other variables is due to their spatio-temporal variability, our ignorance of their true value or some inaccuracies of their estimation. We suppose that the input variables are independent. We also consider another model output: the associated cost (in million euros) of the dyke presence, compare these results to the global sensitivity indices, we can infer that they are obviously wrong. This is easily explained by the fact that the input variables have different unities and that the indices ν j and τ j have not been renormalized by the constant depending on the probability distribution of X j .

Input

C p = 1I S>0 + 0.2 + 0.8 1 -exp -1000 S 4 1I S≤0 + 1 20 (H d 1I H d >8 + 81I H d ≤8 ) ,
By looking at the total sensitivity upper bound Υ j , the most influential variables are the following: Q, Z v , H d , K s for the overflow output and for the cost output. It gives the same subset of the most influential variables with some slight differences for the prioritization of the most influential variables. In conclusion, we state that Υ j can provide correct information on input variance-based sensitivities.

Conclusion

Global sensitivity analysis, that allows exploring numerically complex model and factors fixing setting, requires a large number of model evaluations. Derivative-based global sensitivity method needs a much smaller number of model evaluations (gain factor of 10 to 100). The reduction of the number of model evaluations becomes more significant when the model output is controlled by a small number of input variables and when the model does not include much interaction among input variables. This is often the case in practice.

In this paper, we have produced an inequality linking the total Sobol' index and a derivative-based sensitivity measure for a large class of probability distributions (Boltzmann measures). The new sensitivity index Υ j , which is defined as a constant times the crude derivative-based sensitivity, is a maximal bound of the total

Acknowlegments

Part of this work has been backed by French National Research Agency (ANR) through COSINUS program (project COSTA BRAVA noANR-09-COSI-015). We thank Jean-Claude Fort for helpful discussions and two anonymous reviewers for their valuable comments.

) 3 .

 3 Variance-based sensitivity indices vs. derivative-based sensitivity indicesAs DGSM estimations need much less model evaluations than total Sobol' indices estimations (Kucherenko et al .[START_REF] Kucherenko | Monte Carlo evaluation of derivative-based global sensitivity measures[END_REF]), it would be interesting to use the DGSM, instead of total Sobol' indices, for factors fixing setting. A formal link is therefore necessary to provide a mathematical relation between total Sobol' indices and DGSM. Sobol and Kucherenko[START_REF] Sobol | Derivative based global sensitivity measures and the link with global sensitivity indices[END_REF] have established an inequality linking these two indices for uniform and Gaussian random variables (maximal bound for S T j ). In this section, we extend the inequality for Sobolev' space model whith the marginal distribution of input variables belonging to the class of Boltzmann measure on R (assumption A4). A measure δ on R is said to be a Boltzmann measure if it is absolutely continuous with respect to the Lebesgue measure and its densitydδ(x) = ρ(x)dx = c exp[-v(x)]dx. Here v(•)is a continuous function and c a normalizing constant. Many classical continuous probability measures used in practice are Boltzmann measures (see de Rocquigny et al . [5] and Saltelli et al . [19]). The class of Boltzmann probability measures includes the well known class of logconcave probability measures. In this case, v(•) is a convex function (assumption

3 7 (

 7 their medians and the functions v(•). We obtain the same results for the normal 4 distribution N (µ, σ 2 ) similar to Sobol and Kucherenko[START_REF] Sobol | Derivative based global sensitivity measures and the link with global sensitivity indices[END_REF] but we prove them in 5 another way (in this case, v(m) = log(σ)). For uniform distribution U[a b], Sobol 6 and Kucherenko [23] obtained via direct integral manipulations the inequality D tot j ≤ ba) 2 π 2 ν j . This relation is the classical Poincaré or Writtinger inequality (Ane et al .

  ) are based on the same function g(•) and it seems that estimations of these two indices will require approximately the same number of model evaluations in order to converge towards their respective values. Computation of DGSM and Sobol' indices can be performed with Monte Carlolike algorithm, such as Latin Hypercube Sampling, quasi-Monte Carlo and Monte Carlo Markov Chain sampling. Kucherenko et al . [13] have shown that quasi-Monte Carlo outperforms Monte Carlo when model has a low effective dimension. Computation of DGSM needs model gradient estimation. For complex models, model gradient computation can easily be obtained by finite difference method. Patelli and

5 and 6 .

 56 (4.21) with 1I A (x) the indicator function which is equal to 1 for x ∈ A and 0 otherwise. In this equation, the first term represents the cost due to a flooding (S > 0) which is 1 million euros, the second term corresponds to the cost of the dyke maintenance (S ≤ 0) and the third term is the investment cost related to the construction of the dyke. The latter cost is constant for a height of dyke less than 8 m and is growing proportionally with respect to the dyke height otherwise. Sobol' indices are estimated with the same algorithms than for the Morris function, using two initial Monte Carlo samples of size 10 5 and 20 replicates of the estimates. It leads to 2 × 10 7 model evaluations in order to compute first order indices S j and total indices S T j (by taking the mean of the 20 replicates). For estimating the DGSM (ν j , weighted DGSM τ j and the total sensitivity upper bound Υ j ), a Sobol sequence is used with 1 × 10 4 model evaluations. Results of global sensitivity analysis and derivative-based global sensitivity analysis for respectively the overflow S and the cost C p outputs are listed in Tables Global sensitivity indices show small interaction among input variables for the overflow and the cost outputs. Four input variables (Q, H d , K s , Z v ) drive the overflow and the cost outputs.

  Sobol' index. It improves factors fixing setting by using derivative-based sensitivities instead of variance-based sensitivities. Two numerical tests have confirmed that the bound Υ j is well-suited for a screening purpose. When total Sobol' indices cannot be estimated because of a cpu time expensive model, Υ j can provide correct information on input sensitivities. Previous studies have shown that estimating DGSM with a small derivatives' sample (with size from tens to hundreds) allows to detect non influent inputs. In subsequent works, we propose to use jointly DGSM and first order Sobol' indices. With these information, an efficient methodology of global sensitivity analysis can be applied and brings useful information about the presence or absence of interaction (see Iooss et al . [10]).

Table 1 :

 1 Standard log-concave probability distributions: v(•) function, median m and Cheeger constant C 1 (see Theorem 3.2).

For general log-concave measures, no analytical expressions are available for the 10 Cheeger constant. In this latter case or in case of non log-concave but Boltzmann 11 measure, we can estimate the Cheeger constant by numerically evaluating the ex-pression sup x∈R min(F j (x),1-F j (x)) ρ j (x)

Table 4 :

 4 Input variables of the flood model and their probability distributions

Table 5 :

 5 Sensitivity indices for the overflow output of the flood model.

	Based on derivative sensitivity indices (ν j ) or weighted derivative sensitivity in-
	dices (τ j ) we have obtained another subset of the most influential variables that
	are Z

v , C b , H d , Z m . These results mean that, for example, the maximum annual flowrate (Q) does not have any impact on the overflow and the cost output. If we

Table 6 :

 6 Sensitivity indices for the cost ouput of the flood model.

Corresponding author: bertrand.iooss@edf.fr, Phone: +33 1877969, Fax: +33 130878213 Preprint submitted to Mathematics and Computers in Simulation July 1,

 3.

In distinguish several situations that can occur:

1. First order and total Sobol' indices are negligible (inputs X11 to X20). In this case, we observe that the bound Υ j is always negligible. For all the inputs, this test shows the high efficiency of the bound: a negligible bound warrants that the input has no influence.

2. First order and total Sobol' indices significantly differ from zero and have approximately the same value (inputs X7 to X10). This means that the input has some influence but no interactions with other inputs. In this case, the bound Υ j is relevant (close to S T j ), except for X7. The interpretation of the bound gives a useful information about the total influence of the input.

3. First order Sobol' index is negligible while total Sobol' index significantly differs from zero (inputs X1 to X6). In this case, the bound Υ j largely oversti-


Alessandro Prest

Christian Leistner

Javier Civera

Cordelia Schmid

Vittorio Ferrari

Learning Object Class Detectors from Weakly Annotated Video

Object detectors are typically trained on a large set of still images annotated by bounding-boxes. This paper introduces an approach for learning object detectors from realworld web videos known only to contain objects of a target class. We propose a fully automatic pipeline that localizes objects in a set of videos of the class and learns a detector for it. The approach extracts candidate spatio-temporal tubes based on motion segmentation and then selects one tube per video jointly over all videos. To compare to the state of the art, we test our detector on still images, i.e., Pascal VOC 2007. We observe that frames extracted from web videos can differ significantly in terms of quality to still images taken by a good camera. Thus, we formulate the learning from videos as a domain adaptation task. We show that training from a combination of weakly annotated videos and fully annotated still images using domain adaptation improves the performance of a detector trained from still images alone.

Introduction

Object class detection is a key problem in computer vision. The standard way to train state-of-the-art methods is to gather a large, diverse set of images and annotate them manually, possibly supported by crowd sourcing platforms such as Mechanical Turk 1 . The typical level of annotation needed is a bounding-box for each object instance [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF]. In general the performance of a detector increases with the number of annotated instances [START_REF] Vijayanarasimhan | Large-scale live active learning: Training object detectors with crawled data and crowds[END_REF]. Because manual annotation can be inflexible, expensive and tedious, recent work investigated methods that can learn from unlabeled or weakly annotated data [START_REF] Arora | Unsupervised segmentation of objects using efficient learning[END_REF][START_REF] Blaschko | Simulatenous object detection and ranking with weak supervision[END_REF][START_REF] Chum | An exemplar model for learning object classes[END_REF][START_REF] Lee | Learning the easy things first: Self-paced visual category discovery[END_REF][START_REF] Winn | LOCUS: learning object classes with unsupervised segmentation[END_REF]. However, learning a detector without location annotation is very difficult and performance is still below fully supervised methods [START_REF] Deselaers | Localizing objects while learning their appearance[END_REF][START_REF] Pandey | Scene recognition and weaklysupervised object localization with deformable part-based models[END_REF].

In this paper, we leave the common path of learning from images and instead exploit video as a source of training data. Interestingly, with a few exceptions [START_REF] Ali | Flowboost -appearance learning from sparsly labeled video[END_REF][START_REF] Leistner | Improving classifiers with weakly-related videos[END_REF][START_REF] Ramanan | Building models of animals from video[END_REF], learning from videos has been disregarded by the vision community. Yet, video offers a rich source of data and is becoming more easily accessible through internet sources such as YouTube. The benefits of video include: (i) it is easier to automatically segment the object from the background based on motion information, (ii) each video shows significant appearances variations of an object, and (iii) a set of videos provides a large number of training images, as each video consists of many frames.

The main contribution of this paper is an approach that learns high quality object detectors from real-world weakly annotated videos. We propose a fully automatic processing pipeline that localizes objects of a target class in a set of training videos (cf. figure 1) and learns a class-specific detector. Our approach requires only one label per video, i.e., whether it contains the class or not. It does not use any other information, such as the number or location of objects. In fact, the method does not even assume that all frames in the video contain the target class. To demonstrate the technique, we collect a video dataset from YouTube, coined YouTube-Objects.

Although we focus on learning from videos, we want to produce a detector capable of detecting objects in images at test time, such as the PASCAL07 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF]. However, individual frames extracted from real-world videos are often of lower quality than images taken by a high-quality camera. Video frames typically suffer from compression artifacts, motion blur, low color contrast, and lower signal-to-noise ratio of the sensor. This makes video frames somewhat different to images at the signal level. Hence, we cast the learning of detectors from videos as a domain adaptation task, i.e., learning while shifting the domain from videos to images. As it turns out, this is crucial for learning an effective detector from a combination of images and videos simultaneously.

Experiments on our YouTube-Objects dataset demonstrate that our technique can automatically localize target objects in videos and learn object detectors for several classes. As test data we use the challenging PASCAL07 object detection data set, and show that (i) detectors trained only from video already yield reasonable performance; (ii) detectors trained jointly from both video and images using domain adaptation perform better than when training from only the images (i.e. the training images of PASCAL07). In practice, our augmented detector outperforms the popular detector of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] on several classes.

In the next section, we review related work. In sec. 3 we introduce our technique for localizing objects in videos, and in sec. 4 we explain how to learn an object detector from them. In sec. 5 we state the task of improving object detectors for images by using video data as a domain adaptation problem and present an effective solution. In the experimental sec. 6 we evaluate our approach using PASCAL07 as test set.

Related Work

Learning from video. Most existing works on object detection train from images, e.g. [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF]. There is only a limited amount of work on learning object detectors from videos. In one of the earliest works, Ramanan et al. [START_REF] Ramanan | Building models of animals from video[END_REF] showed how to build part-based animal models for tracking and detection without explicit supervisory information. The tracking is based on a simple hidden Markov model and the detector is a pictorial structure based on a 2D kinematic chain of rectangular segments. The model allows to detect new instances of the animal. Ommer et al. [START_REF] Ommer | Seeing the objects behind the dots: Recognition in videos from a moving camera[END_REF] learn detection models as 3D point clouds using structure-frommotion. They train from controlled, hand-recorded video and the model can detect objects in test video, but not in images. Leistner et al. [START_REF] Leistner | Improving classifiers with weakly-related videos[END_REF] train a part-based random forest object detector from images and use patches extracted from videos to regularize the learning of the trees. Their approach captures the appearance variation of local patches from video and is tested on rather simple benchmarks. Also related to our approach are works on tracking-bydetection [START_REF] Grabner | On-line boosting and vision[END_REF][START_REF] Kalal | P-N learning: Bootstrapping binary classifiers from unlabeled data by structural constraints[END_REF]. Typically, a target object is marked by hand in one frame, or initialized with a preexisting detector, then a classifier is trained on-line in order to redetect the object in each frame. These approaches continuously adapt a detector specific to one video and do not attempt to train a generic class detector. In contrast, Ali et al. [START_REF] Ali | Flowboost -appearance learning from sparsly labeled video[END_REF] proposed a semi-supervised boosting variant that uses space-time coherence of video frames to determine the similarity among objects used for training a detector. The method requires a subset of fully annotated frames in each training video. Testing is performed on videos of the same scene, but at different time instances.

Our technique differs from the above ones in several respects: (i) we localize target objects in multiple training videos fully automatically and, then, use them to train an explicit object detector, e.g. [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]; (ii) our technique can train on videos alone and yet yield reasonable detectors for images; (iii) we operate on realistic video sequences downloaded from YouTube. The difficulty of applying state-ofthe art vision algorithms to real-world videos from the web has been recently reported in [START_REF] Zanetti | A walk through the web's video clips[END_REF]. Weakly-supervised learning from images. There are many works for learning object detectors from images without location annotation. These methods typically try to approximately localize object instances while learning a model of the class [START_REF] Arora | Unsupervised segmentation of objects using efficient learning[END_REF][START_REF] Blaschko | Simulatenous object detection and ranking with weak supervision[END_REF][START_REF] Crandall | Weakly supervised learning of part-based spatial models for visual object recognition[END_REF][START_REF] Chum | An exemplar model for learning object classes[END_REF][START_REF] Deselaers | Localizing objects while learning their appearance[END_REF][START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF][START_REF] Lee | Learning the easy things first: Self-paced visual category discovery[END_REF][START_REF] Winn | LOCUS: learning object classes with unsupervised segmentation[END_REF][START_REF] Pandey | Scene recognition and weaklysupervised object localization with deformable part-based models[END_REF]. In particular, Deselaers et al. [START_REF] Deselaers | Localizing objects while learning their appearance[END_REF] propose a technique to select one window per training image out of a large pool of candidates, so as to maximize the appearance similarity of the selected windows. Our technique of sec. 3.3 can be seen as an extension of [START_REF] Deselaers | Localizing objects while learning their appearance[END_REF] to video.

Localizing objects in real-world videos

We start with an overview of our pipeline, see fig. 2. The input is a collection of realistic videos, all labeled as containing the target class. Each video is typically a collage of heterogeneous footage recorded at different times and places. Sec. 3.1 explains how we partition a video into shots, each corresponding to a different scene. In sec. 3.2 we extract segments of coherent motion from each shot, using the technique of Brox and Malik [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF] (fig. 3

top row).

We then robustly fit a spatio-temporal bounding-box to each segment, which we call a tube (fig. 3

bottom row

). There are between 3 and 15 tubes per shot. Typically, there is one tube on the object of interest and several on other objects or the background. Given all tubes over all shots in the input training set, we jointly select one tube per shot by minimizing an energy function which measures the similarity of tubes, their visual homogeneity over time, and how likely they are to contain objects (cf. sec. 3.3). The tubes selected by these criteria are likely to contain instances of the target class (fig. 3 bottom row, blue boxes). The selected tubes are the output of our localization algorithm. We use them to train a detector for the target class, cf. sec. 4.2.

Temporal partitioning into shots

Consumer videos are often the concatenation of footage recorded at different times and places. This results in abrupt changes of the visual content of the video, called shot changes. These are very informative as they usually indicate that a new object or a new scene is filmed, thus breaking motion consistency. We detect shot changes by thresholding color histogram differences in consecutive frames [START_REF] Kim | An adaptive shot change detection algorithm using an average of absolute difference histogram within extension sliding window[END_REF]. We operate at a low threshold to ensure all shot changes are found. This partitions each video into multiple shots.

Forming candidate tubes

We extract motion segments from each shot using the recent approach of Brox and Malik [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF] which is based on large-displacement optical flow (LDOF). LDOF is a variational technique that integrates discrete point matches, namely the midpoints of regions, into a continuous energy formulation. The energy is optimized by a coarse-to-fine scheme to estimate large displacements even for small scale structures. As opposed to traditional optical flow, this algorithm tracks points over multiple frames, not only over two.

The motion segments are obtained by clustering the dense point tracks based on the similarity in their motion and proximity in location. This works very well for rigid objects, where an entire object is typically put in a single segment. Moreover, in many cases this provides a consistent segmentation even if parts of an object move somewhat differently than the average motion of the whole object (e.g. the jumping cat in fig. 3). This process outputs a set of motion segments, defined by a collection of spatio-temporal point tracks (fig. 3

top row).

The last step is to fit a spatio-temporal bounding-box to each motion segment M. At each frame t, we want to derive a bounding-box b t from the set of point-tracks M t . Simply taking the enclosing box of M t would lead to an unreliable estimate, as the outer region of a motion segment often contains spurious point-tracks. To alleviate this problem we select a subset of point tracks M ⊂ M which are required to be in the top 80-percentile of the median location of M i for all i ∈ {t, . . . , t + 4}. The box b t is then defined as the bounding-box of Mt . This method is robust to outlier point tracks in M and leads to a temporal series of bounding-boxes which vary smoothly over time and are well-anchored on the moving object.

Joint selection of tubes

At this point we have a set of candidate tubes T s = {T t s } in each shot s. Typically one tube contains the object of interest and the remaining ones background and other objects (fig. 3 bottom row). We describe in the following how to select the tubes l s ∈ {1, ..., |T s |} most overlapping with the object in each shot. We model this selection problem as minimizing an energy defined jointly over all N shots in all training videos. Formally, we define the energy of a configuration of tubes L = (l 1 , ..., l N ) to be

E(L|α) = s Φ s (l s ) + s,q Ψ s,q (l s , l q )
(1)

The pairwise potential Ψ. It measures the appearance dissimilarity between tubes l s , l q in two different shots s, q. It encourages selecting tubes that look similar. It is a linear combination of two dissimilarity functions ∆ that compare the appearance of the tubes over several frames according to two image features (details below)

Ψ s,q (l s , l q ) = α 1 ∆ BoW s,q (l s , l q ) + α 2 ∆ Phog s,q (l s , l q ) (2)
The pairwise terms connect all pairs of shots. Every tube in a shot is compared to every tube in all other shots (also from other videos, fig. 4). The unary potential Φ. It defines the cost of selecting tube l s in shot s. It is a linear combination of four terms

Φ s (l s ) = α 3 ∆ BoW s,s (l s , l s )+ α 4 ∆ Phog s,s (l s , l s ) (3) + α 5 Γ s (l s )+ α 6 Ω s (l s )
The first two terms prefer tubes which are visually homogeneous over time. They penalize tubes fit to incorrect motion segments, which typically start on an object but then drift to the background. For measuring homogeneity we use the same ∆ functions as above, but we compare some frames of l s to other frames of l s . The Γ term is the percentage of the bounding-box perimeter touching the border of the image, averaged over all frames in the tube. It penalizes tubes with high contact with the image border, which typically contain background (e.g., the blue segment in fig. 3

top row).

The Ω term is the objectness probability [START_REF] Alexe | What is an object?[END_REF] of the bounding-box, averaged over all frames in the tube. It measures how likely a box is to contain an object of any class, rather than background. It distinguishes objects with a welldefined boundary and center, such as cows and telephones, from amorphous background windows, such as grass and road. For this it measures various characteristics of objects in general, such as appearing different from their surroundings and having a closed boundary (see [START_REF] Alexe | What is an object?[END_REF] for more details). Minimization. The objective of tube selection is to find the configuration L * of tubes that minimizes E. We perform this minimization using the TRW-S algorithm [START_REF] Kolmogorov | Convergent tree-reweighted message passing for energy minimization[END_REF], which delivers a very good approximation of the global optimum L * = arg min L E(L|Θ) in our fully connected model. TRW-S also returns a lower bound on the energy. When this coincides with the returned solution, we know it found the global optimum. In our experiments, the lower bound is only 0.05% smaller on average than the returned energy. Thus, we know that the obtained configurations are very close to the global optimum. The tubes selected by L * are the output of our localization algorithm. They are used as input to train a detector for the target class in sec. 4.

Our technique is related to [START_REF] Deselaers | Localizing objects while learning their appearance[END_REF], where an energy function was minimized to select one window per image. We extended this idea to video, redefining the problem to select one tube per shot, and introducing potentials relevant for spatio-temporal data. Comparing tube appearance. To compute the ∆ appearance dissimilarity function, a subset of boxes within a tube is represented by two complementary visual features.

(1) BoW, a bag-of-word of dense SURF [START_REF] Bay | SURF: Speeded up robust features[END_REF] features quantized to a visual vocabulary of 500 words, learned from 200 random frames. We use a 3-level spatial pyramid to enforce spatial consistency [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]. (2) Phog, PHOG features [START_REF] Bosch | Representing shape with a spatial pyramid kernel[END_REF] capturing local shape as a distribution of HOG-features [START_REF] Dalal | Histogram of oriented gradients for human detection[END_REF] organized in a spatial pyramid [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]. For each tube, we compute BoW and Phog for the bounding-boxes in 5 frames sampled uniformly over the temporal extent of the tube. The function ∆ f s,q (l s , l q ) is the median of the χ 2 dissimilarity of the descriptors f over all 25 pairs of frames (one frame from tube l s in shot s and the other frame from tube l q in shot q). Weights α. The scalars α weight the terms of our energy model. We learn the optimal α using constraint generation [START_REF] Tsochantaridis | Large margin methods for structured and interdependent output variables[END_REF] on a separate set of 50 held out shots of cars. We manually annotated the location of the car in one frame of each shot. The constraint generation algorithm efficiently finds the weights that maximize the localization performance wrt the ground-truth annotations. The α learned from this small held-out dataset is then used for all classes in our experiments.

Learning a detector from the selected tubes

The previous section selects one tube per shot likely to contain an instance of the target class. This corresponds to automatically localizing a bounding-box in each frame of the shot covered by the tube. We now describe how to train an object detector from this data. The main technical issue is sampling high quality bounding-boxes from the large pool offered by all selected tubes (sec. 4.1). The sampled bounding-boxes can then be used to train any standard object detector which requires bounding-boxes for training, e.g., [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Harzallah | Combining efficient object localization and image classification[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF] (sec. 4.2).

Sampling positive bounding-boxes

The tubes selected in sec. 3.3 offer a very large number of bounding-boxes that could be used as positive samples for training a detector. In our YouTube-Objects dataset, this number is about 10k-70k, depending on the class (tab. 1). This is too much data to handle for the training procedures of most modern detectors, which input about 1k positive samples [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Harzallah | Combining efficient object localization and image classification[END_REF]. However, not all of these bounding-boxes contain the object of interest. Even with perfect tube selection, the best available tube might contain bounding-boxes covering other image elements. This happens when tubes mostly on the object start or end on something else, e.g., when the object moves out of the field of view, or when the underlying motion segment drifts to the background. Moreover, some shots might not even contain the target class as they are automatically collected from YouTube (recall we only assume annotation at the video level, not at the shot level). Using such bounding-boxes as positive samples can confuse the training of the detector.

We introduce here a sampling technique to (i) reduce the number of positive samples to a manageable quantity; (ii) select samples more likely to contain relevant objects. The first step is to quantify the quality of each bounding-box in the pool. For this we use a linear combination of its objectness probability and the percentage of perimeter touching the border of the image, exactly as the Ω and Γ terms in eq. ( 3) (but applied to a single frame). The second step is to sample a fixed number S of bounding-boxes according to this quality measure (treating the set of probabilities for all samples as a multinomial distribution). In all our experiments we use S = 500.

Training the object detector

The bounding-boxes sampled as described in the previous subsection can be used to train any object detector. As negative training set we randomly sample 2400 video frames from other classes. From this data we train two popular and complementary detectors: DPM: the part-based model2 of Felzenszwalb et al. [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. It consists of a root filter and deformable part filters. The method has been demonstrated to yield highly competitive results on the PASCAL07 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF] dataset.

SPM:

We employ SURF [START_REF] Bay | SURF: Speeded up robust features[END_REF] features quantized into a 500entries codebook learned on 500 frames randomly sampled from the training videos. A bounding-box is described by a 3-level spatial pyramid [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]. At training time we collect an initial set of negative samples by sampling 10 objectness [START_REF] Alexe | What is an object?[END_REF] windows in every negative training image. We, then, train a preliminary SVM classifier using Intersection Kernel [START_REF] Maji | Classification using intersection kernel support vector machines is efficient[END_REF], and search exhaustively for false positives in the negative images [START_REF] Dalal | Histogram of oriented gradients for human detection[END_REF]. The classifier is retrained using these additional hard negatives. At test time the detector operates on 100000 windows uniformly sampled for every test image, followed by non-maxima suppression.

Domain adaptation: from videos to images

Training a detector on videos and applying it to images corresponds to having training and test datasets from different domains. Recently, [START_REF] Torralba | An unbiased look on dataset bias[END_REF] highlighted the problems of visual classifiers if training and test set differ. [START_REF] Zanetti | A walk through the web's video clips[END_REF] showed that this is especially valid for videos from the web that suffer from compression artifacts, low resolution, motion blur and low color contrast. Thus, it is hard to train a detector from video that yields good results on images. Fig. 5. Images vs videos. Left: the sum of the magnitude of the HOG features in an object bounding-box, normalized by its size (computed using the implementation of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]). The 300 samples are sorted by gradient energy along the x-axis.

To illustrate that video and still images can be seen as two different domains, we conducted two experiments. The first is illustrated in fig. 5 and compares the HOG representation for 300 aeroplanes on frames from our YouTube-Objects dataset to 300 similar aeroplane images from PAS-CAL07 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF]. We can observe that the gradient energy of images is significantly larger, i.e., around one third, than that of video frames. In the second experiment, we follow the Name that Dataset protocol of [START_REF] Torralba | An unbiased look on dataset bias[END_REF]. We trained an SVM on GIST features [START_REF] Oliva | Modeling the shape of the scene: a holistic representation of the spatial envelope[END_REF] to distinguish video from images. This achieves a classification accuracy of 83%, confirming that images and videos are indeed different domains. Another difference between images and videos is the different distribution of viewpoints in which an object typically appears.

Domain adaptation

Domain Adaptation (DA) approaches try to improve classification accuracy in scenarios where training and test distributions differ. Let X = R F be the input space with F being the number of feature dimensions, and let Y = {-1, 1} be the output space (e.g. aeroplane or not). In DA, we have access to N samples from the source domain X s (e.g. video) together with their labels Y s , and M samples from the target domain X t (e.g. images) along with their labels Y t . Usually, N M . The task of domain adaptation is to train a function f : X → Y that performs well on the target domain. Note that the case where the performance decreases for the target domain is referred to as negative transfer [START_REF] Pan | A survey on transfer learning[END_REF]. There exists a number of approaches for domain adaptation [START_REF] Pan | A survey on transfer learning[END_REF]. For our application we explore a few simple methods that have been reported to perform surprisingly well [START_REF] Daume | Frustratingly easy domain adaption[END_REF]. We summarize below the three approaches we experiment with, following the nomenclature and notation of [START_REF] Daume | Frustratingly easy domain adaption[END_REF].

All. The simplest possible approach is to ignore the domain shift and directly train a single classifier using the union of all available training data {(x s i , y s i )} N i=1 and { x t j , y t j } M j=1 . This is a simple baseline that should be beaten by any real domain adaptation technique.

Pred. A popular approach is to use the output of the source classifier as an additional feature for training the target classifier. More precisely, we first train a classifier f s (x) on the source data {(x s i , y s i )} N i=1 . We, then, expand the feature vector of each target sample x t to [x t f s (x t )]. Finally, we train the target classifier using the expanded target training data { x t j f s (x t j ) , y t j } M j=1 . Prior. One of the most popular DA methods in Computer Vision is Prior, where the parameters of the source classifier are used as a prior when learning the target classifier [START_REF] Tommasi | Safety in numbers: Learning categories from few examples with multi model knowledge transfer[END_REF][START_REF] Aytar | Tabula rasa: Model transfer for object category detection[END_REF]. For instance, an SVM can be regularized in form of ||w sw t || 2 , where w is a learned weight vector. LinInt. Another technique is to first train two separate classifiers f s (x), f t (x) from the source and the target data, and then linearly interpolate their predictions on new target data at test time. Thus, LinInt forms a new classifier

f st (x) = λf s (x) + (1 -λ)f t (x)
, where λ is the interpolation weight (it can be set so as to minimize the expected loss on the target domain).

Beside these four approaches, there exist many others. One advantage of Pred and LinInt over other techniques is that they can combine heterogeneous classifiers, where the dimensionality or even the kind of features differ between the source and target domains.

LinInt for object detection

In the context of sliding-window object detection, as opposed to classification, LinInt cannot directly be applied. Different detectors might not only operate on different kinds of features, but even on different sets of windows in an image. For example, most detectors [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Pandey | Scene recognition and weaklysupervised object localization with deformable part-based models[END_REF] learn an optimal aspect-ratio from the training data and only score windows of that aspect-ratio on a test image. In our case, the aspectratio learned from video data might differ from that learned from images. Other differences might include the slidingwindow step and the sampling of the scale-space.

We introduce here a technique for combining arbitrary heterogeneous sliding-window detectors based on LinInt. We first let each detector score its own set of windows D on a test image I. Each window is represented as a 5-D vector d = {x 1 , y 1 , x 2 , y 2 , s} composed of the coordinates of the window in the image and its score. The two detectors, each trained separately, produce two separate sets of windows D 1 and D 2 for the same image I. We combine them into a set of windows D c with the following algorithm. First, we initialize D c = ∅. Then, for each window d 1 ∈ D 1 we do 1. Find the most overlapping window in D 2 :

d 2 = arg max d2∈D2 IoU(d 1 , d 2 ) with IoU(d 1 , d 2 ) = |d1∩d2| |d1∪d2|
the spatial overlap of two windows. 2. Combine the scores of d 1 , d 2 with a modified LinInt: between the two sets based on their overlap and combines scores of matched pairs of windows. In practice two matched windows often have very high overlap and are almost identical. However, in the case a window from D 1 has no good match in D 2 , our technique automatically reduces the combination weight.

s = λ • d s 1 + (1 -λ) • IoU(d 1 , d 2 ) • d s 2 where λ ∈ [0,
6. Experiments

Dataset

Our YouTube-Objects dataset is composed of videos collected from YouTube. For each of 10 object classes, we collected between 9 and 24 videos, whose duration varies between 30 seconds and 3 minutes (tab. 1). The videos are weakly annotated, i.e. we only ensure that at least one object of the relevant class is present in each video. For evaluating our automatic localization technique, we annotated bounding-boxes on a few frames containing the object of interest. For each class we annotated one frame per shot on 100-290 different shots. Importantly, these annotations are used exclusively to evaluate our technique (sec. 6.2). They are not input at any point in our fully automatic pipeline.

Localizing objects in the training videos

We evaluate here the quality of object localization in the training videos. We adopt the CorLoc performance measure used in [START_REF] Deselaers | Localizing objects while learning their appearance[END_REF][START_REF] Pandey | Scene recognition and weaklysupervised object localization with deformable part-based models[END_REF], i.e., the percentage of ground-truth bounding boxes which are correctly localized up to the PAS-CAL criterion (intersection-over-union >= 0.50). We evaluate separately the quality of (i) the tube extraction process (sec. 3.2) and of (ii) the tube selection process (sec. 3.3). To evaluate the tube extraction process, we select the tube with the maximum overlap with the ground-truth bounding box. The CorLoc of this best available tube can be seen as an upper-bound on the CorLoc that can be achieved by the automatic tube selection process.

The results are shown in tab. 2. Our automatic tube selection technique is very effective. In 7 classes out of 10 it performs close to the upper-bound, indicating it selects the best available tube most of the time. Cat, dog and train present higher intra-class variability which makes it harder to leverage on recurrent appearance patterns to select tubes covering the target objects. The performance of tube extraction varies substantially from class to class and is in general higher for rigid objects. The overall performance is satisfactory, but could be improved as it is currently missing many objects. The main reason for this is the difficulty of motion Table 4. Comparison of our approach to weakly supervised learning from images [START_REF] Pandey | Scene recognition and weaklysupervised object localization with deformable part-based models[END_REF].

segmentation in low quality, uncontrolled YouTube videos.

Training from video

Here we test on the 4952 images from the PASCAL07 test set using the official protocol [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007 Results[END_REF]. This is a very challenging dataset, with large variations in pose, appearance and scale. We report results on a subset of 10 classes, corresponding to objects that move and for which enough video data is available online. Tab. 3 presents results for three different training regimes: VOC: models trained on manual bounding-box annotations from the PASCAL07 Train + Val image set. VMA: models trained on the manually annotated frames from YouTube-Objects (sec. 6.1). VID: models trained from YouTube-Objects on the output of our fully automatic pipeline (sec. 3 and 4). Tab. 3 reports performance for the SPM as well as DPM detectors. The VOC training regime serves as a high quality reference. First we observe that the VID model performs close to the manually annotated VMA, confirming the quality of our automatic learning approach. Moreover, compared to the VOC models, the VID models offer reasonable performance, especially considering they take no manual intervention to train.

Interestingly, the results confirm the domain shift discussed in sec. 5. There is a significant performance gap between VOC and VMA, although they are trained with a similar number of samples and level of supervision. In sec. 6.5 we will improve over these results by training jointly from both images and video with domain adaptation.

Comparison to WS learning from images [29]

We compare our approach to a recent weakly supervised method for learning from images [START_REF] Pandey | Scene recognition and weaklysupervised object localization with deformable part-based models[END_REF]. It learns each model from all PASCAL07 training images corresponding to a class, given also its ground-truth average aspect-ratio. This information is required as their approach iteratively refines the DPM detector and does not converge if initialized with a square window. This is a little more supervision than used normally in weakly supervised learning, where only class labels for the image/video are given (as is our case).

Results [START_REF] Pandey | Scene recognition and weaklysupervised object localization with deformable part-based models[END_REF] are presented for a subset of 14 classes of PASCAL07. We obtained the learned DPM detectors [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] from the authors and evaluated them on the test set. Tab. 4 presents results on the 5 classes that have been evaluated in both our work and theirs. Our models learned on videos outperform their models learned from images. We believe this result validates our approach as an effective alternative to weakly supervised learning from images.

Training from video and images

Here we train detectors from a combination of weakly supervised video data and PASCAL07 fully supervised images using domain adaptation. Tab. 5 presents results for various adaptation methods (sec. 5). We report differential results wrt learning only on the target domain (still images, VOC rows in tab. 3). We train the λ parameter of LinInt by maximizing performance on the Val set of PASCAL07.

The results show that the All method, which combines training data at the earliest stage, degrades performance (negative transfer [START_REF] Pan | A survey on transfer learning[END_REF]). The problem is only partially alleviated when the combination happens at the feature level (Pred) or the parameter level (Prior). The LinInt method instead is immune to negative transfer and prevents a weaker model to harm the combined performance (by automatically setting λ to 0). Moreover, for DPM in 5 out of 10 classes LinInt improves over VOC, demonstrating that knowledge can be transferred from the video to the image domain, leading to a better detector than one trained from images alone (+2.0% AP on average on the 5 classes where λ > 0).

Conclusions

We introduced a technique for learning object detectors from real-world web videos. Furthermore, we formulated the problem of learning from both videos and still images jointly as a domain adaptation task. On PASCAL07 this resulted in increased performance compared to training from images alone.

The YouTube-Objects dataset is available for download on our project page 3

Fig. 1 .

 1 Fig. 1. Learning from Video. Yellow boxes represent tubes extracted by our method on the YouTube-Objects dataset. Blue boxes indicate the automatically selected tubes.

Fig. 2 .

 2 Fig. 2. Overview of our approach.

Fig. 3 .

 3 Fig. 3. Localizing objects in videos. (Top) Results of the motion segmentation. (Bottom) Tubes fit to the motion segments (the one selected by our approach is in blue).

Fig. 4 .

 4 Fig. 4. Candidate tubes from different shots are connected through pairwise terms (dashed lines).

Table 1 .

 1 1] weights the two detectors. 3. Add a new window to D c with the coordinates of d 1 but with score s. Statistics of our YouTube-Objects dataset. In total the dataset is composed of 155 videos, divided into 5507 shots and amounting to 571089 frames.

	This procedure is flexible as it can combine detectors de-
	fined on arbitrary sets of windows. It matches windows

Table 2 .

 2 Evaluation of the object localization performance of our method, as the percentage of correctly localized objects for (i) the best available extracted tube (first row) and (ii) the automatically selected tubes (second row).

					aero	bird	boat	car	cat	cow	dog	horse	mbike	train	AVG
			Tube extraction	53.9	19.6	38.2	37.8	32.2	21.8	27.0	34.7	45.4	37.5	34.8
			Tube selection		51.7	17.5	34.4	34.7	22.3	17.9	13.5	26.7	41.2	25.0	28.5
		aero	boat	horse	mbike	train	mAP
	DPM-VID	17.4	9.2		16.2	27.3	15.0	17.0
	[29]	11.5	3.0		20.3	9.1	13.2	11.4

Table 3 .

 3 together with additional videos showing intermediate processing stages of our approach. Evaluation of different detectors and different training regimes on the PASCAL07 test set, in Average Precision computed as the area under the precision-recall curve. The mAP column reports the mean AP over all classes.

			aero	bird	boat	car	cat	cow	dog	horse	mbike	train	mAP
	SPM	VOC VMA VID	22.5 16.8 14.0	10.0 3.9 9.4	10.4 2.6 0.6	27.4 18.7 15.0	22.1 16.5 14.9	10.8 10.1 9.4	13.4 6.0 7.5	21.1 8.5 11.9	25.8 15.9 14.6	27.3 12.0 5.6	19.1 11.1 10.3
	DPM	VOC VMA VID	29.6 23.6 17.4	10.1 9.9 9.3	17.1 8.4 9.2	55.0 40.4 35.7	18.4 2.0 9.4	24.7 18.6 9.7	11.3 9.7 3.3	57.7 28.3 16.2	47.8 29.5 27.3	44.5 15.7 15.0	31.6 18.6 15.2
				aero	bird	boat	car	cat	cow	dog	horse	mbike	train
		All(VOC,VID)	1.7	-4.7	-8.4	-1.7	1.5	-2.2	0.2	-2.1	-2.2	-4.2
	SPM	Pred(VOC,VID) Prior(VOC,VID)	1.3 -1.1	-4.6 0.5	0.3 -1.1	-4.3 0.6	2.9 -2.2	-0.3 -5.8	-5.2 -6.8	-1.6 0.7	-0.3 -1.3	-0.1 -0.3
		LinInt(VOC,VID)	2.9	0.0	0.2	0.6	0.0	0.0	0.0	0.0	1.9	0.0
	DPM	All(VOC,VID) LinInt(VOC,VID)	1.1 4.5	-0.4 1.4	-7.5 2.4	-2.7 0.0	-1.0 1.5	-9.2 0.4	-0.7 0.0	-9.0 0.0	-2.6 0.0	-12.2 0.0

Table 5 .

 5 We show relative improvement in Average-Precision wrt VOC models.

www.amazon.com/mturk

www.cs.brown.edu/ pff/latent/

http://groups.inf.ed.ac.uk/calvin/learnfromvideo

Acknowledgements. This work was partially funded by the QUAERO project supported by OSEO, French State agency for innovation, the European integrated projects AXES and RoboEarth, DPI2009-07130, SNSF IZK0Z2-136096, CAI-DGA IT 26/10 and a Google Research Award.