On Strings with Trivial Kolmogorov Complexity

The Kolmogorov complexity of a string is the length of the shortest program that generates it. A binary string is said to have trivial Kolmogorov complexity if its complexity is at most the complexity of its length. Intuitively, such strings carry no more information than the information that is inevitably coded into their length (which is the same as the information coded into a sequence of 0s of the same length). We study the set of these trivial sequences from a computational perspective, and with respect to plain and prefix-free Kolmogorov complexity. This work parallels the well known study of the set of nonrandom strings (which was initiated by Kolmogorov and developed by Kummer, Muchnik, Stephan, Allender and others) and points to several directions for further research.     

Rudimentary结构等价性及其应用研究

Bayesian网的结构学习是Bayesian网研究的难点之一．当问题中的变量较多时，通过结构学习得到的网络结构往往不具有唯一性．文中通过对Bayesian网结构等价性的研究，提出了Rudimentary结构等价性定理，并给出了该定理的证明．该等价性定理为提高结构学习的速度和优化Bayesian网的结构提供了理论依据．实验结果表明该定理具有较好的实用价值．     

Stochastic Finite Learning of the Pattern Languages

The present paper proposes a new learning model—called stochastic finite learning—and shows the whole class of pattern languages to be learnable within this model.This main result is achieved by providing a new and improved average-case analysis of the Lange–Wiehagen (New Generation Computing, 8, 361–370) algorithm learning the class of all pattern languages in the limit from positive data. The complexity measure chosen is the total learning time, i.e., the overall time taken by the algorithm until convergence. The expectation of the total learning time is carefully analyzed and exponentially shrinking tail bounds for it are established for a large class of probability distributions. For every pattern containing k different variables it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of , where and are two easily computable parameters arising naturally from the underlying probability distributions, and E[] is the expected example string length.Finally, assuming a bit of domain knowledge concerning the underlying class of probability distributions, it is shown how to convert learning in the limit into stochastic finite learning.     

一种快速的贝叶斯网结构学习算法

贝叶斯网是不确定性问题知识表达和推理中最重要的一个理论模型．迄今为止人们提出了许多贝叶斯网结构学习算法,基于约束满足和评分搜索相结合的混合方法是其中的一个研究热点．以I—B＆B—MDL为基础,提出了一种快速的学习算法．新算法不仅利用约束知识来压缩搜索空间,而且还用它作为启发知识来引导搜索．首先利用0阶和少量的1阶测试有效地限制搜索空间,获得网络候选的连接图,减少了独立性测试及对数据库的扫描次数,然后利用互信息作为启发性知识来引导搜索,增加了B＆B搜索树的截断．在通用数据集上的实验表明：快速算法能够有效地处理大规模数据,且学习速度有较大改进．     

一种基于SLIQ的快速扩展分类算法的实现

ID3算法是一种信息熵的决策树学习算法,把信息熵作为选择测试属性的标准,对训练实例集进行分类并构造决策树来预测如何由属性对整个实例空间进行划分。ID3算法对于相对小的数据集是很有效的,但对大型数据库而言,ID3算法无法处理。SLIQ分类算法使用了一些独特的技术,改进了学习的时间,同时在没有降低精确度的情况下,解决了对磁盘驻留大数据集的分类。具有更快的速度而且生成较小的树。     

Learning multiple languages in groups

We consider a variant of Gold’s learning paradigm where a learner receives as input n$n$ different languages (in the form of one text where all input languages are interleaved). Our goal is to explore the situation when a more “coarse” classification of input languages is possible, whereas more refined classification is not. More specifically, we answer the following question: under which conditions, a learner, being fed n$n$ different languages, can produce m$m$ grammars covering all input languages, but cannot produce k$k$ grammars covering input languages for any k>m$k>m$. We also consider a variant of this task, where each of the output grammars may not cover more than r$r$ input languages. Our main results indicate that the major factor affecting classification capabilities is the difference n−m$n-m$ between the number n$n$ of input languages and the number m$m$ of output grammars. We also explore the relationship between classification capabilities for smaller and larger groups of input languages. For the variant of our model with the upper bound on the number of languages allowed to be represented by one output grammar, for classes consisting of disjoint languages, we found complete picture of relationship between classification capabilities for different parameters n$n$ (the number of input languages), m$m$ (number of output grammars), and r$r$ (bound on the number of languages represented by each output grammar). This picture includes a combinatorial characterization of classification capabilities for the parameters n,m,r$n,m,r$ of certain types.     

Using Dialogue Features to Predict Trouble During Collaborative Learning

A web-based, collaborative distance-learning system that will allow groups of students to interact with each other remotely and with an intelligent electronic agent that will aid them in their learning has the potential for improving on-line learning. The agent would follow the discussion and interact with the participants when it detects learning trouble of some sort, such as confusion about the problem they are working on or a participant who is dominating the discussion or not interacting with the other participants. In order to recognize problems in the dialogue, we investigated conversational elements that can be utilized as predictors for effective and ineffective interaction between human students. These elements can serve as the basis for student and group models. In this paper, we discuss group interaction during collaborative learning, our representation of participant dialogue, and the statistical models we are using to determine the role being played by a participant at any point in the dialogue and the effectiveness of the group. We also describe student and group models that can be built using conversational elements and discuss one set that we built to illustrate their potential value in collaborative learning. An erratum to this article is available at .     

On universal transfer learning

In transfer learning the aim is to solve new learning tasks using fewer examples by using information gained from solving related tasks. Existing transfer learning methods have been used successfully in practice and PAC analysis of these methods have been developed. But the key notion of relatedness between tasks has not yet been defined clearly, which makes it difficult to understand, let alone answer, questions that naturally arise in the context of transfer, such as, how much information to transfer, whether to transfer information, and how to transfer information across tasks. In this paper, we look at transfer learning from the perspective of Algorithmic Information Theory/Kolmogorov complexity theory, and formally solve these problems in the same sense Solomonoff Induction solves the problem of inductive inference. We define universal measures of relatedness between tasks, and use these measures to develop universally optimal Bayesian transfer learning methods. We also derive results in AIT that are interesting by themselves. To address a concern that arises from the theory, we also briefly look at the notion of Kolmogorov complexity of probability measures. Finally, we present a simple practical approximation to the theory to do transfer learning and show that even these are quite effective, allowing us to transfer across tasks that are superficially unrelated. The latter is an experimental feat which has not been achieved before, and thus shows the theory is also useful in constructing practical transfer algorithms.     

一种混合的贝叶斯网结构学习算法

贝叶斯网是人工智能中一个重要的理论模型,也是现实世界中不确定性问题建模的重要工具.针对贝叶斯网的结构学习问题,提出了一种将约束满足、蚁群优化和模拟退火策略相结合的混合算法.新算法首先利用阈值自调整的条件测试来动态地压缩搜索空间,在加速搜索过程的同时保证学习的求解质量;然后在基于MDL的蚁群随机搜索中引入模拟退火的优化调节机制,改进了算法的优化效率.实验结果验证了所提策略的有效性,与最新的同类算法相比,新算法在保持较快收敛速度的前提下具有更好的求解质量.     

Learning to Predict by the Methods of Temporal Differences

This article introduces a class of incremental learning procedures specialized for prediction – that is, for using past experience with an incompletely known system to predict its future behavior. Whereas conventional prediction-learning methods assign credit by means of the difference between predicted and actual outcomes, the new methods assign credit by means of the difference between temporally successive predictions. Although such temporal-difference methods have been used in Samuel's checker player, Holland's bucket brigade, and the author's Adaptive Heuristic Critic, they have remained poorly understood. Here we prove their convergence and optimality for special cases and relate them to supervised-learning methods. For most real-world prediction problems, temporal-difference methods require less memory and less peak computation than conventional methods and they produce more accurate predictions. We argue that most problems to which supervised learning is currently applied are really prediction problems of the sort to which temporal-difference methods can be applied to advantage.     

利用学习向量化样本分类的在线学习成绩预测

对网络在线学习者产生的数据进行记录和分析,并为其提供精准化的个性化服务是在线教育发展的重要方面.本文以学习者在平台上产生的日常学习数据为样本,综合其最具代表性的五种影响因子,通过学习向量化神经网络对样本进行分类,得到基于BP神经网络的在线学习成绩预测数据.在模型中采用遗传算法有效优化BP神经网络的权重和阈值,在提高预测精度的同时加快模型的收敛速度.最后与其他两种模型进行对比分析,结果表明：该模型进行预测的结果与真实的成绩分布基本一致,具有很高的可信度,能够为有效的预测学习状态提供决策依据,具有一定的工程应用价值.     

Complexity–Based Induction

A central problem in inductive logic programming is theory evaluation. Without some sort of preference criterion, any two theories that explain a set of examples are equally acceptable. This paper presents a scheme for evaluating alternative inductive theories based on an objective preference criterion. It strives to extract maximal redundancy from examples, transforming structure into randomness. A major strength of the method is its application to learning problems where negative examples of concepts are scarce or unavailable. A new measure called model complexity is introduced, and its use is illustrated and compared with a proof complexity measure on relational learning tasks. The complementarity of model and proof complexity parallels that of model and proof–theoretic semantics. Model complexity, where applicable, seems to be an appropriate measure for evaluating inductive logic theories.     

基于描述复杂性的优化学习算法

从描述复杂性的角度出发，提出了一种新的优化学习算法，描述复杂性理论认为，一个数据集的最小长度描述最能体现出这个数据集的本质规律，借鉴机器学习和认知心理学领域的研究成果，该文采用“规则＋例外”作为描述方法，从而把学习问题转化成求在“规则＋例外”描述方法下的最小长度描述的优化问题，实验表明，这种算法的结果能够得到很好的解释。     

A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems

In 2002, Jurdziński and Lory? settled a long-standing conjecture that palindromes are not a Church-Rosser language. Their proof involved a difficult analysis of computation graphs associated with 2-pushdown-stack automata. We present a shorter and easier proof in terms of 1-tape Turing machines.We also discuss how the proof generalises to almost-confluent Thue systems and the differing powers of Church-Rosser, almost-confluent, and preperfect Thue systems in relation to palindromes.     

Comprehension Grammars Generated from Machine Learning of Natural Languages

We are developing a theory of probabilistic language learning in the context of robotic instruction in elementary assembly actions. We describe the process of machine learning in terms of the various events that happen on a given trial, including the crucial association of words with internal representations of their meaning. Of central importance in learning is the generalization from utterances to grammatical forms. Our system derives a comprehension grammar for a superset of a natural language from pairs of verbal stimuli like Go to the screw! and corresponding internal representations of coerced actions. For the derivation of a grammar no knowledge of the language to be learned is assumed but only knowledge of an internal language.We present grammars for English, Chinese, and German generated from a finite sample of about 500 commands that are roughly equivalent across the three languages. All of the three grammars, which are context-free in form, accept an infinite set of commands in the given language.     

基于最小描述长度准则的数字信道化接收机频谱检测方法

数字信道化接收机常采用频谱检测方法判断其分析滤波器组中的输出子带信号的存在。为解决现有基于特征值的频谱检测方法由于采用最大和最小特征值的近似值而导致采样点数较少时性能无法满足要求的问题,提出了一种适用于数字信道化接收机的基于最小描述长度(MDL)准则的子带频谱检测方法。基于子带过采样数据构建协方差矩阵,计算矩阵特征值的平均值以减少噪声带来的波动。将矩阵特征值的平均值作为MDL准则的参数估计所有子带的平均特征值中包含信号的个数,以此确定包含信号的子带。仿真实验表明,该方法比现有的频谱检查方法具有更好的检测性能,且克服了需要设置固定门限的缺点,对噪声和信号波动具有较强的适应能力。