Ex 02. ML Part 2

• it

  • encodes

  • stores

  • retrieves

• the outcome of the learning process

• search in the hypothesis space

• in most practical applications not possible to find global minima

• => most learning algos search for local optima

• which aspects of the data are captured

  • e.g. simple statistics or probabiltiy distributions

• and how they are represented

  • e.g. implicit or human-readable

• incorporation of a priori knowledge about the learning task

• (at least to different degrees…)

• decision trees

• polynomials

• logic

• neural networks

• bayesian networks

• markov models

  
  

• simple way to extend hypothesis space

• => by combining a set of hypotheses h1, h2, …, hn element H

• to a new hypothesis h* element H^n

• build strong learner by combining several weak lerners

• boosting algorithms compute strong learner

• by incrementally constructing an ensemble of hypothesis

• assign weight to every trainign sample

  • -> initially set to same value

• weights of incorrectly learned samples are increased

• training of new hypothesis focuses on samples with high weights

• by how well it predicts

  • seen data from the dataset

  • and unseen data

• performance of h on training data

  • i.e. value of objection funciotn L for h and S

  • -> Fit

• preformance of h on unseen data

  • -> Generalization

• underfitting

  • bad fit

  • does not fint underlygin process, as not expressive enough

• overfitting

  • good fit

  • bad generalization

• “Of two competing theories, the simpler explanation of an entity is to be preferred”

• in general:

  • overfitting as result of model having more parameters than required to capture properties of process generated by S

  • desirable to choose model as simple as possible

    • => occams razor states the so called law of parsimony

• discriminative based on posterior probabilities

  • P(y|x) -> compute prediction x for an input y

• generative based on prior probabilities

  • P(x|y) -> model Distribution D that generate S directly

  • => compact representation of training data

    • having considerably less parameters than dataset S

  • can be computed using bayes theorem

• learn internal scene representations in a representation network

• => generate and predict visual appearance of the scene through a generation network

-> kind of learn world frame and query view from certian camera angle…

• applying model h to unseen data samples

• then compute objective funciton L

• training set

  • samples used in training phase by learning algo

  • to search for hypothesis h in hypothesis space H

• validation set

  • set of samples used to assess performance of hypothesis h that was computed in training phase

  • -> based on performance of h, parameters of training phase can be adjusted

• test set

  • set of samples used to assess performance of final model

• if h (hypothesis) is modified based on the performance of the test set

• in typical real-world applications

• -> data generated by physical process and thus limited

• k-fold cross validation enables efficient use of dat at cost of computational complexity

• partition dataset into k subsets and learned in k iterations

• in every iteration, different subset selected as validation set

• overall performance corresponds to average performances of the k iterations

• regularization

• more training data

  • incrase size (i.e. complexity) of dataset

• dataset augmentation

  • if not enough data available

  • -> increase by applying transformaitons to training samples

• overfitting due to model complex enough to capture statistical data that does not explain the data (i.e. noise)

• -> introduciton of regularization term in the objective funciton L

• => that guides learning process towards simpler solution by punishing complexity

• deterministic vs stochastic

• parametric vs nonparametric

• generative vs discriminative

• discrete (classification)

• continuous (regression)

• inductive

  • learn general model from specific examples

• deductive

  • use model to make predictions

• transductive

  • use specific examples to make predictions (at certain point of interests rather than general approximator…)

• synaptic weights

  • weights and bias

• activation funciton

• linear classifier based on single neuron

• with a threshold funciton

• wTx negative -> yn = -1

  • => > 0

• wTx positive -> yn = 1

  • => > 0

• only punishes incorrectly classified samples n element M

• use perceptron criterion and compute the gradient (basically loss….)

• apply stochastic gradient descent with learning rate

• update the weights

• if solution exists (i.e. dataset linearly separable)

  • -> perceptron learning algo finds solution

  • within finite number of steps

    • -> so called perceptron convergence theorem

• the solution calculated by the algorithm depends on

  • initialization of parameters

  • order of presentation of the training samples

• algorithm does not converge for not linearly separable datasets

• no!

• -> not linearly separable

• input:

  • dataset S

    • {(x0,y0),…,(xn,yn)}

    • with xi element X^K

    • with yi element Y^L

• Y^L continuous space (e.g. R^L)

• loss function L: Y^L x Y^L -> R

desired output:

• regressor h: X^K -> Y^L

• that predicts yn for a given yn with minimum loss L

• class of hypothesis spaces

• that are linear combinations of funcitons on the samples xn

• where phi_j are the basis fucitons of the model

• where phi_0(x) = 1

• values phi_j(xn) are called features of xn

• linear functions

• powers of x_i

• radial basis functions

• sigmoid functions

• L2 loss…

• L2 loss

• plus

• puishment for large weights

• interpolation:

  • must be consistent with S: f(xi) = yi

• regression:

  • hypotehsis h should minimize L and generalize well to new samples

• minimize L2 loss with:

• orthogonal projeciotn of vector y

• to vector h_w* (hypothesis with optimal weights)

• in the subspace spanned by teh column vectors of the matrix phi

• interpret prediction error of hypothesis as noise term epsilon

• model noise (usually) using gaussian distribution with mean hw(xn) and precision (inverse variance) beta

• compute the arg max w.r.t. w so that the likelihood of correct predictions is maximized

• often easier to maximize the log likelihood

-> as we mostly have minimizers (numerically more stable…) minimize negative log likelihood…

• for linear basis fuctions

• when assuming gaussian distributino of prediction error

• Input:

  • labeled dataset

  • C = {C1, …, CL} -> discrete space of classes C1,…,CL

  • we only consider assigning inputs exactly one class…!

    • => partitioning the input space X^K into decision regions

  • Classes represented as 1-of-K coding scheme (Cl = (0,0,…,1,…,0) element {0,1} ^K

• output:

  • classifier h: X^K -> C that predicts yn for given xn with minimum error

• space of classes C = {0,1}

• use linear regression model

• add nonlinear activation function f that discretizes the output space

->y_cls is called the generalized linear model

• subspaces

-> constant c

=> are linear functions of x…

• artificial neurons are generalized linear models!

• heaviside step function

=> uses decision surface with

• in genearl: combining discriminative functions (functions that separate datapoints based on decision surface…) that classify subsets of the classes

• one-versus-the-rest classifier (top)

• one-versus-one-classifier (bottom)

• separates K classes with K-1 discriminatn functions

• every discriminant function separates one class from all others

-> some regtions (?) are classified ambiguously

-> here: is it C1 or is it C2?

• pairwise separation of K classes with K(K-1)/2 binary discriminant funcitons

• class of data sample assinged by majority vote

  • -> for all classificatoins betwen two classes, which class was assigned most often?

-> problem: some regions classified ambiguously (here due to draw in majority vote…!)

• discriminant functions overlap or do not cover the whole input space

• determine partition of the input space

• assign regular linear function (without discretization) to all classes (regular decision boundary)

• calculate the output for a sample

• => assign to class where the output is largest…

• implies not existing order that might be captured by the learned model

• => use one hot encoding

• for n dimensions, create n-dimensional vector

• i-th class is represented with (0,0,…,1,…,0) where only the i-th element is 1 and the rest 0

• enables mapping classification problem to regression problem

• -> make use of least squares

• individual classes represented by own liear model

• grouped together into classifier

• where W is matrix compromised of weight vectors wk of individual linear models y_Ck

• L2 loss (0.5(y_hat)^2)

• -> Trace Tr ensures that only quadratic terms on diagonal of product matrix account for the loss

• sensitive to outliers!

• => as hyperplane (decision boundary) depens on all samples of dataset…

• => algo computes one of infinitely many solutions!

• support vector machines

• minimize generalization error by maximizing the margin of the classifier

• => margin: smallest distance between the decisino boundary and the training samples

  • -> only closest samples to boundary are important => so called support vectors…

-> minimize ||w|| to maximize the distance…

• introduce slack variable

• -> allowing for some training samples lying inside the margin or on the other side…