Fuzzy Logic
A New Direction in AI: Toward a Computational Theory of Perceptions
Fast-forward (FF) was the most successful automatic planner in the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS '00) planning systems competition. Like the well-known hsp system, FF relies on forward search in the state space, guided by a heuristic that estimates goal distances by ignoring delete lists. It differs from HSP in a number of important details. This article describes the algorithmic techniques used in FF in comparison to hsp and evaluates their benefits in terms of run-time and solution-length behavior. Humans have a remarkable capability to perform a wide variety of physical and mental tasks without any measurements and any computations. Familiar examples are parking a car, driving in city traffic, playing golf, cooking a meal, and summarizing a story. In performing such tasks, humans use perceptions of time, direction, speed, shape, possibility, likelihood, truth, and other attributes of physical and mental objects. Reflecting the bounded ability of the human brain to resolve detail, perceptions are intrinsically imprecise. In more concrete terms, perceptions are f-granular, meaning that (1) the boundaries of perceived classes are unsharp and (2) the values of attributes are granulated, with a granule being a clump of values (points, objects) drawn together by indistinguishability, similarity, proximity, and function. For example, the granules of age might be labeled very young, young, middle aged, old, very old, and so on. F-granularity of perceptions puts them well beyond the reach of traditional methods of analysis based on predicate logic or probability theory. The computational theory of perceptions (CTP), which is outlined in this article, adds to the armamentarium of AI a capability to compute and reason with perception-based information. The point of departure in CTP is the assumption that perceptions are described by propositions drawn from a natural language; for example, it is unlikely that there will be a significant increase in the price of oil in the near future. In CTP, a proposition, p, is viewed as an answer to a question, and the meaning of p is represented as a generalized constraint. To compute with perceptions, their descriptors are translated into what is called the generalized constraint language (GCL). Then, goal-directed constraint propagation is utilized to answer a given query. A concept that plays a key role in CTP is that of precisiated natural language (PNL). The computational theory of perceptions suggests a new direction in AI -- a direction that might enhance the ability of AI to deal with realworld problems in which decision-relevant information is a mixture of measurements and perceptions. What is not widely recognized is that many important problems in AI fall into this category.
Policy Gradient Methods for Reinforcement Learning with Function Approximation
Sutton, Richard S., McAllester, David A., Singh, Satinder P., Mansour, Yishay
Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically intractable. In this paper we explore an alternative approach in which the policy is explicitly represented by its own function approximator, independent of the value function, and is updated according to the gradient of expected reward with respect to the policy parameters. Williams's REINFORCE method and actor-critic methods are examples of this approach. Our main new result is to show that the gradient can be written in a form suitable for estimation from experience aided by an approximate action-value or advantage function. Using this result, we prove for the first time that a version of policy iteration with arbitrary differentiable function approximation is convergent to a locally optimal policy.
Policy Gradient Methods for Reinforcement Learning with Function Approximation
Sutton, Richard S., McAllester, David A., Singh, Satinder P., Mansour, Yishay
Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically intractable. In this paper we explore an alternative approach in which the policy is explicitly represented by its own function approximator, independent of the value function, and is updated according to the gradient of expected reward with respect to the policy parameters. Williams's REINFORCE method and actor-critic methods are examples of this approach. Our main new result is to show that the gradient can be written in a form suitable for estimation from experience aided by an approximate action-value or advantage function. Using this result, we prove for the first time that a version of policy iteration with arbitrary differentiable function approximation is convergent to a locally optimal policy.
Policy Gradient Methods for Reinforcement Learning with Function Approximation
Sutton, Richard S., McAllester, David A., Singh, Satinder P., Mansour, Yishay
Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining apolicy from it has so far proven theoretically intractable. In this paper we explore an alternative approach in which the policy is explicitly represented by its own function approximator, independent ofthe value function, and is updated according to the gradient of expected reward with respect to the policy parameters. Williams's REINFORCE method and actor-critic methods are examples of this approach. Our main new result is to show that the gradient can be written in a form suitable for estimation from experience aided by an approximate action-value or advantage function. Using this result, we prove for the first time that a version of policy iteration with arbitrary differentiable function approximation is convergent to a locally optimal policy.
Function Approximation with the Sweeping Hinge Algorithm
Hush, Don R., Lozano, Fernando, Horne, Bill G.
We present a computationally efficient algorithm for function approximation with piecewise linear sigmoidal nodes. A one hidden layer network is constructed one node at a time using the method of fitting the residual. The task of fitting individual nodes is accomplished using a new algorithm that searchs for the best fit by solving a sequence of Quadratic Programming problems. This approach offers significant advantages over derivative-based search algorithms (e.g.
Function Approximation with the Sweeping Hinge Algorithm
Hush, Don R., Lozano, Fernando, Horne, Bill G.
We present a computationally efficient algorithm for function approximation with piecewise linear sigmoidal nodes. A one hidden layer network is constructed one node at a time using the method of fitting the residual. The task of fitting individual nodes is accomplished using a new algorithm that searchs for the best fit by solving a sequence of Quadratic Programming problems. This approach offers significant advantages over derivative-based search algorithms (e.g.
Function Approximation with the Sweeping Hinge Algorithm
Hush, Don R., Lozano, Fernando, Horne, Bill G.
We present a computationally efficient algorithm for function approximation withpiecewise linear sigmoidal nodes. A one hidden layer network is constructed one node at a time using the method of fitting the residual. The task of fitting individual nodes is accomplished usinga new algorithm that searchs for the best fit by solving a sequence of Quadratic Programming problems. This approach offers significantadvantages over derivative-based search algorithms (e.g.
Intelligent Data Analysis: Reasoning About Data
Berthold, Michael, Cohen, Paul R., Liu, Xiaohui
The Second International Symposium on Intelligent Data Analysis (IDA97) was held at Birkbeck College, University of London, on 4 to 6 August 1997. The main theme of IDA97 was to reason about how to analyze data,perhaps as human analysts do, by exploiting many methods from diverse disciplines. This article outlines several key issues and challenges, discusses how they were addressed at the conference, and presents opportunities for further work in the field.
Analysis of Temporal-Diffference Learning with Function Approximation
Tsitsiklis, John N., Roy, Benjamin Van
We present new results about the temporal-difference learning algorithm, as applied to approximating the cost-to-go function of a Markov chain using linear function approximators. The algorithm we analyze performs online updating of a parameter vector during a single endless trajectory of an aperiodic irreducible finite state Markov chain. Results include convergence (with probability 1), a characterization of the limit of convergence, and a bound on the resulting approximation error. In addition to establishing new and stronger results than those previously available, our analysis is based on a new line of reasoning that provides new intuition about the dynamics of temporal-difference learning. Furthermore, we discuss the implications of two counterexamples with regards to the Significance of online updating and linearly parameterized function approximators. 1 INTRODUCTION The problem of predicting the expected long-term future cost (or reward) of a stochastic dynamic system manifests itself in both time-series prediction and control.