Benjamin Assel

John Estes

Masahito Yamazaki

Large N Free Energy of 3d N = 4 SCFTs and AdS 4 /CFT 3

We provide a non-trivial check of the AdS 4 /CFT 3 correspondence recently proposed in [1] by verifying the GKPW relation in the large N limit. The CFT free energy is obtained from the previous works [2, 3] on the S 3 partition function for 3-dimensional N = 4 SCFT T [SU (N )]. This is matched with the computation of the type IIB action on the corresponding gravity background. We unexpectedly find that the leading behavior of the free energy at large N is 1 2 N 2 ln N . We also extend our results to richer T ρ ρ [SU (N )] theories and argue that 1 2 N 2 ln N is the maximal free energy at large N in this class of gauge theories.

Introduction

In this paper we study a class of 3d N = 4 SCFT T ρ ρ [SU (N )] introduced in [START_REF] Gaiotto | S-Duality of Boundary Conditions In N=4 Super Yang-Mills Theory[END_REF], where ρ, ρ are partitions of N . This theory is a 1/2 BPS domain wall theory inside the 4d N = SU (N ) Yang-Mills theory, and plays crucial roles in the generalizations [START_REF] Drukker | The Virtue of Defects in 4D Gauge Theories and 2D CFTs[END_REF][START_REF] Hosomichi | AGT on the S-duality Wall[END_REF] of the AGT correspondence, as well as the connection with the 3d SL(2) Chern-Simons theory [START_REF] Terashima | SL(2,R) Chern-Simons, Liouville, and Gauge Theory on Duality Walls[END_REF][START_REF] Terashima | Semiclassical Analysis of the 3d/3d Relation[END_REF][START_REF] Dimofte | Chern-Simons Theory and S-duality[END_REF]. The T ρ ρ [SU (N )] theories also appear as the basic building blocks for the 3d mirror of the 4d N = 2 Gaiotto theories [START_REF] Gaiotto | N=2 dualities[END_REF] compactified on S 1 [START_REF] Benini | Mirrors of 3d Sicilian theories[END_REF][START_REF] Nishioka | 3d Partition Function as Overlap of Wavefunctions[END_REF].

The type IIB supergravity dual for T ρ ρ [SU (N )] theories has recently been constructed in [START_REF] Assel | Holographic Duals of D=3 N=4 Superconformal Field Theories[END_REF]. In this paper we provide further quantitative consistency checks of this AdS4/CFT3 correspondence by verifying the GKPW relation [START_REF] Witten | Anti-de Sitter space and holography[END_REF][START_REF] Gubser | Gauge theory correlators from noncritical string theory[END_REF] in the leading large N limit.

On the CFT side, we take the large N limit of the S 3 partition functions of [START_REF] Benvenuti | 3D-partition functions on the sphere: exact evaluation and mirror symmetry[END_REF][START_REF] Nishioka | 3d Partition Function as Overlap of Wavefunctions[END_REF], evaluated at the conformal point. On the gravity side, we evaluate the gravity action in the gravity background of [START_REF] Assel | Holographic Duals of D=3 N=4 Superconformal Field Theories[END_REF]. We find that in both cases the leading contribution of the free energy in the large N limit scales as

F ∼ N 2 ln N + O(N 2 ) .
More detailed statements will be given momentarily in section 2.2. As we will see, on the CFT side N 2 ln N comes from the asymptotic behavior of the Barnes G-function. On the gravity side, a factor of N 2 comes from the local scaling of the supergravity Lagrangian, and an extra ln N comes from the size of the geometry.

The organization of this paper is as follows. We first summarize the notations and the main results (section 2). We then give the derivations the results in gauge theory (section 3) and gravity (section 4). We also include two appendices.

Summary of the Results

Review of T ρ ρ [SU (N )] Theories

Let us first briefly summarize the basics of T ρ ρ [SU (N )] theories needed for the understanding of this paper (see [START_REF] Gaiotto | S-Duality of Boundary Conditions In N=4 Super Yang-Mills Theory[END_REF] for details).

As stated in the introduction, the T ρ ρ [SU (N )] theory is specified by two partitions ρ and ρ of N :

ρ = N (1) 5
l (1) , l (1) , .., l (1) , N

l (2) , l (2) , .., l (2) , ... , where l (a-1) > l (a) , l(a-1) > l(a) for all a and To construct the 3d theory, it is useful to use the brane configurations of [START_REF] Hanany | Type IIB superstrings, BPS monopoles, and three-dimensional gauge dynamics[END_REF]. Namely, we consider a D3-D5-NS5-brane configuration with N D3-branes suspended between NS5branes on the left and D5-branes on the right, where l (a) D3-branes ( l(a) D3-branes) end on the i-th D5-brane (NS5-brane). We can identify the 3d theory after suitable exchanges of D5 and NS5-branes. The result is a 3d N = 4 quiver gauge theory. This theory has a non-trivial irreducible IR fixed point only when [START_REF] Gaiotto | S-Duality of Boundary Conditions In N=4 Super Yang-Mills Theory[END_REF]

ρ T > ρ ⇔ ρT > ρ , (2.3)
where ρ > ρ for ρ = [n 1 , n 2 , . . .] and ρ = [m 1 , m 2 , . . .] is defined by

k i=1 n i > k i=1 m i (2.4)
for all k. When the inequality is saturated for some value of i, the quiver breaks into pieces and the IR fixed point consists of products of irreducible theories. The global symmetry of

T ρ ρ [SU (N )] is given by G ρ × G ρ, where G ρ is a subgroup of SU (N ) commuting with the embedding ρ G ρ = S(U (N (1) 5 ) × • • • × U (N (p) 5 )) . (2.5)
G ρ is a symmetry of the Lagrangian, and acts non-trivially on the Higgs branch, whereas G ρ is a quantum mechanical symmetry acting on the Coulomb branch 1 . We can weakly gauge these symmetries to introduce a set of real mass parameters and FI parameters, which we collectively denote by m and m, respectively. The two global symmetries are related by 3d mirror symmetry [START_REF] Intriligator | Mirror symmetry in three-dimensional gauge theories[END_REF] exchanging Higgs and Coulomb branches, together with real mass and FI parameters. This is simply the S-duality of the D3-D5-NS5 system, and in particular,

T ρ ρ [SU (N )] is the mirror of T ρ ρ [SU (N )].

Large N Free Energy

We will verify the GKPW relation in the large N limit:

Z CFT = e -S gravity , i.e. F CFT = S gravity , (2.6)
where Z CFT is a CFT partition function on S 3 , F CFT :=ln Z CFT is the free energy, and S gravity is the action for the type IIB supergravity holographic dual to the CFT. Our findings are summarized as follows.

• The simplest prototypical example is the T [SU (N )] theory, which is a

T ρ ρ [SU (N ))] theory with ρ = ρ = N 1, 1, ..., 1 .
(2.7)

In this case we find

F CFT = S gravity = 1 2 N 2 ln N + O(N 2 ) . (2.8)
1 The Cartan of this symmetry is the shift of the dual photon, and is present in the Lagrangian.

3

• More generally we consider the case p = 1, i.e.,

ρ = N (1) 5
l (1) , l (1) , .., l (1) , N

l (2) , l (2) , .., l (2) , ... ,

N (p) 5
l (p) , l (p) , .., l (p) , ρ = N5 l, l, .., l .

(2.9)

We take the scaling limit

N (a) 5 = N 1-κa γ a , l (a) = N κa λ (a) , N5 = N γ , (2.10)
where we take N large, while keeping κ a , λ (a) , γ a , γ finite. We require

κ a-1 ≥ κ a , 0 ≤ κ a < 1, for all a .
(2.11)

The first condition is necessary for ρ to be partition, and the second ensures that the N (i) 5 becomes large, hence justifying the validity of the supergravity solution. We also have from (2.2) the constraint p a=1 γ a λ (a) = γ l = 1 .

(2.12)

In this more general case we find (CFT analysis will be provided for l = 1, and gravity analysis for general l):

F CFT = S gravity = 1 2 N 2 ln N   (1 -κ 1 ) + p i=2 p a=i γ a λ (a) 2 (κ i-1 -κ i )   + O(N 2 ).
(2.13)

In particular when all κ a = 0, i.e. when all l (a) are finite, the leading large N behavior coincides with that in (2.8).

Note the number inside the bracket in (2.13) is a non-negative number smaller than 1 due to (2.11). Motivated by this result we conjecture

F T ρ ρ [SU (N )] ≤ F T [SU (N )] . (2.14)
for all ρ, ρ satisfying (2.3). The rest of this paper will be devoted to the derivation of (2.8) and (2.13).

CFT Analysis

In this section we analyze the CFT free energy F CFT .

The S 3 Partition Function

Let us begin with the T [SU (N )] theory (2.7). The partition function of this theory was computed by localization [START_REF] Kapustin | Exact Results for Wilson Loops in Superconformal Chern-Simons Theories with[END_REF] to be [START_REF] Benvenuti | 3D-partition functions on the sphere: exact evaluation and mirror symmetry[END_REF][START_REF] Nishioka | 3d Partition Function as Overlap of Wavefunctions[END_REF] (see also [START_REF] Gulotta | From Necklace Quivers to the F-theorem, Operator Counting, and T(U(N))[END_REF]):

2 Z S 3 [T [SU (N )]](m, m) = w∈S N (-1) w e 2πım•w( m) ∆(m)∆( m) , (3.15)
where (-1) w is a sign of a permutation w ∈ S N , m = (m 1 , . . . , m N ) with i m i = 0 ( m = ( m1 , . . . , mN ) with i mi = 0) are the FI parameters3 (real mass parameters), and

m • w( m) := i m i mw(i) ,
and ∆ is the (sinh) Vandermonde determinant

∆(m) := i<j 2 sinh π(m i -m j ), ∆( m) := i<j 2 sinh π( mi -mj ). (3.16)
For more general T ρ ρ [SU (N )] theories, the partition function takes a similar form as in (3.15) [START_REF] Nishioka | 3d Partition Function as Overlap of Wavefunctions[END_REF]:

Z S 3 [T ρ ρ [SU (N )]](m, m) = w∈S N (-1) w e 2πımρ•w( mρ ) ∆ ρ (m)∆ ρ( m) . (3.17)
Here m ρ , mρ are N -vectors, and each of their components is associated with a box of the Young diagram (also denoted by ρ, ρ) corresponding to the partitions ρ, ρ. For later our purposes let us describe them by dividing the boxes of ρ into p blocks, where a-th block is a rectangle with rows of length N (a) 5

and columns of length l (a) (recall (2.1), and see fig. 1). A box of ρ could then be labeled by a triple (a, i, α)

with 1 ≤ a ≤ p, 1 ≤ i ≤ N (a) 5 , 1 ≤ α ≤ l (a)
, where a is the label for the block and i (α) is the label for the column (row) inside the a-th block. The same applies to ρ. In this notation, we have

(m ρ ) (a,i,α) = ı(w l (a) ) α + m a,i , ( mρ ) (a,i,α) = ı(w l(a) ) α + ma,i , (3.18)
where w N is a Weyl vector of the SU (N ) Lie algebra defined by

w N = N -1 2 , N -3 2 , . . . , - N -1 2 . (3.19)
Also, ∆ ρ (m) and ∆ ρ( m) are defined by

∆ ρ (m) = i a<b 2 sinh π((m ρ ) [i,a] -(m ρ ) [i,b] ), ∆ ρ( m) = i a<b 2 sinh π(( mρ ) [i,a] -( mρ ) [i,b] ) , (3.20)
where [i, a] represents a box inside ρ, ρ at row i and column a. Several remarks are now in order. First, the partition function (3.17) is manifestly invariant under the simultaneous exchange of ρ, ρ and m, m. This is a manifestation of the 3d mirror symmetry.

Second, (3.17) vanishes unless ρ T ≥ ρ [START_REF] Nishioka | 3d Partition Function as Overlap of Wavefunctions[END_REF]. This is consistent with the condition (2.3) for the existence of a non-trivial IR SCFT. This condition has a counterpart in the gravity dual [START_REF] Assel | Holographic Duals of D=3 N=4 Superconformal Field Theories[END_REF].

Third, the expression (3.15) is either real or pure imaginary, however there is an ambiguity of the phase of the S 3 partition function and we will hereafter concentrate on the absolute value of the S 3 partition function.

T [SU (N )]

Let us study the large N behavior of our partition functions.

For clarity, let us begin with the T [SU (N )] theories, whose partition function is given in (3.15). When the parameters m and m are generic and kept finite in the limit, 4 we have

F CFT ∼ O(N 2 ) . (3.21)
This is not surprising since after all our theories are standard gauge theories. However, the scaling behavior could change if we consider non-generic values of m and m. This is exactly happens to our CFT case, where we need to take the limit m, m → 0 of (3.15):

Z CFT = lim m, m→0 Z S 3 . (3.22)
We choose to take the limit in two steps. First, let us take the m → 0 limit of (3.17) with ρ = [1, . . . , 1]. This is conveniently done by setting m = w N and by taking → 0, where w N is defined in (3.19). Using the Weyl denominator formula, we have

w∈S N (-1) w e 2πı w N •mρ = α>0 2ı sin (π α • m ρ ) = j<k 2ı sin (π (m j -m k )) .
(3.23)

In the limit 2 → 0, this cancels the factor ∆( w

N ) = j<k 2 sinh π( (j -k)), giving j<k ı (j -k) j<k (m ρ ) j -(m ρ ) k ∆ ρ (m) = 1 G 2 (N + 1) j<k (m ρ ) j -(m ρ ) k ∆ ρ (m) . (3.24)
We next need to take the limit m → 0. This is easy for our case, ρ = [1, . . . , 1];

i<j (m ρ ) i -(m ρ ) j ∆ ρ (m) = i<j m i -m j 2 sinh π(m i -m j ) → (2π) -N (N -1)

2

, which gives

Z CFT = 1 (N -1)!(N -2)! . . . 2!1! 1 2π N (N -1) 2 = 1 G(N + 1) 1 2π N (N -1) 2 , (3.25)
where G 2 (x) is the Barnes G-function defined in Appendix A. From the asymptotics of G 2 (x) (A.57), we have

F CFT = N 2 2 ln N + - 3 4 - 1 2 ln 1 2π N 2 + O(N ln N ) , (3.26)
which gives (2.8).

T ρ ρ [SU (N )]

Let us consider a more general case (2.9). As long as ρ = [1, . . . , 1] the argument of the previous subsection works up until (3.24). In (3.24) we already have a factor of G 2 (N + 1). Just as in the T [SU (N )] case, this contributes

1 2 N 2 ln N , (3.27)
to the free energy. Next, let us send the FI parameters to zero in (3.24). The denominator ∆ ρ (m) goes to zero in the limit, but the same is true for the numerators, yielding the finite answer. We obtain powers of 2π in this process from the limit of ∆ ρ (m), however this only gives a subleading contribution of order N 2 . There are still contributions from the numerator i<j [(m ρ ) i -(m ρ ) j ], which we have not yet taken into account. In the notation of the previous section the limit of this contribution is 5(

m ρ ) (a,i,α) -(m ρ ) (b,j,β) = ı [(w l (a) ) α -(w l (b) ) β ] = ı(α -β) , where 1 ≤ α ≤ l (a) , 1 ≤ β ≤ l (b) and α = β.
When the two boxes are in the same block, this contributes a factor

N (a) 5 2 ln (l (a) -1)!(l (a) -2)! . . . 1! ,
where the factor N (a) 5 2 accounts for the degeneracy from the column labels i. This contributes, under the scaling (2.10),

- 1 2 κ a (λ (a) γ a ) 2 N 2 ln N + O(N 2 ) , (3.28)
to the free energy. When the two boxes are in the different blocks a, b with l (a) ≥ l (b) , κ a ≥ κ b , the contribution to the free energy is

-2 N (a) 5 N (b) 5 ln l (a) + l (b) 2 -1 ! l (a) + l (b) 2 -2 ! . . . l (a) -l (b) 2 ! .
The expression inside the bracket gives

ln G 2 l (a) + l (b) 2 + 1 -ln G 2 l (a) -l (b) 2 + 1 ∼ 1 2 l (a) l (b) ln l (a) .
Thus the contribution amounts to

-2 N (a) 5 N (b) 5 1 2 l (a) l (b) ln l (a) = -2 1 2 (λ (a) γ a λ (b) γ b )κ a N 2 ln N . (3.29)
Collecting all the contributions (3.27), (3.28) and (3.29), we have

F CFT = 1 2 N 2 ln N   1 - p a=1 (λ (a) γ a ) 2 κ a -2 a =b, l (a) >l (b) (λ (a) γ a λ (b) γ b )κ a   + O(N 2 ) . (3.30)
From (2.12) we can show that this coincides with (2.13). In all of the examples above, the leading contribution to the partition function comes from the Barnes G-functions. It is curious to note that the same function appears in the formula for the volumes of Lie group SU (N ) [START_REF] Macdonald | The volume of a compact Lie group[END_REF], and hence in the measure for the SU (N ) gauge theory. This is probably not a coincidence, since in the correspondence in [START_REF] Nishioka | 3d Partition Function as Overlap of Wavefunctions[END_REF] the S 3 partition function is related with dimensional reduction of the 2d SU (N ) Yang-Mills on a cylinder, which in turn is related with the 3d SU (N ) Chern-Simons theory. The same N 2 ln N type behavior appears in a number of different contexts, such as Gaussian matrix models, c = 1, topological string on the conifold or more recently in the weak coupling expansion of the ABJM theory [START_REF] Drukker | From weak to strong coupling in ABJM theory[END_REF].

Gravity Analysis

In this section we analyze the type IIB supergravity action S gravity in the holographic dual.

Summary of the Gravity Solution

First we summarize the holographic duals of the T ρ ρ [SU (N )] theories constructed in [START_REF] Assel | Holographic Duals of D=3 N=4 Superconformal Field Theories[END_REF] (see also [START_REF] Aharony | Near-horizon solutions for D3-branes ending on 5-branes[END_REF] for related work), which is based on earlier solutions found in [START_REF] Hoker | Exact half-BPS Type IIB interface solutions. I. Local solution and supersymmetric Janus[END_REF][START_REF] Hoker | Exact half-BPS Type IIB interface solutions. II. Flux solutions and multi-Janus[END_REF].

The geometry of the type IIB backgrounds is an AdS 4 × S 2 × S 2 fibration over a twodimensional Riemann surface Σ. We will parameterize Σ by an infinite strip, although it will turn out that Σ has finite volume and is really compact. Next we introduce complex coordinates on Σ as z, z. We will also make use of the real coordinates defined by writing z = x + ıy. After fixing Σ, the solution is then determined by two real harmonic functions, h 1 and h 2 , on Σ.

The metric can be written as

ds 2 = f 2 4 ds 2 AdS 4 + f 2 1 ds 2 S 2 1 + f 2 2 ds 2 S 2 2 + 4ρ 2 dzdz , (4.31)
where the warp factors are given by

f 8 4 = 16 N 1 N 2 W 2 , f 8 1 = 16h 8 1 N 2 W 2 N 3 1 , f 8 2 = 16h 8 2 N 1 W 2 N 3 2 , ρ 8 = N 1 N 2 W 2 h 4 1 h 4 2 , (4.32)
and we defined the auxiliary functions

W = ∂ ∂(h 1 h 2 ) , N j = 2h 1 h 2 |∂h j | 2 -h 2 j W . (4.33)
This geometry is supported by non-vanishing "matter" fields, which include the dilaton field

e 2φ = N 2 N 1 , (4.34)
in addition to non-vanishing 3-form and 5-form fluxes which are given in appendix B. We now turn to the specific solutions corresponding to T ρ ρ [SU (N )]. The classical supergravity solutions describing the near horizon limit of D3-branes suspended between p stacks of D5-branes and p stacks of NS5-branes is given by the two harmonic functions:

h 1 = - p a=1 α 4 N (a) 5 ln tanh ıπ 4 - z -δ a 2 + c.c. , h 2 = - p b=1 α 4 N (b) 5 ln tanh z -δb 2 + c.c. , (4.35)
with -∞ < x < ∞ and 0 ≤ y ≤ π/2. Here δ 1 < δ 2 < ... < δ p are the positions of D5-brane singularities on the upper boundary of the strip (y = π/2), whereas δ1 > δ2 > ... > δp are the positions of NS5-brane singularities on the lower boundary (y = 0) (see fig. 2). The points at x = ±∞ are regular interior points of the ten-dimensional geometry.

The coefficients of the logarithms determine the number of 5-branes located at the singularities. The number of D5-branes located at δ a is denoted by N

5 , N (a) 5 , l (a) , l(a) , are identified with the same parameters of the same names in section 2 under the holographic duality.

The Gravity Action

The type IIB action in Einstein frame is7

S IIB = - 1 2κ 2 10 d 10 x √ g R - 4 2 ∂ M φ∂ M φ - 1 2 e 4φ ∂ M χ∂ M χ - 1 2 e -2φ |H (3) | 2 - 1 2 e 2φ |F (3) + χH (3) | 2 - 1 4 | F(5) | 2 + 1 4κ 2 10 d 10 x C (4) ∧ H (3) ∧ F (3) , (4.37)
where one imposes the self-duality condition F(5) = * F (5) as a supplementary equation. The coupling κ 10 is related to the string scale α by 2κ 2 10 = (2π) 7 (α ) 4 . Due to the presence of the self-duality condition, the action (4.37) cannot be directly used to compute the on-shell value of the action. One way to deal with this is to relax the requirement of Lorentz invariance of the action. In this case an action principle could be obtained along the lines of [START_REF] Henneaux | DYNAMICS OF CHIRAL (SELFDUAL) P FORMS[END_REF]. As suggested in [START_REF] Giddings | Hierarchies from fluxes in string compactifications[END_REF], perhaps the easiest way to implement this for the full type IIB supergravity action is to make a T-duality transformation of the type IIA action. A simpler method is to first dimensionally reduce the theory to 4-dimensions.

After carrying out the dimensional reduction, one can then truncate the theory to the 4dimensional graviton. To see this is consistent, one may check that the solutions of [START_REF] Hoker | Exact half-BPS Type IIB interface solutions. I. Local solution and supersymmetric Janus[END_REF][START_REF] Hoker | Exact half-BPS Type IIB interface solutions. II. Flux solutions and multi-Janus[END_REF] can be extended by replacing the AdS 4 space with any space which obeys the same Einstein equations. Thus truncating to the 4-dimensional graviton is a consistent truncation. 8 The effective action for this mode is given by

S eff = - 1 2κ 2 10 vol 6 AdS 4 d 4 x √ g (4) (R (4) + 6) , (4.38)
where the cosmological constant has been chosen so that the unit AdS 4 space is a solution.

The subscript (4) reminds us that g (4) is the 4-dimensional metric and R (4) is the associated Ricci scalar. The quantity vol 6 follows from the initial dimensional reduction and is the volume of the internal space dressed appropriately with the warp factor of AdS 4

vol 6 = (4π) 2 Σ d 2 x(f 4 f 1 f 2 ) 2 4ρ 2 = 32(4π) 2 Σ d 2 x(-W )h 1 h 2 . (4.39)
The specific solution we are interested in is AdS 4 with Ricci scalar R (4) = -12. Thus the on-shell action becomes simply

S eff = - 1 (2π) 7 (α ) 4 vol 6 4 3 π 2 (-6) , (4.40)
where we have used the regularized volume of AdS 4 , vol AdS 4 = (4/3)π 2 , which may be computed using holographic regularization [START_REF] Henningson | The Holographic Weyl anomaly[END_REF][START_REF] Balasubramanian | A Stress tensor for Anti-de Sitter gravity[END_REF][START_REF] Emparan | Surface terms as counterterms in the AdS / CFT correspondence[END_REF][START_REF] Haro | Holographic reconstruction of space-time and renormalization in the AdS / CFT correspondence[END_REF] (see for example section 5 of [START_REF] Marino | Lectures on localization and matrix models in supersymmetric Chern-Simonsmatter theories[END_REF]).

T [SU (N )]

Let us first consider the gravity dual for T [SU (N )]. The harmonic functions are:

h 1 = - α N 4 ln tanh ıπ 4 - z -δ 2 + c.c. , h 2 = - α N 4 ln tanh z + δ 2 + c.c. , (4.41)
8 To see this more explicitly, first consider the 10-dimensional metric 2 , where ds 2 (4) is an arbitrary 4-dimensional metric. This is a solution to the type IIB supergravity equations of motion as long as the 4-dimensional Ricci tensor satisfies R (4)µν = -3g (4)µν . One can then write the 10-dimensional Ricci scalar as R = f -2 4 R (4) + ..., where the omitted terms do not depend on ds 2 (4) . The action then takes the form S = -1 2κ 2 10

ds 2 = f 2 4 ds 2 (4) + f 2 1 ds 2 S 2 1 + f 2 2 ds 2 S 2 2 + 4ρdzdz
d 10 x(f 4 f 1 f 2 ) 2 4ρ 2 √ g (4) (R (4) + ...)
, where again the omitted terms do not depend on ds 2 (4) . Requiring the variation with respect to ds 2 (4) to now reproduce the correct equation of motion yields the effective action (4.38). with

δ = - 1 2 ln tan π 2N , (4.42)
where we have used a translation to set δ = -δ. There is one stack of N D5-branes at the position

z = ı π 2 -1 2 ln[tan( π 2N )
] and one stack of N NS5-branes at z = 1 2 ln[tan( π 2N )] with N D3-branes stretched between them.

We now wish to take the large N limit of this configuration. It will turn out that locally the Lagrangian density will scale with a factor of N 2 at leading order in N . Secondly, as N goes to infinity, the positions δ of the 5-brane stacks are sent to infinity in opposite directions (see fig. 3). This leaves a large region of geometry between -δ and δ of size ln N , which will reproduce the ln N behavior of the partition function. Thus one can understand the leading behavior of the T [SU (N )] partition function as coming from the geometry located between the two stacks of 5-branes.

To make this more explicit and also compute the exact numerical coefficient, we now work out the large N expansion. First we re-scale the x coordinate so that z = δx + ıy and then expand the harmonic functions h 1 and h 2 around large N . At leading order we obtain

h 1 = α sin(y)N e δ(x-1) + ... if x < 1 , = α sin(y)N e δ(1-x) + ... if x > 1 , h 2 = α cos(y)N e δ(1+x) + ... if x < -1 , = α cos(y)N e -δ(1+x) + ... if x > -1 . (4.43)
From (4.43) we find that the only contribution to the action at this order comes from the central region -1 < x < 1. In this region W is given by W = -1 2 e -2δ N 2 (α ) 2 sin(2y).

Computing the volume of the internal space, (4.39), and plugging into the expression for the effective action, (4.40), we find

S eff = 4N 4 δe -4δ π 2 + ... = 1 2 N 2 ln N + O(N 2 ) . (4.44)
This reproduces exactly the leading order behavior of the CFT partition function (3.26). Finally we note that including higher order terms in the expansions of the harmonic functions will give additional contributions of order N 2 . Since we have explicit D5-brane and NS5-brane singularities in the geometry, one may worry about the validity of our approximation. We shall argue that the corrections due to the 5-brane singularities are at most of order N 2 and do not contribute to the leading N 2 ln N behavior. To do so, we first examine the geometry in the central region in the large N limit. The metric factors are given by It is interesting to note that this is exactly the limiting geometry of Janus found in [START_REF] Bachas | Spin-2 spectrum of defect theories[END_REF] for the case of an infinite jump in the coupling. 9 The radius L of the Janus space is related to N by L 2 = 2 √ 2α N e -δ . In the case we consider here, the Σ space comes with a natural cutoff at |x| = δ, while for Janus the space is unbounded.

f 2 4 = √ 2α N e -δ [(2 -cos(2y))(2 + cos(2y))] 1 4 , f 2 1 = 2 √ 2α N e -δ sin(y) 2 2 + cos(2y) (2 -cos(2y)) 3 1 4 , f 2 2 = 2 √ 2α N e -δ cos(y) 2 2 -cos(2y) (2 + cos(2y)) 3
We now consider curvature corrections. Using the above formulas for the metric factor and dilaton, the string frame Ricci scalar in the central region, -1 ≤ x ≤ 1, is given by

α R = 1 π2 1/2 2N π x-1 2
419 -60 cos(4y) + cos(8y) (7cos(4y)) 2 (2 + cos(2y)) 1/2 .

(4.47) Due to the large N limit, throughout most of the region we have α R 1. However, due to the presence of D5-branes, as one approaches x = 1, α R is of order one and one expects higher curvature corrections to play a role. Since these corrections are localized only in the region near x = 1, we expect that they do not receive the ln N enhancement and therefore contribute only at order N 2 . A similar argument can be made when one examines the geometry near the D5-branes using (4.41) before taking the large N limit.

Due to the presence of N5-branes, the second issue for our calculation is to understand if the string coupling, g s , is small so that string loop corrections can be ignored. The dilaton in the central region, -1 < x < 1, is given by

g s = e 2φ = 2N π -x 2 + cos(2y) 2 -cos(2y) . ( 4

.48)

We observe that the dilaton is small in the region 0 < x < 1 but is big in the region -1 < x < 0. We first focus our attention on the region 0 < x < 1. In the large N limit, the string coupling is small except in the neighborhood of x = 0, where it is of order one. Thus we expect string loop corrections to be important, but again we argue that since they are localized near x = 0, they will give contributions at most of order N 2 . For the region -1 < x < 0, we find that the string coupling is generically large and one might expect string loop corrections to modify the leading N 2 ln N behavior. From this point of view, the exact match between gravity and CFT partition functions is surprising. One possible explanation of the exact agreement, is that locally we may use an S-duality transformation on this region and compute the action in the S-dual geometry. This will then yield a geometry with a small string coupling, whose action we may reliably compute. Since the type IIB supergravity action is invariant under S-duality transformations, we then conclude that the original analysis also gives the correct answer up to order N 2 corrections. One subtlety in this picture is how to exactly glue the two different patches together after such an S-duality transformation. Since patching only needs to occur in the region near x = 0, we again argue that such subtleties will introduce corrections only of order N 2 . Similar arguments can be made when one examines the geometry near the NS5-branes using (4.41) before taking the large N limit.

T ρ ρ [SU (N )]

We now consider more general partitions which take the form (2.9). In this case, there is a single NS5-brane stack and the charge relations, (4.36), can be easily inverted to express the phases δ a and δ in terms of the partitions ρ and ρ:

δ a -δ = -ln tan π 2 l (a) N5 . ( 4

.49)

To analyze the large N behavior, we proceed analogously to the T [SU (N )] case and consider the limit where δ → -∞ and the δ a → ∞. In this case, we approximate the harmonic functions by the following expressions We now consider the scaling behavior defined by (2.10). The idea is to introduce separations between the δ a which are of order ln N . In this case each region between a given δ a and δ a+1 will contribute to the action at order N 2 ln N . In terms of this scaling the action becomes which coincides with (2.13).

h 1 = α sin(y) p a=1 N (
S eff = 1 2 N 2

Subleading Terms

So far we have concentrated on the leading N 2 ln N contributions to the free energy and it is a natural question to ask about the subleading N 2 contributions. Comparing the CFT and gravity partition functions, we find that the subleading N 2 contributions do not match. 10However, this is not surprising since the gravity solution contains 5-brane singularities around which supergravity approximation breaks down. It would be interesting to interpret and if possible match the subleading contributions to the CFT partition function with higher curvature corrections on the gravity side. For the T [SU (N )] theory, we note that near the D5-brane singularity, the Ricci scalar, (4.47) does not depend on N and so all powers of R will contribute at order N 2 . Similarly, one may check that other contractions of the Riemann tensor will also contribute at order N 2 . Thus even at order N 2 , the CFT partition function contains information about all of the higher curvature corrections.

N (p) 5 l 5 l( 1 )N ( 2 ) 5 l( 2 )

 551252 (p) , l (p) , .., l (p) , , l(1) , .., l(1) , , l(2) , .., l(2) , ... ,N ( p) 5 l(p) , l(p) , .., l(p) ,(2.1)

5 represent the 5 -

 55 branes charges of the supergravity solution (see section 4).

Figure 1 :

 1 Figure 1: We decompose the young diagram corresponding to ρ into p blocks, see (2.1).

  w∈S N ∼ O(N !), whose logarithm contributes O(N ln N ) to the F CFT . The remaining contributions come from the two sinh Vandermonde determinants, each of which involves N 2 ∼ O(N 2 ) terms. This gives

5 ,

 5 while the number of NS5-branes located at δ(b) is denoted by N (b) 5 . Unbroken supersymmetry requires that there are only branes (or only anti-branes) of each kind. Thus all the N (a) 5 must have the same sign, and likewise for all the N (b) 5 . This positivity condition is also necessary for smoothness away from the 5-brane singularities. The net number of D3-branes ending on the a-th D5brane stack is denoted by N (a) 3 , while the number of D3-branes ending on the b-th NS5-brane stack is denoted by N (b) 3 . These quantities are determined by the locations δ a and δb , of the 5-brane stacks as N δb -δa ) .

Figure 2 : 3 , 5 . 6

 2356 Figure 2: The infinite strip with logarithmic singularities corresponding to stacks of fivebranes. The upper (red) singularities correspond to D5-branes, while the lower (blue) singularities correspond to NS5-branes. The geometry smoothly caps off into an S 6 as x → ±∞. We define the total number of D3-branes as N ≡ p a=1 N (a) 3 = p b=1 N (b) 3 , and the linking numbers by l (a) = N (a) 3 /N (a) 5 and l(b) = N (b) 3 / N (b) 5 . 6 These parameters, N, N

Figure 3 :

 3 Figure 3: Geometry of the T [SU (N )] dual background represented by the strip with two 5-brane singularities at positions ±δ ∼ ± 12 log N . In the large N limit the stacks go to ± infinity.

1 4 , 2 = 2 √ 4 , b 1

 142241 4ρ 2α N e -δ [(2cos(2y))(2 + cos(2y))] and fluxes are given by (see B) e φ = e -δx 2 + cos(2y) 2cos(2y) 1 = 8α N e -δ(1+x) sin 3 (y) 2cos(2y) , b 2 = -8α N e δ(x-1) cos 3 (y) 2 + cos(2y) , j 1 = -e -2δ N 2 (α ) 2 (3xδ + cos(2y)) .

a) 5 e-W h 1 h 2 2 sin 2 2 sin 2 2 ( 2 (

 52222222 x-δa + ... if x < δ 1 , = α sin(y) -δa + ... if δ i < x < δ i+1 , h 2 = α cos(y) N5 e -(x-δ) + ... if x > δ ,(4.50)while the regions with x > δ p and x < δ will give only subleading contributions. In this approximation we find that W = -h 1 h 2 so that (2y) if δ < x < δ 1 , (2y) if δ i < x < δ i+1 . δ iδ i-1 )(4.52)where we define δ 0 ≡ δ. Plugging into (4.40) and combining all of the numerical factors, we obtain δ iδ i-1 ) + ... . (4.53)

The expression in[START_REF] Nishioka | 3d Partition Function as Overlap of Wavefunctions[END_REF] contains an extra factor of 1/N !. However, this factor does not alter the leading behavior of the free energy and hence will be dropped in this paper.

FI parameters are actually the differences of mi . However, we will loosely refer to m as FI parameters.

By generic we mean that there are no cancellations in the sum in the numerator of(3.15).

A small modification is needed for the formula (3.3) when αβ is odd. This does not, however, affect the leading behavior of the free energy.

The relations between the integer brane charges and the supergravity parameters are not easily inverted. To express the latter in terms of the brane charges one must solve a system of transcendental equations.

We use the convention |F (a) | 2 = 1 a! F (a) M1M2..Ma F M1M2..Ma (a).

The supersymmetric Janus solution is dual to N = 4 super-Yang-Mills with a jumping coupling.

We have checked this numerically for T [SU (N )] using the full expressions for the harmonic functions (4.41).

Acknowledgments

The authors would like to thank C. Bachas and J. Gomis collaboration in early stages of this project, and also for inputs crucial for the completion of this project. J. E. and M. Y. would like to thank Simons Center for Geometry for Physics (Simons Summer Workshop in Mathematics and Physics 2011) for hospitality. J. E. is supported by the FWO -Vlaanderen, Project No. G.0651.11, and by the "Federal Office for Scientific, Technical and Cultural Affairs through the Inter-University Attraction Poles Programme," Belgian Science Policy P6/11-P, as well as the European Science Foundation Holograv Network.

A Barnes G-function

Let us briefly summarize the properties of the Barnes G-function. Barnes G-function G 2 (z) satisfies

From the definition it follows that

Its asymptotic expansion is given by

B Flux Formulas

The NS-NS and R-R three forms can be written as 3-forms:

where ω 45 and ω 67 are the volume forms of the unit-radius spheres S 2 1 and S 2 2 , while the gauge potentials b 1 and b 2 are given by

In this expression one needs the dual harmonic functions, defined by

for holomorphic harmonic functions A 1 , A 2 . The constant ambiguity in the definition of the dual functions is related to changes of the background fields under large gauge transformations. The expression for the gauge-invariant self-dual 5-form is given by: 5-form:

where ω 0123 is the volume form of the unit-radius AdS 4 , F is a 1-form on ρ with the property that f 4 4 F is closed, and * 2 denotes Poincaré duality with respect to the ρ metric. The explicit expression for F is given by


Arshia Cont

José Echeveste

Florent Jacquemard

Jean-Louis Giavitto

CORRECT AUTOMATIC ACCOMPANIMENT DESPITE MACHINE LISTENING OR HUMAN ERRORS IN ANTESCOFO

Automatic accompaniment systems are comprised of realtime score following systems that in reaction to recognition of events in a score from a human performer, launch necessary actions for the accompaniment section. While the realtime detection of score events out of live musicians' performance has been widely studied in the literature, score accompaniment (or the reactive part of the process) has been rarely addressed. In this paper, we expose the respective literature concerning this missing consideration. We show how its explicit design considerations would allow correct accompaniment despite machine listening or human errors introduced during score following, and furthermore how it enables a more elaborate authoring of time and interaction for mixed live electronic pieces.

INTRODUCTION

Automatic accompaniment is the act of delegating the interpretation of one or several musical voices to a computer in interaction with a live solo (or ensemble) musician(s). The paradigm was first put through disjointly by Dannenberg and Vercoe in [START_REF] Dannenberg | An on-line algorithm for realtime accompaniment[END_REF][START_REF] Vercoe | The synthetic performer in the context of live performance[END_REF] where a computer would provide automatic accompaniment out of incoming symbolic signals (MIDI) from a musician. The most popular form of such systems is the automatic accompaniment of an orchestral recording with that of a soloist in the classical music repertoire (concertos for example) as described in [START_REF] Raphael | The informatics philharmonic[END_REF]. In a larger context, these systems became popular for interactive computer music repertoire [START_REF] Rowe | Interactive music systems: machine listening and composing[END_REF], where the association of live musicians with computer generated processes becomes crucial. Figure 1 shows the score of a simple interactive computer music piece where the top staff corresponds to the part for human musician and the lower staves correspond to automatic accompaniment sections that should be run synchronously to the first staff during live performance. Note here that the accompaniment commands depend exclusively on the nature of the computer music process in question. They can be symbolic commands, continuous curves or sequences written relative to the live instrument section of the score. Within this context, the case of automatic accompaniment for classical music repertoire is thus a special case of this larger context where accompaniment commands are replaced by either symbolic MIDI messages or a live rendering of an audio recording of the orchestral part. Figure 1. Score example for an interactive piece, the top staff contains the instrumental section whereas lower staves correspond to specific computer music commands.

The best starting point in the design of an accompaniment system is to observe the human counterpart. Musical accompaniment among musicians is a combined act of listening and coordination governed by music scores. While human listening plays a crucial role in accompaniment, it is (computationally speaking) fallible. Moreover, actions produced by musicians in an ensemble can contain (perceivable or unperceivable) errors. Despite such inconsistencies, the overall musical output should stay more or less intact and error-free. This is to say that despite the importance of the recognition (or listening) phase in musical accompaniment, the coherence of the overall musical output is to a great extent covered by the ability of human musicians to coordinate and anticipate their actions and adopt the best synchronization strategies in realtime to achieve the best musical output.

Automatic accompaniment systems in general are comprised of two main components as illustrated in figure 2: A score follower that is capable of decoding the live instrument position as well as necessary musical parameters in realtime given the instrumental score (for the top staff of fig 1); and a second component in charge of launching the accompaniment commands synchronously to the live musician (for lower staves in fig 1). In realtime control theory [START_REF] Shyamasundar | Real time programming: languages, specification and verification[END_REF], the score follower is an interactive system with transactions at its own speed with the environment (usually governed by signal processing and machine learning techniques). Execution speed is formally abstracted to be perceptively close to zero for such processes. The ac-companiment block is however a reactive system, reacting continuously to the external environment and at the speed imposed by the environment (the human performers).

Interactive System

Reactive System Score Follower Electronic Score Executor (qlist, messages, etc.) Sound Generation (MaxMSP / PureData) Figure 2. Architecture of an automatic accompaniment system comprising of interactive and reactive systems.

Considering both human and computer accompaniment together, the "healthiness" of the musical output of an accompaniment system requires as much considerations for the coordination/reaction phase as for the recognition phase. The general score following and accompaniment literature has however underestimated the first, focusing on robustness in the listening phase; leaving the action phase to hand-engineered and most often preliminary considerations for the accompaniment actions. This lack of consideration for action coordination would in return reduce the paradigms of interaction between human and computer mediums for interactive pieces, leading to severely simplified programming and authorship for mixed instrumental and live electronic pieces as discussed in [START_REF]On the creative use of score following and its impact on research[END_REF].

In this paper, we aim to illustrate the importance of the reactive system architecture in automatic accompaniment and showing its usefulness within two contexts: (1) the ability to automatically handle machine listening or human errors with no propagation to the accompaniment output; and (2) to enrich the vocabulary of live electronics accompaniment by providing explicit access to the authoring of time and interaction in the interactive computer music repertoire. We therefore assume throughout this paper that an interactive listening system is readily available and focus on handling and authoring accompaniment actions. This paper discusses the integration and employment of the proposed paradigms within the Antescofo1 [START_REF] Cont | Antescofo: Anticipatory synchronization and control of interactive parameters in computer music[END_REF] software coupling both listening and coordination aspects of such systems. In section 2 we discuss previous works that explicitly handle accompaniment actions integrated within a score following systems. We showcase and motivate problems with existing approaches in section 3 and propose an approach to exposed problems by adopting synchronization strategies during authorship and run-time in section 4. We conclude the paper by illustrating several examples of this approach for automatic accompaniment as well as live electronic pieces using Antescofo.

PREVIOUS WORKS

In this section, we overview two existing and popular systems that handle both machine listening and online accompaniment. For the scope of this paper, we focus on the way automatic accompaniment is transcribed and handled in such systems. Therefore, we do not provide any discussions on the machine listening aspects and do not overview all existing score following systems.

Music-Plus-One

Music-Plus-One is a musical accompaniment system developed by Christopher Raphael for the classical music repertoire and destined for a soloist in a concerto-like setting. The system is decomposed into three modules: one for a realtime score match using hidden Markov models, a second for coordinating audio playback of the existing accompaniment using a phase-vocoder, and a third for linking the two using a Kalman filter model for tempo adjustments [START_REF] Raphael | The informatics philharmonic[END_REF]. Whereas the listening and decoding parts of Music-Plus-One is well documented, there are no explicit documentation on the authoring and handling of the coordination for the accompaniment part (at least at the time of writing this paper). However, demos of the software are available on the web2 . Here we aim to study the making of the accompaniment part in order to understand the behavior of the system in an online accompaniment setting. Music-Plus-One's application is destined for the classical music repertoire and concerto-like settings. It has been however rarely used for contemporary interactive music repertoire. Understanding the synchronization and coordination strategies are important for the creation of new pieces for the system. The discussions hereafter are thus by no means a criticism of this approach.

Music-Plus-One uses the following minimal text data to undertake automatic accompaniment: a musical score of the solo part, an audio recording of the orchestral or accompaniment part, a set of trained parameters for the listening model (trained offline and used during realtime detection), and some timing data in charge of associating the solo score to the accompaniment audio for the rendering phase. Among these, the timing data is of outmost importance since it creates the necessary binding between the soloist score and the accompaniment audio that will be employed during realtime rendering. Figure 3 shows an excerpt of Music-Plus-One text input for illustrating this point. On the left, is a text description of the soloist music score, in terms of relative position in a measure, MIDI pitch numbers and other necessary information for the listening module. On the right (a separate text file), each line contains the accompaniment audio onset time for the specific event in the solo score. This correspondence is (most probably) obtained by a rigorous segmentation of the accompaniment audio with regards to the solo score, to provide coherent musical phrases to be used during live accompaniment rendering. Note that the coordination points on the right, do not necessarily correspond to the solo score. This is normal since an optimal segmentation of accompaniment onsets should be based on musical phrasing rather than a one-to-one correspondence.

Within the structure described in the above example, it is not clear how Music-Plus-One handles machine listening or human errors during live performance. Depending on the musical context, and in presence of machine listening or human errors (missing events for example), one might want to skip an accompaniment phrase or launch it with varying speed. Moreover, preparing such accompaniment/coordination score seems to be a heavy phase in preparing an accompaniment and not very suitable for compositional purposes.

Antescofo

Antescofo [START_REF] Cont | Antescofo: Anticipatory synchronization and control of interactive parameters in computer music[END_REF] is another polyphonic score following system capable of handling accompaniment actions and integrated within the same system. The listening machine of Antescofo is documented in [START_REF]A coupled duration-focused architecture for realtime music to score alignment[END_REF] and some aspects of its accompaniment language in [START_REF] Cont | Antescofo: Anticipatory synchronization and control of interactive parameters in computer music[END_REF][START_REF]On the creative use of score following and its impact on research[END_REF]. The main musical paradigm addressed by Antescofo is that of mixed instrumental and live electronic (or interactive computer music) pieces, where the "accompaniment actions" can range from a simple concerto-like setting to triggering of live electronic processes as common in interactive computer music. Antescofo requires no training for its listener and accept a single text as score input.

An Antescofo score is composed of both instrumental (soloist) score and the accompaniment actions within one integrated score. Figure 4 shows an example of a simple Antescofo score with both instrumental and accompaniment actions. The semantics of the instrumental score allows the construction of complex events such as trills, glissandi, improvisation boxes and also continuous events. The (accompaniment) action semantics is entirely based on message-passing and provides constructions for grouping of events in order to create polyphonic phrases, as well as loops and continuous trajectories. The timing of actions can be relative (to the score tempo) in floating points or rational numbers, or in absolute time. Graphical representation and authoring of such scores is possible thanks to its integration within the NoteAbility score editor. Figure 1 is in fact an illustration of an Antescofo score featuring three discrete-sequence groups (green boxes), a continuous trajectory and a symbolic action group (lower staff) as accompaniment actions, all living within a single score framework. In its original text format, composers are also able to create nested hierarchies within electronic phrases (groups inside groups), employ macro expansions and use data flow functionals (see [START_REF]On the creative use of score following and its impact on research[END_REF] for descriptions).

BPM 60! ! NOTE 60 1.0! ! Group1{! !0 action11! !½ action12! }! ! NOTE 67 1.0! ! Group2{! !0 action21! !½ action22! }! Performer' events' Electronic'' ac1ons' a21' a22' Group2' a11' a21'
Group1' The role of Antescofo in realtime is to decode the position and tempo of the performer within a synchronous reactive system to best interpret the accompaniment section. Compared to previous approaches in interactive computer music, the accompaniment actions can be described as relative to the performers' tempo and thus dynamically rescheduled in realtime. Each action's starting point is relative to its backward closest event in the instrumental score. The phrasing schemes available in Antescofo allow the scope of such electronic phrases to go beyond interonsets of the instrumental score.

While the ability of authoring parallel phrases (as opposed to segmented and chopped actions) makes the act of authoring more appealing, such timing overlaps create important issues both for realtime coordination of events with the live performer and also their authoring. For example, for a simple concerto-like accompaniment setting, one might want to specify the accompaniment part as one single (and non-chopped and non-segmented) electronic phrase. This appealing tendency creates interesting challenges for synchronization strategies as well as error handling of the virtual accompaniment interpreter which are described in the next section.

MOTIVATIONS

Synchronizing electronic with live musicians

For compositional purposes, it seems more natural to be able to express accompaniment actions as phrases as opposed to small segments within instrumental note onsets. However, such additions require explicit and dynamic strategies for handling synchrony between accompaniment actions when their scope goes beyond that of its starting instrumental event. The need for such strategies become even more crucial when tempo changes occur after the phrase's launch. Figure 5 attempts to illustrate this within a simple example: Figure 5(a) shows the ideal perfor-mance or how actions and instrumental score is specified to the system. In this example, an accompaniment phrase is launched at the beginning of the first event from the human performer. The accompaniment here is a simple group consisting of four actions that are written parallel to subsequent events of the performer in the original score. In an ideal setting (i.e. correct listening module) the action group is launched synchronous to the onset of the first event. For the rest of the actions however, the synchronization strategy depends on the dynamics of the performance. This is demonstrated in figure 5(b) where the performer hypothetically decelerate the consequent events in her score. In this case, the delays between the actions and their corresponding instrumental event will naturally increase. Such asynchrony is despite correct decoding of tempo from the listening machine. We note however, that this behavior ensures a smooth synchronization with performer tempo changes, but without any guarantee for position synchronicity. Although this behavior is desired in some musical configurations, it seems natural to propose an alternative strategy where the electronic actions would be synchronous to the events detection.

The case of machine listening or human errors

The musical output of an automatic accompaniment system should not solely depend on its listening module or even to the human performer at specific circumstances. This is in analogy to human coordination for ensemble performance: A live music performance output should not be at stake in presence of any error in realtime.

In a live performance situation different errors may be encountered: the listening module could confuse an event with another, miss an event, or produce a false-alarm. Additionally, musicians might introduce performance errors that can affect the accompaniment results. In all cases, we expect not only that the system continues to work, but also that it reacts as musically as possible. Parts but not all of these errors can be handled directly by the listening modules (such as false-alarms and missed events by the performer). The critical safety of the accompaniment part can thus be reduce to handling of missed events (whether missed by the listening module or human performer). The natural question to ask in this case is what the system should do in case of a missed event? Should the associated actions be performed or not? The answer to this question seems more musical than technical: In some automatic accompaniment situations, one might want to dismiss associated actions to a missed event if the scope of those actions does not bypass that of the current event at stake. On the contrary, in many live electronic situations such actions might be initializations for future actions.

This discussion shows that while such considerations can be addressed automatically in special cases, error handling attributes should be first-class citizens in any specification language for automatic accompaniment and interactive computer music pieces.

PROPOSED APPROACH

The musician's performance is subject to many variations from the score. There are several ways to adapt to this musical indeterminacy based on specific musical context. The correct synchronization and error handling strategies is at the composer or arranger's discretion. To this end, we propose explicit synchronization and error handling strategies as attributes for the composer to choose, taking into account performance variations and to manage the errors of the musician and the recognition algorithm. In this paper, we provide a verbal description of the proposed approach. The formal and semantical definition of these concept are described in [START_REF] Echeveste | Antescofo: a Domain Specific Language for real time musician-computer interaction[END_REF].

Accompaniment phrase and loop constructs are used to start a sequence of actions from a trigger event in the instrumental score. Once a sequence of relatively-timed actions is launched, its synchrony by default is governed by dynamic rescheduling following changes of tempo from the musician. However, as seen in section 3.1, knowledge of realtime tempo is not sufficient for precise synchronization with events played by the musician as shown in Figure 5. While this loose synchrony is useful in some musical context (loose phrasing of electronics for example), it is not always desirable. For a finer synchronization, we provide the composer the ability to assign a tight attribute to a phrase block. If a block is tight, its inside actions will be dynamically analyzed to be triggered not only using relative timing but also relative to the nearest event in the future. This new feature evades the composer from segmenting the actions blocks to smaller segments with regards to synchronization points and provide a highlevel vision during the compositional phase. A dynamic scheduling approach is adopted to implement the tight block behavior. During the execution, the system attempts to synchronize the next action to be launched with the corresponding event using a hybrid strategy employing both tempo and future-event positions.

The problem of error handling, as discussed in section 3.2, boils down to the ability of attributing scopes to accompaniment phrases and blocks. Despite their space occupancy in the score, a block is said to be local if dismissible in the absence of its triggering event during live performance; and accordingly it is global if it should be launched in priority and immediately if the system recognizes the absence of its triggering event. Once again, the choice of an entity being local or global is given to the discretion of the composer.

The combination of the synchronization strategy attributes (tight or loose) and error handling attributes (local or global) for a group of accompaniment actions give rise to four distinct situations. Figure 6 attempts to showcase these four situations for a simple hypothetical performance setup. In this example, the score is assumed to demand for four distinct performer events (e 1 to e 4 ) with grouped actions whose two actions are initially specified to occur on e 1 and e 3 . The figure demonstrates the simulation of the system behavior in case e 1 is missing during live performance for the four configurations discussed above. Naturally, in our realtime setup, e 1 is reported as missed once e 2 is detected. It is worth to note that each combination corresponds to a specific musical situation encountered in authoring of mixed interactive pieces: local and loose: A block that is both local and loose corresponds to a musical entity with spatial independence with regards to its counterpart instrumental events, and strictly reactive to its triggering event onset (thus dismissed in the absence of this event).

local and tight: Strict synchrony of inside actions whenever there's a spatial correspondence between events and actions in the score. However actions within the strict vicinity of a missing event are dismissed. This case corresponds to an ideal concerto-like accompaniment system. and tight: Strict synchrony of corresponding actions and events while no actions is to be dismissed in any circumstance. This situation corresponds to a strong musical identity, strictly tied to the performance events.

global and loose: An important musical entity with no strict synchrony once launched. Such entity is similar to musical phrases that have strict starting points with rubato type progressions (free endings, tempo-synchronous).

SAMPLE RESULTS

The above proposal has been integrated in Antescofo's formal language and adopted in various new music productions involving live instrumental and electronic music. The best test for such systems is to see and use them in action. For the sake of completeness we discuss two sample results: one on a simple automatic accompaniment setting and another in case of a contemporary music production. Curious readers are referred to our website for further videos and events3 .

In the first example, we attempt to reconstruct the performance of a four-voice Fugue by J.S. Bach (in B-minor) where one voice is performed by a musician and others by automatic accompaniment. Figure 7 shows the score for this performance. In this example, and on purpose, the three accompanying voices are written as three distinct groups of actions (for MIDI accompaniment in this case). Each block corresponds to the accompaniment actions for each voice and the top staff represents the instrumental part. We choose tight synchronization strategies to ensure precise synchrony with a performer and also between different accompaniment voices. To ensure musical consistency, local strategies are assigned to the groups. In this way, missed event's corresponding actions will be dismissed without altering the overall performance. Despite its intuitive nature in run-time, the way the accompaniment voices are written and handled in realtime provide ease of authoring for composers willing to use such systems for their compositions.

The second example is an excerpt score from the beginning of "Tensio" (2010) for String Quartet and live electronic by French composer Philippe Manoury as illustrated in Figure 8. The left side of Figure 8 corresponds to the hand-written manuscript (excerpt) containing both instrumental (string section, four staves in bottom) and live electronic scores (top staves), and the right side of the figure correspond to its Antescofo equivalent used during live performance. The Antescofo score describes three parallel group actions entitled arco, h1-trans and Pizzicati corresponding to the left column. The two groups arco and Pizzicati contain discrete and atomic sequences (defined with the keyword GFWD) whereas the h1-trans (defined as CFWD) contains a continuous sequence. The continuous process h1-trans correspond to the top staff in the left column. During realtime performance their polyphonic synchrony is assured despite any variations in the performance. These groups are notated as global and loose (the default behavior of Antescofo) and correspond as discussed to integral musical phrases launched in parallel to the instrumental world and influenced by the environment's tempi.

BPM$ $72$ TRILL $$($8500$)$ $0.5 $ $IA...EVT41$ GFWD $ $arco$$ {$$ $syn_voices$1 $pgm$40$ $bnk$7 $vol$122 $$ $syn_voices$1 $56 $$120$ $@b(2)$ $syn_voices$1 $50 $$120$ $@b(2)$ $syn_voices$1 $46$ $120 $@b(2)$ 2.0 $$syn_voices$1 $53$ $$120$ $@b(0.36)$$ $syn_voices$1 $52 $$120$ $@b(0.36)$ $syn_voices$1 $58 $$120$ $@b(0.36)$ 0.36 $syn_voices$1 $69 $$120$ $@b(1.5)$ $syn_voices$1 $63 $$120$ $@b(1.5)$ $syn_voices$1 $59 $$120$ $@b(1.5)$ 1.5$ $syn_voices$1 $66 $$120$ $@b(0.8)$ $syn_voices$1 $65 $$120$ $@b(0.8)$ $syn_voices$1 $62$$$$$$$$$$$$$120$$$$$$$$@b(0.8)$$ }$ CFWD$$$$$$$$$$$$$$h1_trans $@grain$30ms$ {$ $ $0$$$$$$$$$$$$$$0$$$$$$$$$$$$$$$ $2.0$$$$$$$$$$$300$ $0 $0$ $0.46 $800$ $0 $0$ $1.5 $4500$ }$ GFWD $0.

CONCLUSION

In this paper we attempted to formalize the problem of synchronization and coordination of actions in an auto-matic accompaniment setting by considering them as reactive synchronous systems on top of classical score following and machine listening. With such considerations we aimed at addressing the error handling and intelligent synchronization strategies despite human or machine listening error imposed to the system during a live performance. This is in contrast to most existing approaches where the integrity of the musical output is highly dependent on the healthiness of the artificial listening modules at work. This becomes possible by studying the language constructs of both music composition and performance within a computer setting. The solutions proposed in the paper try to cover various musical situations that correspond to concerto-like accompaniment settings as well as compositional and performative aspects of interactive computer music pieces. They are integrated within the Antescofo software and have been employed in various music productions.

The coupling of high-level computer language constructions with that of low-level machine listening, at the core of this paper, is a necessity in musical practices of interactive computer music and requires more research in the computer music community. We believe that research on those lines could address complex problems with simple and elegant solutions useful for both music composition and live performance.

Figure 3 .

 3 Figure 3. Excerpts of Music-Plus-One input. Left is the soloist score, Right is the coordination score. Extract from Beethoven's Romance 2 for violin and orchestra, Op. 50'.

Figure 4 .

 4 Figure 4. Sample score diagram and the corresponding simple Antescofo score

Figure 5 .

 5 Figure 5. The effect of tempo-only synchronization for accompaniment phrases. Illustration for different tempi.

Figure 6 .

 6 Figure 6. Accompaniment behavior in case of missed event for 4 synchronization and error handling strategies.

Figure 7 .

 7 Figure 7. Antescofo score of Bach's B-minor fugue in automatic accompaniment mode, in NoteAbility Pro.

Figure 8 .

 8 Figure 8. Score manuscript of the first bars of "Tensio" (left), and the Antescofo counterpart (right).

http://repmus.ircam.fr/antescofo

http://music-plus-one.com/

http://repmus.ircam.fr/antescofo


Anh-Phuong Ta
email: anh-phuong.ta@inria.fr

Guillaume Gravier
email: guillaume.gravier@irisa.fr

UNSUPERVISED MINING OF MULTIPLE AUDIOVISUALLY CONSISTENT CLUSTERS FOR VIDEO STRUCTURE ANALYSIS

Keywords: Multiple events, Video mining, Video structuring, Cluster selection, Mutual Information, Event discovery, Structural event, Audiovisual consistency

We address the problem of detecting multiple audiovisual events related to the edit structure of a video by incorporating an unsupervised cluster analysis technique into a cluster selection method designed to measure coherence between audio and visual segments. First, mutual information measure is used to select audio-visually consistent clusters from two dendrograms representing hierarchical clustering results respectively for the audio and visual modalities. A cluster analysis technique is then applied to define events from the audio-visual (AV) clusters with segments co-occurring frequently. Candidate events are then characterized by groups of AV clusters from which models are built by automatically selecting positive and negative examples. Experiments on the standard Canal9 data set demonstrates that our method is capable of discovering multiple audiovisual events in a totally unsupervised manner.

INTRODUCTION

Generally speaking, video structuring consists in extracting semantic events-e.g., actions in sport videos, violent scenes in movies, etc.-and/or events related to the edition of the video-e.g., monochrome frames, dissolve, shot boundaries, etc.-so as to segment the video into its constituents. In this work, we define a structural element as a key content that appears frequently in a video and exhibits audio and visual consistency. Typical examples of such events are jingles in news videos, anchor persons or participants in a talk show, etc. Existing approaches to video structure analysis fall into two main categories: i) segmentation of the entire video (referred as dense segmentation), where the input video is mapped to a predefined structure, like points, games or sets in tennis videos; ii) detection of specific events related to the video structure, such as advertisements or goals in sport videos. This paper presents a novel approach belonging to this last category where events are defined from the data rather than a priori. We focus on the detection of multiple events relevant to the structure of a video, in a totally unsupervised fashion without any prior knowledge about the events to be detected. Our aim is to propose a generic method for video structure analysis, which can have applications in semi-supervised video annotation and edition, automatic structuring of videos, summarization, etc.

In the multimodal video mining literature, many efforts have been focusing on supervised learning (see [START_REF] Snoek | Multimodal video indexing: A review of the state-of-the-art[END_REF]) and content-based analysis techniques such as speech recognition or face detection and identification. For instance, such approaches have been employed for anchor person detection [START_REF] Chua | Story boundary detection in large broadcast news video archives: techniques, experience and trends[END_REF], or for the detection of specific events like goals in sport videos [START_REF] Wang | A generic framework for semantic sports video analysis using dynamic bayesian networks[END_REF]. Similarly, Li et al. [START_REF] Li | Adaptive speaker identification with audiovisual cues for movie content analysis[END_REF] proposed to combine face recognition and speaker detection to find occurrences of characters in movies. Despite their success, the common limitations of such supervised methods are the need to train a model from manually annotated data and the lack of robustness to unseen data. Moreover, some methods require a manual initialization step, e.g., [START_REF] Li | Adaptive speaker identification with audiovisual cues for movie content analysis[END_REF], therefore, lacking the generality to cope with diverse video genres.

As an alternative, detecting repeating patterns has been considered [START_REF] Covell | Detecting ads in video streams using acoustic and visual cues[END_REF][6] [START_REF] Yang | Efficient short video repeat identification with application to news video structure analysis[END_REF]. However, such methods focus on discovering near-duplicate repetitions, and cannot deal with variations across repetitions (i.e., the repetitions are not exact), which is a crucial issue in video structuring. The problem of mining repeating structural elements has also been addressed using clustering techniques [START_REF] Divakaran | Video summarization using mpeg-7 motion activity and audio descriptors[END_REF][9][10] [START_REF] Dielmann | Unsupervised detection of multimodal clusters in edited recordings[END_REF] to group video shots exhibiting a strong visual similarity, which are likely to be relevant with respect to the structure of the video. However, clustering-based techniques cannot avoid the nontrivial problems of choosing the optimal number of clusters, and of dealing with outliers (as most of the data does not fit into any cluster).

To overcome these drawbacks, we propose an unsupervised approach to detect multiple events exhibiting a strong audio and visual consistency, often related to the video editing. We elaborate on the work of Ben and Gravier [START_REF] Ben | Unsupervised mining of audiovisually consistent segments in videos with application to structure analysis[END_REF][13] and of Dielmann [START_REF] Dielmann | Unsupervised detection of multimodal clusters in edited recordings[END_REF]. The former have proposed an unsupervised method to detect a single audiovisual structural event without any prior knowledge. From two dendrograms representing hierarchical clustering results of the audio and visual modalities, they measure the consistency between an audio cluster and a visual cluster using mutual information in the temporal domain. Several heuristics are then applied to select a unique pair, made of an audio and a visual clusters, relevant to the video structure. As in most cases, discovery of multiple events is not considered while many videos exhibit several structural events (e.g., two anchor persons, guests in talk shows). However, the work of Dielmann [START_REF] Dielmann | Unsupervised detection of multimodal clusters in edited recordings[END_REF] was designed to select multiple pairs of audio and visual clusters from two independent partitions of the data. To this end, Pearson's χ 2 statistical test is adopted to analyze the co-occurrences between audio and visual labels (clusters). AV-clusters are then identified as the ones whose labels most frequently co-occur. However, this method entirely relies on the performance of the partitioning algorithms used to construct two sets of labels corresponding to, resp., the audio and visual modalities. In particular, the number of clusters in each partition has to be defined in some way.

In this paper1 , we introduce a new scheme which combines the use of nested clusters and mutual information criterion with the χ 2 statistical test to select multiple pairs of audio-visual clusters, thus defining several structural events from the data. Note that, this paper differs from [START_REF] Dielmann | Unsupervised detection of multimodal clusters in edited recordings[END_REF] in two major ways. First of all, we propose a method that does not need initial partitioning of the audio and visual data. Moreover, the absence of labels attached to segments as a result of the partioning steps requires significant adaptation of the χ 2 criterion. In particular, as opposed to the detection of only a single event in [START_REF] Ben | Unsupervised mining of audiovisually consistent segments in videos with application to structure analysis[END_REF], we propose a fully unsupervised method able to detect multiple sets-clusters-gathering audiovisually consistent segments, selecting and grouping pairs of audio and visual clusters from two independent hierarchical clustering trees, one for each modality. Further, automatic selection of positive and negative samples enables to refine the results using support vector machines in addition to the initial discovery step.

The rest of the paper is structured as follows. Section 2 presents the general framework to discover multiple events. In section 3, we briefly present the audio and visual clustering step. We discuss how to select structurally consistent clusters in section 4, and presents our adaptation of the χ 2 test for relevant event identification in section 5. Event characterization and modeling is discussed in section 6. In section 7, we describe experimental results, followed by the conclusion and future work in section 8.

OVERVIEW

The general idea of the algorithm, illustrated in Figure 1 is as follows: two segmentations are built independently for the audio and visual modalities and a set of nested clusters is established for each modality using hierarchical bottomup clustering. This initial step results in two independently constructed dendrograms, where each node represents a set of (supposedly) coherent segments. We then explore crossmodal relations to select pairs of audiovisual clusters-one from each modality-which define consistent audiovisual segments. This idea is introduced in [START_REF] Ben | Unsupervised mining of audiovisually consistent segments in videos with application to structure analysis[END_REF] where the single most consistent pair of clusters is selected according to some heuristics on the pattern of occurrence of structurally relevant events. A rather similar philosophy is used in [START_REF] Dielmann | Unsupervised detection of multimodal clusters in edited recordings[END_REF] to select pairs of segments assuming each segment is labeled. The key difference is that in [START_REF] Dielmann | Unsupervised detection of multimodal clusters in edited recordings[END_REF] a unique segmentation is used in each modality, with cluster labels attached to segments, rather than a nested hierarchy of clusters. Exploiting the general idea of selecting consistent pairs of clusters, we investigate the selection of multiple events, combining several criteria. First, a list of candidate pairs is constructed from the N most consistent AV-cluster pairs according to the mutual information criterion. These candidates are then filtered using a χ 2 test and events are defined from the filtered list by grouping pairs corresponding to the same underlying event. Finally, for each candidate group (or event), segments are automatically selected to train a SVM classifier which is used to refine event detection. In the next sections, we discuss, in turn, each step of the process.

SEGMENTATION AND HIERARCHICAL CLUSTERING

The audio and video streams are first independently segmented into audio and video segments, respectively. For each modality, a classical bottom-up clustering technique is used to create a set of nested clusters represented as a dendrogram.

The dendrogram encodes the various stages of the hierarchical clustering and each node in the dendrogram corresponds to a set of segments, either in the video or in the soundtrack. Audio segmentation implements a standard Bayesian information criterion to detect abrupt changes in the signal. Gaussian mixture models (GMM) are used to model each segment and an approximation of the Kullback-Liebler divergence between two GMMs is used for agglomerative bottom-up clustering. This approach, commonly used in speaker segmentation systems, groups segments with similar audio contents, e.g., sharing the same type of music or the same speaker voice. The video is segmented into shots based on color histograms to detect changes across different frames and a keyframe is extracted for each shot. Keyframe clustering is also color-based, each shot being represented by its color histogram in the RGB space with 8 bins per color. Euclidian distance and Ward's linkage are used in bottom-up clustering.

CONSISTENT CLUSTER SELECTION

Given the audio and visual dendrograms, the next step consists in selecting relevant pairs of audiovisual clusters (AV cluster pair), where an AV cluster pair consists of one node Fig. 1: Schematic illustration of our approach to detecting multiple events (best viewed in color).

from the audio dendrogram and one from the video one.

Hence, an AV cluster pair is defined by the set of audio segments corresponding to the audio cluster and the set of video segments which corresponds to the visual cluster. Let (C A i , C V j ) be an AV cluster pair composed of the ith and the j-th clusters of the audio and video dendrograms, respectively. Our objective is to measure the consistency between the AV cluster pair. To this end, the mutual information (MI) is applied:

M I(C A i , C V j ) = (a,v)∈{(0,0),(1,1)} p(a, v) ln( p(a, v) p(a)p(v) ) (1)
where a and v are binary random variables which indicate membership in C A i and C V j , respectively. The probabilities p(a, v), p(a), and p(v) are estimated from the temporal segmentation. For example, the join probability p(a = 1, v = 1) is measured as the amount of time that segments of C A i and segments of C V j co-occur, normalized by the total duration of the video. A large value of the MI therefore indicates that the two corresponding clusters are closely consistent with each other.

Audiovisual consistency is measured using Equation 1 for each possible cluster pair and a list of the N best pairs is established. It must be noted that some pairs in the N-best list are strongly overlapping due to the fact that a dendrogram defines a set of nested clusters. Moreover, some AV cluster pairs might be irrelevant for video structure analysis. The next two steps of the algorithm therefore consist in selecting relevant pairs before grouping overlapping pairs which correspond to the same underlying event in the video. We detail the first step in the next section.

RELEVANT EVENT IDENTIFICATION

In [START_REF] Ben | Unsupervised mining of audiovisually consistent segments in videos with application to structure analysis[END_REF], the selection of a single AV cluster pair was considered using heuristics to measure the relevance to the structure of the video. However, this only allows for the selection of a single pair and is highly application dependent. Instead, inspired by the work from Dielmann [START_REF] Dielmann | Unsupervised detection of multimodal clusters in edited recordings[END_REF], we use a cluster analysis technique based on Pearson's χ2 test to identify relevant pairs in the N-best list generated using mutual information.

Cluster analysis using χ 2 test

Pearson's χ 2 test can be used to verify whether two random variables are statistically independent or not. Particularly, Dielmann used χ 2 to compare pairs of labels (clusters) resulting from an independant partitions of the audio and visual modalities 2 . The test intends to determine whether a pair of labels (clusters) resulting from the partitioning step, expressed in a contingency table (matrix), are independent of each other (i.e., the null hypothesis) or not. In other words, the test consists in determining if two labels jointly occur more frequently than at random. Formally, let O be a U × V matrix, where each entry O ij represents the number of times that a pair (i, j) (i.e. the co-occurrence of an audio segment labeled i and a video segment labeled j) is observed, and U , V are the audio and visual dictionaries, respectively. Under the null hypothesis that the occurrence of a video cluster and an audio cluster is statistically independent, the maximum likelihood estimated probability p(i, j) of the pair of labels (i, j) is given as

p(i, j) = p(i)p(j) = U k=1 O ik N V l=1 O lj N , (2)
where N is the total number of observations, i.e., the sum of all entries in the matrix O. Under the null hypothesis, the expected (theoretical) frequency for any pair of labels is given by E ij = N.p(i, j). The χ 2 aims at identifying audiovisual label pairs (i, j) which co-occur more frequently than the expected frequency under the null hypothesis E ij . Globally, the value of the test statistic χ 2 is given by:

X 2 = U i=1 V j=1 (O ij -E ij ) 2 E ij (3)
The higher the value of X 2 , the bigger the deviation from the expected value under the null hypothesis and, hence, the higher the confidence that the two partitions coincide.

Identification of candidate events

Our idea consists in applying the χ 2 test to select AV cluster pairs relevant to the structure of the video from the N-best list of pairs obtained with mutual information. In other words, we want to find cutting points in the dendrograms where the resulting sets of audio and visual segments coincide more than at random. However, contrary to Dielmann's work, no labels are available and clustering does not provide a partition of the data into several classes. Therefore, applying the χ 2 test statistic as described in the previous section is not straightforward. Rather, we consider binary labels instead of an arbitrary number of labels obtained from a partitioning step. Let us consider the audiovisual segmentation resulting from the union of the audio and visual boundaries. Considering one AV cluster pair (i.e., a node from the audio dendrogram and one from the visual one), each audiovisual segment can be labeled with a binary label indicating whether the segment belongs to the AV cluster or not. More precisely, for a given AV cluster pair, we analyze the co-occurrences between audio and visual segments by the chi-squared distribution with 1 degree of freedom, i.e., O is now a 2 × 2 matrix representing the observations for two binary variables. The frequency of each pair of labels (i ∈ {0, 1}, j ∈ {0, 1}) is computed as the number of corresponding audiovisual segments 3 . For instance, for a given AV cluster pair, 0 11 is the number of audiovisual segments belonging to both the audio and visual cluster, while 0 10 indicates the frequencies of audiovisual segments that belong to the audio cluster but do not belong to the visual cluster. Since our objective is to determine whether there is a significant relationship between an audio cluster and a visual cluster, only the contribution of O 11 to the test statistic χ 2 is verified. In particular, we compare a χ 2 distribution with a variable X 2 11 :

X 2 11 = (O 11 -E 11 ) 2 E 11 (4)
A threshold on the value of X 2 11 (set to 15 in our experiments) is used to decide if a given audiovisual cluster is relevant, i.e. jointly occur with sufficient frequency to be of interest for structure analysis. It can be observed that the χ 2 statistic is not reliable if the expected frequencies (E ij ) are too small (this problem was not mentioned in [START_REF] Dielmann | Unsupervised detection of multimodal clusters in edited recordings[END_REF]). In our experiments, we reject pairs of labels (i.e., AV cluster pairs) for which E 11 < 1. The χ 2 test is applied to all elements in the N-best list, yielding a filtered list of highly consistent pairs.

It is interesting to note that, at first glance, the mutual information (cf. Eq. 1) and the χ 2 test (cf. Eq. 4) encodes similar information and might therefore be redundant. However, Eq. 1 tends to select time-based consistent AV cluster pairs which generate time-based consistent segments, regardless of their frequencies. This may result in partially discov-ered events, i.e., events for which only a few occurrences were discovered, a fact that was experimentally confirmed. On the contrary, Eq. 4 selects AV cluster pairs based on the occurrence frequency only, which cannot ensure that all selected AV clusters are relevant. Therefore, both methods must be combined to ensure that the filtered N-best list contains AV cluster pairs consistent both in time-wise and frequency-wise.

EVENT CHARACTERIZATION AND MODELING

Because of the nested cluster structure of the dendrograms, the filtered list of AV cluster pairs contains redundant entries which correspond to the same underlying event. Typically, considering the parent (or the descendant) of either the audio cluster or the video cluster of a good AV cluster pair will most probably result also in a good AV cluster pair as the two (audio or visual) clusters, which differ only by one segment. It is therefore necessary to group redundant entries to define events for which models can be built in an unsupervised fashion.

Advantage is taken of the dendrogram structure to group AV cluster pairs which share segments. All AV cluster pairs belonging to the same branches in the two dendrograms are grouped together. The result is a list of non-intersecting groups, each of which represents a potential event.

Each potential event is thus characterized as a group of AV cluster pairs from which a model can be built by automatically selecting positive and negative examples. Let E = {e 1 , e 2 , ..., e m } be a group of AV cluster pairs, where e i represents an AV cluster pair (C A , C V ) with the corresponding temporal segments (S A , S V ). Positive and negative samples for each pair e i ∈ E are determined as follows:

AV s k ∈ +1l if s k ⊂ S A ∩ S V AV s k ∈ -1l if s k ⊂ S A ∪ S V
where s k is an audiovisual segment as defined previously and AV s k is the corresponding audiovisual feature vector (i.e., the concatenation of the audio and visual features used for clustering). To select training samples for the group E, each element in the group cast its votes for negative and positive, and the accumulated results are kept for all elements. Thresholding is applied on the accumulated results of the votes to select positive and negative samples for the group. In our experiments, a (positive or negative) sample is selected if its votes are greater than the mean value of the corresponding accumulated voting result. In other words, we select as positive samples of an event those audiovisual segments which appear in most of the AV cluster pairs e i . Similarly, negative samples correspond to audiovisual segments which appear rarely (if at all) in the AV cluster pairs characterizing the event. From the selected positive and negative examples, a binary SVM classifier is trained, yielding a model of the event which is classically used to detect the event considered in the video.

EXPERIMENTAL RESULTS

Experiments are carried out on the standard, publicly available, Canal9 political debate data set (cf. Fig. 2), provided by Vinciarelli et al. [START_REF] Vinciarelli | Canal9: A database of political debates for analysis of social interactions[END_REF] in 2009. To the best of our knowledge, this is the only publicly available data set that can be used to test audiovisual structuring tasks. This data set contains a collection of 72 political debates with roughly 42 hours of edited high quality audiovisual recordings, recorded by the Canal 9 local TV station and broadcast in Valais, Switzerland. Debates exhibit a strong audiovisual structure, with a limited number of speakers and a limited number of camera viewpoints. As a result, multiple audiovisually consistent events can be found in such videos. Typically such events are a close-up of one of the guests speaking or a global view of the guests with the anchor speaking.

Results are reported in terms of recall (R), precision (P), and F-measure (F1), computed on a time basis. An event discovered is first mapped to the corresponding reference event by finding the most overlapping event in the reference annotation. Given this mapping, recall is measured as the amount of time the discovery is correct divided by the total duration of the reference event. Precision is defined in a similar way. Recall and precision measures are averaged across files.

The output of the algorithm is a list of events discovered, ordered from the one with the best AV consistency according to the χ 2 test to the less. Results for the five best events discovered are reported in Table 1. For comparison purposes, results obtained without the χ 2 test (i.e., ranking of the events is solely based on the mutual information) are also reported (column "Baseline" in this table). Note however that, when not using the χ 2 test, we observed quite frequently candidate events for which SVM training could not converge. This is the case of partially discovered events, i.e., only a few occurrences have been detected, which lead to very few positive training samples selected in comparison with the negative ones. Results for such events are not included in the baseline performance which is therefore optimistic. From this table, one can see that the proposed method gives rather balanced recall and precision values while for the baseline, recall values are rather high whereas precision values are quite low. This reveals that each detected AV cluster pair from the "Baseline" experiments is not well matched to any annotated AV cluster, thus demonstrating the benefit of χ 2 filtering to select multiple events. Besides this evaluation, we investigated how well typical events of such shows are discovered. To this end, we selected typical audiovisual events in the Canal9 data set, for example close ups of a guest speaking (see middle image in Figure 2). For such events, we search in the first 10 events discovered for a match and evaluate the match using recall and precision. Results are reported in Table 2 for different types of typical events, namely: Guest views which are individual participants where the person shown is also speaking; Full-group views which are specified by a whole group that appear when only one participant is speaking; Multiple participants consist of two or more participants which appear in different camera angles when one participant is speaking; Credits are like jingles in news videos, which appear at the beginning and the end of each debate; Topic introduction appear at the beginning of each debate, which comprise a generated-computer screen with background music. The last column in this table shows the most frequent rank at which the event was found in the list of events discovered. It can be seen from this table that our method achieves very good results on credits and topic introduction which exhibit very limited variability. Full-group views are poorly detected, primarily due to the high variations between audio clusters, i.e., for events of this genre, while the whole group is shown participants speaking in turns, resulting in strong variations between the occurrences. Finally, the last row of Table 2 reports results for compound event types where a group of participants is shown while several persons are speaking simultaneously. In this case, very poor results are obtained as grouping speech from multiple speakers is a highly challenging task. This illustrates the limits of our method for such challenging events.

Finally, we focus on events of type guest views, i.e., showing a guest speaking. Such events are of most importance in debates and accounts for 2/3 of the events annotated in the reference. Given a list of 10 events discovered, we evaluate for each rank the guest view events discovered for the rank. Table 3 reports recall and precision for each rank, as well as the cumulated ratio of guest view events discovered up to that rank. More than 70 % of the 50 guest view events of the reference are found before rank 6, with a precision of 76 % and a recall of 80 %. Precision decreases quite moderately at each rank. These results demonstrate the benefit of unsupervised mining of multiple audiovisually consistent events for video structure analysis.

CONCLUSION

In this paper, we have presented a new framework that incorporates Pearson's χ 2 statistical test into a cluster selection method based on mutual information for the discovery of multiple audiovisual events in a video. Through experiments, we have shown that it is feasible to detect multiple events in a totally unsupervised way, without any prior knowledge on the events to be detected. We have demonstrated that the method can be used for video structure analysis. Future work includes the estimation of the number of events of interest and the use of more complex features for the discovery of events in different domains.

Fig. 2 :

 2 Fig. 2: Example of several typical structural events from the Canal9 data set. From left to right: a full group of participants, anchor person, and multiple participants.

Table 1 :

 1 Multiple structural event detection performances.

	order	R	"Baseline" P	F1	R	Our method P	F1
	1st	0.95	0.59	0.69	0.94	0.77	0.84
	2nd	0.94	0.63	0.73	0.87	0.75	0.78
	3rd	0.92	0.58	0.66	0.81	0.77	0.77
	4th	0.79	0.64	0.63	0.75	0.77	0.71
	5th	0.74	0.60	0.57	0.60	0.73	0.60

Table 2 :

 2 Average performances of the different genres of events for the first 10 events discovered.

	Event type		R	P	F1	Rank
	Guest view		0.70	0.76	0.66	1
	Multiple participants	0.53	0.71	0.53	8
	Full-group views	0.46	0.72	0.50	7
	Credits (jingles)	0.93	0.87	0.88	4
	Topic introduction	0.78	0.99	0.86	6
	Compound		0.64	0.16	0.21	7
	Rank	R	P	F1	ratio
	1st	0.94	0.77	0.84	34%
	2nd	0.90	0.77	0.81	48%
	3rd	0.87	0.77	0.80	56%
	4th	0.85	0.77	0.78	68%
	5th	0.80	0.76	0.75	74%
	6th	0.77	0.76	0.72	76%
	7th	0.74	0.76	0.70	76%
	8th	0.72	0.76	0.69	76%
	9th	0.70	0.76	0.66	80%

Table 3 :

 3 Performance for the detection of Guest views events in the first 10 events discovered.

This work was partly funded by OSEO, French State agency for innovation, in the framework of the Quaero research program.

Here, a partition is a segmentation with arbitrary labels attached to segments. The audio partition is the result of a speaker diarization algorithm while shot clustering is considered to obtain arbitrary labels for video shots.

For practical reasons, very short segments of less than 10 ms are not counted.