Search

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]