0
$\begingroup$

I am new to optimization in particular so I think what I am looking for is vocabulary to describe a particular area of problems. In many (all?) optimization algorithms you need to take the gradient of the objective function at various points in the algorithm.

Many examples I find assume you already know the objective function, but, I assume, in most interesting problems you only have inputs and outputs of the objective function (testing and training data set). So how do you go from just the results of the function to the gradient of a function? I guess you could use regression analysis or slope of data points, but what are the common techniques (pros and cons) in optimization?

$\endgroup$
2
$\begingroup$

I think you are confusing the true objective function with the learner's objective function. Often, in machine learning and data science, we approximate a function using a model by following the gradient of the loss function with respect to the parameters of the model.

For example, let us approximate a true objective function $t(x)$ using a model $f(x,\alpha)$, given a dataset of points $(x_i,y_i)$ (with $i \in \{0\ldots n\}$). We first define the loss function as the sum of the loss with respect to each training point:

$\qquad L(x) = \sum_{i=1}^n (t(x_i) - f(x_i,\alpha))^2 = \sum_{i=1}^n (y_i - f(x_i,\alpha))^2$

And then use an optimization procedure to minimize the loss. One way to solve this, is to use gradient descent, which would require you to follow the gradient with respect to the loss function in an online manner:

$\text{while not stop:}\\ \quad\text{pick a parameter index i}\\ \quad\alpha \leftarrow \alpha + \eta \cdot \nabla f(x_i,\alpha) $

Now if we have a form of the model, we can calculate this in a straightforward way. For instance, if $f(x,\alpha)$ is a one-dimensional plane:

$ \qquad f(x,\alpha) = \alpha_1 \cdot x + \alpha_0\\ \qquad \nabla L(x,\alpha) = \nabla(y_i - f(x_i,\alpha))^2 = \nabla(y_i - \alpha_1 \cdot x + \alpha_0)^2 = \ldots $

Plug in the second equation into the algorithm, and you're good to go. This is, of course, just one example. There exist many different formulations of loss functions and many different associated optimization procedures. Enumerating all of them would require an enumeration of the discipline and is simply too broad (although I can say many of the optimization procedure encoutered in machine learning are either linear or convex).

Note also, that we don't always optimize with respect to the loss immediatly. Often, other terms are introduced in the optimization problem such as regularization terms. Furthermore, in some cases we want to avoid working with the loss function directly alltogether, one famous example being support vector machines.

$\endgroup$
2
  • $\begingroup$ $t(x_i a)$ in the loss function above is an approximation derived from the model $f(x,a)$? The model would be something like regression, right? I think I am misunderstanding something, "approximate a function using a model by folowing the gradient of the loss function", but it looks like the loss function is using the approximated function, or are they different functions? $\endgroup$
    – MCH
    Nov 27 '13 at 4:29
  • $\begingroup$ Sorry, I changed the definition while I was writing the post and switched them in the first formula. It should be clearer now. The loss function measure the mistake you are making at a certain time in the algorithm and is equal to the difference between the true value (as observed, $t(x_i) = y_i$) and the predicted value of the model in the current stage ($f(x,\alpha)$, $\alpha$ is the current guess for the parameters). $\endgroup$
    – ciri
    Nov 27 '13 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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