Insight Centre for Data Analytics - Doctoral Theseshttps://hdl.handle.net/10468/52312024-04-22T12:02:44Z2024-04-22T12:02:44Z241Active learning in recommender systems: an unbiased and beyond-accuracy perspectiveCarraro, Diegohttps://hdl.handle.net/10468/112812023-09-26T13:42:39Z2020-12-05T00:00:00Zdc.title: Active learning in recommender systems: an unbiased and beyond-accuracy perspective
dc.contributor.author: Carraro, Diego
dc.description.abstract: The items that a Recommender System (RS) suggests to its users are typically ones that it thinks the user will like and want to consume. An RS that is good at its job is of interest not only to its customers but also to service providers, so they can secure long-term customers and increase revenue. Thus, there is a challenge in building better recommender systems.
One way to build a better RS is to improve the quality of the data on which the RS model is trained. An RS can use Active Learning (AL) to proactively acquire such data, with the goal of improving its model. The idea of AL for RS is to explicitly query the users, asking them to rate items which have not been rated yet. The items that a user will be asked to rate are known as the query items. Query items are different from recommendations. For example, the former may be items that the AL strategy predicts the user has already consumed, whereas the latter are ones that the RS predicts the user will like. In AL, query items are selected `intelligently' by an Active Learning strategy. Different AL strategies take different approaches to identify the query items.
As with the evaluation of RSs, preliminary evaluation of AL strategies must be done offline. An offline evaluation can help to narrow the number of promising strategies that need to be evaluated in subsequent costly user trials and online experiments. Where the literature describes the offline evaluation of AL, the evaluation is typically quite narrow and incomplete: mostly, the focus is cold-start users; the impact of newly-acquired ratings on recommendation quality is usually measured only for those users who supplied those ratings; and impact is measured in terms of prediction accuracy or recommendation relevance. Furthermore, the traditional AL evaluation does not take into account the bias problem. As brought to light by recent RS literature, this is a problem that affects the offline evaluation of RS; it arises when a biased dataset is used to perform the evaluation. We argue that it is a problem that affects offline evaluation of AL strategies too.
The main focus of this dissertation is on the design and evaluation of AL strategies for RSs. We first design novel methods (designated WTD and WTD_H) that `intervene' on a biased dataset to generate a new dataset with unbiased-like properties. Compared to the most similar approach proposed in the literature, we give empirical evidence, using two publicly-available datasets, that WTD and WTD_H are more effective at debiasing the evaluation of different recommender system models.
We then propose a new framework for offline evaluation of AL for RS, which we believe facilitates a more authentic picture of the performances of the AL strategies under evaluation. In particular, our framework uses WTD or WTD_H to mitigate the bias, but it also assesses the impact of AL in a more comprehensive way than the traditional evaluation used in the literature. Our framework is more comprehensive in at least two ways. First, it segments users in more ways than is conventional and analyses the impact of AL on the different segments. Second, in the same way that RS evaluation has changed from a narrow focus on prediction accuracy and recommendation relevance to a wider consideration of so-called `beyond-accuracy' criteria (such as diversity, serendipity and novelty), our framework extends the evaluation of AL strategies to also cover `beyond-accuracy' criteria. Experimental results on two datasets show the effectiveness of our new framework.
Finally, we propose some new AL strategies of our own. In particular, our new AL strategies, instead of focusing exclusively on prediction accuracy and recommendation relevance, are designed to also enhance `beyond-accuracy' criteria. We evaluate the new strategies using our more comprehensive evaluation framework.
2020-12-05T00:00:00ZAn analytics-based decomposition approach to large-scale bilevel optimisationFajemisin, Adejuyigbehttps://hdl.handle.net/10468/65682023-04-04T07:02:45Z2018-01-01T00:00:00Zdc.title: An analytics-based decomposition approach to large-scale bilevel optimisation
dc.contributor.author: Fajemisin, Adejuyigbe
dc.description.abstract: Bilevel optimisation problems contain several decision makers, each with different objectives and constraints, arranged in a hierarchical structure. One type of bilevel problem is the single-leader, multiple-follower problem, which has been used in applications like toll-setting, resource management, conflict resolution, and many others. This hierarchical structure allows for the reformulation of the forest harvesting problem as a multiple-follower bilevel problem. In the forest harvesting problem of Chapter 4, trees are cut into different log types, some of which are more valuable than others. Due to the fact that harvesting machines are designed to prioritise the production of these higher-value log types, over-production and waste of the high-value logs, as well as unfulfilled demand for the low-value logs is seen. Additionally, the discrepancy between amounts of log types expected pre-harvest and the actual amounts seen post-harvest leads to the inefficient harvesting of the forest. Despite the many approaches for solving multiple-follower problems, they are either not applicable in cases in which the follower problems are not traditional optimisation problems, or do not scale up appropriately. An example of this case occurs with the forest harvesting problem, where the follower problems are dynamic programming problems. Another example is the case where the follower problems are black-box functions. In such cases, replacing the follower problems with reformulations or optimality conditions are not applicable. Evolutionary algorithms can be used, but these are computationally-intensive schemes which do not scale up effectively. For this reason, an analytics-based approach, which is better able to sample the solution space is needed. The thesis defended throughout this dissertation is that an analytics-based decomposition approach can be used to solve largescale multiple-follower bilevel problems more efficiently than the other approaches. Specifically, the contributions of this thesis are: (i) a new class of multiple-follower bilevel problems is proposed; (ii) a novel analytics-based decomposition approach for solving this class of large-scale bilevel multiple-follower problems is given; (iii) the forest harvesting problem is reformulated as a bilevel optimisation problem to take into the account operation of harvester, and (iv) a reactive harvesting approach is developed to mitigate the effects of the uncertainty in the data .
2018-01-01T00:00:00ZAn approach to robustness in stable marriage and stable roommates problemsGenc, Begumhttps://hdl.handle.net/10468/83612023-04-04T06:59:02Z2019-01-01T00:00:00Zdc.title: An approach to robustness in stable marriage and stable roommates problems
dc.contributor.author: Genc, Begum
dc.description.abstract: This dissertation focuses on a novel concept of robustness within the context of matching problems. Our robustness notion for the stable matching framework is motivated by the unforeseen events that may occur after a matching is computed. We define the notion of (a,b)-supermatches as a measure of robustness of a matching. An (a,b)-supermatch characterizes a stable matching such that if any combination of 'a' pairs want to leave the matching, there exists an alternative matching in which those 'a' pairs are assigned new partners, and in order to obtain the new assignment at most 'b' other pairs are broken. We first formally define the notion of (a,b)-supermatches by using one of the most famous matching problems, namely the Stable Marriage problem (SM), as the platform. We name the problem of finding an (a,b)-supermatch to the SM as the Robust Stable Marriage problem (RSM). Subsequently, we prove that RSM is NP-hard, and the decision problem for the case where a=1 (i.e. deciding if there exists a (1,b)-supermatch) is NP-complete. We also develop a constraint programming model and a number of meta-heuristic approaches to find a (1,b)-supermatch that minimizes the value of 'b' for the RSM. Following the results on the RSM, we extend the notion of (a,b)-supermatches to the Stable Roommates problem (SR), namely, the Robust Stable Roommates problem (RSR). We show that the NP-hardness is also valid for the RSR, and we also define a polynomial-time procedure for the RSR to decide if a given stable matching is a (1,b)-supermatch. Similarly, we provide a number of meta-heuristic models to solve the optimization problem for finding a (1,b)-supermatch that minimizes the value of 'b'. We conclude this dissertation by providing some empirical results on the robustness of different datasets of RSM and RSR instances.
2019-01-01T00:00:00ZAsynchronous distributed clustering algorithms for wireless mesh networkQiao, Chenghttps://hdl.handle.net/10468/113002023-04-04T10:56:44Z2021-04-10T00:00:00Zdc.title: Asynchronous distributed clustering algorithms for wireless mesh network
dc.contributor.author: Qiao, Cheng
dc.description.abstract: Wireless Mesh Networks are becoming increasingly important in many applications.
In many cases, data is acquired by devices that are distributed in space, but
effective actions require a global view of that data across all devices. Transmitting
all data to the centre allows strong data analytics algorithms to be applied,
but consumes battery power for the nodes, and may cause data overload. To
avoid this, distributed methods try to learn within the network, allowing each
agent to learn a global picture and take appropriate actions.
For distributed clustering in particular, existing methods share simple cluster
descriptions until the network stabilises. The approaches tend to require either
synchronous behaviour or many cycles, and omit important information about
the clusters. In this thesis, we develop asynchronous methods that share richer
cluster models, and we show that they are more effective in learning the global
data patterns.
Our underlying method describes the shape and density of each cluster, as well
as its centroid and size. We combine cluster models by re-sampling from received
models, and then re-clustering the new data sets. We then extend the approach,
to allowing clustering methods that do not require the final number of clusters as
input. After that, we consider the cases that there might be sub-groups of agents
that are receiving different patterns of data. Finally, we extend our approaches
to scenarios where each agent has no idea about whether there is a single pattern
or are multiple patterns.
We demonstrate that the approaches can regenerate clusters that are similar to
the distributions that were used to create the test data. When the number of
clusters are not available, the learned number of clusters is close to the ground
truth. The proposed algorithms can learn how data points are clustered even
when there are multiple patterns in the network. When the number of patterns
(single or multiple) is not known in advance, the proposed methods Optimised
KDE and DBSCAN preform well in detecting multiple patterns. Although they
perform worse in detecting the single pattern, they can still learn how data points
are clustered.
2021-04-10T00:00:00ZAutonomous system control in unknown operating conditionsSohège, Yveshttps://hdl.handle.net/10468/119012023-04-04T11:03:45Z2021-08-24T00:00:00Zdc.title: Autonomous system control in unknown operating conditions
dc.contributor.author: Sohège, Yves
dc.description.abstract: Autonomous systems have become an interconnected part of everyday life with the
recent increases in computational power available for both onboard computers and
offline data processing. The race by car manufacturers for level 5 (full) autonomy in
self-driving cars is well underway and new flying taxi service startups are emerging
every week, attracting billions in investments. Two main research communities,
Optimal Control and Reinforcement Learning stand out in the field of autonomous
systems, each with a vastly different perspective on the control problem. Controllers
from the optimal control community are based on models and can be rigorously
analyzed to ensure the stability of the system is maintained under certain operating
conditions. Learning-based control strategies are often referred to as model-free and
typically involve training a neural network to generate the required control actions
through direct interactions with the system. This greatly reduces the design effort
required to control complex systems. One common problem both learning- and model-
based control solutions face is the dependency on a priori knowledge about the system
and operating conditions such as possible internal component failures and external
environmental disturbances. It is not possible to consider every possible operating
scenario an autonomous system can encounter in the real world at design time. Models
and simulators are approximations of reality and can only be created for known
operating conditions. Autonomous system control in unknown operating conditions,
where no a priori knowledge exists, is still an open problem for both communities and
no control methods currently exist for such situations.
Multiple model adaptive control is a modular control framework that divides the
control problem into supervisory and low-level control, which allows for the
combination of existing learning- and model-based control methods to overcome the
disadvantages of using only one of these. The contributions of this thesis consist of
five novel supervisory control architectures, which have been empirically shown to
improve a system’s robustness to unknown operating conditions, and a novel low-
level controller tuning algorithm that can reduce the number of required controllers
compared to traditional tuning approaches. The presented methods apply to any
autonomous system that can be controlled using model-based controllers and can
be integrated alongside existing fault-tolerant control systems to improve robustness
to unknown operating conditions. This impacts autonomous system designers by
providing novel control mechanisms to improve a system’s robustness to unknown
operating conditions.
2021-08-24T00:00:00ZChain-based recommendationsRana, Arpithttps://hdl.handle.net/10468/97432023-04-04T11:04:47Z2019-10-14T00:00:00Zdc.title: Chain-based recommendations
dc.contributor.author: Rana, Arpit
dc.description.abstract: Recommender systems are discovery tools. Typically, they infer a user's preferences from her behaviour and make personalized suggestions. They are one response to the overwhelming choices that the Web affords its users. Recent studies have shown that a user of a recommender system is more likely to be satisfied by the recommendations if the system provides explanations that allow the user to understand their rationale, and if the system allows the user to provide feedback on the recommendations to improve the next round of recommendations so that they take account of the user's ephemeral needs. The goal of this dissertation is to introduce a new recommendation framework that offers a better user experience, while giving quality recommendations. It works on content-based principles and addresses both the issues identified in the previous paragraph, i.e.\ explanations and recommendation feedback. We instantiate our framework to produce two recommendation engines, each focusing on one of the themes: (i) the role of explanations in producing recommendations, and (ii) helping users to articulate their ephemeral needs. For the first theme, we show how to unify recommendation and explanation to a greater degree than has been achieved hitherto. This results in an approach that enables the system to find relevant recommendations with explanations that have a high degree of both fidelity and interpretability. For the second theme, we show how to allow users to steer the recommendation process using a conversational recommender system. Our approach allows the user to reveal her short-term preferences and have them taken into account by the system and thus assists her in making a good decision efficiently. Early work on conversational recommender systems considers the case where the candidate items have structured descriptions (e.g.\ sets of attribute-value pairs). Our new approach works in the case where items have unstructured descriptions (e.g.\ sets of genres or tags). For each of the two themes, we describe the problem settings, the state-of-the-art, our system design and our experiment design. We evaluate each system using both offline analyses as well as user trials in a movie recommendation domain. We find that the proposed systems provide relevant recommendations that also have a high degree of serendipity, low popularity-bias and high diversity.
2019-10-14T00:00:00ZCognitive radio adaptive rendezvous protocols to establish network services for a disaster responseGhafoor, Saimhttps://hdl.handle.net/10468/71312023-04-04T07:14:33Z2018-01-01T00:00:00Zdc.title: Cognitive radio adaptive rendezvous protocols to establish network services for a disaster response
dc.contributor.author: Ghafoor, Saim
dc.description.abstract: Disasters are catastrophic events that cause great damage or loss of life. In disasters, communication services might be disrupted due to damage to the existing network infrastructure. Temporary systems are required for victims and first responders, but installing them requires information about the radio environment and available spectrum. A cognitive radio (CR) can be used to provide a flexible and rapidly deployable temporary system due to its sensing, learning and decision-making capabilities. This thesis initially examines the potential of CR technology for disaster response networks (DRN) and shows that they are ideally suited to fulfill the requirements of a DRN. A software defined radio based prototype for multiple base transceiver stations based cellular network is proposed and developed. It is demonstrated that system can support a large number of simultaneous calls with sufficient call quality, but only when the background interference is low. It is concluded that to provide call quality with acceptable latency and packet losses, the spectrum should be used dynamically for backhaul connectivity. The deployment challenges for such a system in a disaster include the discovery of the available spectrum, existing networks, and neighbours. Furthermore, to set up a network and to establish network services, initially CR nodes are required to establish a rendezvous. However, this can be challenging due to unknown spectrum information, primary radio (PR) activity, nodes, and topology. The existing rendezvous strategies do not fulfill the DRN requirements and their time to rendezvous (TTR) is long. Therefore, we propose an extended modular clock algorithm (EMCA) which is a multiuser blind rendezvous protocol, considers the DRN requirements and has short TTR. For unknown nodes and topologies, a general framework for self-organizing multihop cooperative fully blind rendezvous protocol is also proposed, which works in different phases, can terminate when sufficient nodes are discovered, and is capable of disseminating the information of nodes which enter or leave a network. A synchronization mechanism is presented for periodic update of rendezvous information. An information exchange mechanism is also proposed which expedites the rendezvous process. In both single and multihop networks, EMCA provides up to 80% improvement in terms of TTR over the existing blind rendezvous strategies while considering the PR activity. A simple Random strategy, while being poorer than EMCA, is also shown to outperform existing strategies on average. To achieve adaptability in the presence of unknown PR activity, different CR operating policies are proposed which avoid the channels detected with PR activity to reduce the harmful interference, provide free channels to reduce the TTR, and can work with any rendezvous strategy. These policies are evaluated over different PR activities and shown to reduce the TTR and harmful interference significantly over the basic Listen before Talk approach. A proactive policy, which prefers to return to channels with recent lower PR activity, is shown to be best, and to improve the performance of all studied rendezvous strategies.
2018-01-01T00:00:00ZCombinatorial optimisation for sustainable cloud computingDe Cauwer, Milanhttps://hdl.handle.net/10468/69032023-04-04T07:10:30Z2018-01-01T00:00:00Zdc.title: Combinatorial optimisation for sustainable cloud computing
dc.contributor.author: De Cauwer, Milan
dc.description.abstract: Enabled by both software and hardware advances, cloud computing has emerged as an efficient way to leverage economies of scale for building large computational infrastructures over a global network. While the cost of computation has dropped significantly for end users, the infrastructure supporting cloud computing systems has considerable economic and ecological costs. A key challenge for sustainable cloud computing systems in the near future is to maintain control over these costs. Amid the complexity of cloud computing systems, a cost analysis reveals a complex relationship between the infrastructure supporting actual computation on a physical level and how these physical assets are utilised. The central question tackled in this dissertation is how to best utilise these assets through efficient workload management policies. In recent years, workload consolidation has emerged as an effective approach to increase the efficiency of cloud systems. We propose to address aspects of this challenge by leveraging techniques from the realm of mathematical modeling and combinatorial optimisation. We introduce a novel combinatorial optimisation problem suitable for modeling core consolidation problems arising in workload management in data centres. This problem extends on the well-known bin packing problem. We develop competing models and optimisation techniques to solve this offline packing problem with state-of-the-art solvers. We then cast this newly defined combinatorial optimisation problem in an semi-online setting for which we propose an efficient assignment policy that is able to produce solutions for the semi-online problem in a competitive computational time. Stochastic aspects, which are often faced by cloud providers, are introduced in a richer model. We then show how predictive methods can help decision makers dealing with uncertainty in such dynamic and heterogeneous systems. We explore a similar but relaxed problem falling within the scope of proactive consolidation. This is a relaxed consolidation problem in which one decides which, when and where workload should be migrated to retain minimum energy cost. Finally, we discuss ongoing efforts to model and characterise the combinatorial hardness of bin packing instances, which in turn will be useful to study the various packing problems found in cloud computing environments.
2018-01-01T00:00:00ZComputing policy parameters for stochastic inventory control using stochastic dynamic programming approachesVisentin, Andreahttps://hdl.handle.net/10468/106012023-04-04T10:45:02Z2020-08-29T00:00:00Zdc.title: Computing policy parameters for stochastic inventory control using stochastic dynamic programming approaches
dc.contributor.author: Visentin, Andrea
dc.description.abstract: The objective of this work is to introduce techniques for the computation of optimal and near-optimal inventory control policy parameters for the stochastic inventory control problem under Scarf’s setting. A common aspect of the solutions presented herein is the usage of stochastic dynamic programming approaches, a mathematical programming technique introduced by Bellman. Stochastic dynamic programming is hybridised with branch-and-bound, binary search, constraint programming and other computational techniques to develop innovative and competitive solutions.
In this work, the classic single-item, single location-inventory control with penalty cost under the independent stochastic demand is extended to model a fixed review cost. This cost is charged when the inventory level is assessed at the beginning of a period. This operation is costly in practice and including it can lead to significant savings. This makes it possible to model an order cancellation penalty charge.
The first contribution hereby presented is the first stochastic dynamic program- ming that captures Bookbinder and Tan’s static-dynamic uncertainty control policy with penalty cost. Numerous techniques are available in the literature to compute such parameters; however, they all make assumptions on the de- mand probability distribution. This technique has many similarities to Scarf’s stochastic dynamic programming formulation, and it does not require any ex- ternal solver to be deployed. Memoisation and binary search techniques are deployed to improve computational performances. Extensive computational studies show that this new model has a tighter optimality gap compared to the state of the art.
The second contribution is to introduce the first procedure to compute cost- optimal parameters for the well-known (R, s, S) policy. Practitioners widely use such a policy; however, the determination of its parameters is considered com- putationally prohibitive. A technique that hybridises stochastic dynamic pro- gramming and branch-and-bound is presented, alongside with computational enhancements. Computing the optimal policy allows the determination of op- timality gaps for future heuristics. This approach can solve instances of consid- erable size, making it usable by practitioners. The computational study shows the reduction of the cost that such a system can provide.
Thirdly, this work presents the first heuristics for determining the near-optimal parameters for the (R,s,S) policy. The first is an algorithm that formally models the (R,s,S) policy computation in the form of a functional equation. The second is a heuristic formed by a hybridisation of (R,S) and (s,S) policy parameters solvers. These heuristics can compute near-optimal parameters in a fraction of time compared to the exact methods. They can be used to speed up the optimal branch-and-bound technique.
The last contribution is the introduction of a technique to encode dynamic programming in constraint programming. Constraint programming provides the user with an expressive modelling language and delegates the search for the solution to a specific solver. The possibility to seamlessly encode dynamic programming provides new modelling options, e.g. the computation of optimal (R,s,S) policy parameters. The performances in this specific application are not competitive with the other techniques proposed herein; however, this encoding opens up new connections between constraint programming and dynamic programming. The encoding allows deploying DP based constraints in modelling languages such as MiniZinc. The computational study shows how this technique can outperform a similar encoding for mixed-integer programming.
2020-08-29T00:00:00ZEvaluating sets of multi-attribute alternatives with uncertain preferencesToffano, Federicohttps://hdl.handle.net/10468/112772023-04-04T10:58:34Z2020-09-01T00:00:00Zdc.title: Evaluating sets of multi-attribute alternatives with uncertain preferences
dc.contributor.author: Toffano, Federico
dc.description.abstract: In a decision-making problem, there can be uncertainty regarding the user preferences concerning the available alternatives. Thus, for a decision support system, it is essential to analyse the user preferences to make personalised recommendations. In this thesis we focus on Multiattribute Utility Theory (MAUT) which aims to define user preference models and elicitation procedures for alternatives evaluated with a vector of a fixed number of conflicting criteria.
In this context, a preference model is usually represented with a real value function over the criteria used to evaluate alternatives, and an elicitation procedure is a process of defining such value function. The most preferred alternative will then be the one that maximises the value function.
With MAUT models, it is common to represent the uncertainty of the user preferences with a parameterised value function. Each instantiation of this parameterisation then represents a user preference model compatible with the preference information collected so far. For example, a common linear value function is the weighted sum of the criteria evaluating an alternative, which is parameterised with respect to the set of weights. We focus on this type of preference models and in particular on value functions evaluating sets of alternatives rather single alternatives. These value functions can be used for example to define if a set of alternatives is preferred to another one, or which is the worst-case loss in terms of utility units of recommending a set of alternatives.
We define the concept of setwise minimal equivalent subset (SME) and algorithms for its computation. Briefly, SME is the subset of an input set of alternatives with equivalent value function and minimum cardinality. We generalise standard preference relations used to compare single alternatives with the purpose of comparing sets of alternatives. We provide computational procedures to compute SME and evaluate preference relations with particular focus on linear value functions.
We make extensive use of the Minimax Regret criterion, which is a common method to evaluate alternatives for potential questions and recommendations with uncertain value functions. It prescribes an outcome that minimises the worst-case loss with respect to all the possible parameterisation of the value function. In particular, we focus on its setwise generalisation, namely \textit{Setwise Minimax Regret} (SMR), which is the worst-case loss of recommending a set of alternatives. We provide a novel and efficient procedure for the computation of the SMR when supposing a linear value function.
We also present a novel incremental preference elicitation framework for a supplier selection process, where a realistic medium-size factory inspires constraints and objectives of the underlying optimization problem. This preference elicitation framework applies for generic multiattribute combinatorial problems based on a linear preference model, and it is particularly useful when the computation of the set of Pareto optimal alternatives is practically unfeasible.
2020-09-01T00:00:00Z