Learning Generalized Horn Sentences

学习广义喇叭句子

• 批准号: 9212011
• 负责人: Vijay Raghavan
• 金额: $ 6万
• 依托单位: Vanderbilt University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-07-01 至 1995-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9212011&HistoricalAwards=false
• 关键词: Learning; Generalized; Horn; Sentences

This research addresses the learning of a concept class in the exact learning model. This concept class, the set of k-quasi Horn sentences, has crucial significance in both models: it is known that if k-quasi Horn sentences are shown to be learnable in the exact learning model, then (under some general cryptographic assumptions) the large class of conjunctive normal form sentences are predictable in the PAC model. Partial research has shown that k-quasi Horn sentences are indeed learnable when the exact learning model is augmented with somewhat more power. This line of research will be continued to obtain a definitive answer about the learnability of k-quasi Horn sentences in the exact learning model.

本研究探讨了概念类的学习， 精确学习模型 这个概念类，k-拟 角句，具有至关重要的意义，在这两个模型：它 已知如果k-拟Horn语句被证明是 在精确的学习模型中是可学习的，那么（在一些 一般密码学假设）的大类 连接范式句子在PAC中是可预测的 模型 部分研究表明，k-拟Horn语句 当精确的学习模型是 增加了更多的力量。 这一系列研究 将继续获得关于 精确学习中k-拟Horn语句的可学性 模型