Learning attribute-efficiently with corrupt oracles

We study learning in a modified EXACT model, where the oracles are corrupt and only few of the presented attributes are relevant. Both modifications were already studied in the literature [Dana Angluin, Mārti?š Krikis, Learning with malicious membership queries and exceptions (extended abstract), in: COLT ’94: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM Press, 1994, pp. 56–57 [3]; Dana Angluin, Mārti?š Krikis, Robert H. Sloan, György Turán, Malicious omissions and errors in answers to membership queries, Machine Learning 28 (1997) 211–255; Laurence Bisht, Nader H. Bshouty, Lawrance Khoury, Learning with errors in answers to membership queries (extracted abstract), in: FOCS ’04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS’04, IEEE Computer Society, 2004, pp. 611–620; Nader H. Bshouty, Lisa Hellerstein, Attribute-efficient learning in query and mistake-bound models, J. Comput. System Sci. 56 (3) (1998) 310–319 [12]; Nick Littlestone, Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Machine Learning 2 (4) (1988) 285–318; Robert H. Sloan, Gyorgy Turan, Learning with queries but incomplete information (extended abstract), in: COLT ’94: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM Press, 1994, pp. 237–245 [5]], and efficient solutions were found to most of their variants. Nonetheless, their reasonable combination is yet to be studied, and integrating the existing solutions either fails or works with a complexity that can be significantly improved. In this paper we prove the equivalence of EXACT learning attribute-efficiently with and without corrupt oracles. For each of the possible scenarios we describe a generic scheme that enables learning in these cases using modifications of the standard learning algorithms. We also generalize and improve previous non-attribute-efficient algorithms for learning with corrupt oracles.     

Learning tree languages from positive examples and membership queries

We investigate regular tree languages’ exact learning from positive examples and membership queries. Input data are trees of the language to infer. The learner computes new trees from the inputs and asks the oracle whether or not they belong to the language. From the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. This paradigm was introduced by Angluin in the seminal work [D. Angluin, A note on the number of queries needed to identify regular languages, Information and Control 51 (1981) 76–87] for the case of regular word languages. Neither negative examples, equivalence queries nor counter-examples are allowed in this paradigm.     

How Many Missing Answers Can Be Tolerated by Query Learners?

We consider the model of exact learning using an equivalence oracle and an incomplete membership oracle. In this model a random subset of the learners membership queries is left unanswered. Our results are as follows. First, we analyze the obvious method for coping with missing answers: search exhaustively through all possible answer patterns associated with the unanswered queries. Thereafter, we present two specific concept classes that are efficiently learnable using an equivalence oracle and a (completely reliable) membership oracle, but are provably not polynomially learnable if the membership oracle becomes slightly incomplete. The first class demonstrates that the aforementioned method of exhaustively searching through all possible answer patterns cannot be substantially improved in general (despite its apparent simplicity). The second class demonstrates that the incomplete membership oracle can be rendered useless even if it leaves only a fraction 1/poly(n) of all queries unanswered. Finally, we present a learning algorithm for monotone DNF formulas that can cope with a relatively large fraction of missing answers (more than 60%), but is as efficient (in terms of run-time and number of queries) as the classical algorithm whose questions are always answered reliably.     

Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle

We introduce a new fault-tolerant model of algorithmic learning using an equivalence oracle and anincomplete membership oracle, in which the answers to a random subset of the learner's membership queries may be missing. We demonstrate that, with high probability, it is still possible to learn monotone DNF formulas in polynomial time, provided that the fraction of missing answers is bounded by some constant less than one. Even when half the membership queries are expected to yield no information, our algorithm will exactly identifym-term,n-variable monotone DNF formulas with an expectedO(mn ²) queries. The same task has been shown to require exponential time using equivalence queries alone. We extend the algorithm to handle some one-sided errors, and discuss several other possible error models. It is hoped that this work may lead to a better understanding of the power of membership queries and the effects of faulty teachers on query models of concept learning.     

Learning with errors in answers to membership queries

We study the learning models defined in [D. Angluin, M. Krikis, R.H. Sloan, G. Turán, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2–3) (1997) 211–255]: Learning with equivalence and limited membership queries and learning with equivalence and malicious membership queries.We show that if a class of concepts that is closed under projection is learnable in polynomial time using equivalence and (standard) membership queries then it is learnable in polynomial time in the above models. This closes the open problems in [D. Angluin, M. Krikis, R.H. Sloan, G. Turán, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2–3) (1997) 211–255].Our algorithm can also handle errors in the equivalence queries.     

Reliable agnostic learning

It is well known that in many applications erroneous predictions of one type or another must be avoided. In some applications, like spam detection, false positive errors are serious problems. In other applications, like medical diagnosis, abstaining from making a prediction may be more desirable than making an incorrect prediction. In this paper we consider different types of reliable classifiers suited for such situations. We formalize the notion and study properties of reliable classifiers in the spirit of agnostic learning (Haussler, 1992; Kearns, Schapire, and Sellie, 1994), a PAC-like model where no assumption is made on the function being learned. We then give two algorithms for reliable agnostic learning under natural distributions. The first reliably learns DNFs with no false positives using membership queries. The second reliably learns halfspaces from random examples with no false positives or false negatives, but the classifier sometimes abstains from making predictions.     

Learning languages from positive data and a finite number of queries

A computational model for learning languages in the limit from full positive data and a bounded number of queries to the teacher (oracle) is introduced and explored. Equivalence, superset, and subset queries are considered (for the latter one we consider also a variant when the learner tests every conjecture, but the number of negative answers is uniformly bounded). If the answer is negative, the teacher may provide a counterexample. We consider several types of counterexamples: arbitrary, least counterexamples, the ones whose size is bounded by the size of positive data seen so far, and no counterexamples. A number of hierarchies based on the number of queries (answers) and types of answers/counterexamples is established. Capabilities of learning with different types of queries are compared. In most cases, one or two queries of one type can sometimes do more than any bounded number of queries of another type. Still, surprisingly, a finite number of subset queries is sufficient to simulate the same number of equivalence queries when behaviourally correct learners do not receive counterexamples and may have unbounded number of errors in almost all conjectures.     

Malicious Omissions and Errors in Answers to Membership Queries

We consider two issues in polynomial-time exact learning of concepts using membership and equivalence queries: (1) errors or omissions in answers to membership queries, and (2) learning finite variants of concepts drawn from a learnable class.To study (1), we introduce two new kinds of membership queries: limited membership queries and malicious membership queries. Each is allowed to give incorrect responses on a maliciously chosen set of strings in the domain. Instead of answering correctly about a string, a limited membership query may give a special I don't know answer, while a malicious membership query may give the wrong answer. A new parameter Lis used to bound the length of an encoding of the set of strings that receive such incorrect answers. Equivalence queries are answered correctly, and learning algorithms are allowed time polynomial in the usual parameters and L. Any class of concepts learnable in polynomial time using equivalence and malicious membership queries is learnable in polynomial time using equivalence and limited membership queries; the converse is an open problem. For the classes of monotone monomials and monotone k-term DNF formulas, we present polynomial-time learning algorithms using limited membership queries alone. We present polynomial-time learning algorithms for the class of monotone DNF formulas using equivalence and limited membership queries, and using equivalence and malicious membership queries.To study (2), we consider classes of concepts that are polynomially closed under finite exceptions and a natural operation to add exception tables to a class of concepts. Applying this operation, we obtain the class of monotone DNF formulas with finite exceptions. We give a polynomial-time algorithm to learn the class of monotone DNF formulas with finite exceptions using equivalence and membership queries. We also give a general transformation showing that any class of concepts that is polynomially closed under finite exceptions and is learnable in polynomial time using standard membership and equivalence queries is also polynomial-time learnable using malicious membership and equivalence queries. Corollaries include the polynomial-time learnability of the following classes using malicious membership and equivalence queries: deterministic finite acceptors, boolean decision trees, and monotone DNF formulas with finite exceptions.     

Queries and Concept Learning

We consider the problem of using queries to learn an unknown concept. Several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries. Examples are given of efficient learning methods using various subsets of these queries for formal domains, including the regular languages, restricted classes of context-free languages, the pattern languages, and restricted types of propositional formulas. Some general lower bound techniques are given. Equivalence queries are compared with Valiant's criterion of probably approximately correct identification under random sampling.     

Automatic detection of learning styles for an e-learning system

A desirable characteristic for an e-learning system is to provide the learner the most appropriate information based on his requirements and preferences. This can be achieved by capturing and utilizing the learner model. Learner models can be extracted based on personality factors like learning styles, behavioral factors like user’s browsing history and knowledge factors like user’s prior knowledge. In this paper, we address the problem of extracting the learner model based on Felder–Silverman learning style model. The target learners in this problem are the ones studying basic science. Using NBTree classification algorithm in conjunction with Binary Relevance classifier, the learners are classified based on their interests. Then, learners’ learning styles are detected using these classification results. Experimental results are also conducted to evaluate the performance of the proposed automated learner modeling approach. The results show that the match ratio between the obtained learner’s learning style using the proposed learner model and those obtained by the questionnaires traditionally used for learning style assessment is consistent for most of the dimensions of Felder–Silverman learning style.     

A complete characterization of statistical query learning with applications to evolvability

Statistical query (SQ) learning model of Kearns is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the examples but cannot see the examples themselves (Kearns, 1998 [29]). We describe a new and simple characterization of the query complexity of learning in the SQ learning model. Unlike the previously known bounds on SQ learning (Blum, et al., 1994; Bshouty and Feldman, 2002; Yang, 2005; Balcázar, et al., 2007; Simon, 2007 [9], [11], [42], [3], [37]) our characterization preserves the accuracy and the efficiency of learning. The preservation of accuracy implies that our characterization gives the first characterization of SQ learning in the agnostic learning framework of Haussler (1992) [23] and Kearns, Schapire and Sellie (1994) [31]. The preservation of efficiency is achieved using a new boosting technique and allows us to derive a new approach to the design of evolution algorithms in Valiant?s model of evolvability (Valiant, 2009 [40]). We use this approach to demonstrate the existence of a large class of monotone evolution algorithms based on square loss performance estimation. These results differ significantly from the few known evolution algorithms and give evidence that evolvability in Valiant?s model is a more versatile phenomenon than there had been previous reason to suspect.     

On the learning of rule uncertainties and their integration into probabilistic knowledge bases

We present a natural and realistic knowledge acquisition and processing scenario. In the first phase a domain expert identifies deduction rules that he thinks are good indicators of whether a specific target concept is likely to occur. In a second knowledge acquisition phase, a learning algorithm automatically adjusts, corrects and optimizes the deterministic rule hypothesis given by the domain expert by selecting an appropriate subset of the rule hypothesis and by attaching uncertainties to them. Then, in the running phase of the knowledge base we can arbitrarily combine the learned uncertainties of the rules with uncertain factual information.Formally, we introduce the natural class of disjunctive probabilistic concepts and prove that this class is efficiently distribution-free learnable. The distribution-free learning model of probabilistic concepts was introduced by Kearns and Schapire and generalizes Valiant's probably approximately correct learning model. We show how to simulate the learned concepts in probabilistic knowledge bases which satisfy the laws of axiomatic probability theory. Finally, we combine the rule uncertainties with uncertain facts and prove the correctness of the combination under an independence assumption.     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.     

The technical framework of interactive functions for course-management systems: Students’ perceptions,uses, and evaluations

This study explores the interactivity of course-management systems (CMSs). First, this study reviews the concepts of interactivity, interactivity dimension, and interaction type on the basis of related theories and studies. Second, this study analyzes the interactive functions attributable to the six major CMSs in Taiwan colleges and universities, and re-constructs a technical framework containing five interaction types, nine interactivity dimensions, and 83 possible interactive functions. This study has found that a total of 21 interactive functions were featured in the six CMSs, while six functions identified from theories and research were not. In terms of interaction type, the results indicate that these six CMSs possessed the highest percentage of possible interactive functions for facilitating human interactions (e.g., learner–learner interaction and learner–instructor interaction), followed by learner–interface interaction and learner–self interaction, with the lowest percentage corresponding to learner–content interaction. In terms of interactivity dimension, these six CMSs seemed more likely to feature a learner-centered design approach than a system-centered one. Also, this study conducted user surveys on students’ perceptions, use, and evaluation of these interactive functions. A total of 491 valid sets of data were collected from six CMS user groups. The results indicate that, for their online learning, students considered the function of “Assignment handling” to be the most known, frequently used, and useful function. In addition, students were well familiar with, and made use of, any functions that would help them monitor or track their learning process. Students required more content-related interactive functions than were currently available in CMSs. Last, the regression results indicate that the more positively the students perceived the CMS interactivity, the usefulness of CMS for learning, and the interactive functions, the more positively these students perceived their CMSs.     

An efficient query learning algorithm for ordered binary decision diagrams

In this paper, we propose a new algorithm that exactly learns ordered binary decision diagrams (OBDDs) with a given variable ordering via equivalence and membership queries. Our algorithm uses at most n equivalence queries and at most 2n (log₂ m + 3n) membership queries, where n is the number of nodes in the target-reduced OBDD and m is the number of variables. The upper bound on the number of membership queries is smaller by a factor of O(m) compared with that for the previous best known algorithm proposed by [R. Gavaldà, D. Guijarro, Learning Ordered Binary Decision Diagrams, Proceedings of the 6th International Workshop on Algorithmic Learning Theory, 1995, pp. 228–238].     

On the Limits of Proper Learnability of Subclasses of DNF Formulas

Bshouty, Goldman, Hancock and Matar have shown that up to term DNF formulas can be properly learned in the exact model with equivalence and membership queries. Given standard complexity-theoretical assumptions, we show that this positive result for proper learning cannot be significantly improved in the exact model or the PAC model extended to allow membership queries. Our negative results are derived from two general techniques for proving such results in the exact model and the extended PAC model. As a further application of these techniques, we consider read-thrice DNF formulas. Here we improve on Aizenstein, Hellerstein, and Pitt's negative result for proper learning in the exact model in two ways. First, we show that their assumption of NP co-NP can be replaced with the weaker assumption of P NP. Second, we show that read-thrice DNF formulas are not properly learnable in the extended PAC model, assuming RP NP.     

Learning Fallible Deterministic Finite Automata

We consider the problem of learning from a fallible expert that answers all queries about a concept, but often gives incorrect answers. The expert can also be thought of as a truth table describing the concept which has been partially corrupted. In order to learn the underlying concept with arbitrarily high precision, we would like to use its structure in order to correct most of the incorrect answers. We assume that the expert's errors are uniformly and independently distributed, occur with any fixed probability strictly smaller than 1/2, and are persistent. In particular, we present a polynomial time algorithm using membership queries for correcting and learning fallible Deterministic Finite Automata under the uniform distribution.     

Agent based affective tutoring systems: A pilot study

An important trend in the development of Intelligent tutoring systems (ITSs) has been that providing the student with a more personalized and friendly environment for learning. Many researchers now feel strongly that the ITSs would significantly improve performance if they could adapt to the affective state of the learner. This idea has spawned the developing field of affective tutoring systems (ATSs): ATSs are ITSs that are able to adapt to the affective state of students. However, ATSs are not widely employed in the tutoring system market. In this paper, a survey was conducted to investigate the critical factors affecting learner’s satisfaction in ATSs based on an ATS developed by us. The results revealed that learner’s attitude toward affective computing, agent tutor’s expressiveness, emotion recognition accuracy, number of emotions recognized by agent tutor, pedagogical action and easy of the use of the system have significant influence on learner’s satisfaction. The results indicate institutions how to further strengthen the ATSs’ implementation.     

EGameFlow: A scale to measure learners’ enjoyment of e-learning games

In an effective e-learning game, the learner’s enjoyment acts as a catalyst to encourage his/her learning initiative. Therefore, the availability of a scale that effectively measures the enjoyment offered by e-learning games assist the game designer to understanding the strength and flaw of the game efficiently from the learner’s points of view. E-learning games are aimed at the achievement of learning objectives via the creation of a flow effect. Thus, this study is based on Sweetser’s & Wyeth’s framework to develop a more rigorous scale that assesses user enjoyment of e-learning games. The scale developed in the present study consists of eight dimensions: Immersion, social interaction, challenge, goal clarity, feedback, concentration, control, and knowledge improvement. Four learning games employed in a university’s online learning course “Introduction to Software Application” were used as the instruments of scale verification. Survey questionnaires were distributed to students taking the course and 166 valid samples were subsequently collected. The results showed that the validity and reliability of the scale, EGameFlow, were satisfactory. Thus, the measurement is an effective tool for evaluating the level of enjoyment provided by e-learning games to their users.     

A study of the relationships among learning styles, participation types, and performance in programming language learning supported by online forums

This study is focused on the relationships among learning styles, participation types, and learning performance for programming language learning supported by an online forum. Kolb’s learning style inventory was used in this study to determine a learner’s learning type: ‘Diverger’, ‘Assimilator’, ‘Converger’, and ‘Accommodator’. Social Learning Theory was also used to define four participation types. These types in turn were used to describe the learning associated with the use of online forums: ‘Replier’, ‘Asker’, ‘Watcher’, and ‘No activity’.A total of 144 students participated in this experiment as part of a half semester ASP.NET programming language learning courses. The course contained an online forum for supporting the students’ social activities and participation. In this study, ‘learning score’ and ‘satisfaction’ were used to measure learning performance.The results of this study were the following: (1) different learning styles were associated with significantly different learning scores and that the ‘Accommodator’ style was associated with superior learning scores; (2) participation types were also associated with significantly different learning scores and that the ‘Replier’ type is associated with superior learning scores; (3) learning satisfaction is not significantly different among the different learning styles or different participation types, but the average is significantly higher than average values (3.5) of 7-point Likert scale; (4) there is no significant association between learning styles and participation types. Explanations and discussions of these results are offered.Based on the results of this study, we propose that programming language learning, supported with online forums and students’ active participation, increases learning performance as measured by student learning scores.