Navikkumar Modi

Philippe Mary
email: philippe.mary@insa-rennes.fr

Christophe Moy

Transfer Restless Multi-Armed Bandit Policy for Energy Efficient Heterogeneous Cellular Network

Keywords: Energy efficiency, green cellular networks, upper confidence bound, reinforcement learning, transfer learning, multi-armed bandit

This paper proposes a learning policy to improve the energy efficiency (EE) of heterogeneous cellular networks. The combination of active and inactive base stations (BS) that allows for maximizing EE is identified as a combinatorial learning problem and requires high computational complexity as well as a large signaling overhead. This paper aims at presenting a learning policy that dynamically switches a BS to ON or OFF status in order to follow the traffic load variation during the day. The network traffic load is represented as a Markov decision process, and we propose a modified upper confidence bound algorithm based on restless Markov multi-armed bandit framework for the BS switching operation. Moreover, to cope with initial reward loss and to speed up the convergence of the learning algorithm, the transfer learning concept is adapted to our algorithm in order to benefit from the transferred knowledge observed in historical periods from the same region. Moreover, based on our previous work, a convergence theorem is provided for the proposed policy. Extensive simulations demonstrate that the proposed algorithms follow the traffic load variation during the day and contribute to a performance jump-start in EE improvement under various practical traffic load profile. It also demonstrates that proposed schemes can significantly reduce the total energy consumption of cellular network, e.g. up to 70% potential energy savings based on a real traffic profile.

Introduction

The increasing popularity of portable smart devices has flared up rising traffic demand for radio access network and has been arousing massive energy consumption, which leads to the exhaustion of energy resources and causes a potential increase of CO2 emissions. Data centers, back-haul routers and cellular access networks are the main source of energy consumption in the information and communication technology industry, which is equivalent of 2% to 10% of the global overall power consumption of human activity [START_REF] Marsan | Optimal energy savings in cellular access networks[END_REF]. In cellular networks, the energy consumption of base stations (BS) is about 60% to 80% of the overall power consumption of the cellular network [START_REF] Fettweis | ICT energy consumption-trends and challenges[END_REF]. Besides, cellular network operators require to spend more than 10 billion dollars to meet current energy consumption of the cellular network [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF][START_REF] Peng | Traffic-driven power saving in operational 3G cellular networks[END_REF], thus there exists both environmental and high economical pressures for cellular network operators to take into account an energy efficiency aspect of the network. The main reason for such high energy consumption is because BS, and more generally cellular networks, are designed on a peak traffic load basis.

In fact, due to the traffic load variation in time domain and dynamic distribution of cellular users among cells in space domain, there are opportunities for some BS to be put in sleep mode in order to achieve higher energy efficiency (EE). The side BS components, controller, air-conditioner are the main sources of energy consumption, rather than transmit power which consumes only 3.1% of the BS power consumption [START_REF] Karl | An overview of energy-efficiency techniques for mobile communication systems[END_REF]. Recent studies on the real temporal traffic have stated that BS are largely underutilized, e.g. traffic load can be below 10% of peak load during 30% and 45% of the day during weekdays and weekends respectively [START_REF] Oh | Toward dynamic energy-efficient operation of cellular network infrastructure[END_REF]. Thus, instead of just turning off radio transceivers, the BS operators may prefer to turn off the underutilized BS and transfer the imposed traffic loads to neighbor active BS during low traffic periods such as night time and/or weekend, which reduces the energy consumption [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF].

Recently, there has been a rising interest on the works dealing with switch ON and OFF BS according to the traffic load, however, it is essential for network operators to guaranty radio coverage and quality of service (QoS) to the cellular users. Dynamically switching the BS' operation mode to ON and OFF with respect to traffic load fluctuation is considered to be one of the effective methods to reduce total energy consumption of cellular network while maintaining good QoS. Moreover, BS operation mode switching decision cannot be made individually at each BS level, since it does not only depend on the load of the cell of interest but also on the load of its neighbors. For instance, a BS may not be turned to sleep mode while its neighboring BS are overloaded, even if its own traffic load is very low. The problem of EE maximization with BS switching operation is a famous combinatorial class of problem. In machine learning, combinatorial problems are mostly addressed with centralized decision made by a central controller taking into account a global information, i.e. channel state information and traffic load information.

In this work, the best BS deployment is learnt in order to maximize the network EE under QoS constraints, by switching ON/OFF some BS. The EE maximization problem is tackled under the multi-armed bandit (MAB) approach where arms are represented by the deployment configurations. MAB is a class of sequential decision making paradigm where, given a set of arms, a user selects an arm at each slot in order to collect some reward. The most important property of MAB paradigm is that a player does not need to know a prior information about each arms' reward distribution, making MAB an interesting solution for EE maximization problem. In this paper, we focus on a restless upper confidence bound policy which has been proven to be efficient for opportunistic spectrum access (OSA) problem [START_REF] Modi | QoS driven channel selection algorithm for opportunistic spectrum access[END_REF][START_REF] Robert | Reinforcement learning approaches and evaluation criteria for opportunistic spectrum access[END_REF][START_REF] Modi | QoS driven Channel Selection Algorithm for Cognitive Radio Network: Multi-User Multi-armed Bandit Approach[END_REF], where selecting an arm leads to two different rewards associated with it. In this paper, the algorithm we proposed in [START_REF] Modi | QoS driven Channel Selection Algorithm for Cognitive Radio Network: Multi-User Multi-armed Bandit Approach[END_REF], i.e. RQoS-UCB policy, is adapted to the problem of finding the optimal BS configuration that maximizes the observed energy efficiency in the long run. Moreover, the transfer learning (TL) concept [START_REF] Taylor | Transfer learning for reinforcement learning domains: A survey[END_REF][START_REF] Li | TACT: A transfer actor-critic learning framework for energy saving in cellular radio access networks[END_REF] is applied in our context, where the temporal dependence in the traffic load between two days is exploited in order to increase the convergence speed of the current learning.

Related Work

Recently, there has been a substantial body of work on traffic load-aware BS adaptation, and the authors in [START_REF] Niu | TANGO: traffic-aware network planning and green operation[END_REF][START_REF] Chiaraviglio | Energy-aware UMTS access networks[END_REF], have validated the possibility of improving EE and also showed the energy saving gains by simulations. In [START_REF] Niu | Cell zooming for cost-efficient green cellular networks[END_REF][START_REF] Li | Gm-pab: A grid-based energy saving scheme with predicted traffic load guidance for cellular networks[END_REF][START_REF] Gong | A Dynamic Programming Approach for Base Station Sleeping in Cellular Networks[END_REF], authors proposed to dynamically adjust the sleeping status of BS, depending on the learnt and predicted traffic load of the network. The works in [START_REF] Marsan | Optimal energy savings in cellular access networks[END_REF][START_REF] Marsan | Energy efficient management of two cellular access networks[END_REF] introduced some BS switching strategies for dynamic BS operations depending on daily traffic variation. However, reliable prediction of BS traffic load is still an important challenge for network operators, which limits its usefulness in practical applications. An alternative energy-efficient procedure is the relay station switching technique employed in [START_REF] Alam | Traffic-and-interference aware base station switching for green cellular networks[END_REF], where certain BS being turned to sleep mode and switched on the low-powered relay station mode during the low-traffic intervals. On the contrary, authors in [START_REF] Oh | Energy savings through dynamic base station switching in cellular wireless access networks[END_REF] introduced reinforcement learning (RL) algorithms as an application of dynamic BS switching operation, however, these algorithms are highly dependent on the a priori knowledge of the traffic load.

As stated in [START_REF] Karp | Complexity of Computer Computations[END_REF][START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF][START_REF] Li | TACT: A transfer actor-critic learning framework for energy saving in cellular radio access networks[END_REF], the problem of EE maximization with BS switching operation is a combinatorial problem, and it has been proven to be NP-hard. Instead of directly addressing this problem, the authors in [START_REF] Han | Energy-efficient base-station cooperative operation with guaranteed QoS[END_REF][START_REF] Soh | Energy efficient heterogeneous cellular networks[END_REF], adopted fixed BS switching patterns and then evaluated the call blocking probability and the outage probability. In [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF][START_REF] Kim | TAES: Traffic-aware energy-saving base station sleeping and clustering in cooperative networks[END_REF][START_REF] Gong | A Dynamic Programming Approach for Base Station Sleeping in Cellular Networks[END_REF], some greedy algorithms have been introduced to tackle BS switching operation without presenting sufficient theoretical guarantees of convergence to optimal configuration. The authors in [START_REF] Kim | TAES: Traffic-aware energy-saving base station sleeping and clustering in cooperative networks[END_REF] have taken forward a greedy algorithm to handle the trade-off between the energy consumption and the revenue in heterogeneous cellular networks. Then, [START_REF] Li | Gm-pab: A grid-based energy saving scheme with predicted traffic load guidance for cellular networks[END_REF][START_REF] Li | TACT: A transfer actor-critic learning framework for energy saving in cellular radio access networks[END_REF] used Markov decision process (MDP) to model the traffic load prediction and used a RL approach, named actor-critic algorithm [START_REF] Konda | Energy-efficient base-station cooperative operation with guaranteed QoS[END_REF], to predict the traffic load of the network without prior information about it. Moreover, authors in [START_REF] Li | TACT: A transfer actor-critic learning framework for energy saving in cellular radio access networks[END_REF] extended the actor-critic algorithm by including the TL concept [START_REF] Taylor | Transfer learning for reinforcement learning domains: A survey[END_REF] leading to Transfer Actor CriTic (TACT) algorithm in order to use the knowledge acquired in previous learning phases. Actor-critic based algorithms provide good performance but are generally more complex than upper confidence bound (UCB) algorithms. Moreover, the existing works for BS energy saving problem often lack for theoretical analysis on the convergence. On the contrary, decentralized schemes for dynamic BS switching operation [START_REF] Wong | Decentralized energy-efficient base station operation for green cellular networks[END_REF][START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF][START_REF] Zhou | Green mobile access network with dynamic base station energy saving[END_REF][START_REF] Guo | Dynamic cell expansion with self-organizing cooperation[END_REF] are more beneficial as they do not require a central controller, but demand more information exchanges. However, all the existing decentralized schemes do not present theoretical analysis on the convergence, which makes them less appealing from theoretical point of view.

We assert that problems such as channel allocation in dynamic spectrum access can be of the same nature than the problem of base station switching, i.e. restless MAB. As a consequence, works dealing with learning strategies for OSA scenario for instance can be related to our approach. In [START_REF] Tekin | Online learning of rested and restless bandits[END_REF] authors tackled the problem of MAB with Markovian rewards that can be applied to OSA or base station switching for green networking. In OSA scenario, the most common addressed optimization problem is to find the band with the highest probability to be vacant. In that case, rewards are generally modeled as binary, but some works have also dealt with continuous rewards rating the quality of the bands for instance. The authors of [START_REF] Oksanen | A sensing policy based on confidence bounds and a restless multi-armed bandit model[END_REF][START_REF] Oksanen | An order optimal policy for exploiting idle spectrum in cognitive radio networks[END_REF] considered the problem of finding the channel that gives the best data rate when data rates on channels are drawn from a Markovian distribution. But in these works, channel quality and availability have never been considered separately. In our previous works [START_REF] Modi | QoS driven channel selection algorithm for opportunistic spectrum access[END_REF][START_REF] Modi | QoS driven Channel Selection Algorithm for Cognitive Radio Network: Multi-User Multi-armed Bandit Approach[END_REF], we proposed a new restless upper confidence bound for Markovian settings in OSA problem. The proposed scheme, named restless quality of service upper confidence bound (RQoS-UCB), allows the radio for learning about the spectrum opportunities, i.e. bands that are less used by a primary network for instance, and also on a quality indicator of the bands that have been identified as unoccupied. The proposed scheme has been proven to have a logarithmic regret which is the best behavior a learning policy may have, and its ability to converge toward the best band, in terms of availability and quality as well, has been shown.

Contributions

This paper tackles the problem of EE maximization from the restless MAB framework, considering varying traffic load. The paper includes the following contributions:

• This paper adapts the UCB policy in [START_REF] Modi | QoS driven Channel Selection Algorithm for Cognitive Radio Network: Multi-User Multi-armed Bandit Approach[END_REF] to fit with the EE maximization problem. In particular, the state reward is fed-back when the BS configuration fulfils a set of constraints of the EE maximization problem. The soft reward is matched with the energy efficiency of the network. • The proposed algorithm includes a transfer learning stage in order to speed up the convergence toward the best deployment configuration. To the best or our knowledge, MAB-UCB has never been applied to the dynamic configuration by switching ON and OFF BS in order to maximize the network EE. Our algorithm that learns on the state of the network and on the energy efficiency, is proven to be efficient to solve the green networking problem.

Paper Structure

The remainder of the paper is organized as follows. Section 2 introduces the system description and EE maximization problem formulation. In Section 3, the traffic load variation is formulated as an MDP and the EE maximization algorithm, energy efficiency maximization-upper confidence bound (EEM-UCB), is presented. Moreover, the TL concept is embedded in the proposed EEM-UCB algorithm to form the TLEEM-UCB algorithm. Section 4 numerically evaluates and compares the proposed schemes with the state of the art methods and presents the validity and effectiveness. Finally, Section 5 concludes this paper and presents future way of researches.

Methods and Problem Formulation

Beforehand, Table 1 summarizes the notations in this paper.

Network Model

In this work, we consider a heterogeneous wireless cellular network comprising of a mixture of macro and small cells, each governed by a macro or micro BS respectively, where set of BS Y = {1, 2, • • • , Y } lies in a two dimensional area in R 2 . In addition, we assume that there exists a central controller, which can timely know the traffic load in the network at each instant and can predict the energy efficiency of BS at next stage. Let us assume that all BS operate in an open access mode, i.e. any MS is allowed to connect to any BS whatever it belongs to the micro or macro Prescribed minimum data rate to continue data transmission M =< S, K, P, R > MDP Tuple: state space, action space, transition probability and reward tier [START_REF] Soh | Energy efficient heterogeneous cellular networks[END_REF]. We focus on the downlink communication as mostly considered for the mobile Internet application. The network area is divided according to the Voronoi tessellation with BS acting as seeds for each cell. Each cell coverage in wireless cellular network is denoted as

P i = {P i k,l , k, l ∈ S} state transition probabilities of the i-th action A(n) a i (n) = a i 1 (n), • • • , a i Y (n) the
G i S (T i (n)) 1 T i (n) T i (n) k=1 R i S (k), the empirical mean of EE rewards G S max (n) max i∈K G i S (T i (n)), maximum expected average EE M i (n, T i (n)) G S max (n) -G i S (T i (n)) B i (n, T i (n)) EEM-UCB
I k (n), k = 0, 1, 2, • • • at time slot n.
At a given time slot, the set of active BS, denoted as Y on defines a partition of the space. Each MS in the network connects to its nearest BS, as explained in Section 2.1.2. As the set of active BS is changing from a time instant to another, MSs connect always to the nearest BS, micro or macro. Each configuration of Y on leads to a certain rate and energy consumption, whose computation is detailed in the following, and we aim at finding the configuration maximizing the energy efficiency, while guaranteeing a minimum data rate to all users.

Traffic Profile

Let x k ∈ I k (n) be the two-dimensional Cartesian coordinates, denoting the locations of MS in the coverage of the k-th BS at time slot n. An MS is referred as active when it is receiving a call. When the call ends, the MS becomes inactive and is departed from the network. Traffic load of a BS is measured in terms of the number of active MSs and their respective call duration.

At each time slot n, new and handover call at x k follows a Poisson point process with arrival rate per time-unit Λ(x k , n). The associated call duration (or file size) is assumed to be exponentially distributed with mean 1/h(x k , n). Then the instantaneous traffic load at location x k can be expressed as L(x k , n) = Λ(x k ,n) h(x k ,n) at time slot n [START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF]. By setting different arrival rates or call holding time for MSs located in different cells, this model can capture temporal and spatial traffic variability. Thus, when the set of BS Y on n is switched ON at time slot n, the instantaneous traffic load served by BS k ∈ Y on n can be expressed as:

L k (n) = x k ∈I k (n) Λ(x k , n) h(x k , n) .
On the contrary when BS k is turned OFF, the instantaneous traffic load served by BS k is defined as zero, i.e. L k (n) = 0. The total arrival rate of a BS k is the composition of all Poisson arrivals at different locations in I k , which again forms a Poisson process [START_REF] Zhang | Performance of real-time and data traffic in heterogeneous overlay wireless networks[END_REF]. Moreover, the daily traffic profile of the whole cellular network repeats periodically as recorded by several works [START_REF] Oh | Toward dynamic energy-efficient operation of cellular network infrastructure[END_REF][START_REF] Alam | Traffic-and-interference aware base station switching for green cellular networks[END_REF]. This model will be useful when considering the performance of the learning algorithms during the day.

BS Selection Rule

An MS is assumed to connect with the nearest BS, in order to suffer from the least path loss during the wireless transmission. An active MS located at x k is connected with and served by the BS k, k ∈ Y on n which presents the best received signal strength at each time slot n [1] , and where Y on n is the set of active BS at instant n.

Channel Model

The service rate of an active MS at location x k provided by the k-th BS at the n-th time slot is assumed to be equal to the Shannon capacity:

Θ k (x k , n) = B a • log 2 (1 + SINR k (x k , n)) (1)
where B a denotes the system bandwidth, SINR k (x k , n) is the received signal to interference plus noise ratio (SINR) at x k from BS k at the n-th time slot, and is defined as

SINR k (x k , n) = g k,x k (n)P tx k φg k,x k (n)P tx k + m∈Y on n \{k} g m,x k (n)P tx m + σ 2 (2)
where g k,x k (n) is the average channel gain from BS k to active MS at location x k at the n-th time slot. The channel gain only comprises path loss in this paper, but log-normal shadowing and fading can be taken into account easily without changing the principle of the learning policy that will be introduced in the next section. Moreover, P tx k is the transmission power of BS k, σ 2 is the noise power [1] Denote that an other user association metric could also be used. The optimal user association problems has been well addressed in [START_REF] Hossain | Distributed inter-bs cooperation aided energy efficient load balancing for cellular networks[END_REF][START_REF] Kim | Distributed α-optimal user association and cell load balancing in wireless networks[END_REF][START_REF] Son | Dynamic association for load balancing and interference avoidance in multi-cell networks[END_REF], however, we focus on the BS sleeping scheme rather than user association due to the space limitation. and m∈Y on n \{k} g m,x k (n)P tx m is the interference power experienced by MS x k from its neighboring BS at the n-th time slot. The parameter φ is the orthogonality (or self interference) factor, φ ∈ [0, 1], and φg k,x k (n)P tx k models intra-cell interference [START_REF] Son | Dynamic association for load balancing and interference avoidance in multi-cell networks[END_REF].

System Load

In order to satisfy the QoS requirement of MSs, a BS should provide a certain amount of resources (e.g., time or frequency) in order to absorb the MSs traffic load and provide enough service rate to users. From the system's perspective, the system load of BS k at the n-th time slot is estimated as the fraction of resource to serve the total traffic load in its coverage [START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF]

ρ k (n) = x k ∈I k (n) L(x k , n) Θ k (x k , n) . (3)
The system load denotes the fraction of time required to serve the total traffic load in the coverage of the k-th BS. Eventually, our main goal is to choose the set of active BS that maximizes the global network energy efficiency without having a prior on traffic load statistic. We will give the details in Section 3.

Power Consumption Model

The total power consumed P k T (n) by each BS k at the n-th time slot can be expressed as [START_REF] Fehske | Energy efficiency improvements through micro sites in cellular mobile radio networks[END_REF]:

P k T (n) = a k P tx k (n) + P k f (4)
where, P tx k (n) denotes the transmission power of BS k at the n-th time slot and P k f denotes the static power consumption independent of P tx k (n) and includes all electronic circuit power dissipation due to site cooling, signal processing hardware as well as battery backup systems. a k is a BS power scaling factor which reflects both amplifier and feeder losses.

Problem Formulation

The energy efficiency of a cell k in bits per joule at instant n, is the ratio between the data sum-rate of the cell over the power used to run the cell. The network EE is then the aggregate EE of each cell and can be expressed as [START_REF] Alam | A scalable multimode base station switching model for green cellular networks[END_REF]:

EE(n) = k∈Y on n x k ∈I k (n) Θ k (x k , n) P k T (n) (5)
EE maximization in the cellular network, without power allocation strategy, can be reduced to find the set of active BS that maximizes [START_REF] Peng | Traffic-driven power saving in operational 3G cellular networks[END_REF]. The problem can be formally written as

Y on * n = arg max Y on n    k∈Y on n x k ∈I k (n) Θ k (x k , n) P k T (n)    (6a) s.t. 0 ≤ ρ k (n) ≤ ρ th , ∀k ∈ Y on n (6b) Θ k (x k , n) ≥ Θ min , ∀x k ∈ I k (n), ∀k ∈ Y on n (6c) Y on n = ∅ (6d)
Like in [START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF][START_REF] Li | TACT: A transfer actor-critic learning framework for energy saving in cellular radio access networks[END_REF], a system load threshold ρ th ≤ 1 is introduced as a constraint, (6b), in order to keep the system stable. Indeed, the service rate of a user, i.e. Θ k (x k , n), should be sufficient to absorb the traffic load at x k . If not, some transmissions may be delayed and should be taken into account in the model, which is out of scope of the paper. For instance, low threshold value ρ th indicates that BS would operate in a more conservative manner with low delay and low call dropping probability for MSs since all calls can be routed to users. On the contrary, with a high threshold ρ th value close to 1, the data rate of users is just enough to avoid overflow implying a limited power consumption but with an increasing call dropping probability. The constraint (6c) guarantees a minimum data rate Θ min to each active user and constraint (6d) states that there is at least one active BS.

The above problem can be proven to be NP-complete by reducing from a vertex cover problem [START_REF] Karp | Complexity of Computer Computations[END_REF][START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF]. Finding the set of active BS maximizing network EE by an exhaustive search is very costly in computational resources since 2 Y -1 ON/OFF combinations have to be tried, specifically when the number of BS is large. This problem can rather be tackled under MAB approach where a specific combination is tried at each iteration and a reward (EE of the system) is collected. In the next section, we will show how this principle can lead to a good state.

RL for Energy Efficient Network

System Model

The dynamic BS switching problem is modeled as an MAB under Markovian settings. Figure 1 illustrates the principle of the learning policy with MAB approach where an arm represents different configuration of BS' activity. We defined an MDP for BS switching operation as a tuple M =< S, K, P, R >, where S denotes the state space, K denotes the action space, P denotes a state transition probability matrix, and finally R is a reward function associated with S, K and P. At each iteration, the controller chooses an action

i among |K| = 2 Y -1 possible actions, i.e. a i (n) = a i 1 (n), • • • , a i Y (n) where a i k (n) = 1 if BS k is switched ON
in action number i at time n and 0 otherwise. This action leads the network to a given state S i (n) ∈ {0, 1}, where S i (n) = 1 if all constraints from (6b) to (6d) are satisfied and 0 otherwise.

Due to the random process governing the time evolution of the traffic load, the state S i (n) transforms into S i (n + 1) at the next time instant according to a transition probability measure for arm i, i.e. P i = {P i k,l , k, l ∈ S, i ∈ K}. Moreover, the Markovian process is considered as stationary, on a short time period e.g. 1 hour, and hence the distribution of this MDP is such as π i S (n) = π i S , ∀n. The reward achieved in state S i from the BS switching operation i after n time slot is, without loss of generality, equal to the value of the state, S i (n), i.e. 0 or 1. In addition, we consider that the network EE achieved by switching BS status according to the action number i is the second reward, i.e. R i S (n) = EE(n), computed from (5) for a given environment state S i (n). The reward on EE and the state are fed back to the controller in order to decide the next action to take. The mean reward µ i associated with BS switching operation i under stationary distribution π i S is given by:

µ i = S∈S S i G i S π i S ,
where

G i S (T i (n)) = 1 T i (n) T i (n) p=1 R i S (p) (7)
where T i (n) refers to the number of times the BS switching operation i has been performed by the controller up to time n. The policy A is a one-to-one mapping such as at each time slot n, a BS switching operation i is selected:

A : N -→ K n -→ i
The goal of a RL policy is to minimize its regret on the long run, i.e.

Φ A (n) = nµ * -E n t=1 S A(t) (t)G A(t) S A(t) (t) (8)
where the expectation E is taken over the states and observed reward. Let S A(t) be the state observed by using the policy A at time slot t. Moreover, µ * is the optimal mean reward obtained by always selecting the best action at each time t.

Restless Energy Efficiency Maximization Upper Confidence Bound (EEM-UCB)

In this section, we adopt the restless UCB policy, i.e. RQoS-UCB, that we proposed in [START_REF] Modi | QoS driven Channel Selection Algorithm for Cognitive Radio Network: Multi-User Multi-armed Bandit Approach[END_REF] for learning the best bands in OSA context based on their probability to be free and the quality of the band. The principle of the algorithm is adapted to the current problem, where the policy aims at finding an optimal set of active BS which maximizes the energy efficiency of the network, and will be named EEM-UCB.

When dealing with an MAB problem, one should first ask if it belongs to rested or restless category. In the former category, the state of the Markov chains corresponding to arms that are not played does not evolve with time and only the Markov chain of the selected arm does. In the later, states of all Markov chains continue to evolve whatever they are selected or not. Our problem fits with the later category. Indeed, the traffic request of users does not depend on selected BS however, the selected configuration definitely influences the traffic load of the network by distributing the data flow among BS. EEM-UCB algorithm operates in a block structure as represented in Fig. 2 which is based on regenerative cycle [START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF][START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF]. Each block is divided into three sub-blocks, SB1, SB2 and SB3. For each arm i, a regenerative state ζ i is defined, i.e. 0 or 1 in our case, and SB1 comprises all time slots from the selection of configuration i to the first visit of the state ζ i . SB2 contains all time slots from the first visit to ζ i up to, but excluded, the second visit to ζ i . The last block is only the second visit to the state ζ i . The selection of the active BS set is based on an index computation B i (n) for configuration i and will be formally expressed in the next section. The computation of the index occurs after the completion of SB3. The reason of this structure lies on the restless nature of arms which evolve even if they are not played. The distribution of the state reward obtained by playing a given arm, is function of the time elapsed since the last time the same arm has been played. In order to deal with an homogenous Markov chain, the stay in a given arm should be sufficiently long in order to reconstruct a sample path with the same statistical characteristic of the Markov chain governing the arm [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF]. It is worth noting, however, that this structure does not prevent to collect rewards, state and EE, in any blocks. This sub-division just comes for mathematical convergence proof.

At a given time slot n, policy A selects the BS switching operation that has the highest policy index B i (n, T i (n)) at time n. This action may transform the current state S i (n) of the network to another state S i (n + 1) with certain probability P. The new reward R i S (n), i.e. energy efficiency, is fed back to the controller. Then, the policy A updates the policy index B i (n + 1, T i (n + 1)) with the empirical average on the state S i and the empirical mean of the energy efficiency experienced so far. The algorithm repeats the above procedure until convergence to optimal BS switching operation during each hour of operation. The formal description of the index computation is given in Section 3.3.

Transfer Learning EEM-UCB (TLEEM-UCB) Policy

The previous strategy may suffer from traffic load variation from one day to another at a given period of time due to the variation of Poisson arrival rate between two consecutive days. This rather advocates for learning from scratch at each new day with the new, unknown, statistic characterizing the underlying Markovian process. In that case, the network would loose time to re-learn the best deployment configuration it learnt the day before at the same hour. Another strategy would consist in using the previous knowledge the controller learnt during some historical periods to find the current optimal BS switching operation. This strategy would make even more sense as per Poisson arrival rate does not change too much between two consecutive days as we will see in Section 4.

The motivation for transfer learning is to utilize previous learnt features on a given task (source task) in order to speed up the learning phase of different features on a target task as illustrated in Fig. 3. In other words, the controller uses the BS deployment learnt in previous time period for the current task with its own statistical characteristics. We hence propose a new policy update method, named Transfer Learning EEM-UCB (TLEEM-UCB) policy that is detailed in Algorithm 1. In the source policy, the reward achieved in state S i,h from a BS switching

operation i ∈ K during H i 2 time slots is S i,h (H i 2 )
, where H i 2 is the number of time slots the BS switching operation i has been selected in SB2 block in the source task as reminded in Table 1. Meanwhile, the observed reward associated with energy efficiency by selecting a BS switching operation i is R i,h S (H i 2 ) during H i 2 source task observations in SB2.

At the end of each block b, Algorithm 1 returns a BS switching operation index maximizing the policy index, B i,h (n 2 , T i ) ∀ i ∈ K, which has to be selected for the next block of operation, i.e. steps 2 and 3. The index computation is done according to three terms: where Si,h (T i 2 ) is the empirical mean of the observed states obtained with action i considering the time period in the source task and in the current task. As reminded in Table 1, T i 2 is the number of times action i has been selected in SB2 block up to time n 2 in the current task. The empirical mean is expressed as

B i,h (n 2 , T i 2 ) = Si,h (T i 2 ) -Q i,h (n 2 , T i 2 ) + A i,h (n 2 , T i 2 ), ∀i (9)
Si,h (T i 2 ) = T i 2 t=1 S i (t) + H i 2 t=1
S i,h (t)

T i 2 + H i 2 , ∀i. (10)
The second term, i.e. Q i,h (n 2 , T i 2 ), is computed similarly than in RQoS-UCB policy [START_REF] Modi | QoS driven Channel Selection Algorithm for Cognitive Radio Network: Multi-User Multi-armed Bandit Approach[END_REF] but including source task observations:

Q i,h (n 2 , T i 2 ) = βM i,h (n 2 , T i 2 ) ln(n 2 + H i 2 ) T i 2 + H i 2 , ∀i, (11)
where,

M i,h (n 2 , T i 2 ) = G S max -G i,h S (T i 2 ), ∀i, and
G i,h S (T i 2 ) = 1 T i 2 T i 2 k=1 R i S (k) + 1 H i 2 H i 2 k=1 R i,h S (
k) denotes the empirical mean of EE reward, i.e. R i S , collected in the current task in SB2 block by applying action i in state S plus the total mean EE reward gathered in source task. Moreover,

G S max = max i∈K G i,h S (T i 2 )
is the maximum reward within the set of BS switching operations from current and historical observations in state S. Finally, the bias term A i,h (n 2 , T i 2 ), is defined as

A i,h (n 2 , T i 2 ) = α ln(n 2 + H i 2 ) T i 2 + H i 2 , ∀i. (12)

Algorithm 1 TLEEM-UCB policy

Require: Transferred Observations : h : total historic time, h 2 : total historic time in SB2 block, H i 2 : total historic time action i has been selected, b h : total blocks in historical observations R i,h S (t), S i,h (t) ∀i ∈ K, 1 ≤ t ≤ H i 2 : Reward and state observed in historic data, Current policy initialization: b = 0, n = 0, n 2 = 0, T i 2 = 0, α, β, ζ i R i S (0) and S i (0). Ensure: A(n + 1)

1: while (1) do 2:

B i,h (n 2 , T i 2 ) = Si,h (T i 2 ) -Q i,h (n 2 , T i 2 ) + A i,h (n 2 , T i 2 ), ∀i 3: A(n) = arg max i B i,h (n 2 , T i ) 4: while S i (n 2 ) = ζ i do 5: n = n + 1 and A(n) = i // Start SB1 sub-block 6:
Activate configuration i and Observe S i (n 2 ) 7:

end while 8:

n = n + 1, n 2 = n 2 + 1, T i 2 = T i 2 + 1 and A(n) = i; // End of SB1, start SB2 9:
Observe current state S i (n 2 ) and update R i S (n 2 ) 10:

Update Si,h (T i 2 ), Q i,h (n 2 , T i 2 ) and A i,h (n 2 , T i 2 ) as of (10), ( 11) and (12), respectively 11:

while

S i (n 2 ) = ζ i do 12: n = n + 1, n 2 = n 2 + 1, T i 2 = T i 2 + 1 and A(n) = i; // Start SB2 sub-block 13:
Observe current state S i (n 2 ) and update R i S (n 2 ) 14:

Update Si,h (T i 2 ), Q i,h (n 2 , T i 2 ) and A i,h (n 2 , T i 2 ) as of (10), ( 11) and (12), respectively 15:

end while 16:

b = b + 1, n = n + 1 and A(n) = i // Start of SB3 sub-block 17: end while
It is worth noting that it exists a class of bandit algorithms that uses side information. This kind of bandits is sometimes called contextual bandit or bandit with feedback [START_REF] Wang | Bandit problems with side observations[END_REF]. Expert systems described in [START_REF] Cesa-Bianchi | Prediction, Learning and Games[END_REF] can also be seen as a generalization of learning with side observations. The main idea of bandits with side information is that at each time instant, and before taking a decision, the player is able to observe a realization of a random variable, or a linear function of it, that is called side information, in order to produce a next estimate closer to the real value that is searched. On the other hand, transfer learning aims at using the index B i of each arm i, computed previously, to initialize the algorithm in order to achieve a jump-start in the convergence rate, that makes transfer learning a quite different approach than bandits with side information.

Convergence Analysis of TLEEM-UCB

In this section, the total number of suboptimal plays is upper-bounded and established under the following condition 1 on the arms.

Condition 1 All arms are finite-state, irreducible, aperiodic Markov chains whose transition probability matrices have irreducible multiplicative symmetrization, and the state of non-played arms may evolve.

Let us consider G

i q ≥ 1 πmax+π i q and β ≥ 84S 2 max r 2 max G 2 max π2 max / min ∆µ R i M min .
We present an upper bound on the total expected number of plays of suboptimal arms in Theorem 1.

Theorem 1 Assume all arms follow condition 1. Let π min , πmax , S max , r max , ε min , M min , ∆µ i and Ω i max defined as in Table 1. The total expected number of plays of suboptimal BS configuration is upper-bounded by:

E[T i,h (n)] ≤ 1 π i min + Ω i max + 1 l + + 4 π min ∞ t=1 (t + H * 2 )
where,

l + = max 0, 4α ln n 2 + H i 2 (∆µ i ) 2 -H i 2 (13)
Proof A sketch of proof of Theorem 1 is provided in Appendix A and follows the same steps as in [10, Th. 1] considering transferred observations. Note that the above bound reduces to the bound of EEM-UCB policy, which is the bound of RQoS-UCB policy [10, Th. 1], when the transferred knowledge is not available (i.e. H i 2 = 0, ∀i).

Complexity and scalability issues

TLEEM-UCB is an index based algorithm. The complexity of the index computation is small. At each iteration in SB2, it requires the evaluation of ( 10), ( 11) and ( 12). ( 10) is nothing but a moving average that only requires one addition and one division at each iteration since other values have been recorded during previous iterations. ( 11) requires a log operation, two multiplications (but one with a constant which is less complex than a multiplication between two varying terms), one division and a moving average for evaluating M at each iteration. Finally, the bias term ( 12) requires a multiplication (with a constant) of the log term already computed once, a division and a square root evaluation at each iteration. The low amount of computation and the long period between two iterations makes it negligible compared to the simplest signal processing operation to be done at PHY layer for instance.

The algorithm complexity of TLEEM-UCB is linear with the number of combinations, but the later is exponential with the number of base stations, i.e. 2 Y -1. But this complexity is entirely concentrated in the first initialization phase where the algorithm explores all combinations once in order to give an index to each configuration. Once this has been done, only one BS configuration is tested for the index computation at a given time, hence with the computational complexity mentioned above. Moreover and thanks to transfer learning, initialization phase does not need to be repeated each day, since algorithm uses the best indexes previously learnt in historical periods, to start the new learning phase. A large network will impact the convergence time of the algorithm, since the best configuration needs to be found in a larger set cardinality, but it does not increase the computational complexity. The convergence time would be far too long for a network with 50 base stations for instance. However, one can imagine to have a learning algorithm to control a cluster of few base stations and not the entire network. Coordination among clusters could be done in a higher level in the network, but this is beyond the scope of the paper. Finally, it is worth noting that actor-critic algorithm in [START_REF] Li | TACT: A transfer actor-critic learning framework for energy saving in cellular radio access networks[END_REF] and decentralized greedy in [START_REF] Wong | Decentralized energy-efficient base station operation for green cellular networks[END_REF] belong to the larger class of Q-learning algorithms whose algorithmic complexity is significantly larger than the computation of an index in an UCB policy.

The algorithm relies on the feedback of energy consumption metric of each cell at the central entity. However, base stations already record the data rate and the transmit power allocated to each user. By monitoring also its own power consumption, an estimation of energy efficiency can be computed. Computed EE only needs to be transmitted over a certain number of bytes, to the central controller leading to a negligible amount of overhead added on fronthaul links. However, the time needed to put decision into action is not equal to zero. The exact evaluation of the time needed to collect measurements, providing a reward, switch on/off a set of BS, would take a certain amount of time that depends on the data used to build a statistic, e.g. average consumed power, and other technological constraints. These features are, of course, of great importance in a real deployment experiment but require much more investigations including implementation in a real platform and are left for further works. We will see in the next section that the proposed algorithms converge around 3000 iterations. If the time lag between the collection of data and the configuration change is 1 second, convergence occurs after 1 hour. However, the algorithm continuously performs the index computation according to the received frames in the network and never stops running such that the base station configuration is continuously changed during the day according to the traffic measured in the network.

Results and Discussion

In this section, the performance of our proposed energy efficient dynamic BS operation algorithm is investigated through extensive simulations under practical configurations similar to [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF][START_REF] Li | TACT: A transfer actor-critic learning framework for energy saving in cellular radio access networks[END_REF][START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF]. We consider an heterogeneous cellular network topology consisting of 5 macro and 5 micro BS arbitrarily deployed in an area of 5 × 5 km 2 . Furthermore, the call arrival rate at location x k follows a Poisson point process with intensity Λ(x k , n) which may vary between source and target task as summarized in Table 2 and the average file size of each call is 1/h(x k , n) = 100 Kbyte. Maximal macro and micro BS transmission powers are set to 20 and 1 W respectively, while the maximum operational power consumption for macro and micro BS are 865 W and 38 W, respectively. The COST 231 modified path loss model is used for radio propagation environment, with macro and micro BS heights are set to 32 m and 12.5 m, respectively similar than in [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF][START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF][START_REF] Li | TACT: A transfer actor-critic learning framework for energy saving in cellular radio access networks[END_REF]. In order to guarantee system reliability, system load threshold ρ th = 0.6 is considered for all BS [START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF] and the minimum bit rate Θ min is set to 122 kbps [START_REF] Alam | A scalable multimode base station switching model for green cellular networks[END_REF] for each active user. The intra-cell interference factor φ is set to 0.01 and the exploration parameters for EEM-UCB and TLEEM-UCB policies are α = 0.25 and β = 0.32. As per [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF], a homogeneous user distribution with intensity Λ = 10 -4 corresponds to 10% of BS utilizations in a case where all BS are switched ON, this value is taken as reference in the analysis on the influence of traffic load variation on the performance of proposed policy. Table 2 summarizes all the parameters used for the simulations.

Convergence Analysis

Fig. 4 compares the convergence behaviors of the proposed EEM-UCB and TLEEM-UCB algorithms w.r.t. the Actor CriTic (ACT) [START_REF] Li | Energy saving through a learning framework in greener cellular radio access networks[END_REF], decentralized greedy [START_REF] Wong | Decentralized energy-efficient base station operation for green cellular networks[END_REF] and Transfer Actor CriTic (TACT) [START_REF] Li | TACT: A transfer actor-critic learning framework for energy saving in cellular radio access networks[END_REF] policies. The cumulative energy efficiency ratio (CEER) is presented for all policies in Fig. 4 which is defined as

CEER π =
EE policy π EE when all BS are ON Moreover, the global optimal solution achieved by an exhaustive search, and referred as ideal policy, is also shown in Fig. 4. The figure shows the behaviors of the policies in terms of CEER after 3000 iterations for 4 configurations of arrival rates in source, i.e. Λ source , and current tasks i.e. Λ target . These curves can be seen as the evolution of the network EE at a given hour of a day with a given arrival rate.

As depicted in Fig. 4, the network utilities of all algorithms tends to increase with time since their confidence on the best deployment strategy increases as the time elapses. However, the performance of all algorithms largely depends on the difference between the source and target task arrival rates. Our policies, EEM-UCB and TLEEM-UCB, converge towards the ideal policy, while ACT, TACT and decentralized greedy algorithms achieve a far suboptimal solution after 3000 iterations. The lower convergence rate of ACT and TACT algorithms is clear regarding these results. Our policy TLEEM-UCB generally performs better than all the others except when the source and target arrival rates are quite different, i.e. Fig. 4(d). From Fig. 4(a) to Fig. 4(d), the source arrival rate is fixed to Λ source = 0.05 × 10 -4 and the target arrival rate varies from Λ target = 0.05 × 10 -4 to Λ target = 2 × 10 -4 . The transfer learning procedure is the most beneficial when Λ source = Λ target , Fig. 4(a) since TLEEM-UCB achieves performance jump start in the beginning and quickly converge towards the best configuration. On the contrary on Fig. 4(d), when the source and target arrival rates are significantly different, i.e. Λ source = 0.05 × 10 -4 and Λ target = 2 × 10 -4 , transferred knowledge impacts the learning in a negative way and thus TLEEM-UCB performs worse than EEM-UCB. In that case, it is more beneficial to learn from scratch since the previously computed indexes B i ∀i has to be forgotten to learn a better configuration. From these results, we can state that temporal knowledge transfer improves the convergence speed of classical MAB approaches, but it also affects in a negative manner if traffic loads in a source and target environments are significantly different. The execution time needed for convergence does not exceed few minutes in a standard simulation platform using Matlab, since one iteration basically consists in the computation of the index B i,h , which does not exceed few milliseconds. Fig. 5 presents the improvement in CEER of our algorithm when using TL concept compared to non transferred knowledge, i.e.

CEER performance of improvement

= CEER T LEEM -U CB -CEER EEM -U CB CEER EEM -U CB
On can observe that the TL concept allows a performance jump-start at the early iterations compared to the simple EEM-UCB. The maximum rate of improvement is around 500 iterations and is as much better than the source and target arrival rates are similar. For instance, a gain about 28% is achieved after 500 iterations when Λ source = Λ target = 0.05 • 10 -4 but reduces to only 5% when Λ target = 2 × 10 -4 . For this setting, the improvement of TLEEM-UCB w.r.t. EEM-UCB is even negative after 3000 iterations, i.e. -5%, meaning that TL has a negative impact on the longrun on the network EE compared to EEM-UCB. Finally, Fig. 6 shows how the network energy efficiency decreases when the number of BS increases. In that figure, the percentages of macro and micro BS are 50-50%, and the same settings than on Table 2 are used. Network EE reduces because the optimal configuration is not necessarily achieved after 3000 iterations, specially for high number of BS. Hence the selected configuration is not the optimal one and the gap increases as the number of BS increases as it can be inferred with the ideal policy. The larger the number of base stations, the larger the exploration space cardinality making the convergence to the optimal configuration longer. EE achieved with the ideal policy always increases or remains constant w.r.t. the number of BS. Indeed, the larger the BS density, the larger the data rate, at least up to a limit where the interference generated by co-channel transmissions prevents from increasing the spectral efficiency. Hence, always selecting the best configuration of active BS increases the data rate and hence EE, in this configuration. We can also note the gain of learning policies compared to a scenario where all BS are always ON. It is also worth mentioning that the achieved EE with Decentralized Greedy finishes to outperform TLEEM-UCB when the number of BS is larger than 15 in this configuration, due to a more efficient search of a local optimum when the problem dimension begins to be high. However, Decentralized Greedy requires to exchange informations between nodes and hence the traffic overhead increases as the number of BS increases.

Performance under Periodic Traffic Load

We also investigate the effectiveness of the proposed learning framework when traffic loads periodically fluctuates. As stated in Section 2, real traffic load follows a periodical pattern that can be approximated by a sinusoidal function as in [START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF]. Fig. 7 compares the network EE achieved with our policies, i.e. EEM-UCB and TLEEM-UCB, with the previously introduced state-of-the-art algorithms, i.e. ACT, TACT and Decentralized Greedy, when traffic load is fluctuating during the day. On can first remark that all policies behave the same, except Decentralized Greedy which is inferior, at high traffic load from noon to 22h. Indeed, in high traffic load all BS need to be switched ON in order to satisfy the demand and hence all learning policies logically converge to the full deployment. Decentralized Greedy tends to switch OFF some BS, even in high traffic load, in order to save energy leading to a loss in EE. On the other hand, in lower traffic period, i.e. night time, less BS need to be switched ON to meet the QoS requirements and hence learning strategies make sense to optimize the network EE. In these time slots (1am to Network Energy Efficiency (bits/Joule)

Network Energy Efficiency

Ideal Policy EEM-UCB ACT TLEEM-UCB TACT Decentralized Greedy

Figure 7 Network EE obtained with several learning algorithms with respect to time 8am), TLEEM-UCB achieves significantly higher EE compared to other algorithms from literature and reaches 95% of the maximum achievable EE, i.e. ideal policy. Moreover, TLEEM-UCB outperforms its counterpart, i.e. TACT, of about 34%. It also confirms that transferred learning improves the performance compared to non transferred knowledge policy, i.e. EEM-UCB, of about 23%. Fig. 8 depicts the average percentage of energy savings achieved by the learning algorithms and the ideal policy during one day. The energy saving percentage is measured w.r.t. to the energy expenditure of a full deployment. As shown in Fig. 8, a large amount of energy saving is achieved by the proposed TLEEM-UCB policy, e.g. about 70% during low traffic load period (night time). Moreover, the difference between the ideal policy and TLEEM-UCB policy is less than 5%. On the contrary, ACT, TACT and EEM-UCB algorithms achieve only about 60% of energy saving. Decentralized Greedy procedure allows the most important energy saving gain which nearly equals the ideal policy performance in the night time. On can also remark that the later policy allows 20% of energy saving during high traffic period by putting more BS into sleep mode, since the energy consumption is privileged. This improvement comes at the cost of user experience and comparatively less network EE as it has been observed in Fig. 7.

The impact of learning algorithms on the actual deployment of the network is also of great interest for operators. Figs. 9 and 10 represent the average number of active BS and the average number of switches that are performed at each time of the day, respectively. Fig. 9 gives insight on the average number of BS that is needed to be switched ON in order to meet the traffic variation along the day. As expected, the average number of BS needed at the night time is less than the one required at the peak period, leading to an increase of network EE and a decrease of energy consumption in night time as corroborated by Figs. 7 and 8 respectively. During the night time, Decentralized Greedy, TACT and ACT are the policies activating the less number of BS in that order. Our policies come after with an average of 5 BS switched ON, close to the optimal average number around 5.5, allowing higher EE than their counterparts. During the peak load in the afternoon, almost all policies activate the whole set of BS. Decentralized Greedy fluctuates around 8.5 BS in average allowing larger energy saving gain but lower EE. It is worth noting that the proposed policies, i.e. EEM-UCB and TLEEM-UCB, activate more micro BS than macro BS to cope with the varying traffic load and to save energy in the same time.

The results presented in Fig. 10 are important because of some practical constraints, i.e. time needed to turn ON/OFF the power amplifier (PA), lifetime of the PA. Indeed, if a learning policy requires to switch PA too often in each time slot, then it will significantly reduce the lifetime of PA and may cause additional power loss due to the initial burst of power consumption when an equipment is switched ON (non taken into account in this work). Our proposed policy, TLEEM-UCB, requires an average about 2 BS mode switches at each time slot in low load period (night time) which is significantly less compared to 5 mode switches with ACT and TACT algorithms in the same period while a little more than 3 switches are needed without TL, i.e. EEM-UCB. All algorithms but Decentralized Greedy do not require BS switches during high traffic periods. Whereas Decentralized Greedy, requires between 1 and 2 BS switches all along the day, irrespective of the traffic load. To conclude this part and to shed the light on the transfer learning feature, let us assume that the average traffic load variation is very small from one day to another at the same day-time, i.e. Λ source ≈ Λ target , which is a reasonable assumption, excepted between a week-day and a week-end day or between two consecutive days with occasional and exceptional events as it has been reported in [START_REF] Oh | Dynamic base station switching-on/off strategies for green cellular networks[END_REF]. As mentioned in Section 3.5, if one second is taken between two configuration switches, stable configuration is roughly achieved after one hour, which may appear relatively high. However, the applicability of TLEEM-UCB has to be thought on the long run, e.g. one week. Indeed, let us consider the particular time-range 10:00-11:00 am during the week. On Monday, the algorithm runs during one hour and saves the configuration achieved at 11:00 am. The next day at 10:00 am, the network just applies the configuration learned the day before and keeps like it is all along the week on the range 10:00-11:00 am without running again the algorithm. This strategy could be applied for each one hour-slot of the day during the first or two first days of the week and network just applies the computed configurations at each time slot for the rest of the week. Of course, this strategy does not work if important variations of the average traffic at a given time and between two days are observed, as it can be inferred in Fig. 4(d).

Conclusion

In this paper, the problem of BS switching operation for EE maximization in heterogeneous wireless cellular network has been tackled under the restless MAB framework. A reinforcement learning algorithm originally proposed in OSA scenario, has been adapted to deal with the optimal BS deployment in order to increase the global network EE. Furthermore and in order to increase the convergence rate of our EEM-UCB algorithm, we proposed to use the learnt knowledge acquired in previous time periods, leading to TLEEM-UCB policy. Our proposed algorithm has been proven to converge to an optimal solution as long as Markov chains governing the arms obey to certain conditions. Extensive numerical analysis shown the ability of our proposed policy to converge to the optimal deployment, maximizing EE. Transfer learning has been shown to be an effective solution to increase the convergence rate of our UCB algorithm when source and target arrival rates are not too different. Moreover, our policies have been shown to be able to follow a practical periodic traffic fluctuation. TLEEM-UCB can achieve 95% of EE achieved by the optimal BS configuration and up to 70% energy saving gain when traffic load is low (night time). Future work may include other index-based policies, such as Thomson sampling or Bayesian-UCB, that are known for their high performance in terms of regret in other scenarios. Moreover, spatial knowledge transfer between cells may also be of great interest for operators in a dynamic environment.

Appendix A: Sketch of Proof of Theorem 1

The regret of TLEEM-UCB policy is governed by the expected number of plays, E[T i,h (n)], for any suboptimal BS switching operation i. Let l be a positive integer. Let us remind that µ i = S∈S S i G i S π i S . Following the steps as in [START_REF] Modi | QoS driven Channel Selection Algorithm for Cognitive Radio Network: Multi-User Multi-armed Bandit Approach[END_REF] and including the historic time, the number of blocks a BS switching operation (action) i has been selected up to block b(n) can be expressed as

F i,h (b) = 1 + b t=2 Y 1{a(t) = i} (14)
F i,h (b) = l + b t=2 Y 1{a(t) = i, T i 2 (t -1) ≥ l} (15) = l + b t=2 Y 1{B * ,h (t -1, T * 2 (t -1)) ≤ B i,h t -1, T i 2 (t -1) , T i 2 (t -1) ≥ l} (16)
≤ l + b t=2 Y 1{∃ω i : l ≤ ω i ≤ t -1, B i,h (ω i , t) > µ * } + 1{∃ω * : 1 ≤ ω * ≤ t -1, B * ,h (ω * , t) ≤ µ * } ( 17
)
where the lower bound in the summation in [START_REF] Chiaraviglio | Energy-aware UMTS access networks[END_REF] comes from the fact that each BS configuration are tried at least once, [START_REF] Niu | Cell zooming for cost-efficient green cellular networks[END_REF] comes from the fact that each action has been sensed at least l blocks up to block b. [START_REF] Li | Gm-pab: A grid-based energy saving scheme with predicted traffic load guidance for cellular networks[END_REF] comes from the reason why suboptimal action i is chosen, i.e. the index of the optimal action at block t -1, B * ,h (T * 2 (t -1), t -1), is below the index of the suboptimal action i. Moreover ( 16) is upper bounded by [START_REF] Gong | A Dynamic Programming Approach for Base Station Sleeping in Cellular Networks[END_REF] because these two conditions are not exclusive. Taking the expectation on both sides and using union bound we get:

E[F i,h (b)] ≤ l + ∞ t=1 t-1 ω i =l P(B i,h (ω i , t) > µ * ) + ∞ t=1 t-1 ω * =1
P(B * ,h (ω * , t) ≤ µ * ) [START_REF] Marsan | Optimal energy savings in cellular access networks[END_REF] The summation over t starts from 1 instead of 2 Y because it does not change the validity of the upper bound. Let remind that G i,h S (T i 2 ) = 1

T i 2 T i 2 k=1 R i S (k) + 1 H i 2 H i 2 k=1
R i,h S (k) denotes the empirical mean of quality observations R i S for action i in state S, G S max = max i∈K G i,h S (T i 2 ) is the maximum empirical reward and G * is the empirical mean of the reward of the optimal action * , optimal in terms of both state and EE reward µ * . it does not necessarily mean that G * = G S max . Moreover, let's remind that ∆µ i = µ * -µ i . let's choose l = 4α ln (n2+H i 2 )

(∆µ i ) 2
and proceed from [START_REF] Marsan | Optimal energy savings in cellular access networks[END_REF]:

E[F i,h (b)] ≤ 4α ln n 2 + H i 2 (∆µ i ) 2 + ∞ t=1 t-1 ω i = 4α ln (n2+H i 2 ) (∆µ i ) 2 P(B i,h (ω i , t) > µ * ) + ∞ t=1 t-1 ω * =1 P(B * ,h (ω * , t) ≤ µ * ) (19)
We first start bounding the first part of (19), i.e. P(B i,h (ω i , t) > µ * ). Substituting B i,h (ω i , t) by its expression, and following the same steps than in [10, Appendix A] but using the number of times action i has been selected in SB2 block, i.e. H i 2 , we end up with

P(B i,h (ω i , t) > µ * ) ≤ S∈S N h i exp      - ω i + H i 2 ∆µ i 2 +D i,h (ω i ,t) r i S |S|G i,h S πi S 2 ε i 28      (20)
where πi S = max π i S , 1 -π i S , πmax = max i∈K πi S and i = 1 -λ i 2 is the eigenvalue gap of action i, defined as the difference between 1 and the second largest eigenvalue of the i-th Markov chain. Moreover, [START_REF] Alam | Traffic-and-interference aware base station switching for green cellular networks[END_REF] follows from [START_REF] Lezaud | Chernoff-type bound for finite markov chains[END_REF]Th. 3.3] . Consider an initial distribution h i as defined in [START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF], N h i can be upper-bounded by 1/π min where π min = min S∈S π i S . By following the same steps than in [10, Appendix A] we get from [START_REF] Alam | Traffic-and-interference aware base station switching for green cellular networks[END_REF],

P(B

where G max ≡ G S max , r max = max S∈S,i∈K r i S , M min = min i∈K M i,h ω i , S max = max i∈K S i and min = min i∈K i . Inserting [START_REF] Oh | Energy savings through dynamic base station switching in cellular wireless access networks[END_REF] into first part of [START_REF] Marsan | Energy efficient management of two cellular access networks[END_REF], and following the same steps than in [START_REF] Modi | QoS driven Channel Selection Algorithm for Cognitive Radio Network: Multi-User Multi-armed Bandit Approach[END_REF] we end up with

∞ t=1 t-1 ω i =l P(B i,h (ω i , t) ≥ µ * ) ≤ |S i | π min ∞ t=1 t + H i 2 -2 (22)
where ( 22) is obtained for of β ≥ 84S

Furthermore, due to presence of transferred knowledge, we consider l + = max 0, 4α ln (n2+H i 2 )

(∆µ i ) 2 -H i 2
instead of l and the following bound follows from combining [START_REF] Karp | Complexity of Computer Computations[END_REF] and [START_REF] Soh | Energy efficient heterogeneous cellular networks[END_REF]. Then, from [START_REF] Marsan | Optimal energy savings in cellular access networks[END_REF]:

E[F i,h (b)] ≤ l + + |S * | π min ∞ t=1 (t + H * 2 ) -2 + |S i | π min ∞ t=1 t + H i 2 -2 (26)
Note that all observations in calculating the EEM-UCB indices come from the SB2 block. Let, SB2 block begin with observing regenerative state ζ i and end with a return to the same ζ i . The total number of time of sub-optimal action i is selected at the end of block b(n) is estimated by considering the observations acquired in: i) the total number of plays of sub-optimal action i during SB2 block (upper-bounded by 1/π i min ), ii) the total number of selections in SB1 before entering the SB2 block (upper-bounded by Γ i max ) and iii) Finally, one more selection resulting from the SB3 block which is state ζ i . Thus, we have

E T i,h (n) ≤ 1 π i min + Ω i max + 1 E F i (b(n))
Moreover, since |S * | = S i = 2 and S max = 2, r max = 1 in our case, Theorem 1 follows.

Figure 1

 1 Figure 1 Reinforcement learning (RL) framework for BS switching operation.

Figure 2

 2 Figure 2 Regenerative sample path for EEM-UCB

Figure 3

 3 Figure 3 Transfer learning for Transfer EEM-UCB (TLEEM-UCB) policy.

4 4 4 4 Figure 4

 44444 Figure 4 Performance comparison under various homogeneous Poisson point process traffic intensity with transferred knowledge estimated from a source task with traffic intensity Λ source = 0.05 × 10 -4 .

Figure 5

 5 Figure 5 Improvement gain of TLEEM-UCB policy w.r.t. EEM-UCB policy for different target arrival rate. The bars corresponding to the left Y-axis reflect the gain in CEER while the right Y-axis represents the difference Λ target -Λ source .

Table 1

 1 List of the main symbols in the paper.

	Symbol	Meaning
	Y	Set of BS Y = {1, • • • , Y }
	Y on n	Set of active (ON) BS at the n-th iteration
	I k (n)	Cell coverage of BS k at time n
	x k	Denote the locations of the MS in coverage I k (n) of the k-th BS at time n
	Λ(x k , n)	Traffic arrival rate at location x k in BS k following a Poisson point process at the n-th iteration
	1/h(x k , n) L k (n)	Average call duration (or file size) at n-th iteration at x k Instantaneous traffic load served by the BS k ∈ Y on n
	Θ k (x k , n)	Service rate at location x k from BS k at the n-th iteration
	SINR k (x k , n)	Received SINR at active MS location x k from BS k at the n-th iteration
	ρ k (n)	System load of BS k at the n-th iteration
	ρ th	System load threshold
	P tx k , P k f and P k T	Transmit, fixed and total operational power of BS k
	EE(n)	Network energy efficiency (EE) in bits per joule
	Θ min

Table 2

 2 Simulation parameters

	Parameter description	Value
	Simulation area	5km × 5km
	Maximum transmission power	Macro BS: 20W, Micro BS: 1W
	Maximum operational power	Macro BS: 865W, Micro BS: 38W
	BS Height	Macro BS: 32m, Micro BS: 12.5m
	Intra-cell interference factor	0.01
	Channel bandwidth	1.25MHz
	Path loss model	COST 231
	Arrival rate Λ(x k ) in source task	0.05 × 10 -4
	Arrival rate Λ(x k ) in target task	0.05 × 10 -4 to 2 × 10 -4
	MSs call holding time 1/[h(x k )]	100Kbyte
	System load threshold ρ th	0.6
	Minimum bit rate requirement Θ min	122kbps
	Exploration parameters of RQoS-UCB	α = 0.25 and β = 0.32

10 6 Network EE with target = 0.05 10 -4 after 3000 iterations

					Ideal Policy
					EEM-UCB
					ACT
					TLEEM-UCB
					TACT
					Decentralized Greedy
					Always ON
	Figure 6 Network EE obtained with several learning algorithms with respect to the number of BS
	after 3000 iterations.
	Network Energy Efficiency [bits/Joule]	0 ×10 6 2	4	6	Time of day [hour] 8 10 12 14 16 18 20 22 24

  Average number of active BS suggested by several learning algorithms with respect to time of day.

	Average Number of Active BSs	5 6 7 8 9 10 4			Average Number of Active BSs Ideal Policy EEM-UCB ACT TLEEM-UCB TACT Decentralized Greedy
		0 3	2	4	6	Time of day [hour] 8 10 12 14 16 18 20 22 24
	Figure 9 Time of day [hour] 0 2 4 6 8 10 12 14 16 18 20 22 24 0 1 2 4 5 Average Number of BSs mode switches Ideal Policy EEM-UCB ACT TLEEM-UCB TACT Average Number of BSs mode switches 3 Decentralized Greedy
	Figure 10 Average number of BS mode switch required at each time slot during one hour with
	respect to time of day.

  and from [47,Lem. 2.1] by considering n = ω i , f (X i t ) =

		1{S i t =S}-G i,h S π i S G i,h S S πi	. The conditions of [46,
	Th. 3.3] are fulfilled if G i,h S ≥	1 πmax+π i S

  i,h (ω i , t) > µ * ) ≤

	S i π min	t + H i 2	-	∆µ i βM min ε min 28S 2 max r 2 max G 2 max π2 max

  min ∆µ R i M min . Similarly, one can bound the second part of (19) by following the same ideas than previously and applying the same steps than in [10, Appendix A] but introducing H * 2 , i.e. the number of times the best action has been chosen in historical period in SB2 block, we getP(B * ,h (ω * , t) ≤ µ * ) ≤ max = max i∈K M i,h ω i . By choosing α such that

		2 max r 2 max G 2 max max / ε |S * | π2 π min (t + H * 2 ) ε min (α-2 √ αβMmax) -28(SmaxGmaxrmax πmax) 2	(23)
	where M εmin(α-2 √ 28(SmaxGmaxrmax πmax) αβMmax)	2 ≥
	3 we obtain
	P(B |S * | π min	(t + H * 2 ) -3	(24)
	Substituting (24) into the second part of (19), we get
	∞ t=1	t-1 ω |S * | π min	∞ t=1	(t + H * 2 ) -2

* ,h (ω * , t) ≤ µ * ) ≤ * =1 P(B * ,h (ω * , t) ≤ µ * ) ≤

Acknowledgements

Not applicable.

Funding

This work has received a French government support granted to the CominLabs excellence laboratory and managed by the National Research Agency in the "Investing for the Future" program under reference No. ANR-10-LABX-07-01. The authors would also like to thank the Region Bretagne, France, for its support of this work.

Availability of data and material

The datasets used and/or analysed during the current study are available from the corresponding author on reasonable request.

Consent for publication

Not applicable.

Competing interests

The authors declare that they have no competing interests.

Author's contributions NM has provided the scientific and technical contents of the paper, deriving analytical results and numerical simulations. The three authors have contributed to the writing of the paper. All authors read and approved the final manuscript.

Author details


P Warintarawej
email: warintarawej@lirmm.fr

A Laurent
email: laurent@lirmm.fr

P Pompidor
email: pompidor@lirmm.fr

B Laurent
email: b.laurent@namaeconcept.com

Classification of Brand Names Based on n-grams

Keywords: Brand Names, Textual Classification, n-grams, Hierarchies

Supervised classification has been extensively addressed in the literature as it has many applications, especially for text categorization or web content mining where data are organized through a hierarchy. On the other hand, the automatic analysis of brand names can be viewed as a special case of text management, although such names are very different from classical data. They are indeed often neologisms, and cannot be easily managed by existing NLP tools. In our framework, we aim at automatically analyzing such names and at determining to which extent they are related to some concepts that are hierarchically organized. The system is based on the use of character n-grams. The targeted system is meant to help, for instance, to automatically determine whether a name sounds like being related to ecology.

I. INTRODUCTION

Brand names are very important as they occur everywhere in our lives and allow companies and organizations to associate distinctive signs on themselves, and their products, services. However, they cost a lot of money to companies if they have to be changed due to bad choices. The challenge is thus to provide automatic tools to analyze such names. These names are often neologisms and must be analyzed in many contexts (languages, social classes, etc.).

In this work, the goal is to analyze brand names so that the end user can be informed about the class which the names is the closest to. For instance, one name could be very close to the concept of ecology. The distance we use is based on a lexical analysis based on sequences of characters (n-grams). Further work will help classifying the names depending on their semantic or phonetic distances. In the currently implemented system, the user can analyze a name he has just created. The input is a name (existing or not in dictionaries) proposed by the user, and the system then shows him/her which concepts are related to this name. For this purpose, starting from this input, the system checks which concepts share the most important number of representative n-grams.

For this purpose, we consider the concepts from the Larousse Thesaurus [START_REF] Pechoin | Thesaurus -des mots aux idées, des idées aux mots[END_REF], which is in French and is equivalent to the Roget Thesaurus [START_REF] Roget | Roget's Thesaurus of English Words and Phrases[END_REF]. In many applications and domains, the concepts are organized into a hierarchy. As shown on Figure 1, this is the case for the thesaurus being In this paper, we study how to classify brand names into these hierarchically organized concepts. In the first part, we recall why brand names are difficult to manage and the existing approaches for hierarchical classification, before presenting our method and reporting experimental results.

II. RELATED WORK

A. Brand Names and Concepts

Brand names are very important in order to identify the products, services or companies they refer to. It is thus crucial to provide people working on trademarks (e.g. in marketing companies) with tools that allow to automatically analyze what brand names may evoke. However, as reported in [START_REF] Laurent | Embedding emotions within automatically generated brand names[END_REF], brand names have been hardly studied in linguistics, although they are an interesting kind of nouns (and expressions). Much research is indeed being done in economics and law regarding trade names used in advertising (which we would refer to as advertising names). However few works are published on the subject in French linguistics. These names can be either taken from a dictionary, or be neologisms. They have been often associated with proper names. However, they must be studied as a very particular piece of language.

B. Hierarchical Classification

Supervised classification (and text classification) has been studied for many years [START_REF] Mitchell | Machine Learning[END_REF], [START_REF] Joachims | Learning to Classify Text Using Support Vector Machines -Methods, Theory, and Algorithms[END_REF] and is a well-known technique to associate objects to predefined categories. In this work, we address a particular problem of supervised learning, as the predefined categories are organized into a hierarchy.

Many works are based on n-grams. An n-gram is a subsequence of n items from a given sequence. These items can for instance be phonemes, syllables, letters or words. Stopword lists are often used to clean data. A stopword list is a set of words that occur frequently in the language and which are not discriminant for the categories. In the other word, they are not meaningful. For instance, the word the in English does not convey any idea of a related concept.

[6] introduces a simple method using n-grams based on characters. The authors assume that documents from the same category should share similar n-grams. The training data set is taken from from newsgroup and is split into ngrams (1-5) that are counted. The top 300 highest frequency n-grams are selected to be the feature set. The authors use the simple rank-order statistic called out-of-place measure to compare new documents and categories. They then pick the category having the smallest distance. No model is learnt.

In [START_REF] Nather | N-gram based text categorization[END_REF], the author also uses n-grams. The approach mixes the ideas of out-of-place measure and the cosine similarity measure from vector space model. This paper proposes two ways of feature selection to represent the document, namely the inverse document frequency (idf) by selecting features greater than a threshold and the top 1,000 n-grams having the highest frequency. The result shows that top 1,000 ngrams with highest frequency is more successful than idf.

[8] proposes an approach for classifying Web documents into large topic ontology. The training data set comes from DMoz topic ontologies that contains web pages organized into a hierarchy consisting of 15 levels with 94,113 nonleaf nodes. Data is pre-processed for removing standard English stop-words (525) and stemming the words using the Porter stemmer [START_REF] Porter | An algorithm for suffix stripping[END_REF]. Bag of words are used for representating the information, by computing TF-IDF as feature vector. The k-nearest neighbor classifier is used for classifying a new document. In classifying phase, all the topics from the hierarchy are considered as a flat structure by building separate classifiers for every class in the hierarchy.

[10] is one of the closest work compared to our approach as the authors use thresholds to classify a document into a hierarchical structure. The authors use a top-down approach, meaning that the classification starts from top level and filters all categories in top level by threshold. The hierarchical structure from LookSmarts web directory is used. For the non-hierarchical case, the authors select 1,000 terms (words) from each of 150 categories by the largest mutual information between a test document and a category. For the hierarchical case, the authors also select 1,000 features from each of 13 top-level categories and 1,000 features from each of 150 second-level categories. During the training phase and classifying, SVM are used as a classifier. In the classifying phase, scores are combined from top and second level models using different combination rules.

In [START_REF] Mccallum | Improving text classification by shrinkage in a hierarchy of classes[END_REF], the objective is to classify documents into appropriate classes by taking advantage of a hierarchy of classes. The authors use the naïve Bayes classifier and propose a new statistical technique called shrinkage to improve the estimation of the parameters. The idea of shrinkage is to smooth the parameter estimation of a node by interpolating all its parent modes. The feature selection for classes is performed by ranking the highest mutual information at each internal node of the hierarchy. The authors claim that the shrinkage method can reduce text classification error by up to 29%, especially when the training data is sparse and the number of classes is large.

In [START_REF] Koller | Hierarchically classifying documents using very few words[END_REF], the authors propose an approach that utilizes the hierarchical structure by focusing a very small set of features. Using the Reuters-22173 dataset, they define top-level categories by merging sub-categories (e.g. Corn and Wheat group into Grain or Dollar and Interest Rate group into Money Effect). For classification, the naïve Bayes classifier is used, with a top-down approach. The test documents are classified into top-level first and then filtered to the firstlevel categories. The result when comparing between flat model and hierarchical models demonstrates the advantage of hierarchical model with a small number of features.

In [START_REF] Mhamdi | A hierarchical n-grams extraction approach for classification problem[END_REF], the authors address the problem of protein classification, using n-grams as the descriptors of their objects. These n-grams are mined using association rule-based methods and SVM are used for the classification task.

III. HCBN: HIERARCHICAL CLASSIFICATION OF BRAND NAMES

The general process we propose is described in Figure 2.

The methodology for building the model for hierarchical classification of brand names is split into the following steps:

(1) Preparing Data, (2) Collecting words into leaf node from French Larousse, (3) Applying Stopword and Stemming (4) Split word into n-grams (2-grams, 3-grams, 4-grams), (5) Selecting the most relevant features.

For classifying a new brand name, the system (1) first gets the new name from the user, (2) then splits the name into n-grams (2-grams, 3-grams, 4-grams), and (3) uses a naive Bayes classifier to classify at leaf node. (5) If the user judges the result as being not satisfactory, then the system tries to sum up the probabilities of siblings to roll up to a higher level in the class hierarchy. It then reports the class that gives the maximum value.

It should be noted that this last step is the main important novel part of our method. We detail the whole approach below.

A. Building Information about the Concepts

In existing text classification methods, it is important, for every concept, to gather related words. These words are then split into n-grams in order to compute the most discriminant n-grams. In our case, the challenge is to choose how to associate discriminant n-grams at several levels of granularity.

Two alternatives are possible: either to gather related names for every entry from the hierarchy (concepts, themes, sections, classes), or to gather related names only at the lowest level (concepts) and aggregate them for building discriminant n-grams at the upper levels (themes, sections, classes). In this work, we choose to gather words at the leaf level.

The data we gather is first cleaned. For this, we remove common words (stopwords). We use a French stopword list from the snowball project [START_REF] Project | [END_REF]. After that we use the Porter stemming algorithm to transform words into their grammatical roots. The stemming is the process for reducing inflected (or sometimes derived) words to their stem, base or root form.

For our task we consider n-grams of characters (letters, punctuation marks), assuming that words belonging to the same category should have some common sequences of letters. We separate a training set of words and a test set, and we choose 2-grams, 3-grams and 4-grams to be the feature set of the classification model.

The main characteristic of text classification is the high dimensionality of textual data. Usually in text classification, a document is represented by using a bag of words. In this work task, we use characters n-grams to be the feature set, and the bag of word is represented by the sequences of characters vector corresponding to a given word, thus leading to a very high number of attributes to be managed. Methods have been proposed to select the most relevant attributes. These methods, also known as feature selection, allow to reduce the dimensionality of the data, and to improve classification effectiveness and computation efficiency. As described in [START_REF] Yang | A comparative study on feature selection in text categorization[END_REF], several methods exist. Statistics (chisquare) and information gain are some of the more effective ones for optimizing classification result. In this work, we apply and compare the results obtained using several feature selection methods.

B. Classifying over Hierarchical Concepts

The naïve Bayes classifier is a simple classifier model that base on probabilistic theory call Bayesian theorem with independence assumptions so-called naïve Bayes assumption. All attributes are assumed to be independent, which is in fact not correct in real-world text classification. However, naïve Bayes performs well [START_REF] Domingos | On the optimality of the simple bayesian classifier under zero-one loss[END_REF].

To classify a document into a class, the best class is selected by maximum a posterior probability (MAP). We use naïve Bayes assumption, all of words in a document are independent and also position of words in the document. To apply naïve Bayes classifier to classify words into a class, we consider the classes from the hierarchical word structure derived from the French Larousse thesaurus. We consider a word as a vector space that consists of sequences of consecutive characters.

We assume that a word is composed of a sequence of consecutive characters called n-grams. For obeying naïve Bayes assumption, we also assume that these sequences are independent. The main idea behind our task is that a word will belong to a class, because it has some sequences of consecutive characters matching with other words from the same class. We thus separate all words into n-grams which become our attributes. If a word contains any such attribute (i.e. sequence), we mark 1 to be a weight of vector and 0 otherwise. Thus a word is represented by binary vector. We use multi-variate Bernoulli model.

Although the result of the comparison between mutivariate Bernoulli model and multinomial model is shown that the multinomial performs usually better at larger vocabulary sizes than the muti-variate Bernoulli model but the muti-variate Bernoulli model works well with small vocabulary size [START_REF] Mccallum | A comparison of event models for naive bayes text classification[END_REF].

For using n-grams sequences to be a feature, we only use a sequence absence or presence in word and we do not consider the frequency of consecutive characters sequences occurring in a word. After classifying at leaf node by naïve classifier, we try to improve classifying performance by using hierarchical structure of words.We purposed new methodology of hierarchical classification based on independence assumption of naïve bayes theory.

When classification is not satisfactory at the leaf level (i.e., the probability is lower than a predifined threshold), then we use the relationship between sibling nodes to go up in the hierarchy. For this purpose, we sum up the probabilities of all children to compute the score of the upper level node. At this upper level, the category having the highest score is chosen as the class to be output to the user. If this class is not satisfactory (i.e. the classification score is lower than the predefined threshold), then this process is repeated by rolling up to the upper level as many times as possible and necessary.

IV. EXPERIMENTAL RESULTS

Words have been collected using an Internet search related to each concept from the French Larousse thesaurus. The hierarchical structure of the data consists of 4 levels: 3 Classes, 27 Sections, 95 Themes and 873 Concepts from top to leaf level. 53,778 words have been collected at leaf node. In our experiment, we selected 6 concepts from different classes containing 821 words. From 821 words, we separate them into training set and testing set by random selection (see Figure 3). We run naïve classifier (multi-variate bernoulli model) and compare the results depending on the feature selection methods and the number and the size of features.

A. Results

Figures 4 and5 show classification accuracy and macro and micro-averaged precision and recall using three types of feature selection techniques with various n-grams and feature size.

Firstly, for overall result of classification accuracy, 2grams with 401 features achieved the best accuracy at 67.61%. Secondly, when comparing between several feature sizes (300, 500, 1000), 300 features of 3-grams with chisquare achieved the highest accuracy score at 57.49%. The second accuracy score is given by 3-grams with 500 features and information Gain at 57.09%.

For every type of feature selection technique, using 1,000 features performed poorly (except for TopRank frequency) even if [START_REF] Joachims | Learning to Classify Text Using Support Vector Machines -Methods, Theory, and Algorithms[END_REF], [START_REF] Mccallum | Improving text classification by shrinkage in a hierarchy of classes[END_REF] claim that a larger vocabulary generally performs better than small sizes. This may be due to the use of Bernoulli Model.

Thirdly, the results show that 2-grams perform better than 3-grams and 4-grams. However for 2-grams, the number of features is too small in our experiment so we cannot compare 2-grams between feature selection types and feature sizes. We can only compare between 3-grams and 4-gram. In this case, the 3-grams perform better than 4-grams.

Regarding the types of feature selection, chi-square achieves better than information gain and TopRank on average.

The results show that the highest micro-averaged performance is achieved with 2-grams with TopRank at 401 features. When comparing feature selection techniques on 3-grams and 4-grams, chi-square with 3-grams and 300 features and TopRank frequency with 3-grams and 500 features give the best classification evaluation measures by micro-averaged f-measure.

When comparing the results depending on the feature size, we show that chi-square with 3-grams and 300 features gives the best classification evaluation measure by micro-averaged f-measure. The second is given by TopRank frequency with 3-grams and 500 features. From these results, we can conclude that when the size of feature increases, then the performance slightly decreases.

V. CONCLUSION

This paper presents a system devoted to automatic brand name classification, with applications over hierarchicallyorganized classes. The solution proposed here consists in using representative character n-grams and defining a strategy to aggregate them over the hierarchy. Experiments have been carried out on the French classification of concepts from the Larousse. The experimental results show the interest of our approach.

The future research directions mostly include the extension of experiments, and the study of classification methods based on phonems [START_REF] Corredor-Ardoy | Classement automatique de phonèmes dans un cadre multilingue[END_REF]. Moreover, we will study how to improve our system in order to support multi-linguism [START_REF] Chowdary | MLPOSTGRES: Implementing Multilingual Functionalities Inside PostGreSQL Database Engine[END_REF].

Figure 1 :

 1 Figure 1: Larousse Thesaurus

Figure 3 :

 3 Figure 3: Corpus used in the Experiments (in French)

Figure 4 :Figure 5 :

 45 Figure 4: Experimental Results: Classification Accuracy on three Types of Feature Selection Techniques with Various n-grams and feature size