Artificial Intelligence

Answer:

• Admissible Heuristic: A heuristic function $h(n)$ is admissible if it never overestimates the true cost to reach the nearest goal node from node $n$, i.e., $h(n) \le h^*(n)$ for all $n$, where $h^*(n)$ is the true optimal cost.
• Consistent (Monotonic) Heuristic: A heuristic $h(n)$ is consistent if, for every node $n$ and every successor $n'$ generated by action $a$ with step cost $c(n, a, n')$, it satisfies the triangle inequality:

  Swipe to see the full formula↔

  $$h(n) \le c(n, a, n') + h(n')$$
  Consistency guarantees that once a node is expanded in graph search, the shortest path to it has already been discovered.

Answer: Turing Test (Alan Turing, 1950): An empirical operational test of machine intelligence based on the "Imitation Game". A human interrogator communicates via text terminal with two unseen respondents (one human, one computer).

• Operationalization: If the interrogator cannot reliably distinguish the computer from the human after a specified duration of questioning, the machine is deemed to possess human-level conversational intelligence.

Answer:

• Forward Chaining (Data-Driven / Bottom-Up): Starts with known facts in working memory and applies inference rules (Modus Ponens) iteratively to deduce new facts until a target goal or hypothesis is proven.
• Backward Chaining (Goal-Driven / Top-Down): Starts with a goal or query hypothesis and searches backwards through rules to determine what supporting premise facts must be true to validate the goal (e.g., medical diagnosis, Prolog execution).

Answer: Role of Activation Function: Introduces non-linearity into the neural network. Without non-linear activation functions, a multi-layer neural network collapses mathematically into a single linear regression transformation ($W_2(W_1 x + b_1) + b_2 = W' x + b'$), unable to learn complex non-linear decision boundaries.

• Examples:
  1. ReLU (Rectified Linear Unit): $f(x) = \max(0, x)$
  2. Sigmoid: $\sigma(x) = \frac{1}{1 + e^{-x}}$

Answer:

• Supervised Learning: The model is trained on labeled data pairs $(x_i, y_i)$, learning a mapping function from input features to known ground-truth targets (e.g., Support Vector Machines (SVM) for loan default classification).
• Unsupervised Learning: The model is provided unlabeled inputs $\{x_i\}$ without predefined target classes, seeking to uncover latent structures, natural clusters, or lower-dimensional representations (e.g., $k$-Means Clustering for customer market segmentation).

Informed State-Space Search: A* Algorithm, Optimality Proof, and Python Implementation

1. Evaluation Function and Mechanics

A* search combines the uniform-cost search (Dijkstra) with greedy best-first search using the evaluation function:

• $g(n)$: Exact path cost accumulated from the initial start node $s$ to current node $n$.
• $h(n)$: Estimated heuristic cost from current node $n$ to the nearest goal state.
• $f(n)$: Estimated total cost of the cheapest solution path passing through node $n$.

2. Mathematical Proof of A* Optimality (Tree Search with Admissible $h$)

Let $G$ be an optimal goal state with true optimal path cost $C^*$. Suppose for contradiction that A* terminates by selecting a suboptimal goal state $G_2$ with path cost $f(G_2) = g(G_2) = C_2 > C^*$.

1. Because $G_2$ is a goal node, by definition $h(G_2) = 0$, so $f(G_2) = g(G_2) = C_2$.
2. Since an optimal path to $G$ exists, consider some unexpanded frontier node $n$ lying along the optimal path to $G$.
3. By definition of $f(n)$:

   Swipe to see the full formula↔

   $$f(n) = g(n) + h(n)$$
4. Because $h$ is admissible ($h(n) \le h^*(n)$):

   Swipe to see the full formula↔

   $$f(n) \le g(n) + h^*(n) = C^*$$
5. Combining inequalities:

   Swipe to see the full formula↔

   $$f(n) \le C^* < C_2 = f(G_2) \implies f(n) < f(G_2)$$
6. Since A* always extracts the frontier node with the minimum $f$-value from its priority queue, it will always expand node $n$ before $G_2$.
7. Therefore, A* can never expand the suboptimal goal $G_2$ while an optimal path frontier exists. Hence, A* is guaranteed to find an optimal path.

3. Complete Working Python Implementation of A*

import heapq
from typing import Dict, List, Tuple, Optional

def a_star_search(
    graph: Dict[str, List[Tuple[str, float]]],
    heuristics: Dict[str, float],
    start: str,
    goal: str
) -> Tuple[Optional[List[str]], float]:
    # Priority queue stores tuples: (f_score, current_node, path, g_score)
    open_set = [(heuristics[start], start, [start], 0.0)]
    visited_costs = {}

    while open_set:
        f_val, current, path, g_val = heapq.heappop(open_set)

        if current == goal:
            return path, g_val

        # If we already found a cheaper path to current node, skip
        if current in visited_costs and visited_costs[current] <= g_val:
            continue
        visited_costs[current] = g_val

        for neighbor, edge_weight in graph.get(current, []):
            new_g = g_val + edge_weight
            if neighbor not in visited_costs or new_g < visited_costs[neighbor]:
                new_f = new_g + heuristics.get(neighbor, 0.0)
                heapq.heappush(open_set, (new_f, neighbor, path + [neighbor], new_g))

    return None, float("inf")

# Demonstration Graph: Route from Kathmandu to Pokhara via intermediate waypoints
if __name__ == "__main__":
    nepal_routes = {
        "Kathmandu": [("Naubise", 26.0)],
        "Naubise": [("Kathmandu", 26.0), ("Galchhi", 22.0), ("Daman", 50.0)],
        "Galchhi": [("Naubise", 22.0), ("Mugling", 62.0)],
        "Daman": [("Naubise", 50.0), ("Hetauda", 55.0)],
        "Mugling": [("Galchhi", 62.0), ("Pokhara", 88.0), ("Narayangarh", 36.0)],
        "Pokhara": [("Mugling", 88.0)],
        "Hetauda": [("Daman", 55.0)],
        "Narayangarh": [("Mugling", 36.0)]
    }

    # Straight-line Euclidean distance heuristic to Pokhara
    heuristic_to_pokhara = {
        "Kathmandu": 140.0,
        "Naubise": 115.0,
        "Galchhi": 95.0,
        "Daman": 120.0,
        "Mugling": 70.0,
        "Narayangarh": 90.0,
        "Hetauda": 150.0,
        "Pokhara": 0.0
    }

    path, total_km = a_star_search(nepal_routes, heuristic_to_pokhara, "Kathmandu", "Pokhara")
    print("Optimal A* Route:", " -> ".join(path))
    print(f"Total Road Distance: {total_km} km")

Adversarial Search: Minimax Algorithm and Alpha-Beta Pruning

1. The Minimax Decision Rule

In a two-player, zero-sum, perfect-information game (e.g., Chess, Tic-Tac-Toe):

• MAX: Aims to choose moves maximizing the utility value:

  Swipe to see the full formula↔

  $$\text{Minimax}(s) = \max_{a \in \text{Actions}(s)} \text{Minimax}(\text{Result}(s, a))$$
• MIN: Aims to choose moves minimizing the utility value:

  Swipe to see the full formula↔

  $$\text{Minimax}(s) = \min_{a \in \text{Actions}(s)} \text{Minimax}(\text{Result}(s, a))$$
• Computational Complexity: For branching factor $b$ and search depth $m$, time complexity is $O(b^m)$ and space complexity is $O(bm)$.

2. Alpha-Beta ($\alpha$-$\beta$) Pruning Optimization

Alpha-Beta pruning removes subtrees that cannot influence the final decision without affecting the optimal Minimax outcome.

• $\alpha$ (Alpha): Best (highest-value) choice found so far along path for MAX (initialized to $-\infty$).
• $\beta$ (Beta): Best (lowest-value) choice found so far along path for MIN (initialized to $+\infty$).
• Pruning Rule: Prune remaining children of node $n$ if:

  Swipe to see the full formula↔

  $$\alpha \ge \beta$$

3. Game Tree Trace (Depth 3)

Consider root MAX node $A$, children MIN nodes $B$ and $C$, and leaf terminal nodes:

                  [A] (MAX) --> Value = 6
                 /         \
          [B] (MIN)       [C] (MIN)
           /     \           /     \
         [D]     [E]       [F]     [G] (Pruned!)
        /   \   /   \     /   \
       3     5 6     9   2    (beta <= alpha prune!)

Step-by-Step Pruning Walkthrough:

1. At Node $D$ (leaves 3, 5): MIN chooses $\min(3, 5) = 3$. Returns 3 to $B$.
2. At Node $B$: $\beta = 3$.
3. At Node $E$ (leaves 6, 9): MIN chooses $\min(6, 9) = 6$.
4. At Node $B$: $\min(3, 6) = 3$. Returns 3 to Root $A$.
5. At Root $A$: $\alpha = \max(-\infty, 3) = 3$. Root will achieve at least 3.
6. Search enters right subtree at $C$ (MIN, $\alpha=3, \beta=+\infty$).
7. At Node $F$: Evaluates first child = 2.
8. At Node $C$: $\beta = \min(+\infty, 2) = 2$.
9. Pruning Condition Checked at $C$:

   Swipe to see the full formula↔

   $$\alpha \ge \beta \implies 3 \ge 2 \quad (\text{TRUE!})$$
   Node $G$ and all remaining branches beneath $C$ are pruned immediately because MIN at $C$ can force an outcome $\le 2$, which Root MAX will never choose over 3.
10. Final Decision: Root $A$ chooses left branch $B$ with value 3.

4. Time Complexity Reduction

• Standard Minimax: $O(b^m)$
• Optimal Alpha-Beta Pruning: $O(b^{m/2})$
• Impact: Effectively doubles the searchable search depth in the same computational time limit.

Knowledge Representation, First-Order Logic, and Resolution Refutation

1. Propositional Logic (PL) vs. First-Order Predicate Logic (FOPL)

2. Conversion to Conjunctive Normal Form (CNF)

A formula is in CNF if it is a conjunction ($\wedge$) of clauses, where each clause is a disjunction ($\vee$) of literals:

1. Eliminate Implications: Replace $\alpha \to \beta$ with $\neg \alpha \vee \beta$.
2. Move Negations Inward (De Morgan’s Laws):
   • $\neg (\alpha \wedge \beta) \equiv \neg \alpha \vee \neg \beta$
   • $\neg (\alpha \vee \beta) \equiv \neg \alpha \wedge \neg \beta$
   • $\neg (\forall x \, P(x)) \equiv \exists x \, \neg P(x)$
3. Standardize Variables: Rename variables so each quantifier binds a unique variable name.
4. Skolemization: Replace existentially quantified variables with Skolem constants or functions.
5. Drop Universal Quantifiers: Assume all remaining variables are universally quantified.
6. Distribute $\vee$ over $\wedge$: Transform $(\alpha \wedge \beta) \vee \gamma$ into $(\alpha \vee \gamma) \wedge (\beta \vee \gamma)$.

3. Theorem Proving by Resolution Refutation

Problem Statement:

• Premise 1: "All software engineers write code." $\forall x (\text{Engineer}(x) \to \text{WritesCode}(x))$
• Premise 2: "Bibek is a software engineer." $\text{Engineer}(\text{Bibek})$
• Query: Prove "Bibek writes code." $\text{WritesCode}(\text{Bibek})$

Step 1: Convert Knowledge Base to CNF Clauses

1. $\neg \text{Engineer}(x) \vee \text{WritesCode}(x)$ (Clause 1)
2. $\text{Engineer}(\text{Bibek})$ (Clause 2)

Step 2: Negate Query and Add to Clause Set

• Negated Goal: $\neg \text{WritesCode}(\text{Bibek})$ (Clause 3)

Step 3: Resolution Graph (Deriving the Empty Clause $\square$)

Clause 1: ~Engineer(x) v WritesCode(x)      Clause 2: Engineer(Bibek)
                   \                           /
                    \   Unification {x/Bibek} /
                     v                       v
               Clause 4: WritesCode(Bibek)        Clause 3: ~WritesCode(Bibek)
                                  \                  /
                                   \                /
                                    v              v
                                  Clause 5: [] (Empty Clause / Contradiction!)

• Derivation of the empty clause $\square$ confirms that the negated goal is unsatisfiable. Hence, the original query $\text{WritesCode}(\text{Bibek})$ is mathematically proven.

Artificial Neural Networks: Architecture, Mathematical Backpropagation, and Code

1. Biological Neuron vs. Artificial Perceptron

• Dendrites $\approx$ Input vector $x_i$: Receive chemical signals from neighboring neurons.
• Synaptic Strengths $\approx$ Weights $w_i$: Scale the influence of incoming inputs.
• Cell Body (Soma) $\approx$ Weighted Sum $\Sigma$: Aggregates net incoming stimulation $z = \sum w_i x_i + b$.
• Axon $\approx$ Output $y$: Propagates activation pulse if cumulative signal exceeds threshold via non-linear activation function $a = \sigma(z)$.

2. Mathematical Model and Backpropagation Derivation

Consider a 2-layer network with Mean Squared Error loss:

1. Forward Propagation:
   • Hidden layer: $z_1 = W_1 x + b_1$, $a_1 = \sigma(z_1)$
   • Output layer: $z_2 = W_2 a_1 + b_2$, $\hat{y} = \sigma(z_2)$
2. Backpropagation Derivation (Chain Rule):
   • For output layer weight $W_2$:

     Swipe to see the full formula↔

     $$\frac{\partial L}{\partial W_2} = \frac{\partial L}{\partial \hat{y}} \cdot \frac{\partial \hat{y}}{\partial z_2} \cdot \frac{\partial z_2}{\partial W_2}$$

     Swipe to see the full formula↔

     $$\frac{\partial L}{\partial \hat{y}} = - (y - \hat{y}) = (\hat{y} - y)$$

     Swipe to see the full formula↔

     $$\frac{\partial \hat{y}}{\partial z_2} = \sigma'(z_2) = \hat{y}(1 - \hat{y})$$

     Swipe to see the full formula↔

     $$\frac{\partial z_2}{\partial W_2} = a_1$$

     Swipe to see the full formula↔

     $$\implies \delta_2 = (\hat{y} - y) \odot \sigma'(z_2), \quad \frac{\partial L}{\partial W_2} = \delta_2 a_1^T$$
   • For hidden layer weight $W_1$:

     Swipe to see the full formula↔

     $$\delta_1 = (W_2^T \delta_2) \odot \sigma'(z_1), \quad \frac{\partial L}{\partial W_1} = \delta_1 x^T$$
3. Weight Updates (Gradient Descent):

   Swipe to see the full formula↔

   $$W \leftarrow W - \eta \frac{\partial L}{\partial W}, \quad b \leftarrow b - \eta \delta$$

3. Python Implementation of 2-Layer Neural Network From Scratch

import numpy as np

class TwoLayerNeuralNetwork:
    def __init__(self, input_dim: int, hidden_dim: int, output_dim: int, lr: float = 0.5):
        np.random.seed(42)
        self.lr = lr
        # Weight initialization
        self.W1 = np.random.randn(input_dim, hidden_dim) * 0.1
        self.b1 = np.zeros((1, hidden_dim))
        self.W2 = np.random.randn(hidden_dim, output_dim) * 0.1
        self.b2 = np.zeros((1, output_dim))

    @staticmethod
    def sigmoid(z: np.ndarray) -> np.ndarray:
        return 1.0 / (1.0 + np.exp(-np.clip(z, -250, 250)))

    @classmethod
    def sigmoid_derivative(cls, a: np.ndarray) -> np.ndarray:
        return a * (1.0 - a)

    def forward(self, X: np.ndarray) -> np.ndarray:
        self.z1 = np.dot(X, self.W1) + self.b1
        self.a1 = self.sigmoid(self.z1)
        self.z2 = np.dot(self.a1, self.W2) + self.b2
        self.a2 = self.sigmoid(self.z2)
        return self.a2

    def backward(self, X: np.ndarray, y: np.ndarray) -> float:
        m = X.shape[0]
        loss = 0.5 * np.mean((y - self.a2) ** 2)

        # Output layer gradients
        delta2 = (self.a2 - y) * self.sigmoid_derivative(self.a2)
        dW2 = np.dot(self.a1.T, delta2) / m
        db2 = np.sum(delta2, axis=0, keepdims=True) / m

        # Hidden layer gradients
        delta1 = np.dot(delta2, self.W2.T) * self.sigmoid_derivative(self.a1)
        dW1 = np.dot(X.T, delta1) / m
        db1 = np.sum(delta1, axis=0, keepdims=True) / m

        # Parameter update
        self.W2 -= self.lr * dW2
        self.b2 -= self.lr * db2
        self.W1 -= self.lr * dW1
        self.b1 -= self.lr * db1
        return float(loss)

# Training on non-linear XOR Problem
if __name__ == "__main__":
    X_train = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
    y_train = np.array([[0], [1], [1], [0]])

    nn = TwoLayerNeuralNetwork(input_dim=2, hidden_dim=4, output_dim=1, lr=1.0)
    for epoch in range(1500):
        preds = nn.forward(X_train)
        loss = nn.backward(X_train, y_train)

    print("Trained XOR Predictions:")
    print(np.round(nn.forward(X_train), 3))

Comprehensive System Design: Nepal FarmTech AI Agricultural Platform

a) PEAS Framework and Environment Classification

1. PEAS Specification for Crop Diagnostic Agent

2. Environmental Property Classification

• Partially Observable: Camera image captures only external leaf surfaces; underground root rot and latent microscopic fungal spores cannot be directly observed.
• Stochastic: Disease incubation depends on unpredictable weather, temperature fluctuations, and wind dispersion of spores.
• Sequential: Current treatment actions directly impact whether blight spreads or halts in subsequent growth cycles.
• Dynamic: Crop foliage status and microclimate continuously evolve while the diagnostic model is computing.
• Continuous: Pixel intensities, temperature, and ambient humidity are continuous real-valued variables.
• Multi-Agent: The agent operates in an ecosystem alongside farmers, pests, beneficial predator insects, and regional agricultural extension officers.

---

b) Computer Vision & Deep Learning Pipeline

1. Rural Data Augmentation Pipeline

To generalize across low-cost mobile lenses and variable outdoor sunlight in Nepal:

• Photometric Distortions: Random brightness variation ($\pm 25\%$), contrast jittering, and solar glare simulation.
• Geometric Transformations: Random rotations ($0^\circ-360^\circ$), horizontal/vertical flips, and random affine shears mimicking hand tilt.
• Weather & Occlusion Simulators: Random Erasing (Cutout) to simulate finger shadows, mud droplets, or water spray on leaves.

2. Convolutional Neural Network (CNN) Architecture

Input Leaf Image (224x224x3)
      |
      v
[Conv2D Layer: 32 filters (3x3), Stride 1, Padding 'same'] -> Feature maps detecting edges
      |
      v
[Batch Normalization + ReLU Activation] -> Introduces non-linearity & stabilizes gradient
      |
      v
[MaxPooling2D: (2x2 pool size, Stride 2)] -> Spatial downsampling (112x112x32)
      |
      v
[Conv2D Block 2: 64 filters (3x3)] -> Complex texture/spot detection
      |
      v
[MaxPooling2D: (2x2)] -> Downsampling (56x56x64)
      |
      v
[Global Average Pooling] -> Flattens spatial dimensions into feature vector (64)
      |
      v
[Dense Fully Connected Layer: 128 units + Dropout (0.4)] -> Prevents co-adaptation / overfitting
      |
      v
[Output Layer: Dense with Softmax Activation (C classes)] -> Probability distribution over diseases

---

c) Expert Diagnostic & Uncertainty Inference Engine (Python Implementation)

Below is the complete, self-contained Python module fusing Computer Vision probabilistic outputs with Bayesian agronomic priors and expert rule-based pesticide prescriptions:

from typing import Dict, Tuple

class AgronomicBayesianEngine:
    # Prior probabilities of diseases across Nepal Terai region
    DISEASE_PRIORS = {
        "RICE_BLAST": 0.30,
        "BROWN_SPOT": 0.25,
        "BACTERIAL_BLIGHT": 0.20,
        "HEALTHY_LEAF": 0.25
    }

    # Conditional likelihood multipliers given high humidity (> 85%) and rainfall
    WEATHER_FACTORS_HIGH_HUMIDITY = {
        "RICE_BLAST": 2.5,        # Highly favorable to blast fungus
        "BROWN_SPOT": 1.4,
        "BACTERIAL_BLIGHT": 1.8,
        "HEALTHY_LEAF": 0.4
    }

    ADVISORY_RULES = {
        "RICE_BLAST": {
            "disease_name_np": "धानको मरुवा रोग (Rice Blast)",
            "severity": "CRITICAL",
            "organic_cure": "Neem seed kernel extract (5%) spray every 10 days.",
            "chemical_cure": "Tricyclazole 75% WP @ 0.6 g/liter water."
        },
        "BROWN_SPOT": {
            "disease_name_np": "खैरो थोप्ले रोग (Brown Spot)",
            "severity": "MODERATE",
            "organic_cure": "Apply balanced potassium fertilizer and vermicompost.",
            "chemical_cure": "Mancozeb 75% WP @ 2 g/liter water."
        },
        "BACTERIAL_BLIGHT": {
            "disease_name_np": "ब्याक्टेरियल पात डढुवा (Bacterial Blight)",
            "severity": "HIGH",
            "organic_cure": "Drain standing water from field for 3-4 days.",
            "chemical_cure": "Copper Oxychloride 50% WP @ 2.5 g/liter water."
        },
        "HEALTHY_LEAF": {
            "disease_name_np": "स्वस्थ बाली (Healthy Crop)",
            "severity": "NONE",
            "organic_cure": "Continue standard nitrogen-phosphorus-potassium balance.",
            "chemical_cure": "No chemical application necessary."
        }
    }

    @classmethod
    def fuse_evidence(
        cls,
        cnn_probabilities: Dict[str, float],
        humidity_pct: float,
        recent_rain: bool
    ) -> Tuple[str, float, dict]:
        # Compute posterior probability via Bayes Rule fusion: P(Disease | Vision, Weather)
        posteriors = {}
        for disease, cnn_prob in cnn_probabilities.items():
            prior = cls.DISEASE_PRIORS.get(disease, 0.1)
            weather_mult = 1.0
            if humidity_pct > 80.0 or recent_rain:
                weather_mult = cls.WEATHER_FACTORS_HIGH_HUMIDITY.get(disease, 1.0)

            unnormalized_posterior = cnn_prob * prior * weather_mult
            posteriors[disease] = unnormalized_posterior

        # Normalize probabilities
        total_sum = sum(posteriors.values())
        for d in posteriors:
            posteriors[d] = round(posteriors[d] / total_sum, 4)

        # Select diagnosis with maximum posterior probability (MAP estimate)
        final_diagnosis = max(posteriors, key=posteriors.get)
        confidence = posteriors[final_diagnosis]
        advisory = cls.ADVISORY_RULES[final_diagnosis]
        return final_diagnosis, confidence, advisory

# Demonstration Execution
if __name__ == "__main__":
    # Simulated CNN model output on leaf photo:
    # Model is slightly ambiguous between Rice Blast (42%) and Brown Spot (38%)
    raw_cnn_probs = {
        "RICE_BLAST": 0.42,
        "BROWN_SPOT": 0.38,
        "BACTERIAL_BLIGHT": 0.15,
        "HEALTHY_LEAF": 0.05
    }

    # Field sensor readings: High humidity monsoon conditions in Chitwan
    current_humidity = 88.0
    rain_last_24h = True

    diagnosis, confidence, advisory = AgronomicBayesianEngine.fuse_evidence(
        raw_cnn_probs, current_humidity, rain_last_24h
    )

    print("=== Nepal FarmTech Diagnostic Advisory ===")
    print(f"Finalized Disease Diagnosis: {diagnosis} (Confidence: {confidence*100:.1f}%)")
    print(f"Nepali Name: {advisory['disease_name_np']}")
    print(f"Severity: {advisory['severity']}")
    print(f"Organic Remedy: {advisory['organic_cure']}")
    print(f"Chemical Prescription: {advisory['chemical_cure']}")