You give the source’s explanation yourself, where it says in your link:
Imagine that you assign a unique id to each example, and map each id
to its own feature. If you don't specify a regularization function,
the model will become completely overfit. That's because the model
would try to drive loss to zero on all examples and never get there,
driving the weights for each indicator feature to +infinity or
-infinity. This can happen in high dimensional data with feature crosses, when there’s a huge mass of rare crosses that happen only on
one example each.
And from Logistic Regression for Machine Learning:
It’s an S-shaped curve that can take any real-valued number and map it
into a value between 0 and 1, but never exactly at those limits.
This "never exactly at those limits" is the point, the logistic regression can almost perfectly predict the class, but is never 100 % sure. Thus the weights can grow almost infinitely as soon as the classes are hit in the vast majority of cases, which can happen if you allow for higher dimensions with a huge mass of rare feature crosses.
Part 1: paper on rare feature crosses
Alert: I am not sure about *Part 1*, this is already edited a lot and it is still vague and might be wrong! Main point of change: an unconstrained MLE is for rare feature crosses, and the constrained MLE is the usual case in low dimensionality, meaning much more observations than features. I rather recommend *part 2* as the main answer. *Part 1* was merged with *Part 2*, it has been a separate answer before.
I assume that the paper "The Impact of Regularization on High-dimensional Logistic Regression" which also uses this outstanding term "rare feature crosses" answers the question here.
This would also be in line with the highly voted comment of @DemetriPananos:
The question is probably about ...
... complete or quasi-complete separation. High dimensional space is
weird, and there may exist some affine plane which perfectly or almost
perfectly separates the 1s from the 0s. In such a case, the
coefficients of the model are very large and the model will predict
probability near 0 or 1 for each case respectively.
Back to the paper, at best, read the abstract of the paper yourself. I just try to show the core of it here, and I am not a professional, perhaps someone can correct me in the following conclusions (with some luck, I got it right, though):
The problem arises from models
where the number of observations and parameters are comparable“ so
that “the maximum likelihood estimator is biased. In the
high-dimensional regime the underlying parameter vector is often
structured (sparse, block-sparse, finite-alphabet, etc.).
Which is nothing but the mass of rare feature crosses meant in your source’s explanation.
An advantage of RLR is that it allows parameter recovery even for
instances where the (unconstrained) maximum likelihood estimate does
I can only assume now that this (unconstrained) MLE does arise from a rare feature cross, with the problem of those observations that are not a rare feature cross and thus need to be "recovered" as parameters because they are dominated by the high weights that the rare feature crosses receive.
In other words: in the usual case and in small dimensionality, a constrained MLE exists for each observation, it is calculated over a given number of observations that face a smaller number of features - thus it needs to be calculated by using constraints. With higher dimensionality, rare feature crosses arise where an unconstrained MLE exists, because parameters and observations become 1:1 cases then: one unique feature (~ parameter) = one isolated class assignment (~ observation).
In these cases, those observations that are not mapped to just one feature lose their impact and need to be recovered by regularisation.
An example from the universe: Think of a case where you can explain say that something is a planet or not from the planetary circles around the sun and you use three features for this (in this example, they are all classified as planets except for the sun). Then you add a dimension by making the earth the center instead. This means you do not need more "new" features, instead you just need a higher dimensionality of the same features that are used in the sun model to explain the circles - and that is the same as adding new features, just by using more dimensions of the original features.
You might just take three features to prove that all are planets around the sun as a binary problem: planet yes or no, as long as a function can explain the planetary circlre using just the three features. As a next step, you can take whatever dimensionality you want of those three features to improve your model around the earth instead. And adding those higher dimensionalities is the same as adding entirely new features. Then, those functions which perfectly explain a planet by an isolated multidimensional feature (a feature that never explains any other planet) can get very high weights in the model, while those planets that are not that isolated from each other in their functions, because their parabolic functions are rather similar, cannot have infinite weights because there will be a part of the planet circles that gets explained worse when improving the explanation of the other part to 100 %. Now if you go to a very sparse area adding more and more dimensionality, you will get to a model where finally all planets can be marked as planets according to some isolated features that are not used for the other planets' functions. These are the rare feature crosses, there is no interception anymore with any other features. Such features only explain one single planet with its planet function. And thus those high-dimensional features can get infinite weights.
What is the final idea here to answer the question at all?
I assume that the logistic regression which never reaches probability 1 or 0 leads to the infinite weights of the rare feature crosses which causes the model to overfit on the rare feature crosses.
We cannot repair the MLEs because they depend on the number of features and obervations, and we cannot just change the number of features or observations. Instead, we can reduce the weights of the rare feature crosses to recover the parameters that are no rare feature crosses.
Which gives us the next conclusion: When the „number of observations and parameters are comparable“, so that you have a mass of rare feature crosses in great sparsity, you lose the ordering function of the MLEs for the rest that is not in this "mass".
End of the abstract:
... and so in this paper we study regularized logistic regression (RLR),
where a convex regularizer that encourages the desired structure is
added to the negative of the log-likelihood function.” meaning a
well-calibrated regularizer can solve the whole issue of the so much
needed constraints by using a convex cost function of the weights (L1
and L2 are both tested) as part of the loss.
Part 2: Intuition of rare feature crosses in maths and graphs
Repeating the quote of your link at the beginning of this answer:
This can happen in high dimensional data with feature crosses, when
there’s a huge mass of rare crosses that happen only on one example
The rare feature crosses can already be understood in a 2-dimensional graph with 2 classes (mathematically, a logistic regression is always for 2 classes, though it can be used to predict multiple classes with the One-vs-All method) that are scattered in slightly overlapping clouds of observations, see the middle row "Classification illustration" (and then after this example, think of the mass of rare feature crosses in 3dim "Classification illustration" in a sparse area):
The borderline between the two classes in the x1/x2 "Classification illustration" example shows the constant likelihood value y = 0.5 to be class 1 or 0.
In this "Classification illustration", with every added dimension (not of new variables, but of the same explanatory variable to the power of 2, 3, 4 aso.) the borderline of the observations‘ classes gets more flexible.
It is like adding new "explanation power", until you find all the dimensions you need to explain all labels.
- "Classification illustration", middle graph, (dim 2):
When adding 1 dimension means to introduce x1^2 and / or x2^2, the graph has 2 features and 1 or 2 calculated "artificial" features, though there are just 2 original features.
- "Classification illustration", right graph, (e.g. dim 9):
In very high dimensionality, the 2 classes can be assigned so well that perfect separation can be reached. Two different classes can be spread in quite some chaos, you might perfectly separate them when you go up to the power of 9, meaning to have 9 different x1 and / or x2 variables to assign the classes correctly.
#### Deep Learning side-note START
- In the Deep Learning example (bottom row), the logistic regression is used as the activation function. Please note that this has to be kept apart from the classification example which is the better example to answer the question.
The logistic regression is a sigmoid function. A wide variety of sigmoid functions including the logistic and hyperbolic tangent functions have been used as the activation function of artificial neurons (https://en.wikipedia.org/wiki/Sigmoid_function). They are used in order to enable nonlinear mapping of the output, so that large numbers do not change so much the activation value anymore, and this because of the asymptotical nature of the curve. The problem is still the same, since every single neuron can be seen as an isolated fitting problem that can also overfit for the same reasons as it is happening in the 2-D-classification example. Once the neuron knows that "it is right", it will allow to increase the probability = activation value to almost
g(z) = 1 by admitting the weights to grow infinitely.
Mind that this Deep Learning paragraph should better be ignored in the direct answer of the question. It is not intuitive and just confusing to the reader since the actual problem of overfitting in neural networks is rather a problem of capacity, not of the activation function. A higher capacity leads to overfitting as well as the asymptotical nature of the logistic regression in higher dimensionality of the "Classification illustration". Better keep "Regression illustration" & "Classification illustration" separate from "Deep Learning illustration". Yet, here is a regression example of an overfitting Deep Learning model, please judge yourself whether that adds to the answer of the question:
Regression and classification examples in a Deep Learning look like those without Deep Learning, see the classification example as follows. On the right, see the examples of underfitting (straight line on the right) vs. overfitting (very complex curve that hits every point):
Capacity differences lead to the difference. It is unclear in what way the logistic regression in the activation function changes the capacity of a network. Definition Capacity: the more trainable parameters, the more functions can be learned and the more complex these functions can be. The capacity (number of layers, number of neurons, complexity of the propagation and activation function, and other parameters, seems to be comparable to the question's "higher dimensions", at least the results are the same and that is why I suspect the capacity to be the equivalent problem to the high dimensions of x1 and x2 in a non-Deep-Learning classification problem.
My guess: the activation function (here: logistic regression) is part of the capacity of a neural network. This would justify this whole paragraph here. If instead the capacity were not partly changed by the choice of the activation function, then this Deep Learning paragraph would have no relevance in answering the question and should be ignored / deleted, as other parameters (number of layers, number of neurons) are not a problem specific to logistic regression.
Here is another hint that the increased dimensionality is meant as the input also in the deep learning setting, see the green marker for the 5 higher dimensionalities.
Source: sigmoid with 7 features (5 in high dimensions) which can be run at https://playground.tensorflow.org/#activation=sigmoid&batchSize=25&dataset=circle®Dataset=reg-gauss&learningRate=0.01®ularizationRate=0.3&noise=20&networkShape=5,4&seed=0.70944&showTestData=false&discretize=false&percTrainData=30&x=true&y=true&xTimesY=true&xSquared=true&ySquared=true&cosX=false&sinX=true&cosY=false&sinY=true&collectStats=false&problem=classification&initZero=false&hideText=false
Strangely, all of the other activation functions have more overfitting than the sigmoid at the use of 5 higher dimensions in 7 features. In the tensorflow playground, you can just change the activation function to check this. The test result at 2760 epochs and 7 features (5 in high dimensions) as follows.
Perhaps the logistic regression is not "especially prone to overfitting in high dimensions" in neural networks? Or these are just too few dimensions added. If we added up to dimension x^9, it might be the case that the logistic regression in the activation functions will overfit the model more than ReLU and linear. I doubt that tanh will be so much different since it is also asymptotical to -1 and 1.
#### Deep Learning side-note END
Core part of this answer, at best looking at the simple classification problem in 2D:
The increase in dimensionality has an effect as if you added new features, until finally every observation is assigned to the right class. After a certain increase in dimensionality you can hit every class.
The resulting unstructured skippy borderline is an overfitting in itself because any visual generalisability is lost, not just to the human eye in this 2dim example, but also for the determination of the correct loss to keep the training relevant for the testing set - the loss simply vanishes to 0. If the regularisation does not punish high weights in order to increase the loss again, the weights of rare feature crosses (metaphorically the skippy borderline, but instead now in a sparse area in high dimensionality) grow without restrictions, overfitting the model. Switching to the other side, this means that the weights of more densely scattered observations (that share some features among each other so that they are no rare feature crosses) lose weight, relatively and also absolutely, possibly till 0, even though they are probably relevant in the testing set.
See here how this looks mathematically. You see that the original two features x1 and x2 stay the only ones, there is no feature added! They are just used in different combinations and dimensionalities.
And here is another visualisation of the increased dimensionality meant in the question:
The sigmoid activation function g(f(x)) can evaluate f(x) both as a multi-dimensional (= polynomial) regression and as a one-dimensional regression.
This supports the idea that adding dimensionality is meant to add different combinations and dimensions of the already existing features (x1,x2) - and it is not to add "new original features" (x3,x4...) as "new dimensions".
And it thus stands in contrast to the accepted answer above which explains the problem of the question by adding predictors (= original features): "As a result, regularisation becomes more important when you have many predictors." This statement seems just wrong to me.
To the point. Why the accepted answer seems to be wrong:
The overfitting issue is not because of added predictors (taking the name of the accepted answer here, = features). It is about using different combinations and dimensions of the existing predictors (features) as artificially new predictors (features). Staying in the examples: x1 and x2 is all what you need to get the overfitting problem explained, no x3 is needed for this. The accepted answer would be only right if it defined "many predictors" as "existing features together with their different combinations and dimensionalities" like x1^2 + x2^2 + x1x2, which I doubt it does, since there is no word about that. Thus in this case, a 200 points assigned accepted answer seems not to offer the true and complete explanation, though its basic direction is right, since: more predictors will tend to overfit the model due to the asymptotical nature of the logistic regression - IF these "more predictors" are the derived higher dimensions from already existing predictors.