0
$\begingroup$

The Linear Regression objective is given by $$ J(\theta) = \frac{1}{2}\sum_{i = 1}^N\Big(h(x^{(i)})- y^{(i)}\Big)^2 $$ and we assumed that the hypothesis function has the form $$ h(x) = \sum_{i = 0}^n\theta_i x_i = \theta^\top x $$ Consider the case when the hypothesis is instead given by $$ h_\phi(x) = \sum_{i = 0}^m\theta_i \phi(x)_i = \theta^\top \phi(x) $$ where $\phi : \mathbb{R}^n \mapsto \mathbb{R}^m$ is an arbitrary feature map. Work out the gradient descent step for this new hypothesis function

Solution For one training sample the error is given by \begin{align*} J(\theta)&= \frac{1}{2}(h_\theta(x) - y)^2\\ &=\frac{1}{2}(\theta^\top\phi(x) - y)^2 \end{align*} The gradient step is $$ \theta_j = \theta_j - \alpha\frac{\partial J(\theta)}{\partial \theta_j} $$ and the gradient is \begin{align*} \frac{\partial J(\theta)}{\partial \theta_j} &= (h_\phi(x) - y)\frac{\partial }{\partial \theta_j}(h_\phi(x) - y)\\ &= (h_\phi(x) - y)\frac{\partial }{\partial \theta_j}\Big(\sum_{i = 0}^m\theta_i\phi(x)_i - y\Big)\\ &=(h_\phi(x) - y)\phi(x)_j \end{align*} Hence $$ {\color{red}\theta_j} := \theta_j + \alpha (y - h_\phi(x))\phi(x)_j\tag{1} $$

My questions

  1. In (1), shouldn't we write ${\color{red}\theta_{j+1}}$ instead of ${\color{red}\theta_{j}}$?
  2. Do we always use gradient descent with one single training example? Is it possible to use a batch or the whole training set to compute a step.
  3. If yes to 2. what would be the mathematical form? / If no to 2. is it because it mathematically not possible/hard or is it because it computacionaly too expensive?

Edit

The step using the whole training set can be computed as \begin{align*} \frac{\partial J(\theta)}{\partial \theta_j} &= \frac{\partial}{\partial \theta_j} \sum_{i = 1}^N\frac{1}{2}(h_\theta(x)^{(i)} - y^{(i)})^2\\ &= \sum_{i = 1}^N\frac{\partial}{\partial \theta_j}\frac{1}{2}(h_\theta(x)^{(i)} - y^{(i)})^2\\ &=\sum_{i = 1}^N(h_\phi(x)^{(i)} - y^{(i)})\phi(x)_j \end{align*} Hence $$ \theta_j := \theta_j + \alpha \sum_{i = 1}^N(h_\phi(x)^{(i)} - y^{(i)})\phi(x)_j $$

$\endgroup$

1 Answer 1

1
$\begingroup$

(1): $\theta$ is an $m$-dimensional vector, and $\theta_j$ is referring to its $j$-th component. Equation (1) simply means reset the $\theta_j$ to be the right hand side. To avoid confusion, this can be written as $$\theta_j^{(t+1)} = \theta_j^{(t)} + \ldots$$ so that the step count is in the superscript.

(2): No, you can use any batch size (including the whole training set) to perform a step. Using the whole training set for each step is called batch gradient descent. Choosing smaller batch sizes (such as a single training example) is called stochastic gradient descent if training examples are randomly chosen on each step. I would say that batch gradient descent is more common, especially for linear regression.

(3): It is not mathematically hard, because the sum and derivative can be interchanged: $$\frac{\partial J(\theta)}{\partial \theta_j} = \frac{\partial}{\partial \theta_j} \sum_{i=1}^N \frac{1}{2} (h_{\phi}(x^{(i)}) - y)^2 = \sum_{i=1}^N \frac{\partial}{\partial \theta_j} \frac{1}{2} (h_{\phi}(x^{(i)}) - y)^2 $$ You already know how to compute each term in the sum, so you just have to add them all together. However, if $N$ is extremely large (like a million), then computing this sum is prohibitive.

When $\phi$ is the identity function, then this is the usual least squares problem. Notice that this has a closed form solution (see "Solving the least squares problem"). In other words, you don't have to use gradient descent at all! I'm not sure if a similar trick works for your case, but it would be interesting to try.

$\endgroup$
2
  • $\begingroup$ Many thanks for your comment @pbn990. I tried to devlop more your answer (3) in my edit, but it looks wrong as $\alpha$ now multiplies a sum. What would be the correct devlopped answer for the computation of the gradient step with the whole training set? $\endgroup$
    – ecjb
    Jan 1, 2020 at 16:57
  • $\begingroup$ Hi, it looks correct to me... the sum is still a scalar quantity so there is nothing wrong with multiplying it by $\alpha$! $\endgroup$
    – user446766
    Jan 1, 2020 at 17:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .