MPhil, Part III, and Part II Project Suggestions (2020-2021)
|
|
Please contact Eiko Yoneki (email: eiko.yoneki@cl.cam.ac.uk) if you are interested in any project below. * indicates high recommendation! 1. Model-based Reinforcement Learning in Computer Systems ** Contact:
Eiko Yoneki (with Sami Alabed)
Reinforcement learning (RL) is gaining interest as a generic optimisation and control method in data management tasks such as resource management/scheduling, database tuning, or stream processing. A central challenge in applying RL to such problems are long decision evaluation times. A single step in a real system may take multiple minutes, as opposed to simulators for standard benchmark tasks (e.g. Atari games), which can execute thousands of steps per second.
One way of improving sample efficiency is model-based RL [1], wherein a model of the environment is learned and subsequently used to plan and evaluate decisions. A 'world-model' approach first learns a compressed version of a state representation, then a recurrent mixture density network to predict future state / reward distributions of compressed states which can be used in place of a simulator [2]. In this project, the student will evaluate a world-model based approach against a model free approach using software infrastructure built in our group [3]. In [3], A2C (Advantage Actor Critic) algorithm is used. However the world model is algorithm agnostic and you can further investigate other algorithms such as the Rainbow comparison [7], which was used Model-Based Reinforcement Learning for Atari paper for their comparisons. You can explore PPO or C51, which could yield better sample complexity and/or max performance.
Example applications include stream processing scheduling, static graph rewriting (e.g. TensorFlow, LLVM IRs), and various database administration tasks. The aim of the project is to evaluate different representations (e.g. graph neural networks) and planning modes to gain novel insights into cost/benefits of model-based deep RL for this domain. The previous project work on bit-rate control in networking [4] can be used as a starting point. A good approach could be to use a latent space representation of the server state - e.g. through a PCA and this would also be closer to WM approach, where a VAE is used to get a latent space representation of pixel images. A VAE with only one layer network should be conceptually equivalent to a PCA. Further complex modelling can be explored and an example will be applying WM to the testbed setup in [5], which ca be compared to OBOE algorithm [6].
2. Optimisation of DNN Accelerators using Bayesian optimisation ** Contact:
Eiko Yoneki (with Sami Alabed)
A recent trend in deep neural network (DNN) development is to extend the reach of deep learning applications
to platforms that are more resource and energy constrained, e.g., mobile devices. In order to reduce the DNN model size and improve the hardware processing efficiency, and have resulted in DNNs that are much more compact in their structures and/or have high data sparsity. These compact or sparse models are different from the traditional large ones in that there is much more variation in their layer shapes and sizes, and often require specialised hardware to exploit sparsity for performance improvement. Therefore, many DNN accelerators designed for large DNNs do not perform well on these models.
This project aims at optimising the design of DNN accelerators, where Eyeriss [1] is used as a DNN accelerator architecture model designed for running compact and sparse DNNs. The model involves various parameters and based on the goal such as the processing speed or energy efficiency the model will be different. Bayesian optimisation (e.g., [2]) offers a data-efficient approach to global optimisation of black-box functions by building a model of the unknown function, including our uncertainty about its values we have yet to observe.
The tasks of the project starts writing a simulator from the model described in [1]. Using simulation, various objective functions will be examined exploring a large parameter space for the model. It will be good to add multi objective function for BO. The result could be compared to other blackbox optimisation tools.
If time allows, the structured BO described in [3] could be explored to deal with high dimensional parameter space.
[1] Yu-Hsin Chenet al.: Eyeriss v2: A Flexible Accelerator for Emerging Deep Neural Networks on Mobile Devices. 3. Explainable Reinforcement Learning for Device Placement ** Contact:
Eiko Yoneki (with Sami Alabed)
Task scheduling over a finite number of resources in order to maximise resources efficiency is a traditionally difficult problem with heuristics made to approximate it. Previous work used Hierarchical Reinforcement Learning [1] to find optimal task scheduling for TensorFlow graph operations.
This project proposes to investigate Contextual Multi-Armed bandit [2] with Bayesian learning (possible Bayesian neural networks) to allow injecting expert knowledge in the system. Using Bayesian models to define a hierarchy of the system allows it to converge faster and be easier to understand.
For this project, Park [3] provides a simulation-based environment to test task scheduling on a TensorFlow graph. TensorFlow Probability [2] provides a probabilistic programming language that makes it possible to define Bayesian models that interacts with deep learning models.
[1] https://ai.google/research/pubs/pub46646 4. Bayesian Optimisation for Query Optimisation in PostgresSQL ** Contact:
Eiko Yoneki (with Sami Alabed)
Query optimisation is several decades-long problems that have made progress slowly through the use of heuristics and handwritten planners. Query optimisation is the process of choosing the best plan for a given SQL query. Recent trends in applying ML to system problems considered optimisation through the use of Reinforcement Learning (RL), random forests, support vector machine, hill climbing, etc... but all of these methods require a large number of data samples and training iterations.
This project instead focuses on using Bayesian Optimisation (BO) [1] to choose the optimal execution plan. BO is a framework for selecting optimal action when data is sparse or expensive to generate; by building a model to approximate the system, then finds points in this model that fulfil an objective. Starting point would be to use BoTorch [2] an open-source framework that provides a implementation of various BOs. For evaluation, Park [3] provides a simulation-based environment to test ideas rapidly, however, Park's query optimisation as of now isn't complete - so part of the work is to contribute an open-source extension to Park. Final model can be tested on PostgresSQL.
[1] Taking the human out of the loop: A review of Bayesian optimization 5. Bayesian Optimisation over discrete domain in RocksDB ** Contact:
Eiko Yoneki (with Sami Alabed)
RocksDB [1] is an embedded-key value store used by many distributed systems application to store state reliably. It has a large configurations space that is a mix of discrete and continuous variables.
This project will use Bayesian Optimisation (BO) [2] to optimise these parameters, considering the discrete variables. Commonly, Gaussian processes (GP) [3] are used as the machine learning model that builds approximation of the system. However, GP struggles with large dimensions and especially struggles with discrete variables. This work proposes implementing a type of sparse GPs that allows inference over discrete variables [4] (more theoretical) or possibly using Bayesian Neural Networks [3] (more applied). And contributing the model to TensorFlow probability.
[1] https://github.com/facebook/rocksdb 6. Structured Bayesian optimisation with probabilistic programs ** Contact:
Eiko Yoneki (with Sami Alabed)
Bayesian optimisation (e.g., [1]) offers a data-efficient approach to global optimization of black-box functions by building a model of the unknown function, including our uncertainty about its values we have yet to observe. [2] introduces a general framework for performing structured Bayesian optimization, where a probabilistic programming language provides a flexible means for defining surrogate models that can incorporate prior knowledge of structure in the underlying problem. The goal of this project is to revisit this methodology using Pyro [3] as a language for defining these models, (i) exploring to what extent automatic inference and automatic acquisition function can be used in a generic library for Bayesian optimization, and (ii) to what extent probabilistic programs in Pyro that are customized to particular targets can accelerate optimization. This project will involve contributing to Pyro, an open-source probabilistic programming language based on PyTorch.
Prerequisites: a familiarity with Python and PyTorch, and ideally also with the basics of variational inference.
[1] Practical Bayesian Optimization of Machine Learning Algorithms 7. Optimisation of JVM Garbage Collection using ML (Bayesian Optimisation) * Contact:
Eiko Yoneki This project extends the Cassandra case study [1,2]
in incremental ways:
1) Cassandra database was
only executed in one setting. We could create an auto-tuner that is able to deal
with a wider variety of settings. This includes:
-
Changing the heap size of the JVM
-
Changing the underlying hardware of Cassandra
-
Changing the underlying hardware of YCSB (Yahoo! Cloud Serving Benchmark)
2) Applying it to other JVM
applications (such as other databases, anything where we have a rigorous
benchmark for throughput and latency)
3) Looking at some of the
other JVM flags (we only tuned three) as well as the other JVM garbage collector For evaluation following two points are evaluated.
1) No GC option as baseline
2) Various GC
implementations (i.e. some are good on certain workloads) [1]
https://www.cl.cam.ac.uk/~ey204/pubs/2017_WWW.pdf 8. Hierarchical Device Placement from Probabilistic Perspective * Contact:
Eiko Yoneki (with Sami Alabed)
This project tackles the hierarchical device placement from probabilistic perspective to seek further improvement to the original work by Google [1]. In [1], two networks, one a grouper and one a placer are used. The grouper learns valid grouping of TensorFlow operations and the placer learns optimal placement on multiple devices. The idea in this project is to replace the grouper network with a Variational Autoencoder (VAE) network that in the latent space and using Bayesian Optimisation (BO) to generate valid grouping representation, similar approach to [2]. The output will be fed into another BO that learns the optimal placement, which is a similar approach described in our BOAT project 3] learning the placement for distributed SGD. Furthermore you can add the second placer learning multiple objectives rather than just the runtime improvement: by making it learn more correlated tasks it should be expected to be converged faster.
[1] A. Mirhoseini et al.: A Hierarchical Model for Device Placement, LCLR, 2018
9.
Learning Compound Index Selection in Database using Deep Reinforcement Learning
* Contact:
Eiko Yoneki (with Sami Alabed)
The project addresses the performance improvement (i.e. speed-up) of database queries by optimising database compound index selection, which requires complex decision making operation including what to index and when to index. The project is tackled by applying Deep Reinforcement Learning (DRL).
Injecting task-specific knowledge into the tuner for a task may allow for more efficient exploration of candidate configurations. We apply this idea to the task of index set selection to accelerate database workloads. Index set selection has been amenable to recent applications of vanilla deep RL, but real deployments remain out of reach. You would explore how learning index selection can be enhanced with task-specific inductive biases, specifically by encoding these inductive biases in better action structures. Index selection-specific action representations arise when the problem is reformulated in terms of permutation learning and we rely on recent work for learning RL policies on permutations. Through this approach, we build an indexing agent that is able to achieve improved indexing and validate its behaviour with task-specific statistics. The project can start from [1] and further build up tuning system.
[1] J. Welborn et al.: Learning Index Selection with Structured Action Spaces. 2019.
10.
Optimising Neural Network Model over Power Consumption
Contact:
Eiko Yoneki
In this project, you would tune neural network model itself. Pick one typical Deep Neural Network application (e.g. image classification), and play with various hyper-parameters, where hyper-parameters might take substantially different values for the best accuracy or performance. Especially you can set an objective function on reducing the power consumption. You would explore various parameters based experiments and build up a probabilistic model expressing the parameter relationship applying the BOAT technique (see [1] and [2]). Also you would explore recent Google’s hyper parameter tuning on Google Cloud Platform [3], in comparison to the above approach.
[1] http://www.cl.cam.ac.uk/~ey204/pubs/2017_WWW.pdf
11.
Optimisation of Parallel SSSP over dynamically changing road networks
Contact:
Eiko Yoneki The road network is static but the edge weight changes.
In this project, the number of nodes in the road is 8000. The goal is calculating SSSP for 10,000 agents, where source to destination for each agent is static). Simply calculating SSSP sequentially takes a long time. Writing
multi-threading code can only increase the parallelism depending on the number of cores. The following is the basic goal and depending on how your idea evolves, it can get additional functionality. + Reduce the number of agents to calculate path: prioritise the subgraph to recalculate based on the density of agents (i.e. less than 10 agents - no update of subgraph) and/or adding prediction/trend of agents' movement to identify potential high density subgraphs. + Reduce the number of update on the edge weight: prioritise the subgraph to recalculate based on the volume of the edge weight update (i.e. less than 10 update of weight - no update of subgraph) Contact EmailPlease email to eiko.yoneki@cl.cam.ac.uk for any question. |