CS Theses & Dissertations 2016

For 2016 graduation dates (in alphabetical order by last name):

Style exploration and generalization for character animation
Agrawal, Shailen
DOI : 10.14288/1.0221364
URI : http://hdl.handle.net/2429/55853
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-02

Believable character animation arises from a well orchestrated performance by a digital character. Various techniques have been developed to help drive this performance in an effort to create believable character animations. However, automatic style exploration and generalization from motion data are still open problems. We tackle several different aspects of the motion generation problem which aim to advance the state of the art in the areas of style exploration and generalization. First, we describe a novel optimization framework that produces a diverse range of motions for physics-based characters for tasks such as jumps, flips, and walks. This stands in contrast to the more common use of optimization to produce a single optimal motion. The solutions can be optimized to achieve motion diversity or diversity in the proportions of the simulated characters. Exploration of style of task achievement for physics-based character animation can be performed automatically by exploiting ''null spaces'' defined by the task. Second, we perform automatic style generalization by generalizing a controller for varying degree of task achievement for a specified task. We describe an exploratory approach which explores trade-offs between competing objectives for a specified task. Pareto-optimality can be used to explore various degrees of task achievement for a given style of physics-based character animation. We describe our algorithms for computing a set of controllers that span the pareto-optimal front for jumping motions which explore the trade-off between effort and jump height. We also develop supernatural jump controllers through the optimized introduction of external forces. Third, we develop a data-driven approach to model sub-steps, such as, sliding foot pivots and foot shuffling. These sub-steps are often an integral component of the style observed in task-specific locomotion. We present a model for generating these sub-steps via a foot step planning algorithm which is then used to generate full body motion. The system is able to generalize the style observed in task-specific locomotion to novel scenarios.

Twistor : anonymous message transfer through Twitter
Alavi, Marjan Sadat
DOI : 10.14288/1.0223805
URI : http://hdl.handle.net/2429/56719
Degree : Master of Science - MSc
Graduation Date : 2016-02

Why visualization? : task abstraction for analysis and design
Brehmer, Matthew Michael
DOI : 10.14288/1.0228806
URI : http://hdl.handle.net/2429/57543
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-05

Why do people visualize data? People visualize data either to consume or produce information relevant to a domain-specific problem or interest. Visualization design and evaluation involves a mapping between domain problems or interests and appropriate visual encoding and interaction design choices. This mapping translates a domain-specific situation into abstract visualization tasks, which allows for succinct descriptions of tasks and task sequences in terms of why data is visualized, what dependencies a task might have in terms of input and output, and how the task is supported in terms of visual encoding and interaction design choices. Describing tasks in this way facilitates the comparison and cross-pollination of visualization design choices across application domains; the mapping also applies in reverse, whenever visualization researchers aim to contextualize novel visualization techniques. In this dissertation, we present multiple instances of visualization task abstraction, each integrating our proposed typology of abstract visualization tasks. We apply this typology as an analysis tool in an interview study of individuals who visualize dimensionally reduced data in different application domains, in a post-deployment field study evaluation of a visual analysis tool in the domain of investigative journalism, and in a visualization design study in the domain of energy management. In the interview study, we draw upon and demonstrate the descriptive power of our typology to classify five task sequences relating to visualizing dimensionally reduced data. This classification is intended to inform the design of new tools and techniques for visualizing this form of data. In the field study, we draw upon and demonstrate the descriptive and evaluative power of our typology to evaluate Overview, a visualization tool for investigating large text document collections. After analyzing its adoption by investigative journalists, we characterize two abstract tasks relating to document mining and present seven lessons relating to the design of visualization tools for document data. In the design study, we demonstrate the descriptive, evaluative, and generative power of our typology and identify matches and mismatches between visualization design choices and three abstract tasks relating to time series data. Finally, we reflect upon the impact of our task typology.

Towards an emotionally communicative robot : feature analysis for multimodal support of affective touch recognition
Cang, Xi Laura
DOI : 10.14288/1.0314100
URI : http://hdl.handle.net/2429/59053
Degree : Master of Science - MSc
Graduation Date : 2016-11

Enhancing interfaces for scholarly peer review
Cormier, Derek M.
DOI : 10.14288/1.0314103
URI : http://hdl.handle.net/2429/59054
Degree : Master of Science - MSc
Graduation Date : 2016-11

Gauge duality and low-rank spectral optimization
de Albuquerque Macêdo Júnior, Ives José
DOI : 10.14288/1.0221436
URI : http://hdl.handle.net/2429/55920
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-02

The emergence of compressed sensing and its impact on various applications in signal processing and machine learning has sparked an interest in generalizing its concepts and techniques to inverse problems that involve quadratic measurements. Important recent developments borrow ideas from matrix lifting techniques in combinatorial optimization and result in convex optimization problems characterized by solutions with very low rank, and by linear operators that are best treated with matrix-free approaches. Typical applications give rise to enormous optimization problems that challenge even the very best workhorse algorithms and numerical solvers for semidefinite programming. The work presented in this thesis focuses on the class of low-rank spectral optimization problems and its connection with a theoretical duality framework for gauge functions introduced in a seminal paper by Freund (1987). Through this connection, we formulate a related eigenvalue optimization problem more amenable to the design of specialized algorithms that scale well and can be used in practical applications. We begin by exploring the theory of gauge duality focusing on a slightly specialized structure often encountered in the motivating inverse problems. These developments are still made in a rather abstract form, thus allowing for its application to different problem classes. What follows is a connection of this framework with two important classes of spectral optimization problems commonly found in the literature :  trace minimization in the cone of positive semidefinite matrices and affine nuclear norm minimization. This leads us to a convex eigenvalue optimization problem with rather simple constraints, and involving a number of variables equal to the number of measurements, thus with dimension far smaller than the primal. The last part of this thesis exploits a sense of strong duality between the primal-dual pair of gauge problems to characterize their solutions and to devise a method for retrieving a primal minimizer from a dual one. This allows us to design and implement a proof of concept solver which compares favorably against solvers designed specifically for the PhaseLift formulation of the celebrated phase recovery problem and a scenario of blind image deconvolution.

Computational methods for systems biology data of cancer
Ding, Jiarui
DOI : 10.14288/1.0303119
URI : http://hdl.handle.net/2429/58164
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-09

High-throughput genome sequencing and other techniques provide a cost-effective way to study cancer biology and seek precision treatment options. In this dissertation I address three challenges in cancer systems biology research :  1) predicting somatic mutations, 2) interpreting mutation functions, and 3) stratifying patients into biologically meaningful groups. Somatic single nucleotide variants are frequent therapeutically actionable mutations in cancer, e.g., the ‘hotspot’ mutations in known cancer driver genes such as EGFR, KRAS, and BRAF. However, only a small proportion of cancer patients harbour these known driver mutations. Therefore, there is a great need to systematically profile a cancer genome to identify all the somatic single nucleotide variants. I develop methods to discover these somatic mutations from cancer genomic sequencing data, taking into account the noise in high-throughput sequencing data and valuable validated genuine somatic mutations and non-somatic mutations. Of the somatic alterations acquired for each cancer patient, only a few mutations ‘drive’ the initialization and progression of cancer. To better understand the evolution of cancer, as well as to apply precision treatments, we need to assess the functions of these mutations to pinpoint the driver mutations. I address this challenge by predicting the mutations correlated with gene expression dysregulation. The method is based on hierarchical Bayes modelling of the influence of mutations on gene expression, and can predict the mutations that impact gene expression in individual patients. Although probably no two cancer genomes share exactly the same set of somatic mutations because of the stochastic nature of acquired mutations across the three billion base pairs, some cancer patients share common driver mutations or disrupted pathways. These patients may have similar prognoses and potentially benefit from the same kind of treatment options. I develop an efficient clustering algorithm to cluster high-throughput and high-dimensional bio- logical datasets, with the potential to put cancer patients into biologically meaningful groups for treatment selection.

Simulating water for computer graphics : particle-in-cell, explicit surfaces, and discontinuous Galerkin
Edwards, Essex
DOI : 10.14288/1.0223154
URI : http://hdl.handle.net/2429/56270
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-02

We propose several advances in the simulation of fluids for computer graphics. We concentrate on particle-in-cell methods and related sub-problems. We develop high-order accurate extensions to particle-in-cell methods demonstrated on a variety of equations, including constrained dynamics with implicit-explicit time integration. We track the liquid-air interface with an explicit mesh, which we show how to do in a provably exact fashion. To address the mismatched simulation and surface resolution, we solve the partial differential equations in each time step with with a p-adaptive discontinuous Galerkin discretization. This allows us to use a coarse regular grid for the entire simulation. For solving the resulting linear system, we propose a novel mostly-algebraic domain decomposition preconditioner that automatically creates a coarse discontinuous Galerkin approximation of the problem.

Precisely quantifying software information flow
Enescu, Mihai Adrian
DOI : 10.14288/1.0228571
URI : http://hdl.handle.net/2429/57379
Degree : Master of Science - MSc
Graduation Date : 2016-05

Refining semantics for multi-stage programming
Ge, Rui
DOI : 10.14288/1.0319338
URI : http://hdl.handle.net/2429/59552
Degree : Master of Science - MSc
Graduation Date : 2016-11

Using unlabeled 3D motion examples for human activity understanding
Gupta, Ankur
DOI : 10.14288/1.0305862
URI : http://hdl.handle.net/2429/58437
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-09

We demonstrate how a large collection of unlabeled motion examples can help us in understanding human activities in a video. Recognizing human activity in monocular videos is a central problem in computer vision with wide-ranging applications in robotics, sports analysis, and healthcare. Obtaining annotated data to learn from videos in a supervised manner is tedious, time-consuming, and not scalable to a large number of human actions. To address these issues, we propose an unsupervised, data-driven approach that only relies on 3d motion examples in the form of human motion capture sequences. The first part of the thesis deals with adding view-invariance to the standard action recognition task, i.e., identifying the class of activity given a short video sequence. We learn a view-invariant representation of human motion from 3d examples by generating synthetic features. We demonstrate the effectiveness of our method on a standard dataset with results competitive to the state of the art. Next, we focus on the problem of 3d pose estimation in realistic videos. We present a non-parametric approach that does not rely on a motion model built for a specific action. Thus, our method can deal with video sequences featuring multiple actions. We test our 3d pose estimation pipeline on a challenging professional basketball sequence.

Designing for authoring and sharing of advanced personalization
Haraty, Mona
DOI : 10.14288/1.0319244
URI : http://hdl.handle.net/2429/59508
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-11

Interactive technologies have become prevalent in all aspects of life including managing our tasks, looking for information, and connecting with others. We often adapt our behaviors, consciously or unconsciously, to accommodate the technology. The unique nature of our needs and preferences, and how they change over time are better supported with technologies that are designed to be personalizable. Lack of personalization facilities limits our range of behaviors. In this dissertation, we focus on understanding and supporting differences in individuals’ behaviors through forms of personalization that are beyond choosing among a set of predefined options, by allowing users to author new functionalities. We refer to such personalizations as “advanced personalizations.” Authoring advanced personalizations, when supported, is often time-consuming and requires programming skills. Consequently, either because of lack of ability or time, many users take advantage of personalizations created and shared by others. The overarching goal of this dissertation is to design for authoring and sharing of advanced personalizations. We explore this goal in the domain of personal task management (PTM), where rich individual differences deeply influence user behavior and tool use. First, to gain insights into individual differences in PTM as well as changes in PTM behaviors over time, we conducted a series of studies :  a focus group and contextual interviews in an academic setting, a large survey questionnaire with a broader population, and follow-up interviews with some of the survey respondents. These studies provide insights into different types of advanced perosnalizations that a PTM tool needs to support. Next, we designed a personalizable PTM tool with two key components for authoring advanced personalizations, building on ideas from end user programming approaches, and following theoretical guidelines on designing personalizable tools such as meta-design guidelines. A controlled user study of our design revealed opportunities and challenges in supporting advanced personalization, and our detailed design process provides a practical starting point for designing personalizable tools. Finally, through studying personalization sharing practices, we characterized the multi-faceted nature of online personalization sharing ecosystems, which include multiple components for hosting personalizations, discussing, and managing them. Our findings also highlight tradeoffs and design considerations in such ecosystems.

Deep learning for predicting human strategic behavior
Hartford, Jason Siyanda
DOI : 10.14288/1.0319323
URI : http://hdl.handle.net/2429/59559
Degree : Master of Science - MSc
Graduation Date : 2016-11

Abelian girth and gapped sheaves
Izsak, Alice
DOI : 10.14288/1.0223486
URI : http://hdl.handle.net/2429/56299
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-02

The girth of a graph is the length of the shortest cycle in a graph, and the abelian girth of a graph is the girth of the graph's universal abelian covering graph. We denote the abelian girth of a graph G as Abl(G) and show that for d-regular graphs on n vertices with d constant and n growing we have Abl(G) ≤ 6 log_{d-1} n plus a vanishing term. This can be seen as a version of the Moore bound for abelian girth. We also prove Girth(G) ≤ Abl(G)/3, which implies that any multiplicative improvement to the abelian girth Moore bound would also improve the standard Moore bound. Sheaves on graphs and two of their homological invariants, the maximum excess and the first twisted Betti number, were used in the proof of the Hanna Neumann Conjecture from algebra and may be of use in proving several related unresolved conjectures. These conjectures can be proven if certain sheaves called ρ-kernels have vanishing maximum excess. Ungapped sheaves have maximum excess equal to the first twisted Betti number, and it is easy to compute the maximum excess of a given sheaf in the case that the sheaf is not gapped. For general sheaves though, there is no known way of computing the maximum excess in polynomial time. We give several conditions that gapped sheaves must satisfy. These conditions include that a gapped sheaf must have edge dimension at least as large as the abelian girth of the underlying graph. The ρ-kernels are subsheaves of constant sheaves. We prove that gapped subsheaves of constant sheaves exist, implying that finding maximum excess of some ρ-kernels may be computationally difficult.

Modeling distal pointing on large screens : the influence of target depth
Janzen, Izabelle
DOI : 10.14288/1.0314096
URI : http://hdl.handle.net/2429/59047
Degree : Master of Science - MSc
Graduation Date : 2016-11

On social event organization
Li, Keqian
DOI : 10.14288/1.0300240
URI : http://hdl.handle.net/2429/57862
Degree : Master of Science - MSc
Graduation Date : 2016-05

Interactive animation of the eye region
Libório Cardoso, João Afonso
DOI : 10.14288/1.0314578
URI : http://hdl.handle.net/2429/59259
Degree : Master of Science - MSc
Graduation Date : 2016-11

Recommending user-generated item lists
Liu, Yidan
DOI : 10.14288/1.0300050
URI : http://hdl.handle.net/2429/57720
Degree : Master of Science - MSc
Graduation Date : 2016-05

Computational social influence : models, algorithms, and applications
Lu, Wei
DOI : 10.14288/1.0305735
URI : http://hdl.handle.net/2429/58394
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-09

Social influence is a ubiquitous phenomenon in human life. Fueled by the extreme popularity of online social networks and social media, computational social influence has emerged as a subfield of data mining whose goal is to analyze and understand social influence using computational frameworks such as theoretical modeling and algorithm design. It also entails substantial application potentials for viral marketing, recommender systems, social media analysis, etc. In this dissertation, we present our research achievements that take significant steps toward bridging the gap between elegant theories in computational social influence and the needs of two real-world applications :  viral marketing and recommender systems. In Chapter 2, we extend the classic Linear Thresholds model to incorporate price and valuation to model the diffusion process of new product adoption; we design a greedy-style algorithm that finds influential users from a social network as well as their corresponding personalized discounts to maximize the expected total profit of the advertiser. In Chapter 3, we propose a novel business model for online social network companies to sell viral marketing as a service to competing advertisers, for which we tackle two optimization problems :  maximizing total influence spread of all advertisers and allocating seeds to advertisers in a fair manner. In Chapter 4, we design a highly expressive diffusion model that can capture arbitrary relationship between two propagating entities to arbitrary degrees. We then study the influence maximization problem in a novel setting consisting of two complementary entities and design efficient approximation algorithms. Next, in Chapter 5, we apply social influence into recommender systems. We model the dynamics of user interest evolution using social influence, as well as attraction and aversion effects. As a result, making effective recommendations are substantially more challenging and we apply semi-definite programming techniques to achieve near-optimal solutions. Chapter 6 concludes the dissertation and outlines possible future research directions.

Formalizing Rust traits
Milewski, Jonatan
DOI : 10.14288/1.0220521
URI : http://hdl.handle.net/2429/55609
Degree : Master of Science - MSc
Graduation Date : 2016-02

Multiview depth-based pose estimation
Shafaei, Alireza
DOI : 10.14288/1.0223065
URI : http://hdl.handle.net/2429/56180
Degree : Master of Science - MSc
Graduation Date : 2016-02

Practical Bayesian optimization with application to tuning machine learning algorithms
Shahriari, Bobak
DOI : 10.14288/1.0314167
URI : http://hdl.handle.net/2429/59104
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-11

Bayesian optimization has recently emerged in the machine learning community as a very effective automatic alternative to the tedious task of hand-tuning algorithm hyperparameters. Although it is a relatively new aspect of machine learning, it has known roots in the Bayesian experimental design (Lindley, 1956; Chaloner and Verdinelli, 1995), the design and analysis of computer experiments (DACE; Sacks et al., 1989), Kriging (Krige, 1951), and multi-armed bandits (Gittins, 1979). In this thesis, we motivate and introduce the model-based optimization framework and provide some historical context to the technique that dates back as far as 1933 with application to clinical drug trials (Thompson, 1933). Contributions of this work include a Bayesian gap-based exploration policy, inspired by Gabillon et al. (2012); a principled information-theoretic portfolio strategy, out-performing the portfolio of Hoffman et al. (2011); and a general practical technique circumventing the need for an initial bounding box. These various works each address existing practical challenges in the way of more widespread adoption of probabilistic model-based optimization techniques. Finally, we conclude this thesis with important directions for future research, emphasizing scalability and computational feasibility of the approach as a general purpose optimizer.

Analysing the empirical time complexity of high-performance algorithms for SAT and TSP
Mu, Zongxu
DOI : 10.14288/1.0215912
URI : http://hdl.handle.net/2429/55351
Degree : Master of Science - MSc
Graduation Date : 2016-02

Device-independent on demand synchronization in the Unico file system
Schroeder, Jonatan
DOI : 10.14288/1.0307469
URI : http://hdl.handle.net/2429/58746
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-09

As people increasingly use a wide variety of devices throughout their day, it becomes important to give users consistent and efficient access to their data in all their devices, while at the same time take into consideration the resource limitations in each device. This dissertation presents a storage platform that presents users with a single view of all their data, independently of the device they are using. Each of the user’s devices has full and up-to-date information about the entire data structure and metadata, and is able to retrieve any file transparently as needed. File content, including history, is efficiently distributed among the user’s own devices according to where it is used, with no need for centralized storage and no data stored in devices that are not owned by the user. Peers communicate with each other directly to maintain a consistent state. Users also have no need to know where the data is stored, or to remember in which device the latest update to a file has been performed. The user is able to adapt the platform to devices with different storage and network characteristics. While the latency to access content is affected, and some data may not be available at all times if some devices are disconnected, applications have access to tools that allow them to adapt to data availability.

Optimizing modern code review through recommendation algorithms
Viviani, Giovanni
DOI : 10.14288/1.0307518
URI : http://hdl.handle.net/2429/58757
Degree : Master of Science - MSc
Graduation Date : 2016-09

Managing data updates and transformations : a study of the what and how
Wong, Jessica Hei-Man
DOI : 10.14288/1.0300153
URI : http://hdl.handle.net/2429/57767
Degree : Master of Science - MSc
Graduation Date : 2016-05

Modeling human behavior in strategic settings
Wright, James Robert
DOI : 10.14288/1.0308657
URI : http://hdl.handle.net/2429/58840
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-09

Increasingly, electronic interactions between individuals are mediated by specialized algorithms. One might hope to optimize the relevant algorithms for various objectives. An aspect of online platforms that complicates such optimization is that the interactions are often strategic :  many agents are involved, all with their own distinct goals and priorities, and the outcomes for each agent depend both on their own actions, and upon the actions of the other agents. My thesis is that human behavior can be predicted effectively in a wide range of strategic settings by a single model that synthesizes known deviations from economic rationality. In particular, I claim that such a model can predict human behavior better than the standard economic models. Economic mechanisms are currently designed under behavioral assumptions (i.e., full rationality) that are known to be unrealistic. A mechanism designed based on a more accurate model of behavior will be more able to achieve its goal. In the first part of the dissertation, we develop increasingly sophisticated data-driven models to predict human behavior in strategic settings. We begin by applying machine learning techniques to compare many existing models from behavioral game theory on a large body of experimental data. We then construct a new family of models called quantal cognitive hierarchy (QCH), which have even better predictive performance than the best of the existing models. We extend this model with a richer notion of nonstrategic behavior that takes into account features such as fairness, optimism, and pessimism, yielding further performance improvements. Finally, we perform some initial explorations into applying techniques from deep learning in order to automatically learn features of strategic settings that influence human behavior. A major motivation for modeling human strategic behavior is to improve the design of practical mechanisms for real-life settings. In the second part of the dissertation, we study an applied strategic setting (peer grading), beginning with an analysis of the question of how to optimally apply teaching assistant resources to incentivize students to grade each others' work accurately. We then report empirical results from using a variant of this system in a real-life undergraduate class.

A comparison of touchscreen and mouse for real-world and abstract tasks with older adults
Zhang, Kailun
DOI : 10.14288/1.0216481
URI : http://hdl.handle.net/2429/55513
Degree : Master of Science - MSc
Graduation Date : 2016-02



Find us on Twitter

a place of mind, The University of British Columbia

 

ICICS/CS Building 201-2366 Main Mall
Vancouver, B.C. V6T 1Z4 Canada
Tel: 604-822-3061 | Fax: 604-822-5485
General: help@cs.ubc.ca
Undergrad program: undergrad-info@cs.ubc.ca
Graduate program: grad-info@cs.ubc.ca

Emergency Procedures | Accessibility | Contact UBC | © Copyright The University of British Columbia