Eric Nichols
email: eric.nichols@inria.fr

Kevin Green

Axel Hutt

Lennaert Van Veen

published or not. The documents may come

P O S T E R P R E S E N T A T I O N Open Access

Two-dimensional patterns in neural fields subject to finite transmission speed Eric Nichols 1* , Kevin Green 1,2 , Axel Hutt 1 , Lennaert van Veen 2

From The Twenty Third Annual Computational Neuroscience Meeting: CNS*2014 Québec City, Canada. 26-31 July 2014 This work analyzes and implements finite axonal transmission speeds in two-dimensional neural populations. The biological significance of this is found in the rate of spatiotemporal change in voltage across neuronal tissue, which can be attributed to phenomena such as delays in spike propagation within axons, neurotransmitter activation and the time courses of neuron polarization and refraction. The authors build upon the finite transmission speed work in [1].

Linear analysis about a spatially homogeneous resting state of the neural population dynamics is performed. The analyses of the resulting analytical expressions guide the parameter selection for simulations. For simulation, computation of the transmission-delayed convolution between the kernel and firing rates is performed with a fast Fourier transform as in [1].

The Neural Field Simulator [2] is used to simulate the activity of the field. We extended the simulator by the implementation of a large class of kernels reflecting global excitation, global inhibition, local excitation-lateral inhibition and local inhibition-lateral excitation. Moreover, we extended the tools by an automatic root finder to compute stationary states and an automatic root finder of the characteristic equation of the linear dynamics. These latter features facilitate the user to perform the linear analysis. Further adjustments to the simulator include a provision to modify neural field variables online while simulations are ongoing and three-dimensional displays of disparate parts of the neural field, such as the external input, kernel and firing rate.

We find Turing patterns appear when starting the simulations with the derived conditions for stationary instability. This is shown in Figure 1(A,B,C). Simulations with travelling wave patterns are also performed using parameter sets for the non-stationary instabilities, and the effects of finite transmission speeds are analyzed and visualized. The software tool provides a large set of analysis and visualization tools, that promises to speed up the analysis of two-dimensional neural field dynamics and hence accelerates research on neural population dynamics.

Acknowledgements This work is funded by the European Research Council for support under the European Union's Seventh Framework Programme (FP7/2007-2013), ERC grant agreement No. 257253 (MATHANA project).

Authors' details 1 INRIA Nancy, Team NeuroSys, 615 rue du Jardin Botanique, 54600 Villers-lès-Nancy, France.


Dawei Feng
email: dawei.feng@lri.fr

Cécile Germain
email: cecile.germain@lri.fr

Julien Nauroy
email: julien.nauroy@lri.fr

Sequential fault monitoring

For large-scale distributed systems, the knowledge component at the core of the MAPE-K loop remains elusive. In the context of end-to-end probing, fault monitoring can be recasted as an inference problem in the space-time domain. We propose and evaluate Sequential Matrix Factorization (SMF), a fully spatio-temporal method that exploits both the recent advances in matrix factorization for the spatial information and a new heuristics based on historical information. Adaptivity operates at two levels: algorithmically, as the exploration/exploitation tradeoff is controlled by a self-calibrating parameter; and at the policy level, as active learning is required for the most challenging cases of a real-world dataset.

I. INTRODUCTION

We depend on computer systems that are not dependable: large scale distributed systems pervade real-world Information Technology infrastructures and usage; and, decades ago, Lamport characterized such systems as those where "the failure of a computer you didn't even know existed can render your own computer unusable".

Computer Science research has worked on large scale fault management since long, with two main directions: discovering faults, and coping with them. With the advent of truly massively distributed systems with complex structures, a key change now occurred: rich monitoring information becomes available. Complete knowledge, and the very concept, of the state of a distributed system remain unreachable for fundamental reasons [START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF]. But, with the availability of equally massive information, estimating elements of the system state becomes a realistic goal. Specifically, some fault management goals can be re-casted as fault inference problems. This work targets a specific aspect of fault monitoring, fault discovery. In the following, the inference approach to fault discovery will be called fault prediction, because it fits with the Collaborative Prediction [START_REF] Koren | Factorization meets the neighborhood: a multifaceted collaborative filtering model[END_REF] context, although fault estimation would more accurately describe the approach.

Predicting faults improves system availability and reliability by providing useful information for the next task of coping with them, as the systems are normally highly redundant and heavily supervised. Often, alternatives to the faulty services can be proposed [START_REF] Torres | A replicated information system to enable dynamic collaborations in the grid[END_REF], [START_REF] Venugopal | A taxonomy of data grids for distributed data sharing, management, and processing[END_REF]; in these cases, a well organized fault management system will conceal the hardware and software dysfunctions and will provide a transparent service that is a crucial ingredient of Quality of Experience. On the other hand, irrecuperable faults must be signaled as fast as possible to the human of automatic supervision. Overall, this amounts to re-evaluate the role of monitoring in fault management, and to consider fault prediction as an inference in the space-time domain.

Autonomous Computing (AC) provides a conceptual framework for designing fault management for these monitoringequipped systems. Its so-called MAPE-K loop is organized around a Knowledge component. To set up fault prediction as a realistic objective in an AC approach, the first question is which kind of knowledge is actually reachable. In a fault diagnosis approach, the knowledge component includes a detailed internal model of the system that can be exploited to pinpoint the faulty components. The root causes of the faults can be revealed through various techniques [START_REF] Zhou | Fault management in distributed systems[END_REF] like statistical inference [START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF], [START_REF] Barham | Using magpie for request extraction and workload modelling[END_REF], [START_REF] Chen | Pinpoint: Problem determination in large, dynamic internet services[END_REF], log-based causality analysis [START_REF] Reynolds | Pip: Detecting the unexpected in distributed systems[END_REF], [START_REF] Fonseca | X-trace: A pervasive network tracing framework[END_REF], [START_REF] Liu | D3s: Debugging deployed distributed systems[END_REF] or deterministic replay [START_REF] Geels | Friday: Global comprehension for distributed replay[END_REF], [START_REF] Liu | Wids checker: Combating bugs in distributed systems[END_REF], [START_REF] Killian | Life, death, and the critical transition: Finding liveness bugs in systems code[END_REF]. Fault diagnosis can be seen as the process of recognizing the most likely explanation for the symptoms based on some causal and effect models among the propositions of interest in the problem domain.

While diagnosis maximizes the usefulness of monitoring data, it faces some potentially significant practical limitations. The first one is simply scalability: diagnosis is NP-hard [START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF]. More profoundly, assuming knowledge of a decent model of the system internals might prove unrealistic (the "computer you didn't even know existed" nicely summarizes this feature). As a consequence, this work formulates the fault prediction problem in the context of end-to-end monitoring. The overall infrastructure is a black box, with no a priori knowledge of its structure. End-to-end probes are designed to test a functional property of this blackbox. Then, fault prediction involves a classification problem: from a selection of the probes (the training set), infer the outcomes of the other probes.

In many cases, the probes can be meaningfully replicated in the system. For instance, in the example that will be further described in section IV, the functionality is related to file access, and the probes are launched from the computing nodes to the storage nodes. Then, the replication takes a matrix form: the endpoints are the row-or column-entities, and the probes outcomes are the entries in this matrix. Formally, fault prediction becomes a matrix completion problem. The benefit with respect to a fully unstructured setting is that the matrix hypothesis grounds a Collaborative Filtering technique that is more powerful than behavioral clustering [START_REF] Quiroz | Design and evaluation of decentralized online clustering[END_REF], [START_REF] Zhang | Data stream clustering with affinity propagation[END_REF]: although the exact causes of failures might remain elusive, causality can be precisely modeled as the rank of the matrix, to be inferred, while clustering is bound to phenomenology and a-posteriori analysis of exemplars or centroids.

Our previous work [START_REF] Feng | Efficient distributed monitoring with active collaborative prediction[END_REF], inspired by [START_REF] Rish | Estimating end-to-end performance by collaborative prediction with active sampling[END_REF], addressed fault prediction in a classical Collaborative Prediction framework, as a purely spatial problem where the matrix is assumed to be a snapshot of the probes outcomes. Here, we take into account the fact that the system dynamically evolves at various time scales. Addressing this issue brings us closer to a model consistent with the practitioners expectations, but turns out to be significantly more difficult than the previous and more idealized setting. Not surprisingly, we cope with this difficulty by exploiting the dynamic setting for enriching the snapshot with time-related information: sequential monitoring deals with a sequence of partially observed matrices and makes prediction using information both from the current and previous time windows.

Within this framework, in order to be realistic, inference has to address two specific difficulties. Firstly, strongly imbalanced distributions must be assumed, as faults are hopefully much less represented that nominal behavior; this belongs to the spatial aspect of inference. Second, in the time domain, one cannot assume that measurements could be kept fully up-todate, as these systems are highly dynamic environments.

Fortunately, the same adaptivity strategy proved successful in various contexts to address both imbalanced distributions and noisy information: active learning iteratively selects mostinformative samples in order to best improve the prediction accuracy. On the other hand, and always with realism in mind, active learning has the drawbacks to slow down the fault discovery process, as it requires to build the input incrementally, and to make it more complicated, thus more fault-prone itself. A transversal goal of this work is thus to evaluate the specific contribution of the active learning ingredient in the fault inference methods that we propose.

Our experimental validation dataset comes form the European Grid Initiative (EGI). Grids tend to be regarded as somehow outdated, thus a few words about the relevance of the dataset might be necessary. The specific grid technologies of the 2000's have of course been superseded by cloud-related ones. However, the essential paradigm of grid is organized sharing: safely and fairly federating hardware, software and data resources from multiple independent providers. Thus grids exemplify both the physical problems of worldwide scale systems, and the major issues of a multi-owned multi-operated system, that are equally present in federated clouds.

The main contributions of this paper is the SMF (Sequential Matrix Factorization) algorithm, and its active learning version, SMFA (Sequential Matrix Factorization with active learning), that efficiently combines the spatial and temporal information sources. Its major strength is to balance exploration and exploitation with a self-calibrating parameter that formalizes and exploits the multi-scale intuition of the practitioners. The adaptive balancing does not suffer form the same drawbacks as active learning, as the required information does not need on-line querying.

The paper is organized as follows. Section II presents the matrix completion context and the empirical motivation for going beyond a pure matrix completion approach. Section III describes SMF and its active learning version, SMFA. The next three sections present a detailed experimental evaluation, where the vanilla algorithms are combined in various ways with agnostic optimizations (smoothing) and informationoriented ones (strategies for active learning). Section IV describes the experimental setting, and sections V and VI the results on the EGI dataset, before the usual conclusion.

II. CONTEXTS AND MOTIVATIONS

A. Matrix factorization for fault prediction

Consider the simple setting where a partial snapshot of the system is available through end-to-end probes (e.g. a ping). Assume that we have M sources and W targets. A probe selection method defines which ones of the possible M W probes are actually launched. Each individual result is binary: positive means that the probe failed, i.e. a fault occurred; negative, the probe succeeded. Let X be the sparse M × W binary matrix of the outcomes of the selected probes.

Then, the inference task falls into the general category of matrix completion: given a sparse matrix X, find a full matrix Y of the same size that approximates X, i.e. that minimizes some measure of discrepancy between X and Y . When Y is required to be equal to X on the known entries, the problem is termed exact completion, and approximate otherwise.

With such a general setting, the problem is hopelessly illdefined: in order to guess the missing entries, some assumptions have to be made about the matrix to recover Y . A natural one is to look for low-rank matrices, amounting to assume that a small number of hidden and partially shared factors (latent factors) affect the matrix entries.

The existence and unicity of a solution of exact matrix completion is a complicated problem (see e.g. [START_REF] Candès | The power of convex relaxation: Near-optimal matrix completion[END_REF]). Anyway, this formulation does not look very helpful, as rank minimization for completion is NP-hard and not feasible practically even for small sizes. However, it has paved the way for efficient algorithms, both for exact [START_REF] Candès | The power of convex relaxation: Near-optimal matrix completion[END_REF], [START_REF] Recht | A simpler approach to matrix completion[END_REF] and approximate [START_REF] Srebro | Maximum-margin matrix factorization[END_REF] completion. The main insight is to replace the rank by the trace (or nuclear) norm in the regularization term. For approximate completion, with hinge loss as the discrepancy measure, this yields the Maximum Margin Matrix Factorization (MMMF) algorithm [START_REF] Srebro | Maximum-margin matrix factorization[END_REF] with the objective function:

||Y Σ + CL h (X(S), Y (S)), (1)
where S is the set of known entries, ||.|| Σ is the trace norm, and

L h (A, B) = ij∈S max(0, 1 -A ij B ij )
is the hinge loss between A and B. This formulation, unlike the lowrank approximation, is convex, thus is guaranteed to find the global optimal solution. More generally, as the trace norm is a convex function, and the matrices of bounded trace norm are a convex set, any convex loss function provides a convex optimization problem. However, each observed entry acts as a constraint during the minimization process, and the computational complexity increases drastically with the number of involved constraints. Therefore, the external cost of each probe as a monitoring overhead doubles as an internal computational practical limit.

In the fault inference case, as the minimization procedure of Eq. ( 1) produces a real-valued matrix, a decision threshold (the classification common practice) gives the binary matrix of predicted behavior that represents the inferred outcomes of launching all M W probes.

In classical collaborative filtering, X is given (e.g. consumer ratings). With fault inference, there are more degrees of freedom: the goal is to optimize the tradeoff between the number of actually launched probes and the prediction quality. [START_REF] Rish | Estimating end-to-end performance by collaborative prediction with active sampling[END_REF] proposed a method to handle fault inference based on a collaborative prediction approach, further analyzed in [START_REF] Feng | Efficient distributed monitoring with active collaborative prediction[END_REF]. Although this method significantly reduces the number of required probes for acquiring an accurate view of the system, it is somehow static. Specifically, its only input is a snapshot from (assumed) simultaneous probes.

B. Motivation

This setting has two drawbacks. Firstly, fault behavior is multi scale in time: beyond the stable system components with consistent status over time, there are other ones which status may fluctuate intensely at peak time and remain stable at offpeak time. Second, transient faults are systematically observed: transients are faults that get on and off at high frequency and should be considered as noise; practitioners do not have a clear explanation for them, and they might as well be produced by flaws in the monitoring software itself. Of course, the problem is to disentangle them from real, but short-lived faults.

A further motivation is to explore the possibility of getting rid of adaptivity. [START_REF] Rish | Estimating end-to-end performance by collaborative prediction with active sampling[END_REF] integrated active learning with MMMF (min-margin heuristic) and [START_REF] Feng | Efficient distributed monitoring with active collaborative prediction[END_REF] showed that active learning was a required ingredient in the most difficult and realistic case on a real-world fault prediction example. On the other hand, active learning is somehow inconvenient: because the probe selection is adaptive, it requires a feedback loop, an interface between online analysis and monitoring, resulting in a more complicated software than with a pre-determined setting. At grid or cloud scale, any unnecessary source of complexity should be eliminated. Thus, we explore the hypothesis that the past could statically provide information equivalent to the one obtained by adaptively querying the present.

To summarize, we explore two questions: 1) can we improve fault inference by integrating historical information within the matrix completion framework; and 2) does the active leaning component remain useful in this case?

III. SEQUENTIAL MATRIX PREDICTIONN

A. Problem statement

There are two types of information available for sequential monitoring: spatial and temporal information. The spatial information can be thoroughly exploited by a collaborative prediction method like MMMF, while on the other hand, the temporal information which concerns the dynamics of the

X_1 X_2 X_t …… time X_3 Y_1 Y_2 Y_t …… Y_3 OK FAILURE UNKNOWN ESTIMATED
Fig. 1. Overview: at each time step, the current probes provide known results; simple matrix completion would use only these, while a spatio-temporal method exploits the history of probes (are they consistent?) and the history of inferences (were they accurate?).

entries provides extra opportunity for improving algorithm performance. Let X t ∈ B M ×W be the partially observed matrix at time t, Ŷt ∈ R M ×W be the result of a prediction algorithm,

Y t ∈ B M ×W be the thresholded binary version of Ŷt .
With threshold ρ, Y T (i, j) is defined by:

Y T (i, j) = -1 if ŶT (i, j) ≤ ρ, 1 otherwise.
With B = {-1, 1}, the binarization threshold ρ is set to 0. We define the task of sequential matrix prediction as: given a series of partially observed matrices (X 1 , . . . , X t ), predict the fully estimated matrix Y t . Figure 1 illustrates the sequential process: at each time step t, a matrix Y t is estimated from the observation sequence (X 1 , . . . , X t ) and the sequence of the past estimates (Y 1 , . . . , Y t-1 ).

B. The SMF algorithm

At each time step t we have a sequence of history predictions Y 1 , ..., Y t-1 . The confidence in these predictions can be expressed by the distance of each predicted value to the separation hyper-plane. Thus two types of predictions emerge: those predictions close to the separation plane and those far from the separation plane. We call the former ones the most uncertain prediction set and the latter ones the most confident prediction set. From the system point of view, the most uncertain predictions are related to those components with short term status like the transient faults and the most confident predictions are related to those components with relatively long term stable status.

In this section, we propose an algorithm, i.e. sequential matrix factorization (SMF), to capture both the long term and short term status behavior by utilizing the spatial information as in MMMF, and exploring the most uncertain and most confident heuristic concealed in the temporal information meanwhile. In the following, S u , S c and S r are index sets of matrix X, for denoting the most uncertain prediction set, most confident prediction set and a random sample set, respectively. The observed set (labels queried at time t) is S u ∪ S r . All three sets depend on t, but we dropped the unnecessary supplementary indices.

Recall that the objective function of MMMF is composed of two terms (Eq. 1): the first one is the trace norm of the estimated matrix Y t and the second term is the hinge loss between estimation and observation. In the following we will develop the objective function of SMF by adding the most uncertain and the most confident information to Eq. 1.

First we consider the most uncertain information. The most uncertain prediction set S u (entries with small margin to the classification hyper-plane) can be derived from Y t-1 and their labels at time t can be queried from the system. Hence, the ground truth of those most uncertain predictions in Y t-1 is available in the sample set X t . We denote this as X t (S u ).

The second information, i.e., the most confident predictions, is concealed in the history estimation. For these most confident entries, instead of sampling their true labels at time t, their previous predictions can be used directly in the next run. Specifically, in SMF we choose those most confident predictions from Y t-1 and assume their states remain unchanged at time t with a confidence level γ.

We compute γ in terms of the overall difference between Y t-1 and X t ( i.e. the difference between last estimation and current observation) on the observed entries in X t . Any classification criteria like accuracy, true positive rate (TPR) or FSCORE can be used for measuring this discrepancy. Since in X t the observed set is S u ∪ S r , we therefore compute γ as the difference between X t (S u ∪ S r ) and Y t-1 (S u ∪ S r ) as follows:

γ = TPR(Y t-1 (S u ∪ S r ), X t (S u ∪ S r )), (2)
where TPR(A, B) is the true positive rate of A according to the ground truth set B. In the prediction, γ is used as an adaptive cost ratio which adjusts the weight (penalty) of the heuristic information in the objective function (similar to the coefficient C in Eq. 1). The reason we choose TPR as the penalty lies in the fact that in distributed system monitoring successfully discovering a failure comes more important than alerting one incorrectly (see section IV-C).

In addition to the most uncertain set S u and most confident set S c , we keep the random set S r in the objective function of SMF. The random sample set S r serves as a term for avoiding over-fitting the history information, as sudden change between past estimation and current observation might occur. To sum up, SMF has the following objective function:

||Y t || Σ + CL h (Y t (S), X t (S)) + CγL h (Y t (S c ), Y t-1 (S c )), (3)
where S = S u ∪ S r is the sample set which labels are queried at time t and S c is the most confident prediction set that we borrow from t -1. Thus the difference between Eq. 1 and 3 is exhibited by the selection of S u and the presence of S c . As in Eq. 1 this function is convex, thus can be directly minimized. Figure 2 illustrates the selection process. The most uncertain and most confident predictions are selected from Y t-1 , where labels of the former set are further queried at time t, and labels of the latter set are the estimation values in the last run.

Algorithm 1 describes the pseudocode of SMF. At the beginning, the sample set S of X t is generated by a combination of selecting most uncertain predictions from Y t-1 and a random sampling (line 1 to 3). Then the true labels of S are queried from the system and are used as ground truth for measuring the discrepancy between Y t-1 and X t (line 4, 5). The most confident predictions in Y t-1 are selected in the following step and used as input for the estimation. In the final step Y t is derived by finding an estimation which minimizes Eq. 3.

C. Sequential matrix factorization with active sampling, SMFA

In active matrix factorization [START_REF] Rish | Estimating end-to-end performance by collaborative prediction with active sampling[END_REF], [START_REF] Feng | Efficient distributed monitoring with active collaborative prediction[END_REF], the prediction performance is improved by selecting the sample entries in X t actively and iteratively, using the most uncertain heuristic from the very last prediction until the maximum allowed number of samples is reached. The key idea is that, with the progress of each iteration, confidence in the estimation increases simultaneously.

In SMF, sample entries are selected under three policies: random, most uncertain and most confident. The latter two strategies rely on information from the last prediction Y t-1 . The selection of active samples is complete all at once in SMF and no further actions can be taken given its first estimation of Y . Sequential matrix factorization with active sampling (SMFA) builds a sequence of estimators Y i t , i = 2, 3, ... that iteratively benefits form the estimation process to refine the definition of both the most uncertain and most confident predictions.

Algorithm 2 describes the steps of SMFA. We denote the estimation matrix at the ith iteration of time t as Y i t . At the beginning, SMF is used to give an initial estimation Y 0 t from Y t-1 (line 4), then an iterative estimation is employed on the prediction sequence Y i t , i = 1, 2, ... until the maximum number of samples is reached (line 5 to 9). Active sample

S c ← Sample(h 3 , N c , Y t-1 ), /*select N c most confident samples from Y t-1 */; 7 Y t ← arg min Y ||Y t || Σ + CL h (Y t (S), X t (S)) + CγL h (Y t (S c ), Y t-1 (S c
)) /*find an estimation that minimizes the objective function*/; 8 return Y t selection is engaged each time the SMF algorithm selects the most uncertain and most confident predictions from the last estimation.

D. Smoothing the results

Although one of the key features in SMF or SMFA is to preserve the of predictions between consecutive time windows, extra smoothing of the outputs can be considered. Smoothing the prediction sequence with exponentially weighted moving average (EWM) works as follows:

Y ′ k (i, j) = Y k (i, j), k = t -l + 1, θY k (i, j) + (1 -θ)Y ′ k-1 (i, j), k = t -l + 2, ..., t , (4)
where θ ∈ (0, 1) is a user-defined damping factor, and l is the lag window length.

E. Methods summary

Table I summarizes the methods introduced in the two previous sections, with their inputs, outputs and related parameters. For a given method H, its smoothed version is noted H * (e.g. the smoothed version of SMF is noted SMF * in later section).

IV. EXPERIMENTAL SETTING

A. The source

The of science, including high energy physics, humanities, biology and more. The infrastructure federates some 350 sites worldwide, gathering more than 250,000 cores, which makes it the largest non-profit distributed system worldwide. Hardware and software failures are intrinsic to such large-scale systems. Middleware e.g. gLite [START_REF] Laure | Programming the Grid with gLite[END_REF], Globus [START_REF] Foster | The globus toolkit for grid computing[END_REF] or ARC [START_REF] Ellert | Advanced resource connector middleware for lightweight computational grids[END_REF] cannot handle this without substantial human intervention. Access rights to EGI are primarily organized along the concept of Virtual Organization (VO), and each of the 200 VOs has to be specifically configured on its supporting sites, which adds complexity and introduces extra failures. User communities exploit two strategies to cope with faults: overlay middleware e.g. DIRAC [START_REF] Tsaregorodtsev | DIRAC3 . The New Generation of the LHCb Grid Software[END_REF], DIANE [START_REF] Moscicki | Diane -distributed analysis environment for gridenabled simulation and analysis of physics data[END_REF], AliEn [START_REF] Bagnasco | Alien: Alice environment on the grid[END_REF] and PaNDA [START_REF] Maeno | Panda: distributed production and distributed analysis system for atlas[END_REF] implements specific fault-tolerance strategies to isolate users from the vagaries of the infrastructure; and monitoring identifies problems and quantifies performance w.r.t. quality of service agreements.

Y i+1 t ← SM F (Y ti , N u , N c , N r , C); 8 n = n + N u + N c + N r ; 9 i = i + 1 ; 10 Y t = Y i t ; 11 return Y t
The data source for this study is the Biomed VO. Biomed has access to 256 Computing Elements (CEs) and 121 Storage Elements (SEs). CEs are shares of computing resources, implemented as queues of each site manager (e.g. PBS), and SEs are shares of storage resources; the formal definition is part of the Glue Information model [START_REF] Andreozzi | Glue Schema Specification, V.2.0[END_REF]. File access remains one the major issues, for numerous causes spanning from hardware breakdowns to entanglements in the complicated verification of access rights, and including the bizarre transients reported by operations managers.

B. Data description

The dataset1 was collected on EGI by submitting a series of jobs to 212 Biomed CEs every two hours between Mon Nov 12 15:52 CET 2012 and Sat Nov 24 09:54 CET 2012, for about 282 hours in total. Each job tested the service availability between its CE and each of 96 Biomed SEs, by launching the lcg-cp probe. lcg-cp copies a file (like Unix cp), thus is a relatively high-level probe that tests core access (network path), availability of the access control services as well as reading and writing capacities. The CEs and SEs have been preselected as relatively reliable, in order to eliminate trivially discoverable faults.

Of course, our test jobs were fully protected again the consequences of a probe failure (the job successful termination does not depend on the outcome of the probe), and the procedure has been designed so that the resources involved in running the jobs are as disjoint as possible from those required by the probes. However, our test jobs were no more immune to middleware faults than any other user job, and a significant part of them did fail, thus reporting no information at all. In order to get a consistent sample, we deleted the data from those CEs with less than 7000 observed entries and also from those time windows with less than 50% data observed. This results in a data cube of size 79 × 96 × 119, with each dimension corresponding to CE, SE, and time window respectively. The goal of our experiment is to predict whether the jth SE is accessible from the ith CE at a given time window t, and this data cube is the ground truth for the prediction algorithms. We use 0 for representing a missing observation, 1 for a Failed probe (job succeeded and lcg-cp failed), and -1 for an OK probe. This notation is in accordance with the general meaning of positive (abnormal) and negative (normal) in statistics.

Let M be the total number of CEs, W be the total number of SEs, and t k,k=1,2,...,T be the time window sequence, we further note N t k as the number of observed entries at t k and N + t k be the number of positive entries (failures) at t k , then the observation rate and test failure rate at t k are defined as r t k = N t k /M W and f t k = N + t k /M W, respectively. Figure 3(a) illustrates the observation rate r t k and failure rate f t k of the dataset. Most of the observation rates stay above 70% and the failure rates are less than 20%. A high observation rate ensures a more reliable result for performance evaluation, since we have more ground truth information at hand. A relatively stable failure rate indicates a consistent system status in consecutive time windows. The failure rate presents some breakpoints, e.g. the sharp drop from 18.74% to 12.57% at the 101st time window. Their impact on prediction performance is discussed in sections V and VI.

Another interesting aspect of the data is the duration length of each status (i.e. OK or Failed). The duration length of a status is defined as the number of time windows the status spans until a different status is observed in the sequence; Table II gives an example, and Figure 3(b) shows the cumulative distributions. The high proportion of duration length 1 for Failed (about 25%) illustrates the phenomenon of transients, while the about 20% entries for both success and failure with a duration length at least 26 illustrate relative stable behavior. These distributions sustain our considerations about a multiscale in time behavior.

C. Criteria

With the availability of the ground truth, the classical performance indicators for binary classification can be measured. Accuracy (the ratio of correctly predicted entries over the total number of entries) is of limited interest: as the data set is not balanced, overly optimistic algorithms that favor OK predictions will exhibit satisfactory accuracy. The indicators associated with the risks (confusion matrix) are more informative: sensitivity (True Positive Rate), the proportion of actual positives that are correctly predicted; specificity, the proportion of actual negatives that are correctly predicted; precision, the ratio of true positives over all predicted positives. They all make sense for operational needs, but sensitivity is the most important one: an undetected failure (bad sensitivity) results in a failed user job and a dissatisfied user, while a false negative might go unnoticed; specifically when the services are redundant (e.g. from replicated data), the failed request can be transparently rerouted to another server. Of course, specificity is nonetheless an important criterion, and compound criteria such as precision, or Fscore measure various tradeoffs between them.

The last important indicator is the Matthews Correlation Coefficient (MCC), a correlation coefficient between the observed and predicted binary classifications that is relatively insensitive to unbalanced classes. Its interest comes from the fact that MCC is a proxy for the Area Under ROC (Receiver Operating Characteristic) Curve (AUC), which summarizes the intrinsic quality of a binary classifier independent of the decision threshold. Moreover, MCC does not assume that the classification error is a reasonable estimation of the prediction error [START_REF] Joachims | A support vector method for multivariate performance measures[END_REF], thus is a more robust indicator with respect to the objective functions involved in the optimization step of the algorithms. Other related indicators such as those involved in Neymann-Pearson learning [START_REF] Scott | Performance measures for neyman-pearson classification[END_REF] have not been reported, as they have not still gained widespread acceptance.

D. Details

All experiments are performed 10 times and results are reported their average. For all algorithms, 10% of the total entries are selected as training set (i.e. N = 10% × W × M ), and for SMF and SMFA another 10% of the most confident entries with values from Y t-1 is added as in algorithm-1. This supplementary information does not require any probe: it only exploits the past (inferred) outcomes. The adaptive weight for the most confident entries is computed according to line 5 in algorithm-1. Table III lists the concrete parameter settings for the algorithms of Table I. Parameters marked with a '+' are selected via training and validation on the first 20 time windows.

V. EXPERIMENTAL RESULTS -NON-CURATED DATASET

We first analyze the vanilla algorithms, then evaluate the impact of active learning and of smoothing. Some supplementary material is available in [START_REF] Feng | Efficient end-to-end monitoring for fault management in distributed systems[END_REF].

A. Vanilla methods

The results of Table IV can be analyzed along different paths. Firstly, while both algorithms reach fairly good specificity, sensitivity exhibits only acceptable performance: 25-30% of the actual failures would not be predicted. This is a natural, but nonetheless problematic effect of the imbalanced dataset.

SMF shows a significant advantage on sensitivity, which is our primary performance indicator (c.f. section IV-C) and is also better for specificity, translating into an altogether clear advantage on the compound indicators.

The time series presented in Figures 4(a) and 4(b) provide some insight on the factors of performance. MMMF and SMF behave essentially in lockstep on sensitivity, showing that matrix factorization provides a decisive contribution; the most important gains of SMF over MMMF occur in the relatively stable intervals (e.g. 40-55) where the knowledge of the past matters. This is also true for specificity, except at the sharp drop of SMF at the 81st time window (recall that we use 20 time windows as initial input, so this is the 101st time window in the original data). As mentioned in IV-B, this is caused by a drop in real failures between the observations in the two adjacent time windows. In this case the historical information does not help, but instead hinders performance improvement, biasing the algorithm towards false positives. As explained in section III-C, active learning is a candidate for improving on sensitivity. Table V compares MMMF and SMF with their active versions. In both cases, sensitivity improves by 11%, while the decrease in specificity is negligible (respectively 1% and 0.2%). Moreover, SMFA outperforms MMMFA, but active learning is powerful enough to make MMMFA outperform SMF on sensitivity by 6%. In other words, the good selection of current information allows to forget the past: for selecting the most uncertain prediction, which is likely to be on the positive entries, active sampling on the current data does a better job than passive history. As explained before, one can wonder whether if simple smoothing would not be competitive with the active approach, with much less complexity. In fact, smoothing actually often degrades sensitivity even with respect to the vanilla algorithm (e.g. MMMF goes from 0.713 down to 0.700): the smoothing process over-corrects the false positive predictions.

B. Active methods

C. Smoothing

Table VI compares the active versus smoothing approach (e.g. SMFA vs SMF*); clearly smoothing is not competitive with active learning on sensitivity, although it always improves specificity and sometimes the compound criteria. On the other hand, combining smoothing and active learning has contrasted results, degrading MMMFA sensitivity, but marginally improving on SMFA.

D. Summary

The above analysis firstly emphasizes the effectiveness of the sequential matrix factorization approach, and specifically of the proposed SMF algorithm and its variants: a properly synthesized use of spatial and temporal information significantly outperforms a purely spatial method. Then, active learning is consistently and significantly beneficial. As the positive entries are the minority part of the whole population, it is therefore difficult to uncover them by using any conventional method with equal cost on positive and negative entries. However, with the aid of active sampling it is possible to unveil those difficult to predict entries, since they are more likely to be exposed and labeled during the active sampling process. Finally, simple smoothing cannot compete with the active approach, and should be considered useful only combined with active learning, and only when false positives are a major concern.

VI. EXPERIMENTAL RESULTS WITH THE CURATED DATASET

A. The curated dataset

It could be argued that our benchmark is too easy: the tail of the distribution of the failure duration lengths corresponds to long-lasting errors, that basic monitoring tools (e.g. heartbeats) would report anyway, and the prediction methods should be applied only to more elusive causes of errors. While this is disputable (remember that all probes succeed as jobs, thus a significant part of the services are up and running), it is worth assessing the performance of the methods when these systematic errors are eliminated. Therefore, we designed a second set of experiments, with curated matrices as the reference fault structure. The curated dataset is derived by removing those lines and columns with at least 98% failed entries in the reference matrices. Figure 5(a) shows the magnitude of the decrease in the failure rate, approximately from 15% to 5% on average. Moreover, the CDF of failure duration length also experiences a sharp change (Figure 5(b)). The percentage of lengthone durations increases from 25% to about 60%, and the percentage of duration lengths less than 20 grows from 75% to approximately 92%. In other words, after the elimination of systematic failures, the proportion of short term failures increases significantly.

B. Vanilla and active methods

The very adverse curated dataset produces quite interesting results (Table VII) concerning sensitivity. Most importantly, all vanilla method perform poorly: more than 60% of the faults will get unpredicted. The extreme imbalance of the data obviously highlights the limits of accuracy-based methods (MMMF). Figure 6 give some insights about the issues encountered by SMF. For sensitivity, contrary to the non-curated case, SMF and MMMF are not in lockstep. More precisely, there are intervals where they go in opposite directions, e.g. at time 40-45; there, taking into account the past somehow helps SMF to limit its loss, but the impact of the catastrophic behavior of MMMF is still too strong.

As can be expected, active learning procures a decisive improvement, in the order of more than 50% for both. SMFA has a clear advantage. It capable of discovering more than 50% of the faults while maintaining good specificity and acceptable precision: only 25% of the alarms are spurious.

C. Higher sampling rate

So far, the sampling rate was limited to 10%. Table VIII illustrates the result of increased sample rates, i.e. 10%, 15% and 20%, of SMFA * on the curated dataset. Results are averaged on a 5-run experiment. A steady and notable improvement is exhibited. For example, at 20%, SMFA * finds out 72% of the faults while keeping a balanced MCC value of 0.825. The good news is that the prediction performance increases steadily with the sample rate even in the curated situation. However, the sampling rate drives two costs: the monitoring overhead per se, and the computational complexity, as discussed in section II-A. To control the computational cost, accelerating methods like Fast MMMF [START_REF] Rennie | Fast maximum margin matrix factorization for collaborative prediction[END_REF] might be required.

D. Summary

The curated dataset is highly imbalanced, with only about 5% positive entries. Then static accuracy-based classification becomes awkward and exhibits poor performance. Active learning is one of the few approaches that can contribute to alleviate this issue. Our question in this section was its impact within already "smart" -heuristic based -methods. The results show that active learning carries a consistent improvement, with a very similar factor, for the two relatively different heuristics involved with SMF and MMMF; in other words, active learning is robust in this context.

VII. CONCLUSION

Efficient monitoring of production grids and clouds at acceptable manpower cost cannot assume exhaustive a priori knowledge of their software and hardware infrastructures. In this context, and with end-to-end probing as sole data acquisition strategy, fault discovery can be re-casted as an inference task, and can borrow methods from collaborative prediction. The challenge as well as the opportunity brought by switching from a static, snapshot-oriented, view of the monitoring to considering the time dimension reside in the sequential correlation between consecutive data points. We have shown that these sequential patterns, if exploited properly, can play an important role in improving prediction performance.

This paper explores various methods that combine time and space information with increasing complexity. It proposes and evaluates SMF, a fully integrated method that exploits both the recent advances in matrix factorization for the spatial information and a new heuristics based on historical information. The effectiveness of the SMF approach has been exemplified on datasets of increasing difficulty. In all cases, active learning unleashed the full potential of coupling the most confident and the most uncertain heuristics, which is the cornerstone of SMF. To our question about the need of adaptivity, and thus more complicated and fault-prone algorithms, the answer is unambiguous: a method versatile enough for accommodating various levels of difficulty on both the sensitivity and specificity criteria must include on-line adaptivity through active learning.

Future work will go further in the adaptivity direction. The first perspective considers self-calibrating not only the SMF balancing parameter, but also the SMFA parameters in an auto-learning approach. The samples are selected with two strategies: the most uncertain predictions in the last run guide the selection of samples to enhance the current prediction confidence, while the random sampling strategy avoids overfitting the past.The current sample ratio between the two strategies is fixed and set to 1 : 1. However, a straightforward extension is to address this problem under the sequential decision optimization framework. The hybrid optimization indicator of [START_REF] Wang | Hypervolume indicator and dominance reward based multi-objective Monte-Carlo Tree Search[END_REF] can be considered to efficiently balance the exploitation and exploration trade-off.

We have seen that performance was limited by the occurrence of abrupt changes, where the advantage of taking into account the past turns into a liability. The second perspective considers a semi-supervised online change detection framework that has already proved to be efficient at the level of the individual timeserie [START_REF] Feng | Efficient end-to-end monitoring for fault management in distributed systems[END_REF]. The next step would be to extend it towards the full matrix data.

Fig. 3 .

 3 Fig. 3. Empirical statistics of the dataset.

  of random samples in Xt; C + = 10, coefficient for slack penalty. SMF Nr = 5% of random samples in Xt; Nu = 5% of most uncertain samples in Xt; Nc = 10% of most confident samples from Yt-1; C + = 10, slack penalty. MMMFA P0 = 5%, initial sample rate; Pa = 1%, active sample rate at each iteration; ρ + = 0.5, equal size of random samples and most uncertain samples at each active iteration; C + = 10, slack penalty. SMFA P0 = 5%, initial sample rate; Pa = 1%, active sample rate at each iteration; Nc, 10% of most confident prediction from Yt i ; ρ + = 0.5, equal size of random samples and most uncertain samples at each active iteration; C + = 10, slack penalty.

Fig. 4 .

 4 Fig. 4. Time series of sensitivity and specificity for the vanilla algorithms. Windows are numbered from the first one where prediction starts.

Fig. 5 .

 5 Fig. 5. Comparison of curated and un-curated datasets.

Fig. 6 .

 6 Fig. 6. Curated dataset: time series of sensitivity and specificity for the vanilla algorithms. Windows are numbered from the first one where prediction starts.

  Algorithm 1: SMF, Sequential Matrix Factorization Input: Y t-1 , last prediction; N u , number of most uncertain samples from Y t-1 ; N c , number of most confident samples from Y t-1 ; N r , number of random samples; C, slack penalty. Output: Full real-valued matrix Y t Initialize: Init h 1 , h 2 , h 3 , /*Initialize the most uncertain, most confident and random sampling heuristic, respectively*/; 1 S u ← Sample(h 1 , N u , Y t-1 ) /*select N u most uncertain sample indexes from Y t-1 */; 2 S r ← Sample(h 2 , N r ), /*select N r random sample indexes*/; 3 S ← S u ∪ S r ; 4 X t (S) ← QueryLabels(S), /*query the true label for entries in S*/ ; 5 γ ← T P R(X t (S), Y t-1 (S)) /*given X t (S) (true labels for entries in S), compute the true positive rate of Y t-1 (S)*/; 6

  European Grid Infrastructure (EGI) enables access to computing resources for European researchers from all fields Algorithm 2: SMFA, Sequential Matrix Factorization with active sampling Input: N , max # of new samples; Y t-1 , last prediction; P 0 , initial sample rate for the 1st prediction; P a , active sample rate at each iteration; ρ, ratio of random samples and most uncertain samples for P a ; C, slack penalty. Output: Full real-valued matrix Y t initialize: Init(N c ). /*Initialize the number of most confident samples to select in each iteration*/; 1 i = 0 /*current iteration index*/ ; 2 n = N × P 0 /*current number of new samples*/ ; 3 [N u , N r ] ← getSampleSize(n, ρ) /*Get random and most uncertain sample size for the initial prediction*/; 4 Y i t ← SM F (Y t-1 , N u , N c , N r , C); 5 while (n < N ) do 6 [N u , N r ] ← getSampleSize(N × P a , ρ) /*Get random and most uncertain sample size according to ρ and P a */;

	7

The dataset will be publicly available of the Grid Observatory web site (www.grid-observatory.org) from April

ACKNOWLEDGMENTS D. Feng acknowledges the support of the Chinese Scholarship Council. C. Germain acknowledges the support of the French cooperative project TIMCO, Pôle de Compétitivité Systematic (FUI 13). The authors acknowledge the support of The European Infrastructure Project EGI-InsPIRE INFSO-RI-261323 and France Grilles for providing computing resources on the French National Grid Infrastructure. The authors thank Michèle Sebag for stimulating discussions and Tristan Glatard for expert grid advice.


William E Marsh
email: william@wemarsh.com

Jean-Rémy Chardonnet
email: jean-remy.chardonnet@ensam.eu

Frédéric Merienne
email: frederic.merienne@ensam.eu

Virtual Distance Estimation in a CAVE

Keywords: Virtual reality, Distance perception, Spatial cognition, Scale, Architecture, CAVE

Past studies have shown consistent underestimation of distances in virtual reality, though the exact causes remain unclear. Many virtual distance cues have been investigated, but past work has failed to account for the possible addition of cues from the physical environment. We describe two studies that assess users' performance and strategies when judging horizontal and vertical distances in a CAVE. Results indicate that users attempt to leverage cues from the physical environment when available and, if allowed, use a locomotion interface to move the virtual viewpoint to facilitate this.

Introduction

When interacting with a virtual architectural model, decision makers must accurately perceive the spatial layout of a virtual environment (VE) and make decisions, often regarding a building that has not yet been built. However, the current state of virtual reality (VR) technology presents challenges. One such challenge is that perceived spaces are routinely compressed in VR.

There are two broad categories of distance judgements: egocentric and exocentric. In egocentric tasks, distances are judged from the observer to an object. In exocentric tasks, distances are judged between two objects in the environment, neither of which is collocated with the observer. Past literature has sometimes shown different biases depending on whether a judgement is egocentric or exocentric. When movement is allowed, the distinction between egocentric and exocentric distances is less clear because a person could move in such a way that an exocentric judgement becomes egocentric, or vice-versa.

Many authors have investigated biases related to physical or virtual distance spans on, or parallel to, the ground plane. However, though they are particularly relevant to architectural decisions, there is a notable lack of studies involving vertical distances, and this dearth is even more profound in VR.

Methods to Assess Perceived Distances

In the following sections, we describe past findings regarding distance perception, and then we discuss our own studies investigating distance perception in a CAVE. This work hinges on identifying appropriate ways to measure perceived distances.

A common way of assessing perceived distances is blind walking, in which participants are asked to walk without vision to a previously viewed landmark [e.g . 11]. However, motor recalibration effects have been reported [START_REF] Mohler | The influence of feedback on egocentric distance judgments in real and virtual environments[END_REF] by which participants learn to improve their estimates through training. These may reflect high-level cognition, as opposed to overall calibration. The effects can be avoided through triangulated blind walking or by withholding performance feedback [START_REF] Richardson | The effect of feedback training on distance estimation in virtual environments[END_REF].

Perceptual matching is another means of testing the accuracy of perceived distances. In this paradigm, participants are asked to reproduce a distance span, often by directing the experimenter to place a target at an equivalent distance [e.g. 9]. Due to the difficulty in blind walking a remembered vertical distance, perceptual matching was chosen for the studies described in this paper.

In the virtual architecture domain, it may be important to reproduce distances both egocentrically and exocentrically. Past researchers have often required participants to learn exocentric distance spans and then reproduce them egocentrically. This difference in orientation between learning and recall should prevent participants from using strategies relying on purely visual snapshots, though it may involve higher-level processing. In the studies described here, perceptual matching estimates are made from the same orientation as experienced during learning, but from a different distance, to prevent judgements based solely on visual angle.

Distance Perception in Real Environments

Most distance perception research has focused on horizontal distances. Realworld distance estimates on the ground are usually very accurate over short ranges, though depth spans are sometimes reportedly compressed relative to frontal spans [START_REF] Li | On the anisotropy of perceived ground extents and the interpretation of walked distance as a measure of perception[END_REF]. In general, absolute distances can be calculated visually with knowledge about the size of familiar objects, the angle between an observer's eye height and an object or, when an object is on the ground, linear perspective. Some additional cues may help when judging distances shorter than approximately 2 m. Binocular disparity provides information, together with the ocular convergence required to target an object and the accommodation required for the lens to focus on an object. Motion parallax and optic flow can also help if the observer is moving.

Vertical distances viewed from the top are often overestimated. Large heights are also overestimated from the bottom, though to a lesser degree. When observing a frontal view of an object, vertical distances are often overestimated by 10-15% relative to horizontal distances [START_REF] Yang | Seeing big things: Overestimation of heights is greater for real objects than for objects in pictures[END_REF]. Stefanucci and Proffitt [START_REF] Stefanucci | The roles of altitude and fear in the perception of height[END_REF] report evidence that these biases may be moderated by an individual's fear of heights.

When constructing the spatial model of a scene, the visual cues above are integrated with proprioceptive, efferent [START_REF] Waller | Body-based senses enhance knowledge of directions in large-scale environments[END_REF], and possibly vestibular information from movements [START_REF] Chrastil | Active and passive contributions to spatial learning[END_REF]. Some researchers have implicated effort, as well as the capacity and intention to interact [START_REF] Witt | Perceiving distance: A role of effort and intent[END_REF], in distance perception. For example, wearing a backpack has been shown to lead to increased distance estimates [START_REF] Proffitt | The role of effort in perceiving distance[END_REF], though Durgin et al. [START_REF] Durgin | Who is being deceived? the experimental demands of wearing a backpack[END_REF] point to alternate explanations. If effort is indeed linked to distance perception, it follows that vertical movement requires greater effort (climbing) than movement along the horizontal plane (walking), and thus vertical distances should be perceived as greater. A related idea, Evolved Navigation Theory, is that biases may relate to evolutionary goals of avoiding danger [START_REF] Jackson | Evolved navigation theory and the environmental vertical illusion[END_REF]. In either case, there is a link to Gibson's [START_REF] Gibson | The Ecological Approach to Visual Perception[END_REF] concept of affordances, in which behavioral potential impacts perception.

Distance Perception in Virtual Environments

Some of the biases described above in Sec. 1.2 also exist in VR, though they are generally greater. Distances are linearly compressed in VEs relative to corresponding estimates in the real world [START_REF] Messing | Distance perception and the visual horizon in head-mounted displays[END_REF] by up to about 50% [START_REF] Loomis | Visual perception of egocentric distance in real and virtual environments[END_REF], with reports of rare exceptions [START_REF] Interrante | Distance perception in immersive virtual environments, revisited[END_REF]. As in the real world, depth spans are often compressed relative to frontal spans [START_REF] Li | On the anisotropy of perceived ground extents and the interpretation of walked distance as a measure of perception[END_REF]. Additionally, Fink et al. [START_REF] Fink | Obstacle avoidance during walking in real and virtual environments[END_REF] showed differences in trajectories between real and virtual movements, indicating greater uncertainty about object positions.

There is a shortage of literature examining vertical distance perception. However, the work referenced above in Sec. 1.2 regarding the horizontal-vertical illusion showed a greater effect in the real world (or VR) than in photos with distances controlled for optical angle, and the magnitude of this illusion increases with physical perceived height on the projection surface [START_REF] Yang | Seeing big things: Overestimation of heights is greater for real objects than for objects in pictures[END_REF]. This shows that humans have knowledge of the display surface and that it may affect perception.

Many authors have studied these phenomena, but the causes remain unclear. The problems may be due to some combination of factors involving sensory fidelity, equipment constraints (i.e. weight), and unnatural interfaces. In principle, VE designers should aim to provide the same cues that are available in the real world. However, in practice, this is never quite possible with current technology. For example, graphics fidelity is often reduced in VR. Thompson et al. [20] showed no impact of impoverished graphics on distance estimates, but distance cues including optic flow may still be limited. In VR, accommodation and convergence cues can be in conflict, possibly also impacting virtual distance estimates [START_REF] Drascic | Perceptual issues in augmented reality[END_REF].

Interfaces for large-scale virtual locomotion often do not allow for the types of body-based translation movements, such as walking, that may lead to construction of accurate spatial representations [START_REF] Ruddle | Walking improves your cognitive map in environments that are large-scale and large in extent[END_REF]. In fact, Sun et al. [START_REF] Sun | Multisensory integration in the estimation of relative path length[END_REF] showed that providing body-based proprioceptive/efferent information improved path length estimates, even if it was inconsistent with reality as experienced visually. A common class of interface for virtual locomotion is the handheld wand. There are several variations and control schemes, but because they use different muscle groups and actions involve less effort than in the real world, they may lead to non-veridical distance estimates.

Past research has indicated that the intention to interact with an environment and the expected effort associated with that interaction impact distance perception [START_REF] Witt | Perceiving distance: A role of effort and intent[END_REF]. These studies have primarily focused on horizontal distances, but such theories should predict underestimation of vertical distances in VR because is often easier to travel virtually (by flying) to higher elevations than it is in the real world (by climbing).

Physical characteristics of a VR system may also serve as distance cues. For example, in a CAVE it is usually possible to see corners where the screens meet. In addition, optical accommodation can inform the user about screen position and orientation [START_REF] Todorović | The effect of the observer vantage point on perceived distortions in linear perspective images[END_REF]. It is conceivable that a user, particularly one with a relatively low level of virtual presence [as defined by 23], may use these physical aspects when judging virtual distances. However, most studies on virtual distance estimation have been administered using a head-mounted display (HMD), likely in an attempt to limit these physical cues. For scenarios in which presence is not critical, these cues may be beneficial. Allowing movement may enable users to move into positions to make maximal use of distance cues provided by the physical system. Alternately, cues in the physical environment may introduce additional unwanted biases, so it is important to study users' abilities to use them effectively.

Architectural Decisions in Virtual Reality

The present work is motivated by the need for scale-one distance perception in architectural walk-throughs. The architectural domain has some key requirements that differentiate it from much of the past literature on spatial perception.

First, architectural decisions frequently involve vertical judgements. Most past work has involved only horizontal distances, but the studies in this paper include a vertical condition.

Second, virtual architectural models are often viewed by more than one person at a time. For this reason, walk-throughs often take place on a large screen or in a CAVE, as opposed to an HMD. Most past virtual distance estimation research has been conducted using an HMD, so those results may provide a good starting point, but they fail to predict the interplay between virtual and physical distance cues that are present in a CAVE. The studies reported in this paper were conducted in a four-sided CAVE. Because trials were quick, participants were not expected to achieve high levels of presence, meaning that they might use distance cues from both the VE and the physical system. This paper will not address additional distortions that arise as multiple untracked users move away from the center of projection [START_REF] Banks | Perception of 3-D layout in stereo displays[END_REF].

Study 1: Distance Estimation and the Role of Locomotion in a CAVE

We conducted a study to investigate horizontal and vertical distance estimation in a high-fidelity, fully furnished virtual office environment displayed in a CAVE.

This was intended to provide insight into the design space for VR systems used for architectural decisions. Specifically, there were two competing hypotheses in Study 1. First, the ability to locomote may help users judge distances by maneuvering to the optimal vantage point(s). If this is the case, we hoped that the experiment would provide insight into the strategies employed. Alternately, using a handheld wand may lead to greater underestimation, particularly on vertical spans, due to the ease of travel.

Method

Participants. Twelve participants (4 female, M = 26.3 years, SD = 5.5 years) were recruited through word of mouth. The only requirements were good (corrected) binocular vision and lack of expertise in the CAVE. Some were familiar with VR, but specific knowledge of the system dimensions was undesirable because it could have biased judgements. There was no compensation for participation.

Apparatus. All distances were learned in a CAVE measuring 3×3 m horizontally and 2.67 m in height, with rear projection on three walls and front projection on the floor. All walls have passive stereoscopic projection. Participants' head positions were tracked with an ARTTRACK2 optical tracking system to control the center of projection. Participants recalled distances in the same room, with their backs facing the CAVE.

Stimuli and Design. The study employed a 2 (interface) × 3 (judgement direction) within-subjects design. Every participant completed two study sessions, counterbalanced, each with a different interface condition (Flystick, none). Three judgement directions (depth, width, vertical) were each experienced three times per session, in random order, such that each participant completed 9 trials per session (18 trials total). Each trial comprised two phases: learning and recall. The learning phase for all trials took place in the same virtual office scene, rendered in Fig. 1a, but each trial in a given session was observed from a different orientation, randomly chosen from a set of nine possible. In the recall phase, exocentric perceptual matching was used to reproduce the learned distance.

The two sessions were on different days to prevent spatial learning in one condition from carrying over to the other. There were two interface conditions: Flystick and none. In the Flystick condition, participants used a Flystick2 wand to translate in the X, Y, and Z directions. The interface did not allow rotation. The hat switch on top of the Flystick2 was used to move along the virtual X-Y plane at a maximum speed of 2.0 m/s, while the trigger button was used to fly at a fixed speed of 2.0 m/s. Releasing the trigger button for 2 s allowed gravity to take over, causing the participant to fall to the virtual floor. In the none interface condition, locomotion was not allowed.

In both interface conditions, participants were allowed to move their heads freely, but they were required to keep their feet in the same spot, 192 cm from the front wall of the CAVE (42 cm behind CAVE center), and equidistant from the side walls. This position was chosen in an attempt to maximize the available peripheral information. The virtual floor and the physical floor were co-planar, except when flying, though the virtual floor was larger in extent.

During the learning phase of each trial, distances were presented as a pair of virtual cones, rendered in Fig. 1b, placed at random positions in the virtual world. For depth trials, both virtual cones were placed in front of the participant, the first at a distance of 10-60 cm and the second at a distance of 245-295 cm. The range of possible observed distances was 185-285 cm, with a mean of 235 cm.

For width trials, the virtual cones were also separated by a distance of 185-285 cm, with a mean of 235 cm. The cones were placed at an equal distance to the left and right of the point 342 cm directly in front of the participant's body.

For vertical trials, the cones were also separated by a distance of 185-285 cm, with a mean of 235 cm. The first cone was placed at a distance of between 10 cm and 60 cm from the virtual floor and the second cone was placed at a distance of between 245 cm and 295 cm from the virtual floor. The vertical trials were the only ones in which the cones were not standing upright. In these trials, the tops of the cones pointed parallel to the floor, toward the participant.

During the recall phase, participants reproduced distances with exocentric perceptual matching using physical cones nearly identical to those modeled in the VE. For depth matching, the first cone was placed 105 cm from the tips of the participant's feet. The experimenter placed the second cone immediately beyond the first and slowly moved it away from the participant, until directed by the participant to stop.

For width matching, the first cone was placed 150 cm in front of and 182 cm to the right of the participant. The experimenter placed the second cone directly to the left of the first and slowly moved it leftward, along a path perpendicular to the direction the participant was facing, until directed by the participant to stop.

For vertical matching, the first cone was fixed 330 cm above the floor. The experimenter initially placed the second cone 1 m lower than the first. This avoided the need for a ladder, thus eliminating an obvious distance cue in the physical environment that may have led to biases involving anchoring or relative judgements between trials. The experimenter then moved the cone downward until directed by the participant to stop.

Procedure. When participants first arrived, they were told that they would be making a series of basic distance judgements and shown the physical cones that would be used for the perceptual matching tasks. They were given a brief explanation of how the real-world perceptual matching tasks would be used to recall the observed virtual distances.

In each trial, participants were allowed as much time as desired to learn the distances. Once they alerted the experimenter that they were ready, they moved quickly and quietly to the recall area across the room. Participants directed the experimenter to reproduce the learned distance and then a new trial began.

Before beginning the experimental trials, participants completed three practice trials (depth, width, vertical) in the real world. They were told that the tasks were intended for practice, but that the answers would be recorded. For these trials, as for the experimental trials described below, participants were allowed to view the target cones for as long as they wanted and then they were quickly and quietly led across the room to do a perceptual matching task to recall the previously seen distance.

Next, if participants were completing the Flystick session, they were trained to use the Flystick. This included a brief explanation and a practice scenario in which participants were encouraged to move around in a scene different from the experimental scene until they felt comfortable with the interface.

Next, participants completed nine experimental trials. Each of these took place in the same virtual office scenario, but viewed from a different orientation, chosen at random (without replacement) from a set of nine. There were three each of depth, width, and vertical judgements, presented in a random order. In the Flystick session, participants were instructed that they could explore as much as they wanted, but that they must also look at each cone up close.

After finishing all trials, participants were asked to complete a post-questionnaire regarding their experiences and problems when estimating the distances. They were also asked to self-report their locomotion performance for the Flystick session. Additionally, after the first session, participants completed a demographic questionnaire with questions about age, sex, height, VR experience, video game experience, and how many hours they exercised per week.

Results: Distance Estimation Error

The following preparations were made before analysis:

-Because the top cone in the vertical matching task was 330 cm from the floor and because the cones were 14 cm wide, the largest distance that could be recalled was 323 cm. For this reason, all measurements were clipped at a maximum of 323 cm. Likewise, because 323 cm is 88 cm greater than the mean cone distance of 235 cm, very low estimates were clipped at an equal distance from the mean cone distance, 147 cm. This prevented depth and width judgements from being larger than those possible for vertical judgements. This only affected four low and four high judgements. -The raw distance estimates were converted to percent error estimates, reflecting the percent of under-or over-estimation in a trial.

A two-factor linear mixed-effects model was constructed with percent error as a response, fixed effects for interface and direction combinations (6 means), a random effect for participant, and a by-participant random slope for direction. An ANOVA using the Satterthwaite approximation for degrees of freedom showed a significant interaction between interface and direction, F (2, 176.81) = 3.13, p = .046. The least-squares means are plotted in Fig. 2a. We were also interested in the question of whether distances were underestimated for each direction and interface. These means were compared to zero using planned t tests. This showed that vertical error was significantly less than 0 (underestimation), t(11.0) = -2.32, p = .04, while depth and width error were not significantly different than 0. Estimates in the none interface condition were less than 0, with marginal significance, t(12.8) = -1.94, p = .07. All means were compared using t tests with the Bonferroni correction for multiple comparisons, showing no additional significant differences.

When using the Flystick interface, participants were able to position themselves such that depth and width judgements may have been analogous. Additionally, there was no statistical difference between the depth and width judgements in either interface condition. Therefore, another analysis was conducted with the depth and width levels pooled into a single horizontal level. A two-factor linear mixed-effects model was constructed with percent error as a response, fixed effects for interface and direction combinations (4 means), a random effect for participant, and a by-participant random slope for direction. An ANOVA using the Satterthwaite approximation for degrees of freedom showed marginally significant main effects of both direction F (1, 11.0) = 4.48, p = .058, and interface, F (1, 189.82) = 3.07, p = .08. The least-squares means are plotted in Fig. 2b, showing that vertical error means are less than those for horizontal error. We can also see that the Flystick may have helped participants make better judgements.

Results: Experimenter Observations and Self-reported Strategies

One question on each post-questionnaire was a Likert scale, regarding perceived performance. The Kruskal-Wallis rank sum test revealed no significant difference in perceived performance between interfaces.

One participant reported problems because virtual objects seemed smaller than physical objects. This may correspond to typical distance underestimation problems in VR.

The experimenter noticed a common strategy when participants used the Flystick interface. Participants often intentionally positioned at least one cone at a physical edge of the CAVE or both cones in the corner between the walls, seemingly as a strategy to help with distance estimation. This was not reported in questionnaire responses. However, participants did comment on difficulty when the distance spans required the use of two physical screens. This problem was reported for both width and vertical judgements. This strategy may reflect attempts to use physical cues when learning the distances.

One participant noted that perceived distances were dependent on point of view, and another reported specifically that objects that were farther away appeared to be a different size when viewed up close. Another participant noted that judgements were easier when using the Flystick interface. This may be because it allows for changing the point of view or because it allows participants to position cones such that they are both on the same physical screen.

One participant reported using the number of imagined footsteps as a metric by which to remember distances. This may be considered a hybrid strategy, as the length of a footstep has meaning in both the virtual and physical environments. This same participant reported trouble on vertical estimates, because they were not easily estimable using this metric, and another stated that she did not know her own virtual height.

Discussion

Statistically, horizontal estimates were veridical. However, there was underestimation of analogous vertical spans that has not been previously explored in the literature. Note that this is not what would be predicted according to distance estimation literature in the real world, which has shown vertical distances to be overestimated relative to horizontal distances. Because estimates were actually more accurate (though not significantly so) with the Flystick interface, these results fail to support the notion that less-effortful locomotion causes underestimation of distances. However, these results do indicate that the ability to interact improves distance estimates.

While many results were not statistically significant, the patterns shown above and the subjective observations were used to motivate the next study. From the patterns we can see that the Flystick interface may have helped participants make more accurate judgements. In line with experimenter observations, this may be a result of different strategies in which the physical system boundaries are used when a participant is able to maneuver accordingly.

Study 2: The Role of CAVE Boundaries in Distance Estimation

We conducted a second study to further investigate the use of information from the physical environment when judging virtual distances. We hypothesized that distance judgements on the plane of the physical floor or walls of the CAVE would be more accurate than those in purely virtual space.

Method

The design and paradigm used in Study 2 closely resembled those in Study 1.

Participants. Fourteen participants (7 female, M = 22.6 years, SD = 3.9 years) were recruited through word of mouth. Participant requirements were the same as in Study 1. There was no compensation for participating.

Apparatus. As in Study 1, participants learned distances in the CAVE and recalled them in the same room, from a position with their backs to the CAVE.

Stimuli and Design. The study employed a 3 (physical position) × 2 (judgement direction) within-subjects design. Two judgement directions (width, vertical) were each experienced six times per session, in alternating order with the starting direction counterbalanced, such that each participant completed 12 trials. As in Study 1, each trial comprised two phases: learning and recall. The learning phase for all trials took place in the same virtual office scene used in Study 1, but each trial with a given judgement direction was observed from a different orientation, randomly chosen from a set of six possible. In the recall phase, exocentric perceptual matching was used to reproduce the learned distance. There were three physical position conditions, as shown in Fig. 3: back, middle, and front. In all three conditions, participants were allowed to move their heads freely, but they were required to keep their feet in the same spot, with an equal distance from each side wall. The virtual floor and the physical floor were co-planar, though the virtual floor was larger in extent. In the middle position, participants stood 187 cm from the front CAVE wall. During the learning phase, distance spans were displayed at the front CAVE wall. In the back condition, participants stood 50 cm behind the middle position, 237 cm from the front CAVE wall. During the learning phase, distance spans were displayed 50 cm in front of the front CAVE wall, on the physical floor (for width judgements) or right wall (for vertical judgements) of the CAVE.

In the front condition, participants stood 50 cm in front of the middle position, 137 cm from the front CAVE wall. During the learning phase, distance spans were displayed 50 cm past the front CAVE wall.

During the learning phase of each trial, participants viewed a pair of randomly positioned virtual cones, as in Study 1, though with a slightly improved cone model. The distances in Study 2 were slightly shorter than those in Study 1, because it was necessary to fit the cones for the vertical trials on the physical screen, which is 267 cm tall.

For width trials, the virtual cones were separated by a distance ranging from 167 cm to 267 cm, with a mean of 217 cm. The first cone was randomly placed at a position between 0 and 50 cm from the plane formed by the left CAVE wall. The second cone was randomly placed between 217 cm and 267 cm from the plane formed by the left CAVE wall.

For vertical trials, the cones were also separated by a distance ranging from 167 cm to 267 cm, with a mean of 217 cm. The first cone was placed at a distance of between 0 cm and 50 cm from the virtual floor and the second cone was placed at a distance of between 217 cm and 267 cm from the virtual floor, both on the plane formed by the right CAVE wall. As in Study 1, the cones did not stand upright in the vertical trials. Instead, the tops of the cones pointed parallel to the floor, toward the participant.

Width matching in the recall phase was identical to that in Study 1, except that the distance specifications were slightly modified. The first cone was placed 150 cm in front of and 168 cm to the right of the participant, a modification intended to expedite distance measurement between trials. The vertical-matching configuration was identical to that in Study 1.

Procedure. The procedure in Study 2 was very similar to that in Study 1, with the following differences.

Before beginning the experimental trials, participants completed only two practice trials (width, vertical) in the real world. These were counterbalanced in the same order as the experimental trials (i.e. if the first experimental trial was to be the width condition, the first practice trial was the width condition).

Participants completed 12 experimental trials. Each of these took place in the same virtual office scenario that was used in Study 1, but viewed from six different orientations chosen at random, such that there were no replacements for trials of a given judgement direction. There were six vertical and six width judgements, interleaved, with the starting direction counterbalanced.

After finishing all trials, participants were asked to complete a post-questionnaire regarding their experiences and problems when estimating the distances and a demographic questionnaire with questions about age, sex, height, VR experience, video game experience, and how many hours they exercised per week. Both questionnaires were slightly modified from Study 1, to more thoroughly investigate problems encountered and strategies employed by the participants.

Results: Distance Estimation Error

Because the mean actual distance was different, as described above, it was not necessary to clamp raw distance estimates as in Study 1. Two distance estimates were missing, due to experimenter error. As in Study 1, raw distance estimates were converted to percent error before analysis.

A two-factor linear mixed-effects model was constructed with percent error as a response, fixed effects for position and direction combinations (6 means), a random effect for participant, and a by-participant random slope for direction. An ANOVA using the Satterthwaite approximation for degrees of freedom showed main effects of both position, F (2, 134.22) = 12.23, p < .01, and direction, F (1, 13.08) = 6.19, p = .03. The least-squares means are plotted in Fig. 4.

Planned comparisons were performed for each of the three pairs of positions in the model. Significant differences were found between the middle and back positions, t(134.4) = 3.5, p < .01, as well as between the middle and front positions, t(133.9) = 4.77, p < .01. Post-hoc comparisons were performed on the model, comparing all eleven means (three positions, two directions, six position-direction combinations) to 0, with the Bonferroni correction for multiple comparisons. As shown in Table 1, all were significant except the width-Middle position mean. Questionnaire responses provided insight into strategies employed and problems encountered during the trials. Interestingly, considering the performance results above in Sec. 3.2, no participants made any mention of using cues from the physical environment to help with distance estimation. However, many participants did report using virtual cues, including furniture and windows. Additionally, participants reported using cues that might be thought of as hybrid, in that they can be thought to exist in the physical world and the virtual world depending on the level of presence. Specifically, participants reported judging horizontal distance in terms of the number of steps required to travel between the cones and judging vertical distances relative to their heights.

Discussion

As in Study 1, there appears to be a difference between horizontal and vertical distances, with vertical distances being underestimated more so than horizontal distances. Note, however, that this study did show some underestimation of horizontal spans, a finding that does not mirror those in Study 1. Significant differences between positions reflect better performance when cones were positioned along the CAVE corners than when cones were behind the physical screen or co-planar with a single physical wall. This indicates that users were able to make use of information from the physical environment to aid in distance estimation, and this helped equally on the vertical and horizontal judgements. However, in contrast with our hypothesis, this only happened when cones were placed at the intersection of two CAVE walls, and not when cones were placed on a single wall or the floor.

General Discussion and Conclusions

We have presented the results of two studies. Together they represent an investigation into the design space for virtual architecture systems. Past studies on underestimation of virtual distances have often neglected to include vertical spans. Additionally, past research has rarely been conducted in a CAVE, which limits the extent to which findings can be applied to the virtual architecture domain.

Both studies incorporated a slightly different perceptual matching paradigm from that used in previous work. While this should allow for more direct estimates of the distance spans, it may also lead to systematic bias. The pattern of differences within a given judgement direction should still be reliable, but future work should consider possible bias particularly as it may limit the ability to measure differences between width and vertical judgements, for example.

Study 1 results indicate that vertical distances are underestimated in a CAVE. This is seemingly in contrast to findings in the real world, which show an overestimation relative to horizontal spans. Note, however, that the paradigm used here is somewhat different. Past real-world findings involved relative distances, while this study was not designed to force any sort of comparison between horizontal and vertical spans. Observations and performance patterns also indicated that participants attempted to use the physical CAVE boundaries when learning distances. This motivated Study 2.

Study 2 results indicate that users can use distance cues in the physical system to help with virtual distance estimates. Surprisingly, performance improved only when the spans were along the highly-salient CAVE corners, and not simply on a CAVE surface.

These analyses indicate that users know where the physical projection surfaces are, and these studies were interpreted under the assumption that users had a low level of subjective presence in the virtual environment. It is likely, given the above conclusions above, that increased virtual presence will cause users to neglect the physical cues in favor of purely virtual judgements. This should be explored in future work. Additionally, the CAVE used in these studies is a cube shape, with right angles and easily inferred boundaries. With a different configuration, such as a curved screen, it is likely that users will not attempt to use physical cues or that they will use them ineffectively.

  (a) Virtual office environment. (b) Virtual cone.

Fig. 1 :

 1 Fig. 1: Virtual models used during the learning phase of the experimental trials.

  Horizontal direction levels pooled.

Fig. 2 :

 2 Fig. 2: Least-squares mean estimation error ± SE in Study 1 as a function of interface and direction.

Fig. 3 :

 3 Fig. 3: Top-down diagram of the CAVE, showing the three physical participant positions together with the corresponding virtual cone positions.

Fig. 4 :

 4 Fig. 4: Least-squares mean estimation error ± SE in Study 2, as a function of position and direction.

Table 1 :

 1 Comparisons between means and 0, with Bonferroni correction for multiple comparisons.

	Direction	Position	df	t	p	p < .05
	vertical		13.1	-6.35	< .01	*
	width		22.1	-3.81	.02	*
		back	17.8	-6.10	< .01	*
		middle	17.4	-3.86	.01	*
		front	17.4	-6.91	< .01	*
	vertical	back	34.7	-5.71	< .01	*
	width	back	32.9	-4.23	< .01	*
	vertical	middle	32.9	-4.36	< .01	*
	width	middle	32.9	-1.93	.75
	vertical	front	32.9	-7.13	< .01	*
	width	front	32.9	-4.15	< .01	*
	3.3 Results: Self-reported Strategies

Acknowledgements. This project was funded by FUI in the framework of the Callisto project.