Artificial Intelligence (IT-504 (A)) - Unit 5 Short Notes

1. FOUNDATIONS OF AI & INTELLIGENT AGENTS

Four Approaches to AI:

• Acting Humanly: Turing Test – machine behavior indistinguishable from human.

• Thinking Humanly: Cognitive modeling – simulate human cognition.

• Thinking Rationally: Laws of thought – formal logic for correct reasoning.

• Acting Rationally: Rational agent – maximizes expected utility.

Agent Structure:

• Sensors: Perceive environment.

• Actuators: Act on environment.

• Agent Function: Maps percept sequence to action.

Agent Types & Comparison:

[!TIP] Goal vs Utility: Goal-based agents seek any goal-satisfying action (binary), utility-based agents rank actions by preference (continuous).

Problem Definition:

• Initial State: Starting configuration.

• Actions: Possible moves from a state.

• Transition Model: Result of action $result(s, a)$.

• Goal Test: Determines if state is goal.

• Path Cost: $cost(path)$, additive.

Tic-Tac-Toe:

• State space: $$\displaystyle 3^9 \approx 19,000 $$ states.

• Minimax application: game tree with alternating max/min nodes.

• Significance: simple domain for demonstrating search, adversarial algorithms.

2. SEARCH ALGORITHMS & STRATEGIES

Uninformed (Blind) Search

Breadth-First Search (BFS):

• Explores all nodes at depth $d$ before depth $d+1$.

• Uses FIFO queue.

• Completeness: Yes (if branching factor finite).

• Optimality: Yes (if step costs uniform).

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

• Example: Finding shortest path in unweighted graph.

Depth-First Search (DFS):

• Explores deepest nodes first.

• Uses LIFO stack.

• Completeness: No (infinite trees).

• Optimality: No.

• Time: $$\displaystyle O(b^m) $$, Space: $O(bm)$.

• Example: Maze traversal.

Depth-Limited Search: DFS with depth limit $l$. Iterative Deepening DFS: Repeatedly run DFS with increasing limits ($$\displaystyle l=0,1,2,... $$). Combines BFS completeness with DFS space efficiency. Bidirectional Search: Search from both start and goal; meet in middle. Reduces time to $$\displaystyle O(b^{d/2}) $$, but requires goal specification and intersection check.

Informed (Heuristic) Search

Best-First Search: General framework using evaluation function $f(n)$ to order nodes.

A Search Algorithm:*

• \boxed{f(n) = g(n) + h(n)}

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

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

• Admissibility: $$\displaystyle h(n) \leq h^*(n) $$ (true cost) → guarantees optimality.

• Consistency: $h(n) \leq c(n,a,n') + h(n')$ for all $n, n'$ → optimal with graph search.

• Pseudocode:

  1. Initialize frontier (priority queue) with start node.

  2. Loop: pop node with lowest $f(n)$.

  3. If goal, return path.

  4. Expand node, add successors with $$\displaystyle f = g + h $$.

• Example: 8-puzzle with $h(n)$ = misplaced tiles or Manhattan distance.

[!TIP] A Optimality*: Requires admissible and consistent heuristic. If inconsistent, use graph search with closed list to avoid re-expansion.

AO Search*:

• For AND-OR graphs (multiple solution paths).

• Solves problems where goal is conjunction of subgoals.

• Expands most promising node, updates cost estimates.

• Compared to A*: handles decomposable problems, but more complex.

Hill Climbing:

• Types:

  • Steepest-ascent: evaluate all successors, choose best.

  • First-choice: choose first better successor.

  • Stochastic: random selection among better successors.

• Problems:

  • Local maxima: peak not global.

  • Plateaus: flat area, no uphill move.

  • Ridges: sequence of local maxima.

• Mitigation: Random restarts, simulated annealing.

Heuristic Search Risks:

• Inadmissible heuristics → suboptimal solutions.

• Overestimation → violates admissibility.

• Trade-off: heuristic accuracy vs computation time.

• Mitigation: Use admissible heuristics, pattern databases, iterative deepening A*.

3. ADVERSARIAL SEARCH & GAME THEORY

Minimax Algorithm:

• Zero-sum, perfect information games.

• Game tree: max nodes (AI), min nodes (opponent).

• Utility values propagated upward: max chooses max value, min chooses min.

• Complexity: $$\displaystyle O(b^m) $$ for depth $m$.

• Example: Tic-Tac-Toe – evaluate terminal states (+1 win, -1 loss, 0 draw).

Alpha-Beta Pruning:

• Alpha ($\alpha$): Best (highest) value for max so far.

• Beta ($\beta$): Best (lowest) value for min so far.

• Prune condition: $\alpha \geq \beta$ – no need to explore further.

• Effect: Reduces nodes evaluated; optimal move ordering achieves $$\displaystyle O(\sqrt{b^m}) $$.

• Variations: Iterative deepening with transposition tables, aspiration windows.

[!TIP] Alpha-Beta Efficiency: Order moves to prune early. Use heuristics to evaluate promising moves first.

4. CONSTRAINT SATISFACTION PROBLEMS (CSP)

CSP Formulation:

• Variables: $$\displaystyle X = \{X_1, ..., X_n\} $$.

• Domains: $$\displaystyle D_i $$ for each $$\displaystyle X_i $$.

• Constraints: Relations $$\displaystyle C_{ij}(X_i, X_j) $$ restricting values.

• State: Assignment of values to variables (partial/complete).

• Goal Test: All variables assigned and constraints satisfied.

Solution Methods:

• Backtracking Search: Depth-first with variable assignments; backtrack on conflict.

• Constraint Propagation:

  • Forward Checking: After assigning $$\displaystyle X_i $$, prune domains of unassigned neighbors.

  • Arc Consistency (AC-3): Enforce $$\displaystyle X_i $$ consistent with $$\displaystyle X_j $$ for all arcs.

• Local Search for CSPs:

  • Min-Conflicts: Start with complete assignment, then change variable with most conflicts to minimize.

  • Example: $n$-queens, graph coloring.

5. KNOWLEDGE REPRESENTATION

Logic-Based Representation

Propositional Logic:

• Syntax: Atoms ($P, Q$), connectives ($$\displaystyle \land, \lor, \neg, \rightarrow $$).

• Semantics: Truth tables.

• Limitations: No quantifiers, cannot represent objects/relations directly.

Predicate Logic (First-Order Logic):

• Symbols: Constants, variables, predicates ($P(x)$), functions.

• Quantifiers: $\forall$ (all), $\exists$ (some).

• Example: "Everybody loves Ram" → $\forall x \; Loves(x, Ram)$.

• Conversion to Clausal Form:

  1. Eliminate $$\displaystyle \rightarrow $$, $$\displaystyle \leftrightarrow $$.

  2. Move $\neg$ inward (De Morgan).

  3. Standardize variables.

  4. Skolemize existential quantifiers (replace with constants/functions).

  5. Distribute $\lor$ over $\land$.

  6. Result: Conjunction of disjunctions (CNF).

Resolution Technique:

• Refutation: To prove goal $G$, add $\neg G$ to KB and derive contradiction.

• Resolution Rule: From $(A \lor B)$ and $(\neg B \lor C)$ infer $(A \lor C)$.

• Completeness: For first-order logic with unification.

• Example: Prove "Steve likes CS3101" from given facts (Dec 2023).

Non-Monotonic Reasoning:

• Conclusions can be withdrawn with new evidence.

• Examples: Default reasoning ("birds fly" unless penguin), truth maintenance systems (TMS).

• Contrast: Monotonic reasoning – adding knowledge never retracts conclusions.

Structured Representation

Semantic Networks:

• Nodes: Objects/concepts.

• Links: Relationships (IS-A, HAS-PART, INSTANCE-OF).

• Inheritance: Properties inherited from superclasses.

• Example: "Fido is a dog" → inherits "has fur" from dog class.

Frames:

• Structure: Slots (attributes) with facets (values, constraints, procedures).

• Inheritance: Frames can inherit from other frames.

• Advantages: Organize knowledge hierarchically, default values.

• Limitations: Rigid, exception handling difficult.

• Applications: Block world, chatbots.

Scripts & Schemas:

• Scripts: Stereotypical event sequences.

  • Components: entry conditions, props, roles, scenes, outcomes.

  • Example: Restaurant script (enter, order, eat, pay).

• Schemas: General knowledge structures (broader than scripts).

• Difference: Frames = static situations; Scripts = dynamic events; Schemas = abstract structures.

• NLP Use: Disambiguate discourse, predict next actions.

Conceptual Dependency:

• Primitive Acts: ATRANS (transfer abstract), PTRANS (transfer physical), MOVE, etc.

• Conceptualization: Meaning independent of words.

• Example: "John cooked dinner" → ATRANS(dinner, John, stove) + MOVE(John, stove) + etc.

6. REASONING & INFERENCE METHODS

Forward Chaining (Data-Driven):

• Start with known facts.

• Match rules: if all antecedents in KB, fire and add consequent.

• Repeat until goal reached or no change.

• Use Cases: Monitoring systems (e.g., intruder detection).

• Advantages: Explains reasoning, good for data-rich environments.

• Disadvantages: May do irrelevant work.

Backward Chaining (Goal-Driven):

• Start with goal.

• Find rules with consequent matching goal.

• Recursively prove antecedents (subgoals).

• Use Cases: Diagnostic systems (e.g., medical diagnosis).

• Advantages: Goal-directed, efficient if few hypotheses.

• Disadvantages: May pursue irrelevant subgoals.

Control Knowledge in Problem-Solving:

• Meta-level reasoning: Reasoning about reasoning (e.g., which rule to apply?).

• Search control: Heuristics to guide search (e.g., most promising variable first in CSP).

• Examples: Variable ordering (minimum remaining values), value ordering (least constraining value).

7. EXPERT SYSTEMS

Definition & Characteristics:

• Knowledge-intensive systems for narrow domains.

• Characteristics: High performance, explanation capability, symbolic reasoning, separation of knowledge and inference.

• vs Conventional Programs: Knowledge is explicit and modifiable; inference engine generic.

Components:

1. Knowledge Base: Facts and rules (production rules, frames).

2. Inference Engine: Applies knowledge (forward/backward chaining).

3. User Interface: Interaction with user.

4. Explanation Facility: Justifies decisions (why/how).

5. Knowledge Acquisition Module: Learns from experts or data.

Inference Engines:

• Forward Chaining: Data-driven; good for monitoring (e.g., alarm systems).

• Backward Chaining: Goal-driven; good for diagnosis (e.g., medical systems).

• Example: MYCIN (medical diagnosis) used backward chaining.

Benefits & Limitations:

Design & Development Considerations:

• Knowledge Elicitation: Interviews, think-aloud protocols.

• Representation Choice: Rules (transparent), frames (structured), neural networks (subsymbolic).

• Validation: Test with known cases, sensitivity analysis.

• Updating: Mechanisms to add/modify rules, handle conflicts.

8. NATURAL LANGUAGE PROCESSING (NLP)

Definition & Significance:

• Tasks: Parsing (syntax), semantics (meaning), discourse (coherence), generation.

• Applications: Chatbots, machine translation, sentiment analysis, information retrieval.

• Significance: Enables human-computer interaction, big data analysis.

Components of NLP:

1. Syntax: Grammar, part-of-speech tagging, parsing.

2. Semantics: Word sense disambiguation, logical form.

3. Pragmatics: Context, speaker intent, implicature.

4. Discourse Processing: Cohesion, anaphora resolution, discourse structure.

Knowledge Representation in NLP:

• Scripts, frames, schemas provide context for understanding.

• Example: Restaurant script helps interpret "We waited 30 minutes" as part of dining experience.

• Conceptual dependency for primitive meaning representation.

Ethical Implications:

• Surveillance: NLP in monitoring can invade privacy (e.g., analyzing emails).

• Bias: Training data biases lead to discriminatory outputs (e.g., gender bias in resumes).

• Mitigation:

  • Diverse, representative training data.

  • Transparency in model decisions.

  • Regulations (GDPR, AI ethics guidelines).

  • Bias detection and debiasing techniques.

9. PROBABILISTIC REASONING & FUZZY LOGIC

Bayes' Theorem:

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

• Significance: Updates belief in hypothesis $A$ given evidence $B$.

• Example (Medical Diagnosis):

  • $A$: Disease, $B$: Symptom.

  • $$\displaystyle P(A|B) = \frac{P(B|A) P(A)}{P(B)} $$ computes posterior probability.

• Advantages:

  • Handles uncertainty systematically.

  • Combines prior knowledge with evidence.

  • Foundation for Bayesian networks.

Fuzzy Sets & Logic:

• Membership Function: $$\displaystyle \mu_A(x) \in [0,1] $$ degree of membership of $x$ in fuzzy set $A$.

• Operations (for fuzzy sets $A$, $B$):

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

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

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

  • Difference: $$\displaystyle \mu_{A-B}(x) = \min(\mu_A(x), 1 - \mu_B(x)) $$

Example (Nov 2022 B):

Given $$\displaystyle A = 1/x_1 + 0.3/x_2 + 0.5/x_3 + 0.2/x_4 $$, $$\displaystyle B = 0.5/x_1 + 0.4/x_2 + 0.1/x_3 + 1/x_4 $$:

• Union: $$\displaystyle \max(1,0.5)/x_1 + \max(0.3,0.4)/x_2 + \max(0.5,0.1)/x_3 + \max(0.2,1)/x_4 = 1/x_1 + 0.4/x_2 + 0.5/x_3 + 1/x_4 $$

• Intersection: $$\displaystyle \min(1,0.5)/x_1 + \min(0.3,0.4)/x_2 + \min(0.5,0.1)/x_3 + \min(0.2,1)/x_4 = 0.5/x_1 + 0.3/x_2 + 0.1/x_3 + 0.2/x_4 $$

• Difference: $$\displaystyle \min(1, 1-0.5)/x_1 + \min(0.3, 1-0.4)/x_2 + \min(0.5, 1-0.1)/x_3 + \min(0.2, 1-1)/x_4 = 0.5/x_1 + 0.3/x_2 + 0.5/x_3 + 0/x_4 $$

• Complement of $A$: $$\displaystyle 1-1/x_1 + 1-0.3/x_2 + 1-0.5/x_3 + 1-0.2/x_4 = 0/x_1 + 0.7/x_2 + 0.5/x_3 + 0.8/x_4 $$

10. CLASSIC AI PROBLEMS & CASE STUDIES

Blocks World:

• Representation: Blocks on table, robot arm actions (pick-up, put-down, stack, unstack).

• Significance: Testbed for planning, robotics, STRIPS language.

• Recent Advancements: Integration with computer vision (perceiving blocks), deep learning for grasp planning, simulation environments (PyBullet).

Water Jug Problem:

• Production Rules (4-gal $x$, 3-gal $y$):

  1. $$\displaystyle (x,y) \rightarrow (4,y) $$ if $$\displaystyle x < 4 $$ (fill 4-gal).

  2. $$\displaystyle (x,y) \rightarrow (x,3) $$ if $$\displaystyle y < 3 $$ (fill 3-gal).

  3. $$\displaystyle (x,y) \rightarrow (0,y) $$ if $$\displaystyle x > 0 $$ (empty 4-gal).

  4. $$\displaystyle (x,y) \rightarrow (x,0) $$ if $$\displaystyle y > 0 $$ (empty 3-gal).

  5. $$\displaystyle (x,y) \rightarrow (x-\min(x,3-y), y+\min(x,3-y)) $$ (pour 4→3).

  6. $$\displaystyle (x,y) \rightarrow (x+\min(y,4-x), y-\min(y,4-x)) $$ (pour 3→4).

• Solution to get 2 in 4-gal: Fill 3-gal, pour to 4-gal, fill 3-gal again, pour to 4-gal until full (leaves 2 in 3-gal), empty 4-gal, pour 2 from 3-gal to 4-gal, fill 3-gal, pour to 4-gal → 2 in 4-gal.

8-Puzzle Problem:

• State: 3×3 grid with 8 tiles, 1 blank.

• A Application*:

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

  • $h(n)$:

    • Misplaced tiles: count of tiles not in goal position.

    • Manhattan distance: sum of horizontal/vertical distances from goal.

• Optimality: Manhattan distance is admissible and consistent.

Production Systems:

• Characteristics: Condition-action rules (IF-THEN), modular, declarative knowledge.

• Comparison:

  • vs Procedural: Knowledge separate from control.

  • vs Logic: Rules easier to encode heuristic knowledge.

• Components: Rule set, working memory, conflict resolution strategy.

11. EVOLUTION & INTERDISCIPLINARY NATURE OF AI

AI as Interdisciplinary Field:

• Computer Science: Algorithms, data structures, complexity.

• Mathematics: Logic, probability, optimization, linear algebra.

• Psychology: Cognitive modeling, human learning.

• Linguistics: Syntax, semantics for NLP.

• Neuroscience: Brain-inspired architectures (neural networks).

Classical vs Modern AI Systems:

AI for Global Challenges:

• Climate Change: Predictive models for weather, optimization of energy grids, carbon footprint analysis.

• Healthcare: Medical diagnosis (imaging analysis), drug discovery (molecular simulation), personalized treatment.

• Education: Adaptive learning systems, automated grading, intelligent tutoring.

[!TIP] Exam Focus: Be prepared to compare classical vs modern AI with examples. Understand interdisciplinary contributions for essay questions.