ML Chapter 1 Introduction

“Principles, methods and algorithms for learning and prediction on the basis of past evidence”

1. Speech recognition // Siri

2. Machine translation // Google Translate

3. Computer vision // Face detection

4. Text filtering // Email spam filters

5. Operation systems // Caching

6. Fraud detection // Credit cards

7. Game playing // Alpha Go

8. Robotics // Everywhere

9. Deep learning

“Machines that learn to perform a task from experience”

1. Crucial component for intelligent/autonomous system

2. Important for a system’s adaptability

3. Important for a system’s generalization capabilities

4. Attempt to understand human learning

1. No explicit knowledge encoded by ourselves

2. Learn relevant criteria automatically from past observations and adapt to given situations

3. Most often indicates optimization as search in hypothesis space for best model parameter w

1. Statistics

2. Probability theory

3. Decision theory

4. Information theory

5. Optimization theory

1. Described by function y=f(x,w) with parameters w

2. Regression with continuous y

3. Classification with discrete y

1. Typically one number in %

2. Generalization with training vs test or “All” data

1. Supervised learning // Target labels

2. Unsupervised learning

3. Semi-supervised learning

4. Reinforcement learning // Games indicate the winner at the end

1. Invariance to irrelevant input variations

2. Selecting the “right” features is crucial

3. Encoding and use of “domain knowledge”

4. Higher-dimensional features are more discriminative but complexity increases exponentially // Curse of dimensionality

“Probability theory is nothing but common sens reduced to calculation.” Pierre-Simon de Laplace

1. Random variables X for possibilities x_i // Boxes r,b and fruits a,o

2. N-many trials give n_ij = #{X=x_i \land Y=y_j} and c_i = #{X=x_i}

3. Probabilities

4. Rules

5. pdf

6. cdf

7. Expectation

8. Variance

9. Covariance

1. Joint p(X=x_i, Y=y_j) = n_ij/N

2. Marginal p(X=x_i) = c_i/N

3. Conditional p(X=x_i|Y=y_j) = n_ij/c_i

1. Sum p(X=x_i) = Sum_j=1^L p(X=x_i, Y=y_j) // With c_i = Sum_j=1^L n_ij

2. Product p(X=x_i, Y=y_j) = p(Y=y_j|X=x_i)*p(X=x_i) // With c_i/c_i

3. Bayes’Theorem p(Y|X) = p(X|Y)*p(Y)/p(X)

1. Function for probabilities over continuous variables

2. p(x in (a,b)) = int_a^b p(x)dx

1. Probability that x lies in (-inf,z)

2. P(z) = int_-inf^z p(x)dx

1. Average value of function f(x) under a pdf p(x)

2. E[f]=Sum_x p(x)f(x) // Discrete

3. E[f]=int p(x)f(x)dx // Continuous

4. E[f]~1/N Sum_n=1^Nf(x_n) // For finite number N of samples of pdf

5. E_x[f|y]=Sum_x p(x|y)f(x) // Conditional

1. How much variability is in f(x) around the mean value E[f(x)]

2. var[f] = E[ (f(x)-E[f(x)])² ] = E[f(x)²] – E[f(x)]²

1. cov[x,y] = E_x,y[{x-E[x]}{y-E[y]}] = E_x,y[xy] – E[x]E[y]

2. Result is a matrix if x,y are vectors

“The theory of inverse probability is founded upon an error and must be wholly rejected.” by Fisher

Classify new occurrence such that probability of misclassification is minimized

1. A priori

2. Conditional

3. Posterior

p(C_k) with Sum_kp(C_k)=1

1. With feature vector x // Certain property of input

2. Likelihood p(x|C_k) for class C_k

3. Decide for a class based on the feature

p(C_k|x) = p(x|C_k)p(C_k) / p(x) // Likelihood x Prior / Normalization

p(mistake) = p(x in R₁, C₂) + p(x in R₂, C₁)

= int_R1 p(x,C₂)dx + int_R2 p(x,C₁)dx

= int_R1 p(C₂|x)p(x)dx + int_R2 p(C₁|x)p(x)dx

1. Likelihood-Ratio test

2. Minimize the loss

1. p(C₁|x) > p(C₂|x)

2. p(x|C₁)p(C₁) > p(x|C₂)p(C₂)

3. p(x|C₁)/p(x|C₂) > p(C₂)/p(C₁) = theta // Likelihood-Ratio test

4. Compare with all other classes in case of more than two

1. But loss function depends on unknown true class

2. Work with expected loss

3. Adapted decision rule taking loss into account

1. E[L]=Sum_k,jint_Rj L_kjp(x,C_k)dx

2. E[L]=Sum_kL_kjp(C_k|x) by choosing regions R_j // Easy with posterior class probabilities

1. Differentiate between the possible decisions and the possible true classes

2. Cost may be assymmetric // loss(d=healty|patient=sick) >> loss(d=sick|patient=healthy)

3. Matrix L_kj = loss for decision C_j if truth is C_k // How much weight to wrong decisions

1. Classification errors arise from regions where largest posterior probability is significantly less than 1

2. Reject the automatic decision entirely and consult a human expert

1. Formulate classification in terms of comparisons

2. Classify x as class C_k if y_k(x) > y_j(x) fa j!=k

1. p(C_k|x)

2. p(x|C_k)p(C_k)

3. log p(x|C_k) + log p(C_k)

1. y_k(x) oc p(x|C_k)p(C_k)

2. First determine class-conditional densities

3. Separately infer the prior class probabilities

4. Then use Bayes’ theorem to determine class membership

1. y_k(x) = p(C_k|x)

2. First solve inference problem of determining the posterior class probabilities

3. The use decision theory to assign each new x to its class

Find y_k(x) mapping each input x directly onto a class label