Search

Abstract: Known algorithms for learning PDFA can only be shown to run in time polynomial in the so-called distinguishability of the target machine, besides the number of states and the usual accuracy and confidence parameters. We show that the dependence on is necessary in the worst case for every algorithm whose structure resembles existing ones. As a technical tool, a new variant of Statistical Queries termed -queries is defined. We show how to simulate -queries using classical Statistical Queries and show that known PAC algorithms for learning PDFA are in fact statistical query algorithms. Our results include a lower bound: every algorithm to learn PDFA with queries using a reasonable tolerance must make queries for every . Finally, an adaptive algorithm that PAC-learns w.r.t. another measure of complexity is described. This yields better efficiency in many cases, while retaining the same inevitable worst-case behavior. Our algorithm requires fewer input parameters than previously existing ones, and has a better sample bound. [Copyright &y& Elsevier]

Abstract: Partial-monitoring games constitute a mathematical framework for sequential decision making problems with imperfect feedback: the learner repeatedly chooses an action, the opponent responds with an outcome, and then the learner suffers a loss and receives a feedback signal, both of which are fixed functions of the action and the outcome. The goal of the learner is to minimize his total cumulative loss. We make progress toward the classification of these games based on their minimax expected regret. Namely, we classify almost all games with two outcomes and a finite number of actions: we show that their minimax expected regret is either zero, , , or , and we give a simple and efficiently computable classification of these four classes of games. Our hope is that the result can serve as a stepping stone toward classifying all finite partial-monitoring games. [Copyright &y& Elsevier]

Abstract: Iterative learning (-learning) is a Gold-style learning model in which each of a learner’s output conjectures may depend only upon the learner’s current conjecture and the current input element. Two extensions of the -learning model are considered, each of which involves parallelism. The first is to run, in parallel, distinct instantiations of a single learner on each input element. The second is to run, in parallel, individual learners incorporating the first extension, and to allow the learners to communicate their results. In most contexts, parallelism is only a means of improving efficiency. However, as shown herein, learners incorporating the first extension are more powerful than -learners, and, collective learners resulting from the second extension increase in learning power as increases. Attention is paid to how one would actually implement a learner incorporating each extension. Parallelism is the underlying mechanism employed. [Copyright &y& Elsevier]

We consider a variant of Gold’s learning paradigm where a learner receives as input 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 different languages, can produce grammars covering all input languages, but cannot produce grammars covering input languages for any . We also consider a variant of this task, where each of the output grammars may not cover more than input languages. Our main results indicate that the major factor affecting classification capabilities is the difference between the number of input languages and the number 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 (the number of input languages), (number of output grammars), and (bound on the number of languages represented by each output grammar). This picture includes a combinatorial characterization of classification capabilities for the parameters of certain types. [Copyright &y& Elsevier]