Title: AI
Tags: Search_Algorithms Constraint_Satisfaction_Problems What_is_AI? Advanced_Search_and_Local_Search Learning_from_Examples_and_Decision_Trees Neural_Networks Deep_Learning_and_Advanced_Natural_Networks Intelligent_Agents Rationality_in_AI

Q: Strong AI
A: Human-like cognitive abilities (understand, reason, learn)

Q: Weak AI
A: specific tasks (image recognition, speech processing)

Q: Think Humanly
A: model human thinking

Q: Think Rationally
A: decisions based on formal logic and reasoning

Q: Act Humanly
A: Mimicking human behaviour (Turing Test)

Q: Act Rationally
A: Maximise goal achievement

Q: Turing Test
A: Determine if a machine can exhibit behaviour indistinguishable for a human

Q: Weak vs Strong AI
A: Weak: for specific task
Strong: perform any cognitive task as well as a human

Q: Components of an Agent
A: Sensors: Preceive the environment (camera, microphone)
Actuators: Take action (motor, display)
Agent Functions: Map percept histories to actions

Q: Agent Types
A: Simple Reflex Agents: act solely based on current percept
Model-Based Reflex Agents: Keep track of the world´s state and update this information as new percepts arrive
Goal-Based Agents: Consider future actions to achieve specific goals
Utility-Based Agents: Make decisions to maximise some utility function (measure of success)

Q: What is Rationality in AI?
A: A rational agent is one that selects actions that are expected to maximize its performance measure, based on its percept history and built-in knowledge.

Q: Rationality in AI - 3 Key Considerations
A: Performance Measure: A way to evaluate how well an agent is performing its task
Rationality != Omniscence (Allwissenheit): Rational agents do the best they can given what they know, but they do not need to be perfect.
Autonomy: The more an agent relies on its own expertice (rather than prior knowledge), the more autonomous it is.

Q: 4 Strucural Elements of Search Algorithms
A: Initial state: The starting point of the search
Successor function: A function that lists possible actions and the resulting states
Goal test: A test to determine if the current state satisfies the goal
Path cost: The cost of a path from the initial state to the current state.

Q: 4 Uninformed (Blind) Search Strategies
A: ... use no additional information about the goal (no heuristics) except the information provided in the problem definition
Breath-First Search BFS
Depth-First Search DFS
Depth-Limited Search DLS
Iterative Deepening Search IDS

Q: Breath-First Search (Complete? Optimal? Time complexity? Space complexity?)
A: Explores all nodes at the present depth level before moving on to nodes at the next depth level.
Complete: Yes (if the branching factor is finite)
Optimal: Yes (if all step costs are equal)
Time Complexity: O(b^d) b = branching factor, d = depth of shallowest solution
Space Complexity: O(b^d) stores all nodes in memory
Suitable for finding the shortest path in uniform-cost problems.

Q: Depth-First Search (Complete? Optimal? Time complexity? Space complexity?)
A: Explores as far down a branch as possible before backtracking.
Complete: No (can get stuck in infinite loop in cyclic graph)
Optimal: No (does not guarantee the shortest path)
Time complexity: O(b^m) b = branching factor, m = maximum depth of search tree
Space complecity: O(b*m) only needs to store current path
Memory efficient but not optimal.

Q: Depth-Limited Search (Complete? Optimal?)
A: DFS with a pre-set depth limit to avoid infinite loops.
Complete: Yes (if solution is within the depth limit)
Optimal: No (does not guarantee shortest path)
Used when depth of solution is known.

Q: Iterative Deepening Search (Complete? Optimal? Time complexity? Space complexity?)
A: Combines the benefits of DFS and BFS by gradually increasing the depth limit until the solution is found.
Complete: Yes
Optimal: Yes (if the costs are uniform)
Time complexity: O(b^d)
Space complexity: O(b*d)
Combines benefits of BFS and DFS.

Q: Informed (Heuristic) Search Strategies - 2 Examples
A: Informed search algorithms use domain-specific information (heuristics) to guide the search.
Greedy Best-First Search
A* Search

Q: Greedy Best-First Search (Complete? Optimal? Time complexity? Space complexity?)
A: Expands the node that appears to be closest to the goal, according to a heuristic function h(n) (an estimate of the cost to reach the goal from node n).
Complete: No (can get stuck in loops)
Optimal: No (it focuses only on the heuristic, ignoring the cost to reach the current state)
Time complexity: O(b^m) m = maximum depth
Space complexity: O(b^m)
Can be faster but may find suboptimal solutions.

Q: A* Search  (Complete? Optimal? Time complexity? Space complexity?)
A: Uses both the path cost g(n) (cost to reach the current state) and the heuristic h(n) (estimated cost to reach the goal). The evaluation function is f(n) = g(n) + h(n).
Complete: Yes
Optimal: Yes (if heuristic is admissable)
Time complexity: Exponential, but more efficiant than uninformed search
Space complexity: O(b^d) stores all explored nodes
Admissable Heuristic: If it never overestimates the cost to reach the goal. (e.g. straight line distance between cities are always less than road distance therefore this would be an admissable heuristic)
Most efficient for optimal solutions with admissible heuristics.

Q: What are Constraint Satisfaction Problems? (CSPs)
A: A Constraint Satisfaction Problem is a type of problem where the goal is to find a solution that satisfies a number of constraints or limitations.

Q: CSP Structure and Example
A: Variables: A set of variables [x1, x2, ..., xn]
Domains: Each vraiable xi has a domain of possible values [d1, d2, ..., dn]
Constraints: A set of constraints restricts the values to that the variables can simultaneously take.
Example:
Map-coloring problem: You are given a map where each region must be colored with one of three colors (red, green, blue), and adjacent regions cannot have the same color​.

Q: CSP Terminology - 4 Terms (3 types of assignment)
A: Assignment: A partucular assignment of values to some or all variables
Consistent Assignment: An assignment that does not violate any constraints.
Complete Assignment: An assignment where every variable has a values.
Solution: A complete, consistent assignment that satisfies all the constraints.

Q: Types of Constraints, Constraint Graph
A: Unary Constraint: single variable (x != 5)
Binary Constraints: pair of variables (x != y)
Higher-order Constraints: three or more variables
Constraint Graph:
Nodes represent variables
Edges represent constraints between pairs of variables

Q: Solving CSPs - Backtracking Search
A: Backtracking is a depth-first search that assigns values to variables, trying to build a complete solution incrementally. When a partial assignment violates a constraint, the algorithm backtracks to try a different assignment.
Steps:
1. Assign value to variable
2. Check if assignment is consistent with constraints
3. If consistent move to next variable, if not backtrack and try different value
Simple but may be inefficient if many variables are involved.

Q: Solving CSPs - Constraint Propagation
A: Forward Checking: After assigning a value to a variable, eliminate values from the domains of unassigned variables that conflict with the assignment. This reduces the number of future options and helps prevent future conflicts​.
Arc Consistency: Focuses on binary constraints between two variables.

Q: Solving CSPs - 3 Heuristics
A: Minimum Remaining Values: Choose the variable with the fewest remaining legal values to assign next.
Degree Heuristic: Choose the variable involved in the largest numer of constraints on unassigned variables.
Least Constraining Value: Choos the value that leaves most options open for other variables.

Q: CSP Complexity
A: CSPs are often NP-complete. (Finding a solution can be computationally expensive)
However, for many practical problems, constraint propagation and heuristics can greatly reduce the search space and computation time.

Q: What are Local Search Algorihms? 3 Features, Example
A: Local search algorithms focus on optimizing a single current state and moving to neightboring states rathern than systematically exploring the eintire search tree.
These methods are particularly useful for problems where the path to the solution is irrelevant and only the solution itself matters. (travelling salesperson problem)
Features:
State space: possible solutions
Neighbors: neighbouring state is obtained by makeing small modifications to current state
Evaluation function: quality or fitness of state
Example Problem: The n-queens problem, where the goal is to place n queens on an n × n chessboard so that no two queens threaten each other. Local search would start with a complete but flawed arrangement and iteratively improve the arrangement by reducing conflicts​.

Q: Hill Climbing Algorithm (Variants, Challenges, Solutions)
A: Hill climbing is a greedy local search algorithm that continuously moves toward the goal by selecting the neighbor with the best evaluation score. The algorithm stops when it reaches a state where no better neighbors exist.
Variants:
Simple hill climbing: Choose first neighbour that improves the current state
Steepest ascent hill climbing: Evaluates all neighbours and move tho the best one
Sochastic hill climbing: Choose ranomly among the better neighbours
Challenges:
Local maxima
Pleatus
Ridges
Solutions:
Random restart hill climbing: Perform multiple hill-climbing searches from randomly selected initial states. Guaranteed to find global maximum if allowed enough time.

Q: Simulated Annealing (Concepts, Properties, Example)
A: Simulated annealing is a probabilistic technique for exploring the search space that allows occasional moves to worse states to escape local maxima.
Concepts:
Temperature parameter (T): Controls the probability of accepting worse moves. Initialiy the temperature is high (allowing many bad moves) but gradually decreases.
Cooling schedule: Defines how the temperature decreases over time.
Properties:
Complete: Given enough time, simulated annealing is complete and can find a global optimum.
Optimal: It is not guaranteed to find the optimal solution, but the likelihood improves with a slow cooling schedule.

Q: Local Beam Search (What it is, differences from Hill Climbing), Stochastic Beam Search
A: Local beam search keeps track of k states instead of just one and generates all possible successors from these states. It then selects the k best successors from the generated states to continue the search.
Differences from Hill Climbing:
Keeps multiple states in mind
Diversification helps avoid local maxima
Stochastic Beam Search: Instead of choosing the best k successors, stochastic beam search chooses successors randomly, with a preference for better ones. This introduces randomness to avoid premature convergence​.

Q: Genetic Algorithms (Components)
A: A genetic algorithm (GA) is an optimization algorithm inspired by the process of natural selection. It works with a population of solutions, using genetic operators like selection, crossover, and mutation to evolve better solutions over time.
Components:
Population: A set of possible solutions (individuals)
Fitness function: The quality of an individual
Selection: Individuals are selected based on their fitness
Crossover: Two selected individuals (parents) are combined to produce new individuals (offspring)
Mutation: Random modifications are applied to individuals to maintain diversity in the population

Q: 3 Applications of Local Search
A: Travelling Salesperson Problem: Minimize the total distance traveled while visiting a set of cities exactly once and returning to the starting point.
n-Queens Problem: Place n queens on an n × n chessboard so that no two queens threaten each other.
Job Scheduling: Assign tasks to machines in such a way that total processing time is minimized.

Q: Learning from Examples (Description, Concepts)
A: Learning from examples is a form of inductive learning, where an AI system generalizes from specific examples to learn patterns or rules. This is a critical aspect of supervised learning, where the system is trained using labeled data.
Concepts:
Hypothesis space: the set of all possible models that can be learned from the data
Training data: Examples provided to the algorithm, including both the input and correct output (label)
Supervised learning: learning a function that maps input data (features) to an output (label) based on labeled training data
Example:
Suppose you are training a model to classify whether an email is spam or not. You provide the model with many emails, each labeled as "spam" or "not spam," and the model learns to generalize patterns based on features like the presence of certain keywords.

Q: Decision Tree Learning (Description, Strucure)
A: A decision tree is a tree-like model used to make decisions based on a series of questions (tests). Each internal node represents a test on an attribute, each branch represents the outcome of the test, and each leaf node represents a class label (decision).
Structure:
Root: top node where the first test is applied
Intenral nodes: tests on attributes
Leaf nodes: Final classification or deicsions

Q: Inductive Learning and Hypothesis Space - 3 Concepts
A: In inductive learning, the goal is to find a hypothesis from the hypothesis space that fits the training data well.
Concepts:
Hypothesis space: The set of all possible hypotheses the algorithm can choose from
Generalization: The ability of a model to perform well on unseen data, not just the training data
Bias-variance tradeoff: A balance between how well a model fits the training data (low bias) and how well it generalizes to new data (low variance)

Q: Information Gain and Entropy
A: Information gain measures how well a given attribute separates the training examples according to their target classification. It is used to decide which attribute to split on at each step of building a decision tree.
Entropy (H): A measure of the uncertainty or impurity in a dataset.
Information Gain (IG): The difference in entropy before and after splitting the data on an attribute.
Example: In a decision tree for classifying animals, you might start with an attribute like "Does the animal have feathers?" If this attribute splits the data perfectly (e.g., birds vs. non-birds), it will have high information gain.

Q: Handling Overfitting in Decision Trees
A: Overfitting occurs when a model is too complex and fits the noise in the training data rather than generalizing well to unseen data.
Preventation methods:
Pruning: Simplify the tree by removeing branches that do not provide significant poewr in classification. (This can be done using techniques such as reduced-error pruning or cost-complexity pruning)
Limit the tree depth: Setting a maximum depth for the decision tree to control its complexity.
Use a validation set: Splitting the data into trianing and validation sets and using the validation set to guide decisions on when to stop growing a tree.

Q: Alternative Hypotheses and Model Selection
A: When learning from examples, multiple hypotheses may fit the data. The challenge is to choose the hypothesis that generalizes best to unseen data. This involves model selection.
Cross-Validation:
A method to evaluate a model's performance by dividing the data into multiple subsets (folds), training the model on some folds, and testing it on the remaining fold(s). Common methods include k-fold cross-validation and leave-one-out cross-validation.

Q: Neural Networks (Description, Concepts)
A: Neural Networks are a set of algorithms modeled loosely after the human brain that are designed to recognize patterns. They are used for both supervised and unsupervised learning tasks, such as classification, regression, and clustering.
Concepts:
Neuron (node): Basic unit of a neural network. A neuron receives inputs, processes them and produces an output based on an activation function.
Layers: Neural networks consist of layers of neurons:
- Input Layer: Receives the raw input data
- Hidden Layers: Layers between the input and output layers, where computations take place
- Output Layer: Produces the final prediction or classification
Weights: Each connection between neurons has a weight that determins the importance of the input value
Bias: additional parameter that allows the model to shift the activation function

Q: Activation Functions, 4 Examples
A: Activation functions introduce non-linearities into neural networks, allowing them to model complex relationships.
Sigmoid: Output is between 0 and 1. Useful for binary classification.
Tanh: Output is between -1 and 1, and its zero-centered.
ReLU (Rectified Linear Unit): Most popular in modern neural networks, introduces sparsity where som neurons are turned off if they receive negative input.
Softmax: Converts a vector of values into probabilities, often used in the outer layer for multi-class classification problems:

Q: Feedforward Neural Networks
A: A Feedforward Neural Network is the simplest type of artificial neural network. In this network, the information moves only in one direction—from the input nodes, through the hidden nodes, and to the output nodes. There are no cycles or loops in the network.
Mathematical Representation:
For a given layer, the output is calculated as:
where:
- W is the weight matrix,
- a is the activation from the previous layer,
- b is the bias vector,
- f is the activation function

Q: Training Neural Networks (Steps of backpropagation)
A: Neural networks are trained using backpropagation, a process that minimizes the error by adjusting the weights and biases.
Steps of Backpropagation:
1. Forward pass: Compute the output for the given inputs by passing the data through the network.
2. Calculate loss: Use a loss function (e.g., mean squared error, cross-entropy) to measure how far the predicted output is from the actual target.
3. Backward pass: Propagate the error back through the network by calculating the gradient of the loss function with respect to the weights.
4. Update weights: Adjust the weights using gradient descent (or a variation like stochastic gradient descent) to minimize the loss

Q: Multi-Layer Perceptron (MLP)
A: An MLP is a type of Feedforward Neural Network that consists of multiple layers:
- An input layer, one or more hidden layers, and an output layer.
- MLPs are universal approximators, meaning they can approximate any continuous function given enough neurons in the hidden layers.

Q: Convolutional Neural Networks (CNNs), Layers
A: Convolutional Neural Networks (CNNs) are specialized neural networks primarily used for image recognition and classification tasks. They leverage a mathematical operation called convolution to capture spatial patterns in images.
Layers:
Convolutional Layer: Applies filters (kernels) to the input image to produce feature maps.
Polling Layer: Reduces the dimensionality of the feature amps while retaining important information
Fully Connected Layer: After several convolutional and polling layers, the output is flattened and fed into a fully connected layer for classification.

Q: Deep Learning - Concepts
A: Deep Learning refers to the use of neural networks with many layers (deep architectures). These networks can learn complex representations of data and are particularly useful for tasks such as image recognition, speech recognition, and natural language processing.
Concepts:
Deep Neural Networks: multiple layers between input and output layer
Representaion Learning: Deep learning automatically learns useful represenations of data, often from raw input, making it powerful for tasks that involve high-dimensional input such as images or text
End-to-End Learning: a single model is trained to process raw input data and directly predict the desired output without manual feature engineering

Q: Computation Graphs - forward and backward passes
A: A computation graph is a directed acyclic graph where nodes represent operations (like addition, multiplication, or activation functions), and edges represent the data dependencies between these operations.
forward pass: inputs are passed through the graph to compute the final output
backward pass: (packpropagattion) gradients are computed by traversing the graph in reverse, allowing for efficient computation of partial derivates needed for updating weights

Q: Recurrent Neural Networks (features, challenges, variants)
A: Recurrent Neural Networks (RNNs) are designed for sequence data, such as time series or natural language, where the order of inputs matters. Unlike feedforward networks, RNNs have connections that form cycles, allowing them to retain information across time steps.
Features:
Hidden State: captures information about previous inputs, allowing the network to model dependencies in the data
Recurrent Connections: The same weights are used each time step, enabling RNNs to handle variable-length sequences
Challenges
Vanishing and Exploding Gradients: When training long sequences, RNNs can struggle with vanishing gradients (where gradients become too small to make updates) or exploding gradients (where gradients become excessively large).
Variants:
LSTM (Long Short-Term Memory): addresses the vanishing gradient problem by introducing memory cells and gates (input, forget, output gates) to controll the flow of information
GRU (Gated Recurrent Unit): fewer gates than LSTM but still effective for capturing long-term dependencies

Q: PEAS Description of Agent
A: Performance - safety, destination, profits, legality, comfort, ...
Environment- streets/freeways, traffic, pedestrians, weather, ...
Actuators - steering, accelerator, brake, horn, speaker/display, . . .
Sensors - video, accelerometers, gauges, engine sensors, keyboard, GPS, . . .

Q: Explain the terms Completeness, Optimality, Time complexity, Space complexity in the context of search algorithms.
A: Completeness: If the algorithm finds a solution (should one exist)
Optimality: If the algorithm finds the best solution
Time Complexity: Number of nodes generated/expanded
Space Complexity: Maximum number of nodes in memory