Caching Policy for Cache-enabled D2D Communications by Learning User Preference
Binqiang Chen Chenyang Yang
cs.IT math.IT





Caching Policy for Cache-enabled D2D Communications by Learning User Preference
    
Binqiang Chen and Chenyang Yang 














	Binqiang Chen and Chenyang Yang are with the School of Electronics and Information Engineering, Beihang University, Beijing, China, Emails: {chenbq,cyyang}@buaa.edu.cn. Part of this work has been presented in IEEE VTC Spring 2017 <cit.>.
	


    January 15, 2018
======================================================================================================================================================================================================================================================================================================





Prior works in designing caching policy do not distinguish content popularity with user preference.
In this paper, we illustrate the caching gain by exploiting individual user behavior in sending requests. After showing the connection between the two concepts, we provide a model for synthesizing user preference from content popularity. We then optimize the caching policy with the knowledge of user preference and active level to maximize the offloading probability  for cache-enabled device-to-device communications, and develop a low-complexity algorithm to find the solution. In order to learn user preference, we model the user request behavior resorting to probabilistic latent semantic analysis, and learn the model parameters by expectation maximization algorithm. By analyzing a Movielens dataset, we find that the user preferences are less similar, and the active level and topic preference of each user change slowly over time. Based on this observation, we introduce a prior knowledge based learning algorithm for user preference, which can shorten the learning time. Simulation results show remarkable performance gain of the caching policy with user preference over existing policy with content popularity, both with realistic dataset and synthetic data validated by the real dataset.




User preference, Content popularity, Caching policy, D2D, Machine learning, data analysis.




§ INTRODUCTION


Caching at the wireless edge has become a trend for content delivery <cit.>, which can improve network throughput and energy efficiency as well as user experience dramatically <cit.>.

Owing to the small storage size of each node at the wireless edge, say  base station (BS) or user device, caching in a proactive manner is critical to achieve the performance gain, where future user demand statistics is exploited <cit.>.
In wireless networks, the contents can be precached at each BS  <cit.> or even directly pushed to user device <cit.>. By caching at BS, backhaul traffic can be offloaded and backhaul cost can be reduced. By caching at user, wireless traffic can be further offloaded from peak time to off-peak time <cit.>. To boost the cache hit rate by precaching contents at each user that has very limited cache size, cache-enabled device-to-device (D2D) communications and coded-multicast strategy are proposed <cit.>.



To heap the proactive caching gain, various caching policies have been optimized with diverse objectives for different networks.
Most existing works assume known content popularity, defined as the probability distribution that every content in a catalog is requested by all users. For example, the policies for caching at BSs were optimized to minimize average download delay in <cit.> and to maximize coverage probability in <cit.>. The policies for caching at users were optimized to maximize the offloading gain of cache-enabled D2D networks in <cit.>. Coded caching policy was optimized to maximize the average fractional offloaded traffic
and average ergodic rate of small-cell networks in <cit.>. In these works, every user is assumed to request files according to content popularity. However, in practice a user actually sends requests according to its own preference, which may not be identical to content popularity.
Noticing such fact, caching policies at the user groups with different group popularity were optimized  in <cit.> to minimize the average delay of cache-enabled D2D communications.

To implement above-mentioned proactive caching policies, content popularity needs to be predicted <cit.>. Popularity prediction has been investigated for diverse applications such as advertisement, where content popularity is defined as the accumulated number of requests every content in a catalog received or the request arrival rate for every content. Numerous methods have been proposed  <cit.>.

 By using these prediction methods, the content popularity defined with probability in  <cit.> can be obtained as a ratio of the number of requests for each file to the number of all requests.

In cellular networks, the number of users in a cell is much less than that in a region covered by a content server, and a mobile user may send requests to more than one BS. Since popularity depends on the group of users who send requests, the local popularity in a cell may differ from the global popularity observed at a server. Designing proactive caching policy at wireless edge with predicted global popularity leads to low cache hit rate  <cit.>.

Optimizing caching policy for a BS should be based on the local popularity, which is formed by the users in a cell. In <cit.>, local popularity was predicted as the number of requests received for each file at a small BS divided by the observation time, i.e., the request arrival rate. Then, the popularity is adjusted with a perturbation term, which is learned by applying multi-arm bandit algorithm, and finally the predicted popularity with perturbation term is used for caching policy optimization. The prediction is based on the cumulative growth method  <cit.> and under the assumption that only the requests for already cached files can be observed, hence the learning algorithm is slow.



In <cit.>, the content popularity was predicted with a real dataset measured from cellular network. By converting the number of requests received at each BS into rating, the local popularity was predicted by a widely-used collaborative filtering technique, matrix factorization <cit.>, with which the files with largest ratings are cached at the BS.




 §.§ Motivation and Contributions


Since caching at wireless edge is motivated by the observation that the majority of requests are initiated for a minority of popular contents, a large body of priori works assume that all users send their requests according to content popularity.  The following facts, which are widely recognized in the communities studying recommendation problem and analyzing user behavior with real data, are largely overlooked in the community of studying caching at wireless edge: (i) as a demand statistic of multiple users, content popularity can not reflect the personal preference of each individual user <cit.>, (ii) only a small portion of users are active in creating traffic <cit.>. In fact, existing works do not differentiate content popularity from user preference. In practice, user preferences are heterogeneous although they may exhibit similarity to a certain extent. The caching policy designed under unrealistic assumptions inevitably yields performance loss.


In this paper, we investigate the gain of optimizing caching policy by learning user preference and active level over content popularity. To this end, we take cache-enabled D2D communications as an example system and offloading probability as an example objective. Because there are different definitions in the domains of computer science and wireless communications,
we first define user preference and active level as well as content popularity to be used in this paper, and provide a probabilistic model to synthesize user preference from content popularity by introducing similarity among user preferences. We then formulate an optimization problem with known user preference and active level to maximize offloading probability. Since the problem is NP-hard, a local optimal algorithm is proposed to reduce the complexity, which achieves at least 1/2 optimality. In order to learn user preference and active level, we model user request behavior resorting to probabilistic latent
semantic analysis (pLSA) originally proposed
for natural language processing <cit.>, whose model parameters can be learned using
approximate inference methods such as expectation maximization (EM) <cit.>. With the help of pLSA model to decompose the user behavior into different components and based on the observation from analyzing a real dataset that active level and topic preference change slowly over time, we provide a prior knowledge based algorithm, which  can quickly learn user preference.

The major contributions of this paper are summarized as follows:

 	
  * We illustrate the caching gain of exploiting user preference and active level by optimizing an caching policy for D2D communications, and predict the behavior of each individual user by estimating model parameters of pLSA. We introduce a prior knowledge based algorithm to learn user preference, which shows the potential of transfer learning.
 	
  * We characterize the connection between content popularity and user preference, provide a probabilistic model for synthesizing user preference
from content popularity, and validate the method by the MovieLens 1M dataset <cit.>. We analyze the relation between file catalog size and the number of users, the statistics of active level and topic preference of each user, and the user preference by the real dataset, which are critical for the caching gain.
 	
  * Simulation results with both synthesized data and MovieLens dataset show remarkable performance gain of the caching policy with user preference over that with local popularity, no matter the user demands are assumed known or learned from historical requests.








 §.§ Related Works

Considering that the tastes of different users are not identical, caching policies were optimized to minimize the average delay of cache-enabled D2D communications in <cit.> and to maximize the cache hit rate of mobile social networks in <cit.>, by assuming user preferences as Zipf distributions with different ranks. However, both works assume that all users have the same active level, do not validate the assumption for user preference, and do not show the gain over caching with popularity. Until now, there exists no method to synthesize user preference validated by real dataset, and the gain of caching with user preference is unknown.

There are few works that consider the relation between content popularity and user preference.
In <cit.>, local popularity is computed as a weighted average of preferences for the users associated with each BS, where the weight is the number of requests sent by each user and the user preference was assumed as uniform distribution. Then, the most popular files at each BS were cached. Differing from this early work, we characterize the connection between the collective and the individual user request behavior in a probabilistic framework, and illustrate the gain of exploiting user preference over popularity by optimizing a caching policy.


These priori works assume known user preference <cit.>.
To facilitate proactive caching, user preference needs to be predicted, which is a key task in recommendation problem. Collaborative filtering is the most commonly used technique to predict user preference<cit.>, which can be mainly classified into memory based method including user-based and item-based approaches, and model based method that is based on models with parameters estimated from historical records  <cit.>. Typical model based methods employ matrix factorization, latent
Dirichlet allocation <cit.>, and pLSA <cit.> as models <cit.>. For recommendation problem, user preference is defined as the rating that a user gives for a file, such as 0 ∼ 5 or simply “like” and “dislike”. Most collaborative filtering methods predict the ratings for unrated contents of each user, which however cannot be used in optimization for wireless caching. To optimize caching policy in wireless edge, where various metrics are in statistical sense <cit.>, user preference needs to be defined in probabilistic form, but there is no widely-accepted approach to map the rating into probability. In this paper, we resort to pLSA to model and predict user preference, which is originally developed for classification in automatic indexing <cit.> and then is applied to predict ratings in <cit.>.



The rest of the paper is organized as follows. Section <ref> provides the relation between content popularity and user preference, and a model to synthesize user preference. Section <ref> optimizes the caching policy with known user preference. Section <ref> presents the learning algorithms. Section <ref> analyzes the statistics of user demands from and validate the synthetic model by a MovieLens dataset. Section <ref> provides simulation results. Section <ref> concludes the paper.
	


§ CONTENT POPULARITY AND USER PREFERENCE


In this section, we first define content popularity, user preference and active level to be used in the following, show their connection, and then provide a probabilistic model with a free parameter to synthesize user preference.




 §.§ Definition and Relationship

Consider a content library ℱ = { f_1, f_2,..., f_F} consisting of F files that K users in an area  may request, where f_f denotes the fth file.


Content popularity is defined as the probability distribution that each file in the library is requested by all users, denoted as  p = [p_1,p_2,...,p_F ], where p_f≜ P( f_f) is the probability that f_f is requested, ∑_f=1^F p_f = 1, p_f∈ [0,1], and 1 ≤ f ≤ F. If the area only consists of a single cellular cell, then p is called local popularity.


User preference is defined as the conditional probability distribution that a user requests a file given that the user sends a request, denoted as q_k= [q_1|k,q_2|k,...,q_F|k ] for the kth user (denoted as u_k)), where q_f|k≜ P( f_f| u_k) is the conditional probability that the kth user requests the fth file when the user sends a file request, ∑_f=1^F q_f|k= 1, q_f|k∈ [0,1], 1 ≤ f ≤ F and 1 ≤ k ≤ K. We use matrix Q= (q_f|k)^K × F to denote the preferences of all users, where (q_f|k)^K × F represents a matrix with K rows and F columns and q_f|k as the element in the kth row and fth column.

Active level is defined as the probability that a request is sent by a user, denoted as w_k ≜ P( u_k) for the kth user, which reflects how active the user is, where ∑_k=1^K w_k = 1 and w_k ∈ [0,1]. Then, the vector w = [w_1,w_2,...,w_K] denotes the active level distribution of the K users.

Content popularity p reflects the
collective request behavior of a group of users, while q_k and w_k characterize the individual request behavior of the kth user.
To show their connection, we consider a K × F user-content matrix <cit.>, where each of its element n_k,f represents the number of requests sent by u_k for f_f. Denote N = ∑_k=1^K∑_f=1^F n_k,f as the overall number of requests sent by all the K users for all the F files, n_f = ∑_k=1^K n_k,f as the total number of requests sent by all users for f_f (i.e., the sum of all elements in the fth column), and n_k = ∑_f=1^F n_k,f as the total number of requests sent by u_k for all files (i.e., the sum of all elements in the kth row). Considering that n_f/N, n_k/N and n_k,f/n_k are respectively multinomial distributions with F, K, and F parameters, it is not hard to show that they are respectively the maximum likelihood estimate of p_f, w_k and q_f|k. From their definitions, we have

    ∑_k=1^Kn_k/N_w_kn_k,f/n_k_q_f|k  = ∑_k=1^Kn_k,f/N = n_f/N_p_f,

and hence each element of p can be expressed as the average of user preferences weighted by their active levels,

    p_f = ∑_k=1^K w_k q_f|k,    1 ≤ f ≤ F.




 In practice, users have different tastes, i.e., q_k ≠ q_m, and hence q_f|k≠ p_f, despite that users may have similar preferences, say for popular contents. Besides, not all users send requests with equal probability.
We can use cosine similarity to reflect the similarity of preferences between two users, which is frequently used in collaborative
filtering  <cit.> and defined as

    sim( q_k, q_m) = ∑_f=1^F q_f|m q_f|k/√(∑_f=1^F q_f|m^2 ∑_f=1^F q_f|k^2).

To show the similarity among K users, we can define average cosine similarity as

    𝔼_k,m [ sim( q_k, q_m) ]= 2/K(K-1)∑_k,m∑_f=1^F q_f|k q_f|m/√(∑_f=1^F q_f|k^2 ∑_f=1^F q_f|m^2).







 §.§ Modeling and Synthesizing User Preference


Content popularity can be modeled as a Zipf distribution according to the analyses for many real datasets <cit.>. The probability that the fth file is requested by all users is

    p_f = f^-β/∑_j=1^F j^-β,   1 ≤ f ≤ F,

where the files in the library are indexed in descending order of popularity, and the content popularity is more skewed with larger value of β.


User preference model obtained from real datasets is unavailable in the literature so far. Inspired by the method in <cit.> to synthesize local popularity of a cell from that of a core network, we represent users and files in a shared one-dimensional latent space, which bears the same spirit as latent factor model widely applied in collaborative
filtering <cit.>. To connect with  content popularity, we model user preference from the following generative process:

	
  * u_k is associated with a feature value X_k, which is randomly selected from [0,1].
	
  * f_f is associated with a feature value Y_f, which is again chosen uniformly from [0,1].
	
  * The joint probability that the fth file is requested by the kth user is given by

    P( u_k,  f_f) = w_kq_f|k = p_f g(X_k,Y_f)/∑_k'=1^K g(X_k',Y_f),

and then u_k's active level is w_k = ∑_ f_f ∈ℱP( u_k ,  f_f ) and its preference is q_f|k = P( u_k ,  f_f )/w_k, where g(X_k,Y_f) ∈ [0,1] is a kernel function used to control the correlation between the kth user and the fth file.
When g(X_k,Y_f) = 0, the fth file will never be requested by the kth user. When g(X_k,Y_f) = 1, the file is a preferred file of the user.


Intuitively, the value of X_k can be interpreted as the likelihood that the kth user prefers a topic, and the value of Y_f can be interpreted as the likelihood that the fth file belongs to a topic.
 Various kernel function can be applied, e.g., Gaussian, logarithmic and power kernels. To control the average similarity among the user preferences by introducing a parameter α in kernel function, we choose power kernel with expression g(X_k,Y_f) = (1-|X_k-Y_f|)^(1/α^3-1)∈ [0,1] (0<α≤ 1), which exhibits a linear relation between 𝔼_k,m [ sim( q_k, q_m) ] and α in a wide range.

Remark 1:
When α = 1, g(X_k,Y_f) = 1 for ∀ k,f. Then, we can see from (<ref>) that all user preferences are identical and equal to the content popularity, and then from  (<ref>) we can obtain 𝔼_k,m[sim ( q_k, q_m) ]=1. When α→ 0, g(X_k,Y_f) → 0 for X_k ≠ Y_f, and g(X_k,Y_f) = 1 only for X_k = Y_f. Because X_k and Y_f are uniformly chosen from [0,1], i.e., ℙ(X_k = Y_f) → 0, we have g(X_k,Y_f)g(X_k',Y_f) → 0, k ≠ k'. Then, according to (<ref>) and (<ref>), 𝔼_k,m[ sim ( q_k, q_m) ] → 0, i.e., no user has the same preference.
When α is small, g(X_k,Y_f) is low, which means that the number of interested files of u_k is small. Because each user randomly chooses feature
values, the interested file sets among different users
are less overlapped, and hence the average similarity among the users is low.

This probabilistic model is appropriate for generating synthetic data of user preference and active level, which differs from pLSA that can be used for predicting the individual behavior. This model will be validated later by a real dataset and the parameter will be fitted.




§ CACHING POLICY OPTIMIZATION: AN ILLUSTRATION


In this section, we illustrate how to optimize the caching policy with known request behavior of each individual user. For comparison, we also provide the corresponding caching policy optimization problem with known content popularity, whose solution reflects the existing policy in literature. To focus on the performance gain brought by distinguishing user preference from content popularity, we consider a simple objective: the offloading gain of D2D communications. To reduce the time complexity in finding the solution, we provide a local optimal algorithm.
	



 §.§ System Model



 Multiple BSs in the area are connected to core network via backhaul to serve the K uniformly distributed users, which constitutes a set of users 𝒰 = { u_1, u_2,..., u_K} that request the files in content library ℱ. Assume that each file is with same file size, but the results are applicable for general case with different sizes <cit.> by dividing each file into chunks of approximately equal size.[We can also formulate another optimization problem with different file sizes, which can be shown as a knapsack problem.] Each single-antenna user has a local cache to store M files, and can act as a helper to share files via D2D link.
To provide high rate  transmission with low energy cost at each user device, we consider a user-centric D2D communication protocol as in <cit.>. A helper can serve as a D2D transmitter and send its cached files to a user only if their distance is smaller than a collaboration distance  r_ c, which reflects the coverage of the helper. Each BS is aware of the cached files at and the locations of the users, and coordinates the D2D communications.


Proactive caching consists of content delivery phase and content placement phase.



In content delivery phase, each user requests files according to its own preference. If a user can find its requested file in local cache (i.e., fetching locally), it directly retrieves the file with zero delay. If not, the user sends the request to a BS. If the BS finds
that the file is cached in the local caches of helpers adjacent to the user, it informs the request to the closest helper, and then a D2D link is established between
the user and the closest helper (i.e., fetching via D2D link). Otherwise, the BS fetches the file via backhaul to serve the user. For simplicity, both fetching locally and via D2D link are called fetching via D2D links in the sequel.

Denote the file requests matrix after a period as N=(n_k,f)^K × F (i.e., the
user-content matrix), where n_k,f≥ 0 is the number of requests from u_k ∈𝒰 to f_f ∈ℱ. 
Assume that a central processor (CP) can record the requests history of users. To predict user preference, the CP needs to be deployed in the mobile core, such that most requests of users can be recorded. To determine where to deploy CP, one needs to consider both coverage area and computational cost.


In content placement phase, the CP learns the user preferences Q and active levels w from the requests history N, and then optimizes the caching policy for users and informs the cached files of the users to the BSs.  We consider deterministic caching policy,[We do not consider probabilistic caching policy, which is designed under the assumption that a group of nodes share the same caching distribution <cit.>, and hence is not appropriate for a system with heterogeneous user preferences. ] denoted as a vector c_k = [c_k,1,c_k,2,...,c_k,F] for the kth user, where c_k,f=1 if  f_f is cached at u_k, c_k,f=0 otherwise, and ∑_f=1^F c_k,f≤ M.  Denote the caching policy for all users as C= (c_k,f)^K × F. After being informed about the files to be cached at the users in its cell, a BS fetches the files from the core network and refreshes the caches of the users during the off-peak time, say every several hours, noticing that traffic load varies on the timescale of hours as measured by real cellular data <cit.>.
Due to user preference similarity, some users may have common
contents to precache  as shown later, which can be pre-downloaded by the BS via multicast to reduce wireless traffic.









 §.§ Caching Policy Optimization with Individual Request Behavior



We use offloading probability to reflect the offloading gain introduced by cache-enabled D2D communications, defined as the probability that a user can fetch the requested file via D2D links, which represent the average ratio of requests able to be offloaded.

When optimizing caching policy in the content placement phase, it is hard to know where a mobile user will be located in the content delivery phase. Therefore, it is hard to know when and how long the users will contact. Fortunately, data analysis shows that users always periodically reappear at the same location with high probability <cit.>. Consequently, it is reasonable to assume that the contact probability is known a priori <cit.>. Let A= (a_i,j)^K × K represent the contact probability among users, where a_i,j∈ [0,1] is the probability that the distance between the ith user and the jth user is less than r_c. When all users do not move, a_i,j=0 or 1.

In D2D communications, adjacent helpers may have overlapped coverage. Since different helpers need to serve different groups of users, which depend not only on r_c but also on the cached files at the adjacent helpers, the “local popularity” observed at a helper differs from that observed at another helper and relies on the caching policy. As a result, the caching policy can not be designed based on the “local popularity”.

Denote p^ d_k,f( A,C) as the probability that the kth user can fetch the fth file via D2D links given contact probability A and caching policy C. The complementary probability of p^ d_k,f( A,C) is the probability that the fth file is not cached at any users in proximity to the kth user, which can be derived as ∏_m=1^K (1- a_k,mc_m,f). Then, we can obtain
the offloading probability as

    p_ off ( Q,w,A,C) = ∑_k=1^K w_k  ∑_f=1^F q_f|k p^ d_k,f( A,C) =∑_k=1^K w_k ∑_f=1^F q_f|k(1-∏_m=1^K (1- a_k,mc_m,f) ).









With known user preference and active level, the caching policy can be optimized to maximize the offloading probability by solving the following problem,

	
    P1:      max_c_m,f          p_ off (Q,w,A,C) 
        s.t.        ∑_f=1^F c_m,f≤ M, c_m,f∈{0,1},   1 ≤ m ≤ K, 1 ≤ f≤ F.




Remark 2: If all users are with equal active level and equal preference, then (<ref>)  becomes

    p_ off ( Q,w,A,C)= 1/K∑_f=1^F p_f∑_k=1^K p^ d_k,f( A,C) ≜ p^ pop_ off ( p,A,C).




Remark 3: If the collaboration distance r_c →∞, then a_k,m=1, and (<ref>) becomes

    p_ off ( Q,w,A,C)     = ∑_f=1^F(1-∏_m=1^K (1- c_m,f) ) ∑_k=1^K w_k q_f|k = ∑_f=1^F(1-∏_m=1^K (1- c_m,f) ) p_f.

It is easy to show that p_ off ( Q,w,A,C)=p^ pop_ off ( p,A,C) in this extreme case where D2D links can be established between any two users in the area even with heterogeneous user preferences.

If the assumptions in the two remarks hold, then the “local popularity” observed at every helper will be identical, which is equal to the content popularity of the area with the K users.
In practice, the assumptions are not true, hence the caching gain from exploiting user preference differs from exploiting content popularity.

With known content popularity, the caching policy is optimized by maximizing p^ pop_ off ( p,A,C) in (<ref>) under constraint (<ref>), called problem P2,[The solution of P2 slightly differs from <cit.>, where  the future user location is exactly known in <cit.> and completely unknown in  <cit.> when optimizing caching policy, where the contact probability is known  in P2.] which is actually a special case of P1.




By setting the contact probability a_i,j as 1 or 0 (i.e., all users are static), we can obtain a special case of problem P2, which has the same structure as a  NP-hard problem
formulated in <cit.>. Since P2 is a special case of P1, problem P1 is NP-hard.
As a consequence, it is impossible to find its global optimal solution within polynomial time. By using similar way of proof  in <cit.>, it is not hard to prove that P1 is equivalent to maximizing a submodular function over matroid constraints. Thus, we can resort to greedy algorithm, which is commonly used to provide a solution achieving at least 1/2 of the optimal value for such type of problem <cit.>.[The best algorithm with polynomial time complexity for such problem can achieve (1-1/e) optimality guarantee, which is based on continuous greedy process and pipage rounding techniques <cit.>. However, when K=100 and F=3000 in the considered setting as detailed later, its complexity is O((FK)^8) = O(6.5×10^43), which is too complex for our problem.]


The greedy algorithm starts with zero elements for the caching matrix, i.e., C= (0)^K × F. In each step, the value of one element in C is changed from zero to one with the maximal incremental caching gain defined as

    v_ C(m,f) = p_ off (Q,w,A,C|_c_m,f=1) - p_ off (Q,w,A,C)
       (a)=∑_k=1^K w_k q_f|k( p^ d_k,f( A, C|_c_m,f=1)-p^ d_k,f( A,C)  ),

where (a) follows by substituting (<ref>), C is the caching matrix at previous step, and C|_c_m,f=1 is the matrix by letting c_m,f=1 in C. The algorithm is summarized in Algorithm <ref>.



The loops in step <ref> of Algorithm <ref> take  KM iterations, because there are totally KM files that are possible to be cached at all users. The step <ref> for finding the element in C that introduces the highest incremental caching gain takes at most KF iterations. For each time of computing v_ C(m,f) in (<ref>), the time complexity is O(K^2), and thus computing all v_ C(m,f) is O(K^3F). Hence the total time complexity for Algorithm <ref> is O(KM(KF+K^3F)) = O(K^2FM(K^2+1)), which is high especially when the numbers of users K and files F are large.







 §.§ A Low Complexity Algorithm with 1/2 Optimality Guarantee

Since the greedy algorithm is with high time complexity, finding a low-complexity algorithm is worthwhile for practice use. In what follows, we  propose an alternating optimization algorithm, which improves the offloading gain at every iteration and converges to a local optimal solution.

To be specific, we fix the caching policy at users c_m(m≠ k', 1 ≤ m ≤ K) and optimize c_k'. Then, from problem P1 we obtain the optimization problem with respect to c_k' as

    P1':      max_c_k',f         f_ off( c_k') = ∑_k=1^K w_k ∑_f=1^F q_f|k(1-∏_m=1,m≠ k'^K (1- a_k,mc_m,f) (1- a_k,k'c_k',f) )  
         s.t.        ∑_f=1^F c_k',f≤ M, c_k',f∈{0,1}, 1 ≤ f ≤ F.





	
	P1' can be solved with polynomial time complexity O(F(K^2+M)).


	See Appendix <ref>.
	


Based on the proof of Proposition <ref>, we propose an algorithm to iteratively solve problem P1' by changing k' from 1 to K until convergence. The algorithm starts with a given initial value of C.  In every iteration, by fixing c_m  (m ≠ k', 1 ≤ m ≤ K), it respectively computes the offloading gain introduced by caching the fth file at the k'th user

    b_k',f = ∑_k=1^K w_k  q_f|k a_k,k'∏_m=1,m≠ k'^K (1- a_k,mc_m,f), 1 ≤ f≤ F, 1 ≤ k' ≤ K.

Then, the algorithm finds the file indices with the maximal M values of b_k',f to constitute a set ℐ_k', and obtain c^*_k' as

    c^*_k',f ={
    1     ,     f ∈ℐ_k'
    
    0     ,     f ∉ℐ_k'.
    .

The detailed algorithm is presented in Algorithm <ref>. The loops in step <ref> take  K iterations. Step <ref> is with complexity O(F(K^2+M)) according to Proposition <ref>. Hence the total time complexity of Algorithm <ref> is O(t_A2KF(K^2+M)), where t_A2 is the number of iterations for step <ref>.




	
	Algorithm <ref> monotonically increases the objective function of problem P1 and finally converges to achieve at least 1/2 optimality.


	See Appendix <ref>.
	






It is noteworthy that Algorithm <ref> and Algorithm <ref> can also solve P2 by letting  q_f|k = p_f, ∀ k,f in Q. Solutions for P1 and P2 obtained with Algorithm <ref> are called S1-A1 and S2-A1, and solutions using Algorithm <ref> for P1 and P2 are called S1-A2 and S2-A2, respectively.





§ LEARNING USER PREFERENCE AND ACTIVE LEVEL


In this section, we first use pLSA to model content request behavior of an individual user. We then learn the model parameters by maximizing likelihood function, either without the pLSA model for comparison or with the model using the EM algorithm, which is efficient for ML parameter estimation with latent variables <cit.>.
Finally, we present a prior knowledge based algorithm to learn user preference.



 §.§ Modeling Individual User Behavior in Requesting Contents


To characterize the request behavior of a user, pLSA associates each request with a topic, which may be unobservable but can be intuitively interpreted as comedy, adventure, etc.













By introducing latent topic set 𝒵 = { z_1, z_2,..., z_Z} with cardinality  |𝒵|=Z, pLSA associates each topic z_j ∈𝒵 with each possible user request, i.e., u_k ∈𝒰 requests  f_f ∈ℱ.  Specifically, the request of each user can be modeled as the following steps with three model parameters:

	
  * A request is sent by u_k with probability P( u_k) (i.e., active level),
	
  * u_k chooses a topic z_j with probability P( z_j| u_k) (i.e., topic preference, ∑_j=1^Z P( z_j| u_k) = 1),
	
  * u_k requests  f_f in topic z_j with probability P( f_f| z_j), ∑_f=1^F P( f_f | z_j) = 1, where conditional independence assumption is used. In particular, conditioned on a request being sent by  u_k who chooses topic z_j, u_k chooses f_f with probability P( f_f| z_j, u_k ) = P( f_f| z_j), i.e., P( f_f | u_k ) = ∑_ z_j ∈𝒵P( f_f | z_j) P( z_j| u_k). In other words, no matter which user sends a request and selects topic  z_j, the user will request f_f with probability P( f_f| z_j).


Then, the joint probability that u_k requests f_f  can be expressed as

    P( u_k  ,  f_f )    = P( u_k  )P( f_f | u_k )  = P( u_k ) ∑_ z_j ∈𝒵P( f_f | z_j) P( z_j| u_k).




 §.§ Learning Individual User Behavior in Requesting Contents

   According to maximal likelihood (ML) principle, we can learn P( u_k ), P( f_f | z_j) and P( z_j | u_k) with requests history n_k , f by maximizing the following log-likelihood function <cit.>

    ℒ = ∑_ilog P( u_i_ u, f_i_ f)= ∑_ u_k ∈𝒰∑_ f_f ∈ℱ n_k , flog P( u_k ,  f_f )_(a) =  ∑_ u_k ∈𝒰∑_ f_f ∈ℱn_k , flog  P( u_k ) ∑_ z_j ∈𝒵P( f_f | z_j) P( z_j| u_k)_(b),

where the ith sample corresponding to the event that the i_ uth user requests the i_ fth file, and in (b) the pLSA model is applied.




  §.§.§ ML algorithm without pLSA model
 By maximizing the log likelihood function in (a) of (<ref>) without the pLSA model, it is not hard to obtain that

    P̂( u_k ,  f_f )= n_k,f/∑_k'=1^K∑_f=1^F n_k', f.


Then, the active level and user preference can be learned as ŵ_k = P̂( u_k) = ∑_f=1^FP̂( u_k ,  f_f ) and q̂_f|k= P̂( u_k ,  f_f )/P̂( u_k) = P̂( u_k ,  f_f )/∑_f=1^FP̂( u_k ,  f_f ), respectively. This algorithm is actually a simple frequency-count prediction, which can serve as a baseline for learning active level and user preference.




Remark 4: If we directly predict w_k and q_f|k using (<ref>), the number of parameters to estimate is KF. By using the pLSA as in (b) of (<ref>), the number of parameters is reduced from KF to K+KZ+ZF = Z(K+F)+K, where  K parameters are for learning active level, KZ parameters are for topic preference, and ZF parameters are for P( f_f| z_j). With less number of parameters to estimate, a learning algorithm can converge more quickly.



  §.§.§ ML algorithm with pLSA model
 To maximize the log-likelihood function in (b) of (<ref>), we first rewrite the function as

    ℒ = ∑_ u_k ∈𝒰   n_k log  P( u_k )_(a) +  ∑_ u_k ∈𝒰∑_ f_f ∈ℱ n_k , flog∑_ z_j ∈𝒵P( f_f | z_j) P( z_j| u_k)_(b),

where n_k =  ∑_ f_f ∈ℱ n_k , f. It is not hard to see that the terms in (a) and (b) can be independently maximized. The active level  of u_k can be learned by maximizing term (a) in (<ref>) as

    ŵ_k = P̂( u_k ) = n_k/∑_k'=1^K∑_f=1^F n_k' , f,

which is the same as that obtained from (<ref>). The other two model parameters P( f_f | z_j) and  P( z_j| u_k) can be learned by maximizing term (b) in (<ref>) using the EM algorithm as follows <cit.>.

Starting from randomly generated initial values for the model parameters P( z_j| u_k) and P( f_f | z_j),  1 ≤ j ≤ Z, 1 ≤ f ≤ F and 1 ≤ k ≤ K, the EM algorithm alternates two steps: expectation (E) step and maximization (M) step.
In the E-step, the posterior probabilities are computed for latent variable z_j with current estimation of the parameters as

    P̂( z_j| u_k, f_f)= P̂( z_j| u_k)P̂( f_f | z_j)/∑_ z_j'∈𝒵P̂( z_j'| u_k) P̂( f_f | z_j'),

which is the probability that f_f requested by  u_k belongs to topic z_j.
In the M-step, given P̂( z_j| u_k, f_f) computed by previous E-step, the parameters are updated  as


    P̂( f_f| z_j) =∑_ u_k ∈𝒰  n_k , fP̂( z_j| u_k, f_f)    /∑_ u_k ∈𝒰∑_ f_f'∈ℱ   n_k , f'P̂( z_j| u_k, f_f') ,    and  P̂( z_j| u_k) = ∑_ f_f ∈ℱ n_k , fP̂( z_j| u_k, f_f)   /n_k .


By alternating (<ref>) with (<ref>), the EM algorithm converges to a local maximum of log-likelihood function.
Then, the preference of the kth user for the fth file can be learned as 
    q̂_f|k= P̂( f_f| u_k) = ∑_ z_j ∈𝒵P̂( f_f | z_j) P̂( z_j| u_k).

































  §.§.§ Prior Knowledge Based Algorithm to Learn User Preference
 Video files in real world website always have topic information, e.g., movies are labeled with comedy, drama and so on.

Intuitively, the topic preference and active level of a user change slowly over time, and hence can be regarded as invariant. This will be validated later by real dataset. Thanks to the pLSA model, such intuition naturally yields a prior knowledge based algorithm to learn user preference by exploiting the active level and topic preference of a user learned previously during a much longer time than learning user preference, with the help of the topic information. This algorithm can be regarded as a parameter-transfer
approach <cit.>. While the active level P( u_k) and topic preference P( z_j| u_k) can never be learned perfectly, we assume that they are known in order to show the potential of such transfer learning.

Then, the user preference can be learned by only estimating P( f_f| z_j), which can be obtained similarly as in (<ref>),

    P̂( f_f| z_j) = {   ∑_ u_k ∈𝒰  n_k , fP̂( z_j| u_k, f_f)    /∑_ u_k ∈𝒰∑_ f_f'∈ℱ   n_k , f'P̂( z_j| u_k, f_f') ,        f_f ∈ℱ_j 
        0 ,        f_f ∉ℱ_j
    	 ,
    	 .

where ℱ_j is the set of files associated with topic z_j (1≤ j ≤ Z), which is available on the video website. For instance, the movie Forrest Gump is associated with topics comedy, romance and war on the MovieLens.  The detailed  algorithm  is presented in Algorithm <ref>. Step 2 takes  KFZ times computation of posterior probability by (<ref>), where each computation is with complexity O(Z-1) and thus totally at most O(KFZ(Z-1)). Step 3 computes (<ref>) with ZF times, each is with complexity O(K(F+1)). It is not hard to see that step 4 is with complexity O(KFZ). Hence the total time complexity for Algorithm <ref> is O(t_A3KFZ(Z+F+1)), where t_A3 is the number of iterations for step <ref>.






§ USER REQUEST BEHAVIOR ANALYSIS WITH MOVIELENS DATASET

The gain from caching highly depends on the user behavior in requesting contents,
both collectively and individually. In this section, we first use a real dataset to analyze the connection between file catalog size and number of users in a region, as well as the active level, topic preference of each user and user preference, and validate the intuition in Section <ref>. Then, we validate the user preference model provided in Section II.




 §.§ Statistical Results of User Demands


We use the MovieLens 1M Dataset <cit.> to reflect the request behavior, where MovieLens is a website that recommends movies for its users operated by GroupLens lab at the University of Minnesota.
This dataset contains 1000209 ratings for 3952 movies provided by 6026 users  from the year of 2000 to 2003. Each sample of the dataset consists of user identity (ID), movie ID, rating  and timestamp. Because users typically give ratings only after watching, we translate  the rating record into the request record, i.e., when a user gives rating for a movie, we set the movie as requested by once. Except for the ratings, MovieLens also provides topic information of movies. Every movie is associated with one, two or more topics from 18 topics, which include action, adventure, animation, children's, comedy, etc. genre and are denoted as z_1, ..., z_18. For instance, Forrest Gump is associated with topics comedy (z_5), romance (z_14) and war (z_17). From the topic information provided by MovieLens, we can see that if the fth movie is not associated with the jth topic, users who select jth topic will not request the fth file, i.e., we can set P( f_f| z_j) = 0  in (<ref>).


To analyze temporal evolution of user behavior, we sort all the 3952 movies according to their released date in ascendant order  and then divide them into two subsets ℱ_1 and ℱ_2, where the file request matrices on ℱ_1 and ℱ_2 are N_1 ∈ℝ^6040× 1976 and N_2 ∈ℝ^6040× 1976, respectively. N_1 can reflect user behavior on previously released file subset ℱ_1, and N_2 can reflect user behavior on subsequently released file subset ℱ_2.

Specifically, we analyze the following statistical results:

	
  * File catalog size: To reflect the randomness of the users in
sending requests, it is the average number of files requested by a given number of randomly chosen users, which is obtained from N = [N_1  N_2 ] and the average is taken over users.

	
  * Active level: P_1( u_k) and P_2( u_k) are computed using (<ref>) with N_1 and N_2, respectively.
	
	
  * Topic preference: Denote the topic preference of the kth user estimated on subsets ℱ_1 and ℱ_2 as p_1(𝒵| u_k) = [P_1(z_1| u_k),...,P_1(z_Z| u_k)] and p_2(𝒵| u_k) = [P_2(z_1| u_k),...,P_2(z_Z| u_k)], respectively. P_1(z_j| u_k), P_2(z_j| u_k) are computed using (<ref>) by EM algorithm with N_1 and N_2, respectively. To reflect the temporal dynamic of topic preference for the kth user, we use the metric of cosine similarity in (<ref>) to evaluate the similarity level as sim (p_1(𝒵| u_k),p_2(𝒵| u_k)).
	
  * User preference:  q_f|k=  ∑_ z_j ∈𝒵P( f_f | z_j) P( z_j| u_k) is obtained by EM algorithm on N_1. The result obtained from N_2 or N is similar, and hence is omitted for conciseness.





In Fig. <ref>(a), we show the relation between file catalog size and the number of users obtained
from dataset (with legend “MovieLens”) and the fitted curves. The curve with legend “Log"  fits the function f(x)=  alog( bx), and the curve with legend “Power" is with  f(x) =  ax^ b +  c. To evaluate the goodness of fit, we use the coefficient of determination (also called R-square) in linear regression, i.e.,
R^2 = 1 - ∑_i=1^S (y_i - f(x_i))^2/∑_i=1^S (y_i - y̅)^2, where S is the number of samples, (x_i,y_i) is the ith sample, and y̅ = ∑_i=1^S y_i/S <cit.>.  R^2 ≤ 1,  and the large value of R^2 indicates good fitting result.  The parameters a, b and c for each function and R^2 are listed in the legends. We can see that the catalog size first increases quickly and then slowly, where “Power" function fits better than “Log" function. When the number of users is small (e.g., in a small cell), the catalog size is small, which implies that the cache hit ratio could be high with limited cache size. However, with limited number of requests due to a few associated users, the popularity is hard to predict rapidly at the small BS. When the number of users is large (e.g., in a macro cell), the catalog size increases slowly, and both fitted curves are close to the measured catalog size. In <cit.>, the authors suggest to use logarithm function to compute the catalog size without validation. Here, the result shows that  “Log" is reasonable when the number of users in the considered area is large, say K ≥ 100, at least for MovieLens dataset.


In Fig. <ref>(b), we show the active levels of users, where the user indices are ranked in descending order according to P_1( u_k). We can see that the distribution of active levels is skewed, which indicates that majority requests are generated by a small number of users. Besides, the distribution of active levels from the two subsets of data  are similar, where the cosine similarity is 0.87. This validates that the active level of a user changes slightly over time.  We also show the corresponding fitted distributions, where “Weibull" is with function f(x) =  abx^ b-1e^- ax^ b, “Exponential" is with function f(x) =  ae^- bx, and “Zipf"  is with function f(x)=  ax^-β (shown only for the most active 1000 users). We can see that the curve with the real data is linear on a log-log scale for active users, but the tail (after the 1000th user) decreases quickly. The truncate tail may come from the rating behavior of users for watched movies on MovieLens website.  Some users rarely give ratings, and some users do not continuously give ratings. As a result, the observed active levels of these users are very low. From the values of R^2, we can find that “Weibull" is the best fitted distribution.
Nonetheless, the distribution of the most active 1000 users is very close to Zipf.





In Fig. <ref>(a), we show the topic preferences of the 1st, 10th and 100th users obtained from ℱ_1, i.e., p_1(𝒵| u_1), p_1(𝒵| u_10) and p_1(𝒵| u_100). The results obtained from ℱ_2 are similar and are not shown. The labels of x-axis are ranked in descending order according to p_1(𝒵| u_1). The topic preferences of the 10th and 100th users with re-ranked x-axis according to p_1(𝒵| u_10) and p_1(𝒵| u_100) are also provided in the inner-figures.  We can see that topic preference of each user is skewed, which indicates that each user has  strong preferences towards specific topics. In fact, the topic preferences of all users in the dataset are skewed, which is not shown for consciousness. We can also see that topic preferences of different users differ. For example, the most favorite topic is comedy for the 1st and 100th user and drama for the 10th user.


In Fig. <ref>(b), we show the topic preference of the 1st user and the fitted distributions in a log-log coordinate. We can see that the best fitted distribution is a Zipf distribution with parameter β = 1.05. We have also fitted distributions of topic preferences for other users, but the curves are not provided. We observe that the best fitted distributions differ for users, where Zipf distribution is the best of 1425 users, Weibull distribution is the best for 1899 users, and Exponential distribution is the best for the remaining 2702 users (but the difference in R^2 from Weibull distribution for these users is negligible). For the users whose best fitted distributions are Zipf distributions, the parameters of β differ, which approximately follow a uniform distribution in [0.5, 3]. Yet for the most favorite several topics, Zipf distribution is always the best.




































In Fig. <ref>(a), we show the empirical cumulative distribution function (CDF) and probability density function (PDF) of the cosine similarity between topic preferences over time of all users. We can see that 60% of all users have cosine similarity larger than 0.8, and almost 90% users among the top 1/3 active users have cosine similarity larger than 0.8 (i.e., their topic preferences change slowly in the three years). Considering that the statistical results for active users with more requests are with high confidence level, this result indicates that topic preferences can be approximated as invariant over time.[In recommendation problem, it has been shown that user preference varies over time due to the dynamic of file catalog and the user's exploration for new items <cit.>. However, the topic preference variation has never been analyzed in the literature.] This validates the intuition in Section <ref>.













In Fig. <ref>(b), we show user preference of the 1st user and the fitted distributions. The user preference for the top 100 favorite files is close to Zipf distribution (a straight line in the log-log  coordinate), and the preference for less favorite files has a truncated tail. This is because a user almost does not request the files belonging to its unfavorable topics. We have also fitted the preferences of other users (but are not shown). We find that Weibull is the best fitted distribution for all users, but the parameters and the skewness of curves  differ. The user preferences for the top favorable 100 files of each user can be fitted with Zipf distribution, but the parameters of β differ in a range of [0.2, 0.8]. In summary, the preferences of different users differ in the favorite file set, skewness, and ranking. This is not consistent with the model that all user preferences are Zipf distributions with same parameter but with different ranks as assumed in <cit.>. Besides, we observe that the average cosine similarity of preferences among different users on dataset N_1 is as low as 𝔼_k,m [ sim( q_k, q_m) ] ≈ 0.4.[We also analyze a real video dataset of Youku in a university campus. The result shows that 𝔼_k,m [ sim( q_k, q_m) ] ≈ 0.28.]  This is mainly because the interested file sets of users are less overlapped, recalling that the topic preferences of users differ.



 §.§ Validating Synthetic User Preference Model






Now, we validate the user preference model by comparing the results obtained from data synthesized by the generative process in Section II and those from the MovieLens dataset.



In Fig. <ref>(a), we first show the impact of parameter α in the kernel function. The inner-figure indicates that the synthetic
user preference model can capture different levels of similarity among user preferences by adjusting α, while the Zip parameter β has negligible impact on the average cosine similarity. This seems counter-intuitive, since a more skewed popularity distribution seems to imply highly correlated user preferences. However, such an intuition comes from the implicit assumption that the users send their requests with equal probability (i.e., with identical active level), which is not true in reality. From the figure we can observe that even when β=1, α can be as small as 0.1. This is because few users are very active in sending file requests and have skewed user preference, who have large impact on content popularity according to (<ref>). We can see that the distributions of user active level are skewed, which agree well with the results in Fig. <ref>(b) obtained from the MovieLens dataset.


In Fig. <ref>(b), we show the topic preference of the 1st, 10th and 100th users. The labels of x-axis are ranked according to p(𝒵| u_1), as in Fig. <ref>(a). We can see that the topic preferences of the users are skewed, and the topic preferences of the three users are with different  distributions, which are consistent with the results in Fig. <ref>(a) obtained from the MovieLens dataset.






§ SIMULATION RESULTS


In this section, we demonstrate the caching gain by exploiting user preference over content popularity, either perfect or predicted. Simulation results are obtained from data generated by the synthetic model in section <ref>, which can provide ground truth of the request behavior for evaluation, and from the MovieLens dataset, which can validate the gain from real data.

We consider a square area with side length 500 m, where K=100 users are  uniformly located. The collaboration distance r_c = 30 m. The file catalog size F=3000 (obtained from Fig. <ref>(a) for 100 users), and each user is willing to cache M=5 files (i.e., 1.67 ‰ of all files).
α=0.36 in the kernel function of the synthetic model, which corresponds to the average cosine similarity 0.4 of the MovieLens dataset (obtained from Fig. 5(a)). The parameter of Zipf distribution is β =0.6, which is slightly smaller for a small area than that is observed at the Web proxy  as reported in <cit.>.  We divide time into two-hour periods, each consisting of a peak time and an off-peak time.[Using other values as the period does not affect the learning performance of user preferences. Yet the period can not be too short, since a frequent content placement brings extra traffic load. Numerical results under the considered setup show large opportunity of using multicast for precaching. In particular, (i) only 76 files need to be pre-downloaded to users via unicast where the other 424 files can be placed to users via multicast, (ii) 20% of the 500 files should be placed at more than 10 users, and 50% of files should be placed at more than 5 users. Besides, not all the 500 files need to be changed in each update.] The cached files at each user are updated in off-peak time.
This setup is used in the sequel unless otherwise specified.








 §.§ Impact of Key Parameters


In the sequel, we analyze the impact of user mobility, user preference similarity parameter α, collaboration distance r_c, cache size M, and Zipf parameter β on the offloading probability.

We consider a widely used mobility  model, random walk model, where a user moves from its current location to a new location by randomly choosing a direction and speed to travel <cit.>. To compute the contact probability matrix, we consider the two-hour period where each user moves 100 seconds before changing direction and speed. The users are initially uniformly distributed, and the speed and direction of each user are uniformly chosen from [0, v_max] m/s and [0, 2π], respectively.  By computing the duration that the kth and the mth user can establish D2D links, t^d_k,m, in the period of T_p = 2 hours, we can obtain the contact probability a_k,m = t^d_k,m/T_p. By increasing v_max, users may move with higher speed, and when v_max = 0, all users keep fixed. In this subsection, both user preference and content popularity are perfect.




In Fig. <ref>, we show the impact of user mobility. A1 and A2 in the legend respectively represent the greedy algorithm (i.e., Algorithm 1) and local optimal algorithm (i.e., Algorithm 2), which achieve almost the same offloading probability. The offloading probabilities decrease slightly with the growth of v_max, as explained as follows. Owing to the mobility model, the average number of users that a user can establish D2D links with at any time does not change with v_max. Then, the total effective cache size seen by the user does not change with v_max. On the other hand, every user can contact with more users in the period with higher v_max. Then, the caching policy needs to be optimized by considering the preferences of more users, which reduces the cache hit ratio due to heterogeneous user preferences. Since the impact of mobility is not significant, we only consider v_max = 0 in the sequel.


To obtain the results of A2 in Fig. <ref>, three iterations of step 1 (i.e., t_A2 = 3) is necessary for convergence.
According to analysis in Section <ref>, the time complexity for A1 and A2 are respectively O(K^2FM(K^2+1)) and O(3KF(K^2+M)), and A2 will be KM(K^2+1)/3(K^2+M)≈ 167 times faster than A1 when K=100 and M=5.

Since the proposed local optimal algorithm can achieve the same performance and is faster than the greedy algorithm, we only use A2 to obtain the caching policy in the following.





In Fig. <ref>(a), we show the impact of α and r_ c. We can see that the offloading gain of S1 over S2 is high when α is small. This suggests that optimizing caching policy according to user preferences is critical when the user  preferences are less correlated. As expected, when α→ 1, the performance of the two policies coincide. The offloading gain is high for large collaboration distance, but the gain by using  S1  reduces as indicated in Remark 3. This is because with the growth of r_ c, the number of users whose preferences a helper should consider for optimizing caching policy increases (when r_ c→∞, the number of users equals to K).

In Fig. <ref>(b), we show the impact of β and M. As expected, with the growth of the value of M or β, the offloading probabilities increase for both S1 and S2. This is because with a given value of α, the preference of every user becomes more skewed when β increases.



 §.§ Offloading Gain with Learned User Preference

In what follows, we demonstrate the performance gain of the proposed caching policy by exploiting user preferences over that with content popularity, and the gain provided by learning with the pLSA model and the priori knowledge. To this end, we compare the following schemes:


  * “S1-perfect”: The proposed caching policy with perfect user preference and active level, which is the solution of problem P1.

  * “S2-perfect”: The existing caching policy optimized with perfect content
popularity, which is the solution of problem P2 (slightly different from the policies in <cit.>).


  * “S1-EM”: The proposed caching policy with ŵ and Q̂ learned by the EM algorithm.

  * “S2-EM”: The existing caching policy with learned local popularity of the K users, which is computed with (<ref>) from the learned user preference by EM algorithm.

  * “S1-prior”: The proposed caching policy with Q̂ learned by Algorithm <ref>.

  * “S2-prior”: The  existing caching policy with learned local popularity of the K users, which is computed from the learned user preference by Algorithm <ref> as p̂_f  = ∑_ u_k ∈𝒰P̂( u_k ,  f_f ).

  * “S1-baseline”: The proposed caching policy with learned user preference, which is obtained by the ML algorithm without pLSA model.

  * “S2-baseline”: The  existing caching policy with learned local popularity of the K users, which is obtained by using the traditional frequency-count popularity prediction method in  <cit.>. Such a popularity learning method is the same as the method used in <cit.>.





In Fig. <ref>, we show the offloading probability achieved by these schemes during the learning procedure with the synthetic data. To compare with the results to be obtained with realistic dataset in the sequel, we set the x-axis as the accumulated number of requests. When the request arrival rate of the users in the area is 0.04 requests per second, which reflects the high traffic load scenario for files with 30 MBytes size (typical size of the YouTube videos) in <cit.>, the accumulated 40, 80 and 120 requests correspond to 22.8, 55.6, and 83.3 hours, respectively. It is shown that using pLSA and even the priori information do not help accelerate convergence of local popularity, because the simple frequency-count method already converges rapidly. Compared to the proposed caching policy with learned user preference (S1-EM, S1-prior and S1-baseline), S2 with learned local popularity (S2-EM, S2-prior and S2-baseline) converge to S2 with perfect  content popularity (S2-perfect) more quickly. This is because the number of requests for each file from each user is much less than that from all the users in the area. Nonetheless, the proposed caching policy with learned user preference can quickly achieve higher offloading probability than S2 with learned (and even perfect) content popularity. The proposed caching policy with pLSA (both S1-EM and S1-prior) is superior to the baseline (S1-baseline), especially when the cache size at each user M is large.  This is because some unpopular files will be cached with large M. For the unpopular files, the number of accumulated requests is less and user preference learning is more difficult. Besides, we can see that by exploiting prior knowledge of user active level and topic preference, S1-prior converges much faster than  S1-EM.





In Fig. <ref>, we show the offloading gain with the MovieLens dataset. Because S2-EM and S2-prior perform closely to S2-baseline, we only simulate S2-baseline here. We randomly choose 100 users from the dataset (which includes both active and inactive users) and the most popular 3000 files. The timestamps of user requests are shuffled as in <cit.> to ensure the training set has the same user demand statistics as the test set.  Compared with Fig. <ref>(a), we can see that the offloading probabilities for all methods on the realistic dataset are less than those with synthetic data. This is because a user requests each movie at most once in the realistic dataset translated from rating data, while a user may request a file more than one time in the synthetic data. In practice, a user may request a file more than once, e.g., the file is a favorite song of the user or an educational video.  Nonetheless, we can see that the proposed caching policy with predicted user preference still achieves much higher offloading gain than existing scheme. Because the prior knowledge of topic preferences is learned on realistic dataset in Fig. <ref> rather than perfectly known as in Fig. <ref>(a), the performance gain of S1-prior over S1-EM is lower here, which however is still remarkable. Besides, we can see that S1-baseline always performs the worst, because user preference for unvisited files is hard to predict by using the ML algorithm without pLSA model when each user only requests a file at most once. However, we can still predict user preference for the unvisited files with both S2-EM and S2-prior, owing to the pLSA model.



§ CONCLUSIONS


In this paper, we demonstrated the caching gain by exploiting learned individual user behavior in sending request. We first showed the connection between user preference and content popularity, and provided a probabilistic model to synthesize user preference from content popularity. We then formulated an optimization problem with given user preference and active level to maximize the offloading probability  for cache-enabled D2D communications. Since the problem is NP-hard, a low-complexity algorithm achieving at least 1/2 optimality was proposed to solve the problem. Next, we modeled the user request behavior by pLSA, based on which the EM algorithm was used to learn the user preference and active level. We used a Movielens dataset to analyze several kind of user behavior in requesting contents, and validated the synthetical model. We find that: (i) when the number of users K in an area is large, the file catalog size is a logarithm function of K, (ii) the active level of the most active users can be modeled as Zipf distribution, (iii) the preferences for
the most favorable files of each user can be modeled as Zipf distribution, but with different skewness parameters and different file sets, (iv) the user preferences are less similar, and (v) the active level and topic preference of each user change slowly over time, say in the time scale of year. Based on the 5th observation from the real dataset, we introduced a prior knowledge based algorithm to exploit the active level and topic preference previously learned, which shows the potential of transfer learning. Simulation results showed that using pLSA can quickly learn the individual user behavior, and the prior knowledge based algorithm converges even faster. Compared to existing caching policy using content popularity, the performance can be remarkably improved by the caching policy exploiting user preferences, both on the synthetic data with parameters fitted from real dataset and on the MovieLens dataset.

equationsection





























































































§ PROOF OF PROPOSITION <REF>




The objective function of problem P1' can be further derived as

    f_ off( c_k' )     =   ∑_k=1^K w_k ∑_f=1^F q_f|k(1-∏_m=1,m≠ k'^K (1- a_k,mc_m,f) (1- a_k,k'c_k',f) ) 
    
    
        =   1- ∑_f=1^F∑_k=1^K w_k  q_f|k∏_m=1,m≠ k'^K (1- a_k,mc_m,f)_(a)
         + ∑_f=1^F c_k',f(∑_k=1^K w_k  q_f|k a_k,k'∏_m=1,m≠ k'^K (1- a_k,mc_m,f))_(b),

where both terms in (a) and (b) are not related to c_k',f. Then, solving the problem in (<ref>) is equivalent to solving the following problem

    P1'      max_c_k',f        ∑_f=1^F c_k',f(∑_k=1^K w_k q_f|k a_k,k'∏_m=1,m≠ k'^K (1- a_k,mc_m,f))(a)=∑_f=1^F c_k',f b_k',f
         s.t.        ∑_f=1^F c_k',f≤ M, c_k',f∈{0,1}, 1 ≤ f ≤ F,

where (a) is obtained by letting b_k',f = ∑_k=1^K w_k  q_f|k a_k,k'∏_m=1,m≠ k'^K (1- a_k,mc_m,f). By finding file indices of the maximal M values of b_k',f (1≤ f ≤ F) to constitute the set ℐ_k', it is not hard to show that the optimal caching policy c^*_k',f can be obtained as (<ref>).










To obtain c^*_k',f, we need to compute b_k',f with time complexity O(K^2F) and then choose the  maximal M values of b_k',f with complexity O(FM). Finally, we can prove that the optimal solution of problem (<ref>) can be obtained with complexity O(K^2F+FM) = O(F(K^2+M)).



§ PROOF OF PROPOSITION <REF>



Denote the caching policy at the k'th user after the (t-1)th iteration as c^(t-1)_k'. In the tth iteration, the offloading probability before step <ref> of Algorithm <ref> is f_ off( c^(t-1)_k' ) as in (<ref>). After that step, c^(t)_k' is computed for the k'th user and the corresponding offloading probability is f_ off( c^(t)_k' ). By subtracting f_ off( c^(t-1)_k' ) from f_ off( c^(t)_k' ), we can obtain


    f_ off( c^(t)_k' ) - f_ off( c^(t-1)_k' )     =   ∑_k=1^K w_k ∑_f=1^F q_f|k(1-∏_m=1,m≠ k'^K (1- a_k,mc_m,f) (1- a_k,k'c^(t)_k',f) ) 
       - ∑_k=1^K w_k ∑_f=1^F q_f|k(1-∏_m=1,m≠ k'^K (1- a_k,mc_m,f) (1- a_k,k'c^(t-1)_k',f) )  
       (a)=∑_f=1^F c^(t)_k',f b_k',f - ∑_f=1^F c^(t-1)_k',f b_k',f
       (b)=  (max_c_k',f∑_f=1^F c_k',f b_k',f )- ∑_f=1^F c^(t-1)_k',f b_k',f≥ 0,

where (a) is obtained by substituting (<ref>) and (<ref>), and (b) is obtained from (<ref>). Thus, the offloading gain is monotonically improved until convergence.

To prove the optimality guarantee of the local optimal algorithm, we first convert the offloading probability into a function of a set instead of a matrix (i.e., C). Denoting f_f^k as an action that caching the fth file at the kth user. Recall that c_k,f=1 represents the kth user caching the fth file. Then, the caching policy for the kth user, c_k = [c_k,1,c_k,2,...,c_k,F], can be re-expressed as a set 𝒞_k = { f^k_f|c_k,f=1}, i.e., caching which files at the kth user. Let 𝒞 = {𝒞_1, 𝒞_2, ..., 𝒞_K }, then problem P1 is equivalent to the following problem,

    max_𝒞         f_(𝒞) =  ∑_k=1^K w_k ∑_f=1^F q_f|k(1-∏_ f_f^m∈𝒞 (1- a_k,m) ) 
         s.t.           |𝒞_k| ≤ M, 1 ≤ k ≤ K.


By defining a set 𝒮 = { f_1^1,  f_2^1, ... ,  f_F^1, ...,  f_1^K, f_2^K,..., f_F^K}, we can see that 𝒞⊆𝒮 and f_(𝒞): 2^𝒮→ R is a discrete set function on subsets of 𝒮.
Let 𝒜,ℬ⊆𝒮, 𝒜⊆ℬ, and f_k'^f'∈𝒮∖ℬ.

Denote the global optimal caching policy as 𝒞^* = {𝒞^*_1,𝒞^*_2,...,𝒞^*_K}, a local optimal caching policy obtained by Algorithm <ref> as 𝒞^L = {𝒞^L_1,𝒞^L_2,...,𝒞^L_K}, and caching policy at users except the kth user as 𝒞̅^̅L̅_̅k̅ = {𝒞^L_1,𝒞^L_2,.,𝒞^L_k-1,𝒞^L_k+1,..,𝒞^L_K}.
Then, we can obtain

    f(𝒞^*) - f(𝒞^L) (a)≤ f(𝒞^*∪𝒞^L ) - f(𝒞^L) ≜  f_𝒞^L(𝒞^*) (b)≤∑_k=1^Kf_𝒞^L(𝒞^*_k) 
       (c)≤∑_k=1^Kf_𝒞̅^̅L̅_̅k̅(𝒞^*_k) (d)≤∑_k=1^Kf_𝒞̅^̅L̅_̅k̅(𝒞^L_k)  (e)≤  f(𝒞^L_1)  +∑_k=2^Kf_∪_i=1^k-1𝒞^L_i(𝒞^L_k) = f(𝒞^L),

where (a) is obtained because offloading probability is a monotone increasing function, i.e., f(𝒞^*) ≤ f(𝒞^*∪𝒞^L), (b) is obtained by the property that for set 𝒜,ℬ,𝒞⊆𝒮, we have f_𝒜(ℬ∪𝒞) ≤ f_𝒜(ℬ) + f_𝒜(𝒞), (c) and (e) are obtained by the property that for set 𝒞⊆𝒜⊆𝒮 and ℬ⊆𝒮, f_𝒜(ℬ ) ≤ f_𝒞(ℬ), and (d) is obtained because for any caching policy at the kth user denoted as 𝒞^a_k, we have f_𝒞̅^̅L̅_̅k̅(𝒞^L_k) - f_𝒞̅^̅L̅_̅k̅(𝒞^a_k) = f(𝒞^L_k ∪𝒞̅^̅L̅_̅k̅) - f(𝒞^a_k ∪𝒞̅^̅L̅_̅k̅) ≥ 0 considering 𝒞^L is the local optimum of Algorithm <ref>. Thus, we have f(𝒞^L) ≥1/2 f(𝒞^*), and Proposition <ref> follows.
IEEEtran



