7. Uncertainty in AI

Course Overview

Instructor: Prof. Jan PetersCourse Title: Probabilistic Methods for Computer ScienceSemester: WiSe 2024/25Institution: Computer Science Department, TU Darmstadt

Uncertainty in AI

Understanding and managing uncertainty is foundational in artificial intelligence (AI). Probabilistic methods provide a structured approach to quantify uncertainty, which is crucial for effective decision-making under unpredictable conditions.

Lecture Structure

The course will cover a comprehensive range of probabilistic methods and their applications across various contexts.

Initial Topics

• Basic Cycle of Probabilistic Modeling and Analysis:

  • Model Structure: Denotes the framework establishing probabilistic relationships.

  • Model Parameters: ( heta ), variables that influence model outcomes, requiring precise estimation.

  • Observed Data from Experiment: Denoted as ( D ), the empirical data used to validate or refine the model.

  • Prior Assumptions: Initial beliefs about the model, encoded as a prior distribution ( P(\theta) ).

  • Model Quality Evaluation: Involves assessing the accuracy of predictions against actual outcomes, often using metrics such as Mean Squared Error (MSE): ( MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 ), where ( y_i ) is the actual value and ( \hat{y}_i ) is the predicted value.

  • Modeling Probability Distribution: Used to describe the behavior of random variables with density functions like Gaussian: ( f(x) = \frac{1}{\sqrt{2\pi \sigma^2}} e^{-\frac{(x - \mu)^2}{2\sigma^2}} ).

  • Estimating Uncertain Quantities: Techniques, including Maximum Likelihood Estimation (MLE): ( \hat{\theta} = \arg\max_{\theta} P(D|\theta) ), to infer hidden parameters.

  • Experimental Design & Evaluation: Structuring experiments to assess hypotheses efficiently, often guided by principles from statistics like sampling methods.

Motivation: Autonomous Cars

Scenario: Decision-making at a crossroad:

• Option 1: A reliable but potentially slower route, minimizing accident risks with stable performance.

• Option 2: A novel, untested route with uncertain traffic behavior but enhanced efficiency.This situation illustrates the Exploration-Exploitation Dilemma, which is critical in AI and decision-making situations.

Types of Uncertainty

• Epistemic Uncertainty: Originates from lack of knowledge regarding the new route. It diminishes with increasing data via Bayesian updating: ( P(\theta | D) = \frac{P(D | \theta) P(\theta)}{P(D)} ).

• Aleatoric Uncertainty: Represents inherent randomness in traffic conditions that persists regardless of the amount of data collected.

• Challenge: Primarily tackling epistemic uncertainty is vital, as it impacts the effectiveness of decision-making.

Importance of Managing Uncertainty

Mismanagement can have detrimental consequences:

• Inefficient Resource Allocation: Wasted time, energy, and financial resources.

• Safety Risks: Increased likelihood of accidents, especially in critical AI implementations, modeled via risk metrics.

• Reduced Reliability: Erosion of user trust due to unreliable system performance, which can often be tracked through reliability metrics.

Decision Making under Uncertainty - Taxonomy

Methods for decision-making under uncertainty include:

• Probabilistic and Statistical Methods: Involves distributions and conditional probabilities.

• Optimization Strategies: Focuses on refining decision-making efficiencies through objective functions ( f(x) ).

• Learning-Based Methods: Algorithms that adapt based on historical data utilizing loss functions: ( L(y, \hat{y}) = -\sum P(y) \log P(\hat{y}) ).

• Bayesian Decision Theory: Uses prior knowledge and evidence to formulate decisions, using Bayes' theorem as noted.

• Monte Carlo Methods: Implement random sampling to compute results via averages from simulations.

• Predictive Analytics: Leverage historical data to predict future outcomes using regression models: ( y = \beta_0 + \beta_1 x_1 + \cdots + \beta_n x_n + \epsilon ).

• Bandits: Addressing multi-armed bandits where rewards reflect unknown distributions, maximizing cumulative reward over time.

• Dynamic Programming: A strategy that recursively breaks problems into simpler subproblems, using Bellman equations: ( V(x) = \max_a [R(x, a) + \gamma E[V(s')] ] ).

• Reinforcement Learning: Involves learning and improving policies based on state-action pairs and rewards, often represented as Q-learning: ( Q(s, a) \leftarrow Q(s, a) + \alpha[r + \gamma \max_{a'}Q(s', a') - Q(s, a)] ).

• Global Optimization: Finding optimal solutions within potentially non-convex spaces while facing uncertainty derived from variances in input values.

• Robust Optimization: Ensures solutions remain valid under uncertainty by formulating constraints that accommodate variations.

• Evolutionary Algorithms: Optimization methods inspired by natural selection, such as genetic algorithms that evolve solutions over generations.

• Bayesian Reinforcement Learning: Merging reinforcement learning with Bayesian methods to accommodate uncertainties in the decision processes.

• Game Theory: Models interactions among rational agents, often represented with utility functions to maximize payoffs.

Today's Lecture Topics

• Overview of probabilistic methodologies and optimization strategies essential for systems operating under uncertainty.

• Focus on learning-based frameworks and the complexities associated with multi-armed bandit problems.

Discrete Finite Optimization

This core process involves determining the optimal choice from a set of alternatives, generally based on performance evaluations and cost functions.

Multi-armed Bandit Problem

• Definition: The classical problem of selecting one of multiple actions (arms) to maximize rewards where each arm gives a different expected return, typically modeled via distributions.

• Core Challenges:

  • Exploration: Identifying and estimating the rewards of each arm, requiring sufficient trials to gain insights.

  • Exploitation: Selecting the arm with currently known best performance for immediate returns.

  • Trade-off: A significant aspect where maintaining a balance between exploration and exploitation is crucial for satisfactory long-term results.

Multi-armed Bandit Example

• Scenario: Determining the fastest server among several in a cloud context with variable performance across different workloads, modeled to manage variance in response times.

Upper Confidence Bound (UCB)

• Method: A strategy to choose the best-performing arm by incorporating both the estimated rewards and the associated uncertainty using confidence bounds: ( UCB(a) = \bar{X}_a + \sqrt{\frac{2 \log n}{n_a}} ), where ( \bar{X}_a ) is the average reward for arm ( a ) and ( n_a ) is the number of times arm ( a ) has been selected.

Global Optimization

• Goal: Identifying the optimal minimum or maximum of a complex function where total exploration is impractical.

• Challenges:

  • Addressing uncertainty in decision variables using models like probabilistic constraints.

  • Dealing with unknown characteristics in the objective function, often treated as a black box leading to heuristics and surrogate models.

Advanced Approaches in Optimization

• Zeroth-Order Optimization: Techniques, like Genetic Algorithms, that optimize without requiring explicit information about the objective function.

• First-Order Optimization: Approaches like Gradient Descent, necessary for function optimization assuming differentiability of the function.

• Surrogate Models: Incorporating historical evaluations to predict best next steps through regression techniques or Kriging approaches.

Bayesian Decision Making

• Bayesian decision-making processes leverage surrogate models that estimate future evaluations by quantifying uncertainties through probability distributions.

• This includes model fitting using parameters and optimization through acquisition functions to maximize information gain.

Dynamic Programming vs. Reinforcement Learning

• Dynamic Programming: Assumes knowledge of the environment, using formulations like the Bellman equation to solve problems exhaustively.

• Reinforcement Learning: Learns policy for optimal action selection through experiences in the environment, adapting through feedback from state transitions and rewards.

Conclusion

• Objectives of the Course:

  • Understanding the influence of uncertainty within the context of decision-making.

  • Establishing connections between differing algorithms across multiple applications.

  • Exploring practical applications for probabilistic methods within AI and beyond.

Self-Test Questions

1. Explain the significance of uncertainty in decision-making processes.

2. Define multiclass bandits and their implications on decision-making.

3. Discuss the challenges presented in global optimization and how Bayesian decision-making tackles them.

4. Identify surrogate modeling methods employed in Bayesian optimization contexts.

5. Illustrate the exploration-exploitation trade-off in decision-making scenarios and its relevance.

6. Assess the advantages of Dynamic Programming compared to traditional search methodologies.

7. Outline the challenges of Dynamic Programming that Reinforcement Learning aims to resolve.