Issues in Knowledge Representation & Resolution

Part 1: Issues in Knowledge Representation (4 marks)

Knowledge representation deals with how knowledge about the world can be represented so that a computer system can use it to solve complex problems. The major issues are:

1. Representational Adequacy

The knowledge representation scheme must be able to represent all kinds of knowledge needed for the domain. It should handle facts, rules, relationships, and exceptions without loss of information.

2. Inferential Adequacy

The system must be able to derive new knowledge from existing knowledge. The representation must support valid inferences and reasoning mechanisms.

3. Inferential Efficiency

The system should be able to draw inferences quickly and efficiently. The representation should allow the inference engine to focus on relevant knowledge and avoid unnecessary search.

4. Acquisitional Efficiency

It should be easy to add new knowledge to the system without reorganizing the entire knowledge base. The representation should support incremental knowledge acquisition.

5. Expressiveness

The representation language must be expressive enough to capture complex relationships, uncertainty, time, and context in the real world.

6. Consistency and Completeness

The knowledge base should be free from contradictions (consistent) and should contain all necessary facts (complete) to answer queries correctly.

7. Handling Uncertainty

Real-world knowledge is often incomplete or uncertain. The representation must handle probabilistic or fuzzy information.

Part 2: Resolution Proof (6 marks)

Knowledge Base (Given Facts)

Let us define the predicates:

• Fruit(x) : x is a fruit
• Likes(x, y) : x likes y
• Eats(x, y) : x eats y
• Loves(x, y) : x loves y

Given Knowledge Base (Axioms)

Convert to Conjunctive Normal Form (CNF) / Clausal Form

F5: ∀x ∀y [Eats(x,y) ∧ Loves(x,y) → Fruit(y)] = ∀x ∀y [¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)] Clause C5: {¬Eats(x,y), ¬Loves(x,y), Fruit(y)}

F6: ∀x ∀y [Eats(x,y) ∧ Loves(x,y) → Likes(x,y)] = ∀x ∀y [¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Likes(x,y)] Clause C6: {¬Eats(x,y), ¬Loves(x,y), Likes(x,y)}

All Clauses:

a.) Prove: Ava likes watermelon → Likes(Ava, Watermelon)

Negate the goal: ¬Likes(Ava, Watermelon) → Clause C7

Resolution Steps:

Step 1: Resolve C6 and C3
         C6: ¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Likes(x,y)
         C3: Eats(Ava, Watermelon)
         Unifier: {x=Ava, y=Watermelon}
         Result C8: ¬Loves(Ava, Watermelon) ∨ Likes(Ava, Watermelon)

Step 2: Resolve C8 and C4
         C8: ¬Loves(Ava, Watermelon) ∨ Likes(Ava, Watermelon)
         C4: Loves(Ava, Watermelon)
         Result C9: Likes(Ava, Watermelon)

Step 3: Resolve C9 and C7
         C9: Likes(Ava, Watermelon)
         C7: ¬Likes(Ava, Watermelon)
         Result: □ (Empty Clause - Contradiction)

Proved: Ava likes watermelon ✓

b.) Prove: Apple and Watermelon are fruits

For Apple: Fruit(Apple) is already given as clause C1, so the proof is immediate.

Negate the goal: C7': ¬Fruit(Apple)

Step 1: Resolve C7' and C1
         C1 : Fruit(Apple)
         C7': ¬Fruit(Apple)
         Result: □ (Empty Clause - Contradiction)

For Watermelon: Fruit(Watermelon) is given as C2, but it can also be derived from the rule C5, which is the more informative proof.

Negate the goal: C7'': ¬Fruit(Watermelon)

Step 1: Resolve C5 and C3
         C5: ¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)
         C3: Eats(Ava, Watermelon)
         Unifier: {x=Ava, y=Watermelon}
         Result C10: ¬Loves(Ava, Watermelon) ∨ Fruit(Watermelon)

Step 2: Resolve C10 and C4
         C4: Loves(Ava, Watermelon)
         Result C11: Fruit(Watermelon)

Step 3: Resolve C11 and C7''
         Result: □ (Empty Clause - Contradiction)

Proved: Apple and Watermelon are fruits ✓

c.) Prove: Ava eats watermelon and loves it so much

The goal is the conjunction Eats(Ava, Watermelon) ∧ Loves(Ava, Watermelon). Negating a conjunction gives a single disjunctive clause.

Negate the goal: C12: ¬Eats(Ava, Watermelon) ∨ ¬Loves(Ava, Watermelon)

Step 1: Resolve C12 and C3
         C3: Eats(Ava, Watermelon)
         Result C13: ¬Loves(Ava, Watermelon)

Step 2: Resolve C13 and C4
         C4: Loves(Ava, Watermelon)
         Result: □ (Empty Clause - Contradiction)

Proved: Ava eats watermelon and loves it so much ✓

d.) Prove: Anything eaten by anybody and loved so much is a fruit

The goal is the universally quantified rule ∀x ∀y [Eats(x,y) ∧ Loves(x,y) → Fruit(y)]. Its negation is existential, so the two existential variables are replaced by Skolem constants a and b, giving three unit clauses.

Negate the goal:
   ¬∀x ∀y [¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)]
 = ∃x ∃y [Eats(x,y) ∧ Loves(x,y) ∧ ¬Fruit(y)]

Skolemize with constants a and b:
   C14: Eats(a, b)
   C15: Loves(a, b)
   C16: ¬Fruit(b)

Step 1: Resolve C5 and C14
         C5 : ¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)
         Unifier: {x=a, y=b}
         Result C17: ¬Loves(a, b) ∨ Fruit(b)

Step 2: Resolve C17 and C15
         Result C18: Fruit(b)

Step 3: Resolve C18 and C16
         Result: □ (Empty Clause - Contradiction)

Proved: anything eaten by somebody and loved so much is a fruit ✓

Conclusion

Resolution refutation works the same way in all four parts: the knowledge base is converted to clausal form, the statement to be proved is negated and added to the clause set, and clauses are resolved with the most general unifier until the empty clause appears. Reaching the empty clause shows that the negated goal is inconsistent with the knowledge base, which means the original goal follows from it. Parts b and c resolve directly against the given facts, while parts a and d need the implication clauses C6 and C5 with the substitution {x = Ava, y = Watermelon} and the Skolem constants respectively.

Mathematical Model of a Neuron, Learning Rule vs Learning Rate, and Back-Propagation Algorithm

Note: No specific curriculum notes were provided for this question. The answer below is based on standard, correct Artificial Neural Networks (ANN) theory as taught in BSc CSIT Neural Networks / AI courses.

1. Mathematical Model of a Neuron (McCulloch-Pitts Model)

A biological neuron is mathematically modelled as a processing unit that receives multiple inputs, weights them, sums them, and passes the result through an activation function.

Structure

x1 --w1--|
x2 --w2--|
x3 --w3--|--> [Σ Weighted Sum] --> [Activation f] --> Output y
  ...     |
xn --wn--|
         |
        bias (b)

Mathematical Expression

Step 1: Weighted Sum (Net Input)

$$net = \sum_{i=1}^{n} w_i x_i + b$$

Where:

• $x_i$ = input signals ($x_1, x_2, \ldots, x_n$)
• $w_i$ = synaptic weights corresponding to each input
• $b$ = bias term (threshold)
• $net$ = net activation value

Step 2: Activation Function

$$y = f(net) = f\left(\sum_{i=1}^{n} w_i x_i + b\right)$$

Where $f(\cdot)$ is the activation function. Common choices:

Vector Form

$$y = f(\mathbf{w}^T \mathbf{x} + b)$$

Where $\mathbf{w} = [w_1, w_2, \ldots, w_n]^T$ and $\mathbf{x} = [x_1, x_2, \ldots, x_n]^T$.

2. Distinction Between Learning Rule and Learning Rate

Example (Delta Rule):

$$\Delta w_i = \eta \cdot (t - y) \cdot x_i$$

• Learning rule here is the Delta Rule (error-correction rule)
• Learning rate is $\eta$ (e.g., 0.1)

3. Back-Propagation Algorithm in Learning

What is Back-Propagation?

Back-propagation (BP) is a supervised learning algorithm used to train multi-layer feedforward neural networks (MLPs). It works by propagating the output error backward through the network to compute gradients and update weights using gradient descent.

Network Architecture

Input Layer    Hidden Layer    Output Layer
  x1 ------>  h1 ------>  o1
  x2 ------>  h2 ------>  o2
  x3 ------>  h3

Algorithm Steps

Phase 1: Forward Pass

1. Present input $\mathbf{x}$ to the network.
2. Compute net input and output at each hidden neuron $j$:

$$net_j = \sum_i w_{ij} x_i + b_j, \quad h_j = f(net_j)$$

3. Compute net input and output at each output neuron $k$:

$$net_k = \sum_j w_{jk} h_j + b_k, \quad o_k = f(net_k)$$

Phase 2: Compute Output Error

For each output neuron $k$, compute the error:

$$E = \frac{1}{2} \sum_k (t_k - o_k)^2$$

Where $t_k$ is the target (desired) output and $o_k$ is the actual output.

Phase 3: Backward Pass (Error Propagation)

At Output Layer:

Compute error signal (delta) for output neuron $k$:

$$\delta_k = (t_k - o_k) \cdot f'(net_k)$$

For sigmoid: $f'(net_k) = o_k(1 - o_k)$

So: $\delta_k = (t_k - o_k) \cdot o_k(1 - o_k)$

At Hidden Layer:

Propagate error back to hidden neuron $j$:

$$\delta_j = \left(\sum_k \delta_k \cdot w_{jk}\right) \cdot f'(net_j)$$

$$\delta_j = \left(\sum_k \delta_k \cdot w_{jk}\right) \cdot h_j(1 - h_j)$$

Phase 4: Update the Weights

Each weight is adjusted against its own delta and the activation feeding it, where $\eta$ is the learning rate:

$$w_{jk} \leftarrow w_{jk} + \eta \cdot \delta_k \cdot h_j$$

$$w_{ij} \leftarrow w_{ij} + \eta \cdot \delta_j \cdot x_i$$

The forward and backward passes repeat for every training pattern until the total error $E$ falls below the chosen tolerance or the epoch limit is reached.

Role of Rewards and Punishment in Reinforcement Learning

What is Reinforcement Learning?

Reinforcement Learning (RL) is a type of machine learning where an agent learns to make decisions by interacting with an environment. The agent learns through trial and error, guided by feedback in the form of rewards and punishments.

Role of Rewards

A reward is a positive numerical signal given to the agent when it performs a desirable action. It tells the agent: "This was a good move, do more of this."

Role of rewards:

• Encourages the agent to repeat beneficial actions
• Guides the agent toward the goal state
• Increases the probability of selecting the same action in similar future states
• Helps the agent learn an optimal policy (best strategy)

Role of Punishment (Negative Reward / Penalty)

A punishment is a negative numerical signal given when the agent performs an undesirable action. It tells the agent: "This was a bad move, avoid this."

Role of punishment:

• Discourages the agent from repeating harmful or incorrect actions
• Helps the agent avoid dangerous or unproductive states
• Speeds up learning by narrowing down the action space

Core Objective

The agent's goal is to maximize the cumulative reward (total reward over time), formally expressed as:

$$G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots$$

Where:

• $G_t$ = total cumulative reward from time step $t$
• $r$ = reward at each step
• $\gamma$ = discount factor (0 to 1), which reduces the weight of future rewards

Example: Training a Robot to Navigate a Maze

Consider a robot agent placed in a maze that must find the exit.

Learning Process:

1. Initially, the robot moves randomly.
2. When it hits a wall, it receives -5, so it learns to avoid walls.
3. When it moves toward the exit, it receives +10, so it repeats that direction.
4. Over many episodes, the robot learns the optimal path to the exit by maximizing total reward.

Summary

In essence, rewards and punishments together act as a feedback mechanism that shapes the agent's behavior over time, enabling it to learn complex tasks without explicit programming.