Department of Computer Science and Technology

Course pages 2017–18

Subsections


Foundations of Data Science

Lecturer: Dr D. Wischik

No. of lectures and practical classes: 12 + 4

Suggested hours of supervisions: 3

Prerequisite courses: either Mathematics for Natural Sciences, or the equivalent from the Maths Tripos

This course is a prerequisite: for Part IB Formal Models of Language, and for Part II Machine Learning and Bayesian Inference, Bioinformatics, Computer Systems Modelling, Information Theory, Quantum Computing, Natural Language Processing, Advanced Graphics.

Aims

This course introduces fundamental tools for describing and reasoning about data. There are two themes: describing the behaviour of random systems; and making inferences based on data generated by such systems. The course will survey a wide range of models and tools, and it will emphasize how to design a model and what sorts of questions one might ask about it.

Lectures

  • Probabilistic models. Examples: random sample, graphical models, Markov models. Common random variables and their uses. Joint distributions, independence. Rules for expectation and variance.

  • Distributions of random variables. Generating random variables. Empirical distribution. Comparing distributions. Law of large numbers, central limit theorem.

  • Inference. Maximum likelihood estimation, likelihood profile. Bootstrap, hypothesis testing, confidence intervals for parameters and predictions. Bayesianism, point estimation, classification. Case study: training a naive Bayes classifier.

  • Feature spaces. Vector spaces, bases, inner products, projection. Model fitting as projection; linear modeling. Orthogonalisation, and application to linear models. Dimension reduction.

  • Random processes. Drift models. Markov chain convergence: notions, and calculations. Examples. Notions of estimation and control. Examples of processes with memory.

Objectives

At the end of the course students should

  • be able to formulate basic probabilistic models, including discrete time Markov chains, graphical models, and linear models

  • be familiar with common random variables and their uses, and with the use of empirical distributions rather than formulae

  • be able to use expectation and conditional expectation, limit theorems, equilibrium distributions

  • understand different types of inference about noisy data, including model fitting, hypothesis testing, and making predictions

  • understand the fundamental properties of inner product spaces and orthonormal systems, and their application to model representation

Recommended reading

* F.M. Dekking, C. Kraaikamp, H.P. Lopuhaä, L.E. Meester (2005). A modern introduction to probability and statistics: understanding why and how. Springer.

S.M. Ross (2002). Probability models for computer science. Harcourt / Academic Press.

M. Mitzenmacher & E. Upfal (2005). Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press.