Blog · Collection
Artificial intelligence
Computational hardness, probabilistic reasoning with Bayesian networks and HMMs, machine learning, decisions with MDPs, reinforcement learning, and games.
Artificial intelligence can be framed as the science of acting well under uncertainty, built from probability, optimization and decision theory.
Hard problems
Many AI tasks are NP-hard, which shapes the whole field. Instead of exact solutions, one looks for approximation guarantees, good heuristics or problem structure to exploit.
Reasoning under uncertainty
Bayesian networks encode a joint distribution as a directed graph in which each variable depends directly only on its parents, so large distributions can be stored and queried compactly. Exact inference is hard in general but tractable on tree-structured graphs. Hidden Markov models handle reasoning over time, and particle filters approximate the current belief with a cloud of weighted samples. Robot localization is the classic example: a robot keeps track of where it might be from noisy sensor readings. Deciding which observation to make or which question to ask next comes down to the value of information.
Learning from data
On the learning side, the core topics are regression, choosing predictors without overfitting, classification, and neural networks, including deep networks trained by gradient descent with backpropagation.
Making decisions
Utility theory defines a rational choice as one that maximizes expected utility. Markov decision processes add sequential structure, and the optimal value function satisfies the Bellman equation
which value iteration and policy iteration solve. Reinforcement learning learns to act when the transition probabilities are unknown, for example with Q-learning, and deep reinforcement learning replaces lookup tables with neural networks. In two-player zero-sum games, the optimal mixed strategy is the solution of a linear program.