All rights reserved.

Reproduction and/or distribution in whole or in

part in electronic, paper or other forms without written permission
is prohibited.

Natural Language Processing ReferencePoint

Suite
SkillSoft Corporation. (c) 2003. Copying Prohibited.

Reprinted for Fernando Balbachan, VerizonBusiness

[Link]@[Link]

Reprinted with permission as a subscription benefit of Books24x7,

[Link]
 i

Table of Contents
Point 2: Memory−Based Learning...................................................................................................1

Introducing Memory−Based Learning............................................................................................2

How Memory−Based Learning Works....................................................................................2
Memory−Based Learning Algorithms......................................................................................3
Modifying the K−Nearest Neighbor Rule.................................................................................5
How to Reduce the Size of the Vector Space.........................................................................6

Types of Memory−Based Learning.................................................................................................9

Rote Learning.........................................................................................................................9
Parameter Adjustment Learning...........................................................................................10
Analogical Learning..............................................................................................................11
Cluster Learning....................................................................................................................14
Incremental Learning............................................................................................................15
Reinforcement Learning........................................................................................................17

Implementing Memory−Based Learning......................................................................................18

Neural Networks...................................................................................................................18
Genetic Algorithms................................................................................................................25

Related Topics................................................................................................................................28
Point 2: Memory−Based Learning
Pankaj Kaushik
Natural language processing (NLP) systems use learning techniques to process natural languages,
such as English, Japanese, and Korean. Learning techniques apply the experience that is gained
from processing previous natural language (NL) elements to process new NL elements, such as
words and sentences. The most commonly used learning technique in NLP systems is
memory−based learning in which processed NL elements are stored in memory to record the
experience on which to base the processing of new NL elements.

This ReferencePoint introduces memory−based learning and describes the various types of
memory−based learning in NLP. It also explains how to implement memory−based learning.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Introducing Memory−Based Learning
The two classes of learning methods in NLP are: lazy and eager. Memory−based learning is a lazy
learning method because it does not extract information from the processed NL elements in
memory until a new NL element needs to be processed. Eager learning methods, such as
decision−tree algorithms and rule−induction algorithms, work on processed NL elements that are
stored in the computer memory to extract additional information, such as rules and deduction
principles. The extracted rules help process new instances of natural language words.

Figure 2−2−1 shows the lazy and eager learning methods used in NLP:

Figure 2−2−1: Classification of Learning Methods

The advantages of memory−based learning in NLP are:

• Availability of information: Stores all the instances of processed NL elements. This collection
ensures that all the available processed instances are factored in before generating the
output of a new NL element.

• Robustness: Handles a large number of processed instances with a large number of

attributes, such as size, shape, and orientation.
Note Memory−based NLP systems process data with varied formats, sizes, and attributes.

• Elimination of abstraction: Avoids preprocessing on processed NL elements to generate

rules for processing new NL elements. This method reduces the processing time for an
individual instance because no rules are induced from existing processed NL elements. In
addition, the processing involves only a comparison of the new and processed NL elements.

• Reusability: New NL elements can reuse information about the processed NL elements.

How Memory−Based Learning Works

In memory−based learning, all the processed NL elements are stored in memory as input/output
(I/O) pairs in the form:
(Xi, Xo)
Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 3

Where, Xi represents the input and Xo represents the response or the output.

For example, an alphabet recognition system is a memory−based NLP system. This system accepts
a handwritten English alphabet as input and returns a computer−generated alphabet as output that
best matches the input. You input the handwritten alphabet through an input device, such as a
stylus. The output appears on the monitor. All the processed NL elements are stored in memory as
Xi/Xo pairs, where Xi represents the handwritten alphabet and Xo represents the output that best
matches the handwritten alphabet.

Xo can be assigned 26 different values because English contains that many alphabets. Each
alphabet has a unique corresponding Xo value. Based on specific features, such as height, width,
shape, and curve, of the input alphabet, an instance−selecting algorithm first creates a set of similar
handwritten alphabets that are stored in the database. The algorithm analyzes this set and selects
an alphabet that best matches the input. The algorithm then declares the output class, Xo, of the
selected processed alphabet as the output class of the input alphabet and stores the new I/O pair
as a data structure in memory. You can easily retrieve or modify information that is stored in data
structures, such as arrays, linked lists, stacks, trees, and graphs.

Each attribute of an NL element is associated with a numeric value and a collection of these
numeric values forms a vector. A unique vector represents each processed NL element. These
vectors are compared with the input vector of the new NL element to determine the closest match
with the input. The memory with all the I/O pairs is an open vector space. A separate node in the
open vector space represents each I/O pair of a processed item.

The location of a node depends on its similarity with its neighboring nodes. Similar nodes form a
local neighborhood. The dimension of the open vector space is equal to the number of attributes
that define an input NL element.

To implement memory−based learning:

1. Create the initial memory space that contains the nodes, which represent the I/O pairs of the
processed NL elements.

2. Accept a new NL element to process.

3. Select a set of similar NL elements that constitutes the local neighborhood of the new NL
element to process.

4. Analyze the neighborhood NL elements of the new NL element using an algorithm.

5. Generate the finalized output.

6. Store the I/O pair as a data structure in memory.

Memory−Based Learning Algorithms

All memory−based learning algorithms first select the processed NL elements that form the local
neighborhood of the new NL element to process. Next, these algorithms apply a learning rule to the
local neighborhood NL elements to finalize the output.

All memory−based learning algorithms evolve from a rule, called the nearest neighbor rule. For
example, Xi is the input vector of a processed NL element and Xo is the output class that is
associated with this element. The number of processed NL elements that is stored in memory is n.
The input vector of a new NL element is Xy that needs to be processed. The input vector of the new
NL element is compared with the input vectors of the processed NL elements from X1 through Xn.
The nearest neighbor rule finds the processed NL element that has an input vector similar to the NL
Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 4

element to process, using the following similarity measure:

Min[d(Xi, Xy)]

Where, i ranges from 1 through n. The Min[] function returns the smallest value of arguments that is
passed to it. The notation, d(Xi, Xy), is the Euclidean distance between the vectors, Xi and Xy. The
Euclidean distance is the shortest absolute distance between two vectors. It is expressed as
((x 1−y1)2+(x2−y2)2) for two−dimensional (2−D) vectors, X and Y, and (£I=1n(Xi−yi) 2) for n
dimensional vectors, X and Y.

Note Other commonly used distance metrics are Manhattan distance and Mahalanobis distance.
Manhattan distance is L1 normal metric, Euclidean distance is L2 normal metric, and
Mahalanobis is L? normal distance metric. A normal metric is a metric that is expressed in the
normalized form, which is a standard way to represent values. The generic distance between
two points is represented by Lm.

For 2−D vectors, X and Y, various L normal metrics are expressed as:

• Lm metric distance: ((x1−y1)m+(x2−y2)m)1/m

• L1 metric distance: (x1−y1)+(x2−y2)

• L? metric distance: max((x1−y1), (x2−y2))

The k−nearest neighbor rule is a modification of the nearest neighbor rule. In the k−nearest
neighbor rule, instead of finding the nearest neighbor of the new NL element, k−processed NL
elements are selected, which form the local neighborhood of the new NL element. The output class
that appears the maximum number of times in the set of k−nearest neighbors is declared the output
class of the new NL element.

Figure 2−2−2 shows the vector space in the nearest neighbor and the k−nearest neighbor rule:

Figure 2−2−2: Nearest Neighbor Vector Space

In the nearest neighbor rule, X is the node that has the minimum Euclidean distance, which is
represented by arrows. The nearest neighbor rule predicts X as the output class of the unprocessed
NL element. In the k−nearest neighbor rule, with k=6, six nodes form the local neighborhood of the
NL element to process. Of the six, X contains the maximum frequency, 4. As a result, the k−nearest
neighbor rule predicts X as the output class of the new NL element.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 5

The formula to obtain the value of k in the k−nearest neighbor rule is:
k=N

Where, k is the nearest number of neighbors and N is the total number of processed NL elements in
memory.

The advantage of the k−nearest neighbor rule over the nearest neighbor rule is that the k−nearest
neighbor rule nullifies NL elements with low frequency that constitute the local neighborhood of the
new NL element. This nullification deletes single−instance NL elements and exceptions, which often
result in erroneous predictions. Single−instance NL elements are those NL elements that occur only
once in the local neighborhood of a new NL element. An exception is a discrete processed NL
element that has an output class that is different from the output class of its neighbors.

Modifying the K−Nearest Neighbor Rule

Various memory−based algorithms are modified or add−on versions of the k−nearest neighbor rule.
These modifications were introduced because of the following disadvantages of memory−based
methods:

• Sparse data: Distributes the instances of the processed NL elements nonuniformly in the
vector space.

• Equal weight attached to NL element features: Accords equal importance to all the features
of the NL elements. This weighting results in inaccurate predictions because the similarity
measure includes irrelevant and redundant features.

• Equal weight attached to processed NL elements: Accords equal importance to all the
processed NL elements that are part of the local neighborhood of the new NL element.

The discontinuous or discrete output that the k−nearest neighbor rule generates because of sparse
input data lowers its accuracy.

The modifications to the k−nearest neighbor rule are:

• Simple average: Calculates the simple average of the output values of the NL elements that
constitute the local neighborhood of the NL element to process.

• Weighted average: Calculates the weighted average of the output values by associating
different weights with different neighbor NL elements. This calculation solves the equal
weight problem of the k−nearest neighbor rule.

The k−nearest neighbor rule can use an average function to predict the output class of the new NL
element. This average function reduces the chances of false prediction if the distribution of the
output classes is continuous. If an average function is used on different unprocessed NL elements
that have the same nearest neighbors, the algorithm predicts the same output class for all the
unprocessed NL elements.

The nodes that belong to a particular output class tend to form a local region in the vector space.
The space between two local regions forms edges and boundaries, which result in discontinuities in
the average k−nearest neighbor rule. A weighted average function smoothes out these
discontinuities and associates different weights to various neighborhood instances.

Figure 2−2−3 shows the weighted functions in the k−nearest neighbor rule:

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 6

Figure 2−2−3: Weighted Functions in the K−Nearest Neighbor Rule

The step weighted function assigns a weight=1 to every NL element within a distance, d, from the
new NL element. All other NL elements are assigned a weight=0. This process eliminates those
processed instances in the local neighborhood of the new NL element that have a low similarity
value.

The linear weighted function assigns weights that are proportional to the distance between the
processed NL elements in the neighborhood and the new NL element.

The asymptotic graph contains two asymptotes, one along the x−axis and the other along the
y−axis. The decrease in the weights of nodes that are separated by significant distances is not
proportional to the increase in the distance. If the number of these far−off nodes is large, they
collectively outweigh the k−nearest neighbor instances. This process affects the accuracy of the
output class prediction.

The Gaussian function adjusts the collective overweighing by the far−off nodes, using the formula:
Wi = exp( −((x1−y1)2+(x2−y2)2)/KW2)

Where, Wi is the weight of the processed NL element with the input vector, X; Y is the input vector
of the new NL element; and KW is the kernel width of the weighted function. When KW increases, the
weights of the processed NL elements approach 1 and the Gaussian function becomes a simple
average. When KW decreases, the weights of the NL elements approach 0 and the function
becomes the k−nearest neighbor rule.

The weighted average of the predicted output class of the test NL element is:
Xo = £WiXoi / £Wi

Where, Xo is the predicted output class of the NL element to process and Wi is the weight of the
processed NL element, Xi, with an output class, Xoi.

How to Reduce the Size of the Vector Space

Memory−based learning methods require significant amount of time to generate an output because
the NL element to process is compared with all the processed NL elements that are stored in
memory to select the neighborhood NL elements. To accelerate the selection procedure, you can
modify the learning algorithm or reduce the size of the vector space.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 7

For example, you can delete certain instances of processed NL elements, such as exceptions and
noise, to shorten the comparison phase and increase accuracy. Noise is a processed NL element
with a wrong output class because of end user or system errors.

The NL elements to delete are selected based on a criterion. This criterion identifies instances in the
vector space whose deletion reduces the comparison time without any loss of output accuracy.

Figure 2−2−4 shows a sample vector space before and after the deletion of similar nodes:

Figure 2−2−4: Instance Deletion in Vector Space

The best way to handle exception and noise instances is to avoid storing them in memory. The best
method is to ensure that each new I/O pair is validated before it is stored.

Storage validation uses two schemes:

• Competence enhancement: Removes exceptional or noise instances.

• Competence preservation: Removes a duplicate or redundant instance, which is a

processed NL element that does not play a critical role in the classification of any new NL
element.

The algorithms that implement competence enhancement and competence preservation are:

• Wilson Editing

• Condensed Nearest Neighbor (CNN) rule

• Selective Nearest Neighbor (SNN) rule

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 8

• IB1, IB2, and IB3

• RT algorithms

The Wilson Editing algorithm scans all the processed NL elements in memory and isolates noise
instances using an editing rule. This rule identifies those instances of the processed NL elements
that do not have the same output class as that of their nearest neighbors. These instances are
mostly noise instances or an exception that resides between two different class regions.

The Wilson Editing algorithm isolates and deletes incoherent instances and smoothes out the
overall vector space. You need to use the algorithm multiple times to apply the Wilson Editing rule
exhaustively. This algorithm handles multiple noise occurrences well.

CNN locates instances that you can delete without affecting the output class of any unprocessed NL
element whose neighborhood might include these instances. This rule facilitates the deletion of
redundant instances. CNN creates a minimal or optimized set of processed NL elements, S, from
the original set of processed NL elements, R, that is stored in memory. The property that defines S
is:

S R

The characteristic of the minimal set, S, is that each NL element is associated with the same class
and with the same prediction accuracy of the previous set, R. Prediction accuracy is the probability
of predicting the correct output class associated with an element.

IB2 decides the validity of the physical storage of a processed NL element based on the output
class of that element. If the last processed NL element is classified using the remaining processed
NL elements, the I/O pair of the last processed NL element is not stored in the computer memory.
The limitation of IB2 is that it facilitates storage of exceptions and noisy instances.

IB3 solves the exception and noise storage problem of the IB2 algorithm. IB3 allows the system to
store a newly processed NL element on a temporary basis. If the predictions that are based on the
newly processed NL element are accurate, the element is permanently stored in memory;
otherwise, it is deleted. To implement IB3, a record of all the classifications of NL elements,
predicted on the basis of temporarily stored processed NL elements, is maintained.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Types of Memory−Based Learning
Learning is defined as changes in the system that are adaptive because they allow the system to do
the same task or tasks, from the same population, more efficiently and more effectively the next
time. Memory−based learning deals with large volumes of processed NL elements.

Based on the knowledge acquisition mode, learning falls into one of the following classes:

• Supervised: Uses the advice of an external source, such as an end user, to implement
learning.

• Unsupervised: Uses the experience of the NLP system to implement learning.

Memory−based learning uses supervised learning techniques. The types of memory−based

learning are:

• Rote

• Parameter Adjustment

• Analogical

• Cluster

• Incremental

• Reinforcement

Rote Learning
Rote learning is a knowledge acquisition technique. Various Artificial Intelligence (AI) programs,
such as game playing, use rote learning as an unsupervised learning class. In game−playing
programs, such as checkers, chess, and tic−tac−toe, the storage of the moves that the end user
played earlier improves the computer output.

A numerical value is associated with each move that specifies the chances of a win after that move
is made. The accuracy of a game−playing program depends on the extent to which it searches for
the possible next moves. A good program examines all the possible options for the next move and
works out at least three or four moves in advance.

A tree data structure represents all the possible moves in the existing state of a game. Each node of
the tree has a label that represents the move and a score that specifies the chances of success that
are associated with the move. The root node of the tree represents the current state of the game. A
tree has various horizontal levels, with the root node at level 1. The various nodes at the same level
represent all the possible options for the next move.

After creating the tree, the program searches for the best possible move. An evaluation function
computes the score of multiple moves. After the computation, the current state and the score are
stored in memory. The stored data acts as a cache if the same state of the game reappears.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 10

Caching avoids computing the score again and implements rote learning in memory−based NLP
systems. If the current state appears for the first time, rote learning facilitates the computation of the
collective score.

Rote learning facilitates the use of cached content in memory−based NLP systems when the
existing state of the game results in a cached state in a definite number of moves. The cached state
is not extended for further moves and the stored score of the cached state is used directly.

Figure 2−2−5 shows the tree structures that represent the different move options; the root node
represents the current state of the game:

Figure 2−2−5: Game Tree Structures

Parameter Adjustment Learning
The desirability of the next move that the computer makes in game−playing applications depends
on various factors, which a static evaluation function summarizes using a numeric score. Each
factor is associated with a scalar coefficient or weight. An external source, such as an end user,
assigns initial values to these weights.

A static evaluation function can be a polynomial, such as:

a1f1 + a2f2 + a3f3 + a4f4 + a5f5

Where, a1, a2, a3, a4, and a5 are the scalar coefficients or weights that are associated with the
factors f1, f2, f3, f4, and f5.

The program uses parameter adjustment learning to modify the weights of the factors, based on
past experience. The weight of a specific factor increases if past predictions based on that factor
are TRUE; otherwise, it decreases. In parameter adjustment, you must decide when to change the
weights and by how much.

To implement learning by parameter adjustment:

1. Initialize the parameters that are associated with each feature of a processed NL element.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 11

2. Compute an evaluation function value for every move that the computer makes.

3. Provide feedback on the evaluation function value that is associated with each move that the
computer makes.

4. Maintain a separate record of the initial state of the game. This record helps revert to the
original state if the intermediate set of moves results in a loss in the game played by the
computer.

5. Replace randomly a feature that is included in the evaluation function with a feature that was
not previously included in it. This method creates a sudden change in the evaluation function
and searches unexplored moves.

Analogical Learning
The basic principle of analogical learning is that if two situations or domains have certain similar
features, they must have other similarities as well. For example, if two living beings have similar
physical characteristics, such as size, shape, and color, they probably belong to the same species.
Analogy facilitates the use of knowledge from known domains in unknown domains that bear certain
similarities.

Analogical learning has an analogical model, which contains a start−point, an end−point, and
mappings between the start and end points. The start−point is the known domain and the end−point
is the unknown domain. All the processed or known analogues are stored in memory. Both domains
have certain similar characteristics that are correspondingly mapped. Analogical inferences map the
unknown elements of the end−point to the known elements of the start−point, which implements
learning.

Figure 2−2−6 shows a working model of analogical learning:

Figure 2−2−6: Working of Analogical Learning

To implement the analogical learning process:

1. Select possible start−end domain analogues stored in memory that bear certain similarities
with the end−point domain to process.

2. Map the similar features of start−point analogues with that of the end−point domain.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 12

3. Extend start−end analogues to fit the end−point domain. This extension generates additional
information about the unknown domain from the available information about the known
domains.

4. Validate the induced solution using validation checks, such as theorems.

5. Store the newly processed NL element in memory. The stored information, which includes
features of the domain as well as the induced information, facilitates processing of further
situations that bear similarities with the newly processed situation.

For example, an atom is analogous to a planet/satellite relationship.

Table 2−2−1 describes the functions in the start−point domain, planet/satellite, to represent various
relationships:

Table 2−2−1: Functions in the Planet/Satellite Domain

Function Description
bigger−than(planet, satellite) Signifies that the size of a planet is larger than
the size of a satellite.
Pulls(planet, satellite) Signifies that planets attract satellites.
Revolves−around(satellite, planet) Signifies that satellites revolve around planets.
results−in(bigger−than(planet, satellite), Induces that the gravitational pull of the
pulls(planet, satellite)) satellites results because planets are bigger
than satellites.
results−in(pulls(planet, satellite), Induces that the gravitational pull of the
revolve−around(satellite, planet)) satellites results in the revolution of the
satellites around the planets.

Figure 2−2−7 shows the start−point domain, planet/satellite:

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 13

Figure 2−2−7: Planet/Satellite Start−Point Domain

The analogical mapping between the planet/satellite domain and the atom is the basis of the
following rules:

• planet −> nucleus: Maps the planet to the nucleus of an atom.

• satellite −> electron: Maps the satellite to the electron of an atom.

The functions that emerge because of this mapping are:

• bigger−than(nucleus, electron): States that the nucleus is bigger than the electron.

• pulls(nucleus, electron): States that the nucleus pulls the electron in an atom.

• revolves−around(electron, nucleus): States that the electron revolves around the nucleus in
an atom.

• results−in(bigger−than(nucleus, electron), pulls(nucleus, electron)): Induces that the nucleus

attracts the electron because it is bigger than the electron.

• results−in(pulls(nucleus, electron), revolve−around(electron, nucleus)): Induces that the

attraction of the electrons results in the revolution of electrons around the nucleus.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 14

Cluster Learning
In clustering, objects or processed NL elements are grouped based on their similar features.
Clustering organizes the vector space in a hierarchical order of similarities. The Euclidean distance
is a common similarity measure used in clustering.

To implement clustering:

1. Form a pair of processed NL elements that have a significantly high degree of similarity from
among the processed NL elements in the memory.

2. Combine the features of the paired processed NL elements to define the features of the
cluster.

3. Replace the two processed NL elements with the cluster and replace the features of the NL
elements with the combined features that are defined in Step 2.

4. Repeat Steps 1 through 3 until the correct cluster size is reached.

For example, a computer memory contains three processed NL elements with five features each:
pro_NL element1 = {f1, f2, f3, f4, f5}
pro_NL element2 = {f2, f4, f5, f7, f8}
pro_NL element3 = {f5, f6, f7, f8, f9}

The similarity measure of a pair that contains two out of the three processed NL elements depends
on the number of common features. The various similarity measures are:
sim(pro_NL element1, pro_NL element2) = 60%
sim(pro_NL element2, pro_NL element3) = 60%
sim(pro_NL element3, pro_NL element1) = 20%

Clustering algorithms uses various numeric threshold values that determine the operations to
perform. For example, ISODATA is a clustering algorithm that uses three threshold values, tm, tb,
and td, which determine when to merge, bisect, and discard clusters. The similarity metric, such as
Euclidean distance, is compared with the threshold value to decide the operation to be performed
on the processed NL elements.

To implement cluster algorithm:

1. Randomly select n initial processed NL elements.

2. Combine the processed NL elements whose Euclidean distance is less than the merge
threshold value, tm.

3. Compute the centers of the newly formed clusters and update the Euclidean distance
between the clusters.

4. Split the clusters that exceed the bisect threshold value, tb, and update the Euclidean
distances.

5. Discard the clusters that contain fewer than td members.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 15

6. Repeat Steps 2 through 5 until no further change occurs.

Incremental Learning
Incremental learning is a modification of memory−based learning. You can use this method in visual
object processing as well as NLP. NLP systems use batch computation or incremental computation.
Both computations use previously processed NL elements to classify new NL elements. For
example, a visual object processing system contains n processed NL elements, with m number of
dimensions or features. The real visual images are converted into corresponding internal
representations that are stored in the memory.

In batch computation, the internal representations as well as the real images are stored in the
memory. The processing of a new visual object requires processing of all the previously processed
NL elements as well. The inclusion of a newly processed NL element in the database changes the
vector space. This change renders the internal representations of the previously processed NL
elements redundant.

Figure 2−2−8 shows how batch computation works:

Figure 2−2−8: Batch Computation

In incremental computation, the real image of a new NL element is converted into its corresponding
internal representation. This representation is included in the vector space that already contains the
existing internal representations.

Figure 2−2−9 shows how incremental computation works:

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 16

Figure 2−2−9: Incremental Computation

If the inclusion of the newly processed representation node does not match the old representation
nodes in the vector space, all the nodes are placed at approximated locations. Location
approximation avoids the processing of all real images for any new image.

Figure 2−2−10 shows the location mismatch and its solution:

Figure 2−2−10: Vector Space in Incremental Learning

Incremental computation avoids processing all the real images when an unprocessed NL element
changes the orientation of the existing vector space.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 17

Reinforcement Learning
Reinforcement learning uses a policy of reward and penalty to facilitate learning in applications,
such as game playing. This learning method delays feedback on moves, which determines the
desirability of a particular move on a long−term basis. The feedback specifies the result of a set of
moves rather than pinpointing a definite move.

A component, called a learning agent, implements reinforcement learning. This method of learning
contains states, actions, and rewards. States represent the current situation of a game. Actions
represent a set of possible moves that can occur when the game is in a particular state. Rewards
represent the incentive for a particular action.

A numeric function is attached to every state, which indicates the desirability of that state, such as:
f(Sn) = f(Sn+1) + rew

Where, Sn represents the nth state, Sn+1 the n+1th state, and rew the reward attached to the action
that transforms Sn into Sn+1.

Listing 2−2−1 shows the reinforcement−learning algorithm:

Listing 2−2−1: The Reinforcement Learning Algorithm

for every state S
for every action A
f(S,A)=0
S=current_state
do forever
A = select an action
perform action A on state S
rew = reward associated with action A
R = resulting state after performing action A
f(S,A) = f(S,A) + (rew + a * (f(R)−f(S,A))
S = R

In the above listing, f(S,A) provides the numeric value that is associated with a state, S, after an
action, A, is performed. The function, f(R), provides the highest numeric value among the various
values of f(S,A). The coefficient, a, is a discount factor that prevents numeric values that are
associated with the states from deviating and ensures shorter sequences of moves.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Implementing Memory−Based Learning
In NLP, you can implement memory−based learning using various techniques, such as neural
network and genetic algorithms. The human brain is the analogy for the architecture and the
working of neural networks. For genetic algorithms, the analogy is the evolution of life.

Neural networks select two possible solutions from a large population of possible solutions and
allow them to reproduce child solutions that are better than the two possible parent solutions. Neural
networks employ the delta rule and the backpropagation algorithm to facilitate supervised learning.
Genetic algorithms implement the survival of the fittest rule.

Neural Networks
Just as human brains contain billions of interconnected neurons, neural networks contain numerous
interconnected computational units that can perform parallel distributed processing. The building
block of a neural network is a computational unit, which is an artificial neuron that a node
represents. An edge represents the interconnection between these neurons. Neurons receive input
through weighted edges from other neurons, which are processed based on the weight and output
signals that are passed on to other neurons.

Table 2−2−2 describes the elements of an artificial neuron:

Table 2−2−2: Elements of an Artificial Neuron

Element Description
Input value(s) Originates from the output of other neurons or from the environment, such
as human response. The domain of the input values can be discrete or
continuous.
Weight(s) Differentiates between the various inputs by associating a scalar value with
each of them.
Activation value Provides the output using an activation function with input values and
weights as parameters. The activation value can act as the input to other
neurons or as a result that the neural network generates.
Activation function Computes an activation value of a neuron, with input values and weights that
act as parameters.
Network topology Provides a pattern of interconnections between various neurons; it is a
global property of the neural network.
Learning algorithm Implements supervised learning from experiences, such as processed NL
elements.

Figure 2−2−11 shows the elements of an artificial neuron:

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 19

Figure 2−2−11: Elements of an Artificial Neuron

Perceptron is one of the earliest systems based on neural networks. Perceptron is implemented
using the perceptron model. The perceptron model recognizes geometrical shapes in a vision
system. The neuron receives input with specific weights, and computes the sum of the product of
input values and the corresponding weights, £ Xiwi. The output depends on the value of a threshold,
t.

The activation value with threshold, t, is:

1 if> £t Xiw
i
0 Otherwise

Where, Xi is the input value and wi is the weight that is associated with an input, i. The value of i
ranges from 1 through n, where n is the number of inputs that are associated with a neuron.

Figure 2−2−12 shows how the perceptron model works:

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 20

Figure 2−2−12: The Perceptron Neural Network

A learning algorithm that is used in the perceptron neural network implements the following rule:

If a neuron is activated when it should not be, you must reduce the weight that is associated with
the input. If a neuron is not activated when it should be, you must increase the weight that is
associated with the input.

The Delta Rule

The delta rule is a generalization of the perceptron−learning algorithm and helps implement various
neural networks. The delta rule modifies the weights that are associated with the input to implement
learning from experience.

The output of an artificial neuron is computed using a linear activation function:

O = £ Xiwi t

Where, Xi is the input, wi is the associated weights, and t is the threshold value.

The difference between the actual output and the correct output is the quantum of change that is
required in the weights. The error of a particular neuron for all possible input values is computed
using:
E = £ (Od Oa)2

Where, Od is the correct output and Oa is the actual output of a particular neuron.

For example, a neuron has two inputs, X1 and X2, and the weights that are associated with them are
w1 and w2. To adjust w1 and w2, you use the gradient descent, which is a technique to reduce an
error measure. In gradient descent, possible solutions are represented as an n−dimensional
surface, where n is the number of weights. You move downward through the n−dimensional surface
toward a point that represents the values of weights that provide correct outputs. This point in the
n−dimensional surface is called the zero−error point.

Figure 2−2−13 shows the 2−D gradient descent surface:

Figure 2−2−13: The Gradient Descent Surface

The change in weights is computed from the difference between the actual and correct weights
using:

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 21

”wi = a (Od Oa) Xi

Where, ”wi is the difference between the new and old values of weights, and a is the learning
constant. The value of the learning constant is directly proportional to the speed with which the
optimal weights are searched. A large value quickens the search; but it may overshoot the point on
the surface that represents the optimal weights. A small value consumes a significant amount of
time to find the optimal weights.

The fixed−increment perceptron−learning algorithm uses a fixed learning constant. To apply this
algorithm on an artificial neuron with n input and two possible outputs:

1. Create an extra input, X0, and set it to 1.

2. Set the n+1 weights to random real values.

3. Pass the various processed NL elements in the memory through the perceptron neuron.

4. List all the processed NL elements that are incorrectly classified.

5. Generate the values of the various weights as the output. Exit if the value in the list of
incorrectly classified NL elements is null; otherwise, continue.

6. Compute the vector sum of the input vectors of the processed NL elements in the list. The
input vector of a processed NL element provides the values of the input, X0 through Xn. The
sign of the input vector depends on the accuracy of the activation value that the perceptron
neuron produces. If the perceptron activates when it should not, add +X to the vector sum. If
the perceptron does not activate when it should, add X to the vector sum.

7. Multiply the learning constant by the computed sum.

8. Add the values of individual scalar elements of the vector sum with the corresponding values
of the weights to provide the new values of the weights.

9. Repeat Steps 3 through 8.

The Backpropagation Algorithm

In backpropagation, a series of processing elements is cascaded to form a linear network. For

example, the output of the processing element, A, is fed as input to the processing element, B.
Learning is implemented by passing the errors that A generates to B.

The perceptron uses a single−layer neural network, whose computational ability is very small. Most
NLP applications involve multilayered neural networks, which contain an input layer, an output layer,
and a set of hidden layers. Separate sets of weights are associated with input and output hidden
neuron pairs.

Figure 2−2−14 shows a multilayered neural network with three layers: input, output, and hidden:

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 22

Figure 2−2−14: A Multilayered Neural Network

The backpropagation algorithm implements learning in multilayered neural networks. Neural
networks that use backpropagation contain various connecting layers; each layer passes the
activation values to the next layer. The activation values of the neurons in the input layer pass
through various hidden layers before they reach the neurons in the output layer. These output layer
neurons generate activation values that are passed to the environment. The generated error is
propagated through the network in a direction opposite that of the activation value propagation.

Figure 2−2−15 shows the propagation of the activation values and the error through the network:

Figure 2−2−15: Propagation in Multilayered Neural Networks

The backpropagation algorithm uses a sigmoidal activation function, which has a S−shaped curve.
The output generated by a sigmoidal activation function is:
Output, O = 1/(1 + e−sum)
Sum = £ Xiwi t
Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 23

Where, Xi is the input value, wi is the weight, and t is the threshold value.

The error that is associated with a particular neuron in a layer is a function of all the errors that are
associated with neurons that use the output of that particular neuron. The error of a particular
neuron is computed using the derivative of the activation function.

The error of a neuron is calculated as:

Er = f(Xr) £ wri Ei

Where, Er is the error that is associated with a neuron, r; Xr is the input to r; and wri specifies the
weights that are associated with the edges between r and the neuron that receive the output
generated by r. The function f(X r) is the derivative of the activation function.

The first derivative of a function, f(x), is computed using the formula:

f(x) = f(x) (1 f(x))

The function, f(x), represents the actual output, O, that the neuron generates. When you replace f(x)
with O, the error function becomes:
Er = O(1 O) £ wri Ei

Figure 2−2−16 shows the different activation functions in neural networks:

Figure 2−2−16: Different Activation Functions

For example, a neural network contains three layers and the variables I, O, and H symbolize the
number of input, output, and hidden units. A separate unit is added to provide threshold values in
the input and hidden layers. The activation value of the neurons in the input, output, and hidden
layers are Xi, Hi, and Oi. The function iwij represents the weights of the edges between the input and
the hidden layers; the function owkl represents the same between the output and the hidden layers.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 24

The values of i range from 0 through i, where i is the number of input units. The values of j range
from 1 through h, where h is the number of hidden units. The values of k range from 0 through h.
The values of i range from 1 through o, where o is the number of output units.

To implement backpropagation:

1. Set the weights, iwij and owkl, with random real values that range from −0.1 through +0.1.

2. Set the values of the threshold units, X0 = 1.0 and H0 = 1.0.

3. Select a processed NL element with the input vector, Xi, and the correct output vector, dOi,
and set the activation levels of the input units.

4. Compute the activation values of the hidden units, which receive the activation values from
the input units, using the activation functions:
Hj = 1/(1 + e−sum) for all j = 1 to H
sum = £iwijXi for all i = 0 to X

5. Compute the activation values of the output units that receive the activation values from the
hidden units, using the activation functions:
Ol = 1/(1 + e−sum) for all l = 1 to O
sum = £owklXk for all k = 0 to H

6. Compute the error of the output units using the formula:

”EOl = Ol(1 Ol)(dOl Ol) for all l = 1 to O

7. Compute the error of the units in the hidden layer using the formula:
”EIj = Hj(1 Hj)esum for all j = 1 to H
esum = £ EOl . owkl for all k = 1 to O

8. Modify the weights that are associated with the edges between the output and the hidden
layer to reduce the output unit error. The formula for weight adjustment is:
”owkl = a . EOl .Hk for all k = 0 to H and l = 1 to O

9. Modify the weights that are associated with the edges between the hidden and the input
layer to reduce the error of the units in the hidden layer. The formula for weight adjustment
is:
”iwij = a . EIj .Xi for all i = 0 to X and j = 1 to H

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 25

10. Repeat Steps 3 through 10 until you receive the correct output from the units in the output
layer.

Genetic Algorithms
In genetic algorithms, the offspring inherits the desirable characteristics from its parents. This
inheritance renders the offspring more fit and adaptable than its parents. Genetic algorithms start
with a fixed−length binary string that are worked upon a number of times and rated, based on their
performance. The strings that perform better than the rest recombine to create a new generation of
data.

Figure 2−2−17 shows the steps in a genetic algorithm:

Figure 2−2−17: Steps in a Genetic Algorithm

The four steps of the genetic algorithm are:

1. Initialize the set of possible solutions.

2. Perform a set of tasks or operations on the possible solutions. A set of new possible
solutions is generated.

3. Assign a numeric value to all the new possible solutions on the basis of the differences
between that possible solution and the correct solution.

4. Select the new possible solutions with a numeric value that is higher than a predefined
threshold value. A new set of possible solutions is generated.

A genetic algorithm deals with multiple possible solutions that are generated by applying various
genetic operators, such as crossover and mutation. The set of possible solutions continues to
change over time.

The following expression represents a set of possible solutions at time, t:

S(t) = {X1t, X2t,..., Xnt}

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 26
t
Where, n is the total number of possible solutions at time, t, and X1 is the first possible solution at
time, t.

Listing 2−2−2 shows a genetic algorithm:

Listing 2−2−2: A Genetic Algorithm

function gen_algo();
begin
t:=0;
set the initial values of S(t);
while desired results are not obtained do
begin
evaluate all the solutions in S(t);
choose solutions that have a good evaluation value;
apply genetic operators on selected solutions to produce offspring solutions;
replace the solution with the worst evaluation value with the offspring solution produced;
t:=t + 1;
end;
end

The above listing shows the gen_algo() function that processes a set of possible solutions using
genetic operators to yield the correct solution.

For example, a solution contains an 8−character string, which uses three characters, a, b, and Y.
The variable, Y, can have at value, a or b. The desirability of a possible solution is computed using
an evaluation function, f(Xi ). Genetic operators decide the features that the offspring should inherit
from its parents. The two types of genetic operators are crossover and mutation.

Crossover involves two possible solutions and divides each solution into two separate components.
The components are swapped or crossed over to form two new solutions.

Figure 2−2−18 shows the crossover of two possible solutions:

Figure 2−2−18: The Crossover Genetic Operator

The mutation genetic operator works on one possible solution. Mutation changes the individual
characters of a possible solution to produce next−generation possible solutions. Mutation
overcomes the limitations of the crossover genetic operator because crossover cannot produce a
next−generation possible solution from two parent possible solutions if both parents lack the
necessary characteristics of a correct solution.
Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Natural Language Processing ReferencePoint Suite 27

The advantages of genetic algorithms are:

• Parallelism: Works on various possible solutions simultaneously. The application

concurrently extends various possible solution branches using genetic algorithms. The best
among them is selected as the next solution on which the genetic operators operate.

• Inheritance: Parents pass the desirable features of the possible solutions to their offspring.

• Nondeletion of weaker solutions: Avoids deleting possible solutions with a small evaluation
value. This avoidance provides the memory−based NLP systems with a chance to inherit the
desirable features in weaker solutions as well.

• Appropriate reproduction chances: Indicates a low reproduction probability for weaker

solutions and a high probability for stronger possible solutions. This chance method ensures
that the focus of the search is to identify the strongest solution. It also reduces the time that
is required to obtain appropriate solutions.

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited
Related Topics
For related information on this topic, you can refer to:

• Context−Free Grammar

• Using Machine Learning in Language Processing

• Stochastic Algorithms and Models for Language Processing

Reprinted for EX3L3/z877571, VerizonBusiness SkillSoft, SkillSoft Corporation (c) 2003, Copying Prohibited