Learning algebraic structures from text
Learning algebraic structures from text
复制标题
从文本中学习代数结构
DOI：
10.1016/s0304-3975(00)00272-3
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Yuri Ventsov
中科院分区：
文献类型：
--
作者：
F. Stephan;Yuri Ventsov
目前的工作研究了一些代数结构的子结构类的可学习性：给定群的子幺半群和子群、给定交换环的理想、给定向量空间的子域。学习者看到所有正数据，但看不到负数据，并收敛到一个程序，枚举或计算要学习的集合。除了语义（BC）和句法（Ex）收敛之外，还考虑了对思维变化数量的更严格的序数界限。如下所示：（a）可学习性在很大程度上取决于学习器综合时给出的语义知识的数量，其中这些知识由代数运算的程序、代数结构的突出元素的代码（如 0 和 1 域）和某些参数（如有限维向量空间的维数）来表示。对于几个自然的例子，良好的语义知识可能能够保持有序的思维变化界限，而有限的知识可能只允许 BC 收敛，甚至根本不允许可学习性。 (b) 递归环的所有理想类都是 BC 可学习的当且仅当该环是诺特环。此外，要么只有 BC 学习者输出可枚举的索引，要么已经可以让前学习者收敛到决策程序并尊重思想变化数量的序数界限。戒指是阿提尼安的，当且仅当理想可以通过思想变化次数的恒定界限来学习，这个常数就是戒指的长度。前可学习性不仅取决于环，还取决于环的表示。有 n 个变量的有理数域上的多项式环恰好具有标准表示中的序数思维变化界限 ω。 unar 也可以得到类似的结果。具有一个函数的 Noetherian unars 可以通过对某个 a 的序数思维变化绑定 aω 来学习。
The present work investigates the learnability of classes of substructures of some algebraic structures: submonoids and subgroups of given groups, ideals of given commutative rings, subfields of given vector spaces. The learner sees all positive data but no negative one and converges to a program enumerating or computing the set to be learned. Besides semantical (BC) and syntactical (Ex) convergence also the more restrictive ordinal bounds on the number of mind changes are considered. The following is shown: (a) Learnability depends much on the amount of semantic knowledge given at the synthesis of the learner where this knowledge is represented by programs for the algebraic operations, codes for prominent elements of the algebraic structure (like 0 and 1 fields) and certain parameters (like the dimension of finite-dimensional vector spaces). For several natural examples, good knowledge of the semantics may enable to keep ordinal mind change bounds while restricted knowledge may either allow only BC-convergence or even not permit learnability at all. (b) The class of all ideals of a recursive ring is BC-learnable iff the ring is Noetherian. Furthermore, one has either only a BC-learner outputting enumerable indices or one can already get an Ex-learner converging to decision procedures and respecting an ordinal bound on the number of mind changes. The ring is Artinian iff the ideals can be Ex-learned with a constant bound on the number of mind changes, this constant is the length of the ring. Ex-learnability depends not only on the ring but also on the representation of the ring. Polynomial rings over the field of rationals with n variables have exactly the ordinal mind change bound ωnin the standard representation. Similar results can be established for unars. Noetherian unars with one function can be learned with an ordinal mind change bound aω for some a .
DOI：
--
发表时间：
2006
期刊：
Integrable systems, geometry, and topology, AMS/IP Studies of Advanced Mathematics, American Mathematical Society 36
影响因子：
--
作者：
FURUYA;Jun;Martin Guest
通讯作者：
Martin Guest