The objective of this course is to study algorithms for general computational problems, with a focus on the principles used to design those algorithms. Efficient data structures will be discussed to support these algorithmic concepts. Topics include: Run time analysis, divide-and-conquer algorithms, dynamic programming algorithms, network flow algorithms, linear and integer programming, large-scale search algorithms and heuristics, efficient data storage and query, and NP-completeness. Although this course may have a few programming assignments, it is primarily not a programming course. Instead, it will focus on the design and analysis of algorithms for general classes of problems.
An in-depth look at modern algorithms used to process string data, particularly those relevant to genomics. This course will cover the design and analysis of efficient algorithms for processing enormous collections of strings. Topics will include string search; inexact matching; string compression; string data structures such as suffix trees, suffix arrays, and searchable compressed indices; and the Burrows-Wheeler transform. Applications of these techniques in biology will be presented, including genome assembly, transcript assembly, whole-genome alignment, gene expression quantification, read mapping, and search of large sequence databases. No knowledge of biology is assumed, and the topics covered will be of use in other fields involving large collections of strings. Programming proficiency is required.
The first half of the course will cover standard and classical string algorithms and data structures. The second half of the course will cover recent research on large-scale string processing. While problems in genomics will be often be the motivating examples, the course covers general results for processing strings that are not specific to biology. Coursework: several homeworks, research paper readings, a midterm, and a course project of your choosing.
Many of the problems in artificial intelligence, statistics, computer systems, computer vision, natural language processing, and computational biology, among many other fields, can be viewed as the search for a coherent global conclusion from local information. The general graphical models framework provides an unified view for this wide range of problems, enabling efficient inference, decision-making and learning in problems with a very large number of attributes and huge datasets. This graduate-level course will provide you with a strong foundation for both applying graphical models to complex problems and for addressing core research topics in graphical models. The class will cover three aspects: The core representation, including Bayesian and Markov networks, dynamic Bayesian networks, and relational models; probabilistic inference algorithms, both exact and approximate; and, learning methods for both the parameters and the structure of graphical models. Students entering the class should have a pre-existing working knowledge of probability, statistics, and algorithms, though the class has been designed to allow students with a strong numerate background to catch up and fully participate. Students are required to have successfully completed 10701/15781, or an equivalent class.
This course builds on the material presented in 10-701(Machine Learning), introducing new learning methods and going more deeply into their statistical foundations and computational aspects. Applications and case studies from statistics and computing are used to illustrate each topic. Aspects of implementation and practice are also treated. A tentative list of topics to be covered includes (but is not restricted to) the following: Maximum likelihood vs. Bayesian inference; Regression, Classficiation, and Clustering; Graphical Methods, including Causal Inference; The EM Algorithm; Data Augmentation, Gibbs, and Markov Chain Monte Carlo Algorithms; Techniques for Supervised and Unsupervised Learning; Sequential Decision making and Experimental Design.
The goal of “Language and Statistics” is to ground the data-driven techniques used in language technologies in sound statistical methodology. We start by formulating various language technology problems in both an information theoretic framework (the source-channel paradigm) and a Bayesian framework (the Bayes classifier). We then discuss the statistical properties of words, sentences, documents and whole languages, and the various computational formalisms used to represent language. These discussions naturally lead to specific concepts in statistical estimation.
Topics include: Zipf’s distribution and type-token curves; point estimators, Maximum Likelihood estimation, bias and variance, sparseness, smoothing and clustering; interpolation, shrinkage, and backoff; entropy, cross entropy and mutual information; decision tree models applied to language; latent variable models and the EM algorithm; hidden Markov models; exponential models and the maximum entropy principle; semantic modeling and dimensionality reduction; probabilistic context-free grammars and syntactic language models.
This course seeks to cover statistical modeling techniques for discrete, structured data such as text. It brings together content previously covered in Language and Statistics 2 (11-762) and Information Extraction (10-707 and 11-748), and aims to define a canonical set of models and techniques applicable to problems in natural language processing, information extraction, and other application areas. Upon completion, students will have a broad understanding of machine learning techniques for structured outputs, will be able to develop appropriate algorithms for use in new research, and will be able to critically read related literature. The course is organized around methods, with example tasks introduced throughout. The prerequisite is Machine Learning (10-601 or 10-701),or permission of the instructors.
We introduce random processes and their applications. Throughout the course, we mainly take a discrete-time point of view, and discuss the continuous-time case when necessary. We first introduce the basic concepts of random variables, random vectors, stochastic processes, and random fields. We then introduce common random processes including the white noise, Gaussian processes, Markov processes, Poisson processes, and Markov random fields. We address moment analysis (including Karhunen-Loeve transform), the frequency-domain description, and linear systems applied to stochastic processes. We also present elements of estimation theory and optimal filtering including Wiener and Kalman filtering. Advanced topics in modern statistical signal processing such as linear prediction, linear models and spectrum estimation are discussed. 4 hrs. lec. Prerequisites: Prerequisites: 36-217 and 18-396 and senior or graduate standing. It is strongly advised that students have a prior Signals and Systems course and a Probability course.
The course studies image processing, image understanding, and video sequence analysis. Image processing deals with deterministic and stochastic image digitization, enhancement. restoration, and reconstruction. This includes image representation, image sampling, image quantization, image transforms (e.g., DFT, DCT, Karhunen-Loeve), stochastic image models (Gauss fields, Markov random fields, AR, ARMA) and histogram modeling. Image understanding covers image multiresolution, edge detection, shape analysis, texture analysis, and recognition. This includes pyramids, wavelets, 2D shape description through contour primitives, and deformable templates (e.g., ‘snakes’). Video processing concentrates on motion analysis. This includes the motion estimation methods, e.g., optical flow and block-based methods, and motion segmentation. The course emphasizes experimenting with the application of algorithms to real images and video. Students are encouraged to apply the algorithms presented to problems in a variety of application areas, e.g., synthetic aperture radar images, medical images, entertainment video image, and video compression.
Finite precision arithmetic, interpolation, spline approximation, numerical integration, numerical solution of linear and nonlinear systems of equations, optimization in finite dimensional spaces.
An introduction to the modern theory of partial differential equations. Including functional analytic techniques. Topics vary slightly from year to year, but generally include existence, uniqueness and regularity for linear elliptic boundary value problems and an introduction to the theory of evolution equations.
This course is a rigorous introduction to the mathematical theory of probability, and it provides the necessary background for the study of mathematical statistics and probability modeling. A good working knowledge of calculus is required. Topics include combinatorial analysis, conditional probability, generating functions, sampling distributions, law of large numbers, and the central limit theorem.
This course covers the fundamentals of theoretical statistics. Topics include: probability inequalities, point and interval estimation, minimax theory, hypothesis testing, data reduction, convergence concepts, Bayesian inference, nonparametric statistics, bootstrap resampling, VC dimension, prediction and model selection.
This seminar provides an introduction to computational approaches for probabilistic modeling and inference. A particular focus is placed on Bayesian networks, although other probabilistic models also will be studied. Medical applications are emphasized, however, the principles are general and no medical knowledge is needed to take the course. The course does not require knowledge of a computer programming language.
The purpose of the course is to present in thorough fashion the material in an outstanding book, Elements of Statistical Learning, by Hastie, Tibshirani, and Friedman. This rigorous and clearly written book places “statistical learning” or “data mining” techniques in the proper context with regard to their origins in simple classical methosds like linear regression, to clarify the strengths and weaknesses from theoretical and practical sides. “Supervised learning” techniques studied incude using regularization and Bayesian methods, kernel methods, basis function methods, neural networks, support vector machines, additive trees, boosting bootstrap-based methods. Unsupervised learning techniques studied include cluster analysis, self-organizing maps, independent component analysis and projection pursuit.
Covers joint, marginal, and conditional probabilities; distributions of random variables and functions of random variables; expectations of random variables and moment generating functions; law of large numbers; central limit theorem.
The theoretical foundations of Bayesian and empirical Bayes statistical methods will be presented. The use of these methods in data analysis will be illustrated with specific examples and with discussions of common data analysis issues contrasts and similarities between Bayesian, empirical Bayesian, and classical methods will be evaluated.
Develop theory and practice for the EM algorithm. Markov chain sampling techniques, importance sampling, and other advanced ideas in statistical computation. Introduces computing on UNIX workstations with X Window and S-PLUS.
The main objective of this course is to provide an in-depth knowledge of database management systems design. Topics covered at length are concurrency control including concurrency on structured data, recovery and query optimization. Some important aspects of distributed databases are discussed, including distributed concurrency control and fault tolerance.
The course gives an introduction to the iterative algorithms for solving linear and nonlinear systems. The course will cover the development and analysis of these numerical algorithms, to be used in the resolution of linear and nonlinear systems.
This is an introductory survey course for non-numerical analysis students. It covers the underlying theory and computational aspects of numerical linear algebra. Topics include directional iterative methods, computation of eigenvalues and eigenvectors and least squares problems.
This course aims to give an in-depth introduction to the numerical methods for solving ordinary differential equations. Both initial value problems and boundary value problems are considered. Important practical issues such as stability, stiffness, error estimation and control will be considered for Runge-Kutta methods, multistep methods and finite difference methods. If time permits, numerical techniques for differential-algebraic equations will be also presented.
This is an introductory graduate course in the theory of statistical estimation. The following topics will be covered. The use of orthogonal transformations in statistical distribution theory, distribution of quadratic forms, the theory of linear estimation, the general theory of estimation and estimation from a decision theoretic point of view.
This course begins with an introduction to Lebesque integral. Then distribution functions, probability measures and random variables are introduced. Convergence concepts and topics from the laws of large numbers and random series are also covered.