NSF Young Investigator: Understanding Basic Issues in Machine Learning, On-line Planning, and Approximate Algorithms

本研究探讨了理论工具的应用，以分析机器学习、不完全信息规划和近似算法中的基本问题。在机器学习领域，一个方向是为快速学习提供新的算法技术，当有很多关于对象的信息，但只有一小部分是真正相关的。这些技术对于加速学习和自动化选择给学习算法提供哪些信息的过程都有潜在的用处。此外，还研究了利用神经网络学习的新算法，特别是在高维输入空间的困难情况下。其他基础研究问题包括学习和密码学之间的关系，以及学习者可以有效地采用更积极的方法的各种方法。在在线规划领域，过去的工作一直是关于在没有地图的情况下在具有简单障碍类型的场景中旅行的策略，如果一个人有该地区的地图，其表现可以保证不会比最好的情况差太多。这可以扩展到更多不同的情况，包括某些类型的局部地图可用的情况。一个有趣的例子是，部分地图是由以前的探索创建的。在这里，人们可以将在线计划和学习结合起来。

This research investigates application of theoretical tools to analyze fundamental issues in machine learning, in planning from incomplete information, and in approximation algorithms. In the area of machine learning, one direction is to provide new algorithmic techniques for fast learning when there is much information available about objects but only a small amount is truly relevant. These techniques are potentially useful both for speeding up learning and for automating the process of selecting what information is given to a learning algorithm. Also new algorithms for learning using neural networks are investigated, especially in the difficult case of high dimensional input spaces. Other fundamental research issues examined include relationships between learning and cryptography, and various ways a learner can usefully employ more active approaches. In the domain of on-line planning past work has been on strategies for traveling without a map in scenes with simple types of obstacles, whose performance can be guaranteed to be not too much worse than the best possible, if one had a map of the region. This is expanded to more varied situations, including those where some kinds of partial maps are available. One interesting case is where partial maps are created by previous explorations. Here one can combine ideas of on-line planning and learning.