HR: 1330h
AN: H12E-1024    [PDF]
TI: Probably Approximately Optimal (PAO) Algorithm for Feature Subset Selection: Theory and Application in Canal Management Problem of Diversion Predictions
AU: * Pande, S
EM: saketpande@cc.usu.edu
AF: Civil Engineering, Utah State University, 4110 Old Main Hill, Logan, UT 84322 United States
AU: Mckee, M
EM: mmckee@cc.usu.edu
AF: Civil Engineering, Utah State University, 4110 Old Main Hill, Logan, UT 84322 United States
AB: The following paper is an application of Probably Approximately Optimal (PAO) model selection to incrementally obtain optimal predictor subset to predict present day diversions into a canal. Local nature of non-parametric models is utilized to provide an efficient algorithm that searches for optimal feature (predictor) subset in n-dimensional feature space (when the cardinality of predictor set is n). The search is based on Probably Approximately Correct (PAC) learning, which ultimately yields a feature subset that is epsilon-optimal (or epsilon better than other feature subsets) with probability of error of at most delta after certain number of algorithm iterations (for some epsilon$>$0 and 0$<$delta$<$1). This PAO algorithm thus provides a feature subset, which is one of the epsilon-optimal feature subsets with probability of at least 1-delta after finite iterations. Thus epsilon-optimal feature subsets could be visualized as epsilon-equivalent best feature subsets and delta provides an upper bound on the error that we make in concluding that. The upper bound on the probability of error is distribution independent; however the algorithm must assume that the underlying joint distribution of inputs and outputs is invariant. The algorithm presented is not just limited to non-parametric models applied in management problems. It could easily be extended to any modeling environment to obtain one of the epsilon-equivalent best input sets with a probability of at least 1-delta.
DE: 1842 Irrigation
DE: 1869 Stochastic processes
DE: 1894 Instruments and techniques
SC: Hydrology [H]
MN: 2003 Fall Meeting