{"id":22479,"date":"2020-12-03T10:17:32","date_gmt":"2020-12-03T10:17:32","guid":{"rendered":"https:\/\/www.experfy.com\/blog\/linear-regression-gradient-descent-for-beginners\/"},"modified":"2021-05-21T03:31:50","modified_gmt":"2021-05-21T03:31:50","slug":"linear-regression-gradient-descent-for-beginners","status":"publish","type":"post","link":"https:\/\/www.experfy.com\/blog\/ai-ml\/linear-regression-gradient-descent-for-beginners\/","title":{"rendered":"Linear Regression And Gradient Descent For Absolute Beginners"},"content":{"rendered":"\n

A simple explanation and implementation of gradient descent<\/em><\/p>\n\n\n\n

Let\u2019s say we have a fictional dataset of pairs of variables, a mother and her daughter\u2019s heights:<\/p>\n\n\n\n

\"height
height of mother\/daughter pairs<\/figcaption><\/figure><\/div>\n\n\n\n

Given a new mother height, 63, how do we predict* her daughter\u2019s height?<\/p>\n\n\n\n

The way you do it is by linear regression<\/a>.<\/p>\n\n\n\n

First, you find the line of best fit. Then you use that line for your prediction*.<\/p>\n\n\n\n

*Note: I used \u201cpredict\/prediction\u201d in this article. However, a reader pointed out in the comment below that the correct terminology is \u201cestimate\/estimation.\u201d<\/p>\n\n\n\n

\"Line
Line of best fit, or \u201cregression line\u201d<\/figcaption><\/figure><\/div>\n\n\n\n

Linear regression is about finding the line of best fit for a dataset. This line can then be used to make predictions.<\/p><\/blockquote>\n\n\n\n

How do you find the line of best fit?<\/strong><\/h2>\n\n\n\n

This is where gradient descent comes in.<\/p>\n\n\n\n

Gradient descent is a tool to arrive at the line of best fit<\/p><\/blockquote>\n\n\n\n

Before we dig into gradient descent, let\u2019s first look at another way of computing the line of best fit.<\/p>\n\n\n\n

Statistics way of computing line of best fit:<\/strong><\/p>\n\n\n\n

A line can be represented by the formula: y = mx + b<\/code>.<\/p>\n\n\n\n

The formula for slope m<\/code> of the regression line is:<\/p>\n\n\n\n

m = r * (SD of y \/ SD of x)<\/code><\/p>\n\n\n\n

Translation<\/em>: correlation coefficient between x and y values (r<\/code>), multiplied by the standard deviation of y values (SD of y<\/code>) divided by standard deviation of x values (SD of x<\/code>).<\/p>\n\n\n\n

The standard deviation of mothers\u2019 heights in the data above is approximately 4.07. The standard deviation of daughters\u2019 heights is approximately 5.5. The correlation coefficient between these two sets of variable is about 0.89.<\/p>\n\n\n\n

So the line of best fit, or regression line is:<\/p>\n\n\n\n

y = 0.89*(5.5 \/ 4.07)x + b
y = 1.2x + b<\/pre>\n\n\n\n
We know that the regression line crosses the point of averages, so one point on the line is (average of x values, average of y values)<\/code>, or (63.5, 63.33)<\/code><\/p>\n\n\n\n
63.33 = 1.2*63.5 + b
b = -12.87<\/pre>\n\n\n\n
Therefore, the regression line as calculated using correlation coefficient and standard deviations is approximately:<\/p>\n\n\n\n
y = 1.2x - 12.87<\/pre>\n\n\n\n
Regression line using statistics is y = 1.2x -12.87<\/p><\/blockquote>\n\n\n\n
Now, let\u2019s dig into gradient descent.<\/p>\n\n\n\n
Gradient descent way of computing line of best fit:<\/strong><\/h2>\n\n\n\n
In gradient descent, you start with a random line. Then you change the parameters of the line (i.e. slope and y-intercept) little by little to arrive at the line of best fit.<\/p>\n\n\n\n
How do you know when you arrived at the line of best fit?<\/p>\n\n\n\n
For every line you try \u2014 line A, line B, line C, etc \u2014 you calculate the sum of squares of the errors. If line B has a smaller value than line A, then line B is a better fit, etc.<\/p>\n\n\n\n
\"Linear
Error and square of error<\/figcaption><\/figure><\/div>\n\n\n\n
Error is your actual value minus your predicted value. The line of best fit minimizes the sum of the squares of all the errors. In linear regression, the line of best fit we computed above using correlation coefficient also happens to be the least squared error line. That\u2019s why the regression line is called the LEAST SQUARE REGRESSION LINE.<\/p>\n\n\n\n
Line of best fit is the least square regression line<\/p><\/blockquote>\n\n\n\n
In the image below, line C is better fit than line B, which is better fit than line A.<\/p>\n\n\n\n
\"Linear
Line C is better fit than B, which is better fit than A<\/figcaption><\/figure><\/div>\n\n\n\n
At a high level, this is how gradient descent works:<\/h4>\n\n\n\n
You start with a random line, let\u2019s say line A. You compute the sum of squared errors for that line. Then, you adjust your slope and y-intercept. You compute the sum of squared errors again for your new line. You continue adjusting until you reach a local minimum, where the sum of squared errors is the smallest and additional tweaks does not produce better result. The way you adjust your slope and intercept will be covered in more details momentarily.<\/p>\n\n\n\n
Gradient descent is an algorithm that approaches the least squared regression line via minimizing sum of squared errors through multiple iterations.<\/p><\/blockquote>\n\n\n\n
Gradient Descent Algorithm<\/h2>\n\n\n\n
In machine learning terminology, the sum of squared error is called the \u201ccost\u201d. This cost equation is:<\/p>\n\n\n\n
\"Linear
cost equation<\/figcaption><\/figure><\/div>\n\n\n\n
Where:<\/p>\n\n\n\n
\"Linear<\/figure><\/div>\n\n\n\n
This equation is therefore roughly \u201csum of squared errors\u201d as it computes the sum of predicted value minus actual value squared.<\/p>\n\n\n\n
The 1\/2m<\/code>is to \u201caverage\u201d the squared error over the number of data points so that the number of data points doesn\u2019t affect the function. See this<\/a> explanation for why we divide by 2.<\/p>\n\n\n\n
In gradient descent, the goal is to minimize the cost function. We do this by trying different values of slope and intercept. But which values to try and how do you go about changing those values?<\/p>\n\n\n\n
We change their values according to the gradient descent formula, which comes from taking the partial derivative of the cost function. The exact math can be found in this link<\/a>.<\/p>\n\n\n\n
By taking the partial derivative, you arrive at the formula:<\/p>\n\n\n\n
\"Gradient
Gradient descent formula by taking partial derivative of the cost function<\/figcaption><\/figure><\/div>\n\n\n\n
This formula computes by how much you change your theta with each iteration.<\/p>\n\n\n\n
The alpha (\u03b1) is called the learning rate. The learning rate determines how big the step would be on each iteration. It\u2019s critical to have a good learning rate because if it\u2019s too large your algorithm will not arrive at the minimum, and if it\u2019s too small, your algorithm will take forever to get there. For my example, I picked the alpha to be 0.001<\/p>\n\n\n\n
To summarize, the steps are:<\/h4>\n\n\n\n
  1. Estimate \u03b8<\/li>
  2. Compute cost<\/li>
  3. Tweak \u03b8<\/li>
  4. Repeat 2 and 3 until you reach convergence.<\/li><\/ol>\n\n\n\n
    Here\u2019s my implementation for simple linear regression using gradient descent.<\/p>\n\n\n\n
    I started at 0,0 for both the slope and intercept.<\/p>\n\n\n\n
    Note: In machine learning, we use theta to represent the vector [y-intercept, slope]. Theta0 = y-intercept. Theta1=slope. That\u2019s why you see theta as variable name in the implementation below.<\/p>\n\n\n

    <\/div>\n\n\n
    Using this algorithm and the dataset above for mothers and daughters heights, I got to a cost of 3.4 after 500 iterations.<\/p>\n\n\n\n
    The equation after 500 iterations is y = 0.998x + 0.078<\/code>. The actual regression line is y = 1.2x -12.87<\/code> with cost of approximately 3.1.<\/p>\n\n\n\n
    With an estimate of [0,0] as initial value for [y-intercept, slope], it\u2019s impractical to get to y = 1.2x -12.87<\/code> . To get close to that without tons and tons of iterations, you\u2019d have to start with a better estimate.<\/p>\n\n\n\n
    For example, [-10, 1] will get roughly y = 1.153x \u2014 10<\/code> and cost of 3.1 after less than 10 iterations.<\/p>\n\n\n\n
    Adjusting parameters like learning rate and starting estimate is commonplace in the world of machine learning.<\/p>\n\n\n\n
    There it is, the gist of gradient descent in linear regression.<\/p>\n\n\n\n
    Gradient descent is an algorithm that approaches the least squared regression line via minimizing sum of squared errors through multiple iterations.<\/p><\/blockquote>\n\n\n\n
    So far, I\u2019ve talked about simple linear regression, where you only have 1 independent variable (i.e. one set of x<\/strong> values). Theoretically, gradient descent can handle n number of variables.<\/p>\n\n\n\n
    I\u2019ve refactored my previous algorithm to handle n number of dimensions below.<\/p>\n\n\n

    <\/div>\n\n\n
    Everything is the same, the only exception is that instead of using mx + b<\/code> (i.e. slope times variable x plus y-intercept) directly to get your prediction, you do a matrix multiplication. See def get_prediction<\/code> in the gist above.<\/p>\n\n\n\n
    \"def
    https:\/\/algebra1course.wordpress.com\/2013\/02\/19\/3-matrix-operations-dot-products-and-inverses\/<\/a><\/figcaption><\/figure><\/div>\n\n\n\n
    With dot product, your algorithm can take in n number of variables to compute a prediction.<\/p>\n\n\n\n
    Thank you for reading! Comment below if you have questions!<\/p>\n","protected":false},"excerpt":{"rendered":"
    Linear regression is about finding the line of best fit for a dataset. This line can then be used to make predictions. Gradient descent is a tool to arrive at the line of best fit.<\/p>\n","protected":false},"author":990,"featured_media":18091,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"content-type":"","footnotes":""},"categories":[183],"tags":[656,1079,92],"ppma_author":[3687],"class_list":["post-22479","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-ai-ml","tag-gradient-descent","tag-linear-regression","tag-machine-learning"],"authors":[{"term_id":3687,"user_id":990,"is_guest":0,"slug":"lily","display_name":"Lily Chen","avatar_url":"https:\/\/www.experfy.com\/blog\/wp-content\/uploads\/2021\/05\/Lily-Chen-150x150.jpeg","user_url":"http:\/\/slack.com","last_name":"Chen","first_name":"Lily","job_title":"","description":"Lily Chen is Frontend Infrastructure Engineer at Slack, the leading channel-based messaging platform,"}],"_links":{"self":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/22479","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/users\/990"}],"replies":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/comments?post=22479"}],"version-history":[{"count":1,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/22479\/revisions"}],"predecessor-version":[{"id":23178,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/22479\/revisions\/23178"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media\/18091"}],"wp:attachment":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media?parent=22479"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/categories?post=22479"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/tags?post=22479"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=22479"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}