<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Paarth bhatnagar on Medium]]></title>
        <description><![CDATA[Stories by Paarth bhatnagar on Medium]]></description>
        <link>https://medium.com/@paarthbhatnagarh3h3?source=rss-e6355a0f9843------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*uDQmpyANksgVoVFNRyR3-g.jpeg</url>
            <title>Stories by Paarth bhatnagar on Medium</title>
            <link>https://medium.com/@paarthbhatnagarh3h3?source=rss-e6355a0f9843------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 02:22:18 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@paarthbhatnagarh3h3/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Attacking Machine Learning models: The Fast Gradient Sign Method.]]></title>
            <link>https://medium.com/@paarthbhatnagarh3h3/attacking-machine-learning-models-the-fast-gradient-sign-method-50b9652575cd?source=rss-e6355a0f9843------2</link>
            <guid isPermaLink="false">https://medium.com/p/50b9652575cd</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[calculus]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[linear-algebra]]></category>
            <dc:creator><![CDATA[Paarth bhatnagar]]></dc:creator>
            <pubDate>Wed, 08 Feb 2023 11:49:47 GMT</pubDate>
            <atom:updated>2023-02-08T11:49:47.466Z</atom:updated>
            <content:encoded><![CDATA[<p>“Adversaries” literally means one’s opponent in a contest, in the case of machine learning models, noisy data can often act like this adversary. Let’s try and understand adversaries by using a straightforward example of a logistic regression model.</p><p>We will use sklearn.datasets to generate dummy data and PyTorch to build our logistic regression model.</p><pre># Importing nessecary libraries<br>import torch<br>import random, os<br>from torch import nn<br>import numpy as np<br>import torch.nn.functional as F<br>import seaborn as sns<br>from sklearn.datasets import make_blobs<br>import matplotlib.pyplot as plt</pre><p>Setting up fixed seeds for reproduction.</p><pre>torch.manual_seed(42)<br>np.random.seed(42)<br>random.seed(42)</pre><p>Now we generate data using the make_blobs() functionality present within sklearn’s dataset module. We generate 500 with 2 features. We will also convert the Numpy array generated from make_blobs to a torch tensor.</p><pre>def generate_data(n_samples = 500):<br>  X, y = make_blobs(n_samples = 500, <br>                    n_features = 2, <br>                    centers = 2, <br>                    cluster_std = 2, <br>                    random_state = 42)<br>  X = torch.tensor(X, dtype = torch.float32)<br>  y = torch.tensor(y, dtype = torch.float32)<br>  return X, y<br>X, y = generate_data()</pre><p>The generated data should look something like this:-</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*IG0hAkhpAoFZuZBuVOx4Fg.png" /><figcaption>Scatter plot of the generated data.</figcaption></figure><p>To define our model now, we basically need a (2, 1) dimensional tensor of random numbers that would get trained during optimization in our model.</p><pre># lr is too high but the model converged at that.<br>def train_model(X, y, <br>                loss_fn = None, <br>                activation = None, <br>                epochs = 2000, lr = 12):<br>    w = torch.randn((2, 1), dtype = torch.float32, requires_grad = True)<br>    b = torch.randn(1, dtype = torch.float32, requires_grad = True)<br>    for _ in range(epochs):<br>        output = activation((X @ w) + b)<br>        loss = loss_fn(output, y.unsqueeze(dim = 1))<br>        w.grad = None<br>        b.grad = None<br>        loss.backward()<br>        w.data = w.data - lr * w.grad.data<br>        b.data = b.data - lr * b.grad.data<br>    print(f&quot;The model achieved a loss of {loss}&quot;)<br>    return w, b<br><br>act = nn.Sigmoid()<br>loss_fn = nn.BCELoss()<br>w, b = train_model(X, y, loss_fn = loss_fn, activation = act)</pre><p>The model should achieve a low loss at this point converging at around 0.018, and the decision boundary should look like this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/374/1*IH6LKuZMwjMx1uVH8z7atQ.png" /><figcaption>Decision boundary of Logistic regression model.</figcaption></figure><p>If we observe the decision boundary closely, there are some points that are misclassified by the model, some that lie relatively close to the decision boundary, and finally some points that are pretty well classified.</p><p>Our focus lies on points that lie relatively close to the decision boundary, if these points were to be given a little “shake” towards the decision boundary by adding some random noise to them, they would be misclassified by our model. It turns out that linear classifiers like logistic regression and nonlinear classifiers like neural networks do not respond well to these shakeups. Neural networks in high dimensions can sometimes become too localized to a certain class of examples, it&#39;s like they have built up a <a href="https://en.wikipedia.org/wiki/Potemkin_village">Potemkin village</a> that responds well to naturally occurring data but is exposed as fake when one visits data points with a low probability of occurring.</p><p>Now, the question arises how do we generate such adversarial examples to expose such Potemkin villages?</p><h3>The Fast Gradient Sign Method (FSGM)</h3><p>The FSGM method proposed by Goodfellow et al (<a href="https://arxiv.org/pdf/1412.6572.pdf">paper</a>) addresses this exact problem of preparing our model against such adversaries. It addresses the problem of generating adversarial examples for our model which can be used to make it more robust.</p><p>While training a machine learning model, we tend to optimize the weights of the model. These weights in the case of neural networks are optimized using backpropagation which involves taking the gradient of the loss function with respect to the weights. In other words, this gradient tells us the values that we need to subtract from our weights to make the loss lower, which in turn makes our model better.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*c3CTZYWTrlEbKPJZUyux2w.gif" /></figure><p>If we can calculate the gradient of the loss with respect to the weights, then we can calculate this gradient with respect to the inputs too. This would give us values that when added to our original inputs increase the overall loss of the model. This was the exact idea proposed by the authors.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/697/1*Q6_PWu8vpk3nnh2MUEOqkw.png" /></figure><p>The image above is taken from the FSGM paper, the model predicts that the input is a panda with a confidence of 57.7% which is pretty low. This low confidence in prediction means that this image lies fairly close to the decision boundary in a higher dimensional space, so if we were to push it a little bit closer to the decision boundary by perturbing it, the model would misclassify this as something else, which in this case turns out to be a gibbon with a confidence of 99.3%.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/186/1*f4t_Gb1wai-D0u0JKDn3jA.png" /><figcaption>The gradient of loss w.r.t input</figcaption></figure><p>The authors calculate the sign of the gradient of the input image with respect to the loss function. This gives us values that when added to the original input will increase the loss function and henceforth give us an adversarial example. <strong>Note</strong>: The perturbation is scaled down by a factor of 0.007 in the panda example.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/297/1*FVrjzoHqYBDDsyegY3wJ2A.png" /><figcaption>The general formula to generate adversarial examples using FSGM</figcaption></figure><p>The purpose of taking the sign of the gradient is that the sign function has a derivative of zero or undefined everywhere, this makes it impossible for models like neural networks to anticipate how the perturbations in inputs might occur. The epsilon here controls the intensity of the FSGM attack by scaling the sign of the gradients up or down. The higher the epsilon value, the higher the intensity of the attack, and the higher the increase in loss when the model is evaluated on these adversarial examples.</p><h4>FSGM in action</h4><p>Let’s look at how we can generate adversarial examples for our logistic regression model from before and attack our model using that data. The code to generate adversarial examples is as simple as setting the requires_grad attribute for the input tensor to True. This will calculate the gradients for the input examples during backpropagation.</p><pre>def generate_adversarial_examples(X, y, w, b, loss_fn, activation, epsilon):<br>    # Set requires_grad for input to True<br>    X.requires_grad = True<br>    outputs = activation((X @ w) + b)<br>    loss = loss_fn(outputs, y.unsqueeze(dim = 1))<br>    loss.backward()<br>    X_adv = X + epsilon * (torch.sign(X.grad.data))<br>    return X_adv<br>X_adv = generate_adversarial_examples(X, y, w, b,<br>                                      loss_fn,<br>                                      activation = act, <br>                                      epsilon = 0.7)</pre><p>We can look at how the newly generated adversarial examples are spread around the old model’s decision boundary using a scatter plot.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/747/1*VpTRVxQFPrq9DVMwpSCUnA.jpeg" /></figure><p>We see how the FSGM attack on the original data has caused some points to shoot off from their original places. The loss of the model increases from around 0.018 to 0.07. <strong>Note</strong>: These numbers might vary due to random weight and bias initialization while training the model.</p><h3><strong>Key points and Takeaways</strong></h3><ol><li>While training machine learning models we encounter noisy data and the Fast gradient sign method provides us a way to evaluate models on these perturbations.</li><li>FSGM is used to generate adversarial examples by calculating the gradient of the loss with respect to the inputs.</li><li>The sign of this gradient gives us values that when added to our original data will increase the loss and henceforth give us adversarial examples.</li><li>These examples can be used to make the model robust against such perturbations. This is called adversarial training, which I plan to cover in upcoming blogs.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=50b9652575cd" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[From Projections to The Principal Component Analysis]]></title>
            <link>https://medium.com/@paarthbhatnagarh3h3/from-projections-to-the-principal-component-analysis-302fdc607085?source=rss-e6355a0f9843------2</link>
            <guid isPermaLink="false">https://medium.com/p/302fdc607085</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[linear-algebra]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Paarth bhatnagar]]></dc:creator>
            <pubDate>Wed, 27 Apr 2022 06:32:46 GMT</pubDate>
            <atom:updated>2022-04-27T08:39:28.335Z</atom:updated>
            <content:encoded><![CDATA[<p>The occurrence of an event might not be always explained by all the factors associated with it. The event might have occurred only due to a few core reasons or maybe the event might have occurred due to several reasons each contributing its share. When we try to model real-life problems with data, the data might be unusually large in size having a lot of variables (also called features).</p><p>The core idea behind principal component analysis is to combine these variables into a lower-dimensional variable in such a way that it does not decrease the “information” provided by the original set of variables drastically. This in turn reduces the dimensionality of the data and leads to an improvement in overall computation time.</p><p>Although we will not get into serious math in this article the reader is still expected to have a basic understanding of vectors, matrix multiplication, eigenvalues, and eigenvectors. We start by exploring the idea behind vector projections, variance, and covariance and then lead up to the principal component analysis.</p><h3>What are projections?</h3><p>Let X (yellow) and Y (blue) be two vectors in a vector space shown in the animation below. The projection of X onto Y can be thought of as a perpendicular shadow of the vector X on Y. Why the perpendicular shadow? If we take a close look, we will find that this perpendicular projection is the one that minimizes the “error” that occurs when projecting.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*lHYIMCbBQcm0AIsElcQosg.gif" /><figcaption>Vector Projections</figcaption></figure><p>This error is represented by the white line in the animation. The resultant vector in Z (in Pink) is the projection of X on Y. The vector Z is just a scaled-down version of the vector Y. One thing to note is that if we try to project a vector onto itself, the projection would be that vector itself.</p><p>The general formula for projection of a vector onto another vector is given by:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/374/1*QEltiWd4BVKVfAdcxcMImA.png" /><figcaption>Eq1: Projection of a vector onto another vector.</figcaption></figure><h3>Variance and Covariance</h3><p>The variance can be thought of as a measure of how much that data is spread around its mean. If we have a set of observations, let’s say [-1,0,1], this dataset has a mean of 0 and a variance of 1 as it is spread with a magnitude of 1 around both sides of its mean. The variance is only defined in one dimension and can be calculated using the following formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/283/1*8zmr3QAPB7c33Fn334D0dQ.png" /><figcaption>Eq2: Formula to calculate variance.</figcaption></figure><blockquote>Note: The above formula is defined for what we call the population variance, there is something called <a href="https://www.cuemath.com/sample-variance-formula/">sample variance</a> too, which is essentially the variance of a subset of data and involves taking N-1 observations in the denominator instead of N. In this article, we will be dealing with population variance and population covariance everywhere.</blockquote><p>In higher dimensions, to capture the co-variability of the data we define something called the covariance. The covariance captures the relationship between each pair of dimensions in our data. If we take an example of the case given below, to capture the variability of how the data in the x-component jointly varies with the data in the y-component we need to calculate the covariance of x with y.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/193/1*GKHNtD6zt9HdBlvt-CwFrQ.png" /><figcaption>Example: Data</figcaption></figure><p>If Cov(x, y) is a large positive number, they have a strong positive covariance, which in turn means as x increases y increases too. If the Cov(x, y) is a large negative number, they have a strong negative covariance, which in turn means as x decreases y decreases too. If the covariance is very close to 0, there is not much evidence of any kind of relationship between x and y.</p><p>The covariance of a dataset can be calculated using the following formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/322/1*Ew_TotG4Tg4-Y72isLbM4A.png" /><figcaption>Eq3: Formula to calculate covariance.</figcaption></figure><p>The variance is just the covariance of a specific component with itself. This notion further helps us define the covariance matrix. The covariance matrix is a square symmetric matrix that contains the covariance of each pair of dimensions present in the data. The case below is the covariance matrix when the data is 2 dimensional. The matrix has the variance of each dimension along its diagonal.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/201/1*LCYYCllXtpD-G6HFI7_YnA.png" /><figcaption>Example: 2D Covariance Matrix.</figcaption></figure><p>The covariance matrix in a general case is an NxN where N is the dimensions in our data and can be calculated using the formula below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/617/1*g2XoWxyALuS4BJlfcnRODw.png" /><figcaption>Eq4: Formula to calculate The Covariance Matrix.</figcaption></figure><h3>What is dimensionality reduction?</h3><p>If you were to transport a file so large in size that no ordinary storage device could store it you would naturally have to find a way to reduce its size in such a way that you lose as less information as possible while doing so. The idea behind dimensionality reduction also follows along the same line. Data can be represented as a matrix and this matrix can be multiplied with another matrix that projects our data onto a lower dimension. From this lower-dimensional representation of our data, we try to reconstruct our original data. The difference between the original data and the data reconstructed from the lower-dimensional representation is called the reconstruction error. The goal is to minimize this reconstruction error.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/794/1*UkhG4CZTmJgbnbpRTSP3_A.png" /></figure><h3>The idea behind PCA</h3><p>The idea behind PCA can be formulated in two ways, minimizing the reconstruction error or maximizing the variance of our data points on the lower dimension we project it onto.</p><h4>1. Minimizing the reconstruction error</h4><p>Our data lies in a higher dimension than what we project it onto. We want to project in a way that when we try to get back to the original data there is as less error as possible between the original representation and the reconstructed one. For example, in the figure below we have 2-dimensional data and we try to project it onto a 1-dimensional line.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/988/1*_aY-mVQYqIhY4mfo4mP36g.png" /></figure><p>If we choose the line in the first case we see that the data points tend to lie really far away from their projected counterparts, this would in turn mean that when we try to reconstruct our original data from the 1-dimensional representation there would be a lot of error in this case. If we choose the line in the second case, we see that the data points tend to lie comparatively close to the line we are projecting onto, this would in turn mean that when we try to reconstruct our original data from the 1-dimensional representation, the error would be less than the one in the first case, and that is exactly what we want to minimize this error.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/455/1*S7o4d0G08kFg0TCsQB8gDw.png" /><figcaption>Eq5: Minimizing The Reconstruction Error.</figcaption></figure><p>This then turns into an optimization problem in which we minimize the function which spits out the reconstruction error. Although we won’t get into the math here the reconstruction error turns out to be minimized along the eigenvectors corresponding to the largest eigenvalues. We explore this idea of projection along eigenvectors with the largest eigenvalues in the next part.</p><h4>2. Maximizing the variance</h4><p>When we have a dataset with a lot of features it is not possible to explore all those features visually and try to find the most important ones.</p><p>Reducing the dimensions of the data can also be thought of as combining certain features of the data to make a new feature along a lower dimension that preserves as much information as possible about the original data. These new combined features are called the principal components of the data. The goal is to find these principal components so they preserve as much information as possible.</p><p>Looking at the example below, there are a bunch of 2-dimensional points and the data tends to follow an increasing trend. We project those points onto a 1-dimensional line to give us a new feature. In the first case, when we project the data onto the 1-D line and see that line individually we get to know almost nothing about the original data, the information that the data was following an increasing trend is lost.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1rtllXTTOMq3d6b-JKeKZA.png" /></figure><p>In the second case, we see, when we project the data onto the respective 1-dimensional line, the projected data seems to be well spread out on it and if we look at the 1-D line individually we are able to see that the projected data to seems to follow an increasing trend too, but now we just need 1-dimension instead of two to explain it. The principal component in the second case seems to capture the “variance” in our original data much better than the principal component in the first case.</p><p>How do we find these principal components? We want to project the data onto a lower-dimensional representation “u_1”, such that the variance of the data is maximized, here “u_1” is a unit vector. Firstly, we center our data around the origin by subtracting the mean vector from each data point.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/513/1*2ZIhc8Z186ln9FDr6IkOnQ.png" /><figcaption>Example: Mean centering data (3D Case) can be extended to N-dimensions.</figcaption></figure><p>Now we use the formula for projections we saw earlier to project data onto a hypothetical principal component “u_1”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/245/1*edB1ylpSledPDy96AduCtw.png" /><figcaption>Eq6: Projection of v onto u_1</figcaption></figure><p>Since u_1 is a unit vector here the term uTu would be the norm of that vector which in the case of unit vectors is 1. Now that the data has been projected we need to maximize its variance. Maximizing the variance just means the magnitude by which we scale our unit vector u_1 while projecting. The variance is given by:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/527/1*B9OQ3jDugaB5DhrvohNUNg.png" /></figure><p>If we look closely, the thing we see in the middle is vTv, and since our data already has a mean of 0 this vTv would turn out to be the covariance matrix!. This then turns into an optimization problem in which we maximize the variance with a given constraint that the norm of u_1 remains to be 1. Turns out solving this maximization problem gives us the following equations along which variance is maximized.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/503/1*t7PyshE9qVBTUWog8dDaYA.png" /><figcaption>Maximization problem.</figcaption></figure><p>The lambda here corresponds to the eigenvalue and since this was a maximization problem this tells us that the variance is maximized along the eigenvectors.</p><p>If we left multiply uT we see that the variance is equal to the eigenvalues and hence we choose the eigenvectors corresponding to the largest eigenvalues to maximize the variance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/154/1*EylUl6zdQiknG3phKw44mw.png" /></figure><p>Here we just found out the principal component 1, likewise, we can find out more principal components by extracting the subsequent eigenvalues and eigenvector pairs. Since the covariance matrix will always be symmetric these principal components will always be orthogonal to each other.</p><p>Although we don&#39;t explore the math behind minimizing the reconstruction error in this article the formulation of PCA in which we minimize the reconstruction error and the formulation in which we maximize the variance are one and the same. Solving the minimization problem of reconstruction error and maximization problem of variance gives us the same results.</p><h3>Conclusion</h3><p>In this article, we started by exploring the idea behind projections, variance, covariance, and dimensionality reduction. We then saw how PCA helps in reducing dimensions of our data whilst preserving maximum information by finding these “principal components” of the data. We saw that the idea behind PCA can be formulated in two ways, minimizing the error between our dimensionally reduced and our original data and then how maximizing the variance of data while projecting it onto a lower-dimensional representation would give us the same results.</p><p>The algorithm behind PCA can be summed up in the following points:</p><ol><li>Centering the data: Finding out the mean vector of the data and subtracting it from each data point.</li><li>Finding out the covariance matrix of the data.</li><li>Eigen Decomposition: Finding out the largest eigenvalues and the corresponding eigenvectors of the covariance matrix.</li><li>Projection: Projecting the data onto the eigenvector corresponding to the largest eigenvalue. This gives us the corresponding principal component of the data.</li></ol><h4>Further Readings and videos</h4><ol><li>The math behind <a href="https://www.youtube.com/watch?v=9EgXm_CtfBg">minimizing reconstruction error</a>.</li><li>The principal component analysis <a href="https://www.youtube.com/watch?v=FgakZw6K1QQ">explained visually</a>.</li><li>Interactive article explaining <a href="https://setosa.io/ev/principal-component-analysis/">PCA</a>.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=302fdc607085" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to retrieve a number — really, really fast.]]></title>
            <link>https://medium.com/@paarthbhatnagarh3h3/how-to-retrieve-a-number-really-really-fast-bf4340d88431?source=rss-e6355a0f9843------2</link>
            <guid isPermaLink="false">https://medium.com/p/bf4340d88431</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[data]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Paarth bhatnagar]]></dc:creator>
            <pubDate>Fri, 26 Nov 2021 06:35:57 GMT</pubDate>
            <atom:updated>2021-12-06T15:08:55.979Z</atom:updated>
            <content:encoded><![CDATA[<h3>How to retrieve a number really, really fast — The Quickselect Algorithm.</h3><p>Let’s say you are given a bunch of random numbers and for some reason, someone asks you to find the 4th smallest number amongst them. A very obvious method one can think of is to arrange those numbers in a sorted manner and then retrieve the 4th smallest number. In fact, sorting those numbers out would help us retrieve any kth smallest number.</p><p>Maybe this method is feasible for a bunch of 5 random numbers or even 10 random numbers but as we start taking more and more numbers it takes more and more time to sort these numbers. So, the question now is can we find a way in which we can retrieve this kth smallest number without sorting? Can we in a sense do a laparoscopy of this array to retrieve out this number as well as keep the process of doing so really really fast?</p><p>Here is an array containing 7 numbers arranged in an unsorted manner.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/688/1*aVydxYGOFiRUiBFsWIA88Q.png" /><figcaption>The unsorted array.</figcaption></figure><p>For example, we want to find the third-smallest number in this array without sorting it. Let’s start by taking any random number from this array. We choose 10. What we will now do is compare 10 with every other number in this array. If 10 is greater than that number we will add that number to a new array called left partition and if 10 is less than that number we will add it to another array called right partition.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/614/1*J0iMp-sQeBTu6WIJ1J6vow.png" /></figure><p>This step leads to something really interesting, if we see carefully the position of 10 now it is exactly greater than 3 elements and exactly lesser than 3 elements in our array. In other words, we can now confidently say that 10 is the 4th smallest number in our array.</p><p>Still, what is the third-smallest number? Since we now know that 10 is the 4th smallest number in our array, we can confidently say that the 3rd smallest number would be a number lesser than 10. We can now take go back to our old left partition and repeat this process of finding the 3rd smallest number within that subarray. We will discard the right partition here as it is of no use to us now. We randomly choose 4 and do the partitioning of our array once again.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/515/1*Hb4t_Z2-tWXrto8u9BKdRQ.png" /><figcaption>New Partitioning</figcaption></figure><p>As 9 is greater than 4 it goes into the right partition and 1 being lesser goes into the left partition. So, now 4 is lesser than exactly one number and greater than exactly one number. This makes 4 the 2nd smallest number. Since we have to find the 3rd smallest number, that number has to be greater than 4 and there is only one number left that is greater than 4 which is 9 in our right partition. So, there it is, 9 is the 3rd smallest number in our original array and we didn&#39;t even have to sort our array to find it.</p><p>This algorithm can be generalized in form of this pseudocode given below. We describe a method called Find which accepts an array and a kth value we want to find. Note: We assume zeroth indexing here.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/1*5EJ5YA2DwkU_u2NLY3qkTA.png" /><figcaption>The Pseudocode</figcaption></figure><h3><strong>Calculating the Efficiency of this Algorithm.</strong></h3><p>Now that we have a method to find the kth smallest number we desire, the question of whether this method is any better than the obvious method of sorting and finding or not comes up. The fastest way possible to sort an array has an efficiency of about Nlog(N). Here, N is the number of elements in our array. So, if we beat Nlog(N) we can confidently say that our method is definitely faster.</p><p>Imagine a strip of paper that is 1 unit long, if we divide our strip exactly at the 1/4th unit and the 3/4th unit this would give us the central region of this strip. Now let’s throw a ball and observe the probability of that ball landing in the central region of this strip.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/390/1*RaWd_rO_Md2fBhQ8yldazw.png" /></figure><p>The area of the central region is 1/2, dividing it by the total area of the strip gives us the probability of a ball falling in the central region to be 1/2. In other words, we can also say that if we get 2 chances to throw a ball, there is a high probability that it will land in the central region in at least one of those 2 throws.</p><p>Let’s carry forward this strip analogy to our array. The idea of choosing a random number every time in our array is like throwing a ball. Whenever a random number is selected we know the probability that the number lies in the central region is 1/2. This means there is a high chance that the number will be greater than at least 1/4th or lesser than at least 3/4th of the numbers present in that array.</p><p>When we do the process of partitioning, we compare the chosen number with every other number. When this is done we have a left partition and a right partition. Given we haven’t found our kth smallest number yet, we then go on to choose a number in one of those partitions and discard the other partition. Since we know that the chosen number has a very high probability of being greater than at least 1/4th or lesser than at least 3/4th of the numbers present. This tells us that the probability of one of those left or right partitions being at least 3/4th the original array is 1/2. This means on average, our original array gets shrunken down to 3/4th its original size every time we choose a random number.</p><p>Now, let’s calculate how efficient this method is.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/719/1*Nmbigop0YSzQeKPhqw8wUA.png" /></figure><p>The sum of the infinite series shown above comes out to be 4N. This means that the time it takes for our algorithm to find the kth element increases linearly as the size of our array gets bigger and bigger. In more formal terms, our algorithm has a time complexity of O(N). O(N) is definitely more efficient than O(NlogN), this, therefore, proves that this algorithm is definitely better than sorting and finding.</p><p>This algorithm was discovered in 1962 by the British computer scientist, Tony Hoare. It is also called Hoare’s selection algorithm. This algorithm works like a charm even when the array sizes are going up to a billion. It’s quite a simple idea and yet leads to such an elegant result.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bf4340d88431" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An introduction to Markov’s and Chebyshev’s Inequality.]]></title>
            <link>https://medium.com/@paarthbhatnagarh3h3/an-introduction-to-markovs-and-chebyshev-s-inequality-1cd09377bfb0?source=rss-e6355a0f9843------2</link>
            <guid isPermaLink="false">https://medium.com/p/1cd09377bfb0</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[mathematics-education]]></category>
            <category><![CDATA[manim]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Paarth bhatnagar]]></dc:creator>
            <pubDate>Mon, 27 Sep 2021 17:29:50 GMT</pubDate>
            <atom:updated>2021-09-27T17:31:27.896Z</atom:updated>
            <content:encoded><![CDATA[<p>It’s normal as a living creature to encounter inequalities, one might overpower another, one might outwit another, there are numerous examples to explain so. Well, guess what, there are inequalities in data too. Although, these are a little different than the ones we are used to. This is a gentle introduction to two of those inequalities.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*Kli2s6Q-RbdwHTaHI0Tuzw.gif" /></figure><p>Let’s consider an event of going to a store to buy chocolates, there are “n” number of stores that I can go to and for each store, I can have two possibilities:<br>1. There is chocolate available.<br>2. There is no chocolate available.</p><p>In probability theory, the probability of any event occurring can be mapped to the range of [0,1]. So, if I say that the probability that I visit a store that has chocolates is 0.5, it means that out of all the shops I visit there is a 50% chance of chocolate being available on it and likewise a (1–0.5) or a 50% chance of chocolate not being available on it. We denote these events of going to a store by something called a random variable. In our case let’s consider it to be X.</p><p>Since I am visiting “n” number of stores and for some reason, if I have infinite stamina the number of stores I visit can range from {0 — &gt; infinity}, that means I can visit {0 shops, 1 shops, 2 shops, …, infinite shops}.</p><p>These probabilities are easy to calculate for a small value of “n” and can be modeled by using a Binomial Distribution. But as the value of “n” increases, it’s nicer to have a “bound” of these probabilities. For example, if I wanted to know what is the probability that if I visit 200 stores out of those 200 stores what is the probability that I will get chocolates on at least 145 stores, that would be P(X is greater than or equal to 145) which will come out to be 0.689, This means that there is at least 68.9% chance that I will get chocolate on 145 or more number of stores.</p><p><strong>Markov’s Inequality<br></strong>The example above was a demonstration of how we can use Markov’s Inequality to calculate certain “Bounds” on probabilities. Bounds can be thought of as barriers to the probabilities of certain events occurring.<br>Markov’s inequality can be calculated using the formula given below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/145/1*qVDuYQXD22jdckfb8_lL9w.gif" /><figcaption>Markov’s Inequality.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*1aNZGUcnhLA27TQkezJIzA.gif" /><figcaption>“Bounds on Values our Random Variable takes”</figcaption></figure><p>Here, E[X] is the Expected value of our random variable X. Expected value can be described as a long-term average of a random variable. In other words what value would our random variable “tend” to if we repeat the experiment “n” number of times. In our chocolate example E[X] of a binomial random variable is given by the formula “np”, where “n” is the number of repeats and p is the probability of success. That will come out to be 100. The denominator here is the value on which we want to find our bound, in our case 145, which gives us the probability as 0.689.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/216/1*ZKUw-7y6ILm0sMnskY8DMQ.gif" /><figcaption>Probability Bound of the chocolate example.</figcaption></figure><p>This is also called the “Upper Bound” on the probability which means that this event would occur with a probability of at most 68.9%.<br>Tho being very useful there are some downsides to this inequality too. Markov’s inequality cannot be applied if our random variable X takes a negative value. For example, if X denotes the difference of the numbers one would get but throwing a fair die twice, there would be cases when that turns out to be negative. To overcome this we define something called Chebyshev’s Inequality.</p><p><strong>Chebyshev’s Inequality<br></strong>The main idea behind Chebyshev’s inequality relies on the Expected value E[X] and the standard deviation SD[X]. The standard deviation is a measure of spread in statistics, it defines how much our data is “deviated” away from the mean value, in our case that mean value is E[X].</p><p>This inequality tells us that certain values in our data can be no more than “k” standard deviations away from our expected value E[X]. The expectation of X is also known as the mean value of our random variable. This, in a sense, gives us a symmetrical point around which X would be spread. This spread can be measured by the standard deviation and multiplying the standard deviation by “k” just gives us the bounds of how far can certain values lie from our expected value. Chebyshev’s Inequality can be calculated using the formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/317/1*N9iV_4p7PvrKBxqR7WJ-7w.gif" /><figcaption>Chebyshev’s Inequality.</figcaption></figure><p>This inequality also defines some bounds that are applicable to a lot of probability distributions. It tells us that 100% of our data values would lie 1 standard deviation away from the mean, 25% of our data would lie 2 standard deviations away from the mean, and so on.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/268/1*RjiQj-_ZjJn9y-Iw1XENSg.gif" /><figcaption>General Probability Bounds by Chebyshev’s Inequality.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*j3i_lY8O3feLp-_vweIqAA.gif" /><figcaption>Bounds in Chebyshev’s Inequality.</figcaption></figure><p>To demonstrate this let&#39;s go back to our chocolate example. Let’s say we wanted to know that what will be the upper bound on my probability if we visit at least 90 stores and at most 110 stores. This can be calculated using the method below. We subtract our mean value from both of our bounds. This gives us the value of k*SD[X] as 10. From that, we calculate the value of k and put it on the right-hand side of the inequality.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/662/1*eRR7Qqgq508mdz1H7tf1Gg.gif" /><figcaption>Using Chebyshev’s Inequality to calculate upper bound.</figcaption></figure><p>Chebyshev’s Inequality can be applied to any probability distribution on which mean and variance are defined. This is of great help when we have no idea how to describe our random variable. This inequality helps us calculate upper and lower bounds by which those certain events can occur.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1cd09377bfb0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Cosine Similarity — yet another mathematical jargon in our daily lives?]]></title>
            <link>https://medium.com/@paarthbhatnagarh3h3/cosine-similarity-yet-another-mathematical-jargon-in-our-daily-lives-8303dbb7c570?source=rss-e6355a0f9843------2</link>
            <guid isPermaLink="false">https://medium.com/p/8303dbb7c570</guid>
            <category><![CDATA[cosine-similarity]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[recommendation-system]]></category>
            <category><![CDATA[deep-learning]]></category>
            <dc:creator><![CDATA[Paarth bhatnagar]]></dc:creator>
            <pubDate>Wed, 22 Sep 2021 13:43:38 GMT</pubDate>
            <atom:updated>2021-09-22T13:43:38.228Z</atom:updated>
            <content:encoded><![CDATA[<h3>Cosine Similarity — yet another mathematical jargon in our daily lives?</h3><p>It might go unnoticed in one’s eye how all these online services popping nowadays tend to get better and better at suggesting to us the things we like.</p><p>From Amazon to Netflix and many more, they never fail to recommend us things we want, and at the heart of this lies this simple yet beautiful idea of cosine similarity.</p><p>There is this quote I’ve come across a dozen times on the internet “you are known by the company you keep”, not sure how much that translates into real-world but becomes evidently clear when we want to build computational engines that map out things based on how similar they are.</p><p>If you’re familiar with basic math you might’ve heard of this term called a “vector”, it’s like a pointy arrow from the origin(or any other point) up to a certain coordinate in something that we call a Vector Space. A Vector Space is just the space that a vector exists in.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*rrvsvVX6Z78z1G6RFkk_QQ.gif" /><figcaption>A Vector Space.</figcaption></figure><p>Turns out these vectors are really helpful in building such big systems. Let’s take an example of Amazon, I go to the Amazon website to order some chocolates when I scroll down on that tab I notice Amazon suggesting all the products that have a certain element of chocolate involved in them. I would never see clothes popping up in the chocolate category.</p><p>This is what we mean by “similarity” and all these products we see on Amazon can be mapped as vectors living in a vector space.</p><p>More the similarity of the category in which those products belong, more closely would their vectors be in the vector space. We can really, convert that textual data into vector representations by using some concepts from the field of machine learning.</p><p>The idea of cosine similarity helps us calculate this similarity between these vectors and helps us decide which one belongs where in the Vector Space.</p><p>A vector can be thought of as a list of numbers and can be denoted as shown in the image below. Sometimes we flip this representation by 90 degrees but intrinsically they both mean the same. Inside these vectors are the numbers we want them to represent.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/180/1*d1aJ3ju_VkBErorA2GBRPw.png" /><figcaption>Vector Representations.</figcaption></figure><p>Let us assume two vectors A and B which denote the chocolates made by any two random companies. Here the chocolate by company A is the vector (1 0) and chocolate by company B is the vector (2 0)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/425/1*cWC7Mn0_CUOq2-fsq3MzYQ.png" /><figcaption>The formula for Cosine Similarity</figcaption></figure><p>The formula above helps us calculate the “cosine similarity” of two vectors.</p><p>The Numerator of the equation of cosine similarity represents the dot product and it can be calculated by the formula given below. This formula is limited to 2x1 dimensional vectors in our case.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/313/1*kV_GHTwGYXAb44Kk1ZumoQ.png" /><figcaption>The Dot Product</figcaption></figure><p>The dot product comes out to be 2, which gives us the numerator of our equation. Note: This is a very simple example of 2x1 dimensional vectors in real-life situations the dimensions of these vectors can get really large.</p><p>The norm of a vector can be thought of as calculating the length of that vector. In our case, we will use the formula for calculating norm as given below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/328/1*M70ZSLeyIoV1eNf54yVPCg.png" /><figcaption>Calculating the Norm.</figcaption></figure><p>Finally diving the value of our dot product by the value of the products of our norm gives us cosine of theta to be 1.</p><p>The Cosine of theta is 1 when the angle between those two vectors in the vector space is 0 degrees. This means that those two vectors lie on the same line, which in turn in our language of similarity means those two vectors are “very similar”. This can be visualized in the animation below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*9-xWtGEsjdlQB67eI14z-w.gif" /></figure><p>In fact, in terms of linear algebra, Vector B is just the scaled-up version of Vector A. This means if we multiply the vector A by 2 it will give us Vector B.</p><p>So when will two things be dissimilar? One might ask, let’s take up a simple example to illustrate this too. Let a vector denoting chocolate be CHOC(1 0) and another vector denoting clothes be CLOTHES(0 1). If we go through the same process of calculating the cosine similarity of these two vectors it will come out to be 90 degrees. This means that these two vectors are perpendicular to each other in that vector space, which in turn in our language of similarity means they are “dissimilar” from each other.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*13xY0S2Vc_Mg9w9Z7ii1_g.gif" /></figure><p>Cosine Similarity is actively used in the field of Natural Language Processing, A subfield of Artificial Intelligence that focuses on summarizing textual data and building predictive models upon it.</p><p>This simple mathematical idea has a lot of applications in the real world, it is what lies at the heart of a lot of recommendation systems, like that of all these OTT Streaming services like Netflix, Amazon Prime. If you’ve ever seen a message on amazon saying “Customers who bought X also bought Y” chances are this simple equation is the reason why you’re seeing it.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8303dbb7c570" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>