H Boutayeb
email: halim.boutayeb@univ-rennes1.fr

T Brillat

J P Daniel

F Gadot

P Y Garel

A De Lustrac
email: andre.delustrac@ief.u-psud.fr

K Mahdjoubi
email: kouroch.mahdjoubi@univ-rennes1.fr

P Ratajczak
email: philippe.ratajczak@francetelecom.com

A RECONFIGURABLE ELECTROMAGNETIC BANDGAP STRUCTURE FOR A BEAM STEERING BASE STATION ANTENNA

INTRODUCTION

The purpose of this communication is to present the works of a French Industry and Research sponsorized project (RNRT Project) named "BIP" [1]. The goal of this project was to design a beam steering multi-band (GSM/DCS/UMTS) base station antenna. After a presentation of the different partners, we will show how we would solved the problem of the beam steering antenna with a controllable Electromagnetic BandGap (EBG) structure and we will present the results of simulations and experiments in order to validate the concept.

"BIP" PROJECT PRESENTATION

The RNRT project was started in 2001 with 5 partners: In this project, we purposed to manage the coverage (single beam or multi-beam) of a base station for mobile communications with a reconfigurable EBG material. The use of this kind of structure for this application must solved different problems like:

• the design of a wide or multi-band controllable EBG material • the capabilities to control the radiation over 360° in the azimuth plane (the maximum of radiation in the elevation plane stay in the 90° direction), • the matching of the antenna

Home Home

A RECONFIGURABLE EBG MATERIAL

For our application, the EBG structure must have the same electromagnetic behavior for the different frequency bands: GSM, DCS and UMTS.

In order to control the EBG material and to manufacture the structure, we choose a lattice of metallic wires that has a wide Electromagnetic BandGap starting from 0 GHz to a frequency depending on the geometrical parameters of the lattice.

To manage the radiation of the antenna, we choose to control the behavior of the EBG material between to complementary state like a lattice of long metallic wires (fig. 1) without transmission in the frequency range 0 to 20 GHz and a lattice of discontinuous metallic wires with transmission in the same band .

If we inserted diodes between the discontinuous wires [2], we can control the state of the EBG structure as we can see on the figure 2: • when the diodes are on: the discontinuous metallic wires are equivalent to long wires thanks to the low impedance and capacitance of the diodes, and the lattice is like a reflector in the frequency range 0-15 GHz • when the diodes are off: the wires stay discontinuous because the diodes have high impedance and the lattice is transparent in the frequency range 0-5 GHz .

The bandwidth of the controllable EBG material is depending on the geometrical parameters of the lattice and the length of the discontinuous part of the wires that must be small toward wavelenght. The choice of PIN diodes was made in order to obtain a very low impedance and capacitance when the diodes are on.

Home Home

THE BEAM STEERING

The square lattice the controllable EBG material is transform to a cylindrical one in the center of it we have placed a omni-directional probe [START_REF] Boutayeb | Etude des structures périodiques planaires et conformes associées aux antennes. Application aux communications mobiles[END_REF]. The control of the coverage is made through the bias of the diodes. The figure 3 shows the electric field in different cases of angular sector of diodes off. We can see that:

• when the diodes are on: the angular sectors are like reflectors,

• for the other sectors where the diodes are off, the EBG material is transparent,

• we can choose the azimuth angle, the beamwidth and manage single or multi-beam coverage.

The matching of this structure: cylindrical EBG material associated to a omni-directional probe in the center is difficult because the reflector behavior of the EBG structure, when the diodes are on, reflects the radiation of the probe. So the radiation go back through the probe and dismatches the input impedance of the antenna.

Different distributions of the cylindrical lattice are possible (fig. 4) like:

• a azimuthally distribution with a constant angle that allows to design a simple control system of the beam steering because a constant number of wire on each cylindrical layer • a distribution with a constant azimuth step where the beam control system is more complex because each must be controlled independently but allows to match the antenna more easily.

The distribution of the cylindrical lattice has been optimized [3] taking into account that the number of cylindrical layers is fixed by the beam shape, the level of back radiation and the input impedance of the antenna.

EVALUATION OF THE PERFORMANCES

In order to estimate the electromagnetic characteristics of the EBG structure to control the coverage of the base station antenna, we develop two breadboards:

• the first one to evaluate the control principle with the EBG material by the design of a single layer of discontinuous metallic wires with diodes • the second without electronically control but with a four layers of EBG structure of continuous metallic wires to evaluate the EM performances: input impedance, capabilities of the single or multi-beam coverage.

Performances of the control principle

The breadboard has been realized in Advanten's metallized foam

The probe is a monopole on a ground plane (fig. 5) inserted in a foam cylinder of 100 mm radius and a r = 1.2 with a metallic plate on the top. The discontinuous wires with 6 diodes are placed on the exterior face of the cylinder and spaced by 15°, this number and this spacing have been optimized in order to keep the control and minimize the cost. So there are 144 diodes on this breadboard.

The design of the antenna has been made with a FDTD software and Ansoft HFSS code. A single layer of metallic wires don't allow to match the antenna in the all frequency band (fig. 6) when 6 contiguous wires are open (diodes off) equivalent to a 90° aperture in the EBG structure. The measured reflection coefficient is presented fig. 6. We can see some differences due to feeding kind: lumped feed for the simulations and a waveguide feeding for the experiment.

The simulated radiation patterns for different frequencies are presented fig. 7. We can see that the maximum of radiation is not in the = 90° direction because a reduced ground plane.

The radiation patterns at 1.7 GHz are presented fig. 8 for different configurations of the diodes: 6 wires open in the azimuth direction +90°, -90° and ±90°. The radiation patterns in E and E polarization are plotted in a 2D polar representation where the axis agrees to = 0° and the exterior circle = 180°. We can see a small dissymmetry on the back radiation between the +90° and -90° configuration certainly due to the manufacturing (soldering, ...).

The experiments show the capabilities of the beam steering with a cylindrical EBG material associated to a omnidirectional probe in the center.

Performances of the beam steering base station

The base station antenna was design with SR3D [4]. The cylindrical EBG material is composed by 4 layers with a constant azimuthally step distribution. For this antenna, we didn't take into account diodes in the EBG material. the structure is modelized with only continuous and discontinuous wires.

On the fig. 9, we can the simulated radiation patterns for different configuration of the EBG material in order to obtain a single or multi-beam coverage. The maximum of radiation in the main polarization (E ) is in the = 90° direction and the level of cross-polarization is below -15 dB for the upper bands and below -10 dB for the GSM band (not presented).

For the experiment, we put and remove the long metallic wires depending the configuration of the EBG material, the discontinuous wires didn't have been manufacturing. So in order to compare experiments and simulations, we have realized new simulation in the same geometrical configurations without discontinuous wires.

When the EBG material is open in a aperture of 60°, we can see that the input impedance (fig. 10) is well predicted with SR3D. the simulated S.W.R. (red symbols) is comparable to the measured one (blue line). there is a frequency shift of 20 MHz on the resonance position. A optimization of the imput impedance is possible and is shown with the green line.

For the same aperture (60°) of the EBG material, the radiation patterns in the E polarization are presented fig. 11 at 0.9, 1.75 and 2 GHz. The comparizon between experiment and simulation is excellent. the difference for the 2 GHz pattern is due to the frequency shift. The manufacturing of the complete structure with 4 layers of controllable EBG material will allow to validate the concept of this antenna and the use of this technology in term of electromagnetic performances (input impedance, radiation pattern, losses, ...) for the application of base station antenna.

• 3

 3 french universties laboratories: • IEF (Institut d'Electronique Fondamentale),University of PARIS XI • GEA (Groupe d'Electronique Appliquée), University of PARIS X, • IETR (Institut d'Electronique et de Telecommunication de Rennes), University of RENNES 1, • Antenna Department of France Telecom R&D, • Advanten: an antennas & radio applications compagny.

fig. 2 :

 2 fig. 1: Examples of transmission coefficients of continuous and discontinuous metallic wires

fig. 3 :

 3 fig. 3: Electric field maps

  fig. 5: Technologic breadboard

fig. 9 :CONCLUSION

 9 fig. 9: Simulated radiation patterns of the base station antenna -F = 1.8 GHz


H Boutayeb
email: halim.boutayeb@univ-rennes1.fr

K Mahdjoubi

A C Tarot

MATCHING OF AN ANTENNA PUT INSIDE A PLANAR EBG STRUCTURE

The purpose of this presentation is to propose a method to design a directive and matched antenna with a planar Electromagnetic Band Gap (EBG) structure. The EBG structure of our example consist on metallic wires. This study use the FDTD method and analytical formulas.

I. INTRODUCTION

Several recent works concern periodic structures associated with microwave antennas to enhance there directivity [START_REF] Thevenot | Directive Photonic Band-Gap Antennas[END_REF][2][3] [START_REF] Boutayeb | EBG Antenna analysis/Unification of frequency and angular dependencies[END_REF]. However, to our knowledge, the impedance aspect is not enough studied. The objective of this presentation is to propose a method to match an antenna put inside a planar EBG structure. Before inserting a real antenna inside the EBG structure, we present a study of the angular filtering characteristics of the EBG structure and the input impedance with an excitation by a line source.

II. PLANE WAVES AND INFINITE LONG METALLIC WIRES : ANGULAR FILTERING

We first interest on the angular filtering aspect due to the EBG structure composed of two layers of metallic wires on each side of the excitation (Figure 1).

Let us call T 2*2 the transmission coefficient obtained with an excitation by plane waves (Figure 1). T 2*2 is function of the frequency 'f' and the angular incidence 'θ'. We obtain this coefficient (T 2*2 ) using (r, t), the complex reflection and transmission coefficients of one surface of metallic wires. To simplify the study we don't consider the angular dependency of (r, t). (r, t) are calculated by the FDTD method. The coefficient T 2*2 (kD') can be written in a simple closed form [START_REF] Boutayeb | EBG Antenna analysis/Unification of frequency and angular dependencies[END_REF][5] :

( ) ( ) ( ) ( ) ( ) ' jkD exp ' kD r 1 2 / ' jkD exp ' kD t ' kD T 2 2 2 * 2 - - - = with ( ) ( ) ( ) ( ) ( ) ' D 2 jk exp k r 1 ' jkD exp k t ' kD t 2 2 2 - - - = , ( ) ( ) ( ) ( ) ( )         - - - + = ' D 2 jk exp k r 1 ' D 2 jk exp k t 1 ) k ( r ' kD 2 2 2 r
k is the free space wave number and D'=Dcos(θ). Figure 2 gives the transmission coefficient |T 2*2 | versus the frequency at the normal incidence (θ=0°). In this figure, is also represented the Gap Bands and the Pass Bands. We call f 0 the frequency corresponding to the first resonance. Figure 3 gives |T 2*2 | versus the incidence angle at the different frequencies represented in Figure 2. These curves can be assimilated as radiation patterns. Until the first resonance f 0 , the patterns have only one lobe at the normal, which is an objective for a directive antenna. At a frequency higher than f 0 the patterns have multiple lobes one each sides of the normal. Figure 3 More details on the study of angular filtering and directivity of the structure can be found in ref. [START_REF] Boutayeb | Etude des structures périodiques planaires et conformes associées aux antennes. Application aux communications mobiles[END_REF], and will be presented during the presentation.

III. LINE SOURCE AND INFINITE LONG METALLIC WIRES : INPUT IMPEDANCE

In this paragraph, we consider infinite long metallic wires and an infinite long line source as the excitation (Figure 5a). In Figure 5b, we give the input impedance Z I for the source with and without the EBG structure. The input impedance is calculated by the FDTD method.

In the first Gap Band, the EBG structure gives a low real part which make difficult the matching of an antenna in this band. The matching is possible for frequencies higher than f 0 .

In the first Pass Band, the EBG structure add an imaginary part in the input impedance : as a result, the real source must be capacitive in this zone if we want to obtain a matched antenna.

IV. MONOPOLE AND FINITE LONG METALLIC WIRES

Let us now consider finite long metallic wires and a monopole as the exciting source (Figure 6). The frequency resonance of the monopole is called f M . The matching curves for the monopole alone and for the complete structure is given for a monopole resonating before f 0 (Figure 7a) and for a monopole resonating after f 0 (Figure 7b).

Monopole of length L M

D=80mm

We know from paragraph II that if we want to obtain a directive antenna at the normal we should not go far away from f 0 . The matching of the complete structure is obtained in the second case only : the matched band (6.7% for S 11 <-10dB) (Figure 7b) is between f M and f 0 , which correspond to the intersection between the possible matching zone and the capacitive zone of the monopole (f<f M ).

Figure 8 shows the radiation pattern of the structure in the H-plane (Figure 6) in the matched band (Figure 7b).

V. CONCLUSION

We have presented a method to design a directive and matched antenna using a monopole as the exciting source. The method consist on using a monopole which resonates at a frequency slightly higher than the first resonance of the transmission coefficient of the structure (which is calculated analytically).

In a future paper we will interest on structures composed of a slot as the exciting source.

Figure 1 -

 1 Figure 1 -Transmission coefficient of the structure excited by plane waves.

Figure 2 -

 2 Figure 2 -|T 2*2 | versus frequency at normal incidence (θ=0°).

Figure 3 -Figure- 4 -

 34 Figure 3 -|T 2*2 (θ)| at the different frequencies represented in Figure 2.

Figure 5 -

 5 Figure 5 -(a) 2 layers of metallic wires on each side of an infinite line source (b) Input impedances Z I for the source with and without the EBG (FDTD).

Figure 6 -

 6 Figure 6 -Monopole inside the finite EBG structure

Figure 7 -0Figure 8 -

 78 Figure 7 -Matching (a) Monopole resonating before f 0 (b) Monopole resonating after f 0


Siddhartha Chandra
email: siddhartha.chandra@inria.frusunier@fb.com

Nicolas Usunier

Iasonas Kokkinos
email: iasonask@fb.com

Dense and Low-Rank Gaussian CRFs Using Deep Embeddings

In this work we introduce a structured prediction model that endows the Deep Gaussian Conditional Random Field (G-CRF) with a densely connected graph structure. We keep memory and computational complexity under control by expressing the pairwise interactions as inner products of low-dimensional, learnable embeddings. The G-CRF system matrix is therefore low-rank, allowing us to solve the resulting system in a few milliseconds on the GPU by using conjugate gradient. As in G-CRF, inference is exact, the unary and pairwise terms are jointly trained end-to-end by using analytic expressions for the gradients, while we also develop even faster, Potts-type variants of our embeddings.

We show that the learned embeddings capture pixelto-pixel affinities in a task-specific manner, while our approach achieves state of the art results on three challenging benchmarks, namely semantic segmentation, human part segmentation, and saliency estimation. Our implementation is fully GPU based, built on top of the Caffe library, and is available at https://github.com/ siddharthachandra/gcrf-v2.0.

Introduction

Structured prediction combined with deep learning has delivered excellent results on a variety of computer vision benchmarks [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF][START_REF] Chen | Semantic image segmentation with deep convolutional nets and fully connected crfs[END_REF][START_REF] Chen | Weakly-and semi-supervised learning of a deep convolutional network for semantic image segmentation[END_REF][START_REF] Chen | Learning Deep Structured Models[END_REF][START_REF] Vemulapalli | Gaussian conditional random field network for semantic segmentation[END_REF][START_REF] Vu | Context-aware cnns for person head detection[END_REF][START_REF] Zheng | Conditional random fields as recurrent neural networks[END_REF]. Deeplab [START_REF] Chen | Semantic image segmentation with deep convolutional nets and fully connected crfs[END_REF][START_REF] Chen | Weakly-and semi-supervised learning of a deep convolutional network for semantic image segmentation[END_REF] successfully exploited the Dense-CRF [START_REF] Krähenbühl | Efficient inference in fully connected crfs with gaussian edge potentials[END_REF] framework, allowing a CNN trained for semantic segmentation to refine object boundaries while compensating for the effects of spatial downsampling within the network. Several works extended this approach to allow for (a) end-to-end training (b) learning of pairwise interaction terms, and (c) using exact inference (table 1). Regarding (a), [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF][START_REF] Lin | Efficient piecewise training of deep structured models for semantic segmentation[END_REF][START_REF] Liu | Deep convolutional neural fields for depth estimation from a single image[END_REF][START_REF] Liu | Semantic image segmentation via deep parsing network[END_REF][START_REF] Vemulapalli | Gaussian conditional random field network for semantic segmentation[END_REF][START_REF] Vu | Context-aware cnns for person head detection[END_REF][START_REF] Zheng | Conditional random fields as recurrent neural networks[END_REF] showed that structured prediction can be unfolded in time and thus be trained end-to-end with CNNs for both sparselyconnected [START_REF] Vemulapalli | Gaussian conditional random field network for semantic segmentation[END_REF] and fully-connected [START_REF] Lin | Efficient piecewise training of deep structured models for semantic segmentation[END_REF][START_REF] Liu | Semantic image segmentation via deep parsing network[END_REF][START_REF] Vu | Context-aware cnns for person head detection[END_REF][START_REF] Zheng | Conditional random fields as recurrent neural networks[END_REF] graphical structures. Regarding (b), [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF][START_REF] Lin | Efficient piecewise training of deep structured models for semantic segmentation[END_REF][START_REF] Liu | Semantic image segmentation via deep parsing network[END_REF][START_REF] Vemulapalli | Gaussian conditional random field network for semantic segmentation[END_REF][START_REF] Vu | Context-aware cnns for person head detection[END_REF] We express pairwise terms as dot products of low-dimensional embeddings (Ai,j = Ai, Aj ) , delivered by a devoted sub-network. This ensures that A is low-rank, allowing for efficient, conjugate gradient-based solutions. The embeddings are optimized in a taskspecific manner through end-to-end training.

connected CRFs, while [START_REF] Zheng | Conditional random fields as recurrent neural networks[END_REF]15] back-propagated on the parameters of the bilateral filter-type kernels defining their dense pairwise terms. Regarding (c), [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] showed that efficient exact inference can be used for the sparselyconnected case using conjugate gradient, while [START_REF] Barron | The fast bilateral solver[END_REF] showed that for densely-connected graphs with bilateral-type pairwise terms linear system methods can be used for efficient inference and backpropagation.

Our work is the first to combine all of the above advances in the case of densely-connected CRFs: we show that we can train in end-to-end manner densely-connected CRFs with non-parametric pairwise terms, while using efficient and exact inference by relying on linear system methods. For this, we build on [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] which combined these advances for sparsely-connected CRFs and extend it to make the densely-connected case tractable. Figure 1 provides an overview of our approach. As in [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] we perform structured prediction by solving a linear system Ax = B, where A + + + Figure 2. Illustration of our end-to-end trainable, fully convolutional network employing a dense-G-CRF module. We get our unary terms from Deeplab-v2 (we only show one of its three ResNet-101 branches, for simplicity). Our pairwise terms are generated by a parallel sub-network, resnet-pw, which outputs the pixel embeddings of our formulation. The unary terms and pairwise embeddings are combined by our fully connected G-CRF module (dense-G-CRF). This outputs the prediction x by solving the inference equation

A T Ax = B. method dense end2end non-parametric exact [5, 7] [40] [27] [33] [34] [28] [15] [2] [26]
[1] Ours Table 1. Comparison of deep structured prediction approaches in terms of whether they accommodate dense connectivity, end-toend training, use of non-parametric, CNN-based pairwise terms, and exact inference. Our method combines all of these favorable properties. and B respectively correspond to pairwise and unary terms, delivered by an end-to-end trainable CNN. Solving this system of linear equations results in couplings among all the node variables.

The core development (Sec. 3) consists in replacing the sparse system matrix used to couple the labels of neighboring nodes in [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] with a low-rank matrix that connects any node with all other image nodes through inner products of learnable, D-dimensional embeddings: A i,j = A i , A j , where i, j ∈ {1, . . . , N }, with N indexing the Cartesian product of pixels and labels. Rather than computing and inverting the full N × N matrix A, our network only needs to deliver the much smaller N × D embedding matrix A, which is all that is needed by the conjugate gradient method. Apart from low memory complexity, this can also result in fast conjugate-gradient based structured prediction.

We note that several other works have concurrently explored the use of embeddings in the context of grouping tasks, employing them as a soft, differentiable proxy for cluster assignments [START_REF] Fathi | Semantic instance segmentation via deep metric learning[END_REF][START_REF] Harley | Deep networks for saliency detection via local estimation and global search[END_REF][START_REF] Harley | Learning dense convolutional embeddings for semantic segmentation[END_REF]30]. Ours however is the first to make the connection between embeddings, lowrank matrices and densely connected random fields, effectively training embeddings for the propagation of information across the full image domain through the solution of a linear system.

We further exploit the structure of the problem by developing Potts-type embeddings that allow us to reduce the memory complexity by L 2 and computational complexity by a factor of L, where L is the number of classes. The computation time of our fastest method is 0.004s on a GPU for a 321×321 image, 2 orders of magnitude less than GPUbased implementations of Dense-CRF inference, while at the same time achieving higher accuracy across all tasks.

Our approach is loss-agnostic and works with arbitrary differentiable losses. As shown in Figures 3 and4, our embeddings can learn task-specific affinities through endto-end training. The resulting networks deliver systematic improvements when compared to strong baselines on saliency estimation, human part segmentation, and semantic segmentation.

We first give a brief review of the G-CRF model in Sec. 2, then provide a detailed description of our approach in Sec. 3, and finally demonstrate the merits of our approach on three challenging tasks, namely, semantic segmentation (Sec. 4.1), human part segmentation (Sec. 4.2), and saliency estimation (Sec. 4.3).

Deep Gaussian CRF

We briefly describe the Deep Gaussian CRF formulation of [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF], following the notation of [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF]; further information can be found in [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF][START_REF] Jancsary | Regression tree fields -an efficient, non-parametric approach to image labeling problems[END_REF][START_REF] Tappen | Learning gaussian conditional random fields for low-level vision[END_REF][START_REF] Vemulapalli | Gaussian conditional random field network for semantic segmentation[END_REF].

We consider an image I containing P patches where each patch can take a label l ∈ {1, . . . , L}. The predictions are represented as a real-valued vector that gives the score for every patch-label combination, x ∈ R N , where we denote the number of variables in our formulation by N = P × L for brevity. The L continuous variables associated to every patch can be interpreted as inputs to a softmax function that yields the label posteriors.

In particular, given an image I the G-CRF model defines a joint posterior distribution through a Gaussian multivariate density:

p(x|I) ∝ exp(- 1 2 x T A I x + B I x),
where B I , A I denote the unary and pairwise terms respectively, with B I ∈ R N and A I ∈ R N ×N . Dropping the dependence on the image I for simplicity, and assuming a positive-definite matrix A, we see that Maximum-A-Posterior inference amounts to solving the system of linear equations Ax = B. For a sparse matrix A, as is the case for grid-structured CRFs, this system can be efficiently solved through the conjugate gradient [31] algorithm.

In [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] the authors drop the probabilistic formulation and treat the G-CRF as a structured prediction layer that is incorporated in a larger network. In the forward pass, the inputs to the layer are A and B, which are delivered by a feed-forward CNN. The output of the layer x is the solution of the linear system:

(A + λI)x = B, (1)
where λ is a positive constant added to the diagonal entries of A to make it positive definite. In the backward pass, considering that the G-CRF layer obtains a gradient for the loss L with respect to its output x, ∂L ∂x , the gradients of the unary terms ∂L ∂B can be obtained by solving a new system of linear equations:

(A + λI) ∂L ∂B = ∂L ∂x , (2)
while the gradients of the pairwise terms ∂L ∂A are given by:

∂L ∂A = - ∂L ∂B ⊗ x, (3)
where ⊗ denotes the Kronecker product operator.

Deep-and-Dense Gaussian-CRF

Low-Rank G-CRF through Embeddings

While the Deep G-CRF model described above allows for efficient and exact inference, in practice it only captures interactions in small (4-,8-and 12-connected) neighborhoods. The model may thereby lose some of its power by ignoring a richer set of long-range interactions. The extension to fully-connected graphs is technically challenging because of the non-sparse matrix A it involves. Assuming an image size of 800 × 800 pixels, 21 labels (PAS-CAL VOC benchmark), and a network with a spatial downsampling factor of 8 [START_REF] Chen | Semantic image segmentation with deep convolutional nets and fully connected crfs[END_REF][START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF], the number of variables is N = (100 × 100) × 21 and the number of elements in A would be N 2 ∼ 10 10 . This is prohibitively large due to both memory and computational requirements.

To overcome this challenge, we advocate forcing A to be a low-rank. In particular, we propose decomposing the N × N matrix A into a product of the form

A = A T A, ( 4
)
where A is a D × N matrix associating every pixel-label combination with a D-dimensional vector ('embedding'), where D << N . This amounts to expressing the pairwise terms for every pair of pixels and labels in the label set as the inner product of their respective embeddings, as follows:

A pi,pj (l m , l n ) = A lm pi , A ln pj ,
where i, j ∈ {1, . . . , P } and m, n ∈ {1, . . . , L}.

Since A is symmetric and positive semi definite by design, A = A T A + λI is positive definite for any λ > 0, unlike the case of [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF], where λ had to be set empirically.

Adapting the development leading to Eq. 1, we see that we now have to solve the system:

(A T A + λI)x = B. (5)
We take advantage of the positive definiteness of A and use the conjugate gradient method [31] for solving the system of linear equations iteratively.

Setting D allows us to control both the memory and the computational complexity of inference: solving the linear system with conjugate gradient only requires keeping A in memory and forming inner products between A and a vector. As such we have a way of trading-off accuracy with speed and memory demands; as indicated in our experiments, with a sufficiently low embedding dimension we obtain excellent results.

Gradients of the dense G-CRF parameters

We now turn to learning the model parameters via endto-end network training. To achieve this we require derivatives of the overall loss L with respect to the model parameters, namely ∂L ∂A and ∂L ∂B . As described in Eq. 5, we have an analytical closed form relationship between our model parameters A,B, and the prediction x. Therefore, by applying the chain rule of differentiation, we can analytically express the gradients of the model parameters in terms of the gradients of the prediction. The gradients of the prediction are delivered by the neural network layer on top of our dense-G-CRF module through backpropagation.

The gradients of the unary terms are straightforward to obtain by substituting Eq. 4 in Eq. 2 as:

(A T A + λI) ∂L ∂B = ∂L ∂x . ( 6
)
We thus obtain the gradients of the unary terms by solving a system of linear equations. Turning to the gradients of the pixel embeddings, A, we use the chain rule of differentiation as follows:

∂L ∂A = ∂L ∂A ∂A ∂A = ∂L ∂A ∂ ∂A A T A . (7)
We know the expression for ∂L ∂A from Eq. 3, but to obtain the expression for ∂ ∂A A T A we need to follow some more tedious steps. As in [10], we define a permutation matrix T m,n of size mn × mn as follows:

T m,n vec(M ) = vec(M T ), (8)
where vec(M ) is the vectorization operator that vectorizes a matrix M by stacking its columns. When premultiplied with another matrix, T m,n rearranges the ordering of rows of that matrix, while when postmultiplied with another matrix, T m,n rearranges its columns. Using this matrix, we can form the following expression [10]:

∂ ∂A A T A = I ⊗ A T + A T ⊗ I T D,N , (9)
where I is the N × N identity matrix. Substituting Eq. 3 and Eq. 9 into Eq. 7, we obtain:

∂L ∂A = - ∂L ∂B ⊗ x I ⊗ A T + A T ⊗ I T D,N . (10)
Despite the apparently complex form, this final expression is particularly simple to implement. These equations allow us to train embeddings in a taskspecific manner, capturing the patch-to-patch affinities that are desirable for a particular structured prediction task. We visualize the affinities learned by our embeddings in Fig. 3 we observe that our embeddings indeed learn to group pixels in a way that is dictated by the task: on the left pixels belonging to similar human parts are grouped together, while on the right this is done for patches belonging to similar object classes. Similar results can also be seen in Fig. 4 for the more compact embeddings described below.

Potts Type G-CRF Pixel Embeddings

We now describe class-agnostic G-CRF pixel embeddings, which simplify and accelerate the G-CRF model by sharing the pairwise terms between pairs of classes. More specifically, these Potts-type embeddings compose pairwise terms between a pair of pixels that depend only on whether they take the same label or not, and are invariant to the particular labels they take. As in [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] we denote by A pi,pj (l i , l j ) the pairwise energy term for pixel p i taking the label l i , and pixel p j taking the label l j . The Potts-type embeddings de-scribe the following model:

A pi,pj (l i , l j ) = 0 l i = l j A pi,pj l i = l j . ( 11
)
The model in Eq. 11 reduces the size of the embeddings from P × L to P , and allows for significantly faster inference (Sec. 3.4) since the number of computations are reduced by a factor of L. As demonstrated in Sec. 4, this leads to fewer model parameters and better performance. The Potts-type embeddings are realized by posing our inference problem in Eq. 5 as:

      λI ÂT Â • • • ÂT Â ÂT Â λI • • • ÂT Â . . . ÂT Â ÂT Â • • • λI       ×      x 1 x 2 . . . x L      =      b 1 b 2 . . . b L      (12)
where x k , denotes the scores for all the pixels for the class k. The per-class unaries are denoted by b k , and the embeddings  are shared between all class pairs. In [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] solving this large linear system was reduced to solving L + 1 smaller linear systems. We have realized that this is not necessary: (1) the same gain in computation speed can be achieved by adapting the conjugate gradient implementation to this structure and avoiding redundant computations, (2) their proposed decomposition of a positive definite linear system may result into smaller non-positive definite systems. These points are detailed in the following subsection.

Implementation and Efficiency

We now provide numerical analysis details that will be useful for the reproduction of our method. Our approach is implemented as a layer in Caffe [START_REF] Jia | Caffe: Convolu-tional architecture for fast feature embedding[END_REF]. We exploit fast linear algebra routines of the CUDA blas library to efficiently implement the conjugate gradient method.

For these timing comparisons, we use a GTX-1080 GPU. Our general-inference procedure takes 0.029s, and Pottstype inference takes 0.004s on average for the semantic segmentation task (21 labels) for an image patch of size 321 × 321 pixels downsampled by a factor of 8, and for an embedding dimension of 128. This is an order of magnitude faster than the approximate dense CRF mean-field inference which takes 0.2s on average. The sparse G-CRF, and the Potts-type sparse G-CRF from [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] take 0.021s and 0.003s respectively for the same input size. Thus, our dense inference procedure comes at negligible extra cost compared to the sparse G-CRF.

We now describe our approach to efficiently implement the conjugate gradient method for G-CRF pixel embeddings. We begin by describing the conjugate gradient algorithm in Algorithm 1.

The conjugate gradient algorithm thus relies on computing the matrix-vector product q = Ap in each iteration (Algorithm 1, line:10). This operation is computationally

α k := r T k r k p T k Ap k 9:
x k+1 := x k + α k p k 10:

r k+1 := r k -α k Ap k 11:
if r k+1 is sufficiently small, then exit loop 12:

β k := r T k+1 r k+1 r T k r k 13:
p k+1 := r k+1 + β k p k 14:

k := k + 1 15:
end repeat 16:

x = x k+1 the most expensive step of this method. We now describe how to efficiently compute this quantity for our case.

Conjugate Gradient for G-CRF Embeddings To solve Eq. 5, each iteration of the conjugate gradient algorithm involves computing q = (A T A+λI)p. Explicitly computing (A T A+λI) is unnecessary because (a) it requires us to keep P L × P L terms in memory, and (b) it is computationally expensive. We therefore compute q as q = Ap; q = A T q + λp.

Conjugate Gradient for Potts-type G-CRF Embeddings

The recurring matrix-vector product for this case is given by

q =      q 1 q 2 . . . q L      =       λI ÂT Â • • • ÂT Â ÂT Â λI • • • ÂT Â . . . ÂT Â ÂT Â • • • λI            p 1 p 2 . . . p L      . ( 14
)
We make two observations by carefully examining Eq. 14:

(1) The terms ÂT Â are repeated L -1 times per column of the precision matrix. A naive implementation would compute ( ÂT Â)p k exactly L -1 times for each class k.

(2) Each q k can be computed as a sum of L terms, and for each pair (q k , q k =k ), L -2 of these terms are equal.

Using these observations, and further simplifications, we compute q k for each class as q = Â L i=1 p i ; q = ÂT q (15) qk = Âp k ; q k = q + λp k -ÂT qk [START_REF] Jancsary | Regression tree fields -an efficient, non-parametric approach to image labeling problems[END_REF] Please note that the quantity q in Eq. 15 is computed once, and used to compute q k for each class using Eq. 16.

Experiments and Results

Base network. Our base network is Deeplab-v2-resnet-101 [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF], a three branch multi-resolution network which processes the input image at scale factors of 1, 0.75, 0.5 and then combines the network responses by upsampling the lower scales and taking an element-wise maximum. It uses random horizontal flipping, and random scaling of the input image to achieve data augmentation.

Fully-Connected G-CRF network.

Our fullyconnected G-CRF (dense-G-CRF) network is shown in Fig. 2. It uses the base network to provide unaries, and a sub-network (resnet-pw) in parallel to the base network to construct the pixel embeddings for the pairwise terms. As dictated by our experiments in Sec. 4.1 the resnet-pw has layers conv1 through res4a. We use a 3-phase training strategy. We first train the unary network without the pairwise stream. We train the pairwise sub-network next, with the softmax cross-entropy loss to enforce the following objective:

A p1,p2 (l 1 , l 2 ) < A p1,p2 (l 1 = l 1 , l 2 = l 2 ),
where l 1 , l 2 are the ground truth labels for pixels p 1 , p 2 . Finally, we combine the unary and pairwise networks, and train them together in end-to-end fashion. Each training phase uses 20K iterations with a batch size of 10. The initial learning rate for the first two phases is fixed to 0.001, while for the third phase we set it to 2.5e -4 . We use a polynomial decaying learning rate with power= 0.9. Training each network takes around 2.5 days on a GTX-1080 GPU.

Semantic Segmentation

Dataset. We use the PASCAL VOC 2012 dataset which has 1464 training, 1449 validation and 1456 test images containing 20 foreground object classes. We also use the additional ground-truth from [START_REF] Hariharan | Hypercolumns for object segmentation and fine-grained localization[END_REF], obtaining 10582 training images in total. The evaluation criterion is the mean pixel intersection-over-union (IOU) metric.

Ablation Studies. In these experiments, we train on the train set, and evaluate on the val set. We study the effect of varying the depth of the pairwise network stream by chopping the resnet-101 at three lengths, indicated by the standard resnet layer names. We also study the effect of changing the size of G-CRF pixel-embeddings. These results are reported in table 2. The best results are obtained at embedding size of 128 and 1024 for general-and Potts-type embeddings respectively. Results improve as we increase the depth of resnet-pw. Even though the Potts-type embeddings are higher dimensional than the general embeddings, we learn less than half the parameters (128 × 21 = 2688 > 1024). Improvement over the base-network is 0.91%.

Base network [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] 76 We compare the performance of our method against that of the base network, and study the effect of varying the depth of the pairwise stream network, and the size of pixel embeddings.

Performance on test set. We now compare our approach with the base network [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF], the base network with the sparse deep G-CRF from [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF], as well as other leading approaches on this benchmark. In these experiments, we train with the train and val sets, and evaluate performance on the test set. In all of the following sections we use our best configurations from table 2.

Baselines. The mainstream approach on this task is to use fully convolutional networks [START_REF] Chen | Semantic image segmentation with deep convolutional nets and fully connected crfs[END_REF][START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF][START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF] trained with the Softmax cross-entropy loss. For this task, we compare our approach with the state of the art methods on this benchmark. The baselines include (a) the CRF as RNN network [START_REF] Zheng | Conditional random fields as recurrent neural networks[END_REF], (b) the Deeplab+Boundary network [18] which exploits an edge detection detection network to boost the performance of the Deeplab network, (c) the Adelaide Context network [START_REF] Lin | Efficient piecewise training of deep structured models for semantic segmentation[END_REF], (d) the deep parsing network [START_REF] Liu | Semantic image segmentation via deep parsing network[END_REF], (e) the Deeplab-v2 base network [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] and (f) the sparse-G-CRF network [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] which combines the Deeplab-v2 network with sparse, Potts-type pairwise terms.

We report the results in table 3. With our dense-Potts embeddings, we get an improvement of 0.8% over the sparse deep G-CRF approach, and 1.3% over the base network. We get a 0.1% boost in performance when we train our dense-Potts model with the sparse G-CRF from [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] (the output after dense-GCRF inference is fed as input to the sparse-GCRF inference module). Qualitative results are shown in Fig. 5. We note that performances of two recent deep-architectures namely PSPNet [START_REF] Zhao | Pyramid scene parsing network[END_REF] and Deeplab-v3 [START_REF] Chen | Rethinking atrous convolution for semantic image segmentation[END_REF] are significantly better than those of our baseline and other competing approaches. However, the authors of these works have not yet released their training pipelines publicly. We expect similar improvements by using our approach on these networks. We will experiment with these networks once their training pipelines are made available.

Method

mean IoU CRFRNN [START_REF] Zheng | Conditional random fields as recurrent neural networks[END_REF] 74.7 Deeplab Multi-Scale + CRF [18] 74.8 Adelaide Context [START_REF] Lin | Efficient piecewise training of deep structured models for semantic segmentation[END_REF] 77.8 Deep Parsing Network [START_REF] Liu | Semantic image segmentation via deep parsing network[END_REF] 77.4 Deeplab V2 (base network) [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] 79.0 Deeplab V2 + CRF [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] 79.7 sparsepotts-G-CRF [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] 79.5 dense-G-CRF (Ours) 80.1 densepotts-G-CRF (Ours) 80.3 densepotts+sparsepotts-G-CRF (Ours) 80.4

Human part Segmentation

Dataset. We use the PASCAL Person Parts dataset [START_REF] Chen | Detect what you can: Detecting and representing objects using holistic models and body parts[END_REF]. As in [START_REF] Liang | Semantic object parsing with graph lstm[END_REF], we merge the annotations to obtain six person part classes, namely the head, torso, upper arms, lower arms, upper legs, and lower legs. This dataset has 1716 train images and 1817 test images. The evaluation criterion is the mean pixel intersection-over-union (IOU) metric.

Baselines. The state of the art approaches on human part segmentation also use fully convolutional networks, sometimes additionally exploiting Long Short Term Memory Units [START_REF] Liang | Semantic object parsing with graph lstm[END_REF][START_REF] Liang | Semantic object parsing with local-global long short-term memory[END_REF]. For this task, we compare our approach to the following methods: (a) the Deeplab attention to scale network [4], (b) the Auto Zoom network [START_REF] Xia | Zoom better to see clearer: Human part segmentation with auto zoom net[END_REF], (c) the Local Global LSTM network [START_REF] Liang | Semantic object parsing with local-global long short-term memory[END_REF] which combines local and global cues via LSTM units, (d) the Graph LSTM network [START_REF] Liang | Semantic object parsing with graph lstm[END_REF], (e) the base network with and without dense CRF post-processing, and (f) the sparse G-CRF Potts model. We report the results in table 4. While the previous state of the art approach Deeplab-v2 achieves 64.94 with dense-CRF post-processing, out Potts-type model outperforms it by 1.33% mean IoU without using dense-CRF postprocessing. Additionally, we outperform the Deeplab-V2 G-CRF Potts baseline from [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] by 1.06%. Using the sparse-G-CRF on top of our results gives us a minor boost of 0.04%. We show qualitative results in Fig. 5.

Attention [4]

56.39 Auto Zoom [START_REF] Xia | Zoom better to see clearer: Human part segmentation with auto zoom net[END_REF] 57.54 LG-LSTM [START_REF] Liang | Semantic object parsing with local-global long short-term memory[END_REF] 57.97 Graph LSTM [START_REF] Liang | Semantic object parsing with graph lstm[END_REF] 60.16 Deeplab-V2 [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] 64.40 Deeplab-V2-CRF [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] 64.94 sparsepotts-G-CRF [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] 65.21 dense-G-CRF (Ours) 66.10 densepotts-G-CRF (Ours) 66.27 densepotts+sparsepotts-G-CRF (Ours) 66.31

Saliency Estimation

Datasets. As in [START_REF] Kokkinos | Ubernet: A universal cnn for the joint treatment of low-, mid-, and high-level vision problems[END_REF], we use the MSRA-10K saliency dataset [START_REF] Wang | PISA: pixelwise image saliency by aggregating complementary appearance contrast measures with edge-preserving coherence[END_REF] for training, and evaluate our performance on the PASCAL-S [START_REF] Li | The secrets of salient object segmentation[END_REF], and the HKU-IS [21] datasets. The Method PASCAL-S HKU-IS LEGS [START_REF] Wang | Deep networks for saliency detection via local estimation and global search[END_REF] 0.752 0.770 MC [39] 0.740 0.798 MDF [21] 0.764 0.861 FCN [START_REF] Li | Deep contrast learning for salient object detection[END_REF] 0.793 0.867 DCL [START_REF] Li | Deep contrast learning for salient object detection[END_REF] 0.815 0.892 DCL + CRF [START_REF] Li | Deep contrast learning for salient object detection[END_REF] 0.822 0.904 Ubernet 1-Task [START_REF] Kokkinos | Ubernet: A universal cnn for the joint treatment of low-, mid-, and high-level vision problems[END_REF] 0.835 -Deeplab-v2 [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] 0.859 0.916 sparse-G-CRF [START_REF] Chandra | Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs[END_REF] 0.861 0.914 dense-G-CRF (Ours) 0.872 0.927 dense+sparse-G-CRF (Ours) 0.864 0.927 MSRA-10K dataset contains 10000 images with annotated pixel-wise segmentation masks for salient objects. The Pascal-S saliency dataset contains pixel-wise saliency for 850 images. The HKU-IS dataset has 4447 images, with multiple salient objects in each image. The evaluation criterion is the maximal F-Measure as in [START_REF] Kokkinos | Ubernet: A universal cnn for the joint treatment of low-, mid-, and high-level vision problems[END_REF][START_REF] Li | The secrets of salient object segmentation[END_REF].

Baselines. Our baselines for the saliency estimation task include (a) the Local Estimation and Global Search (LEGS) framework [START_REF] Wang | Deep networks for saliency detection via local estimation and global search[END_REF], (b) the multi-context network [39], (c) the multiscale deep features network [21], (d) the deep contrast learning networks [START_REF] Li | Deep contrast learning for salient object detection[END_REF] which proposes a network structure that better exploits object boundaries to improve saliency estimation and additionally uses a fully connected CRF model, (e) the Ubernet architecture [START_REF] Kokkinos | Ubernet: A universal cnn for the joint treatment of low-, mid-, and high-level vision problems[END_REF] which demonstrates that sharing parameters for mutually symbiotic tasks can help improve overall performance of these tasks, (f) our base network, i.e. Deeplab-v2, and (g) the sparse G-CRF Potts model alongside the base network.

Results are tabulated in table 5. Our method significantly outperforms the competing methods on both datasets. Additionally, we do not obtain improvements when combining our method with the sparse G-CRF approach.

Conclusions and Future Work

In this work we propose a fully-connected G-CRF model for end-to-end training of deep architectures. We propose strategies for efficient implementation and show that inference over a fully-connected graph comes with neglegible computational overhead compared to a sparsely connected graph. Our experimental evaluation indicates consistent improvements over the state of the art approaches on three challenging public benchmarks for semantic segmentation, human part segmentation and saliency estimation. Future work would involve exploiting this framework on other dense labeling and regression tasks such as depth estimation, image denoising and estimation of surface normals, which can be naturally handled by our model owing to its continuous nature. Further, we would also like to exploit G-CRF embeddings for dense-labeling tasks such as semantic/instance segmentation and optical flow estimation in videos. In the case of videos, we would like to capture not only the spatial context but temporal context as well by expressing temporal pairwise terms between two frames via dot products of embeddings computed on them.

Figure 1 .

 1 Figure 1. Method overview: each image patch amounts to a node in our fully-connected graph structure. As in the G-CRF model, we infer the prediction x by solving a system of linear equations Ax = B, based on CNN-based unary (B) and pairwise (A) terms.We express pairwise terms as dot products of low-dimensional embeddings (Ai,j = Ai, Aj ) , delivered by a devoted sub-network. This ensures that A is low-rank, allowing for efficient, conjugate gradient-based solutions. The embeddings are optimized in a taskspecific manner through end-to-end training.

Figure 3 .

 3 Figure 3. Visualization of pairwise terms obtained by our G-CRF embeddings trained for the (i) human part segmentation, and (ii) semantic segmentation tasks. Column (a) shows the reference pixel (p * ), marked with a dartboard, on the image. The pairwise term corresponding to p * taking the ground truth label l * and any other pixel p taking the label l is given by the inner product Ap * ,p (l * , l) = A l p , A l * p * . In (i) we show the pairwise terms Ap * ,p (l * , head) in (b), Ap * ,p (l * , torso) in (c), and Ap * ,p (l * , upper-limb) in (d). In (ii) we show the pairwise terms Ap * ,p (l * , bkg) in (b), Ap * ,p (l * , l * ) in (c), and Ap * ,p (l * , l2) in (d), where l2 is the most dominant class in the image besides l * .

Figure 4 .

 4 Figure 4. Visualization of pairwise terms obtained by our Potts-Type task-specific G-CRF embeddings. The first column shows the reference pixel (p * ), marked with a dartboard, on the image. The pairwise term between p * and any other pixel p is given by the dot product Ap * ,p = Ap T Ap * . We show the pairwise terms Ap * ,p for the segmentation task in (b), human part estimation in (c), and saliency estimation in (d).

Figure 5 .

 5 Figure 5. Qualitative Results of (i) Part Segmentation, and (ii) Semantic Segmentation tasks. (a) shows the unary network output, (b) shows the sparsepotts-G-CRF output, (c) shows the densepotts-G-CRF output, and (d) shows the input image and ground truth. In (i), our fully connected model recovers false negatives (rows 1,4), and missing parts (the right foot in rows 2,3), and prevents propagation of erroneous labels (a patch labeled face is eliminated from the right foot in row 5). In (ii), this information flow from the rest of the image helps recover missing object parts (cycle in rows 1,3, person's leg in row 2, table in row 4, sheep's leg in row 5, and left hand in row 7.)

Table 2 .

 2 Ablation study-mean Intersection Over Union (IOU) accuracy on PASCAL VOC 2012 validation set.

	.30

Table 3 .

 3 Semantic segmentation -mean Intersection Over Union (IOU) accuracy on PASCAL VOC 2012 test.

Table 4 .

 4 Part segmentation -mean Intersection-Over-Union accuracy on the PASCAL Parts dataset of[START_REF] Chen | Detect what you can: Detecting and representing objects using holistic models and body parts[END_REF].

Table 5

 5

. Saliency estimation results: we report the Maximal Fmeasure (MF) on the PASCAL Saliency dataset of

[START_REF] Li | The secrets of salient object segmentation[END_REF]

, and the HKU-IS dataset of

[21]

.


L Urban

A Jawad

P C Nicot

Prospects for Using Environmental Levers in Greenhouses to Stimulate Plant Defences and the Quality of Fruits and Vegetables

Keywords: light, organic farming, secondary metabolism, stress

The environment of greenhouses is commonly modified to reduce the pressure of pests and diseases, but it can also be exploited to stimulate natural defences of plants. In addition to genetic influences, several agronomic factors can be used as levers to increase the concentrations of secondary metabolites involved in the defence of fruit and vegetable crops. Many secondary metabolites involved in plant defences are also phytonutrients, i.e., compounds that have beneficial effects on human health, including protection against cardiovascular diseases, cancers, and metabolic or neurodegenerative diseases. Nitrogen deprivation, photooxidative stress and exposure to specific wavelengths such as those supplied by UV radiations are well known for stimulating the production of secondary metabolites in a large range of plants. We propose here a review of factors meeting the specifications of organic farming, which are both effective and applicable in greenhouse conditions. Among all these factors, mild stress and innovative covering materials emerge as especially promising.

INTRODUCTION

Plants produce a diverse set of organic molecules, some of which are traditionally considered not to participate directly in the major processes involved in growth and development. These substances, secondary metabolites, encompass terpenes (e.g., carotenoids, vitamin E), phenolic compounds (e.g., stilbenes, flavonoids, anthocyanins), nitrogen-containing compounds (e.g., alkaloids, glucosinolates), and sulfur-containing compounds such as diallyl disulfide [START_REF] Goldberg | Plants: Diet and Health. The Report of a British Nutrition Foundation Task Force[END_REF]. They play many roles in plants. Some of the secondary metabolites are involved in defence functions or are antioxidants, which indicates that they have strong biological effects. Some have positive dietary effects, and some even have medicinal properties. It is well established that fruits and vegetables (FAVs) represent a major source of useful secondary metabolites, the so-called phytochemicals [START_REF] Kaur | Antioxidants in fruits and vegetables -the millennium's health[END_REF]. The high concentrations of phytochemicals in FAVs are considered to exert protective effects against cardio-vascular diseases, metabolic diseases (e.g., obesity, diabetes), neuro-degenerative diseases (e.g., Parkinson's, Alzheimer's) (UNESCO, 2008), and certain forms of cancer [START_REF] Jansen | Nutrients from fruit and vegetable consumption reduce the risk of pancreatic cancer[END_REF][START_REF] Park | Fruit and vegetable intakes are associated with lower risk of bladder cancer among women in the Multiethnic Cohort Study[END_REF]. Although the nutritional benefits of fresh FAVs are well established, their consumption remains insufficient. In developed countries, it may be tempting for the fruit and vegetable industry to offer consumers FAVs with increased or guaranteed amounts of micronutrients [START_REF] Dorais | Agronomy and the nutritional quality of fruit[END_REF][START_REF] Poiroux-Gonord | Health benefits of vitamins and secondary metabolites of fruits and vegetables and prospects to increase their concentrations by agronomic approaches[END_REF]. This could help the cause of public health while contributing to the competitiveness of the industry in a more and more challenging global market. There are basically two ways to reach the objective of increased or guaranteed amounts of micronutrients in FAVs: the genetic approach and the environmental approach. A recent survey of the existing literature provided evidence that agronomic methods may stimulate an increase in the concentrations of secondary metabolites of FAVs, likely without attaining undesirable levels [START_REF] Poiroux-Gonord | Health benefits of vitamins and secondary metabolites of fruits and vegetables and prospects to increase their concentrations by agronomic approaches[END_REF]. The good news for greenhouse growers is that they have a much wider range of environmental levers at their disposal than growers in open field conditions. This review will cover the most common environmental levers exploitable in organic greenhouse conditions to increase the concentrations of phytochemicals in FAVs. Then we shall discuss the consequences regarding plant natural defences.

THE STRESS THEORY

The stress theory is based on the idea that all stresses stimulate the production of secondary metabolites by generating an oxidative stress, i.e., the production of Reactive Oxygen Species (ROS), namely O 2 -, 1 O 2 , and H 2 O 2 . There is a large body of evidence that all biotic and abiotic stresses are conducive to oxidative stress, and more specifically to photooxidative stress, i.e., the production of ROS associated with the functioning of the photosynthetic machinery [START_REF] Grassmann | Plant's defence and its benefits for animals and medicine: Role of phenolics and terpenoids in avoiding oxygen stress[END_REF] as shown in Figure 1. The photosynthetic machinery is considered to be the major contributor to the production of ROS in green plant parts, and even in plant parts that have lost their photosynthetic machinery. The synthesis of carotenoids can be stimulated in the pulp of non-stressed fruits that lost their chlorophyll by submitting nearby leaves to photooxidative stress (Poiroux-Gonord et al., 2013b). Other physiological processes can be involved in ROS production as a consequence of stress, such as mitochondrial respiration and activity of the membrane-located NADPH oxidase. Generally, plants are well equipped to deal with ROS. However, even small and transient accumulations of ROS or the associated imbalances in redox status are involved in the stimulation and regulation of processes that eventually lead to the production of secondary metabolites (Fanciullino et al., 2013). There is ample evidence that ROS either directly or indirectly influence the expression of genes of the biosynthetic pathways, arguably via the redox-sensitive thiols-disulfite systems. Moreover NADPH, whose availability dependsin part on the scavenging activity of the ascorbate-glutathione cycle, and thus the abundance of ROS, is required by several steps of the biosynthetic pathways of terpenes and glucosinolates. The idea that oxidative stress stimulates the secondary metabolism makes sense from a deterministic point of view since many secondary metabolites are involved either directly or indirectly in the defence against oxidative stress.

The scientific literature abounds in references about the positive effects of mildly stressing conditions (e.g., drought, high salinity or electrical conductivity, NaCl, high light, low temperature) on the concentrations of carotenoids and phenolic compounds in FAVs [START_REF] Maggio | Saline agriculture in Mediterranean environments[END_REF][START_REF] Poiroux-Gonord | Health benefits of vitamins and secondary metabolites of fruits and vegetables and prospects to increase their concentrations by agronomic approaches[END_REF]. Some growing systems could be more favourable to the accumulation of phytonutrients in FAVs than others. It has been hypothesised that organic FAVs could be richer in secondary compounds because organic plants are less intensively managed (e.g., plants in conventional growing systems are better protected against pests and diseases by pesticides, in contrast to plants in organic systems) [START_REF] Urban | The effect of environmental factors on biosynthesis of carotenoids and polyphenolics in fruits and vegetables: a review and prospects[END_REF]. The idea that organic tomatoes are better because they are picked from plants that have undergone oxidative stress has received some support by a recent study [START_REF] Oliveira | The impact of organic farming on quality of tomatoes is associated to increased oxidative stress during fruit development[END_REF].

THE CARBON THEORY

The carbon theory stipulates that carbohydrate concentration determines the synthesis of both primary and secondary metabolites. While ecologists still debate the relationships between the primary and secondary metabolisms in terms of competition or optimal allocation [START_REF] Herms | The dilemma of plants -To grow or defend[END_REF][START_REF] Loomis | Growth-differentiation balance vs. carbohydrate nitrogen ratio[END_REF][START_REF] Wilkens | Differential responses of growth and two soluble phenolics of tomato to resource availability[END_REF], there is mounting evidence from physiological studies that availability of resources does not necessarily directly determine the synthesis of all types of secondary metabolites in all plant organs (Fanciullino et al., 2013). This idea certainly has merits as far as defence compounds are concerned, but there are contradictory observations. In leaves, accumulation of carbohydrates generally represses the synthesis of carotenoids; whereas in fruits, low availability of carbohydrates may reduce carotenoid concentrations of (Poiroux-Gonord et al., 2013a). It is interesting to note that there are links between the stress and carbon theories. On the one hand, sugars play a generally positive role in the protection of cells against ROS. Soluble sugars can feed NADPH-producing metabolic processes such as the oxidative pentose-phosphate pathway. On the other hand, sugars are potentially exacerbating factors of photoinhibition and the associated production of ROS in photosynthetic tissues [START_REF] Urban | Girdling decreases photosynthetic electron fluxes and induces sustained photoprotection in mango leaves[END_REF]. To summarise, manipulation of the carbon lever does not reliably generate predictable results in terms of concentrations of useful secondary metabolites. Moreover, manipulating a plant's primary metabolism may reduce yield and quality criteria such as harvested organ size, dry matter content and concentrations in sugars and organic acids.

THE EFFECT OF NITROGEN DEPRIVATION

One may be tempted to provoke a nitrogen deficit in plants. It is well established that nitrogen deprivation stimulates the Phenyl Ammonia Lyase (PAL) which is the first enzyme of the biosynthetic pathway of phenolic compounds. The PAL is also a ratedetermining enzyme, which means that stimulating the PAL will actually result in the accumulation of end-of-the-chain phenolic compounds. Recent observations suggest that phenolic compounds do not accumulate in tomato fruit as a consequence of nitrogen deprivation [START_REF] Bénard | Effects of low nitrogen supply on tomato (Solanum lycopersicum) fruit yield and quality with special emphasis on sugars, acids, ascorbate, carotenoids, and phenolic compounds[END_REF]; however, defence compounds such as tomatine, a glycoalkaloid, do accumulate in other plant parts [START_REF] Royer | Etude des relations entre croissance, concentrations en métabolites primaires et secondaires et disponibilité en ressources chez la tomate avec ou sans bioagresseurs[END_REF]. This said, it could be risky to recommend a substantial reduction in nitrogen supply because nitrogen is the major ingredient of the photosynthetic machinery. In other words, nitrogen deficit would automatically result in a decrease in photosynthetic capacity, net photosynthetic rate, and eventually, commercial yield.

THE EFFECT OF SPECIFIC WAVELENGTHS

Evidence exists that the light spectrum provides opportunities for stimulating the synthesis of secondary metabolites in plants, especially in FAVs. For instance, red light increased concentrations of anthocyanins in tomato fruit [START_REF] Mancinelli | Light-dependent anthocyanin synthesis -a model system for the study of plant photomorphogenesis[END_REF], whereas blue light increased concentrations of carotenoids [START_REF] Gautier | Effect of photoselective filters on the physical and chemical traits of vine-ripened tomato fruits[END_REF]. Even green light, long believed to play no role in plants, has recently been reported to increase the concentration in anthocyanins in lettuce [START_REF] Samuoliené | LED illumination affects bioactive compounds in romaine baby leaf lettuce[END_REF]. Ultraviolet (UV) radiations also have been observed to stimulate the synthesis of secondary metabolites [START_REF] Jansen | Plant stress and human health: Do human consumers benefit from UV-B acclimated crops?[END_REF] and can be exploited to stimulate natural defences against diseases such as grey mould [START_REF] Charles | Physiological basis of UV-C induced resistance to Botrytis cinerea in tomato fruit: III. Ultrastructural modifications and their impact on fungal colonization[END_REF][START_REF] Charles | Physiological basis of UV-C induced resistance to Botrytis cinerea in tomato fruit. V. Constitutive defence enzymes and inducible pathogenesis-related proteins[END_REF]). An interesting perspective with the effect of light is that the spectrum can be easily modified in greenhouses, either by using innovative plastic materials or by using LED lamps. Depending on organic regulations, artificial lighting with specific wavelengths may not be acceptable for some organic growers. There is still a lot of work ahead to find the right combinations of wavelengths that will prove beneficial to both yield and quality or defences, but there is little doubt that innovation in plastic materials and LEDs will foster the development of greenhouse systems that will perform substantially better in terms of yield and quality than the existing systems.

THE CROSS-TALK THEORY

Complex signalling pathways involving ROS and the production of defence compounds, including secondary metabolites (e.g., terpenoids, phenolic compounds, glucosinolates) originate from biotic stresses (Fig. 2). The idea that responses to biotic and abiotic stresses share, to a certain extent, the same signalling and metabolic pathways has been extensively discussed and theorised, giving birth to the so-called cross-talk theory [START_REF] Fujita | Crosstalk between abiotic and biotic stress responses: a current view from the points of convergence in the stress signaling networks[END_REF][START_REF] Orsini | Systemin-dependent salinity tolerance in tomato: evidence of specific convergence of abiotic and biotic stress responses[END_REF]. This scientific concept holds many interesting perspectives for growers. For instance, abiotic stress could be exploited to increase plants' resistance to pests. The possibility of using stimulators of natural plant defences to increase the concentrations of phytonutrients has not formally been tested to our knowledge, but there is good hope that it will work. Similarly, it would be interesting to test the idea that tolerant or resistant cultivars may also be better in terms of micronutritional value. There are known limits to the cross-talk theory and to what can be achieved, but at least this theory clearly shows that the issue of nutritional quality and the issue of plant defences should be addressed jointly.

CONCLUSION

Environmental factors represent powerful natural levers to increase concentrations of secondary metabolites in plants, which should benefit both plant defences and produce quality. While modifying the carbon status and creating conditions of nitrogen deficit are certainly effective methods regarding this objective, they must be used with caution because of the negative effects they may produce in terms of yield and quality. Specific light wavelengths could be exploited in greenhouses by using innovative plastic covering materials or LED lamps. In addition, oxidative stress could be applied by reducing irrigation, ideally at the end of the cropping cycle, at a time when the benefits of a mild stress will have only a very low, if any, negative side-effect on yield. All the exciting and promising observations made and ideas expressed should represent a strong incentive to develop techniques that will stimulate plant defences and improve the micronutritional quality of produce. It seems only too natural that organic growers take the lead in that field.

FiguresFig. 1

 1 Figures

  Fig. 1. Photooxidative stress. Crosses indicate common limitations to photosynthesis that create conditions favorable to the production of Reactive Oxygen Species.


Guangshuo Chen
email: guangshuo.chen@inria.fr

Sahar Hoteit
email: sahar.hoteit@u-psud.fr

Aline Carneiro Viana

Marco Fiore
email: marco.fiore@ieiit.cnr.it

Carlos Sarraute

The Spatiotemporal Interplay of Regularity and Randomness in Cellular Data Traffic

Keywords: Fundamental limits, user mobility, user data traffic, call detail records, performance analysis

In this paper, we leverage two large-scale real-world datasets to provide the first results on the limits of predictability of cellular data traffic demands generated by individual users over time and space. Using information theory tools, we measure the maximum predictability that any algorithm has potential to achieve. We first focus on the predictability of mobile traffic consumption patterns in isolation. Our results show that it is theoretically possible to anticipate the individual demand with a typical accuracy of 85% and reveal that this percentage is consistent across all user types. Then, we analyze the joint predictability of the traffic demands and mobility patterns. We find that the two dimensions are correlated, which improves the predictability upper bound to 90% on average.

I. INTRODUCTION

The quantitative understanding of human behavior (e.g., user's whereabouts or data traffic) has recently emerged as a central question in multi-disciplinary research [START_REF] Naboulsi | Large-scale Mobile Traffic Analysis: a Survey[END_REF]. The performance of any practical technique that aims at anticipating human behaviors is bounded by predictability, measuring to what degree a specific behavior can be foreseen. In the area of wireless communication, the predictability bound of mobile data traffic predictors opens new opportunities to network operators to (i) manage their resources in advance, (ii) accommodate the future demand at lower maintenance and operational costs, and (iii) define traffic plans that are better tailored to users' needs. Also, the predictability bound contributes to the understanding of human nature as well as the design of effective prediction algorithms.

In this paper, we analyze the traffic predictability from the viewpoint of individual users instead of base stations or aggregated perspective [START_REF] Zhou | The predictability of cellular networks traffic[END_REF], [START_REF] Li | The prediction analysis of cellular radio access network traffic: From entropy theory to networking practice[END_REF]. For mobile phone users, the regularity of their Internet traffic, which drives the predictability together with randomness, is not only reflected by statistical measures of their consumed data volumes [START_REF] Shafiq | Characterizing and modeling internet traffic dynamics of cellular devices[END_REF] but also by their whereabouts [START_REF] Jo | Spatiotemporal correlations of handset-based service usages[END_REF]. However, to the best of our knowledge, there is no analysis of (i) how per-user regularity of mobile data traffic is translated into actual predictability, or (ii) the associated impacts brought by jointly considering users' visited locations.

We aim at filling the gap above, and provide a first investigation of the predictability of mobile data traffic generated by individual users. Specifically, we focus on data traffic volume, i.e., the amount of bytes generated by the mobile services consumed by a given user. Overall, our study allows answering an important question: to what degree is the individual consumption of mobile data traffic predictable?

We address this problem by studying the variation in individual's mobile data traffic over time and space and investigating its predictability limits by using tools from information theory. In summary, our contributions are:

• We provide a first study of the predictability of mobile data traffic usage from the viewpoint of individual users. Our work is powered by two large-scale real-world datasets, presented in Sec. II. • We derive a promising upper bound (85%) to the performance of practical algorithms for the prediction of the volume of mobile data traffic from the user's historical usage. Details are provided in Sec. III. • We also introduce a first investigation on the power of jointly forecasting when, where, and how much mobile data traffic is generated by individual users. We observe that the strong correlation between mobility and mobile service usage leads to a performance gain on the upper predictability bound from 85% to 90%. Details are provided in Sec. IV. • Our discussion about the cause of the high (joint) predictability sheds light on the design of predicting algorithms. Details are provided in Sec. V.

II. DATA OVERVIEW Our study is based on the observation across the population of approximately 45K mobile phone users during a consecutive period of 92 days in 2014. Footprints and Internet data traffic demands are provided by two anonymous datasets having the same hashed users' identifiers, respectively:

1) CDR (Call Detail Record) dataset: A CDR entry is logged once a user initiates or receives a voice call [START_REF] Naboulsi | Large-scale Mobile Traffic Analysis: a Survey[END_REF]. Each CDR entry contains the user's identifier, the call start time and the handling cell tower location. The users and their CDRs are collected from a major cellular operator in a metropolitan area where a cell tower covers around 2 km 2 on average, leading to a fair spatial granularity in localizing the users.

2) Internet data session dataset: This dataset describes how the users generate Internet data traffic through their devices and consists of Internet data sessions. Every data session is established upon the allocation of a radio channel for the exchange of IP traffic, and it ends after an idle period over the same channel. Each session entry contains the user's identifier, the volume of upload and download data (in KiloBytes) and the session start time.

Those 45K users meet the followng criteria: (i) they have visited at least 2 locations; (ii) they have CDR-based footprints in at least 20% of the observing hours; (iii) they establish sessions in at least 73 days (i.e., 80% of the observing period). The criteria ensures statistical significance of our analysis.

Given the two datasets, we compute representative discretized time series of data traffic volumes S vol u and of locations S loc u per user as follows:

1) Volume processing: The Internet session dataset allows processing sessions and quantizing volume in a straightforward way. Hence, for a user u ∈ U (where U is the user set), her volume time series, represented as

S vol u = {v 1 u , v 2 u , . . . , v i u , . . . , v T u }
, is computed by aggregating the volume of traffic from all her sessions recorded during each one-hour interval. Particularly, the observing period is divided into T 24 hours/day × 92 days = 2208 intervals, and v i u describes the usage of data traffic of the user u in the i th interval and is symbolized as one of the eight quantization intervals: 0 (idle), (1, 10), (10, 10 2 ), . . . , (10 6 , 10 7 ) in KB.

2) Location processing: An imputation is necessary before processing CDRs because the mobility information is actually incomplete. For that, we firstly apply the stop-by-spothome approach, a CDR completion approach introduced in [START_REF] Hoteit | Filling the gaps: On the completion of sparse call detail records for mobility analysis[END_REF]. This significantly increases the temporal coverage of CDRs, particularly overnight, without affecting the localization precision. Then for a user u, his movement is represented by a time series of locations as S loc u = { 1 u , 2 u , . . . , i u , . . . , T u }, where i u is the location of u in the i th one-hour interval. On each interval, i u is the cell tower location where the user u spend the most time or unknown if the user has no calls during the interval. S loc u and S vol u of each user cover the same observing period and thus have the same length. For more details on the data and preprocessing, we refer the reader to the full paper [START_REF] Chen | Spatio-Temporal Predictability of Cellular Data Traffic[END_REF].

III. PREDICTABILITY OF MOBILE DATA TRAFFIC

We first study the predictability of the mobile data traffic generated by individual subscribers by focusing on the forecast of traffic volume in isolation. Methodology: For each user, we consider her S vol u as a consecutive sequence of sampled from a corresponding model describing how she generates data traffic. Given the model, we then estimate the entropy rate as

H u (V ) = lim t→∞ H(V t u |V t-1 u , • • • , V 1 u )
from the S vol u as a prepositive step of measuring the predictability. The entropy rate measures the average uncertainty of anticipating data traffic quantization as V (•) u on each interval. Hereby, we derive four variants of the entropy rate from different models, as follows:

• The random entropy rate is formulated as H rand u (V ) ≡ log 2 N , where N is the number of distinct quantizations of traffic volumes, derived from an equally probable and time-independent model. • The temporal-uncorrelated entropy rate is formulated as

H unc u (V ) ≡ -v∈V P (v) log 2 P (v)
where the user's

P (H) PDF H rand u (V ) H unc u (V ) H n0 u (V ) Hu(V) (a) Entropy
P (Π) PDF Π rand u (V ) Π unc u (V ) Π n0 u (V ) Π max u (V) (b) Predictability
Π rand u (V ), Π unc u (V ), Π n0 u (V ) and Π max u (V).
traffic follows a heterogeneous and time-independent model. This entropy rate characterizes the heterogeneity of a mobile demand model that has no temporal correlations, hence its name. • The nonzero-temporal-uncorrelated entropy rate is based on the same model of H unc u (V ), but it is limited to those cases when the user is not idle. Formally, it is H n0 u (V ) ≡ -v∈V /{0} P (v|v = 0) log 2 P (v|v = 0). It captures the heterogeneity of the traffic volume exchanged during active hours only, yet still ignoring temporal correlations.

• Finally, the actual entropy rate, denoted by H u (V), is estimated based on Lempel-Ziv compression [START_REF] Schürmann | Entropy estimation of symbol sequences[END_REF], where the data traffic is considered to follow a stochastic process without other constraints. This entropy rate depends not only on the frequency of appearance of each discretized traffic volume but also on the order in which they appear, capturing the temporal order presented in a subscriber's traffic usage pattern. The entropy rate and predictability are negatively correlated variables: a behavior with low (or high) uncertainty is highly (or little) predictable. Mathematically, given an entropy rate variant H, its predictability Π satisfies Π ≤ Φ -1 (H) where Φ(x) ≡ (1x)log(N -1)x log x -(1x) log(1x) and Φ -1 (x) is its inverse function [START_REF] Feder | Relations between entropy and error probability[END_REF]. In our context, the upper bound of Π is an estimation of the maximum achievable accuracy in the prediction of the mobile traffic demand, given a particular model. Hence, four upper bounds for the predictability, i.e.., Π max u (V), Π rand u (V ), Π unc u (V ), and Π n0 u (V ), are calculated from the entropy rates. Results: Let us start by considering the PDF of H rand u (V ) in Fig. 1(a). It peaks at H rand u (V ) ≈ 2.7 which indicates that on average, the quantization level of traffic volume can be represented by at most three bits per time interval of new information; that is, a user who randomly demand traffic can generate traffic on average in 2 H rand u (V ) = 2 3 ≈ 8 quantization levels. This phenomenon is normal, as most of users have eight traffic volume quantization levels (up to 10GB/hr). When the temporal-uncorrelated entropy, i.e., H unc u (V ), is concerned, a sizable shift of probability occurs: the uncertainty decreases to 2 H unc u (V ) = 2 1.63 ≈ 3. Under this model, each user tends to generate traffic that is described by just three quantization levels out of the eight available.

Interestingly, idle time intervals do not bias such regularity.

Fig. 1 .

 1 Fig. 1. (a) Distributions of the random entropy H rand u (V ), the temporaluncorrelated entropy H unc u (V ), the nonzero-temporal-uncorrelated entropy H n0 u (V ), and the entropy rate Hu(V) as observed in the individual traffic demand. (b) Equivalent distributions of the upper bounds on the predictability Π rand u (V ), Π unc u (V ), Π n0 u (V ) and Π max u (V).

ACKNOWLEDGEMENT

This work is supported by the EU FP7 ERANET program under grant CHIST-ERA-2012 MACACO.

Indeed, the PDF of H n0 u (V ) overlaps well to that of H unc u (V ), suggesting that the considerations above also hold when only time intervals with data sessions are considered. However, our main result is the significant shift presented by the PDF of H u (V), which peaks at 0.97. When taking the temporal ordering of data sessions into account, one can reduce the uncertainty to just two quantization levels.

The probability distributions in Fig. 1(b) confirm these findings and provide upper numerical bounds to the predictability of the mobile data traffic demand generated by individual subscribers. We observe that Π rand u (V ) peaks at 0.16, i.e., it is very hard to guess the volume of traffic generated by such a stochastic model. The predictability grows for Π unc u (V ) and Π n0 u (V ), which peak at 0.69 and 0.66, respectively. More importantly, Π max u (V) indicates that the demand of a subscriber can be possibly predicted within 85% accuracy on average. It means that in only 15% of the time does the subscriber generate a traffic volume in a manner that appears to be random, but in the remaining 85% of the time, we could hope to predict her volume. This result proves, for the first time, that the traffic volume which subscribers generate via their mobile devices is highly predictable.

IV. JOINT PREDICTABILITY OF TRAFFIC AND MOBILITY

We further study the joint predictability of future mobile data traffic volume and visited locations, on a per-user basis. We investigate how predictable is the combination of how much traffic is generated by a mobile phone user and where this happens. Note that the temporal dimension, i.e., when the mobile data traffic is consumed, is implicitly taken into account by the temporal correlation in the definition of the predictability upper bound. Methodology: Firstly, as in Sec. III, we leverage S loc u to calculate two entropy rate variants on subscribers' mobility: the temporal-uncorrelated entropy rate H unc u (L) and the actual entropy rate H u (L) and their corresponding upper bounds on the predictability Π unc u (L) and Π max u (L). Secondly, from a user's S loc u and S vol u , we compute two joint entropy variants that consider the user's volume and location together. The temporal-uncorrelated entropy rate H unc u (V, L) ≡ -v∈V,l∈L P (v, l) log 2 P (v, l) determines the joint heterogeneity of the user's location and traffic volume. The joint actual entropy rate H u (V, L) is defined as the actual entropy rate of the joint stationary process that generates S vol u and S loc u . It expresses the combined uncertainty of a user's location and traffic volume at a given time instant, considering his previous history of movements and mobile service usage. Also, the corresponding predictability upper bounds Π unc u (V, L) and Π max u (V, L) are calculated. We also measure the conditional entropy rate as H u (V|L) ≡ H u (V, L) -H u (L) and the temporal-uncorrelated conditional entropy rate as

along with their corresponding predictability upper bounds, respectively. The conditional variants corresponds to the case that only the traffic volume is forecast, assuming knowledge of the past and current locations. Results: Fig. 2 summarizes results with respect to the uncertainty and predictability of traffic volume and mobility, for different ways of bringing together the two dimensions of A first interesting remark is that H unc u (V, L) and H unc u (V ) + H unc u (L) in Fig. 2(a), and consequently Π unc u (V, L) and Π unc u (V ) • Π unc u (L) in Fig. 2(c), are nearly indistinguishable. Instead, H u (V, L) and H u (V) + H u (L) in Fig. 2(b), and consequently Π max u (V, L) and Π max u (L)•Π max u (V) in Fig. 2(d), show significant differences. Hence, there exists some correlation between the mobility and traffic volume consumption processes, and such correlation mainly emerges when considering -and it is thus driven by -the temporal ordering of events. As observed in Fig. 2(d), a joint prediction of the next consumed amount of traffic and of the future location where this occurs can yield a better accuracy than forecasting the two separately, when knowledge of the previous actions of the individual is taken into account. The shift between Π max u (L) • Π max u (V) and Π max u (V, L) is of 10% on average. More importantly, we note that the mean value of Π max u (V, L) is at 0.88, with the probability mass above 0.8 and a noticeable peak at 0.98. Therefore, our main conclusion is that it is possible to anticipate how much mobile data traffic (as an order of magnitude) will be consumed by a given user and where this will occur in a very effective manner (i.e., with an 88% accuracy on average), by knowing the past history of activities of the target individual.

If the available information about each user increases, and the location information can be precisely established, one can remove the uncertainty about the mobility dimension. This would improve the accuracy of the prediction, which occurs in both temporal-uncorrelated and actual cases, as shown in Fig. 2. The plot in Fig. 2(d) also portrays the range of the predictability gain: by comparing Π max u (V|L) with Π max u (V) in Fig. 1(b), we observe that including location information in the prediction process allows forecasting the future consumption of mobile data traffic with 5% higher accuracy, pushing the overall performance from 85% to 90%. Hence, our second conclusion is that using knowledge of the spatio-temporal trajectories of users can further improve the design of a prediction model targeting individual traffic volume consumption. Yet, the gain is not dramatic with respect to a technique that only relies on temporal information.

V. DISCUSSION AND CONCLUSION

Discussion: In order to understand the cause of the high (joint) predictability observed in Sec. IV, we map each user's Internet sessions into a three-dimensional space of location, time, and volume, so as to have an intuitive spatiotemporal representation. Each session becomes then a point p(l, t, v) into this space. Note that we express l as the linear ordering of the corresponding bidimentional locations, as returned by Optics [START_REF] Ankerst | Optics: ordering points to identify the clustering structure[END_REF]: a density-based cluster algorithm that places spatially close bidimentional locations as neighbors in the ordering l. Time t is expressed by hours with decimals from 0 to 24, where the date is ignored. Volume v is the magnitude of the traffic volume, i.e., log 10 (•). This mapping reveal how a user generates mobile Internet sessions. In Fig. 3(a), most sessions are aggregated on two major locations (30 and 60), probably mapping to home and working place according to their time of visits. Sessions containing data traffic over 10MB mainly occur at the location 30 during nighttime.

To quantitatively investigate the 3D space representation of p(l, t, v) points, we use DBScan [START_REF] Tan | Introduction to data mining[END_REF] to cluster each user's sessions in the three-dimensional space. For the clustering, a weighted euclidean distance is measured between every two points p 1 (l 1 , t 1 , v 1 ) and p 2 (l 2 , t 2 , v 2 ), where the distance of each dimension is computed as follows:

Each distance is applied to 99% percentile normalization. For each cluster shown in Fig. 3(a), we then use the relative cohesion (RC) to quantify the contribution of each dimension to a given cluster as RC ( * ) = p∈C dist ( * ) (p,c) 2 p∈C dist(p,c) 2 , where C and c respectively represent the cluster and its centroid c = (l centroid , t mean , v mean ). The RCs of the three dimensions satisfy RC (loc) + RC (time) + RC (vol) = 1, where 0 < RC ( * ) < 1. Hence, if a cluster's RC in one dimension is significantly smaller than the other two dimensions, this dimension is contributing the most to creating the cluster. Fig. 3(b) shows the distributions of RCs along the three dimensions for all users. The most striking behavior is the much lower RC in space than time or traffic volume: i.e., "where a user is" drives the creation of the majority of clusters: The location of a mobile user has a high probability to trigger some routine service consumption activity. Hence, anticipating the future location of a user should be the first target of a solution aiming at predicting mobile user activity. However, we also observe that locations alone do not explain all clusters. A nonnegligible fraction of clusters showing high RC in space and low RC in time and traffic volume are also present in several cases. We conclude that the three dimensions are complementary, and though different weights, they are all important for an accurate prediction of the behavior of mobile users. This is consistent with -and explains -our results on the high joint predictability of temporally correlated visited locations and consumed traffic. Conclusions: To the best of our knowledge, this is the first work to (i) show the maximum predictability of personal mobile data traffic volume and (ii) jointly consider user's location and mobile service usage in a per-user predictability analysis. Our results indicate that there is a large space for predicting mobile data traffic and adapting network optimizing solutions based on the latter, such as for load balancing.