Introduction to Artificial Neural Network (2)

Introduction to Artificial Neural Network (1)

Everyone is talking about AI and machine learning recently. But the concepts of AI goes back to more than 40 years ago when scientists took steps to model the brain and cognition. In its original concept, there lies a perceptron, an artificial neuron that can form a neural network to learn and make decision (after F. Rosenblatt). Just as a neuron has an all-or-none firing characteristic, a neural network is able to provide a binary response or yes/no. While in the past it required advanced C++ and expensive hardware to run modeling, today knowing Python and having a high-speed computer are sufficient.

1. Principles of a perceptron
A perceptron takes several binary inputs and produces a single binary output. How does it compute the output? Each input is associated with a certain weight w_i and the total value of w_i x_i will be compared against a certain threshold to decide the output. Look at the figure below.

We can take a simplified real life example for how a perceptron works. Suppose there is a jazz festival and you need to decide whether you want to go ('1') or not ('0'). There seems to be 3 important factors that influence your decision, each has its own influence value:
      - Is the weather good (yes/no)? Influence scale = 10.
      - Is your girlfriend going with you (yes/no)? Influence scale = 3.
      - Is the place near a metro station (yes/no)? Influence scale = 4.
Note that the influence scales here represent the weights you personally assign to these factors. For example, you really hate being caught in the rain so much; or you don't really mind if you go alone without your girlfriend and make new friends. You should also infer a threshold to make your decision. That's it, a perceptron has just been used to model how you make a decision. What happens when we combine multiple perceptrons? This structure is called a neural network, as shown in the figure below. In practice, such network is used to take into account more factors and make a better decision.

Let us describe the perceptron more formally. First, the summation of weights and inputs can be rewritten as a dot product of w.x = Σ w_i x_i . Second, the threshold is in fact a bias, b = −threshold. This bias can be thought as a measure of how easy it is to get the perceptron to give an output '1'. Or to put it in more biological terms, it is a measure of how easy it is to get the perceptron to fire. The formula to get the output thus becomes, y = w . x + b. Thirdly, the binary output of '0' or '1' beyond a certain threshold mimics a type of function called a step function.

2. Simple neural network
A neural network is basically a multi-layer perceptron or MLP as shown in the figure above. The leftmost layer is called the input layer and the neurons inside it are called input neurons. The rightmost layer is called an output layer with just a single output neuron. In between, there exists 2 layers of what is called hidden layers, which take inputs from the input layer and project outputs to the output layer. A neural network in such structure is also popularly known as a feedforward neural network since the outputs from one layer are projected to the the next layer to the right and so on, with no feedback allowed. There are a few other neural network architecture, which will be said at a later time.

The power of a neural network lies in the capability to be trained. Neural networks can be 'trained' to behave in a certain way, or to produce a certain output given some patterns of inputs. Engineers can call this an iterative fine-tuning process. We use neural networks to help us decide something. For example, you want to decide whether a blurred image is a picture of a handwritten digit (number "0" to "9"). Training the neural network here means we let the network to readjust the weights and biases within the network according to the given inputs, in this case, different images.

How can we readjust the weights and biases? We let a small change in a weight or bias to cause only a small change in output Δy (like fine-tuning). In this way, we would get our network to behave more in the manner we want. For example, suppose the network was mistakenly classifying an image as an "8" when it should be a "9". We could figure out how to make a small change in the weights and biases so the network gets a little closer to classifying the image as a "9". This process is then repeated over and over again to make the output more and more accurate to decide "9". The network is said to be learning.

But there is one problem. With the current setup, a small change in an input x_i will yield quite a big jump in the binary output, it can completely be flipped (yes/no, '1' or '0'). This is primarily due to the all-or-none nature of the perceptron output. Scientists were not satisfied with such characteristic, so they defined a new type of perceptron where the output follows a sigmoid rather than a step function characteristic. Thus, a neuron with a sigmoid function don't just produce output '1' or '0'. It turns out that with this characteristic, Δy is a linear function of the changes Δw and Δb. This linearity makes it easy to choose small changes in the weights and biases to achieve any desired small change in the output. Formally, output characteristic of an artificial neuron or perceptron can be defined by the activation function, where a sigmoid is one of the examples.

As mentioned, training a neural network means allowing the weights w and biases b to readjust themselves such that a desired output is obtained. We can track how well the training progresses through a metric called a cost function, sometimes also a loss or objective function as a function of weights and biases. Remember that the goal of a neural network is to help us make decision or prediction. Traditionally, the cost function defines the difference between the predicted and the actual output of the network. Our end goal is to find w and b such that this difference is minimized.

3. Minimizing cost function
Suppose we have our multi-layer perceptron and this is so-called our model. Mathematically, the method to "train" the model of a neural network is called backpropagation algorithm. This term is coned after Rumelhart et al who proposed an efficient numerical solution of the training problem. Training or learning in terms of backpropagation here means to minimize discrepancy or error (or something bad) by adjusting weights and biases. 

To portray the discrepancy or error, we need a cost function, which defines how 'good' our model is at the moment as learning progresses. Now we wish to obtain a set of parameters (weights and biases) such that the discrepancy between the predicted and actual output of the model (neural network) as defined by the cost function is minimized. To minimize this so-called cost function, we can use an optimization algorithm called gradient descent, by iteratively moving in the direction of steepest descent as defined by the negative of the gradient (or slope).

Suppose we have a cost function F that depends on imaginary parameter x (x₁ and x₂). Let us imagine a valley defined in the dimension of x₁ and x₂, such as the one shown below, and we want to roll a ball down this valley. Making the ball roll down at different dimension of x₁ and x₂ is akin to saying that the change in F is negative, ΔF < 0. We can build a relationship such that: ΔF ≈ ∇F ⋅ Δx ; where ∇F is a the gradient vector of F, which carries partial differentiation operators. At the moment, it is enough to think a gradient vector simply as something that relates changes in x to changes in F, just as we would expect something called a gradient to do. Suppose we make the change in x to be Δx = −η∇F, where η > 0. Then mathematically, ΔF ≈ −η ∇F⋅∇F = −η∥∇F∥² , which means that ΔF is guaranteed to be negative and F will forever decrease not increase. The ball is for sure rolling down the valley!

The whole idea of iteration is as follows. From an arbitrary ball position of in dimension x, we first compute the change in Δx. so that to find a new position of x → x' = x − η∇F. Note that the arrow denotes an update rule, the variable takes up a new value. This update rule can be thought as defining the gradient descent algorithm. It gives us a way of repeatedly changing the ball position in order to find a minimum value of the function. If we keep doing this over and over again, we will keep decreasing F, until theoretically we reach a global minimum. Once this global minimum has been found, it is said that the training algorithm has converged. Note that η is called learning rate where it is usually kept small, to control learning and to prevent the update behavior to be chaotic.

To summarize, the way the gradient descent algorithm works is to repeatedly compute the gradient vector ∇F, and then to move in the opposite direction step by step, so as to "fall down" the valley. Updates of weight and bias parameters occur in an efficient way until the error is minimized.

Some notes:

1) In more complex networks for a multiclass prediction, softmax is used as the activation function instead of a sigmoid.

2) The following website is informative to understand backpropagation.

Gaussian Mixture Models and EM algorithm

1. Gaussian Mixture Model (GMM)
In an earlier post, it was shown that we can partition our dataset into different subgroups or clusters, or how we hierarchically partition them step by step. One fundamental flaw of the k-means algorithm is the assumption that the dataset is more or less spherical. If it is not, then the algorithm will not do the job well (it will still partition, wrongly!) Another limitation of the k-means algorithm is that it is a hard-clustering algorithm, i.e. the clusters don't overlap. It does not provide any possibility or probability that the point can belong to any of the clusters.

A finite mixture model is a model comprised of an unspecified combination of multiple, but finite number of probability distribution functions.

A mixture model where the probability distribution functions are Gaussian or normal is called a Gaussian Mixture Model (GMM). It exactly attempts to provide a soft-clustering approach where clusters tend to overlap, i.e. there is some probability that a particular point belongs to more than one cluster. As an example, the probability density function of a 1D univariate dataset with 3 mixture components (K = 3) is below.

Fig-1: Probability density function (pdf) of a 1D dataset consisting of 3 mixture components. Note that the separation is not complete between adjacent clusters, and thus it reflects some probabilistic nature in it. [Ref 1]


So, a finite Gaussian mixture model means that we represent the dataset as being composed of K Gaussian functions, each has its own set of model parameters grouped as θ_k = { π, μ, Σ }:
     (1) A mean μ that defines its center.
     (2) A covariance matrix Σ that defines its width.
     (3) A mixing probability π or mixing weights.
In a univariate sense, a Gaussian or Normal distribution is modeled by the mean and variance (μ, σ²), satisfying the sufficient statistics. However, for a D-dimensional multivariate Gaussian distribution, we have a D × D covariance matrix Σ to represent the spread instead. In practice, the covariance matrix Σ can be further decomposed into several parameters that define certain geometric properties which at the same time provide certain constraints in the model for easy estimation (out of scope, but see Fig-3).

The mixing probability defines the probability that a certain point belongs to any clusters (Σπ = 1), which is essentially the cluster assignment problem in k-means. The larger this value is, the wider the shape of the Gaussian function will be, as it provides a higher chance that more points will be included under that function. A cluster assignment problem is estimated by the marginal probability distribution of a point in the mixture model, i.e. a weighted sum of the individual Gaussian function (defined by its three parameters above, Fig-1), where x is our dataset.

Fig-2: (a) Probability density function of 1D GMM; (b) Multivariate 2D gaussian probability density function; (c) An example of finite GMM consisting of 3 mixture components.

Fig-3: Comparison between k-Means and model-based GMM clustering algorithms. In the model-based method, we are not limited to spherical data and can estimate the shape of the distribution through an iterative process called EM algorithm. 


Now, how do we obtain the values for these parameters bearing in mind that we have K Gaussian functions? Of course, if we know the grouping sources beforehand (Fig-1), we can easily fit the Gaussian functions, compute the mean and standard deviation of each function (μ, σ²). In practice, we don't know the grouping sources, and the task can be even more challenging for the multidimensional Gaussian functions. Fortunately, we can estimate the relevant parameters with the help of the maximum likelihood estimation (MLE).

Note: Due to the fact that we need to determine model parameters, the soft-clustering approach using GMM is often called the model-based algorithms.

2. Expectation-Maximization Algorithm
Suppose we have a dataset x with n number of points in a GMM comprising K functions. The data is combined and the distributions are similar enough that it is not obvious to which distribution a given point may belong. To draw a sample from x, we select one of the components having a certain mixing probability π_k. Then with the help of a latent variable, z, for cluster assignment, we define a new probability (or in fact, likelihood) as a form of joint-probability distribution of the dataset x assuming that each data point is i.i.d.

Expectation-Maximization algorithm (EM) is an approach for maximum likelihood estimation with some latent variables. EM algorithm is a way to find maximum-likelihood estimates (MLE) for model parameters when the data is either incomplete, hidden, or multidimensional. The algorithm alternates between two steps:

• The first mode attempts to estimate the missing or latent variables called the estimation-step or E-step.
• The second mode attempts to optimize or maximize the parameters of the model to best explain the data called the maximization-step or M-step.

Nice references:
(1) Gaussian Mixture Model explained (more Maths involved!).
(2) Comparisons between k-means and EM algorithm
(3) Gaussian mixture modeling
# Gentle Introduction to Expectation Maximization
https://www.youtube.com/watch?v=REypj2sy_5U&ab_channel=VictorLavrenko

On Cluster-based Algorithms

I no longer post neuro/stroke-related blog, but more and more machine learning stuffs. Well, "Big Data" and AI/Machine Learning have entered a new beginning worldwide; it becomes a trend now. And this post is inspired by what I found from several online sources regarding clustering algorithms.

What and Why?
Generally speaking, cluster analysis means you group the dataset into different groups or clusters. It is commonly used to identify the underlying structures or patterns in the data. Cluster types are usually not known beforehand. Technically, any cluster-based algorithms try to maximize within-group similarity and maximize between-group distance. In machine learning, clustering is considered unsupervised learning, i.e. an algorithm that tries to discover unknown patterns in the dataset without any known reference (teacher), or prior knowledge of the labels. Lastly, clustering is related to a similar (but not the same!) algorithm called 'classification' which works on reference or labeled data through supervised learning processes. Look at the table below.

Cluster analyses have been widely used in data mining, biomedical research (genetic sequencing, phylogenetic, evolution), image processing, business analytics and social media, etc.

About k-means Algorithm
Let's talk about one of the most popular unsupervised learning algorithms out there, the k-means. This algorithm tries to partition the dataset into k distinct clusters (sub-groups), where each point or observation belongs to only one cluster. Before running the iteration, pre-processing ensures that the dataset belongs to the same scale on the coordinates. If these data points are not normalized, then it may lead to false grouping. Often, missing values are sometimes suboptimal to clustering.

Once your data is ready, we will start the k-means. As with any machine learning techniques, k-means involves an iterative process up to a termination point. In each iteration, it computes the cluster’s centroid, which is the arithmetic mean of all the data points that belong to that cluster.

Step1: Define the number of clusters, k.
Step2: Randomly select k different points to serve as the cluster centroid.
Step3: Assign all other data points to a cluster whose centroid is the nearest.
Step4: After that, calculate the new centroid position for each cluster.
Step5: Repeat Step 3 & 4 until the process reaches the termination criteria.

Objective: to minimize the sum of the squared within-cluster distance, that is, the
Euclidean distance between the data points and the cluster’s centroid.Termination criteria may include: centroids location do not change after some iterations, data points remain in the same cluster, or the user-defined max. number of iterations (e.g. 100) has been reached.

Refer to the GIF animation below. Each centroid is depicted as a white cross. Prior to grouping, data points are still black in color. After the grouping is done, the data points change color accordingly. In each iteration, k-means minimizes the total within-cluster distance which results in a new centroid location, and a shift in the color shade after. Indeed, some points can be reassigned to a different cluster in each iteration. The right panel shows what is known as the "Elbow method" (Fig-1).

Fig-1: Step-by-step process showing k-means clustering algorithm and its performance indicator (*).

In another example below, the initial guess produces three centroid locations in the left panel. The right panel shows the final outcome.

Fig-2: Initial and final centroid position of three different clusters (k = 3) after the iteration process stopped.

where w_ik= 1 for point x_i if it belongs to a certain cluster k; otherwise, w_ik= 0; and μ_k is the centroid of the x_i’s cluster. Minimizing this function contains two parts: first we differentiate J with respect to w_ik first and update the cluster assignments. Following this, we differentiate J with respect to μ_k, and recompute the centroids after the cluster assignments from the previous step.

How do we know whether our k-means has done a good job? Although a visual inspection is easy, one quantitative way is to see whether the # of clusters is already 'good enough' by using some evaluation metrics.

The first type is called the elbow-method, which uses the within-cluster sum of squared distance mentioned earlier. As shown in the figure above, the "elbow" here refers to the profound deflection downward that signifies a maximum improvement in the sum of squared distance. It is crucial to note that this metric continues to decrease monotonically as k increases.

The silhouette method, on the other hand, determines the degree of separation between clusters. It computes a certain coefficient whose value can take up anything in the interval [-1, 1]. Therefore, ideally the value should be as big as possible and closer to 1 to have a good clustering.

Hierarchical Clustering
In hierarchical clustering (HC), grouping is done in steps between two closest or most similar points, to produce certain hierarchy that is depicted as a dendrogram. There are essentially two techniques, the more popular agglomerative HC (bottom-up approach) and the divisive HC (top-down approach). Refer to the following Fig-3 for an illustration.

Fig-3: Two main types of hierarchical clustering, a different way of doing cluster-based analysis (tds com).

Refer to the nice GIF animation below with the different colors in each iteration. The vertical axis is a measure of similarity or closeness of either individual data points or clusters. The height of this vertical axis (Fig. 4) represents the Euclidean distance between the relevant data items grouped together.

Fig-4: Step-by-step process showing agglomerative HC algorithm and its dendrogram with colour-coding (*).

Suppose we work with the agglomerative HC:

Step1: Begin by treating each data point or observation as a separate cluster.
Step2: Compute a distance metric to identify the two points that are closest together.
Step3: Then, merge two points as a new cluster (linkage).
Step4: Repeat Step 2 & 3 for any pair of clusters obtained earlier until it reaches k clusters.

A set of distance or proximity metric between two data points/clusters is used, such as Euclidean distance, maximum distance, Manhattan distance, cosine distance, etc. This matrix is updated in each iteration to display the distance between the pair. 

The order in which clusters are joined is controlled by the linkage methods, meaning the manner you link the two clusters and categorize them hierarchically. There are generally 3 types of linkage in HC, the choice of which is up to us:
   (a) Single linkage: nearest-neighbour distance.
   (b) Complete linkage: furthest-neighbour distance.
   (c) Average linkage: taking the average distance.
   (d) Ward's method: taking the minimum sum of squared distance.

With the Ward's method, the sum of squares starts out at zero, because every point is in its own cluster. It then grows as more clusters are merged in the second iteration (each cluster now consists of more data). Given two pairs of clusters whose centers are equally far apart, Ward’s method will prefer to merge the smaller ones.
Refer to the diagram for more information on the agglomerative hierarchical clustering.


Final notes: Model-based approach
Now let's contrast the two algorithms. Clustering results are much more reproducible (consistent) in the HC if we were to repeat the analysis multiple times. Conversely, different results can be obtained in k-means since we started of with random centroids for every fresh analysis. Care should then be taken in choosing which algorithm and in interpreting the results. Another thing to note is that HC is computationally expensive and cannot handle big data well, but k-means clustering can. The time complexity of k-means is linear, i.e. O(n); while that of HC follows power rule, i.e. O(n²).

Although the k-means algorithm is popular, it suffers some drawbacks. First, the shape of the data is best to be spherical. It will be sub-optimal when the shape of data deviates from spherical shapes. Moreover, it will be confused when there are potentially two overlapping clusters as there is no obvious measure of uncertainty. This is because k-means is hard clustering, no way for a probabilistic partitioning. Lastly, although some methods exist to 'predict' the best number of clusters, it does not know the number of clusters from the data and requires it to be pre-defined.

Traditional clustering algorithms presented here are heuristic-based algorithms that derive clusters directly based on the data. In contrast, another form of clustering, model-based clustering attempts to address this concern and provide a soft assignment where observations have a probability of belonging to each cluster, hence, incorporating a measure of probability or uncertainty to the cluster assignments. For high-dimensional data, model-based approaches are preferred with some iterative methods called the Expectation-Maximization (EM). Unlike the k-means method which uses the Euclidean distance while calculating the distance between each point, the EM method uses more sophisticated statistical models, Gaussian Mixture Model (GMM), so making this a model-based approach. 

Briefly, the EM algorithm is often used to provide the functions more effectively. In the E-step, data points are assigned to the closest cluster according to the highest likelihood. In the M-step, the new centroid of each cluster is computed. In other words, assign the data point x_i to the closest cluster judged by its sum of squared distance from the cluster’s centroid. Iteration stops if the likelihood converges or stabilizes.

(*) Nice tutorial on k-Means
[*] Image source: Giphy website.