Exploiting user feedback to compensate for the unreliability of user models

Natural Language is a powerful medium for interacting with users, and sophisticated computer systems using natural language are becoming more prevalent. Just as human speakers show an essential, inbuilt responsiveness to their hearers, computer systems must tailor their utterances to users. Recognizing this, researchers devised user models and strategies for exploiting them in order to enable systems to produce the best answer for a particular user.Because these efforts were largely devoted to investigating how a user model could be exploited to produce better responses, systems employing them typically assumed that a detailed and correct model of the user was available a priori, and that the information needed to generate appropriate responses was included in that model. However, in practice, the completeness and accuracy of a user model cannot be guaranteed. Thus, unless systems can compensate for incorrect or incomplete user models, the impracticality of building user models will prevent much of the work on tailoring from being successfully applied in real systems. In this paper, we argue that one way for a system to compensate for an unreliable user model is to be able to react to feedback from users about the suitability of the texts it produces. We also discuss how such a capability can actually alleviate some of the burden now placed on user modeling. Finally, we present a text generation system that employs whatever information is available in its user model in an attempt to produce satisfactory texts, but is also capable of responding to the user's follow-up questions about the texts it produces.Dr. Johanna D. Moore holds interdisciplinary appointments as an Assistant Professor of Computer Science and as a Research Scientist at the Learning Research and Development Center at the University of Pittsburgh. Her research interests include natural language generation, discourse, expert system explanation, human-computer interaction, user modeling, intelligent tutoring systems, and knowledge representation. She received her MS and PhD in Computer Science from the University of California at Los Angeles, and her BS in Mathematics and Computer Science from the University of California at Los Angeles. She is a member of the Cognitive Science Society, ACL, AAAI, ACM, IEEE, and Phi Beta Kappa. Readers can reach Dr. Moore at the Department of Computer Science, University of Pittsburgh, Pittsburgh, PA 15260.Dr. Cecile Paris is the project leader of the Explainable Expert System project at USC's information Sciences Institute. She received her PhD and MS in Computer Science from Columbia University (New York) and her bachelor's degree from the University of California in Berkeley. Her research interests include natural language generation and user modeling, discourse, expert system explanation, human-computer interaction, intelligent tutoring systems, machine learning, and knowledge acquisition. At Columbia University, she developed a natural language generation system capable of producing multi-sentential texts tailored to the users level of expertise about the domain. At ISI, she has been involved in designing a flexible explanation facility that supports dialogue for an expert system shell. Dr. Paris is a member of the Association for Computational Linguistics (ACL), the American Association for Artificial Intelligence (AAAI), the Cognitive Science Society, ACM, IEEE, and Phi Kappa Phi. Readers can reach Dr. Paris at USC/ISI, 4676 Admiralty Way, Marina Del Rey, California, 90292     

Learning from Different Teachers

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.     

Fuzzy systems and neural networks in software engineering project management

To make reasonable estimates of resources, costs, and schedules, software project managers need to be provided with models that furnish the essential framework for software project planning and control by supplying important management numbers concerning the state and parameters of the project that are critical for resource allocation. Understanding that software development is not a mechanistic process brings about the realization that parameters that characterize the development of software possess an inherent fuzziness, thus providing the rationale for the development of realistic models based on fuzzy set or neural theories.Fuzzy and neural approaches offer a key advantage over traditional modeling approaches in that they aremodel-free estimators. This article opens up the possibility of applying fuzzy estimation theory and neural networks for the purpose of software engineering project management and control, using Putnam's manpower buildup index (MBI) estimation model as an example. It is shown that the MBI selection process can be based upon 64 different fuzzy associative memory (FAM) rules. The same rules are used to generate 64 training patterns for a feedforward neural network. The fuzzy associative memory and neural network approaches are compared qualitatively through estimation surfaces. The FAM estimation surfaces are stepped, whereas those from the neural system are smooth. Also, the FAM system sets up much faster than the neural system. FAM rules obtained from logical antecedent-consequent pairs are maintained distinct, giving the user the ability to determine which FAM rule contributed how much membership activation to a concluded output.     

Polar IFS+Parisian Genetic Programming=Efficient IFS Inverse Problem Solving

This paper proposes a new method for treating the inverse problem for Iterated Functions Systems (IFS) using Genetic Programming. This method is based on two original aspects. On the fractal side, a new representation of the IFS functions, termed Polar Iterated Functions Systems, is designed, shrinking the search space to mostly contractive functions. Moreover, the Polar representation gives direct access to the fixed points of the functions. On the evolutionary side, a new variant of GP, the Parisian approach is presented. The paper explains its similarity to the Michigan approach of Classifier Systems: each individual of the population only represents a part of the global solution. The solution to the inverse problem for IFS is then built from a set of individuals. A local contribution to the global fitness of an IFS is carefully defined for each one of its member functions and plays a major role in the fitness of each individual. It is argued here that both proposals result in a large improvement in the algorithms. We observe a drastic cut-down on CPU-time, obtaining good results with small populations in few generations.     

Variable Precision Algorithm for the Numerical Computation of the Fermi–Dirac Function ℱj(x) of Order j=−3/2

The purpose of this technical note is to present a piecewise Chebyshev expansion for the numerical computation of the Fermi–Dirac function _–3/2(x), –<x<. The variable precision algorithm we given automatically adjusts the degrees of the Chebyshev expansions so that _–3/2(x) can be efficiently computed to d significant decimal digits of accuracy, for a user specified value of d in the range 1d15.     

A Novel Scheme for Human-Friendly and Time-Delays Robust Neuropredictive Teleoperation

A novel Neuropredictive Teleoperation (NPT) Scheme is presented. The design results from two key ideas: the exploitation of the measured or estimated neural input to the human arm or its electromyograph (EMG) as the system input and the employment of a predictor of the arm movement, based on this neural signal and an arm model, to compensate for time delays in the system. Although a multitude of such models, as well as measuring devices for the neural signals and the EMG, have been proposed, current telemanipulator research has only been considering highly simplified arm models. In the present design, the bilateral constraint that the master and slave are simultaneously compliant to each other's state (equal positions and forces) is abandoned, thus obtaining a simple to analyze succession of only locally controlled modules, and a robustness to time delays of up to 500 ms. The proposed designs were inspired by well established physiological evidence that the brain, rather than controlling the movement on-line, programs the arm with an action plan of a complete movement, which is then executed largely in open loop, regulated only by local reflex loops. As a model of the human arm the well-established Stark model is employed, whose mathematical representation is modified to make it suitable for an engineering application. The proposed scheme is however valid for any arm model. BIBO-stability and passivity results for a variety of local control laws are reported. Simulation results and comparisons with traditional designs also highlight the advantages of the proposed design.     

A “Microscopic” Study of Minimum Entropy Search in Learning Decomposable Markov Networks

Several scoring metrics are used in different search procedures for learning probabilistic networks. We study the properties of cross entropy in learning a decomposable Markov network. Though entropy and related scoring metrics were widely used, its microscopic properties and asymptotic behavior in a search have not been analyzed. We present such a microscopic study of a minimum entropy search algorithm, and show that it learns an I-map of the domain model when the data size is large.Search procedures that modify a network structure one link at a time have been commonly used for efficiency. Our study indicates that a class of domain models cannot be learned by such procedures. This suggests that prior knowledge about the problem domain together with a multi-link search strategy would provide an effective way to uncover many domain models.     

Elderly Japanese computer users: assessing changes in usage,attitude, and skill transfer over a one-year period

Changes and interrelations among computer usage, computer attitude, and skill transfer of elderly Japanese computer users were investigated over a one-year period. Each participant, aged 60 to 76 years, was provided with one touchscreen-based computer specialized for e-mail handling for 12 months. Participants usage of the computer, mouse and/or keyboard, and computer attitudes were investigated. The results showed that the Liking factor of the computer attitude scale was a possible predictor of computer usage. The results suggested the existence of four different types of users adaptation to computers, according to a combination of the Liking and Confidence dimensions of computer attitude.     

Polynomial-Time Decomposition Algorithms for Support Vector Machines

This paper studies the convergence properties of a general class of decomposition algorithms for support vector machines (SVMs). We provide a model algorithm for decomposition, and prove necessary and sufficient conditions for stepwise improvement of this algorithm. We introduce a simple rate certifying condition and prove a polynomial-time bound on the rate of convergence of the model algorithm when it satisfies this condition. Although it is not clear that existing SVM algorithms satisfy this condition, we provide a version of the model algorithm that does. For this algorithm we show that when the slack multiplier C satisfies 1/2 C mL, where m is the number of samples and L is a matrix norm, then it takes no more than 4LC ² m ⁴/ iterations to drive the criterion to within of its optimum.     

Continuous reductions among combinatorial optimization problems

Summary Many reductions among combinatorial problems are known in the context of NP-completeness. These reductions preserve the optimality of solutions. However, they may change the relative error of approximative solutions dramatically. In this paper, we apply a new type of reductions, called continuous reductions. When one problem is continuously reduced to another, any approximation algorithm for the latter problem can be transformed into an approximation algorithm for the former. Moreover, the performance ratio is preserved up to a constant factor. We relate the problem Minimum Number of Inverters in CMOS-Circuits, which arises in the context of logic synthesis, to several classical combinatorial problems such as Maximum Independent Set and Deletion of a Minimum Number of Vertices (Edges) in Order to Obtain a Bipartite (Partial) Subgraph.     

One Connection between Standard Invariance Conditions on Modal Formulas and Generalized Quantifiers

The language of standard propositional modal logic has one operator ( or ), that can be thought of as being determined by the quantifiers or , respectively: for example, a formula of the form is true at a point s just in case all the immediate successors of s verify .This paper uses a propositional modal language with one operator determined by a generalized quantifier to discuss a simple connection between standard invariance conditions on modal formulas and generalized quantifiers: the combined generalized quantifier conditions of conservativity and extension correspond to the modal condition of invariance under generated submodels, and the modal condition of invariance under bisimulations corresponds to the generalized quantifier being a Boolean combination of and .     

Cockpit cognition: Education,the military and cognitive engineering

The goals of public education, as well as conceptions of human intelligence and learning, are undergoing a transformation through the application of military-sponsored information technologies and information processing models of human thought. Recent emphases in education on thinking skills, learning strategies, and computer-based technologies are the latest episodes in the postwar military agenda to engineer intelligent components, human and artificial, for the optimal performance of complex technological systems. Public education serves increasingly as a human factors laboratory and production site for this military enterprise, whose high performance technologies and command and control paradigms have also played central roles in the emergence of the information economy.Our final hope is to develop the brain as a natural resource ... Human intelligence will be the weapon of the future.Luis Alberto MachadoThis paper will also appear, under the title Mental Material inCyborg Worlds: The Military Information Society, eds. Les Levidow and Kevin Robins, London: Free Association Press, (in press).     

Duality in Quantum Information Geometry

Let H be a separable Hilbert space. We consider the manifold M consisting of density operators on H such that ^p is of trace class for some p (0, 1). We say M is nearby if there exists C > 1 such that C ^–1C. We show that the space of nearby points to can be furnished with the two flat connections known as the (±)-affine structures, which are dual relative to the BKM metric. We furnish M with a norm making it into a Banach manifold.     

Surface reconstruction from stereoscopy and “shape from shading” in SEM images

The computational reconstruction of surface topographies from scanning electron microscope (SEM) images has been extensively investigated in the past, but fundamental image processing problems still exist. Since conventional approaches adapted from general-purpose image processing have not sufficiently met the requirements in terms of resolution and reliability, we have explored combining different methods to obtain better results.This paper presents a least-squares combination of conventional stereoscopy with shape from shading and a way of obtaining self-consistent surface profiles from stereoscopy and stereo-intrinsic shape from shading using dynamic programming techniques. Results are presented showing how this combined analysis of multi-sensorial data yields improvements of the reconstructed surface topography that cannot be obtained from individual sensor signals alone.     

Sound and complete Hoare-like calculi based on copy rules

Summary This paper presents a uniform approach to known and new results on relative completeness of Hoare-like calculi for languages of ALGOL-like programs with procedures as procedure parameters. First the notion of a copy rule is introduced. It provides a uniform framework for dealing with different variants of semantics reaching from dynamic to static scope. Then for each copy rule a Hoare-like calculus () is presented, the soundness of which is shown by using an approximating semantics. The key to the completeness results lies in a general completeness theorem on the calculi () which has these results as corollaries. Finally, a new type of theorem on Hoare-like calculi is proved by which the notion of formal provability in () is completely characterized. This characterization theorem is the main result of the paper. It covers both soundness and completeness of the calculi () and additionally gives an idea of what the limits of presently known Hoare-like proof techniques for programming languages with procedures are.     

An authorization model for multimedia digital libraries

In this paper we present a generalized authorization model for multimedia digital libraries. Our aim is to support the enforcement of access control requirements of the original data sources without the need to create a new, unified model for the digital library. We integrate the three most widely used access control models (i.e., mandatory, discretionary, and role-based) within a single framework, allowing seamless accesses to data protected by these security models. In particular, we address the access control needs of continuous media data while supporting quality of service (QoS) requirements and preserving operational semantics. The technical core of the paper focuses on the development of metadata and the corresponding metastructure to represent authorization policies and QoS requirements and shows their applicabilty to continuous media. We define our security objects based on the Synchronized Multimedia Integration Language (SMIL), which controls multimedia presentations. Following the synchronization constructs par and seq of SMIL, we define a normal form for multimedia streams, called SMIL normal form. SMIL normal form provides a syntax-independent representation of semantically equivalent multimedia data. SMIL normal form compositions are extended (decorated) with RDF statements, representing security and QoS metadata. Interpretation of these statements and, therefore, the authorization and QoS requirements of the decorated multimedia object are defined by the metastructure, represented as a DAML+OIL ontology. We propose the concept of generalized subject that encompasses all access permissions of a given user regardless of the multiple permissions in different access control models. Finally, we develop methods to generate secure views for each generalized subject and retrieve them using a secure multimedia server.     

Data structures as sets with repeating elements

Data structures are interpreted as sets which may contain repeating elements. An algebraic system close to the integer ring is constructed on these sets.Translated from Kibernetika, No. 4, pp. 82–88, July–August, 1990.     

Mechatronics engineering education and dissemination program

For evolution of Mechanical System Technology, a simplified mechanism with sophisticated electronics control are replacing the traditional pure mechanical system. The new technology which combines the mechanical system with electronics control is being referred to as Mechatronics Technology and explosively growing in all over the industrialized countries. The paper describes, the concept and essential technology components of the mechatronics technology and the methodology and implementation of the Mechatronics Engineering Education.     

Three-valued representative systems

A representative system defined onn voters or propositionsi = 1,,n is a functionF: {1,0, -1} ⁿ {1,0, -1} which is monotonic (D E F(D) F(E)), unanimous (F(1,, 1) = 1), dual (F(-D) = -F(D)), and satisfies a positivity property which says that the set of all non-zero vectors in {1, 0, -1} ⁿ for whichF(D) = 0 can be partitioned into two dual subsets each of which has the property that ifD andE are in the subset thenD _i+E _i > 0 for somei. Representative systems can be defined recursively from the coordinate projectionsS _i (D) = D _i using sign functions, and in this format they are interpreted as hierarchical voting systems in which outcomes of votes in lower levels act as votes in higher levels of the system. For each positive integern, (n) is defined as the smallest positive integer such that all representative systems defined on {1, 0, -1} ⁿ can be characterized by(n) or fewer hierarchical levels. The function is nondecreasing inn, unbounded above, and satisfies(n) n–1 for alln. In addition,(n) = n–1 forn {1, 2, 3, 4}, and it is conjectured that does not continue to grow linearly asn increases.