Bachelor Thesis Dimensionality Reduction

The concept of dimensionality reduction is quite straightforward. The idea is to reduce the number of dimensions/features while retaining maximum information. Even though the definition is quite simple, being able to perform such transformations is not trivial.

Ideally, the reasons for performing such processes are:(Note this list is not complete but gives a general overview)

• Avoid the curse of dimensionality
• Reducing potential overfitting of further processing
• Reducing computation time of further processing
• Reducing storage space
• Plotting
• Noise removal
• Removing Correlated features
• Removing redundant features

Several methods can perform this transformation. They are usually divided into 2 categories:

• Linear methods
• Non-Linear methods

Of course, there can also be other types of categorizations (e.g. feature selection, feature extraction, Neural, Manifold based, Local methods etc.) In the following sections, we will present roughly 2 approaches per category.

An Autoencoder is a special network architecture which approximate two different function encode and decode such as: \[decode(encode(\hat{X})) = \hat{X}\]

The network is therefore composed of two different sub-networks. An Encoder which can be defined as: \[encode \rightarrow \mathbb{R}^n \times \mathbb{R}^m \] And a Decoder which can be defined as: \[decode \rightarrow \mathbb{R}^m \times \mathbb{R}^n \]

There are two constraints to these two functions. The first one is that decode must be approximately the inverse of the encode¹. The second one is that \[ m << n \]

The second constraint is an architectural one, meanwhile the first one is a functional constraint that will be achieved after the network is trained.

The error function is, therefore, a reconstruction error or distance measure between the input and output.

The layer between the Encoder and the Decoder express what is usually known as Latent space which dimensionality is \(\mathbb{R}^m\).

We will from now on refer to the Latent space as \(\hat{z}\). For clarity we can rewrite the above formulas as: \[encode(\hat{X}) = \hat{z}\] \[decode(\hat{z}) \approx \hat{X}\]

As Wang stated ²

Auto-encoder can be seen as a way to transform representation.

Principal Component Analysis(PCA) is a linear technique. It is probably one of the most used methods because of its reliability and explainability. Conceptually, PCA find the directions of maximum variance in the data and project it into a new space with fewer dimensions than the data

The crucial point of PCA is to find the Principal Component of the data which are therefore completely uncorrelated while maintaining most of the variability of the data. Note The Principal Components are selected based on the explained variance.

Linear Discriminant Analysis (LDA) is a linear method. In a nutshell, we want to find a new subspace to project the data in order to maximize classes separability.

The idea to measure such separability is to maximize the difference between the mean of each class while minimizing the spread within the class.

The main disadvantage is that LDA have good performance only if the dataset is Normally distributed.

Locally Linear Embedding (LLE) is a non-linear methods. Conceptually it aims to discover the underline non-linear structure of the data set while preserving the distance within local neighborhoods.

This techinique is a 3 steps procedure:

1. Uses a KNN approach to find the k nearest neighbors of every data point.
2. Approximates each data vecotr as a weighted linear combination of its k-nearest neighbors. (Note all data point which are not in a particular neighborhoods have 0 weight)
3. Computes the wieghts that best reconstruct the vectors from its neighbors

Isometric Mapping (Isomap) is non-linear method which belong to the category of Manifold Learning.

Ideally, it is quite similar to LLE, however, the crucial objective of this mapping is to maintain a geodesic distance between two points.

This technique is also defined by a 3 steps process:

1. Construct a neighbourhoods graph (equivalent to the first step of LLE)
2. Compute the shortest path between points (using either Dijkstra's or Floyd-Warshall algorithm)
3. Construct a d-dimensional embedding by a partial eigenvalue decomposition (i.e. taking the d largest eigenvalues of the kernel)

So, we have rapidly been through classical and not dimensionality reduction techniques. The main focus of this thesis, though, is to perform what is usually referred to as Representation Learning.

Of course, it is quite trivial to see how Representation Learning and Dimensionality reduction are strictly related.

Indeed, a representation usually has fewer dimensions than the original input. A good representation also should maintain the most important information/features of the input space.

Therefore, the two branches are strictly related. However, it is important to notice that a good Dimensionality reduction method does not always produce a good representation (by good we mean that it has all the important features needed to learn a mapping between states and actions)

For this reason, this thesis will mainly focus on Autoencoders technique to perform dimensionality reduction (and/or Representation learning) since they give a good tradeoff between process flexibility and accuracy. (for reference: ^{2, 3, 4})

It is also crucial to notice that the literature indicate that usually Autoencoders-based latent space (or embeddings) outperforms other dimensionality reduction technique when the latent space is used as input in an RL-based framework (for reference : ^{5 , 6 , 7 , 8 , 9 , 10})

Before jumping into more advanced Autoencoders-based technique we will briefly introduce MDPs Generalization. This is another important point in the thesis since, the two main objectives of constructing low dimensional latent space for an RL algorithm are:

• Faster and more stable convergence
• Better Generalization property

The first point seems quite intuitive. Having a low dimensional state-space should result in a faster and more stable convergence since the RL algorithm needs to learn a mapping from a low dimensional state-space to action which should be easier than learning a mapping from a high dimensional state space to action.

Another interesting point made in ⁵ is that all Deep Reinforcement Learning (DRL) algorithm implicitly learns a first mapping from high dimensional state space to low dimensional state space and then the maps this low dimensional state space to action. Therefore, by performing dimensionality reduction we take away the concern of learning a good representation from the DRL algorithm which therefore will only focus on learning a mapping from state to action directly.

Other valuable properties of doing such a process are described in the next chapter.

For formal description of this concept look up at ⁵ (section 2.2) The idea though is quite intuitive. Let us assume that we have a natural world from which we can sample MDPs. The crucial characteristic of these MDPs is that they all do have the same action space but they have differences between the state spaces. However, since we are sampling these MDPs from the same natural world these state spaces must have some structural similarity (i.e. isomorphisms)

Therefore, to have good generalization property, we need to construct a good representation that aims to represent the state space of the natural world. To do so, we cannot leave this concern to a DRL method for the following reason.

Since DRL is maximizing some objectives, it makes sense that the best representation is the most MDP-entangled one and therefore is the one that is guided by the learning process to learn.⁵ Therefore, if we do not move this concern outside the DRL we will have poor generalization ability, particularly without extensive fine-tuning.

Here, Dimensionality reduction methods such as Autoencoders comes to the rescue. Since they do not maximize the same objective as the DRL we can guide the process of learning a representation as we please. Moreover, we will discover in the next chapters how it is crucial to aims for disentangled representation.

The main downfall of moving the concern of learning a representation outside DRL is that we need to be careful of what kind of dataset we use to train the autoencoders. It is crucial that the dataset has big variability and covers most of the "visible" state space. This is because a lot of autoencoders architecture have weird/undefined behaviour in point of the space not explored during training which is not desirable.

Other potential downfalls are:

• Increase overall computation time (not always true though)
• Risk of losing important information for the DRL algorithm
• Non-trivial definition of AE-hyperparameters

Since usually the AE objective is centred on the reconstruction error it is not trivial to focus on learning useful representations as opposed to learning representations which are based on the ability of the decoder to achieve better reconstruction errors. Therefore, a tradeoff must be made to achieve useful representations for RL. We will see in future sections how different AE architectures deal with this tradeoff.

This is a big topic in current AI research ¹¹ (6th big challenge)

In the literature is not entirely clear what we mean when we talk about disentangled representations. However, some research and effort was made to have a formal definition ¹² It seems, following their¹² definition, that the concept of disentangled is quite similar to the concept of symmetry in physics. Physics, indeed, can be seen as an in-depth study of symmetries (see More is different from P.W.Anderson in Science which stated "it is only slightly overstating the case to say that physics is the study of symmetry")

This is quite important because, given this point of view, it is easier to define formally (i.e. mathematically) what are the properties of disentangled representations.

As stated in ¹²

Intuitively. we define a vector representation as disentangled if it can be decomposed into a number of subspaces, each one of which is compatible with, and can be transformed independently by a unique symmetry transformation

The paper¹², then goes towards defining more formally this intuition using group theory, and this concept of symmetries.

Of course, this is one point of view on disentangled representations, there are different ones, however, this is to the best of our knowledge the best formal attempt to define it.

Another important point is that this "new" definition tries to put together all the different approaches/points of view that were present in the literature at that time. The main 3 characteristics that the authors identify are: modularity, compactness and explicitness. Directly quoting from ¹²:

• Modularity "measures whether a single latent dimension encodes no more than a single data generative factor"
• Compactness "measures whether each data generative factor is encoded by a single lantent dimension"
• Explicitness "measures whether the values of all of the data generative factors can be decoded from the representation using a linear transformation"

Not all of them are explicitly required to have a disentangled representation. Particularly the explicitness characteristic, since linearity is not required to have a disentangled representation (given the definition in ¹²)

So now that we have a general overview of what we mean when we talk about disentangled representation, we can move on in understanding whether having such a representation is useful or at least is better than having a "normal" representation (i.e. without forcing any of the properties aforementioned)

Understanding whether it is useful having such a representation is also, not a trivial task and the literature is not clear on it. Most papers, claims that having such a thing is useful for three main reasons ¹³:

• more sample-efficient
• less sensitive to nuisance variables
• better in terms of generalization

This has been shown to be experimentally correct¹³, however, from a formal point of view, it is not clear why this is the case.

That is another motivation for conducting this thesis on disentangled representation to see whether these findings translate to harder and more complex settings.

Now we will proceed to show the different architectures that will be used in the thesis and we will justify the decision on each one.

Before diving into the different VAEs architecture let's take a step back and let's understand the core concept of Variational inference in Bayesian modelling. In general, Variational inference comes from Variational Calculus

The main reference of this overview is the paper ¹⁴

The core problem is to approximate a probability density that can be hard to compute or even intractable computationally.

Formally the problem can be expressed as following:

Let \(x=x_{1:n}\) be the dataset or observed variables and let \(z=z_{1:m}\) the set of latent variables The problem is to compute the conditional density of \(z\) over \(x\) \[p(z|x)=\frac{p(z,x)}{p(x)}\] Rewriting the nominator using Bayes rules we get : \[p(z|x) = \frac{p(x|z)p(z)}{p(x)}\] so \(p(x|z)\) is the likelyhood and \(p(z)\) is the prior of the latent variable. We can rewrite the evidence (or the marginal) such that: \[p(x) =\int p(z,x) dz\]

Therefore, since in the general case computing this integral is intractable, we want to find a surrogate posterior which is close enough to the real one but it is more tractable and easier to work with. We can express this surrogate as: \[q(z)\approx p(z|x)\]

Therefore to find such a surrogate, in an optimization problem framework, we first need to find how to assess the "goodness of the fit". In other words, we need to find a measure that tells us how close \(q(z)\) is to \(p(z|x)\). The most natural measure of distributions distance is the KL-divergence. This metric comes directly from Information theory (TODO explain better KL-divergence)

We can write how optimization problem in terms of the KL-divergence as follows: \[ q^*(z)=argmin_{q(z)\in Q}KL(q(z)||p(z|x))\]

\(Q\) is the family of "simple" distribution from which we sample our \(q(z)\). Note simple here just means we have an analytical form of the distribution

The KL-divergence is expressed as: \[KL(q(z)||p(z|x)) = \mathbb{E}_{z \thicksim q(z)}\left[log\left(\frac{q(z)}{p(z|x)}\right)\right]\]

As we can see we still have the intractable posterior \(p(z|x)\) We can rearrange the equation as following: (note expectation in a continuos situation it is express as an integral) \[KL(q(z)||p(z|x)) = \int q(z) log\left(\frac{q(z)}{p(z|x)}\right)\] using the aforementioned definition of the posterior we get \[= \int q(z) log\left(\frac{q(z)p(x)}{p(z,x)}\right) dz\] Now we can rearrange and we can separete the integral in two different part: \[= \int q(z) log\left(\frac{q(z)}{p(z,x)}\right)dz + \int q(z) log(p(x))dz \] Now we can see that we have two different expectations: \[= \mathbb{E}_{z \thicksim q(z)}\left[log\left(\frac{q(z)}{p(z,x)}\right)\right] + \mathbb{E}_{z \thicksim q(z)}\left[log(p(x))\right]\]

Now it is important to notice that the second expectation does not contains \(z\) therefore we can remove the expectation operation. Finally, we will do another further rearrangement to the first expectation. Specifically we will invert the numerator with the denominator, and to make it mathematically sound we need to negate it (exploiting logarithms properties) \[= -\mathbb{E}_{z \thicksim q(z)}\left[log\left(\frac{p(z,x)}{q(z)}\right)\right] + log(p(x))\]

Let us call the first expectation \(\mathcal{L}(q)\) Now we have the final form of the KL-divergence: \[KL = - \mathcal{L}(q) + log(p(x))\] \(p(x)\) is known as the marginal probability. \(log(p(x))\) is known as the evidence and it will always be negative since taking the log of something between 0 and 1 will always result in negative values. Another important point is that \(log(p(x))\) will be a constant since it does not change given the dataset (i.e. the observed variables)

The KL-divergence is by definition something positive. Therefore, \(\mathcal{L}(q)\) must be negative for the formula to have sense.

Also \(\mathcal{L}(q)\) must be smaller than the evidence (\(log(p(x))\)), therefore, \(mathcal{L}(q)\) is also known as Evidence Lower Bound (ELBO).

Finally, we also know that \(\mathcal{L}{q}=log(p(x))\) is true iff \(KL(q(z)||p(z,x))=0\)

Therefore, we just derived the ELBO and we know that it is tractable. So now instead of minimizing the KL-divergence , we can maximise the ELBO.

The optimization problem we had before was: \[ q^*(z)=argmin_{q(z)\in Q}KL(q(z)||p(z|x))\] Now, we have: \[q^*(z)=argmax_{q(z)\in Q}\mathcal{L}(q)\]

To conclude, let us rewrite the ELBO (\(\mathcal{L}(q)\)) in a more tractable for and one that you will see more often in papers and literature. \[ELBO(q)= \mathbb{E}\left[log\left(p(z,x)\right)\right] - \mathbb{E}[log(q(z))]\] Another important form is the one in terms of the KL-divergence Directly quoting from ¹⁴

Examining the \(ELBO\) gives intuitions about the optimal variational density. We rewrite the
ELBO as a sum of the expected log-likelihood of the data and the KL divergence between the
prior \(p(z)\) and \(q(z)\),

\[ELBO(q)=\mathbb{E}[log(p(x|z))] - KL(q(z)||p(z))\]

This will be the form we will use while optimizing Variational Autoencoders and its derivatives

The Variational autoencoder is a variation of the standard Autoencoder architecture. The first and crucial difference is that instead of mapping one data point to one latent point, it encodes the data point into a distribution. Therefore, transforming both encoder and decoder into probabilistic ones instead of deterministic (like in standard autoencoders)

Therefore, the encoder part instead of returning a single point it will return a mean and a variance (log variance will be used to have a more stable and reliable learning process)

Given this change in architecture, also the loss function will have to change to address the new needs. In particular, the loss function will be now formed by two different part: reconstruction error term and a regularization term. The reconstruction term will be the same as before (e.g the L₂ between the input and the output) The regularization term, on the other hand, will be the KL-divergence between the current latent space distribution and the "wanted" one.

The intuition behind the regularization term is that we want to have two properties for the latent space distribution: Continuity (two close points in the latent space must be mapped to close points in the output) and Completeness (sampling from the latent distribution must returns some "meaningful" output).

As we can see, we are entering into a probabilistic framework. Here, the previous chapter on Variational inference will become handy.

We can the decoder as \(p(x|z)\) and the encoder as \(p(z|x)\) As seen before we can express \(p(z|x)\) as: \[p(z|x) = \frac {p(x|z)p(z)}{p(x)}\]

That said, as before \(p(z|x)\) is intractable however, in this architecture, we will assume that our surrogate posterior \(q_x(z)\) is a Guassian specified by \[q_x(z)=\mathcal{N}(g(x),h(x))\] where \(g\in \mathcal{G}\) and \(h\in \mathcal{H}\). \(\mathcal{G}\mathcal{H}\) represent family of function which will be approximate by the encoder.

To find such functions we can use the last equation in the previous chapter:

\[(g^*,h^*)=argmax_{(g,h)\in\mathcal{G}\times\mathcal{H}}\mathbb{E}[log(p(x|z))] - KL(q(z)||p(z))\]

It is important to notice that \(p(x|z)\) is our decoder and therefore we will approximate by minimizing the reconstruction error.

So we can finally rewrite the above equation to also consider the decoder part (again \(\mathcal{F}\) is a family of functions): \[(f^*,g^*,h^*) =argmax_{(f,g,h)\in\mathcal{F}\times\mathcal{G}\times\mathcal{H}}\mathbb{E}\left[-\frac{||x-f(z)||^2}{2c}\right] - KL(q(z)||p(z))\]

Of course, this is only one possibility, we can change the reconstruction error accordingly to the type of data or results we want to achieve.

Some reference ¹⁵Understanding Variational Autoencoders

The Adversarial Autoencoder is a variation on the standard Autoencoder. It aims to induce some prior distribution on the latent space, semantically performing the same idea of VAE. However, this architecture exploits a completely different mechanism. It uses adversarial learning to force such distribution. It takes the idea from Generative adversarial networks (GANs) (Goodfellow et al, 2014)

Therefore, the idea is to have a discriminator network (\(\mathcal{D}\)) which tries to distinguish between the real prior distribution (\(p(z)\)) and the actual latent space distribution (\(q(z|x)\)). In an adversarial learning process, the encoder is encouraged to fool the discriminator network, therefore, bringing \(q(z|x)\) closer to the actual prior (\(p(z)\)). In this way, this architecture achieve similar results to the VAE architecture. The main advantage over the VAE is that we do not need a functional form of the prior to enforce it. We only need to be able to sample from it. The error function of this architecture is quite similar to the VAE with the main difference that instead of the regularization term (i.e. KL-divergence )we have the adversarial training procedure.

The β-VAE is a variation on the VAE architecture that slightly changes the optimization problem by mutating the objective function. In particular, it adds a hyperparameter β to the KL-divergence in order to arbitrarily force the latent space distribution to match the prior. With β = 1 we have the same formula of the VAE meanwhile, with β >> 1 the KL constraint has a higher force. In this way, following the paper ¹⁶ we will have more disentangled representations. In the same paper, they also show that β is not strictly bound from above, the only limitation is that β >= 0. Of course, with higher \betat we are also making the tradeoff between reconstruction error and similarity to the prior.

The InfoVAE was first presented in ¹⁷. This architecture tries to make more explicit the ELBO tradeoff that in other architecture are implicit. Doing so they add a new term and 2 hyperparameter α and λ. They also introduce a new term in the ELBO objective which is the amount of mutual information between \(x\) and \(z\) under \(q\). This new term should avoid that \(x\) and \(z\) are completely independent. The α hyperparameter should control this value. The λ hyperparameter, on the other side, should control the KL divergence.

Therefore the objective function is: \[\mathcal{L}_{infoVAE} = - \lambda D_{KL}(q_\phi(z)||p(z)) - \mathbb{E}_{q(z)}\left[D_{KL}(q_\phi(x|z)||p_\theta(x|z))\right] + \alpha I_q(x;z)\] where \(I_q(x;z)\) is the mutual information between \(x\) and \(z\) under the distribution \(q_\phi(x,z)\) However, it is not possible to optimize this objective. Therefore an alternative but equivalent formulation is: \[\mathcal{L}_{infoVAE} = \mathbb{E}_{p_{\mathcal{D}}(x)}\mathbb{E}_{q_\phi(z|x)}[log p_\theta(x|z)] - (1-\alpha) \mathbb{E}_{p_{\mathcal{D}}(x)}D_{KL}(q_\phi(z|x)||p(z)) - (\alpha + \lambda -1) D_{KL}(q_\phi(z)||p(z))\]

It is important to notice that this formulation of the objective capture all the previous seen autoencoders architectures.

We get the standard VAE when α = 0 and λ = 1.

We get the β-VAE when λ > 0 and α + λ - 1 = 0.

Finally, we get the AAE when α = 1 and λ = 1 and \(\mathcal{D}\) is chosen to be the Jensen Shannon divergence.

Based on (towards ) why not training the AE and RL toghether. an idea can be to mix the two objective toghether by a sum (for a trivial case) other ideas can be to scale the objective of the AE based on time another idea can be to scale the objective of the AE based on how "good" the current representation is. For example we can use on of the disentanglement metrics described in the papers . Another interesting ideas is to use some metric of the representation to guide the exploration policy of the RL agent. Something like: There are points/ areas of the latent space which we did not explore yet or that maybe we have a low "bias" (we just encounter those states just few times)

Seems that active perception is quite crucial to learn a good and usefull representation of the world! and more importantly to learn the invariant of the world. Maybe this has something to do with active learning and GFlow net by Benjo! More investigation is needed.

The project aim to build an autoencoder for dimensionality reduction. In particular, this will be used to hopefully enhance the performance of a DRL algorithm for opensim-rl simulation and to enhance the ability to generalize in different environment. In this project different type of Autoencoders will be tested.

The first hyperparameters we would like to remove is the number of neurons per layer. Since we are doing an autoencoder and therefore we are trying to find a compression function f we can assume that the number of neurons per layer is defined by some kind of function h that given the number of layers N, the numeber of dimension of the input I and the final number of dimension of the latent space Z returns the number of neurons for a specific layer. This function can be either linear or non-linear. The first intuition is that if h is linear it should be somewhat easier to learn a good compression function f. However, until now, we do not have any mathematical backgroud for this intuition! We need to do more research!

The first possible implementation of this function is defined as follows: (n is the index of the layer for which we are trying to find the number of neurons)

\[n_1 = I\] \[n_N = Z\] \[n_i = n_{i+1}*\lambda\] From these equations we can find out the equation which define the value of λ quite intuitevely. \[ \lambda = \sqrt[N-1]{\frac{I}{Z}} \] Now we can derive the number of layers given the number of neurons for the first and last layer \[ n_i = n_N * \prod_{x=1}^{N-i} \lambda \] \[ n_i= n_N * \lambda^{N-1}\] Substitute λ with the prievious found equation. \[ n_i = n_N * \left(\sqrt[N-1]{\frac{I}{Z}}\right)^ {N-i} \] \[ n_i = n_N * \left(\frac{I}{Z}\right)^{\frac{N-i}{N-1}} \] \[ n_i = Z * \left(\frac{I}{Z}\right)^{\frac{N-i}{N-1}} \]

The vanilla autoencoder is the classical one. Composed by an encoder and a decoder without any kind of constriction.

The Variational autoencoder is a modified version of a vanilla AE which forces the distribution of the latent space to be a gaussian.

Adversarial Variational Bayes is a relatively new ideas which exploits some Bayesian concept to force a particular latent space distribution. All is done in an adversarial environment.

Quite interesting if focus is on transfer learning and disentangled representations

• autoencoder dim red python
• dimredtechniques
• applications autoencoders
• reduce overfitting dim red
• disentaglement pytorch autoencoders

vbotics repo

autoencoders code repo

thesis repo

[email protected]

• Raffealla carloni
• SkypeID rafficar
• BlueJeans https://bluejeans.com/821650990 id number = 821650990

• [email protected]
• [email protected] -> Master student for dim red
• Chadan