Optimal language learning from positive data

Gold?s original paper on inductive inference introduced a notion of an optimal learner. Intuitively, a learner identifies a class of objects optimally iff there is no other learner that: requires as little of each presentation of each object in the class in order to identify that object, and, for some presentation of some object in the class, requires less of that presentation in order to identify that object. Beick considered this notion in the context of function learning, and gave an intuitive characterization of an optimal function learner. Jantke and Beick subsequently characterized the classes of functions that are algorithmically, optimally identifiable.Herein, Gold?s notion is considered in the context of language learning. It is shown that a characterization of optimal language learners analogous to Beick?s does not hold. It is also shown that the classes of languages that are algorithmically, optimally identifiable cannot be characterized in a manner analogous to that of Jantke and Beick.Other interesting results concerning optimal language learning include the following. It is shown that strong non-U-shapedness, a property involved in Beick?s characterization of optimal function learners, does not restrict algorithmic language learning power. It is also shown that, for an arbitrary optimal learner F of a class of languages L, F optimally identifies a subclass K of L iff F is class-preserving with respect to K.     

Control structures in hypothesis spaces: the influence on learning

In any learnability setting, hypotheses are conjectured from some hypothesis space. Studied herein are the influence on learnability of the presence or absence of certain control structures in the hypothesis space. First presented are control structure characterizations of some rather specific but illustrative learnability results. The presence of these control structures is thereby shown essential to maintain full learning power. Then presented are the main theorems. Each of these non-trivially characterizes the invariance of a learning class over hypothesis space V and the presence of a particular projection control structure, called proj, in V as: V has suitable instances of all denotational control structures. In a sense, then, proj epitomizes the control structures whose presence need not help and whose absence need not hinder learning power.     

On the data consumption benefits of accepting increased uncertainty

In the context of learning paradigms of identification in the limit, we address the question: why is uncertainty sometimes desirable? We use mind change bounds on the output hypotheses as a measure of uncertainty and interpret ‘desirable’ as reduction in data memorization, also defined in terms of mind change bounds. The resulting model is closely related to iterative learning with bounded mind change complexity, but the dual use of mind change bounds — for hypotheses and for data — is a key distinctive feature of our approach. We show that situations exist where the more mind changes the learner is willing to accept, the less the amount of data it needs to remember in order to converge to the correct hypothesis. We also investigate relationships between our model and learning from good examples, set-driven, monotonic and strong-monotonic learners, as well as class-comprising versus class-preserving learnability.     

Relations between Gold-style learning and query learning

Different formal learning models address different aspects of human learning. Below we compare Gold-style learning—modelling learning as a limiting process in which the learner may change its mind arbitrarily often before converging to a correct hypothesis—to learning via queries—modelling learning as a one-shot process in which the learner is required to identify the target concept with just one hypothesis. In the Gold-style model considered below, the information presented to the learner consists of positive examples for the target concept, whereas in query learning, the learner may pose a certain kind of queries about the target concept, which will be answered correctly by an oracle (called teacher). Although these two approaches seem rather unrelated at first glance, we provide characterisations of different models of Gold-style learning (learning in the limit, conservative inference, and behaviourally correct learning) in terms of query learning. Thus we describe the circumstances which are necessary to replace limit learners by equally powerful one-shot learners. Our results are valid in the general context of learning indexable classes of recursive languages. This analysis leads to an important observation, namely that there is a natural query learning type hierarchically in-between Gold-style learning in the limit and behaviourally correct learning. Astonishingly, this query learning type can then again be characterised in terms of Gold-style inference.     

Prescribed learning of r.e. classes

This work extends studies of Angluin, Lange and Zeugmann on the dependence of learning on the hypothesis space chosen for the language class in the case of learning uniformly recursive language classes. The concepts of class-comprising (where the learner can choose a uniformly recursively enumerable superclass as the hypothesis space) and class-preserving (where the learner has to choose a uniformly recursively enumerable hypothesis space of the same class) are formulated in their study. In subsequent investigations, uniformly recursively enumerable hypothesis spaces have been considered. In the present work, we extend the above works by considering the question of whether learners can be effectively synthesized from a given hypothesis space in the context of learning uniformly recursively enumerable language classes. In our study, we introduce the concepts of prescribed learning (where there must be a learner for every uniformly recursively enumerable hypothesis space of the same class) and uniform learning (like prescribed, but the learner has to be synthesized effectively from an index of the hypothesis space). It is shown that while for explanatory learning, these four types of learnability coincide, some or all are different for other learning criteria. For example, for conservative learning, all four types are different. Several results are obtained for vacillatory and behaviourally correct learning; three of the four types can be separated, however the relation between prescribed and uniform learning remains open. It is also shown that every (not necessarily uniformly recursively enumerable) behaviourally correct learnable class has a prudent learner, that is, a learner using a hypothesis space such that the learner learns every set in the hypothesis space. Moreover the prudent learner can be effectively built from any learner for the class.     

A general comparison of language learning from examples and from queries

In language learning, strong relationships between Gold-style models and query models have recently been observed: in some quite general setting Gold-style learners can be replaced by query learners and vice versa, without loss of learning capabilities. These ‘equalities’ hold in the context of learning indexable classes of recursive languages.     

Increasing the power of uniform inductive learners

The analysis of theoretical learning models is basically concerned with the comparison of identification capabilities in different models. Modifications of the formal constraints affect the quality of the corresponding learners on the one hand and regulate the quantity of learnable classes on the other hand.For many inductive inference models—such as Gold's identification in the limit—the corresponding relationships of learning potential provided by the compatible learners are well-known. Recent work even corroborates the relevance of these relationships by revealing them still in the context of uniform Gold-style learning. Uniform learning is rather concerned with the synthesis of successful learners instead of their mere existence.The subsequent analysis further strengthens the results regarding uniform learning, particularly aiming at the design of methods for increasing the potential of the relevant learners. This demonstrates how to improve given learning strategies instead of just verifying the existence of more powerful uniform learners.For technical reasons these results are achieved using various formal conditions concerning the learnability of unions of uniformly learnable classes. Therefore numerous sufficient properties for the learnability of such unions are presented and illustrated with several examples.     

Estimation-based norm-optimal iterative learning control

The norm-optimal iterative learning control (ilc) algorithm for linear systems is extended to an estimation-based norm-optimal ilc  algorithm where the controlled variables are not directly available as measurements. A separation lemma is presented, stating that if a stationary Kalman filter is used for linear time-invariant systems then the ilc  design is independent of the dynamics in the Kalman filter. Furthermore, the objective function in the optimisation problem is modified to incorporate the full probability density function of the error. Utilising the Kullback–Leibler divergence leads to an automatic and intuitive way of tuning the ilc  algorithm. Finally, the concept is extended to non-linear state space models using linearisation techniques, where it is assumed that the full state vector is estimated and used in the ilc  algorithm. Stability and convergence properties for the proposed scheme are also derived.     

Adaptive iterative learning control for robot manipulators

In this paper, we propose some adaptive iterative learning control (ILC) schemes for trajectory tracking of rigid robot manipulators, with unknown parameters, performing repetitive tasks. The proposed control schemes are based upon the use of a proportional-derivative (PD) feedback structure, for which an iterative term is added to cope with the unknown parameters and disturbances. The control design is very simple in the sense that the only requirement on the PD and learning gains is the positive definiteness condition and the bounds of the robot parameters are not needed. In contrast to classical ILC schemes where the number of iterative variables is generally equal to the number of control inputs, the second controller proposed in this paper uses just two iterative variables, which is an interesting fact from a practical point of view since it contributes considerably to memory space saving in real-time implementations. We also show that it is possible to use a single iterative variable in the control scheme if some bounds of the system parameters are known. Furthermore, the resetting condition is relaxed to a certain extent for a certain class of reference trajectories. Finally, simulation results are provided to illustrate the effectiveness of the proposed controllers.     

Predictive iterative learning control with experimental validation

This paper develops an iterative learning control law that exploits recent results in the area of predictive repetitive control where a priori information about the characteristics of the reference signal is embedded in the control law using the internal model principle. The control law is based on receding horizon control and Laguerre functions can be used to parameterize the future control trajectory if required. Error convergence of the resulting controlled system is analyzed. To evaluate the performance of the design, including comparative aspects, simulation results from a chemical process control problem and supporting experimental results from application to a robot with two inputs and two outputs are given.     

高阶无模型自适应迭代学习控制

针对一类非线性非仿射离散时间系统,提出了高阶无模型自适应迭代学习控制方案.控制器的设计和分析仅依赖于系统的输入/输出(I/O)数据,不需要已知任何其他知识.该方法采用了高阶学习律,可利用更多以前重复过程中的控制信息提高系统收敛性,且学习增益可通过"拟伪偏导数"更新律迭代调节.仿真结果验证了所提出算法的有效性.     

Generalized iterative RELIEF for supervised distance metric learning

The RELIEF algorithm is a popular approach for feature weighting. Many extensions of the RELIEF algorithm are developed, and I-RELIEF is one of the famous extensions. In this paper, I-RELIEF is generalized for supervised distance metric learning to yield a Mahananobis distance function. The proposed approach is justified by showing that the objective function of the generalized I-RELIEF is closely related to the expected leave-one-out nearest-neighbor classification rate. In addition, the relationships among the generalized I-RELIEF, the neighbourhood components analysis, and graph embedding are also pointed out. Experimental results on various data sets all demonstrate the superiority of the proposed approach.     

All-pass filtering in iterative learning control

In iterative learning control (ILC), it is highly desirable to have a learning compensator with a unit-gain for all frequencies, in order to avoid noise amplification and learning speed degradation during the learning process. In this paper, we show that the realization of a unit-gain compensator is straightforward in ILC, using both forward and backward filtering. As an illustrative example, a unit-gain derivative is proposed to overcome the drawbacks of the conventional derivative. The proposed scheme is equivalent to an all-pass unit-gain phase shifter; the forward filtering uses a 0.5-order derivative and the backward filtering employs a 0.5-order integral. The all-pass phase shifter is deployed in a unit-gain D-type ILC. The advantages of the unit-gain feature are demonstrated by some experimental results on a robot manipulator.     

Convex modifications to an iterative learning control law

In this paper, a predictive norm-optimal iterative learning control algorithm from Amann, Owens, and Rogers (Int. J. Control 69 (2) (1998) 203-226) is analyzed. The main new result of this is that any of the predictive inputs from the predictive algorithm can be used in the control of the plant. This results in a faster convergence rate than that obtained with the approach proposed by Amann, Owens, and Rogers. Furthermore, the nature of the convergence of this new scheme is analysed in detail in terms of the free parameters of the algorithm.     

倒立摆的可变增益迭代学习控制算法

对倒立摆系统的平衡控制问题进行研究。在建立系统数学模型的基础上,提出指数变增益迭代学习控制律,并设计了控制器。通过系统仿真实验,结果表明：与常规迭代学习控制律相比较,本文采用的方法收敛速度大大加快,系统动态性能得到很大改善。     

A note on causal and CITE iterative learning control algorithms

The convergence properties of causal and current iteration tracking error (CITE) discrete time iterative learning control (ILC) algorithms are studied using time and frequency domain convergence criteria. Of particular interest are conditions for monotone convergence, and these are evaluated using a discrete-time version of Bode's integral theorem.     

Nonlinear iterative learning control with applications to lithographic machinery

An experimental demonstration is given of (nonlinear) iterative learning control applied to a reticle stage of a lithographic wafer scanner. To limit the presence of noise in the learned forces, a nonlinear amplitude-dependent learning gain is proposed. With this gain, high-amplitude signal contents is separated from low-amplitude noise, the former being compensated by the learning algorithm. Contrary to the underlying linear design, the continuously varying trade-off between high-gain convergence rates and low-gain noise transmission demonstrates a significant improvement of the nonlinear design in achieving performance.