Artificial Intelligence and Machine Learning

Module -2

Concept Learning

1. Introduction to Knowledge Representation

1.1 What is Knowledge?

In Artificial Intelligence and Machine Learning, knowledge refers to structured information that
allows a system to:
• reason
• make decisions
• solve problems
• learn from experience

Example of knowledge:
Birds fly
Penguins are birds
Penguins do not fly

This knowledge must be represented in a machine-readable format.

1.2 What is Knowledge Representation?

Knowledge Representation (KR) is the process of encoding knowledge in a formal structure

that a computer can understand and manipulate.

A good representation should:

1. Be expressive
2. Support reasoning
3. Be efficient
4. Be understandable by humans

Expressiveness
A representation must be rich enough to represent all necessary knowledge about a domain.

• It should be capable of describing objects, relationships, properties, and events.

• It must allow representation of complex concepts, rules, and constraints.

Example:
Using predicate logic, we can represent knowledge.

Support Reasoning
A representation should allow the system to derive new knowledge from existing knowledge.
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 1 of 19
• The system should be able to answer questions and make decisions based on stored
knowledge.

Example:

Knowledge:

• All humans are mortal

• Socrates is a human

Inference:

• Socrates is mortal

Thus, the representation should enable logical reasoning.

Efficiency

The representation should allow fast storage, retrieval, and inference.

Efficiency involves three aspects:

a) Storage efficiency – knowledge should not consume excessive memory.

b) Inference efficiency – reasoning should be computationally manageable.
c) Update efficiency – adding or modifying knowledge should be easy.

If reasoning takes too long, the representation becomes impractical for real systems.

Human Understandability

The representation should be easy for humans to interpret and maintain.

• Knowledge engineers should be able to read, understand, and modify it.

• It should resemble natural reasoning or logical thinking as much as possible.

Example:
Rule-based representation:

IF temperature > 38°C

THEN patient_has_fever

This rule is easy for humans to understand and verify.

2. Rule-Based Representation
One of the most common symbolic representations is rule-based representation.
Knowledge is expressed using IF–THEN rules. These are also known as Production Rules.

General structure:
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 2 of 19
IF Condition THEN Conclusion

Example:
IF temperature > 38°C
THEN fever

2.1 Structure of a Rule

A rule consists of two parts.

a) Antecedent (Condition)

The IF part.

Example:
IF humidity = high

b) Consequent (Conclusion)

The THEN part.

Example:
THEN rain = likely

2.2 General Form

A rule can contain multiple conditions.

IF P1 ∧ P2 ∧...∧ Pn → Q

Where:

• P1, P2 ,... Pn are conditions

• Q is conclusion

Example:

Rule 1:
IF temperature > 38 AND cough = true
THEN influenza

Rule 2:
IF rash=true AND temperature > 38
THEN measles

3. Rule-Based Knowledge Systems

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 3 of 19
A rule-based system contains three main components.

3.1 Knowledge Base

The knowledge base contains:

• facts
• rules

Example:

Facts:

temperature = 39
cough = true

Rules:

IF temperature > 38 AND cough = true

THEN flu

3.2 Working Memory

Stores current known facts.

Example:

fever = true
cough = true

Working memory changes during reasoning

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 4 of 19
3.3 Inference Engine

The inference engine applies rules to facts to derive conclusions. It performs reasoning using
two major strategies:

a) Forward chaining
b) Backward chaining

a) Forward Chaining

Forward chaining is data-driven reasoning.

The system starts with known facts and applies rules to infer new facts.

Steps

1. Start with known facts

2. Find rules whose conditions match facts
3. Apply rule
4. Add new fact
5. Repeat

Example

Facts:

temperature = 39
cough = true

Rules:

R1: IF temperature > 38 THEN fever

R2: IF fever AND cough THEN flu

Reasoning:

Step 1:

temperature > 38 → fever

Step 2:

fever AND cough → flu

Conclusion:

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 5 of 19
Patient has flu

b) Backward Chaining

Backward chaining is goal-driven reasoning. The system starts with a goal and tries to prove it.

Steps

1. Identify goal
2. Find rules that produce goal
3. Check if rule conditions are true
4. Recursively verify conditions

Example

Goal:

flu

Rule:

IF fever AND cough THEN flu

Check:

fever?
cough?

If both true → goal achieved.

4) Rule Set Representation

Concepts can be represented by multiple rules.

Example:

Rule 1:
IF sunny AND humidity low
THEN play

Rule 2:
IF overcast
THEN play

Rule 3:
IF rain AND wind weak
THEN play
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 6 of 19
5) Learning Rules from Data
Instead of writing rules manually, machine learning algorithms can learn rules automatically.

Two common approaches:

1. Decision tree to rules

2. Direct rule learning (Develop Hypothesis (Specific (S) and Generalized (G) from given Data)

5.1 Converting Decision Trees to Rules

A decision tree can be converted to rules.

Example tree:

Converted rules:

Rule 1:
IF outlook = sunny AND humidity = high
THEN play = no

Rule 2:
IF outlook = sunny AND humidity = normal
THEN play = yes

Rule 3:
IF outlook = rain
THEN play = yes

Each path from root to leaf becomes a rule.

6) First Order Rule Learning

In more complex systems, rules involve variables and relations.

Example:
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 7 of 19
IF parent(X,Y)
THEN ancestor(X,Y)

Another rule:

IF parent(X,Z) AND ancestor(Z,Y)

THEN ancestor(X,Y)

These rules allow recursive reasoning.

7) Limitations of Rule-Based Systems

7.1 Rule Explosion

Large systems require many rules.

Example: Medical expert systems may contain thousands of rules.

7.2 Knowledge Acquisition Problem

Expert knowledge is difficult to encode.

7.3 Conflict Resolution

Multiple rules may fire simultaneously.

Example:

Rule1 → disease = flu

Rule2 → disease = covid

The system must decide which rule to use.

7.4 Handling Uncertainty

Classical rules assume certainty.

Real-world problems require probabilistic reasoning.

8) Knowledge Representation Issues

Knowledge Representation (KR) is the method used to represent information about the world in
a form that a computer system can understand and reason with. When designing a knowledge
representation scheme, several important issues must be considered to ensure the system is
effective and useful.

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 8 of 19
8.1 Representational Adequacy
Representational adequacy refers to the ability of a knowledge representation scheme to
represent all the necessary knowledge about a domain.

A good KR system must be capable of representing:

• objects
• relationships between objects
• properties of objects
• events and actions

8.2 Inferential Adequacy

Inferential adequacy is the ability of the representation to allow new knowledge to be
inferred from existing knowledge.

The system should support reasoning mechanisms such as:

• logical deduction
• rule application
• inference procedures

Example:

If the system knows:

IF fever AND cough THEN flu

and it knows the facts:

fever = true
cough = true

then it should infer: flu

8.3 Inferential Efficiency

Even if knowledge can be represented and inferred, the process must be computationally
efficient.

A representation should therefore:

• organize knowledge in a way that speeds up reasoning

• avoid unnecessary computations

Example:

Indexing rules so that only relevant rules are checked.

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 9 of 19
8.4 Acquisitional Efficiency
Acquisitional efficiency refers to the ease with which new knowledge can be added or
updated in the system.

A good KR system should allow:

• easy modification of knowledge

• addition of new rules or facts
• updating outdated knowledge

Example:

Adding a new rule:

IF sore_throat AND fever

THEN throat_infection

should not require redesigning the entire system.

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 10 of 19
9) Predicate Logic
9.1 Components of Predicate Logic

Predicate logic consists of several basic elements.

9.1.1 Constants

Constants represent specific objects in the domain.

Examples:
John
India
Car1

Example statement:

Student(John)

This means John is a student.

9.1.2 Variables

Variables represent general objects.

Examples:

x, y, z

Example:

Student(x)

This means x is a student.

9.1.3 Predicates

A predicate represents a property of an object or a relationship between objects.

General form:
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 11 of 19
Predicate(object1, object2,….....)

Examples:

Student(x)
Parent(x,y)
Likes(John,IceCream)

Example interpretation:

Parent(John,Mary)

means John is the parent of Mary.

9.1.4 Functions

Functions map objects to other objects.

Example-1 :

FatherOf(x)

Example statement:

Parent(FatherOf(x), x)

Meaning:

The father of x is a parent of x.

Example -2
CapitalOf(x)

Example statement:
LocatedIn(CapitalOf(x), x)

Meaning:
The capital of x is located in x.

9.1.5 Quantifiers

Predicate logic uses quantifiers to express statements about groups of objects.

a) Universal Quantifier (∀)

The universal quantifier means “for all”.

Symbol:

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 12 of 19
∀ : forall

Example:

∀x Student(x) → Studies(x)

Meaning:

All students study.

b) Existential Quantifier (∃)

The existential quantifier means “there exists”.

Symbol:

∃x

Example:

∃ x Student(x)

Meaning:

There exists at least one student.

9.1.6 Logical Connectives

Predicate logic also uses logical operators.

Symbol Meaning
∧ AND
∨ OR
¬ NOT
→ IMPLIES

Example:

Student(x) ∧ Smart(x)

Meaning:

x is a student and x is smart.

Example

The example given below demonstrates knowledge representation and logical reasoning using
predicate logic.
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 13 of 19
Consider the following facts:

Parent(John,Mary)
Parent(Mary,Sam)

Rule:

∀x ∀y Parent(x,y) → Ancestor(x,y)

Another rule:

∀x ∀y ∀z Parent(x,z) ∧ Ancestor(z,y) → Ancestor(x,y)

Inference:

Ancestor(John,Sam)

9.2 Advantages of Predicate Logic

1. Expressive representation
Can represent relationships between objects.
2. Supports reasoning
Logical inference can derive new knowledge.
3. Generalization using variables
Rules can apply to many objects.
4. Foundation for rule learning algorithms
Used in many machine learning systems.

9.3 Limitations
1. Reasoning can be computationally expensive.
2. Requires formal logical formulation of knowledge.
3. Handling uncertainty is difficult.

9.4 Role in Machine Learning

Predicate logic is very useful in Machine Learning in learning Rules/Hypotheses from examples
and express them using predicate logic

Example learned rule:

Grandparent(x,y) ← Parent(x,z) ∧ Parent(z,y)

This rule can be learned from data.

10) What is a Concept

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 14 of 19
A concept is a rule or function that classifies objects (instances/examples) into positive or
negative categories.

• Formally:
A concept is a function

f : X→{0,1}

where:

o X = set of all possible instances

o Output = 1 (belongs to concept) or 0 (does not belong)

Example

Each day is described by attributes/features:

• Sky : Sunny / Rainy

• Temperature : Warm / Cold
• Humidity : Normal / High
• Wind : Strong/Weak
• Water : Cool/Warm
• Forecast : Change/Same

Instances / Examples:
Sky Temp Humidity Wind Water Forecast
Sunny Warm Normal Strong Warm Same
Sunny Warm High Strong Warm Same
Rainy Cold High Strong Warm Change
Sunny Warm High Strong Cool Same
Sunny Warm High Weak Cool Change

Concept:

A function
f= “If Sky = Sunny AND Temp = Warm” AND Humidity=High/Normal AND
Wind=Strong AND Water = Warm/Cool AND Forecast = Same
Then EnjoySport = Positive”

The Concept when applied on the instances/examples classifies them as follows:

Sky Temp Humidity Wind Water Forecast Enjoy Sport

Sunny Warm Normal Strong Warm Same +
Sunny Warm High Strong Warm Same +
Rainy Cold High Strong Warm Change -
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 15 of 19
 Sky Temp Humidity Wind Water Forecast Enjoy Sport
Sunny Warm High Strong Cool Change +

So, in the above example the “Concept” is the hidden rule/hypothesis that classifies the
examples/ instances into two classes i.e. “Yes” from “No”.

11) What is Concept Learning

Concept learning is the process of formulation of a concept by using labelled training
examples.
• Input: examples with labels (positive/negative)
• Output: a hypothesis (rule) that approximates the true concept

Key idea : We don’t know the true rule → we try to learn it from data.

12) Concept Learning as Search

Concept learning = searching through the hypothesis space

Why is it a search problem?

• We have many possible hypotheses (rules)

• We must find the one that:
o Fits training data
o Generalizes well

Example : Candidate Elimination Algorithm is a search process for an Upper (G Set) and Lower
bound (S Set) of the Hypotheses space that fits into the examples or training data. Candiadet
Elimination Algorithm was already covered earlier.

13) Find-S Algorithm

What is Find-S?

Find-S is a simple concept learning algorithm that:

• Finds the most specific hypothesis consistent with all positive training examples
• Ignores negative examples

It searches from most specific → more general

Representation
Each hypothesis is a conjunction of attributes/features:
• Specific value (e.g., Sunny)
• “?” → any permitted value allowed
• “Ø” → most specific (no value/Null)

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 16 of 19
Algorithm Steps

1. Initialize hypothesis: h=⟨Ø,Ø,Ø,...⟩ where hi is the ith attribute of the hypothesis(h)

2. For each positive example:
o For each attribute: If hi=Ø, replace with example value Else if hi≠ corresponding attribute
value in the example then replace hi with “?”
3. Ignore negative examples
4. Output final hypothesis

Example (Classic EnjoySport)

Attributes:
• Sky: Sunny / Rainy
• Temp: Warm / Cold
• Humidity: Normal / High

Training Data:
Sky Temp Humidity EnjoySport
Sunny Warm Normal Yes
Sunny Warm High Yes
Rainy Cold High No

Step-by-Step Execution

Step 0: Initialize : h = ⟨Ø, Ø, Ø⟩

Step 1: First positive example: (Sunny, Warm, Normal)

h = ⟨Sunny, Warm, Normal⟩

Step 2: Second positive example: (Sunny, Warm, High)

Compare attribute-wise:
• Sky: Sunny = Sunny → keep
• Temp: Warm = Warm → keep
• Humidity: Normal ≠ High → generalize → ?

h = ⟨Sunny, Warm, ?⟩

Step 3: Negative example: (Rainy, Cold, High) → ignored because it is a negative example

Final Hypothesis: h = ⟨Sunny, Warm, ?⟩

Meaning of the Final Hypothesis : “EnjoySport = Yes if Sky = Sunny AND Temp = Warm”

14) Inductive Bias of Candidate Elimination Algorithm

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 17 of 19
What is Candidate Elimination?

This algorithm maintains the Hypotheses ( or version) space:

• All hypotheses consistent with training data

It maintains:
• S → most specific boundary
• G → most general boundary

What is Inductive Bias?

Inductive bias is the assumptions a learning algorithm makes to generalize beyond training data.
Without bias, learning is impossible (infinite hypotheses!)

Inductive Bias of Candidate Elimination

The Candidate Elimination algorithm assumes:

1) Target concept lies in hypothesis space (H)

It assumes:

The actual target concept can be represented using the chosen hypothesis language

Example:

• H allows only conjunctions (AND rules)

• If true concept is OR-based → algorithm fails

2) Preference for consistency

It considers only hypotheses consistent with all training data

• Any hypothesis inconsistent with even one example → eliminated

3) No preference among consistent hypotheses

Unlike Find-S:

• It does NOT pick one preferred hypothesis

• It keeps all possible consistent hypotheses

4) General-to-specific ordering bias

The algorithm assumes:

• Hypotheses can be ordered by generality

• Learning = narrowing between S and G

Example to Understand Bias

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 18 of 19
Attributes:

• Color: Red / Blue

• Shape: Circle / Square

Training Data:

Color Shape Label

Red Circle Yes
Blue Circle No

Hypothesis Space:

All conjunctions like:

• ⟨Red, ?⟩
• ⟨?, Circle⟩
• ⟨Red, Circle⟩

What Candidate Elimination Does:

• Keeps all consistent hypotheses:

o ⟨Red, ?⟩
o ⟨Red, Circle⟩

Inductive Bias in Action

It assumes:

• True concept is one of these hypotheses

• Ignores hypotheses outside H (e.g., OR rules like “Red OR Circle”)

*** End of Document ***

_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 19 of 19