Search

This paper extends the traditional inductive logic programming (ILP) framework to a ψ-term capable ILP framework. Aït-Kaci's ψ-terms have interesting and significant properties for markedly widening applicable areas of ILP. For example, ψ-terms allow partial descriptions of information, generalization and specialization of sorts (or types) placed instead of function symbols, and abstract descriptions of data using sorts; they have comparable representation power to feature structures used in natural language processing. We have developed an algorithm that learns logic programs based on -terms, made possible by a bottom-up approach employing the least general generalization (lgg) extended for ψ-terms. As an area of application, we have selected information extraction (IE) tasks in which sort information is crucial in deciding the generality of IE rules. Experiments were conducted on a set of test examples and background knowledge consisting of case frames of newspaper articles. The results showed high precision and recall rates for learned rules for the IE tasks. [ABSTRACT FROM AUTHOR]

Flattening is a method to make a definite clause function-free. For a definite clause C, flattening replaces every occurrence of a term f(t1. . . , tn) in C with a new variable v and adds an atom pf (t1. . . , tn, v) with the associated predicate symbol pf with f to the body of C. Here, we denote the resulting function-free definite clause from C by flat(C). In this paper, we discuss the relationship between flattening and implication. For a definite program П and a definite clause D, it is known that if flat(П) ⊨ flat(D) then П ⊨ D, where flat(П) is the set of flat(C) for each C ∈ П. First, we show that the converse of this statement does not hold even if П = {C}, that is, there exist definite clauses C and D such that C ⊨ D but flat(C) ⊭ flat(D). Furthermore, we investigate the conditions of C and D satisfying that C ⊨ D if and only if flat(C) ⊨ flat(D). Then, we show that, if (1) C is not self-resolving and D is not tautological, (2) D is not ambivalent, or (3) C is singly recursive, then the statement holds. [ABSTRACT FROM AUTHOR]

The basis of inductive learning is the process of generating and refuting hypotheses. Natural approaches to this form of learning assume that a data item that causes refutation of one hypothesis opens the way for the introduction of a new (for now unrefuted) hypothesis, and so such data items have attracted the most attention. Data items that do not cause refutation of the current hypothesis have until now been largely ignored in these processes, but in practical learning situations they play the key role of corroborating those hypotheses that they do not refute. We formalise a version of K.R. Popper's concept of degree of corroboration for inductive inference and utilise it in an inductive learning procedure which has the natural behaviour of outputting the most strongly corroborated (non-refuted) hypothesis at each stage. We demonstrate its utility by providing characterisations of several of the commonest identification types in the case of learning from text over class-preserving hypothesis spaces and proving the existence of canonical learning strategies for these types. In many cases we believe that these characterisations make the relationships between these types clearer than the standard characterisations. The idea of learning with corroboration therefore provides a unifying approach for the field. [ABSTRACT FROM AUTHOR]

Learning in the limit deals mainly with the question of what can be learned, but not very often with the question of how fast. The purpose of this paper is to develop a learning model that stays very close to Gold's model, but enables questions on the speed of convergence to be answered. In order to do this, we have to assume that positive examples are generated by some stochastic model. If the stochastic model is fixed (measure one learning), then all recursively enumerable sets are identifiable, while straying greatly from Gold's model. In contrast, we define learning from random text as identifying a class of languages for every stochastic model where examples are generated independently and identically distributed. As it turns out, this model stays close to learning in the limit. We compare both models keeping several aspects in mind, particularly when restricted to several strategies and to the existence of locking sequences. Lastly, we present some results on the speed of convergence: In general, convergence can be arbitrarily slow, but for recursive learners, it cannot be slower than some magic function. Every language can be learned with exponentially small tail bounds, which are also the best possible. All results apply fully to Gold-style learners, since his model is a proper subset of learning from random text. [ABSTRACT FROM AUTHOR]

This paper provides a systematic study of incremental learning from noise-free and from noisy data, thereby distinguishing between learning from only positive data and from both positive and negative data. Our study relies on the notion of noisy data introduced in [22]. The basic scenario, named iterative learning, is as follows. In every learning stage, an algorithmic learner takes as input one element of an information sequence for a target concept and its previously made hypothesis and outputs a new hypothesis. The sequence of hypotheses has to converge to a hypothesis describing the target concept correctly. We study the following refinements of this scenario. Bounded example-memory inference generalizes iterative inference by allowing an iterative learner to additionally store an a priori bounded number of carefully chosen data elements, while feedback learning generalizes it by allowing the iterative learner to additionally ask whether or not a particular data element did already appear in the data seen so far. For the case of learning from noise-free data, we show that, where both positive and negative data are available, restrictions on the accessibility of the input data do not limit the learning capabilities if and only if the relevant iterative learners are allowed to query the history of the learning process or to store at least one carefully selected data element. This insight nicely contrasts the fact that, in case only positive data are available, restrictions on the accessibility of the input data seriously affect the capabilities of all types of incremental learning (cf. [18]). For the case of learning from noisy data, we present characterizations of all kinds of incremental learning in terms being independent from learning theory. The relevant conditions are purely structural ones. Surprisingly, where learning from only noisy positive data and from both noisy positive and negative data, iterative learners are already exactly as powerful as unconstrained learning devices. [ABSTRACT FROM AUTHOR]

This paper presents a computation of the Vγ dimension for regression in bounded subspaces of Reproducing Kernel Hilbert Spaces (RKHS) for the Support Vector Machine (SVM) regression ε-insensitive loss function Lε, and general Lp loss functions. Finiteness of the Vγ dimension is shown, which also proves uniform convergence in probability for regression machines in RKHS subspaces that use the Lε or general Lp loss functions. This paper presents a novel proof of this result. It also presents a computation of an upper bound of the Vγ dimension under some conditions, that leads to an approach for the estimation of the empirical Vγ dimension given a set of training data. [ABSTRACT FROM AUTHOR]

This paper derives the Vapnik Chervonenkis dimension of several natural subclasses of pattern languages. For classes with unbounded VC-dimension, an attempt is made to quantify the "rate of growth" of VC-dimension for these classes. This is achieved by computing, for each n, size of the "smallest" witness set of n elements that is shattered by the class. The paper considers both erasing (empty substitutions allowed) and nonerasing (empty substitutions not allowed) pattern languages. For erasing pattern languages, optimal bounds for this size — within polynomial order — are derived for the case of 1 variable occurrence and unary alphabet, for the case where the number of variable occurrences is bounded by a constant, and the general case of all pattern languages. The extent to which these results hold for nonerasing pattern languages is also investigated. Some results that shed light on efficient learning of subclasses of pattern languages are also given. [ABSTRACT FROM AUTHOR]

We prove a new combinatorial characterization of polynomial learnability from equivalence queries, and state some of its consequences relating the learnability of a class with the learnability via equivalence and membership queries of its subclasses obtained by restricting the instance space. Then we propose and study two models of query learning in which there is a probability distribution on the instance space, both as an application of the tools developed from the combinatorial characterization and as models of independent interest. [ABSTRACT FROM AUTHOR]

The neuroidal tabula rasa (NTR) as a hypothetical device which is capable of performing tasks related to cognitive processes in the brain was introduced by L.G. Valiant in 1994. Neuroidal nets represent a computational model of the NTR. Their basic computational element is a kind of a programmable neuron called neuroid. Essentially it is a combination of a standard threshold element with a mechanism that allows modification of the neuroid's computational behaviour. This is done by changing its state and the settings of its weights and of threshold in the course of computation. The computational power of an NTR crucially depends both on the functional properties of the underlying update mechanism that allows changing of neuroidal parameters and on the universe of allowable weights. We will define instances of neuroids for which the computational power of the respective finite-size NTR ranges from that of finite automata, through Turing machines, upto that of a certain restricted type of BSS machines that possess super-Turing computational power. The latter two results are surprising since similar results were known to hold only for certain kinds of analog neural networks. [ABSTRACT FROM AUTHOR]

The statistical asymptotic theory is often used in theoretical results in computational and statistical learning theory. It describes the limiting distribution of the maximum likelihood estimator (MLE) as an normal distribution. However, in layered models such as neural networks, the regularity condition of the asymptotic theory is not necessarily satisfied. The true parameter is not identifiable, if the target function can be realized by a network of smaller size than the size of the model. There has been little known on the behavior of the MLE in these cases of neural networks. In this paper, we analyze the expectation of the generalization error of three-layer linear neural networks, and elucidate a strange behavior in unidentifiable cases. We show that the expectation of the generalization error in the unidentifiable cases is larger than what is given by the usual asymptotic theory, and dependent on the rank of the target function. [ABSTRACT FROM AUTHOR]

This paper clarifies learning efficiency of a non-regular parametric model such as a neural network whose true parameter set is an analytic variety with singular points. By using Sato's b-function we rigorously prove that the free energy or the Bayesian stochastic complexity is asymptotically equal to λ1 log n − (m1 − 1) log log n+constant, where λ1 is a rational number, m1 is a natural number, and n is the number of training samples. Also we show an algorithm to calculate λ1 and m1 based on the resolution of singularity. In regular models, 2λ1 is equal to the number of parameters and m1 = 1, whereas in non-regular models such as neural networks, 2λ1 is smaller than the number of parameters and m1 ≥ 1. [ABSTRACT FROM AUTHOR]

We are concerned with the problem of sequential prediction using a given hypothesis class of continuously-many prediction strategies. An effective performance measure is the minimax relative cumulative loss (RCL), which is the minimum of the worst-case difference between the cumulative loss for any prediction algorithm and that for the best assignment in a given hypothesis class. The purpose of this paper is to evaluate the minimax RCL for general continuous hypothesis classes under general losses. We first derive asymptotical upper and lower bounds on the minimax RCL to show that they match (k/2c) lnm within error of o(lnm) where k is the dimension of parameters for the hypothesis class, m is the sample size, and c is the constant depending on the loss function. We thereby show that the cumulative loss attaining the minimax RCL asymptotically coincides with the extended stochastic complexity (ESC), which is an extension of Rissanen's stochastic complexity (SC) into the decision-theoretic scenario. We further derive non-asymptotical upper bounds on the minimax RCL both for parametric and nonparametric hypothesis classes. We apply the analysis into the regression problem to derive the least worst-case cumulative loss bounds to date. [ABSTRACT FROM AUTHOR]

Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, we briefly survey theoretical work on boosting including analyses of AdaBoost's training error and generalization error, connections between boosting and game theory, methods of estimating probabilities using boosting, and extensions of AdaBoost for multiclass classification problems. Some empirical work and applications are also described. [ABSTRACT FROM AUTHOR]

Designing the representation languages for the input and output of a learning algorithm is the hardest task within machine learning applications. Transforming the given representation of observations into a well-suited language LE may ease learning such that a simple and efficient learning algorithm can solve the learning problem. Learnability is defined with respect to the representation of the output of learning, LH. If the predictive accuracy is the only criterion for the success of learning, the choice of LH means to find the hypothesis space with most easily learnable concepts, which contains the solution. Additional criteria for the success of learning such as comprehensibility and embeddedness may ask for transformations of LH such that users can easily interpret and other systems can easily exploit the learning results. Designing a language LH that is optimal with respect to all the criteria is too difficult a task. Instead, we design families of representations, where each family member is well suited for a particular set of requirements, and implement transformations between the representations. In this paper, we discuss a representation family of Horn logic. Work on tailoring representations is illustrated by a robot application. [ABSTRACT FROM AUTHOR]

People with severe speech and motor impairments (SSMI) can often use augmentative communication devices to help them communicate. While these devices can provide speech synthesis or text output, the rate of communication is typically very slow. Consequently, augmentative communication users often develop telegraphic patterns of language usage. A natural language processing technique termed compansion (compression-expansion) has been developed that expands uninflected content words (i.e., compressed or telegraphic utterances) into syntactically and semantically well-formed sentences. While originally designed as a rate enhancement technique, compansion may also be viewed as a potential tool to support English literacy for augmentative communication users. Accurate grammatical feedback from ill-formed inputs might be very beneficial in the learning process. However, the problems of dealing with inherently ambiguous errors and multiple corrections are not trivial. This paper proposes the addition of an adaptive user language model as a way to address some of these difficulties. It also discusses a possible implementation strategy using grammatical mal-rules for a prototype application that uses the compansion technique. [ABSTRACT FROM AUTHOR]

Many people with severe speech and motor impairments make use of augmentative and alternative communication (AAC) systems. These systems can employ a variety of techniques to organize stored words, phrases, and sentences, and to make them available to the user. It is argued in this chapter that an AAC system should make better use of the regularities in an individual's conversational experiences and the expectations that the individual normally brings into a conversational context. An interface and methodology are described for organizing and retrieving sentences appropriate to a particular conversational context, sentences that were possibly developed from earlier conversations. These conversations are represented according to the schema structures discussed by Schank as a model for memory and cognitive organization [16]. The interface allows the user to proceed with minimal effort through conversations that follow the schema closely, and facilitates the derivation of new schemata when the conversation diverges from existing ones. This interface, called SchemaTalk, is intended to operate in parallel with and to complement a user's existing augmentative communication system. The results of preliminary investigations into the effectiveness of the interface and methodology have been encouraging; further investigations are planned. Of interest for future study is how the use of schematized text might influence the way that augmented communicators are perceived by their conversational partners. Possible design modifications to improve the usability of the interface are also under investigation. [ABSTRACT FROM AUTHOR]

In this paper, we present a prototype translation system named SYUWAN which translates Japanese into Japanese sign language. One of the most important problems in this task is that there are very few entries in a sign language dictionary compared with a Japanese one. To solve this problem, when the original input word does not exist in a sign language dictionary SYUWAN applies several techniques to find a similar word from a Japanese dictionary and substitutes this word for the original word. As the result, SYUWAN can translate up to 82% of words which are morphologically analyzed. [ABSTRACT FROM AUTHOR]

Modern wearable computer designs package workstation level performance in systems small enough to be worn as clothing. These machines enable technology to be brought where it is needed the most for the handicapped: everyday mobile environments. This paper describes a research effort to make a wearable computer that can recognize (with the possible goal of translating) sentence level American Sign Language (ASL) using only a baseball cap mounted camera for input. Current accuracy exceeds 97% per word on a 40 word lexicon. [ABSTRACT FROM AUTHOR]

This paper considers ways in which a person can cue and constrain an artificial agent's attention to salient features. In one experiment, a person uses gestures to direct an otherwise autonomous robot hand through a known task. Each gesture instantiates the key spatial and intentional features for the task at that moment in time. In a second hypothetical task, a person uses speech and gesture to assist an "intelligent room≓ in learning to recognize the objects in its environment. Both experiments use a system of dynamic reference, termed deictic, to bind the robot's perception and action to salient task variables. [ABSTRACT FROM AUTHOR]

EagleEyes is a system that allows the user to control the computer through electrodes placed on the head. For people without disabilities it takes 15 to 30 minutes to learn to control the cursor sufficiently to spell out a message with an onscreen keyboard. We currently are working with two dozen children with profound disabilities to teach them to use EagleEyes to control computer software for entertainment, communication, and education. We have had some dramatic successes. [ABSTRACT FROM AUTHOR]

This work presents a method for translation of American Sign Language (ASL) to English using a feature-based lexicon, designed to exploit ASL's phonology by searching the lexicon for the sign's manual and non-manual information. Manual sign information consists of phonemes sig (movement), tab (location), dez (handshape), and ori (hand orientation), which we use as the ASL unit of analysis. Non-manual sign information consists of specific facial and body configurations. A camera acquires the sign and individual frames are analyzed and values assigned to the sig, tab, dez, and ori sign parameters as well as other sign features, for referencing during lexical search. ASL formational constraints are exploited to target specific image segments for analysis and linguistic constraints serve to further reduce the lexical search space. Primary keys for lexical search are sig and tab, the most discriminating sign features, followed by the remaining features, as necessary, until a single lexical entry is extracted from the lexicon. If a single lexical candidate cannot be determined, an exception is raised, signaling search failure. This method of using ASL phonological constraints to aid image analysis and lexical search process simplifies the task of sign identification. [ABSTRACT FROM AUTHOR]

We present an approach of iconic language design for people with significant speech and multiple impairments (SSMI), based upon the theory of Icon Algebra and the theory of Conceptual Dependency (CD) to derive the semantics of iconic sentences. A knowledge based design environment supporting the phases of this approach is described. [ABSTRACT FROM AUTHOR]

Many people in wheelchairs are unable to control a powered wheelchair with the standard joystick interface. A robotic wheelchair can provide users with driving assistance, taking over low-level navigation to allow its user to travel efficiently and with greater ease. Our robotic wheelchair system, Wheelesley, consists of a standard powered wheelchair with an on-board computer, sensors and a graphical user interface. This paper describes the indoor navigation system and the customizable user interface. [ABSTRACT FROM AUTHOR]

A Robotic Travel Aid (RoTA) is a motorized wheelchair equipped with vision, sonar, and tactile sensors and a map database system. A RoTA can provide a visually impaired user assistance with orientation and obstacle avoidance, as well as information about their present location, landmarks, and the route being followed. In this paper we describe HITOMI, an implementation of the RoTA concept that can guide a visually impaired user along a road with lane marks or along a sidewalk while avoiding obstacles. [ABSTRACT FROM AUTHOR]

People with both visual and mobility impairments have great difficulty using conventional mobility aids for the blind. As a consequence they have little opportunity to take exercise without assistance from a carer. The combination of visual and mobility impairments occurs most often among the elderly. In this paper we examine the issues related to mobility for the blind and pay particular attention to the needs of the elderly or frail. We overview current mobility aids and detail some of the research in this area. We then describe our robot mobility aid, PAM-AID, that aims to provide both physical support during walking and obstacle avoidance. We examine factors that are relevant to the operation of PAM-AID and describe some initial user trials. Finally we describe the current status of the project and indicate its future direction. [ABSTRACT FROM AUTHOR]

The Multimodal User Supervised Interface and Intelligent Control (MUSIIC) project addresses the issue of telemanipulation of everyday objects in an unstructured environment. Telerobot control by individuals with physical limitations pose a set of challenging problems that need to be resolved. MUSIIC addresses these problems by integrating a speech and gesture driven human-machine interface with a knowledge driven planner and a 3-D vision system. The resultant system offers the opportunity to study unstructured world telemanipulation by people with physical disabilities and provides means for generalizing to effective manipulation techniques for real-world unstructured tasks in domains where direct physical control may be limited due to time delay, lack of sensation, and coordination. [ABSTRACT FROM AUTHOR]

This paper describes the goals and research directions of the University of Texas Artificial Intelligence Lab's Intelligent Wheelchair Project (IWP). The IWP is a work in progress. The authors are part of a collaborative effort to bring expertise from knowledge representation, control, planning, and machine vision to bear on this difficult and interesting problem domain. Our strategy uses knowledge about the semantic structure of space to focus processing power and sensing resources. The semi-autonomous assistive control of a wheelchair shares many sub-problems with mobile robotics, including those of sensor interpretation, spatial knowledge representation, and real-time control. By enabling the wheelchair with active vision and other sensing modes, and by application of our theories of spatial knowledge representation and reasoning, we hope to provide substantial assistance to people with severe mobility impairments. [ABSTRACT FROM AUTHOR]

A brief survey of research in the development of autonomy in wheelchairs is presented and AAI's R & D to build a series of intelligent autonomous wheelchairs is discussed. A standardized autonomy management system that can be installed on readily available power chairs which have been well-engineered over the years has been developed and tested. A behavior-based approach was used to establish sufficient on-board autonomy at minimal cost and material usage, while achieving high efficiency, sufficient safety, transparency in appearance, and extendability. So far, the add-on system has been installed and tried on two common power wheelchair models. Initial results are highly encouraging. [ABSTRACT FROM AUTHOR]

We aim to develop a robot which can be commanded simply and accurately, especially by users with reduced mobility. Our shared control approach divides task responsibilities between the user (high level) and the robot (low level). A video interface shared between the user and robot enables the use of a deictic interface. The paper describes our progress toward this goal in several areas. A complete command set has been developed which uses minimal environmental features. Our video tracking algorithms have proven robust on the types of targets used by the commands. Specialized hardware and new tactile and acoustic sensors have been developed. These and other advances are discussed, as well as planned work. [ABSTRACT FROM AUTHOR]

Intelligent robotics is the study of how to make machines that can exhibit many of the qualities of people. This seems a very appropriate technology to use to assist those people who have lost certain abilities that are common to the majority of the population. This paper gives an overview of some of the robotic technology that has been or is being developed to assist people with disabilities. [ABSTRACT FROM AUTHOR]

The papers in this volume provide us with a snapshot of the variety of issues that must be considered when applying AI technologies to projects involving people with disabilities. Here a focus is on controlling interfaces and language issues. The AI technologies used are quite varied; the resulting ideas have a great deal of promise and point us to future possibilities. [ABSTRACT FROM AUTHOR]

Overfitting is often considered the central problem in machine learning and data mining. When good performance on training data is not enough to reliably predict good generalization, researchers and practitioners often invoke "Occam's razor" to select among hypotheses: prefer the simplest hypothesis consistent with the data. Occam's razor has a long history in science, but a mass of recent evidence suggests that in most cases it is outperformed by methods that deliberately produce more complex models. The poor performance of Occam's razor can be largely traced to its failure to account for the search process by which hypotheses are obtained: by effectively assuming that the hypothesis space is exhaustively searched, complexity-based methods tend to over-penalize large spaces. This talk describes how information about the search process can be taken into account when evaluating hypotheses. The expected generalization error of a hypothesis is computed as a function of the search steps leading to it. Two variations of this "process-oriented" approach have yielded significant improvements in the accuracy of a rule learner. Process-oriented evaluation leads to the seemingly paradoxical conclusion that the same hypothesis will have different expected generalization errors depending on how it was generated. I believe that this is as it should be, and that a corresponding shift in our way of thinking about inductive learning is required. [ABSTRACT FROM AUTHOR]