Research Report No. UVACTS-15-13-11
May, 2003
Low-Cost Modified Adaptive Control (Phase I)
State-Based Modeling: An Analysis of Error in Order
Approximation
By:
Christopher Patrick Allred
Dr. William Scherer
A Research Project
Report for:
The Virginia
Transportation Research Council (VTRC)
Christopher Patrick Allred
University of Virginia
Dr. William T. Scherer
Department of Systems and Information Engineering
University of Virginia
Email: wts@virginia.edu
Center for Transportation Studies at the University of Virginia produces outstanding transportation professionals, innovative research results and provides important public service. The Center for Transportation Studies is committed to academic excellence, multi-disciplinary research and to developing state-of-the-art facilities. Through a partnership with the Virginia Department of Transportations (VDOT) Research Council (VTRC), CTS faculty hold joint appointments, VTRC research scientists teach specialized courses, and graduate student work is supported through a Graduate Research Assistantship Program. CTS receives substantial financial support from two federal University Transportation Center Grants: the Mid-Atlantic Universities Transportation Center (MAUTC), and through the National ITS Implementation Research Center (ITS Center). Other related research activities of the faculty include funding through FHWA, NSF, US Department of Transportation, VDOT, other governmental agencies and private companies.
Disclaimer: The contents of this report reflect the views of the authors, who are responsible for the facts and the accuracy of the information presented herein. This document is disseminated under the sponsorship of the Department of Transportation, University Transportation Centers Program, in the interest of information exchange. The U.S. Government assumes no liability for the contents or use thereof.
CTS Website Center for Transportation Studies
http://cts.virginia.edu University of Virginia
351 McCormick Road, P.O. Box 400742
Charlottesville, VA 22904-4742
434.924.6362
|
1. Report No. |
2. Government Accession No. |
3. Recipients Catalog No. |
||
|
UVACTS-15-13-11 |
|
|
||
|
4. Title and Subtitle |
5. Report Date |
|||
|
Low-Cost
Modified Adaptive Control (Phase I) State-Based
Modeling: An Analysis of Error in Order Approximation |
May, 2003 |
|||
|
|
6. Performing Organization Code |
|||
|
|
|
|||
|
7. Author(s) Christopher Patrick Allred, William T. Scherer |
8. Performing Organization Report No. |
|||
|
|
|
|||
|
9. Performing Organization and Address |
10. Work Unit No. (TRAIS) |
|||
|
Center for Transportation Studies |
|
|||
|
University of Virginia |
11. Contract or Grant No. |
|||
|
PO Box 400742 Charlottesville, VA 22904-7472 |
|
|||
|
12. Sponsoring Agencies' Name and Address |
13. Type of Report and Period Covered |
|||
|
Office of University
Programs, Research and Special Programs Administration US Department of
Transportation 400 Seventh Street, SW Washington DC 20590-0001 |
|
Final Report |
||
|
|
|
14. Sponsoring Agency Code |
||
|
|
|
|
||
|
15.
Supplementary Notes |
||||
|
|
||||
|
16. Abstract |
||||
|
When building discrete
time, discrete-state data-driven models, transition probabilities are stored
in Markov transition matrices.
Augmenting the history or order
of the associated Markov chains allows for present states to be predicated
upon states in previous time periods without contradicting the Markovian
property. However, when faced with
real data, the true order of the model is not always known. This project details the inadequacies of
the present method of evaluating order, and outlines and evaluates new
methods to approximate the model order including simulation, the
likelihood-based Bayesian Information Criterion, Schwarz Information
Criterion, and Akaike Information Criterion as well as using comparison
vectors, an ad-hoc method. In
addition, this project suggests an approach for using these techniques to
approximate order, and discusses the error associated with using that
prediction model. |
||||
|
17 Key Words |
18. Distribution Statement |
|||
|
|
No restrictions. This document is available to the
public. |
|||
Abstract
When building discrete time, discrete-state data-driven models, transition probabilities are stored in Markov transition matrices. Augmenting the history or order of the associated Markov chains allows for present states to be predicated upon states in previous time periods without contradicting the Markovian property. However, when faced with real data, the true order of the model is not always known. This project details the inadequacies of the present method of evaluating order, and outlines and evaluates new methods to approximate the model order including simulation, the likelihood-based Bayesian Information Criterion, Schwarz Information Criterion, and Akaike Information Criterion as well as using comparison vectors, an ad-hoc method. In addition, this project suggests an approach for using these techniques to approximate order, and discusses the error associated with using that prediction model.
Acknowledgements
I would like to sincerely thank my advisor, Professor William T. Scherer, for his guidance and supervision. He has been both a teacher and a friend throughout the thesis effort. Thanks go to Thomas Pomroy whose related research helped establish the foundations of the project. I am grateful to Dr. James Lark and Dr. Roman Krzysztofowicz for the insight they brought to the project, as well as taking the time to serve on my committee.
Research for this thesis was funded by Providian and the Virginia Department of Transportation Smart Travel Lab.
Table of Contents
1.2. Estimation
of Model Order
2.1. ...................................... State-Based
Modeling as a Markov Process
2.1.2. Order in State-Based
Models
2.1.3. True
Order in State-based Models
2.2. Error Factors in Data
Driven Modeling
2.3.1. Description
of Bayes Factors
2.3.3. Bayesian
Information Criterion
2.3.4. Testing
of Bayesian Information Criterion
2.3.5. Large Sample Bayes Procedure (Schwarz
Information Criterion)
2.3.6. Akaike
Information Criterion
2.4. .............................................. Convergence
Bounds of Markov Chains
3.2. Formulaic Description of the Problem
3.3. .................................................... Time
Dependence of Data Evaluation
3.4. Simulated
Model Order Estimation vs. Statistical Model Order Estimation
3.5. Ad-Hoc
Simulation Approach for the Determination of Model Order
3.6. .................................................................. Comparison
Vector Technique
3.6.1. Coding
Issues Associated with the Comparison Vector
3.7. ........................................................ Information
Criterion Techniques
4.1. ...................................................... Small-Sample
Known Order Dataset
4.1.3. Comparison
Vector Results
4.1.4. Information Criterion
Results
4.2. ......................................................... Large-Sample
Known-Order Model
4.2.3. Comparison Vector Results
4.2.4. Information Criteria
Results
4.3.3. Comparison
Vector Results
4.3.3. Information Criteria
Results
4.4.3. Comparison Vector
Technique
4.4.4. Information Criteria
Results
4.5. Virginia
Department of Transportation Data
4.5.3. Comparison Vector Results
4.5.4. Information Criteria
Results
5.1. Observations
about techniques
Appendix A: Number Generation Code
Appendix B: Simulation Technique
Code
Appendix C: Comparison Vector
Technique Code
Appendix D: Bayesian Information
Criterion Code
Appendix E: Referenced Prior Densities
List of Figures
Figure 4 - 1st and 2nd
order 2-state TPMs
Figure 5 2nd order augmented 1st
order matrix for a 2-state model
Figure 6 - Dataset Orientation
Figure 8- Formulation of rth order
transition count model
Figure 9 - Transition count matrices
generated from simulated data
Figure 10 - Comparison vector generated from
N(k)
Figure 11 - 1st, 2nd,
and 3rd order transition probability matrices
Figure 12 Comparison Vector associated with
matrix from figure 12, C(4,k)
Figure 13 - Formulaic Approach to Comparison
Vectors
Figure 14 - Experimental Data Description
Figure 15 - Convergence of probabilities
Figure 16 - Makeup of Small Sample Known
Dataset
Figure 17 - Known 3rd order matrix
Figure 18 - Transition Matrix Squared: P(3)
Figure 19 - Absolute Error of Small Sample
Model
Figure 20 - Mean Absolute Error for Small
Sample Model
Figure 21 - Absolute Prediction Error for 8
Time Periods
Figure 22 - Makeup of Large-Sample
Known-Order Model
Figure 23 - Mean Average Error for 343 accountrealization
Large-Sample Known Order Model
Figure 24 Mean Percent Error of Prediction
for Large Sample Known Order Model
Figure 25 - Data Classification for Bank of
Scotland Bank AccountRealization
Data
Figure 26 - Mean Absolute Error for Bank of
Scotland Data
Figure 27 - Prediction Mean Average
Percentage Error for Individual AccountRealizations
Figure 28 - Histogram for 12,000 accountrealization
sample
Figure 29 - Percentage in Each State as
Classified by the Max Value
Figure 30 - Data Breakdown for Calgary
Healthcare Datasets
Figure 31 - Mean Absolute Percent Error for
Calgary Healthcare Dataset
Figure 32 - Percentage Error measuring
prediction in Calgary Healthcare data
Figure 33 - Predicted Cost at Each Period vs.
Real Cost
Figure 34 - Percent Error in Approximation of
Cost Associated with 3rd and 4th Order Models
Figure 35 - Makeup of Transportation Dataset
Figure 36 - Mean Absolute Error for
Simulation of Transportation Data
Figure 37 - Prediction Error on
Transportation Data for 6 simulated time periods
Figure 38 - Mean Absolute Error for 4 orders
List of
Tables
Table 1 - Sample Transition Probability
Matrix
Table 2 2nd Order Augmented State Matrix
Table 3 - Simplified 2nd Order Augmented
Transition Probability Matrix
Table 4 - True 2-state 2nd order model
Table 5 - Expanded 2 state 3rd order
model
Table 7- Creating Matrix for Small Sample
Known Order Model
Table 8-Values for Mean Absolute Error of 473
accountrealization
sample
Table 9- Difference in Closeness of
Comparison Vectors
Table 10 - Information Criterion Results for
Small-Sample Known- Order Dataset
Table 11 - Absolute Error (Max 5000) per
simulated time epoch
Table 12 - Mean Absolute Error and Mean
Absolute Percent Error over 8 simulated periods
Table 13 - Short-term individual error
Table 14 - Generating Probability Matrix
Table 16-Large-sample Known-order model
Comparison Vector Convergence
Table 17 - Information Criterion Data for
Large-Sample Known-Order dataset
Table 19- State Classification Table for Bank
of Scotland Data; All Balances are given in Pounds.
Table 21 - Bank of Scotland Model Comparison
Vector Closeness Measures
Table 22 - Information Criterion Analysis for
Bank of Scotland Data
Table 23 - Mean Absolute Error and Mean
Absolute Percent Error for the Bank of Scotland Data
Table 24 - Histogram Breakdown for 12,000 accountrealization
Calgary Sample
Table 25 - Comparison Vector Convergence
Table for Calgary Healthcare
Table 26 - Information Criteria Data for
Calgary Healthcare
Table 27 - Mean Absolute Error and Mean
Absolute Percent Error for Calgary Healthcare Data
Table 28 - Predicted Cost at Each Period vs.
Real Cost
Table 31 - Difference in Closeness of
Comparison Vectors
Table 32 - Information Criteria Calculation
Results
Table 34 - Difference between suggested error
and real error of the model from results section
Table 35 - Sample Size Breakdown
Table 36 - Reccomendation Matrix
Table 39 - Expected Predicted Rainfall vs.
Real Rainfall
Glossary
T time scale for which T={t:0,1, T}
A accountrealization space for which A
= {a:0,1,
A}
S state space for which S = {s: 0,1, S}
K order space for which K = {k: 0,1, r, }
- worst case order of
K
for the comparison vector; the order of the largest transition probability
matrix contained in the comparison vector
P(k) kth order transition probability matrix
pij transition probability contained in P(k); given the system is in state i , the probability of transitioning into state j at the next time period
pij(n) n-step transition probability; given the system is in state i , the probability of transitioning into state j n periods in the future
πj the steady-state probability of being in state j
π
set of steady-state probabilities; π
= (π0, π1,
πS)
- a sequence of events occurring at times t, for a accountrealizations
- an indexed event occurring at time t for accountrealization
a
nij kl number of occurrences of the sequence of states ij kl in a given data range
sk vector of states for a kth order transition probability matrix
- estimated kth
order transition probability matrix
N(k) kth order transition matrix
C(k, r) the comparison vector created for an rth order model, containing the transition matrices up to an order k
μt(i) the probability of being in state i at time t
β Convergence Factor
y set of observed data
θ(k) parameters of the kth order Markov model
ρi The number of parameters in model i
Mi model i
, which occur over a set of states, T, where 
.
, where Xt
represents an event at time t, for
which the conditional probability, also known as the transition probability, 
, and 
.
. The transition probability matrix encapsulates all the
possible transitions and the conditional probabilities, allowing for calculations
of the modeled process.
, and are equivalent to the individual probabilities in the
matrix Pn.
, and 
, which can be calculated as follows for the preceding table:
