<?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 Eugen Hotaj on Medium]]></title>
        <description><![CDATA[Stories by Eugen Hotaj on Medium]]></description>
        <link>https://medium.com/@eugenhotaj?source=rss-6454fd7d51dd------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*c5xG478VcXce8v-Xs75wIg.jpeg</url>
            <title>Stories by Eugen Hotaj on Medium</title>
            <link>https://medium.com/@eugenhotaj?source=rss-6454fd7d51dd------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 17:46:32 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@eugenhotaj/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[Talko: An End-to-End Chat Application]]></title>
            <link>https://medium.com/better-programming/writing-web-servers-from-first-principles-92ecce110480?source=rss-6454fd7d51dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/92ecce110480</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[microservices]]></category>
            <category><![CDATA[devops]]></category>
            <category><![CDATA[web-development]]></category>
            <dc:creator><![CDATA[Eugen Hotaj]]></dc:creator>
            <pubDate>Thu, 23 Apr 2020 23:37:11 GMT</pubDate>
            <atom:updated>2020-04-30T04:00:45.053Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*b2aeHXICZ_Wwe-boLyvqlQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*b2aeHXICZ_Wwe-boLyvqlQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*b2aeHXICZ_Wwe-boLyvqlQ.png" /></figure><h4>How to build a chat app from first principles (no libraries or frameworks)</h4><p>Web development is possibly the most ubiquitous form of programming that exists today. Frameworks like <a href="https://flask.palletsprojects.com/en/1.1.x/">Flask</a> and <a href="https://nodejs.org/en/">Node.js</a> have made writing web applications extremely accessible and hosting on sites like <a href="https://www.heroku.com/home">Heroku</a> is a breeze. While these frameworks are powerful, many people treat them as black boxes, using them without really understanding what’s going on under the hood. In this article, we’ll crack open the black box and see how to build a real-time chat application, <a href="https://www.github.com/EugenHotaj/talko">Talko</a> 🌮, from first principles. <em>We won’t use</em> <em>HTTP, </em><a href="https://requests.readthedocs.io/en/master/"><em>requests</em></a><em>, or frameworks.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/898/1*GIo29YIxNbt21KvUZEoYzg.gif" /><figcaption>Figure 1: A Talko web client (left) communicating with a Talko terminal client (right).</figcaption></figure><p>Starting with only TCP sockets, we’ll first implement a custom transfer protocol to allow our services to easily transfer messages between themselves. Then, we’ll implement two servers and a client library and use <a href="https://www.jsonrpc.org/">JSON-RPC</a> on top of the transfer protocol to communicate between them. Finally, using the client library, we’ll implement the two basic clients shown in Figure 1.</p><p><em>All working code accompanying this article can be found on </em><a href="https://www.github.com/EugenHotaj/talko"><em>my GitHub</em></a><em>.</em></p><h3>The Talko Transfer Protocol (TTP)</h3><p>Our main goal is to build as much of the application stack from scratch as possible. This means we won’t use HTTP and will instead build everything up using raw byte streams from TCP sockets. Communicating with raw byte streams quickly gets unwieldy, so we’ll devise the Talko Transfer Protocol (TTP) to formalize how our services can turn the byte streams into messages. (For some more background on why it makes sense to do this, take a look at the <em>TCP Sockets</em> appendix).</p><p>The main issue our protocol must solve is how to separate out different messages from the continuous byte stream. A straightforward approach is for the sender to tell the receiver exactly how many bytes are being sent. This can be done by attaching a header to the message which encodes how many bytes the message body is. The header must be of constant size, otherwise, the same issue would persist as services would not know how to separate the header from the body. TTP uses a 10 digit header, meaning we can send up to ~10 gigabyte messages, which should be good enough for most things. Finally, messages are encoded to utf-8 binary strings before being transmitted over the wire.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qMzhAzw8bvgPwlPuH7It9g.jpeg" /><figcaption>Figure 2: How the message “hello world” is encoded using the Talko Transfer Protocol. The ten digit header uses the two leading digits to encode the size of the body (11 bytes) followed by eight padding digits.</figcaption></figure><h3>Talko’s Architecture Overview</h3><p>Using TTP, we can now transfer data between any services we build. We’ll begin with a high-level overview of Talko’s architecture then dive into each component in more detail. Along the way, we’ll also discuss previous implementation approaches that didn’t pan out for various reasons. These sections are marked as <strong>Previous implementations</strong> so uninterested readers can skip them without losing the thread of the article.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OR4KyX5H0tOBmz0WBLyUiQ.jpeg" /><figcaption>Figure 3: A high level overview of Talko’s architecture.</figcaption></figure><p>As you can see from Figure 3 above, Talko is designed using a client-server architecture. The client communicates with two servers, the DataServer and the BroadcastServer, via a JSON-RPC <a href="https://github.com/EugenHotaj/talko/blob/master/talko/protocol.py">request/response protocol</a>. The DataServer is responsible for reading and writing chat data and exposes typical methods you’d expect from a <a href="https://en.wikipedia.org/wiki/Create,_read,_update_and_delete">CRUD</a> application. The client sends *Requests to the DataServer and the server responds with the corresponding *Response then closes the connection. To send follow up requests, the client must reopen the connection to the server.</p><p>The BroadcastServer handles real-time chat message delivery. It only exposes two methods to the client, OpenStreamRequest and CloseStreamRequest. When a client sends an OpenStreamRequest, the BroadcastServer responds with an OpenStreamResponse and, unlike the DataServer, keeps the client connection open so it can broadcast messages to it in the future. The final method the BroadcastServer exposes is BroadcastMessage. This is meant to be an internal method used only by the DataServer to inform the BroadcastServer that a particular message should be broadcast.</p><p>Besides the broadcast handshake described above, the client only communicates with the DataServer. For most requests, the DataServer simply reads and writes data to the SQLite database. However, for InsertMessageRequests, the DataServer also forwards the newly inserted message to the BroadcastServer so it can be broadcast to its recipients. Figure 4 shows the life of an InsertMessageRequest through the Talko backend.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dtoKMRRLvi1Y7oRTAtSsjg.jpeg" /><figcaption>Figure 4: How the Talko backend handles inserting new messages and broadcasting them to the receivers.</figcaption></figure><p>At a high level, when a user types in a new chat message, the user’s client uses the client library to send an InsertMessageRequest to the DataServer. The DataServer receives the request and stores the user’s message in the SQLite database. Once the message is successfully stored, the DataServer sends a BroadcastMessageRequest to the BroadcastServer and includes both the new message as well as the list of recipients. Finally, the BroadcastServer looks up the socket of each connected recipient and sends them the message.</p><h4>Previous implementations</h4><p>In a previous design, the role of the BroadcastServer and DataServer were flipped. To insert messages, clients would send InsertMessageRequests to the BroadcastServer using their long-lived connection. This approach was quickly abandoned as it was confusing for the client. Furthermore, it caused a huge bottleneck in the BroadcastServer by requiring the server to dedicate one thread per connected user in order to continuously listen for InsertMessageRequests.</p><h3>Database Storage</h3><p>When I first started working on Talko, I had no previous experience building chat applications. To get a general idea of how others approached this task, I googled around looking for some resources. What bothered me about most things I found is that they only mentioned how to connect two TCP sockets together and call it a day. But this is hardly a chat application! What happens when the receiving user is not online? How can we support group conversations? How is it possible to handle multiple connected clients?</p><p>To answer the first question, we need to store chat conversations in a database so messages are not lost if a user is offline. Talko uses SQLite since it’s natively supported by Python, but any database engine will work. A big downside of SQLite is that it’s not suited for production, but this is not a blocker for our case. Talko structures its data across four tables, Users, Chats, Participants, and Messages. The <a href="https://github.com/EugenHotaj/talko/blob/master/talko/schema.sql">schema</a> for each table is illustrated in Figure 5 below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/964/1*ZIfTiFwGFg-NsWl_TQ_42Q.jpeg" /><figcaption>Figure 5: The tables used to store Talko’s data. Foreign Keys are connected by arrows to their canonical Private Key.</figcaption></figure><p>Splitting the participants into a separate table makes it trivial to support both private (i.e. one-on-one) chats as well as group chats. Participants can be added or removed from groups by simply adding or removing a row from the Participants table. Furthermore, querying for group memberships can be made blazingly fast by creating indices on the Foreign Keys in the Participants table.</p><h4><strong>Previous implementations</strong></h4><p>Initially, Talko only supported private chats so participants were stored as separate columns in theChats table. However, it quickly became clear that this approach is not feasible for groups. For one thing, we would have to impose an arbitrary maximum group size since at a certain point we can’t keep adding columns to the Chats table. Querying for group memberships would also be slow and unwieldy as each individual column would have to be checked separately. Finally, adding and removing participants from a group would be similarly slow and tedious. Another approach is to store participants in a single column using arrays. While this mitigates the maximum group size limit, other issues are exacerbated.</p><h3>The Data and Broadcast Servers</h3><p>Talko’s DataServer and BroadcastServer comprise the <a href="https://github.com/EugenHotaj/talko/blob/master/talko/server.py">main logic</a> of the application. Besides correctness, a big focus was to make the servers as scalable as possible in order to handle hundreds to thousands of simultaneously connected users. One way to achieve this scalability is by heavily parallelizing across requests. Thankfully, individual requests are self-contained so this is pretty easy to do.</p><p>Both servers use the same basic set up. A main thread accepts new client connections and directly hands off the connection to a worker thread for processing. Since there’s only one main thread, it’s imperative that work is handed off as quickly as possible, otherwise the main thread would bottleneck the whole server. One technicality is that Talko uses <a href="https://docs.python.org/3.9/library/multiprocessing.html">processes</a> instead of threads to work around <a href="https://wiki.python.org/moin/GlobalInterpreterLock">Python’s GIL</a> and achieve maximum parallelism.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/924/1*lkWSARlrFtFhOH8fyHRFiw.jpeg" /><figcaption>Figure 6: An overview of Talko’s servers. Each server uses a single main thread to accept new connections (red envelopes). Connections are immediately handed off to worker threads for processing. In addition, the Broadcast Server uses an in-memory socket_table to share connections across threads.</figcaption></figure><p>While the DataServer is stateless, the BroadcastServer needs to keep track of all connected users in order to broadcast messages between them. To do this, the server uses an in-memory socket_table to store user_id → socket. When a new client connects, their socket is added to the socket_table for later use. A socket is only explicitly removed from the socket_table if the client sends a CloseStreamRequest. However, it’s much more likely that the client will close the connection without first sending a CloseStreamRequest (e.g. by closing the Talko tab in their web browser). This means that the BroadcastServer will leak memory by indefinitely keeping around closed sockets. This can be fixed by either having a background thread periodically purge closed sockets or by lazily removing them next time they’re used.</p><h4>Previous implementations</h4><p>Talko was not designed using micro-services initially. Instead, all of the logic was encapsulated inside one server. However, this made the code a lot messier and harder to reason about. Micro-services naturally arose as an effort to make the overall logic simpler. That being said, there are definite drawbacks to this approach, such as maintaining multiple servers and eating the cost of an extra (albeit fast) RPC for each BroadcastMessageRequest.</p><h3>The Client Library</h3><p>It would be quite tedious to have all clients manually handle communicating with both servers. To slightly ease the burden, we abstract most of the details behind a <a href="https://github.com/EugenHotaj/talko/blob/master/talko/client.py">client library</a>. The library exposes the necessary methods a client needs to interact with the Talko backend without getting bogged down with the exact details.</p><p>In particular, the library exposes two ways clients can get real-time messaging — <a href="https://en.wikipedia.org/wiki/Push_technology#Long_polling">long-polling</a> or continuous streaming. Long polling is provided by simply waiting some time for a message from the back end and returning an empty response if nothing is received within the interval. For continuous streaming, the library returns a (blocking) generator to the client which yields new messages as they come in. The client can receive new messages asynchronously by iterating over the generator in a separate thread.</p><h4><strong>Previous implementations</strong></h4><p>I’m particularly proud of the generator approach. In a previous attempt, the client library accepted a callback from the client which would then call in a separate thread for each new message. This forced the client library to act as a pseudo-server by managing threads for the client — clearly a bad idea. Pushing the threading responsibility to the client allows the library to be completely stateless.</p><h3>User Interfaces</h3><p>Having implemented all the necessary components, it’s now trivial, using the client library, to write clients that interface with the backend. We won’t cover the specifics of how to do this here as it’s outside the scope of this article. If you’re interested in the details, code for both an <a href="https://en.wikipedia.org/wiki/Ncurses">ncurses</a> client and a Flask web client is available <a href="https://github.com/EugenHotaj/talko/tree/master/talko/ui">on GitHub</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5upJXlrJmzrgSp_H12Nbww.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SZKp7D4MofC5UrWtWyCwjw.png" /><figcaption>Figure 6: (Left) A Talko web client written using Flask. (Right) A Talko terminal client written using ncurses.</figcaption></figure><h3>(A Surprising) Conclusion</h3><p>In this article, we built a chat application starting from nothing but TCP sockets. Although we built mostly custom components, our final implementation matches fairly closely to how modern web servers and frameworks are written. <em>This was not my goal.</em></p><p>Indeed, I tried to eschew as many of the established best practices as possible and wanted to truly build everything from first principles. For example, I did not initially set out to write a request/response protocol, opting instead to stream data bidirectionally between services. When this became too unwieldy, message passing clearly emerged as the next logical step. In this sense, a lot of the best practices unintentionally arose during the implementation. <em>This was somewhat surprising to me.</em> Perhaps it implies that a lot of the best practices really are the best way to structure web applications. Or perhaps, giving up preconceived beliefs is a lot harder than we think.</p><h4>The Long Road Ahead</h4><p>Although Talko is a fully functioning application in its current form, making it production-ready it would be a herculean effort. The biggest issue is that all communication happens in plain text and is susceptible to <a href="https://en.wikipedia.org/wiki/Sniffing_attack">data sniffing</a>, <a href="https://en.wikipedia.org/wiki/Man-in-the-middle_attack">man-in-the-middle attacks</a>, etc. Using TLS and encrypting messages end-to-end is imperative to protect ourselves against these threats. Talko also doesn’t have any real error handling for things like malformed requests, missing data, duplicate entries, etc. Finally, the database would have to be upgraded, the SQL queries would need to be tuned, and the overall application would have to be made more robust.</p><p>If you enjoyed this article, follow me to get notified when I post new stuff. All the code is available on <a href="https://www.github.com/EugenHotaj/talko">my GitHub</a>.</p><p>Eugen Hotaj,<br>April 23, 2020</p><h3>Appendix — TCP Sockets</h3><p>If you’re reading this article, chances are you’re already familiar with how most services communicate over the internet. One service (the client) requests some data from another service (the server) which then responds back with the requested data. It turns out that this request/response scheme is arbitrarily imposed by the communication protocol (HTTP in this case) and what’s happening under the hood is somewhat different.</p><p>In order to transmit data, two services first establish a connection between themselves, usually by using <a href="https://en.wikipedia.org/wiki/Network_socket">TCP Sockets</a>. This creates a bi-directional channel that either service can use to both send and receive data from the other. Besides ensuring that data arrives in the same order that it was sent, TCP doesn’t really impose any rules. The data can be practically anything: bytes, strings, random digits of PI, corrupted images, etc. There’s also no restriction on communication. One service can choose to completely ignore data from the other, only read every third byte, etc.</p><p>With this much freedom, it becomes almost impossible for services to communicate in a way that both will understand. This is where HTTP comes in. It establishes a common protocol which services can use to send and receive data in a uniform way. The protocol imposes restrictions on what data can be sent (for example an HTTP request) as well as how the communication should occur (each request gets one response). HTTP is what makes it possible for disparate services on the open internet to easily communicate with each other.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=92ecce110480" width="1" height="1" alt=""><hr><p><a href="https://medium.com/better-programming/writing-web-servers-from-first-principles-92ecce110480">Talko: An End-to-End Chat Application</a> was originally published in <a href="https://betterprogramming.pub/">Better Programming</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to Get Beautiful Results with Neural Style Transfer]]></title>
            <link>https://medium.com/data-science/how-to-get-beautiful-results-with-neural-style-transfer-75d0c05d6489?source=rss-6454fd7d51dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/75d0c05d6489</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[towards-data-science]]></category>
            <category><![CDATA[neural-style-transfer]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <dc:creator><![CDATA[Eugen Hotaj]]></dc:creator>
            <pubDate>Sat, 28 Mar 2020 00:32:52 GMT</pubDate>
            <atom:updated>2020-03-31T21:02:26.800Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*esra58I1ZIpcHeUjpro_6Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*zut4OvEX6h_1jkIX64EE0w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*3IdVhB62IBQhXHIJTbNeVg.png" /></figure><h4>A deep dive into the tricks that make Neural Style Transfer work</h4><p>I recently became interested in generating a Medium profile picture with Machine Learning. This pulled me deep into the land of Neural Style Transfer. While NST is conceptually simple to understand, generating high quality images is surprisingly difficult. There are a lot of intricate details and unmentioned tricks that one must implement correctly in order to get great results. In this article, we’ll dive deep into Neural Style Transfer and examine what these tricks are in detail.</p><p>There are a number of solid introductions to NST, both on Medium and other publications, so I won’t waste any time going over the basics. If you have no idea what NST is (or you want to follow along with the article) a great way to get started is by looking at the <a href="https://pytorch.org/tutorials/advanced/neural_style_tutorial.html">official PyTorch tutorial</a>. Unfortunately, like many other introductory articles, the final implementation generates mediocre results at best (Figure 1). We’ll spend the next few sections updating the tutorial code to improve the transfer quality, but first we go on a tangent.</p><p><em>All the accompanying code for this article can be found on </em><a href="https://github.com/EugenHotaj/nn-hallucinations"><em>my GitHub</em></a><em>.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XKRk2Vr0bse4GkkWf6UNXg.png" /><figcaption>Figure 1: A comparison of Neural Style Transfer quality for two different implementations. (Bottom Left) The image whose content we want to match. (Top Left) The image whose style we want to match. (Middle) Style transfer result using the PyTorch tutorial implementation. (Right) Style transfer result using the implementation detailed in this article. The generated image is of visually higher quality and matches the style of the style image more faithfully.</figcaption></figure><h3>An aside: why does the Gram matrix measure style?</h3><p>Most of the <a href="https://arxiv.org/abs/1508.06576">Gatys et al. paper</a> which introduced Neural Style Transfer is simple and straightforward to understand. However, one question that does not get addressed is why the Gram matrix is a natural way to represent style (i.e. texture)?</p><p>At a high level, the Gram matrix measures the correlations between different feature maps in the same layer. A feature map is simply the post-activation output of a convolutional layer. For example, if a convolutional layer has 64 filters, it will output 64 feature maps. The Gram matrix then measures the correlation (similarity) between each feature map and every other feature map in the layer, without necessarily caring about exact pixel positions. To illustrate why this is a reasonable measure of texture, suppose we have two filters, one which detects blue things and one which detects spirals. We can apply these filters to an input image to produce 2 filter maps and measure their correlation. If the filter maps are highly correlated, then any spiral present in the image is almost certain to be blue. This means the texture of the image is composed of blue spirals, instead of red, green, or yellow spirals.</p><p>Although this explanation still leaves me slightly uneasy, it seems to be a widely accepted fact in the texture synthesis community that the Gram matrix corresponds to style, as <a href="https://ptrrupprecht.wordpress.com/2017/12/05/understanding-style-transfer/">this article</a> explains. Furthermore, we can’t deny that the results we get by using the Gram matrix are impressive.</p><h3>Fixing the PyTorch implementation</h3><p>The first step to improve transfer quality is to fix the PyTorch tutorial implementation. The tutorial tries to be faithful to the Gatys et al. paper but misses a few things along the way. For one thing, the paper’s authors replace the MaxPool2d with an AvgPool2d as they found it produces higher quality results. Another detail is that the tutorial computes the ContentLoss and StyleLoss on the outputs of the convolutions instead of the the ReLU activations. This is more of a nitpick since I did not notice a big difference between using the convolutions vs. the ReLUs in my experiments.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/0*5Lk8jWtWkHfg0rUm.jpg" /><figcaption>Figure 2: The VGG19 network and its layers (<a href="https://www.researchgate.net/figure/llustration-of-the-network-architecture-of-VGG-19-model-conv-means-convolution-FC-means_fig2_325137356">source</a>).</figcaption></figure><p>The most egregious difference between the tutorial and paper is that the “wrong” layers are used for the ContentLoss and StyleLoss respectively. I put wrong in quotes as the choice of layers is largely subjective and depends heavily on what produces the most pleasing style. That being said, there are some rules of thumb we can use to guide our decision. When measuring content similarity, the lower layers tend to activate most highly when there is a pixel perfect match between the content_img and the generated input_img. The deeper we go into the network, the less the layers care about an exact match, and instead activate highly when features are generally in the right place. To visualize what each layer is most concerned with, we can set style_weight=0 and run the training process on a random input_img using different layers as the content_layer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bSV2t00wFnkuYL0AP93SuQ.png" /><figcaption>Figure 3: Visualizing what content different layers of the VGG19 network respond to. Layers further to the right are deeper in the network.</figcaption></figure><p>The tutorial uses the 4th convolution (conv2_2 in Figure 2) as the content layer. As we can see in Figure 3 above, this is likely too low of a layer to use for content as the network still cares about matching pixels exactly at this depth. Gatys et al. use conv4_2 instead, which is much more concerned with the overall feature arrangement instead of individual pixels.</p><p>In the case of style, lower layers respond to small repetitive features while higher layers capture more abstract, global features. Therefore, in order to transfer the whole style of the style_img— from low level details to overarching motifs — we should include layers from all depths in the network. The tutorial uses the first 5 convolution layers, but these are all fairly low in the network and are unlikely to capture global features. Gatys et al. use conv1_1, conv2_1, conv3_1, conv4_1, and conv5_1, a nice distribution of layers across the entire network hierarchy. We can use the same method we used for content to visualize the style each choice of layers is optimizing for. To do this, we set content_weight=0, specify which style_layers we want to use, and run the training process on a random input_img.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/621/1*2RGHWW3GEy_EaYq3Vd0Ing.png" /><figcaption>Figure 4: (Left) The style produced by the layers chosen in the PyTorch tutorial. (Right) The style produced by the layers chosen in the <a href="https://arxiv.org/pdf/1508.06576.pdf">Gatys et al. paper</a>.</figcaption></figure><p>As expected, the style optimized by the tutorial layers captures low level, repetitive features but fails to capture high level, global features.</p><h3>Improving the transfer quality</h3><p>The fixes we’ve implemented so far should get us fairly close to the quality seen in the Gatys et al. paper. From here, we’ll go even deeper and look at what next steps we can take to generate even better images.</p><p>One of the first things I changed from the paper was to switch the optimizer from L-BFGS to Adam. In the paper, the authors claim that L-BFGS results in higher quality transfer but I did not notice a difference when using Adam in my experiments. Furthermore, Adam seemed to be more stable, especially when training for a large number of steps or with a large style_weight. In these cases, L-BFGS seemed to NaN out, probably due to exploding gradients (though I didn’t look too deeply into it).</p><p>Another minor tweak was to switch the mse_loss (i.e. L2 loss) to l1_loss. I can’t think of a good reason to use L2 loss for style transfer (besides differentiability at 0) as the square term heavily penalizes outliers. As alluded to in the previous section, we don’t really care about matching pixels exactly and can tolerate a few outliers in the generated image. Indeed, the outliers may even lead to more visually pleasing results as the style and content features are blended together. Finally, the authors of <a href="https://distill.pub/2017/feature-visualization/">Feature Visualization</a> — a must read article on a related topic — also use l1_loss for their task, likely for similar reasons.</p><p>Actually, a lot of the tricks used to generate high quality Feature Visualizations elegantly transfer over to Neural Style Transfer. In fact, FV and NST are conceptually very similar and only differ in how they generate the input_img. In NST the input_img is optimized to activate different layers in a network in the same way as the content_img and style_img. FV on the other hand does not use a content_img and style_img but instead generates an input_img which maximally excites neurons in different layers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/350/1*x89fDTofVmZ2PF0QLnCDCA.png" /><figcaption>Figure 5: Rotation artifacts at the top right edge of the generated image caused by aggressive data augmentation .</figcaption></figure><p>One trick I borrowed from FV is to use data augmentation on the input_img. This works exactly the same as with regular classification tasks: at each step, we apply some augmentations to the input_img (e.g rotation, cropping, resizing, etc.) before running it through the model and computing the loss. By augmenting the input_img at each step, we’re forcing the input_img to generate features which are robust to minor perturbations. These robust features should contain less high frequency artifacts and generally look more visually appealing.¹ However, I found the augmentations used in the Feature Visualization article to be very aggressive and had to scale them down appropriately. Even so, there are still some rotation artifacts that develop around the edges of the generated image (Figure 5). The simplest way to get rid of these artifacts is to just crop the image down by a few pixels 🙃.</p><p>Finally, the last modification I made was to switch the content_layer to conv3_2 instead of the conv4_2 Gatys et al. use. Most of the articles I read also recommend conv4_2, though I found that fine details get washed out at conv4_2 and the style overpowers the content in the generated image. On the other hand, conv3_2 still maintains these fine details without over-penalizing for pixel perfectness like lower layers do. Indeed, we can confirm that this is the case by looking at the Figure 3 again.</p><h3>Further quality improvements</h3><p>We’ve now discussed all the tricks I’ve implemented in my Neural Style Transfer <a href="https://github.com/EugenHotaj/nn-hallucinations">code</a>. At this point, we’ve substantially improved the transfer quality over the original PyTorch tutorial. Furthermore, the content_weight and style_weight are a lot more robust to the specific choice of images. For example, in the PyTorch tutorial, I found that a good style_weight on one set of images did not readily transfer to another set without proper tuning.</p><p>That being said, it’s possible to get even better results by trying to remove high frequency noise in the generated image. The most interesting approach to this that I came across was from the article <a href="https://distill.pub/2018/differentiable-parameterizations/#section-styletransfer">Differentiable Image Parameterization</a> — another must read which touches on similar topics. In the article, the authors generate the input_img by first parameterizing it in (decorrolated) Fourier space instead of (corrolated) pixel space. Since the input_img is generated via gradient descent, decorrelating the input acts as a preconditioner which makes optimization easier by allowing gradient descent to find minima more quickly (similar to <a href="https://www.quora.com/Why-is-it-important-to-remove-correlated-features-in-machine-learning">removing correlated features</a> in supervised learning tasks). W<em>hy that leads to higher quality transfer is not entirely clear to me</em>, besides hand-wavy explanations like the minima found in decorrelated space are wider and more robust.</p><p>A simpler approach is to dampen high frequency noise by penalizing it either directly or indirectly. The noise can be directly penalize by adding the <a href="https://en.wikipedia.org/wiki/Total_variation_denoising">total variation loss</a> of the input_img to the optimization objective. Conversely, it’s possible to <a href="https://www.auduno.com/2015/07/29/visualizing-googlenet-classes/">implicitly penalize</a> the noise by either blurring the input_img after each gradient descent step, or by blurring the gradients before applying them to the input_img. One issue with both approaches is that they also adversely penalize true high frequency features. This can be somewhat ameliorated by scaling down either the total variation loss or the amount of blur during training.</p><h3>Conclusion</h3><p>If you made it this far, you should now know quite a lot about generating beautiful images with Neural Style Transfer. While conceptually simple, getting high quality results requires a lot of care. My original goal was to use Machine Learning to generate a Medium profile picture. After much trial and error, I think I’ve stumbled on something that looks pretty striking. To me, the most exciting part of this whole process is the end-to-end differentiability of Neural Networks. With very little effort, we were able to “invert” a model originally trained to discriminate between cats and dogs, and use it to generate countless images in a myriad different styles. Try doing that with a random forest.</p><p>If you enjoyed this article, follow me to get notified when I post new stuff. All the code is available on <a href="https://github.com/EugenHotaj/nn-hallucinations">my GitHub</a>.</p><p>Eugen Hotaj,<br>March 27, 2020</p><h3>Footnotes</h3><ol><li>Robust features have also <a href="https://reiinakano.com/2019/06/21/robust-neural-style-transfer.html">been shown</a> to produce high quality transfer results in non-VGG architectures. For reasons <a href="https://www.reddit.com/r/MachineLearning/comments/7rrrk3/d_eat_your_vggtables_or_why_does_neural_style/">not yet understood</a>, non-VGG architectures do not work out-of-the-box for Neural Style Transfer.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=75d0c05d6489" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/how-to-get-beautiful-results-with-neural-style-transfer-75d0c05d6489">How to Get Beautiful Results with Neural Style Transfer</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[Why is Machine Learning Feasible?]]></title>
            <link>https://medium.com/data-science/is-learning-feasible-8e9c18b08a3c?source=rss-6454fd7d51dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/8e9c18b08a3c</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[towards-data-science]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[learning]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Eugen Hotaj]]></dc:creator>
            <pubDate>Fri, 29 Nov 2019 23:14:06 GMT</pubDate>
            <atom:updated>2020-03-27T04:44:58.803Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xTToiWrCVLw2oEbjz0Yzbw.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@rocknrollmonkey?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Rock’n Roll Monkey</a> on <a href="https://unsplash.com/s/photos/robot?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><h3>Why Is Machine Learning Feasible?</h3><h4>A quick foray into the foundations of learning</h4><p>It’s late 2019 and the hype around Machine Learning has grown to unreasonable proportions. It seems like every week a new state of the art result is reported, a slicker Deep Learning library surfaces on GitHub, and OpenAI releases a GPT-2 model with more parameters. With the mind-bending results we’ve seen so far, it’s hard not to get swept up in the hype.</p><p>Others, however, warn that Machine Learning has overpromised and underdelivered. They worry that such continued action could cause research funding to dry up, leading to another Artificial Intelligence winter. This would be bad news indeed. Therefore, in order to curb the enthusiasm around Machine Learning, and single-handedly prevent the inevitable AI winter, I will convince you that <strong>learning is not feasible</strong>.</p><p><em>This article was adapted from the book “Learning from Data” [1].</em></p><h3>The Learning Problem</h3><p>Fundamentally, the goal of Machine Learning is to find a function <em>g</em> which most closely approximates some unknown target function <em>f</em>.</p><p>For example, in Supervised Learning, we are given the value of <em>f</em> at some points <em>X</em>, and we use these values to help us find <em>g</em>. More formally, we are given a dataset <em>D = {(x₁, y₁), (x₂, y₂), …, (xₙ, yₙ)} </em>where<em> yᵢ = f(xᵢ) </em>for<em> xᵢ ∈ X</em>. We can use this dataset to approximate <em>f</em> by finding a function <em>g </em>such that <em>g(x) ≈ f(x) </em>on <em>D</em>. However, the goal of learning is not to simply approximate <em>f</em> well on <em>D, </em>but to approximate <em>f</em> well everywhere. That is, we want to <em>generalize</em>. To drive this point home, take a look at the figure below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/597/1*iehVjXsBaUAqwZOB7WrB2A.jpeg" /><figcaption>Two different approximations to the function f.</figcaption></figure><p>Both <em>g </em>and <em>g’ </em>perfectly match <em>f</em> on the training data (denoted by the “x”s in the figure). However, <em>g</em> is clearly a better approximator of <em>f </em>than<em> g’</em>. What we want is to find a function like <em>g</em>, not <em>g’.</em></p><h3>Why Learning is not Feasible</h3><p>Now that we’ve set up the learning problem, it’s worth stressing that the target function <em>f </em>is <em>genuinely</em> <em>unknown</em>. If we knew the target function, we wouldn’t need to do any learning at all, instead we would just use it directly. And, since we don’t know what <em>f </em>is, regardless of what <em>g </em>we ultimately chose, there is <em>no way</em> for us to verify how well it approximates <em>f</em>. This may seem like a trivial observation, but the rest of this article will hopefully demonstrate its ramifications.</p><p>Suppose that the target function <em>f </em>is a Boolean function with a three-dimensional input space, i.e. <em>f: X → {0, 1}, X = {0, 1}³</em>. This is a convenient setup for us to analyze since it’s easy to enumerate all possible functions in the space [2]. We want to approximate <em>f </em>with a function <em>g</em> by making use of the training data below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/191/1*pODTl73xi7ywnZXasQDDcw.jpeg" /><figcaption>Training data available to approximate f. Here, x is the input and y = f(x). For clarity, we use ○ to indicate an output of 0 and ● to indicate an output of 1.</figcaption></figure><p>Since we want to find the best possible approximation to <em>f</em>, let’s only keep the functions in the space which agree with the training data and get rid of all the others.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Cv6u4VNjgzvaa8ZG0B4zKQ.jpeg" /><figcaption>All possible target functions which agree with the training data.</figcaption></figure><p>Great, now we’re down to only 8 possible target functions, labeled <em>f₁</em> to <em>f₈</em>, in the figure above. For convenience we’ve also kept around the labels of the training data. Notice that we don’t have access to the out of sample labels since we don’t know what the target function is.</p><p>Now the question becomes, which function do we choose as <em>g? S</em>ince we don’t know which <em>f </em>is the real target function, maybe we can try to hedge our bets by choosing a <em>g</em> which agrees with the most potential target functions. We can even use the training data to guide our choice (learning!). This sounds like a promising approach. But first, let’s define what we mean by “agrees with the most potential target functions.”</p><h4>Learning the best hypothesis</h4><p>In order to determine how good a hypothesis (i.e. a choice of <em>g</em>) is, we first need to define an objective. One straightforward objective is to give a hypothesis one point each time it agrees with one of the <em>fᵢ</em> on the out of sample input. For example, if the hypothesis agrees with <em>f₁</em> on all inputs, it gets 3 points, if it agrees on 2 inputs, it gets 2 points, and so on for all <em>fᵢ</em>. It’s easy to see that the maximum number of points a hypothesis can score is 24. However, to score 24 points, the hypothesis would have to agree with all possible target functions on all possible inputs. This is, of course, impossible since the hypothesis would have to output both 0 and 1 for the same input. If we ignore impossible scenarios, then the maximum number of points is only 12.</p><p>The only thing left to do now is pick a hypothesis and evaluate it. Since we’re smart humans, we can look at our training data and “learn” if there is a pattern there. The XOR function seems to be a good candidate: output 1 if the input has an odd number of 1s, otherwise output 0. It agrees with the training data perfectly, so let’s see how well it does on the objective.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZCU73pDf396UQjyL2kAVKg.jpeg" /><figcaption>Computing the objective value for the XOR hypothesis.</figcaption></figure><p>If we go through the exercise, we see that, on the out of sample data, XOR agrees with one function exactly (+3 points), three functions on two inputs (+6 points), three functions on one input (+3 points), and does not agree at all with one function (+0 points), giving a grand total of 12 points. Perfect! We were able to find a hypothesis which achieves the highest possible score. There may be other hypotheses that are as good, but we’re guaranteed that these is no hypothesis which is better than the XOR. There may even be hypotheses that are worse which get less than 12 points. In fact, let’s find one such bad hypothesis just so we can sanity check that XOR is indeed a good candidate for the target function.</p><h4>The worst possible hypothesis?</h4><p>If XOR is one of the best hypotheses, an obvious candidate for a bad hypothesis is its exact opposite, ¬XOR. For each input,¬XOR outputs 0 if XOR outputs 1 and vice versa.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vYr9kTF6_Z5N6EjBER5GwQ.jpeg" /><figcaption>Computing the objective value for the ¬XOR hypothesis.</figcaption></figure><p>Going through the exercise again, we now see that, on the out of sample data, ¬XOR agrees with one function exactly (+3 points), three functions on two inputs (+6 points), three functions on one input (+3 points), and does not agree at all with one function (+0 points), giving a perfect score… again. In fact, <em>any</em> function we choose as our hypothesis will get a perfect score. This is because any function <em>must</em> agree with one — and only one — of the possible target functions exactly. From there, it’s easy to see that any <em>fᵢ</em> will match three of the other <em>fᵢ</em> on two inputs, three on one input, and one on no inputs.</p><p>What’s shocking is that we can choose a perfect hypothesis without even looking at the training data. Even worse, we can choose a hypothesis which completely disagrees with the training data, and it would still achieve a perfect score. In fact, this is exactly what ¬XOR did.</p><blockquote>This means that all functions are equally likely to agree with the target function on the out of sample data, regardless of whether they agree on the training.</blockquote><p>Put another way, the fact that a function agrees with the training data gives <em>no information whatsoever </em>on how well it will agree with the target function out of sample. <em>Since all we actually care about is performance out of sample, why do we even need to learn?</em> This isn’t just true for Boolean functions either, but for any possible target function whatsoever. Here’s a figure which illustrates the point more clearly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5BRKFpj4zOeKlG4-6XpyUQ.jpeg" /><figcaption>Valid values the function f could take for input &gt; n.</figcaption></figure><p>Knowing <em>f</em> on <em>(-∞, n)</em> tells us nothing about its behavior on [n, ∞). Any of the dotted lines could be valid continuations of <em>f</em>.</p><h3>Probability, the Saving Grace</h3><p>Maybe this is the part you expect me to say that it’s all been a huge joke and explain how I pulled the wool over your eyes. Well, it’s no joke, but clearly Machine Learning works in practice, so there must be something we’re missing.</p><p>The reason learning “works” is due to a crucial, fundamental assumption known as the <a href="https://en.wikipedia.org/wiki/Independent_and_identically_distributed_random_variables">i.i.d assumption</a>: <em>both</em> the training data <em>and</em> the out of sample data are <strong>i</strong>ndependent and <strong>i</strong>dentically <strong>d</strong>istributed. This simply means that our training data should be representative of the out of sample data. This is a reasonable assumption to make: we can’t possibly expect what we learn on the training data to generalize out of sample if the out of sample data differs significantly. Put more simply, if all our training data comes from <em>y = 2x</em>, then we can’t possibly learn anything about <em>y = -9x² + 5</em>.</p><p>The i.i.d assumption also roughly holds in practice — or at least does not break down too significantly. For example, if a bank want to build a model using information from past clients (training data), they can reasonably assume that their new clients (out of sample data) won’t be too different. We didn’t make this assumption in the Boolean function example above, so we couldn’t rule out any <em>fᵢ</em> from being the true target function. If we do, however, assume that the output of the target function on the out of sample data is similar to the training data, then clearly f₁ or f₂ are most likely to be the target function. But of course, we can never know for sure 😉.</p><p>Eugen Hotaj<br>November 29, 2019</p><p><em>If you liked this article, follow me on Medium to get notified about new posts.</em></p><h3>Footnotes</h3><p>[1] Abu-Mostafa et. al, <a href="https://amzn.com/1600490069">Learning from Data</a> (2012) — This is a great book if you want to dive into the basics of learning theory. It is very well written and the authors have a talent for explaining complicated topics in simple and intuitive ways. Professor Abu-Mostafa also has <a href="https://work.caltech.edu/telecourse">a free online course</a> which follows along with the book and that I <em>highly</em> recommend.</p><p>[2] The entire space is made up of only 256 functions. Each input can either be a 0 or a 1, giving 2³ = 8 possible combinations of the inputs. Furthermore, for each combination of inputs, a function can only return 0 or 1. Therefore, there are 2⁸ = 256 possible functions.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8e9c18b08a3c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/is-learning-feasible-8e9c18b08a3c">Why is Machine Learning Feasible?</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[Extending the Python Syntax]]></title>
            <link>https://medium.com/better-programming/adding-sugar-to-the-python-syntax-e89248ce6e72?source=rss-6454fd7d51dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/e89248ce6e72</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[metaprogramming]]></category>
            <dc:creator><![CDATA[Eugen Hotaj]]></dc:creator>
            <pubDate>Wed, 17 Jul 2019 14:00:53 GMT</pubDate>
            <atom:updated>2020-03-27T04:44:23.791Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qbXYuHzKD0B8kTbRN0BEwA.jpeg" /><figcaption>(<a href="https://unsplash.com/photos/72vLY-QMd3w">source</a>)</figcaption></figure><h4>How to add sugar to the Python syntax with main wrappers</h4><p>I love Python. It’s an extremely powerful language that’s very simple to write and understand. It also has an extensive ecosystem of libraries that allow you to do pretty much anything you can think of (<a href="https://xkcd.com/353/">even fly</a>). Recently, it has become the lingua franca of Data Science and Machine Learning. I use it constantly in my day job, so I’d say I’m fairly proficient at it (I do have Python readability at Google after all 😏¹).</p><p>However, Python is not perfect. I’ve recently started learning Lisp in my free time.² While learning, I stumbled across what I think is a very cool (but minor) feature of Lisp. When defining functions, Lisp allows you to use previous arguments as default values.</p><p>For example, suppose you’re writing a make_rectangle function which takes as input the x, y coordinates of the top-left corner, width, and height and returns the x, y coordinates of the 4 corners of the rectangle. We can do this pretty easily in Python:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/373214f9dc69396fe013cb85990b711e/href">https://medium.com/media/373214f9dc69396fe013cb85990b711e/href</a></iframe><p>Now suppose that we want the function to return squares if it’s only passed the width argument. If you never programmed before, you might expect that a reasonable thing to is to set height=width, like so:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ae7e656c31442b62ced48c1ed07c5560/href">https://medium.com/media/ae7e656c31442b62ced48c1ed07c5560/href</a></iframe><p>Unfortunately, it’s not valid Python. If you try to run it, you’ll get an error:</p><pre>NameError: name &#39;width&#39; is not defined.</pre><p>Personally, I feel that this is a failing of the language. Sure, it’s pretty easy to work around the syntax and get a similar behavior:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d822eac20fa120f50e9e4659306eaf57/href">https://medium.com/media/d822eac20fa120f50e9e4659306eaf57/href</a></iframe><p>But that pisses me off! The language should do what I want, not the other way around. Instead of bending to the will of Python, I’ve created a __main__ wrapper that lets me write the code I want.</p><p>As always, full working code is available <a href="https://github.com/EugenHotaj/python-meta">on my GitHub</a>.</p><h3><em>Main Wrappers</em></h3><p>A __main__ wrapper is a Python program which wraps the __main__ function of another Python program. The wrapper can run whatever code it wants before calling through to the main program. It turns out that a lot of tools are written this way, such as <a href="https://docs.python.org/3/library/pdb.html">pdb</a>, <a href="https://docs.python.org/2/library/profile.html#module-profile">profile</a>, etc. If you’re interested in all the details, David Beazley has an interesting talk on the topic [1].</p><p>Since the wrapper runs before the main program, it’s possible for it to modify the code of the main program before executing it. This means that we can use the __main__ wrapper to transform code like improved_make_rectangle.py into valid Python like valid_make_rectangle.py. This way we can write in the more pleasant syntax while still having it execute correctly by the Python interpreter.</p><h4>Discourse On Method</h4><p><em>(A quick tangent on other possible approaches; feel free to skip.)</em></p><p>I thought a lot about how to add this functionality without the wrapper, perhaps through function decorators, context managers, etc. However, I came to realize that it’s likely impossible since improved_make_rectangle.py is not valid Python.</p><p>Another avenue I thought about exploring was to modify the Python interpreter itself. I didn’t go with this approach for primarily two reasons:</p><ol><li>It sounds a lot more tedious to pull off since you’d have to modify the underlying C code.</li><li>It’s a less portable because it involves forking the Python interpreter. Anyone who might want to use the new syntax can only do so via the forked interpreter. Conversely, the __main__ wrapper is just regular Python.</li></ol><p>If you know any better ways to implement this functionality, please let me know in the comments. I’m very interested in finding out!</p><h3>Extending the Python Syntax</h3><p>The first thing we need to do is create a wrapper which is able to run other programs. As demonstrated in [1], this is fairly simple:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/eea5a6381c533c83471178c8724af84d/href">https://medium.com/media/eea5a6381c533c83471178c8724af84d/href</a></iframe><p>Most of the code just makes sure the Python environment is set up correctly when we execute the main program in line 17. The interesting part happens in lines 7–10: here we read the main program code, preprocess (i.e. rewrite) it to be valid Python, and compile it to be executed. We can now wrap any Python program by running it like this:</p><pre>python3 -m main_wrapper some_random_program.py</pre><p>Of course, the preprocess function is up to us to write. What we want to do is go through every line of code in the main program and find all function headers, i.e. all lines that start with def (ignoring any leading whitespace).³ Then for each header we find, we want to see if any of it’s arguments reference previously defined ones. If so we want to transform them into the make_rectangle_valid.py equivalent by setting them to None and for each one adding argument = argument or prev_argument to the top of the function definition. Here’s how this looks in code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/893eaf2a0afeeba7e4797056f6931140/href">https://medium.com/media/893eaf2a0afeeba7e4797056f6931140/href</a></iframe><p>We’re making a lot of implicit assumptions that would need to be ironed out in a more robust implementation. For example, we’re assuming that the main program’s code uses 4 white space characters for each indentation level (line 9) and that the overall code follows the PEP 8 style guide (otherwise line 12 would fail if kwargs had whitespace around the =, such as some_arg = 12). While we could relax these assumptions with some effort, what we have here is a good first step.</p><p>Finally, you may have noticed the cryptic call to the _buid_arg_to_prev_arg function on line 10. This function is responsible for parsing a function header and extracting all arguments which reference previously defined arguments. To do this, it first removes everything that’s not a function argument, such as white space, parentheses, the def statement, etc. Then, for each argument, it checks if it references any previously defined argument, and if so adds it to a dictionary. Finally, the dictionary is returned. This translates into the following code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/431e4fa79ebf9e2d568c69a9f4b3a31f/href">https://medium.com/media/431e4fa79ebf9e2d568c69a9f4b3a31f/href</a></iframe><p>We now have all the components in place to make our wrapper work. Here is the improved_make_rectangle.py code again with a simple __main__ method to sanity check the implementation for both rectangles and squares:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6867f801296368bc59ad9f9bdaee77ac/href">https://medium.com/media/6867f801296368bc59ad9f9bdaee77ac/href</a></iframe><p>As before, running without the wrapper raises a NameError:</p><pre>$ python3 wrapper_test.py<br>Traceback (most recent call last):<br>  File &quot;wrapper_test.py&quot;, line 1, in &lt;module&gt;<br>    def make_rectangle(x, y, width, height=width):<br>NameError: name &#39;width&#39; is not defined</pre><p>However, when we run with the wrapper, the messages correctly print out in the terminal:</p><pre>$ python3 -m wrap_main wrapper_test.py<br>Rectangle: ((0, 0), (100, 0), (100, 200), (0, 200))<br>Square: ((0, 0), (100, 0), (100, 100), (0, 100))</pre><h3>Conclusion</h3><p>In this article we added some extra syntactic sugar to Python by writing a __main__ wrapper. As it currently stands, the wrapper is pretty brittle and would fail spectacularly if you tried to use it in real world situations. Also the amount of code we had to write to get rid of a few extra lines is pretty large. So, all things considered, the wrapper is probably not worth it. However, __main__ wrappers themselves are a general meta-programming technique which allow you to extend Python to do very cool and interesting things. If nothing else, they’re fun to write 🙂.</p><p>Thanks for reading!</p><p>Eugen Hotaj<br>July 15, 2019</p><p>P.S. For the sake of brevity, I’ve skipped over some minor things in this article. If you want the full details, please check out the full, working code <a href="https://github.com/EugenHotaj/python-meta">on my GitHub</a>.</p><p>If you liked this article, then follow me to get notified about new posts!</p><h3>Footnotes</h3><p>¹ Of all things to brag about, having Python readability at Google is probably the dumbest. In case it wasn’t obvious, I’m only kidding.</p><p>² If the gods <a href="https://xkcd.com/224/">wrought the universe in Lisp</a>, I want to find out what all the fuss is about. If you’re also curious, <a href="http://www.gigamonkeys.com/book/">Practical Common Lisp</a> is a great, free book.</p><p>³ It’s worth pointing out that finding function definitions this way is very brittle. While this is OK for quick prototyping, something more robust would need to follow the <a href="https://docs.python.org/3/reference/compound_stmts.html#function-definitions">Python reference</a>.</p><h3>References</h3><p>[1] D. Beazley, <a href="https://speakerdeck.com/dabeaz/modules-and-packages-live-and-let-die?slide=70">Modules and Packages: Live and Let Die!</a>, PyCon (2015).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e89248ce6e72" width="1" height="1" alt=""><hr><p><a href="https://medium.com/better-programming/adding-sugar-to-the-python-syntax-e89248ce6e72">Extending the Python Syntax</a> was originally published in <a href="https://betterprogramming.pub/">Better Programming</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Generating Beatles Lyrics with Machine Learning]]></title>
            <link>https://medium.com/data-science/generating-beatles-lyrics-with-machine-learning-1355635d5c4e?source=rss-6454fd7d51dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/1355635d5c4e</guid>
            <category><![CDATA[towards-data-science]]></category>
            <category><![CDATA[beatles]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[gpt-2]]></category>
            <category><![CDATA[nlp]]></category>
            <dc:creator><![CDATA[Eugen Hotaj]]></dc:creator>
            <pubDate>Sun, 30 Jun 2019 23:48:16 GMT</pubDate>
            <atom:updated>2020-03-27T04:42:40.387Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*w5Oyn62pTisTUX4uQPcFzw.jpeg" /><figcaption>(<a href="https://www.rollingstone.com/music/music-album-reviews/review-the-beatles-sgt-peppers-anniversary-editions-reveal-wonders-121092/">source</a>)</figcaption></figure><h4>A high level primer on language models and OpenAI’s GPT-2</h4><p>The Beatles were a huge cultural phenomenon. Their timeless music still resonates with people today, both young and old. Personally, I’m a big fan. In my humble opinion, they are the greatest band to have ever lived¹. Their songs are full of interesting lyrics and deep ideas. Take these bars for example:</p><blockquote>When you’ve seen beyond yourself <br>Then you may find peace of mind is waiting there²</blockquote><p>Powerful stuff. However, the thing that made the Beatles great was their versatility. Some of their songs are deep and thoughtful while others are fun and lighthearted. Unsurprisingly, the biggest theme that weaves throughout their lyrics is <em>love</em>. Here is one such verse:</p><blockquote>My sweet little darling can’t you see,<br>how wonderful it is when you’re mine.<br>If only I could be your lover forever,<br>I can never get my heart, I can’t get my mind.</blockquote><p>Actually, these lyrics weren’t written by any Beatles you may know. Not by Lennon, or McCartney, or Harrison, or even, God forbid, Ringo Starr (just kidding, Ringo’s alright). They were actually generated by a Machine Learning model, namely OpenAI’s GPT-2 [1]. Although this uses their smallest model, the results are quite astonishing.</p><p>But before we get too ahead of ourselves, let’s take a step back and look at how this all works. As always, full working code is <a href="https://github.com/EugenHotaj/beatles">available on my Github</a>.</p><h3>Language Modeling</h3><p>Language models try to learn the structure of a language (e.g. English or Beatles’ lyrics). They are generative models that are trained using supervised learning. Like other supervised learning tasks, language models try to predict a label given some features. However, unlike most supervised learning tasks, there are no explicit labels, rather the language itself acts both features and labels.</p><p>At a high level, what a language model tries to do is predict the next word given a sequence of previous ones. For example, a good language model might predict that <em>“milk”</em> is the logical conclusion to the phrase <em>“to buy a gallon of ____.”</em></p><p>By trying to guess which word comes next, what we’re really doing is learning a probability distribution over the vocabulary conditioned on the words we’ve seen so far. That is, we want to learn</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/238/1*canPje2h8hit_SehEKsKSw.png" /></figure><p>where w_i are the words in our vocabulary.</p><p>Because we’re explicitly modeling this distribution we can do some cool things with it, such as use it to generate words we haven’t seen before. The way we can to this is by repeatedly sampling the next word from this distribution, then using that as the conditional when we sample the next-next word, and so on. To make it concrete, let’s see what this might look like in Python. If we had a model object with a sample method, then we can generate new samples by doing something like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/af7cbcd2dca76b150e4c6d5afbfb55cc/href">https://medium.com/media/af7cbcd2dca76b150e4c6d5afbfb55cc/href</a></iframe><p>Of course I’m skipping over a few details but hopefully these will become clearer as we go on. For now, let’s consider the world’s simplest language model, the unigram.</p><p>The unigram model ignores any conditioning and simply chooses the next word randomly from the training data. What this amounts to is throwing our training data into a blender and spilling out the contents after a 10 minute blend on high. Needles to say, we’re not going to be generating anything that resembles English (unless of course we had a trillion monkeys with a trillion blenders, or was it <a href="https://en.wikipedia.org/wiki/Infinite_monkey_theorem">typewriters</a>).</p><h3>The Bigram Model</h3><p>A step above the unigram model is the bigram model. As you might have guessed from the name, the bigram model learns a distribution that is conditioned on <em>only</em> the previous word, i.e.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/111/1*6SLpkVSF5W9WJQrEjyDBZQ.png" /></figure><p>Being that it’s so simple, the bigram model is easy to implement in Python, and will give us a deeper understanding of how language models work.</p><h4>Collecting data</h4><p>Before we get to the implementation, we first need some data. Our ultimate goal is to generate songs that would have made the Beatles proud, so let’s start by harvesting all their known lyrics.</p><p>I found <a href="http://toti.eu.com/beatles/index.asp">this website</a> which catalogues the lyrics for every song they ever released. It also has a helpful index page with links to the individual songs which we can use to scrape the site. I wrote a <a href="https://github.com/EugenHotaj/beatles/blob/master/scraper.py">simple script</a> to iterate over each link on the page, parse its HTML to extract the lyrics, and dump the lyrics to a file, one song per line. If you plan on following along, or just want the Beatles’ lyrics yourself, I highly recommend using it since scraping HTML is pretty tedious and annoying, even with tools like <a href="https://www.crummy.com/software/BeautifulSoup/">Beautiful Soup</a>.</p><p>Once we have the data in a nice, clean format, the rest is easy. But don’t just take my word for it, take it from this chart:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*3VMAtWKEx71I8nf2o_ffTA.jpeg" /><figcaption>Data cleaning and organizing accounts for the biggest chunk of data science projects (<a href="https://www.forbes.com/sites/gilpress/2016/03/23/data-preparation-most-time-consuming-least-enjoyable-data-science-task-survey-says/#2b97379b6f63">source</a>).</figcaption></figure><h4>Building the model</h4><p>As mentioned above, the bigram model just samples the next word conditioned on the previous one. One simple way we can do this is to keep track of which words follow the current one and with what frequency. That is, we keep a dictionary for each word current_word in our training data, then every time we see a next_word, we update current_word[next_word] += 1. Then, to generate words we simply look up all the words and counts in the current_word dictionary and sample a word with probability proportional to its count. Here’s a sketch³ of what the full model would look like in Python:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/77cf60ded88da043082a4b9b89dbb25c/href">https://medium.com/media/77cf60ded88da043082a4b9b89dbb25c/href</a></iframe><p>One last thing to note is that we probably want to preprocess the lyrics by adding some special tokens to denote the starts/ends of lines and songs. This is to force our model to maintain some of the song structure when generating new lyrics, otherwise the model will just spit out large blobs of text with no end. In my code I use XXSL, XXEL, XXSS, and XXES to denote start line, end line, start song, and end song respectively.</p><p>Finally, to generate songs, we can start with the XXSS token and keep calling model.predict() until we hit an XXES token.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1b9ba3f663f3f69ae3791b726ad51687/href">https://medium.com/media/1b9ba3f663f3f69ae3791b726ad51687/href</a></iframe><p>In theory, once the loop stops, we will have generated a never-before-seen Beatle’s song. But is it any good?</p><h4>A never-before-seen Beatles’ song</h4><p>Here’s a small snippet of one of the songs the bigram model generates:</p><blockquote>She’s so I love her heart.<br>Well they are; they said I’m so many,<br>She no surprise<br>When you’re mine<br>Sad and the Amsterdam Hilton<br>they make my way,<br>Yes I wait a boy been born with a rich man,<br>all share</blockquote><p>The generated samples sound like the ramblings of a madman and only make sense if we get extremely lucky.</p><p>We can keep extending the bigram model to take into account the previous two words. This is known as a trigram model. You may find that the trigram model actually produces better sounding lyrics. This is because there’s less three word combinations so the model has less choices at each step, and at some steps it only has one choice. In general, we can create an arbitrary <em>n-gram</em> model by considering the previous <em>n</em> words. When <em>n</em> is equal to the length of a full song, you may find that the model is perfect at generating Beatles’ songs. Unfortunately, the songs it generates already exist.</p><h4>Towards a better model</h4><p>One of the most glaring issues of the bigram model is that it will only use the words and phrases it has seen in the training data. While we want to generate lyrics which sound like they were written by the Beatles’, we don’t want constrain ourselves to only the words they used. For example, if the word “parade” was never used by the Beatles, then the bigram model will not generate any songs about “parades”. Of course, since we’re training only on the Beatles’ lyrics, we can’t possibly expect our model to use words it’s never seen. What we need is to train on enormous corpora, such as <a href="https://www.wikipedia.org/">Wikipedia</a> or <a href="https://www.reddit.com/">Reddit</a>.</p><p>However, even if we trained on all of Wikipedia and saw every single word in the English language, our bigram model would still be way too rigid. For example, take the phrase “tall man”. Everyone with a basic grasp on the English language would recognize that “tall” is simply a modifier of “man” and not tied to it. Instead “tall” could be used to modify countless other things, such as “woman”, “boy”, “building”, “giraffe”, etc. Our bigram model, however, can’t learn this and instead must see any use of “tall” at least once before it can use it. So if the model only ever saw “tall man”, “tall boy”, “tall woman”, but not “tall girl”, as far as it’s concerned, the phrase “tall girl” doesn’t even exist.</p><p>Therefore, what we want is a model which has a much richer vocabulary and a deeper understanding of the relationships between the words in the vocabulary. Luckily for us, clever researchers have already invented such powerful models and we can use them to generate much better songs.</p><h3>The GPT-2 Model</h3><p>OpenAI’s GPT-2 model [1] recently made headlines for being “too dangerous to release.” The model generated such convincing text that the authors believed it might be used for malicious purposes⁴. Instead they released two smaller versions for people to play around and experiment with. We’ll use the smallest of the two to generate our Beatles’ lyrics.</p><p>GPT-2 is a <a href="https://ai.googleblog.com/2017/08/transformer-novel-neural-network.html">transformer</a> based model which was trained on huge amounts of Reddit data for hundreds of GPU hours. During its training, it was able to learn a very good model of the English language (or at least the version of English used on Reddit). This means that it’s able to understand things like “tall” can apply to humans or buildings or giraffes. Also, because it trained on a huge portion of Reddit, it’s likely that it’s seen 99.9% of words and phrases in the English language. This is great news for us since this is exactly what we were looking for: an expansive vocabulary and a deep understanding of how to use that vocabulary.</p><p>However, if we turned on the model and asked it to generate something, it’s extremely unlikely that it would come up with resembling Beatles’ lyrics (even if <a href="https://www.reddit.com/r/beatles/">r/beatles</a> exists). This is because the model doesn’t know that what we care about is generating Beatles lyrics, after all this wasn’t what it was trained to do. Instead we need to nudge the model towards doing what we want it to do. One way we can do this is via transfer learning.</p><h4>Transfer Learning</h4><p>Transfer learning is the idea that we can leverage information we’ve learned by doing one thing and apply it to solve a related thing. For example, when you started reading this article, you didn’t have to relearn what words are, which words follow which other words, or how they fit together to form sentences. Imagine how tedious that would be. Instead you leveraged all those hours spent reading AP Literature books to understand what I’m talking about now (I guess <a href="https://en.wikipedia.org/wiki/Adventures_of_Huckleberry_Finn">Huck Fin</a> came in handy after all).</p><p>In a similar fashion, we can leverage the knowledge GPT-2 has already learned through it’s hundreds of hours of reading Reddit posts and transfer it to our task of generating Beatles’ lyrics. The high level idea is to take the pre-trained model and keep training it for bit longer. However, instead of Reddit posts, we’ll use the scraped Beatles’ lyrics <em>only</em>. This will heavily bias the model towards generating Beatles-like songs.</p><p>I’ll skip exactly how to do this here since it would take another post of similar length to explain everything. Instead, if you’re interested in the exact details, I’ll refer you to [2]. It’s a great blog post with step-by-step instructions of how to transfer the GPT-2 model to any language task you care about. It’s also what I followed to get the results shown here.</p><h4>The new Beatles</h4><p>Like all good deep learning results, the lyrics I posted in the introduction were heavily cherry picked. The generated songs are not all as good and their quality depends on where in the fine-tuning phase you are. Here’s what you might get after fine-tuning for ~100 mini-batches, when the model is still heavily underfitting the training data:</p><blockquote>Ev’ry I Love You<br>Lennon &amp; McCartney<br>Ev’ry I will always be<br>Ev’ry you love me.<br>Ev’ry you love me,<br>Ev’ry you love me too.<br>Ev’ry I will always be</blockquote><p>And it just goes on like that for another 10–15 lines. Still better than <a href="https://en.wikipedia.org/wiki/Lil_Pump">Lil’ Pump</a> at least.</p><p>Joking aside, what’s very interesting to me is the fist two lines. In the training data, each song starts out with the title on the first line, the writer(s) on the second, and the actual lyrics in the following lines. Even at this early stage the model has managed to learn the structure of our data: the first and second lines are special; in the second line there’s only a few combinations of words that could possibly appear, with Lennon &amp; McCartney being the most likely.</p><p>If we fine-tune for ~350 mini-batches, the model starts generating much more believable lyrics, such as the one in the intro, or this one:</p><blockquote>Woman in Black<br>Lennon &amp; McCartney<br>I’d make a scene<br>If you don’t want me to appear<br>You might as well leave me alone.<br>I’m near death and I’m in love</blockquote><p>Not perfect, but not bad. Finally, this is what happens if we keep fine-tuning for way too long (~2800 min-batches):</p><blockquote>Get Back (Get Back)<br>Lennon &amp; McCartney<br>Yellow Submarine<br>Lennon &amp; McCartney<br>On a Saturday night as the sun shines down on me<br>The sun is out, the sails are clear<br>The sun is in, the sails are clear<br>Oooh — Hey</blockquote><p>The model starts overfitting and the generated samples are things that are very likely to be present in the training data, such as the repeated “Lennon &amp; McCartney” lines, “Yellow Submarine,” etc. I found that fine-tuning for ~300–500 steps produced the best lyrics.</p><h3>Conclusion</h3><p>Hopefully you now have a much better idea of how language models work and how we can leverage state-of-the-art models to greatly improve downstream tasks.</p><p>That being said, there’s so much left to explore with the GPT-2 model. The samples I generated used the default, (probably) suboptimal hyperparameters. It would be interesting to see how much better the generated lyrics can be if more time was spent getting the fine-tuning right. I also only used the smallest of the released models since I was using my laptop to train. I’m confident the bigger model would produce even more spectacular results. Finally, OpenAI recently released <a href="https://openai.com/blog/musenet/">MuseNet</a> which is capable of generating pretty realistic sounding music. How amazing would it be put GPT-2 and MuseNet together (they’re basically the same model) and generate both the lyrics and the accompanying music? If I had more time, money, or any idea of what I’m doing, I’d love to generate a full fledged song using Machine Learning, then have someone with actual talent perform it.</p><p>Thanks for reading!</p><p>Eugen Hotaj,<br>June 30, 2019</p><p>P.S. If you liked this article, then follow me to get notified about new posts! As always, all the code and data is available on <a href="https://github.com/EugenHotaj/beatles">my GitHub</a>.</p><h3>Footnotes</h3><p>¹ Though I think the best solo musician would have to be another ’60s legend, <a href="https://en.wikipedia.org/wiki/Bob_Dylan">Bob Dylan</a>. His single, <a href="https://www.youtube.com/watch?v=IwOfCgkyEj0">Like a Rolling Stone</a>, may be the best song ever written, and that’s <a href="https://www.rollingstone.com/music/music-lists/500-greatest-songs-of-all-time-151127/bob-dylan-like-a-rolling-stone-2-54028/">not just my opinion</a>.</p><p>² From <a href="http://go/wiki/Within_You_Without_You"><em>Within You Without You</em></a><em>, </em>my favorite Beatles’ song from my favorite Beatles’ album. It’s so weird, yet so good.</p><p>³ For the sake of brevity I’ve skipped over a few minor details. You can all the gory details <a href="https://github.com/EugenHotaj/beatles">on my GitHub</a>.</p><p>⁴ Some people believe that this was just a huge publicity stunt, but that’s neither here nor there.</p><h3>References</h3><p>[1] A. Radford et al., <a href="https://d4mucfpksywv.cloudfront.net/better-language-models/language_models_are_unsupervised_multitask_learners.pdf">Language Models are Unsupervised Multitask Learners</a> (2019)</p><p>[2] S. Todorov, <a href="https://svilentodorov.xyz/blog/gpt-finetune">Generating Fake Conversations by fine-tuning OpenAI’s GPT-2 on data from Facebook Messenger</a> (2019)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1355635d5c4e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/generating-beatles-lyrics-with-machine-learning-1355635d5c4e">Generating Beatles Lyrics with Machine Learning</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[Making Rockets Hover with PID Controllers]]></title>
            <link>https://eugenhotaj.medium.com/controlling-rockets-with-theory-b8bf3d8b263f?source=rss-6454fd7d51dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/b8bf3d8b263f</guid>
            <category><![CDATA[science]]></category>
            <category><![CDATA[control-theory]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[space]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Eugen Hotaj]]></dc:creator>
            <pubDate>Wed, 08 May 2019 03:19:32 GMT</pubDate>
            <atom:updated>2020-03-27T04:41:28.009Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VkFa9OIaHKgt6ceQKR0ChQ.jpeg" /><figcaption><a href="https://www.pexels.com/photo/white-smoke-of-a-space-craft-73872/">Source</a></figcaption></figure><h4>It’s not rocket science, it’s control theory</h4><p>I spend way too much time on YouTube… probably much more than I’d like to admit. For all of its shortcomings, YouTube has a lot of very interesting content from dedicated and passionate creators. Every so often I’ll run across a video that sparks an idea for something I want to try. One such video I recently came across was this SpaceX propulsion test of their Dragon 2 spacecraft.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F07Pm8ZY0XJI%3Ffeature%3Doembed&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D07Pm8ZY0XJI&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F07Pm8ZY0XJI%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/8b6ada66d04f55b73c440a308d57d8b1/href">https://medium.com/media/8b6ada66d04f55b73c440a308d57d8b1/href</a></iframe><p>What stands out to me in particular about this video is that the spacecraft uses its boosters to perfectly hover a few feet off the ground. At first glance, this might not seem like a big deal. However, to achieve this, the craft must fire its thrusters hard enough to accelerate towards the target while slowly reducing the thrust force until it exactly counteracts gravity and the rocket hovers in midair [1].</p><p>The <a href="https://en.wikipedia.org/wiki/Tsiolkovsky_rocket_equation">rocket equation</a> has been known for quite some time, so it’s possible to calculate the exact thrust schedule needed to make the rocket hover. However, it’s much easier (and more fun!) to let the computer do all the heavy lifting for us. Instead of doing the math by hand, we’ll use <a href="https://en.wikipedia.org/wiki/Control_theory">Control Theory</a> to make the rocket hover.</p><p>To get a feel for things, we’ll create our own basic rocket simulation and implement a couple of controllers. Unlike <a href="https://medium.com/@eugenhotaj/knn-for-pwned-passwords-e4895f66b836">my last post</a>, this one requires a lot more code, so I’ll only give a brief sketch of the most important parts of the implementation [2]. If you want something that actually works, or you’re curious what the final product looks like, you can find everything on <a href="https://github.com/EugenHotaj/rockets">my GitHub</a>. As always, pull requests welcome :).</p><h3>Playing God — Simulating Physics</h3><p>Before we can control the rocket we need to first build the rocket. To do this, we’ll implement a <em>very</em> idealized physics simulation. We’ll treat our rocket as a particle with only the forces of gravity and thrust acting on it. Since there will be no lateral forces we can conveniently skip calculating any angular dynamics. We’ll also assume that the rocket has infinite fuel so we don’t have to deal with things like changing mass or fuel slosh.</p><p>To compute the instantaneous rocket dynamics, we first discretize time into intervals of size <em>dt </em>and take into account any forces acting on the rocket at the end of each interval. Once we’ve resolved the forces, we can update the acceleration, velocity, and position of the rocket.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/76dc06eab6f32ef522e2a080bc1f119d/href">https://medium.com/media/76dc06eab6f32ef522e2a080bc1f119d/href</a></iframe><p>There are two things to note here:</p><ol><li>Our rocket lives in a flat world so we’ll use 2D numpy arrays as 2D vectors for our simulation.</li><li>Annoyingly, <a href="http://www.e-cartouche.ch/content_reg/cartouche/graphics/en/html/Screen_learningObject3.html">screen coordinate systems</a> set the origin <em>(0, 0) </em>to be the top left of the screen, so increasing <em>y</em> moves things <em>down </em>not up. This means that in our world gravity is<em> 9.8 m/s² </em>and not <em>-9.8 m/s².</em></li></ol><p>Now that we have a rocket, the only reasonable thing to do is set the thrust to 100% and let that baby rip.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*pDrI8ntLX5P7bDP02fTueA.gif" /><figcaption>Full speed ahead.</figcaption></figure><p>And just like that we’re off to the moon. It’s interesting to note that even though this is a very simple simulation with crude programmer graphics, the rocket taking off actually looks <a href="https://www.youtube.com/watch?v=lS9XcEEek48">kind of realistic</a>. Ok, maybe not <em>that</em> realistic.</p><h4>Aside: Integration</h4><p>If you don’t care that our simple physics system is slightly wrong, or simply hated Calc I in college, feel free to skip this section. However if, like me, <a href="https://en.wikipedia.org/wiki/Numerical_integration">Numerical Quadrature</a> really does it for you, then read on.</p><p>When you think about it, what we’re really doing in Rocket.update is integrating the acceleration and velocity over time. Actually, we’re using the <a href="https://en.wikipedia.org/wiki/Euler_method">Euler Method</a> to approximate the integrals with rectangles of width <em>dt. </em>Since the acceleration is constant, our velocity computation will be exact. However, because of this constant acceleration, the velocity increases linearly over time, so the position approximation will be incorrect. If we think about the curves traced out in the Cartesian plane, the acceleration curve forms a rectangle with the x-axis, while the velocity curve forms a triangle. Intuitively, we should able to exactly compute the rectangle’s area by smaller rectangles, but no matter how hard we try we cannot exactly compute the triangle’s area and will end up overestimating it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/956/1*3h6mszgQlZj79l26R7OxNg.png" /><figcaption>Left: We can exactly compute the acceleration integral by using small rectangles. Right: We cannot exactly compute the velocity integral using the same method.</figcaption></figure><p>To make this explicit, let’s see what the error is between our approximated position and the actual position, which we can figure out using the <a href="https://en.wikipedia.org/wiki/Kinematics_equations">kinematic equations</a>. Assume that the rocket has a constant acceleration of <em>5m/s² </em>and we use <em>dt=.5.</em> According to our approximation, after <em>5</em> seconds the rocket will be displaced by <em>68.75m,</em> while the kinematic equations give 62.5m, so our approximation error is <em>+6.25m</em>.</p><p>It’s possible to get better integral approximations by using more sophisticated methods like <a href="https://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods">Runge-Kutta</a>. That being said, <em>dt=.5</em> is unreasonably large. If instead we use something like <em>dt=1/60 (</em>which is what I’m using) we get an error of only <em>~.63m</em>. So while our simulation is wrong, it’s not <em>that </em>wrong. Of course, as <em>dt → 0, </em>our approximation will get closer and closer to the actual value.</p><h3>Control</h3><p>Getting a rocket to shoot off into space is cool and all, but wasn’t the point to make it hover? For that we’ll need some way to control the rocket, and what better way to do that with than with Control Theory. Control Theory is a deep and interesting field which I have neither the time, nor the expertise to explain. For now, we’ll use just enough to do some cool things with it.</p><h4>On-Off Control</h4><p>If we sat down and tried to come up with a quick solution, the immediate thing that comes to mind is to just hit the gas until we reach our target then slam on the breaks once we’re there. This is actually one of the simplest controllers possible called an <a href="https://en.wikipedia.org/wiki/Bang%E2%80%93bang_control">On-Off controller</a> (or Bang-Bang controller, which in my opinion sounds 100x cooler). Implementing it is extremely simple.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/711fd4411726dfb643dbd77137d954eb/href">https://medium.com/media/711fd4411726dfb643dbd77137d954eb/href</a></iframe><p>In Control Theory terms, what we’re trying to do is move a process towards a desired setpoint. We can do this by minimizing the error (i.e. difference) between the setpoint and the measured sate of the process, known as the process variable. To put things into our own terms, the setpoint is the height at which we want the rocket hover at and the process variable is simply the rocket’s vertical position.</p><p>Since the On-Off controller is binary, it returns either ∞ if the error is positive or -∞ if it’s negative. We can use this signal to set the rocket’s thrust, but we first have to squash it through a <a href="https://en.wikipedia.org/wiki/Sigmoid_function">sigmoid</a> (💁‍♂️🦋 “is this ML?” ) and turn it into a percentage which the rocket can use. We finally have all the components needed to run our simulation end-to-end.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a55b1940d8883b33fd9b6219349c184a/href">https://medium.com/media/a55b1940d8883b33fd9b6219349c184a/href</a></iframe><p>Now that we’ve imbued our rocket with some decision making abilities, let’s see how well it can hover.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*DmgJ2sBK6DeYOWgs9ZPhuA.gif" /><figcaption>The On-Off controller causes wild oscillations around the target.</figcaption></figure><p>Unfortunately, not too well. This is because we’re not taking into account the rocket’s inertia. When we cut off the thrust at the target point, the rocket will still have a high upwards velocity which causes it to keep going up for a while. Similarly, when the rocket’s coming down, its velocity due to gravity will be too high for the thrust force to immediately counteract.</p><p>What we need to do instead is to slowly decrease our acceleration to 0 as we get closer to the target. To do this, we have to thrust with just enough force to perfectly counterbalance gravity. Since the On-Off controller is binary, we can’t possibly do this [3], and we must instead use something more powerful. Enter the PID controller.</p><h4>PID Control</h4><p>The PID controller is more sophisticated as it keeps track of the process’ state over time and tries to account for the inertia issues discussed. It does this by adjusting the response via proportional, integral, and derivative control. Let’s take a look at how each component plays a role in our case:</p><ol><li>Proportional control scales the rocket’s thrust based on the magnitude of the error. This makes sense intuitively: if the error is large and negative (i.e. the rocket is way below the target) we want to hit the thrust as hard as possible. On the other hand, if we’re close to the target we want to apply just enough thrust to get to the target but not overshoot it.</li><li>Integral control is probably the least intuitive component to think about. It adjusts the rocket’s thrust based on the accumulated error over time which has the effect of driving the steady state error towards zero. For example, if the error keeps increasing over time, more thrust will be applied to counteract this. In my experiments, the integral component mattered the least in controlling the rocket hovering, so if you don’t understand exactly what it is, don’t worry, neither do I.</li><li>Lastly, derivative control accounts for the error’s rate of change over time. This is really the term that makes the whole system work as it’s responsible for annealing the acceleration towards zero as we approach the target. Like the proportional control, this also has a very intuitive interpretation: if the error is changing rapidly, the thrust must also change rapidly.</li></ol><p>It takes some thinking to fully wrap your head around the 3 different PID components. Fortunately, the implementation is pretty straightforward and is easily translated into code.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/66a64fb3ed9c860cad4a453dc220c564/href">https://medium.com/media/66a64fb3ed9c860cad4a453dc220c564/href</a></iframe><p>The <em>kp</em>, <em>ki</em>, and <em>kd </em>parameters are weighting constants applied to each of the 3 components. Because the proportional, integral, and derivative terms interact unintuitive ways, setting them appropriately is heavily task dependent and takes a bit of manual tuning. There are even methods which do this for you <a href="https://en.wikipedia.org/wiki/PID_controller#Overview_of_tuning_methods">automatically</a> [4].</p><p>When I was first implementing everything, I tried a bunch of different settings for the weights but nothing seemed to be working. The rocket would either wildly oscillate around the target, like the On-Off controller, or just shoot off into space, never returning again. After a while, I found that the integral constant was ridiculously high. A good rule of thumb, at least for our rocket situation, is to set the <em>ki</em> to be about 3–4 orders of magnitude smaller than <em>kp</em> and <em>kd</em>. In fact, starting out with <em>ki=0 </em>and<em> </em>kp=kd=1 will almost certainly give you good results. You can then play around with the parameters until the rocket trajectory looks good. After some tweaking I found that <em>kp=1.0</em>,<em> ki=.0001</em>, <em>kd=2.3 </em>work pretty well.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*dp8-2qn6Mr5G1AYr72u0sQ.gif" /><figcaption>Near optimal control with the PID controller.</figcaption></figure><p>That’s a pretty smooth hoverin’ rocket.</p><h3>Conclusion</h3><p>I first heard about PID control in the context of some Reinforcement Learning experiments I was running at work. With the recent extreme hype of Machine Learning and Deep Learning, these “classic” methods are easy to overlook, but as we saw, we can get extremely good results with very little effort. It seems the thousands of hours people invested into researching and perfecting these methods have not gone to waste.</p><p>That being said, a great next step would be to see if a Reinforcement Learning algorithm could learn to control the rocket to hover at the target. While I’m certain this is doable, I wonder how long you’d need to train for and how good the final results would be.</p><p>Thanks for reading! Check out <a href="https://github.com/EugenHotaj/rockets">the GitHub</a> for the full code.</p><p>Eugen Hotaj<br>May 7th, 2019</p><p>[1] For what it’s worth, the spacecraft seems to be suspended by cables in the exact target position, so all the craft must do is apply enough force to counteract gravity — a much simpler problem.</p><p>[2] The biggest chunk of code that I’m skipping over is the rendering code, since it’s pretty boring. Funny story, while I was writing all the code for this blog post, I ran into <a href="https://stackoverflow.com/questions/52718921/problems-getting-pygame-to-show-anything-but-a-blank-screen-on-macos-mojave">issues with PyGame on Mac</a>. After spending like 3–4 hours trying out different rendering frameworks (<a href="https://docs.python.org/3/library/tkinter.html">tkinter</a>, <a href="https://docs.python.org/3.3/library/turtle.html?highlight=turtle">turtle</a>, <a href="https://kivy.org/">kivy</a>, etc), I settled on <a href="https://mcsp.wartburg.edu/zelle/python/graphics.py">graphics.py</a>. It’s extremely simple, but turned out to have everything I needed.</p><p>[3] It’s possible to get even better results with the On-Off controller. For example, we can have a dead-band around the target so that the thrusters are turned off when the rocket is close to the target, or rapidly switched on/off to fake applying a certain thrust force. However, if we were to implement all of that, we’d find that what we’ve created is a rough approximation to the PID controller anyways.</p><p>[4] It should be possible to set learn these constants as well using ordinary least squares regression. It would be interesting to see how much easier or harder this is compared to the traditional methods and how the learned coefficients would differ.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b8bf3d8b263f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[kNN for Pwned Passwords]]></title>
            <link>https://eugenhotaj.medium.com/knn-for-pwned-passwords-e4895f66b836?source=rss-6454fd7d51dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/e4895f66b836</guid>
            <category><![CDATA[passwords]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[security]]></category>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[knn]]></category>
            <dc:creator><![CDATA[Eugen Hotaj]]></dc:creator>
            <pubDate>Mon, 08 Apr 2019 02:57:28 GMT</pubDate>
            <atom:updated>2020-03-27T04:38:59.205Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*36v1BuS1DRMIehQb6Hp9Tw.jpeg" /><figcaption><a href="https://unsplash.com/photos/IwybMCZouWY">https://unsplash.com/photos/IwybMCZouWY</a></figcaption></figure><h3>kNN for Stronger Passwords</h3><h4>How to build a smarter test for password strength</h4><p>I recently came across an extremely useful tool for checking the quality of your passwords, <a href="https://haveibeenpwned.com/Passwords">haveibeenpwned.com</a>. You type in a password and it automatically gets checked against a database of <strong>~500M leaked passwords</strong>. If any matches were found, you should p̶r̶o̶b̶a̶b̶l̶y̶ definitely change your password.</p><p>Let’s see what happens when we try <a href="https://xkcd.com/936">the classic <em>correcthorsebatterystaple</em></a><em>.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*u9ZQh7iG2qUH23j71IdtAQ.png" /></figure><p><strong>At least 114</strong> other people have used this and been pwned. Needless to say DO NOT USE it (I’ll patiently wait while you go change your password).</p><p>Having a tool like this is great. However, and somewhat unfortunately, only exact matches are returned. In a database of 500 million passwords, this may not be a huge deal since it’s very likely that any iteration of <em>password, p4assw0rd, paSSwOrD, </em>etc<em>,</em> will already be present. But for rarer passwords, this is not always the case. For example, let’s see what happens when we replace the first <em>o</em> with a <em>0 </em>in <em>c0rrecthorsebatterystaple</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*psVIHhNi_4hMYNW5p2Dtlg.png" /></figure><p>As you can see, no matches were found. So, perfectly safe, right? <a href="https://security.stackexchange.com/questions/139906/are-leet-passwords-easily-crackable/139908#139908">Not exactl</a>y. It turns out that most would-be password hackers are quite savvy to this tactic and it’s easy to break with a dictionary attack. Therefore, it would be great if haveibeenhacked.com also notified you if your password was <em>similar</em> to leaked ones<em>.</em></p><p>This is where <em>~~machine learning~~</em> comes in.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*ugR2g7Z2VWkIOSaV0bb8lg.png" /><figcaption><a href="https://blog.evjang.com/2018/11/memes.html">https://blog.evjang.com/2018/11/memes.html</a></figcaption></figure><p>Well, sort of… While we could build a super cool deep neural network with thousands of layers trained using some type of contrastive loss between good and bad passwords (and while this may or may not work), let’s start out with something simpler, like k-Nearest-Neighbors (kNNs). The system we’ll be creating takes a user provided password and checks if it is similar enough to any of the passwords in our database of leaked passwords. To determine similarity, we could use any kind of <a href="https://en.wikipedia.org/wiki/Metric_(mathematics)">distance metric</a>, and one which seems pretty suited to strings is the <a href="https://en.wikipedia.org/wiki/Edit_distance">edit distance</a> (or the Levenshtein distance if you’re trying to impress your friends).</p><p>I was actually surprised to find that none of the mainstream data science libraries (<a href="https://scikit-learn.org/stable/">sklearn</a>, <a href="http://www.numpy.org/">numpy</a>, <a href="https://www.scipy.org/">scipy</a>, etc) provide this out of the box. There may be a lot of reasons for this, and one of them might be that it’s not very computationally efficient (at least that’s my guess). In any case, we’ll implement it ourselves given that it’s relatively simple:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d14e85d6790a1dc38459fc8836a2f248/href">https://medium.com/media/d14e85d6790a1dc38459fc8836a2f248/href</a></iframe><p>This metric function is the meat of our system, the rest is just plumbing. If you’re never written kNN before, it’s probably the easiest machine learning algorithm to implement from scratch. In fact, since it is a non-parametric model, there isn&#39;t even any learning that takes place. All it does is take your test data, in our case the user provided password, and compares to every single “training” data point using the distance metric. If two data points are close enough<em> </em>in distance space, then we consider them to be neighbors. Here’s what this looks like in code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/854a3a0f8756aa12d541889b047d3aff/href">https://medium.com/media/854a3a0f8756aa12d541889b047d3aff/href</a></iframe><p>Looks good! As you might have noticed, we glossed over an important detail. If you look on <em>line 15 </em>in the code snippet above you’ll see we’re accessing a file called <em>passwords.txt</em>. This is the database of leaked passwords we use to test the user password against. There’s plenty of places to find leaked passwords online, and for the purpose of this article I’ve used <a href="http://go/gh/danielmiessler/SecLists/blob/master/Passwords/Common-Credentials/10-million-password-list-top-1000000.txt">this list</a> I found on GitHub.</p><p>All that’s left now is to wire everything together and we’ll have a simple, yet powerful, machine learning model for predicting password strength:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/622e0baed1bc840ea95f47e28830c986/href">https://medium.com/media/622e0baed1bc840ea95f47e28830c986/href</a></iframe><p>While this does the job, it turns out that users aren’t too keen on typing their passwords as plaintext on a terminal. Instead let’s use <a href="https://docs.python.org/2/library/getpass.html"><em>getpass</em></a> to ask the user for their password instead. Also, if we do find matching passwords, we may not want to display them on the terminal since it would be pretty easy to derive the user password from these matches. Instead, let’s make this option available only if the user requests it via the <em>show_matching</em> flag. Lastly, we’ll also add a knob to tune the matching threshold through a <em>max_distance</em> flag. Putting it all together we have:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/588b45481a931e4ecb5f1a28f3745761/href">https://medium.com/media/588b45481a931e4ecb5f1a28f3745761/href</a></iframe><p>Finally, let’s see how our system can handle the ultimate test of <em>c0rrecthorsebatterystaple</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ygXhTRvBkJ6a7rpGDwHDgQ.png" /><figcaption>Not so safe password.</figcaption></figure><p>Nice! We were able to warn the user that their password is weak without ever having seen an exact match.</p><h3>Conclusion</h3><p>With a few lines of code we built a smarter password strength prediction system. While this is a toy example, these ideas have potential applications in the real world. Imagine that when creating a new account, instead of vague heuristics about how many special characters your password has, it was tested for similarity against the millions of already known bad passwords. It could even be provided as a service for other apps to send requests to. Of course, if you’re serious about your online security, you should be using a <a href="https://en.wikipedia.org/wiki/Password_manager">password manager</a> anyways.</p><p>What we’ve built could be improved in several substantial ways, from the efficiency of the current system to the algorithm itself. Can you think of some improvements? If so, all the code can be found at my <a href="https://github.com/EugenHotaj/password-strength">GitHub</a>. Feel free to fork, steal, send PRs, or anything else you might want to do with it.</p><p>Finally, it should go without saying, but please DO NOT USE this system to check your <em>actual</em> passwords and use <a href="https://haveibeenpwned.com/Passwords">haveibeenpwned.com</a> instead.</p><p>Thanks for reading!</p><p>Eugen Hotaj,<br>April 7th, 2019</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e4895f66b836" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>