How can we create neural net to detect false predictions? I created a convolutional network to recognise certain substrings.

For example, the following phrases would be mapped to the "What" class:

What are you doing?
What you doing?
Whatcha doing?


The following to the "How":

How are you doing?
How you doing?


Now, say I have millions of examples and thousands of classes, my network learns relatively well. However, sometimes a new "phrase" that belongs to a never seen class appears. Of course, the model cannot map it to something it has never seen, however, when I look at the output layer values, I was hoping to see all neurons to have small values. My idea was that, I would use the softmax and then if the max value is less than 0.95 or some high value, I would assume the network is unsure, therefore remove that result for manual observation.

However, in many cases, I have seen my network to be almost sure (a neuron with value close to 1) even when it has never seen that class.

For example, say I have the two classes What and How, I would expect:

Whatcha doing? --&gt; "What"= 0.95, "How"= 0.05
How you doing? --&gt; "What" = 0.02, "How"= 0.98
Where you going?--&gt; "What"= 0.6, "How"=0.4


In the last case, the network is not too sure on either, and I would check the input. Unfortunately, this is not working, and I am getting high values (close to 1) neurons for some new input.

How can I fix this? Please, bear in mind, I am happy to sacrifice some accuracy in order to ensure the network never tells me it is sure about new inputs, in other words, I am happy to go and manually check more inputs (even if seen before) rather that let even one unseen input go unnoticed.
One thing you could try is to change the softmax activation on your final layer to sigmoid. This will give a value between zero and one for each class, the sum of which may not equal one. This means that for a given example there may be more than one output neuron activated, or no output neurons activated, in which case you can treat the example as 'unsure' and manually check it out. In the case that there is exactly one output neuron activated (should be most of the time), that should be the classification given.