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

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$).

-
What is u? You started talking about it before introducing it. More generally: please take a few moments to edit your question for clarity and consistency in use of notation. – Arthur Small Jan 14 '13 at 20:40
@ArthurSmall done, 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$). – shn Jan 15 '13 at 16:16

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.

-
(1) Why do you think using "Log P1 - Log P2" is better than just "P1 - P2" ? (2) Is what I've called P1 the same as P* in your explanation ? (3) What do you mean by log P(x) ? is it same as Log P – shn Jan 19 '13 at 14:22
1. Underflow. When working with probabilities, you handle small numbers, 2. Sorry for the confusion. Now that I re-read your question: $P_{*} = P_{c_{x}}$ in your notation. 3. $\log P_{c}(x) = \log P(x|c)$ – jpmuc Jan 19 '13 at 15:03
I just edited it for clarity. Now I use the same notation and terms you introduced – jpmuc Jan 19 '13 at 16:41
It is not very clear how to find $u$ such that the sum of all terms (over i) is maximized. The more we choose $u$ high the more $J(z_i + u)$ is high. Can you please explain more clearly how to how to find $u$ such that the sum of all terms (over i) is maximized ? Should I for each $x_i$ find the value of $u_i$ for which $J(z_i + u_i) = 0.5$, and the put $u$ equals to the average of values $u_i$ ? – shn Jan 23 '13 at 22:22
With your suggestion, always given a highest value for $u$ will maximize the sum function. Maybe another point that we forgot to talk about is the about cost of making a wrong prediction (error) and the cost of failing to make a prediction (rejection). For me the 1st cost is higher than the 2nd: if we are not sure about the predicted class, then we prefer to reject the data and ask a human for its true class. Let's say that the error cost EC (0<EC<1) is a parameter given by the user and that the reject cost RC = 1-EC. – shn Jan 23 '13 at 23:23