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.     

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.     

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.     

U-shaped, iterative, and iterative-with-counter learning

This paper solves an important problem left open in the literature by showing that U-shapes are unnecessary in iterative learning from positive data. A U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Iterative learning is a Gold-style learning model in which each of a learner’s output conjectures depends only upon the learner’s most recent conjecture and input element. Previous results had shown, for example, that U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct learning. Work on the aforementioned problem led to the consideration of an iterative-like learning model, in which each of a learner’s conjectures may, in addition, depend upon the number of elements so far presented to the learner. Learners in this new model are strictly more powerful than traditional iterative learners, yet not as powerful as full explanatory learners. Can any class of languages learnable in this new model be learned without U-shapes? For now, this problem is left open.     

Learning from natural instructions

Machine learning is traditionally formalized and investigated as the study of learning concepts and decision functions from labeled examples, requiring a representation that encodes information about the domain of the decision function to be learned. We are interested in providing a way for a human teacher to interact with an automated learner using natural instructions, thus allowing the teacher to communicate the relevant domain expertise to the learner without necessarily knowing anything about the internal representations used in the learning process. In this paper we suggest to view the process of learning a decision function as a natural language lesson interpretation problem, as opposed to learning from labeled examples. This view of machine learning is motivated by human learning processes, in which the learner is given a lesson describing the target concept directly and a few instances exemplifying it. We introduce a learning algorithm for the lesson interpretation problem that receives feedback from its performance on the final task, while learning jointly (1) how to interpret the lesson and (2) how to use this interpretation to do well on the final task. traditional machine learning by focusing on supplying the learner only with information that can be provided by a task expert. We evaluate our approach by applying it to the rules of the solitaire card game. We show that our learning approach can eventually use natural language instructions to learn the target concept and play the game legally. Furthermore, we show that the learned semantic interpreter also generalizes to previously unseen instructions.     

Affective learning: improving engagement and enhancing learning with affect-aware feedback

This paper describes the design and ecologically valid evaluation of a learner model that lies at the heart of an intelligent learning environment called iTalk2Learn. A core objective of the learner model is to adapt formative feedback based on students’ affective states. Types of adaptation include what type of formative feedback should be provided and how it should be presented. Two Bayesian networks trained with data gathered in a series of Wizard-of-Oz studies are used for the adaptation process. This paper reports results from a quasi-experimental evaluation, in authentic classroom settings, which compared a version of iTalk2Learn that adapted feedback based on students’ affective states as they were talking aloud with the system (the affect condition) with one that provided feedback based only on the students’ performance (the non-affect condition). Our results suggest that affect-aware support contributes to reducing boredom and off-task behavior, and may have an effect on learning. We discuss the internal and ecological validity of the study, in light of pedagogical considerations that informed the design of the two conditions. Overall, the results of the study have implications both for the design of educational technology and for classroom approaches to teaching, because they highlight the important role that affect-aware modelling plays in the adaptive delivery of formative feedback to support learning.     

Results on memory-limited U-shaped learning

U-shaped learning is a learning behaviour in which the learner first learns a given target behaviour, then unlearns it and finally relearns it. Such a behaviour, observed by psychologists, for example, in the learning of past-tenses of English verbs, has been widely discussed among psychologists and cognitive scientists as a fundamental example of the non-monotonicity of learning. Previous theory literature has studied whether or not U-shaped learning, in the context of Gold’s formal model of learning languages from positive data, is necessary for learning some tasks.It is clear that human learning involves memory limitations. In the present paper we consider, then, the question of the necessity of U-shaped learning for some learning models featuring memory limitations. Our results show that the question of the necessity of U-shaped learning in this memory-limited setting depends on delicate tradeoffs between the learner’s ability to remember its own previous conjecture, to store some values in its long-term memory, to make queries about whether or not items occur in previously seen data and on the learner’s choice of hypotheses space.     

Variations on U-shaped learning

The paper deals with the following problem: is returning to wrong conjectures necessary to achieve full power of algorithmic learning? Returning to wrong conjectures complements the paradigm of U-shaped learning when a learner returns to old correct conjectures. We explore our problem for classical models of learning in the limit from positive data: explanatory learning (when a learner stabilizes in the limit on a correct grammar) and behaviourally correct learning (when a learner stabilizes in the limit on a sequence of correct grammars representing the target concept). In both cases we show that returning to wrong conjectures is necessary to achieve full learning power. In contrast, one can modify learners (without losing learning power) such that they never show inverted U-shaped learning behaviour, that is, never return to old wrong conjecture with a correct conjecture in-between. Furthermore, one can also modify a learner (without losing learning power) such that it does not return to old “overinclusive” conjectures containing non-elements of the target language. We also consider our problem in the context of vacillatory learning (when a learner stabilizes on a finite number of correct grammars) and show that each of the following four constraints is restrictive (that is, reduces learning power): the learner does not return to old wrong conjectures; the learner is not inverted U-shaped; the learner does not return to old overinclusive conjectures; the learner does not return to old overgeneralizing conjectures. We also show that learners that are consistent with the input seen so far can be made decisive: on any text, they do not return to any old conjectures—wrong or right.     

Motivation in online learning: Testing a model of self-determination theory

As high attrition rates becomes a pressing issue of online learning and a major concern of online educators, it is important to investigate online learner motivation, including its antecedents and outcomes. Drawing on Deci and Ryan’s self-determination theory, this study proposed and tested a model for online learner motivation in two online certificate programs (N = 262). Results from structural equation modeling provided evidence for the mediating effect of need satisfaction between contextual support and motivation/self-determination; however, motivation/self-determination failed to predict learning outcomes. Additionally, this study supported SDT’s main theorizing that intrinsic motivation, extrinsic motivation, and amotivation are distinctive constructs, and found that the direct effect and indirect effects of contextual support exerted opposite impacts on learning outcomes. Implications for online learner support were discussed.     

Uncountable automatic classes and learning

In this paper we consider uncountable classes recognizable by ω-automata and investigate suitable learning paradigms for them. In particular, the counterparts of explanatory, vacillatory and behaviourally correct learning are introduced for this setting. Here the learner reads in parallel the data of a text for a language L from the class plus an ω-index α and outputs a sequence of ω-automata such that all but finitely many of these ω-automata accept the index α if and only if α is an index for L.It is shown that any class is behaviourally correct learnable if and only if it satisfies Angluin’s tell-tale condition. For explanatory learning, such a result needs that a suitable indexing of the class is chosen. On the one hand, every class satisfying Angluin’s tell-tale condition is vacillatorily learnable in every indexing; on the other hand, there is a fixed class such that the level of the class in the hierarchy of vacillatory learning depends on the indexing of the class chosen.We also consider a notion of blind learning. On the one hand, a class is blind explanatorily (vacillatorily) learnable if and only if it satisfies Angluin’s tell-tale condition and is countable; on the other hand, for behaviourally correct learning, there is no difference between the blind and non-blind version.This work establishes a bridge between the theory of ω-automata and inductive inference (learning theory).     

Refuting learning revisited

We consider, within the framework of inductive inference, the concept of refuting learning as introduced by Mukouchi and Arikawa, where the learner is not only required to learn all concepts in a given class but also has to explicitly refute concepts outside the class.In the first part of the paper, we consider learning from text and introduce a concept of limit-refuting learning that is intermediate between refuting learning and reliable learning. We give characterizations for these concepts and show some results about their relative strength and their relation to confident learning.In the second part of the paper we consider learning from texts that for some k contain all positive Π_k-formulae that are valid in the standard structure determined by the set to be learned. In this model, the following results are shown. For the language with successor, any countable axiomatizable class can be limit-refuting learned from Π₁-texts. For the language with successor and order, any countable axiomatizable class can be reliably learned from Π₁-texts and can be limit-refuting learned from Π₂-texts, whereas the axiomatizable class of all finite sets cannot be limit-refuting learned from Π₁-texts. For the full language of arithmetic, which contains in addition plus and times, for any even k there is an axiomatizable class that can be limit-refuting learned from Π_k+1-texts but not from Π_k-texts. A similar result with k+3 in place of k+1 holds with respect to the language of Presburger's arithmetic.     

The Strength of Weak Learnability

This paper addresses the problem of improving the accuracy of an hypothesis output by a learning algorithm in the distribution-free (PAC) learning model. A concept class is learnable (or strongly learnable) if, given access to a source of examples of the unknown concept, the learner with high probability is able to output an hypothesis that is correct on all but an arbitrarily small fraction of the instances. The concept class is weakly learnable if the learner can produce an hypothesis that performs only slightly better than random guessing. In this paper, it is shown that these two notions of learnability are equivalent.A method is described for converting a weak learning algorithm into one that achieves arbitrarily high accuracy. This construction may have practical applications as a tool for efficiently converting a mediocre learning algorithm into one that performs extremely well. In addition, the construction has some interesting theoretical consequences, including a set of general upper bounds on the complexity of any strong learning algorithm as a function of the allowed error .     

Zone analysis: a visualization framework for classification problems

There have been large attempts to adopt the bias-variance framework from the regression problems to the classification problems. However, recently, it has been shown that only non-straightforward extensions exist for classification problems. In this paper, we present an alternative visualization framework for classification problems called zone analysis. Our zone analysis framework partly extends the bias-variance idea; instead of decomposing an error into two parts, i.e. the biased and unbiased components, our framework decomposes the error into K components. While bias-variance information is still contained in our framework, our framework provides interesting observations which are not obviously seen in the previous bias-variance framework, e.g. a prejudice behavior of the bagging algorithm to various unbiased instances. Our framework is suitable for visualizing an effect of context changes on learning performance. The type of context changes which we primarily investigate in the paper is “a change from a base learner to an ensemble learner such as bagging, adaboost, arc-x4 and multi-boosting”.     

The effects of assessment design on academic dishonesty,learner engagement,and certification rates in MOOCs

Background

Massive Open Online Courses (MOOCs) have touted the idea of democratizing education, but soon enough, this utopian idea collided with the reality of finding sustainable business models. In addition, the promise of harnessing interactive and social web technologies to promote meaningful learning was only partially successful. And finally, studies demonstrated that many learners exploit the anonymity and feedback to earn certificates unethically. Thus, establishing MOOC pedagogical models that balance open access, meaningful learning, and trustworthy assessment remains a challenge that is crucial for the field to achieve its goals.

Objectives

This study analysed the influence of an MOOC assessment model, denoted the Competency Exam (CE), on learner engagement, the level of cheating, and certification rates. At its core, this model separates learning from for-credit assessment, and it was introduced by the MITx Biology course team in 2016.

Methods

We applied a learning analytics methodology to the clickstream data of the verified learners (N = 559) from four consecutive runs of an Introductory Biology MOOC offered through edX. The analysis used novel algorithms for measuring the level of cheating and learner engagement, which were developed in the previous studies.

Results and Conclusions

On the positive side, the CE model reduced cheating and did not reduce learner engagement with the main learning materials – videos and formative assessment items. On the negative side, it led to procrastination, and certification rates were lower.

Implications

First, the results shed light on the fundamental connection between incentive design and learner behaviour. Second, the CE provides MOOC designers with an ‘analytically verified’ model to reduce cheating without compromising on open access. Third, our methodology provides a novel means for measuring cheating and learner engagement in MOOCs.

     

Iterative learning from positive data and negative counterexamples

A model for learning in the limit is defined where a (so-called iterative) learner gets all positive examples from the target language, tests every new conjecture with a teacher (oracle) if it is a subset of the target language (and if it is not, then it receives a negative counterexample), and uses only limited long-term memory (incorporated in conjectures). Three variants of this model are compared: when a learner receives least negative counterexamples, the ones whose size is bounded by the maximum size of input seen so far, and arbitrary ones. A surprising result is that sometimes absence of bounded counterexamples can help an iterative learner whereas arbitrary counterexamples are useless. We also compare our learnability model with other relevant models of learnability in the limit, study how our model works for indexed classes of recursive languages, and show that learners in our model can work in non-U-shaped way—never abandoning the first right conjecture.     

Learning Changing Concepts by Exploiting the Structure of Change

This paper examines learning problems in which the target function is allowed to change. The learner sees a sequence of random examples, labelled according to a sequence of functions, and must provide an accurate estimate of the target function sequence. We consider a variety of restrictions on how the target function is allowed to change, including infrequent but arbitrary changes, sequences that correspond to slow walks on a graph whose nodes are functions, and changes that are small on average, as measured by the probability of disagreements between consecutive functions. We first study estimation, in which the learner sees a batch of examples and is then required to give an accurate estimate of the function sequence. Our results provide bounds on the sample complexity and allowable drift rate for these problems. We also study prediction, in which the learner must produce online a hypothesis after each labelled example and the average misclassification probability over this hypothesis sequence should be small. Using a deterministic analysis in a general metric space setting, we provide a technique for constructing a successful prediction algorithm, given a successful estimation algorithm. This leads to sample complexity and drift rate bounds for the prediction of changing concepts.     

Learning all subfunctions of a function

Sublearning, a model for learning of subconcepts of a concept, is presented. Sublearning a class of total recursive functions informally means to learn all functions from that class together with all of their subfunctions. While in language learning it is known to be impossible to learn any infinite language together with all of its sublanguages, the situation changes for sublearning of functions. Several types of sublearning are defined and compared to each other as well as to other learning types. For example, in some cases, sublearning coincides with robust learning. Furthermore, whereas in usual function learning there are classes that cannot be learned consistently, all sublearnable classes of some natural types can be learned consistently. Moreover, the power of sublearning is characterized in several terms, thereby establishing a close connection to measurable classes and variants of this notion. As a consequence, there are rich classes which do not need any self-referential coding for sublearning them.     

Attentiveness assessment in learning based on fuzzy logic analysis

Learner attention affects learning efficiency. However, in many classes, teachers cannot assess the degree of attention of every learner. When a teacher is capable of addressing inattentive learners immediately, he can avoid situations in which learners are inattentive. Many studies have analyzed driver attentiveness by the applying of image detection technologies. If this mechanism can be applied to in-class learning, it will help teachers keep learners attentive, and reduce teacher load during class. This study mainly applies fuzzy logic analysis of learner facial images when participating in class. Two fuzzy logic algorithms are proposed to determine the level of inattention by measuring the leaving, drowsiness, head turning and no motion. Applying fuzzy logic can prevent erroneous judgments associated with a single term, and help teachers deal with learner attentiveness. The simulation works are carried to evaluate the effect of the proposed system under various conditions. The simulation results indicated that the proposed system is effective for detecting of learner attentiveness in class.