Learn from Example and Learn Probabilistic Model

Learning from Example
and
Learning Probabilistic Model
2017.07.06(Fri)
Junya Tanaka

Agenda
• Learning from Example
oNonparametric Model
oEnsemble Learning
oPractical Machine Learning
• Learning Probabilistic Model
oStatistical Learning
oLearning with Complete Data
oLearning with Hidden Variable : The EM Algorithm

Learning from Example
2017.07.06(Fri)
Junya Tanaka

1.Nonparametric Models
• Parametric Model
oA learning model that summarizes data with a set of parameters
of fixed size (independent of the number of training examples)
oNo matter how much data you throw at a parametric model
oWhen data sets are small, it makes sense to have a strong
restriction on the allowable hypotheses, to avoid overfitting
• Nonparametric Model
oA learning model that cannot be characterized by a bounded
set of parameters
oThe problem with this method is that it does not generalize well
oeach hypothesis we generate simply retains within itself all of
the training examples and uses all of them to predict the next
example

Nearest neighbor models
• given a query xq, find the k examples that are nearest to xq
• Use the notation NN(k, xq) to denote the set of k nearest
neighbors
• To do classification
ofirst find NN(k, xq)
otake the plurality vote of the neighbors
• the decision boundary of k-nearest-neighbors classification
for k= 1 and 5 on the earthquake data
o1-nearest neighbors is overfitting
o5-nearest-neighbors is good

Distance
• The very word “nearest” implies a distance metric.
• Distances are measured with a Minkowski distance or p
norm, defined as
op=2 is Euclidean distance
op=1 is Manhattan distance
oWith Boolean attribute values, the number of attributes on
which the two points differ is called the Hamming distance
• if we change dimension I, we’ll get different nearest
neighbors while keeping the other dimensions the same
• To avoid this, it is common to apply normalization to the
measurements

Curse of dimensionality
• Nearest neighbors works very well in low-dimensional data
• Computational complexity becomes enormous if data
dimensions increases
• Generally, reduce the number of actual distance calculations
oK-d tree
oLocally sensitive hashing

Finding nearest neighbors with k-d trees
• k-d tree (k-dimensional tree)
oA balanced binary tree over data with an arbitrary number of
dimensions
• The construction of a k-d tree is similar to the construction of
a one-dimensional balanced binary tree
• Construction
oAs one moves down the tree, one cycles through the axes used
to select the splitting planes
oPoints are inserted by selecting the median of the points being
put into the subtree, with respect to their coordinates in the axis
being used to create the splitting plane.

Locality-sensitive hashing
• Locality-sensitive hashing (LSH) reduces the
dimensionality of high-dimensional data
• LSH hashes input items so that similar items map to the
same “buckets” with high probability
• LSH differs from conventional and cryptographic hash
functions because it aims to maximize the probability of a
“collision” for similar items
• Locality-sensitive hashing has much in common with data
clustering and nearest neighbor search

Nonparametric regression
• Nonparametric approaches to regression
• (a)connect the dots
oPiecewise linear nonparametric regression
• (b)3-nearest neighbors average
ok-nearest-neighbors regression

Nonparametric regression
• (c) 3-nearest-neighbors linear regression
oThis does a better job of capturing trends at the outliers, but is
still discontinuous
owe’re left with the question of how to choose a good value for k
• (d) locally weighted regression with a quadratic kernel of
width k =10

2.Ensemble Learning
• To select a collection, or ensemble, of hypotheses from the
hypothesis space and combine their predictions
• Ex.
oDuring cross-validation we might generate twenty different
decision trees, and have them vote on the best classification for
a new example
• The ensemble method provides a way to learn a much more
expressive class of hypotheses
• Three linear threshold hypotheses
• Each of which classifies positively
on the unshaded side

Boosting
• The most widely used ensemble method
• weighted training set
oIn such a training set, each example has an associated weight
wj ≥ 0.
oBoosting starts with wj =1 for all the examples
ogenerates the first hypothesis, h1
oThis hypothesis will classify some of the training examples
correctly and some incorrectly
oThe next hypothesis to do better on the misclassified examples
owe increase their weights while decreasing the weights of the
correctly classified examples
oFrom this new weighted training set, we generate hypothesis h2
ocontinues in this way until we have generated K hypotheses

Boosting
• How the boosting algorithm works
oEach shaded rectangle corresponds to an example
o the height of the rectangle corresponds to the weight
oThe checks and crosses indicate whether the example was
classified correctly by the current hypothesis
oThe size of the decision tree indicates the weight of that
hypothesis in the final ensemble.

3. Practical Machine Learning
• Introduced a wide range of machine learning techniques
• Simple learning tasks
• Consider two aspects of practical machine learning
ofinding algorithms capable of learning to recognize handwritten
digits and squeezing every last drop of predictive performance
out of them’
opointing out that obtaining, cleaning, and representing the data
can be at least as important as algorithm engineering

Case study: Handwritten digit recognition
• Example for machine learning problem

Learning Probabilistic Model
2017.07.06(Fri)
Junya Tanaka

Introduction
• We view learning as a form of uncertain reasoning from
observations
• First we must learn their probabilistic theories of the world
from experience
oThis chapter explains how they can do that, by formulating the
learning task itself as a process of probabilistic inference
oBayesian learning is extremely powerful solutions to the
problems of noise, overfitting, and optimal prediction

1. Statistical Learning
• The key concepts are data and hypotheses
oData are evidence
oInstantiations of some or all of the random variables describing
the domain
• Bayesian learning simply calculates the probability of each
hypothesis, given the data, and makes predictions
oPredictions are made by using all the hypotheses, weighted by
their probabilities
oLearning is reduced to probabilistic inference.

• Let D represent all the data, with observed value d; then the
probability of each hypothesis is obtained by Bayes’ rule
• Suppose we want to make a prediction about an unknown
quantity X. Then we have
• where we have assumed that each hypothesis determines a
probability distribution over X
• This equation shows that predictions are weighted averages
over the predictions of the individual hypotheses

• Example
oSome candy comes in two flavors cherry(yum) and lime (ugh)
owraps each piece of candy in the same opaque wrapper,
regardless of flavor
oThe candy is indistinguishable from the outside
oGiven a new bag of candy, the random variable H denotes the
type of the bag, with possible values h1 through h5
oD1, D2, . . ., DN, where each Di is a random variable with
possible values cherry and lime
oThe basic task faced by the agent is to predict the flavor of the
next piece of candy

• Apply Bayesian Learning to Candy Example
oThe prior distribution over h1, . . . , h5 is given by ⟨0.1, 0.2, 0.4,
0.2, 0.1⟩
oThe likelihood of the data
oSuppose the bag is really an all-lime bag (h5) and the first 10
candies are all lime; then P(d | h3) is 0.510, because half the
candies in an h3 bag are lime

• (a) Posterior probabilities P(hi | d1, . . . , dN)
oThe number of observations N ranges from 1 to 10, and each
observation is of a lime candy
oThe probabilities start out at their prior values
• (b) Bayesian prediction P(dN+1 =lime | d1, . . . , dN)
opredicted probability that the next candy is lime

• The example shows that the Bayesian prediction eventually
agrees with the true hypothesis
• Bayesian prediction is optimal, whether the data set be small
or large
• Given the hypothesis prior, any other prediction is expected
to be correct less often

2. Learning with Complete Data
• Density estimation
oThe general task of learning a probability model, given data that
are assumed to be generated from that model
• This section covers the simplest case, where we have
complete data
oData are complete when each data point contains values for
every variable in the probability model being learned
• Parameter learning
oFinding the numerical parameters for a probability model whose
structure is fixed

Maximum-likelihood parameter learning: Discrete models
• Suppose we buy a bag of lime and cherry candy that lime–
cherry proportions are completely unknown
oThe parameter in this case, which we call θ, is the proportion of
cherry candies, and the hypothesis is hθ
oHas values cherry and lime, where the probability of cherry is θ
oNow suppose we unwrap N candies, of which c are cherries
and ℓ=N − c are limes
othis particular data set is
oThe maximum-likelihood hypothesis is given by the value of θ
that maximizes this expression

Maximum-likelihood parameter learning: Discrete models
• To find the maximum-likelihood value of θ, we differentiate L
with respect to θ and set the resulting expression to zero:
• 1. Write down an expression for the likelihood of the data as
a function of the parameter(s).
• 2. Write down the derivative of the log likelihood with respect
to each parameter.
• 3. Find the parameter values such that the derivatives are
zero.

Naive Bayes models
• Most common Bayesian network model used in machine
learning
• the “class” variable C (which is to be predicted) is the root
and the “attribute” variables Xi are the leaves
• With observed attribute values x1, . . . , xn, the probability of
each class is given by

Maximum-likelihood parameter learning: Continuous models
• Continuous variables are ubiquitous in real-world
applications
• The principles for maximum-likelihood learning are identical
in the continuous and discrete cases
• Simple case
olearning the parameters of a Gaussian density function
othe data are generated as follows
oLet the observed values be x1, . . . , xN,then log likelihood is

• Now consider a linear Gaussian model with one continuous
parent X and a continuous child Y
• Y has a Gaussian distribution whose mean depends linearly
on the value of X and whose standard deviation is fixed
• To learn the conditional distribution P(Y |X), we can
maximize the conditional likelihood
• the log likelihood with respect to these parameters is the
same as minimizing the numerator(y − (θ1x + θ2))
• Now we can understand why: minimizing the sum of squared
errors gives the maximum-likelihood straight-line model,
provided that the data are generated with Gaussian noise of
fixed variance

Bayesian parameter learning
• The hypothesis prior
oThe Bayesian approach to parameter learning starts by defining
a prior probability distribution over the possible hypotheses
• In the Bayesian view, θ is the (unknown) value of a random
variable Θ that defines the hypothesis space
• The hypothesis prior is just the prior distribution P(Θ)
• If the parameter θ can be value between 0 and 1, then P(Θ)
must be a continuous distribution that is nonzero only
between 0 and 1 and that integrates to 1
• the uniform density is a member of the family of beta
distributions
• Each beta distribution is defined by two hyperparameters a
and b such that

• Figure shows what the distribution looks like for various
values of a and b

• Let’s see how this works. Suppose we observe a cherry
candy;

Density estimation with nonparametric models
• The task of nonparametric density estimation is typically
done in continuous domains, such as that shown in figure
• The figure shows a probability density function on a space
defined by two continuous variables
• we see a sample of data points from this density function
• can we recover the model from the samples

• Consider k-nearest-neighbors models
oGiven a sample of data points, to estimate the unknown
probability density at a query point x we can simply measure
the density of the data points in the neighborhood of x.
oFigure shows two query points (small squares)
oThe central circle is large, meaning there is a low density there
oThe circle on the right is small, meaning there is a high density
there

• Three plots of density estimation using k-nearest-neighbors
for different values of k applied to the data in previous Fig
o(b) is about right(k is midium, k = 10), while (a) is too spiky (k is
too small, k = 3) and (c) is too smooth (k is too big, k = 40)

3. Learning with Hidden Variables : EM Algorithm
• Many real-world problems have hidden variables (sometimes
called latent variables)
• Hidden variables are important, but they do complicate the
learning problem
oIt is not obvious how to learn the conditional distribution for
HeartDisease, given its parents, because we do not know the
value of HeartDisease in each case; the same problem arises
in learning the distributions for the symptoms.
• EM algorithm can solve the problems

Unsupervised clustering: Learning mixtures of Gaussians
• The problem of discerning multiple categories in a collection
of objects
• Example
osuppose we record the spectra of a hundred thousand stars
ohow many types and what are their characteristics?
oThe data points might correspond to stars
oThe attributes might correspond to spectral intensities at two
particular frequencies.
• Next, we need to understand what kind of probability
distribution might have generated the data
• Such a distribution has k components based on a mixture
distribution P, each of which is a distribution in its own right

Unsupervised clustering: Learning mixtures of Gaussians
• Let the random variable C denote the component, with
values 1, . . . , k; then the mixture distribution is given by

Learning hidden Markov models
• hidden Markov model can be represented by a dynamic
Bayes net with a single discrete state variable
• the problem is to learn the transition probabilities from a set
of observation sequences
• To estimate the transition probability from state i to state j
• we simply calculate the expected proportion of times that the system
undergoes a transition to state j when in state i:

The general form of the EM algorithm
• Let x be all the observed values in all the examples, let Z
denote all the hidden variables for all the examples, and let θ
be all the parameters for the probability model.
• Then the EM algorithm is
• The E-step is the computation of the summation, which is the
expectation of the log likelihood of the “completed” data with
respect to the distribution P(Z=z | x, θ(i))
• The M-step is the maximization of this expected log
likelihood with respect to the parameters.

Learn from Example and Learn Probabilistic Model

Recommended

More Related Content

What's hot (20)

Similar to Learn from Example and Learn Probabilistic Model (20)

Recently uploaded (20)

Learn from Example and Learn Probabilistic Model

Editor's Notes