{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Why random Linear layer works\nYou could have noticed, that in [baseline kernel](https://www.kaggle.com/code/andrefaraujo/pytorch-baseline-submission/notebook) the author uses Linear layer to map the embeddings to lower dimentional space of 64.\n   \nEven though they dont get a very high score, still isnt it surprising? Supposedly random matrix multiplication gives some not-random result at the end. In this notebook I will try to explain whats happening, why it works and how it can be useful for this challenge.","metadata":{}},{"cell_type":"markdown","source":"## Random Projections and Johnson-Lindenstrauss\n\nLets take a look at one of probably best known examples of (supervised) dimention reduction - PCA. Quote from Wikipedia:\n\n    PCA is defined as an orthogonal linear transformation that transforms the data to a new coordinate system such that the greatest variance by some scalar projection of the data comes to lie on the first coordinate (called the first principal component), the second greatest variance on the second coordinate, and so on.\n    \nThe PCA choses the directions of coordinate system by minimizing the\n$$\nw_{k} = \\text{argmax}_w \\left\\{ || \\hat{X}_k w ||^2 \\right\\} = \\text{argmax} \\left\\{ \\frac{w^T \\hat{X}_k^T \\hat{X}_k w}{w^T w} \\right\\}\n$$\n\n$$\n\\hat{X}_k = X - \\sum^{k-1}_{s=1} X w_{(s)} w_{(s)}^T\n$$\n\nand it works well if we have enough data points to estimate good direction, that why its so popular. You can see that for PCA we actually optimize the $w$ vector, which represents the direction in space over dataset.  \n\nIn the challenge however there are no data provided so naturally the question arises. What can we do, when we have no access to any form of data? Well, the easiest way to go is to chose the direction randomly.\n\nThats where the random projections come in. The general idea is very straight forward! Just randomly select group of vectors and use them as a projection matrix to extract features, hoping that some of the directions will be good.  In other word the vector $w$ is to be sampled from some distribution.\n\nThe most common method of random projections is Gaussian Random Projections. The random projection matrix is generated using a Gaussian distribution. The first row is a random unit vector uniformly sampled from the sphere $S^{d-1}$, the next vector is a unit vector orthogonal to the first one and so on. The implementation for that, and other methods can be found in [sklearn](https://scikit-learn.org/stable/modules/random_projection.html).\n\nEssentially that is happening, when you are adding the **Linear layer** to the end of pre-trained feature extraction network. Since weights are sampled randomly, you are randomly selecting the direction in the space of features for the projections. The main theoretical result behind the efficiency of random projection is the **Johnson-Lindenstrauss** lemma (quoting Wikipedia):\n    \n    In mathematics, the Johnson-Lindenstrauss lemma is a result concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved. The map used for the embedding is at least Lipschitz, and can even be taken to be an orthogonal projection.\n    \nThe result states, that using **Gaussian Random Projection** you can hope to keep the relative distances in the projected space ( this is exactly what we want, considering that the championship is evaluated by knns ), up to some distortion threshold. You can even calculate, how much components you need for given level of distortion in the projected space by the formula\n$$\n\\text{n}_{\\text{components}} \\geq 4 \\frac{\\text{ln}(\\text{n}_\\text{samples})}{ (\\epsilon^2 / 2 - \\epsilon^3 / 3)}\n$$\nFor visualisation and more on the minimal necessary dimention for given distortion thershold adress the [sklearn page](https://scikit-learn.org/stable/modules/generated/sklearn.random_projection.johnson_lindenstrauss_min_dim.html#sklearn.random_projection.johnson_lindenstrauss_min_dim).\n\nThis intuition can help us to improve a little bit on the result of random projections, since the actual Linear layer is not initialized by gaussian distribution and does not have the unit length, by expilistly making it so we can hope to get a slightly better results. I have tested different methods to pool the features. Lets take a look at the results with the [inception](https://pytorch.org/hub/pytorch_vision_inception_v3/) network v3 from pytorch library \n* Features From Inception + MaxPool - 0.089\n* Features From Inception + AvgPool - 0.130 \n* Features From Inception + L3Pool - 0.116\n* Features From Inception + SumPool - 0.130\n* Features From Inception + RandomProjection - 0.172\n* Features From Inception + GaussianRandomProjection - 0.174\n\nIn this case, the random Linear layer performed even !!better!! then Average Pool method.\n\nAs a **Conclusion** i would say that if you are pooling the high-dimentional vector into small dimentional space of 64, consider doing it by Random Projections. Gaussian Distribution are just one of possible ways of performing this method and even though I have not tested all of them, maybe there are a random projection method that will boost your leaderboard score.\n\nTo read more on the topic, you can look at:\n* [Wiki for PCA](https://en.wikipedia.org/wiki/Principal_component_analysis)\n* [Wiki for RandomProjections](https://en.wikipedia.org/wiki/Random_projection)\n* [Sklearn RandomProjections](https://scikit-learn.org/stable/modules/random_projection.html)\n* [Paper, proposing possibly more effiecent method, then gaussian](https://www.researchgate.net/publication/322547028_Data-independent_Random_Projections_from_the_feature-map_of_the_Homogeneous_Polynomial_Kernel_of_degree_two)","metadata":{}}]}