Learning a value of a parameter u given “true” or “false” prediction for each data-point x

Question

We have a data-point x and many classes. Let $P(c|x)$ the probability that $x$ is of class $c$. We note $c_1$ the most probable class for $x$ (i.e. $P_1=P(c_1|x)$ is the highest probability), $c_2$ the second most probable class for $x$ (i.e. $P_2=P(c_2|x)$ is the second highest probability ($P_1> P_2$)).

Obviously, when $P_1$is close to P2 (i.e. $P_1P_2$ is small or closer to 0) we are not sure whether $c_1$ or $c_2$is the true class of $x$, then it is useful to ask for the true label of $x$.

We define $u$ to be a threshold value for the difference between the highest and the second highest probability (a threshold for $P_1$-P2); thus, if $P_1-P_2 > u$ then we can (with some cost) ask for the true class of $x$ (let's note it $c_x$).

$c_1$(the predicted class for $x$) is usually equals to cx, but may sometimes not be equal. Given this problem, I want to learn a good value for the parameter $u$. To do that, currently, I just set u at an initial value (e.g. $u=0.2$) and then adjust this value according to whether or not $c_1$ equals $c_x$:

if $c_1 = c_x$then we get more confident and thus decrease the value of $u$ (e.g. $u=u-\epsilon$), otherwise (when $c_1$!= cx) we get less confident and thus increase the value of u (e.g. $=u+\epsilon$), where $\epsilon=0.01$ for example.

Question:

Is there any better why to "learn" a value for $u$ ? (Assuming that we can start with a hight initial value of u in order to get labelled data at the beginning, or assuming that I have a subset of labelled data that I can to use to learn the value of $u$).

Answer 1

If $P_{1}$ and $P_{2}$ are probabilities, I would rather compare them as $\log P_{1} - \log P_{2} = \log \frac{P_{1}}{P_{2}}$ which is numerically more stable.

As for your question: as I understand it, $u$ is a sort of confidence value. When the difference between $P_{1}$ and $P_{2}$ is below $u$, then you do not trust the result of your classifier.

The idea would be to find a smooth cost function upon which you can apply gradient methods. When a sample is classified correctly $$\log \frac{P_{c_{x}}}{P_{c_{2}}} > 0$$, which to me suggest making use of a sigmoidal function, where the threshold is $u$.

Concretely, you could try to maximize the functional, $$ \sum_{i} J\left(z_{i}+u\right)$$ where $J(z) = \frac {1} {1+\exp (-z)}$ and $z_{i} = \log P_{c_{x}}(x_{i})-\log P_{c_{2}}(x_{i})$ subject to $u > 0$.

For more details on the function, see http://en.wikipedia.org/wiki/Logistic_function. The idea is that the mistakes belong to the left handside of the function. In order to maximize the function, you need to shift the graph to the right in order to make all terms of the sum positive.