Introduction and Overview

Introduction

The past few years have seen considerable progress towards understanding theories of conformal matter coupled to 2D gravity. Although some insights were due to advances in continuum Liouville theory, stunning progress was made in understanding and solving discrete models of 2D gravity. Initially, the number of such models available was small. Due to recent interest in the subject, however, we now have a plethora of such models available. Some of these models are known to correspond to conformally coupled matter of central charges C ≤ 1, while the continuum limit of many others still remains to be understood. Classifying the possible critical behaviour of lattice models of 2D gravity is potentially an important pursuit. Because of their interpretation as toy models of bosonic string theory we might hope to eventually attack more physical string theories with higher central charges and built-in supersymmetry.

The perhaps simplest such theory is the one matrix model and its multicritical points discovered by Kazakov [1]. They were identified in [2], [3]as corresponding to the (2m-1, 2) minimal models coupled to gravity. Even though this identification is beyond any doubt correct, it is less clear why the lattice curvature dependent Boltzmann weights of these models conspire to give precisely these minimal models. In fact, we only understand this puzzle for the first three cases m = 1, 2 and m = 3 [2]. General (p, q) minimal models require several linearly coupled matrices [4]; actually two are sufficient [START_REF] Douglas | The two-matrix model[END_REF]. Again a better understanding of why the Boltzmann weights of these multimatrix models result in particular conformally coupled theories would be quite interesting.

An alternative way to introduce C ≤ 1 matter fields onto random lattices is the loop gas construction [6] [7]. An advantage over the multimatrix approach is that the construction is manifestly physical; i.e. it is clear (through the Coulomb gas mapping) why a specific critical behavior occurs. All (p, q) minimal models coupled to quantum gravity can be constructed in this way. So far a non-perturbative definition of all these models has not been given; it is however possible to derive diagrammatic rules signaling the existence of a "string field theory" [START_REF] Kostov | Strings with Discrete Target Space[END_REF].

The simplest statistical model allowing interpretation in terms of the loop gas is the O(n) model [START_REF] Nienhuis | Phase Transitions and Critical Phenomena[END_REF]. The O(n) on a fluctuating surface is equivalent to a special one-matrix model [6] and thus can be defined in a nonperturbative way. In this simplest model all loops (contractible and noncontractible) are taken with the same weight n. The partition function of the corresponding loop gas on a 3-coordinated fluctuating lattice reads F (λ, T, N ) = φ 3 graphs loops N 2-2H n #loops e -λv e -T (total length of loops)

(1. 1) where λ is the cosmological constant coupled to the volume v = # vertices of the lattice, T is the temperature of the loop gas and 1/N is the string interaction constant coupled to the Euler characteristics 2 -2H of the graph. The right hand side of (1.1) represents a triple series: It is asymptotic in 1/N 2 and of finite radius of convergence in the fugacities g 1 = e -λ and 1 2P 0 = e -λ-T corresponding to vertices empty and occupied by loops, respectively.

For N and n integers this series coincides with the perturbative expansion of the vacuum energy of a zero-dimensional N × N matrix field theory [6]

Z = DM n i=1 DΦ i exp{-N Tr[V (M ) + 1 2 n µ=1 Φ 2 µ - 1 2P 0 n µ=1 Φ 2 µ M ]} (1.2)
The corresponding Feynman diagrams can be interpreted in terms of surfaces populated by nonintersecting loops ( fig. 1) Then n gives the number of species of loops and the matrix potential V (M ) specifies the measure in the configuration space of the random surface.

With the choice

V (M ) = 1 2 M 2 + 1 3 g 1 M 3
the perturbative expansion of the matrix integral creates the cluster expansion of the O(n) model on a 3-coordinated lattice.

The integration over the matrix variables Φ µ , µ = 1, 2, ..., n can be performed immediatelly and the result is the following one-matrix integral [6]

Z = DM exp {-N Tr V (M ) + n 2 ∞ 0 d (Tr e M ) 2 } (1.
3)

The method of orthogonal polynomials used in the "ordinary" matrix models is not applicable here but the saddle point method in the limit N → ∞ works equally well.

Indeed, the action depends only on the eigenvalues P 1 , ..., P N of the random matrix M and the integral (1.3) equals, up to a constant factor, to

Z = N i=1 dP i e -N N i=1 V (P i ) + i =j log |P i -P j |-n 2 i,j log |2P 0 -P i -P j | (1.4)
This last integral is defined for any real value of n and it is known from the flat case that criticality occurs for -2 ≤ n ≤ 2. This is exactly the interval in which the saddle point solution exists [6]. In this paper we will restrict our study to the saddle point solution;

this is sufficient for classifying the possible critical regimes of the model. The stability if the saddle point solution and the nonperturbative effects due to instantons are considered in [START_REF] Eynard | [END_REF].

It is very useful to parametrize n in terms of the Coulomb gas coupling constant g as

n = -2 cos πg (1.5)
The model can be in a dense phase with 0 ≤ g ≤ 1 or, if g 1 in V (M ) is tuned appropriately, in a dilute phase with 1 ≤ g ≤ 2.

In both phases the central charge is given by C

= 1 -6( √ g -1 √ g ) 2 .
Which models may be described within the two phases? Let us agree that for our entire discussion in the present work p > q. Then in the dense phase g = q p and all minimal1 models may be obtained; while in the dilute phase g = p q and only models with p < 2q can be reached. In particular, the p = 2m -1,q = 2 models are not present for m ≥ 3. It is therefore natural to put them in by hand and investigate the loop gas in the presence of a general potential

V (M ) = m+1 k=2 1 k g k M k (1.6)
In order to analyze the possible critical behavior it is sufficient to study the theory on a disc, i.e. we will consider the loop function

W (P ) = 1 N Tr 1 P -M (1.7)
where the average is taken with respect to (1.2). For later use we remind the reader that the asymptotics of W (P ) for P → ∞ is given by

W (P ) = 1 P + W 1 P + W 2 P + . . . (1.8)

Overview, Conclusions and Open Problems

Our main result consists in establishing the phase diagram of fig. 2. In all phases the relation n = -2 cos πg remains valid; i.e. the phases may be thought of as an infinite number of branches in the complex n-plane (the branchpoints being at n = ±2). The Kazakov multicritical points are situated by construction at the center (i.e. n = 0) of each phase. For a given central charge between -∞ and 1 there are always two points; one lying in the dense and the other in a higher phase. These two models related by the duality g → 1 g are however not equivalent. This is particularly surprising for the minimal models: There is a dense realization at g = q p and a multicritical one at g = p q . We argue in section 2.2. that the difference is due to a different set of boundary operators.

From this point of view, then, the infamous (p, q) asymmetry of the matrix chain models arises because the chain models always favor one set of boundary operators over the other (with the exception of the Hermitian one matrix model with g = 1 2 ). Another sequence of particularly interesting points in the dense phase is generated by the "topological" series g = 1 p . We demonstrate that these models appear in our lattice approach as theories of "boundaries" (i.e. loops) without "worldsheet"2 . Our understanding is aided by the realization that the loop equation of the model may actually be exactly solved for rational values of g. The first member (g = 1 2 ) of this series is the model of topological gravity whose continuum limit is known [12]. The correct continuum limit of the higher members of the series remains to be found. In section 3. we further establish the above diagram by investigating the "perturbation" of the (2m -1, 2) models by the loop gas. Note that our approach smoothly interpolates between the physical construction in the dense and dilute phase and the higher Kazakov points. One may therefore hope to eventually obtain a better understanding of the latter. Let us note that flat multicritical O(n) models have recently attracted some attention in relation to a search for multicritical theories of polymers [START_REF] Saleur | Polymers and Percolation in Two Dimensions and Twisted N = 2 Supersymmetry[END_REF], [START_REF] Zamolodchikov | [END_REF]. Polymers are obtained by taking a n → 0 limit in the O(n) model. Dense and dilute polymers have been related to a, respectively, broken and unbroken twisted N = 2 supersymmetry [START_REF] Saleur | Polymers and Percolation in Two Dimensions and Twisted N = 2 Supersymmetry[END_REF], and it is natural to ask whether some insights into 2D gravity and noncritical string theory can be derived from this fact. A further very interesting problem is to find out what kind of multicritical polymer theories are obtained by taking an n → 0 limit in the Kazakov backgrounds. A comparison of critical exponents (see 3.3.) indicates that our multicritical polymers do not correspond to the ones considered in [START_REF] Saleur | Polymers and Percolation in Two Dimensions and Twisted N = 2 Supersymmetry[END_REF]. In section 4. the phase boundaries between the various regimes are studied. A discontinuity at these points is detected, resulting in two qualitatively different models at each integer g. The first boundary, g = 1, possesses C = 1, while the second boundary, g = 2, has C = -2.

We demonstrate that the model connected to the m = 3 phase possesses the Parisi-Sourlas "target space" supersymmetry. The dilute O(-2) model is different; only a n → -2 limit in the dilute phase yields again the Parisi-Sourlas model. The further boundaries at g = 3, 4, . . . all correspond to "topological" models. Their correct continuum description remains obscure for the moment.

The Dense Phase, Revisited

The Loop Equation and its Solution

The dense phase corresponds to setting all couplings {g k } in (1.6) to zero, except for g 0 = 1. All loops are then densely packed on the ϕ 3 random graphs. The loop equation reads

W 2 (P ) = C dP W (P ) 2πi(P -P ) [V (P ) -nW (2P 0 -P )] (2.1)
It may be derived from the matrix model (1.2)or by combinatorial methods [7]. After a symmetrization with respect to the reflection P → 2P 0 -P the contour integral can be performed using the Cauchy theorem and we arrive at the following functional equation ( for the gaussian potential V (P ) = 1 2 P 2 )

W (P ) 2 + W (2P 0 -P ) 2 + nW (P )W (2P 0 -P ) = P W (P ) + (2P 0 -P )W (2P 0 -P ) -2 (2.2)
The critical point is located to be at P * = 2(2 + n). If we transform P = P 0 + P and

W (P ) = 1 2 sin 2 πg [P + cos πg (2P 0 -P )] + W ( P ) (2.
2)simplifies to

W ( P ) 2 + W (-P ) 2 + n W ( P ) W (-P ) = 1 2 + n (P 2 0 -P 2 * ) + 1 2 -n P 2 (2.3)
In [START_REF] Kostov | Strings embedded in Dynkin diagrams[END_REF], [START_REF] Kostov | [END_REF] the equation was solved in the vicinity of P * . After introducing a cutoff ā we blow up the vicinity of P * by the following change of variables

P 0 -P * P * = ā2g Λ, P -P 0 P * -P L = āz, P 0 -P R P * -P L = āM (2.4)
Here Λ is the continuum cosmological constant, z the continuum boundary cosmological constant, and M is the boundary cosmological constant induced by the fluctuations of the worldsheet geometry.

One obtains for the singular part āg w(z) of W (P )

w(z) = - 1 2 A g [(z + z 2 -M 2 ) g + (z -z 2 -M 2 ) g ] = A g M g cosh(gτ ); z = M cosh(τ ) (2.5) with Λ = 2 (1 -g) 2 M 2g
(2.6)

A g = -2 √ 2 1 -g 1 sin πg (2.7)
The last relation follows if we compare (2.5) with the exact solution obtained for

P 0 = P * in [17] W = - 1 2 A g u 1-g + u g-1 u + u -1 P = 2(P * -P L ) u + u -1 P * -P L = 2(2 -β) 1 -g (2.8)
The inverse Laplace image of w(z) gives the amplitude w( ) for a disc with fixed length of its boundary

w(z) = ∞ 0 d e -z w( ); w(l) = 2 3/2 gM g (1 -g) 1 K g ( ) ∼ 2g √ π (1-g) M g-1/2 -3/2 e -M , if 1/M, -2 g+1/2 πg (1-g) sin πg M -g -g-1 , if 1/M, (2.9)
Now (2.5), (2.6) is quite puzzling for several reasons:

1. (2.6) says that quantum area does not scale like the square of quantum length in these models. An attempt at an explanation is made in section 2.2.

2. For the topological models g = 1 p we see that the string susceptibility is an integer:

γ s = 1 -1
g . This is surprising, since it means either that the exact lattice solution is analytic in the lattice cosmological constant P 0 around P * or that we have logarithmic scaling violations at these points. Below we will argue that the first possibility holds (in accordance with [18]).

3. A subtle but important point is that, for g < 1 2 , we have to approach the critical value of the boundary cosmological constant as P = P 0 + āz, not P = P * + āz. We do not have a deep explanation for this, but note that it constitutes annother instance of an "analytical redefinition" (discovered in [START_REF] Moore | [END_REF]) necessary to get sensible results from lattice gravity models.

It is interesting to realize that (2.2)may actually be exactly solved for rational g. This serves as a check for (2.5), (2.6)and will help in getting some insight into the second problem just mentioned. At the critical point P 0 = P * the solution to (2.3)has been known already for some time [17][7]. It may be parametrized using circular functions or rational functions(g = q p ):

W = - √ 2 1 -g 1 sin πg t 2p-q + t q t 2p + 1 P = 4 1 -g 1 + cos πg t p t 2p + 1 (2.10)
Here t is defined on (the double cover of) the Riemann sphere. It is apparent from (2.10)that the Riemann surface of W (P ) is algebraic. Furthermore, since the surface is uniformized by rational functions of t we see that it has genus zero. P is defined on a surface with p sheets. On the lowest (physical) sheet there is one cut from P L (branchpoint of order 2) to P R = P 0 (branchpoint of order p). The higher (unphysical) sheets possess also a cut from P 0 to 2P 0 -P L , except for the topmost, which again has just one cut. Now it is important to understand what happens if we move away from the critical point: The degeneracy at P = P 0 will be removed and all branchpoints will be of order 2. However, we still have a Riemann surface; it has a finite number of sheets and only square root singularities. By a standard theorem we therefore conclude that the solution of (2.3)is algebraic and thus given by W p + h p-1 ( P ) W p-1 + . . . + h 1 ( P ) W + h 0 ( P ) = 0 (2.11)

Here the h i ( P ) are polynomials in P , with P 0 dependent coefficients. These coefficients are determined by expanding (2.3), (2.11)around P = ∞ and matching the two expansions. It is easy to see that the genus of the Riemann surface will not change off the critical point; we therefore know the existence of a parametrization of (2.11)using rational functions of one parameter. Unfortunately we did not succeed in finding a simple such parametrization for arbirary g. Nevertheless we are now in a position to get some insight into the second problem mentioned above. Given the just presented algorithm for generating exact solutions to the loop equation we see that the singularities in the lattice cosmological constant P 0 are necessarily algebraic for rational g. Logarithmic scaling violations are thus impossible and we have analytic behavior in P 0 at the topological points g = 1 p .

Bulk and Boundary Operators

The loops in 2D quantum gravity may be considered as generating functions for the local operators of the theory [19]. Since the loops of the dense phase are clearly different from the ones in the standard lattice models it will be interesting to investigate their spectrum. Recall that Lian and Zuckerman have calculated the bulk spectrum in a version of continuum Liouville gravity. They found for the (p, q) minimal model coupled to gravity an infinite number of states with Liouville charges α given by (as always p > q)

α γ = p + q -k 2q k = 1, 2, . . . (2.12)
with the important restrictions k ≡ 0(mod q) and k ≡ 0(mod p) (γ is the charge of the identity operator, k = p -q). In [20], [21]it was shown that it is precisely these states which propagate around the torus. Now, in [START_REF] Kostov | Strings with Discrete Target Space[END_REF]it was found that the torus partition function for the dense minimal models coincides with the one found in [21], establishing that the dense models do have the expected bulk spectrum. As is well known, the standard matrix model realizations of the minimal models contains further operators. One way to see them is to look at the scaling dimensions obtained from expanding the macroscopic loops in the length . It is found that there are also operators with charges (2.12)but k divisible by p. They were identified by Martinec, Moore and Seiberg [22] as boundary operators. The first such operator, k = p, has α = γ 2 and is beautifully interpreted as the length (φ is the Liouville field)

= e γ 2 φ
(2.13) For the dense phase models, the spectrum of dimensions found in the loop expansions was worked out in [START_REF] Kostov | [END_REF]. It is easily seen that they correspond to operators with α γ as in (2.12)but with k divisible by p missing and k divisible by q appearing. The dense models are therefore different from the standard models because they possess a different set of boundary operators. This has dramatic effects, like the non-trivial Hausdorff dimension of the boundary. Indeed, here the first boundary operator has α = p q γ 2 and may be interpreted as the quantum length = e p q γ 2 φ

(2.14)

The Hausdorff dimension 2g = 2 q p may be directly read off from the last equation. Note that the choice of α in (2.14)corresponds to taking the "wrong" branch in the KPZ dressing of the identity on the boundary. It appears that the Seiberg rule for choosing these branches does not necessarily hold for boundary operators [START_REF] Seiberg | Notes on Quantum Liouville Theory and Quantum Gravity[END_REF] [22]. It should also be pointed out that the dense minimal models possess p-1 loops as opposed to the dilute minimal models, which have q -1 loops. In the KP description of the minimal models inspired by the matrix chains the dense phase is formally recovered by interchanging the operators P and Q (see [4], [START_REF] Douglas | The two-matrix model[END_REF], [START_REF] Francesco | [END_REF]). This remains however a formal excercise since it is not hard to see 3 that for the matrix chains the order of P is always larger than the order of Q (except for the hermitian one matrix model which is in the dense phase.). Our interpretation of dense models as being endowed with "standard worldsheets" but "nonstandard boundaries" is especially manifest in the example of the subsequent section.

2.3. g = 2 3 g = 2 3
is "pure gravity" (C = 0) in the dense phase. And indeed, for n = 1 in the maximally dense case (only g 0 = 1 = 0) we can integrate out the M matrix in (1.2)and obtain

Z = DΦ 1 exp {-N Tr[ 1 2 Φ 2 1 - 1 4P 2 0 Φ 4 1 ]} (2.15)
Of course the integration is this trivial only for the partition function and gets harder (although it may still be done) if the boundary is present: Remember the loop operator Being of third degree, it may be solved for W ( P ) to yield (∆ = P 2 0 -6)

is 1 N Tre LM , not 1 N Tre LΦ 1 .
W ( P ) = - 1 3 P 0 P 2 - 1 27 ∆ 3 2 + 1 √ 27 P 2(P 2 0 + 3) P 2 -P 4 - 1 3 ∆ 2 - 2 3 P 0 ∆ 3 2 1 3 - 1 3 P 0 P 2 - 1 27 ∆ 3 2 - 1 √ 27 P 2(P 2 0 + 3) P 2 -P 4 - 1 3 ∆ 2 - 2 3 P 0 ∆ 3 2 1 3
(2.17) 3 We acknowledge a discussion with M.R.Douglas on this matter. This model is the first nontrivial point in the "topological" series g = 1 p and has n = -1. Because of the minus signs one easily proves that all closed string diagrams are identically zero because of precise cancellations. The free energy is zero even before taking the scaling limit! Open string diagrams, however, survive (see fig. 3). Just as g = 1 2 , the model is rather a theory of loops than of surfaces. The solution (2.11)of (2.3)is

W 3 -(P 2 0 -2 + 1 3 P 2 ) W + 2 3
(1 + P 2 0 ) P -

2 27 P 3 = 0 (2.18)
The equation may be solved to give (∆ = P 2 0 -2) It is manifest that the solution is analytic at P 2 0 = P 2 * = 2.

W ( P ) = + 1 27 P 3 - 1

g = 1 4

In order to study the puzzling question of the singularity in the lattice cosmological constant we have analyzed yet annother topological point. The model is less trivial than g = 1 3 because here n = -√ 2 and we do not have precise cancellation of the worldsheetloops away from the scaling region. The exact solution for W ( P ) is (we introduced the

abbreviations σ ± = 1 ± 1 2 √ 2) W ( P ) = -σ + (P 2 0 -4σ -) + σ -P 2 - 1 2 √ 2σ -( P -B) ( P -PR )( P -PL ) (2.20)
which is, in accordance with (2.11)a solution to a bicubic equation for W . The positions of the cut are given through PR + PL = 4 √ 2σ + P 0 -2B and PR PL = 4σ 4 + (P 2 0 -4σ -) 2 1 B 2 . The auxiliary parameter B is determined by

B 4 - 8 3 √ 2σ + P 0 B 3 + 4 3 σ 2 + (P 2 0 -4σ -)B 2 - 4 3 σ 4 + (P 2 0 -4σ -) 2 = 0 (2.21)
It is seen 4 that any singular behavior in the cosmological constant P 0 would have to be generated from eq.(2.21). A (most conveniently numerical) study shows however that the branchpoints of the physical sheet of (2.21)are not located at the critical value P 2 * = 4σ - (i.e.P 0 ≈ 1.082) but are lying off the real axis at ±0.327±0.633i. This confirms the general discussion given in section 2.1. and agrees with the picture of [18]. Let us further note that, since there are no singularities on the real P 0 axis, the lattice model does not undergo any phase transition in the bulk cosmological constant, i.e. not even for some P 0 < P * .

The Multicritical Phases

Solution and Scaling of the Loop Equation

We will now turn on m -1 couplings {g k } in order to reach the m th multicritical phase. The loop equation is easily generalized to

W (P ) 2 + W (2P 0 -P ) 2 + nW (P )W (2P 0 -P ) = = V (P )W (P ) + V (2P 0 -P )W (2P 0 -P ) + m k=1 k j=1 g k+1 W j-1 [P k-j + (2P 0 -P ) k-j ] (3.1)
where V is the derivative of the potential (1.6). A new feature compared to the dense phase equation (2.2)is the appearance of the (as yet) unknown functions {W j } (see eq.(1.8))

which depend on all matter couplings {g k },P 0 . As for the dense phase the linear terms may be eliminated through the transformation P = P 0 + P , W (P ) = Here the {s 2i } are both explicitly and implicitly (through the functions {W j }) dependent on the matter couplings. In the m th critical phase the loop function should behave for P → 0 as W ( P ) ∼ P g with m -1 ≤ g ≤ m. The critical point is found to be fixed through the conditions 5

s 0 = s 2 = . . . = s 2(m-1) = 0 s 2m = 0 (3.3)
4 That is because the j-leg functions {W j } are simple rational functions in B, as (2.20)shows. E.g., W 1 is given by

P 0 + 1 B 2 [ 1 4 √ 2B 5 -(1 + 1 8 √ 2)P 0 B 4 -2σ + P 2 0 B 3 + (2σ 4 + (P 2 0 -4σ -)P 0 -( 25 2 + 35 4 √ 2)P 3 0 )B 2 - √ 2σ 4 + (P 2 0 -4σ -) 2 B -( 3 4 √ 2 + 1)σ 2 + (P 2 0 -4σ -) 2 P 0 ]
5 Note that we have m couplings at our disposal in order to fulfill the m conditions.

At that point eq.(3.2)may be explicitly solved; the solution with the correct asymptotics at P = ∞ reads

W ( P ) = - 1 2 sin πg 1 √ 2 -n g * m-1 P m - PL P + PL P 2 -1 m-g + - PL P - PL P 2 -1 m-g (3.4)
The position of the left branchpoint PL as well as the critical couplings {g * k } are determined from the asymptotics. We see that indeed W ( P ) ∼ P g . In view of this solution at the m-th multicritical point our arguments about the structure of the Riemann surface of W in section 2.1. may be repeated; we thus conclude that the exact solution for rational g = p q and arbitrary matter couplings is given by W q + h q-1 ( P )W q-1 + . . . + h 1 ( P ) W + h 0 ( P ) = 0 (3.5)

Again the h i ( P ) are polynomials in P whose degree increases with p; they (as well as the functions W j ) are determined by matching (3.5)and (3.2)at P = ∞. In order to infer the scaling limit of W ( P ) we however do not need this exact solution; instead we simply generalize the arguments of [START_REF] Kostov | Strings embedded in Dynkin diagrams[END_REF], [START_REF] Kostov | [END_REF]: upon scaling P = āz one concludes from (3.4)that W ( P ) ∼ āg w(z); thus the dominant piece in (3.2)is s 0 which has to vanish as ā2g . Parametrizing the proper approach to the critical point (3.3)by the continuum cosmological constant Λ one expects to find s 0 ∼ ā2g Λ g ; this will give as expected w(z) = -1

sin πg [(z + √ z 2 -Λ) g + (z - √ z 2 -Λ) g ].
The Hausdorff dimension takes on the "classical" value 2 for all multicritical phases.

Boltzmann Weights on Flat and Random lattices

The dense and dilute loop gas has been constructed as a direct adaptation of flat lattice models to the random case. It is therefore natural to ask whether we can go back from our formulation of the multicritical loop gas and deduce how a multicritical O(n) model might look like on flat honeycomb lattices. Generically we would expect to obtain such a model by introducing interactions between the loops [START_REF] Zamolodchikov | [END_REF], [START_REF] Saleur | Polymers and Percolation in Two Dimensions and Twisted N = 2 Supersymmetry[END_REF]. In the case of the first multicritical phase (m = 3) a concrete suggestion may be made, using the procedure of [2]. In this case the matrix model (1.2)generating the loop gas may be rewritten with the help of an additional matrix Ψ as

Z = DM DΨ n i=1 DΦ i × × exp{-N Tr[ 1 2 M 2 + g 1 3 M 3 + 1 2 Ψ 2 + i g 2 2 ΨM 2 + 1 2 n µ=1 Φ 2 µ - 1 2P 0 n µ=1 Φ 2 µ M]} (3.6)
which is seen to possess the graphical expansion exemplified in fig. 4. In addition to the loops we have dimers placed on the random "honeycomb" lattice. Their fugacity has to be chosen negative in order to perturb away from the m = 2 regime. Note that this formulation may be applied to flat lattices and, even though it does not constitute an exactly solvable model, could be checked by numerical analysis of the transfer matrix.

According to our phase diagram in fig. 2 we predict central charges between C = -2 and C = -7. For the higher phases it is less clear how to proceed. One guess would be to complement the dimers by increasingly longer strands (2-chains, 3-chains etc.) with alternating signs for their Boltzmann weights. An interesting question from the point of view of polymer theory is whether the multicritical matter induces in the continuum limit an effective interaction between the loops. An alternative possibility is that directly introducing such interactions results in yet another class of multicritical polymers.

Geometrical critical exponents for the O(n) vector model

The order parameters (the magnetic operators) in the O(n) model have a simple discription in terms of the loop gas. The m-th magnetic operator Ψ L is represented as the source of L nonintersecting lines meeting at a point. The correlation function of two such operators can be evaluated as the partition function F L of a network consisting of L nonintersecting lines tied at their extremities, moving in the sea of vacuum loops of the O(n) model [START_REF] Duplantier | [END_REF]. The dimension of the star operator Ψ L can be extracted from the dimension of the partition function F L . This last quantity can be calculated immediately.

First observe that the L nonintersecting lines cut the world sheet into k pieces with the topology of a disk. Let 1 , ..., L be the lengths of the L lines which form the watermelon network. As usual, we first sum over all configurations of the world sheet populated by vacuum loops keeping these lengths fixed. Then the partition function F L can be represented as an integral over 1 , ... L of the product of L loop amplitudes with lengths

F L = k i=1 d i e -2P 0 i w( 1 + 2 ) w( 2 + 3 )... w( L + 1 )
By the general scaling argument

F L ∼ Λ 2δ L -γ str
where δ L is the gravitational dimension of the operator Ψ L . On the other hand the loop amplitude behaves asymptotically as w( ) ∼ -1-g and therefore

F L ∼ M Lg = Λ Lg/(2ν)
It follows that

δ L = (Lg/(2ν) + γ str )/2 = Lg 4 -g-1 2 , if g > 1 L 4 -1-g 2g , if g < 1
The corresponding flat conformal dimensions are

∆ L = ∆ L/2,0 = g L 2 16 -(g-1) 2 4g , if g > 1 ∆ 0,L/2 = L 2 16g -(g-1) 2 4g , if g < 1 The smallest dimension ∆ 1 is positive only in the interval -1/2 ≤ g ≤ 2.
Outside this interval the propagator of the nonintersecting random walk grows with the distance between its two extremities. The fact that two points are connected with a line leads to an effective repulsion between them. Such a phenomenon is typical for nonunitary theories.

The Phase Boundaries

Exact Solution and Scaling of the Loop Equation at n = ±2

We will now investigate in some detail the loop gas with n = ±2 in the presence of multicritical matter. This will serve as an important check of our ideas. As we discussed before we expect to be able to tune to points with g = p integer, which form the crossover points from the p-phase to the (p + 1)-phase. Consider again the scaled loop function

w(z) = -1 sin πg [(z + z 2 -M 2 ) g + (z -z 2 -M 2 ) g ] (4.1)
Were it not for the "wavefunction renormalization" factor 1 sin πg we would get a trivial (i.e. purely analytic) result for w(z) for g ∈ N . Including this factor and subtracting terms analytic in z we instead obtain

w(z) = (-1) g-1 π [(z + z 2 -M 2 ) g -(z -z 2 -M 2 ) g ] log z + √ z 2 -M 2 M (4.2)
Upon Laplace-transforming this result, one obtains correctly w( ) = 1 M g K g (M ), as one expects from Liouville theory [START_REF] Moore | [END_REF]. We will now demonstrate how to derive this result from our lattice model. The algebraic approach clearly breaks down for integer g: the Riemann surface associated with W (P ) becomes ininitely foliated. Fortunately it is however possible to directly solve the saddlepoint equation of the O(n) model's matrix model formulation [26]. This equation for the eigenvalue density of the matrix model reads [17] b a dyρ(y)(

1 x -y + n 2 1 2P 0 -x -y ) = 1 2 V (x) = 1 2 m k=1 g k+1 x k (4.3)
where V (x) is the potential of the matrix model. It is convenient to change variables to

λ = 1 2 (P 0 -x), µ = 1 2 (P 0 -y), b 0 = 1 2 P 0 , ρ(x) → 1 2 ρ(λ ), g k → (-1 2 ) k-2 g k and rewrite (4.3)as b a ρ(µ ) 2µ λ 2 -µ 2 = 2 m k=1 g k+1 (λ -b 0 ) k (n = +2) b a ρ(µ ) 2λ λ 2 -µ 2 = 2 m k=1 g k+1 (λ -b 0 ) k (n = -2) (4.4) A further transformation λ = √ A + Bλ with A = 1 2 (a 2 + b 2 ) and B = 1 2 (a 2 -b 2 ) simplifies these equations to 1 -1 dµ ρ(µ) λ -µ = 2 m k=1 g k+1 ( √ A + Bλ -b 0 ) k (n = +2) 1 -1 dµ ρ(µ) √ A + Bµ 1 λ -µ = 2 m k=1 g k+1 √ A + Bλ ( √ A + Bλ -b 0 ) k (n = -2) (4.5)
These integral equations may now be immediately inverted [START_REF] Muskhelishvili | Singular Integral Equations[END_REF] to yield

ρ(λ) = - 2 π 2 1 -λ 2 1 -1 dµ 1 λ -µ 1 1 -µ 2 m k=1 g k+1 ( A + Bµ -b 0 ) k ρ(λ) = - 2 π 2 √ A + Bλ 1 -λ 2 1 -1 dµ 1 λ -µ 1 1 -µ 2 m k=1 g k+1 √ A + Bλ ( A + Bµ -b 0 ) k (4.6)
for n = +2 and n = -2, respectively. Since ρ(λ) has to be non-negative it is easy to prove the positivity condition The critical points are located by setting b = 0 [17]. At the g th multicritical point we expect the density to behave for λ → 0 like

1 -1 dµ 1 1 -µ 2 m k=1 g k+1 ( A + Bµ -b 0 ) k = 0 (n = +2) 1 -1 dµ 1 1 -µ 2 1 √ A + Bµ
ρ(λ ) ∼ λ g (4.9)
In order to locate these points we rewrite (4.6)for n = +2 as

ρ(λ) = 2 π 1 -λ 2 [ m-2 2 ] i=0 r 2i (A + Bλ) i - 2 π 2 1 -λ 2 [ m-1 2 ] l=0 t 2l+1 (A + Bλ) l 1 -1 dµ 1 λ -µ √ A + Bµ 1 -µ 2 (4.10)
and for n = -2 as

ρ(λ) = 2 π 1 -λ 2 [ m-3 2 ] i=0 r 2i+1 (A + Bλ) i+ 1 2 - 2 π 2 1 -λ 2 t 0 √ A + Bλ 1 -1 dµ 1 λ -µ 1 1 -µ 2 1 √ A + Bµ - 2 π 2 1 -λ 2 [ m-2 2 ] l=0 t 2l+2 (A + Bλ) l+ 1 2 1 -1 dµ 1 λ -µ √ A + Bµ 1 -µ 2 (4.11)
Here the {r 2i , t 2l+1 } and {r 2i+1 , t 2l } are known functions of the couplings {b 0 , g k } and the parameters A, B (but not of λ !) whose precise form we do not need at present. The remaining integrals in (4.10),(4.11)may be expressed in terms of complete elliptic integrals of the third kind. At the critical point b = 0 they become elementary. Transforming back to λ (4.10) may then be written

ρ(λ ) = 4 πa 2 a 2 -λ 2 [ m-2 2 ] i=0 r 2i λ 2i+1 - 4 π 2 [ m-1 2 ] l=0 t 2l+1 λ 2l+1 log λ a + √ a 2 -λ 2 (4.12)
In view of (4.9), the possible critical behavior for n = +2 is now transparent from (4.12).

We note that it is immediately obvious that we can reach only points with g odd, as

expected. There are two kinds of critical points:

1. m = g (we approach the g th point from below.) It is obtained through the conditions

r 0 = r 2 = . . . = r g-3 = 0 t 1 = t 3 = . . . = t g-2 = 0 t g = 0 (4.13)
There are g -1 couplings {g k } and g -1 constraints, so we indeed have a critical point.

2. m = g + 1 (we approach the g th point from above.) The conditions are

r 0 = r 2 = . . . = r g-3 = 0 r g-1 = 0 t 1 = t 3 = . . . = t g-2 = t g = 0 (4.14)
Here one has g couplings {g k } and g constraints; (4.14)defines again a critical point.

However, one may imagine relaxing the last condition to t g = 0 and still be consistent with the scaling law (4.9), see below.

An analogous analysis shows that for n = -2 the points with even g are generated.

At b = 0 (4.11) gives

ρ(λ ) = 4 πa 2 a 2 -λ 2 [ m-3 2 ] i=0 r 2i+1 λ 2i+2 - 4 π 2 [ m-2 2 ] l=0 t 2l+2 λ 2l+2 log λ a + √ a 2 -λ 2 (4.15)
The first integral in (4.11)is actually divergent for b → 0. This simply gives the condition t 0 = 0. Again one finds two distinct kinds of critical points:

1. m = g (we approach the g th point from below.) It is obtained through the conditions

r 1 = r 3 = . . . = r g-3 = 0 t 0 = t 2 = . . . = t g-2 = 0 t g = 0 (4.16)
2. m = g + 1 (we approach the g th point from above.) The conditions are

r 1 = r 3 = . . . = r g-3 = 0 r g-1 = 0 t 0 = t 2 = . . . = t g-2 = t g = 0 (4.17)
Here also one has as many constraints as couplings, but it is consistent to relax t g = 0 in 2..

Having found the critical points we will now scale the density in the vicinity of these points: Introduce a cutoff ā and define λ a = āζ in addition to the usual scaled separation of the cuts k = b a = āM . First concentrate on the points of type 2. Approaching them along a line in coupling constant space where the conditions (4.14), (4.17)remain satisfied we obtain from (4.10), (4.11)for the singular limit of ρ(λ

) ∼ āg ρ(ζ) ρ(ζ) = ζ g-1 ζ 2 -M 2 (4.18)
āg w(z) being defined as the singular part of W (P ) = W (P ) = -1 2 a b dµ ρ(µ ) P -µ (here P = 1 2 (P 0 -P ), P a = -āz) we derive from (4.18)

w(z) = (-1) g-1 z g-1 z 2 -M 2 log z + √ z 2 -M 2 M (4.19)
Some divergent contributions analytic in z, M were discarded in the course of the derivation; the general meaning of such terms was elucidated in [START_REF] Moore | [END_REF]. Eq.(4.19)is already almost (4.2). For g = 1, 2 they in fact exactly coincide. (Overall wavefunction normalizations are ignored.) For g ≥ 3 there are additional terms of the form where v is the total number of vertices and v 0 the number of vertices not occupied by either loops or dimers 10 . The dimers and loops are totally self-avoiding (see fig. 4). Now, a comparison of our loop gas Boltzmann weights with (4.27)immediately reveals the identity of the two models (the two lattice cosmological constants being related through g = 1 4b 0 ). It is interesting to note that the loops are generated by the "fermionic fields" Ψ, Ψ while the dimers are associated with the auxiliary field A. What we have shown here is that the latter degrees of freedom are absolutely necessary in order to preserve the supersymmetry: without them, the critical behavior is different.

z i M g-1-i √ z 2 -M 2 log . . . in (

g ≥ 3

We will only briefly comment on the type 2 critical point m = 4, a g = 3 model. The conditions that turn off the logarithmic terms are t 1 = 1 -2g 1 b 0 + 3g 2 b 2 0 -4g 3 b 3 0 = 0 and t 3 = g 2 -4g 3 b 0 = 0. The third parameter is r 0 = g 1 -3g 2 b 0 + 6g 3 b 2 0 + g 3 A but now we have to remember that r 0 = 0 upon approaching criticality gives (4.19)while we produce (4.2)by tending r 0 to zero appropriately. It is possible if somewhat tedious to prove ā2 Λ = 5 4 k 2 and therefore confirm (4.20).

We also carefully investigated g = 4; no new elements or surprises are found.

10 2. 4 . g = 1 3

 1043

1 2 sin 2

 12 πg [V (P ) + cos πg V (2P 0 -P )] + W ( P ): W ( P ) 2 + W (-P ) 2 + n W ( P ) W (-P ) =

g( 4 . 7 )

 47 k+1 ( A + Bµ -b 0 ) k = 0 (n = -2) Together with the normalization condition for the density b a dµ ρ(µ ) = 1, i.e. given two constraints determining the eigenvalue interval [a , b ] as a function of the couplings {b 0 , g k }. Equations (4.6),(4.7),(4.8) constitute the exact solution of the n = ±2 loop equation in the presence of general multicritical matter. We will now investigate the singular structure of the solution; specific examples are presented in the next section.

6 Λ-g 2 b 3 0 , t 2 = g 1 -3g 2 b 0 and r 1 = 2 0λ (a 2 -λ 2 )(λ 2 -b 2 ) ( 4 . 23 ) 9 S9

 63211222224239 4.2). In view of eqs.(4.10),(4.11)it is clear how to generate these terms. Approaching the critical point we have to tune the {g k } such that the {r 2i }, {r 2i+1 } vanish as the appropriate power of k . This constitutes, for g integer, the analog of the "analytic redefinitions" of[START_REF] Moore | [END_REF]in the half-integer case. Only along special trajectories in coupling constant space do we satisfy the Wheeler-de-Witt constraint.It remains to analyze the relation between the cosmological constant Λ and the scaling parameter M . This is done by investigating the conditions (4.7), (4.8). The result is logarithmic term. The positivity condition gives 2a E(k ) = πb 0 while the normalization condition turns out to be identical to(4.22). One thus locates the critical point to be at b 2 0 = 24 π 2 and finds ā2 Λ = 5 2 k 2 log 4 k . Therefore the Boltzmann weights are positive (a necessary consistency check since we are approaching this point from the dilute phase); however, there exists a logarithmic scaling violation Λ = M 2 log 1 āM . m = 3 corresponds to the left boundary of the first higher multicritical phase (the Yang-Lee phase). One hast 0 = -b 0 + g 1 b 2 0 Bg 2 . Imposing t 0 = t 2 = 0 it follows ρ(λ) = 1 πb Positivity gives A = b 2 0 and normalization B = 2b 0 . Thus k = b 0 -2 b 0 + 2 (4.24)and it is obvious (b * = 2) that Λ = M 2 . The couplings are g 1 = 3 2b 0 , g 2 = into positive weights for the ϕ 3 vertices and negative weights for the ϕ 4 vertices, as it must be in the Yang-Lee phase. Surprisingly, the model is exactly identical to the "D = -2" theory solved several years ago[START_REF] Boulatov | [END_REF]. It possesses a Parisi-Sourlas supersymmetry and is most elegantly described by a zero dimensional supersymmetric matrix model. The supermatrix is Σ = M + θΨ + Ψ + θ + θθA where θ, θ are Grassmann variables, Ψ,Ψ + are Grassmann valued hermitian matrices and A is the auxiliary hermitian matrix. The action is = N Tr dθd θGrassmann integrals and integrating out the auxiliary field one obtainsS = N Tr[ 1 2 (M -gM 2 ) 2 -Ψ + Ψ(1 -2gM )](4.26)By looking at the diagrams the action S is generating one finds the graphical expansion {ϕ 3 graphs} g v {dimers + loops} 3 v 0 (-1) #(dimers) (-2) #(loops) (4.27) One may equally well use a Gaussian propagator.

Fig. 1 .Fig. 2 .

 12 Fig. 1. A configuration of nonintersecting loops Fig. 2. The multicritical phase diagram of the loop gas coupled to 2D gravity. C is the central charge, g is the Coulomb gas coupling and n the weight of the loops.

Fig. 3 .

 3 Fig. 3. An example for a diagram of the topological model (1, 3).

Fig. 4 .

 4 Fig. 4. A typical diagram in the m = 3 multicritical phase.

  It shows, however, that the bulk consists of ordinary ϕ 4 lattice gravity while the boundary is different.

	The exact solution (2.11)to the loop equation (2.3)reads
	W 3 -(	1 3	(P 2 0 -6) + P 2 ) W -	2 27	(P 2 0 -6)	3 2 +	2 3	P 0	P 2 = 0	(2.16)

Note that the O(n) model is not minimal at generic values of n, even if the associated central charge is in the BPZ list. Special weights have to be assigned to noncontractible loops, as soon as the genus exceeds zero or operator insertions are present (see[7]). In particular eq.(1.2)may not be used to give a nonperturbative definition for the minimal models.

This way of looking at topological theories was first clearly stated in[START_REF] Kostov | Strings with Discrete Target Space[END_REF],[START_REF] Moore | [END_REF].

+

, 2 +

, ..., L + 1

We have not carried out a detailed proof except for g = 1, 2, 3, 4 (see examples) but strongly suspect the validity of our claim for all g.

Acknowledgements

We would like to thank M.Douglas, E.Martinec, G.Moore, H.Saleur, N.Seiberg and S.Zamolodchikov for discussions. This work was supported in part by DOE grant DE-FG05-90ER40559. 10 Because of the zero mode of the discrete Laplacian (4.27)is of course identically zero for closed string diagrams. Inserting a loop operator 1 N Tre LM fixes the zero mode and yields a nontrivial result.

The critical points of type 1 are essentially different from the type 2 just discussed. They exhibit logarithmic behavior in the eigenvalue density; it is easily seen that upon scaling we do not obtain (4.2)and (4.20)does not hold.

The general theory of this section will now be applied to the lowest (and most interesting) values of g.

g = 1

This is the loop gas model at C = 1. m = 1 is the right boundary of the dense phase discussed in section 2; t 1 = 1. The critical coupling is b * = 2. If we introduce the cosmological constant as b 2 0 = 2 + 32ā 2 Λ the relation to the scaling parameter is Λ = (M log āM ) 2 . The density, however, contains a logarithmic piece, as explained above.

On the other hand, m = 2 constitutes the left boundary of the dilute phase. The parameters in this case read t 1 = 1 -2g 1 b 0 and r 0 = g 1 B. Imposing the condition (4.14), i.e. g 1 = 1 2b 0 , the logarithmic piece in the density is killed and one obtains

Working out the positivity condition (4.7)gives A = b 2 0 , while the normalization constraint yields 8 Note that for g 1 = 0 we are in the dense phase (m = 1). The "critical limit" thus corresponds to b 0 → 0, meaning infinite Boltzmann weights for loops. In other words, it does not correspond to a critical theory at all; the lattice version of "C = -∞".


Ngoc-Quang Luong

Laurent Besacier

Benjamin Lecouteux

Find The Errors, Get The Better: Enhancing Machine Translation via Word Confidence Estimation

This article presents two novel ideas of improving the Machine Translation (MT) quality by applying the word-level quality prediction for the second pass of decoding. In this manner, the word scores estimated by Word Confidence Estimation (WCE) systems help to reconsider the MT hypotheses for selecting a better candidate rather than accepting the current sub-optimal one. In the first attempt, the selection scope is limited to the MT N-best list, in which our proposed re-ranking features are combined with those of the decoder for re-scoring. Then, the search space is enlarged over the entire search graph, storing many more hypotheses generated during the first pass of decoding. Over all paths containing words of the N-best list, we propose an algorithm to strengthen or weaken them depending on the estimated word quality. In both methods, the highest-score candidate after the search becomes the official translation. The results obtained show that both approaches advance the MT quality over the one-pass baseline, and the Search Graph Re-decoding achieves more gains (in BLEU score) than N-best List Re-ranking method.

• The MT N -best list: after decoding, besides the official translation e 1 , the decoder generates also N -1 other alternative hypotheses {e 2 , e 3 , ..., e N } with lower scores. The totality of these N hypotheses is known as the N -best list.

Working on this list, we integrate into the current objective scoring function with our proposed parameters based on WCE scores, then re-rank it by this enriched function. • The MT Search Graph (SG) can be considered as a "vast warehouse" storing all possible hypotheses generated by the SMT decoder. Our idea when exploring this huge space is that the overall scores of all paths containing tagged (error/ no error) words will be modified due to their quality predicted beforehand by WCE. More precisely, the score is strengthened (increased) in case of the path contains good words and weakened (decreased) otherwise.

Word Confidence Estimation (WCE) is not a novel topic, although it is still understudied compared to research on Sentence-level Quality Estimation. Nevertheless, the idea of using it to enhance MT quality has not been widely investigated in literature. To the best of our knowledge, if we ignore our previously published conference papers, the confidence score (called Goodness) is applied only once in the work of Nguyen, Huang and Al-Onaizan (2011) to re-rank the N -best list, in a different way from our approach. The rest of this article is organized as follows. After reviewing some related work in Section 2, we investigate the correlation between our proposed scores (built using WCE) and other MT quality metrics (BLEU, TER, TERp-A) in Section 3. Section

Introduction

The core idea of Statistical Machine Translation (SMT) is to generate all possible hypotheses for a given input sentence, then search for the hypothesis of highest score to become the output. The score used to judge the candidates consists of various factors, e.g. language model, translation model, reordering model, etc. Since the state-of-the-art MT models are imperfect, their outputs might not meet the user's expectations. More specifically, the MT output perhaps beats the others under the decoder's assessment, yet in many cases remains sub-optimal according to readers' viewpoint. For instance, by looking at the N-best list presented in Table 1, it is not hard to realize that the third ranked hypothesis is more valuable than the current 1-best, with only one "Shift" operation ("association udf " → "udf association") is required to become the reference (post-edition), although its model score is lower. Therefore, improving MT performance by adding more objective and decoder-independent features is a roadmap that many researchers are attempting.

Source (fr)

l'association udf hausse le ton et somme le nouveau centre de ne plus utiliser son sigle. Post-edition (en) the udf association increases the tone and commands the new centre to stop using its acronym. Hypothesis e 1 the association udf increase the tone and after the new centre to stop using its acronym. Hypothesis e 2 the association udf rise the tone and warn the new centre to stop using the acronym. Hypothesis e 3 the association udf increases the tone and commands the new centre to stop using its acronym. Hypothesis e 4 the association udf tone and increase the amount the new centre to use its acronym. Hypothesis e 5 the association udf increase the tone and warn the new centre not to use its abbreviation.

Table 1. With state-of-the-art SMT systems, the 1-best is not always optimal Joining these endeavors, this article contributes two novel ideas for generating a better candidate from the quality labels predicted for words of the current MT output. More specifically, we automatically identify the good and bad words (word confidence estimation), then exploit them as additional indicators to "decode" one more time for acquiring more valuable translation. There are two spaces over which the search can be conducted:

4 presents the WCE system building. Sections 5 details the idea of using WCE to re-rank the N -best list. Another way of exploiting it to re-decode the SMT search graph is discussed in Section 6. Section 7 compares the two methods, concludes the article and points some perspectives.

2 Related Work

Word Confidence Estimation

Confidence Estimation (CE) is the task of identifying the correct parts and detecting the translation errors in MT output. If the quality is predicted for each word, this becomes WCE. The interesting uses of WCE include: pointing out the words that need to be corrected by the post-editor, telling readers about the reliability of a specific portion, and selecting the best segments among options from multiple translation systems for combination.

To deal with this problem, various approaches have been proposed. They mainly focus on two principal issues: the features to represent each word and the Machine Learning (ML) methods to train the classifier. In this domain's pioneer work, [START_REF] Blatz | Confidence Estimation for Machine Translation[END_REF] combine several features using neural network and Naïve Bayes learning algorithms. One of the most effective feature combinations is the Word Posterior Probability (WPP) as suggested by [START_REF] Ueffing | Confidence Measures for Statistical Machine Translation[END_REF] associated with IBM-model based features [START_REF] Blatz | Confidence Estimation for Machine Translation[END_REF]). Basically, WPP is the likelihood of the word occurring in the target sentence, given the source sentence. Numerous knowledge sources have been proposed to calculate it, such as word graphs, N-best lists, etc. To quantify it, the key point is to determine sentences in N-best lists that contain the word e under consideration in a fixed position i. [START_REF] Ueffing | Word-level Confidence Estimation for Machine Translation Using Phrased-based Translation Models[END_REF] propose an approach for phrase-based translation models: a phrase is a sequence of contiguous words and is extracted from the word-aligned bilingual training corpus. The confidence value of each word is then computed by summing over all phrase pairs in which the target part contains this word. Xiong, Zhang and Li (2010) incorporate linguistic features (the word itself, part-of-speech (POS) and null-link feature) with WPP and train their Maximum Entropy classifier, allowing considerable gains in comparison to the one using only WPP features. The novel features from source side, alignment context, and dependency structure [START_REF] Nguyen | Goodness: A Method for Measuring Machine Translation Confidence[END_REF] advance the error prediction accuracy of the baseline system using WPP and POS features in both F-score and Pearson correlation with human judgment. Other approaches are based on external features, which are independent from MT system's resources [START_REF] Soricut | Trustrank: Inducing Trust in Automatic Translations via Ranking[END_REF], Felice and Specia (2012)), allowing to cope with various MT systems, such as statistical, rule-based, etc.

Recent workshops on MT (WMT 2013(WMT , 2014(WMT and 2015) ) launched WCE as an evaluation shared task. In WMT 2013, while [START_REF] Han | Quality estimation for machine translation using the joint method of evaluation criteria and statistical modeling[END_REF]; Luong, Lecouteux and Besacier (2013) employ the Conditional Random Fields (CRF) model [START_REF] Lafferty | Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data[END_REF]) to build classifiers, [START_REF] Bicici | Referential translation machines for quality estimation[END_REF] presents the global learning model by dynamic training with adaptive weight updates in the perceptron training algorithm. Concerning features: [START_REF] Bicici | Referential translation machines for quality estimation[END_REF] presents the "common cover links" (the links that point from the leaf node containing this word to other leaf nodes in the same subtree of the syntactic tree). [START_REF] Han | Quality estimation for machine translation using the joint method of evaluation criteria and statistical modeling[END_REF] focus on various n-gram combinations of target words. (Luong et al. 2013) integrated a number of new indicators relying on graph topology, pseudo reference, syntactic behavior (constituent label, distance to the semantic tree root) and polysemy characteristic.

In WMT 2014, Wisniewski, Pécheux, Allauzen andYvon (2014) exploit random forest classifier and build only 16 dense and continuous features of two categories: association features between source sentence and each target word, and fluency features describing the quality of the translation hypotheses. Meanwhile, confusion network, word lexicon and POS tags are the main resources to form the feature set of the systems of Camargo-de-Souza, [START_REF] Camargo-De-Souza | Fbk-upv-uedin participation in the wmt14 quality estimation shared-task[END_REF].

In WMT 2015, deep neural network is employed by [START_REF] Kreutzer | QUality Estimation from ScraTCH (QUETCH): Deep Learning for Word-level Translation Quality Estimation[END_REF] to learn continuous feature representations from bilingual contexts. Their network is firstly trained by initializing the word lookup-table with distributed word representation, and then adapted to the WCE task via a backpropagation process, which aims to minimize the word prediction errors using stochastic gradient descent. Meanwhile, the conventional sequence labeling technique, CRF, is applied by many other participants [START_REF] Shah | SHEF-NN: Translation Quality Estimation with Neural Networks[END_REF], [START_REF] Logacheva | Data enhancement and selection strategies for the word-level Quality Estimation[END_REF], [START_REF] Shang | Strategy-Based Technology for Estimating MT Quality[END_REF]) to train their classifiers. Beside using baseline features, [START_REF] Tezcan | UGENT-LT3 SCATE System for Machine Translation Quality Estimation[END_REF] propose new ones to capture the accuracy (meaning transfer from source to target sentence) using word and phrase alignments, and the fluency (target sentence wellformedness level) via training language models on word surface forms and on part-of-speech tags.

As stated above, the main goal of this article is to apply WCE outputs in the second pass of decoding (i.e. for re-ranking the SMT N -best list, as well as redecoding the Search Graph). Therefore, it is interesting to investigate how SMT multiple-pass decoding was examined in the literature in the next section.

SMT Multiple-Pass Decoding

Among related work concerning this issue, we observe some prominent ideas. The first direction focuses on proposing additional Language Models. [START_REF] Kirchhoff | Improved language modeling for statistical machine translation[END_REF] train one word-based 4-gram model (with modified Kneser-Ney smoothing) and one factored trigram model, then combine them with seven decoder scores for re-ranking N -best lists of several SMT systems. Their proposed LMs increase the translation quality of the baselines (measured by BLEU score) from 21.6 to 22.0 (Finnish -English), or from 30.5 to 31.0 (Spanish -English). Meanwhile, Zhang, Almut, and Stephan (2006) experiment with a distributed LM where each server, among the total of 150, hosts a portion of the data and responses its client, allowing them to exploit an extremely large corpus (2.7 billion word English Gi-gaword) for estimating N-gram probability. The quality of their Chinese -English hypotheses after the re-scoring process by using this LM is improved by 4.8% (from BLEU 31.44 to 32.64,oracle BLEU score = 37.48).

In another direction, several authors propose to replace the current decoder's linear scoring function by more efficient functions. [START_REF] Ueffing | Word-level confidence estimation for machine translation[END_REF] linearly combine sentence-level WPP with scores assigned by the underlying SMT system and additional language model scores . Sokolov, Wisniewski and Yvon (2012) learn their non-linear scoring function in a learning-to-rank paradigm, applying Boosting algorithm. Their gains on the WMT'{10, 11, 12} are modest yet consistent and higher than those based on linear scoring functions. [START_REF] Duh | Beyond log-linear models: Boosted minimum error rate training for n-best re-ranking[END_REF] use Minimum Error Rate Training (MERT) [START_REF] Och | Minimum error rate training in statistical machine translation[END_REF]) as a weak learner and build their own solution, BoostedMERT, a highly-expressive re-ranker created by voting among multiple MERT ones. Their proposed model considerably beats the decoder's log-linear model (43.7 vs. 42.0 BLEU) in IWSLT 2007 Arabic -English task. Aiming at lattice rescoring methods for large-scale SMT, [START_REF] Blackwood | Lattice Rescoring Methods for Statistical Machine Translation[END_REF] proposes a linearized lattice minimum Bayes-risk decoding method based on efficient path counting transducers. He also suggests to combine multiple SMT lattices, allowing the decoder to operate on a much richer and more diverse searching space, thus improves the translation quality over several language pairs. Applying solely goodness (the sentence confidence) scores, [START_REF] Nguyen | Goodness: A Method for Measuring Machine Translation Confidence[END_REF] obtain slight yet consistent TER reductions (0.007 and 0.006 on the dev and test set) after a 5-list re-ranking for their SMT hypotheses. This latter work is the most related to our paper, yet discrepant in some points: (1) our proposed sentence scores are computed based on word confidence labels; (2) we perform a study of the use of WCE for Nbest reranking and assess its usefulness in a simulated interactive scenario (using oracle WCE labels); and (3) we also use, in the second part of this paper, the WCE score to re-decode the full SMT search graph.

3 Word Quality Scores and MT Quality Metrics Before exploiting WCE scores to improve MT quality, we first investigate the correlation between sentence-level scores (obtained from WCE labels) and conventional evaluation scores, including BLEU [START_REF] Papineni | Bleu: a method for automatic evaluation of machine translation[END_REF]), TER and TERp-A [START_REF] Snover | Terp system description[END_REF]). For each output sentence, a word quality score (WQS) is defined by the ratio of the number of words predicted as "Good" by WCE system over its total number of words:

W QS = # G (good) words #words (1)
In other words, we are trying to examine whether the high percentage of "G" (good) words (predicted by WCE system) in a MT output ensure its possibility of having a better BLEU and low TER (TERp-A) value. This investigation is a strong prerequisite for further experiments in order to verify that WCE scores do not bring additional "noise" to the candidates' re-judgement process. In this investigation, we compute WQS over a French -English dataset (encompassing total of 10,881 1-best translations), taken from news corpora of the WMT evaluation campaign (from 2006 to 2010). The post-editions of these translations are generated by using a crowdsourcing platform: Amazon Mechanical Turk. Matching MT hypotheses against post-editions using TERp-A1 , a tuned version of TERp2 , enables us not only to compute TER and TERp-A scores, but also to determine the word quality labels ("G", "B"), and then WQS. More details of the corpus can be found in [START_REF] Potet | Collection of a Large Database of French-English SMT Output Corrections[END_REF]) and those of the quality label determination with TERp-A are depicted in [START_REF] Luong | Integrating Lexical, Syntactic and System-based Features to Improve Word Confidence Estimation in SMT[END_REF]. Once TERp-A labels are obtained, we convert them into binary labels "G", "B" (see Section 4.2 for conversion details).

Once we have three conventional scores (BLEU, TER, TERp-A) for each sentence, we plot each against WQS. Here, we use the "oracle" labels in order to verify the correlation with conventional evaluation metrics, but obviously, the predicted labels will be used for the two-pass SMT described in the next section. BLEU, TER and TERp-A scores are calculated after matching with post-editions. The results are plotted in Figure 1, where the y axis shows the "G" (good) word percentage, and the x axis shows BLEU (1a), TER (1b) or TERp-A (1c) scores. It can be seen from Figure 1 that the majority of points (the densest areas) in all three cases conform the common tendency. In Figure 1a, the higher "G" percentage, the higher BLEU score is. Conversely, in Figure 1b (Figure 1c), the higher "G" percentage, the lower TER (TERp-A) is. Furthermore, these high correlations are quantified by the high positive (0.7814 for BLEU) and negative (-0.8687 for TER, and -0.7968 for TERp-A) correlation scores. We notice some outliers, i.e. sentences with most or almost all words labeled "good", yet still have low BLEU or high TER (TERp-A) scores. This phenomenon is to be expected when many unknown source words are not translated or when the unique reference is simply too far from the hypothesis. Nevertheless, the information extracted from oracle WCE labels seems useful to assess the MT hypotheses in the second pass.

4 Experimental Setting

Dataset, N-best List and Search Graph Preparation

From a dataset of 10,881 French sentences, we applied a Moses-based SMT system to generate their English hypotheses. In our SMT system, the translation model is trained on the Europarl and News parallel corpora of WMT103 (1,638,440 sentences), and the target language model is trained by the SRILM toolkit [START_REF] Stolcke | Srilm -an Extensible Language Modeling Toolkit[END_REF]) on a news monolingual corpus of WMT10 (48,653,884 sentences). Next, human translators were invited to correct MT outputs, giving us the post editions. More details on this post-edited corpus can be found in [START_REF] Potet | Collection of a Large Database of French-English SMT Output Corrections[END_REF]. The set of triples (source, hypothesis, post edition) was then divided into the training set (10000 first triples) and test set (881 remaining ones). The WCE classifier was trained over all 1-best hypotheses of the training set.

The N -best list (N = 1000) with associated alignment information is also obtained on the test set (1000 * 881 = 881000 sentences) by using options "-n-bestlist" and "-print-alignment-info-in-n-best" of Moses (version 2009-04-13) [START_REF] Koehn | Moses: Open source toolkit for statistical machine translation[END_REF]). Besides, the SGs are extracted by some parameter settings: "-output-search-graph", "-search-algorithm 1" (using cube pruning) and "-cube-pruning-pop-limit 5000" (adds 5000 hypotheses to each stack). We then store the SG for each source sentence in a separated file, and the average size is 43.8 MB.

WCE System Building

We employ the Conditional Random Fields [START_REF] Lafferty | Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data[END_REF]) (CRFs) as our machine learning method, with WAPITI toolkit4 (Lavergne, Cappé and Yvon (2010)), to train the WCE model. A number of knowledge resources are employed for extracting the system-based, lexical, syntactic and semantic characteristics of a word. This results in the total of 25 major feature types as follows:

• Target Side: target word; bigram (trigram) backward sequences; number of occurrences • Source Side: source word(s) aligned to the target word • Alignment Context [START_REF] Nguyen | Goodness: A Method for Measuring Machine Translation Confidence[END_REF]: the combinations of the target (source) word and all aligned source (target) words in the window ±2 • Word posterior probability [START_REF] Ueffing | Confidence Measures for Statistical Machine Translation[END_REF] • Pseudo-reference (Google Translate): does the word appear in the pseudo reference? • Graph topology (Luong, Besacier and Lecouteux (2013)): number of alternative paths in the confusion set, maximum and minimum values of posterior probability distribution • Language model (LM) based: length of the longest sequence of the current word and its previous ones in the target (resp. source) LM. For example, with the target word w i : if the sequence w i-2 w i-1 w i appears in the target LM but the sequence w i-3 w i-2 w i-1 w i does not, the n-gram value for w i will be 3. In the next step, the word's reference labels (or so-called oracle labels) are initially set by using TERp-A toolkit [START_REF] Snover | Terp system description[END_REF] in one of the following classes: "I" (insertions), "S" (substitutions), "T" (stem matches), "Y" (synonym matches), "P" (phrasal substitutions), "E" (exact matches). "E", "T" and "Y" are then regrouped into "good" class "G", meanwhile the rest ("I", "P" and "S") belongs to "bad" class "B". We observe that 85% of the words in our dataset are labeled as "G" and 15% are labeled as "B". Once having the prediction model, we apply it on the test set (881 x 1000 best = 881000 sentences) and get needed WCE labels along with confidence probabilities. In terms of F-score, our WCE system gets performance in predicting "G" label of 87.65%, and"B" label of 42.29%. The above-mentioned feature types were also used in our English -Spanish WCE System submitted for WMT Quality Estimation shared task and achieved a high rank (first rank in 2013 (Luong et al. 2013) and third rank in 2014 [START_REF] Luong | LIG System for Word level WE Task at WMT14[END_REF]). Both WCE and oracle labels will be used in the experiments.

WCE in N-best List Re-ranking

As stated above, the main goal of this idea is to add WCE-based scores along with existing decoder ones (LM, Translation model, Reordering model, etc.) in order to re-select the best hypothesis among N candidates. We start by describing our proposed features, followed by experiments and further analysis.

Proposed Features

Since the scores resulting from the WCE system are for words, we have to synthesize them in sentence level scores for integrating with the 14 (already existing) Moses decoder scores. Six new scores are proposed; they include:

• The ratio of number of good words to total number of words (1 score) • The ratio of number of good nouns (verbs) to total number of nouns (verbs)

(2 scores) • The ratio of number of n consecutive good word sequences to the total number of consecutive word sequences; n=2, n=3 and n=4 (3 scores) Let us give an example in Figure 2: among the total of 18 words of a given SMT hypothesis, we have 12 labeled as "G"; 7 out of 17 word pairs (bigram) are labeled as "GG" and 3 out of 16 triples are labeled as "GGG". In this case, some of the above scores can be computed as: With the features built on oracle labels, we are able to analyze the upper bound performance. In other words, we can establish an "oracle" setting which is comparable to an interactive case where users would validate a word as "G" or "B" without providing any confidence score.

Experiments

To better examine the impact of the proposed scores, we calculate them not only using our predicted WCE system, but also using an oracle WCE (further called "WCE scores" and "oracle scores", respectively). We experiment with the three following systems:

• BL: Baseline SMT system with 14 above decoder scores • BL+WCE: Baseline + 6 predicted WCE scores • BL+OR: Baseline + 6 oracle WCE scores (simulating an interactive scenario).

The weights assigned to these scores are tuned by a 2-fold cross validation on the test set, using MERT [START_REF] Och | Minimum error rate training in statistical machine translation[END_REF] and MIRA [START_REF] Watanabe | Online large-margin training[END_REF]) methods. More specifically, we split the test set into two equivalent parts: S1 and S2, then take S1 as a development set to optimize the parameters 2012)) for instance). In such an environment, once having the hypothesis produced by the first pass (translation task), the human editor could simply click on words considered as bad (B), the other words being implicitly considered as correct (G).

For more insightful understanding about WCE scores' role, we calculate the possible optimal BLEU score obtained from the N -best list. Applying the sentence-level BLEU+1 metric [START_REF] Nakov | Optimizing for sentence-level bleu+1 yields short translations[END_REF]) over candidates in the list, we select the one with highest score and aggregate all of them in an oracle-best translation; the resulting performance obtained is 60.48. This score shows that the simulated interactive scenario (BL+OR) is less than optimal only 2.38 points (in case of MERT) and clearly overpasses the baseline (8.17 points below the best score).

The contribution of a real (predicted) WCE system seems more modest: BL+WCE marginally increases BLEU scores of BL (0.46 gain in case of optimizing by MERT and 0.32 by MIRA). For both TER and TERp-A metric, the improvements are also negligible. To verify the significance of this result, we estimate the p-value between BLEU of BL+WCE system and BLEU of baseline BL relying on Approximate Randomization (AR) method [START_REF] Clark | Better hypothesis testing for statistical machine translation: Controlling for optimizer instability[END_REF]) which indicates if the improvement yielded by the optimized system is likely to be generated again by some random processes (randomized optimizers). After various optimizer runs, we randomly selected 5 optimizer outputs to perform the AR test and obtain a p-value of 0.01. This result reveals that the improvement yielded by BL+WCE is significant although small, originated from the contribution of WCE score, not by any optimizer variance. This modest but positive change in BLEU score using WCE features encourages us to investigate and analyze further about WCE scores' impact by illustrating the gradual improvement of WCE performance, which we now explain. Firstly, we filter out all wrongly classified words in the test set (by matching against the oracle labels) and push them into a temporary set, called T. Then, we correct randomly a percentage (25%, 50%, or 75%) of labels in T. Finally, the altered T will be integrated back with the correctly predicted part (by the WCE system) in order to form a new "simulated" result set. This strategy results in three "virtual" WCE systems called "WCE+N%" (N=25, 50 or 75), which use 14 decoder scores (including 7 reordering, 1 language model, 5 translation model and 1 word penalty scores) and 6 "simulated" WCE scores. From each of the above systems, the whole experimental setting is identical to what we did with the original WCE and oracle systems: six scores are built and combined with existing 14 system scores for each hypothesis in the N -best list. After that, MERT and MIRA methods are invoked to optimize their weights, and finally the reordering is performed thanks to these scores and appropriate optimal weights. The translation quality measured by BLEU, TER and TERp-A after re-ranking using "WCE+N%" (N=25,50,75) can be seen also in Table 2.

We note that all obtained scores behave as expected: the better performance WCE system reaches, the clearer its role in improving MT output quality. Diminishing 25% of the wrongly predicted words leads to a gain of 0.68 point (by MERT) and 0.32 (by MIRA) in BLEU score. More significant increases of BLEU 3.00 and BLEU 3.63 (MERT) can be achieved when prediction errors decrease up to 50% and 75%. These scores suggest that WCE has a promising role in improving MT quality if its quality is adequate.

WCE for SMT Search Graph Re-decoding

The major drawback of the approach previously presented is that the search is limited to a set of N best sentences. What would happen if this space was widened? Will it be efficient for mining better hypothesis? These questions motivate us to investigate SMT search graph re-decoding.

Search Graph Structure

The SMT decoder's Search Graph (SG) can be roughly considered as a "vast warehouse" storing most promising hypotheses generated by the SMT system during decoding for a given source sentence. In this large directed acyclic graph, each hypothesis is represented by a path, carrying all nodes between its start and end ones, along with the edges connecting adjacent nodes. One hypothesis is called complete when all the source words are covered and incomplete otherwise. Starting from the empty initial node, the SG is gradually enlarged by expanding hypotheses during decoding. In order to facilitate the access and the cost calculation, each hypothesis H is further characterized by the following fields:

• hyp: hypothesis ID • back: the backpointer pointing to its previous cheapest path.

• transition: the cost to expand from the previous hypothesis (denoted by pre(H)) to this one. • score: the cost of this hypothesis: score(H) = score(pre(H)) + transition.

• out: the last output (target) phrase, can contain multiple words.

• covered: the source coverage of out, represented by the start and the end position of the source words translated into out. Figure 3 illustrates a simple SG generated for the source sentence: "identifier et mesurer les facteurs de mobilization". The attributes "t" and "c" refer to the transition cost and the source coverage, respectively. Hypothesis 175541 is extended from 57552, when the three words from 3rd to 5th position of the source sentence ("les facteurs de") are translated into "the factors of " with the transition cost of -8.5746. Hence, its cost is: score(175541) = score(57552)+transition(175541) = -16.1014 + (-8.5746) = -24.6760. Three rightmost hypotheses: 204119, 204109 and 198721 are complete since they cover all source words. Among them, the cheapest-cost one is 198721, from which the model-best translation is read off by tracing back to the initial node 0: "identify the causes of action .".

Overview of the Approach

We assume that the decoder generates N best hypotheses T = {T 1 , T 2 , ..., T N } at the end of the first pass. Using the WCE system (which can only be applied to sequences of words -and not directly to the search graph -that is why N best hypotheses are used), we are able to assign the j-th word in the hypothesis T i , denoted by t ij , with one appropriate quality label, c ij ( i.e. "G" (Good: no translation error), "B" (Bad: need to be edited)), along with the confidence probabilities (P ij (G), P ij (B) or P (G), P (B) for short, where P (B) = 1 -P (G)). Then, the second pass is carried out by considering every word t ij as well as its labels and scores c ij , P (G), P (B). Our principal idea is that, if t ij is a positive (good) translation, i.e. c ij = "G or P (G) ≈ 1, all hypotheses H k ∈ SG containing it in the SG should be "rewarded" by reducing their cost. On the contrary, those containing negative (bad) translation will be "penalized". Let reward(t ij ) and penalty(t ij ) denote the reward or penalty score of t ij . The new transition cost of H k after being updated is formally defined by:

transition (H k ) = transition(H k ) + reward(t ij ) if t ij = good penalty(t ij ) if otherwise (3)
The update finishes when all words in the N -best list have been considered. We then re-compute the new score of complete hypotheses by tracing backward via backpointers and aggregating the transition cost of all their edges. Essentially, the re-decoding pass reorders SG hypotheses: the more "G" words (predicted by WCE system) they contain, the more cost reduction will be made and consequently, the more opportunity they get to be the best hypothesis. It is vital to note that, during the update process, we might face a phenomena that the word t ij (corresponds to the same source words) occurs in different sentences of the N -best list. In this case, for the sake of simplicity, we process it only at its first occurrence (in the highest rank sentence) instead of updating the hypotheses containing it multiple times. In other words, if we meet the word t ij which aligns to the same source word once again in the next N-best sentence(s), no further score update will be done in the SG.

Update Score Definitions

Defining the update scores is a nontrivial issue as there is no quantitative estimate on the importance of WCE scores over the SG scores or vice versa. Our approach is to measure their importance empirically via weight optimization. In this article, we propose several types of update scores, deriving from the global or local cost.

Definition #1: Global Update Score

In this type, an unique score derived from the cost of the current best hypothesis H * (by the first pass) is used for all updates. We propose to compute this score by two ways: (a) exploiting WCE labels {c ij }; or (b) only WCE confidence probabilities {P (G), P (B)} will matter and WCE labels will be left aside. Definition #1a:

penalty(t ij ) = α * score(H * ) #words(H * ) reward(t ij ) = -penalty(t ij ) (4)
Where #words(H * ) is the number of target words in H * , the positive coefficient α accounts for the impact level of this score on the final cost of the hypothesis and can be optimized during experiments. Here, penalty(t ij ) gets negative sign (since score(H * ) < 0) and will be added to the transition cost of all hypotheses containing t ij in case where this word is labelled as "B"; whereas reward(t ij ) (same value, opposite sign) is used in the other case. Definition #1b:

update(t ij ) = α * P (B) * score(H * ) #words(H * ) -β * P (G) * score(H * ) #words(H * ) = (α * P (B) -β * P (G)) * score(H * ) #words(H * ) (5)
Where P (G), P (B) (P (G) + P (B) = 1) are the probabilities of "Good" and "Bad" class of t ij . The positive coefficients α and β can be tuned in the optimization phase. In this definition, the fact that update(t ij ) is a reward (reward(t ij )) or a penalty (penalty(t ij )) will depend on t ij 's goodness. Indeed, we have:

update(t ij ) = reward(t ij ) if update(t ij ) > 0, which means: α * [1 -P (G)] -β * P (G) < 0 (since score(H * ) < 0), therefore P (G) > α
α+β . On the contrary, if P (G) is under this threshold, update(t ij ) takes a negative value and therefore becomes a penalty.

Definition #2: Local Update Score

The update score of each (local) hypothesis H k depends on its current transition cost, even when they cover the same word t ij . Similarly to Definition 1, two sub-types are defined as follows: Definition #2a:

penalty(t ij ) = -reward(t ij ) = α * transition(H k ) (6)
Definition #2b:

update(t ij ) = α * P (B) * transition(H k ) -β * P (G) * transition(H k ) = (α * P (B) -β * P (G)) * transition(H k ) (7)
Where transition(H k ) denotes the current transition cost of hypothesis H k , and the meanings of coefficient α (Definition 2a) or α, β (Definition 2b) are analogous to those of Definition 1a (Definition 1b), respectively.

Re-decoding Algorithm

Algorithm 1 Using WCE labels in SG decoding The above pseudo-code depicts our re-decoding algorithm using WCE labels (Definition 1a and Definition 2a). The algorithm in case of using WCE confidence probabilities (Definition 1b and Definition 2b) is essentially similar, except the update step (from line 10 to line 18) is replaced by the following part:

Input: SG = {H k }, T = {T1, T2, ..., TN }, C = {cij} Output: T = {T 1 , T 2 , ...,
for H k in Hypos do transition(H k ) ← transition(H k ) + update(tij) end for
During the update process, the pairs including the visited word t ij and the position of its aligned source words p ij are consequently admitted to be P rocessed, so that all the analogous pairs (t ij , p ij ) occuring in the latter sentences can be discarded. For each t ij , we search for all hypotheses in the SG whose the output phrase (stored in the field out) contains t ij to form the set Hypo. To avoid the ambiguity where t ij occurs multiple times in the sentence, the position coverage (stored in the field covered ) must be ensured to bound the position of the aligned source word of the current t ij . Then, the confidence score of t ij , denoted by c ij (or P (G)), determines whether all members H k in Hypo will be rewarded or penalized. Once having all words in the N -best list visited, we obtain a new SG with updated transition costs for all edges containing them. On this updated SG, we re-compute the score of all complete hypotheses stored in F inal. Finally, we backtrack the cheapest-cost hypothesis to obtain the new translation.

Rank Cost

Hypotheses

G G G G G G G
Table 3. The N-best (N=2) list generated by the SG in Figure 3 and WCE labels

These above depictions can be clarified by taking another look at the example in Figure 3: from this SG, the N -best list (for the sake of simplicity, we choose N = 2) is generated as the single-pass decoder's result. According to our approach, the second pass starts by tagging all words in the list with their confidence labels, as seen in Table 3. Then, the graph update process is performed for each word in the list, sentence by sentence, which details are tracked in Figure 4. In this example, we apply Definition 1a to calculate the reward or penalty score, with α = 1 2 , resulting in: penalty(t ij ) = -reward(t ij ) = 1 2 * -29.9061 6 = -2.4922. Firstly, all hypotheses containing words in the 1st ranked sentence are considered. Since the word "identify" is labeled as "G", its corresponding edge (connecting two nodes 0 and 1) is rewarded: t new = t old + reward = -1.8411 + 2.4922 = +0.6511. On the contrary, the edge between two nodes 121252 and 182453 is penalized and takes new cost: t new = t old + penalty = -5.8272 + (-2.4922) = -8.3194, due to the bad quality of the word "action". The edges having multiple considered words (e.g. between nodes 19322 and 121252) will be updated multiple times, and the transition costs after each update can be also observed in Figure 4 ( e.g. t1, t2, etc). Next, when the 2nd-best is taken into consideration, all repeated words (e.g. "identify", "the" and "of ") are ignored since they have been visited before, whereas the remaining ones are identically processed. The only untouched edge in this SG corresponds to the word "mobilizing", as this word does not belong to the list. Once having the update process finished, we recalculate the final cost for every complete path and return the new best translation: "identify and measure the factors of mobilization" (new cost = -22.6414).

Experimented Decoders

As in the Re-ranking approach, we investigate the WCE's contributions in two scenarios: predicted WCE and ideal WCE (oracles). We experiment with the seven following decoders:

• BL: Baseline (1-pass decoder) • BL+WCE(1a, 1b, 2a, 2b): four 2-pass decoders, using our estimated WCE labels and confidence probabilities to update the SGs, and the update scores are calculated by Definition (1a,1b,2a,2b).

• BL+OR(1a, 2a): two 2-pass decoders, computing the reward or penalty scores by Definition (1a, 2a) on the oracle labels

It is important to note that, when using oracle labels, Definition 1b becomes Definition 1a and Definition 2b becomes Definition 2a, since if a word t ij is labelled as "G", then P (G) = 1 and P (B) = 0, and vice versa. In order to tune the coefficients α and β, we carry out a 2-fold cross validation on the test set.

First, the set is split into two equivalent parts: S1 and S2. Playing the role of a development set, S1 will train the parameters which are then used to compute the update scores on S2 re-decoding process, and vice versa. The optimization steps are handled by CONDOR toolkit [START_REF] Frank | CONDOR: a constrained, non-linear, derivative-free parallel optimizer for continuous, high computing load, noisy objective functions[END_REF], in which we vary α and β within the interval [0.00; 5.00]. Test set is further divided to launch experiments in parallel on our cluster using an open-source batch scheduler: OAR [START_REF] Capit | OAR Documentation -User Guide[END_REF]. This mitigates the overall processing times on such huge SGs. The re-decoding results for them are properly concatenated for evaluation. Tuned values for these parameters are: α = 0.9 (Definition 1a); α = 1.7, β = 0.8 (Definition 1b); α = 0.9 (Definition 2a); and α = 1.8, β = 0.8 (Definition 2b). Table 4. Translation quality of the conventional decoder and the 2-pass decoders using scores from predicted or oracle WCE, followed by the percentage of better (B), equivalent (E) or worse (W) sentences compared to BL system, as well as p-values Table 4 shows the translation performances of all experimental decoders and their percentages of sentences which outperform, remain equivalent or degrade the baseline hypotheses (when match against the references, measured by TER). Results suggest that using oracle labels to re-direct the graph searching considerably boosts the baseline quality. BL+OR(1a) augments 7.87 points in BLEU, and diminishes 0.0607 (0.0794) point in TER (TERp-A), compared to BL. Meanwhile, with BL+OR(2a), these gains are 7.67, 0.0565 and 0.0514 (in that order). Besides, the contribution of our WCE system scores seems less prominent, yet positive: the best performing BL+WCE(1a) increases 1.49 BLEU points of BL (0.0029 and 0.0136 gained for TER and TERp-A). The small p-values (in the range [0.00; 0.02], seen on Table 2) estimated between BLEU of each BL+WCE system and that of BL using Approximate Method [START_REF] Clark | Better hypothesis testing for statistical machine translation: Controlling for optimizer instability[END_REF] indicate that these performance improvements are significant. Results also reveal that the use of WCE labels is slightly more beneficial than that of confidence probabilities: BL+WCE(1a) and BL+WCE(2a) outperform BL+WCE(1b) and BL+WCE(2b). In both scenarios, we observe that the global update score (Definition 1) performs better compared to the local one (Definition 2). For more insightful understanding about WCE scores' usefulness, we make a comparison with the best achievable hypotheses in the SG (oracles), based on the "LM Oracle" approximation approach presented in (Sokolov, Wisniewski and Yvon (2012)). This method simplifies the oracle decoding to the problem of searching for the cheapest path on a SG where all transition costs are replaced by the n-gram LM scores of the corresponding words. The LM is built for each source sentence uniquely using its target post-edition. We update the SG by assigning all edges with the LM back-off score of the word it contains. Finally, we combine the oracles of all sentences yielding BLEU oracle of 66.48: 6.30 points higher than BL+OR(1a). This result reveals that the use of oracle WCE scores, although helps to outperform significantly over the Baseline (52.31 BLEU → 60.18 BLEU), yet still remains a big gap to the best-achievable performance by SG re-decoding. It opens a room for future work on how to exploit WCE scores more efficiently toward this goal. We close this section with some examples of outputs before and after the redecoding process (shown in Table 5). In the first example, re-decoding yields a slightly better translation compared to the baseline MT system. Using labels predicted by WCE: "Bad" for "a" (at the beginning of the MT hypothesis) and "penalty", and "Good" for the rest, BL+WCE(1a) led to a new candidate whose last words ("demoralization death") are closer to the post-edition ("deadly demoralization") than the corresponding part of BL ("penalty demoralisation"). Similarly, in the second example, thanks to word error detection in the second example (tagged for "it has", "speech that was", and "post route"), BL+OR(1a) helped to translate correctly the pronoun ("he" instead of "it"), as well as to translate better the final part of the source sentence (into "after operating were normal"). The positive contributions of WCE-predicted labels and scores can also be observed in the remaining (from the third to the fifth) examples in the same table.

Results

Systems

Discussion, Conclusion and Perspectives

If we compare the performances between the use of WCE for N -best list re-ranking (Table 2) and SG Re-decoding (Table 4), the results suggest that the contribution of WCE in SG re-decoding outperforms that in N-best re-ranking in both "oracle" or real scenarios. BL+OR(1a) outperforms its corresponding oracle reranker BL+OR(N-best Reranking) in 2.08 points of BLEU, diminishes 0.0253 (0.0280) in TER (TERp-A). Meanwhile, BL+WCE(1a) beats BL+WCE(Nbest Reranking) (the re-ranker which uses predicted WCE scores) in 1.03 (BLEU), 0.0015 (TER), 0.0103 (TERp-A). In addition, there are 178 out of 881 sentences (20.20 %) outputted by BL+WCE(1a) that do not belong to the N-best list, suggesting that the re-decoding method can help to generate candidates which

BL

for the rail traffic system , s21 is damaging . BL+OR (2a)

for the system of rail transport the s21 is harmful .

Post-edition

for the railway transportation system the s21 is harmful . Example 4 Source tout comme le rêve , la psychose ouvre les écluses à une marée d' idées et de fantasmes issue des couches plus profondes de la conscience . BL as the dream , the hype opens the floodgates to a tide of ideas and fantasies , the deeper layers of conscience . BL+OR (1b) like the dream , a psychosis also opens the floodgates to a tide of ideas and phantasies , which stem from the deepest layers of conscience . Post-edition just like the dream , the psychosis opens the floodgates to a tide of ideas and fantasies that emerged from the deepest layers of consciousness . Example 5 Source burda avait fait savoir jeudi dernier qu' il se retirait du poste président-directeur-général dès le mois de janvier et que son successeur était paul-bernhard kallen . BL burda said last thursday that it is pulling out of the post présidentdirecteur-général in january and that his successor was paul-bernhard kallen . BL+OR (2b) burda let it be known last thursday that he is pulling out of his post président-directeur-général in january and that his successor was paul-bernhard kallen . Post-edition burda let it be known last thursday that he is pulling out of his post as president director general beginning in january and that his successor would be paul-bernhard kallen .

Table 5. Examples of MT outputs before and after re-decoding have not been nominated by SMT decoder. More notably, among these newlyproduced translations, 113 (63.5%) translations are better than the corresponding 1-best of the N-best list, measured by sentence-level BLEU+1 metric [START_REF] Nakov | Optimizing for sentence-level bleu+1 yields short translations[END_REF]). These positive results can be explained by the following facts: (1) in re-ranking, WCE scores are integrated at sentence level, so word translation errors are not fully penalized; and (2) in re-ranking, best translation selection is limited to the N -best list, whereas in re-decoding, we allow the search over the entire updated SG (on which not only N-best list paths but also those containing at least one word in this list are altered).

To conclude, we have presented two novel two-pass decoding methods for enhancing SMT quality. From the output of the first pass (N -best list), we predict words' labels and confidence probabilities, then employ them to seek a more valuable candidate; first among the other in the N -best list, and then over the entire SGs. In both methods, while "oracle" WCE labels substantially improve the MT quality (to reach the oracle score), real WCE achieves also the positive and promising gains. These methods show that error prediction using WCE helps to guide the decoding to less erroneous parts of the graph.

As future work, we plan to focus on enhancing our WCE system using more linguistic features as well as advanced techniques (feature selection, Boosting method...). We also focus on breaking down the translation errors (i.e."Bad" label) into more concrete categories, so that they will be more informative. Besides, the update scores used in this article will be further considered towards the consistency with SMT graph scores to obtain a better updated SG. Also, currently in the graph-redecoding process, our WCE scores can only be applied to sequences of words -and not directly to the search graph. Applying WCE to tag directly the search graph will be part of future work. Finally, we will investigate the use of WCE labels to re-decode speech translation graphs and improve spoken language translation (SLT) performance.

for statistical machine translation. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 64-73, Prague, Czech Republic. Wisniewski, G., Pécheux, N., Allauzen, A. and Yvon, F. 2014

Fig. 1 .

 1 Fig. 1. The correlation between WQS in a sentence and its overall quality measured by: (a) BLEU, (b) TER and (c) TERp-A metrics

Fig. 2 .

 2 Fig. 2. Example of our WCE classification results for one MT hypothesis

Fig. 3 .

 3 Fig. 3. An example of search graph representation

Fig. 4 .

 4 Fig. 4. Details of update process for the SG in Figure 3. The first loop is represented in red color, while the second one is in blue. For edges with multiple updates, all transition costs after each update are logged. The winning cost is emphasized by green color.

  • Lexical Features: word's Part-Of-Speech (POS) obtained by TreeTagger toolkit

5

on both source and target sides; sequence of POS of all its aligned source words; POS bigram (trigram) backward sequences; binary lexical features: is the character sequence a punctuation? a proper name? a numerical value?

• Syntactic Features: null link (Xiong et al. 2010); constituent label; depth in the constituent tree • Semantic Features: number of word senses in WordNet.

Table 2 .

 2 The results obtained show that the integration of oracle scores signifi-

	Systems	MERT		MIRA
		BLEU TER TERp-A BLEU TER TERp-A
	BL	52.31 0.2905	0.3058	50.69 0.3087	0.3036
	BL+OR	58.10 0.2551 0.2544 55.41 0.2778 0.2682
	BL+WCE	52.77 0.2891	0.3025	51.01 0.3055	0.3012
	WCE + 25%	53.45 0.2866	0.2903	51.33 0.3010	0.2987
	WCE + 50%	55.77 0.2730	0.2745	53.63 0.2933	0.2903
	WCE + 75%	56.40 0.2687	0.2669	54.35 0.2848	0.2822
	Oracle BLEU score BLEU=60.48

Table 2 .

 2 Translation quality of the baseline system (only decoder scores) and that with additional scores from real "WCE" or "oracle" WCE system cantly boosts the MT output quality, measured by all three metrics and optimized by both tuning methods employed. We gained 5.79 and 4.72 points in BLEU score, byMERT and MIRA (respectively). With TER, BL+OR helps to gain 0.03 point in both methods. Meanwhile, in case of TERp-A, the improvement is 0.05 point for MERT and 0.03 point for MIRA. It is worthy to mention that the possibility of

obtaining such oracle labels is doable through a human-interaction scenario (which could be built from a tool like PET (Post-Editing Tool)

(Aziz, De Sousa and Specia (

  . Limsi submission for wmt'14 qe task. In Proceedings of the Ninth Workshop on Statistical Machine Translation, Baltimore, Maryland, USA. Xiong, D., Zhang, M. and Li, H. 2010. Error Detection for Statistical Machine Translation Using Linguistic Features. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, 604-11, Uppsala, Sweden. Zhang, Y., Almut, S.H. and Stephan, V. 2006. Distributed language modeling for n-best list re-ranking. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), 216-23, Sydney.

https://github.com/snover/terp

TERp is an extension of TER (Translation Edit Rate) that uses phrasal substitutions (using automatically generated paraphrases), stemming, synonyms, relaxed shifting constraints and other improvements.

http://www.statmt.org/wmt10/

https://wapiti.limsi.fr/

http://www.cis.uni-muenchen.de/ schmid/tools/TreeTagger/