CS Theses & Dissertations 2013

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

Acquisition of transparent refractive media
Atcheson, Bradley
DOI : 10.14288/1.0052220
URI : http://hdl.handle.net/2429/43621
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05

Transparent refractive media are invisible but for the distortions they impart upon a background scene. Computerised acquisition of such media can therefore often not be performed via traditional scanning methods. By capturing refracted backgrounds rather than reflections off the target media itself, we develop techniques for reconstructing the intervening refractive index distribution for both static and time-varying media. The approach is based on tracking optical distortions and then performing tomographic reconstruction. For multi-view tomography we first require a suitably calibrated camera array. To this end we show how to temporally synchronise and geometrically calibrate an array of consumer-grade video cameras that can scale to larger sizes, and at lower cost, than a comparative array of machine vision cameras. For media of low dynamic refractive index range, such as mixing gases, we show how to acquire data and formulate a linear least-squares problem to solve for the refractive index distribution. Unlike traditional methods of fluid flow measurement, ours is non-invasive and fully volumetric. For materials of higher dynamic refractive index range, we develop an alternative acquisition method based on temporally-encoded structured light patterns. Media causing significant distortion of light rays give rise to a large, nonlinear inverse problem. Results indicate that grid resolution relative to the minimum refractive feature size is a key factor limiting the accuracy of reconstructions.

Capturing fast motion with consumer grade unsynchronized rolling-shutter cameras
Chen, Xing
DOI : 10.14288/1.0052112
URI : http://hdl.handle.net/2429/43538
Degree : Master of Science - MSc
Graduation Date : 2013-05

A multi-agent security system for Android platform
Cheng, Zhiyong
DOI : 10.14288/1.0052211
URI : http://hdl.handle.net/2429/43775
Degree : Master of Science - MSc
Graduation Date : 2013-05

Recklessly approximate sparse coding
Denil, Misha
DOI : 10.14288/1.0052215
URI : http://hdl.handle.net/2429/43662
Degree : Master of Science - MSc
Graduation Date : 2013-05

Managing on-line submission and marking of programming assignments
Dindar, Nuray
DOI : 10.14288/1.0052207
URI : http://hdl.handle.net/2429/43763
Degree : Master of Science - MSc
Graduation Date : 2013-05

Herded Gibbs and discretized herded Gibbs sampling
Eskelinen, Mareija
DOI : 10.14288/1.0052182
URI : http://hdl.handle.net/2429/44896
Degree : Master of Science - MSc
Graduation Date : 2013-11

Control of complex biomechanical systems
Fain, Mikhail
DOI : 10.14288/1.0052179
URI : http://hdl.handle.net/2429/45401
Degree : Master of Science - MSc
Graduation Date : 2013-11

Eulerian finite volume method for musculoskeletal simulation and data-driven activation
Fan, Ye
DOI : 10.14288/1.0052197
URI : http://hdl.handle.net/2429/44645
Degree : Master of Science - MSc
Graduation Date : 2013-11

Social influence and its applications : an algorithmic and data mining study
Goyal, Amit
DOI : 10.14288/1.0052213
URI : http://hdl.handle.net/2429/43935
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05

Social influence occurs when one's actions are affected by others. If leveraged carefully, social influence can be exploited in many applications like viral marketing (or targeted advertising in general), recommender systems, social network analysis, events detection, experts finding, link prediction, ranking of feeds etc. One of the fundamental problems in this fascinating field is the problem of influence maximization, primarily motivated by the application of viral marketing. The objective is to identify a small set of users in a social network, who when convinced to adopt a product will influence others in the network leading to a large number of adoptions. The vision of our work is to take the algorithmic and data mining aspects of viral marketing out of the lab. We organize ours goals and contributions into four categories: (i) With the ever-increasing scale of online social networks, it is extremely important to develop efficient algorithms for influence maximization. We propose two algorithms -- CELF++ and SIMPATH that significantly improve the scalability. (ii) We remark that previous studies often make unrealistic assumptions and rely on simulations, instead of validating models against real world data. For instance, they assume an arbitrary assignment of influence probabilities in their studies, which focused more on algorithms than on validity with respect to real data. We attack the problem of learning influence probabilities. In another work, we propose a novel data driven approach to influence models and show that it predicts influence diffusion with much better accuracy. (iii) Next, we propose alternative problem formulations -- MINTSS and MINTIME and show interesting theoretical results. These problem formulations capture the problem of deploying viral campaigns on budget and time constraints. In an additional work, we take a fresh perspective on identifying community leaders using a pattern mining approach. (iv) Finally, we examine applications of social influence. We begin with the application of viral marketing. We show that product adoption is not exactly influence. Given this, we develop a product adoption model and study the problem of maximizing product adoption. Furthermore, we propose and investigate a novel problem in recommender systems, for targeted advertising -- RECMAX.

East is not west : is there validity in cross-cultural usability?
Haddad, Shathel Yacoub
DOI : 10.14288/1.0052193
URI : http://hdl.handle.net/2429/44699
Degree : Master of Science - MSc
Graduation Date : 2013-11

Decision making with inference and learning methods
Hoffman, Matthew William
DOI : 10.14288/1.0052214
URI : http://hdl.handle.net/2429/44083
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05

In this work we consider probabilistic approaches to sequential decision making. The ultimate goal is to provide methods by which decision making problems can be attacked by approaches and algorithms originally built for probabilistic inference. This allows us to directly apply a wide variety of popular, practical algorithms to these tasks. In Chapter 1 we provide an overview of the general problem of sequential decision making and a broad description of various solution methods. Much of the remaining work of this thesis then proceeds by relying upon probabilistic reinterpretations of the decision making process. This strategy of reducing learning problems to simpler inference tasks has been shown to be very fruitful in much of machine learning, and we expect similar improvements to arise in the control and reinforcement learning fields. The approaches of Chapters 2–3 build upon the framework of [Toussaint and Storkey, 2006] in reformulating the solution of Markov decision processes instead as maximum-likelihood estimation in an equivalent probabilistic model. In Chapter 2 we utilize this framework to construct an Expectation Maximization algorithm for continuous, linear-Gaussian models with mixture-of-Gaussian rewards. This approach extends popular linear-quadratic reward models to a much more general setting. We also show how to extend this probabilistic framework to continuous time processes. Chapter 3 further builds upon these methods to introduce a Bayesian approach to policy search using Markov chain Monte Carlo. In Chapter 4 we depart from the setting of direct policy search and instead consider value function estimation. In particular we utilize least-squares temporal difference learning to reduce the problem of value function estimation to a more standard regression problem. In this chapter we specifically tackle the use of regularization methods in order to encourage sparse solutions. In Chapters 5–6 we consider the task of optimization as a sequential decision problem. In the first of these chapters we introduce the bandit framework and discuss a number of variations. Then in Chapter 6 we discuss a related approach to optimization utilizing Bayesian estimates of the underlying, unknown function. We finally introduce a novel approach to choose between different underlying point selection heuristics.

Practical considerations for Dimensionality Reduction : user guidance, costly distances, and document data
Ingram, Stephen
DOI : 10.14288/1.0052184
URI : http://hdl.handle.net/2429/45175
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11

In this thesis, we explore ways to make practical extensions to Dimensionality Reduction, or DR algorithms with the goal of addressing challenging, real-world cases. The first case we consider is that of how to provide guidance to those users employing DR methods in their data analysis. We specifically target users who are not experts in the mathematical concepts behind DR algorithms. We first identify two levels of guidance: global and local. Global user guidance helps non-experts select and arrange a sequence of analysis algorithms. Local user guidance helps users select appropriate algorithm parameter choices and interpret algorithm output. We then present a software system, DimStiller, that incorporates both types of guidance, validating it on several use-cases. The second case we consider is that of using DR to analyze datasets consisting of documents. In order to modify DR algorithms to handle document datasets effectively, we first analyze the geometric structure of document datasets. Our analysis describes the ways document datasets differ from other kinds of datasets. We then leverage these geometric properties for speed and quality by incorporating ideas from text querying into DR and other algorithms for data analysis. We then present the Overview prototype, a proof-of-concept document analysis system. Overview synthesizes both the goals of designing systems for data analysts who are DR novices, and performing DR on document data. The third case we consider is that of costly distance functions, or when the method used to derive the true proximity between two data points is computationally expensive. Using standard approaches to DR in this important use-case can result in either unnecessarily protracted runtimes or long periods of user monitoring. To address the case of costly distances, we develop an algorithm framework, Glint, which efficiently manages the number of distance function calculations for the Multidimensional Scaling class of DR algorithms. We then show that Glint implementations of Multidimensional Scaling algorithms achieve substantial speed improvements or remove the need for human monitoring.

Blog comments classification using tree structured conditional random fields
Jin, Wei
DOI : 10.14288/1.0052167
URI : http://hdl.handle.net/2429/43571
Degree : Master of Science - MSc
Graduation Date : 2013-05

The pairwise heuristic : a method for treating uncertainty in planning and robot localization
Khalvati, Koosha
DOI : 10.14288/1.0052218
URI : http://hdl.handle.net/2429/43747
Degree : Master of Science - MSc
Graduation Date : 2013-05

Variational learning for latent Gaussian model of discrete data
Khan, Mohammad
DOI : 10.14288/1.0052219
URI : http://hdl.handle.net/2429/43640
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05

This thesis focuses on the variational learning of latent Gaussian models for discrete data. The learning is difficult since the discrete-data likelihood is not conjugate to the Gaussian prior. Existing methods to solve this problem are either inaccurate or slow. We consider a variational approach based on evidence lower bound optimization. We solve the following two main problems of the variational approach: the computational inefficiency associated with the maximization of the lower bound and the intractability of the lower bound. For the first problem, we establish concavity of the lower bound and design fast learning algorithms using concave optimization. For the second problem, we design tractable and accurate lower bounds, some of which have provable error guarantees. We show that these lower bounds not only make accurate variational learning possible, but can also give rise to algorithms with a wide variety of speed-accuracy trade-offs. We compare various lower bounds, both theoretically and experimentally, giving clear design guidelines for variational algorithms. Through application to real-world data, we show that the variational approach can be more accurate and faster than existing methods.

Flexible and efficient exploration of rated datasets
Kolloju, Naresh Kumar
DOI : 10.14288/1.0052206
URI : http://hdl.handle.net/2429/44028
Degree : Master of Science - MSc
Graduation Date : 2013-05

Reconstruction of bubble trajectories and velocity estimation
Krimerman, Michael
DOI : 10.14288/1.0052212
URI : http://hdl.handle.net/2429/43919
Degree : Master of Science - MSc
Graduation Date : 2013-05

Probabilistic reasoning with undefined properties in ontologically-based belief networks
Kuo, Chia-Li
DOI : 10.14288/1.0052177
URI : http://hdl.handle.net/2429/45338
Degree : Master of Science - MSc
Graduation Date : 2013-11

Data coordination
Lawrence, Michael
DOI : 10.14288/1.0052209
URI : http://hdl.handle.net/2429/44046
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05

Data coordination is the problem of updating a contingent database C as a result of changes to a database B on which it depends. For example, a general contractor’s construction cost estimate (C) needs to be updated in response to changes made by an architect to a building design (B). Although these two databases are related in a very specific way, they contain information about fundamentally different types of objects: the cost estimate is composed of items which represent work results, and the building design is composed of physical objects. Motivated by scenarios such as design-cost coordination, we propose an approach to coordinating data between autonomous, heterogeneous sources which have a base-contingent relationship. We propose the use of declarative mappings to express exact relationships between the two. Using materialized views to maintain state, we give an overall approach for coordinating sets of updates from B to C through view differencing and view update translation. We adopt ideas from data exchange and incomplete information to generate the set of all possible updates which satisfy a mapping. We propose methods for assisting a user (C’s administrator) in choosing amongst the possible updates, and experimentally evaluate these methods, as well as the overall benefit of semiautomatic data coordination, in a usability study. We then discuss practical challenges in applying our general techniques to the domain of architecture, engineering and construction, by interviewing practitioners and analyzing data from two construction projects.

Biomechanical simulation of the hand musculoskeletal system and skin
Li, Duo
DOI : 10.14288/1.0052208
URI : http://hdl.handle.net/2429/44027
Degree : Master of Science - MSc
Graduation Date : 2013-05

A parallel active-set method for solving frictional contact problems
Litven, Joshua Alexander
DOI : 10.14288/1.0052205
URI : http://hdl.handle.net/2429/43934
Degree : Master of Science - MSc
Graduation Date : 2013-05

Runtime migration of browser sessions for JavaScript web applications
Lo, Teng Kin
DOI : 10.14288/1.0052216
URI : http://hdl.handle.net/2429/43748
Degree : Master of Science - MSc
Graduation Date : 2013-05

Dynamic facial appearance capture using six primaries
Mahmud, Anika
DOI : 10.14288/1.0052144
URI : http://hdl.handle.net/2429/43560
Degree : Master of Science - MSc
Graduation Date : 2013-05

Dialogue act recognition in synchronous and asynchronous conversations
Maryam, Tavafi
DOI : 10.14288/1.0052186
URI : http://hdl.handle.net/2429/44874
Degree : Master of Science - MSc
Graduation Date : 2013-11

Visual object recognition for mobile platforms
Meger, David Paul
DOI : 10.14288/1.0052195
URI : http://hdl.handle.net/2429/44682
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11

A robot must recognize objects in its environment in order to complete numerous tasks. Significant progress has been made in modeling visual appearance for image recognition, but the performance of current state-of-the-art approaches still falls short of that required by applications. This thesis describes visual recognition methods that leverage the spatial information sources available on-board mobile robots, such as the position of the platform in the world and the range data from its sensors, in order to significantly improve performance. Our research includes: a physical robotic platform that is capable of state-of-the-art recognition performance; a re-usable data set that facilitates study of the robotic recognition problem by the scientific community; and a three dimensional object model that demonstrates improved robustness to clutter. Based on our 3D model, we describe algorithms that integrate information across viewpoints, relate objects to auxiliary 3D sensor information, plan paths to next-best-views, explicitly model object occlusions and reason about the sub-parts of objects in 3D. Our approaches have been proven experimentally on-board the Curious George robot platform, which placed first in an international object recognition challenge for mobile robots for several years. We have also collected a large set of visual experiences from a robot, annotated the true objects in this data and made it public to the research community for use in performance evaluation. A path planning system derived from our model has been shown to hasten confident recognition by allowing informative viewpoints to be observed quickly. In each case studied, our system demonstrates significant improvements in recognition rate, in particular on realistic cluttered scenes, which promises more successful task execution for robotic platforms in the future.

Feasibility of supporting pointing on large wall displays using off-the-shelf consumer-grade tracking equipment
Muradov, Orkhan
DOI : 10.14288/1.0052180
URI : http://hdl.handle.net/2429/45379
Degree : Master of Science - MSc
Graduation Date : 2013-11

Interaction with large stereoscopic displays : Fitts and multiple object tracking studies for virtual reality
Rajendran, Vasanth Kumar
DOI : 10.14288/1.0052210
URI : http://hdl.handle.net/2429/43788
Degree : Master of Science - MSc
Graduation Date : 2013-05

Summarizing software artifacts
Rastkar, Sarah
DOI : 10.14288/1.0052199
URI : http://hdl.handle.net/2429/44482
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11

To answer an information need while performing a software task, a software developer sometimes has to interact with a lot of software artifacts. This interaction may involve reading through large amounts of information and many details of artifacts to find relevant information. In this dissertation, we propose the use of automatically generated natural language summaries of software artifacts to help a software developer more efficiently interact with software artifacts while trying to answer an information need. We investigated summarization of bug reports as an example of natural language software artifacts, summarization of crosscutting code concerns as an example of structured software artifacts and multi-document summarization of project documents related to a code change as an example of multi-document summarization of software artifacts. We developed summarization techniques for all the above cases. For bug reports, we used an extractive approach based on an existing supervised summarization system for conversational data. For crosscutting code concerns, we developed an abstractive summarization approach. For multi-document summarization of project documents, we developed an extractive supervised summarization approach. To establish the effectiveness of generated summaries in assisting software developers, the summaries were extrinsically evaluated by conducting user studies. Summaries of bug reports were evaluated in the context of bug report duplicate detection tasks. Summaries of crosscutting code concerns were evaluated in the context of software code change tasks. Multi-document summaries of project documents were evaluated by investigating whether project experts find summaries to contain information describing the reason behind the corresponding code changes. The results show that reasonably accurate natural language summaries can be automatically produced for different types of software artifacts and that the generated summaries are effective in helping developers address their information needs.

Enhancing particle methods for fluid simulation in computer graphics
Schechter, Hagit
DOI : 10.14288/1.0052201
URI : http://hdl.handle.net/2429/44212
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05

We introduce novel methods for enriched Lagrangian fluid simulation in three distinct areas: smoke animation, liquid animation, and surfacing of simulation particle data. The techniques share a common goal, to efficiently enhance realism of natural-phenomena animations in particle simulation framework. Sub-Grid Turbulence adds synthesized small scale detail to large scale smoke simulation. The transport, diffusion and spectral cascade of turbulent energy are captured, whereas they are left unresolved on a typical simulation grid. Ghost-SPH handling of free-surface and solid boundary conditions in Smoothed Particle Hydrodynamics liquid simulation captures realistic cohesion for the first time and avoids the spurious numerical errors of previous approaches. Ghost particles are carefully seeded in the air and solid regions near the fluid and are assigned with extrapolated fluid quantities to reach correct boundary conditions. The Beta Mesh is a new method for reconstructing mostly temporally coherent surface meshes from particles representing the volume of a liquid. While current particle surfacing techniques address the geometrical characteristics of the surface, the focus in Beta Mesh is producing a surface which varies smoothly in time, outside of topological changes, while preserving essential geometrical properties.

Benchmarking the performance of application startup for AspectJ-aware Java virtual machines
Selby, Vincent
DOI : 10.14288/1.0052191
URI : http://hdl.handle.net/2429/44750
Degree : Master of Science - MSc
Graduation Date : 2013-11

Space and energy efficient molecular programming and space efficient text indexing methods for sequence alignment
Thachuk, Christopher Joseph
DOI : 10.14288/1.0052204
URI : http://hdl.handle.net/2429/44172
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05

Nucleic acids play vital roles in the cell by virtue of the information encoded into their nucleotide sequence and the folded structures they form. Given their propensity to alter their shape over time under changing environmental conditions, an RNA molecule will fold through a series of structures called a folding pathway. As this is a thermodynamically-driven probabilistic process, folding pathways tend to avoid high energy structures and those which do are said to have a low energy barrier. In the first part of this thesis, we study the problem of predicting low energy barrier folding pathways of a nucleic acid strand. We show various restrictions of the problem are computationally intractable, unless P=NP. We propose an exact algorithm that has exponential worst-case runtime, but uses only polynomial space and performs well in practice. Motivated by recent applications in molecular programming we also consider a number of related problems that leverage folding pathways to perform computation. We show that verifying the correctness of these systems is PSPACE-hard and in doing so show that predicting low energy barrier folding pathways of multiple interacting strands is PSPACE-complete. We explore the computational limits of this class of molecular programs which are capable, in principle, of logically reversible and thus energy efficient computation. We demonstrate that a space and energy efficient molecular program of this class can be constructed to solve any problem in SPACE ---the class of all space-bounded problems. We prove a number of limits to deterministic and also to space efficient computation of molecular programs that leverage folding pathways, and show limits for more general classes. In the second part of this thesis, we continue the study of algorithms and data structures for predicting properties of nucleic acids, but with quite different motivations pertaining to sequence rather than structure. We design a number of compressed text indexes that improve pattern matching queries in light of common biological events such as single nucleotide polymorphisms in genomes and alternative splicing in transcriptomes. Our text indexes and associated algorithms have the potential for use in alignment of sequencing data to reference sequences.

The impact of individual differences on visualization effectiveness and gaze behaviour : informing the design of user adaptive interventions
Toker, Dereck J
DOI : 10.14288/1.0052188
URI : http://hdl.handle.net/2429/44765
Degree : Master of Science - MSc
Graduation Date : 2013-11

Modeling standing, walking and rolling skills for physics-based character animation
Torres Vidal, Ernesto
DOI : 10.14288/1.0052221
URI : http://hdl.handle.net/2429/43614
Degree : Master of Science - MSc
Graduation Date : 2013-05

Auxiliary variable transformations for intractable distributions
Vanetti, Paul Justin Cesare
DOI : 10.14288/1.0052200
URI : http://hdl.handle.net/2429/44340
Degree : Master of Science - MSc
Graduation Date : 2013-05

Design-driven quadrangulation of closed 3D curves
Wang, Caoyu
DOI : 10.14288/1.0052222
URI : http://hdl.handle.net/2429/43602
Degree : Master of Science - MSc
Graduation Date : 2013-05

Flowshape : 3d concept modeling from single-view design sketches
Xu, Baoxuan
DOI : 10.14288/1.0052203
URI : http://hdl.handle.net/2429/44274
Degree : Master of Science - MSc
Graduation Date : 2013-05

Computational modeling of neuromusculoskeletal systems : from filaments to behavior
Yeo, Sang Hoon
DOI : 10.14288/1.0052217
URI : http://hdl.handle.net/2429/43756
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05

This thesis describes computational approaches to modeling and simulating aspects of the neuromusculoskeletal system. We make contributions to models at three different levels of detail. We first investigate the mechanics of shortening muscle and evaluate two forms of the traditional Hill-type muscle model, force scaling and f-max scaling, and show that the f-max scaling model is significantly better at predicting experimental results. We hypothesize a new model called the winding filament model that incorporates the role of titin during active force development. Based on the proposed hypothesis, we develop a computational model that is able to simulate residual force enhancement. The suggested model can qualitatively simulate the pattern of the force enhancement observed in previous studies. In order to model the higher levels of the system consisting of muscles and bones, we propose an optimal design framework for estimating parameters of the musculoskeletal model. The method finds a set of morphological and physiological parameters that can optimally simulate the measured force and moment at the point of action. We apply the suggested framework to modeling two rat hindlimb muscles, gracilis posticus and posterior part of biceps femoris, to see if the traditional line segment based muscle geometry model is valid for musculoskeletal system modeling. The result shows that even a complex muscle like biceps femoris can be well modeled as a line segment, but its estimated insertion point is far from that of the traditional model based on anatomy. Finally, this thesis addresses a behavioral aspect of biological movement; in particular, how a high level movement is planned and controlled, in coordination with perception. We present a fully generative model of object interception that can simulate realistic, human-like behavior of ball catching for given arbitrary ball trajectory. The model includes a simplified probabilistic model of vision, a model of eye movements combining saccades and pursuit, and corresponding head, hand and body movements. The movements are constructed from submovements. By combining these components, realistic interception behavior is simulated with minimal user intervention.




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