Recitation 1: Intro, Projections

Shauli Ravfogel

Partially based on prof. Yoav Goldberg’s slides

​

Administration

• Shauli Ravfogel
• Mail: shauli321@gmail.com
• Course website: https://gal-chechik-biu.github.io/Neural_Networks_Grad/
• ~5 exercises + a project
• Midterm exam

Office hours: contact me via the mail

What is learning?

• Making predictions
• Based on past observations
• finding patterns in data
• learning from data
• generalization

Types of learning

• Supervised
• Regression
• Classification
• Structured
• Unsupervised
• Semi supervised
• Reinforcement

Machine learning

Machine learning - formulation

Machine learning - formulation

The perceptron model

Dot product

• w*x is a dot product:

Planes and hyperplanes

• A n-dimensional hyperplane is defined by a₁x₁ + a₂x₂ + … + a_nx_n = b
• The vector n = (a₁, …, a_n) is the normal (perpendicular vector) to the plane.
• Proof:
• Let (x₁,..,x_n), (x’₁, …, x’_n) be two points on the plane
• a₁x₁ + a₂x₂ + … + a_nx_n = b
• a₁x’₁ + a₂x’₂ + … + a_nx’_n = b
• => (a₁, …, a_n).dot(x₁-x’₁ , …, x_n-x’_n) = 0
• (x₁-x’₁ , …, x_n-x’_n) is a general vector on the plane

Projection on a vector

• It is often useful to calculate the component of a vector v in the direction of another vector u
• This is called a projection of v onto u
• Notation: Proj_u(v)

Distance from a plane (margin)

​

Distance from a plane (margin)

​

Learning as optimization

• We want to find a “good” f_θ(x)
• This requires a measure for the performance of f_θ

​

• In general, this optimization is hard
• Instead, change the parameters in the direction that minimizes the loss.
• We will focus in gradient-based optimization

(Whiteboard)

Derivative

• For a single variable: the slope of the tangent line

Gradient

• ​

​

• A vector pointing to the direction of the steepest ascent
• Thus minus the gradient points to the direction of steepest descent
• f changes the most in the direction of the gradient

Example: Linear Regression

Vector notation

Gradient descent

• We have a model with parameters θ = θ₁, … , θ_n
• We want to find the “best” θ with respect to some measure of the loss L(θ)
• e.g. L(θ=w; x, y) = (wx-y)²
• Gradient descent:
• Initialize θ randomly
• Change θ in the direction that minimizes L
• This direction is given by the opposite direction of the gradient

​

Algorithm outline

1. Initialize values θ = θ₁, … , θ_n
2. While not converged:
1. Calculate the gradient
2. For each θ_k in θ:

​

Newton method

• An iterative method for finding the roots (zeros) of a function

Newton method

​

Newton method for optimization

• We saw that Newton method enables us to find a root x* of a function F: F(x*) = 0
• Since extremum points of F correspond to roots of the gradient, we can apply Newton's method on the gradient to optimize the function F.

• Geometric interpretation: We find the maximum/minimum of the parabola that locally approximates F:

Formulation

​

We know the function value at point Xn, and want to approximate f(X) = f(Xn + Δx)

The Hessian

​