Learning based programming

Rizzolo, Nicholas

Permalink

https://hdl.handle.net/2142/29738 Copy

Description

Title

Learning based programming

Author(s)

Rizzolo, Nicholas

Issue Date

2012-02-06T20:13:51Z

Director of Research (if dissertation) or Advisor (if thesis)

Roth, Dan

Committee Member(s)

• DeJong, Gerald F.
• Roşu, Grigore
• Pfeffer, Avrom

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2011-12

Permalink

http://hdl.handle.net/2142/29738

Copyright and License Information

Copyright 2011 by Nicholas Rizzolo. All rights reserved.

Owning Collections