Adel Alahmadi

Alaa Altassan
email: aaltassan@kau.edu.sa

Widyan Basaffar
email: whbasaffar@kau.edu.sa

Alexis Bonnecaze
email: alexis.bonnecaze@univ-amu.fr

Hatoon Shoaib
email: hashoaib@kau.edu.sa

Patrick Solé
email: sole@enst.fr

AA,WB Aa

Type IV codes over a non-unital ring

Keywords: rings, codes, additive codes, Type IV codes. MSC(2010): Primary 94 B05, Secondary 16 A10

come

Introduction

The rings of order 4 used as alphabets in coding theory are historically, and by order of importance, F 4 [START_REF] Macwilliams | The theory of error-correcting codes[END_REF], Z 4 [START_REF] Hammons | The Z 4 -linearity of Kerdock, Preparata, Goethals, and related codes[END_REF], F 2 + uF 2 [START_REF] Dougherty | Type II Codes Over F 2 + uF 2[END_REF], and F 2 × F 2 [START_REF] Steven | Type IV self-dual codes over rings[END_REF]. A quick look at the classification of finite rings of order 4 shows that these four rings above are exactly all the rings, amongst the list of 9 rings of order 4, that possess an identity element for the multiplication [START_REF] Fine | Classification of finite rings of order p 2[END_REF][START_REF] Raghavendran | A class of finite rings[END_REF]. More generally, in the abundant literature of codes over rings no non-unital ring has ever been used as alphabet [START_REF] Solé | Codes over Rings[END_REF][START_REF] Shi | Codes and Rings: Theory and Practice[END_REF].

In this paper, for the first time in the history of Coding Theory, codes over a non-unital ring are studied. This ring has order four, and is denoted by E in the classification of [START_REF] Fine | Classification of finite rings of order p 2[END_REF][START_REF] Raghavendran | A class of finite rings[END_REF]. The ring E turns out to be also noncommutative. Our original intention was to study self-dual codes over E. However, the usual relation between the size of the code and that of its dual does not hold in general (see the notion of nice code in the next section). This situation led us to introduce the notion of quasi self dual code (QSD), that is of an E-code of length n that is both self-orthogonal and of size 2 n . The aim of this paper is thus to study the structure of QSD codes. In particular we study a multilevel construction of a QSD code as a function of a pair of dual codes. Like in the case of other local rings of order 4, the notions of residue and torsion codes are fundamental [START_REF] Conway | Self-dual codes over the integers modulo four[END_REF]. They lead in particular, to a canonical form for the generator matrix of any E code of given residue and torsion codes dimensions. However, the characterization of Theorem 6 of a QSD code as a multilevel construction from its residue and torsion code would not be true over the four commutative rings of order 4. This characterization is strong enough to allow us to characterize Type IV codes by their residue code, and to classify them in short lengths.

An important computational tool is the connection with additive codes over F 4 , made possible by the fact that E and F 4 share the same additive group. In analogy with [START_REF] Steven | Type IV self-dual codes over rings[END_REF], we introduce the notion of Type IV codes over E as those QSD codes, all codewords of which have even Hamming weight. While additive codes over F 4 were introduced in a Quantum coding context [START_REF] Calderbank | Quantum error correction via codes over GF (4)[END_REF], they enter the picture here as a computational tool. Thus, by forgetting the multiplicative structure, a linear E-code is, in particular an additive code over F 4 . The connection is close enough that there is a one-to-one correspondence between the residue and torsion code over E, and the Trace code and subfield subcode over F 4 . This allows in particular, efficient computation in the Magma package dedicated to additive codes [13]. While the additive codes classified here are not, in general, strong error correcting codes, they can have an interesting combinatorial structure as evidenced by Example 3.

We also study the weight enumerators in two and four variables of Type IV codes from the standpoint of invariant theory. This study refines the theory of the joint weight enumerator of a binary code and its dual started in [START_REF] Alahmadi | Joint weight enumerator of an LCD code and its dual[END_REF], to binary codes containing the all-one vector. This leads us to a Gleason formula for the weight enumerators of Type IV codes, in four variables (complete weight enumerator) and by specialization to the weight enumerator in two variables.

The material is organized as follows. The next section collects basic facts and definitions about rings, modules, and duality. Section 3 describes the structure of generator matrices of linear codes over E. Section 4 exploits this theory to construct QSD codes and derives a criterion for a QSD code to be Type IV. Section 5 studies the weight enumerators of QSD and Type IV codes. Section 6 classifies, up to equivalence, QSD codes of length n < 7. Section 7 concludes the article.

Background material 2.1 Binary codes

Denote by wt(x) the Hamming weight of x ∈ F n 2 . The dual of a binary linear code C is denoted by C ⊥ and defined as

C ⊥ = {y ∈ F n 2 | ∀x ∈ C, (x, y) = 0},
where (x, y) = n i=1 x i y i , denotes the standard inner product. A code C is self-orthogonal if it is included in its dual: C ⊆ C ⊥ . Two binary codes are equivalent if there is a permutation of coordinates that maps one to the other.

Rings

Following [START_REF] Fine | Classification of finite rings of order p 2[END_REF] we define a ring on two generators a, b by its relations

E = a, b | 2a = 2b = 0, a 2 = a, b 2 = b, ab = a, ba = b .
A model for that ring can be obtained by taking a, b to be matrices over F 2 defined by

a = 0 0 0 1 , b = 0 1 0 1 .
Thus, E has characteristic two, and consists of four elements E = {0, a, b, c}, with c = a + b. The addition table is immediate from these definitions.

+ 0 a b c 0 0 a b c a a 0 c b b b c 0 a c c b a 0
The multiplication table is as follows.

× 0 a b c 0 0 0 0 0 a 0 a a 0 b 0 b b 0 c 0 c c 0
From this table, we infer that this ring is not commutative, and without an identity element for the multiplication. It is local with maximal ideal J = {0, c}, and residue field E/J = F 2 = {0, 1}, the finite field of order 2.

Thus we have a c-adic decomposition as follows. Every element e ∈ E can be written e = as + ct, where s, t ∈ F 2 and where we have defined a natural action of F 2 on E by the rule r0 = 0r = 0 and r1 = 1r = r for all r ∈ E. Thus a = 1a, c = 1c and b = a1 + c1. Note that for all r ∈ E, this action is "distributive" in the sense that r(s ⊕ 2 t) = rs + rt, where ⊕ 2 denote the addition in F 2 .

Denote by α : E → E/J F 2 the map of reduction modulo J. Thus α(0) = α(c) = 0, and α(a) = α(b) = 1. This map is extended in the natural way in a map from E n to F 2 .

Modules

A linear E-code of length n is a one-sided E-submodule of E n . An additive code of length n over F 4 is an additive subgroup of F n 4 . It is a free F 2 module with 4 k elements for some k ≤ n (here 2k is an integer, but k may be halfintegral). Using a generator matrix G, such a code can be cast as the F 2 -span of its rows. To every linear E code C is attached an additive F 4 code φ(C) by the substitution

0 → 0, a → ω, b → ω 2 , c → 1,
where

F 4 = F 2 [ω]
. Note that the reverse substitution attaches to every additive F 4 code an additive subgroup of E n , which may or may not be linear. Two E-codes are permutation equivalent if there is a permutation of coordinates that maps one to the other.

Duality

Define an inner product on E n as (x, y) = n i=1 x i y i . The right dual C ⊥ R of C is the right module defined by

C ⊥ R = {y ∈ E n | ∀x ∈ C, (x, y) = 0}.
The left dual C ⊥ L of C is the left module defined by

C ⊥ L = {y ∈ E n | ∀x ∈ C, (y, x) = 0}.
Thus the left (resp. right) dual of a left (resp. right) module is a left (resp. right) module. A code is left self-dual (resp. right self-dual) if it is equal to its left (resp. right) dual. A left self dual code C satisfies

C ⊥ L = C. Likewise a right self dual code C satisfies C ⊥ R = C. A code is self-dual if it
is equal to both of its duals.

Remark 1

1. The repetition code of length 2 defined by R 2 := {00, aa, bb, cc},

is left self-dual. Its right dual is R ⊥ R 2 = aa, bb, ab , a supercode of R 2 of size 8.
2. In length one, we have J ⊥ R = J. By taking direct sums of J with itself, we see that (right) self-dual codes over E exist for all lengths. Remark 1 shows that the product of the sizes of a code and its dual is not always 4

n . A code C of length n is left nice (resp. right nice) if |C||C ⊥ L | = 4 n (resp. |C||C ⊥ R | = 4 n ). A code is nice if it is both left and right nice.
Remark 2 J is a right nice code, but it is not a left nice code since n = 1, and

J ⊥ L = E. Similarly, R 2 is not right nice since R ⊥ R 2 is of size 8. A code C is self-orthogonal if ∀x, y ∈ C, (x, y) = 0. Clearly, C is self-orthogonal iff C ⊆ C ⊥ L . Likewise, C is self-orthogonal iff C ⊆ C ⊥ R . Thus, for a self-orthogonal code C, we always have C ⊆ C ⊥ L ∩ C ⊥ R . A code of length n is quasi self-dual if it is self-orthogonal and of size 2 n .
Remark 3 Every one-sided nice self-dual code is quasi-self-dual but not conversely, as the next example shows.

Example 1 The code R 2 as a right module is quasi self-dual but not self-dual as R 2 R ⊥ R 2 .
Following a terminology from [START_REF] Steven | Type IV self-dual codes over rings[END_REF], a quasi self-dual code over E with all weights even is called a Type IV code.

Structure of linear codes

Let C be code of length n over E. With that code we associate two binary codes of length n :

1. the residue code defined by res(C) = {α(y) | y ∈ C},

the torsion code defined by tor

(C) = {x ∈ F n 2 | cx ∈ C}.
It can be checked that for all x ∈ E n , we have T r(φ(x)) = α(x), and thus

res(C) = T r(φ(C)), where ∀z ∈ F 4 , T r(z) = z + z 2 . Similarly, we see that tor(C) is the subfield subcode of φ(C).
Example 2 The dodecacode, the most famous additive code [START_REF] Calderbank | Quantum error correction via codes over GF (4)[END_REF], is not φ(C) for some E-code C, since it can be checked by electronic computation that the residue and torsion code would have dimensions 6, and 2 respectively, contradicting Lemma 1 below.

Denote by α C the restriction of α to C. We see that tor(C)c = Ker(α C ), and that res(C) = Im(α C ). By the first isomorphism theorem applied to the map α C , we see that |C| = |res(C)||tor(C)|. There is a relationship between these two codes.

Lemma 1 If C is an E-linear code then res(C) ⊆ tor(C).

Proof.

Write an arbitrary codeword in c-adic decomposition form as ax + cy, with x, y binary vectors. Since α(ax + cy) = x, we have x ∈ res(C). Note that, by definition of the residue code, any x ∈ res(C) arises in that way. Multiplying the codeword ax + cy on the left by c, we see that cx ∈ C, implying x ∈ tor(C).

We let k 1 = dim(res(C)), and k 2 = dim(tor(C)) -k 1 , a nonegative quantity by Lemma 1, and say that C is of type (k 1 , k 2 ). It can be seen that C is free as an E-module iff k 2 = 0. Further, by a previous observation,

|C| = |res(C)||tor(C)| = 2 2k 1 +k 2 .
We give a characterization of the generator matrix of a linear code as a function of these invariants.

Theorem 1 Assume C is an E-linear code of length n and type (k 1 , k 2 ). Then a generator matrix G of C is of the form G = aI k 1 X Y 0 cI k 2 cZ ,
where I j denotes the identity matrix of order j, the matrices X, Y have entries in E, and Z is a binary matrix.

Proof.

Write the generator matrices of res(C) and tor(C) as

G 1 = I k 1 α(X) α(Y ) and G 2 = I k 1 α(X) α(Y ) 0 I k 2 Z
, respectively, where X, Y are matrices of suitable dimensions with entries in E, and Z is a binary matrix. By the first isomorphism theorem applied to the map α C , the matrix

G can be written in the form R cT , where
tor(C) = res(C) ⊕ T , and α(R) = G 1 .
We give a left oriented result and leave the right leaning reader generalize it.

Theorem 2 Assume C is a left nice E-linear code of length n and type (k 1 , k 2 ). Then a parity check matrix H of C consistent with Theorem 1 is of the form

H = Y t + Z t X t aZ t aI n-k 1 -k 2 cX t cI k 2 0 ,
where I j denotes the identity matrix of order j, and X, Y, Z are as in Theorem 1. In particular

C ⊥ is of type (n -k 1 -k 2 , k 2 ). If, furthermore C is self-dual, then n = 2k 1 + k 2 .
Proof. A direct calculation shows that HG t = 0. This shows that, as left modules,

H = E n-k 1 H ⊆ C ⊥ .
= n -k 1 -k 2 .

Constructions of quasi self-dual codes

We call the next construction of E-codes from binary codes the multilevel construction.

Theorem 3 Let B be a self-orthogonal binary code of length n. The code C defined by the relation

C = aB + cB ⊥ ,
is a quasi-self-dual code. Its residue code is B and its torsion code is B ⊥ .

Proof. The code C is closed under addition, by linearity of B. Note that

aC ⊆ aB ⊆ C. Since B is self-orthogonal, we see that cC ⊆ cB ⊆ cB ⊥ ⊆ C. Again by self-orthogonality of B we get bC ⊆ bB ⊆ aB + cB ⊆ aB + cB ⊥ ⊆ C.
Thus C is E-linear. For all x, x in B and y, y in B ⊥ we have the inner products

(ax + cy, ax + cy ) = a(x, x ) + c(y, x ) = 0 since B is self orthogonal. Thus C is self-orthogonal. Since |C| = |B||B ⊥ | = 2 n , we see that |C| = 2 n .
The residue and torsion codes are direct to derive from the definitions.

Remark 4

1. The same result would hold for the rule C = bB + cB ⊥ , by symmetry of the multiplication table between a and b.

2. A similar construction for right modules is immediate and left to the reader. The above multilevel construction leads to the following result. Henceforth, ⊕ will denote the direct sum of vector spaces and modules.

Corollary 1 If B 1 , and B 2 are two binary codes of length n, with B 1 ⊆ B 2 , then there is an E-code C with residue code B 1 and torsion code

B 2 . If, furthermore, B 1 is self-orthogonal and B 2 ⊆ B ⊥ 1 then C is self-orthogonal. If, in addition, B 2 = B ⊥ 1 , then C is quasi self-dual. Proof.
Take C = aB 1 + cB 2 and apply the construction of Theorem 3. Note that then

|C| = |B 1 ||B 2 |.
The most general construction of self-dual E-codes from the Residue /Torsion viewpoint is given in the next theorem, which requires the two following lemmas.

Lemma 2 For all self-orthogonal E-linear codes C we have

1. res(C) ⊆ res(C) ⊥ , 2. tor(C) ⊆ res(C) ⊥ , 3. tor(C) = res(C) ⊥ if |C| = 2 n .

Proof.

The first statement follows by the fact that α is a ring morphism. Note that if ax + cy, cz ∈ C for binary vectors x, y, z then (cz, ax + cy) = 0 yielding c(x, z) = 0, hence (x, z) = 0. This proves the second statement. The last statement follows by 2, and dimension count, since

|C| = 2 2k 1 +k 2 = 2 n yields n -k 1 = k 1 + k 2 .
The following lemma does not hold over other rings of size 4.

3. n = 2k 1 + k 2 .
Furthermore, a quasi self-dual code C is Type IV iff res(C) contains the all-one codeword.

Proof.

By Lemma 2, the first two conditions are necessary. The third condition follows by

|C| = 2 2k 1 +k 2 = 2 n .
We claim that a quasi self-dual code C is Type IV iff tor(C) has only even weight codewords. This happens iff res(C) = tor(C) ⊥ contains the all-one codeword. We now prove the claim.

The condition is necessary as c tor(C) ⊆ C.

To prove that the condition is sufficient, write S, T for binary vectors of length n, such that aS + cT ∈ C. We see that wt(aS + cT ) = wt(S) + wt(T ) -wt(S ∩ T ), where we let S ∩ T = (s 1 t 1 , . . . , s n t n ).

By assumption, and Lemma 3, we know that wt(T ) is even. Similarly wt(S) is even since res(C) ∈ tor(C). Now wt(S ∩ T ) is congruent to (S, T ) modulo 2, which is zero since T ∈ tor(C) = res(C) ⊥ . Thus wt(aS + cT ) ≡ 0 (mod 2), showing sufficiency.

The power of Lemma 3 is best illustrated by the following three results.

d ≤ n -k 1 + 1, d ≤ n -k 1 -k 2 + 1.
Adding up these two inequalities and using

n = 2k 1 + k 2 yields 2d ≤ 2n -n + 2 = n + 2.
Since d is an integer this yields d ≤ n 2 + 1. For a Type IV code, both n and d are even. Since 2 x/2 is the largest even integer less than a real x, we see that

d ≤ 2 n 2 +1 2 = 2 n+2 4 .
The next result shows that all QSD codes can be obtained by a multilevel construction. Example 3 If C is a QSD code with res(C) = tor(C), then its residue code is self-dual. It is easy to check by Theorem 6 that φ(C) is obtained by extension of scalars from res(C). Formally, C = res(C) ⊗ F 4 . Thus, a QSD code of length 8 can be constructed in that way from the extended Hamming code, a self-dual code of parameters [START_REF] Fine | Classification of finite rings of order p 2[END_REF][START_REF] Conway | Self-dual codes over the integers modulo four[END_REF][START_REF] Conway | Self-dual codes over the integers modulo four[END_REF]. Its weight enumerator can be computed to be as follows.

[< 0, 1 >, < 4, 42 >, < 6, 168 >, < 8, 45 >].

The columns of its check matrix form a triple sum set in the sense of [START_REF] Shi | Three-weight codes, triple sum sets, and strongly walk regular graphs[END_REF], since the sum of the weights (4 + 6 + 8) equals 3 × 8 × 3 4 .

Weight enumerators

In this section we study the weight enumerators of QSD codes. If r denotes a vector of E n , denote by n i (r) the number of components taking the value i ∈ E it contains. The complete weight enumerator cwe C of an E-code C can then be defined as the homogeneous polynomial in four variables.

cwe C ((x i ) i∈E ) = r∈C i∈E x n i (r) i .
The weight enumerator W C (x, y) of C is then defined as W C (x, y) = cwe C ((x i ) i∈E ), when x 0 = x and x i = y for i = 0. The joint weight enumerator of two binary codes is defined as follows. Let u, v denote binary vectors of length n. We define the integers i(u, v), j(u, v), k(u, v) and l(u, v) to be the number of indices ι ∈ {1, • • • , n} with (u ι , v ι ) = (0, 0), (0, 1), (1, 0) and (1, 1), respectively. The joint weight enumerator J(A, B) of, say, two binary linear codes A, B, is the four-variable polynomial defined by the formula

J(A, B)(w, x, y, z) = u∈A, v∈B w i(u,v) x j(u,v) y k(u,v) z l(u,v) .
The following result connects the complete weight enumerator of a QSD code with that of its residue and torsion codes.

Theorem 8 Order E as (0, c, a, b). If C is QSD, then cwe C (w, x, y, z) = J(res(C), tor(C))(w, x, y, z).

Proof.

By Theorem 6 we can write any element of C in unique fashion as au + cv, with u ∈ res(C), and v ∈ tor(C). Considering the four cases (u i , v i ) = (0, 0), (0, 1), (1, 0) and (1, 1) yields in succession

(au + cv) i = au i + cv i = 0, c, a, b.
The result follows. We proceed to derive the matrix group G under which the cwe C of a QSD code C of residue code R is invariant.

Proposition 1 J(R, R ⊥ )(w, x, y, -z) = J(R, R ⊥ )(w, x, y, z).

Proof.

By orthogonality of u ∈ R and v ∈ R ⊥ , we see that l(u, v) is even.

Proposition 2 J(R, R ⊥ )(w, x, y, z) = 1 2 n J(R, R ⊥ )(w + x + y + z, w + x -y -z, w -x + y -z, w -x -y + z).
Proof. Combine MacWilliams identity [12, (32) p.148] between J(R, R ⊥ ) and J(R ⊥ , R) with the relation [12, (29) p.148]. Further, there is the following relation for n even.

Proposition 3 If n is even, then J(R, R ⊥ )(-w, -x, -y, -z) = J(R, R ⊥ )(w, x, y, z).
Proof. Follows by homogeneity of the polynomial.

The polynomial J(R, R ⊥ ) is an invariant of degree n of a group G = H, J, -I of order 24, where

2H =     1 1 1 1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 1     , and J =     1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 -1     .
The three generators are implied by the three above propositions. The Molien series of G is

1 + 2t 2 + t 4 (1 -t 2 ) 3 (1 -t 6 )
.

This is consistent with the Molien series of [1, §3]. The relevant primary and secondary invariants can be found in [START_REF] Alahmadi | Joint weight enumerator of an LCD code and its dual[END_REF]Appendix]. If, furthermore, C is Type IV, we need to use the fact that, by Theorem 4, R ⊥ has only even weight codewords .

Proposition 4 If C is Type IV, then J(R, R ⊥ )(w, -x, y, -z) = J(R, R ⊥ )( w, x, y, z).

Proof.

By Theorem 4, the QSD code C is Type IV iff R contains the all-one vector, that is to say iff R ⊥ has only even weights. Since the weight of v ∈ R ⊥ in terms of exponents of J(R, R ⊥ ) is j + l, we see that j + l is an even number. The result follows. This means that cwe C is invariant under K where

K =     1 0 0 0 0 -1 0 0 0 0 1 0 0 0 0 -1     . Let G 4 = G, K . It turns out that G 4 is a group of order 48 with Molien series 1 + t 4 (1 -t 2 ) 2 (1 -t 4 )(1 -t 6 )
.

Define the following four primary invariants, of respective degrees 2, 2, 4, 6. We also need the secondary invariant of degree four

f 2 = w 2 + x 2 + y 2 + z 2 , f 2 = wy -1/2x 2 -1/2z 2 , f 4 = w 4 + 6wx 2 y + 6wyz 2 -1/2x 4 + 3x 2 z 2 + y 4 -1/2z
h 4 = w 4 + 10w 2 x 2 -2w 2 y 2 -2w 2 z 2 + x 4 -2x 2 y 2 -2x 2 z 2 + y 4 + 10y 2 z 2 + z 4 .
After specialization of the variables (w = x and x = y = z = y) we obtain polynomials in two variables x, y. We summarize the above discussion in the following Theorem.

g 2 = x 2 + 3y
Theorem 9 If C is a Type IV E-code then its complete weight enumerator is in the

C[f 2 , f 2 , f 4 , f 6 ]-module C[f 2 , f 2 , f 4 , f 6 ]+h 4 C[f 2 , f 2 , f 4 , f 6 ]. Its Hamming weight enumerator is in the algebra C[g 2 , g 2 , g 4 , g 6 ]-module C[g 2 , g 2 , g 4 , g 6 ] + h 4 C[g 2 , g 2 , g 4 , g 6 ].
Remark 5 1. The repetition code R 2 has weight enumerator g 2 .

2. The group G 4 has the same size and Molien series as the group appearing in [15, §7.7] acting on the cwe of trace self-dual additive even codes that contain the all-one vector.

3.

It is an open problem to describe the invariant ring of Type IV codes by only using invariants that are weight enumerators.

6 Short length classification (n < 7)

In the following, we classify, up to equivalence, QSD codes by means of the multilevel construction, and of the characterization of Theorem 6. To each binary self orthogonal code is attached a QSD code, it is the residue code of. The torsion code is then the dual of the self-orthogonal code. By Theorem 4 and Theorem 6, classifying QSD E-codes up to permutation equivalence is equivalent to classifying self-orthogonal binary codes up to equivalence. Likewise, classifying Type IV QSD E-codes up to permutation equivalence is equivalent to classifying self-orthogonal binary codes containing the all-one vector up to equivalence. We thus construct self-orthogonal codes by hand in short lengths and rely on the classification of Hou [START_REF] Hou | On the Number of Inequivalent Binary Self-Orthogonal Codes[END_REF] to know the maximum number of equivalence classes. Some codes can be generated by triads or tetrads. Recall that an isotropic vector x ∈ E n is any vector satisfying (x, x) = 0. We define a triad as an isotropic vector of Hamming weight three in E n with n ≥ 3. Likewise we define a tetrad as an isotropic vector of Hamming weight four in E n with n ≥ 4.

We use the term additive generator matrix to mean that the code is obtained by taking sums of the rows. Thus, the additive generator matrix of a QSD code is always a square matrix.

n = 2 (2 codes)

A QSD code that is not type IV can be constructed by the multilevel construction from the binary self-orthogonal code { 0 0 } and its dual, F 2 2 . Its generator matrix is

cI 2 = c 0 0 c and its weight distribution is [< 0, 1 >, < 1, 2 >, < 2, 1 >].
The other one is a type IV E-code with residue code the binary self-orthogonal code generated by 1 1 . Its generator matrix is a a and its weight distribution is [< 0, 1 >, < 2, 3 >]. Its φ-image is F 4 -linear.

n = 3 (2 codes)

One QSD code can be constructed from the binary self-orthogonal code generated by 0 0 0 . Its generator matrix is cI 3 and its weight distribution is

[< 0, 1 >, < 1, 3 >, < 2, 3 >, < 3, 1 >].
The other QSD code can be constructed from the binary self-orthogonal code generated by 1 0 1 . Its additive generator matrix is

  a 0 a c 0 c 0 c 0   and its weight distribution is [< 0, 1 >, < 1, 1 >, < 2, 3 >, < 3, 3 >].
6.3 n = 4, 5, 6

We summarize the information in the following four tables.

[< 0, 1 >, < 1, 4 >, < 2, 6 >, < 3, 4 >, < 4, 1 >] no 1 0 0 1     c 0 0 c a 0 0 a 0 c 0 0 0 0 c 0     , [< 0, 1 >, < 1, 2 >, < 2, 4 >, < 3, 6 >, < 4, 3 >] no 1 1 1 1     c 0 0 c a a a a 0 c 0 c 0 0 c c     , [< 0, 1 >, < 2, 6 >, < 4, 9 >] no 1 0 1 0 0 1 0 1 a 0 a 0 0 a 0 a [< 0, 1 >, < 2, 6 >, < 4, 9 >] yes Table 2: codes of length 5
Residue code Generator Matrix weight distribution Type IV 0 0 0 0 0 cI 5

[< 0, 1 >, < 1, 5 >, < 2, 10 >, < 3, 10 >, < 4, 5 >, < 5, 1 >] no 1 1 0 0 0       a a 0 0 0 c c 0 0 0 0 0 c 0 0 0 0 0 c 0 0 0 0 0 c       [< 0, 1 >, < 1, 3 >, < 2, 6 >, < 3, 10 >, < 4, 9 >, < 5, 3 >] no 1 1 1 1 0     a a a a 0 c 0 0 c 0 0 c 0 c 0 0 0 0 0 c     [< 0, 1 >, < 1, 1 >, < 2, 6 >, < 3, 6 >, < 4, 9 >, < 5, 9 >] no 1 0 1 0 0 0 1 0 0 1       c 0 c 0 0 a 0 a 0 0 0 c 0 0 c 0 a 0 0 a 0 0 0 c 0       [< 0, 1 >, < 1, 1 >, < 2, 6 >, < 3, 6 >, < 4, 9 >, < 5, 9 >] no

Conclusion and open problems

In this article we have studied quasi self-dual codes over the non-unital noncommutative ring E of order four. The existence of codes that are not nice preclude any attempt to derive a general MacWilliams formula, since this would imply a relation between the size of a code and that of its dual. We have thus introduced QSD codes as an alternative to the concept of self-dual codes. However, the special structure of QSD codes allowed us to use the invariant approach to the joint weight enumerator of the residue code and the torsion code. Eventually, we gave a classification up to length 6 of the QSD codes, and of the Type IV QSD codes. Reference [START_REF] Hou | On the Number of Inequivalent Binary Self-Orthogonal Codes[END_REF] allows us to reduce the classification problem for QSD codes to that of binary self-orthogonal codes. Since such a classification is not known in the literature for n > 6, another technique is needed in higher lengths. One possibility would be to derive a mass formula, as it exists already over certain rings [START_REF] Balmaceda | Mass formula for self-dual codes over Z p 2[END_REF][START_REF] Gaborit | Mass formulas for self-dual codes over Z 4 and F q +uF q rings[END_REF].

Lemma 3

 3 If C is a QSD code, and an arbitrary codeword of C is aS + cT, with S, T binary vectors of length n, then S ∈ res(C), and T ∈ tor(C). In particular, a res(C) ⊆ C.

Theorem 4

 4 Proof.Since α(aS + cT ) = S, we see that S ∈ res(C). Since res(C) ⊆ tor(C) any S ∈ res(C), satisfies aS ∈ C. Using the self-orthogonality of C, we get, (aS + cT, aS ) = 0, and by 1 of Lemma 2 (T, S ) = 0, ∀S ∈ res(C). Thus T ∈ res(C) ⊥ = tor(C), by 3 of Lemma 2. Since cT ∈ C, we see that aS = (aS + cT ) + cT ∈ C. If a left linear code C of length n is quasi self-dual then 1. res(C) ⊆ res(C) ⊥ , 2. tor(C) = res(C) ⊥ ,

Theorem 5 4 .

 54 If C is QSD of minimum Hamming distance d, then d ≤ n 2 +1. If, furthermore, C is Type IV, then d ≤ 2 n+2 Proof. Denote by d R and d T , respectively, the minimum distances of the residue and torsion codes of C. By definition of tor(C), we have d ≤ d T . By Lemma 3, we have a res(C) ⊆ C, implying d ≤ d R . The Singleton bound for binary codes applied to res(C) and tor(C) successively shows then that

Theorem 6

 6 If C is QSD, then C = a res(C) ⊕ c tor(C) as modules. Proof. By Lemma 3 we have the inclusion C ⊆ a res(C) + c tor(C). Comparing sizes of both sides shows that equality holds. Indeed, by hypothesis C has size 2 n . Since by Lemma ??, we have res(C) = tor(C) ⊥ , the size of the right handside is at most 2 n . Thus C = a res(C) + c tor(C), and the counting argument shows that the sum is direct. Theorem 7 If C is QSD, and is left linear, then φ(C) = φ(C). If, furthermore, φ(C) is linear then it admits a binary basis. Proof. By Lemma 3, if as + ct ∈ C, then both as and ct are in C. By left multiplication, bs = b(as) ∈ C. Thus bs + ct ∈ C, yielding that φ(as + ct) = φ(bs + ct) ∈ φ(C), if φ(as + ct) ∈ φ(C). The first assertion follows. If φ(C) is linear, let G = (I, M ) be its generator matrix in systematic form. The fact that φ(C) = φ(C) implies that M = M . The rows of G form the sought basis.

Table 3 :

 3 codes of length 6, part I 1 >, < 1, 6 >, < 2, 15>, < 3, 20 >, < 4, 15 >, < 5, 6 >, < 6, 1 >]. 1 >, < 1, 4 >, < 2, 9 >, < 3, 16 < 4, 19 >, < 5, 12 >, < 6, 3 >] 1 >, < 1, 2 >, < 2, 7 >, < 3, 12 >, < 4, 15 >, < 5, 18 >, < 6, 9 >] 1 >, < 2, 15 >, < 4, 15 >, < 6, 33 >] noTable4: codes of length 6, part II 1 >, < 1, 2 >, < 2, 7 >, < 3, 12 >, < 4, 15 >, < 5, 18 >, < 6, 9 >] 1 >, < 2, 3 >, < 3, 8 >, < 4, 15 >, < 5, 24 >, < 6, 13 >] 1 >, < 2, 9 >, < 4, 27 >, < 6, 27 > no 0, 1 >, < 2, 9 >, < 4, 27 >, < 6, 27 >] no

  4 , f 6 = w 6 + 6/17w5 y + 15/17w 4 x 2 + 15/17w 4 y 2 + 15/17w 4 z 2 + 60/17w 3 x 2 y + 20/17w 3 y 3 + 60/17w 3 yz 2 + 15/17w 2 x 4 + 90/17w 2 x 2 y 2 + 90/17w 2 x 2 z 2 + 15/17w 2 y 4 + 90/17w 2 y 2 z 2 + 15/17w 2 z 4 + 30/17wx 4 y + 60/17wx 2 y 3 + 180/17wx 2 yz 2 + 6/17wy 5 + 60/17wy 3 z 2 + 30/17wyz 4 + 1/17x 6 + 15/17x 4 y 2 + 15/17x 4 z 2 + 15/17x 2 y 4 + 90/17x 2 y 2 z 2 + 15/17x 2 z 4 + y 6 + 15/17y 4 z 2 + 15/17y 2 z 4 + 1/17z 6 .

  2 , g 2 = xy -y 2 , g 4 = x 4 + 12xy 3 + 3y 4 , g 6 = x 6 + 6/17x 5 y + 45/17x 4 y 2 + 140/17x 3 y 3 + 315/17x 2 y 4 + 366/17xy 5 + 199/17y 6 h 4 = x 4 + 6x 2 y 2 + 9y 4 .

Table 1 :

 1 codes of length 4

	Residue code	Generator Matrix weight distribution	Type IV
	0 0 0 0	cI 4


Antoine Miech

Ivan Laptev

Josef Sivic

Heng Wang

Lorenzo Torresani

Du Tran

Leveraging the Present to Anticipate the Future in Videos

Anticipating actions before they are executed is crucial for a wide range of practical applications including autonomous driving and robotics. While most prior work in this area requires partial observation of executed actions, in the paper we focus on anticipating actions seconds before they start. Our proposed approach is the fusion of a purely anticipatory model with a complementary model constrained to reason about the present. In particular, the latter predicts present action and scene attributes, and reasons about how they evolve over time. By doing so, we aim at modeling action anticipation at a more conceptual level than directly predicting future actions. Our model outperforms previously reported methods on the EPIC-KITCHENS and Breakfast datasets.

Introduction

Automatic video understanding has improved significantly over the last few years. Such advances have manifested in disparate video understanding tasks, including action recognition [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF][START_REF] Feichtenhofer | Convolutional two-stream network fusion for video action recognition[END_REF][START_REF] Girdhar | Actionvlad: Learning spatio-temporal aggregation for action classification[END_REF][START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF][START_REF] Tran | A closer look at spatiotemporal convolutions for action recognition[END_REF], temporal action localization [START_REF] Shou | Autoloc: Weaklysupervised temporal action localization in untrimmed videos[END_REF][START_REF] Singh | Hide-and-seek: Forcing a network to be meticulous for weakly-supervised object and action localization[END_REF][START_REF] Wang | Untrimmednets for weakly supervised action recognition and detection[END_REF][START_REF] Zhao | Temporal action detection with structured segment networks[END_REF], video search [START_REF] Hendricks | Localizing moments in video with natural language[END_REF], video summarization [START_REF] Plummer | Enhancing video summarization via vision-language embedding[END_REF] and video categorization [29]. In this work, we focus on the problem of anticipating future actions in videos as illustrated in Figure 1.

A significant amount of prior work [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF][START_REF] Feichtenhofer | Convolutional two-stream network fusion for video action recognition[END_REF][START_REF] Girdhar | Actionvlad: Learning spatio-temporal aggregation for action classification[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF][START_REF] Liu | Recognizing human actions by attributes[END_REF][START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF][START_REF] Tran | A closer look at spatiotemporal convolutions for action recognition[END_REF][START_REF] Varol | Long-term Temporal Convolutions for Action Recognition[END_REF][START_REF] Wang | Action Recognition with Improved Trajectories[END_REF] in automatic video understanding has focused on the task of action recognition. The goal of action recognition is to recognize what action is being performed in a given video. While accurate recognition is crucial for a wide range of practical applications such as video categorization or automatic video filtering, certain settings do not allow for complete and even partial observation of action before it happens. For instance, an autonomous car should be able to recognize the intent of a pedestrian to cross the road much before the action is actually initiated in order to avoid an accident. In practical applications where we seek to act before an action gets executed, being able to anticipate the future given the present is critical.

Anticipating the future, especially long-term, is a chal- lenging task because the future is not deterministic: several outcomes are possible given the current observation. To reduce uncertainty, most work in this field [START_REF] Aliakbarian | Encouraging lstms to anticipate actions very early[END_REF][START_REF] Hoai | Max-margin early event detectors[END_REF][START_REF] Kong | Deep sequential context networks for action prediction[END_REF][START_REF] Ma | Learning activity progression in lstms for activity detection and early detection[END_REF][START_REF] Ryoo | Human activity prediction: Early recognition of ongoing activities from streaming videos[END_REF][START_REF] Shi | Action anticipation with rbf kernelized feature mapping rnn[END_REF] requires partially observed execution of actions. In this paper, we address the task of action anticipation even when no partial observation of the action is available. While prior work [START_REF] Farha | When will you do what?-anticipating temporal occurrences of activities[END_REF][START_REF] Lan | A hierarchical representation for future action prediction[END_REF][START_REF] Mahmud | Joint prediction of activity labels and starting times in untrimmed videos[END_REF][START_REF] Vondrick | Anticipating visual representations from unlabeled video[END_REF] has addressed this same task, in this work, we specifically focus on better leveraging recognition models to improve future action prediction. We propose a fusion of two approaches: one directly anticipates the future while the other first recognizes the present and then anticipates the future, given the present. We have empirically observed complementary of these two approaches when evaluating on three distinct and diverse benchmarks: EPIC-KITCHENS [START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF], Breakfast [START_REF] Kuehne | The language of actions: Recovering the syntax and semantics of goal-directed human activities[END_REF] and ActivityNet [4].

Contributions

The contributions of our work are: (i) We propose a new framework for the task of anticipating human actions several seconds before they are performed. Our model is decomposed into two complementary models. The first, named the predictive model, anticipates action directly from the visual inputs. The second one, the transitional model, is first constrained to predict what is happening in the ob-served time interval and then leverages this prediction to anticipate the future actions. (ii) We present extensive experiments on three datasets with state-of-the-art results on the EPIC-KITCHENS [START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF] and Breakfast action dataset [START_REF] Kuehne | The language of actions: Recovering the syntax and semantics of goal-directed human activities[END_REF]. In addition, our model provides ways to explain its ouputs, which allows us to easily interpret our model as we demonstrate in our qualitative analysis.

Related work

Predicting the future is a big area. Our work touches on future frame, motion and semantic mask prediction as well as human trajectory and action prediction, which we review below.

Future pixel, motion or semantic mask prediction. Future frame prediction has recently attracted many research efforts. Mathieu et al. [START_REF] Mathieu | Deep multi-scale video prediction beyond mean square error[END_REF] predict future frames of a video by proposing a multi-scale network architecture. They train it using an adversarial approach to minimize an image gradient difference loss. Vondrick et al. [START_REF] Vondrick | Generating the future with adversarial transformers[END_REF] also generate future video frames using a transformation of pixels from the past. Xue et al. [START_REF] Xue | Visual dynamics: Probabilistic future frame synthesis via cross convolutional networks[END_REF] instead propose a probabilistic model to generate future frames from a single image. Oh et al. [START_REF] Oh | Actionconditional video prediction using deep networks in atari games[END_REF] predict action dependent future frames in old-school Atari video games. Finn et al. [START_REF] Finn | Unsupervised learning for physical interaction through video prediction[END_REF] explore video prediction for real-world interactive robot agents. Instead of directly predicting future pixels, Luc et al. [24] aim at predicting future semantic segmentation mask in videos, Walker et al. [START_REF] Walker | The pose knows: Video forecasting by generating pose futures[END_REF] explore future pose prediction in videos and Pinteal et al. [START_REF] Pintea | Déja vu[END_REF] predict motion from single still images. Our work differs from them as we predict future action labels instead of predicting pixel level information.

Human trajectory prediction. Predicting human trajectories has also received wide attention [START_REF] Alahi | Social lstm: Human trajectory prediction in crowded spaces[END_REF][START_REF] Ma | Forecasting interactive dynamics of pedestrians with fictitious play[END_REF][START_REF] Kitani | Activity forecasting[END_REF][START_REF] Xu | Encoding crowd interaction with deep neural network for pedestrian trajectory prediction[END_REF]. Kitani et al. [START_REF] Kitani | Activity forecasting[END_REF] approach this task by casting it as an inverse reinforcement learning (IRL) problem. Alahi et al. [START_REF] Alahi | Social lstm: Human trajectory prediction in crowded spaces[END_REF] model prediction of human trajectories as a sequence generation task and propose to generate these trajectories using recurrent neural networks (LSTMs). These work differs from our as they are predicting an entire sequence of future locations instead of a single action.

Early-stage action recognition. Our work is related to the field of action anticipation and early-stage action prediction. A large body of work [START_REF] Aliakbarian | Encouraging lstms to anticipate actions very early[END_REF][START_REF] Hoai | Max-margin early event detectors[END_REF][START_REF] Kong | Deep sequential context networks for action prediction[END_REF][START_REF] Ma | Learning activity progression in lstms for activity detection and early detection[END_REF][START_REF] Ryoo | Human activity prediction: Early recognition of ongoing activities from streaming videos[END_REF][START_REF] Shi | Action anticipation with rbf kernelized feature mapping rnn[END_REF] focuses on predicting actions given partially observed executions. This setting differs from action recognition [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF][START_REF] Feichtenhofer | Convolutional two-stream network fusion for video action recognition[END_REF][START_REF] Girdhar | Actionvlad: Learning spatio-temporal aggregation for action classification[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF][START_REF] Liu | Recognizing human actions by attributes[END_REF][START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF][START_REF] Tran | A closer look at spatiotemporal convolutions for action recognition[END_REF][START_REF] Varol | Long-term Temporal Convolutions for Action Recognition[END_REF][START_REF] Wang | Action Recognition with Improved Trajectories[END_REF] or temporal action detection [START_REF] Shou | Autoloc: Weaklysupervised temporal action localization in untrimmed videos[END_REF][START_REF] Singh | Hide-and-seek: Forcing a network to be meticulous for weakly-supervised object and action localization[END_REF][START_REF] Wang | Untrimmednets for weakly supervised action recognition and detection[END_REF][START_REF] Zhao | Temporal action detection with structured segment networks[END_REF], as it assumes access to a small fraction (the beginning) of an action. One early work in this genre is from Ryoo [START_REF] Ryoo | Human activity prediction: Early recognition of ongoing activities from streaming videos[END_REF], who uses dynamic bag-of-words to efficiently model the feature distribution change over time. Hoai et al. [START_REF] Hoai | Max-margin early event detectors[END_REF] and Ma et al. [START_REF] Ma | Learning activity progression in lstms for activity detection and early detection[END_REF] formulate this task as a ranking problem where a monotonically non-decreasing prediction score is enforced as visual evidences are being accumulated. Similarly to Vondrick et al. [START_REF] Vondrick | Anticipating visual representations from unlabeled video[END_REF], Shi et al. [START_REF] Shi | Action anticipation with rbf kernelized feature mapping rnn[END_REF] aim first at regressing future visual feature vectors. These feature vectors are then used as input to an action recognition model for the earlystage action prediction. Our work differs from early-stage action prediction, as we aim at predicting an action even before it has actually started.

Action anticipation.

Prior efforts [START_REF] Farha | When will you do what?-anticipating temporal occurrences of activities[END_REF][START_REF] Kitani | Activity forecasting[END_REF][START_REF] Lan | A hierarchical representation for future action prediction[END_REF][START_REF] Mahmud | Joint prediction of activity labels and starting times in untrimmed videos[END_REF][START_REF] Vondrick | Anticipating visual representations from unlabeled video[END_REF] have been addressing the task of anticipating action before they are executed. The work of Farha et al. [START_REF] Farha | When will you do what?-anticipating temporal occurrences of activities[END_REF] aims at predicting not only one but a sequence of future actions. However, their experiments concern a restricted setup with a strong "action grammar" specific to cooking videos with predefined recipes [START_REF] Kuehne | The language of actions: Recovering the syntax and semantics of goal-directed human activities[END_REF]. Our work is not restricted to these type of datasets since we are also experimenting on unscripted cooking video dataset (EPIC-KITCHENS [START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF]) and non cooking video dataset (ActivityNet 200 [4]). Also their action anticipation approach can only be applied to videos with annotated sequence of actions whereas our method can be applied to any type of video dataset. Similarly to Mahmud et al. [START_REF] Mahmud | Joint prediction of activity labels and starting times in untrimmed videos[END_REF], their system is also trained to predict the start of the next action. Anticipating events before they occur is also used to predict traffic accidents [START_REF] Jain | Car that knows before you do: Anticipating maneuvers via learning temporal driving models[END_REF][START_REF] Suzuki | Anticipating traffic accidents with adaptive loss and large-scale incident db[END_REF][START_REF] Zeng | Agent-centric risk assessment: Accident anticipation and risky region localization[END_REF]. Prior work also applied action anticipation in the domain of sports analytics such as basketball [START_REF] Bertasius | Using cross-model egosupervision to learn cooperative basketball intention[END_REF][START_REF] Felsen | What will happen next? forecasting player moves in sports videos[END_REF], water polo [START_REF] Felsen | What will happen next? forecasting player moves in sports videos[END_REF], tennis and soccer [START_REF] Wei | Forecasting events using an augmented hidden conditional random field[END_REF]. Such models aim to anticipate future trajectories of a ball and individual players. IRL has also been recently applied to activity forecasting from firstperson egocentric daily activity videos [START_REF] Rhinehart | First-person activity forecasting with online inverse reinforcement learning[END_REF]. On the other hand, Wu et al. [START_REF] Wu | Anticipating daily intention using on-wrist motion triggered sensing[END_REF] combine on-wrist motion accelerometer and camera to perform daily intention anticipation. Note that several of these systems [START_REF] Alahi | Social lstm: Human trajectory prediction in crowded spaces[END_REF][START_REF] Aliakbarian | Encouraging lstms to anticipate actions very early[END_REF][START_REF] Farha | When will you do what?-anticipating temporal occurrences of activities[END_REF][START_REF] Ma | Learning activity progression in lstms for activity detection and early detection[END_REF][START_REF] Mahmud | Joint prediction of activity labels and starting times in untrimmed videos[END_REF][START_REF] Rhinehart | First-person activity forecasting with online inverse reinforcement learning[END_REF][START_REF] Shi | Action anticipation with rbf kernelized feature mapping rnn[END_REF][START_REF] Suzuki | Anticipating traffic accidents with adaptive loss and large-scale incident db[END_REF][START_REF] Wu | Anticipating daily intention using on-wrist motion triggered sensing[END_REF] employ the use of recurrent neural networks (RNNs) to address the sequential nature of these predictive tasks.

Action Anticipation Model

Our goal is to anticipate an action T seconds before it starts. More formally, let V denote a video. Then we indicate with V a:b the segment of V starting at time a and ending at time b, and with y c the label of the action that starts at time c . We would like to find a function f such that f (V 0:t ) predicts y t+T . The main idea behind our model is that we decompose f as a weighted average of two functions, a predictive model f pred and a transitional model f trans :

f = αf pred + (1 -α)f trans , α ∈ [0, 1], (1)
where α is a dataset dependent hyper-parameter chosen by validation. The first function f pred is trained to predict the future action directly from the observed segment. On the other hand, f trans is first constrained to compute highlevel properties of the observed segment (e.g., attributes or the action performed in the present). Then, in a second stage, f trans uses this information to anticipate the future action. In the next subsections we explain how to learn f pred and f trans . Figure 2 presents an overview of the proposed model.

Predictive model f pred

The goal of the predictive model f pred is to directly anticipate future action from the visual input. As opposed to f trans , f pred is not subject to any constraint. Suppose that we are provided with a training video V with action labels y t0+T , . . . , y tn+T . For each label y ti+T , we want to minimize the loss:

l(f pred (V s(ti):ti ), y ti+T ), (2)
where s(t i ) = max(0, t i -t pred ), l is the cross entropy loss, t pred is a dataset dependent hyper-parameter, also chosen by validation, that represents the maximum temporal interval of a video f pred has access to. This hyper-parameter is essential because looking too much in the past may add irrelevant information that degrades prediction performance. This loss is then summed up over all videos from the training dataset. In this work, f pred is a linear model which takes as input a video descriptor which we describe in section 4.2.

Transitional model f trans

The transitional model f trans splits the prediction into two stages: g s and g t . The first stage g s aims at recognizing a current state s, describing the observed video segment. The state s can represent an action or a latent actionattribute. The second stage g t takes as input the current state s, and anticipates the next action given the current state s. g s can be thought of as a complex function extracting highlevel information from the observed video segment, while g t is a simple (in fact, linear) function operating on the state s and modeling the correlation between the present state and the future action. We will next explain in detail how we define the current state s and how we model the transition function g t . We propose two different approaches for our transitional model: one that is based on action recognition and one that relies on visual attributes, as illustrated in Figure 3.

Transitional Model based on Visual Attributes. In this approach, we leverage visual attributes [START_REF] Liu | Recognizing human actions by attributes[END_REF] to anticipate the future. Visual attributes have been previously used for action recognition by Liu et al. [START_REF] Liu | Recognizing human actions by attributes[END_REF]. The idea is to first predefine a set of visual attributes describing the presence or absence of objects, scenes or atomic actions in a video. Then, a model is trained on these visual attributes for action recognition. In this work, we instead use visual attributes as a means to express the transitional model. The current state s ∈ [0, 1] a predicted by g s , is then a vector of visual attributes probabilities, where a is the number of visual attributes. Given the presently observed visual attribute s, g t predicts the future action. We model g t as a low-rank linear model:

g t (s) = W 2 (W 1 s + b 1 ) + b 2 , (3)
where

W 1 ∈ R r×a , W 2 ∈ R K×r , b 1 ∈ R r , b 2 ∈ R K , K ∈ N the
number of action classes and r is the rank of g t . These parameters are learned, in the same manner as the predictive model, by minimizing the cross entropy loss between the predicted action given by g t (s) and the future action ground-truth. Implementing g t through a lowrank model reduces the number of parameters to estimate. Empirically, we found that this leads to better accuracy, as shown in our experiments. The lower part of Figure 3 illustrates this case.

Transitional Model based on Action Recognition.

Real-world videos often consist of a sequence of elementary actions performed by a person in order to reach a final goal such as Preparing coffee, Changing car tire or Assembling a chair. Many datasets come with a training set where each video has been annotated with action labels and segment boundaries for all occurring actions (e.g EPIC-KITCHENS, Breakfast). When this is available we can use action labels instead of predefined visual attributes for state s. The intuition behind our claim is the fact that the anticipation of the next action significantly depends on the present beingperformed action. In other words, we make a Markov assumption on the sequence of performed actions. More formally, suppose we are provided with an ordered sequence of action annotations (a 0 , . . . , a N ) ∈ {1, . . . , K} N for a given video, where a n defines the action class performed in video segment V n . We propose to model P (a n+1 = i|V n ) as follows:

P (a n+1 = i|V n ) = K j=1 P (a n+1 = i| a n = j)P (a n = j|V n ) (4)
∀n ∈ {0, . . . , N -1}, i ∈ {1, . . . , K}. This reformulation decomposes the computation of P (a n+1 = i|V n ) in terms of two factors: 1) an action recognition model g s (V n ) that predicts P (a n = j|V n ), i.e., the action being performed in the present; 2) a transition matrix T that captures the statistical correlation between the present and the future action, i.e., such that T ij ≈ P (a n+1 = i| a n = j). In this scenario, g t takes as input the probability scores of each action given by g s to anticipate the next action in a probabilistic manner:

g t (s) = T s, (5)
P (a n+1 = i) = K j=1 T i,j s j = [g t (s)] i . (6)
In practice, we compute T by estimating the conditional probabilities between present and future actions from the the sequences of action annotations in the training set. The top part of Figure 3 illustrates this model.

Prediction Explainability. The transitional model f trans provides interpretable predictions that can be easily analyzed for explanation. Indeed, the function g t of the transitional model takes the form of a simple linear model applied to the state s, both when using visual attributes as well as when using action predictions. The linear weights of g t can be interpreted as conveying the importance of each element in s for the anticipation of the action class. For example, given an action class k to anticipate, we can analyze the linear weights of g t to understand which visual attributes or action class are most responsible for the prediction of action class k.

It also provides an easy way to diagnose the source of mispredictions. For example, suppose the transitional model anticipates wrongly an action k and we seek to understand the reason behind such misprediction. Let v 1 , . . . , v a ∈ [0, 1] be the vectors encoding the visual attributes (or action recognition scores) for this wrong prediction. Let also w k,1 , . . . , w k,a ∈ R be the learned linear weights associated to the prediction of action class k. The top factor for the prediction of action k is max i∈[1,a] (w k,i v i ). By analyzing this top factor, we can understand whether the misprediction is due to a recognition problem (i.e. wrong detection score for the visual attribute/action class) or due to the learned transition weights.

Experiments

In this section, we evaluate our approach on three datasets. Then we provide an ablation study, compare our method with the state-of-the-arts and present qualitative analysis of the transitional model.

Datasets

These datasets were picked because they are diverse and contain accurate annotated action temporal segments necessary for the evaluation of action anticipation. [START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF] is a largescale cooking video dataset containing 39,594 accurate temporal segment action annotations. Each video is composed of a sequence of temporal segment annotations. Three different tasks are proposed together with the dataset: object detection, action recognition and action anticipation. The action anticipation task is to predict an action one second before it has started. The dataset contains three different splits: the training set, the seen kitchens test set (S1) composed of videos from kitchens also appearing in the training set and finally the unseen kitchens test set (S2) with kitchens that are not appearing in the training set. A publicly available challenge is also organized to keep track of the best performing approach on this anticipation task. Because of this public challenge, the labels of S1 and S2 test sets are not available. Thus, most of our results are reported on our validation set composed of the following kitchens: P03, P14, P23 and P30. We also report results evaluated by the challenge organizers on the held-out test set. Unless specified otherwise, for comparison purposes, we report experiments with T = 1 sec.

EPIC-KITCHENS. EPIC-KITCHENS

Breakfast. The Breakfast action dataset [START_REF] Kuehne | The language of actions: Recovering the syntax and semantics of goal-directed human activities[END_REF] is an annotated cooking video dataset of people preparing breakfast meals. It comes with 11267 temporal segment action annotations. Each video is also composed of a sequence of temporal action segment annotations. The dataset is partitioned into four different train / test splits: S1, S2, S3 and S4. We quantify performance with the average scores over all of the four splits. Unless specified differently, for comparison purposes, we report experiments with T = 1 sec.

ActivityNet 200. The ActivityNet 200 video dataset [4] contains 15410 temporal action segment annotations in the training set and 7654 annotations in the validation set. This video dataset is mainly used for evaluating action localization models but as the videos are provided accurate temporal segment for each action, we can also use them to evaluate models on action anticipation. As opposed to the EPIC-KITCHENS [START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF] and Breakfast [START_REF] Kuehne | The language of actions: Recovering the syntax and semantics of goal-directed human activities[END_REF] datasets, each video contains only one single action annotation instead of a sequence of action segments. For this reason, we cannot test on ActivityNet the transitional model based on action recognition. We only train and evaluate on videos in the datasets with at least 10 seconds of video before the action starts. In total, the training and validation sets consists of respectively 9985 and 4948 action localization annotations.

Video Representation

In this subsection we discuss how we represent the observed video segment V to perform action prediction. Our overall strategy is to split the video into clips, extract clips Action Verb Noun A@1 A@5 A@1 A@5 A@1 A@5 Transitional (VA) 4. [START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF] representation and perform pooling over these clips. Given an input video segment V , we uniformly split it into small clips

V = [V 1 , . . . , V N ] where each clip V i , i ∈ [1, N ] is short enough (e.
g. 8 or 16 frames) that it can be fed into a pretrained video CNN C. From the penultimate layer of the CNN we extract an L 2 -normalized one-dimensional representation C(V i ) for each clip V i . Then we perform a temporal aggregation Agg([C(V 1 ), . . . , C(V N )]) of the extracted features in order to get a one-dimensional video representation for V . In our experiments, C is the R(2+1)D network of 18-layers from Tran et al. [START_REF] Tran | A closer look at spatiotemporal convolutions for action recognition[END_REF]. We perform a simple max pooling to aggregate features from all clips, but more sophisticated temporal aggregation techniques [29] can also be used in our model.

Visual Attributes. Our visual attributes presented in Section 3.2 include the taxonomies of Imagenet-1000 [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF], Kinetics-600 [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] and Places-365 [START_REF] Zhou | Places: A 10 million image database for scene recognition[END_REF]. We train two ResNet-50 [START_REF] He | Deep Residual Learning for Image Recognition[END_REF] CNN models: one on Imagenet-1000 and the other one on Places-365. For the Kinetics-600 taxonomy, we train a R(2+1)D-18 [START_REF] Tran | A closer look at spatiotemporal convolutions for action recognition[END_REF] model. In total, our set is composed of 1965 (1000+600+365) visual attributes. We densely extract these visual attributes every 0.5 seconds and apply the temporal max pooling operation to obtain a single vector for each video, as discussed above.

Leveraging the present for pretraining. In previous work [START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF][START_REF] Vondrick | Anticipating visual representations from unlabeled video[END_REF] the video representation was learned by finetuning a pretrained video CNN on the task of action anticipation. Instead, we propose to finetune the CNN representation on the task of action recognition on the target dataset. More specifically, instead of training the CNN on video clips sampled before action starts, we train it on clips sampled in the action segment interval. This is motivated by the fact that the task of action recognition is "easier' than action anticipation and thus it may lead to better feature learning. [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] and then finetuned for action recognition on the target dataset.

Ablation study

In order to understand the benefits of the different components in our model, we evaluate the predictive model separately from the transitional model. For the transitional model we report results for both the variant based on Visual Attributes (VA) as well as the version based on Action Recognition (AR). Table 2 summarizes the results achieved on the validation set of EPIC-KITCHENS [START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF]. The AR transitional model performs better than the VA transitional model. However, both are outperformed by the purelypredictive model. Interestingly, combining the predictive model with either of the two transitional models yields further accuracy gains. This suggests that the predictions are complementary.

We also show in grey, an accuracy upper bound achieved when directly recognizing the future frame as opposed to predicting from the past one (row Action recognition). The grey row Transitional (AR with GT) experiments shows the accuracy achieved when the transitional model is provided the groundtruth label of the last observed action. The improvement when using the groundtruth label is significant. This suggests that a large cause of missing performance is weak action recognition models and that better action recognition will produce stronger results for prediction.

We also perform ablation studies on the ActivityNet dataset in Table 3. Since we are not provided sequences of action annotations in this dataset, for this experiment we can only apply the transitional model based on Visual Attributes. Here again, we demonstrate the complementarity of the predictive and transitional models. The average of both approaches provides the best results for action anticipation. We also show the importance of modeling g t as a low-rank linear model on visual attributes. Constraining g t to be a low-rank linear model provides a boost of more than 4% in accuracy.

Comparison to the state-of-the-art

We compare our approach to the state-of-the-art on both the EPIC-KITCHENS and the Breakfast dataset. Table 5 shows our method compared to the recent work of Farha et al. [START_REF] Farha | When will you do what?-anticipating temporal occurrences of activities[END_REF]. The numbers for Vondrick et al. [START_REF] Vondrick | Anticipating visual representations from unlabeled video[END_REF] are based on the reimplementation of this method provided in [START_REF] Farha | When will you do what?-anticipating temporal occurrences of activities[END_REF]. Table 4 reports results obtained from the EPIC-KITCHENS unseen kitchens action anticipation challenge submission server. Note that our EPIC-KITCHENS submission is done under the anonymous nickname of masterchef and is reported by the row Ours (Predictive [D] + Transitional) in this paper. On both datasets, our method outperforms all previously reported results under almost all metrics. Note that our best submitted model on the EPIC-KITCHENS challenge is simple and does not make use of any ensembling nor optical flow input.

Qualitative analysis

As explained in subsection 3.2, through the analysis of the transitional model f trans , we can analyze which visual attributes are responsible for the anticipation of each action class. To do so, we analyze the linear weights from g t (3) to list the top visual attributes maximizing the prediction of each action class. Table 6 shows some action classes from the ActivityNet 200 [4] dataset and the top-3 visual attributes that maximize their anticipation. For instance, we can observe that identifying a Border collie dog (A dog specialized in the activity of disc dog) in a video is useful for the prediction of the Disc dog action class. Recognizing Lemon and Measure cup is indicative for the anticipation of Making lemonade.

Conclusion

We have described a new model for future action anticipation. The main motivating idea for our method is to model action anticipation as a fusion of two complementary modules. The predictive approach is a purely anticipatory model. It aims at directly predicting future action given the present. On the other hand, the transitional model is first constrained to recognize what is currently seen and then uses this output to anticipate future actions. Our approach achieves state-of-the-art action anticipation performances on the EPIC-KITCHENS [START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF] and Breakfast [START_REF] Kuehne | The language of actions: Recovering the syntax and semantics of goal-directed human activities[END_REF] datasets.

Action

Verb

Noun A@1 A@5 P R A@1 A@5 P R A@1 A@5 P R

Figure 1 :

 1 Figure 1: Action anticipation. Examples of action anticipation in which the goal is to anticipate future actions in videos seconds before they are performed.

Figure 2 :

 2 Figure 2: Overview of our approach. Our task is to predict an action T seconds before it starts to be performed. Our model is a combination of two complementary modules: the predictive model and the transitional model. While the predictive model directly anticipates the future action, the transitional model is first constrained to output what is currently happening. Then, it uses this information to anticipate future actions.

3 :

 3 Illustration of our transitional models. Upper: our Action Recognition (AR) based transitional model learns to prediction future actions based on the predictions of an action recognition classifier applied on current/present frames (clips). Lower: our Visual Attributes (VA) based transitional model learns to predict future actions based on visual attributes of the current/present frames (clips).

  report anticipation accuracy averaged over all of the test splits of Breakfast dataset[START_REF] Kuehne | The language of actions: Recovering the syntax and semantics of goal-directed human activities[END_REF] and use T = 1 sec. mug, Espresso Making an omelette Cooking egg, Wok, Shaking head Making lemonade Lemon, Measure cup, Pitch Playing ice hockey Hockey arena, Hokey stop, floor, Rapeseed Using parallel bars Parallel bars, High jump, Coral fungus Table 6: Top-3 attributes that indicative of actions. Top-3 visual attributes activations for the anticipation of some action class from the ActivityNet 200 dataset.

Table 1 :

 1 Effects of pre-training. Action anticipation top-1 per clip accuracy on EPIC-KITCHENS with different models and pretraining datasets.

	Model	Pretrain Fine-tune Action Verb Noun
	ResNet-50 Imagenet	No	3.4 24.5 7.4
	R(2+1)D-18 Kinetics	No	5.2 27.2 10.3
	R(2+1)D-18 Kinetics EK-Anticip. 5.0 24.6 9.7
	R(2+1)D-18 Kinetics EK-Recogn. 6.0 27.6 11.6

Table 2 :

 2 12.1 25.0 71.7 9.1 24.5 Transitional (AR) 5.1 17.1 25.2 72.0 12.1 33.2 Predictive 6.3 17.3 27.4 73.1 11.9 31.5 Predictive + Transitional (VA) 6.8 18.1 28.4 74.0 12.5 33.0 Predictive + Transitional (AR) 6.7 19.1 27.3 73.5 12.9 34.6 Transitional and predictive model ablation. Transitional model and predictive model ablation study on our EPIC-KITCHENS validation set with T = 1 sec. VA and AR denote for Visual Attributes and Action Recognition. Grey rows should be interpreted as accuracies upper bounds.

	Transitional (AR with GT)	16.1 29.4 29.3 63.3 30.7 44.4
	Action recognition	12.1 30.0 39.3 80.0 23.1 49.3

  Table 1 reports accuracies on the EPIC-KITCHENS validation set obtained with our predictive model applied to

	Model	Accuracy
	Random baseline	0.3
	Predictive	51.6
	Transitional (All VA, Full rank)	48.0
	Transitional (Object & Scene VA, Low rank, r = 256)	37.0
	Transitional (All VA, Low rank, r = 256)	52.8
	Predictive + Transitional (VA, Low rank)	54.8

Table 3 :

 3 Results on ActivityNet action anticipation. Our methods compared with baseline on our validation set with T = 5 sec. VA stands for Visual Attributes.different CNN representations. These results illustrate the benefit of fine-tuning the CNN on action recognition, instead of action anticipation as done in prior work[START_REF] Damen | Scaling egocentric vision: The epic-kitchens dataset[END_REF][START_REF] Vondrick | Anticipating visual representations from unlabeled video[END_REF]. The Table provide also numbers for two additional baselines corresponding to 1) using the CNN pretrained on Kinetics without finetuning and 2) extracting features from a ResNet-50 2D CNN pretrained on Imagenet. It can be noted that the best accuracies for actions, verbs and nouns are obtained with the CNN finetuned on the action recognition task of EPIC-KITCHENS. Based on these results, in the rest of the work, we use CNN features computed from a R(2+1)D-18 first pretrained on Kinetics

Table 4 :

 4 Damen et al. (TSN Fusion) [6]1.7 9.1 1.0 0.9 25.4 68.[START_REF] Bertasius | Using cross-model egosupervision to learn cooperative basketball intention[END_REF] 13.0 5.7 9.8 27.2 5.1 5.6 Damen et al. (TSN Flow) [6] 1.8 8.2 1.1 0.9 25.6 67.6 10.8 6.3 8.4 24.6 5.0 4.7 Damen et al. (TSN RGB) [6] 2.4 9.6 0.9 1.2 25.3 68.3 7.6 6.1 10.4 29.5 8.8 6.7 DMI-UNICT 7.3 18.8 2.5 4.0 27.2 69.3 13.6 9.2 12.4 30.7 8.7 8.9 Ours (Predictive) 6.1 18.0 1.6 2.9 27.5 71.1 12.3 8.4 10.8 30.6 8.6 8.7 Ours (Predictive + Transitional) 7.2 19.3 2.2 3.4 28.4 70.0 11.6 7.8 12.4 32.2 8.4 9.9 EPIC-KITCHENS results on hold-out unseen test set S2.The official ranking is based on the action top 1 accuracy score (A@1). A@1: top-1 accuracy, A@5: top-5 accuracy, P: precision, R: recall. Challenge website details: https://competitions. codalab.org/competitions/20071. Note that our best model was submitted under the anonymous nickname masterchef.

	Model	Accuracy
	Random baseline	2.1
	Vondrick et al. [43]	8.1
	Abu Farha et al. (CNN) [7]	27.0
	Abu Farha et al. (RNN) [7]	30.1
	Ours (Transitional (AR))	23.9
	Ours (Predictive)	31.9
	Ours (Predictive + Transitional (AR))	32.3
	Ours (Transitional (AR with GT))	43.0

Table 5 :

 5 Comparison to state-of-the-art on the Breakfast. We

Acknowledgment. The project was partially supported by the Louis Vuitton -ENS Chair on Artificial Intelligence, the ERC grant LEAP (No. 336845), the CIFAR Learning in Machines&Brains program, and the European Regional Development Fund under the project IMPACT (reg.

no. CZ.02.1.01/0.0/0.0/15 003/0000468).