Method and processing unit for computer-implemented analysis of a classification model

Abstract

Provided is a method and processing unit for computer-implemented analysis of a classification model which is adapted to map, as a prediction, a number of input instances, each of them having a number n of features, into a number of probabilities of output classes, as a classification decision, according to a predetermined function, and which is adapted to determine a relevance value for each feature resulting in a saliency map. The disclosure includes the step of identifying an effect of each feature on the prediction of the instance by determining, for each feature, a relevance information representing a contextual information for all features of the instance omitting the considered feature. Then, the relevance value for each feature is determined. Finally, the plurality of relevance values for the features of the instance is evaluated to identify the effect of each feature on the prediction of the instance.

Claims

1. A method for computer-implemented analysis of a classification model which is adapted to map, as a prediction, a number of input instances, each of them having a number of features, into a number of probabilities of output classes, as a classification decision, according to a predetermined function; and which is adapted to determine a relevance value for each feature resulting in a saliency map; comprising the steps of: identifying an effect of each feature on the prediction of the instance by determining, for each feature, a relevance information representing a contextual information for all features of the instance omitting the considered feature; determining the relevance value for each feature by combining the relevance information for the features of the instance; evaluating the plurality of relevance values for the features of the instance to identify the effect of each feature on the prediction of the instance.

2. The method according to claim 1, wherein the relevance value for each feature is calculated by the sum of the ratios of the relevance information and the absolute value of the relevance information with feature being the omitted considered feature.

3. The method according to claim 1, wherein the relevance value for each feature is equal to or larger than 0.

4. The method according to claim 1, wherein the relevance information (R.sub.\i) is determined by calculating
R.sub.\i=f(x)−Σ.sub.k=1.sup.Mp(v.sub.k|x.sub.i)p(y|x.sub.i,v.sub.k)=f(x)−f(x.sub.i), with v.sub.k being the sampled values conditional on x.sub.i, x.sub.i being feature i of the instance x, M being the number of samples or classes considered and y being an output class.

5. The method according to claim 1, wherein, when analyzing a classification model of high-dimensional images on deep neural networks, image patches instead of pixels are used as individual features.

6. The method according to claim 5, wherein the shape of the image patches is squared.

7. The method according to claim 5, wherein, instead of splitting the image into separated image patches, a patch is slid over the whole image with a fixed stride.

8. The method according to claim 1, wherein the classification model is a model-agnostic method.

9. A computer program product, comprising a computer readable hardware storage device having computer readable program code stored therein, said program code executable by a processor of a computer system to implement a method, directly loadable into the internal memory of a digital computer, comprising software code portions for performing the steps of claim 1 when the product is run on a computer.

10. A processing unit for computer-implemented analysis of a classification model which is adapted to map, as a prediction, a number of input instances, each of them having a number of features, into a number of probabilities of output classes, as a classification decision, according to a predetermined function; and which is adapted to determine a relevance value for each feature resulting in a saliency map; the processing unit being configured to identify an effect of each feature on the prediction of the instance by determining, for each feature, a relevance information representing a contextual information for all features of the instance omitting the considered feature; determine the relevance value for each feature by combining the relevance information for the features of the instance; evaluate the plurality of relevance values for the features of the instance to identify the effect of each feature on the prediction of the instance.

11. The processing unit according to claim 10, which is further adapted to carry out the steps of identifying an effect of each feature on the prediction of the instance by determining, for each feature, a relevance information representing a contextual information for all features of the instance omitting the considered feature; determining the relevance value for each feature by combining the relevance information for the features of the instance; evaluating the plurality of relevance values for the features of the instance to identify the effect of each feature on the prediction of the instance, wherein the relevance value for each feature is calculated by the sum of the ratios of the relevance information and the absolute value of the relevance information with feature being the omitted considered feature.

Description

BRIEF DESCRIPTION

(1) Some of the embodiments will be described in detail, with references to the following Figures, wherein like designations denote like members, wherein:

(2) FIG. 1 shows a program sequence according to an embodiment of the present invention;

(3) FIG. 2a shows a table illustrating explanations produced by different approaches for text classifications of a naive Bayes classifier;

(4) FIG. 2b shows a table illustrating explanations produced by different approaches for text classifications of a naive Bayes classifier.

DETAILED DESCRIPTION

(5) A deep neural network is a function mapping input features into a target space. Individual classification decisions of the deep neural network can be explained by way of saliency methods by creating saliency maps. Saliency maps produced by existing methods are however, not reliable. The two main model-agnostic explanation methods are LIME and PDA.

(6) LIME trains a small classifier with interpretable weights (e.g., linear classifier) to approximate a local decision boundary of deep classifier. For each classification decision, this approach requires to train a new classifier, which is inefficient. Given a single classification, the optimization of a classifier could end with different parameters, which leads to inconsistent explanations. When explaining a classification using different classifiers, LIME produces different explanations.

(7) PDA is another model-agnostic method to analyze classifiers. PDA is a probabilistic sound methodology and identifies the relevance of input features by marginalizing the effect of this feature and computing their prediction difference. PDA faces many challenges when it is applied to high-dimensional data. It requires many forward inferences, which is very slow. To reduce the times of inferences, it can analyze an image in super-pixel level. Beside this, PDA suffers from another problem that the method does not work well when many features of the classified instance support classifications which is called saturated classification.

(8) In the following, PDA will be explained in more detail as PDA will form the basis for the suggested improved method for computer-implemented analysis of a classification model.

(9) Generally, a classifier is a function mapping input instances into probabilities of output classes f:x.fwdarw.f(x). Each instance has n features x={x.sub.1, x.sub.2, . . . , x.sub.n}. Given a classification decision f(x) of the instance x, saliency methods assign a relevance value r.sub.i to each feature x.sub.i. The resulted saliency map is defined as R={r.sub.1, r.sub.2, . . . , r.sub.n}. To identify the effect, a feature x.sub.i has on the prediction of the instance x, PDA computes the difference between the two predictions:
r.sub.i=D(f(x),f(x.sub./i)),  (1)
where f(x.sub.\i) means the model's prediction without the knowledge of the feature x.sub.i (marginal prediction) and D( ) is a function measuring the difference between two predictions. Two different ways may be used to evaluate such difference. The first is based on information theory. For a given class y, this measure computes the difference of the amount of information necessary to find out that y is true for the given instance x.
r.sub.i=log.sub.2p(y|x)−log.sub.2p(y|x.sub.\i)[bit].  (2)

(10) The second one directly computes the difference between two probabilities as follows:
r.sub.i=p(y|x)−p(y|x.sub./i).  (3)

(11) In the following, the difference is evaluated using a second measure. The first term p(y|x) can be obtained by just classifying the instance x with the classifier to be explained. The second term is computed by setting the feature x.sub.i unknown, which is allowed only in a few classifiers, e.g. naive Bayesian classifier. Another way to remove the effect of the feature x.sub.i is to retrain the classifier with the feature left out. Such retraining procedure is not feasible when the input instance is high-dimensional, such as is the case with images. A practical approach to simulate the absence of a feature is to marginalize the feature:
p(y|x.sub.\i)=Σ.sub.k=1.sup.Mp(v.sub.k|x.sub.\i)p(y|x.sub.\i,v.sub.k),  (4)
where v.sub.k is a sampled value for the feature variable x.sub.i. The conditional probability p(x.sub.j|x.sub.\i) can be approximated with the prior probability p(x.sub.j) and considers a single input variable one feature.

(12) As will be shown below, PDA suffers from classifier saturation. Given an instance x={x.sub.1, x.sub.2, x.sub.3} and a classifier specifying its probability of belonging to a class c: p(c|x)=max(x.sub.1, x.sub.2, x.sub.3) where x.sub.i∈[0,1], individual classification decisions are made by the classifier using PDA. A concrete instance x={1,1,0} is classified as p(c|x)=max(1,1,0)=1. Following PDA, the relevance values of the three input features are as follows:
r.sub.i=p(c|x)−p(c|x.sub.\i)=0,i∈{1,2,3}.  (5)

(13) The analysis result means that the relevance values of all the features are zeros, which is on the contrary to the fact that the features {x.sub.1, x.sub.2} support the classification decision.

(14) The saturation phenomenon exists widely in the existing state-of-the-art classifiers. In image classification, many visual features could contribute to a single classification decision at the same time. For instance, in an image, two zebras support that the image belongs to the class “Zebra”. When analyzing the classification decision on a series of state-of-the-art classifiers using prediction difference, different parts of the image are removed.

(15) Table 1 shows the prediction differences of the respective samples, which is the relevance value of the removed visual feature. All the classifiers are confident to classify the original images as a zebra. In an image img_1, the head of one zebra is removed and the rest of the visual features is classified. The confidence of all classifiers hardly decreases, which means these classification decisions are saturated. Similarly, if the head of the other zebra in image img_2 is removed, all the classifiers also show high confidence as in the original image img_0. The removal of part of the background does not decrease the classification score (img_3). PDA assigns the difference as the relevance of the removed visual features to the classification decision. It is observed that PDA does not work in this case.

(16) TABLE-US-00001 TABLE 1 classification scores of different images Image img_0 img_1 img_2 img_3 AlexNet .9999 .9999(+.0000) .9999(+.0000) .9999(+.0000) VGG16 .9998 .9995(−.0003) .9997(−.0001) .9997(−.0001) Inception_V3 .9415 .9365(−0.050) .9587(+.0172) .9336(−.0079) ResNet .9945 .9983(+.0038) .9986(+.0041) .9964(+.0019) DenseNet .9817 .9920(+.0103) .9712(−.0105) .9803(−.0012)

(17) The suggested method for computer-implemented analysis of a classification model can be called a contextual prediction difference analysis (CPDA). This method is able to overcome the shortcomings presented above. When a feature x.sub.i is removed from the original instance x, the low prediction difference means the feature x.sub.i is not relevant according to the equation (3) of PDA, namely, r.sub.i=f(x)−f(x.sub.\i)≈0.

(18) According to the method of embodiments of the invention, instead of handling the single feature x.sub.i directly, the relevance of the contextual information is computed, i.e. the rest of the features or the single feature x.sub.i is omitted.
R.sub.\i=f(x)−Σ.sub.k=1.sup.Mp(v.sub.k|x.sub.i)p(y|x.sub.i,v.sub.l)=f(x)−f(x.sub.i),  (6)
where R.sub.\i are the reference values of all the features except x.sub.i, and v.sub.k are the sampled values conditional on x.sub.i. R.sub.\i can be distributed to individual features in many different ways. For simplification, the equal distribution is taken:

(19) $\begin{array}{cc}{r}_j=\frac{R_{\setminus i}}{.Math.R_{\setminus i}.Math.},j\ne i.& \left(7\right)\end{array}$

(20) An alternative formulation to identify the relevance of the individual attribute is r.sub.i=f(x.sub.i), which computes the effect of a single feature. However, this formulation cannot identify negative evidence since r.sub.i=f(x.sub.i)≥0. The order of identified relevance values is equivalent to the one when marginalizing all the rest of features.

(21) Using the demo instance x={1,1,0} presented above, in which an instance is classified as a class c with the probability p(c|x)=max(1,1,0)=1, the analysis with equation (7) of contextual PDA (CPDA) is as follows:

(22) $\begin{array}{cc}{r}_1=\frac{R_{\setminus 2}}{.Math.R_{\setminus 2}.Math.}+\frac{R_{\setminus 3}}{.Math.R_{\setminus 3}.Math.}=0/2+1/2=0.5r_2=\frac{R_{\setminus 1}}{.Math.R_{\setminus 1}.Math.}+\frac{R_{\setminus 3}}{.Math.R_{\setminus 3}.Math.}=0/2+1/2=0.5r_3=\frac{R_{\setminus 1}}{.Math.R_{\setminus 1}.Math.}+\frac{R_{\setminus 2}}{.Math.R_{\setminus 2}.Math.}=0/2+1/2=1.& \left(8\right)\end{array}$

(23) The features x.sub.1 and x.sub.2 make equal positive contributions to the decision. The last feature x.sub.3 contributes nothing to the decision in this demonstration instance. The analysis result illustrates that CPDA can overcome the saturation problem. The reason behind this is that the relevance of each feature depends on inferences of all the contextual features instead of the feature (i.e. the omitted feature) itself.

(24) In case that an input is high-dimensional, such as an input image, it is inefficient to consider the pixels as individual features. On the other hand, the individual pixels are not human-understandable visual features. Hence, it is proposed to take image patches as features.

(25) The neural network-based classifiers often require a fixed input size, and the selected image patch should be resized to the required size. The shape of the image patch selected is squared which makes the computation of f(x.sub.i) possible. Hence, the image classifiers are assumed to be invariant to translation and scaling operation, which is satisfied in existing convolutional neural networks.

(26) As not all pixels inside a patch are equally important, the resolution of the obtained saliency maps depends on the size of a single image patch. While too big patches lead to low-resolution saliency map, too small patches are not visually understandable as f(x.sub.i) is not meaningful. To avoid this dilemma, instead of splitting the image into separated patches, the patch is slid over the whole image with a fixed stride like in convolutional operations.

(27) In the following, text and image classification decisions using different methods compared to the suggested method are explained.

(28) Text classification with naive base classifiers

(29) A text dataset 20 newsgroup as described in Lang, K. Newsweeder: Learning to filter netnews. In Machine Learning Proceedings 1995, pp. 331-339. Elsevier 1995. is taken, which is a collection of approximately 20,000 newsgroup documents, partitioned evenly across 20 different news topics. Each document is an email message including contents, a header, a signature block, and possible quotation blocks.

(30) Most well-trained classifiers make decisions based on information in headers and footers. The sender and the receiver are affiliated with universities and institutes. The headers or the footers are informative enough to classify the document. The classifier makes decisions not based on words related to certain topics. To avoid that a classifier overfits to the irrelevant information, the header and the footer are removed from all documents in the dataset.

(31) Given a class variable y and a dependent feature vector {x.sub.1, x.sub.2, . . . , x.sub.n} and the assumption all the feature variables are independent, Bayes' theorem shows the relationship

(32) $\begin{array}{cc}p\left(y|x_1,x_2,\mathrm{.Math.},x_n\right)=\frac{p\left(y\right)p\left(x_1,x_2,\mathrm{.Math.},x_n|y\right)}{p\left(x_1,x_2,\mathrm{.Math.},x_n\right)}=\frac{p\left(y\right){.Math.}_{t=1}^{n}p\left(x_i|y\right)}{p\left(x_1,x_2,\mathrm{.Math.},x_n\right)}\propto p\left(y\right){.Math.}_{i=1}^{n}p\left(x_i|y\right).& \left(9\right)\end{array}$

(33) The individual instance is classified by ŷ=argmax.sub.yp(y)π.sub.i=1.sup.np(x.sub.i|y).

(34) One of the classic naive Bayes variants used in text classification is Multinomial Naive Bayes where the data are typically represented as word vector counts. tf-idf vectors are also known to work well in practice. tf-idf vectors of documents are taken as input features to estimate the parameters of the model. For each class, the model parameters are θ.sub.y={θ.sub.y1, θ.sub.y2, . . . , θ.sub.yn}. The parameter θ.sub.yi is estimated by a smoothed version of maximum likelihood

(35) ${\hat{\theta }}_{yi}=\frac{N_{\mathrm{yi}}+\alpha }{N_y+\alpha *n}$
where N.sub.yi is the number of times feature that appears in samples of class yin the training set, and N.sub.y is the total count of all features for the class. The smoothing factor α is empirically set as 0.01.

(36) For an explanation of individual document classifications, the parameters of MultinomialNB classifiers are estimated with the training data set of the 20 newsgroup and achieves 70.09% accuracy of the test dataset. The parameter θ.sub.yi specifies the sensitivity of classifier of class y to the feature x.sub.i. For each classification, given the output class, the most sensitive words that appear in the document are chosen which is called sensitivity analysis (SA). The other model-agnostic methods LIME, PDA and the suggested CPDA are also applied to explain the individual document classifications.

(37) The explanations of the classifications are shown in FIGS. 2a and 2b. Each column corresponds to the classification of a single document D1, . . . , D4. The first row R1 shows the part of the document text; the second row R2 shows the ground truth class GTC, the predicted class PC, the probability degree PD and the saturation degree SD (the extend of getting close to one). The explanations produced by the four methods are shown in the last row R3 respectively.

(38) In the method of SA, the words with high sensitivity are top words since they would appear many times in a document. The relevant words identified by SA cannot explain the classification of documents. They are highlighted in bold italic. The identified relevant words cannot convince the user to trust the classification decisions. For each document, the method LIME generates 5000 distorted versions by removing some words, predicts probabilities for these distorted texts using the naive Bayesian classifier and trains a logistic regression with SGD (Stochastic Gradient Descent). SGD is a basic optimization method to train a neural network. The weights of the logistic regression are used to identify the words that make positive contributions to the classifier. As shown in FIGS. 2a and 2b, the produced explanations are more convincing.

(39) In most classifications, especially the classifications with low saturation degree, e.g. document D1, both, PDA and CPDA, give similar good explanations, which successfully identify words related to the corresponding target class. In the classification with high saturation degree SD, PDA suffers from saturation of classification, where the biggest relevance value is close to zero, and the ones of most words are exactly zeros. CPDA produces better explanations without suffering saturation problems. For instance, in the classification of document D3, PDA identifies the word “in” as the most relevant word to the topic “sci.med”. On the contrary, the word “yeast” in document D3 is identified by CPDA as the most relevant to the topic. CPDA produces reliable and stable explanations for individual classifications.

(40) Image Classification with Deep Convolutional Neural Networks CNNs

(41) In the following, individual image classifications of deep convolutional neural networks are explained. Pretrained vision models from pytorch framework as classifiers (AlexNet by default f( )) are taken, which requires a fixed input size 224×224. The input image x of size H×W is resized to the fixed input size, processed and classified f(x). The squared image patch k×k is clipped from the processed image of 224×224 and resized to the fixed input size again. The single image patch x.sub.i is classified as f(x.sub.i). It is assumed that the image classifier is invariant to image translation and scaling. When resizing an image patch, instead of resizing the clipped patch itself, the corresponding patch of the original image is resized to avoid unexpecting scaling effect, e.g., too blurry. Hence, f(x.sub.i) can describe the effect that the patch x.sub.i has on the prediction.

(42) Is could be shown in empirically experiments that the method according to embodiments of the invention is better than LIME and PDA. In particular, the suggested method is more consistent and efficient.

(43) The efficiency is a non-ignorable factor for model-agnostic saliency methods. Since they have no access to the parameters of classifiers, the algorithms have to make many times inferences to obtain enough information for identifying the relevance of input features. Additionally, the consistency of produced explanations is another important indicator to evaluate saliency methods. The consistent explanations make more sense to understand the classifier and gain more trust from end users.

(44) For a single instance, LIME trains a local surrogate classifier to approximate the local classification boundary of the target classifier. Although the surrogate classifier takes the superpixels as individual features, LIME takes several minutes to produce an explanation for a classification. The explanations produced by LIME are inconsistent. The sources of inconsistency could be the modeling and the sampling process, the type of surrogate classifiers and the organization process of the surrogate classifiers.

(45) PDA considers patches of an image as individual features to produce explanations. For each individual patch, PDA first models the conditional distribution P(x.sub.i|{dot over (U)}(x.sub.i)) and samples the patches from the distribution. The modeling and sampling processes are computationally expensive. Given an input image of size n×n and a patch of size k×k, S(n−k+1).sup.2 times forward passes are required to evaluate the relevance of all pixels, where S is the number of samples from the distribution P(x.sub.i|{dot over (U)}(x.sub.i)). Tens of minutes are required to produce an explanation.

(46) Compared to LIME, CPDA requires neither the construction of noisy variant instances nor an extra classifier. Different from PDA, CPDA does not have to model the conditional distribution of image patches. Image patches are classified directly to identify the relevance of contextual pixels. With the same setting as in PDA, only

(47) ${\left(\frac{\left(n-k+1\right)}{s}\right)}^2$
times inferences are required to produce an explanation using CPDA, where k is the size of image patches and s is the stride. CPDA is S*s.sup.2 times faster than PDA. It only takes seconds to minutes to produce an explanation when s=5. Table 2 lists the average time to produce a single explanation.

(48) TABLE-US-00002 TABLE 2 Average time to produce a single explanation Model LIME PDA CPDA AlexNet .sub.CPU 5.15 min 380.82 min 1.81 sec AlexNet 4.03 min 20.71 min 10.82 sec VGG16 5.17 min 86.62 min 42.68 sec Inception_V3 6.06 min 184.67 min 93.34 sec ResNet 4.46 min 97.21 min 49.10 sec DenseNet 3.36 min 61.25 min 30.39 sec

(49) The first row shows the time of running the method (LIME, PDA, CPDA) on AlexNet on a CPU while the other rows show the time on a single GPU (Tesla K80).

(50) VGG16 outlined in table 2 has a similar architecture as AlexNet, but with more deeper layers. The deeper VGG16 identifies the most discriminative features to classify the image. Instead of wheels of a car shown in an original image to be assessed, for example, a sport-car image is classified based on the car roof, which can be used to distinguish it from cabs and busses. The most discriminative feature of a hot-air balloon image is a basket of the balloon for VGG16. Indian elephants differ from other species of elephants in their ears. Indian elephants have smaller ones than others. In explanations on VGG16, the corresponding discriminative visual features are highlighted. GoogleNet (also known as Inception_V3) convolves images and filters with multiple kernel size, where the features of different sizes can be identified as the class-discriminative features, e.g. a part of a balloon in an image. ResNet and DenseNet are equipped with skip connections where they learn features from a global view. Together with contexture information, the discriminative features are used to classify images. For instance, a sports car and the racetrack are extracted as relevant features for classification. Both the balloon and the basket are used to identify the image as a hot-air balloon.

(51) FIG. 1 illustrates the steps of the method for computer-implemented analysis of a classification model as described above. In step S1, an effect of each feature on the prediction of the instance is identified by determining, for each feature, a relevance information representing a contextual information for all features of the instance omitting the considered feature. In step S2, the relevance value for each feature is determined by combining the relevance information for the features of the instance. In step S3, the plurality of relevance values is evaluated for the features of the instance to identify the effect of each feature on the prediction of the instance. Steps S1 to S3 are carried out by a processing unit PU which is adapted to perform the steps as described above.

(52) Although the present invention has been disclosed in the form of preferred embodiments and variations thereon, it will be understood that numerous additional modifications and variations could be made thereto without departing from the scope of the invention.

(53) For the sake of clarity, it is to be understood that the use of “a” or “an” throughout this application does not exclude a plurality, and “comprising” does not exclude other steps or elements.