Rafael Wanyu Liu

Lucas

D E D I C AT I O N

This thesis is dedicated to my family, mentors and friends across three continents and multiple countries, without whom, I would have not been able to arrive at where I stand today. I would like to acknowledge my appreciation to these amazing people. I am deeply indebted to Dr. Bernd Ploderer who introduced me to Human-Computer Interaction (HCI). It was a bug from the course application platform, which resulted in me taking a not-supposed-to selective course -Usability Design and Interaction in the first semester of my master study, and met Bernd who has been a tremendous mentor for me. I still remember all these afternoons that we spent in his office in Doug McDonell building where Bernd walked me through on how to conduct research and write papers step by step. I appreciate all his time and patience during my master study and his strong encouragement for pursuing a Ph.D. I am extremely grateful for my Ph.D. advisors: Professor Olivier Rioul, Professor Michel Beaudouin-Lafon, Dr. Yves Guiard, who have taught me, both consciously and unconsciously, how good research is done. Working with three advisors from three distinctive domains (Information theory, HCI, experimental psychology) has not been easy, but I have learned a great deal from these three excellent examples. All of them have been immensely helpful and motivational and made my Ph.D. experience stimulating and productive. I would like to thank them wholeheartedly, not only for their continuous support, but also for giving me so many wonderful opportunities to go to conferences and meet people. A special thanks goes to Dr. Dr. Wendy Mackay, whose enthusiasm for science has greatly influenced me for the past three years and will stay for life time.

My sincere gratitude also goes to all of those with whom I have had the pleasure to work during my Ph.D. Dr. Rafael Gregorio Lucas D'Oliveira, with whom I came up with the "BIG" idea, has been an amazing collaborator and a true friend. It took us lots of fights and beers to speak the same research language, but the outcome has become a cornerstone of my thesis. My co-authors Dr. Gilles Bailly, Professor Andrew Howes, and Professor Joanna McGrenere have provided me extensive personal and professional guidance throughout the thesis. A special mention goes to Professor Antti Oulasvirta for the valuable experience of a 2-week visit at Aalto University where we have had numerous inspirational discussions, as well as for his priceless and constant encouragement for better self development.

I would have never thought of teaching a course at the summer school without him. My Ph.D. was also enriched by the extraordinary interaction that I have had with the computational interaction community: attending Dagstuhl seminar, visiting Cambridge with Professor Per Ola Kristensson and ETH Zurich with Professor Otmar Hilliges.

For this dissertation, I would like to thank my thesis reviewers: Professor Roderick Murray-Smith and Professor Géry Casiez for their time, interest and helpful comments. I would also like to thank the two thesis examiners: Professor Joseph Jean Boutros, and Professor Otmar Hilliges for their time and insightful questions. Most of all, they have made this defense an enjoyable moment.

My time in Paris was made delightful in large part due to the many friends and groups that became a part of my life. Manos and Bruno have been like family to me. We went together to the summer school in Helsinki in 2016, CHI 2017 in Denver, after which, with Julien, we have had a lovely one-week road trip from central America to the west coast. Their presence reassures me that whatever happens, I am not alone. The three teams -Comelec, VIA, ExSitu that I was affiliated with have also been a source of friendships as well as good advice. I appreciate all the lunch discussions, sometimes intense debates, and coffee breaks with Julien, Alaa, Artur, Vincent and many other Comelec fellows; the time we spent at butte aux cailles every Thursday evening sharing visions about research and life with Marc, Michael, Arnaud, James, Sally, and sometimes Stacy, Jiali, Germán, Carla, Philip, Nacho, Chengcheng, Jean-Philippe, Janin, Mathieu and many others if I forgot to mention their names. I would also like to thank all that I have met at the summer school and conferences: Abdo, Beren, Artem, Jan, Damien, Kashyap, and my friends outside of research: Laura, Xi and Miao, with whom I have shared moments of anxiety (rarely) but also of big excitement. The dancing community has also given me constant joy: Fabian, Nadya, Thomas, Anthi, Lucia, Alexis. Thank you guys very much, especially Fabian, who has taught me everything about ballroom dancing. A very special word of thanks goes for Alex, my dancing partner and diving buddy, with whom I spin and twirl, and discover the extraordinary underwater world. This journey would not have been possible without the support of my family, who gives me unconditional love and encouragement. To my parents, thank you for raising me with a love of science, for supporting me in all my pursuits and for teaching me to always learn, laugh and love. An overview of this thesis. . . . . . . . . . . . . Figure 2 Shannon's communication scheme. . . . . . . . Figure 3 Noiseless binary and noisy channel. . . . . . . Figure 4 Schematic diagram of the choice-reaction time as a model of communication. . . . . . . . . . . Figure 5 Hick's and Hyman's data. . . . . . . . . . . . . Figure 6 Channel capacity in absolute judgement tasks. Figure 7 Schematic diagram of human motor system as a model of communication. . . . . . . . . . . . Figure 8 Results of Fitts' 4 experiments. . . . . . . . . . Figure 9 Card, Moran and Newell's description of Fitts' law. . . . . . . . . . . . . . . . . . . . . . . . . . Figure 10 Comparison between ID(ε) and ID e . . . . . . . Figure 11 Movement data as a function of ID in a wild study. . . . . . . . . . . . . . . . . . . . . . . . . Figure 12 Movement time, accuracy rate and throughput accross 3 conditions. . . . . . . . . . . . . . . . Figure 13 Guiard and Rioul's WHo model describing speedaccuracy tradeoff of aimed movement. . . . . . Figure 14 Card, Moran and Newell's description of Uncertainty Principle. . . . . . . . . . . . . . . . . Figure 15 Reaction time as a function of stimulus "information" in different tasks. . . . . . . . . . . . . Figure 16 Time measures in controlled experiments. . . . Figure 17 Reanalysis of data from Roy et al. [START_REF] Roy | Glass+ skin: an empirical evaluation of the added value of finger identification to basic single-touch interaction on touch screens[END_REF] and Liu et al. [START_REF] Liu | BIGnav: Bayesian Information Gain for Guiding Multiscale Navigation[END_REF]: reaction time as a function of stimulus uncertainty. . . . . . . . . . . . . . . . Figure 18 xT design guideline based on data categorization and xT function. . . . . . . . . . . . . . . . Figure 19 Writing in Dasher. . . . . . . . . . . . . . . . . . Figure 20 Token passing strategy. . . . . . . . . . . . . . . Figure 21 Information capacity of repeated movements. . Figure 22 Model of a user controlling sound using continuous analog sensors. . . . . . . . . . . . . . . Figure 23 Pointing without a pointer. . . . . . . . . . . . . Figure 24 The Bayesian Information Gain (BIG) framework. Figure 25 Multiscale representations and interactions. . . Figure 26 Space-scale diagrams. . . . . . . . . . . . . . . . Figure 27 Fitts' law in multiscale navigation. . . . . . . . Figure 28 GravNav and Content-aware scrolling. . . . . . Figure 29 "The River Analogy" to assist 3D navigation. .

SDAZ and Orthozoom. . . . . . . . . . . . . . . Figure 31 Controlled experiment comparing Orthozoom with SDAZ. . . . . . . . . . . . . . . . . . . . . Figure 32 Illustration of BIGnav. . . . . . . . . . . . . . . Figure 33 Navigation with BIGnav in 4 steps. . . . . . . . Figure 34 Discretization of user input in BIGnav. . . . . . Figure 35 BIGnav experimental condition. . . . . . . . . . Figure 36 Task completion time by ID in BIGnav experiment. . . . . . . . . . . . . . . . . . . . . . . . . Figure 37 Task completion time by distribution in BIGnav experiment. . . . . . . . . . . . . . . . . . . Figure 38 Number of commands by technique in BIGnav experiment. . . . . . . . . . . . . . . . . . . . . . Figure 39 Uncertainty decrease and information gain in BIGnav experiment. . . . . . . . . . . . . . . . . Figure 40 Time plot of the decrease in ID in BIGnav experiment. . . . . . . . . . . . . . . . . . . . . . . Figure 41 BIGMap. . . . . . . . . . . . . . . . . . . . . . . Figure 42 Three common views to represent files and structures. . . . . . . . . . . . . . . . . . . . . . . . . Figure 43 File retrieval practices. . . . . . . . . . . . . . . Figure 44 Search-based systems MyLifeBits and Stuff I've Seen. . . . . . . . . . . . . . . . . . . . . . . . . Figure 45 Prediction list stability v.s. Average Rank and Percentage Revisitations predicted over three datasets. . . . . . . . . . . . . . . . . . . . . . . Figure 46 Three augmented file interfaces: Icon Highlights, Hover Menus and Search Directed Navigation. Figure 47 Experiment results of the three augmented file interfaces. . . . . . . . . . . . . . . . . . . . . . . Figure 48 Ephemeral adaptation applied to menus. . . . Figure 49 SUPPLE generates personalized interfaces for users with motor impairments. . . . . . . . . . Figure 50 Adapted interfaces for users with different ethnic backgrounds. . . . . . . . . . . . . . . . . . Figure 51 Static split menu and Adaptable split menu. . Figure 52 Split, moving and visual popout interface. . . . Figure 53 The BIGFile interface. . . . . . . . . . . . . . . . Figure 54 Algorithm BIGFileFast with a binary tree. . . . Figure 55 Visualization of P12's Documents folder, a 5level tree. . . . . . . . . . . . . . . . . . . . . . . Figure 56 Simulations of BIGFileFast v.s. AccessRank. . . Figure 57 BIGFile experimental condition. . . . . . . . . . Figure 58 Task completion time and number of steps in BIGFile experiment. . . . . . . . . . . . . . . . . Auto-correction in text entry. . . . . . . . . . . Figure 85 Comparison among three measures of throughput and KSCP with or without auto-correction. Figure 86 Comparison among three measures of throughput and KSCP in the pilot study. . . . . . . . .

xvi L I S T O F TA B L E S

Table 1 A comparison of [START_REF] William | On the rate of gain of information[END_REF][START_REF] Hyman | Stimulus information as a determinant of reaction time[END_REF] and HCI studies that used Hick's law. . . . . . . . . Table 2 Full-factorial ANOVA for 3 conditions on their respective reaction times. . . . . . . . . . . . . . Table 3 Notations in Bayesian Experimental Design (BED) and in Bayesian Information Gain (BIG). . . . . Table 4 Calibration results used as prior knowledge about user behavior. . . . . . . . . . . . . . . . . . . . Table 5 Full-factorial ANOVA on TCT. . . . . . . . . . Table 6 Full-factorial ANOVA on the number of commands. . . . . . . . . . . . . . . . . . . . . . . . Table 7 Significant effects in the full-factorial ANOVA on TCT. . . . . . . . . . . . . . . . . . . . . . . . Table 8 Full-factorial ANOVA on the number of steps required to locate the target. . . . . . . . . . . . Table 9 A summary of how the three definitions of throughput change when different conditions change. . . . . . . . . . . . . . . . . . . . . . . . Table 10 A summary of different measures on the simulations of 3 keyboards. . . . . . . . . . . . . . Table 11 A summary of different measures on the simulations of 2 error types. . . . . . . . . . . . . . Table 12 A summary of different measures on the simulations with or without auto-correction. . . .

O V E R V I E W research context
Information theory, since it was first introduced by Claude Shannon back in 1948, has received much attention and successful applications in a number of domains, notably in electrical engineering. This mathematically described communication scheme outlines the information transmission process from a sender to a receiver over a noisy channel. Apart from the two remaining principles: Fitts' law and Hick's law (or the Hick-Hyman law), which came out when experimental psychologists were still enthusiastic about applying information theory to various areas of psychology, the relation of information theory to human-computer interaction (HCI) has not been clear. Even the two above-mentioned "laws" remain controversial in both psychology and HCI.

As users, we implicitly and explicitly send information to the computer to accomplish tasks and to express our intentions. Interestingly, this communication standpoint is supported by the ACM SIGCHI Curriculum for human-computer interaction [START_REF]ACM SIGCHI Curricula for Human-Computer Interaction[END_REF], which points out that "Because human-computer interaction studies a human and a machine in communication, it draws from supporting knowledge on both the machine and the human side". In recent years, we have also started seeing information theory inspire or contribute to HCI research.

This thesis strives to bridge the gap between information theory and human-computer interaction. I argue that information theory can be used as a unified tool for understanding the human-computer communication process as well as for designing interactions with more efficient communication rates. Towards this goal, I propose a Bayesian Information Gain (BIG) framework to quantify the information sent by the user to the computer and I present two interaction techniques that use BIG to improve communication efficiency. I then illustrate the advantages of using information-theoretic measures to evaluate input performance and to characterize the rich aspects of an interaction task. These two contributions are not possible without a historical walkthrough of how information theory influenced psychology and HCI. I conclude with a plea for using information theory as a unified tool to understand and design human-computer communication & interaction.

outlining contributions

This thesis is organized in 3 parts:

Part i provides a detailed historical perspective on how information theory influenced psychology and HCI. It starts with basic concepts of information theory that are used throughout the thesis and highlight how they are different from our ordinary understanding, particularly of the notion of "information". Then it goes through the history of how experimental psychologists were first excited by the ability to quantitatively measure "information", and then abandoned information theory completely under the criticism of the information theory community. Today, two principles born during this 1950's period are still used in HCI: Fitts' law and Hick's law. While Fitts' law has welcome a large number of applications, Hick's law remains rather controversial. This part continues with an in-depth discussion and analysis of how relevant Hick's law is for HCI. I argue that only by understanding the essence of information-theoretic concepts and by examining the ups and downs from a historical perspective, we can grasp the theory, clarify the misunderstandings and take advantage of it in the domain of HCI.

Part ii presents the Bayesian Information Gain (BIG) framework that is built on the scheme of human-computer communication: users send information to computers to express their intentions and interests. BIG is based on Bayesian Experimental Design using the criterion of mutual information from information theory and quantifies the information in the user input to reduce the computer's uncertainty in bits. By actively probing users for information at each interaction step, the computer can play a more active role and improve the interaction & communication efficiency.

The part first introduces the framework and demonstrates it with a 1D scenario where the computer tries to gain maximum information from the user. Then it goes in depth with two use cases in multiscale navigation and in hierarchical file retrieval respectively. We report two controlled experiments: a controlled experiment with 16 participants in multicale navigation comparing the BIG technique BIGnav with conventional pan and zoom; and a controlled experiment with 18 participants in hierarchical file retrieval comparing the BIG interface BIGFile with two other interfaces. Both experiments favor the BIG-inspired interaction technique and interface. Lastly we outline the possibilities for future work.

Part iii builds on and extends the concept that users send information to the computer through the input device or the interface, which constitute the communication channel. The information-theoretic measures quantify how much information can be transmitted (entropy), how much information is successfully transmitted (mutual information) and what is the information transmission rate (throughput). Compared to the conventional objective assessment of input techniques and interfaces, they offer a richer and more coherent description of an interaction task.

The part starts by going through some similar ideas in the HCI literature and introduces the information-theoretic measures. It then demonstrates how to use these measures in the context of command selection and text entry, comparing the information-theoretic notion of throughput with two existing definitions of throughput and outlines the coherence as well as consistency of the information-theoretic measures. Finally, I emphasize the benefits of using this general framework and discuss its potential use in other contexts as well as its limitations.

In summary, the main contributions of this thesis are:

• A historical walkthrough of information theory applications in psychology and in HCI with an extensive discussion of how relevant Hick's law is for HCI (Part i);

• A Bayesian Information Gain (BIG) framework to quantify information sent by the user to the computer (Part ii);

• An information-theoretic notion of throughput for characterizing information transmission efficiency (Part iii).

Overall, the aim of this thesis is to formally examine the humancomputer communication process using the tools of information theory. The notations X and Y used in the chapters do not always correspond to the same meaning (Fig. 1), but in both cases, I only consider information transmitted from the user to the computer. I do not consider information transmitted from the computer to the user. I illustrate two use cases in Part ii and two use cases in Part iii and discuss future perspectives in the conclusion.

The content of this thesis is based on work already published or under review, and more specific details will be given at the beginning of each chapter. I do not provide a separate chapter for the related work, but prefer to refer to it as research context that motivates the work at the beginning of each treated subject.

Part I I N F O R M AT I O N T H E O R Y I N P S Y C H O L O G Y A N D I N H C I
The goal of this part is to provide a historical perspective on how information theory influenced psychology and HCI. It starts with basic concepts of information theory that are used throughout this thesis. Then it outlines a number of information theory applications in psychology and in HCI and provides an in-depth discussion and analysis of how relevant Hick's law is for HCI.

I argue that by understanding the basic concepts of information theory and walking through history, we as a community can better understand why information theory has not been successfully applied in experimental psychology, clarify the misunderstanding that we hold so far and further take advantage of the theory in the domain of HCI.

Information in the sense of information theory is defined against our common sense. We ordinarily think of information as a collection of facts, a file of meaningful data. The key to Shannon's theory is precisely that he deliberately avoided the question of meaning. Here information measures randomness or uncertainty of the outcome of a random variable and is captured by an entropy function, defined as follows (entropy of a discrete random variable X):

H(X) = - x p(x) log 2 p(x). ( 1
)
where X is drawn according to the probability distribution p(x) = P(X = x) and entropy H(X) is measured in bit. The higher the entropy, the more uncertain the outcome, the harder the prediction. Entropy measures "information" in the sense that the outcome of a random variable will increase the receiver's knowledge (or decreases the receiver's uncertainty).

A simple example is the weather on the next day. If the chance of rain is 0% and the chance of sun is 100%, the entropy is 0 as it is a sure event. However, if the chance of rain and chance of sun are 50% each, the entropy reaches its maximum, 1 bit, as the uncertainty about the weather is maximal. In other words, a message brings maximum "information" to those who receive it. Equiprobable messages generate maximum entropy.

Entropy is bounded by sure event and maximum random event 0 H(X) log 2 N:

• Entropy is zero if the event is sure or it is impossible:

H(X) = 0 if p(x) = 0 or 1.
• Entropy of a set of N equiprobable messages:

H(X) = log 2 N if p(x) = 1 N .

mutual information and equivocation

Since information is transmitted over a noisy channel, some information might get lost. The actually transmitted information, which is captured by mutual information, characterizes the amount of information that is effectively transmitted through the channel. Mutual information of two discrete random variables X and Y is defined as follows:

I(X; Y) = y x p(x, y) log p(x, y) p(x)p(y) = H(X) -H(X|Y). (2)
where p(x, y) is the joint probability function of X and Y, and p(x) and p(y) are the marginal probability distribution functions of X and Y respectively.

Mutual information is also bounded by two quantities 0 I(X; Y) H(X):

• If no messages get transmitted from the source to the receiver, mutual information is 0;

• If all messages get transmitted from the source to the receiver, mutual information is entropy H(X).

Continuing with the weather example: if a person needs to tell a friend about the weather she experienced last week, she says"rainy on Monday, sunny on Tuesday, rainy on Wednesday, sunny on Thursday, rainy on Friday and sunny on Saturday". The information she is transmitting is H(X) = 1 bit, since P(rain) = 50% and P(sun) = 50%. If her friend perfectly receives all the information, the mutual information is I(X; Y) = H(X) = 1 bit. But if her friend does not receive anything, the mutual information is 0. If her friend is distracted and hears "rainy on Monday, sunny on Tuesday, rainy on Wednesday, sunny on Thursday, rainy on Friday and rainy on Saturday", most of the information is transmitted but one day's weather condition is lost. Here the mutual information is between 0 and 1 bit.

The information lost in transmission is captured by equivocation H(X|Y) (Equation 2). It describes the receiver's uncertainty about the source after the transmission given the channel output Y. In an ideal channel without noise, equivocation H(X|Y) would be zero and mutual information I(X; Y) = H(X): information is perfectly transmitted from the source to the destination.

Equivocation is related to how errors are made. Particularly, Fano's inequality [START_REF] Thomas | Elements of information theory[END_REF]Theorem 2.4.1] relates the average information lost in a noisy channel to the probability of the categorization error:

H(X|Y) H(E) + P e × H(Z|E = 1). (3)
where random variable E represents errors, P e represents error rate and random variable Z represents the noise in the channel that perturbs the effective transmission due to errors. We will provide a more detailed discussion in Chapter 15 when this notion is needed.

channel capacity and throughput

The "information" channel has a certain capacity, computed as the maximum amount of mutual information I(X; Y) conveyed by the channel. It is defined as (a discrete memoryless channel):

C = max p(x) I(X; Y). ( 4
)
where the maximum is taken over all possible input distributions p(x).

The well-known Shannon's theorem [START_REF] Shannon | A mathematical theory of communication[END_REF]Theorem 17], which inspired Fitts' law [START_REF] Paul | The information capacity of the human motor system in controlling the amplitude of movement[END_REF], applied the channel capacity concept to an additive white Gaussian noise (AWGN) channel with B Hz bandwidth and signal-to-noise ratio S/N, measured in bits per second:

C = B log 2 1 + S N (5)
Furthermore, the theorem states that given a noisy channel with channel capacity C and information transmitted at a rate R, then if R < C, there exists a code that allows the probability of error at the receiver to be made arbitrarily small [START_REF] Thomas | Elements of information theory[END_REF]Theorem 8.7.1]. This transmission rate R is widely used in wireless network communication, packet-based schemes, etc. to measure an effective speed of data transmission, which is also known as throughput (T P). One common computation of throughput is dividing successfully transmitted information (mutual information) by the time it takes to transmit such information. For instance, if a friend is telling another friend perfectly about the weather condition in 10 seconds (T ), then the throughput in this case is:

T P = I(X; Y) T = 1/10 = 0.1 bits/s. (6)
The notions of entropy and mutual information are used throughout the thesis. Equivocation and throughput will be discussed and compared in Part iii.

I N F O R M AT I O N T H E O R Y I N P S Y C H O L O G Y

Although information theory is still alive and well in a number of fields, it went through a rather interesting development in psychology: experimental psychologists were first swept by a wave of excitement for information theory during the 1950s and 1960s, then experienced a period of critical analysis and finally decided on the incompatibility between information theory and psychology. In the article Whatever Happened to Information Theory in Psychology?, Luce [START_REF] Duncan | Whatever happened to information theory in psychology?[END_REF] explains that "... after an initial fad in psychology during the 1950s and 1960s it [information theory] no longer is much of a factor, beyond the word bit, in psychological theory." While it is still well applied in biology, engineering, computer science, physics, and statistics, it is true that psychologists today are no longer supporters of information theory.

In this chapter, I examine the dramatic changes of information theory in psychology.

enthusiasm at the early stage

Even though Shannon himself strongly preferred the term communication theory to information theory, psychologists in the 1950s and 1960s seemed to be thrilled by the ability to quantitatively measure information and to investigate human information capacity in various psychological contexts. Note that the applications of information theory during this period exclusively explored these two concepts but left most of the engineering parts (e. g. channel coding) of the transmission process aside.

Measuring Information

The Entropy of Language An important example of an information source is English text [START_REF] Shannon | A mathematical theory of communication[END_REF][START_REF] Shannon | Prediction and entropy of printed English[END_REF]. If we assume that the alphabet of English consists of 26 letters and the space symbol, and ignore punctuation and the difference between upper and lower case letters, we can construct models of English using empirical distributions collected from samples of text1 . Using such a method, Shannon [START_REF] Shannon | A mathematical theory of communication[END_REF] estimated that the entropy of English is 4.14 bits per letter.

We can also build more complex models by incorporating conditional probability as we know that the frequency of pairs of letters is also far from uniform. For example, the letter Q is always followed by a U. The most frequent pair is TH, which occurs with a frequency of about 3.7%. We can use the frequency of the pairs to estimate the probability that a letter follows any other letter. For example, to build a fourth order Markov approximation, we must estimate the values of p(x i |x i-1 , x i-2 , x i-3 , x i-4 ). Such a model gives an estimation of 2.8 bits per letter.

Similarly, Shannon estimated the word-entropy of printed English as 11.82 bits per word. Later on, Grignetti [START_REF] Grignetti | A note on the entropy of words in printed English[END_REF] estimated the word entropy in printed English as 9.83 bits using a different word sample. Miller et al. [START_REF] Miller | The intelligibility of speech as a function of the context of the test materials[END_REF][START_REF] George | Verbal context and the recall of meaningful material[END_REF] also studied the word context, particularly the extent to which the prior occurrence of certain verbal elements (word choice) influences the talker's present choice. For instance, if the talker has said "children like to," his choice for the next word in this pattern is considerably limited -elephant, punished, loud, Bill, and many other words are highly unlikely continuations.

These statistics of English are useful in decoding encrypted English text and in word prediction. A commonly used model is the trigram (second-order Markov) word model, which estimates the probability of the next word given the previous two words, as seen in intelligent text input and speech recognition systems these days. We can also apply the techniques above to estimate the entropy rate of other information sources such as images and other multimedia content.

The Information in Stimuli

The relationship between the number of alternate stimuli and choice-reaction times was first reported by Helmholtz [START_REF] Helmholtz | Ueber die Fortpflanzungsgeschwindigkeit der Nervenreizung[END_REF] in 1850, Donders in 1868 [START_REF] Cornelis | Die schnelligkeit psychischer processe (On the speed of mental processes)[END_REF] and then by Merkel in 1883 [START_REF] Merkel | Die zeitlichen verhältnisse der willensthätigkeit (The Temporal Relations of the Actions of Will, or The Timing of Voluntary Action)[END_REF]. Using 1 to 10 alternatives, Merkel discovered that it takes longer to respond to a stimulus when it belongs to a large set as opposed to a smaller set of stimuli. This was later on taken by psychologists, notably Hick [START_REF] William | On the rate of gain of information[END_REF] and Hyman [START_REF] Hyman | Stimulus information as a determinant of reaction time[END_REF], as an analogy to information theory: the display is the transmitter of information; each alternate stimulus the message; the sensory-perceptual system the channel; the participant the receiver, and the appropriate action the destination [START_REF] Richard | Information theory of choicereaction times[END_REF] (Fig. 4).

Hick was clearly motivated by finding a formula to capture the "reaction-time era" as other psychologists discussed the increase in reaction time with the number of alternatives and attributed it to such causes as the division of attention or a reduction in the effective intensity of the stimulus, but not with quantitative theory. The only reference to a mathematical relation between reaction time and number of alternatives was by Blank [START_REF] Blank | Brauchbarkeit optischer Reaktionsmessungen (Usability of optical reaction measurements)[END_REF], where a logarithmic relation was mentioned without further explanation.

Hyman used 8 lights in a matrix of 36 lights (6 rows by 6 columns) display and used names -Bun, Boo, Bee, Bore, By, Bix, Bev, and Bate -to designate them. At the beginning of each trial, the experimenter gave a warning signal and 2 seconds later turned on one of the 8 lights and started a timer. Participants responded by calling out the designated name of the light. A throat microphone attached to the participant activated an electronic voice key to stop the timer. Four subjects participated in the experiments and they all attended more than 40 experimental sessions over a 3-month period with approximately 15,000 reaction times recorded for each subject. All errorless performance.

The first experiment replicated Merkel's and Hick's experiment using 8 conditions with different numbers of equally probable alternatives. The second experiment had 8 conditions which involved different numbers of alternatives and different probabilities of the occurrence of these alternatives, therefore varying the average information content by altering the probability of occurrence of each choice. The last experiment also had 8 conditions and introduced sequential dependencies between successive choices of alternatives. In each condition, each of the alternatives had equal likelihood of occurring but its probability was conditional. For example, in condition 1, where two alternatives were used, the conditional probability of b given that a has occurred was p(b|a) = 0.8. These conditions yielded entropies ranging from 0.72 to 2.81 bits.

With the three experiments, Hyman [104, p.196] concluded:

"The reaction time to the amount of information in the (visual) stimulus produced a linear regression for each of the three ways in which information was varied."

His formula is written as:

RT = a + b × H T . ( 8
)
where RT is reaction time, a and b are empirically determined constants, and H T is the transmitted information captured by log 2 n for equiprobable stimuli orn i=1 p i log 2 p i for non-uniformly distributed stimuli with probability p i .

Investigating Information Capacity

Information Capacity of Working Memory The Magical Number Seven, Plus or Minus Two: Some Limits on Our Capacity for Processing Information by Miller [START_REF] Miller | The magical number seven, plus or minus two: Some limits on our capacity for processing information[END_REF] is one of the most highly cited papers in psychology. Miller demonstrated that the number of objects an average human can hold in working memory is 7 ± 2.

Index of Difficulty (ID) states that the minimum amount of information required to produce a movement having a particular average amplitude plus or minus a specified tolerance (variable error) is proportional to the logarithm of the ratio of the tolerance to the possible amplitude range:

ID = log 2 2A W . ( 9
)
Index of Performance (IP) shows the capacity of the human motor system. It is measured in bits per unit time and is homologous to the rate of gain of information in Hick's paradigm [START_REF] William | On the rate of gain of information[END_REF] and analogous to Shannon's channel capacity:

IP = ID MT . ( 10
)
where MT is the empirically determined movement time.

Fitts reported that IP ranged from 10.3 to 11.5 bits/s in Experiment 1; 7.5 to 10.4 bits/s in Experiment 2; and 8.9 to 12.6 bits/s in Experiment 3. He concluded that the rate of performance (IP) in a given type of task is approximately constant over a considerable range of movement amplitudes and tolerance limits, but falls off outside this optimum range. The level of optimum performance was found to vary slightly among the three tasks in the range between about 10 to 12 bits/s. It was not until 1964, by examining the effects of response amplitude and terminal accuracy on 2-choice reaction time (RT ) and on movement time (MT ) that Fitts found the correlation between ID and MT was found to be above 0.99 over the ID range from 2.6 to 7.6 bits per response [START_REF] Paul | Information capacity of discrete motor responses[END_REF]. Therefore, the Fitts' law that we know today is written as:

MT = a + b × ID. ( 11
)
where a and b are empirically determined constants. All above-mentioned studies except Fitts (1964) were done during the 1950s and most of these applications were summarized in a book by Attneave [START_REF] Attneave | Applications of information theory to psychology: A summary of basic concepts, methods, and results[END_REF].

from criticism to abandonment

While psychologists were still enthusiastic about applying information theory, Shannon and the information theory community started to challenge the use of information theory outside the sphere of communication engineering.

Shannon himself was among the skeptics as he is quoted as saying "Information theory has perhaps ballooned to an importance beyond its actual accomplishments" (cited in [START_REF] Johnson | Claude Shannon, mathematician, dies at 84[END_REF]). He insisted that "the use of a few exciting words like information, entropy, redundancy, do not solve all our problems" [START_REF] Shannon | The bandwagon[END_REF]. Elias [START_REF] Elias | Two famous papers[END_REF], an important figure of the information theory community, urged authors to stop writing papers using information theory outside of its intended scope.

Reflecting on its applications in psychology, McGill [START_REF] William | Applications of information theory in experimental psychology[END_REF] also stated that "The somewhat fortuitous marriage of the information measures and information theory may, in the long run, prove to have confused psychologists as much as it has stimulated them." He mentioned that perhaps the most important reason is that Shannon's information measure is not the sort of information with which we are familiar, and psychologists have made very little use of the performance criteria and of the basic theorems of information theory apart from the notion of channel capacity.

Garner [START_REF] Garner | Uncertainty and structure as psychological concepts[END_REF] not only summarized the ideas and experiments of information-theoretic applications in psychology, but also expanded the interest to the relation between mean response times and the uncertainty of the stimuli to which participants were responding. In early experiments, mean response time appeared to grow linearly with uncertainty, but glitches soon became evident. Laming [START_REF] Richard | Information theory of choicereaction times[END_REF] in the late 1960s also commented on the choice-response paradigm that "This idea does not work... there are further unpublished results that show it to be hopeless". Substantial sequential effects exist between a stimulus and at least the immediately preceding stimulus-response pair, but with the magnitude of the correlation dropping from close to one for small signal separation in either decibels or frequency to about zero for large separations [START_REF] David M Green | Variability and sequential effects in magnitude production and estimation of auditory intensity[END_REF]. Similarly, Bertelson [START_REF] Bertelson | Sequential redundancy and speed in a serial two-choice responding task[END_REF] expressed that the paradigm could be explained as a sequential effect independently of stimulus entropy.

Gradually, as the importance of this reality began to set in at the end of the 1960s, one saw fewer -although still a few -attempts to understand global psychological phenomena in simple information theory terms. When Shannon died on February 24, 2001, at age 84, several psychologists paid homage to this creator of information theory by looking back at history. The same year, Laming [START_REF] Laming | Statistical information, uncertainty, and Bayes' theorem: Some applications in experimental psychology[END_REF] provided a detailed critique. He mentioned that Shannon's way of defining capacity requires that not individual signals be transmitted but rather very long strings of them so as to get rid of redundancies. This is rarely possible within psychological experiments, e. g. a choice-reaction experiment involves the transmission of single stimuli, one at a time, a condition that affords no opportunity for the sophisticated coding on which Shannon's theorem depends.

Furthermore, under the influence of Shannon's theory, psychologists are inclined to suppose that information is absolute. The truth is that it is not. Data is absolute, but information is always relative to the two hypotheses between which it distinguishes. Criticizing the human observer as a physical system, Laming [START_REF] Richard | Mathematical psychology[END_REF] also put forward the difference between information available to the observer and the partitioning of values of that information between the available responses (the choice of criteria). As he said "Looking solely at information throughput, and disregarding the criteria, it can be shown that the information available to the observer is derived from a sensory process that is differentially coupled to the physical stimulus, because the component of information derived from the stimulus mean is entirely absent from the information implicit in the observer's performance".

Luce [START_REF] Duncan | Whatever happened to information theory in psychology?[END_REF] in 2003 echoed this statement by further elaborating on the incompatibility between information theory and psychology. He argued that the elements of choice in information theory are absolutely neutral and lack any internal structure; the probabilities are on a pure, unstructured set whose elements are functionally interchangeable. That is fine for a communication engineer who is totally unconcerned with the signals communicated over a transmission link; interchanging the encoding does not matter at all. By and large, however, the stimuli in psychological experiments are to some degree structured, and so, in a fundamental way, they are not in any sense interchangeable. If one is doing an absolute judgment experiment of pure tones that vary in intensity or frequency, the stimuli have a powerful and relevant metric structure, namely, differences or ratios of intensity and frequency measures between pairs of stimuli. Similarly, if one does a memory test, one has to go to very great pains to avoid associations among the stimuli. Stimulus similarity, although still ill understood and under active investigation, is a powerful structural aspect of psychology.

In summary, the word information has been almost seamlessly transformed into the concept of "information-processing models" in which information theory per se plays no role. The idea of the mind being an information-processing network with capacity limitations has stayed with us, but in far more complex ways than pure information theory.

which minimum amount of information?

Fig. 9 shows Card, Moran and Newell's description of Fitts law. Note that the version shown in their book was not Fitts' original formula. This formula was in fact proposed by Welford [START_REF] Traviss | The measurement of sensorymotor performance: survey and reappraisal of twelve years' progress[END_REF], who argued that the formulation log 2 D W + 0.5 makes movement time dependent on a kind of Weber fraction 2 in that the subject is called upon to distinguish between the distances to the far and the near edges of the target.

Fitts originally denoted ID = log 2 2D W to express the minimum amount of information. This expression is still being used in psychology today [START_REF] Mottet | Trajectory formation principles are the same after mild or moderate stroke[END_REF][START_REF] Plamondon | Speed/accuracy tradeoffs in target-directed movements[END_REF]. The HCI community, on the other hand, has unanimously adopted Mackenzie's formulation to describe task difficulty, written as:

ID = log 2 (1 + D W ).
This improvement, according to Mackenzie [START_REF] Mackenzie | Fitts' law as a research and design tool in human-computer interaction[END_REF], was more consistent with Shannon's Theorem 17 and the available empirical data. Gori et al. [START_REF] Gori | Speed-Accuracy Tradeoff: A Formal Information-Theoretic Transmission Scheme (FITTS)[END_REF] recently used the notion of "geometrically uniformly distributed targets" and proved that this version of ID is indeed equivalent to Shannon's Capacity.

Mackenzie [START_REF] Mackenzie | Fitts' law as a research and design tool in human-computer interaction[END_REF] also proposed to measure movement endpoints from the center of the target and, assuming that the distributions of these measures is normal, to compute an effective index of difficulty ID e , written as:

ID e = log 2 1 + D W e . ( 12
)
where D corresponds to the average covered distance and W e is the effective width. The computation of W e is detailed in [START_REF] Soukoreff | Towards a standard for pointing device evaluation, perspectives on 27 years of Fitts' law research in HCI[END_REF]. Let σ denote the standard deviation of the endpoint distribution, and ε the error rate, e. g. the proportion of target misses:

If σ is available: W e = 4.133σ

If not:

W e = W × 2.066 z(1-ε/2) if ε > 0.0049% 0.5089 × W otherwise. ( 13
)
2 The Difference Threshold (or "Just Noticeable Difference") is the minimum amount by which stimulus intensity must be changed in order to produce a noticeable variation in sensory experience. It was first proposed by Ernst Weber, who observed that the size of the difference threshold appeared to be lawfully related to initial stimulus magnitude [START_REF] Theodor | Elements of Psychophysics (translated by Adler HE[END_REF]. This relationship, known as Weber's law: ∆I I = k where ∆I represents the difference threshold, I represents the initial stimulus intensity and k signifies that the proportion on the left side of the equation remains constant despite variations in the I term.

the average of minimum or the average of average?

Fitts needed the participant (S) to work at his maximum rate, so that the resulting movement times MT reflected S's full commitment to the pointing task. Therefore, the average time per response in Fitts' term corresponds to "average minimum", which seemed to have confused many. Authors in Fitts' law research use different wordings, which suggest other interpretations of MT : Soukoreff and Mackenzie [START_REF] Soukoreff | Towards a standard for pointing device evaluation, perspectives on 27 years of Fitts' law research in HCI[END_REF] considered "movement time performance for rapid aimed movements", Hoffman [START_REF] Errol R Hoffmann | Which version/variation of Fitts' law? A critique of information-theory models[END_REF] "movement time", and Drewes [START_REF] Drewes | Only One Fitts' Law Formula Please![END_REF] "mean time". Consequently, Fitts' law has always been considered as a law of average performance.

Yet historically speaking, Fitts' information-theoretic rationale for aiming movements considers the transmission of information about the target through a human motor channel. Fitts' law can be derived by computing the capacity of this channel, which is a theoretical upper bound -the maximum amount of information that can be transmitted reliably -and which is accordingly calculated as an extreme through the Channel Coding Theorem -the maximum of mutual information over all input distributions. Hence, only movements that maximize transmitted information should be relevant for the derivation of Fitts' law. But can one always reach his or her maximum performance? Participants can be instructed to perform as fast as they could in a controlled experiment. In the real world, however, one rarely tries to point as fast and as accurately as possible. Even in a controlled experiment, participants' attention fluctuates.

Building on Guiard and colleagues [START_REF] Guiard | On the measurement of movement difficulty in the standard approach to Fitts' law[END_REF][START_REF] Guiard | A Mathematical Description of the Speed/Accuracy Trade-off of Aimed Movement[END_REF], Gori et al. [START_REF] Gori | Speed-Accuracy Tradeoff: A Formal Information-Theoretic Transmission Scheme (FITTS)[END_REF] recently argued that Fitts' law should be considered as a law of performance limit. They introduce this concept by reanalyzing the data from a pointing study run "in the wild" [START_REF] Chapuis | Fitts' law in the wild: A field study of aimed movements[END_REF]. For several months Chapuis et al. [START_REF] Chapuis | Fitts' law in the wild: A field study of aimed movements[END_REF] unobtrusively logged cursor motion from several participants using their own computer. The authors were able to identify offline the start and end of pointing movements as well as the target information, for several hundreds of thousands of click-terminated movements. With this information, one can then represent the movements in a MT versus ID graph, as normally done in a controlled Fitts' law study. To compute task difficulty in the 2D space of computer screens, they followed the suggestion of Mackenzie and Buxton [START_REF] Mackenzie | Extending Fitts' Law to Two-dimensional Tasks[END_REF] and chose ID = log 2 1 + D min(H,W) where H and W are the height and width of the target, respectively. Whenever an item was clicked, it was considered the target, meaning the rate of target misses was zero percent.

does throughput equal channel capacity?

It seems that Mackenzie, Zhai and Guiard all agreed that this speedaccuracy tradeoff paradigm, namely throughput, is described and supported by Fitts' law.

• Mackenzie [START_REF] Mackenzie | Fitts' Throughput and the Speed-accuracy Tradeoff[END_REF]: "We describe an experiment to test the hypothesis that Fitts' throughput is independent of the speed-accuracy tradeoff";

• Zhai [START_REF] Zhai | Characterizing computer input with Fitts' law parameters -the information and non-information aspects of pointing[END_REF]: "Throughput (TP), also known as index of performance or bandwidth in Fitts' law tasks, has been a fundamental metric in quantifying input system performance";

• Guiard [START_REF] Guiard | A Mathematical Description of the Speed/Accuracy Trade-off of Aimed Movement[END_REF]: "The trade-off is described by the Fitts' law".

However, from previous analysis we know that what Fitts [START_REF] Paul | The information capacity of the human motor system in controlling the amplitude of movement[END_REF][START_REF] Paul | Information capacity of discrete motor responses[END_REF] called the index of performance represents the maximum rate and channel capacity (as demonstrated by Gori et al. [START_REF] Gori | Speed-Accuracy Tradeoff: A Formal Information-Theoretic Transmission Scheme (FITTS)[END_REF]), which, in engineering terms, is the maximum rate at which data could be potentially transmitted. Yet throughput captures the actually transmitted information rate, which is bounded by the channel capacity 3 . Even though Fitts' law has firm empirical validation, we invite the HCI community to revisit these three questions: What is the minimum amount of information? Should we take the average of the minimum or the average of the average? What are we measuring -throughput or capacity?

It has been claimed to apply to a large number of contexts, including menu design, device settings and road signs. Essentially, when faced with a set of choices, this "Hick-based" design principle guides interface design with the concept less is more (or rather, fewer is better).

• In practice, it has not seen many successful applications. Only a few HCI publications incorporate Hick's law, e. g. Soukoreff & Mackenzie [START_REF] Soukoreff | Theoretical upper and lower bounds on typing speed using a stylus and a soft keyboard[END_REF]. In 2005, Seow [187] compared Hick's law and Fitts' law, the two information-theoretic principles, and examined the possible reasons for the lack of uptake of Hick's law to gain momentum in the field. Nevertheless, few studies have incorporated Hick's law into their work since then, e. g. Cockburn et al. [START_REF] Cockburn | A Predictive Model of Menu Performance[END_REF].

The controversial aspect of Hick's law and the lack of comprehensive understanding may explain why many HCI researchers have not ventured to apply it to interaction tasks. Furthermore, there seems to be different definitions of Hick's law. While for psychologists the law has exclusively to do with the context of the choice-reaction paradigm, HCI researchers seem to apply it whenever choices are presented to the user, including for visual search time, e. g. [START_REF] Landauer | Selection from Alphabetic and Numeric Menu Trees Using a Touch Screen: Breadth, Depth, and Width[END_REF][START_REF] Mackenzie | Text entry using soft keyboards[END_REF][START_REF] Wobbrock | From Letters to Words: Efficient Stroke-based Word Completion for Trackball Text Entry[END_REF], decision time, e. g. [START_REF] Cockburn | A Predictive Model of Menu Performance[END_REF] or reaction time, e. g. [START_REF] Roy | Glass+ skin: an empirical evaluation of the added value of finger identification to basic single-touch interaction on touch screens[END_REF]. Does the law really apply to these settings?

This chapter strives to clarify some misunderstanding about Hick's law so as to provide a clearer picture of the choice-reaction paradigm in HCI studies. First, I re-examine HCI studies that have used Hick's law and revisit the historical context of the choice-reaction paradigm in psychology. I then demonstrate that a number of logarithmic phenomena observed in HCI do not justify the law; conversely, I show that the choice-reaction paradigm does not always scale logarithmically with the number of choices. I conclude with the practical implications of this new look at Hick's law for HCI.

hci applications of hick's law

I first review HCI studies that have used Hick's law. I describe their respective contexts and tasks, and highlight the inconsistencies that emerge.

Modeling Menu Performance

In a menu selection task, Landauer & Nachbar [START_REF] Landauer | Selection from Alphabetic and Numeric Menu Trees Using a Touch Screen: Breadth, Depth, and Width[END_REF] asked participants to select a target item (a number in the ordered list from 1 to 4096, or a word in a list of 4096 alphabetically ordered words) by a series of touch menu choices among sequentially subdivided ranges.

The number of alternatives at each step was 2, 4, 8, or 16. The authors found that a logarithmic function fits the mean response time (T ) well, as implied by Hick's law (reaction time RT ) and Fitts' law (movement time MT ):

T = c 1 + k 1 log b RT + c 2 + k 2 log d w MT = c + k log b. ( 16
)
where c and k are empirically determined constants, b is the number of alternatives at each step, d is the distance moved and w the width of the target that must be hit. Since the target width w was proportional to 1/b in their experiment, the Fitts' law term log d w reduces to log b.

Landauer & Nachbar also observed that "in the most extreme case (words), total selection time varied from 23.4 down to 12.5 seconds for branching factors of 2 to 16". They consequently concluded that broader, shallower menu trees yield faster search time than narrower, deeper ones (p. 76).

Cockburn et al. [START_REF] Cockburn | A Predictive Model of Menu Performance[END_REF] present a predictive model for linear menu performance that uses the "Hick-Hyman law" to model decision time for expert users. They state that the decision time is dependent on the entropy of each item H i = log 2 (1/p i ). Therefore, decision time for each item is given by

T hhi = b hh × H i + a hh .
The authors conducted a calibration study with 8 participants, varying menu length (2, 4, 8 and 12 items) and block (1 to 7 for two static menu conditions and 1 to 3 for a random condition) and using a uniform distribution of target occurrences. Removing data from block 1 where participants were mostly doing visual search, they found that the decision time could be modeled as T hhi = 0.08 log 2 n + 0.24 with R 2 = 0.98. They then used the values of a hh and b hh for the real experiment, which used a Zipfian distribution 2 to account for target frequencies and found that decision time followed Hick's law. It is unclear how they applied the law though, namely whether H i in the real experiment was computed as b hh × log 2 (1/p i ) + a hh or as b hh × (p i × log 2 (1/p i )) + a hh . Either way seems problematic as the constants were derived from a uniformly distributed menu.

2 A Zipfian distribution is defined as: f(k; s, N) = 1/k s N n=1 (1/n s )
where N is the number of elements, k ∈ [1, N] the rank of the considered element (with k = 1 is the element with highest frequency) and s the value of the exponent characterizing the distribution.

Modeling Text Entry

Hick's law has also been used for modeling text entry. Investigating the theoretical upper and lower bounds of typing speed using a stylus on a soft keyboard, Soukoreff & Mackenzie [START_REF] Soukoreff | Theoretical upper and lower bounds on typing speed using a stylus and a soft keyboard[END_REF] argue that Hick's law can be used to account for the visual scan time (RT ) of each entry, in order to compute the lower bound of the typing rate:

RT = a + b log n. ( 17
)
where n is the number of choices and a and b are empirically determined constants.

Borrowing from Welford [START_REF] Traviss | Fundamentals of skill[END_REF], they set a = 0 and b = 1/5 = 0.2 as Welford states that for subjects in their twenties using key presses to signal choices, the reciprocal of the slope of Hick's law lies is between 5 and 7 bps. Therefore, with a 27-character alphabet (26 letters plus space), n = 27, the lower bound of the visual scan time for novices is:

RT = 0.2 log 2 27 = 0.951 seconds. ( 18
)
This model was rejected by empirical investigations by Mackenzie et al. [START_REF] Mackenzie | An empirical investigation of the novice experience with soft keyboards[END_REF][START_REF] Mackenzie | Text entry using soft keyboards[END_REF] who observed about twice the time expected of 0.951 seconds for visual scanning. Mackenzie et al. concluded that "Although the Hick-Hyman metric may still be valid in general, clearly as applied here it is confounded with the complex movement behavior we observed".

Sears et al. [START_REF] Sears | The role of visual search in the design of effective soft keyboards[END_REF] also illustrate that it is inappropriate to use Hick's law for a simple visual search component task, such as the one introduced by Soukoreff & Mackenzie [START_REF] Soukoreff | Theoretical upper and lower bounds on typing speed using a stylus and a soft keyboard[END_REF]. Sears et al. argue that using Hick's law implies that only the number of keys is important when determining which key to press. In contrast, they provide evidence that both the keyboard layout, e. g. QWERTY or Dvorak, and the number of letters represented by each key, e. g.three letters per key on a telephone keypad, must be considered.

Wobbrock & Myers [START_REF] Wobbrock | From Letters to Words: Efficient Stroke-based Word Completion for Trackball Text Entry[END_REF] introduce a stroke-based word completion technique for trackball text entry and include Equation 18 in their model. This term is added after the entry of every letter and represents the time it takes for a user to find their word among n choices, where n is the number of completions offered for the current prefix (0 n 4). The authors show that this new stroke-based word prediction and completion technique outperforms a major commercial on-screen keyboard. They do not, however, demonstrate nor analyze if and how reaction time plays a role.

Interface Design Guideline

In the design community, Hick's law is interpreted as a general design guideline, which we refer to as the "Hick-based design principle" in this chapter. In the book Universal Principles of Design [START_REF] Lidwell | Universal principles of design, revised and updated: 125 ways to enhance usability, influence perception, increase appeal, make better design decisions, and teach through design[END_REF], Lidwell et al. state that "Designers can improve the efficiency of design by understanding the implications of Hick's law" (p. 120). Similarly, in a Web entry titled "Hick's law: Making the choice easier for users"3 , Soegaard writes that "Understanding Hick's law means you can design so that more users will visit and stay on your website".

Wang [START_REF] Wang | A guide to assistive technology for teachers in special education[END_REF] states that "Essentially, Hick's law provides a general guideline for the design and use of hierarchical menu structures. This is consistent with the study [START_REF] Landauer | Selection from Alphabetic and Numeric Menu Trees Using a Touch Screen: Breadth, Depth, and Width[END_REF] showing that users do not consider each choice one by one. What they normally do is to subdivide the choices into categories, and choices in each category are further divided. The resulted structure will be a tree, which can help users to make a quicker decision."

Ali & Liem [START_REF] Ali | The use of formal aesthetic principles as a tool for design conceptualisation and detailing[END_REF] claim that "Within the context of design, Hick's law promotes the use of design methods to simplify decision-making in situations where designers are presented with multiple options. In practice, it has fundamentally proven to be effective in the design of menus, control display, way finding layout."

Hick's law is also invoked in guidelines for designing applications for mobile devices [START_REF] Nayebi | An expert-based framework for evaluating ios application usability[END_REF], visualizations [START_REF] Hall | Critical visualization: a case for rethinking how we visualize risk and security[END_REF] and spreadsheets [START_REF] Hock Chuan Chan | An alternative fit through problem representation in cognitive fit theory[END_REF]. It seems that Hick's law is a magical formula in the design community and is widely used to rationalize two principles: (a) Minimize the number of choices; and (b) Categorize choices, instead of overwhelm users with all the choices at once.

Summary: Inconsistencies

From the literature above, we can see several inconsistencies in the use of Hick's law.

First, we notice that the formulation used in HCI studies is different from the one introduced by Card et al. [START_REF] Newell | The psychology of human-computer interaction[END_REF], especially the question of n vs. n + 1. Nearly all authors use log n, with the notable exception of Cockburn et al. [START_REF] Cockburn | A Predictive Model of Menu Performance[END_REF], although in that case it is unclear how the stimulus information was computed. This raises a first question:

Which formula for Hick's Law?

Second, Hick's law is used to model expert users' decision time by Cockburn et al. [START_REF] Cockburn | A Predictive Model of Menu Performance[END_REF] and novice users' visual search time by Soukoreff & Mackenzie [START_REF] Soukoreff | Theoretical upper and lower bounds on typing speed using a stylus and a soft keyboard[END_REF]. Even though Sears et al. [START_REF] Sears | The role of visual search in the design of effective soft keyboards[END_REF] showed the incompatibility of the law with visual search, Wobbrock & Myers [START_REF] Wobbrock | From Letters to Words: Efficient Stroke-based Word Completion for Trackball Text Entry[END_REF] use it to model visual search time. In the design community, on the other hand, the law seems to work universally. This raises a second question: When does the law apply? Third, Landauer & Nachbar [START_REF] Landauer | Selection from Alphabetic and Numeric Menu Trees Using a Touch Screen: Breadth, Depth, and Width[END_REF] conclude, based on their empirical data, that broader, shallower menu trees yield faster search than narrower, deeper ones. This contradicts the common belief in the design community that a tree structure helps users make a quicker decision [START_REF] Wang | A guide to assistive technology for teachers in special education[END_REF]. This raises the third question: What does the law really say?

To answer the questions above, in the next section I review the choice-reaction paradigm in psychology.

choice-reaction time in psychology

While HCI researchers associate reaction time with Hick's law, there is a long tradition in psychology in studying choice-reaction paradigm. In this section, I review these studies in psychology and attempt to give a more precise definition of Hick's law.

Before Information Theory

Several studies have been conducted before Hick's experiment, which are briefly mentioned in Chapter 2 Section 2.1. The first results on reaction time (RT) are due to Helmholtz [START_REF] Helmholtz | Ueber die Fortpflanzungsgeschwindigkeit der Nervenreizung[END_REF], the famous physician & physicist of the nineteenth century. He determined that signals travel the nervous system at about 60 m/s. A comparison between typical reaction times observed in common tasks and the calculated propagation times revealed that the propagation time for signals could not account for the reaction time, implying that humans were not simply hard-wired to respond to certain stimuli but that time was required "in the brain for the processes of perceiving and willing". By the end of the nineteenth century and early twentieth century, three other important results were known:

• Donders [START_REF] Cornelis | Die schnelligkeit psychischer processe (On the speed of mental processes)[END_REF] introduced the three-class taxonomy of reaction time that is still in use today: simple RT (a-reaction time) is the time it takes to react, with a predetermined response, to the onset of a stimulus whose identity is known in advance but whose time of occurrence is uncertain; choice RT (b-reaction time) is the time it takes to react to the onset of one of several possible stimuli, following a given stimulus-response mapping rule;

and go-no-go RT (c-reaction time) is the time it takes to respond to a stimulus that may or may not occur at a predetermined point in time. Donders showed that simple RT was the shortest and choice RT the longest.

• Merkel [START_REF] Merkel | Die zeitlichen verhältnisse der willensthätigkeit (The Temporal Relations of the Actions of Will, or The Timing of Voluntary Action)[END_REF] performed an experiment using an identificationchoice reaction task, i. e. measured b-reaction time. It showed that it takes longer to respond to a stimulus when it belongs to a larger set of stimuli.

• Many psychologists have attributed the "reaction-time era" to such causes as the division of attention or a reduction in the effective intensity of the stimulus without providing a quantitative theory. Blank [START_REF] Blank | Brauchbarkeit optischer Reaktionsmessungen (Usability of optical reaction measurements)[END_REF] was the first to postulate a logarithmic relationship between reaction time and the number of alternatives but did not give further explanation.

The Information Analogy: Hick & Hyman

Hick's work was strongly inspired by Merkel's results. In fact one could say that Hick did nothing but replicate Merkel's experiment and used a logarithmic scale for the x-axis rather than Merkel's linear scale. This misses an important point: Hick's contribution is conceptual rather than experimental. Using the information-theoretical rationale that was popular at the time, Hick interpreted this logarithmic curve by considering the human as a channel of information transmission [START_REF] William | On the rate of gain of information[END_REF]. Accordingly, reaction time is seen as resulting from the uncertainty of the stimulus, which can only be processed at some maximum rate. The information rationale had an immediate effect: If the "information" -in layman's sense -mattered, then all the ways in which information could be varied mattered. This introduced new ways of testing the relationship between reaction time and the "information" provided by the stimulus.

Hyman [START_REF] Hyman | Stimulus information as a determinant of reaction time[END_REF] varied the entropy of the stimuli in 3 ways:

• By changing the total number n of stimuli (Hick [98], Merkel [START_REF] Merkel | Die zeitlichen verhältnisse der willensthätigkeit (The Temporal Relations of the Actions of Will, or The Timing of Voluntary Action)[END_REF]). In this case, uncertainty increases with the number of stimuli.

• By changing the probability that each stimulus is indeed activated. The more similar the probabilities, the higher the uncertainty. In the limit case, when all the stimuli are activated with equal probability, uncertainty reaches its maximum value of log n.

• By establishing "grammar rules", i. e. introducing conditional probabilities between successive stimuli. For example, if stimuli B is activated, then it is certain that stimuli D will be activated next.

Their respective experiments are detailed in Chapter 2 Section 2.1.

Choice Reaction Time: Results

After Hick's and Hyman's respective experiments, a number of studies measuring reaction time in a choice-reaction task were reported.

Here I summarize the main results.

Reaction Time: Context

Most choice reaction time studies were conducted with the goal of measuring b-reaction time on very simple tasks, such as responding to bulbs lighting up by pressing keys (Hick [START_REF] William | On the rate of gain of information[END_REF]) or through speech (Hyman [START_REF] Hyman | Stimulus information as a determinant of reaction time[END_REF]). It is not clear how well the logarithmic relationship between time and information holds for more complex tasks that potentially require a lot of decision making. One exception is given by Crossman [START_REF] Edward Rfw Crossman | The measurement of discriminability[END_REF], who investigated card sorting and found results consistent with the rest of the literature.

Measuring Information: Entropy or Mutual Information?

It has consistently been found that for a range between 1 and 3 to 4 bits, reaction time increases linearly with entropy, irrespective of which of the three variables described above is being manipulated. However, whenever the number of choices becomes larger, it seems that reaction time is consistently over-estimated. In fact, Fitts & Posner [START_REF] Paul | Human performance[END_REF] indicated that whatever the number of possible stimuli, reaction time will seldom exceed 1s. Seibel [START_REF] Seibel | Discrimination reaction time for a 1,023alternative task[END_REF] reported that there is almost no difference in reaction time between responses to 31 (5 bits) or 1023 (10 bits) stimuli. Fitts et al. [START_REF] Paul M Fitts | Cognitive aspects of information processing: II. Adjustments to stimulus redundancy[END_REF] showed that the response to very low probability alternatives is faster than predicted by the law.

On the other hand, Pollack [START_REF] Pollack | The intelligibility of excerpts from conversation[END_REF] found that the linear relationship extends to about 10 bits in a task where words had to be named. The actual range where the relationship holds is thus very dependent on the actual task.

Modulating the speed-accuracy characteristic to modify the values of mutual information leads to gross underestimates of reaction time, especially for very small values of mutual information I, i. e. in conditions where many mistakes are made. Fitts [START_REF] Paul | Cognitive aspects of information processing: III. Set for speed versus accuracy[END_REF] reported that beyond 0.6 bits of equivocation (H(X|Y), see Equation 2), the loss of information resulting from errors increases faster than the gain from increased response speed. We will therefore now consistently use the term stimulus uncertainty rather than the vague term of "information" to characterize the stimuli.

N or N+1?

Hick [START_REF] William | On the rate of gain of information[END_REF] found that if the number of possible signals is n and reaction time is plotted against log(n + 1), the observed reaction times for different numbers of signals lie on a straight line which also passes through the origin.

The reason why the fit is better for (n + 1) instead of n is that if the subject is uncertain about when a signal will appear, then when it does appear, he or she needs to not only decide which it is, but also decide that a signal has occurred at all. In fact, the +1 in Hick's formulation has not always been easy to understand and several other alternative equations have often been preferred.

Immediately after Hick, Crossman [START_REF] Erfw Crossman | Entropy and choice time: The effect of frequency unbalance on choice-response[END_REF] conducted a card-sorting experiment: The subjects held a well-shuffled pack, turned up the cards one by one and sorted them into various classes. The results were plotted against log n as the pack was always available, hence there was no uncertainty about when a fresh signal would appear. Hyman [START_REF] Hyman | Stimulus information as a determinant of reaction time[END_REF] extended Hick's concept by manipulating uncertainty with unequal probabilities: -n i=1 p i log 2 p i . Even when he replicated Hick's experiment with equal probability, he proposed log n, not log(n + 1). While Suci et al. [START_REF] George | Reaction time as a function of stimulus information and age[END_REF] fitted the data equally well with n and n + 1, other researchers such as Griew [START_REF] Griew | Information gain in tasks involving different stimulus-response relationships[END_REF] and Brown [START_REF] Id Brown | Many messages from few sources[END_REF] found that n + 1 fitted data slightly better. Crossman [START_REF] Edward Rfw Crossman | The measurement of discriminability[END_REF] also plotted data against log(n + 0.45).

As Welford [START_REF] Traviss | Fundamentals of skill[END_REF] pointed out, the proposed mathematical formulations provide merely a summary statement of a complex process of observation, identification, choice and reaction which highly depends on the specific task environment. Hence one possible formula to account for this complexity is log(n + n 0 ) where n 0 describes the effect of temporal uncertainty expressed in terms of n. n 0 varies from zero if the subject is able to estimate exactly when the next signal will appear, to more than 1 if she does not have any idea of when the stimulus will show up. When the time at which the stimulus appears is reasonable but not completely predictable, n 0 ∈ [0, 1].

Effect of Stimulus-Response Compatibility

S-R (Stimulus-Response) compatibility was introduced in psychology to characterize the fact that it is easier to respond to a stimulus using certain responses than others. If the stimulus is coded in terms of digits appearing on a screen, it is for example much easier for someone to call the corresponding digit out than, say, to call a letter or another digit out. It has repeatedly been found that the better the SR compatibility, the shallower the slope relating reaction time to stimulus uncertainty.

In fact, whereas Hick's light and key experiment reports rates of about 200 ms/bit, there are many cases where the slope can approach 0 ms/bit (Fig. 15), such as Leonard's experiment [START_REF] Alfred | Tactual choice reactions: I[END_REF] where the subject rested his fingers upon vibrators and touched the vibrator that was activated (Fig. 15 Curve J), or Mowbray's experiment [START_REF] Mowbray | Choice reaction times for skilled responses[END_REF] where subjects gave a voice reaction to Arabic numerals (Fig. 15 Curve G). Indeed, as Fitts & Posner pointed out [START_REF] Paul | Human performance[END_REF], anything that decreases the spatial or energy correspondence between input and output, therefore reducing compatibility, increases the slope. This principle can probably be beneficial to interface design.

Effect of Learning

The effect of learning is very similar to that of S-R compatibility. When participants are heavily trained, the effects of the uncertainty of the stimulus and even of the S-R compatibility can be reduced so that reaction time is almost constant, regardless of the number of items. Mowbray's experiment [START_REF] Mowbray | On the reduction of choice reaction times with practice[END_REF] showed that reaction time for choices among up to 10 possibilities could be reduced to that of a two choices alternative when a subject practiced a key-press task for a period of 6 months. Although this is somewhat questioned by Welford [START_REF] Traviss | Fundamentals of skill[END_REF], it is clear that practice will significantly reduce the slope: Knight & Dagnall [START_REF] Knight | Precision in movements[END_REF] reported slopes dropping from 73 ms/bit to 23 ms/bit after two months of practice.

Clarifying Hick's law

It is clear at this point that Hick's law is much more complicated than Card et al.'s description [START_REF] Newell | The psychology of human-computer interaction[END_REF] would suggest. Indeed, learning, S-R compatibility and stimulus uncertainty all affect reaction time. Furthermore, these effects are dependent on each other. For example, if one wishes to modify uncertainty by changing the probabilities of activation of each stimulus, then the subject has to go through an extensive learning phase, as discussed by Hyman [START_REF] Hyman | Stimulus information as a determinant of reaction time[END_REF]. Yet, she will inevitably improve her skill in the matter of the experiment, leading to a reduction of the slope.

Similarly, good S-R compatibility is usually desirable, otherwise the experiment will appear poorly designed. However, this makes the effect of Hick's law much harder to grasp, as the influence of stimulus uncertainty is then highly reduced.

Finally, learning does not affect all experiments in the same way. The highest rates are usually found with experiments using words. This is not necessarily because the S-R compatibility is particularly good, but rather because reading and remembering words is a highly over-learned task, which we train daily. What can we say about Hick's light-key association task? Is this a completely new task, or are we somewhat familiar with it?

We therefore propose the following, a clarification of Hick's law:

The choice reaction time for users performing a simple task grows linearly with the stimulus uncertainty, measured by entropy, in the range of 1 to 4 bits. The better the S-R compatibility and the better the training, the shallower the slope. With appropriate learning, the effects of S-R compatibility and stimulus uncertainty can be reduced to almost zero.

the choice-reaction paradigm and hci

In this section, I revisit the HCI applications of Section 4.1, comparing them with the choice-reaction paradigm in psychology and outlining the discrepancies in the use of the law. Seow [START_REF] Steven | Information theoretic models of HCI: a comparison of the Hick-Hyman law and Fitts' law[END_REF] offered three plausible reasons for the failure of Hick's law in HCI: [START_REF]ACM SIGCHI Curricula for Human-Computer Interaction[END_REF] The complexity of computing information measures; (2) The complexity of stimuli including font sizes, colors, etc. and (3) The unpredictability of stimuli changes over time with practice. Therefore Hick's law appears to be optimal only in predicting novice performance. Here we offer two additional explanations for why it is not trivial to use Hick's law in HCI studies.

Decomposition of Time Measures

Table 1 summarizes and demonstrates the differences between how Hick and Hyman introduced the paradigm and how the law has been used in HCI studies. All the studies assume a stimulus-response (S-R) paradigm. From a measurement perspective we typically face three time marks: Stimulus-onset time T1, Response-onset time T2, and Response-termination time T3, allowing the calculation of three relevant time durations: movement time MT = T3 -T2, task completion time TCT = T3 -T1 and a third time, say xT = T2 -T1 (Fig. 16 (a)). xT can stand for RT as in "reaction time" (e. g. Hick [START_REF] William | On the rate of gain of information[END_REF], Hyman [START_REF] Hyman | Stimulus information as a determinant of reaction time[END_REF]), or in more complex tasks, can include, e. g. visual search [START_REF] Landauer | Selection from Alphabetic and Numeric Menu Trees Using a Touch Screen: Breadth, Depth, and Width[END_REF][START_REF] Soukoreff | Theoretical upper and lower bounds on typing speed using a stylus and a soft keyboard[END_REF], decision [START_REF] Cockburn | A Predictive Model of Menu Performance[END_REF]. Importantly, xT and movement time MT are, by definition, non-overlapping intervals.

From the previous section we know that Hick along with other psychologists measured the choice reaction time (b-RT) in response to a particular stimulus: the time it takes to press the key, hence, reaction time dominates task completion time (Fig. 16 (b)). In contrast, all the studies in Table 1 fall into the paradigm of Fig. 16 (c) where movement time MT contributes a relatively large portion of task completion time TCT. Despite the fact that xT involves different mental processes in these studies (e. g. S identification, visual search, memory search, decision to respond), the authors of these studies attributed these phenomena to Hick's law.

Hick [START_REF] William | On the rate of gain of information[END_REF] Hyman [START_REF] Hyman | Stimulus information as a determinant of reaction time[END_REF] Landauer & Nachbar [ Indeed, as shown in the previous section, later studies confirmed that an extremely well-trained participant can react in almost constant time despite stimulus uncertainty [START_REF] Mowbray | On the reduction of choice reaction times with practice[END_REF]. There are also tasks that we are naturally experts at, such as resting fingers on vibrators and pressing the corresponding key when it vibrates [START_REF] Alfred | Tactual choice reactions: I[END_REF], or giving a voice reaction to Arabic numerals [START_REF] Mowbray | Choice reaction times for skilled responses[END_REF].

In HCI studies, it is difficult to judge novice vs. expert users in the stimulus-response context. We are daily computer users, and we are all semi-experts in responding to a visual stimulus with a mouse pointer. Unless the interaction technique uses a device that participants have never seen before or a mapping that is completely novel, we should rethink what is their expertise in this choice-reaction paradigm.

Effect Size of Hick's Law

Then what is the effect size of choice reaction time in HCI studies? As stated in Section 4.2, the slope in Hick's law depends on learning and S-R compatibility. Two questions then naturally emerge:

• How familiar are the participants in HCI experiments with the tasks we have them perform?

• What is the S-R compatibility of the tasks we usually ask participants to perform?

Arguably, a successful interaction should be easily learned by participants, or, even better, exploit already over-learned tasks, and should have a good S-R compatibility. Therefore, it can be expected that for a successful technique, the slope of Hick's law is already quite shallow.

To illustrate this point, we reanalyzed data from Roy et al. [START_REF] Roy | Glass+ skin: an empirical evaluation of the added value of finger identification to basic single-touch interaction on touch screens[END_REF] and Liu et al. [START_REF] Liu | BIGnav: Bayesian Information Gain for Guiding Multiscale Navigation[END_REF] where a simple command selection task was carried out. In Roy et al. [START_REF] Roy | Glass+ skin: an empirical evaluation of the added value of finger identification to basic single-touch interaction on touch screens[END_REF], participants needed to select a highlighted command by touching the screen of a tablet with a predetermined finger in the Glass condition vs. one of several fingers in the Glass+Skin condition. In Liu et al. [START_REF] Liu | BIGnav: Bayesian Information Gain for Guiding Multiscale Navigation[END_REF], participants were instructed to move the mouse pointer to hit a highlighted stimulus among several commands. The finger or the pointer was rested on a designated area at the beginning of each trial. In both cases, reaction time was measured between the start of the trial and the first move of the finger or pointer. Fig. 17 shows the plot of reaction time as a function of stimulus uncertainty.

We ran a repeated-measures full factorial ANOVA for 3 conditions on these reaction times (Table 5). In conditions Glass+Skin [START_REF] Roy | Glass+ skin: an empirical evaluation of the added value of finger identification to basic single-touch interaction on touch screens[END_REF] and command selection [START_REF] Liu | BIGnav: Bayesian Information Gain for Guiding Multiscale Navigation[END_REF], the effect of stimulus uncertainty on reaction time is not significant.

implications for hci

In this section, based on a mathematical analysis, I first show that the Hick-based design principle praised in the design community is unduly justified by Hick's law. Then, I build on the previous discussions and suggest that, in spite of the complexity of the psychological process behind xT (Fig. 16), we can advocate a simple design strategy, on the premise that xT is either convex or concave.

The Concavity of the Logarithm Contradicts the Hick-based Design Principle

Hick's law is usually used as an argument by the design community to justify the need to display as few items as possible (Section 4.2).

Consider a scenario where a designer has to display N items, to see how the Hick-based design principle holds.

car website scenario We consider as a practical example a car website which has N = 512 cars to display. We list three display strategies and evaluate Hick's law in each case:

• Display all the cars on the same page. Hick's law states that reaction time RT is given by

RT = a + b log 2 (512) = a + 9 × b. (19)
• Split the 512 cars into 4 pages of 128 uncategorized cars. We apply Hick's law to each page and sum the reaction times. If we consider that the user will go through all the pages, total reaction RT time is given by

RT = 4 × (a + b log 2 (128)) = 4a + 28 × b. (20)
Over time, there is one chance out of four that the item she is looking for is in each page, so that the average RT is given by

RT = 1/4 4 i=1 a i + b i log 2 (128) = 10/4 a + 70/4 b. (21)
• Split the 512 cars in 4 categories of 128 cars. The participant selects one item among 4 to select a category, and then selects one item among 128. This is the so called tree strategy, or divide and conquer strategy. The total reaction time RT is given by

RT = a + b log 2 (4) + a + b log 2 (128) = 2a + 9 × b. ( 22
)
For this example, the optimal strategy according to Hick's law consists of displaying all the cars at once on the same page.

In fact the following general result holds. When there are N items to be displayed that can be separated into k subgroups, applying Hick's law leads to the following:

• It is never advantageous to split elements into uncategorized subgroups of equal sizes. Indeed, for k ∈ N; 2 k N, we have that:

N/k k N; if N k k/(k-1) . ( 23
)
Then, taking the logarithms on both sides, we get:

k log(N/k) log N, (24)
which generalizes4 Equation ( 20).

• It is not advantageous, or at best useless, to split elements into categorized subgroups of equal size. Indeed, since

N = k × N k , log N = log k + log N/k, so that RT = a + b log(k) + a + b log(N/k) (25) = a + (a + b log N). (26)
This generalizes Equation [START_REF] Robert W Brainard | Some variables influencing the rate of gain of information[END_REF]. Assuming there are m nested categories, we must ultimately pay the price of an additional (m -1)a seconds on RT if we use a tree strategy.

The conclusion of this small example is that, contrary to common sense, Hick's law actually suggests displaying as many items as possible on the car rental site. We do not claim that the Hick-based design principle is flawed, but rather that it cannot be justified by Hick's law. There are many different phenomena taking place when a user is investigating the car rental web page, which are far more complex than simple stimulus response and therefore Hick's model is far too simple.

In serial visual search, selection time increases linearly with size [START_REF] Traviss | Fundamentals of skill[END_REF], i. e. RT = a + b N. If one were to choose a joint pair among a set of size N, we would expect a quadratic increase in RT as there are N(N -1)/2 possible pairs. This suggests a variety of non logarithmic models.

xT Design Principle: A Matter of Convexity

What matters for design is whether the function relating xT and N is convex or concave. As in the previous example, we consider two different situations: one in which items can be categorized, the other in which they cannot. This leads to two different convexity results. Let f be the function that relates xT to

N xT = f(N), (27)
case 1: items cannot be categorized If the items are displayed in two sets of sizes x and y (x + y = N), then xT = f(x) + f(y), whereas if the items are displayed all at once, xT = f(x + y). Therefore, determining whether or not we should split the items boils down to whether f(x + y) is greater or lower than f(x) + f(y)

f(x + y) f(x) + f(y), (28)
If Equation ( 28) holds, then f is said to be superadditive; else f is subadditive. It can be shown [START_REF] Andrew M Bruckner | Some function classes related to the class of convex functions[END_REF] that if f(0) = 0:

f convex implies f superadditive; ( 29
)
f concave implies f subadditive. ( 30
)
The important information is thus whether f is a convex or concave function. This leads to our first xT design principle:

If items are not categorizable and f is convex, e. g. quadratic, then it is useful to group the items, even arbitrarily. If f is concave, e. g. logarithmic , then it is better to display all items at once5 . case 2: items can be categorized For this case, we assume for simplicity that the items are categorized in x categories with y items each. Therefore N = xy. From the example of the previous subsection, it is clear that the relevant question is whether f(x) + f(y) is greater or not than f(xy). It is easily shown through the previous result that

f(exp (.)) convex implies f(x) + f(y) f(xy); (31)
f(exp (.)) concave implies f(x) + f(y) f(xy). (32)
In Hick's paradigm reaction time grows logarithmically, in which case f(exp(x)) is linear; this is the limit case where f(x) + f(y) = f(xy), i. e. the two strategies are equivalent. As all functions relating selection time to the number of items realistically grow faster than the logarithm (any practical HCI setup is likely more time consuming than Hick's task), we can state the second xT design principle as follows:

Looking forward, creating an empirical taxonomy for reaction times analogous to the more theoretical computational complexity might be useful for HCI researchers who strive to model human behavior. Since sub-additivity is the main issue, an index that quantifies this property would probably be useful. S = f(x)+f(y) f(x+y) is a natural candidate. More empirical and theoretical work should determine whether S is indeed useful.

O T H E R I N F O R M AT I O N T H E O R Y AT T E M P T S I N H C I

Apart from Fitts' law and Hick's law, information theory has found few other uses in HCI. This chapter examines several attempts: statistical language modeling for text entry, human information capacity and some applications inspired by control theory [START_REF] Richard | Control theory for humans: Quantitative approaches to modeling performance[END_REF]. My goal is to explore how information theory has been used in these domains and what can be done for future work.

statistical language processing for text entry

Statistical language processing models text entry as communication over a noisy channel and calculates the bitrate of a text entry method. It is based on Shannon's estimation of entropy [START_REF] Shannon | Prediction and entropy of printed English[END_REF] and exploits the inherent redundancies for language modeling and prediction. Intelligent text entry systems that use this approach result in a lower error rate and potentially a higher entry rate [START_REF] Per | Five challenges for intelligent text entry methods[END_REF].

The basic idea is in line with fundamental information-theoretic concepts. Assume a source alphabet Ω follows a probability distribution. The entropy of such alphabet is then H(Ω) (Equation 1) and the perplexity. PP(Ω) = 2 H(Ω) , measures how well a probability model is at prediction1 . The lower the perplexity, the easier the prediction. If the random variable I is a distribution over the set of words the user is intending to write and the random variable O is a distribution over the set of words the user is actually writing, then the rate R (in bits per time unit) is:

R = I(I; O) t . ( 33
)
where I(I; O) is the mutual information (Equation 2) and and t is the average time it takes to write a word in O. If the probability of error is zero, that is, all words in I can always be inferred from O, then R = H(I) t (Equation 6).

A typical use example of these measures is described as follows:

Intended sentence: I am fine if you ask. Transcribed sentence: I an finw ← e if you ask.

If we assume that a rather expert user 3 Keystrokes per character (KSPC) corresponds to corrected error rate while Levenshtein string distance to not-corrected error rate. We can see that even with such a complicated error measurement approach, the 4 types of errors are still not fully taken into account. Indeed, measuring errors has proven to be difficult in text entry. But one can hardly make meaningful observations about speed in the absence of accuracy. As a result, in controlled experiment settings, participants were often instructed to consciously limit errors within a reasonable range, such as 4% (e. g. [START_REF] Maria Feit | How We Type: Movement Strategies and Performance in Everyday Typing[END_REF]), so that only the speed dimension is of concern.

It is surprising that so few researchers have taken advantage of information theory to measure performance in text entry when it has already been used for statistical language modeling. The notion of equivocation H(X|Y) (Equation 2and 3) naturally provides measures for errors and how one can recover the source messages from the received ones. I will demonstrate in Part iii that we can use informationtheoretic measures for evaluating text entry performance.

human information capacity

The notion of human information capacity, or rather the notion of throughput, has been mostly used in aimed movement, for instance, selecting targets with the mouse yields throughput of 3.7-4.9 bits per second [START_REF] Soukoreff | Towards a standard for pointing device evaluation, perspectives on 27 years of Fitts' law research in HCI[END_REF]. It has also recently been applied to full-body movements [START_REF] Oulasvirta | Information Capacity of Full-body Movements[END_REF] 4 . This work inspired Fekete et al. [START_REF] Fekete | Motion-pointing: Target Selection Using Elliptical Motions[END_REF] to explore motion correlation as a selection technique in conventional graphical user interfaces. Rather than using pseudo-random movement, their idea was to associate objects with oscillatory movement, drawing on user's natural ability for harmonic motion with their hands. In their design of the motion-pointing technique, the graphical objects of interest retain their static presence in the interface but are augmented with a moving dot describing a small elliptical movement. These works represent milestones in establishing the motion correlation principle [START_REF] Velloso | Motion Correlation: Selecting Objects by Matching Their Movement[END_REF].

In summary, these studies demonstrate the potential of using information theory and information-theoretic notions to study the userto-computer communication process and to design interaction with improved communication rate.

S U M M A R Y

I have presented various research endeavors applying information theory in psychology and in human-computer interaction. Some involve the communication channel with human users while others do not; some are more intuitive than others; some are more successful than others. I particularly want to summarize and highlight the following four aspects that motivate the rest of the thesis:

• Chapter 2: Indeed, there are a number of difficulties in applying information theory, notably the fact that the notion of information in information-theoretic terms has absolutely no semantic meaning; it is entirely described by a probability distribution. Measuring information content (entropy) in printed English text or multimedia content is absolute as long as the probability distribution of words and multimedia content (e. g. video frames) is considered objectively and as a matter of fact. On the other hand, if we were to derive information content from the stimuli based on human users' reaction, as in the stimulusresponse paradigm, we need to make sure that the experimental setting corresponds to the information transmission process, rather than the information processing phase.

• Chapter 3 and 4: We have seen that the understanding and applications of the two main laws in HCI -Fitts' law and Hick's law -are problematic and I have provided an in-depth discussion of Hick's law in Chapter 4. It is necessary, therefore, to clarify what they are, how they should be used and when they do not apply. I believe that the HCI community at large can benefit from theoretically justified methods.

• Chapter 5:

We have also seen the potential of investigating the information transmission process from the user to the computer using the tools of information theory. Particularly, how to quantify the information is an interesting question. In Part ii, I will introduce a Bayesian Information Gain framework that is based on Bayesian Experimental Design using the criterion of mutual information from information theory. This approach quantifies the information sent by the user to the computer to express her intention. By having the computer demanding more information at each time, I will show that the interaction & communication efficiency can be improved.

• Chapter 5: Since information theory has already been used in measuring entropy of English and measuring human performance, can we further extend it to describe interaction tasks at large? This generic communication scheme enables us to examine the communication process between the user and the computer with theoretically valid tools and provides several useful measures that have not been taken advantage of. In Part iii, I will introduce these information-theoretic measures for characterizing interaction tasks and demonstrate that it offers a richer picture of a given interaction scenario in comparison to the existing measurements.

We cannot foresee how information theory is going to affect and inspire future interaction design, nor can we guess which theory will be the next trend. Information theory was adopted and then dropped by psychologists, yet it still has much potential for understanding and designing the human-computer communication process. I hope this part has fulfilled its purpose: understanding the past as well as the present, and taking a glimpse into the future.

-------"The farther backward you can look, the farther forward you are likely to see." -Winston S. Churchill

Part II A B AY E S I A N I N F O R M AT I O N G A I N ( B I G ) F R A M E W O R K F O R Q U A N T I F Y I N G I N F O R M AT I O N
The goal of this part is to introduce Bayesian Information Gain (BIG), an information-theoretic framework based on Bayesian Experimental Design to quantify the information sent by users to computers in the interaction loop. BIG (a) allows the measurement of information in bits and (b) improves the efficiency of interaction & communication by maximizing or leveraging the expected information gain from the user's subsequent input.

I first introduce the BIG framework and then demonstrate two use cases: BIGnav, for multiscale navigation and BIG-File, for hierarchical file retrieval, both of which show a new way of interacting with improved communication efficiency, suggesting other possible "BIG" opportunities.

B AY E S I A

N I N F O R M AT I O N G A I N F R A M E W O R K 7.

motivation

In this information-abundant world, a large amount of information is exchanged between users and computers: we obtain information from the computer to increase our knowledge and to complete tasks, and we send information to the computer to express our ideas and intentions. Several studies have investigated the information that users obtain from computers. For instance, Pirolli and Card [START_REF] Pirolli | Information foraging[END_REF] have introduced the concept of information foraging, describing the phenomenon that people adapt their strategies to increase information gain in an online information seeking task.

However, there is little understanding of the information sent by the user to the computer. We are familiar with the notion that we give inputs (or commands) to the computer, not information. Yet these inputs reflect the user's intentions, letting the computer know what is the user's goal, therefore, they represent information. This leads to a number of questions: how much information is there in these input commands? Can we quantify this information? If we can, what can we do with it and what does it imply?

In this part, we introduce a Bayesian Information Gain framework (BIG), based on Bayesian Experimental Design [START_REF] Dennis | On a measure of the information provided by an experiment[END_REF]. It uses the criterion of information gain, also known as mutual information in information theory [START_REF] Shannon | A mathematical theory of communication[END_REF], to quantify the information sent by the user to the computer in the interaction loop. Information is defined in terms of the computer's knowledge about what the user wants. At the beginning of the interaction, the user has certain goals, e. g. looking for a particular item on a website or typing a particular word on the keyboard. The computer has some uncertainty about the user's goal. This uncertainty is represented by the computer's prior knowledge, expressed in a probabilistic model. When taking input from the user, the computer updates its knowledge about what the user is looking for. Therefore, the information carried by the user input is the knowledge gained by the computer to know the user's goal.

One can simply use BIG to measure the information sent by the user to the computer. Furthermore, by maximizing or leveraging the expected information gain from the user's subsequent input through manipulation of the feedback, the computer can increase the information gain from the user, improving interaction efficiency. 1. Θ represents the possible intended targets in the user's mind.

p(Θ = θ

) for all values of θ is the prior probability distribution of target, which expresses the computer's prior knowledge about the random variable Θ. p(Θ = θ) can be uniform if no data about the user's interests is available, or can be based on external data sources or interaction history.

3. X represents any possible feedback provided by the computer and X = x is a particular feedback sent to the user.

4. Y represents any particular command y issued by the user.

p(Y

= y|Θ = θ, X = x)
is the probability of the user giving an input command Y = y when she wants Θ = θ and sees X = x. This can be modeled from the interaction history, or by user calibration, and can be user-independent.

6. p(Θ|X = x, Y = y) is the computer's updated knowledge about the user's goal after showing the user X = x and receiving the input Y = y from the user. It is calculated through Bayes' theorem:

p(Θ = θ | X = x, Y = y) = p(Y = y | Θ = θ, X = x)p(Θ = θ) p(Y = y|X = x) . ( 34
)
where

p(Y = y | X = x) = θ ′ p(Y = y | Θ = θ ′ , X = x)p(Θ = θ ′ ).
I(Θ; Y|X = x) = H(Θ) -H(Θ|X = x, Y). (35)
This can also be interpreted as the expected information gain, which is always positive. To calculate this, we use Bayes' theorem for entropy to convert Equation 35 to:

I(Θ; Y|X = x) = H(Y|X = x) -H(Y|Θ, X = x). ( 36
)
where the first term is given by:

y p(Y = y|X = x) log 2 p(Y = y|X = x).
and the second one by:

y,θ p(Θ = θ)p(Y = y|Θ = θ, X = x) log 2 p(Y = y|Θ = θ, X = x).
8. IG(Θ|X = x, Y = y) is the difference between the computer's previous knowledge H(Θ) and current knowledge H(Θ|X = x, Y = y) about the user's goal, representing the actual information carried by the user input:

IG(Θ|X = x, Y = y) = H(Θ) -H(Θ|X = x, Y = y). (37)
Information gain might be negative if the user, e. g. makes an error, but is positive on average2 . One can always calculate the actual information gain, or the information carried by the user input informing the computer what she wants with Equation 37-"Running a normal experiment". By manipulating the feedback with Equation 35, e. g. finding the X = x that maximizes or leverages the expected information gain, the system "runs a better experiment" on the user in order to gain more information about the user's goal, i. e. the intended target. The computer then plays a more active role and therefore increases interaction & communication efficiency.

In the next 4 chapters, I illustrate two applications of this BIG approach: maximizing the expected information gain in multiscale navigation (Chapter 9) and leveraging the expected information gain in hierarchical file retrieval (Chapter 11). In both cases, BIG is used in a different manner regarding the types of intended target Θ, system feedback X and user input Y and receives different subjective experience by the participants in the respective controlled experiments. Chapter 8 and Chapter 10 provide the context of multiscale navigation and hierarchical file retrieval respectively. In Chapter 12, I discuss how BIG is related to other conceptual frameworks, and outline opportunities for future work.

BIGnav guides navigation through 3 steps:

(1) Interpreting user input: Given the view x shown to the user and the user's intended target θ, p(Y = y|Θ = θ, X = x) is the probability that the user provides an input command Y = y given θ and x. This probability distribution is the system's interpretation of the user's intention when giving this command. For instance, if city A is to the left of the user, what is the probability of the user giving the left command when knowing that city A is located to her left, provided she can only go left or right? p(go left | city A is the intended target, city A is located to the left of the current view) = 1 if the user is completely confident about what she is doing. But maybe the user is not accurate all the time. Say she is only correct 95% of time, then we need to consider that she makes errors. For instance, p(go left | city A is the intended target, city A is located to the left of the current view) = 0.95 and p(go right | city A is the intended target, city A is located to the left of the current view) = 0.05. p(Y|Θ = θ, X = x) is a priori knowledge that must be given to the system. In the implementation section, we describe how we define it in 1D and 2D situations respectively.

(2) Updating system's knowledge: Given the view x shown to the user and the user reaction y to that view, the system can update its estimate p(Θ|X = x, Y = y) of the user's interest with Equation 34. If the system has no prior knowledge about the user's intended target, e. g. at the beginning, each θ has the same probability of being the target and p(Θ) is uniform. As the user issues commands, the system gains knowledge about the likelihood that each point of interest be the target, reflected by the changes to the probability distribution. This is done, for each point of interest, by taking its previous probability, multiplying by the above user input function p(Y = y|Θ = θ, X = x), and normalizing it so that the sum of the new probabilities over all the points of interest equals one.

(3) Navigating to a new view: With the new probability distribution after receiving user input, BIGnav then goes over each view x ∈ X, calculates its expected information gain with Equation 36 and picks the view for which it is maximal. To maximize Equation 36, BIGnav looks for a trade-off between two entropies. To maximize the first term, the view should be such that all user commands given that view are equally probable (for the system). To minimize the second term, the view should provide the user with meaningful information about the points of interest. Maximizing a difference does not necessarily mean to maximize the first term and minimize the second, so the maximum information gain is a trade-off between these two goals. For example, showing only ocean will increase the first term but will also increase the second term. After locating the view with maximal information gain, BIGnav navigates there and waits for the user's next input. In Fig. 33, the cities are represented by square boxes and colored in shades of red indicating the degrees to which the system believes the city is the target, i. e. city i is darker than j if p(Θ = i) > p(Θ = j). City 8 has a T indicating that it is the target. The yellow rectangle is the view that the system shows to the user. After seeing the view, the user provides an input command y to the system.

p(Y = + | Θ = θ, X = [a, b]) =           
We can now show BIGnav in action.

Step 1 (Fig. 33 (a)): Since the initial distribution is uniform, the system's uncertainty about the user's target is H 1 = H(Θ 1 ) = log 2 50 = 5.64 bits.

The system then goes over every image [a, b], finds that [START_REF] Bertelson | Sequential redundancy and speed in a serial two-choice responding task[END_REF][START_REF] Thomas | Elements of information theory[END_REF] maximizes the expected information gain and displays the corresponding initial view to the user. In this case the expected information gain from the user's next action is IG(Θ 1 | X = [START_REF] Bertelson | Sequential redundancy and speed in a serial two-choice responding task[END_REF][START_REF] Thomas | Elements of information theory[END_REF], Y) = 1.08 bits.

The user inputs ← after seeing [START_REF] Bertelson | Sequential redundancy and speed in a serial two-choice responding task[END_REF][START_REF] Thomas | Elements of information theory[END_REF]. The system then updates its knowledge with Equation 34 and ends up with a new distribution Θ 2 given by p(Θ 2 ) = p(Θ 1 | X = [START_REF] Bertelson | Sequential redundancy and speed in a serial two-choice responding task[END_REF][START_REF] Thomas | Elements of information theory[END_REF], Y =←). Using Bayes' theorem we have:

p(Θ 2 = i) = 0.05 i < 18 0.002 i 18.
The updated uncertainty is H 2 = H(Θ 2 ) = 4.65 bits, resulting in an actual information gain H 1 -H 2 = 0.99 bits, very close to the expected information gain of 1.08 bits.

Step 2 (Fig. 33 (b)): The system now searches for the best view using the new distribution p(Θ 2 ), finds that it is [START_REF] Bailly | Model of Visual Search and Selection Time in Linear Menus[END_REF][START_REF] Bakaev | Fitts' law for older adults: considering a factor of age[END_REF] with an expected information gain of IG(Θ 2 | X = [9, 10], Y) = 1.24 bits and displays it to the user. The user then inputs ← after seeing [START_REF] Bailly | Model of Visual Search and Selection Time in Linear Menus[END_REF][START_REF] Bakaev | Fitts' law for older adults: considering a factor of age[END_REF]. The system then updates Θ 2 to Θ 3 as follows: The entropy of Θ 3 is H 3 = 3.36 bits, so the actual information gain for this step is H 2 -H 3 = 1.29 bits, higher than the expected information gain of 1.24 bits.

p(Θ 3 = i) =           
Step 3 (Fig. 33 (c)): With the same process, the best view is now [START_REF] Je Allen | Mixed-initiative interaction[END_REF][START_REF] Appert | OrthoZoom Scroller: 1D Multi-scale Navigation[END_REF] with an expected information gain of IG(Θ 3 | X = [START_REF] Je Allen | Mixed-initiative interaction[END_REF][START_REF] Appert | OrthoZoom Scroller: 1D Multi-scale Navigation[END_REF], Y) = 1.58 bits. The user inputs →, leading to the updated distribution: The entropy of Θ 4 is H 4 = 2.70 bits, so the actual information gain is H 3 -H 4 = 0.66 bits, compared to the expected information gain of 1.58 bits.

p(Θ 4 = i) =                       
Step 4 (Fig. 33 (d)): The best view is now [START_REF] Attneave | Applications of information theory to psychology: A summary of basic concepts, methods, and results[END_REF][START_REF] Bailly | Visual Menu Techniques[END_REF] with an expected information gain of IG(Θ 4 | X = [7, 8], Y) = 1.84 bits. The user sees that the target city is in the view and clicks on it. The updated distribution is updated to:

p(Θ 5 = i) = 1 i = 8 0 otherwise.
The entropy of Θ 5 is H 5 = 0 bits since there is no more uncertainty about the target. The actual information gain is H 4 -H 5 = 2.7 bits, while the expected gain was 1.84 bits.

In this way, the user finds her target city in only 4 steps. At step 1, BIGnav divides the map in 3 so that the three commands (left, right and zoom in) have equal probability. It does not consider a click as the view is still far from being fully zoomed-in to select the target. At step 2, one would expect it to divide the left third of the map in 3 again so that the view would be about 5 boxes wide. However, since it is close to the maximum scale, and it knows that the user never misses her target when it is in the view and is clickable, showing a 2-box zoomed-in view will give BIGnav extra information: if this is the target, the user will click on it; if it is not and the user moves away, the probabilities of these two boxes become 0. Step 3 and step 4 work similarly.

We ran 200 simulations with 50 cities and a uniform initial distribution and found that it required 3.3 steps on average.

P(Y = y|Θ = θ, X = x).
We now describe our implementation of the navigation steps.

(1) Interpreting user input: To interpret user input, we need to define p(Y = y | Θ = θ, X = x), e. g. the probability of each command given a target and a view, e. g. p(pan East | target (5, 7), view (4, 4, 2)). If the user were perfectly reliable, we could assign a probability of 1 to the correct command for each target θ and each view x, and 0 to the others. But we know that users make errors. To model the error rate, we collected data during a calibration session. The goal was to determine how confident users were when issuing commands. The task was to indicate in which direction the target was in a set of views. A set of concentric circles, identical to those used in the experiment below, showed the direction of the target when it was not within the view (Fig. 35 (a)).

We tested all ten input commands Y (8 pan operations, zoom in and click on the target) with 5 repetitions each, resulting in 50 trials per participant (N = 16). The results (Table 4) show that 90% of panning commands are correct and 4% are in one of the adjacent directions (Fig. 34). For zooming commands, 95% of the commands are correct while for clicking on the target, 100% of the commands are correct.

(2) Updating system's knowledge: We use Equation 34 to update the probabilities p i of each point of interest being the target given the current view x: For all points of interest θ i , the new p ′ i is the previous p i multiplied by the user expected behavior p(Y = y | Θ = θ i , X = x) divided by the normalization over all points of interest.

(3) Navigating to a new view with maximum expected information gain: For each view x and each user input y, the expected information gain is the difference between two uncertainties: Uncertainty before user input y minus the sum of p i × log 2 p i over all points of interest Uncertainty after user input y minus the sum of p ′ i × log 2 p ′ i over all points of interest Participants were instructed to navigate to the target as fast as they could but were not informed of the condition they used.

Apparatus

The experiment was conducted on a MacBook Air with a 1.4 GHz processor and 4 GB RAM. The software was implemented in Java with the ZVTM toolkit [START_REF] Pietriga | A toolkit for addressing hci issues in visual language environments[END_REF]. The window was 800 × 600 pixels, centered on a 13-inch screen set to 1440 × 900 resolution. A standard mouse was used with the same sensitivity for all participants.

Procedure

We use a full-factorial within-participants design with a main factor: navigation technique (Tech); and two secondary factors: distribution of targets (DISTR), index of difficulty (ID).

Navigation Technique (Tech)

We compare BIGnav with standard pan-and-zoom:

• BIGnav: our guided navigation technique. The ten user commands (eight pan, zoom in, select target) and error rates are as described in the previous section.

• STDnav: the standard pan and zoom technique, used as baseline. A left mouse drag pans the view in world space proportional to the number of pixels dragged in screen space, and the mouse wheel zooms around the center of the view.

In order to compare information gains between the two conditions, we make the same computations as for BIGnav in the STDnav condition, except for the display of the new view.

Distribution (DISTR)

In order to compare different types of information spaces, we compared 6 distributions of points of interest by combining three spatial distributions (Grid, Random and Cluster) with three probability distributions (Uniform, Random, Cluster) of the a priori likelihood of each target. Since not all combinations are meaningful, we selected 6 of them. The first 3 have a uniform probability distribution, e. g. all points of interest have equal probability of being the target, and different spatial distributions:

• Grid+Uniform: Points of interest are arranged in a grid, providing a strong visual pattern.

• Random+Uniform: Points of interest are placed randomly.

• Cluster+Uniform: Points of interest are organized in clusters that are typical of geographical maps [START_REF] Stephen | Integrating multi-criteria evaluation with geographical information systems[END_REF], where a central city is surrounded by smaller towns. We used 5 clusters of 10 targets.

The other 3 distributions use a non-uniform probability distribution of being the target:

• Grid+Random: Points of interest are on a grid with random probabilities of being the target. These probabilities are bounded by Uniform and Cluster.

• Random+Random: Points of interest are randomly distributed and have random probabilities.

• Cluster+Cluster: Points of interest are clustered and the probability of the center of each cluster is ten times higher than that of the surrounding points of interest.

The first 3 configurations are meant to demonstrate that BIGnav works well even without prior knowledge about potential targets. The other 3 configurations are meant to assess the added advantage, if any, of using such prior knowledge. In particular, the last distribution is typical of, e. g. maps.

Index of Difficulty (ID)

The ID is related to the distance between the initial position of the view and the target to navigate to. Using Fitts' definition of the ID [START_REF] Paul | The information capacity of the human motor system in controlling the amplitude of movement[END_REF], the distance D to travel is D = 2 ID × W, where W is the (constant) target width. We adopted the same large IDs as in other multiscale navigation studies [START_REF] Appert | OrthoZoom Scroller: 1D Multi-scale Navigation[END_REF][START_REF] Javed | GravNav: Using a Gravity Model for Multi-scale Navigation[END_REF]: 10, 15, 20, 25 and 30 bits.

We used a [2×6×5] within-subject design: we tested 2 Tech for 6 DISTR and 5 ID conditions. Each condition was replicated 5 times, so that each participant performed 300 trials. We blocked the conditions by Tech. Half the participants started with STDnav and the other half with BIGnav. Within each block, we systematically varied the order of DISTR and ID combinations across participants using a Latin square so as to reduce the influence of learning effects. For each condition, the targets were drawn randomly according to the probability distribution of the DISTR condition. All participants used the same target in the same DISTR× ID× Replication condition.

Task

The task is a multiscale pointing task: starting from a fully zoomedout view, the participant must navigate towards the target until it is fully zoomed in and click on it. The target is surrounded by concentric circles so that it is always possible to tell in which direction and how far it is (Fig. 35).

The information space contains 50 points of interest: 49 are distractors and displayed in blue, one is the target and displayed in red. The ID is used to compute the scale of the initial view so that it contains all the points of interest. The target becomes green and clickable only when the view is fully zoomed in.

Participants first receive general instructions about the session and performed several practice trials with each technique. After the session, they answer a questionnaire asking them for feedback and comments on the experiment and the techniques. A typical session lasts 60 minutes, including training.

Data Collection

For each trial, the program collects the task completion time (TCT), the commands that the participants issued, the uncertainty and position of the view at each step and the information gain after each command. We collected 2 Tech × 6 DISTR × 5 ID × 5 Replications × 16 Participants = 4800 trials in total.

results

For our analyses, we first removed 23 missed trials (about 0.5%) and then 54 outliers (about 1.1%) in which TCT was 3 standard deviations larger than the mean. We verified that misses and outliers were randomly distributed across participants, techniques and conditions.

Task Completion Time

Table 5 shows the results of a repeated-measures full factorial ANOVA on TCT. All main effects are significant, as well as two interaction effects: Tech × DISTR and Tech × ID.

Figure 36 shows the interaction effect between Tech and ID for task completion time (TCT). On average, BIGnav is 24.1% faster than STDnav across all ID. A post-hoc Tukey HSD test reveals a robust interaction effect: BIGnav is significantly faster than STDnav when ID > 15 (p < 0.0001), significantly slower when ID = 10 (p < 0.0001) and not significantly different for ID = 15 (p = 0.99). These results support H1: BIGnav is 22.3% faster than STDnav for ID = 25 and 35.8% faster for ID = 30. In summary, these results support hypotheses H1 and H2: BIGnav is faster than STDnav for distant targets, especially in non-uniform information spaces. BIGnav is also not significantly different from STDnav for close targets (ID = 15).

Number of Commands

In order to get a sense of the differences in control strategies across conditions, we compare the number of user commands issued by the participants. Because of the continuous control in the STDnav conditions, we aggregate the mouse and wheel events as follows: we count one panning command per sequence from a mouse down to a mouse up, and one zooming command per series of mouse wheel with less than 300ms between them.

We perform a Tech × DISTR × ID full-factorial ANOVA on the number of commands issued (Table 6) and find that while Tech and ID significantly affect the number of commands used, DISTR has a non-significant effect. The ANOVA also indicates that the Tech × ID interaction effect is significant. A post-hoc Tukey HSD confirms that while the number of commands progressively increases with ID in STDnav, it is barely affected by ID in BIGnav (Fig. 38). BIGnav illustrates how to derive a probability distribution from external data, here the population of the cities. More generally, the distribution should reflect the targets' degree of interest, which is typically application-dependent. The distribution can also integrate usage data, such as the most popular cities. Finally the results of a search can be turned into a distribution according to the ranking of the results, therefore integrating searching and navigation into a single paradigm.

discussion

We have shown that BIGnav is an effective technique, especially for distant targets and non-uniform information spaces. The most efficient distribution condition in the experiment was Cluster+Cluster, which corresponds to the small-world structures found in a large number of datasets, showing that BIGnav is a promising approach for real-world applications.

However, both the experiment and the BIGnav prototype exhibit some shortcomings, especially for small-ID tasks. We now discuss how to make BIGnav more comfortable to use.

In standard pan-and-zoom interfaces, users can navigate the space in a continuous manner and constantly anticipate the system response. This gives them a sense of control and makes for a smooth user experience. By contrast, BIGnav uses discrete steps and the system's response can be difficult to anticipate and even frustrating, in particular when getting close to the target. This results in long idle times between commands (Fig. 40) and a higher cognitive load as users reorient themselves and decide on their next move. In a sense, this proves the success of the technique, since it is designed to maximally challenge the user at each step.

Yet there must be a way to improve user experience and make navigation smoother. First, we could use animations to smooth transitions and help users stay oriented 3 . Research has shown that one-second animations are sufficient and do not slow down expert users [START_REF] Benjamin | Does animation help users build mental maps of spatial information?[END_REF]. Second, we could combine BIGnav with standard pan-and-zoom according to user input: large panning and zooming movements would use BIGnav, smaller ones traditional pan and zoom. Finally we could reduce the size of the grid and increase the number of panning directions to provide finer control, however this requires heuristics or optimizations of the computational cost.

In the next two chapters, I demonstrate another use of the BIG framework where improved efficiency and user experience are both met in the context of hierarchical file retrieval. I will return to more discussions of these two applications as well as the framework itself in Chapter 12.

I first review related work on personal file systems, file retrieval techniques, and adaptive user interfaces in this chapter. In the next chapter, I describe BIGFile's interface as well as its underlying algorithm and report on two studies.

personal file systems

Many prior studies have investigated how people manage and retrieve information from their personal file systems.

File Management

File hierarchies are the predominant way to organize files: files and folders nested inside other folders. Previous studies that investigated how people structure their file hierarchies have found that these hierarchies are broad, shallow, and often unbalanced.

Gonçalves and Jorge [START_REF] Daniel | An empirical study of personal document spaces[END_REF] analyzed the structure of the file hierarchies of 11 participants, examining only portions containing user documents. Users averaged about 8000 files, however there was considerable variation. Folders contained an average of 13 files, had a branching factor (the average number of subfolders at a given tree level) of 1.84, and the hierarchies were fairly well balanced. The hierarchies had an average depth of 8. [START_REF] Dumais | Stuff I'Ve Seen: A System for Personal Information Retrieval and Re-use[END_REF]. In an analysis of filenames, they found that 60% of filenames contained numbers, but only 0.33% contained dates. Filename lengths averaged 12.6 characters. However they are likely longer in modern systems as the study was conducted in 2003 and file systems no longer impose tight constraints on filename lengths.

Henderson and Srinivasan [START_REF] Henderson | An empirical analysis of personal digital document structures[END_REF] ran a similar but larger scale study of Windows XP users in 2009, again analyzing portions of hierarchies that contained user documents. They found similar results to Gonçalves and Jorge: 5850 documents per user, an average tree depth of 9.65, folders containing an average of 11.1 files and a branching factor of 1.93. They also found that 74% of folders did not contain any subfolders, but the folders that did averaged 4.1 subfolders each. 7.9% of folders were completely empty. When performing name comparisons, 21.8% of filenames were duplicates, as well as 23.5% of folder names. Although the average maximum tree depth was 9.65, average depths within the trees were considerably smaller -3.4.

Futhermore, users tend to have different habits for building these structures. Malone [START_REF] Malone | How Do People Organize Their Desks?: Implications for the Design of Office Information Systems[END_REF] described two types of users based on their document management strategies for paper documents, later referred to as filers and pilers [START_REF] Teevan | The Perfect Search Engine is Not Enough: A Study of Orienteering Behavior in Directed Search[END_REF]. Filers are more organized, quickly classifying new documents and placing them in an appropriate location. Pilers spend less effort organizing their documents, and their collections may appear to be less orderly. This reduced level of organization means that it can be harder to remember document locations. Whittaker and Hirschberg [START_REF] Whittaker | Email Overload: Exploring Personal Information Management of Email[END_REF] also found that people often forgot the categories they had already created, leading to duplicate categories that meant that files were often overlooked when attempting to retrieve all the information on a topic.

File Retrieval

Similar to various file management practices, users retrieve files in different manners.

How Fast Do Users Retrieve Files?

In a large-scale study with 289 participants, Bergman et al. [START_REF] Bergman | How Do We Find Personal Files?: The Effect of OS, Presentation & Depth on File Navigation[END_REF] examined how various factors affected file navigation (retrieving a file by traversing through the hierarchy using a file browser). Their method involved statically recording the state of participants' 'recent documents' list, then asking them to navigate to each of those files using a file browser, with video capturing their actions. By analyzing the video they found that Mac and Windows users structured their files in different ways, with Windows users keeping more files but fewer subfolders in each folder than Mac users. As a result, retrieved files were deeper in the file hierarchy on Windows (2.9 levels deep, compared to 2.4 levels on Mac OS X) and file retrieval times were slower (17.3 seconds on Windows, 12.6 seconds on Mac OS X). [START_REF] Fitchett | An empirical characterisation of file retrieval[END_REF] conducted a 4-week empirical study to characterize 26 participants' actual file retrievals on their personal Mac computers. They found that the mean time to retrieve files using file browser navigation was 10.2 seconds, vs. 5.7 seconds when using Spotlight searches, and 16.5 seconds when using Finder searches. Their explanation for the high mean value with Finder search is that it was used for files that were harder to find. Since each navigation retrieval can be decomposed into a series of individual steps at each level of the hierarchy, they also analyzed 'step time', where each step descended to the next level of the hierarchy within a single window by opening a folder. They found that the mean step time was 3.6 seconds and that the step times were shorter at deeper levels, possibly because deeper locations contain fewer items [START_REF] Bergman | How Do We Find Personal Files?: The Effect of OS, Presentation & Depth on File Navigation[END_REF].

Fitchett and Cockburn

Bergman et al. offered an explanation by the relative cognitive requirements of the two approaches [START_REF] Bergman | Improved Search Engines and Navigation Preference in Personal Information Management[END_REF]. They pointed out that users prefer orienteering (that is, taking small steps towards a target using partial information and contextual knowledge) to teleporting (that is, jumping directly to the target) [START_REF] Ravasio | In Pursuit of Desktop Evolution: User Problems and Practices with Modern Desktop Systems[END_REF][START_REF] Teevan | The Perfect Search Engine is Not Enough: A Study of Orienteering Behavior in Directed Search[END_REF]. Navigation uses an orienteering approach, with users able to use recognition at each step of a retrieval to identify the next folder [START_REF] Bergman | Improved Search Engines and Navigation Preference in Personal Information Management[END_REF]. Orienteering offers several advantages over keyword search, including decreased cognitive load, a sense of location, and a better understanding of the result [START_REF] Teevan | The Perfect Search Engine is Not Enough: A Study of Orienteering Behavior in Directed Search[END_REF]. Bergman et al. [START_REF] Bergman | Improved Search Engines and Navigation Preference in Personal Information Management[END_REF] also note that, with navigation, "users can continue to think of the project they are working on at the time", even if search might be faster.

Search interfaces, on the other hand, typically use a teleporting approach that shows an immediate list of results with little or no context [START_REF] Teevan | The Perfect Search Engine is Not Enough: A Study of Orienteering Behavior in Directed Search[END_REF]. Search also relies on users recalling attributes of a target file in order to devise a search query [START_REF] Bergman | Improved Search Engines and Navigation Preference in Personal Information Management[END_REF], which is more cognitively demanding than recognition [START_REF] Treisman | Perceptual grouping and attention in visual search for features and for objects[END_REF]. Furthermore, search offers no reminding feature. This means that users are unlikely to encounter an item through search if they have forgotten they have it or how it is described in the file system, resulting in a lower sense of control [START_REF] Barreau | Finding and Reminding: File Organization from the Desktop[END_REF]. A final potential limitation of search-based file access is that it provides minimal support for learning and rehearsing the location-based retrieval mechanics that users are likely to use for future accesses.

Folder Uncertainty

If users are unsure of their navigation to files, they are likely to open more folders than necessary, i. e. opening an incorrect folder and then backtracking. Elsweiler et al. [START_REF] Elsweiler | Understanding Re-finding Behavior in Naturalistic Email Interaction Logs[END_REF] introduced the Folder Uncertainty Ratio (FUR) to account for this effect in email folders. FUR is defined as "the number of folders opened with respect to the number of unique folders opened".

Fitchett [START_REF] Fitchett | An empirical characterisation of file retrieval[END_REF] reported that in their study, the mean FUR value for navigation retrievals was low at 1.02. The percentage of retrievals with a FUR > 1 was 5.2%, and the percentage of retrievals with FUR 2 was 0.3%. These values contrast with Elsweiler et al. [START_REF] Elsweiler | Understanding Re-finding Behavior in Naturalistic Email Interaction Logs[END_REF] who found high levels of uncertainty when navigating to email messages, with 29.5% of retrievals having a FUR > 1, and 8.67% having FUR 2. Fitchett [START_REF] Fitchett | An empirical characterisation of file retrieval[END_REF] offered a plausible explanation that users invest more effort in crafting effective file hierarchies than they do with email.

These practices and characteristics might evolve over time with the continuous improvements in search algorithms and the introduction of new interfaces and novel interaction techniques. In the next chapter, I report on a pilot study to capture real users' file structures and understand their file navigation practices, informing our simulations (Study 1) and experiment (Study 2).

Prediction

Several prediction algorithms have been proposed to account for users' repetitive behavior and to improve the efficiency of accessing previously used items. Algorithms that predict upcoming actions based on previous actions include:

1. Most Recently Used (MRU) calculates ranks based solely on recency.

2. Most Frequently Used (MFU) calculates ranks based solely on frequency.

3. Split Recency and Frequency (SR&F) [START_REF] Findlater | A Comparison of Static, Adaptive, and Adaptable Menus[END_REF] selects n items with MRU, then the rest with MFU.

4.

Combined Recency and Frequency (CRF) [START_REF] Lee | On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies[END_REF], used originally for cache management, considers every past access of an item. It is calculated by Equation 38, where w f is the item's weight, n is the number of past accesses, t is the current time and t i is the time of access i (where time is counted in terms of discrete events).

w f = n i=1 1 p λ(t-t i ) . ( 38
)
5. The Adaptive algorithm filters menus in software such as Microsoft Office 2000 [START_REF] Michael P Arcuri | Adaptive menus[END_REF]. Item counts are incremented when selected and decremented after multiple sessions of disuse.

6. The Places Frecency algorithm (PF) is used in Firefox to order URL suggestions when typing a web address [START_REF]The Places frecency algorithm[END_REF]. The last 10 accesses of each item are placed in time-based buckets with different weights based on recency. Other factors, such as the method of website access, are also incorporated but can be stripped out for general purpose use.

7.

A Markov chain [START_REF] Andreyevich | The theory of algorithms[END_REF] can be used to make predictions:

P(X n+1 = x|X n = x n ) = |x n → x| |x n | .
where |x n | is the number of previous occurrences of state x n , and |x n | is the number of previous transitions from state x n to x. X i represents the state at time i. Given the most recent access x n , the calculated probabilities provide a ranking, and MRU can be used to break ties.

8.

AccessRank uses a score that blends Markov chains and CRF, a time weighting component as well as a switching threshold to predict what users will do next and to maximize list stability [START_REF] Fitchett | AccessRank: Predicting What Users Will Do Next[END_REF].

The AccessRank score w n is defined as:

w n = w m n α w crf n 1 α w t n . ( 39
)
where w m n is the Markov weight and w crf n is the combined recency and frequency (CRF) weight with p = 2 and λ = 0.1 (Equation 38). The Markov weight is rewritten to always give non-zero weights:

w m n = |x n → x| + 1 |x n | + 1 .
time weight w t n gives higher weight to items that have historically been more frequently accessed at the current time of day or day of week, and is defined as:

w t n = max(0.8, min(1.25, hd)) 0.25 .
where h and d are defined as follows: let c h be the current hour of the day. For item n, let h be the ratio of the number of previous accesses of n in hours in the range [c h -1, c h + 1] compared to the average number of previous accesses of n for a three hour slot. Similarly, let d be the ratio of the number of previous accesses of n on the current day of the week to the average across all days of the week. h and d are set to 1 if fewer than 10 accesses in total have occurred in the corresponding slot.

To improve prediction list stability, Fitchett and Cockburn [START_REF] Fitchett | AccessRank: Predicting What Users Will Do Next[END_REF] also defined a switching threshold: item A and item B are compared and their new weights w A and w B are such that w B > w A , then B will only be ranked higher than A if w B > w A + δ where δ 0 is an AccessRank parameter. An item C not in the previous list is assumed to have ranking r C = ∞.

Using 3 log datasets from previously published studies (window switching [START_REF] Tak | Understanding and Supporting Window Switching[END_REF], web browsing [START_REF] Tauscher | How people revisit web pages: empirical findings and implications for the design of history systems[END_REF], and command line use [START_REF] Greenberg | Using unix: Collected traces of 168 users[END_REF]), Fitchett and Cockburn [START_REF] Fitchett | AccessRank: Predicting What Users Will Do Next[END_REF] demonstrated that AccessRank more accurately predicts upcoming accesses than Markov, CRF and MRU. Moreover, the prediction lists generated by AccessRank are more stable than the three other algorithms (Fig. 45).

Based on the results, they also recommended to use (λ, δ) values of (1.65, 0.2) to give the best compromise between accuracy and stability [START_REF] Fitchett | AccessRank: Predicting What Users Will Do Next[END_REF]. When stability is unimportant, values of (1.65, 0) give the best top prediction accuracy, while (2.5, 0) may be better if the average rank is the primary goal. When stability is particularly important, high values for both parameters can be used, e. g. (2.5, 0.5).

BIGFile features a split adaptive interface (Fig. 53): the shortcuts are presented in the adaptive area at the top, while the static area at the bottom is a traditional list view of the current folder. The shortcuts in the adaptive area are the paths to the items selected by the BIGFile algorithm, relative to the current folder. Displaying the relative paths, rather than just the items, offers users contextual information that helps them determine if they correspond to the target they are looking for. It also lets users navigate directly to any folder in the path by clicking on it, typically when the target is not in the shortcuts, but a partial path to it is. Finally a back button (visible in Fig. 57) lets users go back to the previous state of the interface.

Both the shortcuts in the adaptive area and the items in the static area are updated after each user input. Similar to many other split adaptive interfaces [START_REF] Findlater | A Comparison of Static, Adaptive, and Adaptable Menus[END_REF][START_REF] Sears | Split Menus: Effectively Using Selection Frequency to Organize Menus[END_REF], if the system correctly estimates the user's target item, the user can select the shortcut, or navigate the hierarchy using the static part as usual. If none of the system's estimates are correct, the impact for the user is minimal since the items remain at their usual locations in the static part of the interface.

For example, in Fig. 53 (left), "Islands" and "Cheese" are the estimated items, presented along with their paths in the designated adaptive area (a). The static area (b) presents the usual hierarchy. A user could, for example, click on "Dairy" to access dairy products other than "Cheese" inside the folder (not shown in the figure). If the user clicks on "Animals", the static area is updated, showing the items inside the "Animals" folder (Fig. 53 (d)). The adaptive area is also updated with a new set of estimated targets ("Dog" and "Salmon", Fig. 53 (c)). If the user is looking for the item "Dog", she can save one step ("Mammals") by clicking the shortcut in the adaptive area. The number of shortcuts is user-customizable.

We created and considered a number of alternative designs for the interface, including an integrated view where each shortcut is displayed, together with its path, next to the corresponding root folder in the list view. However, we found that this integrated view makes it difficult to display shortcuts of arbitrary depth. Moreover, scrolling the view often hides shortcuts, which partially defeats their purpose. In addition, this design only works for the list view, while the split interface can work with any of the traditional views in the static area, e. g. the icon and column views of the Mac OS Finder. Therefore, we chose what seemed to be the simplest and most obvious option for our first implementation and comparison. Note that the split interface design is not specific to BIGFile and can be used with any algorithm that predicts potential targets. For example, we used it with the Ac-cessRank algorithm in Study two, described later this chapter.

bigfile algorithm

I introduce two algorithms for BIGFile: BIGFileOpt, an optimal but computationally costly algorithm and BIGFileFast, a suboptimal but very efficient version, which is used for both the simulations and experiment.

BIGFileOpt: Optimal Algorithm

In order to apply the Bayesian Information Gain (BIG) framework to file retrieval, let us consider a regular hierarchical file system. Without loss of generality, we consider a single window, with a current folder F. We define the following:

• Θ represents all the folders and files that a user might be interested in. Θ may include all the files and folders in the file system, but is more likely to be narrowed to a subset based on user preference or the task at hand. For example, it can be reduced to a subset of the user's home folder and/or to a category of files such as documents of a certain type. In the simulations and the experiment, we used only the files as potential targets and excluded the folders.

• For each potential target Θ = θ, the initial probability, at the beginning of a retrieval task, that it is the actual intended target is P(Θ = θ). This probability distribution is calculated using the Combined Recency and Frequency (CRF) algorithm (Equation 38) using {p = 2, λ = 0.1}, in AccessRank [START_REF] Fitchett | AccessRank: Predicting What Users Will Do Next[END_REF]. The probability that a file θ is the target is calculated by normalizing its weight: P(Θ = θ) = w θ / w θ and is updated after each retrieval of a target by the user, to reflect interaction history. At each step of the retrieval task, i. e. after each user input, P(Θ = θ) is updated using Bayes' rule, as described in Algorithm 1.

• X represents the view generated by the system when first opening a window and after receiving each user input in that window. This view is composed of the static part S, which shows the folders and files of the current folder F, and the adaptive part A, which shows the N folders and files that are produced by the BIGFile algorithm to serve as shortcuts at this step. A view X = x is therefore represented by S A. The number of shortcuts N is user customizable.

• Y represents any user input. At each step, the user issues an input Y = y to the system: the user can select any of the items in the static and adaptive parts, or go back to the previous view with the back button in case of an error.

Algorithmus 1 : BIGFileOpt Search the optimal set of N shortcuts.

Data : Θ, X, Y, P(Y = y|Θ = θ, X = x), IG max = 0 Result : Return set A that, together with set S, has the maximal expected information gain (IG). • P(Y = y|Θ = θ, X = x) represents prior knowledge about user behavior: given view x and target θ, what is the probability that user input is y at this step. For simplicity, one can assume that the user does not make mistakes and therefore that this probability is 1 if the user is issuing the correct input, 0 otherwise. Alternatively, one can use a calibration session, as in the BIGnav experiment (Chapter 9). Note that since the user may select items that are not in Θ during the steps that lead to a selection, user behavior must be known for any item in the file system.

At each step, i. e. after each user input, the static part S of the interface is updated if the current folder has changed, i. e. if the user has clicked on a folder to navigate to it. Then the adaptive part A of the interface is updated to display the N items selected by the BIGFile algorithm.

Algorithm 1 presents BIGFileOpt, an optimal algorithm that finds the N items that, together with S, maximize the expected information gain from the user's next input. This slight modification of the original BIG framework lets us calculate an optimal view S A. However, considering the sizes of typical personal file systems, this algorithm is not practical: the number of sets to test grows like f N , where f is the number of files and folders and N the number of items in the adaptive part. I now present a suboptimal but computationally efficient algorithm to address this problem.

Navigation Difficulty. Participants reported two main challenges when retrieving a file: (1) files/folders with repeated names, and (2) having partial knowledge about the location or the name of the target. This echoes previous studies [START_REF] Henderson | An empirical analysis of personal digital document structures[END_REF][START_REF] Malone | How Do People Organize Their Desks?: Implications for the Design of Office Information Systems[END_REF] reporting that people face retrieval difficulties stemming from semantic ambiguity. Hence, contextual information is crucial for a successful file retrieval. We used the findings from this pilot study to inform the designs of the simulations and experiment.

11.4 study 1: simulations I ran simulations to investigate BIGFileFast's performance in estimating the target in a given hierarchical structure. The goal was to know how well the algorithm performs with respect to the following factors:

1. Depth and width: Both previous studies [START_REF] Daniel | An empirical study of personal document spaces[END_REF][START_REF] Henderson | An empirical analysis of personal digital document structures[END_REF] and our pilot study show that users have different file structures. Combining the results from [START_REF] Daniel | An empirical study of personal document spaces[END_REF][START_REF] Henderson | An empirical analysis of personal digital document structures[END_REF] and our pilot study, we used DEPTH = {4, 6, 8, 10, 12} and BRANCHING FACTOR = {2, 4, 6, 8} for the simulations.

Initial distribution:

We did not log participants' use of their file system in the pilot study, but previous work indicates that file system use approximately follows a Zipf distribution [START_REF] Fitchett | An empirical characterisation of file retrieval[END_REF]. To simulate different types of use history, we used two DISTRI-BUTIONs: Z(s = 1) and Z(s = 2). The latter is a more skewed distribution describing cases where users focus primarily on a small set of targets.

3. Size of target set: Both previous work [START_REF] Daniel | An empirical study of personal document spaces[END_REF][START_REF] Henderson | An empirical analysis of personal digital document structures[END_REF] and the pilot study suggest that users have different numbers of files and folders in their file system. Therefore, we used different target set sizes to see how BIGFileFast would perform. In our simulations, TAR-GET SET SIZE = {10, 100, 1000}.

We used AccessRank as baseline as it outperforms existing prediction algorithms [START_REF] Fitchett | AccessRank: Predicting What Users Will Do Next[END_REF]. In the case of navigation-based file retrieval, AccessRank predicts the target by assuming that a subfolder is likely to be selected if its parent folder is selected, captured by the Markov chain model. Similarly, BIGFileFast also assumes that the target is within the subtree of the current folder, and renormalizes the probabilities at each step. The key differences between AccessRank and BIGFileFast are as follows:

• AccessRank assigns a score to all folders and files while BIG-FileFast only considers the set of potential targets.

• AccessRank updates the score of an item (file or folder) once it has been clicked while BIGFileFast updates the probability of all potential targets after each user input.

• AccessRank identifies the N items with highest scores while BIGFileFast identifies N items that provide the maximally informative view.

• AccessRank has a parameter δ to control the stability of the prediction list; BIGFileFast does not.

Simulation Settings

We generated a number of symmetric hierarchical structures crossing DEPTH with BRANCHING FACTOR = 2 and BRANCHING FAC-TOR with DEPTH = 4. When needed, extra targets were added at the deepest level so that there would be 100 and 1000 targets respectively. Depending on the target set sizes, we constructed a series of selections following the Zipf distributions. We randomized the mapping between the Zipf distribution and the targets, as well as the order of the selections.

We logged the number of steps needed to locate the target, the information gain and the accuracy rate for both algorithms. Note that we consider the folders on the path to the final target to be partially correct. For example, if the target is at level L 2 but the shortcut is only correct up to the folder at level L 1 < L 2 , we consider the accuracy rate to be L 1 /L 2 , no matter how many steps it takes to get to the target level L 2 .

We used {α = 0.8, δ = 0.5} for AccessRank as in [START_REF] Fitchett | Improving Navigation-based File Retrieval[END_REF] and {p = 2, λ = 0.1} in CRF for both AccessRank and BIGFileFast. We also assumed 100% correct user behavior for all simulations, i. e. that users would be as efficient as possible, always selecting an item from the adaptive area if it would get them to the target in fewer steps. Each condition [DEPTH × BRANCHING FACTOR × TARGET SET SIZE × DISTRIBUTION] was run 100 times, and the average taken.

Simulation Results

Fig. 56 shows the number of steps and the accuracy rate for the two algorithms using a Z(s = 1) distribution. The results for Z(s = 2) distribution are very similar; both BIGFileFast and AccessRank performed slightly better than they did with the Z(s = 1) distribution. This is intuitive since both algorithms are based on frequency and recency of the file system use, and Z(s = 2) focuses on a small set of very frequent items. In information-theoretic terms, the computer starts with more knowledge (less uncertainty) about the user's goal.

By comparison, BIGFileFast considers each user input within a retrieval, and since it assumes correct user behavior, if a node is shown and not chosen, all potential targets inside that node will be assigned a probability of 0. Therefore, the whole branch starting from that node will be discarded, i. e. it will not show up in the prediction slots at the next step.

Increasing the branching factor negatively affects both BIGFileFast and AccessRank (Fig. 56,bottom). The accuracy rate of BIGFileFast drops from 66.5% to 30.1% while the accuracy of AccessRank drops from 62.4% to 24.3%. This is not surprising as there is not much information from the user input for a wide but shallow (DEPTH = 4) hierarchy. Increasing target set size also negatively affects the performance of both BIGFileFast and AccessRank.

Averaged across all simulations, BIGFileFast is 15.5% more accurate and takes 23.1% fewer steps than AccessRank. The results can be summarized as follows: The deeper the target is located, the better BIGFileFast is than AccessRank; Increasing either target set size or branching factor negatively affect the performance of both BIG-FileFast and AccessRank; and BIGFileFast performs better on a deep hierarchy than on a broad hierarchy. This echoes the results of BIGnav, which exhibits better results on navigation tasks with higher IDs, i. e. on harder tasks. We next compare BIGFile (which uses BIGFile-Fast) with a split interface using AccessRank in an experiment with real users.

study 2: experiment

I conducted an experiment to investigate the effectiveness of BIGFile with users. The goal was to replicate and extend the methodology used by Fitchett et al. [START_REF] Fitchett | Improving Navigation-based File Retrieval[END_REF]. We used their implementation of the algorithm with the exception of one improvement which is noted below. We also used their hierarchical structure, which is a 3-level semantically organized hierarchy.

Since the pilot study showed that people do navigate to deep levels, we extended their structure to 6 levels using the branching factors and folder sizes from Bergman [START_REF] Bergman | The Effect of Folder Structure on Personal File Navigation[END_REF]: 10, 5, and 4 folders, and 11, 8 and 7 files at levels 4, 5 and 6 respectively. Example targets for level 3 include 'Dog' with the path "Animals > Mammals > Dog" and 'Darwin' with the path "People > Inventors/Scientists > Darwin". Example targets for level 6 include 'Hawaii' with the path "Geography > Islands > Tropical > Touristic > Large > Hawaii", and 'Brie' with the path "Food > Dairy > Cheese > France > Creamy > Brie". As in [START_REF] Fitchett | Improving Navigation-based File Retrieval[END_REF], only the folders containing the final target are populated. In total, the hierarchy contains 958 folders and 1068 files, of which 30 files are chosen as targets for each level-3 and level-6 condition.

Method

We used a [3×2] within-subject design with 3 INTERFACE conditions: BIGFile with the BIGFileFast algorithm, ARFile, a split interface using AccessRank for prediction, and a standard Finder interface as baseline; and 2 target LEVELs: 3 and 6.

We made a slight modification to AccessRank in order to make ARFile as effective as possible for users. In AccessRank, each folder and file is assigned a score. If users constantly go to the same item (file or folder), the algorithm's set of top predictions might include both the item and its parent folder. Since we are showing the full paths to the predicted items (not just the items themselves), this would result in an overlap between the shortcuts. Therefore we only show the deepest path if one shortcut is a prefix of another.

To model the user behavior, we used the notion of Folder Uncertainty Ratio [START_REF] Elsweiler | Understanding Re-finding Behavior in Naturalistic Email Interaction Logs[END_REF], which was used by Fitchett & Cockburn [START_REF] Fitchett | An empirical characterisation of file retrieval[END_REF] to illustrate users' uncertainty when navigating to files. If users are uncertain that they are going down the correct path, they are likely to select incorrect folders by mistake. Fitchett and Cockburn [START_REF] Fitchett | An empirical characterisation of file retrieval[END_REF] found that users were accurate about 94% of the time, while the other 6% of the time, they clicked on the wrong folder. Thus, we set the rate of correct user input to 94% and divided the remaining 6% among the other user inputs. These rates were used in the user behavior function in BIGFileFast and for calculating information gain in ARFile and in Finder. Furthermore, as in our simulations, we used {α = 0.8, δ = 0.5} for AccessRank as in [START_REF] Fitchett | Improving Navigation-based File Retrieval[END_REF] and {p = 2, λ = 0.1} for CRF for both Ac-cessRank and BIGFileFast. A list view was used for the static part in all interface conditions because it was preferred in our pilot study.

Participants

Eighteen participants (7 women), aged 21 to 39 (mean = 28.5, σ = 5.1), all right-handed and with normal or corrected-to-normal vision, volunteered to participate in the experiment. Ten were MacOS users, eight were Windows users but were familiar with list view.

Apparatus

The experiment was conducted on a Macbook Pro with a 2.7 GHz processor, 8 GB RAM with resolution of 2560×1600. The file browser window was 880 × 631 pixels, as in [START_REF] Fitchett | Improving Navigation-based File Retrieval[END_REF]. One row on the list view takes 20 pixels. The software was implemented in Swift 3.0. The code can be found at https://github.com/wanyuliu/BIGFile.

Each trial started by displaying the stimulus inside a popup window hiding the file browser. Participants were instructed to take as much time as they needed to understand the stimulus. When they were ready, they hit a start button to initiate the trial, at which point the content appeared inside the file browser (in both the adaptive and static parts, for the two conditions with split interfaces) and they were instructed to retrieve the file as fast and accurately as possible. When the popup window disappeared, the stimulus was shown in the toolbar at the top of the file browser, as in Fig. 57. When the participant successfully clicked the target, a popup window appeared with the stimulus for the next trial. If they clicked a wrong target, a popup window let them know that they had made an error and asked them to try again. After clicking a folder or a file, the score for this item was updated in ARFile. Similarly, after each user input, the probability of each potential target being the actual target was updated, and after each retrieval, the initial distribution for the potential targets was updated in BIGFile.

Session 2 repeated Session 1 with the same initial distribution and randomized selection order. The goal was to see whether and how participants would use the split interfaces once they were more familiar with the file hierarchy and had some expectations about the targets, which is more representative of real use. Participants could take a break between sessions and between interface conditions.

For each level, we categorized the 30 targets into 3 non-overlapping groups of 10. To reduce learning effects stemming from familiarity with the hierarchy, within each group, the targets came from different top-level folders for level 3, and from different second-level folders for level 6. The order of interface and group of targets were counterbalanced using Latin Square across all participants. Thus, the target group, the order in which each target group is seen, the ordering of targets within a group, and the order in which each interface is seen all serve as control variables. After Session 2, for each interface, participants completed the NASA Task Load Index (TLX) worksheets [START_REF] Sandra | Development of NASA-TLX (Task Load Index): Results of empirical and theoretical research[END_REF] and provided comments on the interface. After all three conditions, participants were asked for their preferences among the three interfaces. The experiment lasted about 90 minutes.

Data Collection

For each trial, the program collects the task completion time (TCT), the number of steps a participant takes to locate the target (the number of items clicked, including the final target), the amount of time spent at each step, the uncertainty the computer has about the final target, the calculated shortcuts, the participant's input at each step,

results

For the analyses, we first removed 60 outliers (about 1.3%) in which TCT was larger than 3 standard deviations from the mean. We verified that outliers were randomly distributed across participants, interfaces and conditions. We also checked for outliers for all our other dependent variables, but none were found. Note that the results are the same if we include the outliers in the analyses. Except where noted, we ran a repeated-measures INTERFACE × LEVEL × Session factorial ANOVA on the dependent measures1 . On average, BIGFile is 39.3% faster than ARFile, and 59.0% faster than Finder, across all levels and sessions. The significant interaction effect between INTERFACE and textbfLEVEL is shown in Fig. 58 (a) and (b). A post-hoc Tukey HSD test reveals that all differences are significant: BIGFile is 44.5% faster than ARFile and 63.8% faster than Finder at level 6, while BIGFile is 27.8% faster than ARFile and 47.6% faster than Finder at level 3. These findings are consistent with our simulation results: the deeper the target is located, the better BIGFile-Fast is compared to AccessRank.

Task Completion Time and Step Time

For example, Gajos & Chauncey [START_REF] Krzysztof | The Influence of Personality Traits and Cognitive Load on the Use of Adaptive User Interfaces[END_REF] have demonstrated systematic individual differences in the use of adaptive features, correlated with users' personality traits. Hence this approach does not benefit all users equally. In our case, the preference might be due to the nature of the task: retrieving a file in a 3-level or 6-level hierarchy is much more difficult than selecting menu items, which is the task used in most split adaptive interface studies. Therefore, split adaptive interfaces may be more beneficial for difficult tasks where users need to "work hard" to reach their goal.

One possible issue with split interfaces is screen real estate. The more shortcuts are shown in the adaptive area, the better the underlying algorithm will work. But more shortcuts use more space and may result in higher cognitive demand and more occurrences of scrolling. Future work should therefore study the effects of the number of shortcuts on performance, preference and cognitive load.

Comparisons with AccessRank

Even though BIGFileFast can locate the final target more accurately than AccessRank in our simulations and experiment, unlike Access-Rank, it does not account for repeated user behavior and repetitive access at the same time of day or day of the week. It also does not have a parameter to control the stability of estimated shortcuts across successive steps. These features are likely to benefit users in real settings. Future work should study their effect in BIGFile. More generally, Ac-cessRank needs to be compared with BIGFileFast in more realistic settings.

We were surprised that users did not express a preference between BIGFile and ARFile, attributing the differences to the set of targets rather than the underlying algorithm. This may be due to the fact that interface differences are more obvious to users than the inner workings of a system. Indeed, Fitchett et al. [START_REF] Fitchett | Improving Navigation-based File Retrieval[END_REF] found Icon Highlights and Search Directed Navigation to be more effective than Hover Menus, even though the latter predicts targets several levels down the hierarchy. In that respect, our split interface is an alternative to Hover Menus that shows to be effective for both BIGFileFast and AccessRank. Further work should therefore tease apart the respective roles of the interface and the prediction algorithm in file retrieval tasks.

Limitations

Despite BIGFile's strong performance benefits, we want to emphasize some limitations of our experiment.

File Hierarchies: Our pilot study was designed to inform the design of our simulations and experiment in terms of the depth and width of the hierarchy we should evaluate. Even though we combined the results from our pilot study with those in the literature, it is still possible that the hierarchies we used are not fully representative. A larger scale study is needed to capture user file structures and retrieval practices.

Potential Target Set Size: The simulations showed that BIGFileFast performs much better on a 10-item potential target set than on a 1000item potential target set. The latter is more realistic since users have thousands files and folders in their file systems. Larger target sets should therefore be tested to produce more robust findings.

Task Instruction: The task was initiated by showing a full path to the final target, which allowed users to compare the paths shown in the adaptive area with the instruction. In real life, recall of either the full path or the name of the final target is imperfect. Therefore, it is important to study how BIGFileFast performs in a more realistic setting, where navigation is combined with exploration.

In the next chapter, I discuss BIGnav and BIGFile as two applications of the Bayesian Information Gain (BIG) framework. I analyze their similarities and differences, discuss how BIG is relevant to other conceptual frameworks, and outline the opportunities for future work.

D I C U S S I O N A N D F U T U R E P E R S P E C T I V E S

In this chapter, I discuss: (a) The possible explanations for why BIG-File was preferred by the participants but not BIGnav, despite improved efficiency in both cases and (b) How BIG is conceptually related to other frameworks in the vein of human-computer partnership.

bignav vs. bigfile

Both BIGnav and BIGFile significantly improved interaction efficiency: up to 40% for BIGnav and up to 64% for BIGFile compared to their respective baseline. Yet the subjective experience in these two cases differ. In BIGnav, half the participants did not prefer BIGnav in comparison to the standard pan and zoom, but in BIGFile, all participants unanimously preferred BIGFile and ARFile, a split adaptive interface using AccessRank [START_REF] Fitchett | AccessRank: Predicting What Users Will Do Next[END_REF] for prediction, to the Finder-like list view, which was used as baseline.

The first plausible explanation is the way in which the BIG framework is used. In BIGnav, the goal was to illustrate the best case scenario. The feedback, which is a view in multiscale navigation, is searched from the entire information space, therefore providing absolutely maximal information. It means that the system can jump far away from the current view, causing confusion for the users. In BIG-File, however, the feedback, which includes the static area presenting the usual hierarchy and the adaptive area presenting the estimated shortcuts, is maximally informative only respective to in this given situation. If BIG were used at its best, the view in BIGFile would comprise folders and files from anywhere in the hierarchical structure. This requires users to have perfect knowledge of their file system, which is fairly unrealistic. Therefore, BIGnav maximizes the absolute expected information gain and BIGFile maximizes the expected information gain relative to the current context.

The second plausible explanation is that in BIGnav, since two consecutive views might be far apart, the users cannot anticipate what they will see next. This results in higher cognitive load as they need to interpret what the system has just done and reorient themselves before inputting the next command (see Fig. 40).

In contrast, in BIGFile, users have access to both the estimated shortcuts and the usual hierarchy so that they can choose which one to use: if the estimated items are not correct, they can always navigate the hierarchy in the usual way. Also, since contextual information is provided, users can navigate to a parent folder if the estimated path is only partially correct.

In both BIGnav and BIGFile, the system is actively probing users for more information. However, it seems that providing users with choices rather than making decisions for them is important. At a higher level, BIG fosters a form of collaborative interaction whereby system and user work together to achieve a common objective [START_REF] Pohl | Human-Computer Partnership in Decision-Support Systems: Some Design Guidelines[END_REF][START_REF] Terveen | Overview of human-computer collaboration[END_REF]. It combines information from the system's side with user's intentions in order to optimize decision under uncertainty. This concept is related to several human-computer collaboration and adaptation notions that I discuss in the next section.

collaboration and adaptation

While the notion of cooperative interaction between humans and computers is quite ancient [START_REF] Licklider | Man-Computer Symbiosis[END_REF], the concept of human-computer collaboration has emerged in HCI only recently [START_REF] Terveen | Overview of human-computer collaboration[END_REF]. In human-computer collaboration, two agents, a human and a computer, work together to achieve shared goals. A key aspect of collaboration is communication, for example to define goals, negotiate how to proceed and determine who will do what. Similar ideas can be found in mixed-initiative design [START_REF] Horvitz | Principles of Mixed-initiative User Interfaces[END_REF], human-computer partnership [START_REF] Pohl | Human-Computer Partnership in Decision-Support Systems: Some Design Guidelines[END_REF] and co-adaptation [START_REF] Mackay | Responding to cognitive overload: Coadaptation between users and technology[END_REF]. All these approaches suggest that great opportunities lie between systems that provide automatic services [START_REF] Horvitz | The Lumiere project: Bayesian user modeling for inferring the goals and needs of software users[END_REF] and systems where users are in full control [START_REF] Shneiderman | Designing the User Interface Strategies for Effective Human-computer Interaction[END_REF].

1. Mixed-Initiative Design. Mixed-initiative interaction is inspired by human-human interaction where two humans communicate to negotiate in a dialogue based conversation [START_REF] Je Allen | Mixed-initiative interaction[END_REF]. The observations are that we use a range of different actions in the course of a conversation such as evaluating and comparing options and suggesting courses of action. In mixed-initiative interaction, a human and an intelligent system, use a flexible interaction strategy where each agent can contribute to the task what it does best [START_REF] Je Allen | Mixed-initiative interaction[END_REF]. Early works such as Lookout [START_REF] Horvitz | Uncertainty, action, and interaction: In pursuit of mixed-initiative computing[END_REF] illustrates how the system and users collaborate to perform complex tasks. The system has a utility function where it evaluates the costs and benefits of offering the service, and takes control when the benefits are significant but leaves the users in control when the costs are high (Fig. 61).

Adaptation and appropriation occur together. In co-adaptive systems, users simultaneously adapt to the constraints imposed by the system and appropriate it in their own personal way. Rather than assuming that the designer is fully responsible for the 'user experience', co-adaptation suggests that users will always place their personal stamp on their use of the system. BIG leads to a reverse form of co-adaptation: while co-adaptation is about users adapting to new technology and also adapting it to their own needs, BIG adapts to users through its prior knowledge, which can change over time, and adapts users to its needs by prompting them constantly for information.

4. Recommender Systems. Another type of interactive systems that are worth mentioning is recommender systems. Recommender systems provide filtered information and seek to predict the "preference" that users would give to an item. They are used in a variety of areas including movies, music, news, books, research articles, search queries, social tags, and products in general [START_REF] Resnick | Recommender systems[END_REF]. Many of them use machine learning on massive data collected from users' history usage. Despite the progressively improved algorithms, recommender systems are still facing problems such as lack of accuracy [START_REF] Mcnee | Being Accurate is Not Enough: How Accuracy Metrics Have Hurt Recommender Systems[END_REF], lack of trust [START_REF] John | Trust in Recommender Systems[END_REF], and being "annoying" for not being aware of the real situation [START_REF] Adomavicius | Contextaware recommender systems[END_REF].

At first glance, BIGFile resembles a recommender system: it uses the user's history as priors and presents estimated shortcuts that users might be interested in. However, unlike recommender systems, in the BIG framework, the system is not trying to predict the most relevant items at the time, but tries to maximize the expected information gain. It might not necessarily show the items with the highest likelihood of being the target, but provides the approximately equiprobable items to estimate the final target. The simulations and controlled experiment in Chapter 11 have illustrated the effectiveness of the BIG approach in comparison to the best-of-breed prediction algorithm [START_REF] Fitchett | AccessRank: Predicting What Users Will Do Next[END_REF].

future perspectives

Despite the effectiveness of the BIG approach demonstrated by BIGnav for multiscale navigation and BIGFile for hierarchical file retrieval, a number of improvements for these two particular cases as well as several opportunities for the framework at large arise.

BIGnav:

In addition to the potential improvements that are mentioned in the discussion section of Chapter 9, namely using animation and combining BIGnav with standard pan and zoom, we can also regularize the search to compute the locally maximal expected information gain. As discussed earlier, BIGnav searches the entire information space, which can result in long-distance jumps between views. Regularizing the search area should therefore reduce the increased cognitive load. Moreover, we could allow users to stop the transition to the next view if they notice that BIGnav is going in the wrong direction, through more dynamic control.

BIGFile: As discussed in Chapter 11, even though BIGFileFast outperforms AccessRank [START_REF] Fitchett | AccessRank: Predicting What Users Will Do Next[END_REF], we would like to evaluate BIGFileFast with AccessRank with the stability parameter and potentially repeated user behavior. As BIGFileFast is a general algorithm that can be applied to navigate any hierarchical tree structure, its potentials should be explored in other applications. In addition, BIGFile should be evaluated in a longitudinal study to see whether and how it scales in realistic settings. BIG: BIG is a general framework that can be utilized in many interaction tasks (Fig. 24). Once the potential targets Θ and their probability distribution p(Θ), system feedback X, user input Y, and user behavior p(Y = y|Θ = θ, X = x) are modeled, one can always compute the actual information gain, or the information carried by the user input informing the computer of what she wants. In addition to maximizing the expected information gain (BIGnav) and leveraging the expected information gain (BIGFile), we can also combine the information criterion with other utility functions. Furthermore, the user behavior model can be personalized to account for individual behavior and can change over time.

BIG offers an operationalized framework that applies to humancomputer communication in general. The information-theoretic notion of information (entropy) is a value capable of measuring a startling array of things -from the flip of a coin, to a telephone call and to human-computer interaction. It helps us better understand how information is exchanged and how technology can play a more active and "intelligent" role in the interaction, leading to more effective human-computer partnerships.

-------"Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information?" -T.S. Eliot

Part III I N F O R M AT I O N -T H E O R E T I C M E A S U R E S F O R C H A R A C T E R I Z I N G I N T E R A C T I O N
This part builds on and extends the two previous parts. Users send information to the computer, therefore, an interaction task can be described using information-theoretic terms: how much information can be transmitted (entropy); how much information is successfully transmitted (mutual information); and what is the rate of successfully transmitted information (throughput).

I first introduce the information-theoretic measures to characterize an interaction task and demonstrate them in the context of command selection and text entry, comparing the information-theoretic notion of throughput with two existing definitions of throughput. By doing so, I further elaborate the benefits of using this framework to quantify the information transmission process from a user to a computer via an input device and an interface.

M O T I VAT I O N

Part i and part ii have shown a number of similar ideas from the lit- erature that describe an interaction task involving a user, a computer, an interface and an input device with information-theoretic terms:

• Pointing: Two different throughputs [START_REF] Stuart K Card | Evaluation of mouse, rate-controlled isometric joystick, step keys, and text keys for text selection on a CRT[END_REF][START_REF] Mackenzie | Fitts' law as a research and design tool in human-computer interaction[END_REF][START_REF] Zhai | Characterizing computer input with Fitts' law parameters -the information and non-information aspects of pointing[END_REF] have been proposed to characterize the performance rate in aimed movements in bits per second (Part i).

• Text Entry: Text entry techniques, such as Dasher [START_REF] David | Efficient communication with one or two buttons[END_REF], which features an average text entry rate of 4.8 bits per second (Part i).

• Full-body information capacity: Oulasvirta et al. [START_REF] Oulasvirta | Information Capacity of Full-body Movements[END_REF][START_REF] Sherman | User-generated Free-form Gestures for Authentication: Security and Memorability[END_REF] studied human control of continuous sensors and estimated throughput from 24 to 37 bits per second in a cyclical tapping experiment with a mouse (Part i).

• Sonic interaction: Berdahl et al. [START_REF] Berdahl | An Approach for Using Information Theory to Investigate Continuous Control of Analog Sensors by Humans[END_REF] focused on users controlling sound using continuous analog sensors and found that channel capacity for controlling a single, continuous sensor as high as 4 or 5 bits per second (Part i).

• Multiscale navigation & hierarchical file retrieval: BIGnav [START_REF] Liu | BIGnav: Bayesian Information Gain for Guiding Multiscale Navigation[END_REF] reduces uncertainty by 0.88 bits on average in the controlled experiment while BIGFile [START_REF] Liu | BIGFile: Bayesian Information Gain for Fast File Retrieval[END_REF] gains 1.27 bits per user input on average (Part ii).

Additionally, Roy et al. [START_REF] Roy | Glass+ skin: an empirical evaluation of the added value of finger identification to basic single-touch interaction on touch screens[END_REF] compared two command selection techniques on touchscreen (Fig. 62) and analyzed data in informationtheoretic terms1 . In the communication channel considered in their study, a user serves as the source of information with her hand as the information emitter, and transmits information to the system with the touch screen as the receiver of the coded message. The code shared by the source (the user) and the destination (the system) is the mapping of a set of touch events to a set of commands. Roy et al. hypothesized that the transmitted information levels off, as in absolute judgment tasks [START_REF] Miller | The magical number seven, plus or minus two: Some limits on our capacity for processing information[END_REF], and that throughput as a function of command entropy is bell-shaped (Fig. 63).

However, Guiard et al. [START_REF] Guiard | Not Just Pointing: Shannon's Information Theory as a General Tool for Performance Evaluation of Input Techniques[END_REF] only provide theoretical discussions, which need to be complemented by experimental evidence. They also do not illustrate how such theoretical measures can be applied to input methods beyond pointing.

Building on previous studies and extending Guiard et al. [90], I advocate for the use of information-theoretic measures to characterize an interaction task. I first introduce each element in this framework and illustrate how these measures can be used in tasks beyond pointing: command selection and text entry, comparing the informationtheoretic notion of throughput with two existing definitions of throughput. I demonstrate the benefits of using the informationtheoretic measures to quantify the information transmission process from a user to a computer via an interface and an input device, which provides a coherent description of the task and allows conducting controlled experiment without deliberately controlling error rate. I also outline other possibilities for using the theoretically justified measurements to investigate and design interaction.

The contribution of this part lies in illustrating the advantages of these measures and promoting the use of information theory as a unified tool to characterize interaction.

input entropy H(X)

The input received by the computer is modeled as random variable Y, which also takes values in {x 1 , x 2 , ..., x n }. Since there is noise Z, which can come from the user's head, motor movement, or computer decoding, the input Y received by the computer does not always equal the input X sent by the user, therefore, there are errors, represented by random variable E:

E =    0 if X = Y; 1 if X = Y. (40)
The probability of error P e = p(X = Y) representing the error rate has binary entropy:

H(E) = -P e log 2 P e -(1 -P e ) log 2 (1 -P e ). (41)

input entropy H(X)

Using Equation 1, input entropy H(X) captures how much information there is for the user to transmit. It is the maximum amount of information that could be transmitted in a given interaction scenario and it corresponds to the input size and the probability distribution of the inputs. The bigger the input size, or the more non-uniform the probability distribution, the higher the input entropy, and the more information can be sent.

A simple example considers a 4-item menu {"copy", "paste", "edit", "share"}. If the user uses all items equally, then the amount of information is maximum: H(X) = log 2 4 = 2 bits. If p(X = x) corresponds to {"copy" = 1 2 , "paste" = 1 4 , "edit" = 1 8 , "share" = 1 8 }, then the information in this context is H(X) = -4 i=1 p i log 2 p i = 1 2 (-1) + 1 4 (-2) + 1 8 (-3) + 1 8 (-3) = 1.75 bits. If there are more items, e. g. 8 equiprobable items, then the information is H(X) = log 2 8 = 3 bits. This information expresses how uncertain the computer is about the user's input. An extreme case would be {"copy" = 1, "paste" = 0, "edit" = 0, "share" = 0}, meaning that the user only accesses the item "copy", then the information transmitted from the user to the computer is H(X) = 0: the computer has zero uncertainty about the user's input and knows exactly what the user would like to do.

transmitted information I(X; Y )

Since there is noise Z in the channel, the received input Y by the computer does not always equal the intended input X. The successfully transmitted information is captured by mutual information (Equation 2).

For instance, in the aboved-mentioned case where all 4 items are equiprobable {"copy" =1 4 , "paste" = 1 4 , "edit" = 1 4 , "share" = 1 4 }, the information the user can transmit is 2 bits. In the following sequence of inputs ["copy", "paste", "copy", "paste", "edit", "share", "edit", "share"], the user made an error for the 5th input ("edit"): she wanted to input"share". Then we can compute mutual information I(X; Y) = 1.656 bits 1 . The transmitted information percentage is therefore I(X; Y)/H(X) = 1.656/2 = 82.8%. Roughly 82% of information gets successfully transmitted from the user to the computer. This measure of how much information the user actually transmits is similar to, but different from, the accuracy measure, which in this case is 7/8 = 87.5%.

transmitted information rate T P

Throughput captures the successfully transmitted information rate. It is computed by dividing the amount of successfully transmitted information I(X; Y) by the average time T required to transmit such information and is measured in bits per second: T P = I(X;Y) T (Equation 6).

For instance, if the user takes 1.5 seconds to complete the series of above-mentioned inputs on average, then we can compute the throughput T P = I(X; Y)/T = 1.656/1.5 = 1.104 bits per second. The transmitted information rate from the user is then 1.104 bits per second. Throughput quantifies the information transmission efficiency for an interaction task and combines speed and accuracy into one single measure. In addition to the individual speed and accuracy dimensions, throughput accounts for the speed-accuracy tradeoff. For instance, if we have one technique that transmits more information than the other but takes longer, we can compare the information transmission rates to decide which technique is better in terms of speed-accuracy tradeoff, or information transmission efficiency.

equivocation H(X|Y )

Equivocation H(X|Y) captures the information loss in the transmission process and describes the uncertainty the computer has about the user's intended target given what is the actual input. It is computed by the difference between how much information the user could have transmitted (input entropy) and how much information the user actually transmitted (transmitted information), as indicated by Equation 2. In the above-mentioned case, the equivocation H(X|Y) = H(X) -I(X; Y) = 2 -1.656 = 0.344 bits.

Equivocation gives much more information about how the user makes errors in comparison to the commonly used error rate P e . Imagine that the user wants to select the item "edit" 4 times in a row and consider the following 2 scenarios:

• She successfully selects "edit" twice and selects the left neighboring item "paste" and the right neighboring item "share" once each due to hand jitter.

• She successfully selects "edit" twice and hits two random items far away from the intended one.

The error rate P e is 0.5 in both cases but it is relatively easier to recover the intended input X from the actual input Y in the first case, therefore equivocation is lower in the first case than in the second. Equivocation not only illustrates the fact that information gets lost in the transmission process but also how it gets lost, therefore potentially helping to recover the true message. We will discuss the use of equivocation in intelligent text entry in Chapter 16.

advantages of the information-theoretic measures

Using these information-theoretic measures has several advantages:

• They provide a standard language to characterize an interaction task. Input entropy H(X) captures how much information can be transmitted; Transmitted information I(X; Y) captures how much information the user actually transmits; Equivocation H(X|Y) captures how much information gets lost in the transmission process and it is related to how the user makes errors; Throughput T P quantifies the information transmission efficiency and characterizes the speed-accuracy tradeoff.

• They are rooted in information theory with solid theoretical foundations. They (a) capture the distribution aspect of an interaction task, which has not been taken into account before; (b) they provide a more consistent description of the task when conditions are changed; and (c) they can be reasoned about using mathematical tools.

• In particular, throughput provides a way of avoiding the pitfall of the classic methodology of performance evaluation: to deliberately control experimental conditions in order to have error rates close to a reasonable minimum, usually below 4%, resulting in performance measures characterized only by speed. Such method is widely used in pointing (e. g. [START_REF] Mackenzie | Fitts' law as a research and design tool in human-computer interaction[END_REF]) and text entry (e. g. [START_REF] Maria Feit | How We Type: Movement Strategies and Performance in Everyday Typing[END_REF]). Throughput offers an accurate and principled way of combining the speed and accuracy dimensions of performance.

• Equivocation provides information about how users make errors. The more errors, the more random the errors, the higher the equivocation. On the other hand, the familiar error rate is a rather coarse measure of accuracy. Insensitive to possible patterns, error rates convey no information on the sorts of errors users are prone to make [START_REF] Attneave | Applications of information theory to psychology: A summary of basic concepts, methods, and results[END_REF]. Only by knowing how users make errors, can we learn from user behavior and design interaction with intelligent error correction approaches.

These measures can be applied and generalized as long as the following are known:

• X: A set of all possible messages (the intended inputs) that a user can transmit;

• p(X): The probability distribution of the intended inputs;

• Y: The actual inputs, which take values in X;

• T : The time required for a user to transmit the messages.

In the next two chapters, I demonstrate how to use these measures as well as their benefits in the context of command selection (Chapter 15) and text entry (Chapter 16). Then I discuss other opportunities for future work in Chapter 17.

C O M M A N D S E L E C T I O N

Selecting commands is one of the most common interactions in graphical user interfaces and menus are widely used for exploring and selecting them. Given their prevalence and importance, menus have motivated many studies in HCI, including more than 60 new menu techniques during the last two decades (see Bailly et al. [START_REF] Bailly | Visual Menu Techniques[END_REF]). Conceptually speaking, menus offer a set of options where selecting and executing one (or more) of the options results in a change in the state of the interface [START_REF] Martin | Handbook of human-computer interaction[END_REF]. They provide a straightforward approach to apply the information-theoretic measures as we know the input size X:

The items in a menu; p(X): The distribution of how each item is used; Y: The actual input on the menu and T : The time it takes to select a menu item.

This chapter demonstrates how the information-theoretic measures are used in the context of command selection. It includes:

• Simulations to explore how conditions affect the measures, comparing the information-theoretic notion of throughput with two existing definitions;

• Data reanalysis of existing command selection datasets to demonstrate the coherence of the information-theoretic notion of throughput in responding to the interaction task;

• A controlled study that investigates the information-theoretic measures with real users and reasons about their characteristics using information-theoretic concepts.

simulations

The goal of simulations is to explore how changing conditions affects the information-theoretic measures. Particularly, we compare the information-theoretic notion of throughput with two existing definitions of throughput, discussed in Part i Chapter 3, both of which only apply to pointing:

• Equation 14 from Mackenzie [START_REF] Mackenzie | Fitts' Throughput and the Speed-accuracy Tradeoff[END_REF].

• 1/b from Card et al. [START_REF] Stuart K Card | Evaluation of mouse, rate-controlled isometric joystick, step keys, and text keys for text selection on a CRT[END_REF] and Zhai [START_REF] Zhai | Characterizing computer input with Fitts' law parameters -the information and non-information aspects of pointing[END_REF].

controlled study

Since the notion of user-to-computer information transmission pro- cess is rooted in information theory, we can use mathematical tools to reason about the properties of the measures. This work is inspired by the study by Roy et al. [START_REF] Roy | Glass+ skin: an empirical evaluation of the added value of finger identification to basic single-touch interaction on touch screens[END_REF] where the information-theoretic measures are used to illustrate the differences between two interaction techniques when the number of inputs, which they call input vocabulary and command's entropy, increases. As Roy et al. [START_REF] Roy | Glass+ skin: an empirical evaluation of the added value of finger identification to basic single-touch interaction on touch screens[END_REF] focused on comparing these two techniques (Fig. 62), they hypothesized that the leveling-off effect of the transmitted information is similar to absolute judgment tasks3 [START_REF] Miller | The magical number seven, plus or minus two: Some limits on our capacity for processing information[END_REF], and that throughput as a function of command's entropy is bell-shaped (Fig. 63).

To investigate and analyze these phenomena theoretically, I designed and conducted an ad-hoc command selection experiment. This section reports on this experiment and provides a theoretical analysis for the above hypotheses. Twelve volunteers (1 female), age 23 to 31 (mean = 26.6, σ = 1.9), were recruited from our institution. All of them were right-handed and interacted with WIMP interfaces regularly.

The experiment was conducted on a Macbook Pro with a 2.7 GHz processor, 8 GB RAM and resolution at 227 pixels per inch. The software was implemented in Java and the experiment window was 600 × 400 pixels. The targets representing the commands were displayed at the top of the window as a row of adjacent rectangles. The total area covered by the targets was 256 pixels wide and 30 pixels high. The width of the targets depended on the experimental condition. A circle positioned 150 pixels down below the target area was used to reset the cursor position of each trial. A standard mouse was used with the same sensitivity for all participants.

Task, Stimulus and Design

In response to a visual stimulus, participants were instructed to click on the highlighted target command (Fig. 76 (a)) as fast and accurately as they could. If they correctly hit the target command, it turned green (Fig. 76 (b)). Clicking on a non-target command would turn it red. In both cases the trial was complete after a single selection. The cursor was reset at the same position at the start of each trial.

Information-Theoretic Analysis

We provide an information-theoretic analysis for (a) why mutual information should level off; and (b) why throughput should be a bellshaped function of the input entropy in the given scenario. As in Chapter 14, X is the intended input, Y is the actual input, Z is the noise in the information channel and E is the errors.

As Equation 2indicates, mutual information is the difference between the input entropy H(X) and equivocation H(X|Y) of the input given the output: I(X; Y) = H(X) -H(X|Y). The conditional entropy equivocation is a measure of the uncertainty about X knowing Y; but if we know Y, the uncertainty on the noise Z is the same as that on X, so we can rewrite Equation 2 as:

I(X; Y) = H(X) -H(Z|Y). (42)
Here H(X) = log 2 M. We now would like to bound the penalty term -equivocation -H(Z|Y) in the transmitted information. Since the knowledge of the output Y reduces the uncertainty on the noise Z (conditioning reduces entropy [34, Theorem 2.6.5]), we have:

H(Z|Y) H(Z). (43)
In other words, equivocation does not exceed the entropy of the noise. Thus it is the noise's entropy that penalizes the transmitted information.

In our experiment, users make errors as defined in Equation 40

since there remains no uncertainty on the noise Z if there is no error (E = 0). Combining the above, we find that the equivocation is bounded by:

H(X|Y) H(E) + P e × H(Z|E = 1). (45)
This is known in information theory as Fano's inequality [34, Theorem 2.10.1].

Here H(E) is given by Equation 41and is at most one bit (when P e = 0.5). Hence making errors penalizes the amount of transmitted information by at most one bit. However, considering the second term of Equation 45, the uncertainty on "wrong selections" H(Z|E = 1) incurs an additional penalty on the amount of transmitted information: how users make errors, not just the fact that they make errors, affects the amount of transmitted information.

In our case, errors are clustered near the actual target, hence the entropy of the noise is lower than if they were evenly distributed. The relationship between error rate P e and H(X|Y) observed from empirical data matches exactly the above illustration as shown in Fig. 77 (d).

We can now reason as follows:

• For small M: users do not tend to make errors, H(E) ≈ 0 and P e ≈ 0, therefore H(X|Y) is close to zero or remains very small when the error rate is low. So I(X; Y) increases with H(X) = log 2 M;

• For large M: we tend to have P e = 1, H(E) = 0, users cannot make a correct selection, but the errors are clustered around the target as in pointing tasks [START_REF] Wobbrock | An Error Model for Pointing Based on Fitts' Law[END_REF]. Doubling the number of commands from M to 2M adds 1 bit to the input entropy, but since the error area around the correct target is approximately the same physical size, the number of possible errors is also doubled. Hence the equivocation is also increased by 1 bit. In our data, the possible errors in condition 128 are 1-3 around the target while in condition 256 they are 1-5 around the target, which corresponds approximately to the same physical area. As a result, the amount of transmitted information I(X; Y) = H(X) -H(Z|Y) is not increasing any more and levels off as illustrated in Fig. 77 (a).

Combining this analysis with movement time, we can now turn to the theoretical analysis of the throughput T P:

• For small M: log 2 M is also small, and movement time is dominated by the intercept, hence can be considered as approximately constant. T P increases slowly with the input entropy;

• For large M: movement time grows linearly with log 2 M, and transmitted information I(X; Y) levels off. Hence T P gradually decreases as demonstrated in Fig. 77 (b).

However, we should distinguish the ceiling effect of transmitted information in our case from that in absolute judgment tasks [START_REF] Miller | The magical number seven, plus or minus two: Some limits on our capacity for processing information[END_REF]. Roy et al. claimed that they have the same characteristics but in our case, the errors made by users are around the target since they can see where it is, and therefore H(Z) is only a few bits. In absolute judgment tasks, since the key phenomenon is that human short-term memory has a limited capacity, one would expect that when the number of randomly ordered stimuli increases, H(Z) gets close to log 2 (M -1) as Y can take any value in {1, 2, . . . , M}. If this were the case, mutual information I(X; Y) should go down, instead of leveling off as I(X; Y) ≈ log 2 M -log 2 (M -1) at first order when M is very large. Since input entropy never gets very large in this type of tasks, the phenomenon is thus never observed. This would require further investigation in the context of absolute judgment tasks.

Summary

In summary, in command selection tasks, the amount of transmitted information gradually increases with input entropy until it reaches its capacity, and then levels off. Correspondingly, T P demonstrates a bell-shaped behavior, increasing to reach a maximum and then decreasing. This maximum (corresponding to an entropy of 5 bits, i. e. 32 commands in our experiment) provides the optimal input size for the given selection technique.

Following Soukoreff and MacKenzie [START_REF] Soukoreff | An informatic rationale for the speed-accuracy trade-off[END_REF], who argue that people are imperfect information processors, this experiment demonstrates that when input entropy increases, users tend to make more errors, which leads to the above-mentioned behavior of transmitted information and throughput. However, we should be aware that this is just one particular case because of the specific conditions of most HCI experiments including the one reported in this section:

• Participants are instructed to move as fast or as accurately as they can, sometimes both. We can imagine that if they could take their time to complete the task, the error rate would be always low, therefore the mutual information I(X; Y) would always increase with H(X).

• Since the stimulus is often visual, the errors are around the real target, which causes the leveling off effect of transmitted information. If errors were different, equivocation would be different, and the transmitted information would be different.

The theoretical formulations have shown that it is not just the fact that users make errors, but how they make errors, that affects the transmitted information, which is in turn tightly related to both the experimental design and the instructions to the users. In this case, equivocation H(X|Y) can help us better understand the nature of errors, which is not captured by the commonly used error rate P e , and potentially inform the design of error correction schemes. In the next chapter, I apply the information-theoretic measures to text entry, demonstrate the computation of conditional input entropy and discuss the effects of auto-correction.

16

T E X T E N T R Y I have outlined the statistical language processing concept in Part i, Chapter 5. Although text entry is modeled as communication over a noisy channel, the information-theoretic measures have not been widely adopted for describing text entry behavior. Instead, text entry is often characterized by words per minute (WPM), keystrokes per character (KSPC), Levenshtein string distance (LD), etc. (See Part i, Chapter 5).

This chapter attempts to apply the information-theoretic measures to text entry. It first introduces how to estimate these measures using conditional entropy and demonstrates the implementation of an intelligent statistical decoder for auto-correction. Then it presents a set of simulations where the information-theoretic measures are compared with the conventional text entry measures and the informationtheoretic notion of throughput is compared with the two other definitions of throughput. I also report on a pilot study with real users to explore the measures in a more realistic setting, as well as the effect of auto-correction. Note that the study in this chapter is still preliminary. It calls for further investigation.

conditional input entropy

Similar to command selection, we need to model the intended input X, the probability distribution p(X) describing X, the actual input Y and the time it takes to transmit the messages. However, unlike command selection, where one command changes the status of the interface, text entry involves typing a sentence that includes a string of letters and special characters. I therefore define a series of random variables X i that represent the character that a user is supposed to type at time i. Instead of considering all 26 letters and special characters, here I use a simplified example (Fig. 78): X i takes values in {a, b, c, d, " ′′ } where " " represents a space. Random variable Y i represents the character that a user actually types at time i. It also takes values in {a, b, c, d, " ′′ }. In Fig. 78, one can also use back to erase the incorrect characters or use next to transcribe the next sentence.

intelligent statistical decoder

As discussed in Part i, Chapter 5, text entry is an integral activity in our daily life, therefore there has been a number of intelligent text entry methods that strive to improve text entry rate [START_REF] Oulasvirta | Computational interaction[END_REF]. These methods infer or predict the user's intended text by exploiting redundancies in natural languages to increase users' ability to communicate as quickly and as accurately as possible.

Auto-correction is one of those methods. Its principal purpose is to correct common spelling or typing errors. If it corrects user input correctly, it saves time compared to doing it manually. On the other hand, if the algorithm corrects it in a wrong way, it is very costly as the user needs to correct the auto-correction before moving on2 .

The information-theoretic measures can be used to investigate the effect of auto-correction. To do so, I implemented a substitution-only statistical decoder using the token passing method [START_REF] Oulasvirta | Computational interaction[END_REF][START_REF] John | Token passing: a simple conceptual model for connected speech recognition systems[END_REF] on the 7-key keyboard (Fig. 78). Since text entry is inherently noisy and uncertain, text entry decoding approach aims to find the most probable message Y given the intended message X. This conditional probability p(y|x) is computed from Bayes' rule:

p(Y = y|X = x) = p(X = x|Y = y)p(Y = y) p(X = x) .
The most probable message Y is then arg max

Y [ p(X=x|Y=y)p(Y=y) p(X=x)
].

Since the decoder is only attempting to identify the message that maximizes the posterior probability, the denominator is just a normalization constant and will be invariant under the search. It can therefore be ignored: arg max Similar to Fig. 20 in Part i Chapter 5, we decode an observation sequence of length i by starting with a single initial token, which predicts the empty string ǫ with 1.0 probability for observing zero observations (Fig. 80).

By adjusting the pre-transcribed sentences, we can simulate two scenarios: (a) a wrong input is auto-corrected to a correct one and (b) a correct input is auto-corrected to an incorrect one. Both cases will be illustrated next with simulations.

keyboard simulations

In this section, I use the 7-key keyboard example (Fig. 78) to explore the characteristics of the information-theoretic measures. The height and the width of each key are adjustable and the language model L is used. Transmitted information before starting the simulation is set to 1. Conventional text entry measures including words per minute (WPM), error rate, and keystrokes per character (KSPC) are computed the same way as in Part i Chapter 5. Since Fitts' law is also used to model pointing behavior in text entry, we can compare the information-theoretic notion of throughput with the two definitions of throughput from Chapter 15: T P m = ID e /MT where ID e is the effective index of difficulty and MT is movement time (Equation 14) and throughput T P z = 1/b where b is the slope of Fitts' law. As in Chapter 15, Fitts' law constants are a = 0.37 and b = 0.13 (from [START_REF] Cockburn | A Predictive Model of Menu Performance[END_REF]).

The pointer is set at the center of the next key at the beginning of the simulation.

Three settings are investigated:

1. The size of the keys is varied and there are no errors.

2.

There are uncorrected errors.

3. An intelligent decoder is in the loop.

No Errors

In the first simulation, I assume that users perfectly transcribe the intended sentence, but use different key sizes, therefore I compare movement times. Three cases are considered: (a) small keys (width × height = 4 × 2); (b) regular keys (width × height = 5 × 5) and (c) large keys (width × height = 10 × 10) (Fig. 82). Obviously, it is more difficult to type with small keys (a) than with large keys (c). When no errors occur, the information-theoretic notion of throughput should be higher with large keys (c) than with small keys (a). The intended sentence is "ad cb aac" as shown in Fig. 82. The simulation ran 10 perfectly transcribed sentences for each of the three cases along with the time for each key press.

In the first case, since all 3 errors are the same, the equivocation is low and there is a certain probability for receiving "b" when it is supposed to receive "a". In contrast, in the second case, "b", "c" and "d" are received once each when "a" is expected, so it is difficult to recover the intended input from the received characters. The equivocation is high in the second case, and the transmitted information is low compared to the first case. On the other hand, how the errors are made is not reflected in the classical measures (Table 11). Fig. 83 (b) also shows the comparison among the three measures of throughput and we can see that neither T P m nor T P z account for the randomness of errors.

Auto-correction

We can also use the information-theoretic measures to investigate the effect of auto-correction on text entry. I simulated 3 scenarios using the keyboard with regular-sized keys (Fig. 82 (b)):

1. There is no intelligent decoder in the loop: users mistype a character, use back key to erase it and retype the correct one;

2. There is an intelligent decoder in the loop: users mistype a character, which is then auto-corrected correctly by the autocorrection method;

3. There is also an intelligent decoder in the loop: users correctly type a character, which is then auto-corrected incorrectly so that users need to correct the auto-correction and then retype the correct character.

Summary

These simulations demonstrate that the information-theoretic measures provide consistent results compared with the conventional text entry measurements. When there are no errors, the informationtheoretic notion of throughput T P i illustrates the speed dimension, similar to words per minute (WPM). When errors are involved, T P i accounts for the randomness of errors, which is not captured by the classical error rate. The information-theoretic measures also provide a way to examine the effect of auto-correction, namely that having an incorrect auto-correction is more costly than correcting errors manually while having a good decoder keeps the text entry rate constant. By contrast, the other two definitions of throughput do not account for the randomness of errors, nor auto-correction in the loop, nor the speed-accuracy tradeoff, as will be demonstrated in the next section.

pilot study

To investigate the information-theoretic measures on text entry in a more realistic setting, I recruited nine participants, age between 24 and 33 (mean = 27.2, σ = 2.1) from our institution. All of them were right-handed, interacted with WIMP interfaces regularly and were familiar with auto-correction methods. The pilot study was conducted on a Macbook Pro with a 2.7 GHz processor and 8 GB RAM. The program (Fig. 78) was implemented in Python 3.6 using the Tkinter GUI toolkit 3 . The same language model L and the keyboard with regularsized keys (Fig. 82 (b)) were used to allow the comparison between the results from this study and those of the simulations. A standard mouse was used with the same sensitivity for all participants.

Three conditions were considered:

1. No auto-correction. Intended sentence: "ad cb aac" (as in Fig. 84);

2. A good decoder that corrects errors correctly. Intended sentence: "cba dda b" where all three 'words' will be correctly corrected if wrongly transcribed;

3. A bad decoder that corrects the right characters wrongly. Intended sentence: "b cd aadc" where the last 'word' will be incorrectly corrected even if correctly transcribed.

Before each condition, participants spent some time familiarizing themselves with the interface. They were then instructed to transcribe as fast and as accurately as possible. Note that unlike most text entry experiments, e. g. Feit et al. [START_REF] Maria Feit | How We Type: Movement Strategies and Performance in Everyday Typing[END_REF], we do not control error rate, so as to assess the speed-accuracy tradeoff.

In the first condition, when auto-correction is not involved, participants corrected incorrectly transcribed characters (corrected error rate 5%), resulting in transmitted information equal to input entropy. Since there are corrections, which usually involves correcting the incorrect character only, KSPC is greater than but close to 1. In the second condition, when a good decoder is in the loop, participants did not need to correct errors themselves. However one participant typed a wrong character, which was automatically corrected, but he then deleted the correction and retyped it (KSPC averages 1.06). In the third condition, when a bad decoder is used, the error rate is the highest (14%). This is due to both uncorrected errors and corrected errors. Seven participants saw the incorrect corrections, corrected them and then retyped the correct character. Two participants even deleted and retyped the whole word (KSPC averages 1.54) (Fig. 86 (b)). Another two participants did not see the incorrect auto-correction, so the errors were left in the final transcribed sentence, leading to uncorrected errors. This is also reflected in the information-theoretic measures. When a good decoder or no decoder is involved, the transmitted information equals input entropy as all errors have been corrected. This is in contrast to the condition when a bad decoder is involved: only 88% information is successfully transmitted. A good decoder also saves error correction time, therefore has the highest throughput than no autocorrection condition, which has higher information transmission efficiency than when a bad decoder is in the loop. These results echo the previous simulations where correcting auto-correction is very costly. On the other hand, the other two definitions of throughput exhibit opposite behaviors (Fig. 86 (a)). As in Chapter 15, this is due to the fact that pointing is no longer a dominating element in this task, therefore the two pointing-oriented definitions of throughput can no longer capture the information transmission efficiency.

summary

This is but a first step to demonstrate how the information-theoretic measures can be applied in the context of text entry, which is one of the most common but complex tasks that we encounter on a regular basis. I showed how to compute each measure using conditional entropy based on a language model, compared these measures with conventional text entry measures as well as the two definitions of throughput, and discussed the effect of auto-correction on text entry. Results from simulations as well as the pilot study show several benefits of using the information-theoretic measures to characterize text entry:

• The information-theoretic measures show consistent results compared to the conventional text entry measurements. Also, the computation of these measures is easy due to the availability of statistical language processing;

• Using the information-theoretic notion of throughput, researchers do not need to deliberately control error rate when running experiments, which offers a more holistic picture of the speedaccuracy tradeoff;

• Using equivocation, we can also better exploit the distribution of errors, and by understanding it, we can improve the text entry rate by designing better auto-correction and other decoding approaches.

The studies reported in this chapter are preliminary and have several limitations. More work is needed, for instance, to investigate the role of the language model in estimating input entropy and how to design more intelligent decoders by incorporating equivocation. In the next chapter, I discuss these limitations and outline future opportunities using the information-theoretic measures.

D I C U S S I O N A N D F U T U R E P E R S P E C T I V E S

In this chapter, I discuss the two use cases in Chapter 15 and Chapter 16 respectively, summarizing their advantages as well as limitations. I then outline opportunities for future work using informationtheoretic measures to characterize human-computer interaction.

command selection & text entry

In order to compute the information-theoretic measures, we need to have a set of intended inputs X associated with a probability distribution p(X) describing the use of each input, as well as the actual inputs Y received by the computer and the time T to transmit these inputs (messages). As discussed in Chapter 15, command selection provides a straightforward scenario to examine these measures. It does not require measuring more than what we normally measure: a series of experimental stimuli, the actual user inputs and the time to complete the task. However, information theory lets us explore the interaction task and interpret the results in terms of communication efficiency. For speed, we use the traditional measure; for error, we look at equivocation & information transmission percentage instead of error rate; for speed-accuracy tradeoff, we look at throughput (information transmission efficiency). These measures had not been systematically considered before.

As shown in Chapter 15, equivocation tells us not only that there are errors in the communication channel, but also how users make errors, which is tightly related to the experimental setting and the instruction given to the participants. Throughput provides information about the rate at which information can be transmitted using a certain input technique and/or interface. For instance, in Fig. 71 (a), the information-theoretic notion of throughput shows that the semantic organization of a 16-item menu leads to a higher information transmission rate than an alphabetic organization, whereas in Fig. 71 (b), the traditional time measure shows the same effect for both organizations. In this case, throughput can help interaction designers make more informed decisions. Additionally, throughput provides a bigger picture of the speed-accuracy tradeoff, helping us better understand human behavior in various conditions.

Text entry in Chapter 16 is another scenario that benefits from applying the information-theoretic measures. First, Shannon himself measured the entropy of the English language right after the introduction of information theory; Second, it is a tradition to consider text entry as communication and language as information (bits); Third, the redundancy in languages naturally provides a probability distribution; Fourth, given the complexity of measuring text entry, a common practice for text entry experiments is to control error rate under, e. g. 4%, therefore only the speed dimension is considered when evaluating new text entry techniques or intelligent decoding methods. In this respect, information theory seems appropriate to measure text entry performance. Chapter 16 demonstrates how to use conditional entropy extracted from a language model to measure input entry, as well as the transmitted information to compute throughput. With the 7-key keyboard, I explored various characteristics of these measures, demonstrating their coherence compared to conventional text entry measures and their benefits over the other two definitions of throughput.

There are certainly many other aspects of text entry that I did not cover. First it should be applied to real text entry experiments comparing the information-theoretic measures with conventional metrics without controlling error rate. To do so, we need to use a real language model and a more sophisticated language modeling scheme. For instance, Weir et al. used a language model trained from Twitter, which has 94.6 M sentences, 626 M words, and 2.56 G characters, as well as a character-based 7-gram language modeling scheme [START_REF] Weir | Uncertain Text Entry on Mobile Devices[END_REF]. Furthermore, as mentioned in Part i, Chapter 5, there are at least 4 types of errors in text entry. I only considered the case of substitution and have not yet explored how omission, insertion or transposition affect the information-theoretic measures. Finally and perhaps most importantly, since equivocation provides information about how errors are made, it can certainly be used to improve intelligent language decoding such as auto-correction and auto-completion.

future work

Command selection and text entry are merely two examples among many where we can apply the information-theoretic measures to characterize the interaction task. I demonstrated its advantages over conventional metrics and I hope that it will inspire researchers to study other tasks. Having a standardized language to examine interaction across devices, platforms, user groups and domain would indeed be most beneficial to the community at large. We can consider any type of interaction is a way for the user to transmit information to the computer. Similar to all communications, the goal is to improve the communication rate, to have more information delivered and to reduce the other party's (here the computer) uncertainty about what we want to express. Information theory provides a way to systematically investigate and characterize interaction1 . There is still a lot we can explore, e. g. how to model continuous inputs such as gestures and how to model intended inputs at all if they are not so straightforward to model. For instance, how do we know what users want to write in daily life? Additionally, what is the relationship between transmitted information percentage I(X; Y)/H(X) and the commonly defined accuracy rate 1 -P e ? Can they be rationalized using other information-theoretic concepts in addition to Fano's inequality? To have closed-loop interaction, rather than the current one-directional scheme, how can we involve feedback, which plays a key role in determining the user's subsequent input? The full spectrum of conceptual and practical benefits of Shannon's information theory seems to have a lot to offer to HCI. I hope the communication standpoint supported by ACM SIGCHI Curriculum can truly become human-computer interaction guidelines. This thesis strives to bridge the gap between information theory and HCI by taking the stance that human-computer interaction can be considered as a communication process and therefore be characterized using information-theoretic concepts. While the notions that humans are capable of transmitting and exchanging information, that we are bound by some information capacity, etc. have been around even before information theory was introduced, to the best of my knowledge, this thesis is the first attempt at clarifying the scientific position of information theory in HCI.

In Part i, I introduced some basic information theory concepts and a historical walkthrough of how information theory influenced experimental psychology and HCI. It is rather interesting today to see how experimental psychologists were swept by information theory back in the 1950s. Indeed, information is everywhere and is vital for many aspects of our lives. One can find many quotes about how information is the key, everything is achievable when we are armed with information. So think about what can be done when information is quantifiable. In the 1950s, psychologists were fascinated by the ability to quantitatively measure how we transmit/process information. However, information, or rather entropy, which is a measure of randomness in information theory, has confused many brilliant minds at the time. Information in information theory has absolutely no semantic meaning and is entirely computed by the probability distribution of a random variable. Among many applications from psychology, Fitts' law and Hick's law are some of the most important and relevant ones to humancomputer interaction. Fitts' law has been used to model pointing behavior, one of the most prevalent interactions, and Hick's law has been used to model reaction time in response to a number of stimuli. While these two laws are the closest link between information theory and HCI, both are subject to several misunderstandings. In Part i, I showed that there are still a number of remaining questions related to Fitts' law after 60 years of empirical validation and it is necessary to rigorously examine them from an information-theoretic perspective. Moreover, the contradictory position of Hick's law is probably not due to the fact that the law is wrong, but to how we understand and implement it. I showed that it has been used in many different contexts where it is not supposed to be at work. More importantly, rather than stamping a phenomenon with Hick's name, we can better benefit from having a well-defined taxonomy where different types of measured time are described using correctly formulated mathematical representations.

Chapters 1, 2, 3 and 4 in Part i explained the elements of information theory and how they were understood and applied in experimental psychology, with the goal of understanding information theory and its applications from a historical perspective. By doing so, we can learn from prior studies and avoid making the same mistakes. By examining how relevant Hick's law is to HCI in Chapter 4, I illustrated that it is important to understand what we are measuring when we measure time in controlled experiments. I showed that several time measures often overlap and it is difficult to tear them apart. Therefore, we should be careful when describing time measures in experiments. Chapter 5 examined the recent studies where information theory plays a role with the goal of inspiring future work. Finally, I believe that there is a great deal to learn from psychology, namely the paradigm of stimulus-response compatibility. Since psychology is tightly related to human-computer interaction and we cannot design or study new interfaces or interaction techniques without understanding users, we should probably take better advantage of what has been learned by Psychology and how it can be applied in HCI.

After clarifying the indirect link between information theory and HCI in Part i, Part ii and Part iii strived to provide novel perspectives on the direct link between information theory and HCI. Part ii introduces a Bayesian Information Gain framework based on Bayesian Experimental Design using the criterion of mutual information to quantify the information sent by the user to the computer and reduce the computer's uncertainty about the user's goal. Information is defined in terms of the computer's knowledge about what the user wants. At the beginning of the interaction, the user has a goal and the computer has some uncertainty about that goal. This uncertainty is represented by the computer's prior knowledge, expressed in a probabilistic model. When providing feedback to the user, the computer takes user input and updates its knowledge about what the user is looking for. Therefore, the information carried by the user input is defined as the knowledge gained by the computer about the user's goal. I showed two applications of BIG to multiscale navigation (BIGnav, Chapter 9) and hierarchical file retrieval (BIGFile, Chapter 11). In both cases, one can compute the information gained by the computer even when using conventional interaction techniques. I showed that often times the input sent by the user does not carry information to reduce the computer's uncertainty. By presenting the user with a view where the expected information gain is maximized (in the case of BIGnav) or leveraged (in the case of BIGFile), the computer can gain much more information from each user input, therefore locating what the user is looking for with a higher rate of information gain.

Bayesian Information Gain is a general framework that can be applied to many interaction tasks. In order to compute information, one needs to model Θ, which represents the potential intended targets; p(Θ), which represents the computer's prior knowledge about the user's goal; X, which represents the possible system feedback and Y, which represents the possible user input. Often times these three random variables take values in a very large set, therefore the cost of computing the optimal feedback is potentially very high. I showed that discretizing the system feedback Y as well as user input Y reduced the sets, and I introduced a suboptimal algorithm to make the computation tractable. I also proposed several ideas to make interaction more comfortable and intuitive so as to increase both communication efficiency and usability.

Conceptually speaking, BIG is related to several other frameworks such as mixed initiative systems, human-computer partnerships, and co-adaptation. BIG enables collaboration between the user and the computer to achieve shared goals and this collaboration is not possible without contributions from both parties. In line with all these approaches that suggest that great opportunities lie between systems that provide automatic services and systems where users are in full control, BIG combines human intelligence with machine power to reinvent interaction.

BIG is also an instance of probabilistic interface. Similar to other probabilistic interface architectures that treat user input as an uncertain process, BIG uses a user behavior model to represent the ambiguity of user input for the computer. In conventional settings, there is no information-theoretic uncertainty for the user regarding the computer's behavior. However, when presenting a feedback to the user, the computer is uncertain about what the user will do. BIG offers non-deterministic system feedback and user interfaces that leverage probabilistic models to better infer user intent by maximizing/leveraging the expected information gain. It opens the door to a wide range of "BIG" applications and also a new era of probabilistic interaction.

Part iii extends these concepts and applies information theory to characterize an interaction task at large. It is based on the idea that since the user sends information to the computer, we can use information-theoretic concepts to describe the maximum amount of information that can be transmitted, the actual amount of information that gets transmitted and the transmission efficiency. The informationtheoretic measures provide several advantages over the conventional speed and accuracy metrics:

1. They allow HCI researchers to investigate the full spectrum of speed and accuracy without deliberately controlling one dimension due to the lack of tool to combine the two (throughput);

2. The information-theoretic notion of equivocation provides much more information about how errors are made in the interaction, which can help design intelligent error correction approaches.

I demonstrated the advantages of using the information-theoretic measures in command selection (Chapter 15) and text entry (Chapter 16). Command selection provides a straightforward perspective on how to compute X: The intended input, which is the possible commands; p(X): The probability distribution of these commands describing their history of use; Y: The actual input, which is the actual commands selected by the user; T : The time to select these commands. I illustrated that the information-theoretic notion of throughput is more consistent than the two existing definitions of throughput and can be rationalized using mathematical tools. Since it provides a rigorous way to combine speed with accuracy, it can help make more informed decisions in terms of speed-accuracy tradeoff for interaction techniques and interfaces.

Text entry is another case where it is possible to apply the information-theoretic measures for the reasons that (a) the redundancy in natural languages provides the probability distribution for the input and (b) Text entry behavior is complex and difficult to capture therefore error rate is usually deliberately controlled by the experimenter. With the information-theoretic measures, one does not need to control the error rate but instead can fully explore the interaction between speed and accuracy as well as take further advantage of how errors are made to devise intelligent text entry methods.

Using these information-theoretic measures to characterize interaction also provides a direct link between information theory and HCI. The communication between the user and the computer is truly modeled as a channel and we characterize how much information can be transmitted and how much information is actually transmitted. To compute these measures, one does not need to collect more data than is already done. Information transmission efficiency (throughput) provides a standardized way to assess human-computer interaction. Overall, these measures provide a standard language to characterize interaction.

looking forward

This thesis is a first step towards using information theory as a unified tool for understanding and designing human-computer interaction & communication. It is just the tip of the iceberg: there is still a great deal to explore and I hope to have demonstrated that the community can benefit from such theoretically sound methods.

I have demonstrated how we can learn from the past, presented a Bayesian Information Gain framework to quantify the information sent by the user to the computer and illustrated the advantages of using information-theoretic measures to characterize interaction. Several avenues of future work present themselves: applying BIG to the design or redesign of other interactions, refining the framework by incorporating user behavior in real time, and combining BIG with other frameworks to construct the utility function. More generally, I see great potential in exploring and applying the information-theoretic measures to other interaction tasks, particularly those with continuous inputs and taking further advantage of the notion of equivocation to devise more intelligent systems. In short, there is a vast space of open research, and I hope this human-computer communication standpoint can truly become a standard to guide future interaction design.

-------"My greatest concern was what to call it. I thought of calling it 'information', but the word was overly used, so I decided to call it 'uncertainty'. When I discussed it with John von Neumann, he had a better idea. Von Neumann told me, 'You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, no one really knows what entropy really is, so in a debate you will always have the advantage'."

-Claude Shannon Purpose of the study: We want to compare three different interfaces for file retrieval and see which one is faster and which one is liked the best.

2. Procedures to be followed: If you agree to participate, we will introduce the three interfaces to you and then ask you to perform a series of tasks. You will begin by filling out a short questionnaire about your experience with navigation-based file retrieval. Next, we will ask you to sit in front of a laptop and find a comfortable position to perform the task. We will show you how the interfaces look like and let you try them out. For each interface, we will display a stimulus which indicates a folder or a file and ask you to navigate to this target accordingly. At the end, we will ask you to fill out another short questionnaire and ask you your opinions about the interfaces. We will record the time you spend to find each target, as well as your cursor movements and eye movements.

Risks and Discomforts:

We do not believe you will experience any risks by participating in this study, beyond those you encounter in daily life. However, you may find the tasks to be repetitive, slightly tiring, uncomfortable or boring.

Benefits:

You may find the interfaces useful for accessing your files and folders.

Duration:

The complete study, including pre-and post-questionnaires will take about 60 minutes.

Confidentiality:

Your participation in this research is confidential and your data will be anonymized. This paper form is the only link between your name and your participant ID, and will be stored in a locked office. The researchers listed below will be able to review only the anonymized data, which will not include any personally identifiable information.

Right to ask questions:

Please contact Wanyu Liu (wanyu.liu@telecom-paristech.fr) with questions, complaints or concerns about this research. Questions about research procedures and future publications will be answered by the research team. You may also contact the Inria COERLE ethics board if you feel this study has harmed you in any way: http://www.inria.fr/institut/organisation/instances/coerle/composition 8. Voluntary Participation: Your decision to be in this research is entirely voluntary. You do not have to answer the questions, and you may ask us to withdraw your data from the analysis, up to two months after the study. You may stop at any time, without giving a reason, and there is no penalty for withdrawal. You will not be paid for taking part in this study.

CONSENT:

You must be at least 18 years to participate in the study. If you agree with the above, please sign your name and indicate the date. You may ask for a copy of this consent form.

Contact:

Principal investigator: Michel Beaudouin-Lafon -mbl@lri.fr Professor Co-investigator:

Wendy Mackay -mackay@lri.fr Professor Co-investigator:

Joanna McGrenere -joanna@cs.ubc.ca Professor Key Contact: Wanyu Liu -wanyu.liu@telecom-paristech.fr PhD Student

The nature and purpose of this research have been sufficiently explained and I agree to participate in this study. I understand that I am free to withdraw at any time without incurring any penalty.

1

 1 Figure 1An overview of this thesis. . . . . . . . . . . . . Figure2Shannon's communication scheme. . . . . . . . Figure3Noiseless binary and noisy channel. . . . . . . Figure4Schematic diagram of the choice-reaction time as a model of communication. . . . . . . . . . . Figure5Hick's and Hyman's data. . . . . . . . . . . . . Figure6Channel capacity in absolute judgement tasks. Figure7Schematic diagram of human motor system as a model of communication. . . . . . . . . . . . Figure8Results of Fitts' 4 experiments. . . . . . . . . . Figure9Card, Moran and Newell's description of Fitts' law. . . . . . . . . . . . . . . . . . . . . . . . . . Figure10Comparison between ID(ε) and ID e . . . . . . . Figure11Movement data as a function of ID in a wild study. . . . . . . . . . . . . . . . . . . . . . . . . Figure12Movement time, accuracy rate and throughput accross 3 conditions. . . . . . . . . . . . . . . . Figure13Guiard and Rioul's WHo model describing speedaccuracy tradeoff of aimed movement. . . . . . Figure14Card, Moran and Newell's description of Uncertainty Principle. . . . . . . . . . . . . . . . . Figure15Reaction time as a function of stimulus "information" in different tasks. . . . . . . . . . . . . Figure16Time measures in controlled experiments. . . . Figure17Reanalysis of data from Roy et al.[START_REF] Roy | Glass+ skin: an empirical evaluation of the added value of finger identification to basic single-touch interaction on touch screens[END_REF] and Liu et al.[START_REF] Liu | BIGnav: Bayesian Information Gain for Guiding Multiscale Navigation[END_REF]: reaction time as a function of stimulus uncertainty. . . . . . . . . . . . . . . . Figure18xT design guideline based on data categorization and xT function. . . . . . . . . . . . . . . . Figure19Writing in Dasher. . . . . . . . . . . . . . . . . . Figure20Token passing strategy. . . . . . . . . . . . . . . Figure21Information capacity of repeated movements. . Figure22Model of a user controlling sound using continuous analog sensors. . . . . . . . . . . . . . . Figure23Pointing without a pointer. . . . . . . . . . . . . Figure24The Bayesian Information Gain (BIG) framework. Figure25Multiscale representations and interactions. . . Figure26Space-scale diagrams. . . . . . . . . . . . . . . . Figure27Fitts' law in multiscale navigation. . . . . . . . Figure28GravNav and Content-aware scrolling. . . . . . Figure29"The River Analogy" to assist 3D navigation. .

Figure 158 Figure 3

 1583 Figure Uncertainty and information gain in BIGFile experiment. . . . . . . . . . . . . . . . . . . . . . 129 Figure NASA TLX scores and overall preference in BIGFile experiment. . . . . . . . . . . . . . . . . 130 Figure Mixed-initiative system Lookout. . . . . . . . . 135 Figure Technique Glass and Glass+Skin with finger identification. . . . . . . . . . . . . . . . . . . . . . . 142 Figure Transmitted information and throughput in the experiment of Glass and Glass+Skin. . . . . . . 142 Figure The decomposition of Shannon's entropy. . . . 143 Figure Information-theoretic measures for examining human-computer interaction as information transmission from the user to the computer through the channel interface. . . . . . . . . . . . . . . . 145 Figure Simulation settings with three variables. . . . . 152 Figure Simulation results when error rate increases. . 153 Figure Simulation results when item height and starting distance are changed. . . . . . . . . . . . . 154 Figure Simulation results when the number of items increases. . . . . . . . . . . . . . . . . . . . . . . 155 Figure Simulation results when distribution is changed.156 Figure Information-theoretic notion of throughput and selection time for 3 organizations and menu lengths. . . . . . . . . . . . . . . . . . . . . . . . 157 Figure Three definitions of throughput in alphabetic, semantic and unordered menus. . . . . . . . . 158 Figure 3 distributions with names, multiset of item frequencies, the r-squared and pairwise distance.159 Figure Information-theoretic notion of throughput and selection time for 3 distributions. . . . . . . . . 159 Figure Three definitions of throughput in 3 distributions. . . . . . . . . . . . . . . . . . . . . . . . . 160 Figure Experimental condition for the command selection task. . . . . . . . . . . . . . . . . . . . . 162 Figure Experimental results in the command selection task. . . . . . . . . . . . . . . . . . . . . . . . . . 163 Figure A toy keyboard with 7 keys. . . . . . . . . . . . 168 Figure Probability of individual character and Conditional probability of pairs of characters in language model L. . . . . . . . . . . . . . . . . . . 169 Figure A substitution-only decoder. . . . . . . . . . . . 171 Figure A decoder for 'a' and 'b'. . . . . . . . . . . . . . 171 Figure Three keyboards with keys in different sizes: small, regular and large. . . . . . . . . . . . . . 173 Figure Comparison among three measures of throughput when key size and error type changes. . . 174

  transcribed the sentence in 4 seconds, then we can compute the measures: Words per Minute(WPM) = 21 ÷ 5 ÷ 4 × 60 = 63 Not Corrected Error Rate = 1 ÷ 22 × 100% = 4.5% Corrected Error Rate = 1 ÷ 22 × 100% = 4.5% Total Error Rate = 2 ÷ 22 × 100% = 9.0% Keystrokes per Character (KSPC) = 23 ÷ 21 = 1.09 Levenshtein String Distance (LD) = 1

7 .

 7 I(Θ; Y|X = x) is the mutual information between what the user wants and what she provides as input when seeing X = x. It is the difference between two uncertainties 1 :

θ b and b -a > 2 0 a θ b and b -a 2 p

 22 (Y = • | Θ = θ, X = [a, b]) = 1 a θ b and ba 2 0otherwise.

Figure 37 :

 37 Figure 37: Means and confidence intervals for TCT by DISTR.

Factors

1 Receive user input Y = y 2 P(Y=y|X=x) 3 for 4 Compute 7 A

 12347 Update the probability distribution of Θ (Bayes rule): P(Θ = θ|X = x, Y = y) = P(Y=y|Θ=θ,X=x)P(Θ=θ) all the combinations A of N nodes that are below the current folder F in the hierarchy do IG(S A) = I(Θ; Y|X(S A))= H(Θ) -H(Θ|X(S A), Y) // I is mutual information and H is entropy5 if IG(S A) > IG max then 6 IG max = IG(S A) max = A 8 return A max

11. 6 FACE × 2 LEVEL × 2

 622 resultsand the information gain after each input. We collected 3 INTER-Session (20 Selections each) × 18 Participants = 4320 trials.

15. 3 . 1

 31 Data Collection 15.3.1.1 Participants and Apparatus

  , and we can use the chain rule [34, Theorem 2.2.1]: H(Z) = H(Z, E) = H(E) + H(Z|E) where: H(Z|E) = P e × H(Z|E = 1) + (1 -Pe) × H(Z|E = 0) = P e × H(Z|E = 1).

Y

  [p(X = x|Y = y)p(Y = y)] where p(X = x|Y = y) is the likelihood of the input message X = x given a particular hypothesis for Y = y and p(Y = y) is the prior probability of the message Y = y without taking the input message into account. The objective of the decoder is therefore to identify the most probable hypothesis for the observation sequence Y = {Y 1 , Y 2 , ...Y i }.

-

  ------"If you just communicate, you can get by. But if you communicate skillfully, you can work miracles." -Jim Rohn C O N C L U S I O N

* 3 .* 4 .

 34 Thank you again for participating in the experiment. Please take a few minutes to fill out the survey. We appreciate your feedback. * 1. Participant ID: ________________________________________ * 2. How would you evaluate your performance in two conditions? How would you evaluate your comfort level in two conditions? Which technique would you prefer? • Standard navigation • Information theoretic navigation * 5. Why do you prefer this technique? _______________________________________________________________________________ * 6. How would you like to have the information theoretic navigation differently? Do you have any other comments and thoughts? _______________________________________________________________________________ Study: BIGfile: Designing Adaptive File Interfaces Participant ID: P-1.

27 .

 27 Participant's name (please print)Signature DateResearcher's name (please print) * How hard did you have to work to accomplish your level of performance? 11. Frustration * How insecure, discouraged, irritated, stressed and annoyed were you? 12. Please provide any additional comments about or reactions to Interface 1* How hard did you have to work to accomplish your level of performance? 18. Frustration * How insecure, discouraged, irritated, stressed and annoyed were you? 19. Please provide any additional comments about or reactions to Interface 2* How hard did you have to work to accomplish your level of performance? 25. Frustration * How insecure, discouraged, irritated, stressed and annoyed were you? 26. Please provide any additional comments about or reactions to Interface 3Rank the interfaces from 1 (Least Preferred) to 3 (Most preferred)

Table 13 A

 13

	HCI Human Computer Interaction
	ID	Index of Difficulty
	KSPC Keystroke Per Character
	WMP Words Per Minute
	BIG Bayesian Information Gain
	BED Bayesian Experimental Design
	MI	Mutual Information
	RT	Reaction Time
	MT Movement Time
	TP	Throughput
	ERP Event Related Potential
	EEG Electroencephalography

summary of different measures of the pilot study. . . . . . . . . . . . . . . . . . . . . . . . . xvii A C R O N Y M S

Table 1 :

 1 A comparison of Hick 1952, Hyman 1953 and HCI studies that used Hick's law (VS

	Cockburn et	Soukoreff &	Mackenzie	Wobbrock
	al. [33]	Macken-	et al. [142,	& My-
	123]	zie [216]	143]	ers [218]

* : Visual Search).

Table 3

 3 summarizes the notations in Bayesian Experimental Design and Bayesian Information Gain respectively.

		BED	BIG
	θ	parameter to be determined	intended target in the user's mind
	y	observation	user input
	x	experimental design	system feedback
		model for making	model for user
	p(y|θ, x)	observation y, given	providing input y,
		θ and x	given θ and x
			system's prior
	p(θ)	prior	knowledge about the
			user's goal
	p(θ|y, x)	posterior	updated knowledge
	I(Θ; Y|X = x)	utility of the design x utility of the feedback x
	IG(Θ|X = x, Y = y)	utility of the experiment outcome after observation y with design x	utility of the outcome after user input y with system feedback x

Table 3 :

 3 Notations in Bayesian Experimental Design (BED) and in Bayesian Information Gain (BIG) respectively.

Table 4 :

 4 Calibration results used as prior knowledge about the user behavior

	Command Main Region Adjacent Regions Other Regions
	Pan	0.90	0.04	0.0033
	Zoom	0.95	0.00625	0.00625
	Click	1	0	0

Table 6 :

 6 Full-factorial ANOVA on the number of commands.

Table 7

 7 shows the results of a repeated measures ANOVA on TCT. All main effects are significant, as well as two interaction effects: IN-

	Factors	df, den	F	p
	INTERFACE	2, 34 452.47 < 0.0001
	LEVEL	1, 17 895.61 < 0.0001
	Session	1, 34	32.12 < 0.0001
	INTERFACE × LEVEL	2, 34 211.89 < 0.0001
	LEVEL × Session	1, 17	14.69 = 0.0242

TERFACE × LEVEL and LEVEL × Session.

Table 7 :

 7 Significant effects in the full-factorial ANOVA on TCT.

Table 12

 12 summarizes the measures in three scenarios.

		No Auto-	Correct Auto-	Incorrect Auto-
		correction	correction	correction
	Total Time (s)	4.4	3.5	4.8
	Input Entropy (bits)	32.8	32.8	32.8
	Transmitted Information (bits)	32.8	32.8	32.8
	Transmitted Information (%)	1.0	1.0	1.0
	Throughput (bit/s)	7.5	9.4	6.8
	Words Per Minute	21.8	27.4	20
	KSPC	1.25	1.0	1.38
	T P m (bit/s)	2.3	2.6	2.4
	T P z (bit/s)	7.7	7.7	7.7

Table 12 :

 12 A summary of different measures on the simulations with or without auto-correction.

The frequency of letters in English is far from uniform. The most common letter E has a frequency of about 13% while the least common letters, Q and Z, occur with a frequency of about 0.1%.

Recall the notions of channel capacity C and information transmitted at a rate R in Chapter 1 Section 1.3.

https://www.interaction-design.org/literature/article/ hick-s-law-making-the-choice-easier-for-users

The right-hand side condition of Equation[START_REF] Id Brown | Many messages from few sources[END_REF] implies that N must always be greater than the number of categories. When we increase k, N should increase a little faster. Practical cases in HCI usually verify that condition, e. g. in the example above with k = 4, N should be greater or equal to 7.

Note that we use the convention that a choice from a null set takes 0 seconds, which explains the extra conditions needed in[START_REF] Id Brown | Many messages from few sources[END_REF] as log(0) → -∞. Also note that using the formulation of[START_REF] Attneave | Applications of information theory to psychology: A summary of basic concepts, methods, and results[END_REF] conveniently solves this issue by adding 1 to N.

The perplexity is the exponentiation of the entropy, which is a more clearcut quantity. The lowest perplexity that has been published on the Brown Corpus (1 million words of American English of varying topics and genres) as of 1992 is about

7.95 = 247 per word, corresponding to a cross-entropy of log 2 247 = 7.95 bits per word or 1.75 bits per letter[START_REF] Peter F Brown | An estimate of an upper bound for the entropy of English[END_REF] using a trigram model. Recall that Shannon[START_REF] Shannon | A mathematical theory of communication[END_REF] estimated the wordentropy of printed English as 11.82 bits per word and Grignetti[START_REF] Grignetti | A note on the entropy of words in printed English[END_REF] estimated 9.83 bits per word (Chapter 2 Section 2.1). It is often possible to achieve lower perplexity on more specialized corpora, as they are more predictable.

An average professional typist types usually at speeds of 50 to 80 wpm.

Like many other researchers (e. g. Mackenzie[START_REF] Mackenzie | Fitts' Throughput and the Speed-accuracy Tradeoff[END_REF], Zhai[START_REF] Zhai | Characterizing computer input with Fitts' law parameters -the information and non-information aspects of pointing[END_REF] and Guiard[START_REF] Guiard | A Mathematical Description of the Speed/Accuracy Trade-off of Aimed Movement[END_REF]), Oulasvirta et al.[START_REF] Oulasvirta | Information Capacity of Full-body Movements[END_REF] was in fact measuring throughput, not capacity in their study. The notions of channel capacity C and information transmitted at a rate R are defined in Chapter 1 Section 1.3.

For a given X, knowing Y decreases uncertainty (increases knowledge) about Θ, by a quantity which is precisely the mutual information I(Θ; Y|X = x).

IG is an "instantaneous" quantity that is positive on average: I = E y (IG) 0.

This is implemented in BIGMap, but not in the original experiment.

11.5 study 2: experiment

All analyses are performed with SAS JMP, using the REML procedure to account for repeated measures.

See Part i Chapter 4.

https://github.com/wanyuliu/Information-Theoretic-Metrics/ includes python code for computing all metrics of the examples in this part.

See Part i Chapter 2.

The growing use of auto-correction on smartphones has also led to the creation of several websites, e. g. http://www.damnyouautocorrect.com, where people post and share humorous or embarrassing cases of improper auto-corrections.

https://docs.python.org/3/library/tk.html

We provide the package to compute these information-theoretic measures at https: //github.com/wanyuliu/Information-Theoretic-Metrics/.

a.3 bigfile experiment consent

Algorithmus 2 : BIGFileFast Efficiently search a suboptimal set of shortcuts.

Result : Return set A that, together with set S, has a suboptimal maximal expected information gain.

// Create the compressed tree, i. e.

1

The minimal subtree of the current folder F that contains the n most probable targets:

for each element t of the tree do 3 if t is the only child of its parent then Replace the parent by t and remove the parent // Search this simplified tree 5 A = a set of N nodes such that no node is in the subtree of another node

6

IG max = IG(S A)

while there are more sets to explore do

pilot study

We conducted a pilot study to capture real users' file structures and understand their file navigation practices, informing our simulations (Study 1) and experiment (Study 2). We wanted to see if and how the structures and practices reported in the literature [START_REF] Bergman | The Effect of Folder Structure on Personal File Navigation[END_REF][START_REF] Henderson | An empirical analysis of personal digital document structures[END_REF] have changed.

We recruited 15 participants from our institution, including faculty members, post-docs and students, all in technical areas. 13 were Ma-cOS users, 2 were Windows users. We wanted to know the depth and breadth of their file systems, their navigation strategies, their preferred view for retrieving files, and the problems they run into.

Information Theory in Understanding and Guiding Multiscale Navigation Experiment

First of all, we express our sincere gratitude to you for participating in this experiment. You can find cookies and candies on the table. Please feel free to serve yourself.

The goal of this study is to gain some insight into the role of information theory in understanding and guiding multiscale navigation. It applies in the scenario where users have already decided a destination and navigate to it. For instance, navigating to Paris from somewhere else. Different from traditional zooming and panning, it utilizes both human inputs and multiscale world characteristics to enhance navigation.

There are two sessions in this experiment --Calibration and Controlled Study .

Calibration:

The goal of this session is to better understand human behavior when zooming and panning in multiscale world. We are particularly interested in your perception regarding direction . For example, if you are aware that your destination --a red dot , indicated by concentric rings, is on the right, what are the chances that you will go to right whereas what are the chances you will go to other directions due to misjudge, motor error, etc. We will then use the result to tune parameters in the real experiment. Sample trials are as below:

Controlled Study:

In this controlled study, your task is to navigate to the target that is in red from certain distance to completely zoomed-in level and right click on it. Concentric circles are placed around the target to always indicate the direction. You will encounter two conditions that represent conventional zooming and panning, and information theoretic navigation respectively. At the end of the experiment, you will be asked for the preference toward these two techniques. There will be 300 trials in total, taking approximately 60 minutes. PLEASE THINK LOUD during the experiment. You can terminate it if you do not feel comfortable at any moment. Do not hesitate to ask questions to experimenter if you have any. If you are ready, please sign the consent form below and we can start the experiment.

Consent Form

I agree to participate in the user study conducted by the Human-Computer Interaction group at Telecom ParisTech.

I understand that participation in this study is voluntary and I agree to immediately raise any concerns or areas of discomfort during the session with the study administrator.

Please sign below to indicate that you have read and you understand the information on this form and that any questions you might have about the session have been answered. For the following questions, please choose a number from 1 to 7 to describe your experience with interface 1.

For each question, we would appreciate any additional comments you have in the "Comments" section.

Interface 2

For the following questions, please choose a number from 1 to 7 to describe your experience with interface 2.

For each question, we would appreciate any additional comments you have in the "Comments" section.

13. Mental Demand * How mentally demanding was the task?

Interface 3

For the following questions, please choose a number from 1 to 7 to describe your experience with interface 3.

For each question, we would appreciate any additional comments you have in the "Comments" section.