I want to learn a nonlinear monotone increasing function $f$ parametrized using a set of weights $w$. Given an input $x$, I can calculate the gradient of the loss with respect to $f(x)$ $\nabla_{f(x)} L$. Then I hope to update $w$ by gradient descent. Ideally, the gradient would be focused on a small set of the parameters $w$ to mitigate the credit assignment problem. I feel like the monotonicity should greatly simplify this problem. Is there any research on this topic?

For example, the parameters could be a set of $z_1 < z_2 < \dots < z_n$ and a corresponding set of $y_i > 0$. Then $f(x)$ could be the interpolated value assuming that it is piecewise linear through the points $(z_i, \sum_{j=1}^i y_j)$. This does not seem easy to train.

  • $\begingroup$ can you explain that with an example? $\endgroup$ – TPArrow Jun 27 '15 at 6:34
  • $\begingroup$ @hamed: You want me to answer my own question? $\endgroup$ – Neil G Jun 27 '15 at 7:21
  • $\begingroup$ :) no but just explain that more. Your question is not clear to me. $\endgroup$ – TPArrow Jun 27 '15 at 10:58
  • $\begingroup$ @hamed: I added an example. $\endgroup$ – Neil G Jun 27 '15 at 11:42

Presume f_fitted(x) is your fitted function. You will have to choose a parameterization. But per your example, piecewise linear is a possibility. You could use fixed break points or have them chosen in the fitting procedure. You could use cross validation to choose the optimal number of break points.

The key to achieving your stated aim of fitting a function which is monotonically increasing is to impose such a condition as part of the fitting optimization problem. So you want derivative of f_fitted(x) >= 0 at all points at which is is defined. It may not be defined at break points if you use linear functions between the break points. So, say you have fitted lines between each break point, you need to impose the constraint that slope >= 0 for each segment. Also impose for all i the continuity constraint that the fitted function between x_i and x_i+1 is equal at x_i+1 to the fitted function between x_i+1 and x_i+2. Together, these constraints will ensure a monotonically increasing continuous function.

You can use the same kind of ideas with functions (basis) other than piecewise linear. In fact, this is roughly the kind of thing that's done in spline regression, except that derivative continuity rather than monotonicity might be imposed

So think of training as fitting, and think of fitting as an optimization problem. Impose the constraints you want as part of the optimization problem. Reading chapter 5 of Hastie, Tibshirani, Friedman 'The Elements of Statistical Learning' may give you ideas on choosing basis functions and how to go about the fitting in general, since perhaps piecewise linear functions may not be a great choice.

  • $\begingroup$ Is this not an adequate answer? Do you need more help? $\endgroup$ – Mark L. Stone Jun 30 '15 at 19:27
  • $\begingroup$ Sorry for the late reply. I don't see your comments unless you precede them with "@NeilG". The first two paragraphs of your answers are a good explanation of my question. I took a look at the chapter you mentioned. However, I could only find things related to spline fitting. I think that there is a lot of structure in my problem that spline fitting does not take advantage of. For example, when you discover that for some x, f(x) is too small, you can increase not only nearby control points, but sometimes also all of the following control points. $\endgroup$ – Neil G Jul 16 '15 at 10:48
  • $\begingroup$ In short, I don't think that curve fitting is a good solution to my problem because it doesn't make use of the constraint of monotonicity. $\endgroup$ – Neil G Jul 16 '15 at 10:49
  • $\begingroup$ @Neil G , as I indicated, you can impose constraints to enforce monotonicity. You need to adapt the book material to impose the constraints you want/need. $\endgroup$ – Mark L. Stone Jul 18 '15 at 23:28
  • $\begingroup$ I'm not sure how to do that in a way that gets the most information from each data point. This answer would be better if it were more explicit. That is, I need to know the model parameters $\theta$, and how to update these parameters given $x$ and the gradient of the loss with respect to $f(x)$. Saying "read this chapter and apply your constraints" is more a restatement of my problem than it is a clear answer. $\endgroup$ – Neil G Jul 19 '15 at 0:29

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.