Computer Laboratory

MPhil, Part III, and Part II Project Suggestions (2018-2019)

Contact

 

 

 

 

 

 

 

  

 

For 2019-2020 suggestion, please see 2019-2020 project suggestion page!

Please contact Eiko Yoneki (email: eiko.yoneki@cl.cam.ac.uk) if you are interested in any project below. * indicates high recommendation!

1.  Tuning Neural Networking Compression with Hierarchical Reinforcement Learning *

Contact: Eiko Yoneki (with Michael Schaarschmidt)

Executing neural network tasks on mobile and edge devices (e.g. facial recognition on smart phones) is gaining increasing focus in the systems community due to constraints in CPU, memory and energy usage on such devices. Consequently, neural networks trained on large servers usually need to be compressed to be fit for low power mobile execution. Recent work has explored various techniques to automatically combine various compression and quantization techniques [1, 2]. This project will investigate hierarchical reinforcement learning [3] to improve on these existing search techniques by attempting to model fine-grained dependencies between different compression and quantization methods.

 

[1] https://www.tik.ee.ethz.ch/file/79a7dd6f6370f809e6180c0746232283/mobisys18-liu.pdf

 

[2] https://arxiv.org/pdf/1806.03723.pdf

 

[3] https://ai.google/research/pubs/pub46646

 

2.  Model-based Reinforcement Learning in Computer Systems *

Contact: Eiko Yoneki (with Michael Schaarschmidt)

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. The goal of this project is to investigate recent work in learning to construct environment models in the context of database administration. The student will use an existing framework to evaluate RL on automatic index selection, and attempt to accelerate training and improve result quality by implementing and evaluating approaches such as Imagination-Augmentation [2,3,4].

[1] https://arxiv.org/pdf/1708.05866.pdf

 

[2] https://arxiv.org/abs/1707.06203

 

[3] https://deepmind.com/blog/agents-imagine-and-plan/

 

[4] https://arxiv.org/abs/1707.06170

 

3.  Reinforcement Learning for Automatic Index Selection in SQL Databases  **

Contact: Eiko Yoneki (with Michael Schaarschmidt)

Index selection is a standard database administration task which is often performed by human experts, typically assisted by profiling tools [0]. Selecting the optimal set of indices is difficult as it depends on query structure, data distribution, anad workload distribution. As each index incurs memory and maintenance cost when inserting new data, the aim of index selection is to identify the minimal number of indices meeting performance requirements (query latency).

 

Previous work in this group has implemented a framework to select compound indices in NoSQL databases such as MongoDB using deep reinforcement learning and pre-existing log data. The goal of the project is to investigate the applicability of this framework to indexing semantics [1] in relational databases such as PostgreSQL. Experimental work in the literature has explored this for single-key indices [2], but not compound cases.


In general, labelling training data is increasingly the bottleneck in deploying machine learning systems and generating labelling function based on heuristics is a growing research topic. Possibly you can extend a project for the general model building using a weak supervision [3].

 

[0] https://stratos.seas.harvard.edu/files/a4-idreos.pdf

 

[1] https://www.postgresql.org/docs/10/static/indexes-multicolumn.html

 

[2] https://arxiv.org/pdf/1801.05643.pdf

 

[3] A. Ratner, S. H. Bach, H. Ehrenberg, J. Fries, S. Wu, and C. Re. Snorkel: Rapid training data creation with weak supervision, VLDB, 2017. https://dawn.cs.stanford.edu/2017/05/08/snorkel/

 

4.  Deep Reinforcement Learning in Networking **

Contact: Eiko Yoneki (with Michael Schaarschmidt)

Modern network infrastructure is increasingly driven by software-defined components. This opens up ample opportunities to explore modern data-driven machine learning methods in traffic protocols. Early work has explored deep reinforcement learning in routing [0].

 

Until recently, standard purpose network simulators (e.g. Ns-3 [1]) were not available via common reinforcement learning benchmark interfaces such as OpenAI gym. An open source bridge between a gym-like interface and Ns-3 has now become available [1], and several example tasks are provided. The aim of this project is to evaluate a baseline deep reinforcement learning algorithm (e.g. high-performance DQN implementation available in RLgraph [2]) on some of these tasks, and subsequently implement and explore approaches from one of the following: Hierarchical RL, model-based RL, Neural combinatorial optimization/optimal transport theory (guidance can be given depending on background and student interests).

 

[0] http://www.cs.huji.ac.il/~schapiram/Learning_to_Route%20(NIPS).pdf

 

[1] https://arxiv.org/pdf/1810.03943.pdf

 

[2] https://github.com/rlgraph/rlgraph

 

5. Convolutional Neural Network for Raspberry Pi 

Contact: Eiko Yoneki

In this project, you will build Convolutional Neural Network (CNN) Library for raspberry Pi in C++. Raspberry Pi has limited computational capabilities comparing to the conventional desktop computers, and you will build up a CNN library specifically designed for Raspberry Pi. The basis for it was to see if parallel training of a convolutional neural network across multiple Raspberry Pis was feasible and provided any performance benefits compared to training a network on a single, faster machine. You would start from our current PiCNN Library, where the basic functionalities are equipped. Your task is extending our current PiCNN to distributed setting with implementing a distributed parameter server architecture to schedule updates and synchronize them via a python script using Berkeley's Ray project [1] including performance improvement.   Required skill sets include Linux, C++, basic knowledge of Computer System’s architecture, basics of Machine Learning, Distributed Systems.

[1] https://github.com/ray-project/tutorial/blob/master/examples/sharded_parameter_server.ipynb

6. Optimisation of JVM Garbage Collection using ML *

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

[2] https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-900.html

7. 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] https://www.cl.cam.ac.uk/~ey204/pubs/2017_WWW.pdf

[2] https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-900.html

[3] https://cloud.google.com/blog/products/gcp/hyperparameter-tuning-on-google-cloud-platform-is-now-faster-and-smarter

 

8. Unikernel over Raspberry Pi: Building Data Processing Platform

Contact: Eiko Yoneki

This project builds a unikernel-based distributed data processing platform over Raspberry Pi clusters, where mapreduce type of operation or simple neural network training and inference can be run. A unikernel is a form of monolithic operating system, but instead of being general purpose a unikernel is built with a single task in mind. By removing the unneeded functionality of an operating system, unikernels bring about a variety of advantages such as extremely small compared to conventional operating systems. Such small footprint makes movement of code to the distributed nodes much faster and easier to deal with limited availability of memory in Raspberry pi. We built a project, RaDiCS [2], where unikernel currently runs over Raspberry pi using QEMU emulator and it can be a starting point of the project. One of the challenges in this project is optimising the performance of unikernel in Raspberry pi. Potential applications running over the built distributed platform will be a type of neural network applications, where each feature can be trained separately without constant synchronisation over the layer of NN model, and parallelism using 100s of Paspberry pis can be deployed.

[1] Jitsu: Just-In-Time Summoning of Unikernels, NSDI, 2015.

[2] RaDiCS https://gitlab.com/RaspiUnikernel/RaDiCS.

9.  Dynamic Task Scheduling on Heterogeneous CPU/GPU Environment using ML for Parallel Processing

Contact: Eiko Yoneki

In this project, various aspects of parallel processing will be explored using a new generation of CPU/GPU integrated board. We use NVIDIA’s Jetson X2. This new GPUs makes it possible to cluster the GPU nodes for different scale of parallel processing. Various applications running over X2 will be investigated including graph processing and neural network training using the Tensorflow framework. Graph processing can take advantage of processor heterogeneity to adapt to structural data patterns. The overall aim of graph processing can be seen as scheduling irregular tasks to optimise data-parallel heterogeneous graph processing, by analysing the graph at runtime and dispatching graph elements to appropriate computation. Various task scheduling strategies over NN applications could be explored such as mixture of model parallelism and data parallelism.

In comparison to the above approach, several types of GPU machines in cluster computing environment will be explored. Furthermore, our recent work, BOAT [1], could be used for optimisation of complex parameter space.

[1] V. Dalibard, M. Schaarschmidt, and E. Yoneki: BOAT: Building Auto-Tuners with Structured Bayesian Optimization, WWW, 2017.  https://github.com/VDalibard/BOAT.

10. Building Graph Query Function using Functional Programming

Contact: Eiko Yoneki

Demand to store and search of online data with graph structure is emerging. Such data range from online social networks to web links which requires efficient query processing in a scalable manner. In this project, you will build a graph query function (layer) to achieve efficient graph data processing. The graph query function builds on a lazy graph loaded from multiple sources and performs queries at the same speed or faster than a relational database. The function should be written in Clojure or another functional language to support practical lazy loading from data source to an in-memory graph database. Efficient representations for graph queries should be also investigated. The evaluation includes comparisons with existing Graph Database and the query capability comparing with SQL. You could start the project by our existing work in this area.

[1] Microsoft Research, “Trinity project: Distributed graph database,” https://research.microsoft.com/en-us/projects/trinity/

[2] Neo Technology, “Java graph database,” https://neo4j.org/

11. Approximate Algorithms Determining Local Clustering Coefficients Anonymously

Originator/Supervisor: Eiko Yoneki (with Amitabha Roy in Google)

Keywords: Sampling, Approximation, Privacy, Cluster Coefficient

Anonymous social networks are a new phenomenon in an increasingly privacy conscious world. A natural question to ask in this setting is whether we can continue to apply known principles of network science in such settings where neighbourhood information is concealed both between nodes and external observers. This project is to work on approximate algorithms that determines clustering coefficient in such settings. Clustering coefficients provide a way to relatively order nodes by importance in a network, determine densely connected neighbourhoods and distinguishing social graphs from web graphs. Algorithms to measure clustering coefficients have hitherto required global knowledge of graph links. This requires individual nodes in the graph to give up the identity of their neighbours. This project investigates an algorithm for estimating the clustering coefficient of a vertex by exchanging only anonymised set summaries of neighbours, from which it is difficult to reverse engineer individual links. The bulk of the project will consist of working on and improving sampling techniques to arrive at accurate local clustering coefficients without exchanging explicit neighbour lists in social networks .

[1] P. Flajolet, Eric Fusy, O. Gandouet, and et al. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In Proceedings of the International Conference on Analysis of Algorithms, 2007.

Contact Email

Please email to eiko.yoneki@cl.cam.ac.uk for any question.