Florian Combes

Ricardo Fraiman

Badih Ghattas

Subsampling under distributional constraints

Keywords: Optimal sampling, numerical models, nearest neighbours, Kolmogorov-Smirnov

Some complex models are frequently employed to describe physical and mechanical phenomena. In this setting we have an input X in a general space, and an output Y = f (X) where f is a very complicated function, whose computational cost for every new input is very high. We are given two sets of observations of X, S 1 and S 2 of different sizes such that only f (S 1 ) is available. We tackle the problem of selecting a subsample S 3 ∈ S 2 of smaller size on which to run the complex model f , and such that distribution of f (S 3 ) is close to that of f (S 1 ).

We suggest three algorithms to solve this problem and show their efficiency using simulated datasets and the Airfoil self-noise data set.

Introduction

Numerical models are often used to model physical or mechanical phenomena [START_REF] Brunton | Machine learning for fluid mechanics[END_REF] [START_REF] Brunton Steven | Special issue on machine learning and data-driven methods in fluid dynamics[END_REF]. Such models are used to generate some scenarios using the solution of partial derivative equations (PDEs). Their input is often composed of border and initial conditions denoted by X, and their output f (X) may be the values of some variables which may be multidimensional and depend on space and time. The use of such models consists in solving complicated PDEs, and each generated scenario corresponds, in the machine learning paradigm, to an inference for a new input X, thus the computation of f (X). In practice, this computation can take several hours and even days depending on the complexity of the model f and on the granularity of time and space chosen to compute the solution. In this context, machine learning and deep learning algorithms may be used to replace such complicated models by learning an approximation of f , often based on small samples. In what follows we consider the subsampling [START_REF] Wu | Sampling Theory and Practice[END_REF] problem in this framework.

Suppose we have an iid sample S 1 = {X 1 , . . . , X n1 }, with the same distribution as X, of data defined on a space, that we will assume to be just a complete separable metric space (E, ρ). We apply to each of these observations a very complicated, expensive and deterministic smooth function f : E → R, which we will consider as black box. The pair (S 1 , f (S 1 )) may also be seen as the result of a large establishment survey.

Next, another large iid sample S 2 of size n 2 is provided with the same distribution as the first one, but for which the values f (S 2 ) are not provided.

The main problem we address is how to provide a subsample S 3 ⊂ S 2 of size n 3 smaller than n 2 and such that the distribution of f (S 3 ) will be close to that of f (S 1 ). The idea is that in the future the values of f (X) will be only computed for S 3 . This problem appears quite often in practice, in particular in some industrial applications, semi-supervised learning, neuroscience, big data regression and clustering, among many other problems. At first glance this problem is that of a classical subsampling. It can be approached by sampling techniques used in surveys, or more recent techniques adapted to unsupervised ( [START_REF] Mak | Support points[END_REF]) or supervised ( [START_REF] Haiying | Information-based optimal subdata selection for big data linear regression[END_REF], [START_REF] Haiying | Optimal subsampling for large sample logistic regression[END_REF], [START_REF] Joseph | Supervised compression of big data, Statistical Analysis and Data Mining[END_REF]) situations. These approaches are tailored to sample from within a population (a large sample, accessible or not). They may be used partially to solve our problem which is semi supervised.

Other approaches consider also the sampling problem with different type of constraints and under uncertainties ( [START_REF] Amri | A sampling criterion for constrained bayesian optimization with uncertainties[END_REF]). In Design of experiments ( [START_REF] Fedorov | Theory of Optimal Experiments Designs[END_REF]) the same problem is faced with other specifications; the sample S 1 is in general of very small size (∼ 15) and the target sample S 3 is built sequentially, observations are sampled one by one. Moreover, the set S 3 is multidimensional space, and not a fixed sample. In our context, we need to sample from S 2 with constraints related to S 1 . This manuscript is organized as follows. In Section 2 we fix some notation that will be used throughout the manuscript and we specify the framework of the problem to be solved. In Section 3 we introduce three different algorithms with different alternative procedures to solve the problem. In Section 4 we provide sharp bounds for the probability of being far from the target distribution, which motivates the last algorithm, which is based on these results. Section 5 is devoted to illustrate, with some simulated experiments, the behaviour of the proposed algorithms. Lastly, in Section 6 some concluding remarks are provided.

The problem setting

Let S 1 = {X 1 , . . . , X n1 } be a set of n 1 iid random elements in a complete separable metric space (E, ρ), with the same common distribution µ as X, and

S 2 = {X ′ 1 , . . . , X ′ n2 }
a second iid sample of size n 2 with the same distribution µ. Let f : E → R, a deterministic function which is very complicated and hard to compute (which we may think as a regular black box). The unknown distribution of f (X) will be denoted by F . We have a sample

Y 1 =: {Y i = f (X i ) for i = 1, . . . n 1 }
of the images of the first sample S 1 . Images for S 2 are not available.

With this information on hand, we want to find a subsample S 3 ⊂ S 2 , with size n 3 << n 2 , such that the empirical distribution of f (S 3 ) := {f (X j ) : X j ∈ S 3 } will be close to the distribution of f (X 1 ).

We will consider several different approaches to this problem throughout the manuscript, with different complexities. Some of them do not make use of the sample Y 1 , while others do.

Let µ 1 be the empirical distribution of S 1 , and given a subset S 3 ⊂ S 2 , write µ 3 for its empirical distribution. If f is regular, we can look for a subset S 3 for which

d(µ 1 , µ 3 ), (1)
is minimum among all possible subsets of size n 3 , and d is a distance that metrizes weak convergence, like the Prokhorov distance. However, this translates the problem into another one which is computationally hard.

In what follows, the corresponding empirical probability measures on the space (E, ρ) are denoted by µ ni , i = 1, . . . , 3 while the ones corresponding to f (X) ∈ R are denoted by F ni i = 1, . . . , 3.

Remark 1. We will use in some of the algorithms that follow the notions of distinct and extended nearest neighbours. More precisely, for each data point in S 1 we will look for the nearest point in S 2 to it. It may happen that the set of the nearest neighbours of observations in S 1 from S 2 (having respectively n 1

and n 2 observations) may contain duplicates from S 2 . If we simply remove these duplicates, the remaining set of neighbours will be of size less than n 1 . We call this set the distinct nearest neighbours. The extended nearest neighbours of S 1 from S 2 refers to the set obtained by adding to the distinct nearest neighbours, further neighbours from S 2 (neighbours which are further away), i.e. in that case we look for the second nearest neighbour, and so on.

Some Algorithms

We first propose a simple solution which does not make use of Y 1 . Then we will introduce two algorithms that make use of the output sample Y 1 in different ways. The idea is to get a subsample Y 3 from Y 1 whose distribution is close to that of Y 1 , consider its inverse image f -1 (Y 3 ), which is a subsample of S 1 , and look for its neighbours in S 2 . The selection of the optimal subsample Y 3 is based on the results given in Section 4.

A simple extended nearest neighbours approach

Consider S 1 = {X 1 , ...X n1 } and S 2 = {X ′ 1 , ...X ′ n2 } with n 2 > n 1 .
Compute the nearest neighbours of S 1 in S 2 , let d 1 , ..., d n1 be their ordered distances and j(1), ...j(n 1 ) their indices.

If two observations from S 1 , X i and X j , have the same nearest neighbour, say X ′ l , at distances d i and d j , such that d i < d j , than X ′ l will be kept as a neighbour of X i and for X j we take its second nearest neighbour from S 2 . If more than two observations have the same nearest neighbour, we will need to explore further away neighbours.

We end with the set S 3 = {X ′ 1 , . . . , X ′ n1 } and its Prokhorov distance to µ 1 will be smaller than d (n1) which will be small if n 2 is large and n 2 >> n 1 . Indeed, d (n1) will converge to 0 over any compact set K ⊂ E.

Algorithm 1: Extended nearest neighbours.

S 1 = [X 1 , ....., X n1 ]; S 2 = [X ′ 1 , ....., X ′ n2 ]; S 3 = Extended nearest neighbours of S 1 in S 2 ;
This simple approach is based on the idea that observations from S 2 close to S 1 , should have images through f close to the images of S 1 .

A histogram based approach

In the previous section we did not make use of Y 1 = f (S 1 ). Suppose now that we are interested in P(f (X) ∈ I), where I ∈ R is an interval, or a finite union of disjoint intervals in R, say I 1 , . . . , I k . We look for a subsample S 3 ⊂ S 2 , with size n 3 << n 2 , such that we can approach P(f (X) ∈ I). We start by considering the set

A n1 (I) := {X j ∈ S 1 : f (X j ) ∈ I}.
Next, given ϵ > 0, define

B n1 (I) := B(A n1 (I), ϵ) := Xj ∈An 1 (I) B(X j , ϵ),
and

S 3 (ϵ) = {X i ∈ S 2 : X i ∈ B(A n1 (I), ϵ)}.
The heuristic idea in this case is to look for a subsample S 3 such that the histogram of f (S 3 ) is close to the one built up with the intervals I of the distri-105 bution of f (X), assuming that the function f is smooth.

In this case, the size of S 3 (ϵ) is random and depends on ϵ. From an asymptotic point of view, we will need that ϵ → 0 slowly enough, since we can think of the problem as estimating the distribution of X 1 |f (X 1 ) ∈ I. Some theory can be derived along this line. An alternative is to fix n 3 and choose ϵ in order 110 to have a subsample of size approximately n 3 . A special case of this approach is implemented in Algorithm 2 and consists in using bins obtained by adjusting a histogram to f (S 1 ).

Algorithm 2: Histogram based algorithm.

S 1 = [X 1 , ....., X n1 ]; S 2 = [X ′ 1 , ....., X ′ n2 ]; S 3 = {∅} ;
Build a histogram for f (S 1 ) using J bins I j and consider the sets

A j = {X ∈ S 1 : f (X) ∈ I j }; for j in 1..J do Z = distinct neighbours of A j in S 2 ; Append Z to S 3 ;

Next, define

W n,k = min C k ∈Cn ∥F k -F n-k ∥ (2)
and

Ĉk = argmin C k ∈Cn ∥F k -F n-k ∥, (3)
where ∥F -G∥ = sup t |F (t) -G(t)| denotes the usual supremum distance.

In other words, this amounts to using the classical Kolmogorov-Smirnov (KS) ( [START_REF]The kolmogorov-smirnov test for goodness of fit[END_REF]) statistic to assess the distance between two empirical distributions or, when F is known, the distance between the empirical distribution and the theoretical underlying distribution F .

Given m, L and t > 0, we want to lower bound the following probability

P( min C k ∈Cn ∥F k -F n-k ∥ ≤ t), (4)
and to provide an algorithm to find Ĉk , for a given family C n .

Alternatively, we will also consider another version, denoted by V n,k . It is obtained by replacing the KS statistic in ( 2) and ( 3) with the Cramer-von

Mises discrepancy,

M(H 1 , H 2 ) = R (H 1 (t) -H 2 (t)) 2 dH 2 (t).
That is, we will use the statistic

V n,k = min C k ∈Cn R (F k (t) -F n-k (t)) 2 dF n-k (t) = min C k ∈Cn M(F k , F n-k ). ( 5
)
Remark 2. The relation between m (the size of the subsample of each C k )

and L, the size of C n where we will perform the search, must take into account two different problems. A larger m will make the approximation better, but our purpose is to look for small values of m relative to n 2 . On the other hand, this will increase L and therefore the computation time.

We start by considering the unrealistic situation where the distribution F is known. In the case where it is unknown it will be replaced by F n-k . Note that when F is continuous (which we will assume throughout the paper), the statistic √ mW n,k has a continuous distribution not depending on F , due to the distribution-free property of the Kolmogorov-Smirnov statistic. This is also the case for mV n,k .

The case where F is known

In order to lower bound the probability given in (4) we first recall the well known Dvoretzky-Kiefer-Wolfowitz (DKW) [START_REF] Dvoretzky | Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator[END_REF] inequality.

P(∥F k -F ∥ ≤ t) ≥ 1 -2e -2mt 2 . ( 6
)
Since the subsets in C n are disjoint, we have independence, and therefore

P( min C k ∈Cn ∥F k -F ∥ ≤ t) = 1 -P(∥F k -F ∥ > t) L ≥ 1 -2e -2mt 2 L , (7)
which will be small if e -2mt 2 < 0.5 (that is, mt 2 > ln(2) 2 ) for L large. For instance, if L = 10000, m = 890 and t = 0.02 the bound is 1.

The corresponding result for the Cramer-von Mises discrepancy follows directly from the fact that

{mM (F k , F ) ≥ t} ⊂ { √ m∥F k -F ∥ ≥ √ t}.

The case where F is unknown

In the above development, we assumed that the distribution F was known.

The whole approach can be adapted to the case where F is continuous but unknown, relying on the distribution-free properties of the statistics we use.

We assume throughout the continuity of F .

Observe that ∥F k -F n-k ∥ is nothing but the two-sample KS-statistic which is distribution free (whenever F is continuous).

P( min

C k ∈Cn ∥F k -F n-k ∥ ≤ t) = 1 -P( min C k ∈Cn ∥F k -F n-k ∥ > t) ≥ 1 -P( min C k ∈Cn (∥F k -F ∥ + ∥F -F n-k ∥) > t) = 1 -P(∥F k -F ∥ > t/2) L + P(∥F n-k -F ∥ > t/2) L ≥ 1 -2e -mt 2 L/2 + 2e -(n-m)t 2 L/2 . ( 8
)
Figure 1 shows the behaviour of the obtained lower bounds for simulated Gaussian datasets using m = 1000 and L = 1000, which shows the good accuracy of inequalities (7 -left) and (8 -right).

A partition based algorithm

From the previous result we obtain k << n 1 for which the distribution of

F k is close to the distribution of F n-k .
Assuming that the function f is smooth enough we propose an algorithm with the following steps: Let Ĉk = {Y i1 , . . . , Y ik } be the minimizer obtained in the one dimensional space.

160

Consider a Ck = {X i1 , . . . X ik } ⊂ S 1 fulfilling f ( Ck ) = Ĉk .
For each X ij ∈ Ck , find its nearest neighbour in the set S 2 . If there are ties, we put the data multiple times.

A detailed description of the algorithm is given below.

Algorithm 3: Partition based algorithm. The partitions in this algorithm may be obtained at random or using a randomized clustering algorithm like k-means. Note that the size of the obtained subsamples in this case are fixed and equal to m.

S 1 = [X 1 , ....., X n1 ]; S 2 = [X ′ 1 , ....., X ′ n2 ]; S 3 = {∅} ; Y i = f (X i ),

Some experiments

In this section we provide the results of some simulations for the three algorithms proposed; extended nearest neighbours (algorithm 1), histogram based (algorithm 2), and partition based (algorithm 3). As mentioned above, our objective is to find a subsample S 3 ⊂ S 2 for which the distribution of the set f (S 3 ) will be close to that of f (S 1 ), without using the values of f (S 2 ).

To do this, we will apply each algorithm to data generated from various distributions, varying sample sizes (n 1 and n 2 ) as well as the dimension d of the inputs. The values of these parameters are fixed as follows: n 1 = 100, except for Algorithm 3 where we also experimented with the values n 1 = 400, Once we get the output subset S 3 from any algorithm we use the Kolmogorov-Smirnov test to compare the observed empirical distributions of f (S 1 ), with that of f (S 3 ) which is not available in general. We report the values of the test statistic as well as the corresponding p-values, averaged over K = 100 runs for each configuration.

Tables 1 and2 give the results for Algorithm 1, Tables 3 and4 for Algorithm 2, and Tables 5 and6 for Algorithm 3.

The three algorithms obtain a subset S 3 for which the distribution of f (S 3 ) is very close to that of f (S 1 ) according to the Kolmogorov test (with a significance value of 0.01), for all the values of n 2 , except for the case of the Gaussian distribution in dimension 20. In all cases, the p-values decrease with the dimension, as expected. The values of the test statistic are often lower with Algorithm 1;

this is due to the fact that Algorithm 1 outputs systematically a subsample S 3 of exactly the same size as that of S 1 , whereas the two other algorithms give smaller subsamples.

The only case where the obtained subsamples are not satisfactory was for the Gaussian distribution in dimension 20. Using the truncated Gaussian distributions (over [-1, 1] and [-2, 2]) improved the results. We think that the actual version of our algorithms might fail for tailed distributions in high dimensions.

Distribution Table 6: Average size of n 3 , Kolmogorov-Smirnov test between S 1 and S 3 for truncated Gaussian distribution and for graphs (Algorithm 3).

n 2 d = 1 d = 2 d =

Comparing to other sampling approaches

Our algorithms aim to construct a subsample S 3 from S 2 using information or constraints related to S 1 . Existing subsampling approaches cannot achieve this task but may be used as an alternative to some steps in our algorithms.

We will use such approaches to obtain a subsample S 3 directly form S 2 without 220 considering neither S 1 or Y 1 in algorithm 1, and as an alternative in algorithms 2 and 3 to select a subsample from S 1 . To do that, we consider two recent unsu-pervised approaches; the "support points" [START_REF] Mak | Support points[END_REF] and the "D-optimality" sampling [START_REF] Haiying | Information-based optimal subdata selection for big data linear regression[END_REF].

Support points 225

In the Support points algorithm, we have a fixed distribution F and we look for a set of observations the best representing F . Those points are obtained by minimizing an energy distance (Székely and Rizzo 2004)

E(F, F n ) = 2 n n i=1 E||x i -Y || - 1 n 2 n i=1 n j=1 E||x i -x j ||,
where Y ∼ F . The minimization of the energy distance can be formulated as a difference-of-convex program. For real valued random variables, energy distance is nothing but twice Cramer-von Mises discrepancy. For our setting the empirical version of E is optimized

Ê({x i }, {y m }) = 2 nN n i=1 N m=1 ||y m -x i || 2 - 1 n 2 n i=1 n j=1 E||x i -x j || 2 ,
where {y m } is a sample from F . The algorithm for the support points using one sample batch is defined as follows [START_REF] Mak | Support points[END_REF] Sample

D (0) = {x (0) i } n i=1 i.i.d. from {y m } N m=1
Set l = 0, and repeat until convergence of D (l) :

-For i = 1, .., n do parallel:

230 Set x (l+1) i ← M i D (l) ; {y m } N m=1 ,.
-Update D (l+1) ← {x (l+1) i

} n i=1 , and set l ← l + 1.

Return the converged point set D (∞) where

M i {x ′ j } n j=1 ; {y m } N m=1 = q -1 x ′ i ; {y m } N m=1   N n n j=1;j̸ =i x ′ i -x ′ j ||x ′ i -x ′ j || 2 + N m=1 y m ||x ′ i -y m || 2   , and
q x i ; {y m } N m=1 = N m=1 ||x i -y m || -1 2 .
Distribution Selection We replace this process by either sampling from Y 1 using support points and D-optimality, either sampling directly from S 1 .

n 2 d = 1 d = 2 d =
Tables 7 and8 give the results obtained when using SP over X in on histogram based algorithm tables 9 and 10 give the results when apply SP and D-optimality over Y.

Using SP gives better results when compared to the other approaches for all the simulations models mainly in dimension lower than 5. D-optimality is less efficient except for large dimensions (20) where its performance is close to that of SP. These observations are correct whether the selection is done over X or Y.

Moreover, the SP and the D-optimality behave like the other algorithms with the normal distribution, i.e. they are less good on the normal distribution than on the truncated normal distributions.

For the uniform distribution, SP gives very good results, while the D-optimality is poor except for dimension 20 where both give the same results.

For graphs, SP works less well than for the other distributions in small dimensions (< 20). On the contrary the D-optimality works well even in small dimension.

Conclusion

We have considered the problem of selecting a new subsample S 3 to use for inference with a model f whose output is available only for a small subsample 305 S 1 . The subsample should be small, and the distribution of f (S 3 ) should be close to that of f (S 1 ). Three algorithms were considered. The first one, an extended nearest neighbours approach, makes no use of the sample f (S 1 ), while the other two (histogram based and partition based approaches) make use of it in different ways. For the last one a mathematical consistency result was given.

310

All the algorithms showed a good behaviour when analysed through simulation using different distributions and different dimensions for the input, except for the Gaussian case in high dimensions. The results obtained on a real dataset showed that all the algorithms behave as expected.

Our algorithms are currently extended to the case where the input data are time series and the output is multidimensional.

end 4 .

 4 Bounds for the probability of being far from a target distributionIn what follows we provide sharp bounds for the probability of being far from a target distribution, when we make use of the sample Y 1 as in Algorithm 2. These results will motivate our proposal of Algorithm 3 given in subsection 4.3 below. Given a large sample of iid random variables Y 1 := {Y 1 , . . . , Y n } with distribution F , we look for a subsample of Y 1 , of much smaller size, and which is as close as possible in distribution to the original one. Suppose we fix the size m of the desired subsample. Searching within the class C of all possible subsamples of size m taken from Y 1 is in general unfeasible in practice from a computational point of view. Thus, we will consider a smaller class defined as follows. We start by considering a partition C n of the subset ⊂ {1, . . . , n} into L disjoint subsets C k ⊂ {1, . . . , n}, k = 1, . . . , L each of size m. We denote by F n the empirical distribution of Y 1 , F k the empirical distribution of the set {Y j : j ∈ C k }, and F n-k the empirical distribution of the set {Y j : j ∈ {1, . . . , n} \ C k }.

Figure 1 :

 1 Figure 1: Bound from Equations 7(left) and 8 (right) for m = 1000 and L = 1000.

  with empirical distribution F ; Partition the set Y 1 , .., Y n1 into L clusters of size m s.t. n = mL; Denote the clusters by C k , and their complements by C n-k = S 1 \ C k ; Find the partition Ĉk which minimizes ∥F k -F n-k ∥; Find the subset Ck = {X i1 , . . . X ik } ⊂ S 1 fulfilling f ( Ck ) = Ĉk ; for i in Ck do Z = nearest neighbour of i in S 2 ; Append Z to S 3 ; end 165 10

n 2 ∈

 2 {200, 1000, 5000}, d ∈ {1, 2, 50} except for graphs where d = 5 is used instead of d = 1. We use the following distributions; the coordinates are independent for d > 1: beta distribution B(0.5, 0.5). Gaussian distribution, N (0, 1). uniform distribution, U[-1, 1]. truncated Gaussian distribution, where the intervals of truncation are [-1, 1] and [-2, 2] . We denote it by T N (1) and T N (2). uniform distribution over graphs, where d in the number of nodes in the graph, and probability for each edge is 0.5. Note that the graphs we generate are neither oriented nor acyclic. They are represented in our runs by their adjacency matrix reshaped into a d 2 length vector. For the function f : E → R we used f (x) = ||x 2 || + <a.x> d where a is the fixed real sequence ranging from -0.5 to 0.5 with step 1 d .

Table 3 :

 3 Average size of n 3 , Kolmogorov-Smirnov test between S 1 and S 3 for beta, Gaussian and uniform distribution (Algorithm 2).

				d = 1			d = 2			d = 20
	Distrbution	n 2	n 3	Stat Pvalue	n 3	Stat Pvalue	n 3	Stat Pvalue
		200	47	0.07	0.99	47	0.09	0.89		0.26	0.11
	T N (1])	1000	48	0.06	0.99	47	0.07	0.97		0.30	0.03
		5000	48	0.07	0.98	48	0.07	0.99		0.29	0.04
		200	47	0.07	0.98	48	0.09	0.89		0.28	0.04
	T N (2)	1000	48	0.06	0.98	48	0.08	0.97		0.32	0.03
		5000	47	0.06	0.99	48	0.07	0.98		0.32	0.01
				d = 5			d = 10			d = 20
		200	46	0.13	0.63	48	0.10	0.84		0.16	0.37
	Graphs	1000	45	0.08	0.97	47	0.08	0.97		0.11	0.81
		5000	45	0.04	1	46	0.13	0.58		0.09	0.93

Table 4 :

 4 Average size of n 3 , Kolmogorov-Smirnov test between S 1 and S 3 for truncated Gaussian distribution and for graphs (Algorithm 2).

			d = 1	d = 2	d = 20
	Distribution	n1	n2
			n3 Stat Pvalue n3 Stat Pvalue n3 Stat Pvalue
			200 50 0.10	0.86 50 0.11	0.82 0.17	0.43
		100	1000 50 0.09	0.85 50 0.10	0.83 0.17	0.38
			5000 50 0.08	0.92 50 0.09	0.88 0.16	0.43
	B(0.5, 0.5)
			200 50 0.08	0.91 50 0.09	0.85 0.15	0.39
		400	1000 50 0.08	0.92 50 0.07	0.93 0.14	0.40
			5000 50 0.07	0.93 50 0.08	0.93 0.14	0.41
			200 50 0.09	0.90 50 0.11	0.76 0.30	0.04
		100	1000 50 0.09	0.88 50 0.10	0.84 0.32	0.01
			5000 50 0.09	0.91 50 0.10	0.85 0.32	0.01
	N (0, 1)
			200 50 0.08	0.91 50 0.09	0.83 0.29	0.02
		400	1000 50 0.08	0.93 50 0.08	0.88 0.32	0.00
			5000 50 0.08	0.93 50 0.08	0.92 0.30	0.00
			200 50 0.10	0.84 50 0.10	0.83 0.15	0.51
		100	1000 50 0.09	0.88 50 0.10	0.81 0.16	0.46
			5000 50 0.09	0.90 50 0.09	0.91 0.15	0.46
	U[-1, 1]
			200 50 0.08	0.91 50 0.09	0.86 0.15	0.43
		400	1000 50 0.08	0.93 50 0.08	0.89 0.14	0.39
			5000 50 0.07	0.95 50 0.07	0.94 0.14	0.44

Table 5 :

 5 Average size of n 3 , Kolmogorov-Smirnov test between S 1 and S 3 for beta, Gaussian and uniform distribution (Algorithm 3).

			d = 1	d = 2	d = 20
	Distrbution	n1	n2
			n3 Stat Pvalue n3 Stat Pvalue n3 Stat Pvalue
			200 50 0.10	0.87 50 0.11	0.78 0.27	0.08
		100	1000 50 0.09	0.88 50 0.10	0.80 0.29	0.03
			5000 50 0.09	0.88 50 0.09	0.88 0.28	0.05
	T N (1)
			200 50 0.08	0.91 50 0.09	0.82 0.27	0.05
		400	1000 50 0.08	0.94 50 0.08	0.89 0.27	0.03
			5000 50 0.07	0.94 50 0.08	0.92 0.27	0.02
			200 50 0.10	0.85 50 0.11	0.77 0.31	0.04
		100	1000 50 0.09	0.86 50 0.10	0.82 0.33	0.02
			5000 50 0.09	0.91 50 0.09	0.87 0.31	0.02
	T N (2)
			200 50 0.08	0.90 50 0.09	0.83 0.29	0.03
		400	1000 50 0.08	0.93 50 0.08	0.87 0.30	0.01
			5000 50 0.07	0.94 50 0.08	0.91 0.30	0.01
			d = 5	d = 10	d = 20
			200 50 0.11	0.85 50 0.13	0.67 0.14	0.51
		100	1000 50 0.10	0.83 50 0.10	0.90 0.13	0.56
			5000 50 0.13	0.61 50 0.17	0.28 0.11	0.80
	Graphs
			200 50 0.10	0.79 50 0.09	0.85 0.21	0.06
		400	1000 50 0.12	0.59 50 0.08	0.91 0.10	0.75
			5000 50 0.09	0.88 50 0.15	0.23 0.10	0.74

Table 7 :

 7 Average size of n 3 , Kolmogorov-Smirnov test between S 1 and S 3 for beta, Gaussian and uniform distribution (Algorithm 2 on X).

	20

Table 8 :

 8 Average size of n 3 , Kolmogorov-Smirnov test between S 1 and S 3 for truncated Gaussian distribution and for graphs(Algorithm 2 on X).

Table 9 :

 9 Average size of n 3 , Kolmogorov-Smirnov test between S 1 and S 3 for beta, Gaussian and uniform distribution (Algorithm 2 on Y).

					d = 1			d = 2			d = 20
	Distribution	Selection	n 2	n 3	Stat Pvalue	n 3	Stat Pvalue	n	Stat Pvalue
			200	50	0.04	1	50	0.07	0.98		0.18	0.34
	T N (1)	SP	1000 5000	50 49.98	0.03 0.02	1 1	50 50	0.05 0.04	1 1		0.21 0.21	0.18 0.21
			200	50	0.26	0.02	50	0.24	0.04		0.18	0.35
		D-opt	1000	50	0.26	0.02	50	0.26	0.02		0.20	0.21
			5000	50	0.26	0.02	50	0.26	0.02		0.21	0.19
									0.02		0.30	0.02
					d = 5			d = 10			d = 20
			200	11	0.22	0.72	24	0.15	0.75		0.14	0.66
		SP	1000	12	0.25	0.67	22	0.16	0.76		0.13	0.70
	Graphs		5000	9	0.29	0.58	21	0.17	0.69		0.14	0.65
			200	47	0.10	0.82	50	0.11	0.72		0.13	0.65
		D-opt	1000	47	0.16	0.43	50	0.10	0.79		0.12	0.67
			5000	47	0.20	0.19	50	0.11	0.73		0.13	0.65

Table 10 :

 10 Average size of n 3 , Kolmogorov-Smirnov test between S 1 and S 3 for truncated Gaussian distribution and for graphs(Algorithm 2 on Y).

	We will use Support Points (SP) and D-optimality as alternatives in the
	histogram based approach (algorithm 2). Recall that in algorithm 2 we use
	a histogram to partition Y 1 , and sample 50% of the observations within each
	bin; we consider then their inverse image by f which is a subsample from S 1 .

Table 11 :

 11 Average results for airfoil data over K = 100 runs, varying values of n 1 and n 2 .

	Algorithm	n1	n2	n3 Stat Pvalue
		100 1403 100 0.11	0.58
	Extended nearest neighbours
		400 1103 314 0.04	0.89
		100 1403	50 0.13	0.61
	Histogram based algorithm
		400 1103 198 0.07	0.61
		100 1403	50 0.13	0.62
	Partition based algorithm
		400 1103	50 0.11	0.62
		100 1403	50 0.13	0.63
	Over X
		400 1103	50 0.11	0.62
	Support Point
		100 1403	50 0.12	0.70
	Over Y
		400 1103	50 0.10	0.71
		100 1403	50 0.12	0.71
	Over X
		400 1103 200 0.07	0.49
	D-optimality
		100 1403	50 0.10	0.88
	Over Y
		400 1103 200 0.12	0.13

Let

2 . M may be written

It can be remarked that M i is composed of two terms; the second term is a weighted average of the y m sample with weights inversely proportional to the distance of y m to x ′ i ; Support points may be applied in our problem either to the input sample (S 1 or S 2 ) or to the output Y 1 . The obtained sample from support points is composed of arbitrary observations which are not part of the original sample.

So when applying this approach we take as a final sample, the nearest neighbors of the obtained support points.

D-optimality

In [START_REF] Haiying | Information-based optimal subdata selection for big data linear regression[END_REF] the authors suggest a procedure for subsampling for linear regression; however, the selection procedure is unsupervised and based on D-optimality.

If x = {x 1 , x 2 , ..., x N } is the data set at hand, such that x i ∈ R p , and n is the size of the desired subsample, let r = n/2p, and x •,j = {x ij , i = 1..N } the observations of the j th coordinate λ of X. The process of sampling is the following:

Let S n = ∅ For j = 1.., p -Let X j the set observations from X having the r largest values and the r smallest values within x •,j -Let S n = S n ∪ X j , and X = X \ X j .

The disared subsample is S n Distribution Selection

Stat Pvalue B(0.5, 0.5) SP

Airfoil self-noise data set

The airfoil self-noise dataset [START_REF] Dua | UCI machine learning repository[END_REF] In order to test our algorithms with this dataset we split it randomly into two disjoint parts S 1 of size n 1 and S 2 of size n 2 . We tried two values for n 1 : 100 and 400. The output values for S 2 are used only to assess the performance of our algorithms. The process was repeated K = 100 times and the results are reported in Table 11.

Note that compared to the simulations, the function f is unknown but the values of the output variable are considered as the observation of f (X).

The results are satisfactory on most of the algorithms, accept the D-optimality.

Moreover we notice that for Support Points the fact of sampling over Xor Y give similar results. Finally, we can see that Support Points on Y and Histogram based algorithm give the same results as Extended nearest neighbours but with twice less elements in S3.


Arnault Pachot
email: arnault.pachot@etu.uca.fradelaide.kissi@uca.fr

Adélaïde Albouy-Kissi

Benjamin Albouy-Kissi
email: benjamin.albouy@uca.fr

Frédéric Chausse
email: frederic.chausse@uca.fr

Identify Potential Diversification to Companies through Collaborative Filtering

Keywords: JEL Codes, L25 Firm Performance: Size, Diversification, and Scope CCS CONCEPTS, Recommender systems, Network economics, Economics, Sustainability, Economic impact Sustainable production, COVID19 and Economy, Econometric modeling, Resilience Index

The industrial fragility of European countries has been a major issue during the latest economic and health crises. Governments have become aware of the partial desertification of our industry but also of the astonishing capacity of the players to reinvent themselves, innovate to find solutions, and show resilience. Everywhere in our society, shaken from all sides, we have seen the emergence of diverse initiatives to overcome the shortages of necessities. In this study, we focus on the ability to diversify from the point of view of a company, which literature has shown to be a major factor in improving industrial resilience. We are interested in the proximity of industrial know-how between two product classes in the HS nomenclature, independent of the country or territory observed. Our goal is to evaluate the ability of a firm that produces product A to adapt its production to produce product B. We analyzed thousands of French companies' websites to label the products they manufacture. From the collected data we built a Recommender System (RS) for diversification based on collaborative filtering (CF). The results show that our Recommender System outperforms methods from macro data analysis, such as co-export analysis on the Product Space or semantic analysis of nomenclatures. We formalize an indicator of a company's agility based on its diversification capabilities. Finally, this work offers new perspectives on the formalization of a measurable Resilience Index (RI).

INTRODUCTION

In this study, we focus on the ability to diversify from the point of view of a company, which appears in the literature to be a factor for improving industrial resilience [START_REF] Agarwal | Evaluation of supply chain resilience index : A graph theory based approach[END_REF][START_REF] Martin | Regional economic resilience, hysteresis and recessionary shocks[END_REF].

To measure this adaptive capacity, we are interested in the proximity of industrial know-how between two classes of products in the HS nomenclature, regardless of the country or territory observed. We need to evaluate the ability of a company that produces product A to adapt its production to produce product B.

After presenting existing methods based on macro-economic approaches, we will describe a new methodology that exploits the observation of real co-productions of manufacturers to model proximities by collaborative filtering (CF). We will study the 𝑘-nn and matrix factorization approaches in a context of implicit data. We will compare the recommendations obtained with the state-of-the-art.

Finally, we formalize a new agility indicator that allows us to evaluate the diversification capacity of a given industrial company. We conclude with the perspectives offered by this indicator in the automatic measurement of a company's Resilience Index (RI).

PREVIOUS WORK

We will present the measures of proximity proposed in the literature. These measures are derived from macroeconomic data and are based on the analysis of exports by country or nomenclatures. We will then present the extent to which the literature considers the diversification capacity of firms in assessing their resilience.

Proximity in the Product Space

The work done by [START_REF] Hausmann | The Atlas of economic complexity : Mapping paths to prosperity[END_REF][START_REF] Hausmann | A Commodity Classification Framework Based on Machine Learning for Analysis of Trade Declaration[END_REF] on economic complexity has defined a measure of proximity between products. This measure is based on a study of the export baskets of each country. A graph built with classes of products linked to each other according to their proximity is called the Product Space. The results obtained for each country can be consulted in the Atlas of Economic Complexity 1 . The proximity 𝜙 ! ! ,! " between the products 𝑝 # and 𝑝 $ is calculated as follows.

Let 𝑋 %! be the exports of product 𝑝 by country 𝑐, then the Revealed Competitive Advantage (RCA) that country 𝑐 has for product 𝑝 can be expressed as a function of exports according to the formula of [START_REF] Balassa | Trade Liberalisation and « Revealed » Comparative Advantage[END_REF]:

𝑅𝐶A &' = * X &' ∑ X &'
Product Space has been used to assess countries' diversification capabilities [START_REF] Alshamsi | Optimal diversification strategies in the networks of related products and of related research areas[END_REF][START_REF] Boschma | Institutions and diversification: Related versus unrelated diversification in a varieties of capitalism framework[END_REF][START_REF] Zhu | How to jump further and catch up? Path-breaking in an uneven industry space[END_REF] or with a view to diversifying companies (Pachot et al., 2021a), in particular to guide towards the production of greener products [START_REF] Hamwey | Mapping Green Product Spaces of Nations[END_REF][START_REF] Huberty | Green exports and the global product space : Prospects for EU industrial policy[END_REF][START_REF] Mealy | Economic complexity and the green economy[END_REF][START_REF] Perruchas | Specialisation, diversification and the ladder of green technology development[END_REF].

Measurement of proximities between products based on the semantic analysis of nomenclatures

Natural Language Processing (NLP) techniques are used in the literature to perform automatic categorizations in HS nomenclature [START_REF] Hausmann | A Commodity Classification Framework Based on Machine Learning for Analysis of Trade Declaration[END_REF][START_REF] Luppes | Classifying Short Text for the Harmonized System with Convolutional Neural Networks[END_REF][START_REF] Spichakova | Application of Machine Learning for Assessment of HS Code Correctness[END_REF]. In a previous work, we built a vector space with Word2vec to characterize the semantic link between class descriptions of the HS nomenclature [START_REF] Pachot | Production2Vec : A hybrid recommender system combining semantic and product complexity approach to improve industrial resiliency[END_REF]. Word2Vec represents each word in a distributed way as a vector. Learning is done from specialized neural networks [START_REF] Bengio | A Neural Probabilistic Language Model[END_REF] or a similar approach [START_REF] Collobert | Natural Language Processing (almost) from Scratch[END_REF]Mikolov, Chen, et al., 2013;Mikolov, Sutskever, et al., 2013). The Word2Vec model can be used in two variants to make a context (skip-gram) or word (CBOW) prediction. In addition to capturing syntactic and semantic information, the vectors produced by Word2Vec have geometric properties (Mikolov, Sutskever, et al., 2013) which allow larger blocks of information (such as sentences and paragraphs) to be represented by combining vectors together. Word2Vec has also shown an amazing ability to capture word concepts by providing the ability to perform translations from simple linear transformations [START_REF] Mikolov | Exploiting Similarities among Languages for Machine Translation[END_REF].

The Skip-gram method seeks to maximize the average logarithmic probability of prediction of words of the sequence 𝑤 # , … 𝑤 ( with respect to each other. Let 𝑘 be the size of the learning window and 𝑛 the size of the sequence. The function is defined as follows:

1 𝑛 E F E log 𝑝I𝑤 )*+ J 𝑤 ) K , +-., L ( )-#
In this model, each word 𝑤 is associated with two vectors of learnable parameters, 𝑢 / and 𝑣 / . The probability of predicting 𝑤 ) by knowing 𝑤 + is computed from 𝑢 / and 𝑣 / , in a softmax function, with 𝑉 representing the vocabulary size:

𝑝I𝑤 ) J 𝑤 + K = 𝑒 0 # $ .2 # % ∑ 𝑒 0 & .2 # % 3 4-5
This gives a minimization problem, solved by the hierarchical softmax [START_REF] Morin | Hierarchical Probabilistic Neural Network Language Model[END_REF]. In [START_REF] Pachot | Production2Vec : A hybrid recommender system combining semantic and product complexity approach to improve industrial resiliency[END_REF], the vector space was used to measure the proximities between the vectors of each product. Since 1 https://atlas.cid.harvard.edu nomenclatures are intended to standardize and structure information, special care was taken in writing the class descriptions to limit ambiguities. This makes them particularly suitable for automated semantic processing.

For each 5387 classes of the HS nomenclature, a vector 𝜈 ! representing the product concept 𝑝 in the vector space Ε was computed. The vector 𝜈 ! is constructed from each vector word that appears in its class description in the HS nomenclature. The vector 𝑣 ! is calculated by averaging the vectors of each word 𝑤 ) that its class description contains. Thus, the distance between the products corresponds to the cosine similarity of their vectors in 𝐸. Let 𝑣 ! $ and 𝑣 ! % be the vectors associated with the products 𝑝 ) and 𝑝 + respectively, then we express the distance between these two products by the following equation:

Ψ ! $ ,! % (𝜏) = 𝑣 ! $ ⋅ 𝑣 ! % J𝑣 ! $ J X𝑣 ! % X

Measuring the Resilience Index of a company

Organizational resilience is defined as the ability to bounce back from a disruption [START_REF] Sheffi | A Supply Chain View of the Resilient Enterprise[END_REF], the ability to return to the original or a new, more desirable state after experiencing a disruption [START_REF] Carvalho | Supply chain redesign for resilience using simulation[END_REF], or the ability to cope with disruptions and contingencies in advance through strategic awareness and linked operational management of internal and external shocks [START_REF] Annarelli | Strategic and operational management of organizational resilience : Current state of research and future directions[END_REF].

A systematic review of research on Supply Chain (SC) resilience is presented by [START_REF] Al Naimi | A systematic mapping review exploring 10 years of research on supply chain resilience and reconfiguration[END_REF]. The level of resilience of a company is represented by the Resilience Index. Agility is an enabler having a positive influence over SC resilience [START_REF] Christopher | Building the Resilient Supply Chain[END_REF], and it is defined as the "Ability to sense the dynamic market changes and react quickly in order to meet customers' needs and prevent losses" [START_REF] Agarwal | Evaluation of supply chain resilience index : A graph theory based approach[END_REF][START_REF] Ali | Where is supply chain resilience research heading? A systematic and co-occurrence analysis[END_REF][START_REF] Kumar | An integrated Delphi -fuzzy logic approach for measuring supply chain resilience : An illustrative case from manufacturing industry[END_REF].

COLLABORATIVE FILTERING RECOMMENDER SYSTEM

We use the production data extracted from the websites of the manufacturers. We have a correspondence file indicating for each company 𝑐 a list of 𝑚 products (𝑝 # , ⋯ , 𝑝 6 ) of the HS nomenclature observed on its website.

Building the data set

We have a list of 6519 French companies on which we have entrusted the ethical platform of data labelling Isahit2 with the task of carrying out a manual labelling of each website. The task consisted of the following:

-On one hand, determine if a website of the company exists.

-If a website exists, consult the main pages, and choose, in the HS nomenclature (version 2017, on 4 digits), the products which are manufactured by the company. The labelling was carried out on 6153 companies with a website. On each website, products were observed according to the following distribution: We constructed a sparce matrix of interactions by considering companies as users 𝑢 ) , who interacted with products 𝑝 + corresponding to the list of products we detected on their website. We obtained 9133 unique interactions. The matrix covers 880 different product classes with a sparsity rate of 0.188%. The number of classes in the 2017 4-digit HS nomenclature is 1222, so our dataset covers 72.01% of the total nomenclature.

Measurement of proximities between products by Item-Item Nearest Neighbor

We first applied a 𝑘-nn method to construct a matrix of proximities between each product class. We reserved 20% of the data for cross-validation, and we measured recall@k prediction scores with 𝑘 ∈ [5,10]. Our metric consists of counting the number of correct recommendations among the 𝑘 recommended products. We obtained the following scores on the validation sample. This RS is not adapted to perform online predictions because of complexity issue in 𝑂(𝑛 $ ), but it gives excellent prediction scores. This first experimentation allows us to have a robust measure of proximity between industrial know-how.

Matrix factorization recommender system

Matrix factorization [START_REF] Koren | Matrix Factorization Techniques for Recommender Systems[END_REF] is a representation of the data in a latent reduced space, which will serve as a model for making predictions in this reduced space with constant dimensions. It is a model-based approach that consists of decomposing the sparce matrix of interactions into a product of several matrices.

Let 𝐼 be the number of users, 𝐽 the number of products, and 𝐾 the number of latent factors. Let us suppose that we wish to carry out an approximation of the interaction's matrix 𝑅, called 𝑅 b , in the form of a product of two matrices 𝑈 of dimension 𝐼 × 𝐾 and 𝑉 of dimension 𝐽 × 𝐾:

𝑅 " ≈ 𝑈 ⋅ 𝑉 !
Then a user's prediction about a product can be expressed as follows:

𝑟 "# ( = 𝑢 $ ! 𝑣 % ! + 𝑢 $ " 𝑣 % " … 𝑢 $ # 𝑣 % # 𝑟 "# ( = . 𝑘 = 1 & 𝑢 $ # 𝑣 % # = 𝑢 $ ! 𝑣 %
Let 𝑢 ) be the latent factor associated with user 𝑖, and 𝑣 + the latent factor associated with product 𝑗. We define 𝑢 ), as the affinity of a user 𝑖 for the concept 𝑘, and 𝑣 +, as the affinity of a product 𝑗 with the concept 𝑘. The principle of this method is to learn the values of the latent factor matrices 𝑈 and 𝑉 by comparing the actual interactions 𝑟 )+ with the predicted values 𝑟 78 h . Let ℜ be the set of interactions. We define the learning error of an interaction 𝑒 )+ = 𝑟 )+ -𝑟 78 h , and the average error with the quadratic error function 𝐽:

J = 1 2 . 3𝑒 $% 5 ' ($,%)∈ℜ = 1 2 . 6𝑟 $,% -. 𝑢 $ # 𝑣 % # & -./ 8 ' ($,%)∈ℜ
We will therefore look for the values of 𝑈 and 𝑉 that minimize the loss function. To minimize the loss function, we apply a gradient descent after having randomly initialized the weights of the matrices 𝑈 and 𝑉. At each step, the gradient descent will consist of performing two series of partial derivatives on the error # $ 𝑒 ),+ $ , relative to 𝑈 and 𝑉, to determine the gradient of the loss function at the point (𝑖, 𝑗). Finally, we obtain two matrices 𝑈 and 𝑉 that allow us to predict the unknown value of an interaction, whatever the user and the product. The prediction of user 𝑖 and product 𝑗 is expressed as follows:

𝑟 "# ( ≈ 𝑢 $ ! 𝑣 %
The classical methods of matrix factorization must be adapted to deal with implicit data [START_REF] Hu | Collaborative Filtering for Implicit Feedback Datasets[END_REF], which is our case. Indeed, we do not have a preference score between companies and products, but only Boolean information to indicate the presence or not of a product on the site of an industry. We use the Implicit3 library to experiment with various implicit CF methods.

We follow the method described by Johnson [START_REF] Johnson | Logistic Matrix Factorization for Implicit Feedback Data[END_REF] as a factorization of the interaction matrix 𝑅 into 2 lower-dimensional matrices 𝑋 (×: and 𝑌 6×: , with 𝑓 as the number of latent factors.

Let 𝑙 0) represent the interaction of user 𝑢 with product 𝑖, let β ) and β + , respectively, be the biases on users and products, then the probability of 𝑙 0) is computed by the sum of the inner product of user and item latent factor vectors and user and item biases.

𝑝I𝑙 0) J𝑥 0 , 𝑦 ) , β ) , β + K = 𝑒𝑥𝑝I𝑥 ) 𝑦 + ; + β 0 + β ) K 1 + 𝑒𝑥𝑝(𝑥 0 𝑦 ) ; + β 0 + β ) )
This minimization problem is solved by performing an alternating gradient ascent [START_REF] Das | Google news personalization : Scalable online collaborative filtering[END_REF]. The partial derivatives for computing the user vectors and their biases are as follows:

∂ ∂𝑥 0 = E α𝑟 0) 𝑦 ) ) - 𝑦 ) (1 + 𝛼𝑟 0) 𝑒𝑥𝑝(𝑥 0 𝑦 ) ; + 𝛽 0 + 𝛽 ) ) 1 + 𝑒𝑥𝑝(𝑥 0 𝑥 ) ; + 𝛽 0 + 𝛽 ) ) -𝜆𝑥 0 ∂ ∂β 0 = E α𝑟 0) ) - (1 + 𝛼𝑟 0) 𝑒𝑥𝑝(𝑥 0 𝑦 ) ; + 𝛽 0 + 𝛽 ) )} 1 + 𝑒𝑥𝑝(𝑥 0 𝑥 ) ; + β 0 + β ) )

Model learning

We use a grid system to determine the optimal hyper-parameters. Tables 3 and4 show the results obtained with the Alternating Least Square (ALS), an approximate (Annoy ALS), Logistical Matrix Factorization (LMF), and Bayesian Personalized Ranking (BPR) methods. The ALS method obtains the best results. We see that the matrix factorization methods have lower performance than the 𝑘-nn methods presented above but have the advantage of being released online.

RESULTS

We presented three methods to measure the proximity between two classes of products, including a new one developed in this research work. The following table summarizes the proximity tables. To compare the proximity tables, we convert them into graphs in order to calculate their distances. The NetComp 4 library developed by [START_REF] Wills | Metrics for graph comparison : A practitioner's guide[END_REF] allows us to measure their spectral distances. Let 𝐺 and 𝐺 < be two graphs of size n with 𝜆 ) = and 𝜆 ) = ' their respective adjacency spectra. Considering a norm 𝑙 $ as a measure of the distance between the two spectra, the spectral adjacency distance between the two graphs is defined as follows [START_REF] Wills | Metrics for graph comparison : A practitioner's guide[END_REF]:

𝑑 0 (𝐺, 𝐺 1 ) ≝ @.3λ 2 3 -λ 2 3 $ 5 ' 4 2./
4 https://github.com/peterewills/NetComp

In our case, we use the normalized Laplace distance 𝑙 > which can be used to compare graphs of different sizes. In Table 6, we present the spectral distance obtained between the three methods.

Comparison of proximity measures based on recommendations

From each proximity table, we can make predictions of the 𝑘 nearest neighbors of each product. Thus, for each product 𝑝 of the HS nomenclature we obtain a set 𝐸 with a maximum of 𝑘 nearest products 𝐸 ? $ (𝑝) = {𝑝 # , ⋯ , 𝑝 , }.

Indeed, the number of neighbors can be less than 𝑘.

We carry out this operation for each of the three measures {𝜙 # , 𝜙 $ , 𝜙 @ }. We count the number of common elements between the sets obtained from the three proximity measures. We note that the Harvard measure on co-export analysis has no common recommendation with the other two methods. The method 𝜙 $ ,which relies on semantic proximities in nomenclatures, obtains a score of 7%. We thus show that the macroeconomic methods fail to predict the diversification of firms. This is in contrast to our measure which obtains a score > 96% using a recall@5 type metric.

MEASURING THE AGILITY OF A COMPANY

We propose to analyze the ability of companies to diversify their production rapidly by analyzing productive proximities. We are interested in the products that each company would be able to produce quickly by slightly adapting its production tool.

To do this, we will evaluate the productive opportunities for e, in the sense of the new product classes that 𝑒 can produce. We define a threshold l of maximum proximity between two product classes below which a productive jump is possible. In our experiments we consider 𝑙 = 0.8.

Let 𝐿 A : (𝑝 # , ⋯ , 𝑝 ( ) be the list of the production of 𝑒 and (𝜆 # , ⋯ , 𝜆 ( ) their respective weights. Let 𝐿 hs be the total list of product classes of the HS 2017 nomenclature on 4 digits. Let 𝜙(𝑝 # , 𝑝 $ ) be our proximity measure between 𝑝 # and 𝑝 $ . We define 𝑃 ) , the list of products close to 𝑝 ) , as follows:

𝑃 $ : 𝑞 $ ∈ 𝐿 hs , 𝜙(𝑞 $ , 𝑝 $ ) < 𝑙, 𝑞 $ ≠ 𝑝 $ , 𝑝 $ ∈ 𝐿 5

We then obtain the formulation of Agility:

Agility(𝑒) = . λ $ 𝑚𝑎𝑥(1, |𝑃 $ |) 6 $.7
Thus, our function evaluates the diversification capacity of each of the products manufactured by 𝑒 while considering their respective importance in the production of 𝑒.

CONCLUSION AND PERSPECTIVES

In this experiment, we presented a new method to propose diversification opportunities to a company. In crossvalidation, our method obtained high recall@5 scores, > 96%, outperforming the scores obtained with macroeconomic methods. The measurement of proximities between product classes offers interesting perspectives in the automatic evaluation of a company's agility score, for which we have proposed a formalization. However, macro-economic methods and our CF methods are not to be opposed. In the case of the analysis of co-exports, for example, there is an interest in identifying "new diversification paths", whereas our method will be satisfied with presenting existing diversifications. With the objective of developing a recommendation system for companies or territories, we could consider combining the different methods to provide a more varied recommendation. A system able to evaluate the relevance of the recommendations on a collaborative platform intended for companies, integrating serendipity in the results, could improve knowledge of the expectations of companies and thus contribute to enrich the models by integrating real user's ratings.

Table 1 :

 1 Number of products detected per website

	Total	0	1	2	3	4	5	6	7	8
	6153 companies	2059	3258	372	313	58	34	20	21	18

Table 2 :

 2 Results Item-Item Nearest neighbor with 𝑘 ∈[5,10]

		recall@5 train	recall@5 test	recall@10 train	recall@10 test
	Cosine	0.98848	0.96561	0.99934	0.95656
	TFIDF	0.98947	0.97104	0.99963	0.97828
	BM25	0.98809	0.96380	0.99901	0.96833

Table 3 :

 3 Results of matrix factorizations with 𝑘 = 5

		recall@15 train	recall@5 test	mse train	mse test
	ALS	0.74574	0.28416	0.00322	0.00221
	Annoy ALS	0.42775	0.17014	0.00326	0.00223
	LMF	0.05929	0.05611	2.11817	2.11486
	BPR	0.03207	0.03258	0.00405	0.00302
		Table 4: Results of matrix factorizations with 𝑘 = 10
		recall@10 train	recall@10 test	mse train	mse test
	ALS	0.79803	0.36290	0.00330	0.00225
	Annoy ALS	0.65597	0.27783	0.00330	0.00227
	LMF	0.09016	0.09231	2.16010	2.15670
	BPR	0.07067	0.07330	0.00365	0.00263

Table 5 :

 5 Summary of the proximity tables between products MéthodeType

	𝜙 !	Co-exports analysis	Macro
	𝜙 "	Semantic analysis of nomenclatures	Macro
	𝜙 #	Products on the websites	Micro

Table 6 :

 6 Spectral distances between the different proximity measurements

		𝜙 !	𝜙 "	𝜙 #
	𝜙 !	0
	𝜙 "	12.74	0
	𝜙 #	9.69	6.86	0

Table 7 :

 7 Identical recommendation scores across measures, avec 𝑘 = 5

		𝜙 !	𝜙 "	𝜙 #
	𝜙 !	1
	𝜙 "	0	1
	𝜙 #	0	0.0685	1

& ∑ M &' ! & , ∑ M &' ! M &' " & ∑ M &'$ & .

https://fr.isahit.com

https://implicit.readthedocs.io


domain: math shs

text:
Laurent Mazliak
email: laurent.mazliak@upmc.fr

Sergey Shalimov

Ervand Kogbetliantz

Vladimir Kosticyn

R Tazzioli

Andrei Nikolaevitch Kolmogorov's visits to France. Resuming the scientific relationship between France and Soviet Union after Stalin's death. 1

In 1958, the star of the university of Moscow mathematical department Andrei Nikolaevitch Kolmogorov (1903-1987) came for a long stay invited by the university of Paris. This visit was highly symbolic as it was the first of a Soviet mathematician after Stalin's death and an attempt to resume normal scientific exchanges between France and Soviet Union which had become rather limited since the 1930s. The paper focuses on how Kolmogorov participated to the academic exchanges between France and USSR.

The last five years of the Stalinist regime in the USSR between 1948 and 1953 had seen an almost complete interruption of scientific exchanges between the two sides of the Iron Curtain, and particularly between France and the USSR. After the consolidation of Soviet power in the 1920s, France had been one of the first capitalist countries to recognize the new USSR in 1924. 3 There was a very slow progression of intellectual exchanges between the two countries. Members of the intellectual emigration of the former tsarist empire, who were numerous in France at the beginning of the 1920s gradually lost their influence.

Since the 1910s, the mathematical field had been active in the exchanges between Russia and France, in particular because of the strong links existing between the two main leaders of the Moscow School of Theory of Functions, Dmitri Fedorovich Egorov and his pupil Nikolai Nikolaevich Lusin, and French analysts such as Emile Borel or Henri Lebesgue whose work the Moscow mathematicians enthusiastically followed and extended. 5 Under Lusin's impetus, a group of young active students went into the field of mathematical analysis and formed the talent-driven basis of the Soviet mathematical school which took off in the 1920s. Several members of this group had the opportunity to go on a study mission abroad, often combining a period in Germany and a period in France. 6 The future star of Soviet mathematicians Kolmogorov joined Lusin group in 1922 at the age of 19, 7 and he had a first opportunity to come to France in 1930, together with his colleague and friend Pavel Alexandrovich Aleksandrov. Kolmogorov, who was then becoming a world's leading specialist in probability, had then the opportunity to get to know better the French mathematician Maurice Fréchet as he was invited for a few summer weeks in Fréchet's holiday home on the coast of the Mediterranean Sea. Documents from the police archives show that there was a close surveillance of the Soviet mathematicians by the authorities during their stay, a sign of a not particularly relaxed situation. This was besides not a real secret and both Soviet mathematicians knew that they were under inspection and tried to keep their situation absolutely regular. A funny aspect of the surveillance reports is the perceptible perplexity of the police officers about the mathematical activity of the potential suspects. It did not seem to be reprehensible, but they were not absolutely confident.

In 1934, the Soviet government wished to promote a certain rapprochement with France as part of a policy of alliance to contain the Nazi threat. [START_REF] Scott | Alliance against Hitler[END_REF] Various bilateral initiatives were encouraged by the new ambassador Charles Alphand, who was a fervent supporter of a rapprochement between France and the USSR. [START_REF]La France et l'URSS dans l'Europe des années 30[END_REF] The attempts were not always successful in those years when Stalin's grip on Soviet society was becoming an absolute control. Kolmogorov was supposed to come to Paris in April and to present a series of six talks on the theory of random motions at the Henri Poincaré Institute. All was ready, even the posters mentioning the various seances. However, the mathematician did not succeed to obtain the permission from the Soviet authorities. Already in January, he had written to Maurice Fréchet that obtaining all the needed documents required "a lot of energy". Despite of Borel's attempts with the ministers of foreign affairs and of public instruction up to the last moment (in the archive one founds exchanges from March and April 1934), [START_REF]Archives of Paris Academy of Science. 13 On Fréchet's journey[END_REF] the operation failed. In September 1934 again, Kolmogorov wrote that it was quite unreliable that he would be able to go to Paris at the end of 1934. 12 Fréchet's long journey in Central and Eastern Europe in the Fall of 1935, 13 during which he spent several weeks in USSR (and met in particular Kolmogorov in Moscow) can besides probably be interpreted as a compensation for the missed opportunities of the previous year (Fréchet was sufficiently lucid to understand that an improvement of the inner Soviet situation would be long to come).

Some common Franco-Soviet activities took place nevertheless. There were for instance sport events, such as a car race organized by the car builder André Citroën in September 1934, but also intellectual exchanges.

In May 1934, a blatant "French scientific decade in the USSR" was organized in Moscow in which took part a pleiad of French scientists whose notoriety is recognized, including the physicist Jean Perrin (who had founded the same year in Paris the Committee for the vigilance of anti-fascist intellectuals), the mathematician Jacques Hadamard or the geologist Charles Jacob. 14 In addition to a busy program of visits, the French were invited to give lectures followed by demonstrations and practical exercises. The event received much attention from the Soviet press.

In France, the communist newspaper L'Humanité published several articles on the topic. In the clipping abovee, the journalist mentions that no comment is necessary « after the unreserved praise bestowed by the scholars on the Bolshevik builders who brought the USSR to the forefront in all fields of human activity. »

In 1935, the president of the council Pierre Laval went to Moscow and met Stalin ; this was the first official summit meeting between France and the USSR. Contrary to the jovial aspect of the picture, the communication was rather difficult. 15 The French delegation was most of the time carried around Moscow to admire the realizations of the new regime and Laval only obtained a short hard-fought interview with Stalin. Nevertheless, a better cooperation was on its way between the two countries and that same year, a Franco-Soviet week was officially organized by the University of Paris from November 23rd to December 2nd. The initiative seems to have been mainly due to the physicist Paul Langevin, a longtime Communist sympathizer and a fervent supporter for a rapprochement with the USSR and to André Mazon, director of Paris Institute for Slavic studies. 16 The Soviet delegation was explicitly presented as an emanation of the USSR Academy of Sciences. There were two leading mathematicians in this delegation : Sergei Natanevich Bernstein and Otto Yulianevich Shmidt. Only Bernstein's lectures at the Henri Poincaré Institute dealt in fact with mathematics, for Shmidt gave a talk on the great Arctic exploratory expedition he had organized the previous year, and he was also honored as the editor-in-chief of the Soviet Encyclopedia17 by his French counterpart, the historian Lucien Febvre who was at the head of the enterprise of the Encyclopédie Française. 18 The eminently political character of the demonstration did not escape anyone. The Soviet delegation was for instance received by the President of the Republic Albert Lebrun on November 25th and the press did not fail to give a certain resonance to the event.

The national newspaper Le Temps published on December 8th, 1935 an enthusiastic comment on the fraternal communion between Soviet and French scholars. It reports the declaration of the French Minister for Education Marius Roustan that "intellectual exchanges are gradually preparing the new era, that of a better and happier humanity in which will finally triumph this essential and fruitful truth that the goal of individual is to enrich collective life, that the goal of national life is to perfect and organize the life of mankind."

In fact, the rapprochement between France and the USSR at the end of the 1930s failed, in particular because of the opposition from London, and the promising announcements of December 1935 remained without a follow-up. From 1938, the succession of events (the Munich conference, the dismemberment of Czechoslovakia, the German-Soviet pact and finally the outbreak of the Second World War) led to the outright interruption of all communication between France and the USSR.

In the aftermath of the conflict, when a new world equilibrium dominated by American power was being established, Stalin insisted that new seductive initiatives be directed towards the countries of Western Europe, and especially France, a country which combined a strong influence of the Communist Party (linked to its participation in the resistance against the German occupier) and General de Gaulle's desire to contain the American influence, of which Stalin was perfectly aware. 19 In We note here a significant point in the history of mathematics. If the calculus of probabilities had been a discipline in full expansion in the 1930s in France, after the Second World War, it was met with skepticism (to say the least), for various reasons that I do not have time to detail here, by the members of the Bourbaki group whose authority on the French mathematical scene for several decades is well known. One therefore notices that it was not until when the two main French probabilists of the time, Fréchet and Lévy, had themselves been elected to the Academy, at a very advanced age, that Kolmogorov could join it. In the report written by the mathematician Jean Leray before the election of 16 May 1966, one can also read the mention that the Academy had "for a long time given a cold welcome to the calculus of probabilities", the discipline of which Kolmogorov had been the renovator. Leray did not forget to enforce his comment by mentioning that probability was gaining a still growing importance and above all by repeating the common place that the discipline had been created by "three French mathematicians Laplace, Poincaré and Borel"(one wonders why Pascal and Fermat do not appear as usual in the list!). Now a few quick concluding words. Kolmogorov's stays in France and his election to the academy that I have presented illustrate to a certain extent the normalization of scientific relations between France and the USSR in a context of detente which lasted during the two decades 1960 and 1970, with ups and downs linked to the state of international relations. It is probable that a further exploration in archives, in particular in Kolmogorov's personal papers, can provide valuable new information on the relations between Kolmogorov and French mathematicians. A particularly significant aspect of this point is related to the fact that Kolmogorov in some way personified the passing of the probabilist baton from Paris to Moscow after WW1 so that the aforementioned relation would also offer an insight on the development of modern probability during the 20th century.

(

  eds.), Mathematical Communities in the Reconstruction After the Great War 1918-1928, Trends in the History of Science, Springer, 2021 and Exile's Experts. Some Considerations on the Activity of the Russian Academic Group in Paris M. Borgato et al. (eds.), In Foreign Lands: The Migration of Scientists for Political or Economic Reasons, Trends in the History of Science, Springer, 2022 5 On this topic see Demidov Sergej S., « Les relations mathématiques franco-russes entre les deux guerres mondiales », Revue d'histoire des sciences, 2009/1 Tome 62, p. 119-142. 6 Smilka Zdravkovska, Peter L. Duren (Eds). Golden Years of Moscow Mathematics, American Mathematical Society,2007. 7 Albert N.Shiryaev. Kolmogorov: Life and Creative Activities. The Annals of Probability. 17, 3. 1989. pp. 866-944 Hence this letter by Kolmogorov to the French authorities, found in the police surveillance file of strangers at French National Archives : 8 I ask you to grant me an extension of the French visa on my passport until November 15th. The reason for my request is that I have a lot of mathematical talks with Mr. Fréchet, professor at the Henri Poincaré Institute of the University of Paris, currently on vacation in Sanary-sur-mer; It is also for scientific reasons that I want to spend a few weeks in Paris to work there at the Henri Poincaré Institute, also with M.Fréchet.

  June 1945 a solemn event on the occasion of the 220 years of the Russian Academy of Sciences was organized in Moscow. 20 The strangeness of the number 220 clearly indicates how urgent the initiative appeared to the Soviet leaders. The French university was particularly well treated there. Stalin delegated his foreign minister Molotov and a special plane to take 22 French scientists to participate in the festivities. If some of the scholars displayed Communist sympathies (the physicist Joliot-Curie or the mathematician Chapelon for example), the group included people of very diverse opinions, showing a real success of the operation of charm. Mathematicians were exceptionally well represented by world glories of the discipline (Emile Borel, Elie Cartan, Jacques Hadamard). The newspaper Ce soir (linked to the communist party) on June 10th, 1945 reported an interview by the secretary general of the France-USSR association, the biochemist and communist activist Jacques Nicolle, in which he mentioned : "you know which brilliant mathematicians are the Russians and how the Russian botanical research helped putting the Soviet agriculture on the first rank of the world" (the last sentence obviously refererring to Lysenko's alledged successes 21 in the reshaping of Soviet agriculture). The initiative again remained without a future and the relations were almost completely interrupted from 1947 until Stalin's death in March 1953. Shortly after Stalin's death, in June 1955, the symbolic occasion of the 200 years of the University of Moscow allowed the Soviet authorities to attempt a new rapprochement with the countries of Western Europe. An official delegation of two members of the University of Paris came to participate in the festivities. On his return, the mathematician Arnaud Denjoy sent the rector of Paris a lyrical and enthusiastic report on the reception he had received in Moscow. 22 The beginning of his text once again underlines the strong mathematical links forged between Paris and Moscow. That same year, the University of Paris decided to include Kolmogorov on the list of honorary doctorates awarded for the year 1955, a proposition strongly supported by Maurice Fréchet. 23 In fact, due to the delay to obtain the French visa, Kolmogorov could not attend the official ceremony in early November 1955 and he arrived in Paris only ten days later. Significant of a certain relaxation in relations between France and the USSR there is a mention of the award of the honorary doctorate to Kolmogorov in the newspaper "The Russian Thought" (Русская мысль), one of the main weekly newspapers of Russian emigration in France, on the issue of November 5th, 1955. I found few direct traces of Kolmogorov's stay in France in 1955, which was rather brief. He made presentations at the Henri Poincaré Institute (in a short report that Arnaud Denjoy made in 1958 on Kolmogorov for the Academy of Sciences in Paris, he mentioned that the Parisian conferences of 1955 had attracted a large audience). Kolmogorov also received an invitation to give a conference in Nancy in the seminar of the mathematician Jean Delsarte, one of the founders of the Bourbaki group. 24At the end of the 1950s, the France-USSR Association was the motor of the Franco-Soviet rapprochement. It invited on her own initiative Soviet academics in Paris. The absence of an official invitation by the University of Paris occasionally caused some tensions. A letter from the rector of Paris addressed to the president of the France-USSR association Georges Huisman mentioned that it was not allowed to use rooms of the Sorbonne for a meeting with a Soviet delegation of academics that had not been officially invited in Paris by the university.25 It is possible that this fact prompted the French authorities to seriously face the question of exchanges with the USSR. One finds traces of such a preoccupation in the following years and an exchange protocol between French and Soviet academics was finally set up in 1958. In this capacity, Kolmogorov was appointed a visiting professor at the Sorbonne for the second semester of 1958.As early as 1958, the Paris Academy of Sciences had considered the election of Kolmogorov as a foreign correspondent. Denjoy strongly supported the idea but it only materialized a few years later, in 1966, when Fréchet (elected in 1958) and Lévy (elected in 1964) campaigned for this election. 27 Paul Lévy wrote an extremely laudatory report on Kolmogorov, presenting him as a leading mathematician of the 20th century.

Archives Nationales, Pierrefitte. 19940457/176

On the Franco-Soviet decade, see Rachel Mazuy, « La décade scientifique franco-soviétique de 1934 », Cahiers du monde russe, 43/2-3 | 2002, 441-448.

Boisdron, M. (2005). Le projet de pacte oriental (février 1934 -mai 1935). Guerres mondiales et conflits contemporains, 220, 23-43.

L.Mazliak and T.Perfettini. A French response to the 1934 Franco-Soviet scientific decade in Moscow: trying to consolidate a fragile alliance. Forthcoming.

Brian Kassof. A Book of Socialism: Stalinist Culture and the First Edition of the Bolshaia sovetskaia entsiklopediia. Kritika:Explorations in Russian and Eurasian History. Volume 6, Number 1, 2005. pp. 55-95

Nicole Racine, « Lucien Febvre et l'encyclopédie française », Vingtième Siècle : Revue d'histoire, no 57,

1998, p. 132-133

Norman Naimark. Stalin and the Fate of Europe: The Postwar Struggle for Sovereignty. (Harvard University Press,

2019). 20 Korzun V.P., Gruzdinskaya V.S. The 220th Anniversary of the Academy of Sciences of the USSR in the Victorious 1945: A Scenario of Celebration in the Sociocultural Context of the Era // RUDN Journal of Russian History. -2020. -Vol. 19. -N. 2. -P. 374-392

See Nikolai Krementsov. Stalinist Science. Princeton University Press, 1997.

Archives Nationales, AJ/16/6994.

Archives Nationales, 0020476/398-401

26 November 1955. Dossier Kolmogorov. Archives Académie Sciences Paris.

Quoted in Колмогоров юбилейное издание в трех книгах. Том 1. Москва, Физматлит, 2003. pp.120-122 (original in Russian).

He gave two courses of ten sessions each: one in function theory and one more specialized in probability. The report he wrote for the Soviet authorities on his return has been preserved. Kolmogorov wrote :

From March 5th [sic] to June 6th, I gave two courses of eleven lectures each. The first course was relatively accessible and initially attracted about 70 and at the end about 40 students, of whom, however, more than half were well-known scientists and only less than half were students. The second course was of a more specialized nature and was attended mainly by specialists in the theory of probability. The audience was thus small, but highly qualified. The lecture notes compiled by Régnier after my processing and additions, are supposed to be published in the Annals of the Poincaré Institute (Paris). I also gave a talk "Linear dimension of vector topological spaces" in the seminar "N. Bourbaki" in front of an audience of about 100 people. In addition, at the request of the university and in agreement with our embassy, a talk with a more general content, "On the Organization of Teaching Mathematics and Scientific Mathematical Research in the USSR," was organized, which gathered an audience of about 150 people. Scientific communication with specialists in the theory of probability was quite intense (especially with Prof. P. Lévy, Prof. R. Fortet and during several collective walks near Paris). 26 In 1960, Kolmogorov published a long article in the journal of the France-USSR Association on the subject of Franco-Soviet scientific relations. He wrote that The year 1959 had been marked by a significant expansion of scientific contacts between scientists from the USSR and France. (...) We were pleased to note that the movement for the extension of friendly relations with the USSR has spread to the most diverse circles of French society, whatever their political opinions.