CS计算机代考程序代写 decision tree algorithm Bayesian AI GMM deep learning lecture/12-em-annotated.pdf

lecture/12-em-annotated.pdf

lecture/13-poe-annotated.pdf

lecture/14-xai-annotated.pdf

lecture/lecture1-annotated.pdf

lecture/lecture10.pdf

lecture/lecture11.pdf

1/24

Outline

� Latent Variable Models
� The Expectation Maximization Procedure
� Gaussian Mixture Models
� K-Means Clustering
� Kernel K-Means

2/24

Motivation

PCA of Iris dataset PCA of Boston dataset

PCA of Diabetes dataset PCA of Digits dataset

Complex data cannot be modeled accurately by standard probability distributions
(e.g. Gaussian) and require a more complex description, e.g. with latent variables.

3/24

Latent Variable Models

A latent variable model (LVM) is a description of the data distribution that makes
use of a layer of abstraction (latent variables) to improve modeling capability.

p(x|z,θ)

p(z|θ)

dataxdata

“Classical”
descrip�on

Latent variable
descrip�on

p(x|θ)

Relation between the ‘classsical’ and latent variable description:

p(� |θ) =
�

z∈Z
p(z |θ) · p(� |z , θ).

4/24

Learning a Latent Variable Model

Assuming a dataset D where we assume that the samples have been drawn i.i.d..
In that case, the log-likelihood of the data according to the model can be written
as:

logP(D|θ) = log
�

�∈D
p(� |θ)

=
�

�∈D
log p(� |θ)

and we wish to maximize that quantity. Injecting the latent variable model, the
objective to optimize becomes

=
�

�∈D
log

�

z∈Z
p(z |θ) · p(� |z , θ)

Problem: The maximum of log p(D|θ) cannot be found analytically.

5/24

Learning a Latent Variable Model

Strategy: If the function p(D|θ) cannot be easily optimized, find a lower-bound
of that function that is easier to optimize.

6/24

Building a Lower-Bound

Jensen’s inequality

For any element λ of the d-dimensional simplex (i.e. λ � 0 and λ�1 = 1, and
any concave function f : Rd → R, we have

f (
d�

i=1

λiai ) ≥
d�

i=1

λi f (ai )

Application to the latent variable model:

� Let λ be some probability distribution q(z |�) independent from θ.
� Let �i containing the remaining terms.
� Because the latent variable model

�
�∈D log

�
z∈Z p(z |θ) · p(� |z , θ) does

not contain such distribution q(z |�) independent from θ, create it!

7/24

Building a Lower-Bound

Step 1: Add q(z |�) both on the numerator and denominator:

log p(D|θ) =
�

�∈D
log

�

p(z |θ) · p(� |z , θ)
q(z |�) · q(z |�)

Step 2: Applying the Jensen inequality

≥
�

�∈D

�

log
�
p(z |θ) · p(� |z , θ)

q(z |�)
�
· q(z |�)

… and verify the bound:

=
�

�∈D

�

log
�
p(� |θ) · p(z |� , θ)

q(z |�)
�
· q(z |�)

=
�

�∈D

�

log
�
p(� |θ)

�
· q(z |�)

� ��
log P(D|θ)

−
�

�∈D

�

log
�

q(z |�)
p(z |� , θ)

�
· q(z |�)

� ��
KL(q(z|�) � p(z|�,θ))≥ 0

8/24

Building a Lower-Bound

Question: How to ensure that

KL(q(z |�) � p(z |� , θ))

is small, so that maximizing the lower-bound with θ gives a good approximation
of the true log-likelihood?

Chicken & egg problem:

� If we use a simple q, e.g. uniformly distributed, we get a loose
lower-bound from which we get a bad θ.

� To get a tight lower-bound, we need to choose q(z |�) ≈ p(z |� , θ) which
requires that we know θ.

9/24

The Expectation-Maximization (EM) Algorithm

Strategy: Start with some random solution θ and alternately estimate q and θ,
until we converge.

10/24

The Expectation-Maximization (EM) Algorithm

θ0 ← random()

q1(z |�) ← p(z |� , θ0) (E-step)

θ1 ← argmax
θ

�

�∈D

�

log
�
p(� , z |θ)
q1(z |�)

�
· q1(z |�) (M-step)

q2(z |�) ← p(z |� , θ1) (E-step)

θ2 ← argmax
θ

�

�∈D

�

log
�
p(� , z |θ)
q2(z |�)

�
· q2(z |�) (M-step)

…

11/24

The Expectation-Maximization (EM) Algorithm

(θ0,q1)

(θn,qn)

Properties of the algorithm:

� Block coordinate descent
� Locally optimal step size
� The algorithm lands in a local

minimum of the function p(D|θ).

Advantages of EM compared to gradient
descent:

� no learning rate
� no need to compute the gradients.

12/24

Application: Cluster Analysis

PCA of Iris dataset PCA of Boston dataset

PCA of Diabetes dataset PCA of Digits dataset

Question: Can we build a model of the cluster structure of the data?

13/24

The Gaussian Mixture Model (GMM)

� The Gaussian Mixture Model is a latent variable model specialized for
clustering.

p(x|z,θ)

p(z|θ)

data

Latent variable
descrip�on
(general
formula�on)

p(x|z=i,θ)

p(z=i|θ)

data

Gaussian
mixture
model

i=1 i=2 i=3 i=4

� The latent variable z of a GMM is an integer between 1 and C . Each
value of z indicates a cluster of the data.

� For each cluster, we associate a different data-generating distribution
(e.g. Gaussian with different means and covariances).

14/24

The Gaussian Mixture Model (GMM)

The GMM is formally defined by the two equations:

p(z = i |θ) = αi

p(� |z = i , θ) = (2π)−d/2 · |Σi |−1/2 · exp
�
− 1

2
(� − µi )

�
Σ

−1
i (x − µi )

�

The parameters θ of the model to be learned are:

� The mixing coefficients (αi )Ci=1 subject to αi ≥ 0 and
�C

i=1
αi = 1

� The mean vectors (µi )
C
i=1.

� The covariances (Σi )Ci=1 subject to positive semi-definiteness.

Various simplifications of the GMM model can be used in practice, e.g. for
speed, statistical robustness, or simplicity of implementation.

� diagonal/isotropic/tied/fixed covariance matrices,
� fixed mixing coefficients, etc.

15/24

EM for the GMM (simplified)

Consider the simplified GMM:

p(z = i |θ) = 1
C

p(� |z = i , θ) = 1
(π/γ)d/2

exp(−γ�� − µi�
2
)

E-step: (Apply Bayes rule)

q(z = i |�) = p(z = i |θ) · p(� |z = i , θ)
p(� |θ) =

exp(−γ�� − µi�2)�C
i=1

exp(−γ�� − µi�2)

M-step: (Set lower-bound gradient to zero)

∂

∂θ

�

�∈D

C�

i=1

log(exp(−γ�� − µi�
2
)) · q(z = i |�) = 0

⇒ µi =
�

�∈D � · q(z = i |�)�
�∈D q(z = i |�)

16/24

Implementing GMMs

The (simplified) GMM model can be implemented easily in few lines of code:

17/24

GMM Demo (1st try)

��

�

��

�

��

�

��

�

��

�

��

�

��

18/24

GMM Demo (2nd try)

��

�

��

�

��

�

��

�

��

�

��

�

��

19/24

Gaussian Mixture Model (Summary)

� Number of clusters need to be determined in advance.
� EM converge to some local minima after a few iterations
� EM is non-convex, initialization matters.
� For a better result, run the algorithm multiple times and retain the best

solution.

20/24

The K-Means Algorithm

Cluster assignments step

c(�) = argmin
k

�� − µk�
2

Centroid update step

µk =

�
� :c(�)=k

�

�
� :c(�)=k

� K-means can be interpreted as the limit case of EM for Gaussian
distributions with γ → ∞.

� K-means produces hard-assignments (i.e. data points belong to a single
cluster).

� K-means has the same limitations as GMM (non-convex, predefined
cluster shape).

� K-means has only one parameter: the number of clusters.

21/24

Kernelizing K-Means

Problem: Standard k-means requires clusters to have round
shape. It fails on ‘banana’ datasets.

Idea: Replace � by the nonlinear feature map φ(�) and de-
fine µi =

�
j
βijφ(� j), i.e. centroids become weighted com-

binations of data points.

1. Cluster assignments step:

c(�) = argmin
i

�φ(�)− µi�
2

= argmax
i

2
�

βijk(� , � j)− β�i Kβi

2. Centroid update step:

βi = argmin
βi

�

� :c(�)=i

�φ(�)− µi�
2

= K
−1 ·

��
� :c(�)=i

k(X , �)
�

� :c(�)=i
1

�

Standard k-means

Kernel k-means

22/24

Other Cluster Algorithms

� Deep k-means

� Hierarchical clustering
� Divisive clustering
� Agglomerative clustering

� DBScan
� Affinity Propagation

23/24

Beyond Clustering

Mixture model
(today’s lecture)

Product of experts
(next week’s lecture)

24/24

Summary

� Latent variable models is a powerful approach to model complex data
distribution.

� Expectation-maximization is a framework to efficiently optimize these
models.

� Latent variable models can be used for clustering, e.g. the Gaussian
mixture model.

� The well-known k-means algorithm can be seen as a limit case of the
Gaussian mixture model.

� K-means can be kernelized to produce nonlinear boundaries between
clusters.

1/24

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

2/24

Beyond Clustering

Mixture model
(last week’s lecture)

Product of experts
(today’s lecture)

3/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:

p(x|α, θ) =
C�

k=1

αk · p(x|θk)

with αk denoting the mixing coefficients subject to the constraints
�C

k=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|θ) = 1Z
H�

j=1

g(x|θj)� ��
jth

expert

where Z is a normalization term set to ensure that p(x|θ) integrates to 1.

4/24

Example 1: Product of Gaussians

Consider the experts to be univariate Gaussians spe-
cialized on a particular input dimension

g(x|θi) =
1

(2πσ2i )
1/2

exp
�
− (xi − µi)

2σ2i

�

The product of experts (PoE) can be developed as:

p(x|θ) =
d�

i=1

g(x|θi)

=
1

(2π)d/2|Σ|1/2
exp

�
− 1

2
(x− µ)�Σ−1(x− µ)

�

with Σ = diag(σ21 , . . . ,σ
2
d), i.e. a multivariate Gaussian

distribution without correlation between features.

5/24

Example 2: Product of Gaussian Mixtures

Let the experts be the univariate mixtures:

g(x|θi) =
C�

k=1

π−1/2 exp(−(xi − µik)2)

The product of experts (PoE) can be developed as:

p(x|θ) = 1Z
d�

i=1

C�

k=1

π−1/2 exp(−(xi − µik)2)

=
1

Z
C�

k1=1

· · ·
C�

kd=1

d�

i=1

π−1/2 exp(−(xi − µiki)2)
� ��

multivariate Gaussian

i.e. a mixture of exponentially many (Cd) multivariate
Gaussians. Therefore, a PoE can encode many varia-
tions with few parameters.

6/24

Example 3: Product of t-Student Distributions

Define experts to be t-Student distributions in some
projected space (z = w�j x):

g(x|θj) =
1

αj + (w
�
j x)

2
�wj� = 1

The resulting product of experts

p(x|θ) = 1Z
H�

j=1

αj + (w
�
j x)

withH 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).

7/24

The Restricted Boltzmann Machine

input

latent

0 1 0 0 1

0 1 0 0 1 1

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 .

p(x,h|θ) = 1Z exp
� d�

i=1

H�

j=1

xiwijhj +

H�

j=1

bjhj

�

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.

8/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(w

�
j x+ bj)).

Proof:
p(x|θ) =

�

h∈{0,1}d
p(x,h|θ)

=
�

h∈{0,1}d

Z
exp

� d�

i=1

H�

j=1

xiwijhj +

H�

j=1

bjhj

�

=
1

Z
�

h∈{0,1}d

H�

j=1

exp((w�j x+ bj) · hj)

=
1

H�

j=1

�

hj∈{0,1}
exp((w�j x+ bj) · hj)

=
1

H�

j=1

(1 + exp(w�j x+ bj))

9/24

Interpreting the RBM Experts

The experts

g(x, θj) = 1 + exp(w
�
j x+ bj)

forming the RBM implement two behaviors:

� w�j x+ bj > 0 : g(x; θj) � 1: the example x is in
the area of competence of the expert and the
latter speaks in favor of x.

� w�j x+ bj < 0 : g(x; θj) ≈ 1: the example x is 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. 10/24 RBM as a Neural Network The product of expert (PoE) model p(x|θ) = 1Z H� j=1 (1 + exp(w�j x+ bj)) can be rewritten as: log p(x|θ) = H� j=1 log(1 + exp(� �� softplus w�j x+ bj)) � �� f(x,θ) − logZ where f(x, θ) can be interpreted as a neural network. ∑ x f softplus w (x) Note: The neural network can predict which examples x are more probable relative to other examples, but not the actual probability score, because logZ is difficult to compute. 11/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. 12/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). 13/24 RBM as a Neural Network RBM weights ((wj) H j=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. 14/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 log p(D|θ) = N� n=1 log C� k=1 αkp(xn|θk) βk βk ≥ N� n=1 C� k=1 log �αkp(xn|θk) βk � β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? log p(D|θ) = N� n=1 � f(xn, θ)− logZ � Answer: No, the expression cannot be bounded in the same way as for the mixture model (it has a different structure). 15/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. ∂ ∂θ log p(D|θ) = ∂ ∂θ N� n=1 � f(xn, θ)− logZ � = ∂ ∂θ N� n=1 � f(xn, θ)− log � x∈{0,1}d exp(f(x, θ)) � = N� n=1 � ∂ ∂θ f(xn, θ)− � x∈{0,1}d exp(f(x, θ)) ∂ ∂θ f(x, θ) � x∈{0,1}d exp(f(x, θ)) � = N� n=1 ∂ ∂θ f(xn, θ)−NEx∼p(x|θ) � ∂ ∂θ f(x, θ) � The gradient is a difference between a data-dependent and a model-dependent term. 16/24 RBM Update Rule Based on the gradient calculation above, we can build the update rule: θ ← θ + γ · � 1 N N� n=1 ∂ ∂θ f(xn, θ)− Ex∼p(x|θ) � ∂ ∂θ f(x, θ) �� Interpretation: � 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. data p(x) data 17/24 Computation of the RBM update rule θ ← θ + γ · � 1 N N� n=1 ∂ ∂θ f(xn, θ)− Ex∼p(x|θ) � ∂ ∂θ f(x, θ) �� 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. 18/24 Recap: ‘Classical’ View of the RBM input latent 0 1 0 0 1 0 1 0 0 1 1 The RBM is a probability model defined over input features x ∈ {0, 1}d and and latent variables h ∈ {0, 1}H . p(x,h|θ) = 1Z exp � d� i=1 H� j=1 xiwijhj + H� j=1 bjhj � 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. 19/24 Conditional Distributions in an RBM Sampling p(x) and p(h) is hard, however, hidden variables h can be sampled easily and independently when we condition on the state x, and similarly for x conditioned on h. Let zj = � i xiwij + bj . We proceed as: p(h|x, θ) = 1 Z exp �� j zjhj � � h 1 Z exp �� j zjhj � = � j exp(zjhj) � j � hj exp(zjhj) = � j exp(zjhj) 1 + exp(zj)� �� 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 the latent variables, i.e. p(xi|h, θ) = exp(zihi)/(1 + exp(zi)) with zi = � j wijhj . 20/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), θ) �H j=1 x(1) ∼ � p(xi |h(0), θ) �d i=1 h(1) ∼ � p(hj |x(1), θ) �H j=1 x(2) ∼ � p(xi |h(1), θ) �d i=1 ... until x(·) converges in distribution to p(x|θ). 21/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. 22/24 Application: RBM for Data 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(Wxnoisy + b) 2. Backprojection on the input domain xrec = sigm(W �h) Before denoising After denoising 23/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: φ(x) =   sigm(w�1 x) ... sigm(w�Hx)   � 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. MNIST example: Source: Erhan et al. (2010) Why Does Unsuper- vised Pre-training Help Deep Learning? 24/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. 1/24 Outline � What is Explainable AI? � Desiderata of an Explainable AI technique � Uses of Explainable AI � Methods for Explainable AI � Activation Maximization � Shapley Values � Taylor Expansions � Layer-wise Relevance Propagation 2/24 What is Explainable AI? Standard machine learning: � The function f is typically considered to be a “black-box” whose parameters are learned from the data using e.g. gradient descent. The objective to minimize encourages the predictions f (x) to coincide with the ground truth on the training and test data. x1 f(x)x2 xd x ... Machine learning + Explainable AI: � We do not only look at the outcome f (x) of the prediction but also at the way the prediction is produced by the ML model, e.g. which features are used, how these features are combined, or to what input pattern the model responds the most. 3/24 What is Explainable AI? Example 1: Synthesize an input pattern that most strongly activates the output of the ML model associated to a particular class. Image source: Nguyen et al. (2016) Multifaceted Feature Visualization: Uncovering the Different Types of Features Learned By Each Neuron in Deep Neural Networks 4/24 What is Explainable AI? Example 2: Highlight features that have contributed for a given data point to the ML prediction. image image image image heatmap (bike) heatmap (person) heatmap (cat) heatmap (person) image image image heatmap (train) heatmap (train) heatmap (dining table) Image source: Lapuschkin et al. (2016) Analyzing Classifiers: Fisher Vectors and Deep Neural Networks 5/24 What is Explainable AI? Example 3: Concept activation vectors (TCAV). Highlight the mid-level concepts that explain, for a given data point, the ML prediction. Source: Google Keynote’19 (URL: https://www.youtube.com/watch?v=lyRPyRKHO8M&t=2279s) 6/24 Desiderata of an Explanation In practice, we would like the explanation technique to satisfy a number of properties: 1. Fidelity: The explanation should reflect the quantity being explained and not something else. 2. Understandability: The explanation must be easily understandable by its receiver. 3. Sufficiency: The explanation should provide sufficient information on how the model came up with its prediction. 4. Low Overhead: The explanation should not cause the prediction model to become less accurate or less efficient. 5. Runtime Efficiency: Explanations should be computable in reasonable time. see also Swartout & Moore (1993), Explanation in Second Generation Expert Systems. image heatmap (train) 7/24 Uses of an Explanation Verify (and improve?) a ML model � Verify that the model is based on features which generalize well to examples outside the current data distribution (this cannot be done with standard validation techniques!). � Reliance of the ML models on wrong features is often encountered when there are spurious correlation in the data. � From the explanation, the model’s trustworthiness can be reevaluated, and the flawed ML model can be potentially retrained based on the user feedback. 8/24 Uses of an Explanation Example: The classifier is right for the wrong reasons image heatmap (horse) aer bic bir boa bot 79.08 66.44 45.90 70.88 27.64 bus car cat cha cow 69.67 80.96 59.92 51.92 47.60 din dog hor mot per 58.06 42.28 80.45 69.34 85.10 pot she sof tra tvm 28.62 49.58 49.31 82.71 54.33 average precision of the Fisher Vector model on the PascalVOC dataset � In this example, the classifier accurately predicts the horse class, but based on the wrong features (some copyright tag in the corner). � This incorrect decision strategy cannot be detected by just looking at the test error. cf. Lapuschkin et al. (2019) Unmasking Clever Hans Predictors and Assessing What Machines Really Learn. Nature Communications 9/24 Uses of an Explanation Learn something about the data (or about the system that produced the data) � Step 1: Train a ML model that predicts well the data. � Step 2: Apply XAI to the trained ML model to produce explanations of the ML decision strategy. � Step 3: Based on the XAI explanations, the user can compare his reasoning with that of the ML model, and can potentially refine his own domain knowledge. Image source: Thomas et al. (2019) Analyzing Neuroimaging Data Through Recurrent Deep Learning Models 10/24 Part II: Methods of XAI Presented methods � Activation maximization � Shapley values � Taylor expansion � Layer-wise relevance propagation Other methods � Surrogate models (LIME) � Integrated gradients / expected gradients / SmoothGrad � Influence functions � . . . 11/24 Activation Maximization Assume a trained a ML model (e.g. a neural network), and we would like to understand what concept is associated to some particular output neuron of the ML model, e.g. the output neuron that codes for the class ‘cat’. Activation maximization proceeds in two steps: � Step 1: Think of the ML model as a function of the input � Step 2: Explain the function f by generating a maximally activating input pattern: x� = arg max x f (x, θ) 12/24 Activation Maximization Problem: In most cases f (x) does not have single point corresponding to the maximum. E.g. in linear models, f (x) = w�x + b, we can keep moving the point x further along the direction w , and the output continues to grow). Therefore, we would like to apply a preference for ‘regular’ regions of the input domain, i.e. x� = arg max x f (x) + Ω(x) In practice, the preference can be for data points with small norm (i.e. we set Ω(x) = −λ�x�2 so that points with large norm are penalized.) 13/24 Activation Maximization: Examples f (x) = w�x + b and Ω(x) = −λ�x�2 f (x) = max(x1, x2) and Ω(x) = −λ�x�2 14/24 Activation Maximization: Probability View Assume the model produces a log-probability for class ωc : f (x) = log p(ωc |x) The input x� that maximizes this function can be inter- preted as the point where the classifier is the most sure about class ωc . Choose the regularizer Ω(x) = log p(x), i.e. favor points that are likely. The optimization problem becomes: x� = arg max x log p(ωc |x) + log p(x) = arg max x log p(x|ωc) where x� can now be interpreted as the most typical input for class ωc . 15/24 Attribution of a Prediction to Input Features ML blackbox predic�on input a�ribu�on 1. The data x ∈ Rd is fed to the ML black-box and we get a prediction f (x) ∈ R. 2. We explain the prediction by determining the contribution of each input feature. Key property of an explanation: conservation ( �d i=1 φi = f (x)). 16/24 Attribution: Shapley Values � Framework originally proposed in the context of game theory (Shapley 1951) for assigning payoffs in a cooperative game, and recently applied to ML models. � Each input variable is viewed as a player, and the function output as the profit realized by the cooperating players. The Shapley values φ1, . . . , φd measuring the contribution of each feature are: φi = � S : i /∈S |S|!(d−|S|−1)! d! � f (xS∪{i}) − f (xS) � where (xS)S are all possible subsets of features contained in the input x. 17/24 Attribution: Shapley Values Recall: φi = � S : i /∈S |S|!(d−|S|−1)! d!� �� αS � f (xS∪{i}) − f (xS) � � �� ΔS Worked-through example: Consider the function f (x) = x1 · (x2 + x3). Calculate the contri- bution of each feature to the prediction f (1) = 1 · (1 + 1) = 2. 18/24 Attribution: Taylor Expansions � Many ML models f (x) are complex and nonlinear when taken globally but are simple and linear when taken locally. � The function can be approximated locally by some Taylor expansion: f (x) = f (�x) + d� i=1 [∇f (�x)]i · (xi − �xi)� �� φi + . . . � First-order terms φi of the expansion can serve as an explanation. � The explanation (φi)i depends on the choice of root point �x. 19/24 Attribution: Taylor Expansions Example: Attribute the prediction f (x) = w�x with x ∈ Rd on the d input features. 20/24 Attribution: Taylor Expansions Limitations: Gradient information is too local- ized. � Cannot handle saturation effects and discontinuities e.g. cannot explain the function f (x) = d� i=1 xi − max(0, xi − θ) at the point x = (2, 2). This limitation can be overcome by looking at the structure of the model and decompose the problem of explanation in multiple parts (→ next slide). 21/24 Attribution: Look at the Structure of the Model ∑a4 a3 a5 a6 x1 x2 yout -1 1 1 1 -1 -1 1 -1 1 1 wij vj Observation: � The function implemented by a ML model is typically a composition of simple elementary functions. � These functions are simpler to analyze than the whole input-output function. Idea: � Treat the problem of explanation as propagating the prediction backward in the input-output graph. � The layer-wise relevance propagation (LRP) method implements this approach and can be used to explain ML models (→ next slide). 22/24 Attribution: The LRP Method ∑a4 a3 a5 a6 x1 x2 yout -1 1 1 1 -1 -1 1 -1 1 1 wij vj Example: Consider yout to be the quantity to explain: Rout ← yout � Step 1: Propagate on the hidden layer ∀6j=3 : Rj ← ajvj�6 j=3 ajvj Rout � Step 2: Propagate on the first layer ∀2i=1 : Ri ← 6� j=3 xiwij�2 i=1 xiwij Rj Note: Other propagation rules can be engineered, and choosing appropriate propagation rules is important to ensure LRP works well for practical neural network architectures. 23/24 Attribution: The LRP Method Effect of LRP rules on the explanation (e.g. class ‘castle’ predicted by a VGG-16 neural network.) VGG-16 Network 3x 3 @ 6 4 3x 3 @ 6 4 3x 3 @ 1 28 3x 3 @ 1 28 3x 3 @ 2 56 3x 3 @ 2 56 3x 3 @ 2 56 3x 3 @ 5 12 3x 3 @ 5 12 3x 3 @ 5 12 7x 1 @ 4 09 6 1x 1 @ 4 09 6 1x 1 @ 1 00 0 3x 3 @ 5 12 3x 3 @ 5 12 3x 3 @ 5 12 LRP-0 LRP-ϵ LRP-° LRP-0LRP-ϵLRP-° 24/24 Summary � Explainable AI is an important addition to classical ML models (e.g. for validating a ML model or extracting knowledge from it). � Many XAI methods have been developed, each of them, with their strengths and limitations: � Activation maximization can be used to understand what a ML model has learned, but is unsuitable for explaining an individual prediction f (x). � Shapley value has strong theoretical foundations, but is computationally unfeasible for high-dimensional input data. � Taylor expansions are simple and theoretically founded for simple models, but the expansion does not extrapolate well in complex nonlinear models. � LRP leverages the structure of the ML model to handle nonlinear decision functions, but requires to carefully choose the propagation rules. 1/29 Machine Learning 1, Course Outline � Covered topics � Bayes Decision Theory, Parameter Estimation � Component/Discriminant Analyses (PCA, Fisher) � Model Selection, Learning Theory � SVMs, Regression, Neural Nets, Boosting, Decision Trees � Clustering, Latent Variable Models � Weekly homeworks � Elective course (only for Machine Learning 1-X) 2/29 Machine Learning 1, Important Dates Registering homework groups � Request need to be sent before Friday 6 November 2020 at 14:00. First homework submission deadline � Monday 9 November 2020 at 14:00. Exam registration � Opens in January 2021. To be able to register, you need to first pass the prerequisites (homeworks / elective) and then request an Übungsschein/Genehmigung. Exams � March 2021, two sessions (you can choose the session you prefer), exact exam dates still to be determined. 3/29 Textbook Reference Duda et al. Pattern Classification, 2nd Edi- tion (2000) � The first four lectures will be based on this textbook. � This week: Sections 2.1-2.6;2.9 4/29 Example of a Machine Learning Classifier Information about the input (fish on the conveyor belt) is first acquired through sensors (e.g. wage, camera, etc.) The data is preprocessed (e.g. cropping, rescaling, normaliza- tion). Then a finite number of features is extracted. Finally, a classifier can be learned on these features. Image source: Duda et al. (2000) 5/29 Single-Feature Example (Length) 6/29 Two-Feature Example (Length + Lightness) 7/29 Bayesian Decision Theory Goals: � Merging empirical observations with prior knowledge about the task (e.g. prior class probabilities). � Incorporating distributional assumptions (e.g. Gaussian-generated data, independence of features). � Build optimal classifiers (in terms of classification accuracy or in terms of costs). 8/29 Bayesian Decision Theory Notation: � ω1,ω2, . . . Different classes (e.g. salmon, sea bass, ...) � x ∈ Rd vector of observations (e.g. x1 is the length and x2 is the lightness). we now add probabilities ... � P(ωj ): Probability of being of class j . � p(x): Data density function (e.g. histogram) � p(x |ωj ): Class-conditioned data density function (e.g. histogram). � P(ωj | x): Probability of being of a certain class after observing x. 9/29 Bayes Theorem P(ωj | x) = p(x |ωj ) · P(ωj ) p(x) Image source: Duda et al. (2000) 10/29 Optimally Accurate Classifier Decide � ω1 if P(ω1 | x) > P(ω2 | x)
ω2 else.

Alternate formulations:

11/29

Multivariate Normal Distributions

P(x|ωj ) =
1�

(2π)ddet(Σj )
exp

�
− 1
2
(x− µj )�Σ−1j (x− µj )

�

� µj is the mean (center of the
data distribution)

� Σj is the covariance
(elongation of the data

distribution).

Image source: Duda et al. (2000)

12/29

Optimal Classifier for Gaussians (Σ1 = Σ2)

Note: logP(x|ωj ) = − d2 log 2π −
1
2
log det(Σ)− 1

2
(x− µj )�Σ−1(x− µj )

13/29

Optimal Classifier for Gaussians (Σ1 = Σ2)

Image source:

Duda et al. (2000)

� Decision boundary is linear and oriented by mean and covariance.

� Offset is controlled by class prior probabilities.

14/29

Optimal Classifier for Gaussians (Σ1 �= Σ2)

� When covariances Σ1 and Σ2
are not the same, the decision

boundary is quadric instead of

linear. Quadrics include circle,

ellipse, parabola, hyperbola,

and degenerate forms.

Image source: Duda et al. (2000)

15/29

Binary Data Distributions

Assume that our data is now binary: x ∈ {0, 1}d . With each dimension
generated independently according to some parameters p and q.

P(xi = 0 |ω1) = 1− pi P(xi = 0 |ω2) = 1− qi
P(xi = 1 |ω1) = pi P(xi = 1 |ω2) = qi

The probability of the whole multivariate observation can be written as:

P(x|ω1) =
d�

i=1

�
pixi + (1− pi ) · (1− xi )

�

Question: How to express the decision boundary

P(ω1|x) > P(ω2|x)

16/29

Optimal Classifier for Binary Data (1st try)

Recall: P(x|ω1) =
�d
i=1

�
pixi + (1− pi ) · (1− xi )

�

17/29

Optimal Classifier for Binary Data

Observation:

For binary data, the data likelihood

P(x|ω1) =
d�

i=1

�
pixi + (1− pi ) · (1− xi )

�

can be equivalently expressed as

P(x|ω1) =
d�

i=1

�
p
xi
i · (1− pi )

(1−xi )
�

18/29

Optimal Classifier for Binary Data (2nd try)

Recall: P(x|ω1) =
�d
i=1

�
p
xi
i · (1− pi )(1−xi )

�

19/29

From Binary to Multi-Class

The two-class problem: ω = (ω1,ω2)

decide

�
ω1 if P(ω1 | x) > P(ω2 | x)
ω2 else,

can be generalized to multiple classes.

Let ω = (ω1,ω2, . . . ,ωC ) be our C possible classes. The optimal decision
now takes the form:

decide ωi if ∀j �=i : P(ωi |x) > P(ωj |x)

… or equivalently …

decide ωi where i = argmax
j
P(ωj |x)

20/29

Example: Multi-Class Gaussian

Decision function:

“decide ωi”

i = argmax
j
P(ωj |x)

Observation:

The decision surface of a multi-class

classifier can be quite complex and

nonlinear.

Image source: Duda et al. (2000)

21/29

From Classification to Cost Minimization

Example: Suppose you would like to purchase a second-hand car. After

observing the car, you assess that it has a defect with probability

P(defect | x) = 0.1 P(no defect | x) = 0.9

Concretely, the decision you need to take is not to classify the whether

the car has a defect or not, but whether to buy the car or not.

For this, we need to evaluate the cost of each scenario, e.g.

cost ( buy | defect ) = 100.0 cost ( buy | no defect ) = −20.0
cost ( not buy | defect ) = 0.0 cost ( not buy | no defect ) = 0.0

and take the action with the lowest expected cost.

22/29

From Classification to Cost Minimization

Classification Accuracy Maximization:

“classify as ωi” where i = argmax
j
P(ωj |x)

Expected Cost Minimization: Let (αi )i be the set of actions. The
expected cost of taking a certain action is given by

R(αj |x) =
C�

k=1

λ(αj |ωk)P(ωk |x)

where λ(αj ,ωk) is the cost of action αj given the class ωk . We then
decide to

“take action αi” where i = argmin
j
R(αj |x)

23/29

Classification Accuracy as a Special Case

Recall: R(αj |x) =
�C
k=1 λ(αj |ωk)P(ωk |x)

Show that the problem of maximum accuracy classification is a special

instance of expected cost minimization with a particular set of actions

(αj )j and a particular cost function λ(αj |ωk).

24/29

Analyzing the Two-Class Case

Recall: R(αj |x) =
�C
k=1 λ(αj |ωk)P(ωk |x)

Show that in the two-action two-class case, changing the cost function

means shifting the decision boundary.

(Note: when differences of lambdas are negative,
we need to stop before applying the log)

25/29

Measuring Classification Error

So far, we have studied what the decision boundary should be in order to

predict optimally.

However, in certain cases, it is also important to determine what is the

expected error of the classifier (e.g. to determine whether the classifier

is good enough for practical use).

The expected error is the probability that the data is of a different class

than the one predicted:

P(Err | x) =
�
P(ω1 | x) if “decide ω2”
P(ω2 | x) if “decide ω1”

For a maximally accurate classifier, this reduces to

P(Err | x) = min{P(ω1 | x),P(ω2 | x)}

26/29

Measuring Classification Error

The expected error of this maximally accurate classifier is computed as

the integral of its error probability over the distribution p(x).

P(Err) =

�

P(Err | x)p(x)dx

�

min{P(ω1 | x),P(ω2 | x)}p(x)dx

This is also known as the Bayes error rate.

Generally, this integral cannot be solved analytically, because of the min

function. Error must instead be bounded or evaluated empirically.

27/29

Bounding the Error of a Classifier

Very basic bound

Observe for binary classification that P(ω1 | x) = 1− P(ω2 | x).
The error can be bounded as:

P(Err) =

�

min{P(ω1 | x),P(ω2 | x)}p(x)dx

≤
�

0.5 p(x)dx = 0.5

The optimal classifier predicts the correct class at least 50% of the time.

28/29

Slightly Better Bound

Recall: P(ωj | x) =
p(x |ωj ) · P(ωj )

p(x)

The error can be bounded as:

P(Err) =

�

min{P(ω1 | x),P(ω2 | x)}p(x)dx

�

min{p(x |ω1)P(ω1), p(x |ω2)P(ω2)}dx

≤
�

max{p(x |ω1), p(x |ω2)}min{P(ω1),P(ω2)}dx

≤ 2min{P(ω1),P(ω2)}

Additional insight: The optimal classifier improves its accuracy when one

class prior probability is strongly dominant over to the other class.

29/29

Summary

� Bayesian decision theory allows to build optimal classifiers based on
prior knowledge about the classes and the data distributions.

� For certain simple data distributions, optimal classifiers are linear.

� The framework is general enough to extend to multi-class
scenarios and user-defined cost functions.

� Error of the optimal classifier is typically harder to compute than
the actual decision function, but it is still possible to compute

bounds on the error.

2020_TUB10

Wojciech Samek & Grégoire Montavon

ML1 Lecture 10: Kernel Ridge Regression 2

ML1 Lecture 10: Kernel Ridge Regression 3

ML1 Lecture 10: Kernel Ridge Regression 4

ML1 Lecture 10: Kernel Ridge Regression 5

ML1 Lecture 10: Kernel Ridge Regression 6

ML1 Lecture 10: Kernel Ridge Regression 7

ML1 Lecture 10: Kernel Ridge Regression 8

ML1 Lecture 10: Kernel Ridge Regression 9

ML1 Lecture 10: Kernel Ridge Regression 10

ML1 Lecture 10: Kernel Ridge Regression 11

ML1 Lecture 10: Kernel Ridge Regression 12

ML1 Lecture 10: Kernel Ridge Regression 13

ML1 Lecture 10: Kernel Ridge Regression 14

ML1 Lecture 10: Kernel Ridge Regression 15

ML1 Lecture 10: Kernel Ridge Regression 16

ML1 Lecture 10: Kernel Ridge Regression 17

ML1 Lecture 10: Kernel Ridge Regression 18

ML1 Lecture 10: Kernel Ridge Regression 19

ML1 Lecture 10: Kernel Ridge Regression 20

ML1 Lecture 10: Kernel Ridge Regression 21

ML1 Lecture 10: Kernel Ridge Regression 22

ML1 Lecture 10: Kernel Ridge Regression 23

ML1 Lecture 10: Kernel Ridge Regression 24

ML1 Lecture 10: Kernel Ridge Regression 25

ML1 Lecture 10: Kernel Ridge Regression 26

ML1 Lecture 10: Kernel Ridge Regression 27

ML1 Lecture 10: Kernel Ridge Regression 28

ML1 Lecture 10: Kernel Ridge Regression 29

ML1 Lecture 10: Kernel Ridge Regression 30

ML1 Lecture 10: Kernel Ridge Regression 31

ML1 Lecture 10: Kernel Ridge Regression 32

ML1 Lecture 10: Kernel Ridge Regression 33

ML1 Lecture 10: Kernel Ridge Regression 34

ML1 Lecture 10: Kernel Ridge Regression 35

ML1 Lecture 10: Kernel Ridge Regression 36

ML1 Lecture 10: Kernel Ridge Regression 37

ML1 Lecture 10: Kernel Ridge Regression 38

ML1 Lecture 10: Kernel Ridge Regression 39

ML1 Lecture 10: Kernel Ridge Regression 40

ML1 Lecture 10: Kernel Ridge Regression 41

ML1 Lecture 10: Kernel Ridge Regression 42

ML1 Lecture 10: Kernel Ridge Regression 43

ML1 Lecture 10: Kernel Ridge Regression 44

ML1 Lecture 10: Kernel Ridge Regression 45

Published by admin

Leave a Reply Cancel reply