FIELD OF THE INVENTION

This invention relates to fair allocation of resources when optimizing a system comprising multiple functions.

BACKGROUND

The maximization of submodular functions appears in a wide and diverse array of applications, including feature selection, network monitoring, news article recommendation, sensor placement and information gathering, viral marketing and influence maximization, and document summarization. In these applications, the key feature that has played a role in the development of algorithms with deep theoretical consequences is the presence of a submodular objective function. A set function is said to be submodular if it satisfies the diminishing return property. While it is widely known that greedy methods work well for a single objective, the problem becomes much harder when there are multiple objectives to handle. For example, the case where the system to be optimized is described by a collection of submodular functions, opposed to a single function, and the aim is to provide a fair allocation among the objectives.

Existing early approaches to investigating the optimization of a system described by a collection of submodular functions use a plain summation of the objectives in order to optimize the average- value of the objectives and use a greedy algorithm to maximize the average-case. Although this approach works technically, it does not necessarily provide the expected output in terms of fairness across the different objectives.

More recent approaches propose to maximize the worst-case value of the objectives instead of the average-value of the objectives. This approach proposes using a proxy function of the minimum function and performing a series of grid search in order to find the optimal parameter which maximizes the worst-case objective. However, only focusing on the worst-case may be too pessimistic in some applications, and more specifically when there are some unknown objectives, often referred to as outliers, that naturally present low values and are probably not relevant for the purposes of optimization. In particular, for such system with outliers, this existing approach does not perform a fair allocation of the resources. Even worse, in the case where outliers are present in the input system, the optimization might not even be possible since the outliers can effectively block the allocation process.

It is desirable to develop a method and apparatus which can fairly determine an allocation set of resources with an optimum configuration for a system described by a collection of submodular functions.

SUMMARY OF THE INVENTION

According to one aspect there is provided a resource allocator for determining an allocation set of resources from an input set of resources, each resource of the input set being represented by one or more objective functions. The resource allocator comprises one or more processors configured to form the allocation set by repeatedly performing the following steps. Forming, for each resource of the input set that is not already in the allocation set, a selection value as a biased version of an evaluation of the or each objective function representing that resource. Then, selecting the resource of the input set corresponding to the highest one of the selection values. Lastly, adding the selected resource to the allocation set.

Each selection value may be formed in dependence on a predetermined constant raised to the power of the evaluation of the respective objective function. The constant may be Euler’s number. This can conveniently bias the effect of the selection values.

Each selection value may be formed by means of a predetermined selection value function, the selection value function being such that it preserves submodularity among the objective functions. This can help in allowing the process to be solved relatively quickly.

The selection value function may be dependent on a tuning parameter, whereby the sensitivity of the selection value function to more or fewer objective functions can be selected. This can assist in tuning the process.

Each selection value may be formed in dependence on a predetermined constant raised to the power of the evaluation of the respective objective function scaled by the tuning parameter. This can conveniently bias the effect of the selection values. The one or more processors may be configured to receive from a user an input value; and select the tuning parameter in dependence on the input value. Thus a user may be able to tune this aspect of the system.

The one or more processors may be configured to select a size for the allocation set, add selected resources to the allocation set until the allocation set has the selected size, and output the allocation set. This can allow the system to form a set of resources of a desired size. That size may be selectable by a user.

The allocation set may be a fair allocation of a predetermined number of the resources of the input set among the objective functions of the resources of the input set. The resources may be data units. The resources may be units of the service capacity of an apparatus. Thus the system may have use in allocating physical resources.

Each resource of the input set may be represented by a single respective objective function. That objective function may model behaviour of the respective resource.

In another aspect there is provided a computer-implemented method for determining an allocation set of resources from an input set of resources, each resource of the input set being represented by one or more objective functions. The method comprising repeatedly performing the following steps. Forming, for each resource of the input set that is not already in the allocation set, a selection value as a biased version of an evaluation of the or each objective function representing that resource. Then, selecting the resource of the input set corresponding to the highest one of the selection values. Finally, adding the selected resource to the allocation set.

The resources may be data units or units of the service capacity of an apparatus. Thus the system may have use in allocating physical resources.

BRIEF DESCRIPTION OF THE FIGURES

The present invention will now be described by way of example with reference to the accompanying drawings. In the drawings:

Figure 1 shows an example of the Greedy Biased Expectation algorithm; Figure 2 shows an example of the Greedy Biased Expectation algorithm with automatic tuning parameter s;

Figure 3 shows an example implementation called the Multi-User pairing problem; and

Figure 4 shows an example implementation scenario which considers selecting a subset of images from a larger collection images which fairly represents the collection.

Figure 5 shows the output values representing the throughput quality for each user in the group considered in the Mulit-User paring example.

DETAILED DESCRIPTION OF THE INVENTION

The proposed approach provides a technical solution to the problem of ensuring a fair allocation of resources among a system that is described by a collection of objective set functions. The purpose of this approach is to ensure that all objectives of the system to be optimized are maximized except for a given number of outliers' objectives set as input. In practice, the fair allocation of resources among a collection of set functions usually relies on summing all the objectives and performing a single optimization over the average-value of the objectives. However, only focusing on the average-case can lead to many objectives with poor values and does not necessarily imply a fair allocation. Hence, the typical approach used do not ensure a fair allocation of the resources. The presently proposed approach solves this precise problem, namely by providing a measure for fairness as well as the associated optimization loop structure.

There is proposed herein a resource allocator for determining an allocation set of resources from an input set of resources, each resource of the input set being represented by one or more objective functions. The resource allocator comprises one or more processors configured to form the allocation set by repeatedly performing the following steps. Forming, for each resource of the input set that is not already in the allocation set, a selection value as a biased version of an evaluation of the or each objective function representing that resource. Then, selecting the resource of the input set corresponding to the highest one of the selection values. Finally, adding the selected resource to the allocation set.

The proposed approach comprises a way to measure fairness among a set of objectives in the context of submodular functions using biased expectations as well as an efficient algorithm to sequentially optimize this fairness criterion, referred to herein as the greedy algorithm. In particular, the proposed approach uses “biased expectations” instead of quantiles to efficiently measure the fairness of the allocation of the resources and by preserving the submodularity assumption, as opposed to plain quantile. The second main contribution is to use the greedy algorithm to optimize this criterion, which is also submodular, in order to provide a fair allocation. The greedy algorithm of the presently proposed approach is not the same greedy algorithm as mentioned earlier in reference to maximising a single average value. Thus, by using both these criterions, there is proposed herein a method to automatically tune the parameters to reach a given precision.

The proposed approach achieves these objectives by the described general methodology based on biased expectation and the greedy algorithm so as to sequentially provide a fair allocation of resources among the objectives of set functions. Namely, by providing a tuning parameter which allows for the level of fairness one wishes to achieve with the algorithm to be tuned. In addition, there is provided a method that automatically tunes the parameter, thereby enabling a given target specified by the user to be achieved.

The proposed approach provides a fair allocation by focusing on optimizing the quantiles instead of the worst-case objective. Using this methodology, the outliers of the system can be discarded, resulting in the ability to optimize systems that could not be previously optimized by using the traditional worst-case optimization.

Specifically, given a set V = {1, of n elements, and a collection Fi F _d Of d > 2 submodular functions defined over the ground set V, the goal is to find a set of at most K elements which maximizes the quantile of the objectives. Each resource of the input set may be represented by a single respective objective function. For example,

S _K G argmax\ _s \ _sK Q _p F ₁ (S'), ... , F _d (S) for some parameter p [0,1],

In order to achieve this, the proposed approach uses biased expectations of the sample of objective functions to measure the fairness of the given allocation. More precisely, the biased expectation plays the role of an aggregate function for the quantile and is defines as follows: A S (F_l (5), ... ,F_d (S)) = 1/s logQjJ e ^A (sF _i (5’)) for some parameter s e R. That is, each selection value may be formed in dependence on a predetermined constant raised to the power of the evaluation of the respective objective function. The constant may be Euler’s number. It can be seen that each selection value may be formed by means of a predetermined selection value function, the selection value function being such that it preserves submodularity among the objective functions.

The biased expectation can be used, instead of quantiles, in a sequential method which creates the output set S _K c y by performing the following steps. First, computing a fairness measurement. Specifically, computing the fairness of the set of objectives using the biased expectation. Then, identifying the best action. Where, for each action, a marginal gain is determined by computing the difference between the fairness computed using the biased expectation and the fairness computed using the typical method. It is then possible to add the best element to the set. That is, adding to the given set, the element which provides the best improvement over the fairness measure. This sequence of steps may then be repeated.

The above summarised approach comprises introducing biased expectations as generic aggregate functions for robustness using an algorithm called Greedy Biased Expectation with provable approximation guarantees. The algorithm is formulated as shown in Figure 1.

The Greedy Biased Expectation algorithm takes as input the ground set V, the cardinality constraint K, the collection of submodular functions F(5") = [F^S), ... , F _d (S)] and a real-valued parameter s. It returns a set S _K of cardinality at most K as an output. The algorithm proceeds sequentially in order to build the output set. It starts with an empty set S _o = 0 and adds, at each iteration t > 0, a single element et+1 among the set of elements that have not been selected yet V/S _t (cf. lines 3 and 4 of the algorithm in Figure 1). At each iteration, the algorithm adds the point et+1 from the remaining set which provides the best improvement over the current marginal value of the biased expectation. This selection process corresponds to the loop of the greedy algorithm.

Moreover, the proposed approach takes as input a tuning parameter s that can be used to tune the amount of fairness one wishes to achieve in the process. In this case, lower values of s provide an equal contribution to each objective; and larger values of s result in focusing on fewer objectives. That is, the selection value function may be dependent on a tuning parameter whereby the sensitivity of the selection value function to more or fewer objective functions can be selected. As a result, each selection value may be formed in dependence on a predetermined constant raised to the power of the evaluation of the respective objective function scaled by the tuning parameter.

The methodology used to automatically estimate the parameter s to maximize the p-th quantile is described in Figure 2. Figure 2 shows a Greedy Biased Expectation with automatic tuning of parameter s.

The advantages of the previously described greedy biased expectation scheme are that the proposed approach provides a fair allocation for systems that present outliers in comparison to existing methods. Further, the proposed approach presents a tuning parameter, which enables the level of fairness achieved to be tuned. The proposed approach additionally features a method for automatically tuning the parameter, s, for a given precision set as input by the user. Finally, the proposed approach is theoretically well-founded as it achieves some guarantees which can be mathematically corroborated. The proposed approach thus may comprise receiving from a user an input value; and selecting the tuning parameter in dependence on the input value.

The above-described approach can be used to select a size for the allocation set, add selected resources to the allocation set until the allocation set has the selected size; and output the allocation set. The allocation set can thereby provide a fair allocation of a predetermined number of the resources of the input set among the objective functions of the resources of the input set.

Some example scenarios for implementing the proposed approach will now be described. One or more of the examples describe how the resources may be data units. For example, the resources may be units of the service capacity of an apparatus.

Telecommunications companies produce many products which must consider the fair allocation of resources among a collection of objectives. For example, the case of multiple users pairing for 5G MIMO, where many users need service in the downlink. Users can be multiplexed by time, frequency, and spatial domain when the base-station has a multi-antenna arrangement. The decision of which users to be served in the same time/frequency resource is called multi-user pairing. A better scheduler is needed to provide a fair allocation for each user in this arrangement. In the current example a base antenna and a number n = 30 users V = {1, located around the antenna are considered. The objective is to select a subset of at most K = 7 users that will directly communicate with the antenna and spread the signal to other users. If one selects a subset S c y of users, the quality of communication received by user i G {1, ... , n is described by a submodular function ^(5"). In this example, it is desired to select a subset of users that will communicate with the antenna in order to provide a fair allocation of the communication throughput among all users.

Figure 3 shows an illustration of this example MU-pairing problem. On the left-hand side a base station 302 is shown with several users 304a-c. Users 304a are within the acceptable connection quality range. User 304b can be provided resources, but the quality could be improved. User 304c is an outlier, allocation of greater resources to this user will only improve their connection quality so much, and continued efforts to improve their situation are likely wasted. On the right-hand side the same base station is shown after the allocation of resources to multiple users, including users 304a-c, according to the proposed approach. To ensure fair allocation of resources only a subset of users have been selected on which to base the allocation assessment using the proposed approach described above. Users 304b and 304c are no longer considered for the purposes of allocating the resources of base station 302.

For this type of example problem, one may wish to have at least 95% percent of the users effectively covered. Thus, Algorithm 2 may be used with parameter p set to 5%. Figure 5 shows a graph of user throughput quality on a scale of zero to six for each of the 30 users. The values as shown in Figure 5 are an example of the output values representing the throughput quality of all users obtained using algorithm 2.

A second example scenario considers selecting a subset of K images from a collection V = {1, ... , n] of n images which fairly represents most of the images without considering outliers. In this example the outliers are considered to be images that appear few times or are not relevant in the dataset.

Figure 4 shows the whole collection of images which need to be represented. Some images are visually similar to each other, while others are visually very different. In this collection there are n = 8 images in total. The proposed method may be used to select K = 3 images from the collection. The images chosen are shown on the right-hand side of Figure 4 and are determined to fairly represent the initial 8 image dataset. More formally, given a subset of S' c y and a non-negative distance over images, one can measure if an image i G V is well taken into account in a subset S c y by measuring the similarity to the closest image to the subset S through the following function: j (S) = max D (i, e) which is non-negative, monotone, and submodular.

Hence, if one wants to have a subset of K images that most fairly represents the whole dataset except the p x n outliers, one can solve the following problem: where p corresponds to the proportion of the images to be discarded.

The above image selecting problem was tested on the Pokemon dataset which contains n = d. = 151 images. The normalized cosine similarity D(i,e) = ■ v _e /\vt ■ v _e \ was used, where the vectors v _e are the centered and normalized img2vec embeddings computed from an AlexNet tuned over the ImageNet data set and the second term may be added to prevent nonnegativity. Specifically, this problem was shown to be solved by running the adaptive algorithm as in Figure 2. Other example scenarios where the proposed approach may be used include creation of a balanced news feed, graph covering, natural language processing, and clustering applications.

There may also be provided a computer-implemented method for determining an allocation set of resources from an input set of resources, each resource of the input set being represented by one or more objective functions. The method comprising repeatedly performing the following steps. Forming, for each resource of the input set that is not already in the allocation set, a selection value as a biased version of an evaluation of the or each objective function representing that resource. Then, selecting the resource of the input set corresponding to the highest one of the selection values. Finally, adding the selected resource to the allocation set. Similarly, the resources may be data units or units of the service capacity of an apparatus. The applicant hereby discloses in isolation each individual feature described herein and any combination of two or more such features, to the extent that such features or combinations are capable of being carried out based on the present specification as a whole in the light of the common general knowledge of a person skilled in the art, irrespective of whether such features or combinations of features solve any problems disclosed herein, and without limitation to the scope of the claims. The applicant indicates that aspects of the present invention may consist of any such individual feature or combination of features. In view of the foregoing description it will be evident to a person skilled in the art that various modifications may be made within the scope of the invention.