The Wayback Machine - https://web.archive.org/web/20221028230514/https://baike.sogou.com/kexue/d10155.htm

极限内语言识别

编辑

极限内语言识别是归纳推理的一种形式模型，它是由马克·戈尔德（E. Mark Gold）在他的同名论文介绍的。[1]在这个模型中，他向学习者提供一些形式语言的表示方法(即字符串)。对这个模型的学习过程是无止尽的，每次阅读形式语言的一个符号时，学习者都应该为该语言提供一个表示(例如形式文法)。据说，如果给定一类语言中任何语言的任何表示，学习者可以在极限内识别该类语言，且表达这一语言的错误率较小，并因此在若干数量的步骤中收敛于正确的表示，然而不一定能够保证其正确性，因为一段时间后，任意出现的符号都可能成为该表达的反例。

戈尔德定义了两种类型的表达方式:

  • 文本（正信息：枚举语言中包含的所有字符串）
  • 完整呈现（正信息和负信息）: 枚举所有可能字符串，每个字符串都有一个标签，指示该字符串是否属于该语言

1 可学性编辑

这个模型是正式研究可学习性概念的早期尝试。戈尔德的论文[2] 介绍了级别更高的模型作为对比

  • 有限识别(学习者必须在有限的步骤后保证正确性)，以及
  • 固定时间识别(在预先指定的步骤数之后必须达到正确性)。

可学习性的一个弱化了的形式模型是莱斯利·瓦利安特在1984年提出的“可能的近似正确的学习(PAC) ”模型。

2 例子编辑

按要求完成演示
教师 学习者
Guess Query
0. abab
1. yes abab baba
2. yes a*(ba)*b* aa
3. no (ab)*(ba)*(ab)*(ba)* bababa
4. yes (ab+ba)* babb
5. no (ab+ba)* baaa
... ...
按陈述表达
教师 学习者
1. abab abab
2. baba a*(ba)*b*
3. aa (ab)*(ba)*(ab)*(ba)*
4. bababa (ab+ba)*
5. babb (ab+ba)*
6. baaa (ab+ba)*
7. ε (ab+ba)*
... ...
联合猜测
教师 学习者
1. abab abab
2. ba abab+ba
3. baba abab+ba+baba
4. ba abab+ba+baba
5. baba abab+ba+baba
6. abab abab+ba+baba
7. ε abab+ba+baba+ε
... ...
文本表达
教师 学习者
1. abab abab
2. baba abab+baba
3. baabab (b+ε)(ab)*
4. baabab (b+ε)(ab)*+baabab
5. abbaabba (ab)*(ba)*(ab)*(ba)*
6. baabbaab (ab+ba)*
7. bababa (ab+ba)*
...

了解学习课程的具体例子(在表格中)是很有启发性的，这一课程对极限内语言识别进行了说明。

  1. 一个虚构的程序，从文本表达中学习字母表{a,b}上的正则语言L。在每个步骤中，老师给出一个属于L的字符串，学习者回答一个对L的猜测，编码为正则表达式。在第三步，学习者的猜测与目前为止看到的字符串不一致；在步骤4中，老师反复给出一个字符串。在步骤6之后，学习者只使用正则表达式(ab+ba)*。如果这恰好是老师心目中语言的描述，那么就说学习者已经学会了那种语言。如果有一个适合学习者角色的计算机程序能够成功地学习每一种正则语言，那么这一类语言在极限内是可以识别的。戈尔德表明情况并非如此。[3]
  2. 一种特殊的学习算法认为L是迄今为止发现的所有字符串的并集。如果L是一种有限的语言，学习者最终会正确地识别它，然而，具体时间无从得知。虽然在第3步到第6步中猜测没有改变，但是学习者不能肯定是正确的。戈尔德已经表明有限语言的类别在极限内是可识别的，[4] 然而，这一类别既不是有限的也不是固定时间可识别的。
  3. 通过讲述从完整的陈述中学习。在每个步骤中，老师给出一个字符串，并判断它是否属于L(绿色)或不属于(红色，划掉)。老师最终会以这种方式对每个可能的字符串进行分类。
  4. 从按要求在表达中学习。学习者给出一个查询字符串，老师判断它是否属于L(是)或不属于(否)；然后，学习者猜测L，接着是下一个查询字符串。在这个例子中，学习者碰巧在每个步骤中查询与例子3中老师给出的字符串相同的字符串。戈尔德已经表明，通常而言在请求表达设置中可识别的每个语言类在讲述表达设置中也是可识别的，因为学习者不需要查询字符串，只需要等待老师最终给出字符串。

3 可学性表征编辑

Dana Angluin在1980年的一篇论文中提出了从文本(积极信息)中学习的特征。[5]如果一个要求学习者有效学习，那么递归语言的索引类在极限内是可学习的，如果有一个有效的程序统一列举该类中每种语言的情况（条件1）。[6] 不难看出，如果一个理想的学习者(即，一个任意的函数)是允许的，那么如果一个编入索引的语言类中的每一种语言都有一个说明（条件2），那么该类语言在极限内是可以学习的。[7]

4 可在极限内学习的语言类别编辑

可识别和不可识别语言类别之间的分界线 [8]
可学习性模型 语言类别
异常文本表达
递归可枚举
递归的
完整表达
原始递归
上下文敏感
上下文无关
正则
超级有限
普通文本表达
有限
单元素

该表显示了在学习模式的极限下哪些语言类别是可识别的。在右边，每个语言类都是所有低级类的超类。每个学习模型(即演示的类型)可以在极限范围内识别比自身等级低的所有类别。需要注意的是，有限语言的类别在极限内可以通过文本表达来识别(参见上面的示例2)，而正则语言的类别则不能。

模式语言，由达娜·安格林（Dana Anguin）在1980年的另一篇论文中介绍，[9] 也可以通过正常的文本表达来识别；表中省略了它们，因为它们在单元素语言之上，在原始递归语言类之下，但是它们之间的类不可比。

5 可学习性的充分条件编辑

安格林论文中的条件1[6]并不总是容易验证的。因此，人们提出了语言类别可学习性的各种充分条件。

5.1 有限厚度

如果一类语言中的每一个非空字符串集最多包含在有限的多种语言中，则该类语言的厚度是有限的。这正是安格林论文中的条件3。[10] 安格林证明，如果一类递归语言具有有限的厚度，那么它是可以在极限内学习的。[11]

一个有限厚度的类必然满足MEF条件和MFF条件；换句话说，有限厚度意味着=M有限厚度。[12]

5.2 有限弹性

如果对于每一个无限的字符串序列…   每一个无限的语言序列  ，存在一个有限的数n     与...不一致  。[13]

证明了一类递归可枚举语言如果具有有限的弹性，则在极限内是可学习的。

6 思想转变的界限编辑

收敛前假设变化次数的界限。

7 其他概念编辑

7.1 无限交叉性质

如果一类语言中存在一种语言具有无限交叉属性，那么这类语言就具有无限弹性。   如果有无限序列   不同的语言   和有限子集序列   使得:

  •  ,
  •  ,
  •  ，和
  •  。

请注意，L不一定是某类语言。

不难看出，如果一类语言中有一种具有无限交叉性质的语言，那么该类语言就具有无限的弹性。

8 概念之间的关系编辑

  • 有限厚度是有限弹性的充分条件；[12][14] 反之则不成立。
  • 有限的弹性和保守的可学习性意味着思维改变界限的存在。
  • 有限弹性和有限厚度意味着思维改变界限的存在。然而，仅仅是有限厚度并不意味着存在一个精神变化界限；思维改变界限的存在也不意味着有限厚度。
  • 思维改变界限的存在意味着可学习性；反之则不成立。
  • 如果我们考虑到不可计算的学习者，那么有限弹性意味着存在一个思维变化界限；反之则不成立。
  • 如果一类语言没有累积顺序，那么就有一种语言(不一定在类中)在类中具有无限的交叉属性，这反过来意味着类的无限弹性。

9 未决问题编辑

  • 如果一个递归语言的可计数类有一个面向不可计算学习者的思维改变，那么这个类也有一个面向可计算学习者的思维改变，或者这个类是一个可计算学习者不可计算的？

10 笔记编辑

  1. i.e. text presentation, where the string given by the teacher is a primitive recursive function of the current step number, and the learner encodes a language guess as a program that enumerates the language
  2. i.e. the class of languages that are decidable by primitive recursive functions
  3. i.e. containing all finite languages and at least one infinite one
  4. i.e. text presentation, except for the anomalous text presentation setting
  5. i.e. the class of languages consisting of a single string (they are mentioned here only as a common lower bound to finite languages and pattern languages)
  6. incomparable to regular and to context-free language class: Theorem 3.10, p.53

参考文献

  • [1]

    ^Gold, E. Mark (1967). "Language identification in the limit" (PDF). Information and Control. 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5..

  • [2]

    ^p.457.

  • [3]

    ^Theorem I.8,I.9, p.470-471.

  • [4]

    ^Theorem I.6, p.469.

  • [5]

    ^Dana Angluin (1980). "Inductive Inference of Formal Languages from Positive Data" (PDF). Information and Control. 45 (2): 117–135. doi:10.1016/S0019-9958(80)90285-5..

  • [6]

    ^p.121 top.

  • [7]

    ^p.123 top.

  • [8]

    ^Table 1, p.452, in (Gold 1967).

  • [9]

    ^Dana Angluin (1980). "Finding Patterns Common to a Set of Strings" (PDF). Journal of Computer and System Sciences. 21: 46–62. doi:10.1016/0022-0000(80)90041-0..

  • [10]

    ^p.123 mid.

  • [11]

    ^p.123 bot, Corollary 2.

  • [12]

    ^Andris Ambainis; Sanjay Jain; Arun Sharma (1997). "Ordinal mind change complexity of language identification" (PDF). Computational Learning Theory. LNCS. 1208. Springer. pp. 301–315.; here: Proof of Corollary 29.

  • [13]

    ^Motoki, Shinohara, and Wright (1991) "The correct definition of finite elasiticity: corrigendum to identification of unions", Proc. 4th Workshop on Computational Learning Theory, 375-375.

  • [14]

    ^Wright, Keith (1989) "Identification of Unions of Languages Drawn from an Identifiable Class". Proc. 2nd Workwhop on Computational Learning Theory, 328-333; with correction in:[13].

阅读 46
版本记录

  • 暂无