Waqas Javed

Kyungtae Kim

Sohaib Ghani

Niklas Elmqvist

Evaluating Physical/Virtual Occlusion Management Techniques for Horizontal Displays

We evaluate unguided and guided visual search performance for a set of techniques that mitigate occlusion between physical and virtual objects on a tabletop display. The techniques are derived from a general model of hybrid physical/virtual occlusion, and take increasingly drastic measures to make the user aware of, identify, and access hidden objects-but with increasingly space-consuming and disruptive impact on the display. Performance is different depending on the visual display, suggesting a tradeoff between management strength and visual space deformation.

Introduction

As digital tabletop displays are becoming increasingly inexpensive, common, and available to the mass market, they will also start to be integrated into everyday work environments. In fact, such devices may even totally replace standard desktop computers in the future; as a case in point, Wigdor et al. [START_REF] Wigdor | Living with a tabletop: Analysis and observations of long term office use of a multi-touch table[END_REF] describe the use of a tabletop display for a single user over the period of a year. However, tabletop displays are horizontal surfaces, and such surfaces invite placing physical objects on them [START_REF] Steimle | Physical and digital media usage patterns on interactive tabletop surfaces[END_REF], such as paper, books, and even coffee mugs. This will inevitably give rise to problems where these physical objects occlude virtual objects on the tabletop display (Figure 1). Fig. 1. Tabletop environment with physical objects (a laptop computer and a book) resting on its surface. The physical objects are occluding virtual objects on the display, so their outlines have been made to glow using one of our occlusion management techniques to indicate this.

Mitigating occlusion is not a new problem and has been addressed previously: for 2D desktop environments, hidden overlapped windows can be retrieved using the taskbar in Microsoft Windows or the dock in Mac OS X. More advanced techniques make windows semi-transparent [START_REF] Baudisch | Multiblending: displaying overlapping windows simultaneously without the drawbacks of alpha blending[END_REF], cut holes in them to expose hidden items [START_REF] Ishak | Interacting with hidden content using content-aware free-space transparency[END_REF], or spread them out to make hidden content accessible [START_REF] Ramos | Tumble! Splat! Helping users access and manipulate occluded content in 2D drawings[END_REF]. Other work considers situations when the user's hand and arm occlude the display on touch and pen-based systems [START_REF] Vogel | Occlusion-aware interfaces[END_REF][START_REF] Vogel | Shift: a technique for operating pen-based interfaces using touch[END_REF][START_REF] Vogel | Hand occlusion with tablet-sized direct pen input[END_REF]. However, with the exception of contextual display bubbles [START_REF] Cotting | Interactive environment-aware display bubbles[END_REF] and relations between virtual and digital media [START_REF] Steimle | Physical and digital media usage patterns on interactive tabletop surfaces[END_REF], little work has been performed on managing occlusion between virtual and physical objects beyond the user's own body.

We propose a framework for occlusion management in such hybrid physical/virtual environments based on three levels of occlusion management: awareness (knowledge that a particular target exists), identification (target is recognizable but cannot be interacted with), and access (the ability to fully interact with the target). These levels, together with additional characteristic parameters, define the design space of tabletop occlusion management. Using this design space, we derive six techniques that represent the spectrum of occlusion management: adding glow to the outlines of physical objects (GLOW, see Figure 1), displaying miniature icons of occluded objects (ICON), creating hybrid piles of virtual and physical objects (PILE), introducing a small overview map (MMAP), displacing virtual objects to empty space (MOVE), and, finally, replicating hidden area in unoccluded space (REPL).

Our evaluation of these techniques begins with a formative study intended to elicit requirements and constraints for a more in-depth evaluation. We then present results from two quantitative user studies designed to determine which technique was most efficient in managing occlusion. Both studies involved 12 (different) participants who performed unguided (Experiment 1) and guided (Experiment 2) visual search in the presence of both physical and virtual distracting objects. For Experiment 1, MOVE was the fastest technique, but the situation is reversed in Experiment 2, where displacing objects has a negative impact. We speculate that a combination is optimal.

Related Work

Existing research has studied occlusion management for virtual objects, for touch and pen-based interaction, and for tabletop displays. Below we review these in detail.

Virtual Occlusion

Windows often overlap in 2D desktop systems. To interact with an overlapped window, users must move, resize, or change the stacking order of windows. To avoid this problem, window managers typically provide ways to cascade or tile windows [START_REF] Bell | Dynamic space management for user interfaces[END_REF]. A window index, like the Windows taskbar or the MacOS Dock, allows for directly accessing windows even if they are hidden behind other windows. Another approach is to mitigate occlusion by placing windows in regions with the least overlap [START_REF] Bell | View management for virtual and augmented reality[END_REF].

Alpha blending [START_REF] Porter | Compositing digital images[END_REF] can be used to show the content of occluded windows using transparency. The problem with this technique is that it is difficult to visually determine which content belongs to which window. Multi-blending [START_REF] Baudisch | Multiblending: displaying overlapping windows simultaneously without the drawbacks of alpha blending[END_REF] addresses this issue through a framework of transparency filters to allow simultaneous display of transparent windows. Free-space transparency [START_REF] Ishak | Interacting with hidden content using content-aware free-space transparency[END_REF] selectively turns unimportant window regions transparent and important regions opaque to optimize visibility.

Physical Body Occlusion

Occlusion in both direct touch and pen-based interaction arises when the user's own hand or arm covers some portion of the display. Ample research has shown that this occlusion is problematic and can severely impede performance [START_REF] Hancock | Improving menu placement strategies for pen input[END_REF][START_REF] Inkpen | Left-handed scrolling for pen-based devices[END_REF]. Forlines et al. [START_REF] Forlines | Evaluating tactile feedback and direct vs. indirect in pointing and crossing selection tasks[END_REF] found that occlusion causes decay in performance in one-dimensional tapping and crossing tasks. Supporting this finding, Leithinger and Haller [START_REF] Leithinger | Improving menu interaction for cluttered tabletop setups with user-drawn path menus[END_REF], while investigating menu placement for tabletops, discovered that menus suffering from occlusion had significant disadvantages compared to other menus. In fact, Vogel et al. [START_REF] Vogel | Hand occlusion with tablet-sized direct pen input[END_REF] found that the user's hand and forearm can occlude up to half of a 12-inch display.

Various interaction techniques have been designed with occlusion in mind [START_REF] Apitz | CrossY: a crossing-based drawing application[END_REF][START_REF] Ramos | Fluid interaction techniques for the control and annotation of digital video[END_REF][START_REF] Zeleznik | Fluid inking: augmenting the medium of free-form inking with gestures[END_REF]. Hancock et al. [START_REF] Hancock | Improving menu placement strategies for pen input[END_REF] improve awareness in menu placement for tabletop display by designing menus that detects user handedness. Brandl et al. [START_REF] Brandl | Occlusion-aware menu design for digital tabletops[END_REF] also designed occlusion-aware menus that are positioned around the table so that they are not occluded. Some techniques actively mitigate occlusion for touch displays. Ramos and Balakrishnan [START_REF] Ramos | Fluid interaction techniques for the control and annotation of digital video[END_REF] use a sinusoidal-shaped slider to reduce occlusion from the user's hand in pen-based displays. CrossY [START_REF] Apitz | CrossY: a crossing-based drawing application[END_REF] uses right-to-left movement to reduce occlusion with right-handed users. Shen et al. [START_REF] Shen | CoR2Ds: Context-rooted rotatable draggables for tabletop interaction[END_REF] utilize a popup widget to overcome occlusion caused by the user's finger for touch displays. This is similar to Shift [START_REF] Vogel | Shift: a technique for operating pen-based interfaces using touch[END_REF], where a copy of the occluded region is moved to a non-occluded region. Building on this, more recent work on occlusion-aware interfaces [START_REF] Vogel | Occlusion-aware interfaces[END_REF] models which area is occluded and uses this knowledge to display hidden objects in a non-occluded screen area.

Physical/Virtual Occlusion

The environment-aware display bubbles presented by Cotting and Gross [START_REF] Cotting | Interactive environment-aware display bubbles[END_REF] are perhaps most relevant to our work. Their technique projects structured light onto the table to acquire inadmissible areas, which are then used to deform the display bubbles.

Recent work by Steimle et al. [START_REF] Steimle | Physical and digital media usage patterns on interactive tabletop surfaces[END_REF] studied usage patterns of physical and virtual media on tabletop surfaces. They found the expected drawbacks of physical occlusion, such as information hiding and interaction costs, but also-interestingly-some desirable features for organizing and partitioning information (particularly for hybrid piles [START_REF] Khalilbeigi | Interaction techniques for hybrid piles of documents on interactive tabletops[END_REF]). Their results indicate the need for tabletop interfaces to explicitly support physical interaction on, above, and around the surface, further motivating our work.

Motivation: Everyday Use of Tabletops

Already in 1991, Shneiderman [START_REF] Shneiderman | Interface-touch screens now offer compelling uses[END_REF] listed the advantages of touch displays and predicted that, as more research will overcome their disadvantages, they will become more and more popular. In 1993, Wellner [START_REF] Wellner | Interacting with paper on the DigitalDesk[END_REF] first described the idea of an office desk as a digital display. True to form, tabletops are nowadays becoming increasingly available to the mass market, and are starting to appear in showrooms, lobbies, and museums. With the decreasing cost of large display technology and increasing demand from a growing potential consumer base, the step to adoption in the living room-and certainly the office-cannot be far away. In a pioneering effort, Wigdor et al. [START_REF] Wigdor | Living with a tabletop: Analysis and observations of long term office use of a multi-touch table[END_REF] describe the use of a tabletop for long-term office use and its pros and cons.

Following this reasoning, it is plausible that in the future, digital tabletops will be commonly used as office desks-or rather, that many of our horizontal surfaces in offices (such as desks) will be appropriated as displays [START_REF] Harrison | Appropriated interaction surfaces[END_REF]. However, the physical affordance of horizontal surfaces also invite placing various physical items on them [START_REF] Steimle | Physical and digital media usage patterns on interactive tabletop surfaces[END_REF], such as coffee mugs, papers, books, etc. When the desk is also a digital display, these items will start to hide virtual objects on the display.

Occlusion Management on Tabletop Displays

We define tabletop occlusion management as methods that give awareness, identification, or access to virtual objects that are occluded by physical objects on tabletops.

Detecting Physical Occlusion

The first step towards managing physical occlusion is to detect it. For tabletop displays built using diffuse illumination (DI) [START_REF]Multitouch Technologies[END_REF], this is relatively easy. DI tabletops have active infrared emitters that cause reflections on a physical object resting on the tabletop surface, allowing the camera tracking system to detect its actual outline. Taken together, these outlines represent occluded space on the display, and become the input for all types of occlusion management techniques.

The single remaining difficulty is for tabletop systems that already rely on DI technology for the touch interaction (not all do-for example, SLAP widgets [START_REF] Weiss | SLAP widgets: bridging the gap between virtual and physical controls on tabletops[END_REF] use FTIR [START_REF] Han | Low-cost multi-touch sensing through frustrated total internal reflection[END_REF] for touch and DI for detecting objects), forcing us to distinguish between physical occluders and the hands of the users. We suggest using a heuristic based on the motion of an object-if an object has not moved for T (e.g., 10) seconds, we regard it as an occluder. Other approaches would be to require a minimum size for an object to be classified as an occluder, or to put fiducial markers on the undersides of physical objects on the display (the latter is not a general solution, however).

Finally, we should note that physical objects are three-dimensional, and thus also have a geometric extension above the table surface. This means that accurate occlusion detection should consider the line of sight of the user, whereas our implementation only utilizes the 2D footprint of an object on the tabletop surface. However, our techniques would also work with a line-of-sight based approach, and thus the technical limitations with our implementation do not affect the validity of our results. We discuss this aspect in more detail in the design implications section.

Levels of Occlusion Management

We define four levels of increasing occlusion management:  No knowledge: A virtual object is fully occluded by a physical object, and the user is unaware of its existence. The virtual object will remain hidden until the user happens to move or lift the occluding object.

 Awareness: A user that is aware of an occluded virtual object knows that one or more virtual objects are occluded by a physical object, but does not necessarily have knowledge about the number or identity of the hidden objects.  Identification: A user that can identify an occluded virtual object can see (part or a copy of) the virtual object, but cannot interact directly with the object. To interact with the object, the user must lift or move the occluding physical object.  Access: Having access to an occluded virtual object means that the user is able to fully view and interact with the object as if it was not hidden at all.

Design Parameters

We suggest four additional design parameters for classifying occlusion management:  Space Consumption: Amount of space utilized by the technique in addition to the space utilized by the physical objects themselves.  Visual Clutter: Degree of visual clutter produced. With occluded objects no longer visible, how much new clutter is introduced by the technique?  Spatial Transformation: Impact on the geometric properties of the visual space, including distortion, displacement, and rotation.  Intention Support: Intentional occlusion possible. The user may want to intentionally hide virtual objects using physical objects. Is this scenario possible? Fig. 2. Overview of occlusion management techniques evaluated in this paper. The large gray rectangle represents the footprint of a physical object placed on a tabletop display, thus occluding three virtual objects drawn on the actual display (ellipse, star, and pentagon).

Techniques

We derive six techniques for different levels of occlusion management. In Figure 2, we use a standard situation with three virtual objects (an ellipse, star, and pentagon) being occluded by a single physical object placed on the tabletop surface.

 Awareness-supporting: This type of technique only makes the user aware of occluded virtual objects without actually showing which objects are occluded. For this reason, such techniques take the least amount of visual space of all proposed techniques. They also respect the user's intention when hiding an object.  Glow (GLOW): Displays a colored glow around the outline of physical objects that are occluding one or more virtual objects (Figure 2(a)).  Identification-supporting: These techniques provide not only awareness, but also allow users to identify the occluded virtual objects. For this reason, the space consumption and visual clutter is often higher than for awareness-supporting techniques. However, while these techniques typically give hints about the occluded content (through miniatures or portions of the objects), the user is still required to manipulate the physical object to interact with the virtual objects.

 Icon (ICON):

This technique displays a fixed-size small visual representationi.e., an icon-of an original occluded object (Figure 2(b)). The icon will be displayed on the nearest edge of the occluding physical object in order to convey some information on where the hidden virtual object is placed.  Piling (PILE): This technique mimics a traditional office desk where people pile papers and books into neat stacks (Figure 2(c)). The technique organizes hidden virtual objects into piles under the occluding physical object, thus showing a small portion of the original objects as a hint to the user (similar to [START_REF] Khalilbeigi | Interaction techniques for hybrid piles of documents on interactive tabletops[END_REF]).  Minimap (MMAP): The minimap technique shows a miniature overview of the virtual space with physical objects outlined (Figure 2(d)). The user can refer to the overview to find the location of hidden objects.  Access-supporting techniques: This family of techniques gives the user full input and output access to hidden virtual objects. To make this possible, these techniques have high space consumption and visual clutter. However, the result is an entirely occlusion-free visual space with no physical object interaction necessary; on the other hand, users cannot intentionally cover virtual objects with physical items.  Move (MOVE): Moves hidden objects to the nearest edge of its occluding object (Figure 2(e)). Items can be connected to their original positions using a virtual spring, causing them to spring back when the occluder is removed.  Replicate (REPL): Inspired by Vogel et al. [START_REF] Vogel | Occlusion-aware interfaces[END_REF], this technique replicates the entire screen content of a particular physical occluder in a callout located in unoccluded space as close to the occluder as possible (Figure 2(f)). Objects are revealed in their natural size and their relative position is maintained. We do not claim that the above six techniques are exhaustive examples of the design space of physical occlusion management; additional possibilities include object indices, distortion, and labels, etc. We also do not claim that these techniques are novel; in fact, some explicitly derive from existing techniques such as Shift [START_REF] Vogel | Shift: a technique for operating pen-based interfaces using touch[END_REF], hybrid piles [START_REF] Khalilbeigi | Interaction techniques for hybrid piles of documents on interactive tabletops[END_REF], and occlusion-aware interfaces [START_REF] Vogel | Occlusion-aware interfaces[END_REF]. However, we do think these techniques are a representative sampling of the occlusion management design space.

Because our work is the first (to the best of our knowledge) to study techniques for managing occlusion between physical and virtual objects on a tabletop display, we wanted to perform a canonical evaluation of the problem. To inform the design of this evaluation, we first conducted a formative evaluation involving graduate students from our university. Below we discuss the design decisions made based on this study.

Evaluation Platform

For the purposes of evaluating the above techniques, we implemented a graphical framework in Java for multitouch tabletop displays based on the Piccolo 2D graphics API and the TUIO [START_REF] Kaltenbrunner | reacTIVision and TUIO: A tangible tabletop toolkit[END_REF] touch event protocol. The framework detects both finger touches as well as physical objects on the surface-an object that has not moved for a given time (10 seconds, in our case) is regarded as an occluder. We encourage the reader to view the paper's video for footage of our occlusion management software.

Formative Evaluation

We conducted a formative evaluation of the testing platform with three participants. All participants performed a jigsaw puzzle task where they reassembled a picture split into 3×3 tiles back into the original image. The tiles were randomly placed on the tabletop surface but were not rotated (in fact, tiles could only be moved, not rotated). We also randomly placed four sheets of paper (physical occluders) on the tabletop surface. Participants performed one reassembly task for each of our techniques.

Because of the formative nature of this evaluation, we did not collect any correctness or time measurements. However, we took careful notes of participant behavior. The qualitative feedback was very positive despite tracking inaccuracies inherent to our tabletop. While the jigsaw puzzle task with sheets of paper as occluders worked well, we found it difficult to control the placement of the occluders on the tabletop surface. Furthermore, even though we asked participants not to pile or remove occluders from the display, a common strategy was to initially move them out of the way before solving the task, thus neutralizing the impact of any specific occlusion management technique. This was an issue we needed to address in the full experiment.

Design Decisions

Based on the formative evaluation, we made the following decisions:  Low-level visual search tasks: Given our intent to build a solid foundation for physical/virtual occlusion management, we decided to select fairly low-level tasks involving visual search [START_REF] Treisman | Search, similarity, and integration of features between and within dimensions[END_REF] for our evaluation. Because visual search generally is split into guided and unguided search (depending on whether the user has a priori knowledge of the spatial position of the target or not), we decided to perform two separate experiments, one for each of these. We argue that these tasks are building blocks for higher-level tasks involving more complex objects like text documents and applications, so our results should therefore generalize even to such objects.  Static occlusion: Existing work [START_REF] Vogel | Occlusion-aware interfaces[END_REF][START_REF] Vogel | Hand occlusion with tablet-sized direct pen input[END_REF] on physical occlusion between a user's arm and the display deals with intrinsically dynamic situations with moving targets and occluders. However, the primary problem on tabletops is static occlusion caused by physical objects placed on the table surface. For this reason, and for the sake of simplicity, we do not consider dynamic situations in our evaluation. Nevertheless, our occlusion management techniques handle dynamic occlusion equally well as static occlusion, so we think that the results should again generalize to other settings. In fact, our framework implementation requires physical objects to be static on the tabletop surface for at least 10 seconds to be regarded as occluders.

Without being able to otherwise differentiate interaction touches and occluders, we think is a reasonable strategy for realistic occlusion management implementations.  Small targets: Occlusion can occur at many scales (such as for small icons vs. large documents) as well as on many levels (i.e., partial vs. total occlusion). On the basis that large and complex visual objects can generally be decomposed into many smaller objects, we opted to design our tasks for small and generic targets.  No physical objects: Based on our experience from the formative evaluation, we chose not to include any actual physical objects in this study, but instead simulated them using virtual objects placed in the top layer of the visual space. This enabled us to fully control the placement of physical occluders for the purposes of the experiment. While this is naturally counterintuitive in a study on physical/virtual occlusion, we do not believe this affects the validity of our results in any way-the efficacy of the techniques themselves are independent of the source of occlusion.  Immovable occluders: Again drawing on our observations from the formative evaluation, we decided not to allow occluders to be moved to avoid having users spend the first portion of each trial moving items to one side of the visual space. While this is clearly an artificial constraint imposed for mostly technical reasons, we can defend this by the fact that in many cases, it is either not practical to move objects away to clear space for interaction (such as for heavy books, large stacks of paper, keyboard or monitors), or the physical items are intimately tied to the task the user is performing (citing research papers, reading manuals, writing notes, etc).

Experiment 1: Unguided Visual Search

Our objective with this study was to derive the properties of our occlusion management techniques for unguided visual search. In perceptual studies, unguided visual search is defined as an active scan of a visual environment for a particular target whose location is not previously known [START_REF] Treisman | Search, similarity, and integration of features between and within dimensions[END_REF]. The goal was to study technique performance under different space and object conditions. In particular, we opted not to compare techniques to a baseline with no occlusion management because our pilot testing made it obvious that the comparison was in favor of all of the new techniques.

Apparatus

We conducted the experiment on an 1.2m×0.9m (approximately 81 inch) DI [START_REF]Multitouch Technologies[END_REF] multitouch tabletop display equipped with with two DLP projectors, each with 1280×800 resolution (for a total of 1600×1280). The projectors were powered by a computer running Microsoft Windows 7.

Participants

We recruited 12 paid volunteers (8 males, 4 females) for the experiment. Ages ranged from 21 to 29 (average 25.3, median 23) years, and all participants had normal or corrected-to-normal vision with no color deficiency (self-reported).

Task

We designed our experiment as a basic instance of unguided visual search [START_REF] Treisman | Search, similarity, and integration of features between and within dimensions[END_REF], where the participants were asked to find a known target object in an unstructured visual space. The visual space consisted of both virtual and physical objects:  Virtual objects: These objects are graphical elements drawn on the display, and include the target as well as a set of distracting objects that have a similar visual appearance as the target. More specifically, all virtual objects were 3×3 rectangular grids of white cells, with one cell colored red. For the target, the colored cell was always the center one, whereas objects with other positions of the colored cell were distractors (Figure 3 gives an overview). The rationale for this design was that targets should not be preattentively distinguishable from distractors.  Physical objects: These represent physical occluders (such as books, stacks of paper, or coffee mugs) placed on the tabletop surface, thereby potentially hiding virtual objects on the display. To allow us to fully control the number and placement of occluders, these were actually not physical in our experiment; instead, they were represented by gray rectangles (300×300 pixels in size) placed in a layer above the virtual objects. Tapping on an occluder's rectangle temporarily lifted the object to make occluded content visible; tapping again on the screen would return that occluder to its original position. Only one occluder could be lifted at a time. We enforced a 1-second delay between lifts to model real occluders.

The space was configured so that all virtual objects were randomly placed behind a physical occluder, and thus initially occluded. Furthermore, all objects were placed so that they did not overlap (except between virtual objects and occluders) and were within reach of a participant without having to move; however, some techniques like MOVE could potentially cause an object to be moved out of reach or to partially overlap another object. Because of the high number of virtual objects, we could not rely on chance to make some physical occluders not occlude any object, so we controlled this by enforcing one occluder to be a dummy occluder, i.e., with no virtual object underneath. This gave some benefit to GLOW by cutting down search space.

Experimental Conditions

We included three factors in our study: Technique, Object Size, and Object Number.  Technique: We included all of the occlusion management techniques above as a factor T: GLOW, ICON, PILE, MMAP, MOVE, and REPL.  Object Size: Because identification-supporting techniques often rely on miniature versions of virtual objects, we included Object Size S as a factor in the experiment with two levels: large and small. Our pilot testing helped us set values to these levels: small objects were 42×42 mm (60×60 pixels) and fully recognizable at normal magnification, and large objects were 56×56 mm (80×80 pixels) or about a quarter of physical occluders (210×210 mm or 300×300 pixels). In particular, the small size was selected so that the miniature versions of targets would not be trivially identifiable using the ICON, MMAP, and PILE identification techniques.  Object Number: Techniques with high visual clutter and space consumption are presumably sensitive to the total number of virtual objects in a visual space. To test this hypothesis, we included an Object Number factor N with two levels: few and many. Again, pilot testing helped us find values for these: 10 objects vs. 20.

Experimental Design

We used a full factorial within-participants design with the following factors:

Procedure

Participants received training with each technique before each block until they indicated that they were ready to proceed. Trials were interleaved with an intermission screen during which participants could rest, also ensuring that their hands were in a neutral position prior to each trial. When starting a trial (and the timer), the screen changed to show the visual space with physical and virtual objects. Participants were instructed to complete the task as fast as possible. The trial ended (stopping the timer) when the participant found and tapped the correct target (or its copy in the REPL technique). Tapping on the wrong virtual target made it flash red to indicate the error.

After finishing each technique block, participants were given a structured interview where they were asked about that technique. A full experimental session, including training and post-block structured interview, lasted approximately 60 minutes.

Hypotheses

H1

Access-supporting techniques (MOVE, REPL) will yield faster performance than identification-supporting techniques (ICON, MMAP, PILE).

H2

Identification-supporting techniques (ICON, MMAP, PILE) will yield faster visual search performance than awareness-supporting ones (GLOW).

Results

For each trial, we measured the completion time, the number of occluder lifts, and the number of taps on objects. For lifts and taps, we found no significant differences between techniques, and so we disregard these measures for the rest of this analysis. Figure 4(a) shows the completion times for each technique (three standard deviation outliers removed per participant and condition). The distribution of completion times was not normal, so we analyzed its logarithm using a repeated-measures analysis of variance (RM-ANOVA, normality and homogeneity of variances assumptions checked with Shapiro-Wilks and Bartlett's tests, respectively, and both valid after log-transformation)-see a summary of completion time effects in Table 1.

We used Tukey's HSD test to analyze pairwise differences for techniques on completion time-significant results (p < .05) are summarized in Figure 5 (left). In particular, MOVE performed significantly faster than any other technique (p < .05), followed by REPL and GLOW, and finally MMAP, ICON, and PILE as the slowest.

Factors

Discussion

Our results show that for unguided visual search, MOVE and REPL perform significantly better than ICON, PILE, and MMAP. While we have only tested a sample of the occlusion management design space, we think that this means that access-supporting techniques (MOVE, REPL) perform better than identificationsupporting techniques (ICON, PILE, MMAP) for unguided visual search. This confirms H1, and it is clearly due to the fact that MOVE and REPL make all targets visible and selectable without requiring any occluders to be lifted. Also, the drawback of these techniques-displacing objects from their original positions-had no impact on the nature of the task. Identification-supporting techniques, on the other hand, generally show a smaller version of the targets, making recognition more difficult.

For H2, we were surprised to find that GLOW performs significantly better than ICON, PILE, and MMAP, thus rejecting the hypothesis. This may partially be due to the reason given above: recognizing the target is harder for these techniques. With GLOW, participants immediately started lifting the occluders to find the target object, whereas for ICON, PILE, and MMAP, they would essentially have to perform two visual search tasks: first for miniature versions on the whole space, and then again under the occluder they lifted. This was also supported by feedback from interviews.

Experiment 2: Guided Visual Search

Beyond the pure unguided visual search in the first experiment, we wanted also to study the impact of occlusion management for guided visual search [START_REF] Treisman | Search, similarity, and integration of features between and within dimensions[END_REF] where the spatial location of objects is important. We thus designed Experiment 2 as a game of Concentration with face-up photographs. Beyond task, we used the same apparatus and procedure as in Experiment 1. Below we discuss differences between the studies.

Participants

We recruited 12 paid volunteers (10 males, 2 females) for the experiment. Ages ranged from 22 to 28 (average 24.3, median 23) years, and all participants had normal or corrected-to-normal vision with no color deficiency (self-reported).

Task

Guided visual search tasks require that the participants have some a priori knowledge of target location. We achieved this using a revisitation task consisting of two phases: I. Learning: Users were shown a 5×5 grid of photographs (each 100×100 mm, or 150×150 pixels, in size and visible at all times). A randomly selected photograph would be highlighted. By tapping and holding the highlighted photograph for a minimum dwell time (1.5 seconds), the highlight would move on to a new photograph. This was repeated 5 times. We also showed a red path connecting all of the photographs to visit to further aid participants in learning the locations. II. Recall: After having visited (and presumably memorized) the location of 5 photographs, the user was asked to revisit the photographs (still face-up and visible) in the recall phase. During this time, a set of physical occluders (again simulated using gray rectangles) was added to the display in random locations, thus obscuring part of the grid. As before, occluders could be lifted, one at a time, by tapping. We enforced the photograph sequence from the learning phase, so participants could only proceed to the next photograph in the sequence by selecting the correct photograph (i.e. no out-of-order selections were possible). Figure 6 shows a typical scenario during Phase I (learning). We timed participants in Phase II, but there was no time limit on Phase I. The sequence of photographs was shown on the right side of the screen with the next photograph to visit highlighted, and out-of-order selections were not possible. We did this to eliminate errors in the experiment, allowing us only to analyze completion time.

Finally, photographs for each trial were selected from the same random category of the CalTech-101 image dataset [START_REF] Fei-Fei | Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories[END_REF]; this ensured that all images had the similar motif. We manually eliminated images that were almost identical, however.

Experimental Conditions

We included two factors: Technique T (same as Experiment 1) and Degree of Occlusion O. The degree of occlusion was simply the number of physical occluders in Phase II (recall).We used the same size occluders as before (210×210 mm or 300×300 pixels) and included two levels: low (1 occluder) and high (2).

Experimental Design

We used a full factorial within-participants design with the following factors:

12 participants × 6 Technique T (see above) × 2 Degrees of Occlusion O (Low, High) × 4 repetitions (training excluded) 576 total trials (48 per participant) As before, trials were organized in blocks for each technique, and block order was counterbalanced using a Latin square (O randomized). The experimental platform collected completion time as well as the number of taps and lifts per trial.

Hypothesis

H3

Identification-supporting techniques (ICON, MMAP, PILE) and awarenesssupporting techniques (GLOW) will yield faster guided visual search performance than access-supporting techniques (MOVE, REPL).

Results

Figure 4(b) shows the completion times for each technique. We again observed that completion time measurements did not obey a normal distribution, so we analyzed its logarithm using an analysis of variance (RM-ANOVA, normality and homogeneity of variances assumptions checked as above and valid after log-transformation) to find significant effects of the factors on completion time-see Table 2 for results.

To compare techniques directly, we performed a Tukey's HSD posthoc test. Results of this analysis can be found in Figure 5 (right). In particular, all other techniques were significantly (p < .05) faster than REPL and MOVE, and REPL was in turn significantly (p < .05) faster than MOVE (almost a reversal from Experiment 1).

Discussion

The results from Experiment 2 confirm hypothesis H3-techniques with less impact on the spatial position of targets performed better than access-supporting techniques that drastically affect the spatial arrangement on the screen. This is not a surprising result given that guided visual search relies on a priori knowledge of target locations.

Our results also show that REPL performed significantly faster than MOVE, indicating that the design of access-supporting techniques is an important factor to consider. In this case, the fact that REPL maintains the relative positions of objects in the locality of occluded space is probably the reason for this difference in performance. In other words, both MOVE and REPL transform the absolute positions of objects, but REPL at least maintains relative positions.

Implications for Design

Based on our findings from both of the experiments, there is no one technique that performs optimally for both guided and unguided visual search. There is clearly a tradeoff between a technique's impact on virtual objects on the display, and its capability to mitigate occlusion due to physical objects. In such circumstances, a balance must be struck between these two factors. The GLOW technique performs only second to MOVE in Experiment 1, and is among the fastest techniques in Experiment 2. It is also relatively lightweight to implement and does not significantly alter the interaction in existing applications. For these reasons, we recommend the use of GLOW as a starting point for managing physical/virtual occlusion on tabletops.

Having said that, there is nothing that prevents us from combining techniques to achieve better performance. For example, the minimap (MMAP) technique is a fairly nonintrusive addition to any application, and may actually serve additional purposes for overview+detail in maps, visualizations, and graphical editors. It is also true that these techniques represent only a sample of the occlusion management design space. Although we based our designs on a systematic exploration of this space, it is possible that other designs exist that would perform better. This is a topic for future research.

Furthermore, our experiments tested only low-level visual search, but general tabletop applications consist of many other types of tasks at different abstraction levels, as well as potential targets of many different shapes and sizes. However, we argue that visual search is a central activity in interactive computing, so our results should generalize to many real-world tabletop applications. Our results for relatively small objects should also generalize to components of larger objects. Still, it would be interesting to study occlusion management in longitudinal and more realistic settings.

Detecting 3D Occlusion

This work does not consider the fact that there is more to physical objects than their 2D footprint on the surface of the tabletop display, and that physical objects also extend along the vertical axis. This means that objects may be hidden from the user's viewpoint by physical objects even if the display area they inhabit is not actually covered-in other words, the occlusion problem between physical and virtual objects on tabletop displays is 3D and not 2D. Provided that we had full knowledge of the visible and hidden areas of the display from the user's viewpoint, we could adapt our techniques to also work in this setting. Our work is a first step towards fully occlusionaware tabletop interfaces, but more research is needed to reach this ultimate goal. Fig. 7. 3D occlusion detection process using an infrared camera mounted on the user's head.

We have experimented further towards reaching this goal by mounting an infrared webcam on a headset so that the camera sees what the user sees (similar to Vogel [START_REF] Vogel | Hand occlusion with tablet-sized direct pen input[END_REF]). With a DI tabletop, the surface of the table will glow with infrared light-except in places where the surface is occluded from the user's point-of-view (Figure 7). This allows us to separate the visible area of the tabletop as a 2D shape. By transforming the 2D shape of visible surface to the coordinate space of the table, we can derive occlusion information that can be used as input for any of the techniques proposed here.

Conclusion and Future Work

We have presented a novel approach to manage occlusion between physical items resting on tabletop displays and virtual objects projected on the display. Our primary objective is not to find an optimal occlusion management technique, but rather to characterize the performance of different techniques under different spatial characteristics and tasks. Results from two user studies on guided and unguided visual search, respectively, clearly show that the different design alternatives have different strengths and weaknesses, and one outcome from our work is perhaps that the more lightweight approaches are more promising for the general case.

In the future we plan on continuing to study occlusion management for tabletop displays. Much work remains to be done for detecting physical/virtual occlusion in 3D. We also envision techniques that distort the visual space to aid visual search.

Fig. 3 .

 3 Fig. 3. Virtual objects in Experiment 1. The object on the left is a target, others are distractors.

Fig. 4 .

 4 Fig. 4. Completion times for occlusion management techniques for both experiments.

Fig. 5 .

 5 Fig. 5. Significant time differences (p < .05) for techniques in Experiment 1 (left) and 2 (right).

Fig. 6 .

 6 Fig. 6. Typical scenario for Phase I in Experiment 2.

  Trials were organized in blocks for each technique. Block order was balanced using a Latin square across participants to counteract learning effects; other factors were randomized within blocks. The experiment platform collected completion time.

		12 participants
	×	6	Techniques T (see above)
	×	2	Object Sizes S (Small, Large)
	×	2	Object Number N (Few, Many)
	×	10 repetitions (training excluded)
		2880 total trials (240 per participant)

Table 1 .

 1 Significant effects of factors on time (Experiment 1, RM-ANOVA).

		df, den	F	Factors	df, den	F
	Technique (T)	5,55 **16.53	Technique (T)	5,55 **23.29
	Object Size (S)	1,11 **23.61	Occl. degree (O)	1,11	0.025
	Object Num (N)	1,11 **60.14	T * O	5,55	2.12
	T * S	5,55	*3.05
	T * N	5,55	**5.05
	S * N	1,11 **17.87
	T * S * N	5,55	0.05

Table 2 .

 2 Significant effects of factors on time (Experiment 2, RM-ANOVA).

	Significance results:
	*	= p  .05
	** = p  .0001

Acknowledgements

This material was partially supported by the U.S. Department of Homeland Security's VACCINE Center under award no. 2009-ST-061-CI0001.


Paolo Cremonesi
email: cremones@elet.polimi.it

Franca Garzotto
email: garzotto@elet.polimi.it

Sara Negro
email: negro@elet.polimi.it

Alessandro Vittorio Papadopoulos
email: papadopoulos@elet.polimi.it

Roberto Turrin
email: roberto.turrin@moviri.com

Looking for "Good" Recommendations: A Comparative Evaluation of Recommender Systems

Keywords: Recommender systems, quality metrics, user study

A number of researches in the Recommender Systems (RSs) domain suggest that the recommendations that are "best" according to objective metrics are sometimes not the ones that are most satisfactory or useful to the users. The paper investigates the quality of RSs from a user-centric perspective. We discuss an empirical study that involved 210 users and considered seven RSs on the same dataset that use different baseline and state-of-the-art recommendation algorithms. We measured the user"s perceived quality of each of them, focusing on accuracy and novelty of recommended items, and on overall users" satisfaction. We ranked the considered recommenders with respect to these attributes, and compared these results against measures of statistical quality of the considered algorithms as they have been assessed by past studies in the field using information retrieval and machine learning algorithms.

Introduction

Recommender Systems (RSs) play an increasingly important role in online applications characterized by a very large amount of data -e.g., multimedia catalogs of music, products, news, images, or movies. Their goal is to filter information and to recommend to users only the items that are likely of interest to them.

Traditionally, the quality of a RS is defined in terms of objective statistical metrics, e.g., error metrics and accuracy metrics, which do not involve users and are evaluated algorithmically, using well-known techniques developed in the fields of information retrieval and machine learning (e.g., hold-out or k-fold cross-validation).

More recently, RS research is exploring user-centric directions for measuring and improving the subjective quality of RSs. A number of researchers highlight the need of a shift of perspective, suggesting that the recommendations that are "best" according to objective metrics are sometimes not the ones that are most satisfactory or (+)Moviri srl, R&D Via Schiaffino, 11 -20158 Milano (Italy) roberto.turrin@moviri.com useful to the users [START_REF] Mcnee | Being accurate is not enough: how accuracy metrics have hurt recommender systems[END_REF]. Some works [START_REF] Mcnee | Being accurate is not enough: how accuracy metrics have hurt recommender systems[END_REF][START_REF] Pu | Trust building with explanation interfaces[END_REF] pinpoint that the quality of the User eXperience (UX) with a RS as determined by its pragmatic factors (e.g., usability) or hedonic characteristics (e.g., aesthetics and "fun") are as important, or even more important than algorithmically assessed quality to determine the user"s attitudes towards a RS, and are more influential on users" decisions to use a system and to "purchase" recommended results.

User-centric approaches to RS quality evaluation have recently received some interest in the research and industry arena of RS and HCI communities. Still, empirical research in this area is currently in its early stage and a limited amount of user-based studies exist. Empirical research in this domain is rather costly, difficult in design and implementation, partially because of the intrinsic complexity induced by the high number of variables to be controlled, the computational sophistication of RSs, and the difficulty of involving need large datasets and a wide number of users.

The paper provides a contribution to this field discussing an empirical study that involved 210 users and considered 7 recommender systems, which use the same dataset and user interface, but implement 7 different baseline and state-of-the-art recommender algorithms. We measured the user's perceived quality of each RS, focusing on three attributes -perceived accuracy, novelty, and global satisfaction. We prioritize the considered recommenders with respect to these attributes and compare our results against the objective statistical quality of the considered algorithms as it has been assessed by past studies in the field, based on accuracy metrics. We discovered some interesting mismatches that suggest that objective metrics are not always good predictors of the perceived quality of RSs.

Background and Related Work

Recommender Systems (RSs) are generally classified into two families, characterized by different types of recommender algorithms [START_REF] Adomavicius | Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions[END_REF]: content-based filtering (CBF) and collaborative filtering (CF).

In CBF algorithms, items are described by means of a set of explicit features. For instance, a movie can be characterized by genre, director, and list of actors. Such RSs tend to recommend items with the same characteristics as the movies a user "liked" in the past, thus they typically propose a limited variety of unexpected recommendations [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF] [START_REF] Weng | Improving recommendation novelty based on topic taxonomy[END_REF].

On the other hand, CF algorithms are based on collective preferences of the crowd: they recommend what similar customers bought or liked. Collaborative RSs are the most used, mainly because their implementation and integration in existing domains is relatively easy and their quality, in terms of objective metrics, is generally higher than CBF algorithms. However, some criticism is addressed also to CF recommenders, pinpointing that they are biased toward popularity, constraining the degree of diversity consumers would ever prefer [START_REF] Fleder | Blockbuster culture's next rise or fall: The impact of recommender systems on sales diversity[END_REF].

Two families of objective metrics are typically adopted to automatically evaluate RSs: error metrics and accuracy metrics [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF]. Error metrics, such as RMSE (Root Mean Square Error), measure the capability of the system to accurately estimate the ratings real users would give to item. Accuracy metrics, such as precision and recall, measure the effectiveness of the "top-N recommendation task" [START_REF] Deshpande | Item-based top-N recommendation algorithms[END_REF], i.e., the capability of a RS to accurately select a small set of items that the user will surely appreciate.

Both error and accuracy metrics can be automatically evaluated by means of wellknown techniques developed in the field of machine learning, such as hold-out and leave-one-out (e.g., [START_REF] Deshpande | Item-based top-N recommendation algorithms[END_REF] and [START_REF] Takács | Scalable collaborative filtering approaches for large recommender systems[END_REF]). However, such standard metrics address a single property of RS"s quality, relevance, while neglecting other issues that can be perceived as important by users but are more complex and articulated to operationalize.

As an alternative or complementary approach, a number of studies investigate a user-centric approach to RS evaluation, carrying on user-based empirical assessment or proposing conceptual frameworks for perceived quality.

Celma and Herrera [START_REF] Celma | A new approach to evaluating novel recommendations[END_REF] report an experiment exploring the users" perceived quality of novel recommendations provided by a CF and a CBF algorithm in the music recommendation context. Shearer [START_REF] Shearer | User response to two algorithms as a test of collaborative filtering[END_REF] describes an experiment with 29 subjects on a movie RS to determine whether recommendations based on CF are perceived as superior to recommendations based on user population averages. The recommender systems suggested movies that subjects later viewed. Participants placed slightly more confidence in the CF recommendations with respect to the recommendations based on the population averages, but the perceived quality of the two algorithms was almost the same.

Ziegler et al. in [START_REF] Ziegler | Improving recommendation lists through topic diversification[END_REF] and Zhang in [START_REF] Zhang | Novelty and redundancy detection in adaptive filtering[END_REF] propose diversity as a quality attribute: recommender algorithms should seek to provide optimal coverage of the entire range of user"s interests. This work is an example of combined use of automatic and usercentric quality assessment techniques.

Pu and Chen [START_REF] Pu | A User-Centric Evaluation Framework of Recommender Systems[END_REF] develop a framework called ResQue, which defines a wide set of user-centric quality metrics to evaluate the perceived qualities of RSs and to predict users" behavioural intentions as a result of these qualities. The framework provides 13 quality attributes and 60 questions that can be put to users for measuring them. Quality constructs are organized in four main classes: 1) "perceived system qualities", which refer to the functional and informational aspects of RRs (recommended items, interaction, and interface); 2) "beliefs" (user"s perception on ease of use, usefulness, and control on interaction); 3) "attitudes" (the user"s overall feeling towards a recommender, e.g., global user satisfaction, confidence and trust); 4) "behavioral intentions" (the degree at which a RS is able to influence users" decisions to implement the suggestions by the system). The framework represents an important contribution to understand the crucial factors that influence the user adoption of RSs, and provides a useful conceptual tool to guide the design and execution of usercentric evaluation studies of RSs. Several user-centric evaluations are reported in literature employing ResQue attributes [START_REF] Chen | A cross-cultural user evaluation of product recommender interfaces[END_REF][START_REF] Hu | Acceptance issues of personality-based recommender systems[END_REF][START_REF] Jones | User Technology Adoption Issues in Recommender Systems[END_REF][START_REF] Pu | Trust building with explanation interfaces[END_REF][START_REF] Pu | Evaluating product search and recommender systems for e-commerce environments[END_REF][START_REF] Pu | Critiquing recommenders for public taste products[END_REF]. They focus on different RSs (employing different user interfaces [START_REF] Pu | Trust building with explanation interfaces[END_REF] or implementations, or datasets in different domains [START_REF] Pu | Evaluating product search and recommender systems for e-commerce environments[END_REF][START_REF] Pu | Critiquing recommenders for public taste products[END_REF] (e.g., music [START_REF] Hu | Acceptance issues of personality-based recommender systems[END_REF] or film [START_REF] Jones | User Technology Adoption Issues in Recommender Systems[END_REF] or investigate the different perceptions of quality in culturally heterogeneous user groups [START_REF] Chen | A cross-cultural user evaluation of product recommender interfaces[END_REF], thus obtaining a variety of not comparable results.

As discussed in the next section, ResQue has been partially adopted also in our work. Still, our research differs from previous works in that it is more focused -it involves seven RSs which differ in terms of algorithms only -and also compares the (+)Moviri srl, R&D Via Schiaffino, 11 -20158 Milano (Italy) roberto.turrin@moviri.com results of perceived quality evaluation with objective quality measures of the considered algorithms.

Empirical study of RS perceived quality

The general goal of the study was to compare measures of user's perceived quality against measures of objective statistical quality of RSs in order to provide some empirical evidence about the degree at which they are aligned, and to validate, or to confute, the hypothesis, underlying most existing studies, that objective statistical quality is a good predictor for user"s perceived quality. The study was designed as a between subjects controlled experiment, in which we measured perceived quality, decomposed into a number of measurable attributes (dependent variables) in seven different experimental conditions, each one using a system that support the same user interface, employ the same dataset in the movie domain, but implements a different recommender algorithm (independent variable).

Perceived Quality attributes

To better scoping our research, we focused our attention on three user-centric quality metrics:

Perceived accuracy (also called Relevance) -how much the recommendation matches the users" interests, preferences and tastes;

Noveltythe extent to which users receive "new" recommended items; Overall users' satisfaction -the global users" feeling of the experience with the RS.

Considering the classification of the ResQue model [START_REF] Pu | A User-Centric Evaluation Framework of Recommender Systems[END_REF], the third metric belongs to the category "Attitudes", while the first two attributes fall in the category "Perceived System Qualities", and, in particular, the subcategory "Quality of recommended items".

Our notion of perceived accuracy is meant in the same way as in the ResQue model. Still, we operationalize their measure is a slightly different way w.r.t. ResQue, as discuss in the following section.

Our concept of novelty can be regarded as a sub-dimension of ResQue novelty, which encompasses not only the idea of "new" but also of "interesting" and "surprising", the latter being referred to as "serendipity" in Herlock [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF]. In addition, we distinguish between two "levels" of novelty, called respectively "First Order Novelty (FON)" and "Second Order Novelty (SON)". FON is a weaker for of novelty: it considers a movie to be novel for a user only if he/she has never watched it (without discriminating whether he/she has any knowledge about it). SON is more stringent concept and subsumes FON: a recommended movie is considered novel if the user has no idea of it. SON is a more conservative way to measure novelty, and, as we will see in the next sections, leads to lower values than FON. Anyway, it is interesting to compute the novelty in both ways and to compare the obtained results.

Algorithms

Our study considered several state-of-the-art recommender algorithms: (i) one nonpersonalized algorithm used as baseline, referred to as TopPop, (ii) five collaborative algorithms -CorNgbr, NNCosNgbr, AsySVD, and two versions of PureSVD -and (iii) a content-based one -LSA. In the following we provide a short description of each algorithm. Further details can be found in [START_REF] Cremonesi | Performance of recommender algorithms on top-N recommendation tasks[END_REF] and in the papers quoted therein.

Non-personalized algorithm

TopPop (Top Popular) implements a simple, non-personalized estimation rule, which recommends the most popular items to any user, regardless his or her ratings. Such algorithm serves as baseline for the more advanced personalized algorithms.

Collaborative algorithms

There are two major approaches to collaborative filtering: (i) the neighborhood approach and (ii) the latent factor approach.

Neighborhood models

Neighborhood models represent the most common approach. Rating prediction is based on the similarity relationships among either users or items, in terms of collected ratings. Item-based similarity is usually preferred to user-based similarity for its better performance in terms of RMSE and its higher scalability [START_REF] Sarwar | Item-based collaborative filtering recommendation algorithms[END_REF]. Prior to computing similarities, it is advised to remove a set of biases in the collected ratings, such as: (i) user effects, which represent the tendency of some users to rate higher than others, and (ii) item effects, which represent the tendency of some items to be rated higher than others. Typically, only the most similar items -referred to as neighbors -are taken into consideration. In our experiments, the neighborhood size has been set to 200.

CorNgbr (Correlation Neighborhood) is a classical technique that computes itemitem similarity by means of the Pearson linear correlation coefficient [START_REF] Koren | Factorization meets the neighborhood: a multifaceted collaborative filtering model[END_REF].

Similarly, NNCosNgbr (Non-normalized Cosine Neighborhood) computes itemitem similarity by means of the cosine coefficient. Unlike Pearson correlation -which is computed only on ratings shared by common rater -the cosine coefficient is computed over all ratings, taking missing values as zeroes. In addition, while CorNgbr averages the ratings received by similar items, NNCosNgbr simply sums up such ratings, higher ranking items with more similar neighbors [START_REF] Cremonesi | Performance of recommender algorithms on top-N recommendation tasks[END_REF].

Latent factor models

Latent factor models -also informally known as SVD models after the related Singular Value Decomposition (SVD) -represent users and items as vectors in a common low-dimensional "latent factor" space. In such a space, users and items are directly comparable and the rating of a user u on an item can be estimated as the proximity (e.g., inner-product) between the related latent factor vectors. This family (+)Moviri srl, R&D Via Schiaffino, 11 -20158 Milano (Italy) roberto.turrin@moviri.com of algorithms has been leading the Netflix contest thanks to its performance in terms on RMSE.

AsySVD (Asymmetric SVD) is a powerful matrix factorization model that reported an RMSE of 0.9000 in the Netflix context. Differently from other latent factor models, AsySVD represents users as a combination of item features. Thus, AsySVD is able to immediately compute recommendations for users not yet parameterized and to adjust recommendations as fast as the user being recommended enters new ratings, providing an immediate feedback to his or her activity [START_REF] Koren | Factorization meets the neighborhood: a multifaceted collaborative filtering model[END_REF].

PureSVD is a latent factor algorithm recently proposed [START_REF] Cremonesi | Performance of recommender algorithms on top-N recommendation tasks[END_REF], whose rating estimation rule is based on the conventional SVD. In order to use conventional SVD -which is not defined for matrices with missing values -unknown ratings have been treated as zeros. We have tested PureSVD with two different sizes of latent factors: 50 and 300. In fact, the larger the number of latent factors the more the algorithm is able to detect the uniqueness in users" taste. The smaller the number of latent factor the more the algorithm tends to recommend the most popular items.

Content-based algorithms

Content-based algorithms recommend items whose content is similar to the content of items the user has positively rated in the past. For instance, in the domain of movies, such content can be the movie title, the playing actors, the director, the genre, and the summary. While the basic approach to content-based recommendations is based on the analysis of term-by-item occurrences, and neglecting the semantic structure of item content, more advanced techniques try to exploit such semantic features. In our experiments we have used LSA (Latent Semantic Analysis), a wellknown method in the field of information retrieval for automatic indexing and searching of documents. The approach takes advantage of the implicit structure (i.e., latent semantic) in the association of terms with documents. Such semantic structure comes out by representing the term-by-item relationships in a low-dimensional "latent factor" space computed through SVD [START_REF] Husbands | On the use of the singular value decomposition for text retrieval[END_REF].

Instruments

Technological framework

To run our experiments, we used a web-based commercial recommender framework -called ContentWise (www.contentwise.tv -Figure 1). ContentWise supports users with a wide range of typical RS functionalities, such as browsing a catalog of products, retrieving the detailed description of each item, rating it, getting recommendations and rating their relevance. The modularization and customization features of the system allowed us to easily create different experimental conditions by implementing different algorithms while maintaining interface and dataset invariant. (+)Moviri srl, R&D Via Schiaffino, 11 -20158 Milano (Italy) roberto.turrin@moviri.com

Dataset

The dataset included 2137 movies and about 7.7 million ratings given by 49,969 users. The data consider a subset of the well-known large-scale movie dataset Netflix, published for the purpose of the famous contest organized by the homonymous movie rental American provider. In addition, for the purpose of our study, these contents were integrated with data and metadata (e.g., movie plot, images, actors, director and genre) collected online.

Data Collection Technique

As discussed more precisely in the following section, the chosen user-centric metrics were measured using a questionnaire that evaluators completed for each user during the experiment. It collects both users" demographic attributes and their opinions about perceived accuracy, novelty and overall satisfaction.

Participants

Data collection was carried on by a team of 14 master students (two per experimental condition) selected among the best ones of those attending two courses -HCI and iTV -at our School of Information Engineering. Students were motivated in performing the evaluation to the best of their capabilities, for a number of reasons. This work represented the second assignment proposed at our courses, and accounted for 50% of the final mark. Students were pre-screened as they had to pass brilliantly the first part of our exam in order to be eligible for performing this one. In addition, they freely selected this assignment from a set of others proposed by teachers.

Students were initially trained by us to perform the study, were given written instructions on the evaluation procedure, and were regularly supervised by a teaching assistant during their activities. After a pre-screening among school maters, friends and relatives, each pair of student evaluators recruited a group of thirty subjects for each algorithm, almost uniformly distributed w.r.t. to gender and age. Overall, the study involved 210 users aged between 20 and 50; 54% subjects were male and 46% female. None of them had been previously exposed to the system used in our study nor had technical knowledge about RSs.

Procedure

The evaluation took place in informal environments such as university (15%), interviewer"s place (32%), and interviewee"s place (31%). Each interview lasted from 15 to 35 minutes. The motivation for such a temporal variability is that in case of completely novel recommendations, users were invited to explore information related to unknown items (see below) in order to express more precise and conscious opinions on the quality of the RS used.

Each participant was initially asked to provide his/her personal information (age, gender, education, nationality, and number of movies watched per month). Afterward, (s)he was invited to browse the movie catalog using the ContentWise system (precustomized on a specific algorithm). The user was then asked to freely select five known (not necessarily watched) movies and rate his/her degree of appreciation or interest for them using a 1-5 point scale (1 = low interest for/appreciation of the movie; 5 = high). On the basis of these ratings, five recommendations were returned by the system (using the current algorithm). The user was finally invited to explore the results and reply to a set of questions related to the quality of the recommendations.

Novelty measures were collected as follows. For each recommended item we first asked the question "Have you ever watched this movie?" This answer (yes/no) was used to compute First Order Novelty (FON). FON for an item is 1 if the user has never watched the movie and 0 otherwise. If the user has never watched a recommended movie (FON=0), we proceeded with an in depth exploration to assess Second Order Novelty (SON). We asked the user if (s)he had ever heard about the movie, inviting him/her to explore the information related to the movie (director, cast, abstract, trailer,...) to refresh her memory. If a user answers "yes" to the above question (or if FON is 0), SON is set to 0, while it is set to 1 otherwise.

Perceived accuracy measures were collected as follows. For each recommended movie, if the user had already watched it, he/she was asked to rate how much he/she liked/disliked (on a 1-5 scale). Otherwise, if the user had already seen the trailer, he/she was invited to rate the degree of potential interest for the movie. If the user had never been exposed to the movie or its trailer, he/she was invited to look at the trailer and to explore additional information (e.g., director, the actors, and so forth) and then to give a rating of potential interest. For each user, each of the above attributes -FON, SON and perceived accuracy is calculated as the average on the respective values assigned to each recommended item.

Finally, the overall satisfaction was computed by asking each subject to provide a global judgment (in a 1-5 rating scale) about the list of recommended movies and was allowed to express a free comment.

Empirical Study Results

In this section we present the user-centric metrics of relevance and novelty computed on the basis of the questionnaire data.

Accuracy

Users" perception of the accuracy of the recommendations is measured by considering, for each user and each suggested movie, the user"s opinion on the movie expressed in a 1-5 scale. Figure 2 shows the box plot of the perceived relevance for each algorithm. Upper and lower ends of boxes represent 75 th and 25 th percentiles.

(+)Moviri srl, R&D Via Schiaffino, 11 -20158 Milano (Italy) roberto.turrin@moviri.com Whiskers extend to the most extreme data point which is no more than 1.5 times the interquartile range. Median is depicted with a solid line, mean with a dot. Outliers are represented with empty circles.

Novelty

A similar analysis was performed for perceived novelty. Novelty refers to the previous knowledge of the user about the suggested movies. Unlike relevance, novelty measures are based on two questions, respectively responded with either "yes" (novelty value = 1= totally novel recommendations) or "no" (novelty value = 0= no novel recommendations). Figure 3 shows the box plot of perceived first-order novelty (percentage of never-watched movies in the recommendation list). Similarly, Figure 3 shows the second-order novelty (percentage of never-heard-of movies in the recommendation list). By definition, first-order novelty (FON) is always greater than or equal to second-order novelty (SON). The two metrics provide quite similar results and are strongly correlated (the correlation factor is 0.8). If perceived relevance was on average satisfactory across all the algorithms, the same cannot be said for novelty. On average, no algorithm was able to suggest more than 40% of totally-unknown-to-the-user movies (SON). Moreover, TopPop and (+)Moviri srl, R&D Via Schiaffino, 11 -20158 Milano (Italy) roberto.turrin@moviri.com PureSVD50 were not able to suggest novel movies at all (with the exceptions of few outliers, SON is always 0%). Finally, Figure 5 shows the results for global user satisfaction. User satisfaction was measured according to a 1-5 points scale. Contrary to the relevance, the collected responses have a large variance and there seems to be no agreement in users" opinion, at least with AsySVD, CorNgbr, LSA and PureSVD300 (median and average equal or close to 3). In order to better compare the results, we first used 1-way ANOVA. The test suggests that, for each of the dependent variables, at least one of the algorithms differs significantly with respect to the others. We run multiple pair-wise comparison post-hoc tests using Tukey's method. All tests were run using a significance level α = 0.05. Although no algorithm is significantly better (or worse) than all the other in terms of any of the quality dimensions, we can at least identify a partial order, as outlined in Table 1. According to this ordering, TopPop is the maximal algorithm in term of relevance (i.e., the algorithm with the best perceived relevance), while NNCosNgbr, CorNgbr and LSA are the minimal algorithms (i.e., the algorithms with the worst perceived relevance).

We have performed the same comparison for first-order and second-order novelty. Being the two novelty metrics correlated, the comparisons define the same partial ordering. According to this ordering, AsySVD, CorNgbr and LSA are the algorithms with the best perceived novelty, while TopPop and PureSVD50 are the algorithms with the worst perceived novelty.

The last column of the table shows the partial ordering according to the global satisfaction; TopPop and PureSVD300 are the algorithms which mostly satisfied the users, while AsySVD, CorNgbr and NNCosNgbr are the algorithms which less satisfied the users.

Objective Evaluation of Quality

Objective Metrics and their Evaluation Method

As mentioned in section 2, RS performance is traditionally usually measured using objective metrics. In particular, there are methodologies based on accuracy metrics (e.g., precision, recall and fallout) and on error metrics (e.g., RMSE and MAE). Some of the algorithms tested in this study (TopPop, NNCosNgbr and PureSVD) cannot be evaluated with error metrics [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF]. Hence, we considered only accuracy metrics in our study. In particular, we focused our attention on recall r (the conditional probability of suggesting a movie given it is relevant for the user) and on fallout f (the conditional probability of suggesting a movie given it is irrelevant for the user).

A good algorithm should have high recall (i.e., it should be able to recommend items of interest to the user) and low fall-out (i.e., it should avoid to recommend items of no interest to the user).

A measure that combines recall and fall-out is the F-measure. F-measure is defined as the harmonic mean of precision and recall. Precision can be estimated from recall and fall-out by using the definition provided in [START_REF] V. Raghavan | A critical investigation of recall and precision as measures of retrieval system performance[END_REF].

The testing methodology adopted in this study is similar to the one described in [START_REF] Cremonesi | Performance of recommender algorithms on top-N recommendation tasks[END_REF]. The known ratings of the dataset are split into two subsets: training set M and test set T. The test set T contains only 5-stars ratings. Therefore we can reasonably state that T contains items relevant to the respective users. The detailed procedure used to create M and T from the Netflix dataset is similar to the one used for the Netflix prize, maintaining compatibility with results published in other research papers [START_REF] Bennett | The Netix Prize[END_REF][START_REF] Cremonesi | Performance of recommender algorithms on top-N recommendation tasks[END_REF].

In this work, the training set M is a subset of the original Netflix training set, while the test set T contains only part of the 5-stars ratings from the Netflix probe-set. The test set contains 69,039 5-star ratings.

In order to measure recall, we first trained the algorithm over the ratings in M. Then, for each item i rated 5-stars by a user u in T, we followed these steps:

(+)Moviri srl, R&D Via Schiaffino, 11 -20158 Milano (Italy) roberto.turrin@moviri.com 1. We randomly selected 1,000 additional items unrated by user u, assuming that the user u is not interested in most of them. 2. We predicted the ratings for the test item i and for the additional 1,000 items. 3. We formed a top-5 recommendation list by picking the 5 items with the largest predicted ratings. The overall recall r was computed as r = # times the element is in the list # elements in T

A similar approach was used to measure fall-out, with the only difference being in the composition of the test set T, that now contains only 1-stars ratings. The fall-out f is computed as

f =
# times the element is in the list # elements in T

Objective Metrics Evaluation Results

Table 2 presents the objective accuracy of the tested algorithm. Algorithms in the table are ordered in decreasing order of recall. Recall and F-measure suggest PureSVD as being the most accurate algorithm. Second in line are AsySVD, the two item-based neighborhood algorithms and the non-personalized TopPop algorithms, all of them with a similar recall. The content-based LSA algorithm has the worst accuracy both in terms of recall and F-measure. If we look at fallout, AsySVD and LSA obtain the best results, while NNCosNgbr and TopPop are the algorithms with the largest error rate. The analysis of the results presented in the previous sections suggests a number of interesting considerations: 1) simple, non-personalized algorithms are well perceived by the users; 2) the perceived novelty of content-based recommendations is equal or even better with respect to collaborative recommendations; 3) objective accuracy metrics (e.g., recall and fallout) are not a good approximation of user perceived quality.

Let"s start from the first point. According to Figure 2, no algorithm is significantly better (or worse) than all the others in terms of perceived relevance. However, the partial ordering among the algorithms (Table 1) highlights that TopPop is the algorithm with the best perceived relevance (this is unexpected) and with the worst novelty (as expected), thus its utility is limited because oftentimes the user has already watched the suggested items. Still, TopPop (together with PureSVD300) is at the top level in terms of global user satisfaction. In summary: simple nonpersonalized TopPop recommendations are better perceived by the users with respect to other more sophisticated and personalized recommender algorithms, although users are aware of the low utility of such recommendations. Global user satisfaction seems mainly driven by the perceived accuracy than by the novelty of the recommendations. This is a somehow surprising result, especially if we consider the large academic and industrial effort in the development of new and more sophisticated recommender algorithms.

As for novelty, Table 2 highlights that AsySVD, CorNgbr and LSA are the algorithms with the best perceived novelty, while TopPop and PureSVD50 are the algorithms with the worst perceived novelty. Thus, the perceived novelty of contentbased recommendations is equal or even better with respect to collaborative recommendations. This result is in contrast with most of the existing literature in RS, which considers content-based algorithms as not able to recommend novel items (see, e.g., [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF] and [START_REF] Weng | Improving recommendation novelty based on topic taxonomy[END_REF]). To try an interpretation of this result, we should consider that collaborative algorithms, by design, are biased toward popular "Blockbuster" items, thus reducing the chances of novel recommendations. Collaborative algorithms are trained (e.g., tuned) to achieve the best performance in terms of objective accuracy. Because objective accuracy is computed on already-rated items, collaborative algorithms cannot recommend items with limited historical data. This creates the richget-richer effect for popular items and the opposite effect for unpopular ones, which results in lower novelty. As a consequence, collaborative algorithms tend to reinforce the popularity of already popular items and to recommend mainly common movies, which are likely not to be novel.

Finally, the comparison between Tables 1 and2 shows the lack of correspondence between objective accuracy metrics (e.g., recall and fallout) and users' perceived quality. In other words, objective quality attributes are not good predictors of users" perceived quality of a recommender algorithm, at least in our case. To try an interpretation of this phenomenon, it is useful to consider that objective metrics compute accuracy of recommendations by (i) exploiting previously rated movies, i.e., user"s rankings of movies that they know about, and (ii) sampling all the ratings in the dataset -the majority of which concern few popular movies. Consequently, objective metrics focus their attentions on measuring the quality of an algorithm when (+)Moviri srl, R&D Via Schiaffino, 11 -20158 Milano (Italy) roberto.turrin@moviri.com recommending popular items and might not be particularly effective for measuring the quality of the same algorithm when recommending novel, unrated items.

Conclusions

In this work we have investigated under different perspectives the quality of 7 RSs that only differ in terms of recommender algorithms. We first measured quality from a user-centric perspective and then compared these results against measures of statistical quality, in terms of recall and fallout. The considered RSs include both state-of-the-art techniques and a trivial non-personalized recommender algorithm. There are three main interesting findings:

(i) the simple, non-personalized algorithm is well perceived in terms of overall user satisfaction, although users are aware of the low utility of such recommendations; (ii) the perceived novelty of content-based recommendations is equal or even better with respect to collaborative recommendations; (iii) statistical accuracy metrics (e.g., recall and fallout) are not necessarily a good approximation of the quality perceived by the users. Our research has its limitations. First, the sample size of participants used for each RS (30) is relatively small. Still, the fact that we replicated the study in seven experimental conditions using the same methodological framework, and involving overall 210 tested subjects, partially compensates for this drawback and strengthens the reliability of our results. Second, we focused our investigation of user perceived quality on a small set of attributes -perceived accuracy, novelty, and overall user satisfaction. Other approaches, e.g., the ResQue model, include many additional usercentric metrics, which we did not consider in our study. Our choice may be regarded as a weakness, but it was motivated by the need to keep data collection workload affordable. ResQue provides a 60 items questionnaire. Administrating so many questions could have been too demanding for respondents and too time-consuming for data collectors, considering our goal of collecting measures in 7 experimental conditions. In addition, we sought to focus on those user-centric attributes that are more related to standard objective quality metrics and thus are more comparable with them. Objective metrics are related to the quality of recommend items, thus we gave higher priority to measuring ResQue attributes related to these aspects. Certainly, other measures of user perceived quality are worth being investigated in relationship to objective quality, and we are planning to replicate our study in order to include them.

In spite of the above limitations, our work provides contributions both from a research and practical perspective. To our knowledge, this is the first work that systematically compares perceived quality in a significant number of different RSs isolating a precise factor -the underlying recommender algorithm -and analyzing the results against statistical, objective measures of quality. For the practice of RS design and evaluation, our results may promote further approaches that move beyond the attention to conventional accuracy metrics and shift the emphasis to more user-centric factors.

Fig. 1 .

 1 Fig. 1. ContentWise interface: a) initial exploring and rating of movies (up); b) results of recommendations; c) movie details.

Fig. 2 .

 2 Fig. 2. Perceived relevance for each algorithm. Relevance ranges from 5 (most relevant) to 1 (not relevant).

Fig. 3 .

 3 Fig. 3. Perceived First-Order Novelty (never watched) for each algorithm.

Fig. 4 .

 4 Fig. 4. Perceived Second-Order novelty (never heard of) for each algorithm.

Fig. 5 .

 5 Fig. 5. Global Satisfaction for each algorithm. Satisfaction ranges from 5 (totally satisfied) down to 1 (no satisfied at all).

Table 1 . Partial Ordering of RSs w.r.t. the various quality attributes Accuracy Novelty Global satisfaction Maximal

 1

		TopPop	AsySVD LSA CorNgbr	PureSVD50 TopPop
	Intermediate	AsySvd PureSVD300 PureSVD50	NNCosNgbr PureSVD300	PureSVD300 LSA
	Minimal	NNCosNgbr LSA CorNgbr	PureSVD50 TopPop	AsySVD CorNgbr NNCosNgbr

Table 2 . Recall, fallout and F-measure computed for Top-5 recommendation lists Type Recall Fallout F-measure PureSVD50

 2

		Collaborative Latent factors	0.29	0.005	0.45
	PureSVD300	Collaborative Latent factors	0.25	0.005	0.40
	AsySVD	Collaborative Latent factors	0.13	0.001	0.23
	NNCosNgbr	Collaborative Item-based	0.12	0.010	0.21
	TopPop	Collaborative Non-personalized	0.11	0.025	0.20
	CorNgbr	Collaborative Item-based	0.08	0.010	0.15
	LSA	Content	0.01	0.002	0.02

We can see that all the algorithms have an average relevance between 3 and 4. This result shows that, on average, users are satisfied by the quality of the recommendations (the median for all the algorithms is greater than 3). Moreover, 75% of the users have received relevant recommendations from five of the considered algorithms (AsySVD, LSA, PureSVD50 PureSVD300 and TopPop). Only NNCosNgbr produces a relatively large number of bad recommendations (25% of the recommendations are rated 2 or less).

The most surprising result is the TopPop algorithm, having the largest perceived accuracy. This result is surprising because the TopPop algorithm suggests to all users the same list of 5 movies, without taking into consideration the user profile. These movies are: "Pirates of the Caribbean: The Curse of the Black Pearl"; "Forrest Gump"; "The Lord of the Rings: The Two Towers"; "The Lord of the Rings: The Fellowship of the Ring"; "The Sixth Sense".

According to our study, any user found in this list an average of four interesting movies (more than 80% of the users rated TopPop recommendations with 3 or more stars). This result may provide evidence against the real usefulness of sophisticated recommender algorithms, a hypothesis that will be further analyzed in the following paragraphs and in the discussion section.