How to utilize user feedback due to miss-classification when correct class label is unknown? Suppose we are developing an app which is supposed to predict a dog's breed by it's picture. We trained a classifier (in my case an MLP) using some dataset and shipped the app to users. Now suppose some user comes and takes a picture of a friend's dog and the app tells her there is 90% chance that this dog is an X. The user knows that this is not true, but she doesn't know what is the dog's breed (if she knew, why would she use our app in the first place?). So we get a feedback which tells us "this is a picture of a dog which is not an X". This sample could be a sample of some other class or a new class or not a dog at all.

I'm looking for a way to use this feedback, to improve the precision of my MLP in class X without touching other classes.
This can be accomplished by a modification to multi-class cross-entropy.

We are faced with two types of supervision. First type is "data $i$ belongs to class $k$" denoted by $y_{ik}=1$, and second type is "data $i$ does not belong to class $k$" denoted by $\bar{y}_{ik}=1$. For example, for 3 classes, $y_i=(1, 0, 0)$ denotes that point $i$ belongs to class $1$, and $\bar{y}_{i}=(0, 0, 1)$ denotes that point $i$ does not belong to class $3$. Let $y'_{ik} \in [0, 1]$ denote the model prediction. The original cross-entropy for $K$ classes is:  

$$H_y(y')=-\sum_{i}\sum_{k=1}^{K}y_{ik}log(y'_{ik})$$.

This objective assigns loss $-log(y'_{ik})$ to $y_{ik} = 1$ to encourage the model to output $y'_{ik} \rightarrow 1$ leading to $-log(y'_{ik})\rightarrow 0$.

On the other hand, for the second supervision $\bar{y}_{ik}=1$, we want to encourage the model to output $y'_{ik} \rightarrow 0$. Therefore, loss $-log(1- y'_{ik})$ can be used to have $-log(1- y'_{ik})\rightarrow 0$.

Accordingly, second supervision can be combined with first one as follows:

$$H_{(y,\bar{y})}(y')=-\sum_{i}\sum_{k=1}^{K}y_{ik}log(y'_{ik})+\bar{y}_{ik}log(1-y'_{ik})$$

Note that supervision "data $i$ does not belong to classes $1$ and $2$" is also supported. For example, $\bar{y}_{i}=(1, 1, 0,...)$ activates both $-log(1 - y'_{i1})$ and $-log(1 - y'_{i2})$ to encourage the model to output less probabilities for classes $1$ and $2$, i.e. $y'_{i1} \rightarrow 0$, and $y'_{i2} \rightarrow 0$.