BSc CSIT (TU) Science Artificial Intelligence (BSc CSIT, CSC261) Question Paper 2081 Nepal

Biological Neuron vs. Artificial Neural Network

The artificial neuron is a mathematical abstraction inspired by the biological neuron:

Thus dendrite → input link, synapse → weight, soma → weighted-sum + activation, axon → output connection.

A Multi-Layer ANN

A typical feed-forward network has three kinds of layers:

 Input layer        Hidden layer        Output layer
   x1 ----w11----->  h1 ----v1----->\
   x2 ----w12----->  h2 ----v2-----> [ y ]
   x3 ----w13----->  h3 ----v3----->/

Each hidden unit computes $h_j = f\!\left(\sum_i w_{ij} x_i + b_j\right)$ and the output computes $y = f\!\left(\sum_j v_j h_j + b_o\right)$, where $f$ is usually the sigmoid $f(z)=\dfrac{1}{1+e^{-z}}$.

Back-Propagation Learning Algorithm

Back-propagation is supervised, gradient-descent learning that minimizes the error $E=\tfrac{1}{2}\sum (t-y)^2$ (target $t$, output $y$).

Steps:

1. Initialize all weights and biases to small random values.
2. Forward pass: present an input pattern and compute activations layer by layer up to the output.
3. Compute output error for each output unit:

4. Back-propagate the error to each hidden unit:

5. Update weights using learning rate $\eta$:

6. Repeat steps 2–5 for all training patterns over many epochs until the error falls below a chosen threshold.

The key idea is the chain rule: the gradient of the error with respect to a weight is propagated backward from the output layer to the input layer, hence the name back-propagation.

Adversarial Search

Adversarial search deals with problems in which two or more agents have conflicting goals — the gain of one is the loss of another (zero-sum games such as Chess, Tic-Tac-Toe, Checkers). The agent must plan against an opponent who also plays optimally. The search space is modelled as a game tree where levels alternate between the player (MAX) and the opponent (MIN).

Minimax Algorithm

Minimax computes the optimal move assuming both players play optimally:

• MAX nodes choose the child with the maximum value.
• MIN nodes choose the child with the minimum value.
• Terminal/leaf nodes are scored by a utility/evaluation function.

function MINIMAX(node, isMax):
    if node is terminal: return utility(node)
    if isMax:
        best = -infinity
        for child in node: best = max(best, MINIMAX(child, false))
        return best
    else:
        best = +infinity
        for child in node: best = min(best, MINIMAX(child, true))
        return best

It is a depth-first exploration with time complexity $O(b^m)$ and space $O(bm)$, where $b$ = branching factor, $m$ = depth.

Alpha-Beta Pruning

Alpha-Beta pruning improves Minimax by eliminating branches that cannot affect the final decision, without changing the result.

• $\alpha$ = best (highest) value MAX can guarantee so far.
• $\beta$ = best (lowest) value MIN can guarantee so far.
• Prune (stop exploring) a node whenever $\alpha \ge \beta$.

With optimal move ordering it reduces complexity to $O(b^{m/2})$, effectively doubling the searchable depth.

Example Game Tree

                MAX
              /     \
           MIN       MIN
          /  \       /  \
         3    5     6    9
        (A)  (B)   (C)  (D)

• Left MIN node = min(3,5) = 3.
• For the right MIN node, after seeing 6 we know it will be ≤ 6. Since MAX already has 3 ($\alpha=3$) and 6 > 3, MAX may still prefer this branch, so we examine 9 → min(6,9) = 6.
• Root MAX = max(3, 6) = 6.

If instead the right subtree began with a value ≤ 3 (say 1), then once that leaf is seen $\beta=1 \le \alpha=3$, the remaining siblings of that node are pruned, because MAX would never choose this branch.

Expert System

An expert system is an AI program that emulates the decision-making ability of a human expert in a narrow domain by reasoning over a body of encoded knowledge. It solves complex problems using knowledge and inference rules rather than conventional procedural code (e.g. MYCIN for medical diagnosis, DENDRAL for chemical analysis).

Architecture and Components

   User
    | (query)            (advice/explanation)
    v                          ^
 +------------------+   +-----------------+
 | User Interface   |   | Explanation     |
 +------------------+   | Facility        |
        |               +-----------------+
        v                       ^
 +------------------+           |
 | Inference Engine |-----------+
 +------------------+
     ^         ^
     |         |
 +---------+  +-----------------+
 | Knowledge|  | Working Memory  |
 |  Base    |  | (facts)         |
 +---------+  +-----------------+
     ^
     | (acquire knowledge)
 +------------------+
 | Knowledge Engineer / Expert |
 +------------------+

1. Knowledge Base – stores domain knowledge as facts and IF–THEN rules. It is the heart of the system.
2. Inference Engine – the reasoning component that applies rules to known facts to derive new conclusions, using forward chaining (data-driven) or backward chaining (goal-driven).
3. Working Memory – holds the current facts about the problem being solved.
4. User Interface – lets the user enter queries and receive answers in a natural way.
5. Explanation Facility – explains how a conclusion was reached and why a question is asked, building user trust.
6. Knowledge Acquisition Module – used by the knowledge engineer/expert to add and update knowledge.

Role of Inference Engine and Knowledge Base

• The Knowledge Base supplies what is known (rules + facts).
• The Inference Engine supplies how to use it — it matches rules against facts, resolves conflicts, and fires rules to infer new facts until a goal/solution is found. Separating these two allows the same engine to work over different knowledge bases.

Applications

• Medical diagnosis (MYCIN), financial loan/credit advising, fault diagnosis in machinery, chemical structure analysis (DENDRAL), weather forecasting, and agricultural advisory systems.

Forward chaining is a data-driven reasoning method. It starts from the known facts and repeatedly applies rules whose conditions (IF parts) are satisfied, adding the conclusions (THEN parts) as new facts, until the goal is derived or no more rules fire. It works bottom-up and is suited to situations where many facts are known and we want to find what conclusions follow (e.g. monitoring, planning).

Backward chaining is a goal-driven method. It starts from a hypothesis/goal and works backward, looking for rules whose conclusion matches the goal, then trying to prove the conditions of those rules as sub-goals, recursively, until they are grounded in known facts. It is suited to diagnosis-type problems (e.g. MYCIN) where we want to verify a specific goal.

Propositional logic deals with whole statements (propositions) that are either true or false, combined using connectives ($\land, \lor, \lnot, \rightarrow, \leftrightarrow$). It cannot look inside a statement or express relationships among objects.

Predicate (first-order) logic extends propositional logic with predicates, objects, variables, functions, and quantifiers ($\forall, \exists$), allowing it to express relationships and generalize over objects.

Example: The sentence "All men are mortal" cannot be captured in propositional logic but is written in predicate logic as $\forall x\,(Man(x) \rightarrow Mortal(x))$.

Semantic Network

A semantic network is a graphical knowledge-representation scheme in which knowledge is stored as a directed graph of nodes and labelled arcs:

• Nodes represent objects, concepts, or events.
• Arcs (edges) represent relationships between them, such as is-a (class membership / inheritance) and has-a (properties).

It supports inheritance: a property attached to a general class is automatically inherited by its sub-classes and instances, making reasoning efficient.

Example

        [Animal]
           ^ is-a
        [Bird] ----has----> [Wings]
           ^ is-a              
        [Sparrow]
           ^ is-a (instance)
        [Tweety] ----color----> [Brown]

From this network we infer that Tweety is a Sparrow, which is-a Bird, which is-an Animal, and (by inheritance) Tweety has Wings, even though that fact was only stored on the Bird node. This inheritance through is-a links is the main reasoning power of semantic networks.

Frame-Based Knowledge Representation

A frame is a data structure (proposed by Marvin Minsky) used to represent a stereotyped object, situation, or concept. It groups together all knowledge about an entity. A frame consists of:

• Slots – attributes/properties of the object.
• Fillers (facets) – the values of those slots, which may be specific values, default values, ranges, procedures (demons / if-needed, if-added), or pointers to other frames.

Frames are organized in a hierarchy with is-a / instance-of links, supporting inheritance of slot values from parent (generic) frames to child (specific) frames, plus the ability to override defaults.

Example

Frame: Bird
  is-a:        Animal
  can_fly:     yes        (default)
  has:         wings, feathers
  no_of_legs:  2

Frame: Penguin
  is-a:        Bird
  can_fly:     no         (overrides default)
  habitat:     Antarctica

Here Penguin inherits has: wings, feathers and no_of_legs: 2 from Bird, but overrides the default can_fly to no.

Advantages: organized, supports inheritance and defaults, attaches procedures (demons) to slots; close to object-oriented representation.

Activation Function

An activation function is a function $f(z)$ applied to the weighted sum $z = \sum_i w_i x_i + b$ of a neuron's inputs to produce its output. It decides whether and how strongly a neuron fires and, crucially, introduces non-linearity, enabling the network to learn complex, non-linear mappings (without it, a multi-layer network would collapse into a single linear function).

Two Common Activation Functions

1. Sigmoid: $\;f(z) = \dfrac{1}{1+e^{-z}}$, output range $(0,1)$ — smooth, used for probabilities.
2. ReLU (Rectified Linear Unit): $\;f(z) = \max(0, z)$ — fast, mitigates vanishing gradients, widely used in deep networks.

(Other examples: tanh, step/threshold, softmax.)

Supervised learning trains a model on labelled data, i.e. each training example has an input and a known correct output (target). The model learns a mapping from inputs to outputs and is used for classification and regression. Examples: spam detection, linear regression, SVM, decision trees.

Unsupervised learning uses unlabelled data; the model discovers hidden structure, patterns, or groupings on its own. It is used for clustering and dimensionality reduction. Examples: K-means clustering, hierarchical clustering, PCA.

Overfitting

Overfitting occurs when a machine-learning model learns the training data too well — including its noise and random fluctuations — so that it fits the training set very accurately but fails to generalize to new, unseen data. The model has low training error but high test/validation error.

It typically happens when the model is too complex (too many parameters) relative to the amount of training data, or when training runs for too long.

Symptom: large gap between high training accuracy and low test accuracy.

Remedies / techniques to reduce overfitting:

• Use more training data.
• Regularization (L1/L2 penalties), dropout in neural networks.
• Cross-validation and early stopping.
• Pruning (decision trees) and reducing model complexity.

(The opposite problem, where the model is too simple to capture the pattern, is called underfitting.)

Genetic Algorithm (GA)

A genetic algorithm is a search and optimization technique inspired by natural selection and genetics (Darwin's "survival of the fittest"). It maintains a population of candidate solutions (called chromosomes, usually encoded as bit strings) and evolves them over generations toward better solutions guided by a fitness function.

General cycle: Initialize population → evaluate fitness → select parents → apply crossover and mutation → form new generation → repeat until a stopping condition is met.

Basic Operators

1. Selection – chooses the fitter chromosomes to reproduce (e.g. roulette-wheel, tournament, rank selection). Higher fitness → higher chance of being selected.
2. Crossover (recombination) – combines two parent chromosomes to produce offspring by exchanging parts of their strings (e.g. single-point crossover):

   Parent1: 1011 | 001     Child1: 1011 | 110
   Parent2: 1100 | 110  →  Child2: 1100 | 001
   

3. Mutation – randomly flips one or more bits (genes) with a small probability to maintain diversity and avoid premature convergence to a local optimum:

   10110 → 10010 (bit flipped)
   

The Wumpus World Problem

The Wumpus World is a classic AI test-bed (from Russell & Norvig) used to demonstrate a knowledge-based agent reasoning under uncertainty and partial observability. It is typically a 4×4 grid of rooms.

Elements of the environment:

• The Wumpus — a monster that kills the agent if entered; it can be shot with the agent's single arrow.
• Pits — bottomless holes; falling in kills the agent.
• Gold — the goal; the agent must grab it and return to the start.
• The agent starts at square [1,1].

Percepts the agent receives (it cannot see the whole grid):

• Stench — in squares adjacent to the Wumpus.
• Breeze — in squares adjacent to a pit.
• Glitter — in the square containing the gold.
• Bump — when walking into a wall.
• Scream — when the Wumpus is killed by the arrow.

Goal: the agent must find and grab the gold and return safely, using logical inference (e.g. propositional logic) over its percepts to deduce safe squares — for example, "no breeze in [1,1] ⇒ no pit in [1,2] or [2,1], so they are safe."

It illustrates how an agent represents knowledge, makes inferences, and acts rationally in a partially observable, uncertain environment.