9501926 Nobel Binary trees play an important role in the methodology of statistics and engineering. Classification trees have been applied to variety of statistical problems, ranging from mortality studies to the recognition of functional groups in gene sequences. Quantization trees have been applied to the compression of medical images and sampled speech. The problem of designing good classification and quantization trees from finite data sets is usually addressed through the use of greedy growing algorithms. While the empirical behavior of these algorithms is well understood, there has been little theory to support their use, or to examine their behavior on large data sets. The proposed research will undertake a systematic study of greedy growing algorithms. It has three broad objectives: To develop theoretical tools that will provide a means of rigorously analyzing such algorithms; To apply these tools to the analysis and comparison of existing algorithms; To use these tools, in conjunction with computer simulations, in the design of new algorithms for specific applications. A key feature of the proposed research is that it addresses classification and quantization in the same framework. Educational activities will be one of the key responsibilities of the principal investigator during the duration of the grant. The Statistics Department at the University of North Carolina at Chapel Hill has a strong tradition of graduate and undergraduate education. Maintaining the tradition entails a strong commitment to teaching, as well as interaction with students, both inside and outside of the classroom. We hope to further the tradition through the development of new courses, which will introduce students to the basic ideas behind the proposed research. Subject to departmental approval, graduate level courses in Statistical Pattern Recognition and Complexity-based Statistical Methods will be developed. A reading course will be designed to encourage advanced graduate students to undertake superviqed research in the proposed area of study. Tree-structured methods of data analysis play an important role in statistics and engineering, because they are easy to implement and lend themselves to ready interpretation. Tree-structured procedures have been applied to statistical problems ranging from the study of housing prices to the prediction of heart attacks. Related procedures have been applied by engineers to the compression of medical images and human speech. In each application, a suitable tree must be constructed from experimental data sets that are typical of the behavior under study. In practice, trees are frequently designed by greedy growing algorithms, which build a tree iteratively, from the ground up. While these algorithms are well understood from an experimental standpoint, there has been little theory to support their use, or to examine their behavior on very large data sets. The proposed research will undertake a systematic study of greedy growing algorithms. It has three broad objectives: To develop theoretical tools that will provide a means of rigorously analyzing such algorithms; To apply these tools to the analysis and comparison of existing algorithms; To use these tools, in conjunction with computer simulations, in the design of new algorithms for specific applications. A key feature of the proposed research is that it addresses statistical and engineering applications within the same framework. Educational activities will be one of the key responsibilities of the principal investigator during the duration of the grant. The Statistics Department at the University of North Carolina at Chapel Hill has a strong tradition of graduate and undergraduate education. Maintaining the tradition entails a strong commitment to teaching, as well as interaction with students, both inside and outside of the classroom. We hope to further the tradition through the development of new courses, which will introduce graduate students to the basic ideas behind the proposed research. In addition, a reading course will be designed to encourage advanced graduate students to undertake supervised research in the proposed area of study.
