Roland Lenain

Marco Medici

Philippe Martinet

Philippe Martinet Ninsar

NINSAR: New itineraries for agroecology using cooperative robots

NINSAR New ItiNerarieS for Agroecology using cooperative Robots

Roland Lenain 1 , Marco Medici 2 , Philippe Martinet 3 , Ouiddad Labbani-Igbida 4 , Patrick Danès 5 , Faiz Ben Amar 6 , Yann Perrot 7 , Vincent Fremont 8 , Maan El Badaoui El Najjar 9 , Youcef Mezouar 10 , Cédric Pradalier 11 , Mohammed Chadli 12 , Olivier Simonin 13 , François Chaumette 14 , Paolo Robuffo 14 , Régis Tournebize 15 , François Pinet 16 , Marilys Pradel 17 , Jean Laneurit 1 , Loïc Sauvee 2 , Ezio Malis 3 , Juan Antonio Escareno 4 , Viviane Cadenat 5 , Eric Lucet 7 , Elwan Hery 8 , Roland Chapuis 10 , Stéphanie Aravecchia 11 , Desiré Sidibé

Social issues

The refinement of agroecology practices requiring relevant human effort appears difficult to consider due to the limited attractiveness of agricultural works for new generations.

Technical limitations

Yields may decrease in case agrochemical use is limited, and it is required that technology perform complex tasks (e.g., bio-control applications require enhanced crop monitoring and highly cadenced treatments, permaculture and bio-control require to simultaneously treat different cultures and to extend field surveillance).

Methods

Based on an iterative approach, activities will be focused on the experimental evaluation of robotic developments capable of producing new research themes at the interface of engineering and agronomic sciences. Robot performances will be measured in terms of level of precision, frequency, and coordination capacity, which will make it possible to build new routes based on the degree of achievable efficiency in terms of precision, speed, and achievable actions. The project will rely on experimental findings of other national actions (PEPR 'Agroecology and ICT', Grand Challenge 'Robotics for agroecology', Roboterrium axis 'Tirrex').

Expected results

• Innovative agroecological actions autonomously handled by cooperative robot fleets;

• Adaptive strategy for autonomous and discriminate treatments of crops;

• Enhancing a close collaboration between farmers and autonomous tools;

• Advancing in soft objects manipulation to operate accurately on crops and soil;

• Definition of new agronomic processes from intersection between agronomy and robotics.

Project aim

To develop robotic approaches for the implementation of agroecological practices, which ultimately means to design agroecological routes using a fleet of robots capable to cooperate while getting feedback from the surrounding environment. To achieve this objective, new farming practices and multi-robot capacities will be developed.

Background

Several agriculture strategies have been proposed in the last decades to achieve a more environment-friendly food production. The challenge is to increase the efficiency of energy, water, and agricultural inputs use by integrating agroecology practices (e.g., organic farming, regenerative agriculture, bio-control input application, sowing under cover, permaculture, PA).

Strategy

The adoption of agroecology principles at large scale can rely on the development of multi-purpose tools and machinery sufficiently autonomous. Albeit promising, robotic capacities need to be developed, particularly focusing on precision, variability of environment and cultures, and productivity. Such approach requires advances both in terms of definition of new farming practices and robotic developments.

HAL

  is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come

  ROMEA 2 UniLaSalle-InTerAct UP 3 INRIA-ACENTAURI 4 XLIM-REMIX 5 LAAS-RAP 6 Institut ISIR-SYROCO 7 CEA-LIST 8 LS2N-ARMEN 9 CRISTAL-Tosyma 10 IP-MACCS 11 IRL-DREAM 12 IBISC-SIAM 13 INRIA-CHROMA 14 INRIA-RAINBOW 15 INRAE-ASTRO 16 INRAE-COPAIN 17 INRAE-PRT-PEE Project scientific structuration and relationship with other national actions project.inria.fr/ninsar


Antoine De Mathelin
email: antoine.de-mathelin-de-papigny@michelin.com

Francois Deheeger
email: francois.deheeger@michelin.com

Mathilde Mougeot
email: mathilde.mougeot@ens-paris-saclay.fr

Nicolas Vayatis
email: nicolas.vayatis@ens-paris-saclay.fr

Fast and Accurate Importance Weighting for Correcting Sample Bias

) and de Mathelin et al. (2021), we derive a novel importance weighting algorithm which scales to large datasets by using a neural network to predict the instance weights. We show, on multiple public datasets, under various sample biases, that our proposed approach drastically reduces the computational time on large dataset while maintaining similar sample bias correction performance compared to other importance weighting methods. The proposed approach appears to be the only one able to give relevant reweighting in a reasonable time for large dataset with up to two million data.

Introduction

The most common assumption in a traditional learning scenario is that training data are independently and identically distributed (iid) and drawn from the same distribution as the target data. However, in real cases, the training dataset often appears to be biased with respect to the target dataset. This happens in particular in medical applications, when, for example, the age distribution of the patients does not match the distribution of the overall population. In product design, predictive models of product performances may be biased by the large amount of data corresponding to outdated products. For both previous cases, it often happens that the learner has access to the unbiased distribution, either because it is known from an external source (the age distribution in the whole population is known) or because he has access to an unbiased dataset (a sample of data of the recent products).

In this paper we assume that the learner owns a sample drawn from a source biased distribution p s (x, y) as well as a sample coming from the target marginal distribution p t (x) such that p s (x) = p t (x). Our goal is to estimate p t (y|x) or p t (y) where y is the variable of interest (e.g. patient survival expectancy for a clinical model or product performances for product design). Given the bias on the marginals, the estimation of p t (y|x) on the target domain will be biased as well.

To correct this type of sample bias, importance weighting methods can be used. These methods seek to reweight the source data to debias the marginals by looking for the weights corresponding to w(x) = p t (x)/p s (x). A successful non-parametric method in this field is the Kernel Mean matching (KMM) method [START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF] which reweights the sources in order to minimize the MMD distance between the reweighted sources and the targets [START_REF] Gretton | A kernel two-sample test[END_REF]. Although KMM is one of the first non-parametric method developed to handle sample bias, it is still used nowadays in modern sample bias correction methods for deep learning [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF] or for deriving two-sample hypothesis testing under sample bias [START_REF] Bellot | A kernel two-sample test with selection bias[END_REF]. KMM solves a quadratic problem for the minimization of the MMD with as many parameters as the number of source instances. Thus, when the number of source data is large, one faces a computational burden because of the large kernel matrix to compute. Some methods have proposed to reduce the problem in batch and to perform a KMM on each of them [START_REF] Chandra | Efficient sampling-based kernel mean matching[END_REF], [START_REF] Miao | Ensemble kernel mean matching[END_REF]. This lightens the memory, but the computational time remains important as the number of KMM sub-problems to compute increases with the number of data. Other importance weighting methods reduce the number of parameters to be optimized by linking the weights of the source instances by a parametric function as done for KLIEP [START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF] and ULSIF [START_REF] Kanamori | A least-squares approach to direct importance estimation[END_REF]. These two methods propose to write each of the weights as a linear combination of kernels centered on target points. Thus, the number of parameters is fixed (in general by selecting a hundred centers in the target domain), however, the computational cost of the pairwise distance calculations between the centers and all the source data still remains. Moreover, this large matrix of pairwise distances is used in the resolution of the gradient descent algorithm which slows the optimization. A last method, NearestNeighborsWeighting (NNW) consists in computing the weights of the source instances according to their number of target nearest neighbors [START_REF] Loog | Nearest neighbor-based importance weighting[END_REF]. This heuristic, not relying on the minimization of a distance between distributions, is quite efficient, and its computation time is generally less than its KMM counterpart. However, the search for the nearest neighbors requires the computation of pairwise distances between source and target data and despite the optimization algorithms of type KDTree [START_REF] Friedman | An algorithm for finding best matches in logarithmic expected time[END_REF] and BallTree [START_REF] Omohundro | Five balltree construction algorithms[END_REF], the method encounters computational burden for datasets with many instances and features.

Finally, all these algorithms rely on hyper-parameters to be tuned. The choice of the kernel and its bandwidth for the KLIEP and KMM methods are very important, as well as the number of nearest neighbors to consider for NNW. To choose these parameters, a cross-validation procedure using an unsupervised metric (which does not require the y data on the target domain) is mainly used such as the J-score for KLIEP [START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF], the normalized mean squared error (NMSE) between the actual and estimated density ratios for KMM [START_REF] Miao | Auto-tuning kernel mean matching[END_REF], an information criterion for ULSIF [START_REF] Kanamori | A least-squares approach to direct importance estimation[END_REF], or any divergence metric between distributions such as the linear discrepancy or the domain classifier divergence [START_REF] Ben-David | Analysis of representations for domain adaptation[END_REF], [START_REF] Deheeger | Handling distribution shift in tire design[END_REF], [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF]. This hyper-parameter selection procedure, necessary to use these methods in practice, adds to the computational time.

Considering the drawbacks of the previous mentioned methods, we propose, in this paper, a new importance weighting algorithm that scales to large datasets. Our goal is to obtain the same level of performance than KMM but with less computational time. To do so, we propose to minimize the objective of KMM, i.e. the MMD, by a batch gradient descent to avoid the memory burden of the huge kernel matrix. However, it should be underlined that optimizing the weights of the source instances individually brings no complexity gain since each source weight is only updated in its corresponding batch. Assuming w(x) = p t (x)/p s (x) continuous and regular, for two close source points x 1 x 2 , the weights will be similar w(x 1 ) w(x 2 ). Consequently, we propose to optimize at each batch the parameters θ of a parametric and continuous function W θ (x) in order to minimize the empirical MMD on the batch. Inspired from recent works of weighting adversarial neural network (WANN) [START_REF] De Mathelin | Adversarial weighting for domain adaptation in regression[END_REF], this function W θ is chosen as a neural network. The advantage of the networks is the fast update of the θ parameters by backpropagation of the gradient through the layers which is highly parallelizable [START_REF] Lecun | Deep learning[END_REF]. This avoids working with huge matrices of pairwise kernel as done in the KLIEP algorithm. We show on several datasets that this approach allows to obtain importance weighting at least as efficient as KMM in a drastically reduced time. The source code of the experiments is publicly available on GitHub3 .

Our contributions can be listed as follows:

-We derive a fast and scalable importance weighting algorithm. This is achieved by using batch gradient descent optimizing the MMD and by parameterizing the weights by a neural network. -The developed algorithm optimizes the kernel parameters of the MMD in the gradient-descent optimization and thus avoid a time consuming CV process to select it.

2 Problem Setting and Proposed Approach

Learning scenario

Given an input space X ∈ R p of dimension p > 0 and an output space Y ∈ R q with q > 0, we consider the sample bias scenario in which the learner has access to a source sample S = {(x 1 , y 1 ), ..., (x m , y m )} ⊂ X × Y drawn iid from a source distribution p s (x, y) on X × Y and a target sample T = {x 1 , ..., x n )} ⊂ X drawn iid according to a target distribution p t (x) on X . We suppose that p s (x) = p t (x) and that p t (x) is absolutely continuous with respect to p s (x). Finally, we make the covariate-shift assumption [START_REF] Bickel | Discriminative learning under covariate shift[END_REF] which states that the conditional probabilities of y|x remain unchanged for the two distributions: p s (y|x) = p t (y|x).

MMD

Let's consider φ σ : X → F σ with F σ the RKHS of Gaussian kernel k σ such that ∀x, x ∈ X , k σ (x, x ) = φ σ (x), φ σ (x ) = exp(-σ||x -x || 2 ) with σ > 0.
The Maximum Mean Discrepancy (MMD) between the source and target distributions is defined as follows:

MMD σ (p s (x), p t (x)) = E x∼ps(x) [φ σ (x)] -E x∼pt(x) [φ σ (x)] (1)
The MMD is a distance characterizing how close are the two marginal distributions p s (x), p t (x). As we consider a Gaussian kernel, MMD σ = 0 if and only if p s (x) = p t (x) [START_REF] Gretton | A kernel two-sample test[END_REF].

As our goal is to correct the sample bias between the source and target distributions with importance weighting, we aim at finding the weights w(x) ∈ R + that solve the following optimization problem:

min w:X →R+ E x∼ps(x) [w(x)φ σ (x)] -E x∼pt(x) [φ σ (x)] 2 subject to w(x) ≥ 0 ∀x ∈ X and E x∼ps(x) [w(x)] = 1 (2)
As we consider p t (x) absolutely continuous with respect to p s (x), the solution of the optimization problem ( 2) is the density ratio w(x) = p t (x)/p s (x) [START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF].

In practice, we only have access to samples {x 1 , .., x m } and {x 1 , .., x n } respectively drawn according to both distributions p s (x) and p t (x), we then consider the empirical formulation of the previous optimization problem (2) which is written:

min w∈R m 1 m 2 m i,j w i w j k σ (x i , x j ) + 1 n 2 n i,j k σ (x i , x j ) - 2 nm m i n j w i k σ (x i , x j ) subject to w i ≥ 0 ∀i ∈ [|1, m|] and 1 m m i w i = 1 (3)

Importance Weighting Network

The optimization problem (3) is a quadratic optimization problem which can be solved by gradient descent. However computing the MMD requires to compute a kernel matrix of size O((n + m) 2 ) which can cause memory burden. We propose, in this paper, to compute the MMD on small batches of size B. At each batch, we impose the constraints on the weights by taking their absolute values and dividing them by their sum. It has been shown that, although self-normalizing the weights creates a biased estimation of the MMD, the estimator is asymptotically unbiased, with the bias decreasing at a rate of O(1/B) [START_REF] Diesendruck | Importance weighted generative networks[END_REF], [START_REF] Martino | Effective sample size for importance sampling based on discrepancy measures[END_REF].

To obtain a fast update of all weights at each batch, we parameterized the weights through a neural network

W θ : X → R such that w i = W θ (x i ) for each i ∈ [|1, m|].
In this way, at each batch, the parameters θ are updated and then all the parameters w i are updated with them. Notice that the MMD estimation produced by the batch of size B is approaching the true MMD at a strong rate of O(1/ √ B) [START_REF] Gretton | A kernel two-sample test[END_REF] which comforts the idea that the update of θ at each batch will be in favor of finding the optimal weights for all x i .

It should be stressed that the MMD quantity depends on σ wich corresponds to the kernel bandwidth. In the seminal paper of KMM [START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF] the choice of σ is not clearly motivated, but a method proposed by KLIEP [START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF] consists in choosing between several predefined σ and compute the optimal weights for each σ value. The value which provides the best matching of the target distribution is finally selected. This type of selection is time consuming and requires fixing a pre-selection of σ values.

We propose, instead, to optimize the σ parameter at the same time as the weights. Inspired by the works on MMD-GAN [START_REF] Li | Mmd gan: Towards deeper understanding of moment matching network[END_REF], the kernel parameter σ is modified at each batch in order to maximize the MMD. The idea behind this choice of implementation is to increase the discriminative power of the MMD and thus reduce the risk of estimating, from finite samples, that the source and target distributions are the same when this is not the case. By maximizing over σ, we end with an alternate gradient descent-ascent algorithm, where we aim at finding a saddle point. The final optimization formulation can be written as follows:

max σ min θ B i,j |W θ (x i )W θ (x j )|k σ (x i , x j ) B i,j |W θ (x i )W θ (x j )| + 1 B 2 B i,j k σ (x i , x j ) - 2 B i B j |W θ (x i )|k σ (x i , x j ) B B i |W θ (x i )| (4)
We therefore introduce the Importance Weighting Network (IWN) which searches for the saddle points that solve the above optimization problem (cf Algorithm 1).

Related work

Instance-based domain adaptation. Our work is in line with instance-based unsupervised transfer learning or domain adaptation [START_REF] Pan | A survey on transfer learning[END_REF]. Most of the instancebased methods have already been introduced previously as KMM, KLIEP, ULSIF and RULSIF [START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF], [START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF], [START_REF] Kanamori | A least-squares approach to direct importance estimation[END_REF], [START_REF] Yamada | Relative densityratio estimation for robust distribution comparison[END_REF]. All of these methods aim to compute the source weights which minimize a distance between the input distributions like the MMD

(xi)|/ B j |W θ (xj)| ∀ xi MMD σ,θ = B i,j wiwjkσ(xi, xj) + 1 B 2 n i,j kσ(x i , x j ) -2 B B i B j wikσ(xi, x j ) Backward propagation θ ← θ -ν∇ θ MMD σ,θ σ ← σ + ν∇σMMD σ,θ
or the Kullback-Leibler. Other methods have also proposed to take into account the model used to estimate y using appropriate metrics such as the discrepancy [START_REF] Cortes | Domain adaptation and sample bias correction theory and algorithm for regression[END_REF], [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF]. Most of the unsupervised instance-based approaches make the assumption of covariate-shift [START_REF] Bickel | Discriminative learning under covariate shift[END_REF].

Importance weighting and deep learning. This work is related to existing works in importance weighting using deep learning. Recently, Fang et al. [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF] have developed a task-oriented sample-bias correction method where a KMM is performed at each batch in different depths of the neural network. In a different context from ours, Diesendruck et al. [START_REF] Diesendruck | Importance weighted generative networks[END_REF] have developed a sample bias correction method for deep generative models. In this approach, the MMD is also minimized by batch, however the weights are not parameterized but assumed to be known (e.g. a uniform proportion of classes is desired). Importance weighting methods have also been used along with deep feature transformation in partial domain adaptation [START_REF] Cao | Partial transfer learning with selective adversarial networks[END_REF], i.e. when the number or the proportion of classes differ between targets and sources. In this category of methods, the output of a domain classifier network is often used to reweight the source instances. The domain classifier is either trained in parallel to the feature transformation [START_REF] Cao | Learning to transfer examples for partial domain adaptation[END_REF], [START_REF] You | Universal domain adaptation[END_REF], [START_REF] Zhang | Importance weighted adversarial nets for partial domain adaptation[END_REF] or after it [START_REF] Park | Calibrated prediction with covariate shift via unsupervised domain adaptation[END_REF], [START_REF] Wang | Transferable calibration with lower bias and variance in domain adaptation[END_REF]. Other methods in this field consider the uncertainty of a task classifier to reweight both source and target instances during the feature transformation [START_REF] Guan | Uncertainty-aware unsupervised domain adaptation in object detection[END_REF], [START_REF] Wen | Bayesian uncertainty matching for unsupervised domain adaptation[END_REF]. These works are interesting from a computational point of view and may be seen as an alternative to MMD minimization. Finally, the weighting adversarial neural network (WANN) [START_REF] De Mathelin | Adversarial weighting for domain adaptation in regression[END_REF], explicitly proposes to use a neural network to learn the source weights minimizing a distance between distribution called the Y-discrepancy [START_REF] Mohri | New analysis and algorithm for learning with drifting distributions[END_REF]. Their approach, however, is developed in the supervised context and involves a task network fitted at the same time as the weights. Their approach is then deep learning specific. The present work generalizes this last approach as any estimator can be used once the weights are computed.

Experiments

We conduct the experiments on a synthetic dataset and 15 UCI datasets 4 [10] of various size and number of features. The experiments are conducted on a 3.3Ghz computer with 64G RAM and 24 Cores. The source code of the experiments is available on GitHub5 .

IWN Settings

The purpose of IWN is to provide a simple and fast tool to perform importance weighting. We observe that the choice of network has little incidence on the learned weights (see Section 4.5), we then arbitrarily choose a three layers neural network with 100 neurons each and a ReLU activation. This architecture is used in all experiments without fine-tuning. We choose the Adam optimizer [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF]. The optimization parameters are also fixed for all experiments to a learning rate of 0.001, a batch size of 256 and a maximal number of iterations set to 5 • 10 4 . Early stopping on the objective function is used, if the objective has not improved after 2 • 10 4 iterations, the learning is stopped.

We remind that the kernel bandwidth σ used to compute the MMD is learned in the gradient descent (cf Algorithm 1) and does not require a cross-validation process. The initial value of σ is set to 0.1 for all experiments.

Competitors Settings

We consider the following competitors which have already been introduced previously in this paper:

-KMM [START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF]. We use a Gaussian kernel and the default optimization parameters B = 1000 and = √ m -1/ √ m. The bandwidth σ of the kernel is selected in the set {10 (i-4) } i∈[|0,8|] with unsupervised cross-validation using the linear discrepancy [START_REF] Mansour | Domain adaptation: Learning bounds and algorithms[END_REF].

-KLIEP [START_REF] Sugiyama | Direct importance estimation with model selection and its application to covariate shift adaptation[END_REF]. We use a Gaussian kernel and a learning rate of 0.01 with a maximum number of iterations of 1000 as parameters for the gradient descent. These parameters have been selected to obtain an important decrease of the objective function with a fast convergence for most of the datasets. The bandwidth σ of the kernel is selected in the set {10 (i-4) } i∈[|0,8|] with the native Likelihood Cross-Validation (LCV) procedure of KLIEP.

-NNW [START_REF] Loog | Nearest neighbor-based importance weighting[END_REF]. The nearest neighbors are computed with the optimized Near-estNeighbors algorithm of scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] which optimizes the computation approach between brute force and KD-Ball-Tree in function of the number of features and samples in the dataset. The Euclidean distance is used and the number of nearest neighbors for averaging is chosen in the set {1, 5, 10, 20, 50, 100} with unsupervised cross-validation using the linear discrepancy.

The implementation of the competitors are provided by the ADAPT library6 [START_REF] De Mathelin | Adapt: Awesome domain adaptation python toolbox[END_REF]. The library also provides the metric for the cross-validation processes.

To offer the best chance to the competitors, the parameters selection with cross-validation are performed with parallel computing for KMM and NNW. For KLIEP, the parallel computing is not available in ADAPT and thus not used, this explains why its computational time is higher than the others.

Synthetic dataset

We consider the synthetic experiment, inspired from [START_REF] Cortes | Domain adaptation and sample bias correction theory and algorithm for regression[END_REF], where p s (x) is a mixture of M = 10 Gaussians, i.e. p s (x) = M k=1 π k N (µ k , 0.2)(x) where the centers µ k ∈ R N are drawn according to the distribution N (0, 1) in R N , the ratios π k are set such that π k = 0.8/(M -1) ∀k = M and π M = 0.2. The output variable is written y = β T k x for any x drawn according to the k th Gaussian. The coefficients β k ∈ R N are drawn according to the distribution N (0, 1) in R N . The target distribution p t (x) is drawn according to the same mixture of Gaussians but with ratios π k = 0.1/(M -2) ∀k < M -1, π M -1 = 0.1 and π M = 0.8. We suppose that the learner has access to a sample of size n of source labeled instance {(x i , y i )} 1≤i≤n drawn according to the source distribution p s (x, y) on R N and an unlabeled set of size n, {x j } 1≤j≤n drawn according to the target distribution p t (x) on R N . An illustration of the problem for dimension N = 2 is given in Figure 1.A.

We conduct several experiments on this synthetic dataset. First, we fit IWN for the setting N = 32, n = 10000. We make 4000 batch updates with batch size 256, at each of them, we use the weights w i returned by the weighting network to fit a weighted Ridge regression model of parameters β on the set {(x i , y i , w i )} 1≤i≤n , we then record the mean absolute error (MAE) of this model on the target dataset:

1 n i |β T x i -y i |.
We also record, at each batch, the computed MMD on the batch and the "true" MMD computed with the whole samples. We also record the current value of the parameter σ which is also updated during the optimization (see Section 2.3). We report the results of this experiment on Figure 1.B, 1.C, 1.D. We first represent the final importance weights returned by the weighting network at the end of the 4000 iterations in Figure 1.B. As we can observe, the learned weights are very close to the true sampling probability. On Figure 1.C, we report the evolution of the recorded MAE in plain orange, the batch and true MMD in blue and the value of σ in green. We also report, for comparison with "MAE (IWN)", the MAE of a Ridge model fitted with uniform weights: "MAE (Unif)" and the MAE of the model fitted with the weights obtained using KMM: "MAE (KMM)". We observe that the importance weighting produced by IWN helps to learn the task on the target domain as the error decreases of 20% compared to the error of the model fitted with uniform weights. Concerning the recorded MMD, we observe that both the batch and "true" MMD decrease very fast, but an offset remains between the two due to the estimation error made with finite samples. We then see on the zoom of Figure 1.D that the error decreases very fast as well as the MMD. After 100 iterations, the MMD is minimized and the target error of IWN is on the same level than the error produced by KMM. We notice that the MAE increases a little after some iterations which may indicates some overfitting effect of the weighting network. This observation argues for the use of early stopping based on the evolution of the MMD. We finally remark, in Figure 1.C, that the σ parameter becomes relatively stable around 0.15 after some iterations which comforts the idea that the parameter can be efficiently set during the optimization thanks to the adversarial learning (see Section 2.3). We could however argue, that the increase of the target error after the 100 th iteration is correlated to the increase of σ from 0.1 to 0.15. This is a plausible explanation as σ is updated in order to make the MMD more discriminative which may provoke overfitting. This is a limitation of the proposed approach which we propose to study in future work.

We then conduct several experiments to observe the evolution of the computational time in function of the sample size and the number of features. We first fix the number of features to N = 128 and vary the number of samples from 100 to 2 • 10 5 and report the computational time in Figure 1.E. Then, we fix the number of samples to n = 20000 and vary N from 16 to 4096 and report the results in Figure 1.F. We observe, on these two Figures, that for the number of samples has a stronger impact on the computational time than the number of features. The two methods KMM and NNW have a quadratic complexity O(n 2 ) which is well reflected in Figure 1.E. The computational time of KLIEP evolves linearly due to the fixed number of target centers considered. Figure 1.E clearly demonstrates the computational supremacy of IWN compared to the other methods. It should be pointed out that the quality of the importance weighting is similar between methods, the corresponding scores are reported in appendix.

UCI datasets

We perform the experiments on several UCI datasets [START_REF] Dua | UCI machine learning repository[END_REF] with different sizes and dimensions. We record the computational time used by each importance weighting method for computing the source importance weights (cf Figure 3). For each dataset, the score is computed with a Ridge model fitted with the importance weights and without importance weighting. The ratio between the two scores is reported in Figure 2.

To evaluate the importance weighting methods we consider different kind of sample bias following the setting of [START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF]: The training set is built by taking n data with replacement using the sampling bias as probabilities of selection. The target set is the original dataset without selection bias. For each experiment, we apply the following preprocessing: standard scaling of the numerical inputs (using the mean and standard deviation of the unbiased inputs) and one-hot-encoding of the categorical inputs. The dimension p of the input space corresponds to the dimension after preprocessing.

-
To evaluate the weighting scheme of each method, we fit a Ridge model with trade-off parameters α selected by leave-one-out process between values {10 (i-4) } i∈[|0,8|] . For regression datasets, we compute the mean absolute error (MAE) on the target testing set (the original dataset without bias). We then fit another Ridge model with the uniformly weighted biased source data and compute the MAE on the target set. We can then compute a score ratio for each method as follows:

Score Ratio = i |β T IW x i -y i | i |β T U nif x i -y i | (5)
where β IW , β U nif are respectively the coefficients of the Ridge models fitted with the importance weights and the uniform weights. We repeat each experiment 10 times and report the results of the experiments with the sample bias on the input features in Figures 2 and3, the standard deviation over the 10 repetitions are given in appendix. The first Figure presents the score ratios computed with Eq (5). We observe that the quality of the weighting scheme provided by IWN is competitive with other methods. IWN is in the top 2 best ratios for all experiments except one. Even more impressive are the computational time of IWN compared to other methods (Figure 3), IWN provides a fast computation of no more than 25 seconds for samples of size < 5 × 10 5 . Whereas the other methods failed to provide importance weights in a reasonable time for samples above 5 × 10 4 samples and > 100 features. The same observations are made on Table 1 which reports the summary results of the experiments conducted on the same datasets with a sample bias on the outputs.

Impact of Network Architecture and Batch Size

Finally, we study the impact of the network architecture and the batch size on the solution of IWN. We conduct the experiments on the CTscan dataset7 [START_REF] Graf | 2d image registration in ct images using radial image descriptors[END_REF] biased through the sample bias on the input features described previously. First, we fix the batch size to 256 and vary the number of hidden layers of the weighting network from 0 to 4 and the number of neurons per layer between [START_REF] Dua | UCI machine learning repository[END_REF]100,300].

Then, we fix the number of hidden layers to 3 and the number of neurons to 100 and vary the batch size on a geometric scale of ratio 4 from 16 to 4096. We repeat each experiment 10 times and report the means and standard deviations of the scores in Table 2. We observe that the architecture of the network has little impact on the score, however, we observe a slight improvement of the score between the simplest architectures and the more complex ones (0.88 for 0 hidden layer and 0.85 for 4 layers and 300 neurons). The impact of the batch size is more significant on the performance of IWN, enlarging the batches produce better corrections of sample bias. This is due to the more accurate estimation of the MMD made with larger batch. However, increasing the batch size comes with an increase of the computational time as shown in the last column of Table 2. 2. Summary of the study on the impact of weighting network architecture and batch size. Standard deviation over the 10 repetitions are given in brackets.

Neural

Conclusion

This work introduces a novel algorithm for importance weighting called Importance Weighting Network and shows that sample biases can be efficiently corrected by fitting a weighting neural network with the MMD as loss function. This approach appears to provide very competitive results with state-of-theart instance-based domain adaptation methods for a minimal cost in term of computational time.

Fig. 1 .

 1 Fig. 1. Visualization of the synthetic experiments. The corresponding experimental settings are: (A) n = 10000, N = 2, (B, C, D) n = 10000, N = 32, (E) n ∈ [100, 2 • 10 5 ], N = 128, (F) n = 2 • 10 4 , N ∈ [16, 4096]

  Sample bias on the input features: the source training set is biased on the input features X with a gaussian weighting on the first component of the PCA of mean m + (µ -m)/3 and standard deviation (µ -m)/8 with m, µ the respective minimum and mean of the first PCA component. -Sample bias on the output features: the source training set is biased on the output features y with a weighting on the first component of the PCA defined as exp(3(y 1 -1))/(1 + exp(3(y 1 -1))) with y 1 the first PCA component of y.

Fig. 2 .

 2 Fig.2. Score ratio for the experiments with the sample bias applied on input features. In each column, the values correspond to the ratios between the mean absolute error (MAE) of the corresponding methods (IWN, NNW, KLIEP and KMM) and the MAE of the Uniform Weighting approach where no reweighting is performed. The MAEs are computed on the target dataset with a Ridge model fitted on the reweighted source data. The two first columns n and p are respectively the number of sample and number of features of the dataset. The lightest colors correspond to the best ratios. The experiment stopped after 500 seconds are marked with Nan.

Fig. 3 .

 3 Fig. 3. Computational times (in second) for the experiments with the sample bias applied on input features. The two first columns n and p are respectively the number of sample and number of features of the dataset. The computational time are given in second. The lightest colors correspond to the lowest computational time. The experiment stopped after 500 seconds are marked (>500).

  Algorithm 1 Importance Weighting Network Inputs: Source and target datasets SX , T , initial bandwidth σ, batch size B, neural network W θ , learning rate ν Initialization: Fit W θ with loss L = i ||W θ (xi) -1|| 2 while stopping criterion is not reached do Take batches {x1, ..., xB} ⊂ SX and {x 1 , ..., x B } ⊂ T Forward propagation wi ← |W θ

Table 1 .

 1 ). Summary of the results of the output sample bias experiments (extensive results are reported in appendix).

	method Avg Score Ratio Avg Rank Avg Comp. Time (in sec.)
	IWN	0.9	2.0	8.06
	NNW	0.92	2.37	182.81
	KLIEP	1.03	2.93	223.16
	KMM	0.87	2.7	290.01

https://github.com/antoinedemathelin/Importance-Weighting-Network

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

https://github.com/antoinedemathelin/Importance-Weighting-Network

https://github.com/adapt-python/adapt

https://archive.ics.uci.edu/ml/datasets/Relative+location+of+CT+slices+ on+axial+axis


The coin toss, the queen, and the princess Bridget Copley, SFL (CNRS/Paris 8) ENS Conditionals, 7 April 2020

1 A causal puzzle about statives and eventives in conditionals

Suppose that there is a country called Clavarel where the queen is selected from amongst the eligible candidates by a series of coin tosses. In the particular situation we are interested in, it so happens that if the coin comes up heads, Yolanda becomes the queen; and if the coin comes up tails, she does not. Suppose also that if someone becomes the queen, any daughters she may have consequently become princesses; moreover, there is no other way to become a princess of Clavarel. Further suppose that Yolanda has exactly one daughter, named Xanthippe. 1 In such a context, we can see that (1a) is true, while (1b) is false. What's wrong with (1b)?

(1)

(2) a. If Xanthippe is the princess, Yolanda is the queen. P (x) ⇒ Q(y) b. If Xanthippe is the princess, Yolanda becomes the queen.

P (x) ⇒ Become Q(y)

Attempted analyses . . .

(3) a. In all the worlds where Xanthippe is the princess, Yolanda becomes the queen. b. ∀w s.t. P (x)(w) : Q(y)(w)

(4) a. In all the world-time pairs where Xanthippe is the princess, Yolanda becomes the queen. b. ∀ w, t s.t. P (x)( w, t ) : Become(Q(y))( w, t )

(5)

For all predicates of entities Q, entities y, world time pairs w, t , w, t , such that t is (just?) after t, let : [START_REF] Dowty | Word meaning and Montague Grammar[END_REF])

Become(Q)(y)( w, t ) := 1 iff ¬Q(y)( w, t ) and Q(y)( w, t ) (cf.
But where does the causal flavor come from in (6) (compare with (2a)) ?

(6) If Yolanda becomes the queen, Xanthippe becomes the princess.

And what's wrong (if anything) with (7a) (and compare to (7b))?

(7) a. If Yolanda becomes/is the queen, Xanthippe is the princess. b. If Yolanda becomes the queen, Xanthippe is laughing.

It seems clear that whatever is causing differences in the properties of these conditionals, including presence or absence of the causal reading, it is the difference between the verb become and the verb be. The major such difference is called variously "the eventive-stative distinction" or "eventuality type", and is one of several distinctions of "Aktionsart" or "situation aspect" [START_REF] Smith | The parameter of aspect[END_REF].

The big question Is the puzzle about time or about causation?

• Temporal relations can in part be recovered from causal relations.

• Verb phrases (especially eventive verb phrases) are organized in terms of causal relations (e.g. [START_REF] Dowty | Word meaning and Montague Grammar[END_REF][START_REF] Pustejovsky | The generative lexicon[END_REF][START_REF] Ramchand | Verb meaning and the lexicon: A first-phase syntax[END_REF][START_REF] Croft | Verbs: Aspect and causal structure[END_REF][START_REF] Copley | A force-theoretic framework for event structure[END_REF].

• We can get the causal relation from the verb meaning, whereas with world-time pairs, we have to add it on, but only (in this data set) for eventive verbs in the consequent (and perhaps eventive-like readings of be). In any case it is sensitive to the choice of verb, which might be surprising under a time-based analysis.

Hypothesis:

The puzzle is about causation.

To-do list: Compositionality, the difference between eventivity and stativity, map event semantics to causal models, define two kinds of update (learning and happening) and a simple dynamic conditional.

Compositionality

The meaning of the parts of the sentence + how those meanings are "glued" together = the meaning of the sentence [START_REF] Frege | Sense and reference[END_REF] Types The meanings that will be composed (meanings of words, phrases) can have atomic or recursively defined derived types.

( 3.2 Some apparent "eventives" in English are actually stative

It turns out that very often in English, predicates that we expect to be eventive actually behave like statives instead. These stative readings of apparently eventive predicates fall into several categories: generic/habitual readings, futurate readings (where there is a futureoriented, "planned" or "settled" reading but no future morphology, [START_REF] Lakoff | Presupposition and relative well-formedness[END_REF][START_REF] Vetter | Someone solves this problem tomorrow[END_REF][START_REF] Dowty | Word meaning and Montague Grammar[END_REF][START_REF] Kaufmann | Conditional truth and future reference[END_REF][START_REF] Copley | The plan's the thing: Deconstructing futurate meaning[END_REF][START_REF] Copley | Dispositional causation[END_REF], and what we will call "storytelling readings", where the reference is to what happens in a story, play, etc. (cf. the "director's reading" in [START_REF] Ritter | The function of have[END_REF]). The fact that generic/habitual readings are stative is well-known, while the behavior of futurate and storytelling readings has not been much talked about (but see [START_REF] Copley | Dispositional causation[END_REF]).

( What follows from this is that habitual/generic readings, futurate readings, and storytelling readings are just statives; or more precisely, that the highest predication in their structure is stative.

(17) "None-of-the-above" readings do not behave like statives (to a speaker within the story, so not a storytelling reading) a. Yolanda must become the queen. b. #If you care to know, Yolanda becomes the queen.

True eventives are not assertable

True eventives can appear in antecedents but are not assertable. ( 18 Assertability and non-assertability correlate nicely with eventivity and stativity with the simplest (verb) phrases, but as more material is added, the assertability/non-assertability distinction sticks around, while the "states" get more and more abstract. This general effect looks something like a grammatical bleaching effect [START_REF] Meillet | L'évolution des formes grammaticales[END_REF][START_REF] Traugott | Meaning-change in the development of grammatical markers[END_REF][START_REF] Sweetser | Grammaticalization and semantic bleaching[END_REF].

Assertability requires more than a mere predication; it additionally requires an act of something like endorsement or commitment from a mind (e.g. [START_REF] Recanati | Perspectival thought: A plea for (moderate) relativism[END_REF]).

On this hypothesis, what goes wrong with our unassertable eventives is that they are not predicates of situations, i.e. they are not type s, t , so assertion, which applies a predicate of situations to the current situation, is not available.

What type are eventives, then?

Events are the type that gives transitions between two states: s×s. This transition gets an energetic causation interpretation, matching with our intuitions in trying to say where causal readings arise in these conditionals. See [START_REF] Copley | A force-theoretic framework for event structure[END_REF], [START_REF] Copley | Force dynamics[END_REF] for further discussion. Eventives are predicates of type s×s, t .

Causal models

A causal model is a directed acyclic graph used to represent causal influences Pearl (2000), [START_REF] Pearl | The book of why: the new science of cause and effect[END_REF]. The relations in the causal model behave as in Pearl (2000), where a relation between nodes such as (A, B) conveys that the second node "listens" to the first node. That is, the second node's value is sensitive to first node's value. It is very important to remember that this relation is not always paraphraseable by the main verb cause; better words are influence or affect. The absence of such a relation between nodes conveys that there is no influence from one node to another.

The graph in (33), for instance, is meant to characterize a context where a captain orders two soldiers to shoot a prisoner. The captain has influence on the soldiers, and the soldiers' actions have influence on whether the prisoner dies or not. Similarly, one could represent causal influences on health with a diagram such as the one in (34). Note that although each additional cigarette per day decreases the value of whatever measure of health we use, the arrow between that node and the health node is correctly drawn.

(34) Cigarettes per day Servings of fruits and vegetables per day Health For our puzzle, we have a very simple causal model:

(35) C Q P (36)
C := 1 if heads, 0 if tails Q := 1 if Yolanda is the queen, 0 if Yolanda is not the queen P := 1 if Xanthippe is the princess, 0 if Xanthippe is not the princess (37)

C Q P a. 1 1 1 b. 0 0 0 c. 1 0 0 d. 1 1 0
"Seeing" vs. "doing"? Pearl's formal tool for talking about causation is the "dooperator". The do-operator erases all causal influences on the node in question and changes the value of the node to the specified value, as shown in ( 38): (38) do(X = x): erase all incoming arrows into X and change the value of X to x.

Looking at the difference between seeing and doing in this system, one might hypothesize that this distinction corresponds to the distinction in English between statives and eventives respectively. Could it be leveraged to solve our puzzle? No. The do-operator does not correspond to eventive predicates become the princess or become the queen as in (2b). For suppose it did. Then if the conditional is again treated as , the meaning of (2b) would be expected to be as follows:

(39) All situations where do(P (x) = 1) are situations where do(Q(y) = 1)

That is, all cases where we erase the arrows into the P (x) node and set the value of the P (x) node to 1 are cases where we erase the arrows into the Q(y) node and set it to 1.

But even then, we do not explain our puzzle. We do get (2b) to be false, but for the wrong reason. Making the reasonable assumption that we have the freedom, as erasers of arrows and setters of values, to apply the do-operator to whatever node we want, it is indeed false, as desired, that any case where we do(P (x) = 1) is a case where we do(Q(y) = 1). But although we get the right result, this reason for getting that result is exactly wrong. The problem with (2b) is not that there is no arrow between Q(y) and P (x); it is that there is an arrow going into P (x) in the causal model, but somehow the conditional seems to require an arrow of causal influence to go the other way. In short, the do-operator cannot help us understand here how eventive predicates relate to causal readings in conditionals, because it erases one of the very things that we need to use, namely that incoming arrow.

In the paper but not in the handout: we need to map event semantics to causal models so we can go back and forth between them. The causal model will tell us if a particular event is possible.

5 How we will solve the puzzle Statives (as in being) and eventives (as in becoming) have two different types and involve two distinct modes of update.

(40) a. stative predicate: s, t , which is a predicate of situations; maps to nodes in causal models b. eventive predicate: s×s, t , which is a predicate of ordered pairs of situations (i.e., a predicate of a "relation"); maps to arrows in causal models

Accordingly, there will be two ways for the speaker to update the current situation: learning, which is an update with a predicate of situations, and happening, which is an update with a predicate of relations between situations.

(41)

a. learning = update with a predicate of situations b. happening = update with a predicate of a relation between situations

With a very basic dynamic semantics meaning for conditionals, and using the causal model to index a causal sequence of situations, I will argue that the event in the consequent is, literally, the causal relation that yields the causal reading in (2b).

5.1 Dynamic semantics [START_REF] Heim | On the semantics of definite and indefinite noun phrases: UMass dissertation[END_REF][START_REF] Kamp | A theory of truth and semantic representation[END_REF][START_REF] Groenendijk | Two theories of dynamic semantics[END_REF] 3. Update (learning) the successor situation of s with the information that Yolanda became queen previous to the time of the successor of s. This is possible, so the conditional is true.

  walked in. Xanthippe left. b. I walked in. Xanthippe was there.

  . If you care to know, Abelard drinks beer at the end of the book.

	(15)	"None-of-the-above" readings do not behave like statives
		a. Yolanda must get sick tomorrow.	no epistemic reading
		b. #If you care to know, Yolanda gets sick tomorrow.
	(16)	a. It must rain tomorrow.	no epistemic reading
		b. #If you care to know, it rains tomorrow.

12) Generic/habitual readings behave like statives a. Clavarelian nobles must drink beer. b. If you care to know, Clavarelian nobles drink beer. (13) Futurate readings behave like statives a. Xanthippe must drink beer with Zelinda tomorrow. b. If you care to know, Xanthippe drinks beer with Zelinda tomorrow. (14) Storytelling readings behave like statives a. (I haven't read to the end of the book, but from what I've read,) Abelard must drink beer at the end of the book. b

  Finally, while in antecedents, true eventives are possible, it seems that in the consequents of simplest conditionals, as long as we resist the temptation to add will or similar, true eventives are not possible. If Zelinda drinks beer tomorrow), Xanthippe drinks beer tomorrow. 'If there's a plan for Zelinda to drink beer tomorrow, there's a plan for Xanthippe to drink beer tomorrow.' 'There's a plan such that if Zelinda drinks beer tomorrow, Xanthippe drinks beer tomorrow.' #'If Zelinda happens to drink beer tomorrow, Xanthippe will happen to drink beer tomorrow.'3.4 Assertability has to do with typeSo, what is it that distinguishes unassertable antecedents from assertable antecedents in English? I want to suggest that it is type. That is, the reason that true eventives are unassertable in English is a formal reason; specifically, they are unable to take a situation argument, because they are of the wrong type to do so.

	(25)	Futurate reading
	) (19) ((26) True eventive a. If it rains tomorrow. . . b. #It rains tomorrow. True eventive a. If Yolanda gets sick tomorrow. . . b. #Yolanda gets sick tomorrow. Turning an eventive into a stative
		s, t
	(20)	a. If Xanthippe is there. . .	P	P	P P
		b. Xanthippe is there. s×s, t , s, t			s×s, t
	(21) (27)	a. If Zelinda drinks beer. . . a. Xanthippe is writing a letter.
		b. Zelinda drinks beer. b. Xanthippe must be writing a letter.
		c. If you care to know, Xanthippe is writing a letter.
	(22)
	(28)	a. Xanthippe has been writing a letter.
		b. Xanthippe must have been writing a letter.
		c. If you care to know, Xanthippe must have been writing a letter.
	(29)	a. #Oh look-it'll rain.
		b. Oh look-it's going to rain.
	(30)	a. #If you care to know, it'll rain.
		b. If you care to know, it's going to rain.
	(24)	Generic/habitual reading
	(If Zelinda drinks beer,) Xanthippe drinks beer. Past tense is interesting . . .
		a. 'If Zelinda habitually drinks beer, Xanthippe habitually drinks beer.
	(31)	b. 'Generally, if Zelinda drinks beer, Xanthippe drinks beer." a. Xanthippe left.
		c. #'If Zelinda happens to drinks beer, Xanthippe will happen to drink beer.' b. Xanthippe must have left. epistemic reading possible
		c. If you care to know, Xanthippe must have left.

a. If Xanthippe drinks beer with Zelinda tomorrow. . . b. Xanthippe drinks beer with Zelinda tomorrow. (23) a. If Abelard drinks beer at the end of the book. . . b. Abelard drinks beer at the end of the book.

  for arbitrary situations s, s , sRs just in case all basic predications mentioning s of the form p(x)(s) are such that the truth value of p(x)(s) is equal to the truth value of p(x)(s ). If Xanthippe is the princess, Yolanda is the queen. 1. Update current situation s with information that Xanthippe is the princess. 2. Look on causal model to see what situation(s) s could be. 3. Update that situation with the information that Yolanda is the queen. This is possible; conditional is true. (47) If Xanthippe is the princess, Yolanda becomes the queen. 1. Update (learning) current situation s with information that Xanthippe is the princess. 2. Look on causal model to see what situation(s) s could be. 3. Update (happening) that situation with the event that Yolanda becomes queen. This means that Yolanda is not queen in s but is queen in the successor of s; the (52) If Xanthippe becomes princess, Yolanda became queen. 1. Update (happening) the current situation s with the event that Xanthippe becomes princess. This means that Xanthippe is not princess in s, but she is in the successor of s. 2. Look at causal model to see what situation s could be.

	: Assertions of propositions in dynamic
	semantic frameworks update the context they are uttered in; they are "context change
	potentials".
	(42) Compatibility/accessibility relation R: (43) Notation: "1

e " is the first member and "2 e " is the second member of an ordered pair of an ordered pair e (44) Two kinds of update: a. learning: s[ϕ s, t ] M := ιs : sRs and ϕ(s ) b. happening: s[ϕ s×s, t ] M := ιs ∈ S M : [ιe ∈ S M × S M : [2 e = s and ϕ(e)]] (45) s[if ϕ, ψ] M := s[ϕ] M [ψ] M 6 Solving the puzzle (46)

Crown by Alfa Design, coin toss by Ariel Kotzer, Girl Smile by Llisole, baby girl by Milinda Courey, all from the Noun Project.

event is that transition. This is not possible; conditional is false.

7 Other examples (48) If Yolanda becomes the queen, Xanthippe becomes the princess. 1. Update (happening) current situation s with the event that Yolanda becomes queen. That means that in s Yolanda is not queen, and in the successor situation of s she is.