My Learnings in ML

Ok, first blog post after a loooooooong time and the first one after baby #2. Have been wanting to catch up on readings for so long and what a better way than to write it and explain it myself. Lets begin with the model which has perhaps been beaten to death in the past few years. Word2Vec is a popular algorithm to generate word embeddings. The original algorithm by Mikolov, et al. has been proposed in the following references ( 1 and 2 ). There are two key pieces of the model: The Skip-gram model: In this model, we are given a corpus of word and its context (context for example is nearby word within a window size). The goal is to train a NN to predict the probability of every word in the vocabulary given the input word (hopefully the probability of context words would be much higher). We thus need to find the parameters that maximize the probability: argmax Π p(c|w;θ) where c is the set of contexts for the word w in the corpus The conditional probability is usually ...

Randomized SVD is a really cute technique for computing the SVD of a large scale matrix. It proceeds as follows: Consider A m x n be the large matrix. Let Q m x k k T = I A can thus be rewritten as - A ≈ QQ T A The first step is to compute the SVD of B=Q T A. As B k x n is much smaller, the SVD of B can be computed using standard methods and is B = SΣV T . Now plugging this back we have A = QSΣV T which becomes the SVD of A with U = QS. The challenge here is constructing the orthogonal matrix Q efficiently. This is done as follows: Compute a Gaussian random matrix Ω n x k . Compute Y m x k = AΩ. Compute the QR decomposition of Y to get the orthonormal matrix Q. The matlab code is as follows: O = randn(n, k); Y = A*O; [Q, R] = qr(Y, 0); B = Q'*A; [S sigma V] = svd(B); U = Q*S;

This is one of the beautiful ideas that came across recently while trying to look for something that works well for dimensionality reduction. It is a very simple technique yet works beautifully. It is as follows- Reduce the given data matrix X d x N = R k x d X d x N The core idea behind the entire field is that of Johnson Lindenstrauss Lemma that says that the points in the high dimensional space can be mapped into a low dimensional space that preserves the original structure with a high probability. The matrix R k x d is the random projection that reduces the data into k dimensional subspace. The initial result showed that R can be generated from a Gaussian distribution consisting of k orthogonal random vectors. Later on, it was shown that the Gaussian distribution can be replaced with a much simpler distribution such as generate +1,-1 with probability 1/2 or even generate 0, -1 and +1 with a probability 2/3, 1/6 and 1/6 respectively . This translates the multiplication in...

t-SNE is a non-linear dimensionality reduction technique that is well suited as a visualization technique as its goal is to reduce the dimensionality to 2 or 3 dimensions. The ideal goal of visualization is to build a map in low dimensional space that reflects the similarities in the original space. Popular dimensionality reduction techniques like PCA are not very useful for this purpose because the goal of PCA is to maximize variance which is the same as trying to minimize the squared error between distances in the original data and the map and hence this leads to preserving large pairwise distance in the map. However large pairwise distances are not always reliable and on the other small distances between neighbors is reliable. Techniques relying upon preserving neighboring distance are Isomap, LLE, SNE and t-SNE. t-SNE is based upon the SNE (stochastic neighbor embedding) algorithm and places a Gaussian around every point in the high dimensional space and then measure the density ...

SVD is a popular approach for factorization of a matrix and has several applications in many domains. It proceeds by factorizing a given matrix A m x n as A = UΣV^T, where U is a m x m unitary matrix, i.e. U^TU=I, Σ is a m x n diagonal matrix consisting of the eigenvalues and V is a n x n unitary matrix. It is popularly used to find the rank k approximation of a given matrix. One of the main problems of using SVD for large matrices is the computation of the eigenvector decomposition. Lets see how the eigenvector decomposition can be carried out for large sparse matrices. Power Iteration : One of the simplest methods of computation of the largest eigenvalue of a large sparse matrix is the power iteration. It however only computes a single largest eigenvalue and may converge very slowly. The algorithm is as follows: Start with a random vector b0 b_{k+1} = Ab_k || Ab_k|| This algorithm converges to the largest eigenvalue under the assumption that th...

The kmeans algorithm is one of the most popularly used algorithms in clustering. However, one of the main problem of the algorithm is the initialization of the seed points. Random initializations is generally used and it can sometimes lead to a clustering arbitrarily worse than the optimal clustering. Further it can cause much slower convergence to the final result. The kmeans++ algorithm comes to our rescue in such cases. The kmeans++ paper was published in 2007 and so far has more than 850 citations. It provides a very cute method to initialize kmeans. The idea is as follows: Instead of picking up random cluster centres, how about picking the farthest point from the chosen cluster centres ? The problem with this approach is that it will result in picking up outliers as cluster centres. Instead, we want to pick cluster centre from the next dense group of points. So here are the two steps for the algorithm - Pick the first cluster center at random. Choose the subsequent cluster c...

Hola, I'm back! Was on a hiatus post baby and now I will try to write more regularly. So, lets get started. The multi-armed bandit problem was formulated in the 50s and is as follows: Suppose there are N slot machines (arms) and the player has to decide which machine to play. Each machine has an unknown probability of distributing a reward and the player has to decide which machines to play and in what order in order to maximize the reward. Note that the probability of reward generation of each machine is unknown otherwise the reward is maximized by simply picking up the machine with the largest probability. This problem has huge applications. For example, ad recommendation, news recommendation, in a clinical trial while trying to come up with the best treatment or in the portfolio management of the stocks. The problem of choosing the best arm is complicated by the stochastic nature of the slot machines. A sub-optimal machine could generate a reward by random chance and similarly...