只需在每条语句末尾加1个比特,就能实现所有可数语言的准确识别。
Globally Consistent Coloring Schemes for Language Identification
- 用末位1比特颜色编码替代完整颜色序列,实现语言识别
- 单个全局预设的二元末位着色可覆盖任意可数语言子集
- 证明有限颜色的显式构造不可能实现,凸显非构造性本质
我们研究在对抗性语言学习中需要多少额外信息。在Gold的语言识别极限模型中,学习者面对一个未知语言的字符串枚举,需逐步猜测其身份,最终所有猜测都应正确。经典结果表明,许多自然语言集合无法在此框架下被学习。近期基于思维轨迹策略的痕迹着色方法通过为每个字符串的每个符号标注颜色,克服了这一障碍。本文探讨是否必须使用完整颜色序列,或仅在每条字符串末尾附加一个颜色(终端着色)是否足够。我们证明:对任意可数无限语言集合,仅需每条字符串一个末位比特即可实现语言识别。事实上,该着色方案可独立于语言集合预先设定——存在一个统一的二值末位着色分配,能识别任意可数子集。该全局构造依赖超限归纳法,且证明任何有限颜色数目的构造均不可避免地具有非构造性。以Borel映射作为构造性标准(满足自然显式构造的正则性),我们证明:不存在由Borel映射定义的有限颜色全局终端着色能识别所有可数子集。相反,已知的痕迹着色构造若编码为末端着色,则是Borel的,但需无穷多颜色。
原文摘要 · Abstract (English)
We study how little extra information is needed to make adversarial language learning possible. In Gold's model of language identification in the limit, a learner is given an enumeration of the strings from an unknown language chosen from a countable language collection. The learner guesses the identity of the language over the course of the enumeration, and it succeeds if, eventually, all of its guesses are the correct language. Classical results of Gold and Angluin show that many natural collections cannot be learned in this way. Recent work on trace colorings, motivated by the success of thinking-trace strategies in language learning, overcomes this obstruction by annotating every symbol of every string with a color. We ask whether the learner really needs this whole sequence of colors, or whether one color at the end of each string (a terminal coloring) is enough for language identification. We show that just one terminal bit per string is enough for every countable collection of infinite languages. In fact, the colorings can be chosen collection-independently: there is a single assignment of a two-color terminal coloring to every infinite language such that the same preassigned colorings identify every countable subcollection. Thus, in this model, an entire color trace can be compressed to one bit attached to the end of each example. Our global construction uses transfinite recursion, and we prove that this kind of nonconstructivity is unavoidable for any bounded number of colors. As a notion of constructivity, we use the formalism of Borel maps (a regularity condition satisfied by natural explicit constructions); we show that no global terminal coloring with a finite number of colors defined by a Borel map can identify all countable subcollections. By contrast, known trace-coloring constructions are Borel when encoded as terminal colorings, but require infinitely many colors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。