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

Fuzzy Logic

Fuzzy logic is a form of many-valued logic that deals with reasoning that is approximate rather than fixed and exact. Unlike classical (Boolean) logic where a proposition is either true (1) or false (0), fuzzy logic allows truth values to range continuously in the interval $[0, 1]$. It is used to model human reasoning and to handle vagueness and imprecision (e.g. "the water is warm").

Fuzzy Sets

In a classical (crisp) set, an element either belongs to the set or it does not. In a fuzzy set $A$ defined over a universe of discourse $X$, every element $x$ has a degree of membership $\mu_A(x) \in [0,1]$:

• $\mu_A(x) = 1$ : full membership
• $\mu_A(x) = 0$ : no membership
• $0 < \mu_A(x) < 1$ : partial membership

Example: For the set Tall of people, a person of height 5'8" might have membership $0.6$, while 6'2" has membership $0.95$.

Membership Functions

A membership function (MF) maps each element of $X$ to its membership degree. Common shapes:

• Triangular, Trapezoidal, Gaussian, Sigmoidal.

A triangular MF is defined as:

Structure of a Fuzzy Inference System (FIS)

A FIS maps crisp inputs to crisp outputs through four stages:

1. Fuzzification – Convert crisp inputs into fuzzy values using membership functions.
2. Rule Base (Knowledge Base) – A set of IF–THEN rules, e.g. IF temperature is high AND humidity is high THEN fan speed is fast.
3. Inference Engine – Applies fuzzy operators (min for AND, max for OR) to evaluate the rules and aggregate their fuzzy outputs (Mamdani / Sugeno methods).
4. Defuzzification – Convert the aggregated fuzzy output back into a crisp value, commonly by the centroid (center of gravity) method:

Example: Air-Conditioner Controller

• Input: room temperature (Cold, Warm, Hot). Output: cooling power (Low, Medium, High).
• Rule: IF temperature is Hot THEN cooling is High.
• If a temperature of $30^\circ C$ is Hot with $\mu = 0.7$ and Warm with $\mu = 0.3$, the inference engine fires the matching rules, aggregates the output fuzzy sets, and defuzzification yields a crisp cooling power (e.g. 75%).

This lets the controller respond smoothly instead of switching abruptly between ON/OFF states.

Constraint Satisfaction Problem (CSP)

A CSP is a problem defined by three components:

• Variables $X = \{X_1, X_2, \dots, X_n\}$
• Domains $D = \{D_1, \dots, D_n\}$ — the set of allowed values for each variable
• Constraints $C$ — restrictions on the values that combinations of variables may take simultaneously

A solution is a complete assignment of a value to every variable that satisfies all constraints. CSPs use a factored state representation, which lets general-purpose solvers exploit problem structure.

Map-Coloring Problem

Given a map of regions, assign one of $k$ colors to each region so that no two adjacent regions share the same color.

Using the classic Australia example with regions WA, NT, SA, Q, NSW, V, T and 3 colors {Red, Green, Blue}:

• Variables: WA, NT, SA, Q, NSW, V, T
• Domains: {Red, Green, Blue}
• Constraints: adjacent regions differ, e.g. $WA \neq NT$, $WA \neq SA$, $NT \neq SA$, $SA \neq Q$, etc.

Backtracking Search

A depth-first search that assigns one variable at a time and backtracks when a constraint is violated:

function BACKTRACK(assignment, csp):
    if assignment is complete: return assignment
    var = SELECT-UNASSIGNED-VARIABLE(csp)   # e.g. MRV heuristic
    for each value in ORDER-DOMAIN-VALUES(var):
        if value is consistent with assignment:
            add {var = value} to assignment
            result = BACKTRACK(assignment, csp)
            if result != failure: return result
            remove {var = value}   # backtrack
    return failure

Heuristics that improve it: MRV (choose variable with fewest legal values), degree heuristic, and least-constraining-value ordering.

Constraint Propagation (Forward Checking / AC-3)

Constraint propagation reduces domains by enforcing arc consistency before/while searching. An arc $X \to Y$ is consistent if for every value of $X$ there exists some value of $Y$ satisfying the constraint.

• Forward checking: when WA = Red is chosen, remove Red from the domains of its neighbors (NT, SA). This detects dead ends early.
• AC-3: repeatedly revises arcs; if any domain becomes empty, the branch fails immediately.

Solving the Map Together

1. Choose SA (MRV/degree) and assign SA = Red.
2. Forward checking removes Red from WA, NT, Q, NSW, V.
3. Assign WA = Green, propagate; NT = Blue; Q = Green; NSW = Blue; V = Green; T = Red (T is isolated).
4. All constraints satisfied → valid 3-coloring.

Combining backtracking with constraint propagation prunes large parts of the search tree, making CSP solving far more efficient than blind search.

Machine Learning

Machine Learning (ML) is a subfield of AI in which a system learns a model from data and improves its performance on a task with experience, rather than being explicitly programmed with fixed rules. Formally (Tom Mitchell): a program learns from experience $E$ with respect to task $T$ and performance measure $P$ if its performance on $T$, measured by $P$, improves with $E$.

Types of Machine Learning

• Supervised learning: trained on labeled examples; the model predicts the correct output for new inputs (e.g. predicting whether a tumor is benign/malignant).
• Unsupervised learning: no labels; the model finds patterns or groups (e.g. grouping customers by buying behaviour with K-Means).
• Reinforcement learning: an agent takes actions in an environment, receives rewards, and learns a policy that maximizes long-term reward (e.g. a robot learning to walk).

Perceptron Learning Rule

The perceptron is the simplest neural unit. It computes a weighted sum of inputs and applies a step activation:

The perceptron learning rule updates weights to reduce the error between the target $t$ and the output $y$:

where $\eta$ is the learning rate.

Algorithm:

1. Initialize weights and bias (often to 0 or small random values).
2. For each training example, compute output $y$.
3. Update weights using the rule above.
4. Repeat over all examples (epochs) until the error is zero (or minimal).

Convergence: The perceptron convergence theorem guarantees that if the data is linearly separable, the rule converges to a separating hyperplane in finite steps. It cannot solve non-linearly-separable problems such as XOR.

Supervised vs Unsupervised Learning

In short, supervised learning predicts known outputs from labeled data, while unsupervised learning finds natural groupings or structure in data that has no labels.

Overfitting

Overfitting occurs when a machine-learning model learns the training data too well — capturing not only the underlying pattern but also the noise and random fluctuations. As a result it achieves very low training error but high test/generalization error, i.e. it performs poorly on new, unseen data.

Symptoms: training accuracy is high while validation/test accuracy is low; a large gap between the two curves.

Causes:

• Model too complex (too many parameters/features) relative to the amount of data
• Too little training data
• Training for too many iterations (epochs)
• Noisy data

Remedies:

• Cross-validation to detect it early
• Regularization (L1/L2 penalty) to constrain weights
• Pruning (decision trees) / dropout (neural nets)
• Gathering more training data or data augmentation
• Early stopping 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 metaheuristic search and optimization technique inspired by Darwin's theory of natural selection and biological evolution. It maintains a population of candidate solutions (chromosomes), and evolves them over successive generations toward better solutions guided by a fitness function, applying the principle of survival of the fittest.

General cycle: Initialize population → Evaluate fitness → Selection → Crossover → Mutation → Replace → repeat until a termination criterion (good enough fitness or max generations) is met.

Basic Operators

1. Selection (Reproduction) – Chooses fitter individuals to act as parents for the next generation. Methods: roulette-wheel, tournament, and rank selection. Fitter chromosomes have a higher chance of being selected.

2. Crossover (Recombination) – Combines genetic material of two parents to produce offspring, exchanging segments of their chromosomes. Example (single-point crossover):

   • Parent1 = 1011|0010, Parent2 = 1100|1101
   • Children = 1011|1101, 1100|0010 Types: single-point, two-point, uniform crossover.

3. Mutation – Randomly flips one or more genes (bits) with a small probability to maintain genetic diversity and avoid premature convergence to a local optimum, e.g. 10110010 → 10110110.

(An additional commonly cited operator is Elitism / Replacement, which carries the best individuals unchanged into the next generation.)

The Wumpus World

The Wumpus World is a classic AI problem (from Russell & Norvig) used to illustrate knowledge representation and reasoning for a logical agent in a partially observable environment.

Environment: A $4 \times 4$ grid of rooms. It contains:

• A Wumpus (a monster) that kills the agent if entered; it can be shot with the agent's single arrow.
• One or more pits that kill the agent if entered.
• A pile of gold to be grabbed.
• The agent starts at square $[1,1]$ facing right.

Percepts (the agent senses 5 things):

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

Actions: Move Forward, Turn Left, Turn Right, Grab, Shoot, Climb.

Goal: Find and grab the gold, return to $[1,1]$, and climb out safely, while avoiding pits and the Wumpus. The agent maximizes its performance score (gold = +1000, death = −1000, each action = −1, using the arrow = −10).

Significance: The agent has no complete map; it must use logical inference on its percepts (e.g. breeze in [1,2] and [2,1] ⇒ pit likely in [2,2]) to deduce which squares are safe. It demonstrates how a knowledge-based agent builds and reasons over a knowledge base (using propositional/first-order logic) to act intelligently under uncertainty.

Depth-First Search (DFS) vs Best-First Search

In essence, DFS blindly dives deep using a stack, whereas best-first search uses domain knowledge (a heuristic) to choose the most promising node to expand next.

Goal of Unification

Unification is the process of finding a substitution that makes two logical expressions (predicates/terms) identical. Its goal is to make two atomic sentences syntactically the same by consistently replacing variables with terms.

The output is a Most General Unifier (MGU) — the substitution that is least restrictive (makes the fewest commitments) while still unifying the expressions.

Why it matters: Unification is the key step that enables inference rules such as resolution and generalized Modus Ponens to be applied in first-order (predicate) logic, allowing automated theorem proving and logic programming (e.g. Prolog).

Example:

• Unify $Knows(John, x)$ and $Knows(y, Mother(y))$
• MGU $\theta = \{\, y/John,\ x/Mother(John)\,\}$
• Applying $\theta$ to both gives $Knows(John, Mother(John))$.

A variable cannot be unified with a term containing that same variable (the occurs check), to avoid infinite structures.

Components of an Expert System

An expert system is an AI program that emulates the decision-making ability of a human expert in a specific domain. Its main components are:

1. Knowledge Base – Stores the domain knowledge: facts about the domain and a set of IF–THEN production rules (heuristics) obtained from human experts. It is the core of the system.

2. Inference Engine – The 'brain' that applies logical rules to the knowledge base to deduce new facts and reach conclusions. It uses reasoning strategies:

   • Forward chaining (data-driven): from known facts to conclusions.
   • Backward chaining (goal-driven): from a hypothesis back to supporting facts.

3. Knowledge Acquisition Module – The subsystem used to gather, organize, and update knowledge from human experts and other sources into the knowledge base.

4. User Interface – Allows a non-expert user to interact with the system: pose queries in a convenient form and receive advice/answers.

5. Explanation Facility – Explains how a conclusion was reached and why certain information is needed, increasing user trust and transparency.

(Some texts also list a Working Memory / Blackboard, which holds the current facts and intermediate results during a consultation.)

Example: MYCIN (diagnosing bacterial infections) and DENDRAL (chemical analysis).

Strong AI vs Weak AI

In short, weak AI performs a specific task by simulating intelligence, whereas strong AI would possess genuine, general, human-equivalent cognitive ability — which has not yet been realized.

The Turing Test

The Turing Test, proposed by Alan Turing in 1950 (in his paper Computing Machinery and Intelligence), is a test to determine whether a machine can exhibit intelligent behaviour indistinguishable from that of a human. Turing reframed the question "Can machines think?" into an operational Imitation Game.

Setup: A human interrogator communicates via text (a keyboard/screen, so appearance/voice give no clue) with two hidden parties — one a human and one a machine. The interrogator asks questions and must decide which respondent is the machine. If the interrogator cannot reliably tell the machine from the human, the machine is said to have passed the test and to display intelligent behaviour.

Capabilities a machine needs to pass: natural-language processing, knowledge representation, automated reasoning, and machine learning (the total Turing test adds computer vision and robotics).

Significance

• It provides an operational, behaviour-based definition of machine intelligence, sidestepping philosophical debate about what 'thinking' means.
• It set a benchmark/goal that has guided AI research for decades and identifies the core AI sub-fields needed to achieve it.
• It highlights the distinction between behaving intelligently and being conscious (later challenged by Searle's Chinese Room argument).
• It remains a cultural and historical landmark in AI, influencing how we evaluate conversational agents and chatbots today.