Anintroductiontomachinelearningandgraphicalmodels.ppt

An introduction to machine learning and probabilistic graphical models Kevin Murphy MIT AI Lab Overview Supervised learning Unsupervised learning Graphical models Learning relational models Supervised learning Supervised learning Key issue: generalization Hypothesis spaces Decision trees Neural networks K-nearest neighbors Na?ve Bayes classifier Support vector machines (SVMs) Boosted decision stumps … Perceptron(neural net with no hidden layers) Which separating hyperplane? The linear separator with the largest margin is the best one to pick What if the data is not linearly separable? Kernel trick Support Vector Machines (SVMs) Two key ideas: Large margins Kernel trick Boosting Supervised learning success stories Face detection Steering an autonomous car across the US Detecting credit card fraud Medical diagnosis … Unsupervised learning What if there are no output labels? K-means clustering Guess number of clusters, K Guess initial cluster centers, ?1, ?2 Assign data points xi to nearest cluster center Re-compute cluster centers based on assignments AutoClass (Cheeseman et al, 1986) EM algorithm for mixtures of Gaussians “Soft” version of K-means Uses Bayesian criterion to select K Discovered new types of stars from spectral data Discovered new classes of proteins and introns from DNA/protein sequence databases Hierarchical clustering Principal Component Analysis (PCA) PCA seeks a projection that best represents the data in a least-squares sense. Discovering nonlinear manifolds Combining supervised and unsupervised learning Discovering rules (data mining) Unsupervised learning: summary Clustering Hierarchical clustering Linear dimensionality reduction (PCA) Non-linear dim. Reduction Learning rules Discovering networks Networks in biology Most processes in the cell are controlled by networks of interacting molecules: Metabolic Network Signal Transduction Networks Regulatory Networks Networks can be modeled at multiple levels of detail/ realism