Files in this item



application/pdfRizzolo_Nicholas.pdf (1MB)
(no description provided)PDF


Title:Learning based programming
Author(s):Rizzolo, Nicholas
Director of Research:Roth, Dan
Doctoral Committee Member(s):DeJong, Gerald F.; Roşu, Grigore; Pfeffer, Avrom
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Learning Based Programming
Learning Based Java
constrained conditional model
machine learning
Abstract:Machine learning (ML) is the study of representations and algorithms used for building functions that improve their behavior with experience. Today, researchers in many domains are applying ML to solve their problems when conventional programming techniques have proven insufficient. The first such were simple, computing the setting of only a single output variable. More recently, structured learning is adding its own set of challenges, and the specifications designed for such learning based programs are not scaling well, nor are the programs they represent. This thesis introduces Learning Based Programming (LBP), the study of programming language formalisms that directly support programs that learn their representations from data. An LBP framework embodies a set of design principles that ensures learning based programs designed under its formalism are composable, prepared for an infinite feature space, and not necessarily dependent on any particular learning or inference algorithms, among other things. We submit that adherence to these principles is necessary to enable the implementation of learning based programs that scale beyond today’s implementations. To ensure independence from learning and inference algorithms, we present the Constrained Conditional Model (CCM) and demonstrate that it is general enough to subsume the majority of models described in the literature. We then present Learning Based Java (LBJ), our first attempt at implementing an LBP framework which supports an important subset of CCMs. LBJ is a discriminative modeling language that abstracts away implementation details of feature extraction, learning, and inference. It also features a First Order Logic inspired syntax for expressing constraints between independently trained classifiers. LBJ has already been used successfully in a variety of Natural Language Processing tasks. We evaluate LBJ with both a comprehensive questionnaire and case studies. A variety of participants responded to the questionnaire, including varying levels of experience in ML and LBJ. They also applied LBJ on different tasks ranging in complexity. Simpler tasks tended to lead to a positive evaluation of LBJ, while those who required more advanced ML techniques, especially structured representations, found LBJ lacking. The case studies came to a similar conclusion while uncovering situations in which LBJ’s syntactic sugar could have encoded specifications more succinctly, as well as specific pieces of syntax that attempted to patch LBJ’s limitations. The results of our evaluation show that LBJ leaves something to be desired; in particular, it cannot naturally specify an arbitrary CCM. As such, we present our second offering in the LBP line: a general purpose programming language called the Constrained Conditional Model Processing language and designed from the ground up to support CCMs. We also present a formal semantics for CCMP specified in the language of rewriting logic and consider several interesting test cases. CCMP is a robust and flexible solution for structured learning techniques at both training-time and inference-time.
Issue Date:2012-02-06
Genre:Dissertation / Thesis
Rights Information:Copyright 2011 by Nicholas Rizzolo. All rights reserved.
Date Available in IDEALS:2012-02-06
Date Deposited:2011-12

This item appears in the following Collection(s)

Item Statistics