<?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 tiefengeist on Medium]]></title>
        <description><![CDATA[Stories by tiefengeist on Medium]]></description>
        <link>https://medium.com/@sahirnambiar?source=rss-8dc41e02b542------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*bSLO5z4N_OAKmKZbtNCPmQ.png</url>
            <title>Stories by tiefengeist on Medium</title>
            <link>https://medium.com/@sahirnambiar?source=rss-8dc41e02b542------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 05:42:16 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@sahirnambiar/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[An Area-Optimization Problem with a Twist]]></title>
            <link>https://medium.com/@sahirnambiar/an-area-optimization-problem-with-a-twist-21aadb74df3c?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/21aadb74df3c</guid>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Wed, 07 Aug 2019 16:13:13 GMT</pubDate>
            <atom:updated>2019-08-07T16:13:13.074Z</atom:updated>
            <content:encoded><![CDATA[<p>Today I’ll be covering an area optimization problem similar to one I earlier covered <a href="https://medium.com/@sahirnambiar/two-area-optimization-problems-decb696823e1">here</a>. In this case, however, rather than trying to find the amount of liquid trapped within a simple rectangular container, we’re trying to find the amount trapped within a more complicated elevation map. That is, we’re given a topography represented by an array, and want to see how much water it can trap after it has ‘rained’. Here’s a visual representation of the problem:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/565/1*8i3AO-7inKQXCFvNaz0ZsQ.png" /></figure><h3>Approach 1: Brute Force</h3><p>Now, the most straightforward way to approach this problem would be the brute force solution. This approach can be described as follows: for each element in our array, we calculate the minimum of the maximum height of the bars on either side of the element, and subtract from it the height of the element itself. This gives us the amount of water each element can trap. So we</p><ol><li>Initialize our result, setting it to zero.</li><li>Initialize our left and right maxima, also setting them to zero.</li><li>Iterate from our present element to the beginning or end of the array, setting max left (right) to the larger of the maximum, or the height currently being considered.</li><li>Subtract the minimum of these maxima from the current height, add it to our result.</li></ol><p>In code, this looks like this (Java):</p><pre>public int getHowMuchWater(int[] elevationMap) {<br>        int prevMaxIndex = 0;<br>        int nextMaxIndex = 0;<br>        int sum = 0;<br>        for (int i = 0; i &lt; elevationMap.length; i++) {<br>            if (elevationMap[i] &gt;= elevationMap[prevMaxIndex]) {<br>                for (int j = prevMaxIndex + 1; j &lt; i; j++) {<br>                  sum += elevationMap[prevMaxIndex] - elevationMap[j];<br>                }<br>                prevMaxIndex = i;<br>            }<br>            else if (nextMaxIndex &gt; prevMaxIndex) {<br>                for (int j = prevMaxIndex + 1; j &lt; nextMaxIndex; j++) {<br>                  sum += elevationMap[nextMaxIndex] - elevationMap[j];<br>                }<br>                prevMaxIndex = nextMaxIndex;<br>                nextMaxIndex = 0;<br>            }<br>            else if (prevMaxIndex != elevationMap.length - 1 &amp;&amp; i + 1 == elevationMap.length) {<br>                nextMaxIndex = prevMaxIndex + 1;<br>                for (int k = nextMaxIndex; k &lt; elevationMap.length; k++) {<br>                  if (elevationMap[nextMaxIndex] &lt; elevationMap[k]) {<br>                    nextMaxIndex = k;<br>                  }<br>                }<br><br>                i = prevMaxIndex;<br>            }<br>        }<br>        return sum;<br>    }</pre><p>Now, as is typical, the brute force solution isn’t the best one. For each element in our array, we’re iterating over the entire array. That means our solution is only completed in O(n²) time — not a great result.</p><h3>Approach 2: Two Pointers</h3><p>Here we’ll employ another, better approach to solving the problem. Different from our earlier area-optimization problem, where we used two pointers to simplify our solution, here we’ll use a ‘stack’ data structure. For those unfamiliar, a <a href="https://www.geeksforgeeks.org/stack-data-structure/">stack</a> is a data structure wherein one only has access to the most recently added element.</p><p>Essentially, as we iterate through our array, we will add the index of an element to our stack if that element is less than or equal to an element at the top of the stack. This means that for every bar closer to the top of the stack, they are bounded by bars deeper within it. So if we encounter an element larger than the one at the top of the stack, we know it’s bounded by a previous element in the stack, and can thus add the resulting difference to our answer.</p><p>More simply:</p><p>While our stack isn’t empty, and the size(current) &gt; size(stack.top),</p><ol><li>Pop the top element</li><li>Find distance between elements (d = current — stack.top — 1)</li><li>Find our bounded size (bs = min(size[current], size[stack.top]) — size[top])</li><li>Add the bounded size to our answer.</li><li>Push current index to top of stack.</li><li>Move current to next element.</li></ol><p>In code, this looks like (Ruby):</p><pre>def trap(height)<br>    water = 0<br>    stack = [] # used to store the index of height<br>    i = 0<br><br>    while i &lt; height.length<br>      if stack.empty? or height[i] &lt;= height[ stack.last ]<br>        stack &lt;&lt; i<br>        i += 1<br>      else<br>        valley = height[ stack.pop ]<br><br>        next if stack.empty?<br><br>        left_idx, right_idx = stack.last, i<br>        peak = height.values_at(left_idx, right_idx).min<br><br>        water += (peak - valley) * (right_idx - left_idx - 1)<br>      end<br>    end<br><br>    water<br>  end</pre><p>In this solution, each element is ‘touched’ at most two times, when inserting or deleting it from the stack. This means our solution is of O(n), which is about as good as we’ll get for this problem.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=21aadb74df3c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Crafting a Simple Sudoku Solver]]></title>
            <link>https://medium.com/@sahirnambiar/crafting-a-simple-sudoku-solver-3f918180e960?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/3f918180e960</guid>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Tue, 30 Jul 2019 01:00:06 GMT</pubDate>
            <atom:updated>2019-07-30T01:00:06.397Z</atom:updated>
            <content:encoded><![CDATA[<p>The topic of this blog post is how to go about solving an arbitrary Sudoku puzzle. Sudoku is a game where one has to fill in a 9x9 box with numbers, subject to certain constraints.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/218/1*QEpaeu3WK4Zoxe4NUKwTpA.gif" /><figcaption>A typical sudoku puzzle</figcaption></figure><p>Sudoku proceeds by the player filling every empty cell with a number. The number in question has to satisfy a few rules.</p><ol><li>The number must be between 1 and 9.</li><li>Each number can appear only once per row.</li><li>Each number can appear only once per column.</li><li>Each number can appear only once per 3x3 “sub-box”.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/242/1*K9H1XD7gJLM7Ot_RR50Ksw.png" /><figcaption>A solution to the above puzzle.</figcaption></figure><p>For our purposes, we are assuming each puzzle has a single unique solution, which is the one we pursue.</p><p>Our board consists of an array of arrays representing each row.</p><h3>Determining Our Options</h3><p>We’ll begin our approach by first writing a function which determines the valid options for each empty cell based on the game rules. Blanks are represented by ‘.’ (a string).</p><pre>def options(board, row, col)<br>  #our options array<br>  options = [*&quot;1&quot;..&quot;9&quot;]<br>  len = board.length</pre><pre>  blank = &#39;.&#39;</pre><pre>  #we first remove the options which are already on the row<br>  options -= board[row].chars.uniq</pre><pre>  #we then do the same for our columns<br>  column = len.times.collect {|row| board[row][col]}<br>  options -= column.uniq</pre><pre>  #we do the same for a block, by calling the get_block function<br>  #which we&#39;ll soon write<br>  block = get_block(board, row, col)<br>  options -= block.uniq</pre><pre>  #and now, we remove our blanks we&#39;ve accumulated, and return the<br>  #remaining options<br>  options -= [blank]<br>  options.map {|x| x.to_s}<br>end</pre><p>Now, as you’ll notice, I made use of a ‘get_block()’ function. Here’s how that one works.</p><pre>def get_block(board, row, col)<br>  #establish starting rows and columns for the block<br>  block_row = 3 * (row / 3)<br>  block_col = 3 * (col / 3)<br>  block = []<br>  #iterate through each block and add to block array<br>  for i in 0..2<br>    for j in 0..2<br>      block &lt;&lt; board[row_start + i][col_start + j]<br>    end<br>  end <br>  #return our block so we can subtract it from options<br>  block<br>end</pre><h3>Solving the Puzzle</h3><p>Now that we have two helper functions to get blocks and determine options for each cell in the puzzle, we can move on to the solution.</p><p>Our approach, described simply in words, is to go through each cell on the board. If a cell is blank, we get our options using the handy function above, then test each option on the board, before running our program again recursively. If we run out of options (our options array is empty) then the solution we have thus far is invalid, so we return nil and kill the program before trying again. If our options array doesn’t run out, and the whole board has numbers on it, we’ve solved the problem and return the board. Here it is in code.</p><pre>def sudoku(board)<br>  #we begin by finding our first blank<br>  for i in 0...board.length<br>    for j in 0...board[i].length<br>      next unless board[i][j] == blank<br>      <br>      options = get_options(board, i, j)<br>      return nil if options.empty? <br>      # this is us returning nothing, since our validity check        #       failed, so we kill the branch<br>      <br>      # we go forward, trying every option, and recursively call our     #       proposal, otherwise leaving a blank<br>      proposed = board.dup<br>      options.each do |v|<br>        proposed[i][j] = v<br>        return proposed if sudoku(proposed)<br>        proposed[i][j] = blank<br>      end<br>      <br>      # if none of the options work, we<br>      return nil<br>    end<br>  end<br>  <br>  # if the whole board has numbers, we simply return it (base case)<br>  board<br>end</pre><p>This solves a sudoku puzzle on the order of the number of cells in the board, which is a lot faster than a human can.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3f918180e960" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Two Area Optimization Problems]]></title>
            <link>https://medium.com/@sahirnambiar/two-area-optimization-problems-decb696823e1?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/decb696823e1</guid>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Mon, 22 Jul 2019 22:50:45 GMT</pubDate>
            <atom:updated>2019-07-30T00:21:25.589Z</atom:updated>
            <content:encoded><![CDATA[<h3>An Area Optimization Problem</h3><p>Today, I’ll be going over a problem about finding the optimal amount of area filled by a hypothetical liquid. As in my previous post, I’ll discuss a couple of possible solutions to the problem, along with a discussion of the time complexity associated with those solutions.</p><h3>Container with Most Water</h3><p>The problem I’ll be covering works as follows: we’re given <em>n</em> non-negative integers in an array. Each of these integers represents a point in a coordinate plane. We then draw <em>n</em> vertical lines, each of which has a height represented by the integer corresponding to its place in the array. Our goal, then, is to find a set of two lines which, with the x-axis as our base, form a container such that the area of the container is maximized. The problem is illustrated below</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/727/1*lZFuI-pXUtdSJpKAcMK6bQ.png" /></figure><p>First, we’ll approach this problem with the naive solution. The simplest solution is to simply look at the area in question for every single pair of lines possible, and determine the area from that. The code for this approach is:</p><pre>def max_area(height)<br>  max = 0<br>  for i in (0..height.size)<br>    for j in (1..height.size)<br>      max = [max, (height[i], height[j]).min * (j - i)].max<br>      j += 1<br>      end<br>    i += 1<br>    end<br>  return max<br>  end<br>end</pre><p>Here, for each element of our array of heights, we multiply the x-distance between our element and every other element in our array by the larger of that first element or the current element to find the area. We then get the maximum value of these, and set that to our <em>max</em> variable. So for each of our <em>n</em> elements, we perform <em>n </em>computations of n*(n-1)/2, meaning our time complexity is O(n²).</p><p>This is really a pretty expensive, poorly-planned-out approach. I think we can do better. Imagine we start with, instead of one pointer (our i/j in the brute force approach), two pointers, one at the start and one at the end. So we begin by considering the area determined by the outermost lines. Then, in order to find the maximum area possible, we’ll only need to consider the area between lines of larger lengths. If we try to move the longer line’s pointer closer in towards the middle, our area won’t increase, since we’re limited by the shorter line. But if we move the shorter line’s pointer in, even though the width gets smaller, that might be compensated for by a much longer line. We then proceed this way for the whole array; if the longer line is on the right, we move the left pointer further, increasing our maximum if the area is larger. While if the longer line is on the left, we move our right pointer to the left (the logic is the same, but the directions are reversed). The code for this solution is:</p><pre>def max_area(height)<br>    l = 0<br>    r = height.length - 1<br>    max = 0<br>    while r &gt; l<br>        area = (r-l) * [height[r], height[l]].min<br>        max = area if area &gt; max<br>        if height[l] &lt; height[r]<br>            l += 1<br>        else<br>            r -= 1<br>        end<br>    end<br>    return max<br>end</pre><p>In this case, we move either right or left down the array only one time total. So our time complexity is, at worst, O(n).</p><p>As you can see, the most straightforward solution frequently isn’t the best. The idea of comparing every single pair of lines <em>does</em> work, but if we had 1000 lines instead of just 10, we would need to perform <em>a million</em> computations in order to find our answer, which is based on finding the maximum within a dataset. The two-pointer method, while less intuitive, will get us there in a time proportional only to the size of the array itself.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=decb696823e1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Summing Two and Three Elements]]></title>
            <link>https://medium.com/@sahirnambiar/summing-two-and-three-elements-48748365c031?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/48748365c031</guid>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Tue, 16 Jul 2019 06:41:11 GMT</pubDate>
            <atom:updated>2019-07-16T06:41:11.996Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/375/0*IITvoURWv8YO4Pcl" /><figcaption>Source: <a href="https://vinsinin.files.wordpress.com/2016/03/111.png?w=545">https://vinsinin.files.wordpress.com/2016/03/111.png?w=545</a></figcaption></figure><p>Today, I’ll be doing a walkthrough of three similar programming problems related to arrays (or lists, or what have you). I’ll be providing implementations in Ruby, with a discussion of time complexity.</p><p>There is a certain class of problem of which variants frequently pop up in interviews for entry-level programming jobs. This is the “sum problem”, wherein one is given an array of numbers, and asked to see if these numbers sum to a given number <em>k</em>. In our case, we will be treating <em>k </em>as zero; the problem is the same either way, but instead of testing for equality by seeing if a sum has a remainder when divided by <em>k </em>(sum%k == 0), we’ll be seeing if the sum is equal to zero.</p><h3>Two Sum</h3><p>The first, and easiest, of these problems is the <em>two sum</em>. Here, we only have to deal with two elements of the array. We attempt to see if they sum to a target value, then return the indices of the elements in question.</p><p>We can start with a naive, “brute-force” solution to this problem. The solution proceeds as follows:</p><ol><li>Consider each element of the array.</li><li>For each of these elements, see if it is equal to the target minus each element after it.</li><li>If so, put both elements into an ‘answers’ array.</li></ol><p>Since for each of our <em>n</em> elements, we need to consider the other <em>n </em>elements of the array, our program takes on the order of n² time to run — it is O(n²).</p><p>Here is the brute-force implementation.</p><pre>def two_sum(nums, target)<br>  for i in (0...nums.length)<br>    for j in (1...nums.length)<br>      if nums[j] == target - nums[i]<br>        return [i, j]<br>      end<br>    end<br>  end<br>end</pre><p>Now, if we’re not concerned with adding some other data types and increasing the space complexity, we can reduce our time complexity considerably. Namely, we can make use of a hash in order to enable our program to run much more quickly.</p><p>The steps in this method are as follows:</p><ol><li>Create a hash.</li><li>For each element <em>n </em>of our array, store the index of <em>n </em>as a value with a key <em>n.</em></li><li>Check if the key corresponding to the target value minus our number already exists.</li><li>If it does, return the index of our number, along with the index of the complement (i.e. the value corresponding to the key of the target value minus the number).</li></ol><p>The code for this follows:</p><pre>def two_sum(nums, target)<br>    search = {}<br>    nums.each_with_index do |num,i| <br>      return [search[target-num], i] unless search[target-num].nil?<br>      search[num] = i <br>    end<br>end</pre><p>In this case, we only have to pass through the array one time, since as we iterate through the array and add elements to our hash, we’re simultaneously looking to see if the complement of each element is already in the hash. As such, our complexity is only O(n).</p><h3>Three Sum</h3><p>Now, the three sum gets a bit trickier. Though lower time complexity algorithms do exist, they are somewhat academic in nature and require a lot of trickery to pull off. I’ll only be covering the brute force method, along with an O(n²) method, here.</p><p>We’ll start with the brute force method. This way, we essentially proceed as in the two-sum case, only instead of just two nested for loops, we have three of them.</p><pre>def three_sum(nums)<br>  for i in (0...nums.length)<br>    for j in (1...nums.length)<br>      for k in (2...nums.length)         <br>         if nums[i] + nums[j] + nums[k] == 0<br>           return [i, j]<br>          end<br>        end<br>      end<br>    end<br>  end<br>end</pre><p>This method is O(n³), which is pretty awful! An array with just 20 elements will take 8000 computations. But we can improve on this.</p><p>Here, we’ll proceed by:</p><ol><li>Sorting our array in place (Ruby uses Quicksort, which has a best case time complexity of O(n log n) and a worst case complexity of O(n²).</li><li>Initialize an empty array.</li><li>Skip any duplicate numbers.</li><li>Set up pointers on the second and last elements of the array.</li><li>Sum the pointers along with the element we start on (the three-sum in question).</li><li>If the sum is positive, we move the last (highest) pointer downwards to a lower number.</li><li>If the sum is negative, we move the first (lower) pointer upwards to a higher number.</li><li>We ensure that the two pointers don’t cross.</li><li>When the sum is zero, we add the numbers comprising the sum to our solutions array.</li><li>Move lower pointer up and upper pointer down, while checking for duplicates, and continue looking for other solutions.</li></ol><p>The code for this method:</p><pre>def three_sum(nums)<br>    nums.sort!<br>    sums = []<br>    <br>    <br>    for i in 0..(nums.length - 3)<br>        #Skip duplicates<br>        next if i &gt; 0 &amp;&amp; nums[i - 1] == nums[i]<br>        #Establish our pointers on either end<br>        j = i + 1<br>        k = nums.length - 1<br>        while (j &lt; k) do<br>            sum = nums[i] + nums[j] + nums[k]<br>            if sum &gt; 0<br>                k -= 1<br>            elsif sum &lt; 0<br>                j += 1<br>            else<br>                #Add numbers to solutions array.<br>                sums &lt;&lt; [nums[i], nums[j], nums[k]]<br>                j += 1<br>                k -= 1<br>                j += 1 while nums[j] == nums[j - 1]<br>                k -= 1 while nums[k] == nums[k + 1]<br>            end<br>        end<br>    end<br>    <br>    return sums<br>end</pre><p>This method only passes through our sorted array once, so all the complexity comes from the Ruby sort function, which, as mentioned above, has an upper limit of O(n²) time complexity. Almost exactly the same approach can be taken for an analogous “four-sum” problem. Can you figure out an implementation?</p><p>That about wraps up our discussion of these two problems. Until next time.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=48748365c031" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Simplified Implementation of PageRank]]></title>
            <link>https://medium.com/@sahirnambiar/a-simplified-implementation-of-pagerank-b8b5d282dc42?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/b8b5d282dc42</guid>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Tue, 09 Jul 2019 03:19:33 GMT</pubDate>
            <atom:updated>2019-07-09T03:19:33.346Z</atom:updated>
            <content:encoded><![CDATA[<p>In the previous blogs, we’ve learned about the theory of eigenvectors and eigenvalues, and how they can be applied to rank pages by relevance (determined by how many sites link to a given page, and how many outgoing sites that page links to). That is, if we have a web of pages interconnected through hyperlinks, we may construct a matrix describing how those pages are linked, weighted based on those pages’ rankings, divided by (inversely proportional to) how many outgoing links are on said pages. We then found that the eigenvector associated with that matrix gives us a ranking of those pages which determines their relevance to the searcher.</p><p>However, we had two problems with the earlier model — one of them is that a dangling page, one with no outgoing links, would be divided by zero, making it impossible to integrate into our model. The other problem is that our rankings were sometimes not unique. These problems can be solved simply by ensuring that every element of the matrix is positive.</p><h3>The Motivation</h3><p>But why would such a fact be justified? Consider the following example. Assume you’re randomly clicking through links on a site — truly at random, so you’re just as likely to pick any link as any other. If you keep doing this, you’ll notice eventually that you’re a lot more likely as time goes on to find pages that have a lot of sites linking to them, rather than pages with only a few links leading to them.</p><p>As it turns out, this is a pretty good way (as discussed in the last post) to quantify the relative importance or relevance of a website; the more popular a website is, the more likely people are to click on a link leading to it.</p><p>Now imagine we make a matrix, where each entry of the matrix, characterized by the ordered pair (<em>i,j</em>), represents the probability that you would click on a link from site <em>j </em>to go to site <em>i.</em> What do you know? We’ve ended up with exactly the same matrix as discussed in the previous post (and above)!</p><p>The thing is, if you end up on a site with no links on it, you’re stuck. But if, at this point, you type a random URL in and go to another site that way, you’ll find that, quickly enough, you’ll be on a lot of the same sites you were on before.</p><p>You can try this out effectively on a website like Wikipedia — see how many times you have to click on random links to arrive at the same page. Chances are, it won’t be far above 30.</p><p>So the solution to our problem for before, how to deal with nodes on our graph/web that ‘dangle’, or have no outgoing links, is just to imagine that at that point, we randomly jump to another website. Mathematically, this is simple enough to do, so long as we scale our matrix by a factor of 1/<em>n</em>, where <em>n </em>is the size of our old, unadjusted matrix.</p><p><strong>Implementation</strong></p><p>What follows is an implementation of PageRank in Python. The program takes in a graph, representing interconnected websites,</p><p>alpha = a parameter (damping constant) representing how quickly we want our ranking to find an answer (with a dense enough dataset, with lots of sites that link to one another, it would take a long time without this parameter) set to 0.85 by default, which is the actual constant from papers on PageRank.</p><p>G = a graph, which is made directed if it isn’t already.</p><p>max_i = number of iterations used in computing eigenvalue through the power method</p><p>weight = weight of a link (graph edge).</p><p>dangling = the outgoing links (edges) to be assigned to any ‘dangling’ node which has no outgoing links of its own.</p><p>Eigenvalues are computed through the <a href="https://en.wikipedia.org/wiki/Power_iteration">power iteration method</a>.</p><pre>import networkx as nx</pre><pre>def pagerank(G, alpha=0.85, personalization=None,<br>             max_i=100, nstart=None, weight=&#39;weight&#39;,<br>             dangling=None):</pre><pre>#nothing in our graph<br>    if len(G) == 0:<br>        return {}<br>    #turns graph directed<br>    if not G.is_directed():<br>        D = G.to_directed()<br>    else:<br>        D = G</pre><pre># Create a copy of our matrix satisfying our properties (positivity, single eigenvalue)<br>    W = nx.stochastic_graph(D, weight=weight)<br>    N = W.number_of_nodes()</pre><pre>#x is our starting trial eigenvector<br>        x = dict.fromkeys(W, 1.0 / N)</pre><pre>p = dict.fromkeys(W, 1.0 / N)</pre><pre>if dangling is None:</pre><pre># Use p if dangling vector not specified<br>        dangling_weights = p<br>    else:<br>        missing = set(G) - set(dangling)<br>        if missing:<br>            raise NetworkXError(&#39;Dangling node dictionary &#39;<br>                                &#39;must have a value for every node. &#39;<br>                                &#39;Missing nodes %s&#39; % missing)<br>        s = float(sum(dangling.values()))<br>        dangling_weights = dict((k, v/s) for k, v in dangling.items())<br>    dangling_nodes = [n for n in W if W.out_degree(n, weight=weight) == 0.0]</pre><pre># power iteration: make up to max_i iterations<br>    for _ in range(max_i):<br>        xlast = x<br>        x = dict.fromkeys(xlast.keys(), 0)<br>        danglesum = alpha * sum(xlast[n] for n in dangling_nodes)<br>        for n in x:</pre><pre># this matrix multiply is different because we&#39;re<br>            # left-multiplying x^T=xlast^T*W<br>            for nbr in W[n]:<br>                x[nbr] += alpha * xlast[n] * W[n][nbr][weight]<br>            x[n] += danglesum * dangling_weights[n] + (1.0 - alpha) * p[n]</pre><pre># check convergence, and if normalized<br>        err = sum([abs(x[n] - xlast[n]) for n in x])<br>        if err &lt; N*tol:<br>            return x<br>    raise NetworkXError(&#39;pagerank: power iteration failed to converge &#39;<br>                        &#39;in %d iterations.&#39; % max_i)</pre><p>Here’s what a fully page-ranked graph, represented visually, might look like.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*F-ms6b1KgDgEhRRVqrYGAQ.jpeg" /><figcaption>Photo credit: <a href="https://upload.wikimedia.org/wikipedia/en/8/8b/PageRanks-Example.jpg">https://upload.wikimedia.org/wikipedia/en/8/8b/PageRanks-Example.jpg</a></figcaption></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b8b5d282dc42" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Some More Applications of Linear Algebra]]></title>
            <link>https://medium.com/@sahirnambiar/some-more-applications-of-linear-algebra-21b894620859?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/21b894620859</guid>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Tue, 02 Jul 2019 03:07:42 GMT</pubDate>
            <atom:updated>2019-07-02T03:07:42.918Z</atom:updated>
            <content:encoded><![CDATA[<p>In my <a href="https://medium.com/@sahirnambiar/some-applications-of-linear-algebra-in-programming-3495bfbe823e">previous post</a> I introduced the basic concepts of linear algebra and described orthogonal matrices. In this post, I’ll discuss eigenvectors and eigenvalues, and give a simple application resembling a primitive version of Google’s PageRank algorithm.</p><h3>Eigenvectors and Eigenvalues</h3><p>In linear algebra, an <strong>eigenvector </strong>is a vector which, when operated on by a matrix, maintains its orientation relative to a given coordinate system, changing, if at all, only by a scalar factor, which is called the <strong>eigenvalue</strong>. It may be written as the following equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*RpLsA4POdDnUO95WEOk8og.png" /></figure><p>Where A is a square matrix, and <em>λ </em>is a scalar. Written out in terms of matrices and vectors more explicitly, this equation looks like the following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/314/1*_P4JHx4Fmzi6lHc4xaIjPA.png" /></figure><p>where w_n = <em>λ</em>v_n.</p><p>Geometrically speaking, this is the same as stating that the vector’s direction is unchanged, though its length or <strong>magnitude </strong>is.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/234/1*VzyBeP7cOAxqpZc9-vq3vQ.png" /><figcaption>A acts on the eigenvector x</figcaption></figure><p>A simple method of finding eigenvectors and their eigenvalues is given <a href="https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors#Eigenvalues_and_the_characteristic_polynomial">here</a>.</p><h3>What Does A Search Engine Do?</h3><p>Now, how does all this apply to search engines? Well, it might make sense to zoom out for a second and think about just what we want a search engine to do.</p><p>If a search engine simply looked through the web, found keywords given by a user, and returned a list of websites bearing them, it would fulfill its most basic purpose, but it wouldn’t be very useful. It needs to not only find the relevant pages for us, but also to sort them by how relevant they might be to our interests. So we need to first <em>copy</em> websites matching keywords into a database, then <em>organize them</em> in order to make them easier to retrieve later on when showing them to users. We then need to <em>rank them, </em>which is the part of the process where linear algebra comes especially in handy.</p><h3>The Web as a Graph</h3><p>To see how Google, in a very broad way, goes about doing this, it’s helpful to conceive of the web as a <strong>directed graph</strong>. Directed graphs are familiar to those of you who have looked into data structures; essentially, they are composed of nodes connected to each other in a single-directional way. The concept is simply illustrated by the following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/511/1*-Ro1Dn1nhBJcEgLdT4b2Og.jpeg" /><figcaption>A directed graph</figcaption></figure><p>The internet can be represented by directed graphs in a very straightforward way: the nodes are websites, and the arrows linking them are — wait for it — links. A fairly logical way to figure out which pages are more important is to figure out which ones are linked to by more sites than others. In the above graph, for example, every node but <em>r</em> has two nodes linking to it, so <em>r</em> would appear at the bottom of the search.</p><h3>PageRank</h3><p>So the straightforward way to rank pages, and the basic logic PageRank is based on, is to rank by how many incoming links a given page has — that is, how many other pages link to a given page. But the problem here is that, in the graph above, we’d have four sites equally ranked.</p><p>Another factor (literally) to consider is that being linked to from some sites matters more than being linked to from others. That is, a random site that anyone could have made, which nobody else has linked to, should, by linking to another site, influence that other site’s ranking a lot less than a really popular site, which a ton of people link to and almost everyone trusts, doing the same. So, to figure out how high a page should be ranked, we can use the following equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/479/1*SYxoYHc2mX0c-rzK1tUvvQ.png" /></figure><p>Where x_n is the page’s rank, B_n is the bank of pages with links to that page, y_k is the rank of a site linking to the page being ranked, and z_k is however many sites <em>that </em>site is linking to (which is used in order to keep sites with a lot of influence from gaining unwarranted clout by simply linking to a bunch of other sites).</p><p>To break this down even further, what we’re doing is, to find the rank, x_n, of a site, we’re summing the ranks of all the sites y_k which link to x_n, and dividing by a factor of how many links that site has on it to keep from double- or triple- or n-tuple-counting that site.</p><p>Consider the following graph:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/204/0*5Pvj43YjmDLkwOdT" /></figure><p>This graph could be, using the equation above, written instead as a system of equations:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*7AjjwKt5vrYRorzLg72o3A.png" /></figure><p>Which can be represented as the matrix:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/704/1*5duBiw10n8-3pHUKREoqMw.png" /></figure><p>To figure out the solution x = (x_1, x_2, x_3, x_4), which gives us our pageranks, all we need to do is find the <strong>eigenvector<em> </em></strong>that corresponds to this matrix. If we do so, it turns out to be</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/658/1*eLcBL3FqOJyWPsjVcnCOYg.png" /></figure><p>Which shows us that node 4 on the above graph is the most highly-ranked site. This actually isn’t so obvious — we can note that node 1 has the most sites linking to it, but is second in the ranking (3/4) because it only links to node 4. Since node 4 has nodes 1 and 3 linking to it, but links to both 2 and 3, it ends up top of the heap.</p><p>This version of “PageRank” has been heavily simplified, and only works for pages that both have links to them and link to other pages, which is obviously a really strong assumption. My next post will go into further depth on these issues, and will be a bit more mathematically precise.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=21b894620859" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Some Applications of Linear Algebra in Programming]]></title>
            <link>https://medium.com/@sahirnambiar/some-applications-of-linear-algebra-in-programming-3495bfbe823e?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/3495bfbe823e</guid>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Tue, 25 Jun 2019 05:15:36 GMT</pubDate>
            <atom:updated>2019-06-25T05:15:36.920Z</atom:updated>
            <content:encoded><![CDATA[<p>Most people who have received a formal education in computer science will be very familiar with computer science. Others, who have come to programming through non-traditional means, frequently don’t.</p><p>It’s always surprised me that linear algebra doesn’t have a larger place in secondary school math curricula. In many ways, it feels like a more logical step forward from “pre-calculus” than calculus itself — in particular, a lot of insight may be derived from the relationships between the trigonometric functions and orthogonal matrices (that is, matrices which preserve the dot product).</p><p>But on a less specific level, linear algebra would likely satisfy many students who complain that calculus is ‘too abstract’, or that math beyond algebra lacks practical value in general (though whether or not these complaints are valid in the first place is a much more complicated issue). In this blog post, I’ll give brief overview of linear algebra, and then discuss some of its applications in computing. I will give more detailed overviews of these applications in subsequent posts, with implementations when appropriate.</p><h3>The Basic Objects of Linear Algebra</h3><p>For our purposes, linear algebra consists of three major types of objects: scalars, vectors, and matrices.</p><p>Scalars are simply numbers as we know them — they can be integers, fractions, real, or imaginary.</p><p>Vectors are like scalars, but also have an associated direction. They can be represented by two numbers in a set of coordinates, as the following image illustrates. In terms of computing, we may represent them as one-dimensional lists or arrays, such as [2, 3] in the case of the example below. This mathematical vector should not be confused with the vector data object in C++’s STL.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ap-yQMXbrdJFFZgsQ2lGpg.png" /><figcaption>A vector. It should be noted that vectors can actually be much more abstract than this, but we are restricting our consideration to regular, Euclidian space.</figcaption></figure><p>The third type of object is a bit more abstract — it’s called a matrix. Readers may have encountered these objects before (like in some of my earlier blog posts). Matrices essentially describe how vectors can be turned into other vectors.</p><p>For example, consider the matrix M:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/471/1*Pl20HIsHcOr8aQLLKl7kmw.png" /></figure><p>This matrix can act on a vector,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/270/1*4flDrTbOTAJCPNW2AU73xw.png" /></figure><p>The result of this multiplication is illustrated as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/263/1*wA5VjyhBjjgQiW0DU9yDKQ.png" /></figure><p>Matrices can act on vectors, but they can also act on entire systems of coordinates. For example, a square with side lengths of one would be transformed as follows (the logic is the same for each ‘square’ in a regular system of coordinates).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/711/1*rbBlexjequS-X93fHHoZNA.png" /><figcaption>A square being transformed by the matrix M.</figcaption></figure><p>It should also be noted that these transformations can be composed — you can do two transformations in a row — just by multiplying the matrices as shown below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/313/1*j7AG9zDYZvadfVACVE81qw.jpeg" /><figcaption>Matrix multiplication</figcaption></figure><p>But be careful — unlike with regular scalar multiplication, AB and BA don’t tend to be the same thing.</p><h3>Orthogonal Matrices</h3><p>There are a number of special kinds of matrices — one type is orthogonal matrices. Put very simply, orthogonal matrices are matrices whose columns and rows, when viewed as vectors, are perpendicular to one another.</p><p>These matrices have extremely special properties. They transform coordinates or vectors in a very special, specific way: they represent rotations, reflections, or a combination of the two. For example, the following matrix:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/138/1*1n1JqCHLOk_e526JkjUcUQ.png" /></figure><p>Represents a rotation by the angle θ.</p><p>A straightforward application of this is computer graphics, particularly polygonal. Most video games, for example, are composed of polygons, which are transformed and rotated according to the rules of linear algebra. In fact, one of the earliest games, Asteroids, made extensive use of these matrix operations, as you can see:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*kZIplZxE51EVskzOEZkZYw.gif" /></figure><p>In my next blog post, I’ll discuss eigenvectors and eigenvalues, and how they are used in Google’s PageRank algorithm.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3495bfbe823e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Gradient Descent]]></title>
            <link>https://medium.com/@sahirnambiar/gradient-descent-f4cefac4b50b?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/f4cefac4b50b</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Wed, 17 Apr 2019 19:45:51 GMT</pubDate>
            <atom:updated>2019-04-17T19:45:51.412Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="Image result for gradient descent" src="https://cdn-images-1.medium.com/proxy/1*f9a162GhpMbiTVTAua_lLQ.png" /></figure><p>Building on my previous blog topic, I will describe how to perform linear least-squares fitting, but with gradient descent, rather determining the closed-form solution. Though we will still be considering the linear case, the approach I am discussing (gradient descent) is primarily used for nonlinear cases, where no closed form solution is available.</p><p>Another use for gradient descent is when the matrix of parameters contains mostly zeros — in this case, gradient descent is much less computationally expensive than attempting to find individual closed form solutions for a bunch of irrelevant (zero) parameters.</p><p>We begin our example by extending our linear equation from 2 to <em>n </em>variables. Rather than looking like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/565/0*byd9D6sqamaOKbd9.png" /></figure><pre>const h = x =&gt; thetaZero + thetaOne * x;</pre><p>It now looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/347/1*92Ner6PucyrENyTRlq4mCQ.png" /></figure><p>Very concretely speaking, this means that, for example, instead of predicting the price of a house as being dependent on city (constant) plus neighborhood * square feet, it could be dependent on any number of factors, like city plus theta_1 * square feet plus theta_2 * number of rooms plus theta_3 * quality of view, etc.</p><p>Now, rather than solving this (much expanded) equation for our thetas analytically, as in the previous blog post, we will be implementing a method known as gradient descent.</p><p>Gradient descent can be roughly described as follows: picture yourself standing on a hill in a landscape — that landscape is a function of two variables, and your position is described by those two variables. The distance to the ground (or to sea-level) represents the cost function I described last week.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0a3JQ9rQoeWXdh1x.png" /><figcaption>The Cost function</figcaption></figure><p>The cost function can be implemented as follows:</p><pre>const cost = () =&gt; {<br>  let sum = 0;<br><br>  for (let i = 0; i &lt; n; i++) {<br>    sum += (h(x[i]) - y[i])**2;<br>  }<br><br>  return sum / (2 * M);<br>}</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RtAPl-eFP2ecG3CKGdpJTQ.jpeg" /><figcaption>Some example “landscapes”</figcaption></figure><p>We are trying to find a valley in this hillscape — that is, we are trying to minimize the cost function.</p><p>The way gradient descent attempts to do this is interesting: to extend our analogy, imagine you have your eyes closed, and you’re trying to find a valley. This takes three major steps.</p><p>First, you feel around for the steepest direction in which you can step.</p><p>Then, you take a step of some size in that direction (the size of this step is called the “learning rate”).</p><p>You then repeat this process until you hit the bottom of a valley.</p><p>Note that the learning rate is quite important, since if it’s too large, you may overstep the actual lowest point, but if it’s too small, you might take way too long to get there. We can set the learning rate here.</p><pre>const alpha = 0.0003;</pre><p>Translating this into math, what we’re doing is we’re taking our function, h(θ_i<strong>), </strong>and take its derivative in the i’th direction. Formally speaking, we can write our iterative algorithm, where α is the learning rate (the “size” of your steps).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/994/0*TqcprbQRXoCaxXzn.png" /></figure><p>More explicitly, we can isolate each of our n ‘features’ (e.g. number of rooms, square feet, quality of view, location) and minimize the cost function for each of them. The following is the equation above with the derivative explicitly carried out, using the chain rule, which you will remember from high school calculus.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/279/1*up4cYxKCxFs0va2BDZCe-w.png" /><figcaption>Here, h_theta is our cost function.</figcaption></figure><p>Putting all of this together, using the variables above, we can now implement gradient descent fully in JavaScript.</p><pre>const gradientDescent = (alpha) =&gt; {<br>  let thetaZeroFinal = 0;<br>  let thetaOneFinal = 0;<br><br>  for (let i = 0; i &lt; n; i++) {<br>    thetaZeroFinal += h(x[i]) - y[i];<br>    thetaOneFinal += (h(x[i]) - y[i]) * x[i];<br>  }<br><br>  thetaZero = thetaZero - (alpha / n) * thetaZeroFinal;<br>  thetaOne = thetaOne - (alpha / n) * thetaOneFinal;<br>}</pre><p>Here’s a visual representation of what this process looks like (the surface is a cost function).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-HcaU10tg4kuO6g7.jpg" /></figure><p>Gradient descent is the most popular optimization strategy used in machine learning and deep learning, due to its relevant computational cheapness, usefulness with inconsistent data sets and nonlinear fitting. It will likely be used for years to come.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f4cefac4b50b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Linear Least Squares: A Javascript Implementation and a Definitional Question]]></title>
            <link>https://medium.com/@sahirnambiar/linear-least-squares-a-javascript-implementation-and-a-definitional-question-e3fba55a6d4b?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/e3fba55a6d4b</guid>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Wed, 03 Apr 2019 19:30:18 GMT</pubDate>
            <atom:updated>2019-04-03T19:30:18.556Z</atom:updated>
            <content:encoded><![CDATA[<p>We are likely all familiar with the concept of curve-fitting — sometimes, we, as humans, can recognize certain patterns in data about which the data itself is agnostic. If we look at a chart like the following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/333/1*8MvgdxgbZpBiP1n56lXRkA.png" /></figure><p>we think immediately of a linear relationship. But what tools can we use to precisely determine a line from these individual points of data?</p><p>Intuitively speaking, we can all figure this out pretty easily — we want to find the line that is minimally far from every single one of these points. The way this is actually implemented is through a method known as <em>least squares regression</em>. This form of regression is very powerful, and is widely used in applications from signals processing to economics research.</p><p>Least squares fitting finds the best curve to fit a set of points through minimizing the sum of the squares of the offsets of each point from the curve.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/203/1*2imZ-NgDWHiiK2fb7L_I9Q.png" /><figcaption>Not the rapper</figcaption></figure><p>We use the squares of the offsets to ensure a property called <em>differentiability</em>, which allows us to use vital tools from calculus in analyzing the data (that’s all I’ll say on the topic here).</p><p>The least squares technique can be straightforwardly extended to exponential cases, but for this post, I’ll only discuss the simple linear case.</p><h3>The Math</h3><p>Least squares consists in finding <em>R², </em>the sum of the squares of the vertical offsets of a set of <em>n </em>data points.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/256/1*XCh6fkwMf54EVaDnGbCqPw.png" /></figure><p>Here, <em>f </em>is a function of data points <em>x</em>, and offsets (<em>y-</em>intercepts, which you’ll remember from school math) <em>a, </em>while <em>y</em> is the vertical coordinate in our data.</p><p>Since we are attempting a linear fit, we know that</p><p><em>f(a,b) = a + bx</em></p><p>and, since we are attempting to minimize our “wrongness” or deviation from the average, we apply the condition for <em>R²</em> to be at a minimum,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/76/1*d_WW78_G0y2MxBNKbLeQoA.png" /></figure><p>for <em>i = 1,..,n.</em></p><p>Since we’re doing a linear fit, these conditions amount to</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/235/1*ttjXI1RJqWf7uLniBQNxSA.png" /></figure><p>We may rewrite these conditions as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/244/1*FwmbCMDpqlFHnhghVr86tQ.png" /></figure><p>Defining the following terms:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/196/1*gFElwKfdnOUFM8_Z8OKenA.png" /></figure><p>more algebra demonstrates that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/162/1*Tl8E3MM0Gi2ASTtQoi-0jw.png" /></figure><p>Then, plugging this value into our equation for a line, we find that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/99/1*MnuakT9VzO6vQP4PqfrhhA.png" /></figure><p>where the bars denote averages.</p><p>In essence, we made a function representing the average sum of squared differences between our actual data and what we might predict, the <em>cost function</em>,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/974/0*Yd2pKkVeTtsGlHRl.png" /></figure><p>and we’ve found its minimum with respect to <em>m </em>and <em>b</em>. We then took those values and plugged them back into the equation for a line to find our fit.</p><p>Here’s an illustration of what we’ve done:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/258/1*Rppj-NBPazgLK_bxwwFYxw.png" /></figure><h3>The Implementation</h3><p>A simple implementation of this in JavaScript follows, where the function takes in a set of datapoints, and returns a new set of points which define the best-fit line.</p><pre>function findLineByLeastSquares(values_x, values_y) {<br>    var x_sum = 0;<br>    var y_sum = 0;<br>    var xy_sum = 0;<br>    var xx_sum = 0;<br>    var count = 0;<br><br>    /*<br>     * The above is just for quick access, makes the program faster<br>     */<br>    var x = 0;<br>    var y = 0;<br>    var values_length = values_x.length;<br><br>    if (values_length != values_y.length) {<br>        throw new Error(&#39;The parameters values_x and values_y need to have same size!&#39;);<br>    }<br><br>    /*<br>     * Above and below cover edge cases<br>     */<br>    if (values_length === 0) {<br>        return [ [], [] ];<br>    }<br><br>    /*<br>     * Calculate the sum for each of the parts necessary.<br>     */<br>    for (let i = 0; i&lt; values_length; i++) {<br>        x = values_x[i];<br>        y = values_y[i];<br>        x_sum+= x;<br>        y_sum+= y;<br>        xx_sum += x*x;<br>        xy_sum += x*y;<br>        count++;<br>    }<br><br>    /*<br>     * Calculate m and b for the line equation:<br>     * y = x * m + b<br>     */<br>    var m = (count*xy_sum - x_sum*y_sum) / (count*xx_sum - x_sum*x_sum);<br>    var b = (y_sum/count) - (m*x_sum)/count;<br><br>    /*<br>     * We then return the x and y data points according to our fit<br>     */<br>    var result_values_x = [];<br>    var result_values_y = [];<br><br>    for (let i = 0; i &lt; values_length; i++) {<br>        x = values_x[i];<br>        y = x * m + b;<br>        result_values_x.push(x);<br>        result_values_y.push(y);<br>    }<br><br>    return [result_values_x, result_values_y];<br>}</pre><p>In the above equations for <em>m </em>and <em>b, </em>note that there is a sign change, since we are attempting to find the equation <em>y = mx + b</em>, rather than <em>b = y-mx</em> as in the discussion above.</p><h3>A Question</h3><p>We hear the term ‘artificial intelligence’ bandied about all the time — and indeed, least squares fitting is used in AI applications — but does this method count as AI?</p><p>In my view, the question is ultimately hollow — as Turing says in his 1950 paper, <em>Computing Machinery and Intelligence</em>, asking whether or not a computer is intelligent is akin to asking whether a submarine ‘swims’, or an airplane ‘flies’ — the question boils down to definition, and therefore to tautology.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/560/1*l9EcdsiimFIKlM6ARGc6DQ.jpeg" /><figcaption>Is this thing some kind of genius?</figcaption></figure><p>But I don’t presume to have the final word on the topic. At the very least, the question is interesting. The method of least squares was developed in the early 19th century in order to assist mathematicians, engineers, and artillery officers(!!!) with their calculations, performed, of course, with pencil and paper. Would those calculations themselves comprise a sort of artificial intelligence?</p><p>With a large enough dataset, a 19th century <em>human</em> computer could, by rote, perform least squares on thousands of datapoints in order to extrapolate the resulting parameters to novel datasets. In essence, his brain would be doing exactly what computers doing “machine learning” do today, albeit much, much more slowly.</p><p>Perhaps AI and machine learning shouldn’t be conflated, as they so often are. Or perhaps we should come up with a better term than ‘machine learning’, considering humans can be the vehicles of such learning, as well. These questions, though maybe trivial, remain open.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e3fba55a6d4b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Basics of the λ-calculus: the Simplest ‘Language’ There Is]]></title>
            <link>https://medium.com/@sahirnambiar/basics-of-the-%CE%BB-calculus-the-simplest-language-there-is-500cea345e91?source=rss-8dc41e02b542------2</link>
            <guid isPermaLink="false">https://medium.com/p/500cea345e91</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[tiefengeist]]></dc:creator>
            <pubDate>Wed, 20 Mar 2019 21:00:09 GMT</pubDate>
            <atom:updated>2019-03-20T21:09:42.004Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/440/0*qy7WaIpqxHsg4Dm8.jpg" /></figure><p>The Lambda Calculus is a formalism designed to describe computation, initially discovered in the 1930s by the mathematician and logician Alonzo Church. The calculus has proved important in theories of formal semantics within linguistics, and, as it turns out, in understanding the structure of functional programming languages , as well. Indeed, every functional programming language implements the lambda calculus.</p><p>So what exactly does the lambda calculus do for us? How does it help us understand how computation occurs? It provides a simple and general method for determining constraints on how statements or propositions can be interpreted. That is, it provides us with a syntax-independent method for the precise examination of how computer programs written in a functional programming language are interpreted. In a sense, the lambda calculus is the most minimal programming language. It is also Turing-complete.</p><pre>x += y        // This is written in JavaScript/Java/Ruby<br>x := x + y   // This is written in Ada/Pascal</pre><p>Two major simplifications lend the lambda calculus its generality. The first of these is anonymity — functions do not in and of themselves have names. That is, an “addone” function described by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/663/0*qpyT01N2iB2uQ0rN.png" /></figure><p>, or in JavaScript,</p><pre>function addone(x) { x + 1}</pre><p>would instead be anonymized as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/358/0*j0fF_Znj0Wp8uraR.png" /></figure><p>or,</p><pre>(x =&gt; x + 1)</pre><p>The other is that the calculus only takes one argument per function — though there’s a way around this, called currying, which I will go into later.</p><h3>The Formalism</h3><p>The lambda calculus (the λ-calculus, from here on out) has three basic objects. These are</p><ul><li>Variables, which we all know and love,</li><li>Abstractions, which are the equivalent of functions,</li><li>Applications, which are functions called with an argument</li></ul><p>These are represented as follows:</p><ul><li>x is a variable,</li><li>λx.x is a function which takes an argument represented by the placeholder value ‘x’, and has a body ‘x’</li><li>(λx.x)a is the function above, called with the argument ‘a’</li></ul><p>‘x’ in the examples above is ‘bound’, because it is both an argument, and appears in the body of the function. ‘Free’ variables are those such as ‘y’ in λx.y, which doesn’t appear as an argument.</p><h3>α-conversion</h3><p>Variables are reassigned through a process known as ‘α-conversion’. If we wanted to change the name of ‘x’ in our above example, we could ‘α-convert’ it as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/460/0*NS2C2bSLB1Z8oy1W.png" /></figure><p>Or, in JavaScript</p><pre>(x =&gt; x)(y =&gt; y) // This evaluates as y =&gt; y</pre><p>We would then call these abstractions ‘α-equivalent’. But note that this operation isn’t completely trivial — for example,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/697/0*ssSpfd5eSMFjsfOw.png" /><figcaption>Equation 1</figcaption></figure><p>however,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/697/0*8Ciz5jcBSXV-6atG.png" /><figcaption>Equation 2</figcaption></figure><p>This is equivalent to the notion of ‘variable shadowing’ in functional programming languages. In eq(1), the final ‘x’ is bound to the inner abstraction, λx, while in eq(2), the final ‘y’ is bound to the outer abstraction, λy.</p><p>The idea is that the first ‘y’ on the right side of equation(2) is bound to a different abstraction from the corresponding ‘x’ on the left side. The only variables which may be renamed while remaining α-equivalent are those bound to the same abstraction.</p><h3>β-reduction</h3><p>The above is supplemented by a process known as ‘β-reduction’, which in essence is a substitution of variables constrained by lexical scope. Essentially, if we have an application (λx.x)a, we’re essentially taking ‘a’ and replacing ‘x’ with it — so that function would evaluate simply to ‘a’. We can even nest functions this way:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/764/0*n4qKpzkbOxRqteCV.png" /></figure><p>Or, for a more applied example (though we’re abusing notation);</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/871/0*28tH-i6gtSr6wylm.png" /></figure><p>But what if we want to create a function with more than one parameter when lambda calculus explicitly only allows one? We can utilize a handy process known as ‘currying’.</p><p>So let’s say we want to execute a function such as</p><pre>function hypsquaredfunc(x, y) { x**2 + y**2 }</pre><p>We would, instead of taking two arguments, pass one single-argument function into another, like so:</p><pre>const hypsquared = x =&gt; y =&gt; x**2 + y**2;</pre><pre>hypsquared(2); // This will return a function, y =&gt; 4 + y**2<br>hypsquared(2)(5) // This returns the same as hypsquaredfunc(2, 5) = 29.</pre><p>In the λ-calculus, we say that (λx.λy.xy) is equivalent to f(x, y) = ((x)y).</p><p>As you can see from the JavaScript function above, currying is implemented in functional programming languages — in fact, as I mentioned above, all functional programming languages fully implement the λ-calculus.</p><p>Though it might seem like we’ve barely done anything at all, the λ-calculus is actually very powerful. We can declare and alter variables, define functions, and call those functions.</p><p>In fact, an abstraction in the λ-calculus is equivalent to an ‘anonymous function’, or arrow-function, in JavaScript, as we’ve seen above.</p><p>Though I didn’t go into detail on the subject, we are also permitted to define recursive functions. Actually, many basic functions of the λ-calculus, such as the substitution of free variables, are defined through recursion.</p><p>There are also a number of ways to self-consistently define the natural numbers, as well as the logical and conditional operators, using the calculus. Though it may be impractical to do so, the λ-calculus offers us almost all the abilities of a given functional programming language, and it does so with minimal baggage. It gives us as fundamental an understanding of functional languages as we can hope for.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=500cea345e91" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>