INSTANCE BASED LEARNING

INTRODUCTION
Instance-based learning methods such as nearest neighbor and locally weighted
regression are conceptually straightforward approaches to approximating real-valued or
discrete-valued target functions.
Learning in these algorithms consists of simply storing the presented training data.
When a new query instance is encountered, a set of similar related instances is retrieved
from memory and used to classify the new query instance
Instance-based approaches can construct a different approximation to the target function
for each distinct query instance that must be classified
Advantages of Instance-based learning
1. Training is very fast
2. Learn complex target function
3. Don’t lose information
Disadvantages of Instance-based learning
The cost of classifying new instances can be high. This is due to the fact that nearly all
computation takes place at classification time rather than when the training examples are first
encountered.
In many instance-based approaches, especially nearest-neighbor approaches, is that they
typically consider all attributes of the instances when attempting to retrieve similar training
examples from memory. If the target concept depends on only a few of the many available
attributes, then the instances that are truly most "similar" may well be a large distance apart.
k- NEAREST NEIGHBOR LEARNING
The most basic instance-based method is the K- Nearest Neighbor Learning. This
algorithm assumes all instances correspond to points in the n-dimensional space Rn .
The nearest neighbors of an instance are defined in terms of the standard Euclidean
distance.
Let an arbitrary instance x be described by the feature vector
((a1(x), a2(x), ………, an(x))
Where, ar(x) denotes the value of the rth attribute of instance x.
Then the distance between two instances xi and xj is defined to be d(xi , xj )
Where,

In nearest-neighbor learning the target function may be either discrete-valued or real
valued.
Let us first consider learning discrete-valued target functions of the form
Where,

V is the finite set {v1, . . . vs }

The k- Nearest Neighbor algorithm for approximation a discrete-valued target
function is given below:
The value 𝑓̂(xq) returned by this algorithm as its estimate of f(xq) is just the most
common value of f among the k training examples nearest to xq

If k = 1, then the 1- Nearest Neighbor algorithm assigns to 𝑓̂(xq) the value f(xi). here xi is
.

the training instance nearest to xq.

For larger values of k, the algorithm assigns the most common value among the k nearest
training examples.
Below figure illustrates the operation of the k-Nearest Neighbor algorithm for the case
where the instances are points in a two-dimensional space and where the target function is
Boolean valued.

The positive and negative training examples are shown by “+” and “-” respectively. A
query point xq is shown as well.
The 1-Nearest Neighbor algorithm classifies xq as a positive example in this figure,
whereas the 5-Nearest Neighbor algorithm classifies it as a negative example.
Below figure shows the shape of this decision surface induced by 1- Nearest
Neighbor over the entire instance space. The decision surface is a combination of convex
polyhedra surrounding each of the training examples.

For every training example, the polyhedron indicates the set of query points whose
classification will be completely determined by that training example. Query points
outside the polyhedron are closer to some other training example. This kind of diagram is
often called the Voronoi diagram of the set of training
The K- Nearest Neighbor algorithm for approximation a real-valued target
function is given below

Distance-Weighted Nearest Neighbor Algorithm

The refinement to the k-NEAREST NEIGHBOR Algorithm is to weight the
contribution of each of the k neighbors according to their distance to the query point xq,
giving greater weight to closer neighbors.
For example, in the k-Nearest Neighbor algorithm, which approximates discrete-valued
target functions, we might weight the vote of each neighbor according to the inverse square
of its distance from xq
Distance-Weighted Nearest Neighbor Algorithm for approximation a discrete-valued target
funcions

Distance-Weighted Nearest Neighbor Algorithm for approximation a Real-valued target

functions
Terminology

Residual is the error 𝑓̂(x) - f (x) in approximating the target function.

Regression means approximating a real-valued target function.

Kernel function is the function of distance that is used to determine the weight of
each training example. In other words, the kernel function is the function K such that
wi = K(d(xi, xq))
LOCALLY WEIGHTED REGRESSION
The phrase "locally weighted regression" is called local because the function
is
approximated based only on data near the query point, weighted because the
contribution of each training example is weighted by its distance from the query point,
and regression because this is the term used widely in the statistical learning community
for the problem of approximating real-valued functions.

to construct an approximation 𝑓̂ that fits the training examples in the neighborhood

Given a new query instance xq, the general approach in locally weighted regression s

surrounding xq. This approximation is then used to calculate the value 𝑓̂(xq), which is
output as the estimated target value for the query instance.
Locally Weighted Linear Regression
Consider locally weighted regression in which the target function f is approximated near
xq using a linear function of the form Where, ai(x) denotes the value of the ith attribute of the
instance x

Derived methods are used to choose weights that minimize the squared error summed over
the set D of training examples using gradient descent

Which led us to the gradient descent training rule

Where, η is a constant learning rate

Need to modify this procedure to derive a local approximation rather than a global one.
The simple way is to redefine the error criterion E to emphasize fitting the local training
examples. Three possible criteria are given below.
1. Minimize the squared error over just the k nearest neighbors:

2. Minimize the squared error over the entire set D of training examples, while
weighting the error of each training example by some decreasing function K of its
distance from xq :

3. Combine 1 and 2:
If we choose criterion three and re-derive the gradient descent rule, we obtain the following
training rule

The differences between this new rule and the rule given by Equation (3) are that the
contribution of instance x to the weight update is now multiplied by the distance penalty
K(d(xq, x)), and that the error is summed over only the k nearest training examples.
RADIAL BASIS FUNCTIONS
One approach to function approximation that is closely related to distance-weighted
regression and also to artificial neural networks is learning with radial basis functions
In this approach, the learned hypothesis is a function of the form

Where, each xu is an instance from X and where the kernel function Ku(d(xu, x)) is
defined so that it decreases as the distance d(xu, x) increases.
Here k is a user provided constant that specifies the number of kernel functions to be
included.
𝑓̂ is a global approximation to f (x), the contribution from each of the Ku(d(xu, x)) terms is
localized to a region nearby the point xu.

some variance 𝜎u 2
Choose each function Ku(d(xu, x)) to be a Gaussian function centred at the point xu with

provided a sufficiently large number k of such Gaussian kernels and provided the width 𝜎 2
The functional form of equ(1) can approximate any function with arbitrarily small error,

of each kernel can be separately specified

The function given by equ(1) can be viewed as describing a two layer network here
the first layer of units computes the values of the various Ku(d(xu, x)) and where the second
layer computes a linear combination of these first-layer unit
Example: Radial basis function (RBF) network
Given a set of training examples of the target function, RBF networks are typically trained in
a two-stage process.

choosing the values of xu and 𝜎u 2 that define its kernel function Ku(d(xu, x))
1. First, the number k of hidden units is determined and each hidden unit u is defined by

2. Second, the weights w, are trained to maximize the fit of the network to the training
data, using the global error criterion given by

Because the kernel functions are held fixed during this second stage, the linear weight values
w, can be trained very efficiently
Several alternative methods have been proposed for choosing an appropriate number of
hidden units or, equivalently, kernel functions.
One approach is to allocate a Gaussian kernel function for each training example

Each of these kernels may be assigned the same width 𝜎 2 . Given this approach, the RBF
(xi,f (xi)), centring this Gaussian at the point xi.

network learns a global approximation to the target function in which each training example
(xi, f (xi)) can influence the value of f only in the neighbourhood of xi.
A second approach is to choose a set of kernel functions that is smaller than the number of
training examples. This approach can be much more efficient than the first approach,
especially when the number of training examples is large.
CASE-BASED REASONING
Case-based reasoning (CBR) is a learning paradigm based on lazy learning methods and
they classify new query instances by analysing similar instances while ignoring
instances that are very different from the query.
In CBR represent instances are not represented as real-valued points, but instead, they use a
rich symbolic representation.
CBR has been applied to problems such as conceptual design of mechanical devices
based on a stored library of previous designs, reasoning about new legal cases based on
previous rulings, and solving planning and scheduling problems by reusing and
combining portions of previous solutions to similar problems
A prototypical example of a case-based reasoning
The CADET system employs case-based reasoning to assist in the conceptual design of
simple mechanical devices such as water faucets.
It uses a library containing approximately 75 previous designs and design fragments to
suggest conceptual designs to meet the specifications of new design problems.
Each instance stored in memory (e.g., a water pipe) is represented by describing both its
structure and its qualitative function.
New design problems are then presented by specifying the desired function and
requesting the corresponding structure.
The problem setting is illustrated in below

The function is represented in terms of the qualitative relationships among the water
flow levels and temperatures at its inputs and outputs.
In the functional description, an arrow with a "+" label indicates that the variable at the
arrowhead increases with the variable at its tail. A "-" label indicates that the variable at the
head decreases with the variable at the tail.
Here Qc refers to the flow of cold water into the faucet, Qh to the input flow of hot ater,
and Qm to the single mixed flow out of the faucet.
Tc, Th, and Tm refer to the temperatures of the cold water, hot water, and mixed water
respectively.
The variable Ct denotes the control signal for temperature that is input to the faucet, and Cf
denotes the control signal for waterflow.
The controls Ct and Cf are to influence the water flows Qc and Qh, thereby indirectly
influencing the faucet output flow Qm and temperature Tm.

CADET searches its library for stored cases whose functional descriptions match the
design problem. If an exact match is found, indicating that some stored case implements
exactly the desired function, then this case can be returned as a suggested solution to the
design problem. If no exact match occurs, CADET may find cases that match various
subgraphs of the desired functional specification.