Yang Li

Samy Bengio
email: bengio@google.comyangli@acm.org

Gilles Bailly
email: gilles.bailly@upmc.fr

Predicting Human Performance in Vertical Menu Selection Using Deep Learning

Keywords: Performance modeling, deep learning, recurrent neural networks, LSTM, touchscreen, lists, menus, TensorFlow. ACM Classification H.5. HCI, I.2. Artificial Intelligence

Predicting human performance in interaction tasks allows designers or developers to understand the expected performance of a target interface without actually testing it with real users. In this work, we present a deep neural net to model and predict human performance in performing a sequence of UI tasks. In particular, we focus on a dominant class of tasks, i.e., target selection from a vertical list or menu. We experimented with our deep neural net using a public dataset collected from a desktop laboratory environment and a dataset collected from hundreds of touchscreen smartphone users via crowdsourcing. Our model significantly outperformed previous methods on these datasets. Importantly, our method, as a deep model, can easily incorporate additional UI attributes such as visual appearance and content semantics without changing model architectures. By understanding about how a deep learning model learns from human behaviors, our approach can be seen as a vehicle to discover new patterns about human behaviors to advance analytical modeling.

INTRODUCTION

Seeking models for predicting human performance in performing an interaction task has long been pursued in the field of human computer interaction [2-8, 11, 16]. In addition to the scientific value of understanding human behaviors, creating these models has practical values in user interface design and development. A predictive model allows a developer or designer to understand the expected performance of an interface without having to test it with real users, which can be expensive and effort consuming.

Several predictive models of human performance have been devised, including Fitts' law [START_REF] Fitts | The Information Capacity of the Human Motor System in Controlling the Amplitude of Movement[END_REF] and Hick's law [START_REF] Hick | On the rate of gain of information[END_REF], which are rooted in information theory and experimental psychology. However, these models capture a certain aspect of human performance in isolation, e.g., motor control or decision making. They are limited in modeling human performance in realistic interaction tasks where multiple factors interplay. Recent work (e.g., [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF]) has attempted to develop compound models that combine models such as Fitts' law. While these methods have made great progress in predicting time performance in more realistic tasks, these analytical models are not easily extensible to accommodate new factors that might come into play.

In this work, we take a departure from existing analytical approaches for performance modeling by using a datadriven approach based on the recent advance in deep learning [START_REF] Lecun | Deep learning[END_REF]. Deep learning has proven successful in many domains, such as computer vision [START_REF] Lecun | Deep learning[END_REF] and natural language processing [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF]. It relieves the need of careful feature engineering and of a great amount of domain knowledge in creating a predictive model. It can also capture patterns that only manifest in the data but are difficult to articulate in an analytical form.

In particular, we devise a predictive model (see Figure 1) for interaction performance based on a deep recurrent neural net architecture using Long-Short Term Memory (LSTM) [START_REF] Hochreiter | Long Short-Term Memory[END_REF]. The unique architecture of our LSTM-based model allows us to naturally capture a variety of factors that come into play in UI tasks, including not only what human users are perceiving and performing at the moment but also what they have learned from the past regarding an interaction task. To scope our work, we focus on a common task on desktop and smartphones, where users select a target item from a vertical menu or list1 , e.g., choosing a song to play, a person to contact, selecting an application in the start menu or simply activating a command in a dropdown menu. Because users often need to perform these selection tasks repeatedly over the time, we investigate our approach in the context of a sequence of selection tasks.

We design a novel hierarchical deep architecture for menu performance modeling. In our architecture, a recurrent neural net is used to encode UI attributes and tasks at each target item selection. This allows us to represent a menu with a varied length and to easily incorporate any additional UI attributes such as visual appearance and semantics. We then use another recurrent net to capture learning effects, a major component in human performance. The entire model is learned end-to-end using stochastic gradient descent. The model outperforms existing analytical methods in various settings for predicting selection time. Importantly, it is easily extensible for accommodating new UI features and human factors involved in an interaction task.

As a machine learning model, especially a deep architecture, the general challenge is that it is difficult to gain insights into what the model actually learns. We analyze how our model learns to mimic human behaviors. We show that our model "remembers" and "forgets" like a human-the model gains expertise on a visited item from past trials and that expertise fades away over time if the user does not access the item for a while. Prior work models expertise as frequency counts [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF], which does not take into account the "forgetting" effect in human behavior. We also discuss how this "memory effect" is affected by different menu organizations. We believe these analyses improve our understanding about how a deep learning model learns from human behaviors, which in turn can inspire analytical modeling.

RELATED WORK

Extensive work has been conducted in modeling human behaviors and predicting human performance for performing interaction tasks. For example, Fitts' Law [START_REF] Fitts | The Information Capacity of the Human Motor System in Controlling the Amplitude of Movement[END_REF] predicts the time needed for an expert human to acquire a visual target. Similarly, Hick's Law [START_REF] Hick | On the rate of gain of information[END_REF] is also a wellknown model that describes the time required for an expert human to make a decision of choosing among a given number of options.

While each of these previous methods is amazingly robust for modeling the specific aspect of human behaviors it focuses on, they are limited in modeling realistic interaction tasks. For example, Fitts' Law was originally proposed for a limited setting of one-dimensional target with no distractors. Although prior work has extended Fitts' Law in several ways (e.g., [START_REF] Bi | FFitts Law: Modeling Finger Touch With Fitts' Law[END_REF][START_REF] Mackenzie | Extending Fitts' law to two-dimensional tasks[END_REF]), it is still constrained. Moreover, target acquisition is only one aspect of an interaction task. In a realistic task, there are many factors convoluted such as visual search, motor control and learning effects on spatial memory, as well as other factors that may or may not have been discovered in the literature.

There has been a considerable amount of efforts in combining these building block models such as Fitts' Law and Hick's Law so that their combination can be more applicable to modeling complex interaction tasks [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF][START_REF] Byrne | ACT-R/PM and menu selection: Applying a cognitive architecture to HCI[END_REF][START_REF] Chen | The Emergence of Interactive Behavior: A Model of Rational Menu Search[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF][START_REF] Halverson | A Computational Model of "Active Vision" for Visual Search in Human-Computer Interaction[END_REF]. Particularly, GOMS/KLM [START_REF] Card | The keystroke-level model for user performance time with interactive systems[END_REF] predicts the time taken for an expert user to perform a routine task. ACT-R [START_REF] Byrne | ACT-R/PM and menu selection: Applying a cognitive architecture to HCI[END_REF] or EPIC [START_REF] Kieras | An overview of the EPIC architecture for cognition and performance with application to human-computer interaction[END_REF] implement a set of production rules to decide, for instance, visual search strategies in linear menus. Prior work (e.g., [START_REF] Kaptelinin | Item recognition in menu selection: the effect of practice[END_REF][START_REF] Sears | Split menus: effectively using selection frequency to organize menus[END_REF]) has also revealed the important role of learning effect played in menu selection, such as the forming of spatial memory reduces visual search.

More recently, Cockburn et al. [START_REF] Cockburn | A predictive model of menu performance[END_REF] combined pointing time (Fitts' Law), decision time (Hick's Law), visual search time, and expertise in a single model. The model is compact and robust in modeling a range of menu selection tasks. In the same vein, Bailly et al. [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF] proposed a more complex model that is formulated based on gaze distribution for menu selection tasks.

While previous methods, which are mostly empirically tuned analytical models, have gained substantial progress in modeling human behaviors, they are not easily extensible for accommodating various aspects of user interfaces and human factors. For example, the saliency of items [START_REF] Näsänena | Effect of stimulus contrast on performance and eye movements in visual search[END_REF] on an interface can significantly affect the time needed for visual search. Learning effect is a profound factor that affects every aspect of human performance. In addition, new generations of computing devices such as touchscreen smartphones have introduced many factors that are not covered by traditional models. While it is possible to further expand existing models, there is a tremendous amount of challenges and effort to do so-new factors are not always obvious or easily analytically articulated.

In contrast to previous approaches, we propose a datadriven approach based on the recent advance of deep learning. Deep learning [START_REF] Lecun | Deep learning[END_REF] employs multiple processing layers to automatically learn representation of raw data, which reduces the need of intensive feature engineering and thus the need of domain expertise. In particular, we designed our model based on Long-Short Term Memory (LSTM) [START_REF] Hochreiter | Long Short-Term Memory[END_REF], a recurrent neural net, which has been successfully applied in many sequential problems such as natural language processing [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF]. Our work is the first in applying deep recurrent neural net for modeling human performance in interaction tasks. While it is challenging to analyze the behavior of a deep model in general, we offer several insights into how such a model learns to mimic human behaviors from data.

THE MODEL DESIGN & LEARNING

We present a model to predict human performance in performing a sequence of UI tasks. It builds on two important capabilities of recurrent neural net (RNN) [START_REF] Graves | Supervised Sequence Labelling with Recurrent Neural Networks[END_REF]. First, it is capable of "reading" in a varied-length sequence of information and encoding it as a fixed-length representation. It is important as an interaction task often involves varied-length information. For example, the number of items in a menu can vary from one application to another. Second, the model is capable of mimicking users' behavior by learning to both acquire and "remember" new experience, and discard (or "forget") what it learns if the experience is too dated. While learning effects are a major component in human performance, prior works primarily use a frequency count as the measure of the user's expertise. In contrast, our model relies on LSTM [START_REF] Hochreiter | Long Short-Term Memory[END_REF], which offers a mechanism that is more natural in mimicking human behaviors.

Encoding A Single-Step Selection Task

At each step, a user selects a target item in a vertical menu. From previous work, there are multiple factors in the task affecting human performance, including the number of items in the menu, the location of the target item in the menu, the visual salience of each item and whether there are semantic cues in assisting visual search.

For each element in the UI-an item in the menu in our context, we represent it as a concatenation of a list of attributes (see Equation 1). We use 1 or 0 to represent whether it is the target item for the current step. To capture the visual salience of an item, we use the length of the item name. An item that is especially short or long in comparison to the rest items on the menu tends to be easier to spot. To capture the semantics of an item, we represent the meaning of the item name with a continuous vector that was acquired from word2vec [START_REF] Pennington | Global Vectors for Word Representation[END_REF], which project a word onto a continuous vector space where similar words are close in this vector space. ! " # denotes the vector representation of the jth item in the menu at step $ in the interaction sequence.

! " # = &'()*&, len(0'!*), word2vec(0'!*) (1)
To encode the selection task that involves a list of items in the menu, we feed the vector representation of each item in sequel to a recurrent neural net [START_REF] Graves | Supervised Sequence Labelling with Recurrent Neural Networks[END_REF] (see Figure 2). * " # represents the hidden state of the recurrent net after reading the jth item and seeing the previous items through * " #9: . 0 denotes the number of items in the menu. This recurrent net performs as a task encoder (thereafter referred as the encoder net) and it does not have an output layer. The final hidden state of the recurrent net, * " ; , a fixed-length vector, represents the selection task at step $. We then concatenate a one-hot vector to indicate whether the menu items are semantically grouped, alphabetically sorted or unsorted, resulting in * " . The task encoder can accommodate a menu with any length, n, and UI attributes.

Modeling A Sequence of Selection Tasks

With the interaction task at each step of a sequence represented as * " , we can now feed the sequence into another recurrent neural net (see Figure 3), which we refer to as the prediction net. Note that * " in Figure 3 represents the encoder net, which is a recurrent neural net itself whose outcome is fed to the prediction net. The task at each step can vary simply because the user might need to select a different target item. The UI at each step can also be different, e.g., an adaptive interface might decide to change the appearance of an item such as its size [START_REF] Cockburn | A predictive model of menu performance[END_REF] to make it easier to acquire.

The recurrent neural net predicts human performance time at each step, & < . The predictions are based on not only the task at the current step but also the hidden state of the previous step that captures the human experience while performing previous tasks. Previous work in deep learning has shown that adding more layers in a deep net can improve the capacity for modeling complex behaviors [START_REF] Lecun | Deep learning[END_REF]. To give the model more capacity, we add a hidden layer, with ReLU [START_REF] Nair | Rectified Linear Units Improve Restricted Boltzmann Machines[END_REF] as the activation function, after the recurrent layer, denoted as nonlinear projection in Figure 3. Finally, the time prediction & < is computed as a linear combination of the outcome of the nonlinear transformation layer.

Model Learning & Loss Function

It is straightforward to compute the time prediction with the feedforward process of a neural net. The two recurrent neural nets involved in our model are trained together, end to end from the data by feeding in sequences of selection tasks as input and observed performance times as the target output (the ground truth), using stochastic gradient descent.

For time performance modeling, one common measure of prediction quality in the literature has been ? @ (e.g., [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF][START_REF] Bi | FFitts Law: Modeling Finger Touch With Fitts' Law[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF][START_REF] Fitts | The Information Capacity of the Human Motor System in Controlling the Amplitude of Movement[END_REF]). It measures how well predicted times match observed ones in capturing relative task difficulty or human performance across task conditions and progression. For general time series modeling regarding continuous values, there are other metrics often used, such as Root Mean Square Error (RMSE) or Mean Absolute Error (MAE).

Mathematically, ? @ is the correlation between the sequence of observed times, A < , and the sequence of predicted times, & < , (see Equation 2). B represents the length of the sequence, and A is the mean of A < .

? @ = 1 -

E F 9G F H I FJK E F 9E H I FJK (2) A < -A @ L <M:
reflects the variance of the observations in each sequence, which is independent of models. Thus, it is a known constant for each sequence in the training dataset, which we refer to as N " . To maximize ? @ , we want to minimize the squared error term

A < -& < @ L <M:
, scaled by a sequence-specific constant N " , which defines the loss function (see Equation 3). The scaling acts effectively as adapting the learning rate based on the variance of each sequence for training the deep neural net. Intuitively, for each training sequence, the more variance the sequence has, the smaller learning rate we should apply for updating the model parameters, and vice versa.

O G = E F 9G F H I FJK P Q (3)
With the loss function defined, our model can be trained using Back Propagation Through Time (BPTT) [START_REF] Graves | Supervised Sequence Labelling with Recurrent Neural Networks[END_REF], a typical method for training recurrent neural nets (see more details in the following sections).

EXPERIMENTS

We experimented with our model based on two datasets from both a controlled and a crowd-sourced environment. We first discuss these datasets, and the model and training configuration. We then discuss the performance of our model in comparison with a state of art analytical method proposed previously [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF].

Datasets

We experimented with the deep net on modeling menu selection tasks with a public dataset [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF] collected from a desktop computer in a controlled laboratory environment, and a dataset we collected from smartphone users using crowdsourcing. For testing different task difficulties and learning effects, these datasets involve menus with different lengths and long sequences of trials.

Public Dataset from a Controlled Laboratory

Bailly et al. conducted a within-subjects study to collect data from 21 participants [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF]. The study involved three menu organizations: Unordered, Alphabetical and Semantic, and three menu lengths: 8, 12 or 16 items.

Participants were asked to complete 12 blocks of trials per menu. For each menu, the order of items in the menu is fixed so that participants can learn item positions over time. Within a block, each target item is selected once and the order of target items was randomized. The experiment was conducted on a windows PC with a 20 LCD display and a traditional optical mouse. In total, there are 189 sequences: 21 participants x 3 Menu configurations x 3 Menu Length. The length of each sequence may vary depending on the menu length: 12 blocks x (8-12-16 items) and there are 39,564 selections.

Touchscreen Smartphone Dataset from Crowdsourcing

To collect data of users interacting on a smartphone, we implemented a data collection tool as a web application (see Figure 4). We recruited smartphone users via Amazon Mechanical Turk and these users are redirected to our web application to complete a sequence of menu selection tasks. Because the data collection takes place in the wild, we intend to maximally assure the consistence of the setting by controlling a few setups. To make sure a list to appear with the same size on a phone, we decide to target on a few specific smartphone models: Apple iPhone 6 and Android Nexus 5. A user is also required to hold the phone in the portrait mode while performing the task, and our web app automatically prohibits the users to continue the task if it detects the landscape mode. Once a user completed a sequence of tasks, the data are automatically uploaded and stored on the server.

Our data collection was designed in a similar way to previous work. There are three menu lengths: 8, 12 and 16. Each worker is randomly assigned to a menu length with the item labels also randomly selected from a set of country names. The order of items in each menu is randomly determined for each worker and remains fixed throughout the trials. The location of the target item in the menu is randomly assigned for each trial. The number of trials completed by each worker ranged from 96 to 192 depending on menu lengths. In total, there were 863 sequences generated, each from a unique smartphone user (804 iPhone and 59 Android users). There were 384 males and 479 females. 50% users aged between 20-29 and 32% users between 30-39. 10% of these users were left-handed. The mean duration of a worker session spanned 7 minutes (STD=2.6 minutes). There are in total 159,072 selections in these sequences.

Model Configuration & Hyper Parameters

For the encoder net, the recurrent layer uses 16 LSTM cells [START_REF] Hochreiter | Long Short-Term Memory[END_REF]. The text name of each menu item is represented as a continuous embedding vector based on a 50-dimensional vector representation learned from the Wikipedia corpus [START_REF] Pennington | Global Vectors for Word Representation[END_REF]. Because the number of unique names in our datasets is relatively small compared to the entire English vocabulary on Wikipedia, we reduce the dimensionality of the name embedding to 4 using PCA, to speed up learning. As a result, each menu is represented as a continuous vector of size 6: 1 slot for indicating if the item is the target, 1 slot for the name length, and 4 slots for the name embedding. For the prediction net, we used 32 LSTM cells for its recurrent layer. The nonlinear transformation over the recurrent layer has a size of 16 that are used for computing the time prediction. We implemented our model in Python based on TensorFlow, an open source deep learning library [START_REF] Martín Abadi | TensorFlow: A system for largescale machine learning[END_REF].

We trained the model by minimizing the loss in Equation 3 using Ada adaptive gradient descent, with a learning rate of 0.01, a norm of 1.0 for clipping the gradients, a batch size 1 and the number of unroll of 40 for truncated backpropagation through time [START_REF] Graves | Supervised Sequence Labelling with Recurrent Neural Networks[END_REF]. To regularize the model learning, we found applying a dropout ratio of 10% to the task encoding, * " , can effectively avoid the model overfitting the training data prematurely.

Performance Results

For each dataset, we randomly split the data on users with half of the users for training and the other half of the users for testing the model. For the experiments with the public dataset, our model was trained for four million iterations. Because there are significantly more data in the smartphone crowd dataset, we trained our model for ten million iterations.

Previous modeling work often reports performance on how well a model can fit the data. As a machine learning model that uses a large number of parameters, it is meaningless to report fitting performance. In this paper, we only report the experiment results based on the test dataset for which the model was not trained on, which truly shows how well the learned model can predict on new data.

We report the accuracy of our model on both target-level and menu-level ? @ that were used in previous work [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF]. Both measure the correlation between predicted and observed performance times. Target-level ? @ examines performance at each target position in a menu with a different amount of practice (blocks). Menu-level ? @ examines the average performance over all target positions in a menu with a varying amount of practice.

For target-level ? @ , our model achieved 0.75 on the public dataset for the overall correlation across menu organizations. In particular, ? @ for alphabetically ordered (A), semantically grouped (S) and unsorted menus (U) are 0.78, 0.62 and 0.80 respectively. Note that we used a single model to predict for all menu organizations. Previously, Bailly et al. tuned and tested their model for each menu organization separately. Their ? @ results were reported as 0.64 (A), 0.52 (S), 0.56 (U) [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF]. For menu-level ? @ , our model achieved 0.87 for overall correlation: 0.85 (A), 0.88 (S) and 0.94 (U), which previous work reported as 0.91 (A), 0.86 (S) and 0.87 (U) [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF]. Our model achieved a similar performance for the smartphone dataset that involves only unordered menus: target-level ? @ = 0.76 and menu-level ? @ = 0.95. It accurately predicts the time performance for each menu length (see Figure 5).

ANALYZING MODEL BEHAVIORS

While it is generally challenging to analyze what a deep model learns, we here offer several analyses of the model behaviors and discuss how they match our intuition about user behaviors. To understand the behavior of our deep net model, we compute its Jacobian that is the partial derivatives of the network output with respect to a specific set of inputs (see Figure 6)-it indicates how sensitive the time prediction is to the change in the input at each step. In particular, we want to find out how users' past experience with selecting a target affects their performance for selecting the target item again. Figure 6 is generated by taking the Jacobian of the deep net output, i.e., the time performance, with regards to the target feature in Equation 1. We see that the more recent the experience is with selecting a target item, the more influence it has on the current trial for selecting the target item again. Intuitively, it might be because the user remembers where the item is on the list, as found in previous work [START_REF] Bailly | Model of visual search and selection time in linear menus[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF]. However, such an effect eventually wears off as the experience becomes dated, which is quite consistent with how human memory works. Previous work uses frequency count to represent the user expertise with an item and is insufficient to capture the profound aspects of human short-term memory such as the forgetting effect.

We also found the degree of how much the current performance relies on the past experience differs for the different menu organizations. As shown in Figure 6, such sequence dependency has the largest effect on unordered menus and less effect on semantically or alphabetically organized menus. We speculate that this is because semantic and alphabetic menus provide additional cues for users to locate an item, which result in less dependency on memory for completing the task.

DISCUSSION & FUTURE WORK

LSTM has been extensively used in domains such as natural language processing (NLP). One major commonality between interaction tasks and NLP is that they both are concerned with sequential dependency, which is manifested as learning effect in interaction tasks. But unlike a standard NLP problem that deals with a sequence of words (tokens), each step in our selection task involves visual search and acquisition of the target in the percept of the menu UI with various attributes, which cannot be simply treated as a token. We designed the model architecture based on LSTM to capture this unique aspect of interaction tasks. The memory cells in LSTM is to simulate human short-term memory that is updated when the user performs each selection task. The execution of a task trial is simulated by another LSTM where visual search and motor control are captured. We found the memory capability is important for modeling human performance and our early exploration with a feedforward neural net did not yield good performance.

There are several advantages for using a deep learning approach for human performance modeling. Creating an effective analytical model requires a lot of domain expertise, including perception, motor control and decision making. Manually combining different performance components is hard to scale as more and more factors are involved in a realistic interface. In contrast, a deep learning approach is easily extensible for incorporating new factors as long as they are manifested in the data. Our model, which employs two hierarchically organized recurrent neural nets, is highly extensible to incorporate additional UI and task attributes.

That said, analytical models are easier to understand than a deep learning model. In fact, it has been a general challenge for the interpretability of deep learning models although they offer superior accuracy performance. In this work, we analyzed how human learning effects are captured and mimicked by a deep model (see Figure 6), and how the learning effect differs across different menu organizations. The Jacobian responds differently for different menu organizations, which reflects memory effect as manifested from the data. These findings can advance our understanding about how human behaves thus may inspire others to design new analytical models to capture these effects. Thus, rather than using deep models only for predictions, the deep learning approach can be seen as a vehicle to discover new patterns about human behaviors to advance analytical research.

There are several directions for future work. It is worth examining the analytical findings about the memory effects on different menu organizations by conducting further user experiments. In addition, there are opportunities to extend our model for multilevel analysis of interaction by considering finer-granularity behaviors such as the mouse and gaze path of users in selection tasks. This has the potential to provide new insights on visual search in menus and the coordination between gaze and hand movements.

CONCLUSION

We presented a deep learning approach for modeling user performance for menu selection, a dominant task in modern interfaces. Our model is highly extensible. It can accommodate various UI aspects without changing the model architecture or using extensive domain knowledge. It outperformed a previous method on predicting performance time based on a public dataset and a large-scale smartphone dataset. We discussed an analysis of the model behaviors, which revealed new findings about how past experience of the user has an influence on the user performance with regard to different menu organizations. We contributed a set of knowledge and technical details about how to design, train and analyze a deep model for performance modeling.

Figure 1 .

 1 Figure 1. A high-level illustration of our approach for predicting human time performance. The model, mimicking a human user, not only sees the UI and task at the moment but also remembers what it has experienced previously, through its recurrent layer. The representation of the UI and task at each step is achieved via another recurrent net.

Figure 2 .

 2 Figure 2. We use a recurrent neural net to encode the selection task at a step, s. ! " # is the vector representation of the jth item in the menu and * " # is the hidden state of the net after reading in the jth item.

Figure 3 .

 3 Figure 3. A recurrent neural net takes in the selection task at each step, =, and the acquired expertise (represented as the hidden state ℎ < ), and predicts the time needed, & < , for completing the selection task at this step.

Figure 4 .

 4 Figure 4. The Data Collection web application on iPhone. For each trial, with informed the target name, the worker taps on the Start button to reveal the menu and then selects the target.

Figure 5 .

 5 Figure 5. The model accuracy over blocks on the smartphone dataset for menus with different lengths, with predicted times in solid lines and observed times in dashed lines.

Figure 6 .

 6 Figure 6. The Jacobian of our deep net indicates how the time performance for selecting a target item is affected by the past experience for selecting the item, in response to different menu organizations. The X axis is the trials in the sequence and the Y axis shows the magnitude of the derivative, i.e., the impact.

In this paper, we use "list" and "menu" interchangeably to refer to a list of items or options for the user to select.


Gilles Bailly

Antti Oulasvirta

Duncan P Brumby

Andrew Howes

Model of Visual Search and Selection Time in Linear Menus

Keywords: Linear menus, User Performance, Mathematical predictive models, Visual search, Eye-tracking. ACM Classification H.5.2. Information Interfaces and Presentation (e.g. HCI): Miscellaneous

This paper presents a novel mathematical model for visual search and selection time in linear menus. Assuming two visual search strategies, serial and directed, and a pointing sub-task, it captures the change of performance with five factors: 1) menu length, 2) menu organization, 3) target position, 4) absence/presence of target, and 5) practice. The novel aspect is that the model is expressed as probability density distribution of gaze, which allows for deriving total selection time. We present novel data that replicates and extends the Nielsen menu selection paradigm and uses eye-tracking and mouse tracking to confirm model predictions. The same parametrization yielded a high fit to both menu selection time and gaze distributions. The model has the potential to improve menu designs by helping designers identify more effective solutions without conducting empirical studies.

INTRODUCTION

Menus are used on numerous applications and systems for presenting, organizing, and selecting commands. However, designers reportedly struggle with menu design [START_REF] Bailly | Menuoptimizer: Interactive optimization of menu systems[END_REF]. While many research papers focus on novel interaction techniques (e.g. [START_REF] Sears | Split menus: effectively using selection frequency to organize menus[END_REF]), and others on human factors (e.g. [START_REF] Brumby | Good enough but I'll just check: web-page search as attentional refocusing[END_REF][START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF][START_REF] Mcdonald | Searching for items in menus: The effects of organization and type of target[END_REF][START_REF] Mehlenbacher | Finding information on a menu: linking menu organization to the user's goals[END_REF][START_REF] Nilsen | Perceptual-motor control in human-computer interaction[END_REF]), surprisingly few develop predictive models of users' performance with menus [START_REF] Brumby | Strategies for guiding interactive search: An empirical investigation into the consequences of label relevance for assessment and selection[END_REF][START_REF] Byrne | Act-r/pm and menu selection: Applying a cognitive architecture to hci[END_REF][START_REF] Card | User perceptual mechanisms in the search of computer command menus[END_REF][START_REF] Cockburn | A predictive model of human performance with scrolling and hierarchical lists[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF][START_REF] Fu | Snif-act: a cognitive model of user navigation on the world wide web[END_REF][START_REF] Hornof | Cognitive modeling reveals menu search in both random and systematic[END_REF][START_REF] Lane | Predicting the skilled use of hierarchical menus with the keystroke-level model[END_REF]. Predictive models are an efficient way of encapsulating scientific knowledge. They synthesize phenomena that are typically fragmented across several studies, and they capture subtle interactions among multiple factors in an empirically verifiable form. They can help designers to design more efficient menus by informing choices without expensive empirical studies. Once matured enough, models can be incorporated into interactive design tools [START_REF] Bailly | Menuoptimizer: Interactive optimization of menu systems[END_REF][START_REF] Fu | Snif-act: a cognitive model of user navigation on the world wide web[END_REF][START_REF] John | Predictive human performance modeling made easy[END_REF]. Models of menu performance can be divided into two categories: cognitive simulations and mathematical models. Simulation models such as ACT-R models [START_REF] Anderson | Act-r: a theory of higher level cognition and its relation to visual attention[END_REF][START_REF] Byrne | Act-r/pm and menu selection: Applying a cognitive architecture to hci[END_REF] and EPIC models [START_REF] Halverson | A computational model of active vision for visual search in humancomputer interaction[END_REF][START_REF] Hornof | Cognitive modeling reveals menu search in both random and systematic[END_REF][START_REF] Kieras | An overview of the epic architecture for cognition and performance with application to human-computer interaction[END_REF] explain the progression of search by reference to underlying cognitive processes, such as perception, attention, and memory. Mathematical models such as the SDP model [START_REF] Cockburn | A predictive model of human performance with scrolling and hierarchical lists[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF] are nonlinear regression equations that predict selection time as a function of external factors such as menu length, target position and practice. These models expose fewer details about the process but may be less complex and more straightforward to apply.

Our goal is to advance the scope and validity of mathematical models of linear menus, a widely used menu type in desktop applications and consumer electronics. We assume that tasks, including both searching and pointing, are performed using one of a number of strategies. In practice, the strategy space for perceptual/motor tasks, even very simple ones, is known to be large [START_REF] Howes | Rational adaptation under task and processing constraints: implications for testing theories of cognition and action[END_REF][START_REF] Smith | More than 8,192 Ways to Skin a Cat : Modeling Behavior in Multidimensional Strategy Spaces[END_REF] but here we explore a few key points in the space. We focus on two searching strategies: 1) Directed search makes use of knowledge, including knowledge of locations acquired through practice, alphabetic and semantic knowledge, to programme saccadic eye movements that jump to the vicinity of the target location or directly to its location. 2) Serial search starts with the first menu item and moves from one item to the next until the target is located or the menu is exhausted. In practice a user would combine elements of these strategies depending on the reliability of available of knowledge. For example, directed search might be combined with serial search in proportion to the reliability of location memories and the available relevance scores. In some situations location knowledge will be highly reliable and in others it will be the relevance scores that are more reliable. Finally, 3) we also explore two pointing strategies: Find-and-point and Track-and-point.

In our current model these strategies are expressed as probability distributions of gaze. A distinct advantage of this model formulation is that it allows deriving both distributions for gaze points on the menu as well as selection time from the same parametrization. These predictions can be checked against eye tracking data.

To parametrize and evaluate the model, we collected an extensive dataset. Although the constituent processes of menu selection have been heavily studied in psychology, the menu selection task has been hard to study for the purposes of modeling. Multiple factors must be controlled, the apparatus like eye-trackers are complex, and the studies must be long enough to gauge practice effects. Our model is informed by a study that replicates and extends the Nielsen [START_REF] Nilsen | Perceptual-motor control in human-computer interaction[END_REF] menu selection task in order to cover more factors. The experimental design controls 1) menu length, 2) menu organization, 3) target position, 4) absence/presence of target, and 5) practice. These factors were chosen to extend the coverage of modeling to a larger number of empirically reliable findings reported in the literature. Particularly important is the effect of menu organization, which we cover with three frequent layouts: alphabetical, semantic, and unordered. Moreover, we reveal a last item effect: items that are positioned toward the end of the menu are faster to select. The data confirms some existing findings and yields new observations of subtle interactions among the factors that our model tries to capture.

GOALS AND RELATED WORK

In our view, an ideal predictive model covers phenomena which are replicated, shown to bear large effect sizes, concern features that designers can affect, and are widespread in real designs. We visited empirical findings on linear menu search and gathered a list of six phenomena which serves as the goal for our modeling efforts. We review them and discuss what is left out of our model due to this scoping. We also briefly review how existing models address these phenomena.

Menu Performance Phenomena

1. Menu length: Users are faster at searching menus with fewer items [START_REF] Anderson | The Atomic Components of Thought[END_REF][START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF][START_REF] Nilsen | Perceptual-motor control in human-computer interaction[END_REF]. More precisely, search time to the same target position increases as the number of items in the menu increase. This effect can be explained by the fact that, on average, it will require more time to localize a random target in a longer menu [START_REF] Ahlström | Why it's quick to be square: modelling new and existing hierarchical menu designs[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF][START_REF] Hornof | Cognitive modeling reveals menu search in both random and systematic[END_REF][START_REF] Sears | Split menus: effectively using selection frequency to organize menus[END_REF].

Menu organization:

The organization of items in the menu affects selection time. In particular, semantic and alphabetic organizations of items are faster than unordered layouts [START_REF] Card | User perceptual mechanisms in the search of computer command menus[END_REF][START_REF] Halverson | The effects of semantic grouping on visual search[END_REF][START_REF] Mcdonald | Searching for items in menus: The effects of organization and type of target[END_REF][START_REF] Mehlenbacher | Finding information on a menu: linking menu organization to the user's goals[END_REF]. This is explained by learning in visual search: experienced users learn to skip items in the menu. The relationship between alphabetic and semantic organization is more nuanced. For targets with unknown labels, semantic organization is faster than alphabetic organization [START_REF] Mcdonald | Searching for items in menus: The effects of organization and type of target[END_REF]. However, for target with known labels the evidence is mixed: One study found no difference [START_REF] Mcdonald | Searching for items in menus: The effects of organization and type of target[END_REF], but two others suggest that alphabetic is faster [START_REF] Card | User perceptual mechanisms in the search of computer command menus[END_REF][START_REF] Mehlenbacher | Finding information on a menu: linking menu organization to the user's goals[END_REF].

Target position:

Users are faster at selecting targets that are closer to the top of the menu [START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF]. This effect is large and only partially explained by pointing time. Visual search strategies can explain the effect [START_REF] Norman | The Psychology of Menu Selection: Designing Cognitive Control at the Human/Computer Interface[END_REF]: Users can follow a serial search strategy, reading items one by one from the top of the list until reaching the target [START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF][START_REF] Hornof | Cognitive modeling reveals menu search in both random and systematic[END_REF][START_REF] Lee | Minimizing user search time in menu retrieval systems[END_REF]. Users can use a mix of serial and random search (with or without replacement) [START_REF] Hornof | Cognitive strategies for the visual search of hierarchical computer displays[END_REF][START_REF] Hornof | Cognitive modeling reveals menu search in both random and systematic[END_REF]. In both cases, search time is a linear function of target position. Moreover, the second item can sometimes be faster to select [START_REF] Byrne | Act-r/pm and menu selection: Applying a cognitive architecture to hci[END_REF][START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF]. Finally, we will reveal below that items that are positioned toward the end of the menu are faster to select (Fig. 2). We call this phenomenon last item effect).

Absent target:

Scanning a menu that does not contain the target takes longer than scanning one with it. This can be explained by exhaustive visual search: Novice users have to scan all items to ensure the target is absent.

Practice:

Performance improves with more experience with the same menu [START_REF] Cockburn | A predictive model of menu performance[END_REF][START_REF] Kaptelinin | Item recognition in menu selection: the effect of practice[END_REF][START_REF] Somberg | A comparison of rule-based and positionally constant arrangements of computer menu items[END_REF]. One explanation is that when the layout is stable, users remember the location of items and can directly glance at them [START_REF] Somberg | A comparison of rule-based and positionally constant arrangements of computer menu items[END_REF]. Moreover, three studies [START_REF] Card | User perceptual mechanisms in the search of computer command menus[END_REF][START_REF] Mcdonald | Searching for items in menus: The effects of organization and type of target[END_REF][START_REF] Mehlenbacher | Finding information on a menu: linking menu organization to the user's goals[END_REF] show that the effect of organization disappears with practice [START_REF] Byrne | Act-r/pm and menu selection: Applying a cognitive architecture to hci[END_REF].

6. Mouse control: Users mainly exhibit two strategies to coordinate its movement with the eyes: 1) a single move once the target item has been located by visual search and 2) the tracking strategy where the cursor trails the eye gaze [START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF]. The latter one decreases time and the contribution of pointing, because the cursor is already closer to the target. The mouse cursor can also be used to tag an item while the eyes are free to move elsewhere and access additional knowledge [START_REF] Cox | The role of mouse movements in interactive search[END_REF].

Our decision to focus on these effects leaves out some other phenomena for future work. One such effect is naming: Item labels that are clearly associated with the target goal are quicker to localize [START_REF] Brumby | Good enough but I'll just check: web-page search as attentional refocusing[END_REF][START_REF] Mehlenbacher | Finding information on a menu: linking menu organization to the user's goals[END_REF]. Another one is distractors: Searching for a number among letter distractors is faster than searching for a letter [START_REF] Anderson | The Atomic Components of Thought[END_REF]. The density of items impacts also visual search [START_REF] Halverson | Local density guides visual search: Sparse groups are first and faster[END_REF][START_REF] Nilsen | Exploring the divide between two unified theories of cognition: modeling visual attention in menu selection[END_REF]. Related to this is the saliency effect: Items that are salient in terms of color or size can be easier to localize. We believe that our scope is justified on the basis that all six effects have been replicated and bear large effects.

Overview of Previous Models

The main difference between mathematical and simulation models is that the latter have a richer description of visual search strategies and assume it to dominate total selection time. Our goal is to incorporate their findings to a mathematical model.

Mathematical models:

The models pre-dating the SDP model assume a linear relationship between item position and search time [START_REF] Lane | Predicting the skilled use of hierarchical menus with the keystroke-level model[END_REF]. The SDP model (Search-Decision-Pointing) [START_REF] Cockburn | A predictive model of human performance with scrolling and hierarchical lists[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF] is a regression model using four variables and seven parameters to predict total selection time. Contrary to the simulation models, it has only a random model of search and it places more emphasis on decision and pointing time. The four predictors are: Number of items, item frequency, spatial consistency and item position.

SDP covers some of the phenomena mentioned above: 1) the Search component predicts that the time to localize an item increases linearly with the number of items in the menu. However, the position effect is only explained by pointing time, not by localization time. 2) The Decision component predicts that the time to decide among items depends on the "entropy" of their relative frequencies in previous selections. It is given by the Hick-Hyman law. 3) The Pointing component is based on Fitts' law [START_REF] Mackenzie | Fitts' law as a research and design tool in human-computer interaction[END_REF] and predicts that items closer to the top are faster to select. Furthermore, mouse movement starts after search. 4) Finally, an expertise scalar modulates the components by the number of repetitions with an item. With practice, performance shifts from being dominated by search (linear) to decision (logarithmic). 6) The model includes a scalar "predictability" variable (1: unchanging, 0: constantly changing order) that predicts a detrimental effect of spatial consistency. With these assumptions, the SDP model has been extended to scrolling lists and hierarchies [START_REF] Cockburn | A predictive model of human performance with scrolling and hierarchical lists[END_REF], square and circular layouts [START_REF] Ahlström | Why it's quick to be square: modelling new and existing hierarchical menu designs[END_REF] and interaction with constrained devices [START_REF] Cockburn | A model of novice and expert navigation performance in constrained-input interfaces[END_REF].

Simulation models mainly refer to visual search as the explanatory factor for the above effects. EPIC (Executive Process Interactive Control) [START_REF] Kieras | An overview of the epic architecture for cognition and performance with application to human-computer interaction[END_REF] consists of a production-rule cognitive processor and perceptual motor peripherals. Their execution is limited by temporal and capacity limitations posed by the cognitive infrastructure [START_REF] Halverson | A computational model of active vision for visual search in humancomputer interaction[END_REF][START_REF] Hornof | Cognitive modeling reveals menu search in both random and systematic[END_REF][START_REF] Hornof | Cognitive modeling demonstrates how people use anticipated location knowledge of menu items[END_REF]. Four strategies are distinguished for menus [START_REF] Hornof | Cognitive modeling reveals menu search in both random and systematic[END_REF]: serial search (one menu item processed at a time), parallel search (many items processed at the same time), random search, and systematic search. The last two are combination of the others. Data suggested that parallel search with both random and systematic search matched well observed data. ACT-R/PM [START_REF] Byrne | Act-r/pm and menu selection: Applying a cognitive architecture to hci[END_REF] extends ACT-R [START_REF] Anderson | Act-r: a theory of higher level cognition and its relation to visual attention[END_REF], which is also a production rule architecture. It differs from EPIC in the details of the visual search process [START_REF] Nilsen | Exploring the divide between two unified theories of cognition: modeling visual attention in menu selection[END_REF]. ACT-R/PM posits a systematic, top-to-bottom search with eye fixations on menu items that share features with the target item [START_REF] Anderson | Act-r: a theory of higher level cognition and its relation to visual attention[END_REF]. In constrast, EPIC posits a 50/50 blend of random and systematic search with eye fixations determined by the number of menu items visible in the fovea. However, a study found that neither EPIC nor ACT-R is a good characterization users' behavior [START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF]. The assumptions concerning mouse movements also differ. EPIC predicts, similar to SDP, that there is a single aimed mouse movement from the initial position to the target item once the target has been located. Timing of this movement should be governed by Fitts' law [START_REF] Mackenzie | Fitts' law as a research and design tool in human-computer interaction[END_REF]. ACT-R, on the other hand, predicts that the mouse should "trail" the eyes such that once the target is located, there is an approximately constant and short distance to the target. This predicts multiple mouse movements that are correlated with the number of eye movements.

MODEL OVERVIEW

The model has four input variables: target position (1-16), menu length [START_REF] Byrne | Act-r/pm and menu selection: Applying a cognitive architecture to hci[END_REF][START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF][START_REF] Card | User perceptual mechanisms in the search of computer command menus[END_REF][START_REF] Card | The Psychology of Human-Computer Interaction[END_REF][START_REF] Cockburn | A predictive model of human performance with scrolling and hierarchical lists[END_REF][START_REF] Cockburn | A model of novice and expert navigation performance in constrained-input interfaces[END_REF][START_REF] Cockburn | A predictive model of menu performance[END_REF][START_REF] Cox | The role of mouse movements in interactive search[END_REF][START_REF] Fu | Snif-act: a cognitive model of user navigation on the world wide web[END_REF], menu organization (unordered, alphabetical, semantic), and number of previous encounters with the item [START_REF] Ahlström | Why it's quick to be square: modelling new and existing hierarchical menu designs[END_REF][START_REF] Anderson | The Atomic Components of Thought[END_REF][START_REF] Anderson | Act-r: a theory of higher level cognition and its relation to visual attention[END_REF][START_REF] Bailly | Flower menus: a new type of marking menu with large menu breadth, within groups and efficient expert mode memorization[END_REF][START_REF] Bailly | Menuoptimizer: Interactive optimization of menu systems[END_REF][START_REF] Brumby | Good enough but I'll just check: web-page search as attentional refocusing[END_REF][START_REF] Brumby | Strategies for guiding interactive search: An empirical investigation into the consequences of label relevance for assessment and selection[END_REF][START_REF] Byrne | Act-r/pm and menu selection: Applying a cognitive architecture to hci[END_REF][START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF][START_REF] Card | User perceptual mechanisms in the search of computer command menus[END_REF][START_REF] Card | The Psychology of Human-Computer Interaction[END_REF][START_REF] Cockburn | A predictive model of human performance with scrolling and hierarchical lists[END_REF]. The model is in a mathematical form that allows deriving both total menu selection time and gaze distribution.

The assumption is that the total time to select an item consists of time spent in two consecutive subtasks-search and pointing-and both are affected by learning (Figure 1):

• Search uses the recruitment of eye gaze and memory recall to identify the position of the target in the menu by scanning it. We follow previous simulation models [START_REF] Hornof | Cognitive strategies for the visual search of hierarchical computer displays[END_REF][START_REF] Hornof | Cognitive modeling reveals menu search in both random and systematic[END_REF] and assume two search strategies:

-Serial search consists of top-to-bottom reading of items that, with practice, allows more skipping. This is modeled as a uniform distribution from the beginning of the menu to the target. -Directed search consists of a direct attempt at moving the eyes on top of the target. At first such attempts are random, as the user tries to guess the location, but with more exposure they become more accurate. We model directed search as a normalized Gaussian distribution centered on the target. • Pointing: After localizing the target, the target is selected by pointing. Pointing time is modeled with Fitts' law, like in previous models. However, like [START_REF] Byrne | Act-r/pm and menu selection: Applying a cognitive architecture to hci[END_REF], we assume two starting locations of the cursor: 1) the first at the top of the menu, 2) the other from a constant distance in the vicinity of the target (trailing). • Learning: Our learning model is a power law of practice model [START_REF] Newell | Mechanisms of skill acquisition and the law of practice[END_REF] which is parametrized for each search component. The negative exponential form of the law implies that largest gains are achieved in the first repetitions, and the gains diminish rapidly after that.

Total Selection Time

Total selection time T is the sum of time spent in serial search T s , directed search T d , and pointing T p :

T (✓) = T s (✓) + T d (✓) + T p (✓) (1)
where ✓ = (l, t, P ) is a vector containing the four input variables: length of the menu l, position of the target t, and a vector giving the number of previous encounters with the items in the menu P (practice).

An original aspect is to explain where (e.g., on which item) the eyes spend time. The total time for selecting target t is the sum of the gaze time required for each item i of the menu. The relationship between total time and the gaze distribution for each component is:

T (✓) = 1 R i=l X i=0 G s (i, ✓) + G d (i, ✓) + G p (i, ✓) (2)
where G s , G d , G p estimate the numbers of gaze points (serial, directed, and pointing) captured using an eye-tracker with a sampling rate of R. In our studies, R = 50Hz.

Serial search

Serial search refers to the top-to-bottom inspection of items. Items after the target are not visited. With practice, users not only skip more items but also spend less time on each visited item. For this reason, the number of gaze points on each item in a menu is not constant but decreases as a function of repetitions. The number of gaze points for i when looking for target t is:

G s (i, ✓) = ⇢ a s ⇥ exp( b s ⇥ p i ) + c s if i  t 0 otherwise ( 3
)
where a s , b s , c s are the parameters of the learning model, while p i is the number of previous encounters with item i.

Directed search

In directed search the user tries to glance directly at the target. Attempts are initially more random, but the spread of gaze distribution decreases with more repetitions. As experienced users have memory about the general location of the target, they can glance at the neighborhood of the target and, eventually, directly move the eyes to it [START_REF] Card | The Psychology of Human-Computer Interaction[END_REF]. As in serial search, we assume that experienced users also skip more items and spend less time reading them than novices.

We thus model this distribution of gaze with a normal distribution centered on the target item t. Probability for item i in the menu is given by its probability density function t, 2 d (i) modulated by the power law of learning:

G d (i, ✓) = t, 2 d (i) ⇥ (a d ⇥ exp( b d ⇥ p i ) + c d ) (4)
where d is the standard deviation reflecting the spread of the search area. a d , b d and b d are the empirical parameters of the learning model. Note that the sum in Eq. 2 ranges from the first item to the end of the menu (i 2 [1, l]), but not longer, because we assume that users only search inside the menu.

The spread d reflects the accuracy of memory-directed search and depends on the number of previous encounters p t with the target. The amplitude of the distribution reflects the amount of time spent in the search area and is affected by the power law of practice. We assume that the spread d is also affected by menu length: Longer menus have more uncertainty and users are more likely to visit more items:

d (i) = l ⇥ a exp( b ⇥ p i ) + c (5)
where a , b and c are the parameters of the learning model. Note that two learning components affect the gaze distribution: The first affects the tendency to engage in directed search (amplitude), the second the accuracy of perceptual memory (spread).

Pointing

Pointing is the time the eyes spend on the target to make the selection after it has been localized. The pointing time is predicted by Fitts' law [START_REF] Mackenzie | Fitts' law as a research and design tool in human-computer interaction[END_REF]:

T p = a + b ⇥ log 2 (1 + ID) with ID = D W ( 6
)
where ID is the index of difficulty. In our model, D t is the distance from the cursor position to the target position when starting the pointing task. Evidence [START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF] suggests that the cursor sometimes trails the eye gaze and can be in the vicinity of the target when this one is localized. However, the distribution of these two strategies (starting from the top vs. starting in the vicinity) is not known. The average distance D t is thus defined with a weighing parameter ↵:

D t = ↵ ⇥ d t + (1 ↵) ⇥ d 0 (7)
where ↵ reflects the relative usage of the two strategies; d t = t ⇤ W is the distance from the top of the menu to the target and d 0 the distance from the cursor to the gaze when using the trail strategy. We assume that d 0 = 0.

T p = a + b ⇥ log 2 (1 + ↵ ⇥ t) (8)
We can thus estimate G p . However, to account for the fact that users can see 2-5 items in the neighborhood of the gaze point, we revisit the equation 8. We add a normal distribution t,1.1 (i) that covers the dispersion of gaze in the items around the target:

G p (i, ✓) = a p + b p ⇥ log(1 + ↵ ⇥ t) ⇥ t,1.1 (i) (9)
where t,1.1 is a normal distribution centered around the target t with a standard deviation equal to 1.1. This reflects that 95% of the gazes are in the users' (extended) fovea.

Absent items

We also provide a simple model for deciding that an item is not in the menu. We assume that search time here only depends on menu length. If users do not know the menu content (p = 0), they inspect all items. They then become quicker at detecting missing items. The model is:

T a (✓) = a a ⇥ exp( b a ⇥ P a ) + c m ( 10
)
where a a , b a , c a are three components of the learning model.

We expect here having a large b a reflects that users quickly acquire knowledge about absent targets.

DATA COLLECTION

The experimental design is based on and extends Nielsen [START_REF] Nilsen | Perceptual-motor control in human-computer interaction[END_REF]. In the experiment, a label is shown and the participant must click the corresponding item as quickly as possible. Distinctive properties of the method include:

• eye fixation and mouse movement data are collected to understand visual search and pointing behavior (cf. [START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF]) • item selections are repeated multiple times to understand practice effects • three different organizations of the items are included (unordered, alphabetical, semantic).

Participants, Apparatus and Setup

Twenty one participants (13 females), ages 18 to 26 years (mean=21.1, =3.54), were recruited by email list advertisements, and paid 45 euros for participation. All participants had normal or corrected-to-normal vision, were familiar with WIMP interfaces, and used menus regularly.

The experiment was conducted on a windows PC and a 20 LCD display at 1280x960 resolution. A traditional optical mouse was used. All Participants used the same sensitivity and acceleration of the mouse.

We used an 1750 Tobii eye-tracker. The sampling data rate is 50Hz (raw eye movement data points every 20 ms); the latency was 20ms and the spatial resolution is 0.25 degrees (0.19cm on the screen) while the height of an item is 0.75 cm. The distance of the users' eyes from the screen was 65cm. It means that participants can simultaneously focus on 3 items if we consider a fovea of 2 degrees.

Experimental Design

The experiment used within-subjects design with four independent variables: Menu length, Menu organization, Practice, and Target location as the main factors. Menus contain 8, 12 or 16 items that are common menu lengths in current applications [START_REF] Malacria | Promoting hotkey use through rehearsal with exposehk[END_REF]. We tested three menu organizations: Unordered, Alphabetical and Semantic organization. In the semantic organization, logical groups contained 4 items for all menu lengths. 4 items were chosen because it is the average number of items per logical groups according to [START_REF] Bailly | Flower menus: a new type of marking menu with large menu breadth, within groups and efficient expert mode memorization[END_REF]. Logical groups were separated by an horizontal line (separator) like traditional linear menus. To investigate the impact of practice, participants carried out 12 blocks per menu. Each item is selected the same number of times. Additionally, we added a missing item in each block. The order of menu length as well as menu organization was counter-balanced between participants. Participants searched one menu organization per session. Menu length was counter-balanced between menu organization. For each layout, participants performed at least 4 blocks. Finally, the order of items was randomized within block. In summary, we have: 22 participants x 3 Menu configurations x 3 Menu Length x 12 blocks (depending on menu length) x (8-12-16 items) = 39,564 selections.

Task and materials

The task consists of selecting the target as fast as possible.

Each trial starts with a single button on the screen. As soon as the cursor enters in the button, the stimulus (label of the target item) appears just above the button (to avoid possible occlusion). The selection task started as soon as participants pressed the button. The label then disappears and the menu appears. The task finishes when participants activate the correct target and then the menu disappears. In the case of missing items, it finishes when participants press the space bar.

We identified several kinds of stimuli in the literature on menus: the explicit target name, a synonym, the definition of the target or an icon [START_REF] Brumby | Good enough but I'll just check: web-page search as attentional refocusing[END_REF][START_REF] Mehlenbacher | Finding information on a menu: linking menu organization to the user's goals[END_REF]. In this experiment, we used the explicit target name to avoid confound effect.

The same set of items was used for each menu organization. The set of items was changed for each menu length. The set of words that we used is a subset of the list that can be found in [START_REF] Halverson | The effects of semantic grouping on visual search[END_REF] with minor modifications: no items in the menu have more than 3 letters length difference. This modification was used to reduce potential saliency effects.

To assess the validity of semantic groupings, seven participants were asked to rate the semantic relatedness (0 to 100) of 120 pairs. Item-pair order was scrambled and the respondents did not know if they originated from a semantic menu or not. We found that items that are in the same semantic group had average relatedness of 44.4 ( = 26.0) whereas other items had 16.0 ( =10.0). A two-sample unequal variance t-test found this difference to be statistically significant, t(47) = 6.828, p < 0.0001.

Procedure

After introduction to the task, the eye tracker was calibrated.

During the experiment, participants took a break every 50 selections. We forced the minimum duration of the break to 1 minute to avoid fatigue. Breaks between conditions were used to re-calibrate the eye-tracker. The experiment was split into 3 sessions of 90 minutes each. The time between two sessions was from 0 to 7 days depending of the schedule of the participants. Participants were instructed to select items as fast as possible. They were not instructed about the layout and the length of the menu they will use. Finally, before the experiment, participants performed a calibration task consisting of selecting a target in a menu with a single item.

RESULTS

To preprocess the data, we removed trials in which selection times were greater than 3 SDs from the mean and trials in which the participant did not correctly select the target on the first attempt. Using these criteria, 3.83% (1,515 out of 39,564) of trials were excluded. In all subsequent analysis, one block has 3 repetitions.

Inferential statistics

To gain an overview of the data we carried out a series independent Organization ⇥ Practice ⇥ Target position ANOVAs on the selection time data. Table 1 provides a summary of the results of this analysis. To simplify our discussion, we focus on the effects that the experiment was designed to replicate and extend: (1) practice effect, (2) target position effect, (3) absent target effect, (4) menu length effect, and (5) menu organization effect. These effects are shown in Figure 2. Practice effect. Table 1 shows that there was a consistent effect of Block, reflecting that users became faster at locating the target with repeated practice at searching the same menu. Table 1 also shows that there were significant interactions between Block and the other factors. Target position effect. There was a robust effect of Target position on search time (see Table 1). To understand this effect, Figure 2 plots selection time as a function of target position for different menu lengths for the first (2-a) and last block (2-b) of trials. It can be seen that during the first block, selection time tends to increase with target position. By the last block of trials, this target position effect has decreased (i.e., the curve has flattened). Absent target effect. Recall that on some trials the menu did not contain the target (an absent target trial). On these trials the participant had to press the space bar to indicate that it was absent. Response times are shown in the Figure 2a -b (at 0 on the x-axis). It can be seen that participants were initially very slow at making these absent target decisions during the first block of trials (particularly for 12-and 16-item menus). By the last block of trials, participants were very quick at indicating when there was an absent target. Menu length effect. The data replicate Nilsen's menu length effect: selection times were longer for targets in a given position when the menu contained more items. To test this effect, we performed a Length ⇥ Organization ⇥ Practice ⇥ Targetposition ANOVA on a subset of the data: trials in which the target was in position 1 to 8. As expected, there was a significant main effect of menu length, F 2,40 = 70.44, p < .001. However, there was also a significant Length ⇥ Block interaction, F 6,120 = 8.84, p < .001. With practice, the effect decreases from the first to the last block (Figure 2a b). Menu organization effect. Figure 2c d shows the menu organization effect. Participants were faster at selecting targets when the menu had either an alphabetic or semantic organization compared to when it had an unordered organization. Reflecting this observation, statistical analysis shows that there was a consistent main effect of menu organization across (see Table 1). There was also significant organization ⇥ block interactions for the longer 12-item and 16-item menus. As can be seen in Figure 2, these interactions reflect that with practice the menu organization effect diminished.

In contrast with the Nilsen experiment, we observed a last item effect: Items that are positioned toward the end of the menu are faster to select. It is the opposite of what would be expected by the Fitts' law. We return to this effect later in the paper and show that our model explains this effect as well as the previous effects and their interaction with practice.

Observations of Pointing Strategies

We here report observations for pointing. We return to gaze distributions in the Modeling section.

The model of pointing in Eq. 9 assumes that there are two strategies of mouse control and the proportion of these is regulated by the parameter ↵. Figure 3 shows two examples of cursor controls for the same target position: on the left trailing behavior, on the right the single move behavior. To better understand cursor control and to derive ↵, we looked at the position of the cursor upon localizing the target. To identify this moment, we used a simple heuristic: we assumed localization to take place at the beginning of the last fixation to the target item (Figure 3). This estimate is conservative, because it does not take into account the time needed to identify Time (s)

Item position

Gaze Cursor the target. Figure 4 shows the relative proportion of mouse strategy according to the target position. Data confirm our assumption that pointing and search are not always sequential.

Visual Search Pointing

MODELING

In this section, we estimate parameters and report model fit. Unlike previous models of menu selection, our approach allows assessment at three levels of granularity: Selection time for menu, Selection time for targets, and Gaze distribution. We used trials containing no missing gaze data (85% of the trials). This is important because we derive selection time from the gaze distribution (integration). Two participants were removed due to incompatibility with the eyes tracker (less than 65% of valid trials). It results in 19690 trials aggregated between participants.

Parameter Estimation

The model consists of 4 independent variables. For each menu organization, we have 12 parameters, 5 of which are shared by all menu organizations. Five parameters were estimated by analysis of user performance in selected conditions. The rest were solved using ordinary least squares (OLS), but insisting on theoretically sound value ranges. Note that we assume that both visual search strategies depend on menu organization: Unordered (U), Alphabetic (A), Semantic (S) [START_REF] Card | User perceptual mechanisms in the search of computer command menus[END_REF][START_REF] Halverson | The effects of semantic grouping on visual search[END_REF][START_REF] Mcdonald | Searching for items in menus: The effects of organization and type of target[END_REF][START_REF] Mehlenbacher | Finding information on a menu: linking menu organization to the user's goals[END_REF]. The parameters of Eq. 3, 4, 5 are thus fitted separately for each menu type.

Serial seach: Parameters a s and b s were obtained by OLS. For the three menu types, this yielded a s =[U: 2.04; A: 1.48; S: 1.05] and b s =[U: 0.15; A: 0.07; S: 0.09]. Second, we assume c s is the same for every menu. This reflects the observation that an expert user can directly glance at the target regardless of the menu organization. We estimated c s based on our Fitts' law calibration task to be c s = 0.2. Notice that all parameters (a s , b s , c s ) are positive, describing that users abandon serial search with practice. We also note that they spend more time in serial search with the unordered menu (a = 2.1) that with the two other organizations Pointing: We used data from the Fitts' law calibration task to estimate the parameters of Eq. 9 as a p = 10.3 and b p = 4.8. We consulted Figure 4 to set ↵ = 0.4. These parameters are organization-independent.

Absent target: We used OLS on the data of absent items and set the parameters to: a m = 3.75, b m = 1.14, and c m = 23.8. We assume these parameters to be independent of menu organization, because every item is read.

Pre-search gaze

Figure 5 shows deployment of gaze on the stimulus before searching the menu. This occurs because users in the study processed the stimulus even a couple of milliseconds after having opened the menu. To cover this in the model, we added a component Pre-search: a normal distribution centered around the stimulus location (above the menu). It reflects the dispersion of gaze around the stimulus. We assume this component to be constant:

G pre (i) = a pre ⇥ S, pre (i) (11)
where a pre = 6, p re = 1.0 were defined using OLS. The two parameters are, respectively, the amplitude of the normal distribution and the standard deviation (spread). S = 0.5 is the position of the stimulus.

Model Fit

We report fit for three levels of analysis: Selection time for Menu, Selection time for Target and Gaze Distribution. The parameter values reported above were utilized for all three levels. Models fit are based on the whole data set. We also report at the end of this section a 2-fold cross-validation to avoid possible overfitting. All predictions for the whole design of the experiment are given in Supplementary Materials.

Selection time averaged for menu: Empirical data matched the predictions well for organization, length, and practice, as shown in Figure 6. Model fit was R2 = 0.95 (pred = 0.93 ⇥ emp 0.01) for Unordered, R 2 = 0.89 for Alphabetic (pred = 1.09 ⇥ emp 0.09) and R 2 = 0.78 for Semantic (pred = 1.84 ⇥ emp 0.74).

Selection time per target: Model fit was R 2 = 0.76 for Alphabetic (pred = 0.76 ⇥ emp + 0.24), 0.71 for Unordered (pred = 0.87 ⇥ emp + 0.25) and R 2 = 0.61 for Semantic (pred = 0.43 ⇥ emp + 0.54). While the absolute value is inferior to the menu-level prediction, many more observations must be predicted 1 . Figure 7 shows a sample of observed vs. predicted values for the different conditions. The model predicts the known effects of target position, menu length, and practice. It also predicts that selection time does not linearly increase with target position. More surprisingly, it predicts the decrease in selection time for the last item (last item effect). These two last effects can be explained by the Eq. 4, which models gaze distribution by a normal distribution centered around the target. When the target is the last in the menu, the predicted gaze distribution is effectively "cut" for items after the menu, lowering the total amount of gaze for that target item. This reflects the observation that users hardly look at the area below the menu. We also observe a limitation of our model for the semantic organization. Selection time increases quickly as a function of target position, especially for the first block. This can be explained by the serial search component. We assumed that users inspect all items from the top of the menu to the target. We hypothesis that users can skip more items with the semantic menus by using logical groups and separators.

Gaze Distribution. This prediction task has 13,800 points to predict (gaze for each item according to target, length, organization and practice). However, empirical data match the model surprisingly well, yielding a fit of R 2 = 0.90 for both Unordered (pred = 0.90 ⇥ emp + 0.05) and Alphabetic (pred = 0.85 ⇥ emp + 0.40) and R 2 = 0.76 for Semantic (pred = 0.81 ⇥ emp + 0.92). One sample is shown Figure 8. We provide more examples in Supplementary Materials.

Unordered Semantic

Alphabetic

Last block First block

Cross-validation

We performed a 2-fold cross-validation analysis to test the generalizability of our model. We calibrated the model parameters on half of the participants and tested it on the others. The R-squared is still high at the menu level (A: 0.91; S: 0.86; U: 0.87), target level (A: 0.64; S: 0.52; U: 0.56) and item level (A:0.85; S: 0.81; U:79).

DISCUSSION

The present paper advances the understanding of menu performance by providing a mathematical model that better accounts for pointing behavior and visual search. It achieves this by combining assumptions about search and pointing strategies that have been identified by previous literature but never modeled in a single model.

We proposed a novel formalization to capture these behaviors. Instead of modeling sequences of elementary operations, like in cognitive simulations, or a linear sum of time spent in sub-tasks, we model the distribution of gaze. The benefit is that the area under the curve is an estimate of the total selection time. Thus, the same model can be used for predicting both dependent variables. The data support the assertion that modeling visual search distributions is a promising approach to mathematical modeling of linear menu performance. The predicted distributions not only yield a good fit but they provide insight into the process of search.

We conclude with a critical appraisal of the model in the light of six criteria for predictive models by Jacobs and Grainger [START_REF] Jacobs | Models of visual word recognition: Sampling the state of the art[END_REF]:

1. Plausibility: Are the assumptions of the model psychologically plausible? 2. Explanation: Is the theoretical explanation reasonable and consistent with what is known? 3. Interpretability: Do the model and its parameters make sense? 4. Descriptive adequacy: Does the model provide a good description of the observed data? 5. Complexity: Does the model capture the phenomenon in the simplest manner? 6. Generalizability: Does the model predict the characteristics of data that will be observed in the future? Plausibility. We modeled pointing time with Fitts' law as previously, but with the additional assumption that the distance to target depends on the selected pointing strategy. One strategy starts from the top, the other trails the eyes. The two strategies were included in previous work but never in a single model [START_REF] Byrne | Eye tracking the visual search of click-down menus[END_REF]. Visual search was also modeled by assuming two strategies: serial and directeded search. The direct search component makes the assumption that search is random in the beginning of experience, but becomes gradually more accurate. It thus subsumes a model of random search assumed in previous works (e.g [START_REF] Cockburn | A predictive model of menu performance[END_REF]). Unlike the SDP model [START_REF] Cockburn | A predictive model of menu performance[END_REF], our model does not assume a separate component for decision. More work is needed to understand the role of decision processes in menu selection.

Explanation. The model increases our ability to cover important design factors by a single model. The model covers the effects of menu organization, absent item, and target position, as well as the previously modeled factors of menu length and experience. The model also describes the"last item effect" that was not reported in the literature and is counter-intuitive. Interpretability. Our modeling assumptions come from previous work. Moreover, the model increases the interpretability of mathematical models in this area by linking selection time to gaze. The model makes predictions of gaze distribution that are verifiable with eye-tracking data. Descriptive adequacy. The model not only provides a high fit at the menu level but also at the target and gaze level. This multi-level approach decreases the risk of over-fitting and better describes the collected data. It is the main difference with previous models. Complexity. Our model is more complex if measured by the number of free parameters, but the ratio of parameters against explained observation points favors our model. A single parametrization was used to describe 13800 gaze points, 432 target-level selections, and 36 menu-level selections. Generalizability. To test the generalizability of our model, we provided a cross-validation result that were mostly favorable to our model. However, novel experiments should be carried out to test generalizability to completely different contexts, for example including other menu organizations, layouts, etc.

We see two opportunities to develop the model further. First, more work is needed to cover other common features of linear menu designs (e.g., icons) as well as more complex menu systems that include hotkeys, toolbars, and hierarchical menus. This means that semantic relatedness among items must be modeled to predict their effect on navigation and exploration behavior [START_REF] Fu | Snif-act: a cognitive model of user navigation on the world wide web[END_REF]. Second, although we are now better able to model search strategies, our model only predicts averaged behavior. This unfortunately can make the approach "fragile" to the sample of users. Were the distribution of strategies to change in the sample, the averaged prediction may not hold.

Future work also needs to consider a more thorough exploration of the strategy space implied by the statistical distribution of menu relevance and the cognitive constraints. For example, Smith et al. [START_REF] Smith | More than 8,192 Ways to Skin a Cat : Modeling Behavior in Multidimensional Strategy Spaces[END_REF] reported a multi-dimensional analysis of the space of possible typing strategies and showed that the assumption that people adopt rational strategies can be used to predict performance. We are currently building a similar analysis of menu search that is aimed at revealing the details of how directed and serial search strategies are combined depending on (1) the availability and precision of relevance and location knowledge and (2) the ecological distribution of relevance and organizational factors in real-world menus.

Figure 1 .

 1 Figure 1. We predict total selection time as a gaze distribution that is the sum of three components: Serial search, Directed search and Pointing.

Figure 2 .

 2 Fig 2a. First block

Figure 3 .Figure 4 .

 34 Figure 3. Two cursor control strategies for selecting the target 13 (dark grey). Left: The cursor (solid) trails the eyes gaze (dash). Right: A single mouse move when the target has been localized.

  [1.48, 1.05]. Directed search: The two parameters a d =[U: 4.83; A: 4.28; S: 4.36], b d =[U: 0.03; A: 0.03; S: 0.03] of the power law of practice, as well as the three describing the spread of directed search, a =[U: 0.14; A: 0.14; S: 0.27], b =[U: 4e-9; A: 1e-9; S: 5e-9] and c =[U: 1.2; A: 1.5; S: 1.24], were obtained using OLS. That all parameters are positive reflects that not only users spend less time on each item but they also reduce the search area. Additionally, b d , b and b are very similar whatever the menu organization indicating that the organization only impacts the initial amplitude and the initial size of search area. Finally, c d = c s = 0.2.

Figure 5 .

 5 Figure 5. Gaze distribution for the target 3 and 11 aggregated across users. The plot shows that gaze occurs also in the vicinity of the stimulus (above the menu).

Figure 6 .

 6 Figure 6. Observed vs. predicted menu selection times by menu organization, menu length an practice.

Figure 7 .Figure 8 .

 78 Figure 7. Observed (solid) vs. predicted (dash) menu selection time per target, organization length for the first and last block

Table 1 .

 1 Summary of main effects and interactions for search time data.

	Length	Organization (O)	Practice (P)	Target (T)	OxP OxT PxT	OxPxT
	8	**	***	***	n.s.	***	*	**
	12	***	***	***	***	***	***	n.s.
	16	***	***	***	***	***	***	*

Note: * p < .05, ** p < .01, *** p < .001

We reanalyzed Cockburn et al.'s data[START_REF] Cockburn | A predictive model of menu performance[END_REF] for selection time per target. Their fit is at

R 2 = 0.42 for this task. The analysis was based on data available at www.cosc.canterbury.ac.nz/ ˜andy/publs/ chi07/.

ACKNOWLEDGMENT

We thank M. Scholtes, M. Staudte and A. Bulling. This research was funded by the Max Planck Centre for Visual Computing and Communication and the Cluster of Excellence for Multimodal Computing and Interaction at Saarland University. Experimental data and model derivation calculations at www.gillesbailly.fr/menumodel.