Crash Course in Machine Learning

In this article we clarify some of the undefined terms in our previous article and thereby explore a selection of machine learning algorithms and their applications to information security.

This is not meant to be an exhaustive list of all machine learning (ML) algorithms and techniques. We would like, however, to demistify some obscure concepts and dethrone a few buzzwords. Hence, this article is far from neutral.

First of all we can classify by the type of input available. If we are trying to develop a system that can identify if the animal in a picture is a cat or a dog, initially we need to train it with pictures of cats or dogs. Now, do we tell the system what each picture contains? If we do, it’s supervised learning and we say we are training the system with labeled data. The opposite is completely unsupervised learning, with a few levels in between, such as

Next, what do want to obtain from our learned sytem? The cat-dog situation above is a typical classification problem; given a new picture, to what category does it belong? A related but different problem is that of clustering, which tries to divide the inputs into groups according to the features identified in them. The difference is that the groups are not known beforehand, so this is an unsupervised problem.

Both of these problems are discrete, in the sense that categories are separate and there are no in-between elements (a picture that is 80% cat and 20% dog). What if my data is continuous? Good old regression to the rescue! Even the humble least squares linear regression we learned in school can be thought of as a machine learning technique, since it learns a couple of parameters from the data and can make predictions based on those.

Two other interesting problems are estimating the probability distribution of a sample of points (density estimation) and finding a lower-dimensional representation of our inputs (dimensionality reduction):

With these classifications out of the way, let’s go deeper into each particular technique that is interesting for our purposes.

Much like linear regression tries to draw a line that best joins a set of closely correlated points, support vector machines (SVM) try to draw a line that separates a set of naturally separated points. Since a line divides the plane in two, any new point must be on one of the two sides, and is thus classified as belonging to one class or the other.

More generally, if the inputs are n-dimensional vectors, an SVM tries to find a geometric object of dimension n-1 (a hyperplane) that divides the given inputs into two groups. To name an application, support vector machines are used to detect spam in images (which is supposed to evade text spam filters) and face detection.

We need to group unlabeled data in a meaningful way. Of course, the number of possible clusterings is very large. In the k-means technique, we need to specify the desired number of clusters k beforehand. How do we choose? We need a way to measure cluster compactness. For every cluster we can define its centroid, something like its center of mass. Thus a measure of the compactness of a cluster could be the sum of the member-to-centroid distances, called the distortion:

With that defined, we can state the problem clearly as an optimization problem: minimize the sum of all distortions. However, this problem is NP-complete (computationally very difficult) but good estimations can be achieved via k-means. It can be shown and, more importantly, makes intuitive sense, that:

Clustering has been used in the context of security for malware detection; see for example Pai (2015) and Pai et al. (2017).

Loosely inspired by the massive parallelism animal brains are capable of, these models are highly interconnected graphs in which the nodes are (mathematical) functions and the edges have weights, which are to be adjusted by the training. A set of weights is scored by the accuracy of labeled output, and optimized in the next step or epoch of training in a process called back-propagation (of error). The weights are adjusted in such a way that the measured error decreases. The nodes are arranged in layers and their functions are typically smooth versions of step functions (i.e., yes/no functions, but with no big jumps), and there are two special layers for input and output. After training, since the whole network is fixed, it’s only a matter of giving it input and getting the output.

The networks described above are feed-forward, but there are also recurrent neural networks. Convolutional networks use mathematical cross-correlation instead of regular smooth step functions. Deep neural networks owe their name to the great number of layers they use and to the fact that they are unsupervised learning models.

The k-nearest neighbors algorithm (kNN), essentially classifies an element according to the k training elements closest to it.

The kNN algorithm can also be adapted to be used in the context of regression, classification, and anomaly detection, in particular by scoring elements in terms of the distance to its closest neighbor (1NN).

Notice that in kNN there is no training phase. the labeled input is the training data and the model in itself. The most natural application for anomaly detection in computer security is in intrusion detection systems.