Why does entropy as error measure leads to overfitting? This post on KDnuggets quoting the post by John Langford states that entropy and mutual information when used as error measures can lead to overfitting. Could you go into more details on this?
 A: I think the key part for these two loss functions is that they are unbounded due to their using logs.
That is, with $x \in [0,1]$, as $x \rightarrow 0$, $\log{x} \rightarrow -\infty$. Here, "brittleness" seems to be implying that certain records can unduly influence the loss, so that a (small) number of these in the training set (and not the test set) would overly influence the loss score and so the update of training parameters, causing overfitting.
The cross-entropy loss function for classification for $n$ observations and some parameters $w$, predictions $\hat{y}$ and actual values $y$ is:
$$J(w) = -\frac{1}{n}\sum_{i=1}^{n}{(y_i \log\hat{y}_i + (1-y_i)\log{(1-\hat{y}_i)})} $$
You can see that if some prediction $\hat{y}_k$ is very small in this, then $\hat{y}_k$ will unduly influence the loss, especially if the true value $y_k$ is nearer to 1. Of course the function is trying to be expensive in these cases, but it's unbounded, so Langford is saying for some combinations of actual/model distribution, and some records, it's unusually expensive, and without already knowing the true distribution, this is always a risk. The same problem exists with mutual information.
A similar problem still exists with other loss functions e.g. high-leverage points in OLS, but it is not unbounded for a finite input domain, and for OLS at least, can be tested for and handled in all cases, using e.g. an influence matrix.
A: Any error measure which does not penalize the complexity of the system may lead to overfitting, e.g. entropy.
In general when you fit your training data to a model which you want to generalize well to new data, this training step is accomplished by minimizing some error measure $E (w) $ which depends, among many things, on your parameters $w $ (a vector that comprises all your model parameters which are going to be fit during training).
If your error measure just cares about fitting better and better your training data, you may find that building models with a huge number of parameters (that aditionally may take any value) is good because your model is so flexible that your training data can be perfectly learnt. On the other hand, if your training data is noisy (which is usually the case) you will this way make your model fit noise also, and this is what overfitting is about.
There are techniques to avoid this, which altogether are called "regularization" techniques, being the most common the ones which add a regularization term to the error function, so that now $E (w) = E_D (w) + E_W (w) $ where $E_D$ is an error that measures how good is your fit (e.g. entropy) and $E_W$ a  penalization for complex models (larger for models with many parameters or large parameter values).
