Computing Science - Theses, Dissertations, and other Required Graduate Degree Essays

Receive updates for this collection

On the role of possibility in action execution and knowledge in the Situation Calculus

Author: 
Date created: 
2019-01-11
Abstract: 

Formalization of knowledge is an important aspect of reasoning about change. We review how knowledge is formalized in the Situation Calculus (a logical formalism for reasoning about action and change) and discuss the problems that occur when unexecutable actions (those actions whose preconditions are not met at the time of execution) are involved. We then provide a generalized framework that addresses these problems by tracing back source of the problem to the answer provided to the Frame Problem in the Situation Calculus. We develop a more generalized form for Successor Sate Axioms based on the new account of the solution to the Frame Problem and show how this solves the problems related to involvement of unexecutable actions.

Document type: 
Thesis
File(s): 
Senior supervisor: 
James Delgrande
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

VRCast: Mobile streaming of live 360-degree videos

Author: 
Date created: 
2018-12-10
Abstract: 

Live streaming of immersive multimedia content, e.g., 360-degree videos, is getting popular due to the recent availability of commercial devices that support interacting with such content such as smart phones, tablets, and head-mounted displays. Unicast streaming of immersive content on cellular networks consumes substantial network resources and does not scale to large number of users. Multicast, on the other hand, offers a scalable solution but it introduces multiple challenges, which include handling user interactivity, ensuring smooth quality, supporting user mobility, conserving the energy of mobile receivers, and ensuring fairness among users. We propose a comprehensive solution for the problem of live streaming of 360-degree videos to mobile users, which we refer to as VRCast. VRCast is designed for cellular networks that support multicast, such as LTE. It divides the 360-degree video into tiles and then solves the complex live streaming problem in two steps to maximize the viewport quality of users and ensure a smooth quality within the same viewport while saving the energy of mobile devices and achieving fairness across users. Extensive trace driven simulation and real LTE testbed results show that VRCast outperforms the closest algorithms in the literature by wide margins across several performance metrics. For example, compared to the state-of-the-art, VRCast enhances the median frame quality by up to 22% and reduces the variation in the spatial quality by up to 53% and improves the energy saving for mobile devices by up to 250%.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Mohamed Hefeeda
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Deep video visual relation detection

Author: 
Date created: 
2018-12-19
Abstract: 

We propose a deep learning approach to the video visual relation detection problem which aims to spatiotemporally localize objects in videos and then predicts the interaction relationship between objects. A video visual relation instance is represented by a relation triplet with the trajectories of the object1 and object2. Our framework is composed of three stages. In stage one, an object tubelet detection model is employed on video RGB frames, which takes as input a sequence of frames and output object tubelets. In stage two, pairs of object tubelets are passed to a temporal relation detection model, which outputs a relation predicate between objects as relation tubelet. In stage three, detected short-term relation tubelets which have same relation triplet and efficient high volume overlap are associated into relation tube. We validate our method on VidVRD dataset and demonstrate that the performance of our method outperforms the state-of-the-art baselines.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Greg Mori
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Optimization for mobile deep learning applications with edge computing

Author: 
Date created: 
2018-12-14
Abstract: 

The emergence of deep learning has attracted the attention from a wide range of fields and brought a large number of related applications. With the rapid growth of mobile computing techniques, numerous deep learning applications are designed for the mobile end. However, since deep learning tasks are computational-intensive, the limited computation resource on the mobile device cannot execute the application effectively. Traditional approach is to push the data and the workload to the remote cloud. Meanwhile, it introduces a high data transmission delay and possibly bottlenecks the overall performance. In this thesis, we apply a new rising concept, edge computing, for mobile deep learning applications. Comparing with cloud learning, the communication delay can be significantly reduced by pushing the workload to the near-end edge. Unlike the existing edge learning frameworks only concerning inference or training, this thesis will focus on both and put forward different optimization approaches towards them. Specifically, the thesis proposes a layer-level partitioning strategy for inference tasks and an edge compression approach with the autoencoder preprocessing for training tasks, to exploit all the available resources from the devices, the edge servers, and the cloud to collaboratively improve the performance for mobile deep learning applications. To further verify the optimization performance in practice, we formulate a scheduling problem for the multi-task execution and propose an efficient heuristic scheduling algorithm. Real-world experiments and extensive simulation tests show that our edge learning framework can achieve up to 70% delay reduction.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Jiangchuan Liu
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Robot following ahead of the leader and learning human-relevant navigational cues

Author: 
Date created: 
2018-12-17
Abstract: 

As robots become more involved in our everyday lives, we may find it useful to design new methods to interact with them. In this thesis, we design two applications to facilitate human-robot interaction. The first application is an autonomous mobile robot that follows a walking user while staying ahead of them. Despite several useful applications for autonomous push-carts, this problem has received much less attention than the easier problem of following from behind. In contrast to previous work, we use multi-modal person detection and a human-motion model that considers obstacles to predict the future path of the user. We implement the system with a modular architecture of an obstacle mapper, a human tracker, a human motion model, a robot motion planner and a robot motion controller. We report on the performance of the robot in real world experiments. We believe that approaches to this largely overlooked problem could be useful in real industrial, domestic and entertainment applications in the near future. The second application is a novel system for describing the navigational cues ahead of the robot. We train a Convolutional Neural Network (CNN) architecture on 2D LiDAR data and occupancy grid maps to detect navigational objects during robot movement through an indoor environment. These navigational objects include closed-rooms (room with closed doors), open-rooms (room with open doors) and intersections. On top of this network, our system uses a tracking module that improves the detection accuracy of the system by clustering and recording each detection of the model. This tracking module also enables us to describe the robot navigational cues. We evaluate the system in both simulation and the real world. We compare the combination of 2D LiDAR data and occupancy grid maps and using each of them alone.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Richard Vaughan
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Alignment-free clustering and error correction of UMI tagged DNA molecules

Author: 
Date created: 
2018-12-07
Abstract: 

The use of circulating tumour DNA (ctDNA) in cancer oncogenomics has the potential for rapid and non-invasive monitoring of patient-specific tumour progression. However, detection of low allele frequency variations in ctDNA raises many challenges, including the handling of sequencing errors. Tagging of DNA molecules with Unique Molecular Identifiers (UMI) attempts to mitigate sequencing errors; UMI tagged molecules are PCR amplified then sequenced independently. Analyzing UMI tagged sequencing data requires clustering reads originating from the same molecule then error-correcting sequencing errors in these clusters. Sizes of the current datasets require this process to be resource-efficient. To address this problem, we introduce Calib, a computational tool that clusters and error-corrects UMI tagged sequencing data. Calib is efficient and its parameters have been optimized to different dataset setups. On simulated datasets, Calib is highly accurate. On a real dataset, Calib results in significantly reduced false positive rates in downstream variation calling.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Cedric Chauve
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

3D visual-inertial odometry and autonomous mobile robot exploration with learned map prediction

Author: 
Date created: 
2018-12-12
Abstract: 

2D and 3D scene reconstruction are important topics in the field of robotics and computer vision. Mobile robots require a model of the environment to perform navigational tasks, and model acquisition is a useful application in itself . This thesis presents a) A 3D odometry and mapping system producing metric scale map and pose estimates using a minimal sensor-suite b) An autonomous ground robot for 2D mapping of an unknown environment using learned map prediction. The first application proposes a direct visual-inertial odometry method working with a monocular camera. This system builds upon the state-of-the-art in direct vision-only odometry. It demonstrates superior system robustness and camera tracking accuracy compared to the original method. Furthermore, the system is able to produce a 3D map in metric scale, addressing the well known scale ambiguity inherent in monocular SLAM systems.The second application demonstrates an autonomous ground robot capable of exploring unknown indoor environments for reconstructing their 2D maps. This method combines the strengths of traditional information-theoretic approaches towards solving this problem and more recent deep learning techniques. Specifically, it employs a state-of-the-art generative neural network to predict unknown regions of a partially explored map, and uses the prediction to enhance the exploration in an information-theoretic manner. The system is evaluated against traditional methods in simulation using floor plans of real buildings and demonstrates advantage in terms of exploration efficiency. We retain an advantage over end-to-end learned exploration methods in that the robot's behavior is easily explicable in terms of the predicted map.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ping Tan
Richard Vaughan
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Applying self-attention neural networks for sentiment analysis classification and time-series regression tasks

Date created: 
2018-11-26
Abstract: 

Many machine learning tasks are structured as sequence modeling problems, predominantly dealing with text and data with a time dimension. It is thus very important to have a model that is good at capturing both short range and long range dependencies across sequence steps. Many approaches have been used over the past few decades, with various neural network architectures becoming the standard in recent years. The main neural network architecture types that have been applied are recurrent neural networks (RNNs) and convolutional neural neworks (CNNs). In this work, we explore a new type of neural network architecture, self-attention networks (SANs), by testing on sequence modeling tasks of sentiment analysis classification and time-series regression. First we perform a detailed comparison between simple SANs, RNNs, and CNNs on six sentiment analysis datasets, where we demonstrate SANs achieving higher classification accuracy while having other better model characteristics over RNNs such as faster training and inference times, lower number of trainable parameters, and consuming less memory during training. Next we propose a more complex self-attention based architecture called ESSAN and use it to achieve state-of-the-art (SOTA) results on the Stanford Sentiment Treebank fine-grained sentiment analysis dataset. Finally, we apply our ESSAN architectures for the regression task of multivariate time-series prediction. Our preliminary results show that ESSAN once again achieves SOTA results, beating previous SOTA RNN with attention architectures.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Fred Popowich
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Improving reliability of large-scale multimedia services

Author: 
Date created: 
2018-11-20
Abstract: 

Online multimedia communication services such as Skype and Google Hangouts, are used by millions of users every day. They have Service Level Agreements (SLAs) covering various aspects like reliability, response times, and up-times. They provide acceptable quality on average, but users occasionally suffer from reduced audio quality, dropped video streams, and failed sessions. The cost of SLA violation is low customer satisfaction, fines, and even loss of business. Service providers monitor the performance of their services, and take corrective measures when failures are encountered. Current techniques for managing failures and anomalies are reactive, do not adapt to dynamic changes, and require massive amounts of data to create, train, and test the predictors. In addition, the accuracy of these methods is highly compromised by changes in the service environment and working conditions. Furthermore, multimedia services are composed of complex software components typically implemented as web services. Efficient coordination of web services is challenging and expensive, due to their stateless nature and their constant change. We propose a new approach to creating dynamic failure predictors for multimedia services in real-time and keeping their accuracy high during run-time changes. We use synthetic transactions to generate current data about the service. The data is used in its ephemeral state to create, train, test, and maintain accurate failure predictors. Next, we propose a proactive light-weight approach for estimating the capacity of different components of the multimedia system, and using the estimates in allocating resources to multimedia sessions in {\em real time}. Last, we propose a simple and effective optimization to current web service transaction management protocols.We have implemented all the proposed methods for failure prediction, capacity estimation, and web services coordination in a large-scale, commercial, multimedia system that processes millions of sessions every day. Our empirical results show significant performance gains across several metrics, including quality of the multimedia sessions, number of failed sessions, accuracy of failure prediction, and false positive rates of the anomaly detectors.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Mohamed Hefeeda
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Expanders in power law graphs

Date created: 
2018-10-22
Abstract: 

Random power-law graphs on n vertices can be defined in different ways. One model we study describes graphs where the expected number of vertices of degree x is proportional to a power law 1/x^β, for constant β>0. In another model, the exact degree sequence follows the power-law distribution and each vertex i has degree pn/i^β, for 0

Document type: 
Thesis
File(s): 
Senior supervisor: 
Valentine Kabanets
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.