Inverse classification with logistic and softmax classifiers: efficient
  optimization
Miguel Á. Carreira-Perpiñán Suryabhan Singh Hada
In recent years, a certain type of problems have become of interest where one
wants to query a trained classifier. Specifically, one wants to find the
closest instance to a given input instance such that the classifier's predicted
label is changed in a desired way. Examples of these ``inverse classification''
problems are counterfactual explanations, adversarial examples and model
inversion. All of them are fundamentally optimization problems over the input
instance vector involving a fixed classifier, and it is of interest to achieve
a fast solution for interactive or real-time applications. We focus on solving
this problem efficiently for two of the most widely used classifiers: logistic
regression and softmax classifiers. Owing to special properties of these
models, we show that the optimization can be solved in closed form for logistic
regression, and iteratively but extremely fast for the softmax classifier. This
allows us to solve either case exactly (to nearly machine precision) in a
runtime of milliseconds to around a second even for very high-dimensional
instances and many classes.