Enka Blanchard Digitrust

Ted Selker

Florentin Waligorski

Towards an Empirical Cost Model for Mental Password Algorithms

Keywords: Psychometrics, Password, Mental Computation, User Study CCS Concepts, Human-centered computing → User models, Empirical studies in HCI, •Applied computing → Psychology

Reliance on technology has diminished our use of mental computation. However, mental computation's inherent privacy features are becoming central to new research on creating more secure and usable passwords than one gets with approaches such as password managers. This work empirically studies the validity of cognitive assumptions relative to mental computation for making codes like passwords, using as a starting point password algorithms and a cost model for mental computation developed by Blum and Vempala. Through a study on 126 participants, we refute some of their model's assumptions, and introduce evidence of behaviours where human computing costs behave counter-intuitively. We also identify three empirical questions around symmetry, repeatability, and distribution of costs whose resolution would allow the development of more predictive cognitive computation models. This would then allow the efficient creation of better security algorithms.

Introduction

In a series of papers Blocki, Blum, Datta and Vempala introduced a series of mental algorithms meant to replace password managers, and also a general model for mental computing [START_REF] Blocki | Naturally rehearsing passwords[END_REF][START_REF] Blocki | Towards Human Computable Passwords[END_REF][START_REF] Blum | The Complexity of Human Computation: A Concrete Model with an Application to Passwords[END_REF][START_REF] Blum | Publishable humanly usable secure password creation schemas[END_REF][START_REF] Samadi | Usability of Humanly Computable Passwords[END_REF]. This model featured a stack, a set of pointers, and costs for basic operations, allowing the formalisation of already existing informal algorithms [START_REF] Lee | Four Methods to Create a Secure Password You'll Actually Remember[END_REF]. More algorithms have since extended this research [START_REF] Yang | An Empirical Study of Mnemonic Sentence-based Password Generation Strategies[END_REF], including a method that produced 42-bit secure independent passwords in under a minute while avoiding mental arithmetic [START_REF] Blanchard | Cue-Pin-Select, a Secure and Usable Offline Password Scheme[END_REF]. Blum and Vempala's computational cost model for passwords includes short-term memory as a 2-item stack, and long-term memory as a set of pointers. Resetting the pointer means going to either the start or the end of the relevant memory item. Operation costs only apply to single or double digit numbers. Applying a map generally corresponds to a letter-to-number or letter-to-letter map.

The development of new mental algorithms is hampered by the high cost linked to testing. Each new algorithm (and every variant) requires an independent usability study to ascertain its performances when compared to other solutions. This would be made easier by having a cost model for mental algorithms that would give the distribution of how timeintensive it is for individuals. We identify three obstacles must be overcome to create an accurate cost function C.

Repeatability. We can't assume that C(A; A) = 2×C(A) for an algorithm A, due to both habituation and mental fatigue. Symmetry. We can't assume that the C(A; B) = C(B; A) = C(A)+C(B) for the concatenations of two sub-algorithms A and B, as task switching might create non-symmetric costs.

Average cost versus distribution. C can be highly dependent on the human considered. This is why, assuming there are clusters of humans with similar performance on similar problems, a distribution of time (instead of an expected time) might be obtainable and more informative.

Cognitive science approaches. Some aspects of mental algorithm performance has been studied extensively with approaches from both psychometry and neuroscience, with studies on learning and memory abilities for a variety of stimuli (such as words, sentences, pictures) [START_REF] Shepard | Recognition memory for words, sentences, and pictures[END_REF][START_REF] Hulme | Word-frequency effects on short-term memory tasks: Evidence for a redintegration process in immediate serial recall[END_REF], mnemonics [START_REF] Bellezza | Mnemonic Devices and Memory Schemas[END_REF], and comparisons with other primates [START_REF] Inoue | Working memory of numerals in chimpanzees[END_REF].

A second focus has been the arithmetical capabilities of the average human, with correlations between arithmetic, algorithmic, and linguistic skill [START_REF] Dehaene | Varieties of numerical abilities[END_REF][START_REF] Fuchs | The cognitive correlates of third-grade skill in arithmetic, algorithmic computation, and arithmetic word problems[END_REF]. It also led to the exploration of neurological bases for our representation of numbers [START_REF] Mark | Cognitive arithmetic: A review of data and theory[END_REF][START_REF] Butterworth | The Mathematical Brain[END_REF][START_REF] Butterworth | Storage and retrieval of addition facts: The role of number comparison[END_REF].

Differences between demographic groups have also inspired extensive studies, especially for arithmetic abilities of people with maths anxiety [START_REF] Chang | Simple arithmetic: not so simple for highly math anxious individuals[END_REF], with short-term memory problems [START_REF] Butterworth | Short term Memory Impairment and Arithmetical Ability[END_REF], and across cultures [START_REF] Rodic | Cross-cultural investigation into cognitive underpinnings of individual differences in early arithmetic[END_REF] and age groups [START_REF] Butterworth | Mathematics and the Brain[END_REF].

Blum-Vempala model. Surprisingly little has been done in the search for a general cost model for human computing that would accurately predict, quantitatively, the difficulty and time cost to compute mental algorithms. So far, the main model used in security was introduced by Blum and Vempala in 2015 [START_REF] Blum | Publishable humanly usable secure password creation schemas[END_REF], and refined in [START_REF] Blum | The Complexity of Human Computation: A Concrete Model with an Application to Passwords[END_REF]. This model, shown in Table 1 was meant to give a rough expectation of time taken but wasn't experimentally validated. The authors also insisted on keeping a low total cost for mental password algorithms; proposing a maximum cost of 12 as a recommendation to cap time under 40 seconds, assuming that an average individual spends 2 to 3 seconds on a task of cost 1. The model's costs might be reasonable, but are its assumptions correct? For example, it has no place for queries of variable complexity (such as getting the n-th letter in the alphabet, which intuitively seemed easier for n = 1 than for n = 13, but which they assume have a uniform cost). We show here the early results of a study on 126 participants that sought to expose mechanisms involved in creating a cost function for mental algorithms. Among other results, we show that accessing a mental map is far from uniform, with a difference of one order of magnitude depending on the element accessed. Arithmetic operations also behave differently, with n + m apparently costing not θ(log(n) + log(m)) but closer to θ(n + m).

This work is exploratory in nature. While our work confirms -and refutes -some of the assertions explicitly or implicitly made by the published model, its goal is to show the need for and value of a rigorous and empirically tested model, to avoid statistical mistakes that can stymie research replication [START_REF] Borsboom | The attack of the psychometricians[END_REF].

Design of the experiment

The goal of this study was to give preliminary answers to some of the following questions and offer insight to researchers studying and proposing new cognitive algorithms. The main goals were the following:

• Get baseline time cost distributions for elementary operations considered in a way that allows comparison between groups and user groups.

• Check whether accessing the n-th element in an array is done in constant time or not, as asserted by Blocki et al [START_REF] Blocki | Naturally rehearsing passwords[END_REF], and check the effects of repeated accesses. • Check whether the costs commute: is it easier to perform an addition after a multiplication or the other way around? • Check the independence of users' performance in elementary linguistic and arithmetic tasks. This is especially relevant for password algorithms as having clusters with different abilities would motivate the need for a set of tailored algorithms instead of a general one.

Demographics 126 participants1 were recruited through a mix of snowball sampling on social networks [START_REF] Handcock | Comment: On the concept of snowball sampling[END_REF] and referral through a web-site that indexes psychological experiments [START_REF] Krantz | Psychological research on the net[END_REF], with data from four being discarded as they skipped most of the questions. As a high number of participants were expected to be French, two versions of the experiment were developed and participants could choose their preferred version on the first page. 85 were native English speakers, 28 were French, and the rest spoke 10 different languages. Ages went from 15 to 63 with a median at 23 and an average at 27.

Protocol

The participants interacted with the system through a webpage that recorded their inputs as well as the times to type a first character and to complete each query. For tasks where the answer is a number or a word, the measures and comparisons were all made on the basis of the first character typed -to compensate for answers of different lengths among other things. To attenuate the delay due to reading and understanding the questions, complex instructions were shown on an example before the question was asked.

The experiment had 9 sections of varying length:

1. Participants were initially told their rights and asked asked basic questions. 2. They were told to learn a four-word sentence, type it, and type it again at the end of sections 3, 4, and 5. They were shown their sentence if they made a mistake. 3. They were given three single-digit additions, singledigit multiplications, and double-digit additions. Then two multiplication on lower double-digit numbers and four remainders of double-digit numbers divided by 3,5,9 and 11.

no personal or identifying information was collected besides age and main language spoken. 4. They had to produce a series of three words starting by t, b and a (three different questions), like tortoise, blueberries and Austria. In a between-groups approach, half were asked for an animal, fruit and country, while the other half were asked to type in any word starting by the same letter.

5. They had to give the n-th letter in the alphabet, for four different letters in a row. They were then asked the reciprocal question, also four times. The numbers were written with Arabic numerals except for one group for which they were spelled out. They were then successively given three words and asked to write the letters in alphabetical order. Finally, they had to say what was the n-th month of the year (for two different months), followed by two reciprocal questions. 6. Participants had to find a given letter in either a sentence on screen -or the one they had memorisedand write the two letters that followed the given letter. 7. They had to type the words they had chosen earlier. 8. Participants had to apply an arithmetic algorithm, then a linguistic algorithm, and finally a mixed algorithm. 9. Finally, participants were asked whether they had used a pen and paper, and for which tasks.

Between-group design was used in multiple ways in this experiment. One was that sections 3, 4 and 5 were given in a random order. For most of the questions, participants were divided into 3 to 5 groups with different but structurally identical questions given to each group.

For sections 3 and 5, one group was given random numbers or letters, while the others were given predetermined questions. This was to ensure that enough data would be collected to establish statistically significant results on certain properties, while maintaining the possibility that, if enough people participated, there would be general data available on more than few specific points. For example, in section 3, a quarter of the participants started with the question "2+2=?", another quarter with "9+8=?", and the rest with random pairs of digits.

Preliminary results

One difference with using these techniques in the wild is that in the experiment participants had to read the instructions and assimilate them before performing the trials, adding a measure of uncertainty. We think this strengthens the results -as this added noise was not enough to make the effect disappear. As the experiment was not in a controlled environment, we couldn't prevent people from taking a break (and some participants did take to a 10 minute break). The pvalues indicated correspond to one way ANOVAs. No significant effects were observed between the two main language groups.

Access time in a list

The first main question was the veracity of the constant access time in a list assumption in the published model, with two different tests for this in section 5. Our expectation was that the first few elements of the list might get accessed in constant time, with a sub-linear increase until close to the end of the list, where it would go back down as people chose to work from the end of the list instead.

This was partially shown to be true: on the first question, there was no significant difference between asking for the letter "A" or the letter "B", with both average and median times between 2.6s and 2.9s. However, "D" is quite slower than "A" (3.4s on average), with p < 0.0003. This difference got absorbed by the second question with no statistically significant differences between "K", "M" and "N" (respectively 8.0, 8.2 and 8.3 seconds on average).

The strongest result came from the third question. All the users who were asked to give the 13th letter ("M") had previously had to give the 14th ("N") in the third question, and did so in 2.2s on average. The ones who were previously asked to give the 14th letter were now asked for the 13th, and did so in 3.6s on average. Getting the next element in the list is then much easier than getting the previous one (p < 0.0005). The speed ratio is at least a factor 1.5, but might even be close to 3, assuming a 1s reaction delay (reasonable as less than 1% of answers were faster than 1s).

Still on the third question, the participants who had had the 11th letter ("K") and had to give the 18th ("R") afterwards did not benefit from their previous computations and took an average of 12.0s. This is confirmed by the fact that getting the 22nd and 23rd letters in the last question also took 14.0 and 14.6 seconds, with no visible priming effect from what participants had to answer just before. Although the sample size for those letters was small, we could still observe speed increase for the last 3 letters of the alphabet, compared to the 3 preceding characters in the alphabet, suggesting that some people proceeded backwards, with an average of 10.1s, compared to 14.9s on average for the three preceding letters (p < 0.05).

Similar results can be shown for character-to-number maps. For example, giving the number corresponding to "D" took an average of 4.8s, as opposed to 3.9s for "A" on the first question, and 7.2s for "K" on the second question (p < 0.03 and p < 10 -4 respectively).

We confirmed those intuitions on month/number queries. When initially asked for either the first or the fifth month of the year, participants were much slower in the latter case (2.8s and 4.6s on average, with medians of 2.4s and 3.8s, p < 0.10 -4 ). In the second question, when asking for the tenth month, there was no statistical difference between the groups who had been asked for the first or the fifth previously. The given the tasks of computing "12+7", "79+87" and "87+5" in various orders, with the rest having random 2-digit additions (one of the linear regressions shown focuses on this group, whereas another ignores it, with little difference in the coefficients). There is a tendency to increase at least linearly, not the logarithmic growth in the published model.

reciprocal question also featured speed differences, with averages of 2.1s to say that February was the 2nd month, versus 4.0s for July being the 7th (p < 005).

Arithmetic operations

We observed a large speed increase between the first and second question -both being single-digit additions -with the average time going down from 2.7s to 1.8s (p < 10 -4 ), which we attribute to switching costs between tasks before the first question and the first question. Discarding this first question, we observed no statistical difference between the cost of doing "2+2" and "4+5" on the second question. However, we saw a difference between "4+5" and "8+9" (1.9s vs 2.3s, p < 0.05).

The same effect can be seen with multiplication: results with a single digit were computed faster than ones with double digits (averages of 1.6s versus 4.8, with p < 2 × 10 -4 ).

The previous results could be seen as a partial confirmation of the published model, but detailed analysis and extension of the addition to 2-digit numbers show that time cost is more probably linearly dependent on the result, with the spread increasing with the complexity, as shown in Figure 1.

To test how the operation complexity depended on the context and previous operations, participants had to enter the result of one of five quasi-equivalent arithmetic algorithmsgoing through the same set of numbers with different operations -shown in Table 2. The first and the third, with their different operations, had statistically equivalent performance to the second, but had a much wider spread. All three were also faster than algorithms [START_REF] Blocki | Naturally rehearsing passwords[END_REF]

Discussion and future work

Exploring the cognitive issues surrounding security practices is overdue. This paper presents empirical testing of assumptions researchers have made regarding cognitive issues while creating strings of characters for codes or passwords. The results of of our experiments show that what character you retrieve, what computation you do and how many of them you do have real impacts on each other. Some assumptions that led to the creation of the published model were not validated, most importantly the idea that humans can assign a map of numbers to letters and use it quickly as a hash function does not work. Instead, the computing time depends strongly on position; there is a large difference between going forward or backward in the list, and there is very limited re-use of already computed ele-ments. From an ecological standpoint, the published model assumed that people would have a training period, although one limited to a few dozen minutes. This is not compatible with its predictions, as it would either have to compensate for decades of semi-regular use, or the "time to access" cost only concerns new maps/functions that people haven't practised before. In such a case, it would stand to reason that most people would get better performances on the functions on which they are trained since childhood, and one needs to separate the costs depending on the kind of function. In both cases, the model requires changes, especially since it was originally developed for critical algorithms where a factor 2 or 3 in the cost matters a lot in terms of wide-scale human adoption of the newly developed methods. This late-breaking work shows some surprising elements. Besides the very limited re-use of precomputed elements, operating the algorithm in section 8 with multiples of 10 takes more time than with multiples of 3 (despite being with double digit numbers in both cases). There are also quite a few questions that will require further analyses: what is the time cost of memory recall (sections 4 and 7), of letter manipulation (sections 5 and 6), of letter searching in a text (sections 6 and 8), and what additional cost is linked to alternating between linguistic and arithmetic tasks (section 8).

The goal of this experiment was to underline the questions at the heart of modelling the cost of human computation, and to provide an empirical basis for a new, more comprehensive model. Such a model should not only include time costs (although they are the easiest to measure), but also perceived cost, linked to the complexity and repetitiveness of the tasks involved. Moreover, just as pre-WW2 cryptosystems relied on a mix of manual labour and precomputed codebooks [START_REF] Rijmenants | Hand Ciphers[END_REF], new algorithms based on the privacy-enhancing properties of tool-aided mental computing could form the basis of new security paradigms.

Figure 1 :

 1 Figure1: Time taken by participants to compute "x+y" as a function of the expected value . Two-thirds of the participants were given the tasks of computing "12+7", "79+87" and "87+5" in various orders, with the rest having random 2-digit additions (one of the linear regressions shown focuses on this group, whereas another ignores it, with little difference in the coefficients). There is a tendency to increase at least linearly, not the logarithmic growth in the published model.

Table 1 :

 1 A summary of

	Operation	Cost
	Access item # 1	1
	Access item # 2	2
	Retrieve pointer	1
	Follow pointer	1
	Reset pointer	1
	Apply a map	1
	=, + and x	#digits
	(mod 2,3,4,5,9,10)	created
	=, + and x	1+#digits
	(mod 11)	created

Table 2 :

 2 Average and median execution time of each arithmetic algorithm.

	Algorithm	Time
	Start with 2.
	Multiply by 2. Add 4.	8.3s / 6.6s
	Divide by 4.
	Start with 2.
	Add 2. Add 4.	7.7s / 7.3s
	Divide by 4.
	Start with 2. Subtract 6. Multiply by 2. Add 4.	7.7s / 6.4s	and 5 (p < 0.02), which are based on algorithm 2, except that all values are multiplied by 10 (for #4) or 3 (for #5).
	Start with 20.
	Add 20. Add 40.	11.1s / 7.0s
	Divide by 4.
	Start with 6.
	Add 6. Add 12.	10.0 / 7.9s
	Divide by 4.

As the country where the experiment was organised does not have institutional review boards, we followed the guidelines for human subject studies enforced in the US as best practices. Participants did not belong to protected groups, were told they could leave the trial at any time, and


Michel Dambrine

Jean-Pierre Richard

come


Leo Adams

Enka Blanchard

Inès Dardouri

Levi Gabasova

Pierre Midavaine

"Set up son? Scam set, asserts Bob": Semi-Automatic Generation of Bilingual Palindromes

Keywords: 2012 ACM Subject Classification Information systems → Structure and multilingual text search; Theory of computation → Algorithm design techniques Palindrome, Computational linguistics, Recreational mathematics

    "Set up son? Scam set, asserts Bob": Semi-Automatic Generation of Bilingual Palindromes

Introduction

Evoles ut ira breve nefas sit; regna!

This sentence is iconic as a linguistic anomaly, as it is the only known example of its kind. Taken in reverse, it gives "Anger? 'Tis safe never. Bar it! Use love." Despite some liberties taken with the translation and typographical symbols, it is the only existing bilingual palindrome with the same meaning in both languages. It was discovered -or at least, first published -by James C.P in an issue of Our Young Folks Magazine [START_REF] James | Letter to the editors[END_REF], a children's magazine. Despite being then -and remaining so ever since its publication more than 150 years ago -our only example of such a palindrome being possible, it was presented with no fanfare by the magazine at all, in small characters on the last page, among other letters to the editor (under a letter featuring one of the simplest palindromes: "Madam, I'm Adam"), with the last name of its creator not even indicated.

The Latin phrase roughly translates to "go forth, in order that anger might be a shallow wrong (over which) you prevail". While the palindrome's English version is clearly not a perfect replication, it does communicate the sense of the Latin appropriately. James C.P was the first to point out that when read forwards, the palindrome is not exactly classical Latin, but it is grammatical. The English version is both grammatically cohesive and in line with the Latin in tense and aspect.

Until recently, a legend permeated the anglophone world, which treated this example as the only bilingual palindrome in existence, barring some examples made up of one or two words. This is, unsurprisingly, untrue, although examples are still exceedingly rare. Even when removing the constraint of having a similar meaning in both languages, only two sources appear to mention such bilingual palindromes. The first is a 16-page internal publication linked to the Oulipo and the Collège de 'Pataphysique, written by Luc Étienne in 1984 [START_REF] Étienne | Palindromes Bilingues[END_REF]. The second is a book published by Gérard Durand on 20/02/2002 with a print run of a few hundred copies 1 , which features two pages on the subject [START_REF] Durand | Palindromes en folie[END_REF]. The palindromes in both works are apparently not ones where the meaning is similar in both languages 2 . Moreover, they are not perusable online, and the only available online source that mentions a new bilingual palindrome features one that is not fully grammatical 3 [3].

This anomaly -and the associated legend (which the authors initially believed) -is linked to a diversity of reasons. A probable explanation is that Latin and English form a pair that is uniquely suited to such constructions. However, the number of fluent Latin locutorsespecially the ones with the expertise and leisure to tackle such problems -has declined greatly since the 19th century.

We then propose to use computational tools to help modern palindrome composers create new bilingual palindromes between arbitrary pairs of languages (as long as they share a segmental script).

Contributions

Our contributions are threefold:

We formalise some of the concepts associated with bilingual palindromes, which give rise to a few non-trivial algorithmic problems. We also introduce several algorithms to generate word lists that can be used as primers for manual composition of bilingual palindromes (which were used to create the palindrome in the title).

We apply those methods and compare the relative difficulties of bilingual palindrome composition between the six following languages: English, French, German, Polish, Spanish, and Swahili. We put a final nail in the coffin of the legend that James C.P.'s palindrome is the only one of its kind (although it remains to this date the only bilingual palindrome with matching meanings).

Preliminaries

We will consider pairs of languages (L, M), and the reverse languages M R and L R , consisting of the words of L and M with reversed letter order. As the languages can feature slightly different diacritics or character sets, we generally follow the convention of removing them (as well as any typographical symbol) to simplify the composition of palindromes, so we will concentrate on a set of characters corresponding to the 26-character Latin letters present in English.

Types of bilingual palindromes

We can define three main kinds of bilingual palindromes.

Bilingual strings, which are parsable in both L and M R with at least one decomposition in each language. For example, wakazaa kazirika in Swahili (a prefix-verb phrase meaning "then they gave birth", and the root form of the verb "to be angry") reversed corresponds to a kir i zak a az a kaw in Polish ("and pall and student and until and coffee"), and although both can be parsed, they do not have meaning.

Bilingual sentences, which are not only parsable in both L and M R but follow a semblance of grammatical rules in both. The rules can be bent somewhat, as is frequently done already in palindrome composition and related word games. For example, Sir, o, blame Diana reversed corresponds to An aide mal Boris (where An is a first name) in French [START_REF] Durand | Palindromes en folie[END_REF].

Bilingual meaningful sentences, which are not just grammatical but make sense in both language even with limited context. A possible example is I am near, I repel as a rat. which becomes Tara, sale, périra en mai. There is a sub-type of this bilingual palindrome, which we could call a "true bilingual palindrome" where the meanings of both sentences are related, but the only palindrome corresponding to this is the one featured at the start of the introduction.

Objectives

There is one central objective, which is to generate bilingual palindromes of the third kind, ideally ones with related meanings. However, short of being able to do that directly, we can look at simplifying the constraints by characterising good sub-languages from which humans -who excel at pattern seeking -can hopefully work more efficiently to manually compose palindromes.

One possibility would be to generate many potential bilingual strings and choosing the best ones. This is because generating bilingual strings is theoretically easy: they correspond to words from L * ∩ (M R ) * . We take a standard representation of L as a prefix tree. We can then obtain a non-deterministic automaton corresponding to L * by adding ε-transitions from each terminal node to the root. The intersection L * ∩ (M R ) * can then be naturally computed by checking the product automaton. The issue with that is one of size: many languages used here have more than 300 000 word forms (including plurals and declensions), and the corresponding prefix trees can have more than a million nodes. Lazy evaluation can help, but this can still be prohibitively computationally expensive.

Besides the computational cost, however, is the fact the overwhelming majority of these strings will be nonsensical, with the probability increasing with the string length -even by uniformly drawing only three words from an English dictionary, one already at most a 5% chance of getting a grammatically correct sentence 4 . A second option is then to find a fixed point in

L * ∩ (M R ) * , or in L * s ∩ (M R s ) * for sub-languages L s ⊆ L and M s ⊆ M
. This is the focus of this article and the objective of the algorithms shown in the next section.

One point that we must be careful with is that we have two opposite constraints. If we look at extremely reduced L s and M s , our work becomes easier in that we get more flexible words, but we might end up with sets too reduced to compose any complex palindrome. On the other hand, if L * s ∩ (M R s ) * has tens of thousands of words, we are too weakly constrained to aid our search efficiently. For example, the following list of 23 words correspond to the palindromic words present in both French and English. That is, for L = French, and M = English, the list is L ∩ L R ∩ M ∩ L R : {a, ana, bob, eme, ere, gag, kayak, non, pep, pop, radar, reifier, rotor, sagas, selles, sexes , shahs, sis, solos, sus, tallat, tot, tut} One can arrange the words in the list in any way one wants and have bilingual strings, but they are too constrained to make long, meaningful sentences. Thus, we are looking for a sweet spot to help human creation.

Language and dictionary choices

For this study, we chose a first set of six languages, from different -although sometimes related -language groups: English, German, French, Spanish, Polish, and Swahili. As the dictionaries chosen matter a lot for the end results, here are the details of the choices we made.

English (278 794 words): the Collins Scrabble Words word list (formerly SOWPODS) was combined with the three one-letter English words i, a, and o, and with words of length > 15 from Moby Words II (collected via [6]).

French (323 422 words): the French word list from the Hunspell wordchecker was used, collected from [START_REF] Titobouzout | Hunspell utf8 dictionaries[END_REF]. Characters with diacritics were replaced by the equivalent non-modified characters (i.e. é → e).

German (675 659 words): a word list designed for wordgames was collected from [START_REF] Enz | German wordlist for tanglet and other wordgames[END_REF]. Special characters were replaced as follows: ä, ö, ü ae, oe, ue ß ss all other characters equivalent non-modified character Spanish (635 039 words): a word list was collected from [START_REF]zeke. an-array-of-spanish-words[END_REF]. Special characters were replaced by the equivalent non-modified characters.

Polish (3 087 991 words): a Polish Scrabble word list (collected from [START_REF]Msc project implementation of manisero & turekj[END_REF]) was combined with the six one-letter Polish words (a, i, o, u, w, z) and with words of length > 15 from the Hunspell Polish word list (collected from [START_REF] Titobouzout | Hunspell utf8 dictionaries[END_REF]). We had to make some tough choices for special characters and followed phonetic rules, replacing as follows: ł w w v5 all other characters equivalent non-modified character Swahili (67 966 words): the Hunspell Tanzanian and Kenyan Swahili word lists were collected from [START_REF] Titobouzout | Hunspell utf8 dictionaries[END_REF] and combined. Special characters, all consisting of punctuation, were removed.

Algorithms

Precomputation

To make the algorithms more efficient, the first step is to remove words that are definitely not in L * ∩ (M R ) * . We can then compute the n-grams present in L, that is, subwords of length n present inside words of L. For a given word to be in L * ∩ (M R ) * , for each n-gram in the word, the n-gram has to be either an n-gram of M R , or split between multiple words of M R . For example, VENT is a 4-gram of the French word ECRIVENT, but does not exist as a 4-gram in reversed English. However, it is present in the reverse of IT NEVER.

If we denote the n-grams of L by n(L), a first idea is then to compute n(L) \ n((M R ) * ). The issue with this method is that, even if we compute n((M R ) * ) using dynamic programming, the set has a size exponential in n, which generally becomes unwieldy around n = 7.

We do this for n < 7 and remove words from L that have n-grams not in (M R ) * , getting us a new language L 2 ⊆ L. We can then go the other way and remove from M R words that have n-grams that are not present in L * 2 . We can proceed iteratively until reaching a fixed point. This fixed point is generally reached in 2 to 5 iterations, depending on n, with some examples shown as Figure 1 and Figure 2 in Section 4.

General algorithms

We can aim to compute three different intersections:

the words present in L ∩ (M R ), such as snores, which exists in both English and reversed French. the words present in L * ∩ (M R ) ∪ L ∩ (M R ) * , such as set on which exists as it is in English, and as notes in French. the words present in decompositions of strings from L * ∩ (M R ) * , which can include arbitrary long sequences of words before a common decomposition can be found.

The first kind can be computed intuitively by checking the list of words in (M) R against a prefix tree for L. That said, this list is generally too small to be directly useful, as is shown on Figure 4.

To compute the second kind, one can operate in the same way, except that the prefix tree becomes a non-deterministic automaton, with ε-transitions from final nodes to the root. This allows a word to have multiple decompositions. Although we were expecting this set to be too reduced to be useful, it is in fact already nearly too large to work with in practice for certain language pairs, as shown on Figure 5.

As the previous set is already too large, the third set becomes a priori unnecessary. It is, however, the set whose computation introduces non-trivial algorithmic questions. As we said above, the intersection language itself can be computed by getting the product of the automata made from prefix trees for L * and ((M) R ) * . The issue is that this automaton does not allow us to trivially eliminate bad candidate words (that cannot be in a bilingual palindrome). There are sufficient conditions: for example, if any node reachable by reading this word and going back to the root (on at least one dimension) can reach an accepting state, the word will appear in a decomposition. But this is not a necessary condition.

We can then create dependency graphs to simplify the process. Our goal is then to make sure to link each word to the words in the other language that are necessary for it to be in the fixed point, and look at cycles within this new graph.

For every word x ∈ L, we start by splitting it into two halves (for every possible split into potentially empty subwords): A and B. Then we know that A must be the ending of a word in M R . That is, there must be y ∈ M R such that y = CA, with a word z ∈ L = DC, and so on until both words align. Similarly, B must correspond to a node in the prefix automaton of M R , either reaching a final node or being splittable into two subwords (reflecting the process of A).

We then get two options. First we could try to compute those sequences of words until we reach either a synchronising prefix and suffix or an empty set. The latter would show that the x cannot be in the fixed point of L * ∩ (M R ) * . The former would give us a string with at least one decomposition in each language, with all the words from those decompositions being in the fixed point. The issue with this is that the direct way to do it is to compute -potentially lazily -a product automaton. To see whether A is a compatible prefix, we need the product of (L R ) * and (M) * , except that the latter is rooted in any potential node corresponding to A R . To see whether B is a compatible suffix, we need the product of L * and (M R ) * , with the former being rooted in any node reachable by B.

The issue with this method is that we once again run into complexity issues, as the product automaton still has an unwieldy size. We can then weaken our constraint temporarily to partially resolve this.

To do this, we construct four prefix automata, for L * , (L R ) * , M * , and (M R ) * . For every final node x in L * , we look at potential splittings into two halves A and B. For each splitting, we follow A R in M * , and compute a set of accepting sets (each set is composed of the last node reached, plus any final node whose ε-transition we went through). We do the same with B by following B in (M R ) * and computing the accepting sets. We then take the set of set products.

By computing the union of all those sets, we get a set of accepting sets, each of which is sufficient to ensure that x is in L * ∩ (M R ) * . If the set of accepting sets is empty, however, the word cannot be in

L * ∩ (M R ) * .
Using all those accepting sets, we add dependency relations, which are represented by directed hyperedges from nodes in M * and (M R ) * to final nodes in L * . We do the same for the final nodes in (M R ) * .

We then get a quadripartite directed hypergraph. For every node that has no hyperedge pointing towards it, we do the following: delete all the hyperedges the node is a part of as a final node; if the node has descendants, remove its final indicator and the ε-transition to the root ; if the node has no descendants, remove it entirely, and remove ascendants recursively until reaching one that is final or has another descendant; do the same operations for the corresponding node in the reversed tree of the same language.

We repeat this process until the set of nodes with no incoming hyperedge becomes empty. Alas, this method ignores the synchronisation mentioned above, but could already eliminate many words in certain contexts. Instead of computing the full product automaton, a hybrid solution would be to follow this and for each incomplete prefix and suffix to compute the first few levels of this product. For example, one could do a breadth-first search in parallel in both M * rooted in A R and in (L R ) * , to try to find either a path leading in parallel to final nodes, or to show that there exists no such path.

Data analysis

This section shows the result of the first few methods mentioned previously, to give an idea of what happens in practice on the languages considered.

We first focus on the percentage of words that gets deleted from each dictionary when we apply the n-gram elimination method until convergence for a pair of language. This depends on n, but it is easy to see that larger n remove a superset of words when we restrict ourselves to words of length at least n. We can see that 6-grams are more efficient at eliminating words, as they correspond to stricter constraints. We can also see that there is generally a last step in the iteration that removes words with very rare n-grams that depended on other rare words, with the last iteration sometimes only removing a few dozen words (Figure 1 and Appendix).

Figure 3 shows that the susceptibility of a language to vocabulary elimination depends on size, orthographic variation, and typological relationship to the other languages. Polish has an extremely high average elimination proportion: this is both due to its size and the high frequency of rare bigrams such as sz. We can observe several other patterns, such as Swahili's tendency to eliminate vocabulary from other languages and English's relatively low elimination proportion in all its language pairs, but they could be statistical artefacts. Figure 3 Graph representing the proportion of words eliminated in each language pair by using the n-gram procedure until convergence. The arrow from L to M represents the proportion of words eliminated from M. For example, Swahili removes 85.6% of Polish words, but Polish removes only 25.8% of Swahili words. The node radius grows with the square root of the language size, and the edge thickness with the proportion of words eliminated.

Instead of eliminating as many words as possible, we can also go from the other end to find words in the fixed point. Figure 4 shows the strictest fixed point, corresponding to the number of full words that are shared between L and M R , and Figure 5 shows the number of words that can be fully decomposed from one language to a reversed other.

Looking at Figure 4, we can see that the number of common words depends is related to the dictionary sizes. While the size of the Polish dictionary does inform the strong overlaps it has with all the other dictionaries, this factor does not explain the fact that it has nearly three times as many words in common with English as it does with French, which are comparably sized. This, rather, is probably due to the high variability of English orthography on account of its tendency to borrow word formation patterns from other languages [START_REF] Romaine | Variability in word formation patterns and productivity in the history of english[END_REF].

Comparing Figure 3 with Figure 4 shows a potential inverse correlation between commonword overlap and n-gram elimination. For instance, English has the largest overlap with Polish and eliminates the least of its vocabulary. This is not easily generalisable, as we can also see that while Spanish has twice as many words in common with Swahili as does French, it eliminates almost 20% more of its vocabulary. Conversely, between Figures 4 and5, the size of the common word list does not inform the mutual decomposability: French and Swahili share the fewest words, but French is highly decomposable into Swahili. Figure 5 Graph representing the proportion of words left in each language pair by only allowing perfect decomposition of one word into many. The arrow from L to M represents the proportion of words from L that can be decomposed into words from M R . For example, 16.2% of German words can be parsed in reversed Polish, whereas only 0.6% of Polish words can be parsed in reverse German. The node radius grows with the square root of the language size, and the edge thickness with the square root of proportion of words decomposed.

5

Making palindromes: the importance of grammar Sadly, the efforts shown in the previous section do not lead to language sets of reasonable sizes that are both constrained enough to be manageable and large enough to be useful. One central reason why the word sets that are left are of limited help is that, with this restricted vocabulary, one has to handle grammatical constraints and still make sense.

Returning to the original palindrome, it seems that the key to its unlikely existence is within the language itself. Latin allows a leeway that many of the modern Romance languages don't -its word order is relatively free, allowing subject, object, and verb to come in any order, though this does effect meaning [START_REF] Devine | Latin Word Order. Structured Meaning and Information[END_REF].

The freedom this creates is particularly useful in building palindromes. For instance, if one wanted to create a bilingual French-English palindrome, one would have to take into account the strict subject-verb-object order of both languages. Thus, a phrase containing a transitive verb would require the word(s) forming the verb to be in the middle and those forming subject and object to be one another's reversible counterparts. The word(s) in question must be part of the narrow strata of each language's lexicon which will reverse into a word in the other language, while making functional sense as both subject and object. In theory, then, Latin or other languages without a fixed word order -or with a flexible order, such as with Polish -make for easier target languages in the creation of bilingual palindromes.

"Evoles ut" is able to sidestep this somewhat by its arguable lack, in the English translation, of a separately expressed subject to some of the verbs. For instance: "bar" as used here is a two-place predicate, requiring both an object and subject to fulfil it and thus make it grammatical. In English this usually looks like SVO, "[you] bar it". However, the "you" here is implied by the use of an imperative aspect, so the subject is already built into the verba separate expression of it is unnecessary. Thus there is more space for wordplay, as there are fewer building blocks required for the palindrome to be grammatical in English. Essentially, the fewer additional characters required to fulfil a predicate and the more flexibility with word order, the easier it will be (in theory) to manually build a bilingual palindrome.

In this regard, Latin and Polish are both ideal. The issue with the former is that it is becoming hard to find people proficient enough to accomplish the last step of mental gymnastics to create meaningful palindromes. The issue with the latter is its heavy reliance on bigrams that are rare in other languages, whether reversed or not. For example, 51% of the words in our Polish dictionary feature a 'z', and 8.5% of them feature an 'sz', whereas the corresponding values for English are respectively 4.2% and 0.002% (and 0.003% of 'zs').

Short of using those languages, we should then rely on decorated dictionaries with indications of grammatical roles potentially held by words. However, there are few complete dictionaries featuring such information in languages other than English, and palindromists often bend some grammatical rules to achieve their ends. This practice and the fact that rare words are very frequently used in palindromes also complicate data-based methods (such as looking online whether a specific sequence of words has ever been used).

Until those problems are solved, making true bilingual palindromes will then keep a mystical aspect 6 .

6

Appendix: n-gram curves for all pairs of languages Figure 6 6-gram curves for English-French, English-German, and English-Spanish.

Figure 1

 1 Figure1Effect of removing the 6-grams using the German-Spanish pair, with curves corresponding to the different iterations. The fully reduced curve corresponds to removing the full set (including the n-grams for n < 6).

Figure 2

 2 Figure 2 Effect of removing the n-grams using the English-French pair until convergence, for different values of n, as well as the intersection of all computed sets.

Figure 4

 4 Figure 4Graph representing the number of bilingual palindrome words between pairs of languages. The node radius grows with the square root of the language size, and the edge thickness with the square root of the size of the number of bilingual palindrome words.

Figure 10 6 -

 6 Figure 10 6-gram curves for French-Swahili and Polish-Swahili.

The exact number is unknown but inferred from the single copy present as legal deposit.

We say apparently, as the existence of Étienne's work was not known to the authors until very recently, and the rarity of the surviving copies of this internal publication makes them hard to consult.

The featured palindrome is taken from the Oulipo, and reads as follows: "Ted, I beg, am I not ever a venom?" which nearly works in French as "Mon Eva rêve ton image, bidet!"

This estimate was done empirically by drawing many sentences, but corresponds to what one would expect from the proportion of the different grammatical classes in English.

This was done to maintain distinguishability from ł, and did not introduce further confusion as v is not in the Polish alphabet.

Generating Bilingual PalindromesFigure76-gram curves for French-German, French-Spanish, and French-Polish.

Figure 8 6-gram curves for German-Polish, Spanish-Polish, and English-Polish.

Figure 9 6-gram curves for English-Swahili, Spanish-Swahili, and German-Swahili.


Olivier Capra
email: olivier.capra@univ-lille.fr

Florent Berthaut
email: florent.berthaut@univ-lille.fr

Laurent Grisoni
email: laurent.grisoni@univ-lille.fr

All You Need Is LOD : Levels of Detail in Visual Augmentations for the Audience

Keywords: audience experience, augmented reality, visual augmentations, level of detail CCS Concepts, Applied computing → Performing arts, Sound and music computing, •Human-centered computing → Laboratory experiments, Mixed / augmented reality

Because they break the physical link between gestures and sound, Digital Musical Instruments offer countless opportunities for musical expression. For the same reason however, they may hinder the audience experience, making the musician contribution and expressiveness difficult to perceive. In order to cope with this issue without altering the instruments, researchers and artists have designed techniques to augment their performances with additional information, through audio, haptic or visual modalities. These techniques have however only been designed to offer a fixed level of information, without taking into account the variety of spectators expertise and preferences. In this paper, we investigate the design, implementation and effect on audience experience of visual augmentations with controllable level of detail (LOD). We conduct a controlled experiment with 18 participants, including novices and experts. Our results show contrasts in the impact of LOD on experience and comprehension for experts and novices, and highlight the diversity of usage of visual augmentations by spectators.

INTRODUCTION

Audience experience has become an important aspect in the creation of Digital Musical Instruments (DMIs), either as an evaluation method [START_REF] Barbosa | Considering audience's view towards an evaluation methodology for digital musical instruments[END_REF] or as a dimension which should be addressed at the design or performance stages [START_REF] Schloss | Using contemporary technology in live performance: The dilemma of the performer[END_REF]. In fact, DMIs may degrade the audience experience in performances, compared to acoustic instruments. Because they break the physical link between gestures and sound, they degrade the attributed agency, i.e. the perceived level of control of the musician [START_REF] Berthaut | Liveness through the lens of agency and causality[END_REF].

Furthermore, their diversity and complexity makes it difficult for the audience to build a familiarity with every instrument. As an attempt to compensate for these issues Licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0). Copyright remains with the author(s). NIME'20, July 21-25, 2020, Royal Birmingham Conservatoire, Birmingham City University, Birmingham, United Kingdom. and restore the audience experience, artists and researchers alike have designed techniques which augment the instruments with additional information. While these techniques explore different modalities (visual, haptic, auditory) and address different aspects of the performance (technical, gestural, intentional), they offer the same fixed level of information to all spectators. However, augmenting the audience experience implies considering spectators from an individual perspective. The information needed by each spectator can differ depending on their personal sensitivity and expertise. In order to ensure an optimal experience for spectators, we propose to allow the audience to dynamically change this level of information using visual augmentations with variable levels of detail (LODs).

Augmenting the audience experience

A number of augmentation techniques for spectator experience have been designed. Perhaps the simplest is the organisation of pre-concert demonstrations, such as described by Bin et al. [START_REF] Bin | Skip the pre-concert demo: How technical familiarity and musical style affect audience response[END_REF]. More common is the use of visual projections that represent the instrument structure and parameters or musician's gestures. Examples can be found in many electronic performances, with accompanying visuals displaying changes in sound processes as abstract or figurative elements. Perrotin et al. have proposed to display the musical controls of musicians in an orchestra with a video projection, to help the audience perceive the actions of each orchestra member [START_REF] Perrotin | Visualizing gestures in the control of a digital musical instrument[END_REF] by representing both gestures and musical parameters. Similarly, Correia et al. discuss the role of visuals in live performances [START_REF] Correia | The role of live visuals in audience understanding of electronic music performances[END_REF] and insist on the importance of showing both the gestures (interface) and parameters to the audience. Berthaut et al. [START_REF] Berthaut | Rouages: Revealing the mechanisms of digital musical instruments to the audience[END_REF] describe an augmented reality which can be used to reveal the mechanisms of DMIs. Haptic augmentations can also be created to increase the audience's engagement, as proposed by Turchet et al. [START_REF] Turchet | Haptification of performer's control gestures in live electronic music performance[END_REF]. All these augmentation techniques however only offer the audience fixed levels of detail.

Benford et al. [START_REF] Benford | Designing the audience journey through repeated experiences[END_REF] combine projected visual augmentations during the performance and visual/textual augmentations on a mobile app after the performance, which allow spectators to access two levels of detail. Capra et al. [START_REF] Capra | Toward augmented familiarity of the audience with digital musical instruments[END_REF] propose adaptive augmentations as part of a pipeline for augmented familiarity, but they do not provide an implementation or evaluate the impact of the described levels.

Contrary to these, in this paper we describe the design and evaluation of visual augmentations with controllable levels of detail, which allow the audience to choose the amount of information they want.

Level of detail

The level of detail (LOD) approach originates from the field of computer graphics where it is used to adapt 3D models and scenes complexity in order to reduce rendering load. It can also be found in the field of information visualisation to adapt quantity of information in order to limit visual overload. In the HCI literature, LODs allow users to access different levels of complexity in the interface, such as with Zoomable User Interfaces [START_REF] Bederson | Pad++: a zooming graphical interface for exploring alternate interface physics[END_REF], or in a musical context to build and manipulate complex musical structures [START_REF] Barbosa | Illusio: A drawing-based digital music instrument[END_REF].

In our case, LODs allow spectators to adapt the amount and the type of information provided by visual augmentations about the interactions of a musician with a DMI.

Contribution

In this paper, we describe the design and implementation of visual augmentations of Digital Musical Instruments for the audience with dynamic and controllable levels of detail. Through a controlled experiment based on a protocol proposed in [START_REF] Capra | Have a seat on stage : Restoring trust with spectator experience augmentation techniques[END_REF], we study the effect of LODs on the audience experience, and investigate how they would be used in performance settings 1 .

DESIGN AND IMPLEMENTATION

In this section, we describe the design and implementation of visual augmentations with controllable levels of detail for Digital Musical Instruments (DMIs).

Visual augmentations

Throughout this paper, we use the term visual augmentations to describe graphical representations of the controls and mechanisms of a DMI, which are superimposed on the physical performance with the help of an augmented reality display. The purpose of visual augmentations is to reveal aspects of DMIs that are not easily perceived by the audience due to their lack of familiarity with them and the absence of physical link between gesture and sound. This includes subtle and/or hidden gestures sensed by the interface, complex or unusual mappings between the gestures and the various controllable parameters and the dynamic behaviour, potential range of output and internal structure of a DMI. Following what Berthaut et al. proposed [START_REF] Berthaut | Rouages: Revealing the mechanisms of digital musical instruments to the audience[END_REF], our visual augmentations represent the three main sections of the instrument : 1) the physical interface composed of sensors (e.g. a MIDI control surface); 2) the mappings, i.e. the connections between sensors and musical parameters (e.g. the first fader controls the volume of the first audio track); 3) the processes (e.g. tracks, loops, patterns) that generate the sound.

An important aspect of visual augmentations is that they do not restrain the design of DMIs. Instrument designers and musicians are free to choose their interfaces, mappings and processes with expressiveness in mind, without worrying about the transparency [START_REF] Fels | Mapping transparency through metaphor: towards more expressive musical instruments[END_REF] of the musicians' actions or the familiarity [START_REF] Gurevich | Digital musical interactions: Performer-system relationships and their perception by spectators[END_REF] of the audience with the instrument.

However, the potential complexity of DMIs implies that visual augmentations may become too detailed if one aims at representing all their events and components, which might in turn degrade the spectator experience that we are trying to improve [START_REF] Leman | Embodied music cognition and mediation technology[END_REF]. Spectators might also prefer more or less detailed information for aesthetic reasons and at various times in the performance.

To that extent, we propose to define dedicated levels of detail for each section (Interface, Processes, Mappings) of the visual augmentations. These local LODs can be chosen independently or combined as global LODs such as the ones we describe in section 2.3.

Local LODs

The augmentations specifically designed for a section of the instrument are called local LODs. We propose 4 levels of detail for the Interface section, 3 levels for the Mappings section, and 5 levels for the Processes section 1 . Each local LOD features a level 0 in which the section is not augmented. If all three sections are at level 0, no information is added to the performance. One should note that the information provided by each level can be displayed in different ways, the representations proposed in our implementation are only one of the many possibilities that artists can explore.

In the Interface section, Level 1 only indicates the global activity, e.g. when the musician performs a gesture sensed by the system. Level 2 represents the activity of each sensor of the physical interface, allowing one to perceive fast and complex gestures such as bi-manual or multifinger interactions. Level 3 describes both the activity and the type of each sensor (discrete/continuous, shape of sensor ...). Level 4 adds a representation of their values and range.

In the Mappings section level 1 only describes to which processes the sensors are connected. Level 2 refines the connection to the parameter level. Level 3 adds a representation of the operation or series of operations which transform sensor values into parameters values [START_REF] Fels | Mapping transparency through metaphor: towards more expressive musical instruments[END_REF], e.g. scaling, inverting, combining and so on.

In the Processes section, Level 1 visualises the output of the system as a whole, merging the activity of all sound processes. Level 2 provides a detailed activity for each process of the system, e.g. a distinct shape whose size indicates the volume of the corresponding sound process. Level 3 adds a dynamic representation of parameters (i.e. inputs) that can be controlled on the processes. Level 4 adds parameters names, types and values range, i.e. as performers would see them when performing with a GUI. Level 5 provides a detailed representation of the complete internal graph of audio synthesis and effects that generate the sound of each process. It corresponds to what the musician would access when designing their instrument, and is potentially similar to the mental model they have when performing.

Global LODs

Global LODs are a combination of local LODs. They provide the spectators with a convenient way to control the level of detail by modifying several sections at a time : Interface (I), Mappings (M) and Processes (P). For instance, "SENSORS (I4-M0-PO)" is a global LOD called "SENSORS" and uses Level 4 for the Interface section and Level 0 for the others.

In the following study, we use 7 global LODs with increasing quantity of information (See Figure 1).

NONE (I0-M0-P0) provides no information at all. The performance remains unchanged.

SENSORS (I4-M0-PO) amplifies the gestures performed by displaying representations of the types and values for all sensors of the interface. It is therefore similar to the level of details provided by Turchet and Bartet [START_REF] Turchet | Haptification of performer's control gestures in live electronic music performance[END_REF] with haptics, and Perrotin et al. [START_REF] Perrotin | Visualizing gestures in the control of a digital musical instrument[END_REF] for visuals. In the case of our study, faders, knobs and buttons of a MIDI controller are displayed.

PROC (I0-M0-P2) displays the sound processes of the instrument as separate shapes with graphical parameters associated to extracted audio features (loudness with size, pitch with color hue, brightness with color luminance), allowing spectators to identify the broad structure of the instrument and the activity of processes. This LOD corresponds to the representations traditionally used to illustrate electronic music performances (e.g VJiing) and defined as audiovisual entities by Correia et al. [START_REF] Correia | The role of live visuals in audience understanding of electronic music performances[END_REF].

SENS PROC (I4-M0-P2) shows both amplified gestures and the activity of separate processes. It provides information on both the interface and processes of the instrument, without detailing its internal structure or behaviour.

MAPPINGS (I4-M1-P2) adds information pertaining to how sensors are mapped to the sound processes. It shows when a sensed gesture has an effect on a sound process but not what effect it has, i.e. not what is exactly controlled by each sensor. In our implementation, mappings are displayed as lines between sensors and processes, which appear when a control is performed and then fade out. It is similar to the level of information proposed in the Rouages project [START_REF] Berthaut | Rouages: Revealing the mechanisms of digital musical instruments to the audience[END_REF].

FULL COMBINED (I4-M2-P3) refines both the Mappings and Processes sections. It shows which parameter are controlled by each sensor and displays both the parameters and activity of the processes. In our implementation, each process is represented by a composite shape with an outer ring displaying the input parameters (i.e. gain with size, filter cutoff with color luminance, position in sample with rotation, delay feedback with shape repetition, pitch with color hue), while the activity is shown by an inner graphical element. This level is similar to the augmentations described by Berthaut et al. [START_REF] Berthaut | Liveness through the lens of agency and causality[END_REF].

FULL GRAPH (I4-M2-P5) provides a complete overview of the instrument with parameters names and value range, processes names and mappings between each sensor and the parameters. It corresponds to the mental model musicians might have of their instrument, with the exact structure, mappings and range of sonic possibilities. In our implementation, each process is labelled and displayed as a group of graphical sliders and buttons representing each parameter, with their names, value and range of values, and another slider serves as a VU-meter. Although this global LOD uses the maximum of each local LODs, we chose to limit the Mappings section to level M2 so that the amount of information remains reasonable. Similarly, the structure of the instrument used in our study is essentially a stack of samplers and effects with one parameter each, so that level P5 adds very little information compared to level P4. This structure was chosen in order to reduce the gap in quantity of information from the previous global LOD, i.e. we do not add a complex audio graph in addition to the details on parameters when going from FULL COMB to FULL GRAPH. FULL GRAPH can be seen as similar to approaches where the full complexity of the instrument is shown such as in live-coding performances.

Implementation

The implementation of visual augmentations with controllable LODs raises questions regarding how to retrieve the information from the instrument and how to give the audience access to the LODs. In this paper the visual augmentations were implemented using the Godot game engine. The information, including activity and mappings, was retrieved in real time from the instrument, implemented with Pure Data, via OpenSoundControl messages. This extraction might however be more difficult with less open software, in which case only the lower LODs might be accessible, i.e. interface and processes activity but not the internal mappings. We envision multiple possibilities for implementing visual augmentations with LODs in a performance setting.

A first one relies on individual views of the augmentations, in order to allow each spectator to choose their LOD freely. This can be implemented with a mixed-reality head-set or a mobile device as shown in Figure 2.b.

To avoid forcing the audience to wear or hold devices which may impair their experience, another possibility is to use a single spatial AR display, either projection mapping or an optical combiner (e.g. Pepper's ghost display), such as depicted in Figure 2.c, in which case viewers all perceive the augmentations spatially aligned with the physical instrument. Another possibility is to film and reproject a close-up view of the interface integrating the augmentations, as shown in Figure 2.a. This solution however moves the focus away from the physical performer. In these scenarios, only one LOD can be displayed at a time. LOD control may be performed by musicians or accompanying visual artists, so that they can modulate the audience experience during the performance. But the shared LOD can also be chosen by spectators. Voting system such as the one used in the Open Symphony project [START_REF] Wu | Open symphony: Creative participation for audiences of live music performances[END_REF] may be used, in the form of a web interface accessible from their mobile devices, as depicted in Figure 2.c. In this case the displayed LOD reflects either the majority or the average vote.

Finally, an intermediary solution is to provide multiple views of the augmentations for groups of spectators, using video (i.e. multiple or multiscopic screens) or optical AR (mirrors at multiple angles). For each group, the LOD can be fixed at a different value, so that spectators can move towards or look at the display they prefer. A voting system may also be setup separately for each group.

USAGE AND EFFECTS OF LODS

In this section, we present an experiment that aims at evaluating the impact of LODs on audience experience and understanding, and studying the use of controllable LODs by spectators with different expertise. In order to retrieve accurate and individual data on spectator experience we chose to conduct a controlled experiment in the lab. We discuss the advantages and limitations of such 'in the lab' studies in more details in [START_REF] Capra | Have a seat on stage : Restoring trust with spectator experience augmentation techniques[END_REF] and plan to address social and environmental aspects of public performances in a future work.

Procedure

18 participants (16 M, 2 F) took part in the experiment, aged of mean 29 (±7.3 , min=20, max=43). Before the beginning of the experiment, they were presented with the details of the experiment and signed a consent form. Participants sat in front of a 24" screen, equipped with headphones and a Pupil-labs Core eye-tracking device (the details of the eye tracking are addressed in a forthcoming study). We measured their expertise with the instrument presented in the study using questions regarding their practice of DMIs, their use of graphical user interfaces similar to the one in Figure 1 and their use of control surfaces. We also asked how often they attended electronic music performances. This allowed us to compute an expertise score, and we used it to separate them into two groups : 9 experts and 9 novices. The experts had a music practice of 17.3±6.4 years and an electronic music practice of 10.7±7.3 years against 1.6±2.6 of music practice and no electronic music practice for the novices. Experts had all used both graphical interfaces for music and control surfaces such as the ones presented in the experiment. Per year, experts claimed going to 12.8±8.3 electronic music performances, while for novices the average was 0.6±1.5.

Dynamic stimuli

The stimuli were videos of short performances with a DMI composed of a Korg NanoKontrol controlling a set of Pure Data patches with three sound processes (melodic, rhythm, granular texture) each with multiple parameters (See Figure 1). We designed 3 sets of mappings between the interface sensors (knobs, faders, buttons) and the parameters. Each set was intended to target a different level of contribution of the musician, i.e how much of the changes in the sound are due to them vs automated. The first set is completely manual so no changes happen without a gesture. It corresponds to the maximum contribution level. The second features automations for half the parameters, the rest being manipulated by the musician. In the third set of mappings, most parameters are automated and the musician is able to take control of some of them temporarily, giving the highest contribution to the computer.

In order to play the videos with dynamic overlapping visual augmentations, we designed the experiment in the Godot game engine. Videos were played synchronised with the playback of control data recorded in Pure Data, so that the sound and the visual augmentations were generated dynamically during the playback. This technical setup gave us the flexibility to play the video footage of a performance and to accompany it with arbitrary audio processes and visual augmentations in real time. The experiment lasted around 45mn and was composed of 2 blocks.

Block 1 : fixed LODs

In the first block, participants watched 7 LODs x 3 contribution levels = 21 videos of short performances (20s). Each video was followed by a questionnaire of 9 order-randomized questions to evaluate their experience and comprehension. The survey included only one objective question. We evaluated the ability of the participants to correctly detect the contribution levels that we induced by the mappings by answering the question "Who from the musician or the computer contributed the most to the performance ?". They also could choose 'both equally'.

The other questions were subjective and were based on 5 communication design issues introduced by Bellotti et al [START_REF] Bellotti | Making sense of sensing systems: five questions for designers and researchers[END_REF] and transposed to the spectator perspective by Gurevitch and Fyans [START_REF] Gurevich | Digital musical interactions: Performer-system relationships and their perception by spectators[END_REF]. We complement them with Association that targets the capacity to expose to spectators the contributions of the user (musician) and the system (DMI) [START_REF] Capra | Have a seat on stage : Restoring trust with spectator experience augmentation techniques[END_REF]. These design challenges are well adapted to the evaluation of NIMEs as they allow for an assessment by components of the subjective experience of spectators. Participants answered on 7-step scales to the question "To which extent do you agree with the following statement ?". Only the extreme values of the scales had a label : "I totally disagree" and "I totally agree".

• "In this video, I know when the musician is interacting with the instrument and when he is not."(Address) • "In this video, I can see when the instrument is responding to the musician gesture and when it is not." (Attention) • "In this video, I can see if the musician is controlling the instrument or if he is not."(Action) • "In this video, I can see when the instrument is properly functioning and when it is not."(Alignment) • "In this video, I can see if the musician or the instrument made a mistake."(Accident) • "In this video, I can see the contribution of the musician and the one of the computer."(Association) Finally, the participants had to report their personal rating of the performer's virtuosity and the overall performance on a 7-point scale.

Block 2 : dynamic LODs

In the second block, participants could change with the scroll wheel the LOD of the augmentations as the video Center LODs did not impact equally the subjective perception of the interactions. Experts reported higher evaluations of the subjective dimensions of the spectator experience. Right When participants could choose their favourite LODs in real time, strategies emerged as illustrated. They were refined in the interviews.

was playing. In a first task, they watched 3 short (60s) performances and were asked to select the LOD that gave them the best experience, i.e. that they preferred. In a second task, they watched the same performances and were asked instead to choose the LOD that allowed them to understand best what the musician was doing.

Results

Data was recorded, anonymised and stored in real time during the experiment by a bespoke experiment software developed in the Godot game engine. Subjective reports were obtained via likert scales and were analysed with parametric tools when the normality assumptions were met. The analyses were conducted under the common frequentist paradigm and were combined to Bayesian statistics [START_REF] Kay | Researcher-centered design of statistics: Why bayesian statistics better fit the culture and incentives of hci[END_REF]. A Bayes factor is reported as BF01 when data better support the null hypothesis and as BF10 when data support the alternative hypothesis (note that '01' becomes '10'). For example, the statement BF10 = 2.4 means that the data are 2.4 times more likely to occur under a model including the corresponding effect. The posterior odds have been corrected for multiple testing by fixing to 0.5 the prior probability that the null hypothesis holds across all comparisons. Analyses were performed with SPSS v25, R studio 1.2 and JASP [14].

Block 1 : fixed LODs

Analysis did not revealed any group effect and any effect of the levels of detail (LODs) on the objective task. Overall, the evaluation of the factual contribution ratio between the musician and the computer proved difficult.

Still, from a subjective perspective, an interesting group effect (χ 2 = 12, p = 0.002, BF10 = 11) showed that Experts considered the musician contributed more than the computer in 62% of the stimuli compared to 45.5% for Novices (Figure 3 -Left).

As depicted in Figure 3 -Center, experts reported higher evaluations of the subjective questions. Regardless of the group, the Accident was the least rated, meaning that participants were not so confident in their capacity to detect errors. The effect of the LOD was revealed on most of the subjective questions (all p-values < 0.027, all BF10 > 6), with the exception of Accident and Virtuosity (all p -values > 0.22, all BF01 > 4). Two LODs were particularly effective, SENS and FULL COMB. Reading the graph (3 -Center ) from left to right, compared to NONE, the control condition, SENS, the level of detail exposing the sole sen-sors activity, presents a significant boost in all dimensions, then PROC exposes an equivalent score to NONE. From SENS PROC to FULL COMB a rather linear progression is observed. In the Experts group, the progression tends to extend to FULL GRAPH. In a much more volatile distribution, the results for the Novices group nevertheless present FULL COMB as the most effective. The efficiency of FULL COMB for Novices is also supported by an analysis of the difference with the Experts' scores. For 6 (out of 9) dimensions, the smallest difference is measured when visual augmentations are presented with FULL COMB. This result is a good illustration of the expected role of visual augmentations, compensate the lack of expertise of novices for a better experience.

Block 2 : dynamic LODs

The score for these tasks was calculated by accumulating the time participants spent using each LOD. Both tasks, experience and comprehension, show comparable evolution characterised by a minimum for the control condition NONE and a maximum for the higher LODs (Figure 3, Right). A decisive effect of LODs was found (F (6,90) = 9.94, p < .001, BF10 > 10000) but with no difference between the groups (BF01 = 4). Novices favoured FULL COMB and SENS for experience and FULL GRAPH for comprehension. Experts chose the highest LODs for experience and FULL COMB and FULL GRAPH for comprehension.

Discussion

LODs affect subjective comprehension. The interviews confirmed and extended the quantitative analyses. Despite the absence of effect of LODs on factual perception, participants favoured levels FULL GRAPH and SENSORS for understanding the performance, especially when the music got more complex with many fast changes in the sound. This suggests that LODs influence the subjective comprehension of spectators, even if their factual understanding is not improved. It also suggests that amplifying the gestures (SENSORS level) might be more informative than displaying the activity of processes alone (PROC level).

The role of expertise. Our study reveals interesting insights on the nature of expertise in DMI spectators. Results of Block 1 showed that experts perceive an higher contribution of the musician when novices perceive a higher contribution of the computer. Also, experts put more trust in their personal representation of the interactions as proven by their higher evaluation of the Bellotti-Fyans challenges. This contrast is confirmed in Block 2 where only novices favoured the SENSORS LOD over no augmentations for a better comprehension and experience (Fig. 3 -Right), as if experts already had an internal representation of the interactions with the sensors and therefore did not need that LOD. Apart from SENSORS, both experts and novices mostly utilised FULL COMB when they could choose their favourite LOD. But when they had to choose a LOD in order to better understand the interactions, experts equally used FULL COMB and FULL GRAPH when novices massively favoured FULL GRAPH. As both groups scored poorly in the objective task in Block 1, whatever the LOD, these preferences in LOD are to be taken as subjective beliefs in a facilitation of understanding rather than a factual help.

Errors and virtuosity. The absence of effect of LODs on both the Accident dimension (i.e. the feeling of being able to perceive a potential error) and the virtuosity ratings underlines the crucial role of error perception in the emergence of a judgement of virtuosity [START_REF] Gurevich | Digital musical interactions: Performer-system relationships and their perception by spectators[END_REF]. A solution to this issue could be inspired by music video games where the virtuosity is materialised by screen indications of combos of successful moves. Such informative contents are efficient and spectacular but imply the restriction of any improvisation or non-expected techniques. Another solution would be to design LODs that inform on the virtuosity, such as visualisations of input complexity or extra-ordinary values for controls and musical parameters.

LOD choice strategies Strong differences in the choice of favoured LODs at the individual level were revealed by the data and refined by the interviews. When analysing the answers of participants regarding how they would use the LODs in public performance, we can distinguish 3 clear strategies: all or (almost) nothing:

4 participants claimed they would alternate between the maximum LOD (or just start with it) in order to form a mental image of how the instrument works (i.e. its capabilities) and then go back to no augmentations or to the SENSORS level, in order to focus on the musician's gestures. adapting to complexity / performance: 4 participants claimed they would use LODs as a way to adapt to the complexity of the instrument or music, or change it depending on the musician playing; progression: 2 participants mentioned that their appreciation of LODs evolved over time, the more complex ones becoming more enjoyable and accessible, so that they would end up not going back to the lower LODs. One must note than even within these strategies there are interpersonal variations, again highlighting the utility of a controllable LOD on visual augmentations.

CONCLUSION

In this paper, we investigated the design of levels of detail (LODs) in visual augmentations and their effect on the audience experience. While our results provide useful insights, we believe the controlled experiment approach that we took could be combined with in the wild study of performances. As future work, we think that augmentations with LODs should be extended to other interfaces, e.g. gestural controllers or graphical interfaces such as live-coding, and that the effect of aesthetic choices should be investigated.

Figure 1 :

 1 Figure 1: The 7 global levels of detail (LODs) used in our experiment, as seen by the participants. Each is built as a combination of local LODs for the Interface, Mappings and Processes sections (details in 2.2 and 2.3).

Figure 2 :

 2 Figure 2: Possible implementations 1 of visual augmentations with LODs : a) Shared close-up with Video AR projected behind the musician and artist defined LOD, b) Mobile AR with individual LOD control, c) Spatial AR with an optical combiner shared between all spectators and mobile control to vote for the LOD.

Figure 3 :

 3 Figure3: Left Regardless of the LOD, Experts perceived a higher contribution of the musician than Novices. Center LODs did not impact equally the subjective perception of the interactions. Experts reported higher evaluations of the subjective dimensions of the spectator experience. Right When participants could choose their favourite LODs in real time, strategies emerged as illustrated. They were refined in the interviews.

All stimuli, illustration videos of the conditions, anonymised raw results, statistical analyses and implementation demos can be found here : http://o0c.eu/0NA