CS计算机代考程序代写 algorithm deep learning Outline

Outline
Covered content:
� Products of Experts (PoE)
� Restricted Boltzmann Machine (RBM) � Structure of an RBM
� RBM learning algorithms
� Application of RBMs
Reference:
� Hinton, Geoffrey E. (2002). ”Training Products of Experts by Minimizing Contrastive Divergence” (PDF). Neural Computation. 14 (8): 1771–1800
1/24

Beyond Clustering
Mixture model Product of experts (last week’s lecture) (today’s lecture)
2/24

Mixture model vs. Product of experts
Mixture Model: Mixture models are commonly used for clustering problems and the probability is defined as a weighted sum of probability distributions:
�C
αk ·p(x|θk)
with αk denoting the mixing coefficients subject to the constraints �Ck=1 αk = 1 and αk ≥ 0.
Product of Experts (PoE): Products of experts are commonly used for learning dis- tributed representations (e.g. unsupervised feature extraction) and are defined as a product
of functions.
p(x|θ) =
where Z is a normalization term set to ensure that p(x|θ) integrates to 1.
p(x|α,θ)=
k=1
1 �H
g(x|θj ) Z j=1 � �� �
jth expert
3/24

Example 1: Product of Gaussians
Consider the experts to be univariate Gaussians spe- cialized on a particular input dimension
g(x|θi) = 1 exp � − (xi − μi)2 � (2π σi2 )1/2 2σi2
The product of experts (PoE) can be developed as:
�d
p(x|θ) = g(x|θi)
i=1 � � = 1 exp − 1(x−μ)�Σ−1(x−μ)
with Σ = diag(σ12 , . . . , σd2 ), i.e. a multivariate Gaussian distribution without correlation between features.
(2π)d/2|Σ|1/2 2
4/24

Example 2: Product of Gaussian Mixtures
Let the experts be the univariate mixtures:
�C k=1
π−1/2 exp(−(xi − μik)2)
g(x|θi) =
The product of experts (PoE) can be developed as:
1 �d �C
p(x|θ) = Z π−1/2 exp(−(xi − μik)2)
i=1 k=1
1�C �C�d
= Z ··· π−1/2 exp(−(xi −μiki)2) k1=1 kd=1 i=1
� �� �
multivariate Gaussian
i.e. a mixture of exponentially many (Cd) multivariate Gaussians. Therefore, a PoE can encode many varia- tions with few parameters.
5/24

Example 3: Product of t-Student Distributions
Define experts to be t-Student distributions in some projected space (z = wj�x):
g(x|θj) = 1 �wj� = 1 α j + ( w j� x ) 2
The resulting product of experts
p ( x | θ ) = 1 �H 1
with H the number of experts, produces a non-Gaussian multivariate distribution, which can be useful to model e.g. image or speech data. This PoE has connections to other analyses, e.g. independent component analysis (ICA).
Zj=1αj +(wj�x)2
6/24

The Restricted Boltzmann Machine
latent 0 1 0 0 1 1
input 01001
The restricted Boltzmann machine (RBM) is a joint probability model defined over input
features x ∈ {0, 1}d and latent variables h ∈ {0, 1}H .
1��d�H �H� p(x,h|θ) = Z exp xiwijhj + bjhj
i=1 j=1 j=1
The parameter wij can be interpreted as the connection strength between input feature xi and latent variable hj. The larger wij the stronger xi and hj co-activate.
7/24

The Restricted Boltzmann Machine (PoE View)
Connection between RBM and PoE
The RBM, when marginalized over its hidden units, has the structure of a Product of Experts with g(x, θj ) = (1 + exp(wj�x + bj )).
Proof:

p(x|θ) = =
p(x, h|θ)
�1��d�H �H�
h∈{0,1}d
h∈{0,1}d i=1 j=1 j=1
Z exp xiwijhj + bjhj 1 � �H
= Z exp((wj�x+bj)·hj) h∈{0,1}d j=1
=1�H � exp((wj�x+bj)·hj) Z j=1 hj ∈{0,1}
1 �H
= Z (1+exp(wj�x+bj))
j=1
8/24

Interpreting the RBM Experts
The experts
g(x, θj ) = 1 + exp(wj�x + bj )
forming the RBM implement two behaviors:
� wj�x+bj >0:g(x;θj)�1: theexamplexisin the area of competence of the expert and the latter speaks in favor of x.
� wj�x+bj <0:g(x;θj)≈1: theexamplexis outside the expert’s area of competence, and the expert ‘withdraws’, i.e. multiplies by 1. This double behavior is important to implement the nonlinearity. 9/24 RBM as a Neural Network The product of expert (PoE) model 1 �H softplus p(x|θ) = Z (1 + exp(wj�x + bj)) j=1 x can be rewritten as: �H j=1 � �� � f ( x ) log(1+exp(wj�x+bj))−logZ � softplus�� � f(x,θ) logp(x|θ) = where f(x,θ) can be interpreted as a neural network. w Note: The neural network can predict which examples x are more probable relative to other examples, but not the actual probability score, because log Z is difficult to compute. 10/24 ∑ RBM as a Neural Network RBM trained on MNIST digits (only digits “3” with 100-125 foreground pixels). 2% least likely 2% most likely Observations: � Digits with anomalies are predicted the RBM to be less likely than clean digits. 11/24 ������������������������ ������������������������������������� ���������������� ��� ��� ��� ��� ��� RBM as a Neural Network Universal approximation The RBM is an universal approximator of data distributions in the binary input space {0, 1}d. “Proof” by construction: Add a softplus neuron pointing to each corner of the hypercube. Scale the weight wj according to the probability of each corner, and choose the bias accord- ingly. Note: This construction requires exponentially many neurons. In practice, each expert θj captures more than a single corner of the hypercube (i.e. learn general features). 12/24 RBM as a Neural Network RBM weights ((wj)Hj=1) K-Means centroids Observation � In the RBM, experts (wj)j encode only part of the digit (e.g. a stroke). The expert therefore contributes to make all data containing that particular stroke more likely. � The experts that the RBM extracts can be used for transfer learning, e.g. reused to predict different digits/characters. � K-means centroids are much more localized, and consequently less transferable. 13/24 Learning an RBM Recap: mixture model (EM bound) The mixture model can be optimized by finding the optimum of a lower-bound at each iteration �N logp(D|θ)= n=1 log �C α k p ( x n | θ k ) β βk ≥ �N �C n=1 k=1 log � α k p ( x n | θ k ) � β βk k k=1 k where N is the number of data points, and (αk)k and (βk)k are distributions over the C mixture elements. Question: Can the same EM approach be used for Product of Experts? logp(D|θ)=�N �f(xn,θ)−logZ� n=1 Answer: No, the expression cannot be bounded in the same way as for the mixture model (it has a different structure). 14/24 Gradient of the RBM Idea: Although EM is not applicable, we can still compute the gradient of the log-likelihood and perform gradient descent. ∂ logp(D|θ)= ∂ �N �f(xn,θ)−logZ� ∂θ ∂θ n=1 ∂�N� �� � = ∂θ f(xn,θ)−log exp(f(x,θ)) n=1 x∈{0,1}d ��� �N ∂ x∈{0,1}d exp(f(x,θ)) ∂ f(x,θ) = f(xn,θ)− � ∂θ n=1 ∂θ x∈{0,1}d exp(f(x,θ)) N∂�∂� ∂θf(xn,θ)−NEx∼p(x|θ) ∂θf(x,θ) The gradient is a difference between a data-dependent and a model-dependent term. = n=1 15/24 RBM Update Rule Based on the gradient calculation above, we can build the update rule: Interpretation: θ←θ+γ·�1 �N ∂f(xn,θ)−Ex∼p(x|θ)�∂f(x,θ)�� N n=1 ∂θ ∂θ � The first term makes the data more likely according to the model. � The second term makes everything that the model considers likely, less likely. � The training procedure terminates when we reach some equilibrium. p(x) data data 16/24 Computation of the RBM update rule θ←θ+γ·�1 �N ∂f(xn,θ)−Ex∼p(x|θ)�∂f(x,θ)�� N n=1 ∂θ ∂θ Observations � The left hand side is easy to compute (backprop in f(x,θ), averaged over all data points). � The right hand side is more tricky, because p(x|θ) is defined over exponentially many states. An unbiased approximation of the expected gradient can be obtained by generating a sample {x1, . . . , xm} from the model distribution p(x|θ). Question: How do we sample from p(x|θ)? � Idea: Switch back to the ‘classical’ (i.e. non-PoE) view of the RBM, where we can use latent variables to ease sampling. 17/24 Recap: ‘Classical’ View of the RBM latent 0 1 0 0 1 1 input 01001 The RBM is a probability model defined over input features x ∈ {0, 1}d and and latent variables h ∈ {0, 1}H . 1��d�H �H� p(x,h|θ) = Z exp xiwijhj + bjhj i=1 j=1 j=1 The parameter wij can be interpreted as the connection strength between input feature xi and latent variable hj. The larger wij the stronger xi and hj co-activate. 18/24 Conditional Distributions in an RBM Sampling p(x) and p(h) is hard, however, hidden variables h can be sampled easily and indep�endently when we condition on the state x, and similarly for x conditioned on h. Let zj= ixiwij+bj.Weproceedas: 1 exp��zjhj� �exp(zjhj) � Z j j exp(zjhj) p(h|x,θ)= � 1 exp��z h � = ��exp(z h ) = 1+exp(zj) Z jj jj j���� h j j hj p(hj|x,θ) and we observe that, conditioned on x, the latent variables (hj)j can be sampled easily (Bernoulli distributions) and independently. By symmetry of the RBM model, we get a similar result for the visible �units conditioned on thelatentvariables,i.e.p(xi|h,θ)=exp(zihi)/(1+exp(zi))withzi = jwijhj. 19/24 Block Gibbs Sampling Observation: We know p(hj |x, θ) and p(xi|h, θ). But how do we sample p(x|θ), which we need to compute the RBM gradient? Block Gibbs Sampling: Start with some ran- dom input x(0), then sample alternately: h(0) ∼ �p(hj | x(0), θ)�Hj=1 x(1) ∼ �p(xi | h(0), θ)�di=1 h(1) ∼ �p(hj | x(1), θ)�Hj=1 x(2) ∼ �p(xi | h(1), θ)�di=1 . until x(·) converges in distribution to p(x|θ). 20/24 Fast Approximations In practice, Gibbs sampling can take a long time to converge. Instead, we can use fast approximations of converged Gibbs sampling. Common approximation strategies: � Contrastive divergence (CD-k): Start from an existing data point, and perform k steps of alternate Gibbs sampling. � Persistent contrastive divergence (PCD): Start from the Gibbs sample x in the previous iteration of gradient descent, and perform one step of Gibbs sampling. 21/24 Application: RBM for Data Denoising Before denoising Suppose you receive an example xnoisy, and would like to denoise it. A reconstruction of that digit can be obtained by mapping to the latent variables and projecting back: 1. Projection on latent variables h = sigm(W xnoisy + b) 2. Backprojection on the input domain xrec = sigm(W�h) After denoising 22/24 Application: RBM for Representation Learning The RBM model can be used as a neural net- work initialization to achieve lower generaliza- tion error on some classification task. � Step 1: Create a layer of features based on the RBM learned parameters: MNIST example: sigm(w1� x) φ(x) =  .  sigm(wH� x) � Step 2: Add a top layer that maps φ(x) to the class probabilities, and train the resulting neural network end-to-end using gradient descent. Source: Erhan et al. (2010) Why Does Unsuper- vised Pre-training Help Deep Learning? 23/24 Summary � The Product of Experts is an unsupervised learning approach that is substantially different from Mixture Models. � Product of experts such as the RBM are optimized by gradient descent (instead of EM). � The RBM has several desirable properties: Simple gradient, block Gibbs sampler (quite fast). � The RBM can be used for various tasks, e.g. probability modeling, data denoising, representation learning. 24/24