Philippe Balbiani

Ilya B Shapirovsky

Valentin B Shehtman

Every world

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

The starting point for our research is the well-known Sahlqvist Theorem. For about thirty years this result was considered as the strongest one giving a syntactic sufficient condition for completeness and first-order definability (elementarity) in modal logic. More recent studies show that Sahlqvist class can be extended to a larger class of "inductive" modal formulas inheriting both completeness and elementarity [START_REF] Goranko | Elementary canonical formulae: extending Sahlqvist's theorem[END_REF].

Now there is natural question: what happens beyond this new class? It is well-known that completeness or definability may be lost. Perhaps the simplest counterexample is given by the McKinsey axiom 3p → 3 p, which is non-elementary, but still complete and even has the finite model property. So after a slight variation of Sahlqvist formulas we may still hope to preserve at least some of nice properties.

On the other hand, recently Ian Hodkinson has found a precise description of quasi-elementary logics (i.e. those complete with respect to elementary classes of Kripke frames) [START_REF] Hodkinson | Hybrid formulas and elementarily generated modal logics[END_REF]: he defines a translation from a first-order theory T into a set of hybrid modal formulas, and next -into a set of pure modal formulas axiomatizing exactly the class of models of T . Moreover, the corresponding hybrid formulas are identified as "quasipositive". This general result is quite impressive, but the suggested axiomatization method may be not optimal in particular cases.

The class of modal logics studied in this paper is certainly covered by Hodkinson's theorem, but we propose a simpler description, which does not directly follow from [START_REF] Hodkinson | Hybrid formulas and elementarily generated modal logics[END_REF]. Namely, consider different versions of a modal formula ϕ(p 1 , . . . , p k ) with disjoint sets of proposition letters: ϕ = ϕ(p k+1 , . . . , p 2k ), ϕ = ϕ(p 2k+1 , . . . , p 3k ), . . . and put

ϕ n 3 = 3(ϕ ∧ ϕ ∧ • • • ∧ ϕ (n-1) ),
Advances in Modal Logic, Volume 6. c 2006, the authors.

L 3 (ϕ) = K + {ϕ n 3 | n ≥ 0}.
As we show, every logic L 3 (ϕ) is quasi-elementary, whenever ϕ is a Sahlqvist formula (or even an inductive formula). By Fine -Van Benthem Theorem (cf. [START_REF] Chagrov | Modal Logic[END_REF]Theorem 10.19]) this implies canonicity. An appropriate first-order condition can be obtained in a standard way:

∀x∃t(xRt ∧ Φ(t)),
where Φ is the first-order correspondent of ϕ, i.e. "every world sees a ϕworld". However this condition does not always characterize the frames for assume the reader is at home with well-known results such as Sahlqvist's theorem and Ladner's theorem. For more on these see Blackburn, de Rijke and Venema [START_REF] Blackburn | Modal Logic[END_REF], Chagrov and Zakharyaschev [START_REF] Chagrov | Modal Logic[END_REF] and Kracht [START_REF] Kracht | Tools and Techniques in Modal Logic[END_REF]. Still in this Section we recall some basic notions, for the sake of terminology and notation.

Syntax

Let P V = {p 1 , p 2 , . . . } be a countable set of proposition letters, with typical members denoted by p, q, etc. Modal formulas over P V are built using the constant ⊥, the unary connective and the binary connective →. Other constructs are defined as usual, in particular 3ϕ is the abbreviation for ¬ ¬ϕ.

For a formula ϕ, cl(ϕ) denotes the set of all subformulas of ϕ. Put P V (ϕ) = cl(ϕ) ∩ P V . The notation ϕ(p 1 , . . . , p n ) means {p 1 , .., p n } ⊇ P V (ϕ). For formulas ψ 1 , . . . , ψ n , ϕ(ψ 1 , . . . , ψ n ) denotes the result of simultaneous substitution of ψ 1 , . . . , ψ n for p 1 , . . . , p n in ϕ. For a set x of formulas, let x = {ϕ | ϕ ∈ x}.

A (normal) modal logic is a set L of formulas that contains all tautologies, the formula (p → q) → ( p → q) and that is closed under the standard rules: Modus ponens, Uniform substitution, and Generalization (given ϕ infer ϕ).

For a set Γ of formulas, L + Γ denotes the smallest modal logic containing (L ∪ Γ).

A formula ϕ is said to be L-deducible from a set Γ of formulas, in symbols Γ L ϕ if there exists formulas ϕ 1 , . . ., ϕ n ∈ Γ such that (ϕ 1 ∧ . . .

∧ ϕ n → ϕ) ∈ L. A set Γ of formulas is called L-consistent if Γ L ⊥.
Recall the inductive definition of uniform modal formulas. Any formula without modal operators is a uniform formula of degree 0; uniform formulas of degree n + 1 are built from the set { ψ | ψ is a uniform formula of degree n} using boolean connectives.

A logic is called uniform if it can be axiomatized by uniform formulas.

Semantics

As usual, a (Kripke) frame is a pair F = (W, R), where W is a non-empty set of worlds and R is a binary relation on

W . A world x ∈ W is called final in F if R(x) ⊆ {x} and deterministic in F if card(R(x)) ≤ 1. F is called serial if for all worlds x in W , R(x) = ∅.
For a world x in W and sets W 1 , . . ., W n ⊆ W , we say that

{W 1 , . . . , W n } is a cover of R(x) if R(x) ⊆ W 1 ∪ • • • ∪ W n .
A (Kripke) model based on F is a pair M = (F, V ), where V is a function assigning to each proposition letter p a subset V (p) of W . The inductive definition of the truth value of a formula ϕ at a world x in a model M is standard. M, x ϕ denotes that ϕ is true at x in M.

A formula ϕ is called true (respectively satisfiable) in a model M = (W, R, V ), in symbols M ϕ, if ϕ is true at any (resp., some) world in W ; ϕ is valid in a frame F, in symbols F ϕ, if ϕ is true in all models based on F. ϕ is valid at F, x (notation: F, x ϕ) if it is true at x in all models based on F. A formula ϕ is said to be valid in a class C of frames, in symbols C ϕ, if ϕ is valid in all frames in C. We say that a set L of formulas is valid in a frame F, in symbols F L, if all formulas from L are valid in F.

Every frame can also be regarded as a first-order structure, and we use the same sign to denote the truth of a first-order formula in this structure.

The modal logic of a class of frames C is defined as

L(C) = {ϕ | C ϕ}. A logic L is called complete with respect to C if L = L(C).
L is said to have the finite model property (fmp) if it is complete with respect to a class of finite frames.

We say that a set of modal formulas Γ modally defines the class of frames

Fr(Γ) := {F | F Γ}; Γ modally defines C within a class C if C = Fr(Γ)∩C .
We say that a formula ϕ modally defines C [within C ] if the set {ϕ} does.

A modal logic L is called strongly complete with respect to a class C of frames if for any L-consistent set Γ of formulas, there exists a model M based on a frame from C such that all formulas from Γ are simultaneously true at some world in M.

Recall that a formula ϕ is locally elementary if for some first-order formula Φ with only one free variable t we have: for any frame F and any world a in F, F, a ϕ iff F Φ(a). In this case Φ is called a local first-order correspondent of ϕ.

A set Γ of modal formulas is called elementary (respectively, Δ-elementary) if the class Fr(Γ) is elementary (respectively, Δ-elementary), i.e. if Fr(Γ) is the class of models of some first-order formula (resp., theory). Every locally elementary formula is obviously elementary.

A modal logic of the form L(C), for an elementary C, is called quasielementary (or elementarily generated).

Every world can see a ϕ-world

In this section we describe a family of quasi-elementary and finitely elementary logics.

For a tuple of proposition letters p = (p 1 , . . . , p k ) let

p n := (p kn+1 , . . . , p kn+k )
for n ≥ 0. So p 0 = p and all the tuples p n are disjoint. For a modal formula ϕ(p) put

ϕ n 3 := 3(ϕ(p 0 ) ∧ • • • ∧ ϕ(p n-1 ))
(in particular, ϕ 0 3 := 3 ), and also

L 3 (ϕ) := K + {ϕ n 3 | n ≥ 0}, L n 3 (ϕ) := K + ϕ n 3 . The following is rather trivial. PROPOSITION 1. L 0 3 (ϕ) ⊆ L 1 3 (ϕ) ⊆ L 2 3 (ϕ) . . . ⊆ L 3 (ϕ)
. Now let ϕ be a locally elementary formula, and let Φ(t) be its local firstorder correspondent. Consider the class of frames

C 3 (ϕ) := {F | F ∀x∃t(xRt ∧ Φ(t))}.
LEMMA 2. For a locally elementary formula ϕ, C 3 (ϕ) ⊆ Fr(L 3 (ϕ)).

Proof. Suppose F ∈ C 3 (ϕ(p)). This means that for any a ∈ F there exists b ∈ R(a) such that F Φ(b), which is equivalent to F, b ϕ, by the definition of Φ. But the latter implies F, b ϕ(p n ) for any n, hence F, a ϕ n 3 , and thus F, a L 3 (ϕ).

A formula ϕ is locally d-persistent if for any descriptive (general) frame (F, D) and any world a, (F, D), a ϕ implies F, a ϕ (the notion of a descriptive frame is defined in a standard way, see e.g. [START_REF] Chagrov | Modal Logic[END_REF]). THEOREM 3. Let ϕ be a locally elementary and locally d-persistent modal formula. Then 1. the canonical frame for L 3 (ϕ) is in C 3 (ϕ); 2. L 3 (ϕ) is canonical and therefore strongly complete with respect to C 3 (ϕ).

Proof. Let us prove (1); then (2) readily follows from Lemma 2 and the properties of the canonical model. Let F = (W, R) be the canonical frame for L 3 (ϕ(p)), p = (p 1 , . . . , p k ). For any a ∈ W , put

a + := a ∪ {ϕ(ψ 1 , . . . , ψ k ) | ψ 1 , . . . , ψ k are arbitrary modal formulas}. Claim 1 a + is L 3 (ϕ)-consistent.
Suppose the contrary. Then for some formulas γ 1 , . . . , γ m ∈ a and for some k-tuples of formulas ψ 1 , . . . , ψ n we have

L 3 (ϕ) γ 1 ∧• • •∧γ m ∧ϕ(ψ 1 )∧ • • • ∧ ϕ(ψ n ) → ⊥. Since 3(ϕ(ψ 1 ) ∧ • • • ∧ ϕ(ψ n )) is a substitution instance of ϕ n 3 , we have 3(ϕ(ψ 1 )∧• • •∧ϕ(ψ n )) ∈ a, so for some b ∈ R(a) we have ϕ(ψ 1 ), . . . , ϕ(ψ n ) ∈ b. Since every γ i is in a , we also have γ 1 , . . . , γ m ∈ b, so ⊥ ∈ b, which is a contradiction. Q.e.d.
By the Lindenbaum Lemma, there exists b ∈ W such that a + ⊆ b. So a ⊆ b, thus aRb. Now consider the general canonical frame (F, D) for L 3 (ϕ); recall that

D = {V 0 (ψ) | ψ is a modal formula},
where V 0 is the canonical valuation. Claim 2 (F, D), b ϕ.

In fact, for a valuation V in (F, D) let us show that b ∈ V (ϕ). By definition of D, for every i there exists a modal formula ψ i such that V (p i ) = V 0 (ψ i ); let ψ = (ψ 1 , . . . , ψ k ). Then by induction it follows that

V (ϕ(p)) = V 0 (ϕ(ψ)). But b ⊇ a + , so ϕ(ψ) ∈ b, and thus b ∈ V 0 (ϕ(ψ)) = V (ϕ). Q.e.d.
Since (F, D) is descriptive and ϕ is locally d-persistent, from Claim 2 we obtain F, b ϕ, i.e. F Φ(b); thus F ∀x∃t(xRt ∧ Φ(t)).

For a set Γ of modal formulas we can also define

L 3 (Γ) := K + {ϕ n 3 | ϕ ∈ Γ, n ≥ 0}, C 3 (Γ) := ϕ∈Γ C 3 (ϕ).
So we have Proof. In fact, every inductive formula is locally elementary and locally d-persistent [START_REF] Goranko | Elementary canonical formulae: extending Sahlqvist's theorem[END_REF]. DEFINITION 6. A modal logic L is called finitely elementary if there exists a first-order formula Φ such that for any finite frame F, F L iff F Φ.

THEOREM 7. If ϕ is a locally elementary modal formula, then L 3 (ϕ) is finitely elementary.

Proof. For a formula ϕ(p), p = (p 1 , . . . , p k ) with a local first-order correspondent Φ, let us prove that F L 3 (ϕ) iff F ∈ C 3 (ϕ) for any finite frame F. The direction "if" is already proved in Lemma 2. So consider a finite frame F = (W, R) with card(W ) = n, such that F L 3 (ϕ). We have to show that F ∀x∃t(xRt ∧ Φ(t)).

Consider the following Kripke model M = (F, V ). Take the N -element set P(W ) k of all k-tuples of subsets of W (where N = 2 nk ) and put it in some order: W 0 , W 1 , . . . , W N -1 . If W j = (W j 1 , . . . , W j k ), we define

V (p jk+i ) := W j i .
So we have defined V (p m ) for m = 1, . . . , Nk, and we assume that V (p m ) is arbitrary for all other m.

Now take any

a ∈ W . Since M, a ϕ N 3 , there exists b ∈ R(a) such that M, b ϕ(p 0 ) ∧ • • • ∧ ϕ(p N -1
). Then we claim that F, b ϕ. In fact, consider an arbitrary valuation V in F. By our construction, there exists j such that W j = (V (p 1 ), . . . , V (p k )), i.e.

V (p i ) = V (p jk+i ) whenever 1 ≤ i ≤ k.
Hence by induction it easily follows that

V (ϕ(p)) = V (ϕ(p j )). Now since M, b ϕ(p j ), we obtain (F, V ), b ϕ. Thus F, b ϕ, which is equivalent to F Φ(b). Eventually F ∀x∃y(xRy ∧ Φ(y)).
The following simple fact is motivated by Proposition 6.2 from [START_REF] Hodkinson | Hybrid formulas and elementarily generated modal logics[END_REF], though it is not formulated explicitly in that paper. PROPOSITION 8. If a recursively axiomatizable and finitely elementary modal logic has the fmp, then it is decidable.

Proof. In fact, if finite frames for L are defined by a certain first-order sentence, then the set of finite L-frames (whose worlds are identified with integers) is decidable. Together with the fmp, this implies the co-enumerability of L. So since L is recursively enumerable, it is decidable.

Note that in general a recursively axiomatizable logic with the fmp can be undecidable (the three-dimensional logic K 3 is a typical example), but this does not affect the logics considered in the present paper.

Every world can see a final world

Definitions

In this section we consider a particular case of the above construction, when ϕ = (p 1 → p 1 ). The corresponding first-order formula is Φ(t) = ∀x(tRx → t = x).

Let

α n := ϕ n 3 = 3((p 1 → p 1 ) ∧ . . . ∧ (p n → p n ))
. Consider the modal logics (for 0 ≤ n < ω):

L fw n := K + α n , L fw ω := L 3 (ϕ) = K + {α 0 , α 1 , . . .}. Note that L fw 0 = D = K + 3 and L fw 1 = K + 3(p → p) = K + p → 3 p. Then C 3 (ϕ) is the class C fw ω of all frames F = (W, R) satisfying possible finality condition 1
• for all worlds x in W , there exists a world y in R(x) such that R(y) ⊆ {y},

i.e. every world can see a final world. Let us also consider for every n ≥ 0, the class C fw n of all frames F = (W, R) such that • for all worlds x in W and for all covers {W 1 , . . . , W n } of R(x), there exists a world y in R(x) such that for all i in {1, . . . , n}, if y

∈ W i then R(y) ⊆ W i . PROPOSITION 9. C fw 0 ⊇ C fw 1 . . . ⊇ C fw ω .
Proof. Trivial.

Weakly condensed frames

Remark that C fw 0 is nothing but the class of all serial frames and C fw 1 is the class of all weakly condensed frames F = (W, R), i.e. such that:

• for all worlds x ∈ W , there exists y ∈ R(x) such that R(y) ⊆ R(x).

For a frame F = (W, R), consider the relation R → ⊆ R:

xR → y := {y} ∪ R(y) ⊆ R(x) Thus F is weakly condensed iff (W, R → ) is serial. One can easily see that R → is transitive: if xR → yR → z, then R(z) ∪ {z} ⊆ R(y) ⊆ R(x).
By a straightforward argument, F is weakly condensed iff F α 1 . Since the Sahlqvist formula p → 3 p is an equivalent form of α 1 , we obtain LEMMA 10. If F is the canonical frame for a logic L ⊇ L fw 1 , then F is weakly condensed.

Completeness

THEOREM 11. The canonical frame for L fw 2 is in C fw ω .

Proof. Let F = (W, R) be the canonical frame for L = L fw 2 . For any x ∈ W , put x + := x ∪ { ϕ | ϕ ∈ x}. Claim 1 For any worlds x, y in the canonical model

R(x) ⊇ R(y) iff y ⊇ { ϕ | ϕ ∈ x}.
In fact, if y ⊇ { ϕ | ϕ ∈ x} and yRz, then by the definition of R, ϕ ∈ x implies ϕ ∈ z, i.e. xRz. The other way round, if y ⊇ { ϕ | ϕ ∈ x}, then for some ϕ ∈ x we have ϕ ∈ y, and so there exists

z ∈ R(y) such that ϕ ∈ z. But ϕ ∈ x, hence z ∈ R(x). Therefore R(y) ⊆ R(x). Q.e.d.
Claim 2 xR → y iff y ⊇ x + . In fact, by definition, xRy iff y ⊇ x , and

R(x) ⊇ R(y) iff y ⊇ { ϕ | ϕ ∈ x}, by Claim 1. Q.e.d.
Due to Lemma 10, F is weakly condensed, and thus by Claim 2, x + is an L-consistent set for any x ∈ W .

For the proof of our theorem, consider an arbitrary world x in W . Assuming that all formulas are arranged in some fixed order ϕ 1 , ϕ 2 , . . ., we define the sequence y 0 , y 1 , . . . of L-consistent sets of formulas by induction:

But (3) 3((ϕ ∧ ϕ → (ϕ ∧ ϕ)) ∧ (ϕ ∧ ¬ϕ → (ϕ ∧ ¬ϕ))) ∈ L
as a substitution instance of α 2 . Since ϕ ∈ y , from ( 2) and ( 3) we obtain for some w ∈ R(y ):

¬(ϕ ∧ ϕ) ∧ ¬(ϕ ∧ ¬ϕ) ∈ w.
Then ¬ϕ ∈ w, which contradicts ϕ ∈ y .

Therefore u is L-consistent. By the Lindenbaum Lemma, there exists a maximal L-consistent set u ⊇ u. By the above construction and Claim 2, y R → u , and also 3ϕ → ϕ ∈ u . So by Claim 3, R(u ) = R(y ). Therefore z, t are worlds in R(u ). Hence 3ϕ ∈ u , and consequently ϕ is in u . Thus ϕ is in t: a contradiction. Q.e.d.

Since F is weakly condensed, for some z we have y R → z, i.e., y Rz and However let us give a syntactic proof of this fact proposed by Max Cresswell in a private communication.

R(z) ⊆ R(y ). By Claim 4, R(y ) = {z}, thus R(z) ⊆ {z}. xR → y and y R → z implies xRz, since R → is transitive and R → ⊆ R. Thus F ∈ C fw ω . COROLLARY 12. L fw
It is sufficient to show that L fw n α n+1 for n ≥ 2. Let Proof. Let F = (W, R) be a frame such that F L fw n and let us show that F ∈ C fw n . Take an arbitrary world x in W and a cover {W 1 , . . . , W n } of R(x). Let M = (F, V ) be a model based on F such that V (p 1 ) = W 1 , . . ., V (p n ) = W n . Since x α n , there exists a world y in R(x) such that for all i in {1, . . . , n}, M, y p i → p i . Then for any i in {1, . . . , n}, if

π 1 := (p 1 → p 1 ), π 2 := (p 2 → p 2 ) ∧ • • • ∧ (p n → p n ), π 3 := (p n+1 → p n+1 ). Now we argue in L fw n : (1) 3(π 1 ∧ (¬q → ¬q)) α 2 , Subst (2) 3(π 1 ∧ (3q → q)) (1), equivalent replacement (3) 3(π 1 ∧ (3(π 2 ∧ π 3 ) → (π 2 ∧ π 3 ))) (2), Subst (4) 3(π 2 ∧ π 3 ) α n , Subst (5) 3(π 2 ∧ π 3 ) ( 4 ) , Gen (6) 3(p ∧ (q → r)) → ( q → 3(p ∧ r)) derivable in K (7) 3(π 1 ∧ π 2 ∧ π 3 ) ( 6 ) , Subst, (3)
y ∈ W i , then R(y) ⊆ W i . Now suppose F = (W, R) is a frame such that F L fw n .
Then there exists a model M = (F, V ) and a world x ∈ W such that for any y ∈ R(x), there exists i in {1, . . . , n} such that M, y p i → p i . Let W i = V (p i ). Then {W 1 , . . . , W n } is a cover of R(x) and for any y ∈ R(x) there exists i in {1, . . . , n} such that y ∈ W i , but R(y) ⊆ W i . Hence F ∈ C fw n .

COROLLARY

(W, R → ) is in C fw 2 . In fact, let x ∈ W and let {W 1 , W 2 } be a cover of R → (x). Also let V 1 := W 1 ∩ R → (x), V 2 := W 2 ∩ R → (x), V 3 = R(x) \ (V 1 ∪ V 2 ). So {V 1 , V 2 , V 3 } is a cover of R(x) and there exists a world y in R(x) such that for all i in {1, 2, 3}, if y ∈ V i , then R(y) ⊆ V i ⊆ R(x). Therefore y ∈ R → (x). Next, for i = 1, 2 we have: if y ∈ W i , then y ∈ V i , so R → (y) ⊆ R(y) ⊆ V i ⊆ W i . Hence (W, R → ) is in C fw 2 . Q.e.d. Claim 2 (W, R → ) is in C fw ω . In fact, 3p → 3 p is in L fw
, R → ) 3p → 3 p. Since R → is transitive, (W, R → ) is in C fw ω . Q.e.d.
By Claim 2, for any world x there exists a world y in R → (x) such that R → (y) ⊆ {y}. Let W 1 = {y} and W 2 = R(y) \ {y}. Then {W 1 , W 2 } is a cover of R(y), and so there exists a world z ∈ R(y) such that for all i in {1, 2}, if z ∈ W i , then R(z) ⊆ W i .

Claim 1 F L dw ω . It is sufficient to show that for all n ≥ 0 and for all models M based on F, M, x β n . Since W/ ≡ M n is finite, there exists an

≡ M n -equivalence class U 0 such that U := U 0 ∩ Z is infinite. Then M, y U (3p 1 → p 1 ) ∧ . . . ∧ (3p n → p n ) and therefore M, x β n . Q.e.d.
Now suppose the class Fr(L) is Δ-elementary, i.e., definable by a firstorder theory T in the language {R, =}. Since F L dw ω , we have F L, thus F T . By the Löwenheim-Skolem theorem, there exists a countable subframe F = (W , R ) of F such that W ⊇ Z ∪ {x} and F T . Then F L, and thus F β 1 However by [6, Theorem 1], ¬β 1 is satisfiable at a point x in a frame (W, R) if for all y in R(x), R(y) is infinite and card(R(y)) ≥ card(R(x)). Thus F , x β 1 .

This contradiction proves the theorem.

COROLLARY 22. C dw ω is not modally definable.

Proof. In fact, if an elementary class of frames C is modally definable, then its modal logic L(C) is elementary -just because Fr(L(C)) is the smallest modally definable class containing C.

For v = {v 1 , . . . , v n } ∈ {0, 1} n , put p v := 1≤i≤n p vi i , where p 1 := p, p 0 := ¬p. It is not difficult to check that for all n > 0, β n is equivalent to results show that they are quasi-elementary. Are they elementary? finitely axiomatizable? Note that e.g. K4 + L 3 (p → p) = K4 + 3p → 3 p is elementary. 10. Theorem 3 can probably be extended to a larger class of logics. Of course, it survives in the polymodal case. Moreover, instead of the prefix 3 one can take a prefix 3 k1 . . . 3 kn , with the corresponding condition "every world sees a ϕ-world via the composed relation R k1 • • • • • R kn ". And furthermore, we can consider more complicated conditions, like "every world sees a world seeing a ϕ-world and a ψ-world". It would be interesting to find a natural general result of this kind.

COROLLARY 4 .COROLLARY 5 .

 45 If Γ is a set of locally elementary and locally d-persistent modal formulas, then L 3 (Γ) = L(C 3 (Γ)). If Γ is a set of inductive modal formulas, then L 3 (Γ) = L(C 3 (Γ)), and thus this logic is canonical and strongly complete with respect to C 3 (Γ).

2

  is strongly complete with respect to C fw ω . COROLLARY 13. The McKinsey formula 3p → 3 p is in L fw 2 . Proof. 2 In fact, C fw ω 3p → 3 p. PROPOSITION 14. L fw 2 = L fw 3 . . . = L fw ω . Proof. Follows from Theorems 3 and 11.

  , MP,[START_REF] Goldblatt | First-order definability in modal logic[END_REF], MP Note that together with Theorem 3, this argument provides an alternative proof of Theorem 11.

4. 4 ElementarityPROPOSITION 15 .

 415 Let n ≥ 2. Then for any frame F, F ∈ C fw n iff F L fw n .

2 (

 2 Corollary 13); then by Proposition 15 and Claim 1, (W

v∈{0,1} n 3 p

 3 v . Thus the logics L dw 1 , L dw 2 , . . . , L dw ω are uniform. Since all serial uniform logics have the fmp (see e.g. [4]), we have the following THEOREM 23. The logics L dw 1 , L dw 2 , . . . , L dw ω have the fmp. COROLLARY 24. The logics L dw 1 , L dw 2 , . . . , L dw ω are decidable.

In the transitive case it is also called "McKinsey property"[START_REF] Segerberg | Decidability of S4.1[END_REF]

Note that there also exists a simple syntactic proof of this corollary.

View publication stats

Acknowledgements

Many thanks to Mikhail Rybakov, Tinko Tinchev and Dimiter Vakarelov who made several helpful comments for improving the readability of the paper. Special thanks to three anonymous referees and also to Ian Hodkinson and Yde Venema who made essential remarks on the earlier version of the paper. We also thank Max Cresswell who kindly sent us his syntactic proof of Proposition 14.

The work of the second and the third authors was supported by Poncelet Laboratory (UMI 2615 of CNRS and Independent University of Moscow), by RFBR-NWO grant 047.011.2004.040, and by Russian presidential program of support of leading scientific schools 5351.2006.1.

BIBLIOGRAPHY

Let y = y 0 ∪ y 1 ∪ . . .. Note that y is L-consistent, and for all formulas ϕ, if y ∪ { ϕ} is L-consistent, then ϕ ∈ y . By the Lindenbaum Lemma, there exists a maximal L-consistent set y such that y ⊆ y . Since y ⊇ x + , then by Claim 2, xR → y .

Given v ∈ R(y ) and R(v) ⊆ R(y ), let us show that R(y ⊆ R(v). So we assume t ∈ R(y ) and show that vRt. For this we further assume ϕ ∈ v and show that ϕ ∈ t. Since v is a world in R(x) such that R(v) ⊆ R(x), we have y ⊆ v. In fact, note that x ⊆ v since xRv; all other formulas in y are of the form ψ, and ψ ∈ y ⊆ y implies y ψ, and thus v ψ

Hence y ∪ { ϕ} is an L-consistent set of formulas, and thus ϕ ∈ y by our construction. Therefore ϕ ∈ y . Since y Rt, we eventually obtain

In fact, let z, t be worlds in R(y ) such that z = t. Then there exists a formula ϕ ∈ z such that ϕ ∈ t. Thus u = (y ) + ∪ {3ϕ → ϕ} is an L-consistent set of formulas. For otherwise there exists formulas ϕ 1 , . . . , ϕ m+n such that ϕ 1 , . . . , ϕ m+n ∈ y and

So ϕ ∧ ϕ is in y . On the other hand, by [START_REF] Van Benthem | A note on modal formulae and relational properties[END_REF] and classical logic

Suppose z ∈ W 2 . Then R(z) ∪ {z} ⊆ R(y). So yR → z and z = y. Consequently R → (y) ⊆ {y}: a contradiction.

Hence z ∈ W 1 , i.e. z = y, and so R(z) ⊆ {y}. Since y ∈ R → (x) ⊆ R(x), y is a final world in R(x).

Fmp and decidability

THEOREM 18. L fw 2 has the fmp and therefore is decidable.

Proof. Given an L fw 2 -consistent formula ϕ, let us show that ϕ is satisfiable in some finite frame from C fw ω . Let M = (W, R, V ) be the canonical model for L fw 2 . Then M, x 0 ϕ for some x 0 ∈ W and (W, R) ∈ C fw ω by Theorem 11. Let W f be the set of all final worlds in M. Take a new proposition letter q ∈ cl(ϕ), and let U be a valuation such that for all p ∈ cl(ϕ), U (p) = V (p), and U (q) = W f . For N := (W, R, U ) we obviously have N , x 0 φ.

Let N = (W , R , U ) be the minimal filtration of N through Ψ = cl(ϕ)∪ {q}. Recall that W is the quotient set under the equivalence relation

x ∼ y iff the same formulas from Ψ are true at N , x and N , y,

where x denotes the class of x modulo ∼. So N is finite, and N , x 0 ϕ, by the Filtration Lemma.

Let us show that (W , R ) ∈ C fw ω . Consider x ∈ W . Since (W, R) ∈ C fw ω , there exists y ∈ W f ∩ R(x). Then xR y. Suppose yR z, so y 1 Rz 1 for some y 1 ∈ y, z 1 ∈ z. Since y ∈ W f we have N , y q, so N , y 1 q and y 1 ∈ W f . Hence

Every world can see a deterministic world

In our second example, we put ϕ := 3p 1 → p 1 . Let

for n ≥ 0. Note that L dw 0 is nothing but K + 3 , and

is the class of all frames F = (W, R) with the following property:

• for all worlds x in W , there exists a world y in R(x) such that card(R(y)) = 1, i.e., every world in W can see a deterministic world in F.

Let us also consider for n ≥ 1, the class C dw n of all frames F = (W, R) such that

• for all worlds x in W and for all sets W 1 , . . . , W n ⊆ W , there exists a world y in R(x) such that for all i in {1, . . . , n}, if R(y)

Let C dw 0 be the class of all serial frames. One can easily see that PROPOSITION 19.

Proof. Given a frame F = (W, R) ∈ C dw n , let us show that for any model M = (F, V ), for any x ∈ W we have M, x β n . Put W i := V (p i ). Then for some y ∈ R(x) we have: for all i in {1, . . . , n}, R(y

For the converse, suppose F L dw n and show that

From [START_REF] Goldblatt | The McKinsey-Lemmon logic is barely canonical[END_REF] it follows that L dw ω is not finitely-axiomatizable (this proof is based on constructions from [START_REF] Goldblatt | First-order definability in modal logic[END_REF], [START_REF] Goldblatt | The McKinsey axiom is not canonical[END_REF]).

It is well known that L dw 1 is not Δ-elementary; this was proved independently in [START_REF] Van Benthem | A note on modal formulae and relational properties[END_REF] and [START_REF] Goldblatt | First-order definability in modal logic[END_REF]; a proof can also be found in [START_REF] Blackburn | Modal Logic[END_REF]. Next, [START_REF] Goldblatt | The McKinsey-Lemmon logic is barely canonical[END_REF] proves that L dw ω is not Δ-elementary (and thus certainly C dw ω = Fr(L dw ω )). Let us now prove the following generalization of this fact:

Proof. The main idea is the same as in [START_REF] Van Benthem | A note on modal formulae and relational properties[END_REF]. First, for any Kripke model M and n ≥ 1 we define the relation

Clearly, ≡ M n is an equivalence relation on M, and the quotient set W/ ≡ M n is finite. By a straightforward argument,

Now let us define a certain frame F = (W, R). For a countable set Z = {z i | i ∈ N}, take the uncountable set

Complexity

It is well-known that all logics between K and S4 are PSPACE-hard [START_REF] Ladner | The computational complexity of provability in systems of modal logic[END_REF]. This result can be easily extended to all logics between K and S4 + 3p → 3 p (see e.g. [START_REF] Shapirovsky | On PSPACE-decidability in transitive modal logics[END_REF]). Thus L fw 2 , L dw ω are PSPACE-hard. PSPACE-decidability of the logics L fw 2 , L dw ω was recently obtained by the first author, the proof will be published in the sequel.

Conclusion

Stepping aside from a familiar field leads us to various nontrivial questions. We hope to address some of them in the second part of this paper. Let us only mention several topics for further study.

1. We see that L 3 (ϕ) (for a Sahlqvist formula ϕ) is sometimes finitely axiomatizable. Does there exist a reasonable criterion (or at least a sufficient condition) for that?

2. Basing on his investigation in first-order modal logic, Sergei Astretsov (Moscow State University) proposed the following conjecture: L 3 (ϕ) is finitely axiomatizable iff it is elementary. This conjecture is consistent with the three examples from the present paper.

3. Does the fmp always transfer from K + ϕ to L 3 (ϕ)? 4. What are the properties of L 3 (ϕ) for well-known formulas ϕ, such as transitivity, non-branching, symmetry? As for transitivity, there is some progress: recently Stanislav Kikot (Moscow State University) has proved that C 3 ( p → 2 p) is not modally definable. This leads to another question: does the elementarity of L 3 (ϕ) imply the modal definability of C 3 (ϕ)? Note that the converse is rather trivial, see the proof of Corollary 22.

5. The logics L 3 (ϕ) are not Δ-elementary for ϕ = p → p, p → p. What happens to other non-elementary logics L 3 (ϕ) from Theorem 3? Note that according to a result by Van Benthem [START_REF] Van Benthem | Modal logic and classical logic[END_REF], every finitely axiomatizable Δ-elementary modal logic is elementary.

6. Note that Theorem 21 on non-elementarity of "approximants" L n 3 (ϕ) holds for KM ∞ , but its analogue fails for Hughes' logic L 3 ( p → p), since L 1 3 ( p → p) = K + p → 3p is axiomatized by a Sahlqvist formula. What happens in the general case -is it true that if L 3 (ϕ) (for a Sahlqvist ϕ) is non-elementary, then L n 3 (ϕ) are also non-elementary for sufficiently large n?

7. Is it true that all the logics L n 3 (ϕ) are complete (again for a Sahlqvist ϕ)? We do not know this even for simple cases, like n = 2, ϕ = p → p.

8. Is it possible to extend the result on non-canonicity of approximants for L 3 (ϕ) by Goldblatt-Hodkinson [START_REF] Goldblatt | The McKinsey-Lemmon logic is barely canonical[END_REF] to a larger class of logics L 3 (ϕ)? What about noncompactness (for the McKinsey axiom this was established in [START_REF] Wang | The McKinsey axiom is not compact[END_REF])?

9. What happens in the transitive case? More exactly, consider logics of the form K4 + L 3 (ϕ) for locally elementary and locally d-persistent ϕ. Our


Song Duong

Alberto Lumbreras

Mike Gartrell

Patrick Gallinari

Learning from Multiple Sources for Data-to-Text and Text-to-Data

Data-to-text (D2T) and text-to-data (T2D) are dual tasks that convert structured data, such as graphs or tables into fluent text, and vice versa. These tasks are usually handled separately and use corpora extracted from a single source. Current systems leverage pre-trained language models fine-tuned on D2T or T2D tasks. This approach has two main limitations: first, a separate system has to be tuned for each task and source; second, learning is limited by the scarcity of available corpora. This paper considers a more general scenario where data are available from multiple heterogeneous sources. Each source, with its specific data format and semantic domain, provides a non-parallel corpus of text and structured data. We introduce a variational autoencoder model with disentangled style and content variables that allows us to represent the diversity that stems from multiple sources of text and data. Our model is designed to handle the tasks of D2T and T2D jointly. We evaluate our model on several datasets, and show that by learning from multiple sources, our model closes the performance gap with its supervised singlesource counterpart and outperforms it in some cases. 1

INTRODUCTION

Data-to-text (D2T) [START_REF] Kukich | Design of a knowledge-based report generator[END_REF][START_REF] Mckeown | Text Generation. Studies in Natural Language Processing[END_REF] is the task of converting structured data into fluent text. This generic task is involved in several applications: generating Figure 1: The same content can be represented by different structures and by different texts. We show here an example from the E2E dataset [START_REF] Dušek | Semantic Noise Matters for Neural Natural Language Generation[END_REF]. On the left side, from top to bottom: knowledge graph, data record, meaning representation, and table .   summaries from patient records [START_REF] Scott | Data-to-text summarisation of patient records: Using computer-generated summaries to access patient histories[END_REF] or from tables such as summaries of sports games [START_REF] Wiseman | Challenges in datato-document generation[END_REF], generating product descriptions from databases in e-commerce [START_REF] Wang | A statistical framework for product description generation[END_REF], and so on. What makes this task different from conventional text generation is that structured data comes in many forms, e.g. web tables, databases, knowledge graphs, and so D2T systems have to handle these heterogeneous formats. Text vocabulary can also vary greatly from one domain to another, and systems need to adapt to this diversity as well (see Fig. 1). In addition, both modalities, text and data, are often noisy and incomplete, and in most practical situations there is no aligned corpus available, or at best small hand-crafted corpora. As a concrete example, consider the generation of product descriptions on an e-commerce website. Items can be described either as structured tables extracted from databases or as text. The former provides details of the characteristics of the items, while the latter summarises this information for the user. Information can be obtained from different providers and in different formats, also known as different sources [START_REF] Ng | Heterogeneous product description in electronic commerce[END_REF]. Even from the same arXiv: 2302.11269v1 [cs.LG] 22 Feb 2023 vendor, descriptions can vary widely depending on the product category (e.g. high-tech products and clothing). They may be quite noisy, such as unstructured sentences or series of keywords instead of a plain description, and in many cases only the text or data is available. In this case, the supervised formulation falls short, as we need to be able to use non-parallel data.

Text-to-data (T2D) is the dual task that aims at extracting relevant information from text and identifying their relations in order to generate structured data in a pre-defined format. Current T2D approaches are mainly limited to the conversion from text to graphs [START_REF] Ye | Contrastive triple extraction with generative transformer[END_REF][START_REF] Agarwal | Machine translation aided bilingual data-to-text genera-tion and semantic parsing[END_REF][START_REF] Paolini | Structured prediction as translation between augmented natural languages[END_REF]. Until now, both tasks have been handled separately through different methods.

Recent advancements in LLMs have enabled encoding various forms of information in text and viewing D2T and T2D as dual tasks within a unified framework. However, existing systems have primarily focused on simplified scenarios to meet these requirements:

(i) First, to the best of our knowledge, all models to date consider a single source for data and text, and deal with a data format and a text style as defined by the training corpus. However, in practice, one is faced with heterogeneous formats, where data is collected from multiple sources, each with its own specificity. This also holds for related NLP tasks including Question Answering (Chen et al., 2020b;[START_REF] Talmor | MultiQA: An empirical investigation of generalization and transfer in reading comprehension[END_REF][START_REF] Nan | FeTaQA: Free-form table question answering[END_REF] and Formal-Language-to-Text [START_REF] Shu | Logic-consistency text generation from semantic parses[END_REF]Chen et al., 2020c). This variety of data sources has led to the development of systems adapted to each case, resulting in architectures designed specifically for knowledge graphs [START_REF] Ke | JointGT: Graph-text joint representation learning for text generation from knowledge graphs[END_REF][START_REF] Zhao | Bridging the structural gap between encoding and decoding for data-to-text generation[END_REF], tables [START_REF] Liu | Tableto-text generation by structure-aware seq2seq learning[END_REF][START_REF] Rebuffel | Capturing Entity Hierarchy in Data-to-Text Generative Models[END_REF][START_REF] Cao | Generating natural language descriptions from tables[END_REF][START_REF] Liu | Hierarchical encoder with auxiliary supervision for neural table-to-text generation: Learning better representation for tables[END_REF], and so on. Recent work unifies multiple sources of structured data while considering a diversity of tasks, such as Structured Knowledge Grounding (SKG) [START_REF] Xie | Unifiedskg: Unifying and multi-tasking structured knowledge grounding with text-to-text language models[END_REF], by grounding both user requests and structured data in a common structured template.

(ii) Secondly, most models are trained in a supervised setting that requires the manual construction of aligned datasets. The latter are usually limited in size; for instance, one of the main D2T reference datasets, WebNLG (Gardent et al., 2017b), is composed of only 35,000 aligned pairs of text and knowledge graphs. Some recent works [START_REF] Jin | GenWiki: A dataset of 1.3 million content-sharing text and graphs for unsupervised graph-to-text generation[END_REF][START_REF] Lebret | Neural text generation from structured data with application to the biography domain[END_REF]Chen et al., 2021a) have proposed larger datasets, e.g., by collecting texts from Wikipedia and extracting knowledge graphs from DBPedia [START_REF] Lehmann | Dbpedia, a large-scale, multilingual knowledge base extracted from wikipedia[END_REF] or Wikidata [START_REF] Vrandečić | Wikidata: A free collaborative knowledgebase[END_REF]. However, as these text-graph pairs have been generated automatically, they are usually loosely aligned or simply nonparallel. Some works [START_REF] Schmitt | An unsupervised joint system for text generation from knowledge graphs and semantic parsing[END_REF]Guo et al., 2020b[START_REF] Guo | Fork or fail: Cycle-consistent training with many-to-one mappings[END_REF] have tackled the non-parallel setting in the presence of a single source of knowledge graphs. This paper considers the dual tasks of D2T and T2D within a unified formalism for multi-source conversion. We assume that structured data and texts are collected from multiple sources, with each source in a specific structured format. Our objective is to develop a unique system capable of performing conversion in both directions for a specified number of sources, where we convert data from a given source to text and, given a text, we convert it to any format from the set of targeted sources. With parameters shared between sources and tasks, the model can take full advantage of all sources, as opposed to systems trained on each source independently. We make the additional assumption that for training, data are collected from each source independently and are not aligned, i.e., there is no unique correspondence between a text and data. Given the difficulty of generating parallel datasets for D2T and T2D, this is a realistic scenario that allows us to leverage larger corpora in many practical situations. Note that even for aligned corpora, most of them are generated automatically, so the correspondence can be extremely loose. Compared to the usual single-source supervised or unsupervised settings, where a one-to-one mapping is assumed between text and data, we consider here a new problem corresponding to a many-to-many mapping between structured data and text: data comes from multiple heterogeneous sources, while text can express the same content in multiple ways.

Our contributions are the following:

• We frame D2T and T2D as two complementary sequence-to-sequence tasks that can be alternately optimized in an end-to-end, cycle-training fashion via iterative back-translation.

• We propose a latent variable model for handling multisource D2T and T2D through a shared model common to both tasks and to all the sources. Our approach is based on a pre-trained T5 language model [START_REF] Raffel | Exploring the limits of transfer learning with a unified text-to-text transformer[END_REF] and leverages the variational autoencoder (VAE) formulation.

• We evaluate our method on several D2T datasets. We show that by learning from multiple sources, our model closes the performance gap with its supervised singlesource counterparts on many datasets and even outperforms them on the DART dataset [START_REF] Nan | DART: Opendomain structured data record to text generation[END_REF]. This demonstrates the utility of learning from multiple heterogeneous sources in a unified way. Although, for practical reasons, our experiments have been conducted with the "T5-small" model, the results remain competitive with current stateof-the-art obtained with larger models on a portion of the datasets.

or using neural networks as part of a pipeline system [START_REF] Moryossef | Step-by-step: Separating planning from realization in neural data-totext generation[END_REF][START_REF] Ferreira | Neural data-to-text generation: A comparison between pipeline and end-to-end architectures[END_REF][START_REF] Puduppully | Data-to-text generation with content selection and planning[END_REF][START_REF] Laha | Scalable Micro-planned Generation of Discourse from Structured Data[END_REF]. In particular, using large pre-trained language models has been shown to greatly improve performance, either by simply framing data-to-text as a text-to-text task [START_REF] Kale | Text-to-text pre-training for datato-text tasks[END_REF], or by using a GNN-based planner for graph-to-text tasks [START_REF] Ribeiro | Investigating pretrained language models for graph-totext generation[END_REF][START_REF] Zhao | Bridging the structural gap between encoding and decoding for data-to-text generation[END_REF]Guo et al., 2020a). Current works mainly consider single-source problems. Some works have considered leveraging multiple sources, either by aggregating multiple structured datasets into a single-format dataset (Chen et al., 2020a;[START_REF] Nan | DART: Opendomain structured data record to text generation[END_REF], or by grounding user requests and structured data in a common structured template [START_REF] Xie | Unifiedskg: Unifying and multi-tasking structured knowledge grounding with text-to-text language models[END_REF].

Text-to-data (T2D). Converting unstructured text to structured data can be framed as a specific instance of (open) information extraction tasks, such as Named Entity Recognition (NER) [START_REF] Nadeau | A survey of named entity recognition and classification[END_REF][START_REF] Putthividhya | Bootstrapped named entity recognition for product attribute extraction[END_REF] or, more commonly, joint entity and relation extraction. Generally, given a text, the T2D task requires identifying the relevant entities and the relations between them, with the result being encoded as a triplet (Entity1, Relation, Entity2). Recent approaches consider the graph as a sequence of triples and cast the problem as a text-totext task. They typically combine an encoder with an autoregressive decoder [START_REF] Ye | Contrastive triple extraction with generative transformer[END_REF][START_REF] Agarwal | Machine translation aided bilingual data-to-text genera-tion and semantic parsing[END_REF][START_REF] Paolini | Structured prediction as translation between augmented natural languages[END_REF]. There has been less work on converting text to tables, although some recent approaches aim to generate tables from queries [START_REF] Gupta | JIGSAW: structuring text into tables[END_REF] in the information retrieval domain.

Cycle training with back-translation for unsupervised learning. Back-translation [START_REF] Cheng | Semi-supervised learning for neural machine translation[END_REF][START_REF] Cheng | Semi-supervised learning for neural machine translation[END_REF][START_REF] Cotterell | Explaining and generalizing back-translation through wake-sleep[END_REF] has been shown to be very effective in unsupervised machine translation [START_REF] Artetxe | Unsupervised neural machine translation[END_REF][START_REF] Lample | Unsupervised machine translation using monolingual corpora only[END_REF]. Given non-parallel samples (x, y) from a source and target language, this approach jointly learns two models (from one language to another and vice-versa) by leveraging cycle-consistencies x → ŷ → x and y → x → y. [START_REF] Lample | Unsupervised machine translation using monolingual corpora only[END_REF] identified a fundamental principle for successful backtranslation, namely that each model must be trained on a specific "language modeling objective to generate correct sentences in its language", i.e., each model must be able to capture the specifics of its own source domain.

Because of the duality of D2T and T2D, some works have framed both tasks as translation tasks between languages by linearizing the structured data. Following [START_REF] Lample | Unsupervised machine translation using monolingual corpora only[END_REF], [START_REF] Schmitt | An unsupervised joint system for text generation from knowledge graphs and semantic parsing[END_REF] introduced a denoising objective for graph-to-text, and apply iterative back-translation to train a single sequence-to-sequence model (LSTM with attention and a copy mechanism) to perform both graphto-text and text-to-graph. Guo et al. (2020b) also leveraged back-translation to perform unsupervised learning, but considered separate graph-to-text and text-to-graph compo-nents. The former component is based on a pre-trained language model and takes a linearized graph as input, while the latter component uses an off-the-shelf entity extraction model and simply learns a relation classification model to obtain the graph. This breaks the symmetry of the two tasks, and it seems that the denoising objectives of [START_REF] Schmitt | An unsupervised joint system for text generation from knowledge graphs and semantic parsing[END_REF] are no longer needed for backtranslation to succeed. A few recent works have incorporated cycle-consistent approaches for the semi-supervised setting. [START_REF] Domingo | A multi-task semi-supervised framework for text2graph & graph2text[END_REF] propose training a single T5 model for both graph-to-text and text-to-graph tasks, while [START_REF] Chang | Neural data-to-text generation with LM-based text augmentation[END_REF] proposes various data augmentation approaches and uses cycle consistency to ensure that the augmented data samples can be correctly reconstructed after having been formulated as text, and vice versa.

Variational framework for data-to-text. The variational autoencoder (VAE) [START_REF] Kingma | Auto-Encoding Variational Bayes[END_REF][START_REF] Rezende | Stochastic backpropagation and approximate inference in deep generative models[END_REF]) is a generative model capable of leveraging latent variables. [START_REF] Bowman | Generating sentences from a continuous space[END_REF] was the first to train a text VAE using an RNN encoder/decoder model, with KL annealing used to mitigate posterior collapse.

In the D2T literature, variational models are used to induce diversity or to enable more fine-grained control over text generation from data. [START_REF] Guo | Fork or fail: Cycle-consistent training with many-to-one mappings[END_REF] proposed a latent variable model to represent the diversity in text, allowing the model to learn a one-to-many mapping from the graph to the text domain. This approach performs both graph-to-text and text-to-graph tasks and uses the same standard NER component as in Guo et al. (2020b). [START_REF] Ye | Variational template machine for data-to-text generation[END_REF] proposed a variational model with disentangled content and style latent variables to perform the graphto-text task. Their semi-supervised algorithm is also inspired by back-translation but still requires some parallel data. For the table-to-text task, [START_REF] Wiseman | Learning neural templates for text generation[END_REF] modeled templates as a sequence of discrete latent variables and learns them using hidden semi-Markov models. [START_REF] Puduppully | Data-to-text generation with variational sequential planning[END_REF] proposed a variational approach to model latent plans in order to perform content planning in D2T generation. Chen et al. (2021b) introduced a VAE to model the causality of logical table-to-text as a latent variable.

PROBLEM DEFINITION

Multi-source scenario. We consider the scenario where we have multiple data sources at our disposal, and the data from each source are collected independently. Each source consists of a set of texts {x n } N n=1 and a set of singleformat structured data {y m } M m=1 . The formats of the different sources may be heterogeneous, e.g., tables of different types, graphs, etc. We consider structured data formats that can be represented or mapped to a set of relational triples (subject, relation, object), as is the case for graphs, data records, and tables (see Fig. 1).

D2T & T2D tasks. Our goal is to solve the D2T and T2D tasks. For the D2T task, we are given structured data from a source, and we seek to generate fluent text that explains the data. Conversely, for the T2D task, we are given a text and a target format indicator, and we aim to generate the corresponding structured data that summarize the text. We make the assumption that for D2T, multiple sentences can describe the same data, since there are many ways to verbalize a given piece of content. For T2D, given a target format, we assume that the mapping is unique since the content is uniquely encoded in the text.

Non-parallel setting. We study a general setting where each source consists of non-parallel sets of text and data, respectively:

(X N , Y M ) = {x n } N n=1 , {y m } M m=1 .
In other words, during training, we assume that the origin of the text and data is known, but their alignment is unknown. Our goal is to train a single system that can perform the conversion in both directions for all sources. We denote p src (x, y) as the unknown joint distribution of the text and data from a source. In a non-parallel setting, since we do not know the correspondence, the samples in the dataset (X N , Y M ) are assumed to come from the marginals, which are respectively p T and p D for the text and the data:

p T (x) = y p src (x, y)dy, (1)
p D (y) = x p src (x, y)dx. (2)
We assume that text and data are not statistically independent, i.e., p src (x, y) = p T (x)p D (y), so that it is possible to learn mappings p T (x|y) and p D (y|x) between the text and the data.

BACKGROUND: ITERATIVE BACK-TRANSLATION

Before delving into our proposed model in Section 5, in this section we formalize iterative back-translation, which is a fundamental part of our model derivation, and formally link our approach to the classical back-translation loss objective (Eq. 7). In the discussion that follows, we consider for simplicity a single-source objective. This is not limiting, since the multi-source problem amounts to solving several single-source problems with a shared model.

In the non-parallel setting, we do not have access to ground-truth parallel pairs (x, y) ∼ p src (x, y), which makes the learning of p T (x|y) and p D (y|x) difficult since we cannot directly maximize the conditional likelihoods.

We address this issue by introducing latent variables y andθ ( d) . We denote by θ n , we can express its log-likelihood using the missing data distribution p θ (d) (y

= [θ (t) , θ (d) ] x (t) n y (t) n θ (t) N x (d) m y (d) m θ (d) M
(t) n ) (see Appendix A.1) as log p θ (x (t) n ) = E p θ (d) (y (t) n ) [log p θ (t) (x (t) n |y (t) n )] + D KL (p θ (d) (y (t) n ) p θ (d) (y (t) n |x (t) n )). (3)
Likewise, the log-likelihood of any given data y

(d)
m can be obtained the same way using p θ (t) (x

(d) m ): log p θ (y (d) m ) = E p θ (t) (x (d) m ) [log p θ (d) (y (d) m |x (d) m )] + D KL (p θ (t) (x (d) m ) p θ (t) (x (d) m |y (d) m )). (4)
Given each equation, we do not know the distribution of the missing data p θ (d) (y

(t) n ) nor of the missing text p θ (t) (x (d) m
). An arbitrary choice of these distributions would lead to an arbitrary estimation of the mapping functions p θ (t) (x

(t) n |y (t) n ) and p θ (d) (y (d) m |x (d) m
). Instead, we follow the iterative back-translation scheme proposed in [START_REF] Hoang | Iterative back-translation for neural machine translation[END_REF] and consider that

p θ (d) (y (t) n ) = p θ (d) (y (t) n |x (t) n ), (5)
p θ (t) (x (d) m ) = p θ (t) (x (d) m |y (d) m ). (6)
From a probabilistic perspective, iterative back-translation can be seen as successively updating the posterior of the missing data (resp. text) using the conditional likelihood of the observed data (resp. data) from the other model component.

Note that under the iterative back-translation scheme, optimizing the log-likelihoods is equivalent to optimizing the cycle objective for unsupervised learning (see Appendix A.2) from prior work [START_REF] Hoang | Iterative back-translation for neural machine translation[END_REF]Guo et al., 2020b[START_REF] Guo | Fork or fail: Cycle-consistent training with many-to-one mappings[END_REF]:

L cycle (θ (t) , θ (d) ) = E p T (x) E p θ (d) (y|x) [log p θ (t) (x|y)] + E p D (y) E p θ (t) (x|y) [log p θ (d) (y|x)] . (7)
Figure 3: Graphical representation of our model. We augment the existing variables in Fig. 2 with additional latent variables s

(t)
n and s

(d)
m to capture the diversity in the text, and condition the generation of the structured data on the data format.

AUGMENTED LATENT VARIABLE MODEL FOR DATA-TO-TEXT AND TEXT-TO-DATA

Our model, shown in Fig. 3 and described below, is a refined version of the general scheme illustrated in Fig. 2. Because of the non-alignment assumption, the corresponding model leads to intractable expressions of the likelihood. Therefore, we use a variational autoencoder (VAE) [START_REF] Kingma | Auto-Encoding Variational Bayes[END_REF][START_REF] Rezende | Stochastic backpropagation and approximate inference in deep generative models[END_REF] to make learning and inference tractable.

Augmented Latent Variable Model

Probabilistic graphical model. In Section 3, we assumed that the content from structured data can be expressed in multiple ways, leading to different textual surface realizations. This is modeled by conditioning the text generation on a latent variable denoted s for style. We make use of two such variables, s

n and s m , as shown in Fig. 3. These style variables will be useful for modeling the diversity of texts -thus potentially allowing us to generate diverse texts from a single piece of data at inference time, and for modeling the uncertainty of the association between text and data during training. Similarly, we introduce a parameter, denoted f , that specifies the targeted conversion format for a text. Since the target format is available at both test and training time, this is a fixed parameter and not a latent one.

ELBO. We choose to leverage the VAE framework for our model. We show that the cycle-training objective can be deduced from the graphical model in a way that is similar to an iteration of the Wake-Sleep algorithm (see Appendix A.3) [START_REF] Cotterell | Explaining and generalizing back-translation through wake-sleep[END_REF]. Therefore, we derive the evidence lower bound (ELBO) equations for the text x and the structured data y as:

L x (θ (t) , φ) = E p θ (d) (ŷ|x;f ) E q φ (s|x) log p θ (t) (x|Enc φ (ŷ), s) -D KL (q φ (s|x) p(s)), (8)
L y (θ (d) , φ) = E p(s) E p θ (t) (x|y,s) log p θ (d) (y|Enc φ (x); f ) , (9)
where Enc φ is the sequence-to-sequence encoder used for learning representations of both text and data (see Section Content encoding).

Priors. We place a Gaussian prior over the style of the text,

p(s (t) n ) = p(s (d) m ) = N (0, I).
Since we want to incorporate information from observed text and data into their corresponding latent variables, we follow the iterative back-translation scheme described in Section 4, Eqs. 5 and 6, and define the priors as

p θ (d) (x (d) m ) = p θ (d) (x (d) m |y (d) m ), (10)
p θ (t) (y (t) n ) = p θ (t) (y (t) n |x (t) n ). (11)
Variational posteriors. For the variational posterior of the style, we use different parameterizations for s m . We parameterize q φ (s

(t) n |x (t) n ) and q φ (s (d) m |y (d)
m ) with a family of Gaussian distributions:

q φ (s (t) n |x (t) n ) = N (µ φ (x (t) n ); Σ φ (x (t) n )), (12)
q φ (s (d) m |y (d) m ) = N (0, I). ( 13
)
Content encoding. We initially considered encoding the content stochastically using a family of Gaussian distributions as in [START_REF] Ye | Variational template machine for data-to-text generation[END_REF]. However, we found in preliminary experiments that considering the content as stochastic leads to a performance decrease, especially when regularizing with a Gaussian prior. Therefore, we follow a simpler approach and choose to encode the content c

(t)
n and c

(t) m deterministically by setting

c (t) n = Enc φ (y (t) n ); c (d) m = Enc φ (x (d) m ), (14)
where Enc φ is the encoder of the T5 model in our case.

Text-to-data inference. In order to infer data y from text x, we first pass a one-hot encoded data format vector f through a linear layer s f = W f f + b f , and then feed it along with the encoded content c = Enc φ (x) to the decoder to generate y ∼ p θ (y|c, s f ).

Data-to-text inference. Here we clarify how to infer text from data, i.e., p θ (x|y). During training, the text style latent code is encoded from the text distribution, which we Figure 4: Given an observed data y, we generate a synthetic text x (black path). We use the synthetic text to retrieve the corresponding style posterior q(s|x). We can now sample multiple style latent codes s (i) ∼ q(s (i) |x) and feed them into the decoder, along with the encoded content c = Enc(y), to generate texts with multiple styles

x (i) = Dec(c, s (i) ) (red path).
do not have at inference time. The usual way to infer text from data in this scenario is to sample from the prior, as the divergence term in the ELBO pushes the variational posterior to its respective prior. Empirically, we found that this sampling method is acceptable when the dimensionality of the latent code is low. However, in the case of a high-dimensional latent space, the model fails to learn. We suspect that this is due to the inherent discrete nature of text; the latent space of the VAE for text exhibits regions of low density and can contain multiple holes [START_REF] Xu | On variational learning of controllable representations for text without supervision[END_REF][START_REF] Li | On the latent holes of vaes for text generation[END_REF], leading to the generation of incoherent text when naively decoding a latent code sampled from the prior. This effect is stronger in our case, since we need to perform inference starting at the very beginning of training. This results in noisy and uninformative samples, and leads to the failure of iterative back-translation.

In order to stabilize the inference process, when optimizing for structured data y, instead of sampling from the prior, we choose to fix the style latent code during training to s = [0, ..., 0] (the mean of the Gaussian prior) in order to infer synthetic text via x ∼ p θ (x|c, s), where c = Enc φ (y).

At inference time, to mitigate the train-test discrepancy, we infer p θ (x|y) by first generating x ∼ p θ (x|c, s) with s = [0, ..., 0] and c = Enc φ (y), and then use this synthetic sample to generate the style latent code s ∼ q φ (s|x). We can then infer x ∼ p θ (x|c, s) (see Fig. 4).

Disentanglement. As we encode the style of the text and the content using the same encoder, it is likely that both variables are entangled. We introduce a way to control their degree of entanglement, since this may influence the performance of the model. One way to assess the level of disentanglement between two random variables X and Y is by computing their Mutual Information (MI), and disentangling X from Y is achieved by minimizing their MI. While some works have explicitly sought to minimize this quantity or an estimate of it [START_REF] Sanchez | Learning disentangled representations via mutual information estimation[END_REF]Cheng et al., 2020a,b;[START_REF] Colombo | A novel estimator of mutual information for learning to disentangle textual representations[END_REF], other works [START_REF] Wang | Style tokens: Unsupervised style modeling, control and transfer in end-to-end speech synthesis[END_REF][START_REF] Chang | Style equalization: Unsupervised learning of controllable generative sequence models[END_REF] have simply chosen to introduce a bottleneck on the capacity of the style encoder, constraining the dimensionality of one of the two variables in order to limit the information flow from one variable to the other, also known as the content leakage phenomenon [START_REF] Hu | Unsupervised style and content separation by minimizing mutual information for speech synthesis[END_REF]. We follow the latter approach and show (see Appendix. A.4) that we can upper-bound the MI between the content and the style variables with a bound that scales with the dimension of the style of the text and the structured data format variables.

Training Algorithm 1: Cycle-training via back-translation

Input: d) , format f , Decoder θ, Encoder φ while not converged do

X (t) , Y (
(x, y) ∼ X (t) , Y (d) // Denoising objectives ∇(θ, φ) ← ∇ (θ,φ) L denoising (θ, φ) (Eq. 15) // T2D (y → x → y) s ∼ N (0, I) (or s ← [0, ..., 0]) x ∼ p θ (x | y, s) / * no gradient * / c ← Enc φ (x) ∇(θ, φ) ← ∇(θ, φ) + ∇ (θ,φ) L y (θ, φ) (Eq. 9) // D2T (x → ŷ → x) ŷ ∼ p θ (y | x, f ) / * no gradient * / c ← Enc φ (ŷ) ∇(θ, φ) ← ∇(θ, φ) + ∇ (θ,φ) L x (θ, φ) (Eq. 8) // Update (θ, φ) ← (θ, φ) + ∇(θ, φ) end
One potential danger that can arise when only optimizing the cycle objective is a collapse onto the trivial identity mapping, which may happen when the source and target domains are the same. We encounter this phenomenon due to our linearization of the structured data, where we implicitly frame the D2T and T2D tasks as translation tasks. Learning the trivial identity mapping for both tasks is one way to locally maximize the objective. To remedy this issue, [START_REF] Lample | Unsupervised machine translation using monolingual corpora only[END_REF] and [START_REF] Schmitt | An unsupervised joint system for text generation from knowledge graphs and semantic parsing[END_REF] introduce denoising objectives, which make the model robust to noise. We follow the same methodology as [START_REF] Schmitt | An unsupervised joint system for text generation from knowledge graphs and semantic parsing[END_REF] and adapt their noise functions (swap, drop, blank, repeat, rule) for all structured data formats (see Appendix A.5 for examples).

In addition to the ELBO, we also optimize the following denoising objective:

L denoising (θ) = E x∼p T (x),x∼N oise(x) [log p θ (x|x)] + E y∼p D (y),ỹ∼N oise(y) [log p θ (y|ỹ)]. ( 15
)
Iterative back-translation leverages the use of synthetic samples. When optimizing for a text x, we sample synthetic data y ∼ p θ (d) (y|x), with θ (d) being fixed, and we do the same with θ (t) when optimizing for a structured data y.

Since we are jointly optimizing Eq. 8 and Eq. 9 using the same model θ = (θ t , θ d ), we accumulate gradients for text and data before updating the parameters of the model. Our method is described in Algorithm 1.

EXPERIMENTS

Datasets

We simulate a heterogeneous multi-source setting by considering a collection of D2T datasets. Each dataset uses a specific structured encoding. Since they are originally designed for a supervised setting, they are all aligned.

We simply remove this alignment information and consider each source as a set of text and structured data.

All the datasets are available from the GEM Benchmark [START_REF] Gehrmann | The GEM benchmark: Natural language generation, its evaluation and metrics[END_REF]. Due to the heterogeneous sizes of these datasets, we use a temperature mixing of T = 2, as in [START_REF] Raffel | Exploring the limits of transfer learning with a unified text-to-text transformer[END_REF], to train our models in the multi-source setting.

WebNLG 2020 (English) [START_REF] Ferreira | The 2020 bilingual, bi-directional webnlg+ shared task overview and evaluation results (webnlg+ 2020)[END_REF]) is a dataset composed of 35,426 pairs of knowledge graphs and text crawled from 15 categories of DBpedia. This is followup work from the WebNLG 2017 challenge (Gardent et al., 2017b).

Cleaned E2E [START_REF] Dušek | Semantic Noise Matters for Neural Natural Language Generation[END_REF] results from cleaning the original E2E NLG dataset [START_REF] Novikova | The E2E dataset: New challenges for end-to-end generation[END_REF], an English benchmark dataset for data-to-text models that verbalizes a set of 2-9 key-value attribute pairs in the restaurant domain. The cleaned version has filtered out examples with hallucinations and outputs that do not fully cover all input attributes.

DART [START_REF] Nan | DART: Opendomain structured data record to text generation[END_REF] is an English dataset composed of 62,659 parallel text-data pairs, which aggregates multiple data-to-text datasets, including E2E and WebNLG, into a common format called data records. These data records consist of sets of triples and can be seen as a flat representation of the graph structure.

ToTTo [START_REF] Parikh | ToTTo: A controlled table-to-text generation dataset[END_REF]) is a high-quality English tableto-text dataset with more than 120,000 examples, where each example is composed of a table from Wikipedia with highlighted cells that is paired with a sentence that describes these cells. All examples in this dataset were postedited in multiple steps to ensure that the targets are fully faithful to the input information.

Baselines

We consider the following baselines for our experiments (MS holds for multi-source, SS for single-source):

MS-Sup: This pre-trained T5 model is fine-tuned on all datasets in a multi-source, supervised setting. We train a separate model for D2T and T2D. For T2D, we consider one prefix for each format and train in a multi-task fashion.

SS-Sup:

This pre-trained T5 model is fine-tuned on each dataset independently and is supervised. We train a separate model for D2T and T2D.

MS-UnSupVAE: Our approach.

SS-UnSupVAE:

This model is a single pre-trained T5 model fine-tuned on each dataset separately for both D2T and T2D. This approach is close to the one in [START_REF] Guo | Fork or fail: Cycle-consistent training with many-to-one mappings[END_REF], but they use separate models for D2T and T2D and additional preprocessing for T2D.

MS-UnSup:

This pre-trained T5 model is fine-tuned on all datasets in a multi-source, unsupervised setting. We consider a prefix for each format and train a single model for both D2T and T2D in a multitask fashion.

SS-UnSup:

This model uses a pre-trained T5 model on each dataset separately for both D2T and T2D. This is comparable to [START_REF] Schmitt | An unsupervised joint system for text generation from knowledge graphs and semantic parsing[END_REF], which uses a BiLSTM-LSTM architecture as the encoder-decoder instead of a T5 model in our case.

Note that because of limited resources, we conducted all of our experiments using the T5-small model. However, we will see that for some experiments we reach the performance of state-of-the-art T5-large models.

Evaluation metrics

D2T metrics. We assess traditional metrics in our experiments, including BLEU [START_REF] Papineni | Bleu: a method for automatic evaluation of machine translation[END_REF][START_REF] Post | A call for clarity in reporting BLEU scores[END_REF], ROUGE-L [START_REF] Lin | ROUGE: A package for automatic evaluation of summaries[END_REF], and METEOR [START_REF] Banerjee | METEOR: An automatic metric for MT evaluation with improved correlation with human judgments[END_REF][START_REF] Denkowski | Meteor universal: Language specific translation evaluation for any target language[END_REF].

T2D metrics. Little has been established in the literature for the evaluation of generated structured data. We follow the same approach as prior works on text-to-graph (Guo et al., 2020b[START_REF] Guo | Fork or fail: Cycle-consistent training with many-to-one mappings[END_REF][START_REF] Schmitt | An unsupervised joint system for text generation from knowledge graphs and semantic parsing[END_REF] and report the precision, recall, and f1 score of predicted entities and relations for all formats. In addition to these metrics, we also compute the SemBLEU score [START_REF] Song | SemBleu: A robust metric for AMR parsing evaluation[END_REF] by converting all formats into a graph structure. This score, which is adapted to the structure of graphs, provides more information on higher-order n-grams than previous entity and relation scores.

Diversity metrics. Since our model has the ability to generate diverse texts from the same data, it is important to assess the effectiveness of this mechanism. We evaluate the diversity of the generated texts in our experiments using the Self-BLEU metric [START_REF] Zhu | Texygen: A benchmarking platform for text generation models[END_REF], which treats one generated sentence as the hypothesis and the others as the reference, and calculates the BLEU score for every set of generated sentences. The score is then averaged over the test set. We also report Distinct-1 and Distinct-2 (Li , 2016), which corresponds to the number of distinct unigrams and bigrams in generated texts. This metric is then scaled by the total number of generated tokens, which penalizes long sentences.

Results

We present some of our results in Table 1. A more complete list of results can be found in Table 2 (Appendix).

D2T. (i) Supervised vs Unsupervised. The supervised model MS-Sup, which is effectively an upper bound on model performance, performs the best as expected. (ii) Single source vs multi-source. Except for E2E, multisource models always outperform their single-source counterparts. Learning from multiple sources improves performance across datasets. Since the E2E dataset is a very specific, small, and closed domain (restaurant) dataset, training on multiple domains may introduce interference. (iii) VAE vs non VAE. For the multi-source setting, the VAE version MS-UnSupVAE always outperforms its non-VAE counterpart MS-UnSup by a significant margin. This result highlights the importance of uncertainty modeling when the conversion problem becomes more challenging, as is the case for multi-source vs single-source scenarios. (iv) Unsupervised models. Except on E2E, where all models have similar performance, our model outperforms all other unsupervised approaches across all metrics, and closes the performance gap with the supervised baselines. Note that MS-UnSupVAE is particularly effective on DART, outperforming even the single-source supervised baselines and current state-of-the-art obtained with larger models (see Appendix 2). We attribute this performance to the multisource nature of DART. By flattening knowledge graphs into sets of triples, the data records in DART have lost information that was present in the original data. Overall, it appears that training on heterogeneous formats that originate from the same content improves model performance.

Figure 5: Evolution of average BLEU, Distinct-1, Distinct-2 (higher is better), and self-BLEU (lower is better) metrics over all datasets as the dimensionality of the style increases.

T2D. First, we notice that using a text-to-text model for T2D results in some format errors, although they are not frequent (less than 5% for all datasets). Training on multiple sources is challenging for the T2D task, as it also increases format errors due to the consideration of several formats, such as for the MS-Sup model on the E2E dataset. Compared to their supervised counterparts, all unsupervised approaches underperform on entity and relation extraction. Nevertheless, our model remains competitive with the other supervised baselines.

Diversity Results. We jointly evaluate the diversity and quality of the text generated by our model as the dimension of the style latent variable varies. Due to the stochasticity of text generation, we report the mean and 95% confidence intervals for the diversity metrics and the BLEU metrics (quality) for 10 different random seeds. We average the metrics over all datasets. We observe that increasing the dimensionality of the style vector increases the Distinct-(1,2) scores, i.e., the number of unigrams and bigrams increases.

The generated sentences are also more diverse, since Self-BLEU decreases. It appears that there is little variation in the generation when the style dimensionality is fairly low (less than 16). As the dimensionality increases, however, the model tends to hallucinate, as the BLEU metrics generally decrease (see more examples in Appendix A.7).

ASSUMPTIONS AND LIMITATIONS

One limitation of our work is that we have considered sources with structured data formats that can be mapped to sets of relational triples. The treatment of more diverse structured formats and tasks remains an open problem. A second limitation concerns the diversity in the text domain and in the relation types considered in different corpora.

Although our model behaves well on sources with different text domains and relations, the types of relations remain relatively simple, typical of the benchmarks in this domain, and extension to more complex situations is challenging. A potentially limiting assumption concerns our non-parallel framework for D2T and T2D. Although we remove alignment from the data by breaking aligned pairs, the domains of the two modalities remain aligned, which differs from the non-parallel framework considered in machine translation [START_REF] Lample | Unsupervised machine translation using monolingual corpora only[END_REF], where no alignment is assumed. This is due to the lack of large open-domain D2T datasets.

CONCLUSION

We have proposed a model capable of learning D2T and T2D mappings in a non-parallel setting, where text and data come from multiple sources. Our experiments show that the model is able to leverage this diversity to provide improved performance compared to unsupervised baselines. Our results suggest that mixing multiple formats can potentially improve model performance in both the parallel and non-parallel setting. The advantage of our method lies in its applicability to more realistic problems, where the data is heterogeneous, or where a strict match between text and data cannot be found. A promising avenue for future work would be to consider the adaptation to scenarios where new sources with scarce data are made available, requiring fewshot learning capability.

A APPENDIX

A.1 Log-likelihood of the Latent Variable Model Given any arbitrary observed text x (t) n , we can express its log-likelihood using the missing data distribution p θ (d) (y

(t) n ) as log p θ (x (t) n ) = E p θ (d) (y (t) n ) [log p θ (x (t) n )] = E p θ (d) (y (t) n ) log p θ (t) (x (t) n |y (t) n )p θ (d) (y (t) n ) p θ (d) (y (t) n |x (t) n ) = E p θ (d) (y (t) n ) [log p θ (t) (x (t) n |y (t) n )] + D KL (p θ (d) (y (t) n ) p θ (d) (y (t) n |x (t) n )). (16)
Likewise, given any observed data y

(d)
m , for any arbitrary density p θ (t) (x

(d) m ) we have log p θ (y (d) m ) = E p θ (t) (x (d) m ) [log p θ (d) (y (d) m |x (d) m )] + D KL (p θ (t) (x (d) m ) p θ (t) (x (d) m |y (d) m )). (17)
A.2 Connection between the Cycle Objective and the Log-likelihood

We use the following notation:

X (t) = {x (t) 1 , ..., x (t)
N } and

Y (d) = {y (d) 1 , ..., y (d)
M } are the sets of observed texts and structured data, respectively.

X (d) = {x (d) 1 , ..., x (d) N } and Y (t) = {y (t) 1 , ..., y (t)
M } are the sets of missing texts and structured data, respectively. We denote by θ = (θ (t) , θ (d) ) the set of parameters of the generative model. Considering the probablistic graphical model (PGM) in Fig. 2, we have

log p θ (X (t) , Y (d) ) = N log p θ (t) (x (t) n ) + M log p θ (d) (y (d) m ) ≈ N E x (t) n ∼p T (x) [log p θ (t) (x (t) n )] + M E y (d) m ∼p D (y) [log p θ (d) (y (d) m )] (18) = N E x (t) n ∼p T (x) E p θ (d) (y (t) n ) [log p θ (t) (x (t) n |y (t) n )] + D KL (p θ (d) (y (t) n ) p θ (d) (y (t) n |x (t) n )) + M E y (d) m ∼p T (y) E p θ (t) (x (d) m ) [log p θ (t) (y (d) m |x (d) m )] + D KL (p θ (t) (x (d) m ) p θ (t) (x (d) m |y (d) m ))] (19)
Iterative back-translation gives us the following:

p θ (d) (y (t) n ) = p θ (d) (y (t) n |x (t) n ), (20)
p θ (t) (x (d) m ) = p θ (t) (x (d) m |y (d) m ). (21)
Under these assumptions, the KL terms D KL (p θ (t) (x

(d) m ) p θ (t) (x (d) m |y (d) m )) and D KL (p θ (d) (y (t) n ) p θ (d) (y (t) n |x (t) n ))) vanish. In addition, if N = M , then argmax θ log p θ (X (t) , Y (d) ) ≈ argmax (θ (t) ,θ (d) ) E x (t) n ∼p T (x) E p θ (d) (y (t) n |x (t) n ) [log p θ (t) (x (t) n |y (t) n )] + E y (d) m ∼p T (y) E p θ (t) (x (d) m |y (d) m ) [log p θ (t) (y (d) m |x (d) m )] = argmax (θ (t) ,θ (d) ) L cycle (θ (t) , θ (d) ) (22)
Thus, optimizing the cycle objective amounts to optimizing the log-likelihood.

This resonates with [START_REF] Cotterell | Explaining and generalizing back-translation through wake-sleep[END_REF], who interpreted iterative back-translation as iterations of the Wake-Sleep algorithm, where one alternatively learns a forward model p θ (y|x) and a variational approximation q φ (y|x). The only difference here is that we only consider the wake phase and choose to skip the sleep phase by assuming that Eqs. 33 and 34 hold. This assumption may be rather strong, but can be justified in the iterative back-translation framework, since both models p θ (t) (x|y) and p θ (d) (y|x) are optimized to approximate the true conditional distributions p T (x|y) and p D ((y|x), in alternate steps. Under these assumptions, the KL terms D KL (q φ (y

(t) n |x (t) n ; f ) p θ (d) (y (t) n ; f )) and D KL (q φ (x (d) m |y (d) m ) p θ (t) (x (d)
m )) vanish. This results in these tractable bounds:

L x (t) n (θ (t) , φ) ≈ E p θ (d) (y (t) n |Enc φ (x (t) n );f ) E q φ (s (t) n |x (t) n ) [log p θ (t) (x (t) n |s (t) n ; Enc φ (y (t) n ))] -D KL (q φ (s (t) n |x (t) n ) p(s (t) n )), (35) L y (d) m (θ (d) , φ) ≈ E p(s (d) m ) E p θ (t) (x (d) m |s (d) m ,Enc φ (y (d) m )) [log p θ (d) (y (d) m |Enc φ (x (d) m ); f )] . (36)
Note that synthetic samples y

(t) n ∼ p θ (d) (y (t) n |Enc φ (x (t) n ); f ) and x (d) m ∼ p θ (t) (x (d) m |s (d) m , Enc φ (y (d) m
)) used for backtranslation are computed without gradients. When optimizing for θ (t) , the parameters θ (d) resulting from the computation of x (d) m are not updated, and vice-versa.

A.4 Disentanglement through constraining the amount of information in style variables

Some works have defined a measure of disentanglement between two random variables X and Y as the Mutual Information (MI) between the two:

I(X; Y ) = E p(X,Y ) log p(X, Y ) p(X)p(Y ) = H(X) -H(X|Y ) = H(Y ) -H(Y |X)
From a MI perspective, disentangling X from Y is achieved by minimizing their MI. While some works have explicitly sought to minimize this quantity or an estimate of it [START_REF] Sanchez | Learning disentangled representations via mutual information estimation[END_REF]Cheng et al., 2020a,b;[START_REF] Colombo | A novel estimator of mutual information for learning to disentangle textual representations[END_REF], other works [START_REF] Wang | Style tokens: Unsupervised style modeling, control and transfer in end-to-end speech synthesis[END_REF][START_REF] Chang | Style equalization: Unsupervised learning of controllable generative sequence models[END_REF] have simply chosen to introduce a bottleneck on the capacity of the style encoder, constraining the dimensionality of one of the two variables in order to limit the information flow from one variable to the other. For completeness, we show here that by constraining the dimensionality of s, we can upper-bound the mutual information between the content c and the style variables with a function that scales with the dimensionality.

• For the style of the text, from the definition of MI, as the entropy is always positive, we can upper-bound it by:

I(s; c) ≤ H(s) = H(N (0, I)) = d 2 (1 + log(2π)) + 1 2 log |I| = d 2 (1 + log(2π)), (37)
where d denotes the dimension of the multivariate Gaussian. Hence, by limiting the dimension of s, we prevent information flowing from the content variable c to s.

• For the format f , as it is a parameter, the entropy is 0:

I(f ; c) ≤ H(f ) = 0. (38)
Note that although these bounds are not tight, this motivates the use of a lower dimensional space to encode the style.

A.5 Examples from the "Rule" Noise Functions T2D Roadside Attractions distributed Super Capers which was also distributed by the public company Lionsgate.

KG: [HEAD] Attractions [TYPE] distributed [TAIL] Super [HEAD] also [TYPE] distributed [TAIL] public [HEAD] Adapting T5. We build our model around T5 [START_REF] Raffel | Exploring the limits of transfer learning with a unified text-to-text transformer[END_REF], which has an architecture that is close to the original Transformer architecture [START_REF] Vaswani | Attention is all you need[END_REF].

We fine-tune the pre-trained t5-small model to generate both text and data. We specify the target format by either adding the prefix "Generate text:" (for θ (t) ) or "Generate data:" (for θ (d) ) to the input sequence given to the encoder.

Encoder-Decoder architectures. For the text style encoder q φ (s|x), we add a special token "[STYLE]" to the text sequence that is passed to the encoder. We take the latent representation from the encoder output h(x), and add a linear layer to obtain the parameters of our variational distribution:

µ(x) = W µ h(x) + b µ Σ(x) = W Σ h(x) + b Σ
where q φ (s|x) = N (s; µ(x), Σ(x)).

For the structured data format f , we simply encode it using a linear layer via s f = W f f + b f , before feeding it along with the encoded content c = Enc φ (x) to the decoder.

KL Vanishing Issue. This issue, also known as KL collapse, is a typical problem encountered when training VAE models.

Fitting the variational posterior to the prior ∀x, q φ (z|x) = p θ (z)) to get a zero KL divergence term at the beginning of training is a simple way to minimize the ELBO loss. This results in a local minimum where the decoder is capable of performing effectively without the latent variable, which is typically the case with large language models and autoregressive decoding [START_REF] Fu | Cyclical annealing schedule: A simple approach to mitigating KL vanishing[END_REF]. Many works have suggested fixes for this problem; we found the MMD-VAE approach [START_REF] Zhao | Infovae: Information maximizing variational autoencoders[END_REF] particularly effective.

In practice, the MMD-VAE approach replaces the KL divergence term D KL (q φ (z|x) p θ (z)) with a sample estimate of the Maximum-Mean Discrepancy (MMD) measure between the aggregated posterior q φ (z) = E x∼p T (x)

[q φ (z|x)] and the prior p θ (z). We also experimented with the β-VAE and the cyclical schedule proposed in [START_REF] Fu | Cyclical annealing schedule: A simple approach to mitigating KL vanishing[END_REF] and used in [START_REF] Li | Optimus: Organizing sentences via pre-trained modeling of a latent space[END_REF], but preliminary experiments were not as successful.

Hyperparameters All models have been trained with the AdamW [START_REF] Loshchilov | Decoupled weight decay regularization[END_REF] optimizer with a learning rate of 10 -4 for 10 epochs. Following [START_REF] Lample | Unsupervised machine translation using monolingual corpora only[END_REF] and [START_REF] Schmitt | An unsupervised joint system for text generation from knowledge graphs and semantic parsing[END_REF], we set p blank = p repeat = 0.2, p drop = 0.1, and use all 5 noise functions swap, drop, blank, repeat, and rule. For inference, we use beam search decoding

  m , corresponding respectively to the unobserved ground-truth pair or missing pair for our observed text x (t) n and data y (d) m , as shown in Fig 2. Our goal is to learn the densities p T (x|y) and p D (y|x), which we parameterize respectively with θ (t)

Figure 2 :

 2 Figure 2: Graphical representation of the unsupervised setting where aligned pairs are not available.

  in the former case we have access to observed text x (t) n , while for the latter there is no style information in the observed y(d)

D2T[

  HEAD] Nord (Year of No Light album)[TYPE] artist[TAIL] Year of No Light[HEAD] Nord (Year of No Light album)[TYPE] genre[TAIL] Post-metal[HEAD] Nord (Year of No Light album) [TYPE] record label [TAIL] Crucial Blast --> Nord (Year of No Light album) artist Year of No Light and Nord (Year of No Light album) record label Crucial Blast and Nord (Year of No Light album) genre Post-metal ARA Veinticinco de Mayo (V-2) : length : 192000.0 (millimetres) | ARA Veinticinco de Mayo (V-2) : country : Argentina --> ARA Veinticinco de Mayo (V-2) length 192000.0 (millimetres) and ARA Veinticinco de Mayo (V-2) country Argentina name[The Phoenix], eatType[pub], food[French], priceRange[more than £30], customer rating[5 out of 5], area[riverside], familyFriendly[no], near[Crowne Plaza Hotel] --> The Phoenix eatType pub and The Phoenix priceRange more than £30 and The Phoenix area riverside and The Phoenix near Crowne Plaza Hotel and The Phoenix name The Phoenix and The Phoenix customer rating 5 out of 5 and The Phoenix food French and The Phoenix familyFriendly no <page_title> Gennady Golovkin vs. Daniel Jacobs </page_title> <section_title> CompuBox stats </section_title> <table> <cell> Golovkin <col_header> Fighter </col_header> </cell> <cell> 231/615 <col_header> Total punches </col_header> </cell> <cell> Jacobs <col_header> Fighter </col_header> </cell> <cell> 175/541 <col_header> Total punches </col_header> </cell> </table> --> Gennady Golovkin vs. Daniel Jacobs and CompuBox stats and Golovkin Fighter and 231/615 Total punches and Jacobs Fighter and 175/541 Total punches A.6 Implementation details

Table 1 :

 1 Evaluation results for D2T and T2D

				DART		WEBNLG		E2E		TOTTO
				BLEU	METEOR	BLEU	METEOR	BLEU	METEOR	BLEU	METEOR
		MS-Sup		52.613	38.29	52.037	35.85	40.679	35.3	44.196	37.32
		SS-Sup		45.163	35.91	50.502	35.58	40.95	35.43	43.74	37.08
		MS-UnSupVAE (ours)	51.074	37.47	49.575	34.3	39.33	34.94	36.793	36.11
		SS-UnSupVAE	39.23	33.35	43.73	32.5	39.31	35.02	32.85	33.83
		MS-UnSup		48.435	36.2	45.172	31.72	39.529	34.95	35.129	34.92
		SS-Unsup		39.27	33.19	44.72	32.59	39.36	34.79	33.40	34.21
			DART			WEBNLG			E2E			TOTTO
		ENT F1	REL F1	SemBLEU	ENT F1	REL F1	SemBLEU	ENT F1	REL F1	SemBLEU	ENT F1	REL F1	SemBLEU
	MS-Sup	92.01	81.36	69.1	73.59	47.5	47.55	97.87	97.64	99.21	49.82	15.04	11.9
	SS-Sup	84.78	71.49	54.5	70.84	45.46	39.87	96.97	96.61	98.85	49.62	14.03	12.82
	MS-UnSupVAE (ours)	84.64	72.65	67.73	65.38	39.22	35.62	88.16	88	95.32	47.02	13.76	15.14
	SS-UnSupVAE	72.56	56.03	39.71	57.22	25.37	16.09	85.57	85.18	93.04	43.36	10.21	5.72
	MS-UnSup	80.74	67.69	56.6	60.45	33.73	26.97	86.44	86.13	95.08	44.95	11.92	10.19
	SS-Unsup	71.29	55.12	42.96	57.3	25.47	13.62	78.96	78.59	80.56	44.26	10.52	8.06
	et al.

The code is available at github.com/sngdng/ MSUnsupVAE.

Acknowledgements

The work has been partly funded through project ACDC ANR-21-CE23-0007. We would like to express our sincere thanks to Alexandre Thomas who did an internship at Criteo and whose work served as the foundation for this paper.

A.3 Derivation of the ELBO

We use the following notation: X (t) = {x M } are the set of latent variables that encode the styles of the text in X (t) and X (d) , respectively. f is the structured data format common to all Y (d) . We denote by θ = (θ (t) , θ (d) ) the set of parameters of the generative model and by φ the parameters of the variational posterior q φ . The joint likelihood of the model can be expressed as

Our goal is to maximize the marginal likelihood (evidence) p θ (X (t) , Y (d) ; f ) of the observed datasets. We can derive the Evidence Lower Bound (ELBO) as

Let us now factorize the different terms. Given the PGM in Fig. 3, the likelihood can be factorized as

The prior can be factorized as

And the variational posterior as

Note that Eq. 24 holds for any arbitrary q φ ; different factorizations of the variational posteriors are possible, for instance q φ (X (d) ,

), which would result in encoding the style with the synthetic text. We ran experiments with this variant and found that the model performs the best with Eq. 28.

Following Eqs. 26, 27, and 28, The ELBO can be factorized as

where each term can be written as Expected Outputs:

The coffee shop Blue Spice is based near Crowne Plaza Hotel and has a high customer rating of 5 out of 5.

The Blue Spice coffee shop, near Crowne Plaza Hotel, has a customer rating of 5 out of 5.

If you want a coffee shop rated 5 out of 5 pick Blue Spice. It is located near Crowne Plaza Hotel.

Generated Texts:

Blue Spice is a 5 star coffee shop located near Crowne Plaza Hotel that also serves fast food, not family-friendly. Blue Spice is a 5-star coffee shop located near Crowne Plaza Hotel that also offers food in moderate prices. Blue Spice is a coffee shop located near Crowne Plaza Hotel that offers great food, at reasonable prices. Blue Spice is a coffee shop located near Crowne Plaza Hotel that offers cheap food, but only has a 5 out of 5 rating. Blue Spice is a 5 star coffee shop located near Crowne Plaza Hotel that also serves food in cheap prices. Blue Spice is a coffee shop near Crowne Plaza Hotel that also offers great food, prices are rated 5 out of 5. Blue Spice is a 5-star coffee shop located near Crowne Plaza Hotel, that sells sushi for more than £30. Blue Spice is a coffee shop located near Crowne Plaza Hotel that sells cheap food, and rated 5 out of 5. Blue Spice is a 5-star coffee shop located near Crowne Plaza Hotel that serves Italian food, and has a price range of more than 30. Blue Spice is a coffee shop located near Crowne Plaza Hotel that also serves Japanese food, and has a 5 out of 5 rating.