Caltech Library System

About | Browse | Search | Caltech Student Instructions

Type of Document	Dissertation
Author	Sill, Joseph
Author's Email Address	joe_sill AT yahoo.com
URN	etd-09222005-110351
Persistent URL	http://resolver.caltech.edu/CaltechETD:etd-09222005-110351
Title	Monotonicity and connectedness in learning systems
Degree	PhD
Option	Computation and Neural Systems
Advisory Committee	Advisor Name Title Yaser S. Abu-Mostafa Committee Chair Demetri Psaltis Committee Member Jehoshua Bruck Committee Member Robert McEliece Committee Member
Keywords	none
Date of Defense	1998-05-21
Availability	unrestricted
Abstract This thesis studies two properties- monotonicity and connectedness- in the context of machine learning. The first part of the thesis examines the role of monotonicity constraints in machine learning from both practical and theoretical perspectives. Two techniques for enforcing monotonicity in machine learning models are proposed. The first method adds to the objective function a penalty term measuring the degree to which the model violates monotonicity. The penalty term can be interpreted as a Bayesian prior favoring functions which obey monotonicity. This method has the potential to enforce monotonicity only approximately, making it appropriate for situations where strict monotonicity may not hold. The second approach consists of a model which is monotonic by virtue of functional form. This model is shown to have universal approximation capabilities with respect to the class M of monotonic functions. A variety of theoretical results are also presented regarding M. The generalization behavior of this class is shown to depend heavily on the probability distribution over the input space. Although the VC dimension of M is [infinity], the VC entropy (i.e., the expected number of dichotomies) is modest for many distributions, allowing us to obtain bounds on the generalization error. Monte Carlo techniques for estimating the capacity and VC entropy of M are presented. The second part of the thesis considers broader issues in learning theory. Generalization error bounds based on the VC dimension describe a function class by counting the number of dichotomies it induces. In this thesis, a more detailed characterization is presented which takes into account the diversity of a set of dichotomies in addition to its cardinality. Many function classes in common usage are shown to possess a property called connectedness. Models with this property induce dichotomy sets which are highly clustered and have little diversity. We derive an improvement to the VC bound which applies to function classes with the connectedness property.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    Sill_j_1998.pdf 3.28 Mb 00:15:09 00:07:47 00:06:49 00:03:24 00:00:17