Transcript Getting a Machine to Fly_Learn - Refresh AV v1

Getting a Machine to Fly Learn
Extending Our Reach Beyond Our Grasp
Daniel L. Silver
Acadia University,
Wolfville, NS, Canada
[email protected]
1
Intelligent Information Technology Research Lab, Acadia University, Canada
2
Intelligent Information Technology Research Lab, Acadia University, Canada
Key Take Away



A major challenge in artificial intelligence has
been how to develop common background
knowledge
Machine learning systems are beginning to
make head-way in this area
Taking first steps to capture
knowledge that can be used
for future learning, reasoning,
etc.
3
Intelligent Information Technology Research Lab, Acadia University, Canada
Outline






Learning – What is it?
History of Machine Learning
Framework and Methods
ML Application Areas
Recent and Future Advances
Challenges and Open Questions
4
Intelligent Information Technology Research Lab, Acadia University, Canada
What is Learning?

Animals and Humans
①
②
③

Learn using new experiences and prior
knowledge
Retain new knowledge from what is learned
Repeat starting at 1.
Essential to our survival and thriving
5
Intelligent Information Technology Research Lab, Acadia University, Canada
What is Learning?
(A little more formally)

Inductive inference/modeling



Developing a general model/hypothesis from
examples
Objective is to achieve good generalization for
making estimates/predictions
It’s like … Fitting a curve to data


Also considered modeling the data
Statistical modeling
7
Intelligent Information Technology Research Lab, Acadia University, Canada
What is Learning?

Generalization through learning is not
possible without an inductive bias
= a heuristic beyond the data
Intelligent Information Technology Research Lab, Acadia University, Canada
Inductive Bias
ASH ST
FIR ST
ELM ST
PINE ST
Human learners use Inductive Bias
SEC OND
THI RD
Inductive bias depends upon:
• Having prior knowledge
• Selection of most related
knowledge
OAK ST
9
Intelligent Information Technology Research Lab, Acadia University, Canada
What is Learning?

Requires an inductive bias
= a heuristic beyond the data

Do you know any inductive biases?

How do you choose which to use?
Intelligent Information Technology Research Lab, Acadia University, Canada
Inductive Biases





Universal heuristics - Occam’s Razor
Knowledge of intended use – Medical
diagnosis
Knowledge of the source - Teacher
Knowledge of the task domain
Analogy with previously learned tasks
Tom Mitchell, 1980
Intelligent Information Technology Research Lab, Acadia University, Canada
What is Machine Learning?

The study of how to build computer
programs that:



Improve with experience
Generalize from examples
Self-program, to some extent
Intelligent Information Technology Research Lab, Acadia University, Canada
History of Machine Learning
Origins
William
James,
Neuronal
learning
1890
Promise
Hiatus
Donald Hebb,
Math models,
The Perceptron
Limited value
1940
1950
Minsky &
Papert
paper,
Research
wanes
1960
Exploration Renaissance AI Success
Genetic alg,
Version
spaces,
Decision
Trees
1970
PDP Group
Multi-layer
Perceptrons,
New apps
1980
Intelligent Information Technology Research Lab, Acadia University, Canada
Data mining,
Web mining,
User models,
New alg.,
Google
1990
2000
Advances
Big Data,
Web Analytics,
Parallel alg.,
Cloud comp.,
Deep learning
Present
Of Interest to Several Disciplines







Computer Science – theory of computation, new
algorithms
Math - advances in statistics, information theory
Psychology – as models for human learning, knowledge
acquisition and retention
Biology – how does a nervous system learn
Physics – analogy to physical systems
Philosophy – epistemology, knowledge acquisition
Application Domains – new knowledge extracted from
data, solutions to unsolved problems
17
Intelligent Information Technology Research Lab, Acadia University, Canada
Classes of ML Methods

Supervised – Develops models that predict the value of
one variable from one or more others:


Unsupervised – Generates groups or clusters of data
that share similar features


K-Means, Self-organizing Feature Maps
Reinforcement Learning – Develops models from the
results of a final outcome; eg. win/loss of game


Artifical Neural Networks, Inductive Decision Trees, Genetic
Algorithms, k-Nearest Neighbour, Bayesian Networks, Support
Vectors Machines
TD-learning, Q-learning (related to Markov Decision Processes)
Hybrids – eg. semi-supervised learning
Intelligent Information Technology Research Lab, Acadia University, Canada
Focus: Supervised Learning

Function approximation
f(x)
(curve fitting)
x

Classification (concept learning, pattern
recognition)
A
x2
B
x1
21
Intelligent Information Technology Research Lab, Acadia University, Canada
Supervised Machine Learning
Framework
Testing
Examples
Instance Space
X
(x, f(x))
Training
Examples
Inductive
Learning System
Model of
Classifier
h
h(x) ~ f(x)
23
Intelligent Information Technology Research Lab, Acadia University, Canada
Supervised Machine Learning


Problem: We wish to learn to classifying two people
(A and B) based on their keyboard typing.
Approach:


Acquire lots of typing examples from each person
Extract relevant features - representation!





M = number of mistakes
T = typing time
Transform feature representation as needed
Use an algorithm to fit a model to the data - search!
Test the model on an independent set of examples of typing from
each person
Intelligent Information Technology Research Lab, Acadia University, Canada
1
Classification
Y
0
Logistic Regression
Y=f(M,T)
Y
B
B
B
B
B
B
B
B
Mistakes
B
B
B
B
BB
B
B
B
B
B A
B
B
A
B
A
A
A
A
A
B
M
A
A
B
B
A
B
B
B
A
A
Typing Speed
Intelligent Information Technology Research Lab, Acadia University, Canada
B
A
A
A
A
A
A
A
T
Classification
Artificial Neural Network
B
B
B
B
B
B
B
B
Mistakes
B
B
BB
B
B
B
B
B A
B
B
A
A
A
A
A
A
B
B
A
A
B
B
A
B
A
A
Typing Speed
Intelligent Information Technology Research Lab, Acadia University, Canada
…
B
B
B
B
Y
B
A
A
A
A
A
A
A
M
T
Root
Classification
M?
T?
T?
B
A
Inductive Decision Tree
B
B
B
B
B
B
B
B
Mistakes
B
B
B
B
BB
B
B
B A
B
B
A
A
A
A
A
A
B
B
B
A
A
Typing Speed
Intelligent Information
Technology Research Lab,
Blood Pressure
Example
B
A
A
B
B
A
B
B
B
Acadia University, Canada
B
A
A
A
A
A
A
A
Leaf
Application
Areas
Data Mining:







Science and medicine: prediction, diagnosis, pattern
recognition, forecasting
Manufacturing: process modeling and analysis
Marketing and Sales: targeted marketing, segmentation
Finance: portfolio trading, investment support
Banking & Insurance: credit and policy approval
Security: bomb, iceberg, fraud detection
Engineering: dynamic load shedding, pattern recognition
31
Intelligent Information Technology Research Lab, Acadia University, Canada
Application Areas





Web mining – information filtering and classification,
social media predictive modeling
User Modeling – adaptive user interfaces,
speech/gesture recognition
Intelligent Personal Agents – email spam
filtering, fashion consultant,
Robotics – image recognition, adaptive control,
autonomous vehicles (space, under-sea)
Military/Defense – target acquisition and classification,
tactical recommendations, cyber attack detection
32
Intelligent Information Technology Research Lab, Acadia University, Canada
Recent and Future Advances







Robotics
Neuroprosthetics
Lifelong Machine Learning
Deep Learning Architectures
ML and Growing Computing Power
NELL – Never-Ending Language Learner
Cloud-based Machine Learning
33
Intelligent Information Technology Research Lab, Acadia University, Canada
OASIS: Onboard Autonomous
Science Investigation System



Since early 2000’s
Goal: To evaluate,
and autonomously
act upon, science
data gathered by
spacecraft
Including planetary
landers and rovers
34
Intelligent Information Technology Research Lab, Acadia University, Canada
DARPA Grand
Challenge 2005




Stanford’s Sebastian Thrun holds a $2M check on top of
Stanley, a robotic Volkswagen Touareg R5
212 km autonomus vehicle race, Nevada
Stanley completed in 6h 54m
Four other teams also finished
Source: Associated Press – Saturday, Oct 8, 2005
35
Intelligent Information Technology Research Lab, Acadia University, Canada
The Competition
36
Intelligent Information Technology Research Lab, Acadia University, Canada
Autonomous Underwater Vehicles
Arctic Explorer



AUV designed and built by International
Submarine Engineering Ltd. (ISE) of
Port Coquitlam, B.C.
Used to map the sea floor underneath
the Arctic ice shelf in support of
Canadian land claims under the UN
Convention on the Law of the Sea.
Various military uses; e.g. mine
detection, elimination
(Source: ISE, Mae Seto)
37
Intelligent Information Technology Research Lab, Acadia University, Canada
Literally Extending Our Reach
– Neuroprosthetic Decoders






Dec, 2012
Andy Schwart,
Univ. of Pittsburgh
Jan Scheuermann,
quadriplegic
Brain-machine
interface, 96
electrodes
13 weeks of
training
High-performance neuroprosthetic
control by an individual with tetraplegia,
The Lancet, v381, p557-654, Feb 2013
39
Intelligent Information Technology Research Lab, Acadia University, Canada
Lifelong Machine Learning (LML)


Considers methods of retaining and using
learned knowledge to improve the effectiveness
and efficiency of future learning
We investigate systems that must learn:




From impoverished training sets
For diverse domains of tasks
Where practice of the same task happens
Applications:

Intelligent Agents, Robotics, User Modeling, DM
40
Intelligent Information Technology Research Lab, Acadia University, Canada
Supervised Machine Learning
Framework
Testing
Examples
Instance Space
X
(x, f(x))
Training
Examples
After model is developed
and used it is thrown away.
Inductive
Learning System
Model of
Classifier
h
h(x) ~ f(x)
41
Intelligent Information Technology Research Lab, Acadia University, Canada
Lifelong Machine Learning
Framework
Testing
Examples
Instance Space
X
Domain
Knowledge
long-term memory
(x, f(x))
Knowledge
Transfer
Training
Examples
Inductive
Bias
Retention &
Consolidation
Selection
Inductive
Learning System
short-term memory
Model of
Classifier
h
h(x) ~ f(x)
42
Intelligent Information Technology Research Lab, Acadia University, Canada
Lifelong Machine Learning
Framework
Testing
Examples
Instance Space
X
Domain
Knowledge
long-term memory
(x, f(x))
Knowledge
Transfer
Training
Examples
Inductive
Bias
Retention &
Consolidation
Selection
Inductive
Learning System
short-term memory
Model of
Classifier
h
h(x) ~ f(x)
43
Intelligent Information Technology Research Lab, Acadia University, Canada
Lifelong Machine Learning
One Implementation
Instance Space
X
f2(x)
f3(x)
…
f9(x)
Domain
Knowledge
fk(x)
Testing
Examples
Consolidated
MTL
long-term memory
(x, f(x))
Knowledge
Transfer
Inductive
Bias
f1(x)
f2(x)
Training
Examples
Retention &
Consolidation
Selection
f5(x)
Model of
Classifier
h
Multiple Task
Learning (MTL)
h(x) ~ f(x)
x1
xn
Intelligent Information Technology Research Lab, Acadia University, Canada
44
An Environmental Example
16
MAE (m^3/s)
15
14
13
12
11
0
No Transfer
1
2
3
4
Years of Data Transfered
Wilmot
Sharpe
Sharpe & Wilmot
5
6
Shubenacadie
x = weather data
Stream flow rate prediction [Lisa Gaudette, 2006]
f(x) = flow rate
48
Intelligent Information Technology Research Lab, Acadia University, Canada
Lifelong Machine Learning
with csMTL
Example:
 Learning to Learn how
to transform images
 Requires methods of
efficiently & effectively


Retaining transform
model knowledge
Using this knowledge to
learn new transforms
(Silver and Tu, 2010)
52
Intelligent Information Technology Research Lab, Acadia University, Canada
Lifelong Machine Learning
with csMTL
Demo
Intelligent Information Technology Research Lab, Acadia University, Canada
55
Deep Learning Architectures

Hinton and Bengio (2007+)



Learning deep architectures of neural
networks
Layered networks of unsupervised autoencoders efficiently develop hierarchies
of features that capture regularities in
their respective inputs
Used to develop models for families of tasks
57
Intelligent Information Technology Research Lab, Acadia University, Canada
Deep Learning Architectures

Consider the problem of trying to classify
these hand-written digits.
Intelligent Information Technology Research Lab, Acadia University, Canada
Deep Learning Architectures
2
2000 top-level artificial neurons
3
0
1
2
3
4
5
6
7
8
9
Neural Network:
- Trained on 40,000 examples
- Learns:
* labels / recognize images
* generate images from labels
- Probabilistic in nature
- Demo
1
500 neurons
(higher level features)
500 neurons
(low level features)
Images of
digits 0-9
(28 x 28 pixels)
Intelligent Information Technology Research Lab, Acadia University, Canada
ML and Computing Power

Moores Law

Expected to
accelerate as the
power of computers
move to a log scale
with use of multiple
processing cores
60
Intelligent Information Technology Research Lab, Acadia University, Canada
ML and Computing Power

IBMs Watson – Jeopardy, Feb, 2011:

Massively parallel data processing system capable
of competing with humans in real-time questionanswer problems





90 IBM Power-7 servers
Each with four 8-core processors
15 TB (220M text pages) of RAM
Tasks divided into thousands of stand-alone
jobs distributed among 80 teraflops (1 trillion ops/sec)
Uses a variety of AI approaches
machine learning
including
61
Intelligent Information Technology Research Lab, Acadia University, Canada
ML and Computing Power
Andrew Ng’s work on Deep
Learning Networks (ICML-2012)
Problem:
Learn to recognize human
faces, cats, etc from unlabeled data
Dataset of 10 million images; each
image has 200x200 pixels
9-layered locally connected neural
network (1B connections)
Parallel algorithm; 1,000 machines
(16,000 cores) for three days
Building High-level Features Using Large Scale Unsupervised Learning
Quoc V. Le, Marc’Aurelio Ranzato, Rajat Monga, Matthieu Devin, Kai Chen,
Greg S. Corrado, Jeffrey Dean, and Andrew Y. Ng
ICML 2012: 29th International Conference on Machine Learning, Edinburgh,
Scotland, June, 2012.
62
Intelligent Information Technology Research Lab, Acadia University, Canada
ML and Computing Power
Results:
 A face detector that is 81.7%
accurate
 Robust to translation, scaling,
and rotation
Further results:
 15.8% accuracy in recognizing
20,000 object categories from
ImageNet
 70% relative improvement over
the previous state-of-the-art.
63
Intelligent Information Technology Research Lab, Acadia University, Canada
Never-Ending Language Learner

Carlson et al (2010)



Each day: Extracts information from the
web to populate a growing knowledge
base of language semantics
Learns to perform this task better than on
previous day
Uses a MTL approach
in which a large number
of different semantic
functions are trained
together
64
Intelligent Information Technology Research Lab, Acadia University, Canada
Cloud-Based ML - Google
https://developers.google.com/prediction/
69
Intelligent Information Technology Research Lab, Acadia University, Canada
Machine Flight vs.
Machine Learning
Factor
Machine Flight
Machine Learning
Effectiveness
Travel higher, father
Learn more things, accurately
To places not reachable
Model complex phenomena
Travel faster
Learn faster
Lower cost
Lower cost
Safe travel, beauty
Confidence, elegance
Reach the moon,
and beyond
Reach new knowledge,
solve new problems
Efficiency
Satisfaction
71
Intelligent Information Technology Research Lab, Acadia University, Canada
Thank You!



[email protected]
http://plato.acadiau.ca/courses/comp/dsilver/
http://ML3.acadiau.ca
72
Intelligent Information Technology Research Lab, Acadia University, Canada