<?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 Sasha Kuznetsov on Medium]]></title>
        <description><![CDATA[Stories by Sasha Kuznetsov on Medium]]></description>
        <link>https://medium.com/@skzv?source=rss-5a3f4178ac1f------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*D8Pr9oC6q_hw3OwH8XNlWg.png</url>
            <title>Stories by Sasha Kuznetsov on Medium</title>
            <link>https://medium.com/@skzv?source=rss-5a3f4178ac1f------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 00:41:46 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@skzv/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[Bringing Colour and Life to Black and White Photos]]></title>
            <link>https://skzv.medium.com/bringing-colour-and-life-to-black-and-white-photos-9bf8b6dcb9a8?source=rss-5a3f4178ac1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/9bf8b6dcb9a8</guid>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[ai-in-ethics]]></category>
            <category><![CDATA[software]]></category>
            <category><![CDATA[history]]></category>
            <dc:creator><![CDATA[Sasha Kuznetsov]]></dc:creator>
            <pubDate>Tue, 15 Jun 2021 10:54:24 GMT</pubDate>
            <atom:updated>2021-06-15T10:54:24.467Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Machine learning allows us to colourise black and white photos with ease, but at what risk?</em></p><p><em>This article originally appeared in my personal blog at: </em><a href="https://blog.skz.dev/bringing-colour-and-life-to-black-and-white-photos"><em>https://blog.skz.dev/bringing-colour-and-life-to-black-and-white-photos</em></a></p><h3>A Different Universe</h3><p>Although colourised photos have technically existed for a century or more (<a href="https://www.loc.gov/pictures/related/?fi=name&amp;q=Prokudin-Gorski%20%2C%20Serge%20%20Mikha%20lovich%2C%201863-1944">Sergey Prokudin-Gorsky and Piotr Vedenisov, pioneers of colour photography, traveled around Imperial Russia documenting it in full colour</a>), the majority of the 20th century was documented in black and white. Even later in the century, much of the world did not have the luxury of colour film- my father was developing his own black and white photos into the 1980s-90s in Soviet Ukraine, and while Americans recorded full colour footage of the Vietnam War, the North’s perspective seems to be relegated to black and white photography.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/0*WRNaB0rJJCrviiz_.jpeg" /></figure><p><em>Young boy near the Sim River, a very early colour photograph from Imperial Russia. This was achieved by taking multiple pictures of the same scene with different colour filters. Courtesy of the Library of Congress.</em></p><p>Some will argue that black and white footage has its own special quality, and this may be true. But for me black and white footage disconnects me from the scene. It is clearly distant in time. We all associate black and white footage with the past, as the trope of black and white footage in cinematagrophy to refer to a memory shows. And as someone who experiences reality in full colour, black and white footage is difficult to experience. I struggle to put myself into the scene or the characters’ shoes, because in my mind it exists in a different, black and white universe. And yet when that footage is colourized, all of sudden everything appears more real, more believable, more tangible. It is then clear that whatever is depicted in the footage is of the same Earth and of the same people, people like you or me.</p><p>And so when my father recently began digitizing our collection of family photos — as physical photos deteriorate, or are otherwise at risk of being lost forever, along with the histories, memories, and legacies preserved by them — I felt an urge to colourise them, too — so that I could experience them to a fuller extent, and so that my family members could reminisce about their loved ones who are no longer around or remember the memories of their past and their youth.</p><h3>Colorizing Photos With AI</h3><p>Color restoration can be done manually and laboriously. Machine learned models offer a quick and inexpensive way to colourize photos, but they have their limitations, as we will discuss later in this post. I did not train my own model for this purpose. Others have already invested thousands of hours into developing and training models to do exactly that. I found an existing model that does a very good job.</p><p>I used the <a href="https://deepai.org/machine-learning-model/colorizer">Image Colorization API from DeepAi</a>. The production model deployed by DeepAi appears to be a form of the DeOldify model, which can be found at <a href="https://github.com/jantic/DeOldify">this github repo</a>.</p><p>I don’t think the DeepAi API allows you to adjust the model parameters, but you can if you run it yourself from the repo above or <a href="https://colab.research.google.com/github/jantic/DeOldify/blob/master/ImageColorizerColabStable.ipynb">a colab instance</a>. <a href="https://www.myheritage.com/incolor">MyHeritage</a> also offers this API as a service with tunable parameters.</p><p>What I did was create a quick script that enables bulk colorization of directories. It iterates over all the photos in a directory, sends them off to Image Colorization API from DeepAi, and downloads the result into a separate folder (ignoring images that have already been colourised). If that would be useful to you, just set your own DeepAi API key as an environment variable and run <a href="https://github.com/skzv/colorize-photos">this script</a>:</p><pre>export DL_API_KEY<strong>=</strong>&lt;your-deep-ai-key&gt;<br>python3 main.py /path/to/images</pre><h3>My Family Photos</h3><p>Here are some examples of the results on our family photos.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*qaYdj10eJYW1w0Pi.jpg" /><figcaption><em>My mother holding my brother in early ’90s Kherson, Ukraine. Courtesy of the Kuznetsov family.</em></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*vSdgQ07WR19bD_Aa.jpg" /><figcaption><em>Now in colour.</em></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/523/0*hCehBzz6QqHE_Fkv.jpg" /><figcaption><em>My grandmother, Allarkadina, likely sometime in the ’50s, on her way to university. She graduated from multiple institutes, specializing in electrical engineering, and had a successful career as a marine electrical engineer.</em></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/522/0*zgUJXcuYxsMOum5g.jpeg" /><figcaption><em>In colour.</em></figcaption></figure><blockquote><em>Looks so nice and alive.</em></blockquote><p>Those words from my father upon seeing the newly coloured photos made it all worth it.</p><h3>Photos From the Vietnam War</h3><p>A couple weeks after preparing a bulk colourising script for my family photos, a post titled <a href="https://news.ycombinator.com/item?id=27283624">“The Vietnam War from the North Vietnamese Side”</a> made it to the top of Hacker News. It seemed like a perfect opportunity to apply the script, and offer a new perspective on historical footage. Just as <a href="https://www.imdb.com/title/tt7905466/">“They Shall Not Grow Old”</a> made the horrors of WW1 living and real, so did I aim to make the characters and scenes from the perspective of North Vietnam.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*U8RwdsqE-uPjYoSI.jpeg" /><figcaption><em>Destruction of the jungle wrought by Agent Orange.</em></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*-xmuflcFniuzBPqt.jpg" /><figcaption><em>In colour.</em></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*xF1TOQ1qUVg8Lq31.jpeg" /><figcaption><em>Locals inspecting a downed American aircraft piloted by Lt. Stephen Owen Musselman. The pilot did not survive- war is hell.</em></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*hwchnU4aZv1BQeWq.jpg" /><figcaption><em>In colour.</em></figcaption></figure><p>All the original black and white images can be found <a href="https://rarehistoricalphotos.com/vietnam-war-images-from-vietnamese-photographers/">here</a>, with the colourised versions <a href="https://imgur.com/a/aJbpMjf">here</a>.</p><h3>Response on Hacker News</h3><p>My efforts were met with both praise</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/0*8IVqgm_SWT3u-HDs.png" /></figure><p>and contempt</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/546/0*rar77GGZfU6T0uSl.png" /><figcaption><em>Too bad about the [flagged] comment, because it raised an interesting point. The comment read something like ‘Please don’t do this.’</em></figcaption></figure><p>but most importantly, they generated a lot of very interesting discussions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/654/0*lNFB7TVvSK1mAvxM.png" /></figure><p>The full thread spurred by the colourised photos can be found <a href="https://news.ycombinator.com/item?id=27284795">here</a>.</p><h3>Limitations</h3><p>There were two aspects of the discussion that stood out to me. First, was the reminder of the limitations of AI.</p><p>For example, the model invoked on an old image of the Golden Gate under construction produces a white bridge. It’s not wholly inaccurate, to be fair- the bridge was indeed white early in its construction, but by the time the picture was taken, the bridge had already been covered in red primer (according to the source at the <a href="https://github.com/jantic/DeOldify">DeOldify repository</a>). So while the training data probably did contain the Golden Gate under construction, and the model could identify the same bridge under construction here, it could not discern the date and know that the bridge had already been primed with red at this point.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*bOFwoPlFOPaVbVX-.jpeg" /><figcaption><em>A white Golden Gate? It was white- but not when this picture was taken.</em></figcaption></figure><p>Some scenes are ambiguous. For example, based on the features in the following, the model cannot differentiate between the ground being field or asphalt, and incorrectly colours the asphalt green, where a human colouriser may get it right.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*8TzjTqTHKGrZiI1K.jpg" /><figcaption><em>The model can’t tell that the ground is asphalt and not grass.</em></figcaption></figure><p>Another interesting observation was that clothes seemed to often lack distinctive hues, textures, features, or context that made them accurately colourisable. The model tended to colour clothes purple — unless they had distinctive features or context. This is probably because when the model cannot make a good inference about the colour of the clothes, purple is a conservative bet, somewhere in the middle of the ambiguous colour space, that minimizes the training loss.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/796/0*zpZ9LxSaP7L93fTi.jpg" /><figcaption><em>I don’t think clothes in the past were as often as purple as this model makes it out to be.</em></figcaption></figure><p>Indeed, my father requested to correct the colour of some of the articles in the photos. Unfortunately I did not pursue this request, nor is it immediately obvious to me how I could. But as one commenter remarked, even when the colours are wrong, they still bring the images to life.</p><h3>Ethical Considerations</h3><p>Now that some of the limitations are clear, we are in a good position to consider the ethical ramifications of a colourising AI. This is was the second aspect of discussion that stood out to me. Ethics did not occur to me when I undertook the project, but some of the feedback I received spurred me to reflect, and for that I am thankful.</p><p>The main ethical consideration is truth. Similar to the controversy around deepfakes confusing us to what is true, artificial coloration can alter our experience of history. The AI makes choices about the colours of the past, which are not necessarily accurate. For example, if we keep and disseminate the white version of the Golden Gate, produced by such an AI, then the version of the bridge that is experienced by viewers is not historically accurate. Of course, neither is the black and white version. Perhaps the trouble is that viewers of the black and white image know that’s not what that past looked like, but viewers of the coloured image are easily tricked into believing that is history as it was.</p><p>Some may go as far as to say such retouching is rewriting of history, and indeed, sometimes it appears so. Take this recent example:</p><blockquote><em>Cambodia has called on US media group Vice to withdraw an article that featured newly-colourised photographs of victims of the Khmer Rouge, saying the images are an insult to the dead because some had been altered to add smiles.</em></blockquote><p><a href="https://www.aljazeera.com/news/2021/4/11/cambodia-condemns-vice-for-altered-khmer-rouge-images"><em>Source</em></a></p><p>Which is a very valid complaint. It appears the model was over-fit, likely trained on mostly smiling faces. It thus altered the faces of the victims to more closely resemble the training data- by smiling. It is a good example of the pitfalls of AI, especially where applied carelessly.</p><p><a href="https://www.myheritage.com/incolor">MyHeritage</a>, which offers a color restoration service based on the same DeOldify model I have used, attempts to make a compromise by watermarking all their retouched images. I think they make a compelling point:</p><blockquote><em>We differentiate colorized photos from those photographed originally in color using a special embossed palette symbol in the bottom left corner of colorized photos. While highly realistic, colorized photos have colors that are simulated by automatic algorithms and these colors may not be identical to the real-life colors of the original image. The palette icon appears on all colorized photos so that users can tell them apart from photos that have real colors. We hope that this responsible practice will be adopted by others who use photo colorization technology. Photos that have undergone color restoration do not have an icon because those colors are authentic.</em></blockquote><p>In my case, my family knew that I had artificially colourised our photos, and they could tell the colours were not wholly accurate. But even with the wrong colours, the photos, and people and scenes within them, were brought back to life. Just as when I was a high-school volunteer in a retirement home, and I was able to transport a senior resident to his childhood home in Dresden via Google Streetview, which he had not visited in 50 years, I was able to use AI to teleport our family to good times decades in the past. Technology is a tool, and I’m thankful I live in an age where magic like this is possible.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9bf8b6dcb9a8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Arbitrage as a Shortest-Path Problem]]></title>
            <link>https://medium.com/swlh/arbitrage-as-a-shortest-path-problem-d8d3ee18c080?source=rss-5a3f4178ac1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/d8d3ee18c080</guid>
            <category><![CDATA[algorithmic-trading]]></category>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[finance]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Sasha Kuznetsov]]></dc:creator>
            <pubDate>Tue, 05 Jan 2021 00:28:38 GMT</pubDate>
            <atom:updated>2021-06-01T23:35:31.110Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Who doesn’t like to make money?</em></p><p><em>This article originally appeared in my personal blog at: </em><a href="https://blog.skz.dev/arbitrage-as-a-shortest-path-problem"><em>https://blog.skz.dev/arbitrage-as-a-shortest-path-problem</em></a></p><p>And what if you could turn the problem of making money into the problem of finding the shortest-path? We can do that in at least one particular way: by exploiting arbitrage opportunities.</p><h3>What is arbitrage?</h3><p><em>Arbitrage</em> is the act of buying or selling things across different markets, or in different forms, to profit from differences in prices. And the people who engage in it? They’re known as <em>arbitrageurs — </em>a fancy title indeed.</p><p>Let’s start with an example. Say Paul, Peter, and Bob live in a village, where they barter carrots, potatoes, and lettuce. Bob trades potatoes for carrots, Peter trades lettuce for potatoes, and Paul trades lettuce for carrots.</p><p>Furthermore, Bob will trade 2 potatoes for a carrot, Peter will trade 1 lettuce for 2 potatoes, and Paul will trade 2 carrots for 1 lettuce. If we were to treat each individual as a market for their respective goods, what would the exchange rates look like?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*fxszEUIWJJjtjpdh3HVSeg.png" /><figcaption>Exchange rates for goods in our village.</figcaption></figure><p>Do you sense an opportunity?</p><p>Being the enterprising individual that you are, you may try to exploit it. Starting with 5 carrots, you approach Bob, and trade your 5 carrots for 10 potatoes, at the rate at which he is willing to trade.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/966/1*Ibmq6OzOlOaIQlfQ1rq5QQ.png" /></figure><p>Next, you approach Peter with your potatoes, knowing that he’ll trade you 5 lettuce for them. Then you approach Paul with your 5 lettuce, and he trades 10 carrots for your lettuce.</p><p>After a few smart trades, you’ve doubled your carrot wealth. You turned 5 carrots into 10, by exploiting an arbitrage opportunity.</p><p>Later on, the villagers may develop more sophisticated markets where Bob, Peter, and Paul aren’t the only traders. Instead this little village might develop a carrot/lettuce market, a lettuce/potato market, and a potato/carrot market, where the going rate for each trade will fluctuate based on what people are willing to trade.</p><p>But the arbitrage principle remains the same. And the opportunity can be exploited until the traders offering to exchange at those rates run out of carrots, lettuce, and potatoes to trade. The arbitrage opportunity is exploited until the market reaches an equilibrium.</p><h3><strong>Arbitrage in Modern Times</strong></h3><p>When you think of modern markets, you probably don’t think of trading carrots, potatoes, and lettuce. If you’re into forex, you’re more likely thinking of trading dollars, pounds, and yen. And in that case, we would be dealing with a dollar/pound market, a pound/yen market, and a yen/dollar market, with many traders acting on each market. From now on, let’s use those currencies as examples of things to trade, but keep in mind the principles can apply to all sorts of trade-able things.</p><p>Say at a given time, the exchange rates are as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/442/1*tGjV-lxJI-J1iS0zBdyPTg.png" /><figcaption>An example of currency market exchange rates.</figcaption></figure><p>If you learned anything from Bob, Peter, and Paul trading carrots, lettuce, and potatoes, you’d sense an opportunity here.</p><p>If you trade $1 for pounds, you’ll end up with £0.8. Trading that for yen, you’ll end up with ¥80. You take your yen to the yen/dollar exchange where you trade it back for dollars… but now you have $1.04!</p><p>But you have to act quickly, before another arbitrageur beats you to the punch. These opportunities only exist temporarily, until the liquidity is used up and the rates equalize.</p><p>The perceptive among you may notice that we haven’t considered exchange fees in our example. Of course, you’d have to take those into account to calculate if a profitable arbitrage opportunity actually exists.</p><h3><strong>Acting Quickly</strong></h3><p>Hopefully you have some intuition to understand why acting fast is paramount. Exchange rates fluctuate quickly, and there is only a limited amount of “thing” available at that exchange rate.</p><p>While we’ve worked with relatively simple examples here, arbitrage opportunities can span many trades, becoming incredibly complex. Our examples used 3 trades, but what if you needed 10? And in a network of 20 currencies with a market for each pair, how quickly could you find an opportunity?</p><p>Using a computer is an obvious answer. But we need an efficient algorithm, lest someone else beat us to the opportunity.</p><p>To achieve that, we can leverage a few clever insights in mathematics and computer science.</p><h3><strong>Markets as a Graph</strong></h3><p>Graphs are an incredibly important structure that has found its uses in numerous applications. Many social and natural structures can be modeled with graphs, and it turns out that markets are one of them.</p><p>In our case, let’s treat each currency as a node. Moving from node to node corresponds to trading one currency for another.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/448/1*bE5PW0sBh28xvo5Tqozatg.png" /><figcaption>Simplified graph — there should be a distinct edge in each direction.</figcaption></figure><p>So moving along an edge, between nodes, should transform the amount of currency by the exchange rate.</p><p>That means moving from the dollar node to the pound node corresponds to multiplying by 0.8 pounds/dollar. Let’s assign the exchange rate as the weight of each edge.</p><p>Note that the exchange rate in each direction will be <em>approximately</em> the reciprocal of each other. That means if the rate to convert pounds to dollars is 0.8 pounds/dollar, the rate in the other direction will be 1/(0.8 pounds/dollar) = 1.25 dollars/pound. The consequence for us is that we need to be careful to treat buying and selling on each market as distinct, directed edges, with different weights.</p><p>The reason that the exchange rates in both directions are only <em>approximately</em> reciprocal is due to small differences in the prices to buy and sell currencies, known as the buy-sell spread. For example, if at a given moment you can buy pounds at 0.8 pounds/dollar (the current price somebody will sell to you), but can sell dollars for pounds at 0.82 pounds/dollar (or 1.22 dollars/pound, and the current price somebody will buy from you), your graph model will look like this (excluding the other exchange rates for simplicity):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/451/1*N8LDQSbjj9DaFQwaigo9sw.png" /></figure><p>A series of trades can be modeled by moving along edges in this graph, and the result of the trades is computed by <strong><em>multiplying </em></strong>the edge weights as you move along them.</p><h3><strong>Seeing the Opportunity</strong></h3><p>Now that we have a working model, what are we looking for in our graph that corresponds to an arbitrage opportunity?</p><p>To determine whether a series of trades is profitable, we need a consistent metric of profitability. In other words, if we begin our series of trades in dollars, then we’ll need to end it in dollars, too. And by comparing the amount of dollars we ended up with to the amount we started with, we’ll know if it was profitable or not.</p><p>In our graph, that means that our series of trades must end at the same node from which it started. In our case, we started at the dollar node, and ended in the dollar node. In graph terminology, we call that a cycle. So we know we’re looking for some sort of cycle- but what kind of cycle makes it profitable?</p><p>Notice that if we multiply along the edges of a cycle, we transform the units of the effective exchange rate.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/498/1*9E0-DwJnDAhHlT0L-FBrRQ.png" /></figure><p>However, when we return to our starting node, the quantity becomes unit-less. It transforms from a rate of exchange, to a ratio of return! Traversing a cycle on our graph and computing the product of exchange rates along the way corresponds to calculating the ratio of return we would get after completing the series of trades.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xvtbdLBhh-Zqnx9Sd7_bfA.png" /></figure><p>If the market is perfectly efficient, our return ratio, <em>abc,</em> will be 1, because the exchange rates have equalized. If the product of weights is greater than 1, say 1.02, then our arbitrage opportunity would have made us a 2% return.</p><p>Therefore, generalizing to an arbitrary number of trades, an arbitrage opportunity corresponds to the following inequality:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*bZUpo5CWhOpDjxQzCw0ZyA.png" /></figure><p>where <em>e_i</em> corresponds to the <em>i</em>’th exchange rate, for each trade <em>i</em>, over <em>n</em> trades.</p><p>So what we need is an algorithm that will find a cycle on the graph of markets, where the product of edge weights is greater than 1. You might be able to invent an algorithm to do that - but in computer science, as in life in general, it’s useful to reduce problems to ones you already know how to solve.</p><h3><strong>The Bellman-Ford Algorithm</strong></h3><p>The problem of finding shortest paths is a common and fundamental problem in computer science, which can be applied to many different scenarios. An obvious one, by drawing a correspondence between a graph and a map, is that of finding the shortest route on a map. But with some cleverness, many other kinds of problems can be transformed into a shortest-path problem, as well. What I’m going to prove to you is that the problem of finding arbitrage opportunities is one such problem.</p><p>First, let’s establish what the shortest path problem is. Given two nodes in a graph, <em>s</em> and <em>t</em>, the shortest path is that path which minimizes the <em>sum</em> of edge weights. In other words, we move along the path from <em>s</em> to <em>t</em>, adding up edge weights along the way, the path with the minimum sum is the shortest path — the path with the smallest cost.</p><p>Next, it will be helpful to understand that there are different classes of shortest-path problems. In the obvious example — like the shortest route on a map — edge weights must be positive. There’s no way, barring a time machine, that driving down a road will reduce your travel time. In a graph with only positive edge weights, Dijkstra’s famous algorithm will compute the shortest path to all nodes in the graph.</p><p>However, there is no reason a graph cannot have negative edge weights. In that case, moving along that edge reduces the total cost of the path. But, if you have a <em>cycle</em> which has a negative weight, then you can keep traversing that cycle forever — every time, lowering your overall cost of the path — and your shortest path will have a cost approaching -∞. In that case, it would be very useful for our shortest-path algorithm to have a mechanism to identify negative weight cycles. Otherwise the shortest path would get stuck circling the negative weight cycle, forever.</p><p>The Bellman-Ford algorithm is exactly that algorithm. A more general version of Dijkstra’s shortest-path algorithm, it can handle negative weights. To do so, it detects <em>negative weight cycles —</em> cycles in a graph along which <em>adding</em> up the weights produces a negative value.</p><p>But how does an algorithm which can find cycles where the <strong><em>sum</em></strong> of edges is less than 0 help us, when we need an algorithm that can detect cycles where the <strong><em>product</em></strong> of edges is greater than 1?</p><h3><strong>Log to the Rescue</strong></h3><p>The next insight is that a product can be turned into a sum by applying the logarithmic function, thanks to the identity:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/518/1*ExpP-9qVrFwTyS9gV6CH1g.png" /></figure><p>Thereby we can transform our problem of finding a cycle with a <em>product</em> greater than 1, to a problem of finding a cycle with a <em>sum</em> greater than 0! We do that by taking the log of each exchange rate, and using that as the weight of each edge.</p><p>Let’s show that by taking the log of both sides of our inequality. First, taking the log of the left-hand side transforms the problem of computing a product into computing a sum:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ysNd2hGPS3emin_cXO0MCA.png" /></figure><p>The log of the right side just transforms the 1 to a 0:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/840/1*Oa88fCo5hdGTwZnG0lwCZQ.png" /></figure><p>We’re close, but not quite there. The final step, to reduce our problem to one that we can solve with this known algorithm, is to multiply each edge weight by -1. This turns the problem of finding a positive weight cycle, into finding a negative one:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/385/1*J5bFE82T3H-3d_dboSOPPg.png" /></figure><p>Which we know the Bellman-Ford algorithm can do! Constructing a graph as specified and executing the Bellman-Ford algorithm on it will quickly and efficiently find arbitrage opportunities for us, because we’ve turned the arbitrage problem into the problem of finding the shortest path — <em>the infinitely shortest path</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/448/1*Frs67B7K1F6C9baQLnh_2g.png" /><figcaption>We need to find a negative weight cycle, where the weights are the negative logarithm of the exchange rates.</figcaption></figure><p>In hindsight, it’s obvious that there should be a correspondence between a negative weight cycle — which lowers the cost of the path every time you traverse it — to an arbitrage opportunity, which makes you a profit every time you traverse it. The key insight is transforming a problem of finding a product greater than 1 into finding a sum less than 0, by applying -log to the edge weights.</p><h3><strong>Prove It</strong></h3><p>Let’s run this algorithm on our exchange rates to see if it correctly identifies the arbitrage opportunity. Transforming the exchange rates by -log, we get:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*vIYKXimQ5NcSROie5-FOxQ.png" /></figure><p>Summing over the trades, our equality holds- <em>we found a negative weight cycle!</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OlHQkB6kGaFA4tHKgQ_NlQ.png" /></figure><p>We can undo the logarithmic operation to restore the product, and calculate the return:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/560/1*DnGdu9InQNwVkCWchH9RwQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/655/1*TPpfqACMfR_OXZxGwjquHw.png" /></figure><p>Which is exactly the 4% return we calculated earlier.</p><h3><strong>In the Real World</strong></h3><p>Since an arbitrage opportunity corresponds to a negative weight cycle, it seems that we could traverse the cycle forever to make infinite money. Of course, that is not the case.</p><p>The liquidity — the volume available before the price changes significantly- available for any arbitrage opportunity is limited, and is quickly exploited by algorithmic traders pushing the boundaries of computing technology and the laws of physics to beat each other.</p><p>That being said, I hope you found this exercise in applying graph theory and a well known shortest path algorithm to solving a problem in the finance domain — and making money — as interesting as I always have.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d8d3ee18c080" width="1" height="1" alt=""><hr><p><a href="https://medium.com/swlh/arbitrage-as-a-shortest-path-problem-d8d3ee18c080">Arbitrage as a Shortest-Path Problem</a> was originally published in <a href="https://medium.com/swlh">The Startup</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>