Overfitting and undercomputing in machine learning
Overfitting and undercomputing in machine learning
复制标题
DOI：
10.1145/212094.212114
复制
发表时间：
1995-09-01
影响因子：
16.6
通讯作者：
Dietterich, T
中科院分区：
文献类型：
--
作者：
Dietterich, T
机器学习的一个核心问题是监督学习，即从标记的训练数据中学习。例如，一个用于医学诊断的学习系统可以用患者的例子来训练，这些患者的病例记录（医学测试、临床观察）和诊断是已知的。学习系统的任务是从病人的病历中推断出一个预测病人诊断的函数。要学习的函数可以表示为一组规则、决策树、贝叶斯网络或神经网络。学习算法本质上是通过搜索某个函数空间（通常称为假设类）来寻找适合给定数据的函数。由于通常有指数级的函数，这种搜索实际上不能检查单个假设函数，而是必须使用一些更直接的方法从数据中构造假设函数。这种搜索通常可以通过定义目标函数（例如，错误预测的数据点的数量）并应用各种算法来找到最小化该目标函数的函数来形式化，这是NP难的。例如，拟合神经网络的权重或找到最小的决策树都是NP完全问题[Blum and Rivest，1989; Quinlan and Rivest 1989]。因此，启发式算法，如梯度下降（用于神经网络）和贪婪搜索（用于决策树）已被成功应用。
A central problem in machine learning is supervised learning—that is, learning from labeled training data. For example, a learning system for medical diagnosis might be trained with examples of patients whose case records(medical tests, clinical observations) and diagnoses were known. The task of the learning system is to infer a function that predicts the diagnosis of a patient from his or her case records. The function to be learned might be represented as a set of rules, a decision tree, a Bayes network, or a neural network.Learning algorithms essentially operate by searching some space of functions (usually called the hypothesis class) for a function that fits the given data. Because there are usually exponentially many functions, this search cannot actually examine individual hypothesis functions but instead must use some more direct method of constructing the hypothesis functions from the data. This search can usually be formalized by defining an objective function(eg, number of data points predicted incorrectly) and applying various algorithms to find a function that minimizes this objective function is NP-hard. For example, fitting the weights of a neural network or finding the smallest decision tree are both NP-complete problems[Blum and Rivest, 1989; Quinlan and Rivest 1989]. Hence, heuristic algorithms such as gradient descent (for neural networks) and greedy search(for decision trees) have been applied with great success.