COSC343 Flashcards
The Agent Function
The agent function maps percepts (P) from the environment to actions (A). The agent program runs on the physical hardware to implement this function, determining how the agent responds to its environment.
Agent Environment Dimensions:
Fully Observable vs Partially Observable:
* Fully Observable: Agent has complete access to the relevant information.
* Partially Observable: Agent has limited or incomplete information.
Deterministic vs Stochastic:
* Deterministic: The next state is completely predictable.
* Stochastic: Outcomes have an element of randomness or uncertainty.
Episodic vs Sequential:
* Episodic: Agent’s actions are independent of past actions.
* Sequential: Current actions affect future actions or outcomes.
Offline vs Online:
* Offline: Decisions are made in advance, without interaction.
* Online: Agent interacts with the environment in real-time.
Discrete vs Continuous:
* Discrete: A finite number of distinct states or actions.
* Continuous: Infinite possibilities for states or actions.
Single-Agent vs Multi-Agent:
* Single-Agent: Only one agent interacts with the environment.
* Multi-Agent: Multiple agents interact, possibly competing or collaborating.
Types of Agents
Reflex Agents:
* Definition: Act based on current percepts using simple rules.
* Example: A basic thermostat adjusting temperature based on current readings.
Model-Based Agents:
* Definition: Use an internal model to understand the environment and past states.
* Example: A robot that remembers room layouts for efficient navigation.
Goal-Based Agents:
* Definition: Make decisions to achieve specific goals, planning actions accordingly.
* Example: A navigation app that finds the shortest route to a destination.
Utility-Based Agents:
* Definition: Optimize decisions based on the utility or value of outcomes.
* Example: An investment bot that selects stocks to maximize returns.
Learning Agents:
* Definition: Improve performance over time by learning from past experiences.
* Example: A self-driving car that enhances its driving skills through accumulated data.
Social Agents:
* Definition: Interact with other agents in a collaborative or competitive manner.
* Example: Online trading bots that compete for the best prices in the market.
Search Strategies (Breadth vs Depth, Depth-limited, Iterative-deepening)
Q-Card: Search Algorithms
____________________________________________
Breadth-First Search (BFS):
* Definition: Explores all nodes at the present depth before moving on to nodes at the next depth level.
Characteristics:
* Uses a queue to keep track of nodes.
* Guaranteed to find the shortest path in unweighted graphs.
* Memory-intensive; stores all nodes at the current level.
Example: Finding the shortest route on a map.
____________________________________________
Depth-First Search (DFS):
Definition: Explores as far down a branch as possible before backtracking.
Characteristics:
* Uses a stack (or recursion) to keep track of nodes.
* Can be more memory efficient than BFS.
* May not find the shortest path; can get stuck in deep branches.
Example: Solving a maze by going down one path until a dead end.
____________________________________________
Depth-Limited Search:
Definition: A variation of DFS that limits the depth to which it can explore.
Characteristics:
* Prevents infinite loops in deep or infinite spaces.
* Useful when the maximum depth is known.
* If the goal is beyond the depth limit, it will not be found.
Example: Searching a game tree with a maximum depth to evaluate moves.
____________________________________________
Iterative Deepening:
Definition: Combines the benefits of DFS and BFS by exploring depth-first with increasing depth limits.
Characteristics:
* Uses depth-limited search in a loop, incrementing the depth limit each iteration.
* Finds the shortest path in an unweighted graph like BFS.
* More memory-efficient than BFS; uses linear space.
Example: Searching a large graph where the depth of the solution is unknown.
What are the properties of Breadth-first search, Depth-frst and Depth-limited search?
Breadth-First Search (BFS)
- Definitions:
- b = maximum branching factor
- d = depth of the least-cost solution
- m = maximum depth of the state space
- Complete? Yes (if b is finite)
- Time Complexity: O(b^(d+1)) (exponential in d)
- Space Complexity: O(b^(d+1))
- Optimal? Yes (if cost = 1 per step); not optimal in general.
- Key Point: Space is a significant issue.
____________________________________________
Depth-First Search (DFS)
- Definitions:
- b = maximum branching factor
- d = depth of the least-cost solution
- m = maximum depth of the state space
- Complete? No (fails in infinite-depth spaces)
- Time Complexity: O(b^m) (poor performance if m is much larger than d)
- Space Complexity: O(b^m) (linear space)
- Optimal? No
- Key Point: Lack of optimality can be problematic.
____________________________________________
Depth-Limited Search
- Complete? Yes, if l >= d; otherwise, No (l = depth limit)
- Time Complexity: O(b^l)
- Space Complexity: O(b^l)
- Optimal? No
____________________________________________
Iterative Deepening
- Definition: Combines the benefits of DFS and BFS by exploring depth-first with increasing depth limits.
- Complete? Yes
- Time Complexity: O(b^d)
- Space Complexity: O(b^d)
- Optimal? Yes (if cost = 1 per step); not optimal in general.
completeness—does it always find a solution if one exists?
time complexity—number of nodes generated/expanded
space complexity—maximum number of nodes in memory
optimality—does it always find a least-cost solution?
Tree Search vs. Graph Search
____________________________________________
#### Tree Search
- Definition: A search strategy that explores nodes in a tree structure.
- Key Notes:
- Assumes no repeated states; each node is unique.
- Can generate an infinite number of nodes due to branching.
- Suitable for problems with a well-defined structure (e.g., decision trees).
- May result in inefficient searches if solutions are deep in the tree.
____________________________________________
#### Graph Search
- Definition: A search strategy that explores nodes in a graph structure.
- Key Notes:
- Tracks visited nodes to avoid cycles and repeated states.
- Handles more complex relationships, including cycles and multiple paths.
- More efficient in scenarios where states may be revisited.
- Can find optimal paths in weighted graphs when used with appropriate algorithms.
____________________________________________
#### Key Differences:
- Repetition: Tree search does not account for repeated states, while graph search does.
- Structure: Tree search is for hierarchical structures, whereas graph search handles more complex interconnections.
- Efficiency: Graph search is generally more efficient in terms of space and time when dealing with cycles and redundancy.
Q-Card: Uniform-Cost Search
Graph search algorithm that expands the least-cost node first, ensuring it finds the optimal solution by considering the cumulative cost to reach each node while maintaining completeness and optimality when all step costs are greater than zero.
Definitions
- b = maximum branching factor
- ε = smallest step cost (must be > 0)
- C* = cost of the optimal solution
Properties
- Complete? Yes, if action cost is always greater than zero.
- Time Complexity: O(b^(C/ε)), where the number of nodes with g(n) ≤ C.
- Space Complexity: O(b^(C/ε)), where the number of nodes with g(n) ≤ C.
- Optimal? Yes – nodes are expanded in increasing order of g(n).
Key Points
- Uniform-cost search is a form of graph search that finds the least-cost path to the goal.
- It considers the cumulative cost to reach each node, ensuring the optimal solution is found.
Q-Card: Greedy Search
Definitions
- b = maximum branching factor of the search tree
- d = depth of the least-cost solution
- m = maximum depth of the state space
Properties
- Complete? Yes in finite space with repeated-state checking; otherwise, it might get stuck in loops.
- Time Complexity: O(b^m), but a good heuristic can lead to dramatic improvements.
- Space Complexity: O(b^m) — keeps all nodes in memory.
- Optimal? No; does not guarantee the shortest path.
Key Points
- Greedy Search uses heuristics to prioritize nodes based on their estimated cost to reach the goal.
- It can be efficient in terms of time with effective heuristics, but it may not always find the optimal solution or complete the search in cyclic spaces.
A* Search
A* Search is an informed search algorithm that combines the strengths of Uniform-Cost Search and Greedy Search by utilizing an admissible or consistent heuristic to efficiently find the optimal path to the goal while ensuring completeness
Definitions
- d = depth of the least-cost solution
- C* = cost of the optimal solution
- K = a constant
Properties
- Complete? Yes, unless there are infinitely many nodes with f(n) ≤ C, where C is the optimal cost of reaching the goal state.
- Time Complexity: Exponential in the length of the solution, O(K^d), where K is some constant.
- Space Complexity: Keeps all nodes in memory, O(K^d).
- Optimal? Yes, if:
- The heuristic used is admissible in tree search.
- The heuristic used is consistent in graph search.
Key Points
- A* Search combines the benefits of both Uniform-Cost Search and Greedy Search by using a heuristic to estimate the total cost from the start to the goal.
- It is designed to find the least-cost path to the goal while maintaining completeness and optimality under specific heuristic conditions.
Consistent vs. Admissible Heuristics
Definitions
- Admissible Heuristic: A heuristic that never overestimates the true cost to reach the goal from a given node. It ensures that the estimated cost is always less than or equal to the actual cost.
-
Consistent Heuristic (also known as Monotonic): A heuristic that satisfies the triangle inequality, meaning the estimated cost from node A to the goal (h(A)) is less than or equal to the cost from A to a neighbor B (c(A, B)) plus the estimated cost from B to the goal (h(B)):
h(A) ≤ c(A, B) + h(B)
Key Differences
- Optimality:
- Admissible: Guarantees optimal solutions in A* search.
- Consistent: Guarantees both optimality and efficiency in A* search.
-
Behavior:
- Admissible: Can allow for non-consistent heuristics, which may lead to suboptimal performance.
- Consistent: Always maintains non-decreasing costs and is therefore less likely to revisit nodes.
-
Example:
- Admissible: A heuristic that estimates straight-line distance to the goal.
- Consistent: A heuristic that estimates distance considering the actual path costs.
Key Points
- A consistent heuristic is always admissible, but not all admissible heuristics are consistent.
- Using a consistent heuristic can lead to more efficient search as it reduces the need to revisit nodes, improving performance in algorithms like A*.
Optimality of A* Search
Definitions
- Tree Search: A search method that does not check for repeated states.
- Graph Search: A search method that avoids adding nodes to the fringe if their state has already been encountered (i.e., not on the closed list).
Optimality in A:
- Tree Search:
- If A tree search uses an admissible heuristic, it is provably optimal; it is guaranteed to find the shortest path to the solution first.
-
Graph Search:
- If A* graph search uses a consistent heuristic, it is provably optimal.
- A consistent heuristic ensures nodes are expanded in non-decreasing order of f(n), meaning when the goal node is first expanded, it must be on the optimal path.
Key Points
- Admissible heuristics allow A* in tree search to guarantee optimal solutions without revisiting states.
- Consistent heuristics enhance A* in graph search by ensuring optimality while efficiently managing node expansions.
MinMax Algorithm
Q-Card: Minimax Algorithm
Core Aspects
-
Purpose:
- Used for two-player, turn-based games to minimize loss while maximizing gain.
-
Players:
- Maximizer: Tries to maximize score.
- Minimizer: Opponent trying to minimize Maximizer’s score.
-
Game Tree:
- Explores moves in a tree structure.
- Maximizer picks the highest value; Minimizer picks the lowest.
-
Recursive Evaluation:
- Recursively evaluates possible moves until a terminal state (win/loss/draw) is reached.
-
Optimal Play:
- Assumes both players play optimally, ensuring the best move for the Maximizer.
Key Points
- Time: O(b^m), where b is branching factor, m is depth.
- Optimal, but computationally expensive; improved with Alpha-Beta Pruning.
Alpha-Beta Pruning
Core Aspects
-
Purpose:
- Improves the efficiency of the Minimax algorithm by skipping branches that won’t affect the final decision.
-
How It Works:
- Alpha (α): Represents the best score the Maximizer can achieve so far. Updated as higher values are found.
- Beta (β): Represents the best score the Minimizer can achieve so far. Updated as lower values are found.
- As the algorithm explores the game tree, if it finds a node where:
- Maximizer’s move can’t improve its score (α ≥ β), or
-
Minimizer’s move can’t worsen its score (β ≤ α),
the algorithm stops exploring that branch (prunes it).
-
Pruning Process:
- During tree traversal, the current node’s value is compared with α and β.
- If further exploration of a branch cannot produce a better result than the best found so far, the branch is pruned (ignored).
-
Example:
- If the Maximizer already found a path with a score of 6 (α = 6), and during exploration the Minimizer can force a result of 4 (β = 4), that path is pruned because it won’t improve the Maximizer’s score.
-
Optimality:
- Even with pruning, the final result is the same as with regular Minimax, but it evaluates far fewer nodes.
Key Points
- Time Complexity: O(b^(m/2)) with perfect pruning—faster than regular Minimax.
- Prunes branches that cannot influence the final decision, significantly reducing the search space.
Purpose:
- Simulates biological evolution to solve optimization problems through a stochastic search over a state space.
How It Works:
- Representation: States are represented as chromosomes, often sequences of numbers or characters.
- Fitness Function: A numeric score that evaluates how well a chromosome solves the problem.
- Population: A set of chromosomes evaluated for fitness.
- Selection: Parents are selected based on fitness; fitter individuals have a higher chance of being chosen.
- Crossover: New offspring are created by combining parents’ chromosomes.
- Mutation: Random changes are introduced to offspring to maintain genetic diversity.
Algorithm Steps:
- Initialize a population with random chromosomes.
- Evaluate fitness for each chromosome.
- Select pairs of parents using methods like roulette wheel or tournament selection.
- Create offspring through crossover and apply mutation.
- Replace the old population with the new one.
- Repeat until a stopping condition is met (e.g., a certain fitness level).
Example:
- In the 8-queens problem, chromosomes represent arrangements of queens on a chessboard. The fitness function could evaluate the number of non-attacking pairs of queens.
Key Points:
- Diversity: Maintaining diversity in the population prevents premature convergence.
- Convergence: The algorithm converges to a solution over generations, ideally finding an optimal or near-optimal solution.
Parent Selection Methods for GA Algorithims
Purpose:
Selects parents for reproduction in a genetic algorithm to promote fitter individuals while maintaining diversity.
Roulette Wheel Selection:
- Fitness Summation: The fitness scores of all individuals in the population are summed.
- Normalization: Each individual’s fitness is normalized to sum to 1.
- Range Assignment: Each individual is assigned a range on a scale of [0, 1].
- Random Selection: A random number is generated between 0 and 1, selecting the individual corresponding to that range.
Tournament Selection:
- Random Subset: A subset of N individuals is randomly selected from the population.
- Fitness Comparison: The two individuals with the highest fitness from this subset are chosen as parents.
- Selection Process: This process can be repeated multiple times to select more pairs of parents.
Promotion of Fitter Individuals:
* In Roulette Wheel Selection, fitter individuals have larger ranges, increasing their chances of being selected.
* In Tournament Selection, fitter individuals are more likely to win the competition within the subset, enhancing their chances of reproduction.
Diversity Maintenance:
* Roulette Wheel Selection allows all individuals a chance to contribute, preserving genetic diversity.
* Tournament Selection can adjust the subset size (N) to control the selection pressure, allowing for some less fit individuals to remain in the population.
Crossover Operations in GA Algorithms
Purpose:
Combines genetic material from parent individuals to create offspring in a genetic algorithm.
Single-Point Crossover:
- A random crossover point is selected along the parent chromosomes.
- Genetic material is exchanged at this point, forming two new offspring.
- Example: If parents are (A1 A2 A3 | A4 A5) and (B1 B2 B3 | B4 B5), the offspring will be (A1 A2 A3 B4 B5) and (B1 B2 B3 A4 A5).
K-Point Crossover:
- Multiple crossover points (k) are selected randomly along the parent chromosomes.
- Segments between crossover points are swapped between parents.
- This allows for more complex combinations of genetic material.
- Example with k=2: If parents are (A1 A2 | A3 A4 | A5) and (B1 B2 | B3 B4 | B5), the offspring might be (A1 A2 B3 B4 A5) and (B1 B2 A3 A4 B5).
Uniform Crossover:
- Each gene (or position in the chromosome) is considered independently.
- For each gene, a random decision is made whether to take it from the first parent or the second.
- This creates high variability in offspring and can preserve diverse genetic traits.
- Example: If parent genes are (A1 A2 A3 A4) and (B1 B2 B3 B4), a uniform crossover might yield (A1 B2 A3 B4) and (B1 A2 B3 A4).
Key Points:
- Crossover operations are crucial for combining desirable traits from parents.
- They help explore the solution space and maintain genetic diversity within the population.
Discrete vs Continuous Random Variables
Discrete Variables
- Definition: Discrete random variables can take on a countable number of distinct values. Examples include the number of students in a class, the outcome of rolling a die, or the number of cars in a parking lot.
- Probability Distribution Function: For discrete variables, the probability distribution function (PDF) gives the probability of each possible value. The sum of all probabilities for the possible outcomes equals 1.
-
Example:
- Consider rolling a six-sided die. The possible outcomes are 1, 2, 3, 4, 5, and 6.
- The probability of rolling each number is 1/6.
- The total probability is 1/6 + 1/6 + 1/6 + 1/6 + 1/6 + 1/6 = 1.
Continuous Variables
- Definition: Continuous random variables can take on an infinite number of values within a given range. Examples include height, weight, and temperature.
- Probability Density Function: For continuous variables, the probability density function describes the likelihood of the variable falling within a particular range of values. Unlike discrete variables, we do not assign probabilities to specific values; instead, we find the probability that the variable falls within a range by integrating the density function over that range.
-
Example:
- Consider a variable representing the height of adults in a population.
- The height can be any value within a range (e.g., between 150 cm and 200 cm).
- To find the probability that a randomly chosen adult is between 170 cm and 180 cm, you would calculate the area under the probability density function curve between these two heights.
- This area represents the probability of selecting an individual within that height range, and the total area under the curve equals 1.
Q-Card: Events from Multiple Random Variables
- Overview: Evaluating probabilities based on multiple random variables is common in probability theory.
-
Key Concepts:
- P(X = x, Y = y): Probability that random variable X equals x and random variable Y equals y.
- P(X = x or Y = y): Probability that either random variable X equals x or random variable Y equals y.
-
Example: Double Dice Roll:
- Let X be the result of the first die and Y be the result of the second die.
- Questions to consider:
- What is P(X = 3, Y = 4)?
- What is P(X = 3 or Y = 3)?
- What is P(X is even and Y is even)?
- What is P(X is even or Y is even)?
- Joint Distribution: A distribution function over two or more random variables is called a joint distribution, often denoted as P(X, Y).
Example: Double Dice Roll Answers
-
What is P(X = 3, Y = 4)?
- There is only one combination that results in X = 3 and Y = 4 (i.e., the first die shows 3 and the second die shows 4).
- The total possible outcomes when rolling two dice is 6 × 6 = 36.
- So, P(X = 3, Y = 4) = 1/36.
-
What is P(X = 3 or Y = 3)?
- To find this, calculate the probabilities for each scenario:
- P(X = 3): Outcomes are (3,1), (3,2), (3,3), (3,4), (3,5), (3,6) → 6 outcomes.
- P(Y = 3): Outcomes are (1,3), (2,3), (3,3), (4,3), (5,3), (6,3) → 6 outcomes.
- However, (3,3) is counted twice, so we subtract it once.
- Therefore:
- P(X = 3) = 6/36
- P(Y = 3) = 6/36
- Thus, P(X = 3 or Y = 3) = P(X = 3) + P(Y = 3) - P(X = 3, Y = 3)
- P(X = 3 or Y = 3) = 6/36 + 6/36 - 1/36 = 11/36.
- To find this, calculate the probabilities for each scenario:
-
What is P(X is even and Y is even)?
- The even outcomes for a single die are 2, 4, and 6.
- Possible combinations for (X, Y) are: (2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6) → 9 outcomes.
- So, P(X is even and Y is even) = 9/36 = 1/4.
-
What is P(X is even or Y is even)?
- Calculate the probabilities:
- Total outcomes for X being even: 18 outcomes.
- Total outcomes for Y being even: 18 outcomes.
- Outcomes where both are even: 9.
- Thus:
- P(X is even) = 18/36
- P(Y is even) = 18/36
- P(X is even or Y is even) = P(X is even) + P(Y is even) - P(X is even and Y is even)
- P(X is even or Y is even) = 18/36 + 18/36 - 9/36 = 27/36 = 3/4.
- Calculate the probabilities:
Summary of Answers:
1. P(X = 3, Y = 4) = 1/36
2. P(X = 3 or Y = 3) = 11/36
3. P(X is even and Y is even) = 1/4
4. P(X is even or Y is even) = 3/4
Example: Dental assistant cont’d
Suppose a patient reported toothache, but the probe did not catch. Should the agent recommend an x-ray or be sent home with advice to brush with Sensodyne? Given that a particular nurse’s track record is ¬catch on 50% of patients with toothache, should the agent recommend more training?
Probabilities:
Toothache:
Cavity & Catch: 0.108
Cavity & ¬Catch: 0.072
¬Cavity & Catch: 0.016
¬Cavity & ¬Catch: 0.144
¬Toothache:
Cavity & Catch: 0.012
Cavity & ¬Catch: 0.008
¬Cavity & Catch: 0.064
¬Cavity & ¬Catch: 0.576
P(cavity|toothache,¬catch) = ?
P(¬catch|toothache) = ?
P(cavity|toothache,¬catch) = P(cavity, toothache,¬catch)/P(cavity|toothache) = (0.012)/(0.012 + 0.064) = 0.1578
P (¬catch|toothache) = P(¬catch|toothache)/P(toothache) = (0.012+0.064) / (0.012+0.064+0.108+0.016) = 0.38
Bayesion Probability – Screening Test
Effectiveness of a test:
Test result is positive given person is sick
* P(+ve|sick) = 0.95
* ^ True Positive
Test result is negative given person is not sick
* P(-ve|¬sick) = 0.96
* ^ True Negative
Given a randomly selected person from the population, what is the probability P(sick|+ve)
(What is the probability a person is sick, given a postitive test)
We cannot know the probability, we also need a belief (estimation) of population that is sick.
P(+ve|¬sick) = 0.04
^ False Positive (Probability of a person testing positive given not sick).
With the additional info 1% of 5M (50K) is actually sick.
Then the probability of a randomly selected person testing positive given sick is - P(sick|+ve):
47.5k / (47.5k + 198k)
Info:
* True Positives (47.5k): People who tested positive and are actually sick.
* False Positives (198k): People who tested positive but are not sick.
If you divide 47.5k by the sum 47.5k + 198k, you’ll get the probability P(sick | +ve). This approach directly uses the counts of true positives and false positives rather than working with probabilities.
What is Bayes’ rule?
From the definition of conditional probability:
* P(b|a) = P(a,b)/P(a) and P(a|b) = P(a,b)/P(b)
It follows:
P(a,b) = P(b|a)P(a) = P(a|b)P(b)
And so:
P(a|b) = P(b|a)P(a) / P(b)
