Week 2

Question 1

make sure you know the answers

Question 2

What is an Expert system? give an example

Answer 2

=symbolic AI
emulates the decision-making ability of a human expert. By applying knowledge and inference rules

Question 3

symbolic AI –>expert systems–>forward chaining

How would forward chaining solve this classification problem?

Answer 3

Forward chaining starts with the available data and uses inference rules to extract more data (in the form of conclusions or actions) until a goal is reached

Question 4

symbolic AI –>expert systems–>backward chaining

how does backward chaining work? Give an example

Answer 4

Backward chaining starts with a list of goals and works backwards to determine what data must be true to achieve those goals.

Example
Goal: Determine why the computer won’t start.
Rule 1: If the computer won’t start, then possible causes are power supply failure, corrupted system files, or hardware failure.
The system then works backwards by checking each possibility:
It first asks if the power supply is functional.
If yes, it checks for system file integrity.
If system files are intact, it then considers hardware failure.
The system continues this process until it finds the specific cause.

Question 5

when would you use backward chaining and when forward chaining?

Answer 5

Backward chaining is well-suited for diagnostic problems where the goal (conclusion) is known, but the path to reach it is not

Forward chaining is ideal in situations where all relevant data is available upfront, and the goal is to deduce all the conclusions that can be derived from that data.

Question 6

What is backtracking? give an example. What is brute force?

Answer 6

• uses trial and error.
• It’s a type of depth-first search that attempts to construct a solution incrementally. When it encounters a step where no progress can be made (a dead end), it backtracks to the previous step and tries another path. This continues until a solution is found or all possibilities are exhausted.
• it is a good option compaired to brute force (go through every option from the start)

example
Imagine you’re trying to solve a maze. You start at the entrance and come to a junction where you must choose which way to go. You pick a direction and continue until you reach a dead end or the exit. If you hit a dead end, you backtrack to the last junction and try a different path. This process repeats until you find the exit or conclude that there’s no exit.

Question 7

basic search–>depth-first search

what is depth-first search (DFS)?

Answer 7

Purpose: DFS is primarily used for traversal or searching in a graph or tree. It aims to explore all nodes and edges to achieve comprehensive traversal.
Process: DFS starts at a root node and explores as far as possible along each branch before backtracking.

Question 8

basic search: breadth-first search

what is breadth-first search? when is it used?

Answer 8

BFS is ideal for finding the shortest path on unweighted graphs. Since it explores all neighbors at the current depth before moving to the next level, it guarantees the shortest path when the edges have the same weight or no weight.

Question 9

when is depth-first search prefered and when is breadth first search prefered?

Answer 9

Question 10

What is the Hill Climbing algorithm in search?

Answer 10

• Hill Climbing is a heuristic search strategy that starts with an arbitrary solution and iteratively makes incremental improvements. It ‘climbs’ towards a better solution by selecting the neighboring state with the highest value and stops when no higher value is found.
• It is DFS with preference

e.g.

1. Start at a Random Point: You begin at a random location on the landscape.
2. Evaluate Neighboring Points: From your current location, you examine neighboring points (nearby locations) to see if they are higher than your current point.
3. Move to the Highest Neighbor: If a neighboring point is higher than your current point, you move to that point. This is analogous to climbing uphill.
4. Repeat Until No Higher Neighbor is Found: You continue this process, always moving to a higher neighboring point if one exists. If you reach a point where no neighboring points are higher, you stop.
5. Solution: The point where you stop is considered the “peak” or the optimal solution by the algorithm.

Question 11

what is a greedy algorithm?

Answer 11

Algorithms that choose the locally optimal choice at each stage are known as greedy algorithms. (eg. hill climbing)

Question 12

basic search–>beam search

regarding beam search algorithm give:
* approach
* goal
* context
* example system
* greedy or not?

Answer 12

• breadth-first search but only the knodes that qualify according the predifined terms are further investigated.
• Goal: Fast good enough solutions
• context: very large space
• e.g.: LLM
• greedy algorithm

Question 13

optimal search–>branch and bound

describe the branch and bound search.
* how does it work?
* goal
* greedy or not?

Answer 13

1. Branching: The algorithm starts with a set of candidate solutions and then systematically divides them into smaller subsets (branches). (nodes in search tree)
2. Bounding: For each subset, the algorithm calculates bounds (upper or lower limits, depending on whether it’s a maximization or minimization problem) on the objective function. These bounds are used to estimate the best possible solution within that subset.
3. Pruning: If the bound of a subset indicates that it cannot possibly contain a better solution than the best one found so far, that subset (branch) is discarded or “pruned” from the search. This step is crucial as it significantly reduces the number of subsets that need to be examined.
4. Exploration and Optimization: The algorithm explores the remaining branches, further subdividing them and applying the bounding and pruning steps. This process continues until the best solution is found or until all branches are pruned.
   * goal: optimal solution
   * not greedy

Question 14

optimal search–>heuristic branch-and-bound

what is heuristic branch-and-bound? what is an advantage compared to the traditional one?

Answer 14

branch and bound, but
* Heuristic functions are used to evaluate the potential of each branch. (After step 2 bounds) These functions provide an educated guess or estimation of how close a particular branch or solution is to the optimal solution, based on available information and problem-specific knowledge.
* reducing the search space and computation time compared to traditional Branch and Bound.

Question 15

what is A* procedure?

Answer 15

Question 16

what is adversarial search?

Answer 16

adversarial=competitive

a method used in artificial intelligence to solve games or problems where two or more agents are in competition. Its function is to find the best move in a given situation by considering the strategies of opposing agents.

this allows for perfect play: the behavior or strategy of a player that leads to the best possible outcome for that player regardles of the response by the opponent.

Question 17

adversarial search applies the alpha-beta principle what does this mean?

Answer 17