Unification, Lifting in Predicate Logic & Knowledge Base Construction

Part 1: Unification and Lifting [4 Marks]

Unification

Unification is the process of finding a substitution (called a unifier) that makes two or more logical expressions identical.

• A substitution θ is a set of bindings of the form {x/term, y/term, ...}
• The Most General Unifier (MGU) is the most general substitution that unifies two expressions

Unification Algorithm Steps:

1. If both expressions are constants or the same variable, they unify (empty substitution)
2. If one is a variable, substitute it with the other term (occurs check: variable must not appear in the term)
3. If both are compound expressions, unify functor/predicate names and then unify arguments recursively
4. If none of the above, unification fails

Example:

Lifting

Lifting refers to the process of generalizing inference rules from propositional logic to first-order predicate logic by incorporating unification.

The key idea: instead of applying rules to ground (fully instantiated) sentences only, we lift them to work with variables using unification.

Example - Lifted Modus Ponens (Generalized Modus Ponens):

If we have:

• P(x) → Q(x) (for all x)
• P(John)

Then by unification {x/John}, we derive: Q(John)

Lifted Resolution:

Standard resolution in propositional logic:

From (A ∨ B) and (¬B ∨ C), derive (A ∨ C)

Lifted resolution in FOL:

From (P(x) ∨ Q(x)) and (¬P(John) ∨ R(y)), unify P(x) with P(John) using {x/John}, derive (Q(John) ∨ R(y))

Benefits of Lifting:

• Avoids instantiating all possible ground instances
• Makes inference efficient and general
• Enables working directly with universally quantified statements

Part 2: Knowledge Base in FOL and CNF Conversion [6 Marks]

Step 1: Represent Statements in FOL

Let:

• S(x) = x is a student
• Smart(x) = x is a smart person
• I(x) = x is intelligent
• H(x) = x is hardworking

Step 2: Convert Each Statement to CNF

CNF Conversion Steps:

1. Eliminate implications (A → B becomes ¬A ∨ B)
2. Move negations inward (De Morgan's laws)
3. Standardize variables apart
4. Skolemize (eliminate existential quantifiers)
5. Drop universal quantifiers
6. Distribute ∨ over ∧

Statement 1: ∀x [S(x) → Smart(x)]

• Eliminate implication: ∀x [¬S(x) ∨ Smart(x)]
• Drop universal quantifier:

CNF: ¬S(x) ∨ Smart(x)

Statement 2: ∀x [Smart(x) → ¬I(x)]

• Eliminate implication: ∀x [¬Smart(x) ∨ ¬I(x)]
• Drop universal quantifier:

CNF: ¬Smart(x) ∨ ¬I(x)

Statement 3: ∃x [I(x)]

• Skolemize: Replace ∃x with a Skolem constant c (since no universal quantifier wraps it)
• Result: I(c)

CNF: I(c)

Statement 4: [∀x (S(x) → I(x))] ∨ [∀x (S(x) → H(x))]

This is the most complex. First, standardize variables apart:

[∀x (S(x) → I(x))] ∨ [∀y (S(y) → H(y))]

• Eliminate implications:

[∀x (¬S(x) ∨ I(x))] ∨ [∀y (¬S(y) ∨ H(y))]

• Move quantifiers outward (prenex normal form):

∀x ∀y [(¬S(x) ∨ I(x)) ∨ (¬S(y) ∨ H(y))]

• Drop universal quantifiers:

(¬S(x) ∨ I(x) ∨ ¬S(y) ∨ H(y))

CNF: ¬S(x) ∨ I(x) ∨ ¬S(y) ∨ H(y)

Summary of CNF Clauses

Conclusion

Unification finds the substitution that makes two literals identical, and lifting is what allows the propositional inference rules to be applied directly to quantified first order sentences by using that substitution. Once every sentence of the knowledge base has been reduced to the four clauses above, resolution can be applied mechanically to them, since every clause is now a disjunction of literals with all quantifiers removed.

Learning Rule and Backpropagation in ANN

Part 1: What is a Learning Rule? [2 marks]

A learning rule is a method or procedure that modifies the weights and biases of a neural network in order to improve its performance on a given task. It defines how the network learns from training data by updating connection weights based on the error between the actual output and the desired output.

Common types of learning rules include:

• Hebbian Learning Rule - weights are updated based on the correlation of input and output activations
• Perceptron Learning Rule - weights are updated when the output is incorrect
• Delta (Widrow-Hoff) Rule - weights are updated proportional to the error
• Backpropagation Rule - generalized delta rule for multilayer networks

General form: $$\Delta w_{ij} = \eta \cdot \delta_j \cdot x_i$$ where $\eta$ is the learning rate, $\delta_j$ is the error signal, and $x_i$ is the input.

Part 2: Learning Using Backpropagation Algorithm [8 marks]

Overview

Backpropagation (BP) is a supervised learning algorithm used to train multilayer feedforward neural networks. It works by:

1. Forward pass - computing the output
2. Backward pass - propagating the error backward and updating weights

Network Architecture

Consider a three-layer network:

• Input layer - nodes indexed $i$
• Hidden layer - nodes indexed $j$
• Output layer - nodes indexed $k$

Step-by-Step Backpropagation Algorithm

Step 1: Initialize Weights

Set all weights $w_{ij}$ and $w_{jk}$ to small random values (typically between -0.5 and 0.5).

Step 2: Forward Pass (Feed Forward)

At the hidden layer, compute the net input and activation for each hidden neuron $j$:

$$net_j = \sum_i w_{ij} \cdot x_i + b_j$$

$$y_j = f(net_j) = \frac{1}{1 + e^{-net_j}} \quad \text{(sigmoid activation)}$$

At the output layer, compute the net input and activation for each output neuron $k$:

$$net_k = \sum_j w_{jk} \cdot y_j + b_k$$

$$o_k = f(net_k) = \frac{1}{1 + e^{-net_k}}$$

Step 3: Compute Output Error

For each output neuron $k$, compute the error signal $\delta_k$:

$$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.

The error gradient at the output layer:

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

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

$$\boxed{\delta_k = (t_k - o_k) \cdot o_k(1 - o_k)}$$

Step 4: Backpropagate Error to Hidden Layer

Compute the error signal $\delta_j$ for each hidden neuron $j$:

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

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

The error is propagated backward from output to hidden layer using the weights.

Step 5: Update Weights

Update weights between hidden and output layer:

$$\Delta w_{jk} = \eta \cdot \delta_k \cdot y_j$$

$$w_{jk}^{new} = w_{jk}^{old} + \Delta w_{jk}$$

Update weights between input and hidden layer:

$$\Delta w_{ij} = \eta \cdot \delta_j \cdot x_i$$

$$w_{ij}^{new} = w_{ij}^{old} + \Delta w_{ij}$$

where $\eta$ is the learning rate (typically 0.01 to 0.9).

Step 6: Repeat

Repeat Steps 2 to 5 for all training patterns until the total error $E$ is minimized below a threshold or the maximum number of epochs is reached.

Summary Diagram

Input Layer      Hidden Layer      Output Layer
   x_i  ---w_ij---> y_j ---w_jk---> o_k
                                      |
                              Error = (t_k - o_k)
                                      |
              <--- delta_j <--- delta_k (backpropagated)
              Weight update          Weight update

Key Points

Advantages and Limitations

Advantages:

• Can learn complex nonlinear mappings
• Works for multilayer networks

Limitations:

• May get stuck in local minima
• Slow convergence for large networks
• Requires labeled training data
• Sensitive to learning rate choice

Intelligent Agent and PEAS Framework for a Particle Picking Robot

What is an Intelligent Agent? [1 mark]

An intelligent agent is anything that can perceive its environment through sensors and act upon that environment through actuators in order to achieve its goals. An intelligent agent takes the best possible action based on its percepts, built-in knowledge, and past experience to maximize its performance measure.

PEAS Framework [4 marks]

PEAS stands for:

• P - Performance Measure
• E - Environment
• A - Actuators
• S - Sensors

PEAS is used to describe the task environment of an intelligent agent.

PEAS Framework for a Particle Picking Robot

Summary Table

Agent:  Particle Picking Robot
+------------------+------------------------------------------+
| P (Performance)  | Particles picked, surface cleanliness,   |
|                  | energy efficiency, time efficiency        |
+------------------+------------------------------------------+
| E (Environment)  | Factory floor, scattered particles,       |
|                  | obstacles, varying lighting               |
+------------------+------------------------------------------+
| A (Actuators)    | Robotic arm, gripper, wheels, suction,    |
|                  | deposit container                         |
+------------------+------------------------------------------+
| S (Sensors)      | Camera, proximity sensor, touch sensor,   |
|                  | position sensor, particle detector        |
+------------------+------------------------------------------+

Key Points to Remember

• The Performance Measure evaluates how well the agent is doing its job.
• The Environment defines where the agent operates.
• Actuators are the means by which the agent affects the environment.
• Sensors are the means by which the agent perceives the environment.

Dempster-Shafer Theory

Note: The reference notes did not contain this topic. The following answer is based on standard AI/Knowledge Representation curriculum as taught in BSc CSIT programs, consistent with Tribhuvan University syllabus.

(a) Dempster-Shafer Theory

Dempster-Shafer Theory (DST), also known as the Theory of Evidence or Belief Function Theory, was developed by Arthur Dempster and later extended by Glenn Shafer. It is a mathematical framework for reasoning under uncertainty that generalizes Bayesian probability theory by allowing degrees of belief to be assigned to sets of possibilities rather than individual outcomes.

Key Concepts

1. Frame of Discernment (Θ) A finite set of mutually exclusive and exhaustive hypotheses (possible answers to a question).

Example: Θ = {Disease A, Disease B, Disease C}

2. Basic Probability Assignment (BPA) / Mass Function m(·) A function m: 2^Θ → [0, 1] such that:

• m(∅) = 0
• Σ m(A) = 1, for all A ⊆ Θ

Here, m(A) represents the degree of belief (evidence mass) assigned directly to subset A, not distributed to its subsets.

3. Belief Function (Bel) The total belief committed to a hypothesis A, including all subsets of A:

Bel(A) = Σ m(B),  for all B ⊆ A, B ≠ ∅

4. Plausibility Function (Pl) The maximum possible support for A (belief that does not contradict A):

Pl(A) = Σ m(B),  for all B ∩ A ≠ ∅

The interval [Bel(A), Pl(A)] represents the uncertainty interval for hypothesis A.

5. Dempster's Rule of Combination When two independent sources of evidence provide mass functions m₁ and m₂, they are combined as:

m(A) = [ Σ m₁(B) · m₂(C) ] / (1 - K)
         B ∩ C = A

Where K is the conflict factor:

K = Σ m₁(B) · m₂(C),  for all B ∩ C = ∅

K measures the degree of conflict between the two sources.

(b) Use in Statistical Reasoning

Dempster-Shafer Theory is used in statistical reasoning in the following ways:

Example (Brief)

Suppose a doctor has two tests for a disease:

• Test 1 gives: m({Disease}) = 0.6, m({Healthy, Disease}) = 0.4
• Test 2 gives: m({Healthy}) = 0.7, m({Healthy, Disease}) = 0.3

Using Dempster's rule, these two pieces of evidence are combined to get a final belief, resolving the conflict statistically.

Summary

DST extends classical probability by allowing partial belief over subsets of hypotheses. It is particularly useful in statistical reasoning when evidence is incomplete, uncertain, or comes from multiple conflicting sources, making it a powerful tool in AI, expert systems, and decision making.

Discourse and Pragmatic Analytics in Natural Language Processing

1. Discourse Analytics

Discourse refers to the analysis of language beyond the sentence level. It deals with how sentences are connected and structured to form coherent text or conversation.

Key Components of Discourse Analytics:

a) Discourse Structure

• Analyzes how sentences and paragraphs are organized to convey meaning.
• Identifies rhetorical relations between text segments (e.g., cause-effect, contrast, elaboration).

b) Coreference Resolution

• Determines when different expressions in a text refer to the same entity.
• Example: "Ram went to the store. He bought milk." -- "He" refers to Ram.

c) Discourse Coherence

• Ensures that a text is logically and semantically connected.
• Models like Centering Theory track how entities are introduced and maintained across sentences.

d) Anaphora Resolution

• Identifies what a pronoun or noun phrase refers to in earlier text.
• Example: Resolving "it", "they", "this" to their antecedents.

e) Topic Segmentation

• Divides a document into segments based on topic shifts.
• Used in summarization, information retrieval, and dialogue systems.

2. Pragmatic Analytics

Pragmatics is the study of how context influences the interpretation of meaning. It goes beyond literal meaning to understand the intended meaning of an utterance.

Key Components of Pragmatic Analytics:

a) Speech Act Theory

• Proposed by Austin and Searle.
• Every utterance performs an act:
  • Locutionary act: The literal meaning.
  • Illocutionary act: The intended action (request, promise, warning).
  • Perlocutionary act: The effect on the listener.
• Example: "Can you pass the salt?" is a request, not a yes/no question.

b) Implicature

• Based on Grice's Cooperative Principle and maxims (Quantity, Quality, Relation, Manner).
• Speakers often imply more than they literally say.
• Example: "It's getting cold in here" implies "Please close the window."

c) Presupposition

• Information that is assumed to be true before an utterance is made.
• Example: "Have you stopped cheating?" presupposes the person was cheating.

d) Deixis

• Words whose interpretation depends on context (time, place, person).
• Types: Person deixis (I, you), Place deixis (here, there), Time deixis (now, then).

e) Dialogue and Conversation Management

• Analyzes turn-taking, topic management, and conversational implicature in dialogues.
• Important for building chatbots and dialogue systems.

3. Importance in NLP Applications

Summary

Discourse analytics focuses on structure and coherence of text across sentences, while pragmatic analytics focuses on contextual and intended meaning of language. Both are essential for building NLP systems that truly understand human language rather than just processing words in isolation.

Knowledge Representation Using Scripts

What is a Script?

A script is a structured representation of knowledge about a stereotyped sequence of events in a particular context. Scripts were introduced by Roger Schank and Robert Abelson (1977) to represent common, everyday situations that follow a predictable pattern.

A script describes a causally ordered sequence of events that are expected to occur in a specific situation. It allows an AI system to make inferences about what happened even when information is incomplete.

Components of a Script

A script consists of the following components:

Example: Restaurant Script

Script:    RESTAURANT
Track:     Coffee Shop
Entry Conditions:
           - Customer is hungry
           - Customer has money
Roles:
           - Customer (C)
           - Waiter (W)
           - Cook (K)
           - Cashier (Ca)
Props:
           - Tables, Menu, Food, Bill, Money

Scene 1: ENTERING
    - Customer enters restaurant
    - Customer looks for a table
    - Customer sits down

Scene 2: ORDERING
    - Waiter brings menu
    - Customer reads menu
    - Customer orders food
    - Waiter takes order to cook

Scene 3: EATING
    - Cook prepares food
    - Waiter brings food to customer
    - Customer eats food

Scene 4: LEAVING
    - Waiter brings bill
    - Customer pays bill
    - Customer leaves restaurant

Results:
    - Customer is no longer hungry
    - Customer has less money
    - Restaurant has more money

How Scripts Help in Inference

Consider the following story:

"John went to a restaurant. He ordered a burger. He left a tip."

Using the restaurant script, the AI system can infer the following facts that were never explicitly stated:

• John sat at a table
• A waiter brought him a menu
• John paid the bill before leaving
• John was hungry when he entered

This ability to fill in missing information is called script-based inference.

Advantages of Scripts

1. Allows inference about unstated events
2. Handles incomplete information effectively
3. Represents real-world common sense knowledge
4. Useful in natural language understanding systems

Limitations

1. Scripts are rigid and do not handle unexpected events well
2. Requires a large number of scripts to cover real-world situations
3. Difficult to handle novel situations not covered by existing scripts

Note: Scripts are a form of frame-based knowledge representation where knowledge is organized around a central concept or situation, making them suitable for AI systems dealing with natural language processing and story understanding.