Preface

I adapted this blog on flow-based models from a technical presentation I gave after reimplementing the ‘Glow: Generative Flow with Invertible 1x1 Convolutions’ paper from OpenAI as a personal project. The blog consists of two parts:

1. Introduce a type of generative model that uses change of variables. These can also be described as flow-based models, reversible generative models, or as performing nonlinear independent component estimation.
2. Explain the ‘coupling layer’ introduced in “NICE: Non-linear independent component estimation,” which is fundamental to recent advances in these models.

My goal is to help a reader familiar with machine learning brush up on the background necessary to understand the Glow paper, which has shown amazing results. To get an idea of what Glow can do, check out this blog post and play around with the tool:

Glow: Better Reversible Generative Models

This model has shown remarkable success on high-resolution images, and the following two papers introduced many of the concepts it uses:

• NICE: Non-linear Independent Components Estimation
• Density estimation using Real NVP

Here’s my quick and dirty reimplementation of Glow using tensorflow:

nolan-dev/glow_reimplementation

Part 1: Introduction

For context, here are some common goals of generative models:

• Model the data distribution so that we can take samples and evaluate densities
• Encode data as latent variables and decode the latent variables to exactly reproduce the original data
• Use latent variables that encode meaningful information useful for downstream tasks
• Produce subjectively high-quality data

Most generative models do not support all of these goals. However, flow-based models like Glow do, with some caveats. Unlike several other popular approaches, they attempt to make finding the density function tractable.

Making the density tractable

The exact definition is fuzzy, but usually, generative models attempt to model the distribution they are trained on in a way that allows sampling from it (generation). For GANs, this just means learning to sample from that distribution. Variational autoencoders allow sampling but also attempt to approximate the probability density function by maximizing the evidence lower bound. Autoregressive models and change of variables models, on the other hand, attempt to make finding the density function (or rather, the best density function in their hypothesis space) tractable by maximizing the likelihood of the training samples.

The following image from Ian Goodfellow’s NIPS 2016 tutorial illustrates how conventional generative models relate to each other in the context of maximizing the likelihood of a density function:

Here’re some examples of how we might calculate the density function:

Say we have a multivariate distribution over a space H, with samples from that distribution h consisting of independent components h_d. We can calculate the density at h by multiplying the density of each component together:

For example, H might consist of two specific attributes of the face which we assume are independent: h_1 indicates if the face is smiling, h_2 indicates if the face is wearing glasses. To get the probability of a specific face that is wearing glasses and not smiling, we can multiply p(h_1=not smiling)*p(h_2=wearing glasses). The independence assumption reduces the problem to finding the density functions of the components.

Unfortunately, the components we have access to often aren’t independent, so (to avoid naivety) we have to incorporate the dependencies using the chain rule of probability:

Continuing with the previous example, if our dataset consists of before-and-after images of people trying on glasses for the first time, it may be that a person is more likely to be smiling if they are experiencing better vision for the first time (wearing glasses). Therefore, to get the probability of a specific face that is wearing glasses and not smiling, we multiply p(h_1=not smiling|h_2=wearing glasses)*p(h_2=wearning glasses). This calculation incorporates the dependency between the two components.

In the case of images, the probability distribution is over all images X, and we want to calculate the density at a specific image x. Calculating the density at an image requires accounting for the dependencies of the image’s components: the pixels. For example, pixel 2 in an image is usually very dependent on pixel 1. Except for borders, pixels that are close together tend to be part of the same object and are therefore highly correlated. Borders make up a small portion of a natural image, as they are nearly 1-dimensional features in a 2-dimensional space. On the other hand, a latent variable like ‘wearing glasses’ is often independent of a latent variable like ‘smiling.’

Nonlinear independent component estimation, when applied to images, aims to transform the dependent distribution over pixels x to an independent distribution over latent variables h by applying a function f(x). The Glow paper, its predecessors, and this blog are mostly about finding the right function.

f(x) must be invertible so we can go back to X from H (otherwise, we can’t generate samples). The invertibility requirement forbids lossy dimensionality reduction: the latent space must have as many components as the image space (usually height*width*3 color channels). Figure 4 roughly shows the concept of going from a complex distribution to a simpler one and vice versa.

Once we have a function f(x) to map to from samples of X to an independent space H with a known probability density function, we could try to calculate the density of a specific image x using the following naive approach:

If you’re as rusty with change of variables as I was when I first read the Glow paper, step 4 may seem intuitive. However, it’s not entirely correct due to how continuous distributions work. I’ll go over why in the next part. If you are familiar with change of variables for integrals, it will be mostly review.

Change of variables

As a simple example, say X is a univariate distribution over beard size instead of pixels. In the illustration below (Figure 5), a light beard is most probable, with larger beards or no beards having lower probabilities. Following step 2, we can apply a function to convert X to H: h = f(x). Say f(x)=x/10. It doesn’t make sense to talk about independent variables when there is only one; this example is meant to illustrate a basic change of variable that can then be extended to include multivariate distributions. Figure 5 and 6 show the before and after of this transformation, with a brown curve indicating the probability density function displayed above the images:

Apply h = x/10.

The image that was previously at 10 is now at 1, and the image that was at -10 is now at -1. The image that was at 0 is still at 0, but it is clear that the probability density is higher at -1, 0, and 1 in the new image than it was at -10, 0, and 10 in the old image, just as the density of images has increased.

The area under the curve of a probability density function must always be 1, so lowering the width must increase the height and vice versa. This concept can be expressed more mathematically using the cumulative density functions F, which are calculated as the integral of the probability density function (pdf) from negative infinity to the point under consideration. The fundamental theorem of calculus indicates that the pdf is, therefore, the derivative of the cumulative density function. After we change from x to h = f(x), we need to use the chain rule to calculate the new pdf. The following equation gives the actual pdf for x in terms of the pdf for h:

Therefore the process should be the:

Therefore the density at x can be calculated as

This StackExchange post includes answers with a good explanation for why we use the absolute value of the determinant.

For me, knowing that each step in an equation is mathematically valid does not always allow me to understand that equation intuitively. The following MSPaint diagram roughly demonstrates how the height of the new pdf needs to change to match the change in the ‘width’ of the space. My favorite youtube channel, 3Blue1Brown, has a video that superbly animates derivatives as stretching or squishing of space https://www.youtube.com/watch?v=CfW845LNObM&t=3m7s, which is an essential intuition for understanding change of variables.

Finding the function

I haven’t mentioned yet why we need the exact density function to generate samples (clearly, we need the density function if we want to calculate densities). GANs, for example, only use it implicitly. Up to this point, I’ve assumed the function that maps pixels to independent components is known, but this won’t be the case for a dataset with non-trivial images. Now, machine learning comes in: we can have a computer learn the function instead of writing it ourselves. With the density function, learning the parameters of f(x) can be done via maximum likelihood estimation. Specifically, we can maximize the log-likelihood of f(x)’s parameters θ to produce a distribution with independent components p_H for input x

If we choose the independent distribution to be a Gaussian with mean 0 and variance σ², the equation becomes

Without the log determinant term, this is equivalent to minimizing the mean squared error between the output of the function and 0. In this case, the best θ is the one that causes f to map every value to the mode of the distribution (0), as illustrated in Figure 8. This mapping produces a Dirac delta distribution rather than a Gaussian:

Here’s another way to understand how the log determinant term is required to find the right function:

If we want to map to a 0 centered Gaussian, the log-likelihood loss we minimize is f(x)²/2σ² (log of the Gaussian density equation with 0 mean). Without the log determinant, this means a function that maps all training data to 0 would have 0 loss (bad: Gaussians should have some variance). The function cannot do this if we maximize its slope near the training data: nonzero slope means not all points are mapped to the same location. Given this, it seems intuitive that the log determinant term should be related to variance in some way. Often when we maximize the MLE of a Gaussian, we can disregard constant factors such as the Gaussian’s variance; however, in this case, we cannot because the log determinant term is not multiplied by the same constant. Because the log-likelihood of a Gaussian is the mean squared error divided by 2σ², variance is effectively a weight term, with higher variance increasing the influence of the log determinant term by lowering the influence of the log density term. For the log determinant term to disappear completely, the variance would have to be 0, giving infinite weight to the log density term, which would produce the Dirac delta type pdf shown in Figure 8.

The next section on the “coupling layer” explains how we might create and invertible function with a tractable Jacobian determinant that is powerful enough to map natural images to their independent components.

Part 2: Coupling Layer

Hopefully, the previous section made it clear that we can create a generative model by using an invertible function with tractable Jacobian determinant to map the input data to an independent representation. Given the complexity of some types of input data (images), it would be challenging to create that function manually. If the function is differentiable and parameterized by a sufficient number of variables, we may be able to use an optimization process to learn it. Neural networks have shown success at learning complicated differentiable functions, but they are generally not invertible with a tractable Jacobian determinant. The coupling layer fulfills all of these requirements: the layer is invertible, has a tractable Jacobian determinant, is differentiable, and incorporates a neural network powerful enough to handle complex input. It achieves this with a ‘triangular’ function structure, where we split the inputs and outputs into two parts. The first layer in the network needs to perform the initial split into x_1 and x_2, which is usually done across channels or with a spatial checkerboard pattern, but to simplify the illustration, Figure 9 shows an example of splitting along the height

The inverse of this specific split is to combine the top and bottom halves into a single image. At the start of a coupling layer, “Key” data is passed through a neural network and combined with “Message” data. The “Key” is also passed along unmodified, which means we do not need to invert the neural network, as the next layer has a version of the network’s input. Coupling layers can be stacked to build more powerful functions that are still invertible with tractable Jacobian determinants.

Figure 10 shows a diagram of a coupling layer, the input is x_1 and x_2, and the output is the ‘new key data’ and ‘new message data.’ The neural network, m, has influenced half that data. By stacking these layers, we can get a ‘deep’ representation.

g is an invertible function combining x_2 and the output of m(x_1) (m can be a neural net). The diagram is equivalent to the following equations (without the mix function) which also demonstrate the invertibility of the layer

The triangular nature of the Jacobian for these equations means only the partial derivative of y_2 with respect to x_2 is needed, which does not require differentiating the neural network m (keeping the calculation simple)

Therefore, by picking the right g and mix functions, we can get an invertible function with a tractable Jacobian determinant even if m is highly complex.

g is often defined as the following simple function, to produce an ‘affine coupling layer’:

The circle with a dot in the middle used to combine x_2 and m_2(x_1) is the Hadamard product, which is an element-wise multiplication. Backpropagation also uses the Hardmard product.

y_1 and y_2 are ‘mixed’ with an invertible transformation. Without mixing, the “Message” data will never be passed through a neural net, and the network won’t learn a deep representation. The diagram below shows two options for this transformation

The first example is what the original paper did: the ‘key’ and ‘message’ data swap position. The inverse is trivial, swap them back.

The second example is closer to how the ‘Glow’ paper implements the mixing operation. The paper points out that the ‘swap’ operation is a specific instance of changing the permutation of channels. It uses a more general permutation implemented as a square matrix transform with learnable weights, initialized as a rotation matrix. This transform is where “Invertible 1x1 Convolutions” from the title of the paper comes in: one way to do a channel-wise ‘permutation’ is 1x1 convolutions. 1x1 convolutions are convolutions with filter height and width of 1 and have been used in architectures such as the inception network to change the number of channels. In Glow, the number of channels must stay the same for the architecture to be invertible (unless we also alter the spatial dimensions to keep the total number of components constant).

Conclusion

I think an important takeaway from this type of model is that we shouldn’t assume the restrictions imposed by a particular approach are insurmountable. I can see myself assuming that the requirement for an invertible function with a tractable Jacobian determinant excludes the use of neural networks. This assumption turns out to be incorrect, and the solution is an effective approach to model the independent components of high dimensional data. The architecture is still restricted, however, which means models like GANs that have more flexibility have been able to produce high-quality results with much less training time and memory usage. I’m also interested in gaining a better understanding of how generative models behave and how they might learn useful concepts in an unsupervised way. I discussed approaches to this in previous blogs https://towardsdatascience.com/animating-ganime-with-stylegan-part-1-4cf764578e and https://towardsdatascience.com/animating-ganime-with-stylegan-the-tool-c5a2c31379d in the context of GANs.

Introduction to Reversible Generative Models was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.

- Ian McDonald.

Suppose you are working on a high-impact yet challenging problem of malware classification. You have a large dataset at your disposal and are able to train a machine learning classifier with an accuracy of 98%. While suppressing your excitement, you convince the team to deploy the model, as who would resist a model with such an amazing performance? Quite disappointingly, the model fails to detect threats in the real world!? This unfortunate scenario is all-too-common in classifier development. While there are numerous culprits, one that is common in the security space is the problem of class imbalance. In class imbalance, one trains on a dataset which contains a large number of instances of one type, for example, malicious files, and only a few instances of other types, for example, clean files.

Terminology

Let’s define class imbalance and some terminologies associated with it. We’ll use a simple example of malware classification to make things clear.

Features
Features are the measurable property of the data. They are generally represented as a matrix of dimension number of features x number of dimensions. In the context of malware classification, the features can be opcodes, memory and file system activities, entropy or learned features through deep learning.

Labels
Labels are class associations which are provided with each feature vector. During training, labels are provided whereas, at test time, labels are predicted. Labels in our example of malware classification are clean and malicious.

Classifier
Classifiers map the features to labels. There are many types of classifier, but in this article, we’ll think of well-known algorithms like Random Forest, Support Vector Machines and Convolutional Neural Networks. Any of these classifiers can be used to train the malware classification model.

Class Imbalance
As the name implies, class imbalance is a classification challenge in which the proportion of data from each class is not equal. The degree of imbalance can be minor, for example 4:1, or extreme, like 1000000:1.

Class imbalance is a challenging problem in machine learning, as it may bias the classifier to emphasize the majority class, which can skew the classifier decision boundary and cause overfitting.

Practical Examples of Class Imbalance

Here are a few real-world use cases where class imbalance occurs. Note that a successful classifier for these applications must ultimately overcome class imbalance in order to be effective.

• Spam classification
• Tumor screening in medical data
• Human and car detection for autonomous driving
• Malware classification
• Face recognition
• Fraud detection

Techniques for Overcoming or Addressing Class Imbalance

Now, let’s talk about a few ways to handle class imbalance.

Feature Level Approaches
These approaches change the data distribution by either undersampling the majority classes or oversampling the minority classes so as to balance the data distribution. In undersampling, one can remove instances from the majority class, whereas in oversampling, duplicates of the minority class instances are added to the learning set. Generally, it is advisable to resort to undersampling when you have a large number of training samples and use oversampling when the number of training examples is small.

Both of these two techniques, however, have drawbacks. Undersampling can lead to the loss of useful and potentially discriminative information about the majority class, whereas oversampling cause overfitting. This overfitting while oversampling can be addressed using approaches such as Synthetic Minority Over-sampling Technique (SMOTE) and Adaptive Synthetic Sampling (ADASYN).

In SMOTE, n-neighboring examples around each minority example are sampled and then on a line connecting these neighboring examples, random points are generated which serve as the augmented examples. ADASYN, on the other hand, utilizes a weighted distribution of minority class examples based on the local density, thereby inherently accounting for skewed label distribution.

“More data beats clever algorithms, but better data beats more data.”

- Peter Norvig

Data Augmentation
Another option to deal with class imbalance is to collect more data. However, in many cases, this option remains exorbitantly expensive in terms of time, effort and resources. In these cases, data augmentation is a common approach used to add extra samples from the minority class. In the context of images, this is generally achieved by adding distortion to the data by performing translation, rotation, varying the scale as well as by adding different types of noise such as Gaussian, Poisson, and Salt-and-Pepper noise. These transformations to the images can lead to more robust models.

Data augmentation can also provide protection against overfitting along with the dropout and regularization methods. Generally, when label preserving transformations are available (such as in images), it is preferable to use data augmentation over feature level augmentation approaches (such as SMOTE and ADASYN). On the condition of label preservation, the above-mentioned transformation can also be generalized to non-imaging data. Generative Adversarial Networks (GANs) have also been explored for generating augmented training data for a classifier [Bowles et al. 2018].

Metric Based Approaches
Metric-based approaches change the evaluation criteria used to judge the performance of the classifier. These include the use of accuracy, precision, sensitivity (recall), specificity, ROC, confusion matrices and other statistics as metrics. For example, in a 95%-5% class imbalance scenario, accuracy cannot be a considered as a reliable measure to evaluate a classifier, as it may assign majority class label of all examples and hence have an accuracy of 95%. In this way, we would be vehemently ignoring the misclassification of minority class, while attributing more significance to the classification of majority class.

Algorithm Level Approaches
Algorithm level approaches actually modify the learning algorithm to improve the performance of the classifier on the minority class. These approaches impose an additional cost for any classification errors pertaining to the minority class and bias the classifier to focus more on the minority class mistakes. Conventionally, cost-sensitive SVM is used as an algorithm level approach to handle class imbalance [Masnadi-Shirazi et al. 2010]:

where C1 and C2 are the costs for positive and negative slack variables respectively. Recently, with the popularity of deep learning and convolutional neural networks for classification, there has been increased interest in implicit handling of class imbalance within the network. One way this is implemented is with elastic deformation. Elastic deformations are applied to generate extra samples for training an image segmentation architecture as in U-NET [Ronneberger et al. 2015].

In the computer vision literature, focal loss had been proposed to handle extreme class imbalance between foreground and background for object detection [Lin et al. 2018]. The focal loss goes one step further than handling class imbalance by giving more importance to the hard negatives. It modifies the cross-entropy loss by adding a scalar factor which down-weights the contribution of well-classified examples and focuses more on a sparse set of hard examples. In this manner, it circumvents the detector from being overwhelmed by a large number of easy examples.

Hard-negative mining can be another way of efficiently exploiting the maximum discriminative information from an existing small dataset. These approaches include boot-strapping the classifier by adding false-positives to the negative set in the next training cycle.

Classification with Missing Labels

In addition to class imbalance, the absence of labels is a significant practical problem in machine learning. When only a small number of labeled examples are available, but there are an overall large number of unlabeled examples, the classification problem can be tackled using semi-supervised learning methods. Semi-supervised learning is quite useful for web-page classification, image classification, structural and functional classification of protein, and speech recognition problems.

There are a three popular approaches to address semi-supervised learning problems: (1) self-training, (2) co-training and (3) graph-based models.

Self-training

In self-training, first a classifier is trained on the labeled data and then the learned model is used to make predictions on the unlabeled examples. The high-confidence predictions from the unlabeled samples along with their predicted labels are appended to the training data and the model is trained on the new training data. The process is repeated either for a fixed number of iterations or until there are no high-confidence examples left in the unlabeled set. A main drawback of self-training is that high-confidence, but incorrect predictions can be added to the training set and the mistakes can be amplified in the subsequent trainings of the model.

Co-training

Co-training requires two feature representations associated with the dataset which serve as two different views of the data. These representations are dissimilar and conditionally independent, but they can provide complementary information about the data. An example of this situation is phishing website classification where we can have images and text as two different views of the data.

In co-training, two models are trained separately, one for each representation of the data. During testing, unlabeled samples with highly-confident predictions for exactly one of the models are appended to the training data of the other model. In contrast to self-training, co-training is less susceptible to mistakes from a single model, however, models that use both sets of features are likely to perform better. A generalized form of co-training is multi-view training, where multiple classifiers are trained on different representations of the labeled training data and a majority voting is used to append the unlabeled example to the labeled training data.

Graph-Based Approaches

In graph-based approaches, labeled and unlabeled examples are represented as different nodes in a graph where the edges in this graph denote the similarity, or affinity, between adjacent nodes. The assumption in this approach is that nodes with strong edges are likely to share the same label. The affinity function on the edges is computed based on the features of the nodes. The unlabeled nodes in the graph can be labeled using random-walk applied over the graph. In a random-walk approach, an unlabeled node initiates a graph traversal based on the strength of the edges. The walk ends when a labeled node is reached and a probability that the random walker started at a particular unlabeled node given that it ended at a specific labeled node is computed. In other words, two points are similar if they have indistinguishable starting points. The graph-based semi-supervised learning approach is common for image segmentation problems where each pixel of an image is represented by a node and a few foreground and background pixels are either manually labeled by the user or assigned labels via image priors.

Concluding Remarks

In conclusion, the ways to address these two challenges in machine learning significantly depend on the data as well as the complexity of the problem. In situations where label preserving transformations are available, data dependent approaches have an upper hand. Recently with deep learning, cost-sensitive training approaches are gaining popularity. Also recently, there has been some interesting work exploring the relationship between transfer learning and semi-supervised learning [Zhou et al. 2018]. Although beyond the scope of this blog, it should be noted that class imbalance is also a practical issue for regression. In summary, class imbalance and missing labels are open research arenas with great potentials of affecting how we address a wide-range of real-world machine learning problems.

Acknowledgement: I’d like to thank Andrew Gardner for helpful comments and suggestions .

AI/ML Security Pro Tips: Class Imbalance and Missing Labels was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.

It always depends. It depends on the specific problem, the data available and the time you are willing to spend.

For the casual readers not steeped in machine learning: you may wonder, what is an LSTM? It is not a cable news alternative. LSTM stands for Long Short-Term Memory, a type of computer neural network usually used to predict sequences of data. CNN on the other hand stands for Convolutional Neural Network, another type of computer neural network that is often used for classifying images. So why the question about abandoning one (LSTM) for the other (CNN)? That is because recently there’s literature that points out that CNN can achieve what LSTM has been used for and great at, namely predicting sequences, but in a much faster, more computationally efficient manner.

· http://arxiv.org/abs/1509.01626

· https://arxiv.org/abs/1803.01271

· https://towardsdatascience.com/the-fall-of-rnn-lstm-2d1594c74ce0

If the articles and blogs are true, then why are people still bothering with LSTM (or other flavors of recurrent neural networks)? As any good scientist interested in this subject, I tried to reproduce results from these papers with data that I have access to. If the claims of CNN superiority are true, then I expect to find the same results with my data, and CNNs should come out on top of LSTMs. And if I find that CNN does not come out on top, then maybe the claims that CNNs are better need refinement. Maybe CNN is often better, or only better under certain conditions; wouldn’t be the doom and gloom for all LSTM as others may have you believe from catchy titles.

Background on CNN/LSTM

CNN

So what makes a CNN different than a LSTM? To see what makes a CNN, I will show a picture representation of what the neural network sees (captured as features) in different layers, hopefully giving you a high-level understanding of what goes on under the hood of this complex machinery.

In the lowest layer, the neurons in the network usually identify important small scale features, such as boundaries, corners and intensity differences. Then in higher layers, the network combines the lower level features to form more complex features such as simple shapes, forms and partial objects. And on the final layer, the network combines the lower features to form fully human recognizable objects. In this particular example, the layer 1 edge features are used to construct the layer 2 eyes and ears, which then get combined to resemble human faces.

One may ask, how does a CNN pick out the features in the first place? Great question! It does this by doing what is called a convolution (hence the name convolutional neural network). It is basically simple matrix multiplication, starting with randomly generated matrices (called “kernels” in machine learning speak).

The kernels are multiplied with different sections of the image and when it encounters a feature that matches well with the kernel, a signal results, indicating that image patch contains an important feature. Suppose the randomly generated kernel didn’t find a good feature (doesn’t get many signals) then it gets updated through the backpropagation algorithm so that it can improve (through a series of chain rule matrix multiplications). The kernel update helps the kernels transition from random matrices, to matrices which discriminate important features. For example, in the first layer of the network, the kernels adapt to find image edges. This self-improving backpropagation algorithm is the way the machine learning algorithm “learns” from the data it is being fed. The algorithm becomes better and better at capturing important features through many iterations or “epochs” of the same data.

Readers interested in learning hands-on how a CNN captures features can visit TensorFlow Playground. The site has a nice GUI that allows one to easily build a CNN and get real-time results from the machine learning algorithm.

So that is CNN at a high level. What about LSTM?

LSTM

An LSTM is designed to work differently than a CNN because an LSTM is usually used to process and make predictions given sequences of data (in contrast, a CNN is designed to exploit “spatial correlation” in data and works well on images and speech).

At a simple level, an LSTM is just a neuron unit that feeds information back on to itself for the next time step in a sequence. It is a flavor of a more general class of neural network called recurrent neural network (RNN).

RNNs were designed to retain long range information, so that in a long sequence, the information is remembered and not lost. However, the feedback loop in RNNs created two problems. The first problem, the vanishing gradient problem, occurs when the updating gradient in backpropagation is small. By consecutive matrix multiplications of the chain rule through the depth of the network the value shrinks quickly, so when the update is tiny or zero, the network does not learn anything. The second problem is the opposite, the exploding gradient problem, occurs when the gradient is big, and gets much bigger quickly by the same consecutive matrix multiplication mechanism. This causes the model to crash or hang because it cannot handle the large values. Here’s a nice post that describes these problems in more detail:

The curious case of the vanishing & exploding gradient

The problem is exacerbated by network depth. When you “unroll an RNN” it looks something like this:

The deeper the network, the more “t” units in this diagram, and the worse the problem of vanishing/exploding gradients because the more matrix multiplications it has to go through for gradient updates to reach from t back to 0.

So far I’ve been talking about RNNs in general. The LSTM is a specific implementation of an RNN that introduces a more complex neuron which includes a forget gate. You can learn more about the details of LSTMs in the above links under the LSTM diagrams. Basically, if the signal passing through the neuron at a particular instant is deemed relevant by being similar to one of the signals it has seen before, then the forget gate in the neuron will not forget that sequence. A sequence of signal is maintained by being let through the forget gate with a certain size (fixed between 0 to 1). This way, the update to the gradient of the signal does not explode. And if a sequence of signal is no longer relevant the forget gate will help rid of it by letting 0 signal through.

Here are some additional details about cnn/rnn if the reader is interested:

• When to Use MLP, CNN, and RNN Neural Networks - MachineLearningMastery.com
• What's the Difference Between a CNN and an RNN?

Literature/Evidence

The works cited earlier, Zhang et al. 2016 tried to use CNN for classifying character sequences. Since text sequences are 1D signals in the time dimension, they want to transform text into 2D to exploit the advantages of using CNN to process 2D spatially correlated data. The way they changed 1D text into 2D is via a mechanism called text embedding. This is to represent each character of the text as a vector. So, instead of doing convolution in 2D on an image, they do the convolution in 1D in the time dimension but with a 2D kernel. The second dimension is the character embedding dimension, because each character of a word is now represented as a vector. So the sequence of character text labeled “Some Text” in the following image can now be represented as a matrix with the time axis going to the right.

If that is too much matrix notation for your liking, you just have to know that this method is a way for the authors to use CNN on text data, which according to them, they are the first to attempt this back in 2016. The results they showed were competitive with state-of-the-art LSTM back then.

Fast forward roughly another two years, the authors Bai et al. 2018 showed their flavor of CNN can remember much longer sequences and again be competitive and even better than LSTM (and other flavors of RNN) for a wide range of tasks. They propose to use causality to restrict the signal a neuron sees, and to apply dilation to the convolution to make the CNN have a much wider receptive field (can see further into the past).

My Work

Reading all the above success stories got me excited that maybe I can apply these tricks of CNN to beat LSTM. One of the reasons why people would prefer to use CNN over LSTM is the amount of training time. The current generation of popular deep learning hardware are basically Nvidia graphics cards, and they are optimized to process 2D data with extreme parallelism and speed, which CNNs utilize. LSTMs on the other hand, process things more sequentially, so the deep learning hardware does not increase its speed by much, especially during the training phase of the network.

I had access to a dataset of regular clean URLs that regular people access daily for information and entertainment and some malicious URLs that bad actors on the internet use as a communication portal to a command center. These malicious URLs are usually randomly generated strings, and I would like to detect which URLs are of the randomly generated type. The LSTM is known to be competitive with the state of the art on this task, so it gave me a baseline for comparison. I worked to implement the techniques for the CNN mentioned in the Zhang et al. and Bai et al. papers to see if I could implement a CNN that beat the LSTM baseline in terms of efficacy. Long story short, no matter what I tried, I was not able to get the character CNN to beat the results of LSTM. I tried a learned embedding, fixed one-hot embedding, causal receptive field, and dilated convolutions. Although some experiments were promising, none were able to surpass the simple LSTM.

While CNNs couldn’t beat the LSTM in efficacy, there was a drastic difference in training time between the two architectures. This could be due to the aforementioned hardware optimization from Nvidia and the sequential nature of LSTM. The character CNNs I played with were able to achieve an accuracy comparable to LSTM in a fraction of the time. The CNN accuracy rapidly increased, then plateaued while the LSTM slowly continued to improve slightly for longer training iterations.

Conclusion/Possible Alternatives

Thinking back, when I first started this problem, I was full of hope, but when I reviewed the results of my experiments, my hopes were dashed. No matter what I tried, I could not find a CNN that outperformed the LSTM. Am I disappointed? Somewhat. Will this stop me from trying character CNNs on other sequence problems? Absolutely not! I am still hopeful that I will be able to use it for other types of sequence problems, especially if I care about the amount of time I spend training the neural network.

One thing that dawned on me after I completed this exercise is that maybe the dataset affected the results. Because of the randomness of the characters in the URL, I didn’t see any improvements when I limited the receptive field to be causal, which makes sense because they are supposed to be random and independent of the past and future. Also, many of the URLS are pretty short. So in retrospect, maybe it did not make that much sense in this case, to expect a CNN to capture more long range information than the LSTM, because there were not many that had that long of a length.

Given my experiments and the dataset I used, the main conclusion I arrived at is this: character CNNs can be comparable to LSTMs, but it does not mean it will always beat LSTM. Others may say I have not optimized my CNN, and that is true, but I also did not optimize my LSTM, both were just vanilla with small tweaks to architecture and not much hyperparameter tuning. I am still hopeful that one of these days I will find a dataset where a character CNN will beat LSTM. And of course, doing some literature search will turn up a sea of results of possible alternatives that may be even better. People are combining CNNs and LSTMs, using attentional mechanisms, etc., so there are always new avenues to explore. There is a clear trend in the literature of moving away from LSTMs, but they have not disappeared and many these experiments provide hints at why. It seems like the CNN vs. LSTM game is not over yet!

Should We Abandon LSTM for CNN? was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.

Malicious software can inflict huge damage to enterprises and users and it continues to pose significant challenge for cybersecurity. Malware changes and evolves with time making it difficult to detect using traditional signature-based techniques. Malware authors have developed techniques such as malware packers to counter traditional signature-based approaches. In response, machine learning techniques have become popular for malware detection. Traditional machine learning approaches are based on heuristic feature engineering, which is expensive and unscalable. In more recent years, advanced machine learning techniques based on artificial intelligence (AI), specifically deep learning, are being actively investigated for this critical cybersecurity application. The hope for these techniques is that they will lead to more robust solutions with higher accuracy.

In this post, we provide an overview of deep learning based malware classification and how it can be employed for static analysis of malware.

Machine Learning

In Machine Learning, classification is the problem of assigning an input sample into one of the target categories. For malware detection, the two categories are benign and malicious files. Training data consists of data samples with ground truth labels. Some well-known examples of machine learning models are support vector machines, logistic regression, decisions trees and neural networks. In classical machine learning, suitable features, which are signals or characteristics of data capable of distinguishing between different categories, are extracted using a process called feature engineering. For a data sample, the extracted features are input into the machine learning model and the output is the classification. Using a training algorithm, parameters of a machine learning model are optimized under a suitably chosen cost function over the training set.

A non-trivial effort is spent in feature engineering which requires domain expertise because one has to know what characteristics make objects belong to different categories and then implement and fine tune all such features. Furthermore, such feature-based solutions for malware detection suffer from a drift problem due to the constant evolution of malware thereby making the efficacy decay over time.

Deep Learning

Deep learning is the application of deep neural networks to machine learning. A neural network consists of layers of neurons, starting with an input layer, followed by a few hidden layers, and ending with an output layer. A neuron receives inputs from previous layer, performs simple mathematical operations and outputs a value. Output of a layer becomes input to the next layer in a cascaded manner. A deep neural network consists of many hidden layers, which can be even in hundreds, and is therefore deep. A large variation of deep neural networks exists in practice, customized for different applications. A well-known example is convolutional neural network which is based on operation of convolution, in which a local receptive field from previous layer is processed in a sliding window manner. Convolutional neural networks are popular in computer vision applications.

Deep learning based solutions can work on raw data without any need of manual feature engineering. Different layers of neural networks automatically learn features at different levels, from low level local features to high level global features. The classifier’s performance typically keeps on gradually increasing as we increase the size of training data. In contrast, it has been empirically observed that performance of a classical machine learning model gradually plateaus out with increasing size of training data. One potential advantage in the case of deep learning is that increasing training data makes neural network learn more robust features. Learning of good robust features is an active area of research in AI. For malware detection, the hope for these techniques is that they will be less prone to the time drift problem. And if the performance does plateau out at some point, we can increase the capacity of the neural network by making it larger by increasing the number of neurons or layers or both and repeat the continuously improving cycle. That is precisely the reason why neural networks have shown steadily increasing gains in computer vision, speech recognition, natural language understanding and game playing.

The Convolutional Neural Network (CNN)

Before we review how deep learning is employed for malware classification, let us revisit how convolutional neural networks are used for image classification. An image is input to the network in its raw pixel format. The image goes through a sequence of convolutional layers which can be viewed as automatically computing image features at different levels of abstraction. The spatial dimension of feature maps decreases due to max pooling layers. Neurons in higher layers correspond to larger receptive fields of pixels in the input image over which features are being computed. These convolutional layers are followed by fully connected layers (dense layers), or in more modern architectures, by global average pooling layer. Right in the end, we have classification output layer which outputs probabilities of the image being in different categories. For speech recognition, we can convert speech signal into a 2-D image called spectrogram in which time is one axis and other is frequency, and we can apply similar techniques.

Embedding

For images or for speech, it is natural to use raw data as the input. This is because an image pixel which is similar in value to another is also visually similar to it. That is why image pixels exhibit correlation in local neighborhoods. In natural language understanding, the situation is radically different. The input is a sequence of words rather than numbers. We will like to convert these words to numerical vectors based on their neighborhood context with adjacent words. Consider them as multi-dimensional thought pixels of the image of a document. In color images which have red, green and blue components, we have 3-dimensional pixels. In natural languages, the number of dimensions or colors can be in hundreds as words have complex meanings and subtle nuances. This approach is called embedding in AI. The good news here is that it can be implemented as the very first layer of a neural network which can be trained by the same algorithm. By converting documents to sequences of these embedding vectors, we can apply deep neural networks to them just as in computer vision and speech recognition.

Classifying Raw Bytes

Now since we have understood how deep neural networks work, we can see how they can be employed for malware classification by static analysis, that is, by just looking at the contents of the file without any dynamic analysis. Consider the specific case of a windows portable executable (PE) file. It is a sequence of bytes as per PE file format with different sections. A classical machine learning method for static analysis will extract features such as byte n-grams, strings, import tables, entropy features, etc., based on a training set of malicious and benign files and then input these extracted features to a machine learning model such as SVM, nearest neighbors, decision trees or neural networks.

In deep learning, the raw bytes will be the input. Consider a deep convolutional neural network for this task. Since the PE files follow format of machine language and data, these bytes go through an embedding layer as in the case of natural language understanding. Initial convolutional layers process local regions in the file and learn discriminating features. Subsequent layers will process these local features and combine them to form intermediate features, and finally the network will learn global patterns over the entire file. By providing a large amount of training data, we can expect the neural network to learn malware family specific patterns as well as time invariant robust features which distinguish malware from benign files.

Convolutional neural networks are natural choice as they work great for computer vision and human malware analysts can often tell if a file is malware by looking at the raw bytes and picking up certain visual features. For expert malware analysts this visual analysis approach is very resistant to drift because extracted features are more fundamentally related to malware. For example, humans can recognize data obfuscated in a way designed to avoid traditional signatures.

Enrichment / Attribution as a Side Benefit

One advantage of using deep learning is that it can also tell us which portions of a file are malicious by looking at receptive fields of neurons which get activated. This opens the possibility of a malware analyst using deep learning as a tool to assist him or her in the task of classifying difficult cases.

Conclusion

In cybersecurity, there is now growing interest in applying deep learning to malware classification as evidenced by several publications from academia as well as industry. Review of these publications show that though there are differences in their neural network architectures, but they all share common themes of very large training datasets and underlying motivation of automatic feature engineering.

The application area of malware classification is very different from conventional areas such as computer vision, speech recognition and natural language understanding, but it is exciting to see that concepts of complex pattern recognition and of hierarchical features learned in an automated data driven manner still carry over to this new domain. Future research work will further advance applications of AI techniques for malware classification and other problems in cybersecurity.

Acknowledgements: Author thanks Andrew Gardner and Nolan Kent for very helpful comments and feedback.

Deep Learning for Malware Classification was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.

User and entity behavioral analytics (UEBA) is a broad umbrella term for many user and entity focused technologies. UEBA is a burgeoning area for numerous industry applications; yet its definition has been a challenge and is the focus of significant blogging:

• Anton Chuvakin at Gartner
• Heather Howland at Preempt
• Chris Brook at Digital Guardian
• Kevin Gee at Bitglass

As researchers and practitioners attempt to define it more clearly, we can see that UEBA is inherently interdisciplinary. It draws on many key areas and technologies: machine learning, networking, statistics, human computer interaction, and visualization. It also encompasses a host of approaches, systems, and technologies, for example in the security industry:

• CASB — cloud access security broker systems enforce policies (and provide data and threat protection) between a cloud service customer and their cloud solutions provider;
• DLP — data loss prevention systems inspect data (both at rest and in use) to apply corporate policies and subsequent actions (log, report, encrypt etc.) to that data;
• DCAP — data-centric audit and protection systems work similarly to DLP by safeguarding specific private data through data governance and monitoring;
• EDR — endpoint detection and response techniques focus on detection, inspection, and mitigation of users’ endpoints.

What is largely agreed upon is the emphasis on producing analytics for tracking the malicious or risky behaviors of users in the context of other users and entities.

A major challenge and misunderstood aspect of many UEBA systems, is that they inherit many serious challenges from their application of anomaly detection. In this article I will elucidate some key challenges and questions for both researchers and practitioners building UEBA systems.

UEBA Challenges

Anomaly detection is the identification of unusual or rare data instances (observations, items, events, samples, cases, records, etc.) when compared to the majority of the data. It is common practice to use the term “normal” to identify the majority of the data and “anomalous” or “outliers” for data outside the normal region. Anomaly and outlier detection is a well-established field, with a plethora of approaches, systems, and techniques being published each year in a wide variety of domains. I will cover just a few that pertain strongly to the security and more specifically UEBA areas. There are many challenges to using anomaly detection for UEBA:

1. We want interesting anomalies, but that depends on an analyst or end-user to determine “interestingness”. Clearly this may vary highly across individuals or groups.

2. Constructing normal boundaries is hard: Defining a normal region, often in a geometrically complex space, is extremely challenging. For example, many approaches require thresholds or hyper-parameters which radically change what is considered an outlier.

3. Real data are noisy. What am I measuring? Are my anomalies noise in the measurement apparatus, or the result of low event frequencies? Often suspicious and malicious behavior is infrequent, but so too are many non-malicious behaviors of real-world systems.

4. The distribution of anomalies and normal behavior are often dynamic

5. What works in one domain often fails to transfer. Cross-domain anomaly detection methods are challenging (e.g., a rapid decrease may not be an anomaly for a stock price, but could be rare and deadly for blood pressure)

As a critical distinction, some UEBA approaches are actually trying to perform novelty detection. Novelty detection is similar to anomaly detection but is instead focused on finding motifs and patterns previously unobserved in a dataset. This research is especially useful for detecting novel data or signals that haven’t yet been seen by a trained, supervised machine learning system. Markou and Singh have great coverage of statistically sound approaches for this [Markou & Singh, 2017].

Subjective User Interest Driving Anomaly Value

UEBA problems often start with someone saying, “I want to find some interesting and uncommon behaviors for a user.” This statement typically flows into a host of semi-supervised and unsupervised methods for anomaly detection. For example, detecting fraud, cyber-intrusions, and fake reviews all share an interesting aspect to an analyst, but precisely what that is varies case-by-case. The type of anomaly itself can vary from problem to problem. Chandola et al. taxonomize anomalies into three general types [Chandola et al., 2009]:

Point Anomalies — when an individual data instance is view as anomalous with respect to the other data. A significant amount of prior research has focused on methods for detecting these.

Contextual Anomalies — when a data instance is anomalous in a very specific context, but not anomalous otherwise. Sometimes called conditional anomalies, these require a neighborhood of other data instances about which the behavior of the data instance in question maybe be anomalous. This can be spatially co-located points, historical points in a time series, or prior behaviors of a user.

Collective Anomalies — when multiple data instances are considered anomalous when compared with the whole of the data. While research has focused on many areas (e.g., time-varying, spatial, graph), sequences are often of the greatest importance to UEBA. Often many actions are needed to constitute an attack.

Unfortunately, most black-box anomaly detectors do a terrible job aligning the anomaly function (the means of selecting a normal region) with the subjective user interest function. The language of your anomaly detector is set by the input feature-space; if you don’t have meaningful inputs, the interpretation and “explainability” of any detected anomalies loses its traction. For example, consider using a one-class-SVM (a fairly popular out-of-the-box method) for finding behavioral anomalies when looking at user event data. The SVM provides you with a ranking of the geometric behavior of your event data instances, in which case an anomaly may not be interesting with respect to any malicious behavior at all (it could be a benign low frequency action or noisy data collection). Capturing the event input data at the right granularity is critical in finding suspicious behaviors, many of which occur as an aggregate of very low-level events.

An additional critical consideration is what is being output to the UEBA system or analyst. Is the goal to label a particular data instance (anomalous vs normal) or to rank (score how anomalous each instance is). If you don’t have labeled data for training, producing meaningful labels will be extremely challenging.

Every system requires validation, in the case of supervised learning a large corpus of work exists on measuring model performance. However, unsupervised anomaly detection systems are notoriously hard to evaluate. Luckily in the UEBA domain we often have the expertise of domain experts and analysts to provide feedback on the efficacy of an approach. There is a growing body of research in creating human-in-the-loop systems that directly utilize feedback to improve actively running models.

Defining Anomalous Regions

Depending on whether the problem is supervised, semi-supervised, or unsupervised a practitioner may use: classification, statistical, clustering, or information theoretic approaches to construct the normal region. No single approach has yet proven unambiguously to be better than all others for a single domain. More details on what works well per domain can be read in [Ahmed et al., 2015]. It is the data themselves which dictate what approaches can and cannot be used.

Many of our datasets rely heavily on large quantities of high-dimensional, heterogeneous data. Defining a normal region for these models is often left completely up to the practitioner. By dialing the various parameters that define the normal region, a practitioner may create an arbitrary number of anomalies and even modify the per-anomaly scores as they adjust system sensitivity. This results in systems which, by design, tend to over-alert. For example, for UEBA and SIEM systems this often means that the analyst is inundated with an endless torrent of anomalies from a model that never adapts to de-rank the ones they actively ignore.

Distributions Are Dynamic & Real Data Are Noisy

The security domain has highly dynamic data, even without the inclusion of active adversaries. This adds an additional challenge to performing anomaly detection in many UEBA technologies. With changes in the normal region come changes to the definition of anomalies for that dataset. If the normal region is highly dynamic, the variance in detected anomalies increases steadily. Some work (like [Pavlov & Pennock, 2003]) addresses this problem, but this is still an ongoing research challenge.

Many UEBA techniques utilize a graph or network to represent users, entities and their interactions. These too are often dynamic! These dynamic networks are of particular interest to modeling many UEBA tasks as they contain rich multi-user-entity relationships. A survey covering many of the best approaches can be found in [Ranshous et al., 2015].

A key approach is utilizing analyst expertise to continually refine the normal region (or ranking model) directly from analyst feedback. Using analyst feedback directly in a statistically sound way tends to produce models that actually detects things according to what is interesting, not just what is different. There are several successful active learning systems anomaly detection systems for security applications like [Beaugnon et al., 2018] and [Almgren & Jonsson, 2004]. Further development in active learning appears to be one of our best chances to conquer dynamic and noisy datasets.

Even the best data collection systems still induce noise. Unfortunately, noise often produces anomalies that are not suited to the analyst’s subjective interest function (e.g., a system hang caused unusual process behavior, but is otherwise uninteresting). Although they have fallen out of favor by researchers, noise removal [Teng et al., 1990] and noise accommodation [Rousseeuw & Hubert, 2011] are both approaches used to lessen noise in a dataset before analysis is performed. If the noise itself is similar to the anomalies, removing it often worsens the detectors performance.

Anomaly Detection System Transfers Are Hard

Lastly, UEBA research tends not to be concentrated in dense academic venues (unlike machine learning or statistics). This makes sharing and disseminating research findings much more challenging. Because UEBA solutions do a wide variety of different things, lessons-learned from one system transfer poorly to others. In addition, anomaly detection approaches are extremely domain-specific as noted in [Chandola et al., 2009] and [Ahmed et al., 2015]. What is considered an anomaly in a fraud detection system may not be of particular interest in an intrusion detection system. These facts make the growth of UEBA as a research area somewhat gangly, segmented, and awkward.

In short, when considering an anomaly detection system for a UEBA solution, think about:

1) What drives the detection of these anomalies? Is it just uncommon behavior? Risky behavior? What makes an example interesting. If you can’t describe these then anomaly detection is likely to underperform in your solution. The data used as an input should be able to help explain what is strange or anomalous about the data.

2) Are your anomalies really point anomalies or is context important? Is a single action enough to say it was anomalous or do you need a collective anomaly (multiple actions)?

3) How quickly does your system or population change?

4) Can I directly involve the analyst with improving my product to perform active learning (human-in-the-loop anomaly detection)?

Acknowledgments: Nociconist, Azmi Dwipranata, and Baboon Designs for diagram components.

On Finding Interesting Anomalies in UEBA Systems was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.

In this post we will examine 10 of the most common misunderstandings about AI/ML, particularly as they impact cybersecurity practices. Save yourself 3.5 hours of online reading: the AI/ML myths described in the blogosphere tend to fall into 6 clusters (the outer ring in illustration above). I will intersperse that with 4 out of many technical/ research-oriented gotchas, drawing from 23 years of experience building detectors for the implantable medical device and cybersecurity industries (the inner ring).

1. AI/ML Semantics Gotchas

Much ado has been made about trying to differentiate AI from machine learning, ML from neural networks, NNs from deep learning, and so forth. Then there is the question of whether AI itself is just automation, or a magic blackbox, or imitation of the human brain, or autonomous agency, etc. Without resorting to yet another Venn diagram, I prefer to think of ML as the “practical subset of AI that works.” Broadly speaking, ML synthesizes a mapping from inputs to outputs by being shown examples (patterns and possibly targets) and getting “experience” from that, as opposed to having the mapping explicitly programmed line by line in computer code. As overheard at the most recent RSA conference,

“AI is written in PowerPoint; ML is written in Python.”

If a little more pedantry is required, then simply think of set-theoretic symbols: AI ⊃ ML ⊃ DL, and AI\ML = ES where the latter refers to expert systems (rule-based symbolic reasoning) that dominated the early days of computational intelligence.

2. Big Data Gotchas

A classic misconception is that big data (more of it and of any kind) is always better for AI/ML models. One area of concern is that unqualified use of big data can amplify implicit biases [Parker-Wood]. In general, we might attach double the gravitas to big models, yet ironically obtain “doubly wrong” conclusions from them. Remember Google Flu? Years ago, it was incorrectly predicting more than double the proportion of flu cases compared to CDC. Big exploratory analysis was misinterpreted as being predictive. It is useful to see any data analysis as falling into one of 6 categories [Leek & Peng]: (1) descriptive (e.g., the Census), (2) exploratory, (3) inferential (will population pattern hold beyond the dataset?), (4) predictive (inferential at individual level; typical ML), (5) causal (on-average effect; e.g., smoking → cancer), and (6) mechanistic (deterministic effect). Then per Leek & Peng, the most common error in data analysis is mistaking the category of the question. So in security as in science, we might see correlation confused with causation, uncorrected multi-comparison fishing expeditions, overfitting, and analyses with “n=1 cases.” Big data has brought us a world of amazing analytics, but that doesn’t mean it can defy principled statistics and reason.

A global intelligence network of big data does confer technical and marketing advantages to security vendors — the more trillions of data points (and their interrelationships), the more we can “know.” Since algorithms are increasingly open-sourced, it has become more about who has “more” and “better” data. But some competitors may suffer from data “endowment effects.” Having more data at the expense of quality doesn’t mean better models — the good ol’ garbage-in-garbage-out adage still applies. A more fundamental limitation is that the threat landscape is ever changing, so if we shorten the time window of observation to counteract or “freeze” its time-varying nature, we end up with smaller, not bigger data.

While big data would seem to make Bayesian reasoning moot (no need to estimate a revised posterior when the prior is already all data ever to be seen), we can’t really aggregate all data in the face of time-varying rules of the game. Thus, reasoning with small data will remain crucially important. In the medium term, lots of data may not be needed thanks to transfer learning and weakly supervised active learning [Berg]. In the long term, machine intelligence will benefit most from small-data friendly forms of learning including one/few-shot, learning-to-learn, and causality [Pearl].

3. Adversarial ML Gotchas

You must have heard by now that ML models are vulnerable to adversarial inputs conducive to seemingly “absurd” errors (to humans anyway). As automated ML classifiers pervade across domains including cybersecurity, these purposeful errors could grow to be a serious problem. Despite numerous studies over the past five years, the field of adversarial ML is still considered “proto-alchemy,” with no unbroken defenses demonstrated to date [Evans keynote; Carlini & Wagner]. The defense side of adversarial ML has tried to answer a blend of 2 questions: (a) How can we robustify a model (make it harder for an attacker to fool)? This led to “adversarial training, defensive distillation, feature squeezing, and architecture modification”; and (b) What about adversarial inputs is measurably different from regular ones? This led to “input validators” and “adversarial detectors.” By omissions in the current discourse, these methods created the illusion that we could one day pre-bake a solution at training time that would protect our model against one-or-few-off adversarial inputs at deployment time. Our investigations at Symantec strongly suggest the latter goal is unrealizable.

As a former academic, I tend to obsess about pedagogy and like to indulge in creating scientific animations that help illustrate concepts without graphs or formulas. In the two videos below (~90s each), you’ll “wear goggles” that let you see what the ML model sees, and henceforth understand what happens to our detector in its regular, intended happy path, vs in the classic adversarial detection experiment. The main takeaway is that what’s really being detected from the appearance of an input sample alone is the model’s difficulty in handling the input sample (i.e., its own uncertainty), not the intentionality of an adversarial actor. We’re better off striving to get our technologies ever closer to Bayesian optimality [cf. Gal & Smith], and adversarial training is one step in that direction provided we don’t fall into the trap of “over-robustifying” for cases that don’t really match the threat environment.

4. Ad Hoc Ensembling Gotchas

As described in another post, ensembling can offer powerful ways to combine models in order to improve malware detection [Kenemer]. Problems arise, however, whenever ensembling is done in an ad hoc rather than principled manner. A common pattern seen in cybersecurity and other industries is one where a research team develops a “textbook” model, correct under ideal conditions, then during deployment the model doesn’t work as expected because real life doesn’t match the assumptions, data are messier and non-stationary, etc. At that point, manually added rules to patch up the deficiencies start creeping up. One example is the use of Boolean ensembling where the binary decisions of M separate detectors are combined by logical disjunction (OR = “any” rule). A rationale for this is to make sure true positives (TPs ) aren’t lost from one training period to the next, while any false positives (FPs) introduced could still be handled by whitelisting. However, it can be shown that this OR rule has TPr better than the best individual detector, but simultaneously has FPr worse than the worst individual, and this worsens as the size of the ensemble grows. Thus, the whitelists and ad hockery required to compensate for this behavior can grow bigger than the underlying decision models themselves!

It is known that taking the convex hull of individual ROC operating points yields a better classifier, however that is still rarely the optimal solution. In seminal work, Barreno et al. show that the optimal Neyman-Pearson solution that can be extracted from M binary detectors is a computationally hard (impractical) piecewise linear function along likelihood ratio intervals. A more realistic practice is to use linear weighted voting combinations (e.g., linear or logistic regression). Even though combining binary decisions may still be suboptimal, combining the soft (not binary) probabilistic outputs of the models tends to get pretty close to the best achievable ROC. Research at Symantec revealed Boolean ROC operating points actually live in a “canopy” formed by all 2^(2^M) possible Boolean rules, whose “Markovitz-efficient” frontier corresponds to Barreno’s optimal. The figure below shows the subset of this canopy corresponding to OR rule for 3 base detectors. The logistic ensembler (cyan curve) surpasses the frontier and almost reaches the best possible solution (gold curve).

Unfortunately, a problem remains: combining expert models that start from the same input features and end up with correlated errors tends to yield no incremental benefit. But at least by using a principled version of ensembling you won’t be eliminating the possibility of finding a better combination from the outset.

5. Dystopian Views Gotchas

“Success in creating effective AI could be the biggest event in the history of our civilization. Or the worst.”

— Stephen Hawking

If the latter doomsday case is in store, a bit ironically, we may not have time to see it, as world-renowned Prof. Hawking warned we only have about 100 years left to leave Earth. These profoundly sobering predictions were conditional on humans not learning or being able to control climate, over-population, disease, and in the case of AI, its malicious use in autonomous weaponry and oppression of the masses [Kharpal].

Other dystopian views revolve around whether AI will replace people, taking over their jobs, or not people but only their mundane tasks. The answer is probably neither. AI/ML isn’t just about replacing mundane tasks, but also augmenting human capabilities and imagination [Mahadevan].

Further, as in past technology-driven economic shifts, new skillset requirements, transient displacement in the adapting job market, and suitable retraining programs will continue to move forward. In the early days of AI, an idea was floating around that we’d all one day be [insert your preferred leisurely gerund here], while the machines worked for us. Despite incredible progress in automation, what I’ve experienced has been the opposite — ever-increasing workloads.

So the above are wake-up calls for those who welcome AI/ML as strictly for-good, as well as those who instill fear about it. AI/ML is a dual-use technology (for good and for bad), and it will primarily help us protect customers in security, but also secondarily increase the attack surface when malicious actors attempt to use data poisoning, model stealing, and adversarial ML against us [Gardner, ITU keynote]. We should continue to focus on the bright side without being oblivious to the dark side. A good way to think about this is English comedian Eric Idle’s response when asked if he was worried about AI:

“I’m worried about Artificial Stupidity” — Eric Idle

6. State-of-the-Art Gotchas

Every AI/ML security project must ensure that the latest state-of-the-art (SoTA) model is implemented, right? Not so fast! At Symantec, we have seen the perils of both ignoring/postponing SoTA, and too eagerly incorporating it. Soon after the Center for Advanced Machine Learning (CAML) was established in 2014, it became clear that some systems in production had been reinventing ML wheels, yet were suboptimal. Dramatic improvements affecting over 100 million endpoints were made by largely returning to ML “textbook” principles, applicable to static and behavioral malware detection.

On the other hand, we have seen that going to the other extreme of eager SoTA adoption results in folks being constantly distracted by new shiny objects, copy-pasting GitHub code without more than a passing understanding of its theoretical underpinnings, and the accumulation of technical [Sculley et al.] and research debt. Whereas open-sourced research and MOOCs promise to democratize AI/ML, others opine AI/ML security would be better left to experts. For example, unlike open-source code to detect a cat in a video, a security log file is far less obvious to identify as suspicious, so the model can’t be simply “set and forget” [Malanov]. Furthermore, SoTA models are usually overfit [Rasmus]. I call this “ML one-trick ponies,” where the hello-world example works, but the variants you’re actually interested in, don’t.

Part of the SoTA dilemma may stem from the difference in workflows between academia and industry. As cogently described by Rothe, the academic research tends to reward beating a flexible performance metric, whereas the industrial one starts from fixed requirements and works backwards to a solution. The best practice seems to be to strike a balance between the publicly visible state of the art and custom in-house developments.

7. Precision-Recall vs ROC Gotchas

Every time I receive a link about someone swearing that precision-recall (PR) curves are superior to ROC curves, it’s “OK, another one good for a chuckle.” So let’s put it to rest, shall we: for a given dataset, there is a one-to-one correspondence between PR and ROC spaces, such that each one contains the other’s same confusion matrices [Davis & Goadrich]. The reason some folks are attracted to PR is that in problems with highly skewed class imbalance it might amplify aspects that seem less obvious in ROC. The caveat they don’t mention is that precision (PPV; the P in PR) is hopelessly tied to whatever proportion of negative vs positive class samples happened to be in effect during the experiment (which may differ from the finally deployed classifier’s proportion encountered in real life). This is in contrast with Sensitivity (TPr) and Specificity (1 minus FPr), which are independent of class priors by definition. To see the relation between Sens =P(1̂|1) and positive predictive value PPV =P(1|1̂), use Bayes rule or algebra to obtain PPV = Sens*P(1)/P(1̂), and therein lies the issue (the P(1) proportionality). There is no such issue with recall (=Sens; the R in PR).

In otherwise sensible security literature you might find downright false statements such as “ROC curves are misleading in an imbalanced dataset.” They’re only misleading during a MISreading of the curves! What the cited references are really talking about is that area under the curve (AUC; not the curves in and of themselves) can be misleading when ROC curves cross each other and we have other costs in mind, which is true. But in malware detection, where very low FPr is absolutely required, we know better than to rely on the whole AUC (if anything, a truncated version would be used). ROC curves are agnostic to class imbalance [Fawcett] and that’s why we tend to prefer them more often than PR curves at Symantec. Love the class-prevalence agnosis and let the user or application decide on a detection threshold that makes sense to them, rather than implicitly baking one into a P(1) that may or may not hold.

8. Covariate Shift Gotchas

From time to time in ML security, when a testing dataset doesn’t match the statistics of a training dataset, people may be quick to point to covariate shift as the culprit. But chances are that’s probably not the case! Think of joint distribution p(.) as a function providing the statistical “glue” between a bunch of variables, describing how frequently or rarely you’d find any particular configuration of co-occurring values. Let A(x,y) be the joint of features x and labels y during training (the past), and let B(x,y) be the joint during testing (the future/ deployment/ production). The problem of learning a classifier from A(x,y) when B(x,y) will be different is called domain adaptation. A joint can change for many reasons, to wit:

(1) The whole problem is time-varying p(x(t),y(t)) (or tougher with separate t). To go beyond frequent classifier retraining, we’d need to learn dynamics, e.g., via reinforcement learning or prognostics.

(2) Features are changing p(x(t),y), e.g., from feature selection or from cybersecurity multi-label classifiers used as features.

(3) Class labels are changing p(x,y(t)), as in cybersecurity reputation systems.

(4) Class label distribution P(y)=Pr[y] (math purists: ignore notation abuses; blog is a trade-off), i.e., good-vs-bad proportion, differs but class-conditionals stay put: A(x|y) = B(x|y). This is called class imbalance. From product rule, p(x,y) =p(x|y)P(y), so B(x,y) =A(x|y)B(y) =A(x|y)A(y)B(y)/A(y) =A(x,y)B(y)/A(y). Thus, to match future B(x,y) from our current A(x,y) (represented empirically by the training set), we can rescale by the label-dependent ratio B(y)/A(y). E.g., during training do instance-weighting or good ol’ oversampling/under-sampling according to that ratio (= a constant B(1)/A(1) for bad samples and another one =B(0)/A(0) for good samples). Equivalently, simply slide the detection threshold to a desired FPr when the model was trained balanced — a preferred best practice at Symantec.

(5) Feature distribution P(x) differs but class-posteriors stay put: A(y|x) =B(y|x). This is called covariate shift [Shimodaira]. Folks think of this as input features having a different mean and variance in train vs test, but it’s more nuanced than that: the P(y|x) relation has to be preserved. From product rule, p(x,y) =P(y|x)P(x), so B(x,y) =A(y|x)B(x) =A(y|x)A(x)B(x)/A(x) =A(x,y)B(x)/A(x). Thus, to match future B(x,y) from our current A(x,y), we can reshape by the input-dependent ratio B(x)/A(x) and attempt instance weighting. However, it can be difficult to estimate this ratio. Since AI/ML models tend to be big and complex, covariate shift where the relation P(y|x) remains intact is a much less likely explanation than (1) thru (3) above.

9. “Next-Gen” Cybersecurity Gotchas

The last few years witnessed a rise in guerrilla tactics among so-called “next-generation” startups driving a wedge between the old AV establishment and a new industry category that purportedly basically “invented” machine learning for cybersecurity. Some aggressive marketing included declaring that signatures are dead, and detecting bogus repacked files as malware while turning off competitors’ protections [Gallagher]. Bolder claims included being able to protect against 0-day malware without updates for 6 months, and that old AV doesn’t use ML. In a now deleted post, it was declared that AV-TEST could confirm the general marketing claims of next-gen vendors. But buyer beware misleading words. First, signatures aren’t really going away soon as an estimated 30% of all protection, including that of next-gens themselves, is still just that (and why wouldn’t any AV company quickly screen against recurring threats they know about?). Second, in the alleged AV-TEST there was no measure or even mention of FPs! It also described how they had to introduce a “new” test by freezing the product and testing 7 days later for 0-days. It’s called retrospective testing and it’s older that Auld Lang Syne!

Part of the confusion created by these claims arises from the fact that there’s actually a continuum from signature/ fingerprint type of detection, to generic/ heuristic definitions that cover 100s of thousands of variants (whether we had seen them before or not) starting to look like decision-tree rules, to a more complete abstraction of rules such as deep neural networks and higher AI. The beginning of ML use in the AV industry happened the moment rule-bases couldn’t be written by hand anymore due to the exploding threat landscape, and that was some 15 years ago [Malanov].

It is useful to recall the 9 principles of testing from the Anti-Malware Testing Standards Organization. Tests should be: (1) not harmful, (2) unbiased, (3) open and transparent, (4) balanced regarding TPs and FPs, (5) validated regarding labels, (6) consistent regarding consumer vs enterprise, (7) conclusive based on evidence, (8) statistically valid, and (9) responsive to questions via correspondents. The solution to bad AV-TEST debuts for any aspiring cybersecurity company should not be to inject confusion, blame the test organizations, and violate all 9 principles above.

10. Not-There-Yet Gotchas

Our final source of nonstop mythology around AI/ML is especially common in security lore: demanding that a trained model test well on 0-day samples, because after all, we don’t care as much about malicious samples in the training set (those are already “known” to be bad). There is a double error going on here. First, there is inherent value in a model that covers 10s of millions of “known” samples in a compressed way, since the equivalent signature-based whitelist + blacklist would be bigger than the model itself.

Second and more importantly, asking for accurate 0-day coverage is like moving from classic statistical ML to the realm of “magic extrapolation.” The former teaches us to train on a distribution and hope to deploy on samples drawn from that same (or close-enough) distribution. If the distribution has continuous variables, repetitions are extremely unlikely and in that sense new samples are always 0-days. But if the distribution is discrete and happens to have {banana, orange, apple} in its domain, then those tokens will typically recur in the future because that is what the distribution is. The issue arises when we train on {banana, orange, apple} and then expect the model to “know” the right answer when a {mango} comes along. Let’s face it, current ML security doesn’t yet reason; it magnificently interpolates and sometimes “luckily extrapolates,” but that’s all predicated on a 0-day not being too far off the learned similarities captured in the model.

In reference to deep learning, Judea Pearl’s The Book of Why interview has described this as amounting to just “curve fitting.” Technologies that “aren’t there yet” in security include cloudless client-side learning, replacements for the industry-standard multi-layered approach to security [Malanov], reinforcement learning, and causality modeling. When we have that, we’ll be in a better position to ask for magic extrapolation.

In closing, I hope to have helped you see the 6 broad categories of misunderstandings surrounding AI/ML security, but also challenged you with 4 out of many technical, and at times controversial, sources of confusion. Some of the latter ideas, including the limits of hardening against adversarial ML, are part of ongoing cutting-edge research at Symantec.

10 ML Gotchas for AI/ML Security! was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.

Millions of hours have been spent writing about the dangers of the brave new world we find ourselves in. Will we find ourselves in thrall to our robot overlords? Displaced from our jobs and cast aside? The monsters loom large in our minds, but much like Dr. Frankenstein, the true monster was with us from the beginning of the story. The most realistic dangers of AI/ML arise not from the jobs displaced (there will be many), or the sentient machines (expert consensus is that there will not be any, any time soon, not as we understand sentience). Rather, it will come from the already present human beings who collect and store our data, and train algorithms.

AI ethicist Dr. Shannon Vallor has called AI/ML a dark mirror of society. How data is collected, how it is used, and how value is extracted from it, are all reflections of how our society already works, for better or for worse. Facebook’s ads do not — cannot — learn from or target impoverished populations without access to the internet, and Amazon’s famously biased resume filter was only as unbiased as the predominantly male resumes fed to it. In machine learning, you can predict the future, but only if it looks exactly like the past or evolves from it smoothly and predictably. AI/ML, at least in its current state of advancement, cannot model truly disruptive phenomena like social change.

However, the fact that AI/ML replicates existing systems doesn’t mean we should undersell its dangers. AI/ML is an accelerator and amplifier of those existing processes, and that means we can create new problems faster and with more impact than ever before. AI/ML’s hunger for data has led to huge accumulations of sensitive information about every human or device with internet access (and many without), and that data poses an attractive nuisance to everyone who can gain access to it through power, money, or theft. And AI/ML’s ability to automate and accelerate decision making means that we can make biased, bad decisions at scale as never before.

Data is often described as the new oil. However, it’s more like a barren plot of land, purchased in hopes of striking oil someday. Very few companies in the “big data” rush have a clear idea of when or how they can monetize their data. But it is clear to everyone that entities with very little data are at a disadvantage. The simple physics of that have led to huge stockpiles of data that pose tempting targets for attackers, while holding an unclear immediate value for their collectors. One of the first things that companies can do to protect themselves from ethical issues around data is to ask whether they have a clear idea of what they will do with it, and whether there is any actual value to be gained. Data that is not collected cannot be stolen or misused, and a good data science consultant early on is generally cheaper than creating and maintaining huge storage pools of useless bits.

Even if a company has a clear plan to monetize their data, ethical concerns will arise. They need to be aware of how data can harm their users in the wrong hands, and also need to ensure their users are not surprised by the ways they collect and use data. As the old saw goes, “never do anything [with data] you wouldn’t want to see reported on the front page of the New York Times.”

There are a number of ways to mitigate risk around data collection. The first and simplest is not to collect it. If it must be collected, follow data handling best practices. Use encryption where appropriate. Don’t keep data longer than you need it. Audit all accesses, and the more sensitive the data, the more carefully it should be audited. Consider using algorithmic privacy techniques such as differential privacy or sketching, which allow you to collect aggregate statistics without exposing the underlying data.

Spend some time doing detailed threat modeling for your data, just like you would with any other security scenario. How could the Russian mafia use this? An abusive ex-spouse with admin credentials? A modern-day 3rd Reich? A foreign government? How would you prevent that abuse?

Once someone has made thoughtful decisions around what they will collect and how it is stored, and gotten user consent, they now have a heavier ethical problem to struggle with. What is the bias in the data? How do the choices of algorithms lead to bias amplification? There are very few truly random samples in this world. Almost all data is biased from the moment it is sampled, and some of those biases have far reaching consequences. For example, as previously noted, Facebook’s algorithms are based only on the pool of Facebook users. Data fed to word embedding algorithms can reflect the implicit sexisms of open source corpora and our own society. IoT devices oversample affluent early adopters. Most of the original facial recognition data sets were collected from college students, who are WEIRD (Western, educated, and from industrialized, rich, and democratic countries), not to mention young, and racially unrepresentative of the world as a whole. Algorithms trained on these data sets can struggle to recognize women, the elderly, people of color, and other minorities. To add fuel to the problem, the primary developers of AI/ML are also WEIRD, and they can readily overlook potential problems that come from outside their own experience.

An algorithm needs to work fairly for all the users of its system, present and potential. How does undersampling racial diversity, economic diversity, or gender impact the choices an algorithm makes for those populations? What are the social consequences? Even if the original algorithm began as just a toy, toy algorithms have a way of finding themselves reused throughout industry. Facial recognition data sets created for benchmarking in academia are now being used to train image recognition algorithms for photo tagging, facial unlocking for phones, and surveillance cameras. There is no such thing as an unimportant bias once the paper is published and the code is on the internet.

Ethics is not a tidy checklist. There is no ISO standard for it. Responsible AI/ML requires compassion and broad systemic thinking about all of your users, not just the ones who are like you, and how your choices will affect people’s lives. However, behaving responsibly towards users is not only the right thing to do, it’s the business savvy thing to do. Unethical handling of data, and bad algorithms are legally and reputationally problematic. (Just look at Facebook’s stock after the Cambridge Analytica scandal, or consider the consequences of a racially biased algorithm in a regulated industry such as loans.) Responsible AI/ML means considering the downstream effects of data handling and algorithmic choices, but the results benefit everyone, companies and users alike.

Responsible AI/ML: privacy, bias and more in the age of the algorithm was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.

Universal Approximation

Some widely-used models, such as random forests and neural networks, are known to be universal approximators, which means they have the capacity to learn any function mapping between inputs and outputs, although this may only occur asymptotically. So, what exactly does this mean? If we can approximate any mapping of input characteristics (features) to our classification labels, then shouldn’t we be able to solve any classification problem perfectly? Initially it may seem so — but fitting a function to a training dataset is only part of the picture and as soon as we clarify our true goal (which is revealed in the next section), it will become apparent that limitations do indeed arise despite the great power of universal approximation.

No Free Lunch

There will always be an inherent tension between learning specific patterns in the data used for training and generalizing to unseen data. For classification problems, the goal is to learn a mapping from input data to an output class label which will also generalize well to new data not seen during training. Unfortunately, the no free lunch theorem tells us there is no model creation method which can generalize well across all possible input data distributions. One problem that arises when training machine learning models is overfitting, which occurs when the model learns the training data set very well but fails to generalize well to new data. Overfitting occurs when the model starts paying attention to irrelevant details (i.e. noise) in the data. This problem is mitigated to a large extent by a technique known as regularization, which adds an extra penalty in the training process to encourage the model to limit its complexity, and this has the end result of better generalization. Also, the use of validation data, which tests how well the model performs on data outside the training set, helps to mitigate overfitting by essentially checking for it during training. The “no free lunch” theorem simply states that there is no procedure to find a model that works well across all problems (there is no magic solution for everything) but this certainly does not imply that there is not a good model, nor does it prevent us from finding a good model for our specific problem.

Bagging, Boosting, Stacking

Some classes of models are themselves already a hierarchy of simpler models. For example, one can think of neural networks as a collection of logistic regression models (loosely speaking, depending on the activation functions used) and random forests are collections of decision trees. We can therefore think of ensembling techniques as extending the hierarchy further in order to partially overcome the limitations of the constituent models. There are many different ways to combine models together — we will review some of the common techniques including bagging, boosting, and stacking, and provide some insight as to how they operate.

Bagging, a shorthand term for “bootstrap aggregation”, is a method which utilizes different model instances of the same algorithm type (in classical bagging) which are trained on random subsets of the training data. How are these random subsets obtained? Usually by sampling with replacement, which means samples can be used multiple times. The predictions from each model are combined, typically by averaging or majority voting. The end result is a more robust model with less output variance in the predictions. The random forest is an example of bagging which randomly subsamples both training data and input features. Bagging generally provides better results overall (due to the variance reduction) as compared to just training on the entire dataset in one shot. A detailed review of the bias-variance trade-off in machine learning is a discussion for another day…

Boosting takes a different approach— a strong model is built sequentially from a cascade of weaker models, each of which are tuned to learn those samples which proved difficult for the previous stages. Each model potentially sees all of the data samples in the training set, but the samples are weighted based on the position in the cascade. Additionally, each model does not necessarily need to use the same algorithm. The combining function can be arbitrary and varies with the particular method. For example, with Adaboost (a well-known boosting technique) the output is combined from a weighted sum of model outputs, where the weights are updated using a specific update rule, whereas with gradient boosting (another well-known technique) the weights are learned via a technique called gradient descent.

What if you already have some classifiers, but want to improve results? Or perhaps you only have access to the outputs of other classifiers? Stacking to the rescue… Stacking utilizes a collection of models based on different learning algorithms which are trained on the entire training set, and then combines the predictions using a combining function which is learned from an additional training step. The combining function can be an arbitrary combining algorithm, but logistic regression is frequently used because it is simple and tends to work well for many problems.

Performance Considerations

Employing ensembling techniques is not a trivial task — there is no universal guarantee that the ensemble will perform better than any constituent model across the metrics-of-interest. One important consideration is how each model provides complementary information to the meta-learner or combiner. In the bagging method, each model instance uses the same algorithm but sees different data samples. With boosting, each model can utilize different algorithms and sees the data according to its own weighting in the cascade. Stacking also utilizes model instances with different algorithms each of which can partition the input space using different mechanisms. One of the big challenges for ensembling strong models is that they already perform well, which by definition implies correlated outputs.

We can illustrate this idea with a simple classification problem using decision trees trained on 20-dimensional synthetic Gaussian mixture data and comparing the ROC (receiver operator characteristic) curves for the individual decision trees vs. the ensemble. The ensemble predictions will be computed by averaging the predictions from the individual models (bagging). The ROC curve shows how a classifier’s discriminative ability varies as a function of the classification threshold and gives a good view into the overall performance of the classifier. A perfect classifier would produce an ROC curve which approaches the (TPR,FPR)=(1,0) coordinate and random guessing would yield a line with slope=1 (on a linear scale) which connects (0,0) to (1,1).

In this example, we take five simple decision trees which are constrained to utilize only two features when constructing decision thresholds and have a maximum depth of two levels. In this case the ensembled ROC (black curve) generally outperforms the individual models since it aggregates information from many features while the individual models only see a small subset of features.

Now, if we increase the complexity of each decision tree by allowing more features (i.e. sixteen) when constructing decision thresholds and increasing the maximum depth to four levels, then each tree becomes more of an ‘expert’ and the variance of the curves decreases as the trees are mostly in consensus. The ensembled ROC (black curve) no longer outperforms all models across the domain and in some areas approaches the average. Note that these examples are for illustration only and much better absolute performance can be achieved with more sophisticated models such as random forests, deep networks, etc. We can see that it is more difficult to realize an improvement when ensembling models with highly correlated output predictions than models which make different errors and so provide complementary information to the meta-learner/combiner.

Conclusion

Ensembling is a powerful and proven set of methods for improving classification performance and robustness of machine learning models. We should keep in mind the effects of using weak-vs-strong learners and the fundamental limitations of generalization to guide our model choices and set expectations for performance. In practice, our data may be limited and noisy, and it may be difficult to determine which ensemble method to adopt for a given problem, but in principle ensembling should provide benefit even if there are diminishing returns when the constituent models are highly correlated. By joining the predictive strengths of many models, ensembling is a powerful way to scale our capabilities to complex real-world classification problems.

AI/ML Security Pro Tips: The Power of Ensembling was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.

As a recently-hired ML Research Engineer in Symantec’s Center for Advanced Machine Learning (CAML), I’ve become familiar with the MinHash technique as a method for document summarization. In this article I’ll detail what I’ve learned from a practitioner’s standpoint, and describe the pros and cons of this classic algorithm as it pertains to privacy, security and ML.

MinHash is a specific type of Locality Sensitive Hashing (LSH), a class of algorithms that are extremely useful and popular tools for measuring document similarity. MinHash is time- and space-efficient with implementations available in most commonly used programming languages. It has a long history across a wide variety of information retrieval use cases, including:

• Near-duplicate detection: identifying and removing duplicates from vast collections of documents, webpages or other files.
• Clustering: grouping like documents or files together
• Fingerprinting: determining unique content
• Large-scale search: efficiently retrieving query content, typically content related to a test document

So how can MinHash be used in machine learning? And equally importantly: how secure is MinHash? Let’s find out.

What is MinHash?

In case you’ve been under a rock for twenty years (as I have), I’ll start with a brief history and conceptual review of the algorithm. MinHash was developed in 1997 during the Dot-com boom to address a common problem faced by early search engines: the existence of multiple near-duplicate websites. How could one identify whether two webpages were nearly identical and remove them from search results? Andrei Broder had the answer and we’ll walk through his algorithm step by step.

Since the goal of MinHash is to find similar documents let’s start with a definition of “similar.” It turns out that many really great ones already exist, and one in particular works well with documents: the Jaccard Index or Jaccard Similarity Coefficient. Jaccard similarity is a statistic that measures how close two sets are in an intuitive fashion using the idea of intersection over union. This is easily explained with a toy example.

Suppose we have two documents:
A: “There are four lights.”
B: “There are five lights.”
We can visualize these like so:

The Jaccard Index for these two documents, J(A,B) = 0.6. How did we compute that? It’s the ratio of the number of shared terms (intersection), to the total number of unique terms (union):

The higher the similarity value, the more terms are shared between documents and the more semantically close we expect the documents to be. (Note: the converse does not hold; that is, two documents about the same topic using completely different words will not necessarily be detected as similar.) This works just fine until you’re faced with millions or billions of documents. Breaking each one down into its respective words, computing their Jaccard Indexes, and performing pair-wise comparisons between each document and every other document in your sample becomes computationally prohibitive.

Enter MinHash, a method for estimating the Jaccard Index, whose key idea is to find the number of overlapping segments by creating a document “fingerprint.” There are two standard implementations. In both cases, we start by running a sliding window of size k over the document in a process called “shingling.” A shingle is the collection of characters that each window “sees” as it slides through the document. For each shingle we generate hashes, a subset of which are used as the desired fingerprint.

Many hash functions

In this algorithm variant, we perform hashing by passing each shingle through h different hash functions. Specifically, we’ll take the first hash function, apply it to all document shingles, and select the minimum resulting value as the first component of the document fingerprint. Then we’ll repeat this for each of the remaining h-1 hash functions resulting in h-element MinHash signature.

Single hash function

Computing many unique hash functions can be costly in its own regard. An alternative variant uses a single hash function. Here, we hash all of our document’s shingles and keep just the n smallest values, resulting in an n-element MinHash signature. As an example, let’s process our sample documents under this implementation using the md5 hash and check that our similarity estimate makes sense.

First, we create our shingles. Here k=5 and white space is represented by underscores.
A: “There are four lights” →
[‘There’, ‘here_’, …, ‘e_are’, ‘are_f’,…, ‘_four’, ‘our_l’,…,‘light’, ‘ights’]
B: “There are five lights” →
[‘There’, ‘here_’, …, ‘e_are’, ‘are_f’,…, ‘_five’, ‘ive_l’,…,‘light’, ‘ights’]

How many shingles did we make? That’s computed as the total number of characters in a document minus the shingle size, plus one. So we have 21–5+1=17 shingles.

Next, we hash each shingle to get:
A: [60e46a, 409f25, 11a972, daf874, f77b37, bd014f, d7b02e, …]
B: [60e46a, 409f25, 11a972, daf874, f77b37, bd014f, d7b02e, …]

Note that the md5 hash function always outputs a 32-character hexadecimal string, but without loss of generality I’ve kept just the first six hex digits. Also notice that most of the hex strings are identical between the two documents since most of the shingles are identical — the same string will always map to the same hash value.

Equivalently, we can express these hexadecimal strings as decimals:
A: [396870, 264690, 72343, 896903, 1013683, 774164, 883458, …]
B: [396870, 264690, 72343, 896903, 1013683, 774164, 883458, …]

Now let’s take the n=10 lowest values as our fingerprint for each document. We can compute the MinHash similarity as M(A,B) = total number of values in common / n. For our example with n=10, we get 0.5 — Not bad! This is really close to our original estimate of the Jaccard similarity.

Why does this work?

The beauty lies in randomness and probability. As an analogy, MinHash can be thought of as taking the union of the two sets, shuffling them into a random order, and then selecting the first value in the new random order (representing the minimum hash). Let’s see how this might work using our running example with words rather than shingles for clarity.

We’ll randomly shuffle our words and highlight in bold the shared words:
[‘five’, ‘are’, ‘there’, ‘four’, ‘lights’]

Q: If we select only a single MinHash component (n=1), what is the probability that one of the shared words ends up first on that list?
A: It’s just the number of shared words (3) divided by the total number of words (5) = 3/5 — the Jaccard Similarity.

Q: If we want n MinHash components, how many of them will be shared words, on average?
A: This is equal to the number of components, n, times the probability of a shared word: (3/5)*n.

Now we can compute the expected value of the MinHash similarity:

M(A, B) = (3/5)*n / n = 3/5 = J(A, B), the Jaccard Similarity!

What if we took all n=17 shingles? We’d get a similarity estimate of 0.588, illustrating that larger n yields a better estimate of similarity since you’re keeping more of the document in your representation. However, there are some drawbacks to keeping more shingles. One issue is that the cost of storing these document summaries increases, which may be a problem depending on your application. There are also security concerns, which we’ll look at in a later section.

We now have fixed length document summary vectors that closely estimate the Jaccard Similarity. So how does this fit into machine learning?

MinHash in ML

MinHash is not typically thought of as “machine learning” but that doesn’t mean it’s worthless in this realm. The MinHash output is essentially a set of randomly selected document features, as opposed to deterministically designed features more commonly used in machine learning. MinHash is not the only document summarization method available, either: alternatives include the canonical Bag-of-Words, TF-IDF (a weighted version of Bag-of-Words), and (all the rage these days) word embeddings like Word2Vec, GloVe, and FastText. MinHash is simpler than popular alternatives, but does it hold up to these other approaches?

Spoiler Alert: yes, surprisingly well.

Vector Representation

In order to train a classic ML classifier on MinHash features, we need a representation that it will recognize. We’ll continue with our running example in which we used the same hash function several times. While the hex hashes presented above work fine in LSH, they won’t fly for traditional ML algorithms. Instead, we convert these into bit vectors. Hex has 16 characters, which is 2⁴ possible bit strings per hex digit. Md5 outputs 32 character hashes resulting in a bit representation that would be (2⁴)³² or 340282366920938463463374607431768211456 0’s and 1’s! Whoa!

Let’s do a concrete example. In our documents above, each 5-character shingle was converted to a 32-character md5 hash and we truncated those to 6 hex characters each. According to our formula above, this will result in a bit array that is (2⁴)⁶ = 16,777,216 bits long!

But this representation may seem familiar to those who know Bag-of-Words. In BoW the document is represented as a large, sparse vector of bits. The length of the vector is the size of the vocabulary. Each bit where a word occurs in the document is assigned the value +1 (in some implementations, repeats are counted to create a true histogram of words).

A typical vocabulary size is, say, 50K English words: {‘a’, ‘aardvark’, … “zap”, ‘zebra’}. In our running example, we can compute a BoW representation for our documents wherein a 1 is located in the spots corresponding to the terms “are”, “four” (or “five”), “lights”, and “there”.

In MinHash, the “vocabulary size” is instead the total number of possible bit values, which we already computed to be 16,777,216. The 1’s are located in the positions corresponding to the hash values. For example, if n=3:

A: “There are four lights” → [ 101228, 1157490, 1539676]
B: “There are five lights” → [ 844631, 1157490, 2802746]

And their corresponding bit vectors would be:

We are now armed with numerical document summary vectors fit for ML algorithms, so let’s see how MinHash performs in the wild.

Time for a Real Example

To do a real world test we’ll need a sample of documents with a rich vocabulary and, ideally, a clear goal — like classification. The Enron Ham/Spam emails are a standard corpus for classifying spam vs. non-spam. This corpus consists of about 33K emails nearly evenly split between real (ham) and spam emails. We’ll treat each email as a document, taking care to remove metadata like subject headers and To/From fields. This ensures that our model focuses on the text of the email body without overfitting to these summary data.

We’ll process each email with MinHash, as well as with several popular pre-trained word embeddings including GloVe, Word2Vec, and FastText. While a detailed explanation would require its own blog post, I’ll briefly describe the concept here. Word embeddings are more sophisticated than the BoW approach. Instead of a bit, each word is itself represented by a vector capturing its semantic relationship to other words, i.e., man is to king as woman is to _____ (queen), something that MinHash is not designed for. Each of these published word embeddings consists of a vocabulary in which each word has been assigned its own unique vector. Most of these vectors are 300 elements long, though this varies (specifically, the GloVe embeddings have been published in sizes ranging from 50 to 300).

One way to apply a word embedding to an email is to first break it up into individual words and, for each word, look up its corresponding semantic vector in the word embedding vocabulary. We can then average together all of the word vectors to obtain a document summary vector. This isn’t the only way to apply word embeddings but it’s straightforward so let’s run with it.

To generate a MinHash vector for each email, I used a single md5 hash function on 5-character shingles. Each md5 output is truncated to 5 hex digits and the n=100 smallest values are retained. After converting to bit vectors they are 1,048,576 elements long and contain exactly 100 1’s.

Using a standard 80/20 train/test split, here are the classification results on both a Linear SVM and a Random Forest. No extensive hyperparameter tuning has been performed: this is straight out of the box binary classification with default parameters. (Note: correctly doing RF with MinHash features requires some special finagling, which is beyond the scope of this article.)

Woo-ee! Who would have thought that MinHash would come anywhere close to what is currently considered the state-of-the-art in text representation? Now there’s a lot we could discuss on the pros and cons of pre-trained word embeddings (like how their dimensionality affects efficacy) but that’s a topic for another day. And while this is by no means conclusive, it certainly demonstrates that MinHash isn’t a completely unreasonable approach to document summarization. And while MinHash can provide reasonable performance for document classification it wouldn’t fair as well in other natural language processing tasks such as question answering, machine translation, or named-entity recognition, all of which rely on cognitive language interpretation.

How Secure is Minhash?

MinHash seems great but how secure is it?

Let’s imagine an attacker whose goal is to reconstruct some or all of the original document using only the minhashes and some knowledge of the hash function. This attack is of concern in scenarios where the summarized documents are private, such as a data loss prevention or email use case. In these applications, a company may want to build models over private corpora of documents. They might reasonably use MinHash as a way to create a storable summary, one which they hope will remain private. Having an irreversible summary of a document is important for legal compliance with privacy regulations such as GDPR, as well as being the right thing for customers in the event of a data breach. If a summary is reversible, however, then the document should be considered vulnerable to attack.

Without performing a detailed crypto-analysis of MinHash, let’s consider some practical guidelines for effective use.

Shingle size

When evaluating the usefulness and security of a given MinHash implementation the shingle size is the first item to consider. If k is very large then the document summary is not robust to minor changes, such as the addition or removal of white space, and it’s difficult to compare near matches. By contrast, if k is extremely small then the saved hashes will cover very little of the document and not carry enough context to be meaningful. (For an extreme example, consider a single character hash.)

Always use as many hash functions as are computationally feasible.

From a security perspective, the shorter the shingle is the easier it is to brute force reverse the text, particularly if the number of hash functions used is small, or one. A k-character shingle for, say, English, has approximately 2.62*k bits of entropy. For example, a 5-character shingle has about 13–14 bits of entropy. Thus, an attacker could build a rainbow table — a pre-computed table for reversing cryptographic hash functions — consisting of all plausible 5-character English shingles, e.g. {“_the_”, “and_a”, “it_is”, …}. Such a table would only cost about 6.8 MB of storage space — easy! (Folks, this is also why your passwords should be much longer than 5 characters and should include special characters when possible!) However, if we increase the shingle size, the attacker’s task becomes much more challenging as the number of plausible variations grows quickly. For example, for k=8, the storage size of the corresponding rainbow table is nearly a petabyte! If we now include several hash functions (instead of one), the attacker will need a rainbow table for each one —further increasing the challenge of reconstruction.

Smaller shingles can lead to more robust comparisons but are also easier to reconstruct.

Number of hashes

We should also consider the number of hashes, n, to keep when forming the signature. When n is small we have a less statistically significant sample of the unique hashes in a document making it harder to determine the similarity between two documents. Imagine if I only kept one hashed shingle per document — comparison would be a challenge! However, when n is very large we are keeping more and more shingles, which represent more of the document. This allows for a more robust comparison (recall in our example that our comparison estimate improved when we kept all 17 shingles).

Consider the trade-off between document coverage and document reconstructability.

While keeping more shingles will help your application determine better similarity estimates, it can also work to an attacker’s advantage since they now have a larger amount of information from which to draw reference. this is particularly troublesome for short documents like emails. For example, I might decide to retain the n=20 smallest hash values for each document in my corpus. Now, if my example documents A and B are included in that corpus, n=20 is larger than the number of possible shingles (17 at k=5) and thus the entire document’s shingles are part of its fingerprint.

Specifically, an attacker now has a sequence alignment problem, which is common in the field of bioinformatics for identifying similar sequences in DNA. When the shingles are long and the attacker has a large number of them, many characters will overlap making the attacker’s task easier. In addition, the attacker has supplementary information about the vocabulary and its frequency in the target language, so even if only a fragment of a word is available it can be used to infer the missing piece.

Though this attack is labor-intensive, a motivated attacker might still find it worthwhile to steal and reconstruct particular emails with key sensitive information. We recommend always using as many hash functions as are computationally feasible for your application. Additionally, consider how important accurate comparisons are to the efficacy of your application and whether it’s possible to increase the shingle size or reduce the number of stored hashes to cover less of each document.

Conclusion

MinHash is a tried and true algorithm for performing document similarity. It is time- and space-efficient and can be used in a variety of machine learning algorithms making it highly versatile. However, these representations are not guaranteed to be private or secure since it is possible to brute force reverse engineer a document depending on the chosen implementation. If security is high on your priority list be especially careful how you implement MinHash and take precautions to select appropriate shingle sizes and number of minhashes so as to maximize protection. There’s another option that we’ve been working on here at CAML related to Differential Privacy, a mathematical framework that provides provable privacy guarantees, but that discussion will have to wait for another blog.

Acknowledgements

I’d like to acknowledge Aleatha Parker-Wood, Andrew B. Gardner, and the entire Symantec CAML team for help in preparing this.

AI/ML Security Pro Tips: Understanding MinHash in a Security Context was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.

The problem of adversarial inputs

Consider the image below: is it a stop sign? To the human eye, even with a few added markings, it is indeed a stop sign. Now what if a deep neural network was responsible for determining what the sign is? Well, deep neural networks are already a crucial part of autonomous vehicle technology, and in many cases are responsible for deciphering the images taken by the powerful cameras of an autonomous vehicle. It turns out that researchers have discovered that the minor change to the stop sign pictured below leads a deep neural network to identify it as a “Speed Limit 45” sign!?

Let’s consider another image, this time of a number. It is easy for the human eye to see that the number in the image is 7. Once again, as we show in the next section, we are able to fool a deep neural network into predicting the number in the image as a 2.

The two examples above illustrate the problem of adversarial inputs — inputs that look typical to the human eye, but which are perturbed in a small fashion, can easily fool deep neural networks into making incorrect predictions.

At this time, one may wonder what causes neural networks to be fooled by the above inputs. The short answer is that due to the design of neural networks, an adversary that has access to the neural network can figure out what changes to a typical input will lead to an incorrect prediction. We try to provide an intuitive explanation of how this fooling is carried out by an adversary in the section titled “Why do adversarial inputs exist?”. In fact, it has also been shown that an adversary can create adversarial inputs for neural networks without having complete access to the network. As we will discuss later, this weakness can have damaging consequences when neural networks are deployed in real world applications such as autonomous driving, speech recognition, and malware detection. Readers who are more interested in the practical implications of these issues can jump to the section titled “Practical threats due to adversarial inputs”.

Given the above, it is only natural to ask whether such adversarial inputs exist naturally, without the intervention of an adversary. For instance, is it possible for a autonomous vehicle to see a stop sign in a thunderstorm and classify it as a “Speed Limit 65” sign? What are the implications of such mistakes? In order to tackle the above questions, we must first understand what adversarial inputs are and how they fool neural networks.

What are adversarial inputs?

Adversarial inputs lack a precise definition as their defining properties vary from one problem domain to another. For example, in the problem of image classification, given an image, one would consider an adversarial input to be an image that looks very similar to the given image but is classified incorrectly. Here, similarity may be measured in terms of how close the two images appear to a human observer or by some other mathematical similarity measure. In a malware classification problem, an adversarial binary may be a binary that preserves the semantic functionality of the original (malicious) binary but is misclassified as a clean binary by adding a few carefully chosen bytes the original binary. In this case, the similarity between the two binaries can be measured by their functionality, which is identical. In this blog, we choose to illustrate the notion of adversarial inputs using the computer vision problem domain as it is the simplest to grasp.

Consider the MNIST handwritten digit classification problem, where the dataset consists of grayscale images of handwritten digits between 0–9 and the machine learning classification task is to correctly label the digit on a given input image. We provide a few examples of such images below.

We built and trained a neural network to classify the above images correctly (i.e. it assigned class labels: 2, 7, 9, 0, and 6 to the above images). Now examine the images below — they seem to be very similar to the images above — however each of these images was incorrectly classified by the same neural network (i.e. it assigned class labels: 4, 2, 3, 9, and 1 to the images below) . That is, we were able to construct adversarial images from the original images that look almost identical to the human eye but fooled the neural network into making incorrect predictions.

In order to understand how these adversarial inputs are created and why it is possible to create them, it is important to understand how neural networks make predictions. Before we are able to explain the prediction mechanism of neural networks, we must provide a brief introduction to them.

What are neural networks?

A neural network is a machine learning algorithm that is modeled loosely on the human brain. As the name suggests, a neural network consists of a network of nodes (neurons) organized in a layer-wise manner, where a layer is simply a collection of neurons. For instance, a 5 layer neural network with 100 neurons in each layer means that the neural network consists of 5 different layers (explained further below) where each layer consists of 100 nodes (neurons). As an aside on terminology: the more layers a neural network consists of, the “deeper” it is, which is why the term “neural network” and “deep neural network” are used interchangeably. The sub-field of machine learning that uses neural networks (or deep neural networks) is referred to as deep learning. For a more complete introduction to neural networks we refer the reader to the easily accessible materials on deep learning and convolutional neural networks.

Below is an image taken from these materials depicting the layer-wise structure of neural networks. The image depicts a 3 layer neural network with 4 nodes (neurons) in the first layer, 4 nodes (neurons) in the second layer and 1 node(neuron) in the last layer (the reader should ignore the use of “hidden” layer and “output” layer for now). The input layer is not considered to be a part of the neural network, it is simply a node based depiction of the input (in the image below, it consists of 3 nodes). Each node in the network holds a number. For instance, if the input is a 28 x 28 gray scale image, then the value of each pixel of the image will be held in exactly one node of the 784 nodes in the input layer. The arrows connecting a node to every node in the layer to the right means that the value from a given node will flow forward to all the nodes in the layer to the right of it. Hence, a neural network makes predictions by pushing the values from the input layer through the network and finally through the output layer which is the answer to a given problem. For instance, a network might take the image of a cat in the input layer and output 0.99 in the output layer, which could be the probability the network assigns to the input image being a cat.

One of the primary reasons behind the success of neural networks [AG1] is that they only need labeled data in order to learn to solve a particular task. This means that if we provide a neural network with enough images of cats and dogs where each cat image is labeled as a cat and each dog image is labeled as a dog, the network will be able to itself learn the complex relationships required to tell if a new image is a cat or a dog. With this brief introduction to neural networks, we can now proceed to understand how they make predictions.

How do deep neural networks make predictions?

Classification is the problem of assigning a class label to a given input, i.e. given an input x, assign it to a class k. For example, in the MNIST handwritten digit classification problem, given an image of a handwritten digit, the classification task is to assign it to a class between 0–9. For most problem domains, the input x belongs to some subset of a finite dimensional Euclidean space, which is commonly referred to as the input space. Any input is a point in this input space, and a deep neural network then divides this space into a small enclosed regions and assigns a class label to each region. One can think of each layer of the neural network as learning successively more and more about the input space, and then successively dividing the input space up into more and more regions. At the output layer, each enclosed region is assigned a particular class label.

This means that every input that lies in a particular enclosed region will be assigned the same class label by the neural network. The lines or curves that divide this input space form what is called the decision boundary. The number of lines or curves used by a neural network to divide the input space is arbitrary as it depends on the architecture of the neural network and is not important for this discussion (more specifically, it depends on the number of layers, and the number of neurons per layer). We illustrate this gradual process with a 3 layer neural network as it divides a 2 dimensional input space and forms its decision boundary.

The first layer (Layer 0) of this neural network uses 4 lines to divide the input space, resulting in 9 enclosed regions, the second layer (Layer 1) adds more lines per enclosed region to further divide each enclosed region into more enclosed regions, and the third layer (Layer 2) further divides each enclosed region in a similar manner and also assigns a class label to each enclosed region in the input space. The final classification of the neural network is then based on the class labels that the final layer (third layer in the image above) assigns to each enclosed region. That is, after the action of the final layer, every enclosed region is assigned a class label and any input belonging to the same enclosed region will be assigned the same class label by the neural network. Since the neural network uses this process to divide the entire input space, it is able to assign a class label to any input. We now explain how this leads to the creation of adversarial inputs.

Why do adversarial inputs exist?

Albeit very powerful, the above process of dividing the input space also makes the neural network vulnerable to adversarial inputs. This is because in many cases neighboring regions have different class labels (in fact this would be true in more cases than not — the reasons behind why neighboring regions may have the same class label are more technical and not crucial for this discussion). Therefore, an adversary can take an input belonging to an enclosed region with class label k (we assume k is the correct label), and change it by a very small amount such that the input is now shifted to a neighboring enclosed region with a different class label j. When this modified input is presented to the neural network, the network will classify it as belonging to class j. Therefore, the adversary has thereby changed the class label that will be predicted by the neural network from a correct one to an incorrect one. However, since the input was only changed by a small amount, it is still very similar to the original input causing the phenomenon of being adversarial. As a techinical aside, it is important to note here that this phenomenon arguably worsens in higher dimensional spaces as most of the points are concentrated on the decision boundary.

One may ask how an adversary knows what changes will cause the input to shift into the desired neighboring region? The short answer is that the adversary utilizes the knowledge of the neural network to craft the required adversarial changes. The long answer requires a deeper understanding neural networks, how they are trained, basic calculus, and optimization. Therefore, we leave it out as an exposition on that topic is not our goal. However, it has been shown that adversaries can also craft adversarial inputs without detailed knowledge of the targeted neural network as well. It is crucial to understand just how many of these regions can be created by neural networks in order to understand just how easy it is to craft adversarial inputs. To illustrate this process, we use the image below which shows how a 1 layer neural network with 1024 neurons divides 2 dimensional input space (we ignore projection details used by the authors for simplicity).

One can see that for any enclosed regions, just how many other enclosed regions are neighbors. The authors also show three inputs belonging to three different classes (i.e. residing in three different regions with different labels). As can be seen, in order to change the label for any of the three inputs, only a small change is required as they are surrounded by numerous regions belonging to different classes.

This raises the question: just how susceptible neural networks are to such adversarial inputs? The answer varies and depends largely on this arrangement of lines or curves in the input space. Consider a neural network that is able to assign the correct class label to any input from the problem domain, can that neural network still be susceptible to adversarial inputs? Yes. Depending on the manner in which the network has divided up the input space, there may still exist regions with a class label k (which is the correct label), that are neighbors of regions with a different class label. Hence, an adversary simply has to perturb the original input in a manner that shifts it into one of the neighboring regions with a different class label in order to fool the network.

The above phenomenon has far reaching security implications in tasks such as facial recognition, malware classification, autonomous driving, financial predictions, and many more. A malicious actor could use this knowledge to masquerade as someone else, modify predictions on business-critical systems, etc. Given the critical impact of this problem, it is natural to ask how we can defend against it.

How can we defend against adversarial inputs?

As explained above, adversarial inputs are crafted by making small changes to the original input. However, these small changes in the input lead to large changes in the neural network output (i.e. network predictions change). Therefore, one natural approach to defend against adversarial inputs would be to ensure that network outputs do not change by a large amount if an attacker makes small changes to the input. This seemingly simple goal however is difficult to accomplish in practice. Most methods attempt to achieve this goal by penalizing the neural network during its training phase to control the amount of change in network output with respect to small changes in the input (we do not explain the details of how this penalization occurs as it requires a deeper understanding of neural networks and the details may take away from the primary point). Although this solution hardens the neural network against adversarial inputs (requires a larger change in the original input in order to fool the network), it does not solve the problem completely. Due to the manner in which a neural network divides up the input space, it is still possible to create adversarial inputs.

Another provable defense against adversarial inputs is to manipulate the decision boundary around the training inputs of the neural network. That is, we move the decision boundary farther away from the training points, hence requiring a larger change to the original input to fool the network. This is illustrated in the image below. Once again, this is a limited defense: it is only applicable to the inputs that the network trained on, and it does not extend to every new test input.

Other defenses use variations of the above ideas in order to make it more difficult for the adversary to fool the network. However, there do not exist any defenses that guarantee protection against adversarial inputs for general deep neural networks. As discussed previously, this is largely due to the manner in which neural networks divide up the input space. Since neural networks have become widely adopted to solve practical problems such as facial recognition, autonomous driving, etc., we must examine the impact of adversarial inputs in such applications.

Practical threats due to adversarial inputs

Due to their superior efficacy and data driven learning, neural networks are extremely popular in practical applications. We examine some real world applications of deep learning and how they are affected by adversarial inputs. We examine some real world applications of deep learning and how they are affected by adversarial inputs.

Autonomous driving technology utilizes deep neural networks for various tasks such as object detection and scene segmentation (determining which class each pixel of an image belongs to). It has been shown that neural networks responsible for segmenting a perceived image can be fooled into an incorrect segmentation of a scene, for example: seeing trucks or cars where there are none, or not seeing a pedestrian where there is one. Another line of work has shown that adversarial inputs also exist in the real world (i.e. it is possible to create an adversarial input, print it out and fool a neural network that looks at this picture). Combining these two properties, one can see that an autonomous driving system that only utilizes deep learning for low level perception may be easily fooled by an adversary. Even without the presence of an adversary, it is crucial to consider how autonomous vehicles perform in extreme conditions (or corner cases).

Another powerful application of deep learning is in speech recognition-based assistants such as Siri, Alexa, and Google Now. These are also vulnerable to adversarial inputs as it has been shown that one can construct inaudible commands that fool these voice assistants into completing simple tasks such as initiating a Face-time call. That is, an adversary can create voice signals which are inaudible to a human, but that fool a voice assistant into completing a particular task. Once again, given the ability of the voice assistant and the sensitivity of the task, this is a critical security issue for such voice recognition systems.

Finally, consider the case of malware classification where a malware detection system examines a file and decides whether it is malicious or not. It has been shown that one can modify a malicious file in a manner that maintains the malicious functionality of the file but fools a neural network based malware detection system into classifying the file as being non-malicious . One can see that the security implications of the vulnerability can be far reaching since a malicious file may be able evade detection and compromise a host.

Conclusion

As shown in this article, adversarial inputs pose a serious threat to deep learning systems. This problem becomes especially important given the large scale adoption of deep neural networks across a variety of domains. Since one of the primary causes of the adversarial phenomenon is the fundamental design of deep neural networks, there do not currently exist any general defenses to this problem and the discovery of such a defense seems unlikely. Hence, it is crucial to examine this problem from a theoretical perspective to formally understand the limits of deep neural networks against adversarial inputs. Even though there are no perfect defenses against adversarial inputs, practitioners currently deploying deep learning models, can try to use existing defenses that reduce the damage for specific network architectures and problem domains.

Adversarial Inputs Against Deep Learning was originally published in AI/ML at Symantec on Medium, where people are continuing the conversation by highlighting and responding to this story.