Aseem Baranwal

James Currie

Lucas Mol

Pascal Ochem

Narad Rampersad

Jeffrey Shallit

Antisquares and Critical Exponents

Keywords: antisquare, critical exponent, binary complement, binary word, avoidability, repetition threshold, enumeration, minimal forbidden word

The (bitwise) complement x of a binary word x is obtained by changing each 0 in x to 1 and vice versa. An antisquare is a nonempty word of the form x x. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is (5 + √ 5)/2. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number.

We say a binary word is good if the only antisquares it contains are 01 and 10. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length n and determine the repetition threshold between polynomial and exponential growth for the number of good words.

Introduction

Let x be a finite nonempty binary word. We say that x is an antisquare if there exists a word y such that x = y y, where the overline denotes a morphism that maps 0 → 1 and 1 → 0. For example, 011100 is an antisquare. The order of an antisquare y y is defined to be |y|, where |y| denotes the length of y.

Avoidance of antisquares has been studied previously in combinatorics on words. For example, [START_REF] Mousavi | Decision algorithms for Fibonacci-automatic words, I: Basic results[END_REF] proved that the infinite Fibonacci word

f = 01001010 • • • ,
the fixed point of the morphism 0 → 01, 1 → 0, has exactly four antisquare factors, namely, 01, 10, 1001, and 10100101. More generally, all the antisquares in Sturmian words have recently been characterized in [START_REF] Hieronymi | Decidability for Sturmian words[END_REF]. On the other hand, [START_REF] Ng | New results on pseudosquare avoidance[END_REF] classified those infinite binary words containing the minimum possible numbers of distinct squares and antisquares.

It is easy to see that no infinite binary word, except the trivial families given by (0 + ϵ)1 ω and (1 + ϵ)0 ω , can contain at most one distinct antisquare. (Here the notation x ω refers to the right-infinite word xxx • • • .) However, once we move to two distinct antisquares, the situation is quite different. We have the following: Proposition 1. There are exponentially many finite binary words of length n having at most two distinct antisquares, and there are uncountably many infinite binary words with the same property.

Proof: It is easy to see that every binary word in {1000, 10000} * has only the antisquares 01 and 10, which proves the first claim.

For the second, consider the uncountable set of infinite words {1000, 10000} ω . (Here, by S ω for a set S of nonempty finite words, we mean the set of all infinite words arising from concatenations of elements of S.) Furthermore, it is easy to see that if an infinite binary word, other than 001 ω and its complement, contains exactly two antisquares, then these antisquares must be 01 and 10. Call a binary word good if it contains no antisquare factors, except possibly 01 and 10. This suggests studying the following problem.

Problem 2. Find the repetition threshold for good words.

The repetition threshold for a class of (finite or infinite) words is defined as follows. First, we say that a finite word w = w[1.

.n] has period p ≥ 1 if w[i] = w[i + p] for 1 ≤ i ≤ n -p. The smallest period of a word w is called the period, and we write it as per(w). The exponent of a finite word w, written exp(w) is defined to be |w|/ per(w). We say a word (finite or infinite) is α-free if the exponents of its nonempty factors are all < α. We say a word is α + -free if the exponents of its nonempty factors are all ≤ α. The critical exponent of a finite or infinite word x is the supremum, over all nonempty finite factors w of x, of exp(w); it is written ce(x). Finally, the repetition threshold for a language L of infinite words is defined to be the infimum, over all x ∈ L, of ce(x).

The critical exponent of a word can be either rational or irrational. If it is rational, then it can either be attained by a particular finite factor, or not attained. For example, the critical exponent of both • the Thue-Morse word t = 0110100110010110100101100 • • • , fixed point of the morphism 0 → 01, 1 → 10; and

• the variant Thue-Morse word vtm = 2102012101202102012021012 • • • , fixed point of the morphism 2 → 210, 1 → 20, 0 → 1 is 2, but it is attained in the former case and not attained in the latter. If the critical exponent α is attained, we typically write it as α + .

In 1972, [START_REF] Dejean | Sur un théorème de Thue[END_REF] wrote a classic paper on combinatorics on words, where she determined the repetition threshold for the language of all infinite words over {0, 1, 2}-it is 7 4 + -and conjectured the value of the repetition threshold for the languages Σ * k for k ≥ 4, where Σ k = {0, 1, . . . , k -1}. Dejean's conjecture was only completely resolved in 2011, in [START_REF] Rao | Last cases of Dejean's conjecture[END_REF] and [START_REF] Currie | A proof of Dejean's conjecture[END_REF], independently.

The repetition threshold has been studied for many classes of words. To name a few, there are the • Sturmian words, studied in (Carpi and Luca, 2000, Prop. 15);

Antisquares and Critical Exponents

3

• palindromes, studied in Shallit (2016);

• rich words, studied in [START_REF] Currie | The repetition threshold for binary rich words[END_REF];

• balanced words, studied in [START_REF] Rampersad | Critical exponents of infinite balanced words[END_REF][START_REF] Dvořáková | On minimal critical exponent of balanced sequences[END_REF]; and

• complementary symmetric Rote words, studied in [START_REF] Dvořáková | Complementary symmetric Rote sequences: the critical exponent and the recurrence function[END_REF].

For variations on and generalizations of repetition threshold, see [START_REF] Ilie | A generalization of repetition threshold[END_REF]; Badkobeh and Crochemore (2011); [START_REF] Fiorenzi | Bounds for the generalized repetition threshold[END_REF]; [START_REF] Samsonov | On Abelian repetition threshold[END_REF]; [START_REF] Mousavi | Repetition avoidance in circular factors[END_REF]. The goal of this paper is to study the repetition threshold for two classes of infinite words:

• AO ℓ , the binary words avoiding all antisquares of order ≥ ℓ;

• AN n , the binary words with no more than n antisquares.

It turns out that there is an interesting and subtle hierarchy, depending on the values of ℓ and n.

Our work is very similar in flavor to that of [START_REF] Shallit | Simultaneous avoidance of large squares and fractional powers in infinite binary words[END_REF], which found a similar hierarchy concerning critical exponents and sizes of squares avoided. The hierarchy for antisquares, as we will see, however, is significantly more complex.

In this paper, in Sections 2 and 3, we solve Problem 2, and show that the repetition threshold for good words is 2 + α, where α = (1 + √ 5)/2 is the golden ratio. Proving that the repetition threshold for a class of infinite words equals some real number β generally consists of two parts: first, an explicit construction of a word avoiding β + powers. This is often carried out by finding an appropriate morphism h whose infinite fixed point x (or an image of x under a second morphism) has the desired property. Second, if β is rational, then one can prove there is no infinite word avoiding β-powers by a breadth-first or depth-first search of the infinite tree of all words. If β is irrational, however, one must generally be more clever.

In Section 4 we determine the repetition threshold for binary words avoiding all antisquares of order ≥ ℓ, and in Section 5 we determine the repetition threshold for binary words with no more than n antisquares. In Section 6 we completely characterize the minimal antisquares; i.e., the binary words that are antisquares but have the property that all proper factors are good. This characterization is then used in Section 7, where we determine the growth rate of the number of good words of length n. In this section we also show that the repetition threshold between polynomial and exponential growth for good words avoiding α-powers is α = 15 4 ; i.e., there are exponentially many such words avoiding 15 4 + -powers, but only polynomially many that avoid 15 4 -powers.

2 A good infinite word with critical exponent 2 + α

Consider the morphisms below:

φ: 0 → 001 g: 0 → 01 1 → 01 1 → 11.
Let us write φ ω (0) for the (unique) infinite fixed point of φ that starts with 0. We claim that the infinite word w = g(φ ω (0)) does not have antisquares other than 01 and 10, and has critical exponent 2 + α, where α = (1 + √ 5)/2. The infinite word w is Fibonacci-automatic, in the sense of [START_REF] Mousavi | Decision algorithms for Fibonacci-automatic words, I: Basic results[END_REF], so we can apply the Walnut theorem-prover [START_REF] Mousavi | Automatic theorem proving in Walnut[END_REF] to establish this claim. For more about Walnut, see [START_REF] Shallit | The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut[END_REF].

We start with the Fibonacci automaton for φ ω (0), as displayed in Figure 1. Let us name the above automaton FF.txt, and store it in the Word Automata Library of Walnut. We can verify the correctness of this automaton as follows. First, we claim that φ ω (0) = 0f . To see this, let f denote the morphism that maps 0 → 010, 1 → 01; i.e., the morphism f is the square of the Fibonacci morphism. One can easily verify the identities φ n (0) = 0f n (0)0 -1 and φ n (01) = 0f n (10)0 -1 by simultaneous induction, whence follows the claim. We can then use Walnut to verify the correctness of the automaton FF with the command

eval verifyFF "?msd_fib FF[0]=@0 & Ai FF[i+1]=F[i]":
which returns TRUE.

Now we can use

Walnut to create a Fibonacci automaton for w.

morphism g "0->01 1->11": image GF g FF:

The resulting automaton is called GF.txt and is displayed in Figure 2.

0/0 0 1/1 1 2/0 0 3/0 1 4/1 0 5/1 1 0, 1 6/1 0 7/0 1 1 0 0 8/1 1 1 9/1 0 1 0 1 10/0 0 1 0 Fig. 2: Fibonacci automaton for w = g(φ ω (0)).
Theorem 3. The word w does not contain antisquares other than 01 and 10, and has critical exponent 2 + α.

Proof: We write a Walnut formula asserting that there exists an antisquare of order ≥ 2, as follows:

eval antisq "?msd_fib Ei,n (n>=2) & At (t<n) => GF[i+t]!=GF[i+n+t]":
This returns FALSE, so there are no antisquares of order ≥ 2.

We now compute the periods that are associated with factors that have exponent ≥ 3.

eval gfper "?msd_fib Ei (p>=1) & (Aj (j<=2 * p) => GF[i+j]=GF[i+j+p])":
The predicate above produces the automaton in Figure 3, which shows that these periods are of the form 10010 * in Fibonacci representation.

6

Aseem Baranwal et al.

Next, we compute the pairs (n, p) such that w contains a factor of length n + p with period p of the form 10010 * and n + p is the longest length of any factor with this period. reg pows msd_fib "0 * 10010 * "; def maximalreps "?msd_fib Ei (Aj (j<n

) => GF[i+j] = GF[i+j+p]) & (GF[i+n] != GF[i+n+p])": eval highestpow "?msd_fib (p>=1) & $pows(p) & $maximalreps(n,p) & (Am $maximalreps(m,p) => m <= n)":
The automaton produced by the predicate highestpow is given in Figure 4. The strings accepted by this automaton, omitting the leading [0, 0], are as follows:

0 [0,0] 1 [1,0] 2 [0,0] 3 [0,1] 4 [0,0] 5 [0,0] 6 [1,0] 7 [0,1] 8 [1,1] 9 [0,1] [0,0] 10 [0,0] 11 [1,0] [0,0] [1,0] [0,0]
•

[1, 0][0, 0][0, 1][0, 0][0, 0][0, 1] • [1, 0][0, 0][0, 1][0, 0][0, 0][1, 1][0, 0] • [1, 0][0, 0][0, 1][0, 0][1, 0][0, 1]([1, 0][0, 0]) k [0, 0][1, 0][0, 0], k ≥ 0 • [1, 0][0, 0][0, 1][0, 0][1, 0][0, 1]([1, 0][0, 0]) k [0, 0][0, 0], k ≥ 0.
These correspond, respectively, to the values

• (n, p) = (13, 6) = (2F 6 -3, 2F 4 ) • (n, p) = (23, 10) = (2F 7 -3, 2F 5 ) • (n, p) = (F 2k+10 + F 3 + 3≤i≤k+3 F 2i , F 2k+8 + F 2k+5 ) = (2F 2k+9 -3, 2F 2k+7 ) for k ≥ 0 • (n, p) = (F 2k+9 + 3≤i≤k+3 F 2i-1 , F 2k+7 + F 2k+4 ) = (2F 2k+8 -3, 2F 2k+6 ) for k ≥ 0.
where we have used the well-known Fibonacci identities

F 2 + F 4 + F 6 + • • • + F 2t = F 2t+1 -1 F 1 + F 3 + F 5 + • • • + F 2t-1 = F 2t .
Now the exponent of these finite factors is (n + p)/p, which is

2F j + 2F j-2 -3 2F j-2
for j ≥ 6. These quotients tend to 2 + α from below, and hence the critical exponent is 2 + α.

Optimality of the previous construction

In this section we show that the critical exponent of the word constructed in Section 2 is best possible; i.e., that every infinite good word has critical exponent at least 2 + α. It is somewhat easier to work with bi-infinite words, so we begin with results concerning bi-infinite words and then explain at the end of the section how to obtain the desired result for right-infinite words. If S is a set of nonempty finite words, then by ω S ω we mean the set of bi-infinite words made up of concatenations of the elements of S.

Theorem 4. Every bi-infinite binary word avoiding 4-powers and {11, 000, 10101} has the same set of factors as f .

Proof: First, we check that f avoids 4-powers and {11, 000, 10101}.

Now consider a bi-infinite binary word w avoiding 4-powers and {11, 000, 10101}. Since w avoids 11, we have w ∈ ω {01, 0} ω . Thus there exists a bi-infinite word v such that w = h(v), where h is the morphism 0 → 01, 1 → 0. Now it suffices to show that the pre-image v also avoids 4-powers and {11, 000, 10101}. Clearly, v avoids 4-powers, since otherwise w = h(v) would contain a 4-power. Now we show by contradiction that v avoids every factor in {11, 000, 10101}.

• If v contains 11, then v contains 110. So w contains h(110) = 0001-a contradiction, since w avoids 000.

• If v contains 000 then w contains h(000) = 010101-a contradiction, since w avoids 10101.

• Proof: Notice that F is closed under bitwise complement and reversal. Let w be a bi-infinite binary word avoiding 4-powers and F . Suppose that w contains 001011.

• Since 1001 ∈ F and 0110 ∈ F , the word w contains 00010111.

• Since 0000 and 1111 are 4-powers, the word w contains 1000101110.

This is a contradiction since 1000101110 ∈ F . So w avoids 001011. By considering the complement, the word w also avoids 110100. Now suppose that w contains 110111011.

• Since 0110 ∈ F , the word w contains 11101110111.

• Since 1111 is a 4-power, the word w contains 0111011101110.

• Since 0011 ∈ F and 1100 ∈ F , the word w contains 101110111011101.

This is a contradiction since 101110111011101 ∈ F . So w avoids 110111011. By considering the complement, the word w also avoids 001000100. Thus, w avoids 4-powers and 0110,1100,1001,010101,101010,001011,110100,110111011, 001000100}.

F ′ = {0011,
Notice that F ′ is closed under complement and reversal. By symmetry, we now suppose that w contains 11. Notice that 111, 11011, and 1101011 are the only possible factors of w that start with 11, end with two identical letters, and contain two identical letters only as a prefix and a suffix. In particular, the word w avoids 00. Moreover, the blocks of consecutive 1's have length 1 or 3. So w ∈ ω {01, 11} ω . Thus w = g(v) for some bi-infinite binary word v.

Since w avoids 4-powers, the word v also avoids 4-powers. Moreover,

• g(11) = 1111 is a 4-power,

• g(000) = 010101 belongs to F ,

• g(10101) = 1101110111 contains 110111011 ∈ F ′ .

So v also avoids {11, 000, 10101}. By Theorem 4, the word v has the same set of factors as f . That is, the word w has the same set of factors as g(f ).

Theorem 6. Every good bi-infinite binary word has critical exponent at least 2 + α.

Proof: Suppose that w is a good bi-infinite binary word; that is, it contain no antisquares except possibly 01 and 10. Also assume w has critical exponent smaller than 2+α. Consider the set F from Lemma 5 and notice that F \ {101110111011101, 010001000100010} contains only antisquares. So w avoids 4-powers and F \ {101110111011101, 010001000100010}. Moreover, w avoids 101110111011101 = (1011) 15/4 since 15/4 > 2 + α. By symmetry, w also avoids 010001000100010. So w avoids 4-powers and F . By Lemma 5, w has the same set of factors as either g(f ) or g(f ). So w has critical exponent 2+α.

Corollary 7. Every (right-) infinite good binary word has critical exponent at least 2 + α.

Proof: Let w be an infinite good binary word, and let RecFac(w) denote the set of its recurrent factors. That is, the set RecFac(w) consists of the factors of w that appear infinitely often in w. Then for any y ∈ RecFac(w), we see that y has arbitrarily large two-sided extensions in RecFac(w). By a 'two-sided' analogue of König's infinity lemma, there exists a bi-infinite word w ′ such that every factor of w ′ is an element of RecFac(w). By Theorem 6, the bi-infinite word w ′ has critical exponent at least 2 + α, and thus so does the infinite word w.

The class AO ℓ

Instead of avoiding all antisquares of order greater than one, we could consider avoiding arbitrarily large antisquares.

Proposition 8. Every infinite binary word avoiding 7 3 -powers contains arbitrarily large antisquares.

Proof: By a result of [START_REF] Karhumäki | Polynomial versus exponential growth in repetition-free binary words[END_REF], we know that every infinite binary word avoiding 7 3 -powers can be written in the form

x 1 µ(x 2 µ(x 3 µ(• • • )) • • • )
, where x i ∈ {ϵ, 0, 1, 00, 11} and µ is the Thue-Morse morphism, defined by µ : 0 → 01, 1 → 10. It follows that every such word must contain arbitrarily large factors of the form µ n (0). But every word µ n (0) for n ≥ 1 is an antisquare.

On the other hand, we can prove the following result on the class AO ℓ of binary words avoiding antisquares of order ≥ ℓ: Theorem 9. There exists an infinite β + -free binary word containing no antisquare of order ≥ ℓ for the following pairs (ℓ, β):

(a) (2, 2 + α) (b) (3, 8/3) (c) (5, 5/2) (d) (6, 7/3)
These are all optimal.

Proof: Item (a) was already proved in Section 2. For each of the remaining pairs (ℓ, β), we apply a morphism ξ ℓ to any ternary squarefree infinite word w and check that it has the desired properties. The morphisms are given in Table 1. The columns are ℓ, where the word contains no antisquares of order ≥ ℓ; β, where the word avoids β + powers; s, the size of the uniform morphism; and the morphism.

ℓ β s morphism name morphism 3 8/3 36 ξ 3 0 → 001001010011001010010011001001010011 1 → 001001010010011001010011001010010011 2 → 001001010010011001001010011001010011 5 5/2 19 ξ 5 0 → 0010110100101101011 1 → 0010110100101100101 2 → 0010110011001010011 6 7/3 37 ξ 6 0 → 0010011010010110100110110011010011011 1 → 0010011010010110100110110010011010011 2 → 0010011010010110100110110010011001011
Tab. 1: Morphisms generating words in AO ℓ .

To verify the β + -freeness of ξ ℓ (w) we use (Mol et al., 2020, Lemma 23). In order to do so, we check that ξ ℓ is synchronizing and that ξ ℓ (u) is β + -free for every squarefree ternary word u of length t, where t is specified by (Mol et al., 2020, Lemma 23). In order to show that ξ ℓ (w) contains no antisquares of order ≥ ℓ, we find a length m such that if v and its complement are both factors of ξ ℓ (w), then |v| ≤ m. We can then check that ξ ℓ (w) contains no antisquares of order ≥ ℓ by exhaustively checking all factors of length at most 2m. The parameters t and m for each ξ ℓ are given in Table 2 The optimality of item (a) was already proved in Section 3. The optimality of the remaining items can be established by depth-first search. For each pair (ℓ, β), a longest word containing no antisquares of order ≥ ℓ, but avoiding β-powers (instead of β + ), is given in Table 3. The columns give ℓ, β, the length L of a longest such word, and a longest such word.

The class AN n

In this section, we consider the class AN n of binary words containing no more than n distinct antisquares as factors.

Theorem 10. There exists an infinite β + -free binary word containing no more than n antisquares for the following pairs (n, β):

(a) (2, 2 + α) (b) (3, 3) (c) (6, 8/3) (d) (9, 38/15) (e) (10, 5/2) (f) (15, 17/7) (g) (16, 7/3).
These are all optimal.

Proof: Item (a) was already proved in Section 2. For the remaining cases, the proof is similar to that of Theorem 9: for each pair (n, β), we apply a morphism ζ n to any ternary squarefree infinite word w and check that it has the desired properties. The morphisms are given in Table 4. The columns are n, the largest number of allowed antisquares; β, where the word avoids β + powers; s, the size of the uniform morphism; and the morphism. Tab. 4: Morphisms generating words in ANn.

To verify the β + -freeness of ζ n (w) we use (Mol et al., 2020, Lemma 23). In order to do so, we check that ζ n is synchronizing and that ζ n (u) is β + -free for every squarefree ternary word u of length t, where t is specified by (Mol et al., 2020, Lemma 23) The optimality of item (a) was already proved in Section 3. The optimality of the remaining items can be established by depth-first search. For each pair (n, β), a longest word containing at most n antisquares, but avoiding β-powers (instead of β + ), is given in Table 6. The columns give n, β, the length L of a longest such word, and a longest such word.

Minimal antisquares

Consider the language L of all finite good words. In this section we determine the minimal antisquares or minimal forbidden factors for L [START_REF] Mignosi | Words and forbidden factors[END_REF]. These are the words w such that w is an antisquare, but w properly contains no antisquare factors, except possibly 01 and 10. This characterization will be useful for enumerating the number of length-n words in L.

The goal is to prove the following theorem:

Theorem 11. The minimal antisquares are, organized by order n, as follows:

• n = 1: {01, 10}

• n = 2: {0011, 0110, 1001, 1100}

• n = 3: {010101, 101010}

• n = 4: ∅

• n ≥ 5: all the 2n conjugates (cyclic shifts) of 0 n-2 101 n-2 01.

We start with some basic results about antisquares.

Lemma 12. If x is an antisquare, so is every conjugate of x.

Proof: Write x as ayay for some (possibly empty) word y. Then a cyclic shift by one symbol gives yaya, which is clearly an antisquare. Repeating this argument |x| times gives the result.

Lemma 13. A word w is a minimal antisquare if and only if all conjugates of w are minimal antisquares.

Proof: Let w = uu. Let us prove the forward direction first. Assume, contrary to what we want to prove, that w is a minimal antisquare, but some rotation of w contains a shorter antisquare, other than 01 and 10.

Let rs be an antisquare of minimum length with |rs| > 2 that is not a factor of w, but is a factor of some rotation of w. Then we can write w = sxr with r, s, x ̸ = ϵ. There are three cases to consider:

|r| ≥ |u|: Let t be defined by r = tu. Then w = uu = sxtsxt, where rs = tsxts is an antisquare. If t = ϵ, then rs = sxs; hence w = sxsx contains the antisquare sxs. This is a contradiction, since we assumed w does not have a shorter antisquare, but sxs is an antisquare in w with s, x ̸ = ϵ. Therefore t ̸ = ϵ.

Since w and rs are both antisquares, they have even length. Therefore |x| is even. Consider the factorization x = x 1 x 2 with |x 1 | = |x 2 |. Then rs = tsxts = tsx 1 x 2 ts is an antisquare, where |tsx 1 | = |x 2 ts|. Therefore, tsx 1 must end with ts and x 2 ts must begin with ts, giving the antisquare tsts, which is not 01 or 10 (since t, s ̸ = ϵ), and is shorter than rs. This contradicts our assumption that rs is the smallest such antisquare.

|s| ≥ |u|: Let s be defined by s = ut. Then w = uu = txrtxr. Now rs = rtxrt is an antisquare, and hence the complement rs = rtxrt is also an antisquare. Let r ′ = rtxr and s ′ = t. So we can write w = txrtxr = s ′ xr ′ where r ′ s ′ is an antisquare of the same length as rs, and |r ′ | > |u|. This reduces the problem to the previous case. and the remaining cases correspond to certain conjugates of 0 n 101 n 01 for n ≥ 3, already listed in the statement of the theorem.

Seven runs: then x = 0 i 1 j 0 k 1 i+l 0 j 1 k 0 l . Again, if i, j ≥ 2, or j, k ≥ 2, or k, l ≥ 2, then x contains a shorter antisquare 0011 or 1100. Since i + l ≥ 2, the same argument rules out k ≥ 2 and j ≥ 2. So the only cases remaining are 1,1,1,1),(1,1,1,n),(n,1,1,1),(n,1,1,n)} for n ≥ 2. The first case (1, 1, 1, 1) corresponds to 010110101, which has the antisquare 0110, and it is easy to verify that the remaining cases are certain conjugates of 0 n+1 101 n+1 01 for n ≥ 3, already listed in the statement of the theorem.

(i, j, k, l) ∈ {(
It now remains to handle the case of more than 7 runs. By Lemma 14 x has at least 10 runs. This involves a rather tedious examination of cases, based on the following three simple observations: Proof: If condition (a) is not satisfied, then z consists of isolated occurrences of numbers ≥ 2, separated by blocks of consecutive 1's. We assume this in what follows.

If z both begins and ends with a number ≥ 2, then zz satisfies (a). Thus we may assume that z either begins or ends with 1 (or both).

Suppose z contains the block 1111. Then zz contains the block b1111c for b, c ≥ 1, and hence satisfies (b). Thus we may assume that the maximal 1-blocks in z are of length 1, 2, or 3.

Suppose all the maximal 1-blocks of z are of length 1 or 3. If z begins with 1 and ends with b ≥ 2, then z cannot be of odd length, and similarly if z ends with 1 and begins with b ≥ 2. So z must begin and end with 1.

Fig. 1 :

 1 Fig. 1: Fibonacci automaton for φ ω (0).

Fig. 3 :

 3 Fig. 3: Automaton for periods associated with 3 + -powers in w.

Fig. 4 :

 4 Fig. 4: Automaton for pairs (n, p) associated with highest powers in w.

  If v contains 10101 then v contains 0101010, since v avoids 11. So w contains h(0101010) = 01001001001. Since w avoids 11, we see that w contains 010010010010 = (010) 4 -a contradiction, since w avoids 4-powers. Lemma 5. Every bi-infinite binary word avoiding 4-powers and F = {0011, 0110, 1100, 1001, 010101, 101010, 1000101110, 0111010001, 101110111011101, 010001000100010} has the same set of factors as g(f ) or g(f ).

  Longest words avoiding β-powers and containing no antisquares of order ≥ ℓ.

  n

  (a) if r(x) contains two consecutive terms, both ≥ 2, then x contains the shorter antisquare 0011 or 1100; (b) if r(x) contains six consecutive terms a1bc1d with a ≥ c and b ≤ d, then x contains the shorter antisquare 0 c 10 b 1 c 01 b or its complement. (c) if r(x) contains an interior occurrence of 2, then x contains the antisquare 0110 or 1001. Suppose x = uu. If z = r(u) is of odd length, then zz = r(x). If z = r(u) is of even length, then writing z = ayb with a, b single numbers, we have r(x) = ay(a + b)yb. When we speak of a maximal 1-block in what follows, we mean one that cannot be extended by additional 1's to the left or right. It now suffices to prove the following two lemmas: Lemma 16. Let z ∈ N * , and suppose |z| ≥ 5 is odd. Then zz contains either (a) two consecutive terms that are ≥ 2, or (b) six consecutive terms a1bc1d with a ≥ c and b ≤ d.

  Since |z| ≥ 5, we know z has a prefix of the form 1c1d and a suffix of the form a1b1, where a, b, c, d ≥ 1. Hence zz contains the block a1b11c1d. If b ≤ c, then the block a1b11c fulfills condition (b); if b ≥ c, then the block b11c1d fulfills condition (b). Thus there must be a maximal 1-block of length 2 in z. Then zz contains two blocks, one of the form a1b11c and one of the form b11c1d, where a, d ≥ 1 and b, c ≥ 2. If b ≤ c, then the block a1b11c fulfills condition (b); if b ≥ c, then the block b11c1d fulfills condition (b).

  . Parameters for checking correctness of ξ ℓ .

	morphism ℓ	β	t	m
	ξ 3 ξ 5 ξ 6	3 8/3 8 5 5/2 10 16 6 6 7/3 14 26
	Tab. 2:

  . In order to show that ζ n (w) contains at most n distinct antisquares, we find a length m such that if v and its complement are both factors of ζ n (w), then |v| ≤ m. We can then enumerate the antisquares appearing in ζ n (w) and check that there are at most n of them. The parameters t and ℓ for each ζ n are given in Table5.

	morphism n	β	t	m
	ζ 3 ζ 6 ζ 9 ζ 10 ζ 15 ζ 16	3 6 9 38/15 9 17 3 6 4 8/3 8 6 10 5/2 10 17 15 17/7 11 12 16 7/3 14 13
	Tab. 5: Parameters for checking correctness of ζn.

  Longest words with at most n antisquares and avoiding β-powers.

		β	L	example
	5	3	17	00101001010010011
	8	8/3	52	0010010100110010100110011010011001101011001101011011
	9 38/15 407 00100101001101001010011010011001101001010011001010011 00110100101001101001100110101100110100101001101001100 11010010100110010100110011010010100110100110011010110 01101001010011010011001101001010011010011001101011001 10100101001101001100110100101001100101001100110100101 00110100110011010110011010010100110100110011010010100 11001010011001101001010011010011001101001010011001010 011001101001010011001101001101011011
	14	5/2	92	001101001011001101100110100101100110110011010011 01100110100101100110110011010011011001101100
	15 17/7 156 0010110011010010110010011010011001001101001011001001 1001011001001101001011001001101001100100110100101100 1001100101100100110100101100100110010110010011001001
	16	7/3	38	00101100101101001011001101001011001011
		Tab. 6:

* The research of JC is supported by NSERC Grant 2017-03901. † The research of NR is supported by NSERC Grant 2019-04111. ‡ The research of JS is supported by NSERC Grant 2018-04118.

Aseem Baranwal et al. |s| < |u|, |r| < |u|: In this case we can write u = sy and u = zr where y, z ̸ = ϵ. This means that u ends in r and u begins with s, implying that w contains the antisquare rs. This contradicts the assumption that w does not contain a shorter antisquare.

The reverse direction is easy. If w contains a shorter antisquare, other than 01 and 10, then at least one rotation of w also has the same antisquare.

We introduce some terminology. A run in a word is a maximal block of consecutive identical symbols. The run-length encoding r : Σ * → N * , where N = {1, 2, 3, . . .} is a map sending a word x to the list of the lengths of the consecutive runs in x. For example, r(access) = 1212.

Lemma 14. If a nonempty word x is an antisquare, then the number of runs it contains must be congruent to 2 or 3 (mod 4).

Proof: Write x = uu and consider the runs in u. If u has 2k + 1 runs, then so does u. Furthermore, u ends in a different letter than the start of u. Hence x has + 2 runs.

Otherwise u has 2k runs. Then the last letter of u is the same as the first letter of u. Hence x has 4k -1 runs.

Lemma 15. The word 0 k 10 1 k 01 is a minimal antisquare for k ≥ 3.

Proof: It is easy to see that x = 0 k 10 1 k 01 is an antisquare. Suppose k ≥ 3 and suppose x has an antisquare proper factor w other than 01 and 10. Now x has six runs, so by Lemma 14 we know that w has either two, three, or six runs.

If w has two runs, it must be of the form a i a i for i ≥ 2, but inspection shows that x has no factor of that form.

If w has three runs, it must be of the form a i a i+j a j for some i, j ≥ 1. The only possibility is i = 1, i + j = k, j = 1, which forces k = 2, a contradiction.

Finally, if w has six runs, then w = 0 ℓ 101 ℓ 01 for some ℓ < k, which would not be a factor of x.

We are now ready to complete the proof of Theorem 11. We say x has an interior occurrence of y if we can write x = wyz for nonempty words w, z.

Proof Proof of Theorem 11.: By combining Lemmas 12, 13, and 15, and verifying the listed cases for n ≤ 4, we see that all the words given in the statement of the theorem are minimal antisquares.

It now remains to see that there are no other minimal antisquares. The idea is to classify antisquares x by the number of runs. In what follows, we assume, without loss of generality, that x begins with 0.

Two runs: then x = 0 i 1 i for some i ≥ 1. If i ≥ 3 then x contains the antisquare 0011. So the only minimal antisquares are 01 and 0011.

Three runs: then x = 0 i 1 i+j 0 j . If either i or j is at least 2, then x contains the antisquare 0011 or 1100. So the only minimal antisquare is 0110.

Six runs: then x = 0 i 1 j 0 k 1 i 0 j 1 k . If i, j ≥ 2 then x contains the antisquare 0011, and similarly if j, k ≥ 2 and k, i ≥ 2. It follows that (i, j, k) ∈ {(1, 1, 1), (1, 1, n), (1, n, 1), (n, 1, 1)} for n ≥ 2. The cases (1, 1, 2), (1, 2, 1), (2, 1, 1) are ruled out by an antisquare of the form 1001 or 0110. So (i, j, k) ∈ {(1, 1, 1), (1, 1, n), (1, n, 1), (n, 1, 1)} for n ≥ 3. The case (1, 1, 1) corresponds to the word 010101, Aseem Baranwal et al. Proof: If condition (a) is not satisfied, then z consists of isolated occurrences of numbers ≥ 2, separated by blocks of consecutive 1's. We assume this in what follows.

If z begins and ends with 1, then z ′ has an interior occurrence of 2, so (c) is satisfied. So assume this is not the case.

If z begins 1b with b ≥ 2, then by the previous paragraph it must end in c ≥ 2. Then z ′ has an occurrence of (c + 1)b, so (a) is satisfied. Exactly the same argument works if z ends with b1 with b ≥ 2. So assume neither of these hold.

If z has an interior occurrence of 11111, then z ′ has an occurrence of c11111, fulfilling condition (b). If z begins 11111c for c ≥ 1, it must end with d ≥ 2, so z ′ has an occurrence of (d + 1)1111c, fulfilling (b). The analogous argument holds if z ends c11111. So all maximal 1-blocks in z are of length ≤ 4.

Now we consider the case that z has a maximal block of the form 1111. If this occurrence is interior in z, then z ′ contains the block b1111c for b, c ≥ 1, and hence satisfies (b). If z has the prefix 1111, then z cannot end in 1 by above. Hence, since z has even length, it must contain another maximal 1-block of even length, which must be interior. Since we have already ruled out the possibility of an interior occurrence of 1111, it must be an interior 1-block of size 2. But then z ′ has a block of the form a1b11c1d where a, d ≥ 1 and b, c ≥ 2. As in the previous lemma, if b ≤ c, then the block a1b11c fulfills condition (b); if b ≥ c, then the block b11c1d fulfills condition (b). The analogous argument holds if the occurrence of 1111 is a suffix. Hence z contains no maximal 1-block of size 4.

Thus we may assume that the maximal 1-blocks in z are of length 1, 2, or 3.

If z has a maximal 1-block of size 2, then since |z| is even, it must have a second maximal 1-block of size 2. Then z ′ has a factor of the form a1b11c1d where a, d ≥ 1 and b, c ≥ 2, and by the argument above, this satisfies condition (b).

Hence all the maximal 1-blocks of z are of size 1 or 3. Hence all the maximal 1-blocks of z are size 1 or 3. Since z has even length, exactly one of its first and last symbols must be 1. We know from above that z cannot begin 1b or end b1 with b ≥ 2. Applying the two lemmas to the case where x = u u and z = r(u) completes the proof of Theorem 11.

Enumerating words with only two distinct antisquares

In this section we obtain some enumeration results for good words. Here the notation ω x refers to the left-infinite word • • • xxx.

Proposition 18. If a bi-infinite good word w contains the factor 001011, then w = ω 0101 ω .

Proof: Consider a maximal factor of w of the form 0 k 101 k , with 2 ≤ k < ∞. By maximality and by symmetry, we can assume that w contains 0 k 101 k 0. This factor is not extendable to the right:

• 0 k 101 k 00 contains the antisquare 1100 as a suffix.

• 0 k 101 k 01 is an antisquare. This is a contradiction to k < ∞, so w = ω 0101 ω .

Theorem 19. There are Θ(ψ n ) good words of length n, where ψ . = 1.465571231876768 is the supergolden ratio, root of the equation X 3 = X 2 + 1.

Proof: Let F = {0011, 1100, 0110, 1001, 010101, 101010, 001011, 110100}. By Theorem 11, F contains the minimal antisquares of order 2 and 3, and the minimal antisquares of order at least 4 contain 001011 or 110100. Thus, the binary words avoiding F are exactly the good words that avoid {001011, 110100}.

By Proposition 18, there are not enough good words containing 001011 to contribute to the growth rate of good words. This also holds for good words containing the symmetric factor 110100. Thus, good words and binary words avoiding F have the same growth rate.

To enumerate binary words avoiding F , we instead enumerate the 'Pansiot codes' of these words. If

For example, the binary word 010 is the Pansiot code for the two binary words 0011 and 1100.

The Pansiot codes of binary words avoiding F are the binary words avoiding {010, 101, 11111, 01110}. These words consist of blocks of 0's of length at least 2 and blocks of 1's of length 2 or 4. Consider the number C n of such words ending with 00. They are obtained from shorter words by adding a suffix 0, 1100, or 111100. From the relation

Next we show that the threshold exponent at which the number of good words becomes exponential is 15 4 . (For overlap-free words, the threshold is 7 3 ; see [START_REF] Karhumäki | Polynomial versus exponential growth in repetition-free binary words[END_REF].) Theorem 20. Let w be any squarefree word over the alphabet {0, 1, 2}. Apply the map h that sends

The resulting word is good, and has exponent at most 15 4 , and it is exactly 15 4 if |w| ≥ 5.

Aseem Baranwal et al.

Proof:

The goodness of h(w) can be seen by inspection. Regarding the exponent 15 4 , suppose that h(w) contains a 15 4 power zzzz ′ , where z ′ is a prefix of z. Note that in h(w) the factor 101 can only occur at the 'boundary' between h(a) and h(b), where a, b ∈ {0, 1, 2}. So we have two cases:

Case 1: z contains 101. Write z = x101y. Then h(w) contains the square 01yx101yx1, where 01yx1 = h(Z) for some factor Z of w. Then w contains the square ZZ, which is a contradiction.

Case 2: z does not contain 101. Clearly z = h(a) or z = h(a)0 for some a ∈ {0, 1, 2} is not possible, so z is contained within some h(a), where a ∈ {0, 1, 2}. The only such 15 4 -power is h(2)0 = (0100) 3 010, which establishes the claim.

Corollary 21. There are exponentially many length-n 15 4 + -free good words.

To show that there are only polynomially many length-n good words avoiding 15 4 -powers we need a version of the results in Section 3 for finite words rather than bi-infinite words. Let g and φ be defined as in Section 2 and let g ′ be the morphism that maps 0 → 01 and 1 → 00.

Lemma 22. Let w be a 4-free word of length ≥ 15 that contains no antisquares other than 01 and 10. Then w can be written as either w = w 1 g(v)w 2 or w = w 1 g ′ (v)w 2 for some v, where |w 1 |, |w 2 | ≤ 5.

Proof: By a finite search, one verifies that any w satisfying the hypotheses of the lemma has a prefix of length ≤ 9 that contains either 0001 or 0111. Suppose it contains 0111. Since w avoids the antisquares 0110 and 1001 and the 4-powers 0000 and 1111 we can write w = w 1 0111z, where z is a prefix of a word in {0001, 01, 0111} * and |w 1 | ≤ 5. We claim that z does not contain 0001. Note that |z| ≥ 6.

If z has 0001 as a prefix, then w contains the antisquare 111000. Suppose z has 01 as a prefix. If z has 010001 as a prefix, then w contains the antisquare 0111010001. If z has 01010 as a prefix, then w contains the antisquare 101010, so necessarily z has 010111 as a prefix. Finally, it may be the case that z has 0111 as a prefix. Applying this argument repeatedly to the suffix of w following this new occurrence of 0111, until we no longer have such a suffix of length at least 6, we see that z does not contain 0001. It follows that w can be written as w = w 1 xw 2 , where x ∈ {01, 0111} * (and hence x ∈ {01, 11} * ), and |w 2 | ≤ 5. Thus w = w 1 g(v)w 2 for some v, as required.

A similar argument shows that if w contains 0001 then w = w 1 g ′ (v)w 2 for some v, where |w 1 | ≤ 5 and |w 2 | ≤ 5.

In what follows we will consider words of the form g(v); the analysis for g ′ (v) is similar.

Lemma 23. Let n ≥ 1 and y = g(φ n (x)) for some binary word x with |x| ≥ 5. If y is 15 4 -free, then x is 4-free and can be written in the form x = px ′ s where |p| ≤ 2, |s| ≤ 1 and x ′ has no 000 or 11.

Proof: Clearly x is 4-free. Suppose x contains an occurrence of 000 that is neither a prefix nor a suffix of x. Then φ(x) contains the 4-power 01(001) 3 0 = (010) 4 and hence y contains a 4-power, which is a contradiction. Suppose x contains an occurrence of 11 of the form x = u11v, where |u| ≥ 2 and |v| ≥ 1. Then φ(x) contains 0101 and hence, extending this occurrence of 0101 to the left and right with blocks 001 and 01 and avoiding 4-powers, we see that φ(x) contains 00101010. Indeed, extending two blocks to the left and one block to the right suffices. If n = 1 then g(00101010) contains the 15 4 -power (1011) 3 101, which is a contradiction. If n > 1, then φ(00101010) contains the 4-power (01001) 4 and hence y contains a 4-power, which is a contradiction.

Lemma 24. Let w be a 15 4 -free word of length ≥ 33 that contains no antisquares other than 01 and 10. Then w can be written in the form Theorem 25. There are polynomially many length-n good words avoiding 15 4 -powers.

Proof: Let w be such a word of length n, where n ≥ 33. By Lemma 24 w can be written in the form E) be the maximum number of possible choices for w 1 (resp. w 2 , u i , v i , V ). Then the number of words w is at most AB(CD) r E. There is a constant ρ such that r ≤ ρ log n, so the number of words w is at most ABEn ρ log(CD) . A similar calculation applies when G = g ′ .

Further work

In this paper we have studied antisquares. This situation has an obvious generalization to patterns with morphic and antimorphic permutations, as studied in [START_REF] Currie | Unary patterns with permutations[END_REF]. This could be the subject of a future study.

A companion paper to this one is [START_REF] Currie | Complement avoidance in binary words[END_REF], which investigates complement avoidance in binary words.


Quentin Leroy
email: quentin.leroy@inria.fr

Olivier Buisson
email: obuisson@ina.fr

How does the degree of novelty impacts semi-supervised representation learning for novel class retrieval?

Supervised representation learning with deep networks tends to overfit the training classes and the generalization to novel classes is a challenging question. It is common to evaluate a learned embedding on held-out images of the same training classes. In real applications however, data comes from new sources and novel classes are likely to arise. We hypothesize that incorporating unlabelled images of novel classes in the training set in a semi-supervised fashion would be beneficial for the efficient retrieval of novel-class images compared to a vanilla supervised representation. To verify this hypothesis in a comprehensive way, we propose an original evaluation methodology that varies the degree of novelty of novel classes by partitioning the dataset category-wise either randomly, or semantically, i.e. by minimizing the shared semantics between base and novel classes. This evaluation procedure allows to train a representation blindly to any novel-class labels and evaluate the frozen representation on the retrieval of base or novel classes. We find that a vanilla supervised representation falls short on the retrieval of novel classes even more so when the semantics gap is higher. Semi-supervised algorithms allow to partially bridge this performance gap but there is still much room for improvement.

INTRODUCTION

Deep neural networks have been the de facto algorithm for processing and training data for a variety of tasks and data modalities whether it is image [START_REF] Oquab | Learning and Transferring Mid-level Image Representations Using Convolutional Neural Networks[END_REF][START_REF] Sharif Razavian | CNN Features Off-the-Shelf: An Astounding Baseline for Recognition[END_REF], text [START_REF] Devlin | BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding[END_REF][START_REF] Vaswani | Attention Is All You Need[END_REF], speech [START_REF] Hannun | Deep Speech: Scaling up end-to-end speech recognition[END_REF][START_REF] Zhang | Pushing the Limits of Semi-Supervised Learning for Automatic Speech Recognition[END_REF] , video [START_REF] Alayrac | Self-Supervised MultiModal Versatile Networks[END_REF][START_REF] Arnab | ViViT: A Video Vision Transformer[END_REF][START_REF] Aytar | SoundNet: Learning Sound Representations from Unlabeled Video[END_REF][START_REF] Sun | VideoBERT: A Joint Model for Video and Language Representation Learning[END_REF]. In this study we focus on image data and retrieval tasks. The major impediment is the sheer amount of annotated images necessary to achieve this feat [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF]. Several lines of research have been tackling this issue and have brought new ideas helping to reduce the amount of annotation necessary: active learning refers to algorithms that select most effectively the unlabeled samples for an annotator to annotate [START_REF] Settles | Active Learning Literature Survey[END_REF], few-shot learning refers to algorithms that adapt most rapidly to new classes with a few annotated support samples [START_REF] Vinyals | Matching Networks for One Shot Learning[END_REF][START_REF] Wang | Generalizing from a Few Examples: A Survey on Few-Shot Learning[END_REF], self-supervised learning refers to algorithms that learn from the samples themselves without any annotation [START_REF] Doersch | Unsupervised Visual Representation Learning by Context Prediction[END_REF][START_REF] Doersch | Multi-task Self-Supervised Visual Learning[END_REF][START_REF] Jing | Self-supervised Visual Feature Learning with Deep Neural Networks: A Survey[END_REF], semi-supervised learning refers to algorithms that effectively leverage unlabeled data while also training with supervised data [START_REF] Chapelle | Semi-Supervised Learning[END_REF][START_REF] Laine | Temporal Ensembling for Semi Supervised Learning[END_REF][START_REF] Pham | Meta Pseudo Labels[END_REF][START_REF] Tarvainen | Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results[END_REF].

Deep networks provide a strong baseline for image representation in image retrieval applications [START_REF] Babenko | Neural Codes for Image Retrieval[END_REF] [START_REF] Babenko | Aggregating Deep Convolutional Features for Image Retrieval[END_REF], whether it is visual instance retrieval or more broadly visual category retrieval. Image retrieval, a long tradition in the computer vision community, is the task of retrieving those images in the search corpus that depict the same visual instance as the query.

Visual object category retrieval evaluates more broadly the retrieving of those images containing the same visual object as the query, allowing for a lot more appearance variation between the query and the correct images.

In this paper, we are interested in the retrieval of an object category unseen beforehand in the training corpus used to train the deep embedding. We term this challenging task novel class retrieval; it aims to reflect the setting of real-world applications where incoming image data contains visual content novel compared to curated image corpora used for training deep networks. This setting exists in various applications. Take for example a corpus of digitized material of a cultural institution containing a large variety of historical photographs, drawings, paintings and manuscripts of various eras. Choosing a generic embedding for these original materials for efficient retrieval is a challenging question. These novel materials can be queried by users in unanticipated ways. Understanding these new types of material without additional human annotation is a challenging problem.

We focus on the question: What learning algorithm allows for the most efficient retrieval of novel classes? We devise an original methodology for comparing deep embeddings towards the task of novel class retrieval; We partition an image corpus category-wise, keeping a set of base classes for training the deep embedding and leaving aside a set of novel classes for evaluating the embedding. We get a strict disjoint label space between the training classes and the evaluation classes. The base and novel sets are further split into a training and a test set. More importantly, in each instance of our experiments we carry out two kinds of category splits: a random split partitioning the labeled space at random and a more carefully crafted semantic split that minimizes the information overlap between base and unseen categories to the extent possible (details in section 3).

Our contributions are summarised as follows: 1) We devise an evaluation methodology to evaluate a deep embedding on the task of novel class retrieval, 2) we simulate new visual content by hiding supervision from the deep network and we are able to vary the degree of novelty of novel classes and 3) we compare several deep learning algorithms from different paradigms (supervised, self-supervised, semi-supervised) on the task of novel class retrieval based on three different datasets (CIFAR10, CIFAR100, In).

The remainder of the paper is organized as follows: the next section reviews important lines of research related to our evaluation methodology. In section 3 we detail how we manage to construct a benchmark relevant to novel class retrieval by masking whole categories from the training process and varying the degree of novelty. Next we present the algorithms we implemented and the different datasets and category splits used in the experiments. Finally we present our experiment results and analysis.

RELATED WORK

Novel Class Retrieval. We aim to benchmark training algorithms for the task of retrieving samples of classes unseen during training. It is similar to Novel class discovery [START_REF] Han | AutoNovel: Automatically Discovering and Learning Novel Visual Categories[END_REF][START_REF] Zhong | OpenMix: Reviving Known Knowledge for Discovering Novel Visual Categories in An Open World[END_REF] where the goal is to cluster the whole set of images of novel classes: instead of clustering we evaluate with retrieval, we do not need to know the number of novel classes or to estimate it. The goal in Few-shot learning [START_REF] Oreshkin | TADAM: Task dependent adaptive metric for improved few-shot learning[END_REF][START_REF] Snell | Prototypical Networks for Few-shot Learning[END_REF][START_REF] Vinyals | Matching Networks for One Shot Learning[END_REF][START_REF] Wang | Generalizing from a Few Examples: A Survey on Few-Shot Learning[END_REF] is to adapt most rapidly to novel classes with a small set of support supervised samples of those novel classes: in contrast we evaluate class retrieval, that is returning the most images of the class of a given single image query. Metric learning [START_REF] Bell | Learning visual similarity for product design with convolutional neural networks[END_REF][START_REF] Krause | 3D Object Representations for Fine-Grained Categorization[END_REF][START_REF] Kulis | Metric Learning: A Survey[END_REF][START_REF] Musgrave | A Metric Learning Reality Check[END_REF][START_REF] Schroff | FaceNet: A Unified Embedding for Face Recognition and Clustering[END_REF][START_REF] Song | Deep Metric Learning via Lifted Structured Feature Embedding[END_REF] benchmarks usually report performance in retrieval tasks of novel classes; datasets for those benchmarks [START_REF] Krause | 3D Object Representations for Fine-Grained Categorization[END_REF][START_REF] Song | Deep Metric Learning via Lifted Structured Feature Embedding[END_REF][START_REF] Wah | The Caltech-UCSD Birds-200-2011 Dataset[END_REF] also have class-disjoint training and testing sets but do not keep a split along the image axis as we do (See Fig. 1); in the testing phase we report retrieval performance on test images of base classes and novel classes among both base and novel-class images while metric learning does not keep test samples of base classes during testing (which prevents from evaluating the performance decrease compared to base classes).

Semi-Supervised Setting. It is often pointed out that labels are expensive to obtain and that is why training data is abundant in unlabeled samples and is lacking labeled samples. Semi-Supervised learning algorithms [START_REF] Chapelle | Semi-Supervised Learning[END_REF] are often proclaimed to work efficiently in that setting [START_REF] Laine | Temporal Ensembling for Semi Supervised Learning[END_REF][START_REF] Li | CoMatch: Semi-supervised Learning with Contrastive Graph Regularization[END_REF][START_REF] Pham | Meta Pseudo Labels[END_REF][START_REF] Tarvainen | Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results[END_REF], some methods showing impressive performance with a quantity of labels as low as one per class for CIFAR10 [START_REF] Sohn | FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence[END_REF], or 1% of labeled data for ImageNet [START_REF] Zhai | S4L: Self-Supervised Semi-Supervised Learning[END_REF]. We investigate an overlooked setting where the labeled pool and the unlabeled pool are class-disjoint; meaning that the unlabeled data are known to come from different classes that those seen during training. The authors in [START_REF] Oliver | Realistic Evaluation of Deep Semi-Supervised Learning Algorithms[END_REF] noted that this should be part of an effective benchmark for evaluating semi-supervised learning algorithms. They did a set of experiments on Random Semantic Supervised Semi-Supervised Table 1. Illustration of the two training schemes: We train algorithms with supervision on base classes (top row) and algorithms that incorporate images of the novel classes without supervision (bottom row). When the label space is partitioned randomly (left column airplane/cat vs. automobile/dog) the semantic gap between base and novel classes is narrower than when the label space is partitioned semantically (right column airplane/automobile vs. cat/dog).

CIFAR10 where they vary the amount of classes present both in labeled and unlabeled data and showed that performance can decrease in some cases. We take this idea further in the following ways: 1) we keep the labeled and unlabeled pools completely class-disjoint, 2) we experiment on CIFAR10, CIFAR100 and ImageNet100 and 3) we vary the degree of novelty between labeled and unlabeled pools by carrying a random split and a semantic split of the label space.

Partitioning the label space semantically. We experiment novel class retrieval on classification datasets: CIFAR10, CIFAR100 [START_REF] Krizhevsky | Learning Multiple Layers of Features from Tiny Images[END_REF] and a subset of ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF]. For CIFAR100 we can use the super-classes which group together classes that are visually alike: we borrow the splits from [START_REF] Oreshkin | TADAM: Task dependent adaptive metric for improved few-shot learning[END_REF] to devised the semantic split. For ImageNet we can use the WordNet hierarchy [START_REF] Fellbaum | WordNet_ An Electronic Lexical Database[END_REF] ; we chose a subset of the high-level categories used for tieredImageNet [START_REF] Ren | Meta-Learning for Semi-Supervised Few-Shot Classification[END_REF] (details in Section 5.1).

PROPOSED EVALUATION METHODOLOGY: VARYING THE DEGREE OF NOVELTY

Random and Semantic Class-disjoint Data Splits

We are given an image set 𝐼 = 𝐼 𝑇 ∪ 𝐼 𝐸 partitioned into training 𝐼 𝑇 and testing 𝐼 𝐸 sets (Fig. 1). We consider that the In each dataset, two kinds of experiments are carried out involving either a random split or a semantic split. The random split divides randomly the set of classes. The semantic split divides the set of classes in a way that minimizes the information overlap between the base and the novel classes. Table 1 illustrates how the semantic split increases the degree of novelty compared to the random split with classes of CIFAR10. We evaluate the trained network via image retrieval by running a similarity search among the whole testing set 𝐼 𝑇 and report R-Precision for queries from base classes B 𝐸 and from novel classes U 𝐸 separately (see Section 5 for the results).

Evaluation via Image Retrieval: R-Precision

We want to evaluate how well a visual representation transfer to unseen classes without any additional training, contrary to other evaluation methods that allow for additional training on the novel-class labels (linear probes [START_REF] Doersch | Unsupervised Visual Representation Learning by Context Prediction[END_REF], few-shot tasks [START_REF] Gidaris | Boosting Few-Shot Visual Learning with Self-Supervision[END_REF], knn-classifier [START_REF] Wu | Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination[END_REF]). Evaluation via clustering requires embeddings to be clustered and is dependent on the clustering algorithm used [START_REF] Musgrave | A Metric Learning Reality Check[END_REF]. We have chosen an evaluation metric that does not require any additional metric nor a choice of a clustering algorithm.

R-Precision.

Visual object category retrieval aims to retrieve examples of the same category than a given query from a search set (𝐼 𝐸 in our case). A function 𝑅 : 𝐼 ∈ 𝐼 𝐸 ↦ → 𝐼 𝑅 ∈ P (𝐼 𝐸 ) maps a query image to a set of similar images. The similarity between two images is evaluated by a dot product in the ℓ 2 -norm normalized feature space (also known as cosine similarity):

𝑠 (𝐼 𝑖 , 𝐼 𝑗 ) = Φ 𝜃 (𝐼 𝑖 ) ∥Φ 𝜃 (𝐼 𝑖 )∥ 2 • Φ 𝜃 (𝐼 𝑗 ) ∥Φ 𝜃 (𝐼 𝑗 )∥ 2 (1)
For an image 𝐼 , 𝑅 returns the list of most similar images ranked by the function 𝑠 in decreasing order. Let us denote the samples of class 𝑐 by I 𝑐 = {(𝐼 𝑗 , 𝑦 𝑗 ), 𝐼 𝑗 ∈ 𝐼 𝐸 , 𝑦 𝑗 = 𝑐}, and the size of the class by 𝑁 𝑐 = |I 𝑐 |. Image retrieval performance is usually evaluated by Recall@𝑘 [START_REF] Jégou | Product Quantization for Nearest Neighbor Search[END_REF] (with 𝑘 = 1, 5), in the metric learning literature [START_REF] Song | Deep Metric Learning via Lifted Structured Feature Embedding[END_REF]. We evaluate instead with Precision@𝑁 𝑐 where 𝑁 𝑐 is the total size of correct hits. The Precision is the proportion of correct hits among the 𝑁 𝑐 retrieved items. We set the cut-off-rank to be the size of the class query, so that the precision is equal to the recall.

ALGORITHMS STUDIED

In this section we present the algorithms we have implemented and tested in our experiments. We experimented with three training schemes. We took four supervised algorithms, two unsupervised algorithms and two semi-supervised algorithms.

The architecture of each algorithm are illustrated in Table 2. In the following we briefly introduce each algorithm.

Supervised Algorithms

Vanilla. This model optimizes the cross-entropy loss on base classes only:

L 𝑉 = ∑ (𝐼,𝑦) ∈B 𝑇 ℓ (𝑔(Φ 𝜃 (𝐼 )), 𝑦). (2)
Triplet Loss. This model optimizes the triplet loss [START_REF] Schroff | FaceNet: A Unified Embedding for Face Recognition and Clustering[END_REF] on base classes only:

L 𝑇 = ∑ (𝐼 𝑎 ,𝐼 𝑝 ,𝐼 𝑛 ) ∈T [𝑑 𝑎𝑝 -𝑑 𝑎𝑛 + 𝛼] + , (3)
where T is the set of all triplets mined from B 𝑇 ; 𝛼 is a margin hyperparameter,

𝑑 𝑎𝑝 = ∥ℎ(Φ 𝜃 (𝐼 𝑎 )) -ℎ(Φ 𝜃 (𝐼 𝑝 ))∥ 2 2 , 𝑑 𝑎𝑛 = ∥ℎ(Φ 𝜃 (𝐼 𝑎 )) -ℎ(Φ 𝜃 (𝐼 𝑛 ))∥ 2 2 .
In practice we optimize L 𝑇 with SGD and mine semi-hard triplets within a batch.

Classification With Triplet Loss. This model jointly optimizes the cross-entropy loss and the triplet loss:

L 𝐶𝑤𝑇 = L 𝑉 + L 𝑇 . (4)

Supervised Vanilla Triplet

CwT SupContrast

Unsupervised RotNet SimSiam

Semi-Supervised The first head 𝑔 classifies into the base classes while the additional head ℎ reduces the dimension and is used to compute the triplet loss.

Supervised Contrastive: SupContrast. This model [START_REF] Khosla | Supervised Contrastive Learning[END_REF] is based on a siamese architecture. It extends self-supervised contrastive methods [START_REF] Chen | A Simple Framework for Contrastive Learning of Visual Representations[END_REF][START_REF] Grill | Bootstrap Your Own Latent: A New Approach to Self-Supervised Learning[END_REF][START_REF] He | Momentum Contrast for Unsupervised Visual Representation Learning[END_REF] to the fully supervised-setting: in addition to construct positive pairs with random augmentations of the same image, it also uses the class labels to construct positive pairs. Similar to the triplet loss the contrastive loss enforces positive pairs to attract themselves and negative pairs to repel themselves. We refer the reader to the paper [START_REF] Khosla | Supervised Contrastive Learning[END_REF] for details.

Unsupervised Algorithms

Predicting Image Rotations: RotNet. This model [START_REF] Gidaris | Unsupervised Representation Learning by Predicting Image Rotations[END_REF] is an instance of a self-supervised algorithm [START_REF] Jing | Self-supervised Visual Feature Learning with Deep Neural Networks: A Survey[END_REF]. It rotates the input image into four possible rotations, and the head 𝑔 classifies into the four possible rotations. The model is trained to correctly classify the rotation applied to the input. It is a 4-class classification problem optimized with a cross-entropy loss:

L 𝑅 = ∑ (𝐼,𝑦) ∈B 𝑇 ∑ 𝑟 ∈R ℓ (𝑔(Φ 𝜃 (𝐼 𝑟 )), 𝑟 ), (5)
where R = {0°, 90°, 180°, 270°} is the set of all possible rotations and 𝐼 𝑟 refers to the corresponding rotated input.

SimSiam. This model [START_REF] Chen | Exploring Simple Siamese Representation Learning[END_REF] is another instance of a self-supervised algorithm [START_REF] Jing | Self-supervised Visual Feature Learning with Deep Neural Networks: A Survey[END_REF]. It is based on a siamese architecture and is trained to maximize the similarity between two randomly augmented views of an input image. Despite being simpler than similar methods [START_REF] Chen | A Simple Framework for Contrastive Learning of Visual Representations[END_REF][START_REF] Grill | Bootstrap Your Own Latent: A New Approach to Self-Supervised Learning[END_REF][START_REF] He | Momentum Contrast for Unsupervised Visual Representation Learning[END_REF] it shows competitive results for unsupervised visual representation learning [START_REF] Chen | Exploring Simple Siamese Representation Learning[END_REF].

We trained our own models on base classes only. We refer the reader to the paper [START_REF] Chen | Exploring Simple Siamese Representation Learning[END_REF] for details.

Semi-Supervised Algorithms

FixMatch. This semi-supervised model [START_REF] Sohn | FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence[END_REF] feeds an unlabeled image to a weak augmentation and a strong augmentation: the weakly augmented input is used for pseudo-labeling and the strongly augmented input is used for computing a cross-entropy loss against the pseudo-label. Note that the head 𝑔 classifies into the base classes. The pseudo-labels are among the base classes and the unlabeled images that are pseudo-labeled are fed to 𝑔 that classifies them into the base classes. The pseudo-labeling module is a threshold applied on the probability of the most confident class: only those images that are classified most confidently are passed to the next cross-entropy loss. FixMatch has two main hyperparameters: 𝜇 the number of unlabeled images per labeled images and 𝜏 the confidence threshold for the pseudo-labeling. We refer the reader to [START_REF] Sohn | FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence[END_REF] for details.

Classification With Rotation: CwRot. We propose to train a network in a semi-supervised fashion by adding an auxiliary self-supervised loss for unsupervised novel-class samples. We append a second head to the network ℎ tasked to predict the rotation applied to the input image as in the RotNet model [START_REF] Gidaris | Unsupervised Representation Learning by Predicting Image Rotations[END_REF]. This model optimizes the loss:

L 𝐶𝑤𝑅 = ∑ (𝐼,𝑦) ∈B 𝑇 ℓ (𝑔(Φ 𝜃 (𝐼 )), 𝑦) + ∑ 𝑟 ∈R ∑ 𝐼 ∈𝐼 𝑇 ℓ (ℎ(Φ 𝜃 (𝐼 𝑟 )), 𝑟 ). (6)
The choice for the auxiliary self-supervised objective was motivated by a series of works that successfully applied it to improve few-shot classification [START_REF] Da Chen | Self-Supervised Learning For Few-Shot Image Classification[END_REF][START_REF] Gidaris | Boosting Few-Shot Visual Learning with Self-Supervision[END_REF][START_REF] Su | When Does Self-supervision Improve Few-shot Learning?[END_REF], robustness [START_REF] Hendrycks | Using Self-Supervised Learning Can Improve Model Robustness and Uncertainty[END_REF], pre-training for novel class discovery [START_REF] Han | AutoNovel: Automatically Discovering and Learning Novel Visual Categories[END_REF], image generation [START_REF] Chen | Self-Supervised GANs via Auxiliary Rotation Loss[END_REF][START_REF] Lucic | High-Fidelity Image Generation With Fewer Labels[END_REF], semi-supervised learning [START_REF] Zhai | S4L: Self-Supervised Semi-Supervised Learning[END_REF].

This is actually a simplified version of the method proposed in [START_REF] Zhai | S4L: Self-Supervised Semi-Supervised Learning[END_REF], where the consistency regularization and pseudo-labeling components of the training scheme are removed.

EXPERIMENTAL RESULTS

Datasets

We experiment on CIFAR10, CIFAR100 [START_REF] Krizhevsky | Learning Multiple Layers of Features from Tiny Images[END_REF] and a subset of ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF]. For each dataset, we split the label space randomly and semantically. The splits are done once and for all. ImageNet100. We experiment on a subset of 100 classes of ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] which we call ImageNet100 in the following.

We keep 16 of the high-level categories among the 34 devised by the authors of tieredImageNet

Implementation details

All networks share the same ResNet18 [START_REF] He | Deep Residual Learning for Image Recognition[END_REF] backbone. On CIFAR10 and CIFAR100, the input images are 32x32 in resolution, we use a first convolutional layer with stride 1, not followed by a max pooling layer. For ImageNet100, the images are stored on disk at 84x84 resolution and are resized to 224x224 resolution before being fed to the network: this time we used the standard ResNet18 architecture where the first layers reduce the spatial dimension.

We reimplemented from scratch Vanilla, Triplet, RotNet, CwT and CwRot. For Vanilla, Triplet, CwT and CwRot, the networks are optimized with SGD with batch size 128, 0.9 momentum, 1𝑒 -4 weight-decay, and an initial learning rate of 0.1 dropped by 10 every 30 epochs for a total of 100 epochs. For RotNet, we followed the guidelines from the paper [START_REF] Gidaris | Unsupervised Representation Learning by Predicting Image Rotations[END_REF].

For Triplet and CwT, in all cases we set the margin 𝛼 to 0.1 we mine semihard [START_REF] Schroff | FaceNet: A Unified Embedding for Face Recognition and Clustering[END_REF] negative samples, and we set the embedding dimension to 128.

For the other three algorithms we used PyTorch implementations readily available (SimSiam 1 , SupContrast 2 , Fix-Match 3 ) and made some modifications. We adapted the codebase by modifying the backbone network to match the Resnet18 used for the other baseline algorithms. For SupContrast on ImageNet100 we reduced the number of epochs to 200, decaying the initial learning rate by 10 at epochs 150, 170 and 190. For FixMatch on ImageNet100, we trained for 2 19 iterations and used 𝜇 = 5 unlabeled images per labeled image. We kept the recommended hyperparameters in every 1 https://github.com/facebookresearch/simsiam 2 https://github.com/HobbitLong/SupContrast 3 https://github.com/kekmodel/FixMatch-pytorch other case. We would like to emphasize that we did not optimize the hyperparameters for the best performance but instead use sensible defaults, following recommendations of ResNet [START_REF] He | Deep Residual Learning for Image Recognition[END_REF] and original papers of each algorithm. on CIFAR100 and ImageNet100. The contrastive model SupContrast performs the best on base and novel classes on CIFAR10 but this does not hold on CIFAR100 and ImageNet100.

Results and analysis

Algo

Unsupervised algorithms. RotNet and SimSiam do not show interesting results even on the base classes there were trained on; and we do not draw a consistent conclusion as for which algorithm is best in general. However we note that for the semantic split in some cases RotNet and SimSiam are better than Triplet and CwT on novel classes. For example on ImageNet100-Semantic it is actually better to use an unsupervised method than to use a metric learning method.

Semi-Supervised algorithms. The semi-supervised models mitigate the performance difference between base and novel classes and surpass the supervised baselines with a greater margin on the semantic split than on the random split. We note that CwRot performs consistently better than Vanilla on all datasets on both base and novel classes.

As for FixMatch, it is consistently better than Vanilla on novel classes. It compares more favorably to CwRot on novel classes for the random split than for the semantic split. We argue that it is due to the fact that during training it learns to classify novel-class images into the set of base classes and, because for the semantic split the novel classes are less visually alike to the base classes than for the random split, it less efficiently leverages similar visual patterns between base and novel classes. This comparison between CwRot and FixMatch for the semantic split is an evidence that semi-supervised methods such as FixMatch that rely on the fact that labeled and unlabeled images come from the same set of classes are less efficient in the setting when an entire set of images from a novel class come into play.

T-SNE embedding visualization.

We show in Table 6 some T-SNE visualization of the embeddings of CIFAR10 for four algorithms. The visualizations support the conclusions from the previous section. In particular, we can see that only the semi-supervised methods succeed in structuring the novel classes in the case of the semantic split (with CwRot providing a better class separation than FixMatch).

CONCLUSION

We presented a method to evaluate novel class retrieval. We argued that existing benchmarks for semi-supervised representation learning algorithms lack a setting where unlabeled data are from novel classes.

  label space Y is partitioned into two parts: a set Y 𝑏 of base classes and a set Y 𝑛 of novel classes. The training set can be partitioned into 𝐼 𝑇 = B 𝑇 ∪ U 𝑇 where B 𝑇 = {(𝐼, 𝑦); 𝐼 ∈ 𝐼 𝑇 , 𝑦 ∈ Y 𝑏 } comprises annotated images of base classes

Fig. 1 .

 1 Fig. 1. We partition the label space into Y = Y 𝑏 ∪ Y 𝑛 , holding out a set of novel classes Y 𝑛 for evaluation. Contrary to metric learning benchmarks we also keep a train/test partition along the image axis 𝐼 = 𝐼 𝑇 ∪ 𝐼 𝐸 , allowing for a comparative performance evaluation on base Y 𝑏 and novel Y 𝑛 classes on the test images 𝐼 𝐸 . We train a various set of algorithms with supervision only on base classes B 𝑇 , and optionally adding images of novel classes of the train partition without supervision U 𝑇 .

Table 2 .

 2 Supervised algorithms train a network with images of base classes only (classes 𝑐 1 , 𝑐 2 ). Unsupervised algorithms train a network with images of base classes without supervision (classes 𝑐 1 , 𝑐 2 ). Semi-Supervised algorithms train a network with images of base classes with supervision, and images of novel classes without supervision (classes 𝑐 1 , 𝑐 2 and 𝑐 3 , 𝑐 4 ). At testing time all the heads are discarded, we take as a visual representation the output of the last average pooling layer of the backbone Φ 𝜃 ( •).

CIFAR10.

  For the random split, we keep 5 classes at random for base classes and the remaining 5 classes for novel classes. We got:Y 𝑏 = {automobile, bird, deer, frog, ship}, Y 𝑛 = {airplane, cat, dog, horse, truck}.Note that 2 vehicles and 3 animals ended in base classes, and also 2 vehicles and 3 animals ended in novel classes. For the semantic split, we also partitioned the label space evenly into 5 base classes and 5 novel classes; we chose the following partitioning:Y 𝑏 = {airplane, automobile, bird, ship, truck}, Y 𝑛 = {cat, dog, deer, frog, horse}.Note that 4 vehicles and 1 animal are in the base classes, while the novel classes consist only of 5 animals and no vehicle. CIFAR100. CIFAR100 contains 100 classes that can be grouped into 20 super-classes. For the random split, we keep 50 classes at random for base classes and the remaining 50 classes for novel classes. Note that for the random split, the super-classes are spread randomly among the base and the novel classes. For example, the people super-class has 3 classes in base classes (baby, girl, man) and 2 classes in novel classes (boy, woman). For the semantic split, we follow the splits of Few-Shot CIFAR100 introduced in[START_REF] Oreshkin | TADAM: Task dependent adaptive metric for improved few-shot learning[END_REF]. We set the base classes to the train classes and the novel classes to the val classes + test classes. Note that for the semantic split, each super-class is entirely either in the base classes or the novel classes. For example, the people super-class has all the 5 classes in novel classes.

  [START_REF] Ren | Meta-Learning for Semi-Supervised Few-Shot Classification[END_REF] using the WordNet hierarchy: 8 categories descending from the artefact synset (motor vehicle, craft, durables, garment, musical instrument, game equipment, furnishing, tool), 8 categories descending from the animal synset (ungulate, primate, feline, working dog, saurian, aquatic bird, insect, aquatic vertebrate); with 6-7 ImageNet classes per high-level category. For the random split we keep in base classes 3-4 classes for each high-level category at random in order to keep 50 classes, and the novel classes are the remaining 50 classes. For the semantic split, we keep the artefact classes for the base classes and the animal classes for the novel classes. Unlike tieredImageNet we keep all training images in the training, and validation images for testing; like tieredImageNet we resize the images to 84x84 resolution.

  T-SNE visualizations of the embeddings of base and novel classes for CIFAR10 for the random split (left columns) and for the semantic split (right columns). The Semi-Supervised algorithms (bottom rows) better separate the novel classes compared to the Supervised algorithms (top rows). The colors encode class membership. Best viewed in color.

Table 3 .

 3 R-Precision on base and novel classes of CIFAR10 for a random split (left columns) and a semantic split (right columns). Top rows are supervised algorithms. Middle rows are unsupervised algorithms. Bottom rows are semi-supervised algorithms. Best R-Precision is marked in bold.

		CIFAR10-Random CIFAR10-Semantic
		Base	Novel	Base	Novel
	Vanilla	65.147	26.380 68.469	19.758
	Triplet	71.479	20.512 74.890	16.760
	CwT	72.336	20.391 74.389	15.438
	SupContrast 74.881	28.954 79.566	22.726
	RotNet	28.476	17.379 27.663	16.732
	SimSiam	19.340	19.048 20.518	17.298
	CwRot	72.816	37.832 77.680	35.764
	FixMatch	57.807	39.238 79.178	27.419
	Algo	CIFAR100-Random CIFAR100-Semantic
		Base	Novel	Base	Novel
	Vanilla	33.339	15.351	39.778	7.891
	Triplet	33.895	10.015	43.745	3.846
	CwT	48.656	10.180	57.021	4.131
	SupContrast 42.981	14.094	49.000	6.678
	RotNet	5.293	3.906	6.149	2.392
	SimSiam	5.287	4.521	6.085	3.863
	CwRot	34.257	17.525	39.962	9.886
	FixMatch	38.771	22.896	47.905	9.444

Table 4 .

 4 R-Precision on base and novel classes of CIFAR100 for a random split (left columns) and a semantic split (right columns). Top rows are supervised algorithms. Middle rows are unsupervised algorithms. Bottom rows are semi-supervised algorithms. Best R-Precision is marked in bold.Retrieval performance is reported in Table 3 (CIFAR10), Table 4 (CIFAR100) and Table 5 (ImageNet100). Readhorizontally we can compare the performance between base and novel classes. In any case the performance is degraded on novel classes, even more so for the semantic split. Read vertically we can compare the performance between the algorithms.

	Supervised algorithms. The metric learning algorithms (Triplet and CwT) exhibit a better fit of the base classes to the
	detriment of a poorer performance on the novel classes classes compared to Vanilla. The benefit of Triplet over Vanilla on
	base classes is most noteworthy on CIFAR10 and slight on CIFAR100 and ImageNet100, indicating that the simpler and
	faster Vanilla algorithm is a better choice on more fine-grained dataset. The contrastive model SupContrast performs
	the best among the supervised baselines on base classes; on novel classes it also performs the best on CIFAR10 but not

Table 5 .

 5 R-Precision on base and novel classes of ImageNet100 for a random split (left columns) and a semantic split (right columns). Top rows are supervised algorithms. Middle rows are unsupervised algorithms. Bottom rows are semi-supervised algorithms. Best R-Precision is marked in bold.

We experimented with a variety of representation learning algorithms and showed evidence that semi-supervised learning algorithms mitigate the performance drop on novel classes. Yet there is still much room for improvement for the novel class retrieval task. Semi-supervised algorithms still fall short in retrieving images of novel classes in the random split setting (low-degree of novelty) and even more so in the semantic split setting (higher degree of novelty).