Umut Şimşekli
email: umut.simsekli@telecom-paristech.fr

Roland Badeau
email: roland.badeau@telecom-paristech.fr

Taylan Cemgil
email: taylan.cemgil@boun.edu.

Gael Richard

Gael Richard Stochastic Quasi

Newton Langevin

A Taylan Cemgil

Gaël Tr

Richard

Stochastic Quasi-Newton Langevin Monte Carlo

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

Markov Chain Monte Carlo (MCMC) methods are one of the most important family of algorithms in Bayesian machine learning. These methods lie in the core of various applications such as the estimation of Bayesian predictive densities and Bayesian model selection. They also provide important advantages over optimization-based point estimation methods, such as having better predictive accuracy and being more robust to over-fitting [START_REF] Chen | Stochastic gradient Hamiltonian Monte Carlo[END_REF][START_REF] Ahn | Large-scale distributed Bayesian matrix factorization using stochastic gradient MCMC[END_REF]. Despite their well-known benefits, during the last decade, conventional MCMC methods have lost their charm since they are often criticized as being computationally very demanding. Indeed, classical approaches based on batch Metropolis Hastings would require passing over the whole data set at each iteration and the acceptancerejection test makes the methods even more impractical for modern data sets.

Recently, alternative approaches have been proposed to scale-up MCMC inference to large-scale regime. An important attempt was made by [START_REF] Welling | Bayesian learning via stochastic gradient Langevin dynamics[END_REF], where the authors combined the ideas from Langevin Monte Carlo (LMC) [START_REF] Rossky | Brownian dynamics as smart Monte Carlo simulation[END_REF][START_REF] Roberts | Langevin Diffusions and Metropolis-Hastings Algorithms[END_REF][START_REF] Neal | Handbook of Markov Chain Monte Carlo[END_REF] and stochastic gradient descent (SGD) [START_REF] Robbins | A stochastic approximation method[END_REF][START_REF] Kushner | Stochastic Approximation and Recursive Algorithms and Applications[END_REF], and developed a scalable MCMC framework referred to as stochastic gradient Langevin dynamics (SGLD). Unlike conventional batch MCMC methods, SGLD uses subsamples of the data per iteration similar to SGD. With this manner, SGLD is able to scale up to large datasets while at the same time being a valid MCMC method that forms a Markov chain asymptotically sampling from the target density. Several extensions of SGLD have been proposed [START_REF] Ahn | Bayesian posterior sampling via stochastic gradient Fisher scoring[END_REF][START_REF] Patterson | Stochastic gradient Riemannian Langevin dynamics on the probability simplex[END_REF][START_REF] Ahn | Distributed stochastic gradient MCMC[END_REF][START_REF] Chen | Stochastic gradient Hamiltonian Monte Carlo[END_REF][START_REF] Ding | Bayesian sampling using stochastic gradient thermostats[END_REF][START_REF] Ma | A complete recipe for stochastic gradient MCMC[END_REF][START_REF] Chen | On the convergence of stochastic gradient MCMC algorithms with high-order integrators[END_REF][START_REF] Shang | Covariance-controlled adaptive Langevin thermostat for large-scale Bayesian sampling[END_REF][START_REF] Li | Preconditioned stochastic gradient Langevin dynamics for deep neural networks[END_REF], which are coined under the term Stochastic Gradient MCMC (SG-MCMC).

One criticism that is often directed at SGLD is that it suffers from poor mixing rates when the target densities exhibit strong couplings and scale differences across dimensions. This problem is caused by the fact that SGLD is based on an isotropic Langevin diffusion, which implicitly assumes that different components of the latent variable are uncor-related and have the same scale, a situation which is hardly encountered in practical applications.

In order to be able to generate samples from non-isotropic target densities in an efficient manner, SGLD has been extended in several ways. The common theme in these methods is to incorporate the geometry of the target density to the sampling algorithm. Towards this direction, a first attempt was made by [START_REF] Ahn | Bayesian posterior sampling via stochastic gradient Fisher scoring[END_REF], where the authors proposed Stochastic Gradient Fisher Scoring (SGFS), a preconditioning schema that incorporates the curvature via Fisher scoring. Later, [START_REF] Patterson | Stochastic gradient Riemannian Langevin dynamics on the probability simplex[END_REF] presented Stochastic Gradient Riemannian Langevin Dynamics (SGRLD), where they defined the sampler on the Riemannian manifold by borrowing ideas from [START_REF] Girolami | Riemann manifold Langevin and Hamiltonian Monte Carlo methods[END_REF]. SGRLD incorporates the local curvature information through the expected Fisher information matrix (FIM), which defines a natural Riemannian metric tensor for probability distributions. SGRLD has shown significant performance improvements over SGLD; however, its computational complexity is very intensive since it requires storing and inverting huge matrices, computing Cholesky factors, and expensive matrix products for generating each sample. It further requires computing the third order derivatives and the expected FIM to be analytically tractable, which limit the applicability of the method to a narrow variety of statistical models [START_REF] Calderhead | Sparse approximate manifolds for differential geometric MCMC[END_REF].

In a very recent study, [START_REF] Li | Preconditioned stochastic gradient Langevin dynamics for deep neural networks[END_REF] proposed Preconditioned SGLD (PSGLD), that aims to handle the scale differences in the target density by making use of an adaptive preconditioning matrix that is chosen to be diagonal for computational purposes. Even though this method is computationally less intensive than SGRLD, it still cannot handle highly correlated target densities since the preconditioning matrix is forced to be diagonal. Besides, in order to reduce the computational burden, the authors discard a correction term in practical applications, which introduces permanent bias that does not vanish asymptotically.

In this study, we propose Hessian Approximated MCMC (HAMCMC), a novel SG-MCMC method that computes the local curvature of the target density in an accurate yet computationally efficient manner. Our method is built up on similar ideas from the Riemannian approaches; however, instead of using the expected FIM, we consider the local Hessian of the negative log posterior, whose expectation coincides with the expected FIM. Instead of computing the local Hessian and inverting it for each sample, we borrow ideas from Quasi-Newton optimization methods and directly approximate the inverse Hessian by using a limited history of samples and their stochastic gradients. By this means, HAMCMC is (i) computationally more efficient than SGRLD since its time and memory complexities are linear with the dimension of the latent variable, (ii) it can be applied to a wide variety of statistical models without requiring the expected FIM to be analytically tractable, and (iii) it is more powerful than diagonal preconditioning approaches such as PSGLD, since it uses dense approximations of the inverse Hessian, hence is able to deal with correlations along with scale differences.

We provide rigorous theoretical analysis for HAMCMC, where we show that HAMCMC is asymptotically unbiased and consistent with posterior expectations. We evaluate HAMCMC on a synthetic and two challenging real datasets. In particular, we apply HAMCMC on two different matrix factorization problems and we evaluate its performance on a speech enhancement and a distributed link prediction application. Our experiments demonstrate that HAMCMC achieves fast convergence rates similar to SGRLD while at the same time having low computational requirements similar to SGLD and PSGLD.

We note that SGLD has also been extended by making use of higher order dynamics [START_REF] Chen | Stochastic gradient Hamiltonian Monte Carlo[END_REF][START_REF] Ding | Bayesian sampling using stochastic gradient thermostats[END_REF][START_REF] Ma | A complete recipe for stochastic gradient MCMC[END_REF][START_REF] Shang | Covariance-controlled adaptive Langevin thermostat for large-scale Bayesian sampling[END_REF]. These extensions are rather orthogonal to our contributions and HAMCMC can be easily extended in the same directions.

Preliminaries

Let θ be a random variable in R D . We aim to sample from the posterior distribution of θ, given as p(θ|x) ∝ exp(-U (θ)), where U (θ) is often called the potential energy and defined as U (θ) = -[log p(x|θ)+log p(θ)]. Here, x {x n } N n=1 is a set of observed data points, and each x n ∈ R P . We assume that the data instances are independent and identically distributed, so that we have:

U (θ) = -[log p(θ) + N n=1 log p(x n |θ)]. (1)
We define an unbiased estimator of U (θ) as follows:

Ũ (θ) = -[log p(θ) + N N Ω n∈Ω log p(x n |θ)] (2)
where Ω ⊂ {1, . . . , N } is a random data subsample that is drawn with replacement, N Ω = |Ω| is the number of elements in Ω. We will occasionally use ŨΩ (θ) for referring to Ũ (θ) when computed on a specific subsample Ω.

Stochastic Gradient Langevin Dynamics

By combining ideas from LMC and SGD, [START_REF] Welling | Bayesian learning via stochastic gradient Langevin dynamics[END_REF] presented SGLD that asymptotically generates a sample θ t from the posterior distribution by iteratively applying the following update equation:

θ t = θ t-1 -t ∇ Ũ (θ t-1 ) + η t ( 3
)
where t is the step-size, and η t is Gaussian noise: η t ∼ N (0, 2 t I), and I stands for the identity matrix.

This method can be seen as the Euler discretization of the Langevin dynamics that is described by the following stochastic differential equation (SDE):

dθ t = -∇U (θ t )dt + √ 2dW t (4)
where W t is the standard Brownian motion. In the simulations ∇U (θ) is replaced by the stochastic gradient ∇ Ũ (θ), which is an unbiased estimator of ∇U (θ). Convergence analysis of SGLD has been studied in [START_REF] Sato | Approximation analysis of stochastic gradient Langevin dynamics by using Fokker-Planck equation and Ito process[END_REF][START_REF] Teh | Consistency and fluctuations for stochastic gradient Langevin dynamics[END_REF]. Since W t is isotropic, SGLD often suffers from poor mixing rates when the target density is highly correlated or contains big scale differences.

The L-BFGS algorithm

In this study, we consider a limited-memory Quasi-Newton (QN) method, namely the L-BFGS algorithm [START_REF] Nocedal | Numerical optimization[END_REF]) that iteratively applies the following equation in order to find the maximum a-posteriori estimate:

θ t = θ t-1 -t H t ∇U (θ t-1 ) (5)
where H t is an approximation to the inverse Hessian at θ t-1 . The L-BFGS algorithm directly approximates the inverse of the Hessian by using the M most recent values of the past iterates. At each iteration, the inverse Hessian is approximated by applying the following recursion: (using

H t = H M -1 t ) H m t = (I - s τ y τ y τ s τ )H m-1 t (I - y τ s τ y τ s τ ) + s τ s τ y τ s τ (6)
where s t θ t -θ t-1 , y t ∇U (θ t ) -∇U (θ t-1 ), and τ = t -M + m and the initial approximation is chosen as H 1 t = γI for some γ > 0. The matrix-vector product H t ∇U (θ t-1 ) is often implemented either by using the twoloop recursion [START_REF] Nocedal | Numerical optimization[END_REF] or by using the compact form [START_REF] Byrd | Representations of quasi-Newton matrices and their use in limited memory methods[END_REF], which both have linear time complexity O(M D). Besides, since L-BFGS needs to store only the latest M -1 values of s t and y t , the space complexity is also O(M D), as opposed to classical QN methods that have quadratic memory complexity.

Surprisingly, QN methods have not attracted much attention from the MCMC literature. [START_REF] Zhang | Quasi-Newton methods for Markov Chain Monte Carlo[END_REF] combined classical Hamiltonian Monte Carlo with L-BFGS for achieving better mixing rates for small-and medium-sized problems. This method considers a batch scenario with full gradient computations which are then appended with costly Metropolis acceptance steps. Recently, [START_REF] Dahlin | Quasi-Newton particle Metropolis-Hastings[END_REF] developed a particle Metropolis-Hastings schema based on [START_REF] Zhang | Quasi-Newton methods for Markov Chain Monte Carlo[END_REF].

In this study, we consider a stochastic QN (SQN) framework for MCMC. The main difference in these approaches is that they use stochastic gradients ∇ Ũ (θ) in the L-BFGS computations. These methods have been shown to provide better scalability properties than QN methods, and more favorable convergence properties than SGD-based approaches. However, it has been shown that straightforward extensions of L-BFGS to the stochastic case would fail in practice and therefore special attention is required [START_REF] Schraudolph | A stochastic quasi-Newton method for online convex optimization[END_REF][START_REF] Byrd | A stochastic quasi-Newton method for large-scale optimization[END_REF].

Stochastic Quasi-Newton LMC

Recent studies have shown that Langevin and Hamiltonian Monte Carlo methods have strong connections with optimization techniques. Therefore, one might hope for developing stronger MCMC algorithms by borrowing ideas from the optimization literature [START_REF] Qi | Hessian-based Markov Chain Monte Carlo algorithms[END_REF][START_REF] Zhang | Quasi-Newton methods for Markov Chain Monte Carlo[END_REF][START_REF] Bui-Thanh | A scaled stochastic Newton algorithm for Markov Chain Monte Carlo simulations[END_REF][START_REF] Pereyra | Proximal Markov Chain Monte Carlo algorithms[END_REF][START_REF] Chaari | A Hamiltonian Monte Carlo method for non-smooth energy sampling[END_REF][START_REF] Bubeck | Finite-time analysis of projected Langevin Monte Carlo[END_REF][START_REF] Li | Preconditioned stochastic gradient Langevin dynamics for deep neural networks[END_REF]. However, incorporating ideas from optimization methods to an MCMC framework requires careful design and straightforward extensions often do not yield proper algorithms [START_REF] Chen | Stochastic gradient Hamiltonian Monte Carlo[END_REF][START_REF] Ma | A complete recipe for stochastic gradient MCMC[END_REF]. In this section, we will first show that a naïve way of developing an SG-MCMC algorithm based on L-BFGS would not target the correct distribution. Afterwards, we will present our proposed algorithm HAMCMC and show that it targets the correct distribution and it is asymptotically consistent with posterior expectations.

A Naïve Algorithm

A direct way of using SQN ideas in an LMC framework would be achieved by considering H t as a preconditioning matrix in an SGLD context [START_REF] Welling | Bayesian learning via stochastic gradient Langevin dynamics[END_REF][START_REF] Ahn | Bayesian posterior sampling via stochastic gradient Fisher scoring[END_REF]) by combining Eq. 3 and Eq. 5, which would yield the following update equation:

θ t = θ t-1 -t H t (θ t-M :t-1 )∇ Ũ (θ t-1 ) + η t (7)
where H t (•) is the approximate inverse Hessian computed via L-BFGS, M denotes the memory size in L-BFGS and

η t ∼ N 0, 2 t H t (θ t-M :t-1
) . Here, we use a slightly different notation and denote the L-BFGS approximation via H t (θ t-M :t-1 ) instead of H t in order to explicitly illustrate the samples that are used in the L-BFGS calculations.

Despite the fact that such an approach would introduce several challenges, which will be described in the next section, for now let us assume computing Eq. 7 is feasible. Even so, this approach does not result in a proper MCMC schema.

Proposition 1. The Markov chain described in Eq. 7 does not target the posterior distribution p(θ|x) unless

D j=1 ∂ ∂θj H ij (θ) = 0 for all i ∈ {1, . . . , D}.
Proof. Eq. 7 can be formulated as a discretization of a continuous-time diffusion that is given as follows:

dθ t = -H(θ t )∇U (θ t )dt + 2H(θ t )dW t (8)
where ∇U (θ t ) is approximated by ∇ Ũ (θ t ) in simulations. Theorems 1 and 2 of [START_REF] Ma | A complete recipe for stochastic gradient MCMC[END_REF] together show that SDEs with state dependent volatilities leave the posterior distribution invariant only if the drift term contains an additional 'correction' term, Γ(θ t ), defined as follows:1

Γ i (θ) = D j=1 ∂ ∂θ j H ij (θ). (9)
Due to the hypothesis, Eq. 8 clearly does not target the posterior distribution, therefore Eq. 7 does not target the posterior distribution either.

In fact, this result is neither surprising nor new. It has been shown that in order to ensure targeting the correct distribution, we should instead consider the following SDE [START_REF] Girolami | Riemann manifold Langevin and Hamiltonian Monte Carlo methods[END_REF][START_REF] Xifara | Langevin diffusions and the Metropolisadjusted Langevin algorithm[END_REF][START_REF] Patterson | Stochastic gradient Riemannian Langevin dynamics on the probability simplex[END_REF][START_REF] Ma | A complete recipe for stochastic gradient MCMC[END_REF]:

dθ t = -[H(θ t )∇U (θ t ) + Γ(θ t )]dt + 2H(θ t )dW t
where Γ(θ t ) must be taken into account when generating the samples. If we choose

H(θ t ) = E[∇ 2 U (θ t )] -1 (i.e
H(θ t ) = diag(1/(λ + v(θ t ))) v(θ t ) = αv(θ t-1 ) + (1 -α)ḡ Ωt-1 (θ t-1 ) • ḡΩt-1 (θ t-1 )
where ḡΩ (θ) (1/N Ω ) n∈Ω ∇ log p(x n |θ), the symbols •/• and • • • respectively denote element-wise division and multiplication, and α ∈ [0, 1] and λ ∈ R + are the parameters to be tuned.

The correction term Γ(θ t ) does not vanish except for a very limited variety of models and computing this term requires the computation of the second derivatives of Ũ (θ t ) in our case (whereas it requires computing the third derivatives in the Riemannian methods). This conflicts with our motivation of using QN methods for avoiding the Hessian computations in the first place.

In classical Metropolis-Hastings settings, where Langevin dynamics is only used in the proposal distribution, the correction term Γ(θ t ) can be discarded without violating the convergence properties thanks to the acceptance-rejection step [START_REF] Qi | Hessian-based Markov Chain Monte Carlo algorithms[END_REF][START_REF] Girolami | Riemann manifold Langevin and Hamiltonian Monte Carlo methods[END_REF][START_REF] Zhang | Quasi-Newton methods for Markov Chain Monte Carlo[END_REF][START_REF] Calderhead | Sparse approximate manifolds for differential geometric MCMC[END_REF]. However, such an approach would result in slower convergence [START_REF] Girolami | Riemann manifold Langevin and Hamiltonian Monte Carlo methods[END_REF]. On the other hand, in SG-MCMC settings which do not include an acceptancerejection step, this term can be problematic and should be handled with special attention.

In [START_REF] Ahn | Bayesian posterior sampling via stochastic gradient Fisher scoring[END_REF], the authors discarded the correction term in a heuristic manner. Recently, [START_REF] Li | Preconditioned stochastic gradient Langevin dynamics for deep neural networks[END_REF] showed that discarding the correction term induces permanent bias which deprives the methods of their asymptotic consistency and unbiasedness. In the sequel, we will show that the computation of Γ(θ t ) can be avoided without inducing permanent bias by using a special construction that exploits the limited memory structure of L-BFGS.

Hessian Approximated MCMC

In this section, we present our proposed method HAM-CMC. HAMCMC applies the following update rules for generating samples from the posterior distribution:

θ t = θ t-M -t H t θ ¬(t-M ) t-2M +1:t-1 ∇ Ũ (θ t-M ) + η t (10)
where

θ ¬c a:b ≡ (θ a:b \ θ c ), η t ∼ N 0, 2 t H t (•)
, and we assume that the initial 2M + 1 samples, i.e. θ 0 , . . . , θ 2M are already provided.

As opposed to the naïve approach, HAMCMC generates the sample θ t based on θ t-M and it uses a history samples θ t-2M +1 , . . . , θ t-M -1 , θ t-M +1 , . . . , θ t-1 in the L-BFGS computations. Here, we define the displacements and the gradient differences in a slightly different manner from usual L-BFGS, given as follows: s t = θ t -θ t-M and y t = ∇ Ũ (θ t ) -∇ Ũ (θ t-M ). Therefore, M must be chosen at least 2 or higher. HAMCMC requires to store only the latest M samples and the latest M -1 memory components, i.e. θ t-M :t-1 , s t-M +1:t-1 , and y t-M +1:t-1 , resulting in linear memory complexity.

An important property of HAMCMC is that the correction term Γ(θ) vanishes due to the construction of our algorithm, which will be formally proven in the next section. Informally, since H t is independent of θ t-M conditioned on θ ¬(t-M ) t-2M +1:t-1 , the change in θ t-M does not affect H t and therefore all the partial derivatives in Eq. 9 become zero. This property saves us from expensive higher-order derivative computations or inducing permanent bias due to the negligence of the correction term. On the other hand, geometrically, our approach corresponds to choosing a flat Riemannian manifold specified by the metric tensor H t , whose curvature is constant (i.e. Γ(θ) = 0).

We encounter several challenges due to the usage of stochastic gradients that are computed on random sub-Algorithm 1: Hessian Approximated MCMC

1 input: M , γ, λ, N Ω , θ 0 , . . . , θ 2M 2 for t = 2M + 1, • • • , T do 3 Draw Ω t ⊂ {1, . . . , N } 4 Generate z t ∼ N (0, I) // L-BFGS computations 5 ξ t = H t θ ¬(t-M ) t-2M +1:t-1 ∇ ŨΩt (θ t-M ) (Eq. 6) 6 η t = S t θ ¬(t-M ) t-2M +1:t-1 z t (Eq. 11) // Generate the new sample 7 θ t = θ t-M -t ξ t + √ 2 t η t (Eq. 10) // Update L-BFGS memory 8 s t =θ t -θ t-M , y t =∇ ŨΩt (θ t )-∇ ŨΩt (θ t-M )+λs t
sets of the data. The first challenge is the data consistency [START_REF] Schraudolph | A stochastic quasi-Newton method for online convex optimization[END_REF][START_REF] Byrd | A stochastic quasi-Newton method for large-scale optimization[END_REF]. Since we draw different data subsamples Ω t at different epochs, the gradient differences y t would be simply 'inconsistent'. Handling this problem in incremental QN settings (i.e., the data subsamples are selected via a deterministic mechanism, rather than being chosen at random) is not as challenging, however, the randomness in the stochastic setting prevents simple remedies such as computing the differences in a cyclic fashion. Therefore, in order to ensure consistent gradient differences, we slightly increase the computational needs of HAMCMC and perform an additional stochastic gradient computation at the end of each iteration, i.e. y t = ∇ ŨΩt (θ t ) -∇ ŨΩt (θ t-M ) where both gradients are evaluated on the same subsample Ω t .

In order to have a valid sampler, we are required to have positive definite H t (•). However, even if U (θ) was strongly convex, due to data subsampling L-BFGS is no longer guaranteed to produce positive definite approximations. One way to address this problem is to use variance reduction techniques as presented in [START_REF] Byrd | A stochastic quasi-Newton method for large-scale optimization[END_REF]; however, such an approach would introduce further computational burden. In this study, we follow a simpler approach and address this problem by approximating the inverse Hessian in a trust region that is parametrized by λ, i.e. we use L-BFGS to approximate (∇ 2 U (θ)+λI) -1 . For large enough λ this approach will ensure positive definiteness. The L-BFGS updates for this problem can be obtained by simply modifying the gradient differences as: y t ← y t + λs t [START_REF] Schraudolph | A stochastic quasi-Newton method for online convex optimization[END_REF].

The final challenge is to generate η t whose covariance is a scaled version of the L-BFGS output. This requires to compute the square root of H t , i.e. S t S t = H t , so that we can generate η t as √ 2 t S t z t , where z t ∼ N (0, I). Fortunately, we can directly compute the product S t z t within the L-BFGS framework by using the following recursion [START_REF] Brodlie | Rankone and rank-two corrections to positive definite matrices expressed in product form[END_REF][START_REF] Zhang | Quasi-Newton methods for Markov Chain Monte Carlo[END_REF]:

H m t = S m t (S m t ) , S m t = (I -p τ q τ )S m-1 t B m t = C m t (C m t ) , C m t = (I -u τ v τ )C m-1 t v τ = s τ s τ B m-1 t s τ , u τ = s τ B m-1 t s τ s τ y τ y τ + B m-1 t s τ , p τ = s τ s τ y τ , q τ = s τ y τ s τ B m-1 t y τ B m-1 t s τ -y τ (11)
where S t ≡ S M -1 t and B m t = (H m t ) -1 . By this approach, η t can be computed in O(M 2 D) time, which is still linear in D. We illustrate HAMCMC in Algorithm 1.

Note that large M would result in a large gap between two consecutive samples and therefore might require larger λ for ensuring positive definite L-BFGS approximations. Such a circumstance would be undesired since H t would get closer to the identity matrix and therefore result in HAMCMC being similar to SGLD. In our computational studies, we have observed that choosing M between 2 and 5 is often adequate in several applications.

Convergence Analysis

We are interested in approximating the posterior expectations by using sample averages:

h R D h(θ)π(dθ) ≈ ĥ 1 W T T t=1 t h(θ t ), (12)
where π(θ) p(θ|x), W T T t=1 t , and θ t denotes the samples generated by HAMCMC. In this section we will analyze the asymptotic properties of this estimator. We consider a theoretical framework similar to the one presented in [START_REF] Chen | On the convergence of stochastic gradient MCMC algorithms with high-order integrators[END_REF]. In particular, we are interested in analyzing the bias E[ ĥ]-h and the mean squared-error E ( ĥh) 2 of our estimator.

A useful way of analyzing dynamics-based MCMC approaches is to first analyze the underlying continuous dynamics, then consider the MCMC schema as a discretetime approximation [START_REF] Roberts | Langevin Diffusions and Metropolis-Hastings Algorithms[END_REF][START_REF] Sato | Approximation analysis of stochastic gradient Langevin dynamics by using Fokker-Planck equation and Ito process[END_REF][START_REF] Chen | On the convergence of stochastic gradient MCMC algorithms with high-order integrators[END_REF]. However, this approach is not directly applicable in our case. Inspired by [START_REF] Roberts | Convergence of adaptive direction sampling[END_REF] and [START_REF] Zhang | Quasi-Newton methods for Markov Chain Monte Carlo[END_REF], we convert Eq. 10 to a first order Markov chain that is defined on the product space R D(2M -1) such that Θ t ≡ {θ t-2M +2 , . . . , θ t }. In this way, we can show that HAM-CMC uses a transition kernel which modifies only one element of Θ t per iteration and rearranges the samples that will be used in the L-BFGS computations. Therefore, the overall HAMCMC kernel can be interpreted as a composition of M different preconditioned SGLD kernels whose (∇ Ũ (θ t ) -∇U (θ t )) H t ∇. Then, we can bound the bias and MSE of HAMCMC as follows:

(a) E[ ĥ] -h = O 1 L K + Y K L K (b) E ( ĥ -h) 2 = O K k=1 2 kM L 2 K E ∆V k 2 + 1 L K + Y 2 K L 2 K
where h is smooth and

∆V k = ∆V m * k +kM
, where m * k = arg max 1≤m≤M E ∆V m+kM 2 , and ∆V t denotes the operator norm.

The proof is given in the Supplement. The theorem implies that as T goes to infinity, the bias and the MSE of the estimator vanish. Therefore, HAMCMC is asymptotically unbiased and consistent.

Experiments

Linear Gaussian Model

We conduct our first set of experiments on synthetic data where we consider a rather simple Gaussian model whose posterior distribution is analytically available. The model is given as follows:

θ ∼ N (0, I), x n |θ ∼ N (a n θ, σ 2 x ), (13)
for all n. Here, we assume {a n } N n=1 and σ 2

x are known and we aim to draw samples from the posterior distribution p(θ|x). We will compare the performance of HAMCMC against SGLD, PSGLD, and SGRLD. In these experiments, we determine the step size as t = (a /t) 0.51 . In all our experiments, for each method, we have tried several values for the hyper-parameters with the same rigor and we report the best results. We also report all of the hyper-parameters used in the experiments (including Sections 4.2-4.3) in the Supplement. These experiments are conducted on a standard laptop computer with 2.5GHz Quad-core Intel Core i7 CPU and all the methods are implemented in Matlab.

In the first experiment, we first generate the true θ and the observations x by using the generative model given in Eq. 13. We set D = 2 for visualization purposes and σ 2

x = 10, then we randomly generate the vectors {a n } n in such a way that the posterior distribution will be correlated. Then we generate T = 20000 samples by using the SG-MCMC methods, where the size of the data subsamples is selected as N Ω = N/100. We discard the first half of the samples as burn-in. Figure 1 shows the typical results of this experiment. We can clearly observe that SGLD cannot explore the posterior efficiently and gets stuck around the mode of the distribution. PSGLD captures the shape of the distribution in a more accurate way than SGLD since it is able to take the scale differences into account; however, it still cannot explore lower probability areas efficiently. Besides, we can see that SGRLD performs much better than SGLD and PSGLD. This is due to the fact that it uses the inverse expected FIM of the full problem for generating each sample, where this matrix is simply ( n a n a n /σ 2

x + I) -1 for this model. Therefore, SGRLD requires much heavier computations as it needs to store a D × D matrix, computes the Cholesky factors of this matrix, and performs matrix-vector products at each iteration. Furthermore, in more realistic probabilistic models, the expected FIM almost always depends on θ; hence, the computation burden of SGRLD is further increased by the computation of the inverse of the D × D matrix at each iteration. On the other hand, Fig. 1 shows that HAMCMC takes the best of both worlds: it is able to achieve the quality of SGRLD since it makes use of dense approximations to the inverse Hessian and it has low computational requirements similar to SGLD and PSGLD. This observation becomes more clear in our next experiment.

In our second experiment, we again generate the true θ and the observations by using Eq. 13. Then, we approximate the posterior mean θ = θp(θ|x)dθ by using the aforementioned MCMC methods. For comparison, we monitor θθ2 where θ is the estimate that is obtained from MCMC. Figure 2 shows the results of this experiment for D = 10 and D = 100. In the left column, we show the error as a function of iterations. These results show that the convergence rate of SGRLD (with respect to iterations) is much faster than SGLD and PSGLD. As expected, HAM-CMC yields better results than SGLD and PSGLD even in the simplest configuration (M = 2), and it performs very similarly to SGRLD as we set M = 3. The performance difference becomes more prominent as we increase D.

An important advantage of HAMCMC is revealed when we take into account the total running time of these methods. These results are depicted in the right column of Fig. 2, where we show the error as a function of wall-clock time 2 . We can observe that, since SGLD, PSGLD, and HAMCMC have similar computational complexities, the shapes of their corresponding plots do not differ significantly. However, SGRLD appears to be much slower than the other methods as we increase D.

Alpha-Stable Matrix Factorization

In our second set of experiments, we consider a recently proposed probabilistic matrix factorization model, namely alpha-stable matrix factorization (αMF), that is given as follows ( Şimşekli et al., 2015):

W ik ∼ GG(a w , b w , -2/α), H kj ∼ GG(a h , b h , -2/α) X ij |W, H ∼ SαS c [ k W ik H kj ] 1/α (14)
where X ∈ C I×J is the observed matrix with complex entries, and W ∈ R I×K + and H ∈ R K×J + are the latent factors. Here GG denotes the generalized gamma distribution [START_REF] Stacy | A generalization of the gamma distribution[END_REF] and SαS c denotes the complex symmetric α-stable distribution [START_REF] Samoradnitsky | Stable non-Gaussian random processes: stochastic models with infinite variance[END_REF]. Stable distributions are heavy-tailed distributions and they are the limiting distributions in the generalized central limit theorem. They are often characterized by four parameters: S(α, β, σ, µ), where α ∈ (0, 2] is the characteristic exponent, β ∈ [-1, 1] is the skewness parameter, σ ∈ (0, ∞) is the dispersion parameter, and µ ∈ (-∞, ∞) is the location parameter. The distribution is called symmetric (SαS) if β = 0. The location parameter is also chosen as 0 in αMF.

The probability density function of the stable distributions cannot be written in closed-form except for certain spe- cial cases; however it is easy to draw samples from them. Therefore, MCMC has become the de facto inference tool for α-stable models like αMF [START_REF] Godsill | Bayesian inference for time series with heavy-tailed symmetric α-stable noise processes[END_REF]. By using data augmentation and the product property of stable distributions, Şimşekli et al. (2015) proposed a partially collapsed Gibbs sampler for making inference in this model. The performance of this approach was then illustrated on a speech enhancement problem.

In this section, we derive a new inference algorithm for αMF that is based on SG-MCMC. By using the product property of stable models [START_REF] Kuruoglu | Signal processing in α-stable noise environments: a least lp-norm approach[END_REF], we express the model as conditionally Gaussian, given as follows:

W ik ∼ GG(a w , b w , -2/α), H kj ∼ GG(a h , b h , -2/α) Φ ij ∼ S α/2, 1, 2 cos(πα)/4 2/α , 0 X ij |W, H, Φ ∼ N c 0, Φ ij [ k W ik H kj ] 2/α , (15)
where N c denotes the complex Gaussian distribution.

Here, by assuming α is already provided, we propose a Metropolis and SG-MCMC within Gibbs approach, where we generate samples from the full conditional distributions of the latent variables in such a way that we use a Metropolis step for sampling Φ where the proposal is the prior and we use SG-MCMC for sampling W and H from their full conditionals. Since all the elements of W and H must be non-negative, we apply mirroring at the end of each iteration where we replace negative elements with their absolute values [START_REF] Patterson | Stochastic gradient Riemannian Langevin dynamics on the probability simplex[END_REF].

We evaluate HAMCMC on the same speech enhancement application described in ( Şimşekli et al., 2015) by using the same settings. The aim here is to recover clean speech signals that are corrupted by different types of real-life noise signals [START_REF] Hu | Subjective comparison and evaluation of speech enhancement algorithms[END_REF]. We use the Matlab code that can be downloaded from the authors' websites in order to generate the same experimental setting. We first train W on a clean speech corpus, then we fix W at denoising and sample the rest of the variables. For each test signal (out of 80) we have I = 256 and J = 140. The rank is set K = 105 where the first 100 columns of W is reserved for clean speech and for speech α = 1.2 and for noise α = 1.89. Note that the model used for denoising is slightly different from Eq. 14 and we refer the readers to the original paper for further details of the experimental setup. In this experiment, we compare HAMCMC against SGLD and PSGLD. SGRLD cannot be applied to this model since the expected FIM is not tractable. For each method, we set N Ω = IJ/10 and we generate 2500 samples where we compute the Monte Carlo averages by using the last 200 samples. For HAMCMC, we set M = 5. Fig. 3 shows the denoising results on the test set in terms of signal-todistortion ratio (SDR) when the mixture signal-to-noise ratio is 5dB. The results show that SGLD and PSGLD perform similarly, where the quality of the outputs of PSGLD is slightly higher than the ones obtained from SGLD. We can observe that HAMCMC provides a significant performance improvement over SGLD and PSGLD, thanks to the usage of local curvature information.

Distributed Matrix Factorization

In our final set of experiments, we evaluate HAMCMC on a distributed matrix factorization problem, where we consider the following probabilistic model:

W ik ∼ N (0, σ 2 w ), H kj ∼ N (0, σ 2 h ), X ij |• ∼ N k W ik H kj , σ 2 x .
Here, W ∈ R I×K , H ∈ R K×J , and X ∈ R I×J . This model is similar to [START_REF] Salakhutdinov | Bayesian probabilistic matrix factorization using Markov Chain Monte Carlo[END_REF] and is often used in distributed matrix factorization problems [START_REF] Gemulla | Large-scale matrix factorization with distributed stochastic gradient descent[END_REF]Şimşekli et al., 2015b).

Inspired by Distributed SGLD (DSGLD) for matrix factorization [START_REF] Ahn | Large-scale distributed Bayesian matrix factorization using stochastic gradient MCMC[END_REF] and Parallel SGLD ( Şimşekli et al., 2015a), we partition X into disjoint subsets where each subset is further partitioned into disjoint blocks. This schema is illustrated in Fig. 4, where X is partitioned into 4 disjoint subsets Ω (1) , . . . , Ω (4) and each subset contains 4 different blocks that will be distributed among different computation nodes. By using this approach, we extend PS-GLD and HAMCMC to the distributed setting similarly to DSGLD, where at each iteration the data subsample Ω t is selected as Ω (i) with probability |Ω (i) |/ j |Ω (j) |. At the end of each iteration the algorithms transfer a small block of H to a neighboring node depending on Ω t+1 . PS-GLD and HAMCMC further need to communicate other variables that are required for computing H t , where the communication complexity is still linear with D. Finally, HAMCMC requires to compute six vector dot products at each iteration that involves all the computation nodes, such as s t y t . These computations can be easily implemented by using a reduce operation which has a communication complexity of O(M 2 ). By using this approach, the methods have the same theoretical properties except that the stochastic gradients would be expected to have larger variances.

For this experiment, we have implemented all the algorithms in C by using a low-level message passing protocol, namely the OpenMPI library. In order to keep the implementation simple, for HAMCMC we set M = 2. We conduct our experiments on a small-sized cluster with 4 interconnected computers each of them with 4 Intel Xeon 2.93GHz CPUs and 192 GB of memory.

We compare distributed HAMCMC against DSGLD and distributed PSGLD on a large movie ratings dataset, namely the MovieLens 1M (grouplens.org). This dataset contains about 1 million ratings applied to I = 3883 movies by J = 6040 users, resulting in a sparse observed matrix X with 4.3% non-zero entries. We randomly select 10% of the data as the test set and partition the rest of the data as illustrated in Fig. 4. The rank of the factorization is chosen as K = 10. We set σ 2 w = σ 2 h = σ 2 x = 1. In these experiments, we use a constant step size for each method and discard the first 50 samples as burn-in. Note that for constant step size, we no longer have asymptotic unbiasedness; however, the bias and MSE are still bounded. Fig. 5 shows the comparison of the algorithms in terms of the root mean squared-error (RMSE) that are obtained on the test set. We can observe that DSGLD and PSGLD have similar converges rates. On the other hand, HAMCMC converges faster than these methods while having almost the same computational requirements.

Conclusion

We presented HAMCMC, a novel SG-MCMC algorithm that achieves high convergence rates by taking the local geometry into account via the local Hessian that is efficiently computed by the L-BFGS algorithm. HAMCMC is both efficient and powerful since it uses dense approximations of the inverse Hessian while having linear time and memory complexity. We provided formal theoretical analysis and showed that HAMCMC is asymptotically consistent. Our experiments showed that HAMCMC achieves better convergence rates than the state-of-the-art while keeping the computational cost almost the same. As a next step, we will explore the use of HAMCMC in model selection applications ( Şimşekli et al., 2016).

  Proceedings of the 33 rd International Conference on Machine Learning, New York, NY, USA, 2016. JMLR: W&CP volume 48. Copyright 2016 by the author(s).

Figure 1 .

 1 Figure 1. The illustration of the samples generated by different SG-MCMC methods. The contours of the true posterior distribution is shown with dashed lines. We set M = 2 for HAMCMC.

Figure 2 .

 2 Figure 2. The error between the true posterior mean θ and the Monte Carlo estimates θ for D = 10 and D = 100. On the left column, we show the error versus iterations and on the right column we show the error versus wall-clock time.

Figure 3 .

 3 Figure3. The performance of HAMCMC on a speech denoising application in terms of SDR (higher is better).

Figure 4 .

 4 Figure 4. The illustration of the data partitioning that is used in the distributed matrix factorization experiments. The numbers in the blocks denote the computer that stores the corresponding block.

Figure 5 .

 5 Figure 5. The performance of HAMCMC on a distributed matrix factorization problem.

The correction term presented in(Girolami & Calderhead,

2011) and[START_REF] Patterson | Stochastic gradient Riemannian Langevin dynamics on the probability simplex[END_REF] has a different form than Eq. 9.[START_REF] Xifara | Langevin diffusions and the Metropolisadjusted Langevin algorithm[END_REF] later showed that this term corresponded to a non-Lebesgue measure and Eq. 9 should be used instead for the Lebesgue measure.

The inverse of the FIM for this model can be precomputed. However, this will not be the case in more general scenarios. Therefore, for fair comparison we perform the matrix inversion and Cholesky decomposition operations at each iteration.

Acknowledgments

The authors would like to thank to Ş. İlker Birbil and Figen Öztoprak for fruitful discussions on Quasi-Newton methods. The authors would also like to thank to Charles Sutton for his explanations on the Ensemble Chain Adaptation framework. This work is partly supported by the French National Research Agency (ANR) as a part of the EDISON 3D project (ANR-13-CORD-0008-02). A. Taylan Cemgil is supported by TÜB İTAK 113M492 (Pavera) and Bogaziçi University BAP 10360-15A01P1.


Claire Arnaud

Pauline Béguin

Patrick Lévy

Jean-Louis Pépin

Normoxic recovery reverses intermittent hypoxia-induced systemic and vascular inflammation Comments on: Intermittent hypoxia-induced cardiovascular remodeling is reversed by normoxia in a mouse model of sleep apnea, by Castro-Grattoni et al 1

teaching and research institutions in France or abroad, or from public or private research centers.

Normoxic recovery reverses intermittent hypoxia-induced systemic and vascular inflammation

Comments on: Intermittent hypoxia-induced cardiovascular remodeling is reversed by normoxia in a mouse model of sleep apnea, by Castro-Grattoni et al

First, in Castro-Grattoni study [START_REF] Castro-Grattoni | Intermittent Hypoxia-Induced Cardiovascular Remodeling is Reversed by Normoxia in A Mouse Model of Sleep Apnea[END_REF] , animals were exposed to a 6 weeks IH exposure, followed by 6 weeks of normoxia. We previously demonstrated that only 14 days IH are enough to induce the same vascular remodeling, with increased intima-media thickness, elastin fiber network disorganization and mucoid deposition [START_REF] Arnaud | The inflammatory preatherosclerotic remodeling induced by intermittent hypoxia is attenuated by RANTES/CCL5 inhibition[END_REF] . Therefore, more than the duration of IH exposure, we believe that the kinetics of hypoxia/re-oxygenation cycles, as well as the severity of hypoxia represents the main triggers explaining IH-induced deleterious effects.

Second, the authors mentioned that aortic wall remodeling is "the result of multiple interactions between intermediary mechanisms, including oxidative stress, systemic and tissue inflammation", but they do not investigate the impact of IH removal on these parameters. In previous studies, we indeed demonstrated that inflammation plays a major role in the IHinduced vascular remodeling and atherosclerosis [START_REF] Arnaud | The inflammatory preatherosclerotic remodeling induced by intermittent hypoxia is attenuated by RANTES/CCL5 inhibition[END_REF][START_REF] Gras | Endothelin-1 mediates intermittent hypoxia-induced inflammatory vascular remodeling through HIF-1 activation[END_REF][START_REF] Poulain | Toll-like receptor-4 mediated inflammation is involved in the cardiometabolic alterations induced by intermittent hypoxia[END_REF][START_REF] Arnaud | Inflammation contributes to the atherogenic role of intermittent hypoxia in apolipoprotein-E knock out mice[END_REF][START_REF] Gautier-Veyret | Intermittent hypoxia-activated cyclooxygenase pathway: role in atherosclerosis[END_REF][START_REF] Poulain | Visceral white fat remodelling contributes to intermittent hypoxia-induced atherogenesis[END_REF] . IH-induced inflammation has been evidenced by increased splenocyte migration capacities, expression of chemokines and increased leucocyte rolling at the systemic level and by an elevated expression of the proinflammatory transcription factor NF-kB, chemokine expression and increased infiltration of lymphocytes in the arterial wall (i.e. aorta) (Arnaud et al [START_REF] Arnaud | The inflammatory preatherosclerotic remodeling induced by intermittent hypoxia is attenuated by RANTES/CCL5 inhibition[END_REF] and Figure 1). In accordance with the study of Castro-Grattoni et al 1 , we have also observed a beneficial effect of IH exposure cessation on these inflammatory markers. After only few days of return to a normoxic situation, proliferative capacities of splenocytes, splenic chemokine expressions and aortic expression of NF-kB were indeed normalized (Figure 1). These experiments in rodents are reflecting the effects of relatively short exposure to IH before irreversible lesions of the vasculature. Taken together, the study of Castro-Grattoni et al 1 , and our additional results strongly support the high interest to early diagnose and alleviate IH in OSA patients, in order to limit cardiovascular complications.

Figure legend

 legend Figure legendSplenic chemokine mRNA expressions (A); splenocyte proliferative capacities in response to increasing doses of concanavalin A (Con-A) (B) and aortic NF-kB protein expression (C). All these experiments were realized on tissues from mice exposed to either 14 days intermittent hypoxia (IH) or normoxia and 14 days IH or N, followed by 7 days normoxic recovery. (n=5-10 per group; *P<0.05 versus N). Data already published in AJRCCM by Arnaud et al 2 .


Jay Young

Valerio Basile

Lars Kunze

Elena Cabrio

Nick Hawes

Towards Lifelong Object Learning by Integrating Situated Robot Perception and Semantic Web Mining

Autonomous robots that are to assist humans in their daily lives are required, among other things, to recognize and understand the meaning of task-related objects. However, given an open-ended set of tasks, the set of everyday objects that robots will encounter during their lifetime is not foreseeable. That is, robots have to learn and extend their knowledge about previously unknown objects on-the-job. Our approach automatically acquires parts of this knowledge (e.g., the class of an object and its typical location) in form of ranked hypotheses from the Semantic Web using contextual information extracted from observations and experiences made by robots. Thus, by integrating situated robot perception and Semantic Web mining, robots can continuously extend their object knowledge beyond perceptual models which allows them to reason about task-related objects, e.g., when searching for them, robots can infer the most likely object locations. An evaluation of the integrated system on long-term data from real office observations, demonstrates that generated hypotheses can effectively constrain the meaning of objects. Hence, we believe that the proposed system can be an essential component in a lifelong learning framework which acquires knowledge about objects from real world observations.

Introduction

It is crucial for autonomous robots working in human environments such as homes, offices or factories to have the ability to represent, reason about, and learn new information about the objects in their environment. Current robot perception systems must be provided with models of the objects in advance, and their extensibility is typically poor. This includes both perceptual models (used to recognise the object in the environment) and semantic models (describing what the object is, what it is used for etc.). Equipping a robot a priori with a (necessarily closed) database of object knowledge is problematic because the system designer must predict which subset of all the different domain objects is required, and then build all of these models (a time-consuming task). If a new object appears in the environment, or an unmodelled object becomes important to a task, the robot will be unable to perceive, or reason about, it. The solution to this problem is for the robot to learn on-line about previously unknown objects. This allows robots to autonomously extend their knowledge of the environment, training new models from their own experiences and observations. The online learning of perceptual and semantic object models is a major challenge for the integration of robotics and AI. In this paper we address one problem from this larger challenge: given an observation of a scene containing an unknown object, can an autonomous system predict the semantic description of this object. This is an important problem because online-learnt object models ( [START_REF] Faeulhammer | Autonomous learning of object models on a mobile robot[END_REF]) must be integrated into the robot's existing knowledge base, and a structured, semantic description of the object is crucial to this. Our solution combines semantic descriptions of perceived scenes containing unknown objects, with a distributional semantic approach which allows us to fill gaps in the scene descriptions by mining knowledge from the Semantic Web. Our approach assumes that the knowledge onboard the robot is a subset of some larger knowledge base, i.e. that the object is not unknown beyond the robot's pre-configured knowledge. To determine which concepts from this larger knowledge base might apply to the unknown object, our approach exploits the spatio-temporal context in which objects appear, e.g. a teacup is often found next to a teapot and sugar bowl. These spatio-temporal co-occurrences provide contextual clues to the properties and identity of otherwise unknown objects.

This paper makes the following contributions:

• a novel distributional semantics-based approach for predicting both the semantic identity of an unknown, everyday object based on its spatial context and its most likely location based on semantic relatedness; • an extension to an existing semantic perception architecture to provide this spatial context; and • an evaluation of these techniques on real-world scenes gathered from a long-term autonomous robot deployment.

The remainder of the paper is structured as follows. In Section 2, we first state the problem of acquiring semantic descriptions for unknown objects and give an overview of our approach. We then discuss related work in Section 3. In Section 4, we describe the underlying robot perception system and explain how it is integrated with a Semantic Web mining component. Section 5 describes how the component generates answers/hypotheses to web-queries from the perception module. In Section 6, we describe the experimental setup and present the results. Before we conclude in Section 8, we provide a detailed discussion about our approach in Section 7. We also make available our data set and software source code for the benefit of the community at: http://github.com/aloof-project/ Room kitchen Surface coutertop Furniture refrigerator, kitchen cabinet, sink Small Objects bowl, teabox, instant coffee, water boiler, mug

Problem Statement and Methodology

Problem Statement

The problem we consider in this work can be summarized as follows: Given the context of a perceived scene and the experience from previous observations, predict the class of an as 'unknown' identified object. The context of a scene can include information about the types and locations of recognized small objects, furniture, and the type of the room where the observation has been made.

In this paper we use the following running example (Figure 1) to illustrate the problem and our approach: While operating 24/7 in an office environment, a robot routinely visits the kitchen and scans all surfaces for objects. On a kitchen counter it finds several household objects: a bowl, a teabox, a box of instant coffee, and a water boiler. However, one of the segmented objects, a mug, cannot be identified as one of the known object classes. The robot's task is to identify the unknown object solely based on the context of the perceived scene and scenes that have been previously perceived and in which the respective object was identified.

The problem of predicting the class of an object purely based on the context can also be seen as top-down reasoning or top-down processing of information. This stands in contrast to data-driven bottomup processing where, for example, a robot tries to recognize an object based on its sensor data. In top-down processing, an agent, or the robot, has some expectations of what it will perceive based on commonsense knowledge and its experiences. For example, if a robot sees a fork and a knife close to each other, and a flat unknown object with a square bounding box next to them, it might deduce that the unknown object is probably a plate. In the following, we refer to this kind of processing which combines top-down reasoning and bottom-up perception as knowledge-enabled perception.

Systems such as the one described in this paper are key components of integrated, situated AI systems intended for life-long learning and extensibility. We currently develop the system with two main use-cases in mind, both stemming from the system's capability to suggest information about unknown objects based on the spatial context in which they appear. The first use case is as part of a crowdsourcing platform, allowing humans that inhabit the robot's environment to help it label unknown objects. Here, the prediction system is used to narrow down the list of candidate labels and categories to be shown to users to select from alongside images of unknown objects the robot has encountered. Our second use case will be to help form more informative queries for larger machine learning systems, in our case an image classification system trained on extensive, though categorised, image data from websites like Amazon. Here, having some hints as to an object's identity, such as a distribution over a set of possible labels or categories it might belong to or be related to, could produce a significant speed boost by letting the classification system know what objects it does not have to test against. In this case, we aim to use the system to help a robot make smarter, more informed queries when asking external systems questions about the world.

Our Approach

In this work we address the problem of predicting information about the class of an object based on the perceived scene context by mining the Semantic Web. The extracted scene context includes a list of recognized objects and their spatial relations among each other, plus additional information from a semantic environment map. This information is then used to mine potential object classes based on the semantic relatedness of concepts in the Web. In particular, we use DBpedia as a resource for object knowledge, and will later on use WordNet to investigate object taxonomies. The result of the web mining component is a ranked list of potential objects classes, expressed as DBPedia entries, which allows us access to further information beyond just the class of an object, such as categorical knowledge. An overview of the entire developed system is given in Figure 2.

Overall, we see our context-based class prediction approach as a means to restrict the number of applicable classes for an object. The aim of our knowledge-enabled perception system is not to replace a bottom-up perception system but rather to complement it as an additional expert. For example, in the context of a crowdsourcing-based labeling platform our system could generate label suggestions for users. Thereby labeling tasks can be performed in less time and object labels would be more consistent across users. Hence, we belief that our system provides an essential functionality in the context of lifelong object learning.

Before we present related work in Section 3 we briefly discuss various resources of object knowledge.

Resources for object knowledge To provide a common format for object knowledge, and to access the wide variety of structured knowledge available on the Web, we link the observations made by the robot to DBpedia concepts. DBpedia [START_REF] Bizer | DBpedia -a crystallization point for the web of data[END_REF] is a crowd-sourced community effort started by the Semantic Web community to extract structured information from Wikipedia and make this information available on the Web. DBpedia has a broad scope of entities covering different domains of human knowledge: it contains more than 4 million things classified in a consistent ontology and denoted by a URI-based Figure 2. System overview. The robot perception component identifies all object candidates within a scene. All object candidates that can be recognized are labled according their class, all remaining objects are labeled as 'unknown'. Furthermore, the component computes the spatial relations between all objects in the scene. Together with context information from a semantic environment map, the robot generates a query to a web service which is processed by the Semantic Web mining component. Based on the semantic relatedness of objects the component provides a ranked list of the potential classes for all unknown objects. reference of the form http://dbpedia.org/page/Teapot for the Teapot concept. DBpedia supports sophisticated queries (using an SQL-like query language for RDF called SPARQL) to mine relationships and properties associated with Wikipedia resources. We link the objects that the robot can encounter in natural environments to DBpedia concepts, thus exploiting this structured, ontological knowledge.

BabelNet [START_REF] Navigli | Babelnet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network[END_REF] is both a multilingual encyclopedic dictionary and a semantic network which connects concepts and named entities in a very large network of semantic relations (about 14 million entries). BabelNet covers and is obtained from the automatic integration of several resources, such as WordNet [START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF], Wiktionary and Wikipedia. Each concept contained in BabelNet is represented as a vector in a high-dimensional geometric space in the NASARI resource, that we use to compute the semantic relatedness among objects.

Related Work

To obtain information about unknown objects from the Web, a robot can use perceptual or knowledge-based queries. Future systems will inevitably need to use both. In this paper we focus on the knowledgebased approach, but this can be seen as complementary to systems which use image-based queries to search databases of labelled images for similarity, e.g. [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF].

Although the online learning of new visual object models is currently a niche area in robotics, some approaches do exist [START_REF] Faeulhammer | Autonomous learning of object models on a mobile robot[END_REF][START_REF] Finman | Toward lifelong object segmentation from change detection in dense rgb-d maps[END_REF]. These approaches are capable of segmenting previously unknown objects in a scene and building models to support their future re-recognition. However, this work focuses purely on visual models (what objects look like), and does not address how the learnt objects are described semantically (what objects are).

The RoboSherlock framework [START_REF] Beetz | Robosherlock: Unstructured information processing for robot perception[END_REF] (which we build upon, see Section 4.1) is one of the most prominent projects to add semantic descriptions to objects for everyday environments, but the framework must largely be configured a priori with knowledge of the objects in its environment. It does support more open ended performance, e.g. through the use of Google Goggles, but does not use spatial or semantic context for its Web queries, only vision. The same research group pioneered Web and cloud robotics, where tools such as KNOWROB [START_REF] Tenorth | KNOWROB-MAP -knowledge-linked semantic object maps[END_REF] (also used in RoboSherlock) both formalised robot knowledge and capabilities, and used this formal structure to exploit the Web for remote data sources and knowledge sharing. In a more supervised setting, many approaches have used humans to train mobile robots about new objects in their environment [START_REF] Gemignani | Living with robots: Interactive environmental knowledge acquisition[END_REF][START_REF] Song | Robot in a room: Toward perfect object recognition in closed environments[END_REF] and robots have also used Web knowledge sources to improve their performance in closed worlds, e.g. the use of object-room co-occurrence data for room categorisation in [START_REF] Hanheide | Exploiting probabilistic knowledge under uncertain sensing for efficient robot behaviour[END_REF].

The spatial organisation of a robot's environment has also been previously exploited to improve task performance. For example, [START_REF] Thippur | A comparison of qualitative and metric spatial relation models for scene understanding[END_REF][START_REF] Kunze | Combining top-down spatial reasoning and bottom-up object class recognition for scene understanding[END_REF] present a system in which the previous experience of spatial arrangements of desktop objects is used to refine the results of a noisy object categorisation system. This demonstrates the predictive power of spatial arrangements, which is something we also exploit in this paper. However this prior work matched between scenes in the same environment and input modality. In our work we connect spatial arrangements in the robot's situated experience to structured knowledge on the Web.

Our predictions for unknown objects rely on determining the semantic relatedness of terms. This is an important topic in several areas, including data mining, information retrieval and web recommendation. [START_REF] Schuster | Learning organizational principles in human environments[END_REF] applies ontology-based similarity measures in the robotics domain. Background knowledge about all the objects the robot could encounter, is stored in an extended version of the KNOWROB ontology. Then, WUP similarity [START_REF] Wu | Verbs semantics and lexical selection[END_REF] is applied to calculate relatedness of the concept types by considering the depth of the concepts and the depth of their lowest common super-concept in the ontology. [START_REF] José | Computing Semantic Relatedness using DBPedia[END_REF] presents an approach for computing the semantic relatedness of terms using ontological information extracted from DBpedia for a given domain, using the results for music recommendations. Contrary to these approaches, we compute the semantic relatedness between objects by leveraging the vectorial representation of the DBpedia concepts provided by the NASARI resource [START_REF] Camacho-Collados | Nasari: a novel approach to a semantically-aware representation of items[END_REF]. This method links back to earlier distributional semantics work (e.g. Latent Semantic Analysis [START_REF] Thomas | A solution to plato's problem: The latent semantic analysis theory of acquisition, induction, and representation of knowledge[END_REF]) with the difference that here concepts are represented as vectors, rather than words.

Situated Robot Perception

The RoboSherlock Framework

To be able to detect both known and unknown objects in its environment a robot must have perceptual capabilities. Our perception pipeline is based on the RoboSherlock framework [START_REF] Beetz | Robosherlock: Unstructured information processing for robot perception[END_REF], an open-source framework for implementing perception systems for robots, geared towards interaction with objects in human environments. The use of RoboSherlock provides us with a suite of vision and perception algorithms. Following the paradigm of Unstructured Information Man-agement (as used by the IBM Watson project), RoboSherlock approaches perception as a problem of content analysis, whereby sensor data is processed by a set of specialised information extraction and processing algorithms called annotators. The RoboSherlock perception pipeline is a sequence of annotators which include plane segmentation, RGB-D object segmentation, and object detection algorithms. The output of the pipeline includes 3D point clusters, bounding boxes of segmented objects (as seen in Figure 2), and feature vectors (colour, 3D shape and texture) describing each object. These feature vectors are important as they allow the robot to track unknown objects as it takes multiple views of the same scene. Though in this paper we work with a collected and annotated dataset, we do not require the segmentation or 3D object recognition steps RoboSherlock can provide via LINE-MOD-3D [START_REF] Hinterstoisser | Multimodal templates for real-time detection of texture-less objects in heavily cluttered scenes[END_REF], though this component is used in our full Robot and Simulated system where a range of perception algorithms are connected and used instead of dataset input. We make use of all other RoboSherlock capabilities the pipeline to process the data and provide a general architecture for our representation and extraction of historical spatial context, web query generation and the application of Qualitative Spatial Relations, which we will discuss in a following section.

Scene Perception

In this paper we assume the robot is tasked with observing objects in natural environments. Whilst this is not a service robot task in itself, it is a precursor to many other task-driven capabilities such as object search, manipulation, human-robot interaction etc. Similar to prior work (e.g. [START_REF] Schuster | Learning organizational principles in human environments[END_REF]) we assume that the robot already has a semantic map of its environment which provides it with at least annotations of supporting surfaces (desks, worktops, shelves etc.), plus the semantic category of the area in which the surface is located (office, kitchen, meeting room etc.). Surfaces and locations are linked to DBpedia entries just as object labels are, typically as entities under the categories Furniture and Room respectively.

From here, we have access to object, surface and furniture labels described by the data, along with 3D bounding boxes via 3D point data. In the kitchen scene the robot may observe various objects typical of the room, such as a refrigerator, a cabinet, mugs, sugar bowls or coffee tins. Their positions in space relative to a global map frame are recorded and we can then record the distance between objects, estimate their size (volume) and record information about their cooccurrences, and the surfaces upon which they were observed, by updating histograms attached to each object.

In the following we assume that each scene only contains a single unknown object, but the approach generalises to multiple unknown objects treated independently. Joint inference over multiple unknown objects is future work.

Spatial and Semantic Context Extraction

In order to provide additional information to help subsequent components predict the unknown object, we augment the scene description with additional spatial and semantic context information, describing the relationships between the unknown object and the surrounding known objects and furniture. This context starts from the knowledge we already have in the semantic map: labels for the room and surface the object is supported by.

We make use of Qualitative Spatial Relations (QSRs) to represent information about objects [START_REF] Frommberger | Structural knowledge transfer by spatial abstraction for reinforcement learning agents[END_REF]. QSRs discretise continuous spatial measurements, particularly relational information such as the dis-tance and orientation between points, yielding symbolic representations of ranges of possible continuous values. In this work, we make use of a qualitative distance measure, often called a Ring calculus. When observing an object, we categorise its distance relationship with any other objects in a scene with the following set of symbols: near 0 , near 1 , near 2 , where near 0 is the closest. This is accomplished by placing sets of thresholds on the distance function between objects, taken from the centroid of the 3D cluster. For example, this allows us to represent that the mug is closer to the spoon than the kettle (near 0 (mug, spoon) near 2 (mug, kettle)) without using floating-point distance values based on noisy and unreliable readings from the robot's sensors. The RoboSherlock framework provides a measure of the qualitative size of objects by thresholding the values associated with the volume of 3D bounding-boxes around objects as they are observed. We categorise objects as small, medium, large in this way, allowing the robot to represent and compare object sizes. Whilst our symbolic abstractions are currently based on manual thresholds, approaches exist for learning parametrisations of QSRs through experience (e.g. [START_REF] Young | Learning by observation using qualitative spatial relations[END_REF]) and we will try this in the future. For now, we choose parameters for our qualitative calculi tuned by our own knowledge of objects in the world, and how they might relate. We use near 0 for distances in cluster space lower than 0.5, near 1 for distances between than 0.5 and 1.0, near 2 for distances between 1.0 and 3.5 and near 3 for distances greater than 3.5.

As the robot makes subsequent observations, it may re-identify the same unknown object in additional scenes. When this happens we store all the scene descriptions together, providing additional context descriptions for the same object. In Figure 3 we show part of the data structure describing the objects that co-occured with a plate in a kitchen, and their most common qualitative spatial relations.

1 "co_occurrences": [ 2 ["Coffee", 0.5, "near_0" ],

3

["Kitchen_side", 1.0,"near_0" ],

4

["Kitchen_cabinet", 1.0,"near_1" ],

5

["Fridge", 0.625,"near_1" ],

6

["Teabox", 0.625,"near_0" ],

7

["Waste_container", 0.375,"near_2" ],

8

["Utensil_rack", 0.625, "near_1" ],

9

["Sugar_bowl_(dishware)", 0.625,"near_0" ] ,

10

["Electric_water_boiler", 0.875,"near_1" ],

11

["Sink", 0.625, "near_1" ] ],

12 "context_history": [ 13 ["Kitchen", 1.0, "Kitchen_counter",1 ],

14

[ "Office", 0.0,"Desk", 0 ]],

15 "context_room_label": "Kitchen",

16

"context_surface_label": "Kitchen_counter",

Semantic Web Mining

For an unknown object, our aim is to be able to provide a list of likely DBpedia concepts to describe it, and we will later consider and compare the merits and difficulties associated with providing object labels and object categories. As this knowledge is not available on the robot (the object is locally unknown), it must query an external data source to fill this knowledge gap. We therefore use the scene descriptions and spatial contexts for an unknown object to generate a query to a Web service. In return this service provides a list of the possible DBpedia concepts which may describe the unknown object. We expect the robot to use this list in the future to either automatically label a new object model, or to use the list of possible concepts to guide a human through a restricted (rather than open-ended) learning interaction.

The Web service provides access to object-and scene-relevant knowledge extracted from Web sources. It is queried using a JSON structure sent via an HTTP request (shown in Figure 2). This structure aggregates the spatial contexts collected over multiple observations of the unknown object. In our current work we focus on the co-occurrence structure. Each entry in this structure describes an object that was observed with the unknown object, the ratio of observations this object was in, and the spatial relation that most frequently held between the two. The room and surface fields describe where the observations were made.

Upon receiving a query, the service computes the semantic relatedness between each object included in the co-occurrence structure and every object in a large set of candidate objects from which possible concepts are drawn from (we discuss the nature of this set in Section 6).

This semantic relatedness is computed by leveraging the vectorial representation of the DBpedia concepts provided by the NASARI resource [START_REF] Camacho-Collados | Nasari: a novel approach to a semantically-aware representation of items[END_REF]. In NASARI each concept contained in the multilingual resource BabelNet [START_REF] Navigli | Babelnet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network[END_REF] is represented as a vector in a highdimensional geometric space. The vector components are computed with the word2vec [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF] tool, based on the cooccurrence of the mentions of each concept, in this case using Wikipedia as source corpus.

Since the vectors are based on distributional semantic knowledge (based on the distributional hypothesis: words that occurr together often are likely semantically related.), vectors that represent related entities end up close in the vector space. We are able to measure such relatedness by computing the inverse of the cosine distance between two vectors. For instance, the NASARI vectors for Pointing device and Mouse (computing) have relatedness 0.98 (on a continuous scale from 0 to 1), while Mousepad and Teabox are 0.26 related.

The system computes the aggregate of the relatedness of a candidate object to each of the scene objects contained in the query. Using relatedness to score the likely descriptions of an unknown object follows from the intuition that related objects are more likely than unrelated objects to appear in a scene, e.g., to identify a Teapot is more useful to know that there is a Teacup at the scene rather than a Desk.

Formally, given n observed objects in the query q 1 , ..., q n , and m candidate objects in the universe under consideration o 1 , ..., o m ∈ O, each o i is given a score that indicates its likelihood of being the unknown object by aggregating its relatedness across all observed objects. The aggregation function can be as simple as the arithmetic mean of the relatedness scores, or a more complex function. For instance, if the aggregation function is the product, the likelihood of an object o i is given by:

likelihood(oi) = n j=1 relatedness(o i , q j )
For the sake of this work, we experimented with the product as aggregating function. This way of aggregating similarity scores gives higher weight to highly related pairs, as opposed to the arithmetic mean, where each query object contributes equally to the final score. The idea behind this choice is that if an object is highly related to the target it should be regarded as more informative.

The information carried by each query is richer than just a bare set of object labels. One piece of knowledge that can be exploited to obtain a more accurate prediction is the relative position of the observed objects with respect to the target unknown object. Since this information is represented as a discrete level or proximity (from near 0 to near 3), we can use this as a threshold to determine whether or not an object should be included in relatedness calculation. In this work we discard any object related by near 3, based on the intuition that the further away an object is spatially, the less related it is. Section 6.2 includes an empirical investigation into approach.

For clarity, here we present an example of execution of the algorithm described above on the query corresponding to the kitchen example seen throughout the paper. The input to the Web module is a query containing a list of pairs (object, distance): (Refrigerator, 3), (Kitchen cabinet, 3), (Sink, 3), (Kitchen cabinet, 3), (Sugar bowl (dishware), 1), (Teabox, 1), (Instant coffee, 2), (Electric water boiler, 3). For the sake of readability, let us assume a set of candidate objects made only of three elements: Tea cosy, Pitcher (container) and Mug. Table 1 show the full matrix of pairwise similarities. 1. Object similarity of the three candidates Tea cosy, Pitcher (container) and Mug to the objects observed at the example kitchen scene. The last line shows the similarity scores aggregated by product.

Among the three candidates, the one with highest aggregated score is Tea cosy, followed by Mug and Pitcher (container). For reference, the ground truth in the example query is Mug, that ended up second in the final ranking returned by the algorithm.

We can also alter the performance of the system using the frequency of the objects returned by the query. The notion of frequency, taken from [START_REF] Daiber | Improving efficiency and accuracy in multilingual entity extraction[END_REF], is a measure based on the number of incoming links in the Wikipedia page of an entity. Using this measure we can choose to filter uncommon objects from the results of the query, by thresholding with a given frequency value. In the example above, the frequency counts of Tea cosy, Pitcher (container) and Mug are respectively 25, 161 and 108. Setting a threshold anywhere between 25 and 100 would filter Tea cosy out of the result, moving up the ground truth to rank 1. Similarly, we can filter out objects that are too far from the target by imposing a limit on their observed distance. A threshold of 2 (inclusive) for the distance of the objects in the example would exclude Refrigerator, Kitchen cabinet, Sink and Electric water boiler from the computation.

Other useful information available from the spatial context includes the label of the room, surface or furniture where the unknown was observed. Unfortunately, in order to leverage such information, one needs a complete knowledge base containing these kind of relations, and such a collection is unavailable at the moment. However, the room and the surface labels are included in the relatedness calculations along with the observed objects.

Experiments

In order to evaluate the effectiveness of the method we propose in predicting unknown objects' labels, we perform some experimental tests. In this section we report on the experimental setup and the results we obtained, before discussing them in further detail.

Experimental Set-up

Our experimental evaluation is an experiment based on a collection of panoramic RGB-D scans taken from an autonomous mobile service robot deployed in a working office for a month. It took these scans at fixed locations according to a flexible schedule. After the deployment we annotated the objects and furniture items in these sweeps, providing each one with a DBpedia concept. This gives us 1329 real world scenes (384 kitchen, 945 office) on which we can test our approach. From this data, our evaluation treats each labeled object in turn as an unknown object in a leave-one-out experiment, querying the Web service with the historical spatial context data for the unknown object similar to that shown in Figure 3. In all of the experiments we compare the ground truth (known label in the data) to the DBpedia concepts predicted by our system. We measure performance based on two metrics. The first WUP similarity measures the semantic similarity between the ground truth and the concept predicted as most likely for the unknown object. The second measure is the ranking of the ground truth in the list of suggested concepts.

For the experiments, the set of candidate objects (O in Section 5) was created by adding all concepts from the DBpedia ontology connected to the room types in our data by up to a depth of 3. For example, starting from office leads us to office equipment, computers, stationary etc. This resulted in a set of 1248 possible concepts. We set the frequency threshold to 20, meaning we ignored any suggest concept which had a frequency value lower than this. This means uncommon concepts such as Chafing dish (frequency=13) would always be ignored if suggested, but more common ones such as Mouse (computing) (frequency=1106) would be kept. Figure 5 shows the result of calculating the WUP similarity [START_REF] Wu | Verbs semantics and lexical selection[END_REF] between the WordNet synsets of the ground truth and the top-ranked result from our semantic web-mining system. WUP measures semantic relatedness by considering the depth of two synsets in addition to the depth of their Lowest Common Subsumer (LCS). This means that large leaps between concepts will reduce the eventual similarity score more than small hops might. To do this we used ready available mappings to link DBPedia concepts in our system to WordNet synsets, which are themselves organised as a hierarchy of is-a relations. This is in contrast to DBPedia, which is organised as a directed acyclic graph, and while that still means that we could apply the WUP measure to DBPedia nodes directly, WordNet offers a more structured taxonomy of concepts that is more well-suited to this kind of work. This serves to highlight the importance of a multi-modal approach to the use of such ontologies. In the results, the system predicted Lightpen when the ground truth was Mouse producing a WUP score of 0.73, with the LCS being the Device concept, with Mouse and Lightpen having depth 10 and 11 respectively, and Device having depth 8 measured from the root node of Entity. In this case, the system suggested an object that fell within 3 concepts of the ground truth, and this is true for the majority of the results in 5. However, in the case of ref rigerator as the ground truth, the system suggests keypad as the highest ranked result, producing a WUP score of 0.52. Here, the LCS is at depth 6 with the concept Artif act, the ground truth ref rigerator is at depth 13 and the prediction keypad is at depth 10. While in this case the node distance between the LCS and the prediction is 4, where in the previous example it was 3, the WUP score is much worse here (0.73 vs 0.52) as there are more large leaps across conceptual space. Our best result in this experiment is for P rinter as the ground truth, for which the system suggests keypad again, however the LCS here is the peripheral node at depth 10, where printer is at depth 11 and keypad is at depth 12. The system suggests a range of objects that are closely related to the unknown object, inferred only from its spatial context and knowledge of the objects and environment around it. From here this allows us to generate a list of candidate concepts which we can use in a second stage of refinement, such as by presentation to a human-in-loop.

Results

Figure 6 shows how frequency thresholding effects the performance of the system. In this experiment we consider the position in the ranked result of the first object with an immediate parent DB-Pedia category in common with the ground truth. Doing so essentially maps the larger set of object labels to a smaller set of object categories. This is in contrast to considering the position in the result of the specific ground truth label, as shown in Figure 7, and allows us to generate a ranking over categories of objects. To ensure categories remain relevant to the situated objects we are interested in, we prune a number DBPedia categories such as those listing objects invented in certain years, or in certain countries. We regard these as being overly broad, and provide a more abstract degree of semantic knowledge about objects than we are interested in. As such, we retrieve the rank-in-result of the first object that shares an immediate DBPedia category with the ground truth, which in the case of Electric water boiler turns out to be Samovar, a kind of Russian water boiler, as both share the immediate ancestor category Boilers (cookware). The Samovar, and thus the boiler category, appears at rank 12, whereas the specific label Electric water boiler appears near the end of the result set of 1248 objects, which covers 641 unique DBPedia categories. In our results, categories associated with 9 of the 16 objects (56%) appear within the result's top 10 entries. Here as we filter out uncommon words by increasing the filter threshold T we improve the position of the concept in the list. Whilst this allows us to definitely remove very unlikely answers that appear related due to some quirk of the data, the more we also start to reduce the ability of the robot to learn about certain objects. This is discussed further in Section 7.

Unlike WordNet synsets and concepts, DBPedia categories are more loosely defined and structured, being generated from WikiPedia, but this means they are typically richer in the kind of semantic detail and broad knowledge representation that may be more suitable for presentation to humans, or more easily mapped to human-authored domains. While WordNet affords us access to a well-defined hierarchy of concepts, categories like device and container are fairly broad, whereas DBPedia categories such as V ideo game control methods or Kitchenware describe a smaller set of potential objects, but may be more semantically meaningful when presented to humans.

Discussion

Overall, whilst the results of our object category prediction system show that it is possible for this novel system to generate some good predictions, the performance is variable across objects. There are a number of factors that influence performance, and lead to this variability. The first issue is that the current system does not rule out suggestions of things it already knows. For example if the unknown object is a keyboard, the spatial context and relatedness may result in a top suggestion of a mouse, but as the system already knows about that, it is probably a less useful suggestion. However, it is possible that the unknown object could be a mouse, but has not been recognised correctly. Perhaps the most fundamental issue in the challenge of predicting objects concepts from limited information is how the limit the scope of suggestions. In our system we restricted ourselves to 1248 possible concepts, automatically selected from DBpedia by ontological connectivity. This is clearly a tiny fraction of all the possible objects in existence. On one hand this means that our autonomous robot will potentially be quite limited in what it can learn about. On the other hand, a large number of this restricted set of objects still make for highly unlikely suggestions. One reason for this is the corpus-based automatically-extracted nature of DBpedia, which means that it includes interesting objects which may never be observed by a robot (e.g. Mangle (machine)). More interestingly though is the effect that the structure of the ontology has on the nature of suggestions. In this work we have been using hierarchical knowledge to unpin our space of hypotheses (i.e. the wider world our robot is placed within), but have not addressed this within our system. This leads to a mismatch between our expectations and the performance of the system with respect to arbitrary precision. For example, if the robot sees a joystick as an unknown object, an appropriate DBpedia concept would seem (to us) to be Controller (computing) or Joystick. However, much more specific concepts such as Thrustmaster and Logitech Thunderpad Digital are also available to the system in its current form. When learning about an object for the first time, it seems much more useful for the robot to receive a suggestion of the former kind (allowing it to later refine its knowledge to locally observable instances) than the latter (which unlikely to match the environment of the robot). Instead, returning the category of the ranked objects our system suggests allows us to go some way towards this as shown in Figure 6, but still provides us a range of possible candidate categories -though narrowed down from 641 possible categories, to in some cases less than 5. As such, from here we can switch to a secondary level of labelling: that of a human-in-loop. We will next integrate the suggestion system with a crowd-sourcing platform, allowing humans that inhabit the robot's environment to help it label unknown objects. The suggestion system will be used to narrow down the list of candidate categories that will be shown to users as they provide labels for images of objects the robot has seen and learned, but has not yet labelled. While further work is necessary to refine the current 56% of objects that have a category in the top-10 ranked result, we expect that the current results will be sufficient enough to allow a human to pick a good label when provided a brief list of candidates and shown images of the unknown objects. Such systems are crucial for life-long situated learning for mobile robot platforms, and will allow robot systems to extend their world models over time, and learn new objects and patterns.

The issue of how to select which set of possible objects to draw suggestions from is at the heart of the challenge of this work: make the set too large and it is hard to get good, accurate suggestions, but make it too small and you risk ruling out objects that your robot may need to know about. Whilst the use of frequency-based filtering improved our results by removing low-frequency outliers, more semantically-aware approaches may be necessary to improve things further. Further improvements can be made, for instance we largely do not use current instance observations about the object, but prefer its historical context when forming queries. This may be the wrong thing to do in some cases, in fact it may be preferable to weight observations of object context based on their recency. The difference between historical context and the context of an object in a particular instance may provide important contextual clues, and allow us to perform other tasks such as anomaly detection or boost the speed of object search tasks.

One issue we believe our work highlights is the need to integrate a multi-modal approach to the use of differing corpora and ontologies. For instance, the more formal WordNet hierarchy was used to calculate the semantic relatedness of our experiment results, rather than the less formal DBPedia ontology. However we hold that the DBPedia category relationships are more useful in the human-facing component of our system. There exist other ontologies such as YAGO which integrates both WordNet and DBPedia, along with its own category system, that will certainly be of interest to us in the future as we seek to improve the performance of our system. One of our primary goals is to better exploit the hierarchical nature of these ontologies to provide a way of retrieving richer categorical information about objects. While reliably predicting the specific object label from spatial context alone is difficult, we can provide higher-level ancestor categories that could be used to spur further learning or improve previous results. As such, we view the prediction process as one of matching the characteristics of a series of increasingly more specific categories to the characteristics of an unknown object, rather than immediately attempting to match the specific lowest-level characteristics and produce the direct object label. This requires an ontology both formally-defined enough to express a meaningful hierarchy of categories for each item, and broad enough to provide us mapping to a large set of common-sense categories and objects. It is not clear yet which combination of existing tools will provide the best route to accomplishing this.

Conclusions

In this paper we presented an integrated system for solving a novel problem: the suggestion of concept labels for unknown objects observed by a mobile robot. Our system stores the spatial contexts in which objects are observed and uses these to query a Web-based suggestion system to receive a list of possible concepts that could apply to the unknown object. These suggestions are based on the relatedness of the objects observed with the unknown object, and can be improved by filtering the results based on both frequency and spatial proximity. We evaluated our system data from real office observations and demonstrated how various filter parameters changed the match of the results to ground truth data.

We showed that the suggestion systems provides object label suggestions with a reasonably high degree of semantic similarity, as measured by WUP similarity on WordNet synsets. We also achieved success in retrieving the categories of objects, rather than their direct labels. In the future we will explore the hierarchical nature of the knowledge used for object concept suggestions, explore different corpora and ontologies to base the suggesting system on, and perform a situated evaluation of our system on a mobile robot with additional perceptual learning capabilities, and crowd-sourcing functionality to label objects on-line with the help of humans using the suggestion system.

The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under ALOOF project (CHIST-ERA program)

Figure 1 .

 1 Figure 1. Perceived and interpreted kitchen scene, with various objects.

Figure 3 .

 3 Figure 3. An example data fragment taken from a series of observations of a Plate in a series of kitchen scenes, showing object, furniture, room and surface co-occurence

Figure 4 .

 4 Figure 4. An example office scene as an RGB image from our real-world deployment. Our data contains 945 office scenes, and 384 kitchen scenes.

Figure 5 .

 5 Figure 5. WUP similarity measure between WordNet synsets of ground truth and top-ranked result, with t = 50, p = 2 using the prod method. Ranks closer to 1 are better. Values closer to 1 indicate similarity, and values closer to 0 indicate dissimilarity.

Figure 6 .

 6 Figure 6. Rank in result by object category, matching the highest ranked object with a category shared with the ground truth in the result set, with varying values of the parameter t, with p = 2 and the prod method. Ranks closer to 1 are better. Ranking is determined by the position in the result of the first object with an immediate category in common with the ground truth. 56% (9/16) achieve <= 10.

Figure 7 .

 7 Figure 7. Rank in result by object label, matching the label of the ground truth in the result set, with varying values of the parameter t, with p = 2 and the prod method. Increasing values of T can cause some objects to be excluded from the result set entirely, such as the Teaware or Monitor at T=50

  Statistics on WUP and Rank-in-result data, both for t = 50, p = 2 using prod

		Mean Median Std. Dev Variance Range
	WUP	0.69	0.70	0.12	0.01	0.43
	Category Rank 17.00 9.50	20.17	407.20	73.00
	Object Rank	50.93 36.5	50.18	2518.32	141
	Figure 8.

Intelligent Robotics Lab, School of Computer Science, University of Birmingham, United Kingdom, {j.young, l.kunze, n.a.hawes}@cs.bham.ac.uk

[START_REF] Bizer | DBpedia -a crystallization point for the web of data[END_REF] INRIA Sophia Antipolis Méditerranée, Sophia Antipolis, France, {valerio.basile, elena.cabrio}@inria.fr

J.Young et al. / Towards Lifelong Object Learning by Integrating Situated Robot Perception and Semantic Web Mining