• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Machine learning >On the Learnability of the Uncomputable
【24h】

On the Learnability of the Uncomputable

机译：论无可争议的可学习性

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Within Valiant's model of learning as formalized by Kearns, we show that computable total predicates for two formally uncomputable problems (the classical Halting Problem, and the Halting Problem relative to a specified oracle) are formally learnable from examples, to arbitrarily high accuracy with arbitrarily high confidence, under any probability distribution. The Halting Problem relative to the oracle is learnable in time polynomial in the measures of accuracy, confidence, and the length of the learned predicate. The classical Halting Problem is learnable in expected time polynomial in the measures of accuracy, confidence, and the (1 - ∈/16)~(th) percentile length and run-time of programs which do halt on their inputs (these quantities are always finite). Equivalently, the mean length and run-time may be substituted for the percentile values in the time complexity statement. The proofs are constructive. While the problems are learnable, they are not poly-nomially learnable, even though we do derive polynomial time bounds on the learning algorithm.
机译：在Kearns形式化的Valiant学习模型中，我们证明了两个形式上无可辩驳的问题（经典的Halting问题和相对于特定oracle的Halting问题）的可计算总谓词可以从示例中正式学习，从而达到任意高精度和任意高在任何概率分布下的置信度。相对于oracle的Halting问题可以在时间多项式中以准确度，置信度和所学谓词的长度来学习。可以在预期时间多项式中以准确性，置信度以及在其输入上停止的程序的（1-ε/ 16）〜（th）百分位数长度和运行时间的量度来学习经典的停止问题（这些数量始终为有限）。等效地，可以用时间长度声明中的百分位值代替平均长度和运行时间。证明是建设性的。尽管这些问题是可以学习的，但是即使我们确实在学习算法上得出了多项式时间边界，也无法通过多项式学习这些问题。

著录项

  • 来源
    《Machine learning》|1996年|302-309|共8页
  • 会议地点 Bari(IT);Bari(IT)
  • 作者

    Richard H. Lathrop;

  • 作者单位

    Information and Computer Science Dept. University of California Irvine, CA 92717-3425;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算机的应用;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号