# Cute math trick and some tips for proofs

I had the privilege of attending ICML 2019 with some colleagues last month, and I’ve started working through some of the papers that stood out to me. First on the docket: Combating Label Noise in Deep Learning Using Abstention. Key idea: When classifying $k$ variables, create a $k+1$ category, codify the extra class as “choosing to abstain”, and then train your model to abstain explicitly rather than deriving abstention after the fact based on classification scores.

## The trick

I was hitting some issues with the very first formula in the paper (I’m new to research if that wasn’t obvious), and I wanted to see how the authors coded it up.

The formula

$${L}(xj) = (1 - p{k+1})(-\sum^{k}_{i=1} t_i \log \frac{pi}{1 - p{k+1}}) + \alpha \log \frac{1}{1 - p_{k+1}}$$

Gets translated to

loss = (1. - p_out_abstain)*h_c - \ self.alpha_var*torch.log(1. - p_out_abstain)


This seems okay (log transform on the rightmost term but whatever), but what is h_c?

h_c = F.cross_entropy(input_batch[:,0:-1],target_batch,reduce=False)


Huh? What happened to $\log \frac{pi}{1 - p{k+1}}$? It took me a few tries to convince myself, but these are actually equivalent.

Even after I was convinced, I had to chew on the proof for a bit. I revisited the problem after a long weekend off, and it’s pretty slick.

$$\begin{split} \frac{pi}{1 - p{k+1}} &= \frac{\frac{e^v}{\sum^{k+1}{i=1}e^v}}{1 - p{k+1}} && \text{given ouput } v \text{, softmax function} \ &= \frac{e^v}{\sum^{k+1}{i=1}e^v} \cdot \frac{1}{1 - p{k+1}} \ &= \frac{e^v}{\sum^{k+1}{i=1}e^v} \cdot \frac{1}{\sum^{k}{j=1}pj} && \quad\text{(1) } \ &= \frac{e^v}{\sum^{k+1} {i=1}e^v} \cdot \frac{1}{\sum^{k}{j=1}(\frac{e^v}{\sum^{k+1}{i=1}e^v})} \ &= \frac{e^v}{\sum^{k+1}{i=1}e^v} \cdot \frac{\sum^{k+1}{i=1}e^v}{\sum^{k}{j=1}e^v} \ &= \frac{e^v}{\sum^{k} {j=1}e^v} \ &= p_j && \text{by softmax definition} \end{split}$$

This means that

$$\begin{split} \text{h_c} &= -\sum^{k}_{i=1} t_i \log \frac{pi}{1 - p{k+1}} \ &= -\sum^{k}_{i=1} t_i \log p_i \ &= \text{cross_entropy}(v, t) && \text{for outputs, targets } v,\space t \end{split}$$

Pretty cool stuff, but definitely deserved a comment!

## The tips

As mentioned above, it’s been a few years since I tried a proof (and to be honest, I don’t think I ever successfully did this much series - apologies to my Calc II teacher). Here are some tips I have for future me the next time I try this, maybe someone else can find them useful, too.

• Demonstrate, then prove. When I originally saw h_c, I assumed it was a typo or mistake in the calculation. It wasn’t until I’d shown for myself that the trick works in practice that I could approach demonstrating why it worked
• A little understanding goes a long way. I spent many hours on this little proof. If I had to give a “eureka” moment, it’d definitely be understanding what $1 - p_{k + 1}$ represents (See $\text{(1)}$ in the proof.). It wasn’t until I asked myself out lout Well, what is this? and answered with The remaining probability mass of the sum of the first k probabilities that I saw a path through the proof.
• Don’t stress subscripts at first, just focus on what’s a scalar and what’s a vector. This might be a little too specific, but I found labeling the dimension of each term immensely helpful. My first work through of this proof eschewed subscripts entirely Instead, I just noted when each value represented a scalar or a vector. I haven’t used many vector-valued functions in proofs, and this explicit labeling approach helped me a lot more than pining for intuition. (Note: This technique was especially helpful, I think, because $p_i$ is overloaded in the paper - see my introduction of $p_k$ in the proof).