Artificial Neural Networks: Biological Analogy and Backpropagation

STEP 1 - EXTRACT (Given / Assumed Data)

The question requires us to assume inputs and weights, so the worked example below uses these values:

Inputs: $x_1 = 0.5$, $x_2 = 0.3$ Target: $t = 1.0$

Learning rate: $\alpha = 0.5$ Activation: Sigmoid $g(x) = \dfrac{1}{1+e^{-x}}$, derivative $g'(x) = g(x)(1-g(x))$ Biases: $0$

Initial weights:

Part 1: Biological vs Artificial Neural Network Mapping

Summary: dendrites $\to$ inputs, synapses $\to$ weights, soma $\to$ summation + activation, axon $\to$ output. Learning in ANN = adjusting synaptic weights.

Part 2: Network Architecture

A 2-2-1 multilayer network:

 x1 ─w13─┐        ┌─w35─┐
         ├──> h1 ─┤     │
 x2 ─w23─┘        │     ├──> o1 ──> y
                  │     │
 x1 ─w14─┐        │     │
         ├──> h2 ─┴─w45─┘
 x2 ─w24─┘

Part 3: Single Iteration of Backpropagation

Step 1: Forward pass - hidden layer

$$net_{h1} = 0.4(0.5) + 0.2(0.3) = 0.20 + 0.06 = 0.26$$ $$h_1 = g(0.26) = \frac{1}{1+e^{-0.26}} = \frac{1}{1.7711} = 0.5646$$

$$net_{h2} = 0.3(0.5) + 0.5(0.3) = 0.15 + 0.15 = 0.30$$ $$h_2 = g(0.30) = \frac{1}{1+e^{-0.30}} = \frac{1}{1.7408} = 0.5744$$

Step 2: Forward pass - output layer

$$net_{o1} = 0.6(0.5646) + 0.7(0.5744) = 0.3388 + 0.4021 = 0.7409$$ $$y = g(0.7409) = \frac{1}{1+e^{-0.7409}} = \frac{1}{1.4767} = 0.6772$$

Step 3: Output error and delta

$$\delta_{o1} = (t - y)\cdot y(1-y) = (1.0 - 0.6772)(0.6772)(1-0.6772)$$ $$= 0.3228 \times 0.6772 \times 0.3228 = 0.07057$$

Step 4: Hidden layer deltas

$$\delta_{h1} = h_1(1-h_1),(w_{35},\delta_{o1})$$ $$= 0.5646(0.4354)(0.6 \times 0.07057) = 0.2458 \times 0.04234 = 0.01041$$

$$\delta_{h2} = h_2(1-h_2),(w_{45},\delta_{o1})$$ $$= 0.5744(0.4256)(0.7 \times 0.07057) = 0.2445 \times 0.04940 = 0.01208$$

Step 5: Weight updates $;w^{new} = w^{old} + \alpha,\delta,(\text{input to that weight})$

Output layer: $$w_{35}^{new} = 0.6 + 0.5(0.07057)(0.5646) = 0.6 + 0.01992 = 0.6199$$ $$w_{45}^{new} = 0.7 + 0.5(0.07057)(0.5744) = 0.7 + 0.02027 = 0.7203$$

Hidden layer: $$w_{13}^{new} = 0.4 + 0.5(0.01041)(0.5) = 0.4 + 0.00260 = 0.4026$$ $$w_{23}^{new} = 0.2 + 0.5(0.01041)(0.3) = 0.2 + 0.00156 = 0.2016$$ $$w_{14}^{new} = 0.3 + 0.5(0.01208)(0.5) = 0.3 + 0.00302 = 0.3030$$ $$w_{24}^{new} = 0.5 + 0.5(0.01208)(0.3) = 0.5 + 0.00181 = 0.5018$$

Result of one iteration

Output moved from $y = 0.6772$ toward target $t = 1.0$; repeating iterations reduces error.

Common mistake: treating $\delta = t - y = 0.3229$ as the output delta. The sigmoid derivative must be included, giving $\delta_{o1} = (t-y),y(1-y) = 0.0706$, and that is the value used in the weight updates. The forward pass gives $h_1 \approx 0.565$, $h_2 \approx 0.574$ and $y \approx 0.677$.

Skolem Constant, Skolemization, and FOPL Representation

1. Skolem Constant

A Skolem constant is a special constant introduced during the process of Skolemization to eliminate existential quantifiers from a First Order Predicate Logic (FOPL) formula. When an existential quantifier appears in a formula without any enclosing universal quantifier, the existentially quantified variable is replaced by a unique new constant (called a Skolem constant) that represents the specific (but unnamed) individual whose existence is asserted.

Example:

• Formula: ∃x P(x)
• After Skolemization: P(a) where a is a Skolem constant.

If the existential quantifier is within the scope of a universal quantifier, the existential variable is replaced by a Skolem function (not a constant) of the universally quantified variables.

Example:

• Formula: ∀x ∃y Loves(x, y)
• After Skolemization: ∀x Loves(x, f(x)) where f(x) is a Skolem function.

2. Skolemization During Resolution

Skolemization is the process of removing existential quantifiers from a FOPL formula to prepare it for resolution. Resolution works on clausal form (CNF), and existential quantifiers must be eliminated before conversion to clause form.

Steps of Skolemization (as part of full conversion to clause form):

Rules of Skolemization:

• Case 1: If ∃x appears outside the scope of any universal quantifier, replace x with a Skolem constant (e.g., a, b, c).

  ∃x Movie(x) becomes Movie(SK1) where SK1 is a Skolem constant.

• Case 2: If ∃x appears within the scope of universal quantifiers ∀y1, ∀y2, ..., replace x with a Skolem function of those variables.

  ∀x ∃y HasScript(x, y) becomes ∀x HasScript(x, f(x)) where f(x) is a Skolem function.

3. Representation of Statements into FOPL

Predicates Used:

• Movie(x) : x is a movie
• Hit(x) : x is a hit
• GoodScript(x) : x has a good script
• Sentimental(x) : x is sentimental
• Comedy(x) : x is a comedy

Statement 1: "All movies are not hit."

Every x, if x is a movie, then x is not a hit.

$$\forall x ; Movie(x) \Rightarrow \neg Hit(x)$$

Statement 2: "Sarangi is a movie."

Sarangi is a specific individual (constant).

$$Movie(Sarangi)$$

Statement 3: "All movies which have good script are hit."

Every x, if x is a movie AND x has a good script, then x is a hit.

$$\forall x ; [Movie(x) \wedge GoodScript(x)] \Rightarrow Hit(x)$$

Statement 4: "Sarangi has a good script but Sarangi is sentimental."

Conjunction of two facts about the constant Sarangi.

$$GoodScript(Sarangi) \wedge Sentimental(Sarangi)$$

Statement 5: "There is a movie which is comedy."

There exists some x such that x is a movie and x is a comedy.

$$\exists x ; [Movie(x) \wedge Comedy(x)]$$

After Skolemization (since ∃x has no enclosing universal quantifier, replace x with Skolem constant SK1):

$$Movie(SK1) \wedge Comedy(SK1)$$

Summary Table

Note: Statements 1 and 3 appear contradictory (all movies are not hit vs. movies with good script are hit). This is intentional in the problem, likely to test resolution-based contradiction detection. In resolution, we would derive a contradiction from Movie(Sarangi), GoodScript(Sarangi), Statement 1, and Statement 3.

Informed vs Uninformed Search, Hill Climbing, and Incompleteness

STEP 1 - EXTRACT: Given Data

This is a conceptual and design question. There are no fixed numeric inputs provided; the student must construct a state space with heuristics. The state space used below is:

Working state space (Part 3):

Modified state space (Part 4):

No data is missing since the values are self-created and internally consistent.

STEP 2 - SOLVE

Part 1: Informed vs Uninformed Search

The heuristic function is: $$h(n) = \text{estimated cost of the cheapest path from node } n \text{ to a goal}$$

Informed search leverages $h(n)$ to prioritize promising nodes, which uninformed search cannot do.

Part 2: Hill Climbing Concept

Hill climbing is a local, informed search that:

• keeps only the current state (no frontier, no memory),
• always moves to the best neighbor (here, lowest $h$ toward goal),
• halts when no neighbor improves on the current node.

Part 3: State Space Where Hill Climbing Succeeds

        A (10)
       /   \
    B(7)    C(8)
    /  \      \
  D(4) E(5)   F(6)
   |
  G(0)  <-- GOAL

Execution (choose neighbor with lowest $h$):

Solution path: $A \to B \to D \to G$

Hill climbing succeeds because the heuristic decreases monotonically along the correct path.

Part 4: Modified State Space Where Hill Climbing Fails

We change $D$'s value to $5$ and add a misleading branch $E \to X$ with $h(E)=3$, $h(X)=4$, so the greedy choice leads into a local minimum.

        A (10)
       /   \
    B(7)    C(8)
    /  \      \
  D(5) E(3)   F(6)
   |     \
  G(0)   X(4)  <-- dead-end trap

Execution:

Path followed: $A \to B \to E$ → stuck at $E$ (local minimum).

The actual goal lies on $A \to B \to D \to G$, but at step 2 the greedy heuristic picked $E$ (h=3) over $D$ (h=5). At $E$, the only neighbor $X$ (h=4) is worse, so hill climbing terminates without reaching $G$.

Why incomplete: Hill climbing has no backtracking and no memory, so once it commits to a locally attractive but misleading node it cannot recover. This illustrates the classic failure modes:

1. Local minimum/maximum (shown above),
2. Plateau (all neighbors equal),
3. Ridge (progress only via non-improving sideways moves).

Hence hill climbing is not complete: it can fail to find an existing goal.

Conclusion: Informed search uses $h(n)$ to guide exploration (unlike blind uninformed search). Hill climbing exploits $h(n)$ greedily and works when the heuristic slopes toward the goal, but because it lacks backtracking it becomes incomplete at local minima, plateaus, and ridges.

What is Intelligence? Foundations of AI

Intelligence

Intelligence is the capacity to learn and solve problems. More specifically, it is the ability to:

• Solve novel problems
• Act rationally
• Act like humans

In the context of computer science, intelligence refers to designing computer systems that exhibit characteristics we associate with intelligent human behaviour, including reasoning, planning, problem solving, knowledge representation, learning, and natural language processing.

Artificial Intelligence (AI)

AI is the field concerned with giving machines human-like capabilities to perform tasks normally associated with reasoning and intelligence. There are four main approaches to defining AI:

a) Thinking Humanly (Cognitive Modeling Approach)

This approach focuses on making computers think like humans. To determine how humans think, three methods are used:

• Introspection - catching our own thoughts as they go by
• Psychological experiments - observing a person in action
• Brain imaging - observing the brain in action

"The automation of activities that we associate with human thinking, such as decision-making, problem solving, learning..." - Bellman, 1978

b) Acting Humanly (Turing Test Approach)

A computer is called intelligent if it passes the Turing Test, where a human interrogator cannot distinguish written responses from a computer versus a human. The computer must possess:

• Natural language processing - to communicate successfully
• Knowledge representation - to store what it knows
• Automated reasoning - to answer questions and draw conclusions
• Machine learning - to adapt to new circumstances

"The art of creating machines that perform functions that require intelligence when performed by people." - Kurzweil, 1990

c) Thinking Rationally

Focuses on using computational methods to model mental faculties and reasoning.

"The study of computations that make it possible to perceive, reason and act." - Winston, 1992

d) Acting Rationally

Focuses on designing intelligent agents that behave rationally in their environment.

"Computational Intelligence is the study of design of intelligent agents." - Poole et al., 1998

Foundations of AI

AI is built upon contributions from several disciplines:

These foundations together provide the theoretical and practical basis upon which AI systems are designed, making AI a truly interdisciplinary field.

Reinforcement Learning and ANN Neuron for OR Gate

STEP 1 - EXTRACT: Given Data

This is a conceptual + design question. The relevant "data" is:

• Task 1: Define reinforcement learning.
• Task 2: Configure a single ANN neuron (perceptron) to implement the OR logic function.
• OR gate truth table (standard, not given but implied):

No numeric parameters are supplied; the weights, bias, and threshold must be chosen by design.

STEP 2 - SOLVE

Part 1: Reinforcement Learning

Reinforcement Learning (RL) is a machine learning paradigm in which an agent learns to make decisions by interacting with an environment through trial and error. The agent performs actions, observes the resulting state, and receives a reward (positive) or penalty (negative) as feedback. Its goal is to learn a policy (a mapping from states to actions) that maximizes the cumulative reward over time.

Key elements:

There is no labelled training data as in supervised learning; instead learning is guided by the reward signal.

Types:

• Positive reinforcement - a favourable outcome strengthens and increases the frequency of a behaviour.
• Negative reinforcement - removing an unfavourable condition strengthens a behaviour.

Examples: game-playing agents (chess, Go), robot navigation, recommendation systems.

Part 2: ANN Neuron (Perceptron) for OR Gate

A single neuron computes a weighted sum plus bias, then applies a step activation function:

$$ \text{Net} = w_1 x_1 + w_2 x_2 + b $$

$$ y = \begin{cases} 1 & \text{if } \text{Net} \ge 0 \ 0 & \text{if } \text{Net} < 0 \end{cases} $$

Chosen parameters:

$$ w_1 = 1,\qquad w_2 = 1,\qquad b = -0.5 $$

This is equivalent to using weights $w_1 = w_2 = 1$ with a threshold $\theta = 0.5$ (since $\text{Net} \ge 0 \Leftrightarrow w_1x_1 + w_2x_2 \ge 0.5$).

Verification:

All four outputs match the OR truth table.

Neuron diagram:

        w1 = 1
x1 ────────────┐
               ├──►[ Σ + b ]──► Step ──► y
x2 ────────────┘   (b = -0.5)
        w2 = 1

Result: With $w_1 = w_2 = 1$ and bias $b = -0.5$ (threshold $\theta = 0.5$), a single perceptron correctly realizes the OR gate.

Common mistake: stating bias $b = 0$ together with threshold $\theta = 0.5$. These are inconsistent: $b = 0$ corresponds to $\theta = 0$, and the bias matching $\theta = 0.5$ is $b = -0.5$. Applying the $\theta = 0.5$ rule in the verification table still gives the correct logical behaviour and weights.

Uniform Cost Search (UCS) in State Space

Given Data

This is a conceptual/descriptive question. No numeric matrices, burst times, or reference strings are provided. The example graph and edge costs are constructed for illustration (as the question requires "an example").

Definition

Uniform Cost Search (UCS) is an uninformed (blind) search strategy that expands the node with the lowest cumulative path cost $g(n)$ from the start node. It is a special case of Best-First Search using the evaluation function:

$$f(n) = g(n)$$

where $g(n)$ = total cost of the path from the start state to node $n$. When all step costs are equal, UCS reduces to Breadth-First Search.

How UCS Searches the Goal

1. Insert the start node into a priority queue ordered by path cost (minimum first), with cost $0$.
2. Remove the node with the least path cost.
3. Goal test at expansion (when popped, not when generated) to guarantee optimality.
4. Generate successors; for each, compute $g(\text{child}) = g(\text{parent}) + \text{step cost}$ and insert into the priority queue.
5. If a cheaper path to an already-seen node is found, update it.
6. Repeat until the goal is popped or the queue is empty.

Illustrated Example

Consider a weighted graph with start $S$ and goal $G$:

Edge costs:

• $S \to A = 1$
• $S \to B = 4$
• $A \to B = 2$
• $A \to G = 5$
• $B \to G = 2$

Step-by-Step Trace

Optimal Path: $S \to A \to B \to G$ with total cost $= 1 + 2 + 2 = \mathbf{5}$

The alternative $S \to A \to G$ costs $6$, so UCS correctly returns the cheaper path.

Check the path, not just the cost: with $S \to A = 1$ and $A \to B = 2$, node $B$ is reached at cost $3$, so the optimal path is $S \to A \to B \to G$ rather than $S \to B \to G$. The final cost (5) is identical either way.

Performance Measures

where $C^{*}$ = cost of optimal solution, $\varepsilon$ = minimum step cost, $b$ = branching factor.

Key Points

• Uses a priority queue ordered by $g(n)$.
• Optimal and complete for positive step costs.
• Uninformed counterpart of A* (A* adds heuristic: $f(n)=g(n)+h(n)$).
• Goal tested at expansion, ensuring no cheaper path is missed.

Reinforcement Learning and ANN Neuron for OR Gate

Given Data

• Task 1: Define reinforcement learning (conceptual).
• Task 2: Configure a single ANN neuron (perceptron) to simulate the OR gate.
• OR gate truth table (standard, boolean logic):

No numeric parameters are supplied, so weights, bias, and threshold are to be designed.

Part 1: Reinforcement Learning

Reinforcement Learning (RL) is a machine learning paradigm in which an agent learns to make decisions by interacting with an environment. The agent performs actions, observes the resulting state, and receives feedback in the form of a reward (for good actions) or a penalty/punishment (for bad actions). The goal of the agent is to learn a policy (a mapping from states to actions) that maximizes the cumulative reward over time.

Unlike supervised learning, there is no labelled dataset; the agent learns purely by trial and error guided by reward signals.

Key elements:

Types of reinforcement:

• Positive reinforcement: rewarding desirable behaviour so it occurs more often.
• Negative reinforcement: removing an unpleasant condition to strengthen desirable behaviour.

Examples: game-playing agents (Chess, Go), robot navigation, recommendation systems.

Part 2: ANN Neuron (Perceptron) for OR Gate

A single neuron computes:

$$y = f!\left(\sum_i w_i x_i + b\right) = f(w_1 x_1 + w_2 x_2 + b)$$

Using a step activation function with threshold $\theta$:

$$f(net) = \begin{cases} 1 & \text{if } net \geq \theta \ 0 & \text{otherwise} \end{cases}$$

Chosen parameters

• $w_1 = 1$
• $w_2 = 1$
• Threshold $\theta = 1$ (equivalently bias $b = -1$ with firing condition $net \geq 0$)

Verification against truth table

Case 1: $x_1=0,\ x_2=0$ $$net = (1)(0)+(1)(0) = 0 < 1 \Rightarrow y = 0\ \checkmark$$

Case 2: $x_1=0,\ x_2=1$ $$net = (1)(0)+(1)(1) = 1 \geq 1 \Rightarrow y = 1\ \checkmark$$

Case 3: $x_1=1,\ x_2=0$ $$net = (1)(1)+(1)(0) = 1 \geq 1 \Rightarrow y = 1\ \checkmark$$

Case 4: $x_1=1,\ x_2=1$ $$net = (1)(1)+(1)(1) = 2 \geq 1 \Rightarrow y = 1\ \checkmark$$

All four outputs match the OR gate truth table.

Neuron diagram

x1 ---(w1=1)---\
                (Σ) --> net --> [Step, θ=1] --> y
x2 ---(w2=1)---/

Conclusion

A single perceptron with $w_1 = 1$, $w_2 = 1$, and threshold $\theta = 1$ (bias $b = -1$) correctly simulates the OR gate.

Robotics and Machine Vision in Robotics

What is Robotics?

Robotics is a branch of Artificial Intelligence that deals with the design, construction, operation, and application of robots. A robot is an intelligent agent that perceives its environment through sensors and performs physical actions in the real world through actuators (motors, arms, wheels, etc.).

Robotics combines multiple AI disciplines to create machines that can:

• Perceive the physical world
• Make decisions based on perception
• Perform physical tasks autonomously or semi-autonomously

Key characteristics of a robotic system:

• Sensors - to perceive the environment (cameras, infrared, ultrasonic)
• Actuators - to perform physical actions
• Controller/Processor - to process information and make decisions
• Knowledge Base - to store learned information about the environment

Machine Vision in Robotics

Machine Vision (also called Computer Vision) is the ability of a robot to interpret and understand visual information from the real world, similar to how humans use their eyes and brain together.

How Machine Vision is Used in Robotics:

1. Object Recognition and Detection

• The robot uses cameras to capture images of its surroundings.
• Machine vision algorithms process these images to identify and classify objects.
• This allows the robot to distinguish between different objects, obstacles, or targets in its environment.

2. Navigation and Path Planning

• Machine vision helps robots understand their spatial environment.
• The robot uses visual input to map surroundings, detect obstacles, and plan a safe path to reach its goal.
• This connects directly to search methods in AI, where the robot determines the best sequence of actions to reach a goal state.

3. Manipulation and Grasping

• Robots use machine vision to locate objects precisely in 3D space.
• This enables robotic arms to pick, place, and manipulate objects accurately in manufacturing or surgery.

4. Quality Inspection (Industrial Robots)

• In manufacturing, robots use machine vision to inspect products for defects.
• The system compares captured images against a standard model and identifies deviations.

5. Facial and Gesture Recognition

• Robots can recognize human faces and interpret gestures using machine vision.
• This enables natural human-robot interaction.

6. Learning from Visual Input (Machine Learning Integration)

• Machine vision is combined with machine learning (supervised/reinforcement learning) so robots can improve their visual recognition over time.
• For example, using supervised learning, a robot is trained with labelled images so it can classify new objects it encounters.
• Using reinforcement learning, a robot receives rewards when it correctly identifies and handles an object, improving its performance over time.

Summary Table

In conclusion, robotics integrates AI techniques such as knowledge representation, machine learning, automated reasoning, and machine vision to build intelligent physical agents. Machine vision acts as the "eyes" of the robot, enabling it to perceive, understand, and interact with the physical world effectively.

Environment Types for Given Agents

Background

Environments are classified along several dimensions:

• Deterministic vs Stochastic
• Dynamic vs Static
• Observable vs Semi-Observable

a. Mission Game with Fixed 6 States Having Two Players

This is a game-playing scenario with two players competing against each other.

Conclusion: This environment is Fully Observable, Deterministic, Static, and Multi-agent (Competitive).

b. Tesla Driverless Robovan Where Road Conditions Are Changing

This is a self-driving vehicle operating in a real-world road environment.

Conclusion: This environment is Semi-Observable, Stochastic, and Dynamic -- the most complex type of environment for an agent to operate in.

c. Game Result Predicting Agent Where Current Prediction State Is Independent of Previous State

This agent predicts game results, and each prediction is made independently without considering past states.

Conclusion: This environment is Stochastic, Static, and Memoryless (Markov-type), where each prediction is made independently based only on the current state.

Summary Table