课题基金 / 基金详情

Efficient learning algorithms based on infomation compression

Efficient learning algorithms based on infomation compression
基于信息压缩的高效学习算法
批准号:
05452349
负责人:
JIMBO Shuji
金额:
$4.8万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for General Scientific Research (B)
财政年份:
1993
资助国家:
日本
项目状态:
已结题
起止时间:
1993 至 1994

项目摘要

项目成果

JIMBO Shuji的其他基金

相似基金

相关文献

中文摘要
翻译
1.学习过程中的信息压缩和获取机制PAC学习模型中,学习算法期望通过使用目标函数的一系列示例来产生一个近似目标函数的假设.另一方面,一个信息压缩算法的概念,称为Occan算法,已被引入和PAC学习算法的关系进行了研究。研究表明,Occam算法直接是PAC学习算法,而PAC学习算法可以通过修改得到随机化Occam算法,并探讨了这两类算法之间的关系。通过反例说明PAC学习算法不一定是Occam算法。介绍了自然PAC学习算法所应满足的合理性条件,即单调性和可重复性。并且证明了PAC学习算法在任何这些条件下都立即成为Occam算法 ...更多信息 两个条件虽然该猜想至今尚未得到证明,但在一定的技术条件下,证明了该命题成立。此外,还介绍了信息增益算法的一种运动,并探讨了它与PAC学习算法和信息压缩算法的关系.析取范式公式的学习在计算学习领域中,判别析取范式(DNF)公式是否是可学习的形式样本是一个重要的开放问题。得到的主要结果如下:具有log n项的单调DNF公式可从正例中学习;新的布尔函数,称为kappa项函数,可从正例中学习.计算复杂性和近似计算学习所需的计算资源取决于其目标的复杂性。研究了目标函数的计算复杂性问题,如布尔复杂性、近似计算、伪随机性等.在利用模式匹配方法进行字符识别时,如何为每个字符模式构造特征向量是关键。从信息压缩的角度出发,研究了用于精确识别的特征向量的确定问题。少
英文摘要
1. Information compressing and gaining mechanism in learning processIn PAC learning model a learning algorithm is expected to produce a hypothesis that approximates a target function by using a sequence of examples of the target. On the other hand the notion of an information compressing algorithm, called an Occan algorithm, has been introduced and its relation to a PAC learning algorithm has been investigated. It has been shown that an Occam algorithm is immediately a PAC learning algorithm, while a PAC learning algorithm can be modified to obtain a randomized Occam algorithm.We investigate relationship between these types of algorithms. We show that a PAC learning algorithm is not necessarily an Occam algorithm by giving a counter example. Reasonal conditions, called preservability and monotonicity, which natural PAC learning algorithms are expected to satisfy are introduced. And it is conjectured that a PAC learning algorithm becomes immediately an Occam algorithm under any of these … More two conditions. Although the conjecture has not been proved so far, it is verified that the statement holds under some technical conditions. Furthermore, a motion of an information gaining algorithm is introduced and its relation to a PAC learning algorithm and an information compressing algorithm is explored.2. Learning of disjunctive normal form formulaeIn the field of computational learning it is one of the most important open problems to decide whether or not disjunctive normal form (DNF) formulae are learnable form examples. The main results obtained are stated as follows : Monotone DNF formulae with log n terms are learnable from positive examples ; New Boolean functions, called kappa term functions, are learnable from examples.3. Computational complexity and appoximate computationComputational resources needed for learning depend on the complexity of its target. Various issues, such as Boolean complexity, approximate computation, pseudo-randomness, concerning computational complexity of target functions are investigated.4. Extracting character feature on pattern matchingWhen character recognition is implemented by using the method of pattern matching, it is crucial how to make a feature vector for each character pattern. In view of information compression, the problem of defining the feature vectors for precies recognition is investigated. Less
期刊论文(30)
专著(0)
科研奖励(0)
会议论文
阿曽弘具: "文字特徴量空間の性質と特徴抽出法の性能評価法" 電子情報通信学会論文誌 D‐II,J76‐D‐II. 2285-2294 (1993)
Hirogu Aso:“特征提取方法的字符特征空间的性质和性能评估方法”,电子信息通信工程师学会会刊 D-II,J76-D-II 2285-2294(1993)。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
Shuji Jimbo: "A method of constructing selection networks with O(log n)depth" SIAM Journal on Computing. (発表予定).
Shuji Jimbo:“一种构建 O(log n) 深度选择网络的方法”SIAM 计算杂志(即将出版)。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
Eiji Takimoto: "Mutual Information gaining algorithm and its relation to PAC-learning algorithm" Proc.of the Workshop on Algorithmic Learning Theory. 547-559 (1994)
Eiji Takimoto:“互信息获取算法及其与 PAC 学习算法的关系”Proc.of the Workshop on Algorithmic Learning Theory。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
共 13 条
    Development of Fast Deterministic Primarity Testing Algorithms Based on Pseudosquares
    • 批准号:
      24650007
    • 项目类别:
      Grant-in-Aid for Challenging Exploratory Research
    • 资助金额:
      $1.5万
    • 财政年份:
      2012
    • 负责人:
      JIMBO Shuji
    • 依托单位:
    海外基金