<?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 Robby Sneiderman on Medium]]></title>
        <description><![CDATA[Stories by Robby Sneiderman on Medium]]></description>
        <link>https://medium.com/@rob-sneiderman?source=rss-cd494db13357------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*cVY_Z0BLK6R2I7_5FmOpmQ@2x.jpeg</url>
            <title>Stories by Robby Sneiderman on Medium</title>
            <link>https://medium.com/@rob-sneiderman?source=rss-cd494db13357------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 05:09:31 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@rob-sneiderman/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[Introduction to High-Dimensional Problems (p>>N)]]></title>
            <link>https://www.cantorsparadise.com/introduction-to-high-dimensional-problems-p-n-1b22cb9a0315?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/1b22cb9a0315</guid>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Tue, 30 Jul 2024 01:18:08 GMT</pubDate>
            <atom:updated>2024-08-21T23:25:43.003Z</atom:updated>
            <content:encoded><![CDATA[<h4>And when “Less fitting is better”</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/864/1*vg3mDou488AR4cL5XZIaSA.png" /><figcaption>Image created by Author via Llama 3.1</figcaption></figure><h3>Part 1:</h3><p>In this article, we will work through and discuss part of Chapter 18 from <a href="https://hastie.su.domains/ElemStatLearn/">“<em>The Elements of Statistical Learning, Second Edition”</em></a>, titled “<em>High-Dimensional Problems: </em><strong><em>p</em></strong><em>&gt;&gt;</em><strong><em>N</em></strong><em>”. </em>I also provide the full code used to generate the simulations and plots via my <a href="https://github.com/Robby955/HighDimensionalData/tree/main">GitHub</a>.</p><p><em>High-dimensional</em> data refers to data in which there is a high number of columns relative to the number of observations, in particular if we have <strong>N </strong>observations, and each observation has <strong>p</strong> columns (or features), if the number of features is much larger than the number of observations, written <strong>p &gt;&gt; N</strong>, it is said to be a <em>high-dimensional</em> problem.</p><p>Before going into details, here is a summary table I made that contrasts standard data problems, with high dimensional problems at a general level.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*JW0-ENKYA0no1hsDSKmH4g.png" /><figcaption>Summary table for high-dimensional data, created by Author.</figcaption></figure><h3>Preliminary:</h3><p>To understand the context of this problem, you should be familiar with regression and especially the concept of <a href="https://medium.com/towards-data-science/from-linear-regression-to-ridge-regression-the-lasso-and-the-elastic-net-4eaecaf5f7e6">regularization.</a> In regularization we have the<em> regularization</em> parameter,<em> </em>λ. In particular, as λ gets large, more and more coefficients approach 0 or are even forced to 0 (for the Lasso).</p><p>But how can we actually relate the λ to an actual understandable definition of complexity?</p><p>To do this, we use the <em>effective degrees of freedom</em>, here is the technical definition:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/525/1*Dnt8L8Sr-AK6Vefb6c049A.png" /><figcaption>The technical definition of the effective degrees of freedom depends on λ. Elements of Statistical Learning, Second Edition, Page 68.</figcaption></figure><p>The effective degrees of freedom is actually a more interpretable version of the usual λ parameter. In fact, when there is no regularization (λ=0), then the effective degrees of freedom is <strong>p</strong>, the number of features. This is the exact case of the familiar regular least squares regression.</p><p>On the other hand, as λ approaches infinity, the effective degrees of freedom approaches 0. This also makes sense if you are familiar with feature selection via Lasso, a larger regularization parameter will cause more and more features to have coefficients set to 0.</p><p>Now, we can get to the details of the problem. In particular in Chapter 18, the authors highlight the<em> less data principle</em>, here they demonstrate a case in which we are better off using less predictors. To do this, they did a simulation study, using 100 simulations for three distinct number of features (p=20, p=100 and p=1000).</p><p>For the simulation, the target variable is <strong>Y</strong>, with this form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/308/1*RuY3KtUPx4Dim_DlCRFjng.png" /><figcaption>The target variable formed for the simulation.</figcaption></figure><p>The <strong>β</strong> and <strong>ε</strong> come from a <em>Normal(0,1)</em> (standard normal distribution). Moreover, they specify that the correlation between any two X (pairwise) is 0.2, and the variance of the error term is 2.</p><pre># Load necessary libraries<br>library(MASS)<br>library(glmnet)<br># Simulation parameters<br>N &lt;- 100<br>sigma_sq &lt;- 2<br>correlation &lt;- 0.2<br>beta_mean &lt;- 0<br>beta_sd &lt;- 1<br># Number of features<br>p_values &lt;- c(20, 100, 1000)<br># Regularization parameters<br>lambdas &lt;- c(0.001, 100, 1000)</pre><p>To simulate <strong>Y</strong> we generate the features by specifying the criteria and calling the <em>mvnorm</em> function.</p><pre># Function to generate correlated Gaussian features<br>generate_features &lt;- function(N, p, correlation) {<br>  Sigma &lt;- matrix(correlation, nrow = p, ncol = p)<br>  diag(Sigma) &lt;- 1<br>  mvrnorm(N, mu = rep(0, p), Sigma = Sigma)<br>}<br><br># Function to generate outcome<br>generate_outcome &lt;- function(X, beta, sigma) {<br>  epsilon &lt;- rnorm(nrow(X), mean = 0, sd = sigma)<br>  Y &lt;- X %*% beta + epsilon<br>  Y<br>}</pre><p>Then, we fit regression models (for each value of λ=0.001, λ=100 and λ=1000) for each of the predictors p=20, p=100 and p=1000.</p><pre><br># Initialize lists to store results<br>test_errors &lt;- list()<br>effective_dof &lt;- list()<br><br>for (p in p_values) {<br>  for (i in 1:100) {<br>    # Generate coefficients<br>    beta &lt;- rnorm(p, mean = beta_mean, sd = beta_sd)<br>    <br>    # Generate features<br>    X &lt;- generate_features(N, p, correlation)<br>    <br>    # Generate outcome<br>    sigma &lt;- sqrt(var(X %*% beta) / sigma_sq)<br>    Y &lt;- generate_outcome(X, beta, sigma)<br>    <br>    # Split data into training and test sets<br>    train_idx &lt;- sample(1:N, size = 0.9 * N)<br>    test_idx &lt;- setdiff(1:N, train_idx)<br>    <br>    X_train &lt;- X[train_idx, ]<br>    Y_train &lt;- Y[train_idx]<br>    X_test &lt;- X[test_idx, ]<br>    Y_test &lt;- Y[test_idx]<br>    <br>    # Fit ridge regression models and calculate test errors<br>    for (lambda in lambdas) {<br>      fit &lt;- glmnet(X_train, Y_train, alpha = 0, lambda = lambda)<br>      predictions &lt;- predict(fit, X_test)<br>      test_error &lt;- mean((Y_test - predictions)^2)<br>      relative_error &lt;- test_error / sigma_sq<br>      test_errors[[paste(p, lambda, sep = &quot;_&quot;)]] &lt;- c(test_errors[[paste(p, lambda, sep = &quot;_&quot;)]], relative_error)<br>      <br>      # Calculate effective degrees of freedom using formula with singular values (d)<br>      d &lt;- svd(X_train)$d<br>      df &lt;- sum(d^2 / (d^2 + lambda))<br>      effective_dof[[paste(p, lambda, sep = &quot;_&quot;)]] &lt;- c(effective_dof[[paste(p, lambda, sep = &quot;_&quot;)]], df)<br>    }<br>  }<br>}</pre><p>Then, we plot the relative test error for each feature level:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/724/1*72J64T2iiqnNv_yP_NeU1w.png" /><figcaption>Plot created in R by Author showing the three cases of varying number of features.</figcaption></figure><h3><strong>Interpretation:</strong></h3><p>For <strong>p = 20 features</strong>, the lowest test error corresponds to a situation where the regular regression case (with minimal regularization, λ = 0.001) is optimal. Here, we can use all features without heavily penalizing complexity, and the model still maintains a low bias.</p><p>For <strong>p = 100 features</strong>, the lowest relative test error occurs with a moderate amount of regularization, corresponding to a model with approximately 33 predictors (λ = 100). This shows that as the number of features increases, some level of regularization is necessary to reduce variance and prevent overfitting.</p><p>For <strong>p = 1000 features</strong>, the best result is achieved with an even smaller effective degrees of freedom (i.e., fewer active predictors). This highlights the growing necessity for regularization when the number of features is very large, as including too many predictors leads to overfitting.</p><p><strong>Why?</strong></p><ul><li>When <strong>p = 20</strong>, the model can incorporate all features while still maintaining low bias due to the relatively small number of predictors.</li><li>When <strong>p = 100</strong>, regularization becomes more important to manage the increased potential for overfitting, and the model performs best with a subset of features (33 predictors).</li><li>When <strong>p = 1000</strong>, the model achieves the best performance using fewer than 50 of the 1000 predictors. This illustrates that as the feature set grows larger, regularization plays a critical role in preventing overfitting by effectively shrinking the number of active predictors.</li></ul><p>In <strong>Ridge regression with λ = 0.001</strong>, when <strong>p &lt; N</strong>, the model can successfully exploit correlations among the features to improve performance. However, as the number of features increases, regularization becomes crucial to counteract the risk of overfitting, highlighting the balance between bias and variance in high-dimensional settings.</p><h3>Conclusion:</h3><p>So, when is less better? When there is a high-dimensional data, it very likely that less predictors is actually better than more.</p><p>We have seen that use of regularization is very important for high dimensional problems. In my next article, I hope to continue study of this chapter of the book and examine the gene expression data and more advanced methods for high dim analysis such as <em>Nearest Shrunken Centroids</em> and <em>Supervised Principal components.</em></p><p>Thanks very much for reading, please let me know if you have any questions or comments, or to make a correction.</p><p>[1] <em>T. Hastie et al,. The Elements of Statistical Learning, Second Edition.</em></p><p>[2] <a href="https://royalsocietypublishing.org/author/Johnstone%2C+Iain+M"><em>Johnstone Iain M.</em></a><em> and </em><a href="https://royalsocietypublishing.org/author/Titterington%2C+D+Michael"><em>Titterington D. Michael</em></a><em>, Statistical challenges of high-dimensional data. Phil. Trans. R. Soc. A.3674237–4253</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1b22cb9a0315" width="1" height="1" alt=""><hr><p><a href="https://www.cantorsparadise.com/introduction-to-high-dimensional-problems-p-n-1b22cb9a0315">Introduction to High-Dimensional Problems (p&gt;&gt;N)</a> was originally published in <a href="https://www.cantorsparadise.com/">Cantor’s Paradise</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Exploring the Monty Hall and Birthday Problem with Simulations]]></title>
            <link>https://www.cantorsparadise.com/exploring-the-monty-hall-and-birthday-problem-with-simulations-9c1bca66c5f5?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/9c1bca66c5f5</guid>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[probability]]></category>
            <category><![CDATA[simulation]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Sun, 28 Jul 2024 20:31:13 GMT</pubDate>
            <atom:updated>2024-08-05T14:40:25.670Z</atom:updated>
            <content:encoded><![CDATA[<h4>Understand the results of two classic probability puzzles through interactive R simulations</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RavaUdW8cX-EisW67ZbShw.jpeg" /></figure><p><strong>Introduction</strong>:</p><p>In this article, we’ll explore two classical problems in probability — the <em>Monty Hall Problem</em> and the <em>Birthday Problem</em>— and we will use R simulations to visualize and verify the surprising results.</p><p>Simulations are an extremely powerful tool in Statistics and Data Science, as they can be used to verify results practically.</p><p>We’ll also provide interactive Shiny apps and links to the <a href="https://github.com/Robby955/ProbabilityPuzzles">GitHub</a> with the full code so you can run it yourself.</p><h3>Section 1: The Monty Hall Problem</h3><p>The Monty Hall problem is a probability puzzle based on the American television game show “Let’s Make a Deal.” Here’s the setup:</p><ul><li>You are a contestant on a game show.</li><li>There are three identical looking doors: behind one is a car, and behind the other two are goats.</li><li>You are asked to pick one of three doors.</li><li>Once you have made your initial pick , the host, who knows what’s behind each door, will always open another door to reveal a goat.</li><li>The host then asks if you want to switch to the remaining door.</li></ul><p><a href="https://robprojects.shinyapps.io/monty_hall_app/"><em>Try it yourself using my interactive Shiny Application</em></a></p><h3>Should you switch doors?</h3><p>A common answer would be “No” as it seems there should be no difference between staying or switching. But the actual answer is, yes, you should switch, in fact this will increase your odds of winning the car to 2/3.</p><p>Here is some code that generates and simulates thousands of random instances of the Monty Hall problem.</p><pre># Monty Hall Simulation Function<br>monty_hall &lt;- function(iterations, switch) {<br>  results &lt;- replicate(iterations, {<br>    # Step 1: Generate doors with one car and two goats<br>    doors &lt;- c(rep(&#39;goat&#39;,2), &quot;car&quot;)<br>    doors &lt;- sample(doors)  # Randomly place the car behind one of the doors<br>    <br>    # Step 2: Player makes a choice<br>    choice &lt;- sample(1:3, 1)  # Player&#39;s initial choice<br>    <br>    # Step 3: Host reveals a goat<br>    car_position &lt;- which(doors == &quot;car&quot;)<br>    available_doors &lt;- setdiff(1:3, c(choice, car_position))<br>    if (length(available_doors) &gt; 1) {<br>      reveal &lt;- sample(available_doors, 1)<br>    } else {<br>      reveal &lt;- available_doors<br>    }<br>    <br>    # Step 4: Player decides whether to switch<br>    if (switch) {<br>      choice &lt;- setdiff(1:3, c(choice, reveal))[1]<br>    }<br>    <br>    # Step 5: Check if the final choice has the car<br>    result &lt;- doors[choice] == &quot;car&quot;<br>    return(as.numeric(result))<br>  })<br>  <br>  win_rate &lt;- mean(results)<br>  loss_rate &lt;- 1 - win_rate<br>  return(list(win_rate = win_rate, loss_rate = loss_rate))  # Return the win and loss rates<br>}<br><br># Function to compare both strategies and plot densities<br>compare_strategies &lt;- function(max_iterations) {<br>  iteration_points &lt;- c(10, 100, 500, 1000, 2000, <br>5000, 10000, 20000, 50000, 100000)<br>  win_rates_switch &lt;- numeric(length(iteration_points))<br>  loss_rates_switch &lt;- numeric(length(iteration_points))<br>  win_rates_stay &lt;- numeric(length(iteration_points))<br>  loss_rates_stay &lt;- numeric(length(iteration_points))<br>  <br>  for (i in seq_along(iteration_points)) {<br>    iter &lt;- iteration_points[i]<br>    result_switch &lt;- monty_hall(iter, TRUE)<br>    result_stay &lt;- monty_hall(iter, FALSE)<br>    win_rates_switch[i] &lt;- result_switch$win_rate<br>    loss_rates_switch[i] &lt;- result_switch$loss_rate<br>    win_rates_stay[i] &lt;- result_stay$win_rate<br>    loss_rates_stay[i] &lt;- result_stay$loss_rate<br>  }<br>  <br>  df &lt;- data.frame(<br>    Iterations = rep(iteration_points, 4),<br>    Rate = c(win_rates_switch, loss_rates_switch, win_rates_stay, loss_rates_stay),<br>    Strategy = rep(c(&quot;Switch (Win)&quot;, &quot;Switch (Loss)&quot;, &quot;Stay (Win)&quot;, &quot;Stay (Loss)&quot;), each = length(iteration_points))<br>  )<br>  <br><br># Example Usage<br>compare_strategies(100000)</pre><p>Here is the result showing the simulation over a number of iterations (on the x axis). As we try enough games, we see that switching most definitely improves our odds of winning.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ryr2zygC087UYybFEagkOQ.png" /><figcaption>Plot showing the iterations and win rate over time on log scale</figcaption></figure><h4>Probability Analysis</h4><p>We won’t provide detail or proof here instead we showcase how using simulation can prove to us a result without needing to understand the details of the proof.</p><p>The standard proof of this result is often given via Bayesian statistics. However it can arguably better be understood via the <em>minimax theorem.</em> it goes as follows:</p><ul><li>The player’s goal is to maximize their chances of winning the car.</li><li>When the player initially picks a door, they have a 1/3 chance of picking the car and a 2/3 chance of picking a goat. The host then opens a door with a goat, introducing new information.</li></ul><p>If you initially chose the correct door (1/3 probability) that had the car behind it, if you switch you will lose the game and switch to a door with a goat.</p><p>If you initially chose a door with a goat behind it (occurs with a 2/3 probability), the host will have no choice but to reveal the other door with the goat, and hence if you switch you will win the car.</p><ul><li><strong>By switching doors, the player effectively maximizes their chances of winning the car to 2/3. This is because the strategy leverages the host’s reveal to update the probabilities and minimize the worst-case scenario (ending up with a goat). Hence, in the more common case, (2/3 case) switching leads to a car every single time. I find this to be the best way of understanding the Monty Hall Problem.</strong></li></ul><h3>Section 2: Birthday Problem</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xma_rajEB5sVZFfJhk3Abw.png" /><figcaption>The Birthday Problem</figcaption></figure><p>Ask yourself the following: how many people would you expect to need in a room for there to be at least a 50% chance at least two share a birthday?</p><p>The answer is the seemingly unintuitive 23 people.</p><p><a href="https://robprojects.shinyapps.io/birthday_paradox_app/"><em>Try it yourself using my interactive Shiny Application</em></a></p><p>Let us also use R to simulate thousands of selections of dates and flag those which have a match. Here is some code that helped generate the simulation and creates samples of random birthdays you can try running.</p><pre># Load necessary libraries<br>library(ggplot2)<br>library(ggthemes)<br># Function to simulate the Birthday Paradox<br>simulate_birthday_paradox &lt;- function(num_people, num_simulations) {<br>  has_shared_birthday &lt;- function(num_people) {<br>    birthdays &lt;- sample(1:365, num_people, replace = TRUE)<br>    return(any(duplicated(birthdays)))<br>  }<br>  <br>  results &lt;- replicate(num_simulations, has_shared_birthday(num_people))<br>  probability &lt;- mean(results)<br>  <br>  return(probability)<br>}<br><br># Function to generate random birthdates and highlight matches<br>generate_birthdates &lt;- function(num_people) {<br>  months &lt;- c(&quot;January&quot;, &quot;February&quot;, &quot;March&quot;, &quot;April&quot;, &quot;May&quot;, &quot;June&quot;, <br>              &quot;July&quot;, &quot;August&quot;, &quot;September&quot;, &quot;October&quot;, &quot;November&quot;, &quot;December&quot;)<br><br>  days_in_month &lt;- c(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)<br>  cumulative_days &lt;- rep(NA, length(days_in_month))<br>  cumulative_days[1] &lt;- days_in_month[1]<br><br>  for (i in 2:length(days_in_month)) {<br>    cumulative_days[i] &lt;- cumulative_days[i - 1] + days_in_month[i]<br>  }<br>  <br>  birthdates &lt;- sample(1:365, num_people, replace = TRUE)<br>  date_names &lt;- sapply(birthdates, function(x) {<br>    month &lt;- months[ceiling(x / 31)]<br>    day &lt;- days[(x %% 31) + 1]<br>    return(paste(month, day))<br>  })<br>  unique_dates &lt;- unique(date_names)<br>  duplicated_dates &lt;- unique(date_names[duplicated(date_names)])<br>  <br>  cat(&quot;Randomly generated birthdates:\n&quot;)<br>  for (i in 1:num_people) {<br>    if (date_names[i] %in% duplicated_dates) {<br>      cat(&quot;*&quot;, date_names[i], &quot;(duplicate)\n&quot;)<br>    } else {<br>      cat(date_names[i], &quot;\n&quot;)<br>    }<br>  }<br>}<br># Example usage<br>num_people &lt;- 23<br>num_simulations &lt;- 10000<br># Print random birthdates with duplicates highlighted<br>generate_birthdates(num_people)<br></pre><p>Here is the plot of our code ran on 10,000 simulations each on a variety of a number of people. We can also see that once the number of people in the room is at or above 23, we have a greater than 50% chance that at least two will share a birthday.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FZiAIUdKI94ObraWpZ3U5A.png" /><figcaption>The plot of the probability for the Birthday Problem</figcaption></figure><p>The key for understanding this unintuitive result is to realize is that each additional person introduces another set of possible combinations to compare.</p><p>Simulations are a powerful and often under utilized tool in statistics and data science. They allow researchers or those working with data to quickly test or verify results, and can be used to model and test results especially in the realm of discrete math and statistics.</p><p>Do you know any other counterintuitive or interesting results in statistics or probability that can be better understood with simulations?</p><p>Thanks for reading!</p><p>- <a href="https://github.com/Robby955/ProbabilityPuzzles">GitHub</a> for the full code used in this project.</p><p><strong>References:</strong></p><p>[1] Gardner, M. (1959a), “Mathematical Games” column, Scientific American, October 1959, 180–182. Reprinted in The Second Scientific American Book of Mathematical Puzzles and Diversions.</p><p>[2] Gill, R.D. (2011), The Monty Hall Problem is not a Probability Puzzle — it’s a challenge in mathematical modelling, Statistica Neerlandica 65 58–71.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9c1bca66c5f5" width="1" height="1" alt=""><hr><p><a href="https://www.cantorsparadise.com/exploring-the-monty-hall-and-birthday-problem-with-simulations-9c1bca66c5f5">Exploring the Monty Hall and Birthday Problem with Simulations</a> was originally published in <a href="https://www.cantorsparadise.com/">Cantor’s Paradise</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Introduction to Elementary Number Theory]]></title>
            <link>https://www.cantorsparadise.com/introduction-to-elementary-number-theory-e598b2300ac3?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/e598b2300ac3</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[numbers]]></category>
            <category><![CDATA[number-theory]]></category>
            <category><![CDATA[prime-numbers]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Sun, 17 Oct 2021 10:42:48 GMT</pubDate>
            <atom:updated>2021-10-22T05:18:57.207Z</atom:updated>
            <content:encoded><![CDATA[<h4><em>Covering the basics (and required details for basic Cryptography)</em></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RNcmh8Y0XN_RH4-lSEe-dQ.jpeg" /><figcaption>Image 1: <a href="https://unsplash.com/photos/GQ327RPuxhI">Susan Holt Simpson via Unsplash</a></figcaption></figure><p>In this article, I will introduce the basic concepts of number theory and provide a description of the most important and basic theorems. This article will provide a brief, non-comprehensive description, and if you are able to follow and understand this article then you will have a solid foundation to understand the more advanced topics in the field. In my next article, I will use the information covered here to introduce and cover the basics of Cryptography. We will eventually see how number theory is actually highly applied and has uses including in data science.</p><h3>Introduction:</h3><p>In the most basic terms, number theory is the study of the<em> Integers.</em> The integers are an extension of the Natural Numbers, the basic numbers that are introduced in early childhood. The integers include those basic natural numbers like 1,2 and 3. But the integers extend the idea to also include the negative numbers such as -1,-2 and -3 and so forth. 0 is also included as an integer, but some people don’t consider 0 a natural number (while others do).</p><p>Because the integers can be seen as the most ‘simple’ or ‘basic’ of numbers used in simple arithmetic, the field has sometimes been ignored or even neglected. Historically, while heavily studied in antiquity, number theory was often viewed as the most ‘pure’ branch of mathematics, in contrast with applied mathematics (such as calculus). However, this turned out to be far from the case and the applications and results of number theory are now vitally important to modern life.</p><p>The history of number theory is a great proof of why branches of mathematics that are currently seen as ‘useless’ or only pure, may nonetheless have important discoveries that are utilized in the future. The number-theorist <a href="https://en.wikipedia.org/wiki/Leonard_Dickson"><em>Leonard Dickson</em></a><em> (1874–1954) said “Thank God that number theory is unsullied by any application.” </em>This would later become a famous quote as it turned out not to be the case. It is also a lesson for us today, because there are currently areas of pure mathematics seen as useless that very well likely become applied in the near or far future<em>.</em></p><p>Firstly, a quick reminder on notation.</p><p>The set of Integers is often denoted as Z:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/390/1*glGbVDBGsGBggOMOLhCXWg.png" /><figcaption>Figure 1: The set of all integers is often denoted as Z. Source: Latex by author.</figcaption></figure><h3><strong>Definition: Division</strong></h3><p>We say a number <strong>U </strong>divides a number <strong>W </strong>if we can write <strong>W=L*U </strong>for some integer <strong>L</strong>.</p><p><strong>Example: </strong>U=15 divides W=30 because 30=15*2 ,(with L=2).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/376/1*VKmskCIPkmhtTf_FJllVHw.jpeg" /><figcaption>Image 2: Euclid of Ancient Greece. One of the fathers of Number Theory. Much of the work and alternate proofs were contained in the famous <a href="https://en.wikipedia.org/wiki/Euclid%27s_Elements">“Elements”</a>. <a href="https://commons.wikimedia.org/wiki/File:Scuola_di_atene_23.jpg">Image Citation: Creative Commons</a>.</figcaption></figure><h3>Euclid&#39;s Division Lemma:</h3><p>Euclid’s lemma states that given any two integers, a and b&gt;0, there exists two unique integers q and r such that;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/326/1*ZiV_4bQ6UGfuAfJp6D0J6g.png" /><figcaption>Figure 2: Any integer a can be written in the above form. Source: Latex by author.</figcaption></figure><p>b is known as the ‘<em>divisor</em>’, q is known as the ‘<em>quotient</em>’ and r is known as the ‘<em>remainder’.</em> This is known as Euclid’s division. Notice that if r=0 we would have an exact division from the first definition. Note, we will consider the case that b&gt;0. If b&lt;0 we could simply write b’=-b and q’=-q and the proofs would remain the same.</p><h4><strong>Proof:</strong></h4><p>To prove Euclid&#39;s lemma we must prove that the solution exists and also that the q and r are unique. We thus have two parts to the proof.</p><p><em>Existence;</em></p><p>Existence can be proven by induction. Firstly, the base case is a=0. Then, for any b&gt;0, we simply take q=0, and the result holds with r=0. That proves the base case.</p><p>Then assume the result holds for any integer a&gt;0. We must show it also holds for a+1.</p><p>Since we assume it holds true for a, we have;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/318/1*qgVR070-RA-5bbHRHCzOPw.png" /><figcaption>Figure 3: We assume it holds for an arbitrary integer a. Source: Latex by author.</figcaption></figure><p>By the condition on r’, we know that r’=b-1 or r’&lt;b-1. We will consider both cases separately.</p><p><strong>Case 1:</strong> r’=b-1;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/542/1*Pg_ecRdcJKnCo-WHahTl1w.png" /><figcaption>Figure 4: If r’ is b-1, we can rewrite as above. Source: Latex by author.</figcaption></figure><p>Then adding 1 to get a+1 gives;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/426/1*frZZ9thwdGCnbfUYkgk1Cg.png" /><figcaption>Figure 5: adding one for the induction step. Source: Latex by author.</figcaption></figure><p>Which is of the exact form we require, with r=0&lt;b, and q=q’+1.</p><p><strong>Case 2: </strong>r’&lt;b-1</p><p>We can simply take q’=q and r=r’+1 and so,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/390/1*veLKlaETy_G97kl6FGcmGQ.png" /><figcaption>Figure 6: The induction step; we add 1 to a. Source: Latex by author.</figcaption></figure><p>And our r term still maintains the constraint as;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/378/1*AnCyUPl-_Nqto4dp0YI1Sg.png" /><figcaption>Figure 7: the constraints on the remainder r. Source: Latex by author.</figcaption></figure><p>Thus, we have proven the base case and the induction step. So, we have the proof of existence for Euclid’s division lemma.</p><p><em>Uniqueness:</em> To prove uniqueness suppose we could write a in two non-unique forms as follows;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/188/1*91UqvFSURQ0DmMa1dBMZ7A.png" /><figcaption>Figure 8: Suppose a could be written in this form with 0≤r1&lt;|b|. Source: Latex by author.</figcaption></figure><p>and as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/178/1*9fxsS_4eN73HW1eSMWMvFQ.png" /><figcaption>Figure 9:Another form of a assuming it exists. Source: Latex by author.</figcaption></figure><p>with the constraints;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/322/1*7x8nmGpfsHlXW8uyrgu3UA.png" /><figcaption>Figure 10: The same constraints as above. Source: Latex by author.</figcaption></figure><p>So, since we are assuming they are both equal to a we have;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/268/1*4Xdh_Roz1KYnGMWbq_VEQA.png" /><figcaption>Figure 11: Setting the terms. Source: Latex by author.</figcaption></figure><p>Rearranging by subtraction;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/442/1*yM5Hw3xobtktgjRSCsO62A.png" /><figcaption>Figure 12: Formatting terms and moving r1-r2 to the left and simplifying. Source: Latex by author.</figcaption></figure><p>Now we have that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/238/1*guPxc7X3rAtxabB2yyJgvA.png" /><figcaption>Figure 13: Based off the constraints on r1 and r2 and subtracting r2 from 1. Source: Latex by author.</figcaption></figure><p>Which also implies that;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/346/1*E_HM7_aBzqj6ho_7eSBupw.png" /><figcaption>Figure 14: By our original requirement on r1 and r2. Source: Latex by author.</figcaption></figure><p>But b is not 0 and so this can only be true in the case that q2-q1=0 and hence q2=q1 which proves uniqueness. Thus, we have proven uniqueness and existence.</p><p><strong>QED.</strong></p><h3><strong>Definition: Prime Number</strong></h3><p><em>A prime number, P , is any integer larger than 1, that has only two distinct factors (‘divisors’), itself, and 1.</em></p><p>One of the most important results of prime numbers is that any integer greater than one can be written as a unique factorization of prime numbers. This is known as the Fundamental Theorem of arithmetic and allows for many important results, including in cryptography.</p><p><strong>Note:</strong> If you are wondering why 1 is not considered prime, this is so that the fundamental theorem of arithmetic can hold. If 1 was prime, we could have 5=5 and 5=5*1 which would violate the uniqueness clause.</p><h3>Definition: Greatest Common Divisor (GCD)</h3><p>The <em>GCD</em> of two or more integers is the largest integer that divides each of them alone. For example, GCD(1000,100,10)=10 because 10 is the largest number that divides all three integers. Note: we define GCD(x,0)=0 for any integer x.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/280/1*oJvtEcSk2GJj7JN_TgXlnQ.jpeg" /><figcaption>Image 3: French Mathematician Étienne Bézout. He was major contributor to number theory. <a href="https://en.wikipedia.org/wiki/%C3%89tienne_B%C3%A9zout#/media/File:Etienne_Bezout2.jpg">Image Citation: Creative Commons.</a></figcaption></figure><h4>Examples:</h4><p>GCD(120,12)=12.</p><p>GCD(240,120,12)=12</p><h3>Bézout’s Identity:</h3><p><em>Let A and B be integers such that GCD(A,B)=D. Then, there exists integers X and Y such that AX+BY=D.</em></p><h4><em>Example:</em></h4><p>A=34, B=19. Notice that 19 is prime, hence we will have GCD(34,19)=1. Thus, Bézout’s Identity implies the existence of integers X and Y such that X*34+Y*19=1. We won’t work through the details, but you can confirm this is indeed the case using X=-5 and Y=9.</p><h3>Proof:</h3><p>Firstly, we define a set <strong>T</strong> as follows;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/574/1*J9QLU7OJPImtk2rwzk-ThQ.png" /><figcaption>Figure 15: We define this set <strong>T. </strong>By definition it will be non-empty as we can choose convenient values for X and Y. Source: Latex by Author</figcaption></figure><p><strong>T</strong> is the set of all numbers of the form AX+BY greater than 0, where X and Y are integers. We know that <strong>T</strong> is not empty because we can choose convenient values for X and Y. If A is positive, we can simply choose X=1 and Y=0 and T will be non-empty. If A is negative, we can choose X=-1 and Y=0 and again T will be non-empty. In the case that A and B are both 0, we have gcd(0,0)=0 by definition so there is nothing to prove.</p><p>Since <strong>T</strong> is a non empty set, it contains a least element (a result that follows from the <a href="https://en.wikipedia.org/wiki/Well-ordering_principle"><em>Well ordering principal</em></a>). Let us call this least element M.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/200/1*f7812cAKknZpy8ACQU6pjQ.png" /><figcaption>Figure 16: We know T has a least element of the above form, we call it M. Source: Latex by author.</figcaption></figure><p>That is, <strong>T </strong>contains an element M=As+Bt for some s,t such that there is no smaller element in <strong>T.</strong> We then must show that GCD(A,B)=M. To do this, we must prove that M divides A and B and that any other number that divides A and B is less than M.</p><p>Let us start with A (the same can be repeated for B). by Euclidian division, we know we can write</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/364/1*OBeUAF-PSLaDwjZBb5dDqg.png" /><figcaption>Figure 17: Using Euclidian division on A. Source: Latex by author.</figcaption></figure><p>If r is exactly 0, we know that M divides A.</p><p>If r is not zero, then,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/792/1*PtARw1Rw-QjhmTcFIBEb_w.png" /><figcaption>Figure 18: Rearranging shows r can be written in the form of AX+BY. Source: Latex by author.</figcaption></figure><p>Which is of the form of AX+BY (with X=1-Qs and Y=-Qt).</p><p>Hence, r =0 or r is in the form that is in T, hence;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/168/1*sLZj0zb_9YPnacyUURFN1w.png" /><figcaption>Figure 19: We have that r is either exactly 0 or in the set T. Source: Latex by author.</figcaption></figure><p><strong>However, M is the least element in T and r&lt;M, so r must be exactly zero. That is, r divides A. The same can be done for B, ie r divides B.</strong></p><p>Finally, if there is another common divisor of both A and B, say it is called K.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/426/1*PPhMZh7eG90piU_YACinwA.png" /><figcaption>Figure: 20 We still need to show that M is the greatest divisor of both A and B. So, choose an arbitrary other divisor, K. Source: Latex by author.</figcaption></figure><p>Then we would have,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/610/1*zJSxK01oSNxQjorKGKelKA.png" /><figcaption>Figure 21: If K is another divisor, we can rewrite M in this form which implies K divides M. Source: Latex by author.</figcaption></figure><p>Which implies that K divides M, and hence by definition K≤M.</p><p>Thus, we have proven that the GCD can always be written in the form specified by Bézout.</p><p><strong>QED</strong></p><p>And there it is, we have proved Bézout’s identity. This will allow us to prove many of the following important results.</p><h3>Definition: Coprime</h3><p>We say integers A and B are ‘<em>coprime’</em> if the only common positive divisor among A and B is 1. Note, this by definition implies GCD(A,B)=1.</p><h4><em>Examples:</em></h4><p>17 and 19 are coprime.</p><p>192 and 161 are coprime.</p><h3>Euclid&#39;s Lemma:</h3><p><em>If a prime number, P, divides the product AB of two integers (A and B), then P must divide at least one of A, B.</em></p><h4><strong>Proof:</strong></h4><p>Suppose P divides AB.</p><p>Firstly, note that we will consider the case that GCD(P,A)=1. If GCD(P,A) was not equal to 1, then there would be nothing to prove since this would immediately imply that P divides A. Mainly because a GCD greater than 1 could only be P itself, which would imply P divides A. For example GCD(3,30)=3=P.</p><p>Since GCD(P,A)=1 by Bézout identity there exists X,Y such that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/212/1*2DUC8hmNPdxDaGNS71WkXQ.png" /><figcaption>Figure 22: Using Bézout’s lemma we can write 1 as above. Source: Latex by author.</figcaption></figure><p>multiplying both sides by B;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/268/1*E3fbMGg-bAkkG7_-QbIjkg.png" /><figcaption>Figure 23: Simply multiplying both sides by B. Source: Latex by author.</figcaption></figure><p>Now, we know that P divides P and hence P divides P(BX)=BPX. We also know that P divides AB from assumption, and hence divides (AB)Y=BAY. Thus, P divides BPX+BAY=B which proves P divides B.</p><p><strong>QED.</strong></p><h3><strong>The Fundamental Theorem of Arithmetic</strong></h3><p><em>Theorem: Any positive integer can be written as a unique factorization of prime numbers.</em></p><h4>Proof:</h4><p>This is proved by induction and using Euclid’s lemma. The proof involves showing that any integer greater than 1 is a prime, or can be written as a unique factorization of primes. Firstly the base case of induction, 2 is prime . Secondly, assume the result is true for all numbers up to N-1.</p><p>If N is prime then there is nothing left to prove. If N is not prime then N=AB for A&lt;N and B &lt;N. But A and B are prime or products of primes by assumption of induction. Thus, this proves the existence.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*ZG_OTRxrs4r_J4Z-fwJEKw.png" /><figcaption>Figure 24: If N is not prime it can be written as the product of some primes less than N. Source: Latex by author.</figcaption></figure><p>Now we most prove uniqueness;</p><p>Suppose M was the smallest integer that had a non-unique prime factorization. Thus, M could be written as;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/1*fxoRSnj-FEYA3LUJGVjM9A.png" /><figcaption>Figure 25: Assuming a non-unique representation. Source: Latex by author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/1*dsLqmCDcbuVbw4BZiCnQ_g.png" /><figcaption>Figure 26: M as separate factorization of primes. Source: Latex by author.</figcaption></figure><p>But by Euclid’s Lemma, since p1 divides M, p1 also divides some q. But p1 and any q are both prime, so if p1 divides q it implies that p1=q, and the same is true for all other p and q. Hence, we have proved both existence and uniqueness.</p><p><strong>QED.</strong></p><h3><strong>Theorem:</strong> There are infinite Prime Numbers</h3><p>Proof: Suppose there were only a finite number (say only K primes), then let A be the product of all primes plus 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/266/1*lLBT4xCBnet5CmjjXS5j1A.png" /><figcaption>Figure 27: Define A as the product of all primes and add 1. Source: Latex by author.</figcaption></figure><p>If A was prime this would prove the result immediately (as A would be a prime larger than all other primes, which would mean our initial assumption of a finite number of primes was incorrect).</p><p>Suppose A was not prime, then by the Fundamental theorem of arithmetic it can be written as a unique product of primes. Say Pj is the largest prime that divides A. So there exists an integer C such that we can write;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/342/1*UkuIKkn10FQk9Zucg3ZV7w.png" /><figcaption>Figure 28: Suppose Pj is a prime that divides A, C is an integer. Source: Latex by author.</figcaption></figure><p>Rearranging the above term gives;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/334/1*9HT6n0Z-Tw5QacWDr4Sjag.png" /><figcaption>Figure 29: Rearranging by subtraction. Source: Latex by author.</figcaption></figure><p>Now if Pj was any of the primes on our finite list of primes, (for example if Pj=P1), then this would allow us to write;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/294/1*wjp9Z_U1MehosjWfOSxWoA.png" /><figcaption>Figure 30 : If Pj was equal to any of the primes in our list it would imply p divides 1 which is impossible. Source: Latex by author.</figcaption></figure><p>Which would imply that P1 divides 1, which is a contradiction.</p><p><strong>Hence, there are an infinite number of primes.</strong></p><p><strong>QED.</strong></p><h3>Modular Arithmetic:</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YE-sfncoBLy4DpYMtoIt-Q.jpeg" /><figcaption>Image 4: <a href="https://unsplash.com/photos/L0xOtAnv94Y">Source: Unsplash Lisence.</a></figcaption></figure><p>Modular arithmetic is very useful in number theory. Sometimes it can be thought of as a clock, it is a representation of division with remainder and will allow for more advanced applications.</p><h3>Definition: Congruence</h3><p><em>Two integers, a and b are called congruent modulo n, if an integer n&gt;1 is a divisor of a-b. The integer n is known as the modulus.</em></p><p>For example;</p><p>30=2 (mod 28) because 28 divides 30–2=28.</p><p>Note that there are infinite such representations, for example</p><p>38=14 mod 12 because 12 divides 38–14=24</p><p>Also, 38=2 mod 12 because 12 divides 38–2=36.</p><p>The same can be done for negative integers as well,</p><p>38=-10 mod 12 because 12 divides 38-(-10)=48.</p><p>We will soon see why modular arithmetic is so useful.</p><h3>Primitive Roots modulo n and Discrete Logarithms:</h3><p>This definition is a bit confusing, but once you review a few examples it becomes much easier to understand.</p><h4><em>Definition:</em></h4><p><em>A number g is a primitive root modulo n if for every a coprime to n, there exists an integer k for which g^k=a mod n. The value k is called the discrete logarithm of a to base g mod n.</em></p><h4>Example 1:</h4><p>2 is a primitive root modulo 5. Why?</p><p>Now, what are all the numbers coprime to n=5? 1,2,3 and 4.</p><p>Start with 1. Take k=0, then 2⁰=1 mod5.</p><p>k=0 is the discrete logarithm of 1 to base 2 mod 5.</p><p>now for 2, take k=1, then 2¹=2 mod 5.</p><p>k=1 is the discrete logarithm of 2 to base 2 mod5.</p><p>Now for 3, take k=3 then 2³=8=3 mod 5</p><p>and for 4, take k=2, then 2²=4 mod 5.</p><p>That shows why g=2 is a primitive root modulo n=5.</p><h4>Example 2:</h4><p>3 is a primitive root modulo 7.</p><p>We must show that there exists integers k such that we can have any number relatively prime to 7 represented. The numbers relatively prime to 7 are 1,2,3,4,5,6 and 7.</p><p>For 1; take k=6, then 3⁶=729=1 mod 7</p><p>For 2; take k=2, then 3²=9=2 mod 7</p><p>For 3; k=7, 3⁷=2187=3 mod 7</p><p>For 4; k=4, 3⁴=81= 4 mod 7</p><p>For 5; k=5, 3⁵= 243=5 mod 7</p><p>For 6; k=3, 3³= 27= 6 mod 7</p><p>In terms of discrete logarithms. k=6 is the discrete logarithm of 1 to base 3 mod 7.</p><p>k=2 is the discrete logarithm of 2 to base 3 mod 7, etc.</p><p>So we have a k to make every number coprime to n=7, hence 3 is a primitive root modulo 7. Note as above, we don’t need to consider larger numbers as they will loop over, for example, 8 is coprime to 7 but 8=1 mod 7.</p><h4><strong>Example 3:</strong></h4><p>4 is not a primitive root mod 5.</p><p>Why? Because no matter what k we choose, we can never form 2 or 3 mod 5.</p><p>4⁰=1=1 mod 5</p><p>4¹=4=4 mod 5</p><p>4²=16=1 mod 5,</p><p>4³=64=4 mod 5,</p><p>And this continues on forever, so we can never get 2 or 3 (despite 2 and 3 being coprime to 5). Hence, 4 is not a primitive root mod 5.</p><h3>Distribution Of Primes:</h3><p>Just a quick note on the distribution of primes. There is currently no way of generating an arbitrary large prime, nor is there an exact science that tells us how the primes are distributed among the integers.</p><p>However, one strong result does hold and is known as the <em>Prime Number Theorem.</em></p><p>Firstly, we define the Prime counting function, often denoted as pi(N).</p><p>pi(N) is equal to the number of prime numbers less than or equal to N. For example,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/188/1*rGJMczr4tkn9cqOblI18cw.png" /><figcaption>Figure 31: There are 25 prime numbers less than or equal to 100. Source: Latex by author.</figcaption></figure><p>The Prime Number Theorem states that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/252/1*Kjmmd9uLPvdYU4cDVSzv0Q.png" /><figcaption>Figure 32: The Prime Number theorem provides an approximation for the PCF. Source: Latex by author.</figcaption></figure><p>We won’t prove it here, as it uses more advanced and non-elementary number theory. In our above example of N=100 we have,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/290/1*aYJyshPC_Re0yXgPJHGS6Q.png" /><figcaption>Figure 33: Plugging in N=100. Source: Latex by author.</figcaption></figure><p>We can visualize this result up to N=10000 easily in R.</p><p>Using the <em>RcppAlgos</em> package;</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4d13cb3196b915d2d068a6c0cf7e6956/href">https://medium.com/media/4d13cb3196b915d2d068a6c0cf7e6956/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cRwLGyr_JWHMmDlnzGJ8gw.png" /><figcaption>Image 5: In red is the line of the actual primes less than N. In blue is the estimate given by N/Log(N). Source: Created in R by author.</figcaption></figure><p>There remains many open problems in the field. One of the most famous unresolved problems is the Riemann Hypothesis. Essentially, the proving of RH would provide a known and very strict bound on the error term of the prime counting function.</p><p>We now have the basic results of elementary number theory. Mainly, the fundamental theorem of arithmetic and the infinite number of primes. This alone will form the basis of modern day cryptography.</p><p>Thank you for reading! I hope you learnt something new, number theory is truly an interesting field and has numerous real world applications. In my next article I will introduce and demonstrate how the field of cryptography uses and applies number theory to allow for secure communications.</p><h3>References:</h3><p>[1]Euclidean algorithm and Bezout’s algorithm. (2020, November 19). Mount Royal University. <a href="https://math.libretexts.org/@go/page/7534">https://math.libretexts.org/@go/page/7534</a></p><p>[2] Personal Notes from McGill Course <a href="https://www.mcgill.ca/study/2021-2022/courses/math-346">Math 346</a>, Number Theory(Winter 2017)</p><p>[3] <a href="https://en.wikipedia.org/wiki/Henryk_Iwaniec">Iwaniec, Henryk</a>; Kowalski, Emmanuel (2004). <em>Analytic Number Theory</em>. American Mathematical Society Colloquium Publications. <strong>53</strong>. Providence, RI: American Mathematical Society. <a href="https://en.wikipedia.org/wiki/ISBN_(identifier)">ISBN</a> <a href="https://en.wikipedia.org/wiki/Special:BookSources/978-0-8218-3633-0">978–0–8218–3633–0</a>.</p><p>[4]Jones, G. A., &amp; Jones, J. M. (1998). <em>Elementary number theory</em>. London: Springer.</p><p>[5] <a href="https://books.google.ca/books?hl=en&amp;lr=&amp;id=-9pg-4Pa19IC&amp;oi=fnd&amp;pg=PR11&amp;dq=elementary+number+theory&amp;ots=AvXROvrCnZ&amp;sig=2GppDnsko8zW_cFOsZT4KZ6iLqw&amp;redir_esc=y#v=onepage&amp;q=elementary%20number%20theory&amp;f=false">Elementary Number Theory with Applications</a> by Thomas Koshy, 2002.</p><p>[6] <a href="http://www.math.hawaii.edu/~pavel/gcd.pdf">http://www.math.hawaii.edu/~pavel/gcd.pdf</a></p><p>[7] <a href="https://www.youtube.com/watch?v=pp06oGD4m00">Terrence Tao Lecture <em>Small and Large Gaps Between the Primes</em></a></p><p>[8] <a href="https://www.cs.cornell.edu/courses/cs2800/2017sp/lectures/lec29-division.html">https://www.cs.cornell.edu/courses/cs2800/2017sp/lectures/lec29-division.html</a></p><p>[9] Primitive Roots. <em>Brilliant.org. </em>Retrieved 16:36, October 14, 2021 from Brilliant.org.</p><p>[10] <a href="https://cran.r-project.org/web/packages/RcppAlgos/index.html">https://cran.r-project.org/web/packages/RcppAlgos/index.html</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e598b2300ac3" width="1" height="1" alt=""><hr><p><a href="https://www.cantorsparadise.com/introduction-to-elementary-number-theory-e598b2300ac3">Introduction to Elementary Number Theory</a> was originally published in <a href="https://www.cantorsparadise.com/">Cantor’s Paradise</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Learn the Preliminary Details Behind Support Vector Machines]]></title>
            <link>https://medium.com/data-science/learn-the-preliminary-details-behind-support-vector-machines-f51599f0772e?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/f51599f0772e</guid>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Tue, 08 Dec 2020 21:13:55 GMT</pubDate>
            <atom:updated>2020-12-08T23:18:42.498Z</atom:updated>
            <content:encoded><![CDATA[<h4>With Examples in R</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tksHlU8s3YPRnHip2ojENw.jpeg" /><figcaption>Vlad Shapochnikov via <a href="https://unsplash.com/photos/uPJzWWhPcP4">Unsplash</a></figcaption></figure><h3>Introduction:</h3><p><em>Support Vector Machines </em>are a popular tool used in several branches of Machine Learning. In particular, they are extremely useful for binary classification. Support Vector Machines have their basis in the concept of separating hyperplanes, so it is useful to first be introduced to this concept.</p><p>In this article, I introduce the method of classification via separating hyperplanes. We start off simple and describe how even linear regression can be used to make simple binary classifications. We then move on to using separating hyperplanes and ‘<em>optimal’</em> separating hyperplanes. Finally, with this background, we are in the position to introduce support vectors and the powerful <em>Support Vector Machine</em>. We also include examples using R, and discuss how one can fit kernel based algorithms in R using the <em>kernlab (Kernel Based Machine Learning) </em>package.</p><p>Much of the mathematical details, and the toy example datasets in this article come from <a href="https://web.stanford.edu/~hastie/ElemStatLearn/"><em>The Elements of Statistical Learning II edition (Hastie).</em></a> The data, and more information on the subject can be found on the textbook&#39;s website. The data can be downloaded from the data tab of the above link, where it is called “ESL.mixture”.</p><p>Let’s start with a simple. You can load in the following toy dataset into R from <a href="https://web.stanford.edu/~hastie/ElemStatLearn/data.html">this link</a>. The dataset consists of observations each with a pair of coordinates (x1,x2). Each observation also has an outcome, y, which we denote in the plot by colour (red (y=1) or blue (y=0) denoting its class).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/81b5c5de319dbf803eea3b7e57d8e3f4/href">https://medium.com/media/81b5c5de319dbf803eea3b7e57d8e3f4/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*2PS3LQj6X2GHrXpDVfvQOg.png" /><figcaption>Figure 1: A Toy example of data from an unknown distribution (x1,x2) where the class is indicated by colour (blue y=0, or red y=1). Image Citation: Created in R by author.</figcaption></figure><p>Figure 1 is a plot of the toy example dataset. It appears that red and blue points are somewhat separated, but clearly there would be no way to perfectly separate the classes with just a simple line.</p><p>Suppose we were given a new observation with coordinates (x1,x2). How should we classify this new point? Clearly, the location of the coordinates will help inform our choice of assigning our new observation to red or blue.</p><p>One simple method would be to fit a linear regression line to the data and classify the new point based off if the point lied above 0.5, or below it.</p><p>If we want to classify based on the 0.5 threshold(the midpoint between the two classes), we could fit the linear regression line and solve in terms of x2; as seen in the below code and plot.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/923e1b77e1f7619a17743abb7018972c/href">https://medium.com/media/923e1b77e1f7619a17743abb7018972c/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*ipSU3BGkIsbkOY94Zj8IiA.png" /><figcaption>Figure 2: The same toy example of data from an unknown distribution (x1,x2) where the class is indicated by colour (blue y=0, or red y=1). We fit a linear regression to the response and defined new classifications based on if the new point was above or below the line. Image Citation: Created in R by author.</figcaption></figure><p>We could then classify a point based on whether it was located above (red) or below (blue) the regression line.</p><p><strong>But is this the optimal way to make classifications? </strong>Well, we don’t know the true underlying distribution, so it would be impossible to conclude definitively. But in reality, it would be extremely unlikely that this simple classification would be ideal.</p><p>We come back to this toy dataset later on, but for now, we move to the more general problem.</p><h4>Separating Hyperplanes:</h4><p>As we noted in the toy example dataset, no line could perfectly separate our two classes. But consider a more simple case, where such a line could actually be fit.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/387/1*vssX0FdKX_rcIfrs5kO5qw.png" /><figcaption>Figure 3: A different simple example dataset. Shown in orange is the linear regression line and in blue are two separating hyperplanes found using the perceptron algorithm. Image Citation: This is Figure 4.14 in the Elements of Statistical Learning II.</figcaption></figure><p>Let&#39;s go back to <a href="http://homepages.math.uic.edu/~lreyzin/papers/rosenblatt58.pdf">Rosenblatt 1958</a> and the Perceptron. The perceptron algorithm can be used to find separating hyperplanes (provided one exists). The method for which they find the plane involves stochastic gradient descent.</p><p>Figure 3 demonstrates three lines fit to a simple two class dataset. The orange line is the least squares solution fit to the data, and it doesn’t even separate the two classes. The two blue lines both perfectly separate the classes, but are not identical. This is due to the fact that the perceptron algorithm finds one solution and then stops (due to random starts it can obtain different solutions).</p><p>Using the perceptron algorithm is better then just using simple linear regression, and can actually separate the classes (provided it is possible). However, it still encounters problems. For one, it doesn’t tell us anything about the multiple different lines it can find (are some ‘better’)? And also, if no perfect separating hyperplane exists, the algorithm does not converge.</p><h4>Optimal Separating Hyperplanes:</h4><p>We saw that the perceptron can find a separating hyperplane (provided one exists). However, it doesn’t tell us anything special about the one it happens to converge on. The next big improvement is from Vapnik (1996), which forms the basis for the support vector machine. Vapnik described not only how to find the unique separating hyperplane, but how to find the <em>optimal separating hyperplane </em>or the<em> ‘</em><a href="https://en.wikipedia.org/wiki/Perceptron"><em>perceptron</em></a><em> of optimal stability’.</em> This has been shown to outperform simple hyperplane separation and often results in lower test error.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/401/1*V2F0SzgOw4HLHsyx66gMXA.png" /><figcaption>Figure 4: The same simple dataset as in Figure 3, fit with the optimal separating hyperplane. The three blue squares are points that lie on the boundary of the margin, and are known as support vectors. Image Citation: Figure 4.16 in The Elements of Statistical Learning II.</figcaption></figure><p>Figure 4 illustrates the optimal separating hyperplane classifier fit to the simple dataset. Three points lie directly on the outside of the margin, and are known as the <em>support points</em>. The red line is the solution from logistic regression, which is very similar, although not identical.</p><h4>Support Vectors:</h4><p>Figure 4 was a simple way to visualise the basic support vector machine. We now describe the details surrounding the support vector classifier, and what can be done when there is no way to perfectly separate the data.</p><p>In simple terms, SVMs find an optimal hyperplane to separate distinct classes. In the most basic case, this would be finding the line that best separates two classes. By ‘best separates’, we mean that the <em>margin</em> is maximised. The margin is the distance from the closest point in each of the two classes. Classifying new observations then depends on their location with respect to the decision boundary.</p><p>Consider a set of N training examples:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/187/1*-wN12hPBA0Zxu0rxIaZfNA.png" /><figcaption>Figure 5: A set of N training examples.</figcaption></figure><p>Where there are only two classes for which y belongs to, -1 or 1. That is;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/114/1*hQTSREKbhm0u3A5ELVN1uA.png" /><figcaption>Figure 6: The two classes that each training set can belong to.</figcaption></figure><p>The support vector works by creating a decision boundary (hyperplane) such that the ‘margin’ is maximised:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/233/1*qo5VJ8xHsaZhLZslqbqjwQ.png" /><figcaption>Figure 7: The decision boundary that we wish to form.</figcaption></figure><p>Points that lie directly on the outside lines (and thus are key in determining the margin), are known as the <strong><em>Support Vectors.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/341/1*IethXXz712twjbzXAEuplQ.png" /><figcaption>Figure 8: This image shows a simple support vector classifier. We classify new points depending on their value of xtB+B. Image Citation: The Elements of Statistical Learning II (Figure 12.1).</figcaption></figure><p>New classes are thus predicted based on if they lie above or below the boundary (the solid middle blue line); i.e simply off their sign.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/228/1*rbZNnvYeQQZTKbpLYJEelg.png" /><figcaption>Figure 9: How we classify new observations (based off their sign). Image by Author.</figcaption></figure><p>When the data is linearly separable, we can perfectly separate the training data with a maximum margin hyperplane.</p><p>In cases in which we can’t separate perfectly, we have to allow for some violations. We then fit the model by using some cost function that allows for some misclassifications.</p><h4>Details:</h4><p>For those interested in more background details please read along, but feel free to skip this section if you are satisfied with knowing that the algorithm is solved using quadratic programming. The method in which this optimal hyperplane is found is not simple; It is a quadratic programming problem that involves Lagrange Multipliers. Thankfully, multiple packages in R and Python can do this automatically.</p><p>Essentially, we want to maximise the Margin M subject to the constraints that we lie on one side of the hyperplane or the other. Which can be simply written as a maximisation problem:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/364/1*tYoRUHJgIK6dOr-U8wemUw.png" /><figcaption>Figure 10: How the margin is maximised subject to constraints. Image by Author.</figcaption></figure><p>This is equivalent to the minimisation in terms of the parameters;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/354/1*ZnxP_J3NAAcrLFsZEIbScA.png" /><figcaption>Figure 11: The equivalent form that allows for a simpler calculation of the optimal hyperplane. Image by Author.</figcaption></figure><p>In fact, it is the hyperplane which produces the <em>maximum margin.</em></p><p><em>This is all solved numerically.</em></p><h3>Back to the Toy Data:</h3><p>Let’s return to the mixture example from the toy dataset we discussed above. In R, the package <em>Kernlab</em> allows us to easily fit support vector machines. We have to specify a few parameters.</p><p><strong>Type: </strong>We specify C-svc (the default setting) for SVM classification.</p><p><strong>Kernel:</strong> We want to first fit a linear kernel (linear decision boundary) so we use the <em>vanilladot</em> linear kernel</p><p><strong>C: </strong>The Cost Parameter (Determines how points around margin are treated). We try first with C=10000. Larger values of C focus the margin on points close to it, while smaller C focuses more on points in the outliers, far from the margin.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/de18c3b12e7a74d25d2308a74fc6a3ce/href">https://medium.com/media/de18c3b12e7a74d25d2308a74fc6a3ce/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*RPox3ZEqDWVuPalb28pShQ.png" /><figcaption>Figure 12: A plot of our linear SVM using C=10000. Image created in R by author.</figcaption></figure><p>The above plot visualises our linear support vector machine which aims to separate the two classes. Since it is not perfectly separable, we have a parameter C that acts as a regularisation parameter</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*kzShLXGB5Cx2BkdN3umBug.png" /><figcaption>Figure 13: Summary of our linear SVM. Image created in R by author.</figcaption></figure><p>The model obtains a training error of 0.27. Considering that the toy dataset was visually non-separable, that isn’t too bad. There are a total of 125 support vectors. These are points that line on the boundary or within the margin.</p><p>We try the same thing but with C=0.01;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*qhEk-zFAF4yZB6tgq1NSfw.png" /><figcaption>Figure 14: Another linear SVM fit but with C=0.01. Image created in R by author.</figcaption></figure><p>This produces a similar plot, but the training error is slightly reduced to 0.265. We have more support vectors now, 172. This is due to the fact that we have a wider margin for this particular C value.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*UiIQLX5zHiegHoLZJ4Gp-A.png" /><figcaption>Figure 15: Results of our second linear SVM. Image created in R by author.</figcaption></figure><p>Above we fit some linear Support Vector Machines. But our data didn’t look linearly separable. Can we improve on our 0.265 training error? The answer is yes. SVMs are popular for this reason, as they can be greatly improved and extended via what is known as the ‘kernel trick’ (which are just a form of basis expansions).</p><h3><strong>Basis Functions and the Kernel Trick:</strong></h3><p>Clearly our toy dataset was not linearly separable. One of the main applications of support vector machines is that we can easily extend them via the ‘kernel trick’. This involves transforming the initial observations, using some sort of dot-product like transformation and THEN finding the optimal separable hyperplane. Above, we simply worked with the observations as they came in the form (x1,x2).</p><p>But, suppose for each observation we instead worked with</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/286/1*JNijw0XnT08S_uvJyqwzhw.png" /><figcaption>Figure 16: The Gaussian or Radial Basis Function transformation. Image by Author.</figcaption></figure><p>This is known as the <strong>Radial Basis Kerne</strong>l and allows us to fit more complicated models.</p><p>Look what happens when we apply the simple radial basis function to our original data:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/081ad846aef749b5d8a6000f7ebee9c0/href">https://medium.com/media/081ad846aef749b5d8a6000f7ebee9c0/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*aASsLI6_VAday48l1p-MDA.png" /><figcaption>Figure 17: The results of applying the radial basis function to each set of observations. Image created in R by Author.</figcaption></figure><p>Which can then be fit linearly and back transformed to the original dimension. We specify our kernel now as ‘rbfdot’ (instead of linear as before).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2ce71a5e0ce628281f9f361528466656/href">https://medium.com/media/2ce71a5e0ce628281f9f361528466656/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*w_MvfZKE6zH6JjBQtIm_2Q.png" /><figcaption>Figure 18: Plot of SVM fit using the radial basis function (Gaussian Kernel) with a C=1. Image created in R by Author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*mLHGPGpiieAe11g3ayoMQg.png" /><figcaption>Figure 19: Summary of our toy data fit with a Gaussian Kernel. Image created in R by author.</figcaption></figure><p>Which has an even lower training error of 0.155. The number of support vectors is reduced to 115 as less points lie inside the margin. The Cost parameter C can be tuned using cross-validation if you want to search a grid of possible values, but C=1 is the default.</p><h3>Summary and Conclusion:</h3><p>Support Vector Machines are an important and useful tool that was originally used for binary classification. However, they can be applied to many machine learning algorithms. The history and method by which they were developed is also interesting. The mathematical details behind the SVM are solid and have a firm foundation in linear algebra. They are worthwhile algorithm for those interested in Data Science and Machine learning to study in more detail.</p><p>SVMs extend the idea of separating hyperplanes and find the optimal separating hyperplane. In low dimensions, this has an intuitive way to understand, in higher dimension, we can’t visualise it, but the math is a simple extension.</p><p>SVMs can be extended to a non-linear decision boundary using ‘kernel tricks’ (or basis expansions) to fit more complicated boundaries. Common other kernels include the Gaussian (Radial Basis Function). These methods work by transforming the data first so that we can fit what appears to be a linear boundary in the transformed input space.</p><p>Despite the theoretical background and more difficult interpretation in words, SVMs are widely used in industry. In particular, they find usage in medical related data, neurological imaging and more.</p><p>In this article, we considered the initial use of SVMs, which is to binary classification. However, SVMs are a topic of ongoing research and several extensions have been developed. You can use SVMs to perform regression and even use them to perform clustering via unsupervised learning.</p><h3>Thanks for Reading!</h3><p>Did you enjoy this article or learn something new? If so, please check out my other Medium articles and consider sharing the article or leaving a clap. If you would like to connect, add me on <a href="https://www.linkedin.com/in/robert-sneiderman-359710188/">LinkedIn</a>. Also please leave any comments/corrections/questions below, and check out the sources.</p><h4>Github Code:</h4><p><a href="https://github.com/Robby955/LearningSVM">Robby955/LearningSVM</a></p><h3>Sources:</h3><p>[1] Hastie, Tibshirani, Friedman (2009). <em>The Elements of Statistical Learning II.</em></p><p>[2] F Rosenblatt (1958).<em> The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain.</em></p><p>[3] V Vapnik (1996). <a href="http://papers.nips.cc/paper/1238-support-vector-regression-machines.pdf">Support vector regression machines</a></p><p>[4] Noble, W. S. (2006). What is a support vector machine?. <em>Nature biotechnology</em>, <em>24</em>(12), 1565–1567.</p><p>[5] Furey, T. S., Cristianini, N., Duffy, N., Bednarski, D. W., Schummer, M., &amp; Haussler, D. (2000). Support vector machine classification and validation of cancer tissue samples using microarray expression data. <em>Bioinformatics</em>, <em>16</em>(10), 906–914.</p><p><a href="https://www.sciencedirect.com/topics/neuroscience/support-vector-machine">[</a>6] Geron, Aurelien (2020). Hands-On Machine Learning with Scikit-Learn, Keras and TensorFlow.</p><p>[7] A Karatzoglou, A Smola (2004). Kernlab- An S4 Package for Kernel Methods in R.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f51599f0772e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/learn-the-preliminary-details-behind-support-vector-machines-f51599f0772e">Learn the Preliminary Details Behind Support Vector Machines</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Best Books for those Serious about Machine Learning]]></title>
            <link>https://rob-sneiderman.medium.com/the-best-books-for-those-serious-about-machine-learning-b1130a13c6aa?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/b1130a13c6aa</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[books]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Sat, 28 Nov 2020 01:54:07 GMT</pubDate>
            <atom:updated>2020-11-28T21:32:16.911Z</atom:updated>
            <content:encoded><![CDATA[<h4>Two Free Books you should have on your Digital Shelf.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WTPzavWLajEvNtWVSIW2aw.jpeg" /><figcaption><a href="https://unsplash.com/@chilledinlife">Rashtravardhan Kataria</a> via Unsplash</figcaption></figure><p><strong>Are you serious about Machine Learning? Do you want to review the<em> </em>gritty details behind the algorithms?</strong></p><p>You may have forgotten that each Machine Learning algorithm has an in depth history, complete with a theoretical basis and justification that involves analysis, linear algebra and even proofs.</p><p>Well the good news is, two of the most comprehensive books in the subject are provided by the authors <em>free of charge.</em></p><p><strong>Lets get right to it</strong></p><p>In my opinion, one book on statistical and Machine learning stands above all the rest in terms of providing a comprehensive analysis.</p><h3><em>The Elements of Statistical Learning: Data Mining, Inference, and Prediction, II Edition.</em></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OUXsU3YU3jbtUfN8-Ktesw.jpeg" /><figcaption>My Copy of EOSL.</figcaption></figure><p>This book covers in depth all the common algorithms (and the not so common), from linear and logistic regression, bagging and boosting, neural networks and unsupervised learning. Plus, it has tons of coloured images, tables and plots.</p><p>Also, the book refers to several datasets, which are freely available on the book website. The book works with <strong>R</strong> and so provides an opportunity for you to brush up on your <strong>R </strong>skills by trying to recreate the results in the book.</p><p><em>Hastie, Tibshirani and Friedman</em> are LEGENDS in the Machine Learning world and inventors of multiple packages and algorithms.</p><p>I like hard copies, but no worries. <a href="https://web.stanford.edu/~hastie/ElemStatLearn/">Whats best? The Authors of this textbook offer the PDF version online for free!</a></p><p><em>Note:</em> If you find The Elements of Statistical Learning to difficult, try the more introductory book from the same authors; <a href="http://faculty.marshall.usc.edu/gareth-james/ISL/"><em>An Introduction to Statistical Learning.</em></a></p><p>. . . . . . .</p><p>While The Elements of Statistical Learning does touch on Neural Networks, the next book covers them in <em>detail.</em></p><h3><em>Deep Learning</em></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iQhlwohW3gym2FLCrm9iXw.jpeg" /><figcaption>My Copy of the Deep Learning Textbook</figcaption></figure><p>This textbook provides a fully comprehensive and theoretical justification for deep learning and neural networks. Ian Goodfellow is also a legend in the field, and is the creator of Generative Adversarial Networks. This book also starts off with a review of important Linear Algebra and numerical methods. I found these sections very useful, as you&#39;ll be needing them!</p><p>Indeed, this textbook also has a website, where the authors offer a free <a href="https://www.deeplearningbook.org/">digital version.</a></p><p>…………</p><p>But just perfecting the theoretical details won’t get you very far. You need to be able to program and code these algorithms. That is why the third book I recommend is:</p><h3><em>Hands On Machine Learning with Scikit-Learn And TensorFlow</em></h3><p>This is also an excellent resource which works through all the common algorithms in Python, mostly deriving them from scratch. It also hosts a GitHub with much of the code so that you can compare.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zsqevtmHfbTVcL58LoYlZg.jpeg" /><figcaption>My Copy of Hands on Machine Learning</figcaption></figure><p>This book isn’t offered for free, but can be purchased online or by Amazon. However, the GitHub and code is free and can be accessed by anyone.</p><p>………….</p><p>Master the first two comprehensive books and you will have a near research level understanding of Machine Learning. After working through the Python book, you will also have a good understanding of the current implementations such as Deep Learning with TensorFlow.</p><p>Have you already done that? Well, you are in a great position to review and implement research papers, such as the paper from Google on the <a href="https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/43022.pdf">Inception Network</a>. You also will want to supplement your learning regarding Natural Language Processing, Time Series and Generative Adversarial Networks, as these topics are not covered in as much detail in these books.</p><p><strong>Thanks for Reading!</strong></p><p><strong>Good luck~</strong></p><p><strong>Where to buy them:</strong></p><ul><li><a href="https://www.amazon.ca/Elements-Statistical-Learning-Inference-Prediction/dp/0387848576">The Elements of Statistical Learning<em> </em></a><em>II</em></li><li><a href="https://www.amazon.ca/Deep-Learning-Ian-Goodfellow/dp/0262035618/ref=pd_lpo_14_t_1/133-6005130-6117801?_encoding=UTF8&amp;pd_rd_i=0262035618&amp;pd_rd_r=36059406-f3fe-408a-a903-a1f7974d978e&amp;pd_rd_w=MJOyG&amp;pd_rd_wg=mJXZg&amp;pf_rd_p=256a14b6-93bc-4bcd-9f68-aea60d2878b9&amp;pf_rd_r=FEDX9N2TF9HC4WJ3G2T7&amp;psc=1&amp;refRID=FEDX9N2TF9HC4WJ3G2T7"><em>Deep Learning</em></a></li><li><a href="https://www.amazon.ca/Hands-Machine-Learning-Scikit-Learn-TensorFlow/dp/1492032646/ref=pd_lpo_14_img_0/133-6005130-6117801?_encoding=UTF8&amp;pd_rd_i=1492032646&amp;pd_rd_r=1d8bb4e2-dd7c-418b-b3dc-16b02bbd2d4f&amp;pd_rd_w=OoMEE&amp;pd_rd_wg=sFZef&amp;pf_rd_p=256a14b6-93bc-4bcd-9f68-aea60d2878b9&amp;pf_rd_r=X5Q8CNGE50C2NJ173KMG&amp;psc=1&amp;refRID=X5Q8CNGE50C2NJ173KMG"><em>Hands on Machine Learning with Sci-kit learn and TensorFlow</em></a></li></ul><p><strong>Websites:</strong></p><ul><li><a href="https://web.stanford.edu/~hastie/ElemStatLearn/">The Elements of Statistical Learning.</a></li><li><a href="https://www.deeplearningbook.org/">Deep Learning</a></li><li><a href="https://github.com/ageron/handson-ml">Hands on Machine Learning.</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b1130a13c6aa" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[From Logistic Regression to Basis Expansions and Splines]]></title>
            <link>https://medium.com/data-science/from-logistic-regression-to-basis-expansions-and-splines-74d6bb3b8dc6?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/74d6bb3b8dc6</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[editors-pick]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Fri, 27 Nov 2020 19:31:06 GMT</pubDate>
            <atom:updated>2020-11-28T04:29:00.646Z</atom:updated>
            <content:encoded><![CDATA[<h4>Sometimes Linearity is not sufficient</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/634/1*dc2wS-urFiTe3nbHRjy6kw.jpeg" /><figcaption><a href="https://unsplash.com/@jannerboy62">Nick Fewings</a> via Unsplash</figcaption></figure><h3>Introduction:</h3><p>Logistic Regression is a common method used for fitting a binary or categorical response variable. But did you know that if you are not careful, logistic regression can miss out on important features?</p><p>In this in depth article, we will use the <a href="https://web.stanford.edu/~hastie/ElemStatLearn/datasets/SAheart.info.txt">South African Heart Disease data</a>, in combination with Chapters 4 and 5 of <em>The Elements of Statistical Learning II </em>to demonstrate why you need to be careful when applying logistic regression. We will also use this example as a starting point to introduce basis functions and splines.</p><p>In particular, we will learn about non-linearity, and how non-linear features can be incorporated into models. It will be fun, so, if you want to learn more intermediate statistical techniques, or are just looking for a review, please read along. The code used can be found on my <a href="https://github.com/Robby955/SAHeartDisease">github</a>.</p><h3>The Data:</h3><p>The<em> South African Heart Disease</em> dataset comes from a real 1983 retrospective study and consists of 462 observations, with the response of interest being Myocardial Infarction, or coronary heart disease (chd) (0/1 or no/yes). The dataset includes several numeric predictors such as Systolic Blood Pressure (sbp), Total Kilograms of Tobacco smoked (tobacco), obesity, alcohol, ldl, and age. There is also a binary factor variable (famhist (Present or Absent)).</p><p><strong>Which predictors do you think will be most significant when modelling? Try to choose some before continuing.</strong></p><p>We will now demonstrate the general approach that one might take for creating a model for chd. We will start with the usual first steps, examining the data and checking out the predictors.</p><h3>Linear Methods:</h3><p>Firstly, you should always examine structured data if possible. R comes with the ‘View’ function which allows us to conveniently see what our data looks like. (Note, we remove predictors adiposity and typea as these were not used in the reviews/books).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/47d941be6817cd849a273b5f925ef88f/href">https://medium.com/media/47d941be6817cd849a273b5f925ef88f/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/694/1*Q6bUYZbEPmGDcAJakzyMXg.png" /><figcaption>Figure 1: The first 20 observations from the South African Heart Disease dataset. Image by Author.</figcaption></figure><p>After looking at the data in a basic form, we want to get an idea about how our predictors are correlated with one another, and how they are correlated with the response. We can do this using a pairs plot, which is also built into R with the ‘pairs’ function. We colour our points according to whether the patient was healthy (black points) or had a heart attack (red points).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*p7Sv5rzQwy-Y58jqSiMZvg.png" /><figcaption>Figure 2: Pairs plot of the predictors, black represents healthy individuals, red indicates those who had a heart attack (chd). Image by Author.</figcaption></figure><h3>Logistic Regression:</h3><p>To classify the response, chd, we are simply trying to classify a binary response. We thus attempt to model the probability that our response belongs to one group, given the predictors X.</p><p>We model the so called logit, this ensures that our estimates remain in the interval [0,1] as we are modelling a probability.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*gUhjSb2ji87dq-vGn_FhZA.png" /><figcaption>Figure 3: The general form of modelling using logit odds. Image by Author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*cNjxQTl5jtuaZTOonlqSkw.png" /><figcaption>Figure 4: Taking exp of both sides. Image by Author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/357/1*Ug3bAC9N1z2WQdEUBTj5QA.png" /><figcaption>Figure 5: Simplifying the terms. Image by Author.</figcaption></figure><p>Logistic Regression is the usual go to method for problems involving classification. R allows for the fitting of general linear models with the ‘glm’ function, and using family=’binomial’ allows us to fit a response. Logistic Regression models are often fit using maximum likelihood using iterated reweighed least squares.</p><h3>Fitting Logistic Regression:</h3><p>Logistic Regression can be fit using iterated reweighed least squares or minimisation of a cost function. In R, we can fit logistic regression for a binary response using the ‘glm’ function and specifying the family as ‘binomial’.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6731d5d2c98005b0b14c6d917ae93d02/href">https://medium.com/media/6731d5d2c98005b0b14c6d917ae93d02/href</a></iframe><p>Here is the result of naively applying logistic regression to the heart data:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/596/1*hv5sdt7ROts8Yklivhtjng.png" /><figcaption>Figure 6: Applying logistic regression on the entire dataset provides these estimates and standard errors. Stars indicate significance. Image by Author.</figcaption></figure><p>Think back to the question I asked about choosing some important variables. It is very likely you chose famhist (that would be correct), but you also probably choose one of obesity or blood pressure (sbp). We know that those definitely have an impact on heart disease, so why is logistic regression indicating these are not significant predictors?</p><p>This example helps illustrate the problem of colinearity. According to Figure 6, obesity has a negative estimate and is not significant, which seems to go against all that we know from medical science. Also, according to the Figure 6, systolic blood pressure is not significant, which seems odd. The issue is, we have correlation. Modelled independently, sbp and obesity have negative signs and are significant.</p><p>Let us apply backward step selection, which is recommended when you believe there is correlated predictors. R has the built in ‘step’ function.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e1b935f5aa8511ad2f69c2dc8f64e2b0/href">https://medium.com/media/e1b935f5aa8511ad2f69c2dc8f64e2b0/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/596/1*8ML3Dgfi_O0_9Ur2CeBlUQ.png" /><figcaption>Figure 7 : Applying backward selection on AIC criteria leaves us with less predictors, but all are significant. Image by Author.</figcaption></figure><p><strong>Our final model apparently does not include obesity or sbp!</strong></p><h4><strong>Interpreting coefficients:</strong></h4><p>Before we move on, it is worth it to review how to interpret the summary table (Figure 7). The estimate for tobacco is 0.0807 with a standard error of 0.0255. Since tobacco was measured in total lifetime usage in kilograms, a 1 unit increase in tobacco represents an exp(0.0807)=1.084 increase in logit odds for chd. That is an 8.4% increase in heart attack! We can also calculate exp(0.0807+/ 2*0.255)=(1,03,1.14) to get the 95% confidence interval, so it ranges from a 3% to a 14% increase.</p><p><strong>But are we done?</strong> Does obesity and sbp really not have an impact on heart attack? If we stopped there, our model still might be okay. But it seems something is going wrong. The reason is that above we fit linear logistic regression. But there are NON linear features. To understand this, we need to understand basis expansions. Come along.</p><h3>Non-Linearity: Basis Expansions and Splines</h3><p>Above we saw that simply using linear functions to model our response didn’t seem to fully address our concern. Moreover, ‘ reality’ or the ‘true function’ is almost never linear, so what are the chances that fitting a model using only linear methods will be sufficient? True, linear models are still wildly popular and useful. They are certainly necessary, but are they sufficient?</p><h3>Basis Expansions:</h3><p>When we fit linear models such as linear regression or linear logistic regression we modelled our function in the form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/181/1*quIrurDzsTWDiQmD7yZGxg.png" /><figcaption>Figure 8: The general form of a linear model. Image by Author.</figcaption></figure><p>To model non-linearity, we <em>don’t</em> mean our weights β. We instead refer to the terms, or the basis functions, multiplying the weights;</p><p>That is, we form models like this instead;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/191/1*ze8lsBT5xDJRdZZzX_kHTQ.png" /><figcaption>Figure 9: The general form of a model made using basis expansions. Image by Author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/165/1*sobbLmuFL_DqSrVKmF85mw.png" /><figcaption>Figure 10: Are basis function maps from a higher dimensional space to R. Image by Author.</figcaption></figure><p>We will see why this is useful and how it can be implemented.</p><p><strong>Local Fitting:</strong></p><p>Suppose <strong>X</strong> is a one-dimensional set of observations. By separating the domain of <strong>X</strong> into adjoining regions, and fitting a polynomial to each region separately, we can start to get at the idea of fitting more complicated functions.</p><p>For example, see the Figure below which shows the division of the domain of <strong>X</strong> into three regions, separated at points <strong>Ɛ1 </strong>and<strong> Ɛ2. </strong>These are often referred to as ‘knots’.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/353/1*mvQ1Xw1U33MXn8F8yBqpTA.png" /><figcaption>Figure 11: Image Citation: Elements of Statistical Learning II. This image shows piecewise constant models fit to each region with no constraints on continuity.</figcaption></figure><p>The function in blue represents some real function. The points around it were generated from the function and then adding noise. In practice, we receive noise and want to find the true underlying structure, the blue curve.</p><p>The green line indicate the model fit using the following three basis functions and least squares;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/1*mxrjG6tnwiDGdH85PXYeyA.png" /><figcaption>Figure 12: The most basic way we could fit the below curve, using piecewise constant fit and identity function. Image by Author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/202/1*t5yK_nbGR2Z6wWxRKLo5pg.png" /><figcaption>Figure 13: The model would be represented like this, with h as above. Image by Author.</figcaption></figure><p>The green lines indicate the least squares solution in each interval which is;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/105/1*apOuKZwpFDzZpANbnHCnMQ.png" /><figcaption>Figure 14: The solution for the weights for the piecewise linear solved using linear regression. Image by Author.</figcaption></figure><p>That is a very simple case, and clearly the fit is not great. Moving on, we could perform simple linear regression in each interval. This requires an additional three basis functions that allow us to model the slope term;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/433/1*O2J3wuH0fP5Ok-dEiox1fQ.png" /><figcaption>Figure 15: The three additional basis functions to allow for slope. Image by Author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/341/1*ZcFdC3Za2euyKSjcrOBDag.png" /><figcaption>Figure 16: Image Citation: The Elements of Statistical Learning II. This image shows simple linear regression applied in each interval.</figcaption></figure><p>And each solution is found using the simple linear regression formula for the weights as usual.</p><p>But we are still missing something. We want to enforce continuity. So we should make the constraints that we touch on the intervals;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/141/1*S-YaCiJQedzEgK88csZLEQ.png" /><figcaption>Figure 17: Constraint 1. Image by Author.</figcaption></figure><p>And;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/141/1*WvYqHHL9BY2Z__Z9-Xni8A.png" /><figcaption>Figure 18: Constraint 2. Image by Author.</figcaption></figure><p>Which results in the following fit:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/335/1*Bb6fAwgA_t1UcCC0TQ_clg.png" /><figcaption>Figure 19 : Image Citation: The Elements of Statistical Learning II. Simple Linear Regression with enforced continuity.</figcaption></figure><p>Which still doesn’t look great.</p><p><strong>Non-Linear:</strong></p><p>Above we considered fitting linear functions locally in each interval, but the major benefit of basis functions is we can also model non linear functions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/627/1*oT5f-UJCie5UDqPQujVemA.png" /><figcaption>Figure 20 : Image Citation: The Elements of Statistical Learning II.</figcaption></figure><p>The bottom right image is continuous and has continuous first derivative and a continuous second derivatives. This thus known as a <strong><em>CUBIC SPLINE.</em> </strong>The following six basis functions define a cubic spline.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/175/1*ZfQSBmJPY-RKjnexTwV8eQ.png" /><figcaption>Figure 21 : The six basis functions that define the cubic spline. Image by Author.</figcaption></figure><p>The top left shows polynomial regression fit to each interval. The top right shows polynomial regression with enforced continuity. The bottom left shows polynomial regression with enforced continuity and enforced continuity of the first derivative. The bottom right, the cubic spline has enforced continuity of the second derivative as well.</p><p>We have discussed the constraints, there is another constraint that forms what is known as the <em>natural cubic spline</em>, this constraint is that the function is linear<em> past the boundary knots</em>, two constraints each in both boundary regions, <strong>a <em>natural cubic spline </em>with K knots is represented by K basis functions. </strong>We will fit our SA heart data with predictors with natural cubic splines.</p><p>Now that we have reviewed basis functions and non-linearity, we can return to the South African Heart disease data! While before we modelled the logit just using the <strong>X </strong>terms in isolation, we now repeat but allow for the <strong>X</strong> terms themselves to be modelled by a natural spline. Thus our estimate for chd will have the form;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/581/1*ASnre727eUKrhFQEo2l3xQ.png" /><figcaption>Figure 22 : The form for coronary heart disease with basis functions of the predictors. Image by Author.</figcaption></figure><p>We fit each of our numeric predictors using a natural spline with four basis functions. Notice that sbp and obesity are non-linear.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/579/1*2AgICPbhcwwAyIiE8uancA.png" /><figcaption>Figure 23: Image Citation: The Elements of Statistical Learning II.</figcaption></figure><p>We then created a logistic regression using the expanded predictors, which included the non-linear terms.Instead of simply multiplying the coefficient by itself by a weight, we multiply a weight by the BASIS function of the parameter, with the basis function being a non-linear fit using splines of that variable! We then used the drop function to remove terms that were not significant. You can fit spline terms in R with the ‘ns’ function. Input the df to tell R how many basis functions you want the spline to fit.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b0167b322b313cae40b539eb96b4511f/href">https://medium.com/media/b0167b322b313cae40b539eb96b4511f/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/631/1*4jCHeuZXsG8VtfGfkPLwQw.png" /><figcaption>Figure 24 : Final logistic regression model after applying backward stepwise selection to a model which included splines. Image by Author.</figcaption></figure><p>Our final model includes higher order terms, including obesity and sbp! It turns out, indeed they were important, but they were lost by not considering that they had a non-linear impact.</p><p>We can confirm they are important in the model by seeing what happens if we remove them from the model.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/da59dab7c735ca6e3e880f3137af5c22/href">https://medium.com/media/da59dab7c735ca6e3e880f3137af5c22/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/556/1*S8rrJG7eEF2y66M8Dcqetw.png" /><figcaption>Figure 25: Indeed, we shouldn’t drop any of these features. Image by Author.</figcaption></figure><p>Figure 25 summaries the Likelihood ratio test when a spline term is deleted from the model. Notice, removing ‘no’ terms keeps the AIC the lowest. Removing any other spline terms raises the AIC. Hence keeping obesity and sbp is indeed useful.</p><p>Be careful using simple linear logistic regression! It may miss out on non-linear features, and it has issues with correlation among predictors. Splines are a way to fit non-linear features and the LRT (Likelihood Ratio Test) can tell you the impact of removing higher order splines from model.</p><p><strong>So why did we see an increase in heart attack at low values of sbp and obesity?</strong> It turns out this was due to the method of the original study, it was a <strong>retrospective study,</strong> and measurements were made after a heart attack had occurred. Hence, patients had already begun to fix their lifestyle (weight and blood pressure). For example, they had a heart attack and so were extra diligent to lower obesity, this likely explains it!</p><h3>Extras: Multidimensional Splines</h3><p>Above we studied one-dimensional splines. But indeed, they can be expanded to multiple dimensions. The details are a bit much for an article, but involves forming the<em> tensor product basis. </em>Below is an example of fitting a<em> thin plate spline </em>to three of the heart disease risk factors and representing the contour plot, the green and red points are the knots.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/666/1*D-KXoFjKLkUD622ff_pYpw.png" /><figcaption>Figure 26: Image Citation: The Elements of Statistical Learning II.</figcaption></figure><h3>Summary:</h3><p>In this article, we reviewed a common real dataset and saw how logistic regression can be fit to model a response variable. We also saw how logistic regression can fail to pick up on important features, especially when there is non-linearity or correlation in the predictors.</p><p>We also reviewed splines and basis functions, and saw how local polynomial regression can be used to fit better models. In our original model for heart disease, logistic regression missed out on obesity and sbp as important features. We had to consider non-linearity for our model to pickup the significance of these features.</p><p><strong>Thank you for reading!</strong></p><p>Also, if you liked this article, please check out my other Medium articles and consider leaving a clap or a comment, or sharing if you learnt something new.</p><p>If you want to connect, <a href="https://www.linkedin.com/in/robert-sneiderman-359710188/?originalSubdomain=ca"><em>add me on LinkedIn.</em></a></p><p><a href="https://web.stanford.edu/~hastie/ElemStatLearn/"><strong>Please see <em>The Elements of Statistical Learning II</em> for more.</strong></a><strong> Images from the textbook are reprinted with permission from </strong><a href="https://web.stanford.edu/~hastie/"><strong>Trevor Hastie.</strong></a></p><h3>Code:</h3><p>Github: <a href="https://github.com/Robby955/SAHeartDisease">https://github.com/Robby955/SAHeartDisease</a></p><h3>Sources:</h3><p>[1] Hastie, Tibshirani, Friedman (2009). <em>The Elements of Statistical Learning, II edition.</em></p><p>[2]<strong> </strong>Rousseauw et al, (1983).<em> South African Medical Journal.</em></p><p>[3] <a href="https://people.cs.clemson.edu/~dhouse/courses/405/notes/splines.pdf">https://people.cs.clemson.edu/~dhouse/courses/405/notes/splines.pdf</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=74d6bb3b8dc6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/from-logistic-regression-to-basis-expansions-and-splines-74d6bb3b8dc6">From Logistic Regression to Basis Expansions and Splines</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Quick Introduction to Time Series Analysis]]></title>
            <link>https://medium.com/data-science/a-quick-introduction-to-time-series-analysis-d86e4ff5fdd?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/d86e4ff5fdd</guid>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[editors-pick]]></category>
            <category><![CDATA[timeseries]]></category>
            <category><![CDATA[statistics]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Thu, 26 Nov 2020 02:04:34 GMT</pubDate>
            <atom:updated>2020-11-26T03:47:47.518Z</atom:updated>
            <content:encoded><![CDATA[<h4>Preliminary Details required for Forecasting.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/649/1*eqqg8E8zwwtuik3eolSRTw.jpeg" /><figcaption>Nathan Dumlao via <a href="https://unsplash.com/photos/5Hl5reICevY">Unsplash</a></figcaption></figure><p>In my first article on Time Series, I hope to introduce the basic ideas and definitions required to understand basic Time Series analysis. We will start with the essential and key mathematical definitions, which are required to implement more advanced models. The information will be introduced in a similar manner as it was in a <a href="https://www.math.mcgill.ca/dstephens/681/Math681-Syllabus.pdf">McGill graduate course on the subject</a>, and following the style of the textbook by <em>Brockwell and Davis.</em></p><h3>Introduction:</h3><p>A ‘<strong><em>Time Series’ </em></strong>is a collection of observations indexed by time. The observations each occur at some time t, where t belongs to the set of allowed times, <strong>T</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/114/1*YxYMQY2u5szC3rWjhq7ZuQ.png" /><figcaption>Figure 1: The general notation used to represent a times series Xt.</figcaption></figure><p><strong>Note:</strong> <strong>T </strong>can be discrete in which case we have a discrete time series, or it could be continuous in the case of continuous time series. Sometimes, we refer to one observation of the time series {Xt} as a <em>realisation of the series.</em></p><p>Examples of time series include the DOW Jones, a simple series indicating if it rained each day or not, or a GDP by year series.</p><p>A <strong>‘<em>Time Series Model’</em></strong><em> </em>for a Time Series {Xt} is a specification of the joint probability distribution of the model (however, often we only consider a model for the mean and first few<a href="https://en.wikipedia.org/wiki/Moment_(mathematics)"> moments</a>).</p><p>Except in special cases, a time series will have a defined and finite mean;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/145/1*xCCuYZY5ONBo6Nh67152iA.png" /><figcaption>Figure 2: Notation for the mean.</figcaption></figure><p>And provided higher level moments exist, the covariance of a time series at time ‘t’ and time ‘s’;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/470/1*hqkf6VyTNckXEgcSambrfA.png" /><figcaption>Figure 3: The Covariance of a time series Xt between two times.</figcaption></figure><p>The mean of the time series may depend on t, or it may not. Similarly, the covariance between two times may depend on t or not, it will become more clear with examples.</p><h3>Stationarity:</h3><p>A Time Series is said to be ‘<strong><em>weakly stationary’</em> </strong>if the following two conditions hold.</p><ol><li>The mean value of the time series does not depend on time.</li></ol><p>2. The Covariance between any two points the same distance apart is constant. (For example, the covariance between realisations three points away from each other should be constant regardless of t).</p><p><strong>Note:</strong> it will be useful to recall that variance and covariance can be linearly separated as follows;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/447/1*EjfeMvgjMPF6mIS34p_pPQ.png" /><figcaption>Figure 4: Covariance (and variance) can be expanded. This often helps in simplifying calculations.</figcaption></figure><p>If a Time Series is weakly stationary, the covariance between any two points will not depend on time. Thus, it will be constant, or only depend on how far away the two points are from each other. Weakly stationary series are much easier to forecast with, thus, much of time series analysis involves trying to reduce a more complicated series to a stationary one.</p><p><strong>Note: </strong>Strong Stationary requires that the entire distribution function does not change with time, which is a harder requirement to verify and meet. We thus focus on weak stationarity for now.</p><h4>Autocovariance Function (ACVF):</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/294/1*3VhWQ1kZJs1sqxEF-VH3vA.png" /><figcaption>Figure 5: The ACVF for a stationary time series does not depend on t.</figcaption></figure><h4><strong>Autocorrelation Function (ACF):</strong></h4><p>We actually more often work with the autocorrelation function of a time series. In particular, the ACF of a stationary time series is defined as;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/303/1*jTTOZV2l5FkU-Wjhi5uxxA.png" /><figcaption>Figure 6: The ACF for a stationary time series.</figcaption></figure><p>The above two definitions are working with well defined random variables. However, in practice we are working with real data, and so we do not know the theoretical ACVF or ACF. Thus we need to introduce their sample counterparts.</p><h3>Sample ACVF and ACF:</h3><p>It is much more common that we are working with data from an unknown distribution (i.e an observed dataset), so it is necessary to define the following: the sample mean, the sample autocovariance function and the sample autocorrelation. These will be used very often, and plotting them gives us an idea about our time series.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Yw3RVWPegclz8PRxtWHdTg.png" /><figcaption>Figure 7: The sample mean, sample autocovariance and sample autocorrelation. We can calculate these on observed data.</figcaption></figure><h3>Fundamental Time Series:</h3><p>Let us now begin to look at the fundamental theoretical time series that are used to build advanced models.</p><h3>IID Noise:</h3><p>One of the simplest examples of a time series is <em>IID noise </em>(independent identically distributed noise). This is a series, {X1,X2,..}, where each realisation Xt is independent and from some identical distribution such as the Normal(0,σ²).</p><p><strong>Is IID Noise weakly stationary?</strong></p><p>By definition, the expected value at any point is constant (zero). That is the first criteria.</p><p>And the covariance between any two points h units away is;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/433/1*VcRYVpUKASKOX4uazdChuA.png" /><figcaption>Figure 8: Covariance of IID noise.</figcaption></figure><p>Which does not depend on t (it only depends on h), which is the second condition. Thus, <strong>IID Noise is weakly stationary.</strong> We could also calculate the autocorrelation, which is simply 1 if h is zero, and 0 otherwise.</p><h3>Random Walk:</h3><p>Suppose now each Xt is an IID Normal(0,σ<strong> ²</strong>). Then, the <em>Random Walk</em> time series, {St}, is defined as;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/258/1*Hw6PmgJ8QChg_3QC7aOssA.png" /><figcaption>Figure 9: The Random Walk Time Series.</figcaption></figure><p>The definition makes it clear why it is called a random walk. The first element of the time series is just a random IID observation. We then add another random observation and repeat.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/433/1*TSlOFVD8NGZJqFsDgfKyOQ.gif" /><figcaption>Figure 10: Animation illustrating the random walk in two dimensions. At each step, we take a random step along a grid. <a href="https://commons.wikimedia.org/wiki/File:Random_walk_2500.svg">Gif Citation: Creative Commons.</a></figcaption></figure><p>Since each X is an IID Normal, the expected value any time t is equal to 0. Moreover, from the definition of variance;</p><p>Var(St)=E(St²)-E(St)²=E((St)²)=σ².</p><p>We can thus simplify the covariance between points t and t+h using the linear expansion</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/617/1*_vPv_Q60vngh79NpGBk1CA.png" /><figcaption>Figure 11: The covariance of points h units apart on a random walk. This depends on t.</figcaption></figure><p>Which depends on t, <strong>the random walk is not weakly stationary.</strong></p><h3>White Noise:</h3><p>White noise (sometimes called ‘static’) is similar to IID noise. If Xt is a sequence of <strong>uncorrelated</strong> zero mean observations with the same variance σ², we say it is White Noise. IID Noise is White Noise, but not all White Noise is IID.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/183/1*s62wUzywxDeZlbSnppkTZQ.png" /><figcaption>Figure 12: Notation used for White Noise. With specified mean and variance.</figcaption></figure><p>What is the difference between IID Noise and White Noise? You may notice the definition of White Noise doesn’t put limitations on the higher order moments, so it doesn’t say anything about E(X10) for example. But, for IID noise all moments are equal. Recall uncorrelated means that E(XtXs)=0 unless t=s.</p><h4>Extra Facts about White Noise:</h4><ul><li>White Noise has constant <em>power spectral density.</em></li><li>A single realisation of White Noise is known as a <em>random shock.</em></li></ul><h3>Moving Average Model:</h3><p>The moving average model is one of the most fundamental time series. We consider the most simple version, the MA(1) model, which can be written as the sum of white noise terms and a real parameter θ.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/211/1*-FpcFGr3f64Vv1hkCWRKCA.png" /><figcaption>Figure 13: Example of a MA(1) model. The Z terms are White Noise.</figcaption></figure><p>By the linearity of expectation, clearly the expectation of the MA(1) model is zero and thus constant for any t. The covariance between time t and time t+h can be derived; for h=0, this will be the variance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/585/1*WsWFQ6-VSFENMINNDpIaHA.png" /><figcaption>Figure 14: The covariance for realisation h=0 units apart is equivalent to the variance.</figcaption></figure><p>Otherwise, the covariance will be non-zero if and only if t and t+h are only 1 unit apart because;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/577/1*kLm590sAWpWu8U3UYDPb5A.png" /><figcaption>Figure 15: The MA(1) model covariance will be nonzero for realisation 1 unit apart.</figcaption></figure><p>Otherwise, the covariance will be zero, which can be confirmed by writing it out in the form of the covariance above. Thus:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/1*P_7Fb_IQsuYOGSXzrHl8nA.png" /><figcaption>Figure 16: The Autocovariance function for the MA(1) model.</figcaption></figure><p>We can also derive the Autocorrelation function, since we know the value of the ACVF at h=0. Mainly, γ(0)=σ²(1+θ²) so the ACF is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*Y9_gtYFg60Ih8nUywSXHng.png" /><figcaption>Figure 17: The Autocorrelation function of the MA(1) model.</figcaption></figure><p>Because the mean is constantly zero (independent of t) and the covariance is also independent of t, the <strong>MA(1) model is weakly stationary.</strong></p><p><strong>Note:</strong></p><ul><li>The MA(q) model is similar, but with the previous q additional terms.</li></ul><h3>Autoregressive:</h3><p>The autoregressive model is another fundamental time series that is used as a building block for more advanced series. <strong>For Autoregressive models, we make the assumption that {Xt} is weakly stationary.</strong> Autoregressive models depend on their previous values, as well as the addition of a scaled uncorrelated (Z and X are uncorrelated) White Noise term. The AR(1) series is the simplest;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/229/1*78p2k3kaDonSreYl7JyfrQ.png" /><figcaption>Figure 18: The AR(1) model.</figcaption></figure><p>To derive the characteristics of the series we note that since we assume {Xt} is stationary, it follows directly that the expected value of the series at any time t is exactly 0.</p><p>We can calculate the Autocovariance function for any points h units away;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/570/1*fKIuRh17QCyfrBZgRe7buw.png" /><figcaption>Figure 19: Since we are assuming weak stationarity, we can drop the additional argument to γ and just write h. We use the assumption that it is equal for all points h units apart to simplify.</figcaption></figure><p>By expanding and use the linearity of the covariance function we obtain the simplified form;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/159/1*wrWAxTaebSKw7c0pnw5fAQ.png" /><figcaption>Figure 20: The simplified covariance function for realisations h units apart on the AR(1) model.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/473/1*4c3HxKNx41Vd2D_HYZUBIg.png" /><figcaption>Figure 21: The variance of the AR(1) model using the assumption of weak stationarity.</figcaption></figure><p>Which solving for by bringing the terms over to one side of the equation gives us;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/155/1*BMWUrweo24IwiObl5vp8Iw.png" /><figcaption>Figure 22: The Variance of a realisation from the AR(1) model.</figcaption></figure><p>Since γ(h)=γ(-h) (covariance is symmetric), we can greatly simplify the autocorrelation (ACF):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/216/1*8fxbdca2cAx9sFvojikBSw.png" /><figcaption>Figure 23: The Autocorrelation of the AR(1) model for realisations h units apart.</figcaption></figure><p><strong>Extra Facts:</strong></p><ul><li>Just like MA(q) models, AR models can be expanded to an arbitrary number of terms, ie AR(q) models.</li><li>The AR model is not always stationary, in particular if it contains a <a href="https://en.wikipedia.org/wiki/Unit_root">unit root.</a> However, we assume for this article the common assumptions that we don’t contain a unit root (ϕ ≠ 1 ).</li><li>AR models are a special case of VAR models (Vector Autoregressive models).</li></ul><h3>Moving On:</h3><p>The moving average model, autoregressive model and White Noise form the basis for most of the actual time series used in practice. For example they are the building blocks of the ARMA and ARIMA models. Now that we have covered some of the theoretical time series, let&#39;s move onto time series in practice.</p><p>What are some common characteristics of a time series? Let us start with a simulated example to get the idea. Consider the following plot of a time series;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/612/1*R715oQLdfC3NqKpHqAhbLw.png" /><figcaption>Figure 24: A simulated time series with an upwards trend and seasonal component.</figcaption></figure><p>You may notice a few features of the plot;</p><ul><li>A generally increasing ‘trend’</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/627/1*T9zsnyOQMyvrpDKUz17VNQ.png" /><figcaption>Figure 25: The same time series with trend indicated by the red line.</figcaption></figure><ul><li>A repeating or ‘seasonal’ component</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/627/1*sg-TLh_OxzFjlKMGS06OvA.png" /><figcaption>Figure 26: Seasonal components are repeating at fixed intervals.</figcaption></figure><p>Trend and Seasonality make up a fundamental portion of a time series. Indeed, much of time series analysis and forecasting involves trying to understand the trend and seasonal components of the series. The importance of these two qualities lead to the ‘<strong><em>fundamental decomposition’.</em></strong></p><h3>Fundamental Decomposition:</h3><p>It is useful to think of a time series as consisting of three distinct parts. The <strong>Trend</strong>, the <strong>Seasonality</strong>, and the <strong>Random Noise.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/167/1*gh9kEQjhrAHHTAmPBm3cQg.png" /><figcaption>Figure 27: The Fundamental decomposition of a time series into trend (mt), seasonality (st) and a random component.</figcaption></figure><p>Where the expected value of the noise Yt is zero.</p><p><strong>Trend: </strong>Trend refers to the slope at an area of the time series. For example, we could be trending upwards in general over a certain time period. We could also be trending downwards. Series with trend will generally not be stationary, as the mean changes depending on the time.</p><ul><li>Dealing with trend involves <a href="http://www.maths.qmul.ac.uk/~bb/TimeSeries/TS_Chapter2_2.pdf">elimination by differencing </a>or the so called <em>backshift operator.</em></li></ul><p><strong>Seasonality: </strong>This is more than just a trend, it is a repeating pattern, it could be weekly, yearly or at some other fixed interval. Seasonality represents a repeated and clear change in a time series.</p><ul><li>Fitting seasonality can be done using <em>harmonic regression. </em>This involves, for example, fitting the series with many sines and cosines (a simplification).</li></ul><h3>In Practice:</h3><p>Up to now we have studied the mathematical details that cover the perfect time series. In reality, we will almost never have a series that is completely represented by a moving average model or an autoregressive model. These ideal models simply form the skeleton that we will use to fit more advanced models with. We will should demonstrate why the sample ACF is useful and what it can tell us about a timeseries.</p><p>Let us work through a few real examples and see what we can learn from them. We will use the R package ‘itsmr’ , which comes preloaded with several datasets.</p><h3>Australian Red Wine Data:</h3><p>This dataset (‘wine’ in the itsmr package) consists of 142 monthly observations of red wine sales in Australia (by 1000kL). Lets plot it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*-py8QksQVxprrIuL6cmUUQ.png" /><figcaption>Figure 28: Australian Wine Sales data. Plot made in R using the built in dataset wine. We notice an upwards trend and seasonal component.</figcaption></figure><p>Clearly there is a trend, and also a seasonal component. Overall, wine sales are increasing, and seasonally, wine sales increase in the summer and decrease in the winter months. Let&#39;s take a look at the sample ACF. R can calculate this automatically using the acf function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*y7QbwJBaaglUUBPTS6P_0w.png" /><figcaption>Figure 29: The sample ACF of the Australian Wine sales data up to the first 50 lags.</figcaption></figure><p><strong>Note</strong>: Slowly decaying sample acf (|ρ(h)|) is indicative of a trend and thus non-stationarity! This makes sense; we saw wine sales were trending upwards.</p><p>Periodic sample acf is indicative of seasonality in the time series. This also makes sense as we saw that wine sales soar in summer months and are at a minimum in the winter months.</p><p>To forecast with the Australian wine data, we would thus need to account for the trend and seasonality. Trend can usually be accounted for by applying a monotonic transformation such as the log transform. This should help in reducing the trend and make the data closer to a stationary series. Other methods include <em>smoothing</em> and <em>filtering.</em></p><p>The seasonal component also must be fit, usually this can be done using trigonometric functions via harmonic regression.</p><h3>Summary:</h3><p>This article introduced the basic mathematical details required to study time series analysis. The Moving Average Model, the Autoregressive Model and White Noise form the fundamental building blocks for more advanced series. We learnt about stationarity, which tells us about how a series changes over time. We also learnt about the important sample statistics you should look at when working with time series such as the sample autocorrelation function.</p><p>Finally, we discussed the common decomposition of a time series into a trend, seasonal and random component, and touched on why these are important.</p><p>In future articles, I hope to cover in more detail how we can actually forecast time series. The general steps are as follows;</p><ol><li>Plot the time series.</li></ol><p>2. Determine the trend and seasonal component. Consider transforming variables if needed (such as taking the log transformation).</p><p>3. Remove (subtract) the trend and seasonal components to get stationary residuals.</p><p>4. Fit the residuals</p><p>5. Perform forecasting on the residuals, then obtain forecasts for the original series by transformation</p><p>Congratulations, you have now learnt the <em>basics</em> of time series analysis. Once you are familiar with these fundamentals, you are in a position to move onto more advanced topics such as forecasting. In my next articles on Time Series I hope to introduce the ARMA and ARIMA models and discuss Box Jenkins, Holt Winters, Signal processing and Fourier Transforms and the ARCH/GARCH/FGARCH models.</p><p><strong>Thank you for reading!</strong> Did you enjoy this article or learn something new? If so, please consider checking out my other articles on medium, and consider giving the article a clap or a share. Also, please feel free to leave a comment or correction below.</p><h3>Sources:</h3><p>[1] Brockwell and Davis (2002) <em>Introduction to Time Series and Forecasting.</em></p><p>[2] TensorFlow in Practice Specialization (2020)— <em>Sequences, Time Series and Prediction </em>(Coursera via DeepLearning.AI).</p><p>[3] Pennsylvania State University <a href="https://online.stat.psu.edu/stat510/">STAT 510</a> Webpage.</p><p>[4] R Shumway, D Stoffer (2011) <em>Time Series Analysis and Its Applications. Third Edition.</em></p><p>[5] Fuller (2009) <em>Introduction to Statistical Time Series</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d86e4ff5fdd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/a-quick-introduction-to-time-series-analysis-d86e4ff5fdd">A Quick Introduction to Time Series Analysis</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An Introduction to Complex Analysis and Applications]]></title>
            <link>https://medium.com/analytics-vidhya/an-introduction-to-complex-analysis-and-applications-7af32522123b?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/7af32522123b</guid>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[applied-mathematics]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Tue, 17 Nov 2020 20:02:29 GMT</pubDate>
            <atom:updated>2024-01-16T11:07:55.150Z</atom:updated>
            <content:encoded><![CDATA[<h4>How imaginary numbers have a real impact.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*iNSdgXQfZyeYJq92hp2qew.jpeg" /><figcaption>Figure 1: A representation of a Complex Function. These can be created once you understand what a complex function is. The Color represents the argument of the complex function, while the brightness/hue is represented by the magnitude. Image Citation: <a href="https://commons.wikimedia.org/wiki/File:Color_complex_plot.jpg">Creative Commons.</a></figcaption></figure><h3>Introduction:</h3><p><strong>Let us start easy. </strong>What is the square root of 100? In other words, what number times itself is equal to 100? Easy, the answer is 10.</p><p>What is the square root of -1?</p><p>Well that isn’t so obvious. Since a negative number times a negative number is positive, how is it possible that we can solve for the square root of -1?</p><p>The answer is; <strong>we define it. </strong>And this isn’t just a trivial definition. Assigning this answer, <strong>i</strong>, the ‘imaginary unit’ is the beginning step of a beautiful and deep field, known as <a href="https://www.analyticsvidhya.com/blog/tag/complex/"><em>complex analysis.</em></a></p><p>So, why should you care about complex analysis? It turns out, that despite the name being ‘imaginary’, the impact of the field is most certainly real. From engineering, to applied and pure mathematics, physics and more, <a href="https://www.analyticsvidhya.com/blog/tag/complex/">complex analysis</a> continuous to show up. Moreover, there are several undeniable examples we will cover, that demonstrate that complex analysis is indeed a useful and important field.</p><p>This article doesn’t even scratch the surface of the field of complex analysis, nor does it provide a sufficient introduction to really dive into the topic. However, I hope to provide some simple examples of the possible applications and hopefully give some context.</p><p><strong>Note:</strong> Some of these notes are based off a tutorial I ran at McGill University for a course on <a href="https://www.mcgill.ca/study/2020-2021/courses/math-316">Complex Variables.</a></p><p><strong>Are you still looking for a reason to understand complex analysis? Maybe this next examples will inspire you!</strong></p><h3>History:</h3><p>Firstly, I will provide a very brief and broad overview of the history of complex analysis. I will also highlight some of the names of those who had a major impact in the development of the field. Note that this is not a comprehensive history, and slight references or possible indications of complex numbers go back as far back as the <a href="https://en.wikipedia.org/wiki/Hero_of_Alexandria#Bibliography">1st Century in Ancient Greece.</a></p><p><strong>Johann Bernoulli, 1702: </strong>The first reference of solving a polynomial equation using an imaginary unit.</p><p><strong>Abraham de Moivre, 1730</strong>: Developed an equation that utilized complex numbers to solve trigonometric equations, and the equation is still used today, the <em>De Moivre Equation.</em></p><p><strong>Leonhard Euler,</strong> <strong>1748:</strong> A True Mathematical Genius. The Euler Identity was introduced.</p><p><strong>Augustin Louis Cauchy 1812:</strong> Introduced the actual field of complex analysis and its serious mathematical implications with his ‘<a href="https://www.jstor.org/stable/1967922#metadata_info_tab_contents"><em>memoir on definite integrals’.</em></a></p><p><strong>Bernhard Riemann 1856:</strong> Wrote his <a href="https://www.usna.edu/Users/math/meh/riemann.html">thesis on complex analysis</a>, solidifying the field as a subject of worthy study. Also introduced the Riemann Surface and the Laurent Series.</p><p>As for more modern work, the field has been greatly developed by <strong>Henri Poincare, Richard Dedekind and Felix Klein.</strong></p><h3>Basics:</h3><p>I will first introduce a few of the key concepts that you need to understand this article.</p><p>We defined the imaginary unit <em>i</em> above. We also define ℂ, the complex plane. A Complex number, <strong>z,</strong> has a <em>real</em> part, and an <em>imaginary</em> part. That is, a complex number can be written as <strong>z=a+bi</strong>, where <strong>a</strong> is the real portion , and <strong>b</strong> is the imaginary portion (a and b are both real numbers). You may notice that any real number could be contained in the set of complex numbers, simply by setting b=0.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*Yh6Q_Mb4wTJXtjMKhecLNA.png" /><figcaption>Figure 2: An image demonstrating the complex plane. Image Citation: <a href="https://commons.wikimedia.org/wiki/File:Argandgaussplane.png">Creative Commons.</a></figcaption></figure><p>The complex plane, ℂ, is the set of all pairs of real numbers, (a,b), where we define addition of two complex numbers as (a,b)+(c,d)=(a+c,b+d) and multiplication as (a,b) x (c,d)=(ac-bd,ad+bc). Hence, (0,1) is the imaginary unit, i and (1,0) is the usual real number, 1. Writing (a,b) in this fashion is equivalent to writing a+bi, and once we have defined addition and multiplication according to the above, we have that ℂ is a <em>field</em>.</p><p><strong>Further Properties:</strong></p><p>If z=(a,b) is a complex number, than we say that the Re(z)=a and Im(z)=b. This in words says that the real portion of z is a, and the imaginary portion of z is b.</p><p>We also define the magnitude of z, denoted as |z| which allows us to get a sense of how ‘large’ a complex number is;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/149/1*jfBdSiDG4y31PE_8NXilqg.png" /><figcaption>Figure 3: The magnitude of a complex number , z.</figcaption></figure><p>If z1=(a1,b1) and z2=(a2,b2), then the distance between the two complex numers is also defined as;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/177/1*zadbjpzL-6wI2XeRAO5zWQ.png" /><figcaption>Figure 4: The distance between two complex numbers.</figcaption></figure><p>And just like in ℝ, the triangle inequality also holds in ℂ.</p><p>We also define the <em>complex conjugate</em> of z, denoted as z*;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/111/1*R1LAIjTjI6Ge5sIrXiD6kg.png" /><figcaption>Figure 5: The Complex Conjugate.</figcaption></figure><p>The complex conjugate comes in handy. Notice that Re(z)=Re(z*) and Im(z)=-Im(z*).</p><p>A complex function can be defined in a similar way as a complex number, with u(x,y) and v(x,y) being two real valued functions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/221/1*U1yx3KBEACOrtGtV17FOWA.png" /><figcaption>Figure 6: An example of how we write an arbitrary complex function. Image Source: Author.</figcaption></figure><p>Just like real functions, complex functions can have a derivative. The <em>Cauchy Riemann</em> equations give us a condition for a complex function to be differentiable. Mainly, for a complex function f decomposed with u and v as above, if u and and v are real functions that have real derivatives, the Cauchy Riemann equations are a required condition;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/98/1*DnY4Wa7dmWzHk_TAChKKSQ.png" /><figcaption>Figure 7: Cauchy Riemann Equations. Image Source: Author.</figcaption></figure><p>A function that satisfies these equations at all points in its domain is said to be <strong>Holomorphic.</strong></p><p>For example, you can easily verify the following is a holomorphic function on the complex plane ℂ, as it satisfies the CR equations at all points.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/236/1*WcjMrPh4k2Rmk9Yslzrjfg.png" /><figcaption>Figure 8: A holomorphic function on C. Image Source: Author.</figcaption></figure><p>Holomorphic functions appear very often in complex analysis and have many amazing properties. They also have a physical interpretation, mainly they can be viewed as being invariant to certain transformations.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/955/1*s3Q0_wFP_8wxJo2AbEKrkg.png" /><figcaption>Figure 6: A graphical interpretation of the Cauchy Riemann equations. Provided a function satisfies the CR, a vector X in the domain multiplied by a complex number z and being mapped by f, will be the same as mapping the multiplication of the vector X times z. Image Citation: <a href="https://commons.wikimedia.org/wiki/File:Cauchy-Riemann.png">Creative commons.</a></figcaption></figure><h3>Euler’s Formula:</h3><p>If you follow Math memes, you probably have seen the famous simplification;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/99/1*LDx93SRMCMua70f1R95sDQ.png" /><figcaption>Figure 9: The Famous Euler Equation. Image Source: Author.</figcaption></figure><p>This is derived from the <em>Euler Formula</em>, which we will prove in just a few steps.</p><p>Firstly, recall the simple Taylor series expansions for cos(z), sin(z) and exp(z). These are formulas you learn in early calculus; Mainly,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/295/1*3VfPlLYQFbLj-r0JsT_iYw.png" /><figcaption>Figure 10: The Taylor Expansions for Sin, Cos, and e. Image Source: Author.</figcaption></figure><p>Hence, using the expansion for the exponential with ix we obtain;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/542/1*wHIUu5IkOlVzGlSBoGf-UA.png" /><figcaption>Figure 11: Plugging in ix to the exponential expansion. Image Source: Author.</figcaption></figure><p>Which we can simplify and rearrange to the following</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*uGFh3MI9209eCdclPyxuQA.png" /><figcaption>Figure 12: Rearranging and simplifying the expansion. Image Source: Author.</figcaption></figure><p>And that is it! That above is the Euler formula, and plugging in for x=pi gives the famous version.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/304/1*Mw2RKoVFKUTeAM9XOt7_qQ.png" /><figcaption>Figure 13: The final result after simplification and plugging in x=pi. Image Source: Author.</figcaption></figure><h3><strong>Residues:</strong></h3><p>Residues are a bit more difficult to understand without prerequisites, but essentially, for a holomorphic function f, the residue of f at a point c is the coefficient of 1/(z-c) in the Laurent Expansion (the complex analogue of a Taylor series ) of f around c. These end up being extremely important in complex analysis. Several types of residues exist, these includes poles and singularities.</p><p>It turns out residues can be greatly simplified, and it can be shown that the following holds true:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/255/1*2yD5ZYNvZ3ycEjLvPvuy5g.png" /><figcaption>Figure 14: Residue Formula. Image Source: Author.</figcaption></figure><p><strong>Example:</strong></p><p>Suppose we wanted to find the residues of f(z) about a point a=1, we would solve for the Laurent expansion and check the coefficients:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/146/1*FhvoXMXynB5vclsPhMneXw.png" /><figcaption>Figure 15: A function for which we want to find the residues. Image Source: Author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/568/1*Jgf_QM8KWZUP4u50cJP6zA.png" /><figcaption>Figure 16: The Laurent Expansion about a=1 of f(z). Image Source: Author.</figcaption></figure><p>Therefor the residue about the point a is sin1 as it is the coefficient of 1/(z-1) in the Laurent Expansion.</p><h3>Contour Integration:</h3><p>The above example is interesting, but its immediate uses are not obvious. Well, solving complicated integrals is a real problem, and it appears often in the real world. Fortunately, due to Cauchy, we know the residuals theory and hence can solve even real integrals using complex analysis. I won’t include all the gritty details and proofs, as I am to provide a broad overview, but full proofs do exist for all the theorems.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*V1rtDoRjikhvCEWD5ZLMvw.png" /><figcaption>Figure 17: Image demonstrating a broad overview of the process of complex integration. ak are points contained within a closed path gamma, and all lie within a open section of the complex plane, U. Image Citation: <a href="https://commons.wikimedia.org/wiki/File:Residue_theorem_illustration.png">Creative Commons:</a></figcaption></figure><p><strong>Cauchy’s Integral Formula:</strong></p><p>For a holomorphic function f, and a closed curve gamma within the complex plane, ℂ, Cauchy’s integral formula states that;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/129/1*R_35V2IXVpg2-WG1BSRnwg.png" /><figcaption>Figure 18: A result of Cauchy Integral formula around a closed path. Image Source: Author.</figcaption></figure><p>That is , the integral vanishes for any closed path contained within the domain.</p><p>Cauchy’s Residue Theorem states that every function that is holomorphic inside a disk is completely determined by values that appear on the boundary of the disk.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/255/1*2yD5ZYNvZ3ycEjLvPvuy5g.png" /><figcaption>Figure 19: Cauchy’s Residue Theorem. Image Source: Author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/303/1*U67mKARGsHNCqb3RrZQ4kg.png" /><figcaption>Figure 20: Cauchy Integral Formula. I is a sum of the winding numbers, which we won’t worry about in this article. The integral around a closed path is a sum of the residues about singularities contained in the path (multiplied by 2pi and a winding number). Image Source: Author.</figcaption></figure><p><strong>Example:</strong></p><p>Suppose we wanted to solve the following line integral;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/89/1*gAsHosVIP_eFMFYAYbEKSQ.png" /><figcaption>Figure 21: An integral we wish to solve over some closed disk on the complex plane. Image Source: Author.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/328/1*zgW--phscWSPDhgpFfPs6A.png" /><figcaption>Figure 22: The formula for solving this integral involves finding its residues on C. Image Source: Author.</figcaption></figure><p>Since it can be easily shown that f(z) has a single residue, mainly at the point <strong>z=0 </strong>it is a ‘<em>pole</em>’, we can evaluate to find this residue is equal to 1/2. Thus, the above integral is simply <em>pi times i</em>.</p><h3>Solving Real Integrals:</h3><p>Suppose you were asked to solve the following integral;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/224/1*6GISpI9xNA9R82llGcGX7A.png" /><figcaption>Figure 23: A hard real valued integral.</figcaption></figure><p>Using only regular methods, you probably wouldn’t have much luck. It turns out, by using complex analysis, we can actually solve this integral quite easily. If you want, check out the details in this <a href="https://www.youtube.com/watch?v=-u0MmAr5XTs">excellent video that walks through it.</a> But the long short of it is, we convert f(x) to f(z), and solve for the residues. Then we simply apply the residue theorem, and the answer pops out;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/116/1*-1WjkoZD7oQVM_UpVvfzkQ.png" /><figcaption>Figure 24: The answer to the above integral.</figcaption></figure><h3>Proving the Fundamental Theory of Algebra:</h3><p>Proofs are the bread and butter of higher level mathematics. While it may not always be obvious, they form the underpinning of our knowledge.</p><p>The Fundamental Theory of Algebra states that every non-constant single variable polynomial which complex coefficients has <em>atleast</em> one complex root.</p><p>Using complex analysis, in particular the <a href="https://en.wikipedia.org/wiki/Maximum_modulus_principle">maximum modulus principal</a>, the proof can be done in a few short lines.</p><h3>Engineering:</h3><p>Indeed complex numbers have applications in the real world, in particular in engineering.</p><p><strong>Electrical:</strong></p><p>Complex numbers show up in circuits and signal processing in abundance. They are used in the Hilbert Transform, the design of Power systems and more.</p><p><strong>Nuclear:</strong></p><p>Complex analysis is used in advanced reactor kinetics and control theory as well as in plasma physics.</p><h3>Theoretical Physics:</h3><p>They also show up a lot in theoretical physics. Do you think complex numbers may show up in the <a href="https://en.wikipedia.org/wiki/Theory_of_everything">“<em>theory of everything</em>”</a>?</p><p><strong>Quantum Mechanics:</strong></p><p>Complex analysis is used to solve the CPT Theory (Charge, Parity and Time Reversal), as well as in conformal field theory and in the Wick’s Theorem.</p><p>Complex variables are also a fundamental part of QM as they appear in the Wave Equation.</p><p><strong>String Theory:</strong></p><p>Indeed, Complex Analysis shows up in abundance in String theory. In particular they help in defining the conformal invariant. I don’t quite understand this, but it seems some <a href="https://math.ucr.edu/home/baez/octonions/strangest.pdf">physicists are actively studying the topic.</a></p><h3>Data Science:</h3><p>Finally, Data Science and Statistics. The field for which I am most interested. I have yet to find an application of complex numbers in any of my work, but I have no doubt these applications exist. Some applications have already been made, such as using complex numbers to represent <a href="https://arxiv.org/pdf/1312.6115.pdf">phases in deep neural networks</a>, and using complex analysis to analyse sound waves in speech recognition.</p><h3>Summary:</h3><p>It is worth being familiar with the basics of complex variables. There are already numerous real world applications with more being developed every day. Despite the unfortunate name of ‘imaginary’, they are in by no means ‘fake’ or not legitimate. Complex analysis shows up in numerous branches of science and engineering, and it also can help to solidify your understanding of calculus. While we don’t know exactly what next application of complex analysis will be, it is clear they are bound to show up again. Maybe even in the unified theory of physics?</p><p><strong>Thanks for reading!</strong></p><p>Questions, comments or suggestions?</p><h3>Sources:</h3><p>[1] Hans Niels Jahnke(1999) <em>A History of Analysis</em></p><p>[2] H. J. Ettlinger (1922) <em>Annals of Mathematics</em></p><p>[3]Peter Ulrich (2005)<em> </em><a href="https://www.sciencedirect.com/science/book/9780444508713"><em>Landmark Writings in Western Mathematics 1640–1940</em></a></p><p>[4] Umberto Bottazzini (1980) <a href="https://www.ams.org/journals/bull/1987-17-01/S0273-0979-1987-15559-5/S0273-0979-1987-15559-5.pdf"><em>The higher calculus’. A history of real and complex analysis from Euler to Weierstrass</em></a><em>.</em></p><p>[5] James Brown (1995) <a href="https://math.unice.fr/~nivoche/pdf/Brown-Churchill-Complex%20Variables%20and%20Application%208th%20edition.pdf"><em>Complex Variables and Applications</em></a></p><p>[6] M Spiegel , S Lipschutz , J Schiller , D Spellman (2009) <em>Schaum’s Outline of Complex Variables, 2ed</em></p><p>[7] R. B. Ash and W.P Novinger(1971) <a href="http://Complex Variables">Complex Variables.</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7af32522123b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/analytics-vidhya/an-introduction-to-complex-analysis-and-applications-7af32522123b">An Introduction to Complex Analysis and Applications</a> was originally published in <a href="https://medium.com/analytics-vidhya">Analytics Vidhya</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[From Decision Trees and Random Forests to Gradient Boosting]]></title>
            <link>https://medium.com/data-science/from-decision-trees-and-random-forests-to-gradient-boosting-6c7dabc516c3?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/6c7dabc516c3</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[editors-pick]]></category>
            <category><![CDATA[gradient-boosting]]></category>
            <category><![CDATA[classification]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Mon, 16 Nov 2020 22:08:18 GMT</pubDate>
            <atom:updated>2020-11-24T04:40:26.151Z</atom:updated>
            <content:encoded><![CDATA[<h4>Review Key Concepts in Machine Learning on an Email Spam Dataset</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kWLv9a5vdRzbWeniriKPyw.jpeg" /><figcaption>Figure 1: Image Citation: Photo by<a href="https://unsplash.com/photos/LPZy4da9aRo"> Brett Jordan on Unsplash.</a></figcaption></figure><p>Suppose we wish to perform supervised learning on a classification problem to determine if an incoming email is spam or not spam. The <a href="https://archive.ics.uci.edu/ml/datasets/spambase"><em>spam dataset </em></a>consists of 4601 emails, each labelled as real (or not spam) (0) or spam (1). The data also contains a large number of predictors (57), each of which is either a character count, or a frequency of occurrence of a certain word or symbol. In this short article, we will briefly cover the main concepts in tree based classification and compare and contrast the most popular methods.</p><p>This dataset and several worked examples are covered in detail in <a href="https://web.stanford.edu/~hastie/ElemStatLearn/datasets/spam.info.txt">The Elements of Statistical Learning, II edition</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/348/1*-Zgaw7f-MJmqHSIJYAg9Rw.png" /><figcaption>Figure 2: The Elements of Statistical Learning II Edition. Image Citation: <a href="https://web.stanford.edu/~hastie/ElemStatLearn/">https://web.stanford.edu/~hastie/ElemStatLearn/</a></figcaption></figure><h3>The Data:</h3><p>The spam dataset consists of 4601 observations, with the response, <strong>Y</strong>, being not spam (0) or spam (1). The data also consists of 57 predictors <strong>x</strong>. Each predictor reflects the frequency of a certain word or letter in the email or a certain symbol. For example the total number of capital letters, the frequency of the ‘$’ sign, etc. Take a look at a sample of the original data.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pfF9vjLpC5Jd_q-Q9Ki_pA.png" /><figcaption>Figure 3: The first 15 observations and the first few columns of the spam dataset. Image from Author.</figcaption></figure><p>Notice that the predictors are quite small and there appear to be many zero data points. We use a log transformation on our predictors before fitting models to help deal with this issue. We add an epsilon of 0.1 to our log to ensure we don’t try to take the log of 0.</p><p>We also randomly split our dataset into a training set and a test set. We will use the test set later to evaluate our model performance.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a77573edacbee2b0029da2e9d2ea75b6/href">https://medium.com/media/a77573edacbee2b0029da2e9d2ea75b6/href</a></iframe><h3><strong>Decision Trees:</strong></h3><p>Decision trees for classification are one of the oldest and most simple machine learning algorithms. They are popular due to the easy visual interpretation. However, in practice, they tend to<em> overfit</em> the training data which leads to poor performance when attempting to make predictions (also known as the high variance problem). R allows us to easily fit decision trees with the <em>rpart </em>function. There are several ways to decide what makes a ‘good’ or ‘best’ tree, but typically we use the <a href="https://www.geeksforgeeks.org/gini-impurity-and-entropy-in-decision-tree-ml/"><em>Gini Impurity</em></a><em>.</em> Ideally, a terminal node should contain only one class. The more mixed it is, the less ‘pure’ it is and the worse the tree will perform on new data.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d9bcb02f043cbade6a448be8eb90e11a/href">https://medium.com/media/d9bcb02f043cbade6a448be8eb90e11a/href</a></iframe><p>The function builds several trees, and at each point we either go left or right depending on our predictors value. We can see that ‘$’ appears to be the most important feature for determining if an email is spam or not in our training data. Depending on ‘$’ we either go left, at which point we check for ‘remove’ or go right at which point we look at ‘hp’. Regardless of our path, we eventually end up at a terminal node, where our email is classified as either spam (1) or not spam(0). At our root node, we have 100% of our training examples. Depending on the value of log($+0.1) we either go to the left (which happens 76% of the time, or to the right, which happens 24% of the time). The number in the middle represents the ‘impurity’ of that node. Our root nodes has an impurity of around 40%, because our training data consists of approximately 40% spam emails.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CZaHz9DkPkEGaI5uEUxn0w.png" /><figcaption>Figure 4: A simple decision tree fit to the spam data. Fit to log(predictor+0.1). At each split, we look at the predictor to determine what side we go to next. Plot made by Author using R.</figcaption></figure><p>Once we have fit a model to our training data, we can see how it performs on our test data. This is done by feeding our new examples into the tree and following the path indicated. To evaluate the performance, we examine the confusion matrix. We obtain a test accuracy of 91% which is quite high.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/435/1*fh8JmohkQrDYQPyxI1p43g.png" /><figcaption>Figure 5: The summary of our confusion matrix. We obtain an accuracy of just under 91% using a simple decision tree. Image from Author.</figcaption></figure><h3>Random Forests and Bagging:</h3><p>In decision trees, our algorithm built several trees and chose one that we found to be the ‘best’. We then used this single tree to produce predictions on new emails. <em>Brieman</em> improved on these simple models greatly by introducing two key concepts. Firstly, <strong>Bagging or Bootstrap Aggregation</strong> and finally, the <strong>Random Forest</strong>. These combine many (hundreds or thousands) of trees, where we take random samples of our observations and predictors to form new trees.</p><p>Random Forests greatly reduce the possibility of overfitting (i.e it reduces variance) by averaging over multiple trees, this is sometimes referred to as the <em>wisdom of crowds.</em></p><p>Hastie described the following in a lecture (linked in sources):</p><ul><li>Bagging (Breiman, 1996): “<em>Fit many large trees to bootstrap-resampled versions of the training data, and classify by majority vote.”</em></li><li><em>Random Forests </em>(Breiman 1999)<em>: “Fancier version of bagging.”</em></li></ul><p>Essentially, Random Forests utilise bagging to form hundreds of trees. Since bagging by definition excludes certain observations from some our models, we can use trees that don’t contain a certain observation to obtain ‘out-of-bag error’ estimates. We can also obtain estimates of the most important features by seeing which predictors consistently are important in many trees. Note that bootstrap aggregation in general will result in a decorrelation of predictors. Hence, if we have some predictors that are essentially identical, the random forest should be able to tease these out and only keep one copy.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ffe36596c7dc6709100c6efc828eb3b1/href">https://medium.com/media/ffe36596c7dc6709100c6efc828eb3b1/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/433/1*TvlCYW8wP4n1OYs_jk4W3w.png" /><figcaption>Figure 6: The confusion matrix for the test data using randomForest function. Image from Author.</figcaption></figure><p>We use the randomForest package in R to fit a model. We can also retain the variables that are most included in our trees, which allows us to visualise the ‘variable importance’. We have greatly improved our accuracy from just under 91% to 94.6%.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/583/1*sf9hR_SKtYXM9TL5OZ9eww.png" /><figcaption>Figure 7: Variable Importance. Image Citation: The Elements of Statistical Learning, II edition. <a href="https://web.stanford.edu/~hastie/ElemStatLearn/">https://web.stanford.edu/~hastie/ElemStatLearn/</a></figcaption></figure><p>One of the great aspects of Random Forests as they also allow us to retain ‘relative importance’ of our predictors. Figure 7 summarises which symbols/words are important in determining spam, and those which are not as important.</p><h3>Gradient Boosting:</h3><ul><li>Boosting (Freund &amp; Shapire, 1996):<em> “Fit many large or small trees to reweighted versions of the training data. Classify by weighted majority vote.” -</em>Hastie.</li></ul><p>Gradient Boosting is an improvement on Random Forests ( if you tune the hyperparameters well). Now, instead of just fitting bootstrap aggregated trees, we take into account how intermediate trees are performing. Using these intermediate trees, we adjust our weights of future trees (we weight certain trees more than others). This can be thought of as <em>repeatedly fitting the residuals of our model.</em> We start with a basic model and see how it preforms at predicting new observations. The residuals are where we did not do as well at predicting, so we fit our next tree to these residuals and so forth to account for where we did poorly (we also don’t use bagging, but instead sample with replacement). Gradient Boosting also tends to create many ‘shallow’ trees. That is, they contain a root node and only a small number of subsequent splits. Often, they only contain a single split, these are known as ‘stumps’ or ‘weak learners’.</p><ul><li><em>“Gradient Boosting inherits all the good features of trees (variable selection, missing data, mixed predictors), and improves on the weak features, such as prediction performance.” — </em>Trevor<em> </em>Hastie</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YqxTMiMpGGrUGKwOvj_tZg.png" /><figcaption>Figure 8: An image illustrating Bagging. Image Citation: <a href="https://commons.wikimedia.org/wiki/File:Ensemble_Bagging.svg">Creative Commons.</a></figcaption></figure><p>Figure 8 illustrates bagging which was discussed above. Bagging can be viewed as an algorithm that works in parallel. That is, bagging is done by selecting multiple sets with replacement at the same time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*V-NAC2LVwUFBUAzCXK7Otg.png" /><figcaption>Figure 9: An image illustrating the general method of Boosting.<a href="https://commons.wikimedia.org/wiki/File:Ensemble_Boosting.svg"> Image Citation: Creative Commons.</a></figcaption></figure><p>Bagging and Boosting are not the same. Bagging is done in parallel as seen in Figure 8 and is used to form several sets of observations to build models with. Boosting, actually uses intermediate trees to adjust the weights that are used when computing the final prediction. As seen in Figure 9, boosting is not done in parallel, it updates weights as it progresses.</p><p>We use the R package, ‘gbm’ to apply gradient boosting to our dataset. Fitting with gradient boosting requires</p><p>The hyperparmaters n.trees, interaction.depth and shrinkage can be tuned using a grid search and cross validation. We set the interaction depth to six, which allows for sixth order interactions.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cb72683a7b85c1fc4b1e034fbc91bda7/href">https://medium.com/media/cb72683a7b85c1fc4b1e034fbc91bda7/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/433/1*cZzp3H6QeIawWCVuHW9agg.png" /><figcaption>Figure 9: We obtain our best accuracy using Gradient Boosting, with an accuracy of over 95%. Image from Author.</figcaption></figure><p>We have ‘boosted’ to an accuracy of over 95% on our test data!</p><h3>Summary:</h3><p>Tree based classification remains one of the most popular algorithms used today, mainly due to there easy interpretation and ability to deal with a large number of predictors. Decision trees are the most basic of the tree based methods, and can be easily interpreted, but are extremely prone to overfitting on the training data. Fortunately, several improvements have been made over the years to address the weaknesses faced by simple decision trees. Random Forests utilise Bagging (Bootstrap Aggregation) to obtain many trees, and use the<em> wisdom of crowds</em> to obtain a lower variance prediction. Boosted Trees further improve on the previous algorithms by considering how intermediate trees preform, and tweaking trees to perform better on places they were previously doing poorly (and weighting powerful trees more). All of these techniques and methods are easy to utilise in R, Python and about every other coding language. Gradient Boosting in particular remains one of the most popular algorithms used in Machine Learning competitions, such as those hosted on Kaggle.</p><p>I hope this article has provided a broad overview, and a simple example of these fundamental ML techniques. Thanks for reading!</p><h3>Code:</h3><ul><li><a href="https://github.com/Robby955/spam">https://github.com/Robby955/spam</a></li></ul><h3>Sources:</h3><p>[1] Lecture Given by Trevor Hastie , <em>Boosted</em>, <a href="https://www.cc.gatech.edu/~hic/CS7616/pdf/lecture5.pdf">https://www.cc.gatech.edu/~hic/CS7616/pdf/lecture5.pdf</a></p><p>[2] Leo Breiman, (1996). Bagging Predictors. <em>Machine Learning</em></p><p>[3] Leo Breiman (2001). Random Forests. <em>Machine Learning</em></p><p>[4] <a href="https://web.stanford.edu/~hastie/ElemStatLearn/">Hastie, Tibshirani, Friedman (2009). The Elements of Statistical Learning II.</a></p><p>[5] Friedman, J. H. (2002). Stochastic gradient boosting. <em>Computational statistics &amp; data analysis</em>, <em>38</em>(4), 367–378.</p><p>[6] Liaw, A., &amp; Wiener, M. (2002). Classification and regression by randomForest. <em>R news</em>, <em>2</em>(3), 18–22.</p><p>[7]Genuer, R., Poggi, J. M., &amp; Tuleau-Malot, C. (2010). Variable selection using random forests. <em>Pattern recognition letters</em>, <em>31</em>(14), 2225–2236.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6c7dabc516c3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/from-decision-trees-and-random-forests-to-gradient-boosting-6c7dabc516c3">From Decision Trees and Random Forests to Gradient Boosting</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Quick Introduction to the Expectation Maximisation (EM) Algorithm]]></title>
            <link>https://rob-sneiderman.medium.com/a-quick-introduction-to-the-expectation-maximisation-em-algorithm-42fca2d38764?source=rss-cd494db13357------2</link>
            <guid isPermaLink="false">https://medium.com/p/42fca2d38764</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[expectation-maximization]]></category>
            <dc:creator><![CDATA[Robby Sneiderman]]></dc:creator>
            <pubDate>Mon, 09 Nov 2020 20:55:51 GMT</pubDate>
            <atom:updated>2020-11-11T17:02:01.469Z</atom:updated>
            <content:encoded><![CDATA[<h3>A Quick Introduction to the Expectation Maximization(EM) Algorithm</h3><h4>And how it can be applied to fit assumed distributions.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*x4mbNquKFLMZCMQKgU9Q4A.jpeg" /><figcaption>Image Citation: <a href="https://unsplash.com/photos/uqtyr_EZ_As">Mor Itam on Unsplash.</a></figcaption></figure><h3>Introduction:</h3><p>In this article we will briefly introduce the Expectation-Maximization (‘EM’) algorithm and walk through several numerical examples. By the end of this article, you should have a better idea of what the EM algorithm is, why it is useful, and how it can be implemented. The EM algorithm is often said to be used when there is ‘missing data’, but in general, it can also be viewed as an algorithm to use when there is ‘latent’ data.</p><p><strong>General Idea:</strong></p><ul><li>We maximise parameters given observed data, that is, we want to find what the parameters should be to result in generating the data we observe with the highest probability.</li></ul><h3>Maximum Likelihood Estimation:</h3><p>The EM algorithm is a method of <em>maximum likelihood estimation</em>, thus we briefly review what that means.</p><p>Suppose we have a random sample of <strong>N </strong>observations;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/126/1*ywNhGT4O_ii3vv9-4XwUug.png" /><figcaption>Figure 1: A random sample of size N.</figcaption></figure><p>With a proposed density function parameterised by theta;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/77/1*t-Cwehh4nlB8wOfd1Z5_vw.png" /><figcaption>Figure 2: The observations y belong to some distribution with parameter theta.</figcaption></figure><p>Then the log-likelihood for that sample is;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/213/1*zNzcgp6hMV907zTs6fHviQ.png" /><figcaption>Figure 3: For a given parameter theta we can calculate the log likelihood of that sample. it will tell us how likely it is we observed the sample if the parameter of the model were theta.</figcaption></figure><p>The EM algorithm works by considering the <em>conditional expectation</em> of the log-likelihood. In particular, if we form the expected log-likelihood conditional on the observed data;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/286/1*n9BHZfAykyxm33hziZfkig.png" /><figcaption>Figure 4: The Expected log-likelihood given the observations and the parameters theta.</figcaption></figure><p>Which is equivalent to;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/286/1*visEsIIdTCfsYJ-6vK3zdw.png" /><figcaption>Figure 5: An equivalent form.</figcaption></figure><p>Which equivalently, can be viewed over all possible missing data.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/361/1*GjPqHlqNJ2314zsyayQF6g.png" /><figcaption>Figure 6: An equivalent form considered over a latent variable z.</figcaption></figure><p>Then, the EM algorithm works by calculating the conditional expectation (E step) and maximising it (M step).</p><h3>Example 1:</h3><p>Suppose we were given a random set of 20 observations, <strong>Y </strong>as seen below, and we wanted to fit some distribution to the data.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/75bb633f088a07e991072318a9a7af80/href">https://medium.com/media/75bb633f088a07e991072318a9a7af80/href</a></iframe><p>Making a histogram of our 20 observations appears to show two normal distributions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*a8-wr29Yk3SGDnCIj67_sQ.png" /><figcaption>Figure 7: Histogram of our observed data points.</figcaption></figure><p>It appears that there are two separate distributions. How could we model this distribution? We could use a mixture model; that is a combination of two normal distributions where;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/243/1*Eq1kPMiBBl2L2xUw0AuMaQ.png" /><figcaption>Figure 8: Our proposed possible mixture distribution. We have two normal distributions. We assume that each observation either belongs to the first model, or the second (with a probability , pi, known as the mixing value).</figcaption></figure><p>The density of <strong>Y</strong> is thus a combination of two normal densities;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/288/1*zkmY95TQwR2FwNQTxudXOA.png" /><figcaption>Figure 9: The density function of our proposed mixture model.</figcaption></figure><p>And the log-likelihood of the mixture is the sum of the individual log likelihoods of two normal distributions. This function alone would be very difficult to simply maximize by taking the derivative. It contains log terms with an inner term containing sums.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/418/1*2ds3NiLDZ7yFJStFQjqS3A.png" /><figcaption>Figure 10. Maximising this likelihood directly would be extremely difficult as it contains the sum.</figcaption></figure><p>Given an observation from <strong>Y</strong>, we can calculate the comparative probability that the observation belongs to one model compared to the other.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/345/1*MnFcZqwsoIC538LvJAfGOg.png" /><figcaption>Figure 11. The ‘Responsibility’. The expected value of delta given that we observed the data point.</figcaption></figure><p>In the case of a simple Gaussian mixture, the EM algorithm can be greatly simplified. Take a look at the algorithm (provided via <em>The Elements of Statistical Learning , 2nd edition</em>). Essentially, we will weight the observation and compare the probability that it belongs to our second model, versus the probability that it belongs to our first model. This is known as the <em>‘responsibility’. </em>We then update our parameters, the mean and variance for both, and finally we update our guess at the mixing parameter.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/652/1*KNR3IeMDNSPMlbWFR8dNeA.png" /><figcaption>Figure 12: The EM algorithm is greatly simplified for Gaussian mixture models. Citation: The Elements of Statistical Learning, 2nd Edition. Chapter 8.</figcaption></figure><p>First, we initialise our parameters. For our mixing parameter, pi, we start with a naive guess of 0.5. For the mean of each distribution, we simply take a random sample (a random observation). For the variance we use the observed mean to form the common variance estimate.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6e146b31a13009ed2e4a1c174a8f719f/href">https://medium.com/media/6e146b31a13009ed2e4a1c174a8f719f/href</a></iframe><p>Now that we have an initial guess, we can iteratively compute the responsibility and update the parameters. We can also compute the log-likelihood at each generation using the formula from Figure 10.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a2cc231766e023f43a954e21692ccf07/href">https://medium.com/media/a2cc231766e023f43a954e21692ccf07/href</a></iframe><p>Once we have run the algorithm for 30 iterations, we can see what a mixed distribution with our expected parameters would look like;</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a91a5f10cb12043939ba3c6b8288afba/href">https://medium.com/media/a91a5f10cb12043939ba3c6b8288afba/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*2tZJiZ26_KabWcWJdxOXTA.png" /><figcaption>Figure 13 : The histogram of our mixture model, which appears to fit the initial observations quite well.</figcaption></figure><p>We can also plot the log-likelihood (evaluated per each iteration).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*dnLePxkrc487GobWj5WYWw.png" /><figcaption>Figure 14: The log-likelihood per each iteration, in general it increases, but it never decreases.</figcaption></figure><h3>Old Faithful:</h3><p>Another common example used to illustrate the EM algorithm is in its application to the old faithful dataset. This dataset consists of time in minutes between each eruption (y-axis) versus the duration of the eruption (x-axis).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3ZqK6m1nTRt0FEOk4CqIjA.png" /><figcaption>Figure 15: It looks like there are two clusters of points. In general, there is a clear trend; the longer we wait between each eruptions seems to result in longer duration eruptions.</figcaption></figure><p>We can obtain better estimates of the clusters by <em>assuming there are two multivariate normal distributions</em>. Once we naively make an assumption of a starting distribution, we use the density of the multivariate normal to preform the EM Algorithm.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/360/1*OyXgise21a23D5JCss8Tlg.gif" /><figcaption>Figure 16: EM algorithm running on the old faithful dataset with two multivariate normal distributions. Gif Citation: Creative Commons: Chire, CC BY-SA 3.0 &lt;<a href="https://creativecommons.org/licenses/by-sa/3.0">https://creativecommons.org/licenses/by-sa/3.0</a>&gt;, via Wikimedia Commons</figcaption></figure><p>The above animation illustrates the steps taken. We start off with two naive and badly fit multivariate normal distributions. Each step of the EM algorithm updates the parameters according to which distribution is more likely. In the end we have two well fitting multivariate normal.</p><h3>Peppered Moths:</h3><p>The colouring of the <em>peppered moth</em> is believed to be determined by a gene which has only three possible alleles. These alleles are denoted as <em>C, I </em>and <em>T</em>.</p><p>C is dominant to I and T, and T is recessive to I. There are three distinct <em>phenotypes</em> of these moths (that is , we can actually observe three different types).</p><p><strong><em>CC, CI </em>and<em> CT</em> result in a solid black moth (<em>carbonaria</em>).</strong></p><p><strong><em>TT </em>results in an light moth (<em> typica).</em></strong></p><p><strong><em>IT </em>and<em> II</em> result in a intermediate coloured moth (<em>insularia</em>).</strong></p><p>Suppose we capture a large number of these months, say<strong> N</strong> of them, and we can then count how many of each phenotype we see. Hence, denote <strong>N=nC+nI+nT</strong></p><p>While we can see the colour of the moth, we can’t actually see the underlying genotype. How can we get an idea of the distribution of alleles? Firstly, note that since only TT results in a light moth, we can simplify the problem. We know that there are <strong>nT</strong> moths with genotype TT.</p><p><strong>What is seen:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/161/1*EzKyrIXKhkpr_ZtIh_SYPg.png" /><figcaption>Figure 17: The Observed data, the three phenotypes. We can only see the three types of moths.</figcaption></figure><p><strong>What is ‘missing’ or latent:</strong></p><p>The Genotype (there are six possible);</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/307/1*_vGzWYqbB7VpVrN0jPii0w.png" /><figcaption>Figure 18: In reality, there are 6 underlying genotypes.</figcaption></figure><p>If the alleles were distributed with probability PC , PI and PT respectively, then the probability of each genotype could be represented by Gp.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/369/1*CNQ8zZtKrhGfiz8my-8c5A.png" /><figcaption>Figure 19: The probability of each genotype. Notice the square term for identical alleles, or the product of two for when we can have a combination of two alleles.</figcaption></figure><p>This distribution can be viewed as a <em>multinomial</em> distribution, with each allele being chosen with probability according Gp.</p><p>Then proceeding as before, to apply the EM algorithm, we need the log- likelihood of the multinomial distribution</p><p>The probability density function (pdf) of the multinomial distribution in this case is thus;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/767/1*IWLRXQnig6Ikp0YS9vFlBw.png" /><figcaption>Figure 20: The pdf of the multinomial distribution.</figcaption></figure><p>And the conditional log likelihood is;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hsO_LGi5PJMxvf2D2MijrQ.png" /><figcaption>Figure 21: The conditional log-likelihood.</figcaption></figure><p>Above is the conditional log-likelihood, and we need to compute the expected value conditional on what we observe.</p><p><strong>Expectation Step:</strong></p><p>The expected number of CC alleles will be proportional to the number of <em>carbonaria </em>counted and the probability of being CC, by the probability of appearing<em> carbnoaria. </em>By the same logic we can obtain all the conditional expectations. These are then replaced in the above formula and we take the derivative, set it to zero to solve for the update steps.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/596/1*iIN3evhd2I8oXMQXsrWepg.png" /><figcaption>Figure 22: The Expected number of genotypes of the form CC.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/597/1*Am0tPkUobP3XxA_ZvicSIQ.png" /><figcaption>Figure 23: The Expected number of genotypes of the form CI.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/593/1*8Lh57-s766sFEww5EHUDLA.png" /><figcaption>Figure 24: The Expected number of genotypes of the form CI.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/486/1*y-zVJILHtTnePad1PMhbvQ.png" /><figcaption>Figure 25: The Expected number of genotypes of the form II.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*7rTOk0kZKGpuck5aH679Pw.png" /><figcaption>Figure 26: The Expected number of genotypes of the form IT.</figcaption></figure><p>Note, we already know the expected number of TT genotypes, as we can actually observe it( the number of light moths).</p><p><strong>Maximization Step:</strong></p><p>We can take the derivative of the log-likelihood to obtain the maximization step.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*UtdCmSsGsMXfajOlcueSWA.png" /><figcaption>Figure 27: Maximising the expected log likelihood with respect to Pc.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/464/1*2AkIcLCchv-Q9-FYx6KWKg.png" /><figcaption>Figure 28: Maximising the expected log likelihood with respect to PI.</figcaption></figure><p>Simplifying ,and noting that <strong>PC+PI+PT=1:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/265/1*48wz4yC-fTT84WxJARSoJg.png" /><figcaption>Figure 29: The updates for each iteration. After solving for each parameter.</figcaption></figure><p>We can now use these steps to form the algorithm and iteratively update each step.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/22cf1e6d6d55e2002c18f75282bbf8af/href">https://medium.com/media/22cf1e6d6d55e2002c18f75282bbf8af/href</a></iframe><p>Given an initial observation of 74 black moths, 176 intermediate and 321 light moths, we can use the EM algorithm to get an idea of the probability distribution of each allele. From the initial observations, we expect that the allele C will be quite rare. The T allele is extremely common, and the I allele is also quite rare. This is because for there to be so many light moths, there must be an overwhelming presence of the T allele. After applying the algorithm we estimate that the probability of having a C is only 0.0625, of I is 0.1904 and T is 0.747, which makes sense.</p><p><strong>Convergence:</strong></p><p>It can be proven that the<a href="http://www.stat.cmu.edu/~siva/Papers/EM_full.pdf"> EM algorithm does converge</a>. That is, that each step does not decrease the log-likelihood. Hence at a minimum it makes no change, but it will in general increase the log-likelihood and converge at the maximum.</p><h3>Summary and Conclusion:</h3><p>The EM Algorithm is a powerful tool that is used when there is underlying or latent data. It is thus crucial that data scientists and statisticians are at least familiar with the algorithm. The EM algorithm is used extensively in industry, EM is frequently used for <a href="https://en.wikipedia.org/wiki/Data_clustering">clustering</a> in also is used in computer vision.</p><p>The Baum-Welch algorithm, a form of the EM algorithm is also used extensively in Natural langue processing where it deals with hidden Markov models.</p><p>The EM algorithm is also widely used in for medical image reconstruction, especially in PET scans and XRays.</p><h3>Sources:</h3><p>[1] Dempster, Laird and Rubin (1977) J Royal Statistical Society (B) Maximum Likelihood from Incomplete Data via the EM Algorithm.</p><p>[2]<a href="https://www.stat.colostate.edu/computationalstatistics/">Computational Statistics, 2nd edition. Geof H Givens, J A. Hoeing (2012).</a></p><p>[3] The Elements of Statistical Learning, II Edition (2009 ).Hastie, Tibshirani and Friedman.</p><p>[4]<a href="https://www.google.ca/search?tbo=p&amp;tbm=bks&amp;q=inauthor:%22Geoffrey+J.+McLachlan%22&amp;source=gbs_metadata_r&amp;cad=6">Geoffrey J. McLachlan</a>, <a href="https://www.google.ca/search?tbo=p&amp;tbm=bks&amp;q=inauthor:%22Thriyambakam+Krishnan%22&amp;source=gbs_metadata_r&amp;cad=6">Thriyambakam Krishnan</a> (2007). The EM Algorithm and Extensions</p><p>[5] <a href="http://www.stat.cmu.edu/~siva/Papers/EM_full.pdf">Statistical Guarantees for the EM Algorithm: From Population to sample based.</a></p><p>[6] Current trends in medical image registration and fusion (2016). <a href="https://www.sciencedirect.com/science/journal/11108665">Egyptian Informatics Journal</a></p><p><strong>Github:</strong></p><p><a href="https://github.com/Robby955/ExpectationMaximization">https://github.com/Robby955/ExpectationMaximization</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=42fca2d38764" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>