Aditya Krishna Menon

Back in 2011, months of exhaustive experimentation with AUC maximisation in the context of link prediction taught me one thing: it's hard to do better than logistic regression. I was excited when later that year, Kotłowski et al. gave a compelling theoretical explanation for why this might be.

When I joined NICTA in 2013, I followed a rite of passage and read Mark Reid and Bob Williamson's tour de force on information, divergences, and risks. Tucked away in that paper was a mention of how the AUC related to the concepts presented. I innocently mentioned to Bob that perhaps there was more to be said here. He agreed, and suggested that I start by spelling out what was in my mind.

We never expected it would take quite that long to spell. [hide]

Long before being introduced to proper losses, I'd known about, and completely accepted, the basic premise as to why density ratio was different to class-probability estimation: the later only indirectly modelled the ratio, which is generally a sub-optimal strategy. Sometime in late 2015, I re-read the cool work on LSIF. This time, with link functions and partial losses fresh in my mind, I noticed that one could think of this as involving a particular proper loss plus link function. This was mildly interesting, but the point remained: using anything but the link that directly yields the density ratio must be a bad idea.

This was something of a defeat for my running theory at the time, that most everything can be attacked with some version of logistic regression. To better understand this failure mode, I was looking at Sugiyama's elegant unified Bregman view of density ratios. I noticed that logistic regression was mentioned, but didn't pay much attention to it; after all, the Bregman view of regret under proper losses immediately led to the KL minimisation view of logistic regression.

It was only on a re-read that I realised there was a bit more to this innocuous result: it was a statement of Bregman minimisation not to the true probability, but to the true density ratio. Now that I didn't know was true for logistic regression. Studying the surprisingly simple proof, I saw it could be viewed as a surprising equality between the KL divergence on probabilities and on ratios.

I was sure this couldn't be true in general; but why? I worked through the case of a general divergence, trying to find out the line where the proof would break.

Half an hour later, after staring at my working multiple times, I was still incredulous that everything seemed to work in general, too. And so was Lemma 2 born. [hide]

Ever since I read Elkan and Noto's 2008 paper on PU learning, I was fascinated by the topic and their approach; I also felt like I didn't fully grok either, since their sample-selection bias viewpoint was unfamiliar to me. I was inspired to rectify this deficiency on my part when reading one of du Plessis and Sugiyama's elegant papers that extended this work, and crisply stated the problem in terms of the distributions the underlying samples are drawn from.

Around the same time, I also stumbled upon some beautiful works on label noise, notably those of Scott et al. and Natarajan et al. I was struck by the apparent similarity of the two problems, but still couldn't quite decipher the apparently different approaches taken to solve them.

At this stage, I sought to clarify in my mind how precisely these different problems relate. Which, as is my wont, involved thinking about them in terms of class-probabilities. On discussing ideas with colleagues at NICTA (serendipitously interested in very similar problems), soon enough we ended up writing this paper. [hide]