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-05
Supervisor : Dr. van de Panne

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-05
Supervisor : Dr. Aiello

A study of provenance in databases and improving the usability of provenance database systems
AlOmeir, Omar
DOI : 10.14288/1.0221370
URI : http://hdl.handle.net/2429/55895
Degree : Master of Science - MSc
Graduation Date : 2016-05
Supervisor : Dr. Pottinger

[no title]
Anwar Joyita, Nowrin
Degree : Master of Science - MSc
Graduation Date : 2016-05
Supervisor : Dr. Feeley

Recovering 3D shape from concept and pose drawings
Bessmeltsev, Mikhail Viktorovich
DOI : 10.14288/1.0308703
URI : http://hdl.handle.net/2429/58914
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-05
Supervisor : Dr. Sheffer

Modern tools to create 3D models are cumbersome and time-consuming. Sketching is a natural way to communicate ideas quickly, and human observers, given a sketch, typically imagine a unique 3D shape; thus, a tool to algorithmically interpret sketches recovering the intended 3D shape would significantly simplify 3D modeling. However, developing such tool is known to be a difficult problem in computer science due to multitude of ambiguities, inaccuracies and incompleteness in the sketches. In this thesis, we introduce three novel approaches in CAD and character modeling that successfully overcome those problems, inferring artist-intended 3D shape from sketches. First, we introduce a system to infer the artist-intended surface of a CAD object from a network of closed 3D curves. Second, we propose a new system for recovering a 3D model of a character, given a single complete drawing and a correspondingly posed 3D skeleton. Finally, we introduce a novel system to pose a 3D character using a single gesture drawing. While developing each system, we derive our key insights from perceptual and artist literature, and confirm our algorithmic choices by various evaluations and comparisons to ground truth data.

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
Supervisors : Dr. Munzner, Dr. McGrenere

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
Supervisor : Dr. MacLean

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
Supervisor : Dr. Booth

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-05
Supervisor : Dr. Freidlander

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-11
Supervisors : Dr. Shah, Dr. Condon

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.

[no title]
Dong, Yingsai
Degree : Master of Science - MSc
Graduation Date : 2016-05
Supervisor : Dr. Leyton-Brown

IfcXMLExplorer: A Visualization Tool for Exploring and Understanding IfcXML
Duttachoudhury, Nayantara
DOI : 10.14288/1.0216480
URI : http://hdl.handle.net/2429/55452
Degree : Master of Science - MSc
Graduation Date : 2016-05
Supervisor : Dr. Pottinger

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-05
Supervisor : Dr. Bridson

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
Supervisors : Dr. Hu, Dr. Aiello

Trade-offs in data representations for learner models in interactive simulations
Fratamico, Lauren
DOI : 10.14288/1.0220737
URI : http://hdl.handle.net/2429/55058
Degree : Master of Science - MSc
Graduation Date : 2016-05
Supervisor : Dr. Conati, Dr. Roll (Centre for Teaching, Learning and Technology)

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
Supervisor : Dr. Garcia

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-11
Supervisors : Dr. Woodham, Dr. Little

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
Supervisor : Dr. McGrenere

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
Supervisor : Dr. Leyton-Brown

Structure-aware computational imaging
Heide, Felix
DOI : 10.14288/1.0318066
URI : http://hdl.handle.net/2429/59343
Degree : Doctor of Philosophy - PhD
Graduation Date : 2016-11
Supervisor : Dr. Heidrich

While traditional imaging systems directly measure scene properties, computational imaging systems add computation to the measurement process, allowing such systems to extract non-trivially encoded scene features. This dissertation demonstrates that exploiting structure in this process allows to even recover information that is usually considered to be completely lost. Relying on temporally and spatially convolutional structure, we extract two novel image modalities that were essentially “invisible” before: a new temporal dimension of light propagation, and a new per-pixel radial velocity dimension, both obtained using consumer Time-of-Flight cameras. These two novel types of images represent first steps toward the inversion of light transport. Specifically, we demonstrate that Non-Line-of-Sight imaging and imaging in scattering media can be made feasible with additional temporal information. Furthermore, structure-aware imaging also represents a completely new approach to traditional color image processing. We show that classical hand-crafted image processing pipelines can be replaced by a single optimization problem exploiting image structure. This approach does not only outperform the state-of-the-art for classical image processing problems, but enables completely new color camera designs. In particular, we demonstrate camera designs with radically simplified optical systems, as well as novel sensor designs. The computation for all imaging problems from this dissertation relies on Bayesian inference using large-scale proximal optimization methods. We present a mathematical framework and a corresponding domain-specific language to automate the development of efficient, structure-aware solvers, allowing to immediately apply the insights gained in this dissertation to new imaging problems.

Finite difference schemes for elliptic partial differential equations requiring a non-uniform mesh
Huber, Sarah
DOI : 10.14288/1.0220517
URI : http://hdl.handle.net/2429/55607
Degree : Master of Science - MSc
Graduation Date : 2016-05
Supervisor : Dr. Greif

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-05
Supervisor : Dr. Freidman

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
Supervisor : Dr. Booth

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
Supervisor : Dr. Lakshmanan

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
Supervisor : Dr. Pai

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
Supervisor : Dr. Lakshmanan

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
Supervisor : Dr. Lakshmanan

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
Supervisor : Dr. Garcia

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-05
Supervisor : Dr. Hoos

Anchored Customization: Anchoring Settings to the Application Interface to Afford Customization
Ponsard, Antoine Benoit
DOI : 10.14288/1.0220520
URI : http://hdl.handle.net/2429/55601
Degree : Master of Science - MSc
Graduation Date : 2016-05
Supervisor : Dr. McGrenere

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-11
Supervisor : Dr. Feeley

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.

[no title]
Sepehry, Behrooz
Degree : Master of Science - MSc
Graduation Date : 2016-11
Supervisor : Dr. Schmidt

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-05
Supervisor : Dr. Little

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
Supervisors : Dr. de Freitas, Dr. Bouchard-Côté (Statistics)

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.

Influence maximization in bandit and adaptive settings
Vaswani, Sharan
DOI : 10.14288/1.0166665
URI : http://hdl.handle.net/2429/54688
Degree : Master of Science - MSc
Graduation Date : 2016-05
Supervisor : Dr. Lakshmanan

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-11
Supervisor : Dr. G. Murphy

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
Supervisor : Dr. Pottinger

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-11
Supervisor : Dr. Leyton-Brown

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.

[no title]
Yang, Yujie
Degree : Master of Science - MSc
Graduation Date : 2016-11
Supervisor : Dr. Little

[no title]
Yu, Jianing
Degree : Master of Science - MSc
Graduation Date : 2016-05
Supervisor : Dr. Feeley

[no title]
Zakeri Hosseinabadi, Alireza
Degree : Master of Science - MSc
Graduation Date : 2016-11
Supervisor : Dr. Kirkpatrick, Dr. Harvey

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-05
Supervisor : Dr. McGrenere

[no title]
Zhao, Yan
Degree : Master of Science - MSc
Graduation Date : 2016-11
Supervisor : Dr. Lakshmanan



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