State space representation
- Searching the state space: greedy methods, simulated annealing
- Backtracking search, properties
- Heuristic information, static evaluation function
- Greedy approaches: irrevocable use of heuristics, simulated annealing
- Graph searching
- "Blind" methods: breadth-first, depth-first, iterative
deepening search
- Cost-based methods: uniform-cost and best-first
- The A* algorithm, properties, variants
- Constructing useful heuristic functions
- Searching for two-person games: the
minimax algorithm, alpha-beta cuts, probabilistic variants of
minimax
Logic-based representations
- Propositional logic, basic laws of logic
- Semantics, interpretations, unsatisfiability,
logical consequence and logical equivalence, truth tables
- Inference rules, proofs, theorems, theorem proving
systems
- Normal forms: DNF and CNF, clauses, empty
conjunctions and empty clauses
- Resolution-based theorem proving
- First order predicate calculus: terms,
predicates, logical connectives, quantifiers, atomic formulas,
literals, sentences
- Converting formulas to the prenex form, skolemization
- Substituting variables in formulas, formula unification,
general case resolution
- Logic programming in Prolog
- Representing simple facts and logical
rules as Prolog clauses. Horn clauses.
- Variables, queries, the Prolog pattern
matching/theorem proving algorithm.
- Numbers, lists, cuts.
Probabilistic representation
- Basic concepts: prior probability, probability
axioms, random variables, joint probability distribution,
conditional probability, Bayes' rule
- Probabilistic belief networks: construction,
reasoning
- Making simple decisions: preferences and
utility functions, the MEU principle, multiattribute
problems, dominance, the value of information, value of perfect
information (VPI)
- Sequential decision problems: Markov decision
processes, agent's policy, state sequence utilities,
discounting, policy evaluation, the value and
policy iteration algorithms
Machine learning methods
- Induction learning types: supervised, unsupervised, reinforcement
- Decision trees: general principles,
computing entropy and information gain, building decision trees,
stopping conditions, binary decision trees,
- Efficiency of inductive learning: missing data,
errors in data, noise, overfitting
- Evaluating classification learning results:
accuracy, confusion matrix, precision, recall, training set, testing
set, validation set, cross-validation, detecting and avoiding
overfitting
- The Naive Bayes Classifier algorithm
- The Nearest-Neighbors algorithm
- Ensemble Learning: Bagging, Random Forest,
Stacking, Boosting, Gradient Boosting
- Classification machine learning: problems with
multi-dimensional spaces (curse of dimensionality), simple and
powerful approaches, feature engineering, availability of data
- Unsupervised learning
- clustering: k-means, EM, and hierarchical clustering algorithms
- dimensionality reductions: the PCA algorithm
- market basket analysis: the Apriori algorithm, collaborative filtering
- Reinforcement learning: trials, direct utility
determination, adaptive dynamic programming (ADP), TD learning,
exploration, Q-learning, function approximation.