Artificial Intelligence

2010 - 2020

Overview

In this module, problem-solving methods from the perspective of the rational agent (one of the four definitions of AI) are investigated. Problems are defined assuming a world for the agent (environment). This world includes a set of states. An agent has a set of actions with which it moves between states. The difference in the structure of the states as well as the agent's level of knowledge from the next state creates a category in artificial intelligence.

		what about the next state?
		determined	stochastic	unknown
how are states in this environment	Atomic (simple)	SEARCH	Stochastic Games Markov Decision Process	Reinforcement Learning
	Factored (Variables)	CSP LOGIC	Bayes Net
	Structured	First Order Logic

Syllabus

\[\color{blue}{Part 1: Introduction to AI}\]

• Introduction
  • History of AI, Definition of AI, Agents and Environments, Rationality, Utility
  • Types of Agents, Search Problem
• Uninformed Search
  • BFS, DFS, DLS, IDS, BS, UCS
• Informed Search
  • Heuristic Functions
  • Greedy Search, A*, IDA*, RBFS, MA*, SMA*
• Constraint Satisfaction Problem
  • Constraint Graphs, Backtracking Algorithm
  • Improving Backtracking
    • Filtering, Forward Checking, Arc Consistency
    • Ordering, MRV, LCV,
    • Structure, tree-structured CSP
  • Local Search
    • Optimization Problems
    • Iterative improvement, min-conflict heuristic
    • Hill Climbing, Random Walk
    • Simulated Annealing, Beam Search
    • Genetic Algorithm
• Adversarial Search and Games
  • Forms of Games, Zero-sum game
  • Minimax Theorem, Alpha-Beta Search, Pruning.
  • Stochastic Games, Expectation Minimax
• Logical Agents
  • Propositional Logic, First Order Logic
  • Satisfiability, Planning
  • Logic Representation(Syntax and Semantic), Logic Inference(Forward Chaining, Backward Chaining, Resolution), Unification
  • ProLog
  • Knowledge Representation, Ontology, Objects

\[\color{blue}{Part 2: Advanced AI}\]

• Markov Decision Process
  • Definition of Markov Decision Process(MDP), State, Action, Transition Functions, Reward
  • Policy, Optimal Policy, State-value, Q-value, Bellman Equation
  • value iteration, policy iteration
  • Convergence, exploration, exploitation, regret
• Reinforcement Learning
  • Model-based RL, Model-free RL
  • Passive RL, Active RL
  • Temporal-Difference Value Learning,
  • Q-Learning
    • 𝜖-Greedy
    • Approximate Q-learning
• Uncertainty and Probability
  • Random variables, Probability, PDF, Joint Probability, Conditional Probability
  • Product Rule, Bayes’ theorem, Chain Rule
  • Independence, conditional Independence
• Bayes Net
  • Bayesian Networks
  • Representation
    • Conditional Independence Semantics
      • Causal Chains, Common Cause, Common Effect
    • Active / Inactive Paths
  • Inference
    • Exact inference
      • Enumeration
      • Variable Elimination
    • Approximate Inference (Sampling)
      • Prior Sampling
      • Rejection Sampling
      • Likelihood Weighting
      • Gibbs Sampling
• Hidden Markov Model
  • Markov chain, Markov property, Markov Model, Hidden Markov Model
  • Evaluation
    • Forward Algorithm
    • Backward Algorithm
  • Most likely sequence of states(Decoding)
    • Viterbi algorithm
  • Training
    • Viterbi training
    • Baum Welch Algorithm
  • Particle Filtering, Kalman filter