Fredrik Johansson
email: fredrik.johansson@gmail.com

Numerical integration in arbitrary-precision ball arithmetic

Keywords: Numerical integration, interval arithmetic, special functions

We present an implementation of arbitrary-precision numerical integration with rigorous error bounds in the Arb library. Rapid convergence is ensured for piecewise complex analytic integrals by use of the Petras algorithm, which combines adaptive bisection with adaptive Gaussian quadrature where error bounds are determined via complex magnitudes without evaluating derivatives. The code is general, easy to use, and efficient, often outperforming existing non-rigorous software.

Introduction

Many users can attest that there is a non-negligible chance of getting an incorrect answer when asking a numerical package or computer algebra system for an approximation of a definite integral b a f (x)dx, as rapid variation, narrow peaks, non-smooth points, cancellation or ill-conditioned numerical evaluation of f are prone to break widely used heuristic numerical integration methods.

One remedy is to compute rigorous error bounds using interval arithmetic. However, little work has been done to date on efficient arbitrary-precision implementations. Here, we present a new implementation of rigorous numerical integration in Arb, a C library for ball arithmetic1 [START_REF] Johansson | Arb: efficient arbitrary-precision midpoint-radius interval arithmetic[END_REF]. The integration code is easy to use directly in C, or can be wrapped from high-level languages. For example, an interface in Sage [START_REF]The SageMath developers[END_REF] exists (thanks to Marc Mezzarobba and Vincent Delecroix), which we demonstrate by computing We obtain nearly 100 digits with a rigorous error bound in 0.04 seconds (0.02 s when using C directly). This relatively difficult test integral (f (x) changes sign 950 times) was introduced by Rump [START_REF] Rump | Verification methods: Rigorous results using floating-point arithmetic[END_REF] who observed that the quad function in Matlab took over a second only to return the erroneous 0.2511 (Rump's interval package Intlab computes 7 digits in about one second; see also [START_REF] Mahboubi | Formally verified approximations of definite integrals[END_REF]).

Algorithm and implementation

We consider integration of a function f : C → C on a segment [a, b], a, b ∈ C. We represent real numbers as mid-rad intervals (balls) [m ± r] and complex numbers as rectangles [m 1 ±r 1 ]+[m 2 ±r 2 ]i (which we also refer to as balls with slight abuse of terminology). True complex balls B(m 1 + m 2 i, r) would sometimes provide slightly better bounds, but rectangles are usually more convenient.

The user supplies the integrand f as a pointer to a C function func implementing its evaluation (we refer to the documentation for the detailed API). In effect, func gets called with the argument z and an extra flag d. If d = 0, func is to evaluate f (z) without any assumptions about regularity. If d = 1, func is to evaluate f (z) and also check that f is analytic on z, returning a non-finite ball (e.g. NaN) otherwise. For meromorphic f , the user can ignore d since f (z) automatically blows up at poles, but d needs to be handled for functions with branch cuts like √ z and log(z) (here by checking whether z overlaps (-∞, 0]). We use the Petras algorithm [START_REF] Petras | Self-validating integration and approximation of piecewise analytic functions[END_REF], which combines bisection with Gaussian quadrature of variable degree n. Error bounds for Gaussian quadrature use complex magnitudes. If f is analytic with |f | ≤ M on an ellipse E with foci ±1 and semiaxes X, Y, then

| 1 -1 f (x)dx - n k=1 w k f (x k )| ≤ M ρ -2n C ρ , ρ = X +Y , where e.g. C ρ < 50 if ρ > 1.1. The tradeoff is that a larger E increases M , with M = ∞ if E
hits a singularity of f , but also improves convergence as n → ∞. Of course, the computed bound for M will not just depend on the function f but also on the stability of its evaluation in ball arithmetic if E is large.

Degree adaptivity ensures near-optimal complexity (O(p) evaluations of f ) for analytic f at high precision p, while space adaptivity (bisection) helps if there are singularities near [a, b] or if the ball enclosures are not optimal. For piecewise analytic f with discontinuities on [a, b] the complexity is typically O(p 2 ), i.e. a bit worse but still polynomial in p. Degree or space adaptivity used alone would give 2 O(p) complexity or fail to converge for common types of integrals.

Our version of the integration algorithm can be described as follows: 2 With default settings, computing nodes takes a few milliseconds for 100-digit precision and a few seconds for 1000 digits. 3 Nodes are automatically cached, so this cost is amortized for repeated integrations at the same or lower precision (possible n are restricted to a sparse sequence ≈ 2 k/2 to avoid computing nodes for many nearby n). As an optional tuning parameter, the user can change the allowed range of n which defaults to n max = 0.5p + 60.

-Initialize sum S ← 0, subinterval work queue Q ← [(a, b)]. -While Q = [(a 1 , b 1 ), . . . , (a N , b N )] is not empty: 1. Pop (α, β) = (a N , b N ) from Q. 2. Compute the direct box enclosure I = (β -α)f ([α, β]) (evaluating f on z = [α, β] with d = 0). If I

Tolerances and evaluation limits

Besides the working precision p, the user specifies absolute and relative tolerances ε abs and ε rel . In effect, the algorithm attempts to achieve an error of max(ε abs , V ε rel ) where V is the magnitude of the integral. Reasonable values (used as defaults by the Sage wrapper) are ε abs = ε rel = 2 -p . Other values can be useful, e.g. if low accuracy is sufficient but a higher p must be used for numerical reasons. One might also set ε abs = 0 to use relative tolerance only, though for efficiency, it is better to supply ε abs ≈ V ε rel if an estimate for V is known when V ≈ 1. This Sage code shows computation of In reality, ε abs and ε rel are only guidelines and the algorithm does not strictly achieve the goal max(ε abs , V ε rel ). Indeed, due to the fixed working precision and possibly inexact parameters, the goal cannot generally be achieved. It is implied that the user will work with some guard bits and if needed adjust (p, ε abs , ε rel ) based on the reliable a posteriori information in the output ball radius.

Use of ε rel further depends circularly on V (V is essentially what we are trying to compute!), so the algorithm must guess V. A too large guess means loss of accuracy and a too small guess means unnecessary work. Our approach is to start with the tolerance ε abs and continuously update ε abs ← max(ε abs , I a ε rel ), ε abs ← max(ε abs , J a ε rel ) where |I| = [I a , I b ] and |J| = [J a , J b ] are intervals computed in steps 2 and 3; I a and J a will then be lower bounds for V (we err on the side of preserving accuracy), modulo global cancellation in the integral. As noted above, the user should exploit knowledge about V if possible since I a and J a may be pessimistic. More clever globally adaptive strategies are possible, but we settled for this simple approach in the present version.

To abort gracefully when convergence is too slow, evaluation limits include a bound on the number of calls to f (default 1000p + p 2 ) and a bound on the size N of the work queue Q (default 2p). By default, Q acts as a stack and step 4 puts the new subinterval with the larger error at the top; optionally, Q can be switched to a global priority queue, which may improve results if convergence is so slow that evaluation limits are exceeded. This has the downside of sometimes requiring N nearly as large as the number of calls to f (e.g. N ∼ p 2 ), whereas we always have N p with the stack. A more clever algorithm might use a top-level priority queue down to some depth before switching to a stack locally.

Benchmarks

We test various integrals with precision between about 10 and 1000 digits. Timings were obtained on an Intel Core i5-4300U CPU. We compare Arb to the heuristic arbitrary-precision integration routines intnum in Pari/GP [START_REF]Pari/GP version 2[END_REF] and quad in mpmath [START_REF] Johansson | mpmath version 1.0[END_REF]. Both use double exponential quadrature without adaptive subdivision, although quad is degree-adaptive. Further comparisons with other numerical and interval packages (as well as alternative methods in Pari/GP and mpmath4 ) would be useful, but out of scope for this brief overview.

We do not show the outputs, but note that in all cases, Arb computes correct balls with radius a small multiple of 2 -p . On some test cases, mpmath with default settings silently returns an inaccurate answer due to exceeding its limit on the quadrature degree, but it provides an optional mechanism to catch this. We increased the degree limit to let mpmath run to full accuracy in all cases, and have written (!) after a timing where the default is insufficient. Pari/GP is not adaptive and silently returns inaccurate answers without providing a catch mechanism or a way to increase the degree. It does provide an option to split the interval non-adaptively into 2 t parts, but it is up to the user to find a correct t. We have done so where necessary, which is also marked in the timings.

Integrals without singularities on the path

Table 1 shows examples with smooth f on [a, b]. For meromorphic f , the number of subintervals largely depends on the location of the poles and does not change with p. The "spike integral" I 1 (Figure 1) is a well known pathological example [START_REF] Cranley | On the automatic numerical evaluation of definite integrals[END_REF][START_REF] Hale | Spike integral[END_REF]; all ordinary numerical integrators we have tested (Mathematica, GSL, SciPy, etc.) give inaccurate results with default settings. This integrand has poles near the real axis, forcing many local bisections. It is a piece of cake for the Petras algorithm, but Pari/GP and mpmath converge slowly unless the user manually splits the path at the peaks. I 2 could be sped up 40% in Arb by using cos 2 (x) = 1 2 (1+cos(2x)) for wide x to bound the denominator more tightly. For entire functions (I 4 , I 5 , I 6 ), the efficiency improves with larger p since arbitrarily large bounding ellipses can be used. I 5 is Rump's example again, and I 6 (whose graph has two sharp "bends") was provided by Silviu-Ioan Filip.

The code is seen to work well with special functions. In I 3 we integrate the Lambert W function, where we need to check for the branch cut on (-∞, -1/e] in the evaluation. I 7 also illustrates integration on a complex path.

Overall, Arb is faster than Pari/GP and mpmath, despite the fact that rigorous error bounds create extra work. The speedup is in part explained by faster arithmetic and transcendental functions in Arb and lower overhead due to using C, as well as the advantage of Gaussian quadrature over the double exponential method for smooth integrands. However, if these differences are accounted for, we can still conclude that the Petras algorithm in ball arithmetic holds up extremely well for high-precision integration, on top of giving rigorous bounds.

Endpoint singularities and infinite intervals

The methods in Pari/GP and mpmath are designed to support typical integrals with infinite intervals or endpoint singularities, which often arise in applications. Arb requires finite a, b and a bounded f to return a finite result, but the user may provide a manual truncation (say

∞ 0 f (x)dx ≈ N ε f (x)dx
) to work around this restriction. Tail bounds must then be added based on symbolic knowledge about f . This is not ideal in terms of usability or efficiency, but since the Petras algorithm works well even with an endpoint very close to a singularity (or ∞), evaluating improper integrals to high precision in this way is at least feasible. 5 In Table 2, E 0 , E 1 and E 2 have algebraic or logarithmic singularities or decay, with E 1 requiring N ≈ 2 p and E 2 requiring ε ≈ 2 -p (no truncation is needed for E 0 , as f is bounded at the algebraic branch point singularity x = 1). Here Arb needs O(p) subintervals and O(p 2 ) evaluations, while the double exponential algorithm in Pari/GP and mpmath only needs roughly O(p) evaluations and therefore scales better. 6 For integrals with exponential decay (E 3 , E 4 and E 5 ), a cutoff of N ∼ p is sufficient, and here Arb retains excellent performance.

In a future extension of this work, some reasonable class of improper integrals could be supported more efficiently and conveniently (e.g. with the user providing a symbolic bound like |f (x)| < Cx α exp(-βx γ )). 5 An exception is when f has an essential singularity inducing oscillation combined with slow decay. Oscillation with exponential decay is not a problem (as in E4, E5), but integrals like

1 0 sin(1/x)dx = ∞ 1 sin(x)/x 2
(not benchmarked here) require 2 O(p) work, so we can only hope for 5-10 digits without specialized oscillatory algorithms. 6 As a means to improve performance, we note the standard trick of manually changing variables to turn algebraic growth or decay into exponential decay. Indeed, x → sinh(x) gives E1 = E3. Similarly x → tanh(x) and x → e -x can be used in E0, E2.

Table 3. Integrals with point discontinuities in f or f . Here p(x) = x 4 + 10x 3 + 19x 2 -6x -6 in D0, and u(x) = (x -x -1 2 ), v = max(sin(x), cos(x)) in D3. For D3, the function evaluation limit had to be increased for convergence at p = 3333.

Piecewise and discontinuous functions

Piecewise real analytic functions can be integrated efficiently using piecewise complex analytic For example, |x| on R extends to the function √ z 2 of z = x + which equals z in the right plane and -z in the left plane with a branch cut on Re(z) = 0. 7 We provide as library methods such extensions of sgn(x), |x|, x , x , max(x, y), min(x, y), with builtin branch cut detection.

Table 3 shows integrals with mid-interval jumps or kinks, including one complex integral crossing a branch cut discontinuity (D 2 ). The example D 0 , where p(x) changes sign once on [0, 1], is due to Helfgott (see comments in [START_REF] Mahboubi | Formally verified approximations of definite integrals[END_REF]).

We see that a mid-interval singularity leads to use of O(p) subintervals and O(p 2 ) evaluations to isolate the problematic point by bisection. With k such points (D 1 and D 3 ), the cost simply increases by another factor k, and the user may have to raise the evaluation limits accordingly to let the algorithm complete (which we did for D 3 ). In contrast, Pari/GP and mpmath cope poorly with midinterval singularities and cannot achieve high accuracy on these examples unless the user manually splits the interval precisely at the problematic points.

Complex analysis

We conclude by illustrating integration as a tool for complex analysis. First, we consider computing derivatives via the Cauchy integral formula. Denote by ℘(z; τ ) = ∞ n=-2 a n (τ )z n the Weierstrass elliptic function for the lattice (1, τ ). We fix τ = i (placing the poles of ℘ at the Gaussian integers) and compute the Laurent coefficients a n = 1 2πi γ z -n-1 ℘(z)dz by integrating along the square connecting ±0.5 ± 0.5i. We ignore symmetry and compute all four segments. With p = 333, some results are (note that a -1 = a 100 = 0 and all a n are real): We lose about n bits of precision to cancellation due to the integrand magnitude growing with n. Apart from this, the difficulty increases quite slowly with n: a -2 takes 0.67 s while a 98 and a 100 take 0.85 s at this precision. The more numerically useful formula on the right, where ε > 0 now is arbitrary, is a well-known consequence of the functional equation, where θ(T ) is the Hardy theta function. We set ε = 99 (!) so that only the horizontal segment is difficult, and evaluate the integrals with ε abs = 10 We obtain balls that provably determine N (T ), and the method scales reasonably well. Unfortunately, the evaluation of ζ(s) in Arb is currently not well tuned for all s, which makes large T slower than necessary and can make this computation extremely slow with slightly different settings. In general, for complicated integrals, the user may need to customize the integrand evaluation to handle wide balls or large parameters optimally for a given path and precision.

8 0

 8 sin(x + e x ) dx: sage: C = ComplexBallField(333) # 333-bit precision sage: C.integral(lambda x, d: sin(x+exp(x)), 0, 8) [0.347400172657247807879512159119893124657456254866180183885492713616748 21398878532052968510434660 +/-5.97e-96]

1 0

 1 e -1000+x sin(10x)dx: sage: C = ComplexBallField(64); f = lambda x, _: exp(-1000+x)*sin(10*x) sage: C.integral(f, 0, 1) [+/-4.09e-434] # time 0.013 ms sage: C.integral(f, 0, 1, abs_tol=0) [1.574528586972758e-435 +/-7.36e-451] # time 1.1 ms sage: C.integral(f, 0, 1, abs_tol=exp(-1000)/2^64) [1.574528586972758e-435 +/-7.27e-451] # time 0.38 ms Conversely, for a large integrand: sage: f = lambda x, _: exp(1000+x)*sin(10*x) sage: C.integral(f, 0, 1) [6.11102916709322e+433 +/-1.98e+418] # time 1.1 ms sage: C.integral(f, 0, 1, abs_tol=exp(1000)/2^64) [6.11102916709322e+433 +/-1.95e+418] # time 0.39 ms

Fig. 1 .

 1 Fig.1. Left: f (x) = sech 2 (10(x-0.2)) + sech4 (100(x-0.4)) + sech6 (1000(x-0.6)), with subintervals used by Arb. Right: complex ellipses used. The dots show the poles of f .

  a[-2] = [1.00000000000000000000000... +/-3.57e-98] + [+/-1.89e-98]*I a[-1] = [+/-4.11e-98] + [+/-2.57e-98]*I a[2] = [9.45363600646169261465306... +/-4.44e-97] + [+/-2.48e-97]*I a[98] = [395.999999999999648281345... +/-2.90e-68] + [+/-1.17e-68]*I a[100] = [+/-4.95e-68] + [+/-4.95e-68]*I

  As a second example, the number N (T ) of zeros ρ k of the Riemann zeta function ζ(s) on the box [0, 1] + [0, T ]i can be computed via the argument principle N (T )the boundary of [-ε, 1 + ε] + [0, T ]i (plus an excursion for the pole at s = 1, whence the -1 term).

Table 1 .

 1 Integrals without singularities on [a, b]. Timings (Pari/GP, mpmath, Arb) are in seconds. Sub = number of terminal subintervals (requiring no further bisection) used by Arb, Eval = total number of integrand evaluations used by Arb.

	p Pari/GP	mpmath Arb	Sub Eval Pari/GP mpmath Arb	Sub Eval
			I0 =	1 0 1/(1 + x 2 )dx		I1 =	1 0	3 k=1 sech 2k (10 k (x -0.2k)) dx
	32 0.00039	0.00057 0.000025 2	32 0.54 (t = 8) 1.9 (!)	0.0030 49	795
	64 0.00039	0.0011		0.000036 2	52 0.54 (t = 8) 5.0 (!)	0.0051 49 1299
	333 0.0043	0.0058		0.00018	2	188 12 (t = 9)	38 (!)	0.038	49 4891
	3333 1.0		0.13			0.014	2 2056 3385 (t = 9) -	8.7	49 48907
		I2 =	π 0 x sin(x)/(1+cos 2 (x))dx		I3 =	1000 0	W0(x)dx
	32 0.00077	0.0021		0.00033 14	229 0.0037	0.012	0.00041 12	163
	64 0.00077	0.0046		0.00054 14	373 0.0037	0.032	0.00093 12	273
	333 0.0088	0.037		0.0040	14 1401 0.052 (t = 1) 0.25	0.0099 12 1109
	3333 2.2		4.4			1.0	14 14401 11 (t = 2)	25	1.3	12 12043
			I4 =	100 0	sin(x)dx			I5 =	8 0 sin(x + e x ) dx
	32 0.0012 (t = 1) 0.0019		0.000047 1	53 0.063 (t = 6) 0.23 (!) 0.0048 33 2115
	64 0.0012 (t = 1) 0.0014		0.000074 1	72 0.063 (t = 6) 0.25 (!) 0.0055 27 2307
	333 0.015 (t = 1) 0.018		0.00030	1	139 0.22 (t = 4) 0.58 (!) 0.017	22 4028
	3333 2.0	I6 =	0.71 -1 e -x erf 1	0.032 √ 1250 x + 3 2 dx 1	526 14 (t = 2)	12 I7 =	1.1 1+1000i 1 Γ(x)dx	8 10417
	32 0.024 (t = 3) 0.018 (!) 0.0025	7	297 0.031 (t = 2) 0.028	0.00076 11	103
	64 0.024 (t = 3) 0.057 (!) 0.0055	6	438 0.054 (t = 3) 0.093	0.0035 12	280
	333 0.50 (t = 3) 0.22			0.047	4	791 0.65 (t = 3) 1.1	0.081	14 1304
	3333 173 (t = 2)	466			5.7	2 2923 561 (t = 3) 847	48	14 16535

Table 2 .

 2 Improper integrals and integrals with endpoint singularities. For integration with Arb, all improper integrals (i.e. excluding E0) have been truncated manually at a lower bound ε or upper bound N , chosen so that the omitted part is smaller than 2 -p .

	p Pari/GP mpmath Arb E0 = 1 0 √ 1 -x 2 dx Sub	Eval Pari/GP mpmath Arb E1 = ∞ 0 1/(1 + x 2 ) dx Sub	Eval
	32 0.00041 0.00055 0.00022 22	234 0.00060 0.0010	0.00079	94	997
	64 0.00041 0.00067 0.00057 44	674 0.00060 0.0012	0.0022	190	2887
	333 0.0044	0.0060	0.015 223	12687 0.0068	0.011		0.048	997	51900
	3333 0.94	0.18		6.6	2223 1187293 1.7	0.24		27	9997 4711128
		E2 =	1 0 log(x)/(1 + x)dx		E3 =	∞ 0 sech(x) dx
	32 0.00081 0.00080 0.00042 34	361 0.0011	0.0019	0.00017	9	144
	64 0.00081 0.00094 0.0012 67	1026 0.0011	0.0043	0.00032	10	251
	333 0.011	0.011	0.038 336	19254 0.013	0.098		0.0030	14	1277
	3333 1.7	1.08		106	3336 1787191 3.5	3.3		0.95	17	16593
		E4 =	∞ 0 e -x 2 +ix dx		E5 =	∞ 0 e -x Ai(-x) dx
	32 0.0014	0.0067	0.00011 1	71 -	0.19		0.0028	4	269
	64 0.0014	0.016	0.00018 1	98 -	0.91 (!) 0.012	9	842
	333 0.017	0.13		0.0016	2	397 -	26 (!)		0.94	124	24548
	3333 4.7	7.1		0.47	4	3894 -	10167 (!) 502	1205 709889

  -6 :

	T	p Time (s) Sub Eval N (T )
	10 3 32 0.51	109 1219 [649.00000 +/-7.78e-6]
	10 5 32 12	353 4088 [138069.000 +/-3.10e-4]
	10 7 48 42	391 4500 [21136125.0000 +/-5.53e-5]
	10 9 48 1590	677 8070 [2846548032.000 +/-1.95e-4]

Arb (http://arblib.org) is open source (GNU LGPL) software. For documentation and example code related to this paper, see http://arblib.org/acb_calc.html.

Clenshaw-Curtis or double exponential quadrature could be used instead of Gaussian quadrature, but typically require more points for equivalent accuracy. We could also use Taylor series, but this makes supplying f more cumbersome for the user, and computing f, f . . . , f (n) tends to be more costly than n evaluations of f .

In benchmark results, we omit the first-time nodes precomputation overhead.

For example, mpmath provides quadgl for Gaussian quadrature, which is 2-3 times faster on some examples, but its precomputations are prohibitive at high precision.

This works for integrating |f | when f is real, but since | • | on C is not holomorphic, integrating |f | for nonreal f must use direct enclosures, with 2 O(p) cost. In that case, the user should instead construct complex-extensible real and imaginary parts f = g+hi (e.g. via Taylor polynomials if no closed forms exist) and integrate g 2 + h 2 .


Brigitte Bigi
email: brigitte.bigi@lpl-aix.fr

Katarzyna Klessa
email: klessa@amu.edu.pl

Automatic Syllabification of Polish

Keywords: automatic syllabification, syllabification rules, speech annotation, free software tools

This paper presents an approach to automatic detection of syllable boundaries for Polish speech based on a phonetized text input. First, we discuss selected issues of syllable structure in Polish with a special focus on the needs of rule-based automatic insertion of syllable boundaries. We describe and verify an existing rule-set for Polish, which is subsequently used as an input information for automatic syllabification with SPPAS, a freely available multiplatform software tool. Then, the applied syllabification methodology is described and illustrated with examples obtained with a Polish speech corpus. Finally, the paper provides information about the syllabification module for Polish that has been implemented as one of the latest extensions of SPPAS.

Introduction

Despite controversies regarding the definition of syllable, e.g., [START_REF] Laver | Principles of phonetics[END_REF], [START_REF] Roach | English Phonetics and Phonology: a practical course[END_REF], and the discussion over its role in speech technology [START_REF] Kishore | Unit size in unit selection speech synthesis[END_REF], [START_REF] Hu | Speech recognition using syllable-like units[END_REF], the syllable is credited as a linguistic unit conditioning both segmental (e.g., consonant or vowel lengthening) and prosodic phonology (e.g., tune-text association, rhythmical alternations) [START_REF] Campbell | Syllable-based segmental duration[END_REF], [START_REF] Roach | On the distinction between 'stresstimed'and 'syllable-timed'languages[END_REF]. Automatic annotation on the syllable level represents a valuable tool for quantitative analyses of large speech data sets.

While the phonological structure of the syllable is similar across different languages, phonological and phonotactic rules of syllabification are language-specific. Automatic approaches to syllable detection have thus to incorporate such constraints to precisely locate syllable boundaries. The question then arises of how to obtain an acceptable syllabification for a particular language and for a specific corpus (a list of words, a written text or transcripts of an oral corpus of more or less casual speech).

Although a number of automatic syllabifiers are currently available online as freeware for some languages (e.g., for French, English or German), the availability of such resources for Polish is still limited. The present work aims at filling this gap by proposing a freely available automatic segmentation tool implemented as a new module in SPPAS [START_REF] Bigi | SPPAS: a tool for the phonetic segmentations of Speech[END_REF].

The main aspect of the SPPAS automatic syllabification reported in this paper is as follows:

• to propose a generic and easy-to-use tool to identify syllabic segments from phonemes;

• to propose a generic algorithm, then a set of rules for the particular context of Polish spontaneous speech.

In this context, "generic" means that the phone set, the classes and the rules are easily changeable; and "easy-touse" means that the system can be used by any user.

Section 2 of the paper introduces selected Polishspecific issues related to the syllable that are potentially relevant for the task of constructing rules for automatic syllabification. Section 3 describes the methodology and implementation of the new, freely available syllabification module in SPPAS, while Section 4 summarizes the study and outlines the necessary future work.

Establishing a rule-set for automatic syllabification of Polish

Polish is known to have a rich consonant inventory and to allow complex consonant clusters to exist within utterance structures both word-initially, word-internally, and word-finally. Many 4-5-element clusters can be easily found within words occurring in typical Polish texts ( Śledziński, 2013), and when cross-word sequences are considered, the clusters can be even longer, reaching e.g., eight consonantal elements such as in the phrase: sierść z pstrym wzorem (Eng. 'fur of motley pattern') where the SAMPA [START_REF] Wells | SAMPA computer readable phonetic alphabet. Handbook of standards and resources for spoken language systems[END_REF] transcription for the underlined fragment would be /r s' ts' s p s t r/. Obviously, in spontaneous speech various types of reductions or elisions might be expected, resulting in simplification of such clusters, but anyway, their proper pronunciation would not pose serious problems for Polish native speakers.

Finding the optimal location for syllable boundaries appears particularly challenging in case of languages characterized by complex consonant clusters. The departing points for syllabification are usually associated with two principles, widely discussed in the subject literature, i.e. the Sonority Sequencing Principle (sonority rise within the syllable onset and its fall within the coda, the nucleus being the most sonorous element) [START_REF] Selkirk | On the major class features and syllable theory[END_REF] and the Maximal Onset Principle (assigning intervocalic consonants to the syllable onset unless it contradicts the sonority principle) [START_REF] Kahn | Syllable-based generalizations in English phonology[END_REF]. Unconditioned application of both of the principles might become problematic in practice, e.g., because of the same sonority level in neighbouring consonants or simply due to the number of consonants in a sequence. Various approaches have been reported so far for Polish corpus-based research. A detailed report of a corpus-based analysis of Polish syllables and consonant clusters can be found in ( Śledziński, 2013) who postulates, among others, postulating among others, purposeful violation of one or both of the principles due to morphological constraints. Other researchers prefer to primarily use the sonority principle, together with a number of additional language-specific constraints [START_REF] Malisz | Acoustic-phonetic realisation of Polish syllable prominence: a corpus study. Speech and Language Technology. Rhythm, melody and harmony in speech[END_REF].

In the present study, we make use of a list including above 1800 phoneme sequences with boundary placement information (henceforth referred to as the syllable pattern list). The list was constructed manually based on the analysis of subject literature (e.g., [START_REF] Rubach | Syllable structure assignment in Polish[END_REF], [START_REF] Szpyra-Kozłowska | The sonority scale and phonetic syllabification in Polish. Biuletyn Polskiego Towarzystwa Językoznawczego[END_REF], ( Śledziński, 2007)) and subsequently refined and extended based on experiences gained during annotation of several speech databases for Polish such as [START_REF] Klessa | Speechlabs ASR. Ppolish lexical database for speech technology: Design and architecture[END_REF] or (Klessa et al., 2013b). For most of the patterns, the boundary positions are defined according to the Maximal Onset Principle on condition that they do not violate the sonority hierarchy (following the approach used e.g., by [START_REF] Klessa | A study of chosen temporal relations within syllable structure in Polish[END_REF].

The current version of the list has been found to be sufficient to successfully syllabify a number of Polish transcripts derived from annotations of spoken language corpora composed both of read narratives and quasispontaneous dialogues or monologues. A single entry in the list consists of:

• a sequence of transcription labels for consonants located between two vowels or between a vowel and a pause; we use SAMPA [START_REF] Wells | SAMPA computer readable phonetic alphabet. Handbook of standards and resources for spoken language systems[END_REF] as the phonetic alphabet in an extended version (Demenko et al., 2010);

• two V labels representing vowels (without distinguishing between particular vowel labels);

• a boundary separator.

The pattern list is used as one of the components in Annotation Pro software tool (Klessa et al., 2013a). Syllable boundaries are inserted into a previously phonetized input string (the phonetization needs to be done either manually or with an external tool). In case of a missing syllable pattern, the software displays a report dialogue window and it is possible for the user to add the missing pattern to the list. As it was mentioned above, the current version of the list suffices for syllabification of standard texts but the possibility to add non-default patterns might be still helpful for users automatically processing non-standard texts, e.g., when constructing test signals for the needs of applications for measuring and fitting hearing aids where many atypical sequences may occur (a recent work for Polish speech test data has been reported by [START_REF] Habasińska | Stworzenie polskiego testowego sygnału mowopodobnego do wykorzystania w miernictwie i dopasowaniu aparatów słuchowych (En. The development of the Polish speech test signal for measuring and fitting hearing aids)[END_REF].

The syllabification method used in Annotation Pro is based on a very straightforward boundary insertion algorithm. The algorithm performs a pattern matching procedure using the whole list of syllable patterns as a reference to match with the sequences found in the transcribed text. No generalisation or grouping of the rules has been implemented. The pattern-matching process is designed so that it always begins with the longest pattern in the list and if no match is found, an attempt is made to match a shorter one. The constraints for the syllable boundary insertion are as follows:

1. a syllable may include only one vowel label; 2. an acoustic pause is a syllable boundary; 3. a word boundary reflected by a space in orthography is a syllable boundary with the exception of word sequences with the Polish prepositions w and z (Eng. 'in' and 'from/with') which are orthographically spelt as separate units, e.g., 'w domu' (Eng. 'at home') but do not constitute separate syllables. The resulting syllabification in such case would be /vdo/ /mu/.

A more detailed discussion of the above syllabification algorithm is beyond the scope of the present paper. Here, we use the syllable pattern list as an initial input for developing a new, class-based set of rules for the Polish SPPAS module.

SPPAS syllabification: Method description

In this section, we report on the adaptation of a rulebased system for automatic syllabification of phoneme strings of the size greater than a graphic word. The system was initially developed for French [START_REF] Bigi | Automatic detection of syllable boundaries in spontaneous speech[END_REF] and then adapted for Italian [START_REF] Bigi | A generic tool for the automatic syllabification of italian[END_REF]. It is here adapted to Polish.

The system proposed in this paper is included in SP-PAS [START_REF] Bigi | SPPAS: a tool for the phonetic segmentations of Speech[END_REF], a tool distributed under the terms of the GNU Public License1 . It is implemented using the programming language Python 2.7. Among other functions, SPPAS offers an automatic speech segmentation at the phone and token levels for French, English, Spanish, Italian, Catalan, Polish, Mandarin Chinese, Cantonese, Taiwanese and Japanese. The problem we deal with is the automatic syllabification of a phoneme sequence. The proposed phoneme-tosyllable segmentation system is based on 2 main principles (Figure 1):

1. a syllable contains a vowel, and only one; 2. a pause is a syllable boundary. As in the initial system for French, we group phonemes into classes and establish language-specific rules dealing with these classes. The identification of relevant classes is then very important.

The following classes were defined for Polish based on the contents of the syllable patterns list described in the previous section of this paper:

V -Vowels: a e e˜i o o˜u y G -Glides: j w L -Liquids: l r O -Occlusives: p t k b d g Q c F -Fricatives: dz dZ f v x tS ts ts' dz' z z' Z S -Fricatives: s' s S N -Nasals: n n' m N J Uppercase bold-letters indicate the abbreviations used for classes throughout this paper. The letter C is also used to mention one of G, L, O, N, F, S.

The system firstly checks if the observed sequence of classes corresponds to an exception. If not, the general rules are applied (see Table 1).

For VCCV, the exception rules are:

• VOCV is segmented as V.OCV • VFCV is segmented as V.FCV • VSCV is segmented asV.SCV, except for C=S • VCGV is segmented as V.CGV For VCCCV, the exception rules are: SPPAS also offers the possibility to fix segmentation in a set of specific rules that deal with phoneme sequences, to which our general or exception rules do not apply. that in some cases, rules are not relevant. These specific rules are not used for Italian and just a few are fixed for French. However, due to the large number of consonant clusters in Polish, these specific rules on phonemes sequences are widely used:

• VOOCV is segmented asV.OOCV • VFFGV is segmented as V.FFGV Observed sequence Segmentation rule 1 VV V.V 2 VCV V.
• 89 specific rules of phoneme sequences in VCCV;

• 135 specific rules of phoneme sequences in VCCCV;

• 86 specific rules of phoneme sequences in VCCCCV;

• 20 specific rules of phoneme sequences in VCCC-CCV;

Then, it represents a total of 330 specific rules that correspond to 18% of the pattern list defined in the previous section. The general rules and the exception rules previously defined cover all the other cases. Finally, in the system described in [START_REF] Bigi | Automatic detection of syllable boundaries in spontaneous speech[END_REF], the syllabification is performed between 2 pauses (as defined in the main principles). From this system, we added the possibility to perform the syllabification between any kind of boundaries. In such case, a "reference tier" is given by the user to the system. Table 2 Of course, the reference tier can contain any type of annotation (we used word tokens in the example, but prosodic contours, syntactic segments, etc. can be used if their annotation is available). The use of tokens is particularly relevant for Polish. Figure 3 illustrates the result SPPAS can produce.

In SPPAS, a simple text file that the user can change as needed contains the phoneset and the rules for the syllabification process.

Conclusion & future work

This paper describes an implementation of an automatic syllabification system for Polish. The implemented functionality is freely available as part of SPPAS software [START_REF] Bigi | SPPAS: a tool for the phonetic segmentations of Speech[END_REF]. The first tests of its performance have been conducted using the conversational speech recordings from the Paralingua corpus (Klessa et al., 2013b), however a more systematic evaluation is a necessary further step. An interesting future task would also be a comparison of the output of automatic syllabification using the two different methodological approaches: the generalised class approach implemented in SPPAS vs. the straightforward pattern-matching method used in Annotation Pro (Klessa et al., 2013a).

An additional outcome of the reported study was an improvement of the Polish syllable pattern list mostly related to the removal of unnecessary patterns (duplicates or spelling errors).

In the course of the present work we have also developed import/export modules to enable data transfer between the native formats of Annotation Pro and SPPAS. Consequently, it is now possible to use SPPAS syllabification output also within Annotation Pro, not only for Polish but also for all other languages available in SP-PAS. Moreover, thanks to the interoperability between the two tools, another types of analyses become supported, e.g., combined studies based on linguistic information automatically generated with SPPAS (e.g., part-of-speech tagging or prosodic labelling) with perception test results or perception-based annotations obtained with Annotation Pro (see Figure 4 for an example view including syllabified data and the graphical representation of the feature space, useful for perception tests).

Figure 1 :

 1 Figure 1: Main principles ("#" denotes a pause)

Figure 2 :

 2 Figure 2: SPPAS: Graphical User Interface with syllabification options

Figure 3 :

 3 Figure 3: SPPAS output example on a read sentence in Polish.

  shows an example when the time-aligned tokens are used as a reference tier.

	segment type sentence	phonemes	syllables
	sentence	do domu	/dodomu/	do.do.mu
		do stołu	/dostowu/	dos.to.lu
	token	do.domu /do/ /domu/ do.do.mu
		do.stołu /do/ /stowu/ do.sto.wu
	Table 2: Syllabification into segments, without changing
	the rules.

See: http://www.gnu.org/licenses/gpl-3.0.en.html for details


Brigitte Bigi
email: brigitte.bigi@lpl-aix.fr

Jorane Saubesty
email: jorane.saubesty@blri.fr

Searching and retrieving multi-levels annotated data

Keywords: software, multi-levels annotations, filtering

The annotation of recordings is related to many Linguistics subfields as Phonetics, Prosody, Gestures or Discourse... Corpora are annotated with detailed information at various linguistic levels thanks to annotation software. As large multimodal corpora become prevalent, new annotation and analysis requirements are emerging. This paper addresses the problem of exploring annotations in order to extract multimodal data in the linguistic field ranging from general linguistic to domain specific information. The answer choose to fulfill this purpose is a useroriented approach: the data can be extracted without any specific knowledge or skill. The paper exposes two ways to filter the annotations by a predicative approach: 1/ single filters, i.e. search in one tier depending of the data content, by the extraction of the time values and the duration; 2/ relation filters, i.e. search on annotations of a tier in time-relation with annotations of another one. This system is distributed in SPPAS software, under the terms of a public license.

Introduction

When people communicate: gestures, postural shifts, facial expression, backchannel continuers such as "mm-hmm", spoken turns and many more, all together work in concert to bring about mutual understanding. Annotating recordings of people communicating may therefore involve many Linguistics subfields such as Phonetics, Prosody, Gestures or Discourse... As a consequence, the last ten years or so have witnessed a real increase of linguistic annotated data. Whereas few years ago it was common to formulate linguistic models on the basis of rather limited data, today it is becoming more and more expected for linguists to take into account large quantities of empirical data, often including several hours of recordings. As a consequence, a number of software for the manual annotation of audio and/or video recordings have become available, such as Anvil [START_REF] Kipp | Anvil, DFKI, German Research Center for Artificial Intelligence[END_REF], Elan [START_REF]ELAN -linguistic annotator. language archiving technology portal[END_REF], Praat [START_REF] Boersma | Praat: Doing phonetics by computer[END_REF], Transcriber [START_REF] Transcriber | A tool for segmenting, labeling and transcribing speech[END_REF] or Exmaralda [START_REF] Schmidt | Exmaralda[END_REF], to name just some of the most popular tools, all of which are both free and multi-platform. Furthermore, linguists need tools for the automatic annotation, including the alignment of the speech recording with a phonetic transcription of the speech, as SPPAS [START_REF] Bigi | SPPAS: a tool for the phonetic segmentations of Speech[END_REF].

As large multimodal corpora become prevalent, new analysis requirements emerge. Multimodal analysis has become a crucial part of research, teaching and practice for a wide range of academic and practical disciplines. The difficulties of multimodal analysis are visible in most of the works that explore this field. Multimodal annotation requires the possibility to encode many different information types, from different domains, with different levels of granularity [START_REF] Jewitt | Handbook of multimodal analysis[END_REF].

"Corpora that include time-based data, such as video and marking gestures, make annotation and analysis of language and behavior much more complex than analysis based solely on text corpora and an audio signal" [START_REF] Bigbee | Emerging requirements for multi-modal annotation and analysis tools[END_REF]. Thus, nowadays one of the biggest barriers with which the linguists must cope, is not the storage of data, nor its annotation, but rather its exploration.

In addition to annotation, some tools provide statistical analysis capabilities. A minimum capability required is to search for annotated entities and their relationships [START_REF] Bigbee | Emerging requirements for multi-modal annotation and analysis tools[END_REF]. Generally, different annotation tools are designed and used to annotate the audio and video contents of a corpus that can later be merged in query systems or databases [START_REF] Abuczki | An overview of multimodal corpora, annotation tools and schemes[END_REF]. With the help of multimodal corpora searches, the investigation of the temporal alignment (synchronized co-occurrence, overlap or consecutivity) of gesture and speech has become possible [START_REF] Abuczki | An overview of multimodal corpora, annotation tools and schemes[END_REF]. "Obviously, the raison d'être of annotation in general is to allow linguists to retrieve all and only all instances of a particular phenomenon" [START_REF] Gries | Linguistic annotation in/for corpus linguistics[END_REF].

The question of multi-levels filtering for linguistic annotated resources covers different aspects. It firstly requires a representation framework making it possible to compare, and eventually merge, different annotation schemes from different annotation tools. The basic structures of speech/video annotated data are "tiers" or "tracks" of annotations. Thus, speech/video annotation tools rely on this formalism because the Tier representation is appropriate to any multimodal annotated data given its genericity and flexibility and that it simply maps the annotations on the timeline. In the context of such tools, a Tier is a series of Annotation instances, each one defined by a temporal localization (an interval or a point) and a label. Obviously, due to the diversity of linguistic phenomena, annotation tools lead to a variety of models, theories and formalisms. This diversity results in heterogeneous description formats, each tool developing its own framework. Then, even if some are compatible, none of the annotation tools are directly interoperable, each one using a native format, some of them on top of XML, some others developing an ad hoc markup language. The heterogeneity of such annotations has been recognized as a key problem limiting the interoperability and re-usability of Natural Language Processing tools and linguistic data collections.

This paper focuses on the problem of searching and retrieving data from multi-levels annotated corpora. After a review of the main tools allowing to built queries in a multimodal annotated corpus, this paper presents the specifications of a software development according to eight criteria it must respect. The system proposed in this paper is a component named DataFilter in SPPAS software [START_REF] Bigi | SPPAS: a tool for the phonetic segmentations of Speech[END_REF], described in Section 3. The method to search and retrieve data is based on a predicative approach allowing the definition of 2 types of filters: 1/ single filters, i.e. search in one tier depending of the data content, by the extraction of the time values or the duration (Section 4); 2/ relation filters, i.e. search on annotations of a tier in time-relation with annotations of another one (Section 5). Finally, Section 6 shows with a concrete study the benefit of the proposed software.

Background and motivations

A query is a request for a subset of all annotation elements, given some constraint. A query language (QL) is a programming language allowing to write queries. In the context of extracting multi-levels annotated data, multi-levels annotations can quickly become cluttered, so that the user needs query functionality to efficiently find relevant information. The following explores some popular and freely available tools.

Praat allows to paint intervals in green color, labels matching a given pattern with one of the following criteria: is equal to, is not equal to, contains, does not contain, starts with, does not start with, ends with, does not end with, matches a regular expression.

EXAKT (EXMARaLDA Analysis-and Concordance Tool) is the query and analysis tool for EXMARaLDA corpora, and can also be used for corpora created with other tools as Transcriber or Elan. Labels of annotations can be search in the corpus using regular expressions. It allows to save query results (HTML, text) or export them to other applications (e.g. Excel).

Elan proposes an advanced search form. It allows cascading constraints on the labels of the annotations and/or on relations between intervals. The relations are: is inside, overlaps, overlaps only begin time, overlaps only end time, is within...around, is within...around begin time of, is within...around end time of. The result is a list of filtered annotations the user can click on to visualize; it can also be saved as text file.

ANVIL internally maps the user's annotations to a temporary SQL database that is kept in sync at all times. Constraints can be formulated in SQL syntax. Labels of annotations can be queried using regular expressions. ANVIL also implements seven of the Allen relations [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] to compare intervals: equals, before, meets, overlaps, starts, finishes and during. In addition, the user can specify a tolerance limit in seconds. To spare the user from using long and complex SQL expressions, it implements a special syntax to ask for annotations from two tiers that are characterized by a certain temporal relationship.

The ANNIS2 system [START_REF] Zeldes | ANNIS: a search tool for multi-layer annotated corpora[END_REF] proposes a query language (QL) including exact and regular expression matching on words forms and annotations, together with complex relations between individual elements, such as all forms of overlapping, contained or adjacent annotation spans, hierarchical dominance (children, ancestors, left-or rightmost child etc.) and more. Alternatively to the QL, data can be accessed using a graphical query builder. The result can be saved as text file or ARFF file.

To sum-up, the previously mentioned annotation tools offer the possibility to search or to retrieve annotations given some constraints. However, none of them fulfills the whole list of the following specifications a system should includes:

• allowing to import multi-levels annotated data from most of the existing annotation tools; • providing the filtered result in the form of a new annotation tier; • dealing with interval tiers as well as point tiers;

• allowing to export the filtered tier(s) in most of the existing annotation tools; • allowing to filter multiple files at once; • proposing both a scripting language and a Graphical User Interface (GUI); • being powerful enough to meet the reasonable needs of end-users; • can be used without requiring any XML-related or QLrelated knowledge or skill;

DataFilter in SPPAS

The system proposed in this paper is implemented as a component named DataFilter in SPPAS [START_REF] Bigi | SPPAS: a tool for the phonetic segmentations of Speech[END_REF], a software for "Automatic Annotation of Speech" and distributed under the terms of the GNU Public License. It is implemented using the programming language Python. This software fulfills the specifications listed in [START_REF] Dipper | Simple annotation tools for complex annotation tasks: an evaluation[END_REF]: it is a linguistic tool, free of charge, ready and easy to use, it runs on any platform and it is easy to install, the maintenance is guaranteed and it is XML-based.

Our proposal is to use the simplest level of representation , which is independent from the constraints of the coding procedure and the tools. Requests are based on the common set of information all tool are currently sharing. Basic operations are proposed and their combination allows the data to be requested, even by non-experts. Such a system fulfills the eight specifications mentioned in Section 2.

The framework implemented in this software to represent multi-levels annotated data is particularly suitable in the context of this paper to compare bounds of intervals or points between the various tiers: SPPAS solves the problem of the imprecision of annotations for each domain. Indeed, it allows to represent a bound as a tuple (M, R), where M is the midpoint value and R is a radius value, i.e. the vagueness of the point, as described in [START_REF] Bigi | Representing multimodal linguistics annotated data[END_REF]. Consequently, each boundary of the annotations is represented as an uncertain time value: it makes it possible to account explicitly for the imprecision of input data. For example, the radius value can be fixed to 40-80ms in case of Gestures annotations and 5-10ms in case of Phonetics. This representation allows robust comparisons of multi-levels annotations over time. SPPAS also allows annotations to contain more than one label, each one associated with a score: the one with the highest score is considered as the main label, and the others as alternatives. Moreover, labels can be of 3 types: string, number or Boolean.

Actually, it is also quite easy to read some existing annotation file formats and to instantiate them into the SPPAS framework. Among others, it allows to open and save files from Praat [START_REF] Boersma | Praat: Doing phonetics by computer[END_REF], Phonedit [START_REF] Phonedit | [END_REF], Elan [START_REF]ELAN -linguistic annotator. language archiving technology portal[END_REF]; HTK [START_REF] Young | The HTK Hidden Markov Model Toolkit: Design and Philosophy[END_REF] and Sclite [START_REF]Speech Recognition Scoring Toolkit, version 2.4.0[END_REF] and some subtitles formats. It also allows to import data from Anvil [START_REF] Kipp | Anvil, DFKI, German Research Center for Artificial Intelligence[END_REF] and Transcriber [START_REF] Transcriber | A tool for segmenting, labeling and transcribing speech[END_REF].

The common denominator of most of the file formats consists in the basic building blocks (e.g. labels with start and end times, or labels and one time point) plus the additional structural entities (tiers). So, the system proposed in this paper is exploiting only these information: it allows to request all annotations regardless the input file format or the annotation type.

The exploration method is based on the creation of 2 different types of predicates. These latter are then respectively used in 2 types of filters:

1. single filters (Section 4), i.e. search in a tier depending on the data content, the time values or the duration of each annotation;

2. relation filters (Section 5), i.e. search on annotations of a tier in time-relation with annotations of another one.

Filtering annotations of a single tier

The main principle here is to create a predicate Sel, or a combination of predicates, that will be used as parameters to create a filter on a tier, named SingleF ilter(predicate, tier).

Filtering on the annotation labels

Pattern selection is an important part to extract data of a corpus and is obviously an important part of any filtering system, as shown in Section 2. Thus, if the label of an annotation is a string, the following predicates are proposed:

• exact match: Sel(exact = P ) is true if the label of an annotation strictly corresponds to the pattern P ;

• contains: Sel(contains = P ) is true if the label of an annotation contains the expected pattern P ;

• starts with, Sel(startswith = P ) is true if the label of an annotation starts with the expected pattern P ;

• ends with, Sel(endswith = P ) is true if the label of an annotation ends with the expected pattern P .

All these matches can be reversed to represent respectively: not exactly match, not contains, not starts with or not ends with. Moreover, this pattern matching can be case sensitive or not.

For complex search, a selection based on regular expressions is available for advanced users, as Sel(regexp = R), where R is the expected regexp. Moreover, in case of numerical labels, we implemented: Sel(equal = v), Sel(greater = v) and Sel(lower = v), and in case of Boolean: Sel(bool = v).

Finally, this pattern matching can be optionally applied either on the label with the highest score, which is the default, or on all labels of an annotation (i.e. the better label and its alternatives).

Filtering on annotations durations or on a time-range

Another important feature for a filtering system is the possibility to retrieve annotated data of a certain duration, and in a certain range of time in the timeline. Therefore, the same predicate Sel can be used on match duration of an interval, compared to a value v, as follow:

• lower: Sel(duration lt = v);

• lower or equal: Sel(duration le = v);

• greater: Sel(duration gt = v);

• greater or equal: Sel(duration ge = v);

• equal: Sel(duration e = v);

Search can also starts and ends at specific time values in a tier by using Sel predicate with begin ge and end le.

Multiple selections

A multiple pattern selection as well as duration or time selections can be expressed with the operator "|" to represent the logical "or" and the operator "&" to represent the logical "and", for example:

Sel(startswith = P1) & Sel(duration gt = v).

Filtering on relations between two tiers

Regarding the searching , linguists are typically interested in locating patterns on specific tiers, with the possibility to relate different annotations a tier to another. The proposed system offers a powerful way to request/extract data, with the help of Allen's interval algebra. The main principle here is to create a predicate Rel that will be used as parameter to create a filter on a tier: RelationF ilter(predicate, tier1, tier2).

Framework: Allen's interval algebra

In 1983 James F. Allen published a paper [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] in which he proposed 13 basic relations between time intervals that are distinct, exhaustive, and qualitative. They are distinct because no pair of definite intervals can be related by more than one of the relationships; exhaustive because any pair of definite intervals are described by one of the relations; qualitative (rather than quantitative) because no numeric time spans are considered. These relations and the operations on them form Allen's interval algebra.

SPPAS extended Allen's work to its framework that can handle relationships between intervals with precise as well as imprecise bounds. This results in a generalization of Allen's 13 interval relations that are also applicable when the bounds of the intervals are imprecise. Table 1 indicates the Allen's relations between TimeInterval X = [X -, X + ] and Y = [Y -, Y + ], where X -, X + , Y -, Y + are TimePoint instances, as defined in [START_REF] Bigi | Representing multimodal linguistics annotated data[END_REF]. This generalization preserves the 3 properties of Allen's original algebra mentioned above.

X relation Y Description before (X + < Y -) after (X -> Y + ) meets (X + = Y -) met by (X -= Y + ) overlaps (X -< Y -) ∧ (X + > Y -) ∧ (X + < Y + ) overlapped by (X -> Y -) ∧ (X -< Y + ) ∧ (X + > Y + ) starts (X -= Y -) ∧ (X + < Y + ) started by (X -= Y -) ∧ (X + > Y + ) during (X -> Y -) ∧ (X + < Y + ) contains (X -< Y -) ∧ (X + > Y + ) finishes (X -> Y -) ∧ (X + = Y + ) finished by (X -< Y -) ∧ (X + = Y + ) equals (X -= Y -) ∧ (X + = Y + )
Table 1: Allen's relations between two imprecise intervals X, Y

The proposed framework was also developed to include time annotations represented by a single TimePoint (mainly used in the Prosody domain). The relations can be extended to such time representation, as we propose in Table 2 between two TimePoint instances. Tables 3 and4 show relations between a TimePoint and a TimeInterval. Each table considers all possible relations (each table forms a complete relation system).

X relation Y Description before (X < Y ) after (X > Y ) equal (X = Y )
Table 2: Relations between two imprecise points X and Y .

These relations can then be used to search annotations of any kind in time-aligned tiers. It is particularly favorable in the context of multimodal annotations, where annotations are carried out thanks to various annotation tools, each one using its own representation of time. The proposed framework solves this problem in a clear, well-suited and well-defined way.

X relation Y Description before (X + < Y ) after (X -< Y ) starts (X -= Y ) finishes (X + = Y ) contains (X -< Y ) ∧ (X + > Y )
Table 3: Relations between an imprecise interval X and an imprecise point Y .

X relation Y Description before (X < Y -) after (X > Y -) starts (X = Y -) finishes (X = Y -) during (X > Y -) ∧ (X < Y + )
Table 4: Relations between an imprecise point X and an imprecise interval Y .

Filtering with time-relations

For the sake of simplicity, only the 13 relations of the Allen's algebra are available in the GUI. We withal implemented in Python the 25 relations proposed by [START_REF] Pujari | Indu: An interval & duration network[END_REF] in the INDU model. This model fixes constraints on INtervals with Allen's relations and on DUration -duration are equals, one is less/greater than the other. Moreover, both our experience while using the proposed system and the user comments and feedback have led us to add the following options:

1. a maximum delay for the relations "before" and "after", 2. a minimum delay for the relations "overlaps" and "overlapped by".

All the above mentioned relations were implemented as predicates.

With this proposal, a predicate can be for example predicate = Rel("overlaps")|Rel("overlappedby") to find witch syllables stretch across two words, and then by creating the filter RelationF ilter(predicate, tiersyllables, tiertokens).

Illustrations

DataFilter of SPPAS has been already used in several studies as to find correlations between speech and gestures [START_REF] Tellier | Same speech, different gestures?[END_REF], to find which gestures are produced while pausing [START_REF]Gesturing while pausing in conversation: Selforiented or partner-oriented?[END_REF] or to extract lexical feedback items [START_REF] Prévot | A quantitative view of feedback lexical markers in conversational French[END_REF] just to cite some of them.

While using the GUI, the user starts filtering tiers by running DataFilter and loading files of a corpus. The user selects the tier of each file that will serve as basis, and click on the appropriate "Filter" button (either Single or Relation). The user has then to define the predicates and to apply such filters. The program will generate new tiers with the matching annotations; each one is automatically added to its corresponding file.

In order to illustrate possible queries using SPPAS, the following request is processed in this section: What speech and hand gestures the locutor produces right before, during and right after the interlocutor produces multimodal feedbacks versus verbal feedbacks only?

We performed this request on 6 files of a corpus created by and belonging to the Institut Paoli-Calmettes (Marseille, France). This corpus is an authentic corpus of training sessions for doctors involved in role plays with an actor playing the role of a patient. The corpus is annotated on different levels of granularity. Tiers contain annotations of vocabulary, hand gestures, gaze, among other. In the context of this article, we will consider only 3 tiers: To perform the illustration request, the first stage consists in filtering the "P -Feedback" tier of each file to create an intermediate result with a tier containing head and oral feedback ("P + T") and oral feedback only ("P").

While using the GUI, this predicates are fixed as represented in Figure 1. It allows to enter multiple patterns at the same time (separated by commas) to mention the system to retrieve either one pattern or the other, etc.

Figure 1: Frame to create a filter on annotation labels. In that case, labels that are exactly matching "P + T" or "P" strings.

So, here the patterns are "P + T, P". Finally, the user has to select the tier name for the result as shown in Figure 2 and must click either to "Apply all" or "Apply any". The user has now one filtered tier by file, each one containing only oral feedbacks and oral and head movements feedbacks.

To complete the original request, the previous tiers must be unchecked. The user must now find annotations of speech and hand gestures that occur right before, during and right after the feedbacks previously filtered. To do so, the newly filtered tiers must in turn be checked and the user must click on the "Rela-tionFilter" button. Then, he/she selects "M -IPUs" in the "X" windows, and the filtered tier previously created in the "Y" window in the list of proposed tiers, as he/she wants to filter speech. Finally, the Allen's relations must be selected: see a glimpse in Figure 3. Regarding the example, quite every relations are needed. Though, the relations "Before" and "After" must be customized. The user needs to extract IPUs before and after the feedbacks. Customizing the delay allows the user to chose the exact delay between the feedback utterance and the nearer IPUs the user wants to take into consideration. To complete the filtering process, it must be clicked on the "Apply filter" button and the new resulting tiers are added in the annotation file(s).

In order to answer the question firstly asked, the user must complete the filter loop once again. He/she must click again on the "Relation Filter" button and select "M -Dimensions" in the "X" windows, and the previously filtered tier in the "Y" window, as the user wants, this time, to filter hand gestures in the list of proposed tiers. Then, the relations must be selected afresh. As the user does not want hand gestures produced out of the IPUs window, the user must check: Starts, Started by, Finishes, Finished by, Contains, During, Overlaps, and Overlapped by. Then, it must be clicked one last time on the "Apply filter" button and the new resulting tiers are added in the annotation file(s). The last resulting tier therefore contains the annotations of hand gestures produced by the locutor while speaking, right before, during and right after the interlocutor produced oral or oral and head movements feedback.

The user can keep or delete intermediate tiers and click on the "Save" button. The files are saved in their original file format and can therefore be opened in the annotation tool used to create the files in the first place. They can also be opened by "Statistics" component proposed in SPPAS.

Conclusions

This paper described a system to filter multi-levels annotations. It is based on the definition of predicates that are used to create filters. These later are applied on tiers of many kind of input files (TextGrid, eaf, trs, csv...). The search process results in a new tier, that can re-filtered and so on. A large list of predicates, applied on a single tier, is available and allows to filter annotations of various label types (string, number, Boolean). The full list of binary relations of the INDU model are also available to filter the annotations of a tier in relation with the annotations of another one. Moreover, this request system can be used either on precise or unprecise annotations. It is available as a Python Application Programming Interface, and with a GUI. Since the proposed system has been developed in a constant exchange with users from various Linguistics fields, we expect it to be especially intuitive.

  1. P -Feedback: feedback produced by the patient 2. M -IPUs: speech produced by the doctor and segmented into Inter Pausal-Units 3. M -Dimensions: hand gestures produced by the doctor

Acknowledgements

This work has been partly carried out thanks to the support of the French state program ORTOLANG (Ref. Nr. ANR-11-EQPX-0032) funded by the " Investissements d'Avenir " French Government program, managed by the French National Research Agency (ANR). This work was supported by Brain and Language Research Institute.


Ousseynou Yade
email: ousseynou.yade@doctorant.ec-lyon.fr

Christian Martin

Christian Vollaire

Arnaud Breard

Régis Meuret

Hervé Morel

Improved Layout of Inverter for EMC Analysis

This paper details EMC (electromagnetic compatibility) analysis on an inverter application. The work deals with the whole power chain (±270Vdc input voltage to 3-phase 115 Vac output voltage). This inverter is composed by modular parts (power module and EMC filters) that supply motors in more electrical aircraft. Through our analysis an approach is defined to design a detailed lumped circuit model of the power module layout by using Q3D extractor and SABER software. From this first step, the power module layout design is improved by reduced parasitic impedances at high frequency (around 30 MHz). Then whole power converter is modeled in SABER by including switches (SiC MOSFET models), LISN (line impedance stabilization network), harness, and load models.

I Introduction

The more electrical aircraft aims to offer many benefits [START_REF] Wheeler | The More Electric Aircraft: Technology and challenges[END_REF]. On the one hand, it reduces operating costs, fuel consumption and the environmental impact of the future air travel. On the other hand, the use of electrical equipment leads to advantages in terms of maintenance, power control and efficiency [START_REF] Roboam | More Electricity in the Air: Toward Optimized Electrical Networks Embedded in More-Electrical Aircraft[END_REF], [START_REF] Wu | Fuel cell applications on more electrical aircraft[END_REF]. Thanks to this concept, electrical systems should substitute conventional power sources used in aircraft. As a result, they take a significant part of the total aircraft mass. Among these systems, there are power electronic converters that control actuator energy. Different efforts are made in order to improve power electronic converter efficiency by considering new semiconductor technologies (GaN, SiC …). These efforts also allow to increase switching frequency and, operating temperature in the way to reduce passive components and cooling requirements. Within the scope of the EU research and innovation program Horizon2020 [START_REF]Horizon 2020 -European Commission[END_REF], the I 2 MPECT project [START_REF]I 2 MPECT[END_REF] Section II explains the importance of detailed lumped circuit model for EMC analysis. In section III, the simulation approach and layout design improvement are described. The simulation results are summarized in section IV. A conclusion and perspectives are given in section V.

II Simulation approach of layout circuit model

To analyse EM disturbances and design EMC filters, it's necessary to model the whole power converter in order to get EM signatures. There are two main approaches to get simulation model: the first one is behavioural modelling approach [START_REF] Liu | Modular-Terminal-Behavioral (MTB) Model for Characterizing Switching Module Conducted EMI Generation in Converter Systems[END_REF] which is suitable when there are no details about inverter layout and it requires few computational time. However, since there is no information about impedance distribution, it is not possible to correlate EM disturbances to the layout. As a result, this technique cannot be used to improve layout. The second one is a detailed lumped circuit modelling approach based on the physics of the circuit. It is the classical way to model any electronic circuit. The interconnections like wires and printed circuit board (PCB) traces are modelled using passive RLC equivalent circuit or impedance matrix [START_REF] Podlejski | Layout modelling to predict compliance with EMC standards of power electronic converters[END_REF]. Other passive components like resistors, capacitors and inductors can be directly measured using an impedance analyser. The equivalent circuit models for the PCBs are usually extracted by electromagnetic numerical tools like Q3D extractor [START_REF]ANSYS Q3D Extractor -Parasitic Extraction[END_REF], [START_REF] Zhong | Comparison of parasitic parameters extraction methods and equivalent circuits for a grounding model[END_REF]. The main benefits of lumped circuit models are accuracy, adaptability and scalability as everything is based on physics. However, it requires more large computational resources and time to simulate precisely the full model. Stray impedances are extracted by using Q3D software. It can provide RLC elements with the same solver by combining finite element method and the method of moments. Typical power module layout designed for this project is shown in fig . 2. The control pins are designed on a PCB flex and there are no bondings on the power part. This power module is composed of two main parts:  The power part which generates the main part of the parasitic impedance. Depending on the power module version, it is composed by (at least) two MOSFETs SiC per switch, shunt resistors for currents sources measurements, DC link connection and output phase.



The control and measurement part on PCB flex above the power part with temperature sensor (NTC), shunt resistor and gate control.

Fig . 2 inverter layout for "one phase" leg (A), power part (B), control and measurement part (C)

After imported or built layout on Q3D extractor, Simulation procedure is launched and parasitic impedance behavior can be computed and analyzed.

To build electrical model, Q3D extractor provide us a ".cir" file which include all parasitic impedance values for one frequency. These parasitic impedances are then converted as electrical model in order to embed it on saber platform. Fig. 3 shows the extraction process that allows building circuit model of the power module layout. A geometrical modification of the DC link allows to reduce this stray inductance by choosing parallel plate overlap as DC link structure (fig. 5) [START_REF]Cree CPWR-AN08 Application Considerations for SiC MOSFETs -design_considerations_for_designing_with_cree _sic_modules_part_2_techniques_for_minimizin g_parasitic_inductance[END_REF]. This improved design allows reducing stray inductance around 50% as shown in Table 2 (L change from 9.1nH to 5.37nH). This part will be detailed in the full paper.

47

Table 2 stray impedance reduction

III Circuit model and simulation results

In order to evaluate this improved layout, its EM signature is compared to original layout one. Fig. 6 shows electrical circuit model used to extracted EM signature and Table 3 summarizes passive components and DC fed values. By associating coupling capacitor to the power module layout, the differential impedance seen between switching cells is lower with the improved layout than with original (for 5 dB). That's mean differential mode disturbances provided by inverter to DC side decreases to 5 dBµA. This improvement is available from 700 kHz to higher frequencies as shown in Fig. 7.It also contributes to increase cut-off frequency of the further EMI filters and to reduce passive components value required to mitigate EM disturbances seen from DC side. Common mode impedance measurements will be done by including common mode parasitic capacitor and analyse impedance between ground and DC link.

Coupling capacitor 10µF

Internal capacitor 15nF

Parasitic capacitor 15pF

Load 8Ω Table 2 stray impedance reduction Fig. 7 Differential impedance seen from switching cells Fig. 8 shows the novel layout design with three MOSFETs per switch in order to reduce stress current through each MOSFET. This design will be embedded as power module in the whole converter with separate parts: LISN, harness, motor and SiC MOSFETs. A three phases pulse width modulation is used with 15 kHz as switching frequency and 100 Hz as output phase frequency. This power module is supplied by a DC fed with ±270 Vdc input voltage.

The LISN is defined by DO-160 standard. Electrical coupling capacitor model is built as an RLC model the capacitor value is 30 µF. The model is based on SPICE level1 MOSFET model with channel mobility modulation effect (level 3) [START_REF] Massobrio | Semiconductor device modeling with SPICE[END_REF] [START_REF] Omari | Extraction des paramètres des modèles du VDMOS à partir des caractéristiques en commutation -comparaison avec les approches classiques[END_REF]. As load, a 15 kW R-L model is used for proof of concept of our design approach. This model can be applied for higher load values (45 kW). This circuit model allows analyzing conducted EM disturbances from each part of inverter layout. Fig. 9 shows EM disturbances seen from DC side for 15 kW (input voltage ±270 V and current load 30 A). Current and voltage slopes during the switching phase reach 2.577 kA/µs and 12.591 kV/µs respectively.

V Conclusions

This paper summarizes detailed lumped circuit model technique applied on advanced inverter layout model. In order to reduce stray impedances, it's necessary to overlap DC link. This approach is accessed by comparing provided results to experimental measurements. Time domain simulations are also accessed through current waveforms and slope during switching phase for the whole converter. For further works EM disturbances will be identified and mitigated through passive EMI for DC and AC side.

Fig. 3

 3 Fig.3 translation procedure from Q3D extractor to SABER software

Fig. 6

 6 Fig.6 circuit model to extract EM signature

Fig. 8

 8 Fig.8 power module embedded in the inverter

Fig. 9

 9 Fig.9 EM disturbances seen from DC side

Table 1

 1

		DC link	Substrate
	Stray	4.3	4.8
	inductance (nH)

shows stray inductance for both DC link connection and substrate. The loop inductance of the switching cell is the sum of both values (around 9.1 nH). As substrate dimension is imposed by SiC chip location and thermal criteria, it is difficult to change the form of the substrate. As conclusion, the modification of the DC link seems to be a good way to reduce the total loop inductance.

Table 1

 1

stray inductance of the two main part of the power part