Automated explanation of machine learning predictions, by: Obtaining an input, a machine learning model, and a classification score produced by application of the machine learning model to the input. Optimizing iterative application of the machine learning model to perturbations of the input, wherein a target of said optimizing is at least a predefined non-zero classification score. Generating, based on one of the perturbations which achieved the predefined non-zero classification score, an explanation to the classification score produced by the application of the machine learning model to the input.