<?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 William Fleshman on Medium]]></title>
        <description><![CDATA[Stories by William Fleshman on Medium]]></description>
        <link>https://medium.com/@william.fleshman?source=rss-797753643492------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*faxECIoUFmt_2gA6u7jZ6w.jpeg</url>
            <title>Stories by William Fleshman on Medium</title>
            <link>https://medium.com/@william.fleshman?source=rss-797753643492------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 04:13:02 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@william.fleshman/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[Pixel Challenge 2022]]></title>
            <link>https://medium.com/@william.fleshman/pixel-challenge-2022-577b4e6f4a89?source=rss-797753643492------2</link>
            <guid isPermaLink="false">https://medium.com/p/577b4e6f4a89</guid>
            <category><![CDATA[infosec]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[william-fleshman]]></category>
            <category><![CDATA[hacking]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[William Fleshman]]></dc:creator>
            <pubDate>Fri, 29 Apr 2022 12:04:49 GMT</pubDate>
            <atom:updated>2022-04-29T12:04:49.772Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/742/1*vPAQaqikcjBAYgE6JxJpPg.png" /></figure><h3>Introduction</h3><p>On April 6th 2022, <a href="https://medium.com/u/6f68ff3b3da6">notdan</a> posted an interesting challenge on his twitter. He was skeptical about recent claims that tools could deobfuscate images of text which had been blurred for redaction purposes. If possible, this vulnerability could be exploited across the many examples of blurred credit card numbers, dollar amounts, PII, and other sensitive information across the internet. The claims didn’t live up to his expectations, and he was confident a general solution to deobfuscation didn’t exist.</p><p>To put his claim to the test he created the Pixel Challenge with a bounty of $100.</p><h3>uɐpʇou@ ✸ on Twitter: &quot;Show me one practical use of the &quot;Deobfuscating Pixel Filter With AI/ML&quot; and I&#39;ll send you $100 in XMR. Must be original, show your work (aka screenrecord everything) and not be one of the samples that the author of the &quot;vulnerability&quot; provided. Print the text on my sample &amp; win: pic.twitter.com/lIOzc2UqdN / Twitter&quot;</h3><p>Show me one practical use of the &quot;Deobfuscating Pixel Filter With AI/ML&quot; and I&#39;ll send you $100 in XMR. Must be original, show your work (aka screenrecord everything) and not be one of the samples that the author of the &quot;vulnerability&quot; provided.</p><p>The very next day, <a href="https://medium.com/u/6f68ff3b3da6">notdan</a> doubled down (actually ten-fold) on his beliefs by raising the stakes of the challenge to a very generous $1000.</p><h3>uɐpʇou@ ✸ on Twitter: &quot;The Bounty Has Officially Been Upped To $1,000 USD. Enjoy! I really would like to see something happen with this, but we will finally see how practical the supposed &quot;pixel deobfuscation attack&quot; actually is. https://t.co/sw0W38yB0Z / Twitter&quot;</h3><p>The Bounty Has Officially Been Upped To $1,000 USD. Enjoy! I really would like to see something happen with this, but we will finally see how practical the supposed &quot;pixel deobfuscation attack&quot; actually is. https://t.co/sw0W38yB0Z</p><h3>So It Begins</h3><p>The Twitter algorithm did its magic, and my good friend the Benevolent Orangutan (@BenevOrang) saw the tweet and shot me a message.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/416/1*IvPwbOwion0Bjy-RKj6YRQ.png" /><figcaption>@BenevOrang kicking things off</figcaption></figure><p>The next morning he had already started experimenting with evolutionary algorithms (his personal favorite technique) and was bouncing a few ideas off of me. I must admit, like <a href="https://medium.com/u/6f68ff3b3da6">notdan</a> I was very skeptical this would be possible. I mean look at how blurry that image is!</p><p>When asked for final thoughts on his game plan, I was less than encouraging:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*SqQZKH6M-a7tWtpQCRn3KQ.png" /><figcaption>not good advice</figcaption></figure><p>Fortunately, he kept the conversation alive, and I took a minute to think about how I would actually tackle something like this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*_ECsNVj9iH5AmsUTk_CI2Q.png" /><figcaption>much better advice (even with typos)</figcaption></figure><h3>Image Super-Resolution</h3><p>In recent years, the task of image super-resolution has been actively researched by the deep learning community. The goal of this super-resolution research is to use deep neural networks to increase the resolution of lower quality images.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mXfb1cU4vpZmSBrzHEwm-g.png" /><figcaption>Left to Right: Low Resolution (4x), Outputs from two SR nets, High Resolution - from: <a href="https://arxiv.org/abs/1609.04802">https://arxiv.org/abs/1609.04802</a></figcaption></figure><p>Most applications of super-resolution focus on improving general image quality, as perfect high resolution recovery is impossible with the loss of information at lower resolutions. I am aware of very little research into using super-resolution for text recovery, other than a few papers dealing with text found in real scenes (street signs, building names, etc.). Regardless, I figured the techniques used for general image super-resolution, in principle, should apply here as well.</p><h3>I Want to Have Fun Too</h3><p>I had taken the day off to prepare for some overseas travel and spent the rest of the morning packing and getting updates about my friend’s attempts. By mid-morning I was convinced he was having more fun than me and so decided to start writing some code.</p><p>In another tweet, <a href="https://medium.com/u/6f68ff3b3da6">notdan</a> had disclosed that the image was created with a Photoshop mosaic filter. I wasn’t familiar with the filter, so did some searching on how it’s implemented. My initial implementation created the pixelized effect by first down-sampling an input image and then up-sampling it back to the original resolution using nearest neighbor interpolation. I examined the challenge image to help estimate how much down-sampling would be required to produce a similar pixelization. The technique was a bit crude, but seemed like an okay starting point.</p><p>I also needed a way to produce training examples. I wrote some code using the python Pillow library for generating new images with white backgrounds and black text. I didn’t know what font was used in the challenge (yet), so I grabbed something generic off of my system. To produce a new image, the code selected a few ascii characters at random and centered them on the frame. I experimented with different font sizes while using my mosaic blur until I was routinely getting examples with words taking up three large pixels (just like the challenge image).</p><p>Armed with the ability to generate an infinite amount of high res and pixelated training examples, I was ready to find a suitable neural network for the job. I did a quick search and settled on a <a href="https://pytorch.org/">pytorch</a> implementation of the Super-Resolution Resnet described in the paper <em>Photo-Realistic Single Image Super-Resolution Using a Generative Adversarial Network </em>by Ledig et al. (ironically from Twitter Research). I slightly modified the network’s architecture to work on black and white images and manipulated how much up-sampling would occur inside the network.</p><p>I wrote a wrapper class around my data generation function to comply with pytorch’s Dataset-Dataloader model and knocked out the pytorch boiler plate code for setting up a training loop. On each iteration, my network would attempt to recover 32 low resolution images. The output of the network would be compared to the ground truth, and the weights of the network were adjusted via gradient descent in order to improve the result. After each epoch of training (1024 random images in this case), I would run the challenge image through the network to look at the results. The output from the first epoch got me pretty excited!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/478/1*EVUX5Uy4eesn47EyaqJjJw.png" /><figcaption>Is that Ancient Sumerian???</figcaption></figure><p>As training continued it became obvious there were some issues. I figured the process I was using to generate the training examples wasn’t good enough, but the day was over, and I was getting on a plane soon. I sent @BenevOrang all of my code and wished him good luck while I was away.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6MFreneG_OUtIvJfCGc-rQ.gif" /><figcaption>A GIF of that original training run. Pretty horrible, but you can actually see “NOBODY” in retrospect.</figcaption></figure><h3>Experiments</h3><p>Motivated by the initial results, my friend continued to build off my code base while I was away. He sent me periodic updates of his experiments modifying the generation process, and by the end of his experimentation the phrase “VULNERABILITY FOR CREDIBILITY” was readable. Even “FAUX” is fairly recovered, but we didn’t even notice (who uses faux??).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qDc5d6UfMnH3ZUYrYqP62w.png" /><figcaption>Output from @BenevOrang’s trained model</figcaption></figure><p>I found the following experiments significantly notable and provide my justification for why:</p><h4>1. Using a dictionary to produce words instead of random strings</h4><p>During the training process the network will learn common patterns in the data. By using words from the English language the network will be able to better correlate common character pairs like “QU” and be less likely to produce uncommon pairs “YJ” it has never seen. Theoretically, this statistical knowledge could allow the network to correctly reconstruct under circumstances where multiple (but mostly jibberish) character sequences blur to the same pixelization.</p><h4>2. Randomly selecting the font</h4><p>Randomly rotating through fonts during training allows the network to become robust to font selection. While this makes the training more difficult, it allows for some uncertainty in the font used for the challenge. He had actually predicted the correct font early in the competition by looking up Adobe defaults which definitely boosted results. By the time I came back <a href="https://medium.com/u/6f68ff3b3da6">notdan</a> had disclosed which font he used which simplified this aspect of the modeling.</p><h4>3. Randomizing location of words in the images</h4><p>If I had to guess, this was one of the most important things my initial generation process didn’t include. My friend had noticed that the same word would have different pixelizations depending on where the word was placed in the image. This caused me to take a deeper look into how my mosaic filter was implemented. Instead of my original method, it’s actually better to think about the filter taking a grid size as input. Then the filter takes each grid cell of pixels and replaces their value with the average for that cell. This is why placement of the text is important. For example, if a character is moved up a single pixel then the top pixels of the character might cross into a new grid cell. The new grid cell would get darker, and the original grid cell will get lighter because of the lost character pixels.</p><h3>Reverse Engineering and Brute Force</h3><p>I got back from my trip on a Sunday and work kept me busy throughout the week. My friend occasionally asked if I’d made progress and by the next Sunday had motivated me to pick up where I had left off. Armed with new insights, I reimplemented my mosaic blur using the grid method. Since he had recovered the word “vulnerability” I decided to use it as a <a href="https://en.wikipedia.org/wiki/Known-plaintext_attack">crib</a> to improve my own generation process. I set up an optimization loop that iterated over different font sizes and offsets while creating a mosaic blur of my generated text. Each iteration measured the distance between my version and the challenge image trimmed down to just that section. The optimization uncovered the best parameters and resulted in an almost perfect reconstruction:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/485/1*jfGhay1lyfPbTCWHjOMc-w.png" /><figcaption>Top: “VULNERABILITY” produced by my generation. Bottom: “VULNERABILITY” produced by <a href="https://medium.com/u/6f68ff3b3da6">notdan</a></figcaption></figure><p>Now that I had a method for creating almost identical examples, I figured I could brute force my way to the solution. I reused the same code for finding optimal font size and offsets but kept the font size fixed to what I previously discovered. I then added logic to loop over every possible character and measure the distance between the added pixels and the corresponding pixels in the other challenge words. Instead of checking a single character at a time, I looped over pairs to account for the blending that occurs from the pixelization. I kept the first character of each optimal pair and then repeated the process for the next character in the word.</p><p>To my great excitement, this brute force technique spit out the answers for lines two through four — “VULNERABILITY FOR CREDIBILITY NOBODY QUESTIONED”. The results for the top line looked like gibberish, a sequence of random characters ending in “AFAUX” (seriously, who uses the word faux!?).</p><h3>Final Touches</h3><p>Motivated by being so close to the complete answer, I fired up my GPU once more and watched my electric bill continue to rise. I had replaced the data generation process with my improved mosaic blur, used a dictionary to generate the words with the correct font and size, and chose the locations in the images randomly. The rest of my initial code base remained the same and the results were markedly better. I was finally able to read off the top line “THIS WAS A FAUX”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/742/1*uAS6gjJacWrclcGgTde7og.gif" /><figcaption>Time lapse of final training run.</figcaption></figure><h3>Claiming the Prize</h3><p>I sent <a href="https://medium.com/u/6f68ff3b3da6">notdan</a> the results that night via DM and posted the winning tweet the next morning:</p><h3>William Fleshman on Twitter: &quot;&quot;this was a faux vulnerability for credibility nobody questioned&quot;Time lapse of output as a super resolution resnet trains on the task: pic.twitter.com/uyZc8FrpfD / Twitter&quot;</h3><p>&quot;this was a faux vulnerability for credibility nobody questioned&quot;Time lapse of output as a super resolution resnet trains on the task: pic.twitter.com/uyZc8FrpfD</p><p>Later that day <a href="https://medium.com/u/6f68ff3b3da6">notdan</a> confirmed the win and in extremely generous fashion sent over the prize money + a bonus:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/890/1*pbJBzy_KZmgKHN3s55PSYg.png" /><figcaption><a href="https://twitter.com/notdan/status/1518934377165590528">https://twitter.com/notdan/status/1518934377165590528</a></figcaption></figure><h3>Closing Thoughts</h3><p>Twitter reactions to the results were a mix of amazement and fear. In general, I think the results do support the claim that pixelization is not a secure means of redaction. Just because the output is unrecognizable, what’s left can be thought of as an alphabet in a different language understandable (or learnable) by algorithms. Some information is lost through the process, but recoveries are still possible when paired with statistical information about the natural language.</p><p>On the other hand, I think <a href="https://medium.com/u/6f68ff3b3da6">notdan</a> was correct in his skepticism. As shown here, there is still a lot of fine tuning to the application that’s required for success. General solutions to arbitrary text super-resolution are unlikely due to numerous possible variations in background/text color, size, font, etc. The vulnerability should still be taken seriously, since it is often easy to derive these features for a specific targeted attack.</p><h3>Acknowledgements</h3><p>A huge thank you to <a href="https://medium.com/u/6f68ff3b3da6">notdan</a> for putting on this super interesting challenge. This is an incredible way to produce and share knowledge with the wider InfoSec community. Everyone buy him a coffee or send some XMR his way. Checkout his medium profile, <a href="https://twitter.com/notdan">twitter</a>, and show <a href="https://hacker.rehab/">HACKER.REHAB</a>.</p><p>Finally, thanks to the Benevolent Orangutan for discovering the competition, sharing it with me, motivating me to keep working on it, and providing the numerous insights and great back and forth throughout.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=577b4e6f4a89" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Evading Machine Learning Malware Classifiers]]></title>
            <link>https://medium.com/data-science/evading-machine-learning-malware-classifiers-ce52dabdb713?source=rss-797753643492------2</link>
            <guid isPermaLink="false">https://medium.com/p/ce52dabdb713</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[william-fleshman]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[infosec]]></category>
            <dc:creator><![CDATA[William Fleshman]]></dc:creator>
            <pubDate>Tue, 03 Sep 2019 16:43:12 GMT</pubDate>
            <atom:updated>2019-09-05T16:33:39.553Z</atom:updated>
            <content:encoded><![CDATA[<h4>for fun and profit!</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7EZVFnsyVnrMTJUkf03R8g.png" /></figure><h3>Introduction</h3><p>In this post, I’m going to detail the techniques I used to win the <a href="https://www.endgame.com/blog/technical-blog/machine-learning-static-evasion-competition">Machine Learning Static Evasion Competition</a> announced at this year’s DEFCON AI Village. The goal of the competition was to get 50 malicious Windows Portable Executable (PE) files to evade detection by three <a href="https://github.com/EndgameInc/malware_evasion_competition">machine learning malware classifiers</a>. Not only did the files need to evade detection, but they also had to maintain their exact original functionality and behavior.</p><p>This competition was sponsored by <a href="https://www.endgame.com/">Endgame</a>, <a href="https://www.mrg-effitas.com/">MRG-Effitas</a>, and <a href="https://www.vmray.com/">VM-Ray</a>. The competition was a ton of fun, and winning comes with an awesome <a href="https://www.nvidia.com/en-us/titan/titan-rtx/">prize</a>!</p><h3>Know Thy Enemy</h3><p>This was a white box competition; meaning I had full access to all model parameters and source code. Therefore, the first thing to do was crack open the models and see what was going on under the hood.</p><h4>MalConv</h4><p>The first model is a neural network trained on the raw bytes of Windows executables. MalConv is implemented in PyTorch, and if you’re already familiar with neural networks the <a href="https://github.com/endgameinc/malware_evasion_competition/blob/master/MalConv.py">code</a> is relatively simple and straight forward:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c8b40138b39c43eec6b7c9310a9952ee/href">https://medium.com/media/c8b40138b39c43eec6b7c9310a9952ee/href</a></iframe><p>Files are passed to MalConv as a sequence of integers representing the bytes of the file (0–255). An embedding layer inside MalConv maps each byte to a vector of numbers. The sequence of vectors can then be processed by additional neural network layers. The model outputs two numbers representing the probabilities of an input being benign and malicious.</p><p>There’s already a decent amount of literature out there on evading MalConv. The easiest attack is to just append a bunch of good looking stuff to the end of the executable. This is a particularly nice trick because the added data (also called the overlay) doesn’t get loaded into memory when the malware is executed. Therefore, we can put whatever we want in the overlay without changing the functionality of the file. MalConv looks for both benign and malicious byte patterns in order to make a decision. The purpose of the overlay attack is to overwhelm it with patterns associated with benign files.</p><h4>Non-Negative MalConv</h4><p>The second model is actually the same as the first but with different weights assigned to the layers. As the name suggests, Non-Negative MalConv was constrained during training to have non-negative weight matrices. The point of doing this is to prevent trivial attacks like those created against MalConv. When done properly, the non-negative weights make binary classifiers monotonic; meaning that the addition of new content can only increase the malicious score. This would make evading the model very difficult, because most evasion attacks do require adding content to the file. Fortunately for me, this implementation of Non-Negative MalConv has a subtle but critical flaw.</p><p>The non-negative defense only works for binary classifiers with a single output score representing the maliciousness of the sample. This version breaks the output into two scores: one for malicious and one for benign. Then, a softmax function converts the scores to probabilities for each class. This construction makes training with non-negative weights meaningless. Additional content can still push the benign score arbitrarily high. As the benign score goes higher, the softmax function will push the malicious score lower, even though the same amount of malicious content is present. So all of the same attacks against MalConv will work here as well.</p><p>If you’re interested in a bit more mathematical detail, check out Appendix A of this <a href="http://ci.louisville.edu/zurada/publications/chor-zur-tnnls.pdf">paper</a>. The authors prove that a softmax network with non-negative weights is essentially equivalent to an unconstrained network in regards to what it can learn. This is why for a proper defense it’s necessary to use a single output; we don’t want the network to learn to look for benign content.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/782/1*QgxKbfDwQkmAkVk2zmHvNw.png" /><figcaption>Excerpt from paper: <a href="http://ci.louisville.edu/zurada/publications/chor-zur-tnnls.pdf">http://ci.louisville.edu/zurada/publications/chor-zur-tnnls.pdf</a></figcaption></figure><h4>Ember</h4><p><a href="https://github.com/endgameinc/ember">Ember</a> is actually a data set maintained by Endgame. Along with the data set comes a trained benchmark model (which I’ll also call Ember). Ember is a <a href="https://lightgbm.readthedocs.io/en/latest/Python-Intro.html">lightgbm</a> model (an ensemble of boosted decision trees) trained on several features parsed from Windows PE files.</p><p>The source code for Ember’s feature parsing is located <a href="https://github.com/endgameinc/ember/blob/master/ember/features.py">here</a>. Seeing how all of the features are parsed was quite useful for crafting attacks. The extracted features include:</p><ul><li>Byte Histogram</li><li>Byte Entropy</li><li>Section Information (names, sizes, entropy, properties)</li><li>Import Table Libraries and Entries</li><li>Exported Functions</li><li>General File Info (sizes and counts of various things)</li><li>Header Info (machine, architecture, linker, versions, etc.)</li><li>Strings (various statistics about strings in the file)</li><li>Data Directories (names, sizes, virtual addresses)</li></ul><p>The numerical features are used as is, while the <a href="https://scikit-learn.org/stable/modules/feature_extraction.html#feature-hashing">hashing trick</a> is used to convert the rest of the features (like section names) to numerical vectors. At first glance, Ember looks more difficult to fool. Many of the features are related to the structure of the file or to characteristics which we won’t be able to change. Remember, we have to evade detection while maintaining the original functionality!</p><p>Ember’s vulnerability is that some of the features can be arbitrarily controlled by an attacker. The lightgbm model uses these features in multiple locations throughout the ensemble of trees. We can take advantage of the complexity of the model by manipulating the features in order to drive the decision down paths which result in evasion.</p><h3>Preparation</h3><p>The competition code came with a script for running all three models against a single file. I changed the script to evaluate the entire directory of malware and used <a href="https://altair-viz.github.io/index.html">altair</a> to add a fun visual scoreboard:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lCykwi8lNboCjKCrNq_VKQ.png" /><figcaption>Initial scan of original malware files.</figcaption></figure><p>The skull emoji represents that a model detected the malware, while the happy face represents an evasion. Interestingly, file 49 already evaded MalConv, so we get 1 point for free!</p><h3>Planning</h3><p>After sinking a few minutes into figuring out how to plot with emojis, I decided it was time to think through how to go about tackling this competition. The tricky part would be finding valid manipulations that impacted all three models simultaneously, or at least impacted one but didn’t throw red flags for the others. I decided to focus on attacks that would hopefully impact all three models at once.</p><h4>The Overlay</h4><p>As mentioned, PE files can have arbitrary content appended to them. These additional bytes are called the overlay, and they’re not loaded into memory when Windows executes the file. Therefore, adding bytes here won’t alter the functionality of the malware.</p><h4>Slack Space</h4><p>Besides the overlay, there is also room at the end of each section to add additional bytes. PE sections are required to be aligned to a power of 2 amount of memory. The section is padded out when the actual content does not fill this entire space. This portion of memory will not get accessed by the executable, so we can alter this space freely as well.</p><h4>New Sections</h4><p>In addition to adding bytes to existing sections, we can also create new sections. New sections won’t break the file’s functionality because there will be no references to them in the existing code. This gives us plenty of room to add whatever kind of content we want.</p><h4>Feature Focused</h4><p>Because the MalConv models treat everything as bytes (without structural context), for them we just have to focus on overwhelming their decision with patterns they attribute to benign files. However, the structure of Ember’s features require us to actually think through the specifics about what might hinder it.</p><p>The most obvious features we can manipulate are Byte Histogram and Byte Entropy. The Byte Histogram just calculates the normalized frequency of each byte value in the file. Because we can add sections containing anything, it is trivial to force the byte distribution to any target distribution we want.</p><p>We also have decent control over the Section Info features. We can change the entropy of the section by using the slack space. We could also change the section names which could take us down different branches in Ember’s decision trees.</p><p>Finally, the Strings feature is also highly vulnerable to manipulation. Again, because we can add new sections containing anything, we can skew the string statistics to our heart’s desire.</p><h3>LIEF</h3><p>All of the above modifications can be done using the same library that Ember uses to parse features: <a href="https://github.com/lief-project/LIEF">lief</a>. The LIEF project is pretty awesome, and I definitely recommend checking it out. I used it for parsing the malware, making the modifications, and rebuilding the PE files; it’s pretty amazing!</p><p>Here’s a short demo showing how easy it is to modify PEs:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4ff9c86c733d75990c3c3173698e5710/href">https://medium.com/media/4ff9c86c733d75990c3c3173698e5710/href</a></iframe><p>The general workflow is: parse the PE, make any modifications, build a new PE, save to disk.</p><h3>Validation VM</h3><p>I also had a Windows Virtual Machine setup for doing reverse engineering. It was important to observe the altered files to ensure they were behaving identically to the original malware. Anytime I need a throw away Windows VM, I grab one from <a href="https://developer.microsoft.com/en-us/microsoft-edge/tools/vms/">here</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/733/1*YmQ-AmYa6LX3D4UbqrxZtA.png" /><figcaption>Watching the Procmon output of an altered file being executed.</figcaption></figure><h3>Attack Time</h3><p>My plan was to start simple and add complexity as needed. New sections seem to be the most promising attack avenue, since it provides us with the ability to make major changes to both Ember’s features as well as the raw bytes of the file. I wrote the following function in order to add a section and fill it with a constant value:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3fab7ffb62e97e3ab364151e8819b489/href">https://medium.com/media/3fab7ffb62e97e3ab364151e8819b489/href</a></iframe><p>I rebuilt the PE after every section addition so that lief would handle all the addressing for me. It would have also been possible to assign the addresses by hand.</p><p>As an experiment, I appended a new section with 100,000 constant bytes to each file and monitored the evasion rate as I iterated over the constants (0–255). Several different values had success, but the value 169 (0xA9) caused the most evasions:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7EZVFnsyVnrMTJUkf03R8g.png" /><figcaption>Evasion success from adding a section filled with 100,000 0xA9’s to each file.</figcaption></figure><p>This simple attack devastated both of the neural network models. If we hadn’t figured out the bug in the non-negative model, this result should have tipped us off. A monotonic classifier shouldn’t be affected by this simple addition.</p><p>Ember stood up well against this naive attack. I would have to come up with a more clever way to alter its scores.</p><h4>Blending In</h4><p>Next, I went over to Microsoft’s download page and grabbed a copy of a random benign executable (<a href="https://download.microsoft.com/download/a/c/1/ac1ac039-088b-4024-833e-28f61e01f102/NETFX1.1_bootstrapper.exe">download link</a>). I ran the models on the file in order to confirm that it scored very low across the board. My plan was to mimic known good features from this file in hopes of causing evasions against Ember.</p><p>I ran the command line utility strings on the file. This utility parses out all printable strings from the binary. I found a large chunk of strings which appeared to contain Microsoft’s End User License Agreement (EULA). I grabbed this portion and saved it to a text file.</p><p>Obviously, some of the most common Windows PE files happen to have been made by Microsoft. Therefore, when training malware classifiers it’s likely that the training set has a bunch of Microsoft files labeled as benign. My idea was to exploit this possibility by adding stuff from my downloaded file to our malware. Things like the Microsoft EULA probably show up across many benign files. This should make the string statistics, byte distributions, and entropy more like benign files in general.</p><p>I wrote the following function to read in the strings from the saved file and put them in a new section of our malicious PEs:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7f6887eb1064fa6f2b86edf2ea188293/href">https://medium.com/media/7f6887eb1064fa6f2b86edf2ea188293/href</a></iframe><p>I used this attack to add 75 new sections to each file (the competition had a file size constraint I had to stay under). I also included the previous attack to maintain our MalConv evasions. The new results were quite promising:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*m8o6m8cxJmy26INbEeU6wA.png" /><figcaption>Evasion results from combined “String Attack” and “Constant Attack”.</figcaption></figure><h4>Final Touches</h4><p>I was down to only a handful of files left to evade. Upon further analysis, several of these files were packed. My manipulations were messing up their unpacking procedures and therefore breaking functionality.</p><p>To make matters worse, at least one of the files also appeared to have code to detect if it had been manipulated:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/921/1*5393akUkN2KRrycrSTk4gg.png" /><figcaption>This file has code to check itself for tampering…</figcaption></figure><p>My first thought was to crack open the file in a debugger and patch out the assembly instructions checking for tampering. Unfortunately, the file also had anti-debugging code that basic anti-anti-debugging procedures weren’t able to bypass.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/911/1*b_OvCm6j8jB0mMBc2qTebg.png" /><figcaption>The file also has anti-debug mechanisms.</figcaption></figure><p>It felt like I was quickly going down a dangerous rabbit hole, so I took a step back and thought things over.</p><p>Thankfully, the anti-tampering mechanism was only checking the portion of the PE that gets loaded into memory. So although I couldn’t add new sections, I should still be able to manipulate the overlay!</p><p>I had already seen that my string attack wasn’t strong enough to fool ember on these files. I needed a different way to figure out what content should be added to the overlay in order to cause an evasion. I turned to my <em>simple first</em> motto and wrote the following code to systematically try swaths of each byte value and add them to the file if they lowered Ember’s score. This continued in a greedy fashion until the file either evaded or got too large.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/63776f86bcb5c94ae208ef1919d13268/href">https://medium.com/media/63776f86bcb5c94ae208ef1919d13268/href</a></iframe><p>I swapped out Ember for the other two models and used the same method for adding the required bytes to evade those models as well. Again, because I’m adding bytes to the overlay, none of the packing, functionality, or anti-tampering checks were affected! I went back and ran this attack against all of the files, discovering it was able to universally result in evasion.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ST_uZ4Ave0XRhWuVo08Lxg.png" /><figcaption>Perfect Score!</figcaption></figure><h3>Conclusion</h3><p>It took relatively simple modifications to get all 50 files to evade detection by this ensemble of malware classifiers. Luckily, all of the models had vulnerabilities which could be exploited. If the Non-Negative MalConv model was implemented correctly, a perfect score may not have even been possible.</p><p>Readers may already be familiar with the <a href="https://skylightcyber.com/2019/07/18/cylance-i-kill-you/">recent discovery</a> of a simple method for evading a well known machine learning based AV product. While none of the competition classifiers were production systems, these results should serve as a caution to designers of machine learning based malware detectors in general. It can be very challenging to find a set of features that can discriminate between benign and malicious files while also being relatively safe under an adversarial threat model. As seen here, the small details can really matter!</p><p>Thanks again to <a href="https://www.endgame.com/">Endgame</a>, <a href="https://www.mrg-effitas.com/">MRG-Effitas</a>, and <a href="https://www.vmray.com/">VM-Ray</a> for putting on an interesting and quite enjoyable competition. Hopefully we see more InfoSec companies step up to this level of scrutiny and involvement with the broader machine learning/security community.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/30/0*oBDUrdYocPu0-yCY" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ce52dabdb713" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/evading-machine-learning-malware-classifiers-ce52dabdb713">Evading Machine Learning Malware Classifiers</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[Fundamentals of Machine Learning (Part 3)]]></title>
            <link>https://medium.com/data-science/fundamentals-of-machine-learning-part-3-b305933f00cd?source=rss-797753643492------2</link>
            <guid isPermaLink="false">https://medium.com/p/b305933f00cd</guid>
            <category><![CDATA[information-theory]]></category>
            <category><![CDATA[william-fleshman]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[William Fleshman]]></dc:creator>
            <pubDate>Mon, 04 Mar 2019 00:27:39 GMT</pubDate>
            <atom:updated>2019-03-04T12:53:34.485Z</atom:updated>
            <content:encoded><![CDATA[<h4>Information Theory</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*ehs-9U2Y7X_6b4Ym8JKBxg.gif" /></figure><h3>Introduction</h3><p>This is part 3 in a series on topics I consider fundamental to machine learning. These topics act as building blocks for gaining a deeper understanding of the field. So far we have covered:</p><ol><li><a href="https://towardsdatascience.com/probability-fundamentals-of-machine-learning-part-1-a156b4703e69">Probability Theory</a></li><li><a href="https://towardsdatascience.com/maximum-likelihood-estimation-984af2dcfcac">Maximum Likelihood Estimation</a></li></ol><p>The purpose of this post is to cover important concepts from Information Theory and describe how they are used in machine learning. Many of the topics here will build on concepts we discussed in the post on Probability Theory, such as independence and expectation.</p><p>I’ll be motivating and constructing these concepts using ideas from machine learning and statistics. If you have a background in Physics, you may have seen these concepts motivated differently (i.e. through thermodynamics).</p><h3>Information</h3><p>Let’s motivate our discussion by assuming our goal is to detect the author of a given text by the words that are used. Which words are useful for detecting authorship? Intuitively, words like “the”, “or”, and “it” aren’t going to be very useful, because those words have high probability of showing up in any text regardless of author. It seems that common words contain less information than rare words, and that information content is somehow directly related to probability.</p><p>Let’s make this more formal by letting x be a random variable representing all possible words, and <em>p</em>(<em>x</em>) be the probability of observing a specific word <em>x</em>. We’d like to create some quantifiable notion for the information gained by observing a specific word.</p><p>We’ll use <em>h</em>(<em>x</em>) to represent the information gained from observing word <em>x</em>. Similarly, for two words <em>x </em>and <em>y</em> we could write the information gained by observing them together as <em>h</em>(<em>x, y</em>). Our goal is to find a suitable <em>h</em>.</p><p>First, let’s consider the independence of two words <em>x</em> and <em>y</em>. Words like “football” and “score” are not independent, as seeing one makes the other more likely. Therefore, the information gained from seeing “score” after “football” should be small. Recall from <a href="https://towardsdatascience.com/probability-fundamentals-of-machine-learning-part-1-a156b4703e69">Part 1</a>, that independence formally means that <em>p</em>(<em>x, y</em>) <em>= p</em>(<em>x</em>)<em>p</em>(<em>y</em>). If two words <em>x</em> and <em>y</em> are unrelated, we want <em>h</em>(<em>x, y</em>) = <em>h</em>(x) +<em> h</em>(<em>y</em>). In other words, the information gained from seeing two unrelated words together should be the sum of the information gained by seeing them both alone.</p><p>We want our formula for <em>h</em> to be related to <em>p,</em> but we have this issue where the joint probability of independent observations is a product, yet the joint information is a sum. To solve this issue, we use the product rule of logarithms to turn the product into a sum:</p><p>log[<em>p</em>(<em>x, y</em>)] = log[<em>p</em>(<em>x</em>)<em>p</em>(<em>y</em>)] = log <em>p</em>(<em>x</em>) + log <em>p</em>(<em>y</em>).</p><p>Relating the information to the log of the probability seems to be the trick we needed. We write the information associated with x as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/241/1*12GpvpvfXHveILz_H10hPA.png" /><figcaption>Information gained from observing <em>x.</em></figcaption></figure><p>This formula meets our requirements that the more probable observations yield less information, and for two independent observations <em>x</em> and <em>y </em>we have <em>h</em>(<em>x, y</em>) = -log <em>p</em>(<em>x, y</em>) = -log [<em>p</em>(<em>x</em>)<em>p</em>(<em>y</em>)] = [-log <em>p</em>(<em>x</em>)] + [-log <em>p</em>(<em>y</em>)] = <em>h</em>(<em>x</em>) + <em>h</em>(<em>y</em>).</p><p>The base of the logarithm is an arbitrary choice. Information theorists generally use base 2 and call the units of information “bits”, whereas in machine learning it is common to use base <em>e</em> and call the units of information “nats”. An alternative view of this information quantity is that <em>h</em>(<em>x</em>) gives us the number of bits (if base 2) required to send a message <em>x </em>given some encoding<em>.</em></p><h3>Entropy</h3><p>We’ve just written down information as a function of a random variable. In <a href="https://towardsdatascience.com/probability-fundamentals-of-machine-learning-part-1-a156b4703e69">Part 1</a>, we learned that the expectation of a function <em>g </em>on a random variable x, gives us the expected value (or average) of g:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/356/1*0lW9RJPFj-qPePT-tChQ0Q.png" /><figcaption>Expectation of g(x) with respect to x.</figcaption></figure><p>The expectation of our information function <em>h</em> is one of the most fundamental concepts in information theory. This expectation is called the entropy of the random variable x and is often represented with a capital H:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/343/1*UcnpHsjumnZEbwhQivCgJw.png" /><figcaption>Entropy of random variable x.</figcaption></figure><p>The entropy is the expected value of the information function, or in other words, it’s the average amount of information gained by observing a random draw from <em>p</em>(<em>x</em>). This is a useful value to know!</p><p>An information theorist might use the entropy to calculate the expected number of bits needed to transmit a message of a given length. Better yet, to reduce transmission cost, it would be beneficial to find an encoding of messages such that the entropy is minimized. This would allow a transmitter to compress messages and send fewer bits per message.</p><p>Finding an efficient encoding is similar to finding an efficient representation of features for a machine learning problem. We’d like to represent our data with as few features as possible (to avoid overfitting and the curse of dimensionality) while still maintaining enough information to make accurate decisions.</p><p>We’ll see that this notion of entropy will be useful for thinking about several other important ideas.</p><h3>Cross Entropy</h3><p>Let’s go back to our author classification problem. Let’s simplify the problem by considering only two classes: {text is from author A, text is not from author A}. We’ll treat each document we’re trying to classify as a “bag of words”, meaning we don’t care about the order of the words, just which ones are present. We represent each document as a vector <strong>x</strong> where entry <em>j </em>is a 1 if word <em>j</em> is present in the document, and 0 otherwise.</p><p>We assume there is some ground truth distribution <em>p</em>(<strong>x</strong>) which gives us the probability that document <strong>x</strong> was written by author A. If we can learn this distribution, then for any document where <em>p</em>(<strong>x</strong>) &gt; 0.5, we can guess that the document was written by A.</p><p>But we don’t know <em>p</em>, so instead we write down a model <em>q</em> and try to fit the parameters of <em>q</em> so that it approximates <em>p.</em> Then we’ll use <em>q</em> to make decisions about whether or not A is the author of any given text.</p><p>Since we’re using <em>q</em>, the amount of information needed for classifying a document <strong><em>x</em> </strong>is <em>h</em>(<strong><em>x</em></strong>) = -log <em>q</em>(<strong><em>x</em></strong>). But if <strong>x</strong> is actually distributed by <em>p</em>, then the expectation of the information needed with respect to <strong><em>x</em></strong> is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/409/1*z02AHbDCq8lthX9XGNjq-Q.png" /><figcaption>Cross Entropy</figcaption></figure><p>This is the cross entropy of <em>q</em> with respect to a true distribution <em>p</em>. If we use this as a cost function and find the parameters of <em>q</em> which minimize the cross entropy, then the best solution will occur when <em>q</em> is identical to <em>p</em>.</p><p>Minimizing cross entropy is often the objective for logistic regression and neural networks used for classification. It can be shown that minimizing the cross entropy is equivalent to maximizing the likelihood of our model <em>q. </em>Therefore, this approach to solving classification finds the Maximum Likelihood Estimator as discussed in <a href="https://towardsdatascience.com/maximum-likelihood-estimation-984af2dcfcac">Part 2</a>.</p><h3>Relative Entropy (KL-Divergence)</h3><p>The cross entropy gives us the average amount of information needed to classify our documents given that we’re using <em>q</em> instead of <em>p</em>. Obviously, if we’re using <em>p,</em> then on average we’d only need <strong>H</strong>(x) amount of bits (the entropy of the true distribution). But since we’re using <em>q</em> it takes <strong>H</strong>(<em>p, q</em>) bits on average (the cross entropy).</p><p>How much worse is using <em>q</em>? Using <em>q </em>instead of <em>p</em> requires <strong>H</strong>(<em>p, q</em>)-<strong>H</strong>(x) extra bits. We call this value the relative entropy or Kullback-Leibler (KL) divergence. If we plug in the equations for cross entropy and entropy and then collect terms, we get that KL-Divergence is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/426/1*B4GwxbWoMsGA7_1A7YRD-A.png" /><figcaption>KL-Divergence</figcaption></figure><p>Again, this gives us the extra number of bits (or nats) needed given that we’re using <em>q</em> in place of <em>p</em>. The KL-Divergence is always greater than 0 unless <em>q</em> equals <em>p</em>. Therefore, it’s also a common objective function to minimize. Minimizing the KL-Divergence also minimizes the cross entropy, which we’ve already said is the Maximum Likelihood Estimator.</p><h3>Mutual Information</h3><p>We discussed earlier that some words aren’t independent of each other, and that the dependence causes us to get redundant information when we observe them both (“football” and “score” for example). We’d like some measure of how much information two variables share.</p><p>Recall, that if x<strong> </strong>and<strong> </strong>y<strong> </strong>are independent variables, then their joint distribution is <em>p</em>(x, y) = <em>p</em>(x)<em>p</em>(y). If they aren’t independent, then we can’t factor the joint distribution in this way. We don’t have any redundancy when the variables are independent, and as the variables get more dependent, the amount of redundant information increases. To quantify this, we use the mutual information of x and y:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/459/1*VBA6UH5fuAqX_4V0401ZYg.png" /><figcaption>Mutual Information.</figcaption></figure><p>The mutual information is the amount of extra information needed if we’re representing the true joint distribution with the independent factorization. If the variables are independent, then the KL-Divergence will be 0, otherwise it will grow as the variables increase in redundancy.</p><p>Mutual information has been frequently used to perform feature selection in machine learning. For a given feature, we can measure the feature’s mutual information with the class labels. If the mutual information is high, then the feature is a strong indicator of the class. For example, if author A always includes their name in their documents, then the mutual information between their name and the class will be extremely high.</p><p>Similarly, if we have too many features to consider, we can use mutual information between features to remove those that are redundant. If author A always includes their name and their home town, then we can safely remove their home town from our vocabulary and still perform well on the task.</p><h3>Conclusion</h3><p>In this post, we’ve covered the main concepts from Information Theory which are directly applicable to machine learning. This hasn’t been an exhaustive treatment in any sense, but these are concepts that I’ve personally seen come up time and time again in practice.</p><p>For more reading, I suggest checking out Christopher Bishop’s book <a href="https://www.microsoft.com/en-us/research/people/cmbishop/#!prml-book">Pattern Recognition and Machine Learning</a>. The entire book is a gold mine of knowledge, but the concepts I’ve discussed can all be found in Chapter 1 under the information theory section.</p><p>David MacKay’s book <a href="https://www.inference.org.uk/itprnn/book.pdf">Information Theory, Inference, and Learning Algorithms</a> is also very popular.</p><p>See you next time!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b305933f00cd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/fundamentals-of-machine-learning-part-3-b305933f00cd">Fundamentals of Machine Learning (Part 3)</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[Spectral Clustering]]></title>
            <link>https://medium.com/data-science/spectral-clustering-aba2640c0d5b?source=rss-797753643492------2</link>
            <guid isPermaLink="false">https://medium.com/p/aba2640c0d5b</guid>
            <dc:creator><![CDATA[William Fleshman]]></dc:creator>
            <pubDate>Thu, 21 Feb 2019 00:38:44 GMT</pubDate>
            <atom:updated>2019-02-21T07:09:53.323Z</atom:updated>
            <content:encoded><![CDATA[<h4>Foundation and Application</h4><h3>Introduction</h3><p>In this post, we’ll cover the ins and outs of spectral clustering for graphs and other data. Clustering is one of the main tasks in unsupervised machine learning. The goal is to assign unlabeled data to groups, where similar data points hopefully get assigned to the same group.</p><p>Spectral clustering is a technique with roots in graph theory, where the approach is used to identify communities of nodes in a graph based on the edges connecting them. The method is flexible and allows us to cluster non graph data as well.</p><p>Spectral clustering uses information from the eigenvalues (spectrum) of special matrices built from the graph or the data set. We’ll learn how to construct these matrices, interpret their spectrum, and use the eigenvectors to assign our data to clusters.</p><h3>Eigenvectors and Eigenvalues</h3><p>Critical to this discussion is the concept of eigenvalues<strong> </strong>and eigenvectors. For a matrix A, if there exists a vector x which isn’t all 0’s and a scalar λ such that Ax = λx, then x is said to be an eigenvector of A with corresponding eigenvalue λ.</p><p>We can think of the matrix A as a function which maps vectors to new vectors. Most vectors will end up somewhere completely different when A is applied to them, but eigenvectors only change in magnitude. If you drew a line through the origin and the eigenvector, then after the mapping, the eigenvector would still land on the line. The amount which the vector is scaled along the line depends on λ.</p><p>We can easily find the eigenvalues and eigenvectors of a matrix using numpy in Python:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/010b78e7abf118ff4423474ae9ab2453/href">https://medium.com/media/010b78e7abf118ff4423474ae9ab2453/href</a></iframe><p>Eigenvectors are an important part of linear algebra, because they help describe the dynamics of systems represented by matrices. There are numerous applications which utilize eigenvectors, and we’ll use them directly here to perform spectral clustering.</p><h3>Graphs</h3><p>Graphs are a natural way to represent many types of data. A graph is a set of nodes with a corresponding set of edges which connect the nodes. The edges may be directed or undirected and can even have weights associated with them.</p><p>A network of routers on the internet can easily be represented as a graph. The routers are the nodes, and the edges are the connections between pairs of routers. Some routers might only allow traffic in one direction, so the edges could be directed to represent which direction traffic can flow. The weights on the edges could represent the bandwidth available along that edge. With this setup, we could then query the graph to find efficient paths for transmitting data from one router to another across the network.</p><p>Let’s use the following undirected graph as a running example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/432/1*DCy-U_0ubtEZfOc94GRCyQ.png" /><figcaption>Graph with two disconnected components.</figcaption></figure><p>This graph has 10 nodes and 12 edges. It also has two connected components {0,1,2,8,9} and {3,4,5,6,7}. A connected component is a maximal subgraph of nodes which all have paths to the rest of the nodes in the subgraph.</p><p>Connected components seem important, if our task is to assign these nodes to communities or clusters. A simple idea would be to make each connected component its own cluster. This seems reasonable for our example graph, but it’s possible that the entire graph might be connected, or that the connected components are very large. There could also be smaller structures within a connected component which are good candidates for communities. We’ll shortly see the importance of this connected component idea for spectral clustering.</p><h4>Adjacency Matrix</h4><p>We can represent our example graph as an adjacency matrix, where the row and column indices represent the nodes, and the entries represent the absence or presence of an edge between the nodes. The adjacency matrix for our example graph looks like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/499bb086620fd504d11c43b3666d79cd/href">https://medium.com/media/499bb086620fd504d11c43b3666d79cd/href</a></iframe><p>In the matrix, we see that row 0, column 1 has a value of 1. That means that there is an edge connecting node 0 with node 1. If the edges were weighted, the weights of the edges would go in this matrix instead of just 1s and 0s. Since our graph is undirected, the entries for row i, col j will be equal to the entry at row j, col i. The last thing to notice is that the diagonal of this matrix is all 0, since none of our nodes have edges to themselves.</p><h4>Degree Matrix</h4><p>The degree<strong> </strong>of a node is how many edges connect to it. In a directed graph we could talk about in-degree and out-degree, but in this example we just have degree since the edges go both ways. Looking at our graph, we see that node 0 has degree 4, since it has 4 edges. We could also get the degree by taking the sum of the node’s row in the adjacency matrix.</p><p>The degree matrix is a diagonal matrix where the value at entry (i, i) is the degree of node i. Let’s find the degree matrix for our example:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/aafc4a46aa31a3fffe74e43302244a21/href">https://medium.com/media/aafc4a46aa31a3fffe74e43302244a21/href</a></iframe><p>First, we took the sum across axis 1 (the rows) of our adjacency matrix, and then we put those values into a diagonal matrix. From the degree matrix, we can easily see that nodes 0 and 5 have 4 edges, while the rest of the nodes have only 2.</p><h4>Graph Laplacian</h4><p>Now we’re going to calculate the Graph Laplacian. The Laplacian is just another matrix representation of a graph. It has several beautiful properties, which we will take advantage of for spectral clustering. To calculate the normal Laplacian (there are several variants), we just subtract the adjacency matrix from our degree matrix:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0499e18da26ad43e6398afa06f0b5995/href">https://medium.com/media/0499e18da26ad43e6398afa06f0b5995/href</a></iframe><p>The Laplacian’s diagonal is the degree of our nodes, and the off diagonal is the negative edge weights. This is the representation we are after for performing spectral clustering.</p><h4>Eigenvalues of Graph Laplacian</h4><p>As mentioned, the Laplacian has some beautiful properties. To get a sense for this, let’s examine the eigenvalues associated with the Laplacian as I add edges to our graph:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/864/1*p2vrLlFxdJgGZxCGO5WBmA.gif" /><figcaption>Eigenvalues of Graph Laplacian.</figcaption></figure><p>We see that when the graph is completely disconnected, all ten of our eigenvalues are 0. As we add edges, some of our eigenvalues increase. In fact, the number of 0 eigenvalues corresponds to the number of connected components in our graph!</p><p>Look closely as that final edge is added, connecting the two components into one. When this happens, all of the eigenvalues but one have been lifted:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/864/1*pemb5XDfUCnWQMTpAHmpfA.png" /><figcaption>Number of 0-eigenvalues is number of connected components.</figcaption></figure><p>The first eigenvalue is 0 because we only have one connected component (the whole graph is connected). The corresponding eigenvector will always have constant values (in this example all the values are close to 0.32).</p><p>The first nonzero eigenvalue is called the spectral gap. The spectral gap gives us some notion of the density of the graph. If this graph was densely connected (all pairs of the 10 nodes had an edge), then the spectral gap would be 10.</p><p>The second eigenvalue is called the Fiedler value, and the corresponding vector is the Fiedler vector. The Fiedler value approximates the minimum graph cut needed to separate the graph into two connected components. Recall, that if our graph was already two connected components, then the Fiedler value would be 0. Each value in the Fiedler vector gives us information about which side of the cut that node belongs. Let’s color the nodes based on whether their entry in the Fielder vector is positive or not:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/432/1*A5B5P03z6paOAIxb-Jnzdw.png" /><figcaption>Nodes colored based on whether their entry in the Fiedler Vector is &gt;0.</figcaption></figure><p>This simple trick has segmented our graph into two clusters! Why does this work? Remember that zero eigenvalues represent connected components. Eigenvalues near zero are telling us that there is almost a separation of two components. Here we have a single edge, that if it didn’t exist, we’d have two separate components. So the second eigenvalue is small.</p><p>To summarize what we know so far: the first eigenvalue is 0 because we have one connected component. The second eigenvalue is near 0 because we’re one edge away from having two connected components. We also saw that the vector associated with that value tells us how to separate the nodes into those approximately connected components.</p><p>You may have noticed that the next two eigenvalues are also pretty small. That tells us that we are “close” to having four separate connected components. In general, we often look for the first large gap between eigenvalues in order to find the number of clusters expressed in our data. See the gap between eigenvalues four and five?</p><p>Having four eigenvalues before the gap indicates that there is likely four clusters. The vectors associated with the first three positive eigenvalues should give us information about which three cuts need to be made in the graph to assign each node to one of the four approximated components. Let’s build a matrix from these three vectors and perform K-Means clustering to determine the assignments:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f417ac3d2a5260335d972d95579c976e/href">https://medium.com/media/f417ac3d2a5260335d972d95579c976e/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/432/1*omUQ6aCQ88uK2rapwOFgvw.png" /><figcaption>Spectral Clustering for 4 clusters.</figcaption></figure><p>The graph has been segmented into the four quadrants, with nodes 0 and 5 arbitrarily assigned to one of their connected quadrants. That is really cool, and that is spectral clustering!</p><p>To summarize, we first took our graph and built an adjacency matrix. We then created the Graph Laplacian by subtracting the adjacency matrix from the degree matrix. The eigenvalues of the Laplacian indicated that there were four clusters. The vectors associated with those eigenvalues contain information on how to segment the nodes. Finally, we performed K-Means on those vectors in order to get the labels for the nodes. Next, we’ll see how to do this for arbitrary data.</p><h3>Spectral Clustering Arbitrary Data</h3><p>Look at the data below. The points are drawn from two concentric circles with some noise added. We’d like an algorithm to be able to cluster these points into the two circles that generated them.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3vBzUSU1jFuSumrhyyhFgQ.png" /><figcaption>Circles Data.</figcaption></figure><p>This data isn’t in the form of a graph. So first, let’s just try a cookie cutter algorithm like K-Means. K-Means will find two centroids and label the points based on which centroid they are closest too. Here are the results:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rzgNKF9GVAStuGhQnhQgeQ.png" /><figcaption>K-Means Clustering of the Circles Data.</figcaption></figure><p>Obviously, K-Means wasn’t going to work. It operates on euclidean distance, and it assumes that the clusters are roughly spherical. This data (and often real world data) breaks these assumptions. Let’s try to tackle this with spectral clustering.</p><h4>Nearest Neighbors Graph</h4><p>There are a couple of ways to treat our data as a graph. The easiest way is to construct a k-nearest neighbors graph. A k-nearest neighbors graph treats every data point as a node in a graph. An edge is then drawn from each node to its k nearest neighbors in the original space. Generally, the algorithm isn’t too sensitive of the choice of k. Smaller numbers like 5 or 10 usually work pretty well.</p><p>Look at the picture of the data again, and imagine that each point is connected to its 5 closest neighbors. Any point in the outer ring should be able to follow a path along the ring, but there won’t be any paths into the inner circle. It’s pretty easy to see that this graph will have two connected components: the outer ring and the inner circle.</p><p>Since we’re only separating this data into two components, we should be able to use our Fiedler vector trick from before. Here’s the code I used to perform spectral clustering on this data:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/634976d7df5bccb1ac7352406c7076be/href">https://medium.com/media/634976d7df5bccb1ac7352406c7076be/href</a></iframe><p>And here are the results:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qmdN607THNkFEmR_yqWeOw.png" /><figcaption>Spectral Clustering of the Circles Data.</figcaption></figure><h4>Other Approaches</h4><p>The nearest neighbor graph is a nice approach, but it relies on the fact that “close” points should belong in the same cluster. Depending on your data, that might not be true. A more general approach is to construct an affinity matrix. An affinity matrix is just like an adjacency matrix, except the value for a pair of points expresses how similar those points are to each other. If pairs of points are very dissimilar then the affinity should be 0. If the points are identical, then the affinity might be 1. In this way, the affinity acts like the weights for the edges on our graph.</p><p>How to decide on what it means for two data points to be similar is one of the most important questions in machine learning. Often domain knowledge is the best way to construct a similarity measure. If you have access to domain experts, ask them this question.</p><p>There are also entire fields dedicated to learning how to construct similarity metrics directly from data. For example, if you have some labeled data, you can train a classifier to predict whether two inputs are similar or not based on if they have the same label. This classifier can then be used to assign affinity to pairs of unlabeled points.</p><h3>Conclusion</h3><p>We’ve covered the theory and application of spectral clustering for both graphs and arbitrary data. Spectral clustering is a flexible approach for finding clusters when your data doesn’t meet the requirements of other common algorithms.</p><p>First, we formed a graph between our data points. The edges of the graph capture the similarities between the points. The eigenvalues of the Graph Laplacian can then be used to find the best number of clusters, and the eigenvectors can be used to find the actual cluster labels.</p><p>I hope you enjoyed this post and find spectral clustering useful in your work or exploration.</p><p>See you next time!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=aba2640c0d5b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/spectral-clustering-aba2640c0d5b">Spectral Clustering</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[Linear Regression]]></title>
            <link>https://medium.com/data-science/linear-regression-91eeae7d6a2e?source=rss-797753643492------2</link>
            <guid isPermaLink="false">https://medium.com/p/91eeae7d6a2e</guid>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[maximum-likelihood]]></category>
            <category><![CDATA[linear-regression]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[william-fleshman]]></category>
            <dc:creator><![CDATA[William Fleshman]]></dc:creator>
            <pubDate>Mon, 11 Feb 2019 03:22:09 GMT</pubDate>
            <atom:updated>2020-03-27T23:06:18.428Z</atom:updated>
            <content:encoded><![CDATA[<h4>A unification of Maximum Likelihood Estimation and minimizing the sum of squares.</h4><h3>Introduction</h3><p>I recently wrote about maximum likelihood estimation in my ongoing series on the fundamentals of machine learning:</p><p><a href="https://towardsdatascience.com/maximum-likelihood-estimation-984af2dcfcac">Maximum Likelihood Estimation</a></p><p>In that post, we learned what it means to “model” data, and then how to use MLE to find the parameters of our model. In this post, we’re going to dive into linear regression, one of the most important models in statistics, and learn how to frame it in terms of MLE. The solution is a beautiful piece of mathematics, which like most MLE models, is rich with intuition. I’ll be assuming you’ve got a handle on the vocabulary I’ve covered in the other series (probability densities, conditional probabilities, likelihood function, iid data, etc.). If you see something here that you’re uncomfortable with, check out the <a href="https://towardsdatascience.com/probability-fundamentals-of-machine-learning-part-1-a156b4703e69">Probability</a> and <a href="https://towardsdatascience.com/maximum-likelihood-estimation-984af2dcfcac">MLE</a> posts from that series for clarity.</p><h3>The Model</h3><p>We use linear regression when our data has a linear relationship between the independent variables (our features) and the dependent variable (our target). In the MLE post, we saw some data that looked similar too this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*actuP8SqXsTz-d9G9OpUNA.png" /></figure><p>We observed that there appears to be a linear relationship between x and y, but it’s not perfect. We think of these imperfections as coming from some error or noise process. Imagine drawing a line right through the cloud of points. The error for each point would be the distance from the point to our line. We’d like to explicitly include those errors in our model. One method of doing this, is to assume the errors are distributed from a Gaussian distribution with a mean of 0 and some unknown variance σ². The Gaussian seems like a good choice, because our errors look like they’re symmetric about were the line would be, and that small errors are more likely than large errors. We write our linear model with Gaussian noise like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/391/1*iJrwssQh4dJARzeuQPw1kw.png" /><figcaption>Linear model with Gaussian noise term.</figcaption></figure><p>The error term is draw from our Gaussian, and then our observed y is then calculated by adding the error to the output of the linear equation. This model has three parameters: the slope and intercept of our line and the variance of the noise distribution. Our main goal is to find the best parameters for the slope and intercept of our line.</p><h3>Likelihood Function</h3><p>To apply maximum likelihood, we first need to derive the likelihood function. First, let’s rewrite our model from above as a single conditional distribution given x:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/448/1*S9Wo7Ay3O-CGarsNULSWOA.png" /><figcaption>Given x, y is drawn from a Gaussian centered on our line.</figcaption></figure><p>This is equivalent to pushing our x through the equation of the line and then adding noise from the 0 mean Gaussian.</p><p>Now, we can write the conditional distribution of y given x in terms of this Gaussian. This is just the equation of a Gaussian distribution’s probability density function, with our linear equation in place of the mean:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/820/1*3M7mJamXgcFPXzvD0U4yIA.png" /><figcaption>PDF of y given x and our linear model.</figcaption></figure><p>The semicolon in the conditional distribution acts just like a comma, but it’s a useful notation for separating our observed data from the parameters.</p><p>Each point is independent and identically distributed (iid), so we can write the likelihood function with respect to all of our observed points as the product of each individual probability density. Since σ² is the same for each data point, we can factor out the term of the Gaussian which doesn’t include x or y from the product:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/936/1*JXtvd6fO6ydgAqQR4jAaWQ.png" /><figcaption>Likelihood for our collection of data X.</figcaption></figure><p>(Note: Thanks to Tongxin for catching an error here. The term before the product should be raised to the number of data points because I factored it from the product.)</p><h4>Log-Likelihood:</h4><p>The next step in MLE, is to find the parameters which maximize this function. To make our equation simpler, let’s take the log of our likelihood. Recall, that maximizing the log-likelihood is the same as maximizing the likelihood since the log is monotonic. The natural log cancels out with the exponential, turns products into sums of logs, and division into subtraction of logs; so our log-likelihood looks much simpler:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gDNxsKgiWTj6AWmolmkjlQ.png" /><figcaption>Derivation of log-likelihood for our model.</figcaption></figure><h4>Sum of Squared Errors:</h4><p>To clean things up a bit more, let’s write the output of our line as a single value:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/251/1*tCAZf5pWI5UYyWLXiZ-tSw.png" /><figcaption>Estimate of y from our line.</figcaption></figure><p>Now our log-likelihood can be written as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/874/1*U8yya-GV548dLYdRVabERQ.png" /><figcaption>Simplified log-likelihood equation.</figcaption></figure><p>To remove the negative signs, let’s recall that maximizing a number is the same thing as minimizing the negative of the number. So instead of maximizing the likelihood, let’s minimize the negative log-likelihood:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/859/1*Y_B6FPJq0jb17qK04MVltw.png" /><figcaption>Minimize the negative log-likelihood.</figcaption></figure><p>Our ultimate goal is to find the parameters of our line. To minimize the negative log-likelihood with respect to the linear parameters (the θs), we can imagine that our variance term is a fixed constant.</p><p>Removing any constant’s which don’t include our θs won’t alter the solution. Therefore, we can throw out any constant terms and elegantly write what we’re trying to minimize as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/194/1*O8b2CNiqn3xjUF3fkklrXQ.png" /><figcaption>Sum of squared error.</figcaption></figure><p>The maximum likelihood estimate for our linear model is the line which minimizes the sum of squared errors! This is a beautiful result, and you’ll see that minimizing squared errors crops up everywhere in machine learning and statistics.</p><h3>Solving for Parameters</h3><p>We’ve concluded that the maximum likelihood estimates for our slope and intercept can be found by minimizing the sum of squared errors. Let’s expand out our minimization objective and use <em>i</em> as our index over our <em>n</em> data points:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/448/1*0zO8-m3ZdruX0hgJ4zLm9g.png" /></figure><p>The square in the SSE formula makes it quadratic with a single minimum. The minimum can be found by taking the derivative with respect to each of the parameters, setting it equal to 0, and solving for the parameters in turn.</p><h4>The Intercept:</h4><p>Let’s start by solving for the intercept. Taking the partial derivative with respect to the intercept and working through gives us:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/611/1*eiBpwnHiIa5SMP_Urxv0AQ.png" /><figcaption>Derivative of SSE with respect to the intercept of our line.</figcaption></figure><p>The horizontal bars over the variables indicate the mean of those variables. We used the fact that the sum over the values of a variable is equal to the mean of those values multiplied by how many values we have. Setting the derivative equal to 0 and solving for the intercept gives us:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/252/1*YzIf9e2kTWbjgx58wb-KXw.png" /><figcaption>MLE for intercept.</figcaption></figure><p>This is a pretty neat result. It’s the equation of the line, with the means of the x’s and y’s in place of those variables. The intercept still depends on the slope, so we’ll need to find that next.</p><h4>The Slope:</h4><p>We start by taking the partial derivative of the SSE with respect to our slope. We plug in our solution for the intercept and use algebra to isolate the slope term:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/933/1*UtfzD3enlt3o76IH5zqy6Q.png" /><figcaption>Derivative of SSE with respect to the slope of our line.</figcaption></figure><p>Setting this equal to 0 and solving for the slope gives us:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/305/1*D9pI8eUL7YqB9EK5Jqu-tA.png" /></figure><p>While we’re technically done, we can use some fancier algebra to rewrite this without having to use the <em>n</em>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/360/1*o0vOZ25b1h57UyidKsJlvQ.png" /><figcaption>MLE estimate of the slope.</figcaption></figure><h4>Putting it all together:</h4><p>We can use these derived equations to write a simple function in python for solving the parameters for any line given at least two points:</p><pre>def find_line(xs, ys):<br>    &quot;&quot;&quot;Calculates the slope and intercept&quot;&quot;&quot;<br>    <br>    # number of points<br>    n = len(xs)</pre><pre>    # calculate means<br>    x_bar = sum(xs)/n<br>    y_bar = sum(ys)/n<br>        <br>    # calculate slope<br>    num = 0<br>    denom = 0<br>    for i in range(n):<br>        num += (xs[i]-x_bar)*(ys[i]-y_bar)<br>        denom += (xs[i]-x_bar)**2<br>    slope = num/denom<br>    <br>    # calculate intercept<br>    intercept = y_bar - slope*x_bar<br>    <br>    return slope, intercept</pre><p>Using this code, we can fit a line to our original data (see below). This is the maximum likelihood estimator for our data. The line minimizes the sum of squared errors, which is why this method of linear regression is often called ordinary least squares.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*n7fVZGmC9ozGiR6JB-ppIA.png" /><figcaption>MLE solution to our Linear Regression model.</figcaption></figure><h3>Final Thoughts</h3><p>I wanted to write this post mostly to highlight the link between minimizing the sum of squared error and the maximum likelihood estimation approach to linear regression. Most people first learn to solve linear regression by minimizing the squared error, but it’s not generally understood that this is derived from a probabilistic model with baked in assumptions (like Gaussian distributed errors).</p><p>There is a more elegant solution for finding the parameters of this model, but it requires linear algebra. I plan to revisit linear regression after covering linear algebra in my fundamentals series, and show how it can be used to fit more complex curves like polynomials and exponentials.</p><p>See you next time!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=91eeae7d6a2e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/linear-regression-91eeae7d6a2e">Linear Regression</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[Maximum Likelihood Estimation]]></title>
            <link>https://medium.com/data-science/maximum-likelihood-estimation-984af2dcfcac?source=rss-797753643492------2</link>
            <guid isPermaLink="false">https://medium.com/p/984af2dcfcac</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[probability]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[william-fleshman]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[William Fleshman]]></dc:creator>
            <pubDate>Sun, 03 Feb 2019 22:25:12 GMT</pubDate>
            <atom:updated>2019-03-09T21:28:17.617Z</atom:updated>
            <content:encoded><![CDATA[<h3>Fundamentals of Machine Learning (Part 2)</h3><p>This is part two in a series of topics I consider fundamental to machine learning. Part one covered probability theory, which we will build on heavily in this post. If you need to refresh on probability check out part one:</p><p><a href="https://towardsdatascience.com/probability-fundamentals-of-machine-learning-part-1-a156b4703e69">Probability — Fundamentals of Machine Learning (Part 1)</a></p><h3>Introduction</h3><p><strong>Maximum Likelihood Estimation</strong> (MLE) is a frequentist approach for estimating the parameters of a model given some observed data. The general approach for using MLE is:</p><ol><li>Observe some data.</li><li>Write down a model for how we believe the data was generated.</li><li>Set the parameters of our model to values which maximize the likelihood of the parameters given the data.</li></ol><p>We’re going to cover the basics of creating models, understanding likelihood, and using the Maximum Likelihood Estimation process for fitting our parameters.</p><h3>Models</h3><p>A <strong>model</strong> is a formal representation of our beliefs, assumptions, and simplifications surrounding some event or process. Let’s look at a couple of examples to make this idea clear.</p><h4>Example: Coin Flip</h4><p>We’d like to build a model for flipping a specific coin. What do we know?</p><ul><li>The coin has two faces and an edge.</li><li>The faces have different designs.</li><li>The coin can sit on either face or the edge (see image below of coins sitting on their edge).</li><li>The weight of the coin.</li><li>The diameter and thickness of the coin.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*cwsWaGP-aleQgl4d" /><figcaption>Photo by <a href="https://unsplash.com/@ryanthomasang?utm_source=medium&amp;utm_medium=referral">Ryan Thomas Ang</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>What assumptions can we make?</p><ul><li>The different designs probably cause the coin’s center of mass to slightly favor one side over another.</li><li>There’s no way to measure the force or angle exerted on the coin when it’s flipped.</li></ul><p>Let’s take a first stab at writing down a model without simplifications:</p><ul><li>The initial position of the coin is drawn from a Bernoulli distribution. This represents the flipper’s preference of starting the coin heads up vs. heads down in their hand.</li><li>The force exerted on the coin is drawn from an exponential distribution.</li><li>The angle in which the force is exerted is drawn from a truncated normal distribution on the interval [-π, π].</li><li>The center of mass of the coin is at some coordinate (x,y,z) in a system where the center of the coin is the origin.</li><li>The force of gravity is … OK, I think you get the picture.</li></ul><p>The real world can be complicated. Sometimes, a simplified model can do just as well or better. Let’s make a simplified model:</p><ul><li>The outcome of the flip is drawn from a Bernoulli distribution with the probability of heads <em>p</em>, and the probability of tails (1-<em>p</em>).</li></ul><p>Our simplified model only has a single parameter! In part one, we learned that we can estimate this parameter by simply flipping the coin a few times and counting the number of heads we get. Fitting the complicated model would require many more flips and difficult calculations. So which model is right? My favorite quote in all of statistics is from George Box:</p><blockquote>“All models are wrong, but some are useful.”</blockquote><p>Usefulness is the key metric when designing models. In this case, I’d rather use the simplified model even though I know it’s wrong. How do I know it’s wrong? I’ve assigned 0 probability to the coin landing on its edge. I’ve never seen this happen in real life, so I’ve made the simplifying assumption that it can’t occur.</p><h4>Example: Linear Model</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*v7vf4KDstvjMKLXH9JmedQ.png" /></figure><p>In this example, we’ll work with the above figure. We’d like to build a model of the data in order to predict future values of y given x. The data almost looks like a line, so let’s start with that as our model.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/305/1*DFEPw-ku2bArFmqBD1Niww.png" /><figcaption>Equation of a line.</figcaption></figure><p>If the underlying relationship is actually linear, how do we account for the deviations we’re observing? Imagine we’re using a sensor to collect this data. Most sensors have some amount of error in their measurements. Similarly, we can think of the deviations from our model as being caused by an error prone sensor. It’s very common to model the error as being drawn from a Gaussian distribution with mean zero and variance σ². A mean of zero distributes the error equally on both sides of the line. The larger the variance, the larger the deviations. Let’s add a Gaussian noise term to our model. The resulting model has three parameters: the slope, the intercept, and the variance of the Gaussian.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/391/1*vOfadmTLY1Kn8hOhTunYYw.png" /><figcaption>Linear model with Gaussian error.</figcaption></figure><h3>Likelihood</h3><p>In both examples, we wrote our model down in terms of some parameters. In general, we might have any number of parameters, so let’s refer to the entire collection of them as<strong> θ </strong>(theta). How do we know what the values of <strong>θ</strong> should be? This is where <strong>likelihood</strong> comes into play. In part one, we talked about the likelihood of a continuous random variable taking on a specific value. We got this likelihood from the probability density function (PDF) for the distribution with the parameters fixed at some value. Instead of having fixed parameters, let’s think of the likelihood as a function of <strong>θ</strong> given the data we’ve observed. For a continuous distribution with PDF <em>f</em>(<em>x</em>|<strong>θ</strong>), the likelihood function becomes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/343/1*2vIp-1lRPG8Jpbum8NMhxQ.png" /></figure><p>Similarly, for a discrete distribution with probability mass function (PMF) P(<em>x</em>|<strong>θ</strong>), the likelihood function becomes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/360/1*Ha3bZb4npyWieby66ZUp0g.png" /></figure><p>We normally have more than a single data point to inform our decisions. How do we calculate the likelihood with respect to an entire collection of data X? Let’s look at the typical situation, where the data is independent and identically distributed (<strong>iid</strong>). Identically distributed means that each data point comes from the same distribution with the same parameters. Independence was covered in part one, and means that for any two data points <em>x </em>and<em> y</em>, P(<em>x, y</em>)=P(<em>x</em>)P(<em>y</em>). Coin flips are a good example of iid data. Every flip uses the same coin, and the outcome of a flip is independent of the flips before it. For iid X, we rewrite the likelihood function as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/491/1*CU8ILu6SqU3LnjXFzGgVwQ.png" /><figcaption>Likelihood is the product of probability density for each data point.</figcaption></figure><p>Notice the product operator in the likelihood function. Often times, individual likelihoods are very small numbers. Taking the product of small numbers creates smaller numbers, which computers can struggle to represent with finite precision. To alleviate these numerical issues (and for other conveniences mentioned later), we often work with the log of the likelihood function, aptly named the <strong>log-likelihood</strong>. Why does taking the log help? The product rule of logarithms says that log(x⋅y) = log(x) + log(y). So taking the log turns our product into a summation! The log-likelihood can then be written as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/589/1*kx8p3_Lp1-yTyeUeNvueKA.png" /><figcaption>Log-likelihood is the sum over the log of the likelihood for each point.</figcaption></figure><p>Logarithms are also monotone, which means that larger inputs produce larger outputs. Therefore, the maximum of the log-likelihood function will occur at the same location as the maximum for the likelihood function. Many probability distributions are written in the form of an exponential or contain exponents. The log and the exponential cancel each other out, and logs allow us to turn exponents into products. Both of these leave us with much simpler equations to maximize.</p><h3>Maximum Likelihood</h3><p>You’ve probably already put the pieces together, but let’s revisit our goal once more. We can write down a model for our data in terms of probability distributions. Next, we can write down a function over the parameters of our model which outputs the likelihood (or log-likelihood) that those parameters generated our data. The purpose of MLE is to find the maximum of that function, i.e. the parameters which are most likely to have produced the observed data.</p><p>Imagine we have some data generated from a Gaussian distribution with a variance of 4, but we don’t know the mean. I like to think of MLE as taking the Gaussian, sliding it over all possible means, and choosing the mean which causes the model to fit the data best. I’ve created a visualization of this process below, where we see the maximum of the log-likelihood occur at a mean of 2. In fact, that is the true mean of the distribution which created the histogram!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*jxZFpWtCbD4jHPV0DdDuMA.gif" /></figure><p>How do we do this process mathematically? If you’re familiar with calculus, you’ll know that you can find the maximum of a function by taking its derivative and setting it equal to 0. The derivative of a function represents the rate of change of the original function. If you look at the log-likelihood curve above, we see that initially it’s changing in the positive direction (moving up). It reaches a peak, and then it starts changing in a negative direction (moving down). The key is that at the peak, the rate of change is 0. So if we know the functional form of the derivative, we can set it equal to 0 and solve for the best parameters.</p><h3>Coin Flip MLE</h3><p>Let’s derive the MLE estimator for our coin flip model from before. I’ll cover the MLE estimator for our linear model in a later post on linear regression.</p><p>Recall that we’re modeling the outcome of a coin flip by a Bernoulli distribution, where the parameter <em>p</em> represents the probability of getting a heads. First, let’s write down the likelihood function for a single flip:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/685/1*KarwwAYUHbu61vibSCExPA.png" /><figcaption>Likelihood function for Bernoulli distribution.</figcaption></figure><p>I’ve written the probability mass function of the Bernoulli distribution in a mathematically convenient way. Take a second to verify for yourself that when <em>x</em>=1 (heads), the probability is <em>p</em>, and when <em>x</em>=0 (tails), the probability is (1-p).</p><p>Now, let’s assume we see the following sequence of flips:</p><p>X = heads, heads, tails, heads, tails, tails, tails, heads, tails, tails.</p><p>Since the coin flips are iid, we can write the likelihood of seeing a particular sequence as the product of each individual flip:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/853/1*P5IgiffLrqta3WaZYcg7Tg.png" /><figcaption>Likelihood of a sequence of flips.</figcaption></figure><p>Plugging in our data, we get:</p><p><em>L</em>(<em>p</em>) = <em>p</em> ⋅ <em>p</em> ⋅ (1-<em>p</em>) ⋅ <em>p</em> ⋅ (1-<em>p</em>) ⋅ (1-<em>p</em>) ⋅ (1-<em>p</em>) ⋅ <em>p</em> ⋅ (1-<em>p</em>) ⋅ (1-<em>p</em>).</p><p>Notice, that for every heads we get a factor of <em>p</em>, and for every tails a factor of (1-<em>p</em>). Let’s generalize this to <em>n</em> coin flips with <em>h </em>heads:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/655/1*F1ia6VulAE-Wyv9OJm5M6g.png" /><figcaption>Likelihood for n coin flips with h heads.</figcaption></figure><p>We want to find the <em>p</em> that maximizes this function. To make our job easier let’s take the log of both sides. This will bring the exponents down, and will turn the product into a sum. Taking the derivative of sums is easier than products (another convenience of log-likelihood). Remember, we can do this because the <em>p</em> that maximizes the log-likelihood is the same as the <em>p</em> that maximizes the likelihood. Our log-likelihood is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KZuVM_hwnlmZMakbZ-JOWw.png" /><figcaption>Log-likelihood of n coin flips with h heads.</figcaption></figure><p>To find the maximum we’re going to take the derivative of this function with respect to <em>p</em>. If you’re not comfortable with calculus, the important thing is that you know the derivative is the rate of change of the function. In this case, the derivative is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/509/1*MrUwg1-5RIoiK5OhH6R49w.png" /><figcaption>Derivative of the log-likelihood with respect to <em>p</em>.</figcaption></figure><p>We set the derivative equal to 0 to find the maximum of the function (where the rate of change is 0). Setting the above equation equal to 0 and solving for <em>p </em>(try doing this yourself)<em> </em>gives us:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/1*3lzimBiwe7EfHfFZqYGEcA.png" /><figcaption>The MLE estimate of p is the number of heads divided by the number of flips!</figcaption></figure><p>It turns out that the Maximum Likelihood Estimate for our coin is simply the number of heads divided by the number of flips! This makes perfect intuitive sense, if you flipped a fair coin (<em>p</em> = 0.5) 100 times, you’d expect to get about 50 heads and 50 tails.</p><h3>Conclusion</h3><p>Maximum Likelihood Estimation is a powerful technique for fitting our models to data. The solutions provided by MLE are often very intuitive, but they’re completely data driven. This means, that the more data we have, the more accurate our solutions become and vice versa. In a future post, we’ll look at methods for including our prior beliefs about a model, which will help us in low data situations.</p><p>Ready for part 3?:</p><p><a href="https://towardsdatascience.com/fundamentals-of-machine-learning-part-3-b305933f00cd">Fundamentals of Machine Learning (Part 3)</a></p><p>See you next time!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=984af2dcfcac" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/maximum-likelihood-estimation-984af2dcfcac">Maximum Likelihood Estimation</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[Probability — Fundamentals of Machine Learning (Part 1)]]></title>
            <link>https://medium.com/data-science/probability-fundamentals-of-machine-learning-part-1-a156b4703e69?source=rss-797753643492------2</link>
            <guid isPermaLink="false">https://medium.com/p/a156b4703e69</guid>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[william-fleshman]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[probability]]></category>
            <dc:creator><![CDATA[William Fleshman]]></dc:creator>
            <pubDate>Tue, 29 Jan 2019 22:45:35 GMT</pubDate>
            <atom:updated>2019-02-20T15:40:05.828Z</atom:updated>
            <content:encoded><![CDATA[<h3>Probability Theory</h3><h4>Fundamentals of Machine Learning (Part 1)</h4><p>This is part one in a series of topics I consider fundamental to machine learning. Probability theory is a mathematical framework for quantifying our uncertainty about the world. It allows us (and our software) to reason effectively in situations where being certain is impossible. Probability theory is at the foundation of many machine learning algorithms. The goal of this post is to cover the vocabulary and mathematics needed before applying probability theory to machine learning applications. The topics covered will be built upon in future posts!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/608/1*m-QPG32yj3NNksd4WE4GoA.png" /></figure><h3>Some Philosophy on Probability</h3><p>What exactly is probability? Most people know that the probability of an event is some value between 0 and 1 which indicates how likely the event is to occur. Seems simple enough, but where do those values actually come from?</p><p>The <strong>objectivist </strong>perspective is that randomness is fundamental to the universe. They would say that the probability of a fair coin coming up heads is 0.5, because that’s the nature of fair coins. Alternatively, the <strong>subjectivist </strong>viewpoint is that probabilities represent our degree of belief that an event will occur. If we knew the initial position of the coin and how the force was applied, then we could determine with certainty if it would come up heads or tails. Under this perspective, probability is a measure of our ignorance (like not knowing how the force is applied to the coin).</p><p>Personally, I’m a subjectivist. If we have the proper measurements we should be able to predict anything with certainty. One area where this isn’t true (yet) is quantum mechanics. To understand some quantum phenomena, we have to treat them as being truly random. It’s possible that one day we will have a better understanding of how the universe works, and therefore how to properly predict these phenomena as well. It seems that Albert Einstein shares in my subjectivism:</p><blockquote>“God does not play dice with the universe.”</blockquote><p>Whatever our beliefs of the true nature of randomness, we need some principled methods for actually estimating probabilities.</p><p>The <strong>frequentist’s </strong>position is that estimations come from experiments and experiments only. If we want to estimate how likely a six sided die is to roll a 4, we should roll the die a number of times and observe the frequency in which a 4 appears.</p><p>This method works well when we have a large amount of data, but with fewer examples we can’t be confident in our estimates. If we haven’t seen a 4 after five rolls, does that mean a 4 is impossible? The other issue is that we can’t inject any of our prior knowledge about dice into our estimates. If we knew the die was fair, not seeing a 4 in the first five rolls is completely understandable.</p><p>Another popular estimation philosophy is that of the <strong>Bayesian</strong>. A Bayesian treatment of probability allows us to combine our prior beliefs with our observations. Imagine that a coin we believe to be fair is flipped three times and results in three heads. A frequentist calculation would suggest the coin is loaded (although with low confidence), but our Bayesian prior that the coin is fair allows us to maintain some degree of belief that a tails is still possible. The actual mechanics of how we combine our prior belief relies on something called Bayes’ rule, which will be covered later.</p><h3>The Mathematics of Probability</h3><p>In the beginning, I suggested that probability theory is a mathematical framework. As with any mathematical framework there is some vocabulary and important axioms needed to fully leverage the theory as a tool for machine learning.</p><p>Probability is all about the possibility of various outcomes. The set of all possible outcomes is called the <strong>sample space</strong>. The sample space for a coin flip is {heads, tails}. The sample space for the temperature of water is all values between the freezing and boiling point. Only one outcome in the sample space is possible at a time, and the sample space must contain all possible values. The sample space is often depicted as Ω (capital omega) and a specific outcome as ω (lowercase omega). We represent the probability of an event ω as P(ω).</p><p>The two basic axioms of probability are:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/379/1*455Xw3AXawCWva3s0Jtv6g.png" /><figcaption>Axioms of Probability</figcaption></figure><p>In plain English, the probability of any event has to be between 0 (impossible) and 1 (certain), and the sum of the probabilities of all events should be 1. This follows from the fact that the sample space must contain all possible outcomes. Therefore, we are certain (probability 1) that one of the possible outcomes will occur.</p><p>A <strong>random variable</strong> x, is a variable which randomly takes on values from a sample space. We often indicate a specific value x can take on with italics. For example, if x represented the outcome of a coin flip, we might discuss a specific outcome as <em>x</em> = heads. Random variables can either be discrete like the coin, or continuous (can take on an uncountably infinite amount of possible values).</p><p>To describe the likelihood of each possible value of a random variable x, we specify a <strong>probability distribution</strong>. We write x ~ P(x) to indicate that x is a random variable which is drawn from a probability distribution P(x). Probability distributions are described differently depending on if the random variable is discrete or continuous.</p><h4><strong>Discrete Distributions:</strong></h4><p>Discrete random variables are described with a <strong>probability mass function</strong> (PMF). A PMF maps each value in the variable’s sample space to a probability. One such PMF is the uniform distribution over <em>n</em> possible outcomes: P(x=<em>x</em>) = 1/<em>n</em>. This reads as “The probability of x taking on the value <em>x</em> is 1 divided by the number of possible values”. It’s called the uniform distribution because each outcome is equally likely (the likelihood is spread uniformly over all possible values). Fair dice rolls are modeled by a uniform distribution since each face of the die is equally likely. A loaded die is modeled by a categorical distribution, where each outcome is assigned a different probability.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/684/1*gKGg7U3DdtgiiKqpmKgUbw.png" /></figure><p>Another common discrete distribution is the Bernoulli. A Bernoulli distribution specifies the probability for a random variable which can take on one of two values (1/0, heads/tails, true/false, rain/no rain, etc.). The PMF of a Bernoulli distribution is P(<em>x</em>) = {<em>p </em>if <em>x</em> =1, and 1-<em>p</em> if <em>x</em>=0}. Therefore, we can specify the entire distribution with a single parameter <em>p</em>, the probability of the positive outcome. For a fair coin we have <em>p</em> = 0.5, and so heads or tails is equally likely. Alternatively, if we say that the probability of rain tomorrow is <em>p</em> = 0.2, then we can infer that the probability of no rain is 0.8.</p><h4><strong>Continuous Distributions:</strong></h4><p>Continuous random variables are described by <strong>probability density functions </strong>(PDF) which can be a bit more difficult to understand. We generally indicate the PDF for a random variable x as <em>f</em>(<em>x</em>). PDFs map an infinite sample space to relative likelihood values. To understand this, let’s look at an example with one of the most famous continuous distributions, the Gaussian (Normal) distribution.</p><p>The Gaussian distribution (colloquially called the bell curve) can be used to model several natural phenomena. For example, heights of each gender are approximately Gaussian distributed. The Gaussian distribution is parameterized by two values: the mean μ (mu) and variance σ² (sigma squared). The mean specifies the center of the distribution, and the variance specifies the width of the distribution. You may have also heard about the standard deviation σ, which is just the square root of the variance. To indicate that x is a random variable drawn from a Gaussian with mean μ and variance σ², we write:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/309/1*b6yxU4ivLewyufRtxjpXOw.png" /><figcaption>X is drawn from a Normal distribution with mean μ and variance σ².</figcaption></figure><p>The functional form of the PDF for the Gaussian can be intimidating at first glance. I promise that after working with Gaussian distributions in applications the fear goes away! The functional form of the PDF is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/671/1*XhNxPXLsU3Q-BzA4bXzZew.png" /><figcaption>The PDF of x given μ and σ²</figcaption></figure><p>The left hand side of the equation says “The PDF of <em>x</em> given μ and σ² ”. The vertical bar represents the word “given” and indicates that we already know all of the values after it in the parenthesis . Let’s plot this equation given μ = 0 and σ² = 4:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/673/1*P1ho8E4v6MSfXCZ5zKNFNQ.png" /></figure><p>So what do I mean by relative likelihoods? Unlike discrete distributions, the value of the PDF at x = <em>x</em> is not the actual probability of <em>x</em>. This is a common misconception when people first start dabbling with probability theory. Since there are infinitely many values that x could take on, the probability of x taking on any specific value is actually 0! I’m guessing you don’t believe me, but let’s think about it together while we revisit our axioms.</p><p>Recall that the total probability for every possible value needs to sum to 1. How do we sum over an infinite number of values? The answer comes from calculus in the form of the integral. We can rewrite our axiom in terms of the PDF using the integral:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/425/1*Xgsk3qAICdosV55UnASzaA.png" /><figcaption>The integral of the PDF over the sample space is 1.</figcaption></figure><p>If you aren’t familiar with calculus, the integral is an operator which calculates the area under the curve <em>f</em>(<em>x</em>). It’s a generalization of the summation to an infinite amount of values. So the area under the PDF represents the total probability of the Gaussian! If you are familiar with calculus (and feel up to it) you can calculate the integral of the Gaussian yourself to confirm that the area is 1.</p><p>Because the area is what we’re interested in, it’s often more useful to work with a continuous random variable’s <strong>cumulative distribution function</strong> (CDF). We write the CDF, <em>F</em>(<em>x</em>) as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*x8DdNm9OAbIufxKLtvO2XQ.png" /><figcaption>CDF is a function of the integral of the PDF.</figcaption></figure><p>What in the world does that mean? Well, for a given value <em>x</em>, we’re taking the integral of the PDF from negative infinity to that value. So <em>F</em>(<em>x</em>) gives us the the area under the PDF for the interval negative infinity to <em>x</em>.</p><p>We just determined that the area corresponds to the probability, so <em>F</em>(<em>x</em>) gives us P(x≤<em>x</em>). Now, we can use the CDF to determine the probability of any given range [<em>a</em>,<em>b</em>] by noticing that P(<em>a</em>≤x≤<em>b</em>) = <em>F</em>(<em>b</em>)-<em>F</em>(<em>a</em>). This answers the question, “What is the probability that x will be between <em>a</em> and <em>b?”</em>.</p><p>Asking for P(x=<em>x</em>) is equivalent to asking P(<em>x</em>≤x≤<em>x</em>) = F(<em>x</em>)-F(<em>x</em>) = 0. So there you have it, the probability of sampling a specific number from the distribution is 0! (Stronger arguments could be made by actually taking the limit). Here’s the CDF for the same Gaussian from before:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/670/1*Qns3LMbAsx-B6DGQFU2SYg.png" /></figure><p>We see that the probability of x taking on values less than -2.5 is nearly 0. We also see that the values sampled from x will mostly be less than 2.5.</p><h4><strong>Joint Probability Distributions:</strong></h4><p>A distribution over multiple random variables is called a <strong>joint probability distribution</strong>. We can write a collection of random variables as a vector <strong>x</strong>. A joint distribution over <strong>x </strong>specifies the probability of any particular setting of all the random variables contained in <strong>x</strong>. To make this more clear, let’s consider two random variables x and y. We write the joint probability as P(x=<em>x</em>, y=<em>y</em>) or just P(<em>x</em>, <em>y</em>) for short. I say this out loud as “The probability that x=<em>x</em> and y=<em>y</em>”. If both random variables are discrete, we can represent the joint distribution as a simple table of probabilities. For example, let’s consider the joint distribution of which outer garment I wear with the weather conditions (in a universe where these are the only options):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/646/1*3ESAV1Rvdt7SZ-gyGCRAhw.png" /><figcaption>Joint Distribution of clothes and weather (in an odd universe)</figcaption></figure><p>This toy example highlights a few important things. First, I’m terrible at making toy examples. Second, notice that the table meets the requirements laid out by our axioms. We can immediately answer questions of the form P(clothes=T-Shirt, weather=Sunny), but joint distributions give us so much more!</p><h4><strong>Marginal Probability Distributions:</strong></h4><p>First, let’s look at the <strong>sum rule</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/397/1*1YfHOgYJSBbEaEex1AXjPQ.png" /><figcaption>Sum Rule</figcaption></figure><p>The term P(<em>x</em>) is called the <strong>marginal probability distribution</strong>, since we’ve “marginalized” away the random variable y. Let’s use the sum rule to calculate the probability I’ll wear a hoodie. P(Hoodie) = P(Hoodie, Sunny) + P(Hoodie, Cloudy) + P(Hoodie, Rainy) = 3/9. We could use the same process to find the marginal probability of any of the clothing items or any weather condition.</p><p>If P(<em>x</em>, <em>y</em>) was a joint distribution over continuous random variables, then to marginalize out y we turn the summation into an integration over y just like before.</p><h4><strong>Conditional Probability Distributions:</strong></h4><p>We’re also often interested in the probability of an event given that another event has already been observed. We denote the <strong>conditional probability distributions </strong>of x given y as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/335/1*6nvktt-uGGbhGER_aqyDCA.png" /><figcaption>Probability of x conditioned on observing y</figcaption></figure><p>In other words, if I’ve observed that y=<em>y</em>, then the probability that x=<em>x</em> is P(<em>x, y</em>)/P(<em>y</em>). Why does observing y change the probability of x? Well, imagine you saw me walk inside with a jacket on. Knowing that I’m wearing a jacket gives you information about the weather without observing the weather directly.</p><p>Note that the conditional probability only exists if P(<em>y</em>) &gt; 0. If it’s impossible for <em>y</em> to occur, then we couldn’t have observed <em>y </em>to begin with.</p><p>By multiplying both sides of the last equation by P(<em>y</em>) we get the <strong>chain rule</strong> of probability, P(<em>x, y</em>) = P(<em>x</em>|<em>y</em>) ⋅ P(<em>y</em>). The chain rule can be generalized to joint distributions with any number of random variables: P(<em>x, y, z</em>) = P(<em>x</em>|<em>y, z</em>) ⋅ P(<em>y, z</em>) = P(<em>x</em>|<em>y, z</em>) ⋅ P(<em>y</em>|<em>z</em>) ⋅ P(<em>z</em>).</p><h4><strong>Bayes’ Rule:</strong></h4><p>Notice that we can write the chain rule for two variables in two equivalent ways:</p><ul><li>P(<em>x, y</em>) = P(<em>x</em>|<em>y</em>) ⋅ P(<em>y</em>)</li><li>P(<em>x, y</em>) = P(y|<em>x</em>) ⋅ P(<em>x</em>)</li></ul><p>If we set both right sides equal to each other and divide by P(<em>y</em>), we get Bayes’ rule:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/422/1*5K_xXbSE3n84XBAWWYk_QA.png" /><figcaption>Bayes Rule</figcaption></figure><p>Bayes’s rule is crucially important to much of statistics and machine learning. As alluded to earlier, it’s the driving force behind Bayesian statistics. This simple rule allows us to update our beliefs about quantities as we gather more observations from data. I’ll definitely discuss Bayes’ rule (and Bayesian statistics) some more in a later post.</p><h4><strong>Independence and Conditional Independence:</strong></h4><p>In the previous example, we saw that P(<em>x|y</em>) ≠ P(<em>x</em>) because observing <em>y</em> gave us information about <em>x</em>. Is this always the case? Let’s imagine that P(<em>x, y</em>) is a joint distribution with x representing the amount of ice cream in a store and y representing the number of times per day that the moon is struck by an object. Does knowing either value give us any information about the other? Of course not! So in this case P(<em>x|y</em>) = P(<em>x</em>)! By plugging this into the chain rule, we find that in this scenario we get P(<em>x, y</em>) = P(<em>x|y) ⋅ P(</em>y<em>) = P(x</em>) ⋅ P(<em>y</em>). This leads us directly to our definition of<strong> independence</strong>. Two variables x and y are said to be independent if P(<em>x, y</em>) = P(<em>x</em>) ⋅ P(<em>y</em>).</p><p>A similar concept is that of <strong>conditional independence</strong>. Two variables x and y are called conditionally independent given another variable z if P(<em>x, y|z</em>) = P(<em>x|z</em>) ⋅ P(<em>y|z</em>). Let’s do an example to see what this is all about.</p><p>Let’s assume x is a random variable indicating whether I brought an umbrella to work, and y is a random variable indicating whether my grass is wet. It seems pretty obvious that these events are not independent. If I brought an umbrella it probably means it’s raining, and if it’s raining my grass is wet. Now let’s assume we observe variable z, which represents that it is in fact raining outside. Now, regardless of whether I brought an umbrella to work, you know that my grass is wet. So the condition of rain has made my umbrella independent of my grass being wet!</p><p>Independence and conditional independence become very important when we need to represent very large joint distributions. Independence let’s us factor our distribution into simpler terms, enabling efficient memory usage and faster calculations. We’ll see this concretely in a future post on Bayesian Networks!</p><h3>Functions of Random Variables</h3><p>It’s often useful to create functions which take random variables as input. Let’s consider a trip to the casino. It costs $2 to play my favorite game “guess a number between 1 and 10”. If you guess correctly you win $10. If you guess incorrectly you win nothing. Let x be a random variable indicating whether you guessed correctly. Then we can write a function<em> h</em>(<em>x</em>) = {$8 if <em>x </em>= 1, and -$2 if <em>x</em> = 0}. In other words, if you guess right you get $10 minus the $2 you paid to play, otherwise you just lose your $2. You might be interested in knowing in advance what the expected outcome will be.</p><h4><strong>Expectation:</strong></h4><p>The expected value, or<strong> expectation,</strong> of a function <em>h</em>(x) on a random variable x ~ P(x) is the average value of <em>h</em>(<em>x</em>) weighted by P(x). For a discrete x, we write this as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/557/1*fF4xGP48JTH4Mv9laRdbZw.png" /><figcaption>Expected Value of h(x) with respect to P(x)</figcaption></figure><p>If x had been continuous, we would replace the summation with an integral (I’ll bet you’re seeing a pattern by now). So the expectation acts as a weighted average over <em>h</em>(<em>x</em>), where the weights are the probabilities of each <em>x</em>.</p><p>What’s the expected value of playing the guessing game at the casino if we assume we have a 1/10 chance of guessing the correct number?</p><p>𝔼[<em>h</em>(x)] = P(winning) ⋅ <em>h</em>(winning) + P(loosing) ⋅ <em>h</em>(loosing)= (1/10) ⋅ $8 + (9/10) ⋅ (-$2) = $0.80 + (-$1.80) = -$1. So on average, we’ll loose $1 every time we play!</p><p>Another nice property of expectations is that they’re linear. Let’s assume <em>g </em>is another function of x, and α and β are constants. Then we have:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/865/1*jSpuasp7kuTiuDSGfanChA.png" /><figcaption>Expectations are linear</figcaption></figure><h4><strong>Variance and Covariance:</strong></h4><p>We saw variance with respect to a Gaussian distribution when we were talking about continuous random variables. In general, <strong>variance</strong> is a measure of how much random values vary from their mean. Similarly, for functions of random variables, the variance is a measure of the variability of the function’s output from its expected value.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/708/1*dsuyjMDk1RxiXqOjkheEKQ.png" /><figcaption>Variance of h(x) with respect to P(x)</figcaption></figure><p>Another important concept is <strong>covariance</strong>. Covariance is a measure of how linearly related two random variables (or functions on random variables) are with each other. The covariance between functions <em>h</em>(x) and <em>g</em>(y) is written as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Uno1sydiIwU8LAQ1sjhHEg.png" /><figcaption>Covariance between h(x) and g(y).</figcaption></figure><p>When the absolute value of covariance is high, the two functions tend to vary far from their means at the same time. When the sign of the covariance is positive, the two functions map to higher values together. If the sign is negative, one function maps to higher values, while the other function maps to lower values and vice versa. The visualization at the beginning of this post shows samples from a joint Gaussian distribution with positive covariance between the variables. You can see that as the first variable increases, so does the second.</p><h4>Moments:</h4><p>Note that we can calculate the expectation and variance for a random variable by replacing the function <em>h</em>(x) with x itself. The expectation of a distribution is its mean, or first moment. The variance of a distribution is its second moment. Higher order moments for probability distributions capture other characteristics like skewness and kurtosis.</p><h3>Important Distributions</h3><p>We’ve covered most of the important aspects of probability theory. These ideas act as building blocks for developing the underpinnings of the majority of statistics and machine learning. In order to master probability theory and start bridging the gap toward statistics, one needs to become somewhat familiar with the more useful probability distributions.</p><p>The functional forms of probability distributions can be intimidating. My advice is to not focus too much on that aspect and instead focus on what types of situation each distribution is good at modeling. Some examples of model/purpose descriptions include:</p><ul><li>Bernoulli: models the outcome of coin flips and other binary events</li><li>Binomial: models a series of Bernoulli trials (a series of coin flips, etc.)</li><li>Geometric: models how many flips necessary before you get a success</li><li>Multinomial: a generalization of the Binomial to more than two outcomes (like a die roll)</li><li>Poisson: models the number of events that occur in a certain interval</li></ul><p>For continuous distributions it’s also useful to know the shape. For example, we saw that the Gaussian distribution is shaped like a bell, with most of its density close to the mean. The Beta distribution can take on a wide range of shapes over the interval [0,1]. This makes the Beta distribution a good choice for modeling our beliefs about particular probabilities.</p><p>It’s also important to remember that these well formed distributions are more like templates than anything else. The true distribution of your data is probably not so nice and may even be changing over time.</p><h3>Great, but what’s all this have to do with Machine Learning?</h3><p>The goal of this post was to build up our language of probability so that we can frame machine learning in a probabilistic light. I’ll cover specific machine learning algorithms and applications in future posts, but I’d like to describe a bit of what we’ve just enabled.</p><h4><strong>Supervised Learning:</strong></h4><p>In supervised machine learning, our goal is to learn from labeled data. Data being labeled means that for some inputs X, we know the desired outputs Y. Some possible tasks include:</p><ul><li>Identify what’s in an image.</li><li>Predict the price of a stock given some features about the company.</li><li>Detect if a file is malicious.</li><li>Diagnose a patient with an illness.</li></ul><p>How can probability help us in these scenarios? We can learn a mapping from X to Y in various ways. First, you could learn P(Y|X), that is to say, a probability distribution over possible values of Y given that you’ve observed a new sample X. Machine learning algorithms that find this distribution are called <strong>discriminative</strong>. Imagine I tell you that I saw an animal that had fur, a long tail, and was two inches tall. Can you discriminate between possible animals and guess what it was?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*QjWB0RHmyzBgjQex" /><figcaption>Photo by <a href="https://unsplash.com/@sweetmangostudios?utm_source=medium&amp;utm_medium=referral">Ricky Kharawala</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Alternatively, we could instead try to learn P(X|Y), the probability distribution over inputs given labels. Algorithms for doing this are called <strong>generative</strong>. Given that I want a mouse, can you describe the possible heights, furriness, and length of tails that mice have? Enumerating the possible values for the features is sort of like generating all possible mice.</p><p>You may be wondering how knowing a generative model would help us with our task of classifying animals? Remember Bayes’ Rule? From our training data we can learn P(Y), the probability of any specific animal, and P(X), the probability of any specific configuration of the features. Using these terms we can answer queries in the form of P(Y|X) using Bayes’ Rule.</p><p>It’s possible to learn a mapping from X to Y which isn’t in the form of a probability distribution. We could fit a deterministic function <em>f </em>to our training data such that <em>f</em>(<em>X</em>) ≈ Y. What makes having a distribution better? Well, imagine an algorithm is diagnosing your illness, and it tells you that you have a month left to live. The function <em>f</em> can’t express to you how confident it is in the assessment. Maybe you have features that the algorithm never saw in the training data, causing it to more or less guess an outcome. The probabilistic model <strong>quantifies uncertainty</strong>, the regular function does not.</p><h4>Unsupervised Learning:</h4><p>Unsupervised learning is a broad set of techniques for learning from unlabeled data, where we just have some samples X but no output Y. Common unsupervised tasks include:</p><ul><li>Grouping similar data points together (clustering).</li><li>Taking high dimensional data and projecting it into a meaningful lower dimensional space (dimension reduction, factor analysis, embedding).</li><li>Representing the data with a distribution (density estimation).</li></ul><p>Characterizing the distribution of unlabeled data is useful for many tasks. One example is anomaly detection. If we learn P(X), where X represents normal bank transactions, then we can use P(X) to measure the likelihood of future transactions. If we observe a transaction with low probability, we can flag it as suspicious and possibly fraudulent.</p><p>Clustering is one of the canonical problems of unsupervised learning. Given some data points originating from separate groups, how can we determine which group each point belongs? One method is to assume that each group is generated from a different probability distribution. Solving the problem then becomes finding the most likely configuration of these distributions.</p><p>Dimension reduction is the other main area of unsupervised learning. High dimensional data takes up memory, slows down computations, and is hard to visualize and interpret. We’d like to have ways of reducing the data to a lower dimension without loosing too much information. One can think of this problem as finding a distribution in a lower dimensional space with similar characteristics to the distribution of the original data.</p><h4>Reinforcement Learning:</h4><p>The field of reinforcement learning is all about training artificial agents to perform well at specific tasks. The agents learn by taking actions in their environment and observing reward signals based on their behavior. The goal of the agent is to maximize its expected long term reward. Probability is used in reinforcement learning for several aspects of the learning process. You may have picked up on the word “expected” in the goal. The agent’s learning process often revolves around quantifying the uncertainty of the utility of taking one specific action over another.</p><h3>Conclusion</h3><p>This has been a gentle overview of the language of probability theory with a brief discussion on how we will apply these concepts to more advanced machine learning and statistics moving forward. Be sure to check out part two on Maximum Likelihood Estimation:</p><p><a href="https://towardsdatascience.com/maximum-likelihood-estimation-984af2dcfcac">Maximum Likelihood Estimation</a></p><p>If you’d like to tackle probability theory from another angle, I highly recommend checking out this amazing visual introduction from Seeing Theory:</p><p><a href="https://seeing-theory.brown.edu/">Seeing Theory</a></p><p>See you next time!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a156b4703e69" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/probability-fundamentals-of-machine-learning-part-1-a156b4703e69">Probability — Fundamentals of Machine Learning (Part 1)</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>
    </channel>
</rss>