Files in this item
Files  Description  Format 

application/pdf 3362927.pdf (2MB)  (no description provided) 
Description
Title:  Exact Solution of Bayes and Minimax ChangeDetection Problems 
Author(s):  Isom, Joshua D. 
Doctoral Committee Chair(s):  Braatz, Richard D. 
Department / Program:  Chemical and Biomolecular Engineering 
Discipline:  Chemical Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Statistics
Engineering, General 
Abstract:  The challenge of detecting a change in the distribution of data is a sequential decision problem that is relevant to many engineering solutions, including quality control and machine and process monitoring. This dissertation develops techniques for exact solution of changedetection problems with discrete time and discrete observations. Changedetection problems are classified as Bayes or minimax based on the availability of information on the changetime distribution. A Bayes optimal solution uses prior information about the distribution of the change time to minimize the expected cost, whereas a minimax optimal solution minimizes the cost under the worstcase changetime distribution. Both types of problems are addressed. The most important result of the dissertation is the development of a polynomialtime algorithm for the solution of important classes of Markov Bayes changedetection problems. Existing techniques for epsilonexact solution of partially observable Markov decision processes have complexity exponential in the number of observation symbols. A new algorithm, called constellation induction, exploits the concavity and Lipschitz continuity of the value function, and has complexity polynomial in the number of observation symbols. It is shown that changedetection problems with a geometric changetime distribution and identically and independentlydistributed observations before and after the change are solvable in polynomial time. Also, changedetection problems on hidden Markov models with a fixed number of recurrent states are solvable in polynomial time. A detailed implementation and analysis of the constellationinduction algorithm are provided. Exact solution methods are also established for several types of minimax changedetection problems. Finitehorizon problems with arbitrary observation distributions are modeled as extensiveform games and solved using linear programs. Infinitehorizon problems with linear penalty for detection delay and identically and independentlydistributed observations can be solved in polynomial time via epsilonoptimal parameterization of a cumulativesum procedure. Finally, the properties of policies for changedetection problems are described and analyzed. Simple classes of formal languages are shown to be sufficient for epsilonexact solution of changedetection problems, and methods for finding minimally sized policy representations are described. 
Issue Date:  2009 
Type:  Text 
Description:  240 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 2009. 
URI:  http://hdl.handle.net/2142/72137 
Other Identifier(s):  (UMI)AAI3362927 
Date Available in IDEALS:  20141217 
Date Deposited:  2009 
This item appears in the following Collection(s)

Dissertations and Theses  Chemical and Biomolecular Engineering
Dissertations and Theses  Chemical and Biomolecular Engineering 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois