Yolanda Matengambiri
R216892J
HAI
Machine learning
15. Final version space using candidate elimination algorithm.
Initial Specific Hypothesis S0 = <null, null, null, null>
Initial General Hypothesis G0 = <{Japan, USA}, {1980, 1970, 1990}, {Economy, Sports},
{Honda, Toyota, Chrysler, null}>
Training Examples:
1. <Japan, ColorDecade1980, Economy, ManufacturerHonda> : S1 = <Japan, 1980,
Economy, Honda> and G1 = <{Japan, USA}, {1980}, {Economy, Sports}, {Honda,
Toyota, Chrysler, null}>
2. <Japan, ColorDecade1970, Sports, ManufacturerToyota> : S2 = <Japan, null, Sports,
null> and G2 = <{Japan, USA}, {1970, 1980, 1990}, {Economy, Sports}, {Toyota, null,
null, null}>
3. <Japan, ColorDecade1990, Economy, ManufacturerToyota> : S3 = <Japan, 1990,
Economy, null> and G3 = <{Japan, USA}, {1990}, {Economy, Sports}, {Toyota, null, null,
null}>
4. <USA, ColorDecade1980, Economy, ManufacturerChrysler> : G4 = <{Japan, USA},
{1980}, {Economy, Sports}, {null, null, Chrysler, null}>
5. <Japan, ColorDecade1980, Economy, ManufacturerHonda> : S5 = <Japan, 1980,
Economy, Honda> and G5 = <{Japan}, {1980}, {Economy}, {Honda}>
6. <Japan, ColorDecade1990, Economy, ManufacturerToyota> : S6 = <Japan, 1990,
Economy, null> and G6 = <{Japan}, {1990}, {Economy}, {Toyota}>
7. <Japan, ColorDecade1980, Sports, ManufacturerHonda> : G7 = <{Japan}, {1980},
{Sports}, {null}>
Final hypothesis after all examples: <Japan, 1980, Economy, Honda>
15b) Write the final version space for mentioned training examples using candidate
elimination algorithm.
[Link] bound on hypothesis space: H = {<Size, Colour, Shape>}
2. Initialize version space: S0 = {<, , >}
3. Initialize the set of all hypotheses: G0 = {<Big, , >, <, Red, Circle>, <, Blue, Circle>,
<Small, , >}
4. Iterate over each training example. For example 1 (Size=Big, Colour=No,
Shape=Circle, Class=No):
- Remove from G any hypothesis that is not consistent with the example - G1 =
{<Big, , >, <, Red, Circle>, <, Blue, Circle>, <Small, , >}
- Find the subset of hypotheses in S that are consistent with the example - S1 =
{<Big, , >}
5. Iterate over the remaining examples and update G and S for each example. After
all examples are processed, we get the following final version space:
- S = {<Big, , >, <, Red, Circle>}
- G = {<Big, , >, <, Red, Circle>}
This final version space suggests that for any new example, if it is a circle or if it is red,
it can be classified as "No". However, if it is not red or a circle and is big, it can also
be classified as "No".
16) Explain in detail the inductive Bias of candidate elimination algorithm.
The candidate elimination algorithm is a machine learning algorithm used for
learning concept descriptions from data. Inductive bias refers to a set of assumptions
or expectations that a learning algorithm makes about the data it will be working
with.
The candidate elimination algorithm is an example of a type of machine learning
algorithm called a lazy learning algorithm. This means that the algorithm does not
create a general model of the data, but instead makes decisions based on the
specific examples it encounters during training.
The inductive bias of the candidate elimination algorithm reflects the
assumptions it makes about the nature of the data it will be working with. The
algorithm assumes that the concept it is trying to learn can be represented as a
conjunction of attributes, and that there is a finite set of hypotheses that can be
used to represent the concept.
The algorithm also has a bias towards simpler hypotheses, meaning it will
choose the most specific and least general hypothesis to represent the concept. This
is known as the minimum description length principle.
