Instance-Based Learning: An Introduction and Case-Based Learning
Instance-based methods are frequently referred to as “lazy” learning methods because they defer processing until a new instance must be classified. In this blog, we’ll have a look at Introduction to Instance-Based Learning.
The training examples are simply stored in the methods. Beyond these examples, generalization is postponed until a new instance has to be classified.
When a new query instance is encountered, its relationship to previously-stored examples is investigated in order to assign a target function value to the new instance.
Nearest neighbor and locally weighted regression approaches are examples of instance-based learning, which presume that instances may be represented as points in a Euclidean space. Case-based reasoning approaches, which use more elaborate, symbolic representations for cases, are also included.
Instead of estimating the target function once for the entire instance space, these approaches can estimate it locally and differently for each new case to be categorized, which is a significant benefit of delayed, or lazy, learning.
Basically, Instance-Based Learning follows the approach of memorizing and learning instead of performing explicit generalization, it compares the new instances with the training data present in the memory.
For example, Any email that looks like spam will be automatically labeled as spam. They aren’t looked into every time.
Pros:
- Instead of estimating the target function for the full instance set, smaller approximations might be made.
- This technique is easily adaptable to new data, which is collected as we go.
Cons:
- The costs of classification are substantial.
- Large amounts of memory are required to hold the data, and each query necessitates the creation of a new local model.
The size of the training data determines the time complexity of this technique. This algorithm’s worst-case time complexity is O (n), where n is the number of training cases.
Approaches to approximating real-valued or discrete-valued target functions using instance-based learning methods such as closest neighbor and locally weighted regression are theoretically simple.
In these algorithms, learning consists of just storing the training data.
When a new query instance is encountered, a set of related instances similar to the current query instance is obtained from memory and used to classify it.
Many strategies merely create a local approximation to the goal function that applies in the immediate vicinity of the new query instance, rather than an approximation that performs well across the entire instance space.
When the target function is exceedingly complicated but can still be described by a set of less complex local approximations, this has substantial advantages.
Some of the Instance-based Learning algorithms are:
- Lazy Learners (KNN algorithm)
- Radial Based Functions (RBF)
- Case-Based Reasoning (CBR)
Case-Based Reasoning:
More elaborate, symbolic representations for instances can also be used in instance-based procedures. In case-based learning, examples are represented in this way, and the method for recognizing “neighboring” instances is expanded in this way as well.
Case-based reasoning has been used to solve difficult scheduling problems by reusing relevant pieces of previously solved problems at a help desk, reasoning about legal matters by referring to previous instances, and storing and reusing past experience at a help desk.
One downside of instance-based techniques is that it can be expensive to classify new instances. This is because practically all computation occurs during categorization rather than when the training samples are encountered for the first time.
As a result, strategies for efficiently indexing training samples constitute a significant practical concern in lowering query time computation.
The second shortcoming of many instance-based techniques, particularly nearest neighbor algorithms, is that when retrieving similar training examples from memory, they often examine all attributes of the instances.
If only a few of the numerous available attributes are used to define the target idea, the instances that are actually “similar” may be a long way apart.
How does it work?
An Instance-based Reasoner (CBR) will first check if an identical training case exists before classifying a new case. If one is identified, the case’s solution is returned along with it.
If no equivalent example can be discovered, the CBR will look for training cases that have components that are comparable to the new cases. These training instances can be thought of as neighbors to the new case in terms of concept.
If the cases are represented as graphs, this entails looking for subgraphs that are similar to those in the new example. To provide a solution for the new example, the CBR attempts to merge the solutions of neighboring training cases.
If there are problems with the particular solutions, you may need to go back and look for other options. To propose a viable solution, the CBR may use prior information and problem-solving methodologies.
Let’s look at an example of case-based reasoning,
- Case-based reasoning is used in the CADET system (Sycara et al. 1992) to aid in the conceptual design of simple mechanical devices such as water faucets.
- It suggests conceptual ideas to satisfy the specifications of new design issues using a library of around 75 prior designs and design fragments. Each memory instance (for example, a water pipe) is described by specifying both its structure and qualitative function.
- By providing the intended function and demanding the associated structure, new design difficulties are provided. Figure 8.3 shows how to build up a situation like this.
- The top half of the diagram depicts a T-junction pipe, which is a common type of storage case. Its function is illustrated by the qualitative correlations between the amounts of water flow and the temperatures at its inputs and outputs.
- An arrow with a “+” label in the functional description to its right indicates that the variable at the arrowhead rises with the variable at its tail. For example, as the input water flow grows, the output water flows Q3 rises.
Reference
Instance-Based Learning: An Introduction and Case-Based Learning