example vector. Create a new prototype vector for this
for this example./
membership[index] =
createNewPrototypeVector( &database[index] [0] );
done = 0;
}
} / for customers loop /
if (fcount--) break;
} / 1done */
return 0;
}
The ART1 algorithm is a simple nested loop in which all customer feature vectors are compared against all cluster prototype vectors. When no further changes occur in the clusters (it is no longer resonating), the algorithm is complete and we return to the main function. The source is a simple implementation of Equations 5.1 through 5.4. The mag* variables, the magnitudes of the vectors, are calculated once for efficiency. The algorithm also includes a number of optimizations to ignore prototype vectors that have no members (empty clusters are not considered). If the example feature vector is not classified during the cluster loop, a new cluster is automatically created. This handles Equation 5.1 in a clean fashion.
The final function, makeRecommendation, provides the recommendation service for a given customer (represented by their feature vector). See Listing 5.7.
LISTING 5.7 Recommendation Algorithm
Per Figure 5.6, the algorithm looks for the intersection of the most-purchased item in the cluster that was also not purchased by the current customer. The initial loop in makeRecommendation finds this intersection by keeping track of the most-purchased item and recording the item number (column of the sumVector). The remaining code emits textual information defining the recommendation (if one could be made). The function also emits all items that the customer has purchased as a check of the result.
Tweaking the Algorithm
Three important parameters can be tuned for the algorithm. The maximum number of clusters possible (defined as TOTAL_PROTOTYPE_VECTORS) should be set high enough so that the algorithm can create a new cluster if it needs to. Because the ability to create new clusters is a major advantage for ART1, sufficient clusters should be available.
Listing 5.9 provides a portion of the output of the recommendation utility. This output applies textual names to the items represented by the feature vector as well as the resulting recommendation choice.
LISTING 5.9 Output of the Recommendation Algorithm
For Customer 0, The best recommendation is 2 (Snickers)Owned by 2 out of 3 members of this clusterAlready owns: Kit-Kat Heath-Bar
For Customer 1, The best recommendation is 4 (Pen)Owned by 1 out of 2 members of this clusterAlready owns: Paper Pencil Binder
For Customer 2, The best recommendation is 0 (Hammer)Owned by 2 out of 3 members of this clusterAlready owns: Screwdriver Wrench Tape-Measure
For Customer 3, No recommendation can be made.
Already owns: Pen Pencil Binder
In each case, the ART1 algorithm correctly segmented the customers into groups based on the items that they've purchased. Customer 0 was placed into the "candy" cluster, Customer 1 into an "office supplies" cluster, and Customer 2 into a "tools" cluster. Recommendations follow the groupings that should be a good prediction of the customer's buying habits. Note that no recommendations could be made for Customer 3. This is because this customer's feature vector was the same as the prototype vector (no dissimilar elements), which meant that it had purchased all items that were represented by this cluster.
PRIVACY ISSUES
Another interesting application of this algorithm is for book recommendations. Consider a recommender system for library users. Each library user is encoded as a feature vector. The feature vector represents the books checked out by the user. Each element of the feature vector represents a small range of books within the spectrum of the Dewey Decimal Classification System (such as 100-103). This
Introduction to Adaptive Resonance Theory (ART1) 111
range represents books within the genre of philosophy. On application of the ART1 algorithm, clusters of feature vectors would be further refined to identify the percentage for which a particular book was checked out within the group. This data could then be used to recommend a book to a library user who may not be familiar with it.
This application works with test data, but it could never work practically due to privacy issues. Most libraries claim that they don't keep historical records of texts that a particular library user checks out. Without a historical data set, the ART1 algorithm in this application is useless.
Quite a bit of fear is associated with personalization algorithms. When they work well, they have the ability to predict a user's actions. This success can create an uneasy feeling for some as they realize that their behavior is being predicted solely on external observations. Although the result could be helpful to the user, other applications exist that can invade an individual's privacy. To combat the fear involved in these types of applications, most companies introduce privacy policies to define to customers what data is collected, what is done with it, and who is able to see or utilize it.
OTHER APPLICATIONS
ART1 generally provides the ability to cluster data into independent segments. The clustering can be of use by itself to understand the classes (types) of clusters that result. In addition, as we saw in the personalization algorithm, looking at the members of an individual cluster can provide interesting information. Additional applications include:
SUMMARY
This chapter has illustrated a simple algorithm that clusters sets of data into groups for use as a recommender system. Although originally defined as an offline pro-
112
cessing tool that could be used for data mining, the efficiency of the algorithm lends itself to real-time processing of data within a commercial Web environment.
The example application shown here represented a very small data set. For Web site personalization, the data set could include not only a representation of the Web content but also the time spent viewing a particular piece of content. The types and representation of the data ultimately depend on the algorithm providing the personalization service. With proper encoding within feature vectors, the ART1 algorithm can work with a wide variety of data representing many aspects of a consumer's behavior in a Web setting.
Despite the harmful applications that exist for personalization engines, they can be beneficial timesaving devices and, therefore, should not be overlooked.
REFERENCES
[Fisher87] Fisher, Douglas H., Machine Learning, Volume 2, Issue 2, Kluwer Academic Publishers: Hingham, Mass., 1987.
[Gallant94] Gallant, Stephen, Neural Network Learning, Cambridge, Mass.: MIT Press, 1994.
RESOURCES
Carpenter, G. and S. Grossberg, "A Massively Parallel Architecture for a Self-Organizing Neural Pattern Recognition Machine," Computer Vision, Graphics and Image Processing 37: 54–115, 1987.
Wolfram Research, "Eric Weisstein's World of Mathematics," available online at http://mathworld.wolfram.com, accessed January 17, 2003.
6 Introduction to Classifier Systems
In This Chapter
Introduction
Taxonomy of a Simple Classifier System
Simple Example
Non-Learning Classifier System Flow
Self-Learning in Classifier Systems
Sample Problem
Source Discussion
Sample Run
Applications of Classifier Systems
Variations of Classifier Systems
Problems with Classifier Systems
Summary
References
Resources
In this chapter, we'll look at one of the older techniques of AI known as classifier systems. The original classifier system was designed by John Holland in the mid 1970s. Classifier systems are simple logical rules that can be used to define how to react to external stimulus. Input stimulus is read and matched with an existing classifier. Once one or more matching rules are found, a single rule is permitted to activate, performing its associated action. This simple but powerful mechanism can also include a learning component to identify new rules and associated actions. We'll explore the basics of classifier systems as well as a simple self-learning scheme.
I have written some rules. Pl. collect from me [Handwritten note]
113
118
SELF-LEARNING IN CLASSIFIER SYSTEMS
Learning within classifier systems involves the discovery of new rules that help the agent achieve its goals while removing those that detract from the objective.
Updating our original Figure 6.1, we add the learning component shown in Figure 6.4. This component includes new elements for rule discovery and credit allocation (how to given credit to classifiers in the classifier list).
(Handwritten note at top right): This is what we are interested in, starting with (may be) 50 rules recruitment/getting selected/getting appointed, we want the algorithm to discover 500 "NEW" rules.
[Environment Diagram with Detector, Classifier Engine, Effictor, Rule Discovery, Credit Allocation, and Learning Component]
FIGURE 6.4 Simple learning classifier system.
Rule Discovery
Rule (or classifier) discovery is the process of creating new classifiers within our classifier list. We'll review two fundamental mechanisms: the covering procedure and the rules evolution.
Covering Procedure
When the agent encounters an input message from the environment, its first task is to search the list of classifiers to find one or more that match. When a rule is not found to match the current input message, we can employ the covering procedure to create a new classifier (see Figure 6.5).
7 Ant Algorithms
In This Chapter
In this chapter, we'll see an interesting multiagent simulation that's useful for solving a wide variety of problems. Ant algorithms, or Ant Colony Optimization (the named coined by its inventor, Marco Dorigo), use the natural metaphor of ants and stigmergy to solve problems over a physical space [Dorigo96]. Nature has provided numerous methods and ideas on the space of optimization (as illustrated by other chapters in this book, such as Chapter 3 "Simulated Annealing" and Chapter 10 "Introduction to Genetic Algorithms"). Ant algorithms are particularly interesting because they can be used to solve not only static problems but also highly dynamic problems such as routing issues in changing networks.
141
(Handwritten notes at top): Can we develop an "Agent" (Ant) for each corpo-subscriber's each job-advt., which travels to "distant places" (different jobsite and safely bring back "food" (resumes) to its own "nest" (folder)?
142
NATURAL MOTIVATION
(Handwritten notes): URLs/Passwords/Firewalls
Although ants are effectively blind, they navigate complex environments and can find food great distances from their nest and return to their nest successfully. They do this by laying down pheromones while they navigate their environment. This process, known as stigmergy, modifies their environment to permit communication between the ants and the colony as well as provide "bread crumbs" for the return trip to the nest.
What is most surprising about this process is that ants tend to take the best route between their nest and some external landmark. This natural optimization is again part of stig
144
(Figure 7.3: Two units of time have passed (
).)
ANT ALGORITHM
Let's now look at the ant algorithm in detail to better
understand how it functions for a specific problem.
Network
For this discussion, the environment in which our ants will
exist is a fully connected bidirectional graph (see Figure 7.4). Recall that a
graph is a set of nodes (or vertices) connected via edges (or lines). Each edge
has an associated weight, which we'll identify as the distance between the two
nodes connected by the edge. The graph is bidirectional so that an ant can
traverse the edge in either direction.
(Handwritten margin note: "path taken / could be /
taken")
The Ant
An ant is a single agent within the ant algorithm, commonly
part of a larger population (colony) used to solve a given problem. The ant is
endowed with a set of simple rules that define how it chooses its path through
the graph. The ant maintains a tabu list, which is simply a list of nodes that
the ant has visited. This list is kept so that the ant moves through each node
only once. A path between two vertices on a graph where each vertex is visited
only once is known as a Hamiltonian path (first proposed by mathematician Sir
William Hamilton).
(Handwritten margin note: "millions of /
Agents")
The ant also maintains the list of nodes in its current
tour, in the order in which the ant has traveled. This list is used later to
identify the tour length through the nodes.
Ant Algorithms 145
(Figure 7.4: Example of a fully connected network graph 
with edge set 
.)
In the natural world, an ant lays pheromones along the trail
as it travels, but in the ant algorithm, the ant distributes pheromone on the
edges of the graph once the tour is complete. The reason for this will
difference be discussed in the section, "Ant Tour."
Initial Population
A population of ants is created and then uniformly
distributed across the nodes of the graph. Distributing the ants equally across
the nodes is important because we want all nodes to have an equal chance as a
starting point. Starting each ant in the same place would assume that the
particular node was the optimal starting node—something we simply don't know.
Ant Movement
Ant movement is based on a single, very simple, probability
equation. Until an ant has completed a tour (visited all nodes within the
graph, otherwise known as a path), the following equation is used to identify
the next edge the ant should take (Equation 7.1).
8 | Introduction to Neural Networks and the
Backpropagation Algorithm
JPG
367
JPG
(Handwritten notes at top: "Game = Online
Recruitment / searching for Employers / searching for Candidates" /
"Characters = (1) Recruiters (2) Jobseekers" / "Agents = (1) Job
Advts (2) Resumes" / "Environment = Virtual Job Fair = Virtual Emp.
Portal } read my notes")
In This Chapter
- Neural
Networks from the Biological Perspective
- Single
Layer Perceptrons
- Multiple-Layer
Networks
- Backpropagation
Learning
- Evolving
Game AI Behaviors
- Source
Discussion
- Neurocontroller
Learning
- Neurocontroller
Memory
- XOR
Network Learning
- Other
Topics
- Other
Applications
- Summary
- References
- Resources
Although various neural network topologies and learning
algorithms exist, this chapter will focus on feed-forward, multilayer networks
using back-propagation learning. We'll begin with a simple introduction of
neural networks and their components and then discuss the learning algorithm
and some problems that can arise during backpropagation learning. We'll look at
an example of a simple network and walk through the backpropagation algorithm
to understand its properties. Finally, we'll look at simple neural networks as
a way to give life to characters within game environments.
JPG
165
JPG
166
NEURAL NETWORKS FROM THE BIOLOGICAL PERSPECTIVE
(Handwritten margin note near heading: "edges /
links")
(Handwritten margin note near 'elements':
"Vertices")
Neural networks are simple implementations of local behavior
observed in our own brains. The brain is composed of neurons, which are the
individual processing elements. Neurons are connected by axons that end at the
neuron in a synapse. The synapse is responsible for relaying a signal to the
neuron. Synapses can be either inhibitory or excitatory.
JPG
The human brain contains approximately 
neurons. Each neuron
connects to approximately 1,000 other neurons, except in the cerebral cortex
where the density of interneuron connectivity is much higher. The structure of
the brain is highly cyclic (self-referential), but it can be thought of as having
a layered architecture (see Figure 8.1). In a simplified model, the input layer
to the network provides our sensory inputs from the environment; the middle
layer, or cerebral cortex, processes the inputs; and the output layer provides
motor control back to the environment.
JPG
(FIGURE 8.1: Layered architecture for a simple brain.
Diagram shows: Environment -> Perception (Sense) -> Cerebral Cortex
(Process) -> Control (React) -> Environment)
JPG
Artificial neural networks attempt to mimic the basic
operation of the brain. Information is passed between the neurons, and based on
the structure and synapse weights, a network behavior (or output mapping) is
provided.
JPG
SINGLE LAYER PERCEPTRONS
A single layer perceptron (SLP) is a connectionist model
that consists of a single processing unit. Each connection from an input to the
cell includes a coefficient that represents a weighting factor. Each connection
is specified by a weight 
that specifies the influence
of cell 
on the cell. Positive
weights indicate reinforcement, and negative weights indicate inhibition. These
weights, along with the inputs to...
JPG
(Handwritten note at top: "I believe Cyril used such
an algorithm, to read a plain text resume. The goal was to pick out the
"Address" from plain text resume. The S/W did manage to accurately
find the "Address" (from anywhere in the resume) after about 72 hours
of continuous "exploring / processing / learning". This was finite
number of times...")
JPG
(Handwritten margin note: "nearly 8-10 years ago I
am sure, or more powerful neural net shells")
JPG
Introduction to Reinforcement Learning
207
JPG
The fundamental idea is that if the environment is traversed
(explored) an infinite number of times, the probabilities for the available
actions, which are computed based on the reward received for entering the
states, will result in an optimal policy to get from the start to the goal
state that maximizes the rewards. We'll look at the math involved in this
process in the coming sections.
JPG
Although RL can be used to solve this type of grid problem,
it can also be used to solve other problems that are state/action based,
including control problems in robotics and a variety of games such as chess and
blackjack.
JPG
(Handwritten note: "can be freely downloaded, which
would parse a plain text resume to find accurately ALL the fields / values
which we need to create structured database.")
JPG
SUPERVISED OR UNSUPERVISED LEARNING
(Handwritten margin note: "07-01-07 / is simply a
strain of experimenting - now, we have no shortage of hardware.")
JPG
Supervised and unsupervised learning techniques vary
greatly. In this book, we've looked at both unsupervised learning (Chapter 5)
and supervised learning (Chapter 8). RL is a kind of unsupervised learning
because the agent receives reward or punishment only by interacting with the
environment. An agent with RL explores the environment to learn and, once
learning is complete, uses this knowledge to exploit the environment.
JPG
BIOLOGICAL MOTIVATIONS
The biological motivation for RL is a simple model of trial
and error. For example, positive reinforcement is given to an agent for a good
response, negative reinforcement (punishment) for a poor response. The agent
transitions probabilistically between states, receiving a reward (or
punishment) based on the value of the state transition. The cause-and-effect
relationships are learned within the model, producing an optimal policy for
maximizing a reward.
JPG
Q LEARNING ALGORITHM
Now let's dig into the Q Learning algorithm to see how
learning is accomplished in an environment. Recall that our environment
consists of a set of states with actions that transition between states. Each
state can have an associated reward, which affects the value of the action
(state transition), which in turn results in a state/action table that provides
our agent with the ability to learn and then intelligently traverse the
environment.
JPG
S
(Handwritten note at top: "Someday (when we have a
million resumes on our website), we will have many subsets of candidates who
started their careers (first job), at the same age, and with same Edu.
Qualification")
JPG
230
JPG
(Handwritten margin note: "Question is: How did
their careers evolve? What - salary - designation did each of them
reach/achieve, after a) 5 yrs b) 10 yrs c) 15 yrs of experience? Was there a
pattern? Did their career-paths run parallel or did they diverge? If the paths
did diverge, what other factors (eg: Employer companies?) influenced such
divergence? Did some plateau off after a time, whereas other continued to climb
the Desig/Salary ladder?")
JPG
species search for increasingly beneficial adaptations for
survival within their complex environments. The search takes place in the
species' chromosomes where changes, and their effects, are graded by the
survival and reproduction of the species. This is the basis for survival of the
fittest—survival and the passing on of these characteristics to future
generations. Survival in nature is the ultimate utility function.
JPG
THE GENETIC ALGORITHM
Instead of trying to optimize a single solution, the genetic
algorithm works with a population of candidate solutions that are encoded as
chromosomes. Within the chromosome are separate genes that represent the
independent variables for the problem at hand (see Figure 10.1).
JPG
(FIGURE 10.1: Encoding candidate solutions into
chromosomes. Diagram shows Chromosome Encoding 
as genes inside Chromosome).
JPG
From the simple example shown in Figure 10.1, we take the
parameters from our problem and create a chromosome that represents the two
unique independent parameters. The parameters could represent bit strings,
floating-point variables, or simple binary-encoded integers.
JPG
Through the selection of fit chromosomes from the population
and the use of genetic operators such as recombination and mutation, better-fit
chromosomes will result in the population. This represents a summary for
Holland's schema theorem and is the basis by which it works.
JPG
The genetic algorithm consists of three fundamental steps,
excluding the initial creation of the population (with a large number of
variations possible within each step). These steps are shown in Figure 10.2.
JPG
(FIGURE 10.2: Genetic algorithm high-level flow diagram:
Initialization -> Evaluation -> Selection -> Recombination -> loop
back to Evaluation)
JPG
During the evaluation process, the fitness of the population
is calculated. Next, a subset of the population is selected based on a
predefined selection criterion. Finally, the selected subpopulation is
recombined, and the result is a new population. The algorithm begins again with
the new population, and the process continues until some constraint is reached
and the algorithm ends.
JPG
Initialization
Creating the initial population provides the starting point
for the algorithm. Typically, this process is done by creating chromosomes
randomly, but it can also be done by seeding the population with known fit
chromosomes (see Figure 10.3).
JPG
(NOTE icon)
One important constraint to this algorithm is that the
initial population must be diverse. This diversity can be ensured by
performing a secondary step to check that each chromosome is somewhat
different. Without adequate diversity, the algorithm may not produce
good solutions.
JPG
12 | Introduction to Rules-based Systems
JPG
In This Chapter
- Introduction
- Anatomy
of a Rules-based System
- Types
of Rules-based Systems
- Phases
of a Rules-based System
- Simple
Example
- Sample
Application
- Source
Discussion
- Building
a Rules Base
- Other
Applications
- Problems
with Rules-based Systems
- Summary
- References
In this chapter, we'll look at one of the original symbolic
AI systems, the knowledge-based system. These systems are also called expert
systems (or production systems), where knowledge is encoded in rules. Knowledge
(or facts) is stored in a working memory, and the rules are applied to the
knowledge to create more knowledge. This process continues until some goal
state is reached. We'll investigate a simple rules-based system in this chapter
along with an application in the domain of fault tolerance.
JPG
INTRODUCTION
Although a number of rules-based systems exist, we'll focus
on a combination of two particular kinds called the deduction system and the
reaction system. A deduction...
JPG
299
JPG
300
JPG
system consists of rules representing antecedents and
consequents. An antecedent is a condition (an "if" statement, if you
will), whereas the consequent represents the resulting action (the
"then" portion). By deduction, the rules insert new facts into the
working memory that were "deduced" (reasoned by deduction) from the
existing working memory by a given rule. A reaction system includes
"actions" that are performed as part of the consequent, such as
issuing a command in an embedded system to alter the environment.
JPG
ANATOMY OF A RULES-BASED SYSTEM
A rules-based system comprises distinct elements. A set of
rules exists that operate over a collection of facts stored in a working
memory. Logic is provided to identify which rule to fire (based on the
antecedents) and then modify working memory (based on the consequents). Figure
12.1 provides a graphical depiction of a simple rules-based system.
JPG
(FIGURE 12.1: Illustration of a rules-based system
showing Working Memory (Data) containing Facts, Rule Memory (Program)
containing Rules, leading to Match/Resolve/Fire).
JPG
(Handwritten diagrams and notes over Figure 12.1:)
JPG
- "Facts
are keywords found in any resume"
JPG
JPG
- "Age
cannot be less than 18"
JPG
- "Edu.
level cannot be less than 12th Std/SSC"
JPG
- "MD
cannot be less than Executive (Logic)"
JPG
- "Post
Grad cannot be less than Grad"
JPG
- "Salary
cannot be less than Rs. 2000/= pm"
JPG
JPG
Rules operate over the body of facts stored in the working
memory. Once a rule is matched, it is permitted to fire, which may (or may not)
alter the working memory. This process continues until a goal state is reached.
JPG
Working Memory
The working memory is the structure where the currently
known facts are stored. This is a persistent space that can be altered only
through the consequent of a rule...
JPG
330
LISTING 12.23 Firing a Timer
C
int fireTimer( int timerIndex )
{
int ret;
char
element[MEMORY_ELEMENT_SIZE+1];
extern int
performAddCommand( char *mem );
sprintf( element,
"(timer-triggered %d)", timerIndex );
ret =
performAddCommand( element );
timers[timerIndex].active = 0;
return ret;
}
Starting a timer is called by the enable command. This
function, shown in Listing 12.24, encapsulates all timer functionality into a
single file.
LISTING 12.24 Starting a Timer
C
void startTimer( int index, int expiration )
{
timers[index].expiration = expiration;
timers[index].active = 1;
return;
}
BUILDING A RULES BASE
Building a rules base is easy, but there are a number of
ways to simplify the task.
Rules should be logically ordered based on their context.
For example, rules that have similar antecedents could be placed together
because they are attempting to deduce the same or similar facts from the
working memory. Similarly, rules that share similar consequents could also be
grouped together because they result in similar actions (represent similar
deductions).
For complex rule bases, state machines can be introduced
using staging elements. For example, consider the following two rules shown in
Listing 12.25.
LISTING 12.25 Example of Staging Rules
C
(defrule stage1-check
(stage stage1)
(battery-temp low)
=>
JPG+ 4
SANJIVANI BOOK HCP_Page_31.jpg
C
(add (check battery-temp))
(delete (stage stage1))
(add (stage stage2))
)
(defrule stage2-check
(stage stage2)
(battery-temp low)
=>
(add (check
battery-pressure))
(delete (stage
stage2))
)
We've introduced the (stage stageX) facts as markers.
Instead of acting as simple information in the working memory, these facts act
as guards for the rules. Neither of the rules is considered unless the staging
rule matches.
Finally, nothing beats pure testing. To fully test, there
must be some way to introduce stimulus into the system. Outside of simply
introducing facts through the init rule, time-triggered rules can also be used
to simulate the addition of facts asynchronously. Recall from Listing 12.2 the
use of time-triggered events to simulate sensor failures.
OTHER APPLICATIONS
Although rules-based systems are often used as knowledge
based expert systems, it should be clear from this application that a
rules-based system could also be used for simple programming tasks. When we
program, we encode our knowledge about the problem at hand into the syntax and
semantics of the programming language. Rules-based systems can also be used to
solve interesting problems, such as the fault-tolerance application discussed
previously for sensor management. One of the key differences between the two
approaches is that when programming in a traditional language, we encode our
knowledge serially into the application using the constructs at hand.
Rules-based systems require instead a mapping of the knowledge about the
application into rules that define the consequents and antecedents. In some
ways, this method can be easier and more readily understandable.
PROBLEMS WITH RULES-BASED SYSTEMS
The greatest drawback to rules-based systems is the amount
of time required to match a rule with available working memory. Recall from the
source discussion...
332
(Handwritten note at top left: "eg: Designation
Synonyms / Abbreviations")
that there is the problem of not only one-to-one mapping of
rules to working memory but also variations based on inexact terms. Therefore,
instead of just trying to map a rule to working memory, we may have to perform
multiple iterations over each rule. If a match is not found, the match process
will continue through to each rule.
A solution to this problem exists—the Rete algorithm
[Forgy82]. The idea behind Rete is to share intermediate information between
rules to limit the number of matches that must be performed. This process is
performed through an acyclic directed graph representing the antecedents for
the rules. For example, if two rules share one common element of their
antecedent, each rule would share a node within the graph for the comment
element. From this node, one would represent the remaining elements of their respective
antecedents. In this way, a match for a given element is performed once,
leading to possibly multiple rules that might match but computing the initial
match only once.
SUMMARY
In this chapter, we've investigated one of the original
reasoning architectures in artificial intelligence, the rules-based system. We
focused specifically on forward-chaining architectures with an implementation
of a simple deduction system. Even though it is simple, this implementation can
be used in various settings, including in other systems with consequent hooks
for manipulating the environment. We looked not only at a classical example
from [Winston 93] (the ZOOKEEPER rule-set) but also at a simple fault tolerance
example, managing sensors within an environment with reliability requirements.
Although rules-based systems do have their drawbacks, they provide a powerful
architecture for reasoning in systems that interact with a user (such as
classical diagnostics systems) down to embedded systems that must manage their
environment.
REFERENCES
[Forgy82] Forgy, C.L., "Rete: A Fast Algorithm
for the Many Pattern/Many Object Pattern Match Problem," Artificial
Intelligence, 19:17–37, 1982.
[Winston93] Winston, P.H., Artificial Intelligence.
3rd ed. Addison Wesley, 1993.
13 | Introduction to Fuzzy Logic
In This Chapter
- Introduction
- Fuzzy
Quality of Service Example
- Membership
Functions
- Fuzzy
Control
- A
Visual Fuzzy Control Example
- The
Fuzzy Axioms
- Hedge
Functions
- Why
Use Fuzzy Logic
- Sample
Application
- Advantages
to Fuzzy Logic
- Other
Applications
- Summary
In this chapter, we'll look at the logic system that Lotfi
Zadeh defined to overcome his believed disparity between real-world systems and
software representations. In software, the Boolean logic values of true and
false represent unique elements in a two-valued system. The real world rarely
operates in this fashion—many conditions can be partially true or partially
false (or both). Fuzzy logic was introduced to allow software to operate in the
domain of degrees of truth. Instead of binary systems that represent truth or
falsity, degrees of truth operate over the infinite space between 0.0 and 1.0,
inclusive.
333
334
INTRODUCTION
To fully understand what Dr. Zadeh proposed in 1963, let's
look at a number of examples that provide more information about fuzzy logic
and its representation.
FUZZY QUALITY OF SERVICE EXAMPLE
The power of fuzzy logic appears when we begin to analyze a
system using linguistics. For example, let's say that we're building a QoS
(Quality of Service) algorithm that manages the output of packets over a
particular link. The purpose of the QoS algorithm is to provide a given
application a consistent amount of bandwidth of the link. If the application
tries to use too much of the link's bandwidth, we must reduce the rate that
packets are emitted for the given application. From a control perspective, we have
three elements. The first is the packet arrival rate from the application, the
second is the measured utilization of the link, and the third is the gate that
controls the flow of packets between the application and the link (see Figure
13.1).
(FIGURE 13.1: Quality of service scenario with rate
feedback. Diagram shows: Application -- Arrival Rate --> Gate (with Measure
feedback from Link) --> Link)
The purpose of the gate is to control when and how many
packets are permitted to pass given the bandwidth allocated to the particular
application. When we think about this problem, we consider it in terms of
linguistics. For example:
- If
the application utilization of the link is high, then reduce the rate of
flow of packets through the gate for the application.
- Conversely,
- If
the application utilization of the link is low, then increase the rate of
flow of packets through the gate for the application.
These rules imply that dead zone exists between the high and
low rates that is "about right" for the application.
Introduction to Fuzzy Logic 335
The question is now what is "high" and
"low" for the application rate and what is "about right"?
Fuzzy logic determines this using membership functions (see Figure 13.2).
(Handwritten note over text: "In developing Function
Profile graphs, we are simply depending on "Presence" or
"Absence" of any given Keyword (Binary State). Then assigning
"Weightage" of a given amount or a weightage of zero depending upon
present or absent. But in real world, it may turn out that the candidate with a
lower Raw score because of many "absent" keywords, turns out to be a
better choice (higher interview-score in IIT 3), than, a candidate having higher
Raw score (where most keywords were "present"). In such a scenario,
should we try out Fuzzy logic Algorithm?")
(FIGURE 13.2: Membership function for packet rate. Graph
showing Low / High curves plotted against Link Utilization)
MEMBERSHIP FUNCTIONS
A membership function defines the degree of membership of a
given real-world value in the membership function. From our QoS example, we
have a membership function over the set of link utilization (see Figure 13.2).
From Figure 13.2, we've defined two segments, with a third
centered between what exists as our target. The low range can be defined
programmatically as shown in Equation 13.1.
The high range can then be defined as shown in Equation
13.2.
352
INTRODUCTION
NLP and natural language understanding (NLU) are important
elements of AI and the development of products that simplify the user
experience. Language, in both speech and text forms, is a natural interface for
us, so to be able to use this medium to communicate with machines is highly
desirable.
Natural Language Taxonomy
Natural language technologies can be broken down into five
major fields (see also Figure 14.1):
- Speech
recognition
- Language
processing
- Language
understanding
- Language
generation
- Speech
synthesis
Speech recognition provides a means by which speech is
broken down into the individual word tokens. One of the most basic problems in
speech recognition is isolated versus continuous speech recognition (whether
pauses are necessary between words to allow the machine to know where one word
ends and another begins). Discrete speech recognition is used widely today,
presenting a minor inconvenience to the user. But there's more to speech than
simply words being uttered. Speech also contains inflections and other elements
of articulation that communicate even more (such as emotion and giving context
to what is being said).
(Handwritten margin note: "Dragon Naturally
Speaking" s/w package.)
Language processing and understanding are commonly grouped
as one element, but we'll separate them here to illustrate their differences.
Once speech (or text) has been tokenized, the job of parsing it into its native
components can be performed. Given a grammar (rules for the language) and a
lexicon (a dictionary of nouns, verbs, prepositions, and adjectives). Once the
basic structure of an utterance has been identified (commonly through a parse
tree), identifying what the speech means is the next step. Understanding
implies that we can map the speech to a conceptual representation that is both
meaningful and usable by the application.
(Handwritten margin note: "Read my notes -> ARDIS
-> ARGIS")
Language generation and speech synthesis (or articulation)
are the reverse aspects of recognition and understanding. Language generation
takes an internal concept or goal of the application and forms the necessary
word sequence to communicate to the user. Most modern systems simply store a
set of predefined messages (or message patterns) that are used to present a
concept or reply to the user. It's interesting to note that patterns are also
used for language understanding.
Natural Language Processing 353
(Handwritten note at top: "ARDIS / ARGIS")
(Understanding and generation are closely related fields
of research because they both involve representations of knowledge.)
(NOTE icon)
Another interesting field of research in language
processing is the recognition of sign language. Rather than processing speech,
sign language requires the processing and understanding of visual gestures.
Finally, the synthesis or articulation of speech is the last
technology that is used to transform a word sequence into audible speech. Like
recognition, synthesis is difficult to do well and even today sounds
mechanical.
(FIGURE 14.1: Natural language technologies and their
relationships. Diagram flow: Speech -> Speech Recognition -- (word
sequences) --> Parsing and Understanding -- (conceptual representation)
--> Intelligent Application -- (Generation) --> Generation -- (Speech
Synthesis) --> Speech)
(NOTE icon)
Another view of natural language processing is syntactic
analysis (checking the word order and ensuring that the words appear in the
proper order), semantic analysis (identifying the meaning of the word
sequence), and contextual interpretation (where the result of semantic analysis
is checked against the world model for the application to ensure it makes
sense).
We'll now focus on the parsing aspect of language processing
and see how this also provides a simple means for language understanding.
354
LANGUAGE PARSING
Although various algorithms exist to parse language, they
all have at least two things in common: a grammar and a lexicon. The parser
must know the words that will appear during the discourse and the roles that
those words play. Now let's look at the basics of language parsing from a high
level.
Lexicon
A lexicon is a collection of words used in a given
application, including attributes for the words. Consider the lexicon shown in
Figure 14.2.
(Handwritten note on left: "hundreds of readymade
"parsing softwares" are available - some even freely downloadable
from web.")
FIGURE 14.2 Sample lexicon for a simple parser.
|
Word
|
Class
|
|
a
|
Determiner
|
|
the
|
Determiner
|
|
cat
|
Noun
|
|
mouse
|
Noun
|
|
man
|
Noun
|
|
eats
|
Verb
|
|
chases
|
Verb
|
|
pets
|
Verb
|
This simple lexicon allows us to communicate a handful of
ideas about the world it describes. It contains determiners (which assist in
referencing one of several possible noun objects in our simple universe), nouns
(which describe things), and verbs (to express an act).
It's simple for us to take this lexicon and construct some
number of simple sentences from it, but how do we express the rules so that a
computer can perform this task? The answer is through the use of a grammar.
Grammar
A grammar is a formal description of the structure of the
language. It defines rules for the legal sequences of words in this small
English language subset (see Figure...
Natural Language Processing 369
Plaintext
(VP_NP [DET the] [ADJ blue] (NOUN car) ) ) )
Actor: man
Action: washed
Object: blue car
(S (NP [DET a] (NOUN dog) )
(VP (VERB chased)
(VP_NP [DET a]
[ADJ dirty] (NOUN cat) ) ) )
Actor: dog
Action: chased
Object: dirty cat
Note that our grammar supports such statements as "the
man ate the house." This is a legal sentence in our grammar, but it
doesn't make sense. This type of inconsistency would be identified during the
semantic or contextual analysis phase.
APPLICATIONS
Natural language processing and understanding has many
useful applications. Many human-computer interfaces exist to help people
communicate with machines (and vice versa). The ability to speak to a machine
provides both a simple and natural model for communication and, therefore, is
an important area of research and development. Outside of speech interfaces,
natural language processing and understanding is also important in text
filtering (indexing user files), language translation, information retrieval (such
as databases and the World Wide Web), and, most important, spam identification.
NLP has also been successfully applied to various computer games.
The key to any NLP application is defining what's "good
enough." Building a program that successfully parses and understands the
English language is a Herculean task, so minimizing the lexicon down to what's
needed for the application is the first step to any development effort.
Outside of human communication, languages have been defined
to support communication between applications (agent-to-agent communication).
One such agent communication language is called KQML, or Knowledge Query and
Manipulation Language. This language (and protocol) permits agents not only to
query one another and communicate information but also to communicate beliefs
and intentions. KQML is part of the Advanced Research Project Agency's
Knowledge Sharing Effort.
(NOTE icon)
The development of chatbots can be simplified using one
of numerous language front-ends. One interesting example is the Artificial
Intelligence Markup Language (AIML). This is an XML-compliant language for
encoding knowl-
372
(FIGURE 15.1: Example of a Markov chain. Diagram showing
phoneme transitions for the word "Tomorrow": T -> AH (0.5) / UW
(0.5) -> M -> AA -> R -> OW)
Figure 15.1 illustrates the pronunciation of the word tomorrow.
Two possible pronunciations are available in the diagram. The probability of
the tahmorrow pronunciation is 0.5, whereas the probability of the
alternate tuwmorrow pronunciation is also 0.5.
This is a simple case, involving a decision at a single
point in the chain. Each state involves the production of a phoneme. At the end
of the chain, a completed pronunciation is available. We'll look more at the
purpose for this model in the applications section.
Next, let's look at a different application. Consider an
e-mail program that monitors the behavior of the user. When an e-mail message
arrives, the model observes what the user does with the e-mail message and uses
this information to learn how to automatically deal with subsequent e-mail
messages. See the chain shown in Figure 15.2.
(Handwritten margin note: "Beysian Spam Filter ?
based on a starting database of "unwanted" keywords in the email
messages.")
(FIGURE 15.2: Learning user interaction with an e-mail
program. Flow chart showing Incoming Mail -> spam (0.8) -> Trash (0.8) /
Read (0.2) OR dank (0.2) -> Read (1.0))
The Bigram Model 373
Our e-mail agent has observed that 8 out of 10 e-mail
messages are spam and 2 out of 10 are from user "dank." The e-mail
agent further observes that 80 percent of the time, we delete the spam e-mail
without reading it. The other 20 percent of the time, we read the e-mail
message. From these probabilities, the e-mail agent can deduce that we're more
likely to delete the e-mail message than to read it. Using these probabilities
provides an opportunity for the e-mail agent to simplify our task of managing
e-mail messages.
(TIP Icon)
In the examples shown here, a limited number of states and
connections were defined. The Markov chain can support a large state space with
large numbers of connections to model complex processes.
An interesting property of both examples is that the current
state is always a function of the previous state, given a connection
probability. This is called the Markov Property. In addition, because in
our examples, a state can be reached by more than one previous state for
example, the "Read" state from Figure 15.2), these models are known
as hidden Markov models (HMMs) or hidden Markov chains.
HMM APPROXIMATIONS
Note that in the previous examples, the current state of the
chain was a function solely of the prior state of the chain with a defined
probability. This is known as a bigram (a sequence of two words). If the
current state were not a function of the prior state, the selection of state
would simply be a random process. If the state were dependent on the prior two
states, it would be called a trigram. Although increasing the dependence
on the prior states (or context) can increase the usability of the chain (as
we'll see in the applications section), the memory requirements on such models
can be inhibitive [Henke99]. For example, consider Table 15.1, which shows the
number of elements necessary for a vocabulary of 100 words.
TABLE 15.1 Context Size and Number of Unique Elements for
a 100-Word Corpus
|
n
|
Type
|
Number of Elements
|
|
2
|
bigram
|
10,000
|
|
3
|
trigram
|
1,000,000
|
|
4
|
4-gram
|
100,000,000
|
374
A corpus of 100 unique words is quite small; therefore,
creating anything other than bigrams over a corpus can be quite expensive.
INTERESTING APPLICATIONS
Let's now look at a few applications of Markov chains for
HMMs. The first example, speech recognition, is a practical method used to
determine the words spoken in natural language processing. The following two
examples are more thought provoking than useful, but they provide a greater
understanding of the possibilities with Markov chains.
Speech Recognition
Recall from Figure 15.1 that the pronunciation of a word can
take on one or more variations based on the dialect or origin of the speaker. Building
speech recognition systems then becomes difficult, because the system must deal
with a variety of pronunciations of a given word.
Hidden Markov chains provide the opportunity to simplify
speech recognition systems through probabilistic parsing of the phonemes of
speech. For example, let's say that a speech system is designed to understand a
handful of words, two of which are tomorrow and today. When the
system first hears the tah phoneme, the spoken word can be either tomorrow
or today. The next phoneme parsed from the speech is m; the
probability that the word being spoken is today is now 0. Given our HMM,
the m phoneme is a legal state, so we transition and then process the
next phoneme. Given the probabilities at the transitions, the speech recognizer
can use these to take the most likely path through the chain to identify the
most likely phoneme that follows.
This example can be extended from phonemes to words. Given a
set of words that can be understood by a speech recognizer, a Markov chain can
be created that identifies the probabilities of a given word following another.
This chain would allow the recognizer to better identify which words were
spoken, based on their context (see Figure 15.3).
It's clear from these examples that HMMs can greatly
simplify tasks such as speech recognition and speech understanding. In this
example, the phoneme inputs caused the transition of states in the model to
define words. Further, word inputs caused a transition for contextual
understanding of a sentence. Next, we'll look at the use of HMMs to generate
symbols based on predefined or learned transition probabilities.
376
(Handwritten note at top left: "We must experiment
with Kurzweil's paraphrasing software.")
(FIGURE 15.4 Sample bigram from a corpus of seven unique
words. Diagram flow: Corpus -> Generated)
SAMPLE APPLICATION
(Handwritten margin note: "Could Ray Kurzweil's
"Paraphrasing" software be based on this? See website of Kurzweil.
using this, can we "rewrite" a resume")
Some suggest, using higher approximations of the HMM, that
it might be possible to mimic the works of great writers such as Shakespeare
[Zhang01]. By training the HMM with a corpus of the author's text, the HMM
could then be used to emit sequences of words that are statistically similar to
those from the training corpus.
For the sample application, we'll discuss the implementation
of a bigram HMM that can be trained with arbitrary text. The HMM will then be
used to generate random sequences of characters. (Handwritten note:
"eg: any text resume?")
The source code for the bigram HMM can be found on the
CD-ROM at /soft-ware/ch15/bigram/.
SOURCE DISCUSSION
(Handwritten notes: "(like creating a step-brother)
from a given Sample Resume? If such "paraphrasing / rewriting" of
resumes can be done Online (automatically) on our website, then we could add
one more element of FUN - even if the rewritten resume contains some absurd
text! In fact such "absurdity" may lend an element of FUN!
7-01-07")
The source for parsing text into bigram chains and then
building sentences from them is surprisingly simple. The bigram is implemented
as a simple two-dimensional array. Each dimension is represented by the unique
words that were parsed from the text. The first dimension is the first word of
a bigram, and the second dimension is the word that follows. The contents of
the two-dimensional array at this intersection are the number of times that the
second word follows the first.
The Bigram Model 385
LISTING 15.9 Emitted Text from Albert Einstein Quotes
Plaintext
$ ./bigram -f einstein
Imagination is shipwrecked by language and other symbolic
devices.
$ ./bigram -f einstein
We all ruled in the authority of imagination.
Each of the generated quotes from Listing 15.9 sounds
reasonable and is actually thought provoking.
Consider now generated text from a corpus of Albert Camus' Absurd
Man (see Listing 15.10).
LISTING 15.10 Emitted Text from Albert Camus' Absurd Man
Plaintext
$ ./bigram -f absurdman
It is to speak only truth that is the breath of future
actions.
$ ./bigram -f absurdman
"My field" said Goethe "is time and unfolds
in a disservice to make."
Finally, consider a Markov chain that was created from two
separate works (see Listing 15.11). The first work is the poem "Ode to
Joy" by German poet Friedrich Schiller, and the second from book one of The
Odyssey by Homer.
LISTING 15.11 Emitted Text from a Collection of Works
Plaintext
$ ./bigram -f combo
From chaos and beasts and hostile shores! From the woods the
hunter strayed.
(Handwritten note: "If we succeed in paraphrasing /
rewriting a text resume online, we could also generate / develop a
"Subliminal / Subconscious" Function Profile Graph!! (since keywords
would have got changed) This would be fantastic!!")
OWNERSHIP?
(Handwritten margin note: "Resume")
Although the Markov chain could be used to mimic a symphony
or the generation of text that appears similar to other literature, the
question arises as to who owns the new work? The Markov chain can emit music or
text that is modeled on the original training data. Therefore, though the
result is very similar to the original author's work, it is a new statistical
representation of the original work.
When trigram or larger models are used to model the original
work, the complexity and coherence of the resulting work becomes very
interesting.
388
development of Bots, which exist in the Internet to provide
capabilities to their users.
Agents are also called intelligent agents, because
intelligence is a key component of agency. Whereas agents can take various
forms, some consider agents to be surrogates on a network or the Internet that
could fulfill some activity useful to their user in the real world [King95].
The agent would be endowed with the wishes of its user and then make any
necessary decisions while communicating with other agents (possibly
representing other users). An example selling agent of this type may find other
buying agents at specially created auction hosts to sell goods for their user.
These agents could also deceptively act as buyers, to identify the costs of a
similar good for sale and adjust their prices accordingly.
(Handwritten margin note: "eg: Agents of Jobseekers
negotiating Salary, Terms etc. with Agent of Recruiters -")
These concepts can open the definition of agency to a large
variety of programs. Therefore, rather than specify exactly what an agent is,
we'll discuss some of the attributes of agents initially and then return to
provide a taxonomy of agents.
Agent Attributes
(Handwritten margin notes near header: "Virtual Job
Fair / Negotiation Platform for (1) Buyer's Agents (Recruiter) (2) Seller's
Agents (Jobseeker)")
Agents can have one or more attributes, as defined in Table
16.1. This section discusses each of these attributes.
TABLE 16.1 Common Attributes for Software Agents
|
Attribute
|
Definition
|
|
Autonomous
|
Operates independently from its user
|
|
Adaptive
|
Learns while it operates
|
|
Communicative
|
Communicates with its user or other agents
|
|
Collaborative
|
Works with other agents to reach its goal
|
|
Personal
|
Exhibits believable character behavior (emotion)
|
|
Mobile
|
Moves around its environment
|
One of the primary attributes associated with software
agents is autonomy. An agent is autonomous if it operates without the
constant direction of a human. Being autonomous implies that the agent has one
or more goals that can be achieved. Although goal-orientedness can be viewed as
a separate attribute, it is a necessary element of autonomy and, therefore,
covered as a subordinate. Having goals also implies that the agent has the
ability to plan, which brings us to the adaptive characteristic.
Agent-based Software 389
(Handwritten note at top: "> Put into my folder
all future / incoming resumes having percentile score of > []." /
"Now he has created an Agent which checks incoming resumes daily &
puts into folder "Resumes of Interest"")
An agent is adaptive if it can change its behavior
based on its experience. Being adaptive means that the agent has the ability to
learn and reason about its environment and own knowledge. Although this is the
most intriguing aspect of agency, it is also the most difficult and, therefore,
is commonly found only in very domain-specific agents.
(Handwritten margin note: "07-01-07")
The ability to communicate is also an important
characteristic of agents. The agent must be able to communicate with its user
to identify its goals or initial information as well as communicate in its
environment. For example, a search agent that identifies Web pages of interest must
be able to communicate using the HTTP (HyperText Transfer Protocol) to connect
to Web sites and gather Web pages. A related attribute is the ability to
communicate with other agents.
(Handwritten margin notes on right: "also an email
will go out to the recruiter concerned (alert)")
An agent is collaborative if it communicates with
other agents to achieve its goals. For example, agents that act on behalf of
their users in auction environments can communicate to broker deals, given
information by their users. Collaborative agents are commonly studied under the
name multiagent systems, because multiple agents are required for
collaboration. This attribute, important for software agents, is a widely
studied and researched characteristic.
For some special agents, the ability to exhibit a personality
can be important. Such agents are commonly found in entertainment, but research
in the domain of emotion has found that intelligence and emotion are linked.
Therefore, allowing an interface agent to exhibit a personality that changes
with the information to be portrayed can simplify our ability to understand
what the agent is trying to communicate. For example, if we try to communicate
information without changing our expression, it can be difficult for the
receiver to understand exactly what we're trying to get across. The information
encoded in our expression represents meta data for our actual message.
Therefore, providing this ability to certain classes of agents can be
important.
Finally, some agents are provided with mobility, or
the ability to move in their environment. This may seem like an odd attribute,
but it can be important in some circumstances. For example, consider an agent
that communicates with a remote database to gather information. In the
traditional case, the host communicates with the remote database, gathers the
defined information, and then filters this information for the user based on
the specific criteria. Given mobility, an agent could be dispatched to the
remote database to automatically filter the results and then return only what
was required by the end user. (Handwritten note: "like our Guru
Grab?") This arrangement provides both network-bandwidth savings and a
simpler architecture, especially when the two hosts can be disconnected from
one another for durations.
To be classified as an agent, a program does not have to
demonstrate all of the previously described attributes. In most cases, only two
or more are used. In our simple application, to be discussed later, the
autonomous and communicative attributes will be applied to a news-filtering
agent.
390
Agent Taxonomy
Now let's return to a broader scope of agents and identify
some of the higher-level types that exist using the previously defined
attributes (see Figure 16.1).
(FIGURE 16.1 Franklin and Graesser's agent taxonomy.
Hierarchy tree showing: Autonomous Agents -> Other Agents / Software Agents
/ Artificial Life Agents -> Task Specific Agents / Entertainment Agents /
Viruses)
Because we're interested in agents only that operate
autonomously, we'll use Franklin and Graesser's 1996 taxonomy [Franklin96].
Although many other classifications exist, we'll focus specifically on the
software-agents variety from Franklin and Graesser's taxonomy.
Task-Specific Agents
(Handwritten margin note: "Guru Grab / Guru
Gem")
A task-specific agent is one that is deployed to solve a
specific problem. An example of a task-specific agent is a Web search agent. In
addition to performing searches given the user's constraints, a Web search
agent also monitors which of the returned links the user follows. This
measurement provides a weighting scheme for searches to help better sort the
results with the hope of providing the user what they want more quickly. The
Web search agent could also operate in the background, doing earlier searches
to see if new information has become available, and then presenting this to the
user.
In addition to being autonomous, the Web search agent is
adaptive because it learns what the user is most interested in based on his
behavior (that is, what links he actually follows).
392
(FIGURE 16.2 Providing agents with decision-making
capabilities. Diagram showing Intelligent Agent surrounded by: Neural Networks,
Knowledge-Based Systems, Natural Language Processing, Decision Trees, Genetic
Algorithms, Bayes Theorem, Fuzzy Logic, Clustering Algorithms)
Reinforcement learning algorithms (Chapter 9) and learning
classifier systems (Chapter 6) are useful mechanisms for intelligent agents
because they include the ability learn in the environment.
The use of forward-chaining, rules-based systems is
discussed in Chapter 12. The rules-based system permits an agent to reason
about its environment given a set of rules and facts that describe its
environment. An important characteristic of rules-based systems is that they
can describe their line of reasoning (what facts lead to a particular
decision).
Clustering algorithms (such as adaptive resonance theory,
described in Chapter 5) are another useful technique for agent intelligence. These
algorithms permit agents to identify relationships in their environment, which
can help an agent learn patterns without any instruction (unsupervised
learning).
Numerous other methods can be used, some of which were
described in prior chapters. Fuzzy logic (described in Chapter 13) is also
useful as an element for intelligent agents, as is simulated annealing
(described in Chapter 3) for constraint satisfaction.
394
search terms matched. The user can then click the link for
the particular monitored Web site or news item and be taken directly to that
content.
The goal of the agent is to simplify news reading for a
user, filtering out content that may not be of interest and presenting first
what should be of most interest to the user.
WebAgent Characteristics
The WebAgent represents a simple agent and includes no
learning ability. Its characteristics include autonomy (it works in the
background without user direction) and its communicative ability with external
servers for data collection.
The WebAgent's sensors are the standard application layer
protocols that allow it to gather the information that it needs for its user,
based on predefined search criteria. The HTTP Web protocol is also used to
communicate results back to the user. The user then connects to the WebAgent,
just as it would any other Web server.
The source code for the WebAgent application can be found on
the CD-ROM at /software/ch16.
SOURCE DISCUSSION
Now let's walk through the source for the WebAgent. To more
easily understand the overall structure of the WebAgent, consider the data flow
shown in Figure 16.4.
Data collection, which feeds data up to the data
repositories, occurs on a timed basis (every 10 minutes). Using the search
criteria stored in the configuration file (predefined by the user), the data is
pruned. When the user requests the current information via the Web page, the
HTML generator constructs a dynamic Web page that is served back through the
HTTP server (see Figure 16.5).
The user can then view specific news items by clicking the
links (see Figure 16.6).
When the user completes reading the articles of interest, he
can click the Mark Read button to clear the current news set. This information
is saved at the WebAgent so that these news items will not be seen again.
Although the configuration is defined in a file outside of
the WebAgent, the user can review the configuration settings through the
WebAgent. The current configuration settings are presented by requesting the
file config.html (see Figure 16.7).
The following sections will describe the WebAgent software
in the layers as defined by Figure 16.4. The Web interfaces layer provides the
ability to communicate with external data servers using standard protocols. The
user instruction layer defines how a user will instill the agent its knowledge
of the user's search constraints. The data collection and filtering layer
performs the actual filtering of incoming data
438
REFERENCES
[Franklin96] Franklin, S., and A. Graesser, Is It
an Agent or Just a Program? A Taxonomy for Autonomous Agents. Proceedings
of the Third International Workshop on Agent Theories, Architectures, and
Languages. New York: Springer Verlag, 1996.
[Kay84] Kay, Alan, "Computer Software," Scientific
American, 251(3): 53–59, September 1984.
[King95] King, J., "Intelligent Agents: Bringing
Good Things to Life," AI Expert: 17–19, February, 1995, available
online at
[http://coqui.lce.org/cedu5100/Intelligent_Agents.htm](http://coqui.lce.org/cedu5100/Intelligent_Agents.htm),
accessed January 17, 2003.
RESOURCES
Ananova Ltd., Ananova Agent, available online at
[www.ananova.com/video](https://www.ananova.com/video), accessed January 18,
2003.
BotSpot, [www.botspot.com](https://www.botspot.com).
Bradshaw, J., Software Agents, AAAI Press/MIT Press,
1997.
SourceForge, Aglet Software Development Kit, available
online at
[http://sourceforge.net/projects/aglets/](http://sourceforge.net/projects/aglets/),
accessed January 18, 2003.
University of Maryland Baltimore County, Agent Web,
available online at [http://agents.umbc.edu/](http://agents.umbc.edu/),
accessed January 18, 2003.
(Handwritten note: "Look these up" with an
arrow pointing to the resource links)
AI Today 441
that these robot pets (including their more productive
vacuum cleaner counter-parts) trigger the human nurturing response in their
owners [Wired03].
COMMONSENSE REASONING AND CYC
Minsky identified one of the primary problems of expert
systems today—although they include a large mass of knowledge about a
particular domain, they lack common sense [Minsky92]. Consider the example of
an expert system and a chess-playing program. Both are reasonably intelligent
in the tiny domain for which they exist, but the expert system knows nothing
about chess, and the chess-playing program is unable to reason about anything
but selecting a chess move. In other words, these intelligent programs are
useless outside of their particular expertise. Perhaps if these systems were
endowed with some kind of common sense, they could communicate with each other
and perhaps even cooperate.
One of the most visible commonsense reasoning projects today
is the CYC project at Cycorp®. This project is led by Doug Lenat. (We'll see
this name again in the domain of scientific discovery.) The original goal of
CYC was to develop a knowledge base containing a massive amount of commonsense
knowledge. In addition to simple facts, the knowledge base also includes
assertions (rules) that relate facts. CYC includes microtheories that bundle
assertions for a particular domain of knowledge to support and optimize the
inference process. The inference engine supports reasoning about the facts in
the knowledge base.
Cycorp has recently released OpenCyc, which is an
open-source version of the CYC technology. OpenCyc includes a knowledge base
(6,000 concepts with 60,000 assertions), the CYC inference engine, and a number
of language bindings and APIs to support software development with the
knowledge base.
(Handwritten note: "May be we can dump if useful in
our narrow domain of Online Recruitment" with bracket pointing to } p =
44)
AUTONOMIC COMPUTING
At Artificial Life IV workshop in 1994, Jeffrey O. Kephart
of IBM presented the paper, "A Biologically Inspired Immune System for
Computers." In this paper, Kephart described an antivirus architecture
that modeled an immune system for computers and computer networks. Other
biologically motivated ideas in this paper include the use of self-replication
to fight virus self-replication.
IBM has since moved forward with an aggressive strategy of
building self-managing computer systems based on autonomic principles. The four
key areas they identify for their self-managing systems follow:
Self-configuring: Adapting to dynamic environments
Appendix B | About the CD-ROM
457
The CD-ROM contains a number of useful applications that
demonstrate the properties of AI algorithmic techniques and methods. The
methods and applications that demonstrate them are noted in this section.
PATHFINDING ALGORITHM
Pathfinding algorithms, specifically the A-Star algorithm,
are explored in Chapter 2. A nonuniform reward landscape is used to demonstrate
the optimal pathfinding abilities of the A-Star algorithm. Also provided on the
CD-ROM are demonstrations of the depth-first search and breadth-first search
algorithms. These can be found on the CD-ROM at /software/ch2.
SIMULATED ANNEALING
Simulated annealing, or modeling of systematic cooling of a
molten metal to a solid, is described in Chapter 3. The theoretical N-Queens
problem is used to demonstrate the constraint satisfaction properties of the
algorithm. The algorithm and application can be found on the CD-ROM at
/software/ch3.
PARTICLE SWARM OPTIMIZATION
Particle Swarm Optimization (PSO) is a swarm intelligence
algorithm that uses a population of loosely dependent particles to solve a
variety of problems. We use PSO here to demonstrate function optimization
(finding the combination of parameters that maximize the results of a given
function). The algorithm and applica-
458
tion to maximize the sombrero function is provided on the
CD-ROM at /software/ch4.
ADAPTIVE RESONANCE THEORY
Adaptive Resonance Theory (ART1) is a clustering algorithm
that provides the ability to separate (or cluster) elements in a data set into
independent data sets based on properties of the individual data items. The
algorithm does this in an unsupervised manner, allowing the algorithm to find
patterns in the data that a user may not notice. The practical problem of
personalization is used to demonstrate ART1 in the context of a recommender
system in Chapter 5. The algorithm and application can be found on the CD-ROM
at /software/ch5.
CLASSIFIER SYSTEMS
In Chapter 6, we explore one of the older learning
algorithms in AI, the learning classifier system (LCS). LCS is a class of
algorithms that learn condition/action rules based on rewards received from the
target environment. We demonstrate the basic LCS in an obstacle grid world,
where the agent learns sets of classifiers to avoid running into obstacles. The
sample application of LCS can be found on the CD-ROM at /software/ch6.
ANT ALGORITHMS
Ant algorithms are a relatively new method that can be used
to identify optimal paths through a graph. This method is described in Chapter
7. Ant algorithms model the movement of ants in an environment and use a
simulated pheromone to communicate with other ants (the process of stigmergy).
The Traveling Salesman Problem (TSP) is used to demonstrate the ant algorithm.
The algorithm and application can be found on the CD-ROM at /software/ch7.
BACKPROPAGATION ALGORITHM
The backpropagation algorithm, discussed in Chapter 8, is
one of the primary methods used to train multilayer neural networks given a
training set and a set of desired outputs. Backpropagation propagates errors
back through the nodes of a network, altering the weights of the connections
based on the error of the actual
About the CD-ROM 459
and desired outputs. The interesting problem of training
game neurocontrollers (game AI) is used to demonstrate backpropagation. Given a
simple neural network, a set of environmental inputs, and a set of allowable
actions (otherwise known as the training set), the algorithm trains the network
to perform the desired action for the current environment. It is then
demonstrated that the neurocontroller is able to generalize and perform useful
behaviors for unforeseen environments. The backpropagation algorithm and
neurocontroller application can be found on the CD-ROM at /software/ch8.
REINFORCEMENT LEARNING
Reinforcement learning, the topic of Chapter 9, is an
interesting state-space/action search and optimization algorithm that learns
probability transitions for a given problem. We demonstrate the Q learning
algorithm of reinforcement learning in a problem landscape that includes both
obstacles and variable rewards for getting from a start to goal position. The
Q-learning example is provided on the CD-ROM at /software/ch9.
GENETIC ALGORITHMS/GENETIC PROGRAMMING
Genetic algorithms, described in Chapter 10, provide a novel
optimization technique that can be applied to both numerical and symbolic
problems. The subfield of genetic programming is further used to illustrate the
creation of instruction sequences to solve problems in code generation.
Sequences of instructions are evolved to solve mathematical functions. These
sequences can find novel strings that are both interesting and optimal, given a
simple virtual machine. The genetic programming algorithm and application can
be found on the CD-ROM at /software/ch10.
ARTIFICIAL LIFE/EVOLVING NEURAL NETWORKS
Artificial life, discussed in Chapter 11, is studied here in
the context of neural networks through evolution of simple organisms in a
synthetic environment. Organisms survive through successfully existing in their
environment, avoiding prey, and foraging for food. Organisms are permitted to
reproduce, once they reach a high enough level of internal energy. Therefore,
reproduction is permitted only if organisms can survive in the environment,
which should lead to more fit organisms. The two types of organisms are
provided with multilayer neural networks as their
460
neurocontrollers to illustrate simple food web
organizations. The artificial life application can be found on the CD-ROM at
/software/ch11.
EXPERT SYSTEMS
Rules-based systems are the topic of Chapter 12, which shows
the emphasis and implementation of a forward-chaining system. Varieties of
examples are provided, in the form of rules and initial facts, with a final
example of integrating the rules-based system into an embedded system and
utilizing it for sensor fault-tolerance. The forward-chaining rules-based
system and application files can be found on the CD-ROM at /software/ch12.
FUZZY LOGIC
In Chapter 13, fuzzy logic and fuzzy control are described,
including an implementation of a fuzzy API for inclusion into other
applications. The API provides not only the standard fuzzy operators but also
helper functions that support the simple creation of fuzzy membership
functions. The fuzzy logic API and a simple battery charger example is provided
on the CD-ROM at /software/ch13.
NATURAL LANGUAGE PROCESSING
Chapter 14 introduces the problem of natural language
processing. We explore a simple predictive parser in this chapter to parse
simple English language sentences. In addition, we exploit the minimal example
to build a knowledge frame once the sentence has been parsed. The natural
language processing source is provided on the CD-ROM at /software/ch14.
HIDDEN MARKOV MODELS
Hidden Markov models, which are networks that include states
and transitions with associated probabilities, are the topic of Chapter 15. The
outcome, or observation, of a state is generated based on the associated
probability distribution. The action is performed—made visible—though the
internal state is hidden, thus the hidden aspect of the Markov model. Hidden
Markov models have a variety of applications; in Chapter 15 we look at the
generation of meaningful text based on
About the CD-ROM 461
training by a corpus. The HMM and a text-generation example
is provided on the CD-ROM at /software/ch15.
INTELLIGENT AGENTS
Intelligent agents are the final topic in the book, covered
in Chapter 16, with emphasis on search and filtering agents. Intelligent agents
are applied in a number of different ways; the application chosen for this
chapter is a filtering agent that acts as an intermediary to UseNet sites on
the Internet. The WebAgent is configured through a simple configuration file. It
then autonomously gathers news using the NNTP protocol and presents it to the
user with the HTTP protocol (acting as a simple Web server). The WebAgent is
provided on the CD-ROM at /software/ch16.
SYSTEM REQUIREMENTS
Applications on this CD-ROM require a PC with Windows 95,
98, 2000, Me, or XP using the Cygwin Unix environment (freely downloadable at
[www.cygwin.com](https://www.cygwin.com)), or Linux (Red Hat 6.1 or later, or
comparable Linux distribution); 486 or higher CPU; 64MB RAM; 60MB disk space;
CD-ROM drive; Internet access and Web browser (for the WebAgent example)
