E Commerce & Governance (IT-504 (B)) - Unit 1 Short Notes

Problem-Solving and Search Techniques

Uninformed Search Algorithms

• Depth-First Search (DFS)

  • Concept: Explores as far as possible along each branch before backtracking. Uses a stack (LIFO).

  • Algorithm:

    1. Push start node onto stack.

    2. While stack not empty:

       • Pop node $n$.

       • If $n$ is goal, return solution.

       • Else, expand $n$ and push all children onto stack.

  • Properties:

    • Not complete (may loop in infinite-depth spaces).

    • Space complexity: $O(bm)$, where $b$ = branching factor, $m$ = max depth.

    • Time complexity: $$\displaystyle O(b^m) $$ worst-case.

    • Not optimal unless step costs are uniform.

  • [!TIP] Use depth-limited DFS or track visited nodes to avoid cycles.

• Breadth-First Search (BFS)

  • Concept: Explores all nodes at current depth before moving deeper. Uses a queue (FIFO).

  • Algorithm:

    1. Enqueue start node.

    2. While queue not empty:

       • Dequeue node $n$.

       • If $n$ is goal, return solution.

       • Else, enqueue all children of $n$.

  • Properties:

    • Complete if $b$ is finite.

    • Space complexity: $$\displaystyle O(b^d) $$, where $d$ = solution depth.

    • Time complexity: $$\displaystyle O(b^d) $$.

    • Optimal for uniform step costs.

  • [!TIP] BFS guarantees shortest path in terms of edges but can be memory-intensive.

• Comparison: DFS vs BFS

  | Feature | DFS | BFS | |----------------------|--------------------------|--------------------------| | Data Structure | Stack | Queue | | Completeness | Incomplete in infinite trees | Complete | | Optimality | Not optimal | Optimal (uniform costs) | | Space Complexity | $O(bm)$ | $$\displaystyle O(b^d) $$ | | Time Complexity | $$\displaystyle O(b^m) $$ | $$\displaystyle O(b^d) $$ | | Best Use Case | Deep solutions | Shallow solutions |

Informed Search Algorithms

• A Algorithm*

  • Evaluation function: $$\displaystyle \boxed{f(n) = g(n) + h(n)} $$

    • $g(n)$: cost from start to node $n$.

    • $h(n)$: heuristic estimate from $n$ to goal.

  • Heuristic Requirements:

    • Admissible: $$\displaystyle h(n) \leq h^*(n) $$ (never overestimates true cost).

    • Consistent: $h(n) \leq c(n,a,n') + h(n')$ for every neighbor $n'$.

  • Application to 8-Puzzle:

    • $g(n)$: depth (number of moves).

    • $h(n)$: misplaced tiles (count of tiles not in goal position, excluding blank).

    • Example: For a state, compute $f$ for all nodes, expand node with lowest $f$.

  • [!TIP] A* is optimal if $h$ is admissible. Misplaced tiles is admissible but not always consistent; Manhattan distance is consistent for 4-direction moves.

• Heuristic Design: Manhattan Distance

  • For grid-based problems (e.g., mouse and cheese maze), Manhattan distance is sum of horizontal and vertical distances.

  • Formula: $$\displaystyle h(n) = |x_n - x_g| + |y_n - y_g| $$.

  • Example: Mouse at $(1,2)$, cheese at $(4,5)$ → $$\displaystyle h = |1-4| + |2-5| = 6 $$.

  • [!TIP] Manhattan distance is admissible for 4-direction movement (up/down/left/right) but not for diagonal moves.

Local Search

• Hill Climbing

  • Algorithm:

    1. Start with initial state $s$.

    2. Loop:

       • Generate successors of $s$.

       • If a successor $s'$ has higher value (or lower cost) than $s$, set $s \gets s'$.

       • Else, stop (local optimum reached).

  • Problems:

    • Local Maxima: State better than neighbors but not global optimum.

    • Plateaus: Flat area where all neighbors have same value; no uphill direction.

    • Ridges: Sequence of local maxima that are difficult to traverse.

  • [!TIP] Hill climbing is greedy and incomplete; use random restarts or simulated annealing to escape local optima.

Production Systems

• Production Rules

  • Definition: IF-THEN rules of the form IF condition THEN action.

  • Characteristics:

    • Modularity: Rules are independent and can be added/removed easily.

    • Condition-Action structure.

    • Incrementality: Knowledge can be acquired incrementally.

    • Expressiveness: Suitable for heuristic knowledge.

  • [!TIP] Production systems are the basis of rule-based expert systems.

• Problem Formulation: Water Jug Problem

  • State: $(a,b)$ where $a$ = gallons in 4-gallon jug, $b$ = gallons in 3-gallon jug.

  • Actions:

    • Fill $A$: $$\displaystyle (a,b) \rightarrow (4,b) $$

    • Fill $B$: $$\displaystyle (a,b) \rightarrow (a,3) $$

    • Empty $A$: $$\displaystyle (a,b) \rightarrow (0,b) $$

    • Empty $B$: $$\displaystyle (a,b) \rightarrow (a,0) $$

    • Pour $$\displaystyle A \rightarrow B $$: until $B$ full or $A$ empty.

    • Pour $$\displaystyle B \rightarrow A $$: similarly.

  • Goal: $(2, *)$ (2 gallons in $A$).

• Solution Generation (one possible sequence):

  1. Fill $B$: $$\displaystyle (0,0) \rightarrow (0,3) $$

  2. Pour $$\displaystyle B \rightarrow A $$: $$\displaystyle (0,3) \rightarrow (3,0) $$

  3. Fill $B$: $$\displaystyle (3,0) \rightarrow (3,3) $$

  4. Pour $$\displaystyle B \rightarrow A $$ until $A$ full: $$\displaystyle (3,3) \rightarrow (4,2) $$

  5. Empty $A$: $$\displaystyle (4,2) \rightarrow (0,2) $$

  6. Pour $$\displaystyle B \rightarrow A $$: $$\displaystyle (0,2) \rightarrow (2,0) $$ → Goal achieved.

  [!TIP] Multiple solutions exist; production rules generate a state-space graph to search.

Knowledge Representation

Properties of a Good Knowledge Representation System

• Representational adequacy: Can express required knowledge.

• Inferential adequacy: Supports derivation of new knowledge.

• Inferential efficiency: Derives conclusions quickly.

• Acquisitional efficiency: Allows easy acquisition of new knowledge.

• Clarity and understandability.

• Modularity and extensibility.

Representation Techniques

• Predicate Logic

  • Syntax: Predicates, variables, constants, quantifiers ($\forall$ universal, $\exists$ existential), connectives ($$\displaystyle \land, \lor, \rightarrow, \neg $$).

  • Conversions:

    • "Everybody loves Ram": $\forall x \, \text{Loves}(x, \text{Ram})$

    • "Everybody loves somebody": $\forall x \, \exists y \, \text{Loves}(x,y)$

    • "There is somebody whom everybody loves": $\exists y \, \forall x \, \text{Loves}(x,y)$

    • "There is somebody who Ram doesn't love": $\exists x \, \neg \text{Loves}(\text{Ram},x)$

    • "There is somebody whom no one loves": $\exists x \, \forall y \, \neg \text{Loves}(y,x)$

  • [!TIP] Order of quantifiers matters: $\forall x \exists y$ ≠ $\exists y \forall x$.

• Fuzzy Logic

  • Fuzzy Sets: Membership function $$\displaystyle \mu_A(x) \in [0,1] $$.

  • Given:

$$A = 1/x_1 + 0.3/x_2 + 0.5/x_3 + 0.2/x_4$$

$$B = 0.5/x_1 + 0.4/x_2 + 0.1/x_3 + 1/x_4$$

• Operations:

  • Union: $$\displaystyle \mu_{A \cup B}(x) = \max(\mu_A(x), \mu_B(x)) $$

$$\boxed{A \cup B = 1/x_1 + 0.4/x_2 + 0.5/x_3 + 1/x_4}$$

- **Intersection**: $$\displaystyle \mu_{A \cap B}(x) = \min(\mu_A(x), \mu_B(x)) $$  

$$\boxed{A \cap B = 0.5/x_1 + 0.3/x_2 + 0.1/x_3 + 0.2/x_4}$$

- **Difference**: $$\displaystyle A - B = A \cap \neg B $$, where $\neg B$ has membership $$\displaystyle 1 - \mu_B(x) $$  

$$\neg B = 0.5/x_1 + 0.6/x_2 + 0.9/x_3 + 0/x_4$$

$$\boxed{A - B = 0.5/x_1 + 0.3/x_2 + 0.5/x_3 + 0/x_4}$$

- **Complement**: $$\displaystyle \mu_{\neg A}(x) = 1 - \mu_A(x) $$  

$$\boxed{\neg A = 0/x_1 + 0.7/x_2 + 0.5/x_3 + 0.8/x_4}$$

• [!TIP] Fuzzy operations use max for union, min for intersection, and difference as $A \cap \neg B$.

• Schematic Nets

  • Structure: Nodes (concepts/objects) connected by arcs (relations).

  • Use: Semantic representation; supports inheritance and reasoning via graph traversal.

  • Example: "Cat is-a Mammal" with an is-a link; properties of Mammal inherited by Cat.

  • [!TIP] Schematic nets are intuitive for representing hierarchical relationships.

Reasoning Methods

• Forward Reasoning (Data-Driven)

  • Concept: Start from known facts, apply rules to derive new facts until goal is reached.

  • Example:

    Rules:

    R1: IF fever AND cough THEN flu.

    R2: IF flu THEN take_rest.

    Facts: fever, cough.

    Forward chain: fever + cough → flu (via R1) → take_rest (via R2).

  • [!TIP] Can generate many irrelevant facts; use goal-directed reasoning to focus.

• Backward Reasoning (Goal-Driven)

  • Concept: Start from goal, work backward to find supporting facts.

  • Example: Goal: take_rest.

    From R2, need flu. From R1, need fever and cough. Check facts: have both → goal achieved.

  • Comparison:

    | Aspect | Forward Reasoning | Backward Reasoning | |------------------|-----------------------------|-----------------------------| | Direction | Data → Conclusion | Goal → Data | | Efficiency | May generate irrelevant facts | Focused on goal | | Best For | Monitoring, interpretation | Problem-solving, query answering |

• Monotonic vs Non-monotonic Reasoning

  • Monotonic: Adding knowledge never retracts conclusions. Classical logic is monotonic.

    Example: "All birds fly. Tweety is a bird." → "Tweety flies." Even if later we learn "Tweety is a penguin," conclusion persists.

  • Non-monotonic: Adding knowledge can invalidate previous conclusions. Handles exceptions.

    Example: "By default, birds fly. Tweety is a bird." → "Tweety flies." But if "Tweety is a penguin" added, retract "Tweety flies."

  • [!TIP] Non-monotonic reasoning (e.g., default logic) is essential for real-world knowledge with exceptions.

• Resolution Technique

  • Principle: Refutation-based proof. Convert statements to clause form (CNF), apply resolution rule to derive empty clause.

  • Application: Used in automated theorem proving and logic programming (e.g., Prolog).

  • [!TIP] Resolution is complete for first-order logic but may not terminate; requires unification.

Decision Making Under Uncertainty

Game Theory: Min-Max Algorithm

• Concept: For two-player, zero-sum games. MAX aims to maximize score; MIN aims to minimize.

• Algorithm:

  1. Generate game tree to a fixed depth (lookahead).

  2. Assign utility values at terminal nodes.

  3. Back up values:

     • MAX nodes: take maximum of children's values.

     • MIN nodes: take minimum of children's values.

  4. At root, choose move leading to highest backed-up value.

• Example:

  DiagramCANVAS: Simple game tree with root (MAX), two children (MIN nodes), each with two leaf nodes having utilities (3,5) and (2,7). Root backs up: left child → min(3,5)=3; right child → min(2,7)=2; root chooses max(3,2)=3 → left move.

• [!TIP] Min-max assumes optimal play; alpha-beta pruning reduces search space.

Bayesian Reasoning: Bayes' Theorem

• Formula:

$$\boxed{P(A|B) = \frac{P(B|A) P(A)}{P(B)}}$$

where $$\displaystyle P(B) = \sum_i P(B|A_i) P(A_i) $$ for all hypotheses $$\displaystyle A_i $$.

• Application in Expert Systems: Update belief in hypothesis $A$ given evidence $B$.

  Example: Medical diagnosis.

  Let $D$ = disease, $T$ = positive test.

  Given: $$\displaystyle P(D)=0.01 $$, $$\displaystyle P(T|D)=0.99 $$, $$\displaystyle P(T|\neg D)=0.05 $$.

$$P(D|T) = \frac{0.99 \times 0.01}{0.99 \times 0.01 + 0.05 \times 0.99} \approx 0.166$$

• [!TIP] Bayes' theorem handles uncertainty by probabilistic updating with evidence.

Expert Systems

• Components:

  • Knowledge Base: Stores facts and production rules.

  • Inference Engine: Applies rules (forward/backward chaining) to derive conclusions.

  • User Interface: Interacts with user (I/O).

  • Explanation Facility: Explains reasoning process.

  • Knowledge Acquisition Tool: For adding/editing knowledge.

• Examples:

  • MYCIN: Medical diagnosis (bacterial infections).

  • DENDRAL: Chemical structure analysis.

• [!TIP] Expert systems separate knowledge from inference, making them maintainable and explainable.

Neural Networks and Natural Language Processing

Neural Networks: Types of Learning

• Supervised Learning:

  • Uses labeled data (input-output pairs).

  • Adjusts weights to minimize error (e.g., via backpropagation).

  • Example: Classification, regression.

• Unsupervised Learning:

  • Uses unlabeled data; finds hidden patterns.

  • Example: Clustering (k-means), dimensionality reduction (PCA), self-organizing maps.

• Reinforcement Learning:

  • Agent learns by interacting with environment; receives rewards/punishments.

  • Example: Q-learning, deep Q-networks (DQN).

• [!TIP] Choice depends on data availability: supervised needs labels, unsupervised discovers structure, reinforcement learns from trial-and-error.

Natural Language Understanding: Components

1. Syntactic Analysis:

   • Parses sentence structure using grammar (e.g., context-free grammar).

   • Output: parse tree or dependency graph.

   • Example: "The cat sat" → [NP [Det The] [N cat]] [VP [V sat]].

2. Semantic Analysis:

   • Determines meaning of words and sentences; disambiguates word senses.

   • Example: "Bank" as financial institution vs. river edge.

3. Pragmatic Analysis:

   • Interprets context-dependent meaning and speaker intent.

   • Example: "Can you pass the salt?" is a request, not a question about ability.

• [!TIP] NLP pipeline: tokenization → POS tagging → parsing → semantic role labeling → discourse analysis.