Soft Computing Week 1

Download Report

Transcript Soft Computing Week 1

Week 1 - An Introduction to
Machine Learning & Soft
Computing
-Yosi Kristian-
Soft Computing STTS – Yosi Kristian
2
Definition
• Soft Computing is a term applied to a field within computer
science which is characterized by the use of inexact solutions
to computationally hard tasks, for which there is no known
algorithm that can compute an exact solution.
• Soft computing differs from conventional (hard) computing in
that, unlike hard computing, it is tolerant of imprecision,
uncertainty, partial truth, and approximation.
Soft Computing STTS – Yosi Kristian
3
Still the Definition..
• In effect, the role model for soft computing is the human
mind.
• The guiding principle of soft computing is: Exploit the
tolerance for imprecision, uncertainty, partial truth, and
approximation to achieve tractability, robustness and low
solution cost.
Soft Computing STTS – Yosi Kristian
4
Components of soft computing
•
•
•
•
Neural networks (NN)
Support Vector Machines (SVM)
Fuzzy logics (FL)
Evolutionary computation (EC), including:
What ???
o Evolutionary algorithms
o
Are we going to
learn them all
Meta heuristic and Swarm Intelligence
• Ant colony optimization
in this subject?
• Genetic algorithms
• Differential evolution
•
•
•
•
•
•
•
Bees algorithms
Bat algorithm
Cuckoo search
Harmony search
Firefly algorithm
Artificial immune systems
Particle swarm optimization
Soft Computing STTS – Yosi Kristian
5
Soft Computing in AI
• Soft computing may be viewed as a foundation component
for the emerging field of conceptual intelligence.
o
o
o
o
Machine Learning
Fuzzy Systems
Evolutionary Computation
Probabilistic Reasoning
• Soft Computing is the CORE component of many Machine
Learning System
Soft Computing STTS – Yosi Kristian
6
Machine Learning
• Arthur Samuel (1959). Machine Learning: Field of study that
gives computers the ability to learn without being explicitly
programmed.
• Tom Mitchell (1998) Well-posed Learning Problem: A
computer program is said to learn from experience E with
respect to some task T and some performance measure P, if
its performance on T, as measured by P, improves with
experience E.
Soft Computing STTS – Yosi Kristian
7
Machine learning usage
• Usage of Machine Learning is to develop applications
that can’t be programed by hand.
• E.g., Autonomous helicopter, handwriting recognition,
most of Natural Language Processing (NLP), Computer
Vision etc.
• Or a machine learning system could be trained on email
messages to learn to distinguish between spam and
non-spam messages. After learning, it can then be used
to classify new email messages into spam and nonspam folders.
Soft Computing STTS – Yosi Kristian
8
Machine Learning Categorized By
Data and Learning Process
Soft Computing STTS – Yosi Kristian
9
Soft Computing In Machine
Learning
• Soft Computing is the soul of many machine
learning system.
• Classification and Clustering is a very common
soft computing problems.
Soft Computing STTS – Yosi Kristian
10
Intro to Supervised Learning
Soft Computing STTS – Yosi Kristian
11
Example
Housing price prediction.
400
300
Price ($)
200
in 1000’s
100
0
0
500
1000
1500
2000
2500
Size in feet2
Supervised Learning
“right answers” given
Soft Computing STTS – Yosi Kristian
Regression: Predict continuous
valued output (price)
12
Example
Breast cancer (malignant, benign)
Classification
Discrete
valued output
(0 or 1)
1(Y)
Malignant?
0(N)
Tumor Size
Tumor Size
Soft Computing STTS – Yosi Kristian
13
Another Example
- Clump Thickness
- Uniformity of Cell
Size
- Uniformity of Cell
Shape
…
Age
Tumor Size
Soft Computing STTS – Yosi Kristian
14
Exercise
• You’re running a company, and you want to develop learning
algorithms to address each of two problems.
• Problem 1: You have a large inventory of identical items. You
want to predict how many of these items will sell over the
next 3 months.
• Problem 2: You’d like software to examine individual customer
accounts, and for each account decide if it has been
hacked/compromised.
• Should you treat these as classification or as regression
problems?
Soft Computing STTS – Yosi Kristian
15
Answer
• Treat both as classification problems.
• Treat problem 1 as a classification problem, problem 2 as a
regression problem.
• Treat problem 1 as a regression problem, problem 2 as a
classification problem.
• Treat both as regression problems.
Soft Computing STTS – Yosi Kristian
16
Classification Example
• Another Example is for image Classification / Categorization
Training
Training
Images
Image
Features
Training
Labels
Classifier
Training
Trained
Classifier
Soft Computing STTS – Yosi Kristian
17
Cont…
Testing
Image
Features
Trained
Classifier
Test Image
Prediction
Outdoor
Soft Computing STTS – Yosi Kristian
18
Learning a classifier
• Given some set of features with corresponding labels, learn a
function to predict the labels from the features
• Training labels dictate that two examples are the same or
different, in some sense
• Features and distance measures define similarity
• Classifiers try to learn weights or parameters for features and
distance measures so that feature similarity predicts label
similarity
Soft Computing STTS – Yosi Kristian
19
Intro to Unsupervised Learning
Soft Computing STTS – Yosi Kristian
20
Supervised Learning
x2
x1
Soft Computing STTS – Yosi Kristian
21
Unsupervised Learning
x2
x1
Soft Computing STTS – Yosi Kristian
22
Clustering Example
Soft Computing STTS – Yosi Kristian
23
Contd…
Soft Computing STTS – Yosi Kristian
24
Exercise
Of the following examples, which would you address using an
unsupervised learning algorithm? (Check all that apply.)
o Given email labeled as spam/not spam, learn a spam filter.
o Given a set of news articles found on the web, group them into set of
articles about the same story.
o Given a database of customer data, automatically discover market
segments and group customers into different market segments.
o Given a dataset of patients diagnosed as either having diabetes or not,
learn to classify new patients as having diabetes or not.
Soft Computing STTS – Yosi Kristian
25
Warming Up….
• Do 10 x Push Ups.
Soft Computing STTS – Yosi Kristian
26
Linear Regression with one variable
Housing Prices
(Portland, OR)
500
400
300
Price 200
(in 1000s 100
of dollars) 0
0
500
1000
1500
2000
2500
3000
Size (feet2)
Supervised Learning
Regression Problem
Given the “right answer”
for each example in the
data.
Predict real-valued output
Soft Computing STTS – Yosi Kristian
27
Linear Regression with one variable
Training set of
housing prices
(Portland, OR)
Notation:
m = Number of training examples
n = Number of feature
x’s = “input” variable / features
y’s = “output” variable / “target” variable
Soft Computing STTS – Yosi Kristian
28
The Concept
How do we represent h ?
Training Set
Learning Algorithm
Size of
house
h
Estimate
d price
Linear regression with one variable.
Univariate linear regression.
Soft Computing STTS – Yosi Kristian
29
Cost Function
Training Set
Hypothesis:
‘s:
Parameters
How to choose
Soft Computing STTS – Yosi Kristian
‘s ?
30
Contd..
3
3
3
2
2
2
1
1
1
0
0
0
0
1
2
3
Soft Computing STTS – Yosi Kristian
0
1
2
3
0
1
2
3
31
Cost Function..
y
x
Idea: Choose
so that
is close to for
our training examples
Soft Computing STTS – Yosi Kristian
32
Simplification: For the sake of
understanding
Hypothesis:
Simplified
Parameters:
Cost Function:
Goal:
Soft Computing STTS – Yosi Kristian
33
Trial 1
(for fixed
, this is a function of x)
(function of the parameter
3
3
2
2
1
1
0
0
-0.5 0
y
0
1
x
2
Soft Computing STTS – Yosi Kristian
3
0.5
1
1.5
)
2
2.5
34
Trial 2
(for fixed
, this is a function of x)
(function of the parameter
3
3
2
2
1
1
0
0
-0.5 0
y
0
1
x
2
Soft Computing STTS – Yosi Kristian
3
0.5
1
1.5
)
2
2.5
35
Trial 3
(for fixed
, this is a function of x)
(function of the parameter
3
3
2
2
1
1
0
0
-0.5 0
y
0
1
x
2
Soft Computing STTS – Yosi Kristian
3
0.5
1
1.5
)
2
2.5
36
Done with simplification, back to
real world.
Hypothesis:
Parameters:
Cost Function:
Goal:
Soft Computing STTS – Yosi Kristian
37
The Contour Figures ….
How to find minimum of J
in that?
Soft Computing STTS – Yosi Kristian
38
Gradient Descent..
• Next Week…
Soft Computing STTS – Yosi Kristian
39