Transcript CS B553: Algorithms for Optimization and Learning

CS B553: ALGORITHMS FOR
OPTIMIZATION AND LEARNING
aka “Neural and Genetic Approaches to Artificial
Intelligence”
Spring 2011
Kris Hauser
TODAY’S AGENDA
Topics covered
 Prerequisites
 Class organization & policies
 Coursework
 Math review

WHAT IS OPTIMIZATION?

The problem of choosing the “best” solution from
some set of candidate solutions
Airplane wing that minimizes drag
 Stock portfolio that maximizes return on investment
 Feedback control strategy with highest probability of
picking up an object
 (In many problems, it is easier to measure the quality
of candidate solutions than to produce the optimum!)

A mathematical discipline that is heavily studied
and utilized in other fields
 Powerful idea in AI, machine learning, computer
vision, engineering, economics, applied sciences

OPTIMIZATION LEARNING OBJECTIVES

Hands-on experience in specifying mathematical
optimization problems
Defining objective functions, constraints
 Identifying problem characteristics (e.g., convexity)
 Characteristics of small/medium/large scale problems
 Mostly continuous optimization, some discrete and
mixed-integer optimization


Solving optimization problems in practice
Algorithms: descent-based, simplex based, stochastic
 Software packages
 Performance tricks
 Applied to realistic scenarios

WHAT IS LEARNING?

Deriving “meaningful” quantities from raw data (e.g.,
gathered from logs, surveys, sensors) and employing
them
Diagnosing a patient from reported symptoms
 Recognizing human activity from video
 Forecasting weather or economic behavior from history


Diverse range of learning tasks, most of which involve
one or more of:
Fitting a model by adjusting model parameters
 Selecting a model structure that explains the data
 Using a model to infer meaningful quantities


Many learning tasks are essentially optimization
problems!
LEARNING LEARNING OBJECTIVES

Conceptual frameworks for large scale learning
Graphical models (e.g., Bayesian networks)
 Hidden Markov Models (HMMs),
 Dynamic Bayesian Networks (DBNs)


Understanding of key components for
implementing many learning algorithms
Belief propagation
 Expectation maximization algorithms
 Monte Carlo techniques


Experience applying algorithms to real-world
datasets
ORGANIZATION

http://www.cs.indiana.edu/classes/b553-hauserk

Lectures, readings
Lecture notes for optimization unit
 Probabilistic Graphical Models: Principles and
Techniques (Koller and Friedman) for learning unit


In-class group exercises
COURSE WORK
Attendance and participation: 20% of grade
 8 homework assignments (4 written, 4
programming): 80% of grade
 Programming in language of your choosing
 Optional final project

Original research, survey, or reproduction of recent
research paper with a substantial
optimization/learning component
 Counts for 4 HW grades

POLICIES
Office hours: W 10-11am, Info E 257 (or by
appointment)
 Should respond to email in 24 hours
 Late HW:


10% deducted for every day late
PREREQUISITES
CS B551 or equivalent introduction to AI course.
Specifically, probabilistic reasoning and Bayesian
networks
 Calculus. (Multivariate recommended)
 Linear algebra

LECTURE