11
$\begingroup$

I am new, so may have a biased sample, but it seems a lot of the discussion on "regularized regression" focuses on methods that penalize some norm of the parameter (coefficient) vector. For example in this context ridge regression is the $L_2$ variant and LASSO is the $L_1$ variant.

However in my experience* Tikhonov regularization is typically considered a superset of ridge regression rather than a synonym. (*mostly geophysics inverse problems.) The usage I usually hear is more in line with the Wikipedia definition (linked above), where essentially any matrix can be used on the regularization term, i.e. not just the identity. For example a spatial derivative operator is commonly used in geophysics and computational photography, where the parameter vector represents gridded data. (This usage also seems to be consistent with Richard Szeliski's well-known Computer Vision textbook.)

Is there another term that would be used for this generalized form of in statistics/machine learning? Is it just considered a special case of MAP estimation for correlated Gaussian errors?

$\endgroup$
  • 1
    $\begingroup$ I had a somewhat similar impression but when I first noticed this I saw that the first sentence of the wikipedia page suggests it's the same as ridge regression and I left it at that. $\endgroup$ – Glen_b Sep 2 '16 at 6:43
  • 1
    $\begingroup$ If the more general form is never discussed on CV (even if by another name), then the point is moot for practical purposes. My question was not intended to promote pedantry! $\endgroup$ – GeoMatt22 Sep 2 '16 at 7:16
  • 5
    $\begingroup$ I don't think we need a tag for it at all. It's basically a specialized math topic. I don't see what it contributes that the plain "regularization" tag does not. $\endgroup$ – shadowtalker Sep 2 '16 at 9:21
  • 1
    $\begingroup$ @ssdecontrol that is reasonable to me. I was really half interested in this, and half on the "Where is the more general form used here?" aspect. For example, Tikhonov regularization with a spatial derivative matrix on a grid is very similar in many ways to Gaussian process regression with a kernel-type covariance function (i.e. both give a smoothness prior). But the Tikhonov version is in some ways more flexible, e.g. the $L_1$ variant will give an edge-preserving smoother. (I can consider asking a question on the main site about this.) $\endgroup$ – GeoMatt22 Sep 2 '16 at 15:40
  • 1
    $\begingroup$ Actually a related tag issue is perhaps sparse coding should be a synonym for LASSO? (Currently though there is no tag for sparse coding, though ~170 questions for it. Probably not worth adding it, though it perhaps would draw some Machine Learning folks to LASSO?) $\endgroup$ – GeoMatt22 Sep 9 '16 at 5:38
  • $\begingroup$ The synonym mapping has been removed, see Update to my answer. You might want to mark it as accepted. $\endgroup$ – amoeba Oct 8 '16 at 0:04
9
$\begingroup$

I feel responsible because it was me who suggested this synonym; the suggestion got several upvotes and was implemented in February (the respective answer is deleted so one needs 10k rep to see it).

At the time of merge, had only 4 threads. Since then the synonym was not used a single time (see here in "Renames" column).

If you say that Tikhonov regularization in your field is understood to mean $$\|y-X\beta\|^2 + \|A\beta\|^2$$ with not necessarily $A=\lambda I$, then I agree that it is a bad synonym. It is also an almost useless synonym (it is practically never being used).

Therefore we might want to delete the synonym mapping and, as a result, stay without tag.

Update Oct 8th: The synonym mapping has been removed. There is currently no [tikhonov-regularization] tag. Anybody with sufficient reputation can re-create it; however there would only be a handful (3-5) of questions where this tag would be appropriate, see @Carl's answer from Sep 14th, and so in my opinion such a tag is currently not particularly needed.

$\endgroup$
  • $\begingroup$ I did not see any threads currently where I would put this tag, though I have not looked extensively. I have no objection to deleting the tag. (At most there could perhaps be a note on the Ridge Regression info page that this is sometimes a synonym.) $\endgroup$ – GeoMatt22 Sep 2 '16 at 15:32
  • 1
    $\begingroup$ @GeoMatt22 It's better not to accept answers on Meta until the corresponding suggestion is implemented. If you want the synonym mapping deleted then wait with accepting this answer until it's deleted. $\endgroup$ – amoeba Sep 2 '16 at 18:42
  • $\begingroup$ I do not agree. Ridge regression is much more limited than Tikhonov regularization. There are unnecessary features in ridge regression, the normalization of the smoothing factor being one. Granted, ridge regression is more commonly used than the more general case, but this is probably more the result of a lack of understanding than a valid reflection on applicability. If you really need examples, I will dig some up. But really, that should not be difficult. $\endgroup$ – Carl Sep 8 '16 at 3:42
  • 1
    $\begingroup$ @Carl You do not agree with what? $\endgroup$ – amoeba Sep 8 '16 at 8:14
  • $\begingroup$ @amoeba I do not agree with the idea of deleting the Tikhonov-regularization tag. $\endgroup$ – Carl Sep 8 '16 at 15:49
  • 1
    $\begingroup$ @Carl But you do agree with the idea of deleting the synonym mapping from tikhonov-regularization to rigde-regression? That is how it is at the moment. If the synonym mapping is removed, tikhonov-regularization will stay without a single tagged thread and will be automatically deleted. $\endgroup$ – amoeba Sep 8 '16 at 21:37
  • $\begingroup$ @amoeba Tikhonov regularization is an infinite set compared to ridge regression. Right now, there is no separate tag for Tikhonov regularization, only one for the small subset; ridge regression. It is not a synonym, it is the super set. If anything, ridge regression should redirect to Tikhonov regularization, not the other way around. I understand why it is backwards, ridge regression was invented independently in the west in the 1970's by a statistician, and it was later on pointed out as being a subset of Tikhonov regularization published by the Soviet Academy of Sciences during WW II. $\endgroup$ – Carl Sep 9 '16 at 0:27
  • $\begingroup$ Due to this meta thread, I could not resist adding a Tikhonov regularization comment to this answer! $\endgroup$ – GeoMatt22 Sep 9 '16 at 16:01
  • $\begingroup$ @Carl I am fine with the two being separate, I just did not want think they should be mapped as synonyms. I think it would be sufficient for the connections to be noted on their respective tag wiki pages. Question: If the tags are separated, would you be interested in drafting an info page for the new tikhonov-regularization tag? $\endgroup$ – GeoMatt22 Sep 9 '16 at 16:06
  • $\begingroup$ Side note: Taxonomy is commonly based on two alternative approaches, external characteristics (phenotype) or lineage (phylogeny). I think it is fine to recognize the de facto difference in lineage (use communities) for ridge regression vs. Tikhonov regularization. $\endgroup$ – GeoMatt22 Sep 9 '16 at 16:09
  • $\begingroup$ Can do, but it may take a few days to find the time. I think I have that privilege (barely). But not sure how to. Also, the explanation for ridge regression may be a bit flaky. $\endgroup$ – Carl Sep 9 '16 at 16:18
  • $\begingroup$ @Carl I am not quite certain how the tag revision process works, but nothing will need to happen until we come to a community consensus on this meta question. So at this point I was just asking to assess your interest level (to provide information for the community). $\endgroup$ – GeoMatt22 Sep 9 '16 at 17:15
  • $\begingroup$ @GeoMatt22 OK, I have never seen the difference spelt out, so, here is my stab at it, as an answer, it is too long for a comment. Check it for me dear community. $\endgroup$ – Carl Sep 10 '16 at 4:21
  • 1
    $\begingroup$ I've removed the mapping. $\endgroup$ – Scortchi Oct 7 '16 at 23:44
  • $\begingroup$ Thanks, @Scortchi. I have made a corresponding update. $\endgroup$ – amoeba Oct 9 '16 at 21:04
4
$\begingroup$

Oh boy, hard to help sometimes. This same thing is now on the main site. As the two things are different, ridge regression and Tikhonov regularization I would be in favor of creating a separate tag for Tikhonov regularization. I note that on Wikipedia, ridge regression redirects to Tikhonov regularization and one cannot find much on ridge regression by itself. That is the 'purist' approach. How anyone can get so upset about this as to try to erase the difference between these two things is anybody's guess. We should really have both tags if we want to appeal to people looking for answers. And, I do not think that revisionism or recalcitrance are substitutes for being helpful.

Suppose that for a known matrix $A$ and vector $b$, we wish to find a vector $\mathbf{x}$ such that :

$A\mathbf{x}=\mathbf{b}$.

The standard approach is ordinary least squares linear regression. However, if no $x$ satisfies the equation or more than one $x$ does—that is the solution is not unique—the problem is said to be ill-posed. Ordinary least squares seeks to minimize the sum of squared residuals, which can be compactly written as:

$\|A\mathbf{x}-\mathbf{b}\|^2 $

where $\left \| \cdot \right \|$ is the Euclidean norm. In matrix notation the solution is, denoted by $\hat{x}$, is given by:

$\hat{x} = (A^{T}A)^{-1}A^{T}\mathbf{b}$

Tikhonov regularization minimizes

$\|A\mathbf{x}-\mathbf{b}\|^2+ \|\Gamma \mathbf{x}\|^2$

for some suitably chosen Tikhonov matrix, $\Gamma $. An explicit matrix form solution, denoted by $\hat{x}$, is given by:

$\hat{x} = (A^{T}A+ \Gamma^{T} \Gamma )^{-1}A^{T}{b}$

The effect of regularization may be varied via the scale of matrix $\Gamma$. For $\Gamma = 0$ this reduces to the unregularized least squares solution provided that (ATA)−1 exists.

Typically for ridge regression, two departures from Tikhonov regularization are described. First, the Tikhonov matrix is replaced by a multiple of the identity matrix

$\Gamma= \alpha I $,

giving preference to solutions with smaller norm, i.e., the $L_2$ norm. Then $\Gamma^{T} \Gamma$ becomes $\alpha^2 I$ leading to

$\hat{x} = (A^{T}A+ \alpha^2 I )^{-1}A^{T}{b}$

Finally, for ridge regression, it is typically assumed that $A$ variables are scaled so that $X^{T}X$ has the form of a correlation matrix. and $X^{T}b$ is the correlation vector between the $x$ variables and $b$, leading to

$\hat{x} = (X^{T}X+ \alpha^2 I )^{-1}X^{T}{b}$

Note in this form the Lagrange multiplier $\alpha^2$ is usually replaced by $k$, $\lambda$, or some other symbol but retains the property $\lambda\geq0$

$\endgroup$
  • 1
    $\begingroup$ (Note: I deleted my old comments, as they're no longer relevant to the meta question here; the 2nd part of this question could be ditched too now that it's on CV main) I think objections to the "pure" approach are more for practical reasons. For many users, they may have only the vaguest idea of the linear algebra underlying even OLS. So while the idea of "prevent overfitting by shrinkage" may have some meaning for them, a wall of math will be "TL;DR". This is a reasonable concern to me. (Tikhonov gets more than enough love from the inverse-modeling community, so his legacy will be OK.) $\endgroup$ – GeoMatt22 Sep 10 '16 at 5:15
  • 1
    $\begingroup$ @ameoba What is your pleasure on this? GeoMatt22 seems to be waffling a bit. I just think it is silly not to have both. Let me put it this way, there needs to be more attention paid to cross-pollination. I note for example, that stats sometimes looks completely ridiculous to people with physics training, sometimes for very good reasons, and vice-versa. In my case, I rewrote pharmacokinetics and had a heck of a time getting it published with one reviewer saying things like, "I have a PhD in this, and you do not. Therefore, I am right and you are wrong." There are no words. $\endgroup$ – Carl Sep 10 '16 at 5:29
  • 1
    $\begingroup$ to be clear, this is my position: I agree wholeheartedly with your statement "We should really have both tags if we want to appeal to people looking for answers.". I think that is sufficient, and the two tag-wikis could point out the connections. $\endgroup$ – GeoMatt22 Sep 10 '16 at 5:40
  • $\begingroup$ @amoeba There are 38 threads with Tikhonov regularization in their content somewhere. If we recreate the tag and edit those posts to include it, would that be worthy? $\endgroup$ – Carl Sep 14 '16 at 3:16
  • 1
    $\begingroup$ you should edit this last comment into your answer. I would phrase your suggestion as a concrete course of action and offset it to make it visually obvious. If your answer gathers more upvotes than amoeba's, then the community will have spoken. (As I understand it, you should make your case to the CV community, rather than to amoeba, who is not the arbiter.) $\endgroup$ – GeoMatt22 Sep 14 '16 at 4:04
0
$\begingroup$

There are 38 threads with Tikhonov regularization in their content somewhere. If we recreate the tag and edit those posts to include it, would that be worthy? Please indicate your preference by voting here for reinstate.

Generalized Tikhonov regularization in glmnet?

Tikhonov regularization in the context of deconvolution

Is Tikhonov regularization the same as Ridge Regression?

Why does regularization of coefficient magnitude improve the generalization of linear regression?

This one is interesting in that there is no ridge-regression tag, just regularization--> When is there a representer theorem?

Non negative least squares with minimal colinearity

$\endgroup$
  • 1
    $\begingroup$ Can you please give several examples of threads where you think this tag would be most appropriate? $\endgroup$ – amoeba Sep 14 '16 at 9:54
  • $\begingroup$ This thread for example on the main site. That is because if all one is interested in is ridge regression, then this thread isn't all that interesting, except in some vague theoretical sense. Another and Another do not mention ridge-regression at all, and I'm going through in search order, but, I am running out of comment space. $\endgroup$ – Carl Sep 15 '16 at 1:46
  • $\begingroup$ @amoeba Most threads that mention Tikhonov regularization do not mention ridge regression, some do. 2/3 to 1/3 or something like that. This isn't a burning issue, I would think if someone like me is looking, I would find what I want, but, having both tags might have advantages, for me, it just seems more professional to have both. I would never suggest, for example, that ridge regression be eliminated as a tag just because it is a subset of Tk. But, it seems awkward to redirect a superset to a subset. $\endgroup$ – Carl Sep 15 '16 at 2:05
  • 1
    $\begingroup$ Carl, we agreed that redirection will be removed. After that, [tikhonov-regularization] will automatically disappear. So the only question is, is it worth re-creating it afterwards, or not. As a rough thumb rule, I would say that if we can find at least 5 questions where it would clearly fit then it might be worth it. I suggest you update your answer (this one) listing 5 such questions if you can find them. There are only 14 questions containing word "tikhonov"; most of them would not need this tag but some could. $\endgroup$ – amoeba Sep 15 '16 at 9:03
  • $\begingroup$ @amoeba There are now some listed in the answer above, in some tikhonov-regularization is a more appropriate tag than ridge-regression but I note that some just use the more general tag regularization, probably because Tikhonov regularization was not an available tag. $\endgroup$ – Carl Sep 15 '16 at 19:27
  • $\begingroup$ Another interesting questions is this one, which asks for "an online (recursive) algorithm for Tikhonov Regularisation", but there case is actually ridge regression (though they do not mention it, i.e. this is a "considered a synonym" case). However I found it interesting because perhaps the most common form of Tikhonov regularization and online least squares is in Kalman filtering. (Though that community does not typically use either of those terms!) $\endgroup$ – GeoMatt22 Sep 19 '16 at 18:33
  • $\begingroup$ @GeoMatt22 Yes, they may be using ridge regression, but do not mention the second ridge regression condition namely conversion of $X^TX$ to be a correlation matrix. So, maybe regularization should be the parent term. Some of the regularization tags questions look more like Tikhonov than ridge $\endgroup$ – Carl Sep 19 '16 at 19:43
  • $\begingroup$ @Carl I actually just updated the regularization tag wiki to generalize beyond the typical m-estimator style penalty terms. (Which themselves include Tikhonov/Ridge as the $L_2$-norm flavor, and LASSO/sparse-coding/TVD/etc. as the $L_1$ flavor.) So I would certainly not absorb either of these into the parent. (They could be mentioned/linked in its wiki, though. Just like Tikhonov could link to Kalman, i.e. OK to be related but not synonym or subsumed in terms of tags.) $\endgroup$ – GeoMatt22 Sep 19 '16 at 21:38
  • $\begingroup$ @GeoMatt22 Gee, imagine that, set theory. If I can help, let me know. $\endgroup$ – Carl Sep 19 '16 at 21:54
  • $\begingroup$ @Carl I finished that one. The take home is that sometimes an appropriate tag wiki edit can be used to address incompleteness. (This chat has some discussion of concerns about overly specific tags, for example.) $\endgroup$ – GeoMatt22 Sep 19 '16 at 22:01

You must log in to answer this question.

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