BE Computer Engineering (IOE, TU) Artificial Intelligence (IOE, CT 653) Question Paper 2078 Nepal

Intelligent Agent

An intelligent agent is any entity that perceives its environment through sensors and acts upon that environment through actuators so as to achieve its goals. A rational agent is one that, for each possible percept sequence, selects an action that is expected to maximise its performance measure, given the evidence provided by the percept sequence and its built-in knowledge.

PEAS Framework

The task of an agent is fully specified by the PEAS description:

Example (automated taxi): P = safe, fast, legal, comfortable trip, maximise profit; E = roads, traffic, pedestrians, customers; A = steering, accelerator, brake, signal, horn; S = cameras, GPS, speedometer, odometer, sensors.

(a) Model-based Reflex Agent vs Utility-based Agent (8)

Model-based reflex agent

It keeps an internal state that depends on the percept history and reflects the unobserved aspects of the current state. It uses a model of the world (how the world evolves and how the agent's actions affect it) to update this state, then applies condition–action rules to choose an action.

        +---------------------------------------------+
Percepts|  Sensors --> [State] <-- How world evolves   |
  --->  |               |        What my actions do   |
        |               v                             |
        |        Condition-action rules --> Actuators | ---> Actions
        +---------------------------------------------+

Utility-based agent

Goals alone give only a binary distinction (happy/unhappy). A utility function maps a state (or sequence of states) to a real number expressing the degree of desirability. The agent chooses the action that maximises expected utility, allowing it to trade off conflicting goals (e.g. speed vs safety) and handle uncertainty.

        +-----------------------------------------------------+
Percepts|  Sensors --> [State] --> What it will be like if I   |
  --->  |                          do action A                |
        |                          --> How happy will I be    |
        |                              (Utility) --> Actuators | ---> Actions
        +-----------------------------------------------------+

Distinction

(b) Task Environment of an Automated Taxi Driver (4)

(It is also multi-agent, since other vehicles are independent agents.)

(a) Admissibility and Consistency (5)

Admissible heuristic: $h(n)$ never overestimates the true cost $h^*(n)$ from node $n$ to the goal, i.e.

$$0 \le h(n) \le h^*(n) \quad \text{for every node } n.$$

Consistent (monotone) heuristic: for every node $n$ and every successor $n'$ reached by action with step cost $c(n,n')$,

$$h(n) \le c(n,n') + h(n'), \qquad h(\text{goal}) = 0.$$

Consistency implies admissibility.

Verification of the given heuristic. The true (optimal) costs to G are:

Since $h(n) \le h^*(n)$ for every node, the heuristic is admissible.

(b) A* Search from A to G (8)

We expand the node with the smallest $f(n)=g(n)+h(n)$. Edges (undirected costs): A-B=3, A-D=5, B-C=4, C-G=5, D-G=9.

Step 1 – Expand A (g=0)

• B: g=3, f = 3+6 = 9
• D: g=5, f = 5+7 = 12

Open = {B(9), D(12)} , Closed = {A}

Step 2 – Expand B (smallest f=9, g=3)

• C: g = 3+4 = 7, f = 7+4 = 11

Open = {C(11), D(12)} , Closed = {A, B}

Step 3 – Expand C (f=11, g=7)

• G: g = 7+5 = 12, f = 12+0 = 12

Open = {G(12), D(12)} , Closed = {A, B, C}

Step 4 – Expand G (f=12) → Goal reached.

(The alternative path A→D→G has g = 5+9 = 14, f = 14, which is larger and never chosen.)

Optimal path: A → B → C → G with total cost 12.

(c) Why A* is Optimal with an Admissible Heuristic (3)

With an admissible heuristic, $f(n)=g(n)+h(n)$ never overestimates the true cost of the cheapest solution through $n$. Suppose a sub-optimal goal $G_2$ (cost $C_2 > C^*$) is on the open list at the same time as a node $n$ on an optimal path. Then $f(G_2)=g(G_2)=C_2 > C^* \ge f(n)$, so A* always expands $n$ before $G_2$. Hence A* can never select a sub-optimal goal for expansion before reaching the optimal one, guaranteeing an optimal solution (for tree search; graph search additionally needs consistency).

(a) FOPL Representation and Resolution Refutation (8)

Statements in First Order Predicate Logic

1. All students who study hard pass the exam:

$$\forall x\,[\,(Student(x) \wedge StudiesHard(x)) \rightarrow Passes(x)\,]$$

2. Ram is a student: $Student(Ram)$
3. Ram studies hard: $StudiesHard(Ram)$

Goal to prove: $Passes(Ram)$.

Conversion to clausal (CNF) form

Eliminate implication in (1): $\forall x\,[\,\neg Student(x) \vee \neg StudiesHard(x) \vee Passes(x)\,]$. The clauses are:

• C1: $\neg Student(x) \vee \neg StudiesHard(x) \vee Passes(x)$
• C2: $Student(Ram)$
• C3: $StudiesHard(Ram)$

Negate the goal (refutation): add $C4:\ \neg Passes(Ram)$.

Resolution steps

The derivation of the empty clause $\square$ shows a contradiction, so the negated goal is false; therefore $Passes(Ram)$ is proved.

(b) Unification and the Most General Unifier (4)

Unification is the process of finding a substitution $\theta$ that makes two literals (or terms) syntactically identical. It is essential in resolution because two clauses can be resolved only when a literal in one and the complementary literal in the other can be made equal by such a substitution.

The Most General Unifier (MGU) is the least constraining unifier: any other unifier can be obtained from it by an additional substitution. Using the MGU keeps inferences as general as possible.

Example. Unify $Knows(John, x)$ and $Knows(y, Mother(y))$:

• $y/John$, then $x/Mother(John)$.
• MGU $\theta = \{y/John,\ x/Mother(John)\}$, giving the common instance $Knows(John, Mother(John))$.

A more specific unifier such as $\{y/John, x/Mother(John)\}$ together with extra bindings would be less general; the MGU above is the most general one.

(a) Multilayer Perceptron and Backpropagation (8)

Architecture (feed-forward MLP)

  Inputs        Hidden layer        Output layer
   x1 ---\        (o)----\
   x2 ----+----->(o)-----+----->( o ) ---> y1
   x3 ---/        (o)----/        ( o ) ---> y2
            w_ij            w_jk

Neurons are arranged in layers; every neuron in one layer connects to every neuron in the next via weighted edges. Signals flow only forward (input → hidden → output). Each neuron computes a weighted sum plus bias and passes it through a non-linear activation $f$.

Backpropagation training (idea)

1. Forward pass: propagate the input through the network to compute the output $\hat{y}$.
2. Compute error using a loss function, e.g. $E = \tfrac{1}{2}\sum_k (t_k - o_k)^2$.
3. Backward pass: propagate the error gradient from the output layer back to the input layer using the chain rule, computing $\partial E/\partial w$ for each weight.
4. Update weights by gradient descent: $w \leftarrow w - \eta\,\dfrac{\partial E}{\partial w}$. Repeat for many epochs until the error converges.

Derivation of the output-layer weight update

Let output neuron $k$ have net input $net_k=\sum_j w_{jk}o_j$, output $o_k=f(net_k)$, target $t_k$, and $E=\tfrac12\sum_k(t_k-o_k)^2$. By the chain rule:

$$\frac{\partial E}{\partial w_{jk}} = \frac{\partial E}{\partial o_k}\cdot\frac{\partial o_k}{\partial net_k}\cdot\frac{\partial net_k}{\partial w_{jk}}.$$

Now $\dfrac{\partial E}{\partial o_k} = -(t_k-o_k)$, $\dfrac{\partial o_k}{\partial net_k}=f'(net_k)$, and $\dfrac{\partial net_k}{\partial w_{jk}}=o_j$. Hence

$$\frac{\partial E}{\partial w_{jk}} = -(t_k-o_k)\,f'(net_k)\,o_j.$$

Defining the output-layer error term $\delta_k=(t_k-o_k)f'(net_k)$, the weight update rule is

$$\boxed{\,w_{jk} \leftarrow w_{jk} + \eta\,\delta_k\,o_j\,}$$

where $\eta$ is the learning rate. For a sigmoid, $f'(net_k)=o_k(1-o_k)$, so $\delta_k=(t_k-o_k)o_k(1-o_k)$.

(b) Activation Functions: Sigmoid vs ReLU (4)

An activation function introduces non-linearity into a neuron, enabling the network to learn complex, non-linear mappings. Without it, any stack of layers would collapse into a single linear transformation. It also bounds/transforms the neuron output.

One advantage of each:

• Sigmoid: smooth output in (0,1), useful as a probability at the output layer for binary classification.
• ReLU: avoids vanishing gradients for positive inputs and is computationally cheap, giving faster training in deep networks.

BFS vs DFS

Let $b$ = branching factor, $d$ = depth of the shallowest goal, $m$ = maximum depth of the search tree.

Summary: BFS guarantees the shallowest (optimal for unit costs) solution but uses huge memory; DFS uses little memory but may go deep, miss shallow goals, and is neither complete nor optimal in general.

When to prefer IDDFS

Iterative Deepening DFS runs DFS with increasing depth limits $0,1,2,\dots$ until the goal is found. It is preferred when:

• The search space is large or infinite and memory is limited, and
• The goal depth is unknown.

It combines the best of both: like DFS it needs only $O(bd)$ space, and like BFS it is complete and optimal (for unit step costs) with time $O(b^d)$. The repeated re-expansion of shallow nodes adds only a small constant overhead, so IDDFS is the preferred uninformed strategy when both memory efficiency and a shallowest-goal guarantee are required.

Semantic Networks and Frames

Semantic network: a graphical knowledge-representation scheme in which nodes represent objects, concepts or events and labelled directed edges (links) represent relationships between them. Common links are is-a (subclass/inheritance), instance-of, and property links such as has-part or can.

Frames: a structured representation where knowledge about a stereotyped object/situation is stored as a record of slots (attributes) and their fillers (values), which may be default values, constraints, or procedures (demons). Frames can be linked in an inheritance hierarchy, so a frame can inherit slot values from its parent frame. Frames are essentially a more structured form of semantic networks.

Semantic Network for the Given Fact

           is-a
  Sparrow --------> Bird
     |                |
  instance-of    can ----> Fly
     |                |
   Tweety        has-part-> Wings

Links used:

• Bird --can--> Fly
• Bird --has-part--> Wings
• Sparrow --is-a--> Bird
• Tweety --instance-of--> Sparrow

Property Inheritance to Tweety

Properties are inherited downward through is-a / instance-of links. Since Tweety is-a Sparrow and Sparrow is-a Bird, Tweety inherits the properties attached to Bird:

• Tweety can Fly (inherited from Bird)
• Tweety has Wings (inherited from Bird)

Thus, without storing these facts on Tweety directly, the network deduces that Tweety can fly and has wings through inheritance.

(a) Architecture of an Expert System (5)

   +-----------+      +----------------+      +-----------------+
   |   User    |<---->| User Interface |<---->| Inference Engine|
   +-----------+      +----------------+      +--------+--------+
                          ^                            |
                          |                            v
                  +---------------+            +-----------------+
                  | Explanation   |            |  Knowledge Base |
                  | Facility      |            | (rules + facts) |
                  +---------------+            +-----------------+
                          ^                            ^
                          |                            |
                  +---------------+            +-----------------+
                  | Working Memory|            | Knowledge       |
                  | (facts)       |            | Acquisition     |<-- Expert
                  +---------------+            +-----------------+

Knowledge Base: stores the domain knowledge as a set of IF–THEN production rules and facts gathered from human experts. It is the heart of the expert system and is kept separate from the reasoning mechanism so that knowledge can be updated independently.

Inference Engine: the reasoning component that applies the rules in the knowledge base to the facts in working memory to derive new conclusions / recommendations. It performs match → select (conflict resolution) → execute cycles, using forward or backward chaining, and drives the problem-solving process.

Other components: working memory (current facts), user interface, explanation facility (justifies conclusions), and knowledge-acquisition module (adds new knowledge).

(b) Forward vs Backward Chaining (3)

Example. Rules: R1: IF fever AND cough THEN flu; R2: IF flu THEN take rest. Facts: fever, cough.

• Forward: fever+cough ⇒ flu (R1) ⇒ take rest (R2). Conclusion derived from data.
• Backward: to prove goal take rest, R2 needs flu; to prove flu, R1 needs fever and cough, which are known ⇒ goal confirmed.

Heuristic Function

A heuristic function $h(n)$ is a problem-specific function that estimates the cost (or distance) from node $n$ to the goal. It uses domain knowledge to guide a search toward promising states, reducing the number of nodes explored. (e.g. straight-line distance in route finding, number of misplaced tiles in the 8-puzzle).

Hill-Climbing Search

Hill climbing is a local search that continually moves in the direction of increasing value (or decreasing cost). Working:

1. Start with an initial state.
2. Evaluate neighbours using the heuristic.
3. Move to the neighbour with the best (highest) heuristic value.
4. Repeat until no neighbour is better than the current state; return the current state.

It keeps only the current node (no backtracking, no search tree), so it is memory-efficient but greedy.

Problems

• Local maximum: a peak higher than its neighbours but lower than the global maximum; the algorithm stops here, missing the true optimum.
• Plateau: a flat region where neighbours have equal value, giving no gradient to follow, so the search wanders or halts.
• Ridge: a sequence of local maxima oriented diagonally; every single-step move lowers the value, so the search cannot climb the ridge efficiently.

Technique to Overcome

Use random-restart hill climbing (run hill climbing from many random initial states and keep the best result) or simulated annealing (occasionally accept worse moves with a probability that decreases over time), which let the search escape local maxima, plateaus and ridges.

Types of Machine Learning

Overfitting in Supervised Learning

Overfitting occurs when a model learns the training data too well, capturing not only the underlying pattern but also the noise and random fluctuations. As a result it gives very low training error but high test/generalisation error — it performs poorly on unseen data. It typically arises when the model is too complex (too many parameters) relative to the amount of training data, or when training runs too long.

Ways to reduce overfitting:

• Use more training data.
• Cross-validation to tune and select models.
• Regularisation (L1/L2) to penalise large weights.
• Pruning (decision trees) / dropout and early stopping (neural networks).
• Reduce model complexity / number of features.

Major Stages of Natural Language Processing

1. Lexical / Morphological analysis — Breaks the input text into tokens (words) and analyses the structure of individual words (root, prefix, suffix, part of speech). E.g. "unhappiness" → un- + happy + -ness. Identifies valid words and their basic grammatical category.

2. Syntactic analysis (parsing) — Arranges the tokens into a grammatical structure (parse tree) according to the rules of grammar, checking that the sentence is well-formed and revealing relationships such as subject–verb–object. Sentences that violate grammar (e.g. "Boy the apple eat") are rejected.

3. Semantic analysis — Derives the literal meaning of the sentence by mapping syntactic structures to meaning, checking that combinations of words make sense (e.g. "colourless green ideas" is grammatical but semantically anomalous).

4. Pragmatic analysis — Interprets the sentence in context, using real-world knowledge to find the intended meaning (e.g. "Can you pass the salt?" is a request, not a question about ability).

Example of Syntactic-Level Ambiguity

Sentence: "I saw the man with the telescope."

This has two valid parse trees (structural / syntactic ambiguity):

• with the telescope attaches to saw → I used a telescope to see the man.
• with the telescope attaches to the man → the man who had a telescope was seen.

Resolving which prepositional-phrase attachment is correct is an ambiguity handled at the syntactic level.

Minimax Algorithm

Minimax is a decision rule for two-player, zero-sum, perfect-information games (e.g. tic-tac-toe, chess). The two players are MAX (tries to maximise the score) and MIN (tries to minimise it). Assuming both play optimally:

• At MAX nodes choose the child with the maximum value.
• At MIN nodes choose the child with the minimum value.
• At terminal/leaf nodes use the utility (evaluation) function. Values are computed bottom-up to give the optimal move at the root.

Example game tree (leaf utilities shown):

            MAX
           /    \
        MIN      MIN
        / \      / \
       3   5    6   9

• Left MIN = min(3,5) = 3
• Right MIN = min(6,9) = 6
• Root MAX = max(3,6) = 6 → MAX chooses the right branch.

Alpha-Beta Pruning

Alpha-beta pruning returns the same minimax value but skips branches that cannot influence the final decision, so it explores far fewer nodes.

• $\alpha$ = best (highest) value found so far for MAX along the path.
• $\beta$ = best (lowest) value found so far for MIN along the path.
• Prune whenever $\alpha \ge \beta$ (further siblings cannot change the result).

With perfect move ordering, time improves from $O(b^d)$ to about $O(b^{d/2})$, effectively doubling the search depth.

Pruning illustration (same tree):

            MAX
           /    \
        MIN      MIN
        / \      / \
       3   5    6   [9]

• Evaluate left MIN = 3, so root has $\alpha = 3$.
• At right MIN, first child = 6. Since the right MIN will be $\le 6$ and could only lower its value, examine next child 9: 9 > 6 so MIN keeps 6. (If instead the first right child had been $\le 3$, the remaining sibling would be pruned because that MIN value $\le \alpha$ could never beat the left branch's 3 at MAX.)

General rule: a sibling is pruned once the running MIN value drops to $\le \alpha$ (or a running MAX value rises to $\ge \beta$), because the opponent would never let that branch be reached.

Conversion of FOL Sentences to CNF

(i) $\forall x\,(Person(x) \rightarrow \exists y\,Loves(x, y))$

Step 1 – Eliminate implication ($A\rightarrow B \equiv \neg A \vee B$):

$$\forall x\,(\neg Person(x) \vee \exists y\,Loves(x, y))$$

Step 2 – Move negations inward: already in negation normal form (no change).

Step 3 – Skolemize. $y$ is existentially quantified inside the scope of $\forall x$, so replace it with a Skolem function $f(x)$ depending on $x$:

$$\forall x\,(\neg Person(x) \vee Loves(x, f(x)))$$

Step 4 – Drop universal quantifiers:

$$\boxed{\neg Person(x) \vee Loves(x, f(x))}$$

This is a single clause in CNF. (Reading: every person loves someone $f(x)$, the person they love.)

(ii) $\forall x\,(Bird(x) \wedge \neg Penguin(x) \rightarrow CanFly(x))$

Step 1 – Eliminate implication:

$$\forall x\,(\neg(Bird(x) \wedge \neg Penguin(x)) \vee CanFly(x))$$

Step 2 – Move negations inward (De Morgan, double negation):

$$\forall x\,(\neg Bird(x) \vee Penguin(x) \vee CanFly(x))$$

Step 3 – Skolemize: no existential quantifiers → nothing to do.

Step 4 – Drop universal quantifiers:

$$\boxed{\neg Bird(x) \vee Penguin(x) \vee CanFly(x)}$$

This is a single disjunctive clause already in CNF.