New Summit website coming in May 2021!

                   Check the SFU library website for updates.

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

Receive updates for this collection

SANet: Scene agnostic network for camera localization

Author: 
Date created: 
2021-03-04
Abstract: 

This thesis presents a scene agnostic neural architecture for camera localization, where model parameters and scenes are independent from each other. Despite recent advancement in learning based methods with scene coordinate regression, most approaches require training for each scene one by one, not applicable for online applications such as SLAM and robotic navigation, where a model must be built on-the-fly. Our approach learns to build a hierarchical scene representation and predicts a dense scene coordinate map of a query RGB image on-the-fly given an arbitrary scene. The 6 DoF camera pose of the query image can be estimated with the predicted scene coordinate map. Additionally, the dense prediction can be used for other online robotic and AR applications such as obstacle avoidance. We demonstrate the effectiveness and efficiency of our method on both indoor and outdoor benchmarks, achieving state-of-the-art performance among methods working for arbitrary scenes without retraining or adaptation.

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

SigTools: An exploratory visualization tool for genomic signals

Author: 
Date created: 
2021-01-20
Abstract: 

With the advancement of sequencing technologies, genomic data sets are constantly being expanded by high volumes of different data types. One recently introduced data type in genomic science is genomic signals, with genomic coordinates associated with a score or probability indicating some form of biological activity. An example of genomic signals isEpigenomicmarkswhich represent short-read coverage measurements over the genome, and are utilized to locate functional and nonfunctional elements in genome annotation studies. To understand and evaluate the results of such studies, one needs to explore and analyze the characteristics of the input data. Information visualization is an effective approach that leverages human visual ability in data analysis. Several visualization applications have been deployed for this purpose such as the UCSC genome browser, Deeptools, and Segtools. However, we believe there is room for improvement in terms of programming skills requirements and proposed visualizations. Sigtools is an R-based exploratory visualization package, designed to enable the users with limited programming experience to produce statistical plots of continuous genomic data. It consists of several statistical visualizations such as value distribution, correlation, and autocorrelation that provide insights regarding the behavior of a group of signals in larger regions – such as a chromosome or the whole genome – as well as visualizing them around a specific point or short region. To demonstrate Sigtools utilization, first, we visualize five histone modifications downloaded from Roadmap Epigenomics data portal and show that Sigtools accurately captures their characteristics. Then, we visualize five chromatin state features, probabilistic generated genome annotations, to display how sigtools can assist in the interpretation of new and unknown signals.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Kay C. Wiese
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Training with adversaries to improve faithfulness of attention in neural machine translation

Author: 
Date created: 
2020-07-17
Abstract: 

Can we trust that the attention heatmaps produced by a neural machine translation (NMT) model reflect its true internal reasoning? We isolate and examine in detail the notion of faithfulness in NMT models. We provide a measure of faithfulness for NMT based on a variety of stress tests where model parameters are perturbed and measuring faithfulness based on how often each individual output changes. We show that our proposed faithfulness measure for NMT models can be improved using a novel differentiable objective that rewards faithful behaviour by the model through probability divergence. Our experimental results on multiple language pairs show that our objective function is effective in increasing faithfulness and can lead to a useful analysis of NMT model behaviour and more trustworthy attention heatmaps. Our proposed objective improves faithfulness without reducing the translation quality and it also seems to have a useful regularization effect on the NMT model and can even improve translation quality in some cases.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Anoop Sarkar
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

An adaptive discretization method for the shortest path problem with time windows

Author: 
Date created: 
2020-12-18
Abstract: 

The Shortest Path Problem with Time Windows (SPPTW) is an important generalization of the classical shortest path problem. SPPTW has been extensively studied in practical problems, such as transportation optimization, scheduling, and routing problems. It also appears as a sub-problem in the column-generation process of the vehicle routing problem with time windows. In SPPTW, we consider a time-constrained graph, where each node is assigned with a time window, each edge is assigned with a cost and a travel time. The objective is to find the shortest path from a source node to a destination node while respecting the time window constraints. When the graph contains negative cycles, the problem becomes Elementary Shortest Path Problem with Time Windows (ESPPTW). In this thesis, we adopt the time-expanded network approach, extend it by incorporating the adaptive expansion idea and propose a new approach: Adaptive Time Window Discretization(ATWD) method. We demonstrate that the ATWD method can be easily combined with label setting algorithms and label correcting algorithms for solving SPPTW. We further extend the ATWD embedded label correcting algorithm by adding k-cycle elimination to solve ESPPTW on graphs with negative cycles. We also propose an ATWD based integer programming solution for solving ESPPTW. The objective of our study is to show that optimal solutions in a time-constrained network can be found without first constructing the entire time-expanded network.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Binay Bhattacharya
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

An experimental study of learned cardinality estimation

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

Cardinality estimation is a fundamental but long unresolved problem in query optimization. Recently, multiple papers from different research groups consistently report that learned models have the potential to replace existing cardinality estimators. In this thesis, we ask a forward-thinking question: Are we ready to deploy these learned cardinality models in production? Our study consists of three main parts. Firstly, we focus on the static environment (i.e., no data updates) and compare five new learned methods with eight traditional methods on four real-world datasets under a unified workload setting. The results show that learned models are indeed more accurate than traditional methods, but they often suffer from high training and inference costs. Secondly, we explore whether these learned models are ready for dynamic environments (i.e., frequent data updates). We find that they can- not catch up with fast data updates and return large errors for different reasons. For less frequent updates, they can perform better but there is no clear winner among themselves. Thirdly, we take a deeper look into learned models and explore when they may go wrong. Our results show that the performance of learned methods can be greatly affected by the changes in correlation, skewness, or domain size. More importantly, their behaviors are much harder to interpret and often unpredictable. Based on these findings, we identify two promising research directions (control the cost of learned models and make learned models trustworthy) and suggest a number of research opportunities. We hope that our study can guide researchers and practitioners to work together to eventually push learned cardinality estimators into real database systems.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Jiannan Wang
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

End-to-end anomaly detection in stream data

Author: 
Date created: 
2020-12-16
Abstract: 

Nowadays, huge volumes of data are generated with increasing velocity through various systems, applications, and activities. This increases the demand for stream and time series analysis to react to changing conditions in real-time for enhanced efficiency and quality of service delivery as well as upgraded safety and security in private and public sectors. Despite its very rich history, time series anomaly detection is still one of the vital topics in machine learning research and is receiving increasing attention. Identifying hidden patterns and selecting an appropriate model that fits the observed data well and also carries over to unobserved data is not a trivial task. Due to the increasing diversity of data sources and associated stochastic processes, this pivotal data analysis topic is loaded with various challenges like complex latent patterns, concept drift, and overfitting that may mislead the model and cause a high false alarm rate. Handling these challenges leads the advanced anomaly detection methods to develop sophisticated decision logic, which turns them into mysterious and inexplicable black-boxes. Contrary to this trend, end-users expect transparency and verifiability to trust a model and the outcomes it produces. Also, pointing the users to the most anomalous/malicious areas of time series and causal features could save them time, energy, and money. For the mentioned reasons, this thesis is addressing the crucial challenges in an end-to-end pipeline of stream-based anomaly detection through the three essential phases of behavior prediction, inference, and interpretation. The first step is focused on devising a time series model that leads to high average accuracy as well as small error deviation. On this basis, we propose higher-quality anomaly detection and scoring techniques that utilize the related contexts to reclassify the observations and post-pruning the unjustified events. Last but not least, we make the predictive process transparent and verifiable by providing meaningful reasoning behind its generated results based on the understandable concepts by a human. The provided insight can pinpoint the anomalous regions of time series and explain why the current status of a system has been flagged as anomalous. Stream-based anomaly detection research is a principal area of innovation to support our economy, security, and even the safety and health of societies worldwide. We believe our proposed analysis techniques can contribute to building a situational awareness platform and open new perspectives in a variety of domains like cybersecurity, and health.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Uwe Glässer
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Temporal consistency in learning action values for volleyball

Author: 
Date created: 
2021-01-26
Abstract: 

Learning actions values is a key idea in sports analytics with applications such as player ranking, tactical insight and outcome prediction. We compare two fundamentally different approaches for learning action values on a novel play-by-play volleyball dataset. In the first approach, we employ regression models that implicitly assume statistical independence of data samples. In the second approach, we use a deep reinforcement learning model, explicitly enforcing the sequential nature of the data in the learning process. We find that temporally independent regression can in certain settings outperform the reinforcement learning approach in terms of predictive accuracy, but the latter performs much better when temporal consistency is required. We also consider a mimic regression tree as a way to add interpretability to the deep reinforcement learning approach. Finally, we examine the computed action values and perform a number of example analyses to verify their validity.

Document type: 
Graduating extended essay / Research project
File(s): 
Supervisor(s): 
Oliver Schulte
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Project) M.Sc.

Deterministic learning of DNF

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

Our main result is a deterministic learning algorithm with membership queries that learns a disjunctive normal form (DNF) with a polynomial number of terms within an additive approximation error in quasi polynomial time n^{O(logn)}. With random examples under the uniform distribution, the learning algorithm of [LMN93] for DNFs runs in time n^{O(log^2(n))}. Our approach is to consider the Fourier expansion of the target DNF and approximate the heavy Fourier coefficients. Our hypothesis is the sign of the sparse polynomial that is defined with the approximated coefficients. We present two approaches for building our sparse polynomial approximating the target DNF. First, we use Gopalan and Meka’s [GMR13] PRG to deterministically approximate small degree coefficients of our target DNF. Second, we generalize the result of [DETT10] to show that a general DNF can be fooled by a small biased set to approximate coefficients of any degree. We show that under the assumption that there exists an ideal PRG with a logarithmic seed length for general DNFs, we can derandomize the Goldreich and Levin algorithm to find all small degree coefficients with large absolute values. Therefore, under the ideal PRG assumption, there exists a deterministic learning algorithm for DNFs that runs in the same time as [Man92], n^{O(loglogn)}.

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

Algorithms and Lower Bounds in Circuit Complexity

Author: 
Date created: 
2020-10-13
Abstract: 

Computational complexity theory aims to understand what problems can be efficiently solved by computation. This thesis studies computational complexity in the model of Boolean circuits. Boolean circuits provide a basic mathematical model for computation and play a central role in complexity theory, with important applications in separations of complexity classes, algorithm design, and pseudorandom constructions. In this thesis, we investigate various types of circuit models such as threshold circuits, Boolean formulas, and their extensions, focusing on obtaining complexity-theoretic lower bounds and algorithmic upper bounds for these circuits. (1) Algorithms and lower bounds for generalized threshold circuits: We extend the study of linear threshold circuits, circuits with gates computing linear threshold functions, to the more powerful model of polynomial threshold circuits where the gates can compute polynomial threshold functions. We obtain hardness and meta-algorithmic results for this circuit model, including strong average-case lower bounds, satisfiability algorithms, and derandomization algorithms for constant-depth polynomial threshold circuits with super-linear wire complexity. (2) Algorithms and lower bounds for enhanced formulas: We investigate the model of Boolean formulas whose leaf gates can compute complex functions. In particular, we study De Morgan formulas whose leaf gates are functions with "low communication complexity". Such gates can capture a broad class of functions including symmetric functions and polynomial threshold functions. We obtain new and improved results in terms of lower bounds and meta-algorithms (satisfiability, derandomization, and learning) for such enhanced formulas. (3) Circuit lower bounds for MCSP: We study circuit lower bounds for the Minimum Circuit Size Problem (MCSP), the fundamental problem of deciding whether a given function (in the form of a truth table) can be computed by small circuits. We get new and improved lower bounds for MCSP that nearly match the best-known lower bounds against several well-studied circuit models such as Boolean formulas and constant-depth circuits.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Andrei Bulatov
Valentine Kabanets
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Machine learning and network analysis for macromolecular structure determination from super-resolution microscopy

Author: 
Date created: 
2019-09-09
Abstract: 

Single molecule localization microscopy (SMLM) is one of the super-resolution imaging techniques that break the diffraction limit barrier of light microscopy. SMLM generates a 3D point cloud from photon blinks generated by fluorophores binding to target proteins. With SMLM it is now possible to image subcellular structures and study their molecular organization. Following a review of state-of-the-art SMLM cluster analysis and quantification methods, we make the following computational contributions, which are applied to studying caveolin-1 (Cav1) protein biological structures (or Cav1 domains) in prostate cancer cells. (i) We propose the first graph-based machine learning pipeline to denoise, segment, and characterize Cav1 clusters (blobs) from SMLM point clouds. Our pipeline comprises computational modules to extract per-protein and per-blob features necessary to perform the aforementioned computational tasks. Our pipeline has enabled us to identify four distinct Cav1 domains, including caveolae as well as three smaller scaffold domains. (ii) We then propose a multi-proximity threshold graphlet analysis of Cav1 blobs to identify biosignatures of Cav1 domains (i.e. classify them into categories). Our graphlet analysis has resulted in discovering the patterns of molecular interactions in the four Cav1 domains, which defines the changes in the structural organization in caveolae and scaffolds. (iii) Subsequently, we compare the performance and tradeoffs between machine learning approaches (including deep learning), on different SMLM data representations. Our observation from this comparison is that deep learning models could be used to automatically learn biological features from 3D point cloud SMLM data that distinguish caveolae and non-caveolae structures. (iv) Finally, we leverage spectral network decomposition to detect modules within the various Cav1 domains at multiple proximity thresholds. By matching the biosignature across different Cav1 domains and their constituent modules, we decipher the assembly of complex structures and describe the biogenesis and formation of the caveolae in the membrane of endogenous HeLa cells. We conclude the thesis by discussing the potential applicability of the proposed methods to studying other proteins and biological structure, stating the limitations of the proposed methods, and providing our vision for future research directions.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Ghassan Hamarneh
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.