I've started taking an online machine learning class, and the first learning algorithm that we are going to be using is a form of linear regression using gradient descent. I don't have much of a background in high level math, but here is what I understand so far.

Given $m$ number of items in our learning set, with $x$ and $y$ values, we must find the best fit line $h_\theta(x) = \theta_0+\theta_1x$ . The cost function for any guess of $\theta_0,\theta_1$ can be computed as:

$J(\theta_0,\theta_1) = \frac{1}{2m}\displaystyle\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})^2$

where $x^{(i)}$ and $y^{(i)}$ are the $x$ and $y$ values for the $i^{th}$ component in the learning set. If we substitute for $h_\theta(x)$,

$J(\theta_0,\theta_1) = \frac{1}{2m}\displaystyle\sum_{i=1}^m(\theta_0 + \theta_1x^{(i)} - y^{(i)})^2$

Then, the goal of gradient descent can be expressed as

$\displaystyle\min_{\theta_0, \theta_1}\;J(\theta_0, \theta_1)$

Finally, each step in the gradient descent can be described as:

$\theta_j := \theta_j - \alpha\frac{\partial}{\partial\theta_j} J(\theta_0,\theta_1)$

for $j = 0$ and $j = 1$ with $\alpha$ being a constant representing the rate of step.

I have no idea how to do the partial derivative. I have never taken calculus, but conceptually I understand what a derivative represents. The instructor gives us the partial derivatives for both $\theta_0$ and $\theta_1$ and says not to worry if we don't know how it was derived. (I suppose, technically, it is a computer class, not a mathematics class) However, I would very much like to understand this if possible. Could someone show how the partial derivative could be taken, or link to some resource that I could use to learn more? I apologize if I haven't used the correct terminology in my question; I'm very new to this subject.

  • What do you know? Do you know derivatives at all? – Phira Oct 7 '11 at 23:43
  • No, I do not, currently. – voithos Oct 8 '11 at 3:26
up vote 131 down vote accepted

The answer above is a good one, but I thought I'd add in some more "layman's" terms that helped me better understand concepts of partial derivatives. The answers I've seen here and in the Coursera forums leave out talking about the chain rule, which is important to know if you're going to get what this is doing...


It's helpful for me to think of partial derivatives this way: the variable you're focusing on is treated as a variable, the other terms just numbers. Other key concepts that are helpful:

  • For "regular derivatives" of a simple form like $F(x) = cx^n$ , the derivative is simply $F'(x) = cn \times x^{n-1}$
  • The derivative of a constant (a number) is 0.
  • Summations are just passed on in derivatives; they don't affect the derivative. Just copy them down in place as you derive.

Also, it should be mentioned that the chain rule is being used. The chain rule says that (in clunky laymans terms), for $g(f(x))$, you take the derivative of $g(f(x))$, treating $f(x)$ as the variable, and then multiply by the derivative of $f(x)$. For our cost function, think of it this way:

$$ g(\theta_0, \theta_1) = \frac{1}{2m} \sum_{i=1}^m \left(f(\theta_0, \theta_1)^{(i)}\right)^2 \tag{1}$$

$$ f(\theta_0, \theta_1)^{(i)} = \theta_0 + \theta_{1}x^{(i)} - y^{(i)} \tag{2}$$

To show I'm not pulling funny business, sub in the definition of $f(\theta_0, \theta_1)^{(i)}$ into the definition of $g(\theta_0, \theta_1)$ and you get:

$$ g(f(\theta_0, \theta_1)^{(i)}) = \frac{1}{2m} \sum_{i=1}^m \left(\theta_0 + \theta_{1}x^{(i)} - y^{(i)}\right)^2 \tag{3}$$

This is, indeed, our entire cost function.

Thus, the partial derivatives work like this:

$$ \frac{\partial}{\partial \theta_0} g(\theta_0, \theta_1) = \frac{\partial}{\partial \theta_0} \frac{1}{2m} \sum_{i=1}^m \left(f(\theta_0, \theta_1)^{(i)}\right)^2 = 2 \times \frac{1}{2m} \sum_{i=1}^m \left(f(\theta_0, \theta_1)^{(i)}\right)^{2-1} = \tag{4}$$

$$\frac{1}{m} \sum_{i=1}^m f(\theta_0, \theta_1)^{(i)}$$

In other words, just treat $f(\theta_0, \theta_1)^{(i)}$ like a variable and you have a simple derivative of $\frac{1}{2m} x^2 = \frac{1}{m}x$

$$ \frac{\partial}{\partial \theta_0} f(\theta_0, \theta_1)^{(i)} = \frac{\partial}{\partial \theta_0} (\theta_0 + \theta_{1}x^{(i)} - y^{(i)}) \tag{5}$$

And $\theta_1, x$, and $y$ are just "a number" since we're taking the derivative with respect to $\theta_0$, so the partial of $g(\theta_0, \theta_1)$ becomes:

$$ \frac{\partial}{\partial \theta_0} f(\theta_0, \theta_1) = \frac{\partial}{\partial \theta_0} (\theta_0 + [a \ number][a \ number]^{(i)} - [a \ number]^{(i)}) = \frac{\partial}{\partial \theta_0} \theta_0 = 1 \tag{6}$$

So, using the chain rule, we have:

$$ \frac{\partial}{\partial \theta_0} g(f(\theta_0, \theta_1)^{(i)}) = \frac{\partial}{\partial \theta_0} g(\theta_0, \theta_1) \frac{\partial}{\partial \theta_0}f(\theta_0, \theta_1)^{(i)} \tag{7}$$

And subbing in the partials of $g(\theta_0, \theta_1)$ and $f(\theta_0, \theta_1)^{(i)}$ from above, we have:

$$ \frac{1}{m} \sum_{i=1}^m f(\theta_0, \theta_1)^{(i)} \frac{\partial}{\partial \theta_0}f(\theta_0, \theta_1)^{(i)} = \frac{1}{m} \sum_{i=1}^m \left(\theta_0 + \theta_{1}x^{(i)} - y^{(i)}\right) \times 1 = \tag{8}$$

$$ \frac{1}{m} \sum_{i=1}^m \left(\theta_0 + \theta_{1}x^{(i)} - y^{(i)}\right)$$


What about the derivative with respect to $\theta_1$?

Our term $g(\theta_0, \theta_1)$ is identical, so we just need to take the derivative of $f(\theta_0, \theta_1)^{(i)}$, this time treating $\theta_1$ as the variable and the other terms as "just a number." That goes like this:

$$ \frac{\partial}{\partial \theta_1} f(\theta_0, \theta_1)^{(i)} = \frac{\partial}{\partial \theta_1} (\theta_0 + \theta_{1}x^{(i)} - y^{(i)}) \tag{9}$$

$$ \frac{\partial}{\partial \theta_1} f(\theta_0, \theta_1)^{(i)} = \frac{\partial}{\partial \theta_1} ([a \ number] + \theta_{1}[a \ number, x^{(i)}] - [a \ number]) \tag{10}$$

Note that the "just a number", $x^{(i)}$, is important in this case because the derivative of $c \times x$ (where $c$ is some number) is $\frac{d}{dx}(c \times x^1) = c \times 1 \times x^{(1-1=0)} = c \times 1 \times 1 = c$, so the number will carry through. In this case that number is $x^{(i)}$ so we need to keep it. Thus, our derivative is:

$$ \frac{\partial}{\partial \theta_1} f(\theta_0, \theta_1)^{(i)} = 0 + (\theta_{1})^1 x^{(i)} - 0 = 1 \times \theta_1^{(1-1=0)} x^{(i)} = 1 \times 1 \times x^{(i)} = x^{(i)} \tag{11}$$

Thus, the entire answer becomes:

$$ \frac{\partial}{\partial \theta_1} g(f(\theta_0, \theta_1)^{(i)}) = \frac{\partial}{\partial \theta_1} g(\theta_0, \theta_1) \frac{\partial}{\partial \theta_1} f(\theta_0, \theta_1)^{(i)} = \tag{12}$$

$$\frac{1}{m} \sum_{i=1}^m f(\theta_0, \theta_1)^{(i)} \frac{\partial}{\partial \theta_1}f(\theta_0, \theta_1)^{(i)} = \frac{1}{m} \sum_{i=1}^m \left(\theta_0 + \theta_{1}x^{(i)} - y^{(i)}\right) x^{(i)}$$


A quick addition per @Hugo's comment below. Let's ignore the fact that we're dealing with vectors at all, which drops the summation and $fu^{(i)}$ bits. We can also more easily use real numbers this way.

$\require{cancel}$

Let's say $x = 2$ and $y = 4$.

So, for part 1 you have:

$$\frac{\partial}{\partial \theta_0} (\theta_0 + \theta_{1}x - y)$$

Filling in the values for $x$ and $y$, we have:

$$\frac{\partial}{\partial \theta_0} (\theta_0 + 2\theta_{1} - 4)$$

We only care about $\theta_0$, so $\theta_1$ is treated like a constant (any number, so let's just say it's 6).

$$\frac{\partial}{\partial \theta_0} (\theta_0 + (2 \times 6) - 4) = \frac{\partial}{\partial \theta_0} (\theta_0 + \cancel8) = 1$$

Using the same values, let's look at the $\theta_1$ case (same starting point with $x$ and $y$ values input):

$$\frac{\partial}{\partial \theta_1} (\theta_0 + 2\theta_{1} - 4)$$

In this case we do care about $\theta_1$, but $\theta_0$ is treated as a constant; we'll do the same as above and use 6 for it's value:

$$\frac{\partial}{\partial \theta_1} (6 + 2\theta_{1} - 4) = \frac{\partial}{\partial \theta_1} (2\theta_{1} + \cancel2) = 2 = x$$

The answer is 2 because we ended up with $2\theta_1$ and we had that because $x = 2$.

Hopefully the clarifies a bit on why in the first instance (wrt $\theta_0$) I wrote "just a number," and in the second case (wrt $\theta_1$) I wrote "just a number, $x^{(i)}$. While it's true that $x^{(i)}$ is still "just a number", since it's attached to the variable of interest in the second case it's value will carry through which is why we end up at $x^{(i)}$ for the result.

  • 9
    Thank you for this! I must say, I appreciate it even more when I consider how long it has been since I asked this question. In reality, I have never had any formal training in any form of calculus (not even high-school level, sad to say), so, while I perhaps understood the concept, the math itself has always been a bit fuzzy. Interestingly enough, I started trying to learn basic differential (univariate) calculus around 2 weeks ago, and I think you may have given me a sneak peek. I'm glad to say that your answer was very helpful, thinking back on the course. Once more, thank you! – voithos Sep 2 '12 at 2:36
  • 1
    When you were explaining the derivation of $\frac{\partial}{\partial \theta_0}$, in the final form you retained the $\frac{1}{2m}$ while at the same time having $\frac{1}{m}$ as the outer term. I suspect this is a simple transcription error? – voithos Sep 2 '12 at 2:44
  • 1
    @voithos yup -- good catch. Just noticed that myself on the Coursera forums where I cross posted. Typing in LaTeX is tricky business! Thanks for letting me know. – Hendy Sep 2 '12 at 15:53
  • 1
    @voithos: also, I posted so long after because I just started the same class on it's next go-around. I have taken multivariable calculus and didn't get the derivation... so I re-taught myself. I knew the gist of taking a partial with respect to a variable, but the chain rule part was missing. After I figured it out, I added the same answer to the Coursera forum where someone had asked the same, and that linked here. The other answer is plenty fine, but it wouldn't quite have gotten things to click for me, so I thought I'd give it a whirl in my own words. – Hendy Sep 3 '12 at 1:01
  • 1
    Do you know guys, that Andrew Ng's Machine Learning course on Coursera links now to this answer to explain the derivation of the formulas for linear regression? :) – gdrt Dec 3 '15 at 1:16

Despite the popularity of the top answer, it has some major errors. The most fundamental problem is that $g(f^{(i)}(\theta_0, \theta_1))$ isn't even defined, much less equal to the original function. The focus on the chain rule as a crucial component is correct, but the actual derivation is not right at all.

So I'll give a correct derivation, followed by my own attempt to get across some intuition about what's going on with partial derivatives, and ending with a brief mention of a cleaner derivation using more sophisticated methods. That said, if you don't know some basic differential calculus already (at least through the chain rule), you realistically aren't going to be able to truly follow any derivation; go learn that first, from literally any calculus resource you can find, if you really want to know.

For completeness, the properties of the derivative that we need are that for any constant $c$ and functions $f(x)$ and $g(x)$, $$\frac{d}{dx} c = 0, \ \frac{d}{dx} x = 1,$$ $$\frac{d}{dx} [c\cdot f(x)] = c\cdot\frac{df}{dx} \ \ \ \text{(linearity)},$$ $$\frac{d}{dx}[f(x)+g(x)] = \frac{df}{dx} + \frac{dg}{dx} \ \ \ \text{(linearity)},$$ $$\frac{d}{dx}[f(x)]^2 = 2f(x)\cdot\frac{df}{dx} \ \ \ \text{(chain rule)}.$$

Taking partial derivatives works essentially the same way, except that the notation $\frac{\partial}{\partial x}f(x,y)$ means we we take the derivative by treating $x$ as a variable and $y$ as a constant using the same rules listed above (and vice versa for $\frac{\partial}{\partial y}f(x,y)$).


Derivation

We have

$$h_\theta(x_i) = \theta_0 + \theta_1 x_i$$

and

$$\begin{equation} J(\theta_0, \theta_1) = \frac{1}{2m} \sum_{i=1}^m (h_\theta(x_i)-y_i)^2\end{equation}.$$

We first compute

$$\frac{\partial}{\partial\theta_0}h_\theta(x_i)=\frac{\partial}{\partial\theta_0}(\theta_0 + \theta_1 x_i)=\frac{\partial}{\partial\theta_0}\theta_0 + \frac{\partial}{\partial\theta_0}\theta_1 x_i =1+0=1,$$

$$\frac{\partial}{\partial\theta_1}h_\theta(x_i) =\frac{\partial}{\partial\theta_1}(\theta_0 + \theta_1 x_i)=\frac{\partial}{\partial\theta_1}\theta_0 + \frac{\partial}{\partial\theta_1}\theta_1 x_i =0+x_i=x_i,$$

which we will use later. Now we want to compute the partial derivatives of $J(\theta_0, \theta_1)$. We can actually do both at once since, for $j = 0, 1,$

$$\frac{\partial}{\partial\theta_j} J(\theta_0, \theta_1) = \frac{\partial}{\partial\theta_j}\left[\frac{1}{2m} \sum_{i=1}^m (h_\theta(x_i)-y_i)^2\right]$$

$$= \frac{1}{2m} \sum_{i=1}^m \frac{\partial}{\partial\theta_j}(h_\theta(x_i)-y_i)^2 \ \text{(by linearity of the derivative)}$$

$$= \frac{1}{2m} \sum_{i=1}^m 2(h_\theta(x_i)-y_i)\frac{\partial}{\partial\theta_j}(h_\theta(x_i)-y_i) \ \text{(by the chain rule)}$$

$$= \frac{1}{2m}\cdot 2\sum_{i=1}^m (h_\theta(x_i)-y_i)\left[\frac{\partial}{\partial\theta_j}h_\theta(x_i)-\frac{\partial}{\partial\theta_j}y_i\right]$$

$$= \frac{1}{m}\sum_{i=1}^m (h_\theta(x_i)-y_i)\left[\frac{\partial}{\partial\theta_j}h_\theta(x_i)-0\right]$$

$$=\frac{1}{m} \sum_{i=1}^m (h_\theta(x_i)-y_i)\frac{\partial}{\partial\theta_j}h_\theta(x_i).$$

Finally substituting for $\frac{\partial}{\partial\theta_j}h_\theta(x_i)$ gives us

$$\frac{\partial}{\partial\theta_0} J(\theta_0, \theta_1) = \frac{1}{m} \sum_{i=1}^m (h_\theta(x_i)-y_i),$$ $$\frac{\partial}{\partial\theta_1} J(\theta_0, \theta_1) = \frac{1}{m} \sum_{i=1}^m (h_\theta(x_i)-y_i)x_i.$$


Intuition for partial derivatives

So what are partial derivatives anyway? In one variable, we can assign a single number to a function $f(x)$ to best describe the rate at which that function is changing at a given value of $x$; this is precisely the derivative $\frac{df}{dx}$of $f$ at that point. We would like to do something similar with functions of several variables, say $g(x,y)$, but we immediately run into a problem. In one variable, we can only change the independent variable in two directions, forward and backwards, and the change in $f$ is equal and opposite in these two cases. (For example, if $f$ is increasing at a rate of 2 per unit increase in $x$, then it's decreasing at a rate of 2 per unit decrease in $x$.)

With more variables we suddenly have infinitely many different directions in which we can move from a given point and we may have different rates of change depending on which direction we choose. So a single number will no longer capture how a multi-variable function is changing at a given point. However, there are certain specific directions that are easy (well, easier) and natural to work with: the ones that run parallel to the coordinate axes of our independent variables. These resulting rates of change are called partial derivatives. (For example, $g(x,y)$ has partial derivatives $\frac{\partial g}{\partial x}$ and $\frac{\partial g}{\partial y}$ from moving parallel to the x and y axes, respectively.) Even though there are infinitely many different directions one can go in, it turns out that these partial derivatives give us enough information to compute the rate of change for any other direction. (Strictly speaking, this is a slight white lie. There are functions where the all the partial derivatives exist at a point, but the function is not considered differentiable at that point. This happens when the graph is not sufficiently "smooth" there.)

In particular, the gradient $\nabla g = (\frac{\partial g}{\partial x}, \frac{\partial g}{\partial y})$ specifies the direction in which g increases most rapidly at a given point and $-\nabla g = (-\frac{\partial g}{\partial x}, -\frac{\partial g}{\partial y})$ gives the direction in which g decreases most rapidly; this latter direction is the one we want for gradient descent. This makes sense for this context, because we want to decrease the cost and ideally as quickly as possible.


A higher level approach

For the interested, there is a way to view $J$ as a simple composition, namely

$$J(\mathbf{\theta}) = \frac{1}{2m} \|\mathbf{h_\theta}(\mathbf{x})-\mathbf{y}\|^2 = \frac{1}{2m} \|X\mathbf{\theta}-\mathbf{y}\|^2.$$

Note that $\mathbf{\theta}$, $\mathbf{h_\theta}(\mathbf{x})$, $\mathbf{x}$, and $\mathbf{y}$, are now vectors. Using more advanced notions of the derivative (i.e. the total derivative or Jacobian), the multivariable chain rule, and a tiny bit of linear algebra, one can actually differentiate this directly to get

$$\frac{\partial J}{\partial\mathbf{\theta}} = \frac{1}{m}(X\mathbf{\theta}-\mathbf{y})^\top X.$$

The transpose of this is the gradient $\nabla_\theta J = \frac{1}{m}X^\top (X\mathbf{\theta}-\mathbf{y})$. Setting this gradient equal to $\mathbf{0}$ and solving for $\mathbf{\theta}$ is in fact exactly how one derives the explicit formula for linear regression.

  • 1
    I can't figure out how to see revisions/suggested edits. Could you clarify on the major errors? It looks like we end up at the same answer, and from what I can tell we just defined $h(x)$ and $J(\theta)$ differently, but the substitutions and chain rule still work out. It's been a long time since I wrote the answer, so it's a bit tricky to re-enter the mindset... I'm happy to fix any issues you've found! – Hendy Aug 30 '16 at 19:30
  • Also, when I look at my equations (1) and (2), I see $f()$ and $g()$ defined; when I substitute $f()$ into $g()$, I get the same thing you do when I substitute your $h(x)$ into your $J(\theta_i)$ cost function... both end up the same. Just trying to understand the issue/error. Do you see it differently? – Hendy Aug 30 '16 at 19:33
  • 1
    Sorry this took so long to respond to. I think there is some confusion about what you mean by "substituting into". Both $f^{(i)}$ and $g$ as you wrote them above are functions of two variables that output a real number. There is no meaningful way to plug $f^{(i)}$ into $g$; the composition simply isn't defined. In fact, the way you've written $g$ depends on the definition of $f^{(i)}$ to begin with, but not in a way that is well-defined by composition. – Christian Sykes Oct 11 '16 at 0:08
  • 1
    I assume only good intentions, I assure you. Thanks for the feedback. I'll make some edits when I have the chance. Mathematical training can lead one to be rather terse, since eventually it's often actually easier to work with concise statements, but it can make for rather rough going if you aren't fluent. It should tell you something that I thought I was actually going step-by-step! :-D – Christian Sykes Oct 13 '16 at 17:25
  • 1
    @TomHale I edited my answer put in a more detail about taking the partials of $h_\theta$. Is that any more clear now? (Note that I am explicitly not substituting in $h_\theta$ when I compute the partials of $J$. You can certainly do this and get the correct answer, but the extra symbols floating around make it harder to follow imo.) – Christian Sykes Jun 1 '17 at 20:10

conceptually I understand what a derivative represents.

So let us start from that. Consider a function $\theta\mapsto F(\theta)$ of a parameter $\theta$, defined at least on an interval $(\theta_*-\varepsilon,\theta_*+\varepsilon)$ around the point $\theta_*$. Then the derivative of $F$ at $\theta_*$, when it exists, is the number $$ F'(\theta_*)=\lim\limits_{\theta\to\theta_*}\frac{F(\theta)-F(\theta_*)}{\theta-\theta_*}. $$ Less formally, you want $F(\theta)-F(\theta_*)-F'(\theta_*)(\theta-\theta_*)$ to be small with respect to $\theta-\theta_*$ when $\theta$ is close to $\theta_*$.

One can also do this with a function of several parameters, fixing every parameter except one. The result is called a partial derivative. In your setting, $J$ depends on two parameters, hence one can fix the second one to $\theta_1$ and consider the function $F:\theta\mapsto J(\theta,\theta_1)$. If $F$ has a derivative $F'(\theta_0)$ at a point $\theta_0$, its value is denoted by $\dfrac{\partial}{\partial \theta_0}J(\theta_0,\theta_1)$.

Or, one can fix the first parameter to $\theta_0$ and consider the function $G:\theta\mapsto J(\theta_0,\theta)$. If $G$ has a derivative $G'(\theta_1)$ at a point $\theta_1$, its value is denoted by $\dfrac{\partial}{\partial \theta_1}J(\theta_0,\theta_1)$.

You consider a function $J$ linear combination of functions $K:(\theta_0,\theta_1)\mapsto(\theta_0+a\theta_1-b)^2$. Derivatives and partial derivatives being linear functionals of the function, one can consider each function $K$ separately. But, the derivative of $t\mapsto t^2$ being $t\mapsto2t$, one sees that $\dfrac{\partial}{\partial \theta_0}K(\theta_0,\theta_1)=2(\theta_0+a\theta_1-b)$ and $\dfrac{\partial}{\partial \theta_1}K(\theta_0,\theta_1)=2a(\theta_0+a\theta_1-b)$.

  • After continuing more in the class, hitting some online reference materials, and coming back to reread your answer, I think I finally understand these constructs, to some extent. Thank you for the explanation. – voithos Nov 29 '11 at 17:50
  • Gradient descent is ok for your problem, but does not work for all problems because it can get stuck in a local minimum. Global optimization is a holy grail of computer science: methods known to work, like Metropolis criterion, can take infinitely long on my laptop. – richard1941 Apr 26 at 12:52
  • @richard1941 Related to what the question is asking and/or to this answer? – Did Apr 26 at 20:16
  • His question was related to gradient descent for finding optimum; just to point out that there are other ways of doing it. – richard1941 Apr 26 at 21:19
  • @richard1941 Yes the question was motivated by gradient descent but not about it, so why attach your comments to my answer? – Did Apr 27 at 4:37

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.