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

Receive updates for this collection

Multidimensional benchmarking

Author: 
Date created: 
2016-03-14
Abstract: 

Benchmarking is a process of comparison between performance characteristics of separate, often competing organizations intended to enable each participant to improve its own performance in the marketplace (Kay, 2007). Benchmarking sets organizations’ performance standards based on what “others” are achieving. Most widely adopted approaches are quantitative and reveal numerical performance gaps where organizations lag behind benchmarks; however, quantitative benchmarking on its own rarely yields actionable insights. It is important for organizations to understand key drivers for performance gaps such that they can develop programs for improvement around them. In this thesis, we develop a multidimensional analysis approach to benchmarking to characterise the properties of key drivers as a step towards “qualitative” benchmarking. Specifically, our approach systematically identifies significant benchmarks, compares organizations in statistical manners, and reveals the most manifesting aspects of uniqueness of an organization of interest. We also evaluate our algorithmic development using systematic empirical studies and show that our methods are effective and efficient.

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

Training Data Annotation for Segmentation Classification in Simultaneous Translation

Date created: 
2016-05-09
Abstract: 

Segmentation of the incoming speech stream and translating segments incrementally is a commonly used technique that improves latency in spoken language translation. Previous work of Oda et al. 2014 [1] has explored creating training data for segmentation by finding segments that maximize translation quality with a user-defined bound on segment length.In this work, we provide a new algorithm that uses Pareto-optimality to find good segment boundaries that can balance the trade-off between latency versus translation quality. We compare against the state-of-the-art greedy algorithm from Oda et al. 2014. Our experimental results show that we can improve latency by up to 12% without harming theBleuscore for the same average segment length. Another benefit is that for any segment size,Pareto-optimal segments maximize both latency and translation quality.

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

Finding Tiny People: Long-range outdoor sensing for establishing joint attention in human-robot interaction

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

In this thesis, we present two novel methods for a robot to determine whether a distant human wants to interact. The first method finds periodic signals in camera streams and clusters them into potential human waving gestures. We demonstrated this on a ground robot by waving at the robot from long distances of up to 45 meters to attract its attention. The robot then approached to close range to confirm the gesture with other, more precise but distance-limited methods, such as human detection. The second contribution is a robot behaviour for establishing joint attention with a human by exploiting trajectory signals. If a human is detected on an intercept course with the robot, the robot can vary its trajectory to probe the intent of the human. If the human corrects its trajectory to maintain the intercept, this can be considered a strong signal that the human wants to interact with the robot. We show that under modest assumptions, an arbitrary level of confidence in human intent can be achieved by iterating the behaviour. In addition to contributions to human-robot interaction, we present a novel outdoor robot dataset captured at Simon Fraser University campus. The dataset consists of hundreds of gigabytes of trail data recorded using a ground-based robot equipped with six cameras and two laser scanners.

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

Multiple instance learning for visual recognition: Learning latent probabilistic models

Peer reviewed: 
No, item is not peer reviewed.
Date created: 
2015-09-08
Abstract: 

Many visual recognition tasks can be represented as multiple instance problems. Two examples are image categorization and video classification, where the instances are the image segments and video frames, respectively. In this regard, detecting and counting the instances of interest can help to improve recognition in a variety of applications. For example, classifying the collective activity of a group of people can be directed by counting the actions of individual people. Further, encoding the cardinality-based relationships can reduce sensitivity to clutter or ambiguity, in the form of individuals not involved in a group activity or irrelevant segments/frames in an image/video. Multiple instance learning (MIL) aims to use these counting relations in order to recognize patterns from weakly supervised data. Contrary to standard supervised learning, where each training instance is labeled, in the MIL paradigm a bag of instances share a label, and the instance labels are hidden. This weak supervision significantly reduces the cost of full annotation in many recognition tasks. However, it makes learning and recognition more challenging. In a general MIL problem, three major issues usually emerge: how to infer instance labels without full supervision; how the cardinality relations between instance labels contribute to predict the bag label; how the the bag as a whole entity which integrates the instances is labeled. In this thesis, we try to address all these challenges. To this end, first we propose a boosting framework for MIL, which can model a wide range of soft and linguistic cardinality relations. Next, a probabilistic graphical model is proposed to capture the interactions and interrelations between instances, instance labels, and the whole bag. This is a general and flexible model, which can encode any cardinality-based relations. For training this model, we introduce novel algorithms based on latent max-margin classification, kernel learning, and gradient boosting. Thus, very rich and high-capacity models are obtained for bag classification. We evaluate our proposed methods in various applications such as image classification, human group activity recognition, human action recognition, video recognition, unconstrained video event detection, and video summarization.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Greg Mori
Anoop Sarkar
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Dissertation) Ph.D.

Learning action primitives for multi-level video event understanding

Author: 
Date created: 
2015-12-21
Abstract: 

Human action categories exhibit significant intra-class variation. Changes in viewpoint, human appearance, and the temporal evolution of an action confound recognition algorithms. In order to address this, we present an approach to discover action primitives, sub-categoriesof action classes, that allow us to model this intra-class variation. We learn action primitives and their interrelations in a multi-level spatio-temporal model for action recognition. Action primitives are discovered via a data-driven clustering approach that focuses on repeatable,discriminative sub-categories. Higher-level interactions between action primitives and the actions of a set of people present in a scene are learned. Empirical results demonstrate that these action primitives can be effectively localized, and using them to model action classesimproves action recognition performance on challenging datasets.

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

Object detection in surveillance video from dense trajectories

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

Detecting objects such as humans or vehicles is a central problem in surveillance video. Myriad standard approaches exist for this problem. At their core, approaches consider either the appearance of people, patterns of their motion, or differences from the background. In this paper we build on dense trajectories, a state-of-the-art approach for describing spatio-temporal patterns in video sequences. We demonstrate an application of dense trajectories to object detection in surveillance video, showing that they can be used to both regress estimates of object locations and accurately classify objects.

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

Latent structure discriminative learning for natural language processing

Author: 
Date created: 
2015-10-27
Abstract: 

Natural language is rich with layers of implicit structure, and previous research has shown that we can take advantage of this structure to make more accurate models. Most attempts to utilize forms of implicit natural language structure for natural language processing tasks have assumed a pre-defined structural analysis before training the task-specific model. However, rather than fixing the latent structure, we may wish to discover the latent structure that is most useful via feedback from an extrinsic task. The focus of this thesis is on jointly learning the best latent analysis along with the model for the NLP task we are interested in. In this work, we present a generalized learning framework for discriminative training overjointly learned latent structures, and apply this to several NLP tasks. We develop a high accuracy discriminative language model over shallow parse structures. We demonstrate an efficient algorithm for learning this grammaticality classifier by combining the input of multiple representations of the latent structures. Next, we set forth a framework for latent structure learning for statistical machine translation (SMT), in which the latent segmentation and alignment of the parallel training data inform the translation model. This model jointly optimizes segmentation and alignment for the translation task, novelly learning over latent representations of the input. We also propose a discriminative bilingual topic model over hierarchically structured latent topics, which allows for weighted contributions from more informative inputs and can be optimized for SMT. We apply this model to morphological disambiguation and domain adaptation for SMT. Finally, we give an investigation of large-scale distributed training for structured discriminative models and propose recommendations for distributed computational topologies.

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

Crowdsourced multimedia content: Resource allocation and data transmission

Author: 
Date created: 
2015-12-15
Abstract: 

Recent years have witnessed the rapid growth of crowdsourced multimedia services, such as text-based Twitter, image-based Flickr, and video streaming-based Twitch and YouTube live events. Empowered by today's rich tools for multimedia generation/distribution, as well as the growing prevalence of high-speed network and smart devices, most of the multimedia contents are crowdsourced from amateur users, rather than from commercial and professional content providers, and can be easily accessed by other users in a timely manner. Since cloud computing offers reliable, elastic and cost-effective resource allocation, it has been adopted by many multimedia service providers as the underlying infrastructure. In this thesis, we formulate the cloud resource allocation in crowdsourced multimedia services as a standard network utility maximization (NUM) problem with coupled constraints, in which real-time user interaction is a fundamental issue, and develop distributed solutions based on dual composition. We further propose practical improvements for the content generation and big data processing of crowdsourced multimedia services in a cloud environment. Crowdsourced multimedia services also rely on convenient mobile Internet access, since mobile users occupy a large portion of both content generators and content consumers. The rich multimedia content, especially images and videos, put significant pressure on the infrastructure of state-of-the-art cellular networks. Device-to-device (D2D) communicationthat smartly explores local wireless resources has been suggested as a complement of great potential to support proximity-based applications. In this thesis, we jointly consider resource allocation and power control with heterogeneous quality of service (QoS) requirements from diverse multimedia applications.

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

Colouring on hereditary graph classes

Author: 
Date created: 
2015-12-15
Abstract: 

The graph colouring problems ask if one can assign a colour from a palette of colour to every vertex of a graph so that any two adjacent vertices receive different colours. We call the resulting problem k-Colourability if the palette is of fixed size k, and Chromatic Number if the goal is to minimize the size of the palette. One of the earliest NP-completeness results states that 3-Colourability is NP-complete. Thereafter, numerous studies have been devoted to the graph colouring problems on special graph classes. For a fixed set of graphs H we denote F orb(H) by the set of graphs that exclude any graph H ∈ H as an induced subgraph. In this thesis, we explore the computational complexity of graph colouring problems on F orb(H) for different sets of H.In the first part of this thesis, we study k-Colourability on classes F orb(H) when H contains at most two graphs. We show that 4-Colourability and 5-Colourability are NPcomplete on F orb({P7}) and F orb({P6}), respectively, where Pt denotes a path of order t. These results leave open, for k ≥ 4, only the complexity of k-Colourability on F orb({Pt}) for k = 4 and t = 6. Secondly, we refine our NP-completeness results on k-Colourability to classes F orb({Cs, Pt}), where Cs denotes a cycle of length s. We prove new NP-completeness results for different combinations of values of k, s and t. Furthermore, we consider two common variants of the k-colouring problem, namely the list k-colouring problem and the pre-colouring extension of k-colouring problem. We show that in most cases these problems are also NP-complete on the class F orb({Cs, Pt}). Thirdly, we prove that the set of forbidden induced subgraph that characterizes the class of k-colourable (C4, P6)-free graphs is of finite size. For k ∈ {3, 4}, we obtain an explicit list of forbidden induced subgraphs and the first polynomial certifying algorithms for k-Colourability on F orb({C4, P6}).We also discuss one particular class F orb(H) when the size of H is infinite. We consider the intersection class of F orb({C4, C6, . . .}) and F orb(caps), where a cap is a graph obtained from an induced cycle by adding an additional vertex and making it adjacent to two adjacent vertices on the cycle. Our main result is a polynomial time 3/2-approximation algorithm for Chromatic Number on this class.

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

Constraint programming solutions to LogicQL program verification and system resilience problems

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

Constraint Programming (CP) is the study of solving problems by stating constraints on the solution to be found. Many computer science problems can be viewed as a special case of the constraint problem. In this thesis, we focus on using CP solvers for solving two distinct problems. First, we develop and implement a framework for an automatic generation of models that satisfy a program in LogicQL, a high-level database query language. We show that our system gives immediate feedback to the user and can be used for incremental development of LogicQL programs. Second, we consider a system resilience problem that is important in many application domains. We present the design and implementation of SR-solver, a novel integrated tool for evaluating system resilience. The SR-solver supports a graphical representation of the system, thus making the evaluation of system resilience accessible to general users.

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