Mathematical Sciences: Greedy Growing and its Applications

1926年，诺贝尔二叉树在统计学和工程学方法论中发挥了重要作用。分类树已经应用于各种统计问题，从死亡率研究到识别基因序列中的功能群。量化树已被应用于医学图像和语音采样的压缩。从有限数据集设计好的分类和量化树的问题通常是通过使用贪婪生长算法来解决的。虽然这些算法的经验行为被很好地理解，但很少有理论支持它们的使用，或者在大数据集上检查它们的行为。本研究将对贪心增长算法进行系统的研究。它有三个主要目标：开发理论工具，提供严格分析此类算法的手段；将这些工具应用于现有算法的分析和比较；将这些工具与计算机模拟相结合，用于特定应用程序的新算法设计。提出的研究的一个关键特征是它在同一框架下处理分类和量化。在资助期间，教育活动将是首席研究员的主要职责之一。北卡罗来纳大学教堂山分校的统计学系有着很强的研究生和本科教育传统。保持这一传统需要坚定的教学承诺，以及与学生在课堂内外的互动。我们希望通过开发新课程来延续这一传统，这些课程将向学生介绍拟议研究背后的基本思想。经院系批准，将开设研究生水平的统计模式识别和基于复杂性的统计方法课程。一门阅读课程的设计将鼓励高级研究生在建议的研究领域进行指导研究。树状结构的数据分析方法在统计学和工程学中扮演着重要的角色，因为它们易于实现并且易于解释。树形结构程序已被应用于从房价研究到心脏病发作预测等各种统计问题。相关程序已被工程师应用于医学图像和人类语言的压缩。在每个应用程序中，必须从具有所研究行为的典型实验数据集构建合适的树。在实践中，树通常是由贪婪生长算法设计的，它迭代地从头开始构建树。虽然从实验的角度来看，这些算法被很好地理解，但很少有理论支持它们的使用，或者在非常大的数据集上检查它们的行为。本研究将对贪心增长算法进行系统的研究。它有三个主要目标：开发理论工具，提供严格分析此类算法的手段；将这些工具应用于现有算法的分析和比较；将这些工具与计算机模拟相结合，用于特定应用程序的新算法设计。拟议研究的一个关键特征是它在同一框架内处理统计和工程应用。在资助期间，教育活动将是首席研究员的主要职责之一。北卡罗来纳大学教堂山分校的统计学系有着很强的研究生和本科教育传统。保持这一传统需要坚定的教学承诺，以及与学生在课堂内外的互动。我们希望通过开发新课程来延续这一传统，这些课程将向研究生介绍拟议研究背后的基本思想。此外，将设计一门阅读课程，鼓励高级研究生在建议的研究领域进行指导研究。

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.