AI Essentials Cheatsheet

Cheatsheet Content

Intelligent Agents An Intelligent Agent is anything that can perceive its environment through sensors and act upon that environment through actuators. Agents strive to achieve goals by performing actions. They can be categorized by their level of intelligence and capability. Agent Structure Architecture: The hardware/software platform on which the agent runs. Agent Program: The implementation of the agent function, mapping percepts to actions. Percepts: Agent's sensory inputs at a given instant. Percept Sequence: The complete history of everything the agent has ever perceived. Agent Function: $f: P^* \rightarrow A$, mapping percept histories to actions. Agent Program: Runs on the physical architecture to produce $f$. function AGENT(percept) returns action static: percepts, a sequence, initially empty add percept to percepts action Environment Agent Percepts Actions Agent-Environment Interaction Agent Types (Behaviour) Simple Reflex Agents: Act based on current percept , ignoring history. function SIMPLE-REFLEX-AGENT(percept) returns action state Model-based Reflex Agents: Maintain an internal state (model of the world) to track unobserved aspects of the environment. How the world evolves: Transition model. Effect of agent's actions: Action model. Goal-based Agents: Consider future actions and their outcomes to achieve a goal. Requires search and planning. Utility-based Agents: Choose actions that maximize their utility function (measure of performance). Useful for conflicting goals or uncertainty. Learning Agents: Improve their performance over time by learning from experience. Learning Element: Makes improvements. Performance Element: Selects external actions. Critic: Provides feedback on how the agent is doing. Problem Generator: Suggests actions that might lead to new experiences. Environment Types Properties of the environment significantly impact agent design: Observable vs. Partially Observable: Can the agent perceive the complete state of the environment? Single Agent vs. Multi-Agent: Is there one agent or multiple interacting agents? Deterministic vs. Stochastic: Is the next state fully determined by the current state and action, or is there randomness? Episodic vs. Sequential: Are actions independent or do they affect future decisions? Static vs. Dynamic: Does the environment change while the agent is deliberating? Discrete vs. Continuous: Are states and actions finite/countable or infinite? Known vs. Unknown: Are the rules of the environment known to the agent? Search Techniques in AI Search algorithms are fundamental to problem-solving in AI, used to explore possible solution paths to find a goal state. Uninformed Search (Blind Search) These algorithms have no information about the distance or cost to the goal. Breadth-First Search (BFS): Explores all nodes at the current depth level before moving to the next level. Uses a queue (FIFO) to store nodes. Completeness: Yes, if a solution exists. Optimality: Yes, for unweighted graphs (finds shortest path in terms of number of edges). Time Complexity: $O(b^d)$, where $b$ is branching factor, $d$ is depth of shallowest solution. Space Complexity: $O(b^d)$, can be very high. Pros: Guaranteed to find the shallowest solution. Cons: High memory consumption for deep trees; not optimal for weighted graphs. Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Uses a stack (LIFO) to store nodes. Completeness: No, can get stuck in infinite paths/loops if not modified. Optimality: No, may find a deep, suboptimal solution first. Time Complexity: $O(b^m)$, where $m$ is maximum depth of search space. Space Complexity: $O(bm)$, much less than BFS. Pros: Low memory usage; finds solutions quickly if they are deep. Cons: Not guaranteed to find the shallowest or optimal solution; can get stuck in infinite paths. BFS vs DFS Comparison Feature BFS DFS Strategy Explore level by level Explore depth-wise Data Structure Queue (FIFO) Stack (LIFO) Completeness Yes No (without modifications) Optimality Yes (for unweighted) No Time Complexity $O(b^d)$ $O(b^m)$ Space Complexity $O(b^d)$ $O(bm)$ Memory Usage High Low Finds Shallowest Yes No Informed Search (Heuristic Search) These algorithms use heuristic functions to estimate the cost from the current state to the goal. A heuristic function $h(n)$ estimates the cost of the cheapest path from node $n$ to a goal node. Greedy Best-First Search: Expands the node that appears to be closest to the goal (using heuristic $h(n)$). Not optimal. A* Search: Combines UCS and Greedy BFS. Expands nodes with the lowest value of $f(n) = g(n) + h(n)$, where $g(n)$ is cost from start to $n$, and $h(n)$ is estimated cost from $n$ to goal. Completeness: Yes, if $h(n)$ is admissible (never overestimates). Optimality: Yes, if $h(n)$ is admissible and consistent. Hill Climbing: A local search algorithm that iteratively moves towards a state with a better value (higher in a maximization problem, lower in a minimization problem) until a peak (or valley) is reached. Starts at an arbitrary solution. Generates neighbors and moves to the best neighbor if it's better than the current state. Problems: Can get stuck in local maxima/minima , plateaus, or ridges. Local Maxima Local Maxima Plateau Global Maxima Start Hill Climbing Challenges: Local Maxima & Plateau Logic & Knowledge Representation Resolution Principle The Resolution Principle is an inference rule used in automated theorem proving for propositional and first-order logic. It's a sound and refutation-complete proof procedure, meaning if a set of clauses is unsatisfiable, resolution will always be able to derive a contradiction (the empty clause $\Box$). Conversion to Conjunctive Normal Form (CNF): All logical statements must first be converted into CNF, which is a conjunction of disjunctions (clauses). Example: $(A \lor \neg B) \land (B \lor C)$ Resolution Rule: For two clauses $(P \lor Q)$ and $(\neg Q \lor R)$, the resolvent is $(P \lor R)$. The literal $Q$ and $\neg Q$ are called complementary literals . Refutation Proof: To prove a statement $S$ from a knowledge base $KB$: Assume $\neg S$ (negation of $S$). Convert $KB \land \neg S$ into CNF. Repeatedly apply the resolution rule to the clauses. If the empty clause $\Box$ is derived, then $KB \land \neg S$ is unsatisfiable, which means $S$ must be true given $KB$. $(A \lor B)$ $(\neg B \lor C)$ $(A \lor C)$ Propositional Resolution Example Production Rules Production Rules , often called If-Then rules, are a popular way to represent knowledge in expert systems and rule-based systems. They consist of a condition part (antecedent) and an action/conclusion part (consequent). Format: IF <condition> THEN <action/conclusion> Condition (Antecedent): A pattern or set of patterns that must be matched against facts in a working memory or database. Action/Conclusion (Consequent): An action to be performed (e.g., add a new fact, modify an existing fact, execute a procedure) or a conclusion to be drawn if the condition is met. Rule Interpreter (Inference Engine): Matching: Identifies rules whose conditions are satisfied by the current facts. Conflict Resolution: If multiple rules match, it selects one to fire (e.g., by priority, specificity, recency). Execution (Firing): Executes the action part of the selected rule. Types of Chaining: Forward Chaining (Data-Driven): Starts with known facts and applies rules to deduce new facts until a goal is reached or no more rules can fire. ($A \rightarrow B, B \rightarrow C$, given $A$ deduce $C$). Backward Chaining (Goal-Driven): Starts with a goal and works backward to find rules that could prove it, recursively trying to prove the conditions of those rules. (To prove $C$, need $B$; to prove $B$, need $A$). Natural Language Processing (NLP) Context-Free Grammars (CFG) Context-Free Grammars (CFGs) , also known as Type 2 grammars in the Chomsky Hierarchy, are widely used in NLP for syntactic parsing . They define the syntax of a language by specifying how sequences of words can form grammatical phrases and sentences. Components: A CFG consists of: A finite set of Non-terminal symbols (variables), typically representing syntactic categories (e.g., S, NP, VP). A finite set of Terminal symbols (words or lexical items), which are the actual words of the language. A finite set of Production Rules , each of the form $A \rightarrow \beta$, where $A$ is a non-terminal and $\beta$ is a sequence of terminals and/or non-terminals. A distinguished Start Symbol (usually S), representing a complete sentence. Example Rules: $S \rightarrow NP \ VP$ $NP \rightarrow Det \ N$ $VP \rightarrow V \ NP$ $Det \rightarrow \text{the} \ | \ \text{a}$ $N \rightarrow \text{cat} \ | \ \text{dog}$ $V \rightarrow \text{chased}$ Parse Trees: CFGs generate parse trees that visually represent the syntactic structure of a sentence. Limitations: CFGs struggle with certain linguistic phenomena that require context-sensitivity , such as agreement ("The cat *sits*" vs. "The cats *sit*") or long-distance dependencies. S NP Det The N cat VP V chased NP a dog CFG Parse Tree for "The cat chased a dog" Transformational Grammars Transformational Grammars (TG) , introduced by Noam Chomsky, extend CFGs by adding a layer of "transformational rules" that operate on the output of CFG (deep structure) to produce the final surface structure of a sentence. They aim to capture more complex linguistic phenomena and the relationship between different sentence forms. Deep Structure: The underlying syntactic representation generated by CFG rules, representing the basic meaning and grammatical relations. Surface Structure: The actual linear sequence of words we speak or write, derived from the deep structure through transformations. Transformational Rules: Operations that modify the deep structure, such as Movement (e.g., forming questions: "John saw who?" $\rightarrow$ "Who did John see?"), Deletion , Insertion . Motivation: TGs were developed to address limitations of CFGs by explaining: Syntactic ambiguities that seemingly have one deep structure. The relationship between active and passive sentences (e.g., "The dog chased the cat" and "The cat was chased by the dog"). Deep Structure Surface Structure Transformational Rules "The dog chased the cat." "The cat was chased by the dog." Passive Transformation Deep Structure to Surface Structure via Transformation Reasoning Default Reasoning Default Reasoning (or Non-monotonic Reasoning ) is a type of reasoning where conclusions can be retracted or revised when new information contradicts them. Unlike classical monotonic logic, where adding new axioms never invalidates existing theorems, default reasoning allows for beliefs to change. Defaults: Allow agents to draw conclusions based on typical expectations , even in the absence of complete information. "Birds typically fly." Example: If we know "Tweety is a bird," we can default to "Tweety can fly." However, if we later learn "Tweety is a penguin," we retract the previous conclusion and infer "Tweety cannot fly." Formalisms: Default Logic, Non-monotonic Logics (Autoepistemic logic, Circumscription). Applications: Common sense reasoning, diagnosis, legal reasoning, where exceptions to general rules are prevalent. Challenge: Managing conflicting defaults . Probabilistic Reasoning Probabilistic Reasoning deals with uncertainty by assigning probabilities to events and using probability theory to update beliefs and make inferences. It's crucial in environments where outcomes are not deterministic. Key Concepts: Probability: A numerical measure of the likelihood of an event. Random Variables: Variables whose values are outcomes of random phenomena. Bayes' Theorem: $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$ - fundamental for updating beliefs based on new evidence . Representations: Bayesian Networks (Belief Networks): Directed Acyclic Graphs (DAGs) where nodes represent random variables and edges represent probabilistic dependencies. They provide a compact way to represent joint probability distributions. Markov Chains: Describe sequences of events where the probability of each event depends only on the state of the previous event. Applications: Medical diagnosis, spam filtering, robotics. Production Systems A Production System is a classic AI architecture for implementing rule-based systems . It's a method for organizing and applying knowledge in a modular and easily modifiable way, often used in expert systems. Components Working Memory (Fact Base): A global database of facts or assertions representing the current state of the problem. Production Memory (Rule Base): A set of production rules (If-Then rules) that operate on the working memory. Inference Engine (Rule Interpreter): The control structure that cycles through three phases: Match: Identifies rules whose conditions are satisfied by facts. These form the "conflict set." Conflict Resolution: Selects one rule to "fire" from the conflict set. Strategies: Recency, Specificity, Priority . Act (Execute): The RHS of the selected rule is executed, modifying the working memory. How it Works (Cycle) The system operates in a continuous Match-Conflict Resolution-Act cycle until a termination condition is met (e.g., no rules match, a goal state is reached). Production Memory Working Memory Conflict Set Match Rules Select Inference Engine Act Production System Architecture Game Playing Alpha-Beta Pruning Algorithm Alpha-Beta Pruning is an optimization technique for the minimax algorithm , used in game theory and AI for two-player zero-sum games (e.g., chess). It reduces the number of nodes that need to be evaluated in the search tree, without changing the final decision. Minimax Algorithm: Assumes both players play optimally. MAX player tries to maximize score, MIN player tries to minimize MAX's score. The Pruning Principle: Eliminates branches that cannot possibly influence the final decision . It maintains two values: $\alpha$ (alpha): The best value (highest) found so far for the MAX player on the path from the root. Initialized to $-\infty$. $\beta$ (beta): The best value (lowest) found so far for the MIN player on the path from the root. Initialized to $+\infty$. How it Works: If a MAX node's $\alpha$ value becomes $\ge$ a MIN node's $\beta$ value ($\alpha \ge \beta$), then the current branch can be pruned . (The MIN player already has a better option elsewhere). Conversely, if a MIN node's $\beta$ value becomes $\le$ a MAX node's $\alpha$ value, the current branch can be pruned . (The MAX player already has a better option elsewhere). Efficiency: In the best case (perfect move ordering), alpha-beta pruning can reduce the effective branching factor from $b$ to $\sqrt{b}$. MAX ? MIN ? MIN ? MAX ? MAX ? MAX ? MAX ? 3 12 8 2 14 5 2 9 12 8 8 14 2 2 8 Pruned Alpha-Beta Pruning Example (after first branch evaluation) Languages PROLOG PROLOG (Programming in Logic) is a declarative logic programming language . Instead of telling the computer *how* to solve a problem, you describe *what* the problem is and *what relationships* exist, and PROLOG's inference engine attempts to find solutions. Declarative Paradigm: Programs consist of facts and rules . Facts: Statements about objects and their relationships (e.g., parent(john, mary). ). Rules: General statements about relationships (e.g., grandparent(X, Z) :- parent(X, Y), parent(Y, Z). ). Unification: The core mechanism where PROLOG matches patterns by assigning values to variables. Backward Chaining (Goal-Driven): PROLOG's inference engine works by trying to prove a query (goal). It starts with the query and attempts to find rules whose heads match, then recursively tries to satisfy subgoals. Uses backtracking if a path fails. Key Features: Built-in Backtracking, Pattern Matching, Recursion. Applications: Expert systems, natural language processing, theorem proving. % Facts father(john, mary). father(john, tom). mother(susan, mary). mother(susan, tom). % Rules parent(X, Y) :- father(X, Y). parent(X, Y) :- mother(X, Y). grandparent(X, Z) :- parent(X, Y), parent(Y, Z). % Query ?- grandparent(X, tom). % Expected Output: X = john ; X = susan. Conceptual Graphs Conceptual Graphs (CGs) are a knowledge representation formalism based on Peirce's existential graphs and semantic networks. They provide a graphically oriented, logic-based notation for representing knowledge that aims to be both human-readable and computationally tractable. Components: A CG is a finite, connected, bipartite graph consisting of two types of nodes: Concept Nodes: Represent entities, attributes, states, or events. Drawn as rectangles (e.g., [Cat] , [Person: John] ). Relation Nodes: Represent relationships between concepts. Drawn as ovals or circles (e.g., (agent) , (obj) ). Basic Structure: Concepts are linked to relations, and relations are linked to concepts. Example: "A cat is on a mat." $\rightarrow$ [Cat]-(on)-[Mat] Example: "John is eating an apple." $\rightarrow$ [Person: John]-(agent)-[Eat]-(object)-[Apple] Referent Field: Concept nodes can specify particular individuals (e.g., [Person: John] ) or quantities. Operations: CGs support formal operations for reasoning: Projection, Join, Simplification . Advantages: Expressiveness, Visual Clarity, Formal Basis. Applications: Knowledge management, natural language understanding, semantic web. Person: John agent Eat object Apple Conceptual Graph for "John is eating an apple." Expert Systems An Expert System is a computer program that attempts to mimic the reasoning ability of a human expert in a specific domain. Its primary goal is to provide specialized problem-solving expertise to non-experts. Features High Performance: Solves problems effectively and efficiently. Reliability: Consistent in its decision-making. Understandability: Can explain its reasoning process (transparency). Responsiveness: Provides solutions in a timely manner. Domain Specificity: Expertise is limited to a narrow domain. Heuristic Reasoning: Uses rules of thumb and experience, not just formal logic. Components Knowledge Base: Contains the domain-specific knowledge, typically represented as production rules (If-Then rules) , frames, or semantic nets. Inference Engine: The "brain" of the expert system. It processes the knowledge base to draw conclusions. Uses forward chaining (data-driven) or backward chaining (goal-driven) or a combination. Working Memory (Fact Base): Stores the current state of the problem, including facts provided by the user or inferred by the system. User Interface: Allows the user to interact with the system (input queries, receive advice, provide facts). Explanation Facility: Provides a justification for the system's conclusions by tracing the rules that were fired. Knowledge Acquisition Module: Helps experts to input and refine knowledge into the knowledge base (often a manual process). User Expert User Interface Explanation Knowledge Acq. Inference Engine Knowledge Base Working Memory Expert System Architecture Logic: First Order Predicate Logic (FOPL) First Order Predicate Logic (FOPL) , also known as First Order Logic (FOL), is a powerful formal system for knowledge representation and reasoning . It extends propositional logic by allowing quantification over individuals and properties, enabling more expressive and nuanced statements about the world. Components of FOPL Constants: Refer to specific objects (e.g., John , 2 , Denver ). Predicates: Represent properties of objects or relationships between objects (e.g., Is_Person(John) , Likes(John, Mary) , Is_Brother_Of(John, Tom) ). Functions: Map one or more objects to another object (e.g., FatherOf(John) , Plus(2, 3) ). Variables: Stand for any object in a domain (e.g., $x, y, z$). Connectives: Same as propositional logic: $\land$ (AND), $\lor$ (OR), $\neg$ (NOT), $\rightarrow$ (IMPLIES), $\leftrightarrow$ (EQUIVALENCE). Quantifiers: Universal Quantifier ($\forall$): "For all" or "For every" (e.g., $\forall x \text{ Is_Person}(x) \rightarrow \text{Has_Two_Legs}(x)$ - "All persons have two legs"). Existential Quantifier ($\exists$): "There exists" or "For some" (e.g., $\exists x \text{ Is_Person}(x) \land \text{Likes_Pizza}(x)$ - "There exists a person who likes pizza"). Knowledge Representation in FOPL FOPL allows representing complex knowledge about objects, properties, and relationships in a precise and unambiguous way. "All men are mortal": $\forall x (\text{Man}(x) \rightarrow \text{Mortal}(x))$ "Socrates is a man": $\text{Man}(\text{Socrates})$ "There is a red car": $\exists x (\text{Car}(x) \land \text{Color}(x, \text{Red}))$ "If a student studies, they will pass": $\forall s (\text{Student}(s) \land \text{Studies}(s) \rightarrow \text{Passes}(s))$ Reasoning with FOPL FOPL provides a basis for powerful inference mechanisms. The Resolution Principle (discussed earlier) is particularly important for automated reasoning in FOPL. To apply resolution in FOPL, sentences must first be converted to Clausal Form (a variant of CNF where quantifiers are eliminated, and variables are standardized). Role of Resolution Principle for Knowledge Representation: Once knowledge is represented in FOPL and converted to clausal form, the resolution principle can be used to deduce new facts or to prove theorems (i.e., answer queries). It works by trying to find a contradiction (empty clause) when the negation of the query is added to the knowledge base. If a contradiction is found, the query is proven true. This makes FOPL, combined with resolution, a foundational tool for building intelligent systems capable of logical inference. Semantic Nets A Semantic Net is a knowledge representation technique that uses a graphical notation to represent knowledge. It consists of nodes representing concepts or objects, and links (arcs) representing relationships between these concepts. How Knowledge is Represented Nodes (Concepts/Objects): Typically drawn as ovals or rectangles. They represent entities like "Bird," "Tweety," "Flying," "Color." Links (Relationships/Arcs): Directed edges between nodes, labeled with the type of relationship. Common relations include: IS-A: Represents a class-subclass relationship (e.g., "Tweety IS-A Bird"). This implies inheritance of properties. HAS-A: Represents a part-whole relationship (e.g., "Bird HAS-A Wings"). CAN: Represents an ability (e.g., "Bird CAN Fly"). Property links: Links to attribute values (e.g., "Bird Color Yellow"). Example Bird Animal Tweety Yellow Fly Wings IS-A IS-A HAS-A CAN COLOR Semantic Net Example Advantages Visual Representation: Easy for humans to understand. Inheritance: Properties can be inherited through IS-A links, reducing redundancy. Flexible: Can represent a wide variety of knowledge. Disadvantages Ambiguity: Meaning of links can sometimes be ambiguous. Lack of Formal Semantics: Not as formally defined as logic, making automated reasoning more complex. Difficulty with Quantification: Hard to represent universal or existential statements (e.g., "All birds fly"). Bayesian Networks A Bayesian Network (also known as a Belief Network or Bayes Net) is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph (DAG) . It's used for probabilistic inference under uncertainty. Components Nodes: Represent random variables (discrete or continuous). Each node has a conditional probability table (CPT) that quantifies the effect of the parents on the node. Directed Edges: Represent direct causal or influential relationships between variables. An edge from A to B means A is a parent of B, and A directly influences B. The absence of an edge implies conditional independence. DAG (Directed Acyclic Graph): No cycles are allowed, meaning a variable cannot be its own ancestor. How it Works (Probabilistic Inference) Bayesian networks allow us to calculate the probability of any variable given evidence, using Bayes' Theorem . The network structure compactly represents the joint probability distribution of all variables. $P(X_1, ..., X_n) = \prod_{i=1}^{n} P(X_i | Parents(X_i))$ Example: Burglar Alarm Network Consider a scenario with a burglar alarm. It can be triggered by a burglar or an earthquake. If the alarm sounds, your neighbors John and Mary might call you. Variables: Burglary (B), Earthquake (E), Alarm (A), JohnCalls (J), MaryCalls (M). Dependencies: B and E are independent causes of A. A is the direct cause of J and M. J and M are conditionally independent given A. Burglary Earthquake Alarm JohnCalls MaryCalls Bayesian Network for Burglar Alarm Inference with Bayesian Networks Given evidence (e.g., JohnCalls is true), we can query the network for the probability of other variables (e.g., the probability of a Burglary). This involves calculating conditional probabilities using the CPTs and the network structure. Exact Inference: Enumeration, Variable Elimination. Approximate Inference: Sampling methods (e.g., Gibbs sampling), Markov chain Monte Carlo (MCMC). Advantages Handles Uncertainty: Provides a principled way to reason under uncertainty. Compact Representation: Captures complex dependencies efficiently. Causal Relationships: Often reflects causal links, which aids understanding. Learning: Network structure and CPTs can be learned from data. Applications Medical diagnosis, spam filtering, image processing, speech recognition, risk assessment. Min-Max Algorithm The Min-Max Algorithm is a decision rule used in artificial intelligence, decision theory, game theory, and statistics for minimizing the possible loss for a worst-case (maximum loss) scenario . It is primarily used for two-player, zero-sum games (where one player's gain is exactly the other player's loss), such as Tic-Tac-Toe, Chess, or Checkers. Core Idea The algorithm explores the game tree, evaluating all possible moves up to a certain depth. It assumes that both players play optimally . MAX Player: The player trying to maximize their score. MIN Player: The opponent, trying to minimize the MAX player's score (which is equivalent to maximizing their own score). How it Works Generate Game Tree: Starting from the current game state, generate all possible subsequent states (moves) up to a predefined search depth. Evaluate Terminal Nodes: Assign a utility value (score) to each terminal node (leaf node) of the game tree. A positive score typically means a win for MAX. A negative score typically means a win for MIN. Zero means a draw. Propagate Values Upwards: For a MAX node (where it's MAX's turn): The value of this node is the maximum of the values of its children nodes. MAX chooses the move that leads to the highest score. For a MIN node (where it's MIN's turn): The value of this node is the minimum of the values of its children nodes. MIN chooses the move that leads to the lowest score for MAX. Choose Best Move: The algorithm continues propagating values up the tree until it reaches the root node. The move from the root that leads to the child node with the highest value is the optimal move for the MAX player. MAX 3 MIN 3 MIN 2 MAX 3 MAX 5 MAX 6 MAX 2 3 12 8 5 14 6 2 9 Min-Max Algorithm Example Limitations Computational Cost: The number of nodes in a game tree grows exponentially with depth (branching factor $b$, depth $d$, nodes $\approx b^d$). This makes it impractical for games with large search spaces (like chess) beyond a shallow depth. Static Evaluation Function: Relies on a good heuristic function to evaluate non-terminal nodes when the search depth is limited. Knowledge-Based Systems A Knowledge-Based System (KBS) is a computer program that uses a knowledge base of human expertise to solve problems that ordinarily require human intelligence. It's a broader term than expert systems, as it encompasses any system that relies heavily on a structured representation of domain knowledge for its operation. Components Knowledge Base: The core of the KBS, containing domain-specific facts, rules, heuristics, and relationships. Inference Engine (or Reasoning Mechanism): Applies logical rules and procedures to the knowledge base to derive new knowledge or solve problems. Knowledge Acquisition Subsystem: Tools and methods used to acquire, refine, and update knowledge from human experts or other sources. Explanation Subsystem: Justifies the system's reasoning and conclusions to the user. User Interface: Facilitates interaction between the user and the system. Various Representation Techniques for Knowledge The choice of representation technique significantly impacts the system's reasoning capabilities and efficiency. 1. Logical Representation (First-Order Predicate Logic, Propositional Logic): Description: Knowledge is expressed as formal logical statements (predicates, quantifiers, connectives). Example: $\forall x (\text{Bird}(x) \land \neg \text{Penguin}(x) \rightarrow \text{Flies}(x))$ Advantages: Precise, unambiguous, allows for formal inference (e.g., resolution principle). Disadvantages: Can be complex for large knowledge bases, computationally expensive for inference, difficulty representing default/uncertain knowledge. 2. Rule-Based Representation (Production Rules): Description: Knowledge is stored as If-Then rules. Example: IF (temperature is high) AND (humidity is high) THEN (predict rain) Advantages: Modular, easy to understand, supports explanation, good for heuristic knowledge. Disadvantages: Limited expressiveness for complex relationships, conflict resolution can be tricky, inefficient for large rule sets. 3. Semantic Networks: Description: Knowledge is represented as a graph where nodes are concepts and links are relationships. Example: Bird --(IS-A)--> Animal , Tweety --(IS-A)--> Bird Advantages: Visually intuitive, supports inheritance, flexible. Disadvantages: Lack of formal semantics, difficulty representing complex logical structures (quantification, negation). 4. Frames: Description: Knowledge is organized into data structures called "frames," which represent stereotypical situations or objects. Each frame has "slots" (attributes) and "fillers" (values or pointers to other frames/procedures). Example (Frame for "Bird"): Slot: Name (value: Tweety) Slot: Class (value: Bird) Slot: Legs (value: 2) Slot: Movement (value: Fly, default: True) Slot: Color (value: Yellow) Advantages: Good for representing structured, hierarchical knowledge, supports default reasoning and inheritance. Disadvantages: Less formal than logic, can be complex for highly dynamic knowledge. 5. Scripts: Description: A specialized type of frame-like structure used to represent knowledge about stereotypical sequences of events in a particular context. Example (Restaurant Script): Props: Tables, Menus, Food, Waiter, Customer. Roles: Customer, Waiter, Chef. Scenes: Entering, Ordering, Eating, Paying, Exiting. Each scene has a sequence of actions. Advantages: Excellent for understanding narratives and predicting events in well-defined contexts. Disadvantages: Limited to highly predictable sequences, less flexible for novel situations. Frames vs Scripts Comparison Feature Frames Scripts What it represents Stereotypical objects, concepts, situations Stereotypical sequences of actions/events Structure Slots and fillers (attributes & values) Props, Roles, Entry Conditions, Scenes (sequences of actions) Focus Static description of an entity/concept Dynamic, time-ordered sequence of events Use Case Object representation, classification, property inheritance Story understanding, expectation generation, planning routines Parsing Techniques in Natural Languages (NLP) Parsing in Natural Language Processing (NLP) is the process of analyzing a sequence of words (a sentence) to determine its grammatical structure according to a given grammar . The output is typically a parse tree (syntactic tree) that shows the syntactic relationships between words and phrases. Types of Parsing Syntactic Parsing: Focuses on the grammatical structure of sentences. This is the most common type. Semantic Parsing: Aims to map natural language sentences into formal meaning representations (e.g., logical forms). Common Parsing Techniques (for Syntactic Parsing) 1. Top-Down Parsing: Approach: Starts from the start symbol (S) of the grammar and tries to apply production rules to derive the input sentence. It predicts what structures should appear and tries to match them to the input. Method: Builds the parse tree from the root downwards to the leaves. Example: Recursive Descent Parser, LL parsers. Pros: Intuitive, directly models grammar rules. Cons: Can suffer from left recursion (e.g., $NP \rightarrow NP \ PP$) and backtracking , leading to inefficiency. 2. Bottom-Up Parsing: Approach: Starts from the input words (terminals) and tries to reduce them to higher-level grammatical categories (non-terminals) until the start symbol is reached. It builds constituents and combines them. Method: Builds the parse tree from the leaves upwards to the root. Example: Shift-Reduce Parsers, LR parsers (SLR, LALR, LR). Pros: Generally more efficient, handles a larger class of grammars than top-down. Cons: Can be less intuitive to design, errors are detected later. 3. Chart Parsing: Approach: A general parsing framework that can implement both top-down and bottom-up strategies. It uses a "chart" (a data structure, often a table or array) to store intermediate parsing results . Key Idea: Avoids redundant computations by storing and reusing parsed constituents. This makes it efficient for ambiguous grammars and languages. Example: Earley Parser, CYK Algorithm. Pros: Handles ambiguity well, efficient for ambiguous grammars, guaranteed to terminate. Cons: Can be more complex to implement than simpler parsers. Challenges in NLP Parsing Ambiguity: Natural language sentences are often highly ambiguous (lexical, syntactic, semantic). Coverage: Real-world language is vast and constantly evolving, making it hard to create a grammar that covers all valid sentences. Efficiency: Parsing complex sentences can be computationally intensive. Applications of AI Artificial Intelligence has permeated various aspects of modern life, transforming industries and improving daily experiences. Here are five significant applications: 1. Natural Language Processing (NLP): Description: Enables computers to understand, interpret, and generate human language. Examples: Virtual Assistants: Siri, Google Assistant, Alexa (speech recognition, natural language understanding). Machine Translation: Google Translate (translating text between languages). Spam Filtering: Identifying and filtering unwanted emails. Sentiment Analysis: Determining the emotional tone of text (e.g., customer reviews). 2. Computer Vision: Description: Allows computers to "see" and interpret visual information from images and videos. Examples: Facial Recognition: Unlocking phones, security systems. Object Detection: Identifying objects in images/videos (e.g., self-driving cars recognizing pedestrians, traffic signs). Medical Imaging Analysis: Detecting diseases from X-rays, MRIs. Augmented Reality: Overlaying digital information onto the real world. 3. Robotics: Description: Designing, building, operating, and applying robots to automate tasks, often combining AI with mechanical engineering. Examples: Industrial Robots: Assembly, welding, painting in manufacturing. Autonomous Vehicles: Self-driving cars, drones (perception, planning, control). Service Robots: Robot vacuum cleaners, surgical robots, delivery robots. Exploration Robots: Rovers on Mars, underwater drones. 4. Expert Systems / Decision Support Systems: Description: AI systems that emulate the decision-making ability of a human expert in a specific domain. Examples: Medical Diagnosis: Assisting doctors in identifying diseases (e.g., MYCIN). Financial Fraud Detection: Identifying suspicious transactions. Loan Approval Systems: Assessing creditworthiness. Configuration Systems: Helping users configure complex products. 5. Game Playing: Description: Developing AI agents that can play and often outperform human experts in various games. This drives research in search, planning, and reinforcement learning. Examples: Chess & Go: Deep Blue, AlphaGo demonstrating superhuman performance. Video Game AI: Non-player characters (NPCs) in video games. Poker AI: Libratus, Pluribus achieving expert-level play. Real-time Strategy Games: AI for Starcraft.