Reinforcement Learning: Parallelizing Genetic Algorithms

Reinforcement Learning 78
Learning Task 79
IV Q Learning 82
Evaluating Hypotheses 86
Basics of Sampling Theory 88
Genetic Algorithms 92
An Illustrative Example 96
Hypothesis Space Search 98

V
Genetic Programming 101
Models of Evolution and Learning 104
105
Parallelizing Genetic Algorithms.
UNIT I
Introduction to Machine Learning
1. Introduction
1.1 What Is Machine Learning?

Machine learning is programming computers to optimize a performance criterion using example
data or past experience. We have a model defined up to some parameters, and learning is the
execution of a computer program to optimize the parameters of the model using the training data or
past experience. The model may be predictive to make predictions in the future, or descriptive to gain
knowledge from data, or both.
Arthur Samuel, an early American leader in the field of computer gaming and artificial intelligence,
coined the term “Machine Learning” in 1959 while at IBM. He defined machine learning as “the field of
study that gives computers the ability to learn without being explicitly programmed.” However, there is
no universally accepted definition for machine learning. Different authors define the term differently.
Definition of learning
Definition
A computer program is said to learn from experience E with respect to some class of tasks T and
performance measure P, if its performance at tasks T, as measured by P, improves with experience E.
Examples
i) Handwriting recognition learning problem
• Task T: Recognising and classifying handwritten words within images
• Performance P: Percent of words correctly classified
• Training experience E: A dataset of handwritten words with given classifications
ii) A robot driving learning problem
• Task T: Driving on highways using vision sensors
• Performance measure P: Average distance traveled before an error
• training experience: A sequence of images and steering commands recorded while
observing a human driver
iii) A chess learning problem
• Task T: Playing chess
• Performance measure P: Percent of games won against opponents
• Training experience E: Playing practice games against itself
Definition
A computer program which learns from experience is called a machine learning program or
simply a learning program. Such a program is sometimes also referred to as a learner.
1.2 Components of Learning
Basic components of learning process

The learning process, whether by a human or a machine, can be divided into four components,
namely, data storage, abstraction, generalization and evaluation. Figure 1.1 illustrates the
variouscomponents and the steps involved in the learning process.
1
1. Data storage
Facilities for storing and retrieving huge amounts of data are an important component of the
learning process. Humans and computers alike utilize data storage as a foundation for advanced
reasoning.
• In a human being, the data is stored in the brain and data is retrieved using electrochemical signals.
• Computers use hard disk drives, flash memory, random access memory and similar devices to store
data and use cables and other technology to retrieve data.
2. Abstraction
The second component of the learning process is known as abstraction.
Abstraction is the process of extracting knowledge about stored data. This involves creating general
concepts about the data as a whole. The creation of knowledge involves application of known models
and creation of new models.
The process of fitting a model to a dataset is known as training. When the model has been trained, the
data is transformed into an abstract form that summarizes the original information.
3. Generalization
The third component of the learning process is known as generalisation.
The term generalization describes the process of turning the knowledge about stored data into a form
that can be utilized for future action. These actions are to be carried out on tasks that are similar, but
not identical, to those what have been seen before. In generalization, the goal is to discover those
properties of the data that will be most relevant to future tasks.
4. Evaluation
Evaluation is the last component of the learning process.
It is the process of giving feedback to the user to measure the utility of the learned knowledge. This
feedback is then utilised to effect improvements in the whole learning process
Applications of machine learning

Application of machine learning methods to large databases is called data mining. In data
mining, a large volume of data is processed to construct a simple model with valuable use, for example,
having
high predictive accuracy.
The following is a list of some of the typical applications of machine learning.

1. In retail business, machine learning is used to study consumer behaviour.
2. In finance, banks analyze their past data to build models to use in credit applications, fraud
detection, and the stock market.
3. In manufacturing, learning models are used for optimization, control, and troubleshooting.
2
4. In medicine, learning programs are used for medical diagnosis.
5. In telecommunications, call patterns are analyzed for network optimization and maximizing the
quality of service.
6. In science, large amounts of data in physics, astronomy, and biology can only be analyzed fast
enough by computers. The World Wide Web is huge; it is constantly growing and searching for
relevant information cannot be done manually.
7. In artificial intelligence, it is used to teach a system to learn and adapt to changes so that the
system designer need not foresee and provide solutions for all possible situations.
8. It is used to find solutions to many problems in vision, speech recognition, and robotics.
9. Machine learning methods are applied in the design of computer-controlled vehicles to steer
correctly when driving on a variety of roads.
10. Machine learning methods have been used to develop programmes for playing games such as
chess, backgammon and Go.
1.3 Learning Models

Machine learning is concerned with using the right features to build the right models that
achieve the right tasks. The basic idea of Learning models has divided into three categories.
For a given problem, the collection of all possible outcomes represents the sample space or instance
space.
 Using a Logical expression. (Logical models)

 Using the Geometry of the instance space. (Geometric models)
 Using Probability to classify the instance space. (Probabilistic models)
 Grouping and Grading
1.3.1 Logical models

Logical models use a logical expression to divide the instance space into segments and hence
construct grouping models. A logical expression is an expression that returns a Boolean value, i.e., a
True or False outcome. Once the data is grouped using a logical expression, the data is divided into
homogeneous groupings for the problem we are trying to solve. For example, for a classification
problem, all the instances in the group belong to one class.
There are mainly two kinds of logical models: Tree models and Rule models.
Rule models consist of a collection of implications or IF-THEN rules. For tree-based models, the ‘if-part’
defines a segment and the ‘then-part’ defines the behaviour of the model for this segment. Rule models
follow the same reasoning.
Logical models and Concept learning

To understand logical models further, we need to understand the idea of Concept Learning.
Concept Learning involves learning logical expressions or concepts from examples. The idea of Concept
Learning fits in well with the idea of Machine learning, i.e., inferring a general function from specific
training examples. Concept learning forms the basis of both tree-based and rule-based models. More
formally, Concept Learning involves acquiring the definition of a general category from a given set of
positive and negative training examples of the category. A Formal Definition for Concept Learning is
“The inferring of a Boolean-valued function from training examples of its input and output.” In
concept learning, we only learn a description for the positive class and label everything that doesn’t
satisfy that description as negative.
3
The following example explains this idea in more detail.
A Concept Learning Task called “Enjoy Sport” as shown above is defined by a set of data from
some example days. Each data is described by six attributes. The task is to learn to predict the value of
Enjoy Sport for an arbitrary day based on the values of its attribute values. The problem can be
represented by a series of hypotheses. Each hypothesis is described by a conjunction of constraints on
the attributes. The training data represents a set of positive and negative examples of the target
function. In the example above, each hypothesis is a vector of six constraints, specifying the values of
the six attributes – Sky, AirTemp, Humidity, Wind, Water, and Forecast. The training phase involves
learning the set of days (as a conjunction of attributes) for which Enjoy Sport = yes.
Thus, the problem can be formulated as:
 Given instances X which represent a set of all possible days, each described by the attributes:
o Sky – (values: Sunny, Cloudy, Rainy),
o AirTemp – (values: Warm, Cold),
o Humidity – (values: Normal, High),
o Wind – (values: Strong, Weak),
o Water – (values: Warm, Cold),
o Forecast – (values: Same, Change).
Try to identify a function that can predict the target variable Enjoy Sport as yes/no, i.e., 1 or 0.
1.3.2 Geometric models

In the previous section, we have seen that with logical models, such as decision trees, a logical
expression is used to partition the instance space. Two instances are similar when they end up in the
same logical segment. In this section, we consider models that define similarity by considering the
geometry of the instance space. In Geometric models, features could be described as points in two
dimensions (x- and y-axis) or a three-dimensional space (x, y, and z). Even when features are not
4
intrinsically geometric, they could be modelled in a geometric manner (for example, temperature as a
function of time can be modelled in two axes). In geometric models, there are two ways we could
impose similarity.
 We could use geometric concepts like lines or planes to segment (classify) the instance space.
These are called Linear models.
 Alternatively, we can use the geometric notion of distance to represent similarity. In this case, if
two points are close together, they have similar values for features and thus can be classed as
similar. We call such models as Distance-based models.
Linear models
Linear models are relatively simple. In this case, the function is represented as a linear
combination of its inputs. Thus, if x1 and x2 are two scalars or vectors of the same dimension
and a and b are arbitrary scalars, then ax1 + bx2 represents a linear combination of x1 and x2. In the
simplest case where f(x) represents a straight line, we have an equation of the form f (x)
= mx + c where c represents the intercept and m represents the slope.
Linear models are parametric, which means that they have a fixed form with a small number of numeric
parameters that need to be learned from data. For example, in f (x) = mx + c, m and c are the
parameters that we are trying to learn from the data. This technique is different from tree or rule
models, where the structure of the model (e.g., which features to use in the tree, and where) is not
fixed in advance.
Linear models are stable, i.e., small variations in the training data have only a limited impact on the
learned model. In contrast, tree models tend to vary more with the training data, as the choice of a
different split at the root of the tree typically means that the rest of the tree is different as well. As a
result of having relatively few parameters, Linear models have low variance and high bias. This implies
that Linear models are less likely to overfit the training data than some other models. However, they
are more likely to underfit. For example, if we want to learn the boundaries between countries based
on labelled data, then linear models are not likely to give a good approximation.
Distance-based models
Distance-based models are the second class of Geometric models. Like Linear models, distance-
based models are based on the geometry of data. As the name implies, distance-based models work on
the concept of distance. In the context of Machine learning, the concept of distance is not based on
merely the physical distance between two points. Instead, we could think of the distance between two
points considering the mode of transport between two points. Travelling between two cities by plane
5

Reinforcement Learning: Parallelizing Genetic Algorithms

Uploaded by

Copyright:

Available Formats

Reinforcement Learning: Parallelizing Genetic Algorithms

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Reinforcement Learning: Parallelizing Genetic Algorithms

Uploaded by

Copyright:

Available Formats

Reinforcement Learning 78

Basics of Sampling Theory 88

Hypothesis Space Search 98

Models of Evolution and Learning 104

1.1 What Is Machine Learning?

1.2 Components of Learning

Basic components of learning process

Applications of machine learning

The following is a list of some of the typical applications of machine learning.

1.3 Learning Models

 Using a Logical expression. (Logical models)

1.3.1 Logical models

Logical models and Concept learning

Thus, the problem can be formulated as:

1.3.2 Geometric models

You might also like