Outline

• Definitions
• Motivation
• Examples
• Learning Problem
• Components of Learning
• Types of Learning
• Puzzle

3
 A Few Quotes
“A breakthrough in machine learning would be worth ten Microsofts”
– (Bill Gates, Chairman, Microsoft)

“Machine learning is the next Internet”

– (Tony Tether, Director, DARPA)

“Machine learning is the hot new thing”

– (John Hennessy, President, Stanford)

“Web rankings today are mostly a matter of machine learning”

– (Prabhakar Raghavan, Dir. Research, Yahoo)

“Machine learning is going to result in a real revolution”

– (Greg Papadopoulos, CTO, Sun)

“Machine learning is today’s discontinuity”

– (Jerry Yang, CEO, Yahoo)
Definitions Motivation Examples Learning Problem Components of Learning Types of Learning Puzzle 4
 Machine Learning Popularity
Google Trends: Machine Learning

5
 So What Is Machine Learning (Informally)?

• Automating automation
• Getting computers to program themselves
• Writing software is the bottleneck
• Let the data do the work instead!

Traditional Programming Machine Learning

6
 What Is Machine Learning (Formally)?
"A computer program is said to learn from experience E with respect to some class of tasks T and
performance measure P, if its performance at tasks in T, as measured by P, improves with experience E."
--Tom M. Mitchell

"Machine learning is the training of a model from data that generalizes a decision against a performance
measure."
--Jason Brownlee

"A branch of artificial intelligence in which a computer generates rules underlying or based on raw data that
has been fed into it."
--Dictionary.com

"Machine learning is a scientific discipline that is concerned with the design and development of algorithms
that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases."
--Wikipedia
7
 Why “Learn”?

• Machine learning is programming computers to optimize a

performance criterion using example data or past experience.
• There is no need to “learn” to calculate payroll
• Learning is used when:
– Human expertise does not exist (navigating on Mars),
– Humans are unable to explain their expertise (speech recognition)
– Solution changes in time (routing on a computer network)

8
 What We Talk About When We Talk
About“Learning”
• Learning general models from a data of particular examples

• Data is cheap and abundant (data warehouses, data marts); knowledge is

expensive and scarce.

• Build a model that is a good and useful approximation to the data.

9
 ML at a Glance
• Machine Learning
– Study of algorithms that
– improve their performance
– at some task
– with experience
• Optimize a performance criterion using example data or past experience.
• Role of Statistics: Inference from a sample
• Role of Computer science: Efficient algorithms to
– Solve the optimization problem
– Representing and evaluating the model for inference

10
 Commercial Motivation for Machine Learning
• Lots of data is being collected
and warehoused
– Web data, e-commerce
– purchases at department/
grocery stores
– Bank/Credit Card
transactions

• Computers have become cheaper and more powerful

• Competitive Pressure is Strong
– Provide better, customized services for an edge (e.g. in Customer Relationship
Management)
Definitions Motivation Examples Learning Problem Components of Learning Types of Learning Puzzle 11
 Scientific Motivation for Machine Learning
• Data collected and stored at
enormous speeds (GB/hour)
– remote sensors on a satellite
– telescopes scanning the skies
– microarrays generating gene
expression data
– scientific simulations
generating terabytes of data
• Traditional techniques infeasible for raw data
• Machine Learning may help scientists
– in classifying and segmenting data
– in Hypothesis Formation 12
 Practical Machine Learning Examples

Spam Detection Credit Card Fraud Detection Speech Recognition

Face Detection Product Recommendation Sentiment Analysis

Definitions Motivation Examples Learning Problem Components of Learning Types of Learning Puzzle 13
 Example: Predicting how a viewer will rate a movie

• 10% improvement = 1 million dollar prize

• The essence of machine learning
– A pattern exists
– We cannot pin it down mathematically
– We have data on it

Definitions Motivation Examples Learning Problem Components of Learning Types of Learning Puzzle 14
Movie rating – a solution

http://work.caltech.edu/slides/slides01.pdf
15
The Learning Approach

http://work.caltech.edu/slides/slides01.pdf
16
 Components of Learning
http://work.caltech.edu/slides/slides01.pdf

Definitions Motivation Examples Learning Problem Components of Learning Types of Learning Puzzle 17
 Components of Learning
Formalization

http://work.caltech.edu/slides/slides01.pdf
18
http://work.caltech.edu/slides/slides01.pdf
19
Solution Components

http://work.caltech.edu/slides/slides01.pdf
20
A simple hypothesis set

http://work.caltech.edu/slides/slides01.pdf
21
 Types of Learning
• Supervised (inductive) learning
– Training data includes desired outputs
• Unsupervised learning
– Training data does not include desired outputs
• Reinforcement learning
– Rewards from sequence of actions

Definitions Motivation Examples Learning Problem Components of Learning Types of Learning Puzzle 22
 Supervised & Unsupervised Learning
Supervised Learning Unsupervised Learning
• Labeled dataset • Unlabeled dataset
• Establish relationship between input and • Decipher structure of the data
output • Output attributes are not defined
• Generate output for new data points • Clustering: Kmeans, DBScan, Hierarchical
• Reliable models but expensive and limited algorithms, Self Organizing Maps, etc
• Classification: Associative classifiers, • Associations: Apriori, FP-Growth, …
Decision Trees, Instance Learning,
Bayesian Learning, Kernel machines,
Neural Networks, Genetic Algorithms, etc
• Regression: Linear Regression, …
Reinforcement Learning
• Maximizing the rewards from the results
• Also called credit assessment learning
• Additional decision about rewards
• Explore the tradeoff between exploring and
exploiting the data
23
 Supervised Learning: Classification
• a way to identify a grouping technique for a given dataset
• depending on a value of the target or output attribute, the entire dataset can be qualified to belong to a class
• this technique helps in identifying the data behavior patterns
Determine good or bad customers?
Total Money Spent

Total Items Purchased

All the customers who spend more than 800 dollars in a single
purchase are categorized as good customers. 24
 Classification: Definition
• Given a collection of records (training set )
– Each record contains a set of attributes, one of the attributes is the class.
• Find a model for class attribute as a function of the values of
other attributes.
• Goal: previously unseen records should be assigned a class
as accurately as possible.
– A test set is used to determine the accuracy of the model.
– Usually, the given data set is divided into training and test sets
– with training set used to build the model and test set used to validate it.

25
 Classification Example

Tid Refund Marital Taxable Refund Marital Taxable

Status Income Cheat Status Income Cheat

1 Yes Single 125K No No Single 75K ?

2 No Married 100K No Yes Married 50K ?
3 No Single 70K No No Married 150K ?
4 Yes Married 120K No Yes Divorced 90K ?
5 No Divorced 95K Yes No Single 40K ?
6 No Married 60K No
10
No Married 80K ? Test
7 Yes Divorced 220K No Set
8 No Single 85K Yes
9 No Married 75K No Learn
Training
10 No Single 90K Yes Model
10

Set Classifier
 Supervised: Regression
• Predict a value of a given continuous valued variable based on the values of other
variables, assuming a linear or nonlinear model of dependency.
• Greatly studied in statistics, neural network fields.
• Examples:
– Predicting sales amounts of new product based on advetising expenditure.
– Predicting wind velocities as a function of temperature, humidity, air pressure,
etc.
– Time series prediction of stock market indices.

27
 Unsupervised: Clustering

• Given a set of data points, each having a set of attributes,

and a similarity measure among them, find clusters such
that
– Data points in one cluster are more similar to one another.
– Data points in separate clusters are less similar to one another.
• Similarity Measures:
– Euclidean Distance if attributes are continuous.
– Other Problem-specific Measures.

28
 Illustrating Clustering
Euclidean Distance Based Clustering in 3-D space.

Intracluster distances Intercluster distances

are minimized are maximized
 Clustering: Application

• Document Clustering:
– Goal: To find groups of documents that are similar to each other
based on the important terms appearing in them.
– Approach: To identify frequently occurring terms in each
document. Form a similarity measure based on the frequencies of
different terms. Use it to cluster.
– Gain: Information Retrieval can utilize the clusters to relate a
new document or search term to clustered documents.
Example: Google Scholar

30
 Unsupervised Learning: Association Rule Discovery:
Application

• Supermarket shelf management.

– Goal: To identify items that are bought together by sufficiently
many customers.
– Approach: Process the point-of-sale data collected with barcode
scanners to find dependencies among items.
– A classic rule --
• If a customer buys diaper and milk, then he is very likely to buy beer.
• So, don’t be surprised if you find six-packs stacked next to diapers!

31
 Reinforcement Learning

• Topics:
– Policies: what actions should an agent take in a particular situation
– Utility estimation: how good is a state (used by policy)
• No supervised output but delayed reward
• Credit assignment problem (what was responsible for the outcome)
• Applications:
– Game playing
– Robot in a maze
– Multiple agents, partial observability, ...

32
 A Learning Puzzle

Definitions Motivation Examples Learning Problem Components of Learning Types of Learning Puzzle 33
Takeaway

https://learning.acm.org/webinar_pdfs/PedroDomingos_FTFML_WebinarSlides.pdf
34
Most of the knowledge in the world in the future is going
to be extracted by machines and will reside in machines.
Yann LeCun, Director of AI Research, Facebook

35
The Five Tribes of Machine Learning

Pedro Domingos, University of Washington

https://learning.acm.org/webinar_pdfs/PedroDomingos_FTFML_WebinarSlides.pdf
36
 Thank You.
Next Lecture - Exploratory Data Analysis

37