Mathematical Sciences: Greedy Growing and its Applications

数学科学：贪婪增长及其应用

• 批准号: 9501926
• 负责人: Andrew Nobel
• 金额: $ 7.2万
• 依托单位: University of North Carolina at Chapel Hill
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-07-01 至 1999-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9501926&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Greedy; Growing; its

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.

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