Ph.D. Final Oral Defense: Benjamin Wiedermann, November 4, 3:00 p.m., ACES 4.116

Date: Wednesday, November 4, 2009

Time:  3:00pm

Place: ACES 5.444

Supervising Professor: William Cook

Title: Integrating Programming Languages and Databases via Program Analysis

and Language Design

Abstract:
This dissertation contributes two novel techniques that integrate programming
languages and databases. Our techniques are rooted in transparent
persistence. A transparently persistent program expresses operations over all
objects in a uniform manner, regardless of whether those objects reside in memory
or in a database. Transparency increases modularity and lowers the barrier of
adoption among programmers and in industry. Unfortunately, fully transparent
programs perform so poorly that no one writes them. Our goal is to increase
the performance of these programs so that transparen t persistence can become a
viable programming paradigm.

Our first contribution --- called query extraction --- is based purely
on program analysis. Query extraction analyzes a transparent, object-oriented
program that retrieves and filters collections of objects. Some of these objects
may be persistent, in which case the program contains implicit queries of
persistent data. Our program analysis extracts these queries from the program,
translates them to explicit queries, and transforms the transparent program into
an equivalent one that contains the explicit queries. Query extraction
enables programmers to write programs in a familiar, modular style and to rely on
the compiler to transform their program into one that performs well. A few
researchers have suggested this idea in previous literature, only to dismiss
it as intractable. Our research demonstrates otherwise.

Our second contributions --- called RBI-DB+ --- is an extension of a new
programming language construct called a batch block. A batch block
provides a syntactic barrier around transparent code. It also provides
a latency guarantee: If the batch block compiles, then the code that
appears in it requires only one client-server communication trip. Researchers
previously have proposed batch blocks for databases. However, batch blocks cannot
be modularized or composed, and database batch blocks do not permit
programmers to modify persistent data. We extend database batch blocks
to address these concerns and formalize the results.

Our contributions permit programmers to write more modular programs than
contemporary approaches, without sacrificing performance. Contemporary
approaches permit programmers to express a wide range of database operations,
but they discourage modularity. We believe the most promising way to integrate
programming languages and databases is for industry to combine their
technology with the approaches contributed by this dissertation.

Ph.D. Oral Proposal, Shivaram Kalyanakrishnan

Date: Thursday, November 5

Time: 9:00am - 11:00am

Location: TAY 3.128

Research Supervisor: Peter Stone

Title: Learning Methods for Sequential Decision Making in Practice

Abstract:

Sequential decision making from experience, or reinforcement learning 

(RL), is a paradigm that is well-suited for agents seeking to optimize 

long-term gains as they carry out sensing, decision and action in an 

unknown environment. RL tasks are commonly formulated as Markov Decision 

Problems (MDPs). While learning in finite MDPs enjoys several desirable 

properties, such as convergence, sample efficiency, and the realization of 

optimal behavior, a large section of the RL tasks we encounter in the real 

world cannot be modeled and solved exactly as finite MDPs. One handicap to 

learning in realistic applications is partial observability, which negates 

the crucial assumption of a Markovian interaction between the agent and 

its environment. Further, tasks with large, possibly continuous, state 

spaces necessitate the use of function approximation. Adopting the view 

that in practice, partial observability and function approximation will 

affect learning to varying degrees, my proposed thesis seeks to 

empirically examine the capabilities and synthesize the strengths of 

learning methods that operate in their presence.

Different RL methods learn from observed state transitions in different 

ways. First, I will conduct a study to test the hypothesis that the 

strength of the reliance of a learning method on observed state 

transitions is correlated with its vulnerability to partial observability 

and function approximation. I have identified five relevant classes of 

learning methods to consider. Arranged in decreasing order of the strength 

of their reliance on observed state transitions, these classes are: 

model-based methods, model-free value function-based methods (using 

eligibility traces), actor-critic methods, policy gradient methods, and 

policy search methods. My study will compare these methods in a synthetic 

domain in which partial observability and function approximation can be 

controlled systematically. In addition, I will test aspects of the study 

on more complex and realistic RL tasks. The second part of my proposed 

thesis will focus on developing new learning methods that are sample 

efficient and capable of yielding high-valued policies, while remaining 

robust in the face of partial observability and poor representations for 

function approximation. Specific techniques I will consider are applying 

model-free value function-based and policy search methods in sequence, and 

learning complex sequential decision making tasks by decomposing them into 

components learned by separate methods.

The contributions of this proposed thesis will be to define a scope for 

learning in practical sequential decision making tasks, to characterize 

the performance of several existing classes of methods within that scope, 

and to provide new methods tailored to improve the performance of existing 

ones.

Ph.D. Final Oral Defense: Serita Nelesen

Date: November 11, 2009

Time: 1:30p

Place: ACES 5.444

Supervising Professors: Warren A. Hunt Jr. and Tandy Warnow

Title: Improved Methods for Phylogenetics

Abstract:

Phylogenetics is the study of evolutionary relationships.  It is a scientific

endeavour to discover history, and it is not easy.  Massive amounts of data

together with computationally difficult optimization problems mean that

heuristics are prevalent, and ever better techniques are sought.  New

approaches are valuable if they are more accurate, but are considered even more

so if they are faster than pre-existing methods. Improvements to existing

algorithms, whether in terms of space requirements, or faster running times,

are also worthwhile. This dissertation explores three new techniques, each of

which is valuable according to the previous definitions.

The first contribution is TASPI, a system for storing collections of

phylogenetic trees, and performing post-tree analyses. TASPI stores collections

of trees more compactly than the previous method, and this compact structure

lends itself to post-tree analyses.  This results in the ability to compute

strict and majority consensus trees faster than common alternatives.  As an

added benefit, TASPI is written in ACL2, which allows properties of the

algorithms and data structures to be formally verified.

The second contribution is an improved method to generate phylogenetic trees.

A common methodology involves two steps, first estimating a Multiple Sequence

Alignment (MSA), and then estimating a tree using that MSA.  This method

changes the way in which the MSA is estimated, and this leads to improved

accuracy of the resultant trees.  Also, in some cases, the time required is

also reduced.

The third contribution is BLuTGEN, a method by which a phylogenetic tree is

estimated from sequence data, but without ever generating an MSA for the full

dataset.  BLuTGEN is as accurate as one of the best published tree estimation

techniques (SAT\'{e}), but takes a novel approach which allows it to be applied

to much larger datasets.

Ph.D. Oral Proposal, Michael Glass

Date: Nov. 6

Time: 9-11am

Place: ACES 5.116

Research Supervisor: Bruce Porter

Title: Semantic Interpretation with Distributional Analysis

Abstract:

The transformation of an unstructured document to a formal representation is a classic problem in Artificial Intelligence.  Semantic interpretation is a key component of a system aimed at tackling this problem. We are attempting to achieve broad coverage semantic interpretation with a deep representation by interpreting sentences using the concepts and relations of a high level, richly axiomatized knowledge base. Creating semantic representations can greatly benefit question answering, particularly for questions that require inference. A semantic interpreter can also be used to annotate documents with semantics. This task is difficult due to two critical properties of natural language: ambiguity and variety.  Words and syntactic relationships are often ambiguous, leading to multiple candidate semantic representations for a single syntactic form.  And due to the variety of natural language, many different syntactic forms may lead to the same semantic representation. 

We are developing a new approach for creating a semantic interpreter. We supplement a small seed set of syntactic-to-semantic mappings authored by knowledge engineers with additional mappings induced from an unannotated corpus. We will evaluate both the method for constructing the semantic interpreter and the resulting interpreter by testing the end to end performance of the interpreter and the performance of each component.

We are leveraging advances from the Natural Language Processing (NLP) and Knowledge Representation and Reasoning (KR&R) communities to attack this problem.  Also, by adapting and combining them, we hope to advance the state of the art in these fields.  The most direct advancement will be for the KR&R community. By creating a method to extract formal representations from text we will help to alleviate the ``knowledge acquisition bottleneck''.  We also aim to advance the state of the art in key fields related to the NLP components, including word sense induction and paraphrase acquisition.     

Ph.D. Final Oral Defense: Prateek Jain

Date: November 23, 2009

Time: 9:00am

Place: ACES 2.402

Supervising Professor: Prof. Inderjit S. Dhillon

Title: Large Scale Optimization Methods for Metric and Kernel Learning

Abstract:

A large number of machine learning algorithms are critically dependent on

the underlying distance/metric/similarity function. Learning an appropriate

distance function is therefore crucial to the success of many methods.

The class of distance functions that can be learned accurately is

characterized by the amount and type of supervision available to the

particular application. In this thesis, we explore a variety of such distance

learning problems using different amounts/types of supervision and provide

efficient and scalable algorithms to learn appropriate distance functions for

each of these problems.

First, we propose a generic regularized framework for Mahalanobis metric

learning and prove that for a wide variety of regularization functions, metric

learning can be used for efficiently learning a kernel function incorporating

the available side-information. Furthermore, we provide a method for fast

nearest neighbor search using the learned distance/kernel function. We

show that a variety of existing metric learning methods are special cases

of our general framework. Hence, our framework also provides a

kernelization scheme and fast similarity search scheme for such methods.

Second, we consider a variation of our standard metric learning framework

where the side-information is incremental, streaming and cannot be stored.

For this problem, we provide an efficient online metric learning algorithm

that compares favorably to existing methods both theoretically and empirically.

Next, we consider a contrasting scenario where the amount of supervision

being provided is extremely small compared to the number of training points.

For this problem, we consider two different modeling assumptions: 1) data

lies on a low-dimensional linear subspace, 2) data lies on a low-dimensional

non-linear manifold. The first assumption, in particular, leads to the problem

of matrix rank minimization  over polyhedral sets, which is a problem of

immense interest in numerous fields including optimization, machine learning,

computer vision, and control theory. We propose a novel online learning

based optimization method for the rank minimization problem and provide

provable approximation guarantees for it. The second assumption leads to

our geometry-aware metric/kernel learning formulation, where we jointly

model the metric/kernel over the data along with the underlying manifold.

We provide an efficient alternating minimization algorithm for this problem

and demonstrate its wide applicability and effectiveness by applying it to

various machine learning tasks such as semi-supervised classification,

colored dimensionality reduction, manifold alignment etc.

Finally, we consider the task of learning distance functions under no

supervision, which we cast as a problem of learning disparate clusterings

of the data. To this end, we propose a discriminative approach and a

generative model based approach and we provide efficient algorithms

with convergence guarantees for both the approaches.

Ph.D. Final Oral Defense, Jungwoo Ha

Date: November 23, 2009

Time: 3:30pm

Place: ACES 5.336

Supervising Professor: Prof. Kathryn S. McKinley

Title: Scaling Managed Runtime Systems for Future Multicore Hardware

Abstract:

The exponential improvement in single core performance has recently come to an end, mainly because of hardware power and memory bandwidth constraints. Thus, processor manufacturers are choosing to enhance computing capabilities by placing multiple cores into a single chip, which can improve performance given parallel software.  This paradigm shift to chip multiprocessors (also called multicore) requires scalable parallel applications that executes tasks on each core, otherwise the additional cores are worthless.

Making an application scalable requires more than simply parallelizing the application code itself.  Modern applications are written in managed languages, which require automatic memory management, type and memory abstractions, dynamic analysis and just-in-time (JIT) compilation. These managed runtime systems monitor and interact frequently with the executing application.  Hence, the managed runtime itself must be scalable, and the instrumentation that monitors the application should not perturb its

scalability.

While multicore hardware forces redesign of managed runtime for scalability, it also provides opportunities when applications do not fully utilize all of the cores. Using available cores for concurrent helper threads that enhance the software, such as debugging, security, and software support, will make the runtime itself more scalable.

This dissertation presents two novel techniques that improve the scalability of managed runtimes by utilizing unused cores. The first technique is a concurrent dynamic analysis framework that provides a low-overhead buffering mechanism called Cache-friendly Asymmetric Buffering (CAB) that quickly offloads data from the application to helper threads that perform specific dynamic analyses.  Our framework minimizes application instrumentation overhead, prevents microarchitectural side-effects, and supports a variety of dynamic analysis clients, ranging from call graph and path profiling to cache simulation.  The use of this framework ensures that helper threads perturb the performance of application as little as possible.

Our second technique is concurrent trace-based just-in-time compilation, which uses of available cores for the JavaScript runtime.  The JavaScript language limits applications to a single-thread, so extra cores are worthless unless they are used by the runtime components. We redesigned a production trace-based JIT compiler to run concurrently with the interpreter, and our technique is the first to improve both responsiveness and throughput in trace-based JIT compiler.

This thesis presents the design and implementation of both techniques and

shows that they improve scalability and core utilization when running application in

managed runtimes. Industry is already adopting our approaches, which

demonstrates the urgency of the scalable runtime problem and the utility of

these techniques.

Ph.D. Oral Proposal:  Bryan Silverthorn

Date:  December 2
Time: 2 p.m.
Place: ENS 31NM

Research Supervisor:  Risto Miikkulainen

Title:  Models of Search

Abstract:

Heuristic solvers for computationally difficult problems such as satisfiability
(SAT) now succeed on some instances viewed as intractable from a worst-case
perspective. Different solvers, however, perform best on different instances,
and their success is rarely formally guaranteed.

This proposal develops probabilistic models of search to infer patterns in
solver behavior. It focuses on their value to algorithm portfolio methods,
which employ multiple solvers and attempt to allocate computational resources
to those best suited to each instance.

Two natural latent class mixture models of search are developed and tested in
the context of a portfolio architecture, showing that such models can be
constructed, fitted, and applied. Three directions for future research are
outlined: models of search that capture solver behavior more accurately, action
selection policies that exploit inferred information more fully, and
model-informed methods that evaluate new heuristics more efficiently. The
proposed dissertation will thus demonstrate a new and valuable approach to
problem solving in challenging domains.

Ph.D. Oral Proposal:  Manish Saggar

Date: Dec 2, 2009

Time: 9 am - 11 am

Venue: ACES 2.402

Research Supervisors:  Dr. Risto Mikkulainen and Dr. Clifford Saron

Title: A Computational Analysis of Meditation

Abstract

Meditation involves focusing one's attention on an object or a

phenomenon. It is believed to result from cognitive regulation of

attention and emotions. However, very few scientific studies have

attempted to understand the underlying mechanisms of meditation. In

order to make further progress, a rigorous computational modeling

approach is required.

The current proposal is to attack this problem in three ways. First,

in order to identify the cortical correlates of meditation, a battery

of advanced signal-processing methods will be employed on the

electroencephalogram (EEG) data of meditation and rest. Second, a

formal computational model will be constructed to account for this

data. Third, in order to test the efficacy of modeling, correlations

will be performed between performance measures in attention-related

tasks and model predictions.

Initial results, based on blind source separation, spectral analysis,

and coarse-scale computational modeling, are promising. In the

proposed work, they will be extended to synchrony, causality and

source localization, resulting in a more detailed model. The proposed

dissertation thus aims at constructing a framework to understand

meditation, using a tight interaction between data, signal processing,

and computational modeling.

Ph.D. Oral Defense: Jason Chaw

Defense Date: November 25th, Wednesday

Time: 10am CST

Location: ACES 6.256

Supervisor: Dr. Bruce Porter

Title: ASKME: A System to Address the Brittleness of Knowledge Based Question Answering

Abstract:

Knowledge base systems are brittle when the users of the knowledge

base are unfamiliar with its content and structure. Querying a

knowledge base requires users to state their questions in precise and

complete formal representations that relate the facts in the question

with relevant terms and relations in the underlying knowledge base.

This requirement places a heavy burden on the users to become deeply

familiar with the contents of the knowledge base and prevents novice

users to effectively use the knowledge base for problem solving.  As a

result, the utility of knowledge base systems is often restricted to

the developers themselves.

The goal of this work is to help users, who may possess little domain

expertise, to use unfamiliar knowledge bases for problem solving.  Our

thesis is that the difficulty in using unfamiliar knowledge bases can

be addressed by an approach that funnels natural questions, expressed

in English, into formal representations appropriate for automated

reasoning. The approach uses a simplified English controlled language,

a handful of well known question types, and a software component,

called the Question Mediator, to identify relevant information in the

knowledge base for problem solving.  With our approach, a knowledge

base user can use a variety of unfamiliar knowledge bases by posing

their questions with simplified English to retrieve relevant

information in the knowledge base for problem solving.

We studied the thesis in the context of a system called ASKME, whose

goal is to help users with different levels of domain expertise to use

unfamiliar knowledge bases for problem solving.  ASKME takes advantage

of features of the generic knowledge representation language, but is

independent of the specific content and organization in these

knowledge bases.  All of the domain knowledge and inference methods

are in the knowledge bases and ASKME's role is to interpret the user's

question and identify the necessary information in the underlying

knowledge base for problem solving. The major pieces of ASKME consist

of a version of restricted English, a general vocabulary, a set of

well known question types, and a software component to extend

questions with information for problem solving.

We evaluated ASKME on the task of answering AP-like exam questions in

the domains of college level Biology, Chemistry, and Physics.  The

evaluation consists of successive experiments to test if ASKME can

help novice users to use unfamiliar knowledge bases for problem

solving.  The initial experiment measures ASKME's level of performance

under ideal conditions where the knowledge base is built and used by

the same knowledge engineers. Successive experiments measure ASKME's

level of performance under increasingly realistic conditions, where

ultimately in the final experiment, we measure ASKME's level of

performance under conditions where the knowledge base is independently

built by subject matter experts and the users of the knowledge base

are a different group of novice users who are unfamiliar with the

knowledge base.

Results from the evaluation show that ASKME works well on different

knowledge bases and answers a broad range of questions that were posed

by novice users in a variety of domains.

A copy of the dissertation is available at

http://www.cs.utexas.edu/users/jchaw/dissertation.pdf