Constant validation loss and increasing validation accuracy I am training a fully convolutional network. The loss is decreasing whilst the validation loss stays mostly where it is. There is some variance in the validation loss. 
I thought it might overfits, but the validation accuracy is increasing with each epoch. Is this legit? How would something like this happen? Introducing L2 regularization helped in the beginning. Validation loss is at a lower level but stays more or less constant. Big L2 values worsened the loss, the validation loss and the validation accuracy. So I kept at around 1e-5. 
My loss function is a categorical-cross-entropy for a one-hot encoded label. The accuracy is just Keras' standard "accuracy" metric. 
 A: Answering the question of whether it is legit: I'd say that yes this is completely viable to have accuracy vary whilst the cross entropy stays the same:
Cross entropy (binary) is: $ - \sum y_{true} \cdot ln(y_{predicted}) + (1 - y_{true}) \cdot ln(1 - y_{predicted}))$
For multicalss it is a little more complicated but still similar to that, for the multiclass case I normally imagine it as an element-wise multiplication of a matrix with true labels, e.g.
[1 0 0]
[0 1 0]
[0 1 0]

With a matrix of predictions (the logarithm gets applied to the matrix below - just like in the equation above for $y_{predicted}$), e.g.:
[0.5 0.1 0.2]
[0.1 0.7 0.3]
[0.2 0.7 0.2]

And then you sum all things together and divide by the number of elements.
In the perfect case we will be taking the log from 1, which will give us a value of 0.  In other words, in the multiclass case the cross entropy only sums together the values for the actual label.  In the two matrices above the cross entropy would be:
$$
- ln(0.5 * 0.7 * 0.7) / 3 = 0.47
$$
Keras' accuracy is measured as K.mean(K.equal(y_true, K.round(y_pred))) , or using K.argmax in case of multiclass which works more-or-less the same as round but round is easier to understand.
In the multiclass case Keras uses argmax which can be said that rounds the biggest value and considers that the predicted class.  See full description of Keras' accuracy on the answer as Data Science
Problem at hand
Your cross entropy loss is above 1, therefore the majority of the predictions are below 0.368 (i.e. $1/e$) which is quite low.  And moreover it does not need the biggest value predicted for the class. i.e. imagine the following case:
True labels:
[1 0 0]
[0 0 1]
[0 1 0]

Predicted labels:
[0.3 0.5 0.1]
[0.2 0.5 0.4]
[0.3 0.5 0.2]

The accuracy is:
$$
\frac{[1,0,0] \cdot [0,1,0] + [0,0,1] \cdot [0,1,0] + [0,1,0] \cdot [0,1,0]}{3} =
\frac{0 + 0 + 1}{3} = 33.3333\%
$$
And the cross entropy is:
$$
- ln(0.3 * 0.4 * 0.5) = 2.81
$$

Now we tuned the model and got the following predictions instead (I changed the middle value - 2nd row and 2nd column - from 0.5 to 0.3):
[0.3 0.5 0.1]
[0.2 0.3 0.4]
[0.3 0.5 0.2]

The accuracy is:
$$
\frac{[1,0,0] \cdot [0,0,1] + [0,0,1] \cdot [0,1,0] + [0,1,0] \cdot [0,1,0]}{3} =
\frac{0 + 1 + 1}{3} = 66.6666\%
$$
And the cross entropy is still:
$$
- ln(0.3 * 0.4 * 0.5) = 2.81
$$

In summary it is completely possible to have cross entropy to stay the same and have the accuracy vary wildly.
This also explains to some extent (but probably not all) your attempt with regulatrization: a tiny regularization will reduce variance within the predicted numbers, possibly reducing extraneous values that were making the accuracy get the wrong class but not affect the values used by cross entropy.  On the other hand heavy regularization will make all values go towards the mean reducing all values in the predicted matrix including the ones used by the cross entropy.
P.S. The above only happens because we have rather low scores (low for accuracy and high for cross-entropy that is) and the true class in a prediction is likely to have a value very close to all other classes predicted for that sample.  i.e. the predictions are likely looking as $[0.3, 0.31, 0.29]$ rather than $[0.2, 0.6, .1]$.
