Simon Leglaive

Roland Badeau

Richard Gaël

Ltci

Autoregressive Moving Average Modeling of Late Reverberation in the Frequency Domain

Keywords: Statistical room acoustics, late reverberation, Gaussian random process, autoregressive moving average model

In this paper, the late part of a room response is modeled in the frequency domain as a complex Gaussian random process. The autocovariance function (ACVF) and power spectral density (PSD) are theoretically defined from the exponential decay of the late reverberation power. Furthermore we show that the ACVF and PSD are accurately parametrized by an autoregressive moving average (ARMA) model. This leads to a new generative model of late reverberation in the frequency domain. The ARMA parameters are easily estimated from the theoretical ACVF. The statistical characterization is consistent with empirical results on simulated and real data. This model could be used to incorporate priors in audio source separation and dereverberation.

I. INTRODUCTION

When an audio source is recorded in a reverberant environment, the signal at the microphone is a filtered version of the source signal plus a possible additive noise. The filter involved in this process is called a Room Impulse Response (RIR) and represents the propagation from the source to the microphone. In the case of a single emitting source, estimating the source signal is called dereverberation. When several sources play simultaneously, the task is referred to as source separation. A large number of methods are based on probabilistic frameworks. One possible approach is to treat the acoustic parameters as being deterministic so that they are estimated in a maximum likelihood sense [START_REF] Schwartz | Multi-microphone speech dereverberation using expectation-maximization and kalman smoothing[END_REF], [START_REF] Ozerov | Multichannel nonnegative matrix factorization in convolutive mixtures for audio source separation[END_REF]. Another way of doing is to incorporate priors on the acoustic parameters, leading to a maximum a posteriori estimation or a full Bayesian treatment [3, ch. 8]. In audio source separation, some recent approaches have shown that improved separation results can be obtained by taking probabilistic priors on RIRs into account. In [START_REF] Duong | Spatial location priors for gaussian model based reverberant audio source separation[END_REF] the authors proposed a prior motivated by statistical room acoustics in order to represent the spatial correlations between RIRs at different microphones. In [START_REF] Leglaive | A priori probabiliste anéchoïque pour la séparation sous-déterminée de sources sonores en milieu réverbérant[END_REF], [START_REF]Multichannel audio source separation with probabilistic reverberation modeling[END_REF] an autoregressive prior in the frequency domain is proposed to model the direct path and the first echoes of the RIRs.

In statistical room acoustics, the late part of a Room Frequency Response (RFR) can be considered as a complex Gaussian random process. In [START_REF] Schroeder | Frequency-correlation functions of frequency responses in rooms[END_REF] Schroeder expressed the theoretical autocovariance function (ACVF) of this process This work is partly supported by the French National Research Agency (ANR) as a part of the EDISON 3D project (ANR-13-CORD-0008-02). from the time-domain exponential decay of the reverberation power. However Schroeder neglected the influence of the direct path and the early echoes, resulting in a mismatch between theoretical and empirical ACVF, as observed in [START_REF] Gustafsson | Source localization in reverberant environments: Modeling and statistical analysis[END_REF]. In this paper, we consider the fact that the exponential decay is only valid for late reverberation. We thus obtain a more accurate match between the new expression of the theoretical ACVF and the experiments. Furthermore we show that an autoregressive moving average (ARMA) modeling of the late part of the RFR leads to an accurate parametrization of the ACVF and Power Spectral Density (PSD). Similar parametric modeling in the frequency domain has been applied to wireless channels in [START_REF] Gu | Parametric modeling of wideband and ultrawideband channels in frequency domain[END_REF], but in a data-dependent way. From the ARMA model it will be possible to define a prior distribution on the late part of the RFR, which could be used for audio source separation in the same way as in [START_REF]Multichannel audio source separation with probabilistic reverberation modeling[END_REF].

We first present in section II the statistical late reverberation model and compare the theoretical results with experiments on simulated and real RIRs. Then we describe in section III the ARMA model for the late part of the RFR, where the parameters are easily estimated from the theoretical ACVF, without the need of any data. Experimental results show the validity of this ARMA model. We finally conclude in section IV on the proposed model invoking its suitability for audio source separation.

II. STATISTICAL LATE REVERBERATION MODEL

An RIR has a well defined structure. As represented in Fig. 1 we distinguish three regions: firstly the direct path between the source and the microphone, then the early echoes, coming from the first reflections on the walls of the room, and finally the late reverberation where the sound is considered to be diffuse. Diffusion means that the energy density is uniformly distributed across the room and the energy at one point is uniformly distributed over all directions [START_REF] Schultz | Diffusion in reverberation rooms[END_REF]. The direct path and early echoes are usually considered as being deterministic, while the characterization of late reverberation involves the use of statistical room acoustics. In this paper, we group the direct path and the early echoes under the term "early contributions". Let h(t) = h e (t) + h l (t) denote the whole RIR, and h e (t), h l (t) the early and late parts respectively. The transition instant between early reflections and late reverberation is referred to as the mixing time and can be defined according to the volume V of the room in m 3 [START_REF] Jot | Analysis and synthesis of room reverberation based on a statistical time-frequency model[END_REF], [START_REF] Lindau | Perceptual evaluation of physical predictors of the mixing time in binaural room impulse responses[END_REF]:

t 0 = C 0 √ V f s samples, (1)
with C 0 a normalization constant, • the floor function and f s the sampling rate in Hz. Different values of C 0 have been proposed in the literature [START_REF] Lindau | Perceptual evaluation of physical predictors of the mixing time in binaural room impulse responses[END_REF], we choose C 0 = 2 × 10 -3 . The RFR is defined as

H(k) = H e (k) + H l (k)
where for k = 0, ..., T -1:

H (•) (k) = F T {h (•) (t)} = T -1 t=0 h (•) (t)e -j2πkt/T . (2)
Equation ( 2) is the T-point Discrete Fourier Transform (DFT) of signal h (•) (t). We also define the inverse DFT by:

h (•) (t) = F -1 T {H (•) (k)} = 1 T T -1 k=0 H (•) (k)e j2πkt/T . (3)
A. Late reverberation model

The theory of statistical room acoustics for diffuse sound fields can be applied in the frequency domain if (a) the dimensions of the room are large compared to the wavelength of the source signal, (b) the average spacing of the room resonance frequencies are smaller than one third of the modes' bandwidth and (c) the source and microphone are located at least at half a wavelength from the walls [START_REF] Schroeder | Frequency-correlation functions of frequency responses in rooms[END_REF], [START_REF] Gustafsson | Source localization in reverberant environments: Modeling and statistical analysis[END_REF], [START_REF] Habets | Speech dereverberation using statistical reverberation models[END_REF]. Condition (b) is fulfilled above Schroeder's frequency:

f sch = C 1 T 60 V Hz, (4)
with C 1 a normalization constant approximately equal to 2000. T 60 is the reverberation time in seconds defined as the time it takes for the sound energy to decrease by 60 dB after extinction of the source. We assume in the following that these conditions are fulfilled. It is well known that for the diffuse part of an RIR the power decays exponentially [START_REF] Jot | Analysis and synthesis of room reverberation based on a statistical time-frequency model[END_REF]. Following this observation we define the Power Temporal Profile (PTP) of the RIR for t = 0, ..., T -1:

hl (t) = E[|h l (t)| 2 ] = P 2 0 e -2t/τ 1 t≥t0 (t), (5)
where 1 t∈T (t) is the indicator function which equals 1 if t ∈ T , 0 otherwise, P 2 0 is a constant related to the total power of late reverberation and τ is linked to the reverberation time T 60 through:

τ = T 60 f s 3 ln(10) samples. ( 6
)
It is important to mention that different realizations of the room responses can be interpreted as different observations at several source and microphone positions in the room.

Expectations have thus to be understood as spatial averaging. We now describe some important statistical results about the late part of the RFR. According to the theory of statistical room acoustics, the signal received by a microphone in a reverberant field combines the contributions of a large number of modes of the room with randomly distributed amplitudes and phases. Assuming that the modes are independent and identically distributed, the central limit theorem implies that the RFR is a random process whose real and imaginary parts are independent Gaussian processes with the same variance. Assuming a centered and wide sense stationary (WSS) process we define the ACVF γ(m) and the PSD φ(t) of the RFR by:

γ(m) = E[H l (k)H l (k -m) * ]; (7)
φ(t) = 1 T E[|F T {H l (k)}| 2 ], (8)
where (•) * denotes complex conjugate. As a centered proper and WSS complex Gaussian random process the RFR is thus fully characterized by its ACVF or its PSD. We have to mention that as we work in discrete time and frequency, all signals are T -periodic. Strictly speaking the RFR is thus a T -periodic WSS random process. Moreover φ(t) has to be understood as a discretized PSD function. One can refer to [START_REF] Gu | Parametric modeling of wideband and ultrawideband channels in frequency domain[END_REF] for a review of some properties of periodic random processes.

From equation ( 8) we can express the PSD of the process {H l (k)} k according to the PTP defined in equation ( 5) (see appendix A):

φ(t) = T hl (T -t). (9)
The PTP is T -periodic so that hl (T ) = hl (0). Applying the Wiener-Khinchin theorem from this expression of the PSD we obtain the theoretical ACVF:

γ(m) = F -1 T {φ(t)} = P 2 0 e -2T /τ 1 -e (j2πm/T +2/τ )(T -t0+1)
1 -e j2πm/T +2/τ .

(10) P 2 0 is related to the variance σ 2 rev := γ(0) of the RFR by:

P 2 0 = σ 2 rev e 2T /τ
1 -e 2/τ 1 -e 2(T -t0+1)/τ .

(

) 11
Moreover it can be shown that (see appendix B and [START_REF] Radlovic | Equalization in an acoustic reverberant environment: Robustness results[END_REF]):

σ 2 rev = 1 -α παS , (12)
with α the average absorption coefficient (without dimension) and S the total wall area in m 2 . The absorption coefficient can be computed using Norris-Eyring's formula [3, p. 24]:

α = 1 -e -24 ln(10)V /(cST60) , (13)
with c the speed of sound in m.s -1 .

B. Experimental validation

As already mentioned before, the authors in [8] compared Schroeder's theoretical ACVF [START_REF] Schroeder | Frequency-correlation functions of frequency responses in rooms[END_REF] with empirical ACVFs computed from simulated and recorded RIRs. The results we present in this section have been obtained using an experimental procedure close to the one presented in [START_REF] Gustafsson | Source localization in reverberant environments: Modeling and statistical analysis[END_REF]. From a given set of RIRs (simulated or recorded) at various locations in the room we first remove the early contributions by setting to zero the samples for t < t 0 . For each realization hr l (t) (one RIR for a particular location of source and microphone), we compute the RFR Hr l (k) and only keep the K samples in the interval [f sch , f s /2] Hz. The empirical ACVF for one realization is obtained using the following estimator for m = -K + 1, ..., K -1:

γr (m) = 1 K K-1-|m| k=0 Hr l (k) Hr l (k -m) * . ( 14
)
Following this Monte Carlo simulation the final empirical ACVF is obtained by averaging over the whole set of realizations:

γ(m) = 1 R R r=1 γr (m). (15)
We will compare this empirical ACVF to the theoretical one defined by equations ( 10)- [START_REF] Habets | Speech dereverberation using statistical reverberation models[END_REF].

During our experiments we first observed a mismatch between the data and the theoretical variance given in equation [START_REF] Lindau | Perceptual evaluation of physical predictors of the mixing time in binaural room impulse responses[END_REF]. Although widely used in the literature this sole expression is rarely compared with experiments. As mentioned in [15, ch. 7] the expression of the reverberant mean square pressure that leads to equation [START_REF] Lindau | Perceptual evaluation of physical predictors of the mixing time in binaural room impulse responses[END_REF] (see appendix B) may be inaccurate depending on the room dimensions and the source to microphone distance. Moreover this formula is obtained by considering that the reverberation field is established after the first reflection of the direct path on a wall, which disagrees with the definition of late reverberation we gave before. This could explain the mismatch. However an empirically accurate correction consists in multiplying σ 2 rev as defined in equation ( 12) by a constant C rev = 75. In the following this correction will always be applied. Moreover we can mention that the variance is only a scale factor in the ACVF and PSD. The correlations between the samples of a random process can also be defined according to the normalized autocorrelation function which does not depend on the variance of the process.

We simulated 196 RIRs from the image source method using the Roomsimove toolbox 1 . The room was a 10 x 6.6 x 3 m shoebox with reverberation time T 60 = 250 ms. The source position remained fixed while the microphone was moved over 196 positions. The results for simulated RIRs are presented in Fig. 2a. We observe a good fit between the theoretical expression in equation ( 10) and the empirical ACVF.

For the experiment on real RIRs we used 130 responses from the C4DM (Center for Digital Music) database [START_REF] Stewart | Database of omnidirectional and bformat room impulse responses[END_REF]. The RIRs were recorded in a room of size 7.5 x 9 x 3.5 m with reverberation time T 60 = 1.8 s. The source position was again fixed while the microphone was moved. Once again we observe a good fit between theory and experiments in Fig. 2b.

For both simulated and real RIRs, the theoretical expression of the ACVF we proposed in equation ( 10) better agree with experimental results than the one Schroeder proposed in [START_REF] Schroeder | Frequency-correlation functions of frequency responses in rooms[END_REF] and that was further investigated in [START_REF] Gustafsson | Source localization in reverberant environments: Modeling and statistical analysis[END_REF].

III. AUTOREGRESSIVE MOVING AVERAGE MODEL

We have seen in the previous section that the statistical properties of the late part of an RFR are fully summarized by the ACVF defined in equation [START_REF] Schultz | Diffusion in reverberation rooms[END_REF]. This ACVF only depends on the reverberation time, the volume of the room and the total wall area. In this section we will show that an ARMA model in the frequency domain is able to accurately fit the theoretical ACVF and PSD we defined in section II-A.

A. ARMA model and estimation

We define the following ARMA(P, Q) model for the late part of the RFR {H l (k)} k :

Φ(L)H l (k) = Θ(L) (k), (16)
1 http://www.irisa.fr/metiss/members/evincent/Roomsimove.zip where Φ(L) = P p=0 ϕ p L p , Θ(L) = Q q=0 θ q L q with ϕ 0 = θ 0 = 1 and L is the lag operator, i.e. LH l (k) = H l (k-1). (k) is a proper complex white Gaussian noise of variance σ 2 for k ∈ [0, ..., T -1] and is extended by T -periodicity elsewhere. H l (k) is the output of a linear filter with transfer function Ψ(z -1 ) = Θ(z -1 )/Φ(z -1 ). The polynomials Θ(z -1 ) and Φ(z -1 ) are assumed to have their zeros within the unit circle so that Ψ(z -1 ) is the transfer function of an invertible causal and stable filter. From this ARMA model we can write the following parametric representations of the PSD φ(t) and ACVF γ(m) :

φ(t) = σ 2 F T {θ q } q=0,...,Q 2 F T {ϕ p } p=0,...,P 2 , (17)
P p=0 ϕ p γ(m -p) =      σ 2 Q q=m θ q ψ * q-m if 0 ≤ m ≤ Q 0 if m > Q, (18)
where

Ψ(z -1 ) = +∞ k=0 ψ k z -k and m = m (mod T ) such that m ∈ [0, ..., T -1].
For equation [START_REF] Schroeder | New method of measuring reverberation time[END_REF] to be valid we have to assume that there is no overlap of the T -periodic ACVF γ(m), i.e. ψ k = 0 for k > T /2 .

The ARMA parameters are estimated from the sole knowledge of the theoretical ACVF given by [START_REF] Schultz | Diffusion in reverberation rooms[END_REF], without need of any data. The procedure is fully described in [17, ch. 2] and we recall it here briefly. The AR parameters {ϕ p } P p=1 are first estimated by solving the modified Yule-Walker equations defined from equation ( 18) for m = Q + 1, ..., Q + P . From the estimated AR parameters we then define the ACVF γ (m) = Φ * (L -1 )Φ(L)γ(m) where Φ * (L -1 ) = P p=0 ϕ * p L -p . This is the ACVF of an MA process whose coefficients and noise variance are {θ q } Q q=1 and σ 2 respectively, as introduced in equation ( 16). We approximate this MA(Q) process by a highorder AR(L) with L = 10Q. From γ (m) we compute the parameters of this high-order AR model by solving the standard Yule-Walker equations. We obtain the estimate of σ 2 and we denote by {ϕ p } L p=1 the resulting AR coefficients. Finally, to obtain the MA parameters {θ q } Q q=1 , we fit an AR(Q) model on the sequence {1, ϕ 1 , ..., ϕ L } again by solving the Yule-Walker equations.

B. Experimental validation

We applied this procedure to compute the ARMA parameters from the theoretical ACVF defined by equation [START_REF] Schultz | Diffusion in reverberation rooms[END_REF]. We used the same room parameters and reverberation time (250 ms) as presented in section II-B for the simulated RIRs. We empirically chose an AR order P = 7 while the MA order is set as Q = 2 by observing the support of the ACVF γ (m) defined in the previous section. Once the ARMA parameters are estimated, the PSD can be computed using equation [START_REF] Kay | Spectral estimation[END_REF], and the ACVF is easily obtained by inverse DFT of the PSD. The results are shown in Fig. 3. We observe a very good fit of the ARMA model on both theoretical ACVF and PSD. The PSDs are represented in decibels so we can observe that the exponential decay is well verified. As a final way of assessing the validity of the whole model (theoretical ACVF, PSD and ARMA parametrization), we synthesize an artificial late reverberation RIR. Using the estimated parameters, the late RFR is obtained by ARMA filtering in the frequency domain of a complex white Gaussian noise. To obtain the late part of the RFR we only keep the samples within the frequency range [f sch , f s /2] Hz. The RFR values below Schroeder's frequency are fixed to zero, but we have to mention that the results are similar by extending the model to [0, f s /2] Hz. The time domain late RIR represented in Fig. 4 is finally obtained using the hermitian symmetry of the RFR and the inverse DFT. We can clearly observe the exponential decay of the late reverberation starting from the mixing time, as described by the PTP in equation [START_REF] Leglaive | A priori probabiliste anéchoïque pour la séparation sous-déterminée de sources sonores en milieu réverbérant[END_REF]. The estimated reverberation time of this RIR obtained by using Schroeder's backward integration method [START_REF] Schroeder | New method of measuring reverberation time[END_REF] is 280 ms which is close to the targeted value of 250 ms.

IV. CONCLUSIONS

In this paper, we refined the expression of Schroeder's ACVF [START_REF] Schroeder | Frequency-correlation functions of frequency responses in rooms[END_REF] for the late part of an RFR by considering that late reverberation only appears after early contributions. We experimentally showed the accuracy of the obtained ACVF. We also proposed a new parametric model of the ACVF and PSD, leading to a generative ARMA model of late reverberation in the frequency domain. From this ARMA representation in equation ( 16) it is possible to define a prior distribution on the late part of an RFR. In future work this prior will be applied to source separation to constrain the estimation of the mixing filters, following the same procedure as in [START_REF]Multichannel audio source separation with probabilistic reverberation modeling[END_REF]. Refinement of the model includes the investigation of a more accurate and justified expression of the variance σ 2 rev . This model could also be extended for frequency dependent reverberation times, by using different ARMA models for different frequency bands.

Fig. 1 :

 1 Fig. 1: Schematic illustration of a room impulse response.

Fig. 2 :

 2 Fig. 2: Theoretical and empirical ACVFs.

Fig. 3 :Fig. 4 :

 34 Fig. 3: ARMA(7,2) modeling of the PSD and ACVF.

APPENDIX A

Proof of equation [START_REF] Gu | Parametric modeling of wideband and ultrawideband channels in frequency domain[END_REF]: From straightforward calculations one can show that:

Applying the inverse DFT, noted F -1 T {•}, to equation ( 19) and using the circular convolution and shift theorems we have:

where denotes the circular convolution, and δ(t) the Dirac delta function. Using the fact that 20) we obtain:

From equations ( 21) and ( 8) we finally obtain [START_REF] Gu | Parametric modeling of wideband and ultrawideband channels in frequency domain[END_REF].

APPENDIX B Proof of equation [START_REF] Lindau | Perceptual evaluation of physical predictors of the mixing time in binaural room impulse responses[END_REF]: Let f = kf s /T . The relation between the RFR H l (f ) and the complex sound pressure (CSP) P l (f ) due to late reverberation at some point in a room for a punctual source is given by [19, p. 311], [START_REF] Radlovic | Equalization in an acoustic reverberant environment: Robustness results[END_REF]:

with ρ 0 the air density in kg.m -3 and Q(f ) the volume velocity of the source in m 3 .s -1 . Using the previous equality we can link the variances of the CSP and of the RFR:

where |Q(f )| 2 is expressed as [19, p. 311], [START_REF] Radlovic | Equalization in an acoustic reverberant environment: Robustness results[END_REF]:

c is the speed of sound in m.s -1 and W s is the power output of the sound source in Watts.

We now have to express the reverberant field mean square pressure E[|P l (f )| 2 ]. We denote by α the average absorption coefficient (without dimension) and S the total wall area in m 2 . In a reverberant field the intensity is constant everywhere and is related to the mean square pressure by [19, p. 581]:

For a diffuse sound field in steady-state conditions, the reverberant power supplied by the source must be equal to the power absorbed by the walls [15, ch. 7]. The reverberant power can be defined as the sound power from the source that remains after the first reflection, (1 -α)W s , and the absorbed power is αSI rev . From this condition we have:

which leads to the reverberant field mean square pressure:

Substituting equations ( 27) and ( 24) into (23) we obtain the result given by equation ( 12).


Giuseppina Turco

Cécile Fougeron

Nicolas Audibert
email: nicolas.audibert@univ-paris3.fr

The effects of prosody on French V-to-V coarticulation: A corpus-based study

Keywords: vowel harmony, coarticulatory resistance, phonetics-prosody interface

This study examines whether the degree of vowel-to-vowel coarticulation in French (better known as "vowel height harmony", V2-to-V1 henceforth) varies as a function of position in prosodic domain (i.e. IP initial vs. word-medial) and duration of V1 (i.e. short vs. long). Following the literature on the phonetics-prosody interface, segments at stronger edges are more resistant to coarticulatory effects induced by their neighboring vowel. While previous studies have mainly looked at non-local V-to-V coarticulation across prosodic boundaries/domains (e.g.,V#(C)V), here we look at V2-to-V1 coarticulation within an Intonational Phrase according to whether target V1 is in absolute initial position (#V1C(C)V2, e.g., #essaie [esɛ]/[ɛsɛ] -'try') or not (wordmedial, e.g., épaissit [epɛsi]/[epesi] -'thikened'). The analyses are based on 33k words presenting possible V1C(C)V2 harmonic contexts, which were extracted from a corpus of French running speech. V2-to-V1 coarticulation is measured as the lowering of the first formant of the target V1 (/e, ɛ, o, ɔ/) in relation to the height of the V2 trigger /+high/ (i.e. midhigh and high) vs. /-high/ (i.e. mid-low and low). Results show an effect of prosodic position (but no effect of V1 duration) on V2-to-V1 coarticulation: V1 is more resistant to coarticulation when initial in an IP.

Introduction

Degree of anticipatory V2-to-V1 coarticulation affecting vowel height in French has been often referred to as a phonological -though optional -process of vowel harmony. In the French word aime ("(I) love"), the first vowel is typically produced as mid-low [ɛm], compared to the first vowel of aimer ("to love"), which tends to be produced as mid-high [eme] due to the closing influence of the mid-closed final vowel. Vowels targeted by this process are the mid French vowels (/e, ɛ, oe, ø, o, ɔ/), which can alternate in height (mid-high/mid-low) according to the height of the following V2 trigger.

While the exact description of the phenomenon may vary in the classical French literature (cf. [START_REF] Dell | Les règles et les sons: Introduction à la phonologie générative[END_REF][START_REF] Fouché | Traité de Prononciation Française[END_REF][START_REF] Tranel | The Sounds of French: An Introduction[END_REF]), recent acoustic studies [START_REF] Nguyen | Acoustic aspects of vowel harmony in French[END_REF][START_REF] Turco | Que nous apprennent les gros corpus sur l'harmonie vocalique en français ?[END_REF] have provided empirical evidence for its sensitivity to several factors. So far, the following effects on V2-to-V1 coarticulation have been attested: a) V1 backness: coarticulation is stronger for back V1 than front V1 [START_REF] Nguyen | Acoustic aspects of vowel harmony in French[END_REF][START_REF] Turco | Que nous apprennent les gros corpus sur l'harmonie vocalique en français ?[END_REF]; b) b) type of intervocalic segment: it is stronger when the intervening consonant is represented by a labial than a lingual consonant and with consonant clusters compared to consonant sequences resulting from schwa drop [START_REF] Turco | Que nous apprennent les gros corpus sur l'harmonie vocalique en français ?[END_REF]; c) speaking variety: it is more systematic in Northern French speaking varieties than in Southern French varieties [START_REF] Nguyen | Acoustic aspects of vowel harmony in French[END_REF]; d) orthographic influence: it is stronger when not biased by orthography [START_REF] Turco | Que nous apprennent les gros corpus sur l'harmonie vocalique en français ?[END_REF]. In the current study, we further look at factors that may influence the V-to-V coarticulatory process in a large database of natural speech, by examining two other well-known sources of variation: position-in-prosodic-domain and vowel duration.

Within the wide range of studies falling under the rubric of prosodic strengthening (i.e. spatio-temporal expansion of segments) at prosodic domain edges (see [START_REF] Cho | The phonetics-prosody interface in laboratory phonology[END_REF] for a review), very little work has so far been devoted to test the idea that strengthening in prosodically strong position is related to coarticulatory resistance (e.g., [START_REF] Fougeron | Articulatory strengthening at edges of prosodic domains[END_REF][START_REF] Farnetani | Coarticulation models in recent speech production theories[END_REF]). Seminal work on V-to-V coarticulation by [START_REF] Cho | Prosodically conditioned strengthening and vowel-tovowel coarticulation in English[END_REF] in English, followed by [START_REF] Fivela | Coarticulation Across Prosodic Domains in Italian: An Ultrasound Investigation[END_REF] in Italian, has shown that the amount of V-to-V coarticulation across a prosodic boundary can be affected by the prosodic strength of this boundary. Hence, in a CV1#CV2 sequence, the postboundary vowel V2 tends to resist coarticulatory influence of the pre-boundary V1 when CV2 is initial in a prosodically strong prosodic domain. If these results bring support to the idea that initial position in a high prosodic domain is somehow a 'preserved' position, it remains unclear whether the reduced coarticulation on V2 is due to the fact that coarticulation is blocked by the presence of a strong boundary between the target and the trigger, or to the fact that the domain initial position is resistant per se (i.e. whether it is a "boundary" vs. "edge" effect).

Here, we investigate V2-to-V1 coarticulation when there is no intervening boundary between the two vowels and when V1 is in IP absolute initial position (i.e. it is immediately preceded by an IP prosodic boundary, #V1C(C)V2 as in '#essaie de faire ça' [ɛsɛdfɛRsa] -'try to do that', with # marking an IP boundary), a position known to show initial strengthening. Note that in this case, V1 is by definition in an onsetless syllable, that is, a position where we expect the vowel to be prosodically strengthened [START_REF] Georgeton | Domain-initial strengthening on French vowels and phonological contrasts: Evidence from lip articulation and spectral variation[END_REF], thereby probably showing more resistance to contextual influence. Cases of V1 in IP-initial position are compared to a position where strengthening is not expected: medial position in both IP and Word (e.g. ça épaissit [saepɛsi] 'it thiken').

The second factor of interest in this study is the duration of the V1 target vowel. On the basis of pioneering work on target undershoot (cf. [START_REF] Lindblom | A spectrographic study of vowel reduction[END_REF]), we know that many sources of contextual variation in continuous speech can influence the acoustic properties of a vowel. For mid-open and mid-closed vowels, factors favoring target undershoot would modify the F1 of V1 in the same direction than V2 coarticulatory would do in a harmonic context: lowering of F1 for mid-high vowels and raising of F1 for mid-closed vowels. In a large database of uncontrolled natural speech, such as the one we are using here, it is quite difficult to disentangle all the factors that could favor V1 undershoot (speech rate, style, prosody, lexical factors, among other ones). However, it is relatively easy to extract segment duration, a known co-variant of undershoot, whose effect on vowel acoustic properties has been relatively well described [START_REF] Audibert | Duration-vs. style-dependent vowel variation: A multiparametric investigation[END_REF].

In the current study, we will thus indirectly test if the coarticulatory effect of V2 on V1 is influenced by other variation factors leading to V1 undershoot. Specifically, we look at whether V2-to-V1 coarticulation is stronger when V1 is temporally reduced.

Corpus-based study

Speech material was extracted from two publicly available French corpora: the corpus ESTER comprises continuous speech based on broadcasted news; the corpus NCCFr represents conversational speech from free and guided discussions on societal topics between friends [START_REF] Galliano | The ESTER 2 Evaluation Campaign for the Rich Transcription of French Broadcast News[END_REF][START_REF] Galliano | Corpus description of the Ester evaluation campaign for the rich transcription of French broadcast news[END_REF][START_REF] Torreira | The Nijmegen corpus of casual French[END_REF].

Data coding

Words in which harmony could occur were selected according to the following principles: words containing one of the following vowels {i, e, ɛ, o, a, y, u, ɑ} as a V2 located in the last syllable and containing one of the following vowels {e, ɛ, o, ɔ} as a V1 placed in the penultimate syllable. A total of 33 325 words were selected by applying no constraint on their syllable structure, their duration and sequence of intervocalic consonants (i.e. between V1 and V2).

The vowels V1 and V2 were defined according to a forced automatic alignment, taking both orthographic and phonological information into account at the word level to raise possible ambiguities between mid-high and mid-close vowels. Vowels /ø, oe/ which associate to complex letter-tophoneme relationships were excluded from the analysis. The mid V1 vowels were classified according to their place of articulation (/e, ɛ/ front vs. /o, ɔ/ back). These vowels were additionally coded according to whether the respective graphemes induce or not a higher pronunciation, that is, é for [e] and au/eau for [o].

The degree of V1-to-V2 coarticulation was measured as the lowering of the first formant of the V1 target in relation to the height of V2. Formant values were extracted at 1/3, 1/2 and 2/3 of the vowel and then averaged for a single value per vowel. In line with a previous study on vowel harmony [START_REF] Turco | Que nous apprennent les gros corpus sur l'harmonie vocalique en français ?[END_REF], the statistical analysis was performed only on V1 represented by mid-front and mid-back vowels and on V2 including /+high/ (i.e. mid-high and high) vs. /-high/ (i.e. mid-low and low) vowels. The height of V2 is referred to as V2 height, a variable containing "high" and "low" values.

Other relevant variables comprise information related to the prosodic position of V1 (Prosodic position) and the duration of V1 (V1 duration). Concerning prosodic position, IP-initial position ("IPi") was determined on the basis of automatic pause detection: IP boundaries have been defined by the presence of pauses, and V1s immediately following a pause were labelled as "IPi". Therefore, all V1 in "IPi" are word initial (in an onsetless syllable) and are post-pausal. Since IP boundaries without pauses can also occur in French, it was not possible to confidently define the prosodic position of the other non-post-pausal word-initial V1. These cases were thus excluded and only Word-medial V1 (for which we are confident to say that they are IP-medial) were included in the analysis and coded as "Wm".

Duration was treated as a categorical variable made of two values values: "short" vowels (up to 50 ms) and "long" (above 50 ms) vowels, largely in line with previous classification criteria applied to the same corpora [START_REF] Audibert | Duration-vs. style-dependent vowel variation: A multiparametric investigation[END_REF].

Statistical analyses

We used R [START_REF]R: A language and environment for statistical computing[END_REF] and lme4 package [START_REF] Bates | lme4: Linear mixed-effects models using eigen and s4[END_REF] to perform linear mixed effect analyses of the relationship between the first formant of V1 (in Hertz, F1 henceforth) and the following fixed effects:

• V2 height: "high" vs. "low" vowels

• Prosodic position: "IPi" vs. "Wm"

• V1 Duration: "long" vs. "short" vowels Since style has been found to have a more subtle effect on Vto-V coarticulation than the one described in the literature [START_REF] Turco | Que nous apprennent les gros corpus sur l'harmonie vocalique en français ?[END_REF], type of corpus (ESTER vs. NCCFr) was not treated as a factor in the analysis. The fixed structure of the model contained two interactions: one between V2 height and Prosodic position and one between V2 height and V1 duration. Given the very unbalanced frequency distribution of the relevant variables, we could not investigate further interactions between the various predictors. As random effects, we modelled intercepts for speakers. To avoid high Type I error rate [START_REF] Cunnings | An overview of mixed-effects statistical models for second language researchers[END_REF], by-speaker random slopes (i.e. by-speaker variability on how fixed factors affect F1) were additionally fitted. Random-slopes were, however, modelled for the effect of V2 height only, due to a problem of convergence.

P-values were obtained on the basis of Satterthwaite approximations by using the lmerTest function [START_REF] Kuznetsova | Lmertest: Tests for random and fixed effects for linear mixed effect models (lmer objects of lme4 package)[END_REF], which gives a more conservative estimate of p-values for linear regressions. Main effects of each predictor and of interactions were tested by comparing the model with a certain factor (or interaction) with a model that lacks that particular factor (or interaction) by using Likelihood ratio test as implemented in the anova()-function. Finally, R 2 values associated to each model have been calculated by using the r.squaredGLMM()function in [START_REF] Nakagawa | A general and simple method for obtaining R2 from generalized linear mixed-effects models[END_REF], whose output provides R squared values. Specifically, this function calculates R 2 marginal values (R 2 m) associated with fixed effects of the model and conditional R squared values (R 2 c), which accounts for the proportion of variance explained by both fixed and random effects of the model.

Results

The linear mixed effect model (R 2 m= .05 vs. R 2 c= .33) shows a main effect of V2 height (χ 2 (1)=42.8, p<.0001), of Prosodic position (χ 2 (2)=92.7 p<.0001), and no effect of V1 duration (p=.17) on the F1 value of V1. As illustrated in Figure 1 and2, V1 height (as measured by F1) is lowered or raised according to the height of V2 as predicted by V2-to-V1 coarticulation (or vowel height harmony) in French. More importantly, the model reveals:

• an interaction between V2 height and Prosodic position (χ 2 (1)=42.8, p<.0001): the effect of V2 height on the F1 of V1 is larger when V1 is in Wm position (β=35.1, SE=5.35, t=6.55, p<.0001, Figure 1). In other terms, V1 is more resistant to V2 coarticulation in IPi compared to Wm position;

• no interaction between V2 height and V1 duration (p=.08):

In Figure 2 the effect of V2 is shown to be similar for both long and short V1.

Discussion

The current study on French V-to-V coarticulation showed that the anticipatory effect from an upcoming vowel was smaller for target vowels sitting in a prosodically strong (IP absolute initial) position than for vowels located in a low-level (word medial) position.

These results go in line with the literature on coarticulatory variation across boundary (cf. Introduction). Prosodic-domain initial segments appear to be more resistant to coarticulation. To the extent that this coarticulatory resistance may be interpreted as being "edge"-induced or "boundary"-induced (cf. Introduction), the present results add to the previous literature in one important way. They suggest that initial positions in prosodically strong constituents are protected in a way that the prosodically strengthened segmental content is more resistant to contextual variation.

Phonetic details linked to vowel distinctiveness and vocalic contrasts have been observed to be enhanced for vowels in prosodically strong position (e.g., [START_REF] Georgeton | Domain-initial strengthening on French vowels and phonological contrasts: Evidence from lip articulation and spectral variation[END_REF], see also references therein for other languages than French) and have been taken as cues for prosodic strengthening. In light of the present results, a slightly reversed interpretation could be argued for: initial segments do not show an 'expansion' or a 'strengthening' of their spatio-temporal properties as often assumed in the literature, but rather a preservation of their distinctive, context-free, properties.

As it stands, the current study acts as a springboard for future work on prosodic effects of vowel-to-vowel coarticulation. While here we could focus our analysis on domain positions at the opposite ends of the hierarchical structure (IPi vs. Wm), in a follow-up study we are planning to conduct a more detailed acoustic and articulatory-based comparison between different prosodic positions on a controlled data-set.

Unlike prosodic boundary, the current study showed that vowel duration did not have any impact on V-to-V coarticulation: V2-to-V1 coarticulation was not stronger with temporally reduced V1. This finding goes along with previous work on effects of speaking rate ( [START_REF] Grosvald | Interspeaker variation in the extent and perception of long-distance vowel-to-vowel coarticulation[END_REF], [START_REF] Hertrich | Coarticulation in slow speech: durational and spectral analysis[END_REF]) and phonemic length contrast [START_REF] Mok | Effects of vowel duration and vowel quality on vowelto-vowel coarticulation[END_REF] on V-to-V (regressive) coarticulation. In these studies, none of these temporal effects was found to be correlated with coarticulatory variation. Furthermore, the absence of segment duration effects on V-to-V coarticulation suggests that this potential source of variation does not represent a confounding factor for the prosodically-induced coarticulatory variation that we observed here.

Conclusions and Outlook

This study investigated coarticulatory variation resulting from prosodic variation in French, a language where V-to-V coarticulation may result in an optional process of harmony. The goal was twofold: a) comparing degree of coarticulation (i.e. coarticulatory resistance) of vowels located at high vs. low-order prosodic level (IP absolute initial position vs. Word medial position); b) rule out the possibility that segment duration could be a confounding factor for vowel-to-vowel coarticulation. Though being widely acknowledged as a crucial factor of coarticulation, this study showed that duration does not exert the same influence on vowel-to-vowel coarticulation that prosodic position does.

Future articulatory-based investigations are expected to complement the current findings by looking at how prosodic boundary influences the detailed operation of the articulators involved in non-local coarticulatory interactions. This contribution would help to deepen our understanding on the still weak connection between articulatory accounts of motor control and psycholinguistic models of speech production.

Furthermore, future work should also look at the impact of these findings on speech comprehension. While we know that vowel harmony has a perceptual relevance for French listeners [START_REF] Nguyen | Perceptual relevance of longdomain phonetic dependencies[END_REF], we still do not know whether its interaction with prosodic structure would be based on the same mechanisms by which phonetic detail modulated by domain-initial strengthening assists listeners in lexical disambiguation (e.g., [START_REF] Cho | Prosodically driven phonetic detail in speech processing: The case of domain-initial strengthening in English[END_REF] for Dutch).

Figure 1 :

 1 Figure 1: F1 of V1 (as fitted by the model) as function of V2 height (high vs. low) and Prosodic position (IP initial vs. Word medial). Degree of vowel-to-vowel coarticulation can be inferred from the stiffness of the slope: greater in Wm. Whiskers represent standard errors.

Figure 2 :

 2 Figure 2: F1 of V1 (as fitted by the model) as function of V2 height (high vs. low) and V1 duration (long vs. short). Degree of vowel-to-vowel coarticulation can be inferred from the stiffness of the slope: similar for long and short vowels. Whiskers represent standard errors.

Acknowledgements

This research was funded by a research programme and innovation of the European Union Horizon 2020, through a Marie Sklodowska-Curie n° 662530 awarded to the first author and through the program "Investissements d'Avenir" overseen by the French National Research Agency, ANR-10-LABX-0083 (Labex EFL).


Dimitri Watel
email: dimitri.watel@ensiie.fr

Marc-Antoine Weisser
email: marc-antoine.weisser@centralesupelec.fr

A note on the inapproximability of the Minimum Monotone Satisfying Assignment problem

Keywords: Combinatorial optimization, Polynomial approximation, Minimum Monontone Satisfying Assignment problem

The Minimum Monotone Satisfying Assignment problem (MMSA) consists, given a monotone boolean formula ϕ, in searching for a minimum number of true variables such that ϕ is satisfied. A polynomial inapproximability ratio was given by Dinur et al. However, this ratio depends on a parameter that is not the size of the MMSA instance. It is instead the size of the problem from which the reduction is done. Consequently, it is hard to reuse this result to prove other hardness of approximability. In this paper, we deepen the previous work and prove two inapproximability ratio for MMSA depending on the size of the formula and the number of variables and we prove that MMSA cannot be polylogarithmically approximated.

Introduction

Problem 1. Minimum Monotone Satisfying Assignment (MMSA). Given a set Y of boolean variables and a monotone boolean formula ϕ, minimize the number of variables assigned to true such that ϕ is satisfied.

We call MMSA h the MMSA problem restricted to the instances in which the height of the formula is no more than h. In other words, this formula has h levels of altenating AND and OR gates, where the top levels is an AND gate. MMSA 2 is equivalent to the Set Cover problem in which, given a set X and a subset S of 2 X , we search for a minimum cover of X with sets of S. Therefore, MMSA 2 is NP-Complete [START_REF] Karp | Reducibility among combinatorial problems[END_REF] and there exists a constant c such that MMSA 2 cannot be approximated to within a c log(|Y |) ratio unless P = NP [START_REF] Feige | A threshold of ln n for approximating set cover[END_REF].

The following theorem, from Dinur et al. and introduced in [START_REF] Dinur | On the hardness of approximating label-cover[END_REF], is an harder inapproximability result for MMSA 3 .

Theorem 1 ([3], page 251). For any c < 1 2 , it is NP-hard to approximate MMSA 3 to within g c (n

) def = 2 log(n) 1- 1 log log(n) c .
A major drawback with this result is that the parameter n given in this theorem is not the size of the MMSA 3 instance. This parameter is instead the size of the problem from which the reduction is done to prove this result. As a consequence, researchers using the Theorem of Dinur et al. to prove an inapproximability result, either cite the theorem without linking the parameter n with their problem (see for example [START_REF] Chinchani | On the Hardness of Approximating the Min-Hack Problem[END_REF]), or must carefully redefine the notations [START_REF] Carr | On the redblue set cover problem[END_REF][START_REF] Gruber | Algorithmic and complexity results for boolean and pseudoboolean functions[END_REF].

Our ontributions. Firstly, as the Theorem of Dinur et al. is an important theoretical result we deepen the previous work in order to prove that MMSA 3 is hard to approximate to within a ratio depending only on the size of a formula ϕ: the number of AND gates Λ, of OR gates V and the number of boolean variables |Y |.

Secondly, we prove a theorem which has a pratical potential arising out of the Theorem of Dinur et al.: MMSA 3 is hard to approximate to within any polylogarithmic ratio depending on the number of AND gates, OR gates and the number of variables. This ratio is useful in case of a reduction from MMSA h to a problem in which the size depends polynomially on Λ, V and |Y |.

The next section is dedicated to study the function g c (n) of the Theorem of Dinur et al. Section 3 describes the links between the parameter n and the size of MMSA 3 . Finally, Section 4 contains the proofs of our results.

The function g c (n)

We prove three useful lemmas about the function g c (n) of the Theorem of Dinur et al. We first rewrite g c (n), for some c ∈]0, 1 2 [.

g c (n) = 2 log(n) ( 1- 1 (log log(n)) c ) = 2 log(n)•log(n) ( - 1 (log log(n)) c ) = 2 log(n)•2 ( -(log log(n)) 1-c )
We firstly show that, on the first hand, it is asymptotically dominated by all the polynomials and, on the other hand, that it asymptotically dominates all the polylogarithms.

Lemma 2. Let δ > 0 and 0 < c < 1 2 , then g c (n) = o(n δ ).
Proof. Let 0 < c < 1 2 and δ > 0, we are interested in the limit of gc(n) n δ

as n approaches infinity.

g c (n) n δ = 2 log(n)•2 ( -(log log(n)) 1-c ) / 2 log(n)δ = 2 log(n)• 2 ( -(log log(n)) 1-c ) -δ (1)
As

1 -c > 0 lim n→+∞ -(log log(n)) 1-c = -∞ lim n→+∞ 2 (-(log log(n)) 1-c ) -δ = -δ lim n→+∞ log(n) • 2 (-(log log(n)) 1-c ) -δ = -∞ By Equation (1) lim n→+∞ g c (n) n δ = 0 Lemma 3. Let δ > 0 and 0 < c < 1 2 , then log(n) δ = o(g c (n)).
Proof. Let 0 < c < 1 2 and δ > 0. We now give the limit of log δ (n) gc(n) as n approaches infinity.

log (n) g c (n) = 2 log log(n)•δ / 2 log(n)•2 ( -(log log(n)) 1-c ) = 2 log log(n)•   δ-   log(n)•2 ( -(log log(n)) 1-c ) log log(n)     (2) log(n) • 2 (-(log log(n)) 1-c ) log log(n) = 2 log log(n)-(log log(n)) 1-c -log log log(n) = 2 log log(n)•(1- 1 (log log(n)) c - log log log(n) log log(n) ) (3)
However, as c > 0

lim n→+∞ 1 (log log(n)) c = 0
Moreover, as log log log is asymptotically dominated by log log

lim n→+∞ log log log(n) log log(n) = 0
As a consequence,

lim n→+∞ log log(n) • 1 - 1 (log log(n)) c - log log log(n) log log(n) = +∞
Consequently, by Equation ( 3)

lim n→+∞ log(n) • 2 (-(log log(n)) 1-c ) log log(n) = +∞ lim n→+∞ log log(n) • δ - log(n) • 2 (-(log log(n)) 1-c ) log log(n) = -∞
Finally, by Equation ( 2)

lim n→+∞ log δ (n) g c (n) = 0
The following lemma shows a useful property of g c (n) that is used later in this paper. Proof. There are four constants c F , n F , c D and n D such that, for all n ≥ n D and n ≥ n

F |F | ≤ c F • g c (n) D ≤ c D (log log(n)) c Consequently |F | D n ≤ c c D •(log log(n)) c F • 2 log(n)•2 ( -(log log(n)) 1-c ) •(c D •(log log(n)) c ) • 1 n |F | D n ≤ 2 c D •log(c F )•(log log(n)) c • 2 c D •log(n)•2 ( -(log log(n)) 1-c +c•log log log(n) ) • 2 -log(n) |F | D n ≤ 2 log(n)• c D •log(c F )• (log log(n)) c log(n) + c D •2 ( -(log log(n)) 1-c +c•log log log(n) ) -1
As lim

n-→+∞ (log log(n)) c log(n) = 0 and lim n-→+∞ -(log log(n)) 1-c + c • log log log(n) = -∞ lim n-→+∞ c D • log(c F ) • (log log(n)) c log(n) + c D • 2 (-(log log(n)) 1-c +c•log log log(n)) -1 = -1 lim n-→+∞ 2 log(n)• c D •log(c F )• (log log(n)) c log(n) + c D •2 ( -(log log(n)) 1-c +c•log log log(n) ) -1 = 0 Consequently, lim n-→+∞ |F | D n = 0.

The reduction

In this section, we describe the parameters of the formula ϕ with the parameter n given in the Theorem of Dinur et al.

We use in this section the same notations as the ones describes in [START_REF] Dinur | On the hardness of approximating label-cover[END_REF]. The given reduction is from the PCP theorem. The parameters of the PCP instance are

n ∈ N, c < 1 2 , c < c, D = O((log log(n)) c ), |F | = Θ(g c (n)).
The following MMSA 3 instance is built where T (x, ψ , r |x ) is a variable. Let 0 < δ < ε, by Lemma 2

|F | = Θ(g c (n)) = O(n δ ) n|F |D = O(n 1+δ (log log(n)) c ) n|F |D = O(n 1+δ (log log(n)) c ) n|F |D = O(n 1+ε )
This gives the result for |Y |.

By Lemma 4

|F | D = o(n) n|F | D D = O(n 2 (log log(n)) c ) n|F | D D = O(n 2+ε )
And this gives the result for Λ and concludes the proof.

Main result

This section is dedicated to proving the main results of this paper. The first theorem is a rewriting of the theorem of [START_REF] Dinur | On the hardness of approximating label-cover[END_REF] with the parameters Λ, V and |Y | using the results of Lemma 5.

Theorem 6. For all ε > 0 and c > 1 2 , it is NP-hard to approximate MMSA 3 to within max(g c ( 2+ε √ Λ), g c (V ), g c ( 1+ε |Y |)).
Proof. The proof for g c (V ) is immediate by Lemma 5. We now prove that there is no g c ( 1+ε |Y |)-approximation. The last result is similar. Theorem 7. Let Q be a polynomial with three variables. Unless P = NP, there is no polynomial approximation with ratio Q(log(|Y |), log(Λ), log(V )) for MMSA 3 .

Proof. The proof is given for the following polynomial Q(x, y, z) = x δ , for some δ > 0. The proof for other polynomials are similar.

We assume that there is a Q(log(|Y |))-approximation for MMSA 3 .

Let now be a PCP instance of size n and 0 < c < c < 1 2 . We build an instance of MMSA 3 such that |Y (n)| = O(n 1+ε ) by Lemma 5. Thus (A) for all ε > 0, there are two constants k ε > 0 and n ε ∈ N such that, for every integer

n > n ε , |Y (n)| ≤ k ε • n 1+ε .
For all δ > δ, log δ is asymptotically dominated by log δ , consequently:

(B) for all ε > 0, k ε > 0, δ > δ, there is an integer n = n(ε, k ε , δ ) ∈ N such that for every integer n > n , (log

(k ε ) + (1 + ε) log(n)) δ < log δ (n).
Finally, by Lemma 3, for all 0 < c < 1 2 and δ > 0, g c (n) asymptotically dominates log δ (n), thus (C) for all δ > 0, there is an integer n δ ∈ N such that for every integer n > n δ , log δ (n) < g c (n).

We are going to use those three properties to prove the inapproximability result. Let ε > 0 and δ > δ be two real numbers. The constants k ε , n ε , n = n(ε, k ε , δ ) and n δ are given by the previous properties. We focus on the P CP instances such that n > max(n ε , n , n δ ). As a consequence, there would be g c (n)-approximation for the MMSA 3 problem, and this would be a contradiction by the Theorem of Dinur et al.

Q(log(|Y (n)|)) = log δ (|Y (n)|) By Property (A) Q(log(|Y (n)|)) ≤ log δ (k ε • n 1+ε ) Q(log(|Y (n)|)) ≤ (log(k ε ) + (1 + ε) log(n))
A consequence of such a result is that, if we now consider a reduction from MMSA h to a problem Π such that • the size s of the instances of Π is a polynomial in |Y |, Λ and V ;

• the reduction proves Π cannot be approximated to within Q(log(|Y |), log(Λ), log(V )) for any polynomial Q with Theorem 7, then we can prove Π cannot be approximated to within Q (log(s)) for any polynomial Q .

Conclusion

In this paper we deepened the inapproximability result of MMSA 3 presented in [START_REF] Dinur | On the hardness of approximating label-cover[END_REF] and gave a new inapproximability ratio only depending on the size of a formula. This allows researchers to have a pratical use of this important theoretical result.

Lemma 4 .

 4 Let c < 1 2 , |F | = Θ(g c (n)) and D = O((log log(n)) c ), then |F | D = o(n).

Remark 1 .

 1 ϕ = ψ∈Ψ r∈R ψ x∈ψ ψ ∈Ψx T (x, ψ , r |x ) The parameters satisfy: |Ψ| = n, |R ψ | = |F | D , |ψ| = D, |Ψ x | = n and the set T contains n|F |D variables. By Lemma 4, |R ψ | is polynomial. Note that there are 4 levels in this formula, however the levels 3 and 4 are two AND Gates levels and can be merged into one level. Any g c (n)-approximation for MMSA 3 could be used to solve the PCP instance in polynomial time and this proves the Theorem of Dinur et al. Lemma 5. Let ε > 0, then Λ = O(n 2+ε ), V = n and |Y | = O(n 1+ε ). Proof. The AND root gate of ϕ has |Ψ| = n children. Any OR gate has |R ψ | = |F | D children. The AND gates of level 3 and 4 have respectively |ψ| = D and |Ψ x | = n children. The number of variables of ϕ is |T | = n|F |D. Consequently, Λ = 1 + n|F | D (1 + D), V = n and |Y | = n|F |D. The result for V is proven. We now have to detail the values of n|F | D D and n|F |D.

  Lemma 5 proves that |Y | = O(n 1+ε ). As g c is a non-decreasing function, g c ( 1+ε |Y |) ≤ g c (O(n)). The conclusion follows from the property that lim n-→+∞ gc(O(n)) g c (n) = 0 for every c ∈]c; 1 2 [: a g c ( 1+ε |Y |)-approximation would lead to a g c (n)approximation and this is a contradiction by the Theorem of Dinur et al. The second theroem is a more easily to use theorem arising out of the Theorem of Dinur et al. It proves MMSA cannot be approximated to within a polylogarithmic ratio.

δ

  By Property (B)Q(log(|Y (n)|)) ≤ log δ (n) By Property (C) Q(log(|Y (n)|) ≤ g c (n)


Adrien Malaisé

Sophie Nertomb

Francois Charpillet

Serena Ivaldi

Towards collaboration between professional caregivers and robots -A preliminary study

Keywords:

Towards collaboration between professional caregivers and robots -A preliminary study

Adrien Malaisé, Sophie Nertomb, François Charpillet, Serena

Introduction

This paper reports on the preliminary results of our investigation on the use of robots by professional caregivers in a nursing facility for elderly care. The use of assisted living technologies and robots in health-care facilities, particularly for the elderly, has been advocated for decades [Jaschinski and Ben Allouch, 2015], [Topo, 2009]. It is important to investigate how a robot can be introduced in such facilities and whether it could be accepted by patients and professional caregivers. We recently started such a study focusing on our town and its numerous facilities for elderly care, to compare with similar studies in other countries [START_REF] Heerink | Assessing Acceptance of Assistive Social Agent Technology by Older Adults: the Almere Model[END_REF].

Our goal here is to evaluate how caregivers could perceive robots and which type of use they imagine for a robot to help them in their work. The attitude towards robot could influence their intention to use the robot for functional tasks or for social entertainment [START_REF] Gaudiello | Trust as indicator of robot functional and social acceptance. An experimental study on user conformation to the iCub's answers[END_REF].

We are also interested by the method they imagine to teach new movements to robots and whether they see operating the robot as a potential part of their work. Indeed, a robot has to be easily controllable by people that are not experts in robotics in such a context, and users could need to add new functions to the robots. Recently, [START_REF] Novanda | What Communication Modalities Do Users Prefer in Real Time HRI[END_REF] investigated touch, speech and gestures for teaching a robot a nursery rhyme, finding that users do not prefer a particular modality but enjoy less touching the robot. In a previous study with 40 adults we investigated the people's preference towards two different interfaces, and evaluated also their attitude towards kinestethic teaching [START_REF] Marichal | One-shot Evaluation of the Control Interface of a Robotic Arm by Non-Experts[END_REF]. In the robotics community kinesthetic teaching is a widely used method for showing new gestures to the robot and programming it by demonstration [START_REF] Billard | Robot Programming by Demonstration[END_REF]. The "teacher" is usually a robotics expert. However, there are few examples in the literature where ordinary people interact physically with the robot, and their attitudes toward robots may influence their performance in the interaction [START_REF] Ivaldi | Towards Engagement Models that Consider Individual Factors in HRI: On the Relation of Extroversion and Negative Attitude Towards Robots to Gaze and Speech During a HumanRobot Assembly Task: Experiments with the iCub humanoid[END_REF]. Therefore, we are also interested in investigating if kinesthetic teaching is perceived as an intuitive and desirable method by non-experts in robotics, especially by caregivers.

Our study was split in two phases: in the first we conducted semi-directed interviews with ordinary people, while in the second we carried out a focus group with caregivers.

Interviews

Forty voluntary adults without expertise in robotics participated to our interviews (age = 36.28 ± 12.57 ; M=20, W=20). The interviews took place in our laboratory (in Inria Nancy, France) after an interaction with the Kinova Jaco robotic arm with a joystick and a graphical user interface (GUI). The experimental protocol is described in [START_REF] Marichal | One-shot Evaluation of the Control Interface of a Robotic Arm by Non-Experts[END_REF]. We asked participants how they would like to teach new movements to a robot. The most cited method was the imitation of the human movements (n=19), with a camera or with sensors on the human arm. Seven participants cited they would use the joystick or the GUI they had already tested. The other cited methods were the use of brain-computer interface to control the robot (n=3), and the voice control (n=4). Four participants didn't cite a specific method, and thought the only way was to program directly the robot with a computer to teach new movements.

Only two participants immediately mentioned the kinesthetic teaching method. Five other participants proposed this method after thinking for some time. Interestingly, when we suggested this method to the participants, most of them said this would be efficient and easy to use for them.

We used the results of these interviews to prepare our focus groups.

Focus group with professional caregivers

We conducted a preliminary focus group with three professional caregivers (three women, age = 32 ± 1) working in the same health-care facility in Nancy, France. One of them was expert in ergonomic. The focus group lasted two hours. In the first part of the focus group, we presented two different robots: a robotic arm (Kinova Jaco) and a humanoid robot (Softbank Robotics Pepper). Figure 1 shows the pictures presented during this part. We used also a short video of each robot to show their movements. We asked to the participants which use they imagined for each robot in their professional context. In a second part, we asked how they imagined to interact with the robot in order to teach new movements.

A B

Fig. 1. The robot pictures presented during the focus group : (A) the Jaco robotic arm of Kinova, (B) the Pepper humanoid robot of Softbank Robotics.

Use of a robotic arm

After seeing the picture of the robot, the participants imagined to use this robot as a replacement for a person who cannot move his arms. After seeing the video, they said it could be used to help a patient to stand up. One participant suggested to use it as an help for meals (i.e., to help feeding the patients). It could also be used to grab objects that have fallen on the floor, or objects in height. Indeed, the participants said that patients often call them to their rooms just to pick up objects, which they perceive as a waste of time in their work. The imagined use for this robot was "functional".

Use of a humanoid robot

In contrast to the previous robot, the imagined use of the Pepper robot was more "social". They imagined to use this robot for entertainment (dancing with patients, showing photos...). Also, a reminder function was imagined, e.g., to remind the patients the time to shower. They also suggested to use it to give information, as the time or the activity of the day. However, one participant perceived this robot as a companion, but not as a true help for the caregivers. After watching the video, the participants imagined to use it as a surveillance device, especially during the night. It could promptly inform the professional caregiver in case of a detected fall.

Teaching new functions

When we asked how the participants imagined to teach new functions to the robot, their first idea was by imitation: the human makes a gesture, and the robot replicates this movement. However, they reckoned the fact that the different number of joints between the robotic arm and the human arm could make it difficult in practice. Another cited method was the voice control.

We presented in videos four types of interaction: a joystick, a GUI, an imitation interaction using the Leapmotion sensor, and kinesthetic teaching. The participants confirmed their idea that the imitation was the best option for teaching a new movement. This method was perceived easier and faster to use. However, for tasks that require precision, they said that the kinesthetic method was the best alternative. The participants said that the joystick and the GUI were slower to use. One of participants said that the joystick could be "funny" to use.

Robot acceptance in a professional context

When we asked which one of the two robots could be the most useful to use in their professional context, one participant answered the Pepper robot as it was seemingly multi-functional. Another participant said that it could be the Jaco robotic arm, as the Pepper could not pick up fallen objects on the floor, and she preferred the more functional aspect of the arm. The last participant would like a mixed between both, but preferred the Pepper if she had to choose only one, for the same reason given by the first participant (multiple functions).

The three participants said they would accept the help of a robot during their work. They perceived the robots as a help to gain more time in their work. Moreover, if a robot as the Jaco robotic arm could help to stand up the patient, the participants said it could avoid back pain: "The problem in our work is the back " ("Le problème dans notre corps de métier, c'est le dos").

All the participants said they would accept to attend a formation if it is necessary to learn how to use the robot. According to them, the benefit would be important. Moreover, if the method to teach new movements was easy and fast to use, they said they could accept to do it themselves, and not asking the technician of their facility.

Conclusion

In this paper, we report on the interviews with 40 adults about the method to teach a robot a new movement. Almost no participant suggested to use kinesthetic teaching in the interviews. However, according to the interviews and then the focus group, this method was seen as effective for some tasks.

We presented the preliminary results of our study on how professional caregivers could perceive the use of robots to help them during their work. We cannot make a general conclusion with only one focus group with three participants at this stage. However, we found some interesting results in our early investigation. Indeed, all the participants to the focus group (professional caregivers) seem keen to accept to work with robots and they acknowledge a potential benefit to the use of a robot to relieve them from the burden of some tasks. This result could be biased by the relative young age of the focus group's participants. However it encourages us to continue the investigation. We will keep conducting more focus groups with other caregivers, including families of the patients, to evaluate the acceptance of a robot as a support for caregiving, identify the best robot for their needs and the tasks where it could intervene. In the future, we plan to conduct experiments with the two robots in an ecological context to observe the impact of their presence in the health-care facilities.