Search

We present a computational model that takes into account semantics for language learning and allows us to model meaning-preserving corrections. The model is constructed with a learner and a teacher who interact in a sequence of shared situations by producing utterances intended to denote a unique object in each situation.We test our model with limited sublanguages of 10 natural languages exhibiting a variety of linguistic phenomena. The results show that learning to a high level of performance occurs after a reasonable number of interactions. Comparing the effect of a teacher who does no correction to that of a teacher who corrects whenever possible, we show that under certain conditions corrections can accelerate the rate of learning.We also define and analyze a simplified model of a probabilistic process of collecting corrections to help understand the possibilities and limitations of corrections in our setting.

In this paper we consider the problem of learning hidden independent cascade social networks using exact value injection queries. These queries involve activating and suppressing agents in the target network. We develop an algorithm that optimally learns an arbitrary social network of size n using O(n2) queries, matching the information theoretic lower bound that we prove for this problem. We also consider the case when the target social network forms a tree and show that the learning problem takes Θ(nlog(n)) queries. We also give an approximation algorithm for finding an influential set of nodes in the network, without resorting to learning its structure. Finally, we discuss some limitations of our approach, and limitations of path-based methods, when non-exact value injection queries are used.

We introduce a new model of a learner learning an unknown concept from examples with a teacher's help. In such models, “outright coding” refers to a situation in which the teacher sends the learner a representation of the concept, either directly or encoded via the examples. Previous models have used adversarial learners or adversarial teachers to try to prevent outright coding. Our model is an attempt to reflect more directly some of the reasons that outright coding is not a common mode of human learning. We model the learner as a Turing machine with oracle access to another programming system, called its “function box.” The programming system in its function box is initially unknown to the learner. The target concept is a partial recursive function and the goal of the learner is to find in its function box a function that is equal to or extends the target concept. We exhibit a class of learner/teacher pairs in which the learner can learn any partial recursive function, provided that the learner's function box is “not too much slower” than the teacher's. This result is shown not to hold if the learner's function box can contain an arbitrary acceptable programming system.

The robot localization problem requires a mobile robot to determine its current location in an environment, given some initial information about the environment. We assume that the robot’s environment is represented by an occupancy grid. The grid is a rectangle of square cells, each of which is either obstructed or unobstructed. All the edge cells of the rectangle are obstructed. The robot can occupy any unobstructed cell and can sense the obstructed/unobstructed status of each of the eight neighboring cells that share at least a corner with the current cell. The robot can move into any unobstructed cell that shares an edge with the current cell, making it the new current cell. An example of a grid is shown in Fig. 1. The robot is placed in an arbitrary unobstructed cell of a grid and moves around the grid making observations until it has determined which grid square it currently occupies. Let n be the number of unobstructed

We consider the problem of online robot navigation in an unfamiliar two-dimensional environment, using comparatively limited sensing information. In particular, the robot has local sensors to detect the proximity of obstacles and permit boundary-following, and it is able to determine its current distance and relative bearing to its final destination (via distance queries). By contrast, most previous algorithms for online navigation have assumed that the robot knows its exact current position. Because determining exact location is prone to error that accumulates over time, the usefulness of such algorithms may be limited. In contrast, distance queries give less information, but the accuracy of each query is independent of the number of queries, which means distance queries can be more robust. We formally define our model and give new, efficient navigation algorithms and lower bounds for this setting.

We present an overview of the results obtained with a computational model that takes into account semantics and corrections for language learning. This model is constructed with a learner and a teacher who interact in a sequence of shared situations. The model was tested with limited sublanguages of 10 natural languages in a common domain of situations.

The phenomenon of meaning-preserving corrections given by an adult to a child involves several aspects: (1) the child produces an incorrect utterance, which the adult nevertheless understands, (2) the adult produces a correct utterance with the same meaning and (3) the child recognizes the adult utterance as having the same meaning as its previous utterance, and takes that as a signal that its previous utterance is not correct according to the adult grammar. An adequate model of this phenomenon must incorporate utterances and meanings, account for how the child and adult can understand each other's meanings, and model how meaning-preserving corrections interact with the child's increasing mastery of language production. In this paper we are concerned with how a learner who has learned to comprehend utterances might go about learning to produce them. We consider a model of language comprehension and production based on finite sequential and subsequential transducers. Utterances are modeled as finite sequences of words and meanings as finite sequences of predicates. Comprehension is interpreted as a mapping of utterances to meanings and production as a mapping of meanings to utterances. Previous work (Castellanos et al., 1993; Pieraccini et al., 1993) has applied subsequential transducers and the OSTIA algorithm to the problem of learning to comprehend language; here we apply them to the problem of learning to produce language. For ten natural languages and a limited domain of geometric shapes and their properties and relations we define sequential transducers to produce pairs consisting of an utterance in that language and its meaning. Using this data we empirically explore the properties of the OSTIA and DD-OSTIA algorithms for the tasks of learning comprehension and production in this domain, to assess whether they may provide a basis for a model of meaning-preserving corrections.

We present a simple computational model that includes semantics for language learning, as motivated by readings in the literature of children's language acquisition and by a desire to incorporate a robust notion of semantics in the field of Grammatical Inference. We argue that not only is it more natural to take into account semantics, but also that semantic information can make learning easier, and can give us a better understanding of the relation between positive data and corrections. We propose a model of meaning and denotation using finite-state transducers, motivated by an example domain of geometric shapes and their properties and relations. We give an algorithm to learn a meaning function and prove that it finitely converges to a correct result under a specific set of assumptions about the transducer and examples.

In this paper we consider the problem of learning hidden independent cascade social networks using exact value injection queries. These queries involve activating and suppressing agents in the target network. We develop an algorithm that optimally learns an arbitrary social network of size nusing O(n2) queries, matching the information theoretic lower bound we prove for this problem. We also consider the case when the target social network forms a tree and show that the learning problem takes i¾?(nlog(n)) queries. We also give an approximation algorithm for finding an influential set of nodes in the network, without resorting to learning its structure. Finally, we discuss some limitations of our approach, and limitations of path-based methods, when non-exact value injection queries are used.

Our formal models of learning seem to overestimate how hard it is to learn some kinds of things, including grammars. One possible reason for this is that our models generally do not represent learning a concept as an incremental addition to a rich collection of related concepts. This raises the question of how to make a good model of a “rich collection of related concepts.” Rather than start by trying to make a general model, or adapting existing formalisms (e.g., logical theories) for the purpose, I have undertaken an extended look at a particular domain, namely mathematics. Mathematics certainly qualifies as a rich collection of related concepts, and has the advantage of thousands of years of effort devoted to improving its representations and clarifying its interconnections. This talk will present some of the issues I have encountered, and will probably consist of more questions than answers.

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 prepositional formulas. Some general lower bound techniques are given. Equivalence queries are compared with Valiant's criterion of probably approximately correct identification under random sampling.

The basic question addressed in this paper is: how can a learning algorithm cope with incorrect training examples? Specifically, how can algorithms that produce an “approximately correct” identification with “high probability” for reliable data be adapted to handle noisy data? We show that when the teacher may make independent random errors in classifying the example data, the strategy of selecting the most consistent rule for the sample is sufficient, and usually requires a feasibly small number of examples, provided noise affects less than half the examples on average. In this setting we are able to estimate the rate of noise using only the knowledge that the rate is less than one half. The basic ideas extend to other types of random noise as well. We also show that the search problem associated with this strategy is intractable in general. However, for particular classes of rules the target rule may be efficiently identified if we use techniques specific to that class. For an important class of formulas – the k-CNF formulas studied by Valiant – we present a polynomial-time algorithm that identifies concepts in this form when the rate of classification errors is less than one half.

Intuitively, the more a machine knows the more it can learn. This intuition is formalized in a recursion theoretic framework. A formal definition of what it means for a machine to learn a finite sequence of recursive functions is presented. We prove that there are sets of sequences S, and a sequence 〈ƒ1, ƒ2, …, ƒn〉ϵ S such that in order to learn a program for ƒi a machine must necessarily know programs for ƒ1, …, ƒi−1. Also investigated is the simultaneous inference of programs for a finite set of recursive functions.