Alexander R T Gepperth
email: alexander.gepperth@ensta.fr

Thomas Hecht

Mandar Gogate
email: mandarvinayakgogate@gmail.com

A generative learning approach to sensor fusion and change detection

We present a system for performing multi-sensor fusion that learns from experience, i.e., from training data and propose that learning methods are the most appropriate approaches to real-world fusion problems, since they are largely model-free and therefore suited for a variety of tasks, even where the underlying processes are not known with sufficient precision, or are too complex to treat analytically. In order to back our claim, we apply the system to simulated fusion tasks which are representative of real-world problems and which exhibit a variety of underlying probabilistic models and noise distributions. To perform a fair comparison, we study two additional ways of performing optimal fusion for these problems: empirical estimation of joint probability distributions and direct analytical calculation using Bayesian inference. We demonstrate that near-optimal fusion can indeed be learned, and that learning is by far the most generic and resource-efficient alternative. In addition, we show that the generative learning approach we use is capable of improving its performance far beyond the Bayesian optimum by detecting and rejecting outliers, and that it is capable to detect systematic changes in the input statistics.

INTRODUCTION

This study is situated in the context of biologically motivated sensor fusion (often also denoted multi-sensory or multi-modal integration). This function is a necessity for any biological organism, and it seems that, under certain conditions, humans and other animals can perform statistically optimal multi-sensory fusion [START_REF] Marc | Humans integrate visual and haptic information in a statistically optimal fashion[END_REF]. As to how this is achieved, many questions remain: mainly, one can speculate whether there is a generic, sensor-independent fusion mechanism, operating on probability distributions and taking into account the basic statistical laws such as Bayes rule at some neural level, or whether optimal fusion, where it occurs, is something that is fully learned through experience.

In this article, we investigate the matter by comparing several feasible possibilities for implementing multi-sensor fusion in embodied agents, namely generative learning, inference based on estimated joint probabilities, and model-based Bayesian inference. The first method is purely learning-driven, knowing nothing of Bayes' law and using adaptive methods both for representing data statistics and inference, whereas the second estimates joint probability statistics from data but uses Bayes' law for inference. The third method is not adaptive at all but uses models (which have to be known beforehand) of the data generation process, based on which it performs Bayesian inference. To perform this comparison in a meaningful way, allowing each approach to play its strengths, we consider two very different simulated fusion tasks: on the one hand the "standard model" of multi-sensor fusion, where two physical sensor readings are modeled by a single underlying "true" value that is corrupted by (not necessarily Gaussian) noise, and on the other hand a more realistic process modeling, e.g., the estimation of depth measurements in which one sensor reading depends non-linearly upon the "true" value and the other reading(s). Testing all three approaches on the same fusion tasks allows a meaningful quantitative comparison, giving indisputable results.

Overview of biological literature

The multisensory processes going on in mammalian brains are implied in maximizing information gathering and reliability by the effective use of a set of available observations from different sensors [START_REF] Angelaki | Multisensory integration: psychophysics, neurophysiology, and computation[END_REF]. Multi-sensory fusion aims at providing a robust and unified representation of the environment through multiple modalities or features [START_REF] Ernst | Merging the senses into a robust percept[END_REF]. This sensory synergy provides speed in physiological reactions [START_REF] Michael | See me, hear me, touch me: multisensory integration in lateral occipital-temporal cortex[END_REF], accuracy in detection tasks, adaptability in decision making and robustness in common abstract representations. It also allows to distinguish relevant stimuli from each other, which permits quick behavioural and cognitive responses. Hence, it helps avoiding saturation and infobesity traps in tasks like motion orientation towards auditory signal source or focusing visual attention for object recognition.

Multi-sensory fusion has been widely studied at different levels (i.e. from particular cortical cells to individual psycho-physiological behaviour) and into different scientific fields (e.g. neurophysiology, neuroimagery, psychophysiology or neurobiology). Several works in neuroscience have already described multi-sensory fusion in individual neurons [START_REF] Stein | Multisensory integration: current issues from the perspective of the single neuron[END_REF] or in various cortical areas [START_REF] Driver | Multisensory interplay reveals crossmodal influences on sensory-specificbrain regions, neural responses, and judgments[END_REF]. Since the 1960's it has been demonstrated that multi-sensory fusion is carried out hierarchically, layer after layer, within cortical areas containing cells which respond to signals from multiple modalities [START_REF] Mark | The development of multisensory processes[END_REF][START_REF] Calvert | Multisensory integration: methodological approaches and emerging principles in the human brain[END_REF]. Regarding the superior colliculus (SC), a mid-brain structure that controls changes in orientation and attention focusing towards points of interest [START_REF] Ghazanfar | Is neocortex essentially multisensory?[END_REF], Multisensory enhancement (MSE) refers to a situation in which a cross-modal stimulus (i.e. from two or more sensory modalities) provokes a response greater than the response to the most effective of its component stimuli [START_REF] Stein | Multisensory integration: current issues from the perspective of the single neuron[END_REF]: this effect increases as the cues strength decreases (inverse effectiveness rule). Multisensory depression (MSD) hints at the opposite phenomenon [START_REF] Stein | Multisensory integration: current issues from the perspective of the single neuron[END_REF]. In psychology, following the idea of a certain harmony across senses [START_REF] Stratton | Vision without inversion of the retinal image[END_REF], several well-known experiments have underlined multi-sensory fusion causing so-called "multi-sensory illusions" like the ventriloquism effect [START_REF] Howard | Human spatial orientation[END_REF], the McGurk effect [START_REF] Mcgurk | Hearing lips and seeing voices[END_REF], the rubber-hand illusion [START_REF] Botvinick | Rubber hands' feel'touch that eyes see[END_REF] or the sound-induced flash illusion [START_REF] Shams | What you see is what you hear[END_REF].

SOM

It stands to reason that multi-sensory fusion in biological systems is not generally innate but learned [START_REF] King | Development of multisensory spatial integration[END_REF][START_REF] Gori | Young children do not integrate visual and haptic form information[END_REF]. Thus not only the question of how multi-sensory fusion is carried out is of importance, but also of how it is acquired and how it can be adapted if the statistics of the environment change.

Goals of the study

This study aims at providing a purely computational perspective on which multisensory fusion strategy might be most appropriate to implement in future artificial cognitive agents. Criteria we use are precision, generality, outlier detection capacity and resource efficiency, the last point being important because resources are usually severely limited in artificial cognitive agents. Lastly, we wish to show that learning approaches offer ways to improve fusion performance beyond the limit imposed by Bayes' law: this seeming paradox can be resolved when accepting to process only those samples which are particularly suited for fusion, based on simple criteria made available by learning approaches. In this "super-Bayesian fusion" setting one may trade reaction speed for precision, where it depends on the frequency of incoming samples which compromises can be made.

Approach

We use a combined generative-discriminative learning approach, see Fig. 1, to address the proposed fusion problem. It is conceptually similar to several of our previous works in multi-sensory fusion [START_REF] Hecht | A generative-discriminative learning model for noisy information fusion[END_REF], incremental learning [START_REF] Gepperth | Biologically inspired incremental learning for high-dimensional spaces[END_REF][START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF][START_REF] Gepperth | Resource-efficient incremental learning in high dimensions[END_REF] and developmental learning [START_REF] Lefort | Active learning of local predictable representations with artificial curiosity[END_REF][START_REF] Gepperth | Efficient online bootstrapping of representations[END_REF]. In the light of the evaluation criteria for multi-sensory fusion approaches proposed in Sec. 1.2, it is in particular the aspect of outlier detection that motivates the use of generative algorithms. Generative algorithms do no simply model a decision boundary, e.g., for separating two classes, but attempt, in various ways, to model the entire distribution of data samples in input space. This will involve, in general, a more substantial effort, which however pays off when the objective goes beyond separating classes, as it is the case here.

As the essential building block implementing the generative part of our model, we chose a modified version of the self-organizing map (SOM) algorithm [START_REF] Kohonen | Essentials of the self-organizing map[END_REF]. This is a prototype-based generative algorithm which therefore permits the detection of outliers and changes in input statistics. Apart from approximating the distribution of input samples by prototype vectors, it implements a topology-preserving mapping of the computed prototypes, which is of no direct concern here, but will become extremely important when incremental learning is concerned [START_REF] Gepperth | A bio-inspired incremental learning architecture for applied perceptual problems[END_REF][START_REF] Gepperth | Biologically inspired incremental learning for high-dimensional spaces[END_REF]. As incremental learning is the logical next step following successful change detection, we feel that the use of the SOM model is very well justified in this case.

Related work

Multi-sensory fusion can be modeled in various ways, the most relevant ones being selforganized learning and Bayesian inference. The former regroups a set of bio-inspired, unsupervised learning algorithms while the latter argues that mammals can combine sensory cues in a statistically optimal manner.

Self-organizing topology-oriented algorithms and multimodal fusion

Among artificial neural networks, self-organizing maps (SOMs) perform clustering while preserving topological properties of the input space. Studies applying SOMs to multimodal fusion are usually focused on reproducing properties one can find in biology: continuous unsupervised processes, adaptation and plasticity, topological preservation of the input space relationship, or dimensionality reduction. Self-organized approaches have the potential to establish a transition from high-dimensional, noisy and modalityspecific sensor readings to abstract, multimodal and symbolic concepts, whereas they are considered less appropriate for reproducing statistical optimality which should be respected by any fusion process.

Most SOM-based approaches imitate, more or less closely, the hierarchical and layered structure of cortical areas, especially the superior colliculus (SC). In [START_REF] Martin | Modeling multisensory enhancement with self-organizing maps[END_REF] the authors use one basic non-layered self-organizing map to simulate biological MSE and inverse effectiveness from artificial combinations of sensory input cues with Gaussian neighborhood and Manhattan distance. Even though their data are low-dimensional and non-realistic, the authors confirm that the (nearly) original SOM algorithm can lead to meaningful multisensory cue combination. As in [START_REF] Anastasio | A two-stage unsupervised learning algorithm reproduces multisensory enhancement in a neural network model of the corticotectal system[END_REF], they emphasize the positive impact of a non-linear transfer function applied to map outputs (in these cases, a sigmoid function). [START_REF] Pavlou | Simulating the effects of cortical feedback in the superior colliculus with topographic maps[END_REF] design a SOM-like feed-forward layered architecture which uses Hebbian learning to associate maps. The study shows how uni-sensory maps can be aligned by a system that learns coordinate transformations, and automatically integrated into a multisensory representation, i.e. a third map. It focuses on comparing simulated and biological responses to spatially coincident or non-coincident stimuli and achieves the reproduction of simplistic MSE and MSD effects. [START_REF] Mayor | A neurocomputational account of taxonomic responding and fast mapping in early word learning[END_REF] models the learning of words and objects relations by young children from a psychological point of view using two unimodal SOMs. Hebbian learning is used to model the mapping between unimodal spaces so that the presentation of an object activates the correct corresponding word and vice versa. [START_REF] Bauer | A som-based model for multisensory integration in the superior colliculus[END_REF] also deals with imitating SC multi-sensory fusion. The study designs a SOM-based model which is task-oriented and aims at autonomously finding a way to reach a specific goal (in this case object localization). The model tries to characterize the reliability of sensory modalities when dealing with noisy artificial stimuli. Using a single SOM, it uses a custom distance function that measures the likelihood of one input vector to be a noisy version of a known prototype. To this effect, the original Kohonen algorithm is adapted so that the metric takes into account the estimation of each sensor modality's reliability. Nevertheless, noise for different modalities is assumed to independent and normally distributed, and the analogy with the superior colliculus is rather superficial.

Finally, several studies aim at designing models inspired by recent neurophysiological findings without fully copying biological architectures or processes, focusing on well-defined applications. Following [START_REF] Georgakis | An ensemble of SOM networks for document organization and retrieval[END_REF], [START_REF] Baruque | A bio-inspired fusion method for data visualization[END_REF] proposes a learning algorithm based on a variant of the original SOM, ViSOM [START_REF] Yin | ViSOM-a novel method for multivariate data projection and structure visualization[END_REF], which forces the inter-unit distances in a map to be proportional to those in the input space. As for multi-expert techniques in supervised learning [START_REF] Baruque | A bio-inspired fusion method for data visualization[END_REF], a single final map is learned that takes into account multiple SOMs. Each unit of the final map corresponds to a fusion by Euclidean distance, and a voting process is performed on neurons at the same position of the grid in each unimodal SOM. Although the model does not really focus on bio-plausibility and prefers enhancing topology preservation and data visualization properties, it is remarkable that it allows autonomous artificial concentration on interesting features in each of the unimodal SOMs. [START_REF] Jantvik | A self-organized artificial neural network architecture for sensory integration with applications to letter-phoneme integration[END_REF] is one of the most ambitious works using self-organized ANNs for multi-sensory fusion without only reproducing known biological phenomena. With a hierarchical lattice of SOMs (two unimodal maps integrated in a multimodal map), they confirm abilities of SOMs and feedforward connections in integrating unimodal artificial percepts into multimodal unified representations, as [START_REF] Gliozzi | The impact of labels on visual categorisation: A neural network model[END_REF] already did. This study above all puts forward the effective role of feedback connections in artificial attentional mechanisms: without feedback, hierchical SOM networks might only achieve multi-sensory fusion for elementary artificial stimuli. They apply their (strongly finetuned) model to produce bimodal fusion of phonemes and letters but do not provide a clear task-oriented (e.g. speech recognition) evaluation.

Bayesian inference as a model of multi-sensory fusion

Several psychophysiological studies have shown that mammalian brains, and in particular humans ones, fuse multiple sensory signals in an statistically optimal way by a weighted linear combination of estimates of the individual measurements [START_REF] Angelaki | Multisensory integration: psychophysics, neurophysiology, and computation[END_REF]. The intrinsic uncertainty of sensory cues make them more or less reliable and this has to be taken into account by the fusion process [START_REF] Landy | Ideal-observer models of cue integration[END_REF]. Most of the time, these observations are conducted using animals at a behavioural level. However, probabilistic inference in neural circuits is still not well understood. Among fusion methods relying on probability distributions or density functions to express data uncertainty, Bayesian fusion is one of the best-known techniques and is known for having strong links to biological multisensory fusion [START_REF] Knill | The bayesian brain: the role of uncertainty in neural coding and computation[END_REF]. It consists of weighting each sense according to its known variance by applying maximum likelihood estimator (MLE) or maximum a posteriori (MAP) techniques. A couple of assumptions are usually made when performing optimal fusion according to Bayesian statistics [START_REF] Jacobs | Optimal integration of texture and motion cues to depth[END_REF][START_REF] Battaglia | Bayesian integration of visual and auditory signals for spatial localization[END_REF][START_REF] Ernst | A bayesian view on multimodal cue integration[END_REF][START_REF] Hannah | Optimal integration of shape information from vision and touch[END_REF][START_REF] Makkook | A reliability guided sensor fusion model for optimal weighting in multimodal systems[END_REF][START_REF] Song | Bayesian fusion of laser and vision for multiple people detection and tracking[END_REF][START_REF] Klingbeil | Multi-modal sensor data and information fusion for localization in indoor environments[END_REF], namely the assumption of Gaussian noise that is applied independently to each sense, and the assumption of known variances. These assumptions, while acceptable on a theoretical level, prevent the use of such techniques in domains such as developmental learning since evidently neither the variances nor the theoretical distribution and independence properties of signals should be known in advance.

METHODS

In this section, we will give all necessary details of the used learning approach (Sec.2.4), Bayesian inference based on estimated joint probabilities (Sec. 2.2) and model-based Bayesian inference (Sec. 2.3). In all cases, the setting is identical: a single "true" value r and two noisy sensor readings s 1 and s 2 . The way of obtaining s 1 and s 2 from r depends on the particular problem that is treated, as do the noise distributions that additionally perturb the sensor readings.

Fusion problems

Two fusion problems are considered in this study, in both of which the goal is to infer the true value r from noisy sensor readings s 1 , s 2 . Several types of noise ˜ (σ) are considered for corrupting sensor readings (Gaussian, uniform, triangular), all of which have a single parameter σ that models their "strength". In the case of Gaussian noise, σ would correspond to the standard deviation, for uniform and triangle noise it is the half-width of the interval with nonzero probability. For every noise type in both problems, we vary the parameter σ in order to determine how this impacts fusion accuracy. The probability density functions for all three (additive) noise types are as follows (see also Fig. 2):

p gauss (x, σ) = 1 √ 2πσ 2 exp - x 2 2σ 2 (1)
p uni (x, σ) = 1 2σ if x ∈ [-σ, σ] 0 else p tri (x, σ)    x+σ 1.1σ 2 iff x ∈ [-σ, 0.1σ] σ-x 0.9σ 2 iff x ∈ [0.1σ, σ] 0 else
Problem I This first "family" of problems follows the "classic" Bayesian framework: a single "true" value r that gives rise to several noisy sensor readings s i . We suppose that the sensor readings s i are obtained from an unique r value by adding independent, parametrized noise ˜ (σ).

r ∼ p uni a,b (x) s i = r + ˜ (σ)
Fig. 2 Probability density functions for the three parametrized noise types used in this article: Gaussian, uniform and triangular. For all curves, a parameter value of σ = 0.5 has been used. Please remark that the triangle distribution is not centered on 0, but on 0.05 which corresponds to 10% of the parameter σ. With larger σ, triangular noise will therefore not only introduce significant noise but also systematic bias.

Problem II A more realistic setting is where the sensory readings s i and the underlying true value r are more tightly coupled. In this second problem family, we suppose that the s i are no longer class-conditionally independent and depend on r as well as each other. In other words, all of the s i have to be considered simultaneously for inferring r. Formally, we express this by drawing r independently from a bounded uniform distribution, and then making s2 a deterministic function of r and s1 : s2 = f (s 1 , r). Afterwards, the si are subjected to additive Gaussian noise in order to produce the real sensor values s i :

r ∼ p uni a,b (x) s1 ∼ p uni a,b (x) s2 = f (s 1 , r) s i = si + ˜ (σ)

Bayesian inference based on estimated joint probabilities

The basic idea of this approach is to empirically estimate the conditional probability distribution p(r|s 1 s 2 ) during a training phase where r is available with each sample, and to perform Bayesian inference using this conditional probability distribution in the subsequent evaluation phase where r is not available. First of all, it is straightforward to see that the maximum of p(r|s 1 s 2 ) w.r.t. r is equivalent to the maximum of the joint probability p(rs 1 s 2 ), so it is sufficient to estimate this quantity. In order to estimate joint probabilities in practice, all variables must be discretized to n bins using an invertible function bµ,n(x) → i ∈ N, where obviously a finer discretization implies higher precision but also higher memory and execution time demands. For variables in the [0, 1] interval, we chose b such that it pads the encoded scalar value with borders of width µ, which is necessary because random variables might fall outside the [0, 1] interval depending on noise, and still need to be represented properly:

b ≡ bµ,n(x) = floor (n -(µ + (1 -2µ)x) (2) b -1 ≡ b -1 µ,n (i) = i n -µ 1 -2µ (3)
For three discretized variables, the estimated joint probability matrix pijk has n 3 entries and requires roughly n 3 samples to be filled properly. During training, samples (r, s 1 , s 2 ) are received on by one, and for each sample the matrix is updated as follows:

p ijk (0) ≡ 0 p b(r)b(s1)b(s2) (t + 1) = p b(r)b(s1)b(s2) (t) + 1 (4)
At the end of the training phase, p ijk is normalized to have a sum of 1. When performing inference during the evaluation phase, only the two sensor readings s 1 and s 2 are available, and the task to infer the underlying value r * that best matches s 1 and s 2 amounts to finding the matrix bin i * for which r has the highest estimated probability:

i * = max i p i b(s1) b(s2) r * = b -1 (i * ) (5)

Model-based Bayesian inference

Similar in spirit to the preceding section, model-based Bayesian inference aims to find the most probable value of r given the observations s 1 and s 2 :

r * = arg max r p(r|s 1 s 2 ) ∼ arg max r p(s 1 s 2 |r)p(r) (6)
This amounts to a maximization problem: Evidently, eqn.(8) needs to be solved both for problem I and II separately, and in general this approach requires that the data generation model be known. So, we present two different solutions for problem I and problem II. In general, this approach is a complex one, and the necessary analytical derivations need to be performed before testing it. Any change in input statistics requires a repetition of these derivations, where the form of the new statistics must be analytically.

Problem I

Corrupting a clean variable like r, here supposed deterministic so its distribution is p(x|r) = δ(x -r), by additive noise drawn from one of the distributions p noise (x, σ) given in eqn. [START_REF] Marc | Humans integrate visual and haptic information in a statistically optimal fashion[END_REF], implies the convolution of the probability densities of clean and noise variables from which the resulting noisy variables are effectively drawn. The result of the convolution is thus the conditional distribution p(s i |r) of the form:

p(s i |r) = p noise (s i -r, σ) (9)
For making the link to eqn.( 8), we observe that the p(s i |r) are class-conditionally independent, and we can thus express their joint probability p(s 1 s 2 |r) by the product of individual probabilities:

p(s 1 s 2 |r) = p(s 1 |r)p(s 2 |r) (10)
This leads to the following estimates for the underlying value r:

r * gauss = i 1/σ 2 i j 1/σ 2 j s i (11)
r * uni ∼ p uni A,B (12)
where

[A, B] = [s 1 -σ 1 , s 1 + σ 1 ] ∩ [s 2 -σ 2 , s 2 + σ 2 ].
For triangle noise, an analytical treatment is difficult and is therefore omitted from these considerations.

Problem II The only tricky point consists here in computing the quantity p(s 1 s 2 |r) required by eqn. [START_REF] Mark | The development of multisensory processes[END_REF], which remains valid as p(r) is still uniformly distributed. Still, the calculation is a little more cumbersome since the factorization p(s 1 s 2 |r) = Π i p(s i |r) no longer holds:

p(s 1 s 2 |r) = ds 1 ds 2 p(s 1 s 2 |s 1 s2 r)p(s 1 s2 |r) = ds 1 ds 2 p(s 1 s 2 |s 1 s2 )p(s 1 s2 |r) = ds 1 ds 2 p(s 1 |s 1 )p(s 2 |s 2 )δ(f (r, s1 ) -s2 ) = ds 1 p(s 1 |s 1 )p(s 2 |f (s 1 , r)) (13)
where the first transformation follows from the law of total probability: we insert a complete set of disjunct states s1 s2 . In the second line, the factor r has been removed from the conditional probability p(s 1 s 2 |s 1 s2 r) as it can be deduced from s1 and s2 . Later, the conditional probability has been split as s i depends only on si . The optimal fused value of r in the interval [a, b] is obtained as before by maximizing eqn. [START_REF] Calvert | Multisensory integration: methodological approaches and emerging principles in the human brain[END_REF]. As the resulting expression is in general intractable analytically, we resort to numerical methods to solve it for r, which do work well for Gaussian noise but not for other forms of noise due to numerical problems for uniform noise and analytical intractability for triangular noise.

Learning approach

The learning approach is schematically depicted in Fig. 1. It is essentially a three-layer neural network that learns a set of plastic, topologically organized prototypes in its hidden layer. A read-out mechanism between hidden and output layer maps the set of graded prototype activities to output values using simple linear regression learning.

Population encoding

In order to increase the computational power of the employed algorithms (see [START_REF] Gepperth | The contribution of context information: a case study of object recognition in an intelligent car[END_REF]), we adopt a population-coding approach [START_REF] Gepperth | The contribution of context information: a case study of object recognition in an intelligent car[END_REF] where continuous values of the input and target variables (i.e., the noisy sensor readings s 1 , s 2 and r) are represented by placing a Gaussian of variance σp onto a discrete position in an one-dimensional activity vector such that the discrete center position is in a linear relationship with the encoded continuous value. As in Sec. 2.2, this discretization is associated with a loss of precision, thus a sufficiently large size of the activity vector must be chosen. Furthermore, the activity vector must have a sufficiently large margin µ around the interval to be encoded because random variables can fall outside this interval and need to be represented as well. The precise way of encoding a scalar value x ∈ [0, 1] into a vector v of size n is as follows, using :

c = bµ,n(x) (14)
v i = exp - (i -c) 2 2σ 2 p ( 15
)
where we have used the discretizing function b from eqn. [START_REF] Angelaki | Multisensory integration: psychophysics, neurophysiology, and computation[END_REF]. As a final step in population encoding, the vector v is normalized to have an L 2 norm of 1.

Neural learning architecture

The architecture is essentially depicted in Fig. 1 and consists essentially of the layers I, T and E: the input layer I obtained by concatenating two population-coded sensor values, a hidden layer T and a fusion estimate layer E, respectively. In addition, there is a ground-truth layer G that represents the "true" sensor value r.

Generally, we denote neural activity vector in a 2D layer X by z X (y, t), and weight matrices feeding layer X, represented by their line vectors attached to target position y = (a, b), by w X y (t). For reasons of readability, we often skip the dependencies on space and time and include them only where ambiguity would otherwise occur. Thus we write z X instead of z X (y, t) and w X instead of w X y (t). Using this notation, the two weight matrices that are subject to learning in this architecture are the connections from I to T, w SOM and the weights from T to E, w LR .

zT (y) = w SOM y • z I (16)
z T = TFp zT ( 17)

z E = w LR • z T ( 18
)
w LR y (t + 1) = w LR y + 2 LR z I z E (y) -z G (y) ( 19
)
w SOM y (t + 1) = norm w SOM y + SOM gσ(y -y * )(z I -w SOM y ) ( 20
) ( 21
)
where gs(x) is a zero-mean Gaussian function with standard deviation s and y * denotes the position of the best-matching unit (the one with the highest similarity-to-input) in P . In accordance with standard SOM training practices, the SOM learning rate and radius, SOM and σ, are maintained at 0 , σ 0 for t < T 1 and are exponentially decreased afterwards in order to attain their long-term values ∞, σ∞ at t = Tconv. The learning rate of linear regression, LR remains constant during at all times. TFp represents a monotonous non-linear transfer function, TFp : [0, 1] → [0, 1] which we model as follows with the goal of maintaining the BMU value unchanged while non-linearly suppressing smaller values: m = maxy zT (y, t)

TFp (z T (y) = m p-1 z T (y) p (22)

Rejection strategy for super-Bayesian fusion

In this setting, we simply reject an incoming sample, i.e., take no decision, if the simple criterion

max z E > θ (23)
with

θ(t + 1) = (1 -α)θ(t) + α max z E (t). ( 24
)
is fulfilled. Simply put, we check whether the highest activated unit in the output layer E has an activity that is higher than the temporal average of past maximal activities, calculated by exponential smoothing. This is pretty ad hoc and not rigorously justified, but we find that in practice this strategy gives significant performance improvements and in no case that we could observe deteriorates performance.

Novelty detection

As the hidden SOM layer implements a generative model of the sensory input, it should be able to recognize out-of-the-ordinary samples, i.e., outliers. This is particularly important for detecting persistent changes in input statistics, which must be countered by adapting the fusion model. Here, a change detection mechanism could provide, first of all, a means to detect when a model should be adjusted to new realities, and furthermore to stop fusion until this has been successfully done. Such an ability is therefore imperative for life-long learning in embodied agents and should be considered a significant advantage. We approach change detection by simply monitoring the temporal average activity of the best-matching until (BMU) in the hidden SOM layer P. This is done because we assume that the SOM prototypes represent the joint distribution of s 1 and s 2 in input space; any significant deviation from this distribution should therefore result in lower input-prototype similarity which results in lower activity. Again, the temporal average is calculated by exponential smoothing and thus requires no memory overhead. The smoothing constant β has to be set such that short-term random fluctuations are smoothed away whereas long-term systematic changes are retained.

EXPERIMENTS

For all experiments, we use an interval of [0, 1] for r, s 1 and s 2 . Each experiment is repeated 25 times, each time with a different pairing of standard deviations which are chosen for each sensor from the following fixed set: 0.016, 0.032, 0.048, 0.064 and 0.08.

Joint probability estimation parameters

The discretization step size is set to n = 100, and the joint probability matrix is built for n 3 iterations. The margin parameter µ is set to µ = 0.2.

Model-based Bayesian inference parameters

This method is parameter-free in the sense that it only uses the parameters contained in the data generation model. There are a few parameters tied to the numerical solution of integrals but the standard values of the numerical solvers always work well so it is not necessary to include them here.

Learning approach Here, several parameters need to be fixed: the hidden layer contains 15x15=225 units, the output layer has n = 100 units. The margin parameter for population encoding is set to µ = 0.2. The variance of Gaussians for population encoding is fixed at σp = 3 pixels. The LR learning rate is LR = 0.01 and the parameters for decreasing SOM learning rate and radius are: 0 = 0.1, σ 0 = 5, ∞ = 0.01, σ∞ = 0.5, Tconv = 5000, T 1 = 1000. The transfer function parameter p is set to 20. Total training time is always 20.000 iterations unless otherwise mentioned, and testing is conducted subsequently for 20.000 iterations for calculating performance statistics, with learning turned off. The smoothing parameter for super-Bayesian fusion is α = 0.001, and the smoothing parameter for change detection is β = 0.001 as well.

Comparison of fusion performances

In this experiment, we compare the performances of all three fusion methods (Bayesian inference by joint probability estimation, model-based Bayesian inference and our learning approach) for problem I and problem II, each time using three noise types (Gaussian, uniform and triangular noise) as described in detail in Sec. 2.1. For each method, problem and noise type we conduct 25 separate experiments, corresponding to all possible combinations of standard deviations given above. In this way, the behavior of each fusion method is sampled uniformly in a representative range of noise strengths in a way that can be directly compared. , learning approach(black) and learning approach using super-Bayesian fusion(green).

Fig. 4 Comparison of fusion performance under uniform noise for four methods on problem I (left) and problem II (right): Bayesian inference using estimated joint probabilities (red), learning approach(black) and learning approach using super-Bayesian fusion(green). Modelbased Bayesian inference is not practicable for uniform noise and therefore not shown.

Fig. 5 Comparison of fusion performance under triangular noise for four methods on problem I (left) and problem II (right): Bayesian inference using estimated joint probabilities (red), learning approach(black) and learning approach using super-Bayesian fusion(green). Modelbased Bayesian inference is not practicable for triangular noise and therefore not shown. Model-based Bayesian inference runs into problems when using uniform noise because the numerical solution of the involved integrals becomes numerically unstable, requiring interval discretization that render the problem intractable. As for triangular noise, it poses severe problems for the analytical derivation due to its non-diffentiability at x = 0, see Fig. 2. Model-based Bayesian inference is therefore conducted for Gaussian noise only.

We observe from Figs. 3, 4, 5 that fusion performances are always very similar for problem I regardless of noise, probably because this problem is rather simple in nature.

For problem II, apart from an overall decrease in precision, we observe that super-Bayesian fusion always performs best, sometimes by large margins. In the parametrization used here, around 50% of samples were rejected for the latter. The only noticeable deviations for problem II occur for triangular noise, for unknown reasons. As we measure the mean squared error here, however, and not is square root, these differences are less than they appear, and overall we can state that all fusion methods independently obtain very similar results on problem II, too, once more supporting the global consistency of our experiments.

Memory usage is non-existent for model-based Bayesian fusion, negligible for the learning approach and enormous for joint probability estimation, as a matrix of n 3 elements is to be represented for n = 100. In terms of computation speed, model-based Bayesian inference is efficient for training as it does not need to be trained, whereas a training session for the learning approach takes approximately 1 minute and 5 minutes for inference by joint probability estimation. Execution of models is rather similar for all three methods, where around 100 estimations can be performed per second.

Change detection performance

For this experiment, we introduce the concepts of a slight, medium and severe change in input statistics. Working on problems I and II using Gaussian noise, we train the system with noise standard deviations of σ 1 = σ 2 = 0.016, and then change these parameters after the first half of the testing phase, i.e., without retraining the system. We therefore expect a reaction to this change, as described in Sec. 2.4.4. Each change condition differs only in the new values for the standard deviations: σ 1 = σ 2 = 0.032 (slight), σ 1 = σ 2 = 0.048 (medium) and σ 1 = σ 2 = 0.08 (severe). From Figs. 6,7 we can observe that even slight changes can be reliably detected by the system since there is always a significant decease in average BMU activity.

DISCUSSION

When we compare the three fusion methods we investigated in the light of the criteria we put forward in Sec. 1.2, namely precision, generality, change detection capacity and resource-efficiency, we find a mixed picture at fist glance.

All proposed methods are pretty equal in terms of precision, except notably the super-Bayesian fusion by the learning approach, although this is not completely fair as it cannot treat all samples. Still, it should be noted that the Bayesian "optimal" fusion can be surpassed significantly by a rather simple and efficient approach, which can be very useful to any artificial cognitive agent.

In terms of generality, it is clearly the learning approach and Bayesian inference by joint probability estimation that are most generally applicable as they can cope with any problem under any type of noise, which is something that model-based Bayesian inference is incapable of.

Regarding resource efficiency, especially in the light of an application in artificial cognitive agents, it is clearly the learning approach that is most favorable: it has both a favorable execution and training time, and it is very memory-efficient. In fact, by reducing the size of the hidden SOM layer, one can gradually trade memory usage for precision, making use of the graceful decay property of SOMs for this purpose. Bayesian inference by joint probability estimation has the problem of training time and memory usage that grow cubically with the discretization step n, quickly rendering this approach impracticable where high precision is needed. Model-based Bayesian inference is memory and time-efficient as well but is not very suited to artificial agents as it is incapable of adapting.

For change detection capacity, it is the learning approach that wins the competition because it offers a very efficient-to-compute criterion to detect even rather slight changes in input statistics, using only quantities like the BMU score that are calculated anyway and thus do not impose a computational burden.

Based on all these points, we may safely conclude that the two adaptive approaches to multi-sensory fusion are certainly preferable due to their generality and resource efficiency. The learning architecture we presented possesses the additional capacity to perform change detection and super-Bayesian fusion which are very important points in their own right, and it rather more resource-efficient than Bayesian inference by joint probability estimation.

Influence of key parameters on the learning approach

The most crucial parameter for the learning approach is the size of the hidden layer T. Especially for change detection, this needs to be of sufficient size otherwise change detection capability deteriorates significantly. Intuitively, with smaller hidden layers it becomes harder to distinguish whether an input is dissimilar from prototypes because it is an outlier, or because there are simply too few prototypes to properly samples the input space. For this parameter we can say: the bigger the better: we never observed a performance deterioration when increasing hidden layer size, but a minimum of 15x15 seems recommended for this task. Another parameter of great importance is the minimal neighbourhood radius σ∞. If it is set too high, neighbouring prototypes will be too similar to each other. This means that one cannot say with surety, from each prototype's response, where exactly the input is situated, so fusion is less precise. We set it as small as possible while still making a difference. Smaller values are acceptable as well but do not change the behavior any more. A free parameter of moderate influence is the transfer function parameter p = 20. It is important that there be a non-linear stage in the network which is realized by the transfer function TFp, and results get slightly better if p > 10. But results tend to be acceptable even for p > 1. The convergence and initialization times are set w.r.t. the total number of samples according to standard SOM practices. Learning parameters for SOM and linear regression are similarly set w.r.t. the number of training samples.

Summary, conclusion and future work

We have presented a comparison of three methods for perform multi-sensory fusion in a simulated setting that is nevertheless very closely modeled after real tasks. We com-pared these methods in terms of precision, generality, change detection capacity and resource-efficiency, and found that the self-organized neural network was most suited, in summary, for application in artificial cognitive agents, thus making a very strong statement in favor of learning methods in multi-sensory fusion. We furthermore investigated a simple way to improve fusion performance beyond the Bayesian optimum and found it both practicable and beneficial for performance under the condition that one accepts to ignore a certain percentage of incoming samples. As a last, we investigated how fusion might be continuously updated and re-calibrated by detecting significant changes in input statistics, and found that the detection of such changes is feasible and simple for the presented system.

In future work, we wish to investigate the issue of incremental learning for multisensory fusion, meaning that upon the detection of changed input statistics, the learned fusion model should be adapted in a way that allows stable life-long learning. In addition, verifying these algorithms on a real-world fusion task will be an important validation of the presented theoretical work.

Compliance with ethical standards

This article does not contain any studies with human participants or animals performed by any of the authors. Thomas Hecht has received a research grant from the Direction Générale de l'Armement (DGA), France. Alexander Gepperth, Thomas Hecht and Mandar Gogate declare that they have no conflict of interest.

Fig. 1

 1 Fig.1Schematic overview of the learning system for multi-sensory fusion proposed in this study.

∂rp(s 1 s 2 8 )

 28 |r)p(r) = 0 ⇔ ∂r (p(s 1 s 2 |r)) p(r) + p(s 1 s 2 |r)∂sp(r) = 0 (7) Eqn. (7) has trivial solutions outside the interval ]a, b[ where both p(r) and ∂sp(r) vanish. However they minimize p(s 1 s 2 |r)p(r) (inserting an appropriate r always gives a value of 0), and are thus excluded from our considerations. If, however, a solution exists inside [a, b], it must obey the simplified equation ∂s (p(s 1 s 2 |r)) = 0 (On the other hand, if eqn.( 8) has a non-trivial solution outside the interval ]a, b[ then it must be either s = a or s = b, depending on which is closer, because the infinities in the derivatives of p(r) achieve a "clamping" of obtained fusion results to the known interval [a, b].This can be implemented very efficiently, without solving any equations at all, as a post-processing step of fusion.

Fig. 3

 3 Fig.3Comparison of fusion performance under Gaussian noise for four methods on problem I (left) and problem II (right): Bayesian inference using estimated joint probabilities (red), model-based Bayesian inference (blue), learning approach(black) and learning approach using super-Bayesian fusion(green).

Fig. 6

 6 Fig.6Change detection performance of the learning approach, evaluated for problem I. Beginning of the testing phase, with unmodified standard deviations, is marked in grey, whereas the second half of the testing phase where a change of statistics occurs is marked in red. Change conditions are slight (upper left), medium (upper right) and severe (centered).

Fig. 7

 7 Fig. 7 Change detection performance of the learning approach, evaluated for problem II. Beginning of the testing phase, with unmodified standard deviations, is marked in grey, whereas the second half of the testing phase where a change of statistics occurs is marked in red. Change conditions are slight (upper left), medium (upper right) and severe (centered).


Michell Guzmán
email: guzman@lix.polytechnique.fr

Frank D Valencia
email: frank.valencia@lix.polytechnique.fr

On the Expressiveness of Spatial Constraint Systems *

Keywords: 1998 ACM Subject Classification F.4.1 Mathematical Logic Keywords and phrases Epistemic logic, Modal logic, Constraint systems, Concurrent constraint programming. Digital Object Identifier 10.4230/OASIcs.ICLP.2016.16

In this paper we shall report on our progress using spatial constraint system as an abstract representation of modal and epistemic behaviour. First we shall give an introduction as well as the background to our work. Then, we present our preliminary results on the representation of modal behaviour by using spatial constraint systems. Then, we present our ongoing work on the characterization of the epistemic notion of knowledge. Finally, we discuss about the future work of our research.

Introduction

Epistemic, mobile and spatial behaviour are common practice in today's distributed systems.

The intrinsic epistemic nature of these systems arises from social behaviour. Most people are familiar with digital systems where users share their beliefs, opinions and even intentional lies (hoaxes). Also, systems modeling decision behaviour must account for those decisions dependance on the results of interactions with others within some social context. Spatial and mobile behaviour is exhibited by applications and data moving across (possibly nested) spaces defined by, for example, friend circles, groups, and shared folders. We therefore believe that a solid understanding of the notion of space and spatial mobility as well as the flow of epistemic information is relevant in many models of today's distributed systems.

Constraint systems (cs's) provide the basic domains and operations for the semantic foundations of the family of formal declarative models from concurrency theory known as concurrent constraint programming (ccp) process calculi [15]. Spatial constraint systems [START_REF] Knight | Spatial and epistemic modalities in constraint-based process calculi[END_REF] (scs) are algebraic structures that extend cs for reasoning about basic spatial and epistemic behaviour such as extrusion and belief. Both spatial and epistemic assertions can be viewed as specific modalities. Other modalities can be used for assertions about time, knowledge and other concepts used in the specification and verification of concurrent systems.

The main goal of this PhD project is the study of the expressiveness of spatial constraint systems in the broader perspective of modal behaviour. In this summary, we shall show that

Background

In this section we recall the notion of basic constraint system [START_REF] Boer | Nondeterminism and infinite computations in constraint programming[END_REF] and the more recent notion of spatial constraint system [START_REF] Knight | Spatial and epistemic modalities in constraint-based process calculi[END_REF]. We presuppose basic knowledge of order theory and modal logic [START_REF] Abramsky | Domain theory. Handbook of logic in computer science[END_REF]14,[START_REF] Fagin | Reasoning about knowledge[END_REF][START_REF] Blackburn | Modal Logic[END_REF].

The concurrent constraint programming model of computation [15] is parametric in a constraint system (cs) specifying the structure and interdependencies of the partial information that computational agents can ask of and post in a shared store. This information is represented as assertions traditionally referred to as constraints.

Constraint systems can be formalized as complete algebraic lattices [START_REF] Boer | Nondeterminism and infinite computations in constraint programming[END_REF] 1 . The elements of the lattice, the constraints, represent (partial) information. A constraint c can be viewed as an assertion (or a proposition). The lattice order is meant to capture entailment of information: c d, alternatively written d c, means that the assertion d represents as much information as c. Thus, we may think of c d as saying that d entails c or that c can be derived from d. The least upper bound (lub) operator represents join of information; c d, the least element in the underlying lattice above c and d. Thus, c d can be seen as an assertion stating that both c and d hold. The top element represents the lub of all, possibly inconsistent, information, hence it is referred to as false. The bottom element true represents the empty information.

Definition 1 (Constraint Systems [START_REF] Boer | Nondeterminism and infinite computations in constraint programming[END_REF]). A constraint system (cs) C is a complete algebraic lattice (Con, ). The elements of Con are called constraints. The symbols , true and false will represent the least upper bound (lub) operation, the bottom, and the top element of C, respectively.

We shall use the following notions and notations from order theory. Notation 2 (Lattices and Limit Preservation). Let C be a partially ordered set (poset) (Con, ). We shall use S to denote the least upper bound (lub) (or supremum or join) of the elements in S, and S is the greatest lower bound (glb) ( infimum or meet) of the elements in S. We say that C is a complete lattice iff each subset of Con has a supremum and an infimum in Con. A non-empty set S ⊆ Con is directed iff every finite subset of S has an upper bound in S. Also, c ∈ Con is compact iff for any directed subset D of Con, c D implies c d for some d ∈ D. A complete lattice C is said to be algebraic iff for each c ∈ Con, the set of compact elements below it forms a directed set and the lub of this directed set is c. A self-map on Con is a function f : Con → Con. Let (Con, ) be a complete lattice. The self-map f on Con preserves the supremum of a set S ⊆ Con iff f ( S) = {f (c) | c ∈ S}. The preservation of the infimum of a set is defined analogously. We say f preserves finite/infinite suprema iff it preserves the supremum of arbitrary finite/infinite sets. Preservation of finite/infinite infima is defined similarly.

Spatial Constraint Systems

The authors of [START_REF] Knight | Spatial and epistemic modalities in constraint-based process calculi[END_REF] extended the notion of cs to account for distributed and multi-agent scenarios where agents have their own space for their local information and performing their computations.

Intuitively, each agent i has a space function [•] i from constraints to constraints. We can think of [c] i as an assertion stating that c is a piece of information residing within a space attributed to agent i. An alternative epistemic logic interpretation of [c] i is an assertion stating that agent i believes c or that c holds within the space of agent i (but it may not hold elsewhere). Similarly, [[c] j ] i is a hierarchical spatial specification stating that c holds within the local space the agent i attributes to agent j. Nesting of spaces can be of any depth. We can think of a constraint of the form [c] i

[d] j as an assertion specifying that c and d hold within two parallel/neighboring spaces that belong to agents i and j, respectively. Definition 3 (Spatial Constraint System [START_REF] Knight | Spatial and epistemic modalities in constraint-based process calculi[END_REF]). An n-agent spatial constraint system (n-scs) C is a cs (Con, ) equipped with n self-maps

Extrusion and utterance

We can also equip each agent i with an extrusion function ↑ i : Con → Con. Intuitively, within a space context [•] i , the assertion ↑ i c specifies that c must be posted outside of (or extruded from) agent i's space. This is captured by requiring the extrusion axiom

[ ↑ i c ] i = c.
In other words, we view extrusion/utterance as the right inverse of space/belief (and thus space/belief as the left inverse of extrusion/utterance).

Definition 4 (Extrusion). Given an n-scs

(Con, , [•] 1 , . . . , [•] n ), we say that ↑ i is an extrusion function for the space [•] i iff ↑ i is a right inverse of [•] i , i.e., iff [ ↑ i c ] i = c.

The Extrusion/Right Inverse Problem

A legitimate question is: Given space [•] i can we derive an extrusion function ↑ i for it ? From set theory we know that there is an extrusion function (i.e., a right inverse)

↑ i for [•] i iff [•] i is surjective. Recall that the pre-image of y ∈ Y under f : X → Y is the set f -1 (y) = {x ∈ X | y = f (x)}.
Thus, ↑ i can be defined as a function, called choice function, that maps each element c to some element from the pre-image of c under [•] i .

Preliminary Results

In this part of the summary we shall describe the work we have achieved so far. It is based on the paper [START_REF] Guzman | Deriving extrusion on constraint systems from concurrent constraint programming process calculi[END_REF] recently accepted for publication.

I C L P 2 0 1 6 T C s 16:4

On the Expressiveness of Spatial Constraint Systems

Modalities in Terms of Space

Modal logics [14] extend classical logic to include operators expressing modalities. Depending on the intended meaning of the modalities, a particular modal logic can be used to reason about space, knowledge, belief or time, among others. Although the notion of spatial constraint system is intended to give an algebraic account of spatial and epistemic assertions, we shall show that it is sufficiently robust to give an algebraic account of more general modal assertions.

The aim of this part of the summary is the study of the extrusion problem for a meaningful family of scs's that can be used as semantic structures for modal logics. They are called Kripke spatial constraint systems because its elements are Kripke Structures (KS's). KS's can be seen as transition systems with some additional structure on their states.

Constraint Frames and Normal Self Maps

Spatial constraint systems can be used, by building upon ideas from Geometric Logic and Heyting Algebras [16], as semantic structures for modal logic. We shall give an algebraic characterization of the concept of normal modality as maps preserving finite suprema. In modal logics one is often interested in normal modal operators. The formulae of a modal logic are those of propositional logic extended with modal operators. Roughly speaking, a modal logic operator m is normal iff (1) the formula m(φ) is a theorem (i.e., true in all models for the underlying modal language) whenever the formula φ is a theorem, and (2) the implication formula m(φ ⇒ ψ) ⇒ (m(φ) ⇒ m(ψ)) is a theorem. Thus, using Heyting implication, we can express the normality condition in constraint frames as follows.

Definition 6 (Normal Maps). Let (Con, ) be a constraint frame. A self-map m on Con is said to be normal if [START_REF] Abramsky | Domain theory. Handbook of logic in computer science[END_REF]

m(true) = true and (2) m(c → d) → (m(c) → m(d)) = true for each c, d ∈ Con.
The next theorem basically states that Condition (2) in Definition 6 is equivalent to the seemingly simpler condition:

m(c d) = m(c) m(d).
Theorem 7 (Normality & Finite Suprema). Let C be a constraint frame (Con, ) and let f be a self-map on Con. Then f is normal if and only if f preserves finite suprema. By applying the above theorem, we can conclude that space functions from constraint frames are indeed normal self-maps, since they preserve finite suprema.

Extrusion Problem for Kripke Constraint Systems

In this section we will study the extrusion/right inverse problem for a meaningful family of spatial constraint systems (scs's), the Kripke scs. In particular, we shall derive and give a complete characterization of normal extrusion functions as well as identify the weakest condition on the elements of the scs under which extrusion functions may exist. To illustrate the importance of this study, let us give some intuition first.

Kripke structures (KS) are a fundamental mathematical tool in logic and computer science. They can be seen as transition systems and they are used to give semantics to modal logics. Formally, a KS can be defined as follows.

Definition 8 (Kripke Structures

). An n-agent Kripke Structure (KS) M over a set of atomic propositions Φ is a tuple (S, π, R 1 , . . . , R n ) where S is a nonempty set of states, π : S → (Φ → {0, 1}) is an interpretation associating with each state a truth assignment to the primitive propositions in Φ, and R i is a binary relation on S. A pointed KS is a pair (M, s) where M is a KS and s, called the actual world, is a state of M . We write

s i -→ M t to denote (s, t) ∈ R i .
We now define the Kripke scs wrt a set S n (Φ) of pointed KS. Definition 9 (Kripke Spatial Constraint Systems [START_REF] Knight | Spatial and epistemic modalities in constraint-based process calculi[END_REF]). Let S n (Φ) be a non-empty set of n-agent Kripke structures over a set of primitive propositions Φ. We define the Kripke n-scs for S n (Φ) as K(S n (Φ)) = (Con, , [•] 1 , . . . , [•] n ) where Con = P(∆) , = ⊇, and

[c] i def = {(M, s) ∈ ∆ | i (M, s) ⊆ c}
where ∆ is the set of all pointed Kripke structures (M, s) such that M ∈ S n (Φ) and

i (M, s) = {(M, t) | s i -→ M t} denotes the pointed KS reachable from (M, s). The structure K(S n (Φ)) = (Con, , [•] 1 , . . . , [•] n ) is
a complete algebraic lattice given by a powerset ordered by reversed inclusion ⊇. The join is set intersection, the meet is set union, the top element false is the empty set ∅, and bottom true is the set ∆ of all pointed Kripke structures (M, s) with M ∈ S n (Φ). Notice that K(S n (Φ)) is a frame since meets are unions and joins are intersections so the distributive requirement is satisfied. Furthermore, each [•] i preserves arbitrary suprema (intersection) and thus, from Theorem 7 it is a normal self-map.

Existence of Right Inverses

We shall now address the question of whether a given Kripke constraint system can be extended with extrusion functions. We shall identify a sufficient and necessary condition on accessibility relations for the existence of an extrusion function ↑ i given the space [•] i .

Definition 10 (Determinacy and Unique-Determinacy). Let S and R be the set of states and an accessibility relation of a KS M , respectively. Given s, t ∈ S, we say that s determines t wrt R if (s, t) ∈ R. We say that s uniquely determines t wrt R if s is the only state in S that determines t wrt R. A state s ∈ S is said to be determinant wrt R if it uniquely determines some state in S wrt R. Furthermore, R is determinant-complete if every state in S is determinant wrt R. The following theorem provides a complete characterization, in terms of classes of KS, of the existence of right inverses for space functions.

Theorem 13 (Completeness). Let [•] i be a spatial function of a Kripke scs K(S). Then [•] i has a right inverse iff for every M ∈ S the accessibility relation

i -→ M is determinant- complete.
Henceforth we use M D to denote the class of KS's whose accessibility relations are determinant-complete. It follows from Theorem 13 that S = M D is the largest class for which space functions of a Kripke scs K(S) have right inverses. Since any Kripke scs space function preserves arbitrary suprema, we obtain the following canonical greatest right-inverse construction. Recall that the pre-image of c under [•] i is given by the set [c]

Right Inverse Constructions

-1 i = {d | c = [d] i }.
Definition 14 (Max Right Inverse). Let a Kripke scs K(S) = (Con, , [•] 1 , . . . , [•] n ) be defined over S ⊆ M D . We define ↑ M i as the following self-map on Con :

↑ M i : c → [c] -1 i .
Then ↑ M i is a right inverse for [•] i , and from its definition it is clear that ↑ M i is the greatest right inverse of [•] i wrt . However, ↑ M i is not necessarily normal in the sense of Definition 6. In what follows we shall identify right inverse constructions that are normal.

Normal Right Inverses

The following central lemma provides distinctive properties of any normal right-inverse.

Lemma 15. Let K(S) = (Con, , [•] 1 , . . . , [•] n ) be the Kripke scs over S ⊆ M D . Suppose that f is a normal right-inverse of [•] i . Then for every M ∈ S, c ∈ Con : (i) i (M, s) ⊆ f (c) if (M, s) ∈ c, (ii) {(M, t)} ⊆ f (c) if t is multiply determined wrt i -→ M , and (iii) true ⊆ f (true).
The above property tell us what sets should necessarily be included in every f (c) if f is to be both normal and a right-inverse of [•] i .

In fact, the least self-map f wrt ⊆, i.e., the greatest one wrt the lattice order , satisfying Conditions 1, 2 and 3 in Lemma 15 is indeed a normal right-inverse. We call such a function the max normal right-inverse ↑ MN i and it is given below.

Definition 16 (Max Normal-Right Inverse). Let K(S) = (Con, , [•] 1 , . . . , [•] n ) be a Kripke scs over S ⊆ M D . We define the max normal right-inverse for agent i, ↑ MN i as the following self-map on Con:

↑ MN i (c) def =      -true if c = true -{(M, t) | t is determined wrt i -→ M & ∀s : s i M t, (M, s) ∈ c} (1)
Notice that ↑ MN i (c) excludes indetermined states (i.e. a state t such that for every s ∈ S, (s, t) ∈ R.) if c = true. It turns out that we can add them and obtain a more succinct normal right-inverse:

Definition 17 (Normal Right-Inverse). Let K(S) = (Con, , [•] 1 , . . . , [•] n ) be a Kripke scs over S ⊆ M D . Define ↑ N i : Con → Con as ↑ N i (c) def = {(M, t) | ∀s : s i M t, (M, s) ∈ c}.
Clearly

↑ N i (c) includes every (M, t) such that t is indetermined wrt i -→ M .

Applications

In this section we will illustrate and briefly discuss the results obtained in the previous section in the context of modal logic. We can interpret modal formulae as constraints in a given Kripke scs C = K(S n (Φ)).

Definition 18 (Kripke Constraint Interpretation). Let C be a Kripke scs K(S n (Φ)). Given a modal formula φ in the modal language L n (Φ), its interpretation in the Kripke scs C is the constraint C φ inductively defined as follows:

C p = {(M, s) | π M (s)(p) = 1}, C φ ∧ ψ = C φ C ψ , C ¬φ =∼ C φ , C i φ = [ C φ ] i .
To illustrate our results in the previous sections, we fix a modal language L n (Φ) (whose formulae are) interpreted in an arbitrary Kripke scs C = K(S n (Φ)). Suppose we wish to extend it with modalities -1 i , called reverse modalities also interpreted over the same set of KS's S n (Φ) and satisfying some minimal requirement. The language is given by the following grammar.

Definition 19 (Modal Language with Reverse Modalities). Let Φ be a set of primitive propositions. The modal language L +r n (Φ) is given by the following grammar: φ, ψ, . . .

:= p | φ ∧ ψ | ¬φ | i φ | -1
i φ where p ∈ Φ and i ∈ {1, . . . , n}. The minimal semantic requirement for each -1 i is that:

i -1 i φ ⇔ φ valid in S n (Φ). ( 2
)
We then say that -1 i is a right-inverse modality for i . Since C i φ = [ C φ ] i , we can derive semantic interpretations for -1 i φ by using a right inverse ↑ i for [•] i in Definition 18. Assuming that such a right inverse exists, we can interpret the reverse modality in C as

C -1 i φ = ↑ i ( C φ ). ( 3
)
We can choose ↑ i in Equation ( 3) from the set {↑ N i , ↑ MN i , ↑ M i } of right-inverses given in Section 3.5.

I C L P 2 0 1 6 T C s 16:8

On the Expressiveness of Spatial Constraint Systems

Temporal Operators

We conclude this section with a brief discussion on some right-inverse linear-time modalities. Let us suppose that n = 2 in our modal language L n (Φ) under consideration (thus interpreted in Kripke scs C = K(S 2 (Φ)). Assume further that the intended meaning of the two modalities 1 and 2 are the next operator ( ) and the henceforth/always operator ( ), respectively, in a linear-time temporal logic. To obtain the intended meaning we take S 2 (Φ) to be the largest set such that: If M ∈ S 2 (Φ), M is a 2-agent KS where -→ M t for s = t is intended to capture the fact that t is one of the infinitely many future states for s.

Let us first consider the next operator 1 = . Notice that

1 -→ M is determinant-complete. If we apply Equation (3) with ↑ 1 = ↑ M
1 , we obtain -1 1 = , a past modality known in the literature as strong previous operator [START_REF] Pnueli | The temporal logic of reactive and concurrent systems[END_REF]. If we take ↑ i to be the normal right inverse ↑ N i , we obtain -1 1 = , the past modality known as weak previous operator [START_REF] Pnueli | The temporal logic of reactive and concurrent systems[END_REF]. Notice that the only difference between the two operators is that, if s is an indetermined/initial state wrt 1 -→ M then (M, s) |= φ and (M, s) |= φ for any φ. It follows that is not a normal operator, since T is not valid in S 2 (Φ) but T is.

Let us now consider the always operator 2 = . Notice that 2 -→ M is not determinantcomplete: Take any increasing chain s 0 1

-→ M s 1 1 -→ M .
. . The state s 1 is not determinant because for every s j such that s 1 2 -→ M s j we also have s 0 2 -→ M s j . Theorem 13 tells us that there is no right-inverse ↑ 2 of [•] i that can give us an operator -1 2 satisfying Equation (2).

Ongoing Work

Knowledge in Terms of Space

In this section we show our current work on using spatial constraint systems to express the epistemic concept of knowledge by using the following notion of global information:

Definition 20 (Global Information). Let C be an n-scs with space functions [•] 1 , . . . , [•] n and G be a non-empty subset of {1, . . . , n}.

Group-spaces [•] G and global information [[[•]]] G of G in C are defined as: [c] G def = i∈G [c] i and [[[c]]] G def = ∞ j=0 [c] j G (4) where [c] 0 G def = c and [c] k+1 G def = [[c] k G ] G . The constraint [c] G means that c holds in the spaces of agents in G. The constraint [[[c]]] G entails [[. . . [c] im . . .] i2 ] i1 for any i 1 , i 2 , . . . , i m ∈ G.

Knowledge Constraint System

In [START_REF] Knight | Spatial and epistemic modalities in constraint-based process calculi[END_REF] the authors extended the notion of spatial constraint system to account for knowledge. In this summary we shall refer to the extended notion in [START_REF] Knight | Spatial and epistemic modalities in constraint-based process calculi[END_REF] as S4 constraint systems since it is meant to capture the epistemic logic for knowledge S4. Roughly speaking, one may wish to use [c] i to represent not only some information c that agent i has but rather a fact that he knows. The domain theoretical nature of constraint systems allows for a rather simple and elegant characterization of knowledge by requiring space functions to be Kuratowski closure operators [START_REF] Charles | The algebra of topology[END_REF]: i.e., monotone, extensive and idempotent maps preserving bottom and lubs.

Definition 21 (Knowledge Constraint System [START_REF] Knight | Spatial and epistemic modalities in constraint-based process calculi[END_REF]). An n-agent S4 constraint system (n-s4cs) C is an n-scs whose space functions [•] 1 , . . . , [•] n are also closure operators. Thus, in addition to S.1 and S.2 in Definition 3, each [•] i also satisfies:

(EP.1) [c] i c and (EP.2) [[c] i ] i = [c] i .
Intuitively, in an n-s4cs, [c] i states that the agent i has knowledge of c in its store [•] i . The axiom EP.1 says that if agent i knows c then c must hold, hence [c] i has at least as much information as c. The epistemic principle that an agent i is aware of its own knowledge (the agent knows what he knows) is realized by EP.2. Also, the epistemic assumption that agents are idealized reasoners follows from the monotonicity of space functions, i.e., for a consequence c of d

(d c), then if d is known to agent i, so is c, [d] i [c] i .
In [START_REF] Knight | Spatial and epistemic modalities in constraint-based process calculi[END_REF] the authors use the notion of Kuratowski closure operators

Knowledge as Global Information

Let C = (Con, , [•] 1 , . . . , [•] n ) be a spatial constraint system. From Definition 20 we obtain the following equation:

[[[c]]] {i} = c [c] i [c]
[[[[[c]]] i ]]] i = [[[c]]] i (EP.2
). Furthermore, we can combine knowledge with our belief interpretation of space functions: clearly, [[[c]]] i [c] i holds for any c. This reflects the epistemic principle that whatever is known is also believed [START_REF] Hintikka | Knowledge and belief[END_REF].

We now show that any spatial constraint system with continuous space functions (i.e. functions preserving lubs of any directed set)

[•] 1 , . . . , [•] n induces an s4cs with space functions [[[•]]] 1 , . . . [[[•]]] n . Definition 22. Given an scs C = (Con, , [•] 1 , . . . , [•] n ), we use C * to denote the tuple (Con, , [[[•]]] 1 , . . . , [[[•]]] n ).
One can show that C * is also a spatial constraint system. Besides, it is an s4cs as stated next.

On the Expressiveness of Spatial Constraint Systems

We shall now prove that S4 can also be captured using the global interpretation of space. From now on C denotes the Kripke constraint system K(M) (Definition 9), where M represent a set of non-empty set of n-agent Kripke strutures. Notice that constraints in C, and consequently also in C * , are sets of unrestricted (pointed) Kripke structures. Although C is not an S4cs, from the above theorem, its induced scs C * is. Also, we can give in C * a sound and complete compositional interpretation of S4 formulae.

The compositional interpretation of modal formulae in our constraint system C * is similar to the one introduced in 18 except for the interpretation of the i φ modality.

Notice that i φ is interpreted in terms of the global operation. Since C * is a power-set ordered by reversed inclusion, the lub is given by set intersection. Thus, from Equation ( 5)

C * i φ = [[[ C * φ ]]] i = ω j=0 [C * φ ] j i = ω j=0 [C * φ ] j i (6)
In particular, from Theorem 23 and Axiom EP.2, C * i φ = C * i ( i φ) follows as an S4-knowledge modality; i.e., if agent i knows φ he knows that he knows it.

We conclude this section with the following theorem stating the correctness wrt validity of the interpretation of knowledge as as global operator.

Theorem 24. C * φ = true if and only if φ is S4-valid.

5

Future Work

As future work we are planning to specify the epistemic notion of Distributed Knowledge (DK) [START_REF] Fagin | Reasoning about knowledge[END_REF] as well as a computational notion of process in our algebraic structures.

Distributed Knowledge in Terms of Space

Informally, DK says that, if a given agent i has c → d in his space and an agent j has c in her space, then if we were to communicate with each other we could have d in their space though individually neither i nor j has d. This could be an important concept for distributed systems, e.g. to predict unwanted behavior in a system upon potential communication among agents.

Using [START_REF] Fagin | Reasoning about knowledge[END_REF] and our notion of Heyting implication in Definition 5 we could extend scs with DK as follows. As future work we would like to give an explicit spatial construction that characterizes D G (c).

Processes as Constraint Systems

Concurrent constraint programming (ccp) calculi are a well-known family of process algebras from concurrency theory [15,[START_REF] Prakash Panangaden | A hyperdoctrinal view of concurrent constraint programming[END_REF][START_REF] Di Pierro | An algebraic perspective of constraint logic programming[END_REF][START_REF] Nax P Mendler | A logical view of concurrent constraint programming[END_REF]. Computational processes from ccp can be seen as closure operators over an underlying constraint system C = (Con, ). A closure operator f over C = (Con, ) is a monotonic self map on Con such that f (c) c and f (f (c)) = f (c).

It is well known that closure operators form themselves a complete lattice. Thus, ccp processes can be interpreted as elements of the cs C + = (Con + , ) where Con + is the set of closure operators over Con ordered wrt (recall that f g iff f (c) g(c) for every c ∈ Con.)

We plan to use the space and extrusion functions from spatial constraint systems to give a declarative semantics to the corresponding spatial, time and extrusion constructs in ccp-based process algebras. More importantly, we plan to use the notion of distributed knowledge to derive a corresponding notion in ccp-process algebras. To our knowledge this will be the first time that distributed knowledge is used in the context of process calculi.

Definition 5 (

 5 First, recall that a Heyting implication c → d in our setting corresponds to the weakest constraint one needs to join c with to derive d: The greatest lower bound (glb) {e | e c d}. Similarly, the negation of a constraint c, written ∼ c, can be seen as the weakest constraint inconsistent with c, i.e., the glb {e | e c false} = c → false. Constraint Frames). A constraint system (Con, ) is said to be a constraint frame iff its joins distribute over arbitrary meets: More precisely, c S = {c e | e ∈ S} for every c ∈ Con and S ⊆ Con. Given a constraint frame (Con, ) and c, d ∈ Con, define Heyting implication c → d as {e ∈ Con | c e d} and Heyting negation ∼ c as c → false.

Example 11 .Figure 1

 111 Figure 1 Accessibility relations for an agent i. In each sub-figure we omit the corresponding KS M k from the edges and draw s i -→ t whenever s i -→M k t.

  Let K(S) = (Con, , [•] 1 , . . . , [•] n ) be a Kripke scs. The Axiom of Choice and Theorem 13 tell us that each [•] i has a right inverse (extrusion function) if and only if S ⊆ M D . We are interested, however, in explicit constructions of the right inverses.

1 -→ 1 -→ M . The relation 1 - 1 -

 1111 M is isomorphic to the successor relation on the natural numbers and 2 -→ M is the reflexive and transitive closure of → M is intended to capture the linear flow of time. Intuitively, s → M t means t is the only next state for s. Similarly, s 2

  Thus, it realizes the intuition that c holds globally wrt G: c holds in each nested space involving only the agents in G. In particular, if G is the set of all agents, [[[c]]] G means that c holds everywhere. From the epistemic point of view [[[c]]] G is related to the notion of common-knowledge of c [5].

  [c] i to capture knowledge. In what follows we show an alternative interpretation of knowledge as the global construct [[[c]]] G in Definition 20.

  simplicity, we shall use [[[•]]] i as an abbreviation of [[[•]]] {i} . We shall demonstrate that [[[c]]] i can also be used to represent the knowledge of c by agent i. We will show that the global function [[[c]]] i is in fact a Kuratowski closure operator and thus satisfies the epistemic axioms EP.1 and EP.2 above: It is easy to see that [[[c]]] i satisfies [[[c]]] i c (EP.1). Under certain natural assumptions we shall see that it also satisfies [

Theorem 23 .

 23 Let C = (Con, , [•] 1 , . . . , [•] n ) be a spatial constraint system. If [•] 1 , . . . , [•] n are continuous functions, then C * is an n-agent s4cs.

Definition 25 .

 25 Let C = (Con, ⊆, [•] 1 , . . . , [•] n ). Let G ⊆ {1, 2, . . . , n} be a non-empty subset of agents. Distributed knowledge of G is a self-map D G : Con → Con satisfying the next axioms:1. D G (true) = true 2. D G (c d) = D G (c) D G (d) 3. D G (c) = [c] i if G = {i} 4. D G (c) D G (d) if G ⊆ G Intuitively D G (c) means that G has DK of c.The first condition says that any G has DK of true. The second condition says that, if G has DK of two pieces of information c and d, then G has DK of their join. The third condition tells us that an agent has DK of what he knows. Finally, the fourth condition says that the larger the subgroup, the greater its DK.In previous paragraphs we argued that if agent i has c → d and an agent j has c then they would have DK of d (D {i,j} (d)). Indeed, from the above axioms and the properties of space, one can prove that [c → d] i [c] j D {i,j} (d).

[•] 1 , . . . , [•] n over its set of constraints Con such that: (S.1) [true] i = true, and (S.2) [c d] i = [c] i [d] i

  for each c, d ∈ Con.

	Axiom S.1 requires [•] i to be strict map (i.e. bottom preserving). Intuitively, it states that
	having an empty local space amounts to nothing. Axiom S.2 states that the information in a
	given space can be distributed. Notice that requiring S.1 and S.2 is equivalent to requiring
	that each [•] i preserves finite suprema. Also, S.2 implies that [•] i is monotonic: I.e., if c d
	then [

c] i [d] i .

An alternative syntactic characterization of cs, akin to Scott information systems, is given in[15].

Sally Popkorn. First steps in modal logic. Cambridge University Press, 1st edition, 1994.

Vijay A Saraswat, Martin Rinard, and Prakash Panangaden. Semantic foundations of concurrent constraint programming. In POPL'91, pages 333-352, 1991.

Steven Vickers. Topology via logic. Cambridge University Press, 1st edition, 1996.

* This work was partially supported by INRIA-CORDI.


Christian Frisson
email: christian.frisson@umons.ac.be

Sylvain Malacria
email: sylvain.malacria@inria.fr

Gilles Bailly
email: gilles.bailly@telecom-paristech.fr

Thierry Dutoit
email: thierry.dutoit@umons.ac.be

Bailly Gilles

Ltci

InspectorWidget: a System to Analyze Users Behaviors in Their Applications

Keywords: Logging, automatic annotation, computer vision ACM Classification H.5.2. [Information Interfaces and Presentation (e.g. HCI)]: User Interfaces---Benchmarking

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Interface designers, HCI researchers or usability experts often need to collect information regarding usage of applications in order to interpret quantitative and behavioral aspects from users or to provide user interface guidelines.

Unfortunately, most existing applications are closed: source code or scripting support are not always available to collect and analyze users' behaviors in real world scenarios.

Different methods can alleviate this problem such as replicating the application with specific interaction "hooks" [START_REF] Scarr | The Usability of CommandMaps in Realistic Tasks[END_REF]. However, implementation is time consuming and the replicated application is often a light version of the real one biasing users' behaviors. Dedicated activity plugins or ad-hoc accessibility monitors can also capture user events at different levels of granularity [START_REF] Alexander | AppMonitor: A tool for recording user actions in unmodified Windows applications[END_REF] but several applications do not support these mechanisms. Moreover, these methods are application dependent, i.e. require a specific programming language and/or implement one plugin for each application which is not ideal for complex task involving several applications. Conversely, screen recording while users carry their task [START_REF] Suresh | The Strategic Use of Complex Computer Systems[END_REF] provides a lot of information, but requires to carefully watch and manually annotate the video, which is tedious and not precise enough for studying low-level interactive phenomena (e.g., duration of scrolling actions).

We propose the InspectorWidget, an opensource application to track and analyze users' behaviors in any closed application by combining computer vision based analysis of video-recording with low-level interaction collection. InspectorWidget has four key features. 1) It works with all applications, in particular closed applications where the source code is not available, or applications that do not offer plugins support. 2) It supports logs and event browsing offering data analysis at different levels of granularity, from low level (mouse, keyboard events) to high level (screen recording). 3) It supports additional post-logging and analysis because it collects all possible events a priori (screen record, mouse and key events) and that the experimenter defines rules a posteriori depending of what the focus of the study is. Thus, the experimenter can run other studies with different focus using the same collected data, weeks or months later, simply by defining new rules and without having to collect data again. 4) InspectorWidget relies on visual programming [START_REF] Resnick | Scratch: Programming for All[END_REF] and thus minimizes the need of of programming skills, making it possible for experimenters with sociological or psychological backgrounds to use it.

To achieve this, InspectorWidget relies on a five-step workflow (figure 1): first, it records users' screen content and low-level user interactions (mouse and key events) while they carry their task. Second, the experimenter browses this recording and programs annotations on it by combining explicit active zones definition (e.g, ``this is the scroller'', ``there is the scrollbar'', etc.) and specifying rules (e.g. ``the scrollbar is clicked''). InspectorWidget then automates annotations, allowing to combine the programmed ones with computer-vision and low-level events analysis. Finally, the experimenter analyzes the annotations either by using the visualization provided in InspectorWidget, or by exporting data to process it in her favorite statistical analysis tools.

Design Goals: Observing Applications' Usage

To better understand users' need and practices, we conducted an informative study with 4 experts. We interviewed two HCI researchers, one usability consultant and one software developer to cover different class of users. Based on these interviews, we present five design goals and discuss related works according to these design goals (tables 1 and 2 summarize these goals and compare existing systems).

Collect diverse data. Understanding subtle interactions generally requires to study both users' actions (e.g. mouse, key events) and the semantics of the interface (e.g. menu, buttons). It is thus necessary to collect diverse data such as:

• keylogging or macro recording, for low-level interactions such as mouse or keyboard events; • widgets and states changes logging, for applications implementing accessibility Application Programming Interfaces (APIs) that are specific to operating systems; or applications providing their own information (e.g. Document Object Model (DOM)). • screencasting, to get a video record of the interface. AppMonitor [START_REF] Alexander | AppMonitor: A tool for recording user actions in unmodified Windows applications[END_REF] combines the two first methods to monitor Microsoft Word and Adobe Reader. However, it requires two different implementations as the "accessibility monitor" differs between these two applications. The Autodesk Screencast based on the Chronicle project [START_REF] Grossman | Chronicle: Capture, Exploration, and Playback of Document Workflow Histories[END_REF] is a powerful tool combining the three methods but it is limited to Autodesk applications only. Screen capture software such as ScreenFlow record both video and key events, events can be overlaid on the video but not exported as raw data.

     Delta [12]   Morae 3.3 [3]                     Patina [13]    Prefab [9]        Chronicle/Screencast [10]        Sikuli [8]           Waken [6]    InspectorWidget []                   
Automate diverse annotations. Combining screen recording with computer vision can be used to reverse engineer the GUI of closed applications. This method has been proven useful for automating GUIs and their testing [START_REF] Chang | GUI Testing Using Computer Vision[END_REF], for better understanding the GUI [START_REF] Banovic | Waken: Reverse Engineering Usage Information and Interface Structure from Software Videos[END_REF], or for regenerating GUIs [START_REF] Dixon | Prefab Layers and Prefab Annotations: Extensible Pixel-based Interpretation of Graphical Interfaces[END_REF].

Browse collected data. Browsing collected data is an important part of data analysis. With Chronicle [START_REF] Grossman | Chronicle: Capture, Exploration, and Playback of Document Workflow Histories[END_REF], users can visualize all event histories on an interactive timeline and play back the actual workflow. Delta [START_REF] Kong | Delta: A Tool for Representing and Comparing Workflows[END_REF] allows to compare workflows through several views, among which a cluster of similar workflows and a union graph of shared commands. Finally, Patina [START_REF] Matejka | Patina: Dynamic Heatmaps for Visualizing Application Usage[END_REF] overlays a heatmap of mouse locations directly over the recorded GUI.

Capitalize through a posteriori annotations. During data analysis, experimenters can think of different study that is unfortunately impossible to conduct and would require to re-collect data. Typically, a usability expert could investigate how users display their slides when editing them in Powerpoint, and then realize that she was interested in how users include external materials in their slides. Efficient application usage observation should capitalize on collected data.

In that respect, a tool recording all data such as the screen and the entire DOM description of the interface, where the experimenter specifies the focus of the study a posteriori, is more powerful and flexible than a dedicated logging plugin (e.g. to study a scrollbar position) or a tool where the experimenter specifies a priori what she wants to collect.

Minimize programming requirements. Experimenters, analysts or usability experts are often not computer scientists. They are thus not always familiar with programming language. Even computer scientists are not familiar with all programming languages. A software observing usage application should minimize the needs of programming skills to favor immediate usability and wide adoption.

Example scenario

Suzanne is a HCI researcher interested in color selection and wants to know which color tool (colorwheel, spectrum, etc.) users prefer when selecting colors. She installs Inspector-Widget on the computers of 2 designers using respectively Photoshop and PowerPoint and starts the record mode. At the end of the day, she retrieves the recordings.

Suzanne then uses Inspec-torWidget to record herself selecting the different tools on her own computer in both Photoshop and Powerpoint and uses that recording to program the annotations she wants to perform with InspectorWidget.

To achieve this, she first draws a bounding box around each tab of each color picker windows when selected. She then uses visual programming to program InspectorWidget that automatically annotates users' recordings to find the exact time a specific color tool was used.

Suzanne now wants to analyze the annotated data in R. She exports the annotated data from InspectorWidget and imports it into R.

InspectorWidget

In this section, we describe the concept and implementation of our application.

Concept

Analyzing user's behaviors with closed applications using InspectorWidget follows a five-step workflow: 1) record activity, 2) browse and 3) program annotations, 4) automate annotations and 5) analyze the results (figure 1).

Record activity. First, the experimenter records the screen and logs events to track users activity. Screen recording and interaction events logging are usually separated into two tools, making the observation process cumbersome and the collected data harder to synchronize. We solve this problem by proposing a cross-platform desktop tool that both records the content displayed on screen(s) and logs low-level interaction events (mouse and keyboard).

Browse and Program annotations. The experimenter then programs annotations. In practice, she browses a recording to find a time frame where the system was in a specific state she is interested in (figure 2). She then draws bounding boxes on widgets of the recording for specifying a center of interest, and creates rules on this object with a dedicated syntax (figure 3). Using our example scenario, the experimenter wants to know which color selection tool users used. She first browses the recording until the color picker window of Powerpoint is displayed; she then draws bound-ing boxes around all of the five color tool buttons (A * on figure 2) for each selection state (ColorWheel, sliders, spectrum, etc.). Because she is only interested in when users were interacting with a color tool, she wants InspectorWidget to annotate only when the mouse pointer was located over the color tool window. In that purpose, she also annotates the color dropper (B), the window buttons (C) and the window title (D). These graphical widgets are always displayed in the color tool window (E) and can be tracked using visual programming (figure 3) to retrieve the size and location of the window even if it has been moved or resized. Note that browsing the video to locate the time where the interface is a in specific state (e.g. the color picker is displayed) might be a difficult task because the experimenter does not know exactly when the interface was in this state, or because it is possible that the interface was never in this state. For this reason, the experimenter sets the interface in the correct states on her own computer and then records it. She can also program the annotations and use these as an input for InspectorWidget to annotate all users' recordings.

Automate annotations. Once all annotations have been programmed, the experimenter clicks on "automatic annotation" to instruct InspectorWidget to start the automatic annotation process, using computer vision and the recorded low-level and programmed annotations as inputs (see below for implementation details).

Analyze. The experimenter can directly visualize simple statistics before exporting results. InspectorWidger produces interactive plots on several extracted and nested metrics, such as the time the mouse pointer was over a widget. Data can also be exported as csv files to be processed in the experimenter's favorite statistical analysis tool.

Implementation

InspectorWidget is composed of a cross-platform desktop application for recording, a dedicated server for automating annotations, and a web-based application for browsing the recordings, programming annotations and analyzing the results. InspectorWidget is released as an opensource project under a GPLv3 license, available on github 1 .

Recording (standalone application). Our tool extends application obs-studio [2] with a plugin for logging input events (mouse and keyboard) using the libuiohook [1] library. It supports recording multiple screens and cameras, all mouse and key events, and audio.

Browse recordings, program annotations. Browsing recordings and programming annotations is achieved through a dedicated web-based application, based on the amalia javascript video player [START_REF] Hervé | Amalia.Js: An Open-Source Metadata Driven HTML5 Multimedia Player[END_REF] for browsing and enriching the video with annotation, and based on Google Blockly (inspired by Scratch [START_REF] Resnick | Scratch: Programming for All[END_REF]) for programming the annotations.

Automate annotations. The automatic annotation of the recording is performed by a dedicated server, using OpenCV for template matching and tesseract [4] for text/number detection.

Analyze. The aforementioned web-based application also provides simple data visualization by displaying charts rendered using the d3.js javascript library.

Discussion and future work

We see several directions to improve these works including technical considerations, novel features and user studies.

Technical considerations. A limitation of our approach is that it relies on computer vision which can require time to process large screen videos. We plan to speed up this computational phase with GPU/Parallel processing since we can process the video frames in a non-linear sequence and after the recording. We also plan to pre-process the video in order to remove sequences without users' actions. This will improve both human processing (less video to watch) and computer vision processing. Finally, we plan to delegate some video-based analysis (eg. position of a popup menu) to accessibility tools when these are available on the target application / operating system. Indeed, extracting DOM data can provide information about the hierarchical structure of the widgets and accelerate the computer vision process.

Features. Extracting DOM information will also provide an additional level of granularity between low-level events (e.g. mouse and key events) and high-level events (video screen) by considering the attributes of graphical widgets. We also plan to extend our software from desktop workstation to mobile devices.

Evaluation (of annotated data).

As every computing system relying on computer vision, InspectorWidget is likely to result in errors, either by missing parts of the videos that should be annotated, or by incorrectly annotating parts that should not. We thus plan to run an evaluation with various use cases in order to quantify the accuracy and precision of InspectorWidget, assessing its efficacy in terms of usability.

Evaluation (through annotation tasks). We also plan to conduct a user study with HCI researchers and usability experts to evaluate the qualitative and quantitative benefits of InspectorWidget over manual annotation, assessing the efficiency of our system and the satisfaction of its users. One of the primary motivations for creating InspectorWidget was to support longitudinal ``in the wild'' studies concerning our own research projects. Reciprocally, the analysis of such upcoming studies will provide insight on the strengths and shortcomings of InspectorWidget.

Figure 2 :

 2 Figure 2: Programming annotations (concept): the experimenter defines an active region for the five color tools selection (A*), and then defines active regions for the color dropper (B), the window buttons (C) and the window title (D) that are used to retrieve the window (E) size and location on screen.

Figure 3 :

 3 Figure3: Programming annotations (implementation): on the top the experimenter creates rules using a visual programming language to program the automated annotations, on the bottom the annotated timeline reveals from 1:22 that the user toggled colors tools from sliders to palette then spectrum but not disc.

Table 1 :

 1 Comparison between InspectorWidget and related works. Gray items indicate partial implementations or plans for future work.

Table 2 :

 2 Legend for comparison table entries

http://github.com/InspectorWidget/InspectorWidget

Acknowledgments

The authors would like to thank Nicolas Riche for bridging their collaboration. This work has been partly funded by the Walloon Region of Belgium through GREENTIC grant 1317970 for project SONIXTRIP. The authors would like to thank the SONIXTRIP project partners for their feedback while developing InspectorWidget: Dame Blanche postproduction studios, Océ Software Laboratories and IRiSib Laras lab.