Draft syllabus 2017–18

Foundations of Data Science

Lecturer: Dr Damon Wischik
Taken by: Part IB
Past exam questions for the predecessor course Mathematical Methods for Computer Science
No. of lectures (including practical classes): 12
Suggested hours of supervision: 3

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.

What's new, compared to the predecessor course Mathematical Methods for Computer Science? (i) a more practical focus on working with data, including Ticks, (ii) three new lectures on the basics of statistical inference, expanding on the ideas introduced in Machine Learning and Real World Data, (iii) material on inner product spaces will be presented as "linear data modelling" rather than abstract linear algebra, (iv) Fourier analysis is removed.

Aims

This course introduces fundamental tools for describing and reasoning about data. There are two themes: describing the behaviour of randomised 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 [2.5 lectures].
  Examples: random sample, graphical models, Markov models. Common random variables and their uses. Joint distributions, independence. Rules for expectation, including generating functions.
• Distributions of random variables [2 lectures].
  Generating random variables. Empirical distribution. Comparison of distributions. Law of large numbers, central limit theorem.
• Inference [3 lectures].
  Maximum likelihood estimation, likelihood profile, hypothesis testing, confidence intervals for parameters and predictions. Bayesianism, point estimation, classification. Case study: training a naive Bayes classifier.
• Feature spaces [2 lectures].
  Vector spaces, bases, inner products, projection. Model fitting as projection; linear modeling. Orthogonalisation, and application to linear models. Dimension reduction.
• Random processes [2.5 lectures].
  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, generating functions, 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.