1 CS 1674: Intro to Computer Vision Final ReviewProf. Adriana Kovashka University of Pittsburgh December 7, 2016

2 Final info Format: multiple-choice, true/false, fill in the blank, short answers, apply an algorithm Non-cumulative I expect you to know how to do a convolution Unlike last time, I’ll have one handout with the exam questions, and a separate one where you’re supposed to write the answers

3 Algorithms you should be able to applyK-means – apply a few iterations to a small example Mean-shift – to see where a single point ends up Hough transform – write pseudocode only Hough transform – how can we use it to find the parameters (matrix) of a transformation, when we have noisy examples? Compute a Spatial Pyramid at level 1 (2x2 grid) Formulate the SVM objective and constraints (in math) and explain it Work through an example for zero-shot prediction Boosting – show how to increase weights Pedestrian detection – write high-level pseudocode

4 Algorithms … able to apply (cont’d)Compute neural network activations Compute SVM and softmax loss Show how to use weights to compute loss Show how to numerically compute gradient Show one iteration of gradient descent (with gradient computed for you) Apply convolution, RELU, max pooling Compute output dimensions from convolution

5 Extra office hours Monday, 3:30-5:30pmAnyone for whom this does not work?

6 Requested topics Convolutional neural networks (16 requests)Hough transform (8) Support vector machines (7) Deformable part models (6) Zero-shot learning (4) Face detection (2) Recurrent neural networks (2) K-means / mean-shift (1) Spatial pyramids (1)

7 Convolutional neural networksBackpropagation + meaning of weights and how computed (5 requests) Math for neural networks + computing activations (4) Gradients + gradient descent (3) Convolution/non-linearity/pooling + convolution output size + architectures (3) Losses and finding weights that minimize them (2) Minibatch – are the training examples cycled over more than once? (1) Effect of number of neurons and regularization (1)

8 Neural networks

9 Deep neural network Figure from

10 Neural network definitionActivations: Nonlinear activation function h (e.g. sigmoid, tanh): Outputs: How can I write y1 as a function of x1 … xD? (binary) (multiclass) Figure from Christopher Bishop

11 Activation functions Sigmoid tanh tanh(x) ReLU max(0,x)Adapted from Andrej Karpathy

12 Activation computation vs trainingWhen do I need to compute activations? How many times do I need to do that? How many times do I need to train a network to extract features from it? Activations: Forward propagation (start from inputs, compute activations from inputs to outputs) Training: Backward propagation (compute a loss at the outputs, backpropagate error towards the inputs)

13 Backpropagation: Graphic exampleFirst calculate error of output units and use this to change the top layer of weights. output k j i Update weights into j hidden input Adapted from Ray Mooney

14 Backpropagation: Graphic exampleNext calculate error for hidden units based on errors on the output units it feeds into. output k j i hidden input Adapted from Ray Mooney

15 Backpropagation: Graphic exampleFinally update bottom layer of weights based on errors calculated for hidden units. output k j i Update weights into i hidden input Adapted from Ray Mooney

16 Loss gradients Denoted as (diff notations):i.e. how does the loss change as a function of the weights We want to find those weights (change the weights in such a way) that makes the loss decrease as fast as possible

17 Gradient descent We’ll update weightsMove in direction opposite to gradient: Learning rate Time L original W negative gradient direction W_1 W_2 Figure from Andrej Karpathy

18 Computing derivativesIn 1-dimension, the derivative of a function: w In multiple dimensions, the gradient is the vector of (partial derivatives). Andrej Karpathy

19 Computing derivativescurrent W: gradient dW: [0.34, -1.11, 0.78, 0.12, 0.55, 2.81, -3.1, -1.5, 0.33,…] loss [?, ?, ?,…] Andrej Karpathy

20 Computing derivativescurrent W: W + h (first dim): gradient dW: [0.34, -1.11, 0.78, 0.12, 0.55, 2.81, -3.1, -1.5, 0.33,…] loss [ , -1.11, 0.78, 0.12, 0.55, 2.81, -3.1, -1.5, 0.33,…] loss [?, ?, ?,…] Andrej Karpathy

21 Computing derivativescurrent W: W + h (first dim): gradient dW: [0.34, -1.11, 0.78, 0.12, 0.55, 2.81, -3.1, -1.5, 0.33,…] loss [ , -1.11, 0.78, 0.12, 0.55, 2.81, -3.1, -1.5, 0.33,…] loss [-2.5, ?, ( )/0.0001 = -2.5 ?, ?, ?,…] Andrej Karpathy

22 How to formulate losses?Losses depend on the prediction functions (scores), e.g. fW(x) = 3.2 for class “cat” One set of weights for each class! The prediction functions (scores) depend on the inputs (x) and the model parameters (W) Hence losses depend on W E.g. for a linear classifier, scores are: For a neural network:

23 Linear classifier (+b) 3072x1 10x1 10x1 10x307210 numbers, indicating class scores [32x32x3] array of numbers 0...1 parameters, or “weights” Andrej Karpathy

24 Neural network In the second layer of weights, one set of weights to compute the probability of each class

25 Linear classifier: SVM lossSuppose: 3 training examples, 3 classes. With some W the scores Multiclass SVM loss: Given an example are: where where is the image and is the (integer) label, and using the shorthand for the scores vector: cat car frog the SVM loss has the form: 3.2 5.1 -1.7 1.3 4.9 2.0 2.2 2.5 -3.1 Andrej Karpathy

26 Linear classifier: SVM lossSuppose: 3 training examples, 3 classes. With some W the scores Multiclass SVM loss: Given an example are: where where is the image and is the (integer) label, and using the shorthand for the scores vector: the SVM loss has the form: cat car frog 3.2 5.1 -1.7 Losses: 2.9 = max(0, ) +max(0, ) = max(0, 2.9) + max(0, -3.9) = = 2.9 Andrej Karpathy

27 Linear classifier: SVM lossSuppose: 3 training examples, 3 classes. With some W the scores Multiclass SVM loss: Given an example are: where where is the image and is the (integer) label, and using the shorthand for the scores vector: the SVM loss has the form: cat 3.2 car 5.1 frog -1.7 1.3 4.9 2.0 2.2 2.5 -3.1 Losses: 2.9 = max(0, ) +max(0, ) = max(0, -2.6) + max(0, -1.9) = 0 + 0 = 0 Andrej Karpathy

28 Linear classifier: SVM lossSuppose: 3 training examples, 3 classes. With some W the scores Multiclass SVM loss: Given an example are: where where is the image and is the (integer) label, and using the shorthand for the scores vector: the SVM loss has the form: cat car frog 3.2 5.1 -1.7 1.3 4.9 2.0 2.2 2.5 -3.1 Losses: 2.9 10.9 = max(0, (-3.1) + 1) +max(0, (-3.1) + 1) = max(0, 5.3) + max(0, 5.6) = = 10.9 Andrej Karpathy

29 Linear classifier: SVM lossSuppose: 3 training examples, 3 classes. With some W the scores Multiclass SVM loss: Given an example are: where where is the image and is the (integer) label, and using the shorthand for the scores vector: the SVM loss has the form: cat car frog 3.2 5.1 -1.7 1.3 4.9 2.0 2.2 2.5 -3.1 and the full training loss is the mean over all examples in the training data: L = ( )/3 2.9 10.9 Losses: = 4.6 Lecture Andrej Karpathy

30 Linear classifier: SVM lossAndrej Karpathy

31 Linear classifier: SVM lossλ = regularization strength (hyperparameter) Weight Regularization In common use: L2 regularization L1 regularization Dropout (will see later) In the case of a neural network: Regularization turns some neurons off (they don’t matter for computing an activation) Adapted from Andrej Karpathy

32 Effect of regularizationDo not use size of neural network as a regularizer. Use stronger regularization instead: (you can play with this demo over at ConvNetJS: edu/people/karpathy/convnetjs/demo/classify2d.html) Andrej Karpathy

33 Effect of number of neuronsmore neurons = more capacity Andrej Karpathy

34 Softmax loss 3.2 5.1 -1.7 24.5 0.13 164.0 0.87 0.18 0.00 cat car frogunnormalized probabilities cat car frog 3.2 5.1 -1.7 exp 24.5 164.0 0.18 0.13 0.87 0.00 L_i = -log(0.13) normalize unnormalized log probabilities probabilities Andrej Karpathy

35 Mini-batch gradient descentIn classic gradient descent, we compute the gradient from the loss for all training examples Could also only use some of the data for each gradient update, then cycle through all training samples Yes, we cycle through the training examples multiple times (each time we’ve cycled through all of them once is called an ‘epoch’) Allows faster training (e.g. on GPUs), parallelization

36 A note on training The more weights you need to learn, the more data you need That’s why with a deeper network, you need more data for training than for a shallower network That’s why if you have sparse data, you only train the last few layers of a deep net Set these to the already learned weights from another network Learn these on your own task

37 Convolutional neural networks

38 Convolutional Neural Networks (CNN)Feed-forward feature extraction: Convolve input with learned filters Apply non-linearity Spatial pooling (downsample) Input Image Convolution (Learned) Non-linearity Spatial pooling Output (class probs) … Adapted from Lana Lazebnik

39 1. Convolution Apply learned filter weights One feature map per filterStride can be greater than 1 (faster, less memory) ... Input Feature Map Adapted from Rob Fergus

40 2. Non-Linearity Per-element (independent) Options: TanhSigmoid: 1/(1+exp(-x)) Rectified linear unit (ReLU) Avoids saturation issues Adapted from Rob Fergus

41 3. Spatial Pooling Sum or max over non-overlapping / overlapping regions Role of pooling: Invariance to small transformations Larger receptive fields (neurons see more of input) Rob Fergus, figure from Andrej Karpathy

42 Convolutions: More detailConvolution Layer 32x32x3 image 5x5x3 filter 32 1 number: the result of taking a dot product between the filter and a small 5x5x3 chunk of the image (i.e. 5*5*3 = 75-dimensional dot product + bias) 32 3 Andrej Karpathy

43 Convolutions: More detailConvolution Layer activation map 32x32x3 image 5x5x3 filter 32 28 convolve (slide) over all spatial locations 32 28 3 1 Andrej Karpathy

44 Convolutions: More detailFor example, if we had 6 5x5 filters, we’ll get 6 separate activation maps: activation maps 32 28 Convolution Layer 32 28 3 6 We stack these up to get a “new image” of size 28x28x6! Andrej Karpathy

45 Convolutions: More detailPreview: ConvNet is a sequence of Convolutional Layers, interspersed with activation functions 32 28 24 …. CONV, ReLU e.g. 6 5x5x3 filters CONV, ReLU e.g x5x6 filters CONV, ReLU 32 28 24 3 6 10 Andrej Karpathy

46 Convolutions: More detail[From recent Yann LeCun slides] Preview Andrej Karpathy

47 Convolutions with some strideOutput size: (N - F) / stride + 1 F e.g. N = 7, F = 3: stride 1 => (7 - 3)/1 + 1 = 5 stride 2 => (7 - 3)/2 + 1 = 3 stride 3 => (7 - 3)/3 + 1 = 2.33 :\ N Andrej Karpathy

48 In practice: Common to zero pad the borderConvolutions with some padding In practice: Common to zero pad the border e.g. input 7x7 3x3 filter, applied with stride 1 pad with 1 pixel border => what is the output? 7x7 output! in general, common to see CONV layers with stride 1, filters of size FxF, and zero-padding with (F-1)/2. (will preserve size spatially) e.g. F = 3 => zero pad with 1 F = 5 => zero pad with 2 F = 7 => zero pad with 3 (N + 2*padding - F) / stride + 1 Andrej Karpathy

49 Combining all three stepsAndrej Karpathy

50 A common architecture: AlexNetFigure from

51 Hough transform (RANSAC won’t be on the exam)

52 Least squares line fittingData: (x1, y1), …, (xn, yn) Line equation: yi = m xi + b Find (m, b) to minimize y=mx+b (xi, yi) where line you found tells you point is along y axis where point really is along y axis You want to find a single line that “explains” all of the points in your data, but data may be noisy! Adapted from Svetlana Lazebnik

53 Outliers affect least squares fitKristen Grauman CS 376 Lecture 11 53

54 Outliers affect least squares fitKristen Grauman CS 376 Lecture 11 54

55 Dealing with outliers: VotingVoting is a general technique where we let the features vote for all models that are compatible with it. Cycle through features, cast votes for model parameters. Look for model parameters that receive a lot of votes. Noise & clutter features? They will cast votes too, but typically their votes should be inconsistent with the majority of “good” features. Adapted from Kristen Grauman CS 376 Lecture 8 Fitting

56 Finding lines in an image: Hough spacey b b0 x m0 m image space Hough (parameter) space Connection between image (x,y) and Hough (m,b) spaces A line in the image corresponds to a point in Hough space Steve Seitz CS 376 Lecture 8 Fitting

57 Finding lines in an image: Hough spacey b y0 Answer: the solutions of b = -x0m + y0 This is a line in Hough space x0 x m image space Hough (parameter) space Connection between image (x,y) and Hough (m,b) spaces A line in the image corresponds to a point in Hough space What does a point (x0, y0) in the image space map to? To go from image space to Hough space: given a pair of points (x,y), find all (m,b) such that y = mx + b Adapted from Steve Seitz CS 376 Lecture 8 Fitting

58 Finding lines in an image: Hough spacey b (x1, y1) y0 (x0, y0) b = –x1m + y1 x0 x m image space Hough (parameter) space What are the line parameters for the line that contains both (x0, y0) and (x1, y1)? It is the intersection of the lines b = –x0m + y0 and b = –x1m + y1 Steve Seitz CS 376 Lecture 8 Fitting

59 Finding lines in an image: Hough spacey b x m image space Hough (parameter) space How can we use this to find the most likely parameters (m,b) for the most prominent line in the image space? Let each edge point in image space vote for a set of possible parameters in Hough space Accumulate votes in discrete set of bins; parameters with the most votes indicate line in image space. Steve Seitz CS 376 Lecture 8 Fitting

60 Parameter space representationP.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959 Use a polar representation for the parameter space Each line is a sinusoid in Hough parameter space y x Hough space Silvio Savarese

61 Algorithm outline Initialize accumulator H to all zerosFor each feature point (x,y) in the image θ = gradient orientation at (x,y) ρ = x cos θ + y sin θ H(θ, ρ) = H(θ, ρ) + 1 end Find the value(s) of (θ*, ρ*) where H(θ, ρ) is a local maximum The detected line in the image is given by ρ* = x cos θ* + y sin θ* ρ θ Svetlana Lazebnik

62 Hough transform for circlesx = a + r cos(θ) y = b + r sin(θ) For every edge pixel (x,y): θ = gradient orientation at (x,y) For each possible radius value r: a = x – r cos(θ) b = y – r sin(θ) H[a,b,r] += 1 end θ x Modified from Kristen Grauman CS 376 Lecture 8 Fitting

63 Hough transform for finding transformation parametersB1 B2 B3 Given matched points in {A} and {B}, estimate the translation of the object Derek Hoiem

64 Hough transform for finding transformation parametersB4 B5 B6 A1 A2 A3 B1 B2 B3 (tx, ty) A4 A5 A6 Problem: outliers, multiple objects, and/or many-to-one matches Hough transform solution Initialize a grid of parameter values Each matched pair casts a vote for consistent values Find the parameters with the most votes Adapted from Derek Hoiem

65 Support vector machines

66 Linear classifiers Find linear function to separate positive and negative examples Which line is best? C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 1998

67 Support vector machinesDiscriminative classifier based on optimal separating line (for 2d case) Maximize the margin between the positive and negative training examples C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 1998

68 Support vector machinesWant line that maximizes the margin. wx+b=1 wx+b=0 wx+b=-1 For support, vectors, Distance between point and line: For support vectors: Support vectors Margin C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 1998

69 Finding the maximum margin lineMaximize margin 2/||w|| Correctly classify all training data points: Quadratic optimization problem: Minimize Subject to yi(w·xi+b) ≥ 1 Objective One constraint for each training point. Note sign trick. Constraints C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 1998

70 Finding the maximum margin lineSolution: Learned weight Support vector C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 1998

71 Finding the maximum margin lineSolution: b = yi – w·xi (for any support vector) Classification function: Notice that it relies on an inner product between the test point x and the support vectors xi If f(x) < 0, classify as negative, otherwise classify as positive. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 1998

72 The “Kernel Trick” The linear classifier relies on dot product between vectors K(xi , xj) = xi · xj If every data point is mapped into high-dimensional space via some transformation Φ: xi → φ(xi ), the dot product becomes: K(xi , xj) = φ(xi ) · φ(xj) The kernel trick: instead of explicitly computing the lifting transformation φ(x), define a kernel function K such that: K(xi , xj) = φ(xi ) · φ(xj) Andrew Moore CS 376 Lecture 22

73 Nonlinear SVMs Datasets that are linearly separable work out great:But what if the dataset is just too hard? We can map it to a higher-dimensional space: x x x2 x Andrew Moore

74 Nonlinear kernel: ExampleConsider the mapping x2 Svetlana Lazebnik

75 Examples of kernel functionsLinear: Polynomials of degree up to d: Gaussian RBF: Histogram intersection: 𝐾( 𝑥 𝑖 , 𝑥 𝑗 )= ( 𝑥 𝑖 𝑇 𝑥 𝑗 +1) 𝑑 Andrew Moore / Carlos Guestrin CS 376 Lecture 22

76 Allowing misclassifications: BeforeObjective The w that minimizes… Maximize margin Constraints

77 Allowing misclassifications: After# data samples Objective Misclassification cost Slack variable The w that minimizes… Maximize margin Minimize misclassification Constraints

78 Deformable part models?

79 Zero-shot learning

80 Image Classification: Textual descriptionsIntroduction Image Classification: Textual descriptions Which image shows an aye-aye? Description, Aye-aye . . . is nocturnal lives in trees has large eyes has long middle fingers We can classify based on textual descriptions Thomas Mensink

81 Zero-shot recognition (2)Introduction Zero-shot recognition (2) Vocabulary of attributes and class descriptions: Aye-ayes have properties X, and Y, but not Z Train classifiers for each attibute X, Y, Z. From visual examples of related classes Make image attributes predictions: 4.Combine into decision: this image is not an Aye-aye Thomas Mensink

82 Zero-shot recognition (2)Introduction Zero-shot recognition (2) P (X|img) = 0.8 ⇒ P (Y |img) = 0.3 P (Z|img) = 0.6 Vocabulary of attributes and class descriptions: Aye-ayes have properties X, and Y, but not Z Train classifiers for each attibute X, Y, Z. From visual examples of related classes Make image attributes predictions: 4.Combine into decision: this image is not an Aye-aye Thomas Mensink

83 DAP: Probabilistic modelAttribute-based classification DAP: Probabilistic model Define attribute probability: .p(am|x ) if az = 1 p(a = a |x ) = z m m m 1 − p(am|x ) otherwise Assign a given image to class z∗ Adapted from Thomas Mensink

84 Example Cat attributes: [1 0 0 1 0] Bear attributes: [0 1 0 0 0]Image X’s probability of the attributes: P(attributei = 1|X) = [ ] Probability that class(X) = “cat”: Probability that class(X) = “bear”: